1/* 2 * Copyright 2017, Ch��� V�� Gia Hy, cvghy116@gmail.com. 3 * Copyright 2011, J��r��me Duval, korli@users.berlios.de. 4 * Copyright 2001-2010, Axel D��rfler, axeld@pinc-software.de. 5 * This file may be used under the terms of the MIT License. 6 */ 7 8 9//! BTree implementation 10 11 12#include "BTree.h" 13#include "Journal.h" 14 15 16//#define TRACE_BTRFS 17#ifdef TRACE_BTRFS 18# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x) 19#else 20# define TRACE(x...) ; 21#endif 22# define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x) 23 24 25BTree::Node::Node(Volume* volume) 26 : 27 fNode(NULL), 28 fVolume(volume), 29 fBlockNumber(0), 30 fWritable(false) 31{ 32} 33 34 35BTree::Node::Node(Volume* volume, off_t block) 36 : 37 fNode(NULL), 38 fVolume(volume), 39 fBlockNumber(0), 40 fWritable(false) 41{ 42 SetTo(block); 43} 44 45 46BTree::Node::~Node() 47{ 48 Unset(); 49} 50 51 52void 53BTree::Node::Unset() 54{ 55 if (fNode != NULL) { 56 block_cache_put(fVolume->BlockCache(), fBlockNumber); 57 fNode = NULL; 58 } 59} 60 61 62void 63BTree::Node::SetTo(off_t block) 64{ 65 Unset(); 66 fBlockNumber = block; 67 fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block); 68} 69 70 71void 72BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty) 73{ 74 Unset(); 75 fBlockNumber = block; 76 fWritable = true; 77 if (empty) { 78 fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(), 79 block, transactionId); 80 } else { 81 fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(), 82 block, transactionId); 83 } 84} 85 86 87status_t 88BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) 89 const 90{ 91 // binary search for item slot in a node 92 int entrySize = sizeof(btrfs_entry); 93 if (Level() != 0) { 94 // internal node 95 entrySize = sizeof(btrfs_index); 96 } 97 98 int high = ItemCount(); 99 int low = 0, mid = 0, comp = 0; 100 uint8* base = (uint8*)fNode + sizeof(btrfs_header); 101 const btrfs_key* other; 102 while (low < high) { 103 mid = (low + high) / 2; 104 other = (const btrfs_key*)(base + mid * entrySize); 105 comp = key.Compare(*other); 106 if (comp < 0) 107 high = mid; 108 else if (comp > 0) 109 low = mid + 1; 110 else { 111 *slot = mid; 112 return B_OK; // if key is in node 113 } 114 } 115 116 // |--item1--|--item2--|--item3--|--etc--| 117 // m-1 m m+1 118 // k : comp < 0 119 // k : comp > 0 120 if (type == BTREE_BACKWARD && comp < 0) 121 mid--; 122 else if (type == BTREE_FORWARD && comp > 0) 123 mid++; 124 125 if (type == BTREE_EXACT || mid < 0) 126 return B_ENTRY_NOT_FOUND; 127 128 *slot = mid; 129 TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n", 130 *slot, comp); 131 return B_OK; 132} 133 134 135int 136BTree::Node::_CalculateSpace(uint32 from, uint32 to, uint8 type) const 137{ 138 if (to < from || to >= ItemCount()) 139 return 0; 140 141 if (Level() != 0) 142 return sizeof(btrfs_index) * (to - from + 1); 143 144 uint32 result = 0; 145 if ((type & 1) == 1) { 146 result += sizeof(btrfs_entry) * (to - from + 1); 147 } 148 if ((type & 2) == 2) { 149 result += Item(from)->Offset() + Item(from)->Size() 150 - Item(to)->Offset(); 151 } 152 153 return result; 154} 155 156 157int 158BTree::Node::SpaceUsed() const 159{ 160 if (Level() == 0) 161 return _CalculateSpace(0, ItemCount() - 1, 3); 162 return _CalculateSpace(0, ItemCount() - 1, 0); 163} 164 165 166int 167BTree::Node::SpaceLeft() const 168{ 169 return fVolume->BlockSize() - SpaceUsed() - sizeof(btrfs_header); 170} 171 172 173void 174BTree::Node::_Copy(const Node* origin, uint32 at, uint32 from, uint32 to, 175 int length) const 176{ 177 TRACE("Node::_Copy() at: %d from: %d to: %d length: %d\n", 178 at, from, to, length); 179 180 if (Level() == 0) { 181 memcpy(Item(at), origin->Item(from), origin->_CalculateSpace(from, to)); 182 // Item offset of copied node must be changed to get the 183 // item data offset correctly. length can be zero 184 // but let it there doesn't harm anything. 185 for (uint32 i = at; i - at <= to - from; ++i) 186 Item(i)->SetOffset(Item(i)->Offset() - length); 187 188 memcpy(ItemData(at + to - from), origin->ItemData(to), 189 origin->_CalculateSpace(from, to, 2)); 190 } else { 191 memcpy(Index(at), origin->Index(from), 192 origin->_CalculateSpace(from, to)); 193 } 194} 195 196 197status_t 198BTree::Node::_SpaceCheck(int length) const 199{ 200 // this is a little bit weird here because we can't find 201 // any suitable error code 202 if (length < 0 && abs(length) >= SpaceUsed()) 203 return B_DIRECTORY_NOT_EMPTY; // not enough data to delete 204 if (length > 0 && length >= SpaceLeft()) 205 return B_DEVICE_FULL; // no spare space 206 return B_OK; 207} 208 209 210status_t 211BTree::Node::Copy(const Node* origin, uint32 start, uint32 end, int length) 212 const 213{ 214 status_t status = origin->_SpaceCheck(length); 215 if (status != B_OK) 216 return status; 217 218 memcpy(fNode, origin->fNode, sizeof(btrfs_header)); 219 if (length == 0) { 220 // like removing [0, start - 1] and keeping [start, end] 221 length = -origin->_CalculateSpace(0, start - 1, 2); 222 _Copy(origin, 0, start, end, length); 223 } else if (length < 0) { 224 // removing all items in [start, end] 225 if (start > 0) 226 _Copy(origin, 0, 0, start - 1, 0); // <-- [start,... 227 if (end + 1 < origin->ItemCount()) { 228 // ..., end] --> 229 // we only care data size 230 length += origin->_CalculateSpace(start, end); 231 _Copy(origin, start, end + 1, origin->ItemCount() - 1, length); 232 } 233 } else { 234 // inserting in [start, end] - make a hole for later 235 if (start > 0) 236 _Copy(origin, 0, 0, start - 1, 0); 237 if (start < origin->ItemCount()) { 238 length -= origin->_CalculateSpace(start, end); 239 _Copy(origin, end + 1, start, origin->ItemCount() - 1, length); 240 } 241 } 242 243 return B_OK; 244} 245 246 247status_t 248BTree::Node::MoveEntries(uint32 start, uint32 end, int length) const 249{ 250 status_t status = _SpaceCheck(length); 251 if (status != B_OK || length == 0/*B_OK*/) 252 return status; 253 254 int entrySize = sizeof(btrfs_entry); 255 if (Level() != 0) 256 entrySize = sizeof(btrfs_index); 257 258 uint8* base = (uint8*)fNode + sizeof(btrfs_header); 259 end++; 260 if (length < 0) { 261 // removing [start, end] 262 TRACE("Node::MoveEntries() removing ... start %" B_PRIu32 " end %" 263 B_PRIu32 " length %i\n", start, end, length); 264 length += _CalculateSpace(start, end - 1); 265 } else { 266 // length > 0 267 // inserting into [start, end] - make room for later 268 TRACE("Node::MoveEntries() inserting ... start %" B_PRIu32 " end %" 269 B_PRIu32 " length %i\n", start, end, length); 270 length -= _CalculateSpace(start, end - 1); 271 uint32 tmp = start; 272 start = end; 273 end = tmp; 274 } 275 276 if (end >= ItemCount()) 277 return B_OK; 278 279 int dataSize = _CalculateSpace(end, ItemCount() - 1, 2); 280 // moving items/block pointers 281 memmove(base + start * entrySize, base + end * entrySize, 282 _CalculateSpace(end, ItemCount() - 1)); 283 if (Level() == 0) { 284 // moving item data 285 int num = start - end; 286 for (uint32 i = start; i < ItemCount() + num; ++i) 287 Item(i)->SetOffset(Item(i)->Offset() - length); 288 289 memmove(ItemData(ItemCount() - 1) - length, ItemData(ItemCount() - 1), 290 dataSize); 291 } 292 293 return B_OK; 294} 295 296 297// #pragma mark - BTree::Path implementation 298 299 300BTree::Path::Path(BTree* tree) 301 : 302 fTree(tree) 303{ 304 for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) { 305 fNodes[i] = NULL; 306 fSlots[i] = 0; 307 } 308} 309 310 311BTree::Path::~Path() 312{ 313 for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) { 314 delete fNodes[i]; 315 fNodes[i] = NULL; 316 fSlots[i] = 0; 317 } 318} 319 320 321BTree::Node* 322BTree::Path::GetNode(int level, int* _slot) const 323{ 324 if (_slot != NULL) 325 *_slot = fSlots[level]; 326 return fNodes[level]; 327} 328 329 330BTree::Node* 331BTree::Path::SetNode(off_t block, int slot) 332{ 333 Node node(fTree->SystemVolume(), block); 334 return SetNode(&node, slot); 335} 336 337 338BTree::Node* 339BTree::Path::SetNode(const Node* node, int slot) 340{ 341 uint8 level = node->Level(); 342 if (fNodes[level] == NULL) { 343 fNodes[level] = new Node(fTree->SystemVolume(), node->BlockNum()); 344 if (fNodes[level] == NULL) 345 return NULL; 346 } else 347 fNodes[level]->SetTo(node->BlockNum()); 348 349 if (slot == -1) 350 fSlots[level] = fNodes[level]->ItemCount() - 1; 351 else 352 fSlots[level] = slot; 353 return fNodes[level]; 354} 355 356 357int 358BTree::Path::Move(int level, int step) 359{ 360 fSlots[level] += step; 361 if (fSlots[level] < 0) 362 return -1; 363 if (fSlots[level] >= fNodes[level]->ItemCount()) 364 return 1; 365 return 0; 366} 367 368 369status_t 370BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size, 371 uint32* _offset) 372{ 373 BTree::Node* leaf = fNodes[0]; 374 if (slot < 0 || slot >= leaf->ItemCount()) 375 return B_ENTRY_NOT_FOUND; 376 377 if (_key != NULL) 378 *_key = leaf->Item(slot)->key; 379 380 uint32 itemSize = leaf->Item(slot)->Size(); 381 if (_value != NULL) { 382 *_value = malloc(itemSize); 383 if (*_value == NULL) 384 return B_NO_MEMORY; 385 386 memcpy(*_value, leaf->ItemData(slot), itemSize); 387 } 388 389 if (_size != NULL) 390 *_size = itemSize; 391 392 if (_offset != NULL) 393 *_offset = leaf->Item(slot)->Offset(); 394 395 return B_OK; 396} 397 398 399status_t 400BTree::Path::SetEntry(int slot, const btrfs_entry& entry, void* value) 401{ 402 if (slot < 0) 403 return B_ENTRY_NOT_FOUND; 404 405 memcpy(fNodes[0]->Item(slot), &entry, sizeof(btrfs_entry)); 406 memcpy(fNodes[0]->ItemData(slot), value, entry.Size()); 407 return B_OK; 408} 409 410 411status_t 412BTree::Path::CopyOnWrite(Transaction& transaction, int level, uint32 start, 413 int num, int length) 414{ 415 Node* node = fNodes[level]; 416 if (node == NULL) 417 return B_BAD_VALUE; 418 419 status_t status; 420 if (transaction.HasBlock(node->BlockNum())) { 421 // cow-ed block can not be cow-ed again 422 status = node->MoveEntries(start, start + num - 1, length); 423 if (status != B_OK) 424 return status; 425 426 node->SetGeneration(transaction.SystemID()); 427 if (length < 0) 428 node->SetItemCount(node->ItemCount() - num); 429 else if (length > 0) 430 node->SetItemCount(node->ItemCount() + num); 431 432 return B_OK; 433 } 434 435 uint64 address; 436 fsblock_t block; 437 status = fTree->SystemVolume()->GetNewBlock(address, block); 438 if (status != B_OK) 439 return status; 440 441 fNodes[level] = new(std::nothrow) BTree::Node(fTree->SystemVolume()); 442 if (fNodes[level] == NULL) 443 return B_NO_MEMORY; 444 445 fNodes[level]->SetToWritable(block, transaction.ID(), true); 446 447 status = fNodes[level]->Copy(node, start, start + num - 1, length); 448 if (status != B_OK) 449 return status; 450 451 fNodes[level]->SetGeneration(transaction.SystemID()); 452 fNodes[level]->SetLogicalAddress(address); 453 if (length < 0) 454 fNodes[level]->SetItemCount(node->ItemCount() - num); 455 else if (length > 0) 456 fNodes[level]->SetItemCount(node->ItemCount() + num); 457 else 458 fNodes[level]->SetItemCount(num); 459 460 // change pointer of this node in parent 461 int parentSlot; 462 Node* parentNode = GetNode(level + 1, &parentSlot); 463 if (parentNode != NULL) 464 parentNode->Index(parentSlot)->SetLogicalAddress(address); 465 466 if (level == fTree->RootLevel()) 467 fTree->SetRoot(fNodes[level]); 468 469 delete node; 470 return B_OK; 471} 472 473 474status_t 475BTree::Path::InternalCopy(Transaction& transaction, int level) 476{ 477 if (abs(level) >= fTree->RootLevel()) 478 return B_OK; 479 480 TRACE("Path::InternalCopy() level %i\n", level); 481 int from, to; 482 if (level > 0) { 483 from = level; 484 to = fTree->RootLevel(); 485 } else { 486 487 488 from = 0; 489 to = abs(level); 490 } 491 492 Node* node = NULL; 493 status_t status; 494 while (from <= to) { 495 node = fNodes[from]; 496 status = CopyOnWrite(transaction, from, 0, node->ItemCount(), 0); 497 from++; 498 if (status != B_OK) 499 return status; 500 } 501 502 return B_OK; 503} 504 505 506// #pragma mark - BTree implementation 507 508 509BTree::BTree(Volume* volume) 510 : 511 fRootBlock(0), 512 fRootLevel(0), 513 fVolume(volume) 514{ 515 mutex_init(&fIteratorLock, "btrfs b+tree iterator"); 516} 517 518 519BTree::BTree(Volume* volume, btrfs_stream* stream) 520 : 521 fRootBlock(0), 522 fRootLevel(0), 523 fVolume(volume) 524{ 525 mutex_init(&fIteratorLock, "btrfs b+tree iterator"); 526} 527 528 529BTree::BTree(Volume* volume, fsblock_t rootBlock) 530 : 531 fRootBlock(rootBlock), 532 fVolume(volume) 533{ 534 mutex_init(&fIteratorLock, "btrfs b+tree iterator"); 535} 536 537 538BTree::~BTree() 539{ 540 // if there are any TreeIterators left, we need to stop them 541 // (can happen when the tree's inode gets deleted while 542 // traversing the tree - a TreeIterator doesn't lock the inode) 543 mutex_lock(&fIteratorLock); 544 545 SinglyLinkedList<TreeIterator>::Iterator iterator 546 = fIterators.GetIterator(); 547 while (iterator.HasNext()) 548 iterator.Next()->Stop(); 549 mutex_destroy(&fIteratorLock); 550} 551 552 553int32 554btrfs_key::Compare(const btrfs_key& key) const 555{ 556 if (ObjectID() > key.ObjectID()) 557 return 1; 558 if (ObjectID() < key.ObjectID()) 559 return -1; 560 if (Type() > key.Type()) 561 return 1; 562 if (Type() < key.Type()) 563 return -1; 564 if (Offset() > key.Offset()) 565 return 1; 566 if (Offset() < key.Offset()) 567 return -1; 568 return 0; 569} 570 571 572status_t 573BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key) 574 const 575{ 576 TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %" 577 B_PRId64 " \n", key.ObjectID(), key.Type(), key.Offset()); 578 fsblock_t physicalBlock = fRootBlock; 579 Node node(fVolume, physicalBlock); 580 int slot; 581 status_t status = B_OK; 582 583 while (node.Level() != 0) { 584 TRACE("BTree::Traverse() level %d count %d\n", node.Level(), 585 node.ItemCount()); 586 status = node.SearchSlot(key, &slot, BTREE_BACKWARD); 587 if (status != B_OK) 588 return status; 589 if (path->SetNode(&node, slot) == NULL) 590 return B_NO_MEMORY; 591 592 TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot); 593 594 status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(), 595 physicalBlock); 596 if (status != B_OK) { 597 ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n", 598 node.Index(slot)->LogicalAddress()); 599 return status; 600 } 601 node.SetTo(physicalBlock); 602 } 603 604 TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount()); 605 status = node.SearchSlot(key, &slot, type); 606 if (status != B_OK) 607 return status; 608 if (path->SetNode(&node, slot) == NULL) 609 return B_NO_MEMORY; 610 611 TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n", 612 node.Item(slot)->Offset(), node.Item(slot)->Size()); 613 return slot; 614} 615 616 617status_t 618BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size, 619 uint32* _offset, btree_traversing type) const 620{ 621 status_t status = Traverse(type, path, wanted); 622 if (status < B_OK) 623 return status; 624 625 btrfs_key found; 626 status = path->GetCurrentEntry(&found, _value, _size, _offset); 627 if (status != B_OK) 628 return status; 629 630 if (found.Type() != wanted.Type() && wanted.Type() != BTRFS_KEY_TYPE_ANY) { 631 ERROR("Find() not found wanted: %" B_PRIu64 " %" B_PRIu8 " %" 632 B_PRIu64 " found: %" B_PRIu64 " %" B_PRIu8 " %" B_PRIu64 "\n", 633 wanted.ObjectID(), wanted.Type(), wanted.Offset(), found.ObjectID(), 634 found.Type(), found.Offset()); 635 return B_ENTRY_NOT_FOUND; 636 } 637 638 wanted = found; 639 return B_OK; 640} 641 642 643status_t 644BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size, 645 uint32* _offset) const 646{ 647 return _Find(path, key, _value, _size, _offset, BTREE_FORWARD); 648} 649 650 651status_t 652BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size, 653 uint32* _offset) const 654{ 655 return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD); 656} 657 658 659status_t 660BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size, 661 uint32* _offset) const 662{ 663 return _Find(path, key, _value, _size, _offset, BTREE_EXACT); 664} 665 666 667status_t 668BTree::MakeEntries(Transaction& transaction, Path* path, 669 const btrfs_key& startKey, int num, int length) 670{ 671 TRACE("BTree::MakeEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %" 672 B_PRIu64 ")\n", num, startKey.ObjectID(), startKey.Type(), 673 startKey.Offset()); 674 675 status_t status = Traverse(BTREE_FORWARD, path, startKey); 676 if (status < B_OK) 677 return status; 678 679 int slot = status; 680 status = path->InternalCopy(transaction, 1); 681 if (status != B_OK) 682 return status; 683 684 status = path->CopyOnWrite(transaction, 0, slot, num, length); 685 if (status == B_DEVICE_FULL) { 686 // TODO: push data or split node 687 return status; 688 } 689 690 if (status != B_OK) 691 return status; 692 return slot; 693} 694 695 696status_t 697BTree::InsertEntries(Transaction& transaction, Path* path, 698 btrfs_entry* entries, void** data, int num) 699{ 700 int totalLength = sizeof(btrfs_entry) * num; 701 for (int i = 0; i < num; i++) 702 totalLength += entries[i].Size(); 703 704 status_t slot = MakeEntries(transaction, path, entries[0].key, num, 705 totalLength); 706 if (slot < B_OK) 707 return slot; 708 709 uint32 upperLimit; 710 if (slot > 0) { 711 path->GetEntry(slot - 1, NULL, NULL, NULL, &upperLimit); 712 } else 713 upperLimit = fVolume->BlockSize() - sizeof(btrfs_header); 714 715 TRACE("BTree::InsertEntries() num: %i upper limit %" B_PRIu32 "\n", num, 716 upperLimit); 717 for (int i = 0; i < num; i++) { 718 upperLimit -= entries[i].Size(); 719 entries[i].SetOffset(upperLimit); 720 path->SetEntry(slot + i, entries[i], data[i]); 721 } 722 723 return B_OK; 724} 725 726 727status_t 728BTree::RemoveEntries(Transaction& transaction, Path* path, 729 const btrfs_key& startKey, void** _data, int num) 730{ 731 TRACE("BTree::RemoveEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %" 732 B_PRIu64 ")\n", num, startKey.ObjectID(), startKey.Type(), 733 startKey.Offset()); 734 735 status_t status = Traverse(BTREE_EXACT, path, startKey); 736 if (status < B_OK) 737 return status; 738 739 int slot = status; 740 int length = -sizeof(btrfs_entry) * num; 741 for (int i = 0; i < num; i++) { 742 uint32 itemSize; 743 path->GetEntry(slot + i, NULL, &_data[i], &itemSize); 744 length -= itemSize; 745 } 746 747 status = path->InternalCopy(transaction, 1); 748 if (status != B_OK) 749 return status; 750 751 status = path->CopyOnWrite(transaction, 0, slot, num, length); 752 if (status == B_DIRECTORY_NOT_EMPTY) { 753 // TODO: merge node or push data 754 } 755 756 return status; 757} 758 759 760status_t 761BTree::PreviousLeaf(Path* path) const 762{ 763 // TODO: use Traverse() ??? 764 int level = 0; 765 int slot; 766 Node* node = NULL; 767 // iterate to the root until satisfy the condition 768 while (true) { 769 node = path->GetNode(level, &slot); 770 if (node == NULL || slot != 0) 771 break; 772 level++; 773 } 774 775 // the current leaf is already the left most leaf or 776 // path was not initialized 777 if (node == NULL) 778 return B_ENTRY_NOT_FOUND; 779 780 path->Move(level, BTREE_BACKWARD); 781 fsblock_t physicalBlock; 782 // change all nodes below this level and slot to the ending 783 do { 784 status_t status = fVolume->FindBlock( 785 node->Index(slot)->LogicalAddress(), physicalBlock); 786 if (status != B_OK) 787 return status; 788 789 node = path->SetNode(physicalBlock, -1); 790 if (node == NULL) 791 return B_NO_MEMORY; 792 slot = node->ItemCount() - 1; 793 level--; 794 } while (level != 0); 795 796 return B_OK; 797} 798 799 800status_t 801BTree::NextLeaf(Path* path) const 802{ 803 int level = 0; 804 int slot; 805 Node* node = NULL; 806 // iterate to the root until satisfy the condition 807 while (true) { 808 node = path->GetNode(level, &slot); 809 if (node == NULL || slot < node->ItemCount() - 1) 810 break; 811 level++; 812 } 813 814 // the current leaf is already the right most leaf or 815 // path was not initialized 816 if (node == NULL) 817 return B_ENTRY_NOT_FOUND; 818 819 path->Move(level, BTREE_FORWARD); 820 fsblock_t physicalBlock; 821 // change all nodes below this level and slot to the beginning 822 do { 823 status_t status = fVolume->FindBlock( 824 node->Index(slot)->LogicalAddress(), physicalBlock); 825 if (status != B_OK) 826 return status; 827 828 node = path->SetNode(physicalBlock, 0); 829 if (node == NULL) 830 return B_NO_MEMORY; 831 slot = 0; 832 level--; 833 } while (level != 0); 834 835 return B_OK; 836} 837 838 839status_t 840BTree::SetRoot(off_t logical, fsblock_t* block) 841{ 842 if (block != NULL) { 843 fRootBlock = *block; 844 } else { 845 if (fVolume->FindBlock(logical, fRootBlock) != B_OK) { 846 ERROR("SetRoot() unmapped block %" B_PRId64 " %" B_PRId64 "\n", 847 logical, fRootBlock); 848 return B_ERROR; 849 } 850 } 851 852 btrfs_header header; 853 read_pos(fVolume->Device(), fRootBlock * fVolume->BlockSize(), &header, 854 sizeof(btrfs_header)); 855 fRootLevel = header.Level(); 856 fLogicalRoot = header.LogicalAddress(); 857 return B_OK; 858} 859 860 861void 862BTree::SetRoot(Node* root) 863{ 864 fRootBlock = root->BlockNum(); 865 fLogicalRoot = root->LogicalAddress(); 866 fRootLevel = root->Level(); 867} 868 869 870void 871BTree::_AddIterator(TreeIterator* iterator) 872{ 873 MutexLocker _(fIteratorLock); 874 fIterators.Add(iterator); 875} 876 877 878void 879BTree::_RemoveIterator(TreeIterator* iterator) 880{ 881 MutexLocker _(fIteratorLock); 882 fIterators.Remove(iterator); 883} 884 885 886// #pragma mark - 887 888 889TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key) 890 : 891 fTree(tree), 892 fKey(key), 893 fIteratorStatus(B_NO_INIT) 894{ 895 tree->_AddIterator(this); 896 fPath = new(std::nothrow) BTree::Path(tree); 897 if (fPath == NULL) 898 fIteratorStatus = B_NO_MEMORY; 899} 900 901 902TreeIterator::~TreeIterator() 903{ 904 if (fTree) 905 fTree->_RemoveIterator(this); 906 907 delete fPath; 908 fPath = NULL; 909} 910 911 912void 913TreeIterator::Rewind(bool inverse) 914{ 915 if (inverse) 916 fKey.SetOffset(BTREE_END); 917 else 918 fKey.SetOffset(BTREE_BEGIN); 919 fIteratorStatus = B_NO_INIT; 920} 921 922 923status_t 924TreeIterator::_Traverse(btree_traversing direction) 925{ 926 status_t status = fTree->Traverse(direction, fPath, fKey); 927 if (status < B_OK) { 928 ERROR("TreeIterator::Traverse() Find failed\n"); 929 return status; 930 } 931 932 return (fIteratorStatus = B_OK); 933} 934 935 936status_t 937TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size, 938 uint32* _offset) 939{ 940 status_t status = B_OK; 941 if (fIteratorStatus == B_NO_INIT) { 942 status = _Traverse(type); 943 if (status != B_OK) 944 return status; 945 type = BTREE_EXACT; 946 } 947 948 if (fIteratorStatus != B_OK) 949 return fIteratorStatus; 950 951 int move = fPath->Move(0, type); 952 if (move > 0) 953 status = fTree->NextLeaf(fPath); 954 else if (move < 0) 955 status = fTree->PreviousLeaf(fPath); 956 if (status != B_OK) 957 return status; 958 959 btrfs_key found; 960 status = fPath->GetCurrentEntry(&found, _value, _size, _offset); 961 if (status != B_OK) 962 return status; 963 964 fKey.SetObjectID(found.ObjectID()); 965 fKey.SetOffset(found.Offset()); 966 if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY) 967 return B_ENTRY_NOT_FOUND; 968 969 return B_OK; 970} 971 972 973status_t 974TreeIterator::Find(const btrfs_key& key) 975{ 976 if (fIteratorStatus == B_INTERRUPTED) 977 return fIteratorStatus; 978 979 fKey = key; 980 fIteratorStatus = B_NO_INIT; 981 return B_OK; 982} 983 984 985void 986TreeIterator::Stop() 987{ 988 fTree = NULL; 989 fIteratorStatus = B_INTERRUPTED; 990} 991