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
23BitmapBlock::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
35BitmapBlock::~BitmapBlock()
36{
37}
38
39
40bool
41BitmapBlock::SetTo(off_t block)
42{
43	fData = NULL;
44	fReadOnlyData = (uint32*)CachedBlock::SetTo(block);
45
46	return fReadOnlyData != NULL;
47}
48
49
50bool
51BitmapBlock::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
60bool
61BitmapBlock::_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
129bool
130BitmapBlock::_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
234void
235BitmapBlock::_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
303void
304BitmapBlock::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
359void
360BitmapBlock::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