bmalloc should support strictly type-segregated isolated heaps
[WebKit-https.git] / Source / bmalloc / bmalloc / IsoPageInlines.h
1 /*
2  * Copyright (C) 2017 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 "CryptoRandom.h"
29 #include "IsoDirectory.h"
30 #include "IsoPage.h"
31 #include "VMAllocate.h"
32
33 namespace bmalloc {
34
35 template<typename Config>
36 IsoPage<Config>* IsoPage<Config>::tryCreate(IsoDirectoryBase<Config>& directory, unsigned index)
37 {
38     void* memory = tryVMAllocate(pageSize, pageSize);
39     if (!memory)
40         return nullptr;
41     
42     return new (memory) IsoPage(directory, index);
43 }
44
45 template<typename Config>
46 IsoPage<Config>::IsoPage(IsoDirectoryBase<Config>& directory, unsigned index)
47     : m_directory(directory)
48     , m_index(index)
49 {
50     memset(m_allocBits, 0, sizeof(m_allocBits));
51 }
52
53 template<typename Config>
54 IsoPage<Config>* IsoPage<Config>::pageFor(void* ptr)
55 {
56     return reinterpret_cast<IsoPage<Config>*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1));
57 }
58
59 template<typename Config>
60 void IsoPage<Config>::free(void* passedPtr)
61 {
62     unsigned offset = static_cast<char*>(passedPtr) - reinterpret_cast<char*>(this);
63     unsigned index = offset / Config::objectSize;
64     
65     if (!m_eligibilityHasBeenNoted) {
66         m_eligibilityTrigger.didBecome(*this);
67         m_eligibilityHasBeenNoted = true;
68     }
69     
70     unsigned wordIndex = index / 32;
71     unsigned bitIndex = index % 32;
72     
73     unsigned newWord = m_allocBits[wordIndex] &= ~(1 << bitIndex);
74     if (!newWord) {
75         if (!--m_numNonEmptyWords)
76             m_emptyTrigger.didBecome(*this);
77     }
78 }
79
80 template<typename Config>
81 FreeList IsoPage<Config>::startAllocating()
82 {
83     static constexpr bool verbose = false;
84     
85     if (verbose)
86         fprintf(stderr, "%p: starting allocation.\n", this);
87     
88     RELEASE_BASSERT(!m_isInUseForAllocation);
89     m_isInUseForAllocation = true;
90     m_eligibilityHasBeenNoted = false;
91     
92     FreeList result;
93     if (!m_numNonEmptyWords) {
94         if (verbose)
95             fprintf(stderr, "%p: preparing to bump.\n", this);
96
97         char* payloadEnd = reinterpret_cast<char*>(this) + numObjects * Config::objectSize;
98         result.initializeBump(payloadEnd, (numObjects - indexOfFirstObject()) * Config::objectSize);
99         
100         unsigned begin = indexOfFirstObject();
101         unsigned end = numObjects;
102         
103         unsigned beginWord = begin >> 5;
104         unsigned endWord = end >> 5;
105         
106         if (verbose) {
107             fprintf(stderr, "begin = %u\n", begin);
108             fprintf(stderr, "end = %u\n", end);
109             fprintf(stderr, "beginWord = %u\n", beginWord);
110             fprintf(stderr, "endWord = %u\n", endWord);
111         }
112         
113         auto setSpan = [&] (unsigned word, unsigned begin, unsigned end) -> unsigned {
114             for (unsigned i = begin; i < end; ++i)
115                 word |= (1 << (i & 31));
116             return word;
117         };
118         
119         if (beginWord == endWord) {
120             m_allocBits[beginWord] = setSpan(m_allocBits[beginWord], begin, end);
121             m_numNonEmptyWords = 1;
122         } else {
123             unsigned endBeginSlop = (begin + 31) & ~31;
124             unsigned beginEndSlop = end & ~31;
125             
126             if (verbose) {
127                 fprintf(stderr, "endBeginSlop = %u\n", endBeginSlop);
128                 fprintf(stderr, "beginEndSlop = %u\n", beginEndSlop);
129             }
130             
131             m_allocBits[beginWord] = setSpan(m_allocBits[beginWord], begin, endBeginSlop);
132             if (verbose)
133                 fprintf(stderr, "m_allocBits[beginWord] = %u\n", m_allocBits[beginWord]);
134             if (end > beginEndSlop) {
135                 m_allocBits[endWord] = setSpan(m_allocBits[endWord], beginEndSlop, end);
136                 if (verbose)
137                     fprintf(stderr, "m_allocBits[endWord] = %u\n", m_allocBits[endWord]);
138             }
139             
140             unsigned beginWordContiguous = endBeginSlop / 32;
141             unsigned endWordContiguous = beginEndSlop / 32;
142             if (verbose) {
143                 fprintf(stderr, "beginWordContiguous = %u\n", beginWordContiguous);
144                 fprintf(stderr, "endWordContiguous = %u\n", endWordContiguous);
145             }
146             
147             for (size_t i = beginWordContiguous; i < endWordContiguous; ++i)
148                 m_allocBits[i] = UINT_MAX;
149             m_numNonEmptyWords = endWordContiguous - beginWordContiguous +
150                 (endBeginSlop > begin) + (end > beginEndSlop);
151         }
152         
153         static constexpr bool verify = false;
154         if (verify) {
155             for (unsigned index = 0; index < indexOfFirstObject(); ++index) {
156                 if (!(m_allocBits[index >> 5] & (1 << (index & 31))))
157                     continue;
158                 fprintf(stderr, "Bit is set even though it should not be: %u\n", index);
159                 BCRASH();
160             }
161             for (unsigned index = indexOfFirstObject(); index < numObjects; ++index) {
162                 if (m_allocBits[index >> 5] & (1 << (index & 31)))
163                     continue;
164                 fprintf(stderr, "Bit is not set even though it should be: %u\n", index);
165                 fprintf(stderr, "Word contents: %u\n", m_allocBits[index >> 5]);
166                 fprintf(stderr, "Mask: %u\n", 1 << (index & 31));
167                 BCRASH();
168             }
169         }
170         
171         return result;
172     }
173     
174     uintptr_t secret;
175     cryptoRandom(&secret, sizeof(secret));
176     FreeCell* head = nullptr;
177     unsigned bytes = 0;
178     
179     for (unsigned index = indexOfFirstObject(); index < numObjects; ++index) {
180         unsigned wordIndex = index >> 5;
181         unsigned word = m_allocBits[wordIndex];
182         unsigned bitMask = 1 << (index & 31);
183         if (word & bitMask)
184             continue;
185         if (!word)
186             m_numNonEmptyWords++;
187         m_allocBits[wordIndex] = word | bitMask;
188         char* cellByte = reinterpret_cast<char*>(this) + index * Config::objectSize;
189         if (verbose)
190             fprintf(stderr, "%p: putting %p on free list.\n", this, cellByte);
191         FreeCell* cell = reinterpret_cast<FreeCell*>(cellByte);
192         cell->setNext(head, secret);
193         head = cell;
194         bytes += Config::objectSize;
195     }
196     
197     result.initializeList(head, secret, bytes);
198     return result;
199 }
200
201 template<typename Config>
202 void IsoPage<Config>::stopAllocating(FreeList freeList)
203 {
204     static constexpr bool verbose = false;
205     
206     if (verbose)
207         fprintf(stderr, "%p: stopping allocation.\n", this);
208     
209     freeList.forEach<Config>(
210         [&] (void* ptr) {
211             free(ptr);
212         });
213
214     RELEASE_BASSERT(m_isInUseForAllocation);
215     m_isInUseForAllocation = false;
216
217     m_eligibilityTrigger.handleDeferral(*this);
218     m_emptyTrigger.handleDeferral(*this);
219 }
220
221 template<typename Config>
222 template<typename Func>
223 void IsoPage<Config>::forEachLiveObject(const Func& func)
224 {
225     for (unsigned wordIndex = 0; wordIndex < bitsArrayLength(numObjects); ++wordIndex) {
226         unsigned word = m_allocBits[wordIndex];
227         if (!word)
228             continue;
229         unsigned firstBitIndex = wordIndex * 32;
230         char* cellByte = reinterpret_cast<char*>(this) + firstBitIndex * Config::objectSize;
231         for (unsigned bitIndex = 0; bitIndex < 32; ++bitIndex) {
232             if (word & 1)
233                 func(static_cast<void*>(cellByte));
234             word >>= 1;
235             cellByte += Config::objectSize;
236         }
237     }
238 }
239
240 template<typename Config>
241 IsoHeapImpl<Config>& IsoPage<Config>::heap()
242 {
243     return m_directory.heap();
244 }
245
246 } // namespace bmalloc
247