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