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

   1 /*
   2  * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
   3  * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
   4  * This file may be used under the terms of the MIT License.
   5  */
   6
   7
   8 //! BTree implementation
   9
  10
  11 #include "BTree.h"
  12
  13
  14 //#define TRACE_BTRFS
  15 #ifdef TRACE_BTRFS
  16 #       define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
  17 #else
  18 #       define TRACE(x...) ;
  19 #endif
  20 #       define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
  21
  22
  23 BTree::Node::Node(Volume* volume)
  24         :
  25         fNode(NULL),
  26         fVolume(volume),
  27         fBlockNumber(0),
  28         fWritable(false)
  29 {
  30 }
  31
  32
  33 BTree::Node::Node(Volume* volume, off_t block)
  34         :
  35         fNode(NULL),
  36         fVolume(volume),
  37         fBlockNumber(0),
  38         fWritable(false)
  39 {
  40         SetTo(block);
  41 }
  42
  43
  44 BTree::Node::~Node()
  45 {
  46         Unset();
  47 }
  48
  49
  50 void
  51 BTree::Node::Keep()
  52 {
  53         fNode = NULL;
  54 }
  55
  56 void
  57 BTree::Node::Unset()
  58 {
  59         if (fNode != NULL) {
  60                 block_cache_put(fVolume->BlockCache(), fBlockNumber);
  61                 fNode = NULL;
  62         }
  63 }
  64
  65
  66 void
  67 BTree::Node::SetTo(off_t block)
  68 {
  69         Unset();
  70         fBlockNumber = block;
  71         fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
  72 }
  73
  74
  75 void
  76 BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
  77 {
  78         Unset();
  79         fBlockNumber = block;
  80         fWritable = true;
  81         if (empty) {
  82                 fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
  83                         block, transactionId);
  84         } else {
  85                 fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
  86                         block, transactionId);
  87         }
  88 }
  89
  90
  91 status_t
  92 BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
  93         const
  94 {
  95         //binary search for item slot in a node
  96         int entrySize = sizeof(btrfs_entry);
  97         if (Level() != 0) {
  98                 // internal node
  99                 entrySize = sizeof(btrfs_index);
 100         }
 101
 102         int high = ItemCount();
 103         int low = 0, mid = 0, comp = 0;
 104         uint8* base = (uint8*)fNode + sizeof(btrfs_header);
 105         const btrfs_key* other;
 106         while (low < high) {
 107                 mid = (low + high) / 2;
 108                 other = (const btrfs_key*)(base + mid * entrySize);
 109                 comp = key.Compare(*other);
 110                 if (comp < 0)
 111                         high = mid;
 112                 else if (comp > 0)
 113                         low = mid + 1;
 114                 else {
 115                         *slot = mid;
 116                         return B_OK;            //if key is in node
 117                 }
 118         }
 119
 120         // |--item1--|--item2--|--item3--|--etc--|
 121         //     m-1        m        m+1
 122         //           k                          : comp < 0
 123         //                     k                : comp > 0
 124         if (type == BTREE_BACKWARD) {
 125                 *slot = mid - 1;
 126                 if (comp > 0)
 127                         *slot = mid;
 128         } else if (type == BTREE_FORWARD) {
 129                 *slot = mid;
 130                 if (comp > 0)
 131                         *slot = mid + 1;
 132         }
 133
 134         if (type == BTREE_EXACT || *slot < 0)
 135                 return B_ENTRY_NOT_FOUND;
 136
 137         TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
 138                 *slot, comp);
 139         return B_OK;
 140 }
 141
 142
 143 /*
 144  * calculate used space except the header.
 145  * type is only for leaf node
 146  * type 1: only item space
 147  * type 2: only item data space
 148  * type 3: both type 1 and 2
 149  */
 150 int
 151 BTree::Node::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
 152 {
 153         if (to < from || to >= ItemCount())
 154                 return 0;
 155
 156         if (Level() != 0)
 157                 return sizeof(btrfs_index) * (to - from + 1);
 158
 159         uint32 result = 0;
 160         if ((type & 1) == 1) {
 161                 result += sizeof(btrfs_entry) * (to - from + 1);
 162         }
 163         if ((type & 2) == 2) {
 164                 result += Item(from)->Offset() + Item(from)->Size()
 165                         - Item(to)->Offset();
 166         }
 167
 168         return result;
 169 }
 170
 171
 172 int
 173 BTree::Node::SpaceUsed() const
 174 {
 175         if (Level() == 0)
 176                 return _CalculateSpace(0, ItemCount() - 1, 3);
 177         return _CalculateSpace(0, ItemCount() - 1, 0);
 178 }
 179
 180
 181 int
 182 BTree::Node::SpaceLeft() const
 183 {
 184         return fVolume->BlockSize() - SpaceUsed() - sizeof(btrfs_header);
 185 }
 186
 187
 188 status_t
 189 BTree::Node::_SpaceCheck(int length) const
 190 {
 191         // this is a little bit weird here because we can't find
 192         // any suitable error code
 193         if (length < 0 && std::abs(length) >= SpaceUsed())
 194                 return B_DIRECTORY_NOT_EMPTY;   // not enough data to delete
 195         if (length > 0 && length >= SpaceLeft())
 196                 return B_DEVICE_FULL;                   // no spare space
 197         return B_OK;
 198 }
 199
 200
 201 //      #pragma mark - BTree::Path implementation
 202
 203
 204 BTree::Path::Path(BTree* tree)
 205         :
 206         fTree(tree)
 207 {
 208         for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
 209                 fNodes[i] = NULL;
 210                 fSlots[i] = 0;
 211         }
 212 }
 213
 214
 215 BTree::Path::~Path()
 216 {
 217         for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
 218                 delete fNodes[i];
 219                 fNodes[i] = NULL;
 220                 fSlots[i] = 0;
 221         }
 222 }
 223
 224
 225 BTree::Node*
 226 BTree::Path::GetNode(int level, int* _slot) const
 227 {
 228         if (_slot != NULL)
 229                 *_slot = fSlots[level];
 230         return fNodes[level];
 231 }
 232
 233
 234 BTree::Node*
 235 BTree::Path::SetNode(off_t block, int slot)
 236 {
 237         Node node(fTree->SystemVolume(), block);
 238         return SetNode(&node, slot);
 239 }
 240
 241
 242 BTree::Node*
 243 BTree::Path::SetNode(const Node* node, int slot)
 244 {
 245         uint8 level = node->Level();
 246         if (fNodes[level] == NULL) {
 247                 fNodes[level] = new Node(fTree->SystemVolume(), node->BlockNum());
 248                 if (fNodes[level] == NULL)
 249                         return NULL;
 250         } else
 251                 fNodes[level]->SetTo(node->BlockNum());
 252
 253         if (slot == -1)
 254                 fSlots[level] = fNodes[level]->ItemCount() - 1;
 255         else
 256                 fSlots[level] = slot;
 257         return fNodes[level];
 258 }
 259
 260
 261 int
 262 BTree::Path::Move(int level, int step)
 263 {
 264         fSlots[level] += step;
 265         if (fSlots[level] < 0)
 266                 return -1;
 267         if (fSlots[level] >= fNodes[level]->ItemCount())
 268                 return 1;
 269         return 0;
 270 }
 271
 272
 273 status_t
 274 BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
 275         uint32* _offset)
 276 {
 277         BTree::Node* leaf = fNodes[0];
 278         if (slot < 0 || slot >= leaf->ItemCount())
 279                 return B_ENTRY_NOT_FOUND;
 280
 281         if (_key != NULL)
 282                 *_key = leaf->Item(slot)->key;
 283
 284         uint32 itemSize = leaf->Item(slot)->Size();
 285         if (_value != NULL) {
 286                 *_value = malloc(itemSize);
 287                 if (*_value == NULL)
 288                         return B_NO_MEMORY;
 289
 290                 memcpy(*_value, leaf->ItemData(slot), itemSize);
 291         }
 292
 293         if (_size != NULL)
 294                 *_size = itemSize;
 295
 296         if (_offset != NULL)
 297                 *_offset = leaf->Item(slot)->Offset();
 298
 299         return B_OK;
 300 }
 301
 302
 303 //      #pragma mark - BTree implementation
 304
 305
 306 BTree::BTree(Volume* volume)
 307         :
 308         fRootBlock(0),
 309         fVolume(volume)
 310 {
 311         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 312 }
 313
 314
 315 BTree::BTree(Volume* volume, btrfs_stream* stream)
 316         :
 317         fRootBlock(0),
 318         fVolume(volume)
 319 {
 320         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 321 }
 322
 323
 324 BTree::BTree(Volume* volume, fsblock_t rootBlock)
 325         :
 326         fRootBlock(rootBlock),
 327         fVolume(volume)
 328 {
 329         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 330 }
 331
 332
 333 BTree::~BTree()
 334 {
 335         // if there are any TreeIterators left, we need to stop them
 336         // (can happen when the tree's inode gets deleted while
 337         // traversing the tree - a TreeIterator doesn't lock the inode)
 338         mutex_lock(&fIteratorLock);
 339
 340         SinglyLinkedList<TreeIterator>::Iterator iterator
 341                 = fIterators.GetIterator();
 342         while (iterator.HasNext())
 343                 iterator.Next()->Stop();
 344         mutex_destroy(&fIteratorLock);
 345 }
 346
 347
 348 int32
 349 btrfs_key::Compare(const btrfs_key& key) const
 350 {
 351         if (ObjectID() > key.ObjectID())
 352                 return 1;
 353         if (ObjectID() < key.ObjectID())
 354                 return -1;
 355         if (Type() > key.Type())
 356                 return 1;
 357         if (Type() < key.Type())
 358                 return -1;
 359         if (Offset() > key.Offset())
 360                 return 1;
 361         if (Offset() < key.Offset())
 362                 return -1;
 363         return 0;
 364 }
 365
 366
 367 /* Traverse from root to fill in the path along way its finding.
 368  * Return current slot at leaf if successful.
 369  */
 370 status_t
 371 BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
 372         const
 373 {
 374         TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
 375                 B_PRId64 " \n", key.ObjectID(), key.Type(), key.Offset());
 376         fsblock_t physicalBlock = fRootBlock;
 377         Node node(fVolume, physicalBlock);
 378         int slot;
 379         status_t status = B_OK;
 380
 381         while (node.Level() != 0) {
 382                 TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
 383                         node.ItemCount());
 384                 status = node.SearchSlot(key, &slot, BTREE_BACKWARD);
 385                 if (status != B_OK)
 386                         return status;
 387                 if (path->SetNode(&node, slot) == NULL)
 388                         return B_NO_MEMORY;
 389
 390                 TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);
 391
 392                 status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
 393                                 physicalBlock);
 394                 if (status != B_OK) {
 395                         ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n",
 396                                 node.Index(slot)->LogicalAddress());
 397                         return status;
 398                 }
 399                 node.SetTo(physicalBlock);
 400         }
 401
 402         TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
 403         status = node.SearchSlot(key, &slot, type);
 404         if (status != B_OK)
 405                 return status;
 406         if (path->SetNode(&node, slot) == NULL)
 407                 return B_NO_MEMORY;
 408
 409         TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
 410                 node.Item(slot)->Offset(), node.Item(slot)->Size());
 411         return slot;
 412 }
 413
 414
 415 /*!     Searches the key in the tree, and stores the allocated found item in
 416         _value, if successful.
 417         Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
 418         It can also return other errors to indicate that something went wrong.
 419 */
 420 status_t
 421 BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
 422         uint32* _offset, btree_traversing type) const
 423 {
 424         status_t status = Traverse(type, path, wanted);
 425         if (status < B_OK)
 426                 return status;
 427
 428         btrfs_key found;
 429         status = path->GetCurrentEntry(&found, _value, _size, _offset);
 430         if (status != B_OK)
 431                 return status;
 432
 433         if (found.Type() != wanted.Type() && wanted.Type() != BTRFS_KEY_TYPE_ANY)
 434                 return B_ENTRY_NOT_FOUND;
 435
 436         wanted = found;
 437         return B_OK;
 438 }
 439
 440
 441 status_t
 442 BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
 443         uint32* _offset) const
 444 {
 445         return _Find(path, key, _value, _size, _offset, BTREE_FORWARD);
 446 }
 447
 448
 449 status_t
 450 BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
 451         uint32* _offset) const
 452 {
 453         return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD);
 454 }
 455
 456
 457 status_t
 458 BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
 459         uint32* _offset) const
 460 {
 461         return _Find(path, key, _value, _size, _offset, BTREE_EXACT);
 462 }
 463
 464
 465 status_t
 466 BTree::PreviousLeaf(Path* path) const
 467 {
 468         // TODO: use Traverse() ???
 469         int level = 0;
 470         int slot;
 471         Node* node = NULL;
 472         // iterate to the root until satisfy the condition
 473         while (true) {
 474                 node = path->GetNode(level, &slot);
 475                 if (node == NULL || slot != 0)
 476                         break;
 477                 level++;
 478         }
 479
 480         // the current leaf is already the left most leaf or
 481         // path was not initialized
 482         if (node == NULL)
 483                 return B_ENTRY_NOT_FOUND;
 484
 485         path->Move(level, BTREE_BACKWARD);
 486         fsblock_t physicalBlock;
 487         // change all nodes below this level and slot to the ending
 488         do {
 489                 status_t status = fVolume->FindBlock(
 490                         node->Index(slot)->LogicalAddress(), physicalBlock);
 491                 if (status != B_OK)
 492                         return status;
 493
 494                 node = path->SetNode(physicalBlock, -1);
 495                 if (node == NULL)
 496                         return B_NO_MEMORY;
 497                 slot = node->ItemCount() - 1;
 498                 level--;
 499         } while(level != 0);
 500
 501         return B_OK;
 502 }
 503
 504
 505 status_t
 506 BTree::NextLeaf(Path* path) const
 507 {
 508         int level = 0;
 509         int slot;
 510         Node* node = NULL;
 511         // iterate to the root until satisfy the condition
 512         while (true) {
 513                 node = path->GetNode(level, &slot);
 514                 if (node == NULL || slot < node->ItemCount() - 1)
 515                         break;
 516                 level++;
 517         }
 518
 519         // the current leaf is already the right most leaf or
 520         // path was not initialized
 521         if (node == NULL)
 522                 return B_ENTRY_NOT_FOUND;
 523
 524         path->Move(level, BTREE_FORWARD);
 525         fsblock_t physicalBlock;
 526         // change all nodes below this level and slot to the beginning
 527         do {
 528                 status_t status = fVolume->FindBlock(
 529                         node->Index(slot)->LogicalAddress(), physicalBlock);
 530                 if (status != B_OK)
 531                         return status;
 532
 533                 node = path->SetNode(physicalBlock, 0);
 534                 if (node == NULL)
 535                         return B_NO_MEMORY;
 536                 slot = 0;
 537                 level--;
 538         } while(level != 0);
 539
 540         return B_OK;
 541 }
 542
 543
 544 status_t
 545 BTree::SetRoot(off_t logical, fsblock_t* block)
 546 {
 547         if (block != NULL) {
 548                 fRootBlock = *block;
 549                 //TODO: mapping physical block -> logical address
 550         } else {
 551                 fLogicalRoot = logical;
 552                 if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
 553                         ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
 554                         return B_ERROR;
 555                 }
 556         }
 557         return B_OK;
 558 }
 559
 560
 561 void
 562 BTree::_AddIterator(TreeIterator* iterator)
 563 {
 564         MutexLocker _(fIteratorLock);
 565         fIterators.Add(iterator);
 566 }
 567
 568
 569 void
 570 BTree::_RemoveIterator(TreeIterator* iterator)
 571 {
 572         MutexLocker _(fIteratorLock);
 573         fIterators.Remove(iterator);
 574 }
 575
 576
 577 //      #pragma mark -
 578
 579
 580 TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
 581         :
 582         fTree(tree),
 583         fKey(key),
 584         fIteratorStatus(B_NO_INIT)
 585 {
 586         tree->_AddIterator(this);
 587         fPath = new(std::nothrow) BTree::Path(tree);
 588         if (fPath == NULL)
 589                 fIteratorStatus = B_NO_MEMORY;
 590 }
 591
 592
 593 TreeIterator::~TreeIterator()
 594 {
 595         if (fTree)
 596                 fTree->_RemoveIterator(this);
 597
 598         delete fPath;
 599         fPath = NULL;
 600 }
 601
 602
 603 void
 604 TreeIterator::Rewind(bool inverse)
 605 {
 606         if (inverse)
 607                 fKey.SetOffset(BTREE_END);
 608         else
 609                 fKey.SetOffset(BTREE_BEGIN);
 610         fIteratorStatus = B_NO_INIT;
 611 }
 612
 613
 614 /*!     Iterates through the tree in the specified direction.
 615 */
 616 status_t
 617 TreeIterator::_Traverse(btree_traversing direction)
 618 {
 619         status_t status = fTree->Traverse(direction, fPath, fKey);
 620         if (status < B_OK) {
 621                 ERROR("TreeIterator::Traverse() Find failed\n");
 622                 return status;
 623         }
 624
 625         return (fIteratorStatus = B_OK);
 626 }
 627
 628
 629 // Like GetEntry in BTree::Path but here we check the type and moving.
 630 status_t
 631 TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size,
 632         uint32* _offset)
 633 {
 634         status_t status;
 635         if (fIteratorStatus == B_NO_INIT) {
 636                 status = _Traverse(type);
 637                 if (status != B_OK)
 638                         return status;
 639                 type = BTREE_EXACT;
 640         }
 641
 642         if (fIteratorStatus != B_OK)
 643                 return fIteratorStatus;
 644
 645         int move = fPath->Move(0, type);
 646         if (move > 0)
 647                 status = fTree->NextLeaf(fPath);
 648         else if (move < 0)
 649                 status = fTree->PreviousLeaf(fPath);
 650         if (status != B_OK)
 651                 return status;
 652
 653         btrfs_key found;
 654         status = fPath->GetCurrentEntry(&found, _value, _size, _offset);
 655         if (status != B_OK)
 656                 return status;
 657
 658         fKey.SetObjectID(found.ObjectID());
 659         fKey.SetOffset(found.Offset());
 660         if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY)
 661                 return B_ENTRY_NOT_FOUND;
 662
 663         return B_OK;
 664 }
 665
 666
 667 /*!     just sets the current key in the iterator.
 668 */
 669 status_t
 670 TreeIterator::Find(const btrfs_key& key)
 671 {
 672         if (fIteratorStatus == B_INTERRUPTED)
 673                 return fIteratorStatus;
 674
 675         fKey = key;
 676         fIteratorStatus = B_NO_INIT;
 677         return B_OK;
 678 }
 679
 680
 681 void
 682 TreeIterator::Stop()
 683 {
 684         fTree = NULL;
 685         fIteratorStatus = B_INTERRUPTED;
 686 }