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