1/* 2 * Copyright (c) 2008-2009,2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23// 24// ExtentManager.cpp 25// 26 27#include "ExtentManager.h" 28 29void 30ExtentManager::Init(uint32_t theBlockSize, uint32_t theNativeBlockSize, off_t theTotalBytes) 31{ 32 blockSize = theBlockSize; 33 nativeBlockSize = theNativeBlockSize; 34 totalBytes = theTotalBytes; 35 totalBlocks = howmany(totalBytes, blockSize); 36 37 // add sentry empty extents at both sides so empty partition doesn't need to be handled specially 38 AddBlockRangeExtent(0, 0); 39 AddBlockRangeExtent(totalBlocks, 0); 40} 41 42void 43ExtentManager::MergeExtent(const ExtentInfo &a, const ExtentInfo &b, ExtentInfo *c) 44{ 45 // merge ext into *curIt 46 c->blockAddr = min(a.blockAddr, b.blockAddr); 47 c->numBlocks = max(a.blockAddr + a.numBlocks, b.blockAddr + b.numBlocks) - c->blockAddr; 48} 49 50void 51ExtentManager::AddBlockRangeExtent(off_t blockAddr, off_t numBlocks) 52{ 53 struct ExtentInfo ext, newExt; 54 ListExtIt curIt, newIt; 55 bool merged = false; 56 57 // make the range a valid range 58 if ((blockAddr > totalBlocks) || (blockAddr + numBlocks < 0)) { // totally out of range, do nothing 59 return; 60 } 61 if (blockAddr < 0) { 62 numBlocks = blockAddr + numBlocks; 63 blockAddr = 0; 64 } 65 if (blockAddr + numBlocks > totalBlocks) { 66 numBlocks = totalBlocks - blockAddr; 67 } 68 69 ext.blockAddr = blockAddr; 70 ext.numBlocks = numBlocks; 71 72 for (curIt = extentList.begin(); curIt != extentList.end(); curIt++) { 73 if (BeforeExtent(ext, *curIt)) 74 break; 75 if (!BeforeExtent(*curIt, ext)) { // overlapped extents 76 MergeExtent(ext, *curIt, &newExt); 77 *curIt = newExt; 78 merged = true; 79 break; 80 } 81 } 82 83 // insert ext before curIt 84 if (!merged) { 85 curIt = extentList.insert(curIt, ext); // throws bad_alloc when out of memory 86 } 87 88 // merge the extents 89 newIt = curIt; 90 curIt = extentList.begin(); 91 while (curIt != extentList.end()) { 92 if (curIt == newIt || BeforeExtent(*curIt, *newIt)) { // curIt is before newIt 93 curIt++; 94 continue; 95 } 96 if (BeforeExtent(*newIt, *curIt)) { // curIt is after newIt now, we are done 97 break; 98 } 99 // merge the two extents 100 MergeExtent(*curIt, *newIt, &newExt); 101 *newIt = newExt; 102 curIt = extentList.erase(curIt); 103 } 104 // printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks); DebugPrint(); 105} // ExtentManager::AddBlockRangeExtent 106 107void 108ExtentManager::RemoveBlockRangeExtent(off_t blockAddr, off_t numBlocks) 109{ 110 struct ExtentInfo ext, newExt; 111 ListExtIt curIt; 112 113 ext.blockAddr = blockAddr; 114 ext.numBlocks = numBlocks; 115 116 curIt = extentList.begin(); 117 while (curIt != extentList.end()) { 118 if (BeforeExtent(*curIt, ext)) { 119 curIt++; 120 continue; 121 } 122 if (BeforeExtent(ext, *curIt)) // we are done 123 break; 124 125 // 126 // If we get here, the input extent and *curIt have at least one block in common. 127 // That is, they overlap in some way. Thus *curIt needs to change, be removed, 128 // or be split into two non-contiguous extents. 129 // 130 131 if (curIt->blockAddr >= ext.blockAddr && 132 curIt->blockAddr + curIt->numBlocks <= ext.blockAddr + ext.numBlocks) { 133 // 134 // The input extent totally contains *curIt, so remove *curIt. 135 // 136 curIt = extentList.erase(curIt); 137 } else if (curIt->blockAddr < ext.blockAddr && 138 curIt->blockAddr + curIt->numBlocks > ext.blockAddr + ext.numBlocks) { 139 // 140 // The input extent does not include the start of *curIt, nor the end of *curIt, 141 // so split *curIt into two extents. 142 // 143 newExt.blockAddr = ext.blockAddr + ext.numBlocks; 144 newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr; 145 curIt->numBlocks = ext.blockAddr - curIt->blockAddr; 146 curIt++; 147 extentList.insert(curIt, newExt); // throws bad_alloc when out of memory 148 curIt++; 149 } else { 150 // 151 // The input extent contains either the start or the end of *curIt, but not both. 152 // The remove will leave either the end or the start of *curIt (respectively) and 153 // not change the number of extents in the list. 154 // 155 if (curIt->blockAddr >= ext.blockAddr) { 156 // 157 // Remove the start of *curIt by updating both its starting block and size. 158 // 159 assert(curIt->blockAddr + curIt->numBlocks > ext.blockAddr + ext.numBlocks); 160 newExt.blockAddr = ext.blockAddr + ext.numBlocks; 161 newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr; 162 *curIt = newExt; 163 } else { 164 // 165 // Remove the end of *curIt by updating its size. 166 // 167 curIt->numBlocks = ext.blockAddr - curIt->blockAddr; 168 } 169 curIt++; 170 } 171 } 172 //printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks); DebugPrint(); 173} 174 175void 176ExtentManager::AddByteRangeExtent(off_t byteAddr, off_t numBytes) 177{ 178 off_t blockAddr = byteAddr / blockSize; 179 off_t blockAddrOfLastByte = (byteAddr + numBytes - 1) / blockSize; 180 off_t numBlocks = blockAddrOfLastByte - blockAddr + 1; 181 AddBlockRangeExtent(blockAddr, numBlocks); 182} 183 184void 185ExtentManager::DebugPrint() 186{ 187 ListExtIt it; 188 189 for (it = extentList.begin(); it != extentList.end(); it++) { 190 printf("[%lld, %lld] ", it->blockAddr, it->numBlocks); 191 } 192 printf("\n"); 193} 194 195 196#if UNIT_TEST 197 198/* 199clang++ -arch i386 -arch x86_64 -DUNIT_TEST ExtentManager.cpp -o ExtentManager && ./ExtentManager 200*/ 201 202#include <cstdio> 203#include <cstdlib> 204 205const char *DebugDescription(class ExtentManager *extMan) 206{ 207 char *result = strdup(""); 208 char *temp; 209 210 ListExtIt it; 211 212 for (it = extMan->extentList.begin(); it != extMan->extentList.end(); it++) { 213 temp = result; 214 asprintf(&result, "%s[%lld, %lld] ", temp, it->blockAddr, it->numBlocks); 215 free(temp); 216 } 217 218 return result; 219} 220 221int SimpleTestCase(off_t addAddr, off_t addBlocks, off_t removeAddr, off_t removeBlocks, const char *expectedResult) 222{ 223 class ExtentManager extMan; 224 const char *actualResult; 225 int result = 0; 226 227 extMan.Init(512, 512, 512*999); 228 extMan.AddBlockRangeExtent(addAddr, addBlocks); 229 extMan.RemoveBlockRangeExtent(removeAddr, removeBlocks); 230 actualResult = DebugDescription(&extMan); 231 if (strcmp(actualResult, expectedResult)) 232 { 233 fprintf(stderr, 234 "SimpleTestCase(%lld, %lld, %lld, %lld) failed.\n" 235 " Expected result: %s\n" 236 " Actual result: %s\n", 237 addAddr, addBlocks, removeAddr, removeBlocks, 238 expectedResult, actualResult); 239 result = 1; 240 } 241 free((void *)actualResult); 242 243 return result; 244} 245 246int main(void) 247{ 248 int failed = 0; 249 class ExtentManager *extMan; 250 251 // Create an extent, and remove one contained inside, 252 // leaving the start and end of the original extent. 253 // Create: [xxxxxxxxxx] 254 // Remove: [......] 255 failed |= SimpleTestCase(10, 10, 12, 6, "[0, 0] [10, 2] [18, 2] [999, 0] "); 256 257 // Create an extent, and remove the whole extent. 258 // Create: [xxxxxxxxxx] 259 // Remove: [..........] 260 failed |= SimpleTestCase(10, 10, 10, 10, "[0, 0] [999, 0] "); 261 262 // Create an extent, and remove the first part of the extent. 263 // Create: [xxxxxxxxxx] 264 // Remove: [......] 265 failed |= SimpleTestCase(10, 10, 10, 6, "[0, 0] [16, 4] [999, 0] "); 266 267 // Create an extent, and remove the last part of the extent. 268 // Create: [xxxxxxxxxx] 269 // Remove: [......] 270 failed |= SimpleTestCase(10, 10, 14, 6, "[0, 0] [10, 4] [999, 0] "); 271 272 // Create an extent and remove before the start, through the middle. 273 // Create: [xxxxxxxxxx] 274 // Remove: [..........] 275 failed |= SimpleTestCase(10, 10, 6, 10, "[0, 0] [16, 4] [999, 0] "); 276 277 // Create an extent and remove from middle to past the end. 278 // Create: [xxxxxxxxxx] 279 // Remove: [..........] 280 failed |= SimpleTestCase(10, 10, 14, 10, "[0, 0] [10, 4] [999, 0] "); 281 282 // Create an extent and remove from before through past end. 283 // Create: [xxxxxxxxxx] 284 // Remove: [..............] 285 failed |= SimpleTestCase(10, 10, 6, 18, "[0, 0] [999, 0] "); 286 287 // Create an extent and remove purely before the extent. 288 // Create: [xxxxxxxxxx] 289 // Remove: [...] 290 failed |= SimpleTestCase(10, 10, 2, 5, "[0, 0] [10, 10] [999, 0] "); 291 292 // Create an extent and remove purely after the extent. 293 // Create: [xxxxxxxxxx] 294 // Remove: [...] 295 failed |= SimpleTestCase(10, 10, 22, 5, "[0, 0] [10, 10] [999, 0] "); 296 297 if (failed) 298 printf("FAIL!\n"); 299 else 300 printf("Success.\n"); 301 302 return failed; 303} 304 305#endif /* UNIT_TEST */ 306