3003ffa55600a5cfcb874bd8ffdb1e0d2030e43f
[WebKit-https.git] / Source / bmalloc / bmalloc / Heap.cpp
1 /*
2  * Copyright (C) 2014-2016 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 "Heap.h"
27 #include "BumpAllocator.h"
28 #include "LargeChunk.h"
29 #include "LargeObject.h"
30 #include "PerProcess.h"
31 #include "SmallChunk.h"
32 #include "SmallLine.h"
33 #include "SmallPage.h"
34 #include <thread>
35
36 namespace bmalloc {
37
38 Heap::Heap(std::lock_guard<StaticMutex>&)
39     : m_largeObjects(VMState::HasPhysical::True)
40     , m_isAllocatingPages(false)
41     , m_scavenger(*this, &Heap::concurrentScavenge)
42 {
43     initializeLineMetadata();
44 }
45
46 void Heap::initializeLineMetadata()
47 {
48     // We assume that m_smallLineMetadata is zero-filled.
49
50     for (size_t size = alignment; size <= smallMax; size += alignment) {
51         size_t sizeClass = bmalloc::sizeClass(size);
52         auto& metadata = m_smallLineMetadata[sizeClass];
53
54         size_t object = 0;
55         size_t line = 0;
56         while (object < vmPageSize) {
57             line = object / smallLineSize;
58             size_t leftover = object % smallLineSize;
59
60             size_t objectCount;
61             size_t remainder;
62             divideRoundingUp(smallLineSize - leftover, size, objectCount, remainder);
63
64             metadata[line] = { static_cast<unsigned short>(leftover), static_cast<unsigned short>(objectCount) };
65
66             object += objectCount * size;
67         }
68
69         // Don't allow the last object in a page to escape the page.
70         if (object > vmPageSize) {
71             BASSERT(metadata[line].objectCount);
72             --metadata[line].objectCount;
73         }
74     }
75 }
76
77 void Heap::concurrentScavenge()
78 {
79     std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
80     scavenge(lock, scavengeSleepDuration);
81 }
82
83 void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
84 {
85     waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
86
87     scavengeSmallPages(lock, sleepDuration);
88     scavengeLargeObjects(lock, sleepDuration);
89     scavengeXLargeObjects(lock, sleepDuration);
90
91     sleep(lock, sleepDuration);
92 }
93
94 void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
95 {
96     while (m_smallPages.size()) {
97         m_vmHeap.deallocateSmallPage(lock, m_smallPages.pop());
98         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
99     }
100 }
101
102 void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
103 {
104     while (LargeObject largeObject = m_largeObjects.takeGreedy()) {
105         m_vmHeap.deallocateLargeObject(lock, largeObject);
106         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
107     }
108 }
109
110 void Heap::scavengeXLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
111 {
112     while (XLargeRange range = m_xLargeMap.takePhysical()) {
113         lock.unlock();
114         vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
115         lock.lock();
116         
117         range.setVMState(VMState::Virtual);
118         m_xLargeMap.addVirtual(range);
119
120         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
121     }
122
123     m_xLargeMap.shrinkToFit();
124 }
125
126 void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpAllocator& allocator, BumpRangeCache& rangeCache)
127 {
128     BASSERT(!rangeCache.size());
129     SmallPage* page = allocateSmallPage(lock, sizeClass);
130     SmallLine* lines = page->begin();
131     BASSERT(page->hasFreeLines(lock));
132
133     // Find a free line.
134     for (size_t lineNumber = 0; lineNumber < smallLineCount; ++lineNumber) {
135         if (lines[lineNumber].refCount(lock))
136             continue;
137
138         LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
139         if (!lineMetadata.objectCount)
140             continue;
141
142         // In a fragmented page, some free ranges might not fit in the cache.
143         if (rangeCache.size() == rangeCache.capacity()) {
144             m_smallPagesWithFreeLines[sizeClass].push(page);
145             BASSERT(allocator.canAllocate());
146             return;
147         }
148
149         char* begin = lines[lineNumber].begin() + lineMetadata.startOffset;
150         unsigned short objectCount = lineMetadata.objectCount;
151         lines[lineNumber].ref(lock, lineMetadata.objectCount);
152         page->ref(lock);
153
154         // Merge with subsequent free lines.
155         while (++lineNumber < smallLineCount) {
156             if (lines[lineNumber].refCount(lock))
157                 break;
158
159             LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
160             if (!lineMetadata.objectCount)
161                 continue;
162
163             objectCount += lineMetadata.objectCount;
164             lines[lineNumber].ref(lock, lineMetadata.objectCount);
165             page->ref(lock);
166         }
167
168         if (!allocator.canAllocate())
169             allocator.refill({ begin, objectCount });
170         else
171             rangeCache.push({ begin, objectCount });
172     }
173
174     BASSERT(allocator.canAllocate());
175     page->setHasFreeLines(lock, false);
176 }
177
178 SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
179 {
180     Vector<SmallPage*>& smallPagesWithFreeLines = m_smallPagesWithFreeLines[sizeClass];
181     while (smallPagesWithFreeLines.size()) {
182         SmallPage* page = smallPagesWithFreeLines.pop();
183         if (!page->refCount(lock) || page->sizeClass() != sizeClass) // Page was promoted to the pages list.
184             continue;
185         return page;
186     }
187
188     SmallPage* page = [this, &lock]() {
189         if (m_smallPages.size())
190             return m_smallPages.pop();
191
192         m_isAllocatingPages = true;
193         SmallPage* page = m_vmHeap.allocateSmallPage(lock);
194         return page;
195     }();
196
197     page->setSizeClass(sizeClass);
198     return page;
199 }
200
201 void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
202 {
203     BASSERT(!line->refCount(lock));
204     SmallPage* page = SmallPage::get(line);
205     page->deref(lock);
206
207     if (!page->hasFreeLines(lock)) {
208         page->setHasFreeLines(lock, true);
209         m_smallPagesWithFreeLines[page->sizeClass()].push(page);
210
211         BASSERT(page->refCount(lock));
212         return;
213     }
214
215     if (page->refCount(lock))
216         return;
217
218     m_smallPages.push(page);
219     m_scavenger.run();
220 }
221
222 inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t size)
223 {
224     BASSERT(largeObject.isFree());
225
226     LargeObject nextLargeObject;
227
228     if (largeObject.size() - size > largeMin) {
229         std::pair<LargeObject, LargeObject> split = largeObject.split(size);
230         largeObject = split.first;
231         nextLargeObject = split.second;
232     }
233
234     largeObject.setFree(false);
235
236     if (nextLargeObject) {
237         BASSERT(!nextLargeObject.nextCanMerge());
238         m_largeObjects.insert(nextLargeObject);
239     }
240
241     return largeObject;
242 }
243
244 inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t alignment, size_t size)
245 {
246     LargeObject prevLargeObject;
247     LargeObject nextLargeObject;
248
249     size_t alignmentMask = alignment - 1;
250     if (test(largeObject.begin(), alignmentMask)) {
251         size_t prefixSize = roundUpToMultipleOf(alignment, largeObject.begin() + largeMin) - largeObject.begin();
252         std::pair<LargeObject, LargeObject> pair = largeObject.split(prefixSize);
253         prevLargeObject = pair.first;
254         largeObject = pair.second;
255     }
256
257     BASSERT(largeObject.isFree());
258
259     if (largeObject.size() - size > largeMin) {
260         std::pair<LargeObject, LargeObject> split = largeObject.split(size);
261         largeObject = split.first;
262         nextLargeObject = split.second;
263     }
264
265     largeObject.setFree(false);
266
267     if (prevLargeObject) {
268         LargeObject merged = prevLargeObject.merge();
269         m_largeObjects.insert(merged);
270     }
271
272     if (nextLargeObject) {
273         LargeObject merged = nextLargeObject.merge();
274         m_largeObjects.insert(merged);
275     }
276
277     return largeObject;
278 }
279
280 void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t size)
281 {
282     BASSERT(size <= largeMax);
283     BASSERT(size >= largeMin);
284     BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
285
286     LargeObject largeObject = m_largeObjects.take(size);
287     if (!largeObject)
288         largeObject = m_vmHeap.allocateLargeObject(lock, size);
289
290     if (largeObject.vmState().hasVirtual()) {
291         m_isAllocatingPages = true;
292         // We commit before we split in order to avoid split/merge commit/decommit churn.
293         vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
294         largeObject.setVMState(VMState::Physical);
295     }
296
297     largeObject = splitAndAllocate(largeObject, size);
298
299     return largeObject.begin();
300 }
301
302 void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
303 {
304     BASSERT(size <= largeMax);
305     BASSERT(size >= largeMin);
306     BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
307     BASSERT(unalignedSize <= largeMax);
308     BASSERT(unalignedSize >= largeMin);
309     BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
310     BASSERT(alignment <= largeChunkSize / 2);
311     BASSERT(alignment >= largeAlignment);
312     BASSERT(isPowerOfTwo(alignment));
313
314     LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
315     if (!largeObject)
316         largeObject = m_vmHeap.allocateLargeObject(lock, alignment, size, unalignedSize);
317
318     if (largeObject.vmState().hasVirtual()) {
319         m_isAllocatingPages = true;
320         // We commit before we split in order to avoid split/merge commit/decommit churn.
321         vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
322         largeObject.setVMState(VMState::Physical);
323     }
324
325     largeObject = splitAndAllocate(largeObject, alignment, size);
326
327     return largeObject.begin();
328 }
329
330 void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject& largeObject)
331 {
332     BASSERT(!largeObject.isFree());
333     largeObject.setFree(true);
334     
335     LargeObject merged = largeObject.merge();
336     m_largeObjects.insert(merged);
337     m_scavenger.run();
338 }
339
340 void Heap::deallocateLarge(std::lock_guard<StaticMutex>& lock, void* object)
341 {
342     LargeObject largeObject(object);
343     deallocateLarge(lock, largeObject);
344 }
345
346 void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
347 {
348     void* result = tryAllocateXLarge(lock, alignment, size);
349     RELEASE_BASSERT(result);
350     return result;
351 }
352
353 void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
354 {
355     return allocateXLarge(lock, alignment, size);
356 }
357
358 XLargeRange Heap::splitAndAllocate(XLargeRange& range, size_t alignment, size_t size)
359 {
360     XLargeRange prev;
361     XLargeRange next;
362
363     size_t alignmentMask = alignment - 1;
364     if (test(range.begin(), alignmentMask)) {
365         size_t prefixSize = roundUpToMultipleOf(alignment, range.begin()) - range.begin();
366         std::pair<XLargeRange, XLargeRange> pair = range.split(prefixSize);
367         prev = pair.first;
368         range = pair.second;
369     }
370
371     if (range.size() - size >= xLargeAlignment) {
372         size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
373         std::pair<XLargeRange, XLargeRange> pair = range.split(alignedSize);
374         range = pair.first;
375         next = pair.second;
376     }
377
378     // At this point our range might contain an unused tail fragment. This is
379     // common. We can't allocate the tail fragment because it's aligned to less
380     // than xLargeAlignment. So, we pair the allocation with its tail fragment
381     // in the allocated list. This is an important optimization because it
382     // keeps the free list short, speeding up allocation and merging.
383
384     std::pair<XLargeRange, XLargeRange> allocated = range.split(roundUpToMultipleOf<vmPageSize>(size));
385     if (allocated.first.vmState().hasVirtual()) {
386         vmAllocatePhysicalPagesSloppy(allocated.first.begin(), allocated.first.size());
387         allocated.first.setVMState(VMState::Physical);
388     }
389
390     m_xLargeMap.addAllocated(prev, allocated, next);
391     return allocated.first;
392 }
393
394 void* Heap::tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
395 {
396     BASSERT(isPowerOfTwo(alignment));
397     BASSERT(alignment < xLargeMax);
398
399     m_isAllocatingPages = true;
400
401     alignment = roundUpToMultipleOf<xLargeAlignment>(alignment);
402
403     XLargeRange range = m_xLargeMap.takeFree(alignment, size);
404     if (!range) {
405         // We allocate VM in aligned multiples to increase the chances that
406         // the OS will provide contiguous ranges that we can merge.
407         size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
408
409         void* begin = tryVMAllocate(alignment, alignedSize);
410         if (!begin)
411             return nullptr;
412         range = XLargeRange(begin, alignedSize, VMState::Virtual);
413     }
414
415     return splitAndAllocate(range, alignment, size).begin();
416 }
417
418 size_t Heap::xLargeSize(std::unique_lock<StaticMutex>&, void* object)
419 {
420     return m_xLargeMap.getAllocated(object).size();
421 }
422
423 void Heap::shrinkXLarge(std::unique_lock<StaticMutex>&, const Range& object, size_t newSize)
424 {
425     BASSERT(object.size() > newSize);
426
427     if (object.size() - newSize < vmPageSize)
428         return;
429     
430     XLargeRange range = m_xLargeMap.takeAllocated(object.begin());
431     splitAndAllocate(range, xLargeAlignment, newSize);
432
433     m_scavenger.run();
434 }
435
436 void Heap::deallocateXLarge(std::unique_lock<StaticMutex>&, void* object)
437 {
438     XLargeRange range = m_xLargeMap.takeAllocated(object);
439     m_xLargeMap.addFree(range);
440     
441     m_scavenger.run();
442 }
443
444 } // namespace bmalloc