Build bmalloc on Mac
[WebKit-https.git] / Source / bmalloc / bmalloc / BoundaryTagInlines.h
1 /*
2  * Copyright (C) 2014 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 BoundaryTagInlines_h
27 #define BoundaryTagInlines_h
28
29 #include "Range.h"
30 #include "BeginTag.h"
31 #include "EndTag.h"
32 #include "Inline.h"
33 #include "LargeChunk.h"
34
35 namespace bmalloc {
36
37 static inline void validate(const Range& range)
38 {
39     UNUSED(range);
40 IF_DEBUG(
41     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
42     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
43
44     ASSERT(!beginTag->isEnd());
45     if (beginTag->isXLarge())
46         return;
47 )
48     ASSERT(range.size() >= largeMin);
49     ASSERT(beginTag->size() == range.size());
50
51     ASSERT(beginTag->size() == endTag->size());
52     ASSERT(beginTag->isFree() == endTag->isFree());
53     ASSERT(beginTag->hasPhysicalPages() == endTag->hasPhysicalPages());
54     ASSERT(beginTag->isXLarge() == endTag->isXLarge());
55     ASSERT(static_cast<BoundaryTag*>(endTag) == static_cast<BoundaryTag*>(beginTag) || endTag->isEnd());
56 }
57
58 static inline void validatePrev(EndTag* prev, void* object)
59 {
60     size_t prevSize = prev->size();
61     void* prevObject = static_cast<char*>(object) - prevSize;
62     validate(Range(prevObject, prevSize));
63 }
64
65 static inline void validateNext(BeginTag* next, const Range& range)
66 {
67     if (next->size() == largeMin && !next->isFree()) // Right sentinel tag.
68         return;
69
70     void* nextObject = range.end();
71     size_t nextSize = next->size();
72     validate(Range(nextObject, nextSize));
73 }
74
75 static inline void validate(EndTag* prev, const Range& range, BeginTag* next)
76 {
77     validatePrev(prev, range.begin());
78     validate(range);
79     validateNext(next, range);
80 }
81
82 inline Range BoundaryTag::init(LargeChunk* chunk)
83 {
84     Range range(chunk->begin(), chunk->end() - chunk->begin());
85
86     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
87     beginTag->setSize(range.size());
88     beginTag->setFree(true);
89     beginTag->setHasPhysicalPages(false);
90
91     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
92     *endTag = *beginTag;
93
94     // Mark the left and right edges of our chunk as allocated. This naturally
95     // prevents merging logic from overflowing beyond our chunk, without requiring
96     // special-case checks.
97     
98     EndTag* leftSentinel = beginTag->prev();
99     ASSERT(leftSentinel >= static_cast<void*>(chunk));
100     leftSentinel->setSize(largeMin);
101     leftSentinel->setFree(false);
102
103     BeginTag* rightSentinel = endTag->next();
104     ASSERT(rightSentinel < static_cast<void*>(range.begin()));
105     rightSentinel->setSize(largeMin);
106     rightSentinel->setFree(false);
107     
108     return range;
109 }
110
111 inline void BoundaryTag::mergeLargeLeft(EndTag*& prev, BeginTag*& beginTag, Range& range, bool& hasPhysicalPages)
112 {
113     Range left(range.begin() - prev->size(), prev->size());
114
115     hasPhysicalPages &= prev->hasPhysicalPages();
116
117     range = Range(left.begin(), left.size() + range.size());
118
119     prev->clear();
120     beginTag->clear();
121
122     beginTag = LargeChunk::beginTag(range.begin());
123 }
124
125 inline void BoundaryTag::mergeLargeRight(EndTag*& endTag, BeginTag*& next, Range& range, bool& hasPhysicalPages)
126 {
127     Range right(range.end(), next->size());
128
129     hasPhysicalPages &= next->hasPhysicalPages();
130
131     range = Range(range.begin(), range.size() + right.size());
132
133     endTag->clear();
134     next->clear();
135
136     endTag = LargeChunk::endTag(range.begin(), range.size());
137 }
138
139 INLINE void BoundaryTag::mergeLarge(BeginTag*& beginTag, EndTag*& endTag, Range& range)
140 {
141     EndTag* prev = beginTag->prev();
142     BeginTag* next = endTag->next();
143     bool hasPhysicalPages = beginTag->hasPhysicalPages();
144
145     validate(prev, range, next);
146
147     if (prev->isFree())
148         mergeLargeLeft(prev, beginTag, range, hasPhysicalPages);
149
150     if (next->isFree())
151         mergeLargeRight(endTag, next, range, hasPhysicalPages);
152
153     beginTag->setSize(range.size());
154     beginTag->setFree(true);
155     beginTag->setHasPhysicalPages(hasPhysicalPages);
156
157     if (endTag != static_cast<BoundaryTag*>(beginTag))
158         *endTag = *beginTag;
159
160     validate(beginTag->prev(), range, endTag->next());
161 }
162
163 inline Range BoundaryTag::deallocate(void* object)
164 {
165     BeginTag* beginTag = LargeChunk::beginTag(object);
166     ASSERT(!beginTag->isFree());
167     ASSERT(!beginTag->isXLarge())
168
169     Range range(object, beginTag->size());
170     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
171     mergeLarge(beginTag, endTag, range);
172     
173     return range;
174 }
175
176 INLINE void BoundaryTag::splitLarge(BeginTag* beginTag, size_t size, EndTag*& endTag, Range& range, Range& leftover)
177 {
178     beginTag->setSize(size);
179
180     EndTag* splitEndTag = LargeChunk::endTag(range.begin(), size);
181     if (splitEndTag != static_cast<BoundaryTag*>(beginTag))
182         *splitEndTag = *beginTag;
183
184     leftover = Range(range.begin() + size, range.size() - size);
185     ASSERT(leftover.size() >= largeMin);
186     BeginTag* leftoverBeginTag = LargeChunk::beginTag(leftover.begin());
187     *leftoverBeginTag = *beginTag;
188     leftoverBeginTag->setSize(leftover.size());
189
190     if (leftoverBeginTag != static_cast<BoundaryTag*>(endTag))
191         *endTag = *leftoverBeginTag;
192
193     validate(beginTag->prev(), Range(range.begin(), size), leftoverBeginTag);
194     validate(leftoverBeginTag->prev(), leftover, endTag->next());
195
196     range = Range(range.begin(), size);
197     endTag = splitEndTag;
198 }
199
200 INLINE void BoundaryTag::allocate(size_t size, Range& range, Range& leftover, bool& hasPhysicalPages)
201 {
202     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
203     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
204
205     ASSERT(beginTag->isFree());
206     validate(beginTag->prev(), range, endTag->next());
207
208     if (range.size() - size > largeMin)
209         splitLarge(beginTag, size, endTag, range, leftover);
210
211     hasPhysicalPages = beginTag->hasPhysicalPages();
212
213     beginTag->setHasPhysicalPages(true);
214     beginTag->setFree(false);
215
216     endTag->setHasPhysicalPages(true);
217     endTag->setFree(false);
218 }
219
220 } // namespace bmalloc
221
222 #endif // BoundaryTagInlines_h