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 */ 8 9 10 #include "BitmapBlock.h" 11 12 13 //#define TRACE_EXT2 14 #ifdef TRACE_EXT2 15 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 16 #else 17 # define TRACE(x...) ; 18 #endif 19 20 21 BitmapBlock::BitmapBlock(Volume* volume, uint32 numBits) 22 : 23 CachedBlock(volume), 24 fData(NULL), 25 fReadOnlyData(NULL), 26 fNumBits(numBits) 27 { 28 TRACE("BitmapBlock::BitmapBlock(): num bits: %lu\n", fNumBits); 29 } 30 31 32 BitmapBlock::~BitmapBlock() 33 { 34 } 35 36 37 /*virtual*/ bool 38 BitmapBlock::SetTo(uint32 block) 39 { 40 fData = NULL; 41 fReadOnlyData = (uint32*)CachedBlock::SetTo(block); 42 43 return fReadOnlyData != NULL; 44 } 45 46 47 /*virtual*/ bool 48 BitmapBlock::SetToWritable(Transaction& transaction, uint32 block, bool empty) 49 { 50 fReadOnlyData = NULL; 51 fData = (uint32*)CachedBlock::SetToWritable(transaction, block, empty); 52 53 return fData != NULL; 54 } 55 56 57 /*virtual*/ bool 58 BitmapBlock::CheckUnmarked(uint32 start, uint32 length) 59 { 60 const uint32* data = fData == NULL ? fReadOnlyData : fData; 61 if (data == NULL) 62 return false; 63 64 if (start + length > fNumBits) 65 return false; 66 67 uint32 startIndex = start >> 5; 68 uint32 startBit = start & 0x1F; 69 uint32 remainingBits = (length - startBit) & 0x1F; 70 71 uint32 iterations; 72 73 if (length < 32) { 74 if (startBit + length < 32) { 75 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]); 76 77 uint32 mask = (1 << (startBit + length)) - 1; 78 mask &= ~((1 << startBit) - 1); 79 80 return (bits & mask) == 0; 81 } else 82 iterations = 0; 83 } else 84 iterations = (length - 32 + startBit) >> 5; 85 86 uint32 index = startIndex; 87 uint32 mask = 0; 88 89 if (startBit != 0) { 90 mask = ~((1 << startBit) - 1); 91 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 92 93 if ((bits & mask) != 0) 94 return false; 95 96 index += 1; 97 } else 98 iterations++; 99 100 for (; iterations > 0; --iterations) { 101 if (data[index++] != 0) 102 return false; 103 } 104 105 if (remainingBits != 0) { 106 mask = (1 << (remainingBits + 1)) - 1; 107 108 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 109 if ((bits & mask) != 0) 110 return false; 111 } 112 113 return true; 114 } 115 116 117 /*virtual*/ bool 118 BitmapBlock::CheckMarked(uint32 start, uint32 length) 119 { 120 const uint32* data = fData == NULL ? fReadOnlyData : fData; 121 if (data == NULL) 122 return false; 123 124 if (start + length > fNumBits) 125 return false; 126 127 uint32 startIndex = start >> 5; 128 uint32 startBit = start & 0x1F; 129 uint32 remainingBits = (length - startBit) & 0x1F; 130 131 uint32 iterations; 132 133 if (length < 32) { 134 if (startBit + length < 32) { 135 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]); 136 137 uint32 mask = (1 << (startBit + length)) - 1; 138 mask &= ~((1 << startBit) - 1); 139 140 return (bits & mask) != 0; 141 } else 142 iterations = 0; 143 } else 144 iterations = (length - 32 + startBit) >> 5; 145 146 uint32 index = startIndex; 147 uint32 mask = 0; 148 149 if (startBit != 0) { 150 mask = ~((1 << startBit) - 1); 151 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 152 153 if ((bits & mask) != mask) 154 return false; 155 156 index += 1; 157 } else 158 iterations++; 159 160 mask = 0xFFFFFFFF; 161 for (; iterations > 0; --iterations) { 162 if (data[index++] != mask) 163 return false; 164 } 165 166 if (remainingBits != 0) { 167 mask = (1 << (remainingBits + 1)) - 1; 168 uint32 bits = B_HOST_TO_LENDIAN_INT32(data[index]); 169 170 if ((bits & mask) != mask) 171 return false; 172 } 173 174 return true; 175 } 176 177 178 /*virtual*/ bool 179 BitmapBlock::Mark(uint32 start, uint32 length, bool force) 180 { 181 if (fData == NULL || start + length > fNumBits) 182 return false; 183 184 uint32 startIndex = start >> 5; 185 uint32 startBit = start & 0x1F; 186 uint32 remainingBits = (length - 32 + startBit) & 0x1F; 187 188 uint32 iterations; 189 190 if (length < 32) { 191 if (startBit + length < 32) { 192 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]); 193 194 uint32 mask = (1 << (startBit + length)) - 1; 195 mask &= ~((1 << startBit) - 1); 196 197 if ((bits & mask) != 0) 198 return false; 199 200 bits |= mask; 201 202 fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits); 203 204 return true; 205 } else 206 iterations = 0; 207 } else 208 iterations = (length - 32 + startBit) >> 5; 209 210 uint32 index = startIndex; 211 uint32 mask = 0; 212 213 TRACE("BitmapBlock::Mark(): start: %lu, length: %lu, startIndex: %lu, " 214 "startBit: %lu, iterations: %lu, remainingBits: %lu\n", start, length, 215 startIndex, startBit, iterations, remainingBits); 216 217 if (startBit != 0) { 218 mask = ~((1 << startBit) - 1); 219 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]); 220 221 TRACE("BitmapBlock::Mark(): index %lu mask: %lX, bits: %lX\n", index, 222 mask, bits); 223 224 if (!force && (bits & mask) != 0) 225 return false; 226 227 bits |= mask; 228 fData[index] = B_HOST_TO_LENDIAN_INT32(bits); 229 230 index += 1; 231 } else 232 iterations++; 233 234 mask = 0xFFFFFFFF; 235 for (; iterations > 0; --iterations) { 236 if (!force && fData[index] != 0) 237 return false; 238 fData[index++] |= mask; 239 } 240 241 if (remainingBits != 0) { 242 mask = (1 << remainingBits) - 1; 243 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]); 244 TRACE("BitmapBlock::Mark(): marking index %lu remaining %lu bits: %lX," 245 " mask: %lX\n", index, remainingBits, bits, mask); 246 247 if (!force && (bits & mask) != 0) 248 return false; 249 250 bits |= mask; 251 fData[index] = B_HOST_TO_LENDIAN_INT32(bits); 252 } 253 254 return true; 255 } 256 257 258 /*virtual*/ bool 259 BitmapBlock::Unmark(uint32 start, uint32 length, bool force) 260 { 261 TRACE("BitmapBlock::Unmark(%lu, %lu, %c)\n", start, length, 262 force ? 't' : 'f'); 263 264 if (fData == NULL || start + length > fNumBits) 265 return false; 266 267 uint32 startIndex = start >> 5; 268 uint32 startBit = start & 0x1F; 269 uint32 remainingBits = (length - 32 + startBit) & 0x1F; 270 271 TRACE("BitmapBlock::Unmark(): start index: %lu, start bit: %lu, remaining " 272 "bits: %lu)\n", startIndex, startBit, remainingBits); 273 uint32 iterations; 274 275 if (length < 32) { 276 if (startBit + length < 32) { 277 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]); 278 TRACE("BitmapBlock::Unmark(): bits: %lx\n", bits); 279 280 uint32 mask = (1 << (startBit + length)) - 1; 281 mask &= ~((1 << startBit) - 1); 282 283 TRACE("BitmapBlock::Unmark(): mask: %lx\n", mask); 284 285 if ((bits & mask) != mask) 286 return false; 287 288 bits &= ~mask; 289 290 TRACE("BitmapBlock::Unmark(): updated bits: %lx\n", bits); 291 fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits); 292 293 return true; 294 } else 295 iterations = 0; 296 } else 297 iterations = (length - 32 + startBit) >> 5; 298 299 TRACE("BitmapBlock::Unmark(): iterations: %lu\n", iterations); 300 uint32 index = startIndex; 301 uint32 mask = 0; 302 303 if (startBit != 0) { 304 mask = ~((1 << startBit) - 1); 305 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]); 306 307 TRACE("BitmapBlock::Unmark(): mask: %lx, bits: %lx\n", mask, bits); 308 309 if (!force && (bits & mask) != mask) 310 return false; 311 312 bits &= ~mask; 313 fData[index] = B_HOST_TO_LENDIAN_INT32(bits); 314 315 TRACE("BitmapBlock::Unmark(): updated bits: %lx\n", bits); 316 index += 1; 317 } else 318 iterations++; 319 320 mask = 0xFFFFFFFF; 321 for (; iterations > 0; --iterations) { 322 if (!force && fData[index] != mask) 323 return false; 324 fData[index++] = 0; 325 } 326 327 TRACE("BitmapBlock::Unmark(): Finished iterations\n"); 328 329 if (remainingBits != 0) { 330 mask = (1 << remainingBits) - 1; 331 uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]); 332 333 TRACE("BitmapBlock::Unmark(): mask: %lx, bits: %lx\n", mask, bits); 334 335 if (!force && (bits & mask) != mask) 336 return false; 337 338 bits &= ~mask; 339 fData[index] = B_HOST_TO_LENDIAN_INT32(bits); 340 341 TRACE("BitmapBlock::Unmark(): updated bits: %lx\n", bits); 342 } 343 344 return true; 345 } 346 347 348 void 349 BitmapBlock::FindNextMarked(uint32& pos) 350 { 351 TRACE("BitmapBlock::FindNextMarked(): pos: %lu\n", pos); 352 353 const uint32* data = fData == NULL ? fReadOnlyData : fData; 354 if (data == NULL) 355 return; 356 357 if (pos >= fNumBits) { 358 pos = fNumBits; 359 return; 360 } 361 362 uint32 index = pos >> 5; 363 uint32 bit = pos & 0x1F; 364 365 uint32 mask = (1 << bit) - 1; 366 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 367 368 TRACE("BitmapBlock::FindNextMarked(): index: %lu, bit: %lu, mask: %lX, " 369 "bits: %lX\n", index, bit, mask, bits); 370 371 bits = bits & ~mask; 372 373 if (bits == 0) { 374 // Find a block of 32 bits that has a marked bit 375 uint32 maxIndex = fNumBits >> 5; 376 TRACE("BitmapBlock::FindNextMarked(): max index: %lu\n", maxIndex); 377 378 do { 379 index++; 380 } while (index < maxIndex && data[index] == 0); 381 382 if (index >= maxIndex) { 383 // Not found 384 TRACE("BitmapBlock::FindNextMarked(): reached end of block, num " 385 "bits: %lu\n", fNumBits); 386 pos = fNumBits; 387 return; 388 } 389 390 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 391 bit = 0; 392 } 393 394 for (; bit < 32; ++bit) { 395 // Find the marked bit 396 if ((bits >> bit & 1) != 0) { 397 pos = index << 5 | bit; 398 TRACE("BitmapBlock::FindNextMarked(): found bit: %lu\n", pos); 399 return; 400 } 401 } 402 403 panic("Couldn't find marked bit inside an int32 which is different than " 404 "zero!?\n"); 405 } 406 407 408 void 409 BitmapBlock::FindNextUnmarked(uint32& pos) 410 { 411 TRACE("BitmapBlock::FindNextUnmarked(): pos: %lu\n", pos); 412 413 const uint32* data = fData == NULL ? fReadOnlyData : fData; 414 if (data == NULL) 415 return; 416 417 if (pos >= fNumBits) { 418 pos = fNumBits; 419 return; 420 } 421 422 uint32 index = pos >> 5; 423 uint32 bit = pos & 0x1F; 424 425 uint32 mask = (1 << bit) - 1; 426 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 427 428 TRACE("BitmapBlock::FindNextUnmarked(): index: %lu, bit: %lu, mask: %lX, " 429 "bits: %lX\n", index, bit, mask, bits); 430 431 bits &= ~mask; 432 433 if (bits == ~mask) { 434 // Find an block of 32 bits that has a unmarked bit 435 uint32 maxIndex = fNumBits >> 5; 436 TRACE("BitmapBlock::FindNextUnmarked(): max index: %lu\n", maxIndex); 437 438 do { 439 index++; 440 } while (index < maxIndex && data[index] == 0xFFFFFFFF); 441 442 if (index >= maxIndex) { 443 // Not found 444 TRACE("BitmapBlock::FindNextUnmarked(): reached end of block, num " 445 "bits: %lu\n", fNumBits); 446 pos = fNumBits; 447 return; 448 } 449 450 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 451 bit = 0; 452 } 453 454 for (; bit < 32; ++bit) { 455 // Find the unmarked bit 456 if ((bits >> bit & 1) == 0) { 457 pos = index << 5 | bit; 458 TRACE("BitmapBlock::FindNextUnmarked(): found bit: %lu\n", pos); 459 return; 460 } 461 } 462 463 panic("Couldn't find unmarked bit inside an int32 whith value zero!?\n"); 464 } 465 466 467 void 468 BitmapBlock::FindPreviousMarked(uint32& pos) 469 { 470 TRACE("BitmapBlock::FindPreviousMarked(%lu)\n", pos); 471 const uint32* data = fData == NULL ? fReadOnlyData : fData; 472 if (data == NULL) 473 return; 474 475 if (pos >= fNumBits) 476 pos = fNumBits; 477 478 if (pos == 0) 479 return; 480 481 uint32 index = pos >> 5; 482 int32 bit = pos & 0x1F; 483 484 uint32 mask = (1 << (bit + 1)) - 1; 485 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 486 bits = bits & mask; 487 488 TRACE("BitmapBlock::FindPreviousMarked(): index: %lu, bit: %lu\n", index, 489 bit); 490 491 if (bits == 0) { 492 // Find an block of 32 bits that has a marked bit 493 do { 494 index--; 495 } while (data[index] == 0 && index >= 0); 496 497 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 498 if (bits == 0) { 499 // Not found 500 pos = 0; 501 return; 502 } 503 504 bit = 31; 505 } 506 507 for (; bit >= 0; --bit) { 508 // Find the unmarked bit 509 if ((bits >> bit & 1) != 0) { 510 pos = index << 5 | bit; 511 return; 512 } 513 } 514 515 panic("Couldn't find marked bit inside an int32 whith value different than " 516 "zero!?\n"); 517 } 518 519 520 void 521 BitmapBlock::FindLargestUnmarkedRange(uint32& start, uint32& length) 522 { 523 const uint32* data = fData == NULL ? fReadOnlyData : fData; 524 if (data == NULL) 525 return; 526 527 uint32 wordSpan = length >> 5; 528 uint32 lastIndex = fNumBits >> 5; 529 uint32 startIndex = 0; 530 uint32 index = 0; 531 uint32 bits = B_LENDIAN_TO_HOST_INT32(data[0]); 532 533 TRACE("BitmapBlock::FindLargestUnmarkedRange(): word span: %lu, last " 534 "index: %lu, start index: %lu, index: %lu, bits: %lX, start: %lu, " 535 "length: %lu\n", wordSpan, lastIndex, startIndex, index, bits, start, 536 length); 537 538 if (wordSpan == 0) { 539 uint32 startPos = 0; 540 uint32 endPos = 0; 541 542 while (endPos < fNumBits) { 543 FindNextUnmarked(startPos); 544 endPos = startPos; 545 546 if (startPos != fNumBits) { 547 FindNextMarked(endPos); 548 549 uint32 newLength = endPos - startPos; 550 551 if (newLength > length) { 552 start = startPos; 553 length = newLength; 554 TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found " 555 "larger length %lu starting at %lu\n", length, start); 556 } 557 558 startPos = endPos; 559 560 if (newLength >= 32) 561 break; 562 } 563 } 564 565 if (endPos >= fNumBits) 566 return; 567 568 wordSpan = length >> 5; 569 startIndex = startPos >> 5; 570 index = (endPos >> 5) + 1; 571 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 572 } 573 574 for (; index < lastIndex; ++index) { 575 bits = B_LENDIAN_TO_HOST_INT32(data[index]); 576 577 if (bits != 0) { 578 // Contains marked bits 579 if (index - startIndex >= wordSpan) { 580 uint32 newLength = (index - startIndex - 1) << 5; 581 uint32 newStart = (startIndex + 1) << 5; 582 583 uint32 startBits = 584 B_LENDIAN_TO_HOST_INT32(data[startIndex]); 585 586 for (int32 bit = 31; bit >= 0; --bit) { 587 if ((startBits >> bit & 1) != 0) 588 break; 589 590 ++newLength; 591 --newStart; 592 } 593 594 for (int32 bit = 0; bit < 32; ++bit) { 595 if ((bits >> bit & 1) != 0) 596 break; 597 598 ++newLength; 599 } 600 601 if (newLength > length) { 602 start = newStart; 603 length = newLength; 604 wordSpan = length >> 5; 605 606 TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found " 607 "larger length %lu starting at %lu; word span: " 608 "%lu\n", length, start, wordSpan); 609 } 610 } 611 612 startIndex = index; 613 } 614 } 615 616 --index; 617 618 if (index - startIndex >= wordSpan) { 619 uint32 newLength = (index - startIndex) << 5; 620 uint32 newStart = (startIndex + 1) << 5; 621 622 TRACE("BitmapBlock::FindLargestUnmarkedRange(): Possibly found a " 623 "larger range. index: %lu, start index: %lu, word span: %lu, " 624 "new length: %lu, new start: %lu\n", index, startIndex, wordSpan, 625 newLength, newStart); 626 627 if (newStart != 0) { 628 uint32 startBits = B_LENDIAN_TO_HOST_INT32(data[startIndex]); 629 630 TRACE("BitmapBlock::FindLargestUnmarkedRange(): start bits: %lu\n", 631 startBits); 632 633 for (int32 bit = 31; bit >= 0; --bit) { 634 if ((startBits >> bit & 1) != 0) 635 break; 636 637 ++newLength; 638 --newStart; 639 } 640 641 TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new start " 642 "to %lu and new length to %lu\n", newStart, newLength); 643 } 644 645 for (int32 bit = 0; bit < 32; ++bit) { 646 if ((bits >> bit & 1) == 0) 647 break; 648 649 ++newLength; 650 } 651 652 TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new length to " 653 "%lu\n", newLength); 654 655 if (newLength > length) { 656 start = newStart; 657 length = newLength; 658 TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found " 659 "largest length %lu starting at %lu\n", length, start); 660 } 661 } 662 } 663 664