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