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 (status != B_OK || (Flags() & flag) == flag) 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 extent 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 extent 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 extent 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 614 " type %" 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 } 699