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

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