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
SystemVolume()100 Volume* SystemVolume() const { return fVolume; }
101 status_t SetRoot(off_t logical, fsblock_t* block);
102 void SetRoot(Node* root);
RootBlock()103 fsblock_t RootBlock() const { return fRootBlock; }
LogicalRoot()104 off_t LogicalRoot() const { return fLogicalRoot; }
RootLevel()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
LogicalAddress()140 uint64 LogicalAddress() const
141 { return fNode->header.LogicalAddress(); }
Flags()142 uint64 Flags() const
143 { return fNode->header.Flags(); }
Generation()144 uint64 Generation() const
145 { return fNode->header.Generation(); }
Owner()146 uint64 Owner() const
147 { return fNode->header.Owner(); }
ItemCount()148 uint32 ItemCount() const
149 { return fNode->header.ItemCount(); }
Level()150 uint8 Level() const
151 { return fNode->header.Level(); }
SetLogicalAddress(uint64 address)152 void SetLogicalAddress(uint64 address)
153 { fNode->header.SetLogicalAddress(address); }
SetGeneration(uint64 generation)154 void SetGeneration(uint64 generation)
155 { fNode->header.SetGeneration(generation); }
SetItemCount(uint32 itemCount)156 void SetItemCount(uint32 itemCount)
157 { fNode->header.SetItemCount(itemCount); }
158
Index(uint32 i)159 btrfs_index* Index(uint32 i) const
160 { return &fNode->index[i]; }
161
Item(uint32 i)162 btrfs_entry* Item(uint32 i) const
163 { return &fNode->entries[i]; }
ItemData(uint32 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
BlockNum()176 off_t BlockNum() const { return fBlockNumber;}
IsWritable()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);
Tree()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
Tree()296 BTree* Tree() const { return fTree; }
Key()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
GetCurrentEntry(btrfs_key * _key,void ** _value,uint32 * _size,uint32 * _offset)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
GetNextEntry(void ** _value,uint32 * _size,uint32 * _offset)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
GetPreviousEntry(void ** _value,uint32 * _size,uint32 * _offset)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