src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp

   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 }