bmalloc: Merge the large and xlarge allocators
[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 "PerProcess.h"
32 #include "Sizes.h"
33 #include <algorithm>
34 #include <cstdlib>
35
36 using namespace std;
37
38 namespace bmalloc {
39
40 Allocator::Allocator(Heap* heap, Deallocator& deallocator)
41     : m_isBmallocEnabled(heap->environment().isBmallocEnabled())
42     , m_deallocator(deallocator)
43 {
44     for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass)
45         m_bumpAllocators[sizeClass].init(objectSize(sizeClass));
46 }
47
48 Allocator::~Allocator()
49 {
50     scavenge();
51 }
52
53 void* Allocator::tryAllocate(size_t size)
54 {
55     if (!m_isBmallocEnabled)
56         return malloc(size);
57
58     if (size <= smallMax)
59         return allocate(size);
60
61     if (size <= largeMax) {
62         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
63         return PerProcess<Heap>::getFastCase()->tryAllocateLarge(lock, alignment, size);
64     }
65
66     return nullptr;
67 }
68
69 void* Allocator::allocate(size_t alignment, size_t size)
70 {
71     BASSERT(isPowerOfTwo(alignment));
72
73     if (!m_isBmallocEnabled) {
74         void* result = nullptr;
75         if (posix_memalign(&result, alignment, size))
76             return nullptr;
77         return result;
78     }
79
80     if (!size)
81         size = alignment;
82
83     if (size <= smallMax && alignment <= smallMax)
84         return allocate(roundUpToMultipleOf(alignment, size));
85
86     if (size <= largeMax && alignment <= largeMax / 2) {
87         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
88         return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size);
89     }
90
91     BCRASH();
92     return nullptr;
93 }
94
95 void* Allocator::reallocate(void* object, size_t newSize)
96 {
97     if (!m_isBmallocEnabled)
98         return realloc(object, newSize);
99
100     size_t oldSize = 0;
101     switch (objectType(object)) {
102     case ObjectType::Small: {
103         BASSERT(objectType(nullptr) == ObjectType::Small);
104         if (!object)
105             break;
106
107         size_t sizeClass = Object(object).page()->sizeClass();
108         oldSize = objectSize(sizeClass);
109         break;
110     }
111     case ObjectType::Large: {
112         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
113         oldSize = PerProcess<Heap>::getFastCase()->largeSize(lock, object);
114
115         if (newSize < oldSize && newSize > smallMax) {
116             PerProcess<Heap>::getFastCase()->shrinkLarge(lock, Range(object, oldSize), newSize);
117             return object;
118         }
119         break;
120     }
121     }
122
123     void* result = allocate(newSize);
124     size_t copySize = std::min(oldSize, newSize);
125     memcpy(result, object, copySize);
126     m_deallocator.deallocate(object);
127     return result;
128 }
129
130 void Allocator::scavenge()
131 {
132     for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) {
133         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
134         BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
135
136         while (allocator.canAllocate())
137             m_deallocator.deallocate(allocator.allocate());
138
139         while (bumpRangeCache.size()) {
140             allocator.refill(bumpRangeCache.pop());
141             while (allocator.canAllocate())
142                 m_deallocator.deallocate(allocator.allocate());
143         }
144
145         allocator.clear();
146     }
147 }
148
149 NO_INLINE void Allocator::refillAllocatorSlowCase(BumpAllocator& allocator, size_t sizeClass)
150 {
151     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
152
153     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
154     m_deallocator.processObjectLog(lock);
155     PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
156 }
157
158 INLINE void Allocator::refillAllocator(BumpAllocator& allocator, size_t sizeClass)
159 {
160     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
161     if (!bumpRangeCache.size())
162         return refillAllocatorSlowCase(allocator, sizeClass);
163     return allocator.refill(bumpRangeCache.pop());
164 }
165
166 NO_INLINE void* Allocator::allocateLarge(size_t size)
167 {
168     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
169     return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size);
170 }
171
172 NO_INLINE void* Allocator::allocateLogSizeClass(size_t size)
173 {
174     size_t sizeClass = bmalloc::sizeClass(size);
175     BumpAllocator& allocator = m_bumpAllocators[sizeClass];
176     if (!allocator.canAllocate())
177         refillAllocator(allocator, sizeClass);
178     return allocator.allocate();
179 }
180
181 void* Allocator::allocateSlowCase(size_t size)
182 {
183     if (!m_isBmallocEnabled)
184         return malloc(size);
185
186     if (size <= maskSizeClassMax) {
187         size_t sizeClass = bmalloc::maskSizeClass(size);
188         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
189         refillAllocator(allocator, sizeClass);
190         return allocator.allocate();
191     }
192
193     if (size <= smallMax)
194         return allocateLogSizeClass(size);
195
196     if (size <= largeMax)
197         return allocateLarge(size);
198
199     BCRASH();
200     return nullptr;
201 }
202
203 } // namespace bmalloc