deb2236533b010d2c3122d6567baa0c58f9c6fa6
[WebKit.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 "Chunk.h"
29 #include "Deallocator.h"
30 #include "Heap.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 (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass)
46         m_bumpAllocators[sizeClass].init(objectSize(sizeClass));
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, alignment, 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)
82         size = alignment;
83
84     if (size <= smallMax && alignment <= smallMax)
85         return allocate(roundUpToMultipleOf(alignment, size));
86
87     if (size <= largeMax && alignment <= largeMax) {
88         size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
89         alignment = roundUpToMultipleOf<largeAlignment>(alignment);
90         size_t unalignedSize = largeMin + alignment - largeAlignment + size;
91         if (unalignedSize <= largeMax && alignment <= chunkSize / 2) {
92             std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
93             m_deallocator.processObjectLog(lock);
94             return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size, unalignedSize);
95         }
96     }
97
98     if (size <= xLargeMax && alignment <= xLargeMax) {
99         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
100         return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, alignment, size);
101     }
102
103     BCRASH();
104     return nullptr;
105 }
106
107 void* Allocator::reallocate(void* object, size_t newSize)
108 {
109     if (!m_isBmallocEnabled)
110         return realloc(object, newSize);
111
112     size_t oldSize = 0;
113     switch (objectType(object)) {
114     case ObjectType::Small: {
115         size_t sizeClass = Object(object).page()->sizeClass();
116         oldSize = objectSize(sizeClass);
117         break;
118     }
119     case ObjectType::Large: {
120         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
121
122         LargeObject largeObject(object);
123         oldSize = largeObject.size();
124
125         if (newSize < oldSize && newSize > smallMax) {
126             if (oldSize - newSize >= largeMin) {
127                 newSize = roundUpToMultipleOf<largeAlignment>(newSize);
128                 PerProcess<Heap>::getFastCase()->shrinkLarge(lock, largeObject, newSize);
129                 return object;
130             }
131         }
132         break;
133     }
134     case ObjectType::XLarge: {
135         BASSERT(objectType(nullptr) == ObjectType::XLarge);
136         if (!object)
137             break;
138
139         std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
140         oldSize = PerProcess<Heap>::getFastCase()->xLargeSize(lock, object);
141
142         if (newSize < oldSize && newSize > largeMax) {
143             PerProcess<Heap>::getFastCase()->shrinkXLarge(lock, Range(object, oldSize), newSize);
144             return object;
145         }
146         break;
147     }
148     }
149
150     void* result = allocate(newSize);
151     size_t copySize = std::min(oldSize, newSize);
152     memcpy(result, object, copySize);
153     m_deallocator.deallocate(object);
154     return result;
155 }
156
157 void Allocator::scavenge()
158 {
159     for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) {
160         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
161         BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
162
163         while (allocator.canAllocate())
164             m_deallocator.deallocate(allocator.allocate());
165
166         while (bumpRangeCache.size()) {
167             allocator.refill(bumpRangeCache.pop());
168             while (allocator.canAllocate())
169                 m_deallocator.deallocate(allocator.allocate());
170         }
171
172         allocator.clear();
173     }
174 }
175
176 NO_INLINE void Allocator::refillAllocatorSlowCase(BumpAllocator& allocator, size_t sizeClass)
177 {
178     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
179
180     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
181     m_deallocator.processObjectLog(lock);
182     PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
183 }
184
185 INLINE void Allocator::refillAllocator(BumpAllocator& allocator, size_t sizeClass)
186 {
187     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
188     if (!bumpRangeCache.size())
189         return refillAllocatorSlowCase(allocator, sizeClass);
190     return allocator.refill(bumpRangeCache.pop());
191 }
192
193 NO_INLINE void* Allocator::allocateLarge(size_t size)
194 {
195     size = roundUpToMultipleOf<largeAlignment>(size);
196
197     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
198     m_deallocator.processObjectLog(lock);
199     return PerProcess<Heap>::getFastCase()->allocateLarge(lock, size);
200 }
201
202 NO_INLINE void* Allocator::allocateXLarge(size_t size)
203 {
204     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
205     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
206 }
207
208 NO_INLINE void* Allocator::allocateLogSizeClass(size_t size)
209 {
210     size_t sizeClass = bmalloc::sizeClass(size);
211     BumpAllocator& allocator = m_bumpAllocators[sizeClass];
212     if (!allocator.canAllocate())
213         refillAllocator(allocator, sizeClass);
214     return allocator.allocate();
215 }
216
217 void* Allocator::allocateSlowCase(size_t size)
218 {
219     if (!m_isBmallocEnabled)
220         return malloc(size);
221
222     if (size <= maskSizeClassMax) {
223         size_t sizeClass = bmalloc::maskSizeClass(size);
224         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
225         refillAllocator(allocator, sizeClass);
226         return allocator.allocate();
227     }
228
229     if (size <= smallMax)
230         return allocateLogSizeClass(size);
231
232     if (size <= largeMax)
233         return allocateLarge(size);
234
235     if (size <= xLargeMax)
236         return allocateXLarge(size);
237
238     BCRASH();
239     return nullptr;
240 }
241
242 } // namespace bmalloc