ExtentManager.cpp

   1 /*
   2  * Copyright (c) 2008 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                 // overlapped extents
 125                 if (curIt->blockAddr >= ext.blockAddr &&
 126                         curIt->blockAddr + curIt->numBlocks <= ext.blockAddr + ext.numBlocks) {
 127                         // *curIt is totally within ext, remove curIt
 128                         curIt = extentList.erase(curIt);
 129                 } else if (curIt->blockAddr < ext.blockAddr &&
 130                         curIt->blockAddr + curIt->numBlocks > ext.blockAddr + ext.numBlocks) {
 131                         // ext is totally within *curIt, split ext into two
 132                         newExt.blockAddr = ext.blockAddr + ext.numBlocks;
 133                         newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr;
 134                         curIt->numBlocks = ext.blockAddr - curIt->blockAddr;
 135                         curIt++;
 136                         extentList.insert(curIt, newExt); // throws bad_alloc when out of memory
 137                         curIt++;
 138                 } else { // remove part of ext
 139                         if (curIt->blockAddr >= ext.blockAddr) { // remove the former part of *curIt
 140                                 assert(curIt->blockAddr + curIt->numBlocks > newExt.blockAddr);
 141                                 newExt.blockAddr = ext.blockAddr + ext.numBlocks;
 142                                 newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr;
 143                                 *curIt = newExt;
 144                         } else { // remove the latter part of *curIt
 145                                 curIt->numBlocks = ext.blockAddr - curIt->blockAddr;
 146                         }
 147                         curIt++;
 148                 }
 149         }
 150         //printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks);      DebugPrint();
 151 }
 152
 153 void
 154 ExtentManager::AddByteRangeExtent(off_t byteAddr, off_t numBytes)
 155 {
 156         off_t blockAddr = byteAddr / blockSize;
 157         off_t blockAddrOfLastByte = (byteAddr + numBytes - 1) / blockSize;
 158         off_t numBlocks = blockAddrOfLastByte - blockAddr + 1;
 159         AddBlockRangeExtent(blockAddr, numBlocks);
 160 }
 161
 162 void
 163 ExtentManager::DebugPrint()
 164 {
 165         ListExtIt it;
 166
 167         for (it = extentList.begin(); it != extentList.end(); it++) {
 168                 printf("[%lld, %lld] ", it->blockAddr, it->numBlocks);
 169         }
 170         printf("\n");
 171 }