mirror of
https://github.com/darlinghq/darling-libutil.git
synced 2024-11-23 04:29:48 +00:00
306 lines
8.8 KiB
C++
306 lines
8.8 KiB
C++
/*
|
|
* 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"
|
|
|
|
void
|
|
ExtentManager::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);
|
|
}
|
|
|
|
void
|
|
ExtentManager::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;
|
|
}
|
|
|
|
void
|
|
ExtentManager::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
|
|
|
|
void
|
|
ExtentManager::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();
|
|
}
|
|
|
|
void
|
|
ExtentManager::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);
|
|
}
|
|
|
|
void
|
|
ExtentManager::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 */
|