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/StdLibExtras.h> 32 #include <wtf/Threading.h> 33 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 51 class LiveObjectIterator; 52 53 struct CollectorHeap { 54 size_t nextBlock; 55 size_t nextCell; 56 CollectorBlock** blocks; 57 58 void* nextNumber; 59 60 size_t numBlocks; 61 size_t usedBlocks; 62 63 size_t extraCost; 64 bool didShrink; 65 66 OperationInProgress operationInProgress; 67 }; 68 69 class Heap : public Noncopyable { 70 public: 71 class Thread; 72 73 void destroy(); 74 75 void* allocateNumber(size_t); 76 void* allocate(size_t); 77 78 bool isBusy(); // true if an allocation or collection is in progress 79 void collectAllGarbage(); 80 81 static const size_t minExtraCost = 256; 82 static const size_t maxExtraCost = 1024 * 1024; 83 84 void reportExtraMemoryCost(size_t cost); 85 86 size_t objectCount() const; 87 struct Statistics { 88 size_t size; 89 size_t free; 90 }; 91 Statistics statistics() const; 92 93 void protect(JSValue); 94 void unprotect(JSValue); 95 96 static Heap* heap(JSValue); // 0 for immediate values 97 static Heap* heap(JSCell*); 98 99 size_t globalObjectCount(); 100 size_t protectedObjectCount(); 101 size_t protectedGlobalObjectCount(); 102 HashCountedSet<const char*>* protectedObjectTypeCounts(); 103 HashCountedSet<const char*>* objectTypeCounts(); 104 105 void registerThread(); // Only needs to be called by clients that can use the same heap from multiple threads. 106 107 static bool isCellMarked(const JSCell*); 108 static void markCell(JSCell*); 109 110 void markConservatively(MarkStack&, void* start, void* end); 111 markListSet()112 HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; } 113 globalData()114 JSGlobalData* globalData() const { return m_globalData; } 115 static bool isNumber(JSCell*); 116 117 LiveObjectIterator primaryHeapBegin(); 118 LiveObjectIterator primaryHeapEnd(); 119 120 private: 121 void reset(); 122 void sweep(); 123 static CollectorBlock* cellBlock(const JSCell*); 124 static size_t cellOffset(const JSCell*); 125 126 friend class JSGlobalData; 127 Heap(JSGlobalData*); 128 ~Heap(); 129 130 NEVER_INLINE CollectorBlock* allocateBlock(); 131 NEVER_INLINE void freeBlock(size_t); 132 NEVER_INLINE void freeBlockPtr(CollectorBlock*); 133 void freeBlocks(); 134 void resizeBlocks(); 135 void growBlocks(size_t neededBlocks); 136 void shrinkBlocks(size_t neededBlocks); 137 void clearMarkBits(); 138 void clearMarkBits(CollectorBlock*); 139 size_t markedCells(size_t startBlock = 0, size_t startCell = 0) const; 140 141 void recordExtraCost(size_t); 142 143 void addToStatistics(Statistics&) const; 144 145 void markRoots(); 146 void markProtectedObjects(MarkStack&); 147 void markCurrentThreadConservatively(MarkStack&); 148 void markCurrentThreadConservativelyInternal(MarkStack&); 149 void markOtherThreadConservatively(MarkStack&, Thread*); 150 void markStackObjectsConservatively(MarkStack&); 151 152 typedef HashCountedSet<JSCell*> ProtectCountSet; 153 154 CollectorHeap m_heap; 155 156 ProtectCountSet m_protectedValues; 157 158 HashSet<MarkedArgumentBuffer*>* m_markListSet; 159 160 #if ENABLE(JSC_MULTIPLE_THREADS) 161 void makeUsableFromMultipleThreads(); 162 163 static void unregisterThread(void*); 164 void unregisterThread(); 165 166 Mutex m_registeredThreadsMutex; 167 Thread* m_registeredThreads; 168 pthread_key_t m_currentThreadRegistrar; 169 #endif 170 171 JSGlobalData* m_globalData; 172 }; 173 174 // tunable parameters 175 template<size_t bytesPerWord> struct CellSize; 176 177 // cell size needs to be a power of two for certain optimizations in collector.cpp 178 #if USE(JSVALUE32) 179 template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; }; 180 #else 181 template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 64; }; 182 #endif 183 template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; 184 185 #if OS(WINCE) || OS(SYMBIAN) 186 const size_t BLOCK_SIZE = 64 * 1024; // 64k 187 #else 188 const size_t BLOCK_SIZE = 64 * 4096; // 256k 189 #endif 190 191 // derived constants 192 const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1; 193 const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK; 194 const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value; 195 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0); 196 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double); 197 const size_t SMALL_CELL_SIZE = CELL_SIZE / 2; 198 const size_t CELL_MASK = CELL_SIZE - 1; 199 const size_t CELL_ALIGN_MASK = ~CELL_MASK; 200 const size_t CELLS_PER_BLOCK = (BLOCK_SIZE - sizeof(Heap*)) * 8 * CELL_SIZE / (8 * CELL_SIZE + 1) / CELL_SIZE; // one bitmap byte can represent 8 cells. 201 202 const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8; 203 const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t); 204 205 struct CollectorBitmap { 206 uint32_t bits[BITMAP_WORDS]; 207 bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 208 void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 209 void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 210 void clearAll() { memset(bits, 0, sizeof(bits)); } 211 size_t count(size_t startCell = 0) 212 { 213 size_t result = 0; 214 for ( ; (startCell & 0x1F) != 0; ++startCell) { 215 if (get(startCell)) 216 ++result; 217 } 218 for (size_t i = startCell >> 5; i < BITMAP_WORDS; ++i) 219 result += WTF::bitCount(bits[i]); 220 return result; 221 } 222 size_t isEmpty() // Much more efficient than testing count() == 0. 223 { 224 for (size_t i = 0; i < BITMAP_WORDS; ++i) 225 if (bits[i] != 0) 226 return false; 227 return true; 228 } 229 }; 230 231 struct CollectorCell { 232 double memory[CELL_ARRAY_LENGTH]; 233 }; 234 235 class CollectorBlock { 236 public: 237 CollectorCell cells[CELLS_PER_BLOCK]; 238 CollectorBitmap marked; 239 Heap* heap; 240 }; 241 242 struct HeapConstants { 243 static const size_t cellSize = CELL_SIZE; 244 static const size_t cellsPerBlock = CELLS_PER_BLOCK; 245 typedef CollectorCell Cell; 246 typedef CollectorBlock Block; 247 }; 248 249 inline CollectorBlock* Heap::cellBlock(const JSCell* cell) 250 { 251 return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK); 252 } 253 254 inline size_t Heap::cellOffset(const JSCell* cell) 255 { 256 return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE; 257 } 258 259 inline bool Heap::isCellMarked(const JSCell* cell) 260 { 261 return cellBlock(cell)->marked.get(cellOffset(cell)); 262 } 263 264 inline void Heap::markCell(JSCell* cell) 265 { 266 cellBlock(cell)->marked.set(cellOffset(cell)); 267 } 268 269 inline void Heap::reportExtraMemoryCost(size_t cost) 270 { 271 if (cost > minExtraCost) 272 recordExtraCost(cost); 273 } 274 275 inline void* Heap::allocateNumber(size_t s) 276 { 277 if (void* result = m_heap.nextNumber) { 278 m_heap.nextNumber = 0; 279 return result; 280 } 281 282 void* result = allocate(s); 283 m_heap.nextNumber = static_cast<char*>(result) + (CELL_SIZE / 2); 284 return result; 285 } 286 287 } // namespace JSC 288 289 #endif /* Collector_h */ 290