3b23d8c1c0ed2ef3b6fe8f229060606779a7a326
[WebKit.git] / Source / JavaScriptCore / runtime / MarkedSpace.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 MarkedSpace_h
23 #define MarkedSpace_h
24
25 #include "MachineStackMarker.h"
26 #include "PageAllocationAligned.h"
27 #include <wtf/FixedArray.h>
28 #include <wtf/HashCountedSet.h>
29 #include <wtf/Noncopyable.h>
30 #include <wtf/Vector.h>
31
32 namespace JSC {
33
34     class CollectorBlock;
35     class Heap;
36     class JSCell;
37     class JSGlobalData;
38     class LiveObjectIterator;
39     class MarkStack;
40     class WeakGCHandle;
41
42 #if OS(WINCE) || OS(SYMBIAN) || PLATFORM(BREWMP)
43     const size_t BLOCK_SIZE = 64 * 1024; // 64k
44 #else
45     const size_t BLOCK_SIZE = 256 * 1024; // 256k
46 #endif
47
48     typedef HashCountedSet<JSCell*> ProtectCountSet;
49
50     struct CollectorHeap {
51         size_t nextBlock;
52         size_t nextCell;
53         PageAllocationAligned* blocks;
54         
55         size_t numBlocks;
56         size_t usedBlocks;
57
58         CollectorBlock* collectorBlock(size_t index) const
59         {
60             return static_cast<CollectorBlock*>(blocks[index].base());
61         }
62     };
63
64     class MarkedSpace {
65         WTF_MAKE_NONCOPYABLE(MarkedSpace);
66     public:
67         static Heap* heap(JSCell*);
68
69         static bool isCellMarked(const JSCell*);
70         static bool checkMarkCell(const JSCell*);
71         static void markCell(JSCell*);
72
73         MarkedSpace(JSGlobalData*);
74         void destroy(ProtectCountSet&);
75
76         JSGlobalData* globalData() { return m_globalData; }
77
78         void* allocate(size_t);
79
80         void clearMarkBits();
81         void markRoots();
82         void reset();
83         void sweep();
84
85         size_t size() const;
86         size_t capacity() const;
87         size_t objectCount() const;
88
89         bool contains(void*);
90
91         LiveObjectIterator primaryHeapBegin();
92         LiveObjectIterator primaryHeapEnd();
93
94     private:
95         bool isCellAligned(void*);
96         bool isPossibleCell(void*);
97         bool containsSlowCase(void*);
98
99         static CollectorBlock* cellBlock(const JSCell*);
100         static size_t cellOffset(const JSCell*);
101
102         NEVER_INLINE CollectorBlock* allocateBlock();
103         NEVER_INLINE void freeBlock(size_t);
104         void resizeBlocks();
105         void growBlocks(size_t neededBlocks);
106         void shrinkBlocks(size_t neededBlocks);
107
108         void clearMarkBits(CollectorBlock*);
109         size_t markedCells(size_t startBlock = 0, size_t startCell = 0) const;
110
111         CollectorHeap m_heap;
112         JSGlobalData* m_globalData;
113     };
114
115     // tunable parameters
116     // derived constants
117     const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
118     const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
119     const size_t MINIMUM_CELL_SIZE = 64;
120     const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
121     const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
122     const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
123     const size_t CELL_MASK = CELL_SIZE - 1;
124     const size_t CELL_ALIGN_MASK = ~CELL_MASK;
125     const size_t CELLS_PER_BLOCK = (BLOCK_SIZE - sizeof(MarkedSpace*)) * 8 * CELL_SIZE / (8 * CELL_SIZE + 1) / CELL_SIZE; // one bitmap byte can represent 8 cells.
126     
127     const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
128     const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
129
130     struct CollectorBitmap {
131         FixedArray<uint32_t, BITMAP_WORDS> bits;
132         bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 
133         void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 
134         bool getset(size_t n)
135         {
136             unsigned i = (1 << (n & 0x1F));
137             uint32_t& b = bits[n >> 5];
138             bool r = !!(b & i);
139             b |= i;
140             return r;
141         } 
142         void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 
143         void clearAll() { memset(bits.data(), 0, sizeof(bits)); }
144         ALWAYS_INLINE void advanceToNextPossibleFreeCell(size_t& startCell)
145         {
146             if (!~bits[startCell >> 5])
147                 startCell = (startCell & (~0x1F)) + 32;
148             else
149                 ++startCell;
150         }
151         size_t count(size_t startCell = 0)
152         {
153             size_t result = 0;
154             for ( ; (startCell & 0x1F) != 0; ++startCell) {
155                 if (get(startCell))
156                     ++result;
157             }
158             for (size_t i = startCell >> 5; i < BITMAP_WORDS; ++i)
159                 result += WTF::bitCount(bits[i]);
160             return result;
161         }
162         size_t isEmpty() // Much more efficient than testing count() == 0.
163         {
164             for (size_t i = 0; i < BITMAP_WORDS; ++i)
165                 if (bits[i] != 0)
166                     return false;
167             return true;
168         }
169     };
170   
171     struct CollectorCell {
172         FixedArray<double, CELL_ARRAY_LENGTH> memory;
173     };
174
175     class CollectorBlock {
176     public:
177         FixedArray<CollectorCell, CELLS_PER_BLOCK> cells;
178         CollectorBitmap marked;
179         Heap* heap;
180     };
181
182     struct HeapConstants {
183         static const size_t cellSize = CELL_SIZE;
184         static const size_t cellsPerBlock = CELLS_PER_BLOCK;
185         typedef CollectorCell Cell;
186         typedef CollectorBlock Block;
187     };
188
189     inline CollectorBlock* MarkedSpace::cellBlock(const JSCell* cell)
190     {
191         return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
192     }
193
194     inline size_t MarkedSpace::cellOffset(const JSCell* cell)
195     {
196         return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
197     }
198
199     inline Heap* MarkedSpace::heap(JSCell* cell)
200     {
201         return cellBlock(cell)->heap;
202     }
203
204     inline bool MarkedSpace::isCellMarked(const JSCell* cell)
205     {
206         return cellBlock(cell)->marked.get(cellOffset(cell));
207     }
208
209     inline bool MarkedSpace::checkMarkCell(const JSCell* cell)
210     {
211         return cellBlock(cell)->marked.getset(cellOffset(cell));
212     }
213
214     inline void MarkedSpace::markCell(JSCell* cell)
215     {
216         cellBlock(cell)->marked.set(cellOffset(cell));
217     }
218
219     // Cell size needs to be a power of two for isPossibleCell to be valid.
220     COMPILE_ASSERT(!(sizeof(CollectorCell) % 2), Collector_cell_size_is_power_of_two);
221
222     inline bool MarkedSpace::isCellAligned(void *p)
223     {
224         return !((intptr_t)(p) & CELL_MASK);
225     }
226
227     inline bool MarkedSpace::isPossibleCell(void* p)
228     {
229         return isCellAligned(p) && p;
230     }
231
232     inline bool MarkedSpace::contains(void* x)
233     {
234         if (!isPossibleCell(x))
235             return false;
236             
237         return containsSlowCase(x);
238     }
239
240 } // namespace JSC
241
242 #endif // MarkedSpace_h