bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
[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::allocate(size_t alignment, size_t size)
55 {
56     BASSERT(isPowerOfTwo(alignment));
57
58     if (!m_isBmallocEnabled) {
59         void* result = nullptr;
60         if (posix_memalign(&result, alignment, size))
61             return nullptr;
62         return result;
63     }
64     
65     if (size <= smallMax && alignment <= smallLineSize) {
66         size_t alignmentMask = alignment - 1;
67         while (void* p = allocate(size)) {
68             if (!test(p, alignmentMask))
69                 return p;
70             m_deallocator.deallocate(p);
71         }
72     }
73
74     if (size <= mediumMax && alignment <= mediumLineSize) {
75         size = std::max(size, smallMax + Sizes::alignment);
76         size_t alignmentMask = alignment - 1;
77         while (void* p = allocate(size)) {
78             if (!test(p, alignmentMask))
79                 return p;
80             m_deallocator.deallocate(p);
81         }
82     }
83
84     size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
85     alignment = roundUpToMultipleOf<largeAlignment>(alignment);
86     size_t unalignedSize = largeMin + alignment + size;
87     if (unalignedSize <= largeMax && alignment <= largeChunkSize / 2) {
88         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
89         return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size, unalignedSize);
90     }
91
92     size = roundUpToMultipleOf<xLargeAlignment>(size);
93     alignment = std::max(superChunkSize, alignment);
94     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
95     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, alignment, size);
96 }
97
98 void* Allocator::reallocate(void* object, size_t newSize)
99 {
100     if (!m_isBmallocEnabled)
101         return realloc(object, newSize);
102
103     void* result = allocate(newSize);
104     if (!object)
105         return result;
106
107     size_t oldSize = 0;
108     switch (objectType(object)) {
109     case Small: {
110         SmallPage* page = SmallPage::get(SmallLine::get(object));
111         oldSize = objectSize(page->sizeClass());
112         break;
113     }
114     case Medium: {
115         MediumPage* page = MediumPage::get(MediumLine::get(object));
116         oldSize = objectSize(page->sizeClass());
117         break;
118     }
119     case Large: {
120         LargeObject largeObject(object);
121         oldSize = largeObject.size();
122         break;
123     }
124     case XLarge: {
125         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
126         Range range = PerProcess<Heap>::getFastCase()->findXLarge(lock, object);
127         RELEASE_BASSERT(range);
128         oldSize = range.size();
129         break;
130     }
131     }
132
133     size_t copySize = std::min(oldSize, newSize);
134     memcpy(result, object, copySize);
135     m_deallocator.deallocate(object);
136     return result;
137 }
138
139 void Allocator::scavenge()
140 {
141     for (unsigned short i = alignment; i <= mediumMax; i += alignment) {
142         BumpAllocator& allocator = m_bumpAllocators[sizeClass(i)];
143         BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass(i)];
144
145         while (allocator.canAllocate())
146             m_deallocator.deallocate(allocator.allocate());
147
148         while (bumpRangeCache.size()) {
149             allocator.refill(bumpRangeCache.pop());
150             while (allocator.canAllocate())
151                 m_deallocator.deallocate(allocator.allocate());
152         }
153
154         allocator.clear();
155     }
156 }
157
158 NO_INLINE BumpRange Allocator::allocateBumpRangeSlowCase(size_t sizeClass)
159 {
160     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
161
162     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
163     if (sizeClass <= bmalloc::sizeClass(smallMax))
164         PerProcess<Heap>::getFastCase()->refillSmallBumpRangeCache(lock, sizeClass, bumpRangeCache);
165     else
166         PerProcess<Heap>::getFastCase()->refillMediumBumpRangeCache(lock, sizeClass, bumpRangeCache);
167
168     return bumpRangeCache.pop();
169 }
170
171 INLINE BumpRange Allocator::allocateBumpRange(size_t sizeClass)
172 {
173     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
174     if (!bumpRangeCache.size())
175         return allocateBumpRangeSlowCase(sizeClass);
176     return bumpRangeCache.pop();
177 }
178
179 NO_INLINE void* Allocator::allocateLarge(size_t size)
180 {
181     size = roundUpToMultipleOf<largeAlignment>(size);
182     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
183     return PerProcess<Heap>::getFastCase()->allocateLarge(lock, size);
184 }
185
186 NO_INLINE void* Allocator::allocateXLarge(size_t size)
187 {
188     size = roundUpToMultipleOf<xLargeAlignment>(size);
189     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
190     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
191 }
192
193 void* Allocator::allocateSlowCase(size_t size)
194 {
195     if (!m_isBmallocEnabled)
196         return malloc(size);
197
198     if (size <= mediumMax) {
199         size_t sizeClass = bmalloc::sizeClass(size);
200         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
201         allocator.refill(allocateBumpRange(sizeClass));
202         return allocator.allocate();
203     }
204
205     if (size <= largeMax)
206         return allocateLarge(size);
207
208     return allocateXLarge(size);
209 }
210
211 } // namespace bmalloc