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