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