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
35namespace bmalloc {
36
37template<typename Config>
38IsoPage<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
47template<typename Config>
48IsoPage<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
56inline IsoPageBase* IsoPageBase::pageFor(void* ptr)
57{
58 return reinterpret_cast<IsoPageBase*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1));
59}
60
61template<typename Config>
62IsoPage<Config>* IsoPage<Config>::pageFor(void* ptr)
63{
64 return reinterpret_cast<IsoPage<Config>*>(IsoPageBase::pageFor(ptr));
65}
66
67template<typename Config>
68void 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
89template<typename Config>
90FreeList 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
210template<typename Config>
211void 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
230template<typename Config>
231template<typename Func>
232void 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
249template<typename Config>
250IsoHeapImpl<Config>& IsoPage<Config>::heap()
251{
252 return m_directory.heap();
253}
254
255} // namespace bmalloc
256
257