xref: /haiku/src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp (revision 820dca4df6c7bf955c46e8f6521b9408f50b2900) 
1 /*
2  * Copyright 2001-2010, Haiku Inc. All rights reserved.
3  * This file may be used under the terms of the MIT License.
4  *
5  * Authors:
6  *		Janito V. Ferreira Filho
7  *		Jérôme Duval
8  */
9 
10 
11 #include "BitmapBlock.h"
12 
13 
14 //#define TRACE_EXT2
15 #ifdef TRACE_EXT2
16 #	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
17 #else
18 #	define TRACE(x...) ;
19 #endif
20 #define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
21 
22 
23 BitmapBlock::BitmapBlock(Volume* volume, uint32 numBits)
24 	:
25 	CachedBlock(volume),
26 	fData(NULL),
27 	fReadOnlyData(NULL),
28 	fNumBits(numBits),
29 	fMaxIndex(fNumBits >> 5)
30 {
31 	TRACE("BitmapBlock::BitmapBlock(): num bits: %lu\n", fNumBits);
32 }
33 
34 
35 BitmapBlock::~BitmapBlock()
36 {
37 }
38 
39 
40 bool
41 BitmapBlock::SetTo(off_t block)
42 {
43 	fData = NULL;
44 	fReadOnlyData = (uint32*)CachedBlock::SetTo(block);
45 
46 	return fReadOnlyData != NULL;
47 }
48 
49 
50 bool
51 BitmapBlock::SetToWritable(Transaction& transaction, off_t block, bool empty)
52 {
53 	fReadOnlyData = NULL;
54 	fData = (uint32*)CachedBlock::SetToWritable(transaction, block, empty);
55 
56 	return fData != NULL;
57 }
58 
59 
60 bool
61 BitmapBlock::_Check(uint32 start, uint32 length, bool marked)
62 {
63 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
64 	if (data == NULL)
65 		return false;
66 
67 	if (start + length > fNumBits)
68 		return false;
69 	if (length == 0)
70 		return true;
71 
72 	uint32 startIndex = start >> 5;
73 	uint32 startBit = start & 0x1F;
74 	uint32 remainingBits = (length + startBit) & 0x1F;
75 
76 	uint32 iterations;
77 
78 	if (length < 32) {
79 		if (startBit + length < 32) {
80 			uint32 bits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);
81 
82 			uint32 mask = (1 << (startBit + length)) - 1;
83 			mask &= ~((1 << startBit) - 1);
84 
85 			return (bits & mask) == (marked ? mask : 0);
86 		} else
87 			iterations = 0;
88 	} else
89 		iterations = (length - 32 + startBit) >> 5;
90 
91 	uint32 index = startIndex;
92 
93 	if (startBit != 0) {
94 		uint32 mask = ~((1 << startBit) - 1);
95 		uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
96 
97 		if ((bits & mask) != (marked ? mask : 0)) {
98 			TRACE("BitmapBlock::_Check(): start %lx mask %lx\n", bits, mask);
99 			return false;
100 		}
101 
102 		index += 1;
103 	} else
104 		iterations++;
105 
106 	for (; iterations > 0; --iterations) {
107 		if (data[index++] != (marked ? 0xFFFFFFFF : 0)) {
108 			TRACE("BitmapBlock::_Check(): iterations %lu bits: %lX\n", iterations,
109 				data[index - 1]);
110 			return false;
111 		}
112 	}
113 
114 	if (remainingBits != 0) {
115 		uint32 mask = (1 << remainingBits) - 1;
116 
117 		uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
118 		if ((bits & mask) != (marked ? mask : 0)) {
119 			TRACE("BitmapBlock::_Check(): remainingBits %ld remaining %lX mask %lX\n",
120 				remainingBits, bits, mask);
121 			return false;
122 		}
123 	}
124 
125 	return true;
126 }
127 
128 
129 bool
130 BitmapBlock::_Update(uint32 start, uint32 length, bool mark, bool force)
131 {
132 	TRACE("BitmapBlock::_Update(%lu, %lu, %c, %c)\n", start, length,
133 		unmark ? 't' : 'f', force ? 't' : 'f');
134 
135 	if (fData == NULL || start + length > fNumBits)
136 		return false;
137 
138 	uint32 startIndex = start >> 5;
139 	uint32 startBit = start & 0x1F;
140 	uint32 remainingBits = (length + startBit) & 0x1F;
141 
142 	TRACE("BitmapBlock::_Update(): start index: %lu, start bit: %lu, remaining "
143 		"bits: %lu)\n", startIndex, startBit, remainingBits);
144 	uint32 iterations;
145 
146 	if (length < 32) {
147 		if (startBit + length < 32) {
148 			uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
149 			TRACE("BitmapBlock::_Update(): bits: %lx\n", bits);
150 
151 			uint32 mask = (1 << (startBit + length)) - 1;
152 			mask &= ~((1 << startBit) - 1);
153 
154 			TRACE("BitmapBlock::_Update(): mask: %lx\n", mask);
155 
156 			if ((bits & mask) != (mark ? 0 : mask)) {
157 				ERROR("BitmapBlock::_Update() Marking failed bits %lx "
158 					"startBit %ld\n", bits, startBit);
159 				return false;
160 			}
161 
162 			if (mark)
163 			    bits |= mask;
164 			else
165 			    bits &= ~mask;
166 
167 			TRACE("BitmapBlock::_Update(): updated bits: %lx\n", bits);
168 			fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
169 
170 			return true;
171 		} else
172 			iterations = 0;
173 	} else
174 		iterations = (length - 32 + startBit) >> 5;
175 
176 	TRACE("BitmapBlock::_Update(): iterations: %lu\n", iterations);
177 	uint32 index = startIndex;
178 
179 	if (startBit != 0) {
180 		uint32 mask = ~((1 << startBit) - 1);
181 		uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
182 
183 		TRACE("BitmapBlock::_Update(): mask: %lx, bits: %lx\n", mask, bits);
184 
185 		if (!force && (bits & mask) != (mark ? 0 : mask))
186 			return false;
187 
188 		if (mark)
189 			bits |= mask;
190 		else
191 			bits &= ~mask;
192 		fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
193 
194 		TRACE("BitmapBlock::_Update(): updated bits: %lx\n", bits);
195 		index += 1;
196 	} else
197 		iterations++;
198 
199 	for (; iterations > 0; --iterations) {
200 		if (!force && fData[index] != (mark ? 0 : 0xFFFFFFFF)) {
201 			ERROR("BitmapBlock::_Update() Marking failed "
202 				"index %ld, iterations %ld\n", index, iterations);
203 			return false;
204 		}
205 		fData[index++] = (mark ? 0xFFFFFFFF : 0);
206 	}
207 
208 	TRACE("BitmapBlock::_Update(): Finished iterations\n");
209 
210 	if (remainingBits != 0) {
211 		uint32 mask = (1 << remainingBits) - 1;
212 		uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
213 
214 		TRACE("BitmapBlock::_Update(): mask: %lx, bits: %lx\n", mask, bits);
215 
216 		if (!force && (bits & mask) != (mark ? 0 : mask)) {
217 			ERROR("BitmapBlock::_Update() Marking failed remaining\n");
218 			return false;
219 		}
220 
221 		if (mark)
222 			bits |= mask;
223 		else
224 			bits &= ~mask;
225 		fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
226 
227 		TRACE("BitmapBlock::_Update(): updated bits: %lx\n", bits);
228 	}
229 
230 	return true;
231 }
232 
233 
234 void
235 BitmapBlock::_FindNext(uint32& pos, bool marked)
236 {
237 	TRACE("BitmapBlock::_FindNext(): pos: %lu\n", pos);
238 
239 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
240 	if (data == NULL)
241 		return;
242 
243 	if (pos >= fNumBits) {
244 		pos = fNumBits;
245 		return;
246 	}
247 
248 	uint32 index = pos >> 5;
249 	uint32 bit = pos & 0x1F;
250 	uint32 maxBit = 32;
251 
252 	uint32 mask = ~((1 << bit) - 1);
253 	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
254 
255 	TRACE("BitmapBlock::_FindNext(): index: %lu, bit: %lu, mask: %lX, "
256 		"bits: %lX\n", index, bit, mask, bits);
257 
258 	bits &= mask;
259 	if (bits == (marked ? 0 : mask) && index < fMaxIndex) {
260 		// Find a 32 bits block that has a marked bit
261 		do {
262 			index++;
263 		} while (index < fMaxIndex && data[index] == (marked ? 0 : 0xFFFFFFFF));
264 		bit = 0;
265 		mask = 0xffffffff;
266 	}
267 
268 	if (index >= fMaxIndex) {
269 		maxBit = fNumBits & 0x1F;
270 
271 		if (maxBit == 0) {
272 			// Not found
273 			TRACE("BitmapBlock::_FindNext(): reached end of block, "
274 				"num bits: %lu\n", fNumBits);
275 			pos = fNumBits;
276 			return;
277 		}
278 		bits = B_LENDIAN_TO_HOST_INT32(data[fMaxIndex]);
279 		mask &= (1 << maxBit) - 1;
280 		if ((bits & mask) == (marked ? 0 : mask)) {
281 			TRACE("BitmapBlock::_FindNext(): reached end of block, "
282 				"num bits: %lu\n", fNumBits);
283 			pos = fNumBits;
284 			return;
285 		}
286 		maxBit++;
287 	} else
288 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
289 
290 	for (; bit < maxBit; ++bit) {
291 		// Find the marked bit
292 		if ((bits >> bit & 1) != (marked ? 0U : 1U)) {
293 			pos = index << 5 | bit;
294 			TRACE("BitmapBlock::_FindNext(): found bit: %lu\n", pos);
295 			return;
296 		}
297 	}
298 
299 	panic("Couldn't find bit inside an uint32 (%lx)\n", bits);
300 }
301 
302 
303 void
304 BitmapBlock::FindPreviousMarked(uint32& pos)
305 {
306 	TRACE("BitmapBlock::FindPreviousMarked(%lu)\n", pos);
307 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
308 	if (data == NULL)
309 		return;
310 
311 	if (pos >= fNumBits)
312 		pos = fNumBits;
313 
314 	if (pos == 0)
315 		return;
316 
317 	uint32 index = pos >> 5;
318 	int32 bit = pos & 0x1F;
319 
320 	uint32 mask = (1 << bit) - 1;
321 	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
322 	bits = bits & mask;
323 
324 	TRACE("BitmapBlock::FindPreviousMarked(): index: %lu bit: %lu bits: %lx\n",
325 		index, bit, bits);
326 
327 	if (bits == 0) {
328 		// Find an block of 32 bits that has a marked bit
329 		do {
330 			index--;
331 		} while (data[index] == 0 && index > 0);
332 
333 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
334 		if (bits == 0) {
335 			// Not found
336 			pos = 0;
337 			return;
338 		}
339 
340 		bit = 31;
341 	}
342 
343 	TRACE("BitmapBlock::FindPreviousMarked(): index: %lu bit: %lu bits: %lx\n",
344 		index, bit, bits);
345 
346 	for (; bit >= 0; --bit) {
347 		// Find the marked bit
348 		if ((bits >> bit & 1) != 0) {
349 			pos = index << 5 | bit;
350 			return;
351 		}
352 	}
353 
354 	panic("Couldn't find marked bit inside an int32 with value different than "
355 		"zero!?\n");
356 }
357 
358 
359 void
360 BitmapBlock::FindLargestUnmarkedRange(uint32& start, uint32& length)
361 {
362 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
363 	if (data == NULL)
364 		return;
365 
366 	uint32 wordSpan = length >> 5;
367 	uint32 startIndex = 0;
368 	uint32 index = 0;
369 	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[0]);
370 
371 	TRACE("BitmapBlock::FindLargestUnmarkedRange(): word span: %lu, last "
372 		"index: %lu, start index: %lu, index: %lu, bits: %lX, start: %lu, "
373 		"length: %lu\n", wordSpan, fMaxIndex, startIndex, index, bits, start,
374 		length);
375 
376 	if (wordSpan == 0) {
377 		uint32 startPos = 0;
378 		uint32 endPos = 0;
379 
380 		while (endPos < fNumBits) {
381 			FindNextUnmarked(startPos);
382 			endPos = startPos;
383 
384 			if (startPos != fNumBits) {
385 				FindNextMarked(endPos);
386 
387 				uint32 newLength = endPos - startPos;
388 
389 				if (newLength > length) {
390 					start = startPos;
391 					length = newLength;
392 					TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
393 						"larger length %lu starting at %lu\n", length, start);
394 				}
395 
396 				startPos = endPos;
397 
398 				if (newLength >= 32)
399 					break;
400 			}
401 		}
402 
403 		if (endPos >= fNumBits)
404 			return;
405 
406 		wordSpan = length >> 5;
407 		startIndex = startPos >> 5;
408 		index = (endPos >> 5) + 1;
409 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
410 	}
411 
412 	for (; index < fMaxIndex; ++index) {
413 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
414 
415 		if (bits != 0) {
416 			// Contains marked bits
417 			if (index - startIndex >= wordSpan) {
418 				uint32 newLength = (index - startIndex - 1) << 5;
419 				uint32 newStart = (startIndex + 1) << 5;
420 
421 				uint32 startBits =
422 					B_LENDIAN_TO_HOST_INT32(data[startIndex]);
423 
424 				for (int32 bit = 31; bit >= 0; --bit) {
425 					if ((startBits >> bit & 1) != 0)
426 						break;
427 
428 					++newLength;
429 					--newStart;
430 				}
431 
432 				for (int32 bit = 0; bit < 32; ++bit) {
433 					if ((bits >> bit & 1) != 0)
434 						break;
435 
436 					++newLength;
437 				}
438 
439 				if (newLength > length) {
440 					start = newStart;
441 					length = newLength;
442 					wordSpan = length >> 5;
443 
444 					TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
445 						"larger length %lu starting at %lu; word span: "
446 						"%lu\n", length, start, wordSpan);
447 				}
448 			}
449 
450 			startIndex = index;
451 		}
452 	}
453 
454 	--index;
455 
456 	if (index - startIndex >= wordSpan) {
457 		uint32 newLength = (index - startIndex) << 5;
458 		uint32 newStart = (startIndex + 1) << 5;
459 
460 		TRACE("BitmapBlock::FindLargestUnmarkedRange(): Possibly found a "
461 			"larger range. index: %lu, start index: %lu, word span: %lu, "
462 			"new length: %lu, new start: %lu\n", index, startIndex, wordSpan,
463 			newLength, newStart);
464 
465 		if (newStart != 0) {
466 			uint32 startBits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);
467 
468 			TRACE("BitmapBlock::FindLargestUnmarkedRange(): start bits: %lu\n",
469 				startBits);
470 
471 			for (int32 bit = 31; bit >= 0; --bit) {
472 				if ((startBits >> bit & 1) != 0)
473 					break;
474 
475 				++newLength;
476 				--newStart;
477 			}
478 
479 			TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new start "
480 				"to %lu and new length to %lu\n", newStart, newLength);
481 		}
482 
483 		for (int32 bit = 0; bit < 32; ++bit) {
484 			if ((bits >> bit & 1) == 0)
485 				break;
486 
487 			++newLength;
488 		}
489 
490 		TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new length to "
491 			"%lu\n", newLength);
492 
493 		if (newLength > length) {
494 			start = newStart;
495 			length = newLength;
496 			TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
497 				"largest length %lu starting at %lu\n", length, start);
498 		}
499 	}
500 }
501 
502