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