Ticket #13612: btrfs.patchset3_2

File btrfs.patchset3_2, 75.1 KB (added by hyche, 7 years ago)

lot of changes since the old one

Line 
1From 40ed6c7fbb43a0c5f7093a5871da342571745d09 Mon Sep 17 00:00:00 2001
2From: hyche <cvghy116@gmail.com>
3Date: Sat, 5 Aug 2017 20:23:52 +0700
4Subject: [PATCH 1/7] AVLTree: forward LeftMost and RightMost method from
5 AVLTreeBase
6
7---
8 headers/private/kernel/util/AVLTree.h | 27 +++++++++++++++++++++++++++
9 1 file changed, 27 insertions(+)
10
11diff --git a/headers/private/kernel/util/AVLTree.h b/headers/private/kernel/util/AVLTree.h
12index 76d6b25..f0e27f8 100644
13--- a/headers/private/kernel/util/AVLTree.h
14+++ b/headers/private/kernel/util/AVLTree.h
15@@ -47,6 +47,9 @@ public:
16 Value* Previous(Value* value) const;
17 Value* Next(Value* value) const;
18
19+ Value* LeftMost(Value* value) const;
20+ Value* RightMost(Value* value) const;
21+
22 inline Iterator GetIterator();
23 inline ConstIterator GetIterator() const;
24
25@@ -256,6 +259,30 @@ AVLTree<Definition>::Next(Value* value) const
26
27
28 template<typename Definition>
29+inline typename AVLTree<Definition>::Value*
30+AVLTree<Definition>::LeftMost(Value* value) const
31+{
32+ if (value == NULL)
33+ return NULL;
34+
35+ AVLTreeNode* node = fTree.LeftMost(_GetAVLTreeNode(value));
36+ return node != NULL ? _GetValue(node) : NULL;
37+}
38+
39+
40+template<typename Definition>
41+inline typename AVLTree<Definition>::Value*
42+AVLTree<Definition>::RightMost(Value* value) const
43+{
44+ if (value == NULL)
45+ return NULL;
46+
47+ AVLTreeNode* node = fTree.RightMost(_GetAVLTreeNode(value));
48+ return node != NULL ? _GetValue(node) : NULL;
49+}
50+
51+
52+template<typename Definition>
53 inline typename AVLTree<Definition>::Iterator
54 AVLTree<Definition>::GetIterator()
55 {
56--
572.7.4
58
59
60From 96e68b0130569ce234f4455b0894777c89490715 Mon Sep 17 00:00:00 2001
61From: hyche <cvghy116@gmail.com>
62Date: Sat, 5 Aug 2017 20:28:00 +0700
63Subject: [PATCH 2/7] BTRFS: Fix node search slot
64
65* Not handle traversing type correctly (looks for the graph).
66* Reorder the codes because *slot is uninitialized if type is BTREE_EXACT.
67* Incorrect return type: int32 -> status_t
68---
69 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 36 ++++++++++++++++---------
70 src/add-ons/kernel/file_systems/btrfs/BTree.h | 4 +--
71 2 files changed, 25 insertions(+), 15 deletions(-)
72
73diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
74index fec0dee..56813a0 100644
75--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
76+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
77@@ -90,8 +90,9 @@ BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
78 }
79
80
81-int32
82-BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
83+status_t
84+BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
85+ const
86 {
87 //binary search for item slot in a node
88 int entrySize = sizeof(btrfs_entry);
89@@ -100,14 +101,13 @@ BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
90 entrySize = sizeof(btrfs_index);
91 }
92
93- int low = 0;
94 int high = ItemCount();
95- int mid, comp;
96- int base = sizeof(btrfs_header);
97+ int low = 0, mid = 0, comp = 0;
98+ uint8* base = (uint8*)fNode + sizeof(btrfs_header);
99 const btrfs_key* other;
100 while (low < high) {
101 mid = (low + high) / 2;
102- other = (const btrfs_key*)((uint8*)fNode + base + mid * entrySize);
103+ other = (const btrfs_key*)(base + mid * entrySize);
104 comp = key.Compare(*other);
105 if (comp < 0)
106 high = mid;
107@@ -119,15 +119,25 @@ BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
108 }
109 }
110
111- TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
112- *slot, comp);
113- if (type == BTREE_BACKWARD)
114- *slot = low - 1;
115- else if (type == BTREE_FORWARD)
116- *slot = low;
117+ // |--item1--|--item2--|--item3--|--etc--|
118+ // m-1 m m+1
119+ // k : comp < 0
120+ // k : comp > 0
121+ if (type == BTREE_BACKWARD) {
122+ *slot = mid - 1;
123+ if (comp > 0)
124+ *slot = mid;
125+ } else if (type == BTREE_FORWARD) {
126+ *slot = mid;
127+ if (comp > 0)
128+ *slot = mid + 1;
129+ }
130
131- if (*slot < 0 || type == BTREE_EXACT)
132+ if (type == BTREE_EXACT || *slot < 0)
133 return B_ENTRY_NOT_FOUND;
134+
135+ TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
136+ *slot, comp);
137 return B_OK;
138 }
139
140diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
141index eebd132..2fa8837 100644
142--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
143+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
144@@ -119,8 +119,8 @@ public:
145 off_t BlockNum() const { return fBlockNumber;}
146 bool IsWritable() const { return fWritable; }
147
148- int32 SearchSlot(const btrfs_key& key, int* slot,
149- btree_traversing type) const;
150+ status_t SearchSlot(const btrfs_key& key, int* slot,
151+ btree_traversing type) const;
152 private:
153 Node(const Node&);
154 Node& operator=(const Node&);
155--
1562.7.4
157
158
159From a70ea75097a0c3e38d4a36592d590f82bd9e7383 Mon Sep 17 00:00:00 2001
160From: hyche <cvghy116@gmail.com>
161Date: Sat, 12 Aug 2017 16:50:07 +0700
162Subject: [PATCH 3/7] BTRFS: Fix mismatched type of item size (should be
163 uint32), and ObjectID of first subvolume when lookup directory (described in
164 commit bd2dab1)
165
166---
167 .../kernel/file_systems/btrfs/Attribute.cpp | 8 ++++----
168 src/add-ons/kernel/file_systems/btrfs/Attribute.h | 2 +-
169 .../file_systems/btrfs/AttributeIterator.cpp | 2 +-
170 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 10 ++++-----
171 src/add-ons/kernel/file_systems/btrfs/BTree.h | 24 +++++++++++-----------
172 .../file_systems/btrfs/DirectoryIterator.cpp | 11 +++++-----
173 src/add-ons/kernel/file_systems/btrfs/Inode.cpp | 4 ++--
174 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 2 +-
175 8 files changed, 32 insertions(+), 31 deletions(-)
176
177diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
178index ecb25ac..ddda28d 100644
179--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
180+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
181@@ -88,7 +88,7 @@ Attribute::Stat(struct stat& stat)
182
183 size_t nameLength = strlen(fName);
184 btrfs_dir_entry* entries;
185- size_t length;
186+ uint32 length;
187 status_t status = _Lookup(fName, nameLength, &entries, &length);
188 if (status < B_OK)
189 return status;
190@@ -116,7 +116,7 @@ Attribute::Read(attr_cookie* cookie, off_t pos, uint8* buffer, size_t* _length)
191
192 size_t nameLength = strlen(fName);
193 btrfs_dir_entry* entries;
194- size_t length;
195+ uint32 length;
196 status_t status = _Lookup(fName, nameLength, &entries, &length);
197 if (status < B_OK)
198 return status;
199@@ -144,7 +144,7 @@ Attribute::Read(attr_cookie* cookie, off_t pos, uint8* buffer, size_t* _length)
200
201 status_t
202 Attribute::_Lookup(const char* name, size_t nameLength,
203- btrfs_dir_entry** _entries, size_t* _length)
204+ btrfs_dir_entry** _entries, uint32* _length)
205 {
206 uint32 hash = calculate_crc((uint32)~1, (uint8*)name, nameLength);
207 struct btrfs_key key;
208@@ -153,7 +153,7 @@ Attribute::_Lookup(const char* name, size_t nameLength,
209 key.SetOffset(hash);
210
211 btrfs_dir_entry* entries;
212- size_t length;
213+ uint32 length;
214 status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
215 (void**)&entries, &length);
216 if (status != B_OK) {
217diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.h b/src/add-ons/kernel/file_systems/btrfs/Attribute.h
218index 7236673..ebbb3e9 100644
219--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.h
220+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.h
221@@ -39,7 +39,7 @@ public:
222 private:
223 status_t _Lookup(const char* name, size_t nameLength,
224 btrfs_dir_entry** entries = NULL,
225- size_t* length = NULL);
226+ uint32* length = NULL);
227 status_t _FindEntry(btrfs_dir_entry* entries,
228 size_t length, const char* name,
229 size_t nameLength,
230diff --git a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
231index 3b67e83..f453a11 100644
232--- a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
233+++ b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
234@@ -48,7 +48,7 @@ AttributeIterator::GetNext(char* name, size_t* _nameLength)
235 {
236 btrfs_key key;
237 btrfs_dir_entry* entries;
238- size_t entries_length;
239+ uint32 entries_length;
240 status_t status = fIterator->GetPreviousEntry(key, (void**)&entries,
241 &entries_length);
242 if (status != B_OK)
243diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
244index 56813a0..726aa84 100644
245--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
246+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
247@@ -212,7 +212,7 @@ btrfs_key::Compare(const btrfs_key& key) const
248 It can also return other errors to indicate that something went wrong.
249 */
250 status_t
251-BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
252+BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
253 bool read, btree_traversing type)
254 {
255 TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
256@@ -268,21 +268,21 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
257
258
259 status_t
260-BTree::FindNext(btrfs_key& key, void** _value, size_t* _size, bool read)
261+BTree::FindNext(btrfs_key& key, void** _value, uint32* _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+BTree::FindPrevious(btrfs_key& key, void** _value, uint32* _size, bool read)
270 {
271 return _Find(key, _value, _size, read, BTREE_BACKWARD);
272 }
273
274
275 status_t
276-BTree::FindExact(btrfs_key& key, void** _value, size_t* _size, bool read)
277+BTree::FindExact(btrfs_key& key, void** _value, uint32* _size, bool read)
278 {
279 return _Find(key, _value, _size, read, BTREE_EXACT);
280 }
281@@ -345,7 +345,7 @@ TreeIterator::~TreeIterator()
282 */
283 status_t
284 TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
285- void** value, size_t* size)
286+ void** value, uint32* size)
287 {
288 if (fTree == NULL)
289 return B_INTERRUPTED;
290diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
291index 2fa8837..5a40fea 100644
292--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
293+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
294@@ -3,8 +3,8 @@
295 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
296 * This file may be used under the terms of the MIT License.
297 */
298-#ifndef B_PLUS_TREE_H
299-#define B_PLUS_TREE_H
300+#ifndef B_TREE_H
301+#define B_TREE_H
302
303
304 #include "btrfs.h"
305@@ -50,11 +50,11 @@ public:
306 fsblock_t rootBlock);
307 ~BTree();
308 status_t FindExact(btrfs_key& key, void** value,
309- size_t* size = NULL, bool read = true);
310+ uint32* size = NULL, bool read = true);
311 status_t FindNext(btrfs_key& key, void** value,
312- size_t* size = NULL, bool read = true);
313+ uint32* size = NULL, bool read = true);
314 status_t FindPrevious(btrfs_key& key, void** value,
315- size_t* size = NULL, bool read = true);
316+ uint32* size = NULL, bool read = true);
317
318 Volume* SystemVolume() const { return fVolume; }
319
320@@ -67,7 +67,7 @@ private:
321 BTree& operator=(const BTree& other);
322 // no implementation
323
324- status_t _Find(btrfs_key& key, void** value, size_t* size,
325+ status_t _Find(btrfs_key& key, void** value, uint32* size,
326 bool read, btree_traversing type);
327 void _AddIterator(TreeIterator* iterator);
328 void _RemoveIterator(TreeIterator* iterator);
329@@ -153,14 +153,14 @@ public:
330
331 status_t Traverse(btree_traversing direction,
332 btrfs_key& key, void** value,
333- size_t* size = NULL);
334+ uint32* size = NULL);
335 status_t Find(btrfs_key& key);
336
337 status_t Rewind();
338 status_t GetNextEntry(btrfs_key& key, void** value,
339- size_t* size = NULL);
340+ uint32* size = NULL);
341 status_t GetPreviousEntry(btrfs_key& key, void** value,
342- size_t* size = NULL);
343+ uint32* size = NULL);
344
345 BTree* Tree() const { return fTree; }
346
347@@ -188,7 +188,7 @@ TreeIterator::Rewind()
348
349
350 inline status_t
351-TreeIterator::GetNextEntry(btrfs_key& key, void** value, size_t* size)
352+TreeIterator::GetNextEntry(btrfs_key& key, void** value, uint32* size)
353 {
354 return Traverse(BTREE_FORWARD, key, value, size);
355 }
356@@ -196,10 +196,10 @@ TreeIterator::GetNextEntry(btrfs_key& key, void** value, size_t* size)
357
358 inline status_t
359 TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
360- size_t* size)
361+ uint32* size)
362 {
363 return Traverse(BTREE_BACKWARD, key, value, size);
364 }
365
366
367-#endif // B_PLUS_TREE_H
368+#endif // B_TREE_H
369diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
370index b19dabf..4f9a1b7 100644
371--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
372+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
373@@ -33,7 +33,8 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
374
375 DirectoryIterator::~DirectoryIterator()
376 {
377- delete fIterator;
378+ if (fIterator != NULL)
379+ delete fIterator;
380 }
381
382
383@@ -61,7 +62,7 @@ DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
384 *_nameLength = 1;
385 strlcpy(name, ".", *_nameLength + 1);
386 fOffset = 2;
387- if (fInode->ID() == BTRFS_OBJECT_ID_CHUNK_TREE) {
388+ if (fInode->ID() == BTRFS_FIRST_SUBVOLUME) {
389 *_id = fInode->ID();
390 return B_OK;
391 }
392@@ -70,7 +71,7 @@ DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
393
394 btrfs_key key;
395 btrfs_dir_entry* entries;
396- size_t entries_length;
397+ uint32 entries_length;
398 status_t status = fIterator->GetNextEntry(key, (void**)&entries,
399 &entries_length);
400 if (status != B_OK)
401@@ -110,7 +111,7 @@ DirectoryIterator::Lookup(const char* name, size_t nameLength, ino_t* _id)
402 {
403 if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0) {
404 if (strcmp(name, ".") == 0
405- || fInode->ID() == BTRFS_OBJECT_ID_CHUNK_TREE) {
406+ || fInode->ID() == BTRFS_FIRST_SUBVOLUME) {
407 *_id = fInode->ID();
408 return B_OK;
409 }
410@@ -124,7 +125,7 @@ DirectoryIterator::Lookup(const char* name, size_t nameLength, ino_t* _id)
411 key.SetOffset(hash);
412
413 btrfs_dir_entry* entries;
414- size_t length;
415+ uint32 length;
416 status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
417 (void**)&entries, &length);
418 if (status != B_OK) {
419diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
420index ef66d34..a2e7bb8 100644
421--- a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
422+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
423@@ -167,7 +167,7 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
424 search_key.SetObjectID(fID);
425 search_key.SetOffset(pos + 1);
426
427- size_t item_size;
428+ uint32 item_size;
429 btrfs_extent_data* extent_data;
430 status_t status = fVolume->FSTree()->FindPrevious(search_key,
431 (void**)&extent_data, &item_size);
432@@ -222,7 +222,7 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
433
434 int status;
435 ssize_t offset = 0;
436- size_t inline_size = item_size - 13;
437+ uint32 inline_size = item_size - 13;
438 bool headerRead = false;
439
440 TRACE("Inode::ReadAt(%" B_PRIdINO ") diff %" B_PRIdOFF " size %"
441diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
442index 561a102..159f67e 100644
443--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
444+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
445@@ -486,7 +486,7 @@ Volume::FindBlock(off_t logical, off_t& physical)
446 search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
447 search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
448 btrfs_chunk* chunk;
449- size_t chunk_length;
450+ uint32 chunk_length;
451 status_t status = fChunkTree->FindPrevious(search_key, (void**)&chunk,
452 &chunk_length);
453 if (status != B_OK)
454--
4552.7.4
456
457
458From 9696e266582ca783618e39d178090b2528a76029 Mon Sep 17 00:00:00 2001
459From: hyche <cvghy116@gmail.com>
460Date: Wed, 16 Aug 2017 20:56:09 +0700
461Subject: [PATCH 4/7] BTRFS: Node now holding Volume instead of cache to
462 retrieve more values
463
464---
465 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 22 +++++++++++-----------
466 src/add-ons/kernel/file_systems/btrfs/BTree.h | 6 +++---
467 2 files changed, 14 insertions(+), 14 deletions(-)
468
469diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
470index 726aa84..4ca1ef1 100644
471--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
472+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
473@@ -20,10 +20,10 @@
474 # define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
475
476
477-BTree::Node::Node(void* cache)
478+BTree::Node::Node(Volume* volume)
479 :
480 fNode(NULL),
481- fCache(cache),
482+ fVolume(volume),
483 fBlockNumber(0),
484 fCurrentSlot(0),
485 fWritable(false)
486@@ -31,10 +31,10 @@ BTree::Node::Node(void* cache)
487 }
488
489
490-BTree::Node::Node(void* cache, off_t block)
491+BTree::Node::Node(Volume* volume, off_t block)
492 :
493 fNode(NULL),
494- fCache(cache),
495+ fVolume(volume),
496 fBlockNumber(0),
497 fCurrentSlot(0),
498 fWritable(false)
499@@ -59,7 +59,7 @@ void
500 BTree::Node::Unset()
501 {
502 if (fNode != NULL) {
503- block_cache_put(fCache, fBlockNumber);
504+ block_cache_put(fVolume->BlockCache(), fBlockNumber);
505 fNode = NULL;
506 }
507 }
508@@ -70,7 +70,7 @@ BTree::Node::SetTo(off_t block)
509 {
510 Unset();
511 fBlockNumber = block;
512- fNode = (btrfs_stream*)block_cache_get(fCache, block);
513+ fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
514 }
515
516
517@@ -81,11 +81,11 @@ BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
518 fBlockNumber = block;
519 fWritable = true;
520 if (empty) {
521- fNode = (btrfs_stream*)block_cache_get_empty(fCache, block,
522- transactionId);
523+ fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
524+ block, transactionId);
525 } else {
526- fNode = (btrfs_stream*)block_cache_get_writable(fCache, block,
527- transactionId);
528+ fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
529+ block, transactionId);
530 }
531 }
532
533@@ -217,7 +217,7 @@ BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
534 {
535 TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
536 key.ObjectID(), key.Type(), key.Offset());
537- BTree::Node node(fVolume->BlockCache(), fRootBlock);
538+ BTree::Node node(fVolume, fRootBlock);
539 int slot, ret;
540 fsblock_t physicalBlock;
541
542diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
543index 5a40fea..bb034dd 100644
544--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
545+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
546@@ -83,8 +83,8 @@ private:
547 public:
548 class Node {
549 public:
550- Node(void* cache);
551- Node(void* cache, off_t block);
552+ Node(Volume* volume);
553+ Node(Volume* volume, off_t block);
554 ~Node();
555
556 // just return from Header
557@@ -127,7 +127,7 @@ public:
558 //no implementation
559
560 btrfs_stream* fNode;
561- void* fCache;
562+ Volume* fVolume;
563 off_t fBlockNumber;
564 uint32 fCurrentSlot;
565 bool fWritable;
566--
5672.7.4
568
569
570From b721459aa0cd333b34287a0663fd11279773ebc1 Mon Sep 17 00:00:00 2001
571From: hyche <cvghy116@gmail.com>
572Date: Sun, 13 Aug 2017 00:30:06 +0700
573Subject: [PATCH 5/7] BTRFS: Implement BTree::Path and change _Find.
574
575Remove attribute fCurrentSlot in BTree::Node as it will be handled by Path explicitly. BTree control Path by passing its type in
576BTree's method, Path also hold BTree type as its attribute to do some internal actions.
577Add constant BTREE_KEY_TYPE_ANY, find search key has this type will success regardless of the found key's type.
578
579Split the the _Find function into Traverse and GetEntry. Traverse will fill in the Path (nodes and slots) along way its finding,
580GetEntry will get the item data, item size, key from leaf, if the slot is valid, that we have from Traverse. The _Find function also
581check type if is correct and then retrieve. Doing this way there will be more flexible, the "read" flag is not needed as we only
582need Path to manipulate tree, and it also enhance the performance at some points, because Path caches all the nodes from root to leaf,
583so that we don't have to block_cache_put and block_cache_get after each finding.
584---
585 .../kernel/file_systems/btrfs/Attribute.cpp | 3 +-
586 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 309 +++++++++++++++++----
587 src/add-ons/kernel/file_systems/btrfs/BTree.h | 67 ++++-
588 .../file_systems/btrfs/DirectoryIterator.cpp | 3 +-
589 src/add-ons/kernel/file_systems/btrfs/Inode.cpp | 13 +-
590 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 30 +-
591 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 1 +
592 7 files changed, 337 insertions(+), 89 deletions(-)
593
594diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
595index ddda28d..1c0b286 100644
596--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
597+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
598@@ -151,10 +151,11 @@ Attribute::_Lookup(const char* name, size_t nameLength,
599 key.SetType(BTRFS_KEY_TYPE_XATTR_ITEM);
600 key.SetObjectID(fInode->ID());
601 key.SetOffset(hash);
602+ BTree::Path path(fInode->GetVolume()->FSTree());
603
604 btrfs_dir_entry* entries;
605 uint32 length;
606- status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
607+ status_t status = fInode->GetVolume()->FSTree()->FindExact(&path, key,
608 (void**)&entries, &length);
609 if (status != B_OK) {
610 TRACE("AttributeIterator::Lookup(): Couldn't find entry with hash %"
611diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
612index 4ca1ef1..ce87f5a 100644
613--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
614+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
615@@ -25,7 +25,6 @@ BTree::Node::Node(Volume* volume)
616 fNode(NULL),
617 fVolume(volume),
618 fBlockNumber(0),
619- fCurrentSlot(0),
620 fWritable(false)
621 {
622 }
623@@ -36,7 +35,6 @@ BTree::Node::Node(Volume* volume, off_t block)
624 fNode(NULL),
625 fVolume(volume),
626 fBlockNumber(0),
627- fCurrentSlot(0),
628 fWritable(false)
629 {
630 SetTo(block);
631@@ -142,7 +140,109 @@ BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
632 }
633
634
635-//-pragma mark
636+// #pragma mark - BTree::Path implementation
637+
638+
639+BTree::Path::Path(BTree* tree)
640+ :
641+ fTree(tree)
642+{
643+ for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
644+ fNodes[i] = NULL;
645+ fSlots[i] = 0;
646+ }
647+}
648+
649+
650+BTree::Path::~Path()
651+{
652+ for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
653+ delete fNodes[i];
654+ fNodes[i] = NULL;
655+ fSlots[i] = 0;
656+ }
657+}
658+
659+
660+BTree::Node*
661+BTree::Path::GetNode(int level, int* _slot) const
662+{
663+ if (_slot != NULL)
664+ *_slot = fSlots[level];
665+ return fNodes[level];
666+}
667+
668+
669+BTree::Node*
670+BTree::Path::SetNode(off_t block, int slot)
671+{
672+ Node node(fTree->SystemVolume(), block);
673+ return SetNode(&node, slot);
674+}
675+
676+
677+BTree::Node*
678+BTree::Path::SetNode(const Node* node, int slot)
679+{
680+ uint8 level = node->Level();
681+ if (fNodes[level] == NULL) {
682+ fNodes[level] = new Node(fTree->SystemVolume(), node->BlockNum());
683+ if (fNodes[level] == NULL)
684+ return NULL;
685+ } else
686+ fNodes[level]->SetTo(node->BlockNum());
687+
688+ if (slot == -1)
689+ fSlots[level] = fNodes[level]->ItemCount() - 1;
690+ else
691+ fSlots[level] = slot;
692+ return fNodes[level];
693+}
694+
695+
696+int
697+BTree::Path::Move(int level, int step)
698+{
699+ fSlots[level] += step;
700+ if (fSlots[level] < 0)
701+ return -1;
702+ if (fSlots[level] >= fNodes[level]->ItemCount())
703+ return 1;
704+ return 0;
705+}
706+
707+
708+status_t
709+BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
710+ uint32* _offset)
711+{
712+ BTree::Node* leaf = fNodes[0];
713+ if (slot < 0 || slot >= leaf->ItemCount())
714+ return B_ENTRY_NOT_FOUND;
715+
716+ if (_key != NULL)
717+ *_key = leaf->Item(slot)->key;
718+
719+ uint32 itemSize = leaf->Item(slot)->Size();
720+ if (_value != NULL) {
721+ *_value = malloc(itemSize);
722+ if (*_value == NULL)
723+ return B_NO_MEMORY;
724+
725+ memcpy(*_value, leaf->ItemData(slot), itemSize);
726+ }
727+
728+ if (_size != NULL)
729+ *_size = itemSize;
730+
731+ if (_offset != NULL)
732+ *_offset = leaf->Item(slot)->Offset();
733+
734+ return B_OK;
735+}
736+
737+
738+// #pragma mark - BTree implementation
739
740
741 BTree::BTree(Volume* volume)
742@@ -206,85 +306,180 @@ btrfs_key::Compare(const btrfs_key& key) const
743 }
744
745
746-/*! Searches the key in the tree, and stores the allocated found item in
747- _value, if successful.
748- Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
749- It can also return other errors to indicate that something went wrong.
750-*/
751+/* Traverse from root to fill in the path along way its finding.
752+ * Return current slot at leaf if successful.
753+ */
754 status_t
755-BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
756- bool read, btree_traversing type)
757+BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
758+ const
759 {
760- TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
761- key.ObjectID(), key.Type(), key.Offset());
762- BTree::Node node(fVolume, fRootBlock);
763- int slot, ret;
764- fsblock_t physicalBlock;
765+ TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
766+ B_PRId64 " \n", key.ObjectID(), key.Type(), key.Offset());
767+ fsblock_t physicalBlock = fRootBlock;
768+ Node node(fVolume, physicalBlock);
769+ int slot;
770+ status_t status = B_OK;
771
772 while (node.Level() != 0) {
773- TRACE("Find() level %d\n", node.Level());
774- ret = node.SearchSlot(key, &slot, BTREE_BACKWARD);
775- if (ret != B_OK)
776- return ret;
777- TRACE("Find() getting index %" B_PRIu32 "\n", slot);
778-
779- if (fVolume->FindBlock(node.Index(slot)->LogicalAddress(), physicalBlock)
780- != B_OK) {
781- ERROR("Find() unmapped block %" B_PRId64 "\n",
782+ TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
783+ node.ItemCount());
784+ status = node.SearchSlot(key, &slot, BTREE_BACKWARD);
785+ if (status != B_OK)
786+ return status;
787+ if (path->SetNode(&node, slot) == NULL)
788+ return B_NO_MEMORY;
789+
790+ TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);
791+
792+ status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
793+ physicalBlock);
794+ if (status != B_OK) {
795+ ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n",
796 node.Index(slot)->LogicalAddress());
797- return B_ERROR;
798+ return status;
799 }
800 node.SetTo(physicalBlock);
801 }
802
803- TRACE("Find() dump count %" B_PRId32 "\n", node.ItemCount());
804- ret = node.SearchSlot(key, &slot, type);
805- if ((slot >= node.ItemCount() || node.Item(slot)->key.Type() != key.Type())
806- && read == true
807- || ret != B_OK) {
808- TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n", key.Offset(),
809- key.ObjectID());
810+ TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
811+ status = node.SearchSlot(key, &slot, type);
812+ if (status != B_OK)
813+ return status;
814+ if (path->SetNode(&node, slot) == NULL)
815+ return B_NO_MEMORY;
816+
817+ TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
818+ node.Item(slot)->Offset(), node.Item(slot)->Size());
819+ return slot;
820+}
821+
822+
823+/*! Searches the key in the tree, and stores the allocated found item in
824+ _value, if successful.
825+ Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
826+ It can also return other errors to indicate that something went wrong.
827+*/
828+status_t
829+BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
830+ uint32* _offset, btree_traversing type) const
831+{
832+ status_t status = Traverse(type, path, wanted);
833+ if (status < B_OK)
834+ return status;
835+
836+ btrfs_key found;
837+ status = path->GetCurrentEntry(&found, _value, _size, _offset);
838+ if (status != B_OK)
839+ return status;
840+
841+ if (found.Type() != wanted.Type() && wanted.Type() != BTRFS_KEY_TYPE_ANY)
842 return B_ENTRY_NOT_FOUND;
843- }
844
845- if (read == true) {
846- TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
847- node.Item(slot)->Offset(), node.Item(slot)->Size());
848-
849- if (_value != NULL) {
850- *_value = malloc(node.Item(slot)->Size());
851- memcpy(*_value, node.ItemData(slot),
852- node.Item(slot)->Size());
853- key.SetOffset(node.Item(slot)->key.Offset());
854- key.SetObjectID(node.Item(slot)->key.ObjectID());
855- if (_size != NULL)
856- *_size = node.Item(slot)->Size();
857- }
858- } else {
859- *_value = (void*)&slot;
860- }
861+ wanted = found;
862 return B_OK;
863 }
864
865
866 status_t
867-BTree::FindNext(btrfs_key& key, void** _value, uint32* _size, bool read)
868+BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
869+ uint32* _offset) const
870 {
871- return _Find(key, _value, _size, read, BTREE_FORWARD);
872+ return _Find(path, key, _value, _size, _offset, BTREE_FORWARD);
873 }
874
875
876 status_t
877-BTree::FindPrevious(btrfs_key& key, void** _value, uint32* _size, bool read)
878+BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
879+ uint32* _offset) const
880 {
881- return _Find(key, _value, _size, read, BTREE_BACKWARD);
882+ return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD);
883 }
884
885
886 status_t
887-BTree::FindExact(btrfs_key& key, void** _value, uint32* _size, bool read)
888+BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
889+ uint32* _offset) const
890 {
891- return _Find(key, _value, _size, read, BTREE_EXACT);
892+ return _Find(path, key, _value, _size, _offset, BTREE_EXACT);
893+}
894+
895+
896+status_t
897+BTree::PreviousLeaf(Path* path) const
898+{
899+ // TODO: use Traverse() ???
900+ int level = 0;
901+ int slot;
902+ Node* node = NULL;
903+ // iterate to the root until satisfy the condition
904+ while (true) {
905+ node = path->GetNode(level, &slot);
906+ if (node == NULL || slot != 0)
907+ break;
908+ level++;
909+ }
910+
911+ // the current leaf is already the left most leaf or
912+ // path was not initialized
913+ if (node == NULL)
914+ return B_ENTRY_NOT_FOUND;
915+
916+ path->Move(level, BTREE_BACKWARD);
917+ fsblock_t physicalBlock;
918+ // change all nodes below this level and slot to the ending
919+ do {
920+ status_t status = fVolume->FindBlock(
921+ node->Index(slot)->LogicalAddress(), physicalBlock);
922+ if (status != B_OK)
923+ return status;
924+
925+ node = path->SetNode(physicalBlock, -1);
926+ if (node == NULL)
927+ return B_NO_MEMORY;
928+ slot = node->ItemCount() - 1;
929+ level--;
930+ } while(level != 0);
931+
932+ return B_OK;
933+}
934+
935+
936+status_t
937+BTree::NextLeaf(Path* path) const
938+{
939+ int level = 0;
940+ int slot;
941+ Node* node = NULL;
942+ // iterate to the root until satisfy the condition
943+ while (true) {
944+ node = path->GetNode(level, &slot);
945+ if (node == NULL || slot < node->ItemCount() - 1)
946+ break;
947+ level++;
948+ }
949+
950+ // the current leaf is already the right most leaf or
951+ // path was not initialized
952+ if (node == NULL)
953+ return B_ENTRY_NOT_FOUND;
954+
955+ path->Move(level, BTREE_FORWARD);
956+ fsblock_t physicalBlock;
957+ // change all nodes below this level and slot to the beginning
958+ do {
959+ status_t status = fVolume->FindBlock(
960+ node->Index(slot)->LogicalAddress(), physicalBlock);
961+ if (status != B_OK)
962+ return status;
963+
964+ node = path->SetNode(physicalBlock, 0);
965+ if (node == NULL)
966+ return B_NO_MEMORY;
967+ slot = 0;
968+ level--;
969+ } while(level != 0);
970+
971+ return B_OK;
972 }
973
974
975@@ -351,8 +546,8 @@ TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
976 return B_INTERRUPTED;
977
978 fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
979- status_t status = fTree->_Find(fCurrentKey, value, size,
980- true, direction);
981+ BTree::Path path(fTree);
982+ status_t status = fTree->_Find(&path, fCurrentKey, value, size, direction);
983 if (status != B_OK) {
984 TRACE("TreeIterator::Traverse() Find failed\n");
985 return B_ENTRY_NOT_FOUND;
986diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
987index bb034dd..30afcaf 100644
988--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
989+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
990@@ -43,21 +43,33 @@ struct node_and_key {
991
992 class BTree {
993 public:
994+ class Path;
995+
996+public:
997 BTree(Volume* volume);
998 BTree(Volume* volume,
999 btrfs_stream* stream);
1000 BTree(Volume* volume,
1001 fsblock_t rootBlock);
1002 ~BTree();
1003- status_t FindExact(btrfs_key& key, void** value,
1004- uint32* size = NULL, bool read = true);
1005- status_t FindNext(btrfs_key& key, void** value,
1006- uint32* size = NULL, bool read = true);
1007- status_t FindPrevious(btrfs_key& key, void** value,
1008- uint32* size = NULL, bool read = true);
1009
1010- Volume* SystemVolume() const { return fVolume; }
1011+ status_t FindExact(Path* path, btrfs_key& key,
1012+ void** _value, uint32* _size = NULL,
1013+ uint32* _offset = NULL) const;
1014+ status_t FindNext(Path* path, btrfs_key& key,
1015+ void** _value, uint32* _size = NULL,
1016+ uint32* _offset = NULL) const;
1017+ status_t FindPrevious(Path* path, btrfs_key& key,
1018+ void** _value, uint32* _size = NULL,
1019+ uint32* _offset = NULL) const;
1020+
1021+ status_t Traverse(btree_traversing type, Path* path,
1022+ const btrfs_key& key) const;
1023+
1024+ status_t PreviousLeaf(Path* path) const;
1025+ status_t NextLeaf(Path* path) const;
1026
1027+ Volume* SystemVolume() const { return fVolume; }
1028 status_t SetRoot(off_t logical, fsblock_t* block);
1029 fsblock_t RootBlock() const { return fRootBlock; }
1030 off_t LogicalRoot() const { return fLogicalRoot; }
1031@@ -67,8 +79,10 @@ private:
1032 BTree& operator=(const BTree& other);
1033 // no implementation
1034
1035- status_t _Find(btrfs_key& key, void** value, uint32* size,
1036- bool read, btree_traversing type);
1037+ status_t _Find(Path* path, btrfs_key& key,
1038+ void** _value, uint32* _size,
1039+ uint32* _offset, btree_traversing type)
1040+ const;
1041 void _AddIterator(TreeIterator* iterator);
1042 void _RemoveIterator(TreeIterator* iterator);
1043 private:
1044@@ -113,8 +127,7 @@ public:
1045 void Unset();
1046
1047 void SetTo(off_t block);
1048- void SetToWritable(off_t block,
1049- int32 transactionId, bool empty);
1050+ void SetToWritable(off_t block, int32 transactionId, bool empty);
1051
1052 off_t BlockNum() const { return fBlockNumber;}
1053 bool IsWritable() const { return fWritable; }
1054@@ -129,18 +142,33 @@ public:
1055 btrfs_stream* fNode;
1056 Volume* fVolume;
1057 off_t fBlockNumber;
1058- uint32 fCurrentSlot;
1059 bool fWritable;
1060 };
1061
1062
1063 class Path {
1064 public:
1065- Path();
1066+ Path(BTree* tree);
1067+ ~Path();
1068+
1069+ Node* GetNode(int level, int* _slot = NULL) const;
1070+ Node* SetNode(off_t block, int slot);
1071+ Node* SetNode(const Node* node, int slot);
1072+ status_t GetCurrentEntry(btrfs_key* _key, void** _value,
1073+ uint32* _size = NULL, uint32* _offset = NULL);
1074+ status_t GetEntry(int slot, btrfs_key* _key, void** _value,
1075+ uint32* _size = NULL, uint32* _offset = NULL);
1076+
1077+ int Move(int level, int step);
1078+
1079+ BTree* Tree() const { return fTree; }
1080 private:
1081 Path(const Path&);
1082 Path operator=(const Path&);
1083- Node* nodes[BTRFS_MAX_TREE_DEPTH];
1084+ private:
1085+ Node* fNodes[BTRFS_MAX_TREE_DEPTH];
1086+ int fSlots[BTRFS_MAX_TREE_DEPTH];
1087+ BTree* fTree;
1088 };
1089
1090 }; // class BTree
1091@@ -176,6 +204,17 @@ private:
1092 };
1093
1094
1095+// #pragma mark - BTree::Path inline functions
1096+
1097+
1098+inline status_t
1099+BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
1100+ uint32* _offset)
1101+{
1102+ return GetEntry(fSlots[0], _key, _value, _size, _offset);
1103+}
1104+
1105+
1106 // #pragma mark - TreeIterator inline functions
1107
1108
1109diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1110index 4f9a1b7..ccfd1b2 100644
1111--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1112+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1113@@ -123,10 +123,11 @@ DirectoryIterator::Lookup(const char* name, size_t nameLength, ino_t* _id)
1114 key.SetType(BTRFS_KEY_TYPE_DIR_ITEM);
1115 key.SetObjectID(fInode->ID());
1116 key.SetOffset(hash);
1117+ BTree::Path path(fInode->GetVolume()->FSTree());
1118
1119 btrfs_dir_entry* entries;
1120 uint32 length;
1121- status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
1122+ status_t status = fInode->GetVolume()->FSTree()->FindExact(&path, key,
1123 (void**)&entries, &length);
1124 if (status != B_OK) {
1125 TRACE("DirectoryIterator::Lookup(): Couldn't find entry with hash %" B_PRIu32
1126diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
1127index a2e7bb8..173fe19 100644
1128--- a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
1129+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
1130@@ -78,9 +78,11 @@ Inode::UpdateNodeFromDisk()
1131 search_key.SetType(BTRFS_KEY_TYPE_INODE_ITEM);
1132 search_key.SetObjectID(fID);
1133 search_key.SetOffset(0);
1134+ BTree::Path path(fVolume->FSTree());
1135
1136 btrfs_inode* node;
1137- if (fVolume->FSTree()->FindExact(search_key, (void**)&node) != B_OK) {
1138+ if (fVolume->FSTree()->FindExact(&path, search_key, (void**)&node)
1139+ != B_OK) {
1140 ERROR("Inode::UpdateNodeFromDisk(): Couldn't find inode %"
1141 B_PRIdINO "\n", fID);
1142 return B_ENTRY_NOT_FOUND;
1143@@ -111,9 +113,10 @@ Inode::FindBlock(off_t pos, off_t& physical, off_t* _length)
1144 search_key.SetType(BTRFS_KEY_TYPE_EXTENT_DATA);
1145 search_key.SetObjectID(fID);
1146 search_key.SetOffset(pos + 1);
1147+ BTree::Path path(fVolume->FSTree());
1148
1149 btrfs_extent_data* extent_data;
1150- status_t status = fVolume->FSTree()->FindPrevious(search_key,
1151+ status_t status = fVolume->FSTree()->FindPrevious(&path, search_key,
1152 (void**)&extent_data);
1153 if (status != B_OK) {
1154 ERROR("Inode::FindBlock(): Couldn't find extent_data 0x%" B_PRIx32
1155@@ -166,10 +169,11 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
1156 search_key.SetType(BTRFS_KEY_TYPE_EXTENT_DATA);
1157 search_key.SetObjectID(fID);
1158 search_key.SetOffset(pos + 1);
1159+ BTree::Path path(fVolume->FSTree());
1160
1161 uint32 item_size;
1162 btrfs_extent_data* extent_data;
1163- status_t status = fVolume->FSTree()->FindPrevious(search_key,
1164+ status_t status = fVolume->FSTree()->FindPrevious(&path, search_key,
1165 (void**)&extent_data, &item_size);
1166 if (status != B_OK) {
1167 ERROR("Inode::FindBlock(): Couldn't find extent_data 0x%" B_PRIx32
1168@@ -292,9 +296,10 @@ Inode::FindParent(ino_t* id)
1169 search_key.SetType(BTRFS_KEY_TYPE_INODE_REF);
1170 search_key.SetObjectID(fID);
1171 search_key.SetOffset(-1);
1172+ BTree::Path path(fVolume->FSTree());
1173
1174 void* node_ref;
1175- if (fVolume->FSTree()->FindPrevious(search_key, &node_ref) != B_OK) {
1176+ if (fVolume->FSTree()->FindPrevious(&path, search_key, &node_ref) != B_OK) {
1177 ERROR("Inode::FindParent(): Couldn't find inode for %" B_PRIdINO "\n",
1178 fID);
1179 return B_ERROR;
1180diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1181index 159f67e..dc2fffe 100644
1182--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1183+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1184@@ -317,15 +317,18 @@ Volume::Mount(const char* deviceName, uint32 flags)
1185 TRACE("Volume::Mount() root: %" B_PRIu64 " (physical block %" B_PRIu64 ")\n",
1186 fSuperBlock.Root(), fRootTree->RootBlock());
1187
1188+ BTree::Path path(fRootTree);
1189+
1190 TRACE("Volume::Mount(): Searching extent root\n");
1191 btrfs_key search_key;
1192 search_key.SetOffset(0);
1193 search_key.SetType(BTRFS_KEY_TYPE_ROOT_ITEM);
1194 search_key.SetObjectID(BTRFS_OBJECT_ID_EXTENT_TREE);
1195 btrfs_root* root;
1196- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
1197+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
1198+ if (status != B_OK) {
1199 ERROR("Volume::Mount(): Couldn't find extent root\n");
1200- return B_ERROR;
1201+ return status;
1202 }
1203 TRACE("Volume::Mount(): Found extent root: %" B_PRIu64 "\n",
1204 root->LogicalAddress());
1205@@ -338,9 +341,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
1206 TRACE("Volume::Mount(): Searching fs root\n");
1207 search_key.SetOffset(0);
1208 search_key.SetObjectID(BTRFS_OBJECT_ID_FS_TREE);
1209- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
1210+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
1211+ if (status != B_OK) {
1212 ERROR("Volume::Mount(): Couldn't find fs root\n");
1213- return B_ERROR;
1214+ return status;
1215 }
1216 TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n",
1217 root->LogicalAddress());
1218@@ -353,9 +357,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
1219 TRACE("Volume::Mount(): Searching dev root\n");
1220 search_key.SetOffset(0);
1221 search_key.SetObjectID(BTRFS_OBJECT_ID_DEV_TREE);
1222- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
1223+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
1224+ if (status != B_OK) {
1225 ERROR("Volume::Mount(): Couldn't find dev root\n");
1226- return B_ERROR;
1227+ return status;
1228 }
1229 TRACE("Volume::Mount(): Found dev root: %" B_PRIu64 "\n",
1230 root->LogicalAddress());
1231@@ -368,9 +373,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
1232 TRACE("Volume::Mount(): Searching checksum root\n");
1233 search_key.SetOffset(0);
1234 search_key.SetObjectID(BTRFS_OBJECT_ID_CHECKSUM_TREE);
1235- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
1236+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
1237+ if (status != B_OK) {
1238 ERROR("Volume::Mount(): Couldn't find checksum root\n");
1239- return B_ERROR;
1240+ return status;
1241 }
1242 TRACE("Volume::Mount(): Found checksum root: %" B_PRIu64 "\n",
1243 root->LogicalAddress());
1244@@ -484,11 +490,11 @@ Volume::FindBlock(off_t logical, off_t& physical)
1245 btrfs_key search_key;
1246 search_key.SetOffset(logical);
1247 search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
1248- search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
1249+ search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
1250 btrfs_chunk* chunk;
1251- uint32 chunk_length;
1252- status_t status = fChunkTree->FindPrevious(search_key, (void**)&chunk,
1253- &chunk_length);
1254+ BTree::Path path(fChunkTree);
1255+ status_t status = fChunkTree->FindPrevious(&path, search_key,
1256+ (void**)&chunk);
1257 if (status != B_OK)
1258 return status;
1259
1260diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1261index 54e4634..d2f4518 100644
1262--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1263+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1264@@ -427,6 +427,7 @@ struct btrfs_extent_data_ref {
1265 #define BTRFS_OBJECT_ID_CHECKSUM_TREE 7
1266 #define BTRFS_OBJECT_ID_FIRST_CHUNK_TREE 256
1267
1268+#define BTRFS_KEY_TYPE_ANY 0
1269 #define BTRFS_KEY_TYPE_INODE_ITEM 1
1270 #define BTRFS_KEY_TYPE_INODE_REF 12
1271 #define BTRFS_KEY_TYPE_XATTR_ITEM 24
1272--
12732.7.4
1274
1275
1276From 4c571bc177506e59c6e5b3b50e86cd0538a0a84a Mon Sep 17 00:00:00 2001
1277From: hyche <cvghy116@gmail.com>
1278Date: Sun, 13 Aug 2017 04:29:18 +0700
1279Subject: [PATCH 6/7] BTRFS: Reimplement TreeIterator, add some error checks
1280 and remove redundancies.
1281
1282Add BTree::Path as a attribute so enhance performance, so that everytime we iterate through items it wont search all the root to leaf
1283again. The Iterator is initialized without rewinding to make more flexible.
1284---
1285 .../file_systems/btrfs/AttributeIterator.cpp | 7 +-
1286 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 86 +++++++++++++++++-----
1287 src/add-ons/kernel/file_systems/btrfs/BTree.h | 49 ++++++------
1288 .../file_systems/btrfs/DirectoryIterator.cpp | 9 +--
1289 4 files changed, 100 insertions(+), 51 deletions(-)
1290
1291diff --git a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
1292index f453a11..b9dfc91 100644
1293--- a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
1294+++ b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
1295@@ -22,9 +22,10 @@ AttributeIterator::AttributeIterator(Inode* inode)
1296 fInode(inode),
1297 fIterator(NULL)
1298 {
1299- struct btrfs_key key;
1300+ btrfs_key key;
1301 key.SetType(BTRFS_KEY_TYPE_XATTR_ITEM);
1302 key.SetObjectID(inode->ID());
1303+ key.SetOffset(BTREE_BEGIN);
1304 fIterator = new(std::nothrow) TreeIterator(inode->GetVolume()->FSTree(),
1305 key);
1306 }
1307@@ -33,6 +34,7 @@ AttributeIterator::AttributeIterator(Inode* inode)
1308 AttributeIterator::~AttributeIterator()
1309 {
1310 delete fIterator;
1311+ fIterator = NULL;
1312 }
1313
1314
1315@@ -46,10 +48,9 @@ AttributeIterator::InitCheck()
1316 status_t
1317 AttributeIterator::GetNext(char* name, size_t* _nameLength)
1318 {
1319- btrfs_key key;
1320 btrfs_dir_entry* entries;
1321 uint32 entries_length;
1322- status_t status = fIterator->GetPreviousEntry(key, (void**)&entries,
1323+ status_t status = fIterator->GetPreviousEntry((void**)&entries,
1324 &entries_length);
1325 if (status != B_OK)
1326 return status;
1327diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1328index ce87f5a..bf93bf3 100644
1329--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1330+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1331@@ -519,13 +519,16 @@ BTree::_RemoveIterator(TreeIterator* iterator)
1332 // #pragma mark -
1333
1334
1335-TreeIterator::TreeIterator(BTree* tree, btrfs_key& key)
1336+TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
1337 :
1338 fTree(tree),
1339- fCurrentKey(key)
1340+ fKey(key),
1341+ fIteratorStatus(B_NO_INIT)
1342 {
1343- Rewind();
1344 tree->_AddIterator(this);
1345+ fPath = new(std::nothrow) BTree::Path(tree);
1346+ if (fPath == NULL)
1347+ fIteratorStatus = B_NO_MEMORY;
1348 }
1349
1350
1351@@ -533,26 +536,72 @@ TreeIterator::~TreeIterator()
1352 {
1353 if (fTree)
1354 fTree->_RemoveIterator(this);
1355+
1356+ delete fPath;
1357+ fPath = NULL;
1358+}
1359+
1360+
1361+void
1362+TreeIterator::Rewind(bool inverse)
1363+{
1364+ if (inverse)
1365+ fKey.SetOffset(BTREE_END);
1366+ else
1367+ fKey.SetOffset(BTREE_BEGIN);
1368+ fIteratorStatus = B_NO_INIT;
1369 }
1370
1371
1372 /*! Iterates through the tree in the specified direction.
1373 */
1374 status_t
1375-TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
1376- void** value, uint32* size)
1377+TreeIterator::_Traverse(btree_traversing direction)
1378 {
1379- if (fTree == NULL)
1380- return B_INTERRUPTED;
1381+ status_t status = fTree->Traverse(direction, fPath, fKey);
1382+ if (status < B_OK) {
1383+ ERROR("TreeIterator::Traverse() Find failed\n");
1384+ return status;
1385+ }
1386
1387- fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
1388- BTree::Path path(fTree);
1389- status_t status = fTree->_Find(&path, fCurrentKey, value, size, direction);
1390- if (status != B_OK) {
1391- TRACE("TreeIterator::Traverse() Find failed\n");
1392- return B_ENTRY_NOT_FOUND;
1393+ return (fIteratorStatus = B_OK);
1394+}
1395+
1396+
1397+// Like GetEntry in BTree::Path but here we check the type and moving.
1398+status_t
1399+TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size,
1400+ uint32* _offset)
1401+{
1402+ status_t status;
1403+ if (fIteratorStatus == B_NO_INIT) {
1404+ status = _Traverse(type);
1405+ if (status != B_OK)
1406+ return status;
1407+ type = BTREE_EXACT;
1408 }
1409
1410+ if (fIteratorStatus != B_OK)
1411+ return fIteratorStatus;
1412+
1413+ int move = fPath->Move(0, type);
1414+ if (move > 0)
1415+ status = fTree->NextLeaf(fPath);
1416+ else if (move < 0)
1417+ status = fTree->PreviousLeaf(fPath);
1418+ if (status != B_OK)
1419+ return status;
1420+
1421+ btrfs_key found;
1422+ status = fPath->GetCurrentEntry(&found, _value, _size, _offset);
1423+ if (status != B_OK)
1424+ return status;
1425+
1426+ fKey.SetObjectID(found.ObjectID());
1427+ fKey.SetOffset(found.Offset());
1428+ if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY)
1429+ return B_ENTRY_NOT_FOUND;
1430+
1431 return B_OK;
1432 }
1433
1434@@ -560,11 +609,13 @@ TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
1435 /*! just sets the current key in the iterator.
1436 */
1437 status_t
1438-TreeIterator::Find(btrfs_key& key)
1439+TreeIterator::Find(const btrfs_key& key)
1440 {
1441- if (fTree == NULL)
1442- return B_INTERRUPTED;
1443- fCurrentKey = key;
1444+ if (fIteratorStatus == B_INTERRUPTED)
1445+ return fIteratorStatus;
1446+
1447+ fKey = key;
1448+ fIteratorStatus = B_NO_INIT;
1449 return B_OK;
1450 }
1451
1452@@ -573,4 +624,5 @@ void
1453 TreeIterator::Stop()
1454 {
1455 fTree = NULL;
1456+ fIteratorStatus = B_INTERRUPTED;
1457 }
1458diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
1459index 30afcaf..d44a401 100644
1460--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
1461+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
1462@@ -176,31 +176,37 @@ public:
1463
1464 class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
1465 public:
1466- TreeIterator(BTree* tree, btrfs_key& key);
1467+ TreeIterator(BTree* tree, const btrfs_key& key);
1468 ~TreeIterator();
1469
1470- status_t Traverse(btree_traversing direction,
1471- btrfs_key& key, void** value,
1472- uint32* size = NULL);
1473- status_t Find(btrfs_key& key);
1474+ void Rewind(bool inverse = false);
1475+ status_t Find(const btrfs_key& key);
1476+ status_t GetNextEntry(void** _value,
1477+ uint32* _size = NULL,
1478+ uint32* _offset = NULL);
1479+ status_t GetPreviousEntry(void** _value,
1480+ uint32* _size = NULL,
1481+ uint32* _offset = NULL);
1482
1483- status_t Rewind();
1484- status_t GetNextEntry(btrfs_key& key, void** value,
1485- uint32* size = NULL);
1486- status_t GetPreviousEntry(btrfs_key& key, void** value,
1487- uint32* size = NULL);
1488-
1489- BTree* Tree() const { return fTree; }
1490+ BTree* Tree() const { return fTree; }
1491+ btrfs_key Key() const { return fKey; }
1492
1493 private:
1494 friend class BTree;
1495
1496+ status_t _Traverse(btree_traversing direction);
1497+ status_t _Find(btree_traversing type, btrfs_key& key,
1498+ void** _value);
1499+ status_t _GetEntry(btree_traversing type, void** _value,
1500+ uint32* _size, uint32* _offset);
1501 // called by BTree
1502 void Stop();
1503
1504 private:
1505 BTree* fTree;
1506- btrfs_key fCurrentKey;
1507+ BTree::Path* fPath;
1508+ btrfs_key fKey;
1509+ status_t fIteratorStatus;
1510 };
1511
1512
1513@@ -219,25 +225,16 @@ BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
1514
1515
1516 inline status_t
1517-TreeIterator::Rewind()
1518-{
1519- fCurrentKey.SetOffset(BTREE_BEGIN);
1520- return B_OK;
1521-}
1522-
1523-
1524-inline status_t
1525-TreeIterator::GetNextEntry(btrfs_key& key, void** value, uint32* size)
1526+TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset)
1527 {
1528- return Traverse(BTREE_FORWARD, key, value, size);
1529+ return _GetEntry(BTREE_FORWARD, _value, _size, _offset);
1530 }
1531
1532
1533 inline status_t
1534-TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
1535- uint32* size)
1536+TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset)
1537 {
1538- return Traverse(BTREE_BACKWARD, key, value, size);
1539+ return _GetEntry(BTREE_BACKWARD, _value, _size, _offset);
1540 }
1541
1542
1543diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1544index ccfd1b2..0be81a4 100644
1545--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1546+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1547@@ -26,6 +26,7 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
1548 btrfs_key key;
1549 key.SetType(BTRFS_KEY_TYPE_DIR_INDEX);
1550 key.SetObjectID(inode->ID());
1551+ key.SetOffset(BTREE_BEGIN);
1552 fIterator = new(std::nothrow) TreeIterator(inode->GetVolume()->FSTree(),
1553 key);
1554 }
1555@@ -33,8 +34,8 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
1556
1557 DirectoryIterator::~DirectoryIterator()
1558 {
1559- if (fIterator != NULL)
1560- delete fIterator;
1561+ delete fIterator;
1562+ fIterator = NULL;
1563 }
1564
1565
1566@@ -69,11 +70,9 @@ DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
1567 return fInode->FindParent(_id);
1568 }
1569
1570- btrfs_key key;
1571 btrfs_dir_entry* entries;
1572 uint32 entries_length;
1573- status_t status = fIterator->GetNextEntry(key, (void**)&entries,
1574- &entries_length);
1575+ status_t status = fIterator->GetNextEntry((void**)&entries, &entries_length);
1576 if (status != B_OK)
1577 return status;
1578
1579--
15802.7.4
1581
1582
1583From 8828e448b2a136b26b4005a008b2e0a69e9fc916 Mon Sep 17 00:00:00 2001
1584From: hyche <cvghy116@gmail.com>
1585Date: Sun, 13 Aug 2017 16:42:23 +0700
1586Subject: [PATCH 7/7] BTRFS: Implement ExtentAllocator
1587
1588There are 4 new classes, structs:
1589* CachedExtent, is a AVLTreeNode, caches the extent locating in extent tree, a extent can be free, allocated, metadata or a data extent. It also hold a references count,
1590that is incremented each time a new extent refer to it (COW) and item data, that is only for allocated extent (NULL for free).
1591* CachedTreeExtent, is a AVLTree, cache the whole extent tree and has CachedExtent as its node.
1592* BlockGroup represents the group of extents that represent the region for each type of allocated extent. For example, region for data extents, metada blocks. It
1593responsible for inserting nodes in CachedTreeExtent.
1594* And the final, ExtentAllocator it knows how to allocate/deallocate extents, but for now only the allocating is implemented, actually allocating and deallocating works
1595are already implemented, they are in functions _AddFreeExtent, _AddAllocatedExtent in CachedTreeExtent. However the deallocating is not needed for now, so it will be
1596finished later then.
1597---
1598 .../kernel/file_systems/btrfs/ExtentAllocator.cpp | 692 +++++++++++++++++++++
1599 .../kernel/file_systems/btrfs/ExtentAllocator.h | 153 +++++
1600 src/add-ons/kernel/file_systems/btrfs/Jamfile | 1 +
1601 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 13 +
1602 src/add-ons/kernel/file_systems/btrfs/Volume.h | 3 +
1603 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 3 +-
1604 src/tools/btrfs_shell/Jamfile | 1 +
1605 7 files changed, 865 insertions(+), 1 deletion(-)
1606 create mode 100644 src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
1607 create mode 100644 src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
1608
1609diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
1610new file mode 100644
1611index 0000000..bb57dc2
1612--- /dev/null
1613+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
1614@@ -0,0 +1,692 @@
1615+#include "ExtentAllocator.h"
1616+#include "Chunk.h"
1617+
1618+
1619+CachedExtent*
1620+CachedExtent::Create(uint64 offset, uint64 length, uint64 flags)
1621+{
1622+ CachedExtent* self = new(std::nothrow) CachedExtent();
1623+ if (self == NULL)
1624+ return NULL;
1625+
1626+ self->offset = offset;
1627+ self->length = length;
1628+ self->refCount = 0;
1629+ if ((flags & BTRFS_EXTENT_FLAG_ALLOCATED) != 0)
1630+ self->refCount = 1;
1631+ self->flags = flags;
1632+ self->item = NULL;
1633+ return self;
1634+}
1635+
1636+
1637+void
1638+CachedExtent::Delete()
1639+{
1640+ if (item != NULL)
1641+ free(item);
1642+ item = NULL;
1643+ delete this;
1644+}
1645+
1646+
1647+bool
1648+CachedExtent::IsAllocated() const
1649+{
1650+ return (flags & BTRFS_EXTENT_FLAG_ALLOCATED) != 0;
1651+}
1652+
1653+
1654+bool
1655+CachedExtent::IsData() const
1656+{
1657+ return (flags & BTRFS_EXTENT_FLAG_DATA) != 0;
1658+}
1659+
1660+
1661+void
1662+CachedExtent::Info() const
1663+{
1664+ const char* extentType = "allocated tree block";
1665+ if (IsAllocated() == false && IsData() == false)
1666+ extentType = "free tree block";
1667+ else if (IsAllocated() == false && IsData() == true)
1668+ extentType = "free data extent";
1669+ else if (IsAllocated() == true && IsData() == true)
1670+ extentType = "allocated data extent";
1671+
1672+ TRACE("%s at %" B_PRIu64 " length %" B_PRIu64 " refCount %i\n",
1673+ extentType, offset, length, refCount);
1674+}
1675+
1676+
1677+// ExtentTree Implementation
1678+
1679+
1680+CachedExtentTree::CachedExtentTree(const TreeDefinition& definition)
1681+ :
1682+ AVLTree<TreeDefinition>(definition)
1683+{
1684+}
1685+
1686+
1687+CachedExtentTree::~CachedExtentTree()
1688+{
1689+ Delete();
1690+}
1691+
1692+
1693+/* Find extent that cover or after "offset" and has length >= "size"
1694+ * it must also satisfy the condition "type".
1695+ */
1696+status_t
1697+CachedExtentTree::FindNext(CachedExtent** chosen, uint64 offset, uint64 size,
1698+ uint64 type)
1699+{
1700+ CachedExtent* found = Find(offset);
1701+ while (found != NULL && (found->flags != type || found->length < size))
1702+ found = Next(found);
1703+
1704+ if (found == NULL)
1705+ return B_ENTRY_NOT_FOUND;
1706+ *chosen = found;
1707+ return B_OK;
1708+}
1709+
1710+
1711+/* this will insert all free extents that are holes,
1712+ * created by existed allocated extents in the tree
1713+ * from lowerBound to upperBound
1714+ */
1715+status_t
1716+CachedExtentTree::FillFreeExtents(uint64 lowerBound, uint64 upperBound)
1717+{
1718+ CachedExtent* node = FindClosest(lowerBound, false);
1719+ CachedExtent* hole = NULL;
1720+ status_t status = B_OK;
1721+ uint64 flags = node->flags & (~BTRFS_EXTENT_FLAG_ALLOCATED);
1722+ if (lowerBound < node->offset) {
1723+ hole = CachedExtent::Create(lowerBound, node->offset - lowerBound,
1724+ flags);
1725+ status = _AddFreeExtent(hole);
1726+ if (status != B_OK)
1727+ return status;
1728+ }
1729+
1730+ CachedExtent* next = NULL;
1731+ while ((next = Next(node)) != NULL && next->End() < upperBound) {
1732+ if (node->End() == next->offset) {
1733+ node = next;
1734+ continue;
1735+ }
1736+
1737+ hole = CachedExtent::Create(node->End(), next->offset - node->End(),
1738+ flags);
1739+ status = _AddFreeExtent(hole);
1740+ if (status != B_OK)
1741+ return status;
1742+ node = next;
1743+ }
1744+
1745+ // final node should be a right most node
1746+ if (upperBound > node->End()) {
1747+ hole = CachedExtent::Create(node->End(), upperBound - node->End(),
1748+ flags);
1749+ status = _AddFreeExtent(hole);
1750+ }
1751+
1752+ return status;
1753+}
1754+
1755+
1756+void
1757+CachedExtentTree::_RemoveExtent(CachedExtent* node)
1758+{
1759+ node->refCount--;
1760+ if (node->refCount <= 0) {
1761+ Remove(node);
1762+ node->Delete();
1763+ }
1764+}
1765+
1766+
1767+status_t
1768+CachedExtentTree::_AddAllocatedExtent(CachedExtent* node)
1769+{
1770+ if (node == NULL || node->IsAllocated() == false)
1771+ return B_BAD_VALUE;
1772+
1773+ CachedExtent* found = Find(node->offset);
1774+ if (found == NULL) {
1775+ Insert(node);
1776+ return B_OK;
1777+ }
1778+
1779+ if ((found->IsData() && !node->IsData())
1780+ || (!found->IsData() && node->IsData())) {
1781+ // this shouldn't happen as because different type has
1782+ // its different region for locating.
1783+ node->Delete();
1784+ return B_BAD_VALUE;
1785+ }
1786+
1787+ if (found->IsAllocated() == false) {
1788+ // split free extents (found)
1789+ if (node->End() > found->End()) {
1790+ // TODO: when to handle this ?
1791+ node->Delete();
1792+ return B_BAD_VALUE;
1793+ }
1794+
1795+ // |----- found ------|
1796+ // |-- node ---|
1797+ uint64 diff = node->offset - found->offset;
1798+ found->offset += diff + node->length;
1799+ found->length -= diff + node->length;
1800+ // diff < 0 couldn't happen because of the Compare function
1801+ if (diff > 0) {
1802+ CachedExtent* leftEmpty = CachedExtent::Create(
1803+ node->offset - diff, diff, found->flags);
1804+ _AddFreeExtent(leftEmpty);
1805+ }
1806+
1807+ if (found->length == 0) {
1808+ // free-extent that has no space
1809+ _RemoveExtent(found);
1810+ }
1811+
1812+ Insert(node);
1813+ return B_OK;
1814+ }
1815+
1816+ if (found->length == node->length) {
1817+ found->refCount++;
1818+ } else {
1819+ // TODO: What should we do in this case ?
1820+ return B_BAD_VALUE;
1821+ }
1822+ node->Delete();
1823+
1824+ return B_OK;
1825+}
1826+
1827+
1828+status_t
1829+CachedExtentTree::_AddFreeExtent(CachedExtent* node)
1830+{
1831+ if (node == NULL || node->IsAllocated() == true)
1832+ return B_BAD_VALUE;
1833+
1834+ CachedExtent* found = Find(node->offset);
1835+ if (found == NULL) {
1836+ Insert(node);
1837+ _CombineFreeExtent(node);
1838+ return B_OK;
1839+ }
1840+
1841+ if ((found->IsData() && !node->IsData())
1842+ || (!found->IsData() && node->IsData())) {
1843+ // this shouldn't happen as because different type has
1844+ // its different region for locating.
1845+ node->Delete();
1846+ return B_BAD_VALUE;
1847+ }
1848+
1849+ if (found->End() < node->End()) {
1850+ // |---- found-----|
1851+ // |--- node ------|
1852+ CachedExtent* rightEmpty = CachedExtent::Create(found->End(),
1853+ node->End() - found->End(), node->flags);
1854+ _AddFreeExtent(rightEmpty);
1855+ node->length -= node->End() - found->End();
1856+ }
1857+
1858+ if (found->IsAllocated() == true) {
1859+ // free part of the allocated extents(found)
1860+ // |----- found ------|
1861+ // |-- node ---|
1862+ uint64 diff = node->offset - found->offset;
1863+ found->offset += diff + node->length;
1864+ found->length -= diff + node->length;
1865+ // diff < 0 couldn't happen because of the Compare function
1866+ if (diff > 0){
1867+ CachedExtent* left = CachedExtent::Create(node->offset - diff,
1868+ diff, found->flags);
1869+ _AddAllocatedExtent(left);
1870+ }
1871+
1872+ if (found->length == 0)
1873+ _RemoveExtent(found);
1874+
1875+ Insert(node);
1876+ _CombineFreeExtent(node);
1877+ }
1878+
1879+ return B_OK;
1880+}
1881+
1882+
1883+status_t
1884+CachedExtentTree::AddExtent(CachedExtent* extent)
1885+{
1886+ if (extent->IsAllocated() == true)
1887+ return _AddAllocatedExtent(extent);
1888+ return _AddFreeExtent(extent);
1889+}
1890+
1891+
1892+void
1893+CachedExtentTree::_CombineFreeExtent(CachedExtent* node)
1894+{
1895+ // node should be inserted first to call this function,
1896+ // otherwise it will overdelete.
1897+ if (node->IsAllocated() == true)
1898+ return;
1899+
1900+ CachedExtent* other = Next(node);
1901+ if (other != NULL) {
1902+ if (node->End() == other->offset && node->flags == other->flags) {
1903+ node->length += other->length;
1904+ _RemoveExtent(other);
1905+ }
1906+ }
1907+
1908+ other = Previous(node);
1909+ if (other != NULL) {
1910+ if (other->End() == node->offset && node->flags == other->flags) {
1911+ other->length += node->length;
1912+ _RemoveExtent(node);
1913+ }
1914+ }
1915+}
1916+
1917+
1918+void
1919+CachedExtentTree::_DumpInOrder(CachedExtent* node) const
1920+{
1921+ if (node == NULL)
1922+ return;
1923+ _DumpInOrder(_GetValue(node->left));
1924+ node->Info();
1925+ _DumpInOrder(_GetValue(node->right));
1926+}
1927+
1928+
1929+void
1930+CachedExtentTree::DumpInOrder() const
1931+{
1932+ TRACE("\n");
1933+ _DumpInOrder(RootNode());
1934+ TRACE("\n");
1935+}
1936+
1937+
1938+void
1939+CachedExtentTree::Delete()
1940+{
1941+ _Delete(RootNode());
1942+ Clear();
1943+}
1944+
1945+
1946+void
1947+CachedExtentTree::_Delete(CachedExtent* node)
1948+{
1949+ if (node == NULL)
1950+ return;
1951+ _Delete(_GetValue(node->left));
1952+ _Delete(_GetValue(node->right));
1953+ node->Delete();
1954+}
1955+
1956+
1957+// BlockGroup
1958+
1959+
1960+BlockGroup::BlockGroup(BTree* extentTree)
1961+ :
1962+ fItem(NULL)
1963+{
1964+ fCurrentExtentTree = new(std::nothrow) BTree(extentTree->SystemVolume(),
1965+ extentTree->RootBlock());
1966+}
1967+
1968+
1969+BlockGroup::~BlockGroup()
1970+{
1971+ if (fItem != NULL) {
1972+ free(fItem);
1973+ fItem = NULL;
1974+ }
1975+
1976+ delete fCurrentExtentTree;
1977+ fCurrentExtentTree = NULL;
1978+}
1979+
1980+
1981+status_t
1982+BlockGroup::SetExtentTree(off_t rootAddress)
1983+{
1984+ status_t status = fCurrentExtentTree->SetRoot(rootAddress, NULL);
1985+ if (status != B_OK)
1986+ return status;
1987+
1988+ if (fItem != NULL) {
1989+ // re-allocate BlockGroup;
1990+ uint64 flags = Flags();
1991+ return Initialize(flags);
1992+ }
1993+
1994+ return B_OK;
1995+}
1996+
1997+
1998+/* Initialize BlockGroup that has flag
1999+ */
2000+status_t
2001+BlockGroup::Initialize(uint64 flag)
2002+{
2003+ if (fCurrentExtentTree == NULL)
2004+ return B_NO_MEMORY;
2005+
2006+ if (fItem != NULL)
2007+ free(fItem);
2008+
2009+ TRACE("BlockGroup::Initialize() find block group has flag: %"
2010+ B_PRIu64 "\n", flag);
2011+ BTree::Path path(fCurrentExtentTree);
2012+ fKey.SetObjectID(0);
2013+ // find first item in extent to get the ObjectID
2014+ // ignore type because block_group is not always the first item
2015+ fKey.SetType(BTRFS_KEY_TYPE_ANY);
2016+ fCurrentExtentTree->FindNext(&path, fKey, NULL);
2017+
2018+ fKey.SetType(BTRFS_KEY_TYPE_BLOCKGROUP_ITEM);
2019+ fKey.SetOffset(0);
2020+ status_t status;
2021+
2022+ while(true) {
2023+ status = fCurrentExtentTree->FindNext(&path, fKey, (void**)&fItem);
2024+ if ((Flags() & flag) == flag || status != B_OK)
2025+ break;
2026+ fKey.SetObjectID(End());
2027+ fKey.SetOffset(0);
2028+ }
2029+
2030+ if (status != B_OK)
2031+ ERROR("BlockGroup::Initialize() cannot find block group\n");
2032+
2033+ return status;
2034+}
2035+
2036+
2037+status_t
2038+BlockGroup::LoadExtent(CachedExtentTree* tree, bool inverse)
2039+{
2040+ if (fItem == NULL)
2041+ return B_NO_INIT;
2042+
2043+ uint64 flags = (Flags() & BTRFS_BLOCKGROUP_FLAG_DATA) != 0 ?
2044+ BTRFS_EXTENT_FLAG_DATA : BTRFS_EXTENT_FLAG_TREE_BLOCK;
2045+ if (inverse == false)
2046+ flags |= BTRFS_EXTENT_FLAG_ALLOCATED;
2047+
2048+ uint64 start = Start();
2049+ CachedExtent* insert;
2050+ void* data;
2051+ uint64 extentSize = fCurrentExtentTree->SystemVolume()->BlockSize();
2052+
2053+ btrfs_key key;
2054+ key.SetType(BTRFS_KEY_TYPE_METADATA_ITEM);
2055+ if ((flags & BTRFS_EXTENT_FLAG_DATA) != 0)
2056+ key.SetType(BTRFS_KEY_TYPE_EXTENT_ITEM);
2057+ key.SetObjectID(start);
2058+ key.SetOffset(0);
2059+
2060+ TreeIterator iterator(fCurrentExtentTree, key);
2061+ status_t status;
2062+ while(true) {
2063+ status = iterator.GetNextEntry(&data);
2064+ key = iterator.Key();
2065+ if (status != B_OK) {
2066+ if (key.ObjectID() != Start())
2067+ break;
2068+ // When we couldn't find the item and key has
2069+ // objectid == BlockGroup's objectID, because
2070+ // key's type < BLOCKGROUP_ITEM
2071+ continue;
2072+ }
2073+
2074+ if (inverse == false) {
2075+ if ((flags & BTRFS_EXTENT_FLAG_DATA) != 0)
2076+ extentSize = key.Offset();
2077+ insert = CachedExtent::Create(key.ObjectID(), extentSize, flags);
2078+ insert->item = (btrfs_extent*)data;
2079+ } else {
2080+ extentSize = key.ObjectID() - start;
2081+ insert = CachedExtent::Create(start, extentSize, flags);
2082+ free(data); // free extent doesn't have data;
2083+ }
2084+ _InsertExtent(tree, insert);
2085+ start = key.ObjectID() + extentSize;
2086+ }
2087+
2088+ if (inverse == true)
2089+ _InsertExtent(tree, start, End() - start, flags);
2090+
2091+ return B_OK;
2092+}
2093+
2094+
2095+status_t
2096+BlockGroup::_InsertExtent(CachedExtentTree* tree, uint64 start, uint64 length,
2097+ uint64 flags)
2098+{
2099+ CachedExtent* extent = CachedExtent::Create(start, length, flags);
2100+ return _InsertExtent(tree, extent);
2101+}
2102+
2103+
2104+status_t
2105+BlockGroup::_InsertExtent(CachedExtentTree* tree, CachedExtent* extent)
2106+{
2107+ if (extent->length == 0)
2108+ return B_BAD_VALUE;
2109+
2110+ status_t status = tree->AddExtent(extent);
2111+ if (status != B_OK) {
2112+ return status;
2113+ }
2114+ return B_OK;
2115+}
2116+
2117+
2118+// ExtentAllocator
2119+
2120+
2121+ExtentAllocator::ExtentAllocator(Volume* volume)
2122+ :
2123+ fVolume(volume),
2124+ fTree(NULL),
2125+ fStart((uint64)-1),
2126+ fEnd(0)
2127+{
2128+ fTree = new(std::nothrow) CachedExtentTree(TreeDefinition());
2129+}
2130+
2131+
2132+ExtentAllocator::~ExtentAllocator()
2133+{
2134+ delete fTree;
2135+ fTree = NULL;
2136+}
2137+
2138+
2139+status_t
2140+ExtentAllocator::_LoadExtentTree(uint64 flags)
2141+{
2142+ TRACE("ExtentAllocator::_LoadExtentTree() flags: %" B_PRIu64 "\n", flags);
2143+ BlockGroup blockGroup(fVolume->ExtentTree());
2144+ status_t status = blockGroup.Initialize(flags);
2145+ if (status != B_OK)
2146+ return status;
2147+
2148+ for (int i = 0; i < BTRFS_NUM_ROOT_BACKUPS; i++) {
2149+ uint64 extentRootAddr =
2150+ fVolume->SuperBlock().backup_roots[i].ExtentRoot();
2151+ if (extentRootAddr == 0)
2152+ continue; // new device has 0 root address
2153+
2154+ status = blockGroup.SetExtentTree(extentRootAddr);
2155+ if (status != B_OK)
2156+ return status;
2157+ status = blockGroup.LoadExtent(fTree, false);
2158+ if (status != B_OK)
2159+ return status;
2160+ }
2161+
2162+ if (fTree->IsEmpty()) // 4 backup roots is 0
2163+ return B_OK;
2164+
2165+ uint64 lowerBound = blockGroup.Start();
2166+ uint64 upperBound = blockGroup.End();
2167+ status = fTree->FillFreeExtents(lowerBound, upperBound);
2168+ if (status != B_OK) {
2169+ ERROR("ExtentAllocator::_LoadExtentTree() could not fill free extents"
2170+ "start %" B_PRIu64 " end %" B_PRIu64 "\n", lowerBound,
2171+ upperBound);
2172+ return status;
2173+ }
2174+
2175+ if (fStart > lowerBound)
2176+ fStart = lowerBound;
2177+ if (fEnd < upperBound)
2178+ fEnd = upperBound;
2179+ return B_OK;
2180+}
2181+
2182+
2183+status_t
2184+ExtentAllocator::Initialize()
2185+{
2186+ TRACE("ExtentAllocator::Initialize()\n");
2187+ if (fTree == NULL)
2188+ return B_NO_MEMORY;
2189+
2190+ status_t status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_DATA);
2191+ if (status != B_OK) {
2192+ ERROR("ExtentAllocator:: could not load exent tree (data)\n");
2193+ return status;
2194+ }
2195+
2196+ status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_SYSTEM);
2197+ if (status != B_OK) {
2198+ ERROR("ExtentAllocator:: could not load exent tree (system)\n");
2199+ return status;
2200+ }
2201+
2202+ status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_METADATA);
2203+ if (status != B_OK) {
2204+ ERROR("ExtentAllocator:: could not load exent tree (metadata)\n");
2205+ return status;
2206+ }
2207+
2208+ fTree->DumpInOrder();
2209+ return B_OK;
2210+}
2211+
2212+
2213+/* Allocate extent that
2214+ * startwith or after "start" and has size >= "size"
2215+ * For now the allocating strategy is "first fit"
2216+ */
2217+status_t
2218+ExtentAllocator::_Allocate(uint64& found, uint64 start, uint64 size,
2219+ uint64 type)
2220+{
2221+ TRACE("ExtentAllocator::_Allocate() start %" B_PRIu64 " size %" B_PRIu64 " type %"
2222+ B_PRIu64 "\n", start, size, type);
2223+ CachedExtent* chosen;
2224+ status_t status;
2225+ while(true) {
2226+ status = fTree->FindNext(&chosen, start, size, type);
2227+ if (status != B_OK)
2228+ return status;
2229+
2230+ if (TreeDefinition().Compare(start, chosen) == 0) {
2231+ if (chosen->End() - start >= size) {
2232+ // if covered and have enough space for allocating
2233+ break;
2234+ }
2235+ start = chosen->End(); // set new start and retry
2236+ } else
2237+ start = chosen->offset;
2238+ }
2239+
2240+ TRACE("ExtentAllocator::_Allocate() found %" B_PRIu64 "\n", start);
2241+ chosen = CachedExtent::Create(start, size,
2242+ type | BTRFS_EXTENT_FLAG_ALLOCATED);
2243+ status = fTree->AddExtent(chosen);
2244+ if (status != B_OK)
2245+ return status;
2246+
2247+ found = start;
2248+ return B_OK;
2249+}
2250+
2251+
2252+// Allocate block for metadata
2253+// flags is BLOCKGROUP's flags
2254+status_t
2255+ExtentAllocator::AllocateTreeBlock(uint64& found, uint64 start, uint64 flags)
2256+{
2257+ // TODO: implement more features here with flags, e.g DUP, RAID, etc
2258+
2259+ BlockGroup blockGroup(fVolume->ExtentTree());
2260+ status_t status = blockGroup.Initialize(flags);
2261+ if (status != B_OK)
2262+ return status;
2263+ if (start == (uint64)-1)
2264+ start = blockGroup.Start();
2265+
2266+ // normalize inputs
2267+ uint64 remainder = start % fVolume->BlockSize();
2268+ if (remainder != 0)
2269+ start += fVolume->BlockSize() - remainder;
2270+
2271+ status = _Allocate(found, start, fVolume->BlockSize(),
2272+ BTRFS_EXTENT_FLAG_TREE_BLOCK);
2273+ if (status != B_OK)
2274+ return status;
2275+
2276+ // check here because tree block locate in 2 blockgroups (system and
2277+ // metadata), and there might be a case one can get over the limit.
2278+ if (found >= blockGroup.End())
2279+ return B_BAD_DATA;
2280+ return B_OK;
2281+}
2282+
2283+
2284+// Allocate block for file data
2285+status_t
2286+ExtentAllocator::AllocateDataBlock(uint64& found, uint64 size, uint64 start,
2287+ uint64 flags)
2288+{
2289+ // TODO: implement more features here with flags, e.g DUP, RAID, etc
2290+
2291+ if (start == (uint64)-1) {
2292+ BlockGroup blockGroup(fVolume->ExtentTree());
2293+ status_t status = blockGroup.Initialize(flags);
2294+ if (status != B_OK)
2295+ return status;
2296+ start = blockGroup.Start();
2297+ }
2298+
2299+ // normalize inputs
2300+ uint64 remainder = start % fVolume->SectorSize();
2301+ if (remainder != 0)
2302+ start += fVolume->SectorSize() - remainder;
2303+ size = size / fVolume->SectorSize() * fVolume->SectorSize();
2304+
2305+ return _Allocate(found, start, size, BTRFS_EXTENT_FLAG_DATA);
2306+}
2307diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
2308new file mode 100644
2309index 0000000..310f8ac
2310--- /dev/null
2311+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
2312@@ -0,0 +1,153 @@
2313+#ifndef EXTENT_ALLOCATOR_H
2314+#define EXTENT_ALLOCATOR_H
2315+
2316+
2317+#include "Volume.h"
2318+#include "BTree.h"
2319+
2320+
2321+//#define TRACE_BTRFS
2322+#ifdef TRACE_BTRFS
2323+# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
2324+#else
2325+# define TRACE(x...) ;
2326+#endif
2327+
2328+#define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
2329+
2330+
2331+struct CachedExtent : AVLTreeNode {
2332+ uint64 offset;
2333+ uint64 length;
2334+ int refCount;
2335+ uint64 flags;
2336+ btrfs_extent* item;
2337+
2338+ static CachedExtent* Create(uint64 offset, uint64 length,
2339+ uint64 flags);
2340+ void Delete();
2341+
2342+ uint64 End() const { return offset + length; }
2343+ bool IsAllocated() const;
2344+ bool IsData() const;
2345+
2346+ void Info() const;
2347+
2348+private:
2349+ CachedExtent() {}
2350+ CachedExtent(const CachedExtent& other);
2351+};
2352+
2353+
2354+struct TreeDefinition {
2355+ typedef uint64 Key;
2356+ typedef CachedExtent Value;
2357+
2358+ AVLTreeNode* GetAVLTreeNode(Value* value) const
2359+ {
2360+ return value;
2361+ }
2362+
2363+ Value* GetValue(AVLTreeNode* node) const
2364+ {
2365+ return static_cast<Value*>(node);
2366+ }
2367+
2368+ int Compare(const Key& a, const Value* b) const
2369+ {
2370+ if (a < b->offset)
2371+ return -1;
2372+ if (a >= b->End())
2373+ return 1;
2374+ return 0;
2375+ }
2376+
2377+ int Compare(const Value* a, const Value* b) const
2378+ {
2379+ int comp = Compare(a->offset, b);
2380+ //TODO: check more conditions here if necessary
2381+ return comp;
2382+ }
2383+};
2384+
2385+
2386+struct CachedExtentTree : AVLTree<TreeDefinition> {
2387+public:
2388+ CachedExtentTree(
2389+ const TreeDefinition& definition);
2390+ ~CachedExtentTree();
2391+
2392+ status_t FindNext(CachedExtent** chosen, uint64 offset,
2393+ uint64 size, uint64 type);
2394+ status_t AddExtent(CachedExtent* extent);
2395+ status_t FillFreeExtents(uint64 lowerBound,
2396+ uint64 upperBound);
2397+ void DumpInOrder() const;
2398+ void Delete();
2399+private:
2400+ status_t _AddAllocatedExtent(CachedExtent* node);
2401+ status_t _AddFreeExtent(CachedExtent* node);
2402+ void _CombineFreeExtent(CachedExtent* node);
2403+ void _RemoveExtent(CachedExtent* node);
2404+ void _DumpInOrder(CachedExtent* node) const;
2405+ void _Delete(CachedExtent* node);
2406+};
2407+
2408+
2409+class BlockGroup {
2410+public:
2411+ BlockGroup(BTree* extentTree);
2412+ ~BlockGroup();
2413+
2414+ status_t SetExtentTree(off_t rootAddress);
2415+ status_t Initialize(uint64 flag);
2416+ status_t LoadExtent(CachedExtentTree* tree,
2417+ bool inverse = false);
2418+
2419+ uint64 Flags() const { return fItem->Flags(); }
2420+ uint64 Start() const { return fKey.ObjectID(); }
2421+ uint64 End() const
2422+ { return fKey.ObjectID() + fKey.Offset(); }
2423+
2424+private:
2425+ BlockGroup(const BlockGroup&);
2426+ BlockGroup& operator=(const BlockGroup&);
2427+ status_t _InsertExtent(CachedExtentTree* tree,
2428+ uint64 size, uint64 length, uint64 flags);
2429+ status_t _InsertExtent(CachedExtentTree* tree,
2430+ CachedExtent* extent);
2431+
2432+private:
2433+ btrfs_key fKey;
2434+ btrfs_block_group* fItem;
2435+ BTree* fCurrentExtentTree;
2436+};
2437+
2438+
2439+class ExtentAllocator {
2440+public:
2441+ ExtentAllocator(Volume* volume);
2442+ ~ExtentAllocator();
2443+
2444+ status_t Initialize();
2445+ status_t AllocateTreeBlock(uint64& found,
2446+ uint64 start = (uint64)-1,
2447+ uint64 flags = BTRFS_BLOCKGROUP_FLAG_METADATA);
2448+ status_t AllocateDataBlock(uint64& found, uint64 size,
2449+ uint64 start = (uint64)-1,
2450+ uint64 flags = BTRFS_BLOCKGROUP_FLAG_DATA);
2451+private:
2452+ ExtentAllocator(const ExtentAllocator&);
2453+ ExtentAllocator& operator=(const ExtentAllocator&);
2454+ status_t _LoadExtentTree(uint64 flags);
2455+ status_t _Allocate(uint64& found, uint64 start,
2456+ uint64 size, uint64 type);
2457+private:
2458+ Volume* fVolume;
2459+ CachedExtentTree* fTree;
2460+ uint64 fStart;
2461+ uint64 fEnd;
2462+};
2463+
2464+
2465+#endif // EXTENT_ALLOCATOR_H
2466diff --git a/src/add-ons/kernel/file_systems/btrfs/Jamfile b/src/add-ons/kernel/file_systems/btrfs/Jamfile
2467index d408e55..78ba20c 100644
2468--- a/src/add-ons/kernel/file_systems/btrfs/Jamfile
2469+++ b/src/add-ons/kernel/file_systems/btrfs/Jamfile
2470@@ -16,6 +16,7 @@ KernelAddon btrfs :
2471 Chunk.cpp
2472 CRCTable.cpp
2473 DirectoryIterator.cpp
2474+ ExtentAllocator.cpp
2475 Inode.cpp
2476 Volume.cpp
2477 : kernel_libz.a
2478diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2479index dc2fffe..c219d40 100644
2480--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2481+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2482@@ -13,6 +13,7 @@
2483 #include "CachedBlock.h"
2484 #include "Chunk.h"
2485 #include "Inode.h"
2486+#include "ExtentAllocator.h"
2487
2488
2489 //#define TRACE_BTRFS
2490@@ -386,6 +387,16 @@ Volume::Mount(const char* deviceName, uint32 flags)
2491 fChecksumTree->SetRoot(root->LogicalAddress(), NULL);
2492 free(root);
2493
2494+ // Initialize ExtentAllocator;
2495+ fExtentAllocator = new(std::nothrow) ExtentAllocator(this);
2496+ if (fExtentAllocator == NULL)
2497+ return B_NO_MEMORY;
2498+ status = fExtentAllocator->Initialize();
2499+ if (status != B_OK) {
2500+ ERROR("could not initalize extent allocator!\n");
2501+ return status;
2502+ }
2503+
2504 // ready
2505 status = get_vnode(fFSVolume, BTRFS_FIRST_SUBVOLUME,
2506 (void**)&fRootNode);
2507@@ -432,10 +443,12 @@ Volume::Unmount()
2508 delete fChecksumTree;
2509 delete fFSTree;
2510 delete fDevTree;
2511+ delete fExtentAllocator;
2512 fExtentTree = NULL;
2513 fChecksumTree = NULL;
2514 fFSTree = NULL;
2515 fDevTree = NULL;
2516+ fExtentAllocator = NULL;
2517
2518 TRACE("Volume::Unmount(): Putting root node\n");
2519 put_vnode(fFSVolume, RootNode()->ID());
2520diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.h b/src/add-ons/kernel/file_systems/btrfs/Volume.h
2521index d839dc0..a4b292c 100644
2522--- a/src/add-ons/kernel/file_systems/btrfs/Volume.h
2523+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.h
2524@@ -17,6 +17,7 @@ enum volume_flags {
2525 class BTree;
2526 class Chunk;
2527 class Inode;
2528+class ExtentAllocator;
2529
2530
2531 class Volume {
2532@@ -45,6 +46,7 @@ public:
2533 uint32 SectorSize() const { return fSectorSize; }
2534 uint32 BlockSize() const { return fBlockSize; }
2535 Chunk* SystemChunk() const { return fChunk; }
2536+ ExtentAllocator* GetAllocator() const { return fExtentAllocator; }
2537
2538 btrfs_super_block& SuperBlock() { return fSuperBlock; }
2539
2540@@ -72,6 +74,7 @@ private:
2541 void* fBlockCache;
2542 Inode* fRootNode;
2543
2544+ ExtentAllocator* fExtentAllocator;
2545 Chunk* fChunk;
2546 BTree* fChunkTree;
2547 BTree* fRootTree;
2548diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2549index d2f4518..a6b4963 100644
2550--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2551+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2552@@ -449,10 +449,11 @@ struct btrfs_extent_data_ref {
2553 #define BTRFS_EXTENT_DATA_PRE 2
2554 #define BTRFS_EXTENT_FLAG_DATA 1
2555 #define BTRFS_EXTENT_FLAG_TREE_BLOCK 2
2556+#define BTRFS_EXTENT_FLAG_ALLOCATED 4
2557
2558 #define BTRFS_BLOCKGROUP_FLAG_DATA 1
2559 #define BTRFS_BLOCKGROUP_FLAG_SYSTEM 2
2560-#define BTRFS_BLOCKGROUP_FLAG_METADA 4
2561+#define BTRFS_BLOCKGROUP_FLAG_METADATA 4
2562 #define BTRFS_BLOCKGROUP_FLAG_RAID0 8
2563 #define BTRFS_BLOCKGROUP_FLAG_RAID1 16
2564 #define BTRFS_BLOCKGROUP_FLAG_DUP 32
2565diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
2566index 5029613..99231c8 100644
2567--- a/src/tools/btrfs_shell/Jamfile
2568+++ b/src/tools/btrfs_shell/Jamfile
2569@@ -42,6 +42,7 @@ local btrfsSources =
2570 Chunk.cpp
2571 CRCTable.cpp
2572 DirectoryIterator.cpp
2573+ ExtentAllocator.cpp
2574 Inode.cpp
2575 Volume.cpp
2576 kernel_interface.cpp
2577--
25782.7.4
2579