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