1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
/*
* Copyright (C) 2011 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of Apple Inc. ("Apple") nor the names of
* its contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef WTF_MetaAllocator_h
#define WTF_MetaAllocator_h
#include <wtf/Assertions.h>
#include <wtf/HashMap.h>
#include <wtf/Lock.h>
#include <wtf/MetaAllocatorHandle.h>
#include <wtf/Noncopyable.h>
#include <wtf/PageBlock.h>
#include <wtf/RedBlackTree.h>
#include <wtf/RefCounted.h>
#include <wtf/RefPtr.h>
namespace WTF {
#define ENABLE_META_ALLOCATOR_PROFILE 0
class MetaAllocatorTracker {
WTF_MAKE_FAST_ALLOCATED;
public:
void notify(MetaAllocatorHandle*);
void release(MetaAllocatorHandle*);
MetaAllocatorHandle* find(void* address)
{
MetaAllocatorHandle* handle = m_allocations.findGreatestLessThanOrEqual(address);
if (handle && address < handle->end())
return handle;
return 0;
}
RedBlackTree<MetaAllocatorHandle, void*> m_allocations;
};
class MetaAllocator {
WTF_MAKE_NONCOPYABLE(MetaAllocator);
public:
WTF_EXPORT_PRIVATE MetaAllocator(size_t allocationGranule, size_t pageSize = WTF::pageSize());
WTF_EXPORT_PRIVATE virtual ~MetaAllocator();
WTF_EXPORT_PRIVATE PassRefPtr<MetaAllocatorHandle> allocate(size_t sizeInBytes, void* ownerUID);
void trackAllocations(MetaAllocatorTracker* tracker)
{
m_tracker = tracker;
}
// Non-atomic methods for getting allocator statistics.
size_t bytesAllocated() { return m_bytesAllocated; }
size_t bytesReserved() { return m_bytesReserved; }
size_t bytesCommitted() { return m_bytesCommitted; }
// Atomic method for getting allocator statistics.
struct Statistics {
size_t bytesAllocated;
size_t bytesReserved;
size_t bytesCommitted;
};
WTF_EXPORT_PRIVATE Statistics currentStatistics();
// Add more free space to the allocator. Call this directly from
// the constructor if you wish to operate the allocator within a
// fixed pool.
WTF_EXPORT_PRIVATE void addFreshFreeSpace(void* start, size_t sizeInBytes);
// This is meant only for implementing tests. Never call this in release
// builds.
WTF_EXPORT_PRIVATE size_t debugFreeSpaceSize();
WTF_EXPORT_PRIVATE Lock& getLock() { return m_lock; }
WTF_EXPORT_PRIVATE bool isInAllocatedMemory(const LockHolder&, void* address);
#if ENABLE(META_ALLOCATOR_PROFILE)
void dumpProfile();
#else
void dumpProfile() { }
#endif
protected:
// Allocate new virtual space, but don't commit. This may return more
// pages than we asked, in which case numPages is changed.
virtual void* allocateNewSpace(size_t& numPages) = 0;
// Commit a page.
virtual void notifyNeedPage(void* page) = 0;
// Uncommit a page.
virtual void notifyPageIsFree(void* page) = 0;
// NOTE: none of the above methods are called during allocator
// destruction, in part because a MetaAllocator cannot die so long
// as there are Handles that refer to it.
private:
friend class MetaAllocatorHandle;
class FreeSpaceNode : public RedBlackTree<FreeSpaceNode, size_t>::Node {
public:
FreeSpaceNode(void* start, size_t sizeInBytes)
: m_start(start)
, m_sizeInBytes(sizeInBytes)
{
}
size_t key()
{
return m_sizeInBytes;
}
void* m_start;
size_t m_sizeInBytes;
};
typedef RedBlackTree<FreeSpaceNode, size_t> Tree;
// Release a MetaAllocatorHandle.
void release(MetaAllocatorHandle*);
// Remove free space from the allocator. This is effectively
// the allocate() function, except that it does not mark the
// returned space as being in-use.
void* findAndRemoveFreeSpace(size_t sizeInBytes);
// This is called when memory from an allocation is freed.
void addFreeSpaceFromReleasedHandle(void* start, size_t sizeInBytes);
// This is the low-level implementation of adding free space; it
// is called from both addFreeSpaceFromReleasedHandle and from
// addFreshFreeSpace.
void addFreeSpace(void* start, size_t sizeInBytes);
// Management of used space.
void incrementPageOccupancy(void* address, size_t sizeInBytes);
void decrementPageOccupancy(void* address, size_t sizeInBytes);
// Utilities.
size_t roundUp(size_t sizeInBytes);
FreeSpaceNode* allocFreeSpaceNode();
WTF_EXPORT_PRIVATE void freeFreeSpaceNode(FreeSpaceNode*);
size_t m_allocationGranule;
unsigned m_logAllocationGranule;
size_t m_pageSize;
unsigned m_logPageSize;
Tree m_freeSpaceSizeMap;
HashMap<void*, FreeSpaceNode*> m_freeSpaceStartAddressMap;
HashMap<void*, FreeSpaceNode*> m_freeSpaceEndAddressMap;
HashMap<uintptr_t, size_t> m_pageOccupancyMap;
size_t m_bytesAllocated;
size_t m_bytesReserved;
size_t m_bytesCommitted;
Lock m_lock;
MetaAllocatorTracker* m_tracker;
#ifndef NDEBUG
size_t m_mallocBalance;
#endif
#if ENABLE(META_ALLOCATOR_PROFILE)
unsigned m_numAllocations;
unsigned m_numFrees;
#endif
};
} // namespace WTF
#endif // WTF_MetaAllocator_h
|
