dd06592058f2d218e976b464fc2398bb05970629
[WebKit-https.git] / Source / WTF / wtf / MetaAllocator.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  *
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 "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         decrementPageOccupancy(handle->start(), handle->sizeInBytes());
66         addFreeSpaceFromReleasedHandle(handle->start(), handle->sizeInBytes());
67     }
68
69     if (UNLIKELY(!!m_tracker))
70         m_tracker->release(handle);
71 }
72
73 MetaAllocatorHandle::MetaAllocatorHandle(MetaAllocator* allocator, void* start, size_t sizeInBytes, void* ownerUID)
74     : m_allocator(allocator)
75     , m_start(start)
76     , m_sizeInBytes(sizeInBytes)
77     , m_ownerUID(ownerUID)
78 {
79     ASSERT(allocator);
80     ASSERT(start);
81     ASSERT(sizeInBytes);
82 }
83
84 MetaAllocatorHandle::~MetaAllocatorHandle()
85 {
86     ASSERT(m_allocator);
87     m_allocator->release(this);
88 }
89
90 void MetaAllocatorHandle::shrink(size_t newSizeInBytes)
91 {
92     ASSERT(newSizeInBytes <= m_sizeInBytes);
93     
94     LockHolder locker(&m_allocator->m_lock);
95
96     newSizeInBytes = m_allocator->roundUp(newSizeInBytes);
97     
98     ASSERT(newSizeInBytes <= m_sizeInBytes);
99     
100     if (newSizeInBytes == m_sizeInBytes)
101         return;
102     
103     uintptr_t freeStart = reinterpret_cast<uintptr_t>(m_start) + newSizeInBytes;
104     size_t freeSize = m_sizeInBytes - newSizeInBytes;
105     uintptr_t freeEnd = freeStart + freeSize;
106     
107     uintptr_t firstCompletelyFreePage = (freeStart + m_allocator->m_pageSize - 1) & ~(m_allocator->m_pageSize - 1);
108     if (firstCompletelyFreePage < freeEnd)
109         m_allocator->decrementPageOccupancy(reinterpret_cast<void*>(firstCompletelyFreePage), freeSize - (firstCompletelyFreePage - freeStart));
110     
111     m_allocator->addFreeSpaceFromReleasedHandle(reinterpret_cast<void*>(freeStart), freeSize);
112     
113     m_sizeInBytes = newSizeInBytes;
114 }
115
116 void MetaAllocatorHandle::dump(PrintStream& out) const
117 {
118     out.print(RawPointer(start()), "...", RawPointer(end()));
119 }
120
121 MetaAllocator::MetaAllocator(size_t allocationGranule, size_t pageSize)
122     : m_allocationGranule(allocationGranule)
123     , m_pageSize(pageSize)
124     , m_bytesAllocated(0)
125     , m_bytesReserved(0)
126     , m_bytesCommitted(0)
127     , m_tracker(0)
128 #ifndef NDEBUG
129     , m_mallocBalance(0)
130 #endif
131 #if ENABLE(META_ALLOCATOR_PROFILE)
132     , m_numAllocations(0)
133     , m_numFrees(0)
134 #endif
135 {
136     for (m_logPageSize = 0; m_logPageSize < 32; ++m_logPageSize) {
137         if (static_cast<size_t>(1) << m_logPageSize == m_pageSize)
138             break;
139     }
140     
141     ASSERT(static_cast<size_t>(1) << m_logPageSize == m_pageSize);
142     
143     for (m_logAllocationGranule = 0; m_logAllocationGranule < 32; ++m_logAllocationGranule) {
144         if (static_cast<size_t>(1) << m_logAllocationGranule == m_allocationGranule)
145             break;
146     }
147     
148     ASSERT(static_cast<size_t>(1) << m_logAllocationGranule == m_allocationGranule);
149 }
150
151 PassRefPtr<MetaAllocatorHandle> MetaAllocator::allocate(size_t sizeInBytes, void* ownerUID)
152 {
153     LockHolder locker(&m_lock);
154
155     if (!sizeInBytes)
156         return 0;
157     
158     sizeInBytes = roundUp(sizeInBytes);
159     
160     void* start = findAndRemoveFreeSpace(sizeInBytes);
161     if (!start) {
162         size_t requestedNumberOfPages = (sizeInBytes + m_pageSize - 1) >> m_logPageSize;
163         size_t numberOfPages = requestedNumberOfPages;
164         
165         start = allocateNewSpace(numberOfPages);
166         if (!start)
167             return 0;
168         
169         ASSERT(numberOfPages >= requestedNumberOfPages);
170         
171         size_t roundedUpSize = numberOfPages << m_logPageSize;
172         
173         ASSERT(roundedUpSize >= sizeInBytes);
174         
175         m_bytesReserved += roundedUpSize;
176         
177         if (roundedUpSize > sizeInBytes) {
178             void* freeSpaceStart = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(start) + sizeInBytes);
179             size_t freeSpaceSize = roundedUpSize - sizeInBytes;
180             addFreeSpace(freeSpaceStart, freeSpaceSize);
181         }
182     }
183     incrementPageOccupancy(start, sizeInBytes);
184     m_bytesAllocated += sizeInBytes;
185 #if ENABLE(META_ALLOCATOR_PROFILE)
186     m_numAllocations++;
187 #endif
188
189     MetaAllocatorHandle* handle = new MetaAllocatorHandle(this, start, sizeInBytes, ownerUID);
190
191     if (UNLIKELY(!!m_tracker))
192         m_tracker->notify(handle);
193
194     return adoptRef(handle);
195 }
196
197 MetaAllocator::Statistics MetaAllocator::currentStatistics()
198 {
199     LockHolder locker(&m_lock);
200     Statistics result;
201     result.bytesAllocated = m_bytesAllocated;
202     result.bytesReserved = m_bytesReserved;
203     result.bytesCommitted = m_bytesCommitted;
204     return result;
205 }
206
207 void* MetaAllocator::findAndRemoveFreeSpace(size_t sizeInBytes)
208 {
209     FreeSpaceNode* node = m_freeSpaceSizeMap.findLeastGreaterThanOrEqual(sizeInBytes);
210     
211     if (!node)
212         return 0;
213     
214     ASSERT(node->m_sizeInBytes >= sizeInBytes);
215     
216     m_freeSpaceSizeMap.remove(node);
217     
218     void* result;
219     
220     if (node->m_sizeInBytes == sizeInBytes) {
221         // Easy case: perfect fit, so just remove the node entirely.
222         result = node->m_start;
223         
224         m_freeSpaceStartAddressMap.remove(node->m_start);
225         m_freeSpaceEndAddressMap.remove(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes));
226         freeFreeSpaceNode(node);
227     } else {
228         // Try to be a good citizen and ensure that the returned chunk of memory
229         // straddles as few pages as possible, but only insofar as doing so will
230         // not increase fragmentation. The intuition is that minimizing
231         // fragmentation is a strictly higher priority than minimizing the number
232         // of committed pages, since in the long run, smaller fragmentation means
233         // fewer committed pages and fewer failures in general.
234         
235         uintptr_t firstPage = reinterpret_cast<uintptr_t>(node->m_start) >> m_logPageSize;
236         uintptr_t lastPage = (reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes - 1) >> m_logPageSize;
237     
238         uintptr_t lastPageForLeftAllocation = (reinterpret_cast<uintptr_t>(node->m_start) + sizeInBytes - 1) >> m_logPageSize;
239         uintptr_t firstPageForRightAllocation = (reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes - sizeInBytes) >> m_logPageSize;
240         
241         if (lastPageForLeftAllocation - firstPage + 1 <= lastPage - firstPageForRightAllocation + 1) {
242             // Allocate in the left side of the returned chunk, and slide the node to the right.
243             result = node->m_start;
244             
245             m_freeSpaceStartAddressMap.remove(node->m_start);
246             
247             node->m_sizeInBytes -= sizeInBytes;
248             node->m_start = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + sizeInBytes);
249             
250             m_freeSpaceSizeMap.insert(node);
251             m_freeSpaceStartAddressMap.add(node->m_start, node);
252         } else {
253             // Allocate in the right size of the returned chunk, and slide the node to the left;
254             
255             result = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes - sizeInBytes);
256             
257             m_freeSpaceEndAddressMap.remove(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes));
258             
259             node->m_sizeInBytes -= sizeInBytes;
260             
261             m_freeSpaceSizeMap.insert(node);
262             m_freeSpaceEndAddressMap.add(result, node);
263         }
264     }
265     
266 #if ENABLE(META_ALLOCATOR_PROFILE)
267     dumpProfile();
268 #endif
269
270     return result;
271 }
272
273 void MetaAllocator::addFreeSpaceFromReleasedHandle(void* start, size_t sizeInBytes)
274 {
275 #if ENABLE(META_ALLOCATOR_PROFILE)
276     m_numFrees++;
277 #endif
278     m_bytesAllocated -= sizeInBytes;
279     addFreeSpace(start, sizeInBytes);
280 }
281
282 void MetaAllocator::addFreshFreeSpace(void* start, size_t sizeInBytes)
283 {
284     LockHolder locker(&m_lock);
285     m_bytesReserved += sizeInBytes;
286     addFreeSpace(start, sizeInBytes);
287 }
288
289 size_t MetaAllocator::debugFreeSpaceSize()
290 {
291 #ifndef NDEBUG
292     LockHolder locker(&m_lock);
293     size_t result = 0;
294     for (FreeSpaceNode* node = m_freeSpaceSizeMap.first(); node; node = node->successor())
295         result += node->m_sizeInBytes;
296     return result;
297 #else
298     CRASH();
299     return 0;
300 #endif
301 }
302
303 void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes)
304 {
305     void* end = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(start) + sizeInBytes);
306     
307     HashMap<void*, FreeSpaceNode*>::iterator leftNeighbor = m_freeSpaceEndAddressMap.find(start);
308     HashMap<void*, FreeSpaceNode*>::iterator rightNeighbor = m_freeSpaceStartAddressMap.find(end);
309     
310     if (leftNeighbor != m_freeSpaceEndAddressMap.end()) {
311         // We have something we can coalesce with on the left. Remove it from the tree, and
312         // remove its end from the end address map.
313         
314         ASSERT(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(leftNeighbor->value->m_start) + leftNeighbor->value->m_sizeInBytes) == leftNeighbor->key);
315         
316         FreeSpaceNode* leftNode = leftNeighbor->value;
317         
318         void* leftStart = leftNode->m_start;
319         size_t leftSize = leftNode->m_sizeInBytes;
320         void* leftEnd = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(leftStart) + leftSize);
321         
322         ASSERT(leftEnd == start);
323         
324         m_freeSpaceSizeMap.remove(leftNode);
325         m_freeSpaceEndAddressMap.remove(leftEnd);
326         
327         // Now check if there is also something to coalesce with on the right.
328         if (rightNeighbor != m_freeSpaceStartAddressMap.end()) {
329             // Freeing something in the middle of free blocks. Coalesce both left and
330             // right, whilst removing the right neighbor from the maps.
331             
332             ASSERT(rightNeighbor->value->m_start == rightNeighbor->key);
333             
334             FreeSpaceNode* rightNode = rightNeighbor->value;
335             void* rightStart = rightNeighbor->key;
336             size_t rightSize = rightNode->m_sizeInBytes;
337             void* rightEnd = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(rightStart) + rightSize);
338             
339             ASSERT(rightStart == end);
340             ASSERT(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(leftStart) + leftSize + sizeInBytes + rightSize) == rightEnd);
341             
342             m_freeSpaceSizeMap.remove(rightNode);
343             m_freeSpaceStartAddressMap.remove(rightStart);
344             m_freeSpaceEndAddressMap.remove(rightEnd);
345             
346             freeFreeSpaceNode(rightNode);
347             
348             leftNode->m_sizeInBytes += sizeInBytes + rightSize;
349             
350             m_freeSpaceSizeMap.insert(leftNode);
351             m_freeSpaceEndAddressMap.add(rightEnd, leftNode);
352         } else {
353             leftNode->m_sizeInBytes += sizeInBytes;
354             
355             m_freeSpaceSizeMap.insert(leftNode);
356             m_freeSpaceEndAddressMap.add(end, leftNode);
357         }
358     } else {
359         // Cannot coalesce with left; try to see if we can coalesce with right.
360         
361         if (rightNeighbor != m_freeSpaceStartAddressMap.end()) {
362             FreeSpaceNode* rightNode = rightNeighbor->value;
363             void* rightStart = rightNeighbor->key;
364             size_t rightSize = rightNode->m_sizeInBytes;
365             void* rightEnd = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(rightStart) + rightSize);
366             
367             ASSERT(rightStart == end);
368             ASSERT_UNUSED(rightEnd, reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(start) + sizeInBytes + rightSize) == rightEnd);
369             
370             m_freeSpaceSizeMap.remove(rightNode);
371             m_freeSpaceStartAddressMap.remove(rightStart);
372             
373             rightNode->m_sizeInBytes += sizeInBytes;
374             rightNode->m_start = start;
375             
376             m_freeSpaceSizeMap.insert(rightNode);
377             m_freeSpaceStartAddressMap.add(start, rightNode);
378         } else {
379             // Nothing to coalesce with, so create a new free space node and add it.
380             
381             FreeSpaceNode* node = allocFreeSpaceNode();
382             
383             node->m_sizeInBytes = sizeInBytes;
384             node->m_start = start;
385             
386             m_freeSpaceSizeMap.insert(node);
387             m_freeSpaceStartAddressMap.add(start, node);
388             m_freeSpaceEndAddressMap.add(end, node);
389         }
390     }
391     
392 #if ENABLE(META_ALLOCATOR_PROFILE)
393     dumpProfile();
394 #endif
395 }
396
397 void MetaAllocator::incrementPageOccupancy(void* address, size_t sizeInBytes)
398 {
399     uintptr_t firstPage = reinterpret_cast<uintptr_t>(address) >> m_logPageSize;
400     uintptr_t lastPage = (reinterpret_cast<uintptr_t>(address) + sizeInBytes - 1) >> m_logPageSize;
401     
402     for (uintptr_t page = firstPage; page <= lastPage; ++page) {
403         HashMap<uintptr_t, size_t>::iterator iter = m_pageOccupancyMap.find(page);
404         if (iter == m_pageOccupancyMap.end()) {
405             m_pageOccupancyMap.add(page, 1);
406             m_bytesCommitted += m_pageSize;
407             notifyNeedPage(reinterpret_cast<void*>(page << m_logPageSize));
408         } else
409             iter->value++;
410     }
411 }
412
413 void MetaAllocator::decrementPageOccupancy(void* address, size_t sizeInBytes)
414 {
415     uintptr_t firstPage = reinterpret_cast<uintptr_t>(address) >> m_logPageSize;
416     uintptr_t lastPage = (reinterpret_cast<uintptr_t>(address) + sizeInBytes - 1) >> m_logPageSize;
417     
418     for (uintptr_t page = firstPage; page <= lastPage; ++page) {
419         HashMap<uintptr_t, size_t>::iterator iter = m_pageOccupancyMap.find(page);
420         ASSERT(iter != m_pageOccupancyMap.end());
421         if (!--(iter->value)) {
422             m_pageOccupancyMap.remove(iter);
423             m_bytesCommitted -= m_pageSize;
424             notifyPageIsFree(reinterpret_cast<void*>(page << m_logPageSize));
425         }
426     }
427 }
428
429 bool MetaAllocator::isInAllocatedMemory(const LockHolder&, void* address)
430 {
431     ASSERT(m_lock.isLocked());
432     uintptr_t page = reinterpret_cast<uintptr_t>(address) >> m_logPageSize;
433     return m_pageOccupancyMap.contains(page);
434 }
435
436 size_t MetaAllocator::roundUp(size_t sizeInBytes)
437 {
438     if (std::numeric_limits<size_t>::max() - m_allocationGranule <= sizeInBytes)
439         CRASH();
440     return (sizeInBytes + m_allocationGranule - 1) & ~(m_allocationGranule - 1);
441 }
442
443 MetaAllocator::FreeSpaceNode* MetaAllocator::allocFreeSpaceNode()
444 {
445 #ifndef NDEBUG
446     m_mallocBalance++;
447 #endif
448     return new (NotNull, fastMalloc(sizeof(FreeSpaceNode))) FreeSpaceNode(0, 0);
449 }
450
451 void MetaAllocator::freeFreeSpaceNode(FreeSpaceNode* node)
452 {
453 #ifndef NDEBUG
454     m_mallocBalance--;
455 #endif
456     fastFree(node);
457 }
458
459 #if ENABLE(META_ALLOCATOR_PROFILE)
460 void MetaAllocator::dumpProfile()
461 {
462     dataLogF(
463         "%d: MetaAllocator(%p): num allocations = %u, num frees = %u, allocated = %lu, reserved = %lu, committed = %lu\n",
464         getCurrentProcessID(), this, m_numAllocations, m_numFrees, m_bytesAllocated, m_bytesReserved, m_bytesCommitted);
465 }
466 #endif
467
468 } // namespace WTF
469
470