xref: /haiku/src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp (revision 040a81419dda83d1014e9dc94936a4cb3f027303) 
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: %" B_PRIu32 "\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 %" B_PRIx32 " mask %" B_PRIx32
99 				"\n", bits, mask);
100 			return false;
101 		}
102 
103 		index += 1;
104 	} else
105 		iterations++;
106 
107 	for (; iterations > 0; --iterations) {
108 		if (data[index++] != (marked ? 0xFFFFFFFF : 0)) {
109 			TRACE("BitmapBlock::_Check(): iterations %" B_PRIu32 " bits: %"
110 				B_PRIx32 "\n", iterations, data[index - 1]);
111 			return false;
112 		}
113 	}
114 
115 	if (remainingBits != 0) {
116 		uint32 mask = (1 << remainingBits) - 1;
117 
118 		uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
119 		if ((bits & mask) != (marked ? mask : 0)) {
120 			TRACE("BitmapBlock::_Check(): remainingBits %" B_PRIu32
121 				" remaining %" B_PRIx32 " mask %" B_PRIx32 "\n", remainingBits,
122 				bits, mask);
123 			return false;
124 		}
125 	}
126 
127 	return true;
128 }
129 
130 
131 bool
132 BitmapBlock::_Update(uint32 start, uint32 length, bool mark, bool force)
133 {
134 	TRACE("BitmapBlock::_Update(%" B_PRIu32 ", %" B_PRIu32 ", %c, %c)\n",
135 		start, length, mark ? 't' : 'f', force ? 't' : 'f');
136 
137 	if (fData == NULL || start + length > fNumBits)
138 		return false;
139 
140 	uint32 startIndex = start >> 5;
141 	uint32 startBit = start & 0x1F;
142 	uint32 remainingBits = (length + startBit) & 0x1F;
143 
144 	TRACE("BitmapBlock::_Update(): start index: %" B_PRIu32 ", start bit: %"
145 		B_PRIu32 ", remaining bits: %" B_PRIu32 ")\n", startIndex, startBit,
146 		remainingBits);
147 	uint32 iterations;
148 
149 	if (length < 32) {
150 		if (startBit + length < 32) {
151 			uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
152 			TRACE("BitmapBlock::_Update(): bits: %" B_PRIx32 "\n", bits);
153 
154 			uint32 mask = (1 << (startBit + length)) - 1;
155 			mask &= ~((1 << startBit) - 1);
156 
157 			TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 "\n", mask);
158 
159 			if ((bits & mask) != (mark ? 0 : mask)) {
160 				ERROR("BitmapBlock::_Update() Marking failed bits %" B_PRIx32
161 					" startBit %" B_PRIu32 "\n", bits, startBit);
162 				return false;
163 			}
164 
165 			if (mark)
166 			    bits |= mask;
167 			else
168 			    bits &= ~mask;
169 
170 			TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n",
171 				bits);
172 			fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
173 
174 			return true;
175 		} else
176 			iterations = 0;
177 	} else
178 		iterations = (length - 32 + startBit) >> 5;
179 
180 	TRACE("BitmapBlock::_Update(): iterations: %" B_PRIu32 "\n", iterations);
181 	uint32 index = startIndex;
182 
183 	if (startBit != 0) {
184 		uint32 mask = ~((1 << startBit) - 1);
185 		uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
186 
187 		TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 ", bits: %" B_PRIx32
188 			"\n", mask, bits);
189 
190 		if (!force && (bits & mask) != (mark ? 0 : mask))
191 			return false;
192 
193 		if (mark)
194 			bits |= mask;
195 		else
196 			bits &= ~mask;
197 		fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
198 
199 		TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n", bits);
200 		index += 1;
201 	} else
202 		iterations++;
203 
204 	for (; iterations > 0; --iterations) {
205 		if (!force && fData[index] != (mark ? 0 : 0xFFFFFFFF)) {
206 			ERROR("BitmapBlock::_Update() Marking failed "
207 				"index %" B_PRIu32 ", iterations %" B_PRId32 "\n", index,
208 				iterations);
209 			return false;
210 		}
211 		fData[index++] = (mark ? 0xFFFFFFFF : 0);
212 	}
213 
214 	TRACE("BitmapBlock::_Update(): Finished iterations\n");
215 
216 	if (remainingBits != 0) {
217 		uint32 mask = (1 << remainingBits) - 1;
218 		uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
219 
220 		TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 ", bits: %" B_PRIx32
221 			"\n", mask, bits);
222 
223 		if (!force && (bits & mask) != (mark ? 0 : mask)) {
224 			ERROR("BitmapBlock::_Update() Marking failed remaining\n");
225 			return false;
226 		}
227 
228 		if (mark)
229 			bits |= mask;
230 		else
231 			bits &= ~mask;
232 		fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
233 
234 		TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n", bits);
235 	}
236 
237 	return true;
238 }
239 
240 
241 void
242 BitmapBlock::_FindNext(uint32& pos, bool marked)
243 {
244 	TRACE("BitmapBlock::_FindNext(): pos: %" B_PRIu32 "\n", pos);
245 
246 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
247 	if (data == NULL)
248 		return;
249 
250 	if (pos >= fNumBits) {
251 		pos = fNumBits;
252 		return;
253 	}
254 
255 	uint32 index = pos >> 5;
256 	uint32 bit = pos & 0x1F;
257 	uint32 maxBit = 32;
258 
259 	uint32 mask = ~((1 << bit) - 1);
260 	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
261 
262 	TRACE("BitmapBlock::_FindNext(): index: %" B_PRIu32 ", bit: %" B_PRIu32
263 		", mask: %" B_PRIx32 ", bits: %" B_PRIx32 "\n", index, bit, mask,
264 		bits);
265 
266 	bits &= mask;
267 	if (bits == (marked ? 0 : mask) && index < fMaxIndex) {
268 		// Find a 32 bits block that has a marked bit
269 		do {
270 			index++;
271 		} while (index < fMaxIndex && data[index] == (marked ? 0 : 0xFFFFFFFF));
272 		bit = 0;
273 		mask = 0xffffffff;
274 	}
275 
276 	if (index >= fMaxIndex) {
277 		maxBit = fNumBits & 0x1F;
278 
279 		if (maxBit == 0) {
280 			// Not found
281 			TRACE("BitmapBlock::_FindNext(): reached end of block, "
282 				"num bits: %" B_PRIu32 "\n", fNumBits);
283 			pos = fNumBits;
284 			return;
285 		}
286 		bits = B_LENDIAN_TO_HOST_INT32(data[fMaxIndex]);
287 		mask &= (1 << maxBit) - 1;
288 		if ((bits & mask) == (marked ? 0 : mask)) {
289 			TRACE("BitmapBlock::_FindNext(): reached end of block, "
290 				"num bits: %" B_PRIu32 "\n", fNumBits);
291 			pos = fNumBits;
292 			return;
293 		}
294 		maxBit++;
295 	} else
296 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
297 
298 	for (; bit < maxBit; ++bit) {
299 		// Find the marked bit
300 		if ((bits >> bit & 1) != (marked ? 0U : 1U)) {
301 			pos = index << 5 | bit;
302 			TRACE("BitmapBlock::_FindNext(): found bit: %" B_PRIu32 "\n", pos);
303 			return;
304 		}
305 	}
306 
307 	panic("Couldn't find bit inside an uint32 (%" B_PRIx32 ")\n", bits);
308 }
309 
310 
311 void
312 BitmapBlock::FindPreviousMarked(uint32& pos)
313 {
314 	TRACE("BitmapBlock::FindPreviousMarked(%" B_PRIu32 ")\n", pos);
315 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
316 	if (data == NULL)
317 		return;
318 
319 	if (pos >= fNumBits)
320 		pos = fNumBits;
321 
322 	if (pos == 0)
323 		return;
324 
325 	uint32 index = pos >> 5;
326 	int32 bit = pos & 0x1F;
327 
328 	uint32 mask = (1 << bit) - 1;
329 	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
330 	bits = bits & mask;
331 
332 	TRACE("BitmapBlock::FindPreviousMarked(): index: %" B_PRIu32 " bit: %"
333 		B_PRIu32 " bits: %" B_PRIx32 "\n", index, bit, bits);
334 
335 	if (bits == 0) {
336 		// Find an block of 32 bits that has a marked bit
337 		do {
338 			index--;
339 		} while (data[index] == 0 && index > 0);
340 
341 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
342 		if (bits == 0) {
343 			// Not found
344 			pos = 0;
345 			return;
346 		}
347 
348 		bit = 31;
349 	}
350 
351 	TRACE("BitmapBlock::FindPreviousMarked(): index: %" B_PRIu32 " bit: %"
352 		B_PRIu32 " bits: %" B_PRIx32 "\n", index, bit, bits);
353 
354 	for (; bit >= 0; --bit) {
355 		// Find the marked bit
356 		if ((bits >> bit & 1) != 0) {
357 			pos = index << 5 | bit;
358 			return;
359 		}
360 	}
361 
362 	panic("Couldn't find marked bit inside an int32 with value different than "
363 		"zero!?\n");
364 }
365 
366 
367 void
368 BitmapBlock::FindLargestUnmarkedRange(uint32& start, uint32& length)
369 {
370 	const uint32* data = fData == NULL ? fReadOnlyData : fData;
371 	if (data == NULL)
372 		return;
373 
374 	uint32 wordSpan = length >> 5;
375 	uint32 startIndex = 0;
376 	uint32 index = 0;
377 	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[0]);
378 
379 	TRACE("BitmapBlock::FindLargestUnmarkedRange(): word span: %" B_PRIu32
380 		", last index: %" B_PRIu32 ", start index: %" B_PRIu32 ", index: %"
381 		B_PRIu32 ", bits: %" B_PRIx32 ", start: %" B_PRIu32 ", length: %"
382 		B_PRIu32 "\n", wordSpan, fMaxIndex, startIndex, index, bits, start,
383 		length);
384 
385 	if (wordSpan == 0) {
386 		uint32 startPos = 0;
387 		uint32 endPos = 0;
388 
389 		while (endPos < fNumBits) {
390 			FindNextUnmarked(startPos);
391 			endPos = startPos;
392 
393 			if (startPos != fNumBits) {
394 				FindNextMarked(endPos);
395 
396 				uint32 newLength = endPos - startPos;
397 
398 				if (newLength > length) {
399 					start = startPos;
400 					length = newLength;
401 					TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
402 						"larger length %" B_PRIu32 " starting at %" B_PRIu32
403 						"\n", length, start);
404 				}
405 
406 				startPos = endPos;
407 
408 				if (newLength >= 32)
409 					break;
410 			}
411 		}
412 
413 		if (endPos >= fNumBits)
414 			return;
415 
416 		wordSpan = length >> 5;
417 		startIndex = startPos >> 5;
418 		index = (endPos >> 5) + 1;
419 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
420 	}
421 
422 	for (; index < fMaxIndex; ++index) {
423 		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
424 
425 		if (bits != 0) {
426 			// Contains marked bits
427 			if (index - startIndex >= wordSpan) {
428 				uint32 newLength = (index - startIndex - 1) << 5;
429 				uint32 newStart = (startIndex + 1) << 5;
430 
431 				uint32 startBits =
432 					B_LENDIAN_TO_HOST_INT32(data[startIndex]);
433 
434 				for (int32 bit = 31; bit >= 0; --bit) {
435 					if ((startBits >> bit & 1) != 0)
436 						break;
437 
438 					++newLength;
439 					--newStart;
440 				}
441 
442 				for (int32 bit = 0; bit < 32; ++bit) {
443 					if ((bits >> bit & 1) != 0)
444 						break;
445 
446 					++newLength;
447 				}
448 
449 				if (newLength > length) {
450 					start = newStart;
451 					length = newLength;
452 					wordSpan = length >> 5;
453 
454 					TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
455 						"larger length %" B_PRIu32 " starting at %" B_PRIu32
456 						"; word span: %" B_PRIu32 "\n", length, start,
457 						wordSpan);
458 				}
459 			}
460 
461 			startIndex = index;
462 		}
463 	}
464 
465 	--index;
466 
467 	if (index - startIndex >= wordSpan) {
468 		uint32 newLength = (index - startIndex) << 5;
469 		uint32 newStart = (startIndex + 1) << 5;
470 
471 		TRACE("BitmapBlock::FindLargestUnmarkedRange(): Possibly found a "
472 			"larger range. index: %" B_PRIu32 ", start index: %" B_PRIu32
473 			", word span: %" B_PRIu32 ", new length: %" B_PRIu32
474 			", new start: %" B_PRIu32 "\n", index, startIndex, wordSpan,
475 			newLength, newStart);
476 
477 		if (newStart != 0) {
478 			uint32 startBits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);
479 
480 			TRACE("BitmapBlock::FindLargestUnmarkedRange(): start bits: %"
481 				B_PRIu32 "\n", startBits);
482 
483 			for (int32 bit = 31; bit >= 0; --bit) {
484 				if ((startBits >> bit & 1) != 0)
485 					break;
486 
487 				++newLength;
488 				--newStart;
489 			}
490 
491 			TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new start "
492 				"to %" B_PRIu32 " and new length to %" B_PRIu32 "\n", newStart,
493 				newLength);
494 		}
495 
496 		for (int32 bit = 0; bit < 32; ++bit) {
497 			if ((bits >> bit & 1) == 0)
498 				break;
499 
500 			++newLength;
501 		}
502 
503 		TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new length to "
504 			"%" B_PRIu32 "\n", newLength);
505 
506 		if (newLength > length) {
507 			start = newStart;
508 			length = newLength;
509 			TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
510 				"largest length %" B_PRIu32 " starting at %" B_PRIu32 "\n",
511 				length, start);
512 		}
513 	}
514 }
515 
516