7dfd71c345e05fa175cd00c33117775eff72bb67
[WebKit.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 "Chunk.h"
29 #include "LargeObject.h"
30 #include "PerProcess.h"
31 #include "SmallLine.h"
32 #include "SmallPage.h"
33 #include <thread>
34
35 namespace bmalloc {
36
37 Heap::Heap(std::lock_guard<StaticMutex>&)
38     : m_vmPageSizePhysical(vmPageSizePhysical())
39     , m_largeObjects(VMState::HasPhysical::True)
40     , m_isAllocatingPages(false)
41     , m_scavenger(*this, &Heap::concurrentScavenge)
42 {
43     RELEASE_BASSERT(vmPageSizePhysical() >= smallPageSize);
44     RELEASE_BASSERT(vmPageSize() >= vmPageSizePhysical());
45     RELEASE_BASSERT(xLargeAlignment >= vmPageSize());
46
47     initializeLineMetadata();
48     initializePageMetadata();
49 }
50
51 void Heap::initializeLineMetadata()
52 {
53     size_t sizeClassCount = bmalloc::sizeClass(smallLineSize);
54     size_t smallLineCount = m_vmPageSizePhysical / smallLineSize;
55     m_smallLineMetadata.grow(sizeClassCount * smallLineCount);
56
57     for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) {
58         size_t size = objectSize(sizeClass);
59         LineMetadata* pageMetadata = &m_smallLineMetadata[sizeClass * smallLineCount];
60
61         size_t object = 0;
62         size_t line = 0;
63         while (object < m_vmPageSizePhysical) {
64             line = object / smallLineSize;
65             size_t leftover = object % smallLineSize;
66
67             size_t objectCount;
68             size_t remainder;
69             divideRoundingUp(smallLineSize - leftover, size, objectCount, remainder);
70
71             pageMetadata[line] = { static_cast<unsigned char>(leftover), static_cast<unsigned char>(objectCount) };
72
73             object += objectCount * size;
74         }
75
76         // Don't allow the last object in a page to escape the page.
77         if (object > m_vmPageSizePhysical) {
78             BASSERT(pageMetadata[line].objectCount);
79             --pageMetadata[line].objectCount;
80         }
81     }
82 }
83
84 void Heap::initializePageMetadata()
85 {
86     auto computePageSize = [&](size_t sizeClass) {
87         size_t size = objectSize(sizeClass);
88         if (sizeClass < bmalloc::sizeClass(smallLineSize))
89             return m_vmPageSizePhysical;
90
91         for (size_t pageSize = m_vmPageSizePhysical;
92             pageSize < pageSizeMax;
93             pageSize += m_vmPageSizePhysical) {
94             RELEASE_BASSERT(pageSize <= largeObjectMax);
95             size_t waste = pageSize % size;
96             if (waste <= pageSize / pageSizeWasteFactor)
97                 return pageSize;
98         }
99         
100         return pageSizeMax;
101     };
102
103     for (size_t i = 0; i < sizeClassCount; ++i)
104         m_pageClasses[i] = (computePageSize(i) - 1) / smallPageSize;
105 }
106
107 void Heap::concurrentScavenge()
108 {
109     std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
110     scavenge(lock, scavengeSleepDuration);
111 }
112
113 void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
114 {
115     waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
116
117     scavengeSmallPages(lock, sleepDuration);
118     scavengeLargeObjects(lock, sleepDuration);
119     scavengeXLargeObjects(lock, sleepDuration);
120
121     sleep(lock, sleepDuration);
122 }
123
124 void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
125 {
126     for (auto& smallPages : m_smallPages) {
127         while (!smallPages.isEmpty()) {
128             SmallPage* page = smallPages.pop();
129             size_t pageClass = m_pageClasses[page->sizeClass()];
130             m_vmHeap.deallocateSmallPage(lock, pageClass, page);
131             waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
132         }
133     }
134 }
135
136 void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
137 {
138     while (LargeObject largeObject = m_largeObjects.takeGreedy()) {
139         m_vmHeap.deallocateLargeObject(lock, largeObject);
140         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
141     }
142 }
143
144 void Heap::scavengeXLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
145 {
146     while (XLargeRange range = m_xLargeMap.takePhysical()) {
147         lock.unlock();
148         vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
149         lock.lock();
150         
151         range.setVMState(VMState::Virtual);
152         m_xLargeMap.addVirtual(range);
153
154         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
155     }
156
157     m_xLargeMap.shrinkToFit();
158 }
159
160 inline LargeObject& Heap::splitAndAllocate(std::lock_guard<StaticMutex>& lock, LargeObject& largeObject, size_t size)
161 {
162     BASSERT(largeObject.isFree());
163
164     LargeObject nextLargeObject;
165
166     if (largeObject.size() - size >= largeMin) {
167         std::pair<LargeObject, LargeObject> split = largeObject.split(size);
168         largeObject = split.first;
169         nextLargeObject = split.second;
170     }
171
172     largeObject.setFree(false);
173     Object object(largeObject.begin());
174     object.line()->ref(lock);
175     BASSERT(object.chunk()->objectType() == ObjectType::Large);
176
177     if (nextLargeObject) {
178         BASSERT(!nextLargeObject.nextCanMerge());
179         m_largeObjects.insert(nextLargeObject);
180     }
181
182     return largeObject;
183 }
184
185 inline LargeObject& Heap::splitAndAllocate(std::lock_guard<StaticMutex>& lock, LargeObject& largeObject, size_t alignment, size_t size)
186 {
187     LargeObject prevLargeObject;
188     LargeObject nextLargeObject;
189
190     size_t alignmentMask = alignment - 1;
191     if (test(largeObject.begin(), alignmentMask)) {
192         size_t prefixSize = roundUpToMultipleOf(alignment, largeObject.begin() + largeMin) - largeObject.begin();
193         std::pair<LargeObject, LargeObject> pair = largeObject.split(prefixSize);
194         prevLargeObject = pair.first;
195         largeObject = pair.second;
196     }
197
198     BASSERT(largeObject.isFree());
199
200     if (largeObject.size() - size >= largeMin) {
201         std::pair<LargeObject, LargeObject> split = largeObject.split(size);
202         largeObject = split.first;
203         nextLargeObject = split.second;
204     }
205
206     largeObject.setFree(false);
207     Object object(largeObject.begin());
208     object.line()->ref(lock);
209     BASSERT(object.chunk()->objectType() == ObjectType::Large);
210
211     if (prevLargeObject) {
212         LargeObject merged = prevLargeObject.merge();
213         m_largeObjects.insert(merged);
214     }
215
216     if (nextLargeObject) {
217         LargeObject merged = nextLargeObject.merge();
218         m_largeObjects.insert(merged);
219     }
220
221     return largeObject;
222 }
223
224 void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t size)
225 {
226     BASSERT(size <= largeMax);
227     BASSERT(size >= largeMin);
228     BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
229     
230     LargeObject largeObject = m_largeObjects.take(size);
231     if (!largeObject)
232         largeObject = m_vmHeap.allocateLargeObject(lock, size);
233
234     if (largeObject.vmState().hasVirtual()) {
235         m_isAllocatingPages = true;
236         // We commit before we split in order to avoid split/merge commit/decommit churn.
237         vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
238         largeObject.setVMState(VMState::Physical);
239     }
240
241     largeObject = splitAndAllocate(lock, largeObject, size);
242
243     return largeObject.begin();
244 }
245
246 void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
247 {
248     BASSERT(size <= largeMax);
249     BASSERT(size >= largeMin);
250     BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
251     BASSERT(unalignedSize <= largeMax);
252     BASSERT(unalignedSize >= largeMin);
253     BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
254     BASSERT(alignment <= chunkSize / 2);
255     BASSERT(alignment >= largeAlignment);
256     BASSERT(isPowerOfTwo(alignment));
257
258     LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
259     if (!largeObject)
260         largeObject = m_vmHeap.allocateLargeObject(lock, alignment, size, unalignedSize);
261
262     if (largeObject.vmState().hasVirtual()) {
263         m_isAllocatingPages = true;
264         // We commit before we split in order to avoid split/merge commit/decommit churn.
265         vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
266         largeObject.setVMState(VMState::Physical);
267     }
268
269     largeObject = splitAndAllocate(lock, largeObject, alignment, size);
270
271     return largeObject.begin();
272 }
273
274 void Heap::shrinkLarge(std::lock_guard<StaticMutex>& lock, LargeObject& largeObject, size_t newSize)
275 {
276     std::pair<LargeObject, LargeObject> split = largeObject.split(newSize);
277     deallocateLarge(lock, split.second);
278 }
279
280 void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject& largeObject)
281 {
282     BASSERT(!largeObject.isFree());
283     BASSERT(Object(largeObject.begin()).chunk()->objectType() == ObjectType::Large);
284     largeObject.setFree(true);
285     
286     LargeObject merged = largeObject.merge();
287     m_largeObjects.insert(merged);
288     m_scavenger.run();
289 }
290
291 SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
292 {
293     if (!m_smallPagesWithFreeLines[sizeClass].isEmpty())
294         return m_smallPagesWithFreeLines[sizeClass].popFront();
295
296     SmallPage* page = [&]() {
297         size_t pageClass = m_pageClasses[sizeClass];
298         if (!m_smallPages[pageClass].isEmpty())
299             return m_smallPages[pageClass].pop();
300
301         m_isAllocatingPages = true;
302         return m_vmHeap.allocateSmallPage(lock, pageClass);
303     }();
304
305     page->setSizeClass(sizeClass);
306     return page;
307 }
308
309 void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object)
310 {
311     BASSERT(!object.line()->refCount(lock));
312     SmallPage* page = object.page();
313     if (object.chunk()->objectType() == ObjectType::Large)
314         return deallocateLarge(lock, LargeObject(object.begin()));
315
316     page->deref(lock);
317     if (!page->hasFreeLines(lock)) {
318         page->setHasFreeLines(lock, true);
319         m_smallPagesWithFreeLines[page->sizeClass()].push(page);
320     }
321
322     if (page->refCount(lock))
323         return;
324
325     size_t sizeClass = page->sizeClass();
326     size_t pageClass = m_pageClasses[sizeClass];
327
328     m_smallPagesWithFreeLines[sizeClass].remove(page);
329     m_smallPages[pageClass].push(page);
330
331     m_scavenger.run();
332 }
333
334 void Heap::allocateSmallBumpRangesByMetadata(
335     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
336     BumpAllocator& allocator, BumpRangeCache& rangeCache)
337 {
338     SmallPage* page = allocateSmallPage(lock, sizeClass);
339     SmallLine* lines = page->begin();
340     BASSERT(page->hasFreeLines(lock));
341     size_t smallLineCount = m_vmPageSizePhysical / smallLineSize;
342     LineMetadata* pageMetadata = &m_smallLineMetadata[sizeClass * smallLineCount];
343     
344     auto findSmallBumpRange = [&](size_t& lineNumber) {
345         for ( ; lineNumber < smallLineCount; ++lineNumber) {
346             if (!lines[lineNumber].refCount(lock)) {
347                 if (pageMetadata[lineNumber].objectCount)
348                     return true;
349             }
350         }
351         return false;
352     };
353
354     auto allocateSmallBumpRange = [&](size_t& lineNumber) -> BumpRange {
355         char* begin = lines[lineNumber].begin() + pageMetadata[lineNumber].startOffset;
356         unsigned short objectCount = 0;
357         
358         for ( ; lineNumber < smallLineCount; ++lineNumber) {
359             if (lines[lineNumber].refCount(lock))
360                 break;
361
362             if (!pageMetadata[lineNumber].objectCount)
363                 continue;
364
365             objectCount += pageMetadata[lineNumber].objectCount;
366             lines[lineNumber].ref(lock, pageMetadata[lineNumber].objectCount);
367             page->ref(lock);
368         }
369         return { begin, objectCount };
370     };
371
372     size_t lineNumber = 0;
373     for (;;) {
374         if (!findSmallBumpRange(lineNumber)) {
375             page->setHasFreeLines(lock, false);
376             BASSERT(allocator.canAllocate());
377             return;
378         }
379
380         // In a fragmented page, some free ranges might not fit in the cache.
381         if (rangeCache.size() == rangeCache.capacity()) {
382             m_smallPagesWithFreeLines[sizeClass].push(page);
383             BASSERT(allocator.canAllocate());
384             return;
385         }
386
387         BumpRange bumpRange = allocateSmallBumpRange(lineNumber);
388         if (allocator.canAllocate())
389             rangeCache.push(bumpRange);
390         else
391             allocator.refill(bumpRange);
392     }
393 }
394
395 void Heap::allocateSmallBumpRangesByObject(
396     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
397     BumpAllocator& allocator, BumpRangeCache& rangeCache)
398 {
399     size_t size = allocator.size();
400     SmallPage* page = allocateSmallPage(lock, sizeClass);
401     BASSERT(page->hasFreeLines(lock));
402
403     auto findSmallBumpRange = [&](Object& it, Object& end) {
404         for ( ; it + size <= end; it = it + size) {
405             if (!it.line()->refCount(lock))
406                 return true;
407         }
408         return false;
409     };
410
411     auto allocateSmallBumpRange = [&](Object& it, Object& end) -> BumpRange {
412         char* begin = it.begin();
413         unsigned short objectCount = 0;
414         for ( ; it + size <= end; it = it + size) {
415             if (it.line()->refCount(lock))
416                 break;
417
418             ++objectCount;
419             it.line()->ref(lock);
420             it.page()->ref(lock);
421         }
422         return { begin, objectCount };
423     };
424
425     Object it(page->begin()->begin());
426     Object end(it + pageSize(m_pageClasses[sizeClass]));
427     for (;;) {
428         if (!findSmallBumpRange(it, end)) {
429             page->setHasFreeLines(lock, false);
430             BASSERT(allocator.canAllocate());
431             return;
432         }
433
434         // In a fragmented page, some free ranges might not fit in the cache.
435         if (rangeCache.size() == rangeCache.capacity()) {
436             m_smallPagesWithFreeLines[sizeClass].push(page);
437             BASSERT(allocator.canAllocate());
438             return;
439         }
440
441         BumpRange bumpRange = allocateSmallBumpRange(it, end);
442         if (allocator.canAllocate())
443             rangeCache.push(bumpRange);
444         else
445             allocator.refill(bumpRange);
446     }
447 }
448
449 void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
450 {
451     void* result = tryAllocateXLarge(lock, alignment, size);
452     RELEASE_BASSERT(result);
453     return result;
454 }
455
456 void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
457 {
458     return allocateXLarge(lock, alignment, size);
459 }
460
461 XLargeRange Heap::splitAndAllocate(XLargeRange& range, size_t alignment, size_t size)
462 {
463     XLargeRange prev;
464     XLargeRange next;
465
466     size_t alignmentMask = alignment - 1;
467     if (test(range.begin(), alignmentMask)) {
468         size_t prefixSize = roundUpToMultipleOf(alignment, range.begin()) - range.begin();
469         std::pair<XLargeRange, XLargeRange> pair = range.split(prefixSize);
470         prev = pair.first;
471         range = pair.second;
472     }
473
474     if (range.size() - size >= xLargeAlignment) {
475         size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
476         std::pair<XLargeRange, XLargeRange> pair = range.split(alignedSize);
477         range = pair.first;
478         next = pair.second;
479     }
480
481     // At this point our range might contain an unused tail fragment. This is
482     // common. We can't allocate the tail fragment because it's aligned to less
483     // than xLargeAlignment. So, we pair the allocation with its tail fragment
484     // in the allocated list. This is an important optimization because it
485     // keeps the free list short, speeding up allocation and merging.
486
487     std::pair<XLargeRange, XLargeRange> allocated = range.split(roundUpToMultipleOf(m_vmPageSizePhysical, size));
488     if (allocated.first.vmState().hasVirtual()) {
489         vmAllocatePhysicalPagesSloppy(allocated.first.begin(), allocated.first.size());
490         allocated.first.setVMState(VMState::Physical);
491     }
492
493     m_xLargeMap.addAllocated(prev, allocated, next);
494     return allocated.first;
495 }
496
497 void* Heap::tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
498 {
499     BASSERT(isPowerOfTwo(alignment));
500     BASSERT(alignment < xLargeMax);
501
502     m_isAllocatingPages = true;
503
504     size = std::max(m_vmPageSizePhysical, size);
505     alignment = roundUpToMultipleOf<xLargeAlignment>(alignment);
506
507     XLargeRange range = m_xLargeMap.takeFree(alignment, size);
508     if (!range) {
509         // We allocate VM in aligned multiples to increase the chances that
510         // the OS will provide contiguous ranges that we can merge.
511         size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
512
513         void* begin = tryVMAllocate(alignment, alignedSize);
514         if (!begin)
515             return nullptr;
516         range = XLargeRange(begin, alignedSize, VMState::Virtual);
517     }
518
519     return splitAndAllocate(range, alignment, size).begin();
520 }
521
522 size_t Heap::xLargeSize(std::unique_lock<StaticMutex>&, void* object)
523 {
524     return m_xLargeMap.getAllocated(object).size();
525 }
526
527 void Heap::shrinkXLarge(std::unique_lock<StaticMutex>&, const Range& object, size_t newSize)
528 {
529     BASSERT(object.size() > newSize);
530
531     if (object.size() - newSize < m_vmPageSizePhysical)
532         return;
533     
534     XLargeRange range = m_xLargeMap.takeAllocated(object.begin());
535     splitAndAllocate(range, xLargeAlignment, newSize);
536
537     m_scavenger.run();
538 }
539
540 void Heap::deallocateXLarge(std::unique_lock<StaticMutex>&, void* object)
541 {
542     XLargeRange range = m_xLargeMap.takeAllocated(object);
543     m_xLargeMap.addFree(range);
544     
545     m_scavenger.run();
546 }
547
548 } // namespace bmalloc