code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/wtf/MetaAllocator.h

   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 #ifndef WTF_MetaAllocator_h
  30 #define WTF_MetaAllocator_h
  31
  32 #include "Assertions.h"
  33 #include "HashMap.h"
  34 #include "MetaAllocatorHandle.h"
  35 #include "Noncopyable.h"
  36 #include "PageBlock.h"
  37 #include "RedBlackTree.h"
  38 #include "RefCounted.h"
  39 #include "RefPtr.h"
  40 #include "TCSpinLock.h"
  41
  42 namespace WTF {
  43
  44 #define ENABLE_META_ALLOCATOR_PROFILE 0
  45
  46 class MetaAllocator {
  47     WTF_MAKE_NONCOPYABLE(MetaAllocator);
  48 public:
  49
  50     MetaAllocator(size_t allocationGranule);
  51
  52     virtual ~MetaAllocator();
  53
  54     PassRefPtr<MetaAllocatorHandle> allocate(size_t sizeInBytes);
  55
  56     // Non-atomic methods for getting allocator statistics.
  57     size_t bytesAllocated() { return m_bytesAllocated; }
  58     size_t bytesReserved() { return m_bytesReserved; }
  59     size_t bytesCommitted() { return m_bytesCommitted; }
  60
  61     // Atomic method for getting allocator statistics.
  62     struct Statistics {
  63         size_t bytesAllocated;
  64         size_t bytesReserved;
  65         size_t bytesCommitted;
  66     };
  67     Statistics currentStatistics();
  68
  69     // Add more free space to the allocator. Call this directly from
  70     // the constructor if you wish to operate the allocator within a
  71     // fixed pool.
  72     void addFreshFreeSpace(void* start, size_t sizeInBytes);
  73
  74     // This is meant only for implementing tests. Never call this in release
  75     // builds.
  76     size_t debugFreeSpaceSize();
  77
  78 #if ENABLE(META_ALLOCATOR_PROFILE)
  79     void dumpProfile();
  80 #else
  81     void dumpProfile() { }
  82 #endif
  83
  84 protected:
  85
  86     // Allocate new virtual space, but don't commit. This may return more
  87     // pages than we asked, in which case numPages is changed.
  88     virtual void* allocateNewSpace(size_t& numPages) = 0;
  89
  90     // Commit a page.
  91     virtual void notifyNeedPage(void* page) = 0;
  92
  93     // Uncommit a page.
  94     virtual void notifyPageIsFree(void* page) = 0;
  95
  96     // NOTE: none of the above methods are called during allocator
  97     // destruction, in part because a MetaAllocator cannot die so long
  98     // as there are Handles that refer to it.
  99
 100 private:
 101
 102     friend class MetaAllocatorHandle;
 103
 104     typedef RedBlackTree<size_t, void*> Tree;
 105     typedef Tree::Node FreeSpaceNode;
 106
 107     // Remove free space from the allocator. This is effectively
 108     // the allocate() function, except that it does not mark the
 109     // returned space as being in-use.
 110     void* findAndRemoveFreeSpace(size_t sizeInBytes);
 111
 112     // This is called when memory from an allocation is freed.
 113     void addFreeSpaceFromReleasedHandle(void* start, size_t sizeInBytes);
 114
 115     // This is the low-level implementation of adding free space; it
 116     // is called from both addFreeSpaceFromReleasedHandle and from
 117     // addFreshFreeSpace.
 118     void addFreeSpace(void* start, size_t sizeInBytes);
 119
 120     // Management of used space.
 121
 122     void incrementPageOccupancy(void* address, size_t sizeInBytes);
 123     void decrementPageOccupancy(void* address, size_t sizeInBytes);
 124
 125     // Utilities.
 126
 127     size_t roundUp(size_t sizeInBytes);
 128
 129     FreeSpaceNode* allocFreeSpaceNode();
 130     void freeFreeSpaceNode(FreeSpaceNode*);
 131
 132     size_t m_allocationGranule;
 133     unsigned m_logAllocationGranule;
 134     size_t m_pageSize;
 135     unsigned m_logPageSize;
 136
 137     Tree m_freeSpaceSizeMap;
 138     HashMap<void*, FreeSpaceNode*> m_freeSpaceStartAddressMap;
 139     HashMap<void*, FreeSpaceNode*> m_freeSpaceEndAddressMap;
 140     HashMap<uintptr_t, size_t> m_pageOccupancyMap;
 141
 142     size_t m_bytesAllocated;
 143     size_t m_bytesReserved;
 144     size_t m_bytesCommitted;
 145
 146     SpinLock m_lock;
 147
 148 #ifndef NDEBUG
 149     size_t m_mallocBalance;
 150 #endif
 151
 152 #if ENABLE(META_ALLOCATOR_PROFILE)
 153     unsigned m_numAllocations;
 154     unsigned m_numFrees;
 155 #endif
 156 };
 157
 158 inline MetaAllocator::~MetaAllocator()
 159 {
 160     for (FreeSpaceNode* node = m_freeSpaceSizeMap.first(); node;) {
 161         FreeSpaceNode* next = node->successor();
 162         m_freeSpaceSizeMap.remove(node);
 163         freeFreeSpaceNode(node);
 164         node = next;
 165     }
 166 #ifndef NDEBUG
 167     ASSERT(!m_mallocBalance);
 168 #endif
 169 }
 170
 171 } // namespace WTF
 172
 173 #endif // WTF_MetaAllocator_h
 174