[JSC] Less contended MetaAllocator
[WebKit-https.git] / Source / WTF / wtf / MetaAllocator.cpp
1 /*
2  * Copyright (C) 2011-2018 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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer. 
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution. 
13  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission. 
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30 #include <wtf/MetaAllocator.h>
31
32 #include <wtf/DataLog.h>
33 #include <wtf/FastMalloc.h>
34 #include <wtf/ProcessID.h>
35
36 namespace WTF {
37
38 MetaAllocator::~MetaAllocator()
39 {
40     for (FreeSpaceNode* node = m_freeSpaceSizeMap.first(); node;) {
41         FreeSpaceNode* next = node->successor();
42         m_freeSpaceSizeMap.remove(node);
43         freeFreeSpaceNode(node);
44         node = next;
45     }
46 #ifndef NDEBUG
47     ASSERT(!m_mallocBalance);
48 #endif
49 }
50
51 void MetaAllocatorTracker::notify(MetaAllocatorHandle* handle)
52 {
53     m_allocations.insert(handle);
54 }
55
56 void MetaAllocatorTracker::release(MetaAllocatorHandle* handle)
57 {
58     m_allocations.remove(handle);
59 }
60
61 ALWAYS_INLINE void MetaAllocator::release(MetaAllocatorHandle* handle)
62 {
63     LockHolder locker(&m_lock);
64     if (handle->sizeInBytes()) {
65         void* start = handle->start().untaggedPtr();
66         size_t sizeInBytes = handle->sizeInBytes();
67         decrementPageOccupancy(start, sizeInBytes);
68         addFreeSpaceFromReleasedHandle(FreeSpacePtr(start), sizeInBytes);
69     }
70
71     if (UNLIKELY(!!m_tracker))
72         m_tracker->release(handle);
73 }
74
75 MetaAllocatorHandle::MetaAllocatorHandle(MetaAllocator* allocator, void* start, size_t sizeInBytes, void* ownerUID)
76     : m_allocator(allocator)
77     , m_start(start)
78     , m_end(reinterpret_cast<char*>(start) + sizeInBytes)
79     , m_ownerUID(ownerUID)
80 {
81     ASSERT(allocator);
82     ASSERT(start);
83     ASSERT(sizeInBytes);
84 }
85
86 MetaAllocatorHandle::~MetaAllocatorHandle()
87 {
88     ASSERT(m_allocator);
89     m_allocator->release(this);
90 }
91
92 void MetaAllocatorHandle::shrink(size_t newSizeInBytes)
93 {
94     size_t sizeInBytes = this->sizeInBytes();
95     ASSERT(newSizeInBytes <= sizeInBytes);
96
97     LockHolder locker(&m_allocator->m_lock);
98
99     newSizeInBytes = m_allocator->roundUp(newSizeInBytes);
100     
101     ASSERT(newSizeInBytes <= sizeInBytes);
102
103     if (newSizeInBytes == sizeInBytes)
104         return;
105
106     uintptr_t freeStart = m_start.untaggedPtr<uintptr_t>() + newSizeInBytes;
107     size_t freeSize = sizeInBytes - newSizeInBytes;
108     uintptr_t freeEnd = freeStart + freeSize;
109     
110     uintptr_t firstCompletelyFreePage = (freeStart + m_allocator->m_pageSize - 1) & ~(m_allocator->m_pageSize - 1);
111     if (firstCompletelyFreePage < freeEnd)
112         m_allocator->decrementPageOccupancy(reinterpret_cast<void*>(firstCompletelyFreePage), freeSize - (firstCompletelyFreePage - freeStart));
113
114     m_allocator->addFreeSpaceFromReleasedHandle(MetaAllocator::FreeSpacePtr(freeStart), freeSize);
115
116     m_end = m_start + newSizeInBytes;
117 }
118
119 void MetaAllocatorHandle::dump(PrintStream& out) const
120 {
121     out.print(RawPointer(start().untaggedPtr()), "...", RawPointer(end().untaggedPtr()));
122 }
123
124 MetaAllocator::MetaAllocator(size_t allocationGranule, size_t pageSize)
125     : m_allocationGranule(allocationGranule)
126     , m_pageSize(pageSize)
127     , m_bytesAllocated(0)
128     , m_bytesReserved(0)
129     , m_bytesCommitted(0)
130     , m_tracker(0)
131 #ifndef NDEBUG
132     , m_mallocBalance(0)
133 #endif
134 #if ENABLE(META_ALLOCATOR_PROFILE)
135     , m_numAllocations(0)
136     , m_numFrees(0)
137 #endif
138 {
139     for (m_logPageSize = 0; m_logPageSize < 32; ++m_logPageSize) {
140         if (static_cast<size_t>(1) << m_logPageSize == m_pageSize)
141             break;
142     }
143     
144     ASSERT(static_cast<size_t>(1) << m_logPageSize == m_pageSize);
145     
146     for (m_logAllocationGranule = 0; m_logAllocationGranule < 32; ++m_logAllocationGranule) {
147         if (static_cast<size_t>(1) << m_logAllocationGranule == m_allocationGranule)
148             break;
149     }
150     
151     ASSERT(static_cast<size_t>(1) << m_logAllocationGranule == m_allocationGranule);
152 }
153
154 RefPtr<MetaAllocatorHandle> MetaAllocator::allocate(size_t sizeInBytes, void* ownerUID)
155 {
156     LockHolder locker(&m_lock);
157
158     if (!sizeInBytes)
159         return nullptr;
160     
161     sizeInBytes = roundUp(sizeInBytes);
162
163     FreeSpacePtr start = findAndRemoveFreeSpace(sizeInBytes);
164     if (!start) {
165         size_t requestedNumberOfPages = (sizeInBytes + m_pageSize - 1) >> m_logPageSize;
166         size_t numberOfPages = requestedNumberOfPages;
167         
168         start = allocateNewSpace(numberOfPages);
169         if (!start)
170             return nullptr;
171         
172         ASSERT(numberOfPages >= requestedNumberOfPages);
173         
174         size_t roundedUpSize = numberOfPages << m_logPageSize;
175         
176         ASSERT(roundedUpSize >= sizeInBytes);
177         
178         m_bytesReserved += roundedUpSize;
179         
180         if (roundedUpSize > sizeInBytes) {
181             FreeSpacePtr freeSpaceStart = start + sizeInBytes;
182             size_t freeSpaceSize = roundedUpSize - sizeInBytes;
183             addFreeSpace(freeSpaceStart, freeSpaceSize);
184         }
185     }
186     incrementPageOccupancy(start.untaggedPtr(), sizeInBytes);
187     m_bytesAllocated += sizeInBytes;
188 #if ENABLE(META_ALLOCATOR_PROFILE)
189     m_numAllocations++;
190 #endif
191
192     auto handle = adoptRef(*new MetaAllocatorHandle(this, start.untaggedPtr(), sizeInBytes, ownerUID));
193
194     if (UNLIKELY(!!m_tracker))
195         m_tracker->notify(handle.ptr());
196
197     return handle;
198 }
199
200 MetaAllocator::Statistics MetaAllocator::currentStatistics()
201 {
202     LockHolder locker(&m_lock);
203     Statistics result;
204     result.bytesAllocated = m_bytesAllocated;
205     result.bytesReserved = m_bytesReserved;
206     result.bytesCommitted = m_bytesCommitted;
207     return result;
208 }
209
210 MetaAllocator::FreeSpacePtr MetaAllocator::findAndRemoveFreeSpace(size_t sizeInBytes)
211 {
212     FreeSpaceNode* node = m_freeSpaceSizeMap.findLeastGreaterThanOrEqual(sizeInBytes);
213     
214     if (!node)
215         return 0;
216     
217     size_t nodeSizeInBytes = node->sizeInBytes();
218     ASSERT(nodeSizeInBytes >= sizeInBytes);
219
220     m_freeSpaceSizeMap.remove(node);
221
222     FreeSpacePtr result;
223
224     if (nodeSizeInBytes == sizeInBytes) {
225         // Easy case: perfect fit, so just remove the node entirely.
226         result = node->m_start;
227         
228         m_freeSpaceStartAddressMap.remove(node->m_start);
229         m_freeSpaceEndAddressMap.remove(node->m_end);
230         freeFreeSpaceNode(node);
231     } else {
232         // Try to be a good citizen and ensure that the returned chunk of memory
233         // straddles as few pages as possible, but only insofar as doing so will
234         // not increase fragmentation. The intuition is that minimizing
235         // fragmentation is a strictly higher priority than minimizing the number
236         // of committed pages, since in the long run, smaller fragmentation means
237         // fewer committed pages and fewer failures in general.
238         
239         uintptr_t nodeStartAsInt = node->m_start.untaggedPtr<uintptr_t>();
240         uintptr_t firstPage = nodeStartAsInt >> m_logPageSize;
241         uintptr_t lastPage = (nodeStartAsInt + nodeSizeInBytes - 1) >> m_logPageSize;
242
243         uintptr_t lastPageForLeftAllocation = (nodeStartAsInt + sizeInBytes - 1) >> m_logPageSize;
244         uintptr_t firstPageForRightAllocation = (nodeStartAsInt + nodeSizeInBytes - sizeInBytes) >> m_logPageSize;
245         
246         if (lastPageForLeftAllocation - firstPage + 1 <= lastPage - firstPageForRightAllocation + 1) {
247             // Allocate in the left side of the returned chunk, and slide the node to the right.
248             result = node->m_start;
249             
250             m_freeSpaceStartAddressMap.remove(node->m_start);
251
252             node->m_start += sizeInBytes;
253
254             m_freeSpaceSizeMap.insert(node);
255             m_freeSpaceStartAddressMap.add(node->m_start, node);
256         } else {
257             // Allocate in the right size of the returned chunk, and slide the node to the left;
258
259             result = node->m_end - sizeInBytes;
260
261             m_freeSpaceEndAddressMap.remove(node->m_end);
262
263             node->m_end = result;
264
265             m_freeSpaceSizeMap.insert(node);
266             m_freeSpaceEndAddressMap.add(result, node);
267         }
268     }
269     
270 #if ENABLE(META_ALLOCATOR_PROFILE)
271     dumpProfile();
272 #endif
273
274     return result;
275 }
276
277 void MetaAllocator::addFreeSpaceFromReleasedHandle(FreeSpacePtr start, size_t sizeInBytes)
278 {
279 #if ENABLE(META_ALLOCATOR_PROFILE)
280     m_numFrees++;
281 #endif
282     m_bytesAllocated -= sizeInBytes;
283     addFreeSpace(start, sizeInBytes);
284 }
285
286 void MetaAllocator::addFreshFreeSpace(void* start, size_t sizeInBytes)
287 {
288     LockHolder locker(&m_lock);
289     m_bytesReserved += sizeInBytes;
290     addFreeSpace(FreeSpacePtr(start), sizeInBytes);
291 }
292
293 size_t MetaAllocator::debugFreeSpaceSize()
294 {
295 #ifndef NDEBUG
296     LockHolder locker(&m_lock);
297     size_t result = 0;
298     for (FreeSpaceNode* node = m_freeSpaceSizeMap.first(); node; node = node->successor())
299         result += node->sizeInBytes();
300     return result;
301 #else
302     CRASH();
303     return 0;
304 #endif
305 }
306
307 void MetaAllocator::addFreeSpace(FreeSpacePtr start, size_t sizeInBytes)
308 {
309     FreeSpacePtr end = start + sizeInBytes;
310
311     HashMap<FreeSpacePtr, FreeSpaceNode*>::iterator leftNeighbor = m_freeSpaceEndAddressMap.find(start);
312     HashMap<FreeSpacePtr, FreeSpaceNode*>::iterator rightNeighbor = m_freeSpaceStartAddressMap.find(end);
313
314     if (leftNeighbor != m_freeSpaceEndAddressMap.end()) {
315         // We have something we can coalesce with on the left. Remove it from the tree, and
316         // remove its end from the end address map.
317         
318         ASSERT(leftNeighbor->value->m_end == leftNeighbor->key);
319
320         FreeSpaceNode* leftNode = leftNeighbor->value;
321
322         FreeSpacePtr leftEnd = leftNode->m_end;
323
324         ASSERT(leftEnd == start);
325         
326         m_freeSpaceSizeMap.remove(leftNode);
327         m_freeSpaceEndAddressMap.remove(leftEnd);
328         
329         // Now check if there is also something to coalesce with on the right.
330         if (rightNeighbor != m_freeSpaceStartAddressMap.end()) {
331             // Freeing something in the middle of free blocks. Coalesce both left and
332             // right, whilst removing the right neighbor from the maps.
333             
334             ASSERT(rightNeighbor->value->m_start == rightNeighbor->key);
335             
336             FreeSpaceNode* rightNode = rightNeighbor->value;
337             FreeSpacePtr rightStart = rightNeighbor->key;
338             size_t rightSize = rightNode->sizeInBytes();
339             FreeSpacePtr rightEnd = rightNode->m_end;
340
341             ASSERT(rightStart == end);
342             ASSERT(leftNode->m_start + (leftNode->sizeInBytes() + sizeInBytes + rightSize) == rightEnd);
343
344             m_freeSpaceSizeMap.remove(rightNode);
345             m_freeSpaceStartAddressMap.remove(rightStart);
346             m_freeSpaceEndAddressMap.remove(rightEnd);
347             
348             freeFreeSpaceNode(rightNode);
349
350             leftNode->m_end += (sizeInBytes + rightSize);
351
352             m_freeSpaceSizeMap.insert(leftNode);
353             m_freeSpaceEndAddressMap.add(rightEnd, leftNode);
354         } else {
355             leftNode->m_end += sizeInBytes;
356
357             m_freeSpaceSizeMap.insert(leftNode);
358             m_freeSpaceEndAddressMap.add(end, leftNode);
359         }
360     } else {
361         // Cannot coalesce with left; try to see if we can coalesce with right.
362         
363         if (rightNeighbor != m_freeSpaceStartAddressMap.end()) {
364             FreeSpaceNode* rightNode = rightNeighbor->value;
365             FreeSpacePtr rightStart = rightNeighbor->key;
366
367             ASSERT(rightStart == end);
368             ASSERT(start + (sizeInBytes + rightNode->sizeInBytes()) == rightNode->m_end);
369
370             m_freeSpaceSizeMap.remove(rightNode);
371             m_freeSpaceStartAddressMap.remove(rightStart);
372
373             rightNode->m_start = start;
374
375             m_freeSpaceSizeMap.insert(rightNode);
376             m_freeSpaceStartAddressMap.add(start, rightNode);
377         } else {
378             // Nothing to coalesce with, so create a new free space node and add it.
379             
380             FreeSpaceNode* node = allocFreeSpaceNode();
381
382             node->m_start = start;
383             node->m_end = start + sizeInBytes;
384
385             m_freeSpaceSizeMap.insert(node);
386             m_freeSpaceStartAddressMap.add(start, node);
387             m_freeSpaceEndAddressMap.add(end, node);
388         }
389     }
390     
391 #if ENABLE(META_ALLOCATOR_PROFILE)
392     dumpProfile();
393 #endif
394 }
395
396 void MetaAllocator::incrementPageOccupancy(void* address, size_t sizeInBytes)
397 {
398     uintptr_t firstPage = reinterpret_cast<uintptr_t>(address) >> m_logPageSize;
399     uintptr_t lastPage = (reinterpret_cast<uintptr_t>(address) + sizeInBytes - 1) >> m_logPageSize;
400
401     uintptr_t currentPageStart = 0;
402     size_t count = 0;
403     auto flushNeedPages = [&] {
404         if (!currentPageStart)
405             return;
406         notifyNeedPage(reinterpret_cast<void*>(currentPageStart << m_logPageSize), count);
407         currentPageStart = 0;
408         count = 0;
409     };
410     
411     for (uintptr_t page = firstPage; page <= lastPage; ++page) {
412         auto result = m_pageOccupancyMap.add(page, 1);
413         if (result.isNewEntry) {
414             m_bytesCommitted += m_pageSize;
415             if (!currentPageStart)
416                 currentPageStart = page;
417             ++count;
418         } else {
419             result.iterator->value++;
420             flushNeedPages();
421         }
422     }
423     flushNeedPages();
424 }
425
426 void MetaAllocator::decrementPageOccupancy(void* address, size_t sizeInBytes)
427 {
428     uintptr_t firstPage = reinterpret_cast<uintptr_t>(address) >> m_logPageSize;
429     uintptr_t lastPage = (reinterpret_cast<uintptr_t>(address) + sizeInBytes - 1) >> m_logPageSize;
430
431     uintptr_t currentPageStart = 0;
432     size_t count = 0;
433     auto flushFreePages = [&] {
434         if (!currentPageStart)
435             return;
436         notifyPageIsFree(reinterpret_cast<void*>(currentPageStart << m_logPageSize), count);
437         currentPageStart = 0;
438         count = 0;
439     };
440     
441     for (uintptr_t page = firstPage; page <= lastPage; ++page) {
442         HashMap<uintptr_t, size_t>::iterator iter = m_pageOccupancyMap.find(page);
443         ASSERT(iter != m_pageOccupancyMap.end());
444         if (!--(iter->value)) {
445             m_pageOccupancyMap.remove(iter);
446             m_bytesCommitted -= m_pageSize;
447             if (!currentPageStart)
448                 currentPageStart = page;
449             ++count;
450         } else
451             flushFreePages();
452     }
453     flushFreePages();
454 }
455
456 bool MetaAllocator::isInAllocatedMemory(const AbstractLocker&, void* address)
457 {
458     ASSERT(m_lock.isLocked());
459     uintptr_t page = reinterpret_cast<uintptr_t>(address) >> m_logPageSize;
460     return m_pageOccupancyMap.contains(page);
461 }
462
463 size_t MetaAllocator::roundUp(size_t sizeInBytes)
464 {
465     if (std::numeric_limits<size_t>::max() - m_allocationGranule <= sizeInBytes)
466         CRASH();
467     return (sizeInBytes + m_allocationGranule - 1) & ~(m_allocationGranule - 1);
468 }
469
470 MetaAllocator::FreeSpaceNode* MetaAllocator::allocFreeSpaceNode()
471 {
472 #ifndef NDEBUG
473     m_mallocBalance++;
474 #endif
475     return new (NotNull, fastMalloc(sizeof(FreeSpaceNode))) FreeSpaceNode();
476 }
477
478 void MetaAllocator::freeFreeSpaceNode(FreeSpaceNode* node)
479 {
480 #ifndef NDEBUG
481     m_mallocBalance--;
482 #endif
483     fastFree(node);
484 }
485
486 #if ENABLE(META_ALLOCATOR_PROFILE)
487 void MetaAllocator::dumpProfile()
488 {
489     dataLogF(
490         "%d: MetaAllocator(%p): num allocations = %u, num frees = %u, allocated = %lu, reserved = %lu, committed = %lu\n",
491         getCurrentProcessID(), this, m_numAllocations, m_numFrees, m_bytesAllocated, m_bytesReserved, m_bytesCommitted);
492 }
493 #endif
494
495 } // namespace WTF
496
497