GC should be 1.7X faster
[WebKit-https.git] / Source / JavaScriptCore / heap / CopiedSpace.cpp
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "CopiedSpace.h"
28
29 #include "CopiedSpaceInlineMethods.h"
30 #include "GCActivityCallback.h"
31
32 namespace JSC {
33
34 CopiedSpace::CopiedSpace(Heap* heap)
35     : m_heap(heap)
36     , m_toSpace(0)
37     , m_fromSpace(0)
38     , m_inCopyingPhase(false)
39     , m_numberOfLoanedBlocks(0)
40 {
41     m_toSpaceLock.Init();
42 }
43
44 CopiedSpace::~CopiedSpace()
45 {
46     while (!m_toSpace->isEmpty())
47         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(static_cast<CopiedBlock*>(m_toSpace->removeHead())));
48
49     while (!m_fromSpace->isEmpty())
50         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(static_cast<CopiedBlock*>(m_fromSpace->removeHead())));
51
52     while (!m_oversizeBlocks.isEmpty())
53         CopiedBlock::destroy(static_cast<CopiedBlock*>(m_oversizeBlocks.removeHead())).deallocate();
54 }
55
56 void CopiedSpace::init()
57 {
58     m_toSpace = &m_blocks1;
59     m_fromSpace = &m_blocks2;
60     
61     if (!addNewBlock())
62         CRASH();
63 }   
64
65 CheckedBoolean CopiedSpace::tryAllocateSlowCase(size_t bytes, void** outPtr)
66 {
67     if (isOversize(bytes))
68         return tryAllocateOversize(bytes, outPtr);
69     
70     m_heap->didAllocate(m_allocator.currentCapacity());
71
72     if (!addNewBlock()) {
73         *outPtr = 0;
74         return false;
75     }
76     *outPtr = m_allocator.allocate(bytes);
77     ASSERT(*outPtr);
78     return true;
79 }
80
81 CheckedBoolean CopiedSpace::tryAllocateOversize(size_t bytes, void** outPtr)
82 {
83     ASSERT(isOversize(bytes));
84     
85     size_t blockSize = WTF::roundUpToMultipleOf(WTF::pageSize(), sizeof(CopiedBlock) + bytes);
86
87     PageAllocationAligned allocation = PageAllocationAligned::allocate(blockSize, WTF::pageSize(), OSAllocator::JSGCHeapPages);
88     if (!static_cast<bool>(allocation)) {
89         *outPtr = 0;
90         return false;
91     }
92
93     CopiedBlock* block = CopiedBlock::create(allocation);
94     m_oversizeBlocks.push(block);
95     m_blockFilter.add(reinterpret_cast<Bits>(block));
96     m_blockSet.add(block);
97     
98     *outPtr = allocateFromBlock(block, bytes);
99
100     m_heap->didAllocate(blockSize);
101
102     return true;
103 }
104
105 CheckedBoolean CopiedSpace::tryReallocate(void** ptr, size_t oldSize, size_t newSize)
106 {
107     if (oldSize >= newSize)
108         return true;
109     
110     void* oldPtr = *ptr;
111     ASSERT(!m_heap->globalData()->isInitializingObject());
112
113     if (isOversize(oldSize) || isOversize(newSize))
114         return tryReallocateOversize(ptr, oldSize, newSize);
115
116     if (m_allocator.wasLastAllocation(oldPtr, oldSize)) {
117         size_t delta = newSize - oldSize;
118         if (m_allocator.fitsInCurrentBlock(delta)) {
119             (void)m_allocator.allocate(delta);
120             return true;
121         }
122     }
123
124     void* result = 0;
125     if (!tryAllocate(newSize, &result)) {
126         *ptr = 0;
127         return false;
128     }
129     memcpy(result, oldPtr, oldSize);
130     *ptr = result;
131     return true;
132 }
133
134 CheckedBoolean CopiedSpace::tryReallocateOversize(void** ptr, size_t oldSize, size_t newSize)
135 {
136     ASSERT(isOversize(oldSize) || isOversize(newSize));
137     ASSERT(newSize > oldSize);
138
139     void* oldPtr = *ptr;
140     
141     void* newPtr = 0;
142     if (!tryAllocateOversize(newSize, &newPtr)) {
143         *ptr = 0;
144         return false;
145     }
146
147     memcpy(newPtr, oldPtr, oldSize);
148
149     if (isOversize(oldSize)) {
150         CopiedBlock* oldBlock = oversizeBlockFor(oldPtr);
151         m_oversizeBlocks.remove(oldBlock);
152         m_blockSet.remove(oldBlock);
153         CopiedBlock::destroy(oldBlock).deallocate();
154     }
155     
156     *ptr = newPtr;
157     return true;
158 }
159
160 void CopiedSpace::doneFillingBlock(CopiedBlock* block)
161 {
162     ASSERT(block);
163     ASSERT(block->m_offset < reinterpret_cast<char*>(block) + HeapBlock::s_blockSize);
164     ASSERT(m_inCopyingPhase);
165
166     if (block->m_offset == block->payload()) {
167         recycleBlock(block);
168         return;
169     }
170
171     {
172         SpinLockHolder locker(&m_toSpaceLock);
173         m_toSpace->push(block);
174         m_blockSet.add(block);
175         m_blockFilter.add(reinterpret_cast<Bits>(block));
176     }
177
178     {
179         MutexLocker locker(m_loanedBlocksLock);
180         ASSERT(m_numberOfLoanedBlocks > 0);
181         m_numberOfLoanedBlocks--;
182         if (!m_numberOfLoanedBlocks)
183             m_loanedBlocksCondition.signal();
184     }
185 }
186
187 void CopiedSpace::doneCopying()
188 {
189     {
190         MutexLocker locker(m_loanedBlocksLock);
191         while (m_numberOfLoanedBlocks > 0)
192             m_loanedBlocksCondition.wait(m_loanedBlocksLock);
193     }
194
195     ASSERT(m_inCopyingPhase);
196     m_inCopyingPhase = false;
197     while (!m_fromSpace->isEmpty()) {
198         CopiedBlock* block = static_cast<CopiedBlock*>(m_fromSpace->removeHead());
199         if (block->m_isPinned) {
200             block->m_isPinned = false;
201             // We don't add the block to the blockSet because it was never removed.
202             ASSERT(m_blockSet.contains(block));
203             m_blockFilter.add(reinterpret_cast<Bits>(block));
204             m_toSpace->push(block);
205             continue;
206         }
207
208         m_blockSet.remove(block);
209         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(block));
210     }
211
212     CopiedBlock* curr = static_cast<CopiedBlock*>(m_oversizeBlocks.head());
213     while (curr) {
214         CopiedBlock* next = static_cast<CopiedBlock*>(curr->next());
215         if (!curr->m_isPinned) {
216             m_oversizeBlocks.remove(curr);
217             m_blockSet.remove(curr);
218             CopiedBlock::destroy(curr).deallocate();
219         } else {
220             m_blockFilter.add(reinterpret_cast<Bits>(curr));
221             curr->m_isPinned = false;
222         }
223         curr = next;
224     }
225
226     if (!m_toSpace->head()) {
227         if (!addNewBlock())
228             CRASH();
229     } else
230         m_allocator.resetCurrentBlock(static_cast<CopiedBlock*>(m_toSpace->head()));
231 }
232
233 CheckedBoolean CopiedSpace::getFreshBlock(AllocationEffort allocationEffort, CopiedBlock** outBlock)
234 {
235     CopiedBlock* block = 0;
236     if (allocationEffort == AllocationMustSucceed)
237         block = CopiedBlock::create(m_heap->blockAllocator().allocate());
238     else {
239         ASSERT(allocationEffort == AllocationCanFail);
240         if (m_heap->shouldCollect())
241             m_heap->collect(Heap::DoNotSweep);
242         
243         if (!getFreshBlock(AllocationMustSucceed, &block)) {
244             *outBlock = 0;
245             ASSERT_NOT_REACHED();
246             return false;
247         }
248     }
249     ASSERT(block);
250     ASSERT(is8ByteAligned(block->m_offset));
251     *outBlock = block;
252     return true;
253 }
254
255 size_t CopiedSpace::size()
256 {
257     size_t calculatedSize = 0;
258
259     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_toSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
260         calculatedSize += block->size();
261
262     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_fromSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
263         calculatedSize += block->size();
264
265     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_oversizeBlocks.head()); block; block = static_cast<CopiedBlock*>(block->next()))
266         calculatedSize += block->size();
267
268     return calculatedSize;
269 }
270
271 size_t CopiedSpace::capacity()
272 {
273     size_t calculatedCapacity = 0;
274
275     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_toSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
276         calculatedCapacity += block->capacity();
277
278     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_fromSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
279         calculatedCapacity += block->capacity();
280
281     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_oversizeBlocks.head()); block; block = static_cast<CopiedBlock*>(block->next()))
282         calculatedCapacity += block->capacity();
283
284     return calculatedCapacity;
285 }
286
287 static bool isBlockListPagedOut(double deadline, DoublyLinkedList<HeapBlock>* list)
288 {
289     unsigned itersSinceLastTimeCheck = 0;
290     HeapBlock* current = list->head();
291     while (current) {
292         current = current->next();
293         ++itersSinceLastTimeCheck;
294         if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
295             double currentTime = WTF::monotonicallyIncreasingTime();
296             if (currentTime > deadline)
297                 return true;
298             itersSinceLastTimeCheck = 0;
299         }
300     }
301
302     return false;
303 }
304
305 bool CopiedSpace::isPagedOut(double deadline)
306 {
307     return isBlockListPagedOut(deadline, m_toSpace) 
308         || isBlockListPagedOut(deadline, m_fromSpace) 
309         || isBlockListPagedOut(deadline, &m_oversizeBlocks);
310 }
311
312 } // namespace JSC