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         fCurrentSlot(0),
  29         fWritable(false)
  30 {
  31 }
  32
  33
  34 BTree::Node::Node(Volume* volume, off_t block)
  35         :
  36         fNode(NULL),
  37         fVolume(volume),
  38         fBlockNumber(0),
  39         fCurrentSlot(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::Keep()
  54 {
  55         fNode = NULL;
  56 }
  57
  58 void
  59 BTree::Node::Unset()
  60 {
  61         if (fNode != NULL) {
  62                 block_cache_put(fVolume->BlockCache(), fBlockNumber);
  63                 fNode = NULL;
  64         }
  65 }
  66
  67
  68 void
  69 BTree::Node::SetTo(off_t block)
  70 {
  71         Unset();
  72         fBlockNumber = block;
  73         fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
  74 }
  75
  76
  77 void
  78 BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
  79 {
  80         Unset();
  81         fBlockNumber = block;
  82         fWritable = true;
  83         if (empty) {
  84                 fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
  85                         block, transactionId);
  86         } else {
  87                 fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
  88                         block, transactionId);
  89         }
  90 }
  91
  92
  93 status_t
  94 BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
  95         const
  96 {
  97         //binary search for item slot in a node
  98         int entrySize = sizeof(btrfs_entry);
  99         if (Level() != 0) {
 100                 // internal node
 101                 entrySize = sizeof(btrfs_index);
 102         }
 103
 104         int high = ItemCount();
 105         int low = 0, mid = 0, comp = 0;
 106         uint8* base = (uint8*)fNode + sizeof(btrfs_header);
 107         const btrfs_key* other;
 108         while (low < high) {
 109                 mid = (low + high) / 2;
 110                 other = (const btrfs_key*)(base + mid * entrySize);
 111                 comp = key.Compare(*other);
 112                 if (comp < 0)
 113                         high = mid;
 114                 else if (comp > 0)
 115                         low = mid + 1;
 116                 else {
 117                         *slot = mid;
 118                         return B_OK;            //if key is in node
 119                 }
 120         }
 121
 122         // |--item1--|--item2--|--item3--|--etc--|
 123         //     m-1        m        m+1
 124         //           k                          : comp < 0
 125         //                     k                : comp > 0
 126         if (type == BTREE_BACKWARD) {
 127                 *slot = mid - 1;
 128                 if (comp > 0)
 129                         *slot = mid;
 130         } else if (type == BTREE_FORWARD) {
 131                 *slot = mid;
 132                 if (comp > 0)
 133                         *slot = mid + 1;
 134         }
 135
 136         if (type == BTREE_EXACT || *slot < 0)
 137                 return B_ENTRY_NOT_FOUND;
 138
 139         TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
 140                 *slot, comp);
 141         return B_OK;
 142 }
 143
 144
 145 //-pragma mark
 146
 147
 148 BTree::BTree(Volume* volume)
 149         :
 150         fRootBlock(0),
 151         fVolume(volume)
 152 {
 153         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 154 }
 155
 156
 157 BTree::BTree(Volume* volume, btrfs_stream* stream)
 158         :
 159         fRootBlock(0),
 160         fVolume(volume)
 161 {
 162         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 163 }
 164
 165
 166 BTree::BTree(Volume* volume, fsblock_t rootBlock)
 167         :
 168         fRootBlock(rootBlock),
 169         fVolume(volume)
 170 {
 171         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 172 }
 173
 174
 175 BTree::~BTree()
 176 {
 177         // if there are any TreeIterators left, we need to stop them
 178         // (can happen when the tree's inode gets deleted while
 179         // traversing the tree - a TreeIterator doesn't lock the inode)
 180         mutex_lock(&fIteratorLock);
 181
 182         SinglyLinkedList<TreeIterator>::Iterator iterator
 183                 = fIterators.GetIterator();
 184         while (iterator.HasNext())
 185                 iterator.Next()->Stop();
 186         mutex_destroy(&fIteratorLock);
 187 }
 188
 189
 190 int32
 191 btrfs_key::Compare(const btrfs_key& key) const
 192 {
 193         if (ObjectID() > key.ObjectID())
 194                 return 1;
 195         if (ObjectID() < key.ObjectID())
 196                 return -1;
 197         if (Type() > key.Type())
 198                 return 1;
 199         if (Type() < key.Type())
 200                 return -1;
 201         if (Offset() > key.Offset())
 202                 return 1;
 203         if (Offset() < key.Offset())
 204                 return -1;
 205         return 0;
 206 }
 207
 208
 209 /*!     Searches the key in the tree, and stores the allocated found item in
 210         _value, if successful.
 211         Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
 212         It can also return other errors to indicate that something went wrong.
 213 */
 214 status_t
 215 BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
 216         bool read, btree_traversing type)
 217 {
 218         TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
 219                 key.ObjectID(), key.Type(), key.Offset());
 220         BTree::Node node(fVolume, fRootBlock);
 221         int slot, ret;
 222         fsblock_t physicalBlock;
 223
 224         while (node.Level() != 0) {
 225                 TRACE("Find() level %d\n", node.Level());
 226                 ret = node.SearchSlot(key, &slot, BTREE_BACKWARD);
 227                 if (ret != B_OK)
 228                         return ret;
 229                 TRACE("Find() getting index %" B_PRIu32 "\n", slot);
 230
 231                 if (fVolume->FindBlock(node.Index(slot)->LogicalAddress(), physicalBlock)
 232                         != B_OK) {
 233                         ERROR("Find() unmapped block %" B_PRId64 "\n",
 234                                 node.Index(slot)->LogicalAddress());
 235                         return B_ERROR;
 236                 }
 237                 node.SetTo(physicalBlock);
 238         }
 239
 240         TRACE("Find() dump count %" B_PRId32 "\n", node.ItemCount());
 241         ret = node.SearchSlot(key, &slot, type);
 242         if ((slot >= node.ItemCount() || node.Item(slot)->key.Type() != key.Type())
 243                         && read == true
 244                 || ret != B_OK) {
 245                 TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n", key.Offset(),
 246                         key.ObjectID());
 247                 return B_ENTRY_NOT_FOUND;
 248         }
 249
 250         if (read == true) {
 251                 TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
 252                         node.Item(slot)->Offset(), node.Item(slot)->Size());
 253
 254                 if (_value != NULL) {
 255                         *_value = malloc(node.Item(slot)->Size());
 256                         memcpy(*_value, node.ItemData(slot),
 257                                 node.Item(slot)->Size());
 258                         key.SetOffset(node.Item(slot)->key.Offset());
 259                         key.SetObjectID(node.Item(slot)->key.ObjectID());
 260                         if (_size != NULL)
 261                                 *_size = node.Item(slot)->Size();
 262                 }
 263         } else {
 264                 *_value = (void*)&slot;
 265         }
 266         return B_OK;
 267 }
 268
 269
 270 status_t
 271 BTree::FindNext(btrfs_key& key, void** _value, uint32* _size, bool read)
 272 {
 273         return _Find(key, _value, _size, read, BTREE_FORWARD);
 274 }
 275
 276
 277 status_t
 278 BTree::FindPrevious(btrfs_key& key, void** _value, uint32* _size, bool read)
 279 {
 280         return _Find(key, _value, _size, read, BTREE_BACKWARD);
 281 }
 282
 283
 284 status_t
 285 BTree::FindExact(btrfs_key& key, void** _value, uint32* _size, bool read)
 286 {
 287         return _Find(key, _value, _size, read, BTREE_EXACT);
 288 }
 289
 290
 291 status_t
 292 BTree::SetRoot(off_t logical, fsblock_t* block)
 293 {
 294         if (block != NULL) {
 295                 fRootBlock = *block;
 296                 //TODO: mapping physical block -> logical address
 297         } else {
 298                 fLogicalRoot = logical;
 299                 if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
 300                         ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
 301                         return B_ERROR;
 302                 }
 303         }
 304         return B_OK;
 305 }
 306
 307
 308 void
 309 BTree::_AddIterator(TreeIterator* iterator)
 310 {
 311         MutexLocker _(fIteratorLock);
 312         fIterators.Add(iterator);
 313 }
 314
 315
 316 void
 317 BTree::_RemoveIterator(TreeIterator* iterator)
 318 {
 319         MutexLocker _(fIteratorLock);
 320         fIterators.Remove(iterator);
 321 }
 322
 323
 324 //      #pragma mark -
 325
 326
 327 TreeIterator::TreeIterator(BTree* tree, btrfs_key& key)
 328         :
 329         fTree(tree),
 330         fCurrentKey(key)
 331 {
 332         Rewind();
 333         tree->_AddIterator(this);
 334 }
 335
 336
 337 TreeIterator::~TreeIterator()
 338 {
 339         if (fTree)
 340                 fTree->_RemoveIterator(this);
 341 }
 342
 343
 344 /*!     Iterates through the tree in the specified direction.
 345 */
 346 status_t
 347 TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
 348         void** value, uint32* size)
 349 {
 350         if (fTree == NULL)
 351                 return B_INTERRUPTED;
 352
 353         fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
 354         status_t status = fTree->_Find(fCurrentKey, value, size,
 355                 true, direction);
 356         if (status != B_OK) {
 357                 TRACE("TreeIterator::Traverse() Find failed\n");
 358                 return B_ENTRY_NOT_FOUND;
 359         }
 360
 361         return B_OK;
 362 }
 363
 364
 365 /*!     just sets the current key in the iterator.
 366 */
 367 status_t
 368 TreeIterator::Find(btrfs_key& key)
 369 {
 370         if (fTree == NULL)
 371                 return B_INTERRUPTED;
 372         fCurrentKey = key;
 373         return B_OK;
 374 }
 375
 376
 377 void
 378 TreeIterator::Stop()
 379 {
 380         fTree = NULL;
 381 }