58bf275b650b8675175ea0fe3160a224703bfa9b
[WebKit-https.git] / Source / bmalloc / bmalloc / LargeObject.h
1 /*
2  * Copyright (C) 2015-2016 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 #ifndef LargeObject_h
27 #define LargeObject_h
28
29 #include "BeginTag.h"
30 #include "EndTag.h"
31 #include "LargeChunk.h"
32 #include "Range.h"
33
34 namespace bmalloc {
35
36 class LargeObject {
37 public:
38     static Range init(LargeChunk*);
39
40     LargeObject();
41     LargeObject(void*);
42
43     enum DoNotValidateTag { DoNotValidate };
44     LargeObject(DoNotValidateTag, void*);
45     
46     operator bool() { return !!*this; }
47     bool operator!() { return !m_object; }
48
49     char* begin() const { return static_cast<char*>(m_object); }
50     char* end() const { return begin() + size(); }
51     size_t size() const { return m_beginTag->size(); }
52     Range range() const { return Range(m_object, size()); }
53
54     void setFree(bool) const;
55     bool isFree() const;
56
57     bool prevCanMerge() const;
58     bool nextCanMerge() const;
59
60     VMState vmState() const;
61     void setVMState(VMState) const;
62
63     bool isMarked() const;
64     void setMarked(bool) const;
65
66     bool isValidAndFree(VMState::HasPhysical, size_t) const;
67
68     LargeObject merge() const;
69     std::pair<LargeObject, LargeObject> split(size_t) const;
70
71 private:
72     LargeObject(BeginTag*, EndTag*, void*);
73
74     void validate() const;
75     void validateSelf() const;
76
77     BeginTag* m_beginTag;
78     EndTag* m_endTag;
79     void* m_object;
80 };
81
82 inline LargeObject::LargeObject()
83     : m_beginTag(nullptr)
84     , m_endTag(nullptr)
85     , m_object(nullptr)
86 {
87 }
88
89 inline LargeObject::LargeObject(void* object)
90     : m_beginTag(LargeChunk::beginTag(object))
91     , m_endTag(LargeChunk::endTag(object, m_beginTag->size()))
92     , m_object(object)
93 {
94     validate();
95 }
96
97 inline LargeObject::LargeObject(DoNotValidateTag, void* object)
98     : m_beginTag(LargeChunk::beginTag(object))
99     , m_endTag(LargeChunk::endTag(object, m_beginTag->size()))
100     , m_object(object)
101 {
102 }
103
104 inline LargeObject::LargeObject(BeginTag* beginTag, EndTag* endTag, void* object)
105     : m_beginTag(beginTag)
106     , m_endTag(endTag)
107     , m_object(object)
108 {
109 }
110
111 inline void LargeObject::setFree(bool isFree) const
112 {
113     validate();
114     m_beginTag->setFree(isFree);
115     m_endTag->setFree(isFree);
116 }
117
118 inline bool LargeObject::isFree() const
119 {
120     validate();
121     return m_beginTag->isFree();
122 }
123
124 inline bool LargeObject::prevCanMerge() const
125 {
126     return m_beginTag->prev()->isFree();
127 }
128
129 inline bool LargeObject::nextCanMerge() const
130 {
131     return m_endTag->next()->isFree();
132 }
133
134 inline VMState LargeObject::vmState() const
135 {
136     validate();
137     return m_beginTag->vmState();
138 }
139
140 inline void LargeObject::setVMState(VMState vmState) const
141 {
142     validate();
143     m_beginTag->setVMState(vmState);
144     m_endTag->setVMState(vmState);
145 }
146
147 inline bool LargeObject::isMarked() const
148 {
149     validate();
150     return m_beginTag->isMarked();
151 }
152
153 inline void LargeObject::setMarked(bool isMarked) const
154 {
155     validate();
156     m_beginTag->setMarked(isMarked);
157     m_endTag->setMarked(isMarked);
158 }
159
160 inline bool LargeObject::isValidAndFree(VMState::HasPhysical hasPhysical, size_t expectedSize) const
161 {
162     if (!m_beginTag->isFree())
163         return false;
164     
165     if (m_beginTag->isEnd())
166         return false;
167
168     if (m_beginTag->size() != expectedSize)
169         return false;
170     
171     if (m_beginTag->compactBegin() != BoundaryTag::compactBegin(m_object))
172         return false;
173
174     if (m_beginTag->vmState().hasPhysical() != static_cast<bool>(hasPhysical))
175         return false;
176
177     return true;
178 }
179
180 inline LargeObject LargeObject::merge() const
181 {
182     validate();
183     BASSERT(isFree());
184
185     BeginTag* beginTag = m_beginTag;
186     EndTag* endTag = m_endTag;
187     Range range = this->range();
188     VMState vmState = this->vmState();
189
190     EndTag* prev = beginTag->prev();
191     if (prev->isFree()) {
192         vmState.merge(prev->vmState());
193         Range left(range.begin() - prev->size(), prev->size());
194         range = Range(left.begin(), left.size() + range.size());
195
196         prev->clear();
197         beginTag->clear();
198
199         beginTag = LargeChunk::beginTag(range.begin());
200     }
201
202     BeginTag* next = endTag->next();
203     if (next->isFree()) {
204         vmState.merge(next->vmState());
205         Range right(range.end(), next->size());
206         range = Range(range.begin(), range.size() + right.size());
207
208         endTag->clear();
209         next->clear();
210
211         endTag = LargeChunk::endTag(range.begin(), range.size());
212     }
213
214     beginTag->setRange(range);
215     beginTag->setFree(true);
216     beginTag->setVMState(vmState);
217     endTag->init(beginTag);
218
219     return LargeObject(beginTag, endTag, range.begin());
220 }
221
222 inline std::pair<LargeObject, LargeObject> LargeObject::split(size_t size) const
223 {
224     Range split(begin(), size);
225     Range leftover = Range(split.end(), this->size() - size);
226     BASSERT(leftover.size() >= largeMin);
227
228     BeginTag* splitBeginTag = m_beginTag;
229     EndTag* splitEndTag = LargeChunk::endTag(split.begin(), size);
230
231     BeginTag* leftoverBeginTag = LargeChunk::beginTag(leftover.begin());
232     EndTag* leftoverEndTag = m_endTag;
233
234     splitBeginTag->setRange(split);
235     splitEndTag->init(splitBeginTag);
236
237     *leftoverBeginTag = *splitBeginTag;
238     leftoverBeginTag->setRange(leftover);
239     leftoverEndTag->init(leftoverBeginTag);
240
241     return std::make_pair(
242         LargeObject(splitBeginTag, splitEndTag, split.begin()),
243         LargeObject(leftoverBeginTag, leftoverEndTag, leftover.begin()));
244 }
245
246 inline void LargeObject::validateSelf() const
247 {
248     BASSERT(!m_beginTag->isEnd());
249     BASSERT(m_endTag->isEnd() || static_cast<BoundaryTag*>(m_endTag) == static_cast<BoundaryTag*>(m_beginTag));
250
251     BASSERT(size() >= largeMin);
252
253     BASSERT(m_beginTag->size() == m_endTag->size());
254     BASSERT(m_beginTag->isFree() == m_endTag->isFree());
255     BASSERT(m_beginTag->vmState() == m_endTag->vmState());
256     BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
257 }
258
259 inline void LargeObject::validate() const
260 {
261     if (!m_beginTag->prev()->isSentinel()) {
262         LargeObject prev(DoNotValidate, begin() - m_beginTag->prev()->size());
263         prev.validateSelf();
264     }
265
266     validateSelf();
267
268     if (!m_endTag->next()->isSentinel()) {
269         LargeObject next(DoNotValidate, begin() + size());
270         next.validateSelf();
271     }
272 }
273
274 inline Range LargeObject::init(LargeChunk* chunk)
275 {
276     Range range(chunk->begin(), chunk->end() - chunk->begin());
277
278     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
279     beginTag->setRange(range);
280     beginTag->setFree(true);
281     beginTag->setVMState(VMState::Virtual);
282
283     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
284     endTag->init(beginTag);
285
286     // Mark the left and right edges of our chunk as allocated. This naturally
287     // prevents merging logic from overflowing beyond our chunk, without requiring
288     // special-case checks.
289     
290     EndTag* leftSentinel = beginTag->prev();
291     BASSERT(leftSentinel >= static_cast<void*>(chunk));
292     leftSentinel->initSentinel();
293
294     BeginTag* rightSentinel = endTag->next();
295     BASSERT(rightSentinel < static_cast<void*>(range.begin()));
296     rightSentinel->initSentinel();
297     
298     return range;
299 }
300
301 } // namespace bmalloc
302
303 #endif // LargeObject_h