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