2011-01-29 Geoffrey Garen <ggaren@apple.com>
[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/Bitmap.h>
28 #include <wtf/FixedArray.h>
29 #include <wtf/HashCountedSet.h>
30 #include <wtf/Noncopyable.h>
31 #include <wtf/Vector.h>
32
33 namespace JSC {
34
35     class CollectorBlock;
36     class Heap;
37     class JSCell;
38     class JSGlobalData;
39     class LiveObjectIterator;
40     class MarkStack;
41     class WeakGCHandle;
42
43 #if OS(WINCE) || OS(SYMBIAN) || PLATFORM(BREWMP)
44     const size_t BLOCK_SIZE = 64 * 1024; // 64k
45 #else
46     const size_t BLOCK_SIZE = 256 * 1024; // 256k
47 #endif
48
49     typedef HashCountedSet<JSCell*> ProtectCountSet;
50
51     struct CollectorHeap {
52         size_t nextBlock;
53         size_t nextCell;
54         PageAllocationAligned* blocks;
55         
56         size_t numBlocks;
57         size_t usedBlocks;
58
59         CollectorBlock* collectorBlock(size_t index) const
60         {
61             return static_cast<CollectorBlock*>(blocks[index].base());
62         }
63     };
64
65     class MarkedSpace {
66         WTF_MAKE_NONCOPYABLE(MarkedSpace);
67     public:
68         static Heap* heap(JSCell*);
69
70         static bool isCellMarked(const JSCell*);
71         static bool checkMarkCell(const JSCell*);
72         static void markCell(JSCell*);
73
74         MarkedSpace(JSGlobalData*);
75         void destroy(ProtectCountSet&);
76
77         JSGlobalData* globalData() { return m_globalData; }
78
79         void* allocate(size_t);
80
81         void clearMarkBits();
82         void markRoots();
83         void reset();
84         void sweep();
85
86         size_t size() const;
87         size_t capacity() const;
88         size_t objectCount() const;
89
90         bool contains(void*);
91
92         LiveObjectIterator primaryHeapBegin();
93         LiveObjectIterator primaryHeapEnd();
94
95     private:
96         bool isCellAligned(void*);
97         bool isPossibleCell(void*);
98         bool containsSlowCase(void*);
99
100         static CollectorBlock* cellBlock(const JSCell*);
101         static size_t cellOffset(const JSCell*);
102
103         NEVER_INLINE CollectorBlock* allocateBlock();
104         NEVER_INLINE void freeBlock(size_t);
105         void resizeBlocks();
106         void growBlocks(size_t neededBlocks);
107         void shrinkBlocks(size_t neededBlocks);
108
109         void clearMarkBits(CollectorBlock*);
110         size_t markedCells(size_t startBlock = 0, size_t startCell = 0) const;
111
112         CollectorHeap m_heap;
113         JSGlobalData* m_globalData;
114     };
115
116     // tunable parameters
117     // derived constants
118     const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
119     const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
120     const size_t MINIMUM_CELL_SIZE = 64;
121     const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
122     const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
123     const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
124     const size_t CELL_MASK = CELL_SIZE - 1;
125     const size_t CELL_ALIGN_MASK = ~CELL_MASK;
126     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.
127     
128     struct CollectorCell {
129         FixedArray<double, CELL_ARRAY_LENGTH> memory;
130     };
131
132     class CollectorBlock {
133     public:
134         FixedArray<CollectorCell, CELLS_PER_BLOCK> cells;
135         WTF::Bitmap<CELLS_PER_BLOCK> marked;
136         Heap* heap;
137     };
138
139     struct HeapConstants {
140         static const size_t cellSize = CELL_SIZE;
141         static const size_t cellsPerBlock = CELLS_PER_BLOCK;
142         typedef CollectorCell Cell;
143         typedef CollectorBlock Block;
144     };
145
146     inline CollectorBlock* MarkedSpace::cellBlock(const JSCell* cell)
147     {
148         return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
149     }
150
151     inline size_t MarkedSpace::cellOffset(const JSCell* cell)
152     {
153         return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
154     }
155
156     inline Heap* MarkedSpace::heap(JSCell* cell)
157     {
158         return cellBlock(cell)->heap;
159     }
160
161     inline bool MarkedSpace::isCellMarked(const JSCell* cell)
162     {
163         return cellBlock(cell)->marked.get(cellOffset(cell));
164     }
165
166     inline bool MarkedSpace::checkMarkCell(const JSCell* cell)
167     {
168         return cellBlock(cell)->marked.testAndSet(cellOffset(cell));
169     }
170
171     inline void MarkedSpace::markCell(JSCell* cell)
172     {
173         cellBlock(cell)->marked.set(cellOffset(cell));
174     }
175
176     // Cell size needs to be a power of two for isPossibleCell to be valid.
177     COMPILE_ASSERT(!(sizeof(CollectorCell) % 2), Collector_cell_size_is_power_of_two);
178
179     inline bool MarkedSpace::isCellAligned(void *p)
180     {
181         return !((intptr_t)(p) & CELL_MASK);
182     }
183
184     inline bool MarkedSpace::isPossibleCell(void* p)
185     {
186         return isCellAligned(p) && p;
187     }
188
189     inline bool MarkedSpace::contains(void* x)
190     {
191         if (!isPossibleCell(x))
192             return false;
193             
194         return containsSlowCase(x);
195     }
196
197 } // namespace JSC
198
199 #endif // MarkedSpace_h