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