[bmalloc] IsoHeap should have lower tier using shared IsoPage
[WebKit-https.git] / Source / bmalloc / bmalloc / IsoHeapImplInlines.h
1 /*
2  * Copyright (C) 2017-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  * 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 #pragma once
27
28 #include "IsoHeapImpl.h"
29 #include "IsoTLSDeallocatorEntry.h"
30 #include "IsoSharedHeapInlines.h"
31 #include "IsoSharedPageInlines.h"
32
33 namespace bmalloc {
34
35 template<typename Config>
36 IsoHeapImpl<Config>::IsoHeapImpl()
37     : lock(PerProcess<IsoTLSDeallocatorEntry<Config>>::get()->lock)
38     , m_inlineDirectory(*this)
39     , m_allocator(*this)
40 {
41     addToAllIsoHeaps();
42 }
43
44 template<typename Config>
45 EligibilityResult<Config> IsoHeapImpl<Config>::takeFirstEligible()
46 {
47     if (m_isInlineDirectoryEligible) {
48         EligibilityResult<Config> result = m_inlineDirectory.takeFirstEligible();
49         if (result.kind == EligibilityKind::Full)
50             m_isInlineDirectoryEligible = false;
51         else
52             return result;
53     }
54     
55     if (!m_firstEligibleDirectory) {
56         // If nothing is eligible, it can only be because we have no directories. It wouldn't be the end
57         // of the world if we broke this invariant. It would only mean that didBecomeEligible() would need
58         // a null check.
59         RELEASE_BASSERT(!m_headDirectory);
60         RELEASE_BASSERT(!m_tailDirectory);
61     }
62     
63     for (; m_firstEligibleDirectory; m_firstEligibleDirectory = m_firstEligibleDirectory->next) {
64         EligibilityResult<Config> result = m_firstEligibleDirectory->payload.takeFirstEligible();
65         if (result.kind != EligibilityKind::Full) {
66             m_directoryHighWatermark = std::max(m_directoryHighWatermark, m_firstEligibleDirectory->index());
67             return result;
68         }
69     }
70     
71     auto* newDirectory = new IsoDirectoryPage<Config>(*this, m_nextDirectoryPageIndex++);
72     if (m_headDirectory) {
73         m_tailDirectory->next = newDirectory;
74         m_tailDirectory = newDirectory;
75     } else {
76         RELEASE_BASSERT(!m_tailDirectory);
77         m_headDirectory = newDirectory;
78         m_tailDirectory = newDirectory;
79     }
80     m_directoryHighWatermark = newDirectory->index();
81     m_firstEligibleDirectory = newDirectory;
82     EligibilityResult<Config> result = newDirectory->payload.takeFirstEligible();
83     RELEASE_BASSERT(result.kind != EligibilityKind::Full);
84     return result;
85 }
86
87 template<typename Config>
88 void IsoHeapImpl<Config>::didBecomeEligible(IsoDirectory<Config, numPagesInInlineDirectory>* directory)
89 {
90     RELEASE_BASSERT(directory == &m_inlineDirectory);
91     m_isInlineDirectoryEligible = true;
92 }
93
94 template<typename Config>
95 void IsoHeapImpl<Config>::didBecomeEligible(IsoDirectory<Config, IsoDirectoryPage<Config>::numPages>* directory)
96 {
97     RELEASE_BASSERT(m_firstEligibleDirectory);
98     auto* directoryPage = IsoDirectoryPage<Config>::pageFor(directory);
99     if (directoryPage->index() < m_firstEligibleDirectory->index())
100         m_firstEligibleDirectory = directoryPage;
101 }
102
103 template<typename Config>
104 void IsoHeapImpl<Config>::scavenge(Vector<DeferredDecommit>& decommits)
105 {
106     std::lock_guard<Mutex> locker(this->lock);
107     forEachDirectory(
108         [&] (auto& directory) {
109             directory.scavenge(decommits);
110         });
111     m_directoryHighWatermark = 0;
112     m_numberOfAllocationsFromSharedInOneCycle = 0;
113     m_allocationMode = AllocationMode::Init;
114 }
115
116 template<typename Config>
117 size_t IsoHeapImpl<Config>::freeableMemory()
118 {
119     return m_freeableMemory;
120 }
121
122 template<typename Config>
123 unsigned IsoHeapImpl<Config>::allocatorOffset()
124 {
125     return m_allocator.offset();
126 }
127
128 template<typename Config>
129 unsigned IsoHeapImpl<Config>::deallocatorOffset()
130 {
131     return PerProcess<IsoTLSDeallocatorEntry<Config>>::get()->offset();
132 }
133
134 template<typename Config>
135 unsigned IsoHeapImpl<Config>::numLiveObjects()
136 {
137     unsigned result = 0;
138     forEachLiveObject(
139         [&] (void*) {
140             result++;
141         });
142     return result;
143 }
144
145 template<typename Config>
146 unsigned IsoHeapImpl<Config>::numCommittedPages()
147 {
148     unsigned result = 0;
149     forEachCommittedPage(
150         [&] (IsoPage<Config>&) {
151             result++;
152         });
153     return result;
154 }
155
156 template<typename Config>
157 template<typename Func>
158 void IsoHeapImpl<Config>::forEachDirectory(const Func& func)
159 {
160     func(m_inlineDirectory);
161     for (IsoDirectoryPage<Config>* page = m_headDirectory; page; page = page->next)
162         func(page->payload);
163 }
164
165 template<typename Config>
166 template<typename Func>
167 void IsoHeapImpl<Config>::forEachCommittedPage(const Func& func)
168 {
169     forEachDirectory(
170         [&] (auto& directory) {
171             directory.forEachCommittedPage(func);
172         });
173 }
174
175 template<typename Config>
176 template<typename Func>
177 void IsoHeapImpl<Config>::forEachLiveObject(const Func& func)
178 {
179     forEachCommittedPage(
180         [&] (IsoPage<Config>& page) {
181             page.forEachLiveObject(func);
182         });
183     for (unsigned index = 0; index < maxAllocationFromShared; ++index) {
184         void* pointer = m_sharedCells[index];
185         if (pointer && !(m_usableBits & (1U << index)))
186             func(pointer);
187     }
188 }
189
190 template<typename Config>
191 size_t IsoHeapImpl<Config>::footprint()
192 {
193 #if ENABLE_PHYSICAL_PAGE_MAP
194     RELEASE_BASSERT(m_footprint == m_physicalPageMap.footprint());
195 #endif
196     return m_footprint;
197 }
198
199 template<typename Config>
200 void IsoHeapImpl<Config>::didCommit(void* ptr, size_t bytes)
201 {
202     BUNUSED_PARAM(ptr);
203     m_footprint += bytes;
204 #if ENABLE_PHYSICAL_PAGE_MAP
205     m_physicalPageMap.commit(ptr, bytes);
206 #endif
207 }
208
209 template<typename Config>
210 void IsoHeapImpl<Config>::didDecommit(void* ptr, size_t bytes)
211 {
212     BUNUSED_PARAM(ptr);
213     m_footprint -= bytes;
214 #if ENABLE_PHYSICAL_PAGE_MAP
215     m_physicalPageMap.decommit(ptr, bytes);
216 #endif
217 }
218
219 template<typename Config>
220 void IsoHeapImpl<Config>::isNowFreeable(void* ptr, size_t bytes)
221 {
222     BUNUSED_PARAM(ptr);
223     m_freeableMemory += bytes;
224 }
225
226 template<typename Config>
227 void IsoHeapImpl<Config>::isNoLongerFreeable(void* ptr, size_t bytes)
228 {
229     BUNUSED_PARAM(ptr);
230     m_freeableMemory -= bytes;
231 }
232
233 template<typename Config>
234 AllocationMode IsoHeapImpl<Config>::updateAllocationMode()
235 {
236     // Exhaust shared free cells, which means we should start activating the fast allocation mode for this type.
237     if (!m_usableBits) {
238         m_slowPathTimePoint = std::chrono::steady_clock::now();
239         return AllocationMode::Fast;
240     }
241
242     switch (m_allocationMode) {
243     case AllocationMode::Shared:
244         // Currently in the shared allocation mode. Until we exhaust shared free cells, continue using the shared allocation mode.
245         // But if we allocate so many shared cells within very short period, we should use the fast allocation mode instead.
246         // This avoids the following pathological case.
247         //
248         //     for (int i = 0; i < 1e6; ++i) {
249         //         auto* ptr = allocate();
250         //         ...
251         //         free(ptr);
252         //     }
253         if (m_numberOfAllocationsFromSharedInOneCycle <= IsoPage<Config>::numObjects)
254             return AllocationMode::Shared;
255         BFALLTHROUGH;
256
257     case AllocationMode::Fast: {
258         // The allocation pattern may change. We should check the allocation rate and decide which mode is more appropriate.
259         // If we don't go to the allocation slow path during 1~ seconds, we think the allocation becomes quiescent state.
260         auto now = std::chrono::steady_clock::now();
261         if ((now - m_slowPathTimePoint) < std::chrono::seconds(1)) {
262             m_slowPathTimePoint = now;
263             return AllocationMode::Fast;
264         }
265
266         m_numberOfAllocationsFromSharedInOneCycle = 0;
267         m_slowPathTimePoint = now;
268         return AllocationMode::Shared;
269     }
270
271     case AllocationMode::Init:
272         m_slowPathTimePoint = std::chrono::steady_clock::now();
273         return AllocationMode::Shared;
274     }
275
276     return AllocationMode::Shared;
277 }
278
279 template<typename Config>
280 void* IsoHeapImpl<Config>::allocateFromShared(bool abortOnFailure)
281 {
282     static constexpr bool verbose = false;
283
284     unsigned indexPlusOne = __builtin_ffs(m_usableBits);
285     BASSERT(indexPlusOne);
286     unsigned index = indexPlusOne - 1;
287     void* result = result = m_sharedCells[index];
288     if (result) {
289         if (verbose)
290             fprintf(stderr, "%p: allocated %p from shared again of size %u\n", this, result, Config::objectSize);
291     } else {
292         constexpr unsigned objectSizeWithHeapImplPointer = Config::objectSize + sizeof(uint8_t);
293         result = IsoSharedHeap::get()->allocateNew<objectSizeWithHeapImplPointer>(abortOnFailure);
294         if (!result)
295             return nullptr;
296         if (verbose)
297             fprintf(stderr, "%p: allocated %p from shared of size %u\n", this, result, Config::objectSize);
298         BASSERT(index < IsoHeapImplBase::maxAllocationFromShared);
299         *indexSlotFor<Config>(result) = index;
300         m_sharedCells[index] = result;
301     }
302     BASSERT(result);
303     m_usableBits &= (~(1U << index));
304     ++m_numberOfAllocationsFromSharedInOneCycle;
305     return result;
306 }
307
308 } // namespace bmalloc
309