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 #ifndef B_TREE_H 8 #define B_TREE_H 9 10 11 #include "btrfs.h" 12 #include "Volume.h" 13 14 15 #define BTREE_NULL -1LL 16 #define BTREE_FREE -2LL 17 18 #define BTRFS_MAX_TREE_DEPTH 8 19 20 21 //! Tree traversal direction status, used by functions manipulating trees 22 enum btree_traversing { 23 BTREE_FORWARD = 1, 24 BTREE_EXACT = 0, 25 BTREE_BACKWARD = -1, 26 27 BTREE_BEGIN = 0, 28 BTREE_END = -1 29 }; 30 31 32 class Transaction; 33 34 35 // #pragma mark - in-memory structures 36 37 38 template<class T> class Stack; 39 class TreeIterator; 40 41 42 // needed for searching (utilizing a stack) 43 struct node_and_key { 44 off_t nodeOffset; 45 uint16 keyIndex; 46 }; 47 48 49 class BTree { 50 public: 51 class Path; 52 class Node; 53 54 public: 55 BTree(Volume* volume); 56 BTree(Volume* volume, 57 btrfs_stream* stream); 58 BTree(Volume* volume, 59 fsblock_t rootBlock); 60 ~BTree(); 61 62 status_t FindExact(Path* path, btrfs_key& key, 63 void** _value, uint32* _size = NULL, 64 uint32* _offset = NULL) const; 65 status_t FindNext(Path* path, btrfs_key& key, 66 void** _value, uint32* _size = NULL, 67 uint32* _offset = NULL) const; 68 status_t FindPrevious(Path* path, btrfs_key& key, 69 void** _value, uint32* _size = NULL, 70 uint32* _offset = NULL) const; 71 72 /*! Traverse from the root to fill in the path along the way 73 * \return Current slot at leaf if successful, error code (out of memory, 74 * no such entry, unmapped block) otherwise 75 */ 76 status_t Traverse(btree_traversing type, Path* path, 77 const btrfs_key& key) const; 78 79 status_t PreviousLeaf(Path* path) const; 80 status_t NextLeaf(Path* path) const; 81 /*! Insert consecutive empty entries 82 * \param num Number of entries to be inserted 83 * \param startKey Slot to start inserting 84 * \return Starting slot on success, error code otherwise 85 */ 86 status_t MakeEntries(Transaction& transaction, 87 Path* path, const btrfs_key& startKey, 88 int num, int length); 89 //! MakeEntries and fill in them 90 status_t InsertEntries(Transaction& transaction, 91 Path* path, btrfs_entry* entries, 92 void** data, int num); 93 /*! Like MakeEntries, but here entries are removed. 94 * \param _data Location to store removed data 95 */ 96 status_t RemoveEntries(Transaction& transaction, 97 Path* path, const btrfs_key& startKey, 98 void** _data, int num); 99 100 Volume* SystemVolume() const { return fVolume; } 101 status_t SetRoot(off_t logical, fsblock_t* block); 102 void SetRoot(Node* root); 103 fsblock_t RootBlock() const { return fRootBlock; } 104 off_t LogicalRoot() const { return fLogicalRoot; } 105 uint8 RootLevel() const { return fRootLevel; } 106 107 private: 108 BTree(const BTree& other); 109 BTree& operator=(const BTree& other); 110 // no implementation 111 112 /*! Search for key in the tree 113 * \param _value Location to store item if search successful 114 * \return B_OK when key found, error code otherwise 115 */ 116 status_t _Find(Path* path, btrfs_key& key, 117 void** _value, uint32* _size, 118 uint32* _offset, btree_traversing type) 119 const; 120 void _AddIterator(TreeIterator* iterator); 121 void _RemoveIterator(TreeIterator* iterator); 122 private: 123 friend class TreeIterator; 124 125 fsblock_t fRootBlock; 126 off_t fLogicalRoot; 127 uint8 fRootLevel; 128 Volume* fVolume; 129 mutex fIteratorLock; 130 SinglyLinkedList<TreeIterator> fIterators; 131 132 public: 133 class Node { 134 public: 135 Node(Volume* volume); 136 Node(Volume* volume, off_t block); 137 ~Node(); 138 139 140 uint64 LogicalAddress() const 141 { return fNode->header.LogicalAddress(); } 142 uint64 Flags() const 143 { return fNode->header.Flags(); } 144 uint64 Generation() const 145 { return fNode->header.Generation(); } 146 uint64 Owner() const 147 { return fNode->header.Owner(); } 148 uint32 ItemCount() const 149 { return fNode->header.ItemCount(); } 150 uint8 Level() const 151 { return fNode->header.Level(); } 152 void SetLogicalAddress(uint64 address) 153 { fNode->header.SetLogicalAddress(address); } 154 void SetGeneration(uint64 generation) 155 { fNode->header.SetGeneration(generation); } 156 void SetItemCount(uint32 itemCount) 157 { fNode->header.SetItemCount(itemCount); } 158 159 btrfs_index* Index(uint32 i) const 160 { return &fNode->index[i]; } 161 162 btrfs_entry* Item(uint32 i) const 163 { return &fNode->entries[i]; } 164 uint8* ItemData(uint32 i) const 165 { return (uint8*)Item(0) + Item(i)->Offset(); } 166 167 //! Reset Node and decrements ref-count to the Node's block 168 void Unset(); 169 170 //! Load node at block offset from disk 171 void SetTo(off_t block); 172 void SetToWritable(off_t block, int32 transactionId, bool empty); 173 int SpaceUsed() const; 174 int SpaceLeft() const; 175 176 off_t BlockNum() const { return fBlockNumber;} 177 bool IsWritable() const { return fWritable; } 178 179 /*! 180 * copy node header, items and items data 181 * length is size to insert/remove 182 * if node is a internal node, length isnt used 183 * length = 0: Copy a whole 184 * length < 0: removing 185 * length > 0: inserting 186 */ 187 status_t Copy(const Node* origin, uint32 start, uint32 end, 188 int length) const; 189 //! Shift data in items between start and end by offset length 190 status_t MoveEntries(uint32 start, uint32 end, int length) const; 191 192 //! Searches for item slot in the node 193 status_t SearchSlot(const btrfs_key& key, int* slot, 194 btree_traversing type) const; 195 private: 196 Node(const Node&); 197 Node& operator=(const Node&); 198 // no implementation 199 200 //! Internal function used by Copy 201 void _Copy(const Node* origin, uint32 at, uint32 from, uint32 to, 202 int length) const; 203 status_t _SpaceCheck(int length) const; 204 205 /*! 206 * calculate used space except the header. 207 * type is only for leaf node 208 * type 1: only item space 209 * type 2: only item data space 210 * type 3: both type 1 and 2 211 */ 212 int _CalculateSpace(uint32 from, uint32 to, uint8 type = 1) const; 213 214 btrfs_stream* fNode; 215 Volume* fVolume; 216 off_t fBlockNumber; 217 bool fWritable; 218 }; 219 220 221 class Path { 222 public: 223 Path(BTree* tree); 224 ~Path(); 225 226 227 Node* GetNode(int level, int* _slot = NULL) const; 228 Node* SetNode(off_t block, int slot); 229 Node* SetNode(const Node* node, int slot); 230 status_t GetCurrentEntry(btrfs_key* _key, void** _value, 231 uint32* _size = NULL, uint32* _offset = NULL); 232 status_t GetEntry(int slot, btrfs_key* _key, void** _value, 233 uint32* _size = NULL, uint32* _offset = NULL); 234 status_t SetEntry(int slot, const btrfs_entry& entry, void* value); 235 236 int Move(int level, int step); 237 238 239 /*! 240 * Allocate and copy block and do all the changes that it can. 241 * for now, we only copy-on-write tree block, 242 * file data is "nocow" by default. 243 * 244 * o parent o 245 * | ===> \ 246 * o x o 247 */ 248 status_t CopyOnWrite(Transaction& transaction, int level, 249 uint32 start, int num, int length); 250 /*! 251 * Copy-On-Write all internal nodes start from a specific level. 252 * level > 0: to root 253 * level <= 0: to leaf 254 * 255 * path cow-path path cow-path 256 * ================================================= 257 * root cow-root root level < 0 258 * | | | 259 * n1 cow-n1 ...______ 260 * | | | \ 261 * n2 cow-n2 n1 cow-n1 262 * | / | | 263 * ...____/ n2 cow-n2 264 * | | | 265 * leaf level > 0 leaf cow-leaf 266 */ 267 status_t InternalCopy(Transaction& transaction, int level); 268 BTree* Tree() const { return fTree; } 269 private: 270 Path(const Path&); 271 Path operator=(const Path&); 272 private: 273 Node* fNodes[BTRFS_MAX_TREE_DEPTH]; 274 int fSlots[BTRFS_MAX_TREE_DEPTH]; 275 BTree* fTree; 276 }; 277 278 }; // class BTree 279 280 281 class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> { 282 public: 283 TreeIterator(BTree* tree, const btrfs_key& key); 284 ~TreeIterator(); 285 286 void Rewind(bool inverse = false); 287 //! Set current key in the iterator 288 status_t Find(const btrfs_key& key); 289 status_t GetNextEntry(void** _value, 290 uint32* _size = NULL, 291 uint32* _offset = NULL); 292 status_t GetPreviousEntry(void** _value, 293 uint32* _size = NULL, 294 uint32* _offset = NULL); 295 296 BTree* Tree() const { return fTree; } 297 btrfs_key Key() const { return fKey; } 298 299 private: 300 friend class BTree; 301 302 //! Iterates through the tree in the specified direction 303 status_t _Traverse(btree_traversing direction); 304 status_t _Find(btree_traversing type, btrfs_key& key, 305 void** _value); 306 //! Like GetEntry in BTree::Path but checks type and moving 307 status_t _GetEntry(btree_traversing type, void** _value, 308 uint32* _size, uint32* _offset); 309 // called by BTree 310 void Stop(); 311 312 private: 313 BTree* fTree; 314 BTree::Path* fPath; 315 btrfs_key fKey; 316 status_t fIteratorStatus; 317 }; 318 319 320 // #pragma mark - BTree::Path inline functions 321 322 323 inline status_t 324 BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size, 325 uint32* _offset) 326 { 327 return GetEntry(fSlots[0], _key, _value, _size, _offset); 328 } 329 330 331 // #pragma mark - TreeIterator inline functions 332 333 334 inline status_t 335 TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset) 336 { 337 return _GetEntry(BTREE_FORWARD, _value, _size, _offset); 338 } 339 340 341 inline status_t 342 TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset) 343 { 344 return _GetEntry(BTREE_BACKWARD, _value, _size, _offset); 345 } 346 347 348 #endif // B_TREE_H 349