CopiedSpace::contains doesn't check for oversize blocks
[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 }
42
43 void CopiedSpace::init()
44 {
45     m_toSpace = &m_blocks1;
46     m_fromSpace = &m_blocks2;
47     
48     if (!addNewBlock())
49         CRASH();
50 }   
51
52 CheckedBoolean CopiedSpace::tryAllocateSlowCase(size_t bytes, void** outPtr)
53 {
54     if (isOversize(bytes))
55         return tryAllocateOversize(bytes, outPtr);
56     
57     m_heap->didAllocate(m_allocator.currentCapacity());
58
59     if (!addNewBlock()) {
60         *outPtr = 0;
61         return false;
62     }
63     *outPtr = m_allocator.allocate(bytes);
64     ASSERT(*outPtr);
65     return true;
66 }
67
68 CheckedBoolean CopiedSpace::tryAllocateOversize(size_t bytes, void** outPtr)
69 {
70     ASSERT(isOversize(bytes));
71     
72     size_t blockSize = WTF::roundUpToMultipleOf(WTF::pageSize(), sizeof(CopiedBlock) + bytes);
73
74     PageAllocationAligned allocation = PageAllocationAligned::allocate(blockSize, WTF::pageSize(), OSAllocator::JSGCHeapPages);
75     if (!static_cast<bool>(allocation)) {
76         *outPtr = 0;
77         return false;
78     }
79
80     CopiedBlock* block = CopiedBlock::create(allocation);
81     m_oversizeBlocks.push(block);
82     m_blockFilter.add(reinterpret_cast<Bits>(block));
83     m_blockSet.add(block);
84     
85     *outPtr = allocateFromBlock(block, bytes);
86
87     m_heap->didAllocate(blockSize);
88
89     return true;
90 }
91
92 CheckedBoolean CopiedSpace::tryReallocate(void** ptr, size_t oldSize, size_t newSize)
93 {
94     if (oldSize >= newSize)
95         return true;
96     
97     void* oldPtr = *ptr;
98     ASSERT(!m_heap->globalData()->isInitializingObject());
99
100     if (isOversize(oldSize) || isOversize(newSize))
101         return tryReallocateOversize(ptr, oldSize, newSize);
102
103     if (m_allocator.wasLastAllocation(oldPtr, oldSize)) {
104         size_t delta = newSize - oldSize;
105         if (m_allocator.fitsInCurrentBlock(delta)) {
106             (void)m_allocator.allocate(delta);
107             return true;
108         }
109     }
110
111     void* result = 0;
112     if (!tryAllocate(newSize, &result)) {
113         *ptr = 0;
114         return false;
115     }
116     memcpy(result, oldPtr, oldSize);
117     *ptr = result;
118     return true;
119 }
120
121 CheckedBoolean CopiedSpace::tryReallocateOversize(void** ptr, size_t oldSize, size_t newSize)
122 {
123     ASSERT(isOversize(oldSize) || isOversize(newSize));
124     ASSERT(newSize > oldSize);
125
126     void* oldPtr = *ptr;
127     
128     void* newPtr = 0;
129     if (!tryAllocateOversize(newSize, &newPtr)) {
130         *ptr = 0;
131         return false;
132     }
133
134     memcpy(newPtr, oldPtr, oldSize);
135
136     if (isOversize(oldSize)) {
137         CopiedBlock* oldBlock = oversizeBlockFor(oldPtr);
138         m_oversizeBlocks.remove(oldBlock);
139         m_blockSet.remove(oldBlock);
140         CopiedBlock::destroy(oldBlock).deallocate();
141     }
142     
143     *ptr = newPtr;
144     return true;
145 }
146
147 void CopiedSpace::doneFillingBlock(CopiedBlock* block)
148 {
149     ASSERT(block);
150     ASSERT(block->m_offset < reinterpret_cast<char*>(block) + HeapBlock::s_blockSize);
151     ASSERT(m_inCopyingPhase);
152
153     if (block->m_offset == block->payload()) {
154         recycleBlock(block);
155         return;
156     }
157
158     {
159         MutexLocker locker(m_toSpaceLock);
160         m_toSpace->push(block);
161         m_blockSet.add(block);
162         m_blockFilter.add(reinterpret_cast<Bits>(block));
163     }
164
165     {
166         MutexLocker locker(m_loanedBlocksLock);
167         ASSERT(m_numberOfLoanedBlocks > 0);
168         m_numberOfLoanedBlocks--;
169         if (!m_numberOfLoanedBlocks)
170             m_loanedBlocksCondition.signal();
171     }
172 }
173
174 void CopiedSpace::doneCopying()
175 {
176     {
177         MutexLocker locker(m_loanedBlocksLock);
178         while (m_numberOfLoanedBlocks > 0)
179             m_loanedBlocksCondition.wait(m_loanedBlocksLock);
180     }
181
182     ASSERT(m_inCopyingPhase);
183     m_inCopyingPhase = false;
184     while (!m_fromSpace->isEmpty()) {
185         CopiedBlock* block = static_cast<CopiedBlock*>(m_fromSpace->removeHead());
186         if (block->m_isPinned) {
187             block->m_isPinned = false;
188             // We don't add the block to the blockSet because it was never removed.
189             ASSERT(m_blockSet.contains(block));
190             m_blockFilter.add(reinterpret_cast<Bits>(block));
191             m_toSpace->push(block);
192             continue;
193         }
194
195         m_blockSet.remove(block);
196         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(block));
197     }
198
199     CopiedBlock* curr = static_cast<CopiedBlock*>(m_oversizeBlocks.head());
200     while (curr) {
201         CopiedBlock* next = static_cast<CopiedBlock*>(curr->next());
202         if (!curr->m_isPinned) {
203             m_oversizeBlocks.remove(curr);
204             m_blockSet.remove(curr);
205             CopiedBlock::destroy(curr).deallocate();
206         } else {
207             m_blockFilter.add(reinterpret_cast<Bits>(curr));
208             curr->m_isPinned = false;
209         }
210         curr = next;
211     }
212
213     if (!m_toSpace->head()) {
214         if (!addNewBlock())
215             CRASH();
216     } else
217         m_allocator.resetCurrentBlock(static_cast<CopiedBlock*>(m_toSpace->head()));
218 }
219
220 CheckedBoolean CopiedSpace::getFreshBlock(AllocationEffort allocationEffort, CopiedBlock** outBlock)
221 {
222     CopiedBlock* block = 0;
223     if (allocationEffort == AllocationMustSucceed)
224         block = CopiedBlock::create(m_heap->blockAllocator().allocate());
225     else {
226         ASSERT(allocationEffort == AllocationCanFail);
227         if (m_heap->shouldCollect())
228             m_heap->collect(Heap::DoNotSweep);
229         
230         if (!getFreshBlock(AllocationMustSucceed, &block)) {
231             *outBlock = 0;
232             ASSERT_NOT_REACHED();
233             return false;
234         }
235     }
236     ASSERT(block);
237     ASSERT(is8ByteAligned(block->m_offset));
238     *outBlock = block;
239     return true;
240 }
241
242 void CopiedSpace::freeAllBlocks()
243 {
244     while (!m_toSpace->isEmpty())
245         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(static_cast<CopiedBlock*>(m_toSpace->removeHead())));
246
247     while (!m_fromSpace->isEmpty())
248         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(static_cast<CopiedBlock*>(m_fromSpace->removeHead())));
249
250     while (!m_oversizeBlocks.isEmpty())
251         CopiedBlock::destroy(static_cast<CopiedBlock*>(m_oversizeBlocks.removeHead())).deallocate();
252 }
253
254 size_t CopiedSpace::size()
255 {
256     size_t calculatedSize = 0;
257
258     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_toSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
259         calculatedSize += block->size();
260
261     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_fromSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
262         calculatedSize += block->size();
263
264     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_oversizeBlocks.head()); block; block = static_cast<CopiedBlock*>(block->next()))
265         calculatedSize += block->size();
266
267     return calculatedSize;
268 }
269
270 size_t CopiedSpace::capacity()
271 {
272     size_t calculatedCapacity = 0;
273
274     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_toSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
275         calculatedCapacity += block->capacity();
276
277     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_fromSpace->head()); block; block = static_cast<CopiedBlock*>(block->next()))
278         calculatedCapacity += block->capacity();
279
280     for (CopiedBlock* block = static_cast<CopiedBlock*>(m_oversizeBlocks.head()); block; block = static_cast<CopiedBlock*>(block->next()))
281         calculatedCapacity += block->capacity();
282
283     return calculatedCapacity;
284 }
285
286 static bool isBlockListPagedOut(double deadline, DoublyLinkedList<HeapBlock>* list)
287 {
288     unsigned itersSinceLastTimeCheck = 0;
289     HeapBlock* current = list->head();
290     while (current) {
291         current = current->next();
292         ++itersSinceLastTimeCheck;
293         if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
294             double currentTime = WTF::monotonicallyIncreasingTime();
295             if (currentTime > deadline)
296                 return true;
297             itersSinceLastTimeCheck = 0;
298         }
299     }
300
301     return false;
302 }
303
304 bool CopiedSpace::isPagedOut(double deadline)
305 {
306     return isBlockListPagedOut(deadline, m_toSpace) 
307         || isBlockListPagedOut(deadline, m_fromSpace) 
308         || isBlockListPagedOut(deadline, &m_oversizeBlocks);
309 }
310
311 } // namespace JSC