[JSC] Less contended MetaAllocator
[WebKit-https.git] / Source / WTF / wtf / MetaAllocator.h
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
40 namespace WTF {
41
42 #define ENABLE_META_ALLOCATOR_PROFILE 0
43
44 class MetaAllocatorTracker {
45     WTF_MAKE_FAST_ALLOCATED;
46 public:
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
61 class MetaAllocator {
62     WTF_MAKE_NONCOPYABLE(MetaAllocator);
63
64 public:
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
110 protected:
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
126 private:
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