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