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