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