Cider Isn't Darwin Emulation, Really
Something went wrong. Try again.
C++
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306/* * Copyright (c) 2008-2009,2011 Apple Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in * compliance with the License. Please obtain a copy of the License at * http://www.opensource.apple.com/apsl/ and read it before using this * file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. * Please see the License for the specific language governing rights and * limitations under the License. * * @APPLE_LICENSE_HEADER_END@ *///// ExtentManager.cpp//
#include "ExtentManager.h"
voidExtentManager::Init(uint32_t theBlockSize, uint32_t theNativeBlockSize, off_t theTotalBytes){ blockSize = theBlockSize; nativeBlockSize = theNativeBlockSize; totalBytes = theTotalBytes; totalBlocks = howmany(totalBytes, blockSize);
// add sentry empty extents at both sides so empty partition doesn't need to be handled specially AddBlockRangeExtent(0, 0); AddBlockRangeExtent(totalBlocks, 0);}
voidExtentManager::MergeExtent(const ExtentInfo &a, const ExtentInfo &b, ExtentInfo *c){ // merge ext into *curIt c->blockAddr = min(a.blockAddr, b.blockAddr); c->numBlocks = max(a.blockAddr + a.numBlocks, b.blockAddr + b.numBlocks) - c->blockAddr;}
voidExtentManager::AddBlockRangeExtent(off_t blockAddr, off_t numBlocks){ struct ExtentInfo ext, newExt; ListExtIt curIt, newIt; bool merged = false;
// make the range a valid range if ((blockAddr > totalBlocks) || (blockAddr + numBlocks < 0)) { // totally out of range, do nothing return; } if (blockAddr < 0) { numBlocks = blockAddr + numBlocks; blockAddr = 0; } if (blockAddr + numBlocks > totalBlocks) { numBlocks = totalBlocks - blockAddr; }
ext.blockAddr = blockAddr; ext.numBlocks = numBlocks;
for (curIt = extentList.begin(); curIt != extentList.end(); curIt++) { if (BeforeExtent(ext, *curIt)) break; if (!BeforeExtent(*curIt, ext)) { // overlapped extents MergeExtent(ext, *curIt, &newExt); *curIt = newExt; merged = true; break; } }
// insert ext before curIt if (!merged) { curIt = extentList.insert(curIt, ext); // throws bad_alloc when out of memory }
// merge the extents newIt = curIt; curIt = extentList.begin(); while (curIt != extentList.end()) { if (curIt == newIt || BeforeExtent(*curIt, *newIt)) { // curIt is before newIt curIt++; continue; } if (BeforeExtent(*newIt, *curIt)) { // curIt is after newIt now, we are done break; } // merge the two extents MergeExtent(*curIt, *newIt, &newExt); *newIt = newExt; curIt = extentList.erase(curIt); } // printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks); DebugPrint();} // ExtentManager::AddBlockRangeExtent
voidExtentManager::RemoveBlockRangeExtent(off_t blockAddr, off_t numBlocks){ struct ExtentInfo ext, newExt; ListExtIt curIt;
ext.blockAddr = blockAddr; ext.numBlocks = numBlocks;
curIt = extentList.begin(); while (curIt != extentList.end()) { if (BeforeExtent(*curIt, ext)) { curIt++; continue; } if (BeforeExtent(ext, *curIt)) // we are done break; // // If we get here, the input extent and *curIt have at least one block in common. // That is, they overlap in some way. Thus *curIt needs to change, be removed, // or be split into two non-contiguous extents. // if (curIt->blockAddr >= ext.blockAddr && curIt->blockAddr + curIt->numBlocks <= ext.blockAddr + ext.numBlocks) { // // The input extent totally contains *curIt, so remove *curIt. // curIt = extentList.erase(curIt); } else if (curIt->blockAddr < ext.blockAddr && curIt->blockAddr + curIt->numBlocks > ext.blockAddr + ext.numBlocks) { // // The input extent does not include the start of *curIt, nor the end of *curIt, // so split *curIt into two extents. // newExt.blockAddr = ext.blockAddr + ext.numBlocks; newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr; curIt->numBlocks = ext.blockAddr - curIt->blockAddr; curIt++; extentList.insert(curIt, newExt); // throws bad_alloc when out of memory curIt++; } else { // // The input extent contains either the start or the end of *curIt, but not both. // The remove will leave either the end or the start of *curIt (respectively) and // not change the number of extents in the list. // if (curIt->blockAddr >= ext.blockAddr) { // // Remove the start of *curIt by updating both its starting block and size. // assert(curIt->blockAddr + curIt->numBlocks > ext.blockAddr + ext.numBlocks); newExt.blockAddr = ext.blockAddr + ext.numBlocks; newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr; *curIt = newExt; } else { // // Remove the end of *curIt by updating its size. // curIt->numBlocks = ext.blockAddr - curIt->blockAddr; } curIt++; } } //printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks); DebugPrint();}
voidExtentManager::AddByteRangeExtent(off_t byteAddr, off_t numBytes){ off_t blockAddr = byteAddr / blockSize; off_t blockAddrOfLastByte = (byteAddr + numBytes - 1) / blockSize; off_t numBlocks = blockAddrOfLastByte - blockAddr + 1; AddBlockRangeExtent(blockAddr, numBlocks);}
voidExtentManager::DebugPrint(){ ListExtIt it;
for (it = extentList.begin(); it != extentList.end(); it++) { printf("[%lld, %lld] ", it->blockAddr, it->numBlocks); } printf("\n");}
#if UNIT_TEST
/*clang++ -arch i386 -arch x86_64 -DUNIT_TEST ExtentManager.cpp -o ExtentManager && ./ExtentManager*/
#include <cstdio>#include <cstdlib>
const char *DebugDescription(class ExtentManager *extMan){ char *result = strdup(""); char *temp; ListExtIt it;
for (it = extMan->extentList.begin(); it != extMan->extentList.end(); it++) { temp = result; asprintf(&result, "%s[%lld, %lld] ", temp, it->blockAddr, it->numBlocks); free(temp); } return result;}
int SimpleTestCase(off_t addAddr, off_t addBlocks, off_t removeAddr, off_t removeBlocks, const char *expectedResult){ class ExtentManager extMan; const char *actualResult; int result = 0; extMan.Init(512, 512, 512*999); extMan.AddBlockRangeExtent(addAddr, addBlocks); extMan.RemoveBlockRangeExtent(removeAddr, removeBlocks); actualResult = DebugDescription(&extMan); if (strcmp(actualResult, expectedResult)) { fprintf(stderr, "SimpleTestCase(%lld, %lld, %lld, %lld) failed.\n" " Expected result: %s\n" " Actual result: %s\n", addAddr, addBlocks, removeAddr, removeBlocks, expectedResult, actualResult); result = 1; } free((void *)actualResult); return result;}
int main(void){ int failed = 0; class ExtentManager *extMan; // Create an extent, and remove one contained inside, // leaving the start and end of the original extent. // Create: [xxxxxxxxxx] // Remove: [......] failed |= SimpleTestCase(10, 10, 12, 6, "[0, 0] [10, 2] [18, 2] [999, 0] ");
// Create an extent, and remove the whole extent. // Create: [xxxxxxxxxx] // Remove: [..........] failed |= SimpleTestCase(10, 10, 10, 10, "[0, 0] [999, 0] "); // Create an extent, and remove the first part of the extent. // Create: [xxxxxxxxxx] // Remove: [......] failed |= SimpleTestCase(10, 10, 10, 6, "[0, 0] [16, 4] [999, 0] ");
// Create an extent, and remove the last part of the extent. // Create: [xxxxxxxxxx] // Remove: [......] failed |= SimpleTestCase(10, 10, 14, 6, "[0, 0] [10, 4] [999, 0] "); // Create an extent and remove before the start, through the middle. // Create: [xxxxxxxxxx] // Remove: [..........] failed |= SimpleTestCase(10, 10, 6, 10, "[0, 0] [16, 4] [999, 0] ");
// Create an extent and remove from middle to past the end. // Create: [xxxxxxxxxx] // Remove: [..........] failed |= SimpleTestCase(10, 10, 14, 10, "[0, 0] [10, 4] [999, 0] "); // Create an extent and remove from before through past end. // Create: [xxxxxxxxxx] // Remove: [..............] failed |= SimpleTestCase(10, 10, 6, 18, "[0, 0] [999, 0] "); // Create an extent and remove purely before the extent. // Create: [xxxxxxxxxx] // Remove: [...] failed |= SimpleTestCase(10, 10, 2, 5, "[0, 0] [10, 10] [999, 0] "); // Create an extent and remove purely after the extent. // Create: [xxxxxxxxxx] // Remove: [...] failed |= SimpleTestCase(10, 10, 22, 5, "[0, 0] [10, 10] [999, 0] "); if (failed) printf("FAIL!\n"); else printf("Success.\n"); return failed;}
#endif /* UNIT_TEST */