aeb520f6a236b725638fba48c4635df6894b569d
[WebKit.git] / Source / JavaScriptCore / runtime / MarkedSpace.cpp
1 /*
2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
3  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
4  *
5  *  This library is free software; you can redistribute it and/or
6  *  modify it under the terms of the GNU Lesser General Public
7  *  License as published by the Free Software Foundation; either
8  *  version 2 of the License, or (at your option) any later version.
9  *
10  *  This library is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  *  Lesser General Public License for more details.
14  *
15  *  You should have received a copy of the GNU Lesser General Public
16  *  License along with this library; if not, write to the Free Software
17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18  *
19  */
20
21 #include "config.h"
22 #include "MarkedSpace.h"
23
24 #include "CollectorHeapIterator.h"
25 #include "JSCell.h"
26 #include "JSGlobalData.h"
27 #include "JSLock.h"
28
29 using std::max;
30
31 namespace JSC {
32
33 class Structure;
34
35 // tunable parameters
36
37 const size_t GROWTH_FACTOR = 2;
38 const size_t LOW_WATER_FACTOR = 4;
39 const size_t ALLOCATIONS_PER_COLLECTION = 3600;
40 // This value has to be a macro to be used in max() without introducing
41 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
42 #define MIN_ARRAY_SIZE (static_cast<size_t>(14))
43
44 MarkedSpace::MarkedSpace(JSGlobalData* globalData)
45     : m_globalData(globalData)
46 {
47     memset(&m_heap, 0, sizeof(CollectorHeap));
48     allocateBlock();
49 }
50
51 void MarkedSpace::destroy(ProtectCountSet& protectedValuesCopy)
52 {
53     clearMarkBits();
54     ProtectCountSet::iterator protectedValuesEnd = protectedValuesCopy.end();
55     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
56         markCell(it->first);
57
58     m_heap.nextCell = 0;
59     m_heap.nextBlock = 0;
60     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
61     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
62     for ( ; it != end; ++it)
63         (*it)->~JSCell();
64
65     protectedValuesEnd = protectedValuesCopy.end();
66     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
67         it->first->~JSCell();
68
69     for (size_t block = 0; block < m_heap.usedBlocks; ++block)
70         m_heap.blocks[block].deallocate();
71
72     fastFree(m_heap.blocks);
73
74     memset(&m_heap, 0, sizeof(CollectorHeap));
75 }
76
77 NEVER_INLINE CollectorBlock* MarkedSpace::allocateBlock()
78 {
79     PageAllocationAligned allocation = PageAllocationAligned::allocate(BLOCK_SIZE, BLOCK_SIZE, OSAllocator::JSGCHeapPages);
80     CollectorBlock* block = static_cast<CollectorBlock*>(allocation.base());
81     if (!block)
82         CRASH();
83
84     // Initialize block.
85
86     block->heap = &globalData()->heap;
87     clearMarkBits(block);
88
89     Structure* dummyMarkableCellStructure = globalData()->dummyMarkableCellStructure.get();
90     for (size_t i = 0; i < HeapConstants::cellsPerBlock; ++i)
91         new (&block->cells[i]) JSCell(dummyMarkableCellStructure);
92     
93     // Add block to blocks vector.
94
95     size_t numBlocks = m_heap.numBlocks;
96     if (m_heap.usedBlocks == numBlocks) {
97         static const size_t maxNumBlocks = ULONG_MAX / sizeof(PageAllocationAligned) / GROWTH_FACTOR;
98         if (numBlocks > maxNumBlocks)
99             CRASH();
100         numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
101         m_heap.numBlocks = numBlocks;
102         m_heap.blocks = static_cast<PageAllocationAligned*>(fastRealloc(m_heap.blocks, numBlocks * sizeof(PageAllocationAligned)));
103     }
104     m_heap.blocks[m_heap.usedBlocks++] = allocation;
105
106     return block;
107 }
108
109 NEVER_INLINE void MarkedSpace::freeBlock(size_t block)
110 {
111     ObjectIterator it(m_heap, block);
112     ObjectIterator end(m_heap, block + 1);
113     for ( ; it != end; ++it)
114         (*it)->~JSCell();
115     m_heap.blocks[block].deallocate();
116
117     // swap with the last block so we compact as we go
118     m_heap.blocks[block] = m_heap.blocks[m_heap.usedBlocks - 1];
119     m_heap.usedBlocks--;
120
121     if (m_heap.numBlocks > MIN_ARRAY_SIZE && m_heap.usedBlocks < m_heap.numBlocks / LOW_WATER_FACTOR) {
122         m_heap.numBlocks = m_heap.numBlocks / GROWTH_FACTOR; 
123         m_heap.blocks = static_cast<PageAllocationAligned*>(fastRealloc(m_heap.blocks, m_heap.numBlocks * sizeof(PageAllocationAligned)));
124     }
125 }
126
127 void* MarkedSpace::allocate(size_t s)
128 {
129     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
130     typedef HeapConstants::Block Block;
131     typedef HeapConstants::Cell Cell;
132     
133     ASSERT(JSLock::lockCount() > 0);
134     ASSERT(JSLock::currentThreadIsHoldingLock());
135     ASSERT_UNUSED(s, s <= HeapConstants::cellSize);
136
137     // Fast case: find the next garbage cell and recycle it.
138
139     do {
140         ASSERT(m_heap.nextBlock < m_heap.usedBlocks);
141         Block* block = m_heap.collectorBlock(m_heap.nextBlock);
142         do {
143             ASSERT(m_heap.nextCell < HeapConstants::cellsPerBlock);
144             if (!block->marked.get(m_heap.nextCell)) { // Always false for the last cell in the block
145                 Cell* cell = &block->cells[m_heap.nextCell];
146
147                 JSCell* imp = reinterpret_cast<JSCell*>(cell);
148                 imp->~JSCell();
149
150                 ++m_heap.nextCell;
151                 return cell;
152             }
153             block->marked.advanceToNextPossibleFreeCell(m_heap.nextCell);
154         } while (m_heap.nextCell != HeapConstants::cellsPerBlock);
155         m_heap.nextCell = 0;
156     } while (++m_heap.nextBlock != m_heap.usedBlocks);
157     
158     return 0;
159 }
160
161 void MarkedSpace::resizeBlocks()
162 {
163     size_t usedCellCount = markedCells();
164     size_t minCellCount = usedCellCount + max(ALLOCATIONS_PER_COLLECTION, usedCellCount);
165     size_t minBlockCount = (minCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
166
167     size_t maxCellCount = 1.25f * minCellCount;
168     size_t maxBlockCount = (maxCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
169
170     if (m_heap.usedBlocks < minBlockCount)
171         growBlocks(minBlockCount);
172     else if (m_heap.usedBlocks > maxBlockCount)
173         shrinkBlocks(maxBlockCount);
174 }
175
176 void MarkedSpace::growBlocks(size_t neededBlocks)
177 {
178     ASSERT(m_heap.usedBlocks < neededBlocks);
179     while (m_heap.usedBlocks < neededBlocks)
180         allocateBlock();
181 }
182
183 void MarkedSpace::shrinkBlocks(size_t neededBlocks)
184 {
185     ASSERT(m_heap.usedBlocks > neededBlocks);
186     
187     // Clear the always-on last bit, so isEmpty() isn't fooled by it.
188     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
189         m_heap.collectorBlock(i)->marked.clear(HeapConstants::cellsPerBlock - 1);
190
191     for (size_t i = 0; i != m_heap.usedBlocks && m_heap.usedBlocks != neededBlocks; ) {
192         if (m_heap.collectorBlock(i)->marked.isEmpty()) {
193             freeBlock(i);
194         } else
195             ++i;
196     }
197
198     // Reset the always-on last bit.
199     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
200         m_heap.collectorBlock(i)->marked.set(HeapConstants::cellsPerBlock - 1);
201 }
202
203 bool MarkedSpace::containsSlowCase(void* x)
204 {
205     uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
206     xAsBits &= CELL_ALIGN_MASK;
207
208     uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
209     const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
210     if (offset > lastCellOffset)
211         return false;
212
213     CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
214     size_t usedBlocks = m_heap.usedBlocks;
215     for (size_t block = 0; block < usedBlocks; block++) {
216         if (m_heap.collectorBlock(block) != blockAddr)
217             continue;
218
219         // x is a pointer into the heap. Now, verify that the cell it
220         // points to is live. (If the cell is dead, we must not mark it,
221         // since that would revive it in a zombie state.)
222         if (block < m_heap.nextBlock)
223             return true;
224         
225         size_t cellOffset = offset / CELL_SIZE;
226         
227         if (block == m_heap.nextBlock && cellOffset < m_heap.nextCell)
228             return true;
229         
230         return blockAddr->marked.get(cellOffset);
231     }
232     
233     return false;
234 }
235
236 void MarkedSpace::clearMarkBits()
237 {
238     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
239         clearMarkBits(m_heap.collectorBlock(i));
240 }
241
242 void MarkedSpace::clearMarkBits(CollectorBlock* block)
243 {
244     // allocate assumes that the last cell in every block is marked.
245     block->marked.clearAll();
246     block->marked.set(HeapConstants::cellsPerBlock - 1);
247 }
248
249 size_t MarkedSpace::markedCells(size_t startBlock, size_t startCell) const
250 {
251     ASSERT(startBlock <= m_heap.usedBlocks);
252     ASSERT(startCell < HeapConstants::cellsPerBlock);
253
254     if (startBlock >= m_heap.usedBlocks)
255         return 0;
256
257     size_t result = 0;
258     result += m_heap.collectorBlock(startBlock)->marked.count(startCell);
259     for (size_t i = startBlock + 1; i < m_heap.usedBlocks; ++i)
260         result += m_heap.collectorBlock(i)->marked.count();
261
262     return result;
263 }
264
265 void MarkedSpace::sweep()
266 {
267 #if !ENABLE(JSC_ZOMBIES)
268     Structure* dummyMarkableCellStructure = globalData()->dummyMarkableCellStructure.get();
269 #endif
270
271     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
272     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
273     for ( ; it != end; ++it) {
274         JSCell* cell = *it;
275 #if ENABLE(JSC_ZOMBIES)
276         if (!cell->isZombie()) {
277             const ClassInfo* info = cell->classInfo();
278             cell->~JSCell();
279             new (cell) JSZombie(info, JSZombie::leakedZombieStructure());
280             Heap::markCell(cell);
281         }
282 #else
283         cell->~JSCell();
284         // Callers of sweep assume it's safe to mark any cell in the heap.
285         new (cell) JSCell(dummyMarkableCellStructure);
286 #endif
287     }
288 }
289
290 size_t MarkedSpace::objectCount() const
291 {
292     return m_heap.nextBlock * HeapConstants::cellsPerBlock // allocated full blocks
293            + m_heap.nextCell // allocated cells in current block
294            + markedCells(m_heap.nextBlock, m_heap.nextCell) // marked cells in remainder of m_heap
295            - m_heap.usedBlocks; // 1 cell per block is a dummy sentinel
296 }
297
298 size_t MarkedSpace::size() const
299 {
300     return objectCount() * HeapConstants::cellSize;
301 }
302
303 size_t MarkedSpace::capacity() const
304 {
305     return m_heap.usedBlocks * BLOCK_SIZE;
306 }
307
308 void MarkedSpace::reset()
309 {
310     m_heap.nextCell = 0;
311     m_heap.nextBlock = 0;
312 #if ENABLE(JSC_ZOMBIES)
313     sweep();
314 #endif
315     resizeBlocks();
316 }
317
318 LiveObjectIterator MarkedSpace::primaryHeapBegin()
319 {
320     return LiveObjectIterator(m_heap, 0);
321 }
322
323 LiveObjectIterator MarkedSpace::primaryHeapEnd()
324 {
325     return LiveObjectIterator(m_heap, m_heap.usedBlocks);
326 }
327
328 } // namespace JSC