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