ExtentManager.cpp

   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
  29 void
  30 ExtentManager::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
  42 void
  43 ExtentManager::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
  50 void
  51 ExtentManager::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
 107 void
 108 ExtentManager::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
 175 void
 176 ExtentManager::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
 184 void
 185 ExtentManager::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 /*
 199 clang++ -arch i386 -arch x86_64 -DUNIT_TEST ExtentManager.cpp -o ExtentManager && ./ExtentManager
 200 */
 201
 202 #include <cstdio>
 203 #include <cstdlib>
 204
 205 const 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
 221 int 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
 246 int 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 */