cef4e992228d69f991405b24ad937265801fbe9e
[WebKit-https.git] / Source / bmalloc / bmalloc / Allocator.cpp
1 /*
2  * Copyright (C) 2014, 2015 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  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "Allocator.h"
27 #include "BAssert.h"
28 #include "Deallocator.h"
29 #include "Heap.h"
30 #include "LargeChunk.h"
31 #include "LargeObject.h"
32 #include "PerProcess.h"
33 #include "Sizes.h"
34 #include <algorithm>
35 #include <cstdlib>
36
37 using namespace std;
38
39 namespace bmalloc {
40
41 Allocator::Allocator(Heap* heap, Deallocator& deallocator)
42     : m_isBmallocEnabled(heap->environment().isBmallocEnabled())
43     , m_deallocator(deallocator)
44 {
45     for (unsigned short size = alignment; size <= mediumMax; size += alignment)
46         m_bumpAllocators[sizeClass(size)].init(size);
47 }
48
49 Allocator::~Allocator()
50 {
51     scavenge();
52 }
53
54 void* Allocator::tryAllocate(size_t size)
55 {
56     if (!m_isBmallocEnabled)
57         return malloc(size);
58
59     if (size <= largeMax)
60         return allocate(size);
61
62     if (size <= xLargeMax) {
63         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
64         return PerProcess<Heap>::getFastCase()->tryAllocateXLarge(lock, superChunkSize, roundUpToMultipleOf<xLargeAlignment>(size));
65     }
66
67     return nullptr;
68 }
69
70 void* Allocator::allocate(size_t alignment, size_t size)
71 {
72     BASSERT(isPowerOfTwo(alignment));
73
74     if (!m_isBmallocEnabled) {
75         void* result = nullptr;
76         if (posix_memalign(&result, alignment, size))
77             return nullptr;
78         return result;
79     }
80     
81     if (size <= smallMax && alignment <= smallLineSize) {
82         size_t alignmentMask = alignment - 1;
83         while (void* p = allocate(size)) {
84             if (!test(p, alignmentMask))
85                 return p;
86             m_deallocator.deallocate(p);
87         }
88     }
89
90     if (size <= mediumMax && alignment <= mediumLineSize) {
91         size = std::max(size, smallMax + Sizes::alignment);
92         size_t alignmentMask = alignment - 1;
93         while (void* p = allocate(size)) {
94             if (!test(p, alignmentMask))
95                 return p;
96             m_deallocator.deallocate(p);
97         }
98     }
99
100     if (size <= largeMax && alignment <= largeMax) {
101         size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
102         alignment = roundUpToMultipleOf<largeAlignment>(alignment);
103         size_t unalignedSize = largeMin + alignment + size;
104         if (unalignedSize <= largeMax && alignment <= largeChunkSize / 2) {
105             std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
106             return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size, unalignedSize);
107         }
108     }
109
110     if (size <= xLargeMax && alignment <= xLargeMax) {
111         size = roundUpToMultipleOf<xLargeAlignment>(size);
112         alignment = std::max(superChunkSize, alignment);
113         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
114         return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, alignment, size);
115     }
116
117     BCRASH();
118     return nullptr;
119 }
120
121 void* Allocator::reallocate(void* object, size_t newSize)
122 {
123     if (!m_isBmallocEnabled)
124         return realloc(object, newSize);
125
126     size_t oldSize = 0;
127     switch (objectType(object)) {
128     case Small: {
129         SmallPage* page = SmallPage::get(SmallLine::get(object));
130         oldSize = objectSize(page->sizeClass());
131         break;
132     }
133     case Medium: {
134         MediumPage* page = MediumPage::get(MediumLine::get(object));
135         oldSize = objectSize(page->sizeClass());
136         break;
137     }
138     case Large: {
139         std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
140         LargeObject largeObject(object);
141         oldSize = largeObject.size();
142
143         if (newSize < oldSize && newSize > mediumMax) {
144             newSize = roundUpToMultipleOf<largeAlignment>(newSize);
145             if (oldSize - newSize >= largeMin) {
146                 std::pair<LargeObject, LargeObject> split = largeObject.split(newSize);
147                 
148                 lock.unlock();
149                 m_deallocator.deallocate(split.second.begin());
150                 lock.lock();
151             }
152             return object;
153         }
154         break;
155     }
156     case XLarge: {
157         BASSERT(objectType(nullptr) == XLarge);
158         if (!object)
159             break;
160
161         std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
162         Range& range = PerProcess<Heap>::getFastCase()->findXLarge(lock, object);
163         oldSize = range.size();
164
165         newSize = roundUpToMultipleOf<xLargeAlignment>(newSize);
166
167         if (newSize == oldSize)
168             return object;
169
170         if (newSize < oldSize && newSize > largeMax) {
171             newSize = roundUpToMultipleOf<xLargeAlignment>(newSize);
172             if (oldSize - newSize >= xLargeAlignment) {
173                 lock.unlock();
174                 vmDeallocate(static_cast<char*>(object) + newSize, oldSize - newSize);
175                 lock.lock();
176
177                 range = Range(object, newSize);
178             }
179             return object;
180         }
181
182         if (newSize > oldSize) {
183             lock.unlock();
184             bool wasExtended = tryVMExtend(object, oldSize, newSize);
185             lock.lock();
186
187             if (wasExtended) {
188                 range = Range(object, newSize);
189                 return object;
190             }
191         }
192         break;
193     }
194     }
195
196     void* result = allocate(newSize);
197     size_t copySize = std::min(oldSize, newSize);
198     memcpy(result, object, copySize);
199     m_deallocator.deallocate(object);
200     return result;
201 }
202
203 void Allocator::scavenge()
204 {
205     for (unsigned short i = alignment; i <= mediumMax; i += alignment) {
206         BumpAllocator& allocator = m_bumpAllocators[sizeClass(i)];
207         BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass(i)];
208
209         while (allocator.canAllocate())
210             m_deallocator.deallocate(allocator.allocate());
211
212         while (bumpRangeCache.size()) {
213             allocator.refill(bumpRangeCache.pop());
214             while (allocator.canAllocate())
215                 m_deallocator.deallocate(allocator.allocate());
216         }
217
218         allocator.clear();
219     }
220 }
221
222 NO_INLINE void Allocator::refillAllocatorSlowCase(BumpAllocator& allocator, size_t sizeClass)
223 {
224     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
225
226     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
227     if (sizeClass <= bmalloc::sizeClass(smallMax))
228         PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
229     else
230         PerProcess<Heap>::getFastCase()->allocateMediumBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
231 }
232
233 INLINE void Allocator::refillAllocator(BumpAllocator& allocator, size_t sizeClass)
234 {
235     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
236     if (!bumpRangeCache.size())
237         return refillAllocatorSlowCase(allocator, sizeClass);
238     return allocator.refill(bumpRangeCache.pop());
239 }
240
241 NO_INLINE void* Allocator::allocateLarge(size_t size)
242 {
243     size = roundUpToMultipleOf<largeAlignment>(size);
244     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
245     return PerProcess<Heap>::getFastCase()->allocateLarge(lock, size);
246 }
247
248 NO_INLINE void* Allocator::allocateXLarge(size_t size)
249 {
250     size = roundUpToMultipleOf<xLargeAlignment>(size);
251     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
252     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
253 }
254
255 void* Allocator::allocateSlowCase(size_t size)
256 {
257     if (!m_isBmallocEnabled)
258         return malloc(size);
259
260     if (size <= mediumMax) {
261         size_t sizeClass = bmalloc::sizeClass(size);
262         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
263         refillAllocator(allocator, sizeClass);
264         return allocator.allocate();
265     }
266
267     if (size <= largeMax)
268         return allocateLarge(size);
269
270     if (size <= xLargeMax)
271         return allocateXLarge(size);
272
273     BCRASH();
274     return nullptr;
275 }
276
277 } // namespace bmalloc