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