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
42namespace WTF {
43
44#define ENABLE_META_ALLOCATOR_PROFILE 0
45
46class MetaAllocatorTracker {
47 WTF_MAKE_FAST_ALLOCATED;
48public:
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
63class MetaAllocator {
64 WTF_MAKE_NONCOPYABLE(MetaAllocator);
65
66public:
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 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
109protected:
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
125private:
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
207