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