Ticket #13612: btrfs.patchset3

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