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 25 BTree::Node::Node(Volume* volume) 26 : 27 fNode(NULL), 28 fVolume(volume), 29 fBlockNumber(0), 30 fWritable(false) 31 { 32 } 33 34 35 BTree::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 46 BTree::Node::~Node() 47 { 48 Unset(); 49 } 50 51 52 void 53 BTree::Node::Unset() 54 { 55 if (fNode != NULL) { 56 block_cache_put(fVolume->BlockCache(), fBlockNumber); 57 fNode = NULL; 58 } 59 } 60 61 62 void 63 BTree::Node::SetTo(off_t block) 64 { 65 Unset(); 66 fBlockNumber = block; 67 fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block); 68 } 69 70 71 void 72 BTree::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 87 status_t 88 BTree::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 135 int 136 BTree::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 157 int 158 BTree::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 166 int 167 BTree::Node::SpaceLeft() const 168 { 169 return fVolume->BlockSize() - SpaceUsed() - sizeof(btrfs_header); 170 } 171 172 173 void 174 BTree::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 197 status_t 198 BTree::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 210 status_t 211 BTree::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 247 status_t 248 BTree::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 300 BTree::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 311 BTree::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 321 BTree::Node* 322 BTree::Path::GetNode(int level, int* _slot) const 323 { 324 if (_slot != NULL) 325 *_slot = fSlots[level]; 326 return fNodes[level]; 327 } 328 329 330 BTree::Node* 331 BTree::Path::SetNode(off_t block, int slot) 332 { 333 Node node(fTree->SystemVolume(), block); 334 return SetNode(&node, slot); 335 } 336 337 338 BTree::Node* 339 BTree::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 357 int 358 BTree::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 369 status_t 370 BTree::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 399 status_t 400 BTree::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 411 status_t 412 BTree::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 474 status_t 475 BTree::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 509 BTree::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 519 BTree::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 529 BTree::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 538 BTree::~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 553 int32 554 btrfs_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 572 status_t 573 BTree::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 617 status_t 618 BTree::_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 643 status_t 644 BTree::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 651 status_t 652 BTree::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 659 status_t 660 BTree::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 667 status_t 668 BTree::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 696 status_t 697 BTree::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 727 status_t 728 BTree::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 760 status_t 761 BTree::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 800 status_t 801 BTree::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 839 status_t 840 BTree::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 861 void 862 BTree::SetRoot(Node* root) 863 { 864 fRootBlock = root->BlockNum(); 865 fLogicalRoot = root->LogicalAddress(); 866 fRootLevel = root->Level(); 867 } 868 869 870 void 871 BTree::_AddIterator(TreeIterator* iterator) 872 { 873 MutexLocker _(fIteratorLock); 874 fIterators.Add(iterator); 875 } 876 877 878 void 879 BTree::_RemoveIterator(TreeIterator* iterator) 880 { 881 MutexLocker _(fIteratorLock); 882 fIterators.Remove(iterator); 883 } 884 885 886 // #pragma mark - 887 888 889 TreeIterator::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 902 TreeIterator::~TreeIterator() 903 { 904 if (fTree) 905 fTree->_RemoveIterator(this); 906 907 delete fPath; 908 fPath = NULL; 909 } 910 911 912 void 913 TreeIterator::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 923 status_t 924 TreeIterator::_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 936 status_t 937 TreeIterator::_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 973 status_t 974 TreeIterator::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 985 void 986 TreeIterator::Stop() 987 { 988 fTree = NULL; 989 fIteratorStatus = B_INTERRUPTED; 990 } 991