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