ac0d7dec8844fa444aab5418bddf8d5f227f0c58
[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 "Chunk.h"
29 #include "PerProcess.h"
30 #include "SmallLine.h"
31 #include "SmallPage.h"
32 #include <thread>
33
34 namespace bmalloc {
35
36 Heap::Heap(std::lock_guard<StaticMutex>&)
37     : m_vmPageSizePhysical(vmPageSizePhysical())
38     , m_isAllocatingPages(false)
39     , m_scavenger(*this, &Heap::concurrentScavenge)
40 {
41     RELEASE_BASSERT(vmPageSizePhysical() >= smallPageSize);
42     RELEASE_BASSERT(vmPageSize() >= vmPageSizePhysical());
43
44     initializeLineMetadata();
45     initializePageMetadata();
46 }
47
48 void Heap::initializeLineMetadata()
49 {
50     size_t sizeClassCount = bmalloc::sizeClass(smallLineSize);
51     size_t smallLineCount = m_vmPageSizePhysical / smallLineSize;
52     m_smallLineMetadata.grow(sizeClassCount * smallLineCount);
53
54     for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) {
55         size_t size = objectSize(sizeClass);
56         LineMetadata* pageMetadata = &m_smallLineMetadata[sizeClass * smallLineCount];
57
58         size_t object = 0;
59         size_t line = 0;
60         while (object < m_vmPageSizePhysical) {
61             line = object / smallLineSize;
62             size_t leftover = object % smallLineSize;
63
64             size_t objectCount;
65             size_t remainder;
66             divideRoundingUp(smallLineSize - leftover, size, objectCount, remainder);
67
68             pageMetadata[line] = { static_cast<unsigned char>(leftover), static_cast<unsigned char>(objectCount) };
69
70             object += objectCount * size;
71         }
72
73         // Don't allow the last object in a page to escape the page.
74         if (object > m_vmPageSizePhysical) {
75             BASSERT(pageMetadata[line].objectCount);
76             --pageMetadata[line].objectCount;
77         }
78     }
79 }
80
81 void Heap::initializePageMetadata()
82 {
83     auto computePageSize = [&](size_t sizeClass) {
84         size_t size = objectSize(sizeClass);
85         if (sizeClass < bmalloc::sizeClass(smallLineSize))
86             return m_vmPageSizePhysical;
87
88         for (size_t pageSize = m_vmPageSizePhysical;
89             pageSize < pageSizeMax;
90             pageSize += m_vmPageSizePhysical) {
91             RELEASE_BASSERT(pageSize <= chunkSize / 2);
92             size_t waste = pageSize % size;
93             if (waste <= pageSize / pageSizeWasteFactor)
94                 return pageSize;
95         }
96         
97         return pageSizeMax;
98     };
99
100     for (size_t i = 0; i < sizeClassCount; ++i)
101         m_pageClasses[i] = (computePageSize(i) - 1) / smallPageSize;
102 }
103
104 void Heap::concurrentScavenge()
105 {
106     std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
107     scavenge(lock, scavengeSleepDuration);
108 }
109
110 void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
111 {
112     waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
113
114     scavengeSmallPages(lock, sleepDuration);
115     scavengeLargeObjects(lock, sleepDuration);
116
117     sleep(lock, sleepDuration);
118 }
119
120 void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
121 {
122     for (auto& smallPages : m_smallPages) {
123         while (!smallPages.isEmpty()) {
124             SmallPage* page = smallPages.pop();
125             size_t pageClass = m_pageClasses[page->sizeClass()];
126             m_vmHeap.deallocateSmallPage(lock, pageClass, page);
127             waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
128         }
129     }
130 }
131
132 void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
133 {
134     auto& ranges = m_largeFree.ranges();
135     for (size_t i = ranges.size(); i-- > 0; i = std::min(i, ranges.size())) {
136         auto range = ranges.pop(i);
137
138         lock.unlock();
139         vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
140         lock.lock();
141
142         range.setPhysicalSize(0);
143         ranges.push(range);
144
145         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
146     }
147 }
148
149 SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
150 {
151     if (!m_smallPagesWithFreeLines[sizeClass].isEmpty())
152         return m_smallPagesWithFreeLines[sizeClass].popFront();
153
154     SmallPage* page = [&]() {
155         size_t pageClass = m_pageClasses[sizeClass];
156         if (!m_smallPages[pageClass].isEmpty())
157             return m_smallPages[pageClass].pop();
158
159         m_isAllocatingPages = true;
160
161         SmallPage* page = m_vmHeap.allocateSmallPage(lock, pageClass);
162         m_objectTypes.set(Chunk::get(page), ObjectType::Small);
163         return page;
164     }();
165
166     page->setSizeClass(sizeClass);
167     return page;
168 }
169
170 void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object)
171 {
172     BASSERT(!object.line()->refCount(lock));
173     SmallPage* page = object.page();
174     page->deref(lock);
175
176     if (!page->hasFreeLines(lock)) {
177         page->setHasFreeLines(lock, true);
178         m_smallPagesWithFreeLines[page->sizeClass()].push(page);
179     }
180
181     if (page->refCount(lock))
182         return;
183
184     size_t sizeClass = page->sizeClass();
185     size_t pageClass = m_pageClasses[sizeClass];
186
187     m_smallPagesWithFreeLines[sizeClass].remove(page);
188     m_smallPages[pageClass].push(page);
189
190     m_scavenger.run();
191 }
192
193 void Heap::allocateSmallBumpRangesByMetadata(
194     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
195     BumpAllocator& allocator, BumpRangeCache& rangeCache)
196 {
197     SmallPage* page = allocateSmallPage(lock, sizeClass);
198     SmallLine* lines = page->begin();
199     BASSERT(page->hasFreeLines(lock));
200     size_t smallLineCount = m_vmPageSizePhysical / smallLineSize;
201     LineMetadata* pageMetadata = &m_smallLineMetadata[sizeClass * smallLineCount];
202     
203     auto findSmallBumpRange = [&](size_t& lineNumber) {
204         for ( ; lineNumber < smallLineCount; ++lineNumber) {
205             if (!lines[lineNumber].refCount(lock)) {
206                 if (pageMetadata[lineNumber].objectCount)
207                     return true;
208             }
209         }
210         return false;
211     };
212
213     auto allocateSmallBumpRange = [&](size_t& lineNumber) -> BumpRange {
214         char* begin = lines[lineNumber].begin() + pageMetadata[lineNumber].startOffset;
215         unsigned short objectCount = 0;
216         
217         for ( ; lineNumber < smallLineCount; ++lineNumber) {
218             if (lines[lineNumber].refCount(lock))
219                 break;
220
221             if (!pageMetadata[lineNumber].objectCount)
222                 continue;
223
224             objectCount += pageMetadata[lineNumber].objectCount;
225             lines[lineNumber].ref(lock, pageMetadata[lineNumber].objectCount);
226             page->ref(lock);
227         }
228         return { begin, objectCount };
229     };
230
231     size_t lineNumber = 0;
232     for (;;) {
233         if (!findSmallBumpRange(lineNumber)) {
234             page->setHasFreeLines(lock, false);
235             BASSERT(allocator.canAllocate());
236             return;
237         }
238
239         // In a fragmented page, some free ranges might not fit in the cache.
240         if (rangeCache.size() == rangeCache.capacity()) {
241             m_smallPagesWithFreeLines[sizeClass].push(page);
242             BASSERT(allocator.canAllocate());
243             return;
244         }
245
246         BumpRange bumpRange = allocateSmallBumpRange(lineNumber);
247         if (allocator.canAllocate())
248             rangeCache.push(bumpRange);
249         else
250             allocator.refill(bumpRange);
251     }
252 }
253
254 void Heap::allocateSmallBumpRangesByObject(
255     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
256     BumpAllocator& allocator, BumpRangeCache& rangeCache)
257 {
258     size_t size = allocator.size();
259     SmallPage* page = allocateSmallPage(lock, sizeClass);
260     BASSERT(page->hasFreeLines(lock));
261
262     auto findSmallBumpRange = [&](Object& it, Object& end) {
263         for ( ; it + size <= end; it = it + size) {
264             if (!it.line()->refCount(lock))
265                 return true;
266         }
267         return false;
268     };
269
270     auto allocateSmallBumpRange = [&](Object& it, Object& end) -> BumpRange {
271         char* begin = it.address();
272         unsigned short objectCount = 0;
273         for ( ; it + size <= end; it = it + size) {
274             if (it.line()->refCount(lock))
275                 break;
276
277             ++objectCount;
278             it.line()->ref(lock);
279             it.page()->ref(lock);
280         }
281         return { begin, objectCount };
282     };
283
284     Object it(page->begin()->begin());
285     Object end(it + pageSize(m_pageClasses[sizeClass]));
286     for (;;) {
287         if (!findSmallBumpRange(it, end)) {
288             page->setHasFreeLines(lock, false);
289             BASSERT(allocator.canAllocate());
290             return;
291         }
292
293         // In a fragmented page, some free ranges might not fit in the cache.
294         if (rangeCache.size() == rangeCache.capacity()) {
295             m_smallPagesWithFreeLines[sizeClass].push(page);
296             BASSERT(allocator.canAllocate());
297             return;
298         }
299
300         BumpRange bumpRange = allocateSmallBumpRange(it, end);
301         if (allocator.canAllocate())
302             rangeCache.push(bumpRange);
303         else
304             allocator.refill(bumpRange);
305     }
306 }
307
308 XLargeRange Heap::splitAndAllocate(XLargeRange& range, size_t alignment, size_t size)
309 {
310     XLargeRange prev;
311     XLargeRange next;
312
313     size_t alignmentMask = alignment - 1;
314     if (test(range.begin(), alignmentMask)) {
315         size_t prefixSize = roundUpToMultipleOf(alignment, range.begin()) - range.begin();
316         std::pair<XLargeRange, XLargeRange> pair = range.split(prefixSize);
317         prev = pair.first;
318         range = pair.second;
319     }
320
321     if (range.size() - size > size / pageSizeWasteFactor) {
322         std::pair<XLargeRange, XLargeRange> pair = range.split(size);
323         range = pair.first;
324         next = pair.second;
325     }
326     
327     if (range.physicalSize() < range.size()) {
328         m_isAllocatingPages = true;
329
330         vmAllocatePhysicalPagesSloppy(range.begin() + range.physicalSize(), range.size() - range.physicalSize());
331         range.setPhysicalSize(range.size());
332     }
333     
334     if (prev)
335         m_largeFree.add(prev);
336
337     if (next)
338         m_largeFree.add(next);
339
340     m_objectTypes.set(Chunk::get(range.begin()), ObjectType::Large);
341
342     m_largeAllocated.set(range.begin(), range.size());
343     return range;
344 }
345
346 void* Heap::tryAllocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
347 {
348     BASSERT(isPowerOfTwo(alignment));
349
350     size_t roundedSize = size ? roundUpToMultipleOf(largeAlignment, size) : largeAlignment;
351     if (roundedSize < size) // Check for overflow
352         return nullptr;
353     size = roundedSize;
354
355     size_t roundedAlignment = roundUpToMultipleOf<largeAlignment>(alignment);
356     if (roundedAlignment < alignment) // Check for overflow
357         return nullptr;
358     alignment = roundedAlignment;
359
360     XLargeRange range = m_largeFree.remove(alignment, size);
361     if (!range) {
362         range = m_vmHeap.tryAllocateLargeChunk(lock, alignment, size);
363         if (!range)
364             return nullptr;
365
366         m_largeFree.add(range);
367         range = m_largeFree.remove(alignment, size);
368     }
369
370     return splitAndAllocate(range, alignment, size).begin();
371 }
372
373 void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
374 {
375     void* result = tryAllocateLarge(lock, alignment, size);
376     RELEASE_BASSERT(result);
377     return result;
378 }
379
380 bool Heap::isLarge(std::lock_guard<StaticMutex>&, void* object)
381 {
382     return m_objectTypes.get(Object(object).chunk()) == ObjectType::Large;
383 }
384
385 size_t Heap::largeSize(std::lock_guard<StaticMutex>&, void* object)
386 {
387     return m_largeAllocated.get(object);
388 }
389
390 void Heap::shrinkLarge(std::lock_guard<StaticMutex>&, const Range& object, size_t newSize)
391 {
392     BASSERT(object.size() > newSize);
393
394     size_t size = m_largeAllocated.remove(object.begin());
395     XLargeRange range = XLargeRange(object, size);
396     splitAndAllocate(range, alignment, newSize);
397
398     m_scavenger.run();
399 }
400
401 void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, void* object)
402 {
403     size_t size = m_largeAllocated.remove(object);
404     m_largeFree.add(XLargeRange(object, size, size));
405     
406     m_scavenger.run();
407 }
408
409 } // namespace bmalloc