--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/JavaScriptCore/runtime/Collector.h Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,309 @@
+/*
+ * Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
+ * Copyright (C) 2001 Peter Kelly (pmk@post.com)
+ * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifndef Collector_h
+#define Collector_h
+
+#include <stddef.h>
+#include <string.h>
+#include <wtf/FixedArray.h>
+#include <wtf/HashCountedSet.h>
+#include <wtf/HashSet.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/OwnPtr.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Threading.h>
+
+#if ENABLE(JSC_MULTIPLE_THREADS)
+#include <pthread.h>
+#endif
+
+#if OS(SYMBIAN)
+#include <wtf/symbian/BlockAllocatorSymbian.h>
+#endif
+
+#define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) <= CELL_SIZE, class_fits_in_cell)
+
+namespace JSC {
+
+ class CollectorBlock;
+ class JSCell;
+ class JSGlobalData;
+ class JSValue;
+ class MarkedArgumentBuffer;
+ class MarkStack;
+
+ enum OperationInProgress { NoOperation, Allocation, Collection };
+
+ class LiveObjectIterator;
+
+ struct CollectorHeap {
+ size_t nextBlock;
+ size_t nextCell;
+ CollectorBlock** blocks;
+
+ void* nextNumber;
+
+ size_t numBlocks;
+ size_t usedBlocks;
+
+ size_t extraCost;
+ bool didShrink;
+
+ OperationInProgress operationInProgress;
+ };
+
+ class Heap : public Noncopyable {
+ public:
+ class Thread;
+
+ void destroy();
+
+ void* allocateNumber(size_t);
+ void* allocate(size_t);
+
+ bool isBusy(); // true if an allocation or collection is in progress
+ void collectAllGarbage();
+
+ static const size_t minExtraCost = 256;
+ static const size_t maxExtraCost = 1024 * 1024;
+
+ void reportExtraMemoryCost(size_t cost);
+
+ size_t objectCount() const;
+ struct Statistics {
+ size_t size;
+ size_t free;
+ };
+ Statistics statistics() const;
+ size_t size() const;
+
+ void protect(JSValue);
+ // Returns true if the value is no longer protected by any protect pointers
+ // (though it may still be alive due to heap/stack references).
+ bool unprotect(JSValue);
+
+ static Heap* heap(JSValue); // 0 for immediate values
+ static Heap* heap(JSCell*);
+
+ size_t globalObjectCount();
+ size_t protectedObjectCount();
+ size_t protectedGlobalObjectCount();
+ HashCountedSet<const char*>* protectedObjectTypeCounts();
+ HashCountedSet<const char*>* objectTypeCounts();
+
+ void registerThread(); // Only needs to be called by clients that can use the same heap from multiple threads.
+
+ static bool isCellMarked(const JSCell*);
+ static void markCell(JSCell*);
+
+ void markConservatively(MarkStack&, void* start, void* end);
+
+ HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
+
+ JSGlobalData* globalData() const { return m_globalData; }
+ static bool isNumber(JSCell*);
+
+ LiveObjectIterator primaryHeapBegin();
+ LiveObjectIterator primaryHeapEnd();
+
+ private:
+ void reset();
+ void sweep();
+ static CollectorBlock* cellBlock(const JSCell*);
+ static size_t cellOffset(const JSCell*);
+
+ friend class JSGlobalData;
+ Heap(JSGlobalData*);
+ ~Heap();
+
+ NEVER_INLINE CollectorBlock* allocateBlock();
+ NEVER_INLINE void freeBlock(size_t);
+ NEVER_INLINE void freeBlockPtr(CollectorBlock*);
+ void freeBlocks();
+ void resizeBlocks();
+ void growBlocks(size_t neededBlocks);
+ void shrinkBlocks(size_t neededBlocks);
+ void clearMarkBits();
+ void clearMarkBits(CollectorBlock*);
+ size_t markedCells(size_t startBlock = 0, size_t startCell = 0) const;
+
+ void recordExtraCost(size_t);
+
+ void addToStatistics(Statistics&) const;
+
+ void markRoots();
+ void markProtectedObjects(MarkStack&);
+ void markCurrentThreadConservatively(MarkStack&);
+ void markCurrentThreadConservativelyInternal(MarkStack&);
+ void markOtherThreadConservatively(MarkStack&, Thread*);
+ void markStackObjectsConservatively(MarkStack&);
+
+ typedef HashCountedSet<JSCell*> ProtectCountSet;
+
+ CollectorHeap m_heap;
+
+ ProtectCountSet m_protectedValues;
+
+ HashSet<MarkedArgumentBuffer*>* m_markListSet;
+
+#if ENABLE(JSC_MULTIPLE_THREADS)
+ void makeUsableFromMultipleThreads();
+
+ static void unregisterThread(void*);
+ void unregisterThread();
+
+ Mutex m_registeredThreadsMutex;
+ Thread* m_registeredThreads;
+ pthread_key_t m_currentThreadRegistrar;
+#endif
+
+#if OS(SYMBIAN)
+ // Allocates collector blocks with correct alignment
+ WTF::AlignedBlockAllocator m_blockallocator;
+#endif
+
+ JSGlobalData* m_globalData;
+ };
+
+ // tunable parameters
+ template<size_t bytesPerWord> struct CellSize;
+
+ // cell size needs to be a power of two for certain optimizations in collector.cpp
+#if USE(JSVALUE32)
+ template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; };
+#else
+ template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 64; };
+#endif
+ template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; };
+
+#if OS(WINCE) || OS(SYMBIAN)
+ const size_t BLOCK_SIZE = 64 * 1024; // 64k
+#else
+ const size_t BLOCK_SIZE = 64 * 4096; // 256k
+#endif
+
+ // derived constants
+ const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
+ const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
+ const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
+ const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
+ const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
+ const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
+ const size_t CELL_MASK = CELL_SIZE - 1;
+ const size_t CELL_ALIGN_MASK = ~CELL_MASK;
+ 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.
+
+ const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
+ const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
+
+ struct CollectorBitmap {
+ FixedArray<uint32_t, BITMAP_WORDS> bits;
+ bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); }
+ void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); }
+ void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); }
+ void clearAll() { memset(bits.data(), 0, sizeof(bits)); }
+ ALWAYS_INLINE void advanceToNextPossibleFreeCell(size_t& startCell)
+ {
+ if (!~bits[startCell >> 5])
+ startCell = (startCell & (~0x1F)) + 32;
+ else
+ ++startCell;
+ }
+ size_t count(size_t startCell = 0)
+ {
+ size_t result = 0;
+ for ( ; (startCell & 0x1F) != 0; ++startCell) {
+ if (get(startCell))
+ ++result;
+ }
+ for (size_t i = startCell >> 5; i < BITMAP_WORDS; ++i)
+ result += WTF::bitCount(bits[i]);
+ return result;
+ }
+ size_t isEmpty() // Much more efficient than testing count() == 0.
+ {
+ for (size_t i = 0; i < BITMAP_WORDS; ++i)
+ if (bits[i] != 0)
+ return false;
+ return true;
+ }
+ };
+
+ struct CollectorCell {
+ FixedArray<double, CELL_ARRAY_LENGTH> memory;
+ };
+
+ class CollectorBlock {
+ public:
+ FixedArray<CollectorCell, CELLS_PER_BLOCK> cells;
+ CollectorBitmap marked;
+ Heap* heap;
+ };
+
+ struct HeapConstants {
+ static const size_t cellSize = CELL_SIZE;
+ static const size_t cellsPerBlock = CELLS_PER_BLOCK;
+ typedef CollectorCell Cell;
+ typedef CollectorBlock Block;
+ };
+
+ inline CollectorBlock* Heap::cellBlock(const JSCell* cell)
+ {
+ return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
+ }
+
+ inline size_t Heap::cellOffset(const JSCell* cell)
+ {
+ return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
+ }
+
+ inline bool Heap::isCellMarked(const JSCell* cell)
+ {
+ return cellBlock(cell)->marked.get(cellOffset(cell));
+ }
+
+ inline void Heap::markCell(JSCell* cell)
+ {
+ cellBlock(cell)->marked.set(cellOffset(cell));
+ }
+
+ inline void Heap::reportExtraMemoryCost(size_t cost)
+ {
+ if (cost > minExtraCost)
+ recordExtraCost(cost);
+ }
+
+ inline void* Heap::allocateNumber(size_t s)
+ {
+ if (void* result = m_heap.nextNumber) {
+ m_heap.nextNumber = 0;
+ return result;
+ }
+
+ void* result = allocate(s);
+ m_heap.nextNumber = static_cast<char*>(result) + (CELL_SIZE / 2);
+ return result;
+ }
+
+} // namespace JSC
+
+#endif /* Collector_h */