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
35namespace bmalloc {
36
37static inline void validate(const Range& range)
38{
39    UNUSED(range);
40IF_DEBUG(
41    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
42    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
43
44    BASSERT(!beginTag->isEnd());
45    if (beginTag->isXLarge())
46        return;
47)
48    BASSERT(range.size() >= largeMin);
49    BASSERT(beginTag->size() == range.size());
50
51    BASSERT(beginTag->size() == endTag->size());
52    BASSERT(beginTag->isFree() == endTag->isFree());
53    BASSERT(beginTag->hasPhysicalPages() == endTag->hasPhysicalPages());
54    BASSERT(beginTag->isXLarge() == endTag->isXLarge());
55    BASSERT(static_cast<BoundaryTag*>(endTag) == static_cast<BoundaryTag*>(beginTag) || endTag->isEnd());
56}
57
58static 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
65static 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
75static 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
82inline 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    BASSERT(leftSentinel >= static_cast<void*>(chunk));
100    leftSentinel->setSize(largeMin);
101    leftSentinel->setFree(false);
102
103    BeginTag* rightSentinel = endTag->next();
104    BASSERT(rightSentinel < static_cast<void*>(range.begin()));
105    rightSentinel->setSize(largeMin);
106    rightSentinel->setFree(false);
107
108    return range;
109}
110
111inline 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
125inline 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
139INLINE 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
163inline Range BoundaryTag::deallocate(void* object)
164{
165    BeginTag* beginTag = LargeChunk::beginTag(object);
166    BASSERT(!beginTag->isFree());
167    BASSERT(!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
176INLINE 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    BASSERT(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
200INLINE 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    BASSERT(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
223