bmalloc: Don't use a whole page for metadata
[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     LargeObject();
39     LargeObject(void*);
40
41     enum DoNotValidateTag { DoNotValidate };
42     LargeObject(DoNotValidateTag, void*);
43     
44     operator bool() { return !!*this; }
45     bool operator!() { return !m_object; }
46
47     char* begin() const { return static_cast<char*>(m_object); }
48     char* end() const { return begin() + size(); }
49     size_t size() const { return m_beginTag->size(); }
50     Range range() const { return Range(m_object, size()); }
51
52     void setFree(bool) const;
53     bool isFree() const;
54
55     bool prevCanMerge() const;
56     bool nextCanMerge() const;
57
58     VMState vmState() const;
59     void setVMState(VMState) const;
60
61     bool isMarked() const;
62     void setMarked(bool) const;
63
64     bool isValidAndFree(VMState::HasPhysical, size_t) const;
65
66     LargeObject merge() const;
67     std::pair<LargeObject, LargeObject> split(size_t) const;
68
69 private:
70     LargeObject(BeginTag*, EndTag*, void*);
71
72     void validate() const;
73     void validateSelf() const;
74
75     BeginTag* m_beginTag;
76     EndTag* m_endTag;
77     void* m_object;
78 };
79
80 inline LargeObject::LargeObject()
81     : m_beginTag(nullptr)
82     , m_endTag(nullptr)
83     , m_object(nullptr)
84 {
85 }
86
87 inline LargeObject::LargeObject(void* object)
88     : m_beginTag(LargeChunk::beginTag(object))
89     , m_endTag(LargeChunk::endTag(object, m_beginTag->size()))
90     , m_object(object)
91 {
92     validate();
93 }
94
95 inline LargeObject::LargeObject(DoNotValidateTag, void* object)
96     : m_beginTag(LargeChunk::beginTag(object))
97     , m_endTag(LargeChunk::endTag(object, m_beginTag->size()))
98     , m_object(object)
99 {
100 }
101
102 inline LargeObject::LargeObject(BeginTag* beginTag, EndTag* endTag, void* object)
103     : m_beginTag(beginTag)
104     , m_endTag(endTag)
105     , m_object(object)
106 {
107 }
108
109 inline void LargeObject::setFree(bool isFree) const
110 {
111     validate();
112     m_beginTag->setFree(isFree);
113     m_endTag->setFree(isFree);
114 }
115
116 inline bool LargeObject::isFree() const
117 {
118     validate();
119     return m_beginTag->isFree();
120 }
121
122 inline bool LargeObject::prevCanMerge() const
123 {
124     return m_beginTag->prev()->isFree();
125 }
126
127 inline bool LargeObject::nextCanMerge() const
128 {
129     return m_endTag->next()->isFree();
130 }
131
132 inline VMState LargeObject::vmState() const
133 {
134     validate();
135     return m_beginTag->vmState();
136 }
137
138 inline void LargeObject::setVMState(VMState vmState) const
139 {
140     validate();
141     m_beginTag->setVMState(vmState);
142     m_endTag->setVMState(vmState);
143 }
144
145 inline bool LargeObject::isMarked() const
146 {
147     validate();
148     return m_beginTag->isMarked();
149 }
150
151 inline void LargeObject::setMarked(bool isMarked) const
152 {
153     validate();
154     m_beginTag->setMarked(isMarked);
155     m_endTag->setMarked(isMarked);
156 }
157
158 inline bool LargeObject::isValidAndFree(VMState::HasPhysical hasPhysical, size_t expectedSize) const
159 {
160     if (!m_beginTag->isFree())
161         return false;
162     
163     if (m_beginTag->isEnd())
164         return false;
165
166     if (m_beginTag->size() != expectedSize)
167         return false;
168     
169     if (m_beginTag->compactBegin() != BoundaryTag::compactBegin(m_object))
170         return false;
171
172     if (m_beginTag->vmState().hasPhysical() != static_cast<bool>(hasPhysical))
173         return false;
174
175     return true;
176 }
177
178 inline LargeObject LargeObject::merge() const
179 {
180     validate();
181     BASSERT(isFree());
182
183     BeginTag* beginTag = m_beginTag;
184     EndTag* endTag = m_endTag;
185     Range range = this->range();
186     VMState vmState = this->vmState();
187
188     EndTag* prev = beginTag->prev();
189     if (prev->isFree()) {
190         vmState.merge(prev->vmState());
191         Range left(range.begin() - prev->size(), prev->size());
192         range = Range(left.begin(), left.size() + range.size());
193
194         prev->clear();
195         beginTag->clear();
196
197         beginTag = LargeChunk::beginTag(range.begin());
198     }
199
200     BeginTag* next = endTag->next();
201     if (next->isFree()) {
202         vmState.merge(next->vmState());
203         Range right(range.end(), next->size());
204         range = Range(range.begin(), range.size() + right.size());
205
206         endTag->clear();
207         next->clear();
208
209         endTag = LargeChunk::endTag(range.begin(), range.size());
210     }
211
212     beginTag->setRange(range);
213     beginTag->setFree(true);
214     beginTag->setVMState(vmState);
215     endTag->init(beginTag);
216
217     return LargeObject(beginTag, endTag, range.begin());
218 }
219
220 inline std::pair<LargeObject, LargeObject> LargeObject::split(size_t size) const
221 {
222     Range split(begin(), size);
223     Range leftover = Range(split.end(), this->size() - size);
224     BASSERT(leftover.size() >= largeMin);
225
226     BeginTag* splitBeginTag = m_beginTag;
227     EndTag* splitEndTag = LargeChunk::endTag(split.begin(), size);
228
229     BeginTag* leftoverBeginTag = LargeChunk::beginTag(leftover.begin());
230     EndTag* leftoverEndTag = m_endTag;
231
232     splitBeginTag->setRange(split);
233     splitEndTag->init(splitBeginTag);
234
235     *leftoverBeginTag = *splitBeginTag;
236     leftoverBeginTag->setRange(leftover);
237     leftoverEndTag->init(leftoverBeginTag);
238
239     return std::make_pair(
240         LargeObject(splitBeginTag, splitEndTag, split.begin()),
241         LargeObject(leftoverBeginTag, leftoverEndTag, leftover.begin()));
242 }
243
244 inline void LargeObject::validateSelf() const
245 {
246     BASSERT(!m_beginTag->isEnd());
247     BASSERT(m_endTag->isEnd() || static_cast<BoundaryTag*>(m_endTag) == static_cast<BoundaryTag*>(m_beginTag));
248
249     BASSERT(size() >= largeMin);
250
251     BASSERT(m_beginTag->size() == m_endTag->size());
252     BASSERT(m_beginTag->isFree() == m_endTag->isFree());
253     BASSERT(m_beginTag->vmState() == m_endTag->vmState());
254     BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
255 }
256
257 inline void LargeObject::validate() const
258 {
259     if (!m_beginTag->prev()->isSentinel()) {
260         LargeObject prev(DoNotValidate, begin() - m_beginTag->prev()->size());
261         prev.validateSelf();
262     }
263
264     validateSelf();
265
266     if (!m_endTag->next()->isSentinel()) {
267         LargeObject next(DoNotValidate, begin() + size());
268         next.validateSelf();
269     }
270 }
271
272 } // namespace bmalloc
273
274 #endif // LargeObject_h