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