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 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 38 BitmapBlock::~BitmapBlock() 39 { 40 } 41 42 43 bool 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 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 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 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 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 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 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 523 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