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