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
BitmapBlock(Volume * volume,uint32 numBits)25 BitmapBlock::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
~BitmapBlock()38 BitmapBlock::~BitmapBlock()
39 {
40 }
41
42
43 bool
SetTo(off_t block)44 BitmapBlock::SetTo(off_t block)
45 {
46 fData = NULL;
47 fReadOnlyData = (uint32*)CachedBlock::SetTo(block);
48
49 return fReadOnlyData != NULL;
50 }
51
52
53 bool
SetToWritable(Transaction & transaction,off_t block,bool empty)54 BitmapBlock::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
63 bool
_Check(uint32 start,uint32 length,bool marked)64 BitmapBlock::_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
134 bool
_Update(uint32 start,uint32 length,bool mark,bool force)135 BitmapBlock::_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
244 void
_FindNext(uint32 & pos,bool marked)245 BitmapBlock::_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
314 void
FindPreviousMarked(uint32 & pos)315 BitmapBlock::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
372 void
FindLargestUnmarkedRange(uint32 & start,uint32 & length)373 BitmapBlock::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
522 uint32
Checksum(uint32 unitsPerGroup) const523 BitmapBlock::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