runtime/Collector.h

   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 MarkedArgumentBuffer;
  43     class CollectorBlock;
  44     class JSCell;
  45     class JSGlobalData;
  46     class JSValue;
  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.
  78         void* inlineAllocateNumber(size_t s) { return heapAllocate<NumberHeap>(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(JSValue);
 100         void unprotect(JSValue);
 101
 102         static Heap* heap(JSValue); // 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
 116         HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
 117
 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<MarkedArgumentBuffer*>* 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 #if USE(JSVALUE32)
 171     template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; };
 172 #else
 173     template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 64; };
 174 #endif
 175     template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; };
 176
 177     const size_t BLOCK_SIZE = 16 * 4096; // 64k
 178
 179     // derived constants
 180     const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
 181     const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
 182     const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
 183     const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
 184     const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
 185     const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
 186     const size_t CELL_MASK = CELL_SIZE - 1;
 187     const size_t CELL_ALIGN_MASK = ~CELL_MASK;
 188     const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2);
 189     const size_t SMALL_CELLS_PER_BLOCK = 2 * CELLS_PER_BLOCK;
 190     const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
 191     const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
 192
 193     struct CollectorBitmap {
 194         uint32_t bits[BITMAP_WORDS];
 195         bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); }
 196         void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); }
 197         void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); }
 198         void clearAll() { memset(bits, 0, sizeof(bits)); }
 199     };
 200
 201     struct CollectorCell {
 202         union {
 203             double memory[CELL_ARRAY_LENGTH];
 204             struct {
 205                 void* zeroIfFree;
 206                 ptrdiff_t next;
 207             } freeCell;
 208         } u;
 209     };
 210
 211     struct SmallCollectorCell {
 212         union {
 213             double memory[CELL_ARRAY_LENGTH / 2];
 214             struct {
 215                 void* zeroIfFree;
 216                 ptrdiff_t next;
 217             } freeCell;
 218         } u;
 219     };
 220
 221     class CollectorBlock {
 222     public:
 223         CollectorCell cells[CELLS_PER_BLOCK];
 224         uint32_t usedCells;
 225         CollectorCell* freeList;
 226         CollectorBitmap marked;
 227         Heap* heap;
 228         HeapType type;
 229     };
 230
 231     class SmallCellCollectorBlock {
 232     public:
 233         SmallCollectorCell cells[SMALL_CELLS_PER_BLOCK];
 234         uint32_t usedCells;
 235         SmallCollectorCell* freeList;
 236         CollectorBitmap marked;
 237         Heap* heap;
 238         HeapType type;
 239     };
 240
 241     template <HeapType heapType> struct HeapConstants;
 242
 243     template <> struct HeapConstants<PrimaryHeap> {
 244         static const size_t cellSize = CELL_SIZE;
 245         static const size_t cellsPerBlock = CELLS_PER_BLOCK;
 246         static const size_t bitmapShift = 0;
 247         typedef CollectorCell Cell;
 248         typedef CollectorBlock Block;
 249     };
 250
 251     template <> struct HeapConstants<NumberHeap> {
 252         static const size_t cellSize = SMALL_CELL_SIZE;
 253         static const size_t cellsPerBlock = SMALL_CELLS_PER_BLOCK;
 254         static const size_t bitmapShift = 1;
 255         typedef SmallCollectorCell Cell;
 256         typedef SmallCellCollectorBlock Block;
 257     };
 258
 259     inline CollectorBlock* Heap::cellBlock(const JSCell* cell)
 260     {
 261         return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
 262     }
 263
 264     inline bool Heap::isNumber(JSCell* cell)
 265     {
 266         return Heap::cellBlock(cell)->type == NumberHeap;
 267     }
 268
 269     inline size_t Heap::cellOffset(const JSCell* cell)
 270     {
 271         return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
 272     }
 273
 274     inline bool Heap::isCellMarked(const JSCell* cell)
 275     {
 276         return cellBlock(cell)->marked.get(cellOffset(cell));
 277     }
 278
 279     inline void Heap::markCell(JSCell* cell)
 280     {
 281         cellBlock(cell)->marked.set(cellOffset(cell));
 282     }
 283
 284     inline void Heap::reportExtraMemoryCost(size_t cost)
 285     {
 286         if (cost > minExtraCostSize)
 287             recordExtraCost(cost / (CELL_SIZE * 2));
 288     }
 289
 290 } // namespace JSC
 291
 292 #endif /* Collector_h */