src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp

   1 /*
   2  * Copyright 2017, Chế Vũ Gia Hy, cvghy116@gmail.com.
   3  * This file may be used under the terms of the MIT License.
   4  */
   5
   6
   7 #include "ExtentAllocator.h"
   8 #include "Chunk.h"
   9
  10
  11 CachedExtent*
  12 CachedExtent::Create(uint64 offset, uint64 length, uint64 flags)
  13 {
  14         CachedExtent* self = new(std::nothrow) CachedExtent();
  15         if (self == NULL)
  16                 return NULL;
  17
  18         self->offset = offset;
  19         self->length = length;
  20         self->refCount = 0;
  21         if ((flags & BTRFS_EXTENT_FLAG_ALLOCATED) != 0)
  22                 self->refCount = 1;
  23         self->flags = flags;
  24         self->item = NULL;
  25         return self;
  26 }
  27
  28
  29 void
  30 CachedExtent::Delete()
  31 {
  32         if (item != NULL)
  33                 free(item);
  34         item = NULL;
  35         delete this;
  36 }
  37
  38
  39 bool
  40 CachedExtent::IsAllocated() const
  41 {
  42         return (flags & BTRFS_EXTENT_FLAG_ALLOCATED) != 0;
  43 }
  44
  45
  46 bool
  47 CachedExtent::IsData() const
  48 {
  49         return (flags & BTRFS_EXTENT_FLAG_DATA) != 0;
  50 }
  51
  52
  53 void
  54 CachedExtent::Info() const
  55 {
  56         const char* extentType = "allocated tree block";
  57         if (IsAllocated() == false && IsData() == false)
  58                 extentType = "free tree block";
  59         else if (IsAllocated() == false && IsData() == true)
  60                 extentType = "free data extent";
  61         else if (IsAllocated() == true && IsData() == true)
  62                 extentType = "allocated data extent";
  63
  64         TRACE("%s at %" B_PRIu64 " length %" B_PRIu64 " refCount %i\n",
  65                 extentType, offset, length, refCount);
  66 }
  67
  68
  69 // ExtentTree Implementation
  70
  71
  72 CachedExtentTree::CachedExtentTree(const TreeDefinition& definition)
  73         :
  74         AVLTree<TreeDefinition>(definition)
  75 {
  76 }
  77
  78
  79 CachedExtentTree::~CachedExtentTree()
  80 {
  81         Delete();
  82 }
  83
  84
  85 /* Find extent that cover or after "offset" and has length >= "size"
  86  * it must also satisfy the condition "type".
  87  */
  88 status_t
  89 CachedExtentTree::FindNext(CachedExtent** chosen, uint64 offset, uint64 size,
  90         uint64 type)
  91 {
  92         CachedExtent* found = Find(offset);
  93         while (found != NULL && (found->flags != type || found->length < size))
  94                 found = Next(found);
  95
  96         if (found == NULL)
  97                 return B_ENTRY_NOT_FOUND;
  98         *chosen = found;
  99         return B_OK;
 100 }
 101
 102
 103 /* this will insert all free extents that are holes,
 104  * created by existed allocated extents in the tree
 105  * from lowerBound to upperBound
 106  */
 107 status_t
 108 CachedExtentTree::FillFreeExtents(uint64 lowerBound, uint64 upperBound)
 109 {
 110         CachedExtent* node = FindClosest(lowerBound, false);
 111         CachedExtent* hole = NULL;
 112         status_t status = B_OK;
 113         uint64 flags = node->flags & (~BTRFS_EXTENT_FLAG_ALLOCATED);
 114         if (lowerBound < node->offset) {
 115                 hole = CachedExtent::Create(lowerBound, node->offset - lowerBound,
 116                         flags);
 117                 status = _AddFreeExtent(hole);
 118                 if (status != B_OK)
 119                         return status;
 120         }
 121
 122         CachedExtent* next = NULL;
 123         while ((next = Next(node)) != NULL && next->End() < upperBound) {
 124                 if (node->End() == next->offset) {
 125                         node = next;
 126                         continue;
 127                 }
 128
 129                 hole = CachedExtent::Create(node->End(), next->offset - node->End(),
 130                         flags);
 131                 status = _AddFreeExtent(hole);
 132                 if (status != B_OK)
 133                         return status;
 134                 node = next;
 135         }
 136
 137         // final node should be a right most node
 138         if (upperBound > node->End()) {
 139                 hole = CachedExtent::Create(node->End(), upperBound - node->End(),
 140                         flags);
 141                 status = _AddFreeExtent(hole);
 142         }
 143
 144         return status;
 145 }
 146
 147
 148 void
 149 CachedExtentTree::_RemoveExtent(CachedExtent* node)
 150 {
 151         node->refCount--;
 152         if (node->refCount <= 0) {
 153                 Remove(node);
 154                 node->Delete();
 155         }
 156 }
 157
 158
 159 status_t
 160 CachedExtentTree::_AddAllocatedExtent(CachedExtent* node)
 161 {
 162         if (node == NULL || node->IsAllocated() == false)
 163                 return B_BAD_VALUE;
 164
 165         CachedExtent* found = Find(node->offset);
 166         if (found == NULL) {
 167                 Insert(node);
 168                 return B_OK;
 169         }
 170
 171         if ((found->IsData() && !node->IsData())
 172                 || (!found->IsData() && node->IsData())) {
 173                 // this shouldn't happen as because different type has
 174                 // its different region for locating.
 175                 node->Delete();
 176                 return B_BAD_VALUE;
 177         }
 178
 179         if (found->IsAllocated() == false) {
 180                 // split free extents (found)
 181                 if (node->End() > found->End()) {
 182                         // TODO: when to handle this ?
 183                         node->Delete();
 184                         return B_BAD_VALUE;
 185                 }
 186
 187                 // |----- found ------|
 188                 //    |-- node ---|
 189                 uint64 diff = node->offset - found->offset;
 190                 found->offset += diff + node->length;
 191                 found->length -= diff + node->length;
 192                 // diff < 0 couldn't happen because of the Compare function
 193                 if (diff > 0) {
 194                         CachedExtent* leftEmpty = CachedExtent::Create(
 195                                 node->offset - diff, diff, found->flags);
 196                         _AddFreeExtent(leftEmpty);
 197                 }
 198
 199                 if (found->length == 0) {
 200                         // free-extent that has no space
 201                         _RemoveExtent(found);
 202                 }
 203
 204                 Insert(node);
 205                 return B_OK;
 206         }
 207
 208         if (found->length == node->length) {
 209                 found->refCount++;
 210         } else {
 211                 // TODO: What should we do in this case ?
 212                 return B_BAD_VALUE;
 213         }
 214         node->Delete();
 215
 216         return B_OK;
 217 }
 218
 219
 220 status_t
 221 CachedExtentTree::_AddFreeExtent(CachedExtent* node)
 222 {
 223         if (node == NULL || node->IsAllocated() == true)
 224                 return B_BAD_VALUE;
 225
 226         CachedExtent* found = Find(node->offset);
 227         if (found == NULL) {
 228                 Insert(node);
 229                 _CombineFreeExtent(node);
 230                 return B_OK;
 231         }
 232
 233         if ((found->IsData() && !node->IsData())
 234                 || (!found->IsData() && node->IsData())) {
 235                 // this shouldn't happen as because different type has
 236                 // its different region for locating.
 237                 node->Delete();
 238                 return B_BAD_VALUE;
 239         }
 240
 241         if (found->End() < node->End()) {
 242                 // |---- found-----|
 243                 //      |--- node ------|
 244                 CachedExtent* rightEmpty = CachedExtent::Create(found->End(),
 245                         node->End() - found->End(), node->flags);
 246                 _AddFreeExtent(rightEmpty);
 247                 node->length -= node->End() - found->End();
 248         }
 249
 250         if (found->IsAllocated() == true) {
 251                 // free part of the allocated extents(found)
 252                 // |----- found ------|
 253                 //    |-- node ---|
 254                 uint64 diff = node->offset - found->offset;
 255                 found->offset += diff + node->length;
 256                 found->length -= diff + node->length;
 257                 // diff < 0 couldn't happen because of the Compare function
 258                 if (diff > 0){
 259                         CachedExtent* left = CachedExtent::Create(node->offset - diff,
 260                                 diff, found->flags);
 261                         _AddAllocatedExtent(left);
 262                 }
 263
 264                 if (found->length == 0)
 265                         _RemoveExtent(found);
 266
 267                 Insert(node);
 268                 _CombineFreeExtent(node);
 269         }
 270
 271         return B_OK;
 272 }
 273
 274
 275 status_t
 276 CachedExtentTree::AddExtent(CachedExtent* extent)
 277 {
 278         if (extent->IsAllocated() == true)
 279                 return _AddAllocatedExtent(extent);
 280         return _AddFreeExtent(extent);
 281 }
 282
 283
 284 void
 285 CachedExtentTree::_CombineFreeExtent(CachedExtent* node)
 286 {
 287         // node should be inserted first to call this function,
 288         // otherwise it will overdelete.
 289         if (node->IsAllocated() == true)
 290                 return;
 291
 292         CachedExtent* other = Next(node);
 293         if (other != NULL) {
 294                 if (node->End() == other->offset && node->flags == other->flags) {
 295                         node->length += other->length;
 296                         _RemoveExtent(other);
 297                 }
 298         }
 299
 300         other = Previous(node);
 301         if (other != NULL) {
 302                 if (other->End() == node->offset && node->flags == other->flags) {
 303                         other->length += node->length;
 304                         _RemoveExtent(node);
 305                 }
 306         }
 307 }
 308
 309
 310 void
 311 CachedExtentTree::_DumpInOrder(CachedExtent* node) const
 312 {
 313         if (node == NULL)
 314                 return;
 315         _DumpInOrder(_GetValue(node->left));
 316         node->Info();
 317         _DumpInOrder(_GetValue(node->right));
 318 }
 319
 320
 321 void
 322 CachedExtentTree::DumpInOrder() const
 323 {
 324         TRACE("\n");
 325         _DumpInOrder(RootNode());
 326         TRACE("\n");
 327 }
 328
 329
 330 void
 331 CachedExtentTree::Delete()
 332 {
 333         _Delete(RootNode());
 334         Clear();
 335 }
 336
 337
 338 void
 339 CachedExtentTree::_Delete(CachedExtent* node)
 340 {
 341         if (node == NULL)
 342                 return;
 343         _Delete(_GetValue(node->left));
 344         _Delete(_GetValue(node->right));
 345         node->Delete();
 346 }
 347
 348
 349 // BlockGroup
 350
 351
 352 BlockGroup::BlockGroup(BTree* extentTree)
 353         :
 354         fItem(NULL)
 355 {
 356         fCurrentExtentTree = new(std::nothrow) BTree(extentTree->SystemVolume(),
 357                 extentTree->RootBlock());
 358 }
 359
 360
 361 BlockGroup::~BlockGroup()
 362 {
 363         if (fItem != NULL) {
 364                 free(fItem);
 365                 fItem = NULL;
 366         }
 367
 368         delete fCurrentExtentTree;
 369         fCurrentExtentTree = NULL;
 370 }
 371
 372
 373 status_t
 374 BlockGroup::SetExtentTree(off_t rootAddress)
 375 {
 376         status_t status = fCurrentExtentTree->SetRoot(rootAddress, NULL);
 377         if (status != B_OK)
 378                 return status;
 379
 380         if (fItem != NULL) {
 381                 // re-allocate BlockGroup;
 382                 uint64 flags = Flags();
 383                 return Initialize(flags);
 384         }
 385
 386         return B_OK;
 387 }
 388
 389
 390 /* Initialize BlockGroup that has flag
 391  */
 392 status_t
 393 BlockGroup::Initialize(uint64 flag)
 394 {
 395         if (fCurrentExtentTree == NULL)
 396                 return B_NO_MEMORY;
 397
 398         if (fItem != NULL)
 399                 free(fItem);
 400
 401         TRACE("BlockGroup::Initialize() find block group has flag: %"
 402                 B_PRIu64 "\n", flag);
 403         BTree::Path path(fCurrentExtentTree);
 404         fKey.SetObjectID(0);
 405         // find first item in extent to get the ObjectID
 406         // ignore type because block_group is not always the first item
 407         fKey.SetType(BTRFS_KEY_TYPE_ANY);
 408         fCurrentExtentTree->FindNext(&path, fKey, NULL);
 409
 410         fKey.SetType(BTRFS_KEY_TYPE_BLOCKGROUP_ITEM);
 411         fKey.SetOffset(0);
 412         status_t status;
 413
 414         while(true) {
 415                 status = fCurrentExtentTree->FindNext(&path, fKey, (void**)&fItem);
 416                 if ((Flags() & flag) == flag || status != B_OK)
 417                         break;
 418                 fKey.SetObjectID(End());
 419                 fKey.SetOffset(0);
 420         }
 421
 422         if (status != B_OK)
 423                 ERROR("BlockGroup::Initialize() cannot find block group\n");
 424
 425         return status;
 426 }
 427
 428
 429 status_t
 430 BlockGroup::LoadExtent(CachedExtentTree* tree, bool inverse)
 431 {
 432         if (fItem == NULL)
 433                 return B_NO_INIT;
 434
 435         uint64 flags = (Flags() & BTRFS_BLOCKGROUP_FLAG_DATA) != 0 ?
 436                 BTRFS_EXTENT_FLAG_DATA : BTRFS_EXTENT_FLAG_TREE_BLOCK;
 437         if (inverse == false)
 438                 flags |= BTRFS_EXTENT_FLAG_ALLOCATED;
 439
 440         uint64 start = Start();
 441         CachedExtent* insert;
 442         void* data;
 443         uint64 extentSize = fCurrentExtentTree->SystemVolume()->BlockSize();
 444
 445         btrfs_key key;
 446         key.SetType(BTRFS_KEY_TYPE_METADATA_ITEM);
 447         if ((flags & BTRFS_EXTENT_FLAG_DATA) != 0)
 448                 key.SetType(BTRFS_KEY_TYPE_EXTENT_ITEM);
 449         key.SetObjectID(start);
 450         key.SetOffset(0);
 451
 452         TreeIterator iterator(fCurrentExtentTree, key);
 453         status_t status;
 454         while(true) {
 455                 status = iterator.GetNextEntry(&data);
 456                 key = iterator.Key();
 457                 if (status != B_OK) {
 458                         if (key.ObjectID() != Start())
 459                                 break;
 460                         // When we couldn't find the item and key has
 461                         // objectid == BlockGroup's objectID, because
 462                         // key's type < BLOCKGROUP_ITEM
 463                         continue;
 464                 }
 465
 466                 if (inverse == false) {
 467                         if ((flags & BTRFS_EXTENT_FLAG_DATA) != 0)
 468                                 extentSize = key.Offset();
 469                         insert = CachedExtent::Create(key.ObjectID(), extentSize, flags);
 470                         insert->item = (btrfs_extent*)data;
 471                 } else {
 472                         extentSize = key.ObjectID() - start;
 473                         insert = CachedExtent::Create(start, extentSize, flags);
 474                         free(data);             // free extent doesn't have data;
 475                 }
 476                 _InsertExtent(tree, insert);
 477                 start = key.ObjectID() + extentSize;
 478         }
 479
 480         if (inverse == true)
 481                 _InsertExtent(tree, start, End() - start, flags);
 482
 483         return B_OK;
 484 }
 485
 486
 487 status_t
 488 BlockGroup::_InsertExtent(CachedExtentTree* tree, uint64 start, uint64 length,
 489         uint64 flags)
 490 {
 491         CachedExtent* extent = CachedExtent::Create(start, length, flags);
 492         return _InsertExtent(tree, extent);
 493 }
 494
 495
 496 status_t
 497 BlockGroup::_InsertExtent(CachedExtentTree* tree, CachedExtent* extent)
 498 {
 499         if (extent->length == 0)
 500                 return B_BAD_VALUE;
 501
 502         status_t status = tree->AddExtent(extent);
 503         if (status != B_OK) {
 504                 return status;
 505         }
 506         return B_OK;
 507 }
 508
 509
 510 // ExtentAllocator
 511
 512
 513 ExtentAllocator::ExtentAllocator(Volume* volume)
 514         :
 515         fVolume(volume),
 516         fTree(NULL),
 517         fStart((uint64)-1),
 518         fEnd(0)
 519 {
 520         fTree = new(std::nothrow) CachedExtentTree(TreeDefinition());
 521 }
 522
 523
 524 ExtentAllocator::~ExtentAllocator()
 525 {
 526         delete fTree;
 527         fTree = NULL;
 528 }
 529
 530
 531 status_t
 532 ExtentAllocator::_LoadExtentTree(uint64 flags)
 533 {
 534         TRACE("ExtentAllocator::_LoadExtentTree() flags: %" B_PRIu64 "\n", flags);
 535         BlockGroup blockGroup(fVolume->ExtentTree());
 536         status_t status = blockGroup.Initialize(flags);
 537         if (status != B_OK)
 538                 return status;
 539
 540         for (int i = 0; i < BTRFS_NUM_ROOT_BACKUPS; i++) {
 541                 uint64 extentRootAddr =
 542                         fVolume->SuperBlock().backup_roots[i].ExtentRoot();
 543                 if (extentRootAddr == 0)
 544                         continue;       // new device has 0 root address
 545
 546                 status = blockGroup.SetExtentTree(extentRootAddr);
 547                 if (status != B_OK)
 548                         return status;
 549                 status = blockGroup.LoadExtent(fTree, false);
 550                 if (status != B_OK)
 551                         return status;
 552         }
 553
 554         if (fTree->IsEmpty())   // 4 backup roots is 0
 555                 return B_OK;
 556
 557         uint64 lowerBound = blockGroup.Start();
 558         uint64 upperBound = blockGroup.End();
 559         status = fTree->FillFreeExtents(lowerBound, upperBound);
 560         if (status != B_OK) {
 561                 ERROR("ExtentAllocator::_LoadExtentTree() could not fill free extents"
 562                         "start %" B_PRIu64 " end %" B_PRIu64 "\n", lowerBound,
 563                         upperBound);
 564                 return status;
 565         }
 566
 567         if (fStart > lowerBound)
 568                 fStart = lowerBound;
 569         if (fEnd < upperBound)
 570                 fEnd = upperBound;
 571         return B_OK;
 572 }
 573
 574
 575 status_t
 576 ExtentAllocator::Initialize()
 577 {
 578         TRACE("ExtentAllocator::Initialize()\n");
 579         if (fTree == NULL)
 580                 return B_NO_MEMORY;
 581
 582         status_t status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_DATA);
 583         if (status != B_OK) {
 584                 ERROR("ExtentAllocator:: could not load exent tree (data)\n");
 585                 return status;
 586         }
 587
 588         status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_SYSTEM);
 589         if (status != B_OK) {
 590                 ERROR("ExtentAllocator:: could not load exent tree (system)\n");
 591                 return status;
 592         }
 593
 594         status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_METADATA);
 595         if (status != B_OK) {
 596                 ERROR("ExtentAllocator:: could not load exent tree (metadata)\n");
 597                 return status;
 598         }
 599
 600         fTree->DumpInOrder();
 601         return B_OK;
 602 }
 603
 604
 605 /* Allocate extent that
 606  * startwith or after "start" and has size >= "size"
 607  * For now the allocating strategy is "first fit"
 608  */
 609 status_t
 610 ExtentAllocator::_Allocate(uint64& found, uint64 start, uint64 size,
 611         uint64 type)
 612 {
 613         TRACE("ExtentAllocator::_Allocate() start %" B_PRIu64 " size %" B_PRIu64 " type %"
 614                 B_PRIu64 "\n", start, size, type);
 615         CachedExtent* chosen;
 616         status_t status;
 617         while(true) {
 618                 status = fTree->FindNext(&chosen, start, size, type);
 619                 if (status != B_OK)
 620                         return status;
 621
 622                 if (TreeDefinition().Compare(start, chosen) == 0) {
 623                         if (chosen->End() - start >= size) {
 624                                 // if covered and have enough space for allocating
 625                                 break;
 626                         }
 627                         start = chosen->End();  // set new start and retry
 628                 } else
 629                         start = chosen->offset;
 630         }
 631
 632         TRACE("ExtentAllocator::_Allocate() found %" B_PRIu64 "\n", start);
 633         chosen = CachedExtent::Create(start, size,
 634                 type | BTRFS_EXTENT_FLAG_ALLOCATED);
 635         status = fTree->AddExtent(chosen);
 636         if (status != B_OK)
 637                 return status;
 638
 639         found = start;
 640         return B_OK;
 641 }
 642
 643
 644 // Allocate block for metadata
 645 // flags is BLOCKGROUP's flags
 646 status_t
 647 ExtentAllocator::AllocateTreeBlock(uint64& found, uint64 start, uint64 flags)
 648 {
 649         // TODO: implement more features here with flags, e.g DUP, RAID, etc
 650
 651         BlockGroup blockGroup(fVolume->ExtentTree());
 652         status_t status = blockGroup.Initialize(flags);
 653         if (status != B_OK)
 654                 return status;
 655         if (start == (uint64)-1)
 656                 start = blockGroup.Start();
 657
 658         // normalize inputs
 659         uint64 remainder = start % fVolume->BlockSize();
 660         if (remainder != 0)
 661                 start += fVolume->BlockSize() - remainder;
 662
 663         status = _Allocate(found, start, fVolume->BlockSize(),
 664                 BTRFS_EXTENT_FLAG_TREE_BLOCK);
 665         if (status != B_OK)
 666                 return status;
 667
 668         // check here because tree block locate in 2 blockgroups (system and
 669         // metadata), and there might be a case one can get over the limit.
 670         if (found >= blockGroup.End())
 671                 return B_BAD_DATA;
 672         return B_OK;
 673 }
 674
 675
 676 // Allocate block for file data
 677 status_t
 678 ExtentAllocator::AllocateDataBlock(uint64& found, uint64 size, uint64 start,
 679         uint64 flags)
 680 {
 681         // TODO: implement more features here with flags, e.g DUP, RAID, etc
 682
 683         if (start == (uint64)-1) {
 684                 BlockGroup blockGroup(fVolume->ExtentTree());
 685                 status_t status = blockGroup.Initialize(flags);
 686                 if (status != B_OK)
 687                         return status;
 688                 start = blockGroup.Start();
 689         }
 690
 691         // normalize inputs
 692         uint64 remainder = start % fVolume->SectorSize();
 693         if (remainder != 0)
 694                 start += fVolume->SectorSize() - remainder;
 695         size = size / fVolume->SectorSize() * fVolume->SectorSize();
 696
 697         return _Allocate(found, start, size, BTRFS_EXTENT_FLAG_DATA);
 698 }