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 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 AbstractLocker&, 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 FreeSpacePtr 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() = default;
132
133 FreeSpaceNode(void* start, size_t sizeInBytes)
134 : m_start(start)
135 , m_end(reinterpret_cast<uint8_t*>(start) + sizeInBytes)
136 { }
137
138 size_t sizeInBytes()
139 {
140 return m_end.untaggedPtr<size_t>() - m_start.untaggedPtr<size_t>();
141 }
142
143 size_t key()
144 {
145 return sizeInBytes();
146 }
147
148 FreeSpacePtr m_start;
149 FreeSpacePtr m_end;
150 };
151 typedef RedBlackTree<FreeSpaceNode, size_t> Tree;
152
153 // Release a MetaAllocatorHandle.
154 void release(MetaAllocatorHandle*);
155
156 // Remove free space from the allocator. This is effectively
157 // the allocate() function, except that it does not mark the
158 // returned space as being in-use.
159 FreeSpacePtr findAndRemoveFreeSpace(size_t sizeInBytes);
160
161 // This is called when memory from an allocation is freed.
162 void addFreeSpaceFromReleasedHandle(FreeSpacePtr start, size_t sizeInBytes);
163
164 // This is the low-level implementation of adding free space; it
165 // is called from both addFreeSpaceFromReleasedHandle and from
166 // addFreshFreeSpace.
167 void addFreeSpace(FreeSpacePtr start, size_t sizeInBytes);
168
169 // Management of used space.
170
171 void incrementPageOccupancy(void* address, size_t sizeInBytes);
172 void decrementPageOccupancy(void* address, size_t sizeInBytes);
173
174 // Utilities.
175
176 size_t roundUp(size_t sizeInBytes);
177
178 FreeSpaceNode* allocFreeSpaceNode();
179 WTF_EXPORT_PRIVATE void freeFreeSpaceNode(FreeSpaceNode*);
180
181 size_t m_allocationGranule;
182 size_t m_pageSize;
183 unsigned m_logAllocationGranule;
184 unsigned m_logPageSize;
185
186 Tree m_freeSpaceSizeMap;
187 HashMap<FreeSpacePtr, FreeSpaceNode*> m_freeSpaceStartAddressMap;
188 HashMap<FreeSpacePtr, FreeSpaceNode*> m_freeSpaceEndAddressMap;
189 HashMap<uintptr_t, size_t> m_pageOccupancyMap;
190
191 size_t m_bytesAllocated;
192 size_t m_bytesReserved;
193 size_t m_bytesCommitted;
194
195 Lock m_lock;
196
197 MetaAllocatorTracker* m_tracker;
198
199#ifndef NDEBUG
200 size_t m_mallocBalance;
201#endif
202
203#if ENABLE(META_ALLOCATOR_PROFILE)
204 unsigned m_numAllocations;
205 unsigned m_numFrees;
206#endif
207};
208
209} // namespace WTF
210