Home | History | Annotate | Download | only in runtime 
      1 /*
      2  *  Copyright (C) 1999-2000 Harri Porten (porten (at) kde.org)
      3  *  Copyright (C) 2001 Peter Kelly (pmk (at) 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 
    112         HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
    113 
    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