1 /* 2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 3 * Copyright (C) 2001 Peter Kelly (pmk@post.com) 4 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved. 5 * 6 * This library is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU Lesser General Public 8 * License as published by the Free Software Foundation; either 9 * version 2 of the License, or (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 * Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public 17 * License along with this library; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 19 * 20 */ 21 22 #ifndef Collector_h 23 #define Collector_h 24 25 #include <stddef.h> 26 #include <string.h> 27 #include <wtf/HashCountedSet.h> 28 #include <wtf/HashSet.h> 29 #include <wtf/Noncopyable.h> 30 #include <wtf/OwnPtr.h> 31 #include <wtf/Threading.h> 32 33 // This is supremely lame that we require pthreads to build on windows. 34 #if ENABLE(JSC_MULTIPLE_THREADS) 35 #include <pthread.h> 36 #endif 37 38 #define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) <= CELL_SIZE, class_fits_in_cell) 39 40 namespace JSC { 41 42 class CollectorBlock; 43 class JSCell; 44 class JSGlobalData; 45 class JSValue; 46 class MarkedArgumentBuffer; 47 class MarkStack; 48 49 enum OperationInProgress { NoOperation, Allocation, Collection }; 50 enum HeapType { PrimaryHeap, NumberHeap }; 51 52 template <HeapType> class CollectorHeapIterator; 53 54 struct CollectorHeap { 55 CollectorBlock** blocks; 56 size_t numBlocks; 57 size_t usedBlocks; 58 size_t firstBlockWithPossibleSpace; 59 60 size_t numLiveObjects; 61 size_t numLiveObjectsAtLastCollect; 62 size_t extraCost; 63 64 OperationInProgress operationInProgress; 65 }; 66 67 class Heap : public Noncopyable { 68 public: 69 class Thread; 70 typedef CollectorHeapIterator<PrimaryHeap> iterator; 71 72 void destroy(); 73 74 #ifdef JAVASCRIPTCORE_BUILDING_ALL_IN_ONE_FILE 75 // We can inline these functions because everything is compiled as 76 // one file, so the heapAllocate template definitions are available. 77 // However, allocateNumber is used via jsNumberCell outside JavaScriptCore. 78 // Thus allocateNumber needs to provide a non-inline version too. inlineAllocateNumber(size_t s)79 void* inlineAllocateNumber(size_t s) { return heapAllocate<NumberHeap>(s); } inlineAllocate(size_t s)80 void* inlineAllocate(size_t s) { return heapAllocate<PrimaryHeap>(s); } 81 #endif 82 void* allocateNumber(size_t); 83 void* allocate(size_t); 84 85 bool collect(); 86 bool isBusy(); // true if an allocation or collection is in progress 87 88 static const size_t minExtraCostSize = 256; 89 90 void reportExtraMemoryCost(size_t cost); 91 92 size_t objectCount(); 93 struct Statistics { 94 size_t size; 95 size_t free; 96 }; 97 Statistics statistics() const; 98 99 void setGCProtectNeedsLocking(); 100 void protect(JSValue); 101 void unprotect(JSValue); 102 103 static Heap* heap(JSValue); // 0 for immediate values 104 105 size_t globalObjectCount(); 106 size_t protectedObjectCount(); 107 size_t protectedGlobalObjectCount(); 108 HashCountedSet<const char*>* protectedObjectTypeCounts(); 109 110 void registerThread(); // Only needs to be called by clients that can use the same heap from multiple threads. 111 112 static bool isCellMarked(const JSCell*); 113 static void markCell(JSCell*); 114 115 void markConservatively(MarkStack&, void* start, void* end); 116 markListSet()117 HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; } 118 globalData()119 JSGlobalData* globalData() const { return m_globalData; } 120 static bool isNumber(JSCell*); 121 122 // Iterators for the object heap. 123 iterator primaryHeapBegin(); 124 iterator primaryHeapEnd(); 125 126 private: 127 template <HeapType heapType> void* heapAllocate(size_t); 128 template <HeapType heapType> size_t sweep(); 129 static CollectorBlock* cellBlock(const JSCell*); 130 static size_t cellOffset(const JSCell*); 131 132 friend class JSGlobalData; 133 Heap(JSGlobalData*); 134 ~Heap(); 135 136 void recordExtraCost(size_t); 137 void markProtectedObjects(MarkStack&); 138 void markCurrentThreadConservatively(MarkStack&); 139 void markCurrentThreadConservativelyInternal(MarkStack&); 140 void markOtherThreadConservatively(MarkStack&, Thread*); 141 void markStackObjectsConservatively(MarkStack&); 142 143 typedef HashCountedSet<JSCell*> ProtectCountSet; 144 145 CollectorHeap primaryHeap; 146 CollectorHeap numberHeap; 147 148 OwnPtr<Mutex> m_protectedValuesMutex; // Only non-null if the client explicitly requested it via setGCPrtotectNeedsLocking(). 149 ProtectCountSet m_protectedValues; 150 151 HashSet<MarkedArgumentBuffer*>* m_markListSet; 152 153 #if ENABLE(JSC_MULTIPLE_THREADS) 154 void makeUsableFromMultipleThreads(); 155 156 static void unregisterThread(void*); 157 void unregisterThread(); 158 159 Mutex m_registeredThreadsMutex; 160 Thread* m_registeredThreads; 161 pthread_key_t m_currentThreadRegistrar; 162 #endif 163 164 JSGlobalData* m_globalData; 165 }; 166 167 // tunable parameters 168 template<size_t bytesPerWord> struct CellSize; 169 170 // cell size needs to be a power of two for certain optimizations in collector.cpp 171 #if USE(JSVALUE32) 172 template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; }; 173 #else 174 template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 64; }; 175 #endif 176 template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; 177 178 const size_t BLOCK_SIZE = 16 * 4096; // 64k 179 180 // derived constants 181 const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1; 182 const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK; 183 const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value; 184 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0); 185 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double); 186 const size_t SMALL_CELL_SIZE = CELL_SIZE / 2; 187 const size_t CELL_MASK = CELL_SIZE - 1; 188 const size_t CELL_ALIGN_MASK = ~CELL_MASK; 189 const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2); 190 const size_t SMALL_CELLS_PER_BLOCK = 2 * CELLS_PER_BLOCK; 191 const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8; 192 const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t); 193 194 struct CollectorBitmap { 195 uint32_t bits[BITMAP_WORDS]; 196 bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 197 void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 198 void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 199 void clearAll() { memset(bits, 0, sizeof(bits)); } 200 }; 201 202 struct CollectorCell { 203 union { 204 double memory[CELL_ARRAY_LENGTH]; 205 struct { 206 void* zeroIfFree; 207 ptrdiff_t next; 208 } freeCell; 209 } u; 210 }; 211 212 struct SmallCollectorCell { 213 union { 214 double memory[CELL_ARRAY_LENGTH / 2]; 215 struct { 216 void* zeroIfFree; 217 ptrdiff_t next; 218 } freeCell; 219 } u; 220 }; 221 222 class CollectorBlock { 223 public: 224 CollectorCell cells[CELLS_PER_BLOCK]; 225 uint32_t usedCells; 226 CollectorCell* freeList; 227 CollectorBitmap marked; 228 Heap* heap; 229 HeapType type; 230 }; 231 232 class SmallCellCollectorBlock { 233 public: 234 SmallCollectorCell cells[SMALL_CELLS_PER_BLOCK]; 235 uint32_t usedCells; 236 SmallCollectorCell* freeList; 237 CollectorBitmap marked; 238 Heap* heap; 239 HeapType type; 240 }; 241 242 template <HeapType heapType> struct HeapConstants; 243 244 template <> struct HeapConstants<PrimaryHeap> { 245 static const size_t cellSize = CELL_SIZE; 246 static const size_t cellsPerBlock = CELLS_PER_BLOCK; 247 static const size_t bitmapShift = 0; 248 typedef CollectorCell Cell; 249 typedef CollectorBlock Block; 250 }; 251 252 template <> struct HeapConstants<NumberHeap> { 253 static const size_t cellSize = SMALL_CELL_SIZE; 254 static const size_t cellsPerBlock = SMALL_CELLS_PER_BLOCK; 255 static const size_t bitmapShift = 1; 256 typedef SmallCollectorCell Cell; 257 typedef SmallCellCollectorBlock Block; 258 }; 259 260 inline CollectorBlock* Heap::cellBlock(const JSCell* cell) 261 { 262 return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK); 263 } 264 265 inline bool Heap::isNumber(JSCell* cell) 266 { 267 return Heap::cellBlock(cell)->type == NumberHeap; 268 } 269 270 inline size_t Heap::cellOffset(const JSCell* cell) 271 { 272 return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE; 273 } 274 275 inline bool Heap::isCellMarked(const JSCell* cell) 276 { 277 return cellBlock(cell)->marked.get(cellOffset(cell)); 278 } 279 280 inline void Heap::markCell(JSCell* cell) 281 { 282 cellBlock(cell)->marked.set(cellOffset(cell)); 283 } 284 285 inline void Heap::reportExtraMemoryCost(size_t cost) 286 { 287 if (cost > minExtraCostSize) 288 recordExtraCost(cost / (CELL_SIZE * 2)); 289 } 290 291 } // namespace JSC 292 293 #endif /* Collector_h */ 294