2011-01-10 Geoffrey Garen <ggaren@apple.com>
[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         size_t numBlocks;
69         size_t usedBlocks;
70
71         size_t extraCost;
72         bool didShrink;
73
74         OperationInProgress operationInProgress;
75
76         CollectorBlock* collectorBlock(size_t index) const
77         {
78             return static_cast<CollectorBlock*>(blocks[index].base());
79         }
80     };
81
82     class Heap : public Noncopyable {
83     public:
84         void destroy();
85
86         void* allocate(size_t);
87
88         bool isBusy(); // true if an allocation or collection is in progress
89         void collectAllGarbage();
90
91         GCActivityCallback* activityCallback();
92         void setActivityCallback(PassOwnPtr<GCActivityCallback>);
93
94         static const size_t minExtraCost = 256;
95         static const size_t maxExtraCost = 1024 * 1024;
96
97         void reportExtraMemoryCost(size_t cost);
98
99         size_t objectCount() const;
100         struct Statistics {
101             size_t size;
102             size_t free;
103         };
104         Statistics statistics() const;
105         size_t size() const;
106
107         void protect(JSValue);
108         // Returns true if the value is no longer protected by any protect pointers
109         // (though it may still be alive due to heap/stack references).
110         bool unprotect(JSValue);
111
112         static Heap* heap(JSValue); // 0 for immediate values
113         static Heap* heap(JSCell*);
114
115         size_t globalObjectCount();
116         size_t protectedObjectCount();
117         size_t protectedGlobalObjectCount();
118         HashCountedSet<const char*>* protectedObjectTypeCounts();
119         HashCountedSet<const char*>* objectTypeCounts();
120
121         static bool isCellMarked(const JSCell*);
122         static bool checkMarkCell(const JSCell*);
123         static void markCell(JSCell*);
124
125         WeakGCHandle* addWeakGCHandle(JSCell*);
126
127         void markConservatively(MarkStack&, void* start, void* end);
128
129         void pushTempSortVector(WTF::Vector<ValueStringPair>*);
130         void popTempSortVector(WTF::Vector<ValueStringPair>*);        
131
132         HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
133
134         JSGlobalData* globalData() const { return m_globalData; }
135         static bool isNumber(JSCell*);
136         
137         LiveObjectIterator primaryHeapBegin();
138         LiveObjectIterator primaryHeapEnd();
139
140         MachineStackMarker& machineStackMarker() { return m_machineStackMarker; }
141
142     private:
143         void reset();
144         void sweep();
145         static CollectorBlock* cellBlock(const JSCell*);
146         static size_t cellOffset(const JSCell*);
147
148         friend class JSGlobalData;
149         Heap(JSGlobalData*);
150         ~Heap();
151
152         NEVER_INLINE CollectorBlock* allocateBlock();
153         NEVER_INLINE void freeBlock(size_t);
154         void freeBlocks();
155         void resizeBlocks();
156         void growBlocks(size_t neededBlocks);
157         void shrinkBlocks(size_t neededBlocks);
158         void clearMarkBits();
159         void clearMarkBits(CollectorBlock*);
160         size_t markedCells(size_t startBlock = 0, size_t startCell = 0) const;
161
162         void recordExtraCost(size_t);
163
164         void addToStatistics(Statistics&) const;
165
166         void markRoots();
167         void markProtectedObjects(MarkStack&);
168         void markTempSortVectors(MarkStack&);
169
170         void updateWeakGCHandles();
171         WeakGCHandlePool* weakGCHandlePool(size_t index);
172
173         typedef HashCountedSet<JSCell*> ProtectCountSet;
174
175         CollectorHeap m_heap;
176
177         ProtectCountSet m_protectedValues;
178         WTF::Vector<PageAllocationAligned> m_weakGCHandlePools;
179         WTF::Vector<WTF::Vector<ValueStringPair>* > m_tempSortingVectors;
180
181         HashSet<MarkedArgumentBuffer*>* m_markListSet;
182
183         OwnPtr<GCActivityCallback> m_activityCallback;
184
185         JSGlobalData* m_globalData;
186         
187         MachineStackMarker m_machineStackMarker;
188     };
189
190     // tunable parameters
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 = 64;
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         FixedArray<uint32_t, BITMAP_WORDS> bits;
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         bool getset(size_t n)
210         {
211             unsigned i = (1 << (n & 0x1F));
212             uint32_t& b = bits[n >> 5];
213             bool r = !!(b & i);
214             b |= i;
215             return r;
216         } 
217         void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 
218         void clearAll() { memset(bits.data(), 0, sizeof(bits)); }
219         ALWAYS_INLINE void advanceToNextPossibleFreeCell(size_t& startCell)
220         {
221             if (!~bits[startCell >> 5])
222                 startCell = (startCell & (~0x1F)) + 32;
223             else
224                 ++startCell;
225         }
226         size_t count(size_t startCell = 0)
227         {
228             size_t result = 0;
229             for ( ; (startCell & 0x1F) != 0; ++startCell) {
230                 if (get(startCell))
231                     ++result;
232             }
233             for (size_t i = startCell >> 5; i < BITMAP_WORDS; ++i)
234                 result += WTF::bitCount(bits[i]);
235             return result;
236         }
237         size_t isEmpty() // Much more efficient than testing count() == 0.
238         {
239             for (size_t i = 0; i < BITMAP_WORDS; ++i)
240                 if (bits[i] != 0)
241                     return false;
242             return true;
243         }
244     };
245   
246     struct CollectorCell {
247         FixedArray<double, CELL_ARRAY_LENGTH> memory;
248     };
249
250     class CollectorBlock {
251     public:
252         FixedArray<CollectorCell, CELLS_PER_BLOCK> cells;
253         CollectorBitmap marked;
254         Heap* heap;
255     };
256
257     struct HeapConstants {
258         static const size_t cellSize = CELL_SIZE;
259         static const size_t cellsPerBlock = CELLS_PER_BLOCK;
260         typedef CollectorCell Cell;
261         typedef CollectorBlock Block;
262     };
263
264     inline CollectorBlock* Heap::cellBlock(const JSCell* cell)
265     {
266         return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
267     }
268
269     inline size_t Heap::cellOffset(const JSCell* cell)
270     {
271         return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
272     }
273
274     inline bool Heap::isCellMarked(const JSCell* cell)
275     {
276         return cellBlock(cell)->marked.get(cellOffset(cell));
277     }
278
279     inline bool Heap::checkMarkCell(const JSCell* cell)
280     {
281         return cellBlock(cell)->marked.getset(cellOffset(cell));
282     }
283
284     inline void Heap::markCell(JSCell* cell)
285     {
286         cellBlock(cell)->marked.set(cellOffset(cell));
287     }
288
289     inline void Heap::reportExtraMemoryCost(size_t cost)
290     {
291         if (cost > minExtraCost) 
292             recordExtraCost(cost);
293     }
294     
295     inline WeakGCHandlePool* Heap::weakGCHandlePool(size_t index)
296     {
297         return static_cast<WeakGCHandlePool*>(m_weakGCHandlePools[index].base());
298     }
299 } // namespace JSC
300
301 #endif /* Heap_h */