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 ArgList; 43 class CollectorBlock; 44 class JSCell; 45 class JSGlobalData; 46 class JSValuePtr; 47 48 enum OperationInProgress { NoOperation, Allocation, Collection }; 49 enum HeapType { PrimaryHeap, NumberHeap }; 50 51 template <HeapType> class CollectorHeapIterator; 52 53 struct CollectorHeap { 54 CollectorBlock** blocks; 55 size_t numBlocks; 56 size_t usedBlocks; 57 size_t firstBlockWithPossibleSpace; 58 59 size_t numLiveObjects; 60 size_t numLiveObjectsAtLastCollect; 61 size_t extraCost; 62 63 OperationInProgress operationInProgress; 64 }; 65 66 class Heap : Noncopyable { 67 public: 68 class Thread; 69 typedef CollectorHeapIterator<PrimaryHeap> iterator; 70 71 void destroy(); 72 73 #ifdef JAVASCRIPTCORE_BUILDING_ALL_IN_ONE_FILE 74 // We can inline these functions because everything is compiled as 75 // one file, so the heapAllocate template definitions are available. 76 // However, allocateNumber is used via jsNumberCell outside JavaScriptCore. 77 // Thus allocateNumber needs to provide a non-inline version too. inlineAllocateNumber(size_t s)78 void* inlineAllocateNumber(size_t s) { return heapAllocate<NumberHeap>(s); } inlineAllocate(size_t s)79 void* inlineAllocate(size_t s) { return heapAllocate<PrimaryHeap>(s); } 80 #endif 81 void* allocateNumber(size_t); 82 void* allocate(size_t); 83 84 bool collect(); 85 bool isBusy(); // true if an allocation or collection is in progress 86 87 static const size_t minExtraCostSize = 256; 88 89 void reportExtraMemoryCost(size_t cost); 90 91 size_t objectCount(); 92 struct Statistics { 93 size_t size; 94 size_t free; 95 }; 96 Statistics statistics() const; 97 98 void setGCProtectNeedsLocking(); 99 void protect(JSValuePtr); 100 void unprotect(JSValuePtr); 101 102 static Heap* heap(JSValuePtr); // 0 for immediate values 103 104 size_t globalObjectCount(); 105 size_t protectedObjectCount(); 106 size_t protectedGlobalObjectCount(); 107 HashCountedSet<const char*>* protectedObjectTypeCounts(); 108 109 void registerThread(); // Only needs to be called by clients that can use the same heap from multiple threads. 110 111 static bool isCellMarked(const JSCell*); 112 static void markCell(JSCell*); 113 114 void markConservatively(void* start, void* end); 115 markListSet()116 HashSet<ArgList*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<ArgList*>; return *m_markListSet; } 117 globalData()118 JSGlobalData* globalData() const { return m_globalData; } 119 static bool isNumber(JSCell*); 120 121 // Iterators for the object heap. 122 iterator primaryHeapBegin(); 123 iterator primaryHeapEnd(); 124 125 private: 126 template <HeapType heapType> void* heapAllocate(size_t); 127 template <HeapType heapType> size_t sweep(); 128 static CollectorBlock* cellBlock(const JSCell*); 129 static size_t cellOffset(const JSCell*); 130 131 friend class JSGlobalData; 132 Heap(JSGlobalData*); 133 ~Heap(); 134 135 void recordExtraCost(size_t); 136 void markProtectedObjects(); 137 void markCurrentThreadConservatively(); 138 void markCurrentThreadConservativelyInternal(); 139 void markOtherThreadConservatively(Thread*); 140 void markStackObjectsConservatively(); 141 142 typedef HashCountedSet<JSCell*> ProtectCountSet; 143 144 CollectorHeap primaryHeap; 145 CollectorHeap numberHeap; 146 147 OwnPtr<Mutex> m_protectedValuesMutex; // Only non-null if the client explicitly requested it via setGCPrtotectNeedsLocking(). 148 ProtectCountSet m_protectedValues; 149 150 HashSet<ArgList*>* m_markListSet; 151 152 #if ENABLE(JSC_MULTIPLE_THREADS) 153 void makeUsableFromMultipleThreads(); 154 155 static void unregisterThread(void*); 156 void unregisterThread(); 157 158 Mutex m_registeredThreadsMutex; 159 Thread* m_registeredThreads; 160 pthread_key_t m_currentThreadRegistrar; 161 #endif 162 163 JSGlobalData* m_globalData; 164 }; 165 166 // tunable parameters 167 template<size_t bytesPerWord> struct CellSize; 168 169 // cell size needs to be a power of two for certain optimizations in collector.cpp 170 template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; }; // 32-bit 171 template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; // 64-bit 172 const size_t BLOCK_SIZE = 16 * 4096; // 64k 173 174 // derived constants 175 const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1; 176 const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK; 177 const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value; 178 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0); 179 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double); 180 const size_t SMALL_CELL_SIZE = CELL_SIZE / 2; 181 const size_t CELL_MASK = CELL_SIZE - 1; 182 const size_t CELL_ALIGN_MASK = ~CELL_MASK; 183 const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2); 184 const size_t SMALL_CELLS_PER_BLOCK = 2 * CELLS_PER_BLOCK; 185 const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8; 186 const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t); 187 188 struct CollectorBitmap { 189 uint32_t bits[BITMAP_WORDS]; 190 bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 191 void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 192 void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 193 void clearAll() { memset(bits, 0, sizeof(bits)); } 194 }; 195 196 struct CollectorCell { 197 union { 198 double memory[CELL_ARRAY_LENGTH]; 199 struct { 200 void* zeroIfFree; 201 ptrdiff_t next; 202 } freeCell; 203 } u; 204 }; 205 206 struct SmallCollectorCell { 207 union { 208 double memory[CELL_ARRAY_LENGTH / 2]; 209 struct { 210 void* zeroIfFree; 211 ptrdiff_t next; 212 } freeCell; 213 } u; 214 }; 215 216 class CollectorBlock { 217 public: 218 CollectorCell cells[CELLS_PER_BLOCK]; 219 uint32_t usedCells; 220 CollectorCell* freeList; 221 CollectorBitmap marked; 222 Heap* heap; 223 HeapType type; 224 }; 225 226 class SmallCellCollectorBlock { 227 public: 228 SmallCollectorCell cells[SMALL_CELLS_PER_BLOCK]; 229 uint32_t usedCells; 230 SmallCollectorCell* freeList; 231 CollectorBitmap marked; 232 Heap* heap; 233 HeapType type; 234 }; 235 236 template <HeapType heapType> struct HeapConstants; 237 238 template <> struct HeapConstants<PrimaryHeap> { 239 static const size_t cellSize = CELL_SIZE; 240 static const size_t cellsPerBlock = CELLS_PER_BLOCK; 241 static const size_t bitmapShift = 0; 242 typedef CollectorCell Cell; 243 typedef CollectorBlock Block; 244 }; 245 246 template <> struct HeapConstants<NumberHeap> { 247 static const size_t cellSize = SMALL_CELL_SIZE; 248 static const size_t cellsPerBlock = SMALL_CELLS_PER_BLOCK; 249 static const size_t bitmapShift = 1; 250 typedef SmallCollectorCell Cell; 251 typedef SmallCellCollectorBlock Block; 252 }; 253 254 inline CollectorBlock* Heap::cellBlock(const JSCell* cell) 255 { 256 return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK); 257 } 258 259 inline bool Heap::isNumber(JSCell* cell) 260 { 261 return Heap::cellBlock(cell)->type == NumberHeap; 262 } 263 264 inline size_t Heap::cellOffset(const JSCell* cell) 265 { 266 return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE; 267 } 268 269 inline bool Heap::isCellMarked(const JSCell* cell) 270 { 271 return cellBlock(cell)->marked.get(cellOffset(cell)); 272 } 273 274 inline void Heap::markCell(JSCell* cell) 275 { 276 cellBlock(cell)->marked.set(cellOffset(cell)); 277 } 278 279 inline void Heap::reportExtraMemoryCost(size_t cost) 280 { 281 if (cost > minExtraCostSize) 282 recordExtraCost(cost / (CELL_SIZE * 2)); 283 } 284 285 } // namespace JSC 286 287 #endif /* Collector_h */ 288