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 "BlockAllocator.h" 12 13 #include <util/AutoLock.h> 14 15 #include "BitmapBlock.h" 16 #include "Inode.h" 17 18 19 #undef ASSERT 20 //#define TRACE_EXT2 21 #ifdef TRACE_EXT2 22 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 23 # define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); } 24 #else 25 # define TRACE(x...) ; 26 # define ASSERT(x) ; 27 #endif 28 #define ERROR(x...) dprintf("\33[34mext2:\33[0m " x) 29 30 31 class AllocationBlockGroup : public TransactionListener { 32 public: 33 AllocationBlockGroup(); 34 ~AllocationBlockGroup(); 35 36 status_t Initialize(Volume* volume, uint32 blockGroup, 37 uint32 numBits); 38 39 status_t ScanFreeRanges(); 40 bool IsFull() const; 41 42 status_t Allocate(Transaction& transaction, uint32 start, 43 uint32 length); 44 status_t Free(Transaction& transaction, uint32 start, 45 uint32 length); 46 status_t FreeAll(Transaction& transaction); 47 status_t Check(uint32 start, uint32 length); 48 49 uint32 NumBits() const; 50 uint32 FreeBits() const; 51 uint32 Start() const; 52 53 uint32 LargestStart() const; 54 uint32 LargestLength() const; 55 56 // TransactionListener implementation 57 void TransactionDone(bool success); 58 void RemovedFromTransaction(); 59 60 private: 61 void _AddFreeRange(uint32 start, uint32 length); 62 void _LockInTransaction(Transaction& transaction); 63 64 65 Volume* fVolume; 66 uint32 fBlockGroup; 67 ext2_block_group* fGroupDescriptor; 68 69 mutex fLock; 70 mutex fTransactionLock; 71 int32 fCurrentTransaction; 72 73 uint32 fStart; 74 uint32 fNumBits; 75 off_t fBitmapBlock; 76 77 uint32 fFreeBits; 78 uint32 fFirstFree; 79 uint32 fLargestStart; 80 uint32 fLargestLength; 81 82 uint32 fPreviousFreeBits; 83 uint32 fPreviousFirstFree; 84 uint32 fPreviousLargestStart; 85 uint32 fPreviousLargestLength; 86 }; 87 88 89 AllocationBlockGroup::AllocationBlockGroup() 90 : 91 fVolume(NULL), 92 fBlockGroup(0), 93 fGroupDescriptor(NULL), 94 fStart(0), 95 fNumBits(0), 96 fBitmapBlock(0), 97 fFreeBits(0), 98 fFirstFree(0), 99 fLargestStart(0), 100 fLargestLength(0), 101 fPreviousFreeBits(0), 102 fPreviousFirstFree(0), 103 fPreviousLargestStart(0), 104 fPreviousLargestLength(0) 105 { 106 mutex_init(&fLock, "ext2 allocation block group"); 107 mutex_init(&fTransactionLock, "ext2 allocation block group transaction"); 108 } 109 110 111 AllocationBlockGroup::~AllocationBlockGroup() 112 { 113 mutex_destroy(&fLock); 114 mutex_destroy(&fTransactionLock); 115 } 116 117 118 status_t 119 AllocationBlockGroup::Initialize(Volume* volume, uint32 blockGroup, 120 uint32 numBits) 121 { 122 fVolume = volume; 123 fBlockGroup = blockGroup; 124 fNumBits = numBits; 125 126 status_t status = fVolume->GetBlockGroup(blockGroup, &fGroupDescriptor); 127 if (status != B_OK) 128 return status; 129 130 fBitmapBlock = fGroupDescriptor->BlockBitmap(fVolume->Has64bitFeature()); 131 132 status = ScanFreeRanges(); 133 134 if (fGroupDescriptor->FreeBlocks(fVolume->Has64bitFeature()) 135 != fFreeBits) { 136 ERROR("AllocationBlockGroup(%lu,%lld)::Initialize(): Mismatch between " 137 "counted free blocks (%lu/%lu) and what is set on the group " 138 "descriptor (%lu)\n", fBlockGroup, fBitmapBlock, fFreeBits, 139 fNumBits, fGroupDescriptor->FreeBlocks( 140 fVolume->Has64bitFeature())); 141 return B_BAD_DATA; 142 } 143 144 fPreviousFreeBits = fFreeBits; 145 fPreviousFirstFree = fFirstFree; 146 fPreviousLargestStart = fLargestStart; 147 fPreviousLargestLength = fLargestLength; 148 149 return status; 150 } 151 152 153 status_t 154 AllocationBlockGroup::ScanFreeRanges() 155 { 156 TRACE("AllocationBlockGroup::ScanFreeRanges()\n"); 157 BitmapBlock block(fVolume, fNumBits); 158 159 if (!block.SetTo(fBitmapBlock)) 160 return B_ERROR; 161 162 uint32 start = 0; 163 uint32 end = 0; 164 165 while (end < fNumBits) { 166 block.FindNextUnmarked(start); 167 ASSERT(block.CheckMarked(end, start - end)); 168 end = start; 169 170 if (start != block.NumBits()) { 171 block.FindNextMarked(end); 172 _AddFreeRange(start, end - start); 173 ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength)); 174 start = end; 175 } 176 } 177 178 return B_OK; 179 } 180 181 182 bool 183 AllocationBlockGroup::IsFull() const 184 { 185 return fFreeBits == 0; 186 } 187 188 189 status_t 190 AllocationBlockGroup::Allocate(Transaction& transaction, uint32 start, 191 uint32 length) 192 { 193 TRACE("AllocationBlockGroup::Allocate(%ld,%ld)\n", start, length); 194 uint32 end = start + length; 195 if (end > fNumBits) 196 return B_BAD_DATA; 197 198 _LockInTransaction(transaction); 199 200 BitmapBlock block(fVolume, fNumBits); 201 202 if (!block.SetToWritable(transaction, fBitmapBlock)) 203 return B_ERROR; 204 205 TRACE("AllocationBlockGroup::Allocate(): Largest range in %lu-%lu\n", 206 fLargestStart, fLargestStart + fLargestLength); 207 ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength)); 208 209 if (!block.Mark(start, length)) { 210 ERROR("Failed to allocate blocks from %lu to %lu. Some were " 211 "already allocated.\n", start, start + length); 212 return B_ERROR; 213 } 214 215 fFreeBits -= length; 216 fGroupDescriptor->SetFreeBlocks(fFreeBits, fVolume->Has64bitFeature()); 217 fVolume->WriteBlockGroup(transaction, fBlockGroup); 218 219 if (start == fLargestStart) { 220 if (fFirstFree == fLargestStart) 221 fFirstFree += length; 222 223 fLargestStart += length; 224 fLargestLength -= length; 225 } else if (start + length == fLargestStart + fLargestLength) { 226 fLargestLength -= length; 227 } else if (start < fLargestStart + fLargestLength 228 && start > fLargestStart) { 229 uint32 firstLength = start - fLargestStart; 230 uint32 secondLength = fLargestStart + fLargestLength 231 - (start + length); 232 233 if (firstLength >= secondLength) { 234 fLargestLength = firstLength; 235 } else { 236 fLargestLength = secondLength; 237 fLargestStart = start + length; 238 } 239 } else { 240 // No need to revalidate the largest free range 241 return B_OK; 242 } 243 244 TRACE("AllocationBlockGroup::Allocate(): Largest range in %lu-%lu\n", 245 fLargestStart, fLargestStart + fLargestLength); 246 ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength)); 247 248 if (fLargestLength < fNumBits / 2) 249 block.FindLargestUnmarkedRange(fLargestStart, fLargestLength); 250 251 return B_OK; 252 } 253 254 255 status_t 256 AllocationBlockGroup::Free(Transaction& transaction, uint32 start, 257 uint32 length) 258 { 259 TRACE("AllocationBlockGroup::Free(): start: %lu, length %lu\n", start, 260 length); 261 262 if (length == 0) 263 return B_OK; 264 265 uint32 end = start + length; 266 267 if (end > fNumBits) 268 return B_BAD_DATA; 269 270 _LockInTransaction(transaction); 271 272 BitmapBlock block(fVolume, fNumBits); 273 274 if (!block.SetToWritable(transaction, fBitmapBlock)) 275 return B_ERROR; 276 277 TRACE("AllocationBlockGroup::Free(): Largest range in %lu-%lu\n", 278 fLargestStart, fLargestStart + fLargestLength); 279 ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength)); 280 281 if (!block.Unmark(start, length)) { 282 ERROR("Failed to free blocks from %lu to %lu. Some were " 283 "already freed.\n", start, start + length); 284 return B_ERROR; 285 } 286 287 TRACE("AllocationGroup::Free(): Unmarked bits in bitmap\n"); 288 289 if (fFirstFree > start) 290 fFirstFree = start; 291 292 if (start + length == fLargestStart) { 293 fLargestStart = start; 294 fLargestLength += length; 295 } else if (start == fLargestStart + fLargestLength) { 296 fLargestLength += length; 297 } else if (fLargestLength <= fNumBits / 2) { 298 // May have merged with some free blocks, becoming the largest 299 uint32 newEnd = start + length; 300 block.FindNextMarked(newEnd); 301 302 uint32 newStart = start; 303 block.FindPreviousMarked(newStart); 304 newStart++; 305 306 if (newEnd - newStart > fLargestLength) { 307 fLargestLength = newEnd - newStart; 308 fLargestStart = newStart; 309 } 310 } 311 312 TRACE("AllocationBlockGroup::Free(): Largest range in %lu-%lu\n", 313 fLargestStart, fLargestStart + fLargestLength); 314 ASSERT(block.CheckUnmarked(fLargestStart, fLargestLength)); 315 316 fFreeBits += length; 317 fGroupDescriptor->SetFreeBlocks(fFreeBits, fVolume->Has64bitFeature()); 318 fVolume->WriteBlockGroup(transaction, fBlockGroup); 319 320 return B_OK; 321 } 322 323 324 status_t 325 AllocationBlockGroup::FreeAll(Transaction& transaction) 326 { 327 return Free(transaction, 0, fNumBits); 328 } 329 330 331 uint32 332 AllocationBlockGroup::NumBits() const 333 { 334 return fNumBits; 335 } 336 337 338 uint32 339 AllocationBlockGroup::FreeBits() const 340 { 341 return fFreeBits; 342 } 343 344 345 uint32 346 AllocationBlockGroup::Start() const 347 { 348 return fStart; 349 } 350 351 352 uint32 353 AllocationBlockGroup::LargestStart() const 354 { 355 return fLargestStart; 356 } 357 358 359 uint32 360 AllocationBlockGroup::LargestLength() const 361 { 362 return fLargestLength; 363 } 364 365 366 void 367 AllocationBlockGroup::_AddFreeRange(uint32 start, uint32 length) 368 { 369 if (IsFull()) { 370 fFirstFree = start; 371 fLargestStart = start; 372 fLargestLength = length; 373 } else if (length > fLargestLength) { 374 fLargestStart = start; 375 fLargestLength = length; 376 } 377 378 fFreeBits += length; 379 } 380 381 382 void 383 AllocationBlockGroup::_LockInTransaction(Transaction& transaction) 384 { 385 mutex_lock(&fLock); 386 387 if (transaction.ID() != fCurrentTransaction) { 388 mutex_unlock(&fLock); 389 390 mutex_lock(&fTransactionLock); 391 mutex_lock(&fLock); 392 393 fCurrentTransaction = transaction.ID(); 394 transaction.AddListener(this); 395 } 396 397 mutex_unlock(&fLock); 398 } 399 400 401 void 402 AllocationBlockGroup::TransactionDone(bool success) 403 { 404 if (success) { 405 TRACE("AllocationBlockGroup::TransactionDone(): The transaction " 406 "succeeded, discarding previous state\n"); 407 fPreviousFreeBits = fFreeBits; 408 fPreviousFirstFree = fFirstFree; 409 fPreviousLargestStart = fLargestStart; 410 fPreviousLargestLength = fLargestLength; 411 } else { 412 TRACE("AllocationBlockGroup::TransactionDone(): The transaction " 413 "failed, restoring to previous state\n"); 414 fFreeBits = fPreviousFreeBits; 415 fFirstFree = fPreviousFirstFree; 416 fLargestStart = fPreviousLargestStart; 417 fLargestLength = fPreviousLargestLength; 418 } 419 } 420 421 422 void 423 AllocationBlockGroup::RemovedFromTransaction() 424 { 425 mutex_unlock(&fTransactionLock); 426 fCurrentTransaction = -1; 427 } 428 429 430 BlockAllocator::BlockAllocator(Volume* volume) 431 : 432 fVolume(volume), 433 fGroups(NULL), 434 fBlocksPerGroup(0), 435 fNumBlocks(0), 436 fNumGroups(0) 437 { 438 mutex_init(&fLock, "ext2 block allocator"); 439 } 440 441 442 BlockAllocator::~BlockAllocator() 443 { 444 mutex_destroy(&fLock); 445 446 if (fGroups != NULL) 447 delete [] fGroups; 448 } 449 450 451 status_t 452 BlockAllocator::Initialize() 453 { 454 fBlocksPerGroup = fVolume->BlocksPerGroup(); 455 fNumGroups = fVolume->NumGroups(); 456 fFirstBlock = fVolume->FirstDataBlock(); 457 fNumBlocks = fVolume->NumBlocks(); 458 459 TRACE("BlockAllocator::Initialize(): blocks per group: %lu, block groups: " 460 "%lu, first block: %lu, num blocks: %lu\n", fBlocksPerGroup, 461 fNumGroups, fFirstBlock, fNumBlocks); 462 463 fGroups = new(std::nothrow) AllocationBlockGroup[fNumGroups]; 464 if (fGroups == NULL) 465 return B_NO_MEMORY; 466 467 TRACE("BlockAllocator::Initialize(): allocated allocation block groups\n"); 468 469 mutex_lock(&fLock); 470 // Released by _Initialize 471 472 thread_id id = -1; // spawn_kernel_thread( 473 // (thread_func)BlockAllocator::_Initialize, "ext2 block allocator", 474 // B_LOW_PRIORITY, this); 475 if (id < B_OK) 476 return _Initialize(this); 477 478 // mutex_transfer_lock(&fLock, id); 479 480 // return resume_thread(id); 481 panic("Failed to fall back to synchronous block allocator" 482 "initialization.\n"); 483 return B_ERROR; 484 } 485 486 487 status_t 488 BlockAllocator::AllocateBlocks(Transaction& transaction, uint32 minimum, 489 uint32 maximum, uint32& blockGroup, off_t& start, uint32& length) 490 { 491 TRACE("BlockAllocator::AllocateBlocks()\n"); 492 MutexLocker lock(fLock); 493 TRACE("BlockAllocator::AllocateBlocks(): Acquired lock\n"); 494 495 TRACE("BlockAllocator::AllocateBlocks(): transaction: %ld, min: %lu, " 496 "max: %lu, block group: %lu, start: %llu, num groups: %lu\n", 497 transaction.ID(), minimum, maximum, blockGroup, start, fNumGroups); 498 499 off_t bestStart = 0; 500 uint32 bestLength = 0; 501 uint32 bestGroup = 0; 502 503 uint32 groupNum = blockGroup; 504 505 AllocationBlockGroup* last = &fGroups[fNumGroups]; 506 AllocationBlockGroup* group = &fGroups[blockGroup]; 507 508 for (int32 iterations = 0; iterations < 2; iterations++) { 509 for (; group < last; ++group, ++groupNum) { 510 TRACE("BlockAllocator::AllocateBlocks(): Group %lu has largest " 511 "length of %lu\n", groupNum, group->LargestLength()); 512 513 if (group->LargestLength() > bestLength) { 514 if (start <= group->LargestStart()) { 515 bestStart = group->LargestStart(); 516 bestLength = group->LargestLength(); 517 bestGroup = groupNum; 518 519 TRACE("BlockAllocator::AllocateBlocks(): Found a better " 520 "range: block group: %lu, %llu-%llu\n", groupNum, 521 bestStart, bestStart + bestLength); 522 523 if (bestLength >= maximum) 524 break; 525 } 526 } 527 528 start = 0; 529 } 530 531 if (bestLength >= maximum) 532 break; 533 534 groupNum = 0; 535 536 group = &fGroups[0]; 537 last = &fGroups[blockGroup + 1]; 538 } 539 540 if (bestLength < minimum) { 541 TRACE("BlockAllocator::AllocateBlocks(): best range (length %lu) " 542 "doesn't have minimum length of %lu\n", bestLength, minimum); 543 return B_DEVICE_FULL; 544 } 545 546 if (bestLength > maximum) 547 bestLength = maximum; 548 549 TRACE("BlockAllocator::AllocateBlocks(): Selected range: block group %lu, " 550 "%llu-%llu\n", bestGroup, bestStart, bestStart + bestLength); 551 552 status_t status = fGroups[bestGroup].Allocate(transaction, bestStart, 553 bestLength); 554 if (status != B_OK) { 555 TRACE("BlockAllocator::AllocateBlocks(): Failed to allocate %lu blocks " 556 "inside block group %lu.\n", bestLength, bestGroup); 557 return status; 558 } 559 560 start = bestStart; 561 length = bestLength; 562 blockGroup = bestGroup; 563 564 return B_OK; 565 } 566 567 568 status_t 569 BlockAllocator::Allocate(Transaction& transaction, Inode* inode, 570 off_t numBlocks, uint32 minimum, off_t& start, uint32& allocated) 571 { 572 if (numBlocks <= 0) 573 return B_ERROR; 574 575 uint32 group = inode->ID() / fVolume->InodesPerGroup(); 576 uint32 preferred = 0; 577 578 if (inode->Size() > 0) { 579 // Try to allocate near it's last blocks 580 ext2_data_stream* dataStream = &inode->Node().stream; 581 uint32 numBlocks = inode->Size() / fVolume->BlockSize() + 1; 582 uint32 lastBlock = 0; 583 584 // DANGER! What happens with sparse files? 585 if (numBlocks < EXT2_DIRECT_BLOCKS) { 586 // Only direct blocks 587 lastBlock = dataStream->direct[numBlocks]; 588 } else { 589 numBlocks -= EXT2_DIRECT_BLOCKS - 1; 590 uint32 numIndexes = fVolume->BlockSize() / 4; 591 // block size / sizeof(int32) 592 uint32 numIndexes2 = numIndexes * numIndexes; 593 uint32 numIndexes3 = numIndexes2 * numIndexes; 594 uint32 indexesInIndirect = numIndexes; 595 uint32 indexesInDoubleIndirect = indexesInIndirect 596 + numIndexes2; 597 // uint32 indexesInTripleIndirect = indexesInDoubleIndirect 598 // + numIndexes3; 599 600 uint32 doubleIndirectBlock = EXT2_DIRECT_BLOCKS + 1; 601 uint32 indirectBlock = EXT2_DIRECT_BLOCKS; 602 603 CachedBlock cached(fVolume); 604 uint32* indirectData; 605 606 if (numBlocks > indexesInDoubleIndirect) { 607 // Triple indirect blocks 608 indirectData = (uint32*)cached.SetTo(EXT2_DIRECT_BLOCKS + 2); 609 if (indirectData == NULL) 610 return B_IO_ERROR; 611 612 uint32 index = (numBlocks - indexesInDoubleIndirect) 613 / numIndexes3; 614 doubleIndirectBlock = indirectData[index]; 615 } 616 617 if (numBlocks > indexesInIndirect) { 618 // Double indirect blocks 619 indirectData = (uint32*)cached.SetTo(doubleIndirectBlock); 620 if (indirectData == NULL) 621 return B_IO_ERROR; 622 623 uint32 index = (numBlocks - indexesInIndirect) / numIndexes2; 624 indirectBlock = indirectData[index]; 625 } 626 627 indirectData = (uint32*)cached.SetTo(indirectBlock); 628 if (indirectData == NULL) 629 return B_IO_ERROR; 630 631 uint32 index = numBlocks / numIndexes; 632 lastBlock = indirectData[index]; 633 } 634 635 group = (lastBlock - fFirstBlock) / fBlocksPerGroup; 636 preferred = (lastBlock - fFirstBlock) % fBlocksPerGroup + 1; 637 } 638 639 // TODO: Apply some more policies 640 641 return AllocateBlocks(transaction, minimum, minimum + 8, group, start, 642 allocated); 643 } 644 645 646 status_t 647 BlockAllocator::Free(Transaction& transaction, off_t start, uint32 length) 648 { 649 TRACE("BlockAllocator::Free(%llu, %lu)\n", start, length); 650 MutexLocker lock(fLock); 651 652 if (start <= fFirstBlock) { 653 panic("Trying to free superblock!\n"); 654 return B_BAD_DATA; 655 } 656 657 if (length == 0) 658 return B_OK; 659 660 TRACE("BlockAllocator::Free(): first block: %lu, blocks per group: %lu\n", 661 fFirstBlock, fBlocksPerGroup); 662 663 start -= fFirstBlock; 664 off_t end = start + length - 1; 665 666 uint32 group = start / fBlocksPerGroup; 667 if (group >= fNumGroups) 668 panic("BlockAllocator::Free() group %ld too big (fNumGroups %ld)\n", group, fNumGroups); 669 uint32 lastGroup = end / fBlocksPerGroup; 670 start = start % fBlocksPerGroup; 671 672 if (group == lastGroup) 673 return fGroups[group].Free(transaction, start, length); 674 675 TRACE("BlockAllocator::Free(): Freeing from group %lu: %llu, %llu\n", group, 676 start, fGroups[group].NumBits() - start); 677 678 status_t status = fGroups[group].Free(transaction, start, 679 fGroups[group].NumBits() - start); 680 if (status != B_OK) 681 return status; 682 683 for (++group; group < lastGroup; ++group) { 684 TRACE("BlockAllocator::Free(): Freeing all from group %lu\n", group); 685 status = fGroups[group].FreeAll(transaction); 686 if (status != B_OK) 687 return status; 688 } 689 690 TRACE("BlockAllocator::Free(): Freeing from group %lu: 0-%llu \n", group, 691 end % fBlocksPerGroup); 692 return fGroups[group].Free(transaction, 0, (end + 1) % fBlocksPerGroup); 693 } 694 695 696 /*static*/ status_t 697 BlockAllocator::_Initialize(BlockAllocator* allocator) 698 { 699 TRACE("BlockAllocator::_Initialize()\n"); 700 // fLock is already heald 701 Volume* volume = allocator->fVolume; 702 703 AllocationBlockGroup* groups = allocator->fGroups; 704 uint32 numGroups = allocator->fNumGroups - 1; 705 706 off_t freeBlocks = 0; 707 TRACE("BlockAllocator::_Initialize(): free blocks: %llu\n", freeBlocks); 708 709 for (uint32 i = 0; i < numGroups; ++i) { 710 status_t status = groups[i].Initialize(volume, i, 711 allocator->fBlocksPerGroup); 712 if (status != B_OK) { 713 mutex_unlock(&allocator->fLock); 714 return status; 715 } 716 717 freeBlocks += groups[i].FreeBits(); 718 TRACE("BlockAllocator::_Initialize(): free blocks: %llu\n", freeBlocks); 719 } 720 721 // Last block group may have less blocks 722 status_t status = groups[numGroups].Initialize(volume, numGroups, 723 allocator->fNumBlocks - allocator->fBlocksPerGroup * numGroups 724 - allocator->fFirstBlock); 725 if (status != B_OK) { 726 mutex_unlock(&allocator->fLock); 727 return status; 728 } 729 730 freeBlocks += groups[numGroups].FreeBits(); 731 732 TRACE("BlockAllocator::_Initialize(): free blocks: %llu\n", freeBlocks); 733 734 mutex_unlock(&allocator->fLock); 735 736 if (freeBlocks != volume->NumFreeBlocks()) { 737 TRACE("Counted free blocks (%llu) doesn't match value in the " 738 "superblock (%llu).\n", freeBlocks, volume->NumFreeBlocks()); 739 return B_BAD_DATA; 740 } 741 742 return B_OK; 743 } 744