hrev51666 adds 27 changesets to branch 'master'
old head: d87218f79e132dc809e44f01be114bf279082949
new head: 99768086b1493648abee3f076683cc9fefa5923e
overview:
http://cgit.haiku-os.org/haiku/log/?qt=range&q=99768086b149+%5Ed87218f79e13
----------------------------------------------------------------------------
e7156146138d: AVLTree: forward LeftMost and RightMost method from AVLTreeBase
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
2ed88a489c8a: BTRFS: Fix node search slot
* Not handle traversing type correctly (looks for the graph).
* Reorder the codes because *slot is uninitialized if type is BTREE_EXACT.
* Incorrect return type: int32 -> status_t
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
16de9db54bf6: BTRFS: Fix mismatched type of item size (should be uint32), and
ObjectID of first subvolume when lookup directory (described in commit bd2dab1)
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
8160f31fc102: BTRFS: Node now holding Volume instead of cache to retrieve more
values
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
3216460dec54: BTRFS: Implement BTree::Path and change _Find.
Remove attribute fCurrentSlot in BTree::Node as it will be handled by Path
explicitly. BTree control Path by passing its type in
BTree's method, Path also hold BTree type as its attribute to do some
internal actions.
Add constant BTREE_KEY_TYPE_ANY, find search key has this type will success
regardless of the found key's type.
Split the the _Find function into Traverse and GetEntry. Traverse will fill
in the Path (nodes and slots) along way its finding,
GetEntry will get the item data, item size, key from leaf, if the slot is
valid, that we have from Traverse. The _Find function also
check type if is correct and then retrieve. Doing this way there will be more
flexible, the "read" flag is not needed as we only
need Path to manipulate tree, and it also enhance the performance at some
points, because Path caches all the nodes from root to leaf,
so that we don't have to block_cache_put and block_cache_get after each
finding.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
bfd7a4fb4274: BTRFS: Reimplement TreeIterator, add some error checks and remove
redundancies.
Add BTree::Path as a attribute so enhance performance, so that everytime we
iterate through items it wont search all the root to leaf
again. The Iterator is initialized without rewinding to make more flexible.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
af419b0e9831: BTRFS: Implement ExtentAllocator
There are 4 new classes, structs:
* 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,
that is incremented each time a new extent refer to it (COW) and item data,
that is only for allocated extent (NULL for free).
* CachedTreeExtent, is a AVLTree, cache the whole extent tree and has
CachedExtent as its node.
* 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
responsible for inserting nodes in CachedTreeExtent.
* And the final, ExtentAllocator it knows how to allocate/deallocate extents,
but for now only the allocating is implemented, actually allocating and
deallocating works
are already implemented, they are in functions _AddFreeExtent,
_AddAllocatedExtent in CachedTreeExtent. However the deallocating is not needed
for now, so it will be
finished later then.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
0deb03560f57: BTRFS: Fix mismatched type of index in inode_ref item.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
8137f447cb15: BTRFS: Fix memory leak
Missing delete for some tree roots.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
1750cd1e9227: block_cache: Implement cache_has_block_in_transaction function
that will check the existence of block in one specific transaction.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
c1320b3a3341: BTRFS: Implement a simple journaling approach, this is not
finished and mostly satisfy the need for passing Transaction object for many
functions.
Some details about the current Journal:
* Journal can only end transaction.
* It holds a transaction id of fs (fCurrentGeneration) that increments each
time a transaction starts.
* _TransactionWritten now just printing message.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
4368661f03c3: BTRFS: Implement GetNewBlock() function that will find the
logical address for allocating and convert it to physical block.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
27ffe0583b71: BTRFS: Implement some space relevant helpers.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
89484dc08d8e: BTRFS: Implement some copy relevant helpers.
Copy() copys data from other node, MoveEntries() changes data on the current
node.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
883b9bf29fae: BTRFS: Implement CopyOnWrite relevant functions, and BTree holds
new attribute that record its root level.
CopyOnWrite works like this:
* Cache original node
* Allocating new block
* Cache new block to be writable
* Copy original node to new node, and changing.
Also if a node is already be COW-ed it cannot be COW-ed again, it will be
changed in-place instead.
InternalCopy does CopyOnWrite all the nodes that we don't need to change
anything on them.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
2b6c2ec3905e: fs_shell: Added socket filetype.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
02bce792d846: BTRFS: Added function to convert standard filetypes to btrfs
filetypes.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
84bc447cae63: BTRFS: Implement InsertEntries() that will insert consecutive
items and its data.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
20185bb9c399: BTRFS: Implement RemoveEntries() for BTree that will remove
consecutive items and its data.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
36a24fb34ef0: BTRFS: Implement Create() that allocate new Inode object.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
371935de1870: BTRFS: Implement Insert() in Inode that inserts inode_item.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
b44d924df453: BTRFS: Implement MakeReference() in Inode that will link file
name to inode.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
8042a045b0af: BTRFS: Implement Remove() in Inode that removes inode_item.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
a9e85cb62f27: BTRFS: Implement Dereference() in Inode that remove the "name"
and unlink it with inode.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
166917c9cdf7: BTRFS: Implement btrfs_create_dir that can create directories in
most case.
We need to handle a case when node is full, the solution should be split or
push data to another node.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
4896a3735e1c: BTRFS: Implement btrfs_remove_dir that can remove directories in
most case.
We need to handle a case when node size is small reasonably it can be merged
with another node or push data from other node to this node.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
99768086b149: BTRFS: Add author and license.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
[ hyche <cvghy116@xxxxxxxxx> ]
----------------------------------------------------------------------------
32 files changed, 2599 insertions(+), 188 deletions(-)
headers/os/drivers/fs_cache.h | 1 +
headers/private/fs_shell/fssh_api_wrapper.h | 16 +-
headers/private/fs_shell/fssh_fs_cache.h | 2 +
headers/private/fs_shell/fssh_stat.h | 1 +
headers/private/kernel/util/AVLTree.h | 27 +
.../kernel/file_systems/btrfs/Attribute.cpp | 12 +-
.../kernel/file_systems/btrfs/Attribute.h | 3 +-
.../file_systems/btrfs/AttributeIterator.cpp | 10 +-
.../file_systems/btrfs/AttributeIterator.h | 1 +
src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 873 +++++++++++++++++--
src/add-ons/kernel/file_systems/btrfs/BTree.h | 166 +++-
.../kernel/file_systems/btrfs/CachedBlock.h | 1 +
src/add-ons/kernel/file_systems/btrfs/Chunk.cpp | 1 +
src/add-ons/kernel/file_systems/btrfs/Chunk.h | 1 +
.../file_systems/btrfs/DirectoryIterator.cpp | 18 +-
.../file_systems/btrfs/DirectoryIterator.h | 1 +
.../file_systems/btrfs/ExtentAllocator.cpp | 698 +++++++++++++++
.../kernel/file_systems/btrfs/ExtentAllocator.h | 157 ++++
src/add-ons/kernel/file_systems/btrfs/Inode.cpp | 237 ++++-
src/add-ons/kernel/file_systems/btrfs/Inode.h | 16 +
src/add-ons/kernel/file_systems/btrfs/Jamfile | 2 +
.../kernel/file_systems/btrfs/Journal.cpp | 169 ++++
src/add-ons/kernel/file_systems/btrfs/Journal.h | 62 ++
src/add-ons/kernel/file_systems/btrfs/Utility.h | 27 +
src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 81 +-
src/add-ons/kernel/file_systems/btrfs/Volume.h | 15 +
src/add-ons/kernel/file_systems/btrfs/btrfs.h | 61 +-
.../file_systems/btrfs/kernel_interface.cpp | 93 +-
.../file_systems/btrfs/system_dependencies.h | 4 +
src/system/kernel/cache/block_cache.cpp | 15 +
src/tools/btrfs_shell/Jamfile | 2 +
src/tools/fs_shell/block_cache.cpp | 14 +
############################################################################
Commit: e7156146138d6422c1d4d87d60ac526c898139d6
URL: http://cgit.haiku-os.org/haiku/commit/?id=e7156146138d
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 5 13:23:52 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:08 2017 UTC
AVLTree: forward LeftMost and RightMost method from AVLTreeBase
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/AVLTree.h
b/headers/private/kernel/util/AVLTree.h
index 76d6b25..f0e27f8 100644
--- a/headers/private/kernel/util/AVLTree.h
+++ b/headers/private/kernel/util/AVLTree.h
@@ -47,6 +47,9 @@ public:
Value* Previous(Value* value)
const;
Value* Next(Value* value)
const;
+ Value* LeftMost(Value* value)
const;
+ Value* RightMost(Value* value)
const;
+
inline Iterator GetIterator();
inline ConstIterator GetIterator() const;
@@ -256,6 +259,30 @@ AVLTree<Definition>::Next(Value* value) const
template<typename Definition>
+inline typename AVLTree<Definition>::Value*
+AVLTree<Definition>::LeftMost(Value* value) const
+{
+ if (value == NULL)
+ return NULL;
+
+ AVLTreeNode* node = fTree.LeftMost(_GetAVLTreeNode(value));
+ return node != NULL ? _GetValue(node) : NULL;
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::Value*
+AVLTree<Definition>::RightMost(Value* value) const
+{
+ if (value == NULL)
+ return NULL;
+
+ AVLTreeNode* node = fTree.RightMost(_GetAVLTreeNode(value));
+ return node != NULL ? _GetValue(node) : NULL;
+}
+
+
+template<typename Definition>
inline typename AVLTree<Definition>::Iterator
AVLTree<Definition>::GetIterator()
{
############################################################################
Commit: 2ed88a489c8a06caa47b7d5f104e08a868d9ec3d
URL: http://cgit.haiku-os.org/haiku/commit/?id=2ed88a489c8a
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 5 13:28:00 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:08 2017 UTC
BTRFS: Fix node search slot
* Not handle traversing type correctly (looks for the graph).
* Reorder the codes because *slot is uninitialized if type is BTREE_EXACT.
* Incorrect return type: int32 -> status_t
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
index fec0dee..56813a0 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
@@ -90,8 +90,9 @@ BTree::Node::SetToWritable(off_t block, int32 transactionId,
bool empty)
}
-int32
-BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing
type) const
+status_t
+BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
+ const
{
//binary search for item slot in a node
int entrySize = sizeof(btrfs_entry);
@@ -100,14 +101,13 @@ BTree::Node::SearchSlot(const btrfs_key& key, int* slot,
btree_traversing type)
entrySize = sizeof(btrfs_index);
}
- int low = 0;
int high = ItemCount();
- int mid, comp;
- int base = sizeof(btrfs_header);
+ int low = 0, mid = 0, comp = 0;
+ uint8* base = (uint8*)fNode + sizeof(btrfs_header);
const btrfs_key* other;
while (low < high) {
mid = (low + high) / 2;
- other = (const btrfs_key*)((uint8*)fNode + base + mid *
entrySize);
+ other = (const btrfs_key*)(base + mid * entrySize);
comp = key.Compare(*other);
if (comp < 0)
high = mid;
@@ -119,15 +119,25 @@ BTree::Node::SearchSlot(const btrfs_key& key, int* slot,
btree_traversing type)
}
}
- TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
- *slot, comp);
- if (type == BTREE_BACKWARD)
- *slot = low - 1;
- else if (type == BTREE_FORWARD)
- *slot = low;
+ // |--item1--|--item2--|--item3--|--etc--|
+ // m-1 m m+1
+ // k : comp < 0
+ // k : comp > 0
+ if (type == BTREE_BACKWARD) {
+ *slot = mid - 1;
+ if (comp > 0)
+ *slot = mid;
+ } else if (type == BTREE_FORWARD) {
+ *slot = mid;
+ if (comp > 0)
+ *slot = mid + 1;
+ }
- if (*slot < 0 || type == BTREE_EXACT)
+ if (type == BTREE_EXACT || *slot < 0)
return B_ENTRY_NOT_FOUND;
+
+ TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
+ *slot, comp);
return B_OK;
}
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h
b/src/add-ons/kernel/file_systems/btrfs/BTree.h
index eebd132..2fa8837 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
@@ -119,8 +119,8 @@ public:
off_t BlockNum() const { return fBlockNumber;}
bool IsWritable() const { return fWritable; }
- int32 SearchSlot(const btrfs_key& key, int* slot,
- btree_traversing type) const;
+ status_t SearchSlot(const btrfs_key& key, int* slot,
+ btree_traversing type) const;
private:
Node(const Node&);
Node& operator=(const Node&);
############################################################################
Commit: 16de9db54bf69fe8d02b228ff706026828f9cb7a
URL: http://cgit.haiku-os.org/haiku/commit/?id=16de9db54bf6
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 12 09:50:07 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:09 2017 UTC
BTRFS: Fix mismatched type of item size (should be uint32), and ObjectID of
first subvolume when lookup directory (described in commit bd2dab1)
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
index ecb25ac..ddda28d 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
@@ -88,7 +88,7 @@ Attribute::Stat(struct stat& stat)
size_t nameLength = strlen(fName);
btrfs_dir_entry* entries;
- size_t length;
+ uint32 length;
status_t status = _Lookup(fName, nameLength, &entries, &length);
if (status < B_OK)
return status;
@@ -116,7 +116,7 @@ Attribute::Read(attr_cookie* cookie, off_t pos, uint8*
buffer, size_t* _length)
size_t nameLength = strlen(fName);
btrfs_dir_entry* entries;
- size_t length;
+ uint32 length;
status_t status = _Lookup(fName, nameLength, &entries, &length);
if (status < B_OK)
return status;
@@ -144,7 +144,7 @@ Attribute::Read(attr_cookie* cookie, off_t pos, uint8*
buffer, size_t* _length)
status_t
Attribute::_Lookup(const char* name, size_t nameLength,
- btrfs_dir_entry** _entries, size_t* _length)
+ btrfs_dir_entry** _entries, uint32* _length)
{
uint32 hash = calculate_crc((uint32)~1, (uint8*)name, nameLength);
struct btrfs_key key;
@@ -153,7 +153,7 @@ Attribute::_Lookup(const char* name, size_t nameLength,
key.SetOffset(hash);
btrfs_dir_entry* entries;
- size_t length;
+ uint32 length;
status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
(void**)&entries, &length);
if (status != B_OK) {
diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.h
b/src/add-ons/kernel/file_systems/btrfs/Attribute.h
index 7236673..ebbb3e9 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.h
+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.h
@@ -39,7 +39,7 @@ public:
private:
status_t _Lookup(const char*
name, size_t nameLength,
btrfs_dir_entry** entries = NULL,
- size_t*
length = NULL);
+ uint32*
length = NULL);
status_t
_FindEntry(btrfs_dir_entry* entries,
size_t
length, const char* name,
size_t
nameLength,
diff --git a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
index 3b67e83..f453a11 100644
--- a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
@@ -48,7 +48,7 @@ AttributeIterator::GetNext(char* name, size_t* _nameLength)
{
btrfs_key key;
btrfs_dir_entry* entries;
- size_t entries_length;
+ uint32 entries_length;
status_t status = fIterator->GetPreviousEntry(key, (void**)&entries,
&entries_length);
if (status != B_OK)
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
index 56813a0..726aa84 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
@@ -212,7 +212,7 @@ btrfs_key::Compare(const btrfs_key& key) const
It can also return other errors to indicate that something went wrong.
*/
status_t
-BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
+BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
bool read, btree_traversing type)
{
TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
@@ -268,21 +268,21 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
status_t
-BTree::FindNext(btrfs_key& key, void** _value, size_t* _size, bool read)
+BTree::FindNext(btrfs_key& key, void** _value, uint32* _size, bool read)
{
return _Find(key, _value, _size, read, BTREE_FORWARD);
}
status_t
-BTree::FindPrevious(btrfs_key& key, void** _value, size_t* _size, bool read)
+BTree::FindPrevious(btrfs_key& key, void** _value, uint32* _size, bool read)
{
return _Find(key, _value, _size, read, BTREE_BACKWARD);
}
status_t
-BTree::FindExact(btrfs_key& key, void** _value, size_t* _size, bool read)
+BTree::FindExact(btrfs_key& key, void** _value, uint32* _size, bool read)
{
return _Find(key, _value, _size, read, BTREE_EXACT);
}
@@ -345,7 +345,7 @@ TreeIterator::~TreeIterator()
*/
status_t
TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
- void** value, size_t* size)
+ void** value, uint32* size)
{
if (fTree == NULL)
return B_INTERRUPTED;
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h
b/src/add-ons/kernel/file_systems/btrfs/BTree.h
index 2fa8837..5a40fea 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
@@ -3,8 +3,8 @@
* Copyright 2001-2010, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx.
* This file may be used under the terms of the MIT License.
*/
-#ifndef B_PLUS_TREE_H
-#define B_PLUS_TREE_H
+#ifndef B_TREE_H
+#define B_TREE_H
#include "btrfs.h"
@@ -50,11 +50,11 @@ public:
fsblock_t rootBlock);
~BTree();
status_t FindExact(btrfs_key&
key, void** value,
- size_t*
size = NULL, bool read = true);
+ uint32*
size = NULL, bool read = true);
status_t FindNext(btrfs_key&
key, void** value,
- size_t*
size = NULL, bool read = true);
+ uint32*
size = NULL, bool read = true);
status_t FindPrevious(btrfs_key&
key, void** value,
- size_t*
size = NULL, bool read = true);
+ uint32*
size = NULL, bool read = true);
Volume* SystemVolume() const {
return fVolume; }
@@ -67,7 +67,7 @@ private:
BTree&
operator=(const BTree& other);
// no
implementation
- status_t _Find(btrfs_key& key,
void** value, size_t* size,
+ status_t _Find(btrfs_key& key,
void** value, uint32* size,
bool
read, btree_traversing type);
void
_AddIterator(TreeIterator* iterator);
void
_RemoveIterator(TreeIterator* iterator);
@@ -153,14 +153,14 @@ public:
status_t
Traverse(btree_traversing direction,
btrfs_key& key, void** value,
- size_t*
size = NULL);
+ uint32*
size = NULL);
status_t Find(btrfs_key& key);
status_t Rewind();
status_t GetNextEntry(btrfs_key&
key, void** value,
- size_t*
size = NULL);
+ uint32*
size = NULL);
status_t
GetPreviousEntry(btrfs_key& key, void** value,
- size_t*
size = NULL);
+ uint32*
size = NULL);
BTree* Tree() const { return fTree; }
@@ -188,7 +188,7 @@ TreeIterator::Rewind()
inline status_t
-TreeIterator::GetNextEntry(btrfs_key& key, void** value, size_t* size)
+TreeIterator::GetNextEntry(btrfs_key& key, void** value, uint32* size)
{
return Traverse(BTREE_FORWARD, key, value, size);
}
@@ -196,10 +196,10 @@ TreeIterator::GetNextEntry(btrfs_key& key, void** value,
size_t* size)
inline status_t
TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
- size_t* size)
+ uint32* size)
{
return Traverse(BTREE_BACKWARD, key, value, size);
}
-#endif // B_PLUS_TREE_H
+#endif // B_TREE_H
diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
index b19dabf..4f9a1b7 100644
--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
@@ -33,7 +33,8 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
DirectoryIterator::~DirectoryIterator()
{
- delete fIterator;
+ if (fIterator != NULL)
+ delete fIterator;
}
@@ -61,7 +62,7 @@ DirectoryIterator::GetNext(char* name, size_t* _nameLength,
ino_t* _id)
*_nameLength = 1;
strlcpy(name, ".", *_nameLength + 1);
fOffset = 2;
- if (fInode->ID() == BTRFS_OBJECT_ID_CHUNK_TREE) {
+ if (fInode->ID() == BTRFS_FIRST_SUBVOLUME) {
*_id = fInode->ID();
return B_OK;
}
@@ -70,7 +71,7 @@ DirectoryIterator::GetNext(char* name, size_t* _nameLength,
ino_t* _id)
btrfs_key key;
btrfs_dir_entry* entries;
- size_t entries_length;
+ uint32 entries_length;
status_t status = fIterator->GetNextEntry(key, (void**)&entries,
&entries_length);
if (status != B_OK)
@@ -110,7 +111,7 @@ DirectoryIterator::Lookup(const char* name, size_t
nameLength, ino_t* _id)
{
if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0) {
if (strcmp(name, ".") == 0
- || fInode->ID() == BTRFS_OBJECT_ID_CHUNK_TREE) {
+ || fInode->ID() == BTRFS_FIRST_SUBVOLUME) {
*_id = fInode->ID();
return B_OK;
}
@@ -124,7 +125,7 @@ DirectoryIterator::Lookup(const char* name, size_t
nameLength, ino_t* _id)
key.SetOffset(hash);
btrfs_dir_entry* entries;
- size_t length;
+ uint32 length;
status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
(void**)&entries, &length);
if (status != B_OK) {
diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
index ef66d34..a2e7bb8 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
@@ -167,7 +167,7 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
search_key.SetObjectID(fID);
search_key.SetOffset(pos + 1);
- size_t item_size;
+ uint32 item_size;
btrfs_extent_data* extent_data;
status_t status = fVolume->FSTree()->FindPrevious(search_key,
(void**)&extent_data, &item_size);
@@ -222,7 +222,7 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
int status;
ssize_t offset = 0;
- size_t inline_size = item_size - 13;
+ uint32 inline_size = item_size - 13;
bool headerRead = false;
TRACE("Inode::ReadAt(%" B_PRIdINO ") diff %" B_PRIdOFF " size %"
diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
index 561a102..159f67e 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
@@ -486,7 +486,7 @@ Volume::FindBlock(off_t logical, off_t& physical)
search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
btrfs_chunk* chunk;
- size_t chunk_length;
+ uint32 chunk_length;
status_t status = fChunkTree->FindPrevious(search_key, (void**)&chunk,
&chunk_length);
if (status != B_OK)
############################################################################
Commit: 8160f31fc102e46f9c3387b708a51b8807c90b72
URL: http://cgit.haiku-os.org/haiku/commit/?id=8160f31fc102
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 16 13:56:09 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:10 2017 UTC
BTRFS: Node now holding Volume instead of cache to retrieve more values
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
index 726aa84..4ca1ef1 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
@@ -20,10 +20,10 @@
# define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
-BTree::Node::Node(void* cache)
+BTree::Node::Node(Volume* volume)
:
fNode(NULL),
- fCache(cache),
+ fVolume(volume),
fBlockNumber(0),
fCurrentSlot(0),
fWritable(false)
@@ -31,10 +31,10 @@ BTree::Node::Node(void* cache)
}
-BTree::Node::Node(void* cache, off_t block)
+BTree::Node::Node(Volume* volume, off_t block)
:
fNode(NULL),
- fCache(cache),
+ fVolume(volume),
fBlockNumber(0),
fCurrentSlot(0),
fWritable(false)
@@ -59,7 +59,7 @@ void
BTree::Node::Unset()
{
if (fNode != NULL) {
- block_cache_put(fCache, fBlockNumber);
+ block_cache_put(fVolume->BlockCache(), fBlockNumber);
fNode = NULL;
}
}
@@ -70,7 +70,7 @@ BTree::Node::SetTo(off_t block)
{
Unset();
fBlockNumber = block;
- fNode = (btrfs_stream*)block_cache_get(fCache, block);
+ fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
}
@@ -81,11 +81,11 @@ BTree::Node::SetToWritable(off_t block, int32
transactionId, bool empty)
fBlockNumber = block;
fWritable = true;
if (empty) {
- fNode = (btrfs_stream*)block_cache_get_empty(fCache, block,
- transactionId);
+ fNode =
(btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
+ block, transactionId);
} else {
- fNode = (btrfs_stream*)block_cache_get_writable(fCache, block,
- transactionId);
+ fNode =
(btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
+ block, transactionId);
}
}
@@ -217,7 +217,7 @@ BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
{
TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
key.ObjectID(), key.Type(), key.Offset());
- BTree::Node node(fVolume->BlockCache(), fRootBlock);
+ BTree::Node node(fVolume, fRootBlock);
int slot, ret;
fsblock_t physicalBlock;
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h
b/src/add-ons/kernel/file_systems/btrfs/BTree.h
index 5a40fea..bb034dd 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
@@ -83,8 +83,8 @@ private:
public:
class Node {
public:
- Node(void* cache);
- Node(void* cache, off_t block);
+ Node(Volume* volume);
+ Node(Volume* volume, off_t block);
~Node();
// just return from Header
@@ -127,7 +127,7 @@ public:
//no implementation
btrfs_stream* fNode;
- void* fCache;
+ Volume* fVolume;
off_t fBlockNumber;
uint32 fCurrentSlot;
bool fWritable;
############################################################################
Commit: 3216460dec5447c463e617b5dd537ac496dc0370
URL: http://cgit.haiku-os.org/haiku/commit/?id=3216460dec54
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 12 17:30:06 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:11 2017 UTC
BTRFS: Implement BTree::Path and change _Find.
Remove attribute fCurrentSlot in BTree::Node as it will be handled by Path
explicitly. BTree control Path by passing its type in
BTree's method, Path also hold BTree type as its attribute to do some internal
actions.
Add constant BTREE_KEY_TYPE_ANY, find search key has this type will success
regardless of the found key's type.
Split the the _Find function into Traverse and GetEntry. Traverse will fill in
the Path (nodes and slots) along way its finding,
GetEntry will get the item data, item size, key from leaf, if the slot is
valid, that we have from Traverse. The _Find function also
check type if is correct and then retrieve. Doing this way there will be more
flexible, the "read" flag is not needed as we only
need Path to manipulate tree, and it also enhance the performance at some
points, because Path caches all the nodes from root to leaf,
so that we don't have to block_cache_put and block_cache_get after each finding.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
index ddda28d..1c0b286 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
@@ -151,10 +151,11 @@ Attribute::_Lookup(const char* name, size_t nameLength,
key.SetType(BTRFS_KEY_TYPE_XATTR_ITEM);
key.SetObjectID(fInode->ID());
key.SetOffset(hash);
+ BTree::Path path(fInode->GetVolume()->FSTree());
btrfs_dir_entry* entries;
uint32 length;
- status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
+ status_t status = fInode->GetVolume()->FSTree()->FindExact(&path, key,
(void**)&entries, &length);
if (status != B_OK) {
TRACE("AttributeIterator::Lookup(): Couldn't find entry with
hash %"
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
index 4ca1ef1..ce87f5a 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
@@ -25,7 +25,6 @@ BTree::Node::Node(Volume* volume)
fNode(NULL),
fVolume(volume),
fBlockNumber(0),
- fCurrentSlot(0),
fWritable(false)
{
}
@@ -36,7 +35,6 @@ BTree::Node::Node(Volume* volume, off_t block)
fNode(NULL),
fVolume(volume),
fBlockNumber(0),
- fCurrentSlot(0),
fWritable(false)
{
SetTo(block);
@@ -142,7 +140,109 @@ BTree::Node::SearchSlot(const btrfs_key& key, int* slot,
btree_traversing type)
}
-//-pragma mark
+// #pragma mark - BTree::Path implementation
+
+
+BTree::Path::Path(BTree* tree)
+ :
+ fTree(tree)
+{
+ for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
+ fNodes[i] = NULL;
+ fSlots[i] = 0;
+ }
+}
+
+
+BTree::Path::~Path()
+{
+ for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
+ delete fNodes[i];
+ fNodes[i] = NULL;
+ fSlots[i] = 0;
+ }
+}
+
+
+BTree::Node*
+BTree::Path::GetNode(int level, int* _slot) const
+{
+ if (_slot != NULL)
+ *_slot = fSlots[level];
+ return fNodes[level];
+}
+
+
+BTree::Node*
+BTree::Path::SetNode(off_t block, int slot)
+{
+ Node node(fTree->SystemVolume(), block);
+ return SetNode(&node, slot);
+}
+
+
+BTree::Node*
+BTree::Path::SetNode(const Node* node, int slot)
+{
+ uint8 level = node->Level();
+ if (fNodes[level] == NULL) {
+ fNodes[level] = new Node(fTree->SystemVolume(),
node->BlockNum());
+ if (fNodes[level] == NULL)
+ return NULL;
+ } else
+ fNodes[level]->SetTo(node->BlockNum());
+
+ if (slot == -1)
+ fSlots[level] = fNodes[level]->ItemCount() - 1;
+ else
+ fSlots[level] = slot;
+ return fNodes[level];
+}
+
+
+int
+BTree::Path::Move(int level, int step)
+{
+ fSlots[level] += step;
+ if (fSlots[level] < 0)
+ return -1;
+ if (fSlots[level] >= fNodes[level]->ItemCount())
+ return 1;
+ return 0;
+}
+
+
+status_t
+BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
+ uint32* _offset)
+{
+ BTree::Node* leaf = fNodes[0];
+ if (slot < 0 || slot >= leaf->ItemCount())
+ return B_ENTRY_NOT_FOUND;
+
+ if (_key != NULL)
+ *_key = leaf->Item(slot)->key;
+
+ uint32 itemSize = leaf->Item(slot)->Size();
+ if (_value != NULL) {
+ *_value = malloc(itemSize);
+ if (*_value == NULL)
+ return B_NO_MEMORY;
+
+ memcpy(*_value, leaf->ItemData(slot), itemSize);
+ }
+
+ if (_size != NULL)
+ *_size = itemSize;
+
+ if (_offset != NULL)
+ *_offset = leaf->Item(slot)->Offset();
+
+ return B_OK;
+}
+
+
+// #pragma mark - BTree implementation
BTree::BTree(Volume* volume)
@@ -206,85 +306,180 @@ btrfs_key::Compare(const btrfs_key& key) const
}
-/*! Searches the key in the tree, and stores the allocated found item in
- _value, if successful.
- Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
- It can also return other errors to indicate that something went wrong.
-*/
+/* Traverse from root to fill in the path along way its finding.
+ * Return current slot at leaf if successful.
+ */
status_t
-BTree::_Find(btrfs_key& key, void** _value, uint32* _size,
- bool read, btree_traversing type)
+BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
+ const
{
- TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
- key.ObjectID(), key.Type(), key.Offset());
- BTree::Node node(fVolume, fRootBlock);
- int slot, ret;
- fsblock_t physicalBlock;
+ TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
+ B_PRId64 " \n", key.ObjectID(), key.Type(), key.Offset());
+ fsblock_t physicalBlock = fRootBlock;
+ Node node(fVolume, physicalBlock);
+ int slot;
+ status_t status = B_OK;
while (node.Level() != 0) {
- TRACE("Find() level %d\n", node.Level());
- ret = node.SearchSlot(key, &slot, BTREE_BACKWARD);
- if (ret != B_OK)
- return ret;
- TRACE("Find() getting index %" B_PRIu32 "\n", slot);
-
- if (fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
physicalBlock)
- != B_OK) {
- ERROR("Find() unmapped block %" B_PRId64 "\n",
+ TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
+ node.ItemCount());
+ status = node.SearchSlot(key, &slot, BTREE_BACKWARD);
+ if (status != B_OK)
+ return status;
+ if (path->SetNode(&node, slot) == NULL)
+ return B_NO_MEMORY;
+
+ TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);
+
+ status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
+ physicalBlock);
+ if (status != B_OK) {
+ ERROR("BTree::Traverse() unmapped block %" B_PRId64
"\n",
node.Index(slot)->LogicalAddress());
- return B_ERROR;
+ return status;
}
node.SetTo(physicalBlock);
}
- TRACE("Find() dump count %" B_PRId32 "\n", node.ItemCount());
- ret = node.SearchSlot(key, &slot, type);
- if ((slot >= node.ItemCount() || node.Item(slot)->key.Type() !=
key.Type())
- && read == true
- || ret != B_OK) {
- TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n",
key.Offset(),
- key.ObjectID());
+ TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
+ status = node.SearchSlot(key, &slot, type);
+ if (status != B_OK)
+ return status;
+ if (path->SetNode(&node, slot) == NULL)
+ return B_NO_MEMORY;
+
+ TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
+ node.Item(slot)->Offset(), node.Item(slot)->Size());
+ return slot;
+}
+
+
+/*! Searches the key in the tree, and stores the allocated found item in
+ _value, if successful.
+ Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
+ It can also return other errors to indicate that something went wrong.
+*/
+status_t
+BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
+ uint32* _offset, btree_traversing type) const
+{
+ status_t status = Traverse(type, path, wanted);
+ if (status < B_OK)
+ return status;
+
+ btrfs_key found;
+ status = path->GetCurrentEntry(&found, _value, _size, _offset);
+ if (status != B_OK)
+ return status;
+
+ if (found.Type() != wanted.Type() && wanted.Type() !=
BTRFS_KEY_TYPE_ANY)
return B_ENTRY_NOT_FOUND;
- }
- if (read == true) {
- TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
- node.Item(slot)->Offset(), node.Item(slot)->Size());
-
- if (_value != NULL) {
- *_value = malloc(node.Item(slot)->Size());
- memcpy(*_value, node.ItemData(slot),
- node.Item(slot)->Size());
- key.SetOffset(node.Item(slot)->key.Offset());
- key.SetObjectID(node.Item(slot)->key.ObjectID());
- if (_size != NULL)
- *_size = node.Item(slot)->Size();
- }
- } else {
- *_value = (void*)&slot;
- }
+ wanted = found;
return B_OK;
}
status_t
-BTree::FindNext(btrfs_key& key, void** _value, uint32* _size, bool read)
+BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
+ uint32* _offset) const
{
- return _Find(key, _value, _size, read, BTREE_FORWARD);
+ return _Find(path, key, _value, _size, _offset, BTREE_FORWARD);
}
status_t
-BTree::FindPrevious(btrfs_key& key, void** _value, uint32* _size, bool read)
+BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
+ uint32* _offset) const
{
- return _Find(key, _value, _size, read, BTREE_BACKWARD);
+ return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD);
}
status_t
-BTree::FindExact(btrfs_key& key, void** _value, uint32* _size, bool read)
+BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
+ uint32* _offset) const
{
- return _Find(key, _value, _size, read, BTREE_EXACT);
+ return _Find(path, key, _value, _size, _offset, BTREE_EXACT);
+}
+
+
+status_t
+BTree::PreviousLeaf(Path* path) const
+{
+ // TODO: use Traverse() ???
+ int level = 0;
+ int slot;
+ Node* node = NULL;
+ // iterate to the root until satisfy the condition
+ while (true) {
+ node = path->GetNode(level, &slot);
+ if (node == NULL || slot != 0)
+ break;
+ level++;
+ }
+
+ // the current leaf is already the left most leaf or
+ // path was not initialized
+ if (node == NULL)
+ return B_ENTRY_NOT_FOUND;
+
+ path->Move(level, BTREE_BACKWARD);
+ fsblock_t physicalBlock;
+ // change all nodes below this level and slot to the ending
+ do {
+ status_t status = fVolume->FindBlock(
+ node->Index(slot)->LogicalAddress(), physicalBlock);
+ if (status != B_OK)
+ return status;
+
+ node = path->SetNode(physicalBlock, -1);
+ if (node == NULL)
+ return B_NO_MEMORY;
+ slot = node->ItemCount() - 1;
+ level--;
+ } while(level != 0);
+
+ return B_OK;
+}
+
+
+status_t
+BTree::NextLeaf(Path* path) const
+{
+ int level = 0;
+ int slot;
+ Node* node = NULL;
+ // iterate to the root until satisfy the condition
+ while (true) {
+ node = path->GetNode(level, &slot);
+ if (node == NULL || slot < node->ItemCount() - 1)
+ break;
+ level++;
+ }
+
+ // the current leaf is already the right most leaf or
+ // path was not initialized
+ if (node == NULL)
+ return B_ENTRY_NOT_FOUND;
+
+ path->Move(level, BTREE_FORWARD);
+ fsblock_t physicalBlock;
+ // change all nodes below this level and slot to the beginning
+ do {
+ status_t status = fVolume->FindBlock(
+ node->Index(slot)->LogicalAddress(), physicalBlock);
+ if (status != B_OK)
+ return status;
+
+ node = path->SetNode(physicalBlock, 0);
+ if (node == NULL)
+ return B_NO_MEMORY;
+ slot = 0;
+ level--;
+ } while(level != 0);
+
+ return B_OK;
}
@@ -351,8 +546,8 @@ TreeIterator::Traverse(btree_traversing direction,
btrfs_key& key,
return B_INTERRUPTED;
fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
- status_t status = fTree->_Find(fCurrentKey, value, size,
- true, direction);
+ BTree::Path path(fTree);
+ status_t status = fTree->_Find(&path, fCurrentKey, value, size,
direction);
if (status != B_OK) {
TRACE("TreeIterator::Traverse() Find failed\n");
return B_ENTRY_NOT_FOUND;
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h
b/src/add-ons/kernel/file_systems/btrfs/BTree.h
index bb034dd..30afcaf 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
@@ -43,21 +43,33 @@ struct node_and_key {
class BTree {
public:
+ class Path;
+
+public:
BTree(Volume*
volume);
BTree(Volume*
volume,
btrfs_stream* stream);
BTree(Volume*
volume,
fsblock_t rootBlock);
~BTree();
- status_t FindExact(btrfs_key&
key, void** value,
- uint32*
size = NULL, bool read = true);
- status_t FindNext(btrfs_key&
key, void** value,
- uint32*
size = NULL, bool read = true);
- status_t FindPrevious(btrfs_key&
key, void** value,
- uint32*
size = NULL, bool read = true);
- Volume* SystemVolume() const {
return fVolume; }
+ status_t FindExact(Path* path,
btrfs_key& key,
+ void**
_value, uint32* _size = NULL,
+ uint32*
_offset = NULL) const;
+ status_t FindNext(Path* path,
btrfs_key& key,
+ void**
_value, uint32* _size = NULL,
+ uint32*
_offset = NULL) const;
+ status_t FindPrevious(Path*
path, btrfs_key& key,
+ void**
_value, uint32* _size = NULL,
+ uint32*
_offset = NULL) const;
+
+ status_t
Traverse(btree_traversing type, Path* path,
+ const
btrfs_key& key) const;
+
+ status_t PreviousLeaf(Path*
path) const;
+ status_t NextLeaf(Path* path)
const;
+ Volume* SystemVolume() const {
return fVolume; }
status_t SetRoot(off_t logical,
fsblock_t* block);
fsblock_t RootBlock() const {
return fRootBlock; }
off_t LogicalRoot() const {
return fLogicalRoot; }
@@ -67,8 +79,10 @@ private:
BTree&
operator=(const BTree& other);
// no
implementation
- status_t _Find(btrfs_key& key,
void** value, uint32* size,
- bool
read, btree_traversing type);
+ status_t _Find(Path* path,
btrfs_key& key,
+ void**
_value, uint32* _size,
+ uint32*
_offset, btree_traversing type)
+ const;
void
_AddIterator(TreeIterator* iterator);
void
_RemoveIterator(TreeIterator* iterator);
private:
@@ -113,8 +127,7 @@ public:
void Unset();
void SetTo(off_t block);
- void SetToWritable(off_t block,
- int32 transactionId, bool empty);
+ void SetToWritable(off_t block, int32 transactionId, bool
empty);
off_t BlockNum() const { return fBlockNumber;}
bool IsWritable() const { return fWritable; }
@@ -129,18 +142,33 @@ public:
btrfs_stream* fNode;
Volume* fVolume;
off_t fBlockNumber;
- uint32 fCurrentSlot;
bool fWritable;
};
class Path {
public:
- Path();
+ Path(BTree* tree);
+ ~Path();
+
+ Node* GetNode(int level, int* _slot = NULL) const;
+ Node* SetNode(off_t block, int slot);
+ Node* SetNode(const Node* node, int slot);
+ status_t GetCurrentEntry(btrfs_key* _key, void** _value,
+ uint32* _size = NULL, uint32*
_offset = NULL);
+ status_t GetEntry(int slot, btrfs_key* _key, void**
_value,
+ uint32* _size = NULL, uint32*
_offset = NULL);
+
+ int Move(int level, int step);
+
+ BTree* Tree() const { return fTree; }
private:
Path(const Path&);
Path operator=(const Path&);
- Node* nodes[BTRFS_MAX_TREE_DEPTH];
+ private:
+ Node* fNodes[BTRFS_MAX_TREE_DEPTH];
+ int fSlots[BTRFS_MAX_TREE_DEPTH];
+ BTree* fTree;
};
}; // class BTree
@@ -176,6 +204,17 @@ private:
};
+// #pragma mark - BTree::Path inline functions
+
+
+inline status_t
+BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
+ uint32* _offset)
+{
+ return GetEntry(fSlots[0], _key, _value, _size, _offset);
+}
+
+
// #pragma mark - TreeIterator inline functions
diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
index 4f9a1b7..ccfd1b2 100644
--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
@@ -123,10 +123,11 @@ DirectoryIterator::Lookup(const char* name, size_t
nameLength, ino_t* _id)
key.SetType(BTRFS_KEY_TYPE_DIR_ITEM);
key.SetObjectID(fInode->ID());
key.SetOffset(hash);
+ BTree::Path path(fInode->GetVolume()->FSTree());
btrfs_dir_entry* entries;
uint32 length;
- status_t status = fInode->GetVolume()->FSTree()->FindExact(key,
+ status_t status = fInode->GetVolume()->FSTree()->FindExact(&path, key,
(void**)&entries, &length);
if (status != B_OK) {
TRACE("DirectoryIterator::Lookup(): Couldn't find entry with
hash %" B_PRIu32
diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
index a2e7bb8..173fe19 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
@@ -78,9 +78,11 @@ Inode::UpdateNodeFromDisk()
search_key.SetType(BTRFS_KEY_TYPE_INODE_ITEM);
search_key.SetObjectID(fID);
search_key.SetOffset(0);
+ BTree::Path path(fVolume->FSTree());
btrfs_inode* node;
- if (fVolume->FSTree()->FindExact(search_key, (void**)&node) != B_OK) {
+ if (fVolume->FSTree()->FindExact(&path, search_key, (void**)&node)
+ != B_OK) {
ERROR("Inode::UpdateNodeFromDisk(): Couldn't find inode %"
B_PRIdINO "\n", fID);
return B_ENTRY_NOT_FOUND;
@@ -111,9 +113,10 @@ Inode::FindBlock(off_t pos, off_t& physical, off_t*
_length)
search_key.SetType(BTRFS_KEY_TYPE_EXTENT_DATA);
search_key.SetObjectID(fID);
search_key.SetOffset(pos + 1);
+ BTree::Path path(fVolume->FSTree());
btrfs_extent_data* extent_data;
- status_t status = fVolume->FSTree()->FindPrevious(search_key,
+ status_t status = fVolume->FSTree()->FindPrevious(&path, search_key,
(void**)&extent_data);
if (status != B_OK) {
ERROR("Inode::FindBlock(): Couldn't find extent_data 0x%"
B_PRIx32
@@ -166,10 +169,11 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
search_key.SetType(BTRFS_KEY_TYPE_EXTENT_DATA);
search_key.SetObjectID(fID);
search_key.SetOffset(pos + 1);
+ BTree::Path path(fVolume->FSTree());
uint32 item_size;
btrfs_extent_data* extent_data;
- status_t status = fVolume->FSTree()->FindPrevious(search_key,
+ status_t status = fVolume->FSTree()->FindPrevious(&path, search_key,
(void**)&extent_data, &item_size);
if (status != B_OK) {
ERROR("Inode::FindBlock(): Couldn't find extent_data 0x%"
B_PRIx32
@@ -292,9 +296,10 @@ Inode::FindParent(ino_t* id)
search_key.SetType(BTRFS_KEY_TYPE_INODE_REF);
search_key.SetObjectID(fID);
search_key.SetOffset(-1);
+ BTree::Path path(fVolume->FSTree());
void* node_ref;
- if (fVolume->FSTree()->FindPrevious(search_key, &node_ref) != B_OK) {
+ if (fVolume->FSTree()->FindPrevious(&path, search_key, &node_ref) !=
B_OK) {
ERROR("Inode::FindParent(): Couldn't find inode for %"
B_PRIdINO "\n",
fID);
return B_ERROR;
diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
index 159f67e..dc2fffe 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
@@ -317,15 +317,18 @@ Volume::Mount(const char* deviceName, uint32 flags)
TRACE("Volume::Mount() root: %" B_PRIu64 " (physical block %" B_PRIu64
")\n",
fSuperBlock.Root(), fRootTree->RootBlock());
+ BTree::Path path(fRootTree);
+
TRACE("Volume::Mount(): Searching extent root\n");
btrfs_key search_key;
search_key.SetOffset(0);
search_key.SetType(BTRFS_KEY_TYPE_ROOT_ITEM);
search_key.SetObjectID(BTRFS_OBJECT_ID_EXTENT_TREE);
btrfs_root* root;
- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
+ if (status != B_OK) {
ERROR("Volume::Mount(): Couldn't find extent root\n");
- return B_ERROR;
+ return status;
}
TRACE("Volume::Mount(): Found extent root: %" B_PRIu64 "\n",
root->LogicalAddress());
@@ -338,9 +341,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
TRACE("Volume::Mount(): Searching fs root\n");
search_key.SetOffset(0);
search_key.SetObjectID(BTRFS_OBJECT_ID_FS_TREE);
- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
+ if (status != B_OK) {
ERROR("Volume::Mount(): Couldn't find fs root\n");
- return B_ERROR;
+ return status;
}
TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n",
root->LogicalAddress());
@@ -353,9 +357,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
TRACE("Volume::Mount(): Searching dev root\n");
search_key.SetOffset(0);
search_key.SetObjectID(BTRFS_OBJECT_ID_DEV_TREE);
- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
+ if (status != B_OK) {
ERROR("Volume::Mount(): Couldn't find dev root\n");
- return B_ERROR;
+ return status;
}
TRACE("Volume::Mount(): Found dev root: %" B_PRIu64 "\n",
root->LogicalAddress());
@@ -368,9 +373,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
TRACE("Volume::Mount(): Searching checksum root\n");
search_key.SetOffset(0);
search_key.SetObjectID(BTRFS_OBJECT_ID_CHECKSUM_TREE);
- if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
+ status = fRootTree->FindExact(&path, search_key, (void**)&root);
+ if (status != B_OK) {
ERROR("Volume::Mount(): Couldn't find checksum root\n");
- return B_ERROR;
+ return status;
}
TRACE("Volume::Mount(): Found checksum root: %" B_PRIu64 "\n",
root->LogicalAddress());
@@ -484,11 +490,11 @@ Volume::FindBlock(off_t logical, off_t& physical)
btrfs_key search_key;
search_key.SetOffset(logical);
search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
- search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
+ search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
btrfs_chunk* chunk;
- uint32 chunk_length;
- status_t status = fChunkTree->FindPrevious(search_key, (void**)&chunk,
- &chunk_length);
+ BTree::Path path(fChunkTree);
+ status_t status = fChunkTree->FindPrevious(&path, search_key,
+ (void**)&chunk);
if (status != B_OK)
return status;
diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
index 54e4634..d2f4518 100644
--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
@@ -427,6 +427,7 @@ struct btrfs_extent_data_ref {
#define BTRFS_OBJECT_ID_CHECKSUM_TREE 7
#define BTRFS_OBJECT_ID_FIRST_CHUNK_TREE 256
+#define BTRFS_KEY_TYPE_ANY 0
#define BTRFS_KEY_TYPE_INODE_ITEM 1
#define BTRFS_KEY_TYPE_INODE_REF 12
#define BTRFS_KEY_TYPE_XATTR_ITEM 24
############################################################################
Commit: bfd7a4fb427485418bc5f2edec48201fd94a1625
URL: http://cgit.haiku-os.org/haiku/commit/?id=bfd7a4fb4274
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 12 21:29:18 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:11 2017 UTC
BTRFS: Reimplement TreeIterator, add some error checks and remove redundancies.
Add BTree::Path as a attribute so enhance performance, so that everytime we
iterate through items it wont search all the root to leaf
again. The Iterator is initialized without rewinding to make more flexible.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
index f453a11..b9dfc91 100644
--- a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.cpp
@@ -22,9 +22,10 @@ AttributeIterator::AttributeIterator(Inode* inode)
fInode(inode),
fIterator(NULL)
{
- struct btrfs_key key;
+ btrfs_key key;
key.SetType(BTRFS_KEY_TYPE_XATTR_ITEM);
key.SetObjectID(inode->ID());
+ key.SetOffset(BTREE_BEGIN);
fIterator = new(std::nothrow) TreeIterator(inode->GetVolume()->FSTree(),
key);
}
@@ -33,6 +34,7 @@ AttributeIterator::AttributeIterator(Inode* inode)
AttributeIterator::~AttributeIterator()
{
delete fIterator;
+ fIterator = NULL;
}
@@ -46,10 +48,9 @@ AttributeIterator::InitCheck()
status_t
AttributeIterator::GetNext(char* name, size_t* _nameLength)
{
- btrfs_key key;
btrfs_dir_entry* entries;
uint32 entries_length;
- status_t status = fIterator->GetPreviousEntry(key, (void**)&entries,
+ status_t status = fIterator->GetPreviousEntry((void**)&entries,
&entries_length);
if (status != B_OK)
return status;
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
index ce87f5a..bf93bf3 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
@@ -519,13 +519,16 @@ BTree::_RemoveIterator(TreeIterator* iterator)
// #pragma mark -
-TreeIterator::TreeIterator(BTree* tree, btrfs_key& key)
+TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
:
fTree(tree),
- fCurrentKey(key)
+ fKey(key),
+ fIteratorStatus(B_NO_INIT)
{
- Rewind();
tree->_AddIterator(this);
+ fPath = new(std::nothrow) BTree::Path(tree);
+ if (fPath == NULL)
+ fIteratorStatus = B_NO_MEMORY;
}
@@ -533,26 +536,72 @@ TreeIterator::~TreeIterator()
{
if (fTree)
fTree->_RemoveIterator(this);
+
+ delete fPath;
+ fPath = NULL;
+}
+
+
+void
+TreeIterator::Rewind(bool inverse)
+{
+ if (inverse)
+ fKey.SetOffset(BTREE_END);
+ else
+ fKey.SetOffset(BTREE_BEGIN);
+ fIteratorStatus = B_NO_INIT;
}
/*! Iterates through the tree in the specified direction.
*/
status_t
-TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
- void** value, uint32* size)
+TreeIterator::_Traverse(btree_traversing direction)
{
- if (fTree == NULL)
- return B_INTERRUPTED;
+ status_t status = fTree->Traverse(direction, fPath, fKey);
+ if (status < B_OK) {
+ ERROR("TreeIterator::Traverse() Find failed\n");
+ return status;
+ }
- fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
- BTree::Path path(fTree);
- status_t status = fTree->_Find(&path, fCurrentKey, value, size,
direction);
- if (status != B_OK) {
- TRACE("TreeIterator::Traverse() Find failed\n");
- return B_ENTRY_NOT_FOUND;
+ return (fIteratorStatus = B_OK);
+}
+
+
+// Like GetEntry in BTree::Path but here we check the type and moving.
+status_t
+TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size,
+ uint32* _offset)
+{
+ status_t status;
+ if (fIteratorStatus == B_NO_INIT) {
+ status = _Traverse(type);
+ if (status != B_OK)
+ return status;
+ type = BTREE_EXACT;
}
+ if (fIteratorStatus != B_OK)
+ return fIteratorStatus;
+
+ int move = fPath->Move(0, type);
+ if (move > 0)
+ status = fTree->NextLeaf(fPath);
+ else if (move < 0)
+ status = fTree->PreviousLeaf(fPath);
+ if (status != B_OK)
+ return status;
+
+ btrfs_key found;
+ status = fPath->GetCurrentEntry(&found, _value, _size, _offset);
+ if (status != B_OK)
+ return status;
+
+ fKey.SetObjectID(found.ObjectID());
+ fKey.SetOffset(found.Offset());
+ if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY)
+ return B_ENTRY_NOT_FOUND;
+
return B_OK;
}
@@ -560,11 +609,13 @@ TreeIterator::Traverse(btree_traversing direction,
btrfs_key& key,
/*! just sets the current key in the iterator.
*/
status_t
-TreeIterator::Find(btrfs_key& key)
+TreeIterator::Find(const btrfs_key& key)
{
- if (fTree == NULL)
- return B_INTERRUPTED;
- fCurrentKey = key;
+ if (fIteratorStatus == B_INTERRUPTED)
+ return fIteratorStatus;
+
+ fKey = key;
+ fIteratorStatus = B_NO_INIT;
return B_OK;
}
@@ -573,4 +624,5 @@ void
TreeIterator::Stop()
{
fTree = NULL;
+ fIteratorStatus = B_INTERRUPTED;
}
diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h
b/src/add-ons/kernel/file_systems/btrfs/BTree.h
index 30afcaf..d44a401 100644
--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
@@ -176,31 +176,37 @@ public:
class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
public:
-
TreeIterator(BTree* tree, btrfs_key& key);
+
TreeIterator(BTree* tree, const btrfs_key& key);
~TreeIterator();
- status_t
Traverse(btree_traversing direction,
-
btrfs_key& key, void** value,
- uint32*
size = NULL);
- status_t Find(btrfs_key& key);
+ void Rewind(bool inverse =
false);
+ status_t Find(const btrfs_key&
key);
+ status_t GetNextEntry(void**
_value,
+ uint32*
_size = NULL,
+ uint32*
_offset = NULL);
+ status_t GetPreviousEntry(void**
_value,
+ uint32*
_size = NULL,
+ uint32*
_offset = NULL);
- status_t Rewind();
- status_t GetNextEntry(btrfs_key&
key, void** value,
- uint32*
size = NULL);
- status_t
GetPreviousEntry(btrfs_key& key, void** value,
- uint32*
size = NULL);
-
- BTree* Tree() const { return fTree; }
+ BTree* Tree() const { return
fTree; }
+ btrfs_key Key() const { return
fKey; }
private:
friend class BTree;
+ status_t
_Traverse(btree_traversing direction);
+ status_t _Find(btree_traversing
type, btrfs_key& key,
+ void**
_value);
+ status_t
_GetEntry(btree_traversing type, void** _value,
+ uint32*
_size, uint32* _offset);
// called by BTree
void Stop();
private:
BTree* fTree;
- btrfs_key fCurrentKey;
+ BTree::Path* fPath;
+ btrfs_key fKey;
+ status_t fIteratorStatus;
};
@@ -219,25 +225,16 @@ BTree::Path::GetCurrentEntry(btrfs_key* _key, void**
_value, uint32* _size,
inline status_t
-TreeIterator::Rewind()
-{
- fCurrentKey.SetOffset(BTREE_BEGIN);
- return B_OK;
-}
-
-
-inline status_t
-TreeIterator::GetNextEntry(btrfs_key& key, void** value, uint32* size)
+TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset)
{
- return Traverse(BTREE_FORWARD, key, value, size);
+ return _GetEntry(BTREE_FORWARD, _value, _size, _offset);
}
inline status_t
-TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
- uint32* size)
+TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset)
{
- return Traverse(BTREE_BACKWARD, key, value, size);
+ return _GetEntry(BTREE_BACKWARD, _value, _size, _offset);
}
diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
index ccfd1b2..0be81a4 100644
--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
@@ -26,6 +26,7 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
btrfs_key key;
key.SetType(BTRFS_KEY_TYPE_DIR_INDEX);
key.SetObjectID(inode->ID());
+ key.SetOffset(BTREE_BEGIN);
fIterator = new(std::nothrow) TreeIterator(inode->GetVolume()->FSTree(),
key);
}
@@ -33,8 +34,8 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
DirectoryIterator::~DirectoryIterator()
{
- if (fIterator != NULL)
- delete fIterator;
+ delete fIterator;
+ fIterator = NULL;
}
@@ -69,11 +70,9 @@ DirectoryIterator::GetNext(char* name, size_t* _nameLength,
ino_t* _id)
return fInode->FindParent(_id);
}
- btrfs_key key;
btrfs_dir_entry* entries;
uint32 entries_length;
- status_t status = fIterator->GetNextEntry(key, (void**)&entries,
- &entries_length);
+ status_t status = fIterator->GetNextEntry((void**)&entries,
&entries_length);
if (status != B_OK)
return status;
############################################################################
Commit: af419b0e9831ff414b8dc53eba9f7d00e7963711
URL: http://cgit.haiku-os.org/haiku/commit/?id=af419b0e9831
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sun Aug 13 09:42:23 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 15:56:12 2017 UTC
BTRFS: Implement ExtentAllocator
There are 4 new classes, structs:
* 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,
that is incremented each time a new extent refer to it (COW) and item data,
that is only for allocated extent (NULL for free).
* CachedTreeExtent, is a AVLTree, cache the whole extent tree and has
CachedExtent as its node.
* 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
responsible for inserting nodes in CachedTreeExtent.
* And the final, ExtentAllocator it knows how to allocate/deallocate extents,
but for now only the allocating is implemented, actually allocating and
deallocating works
are already implemented, they are in functions _AddFreeExtent,
_AddAllocatedExtent in CachedTreeExtent. However the deallocating is not needed
for now, so it will be
finished later then.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
new file mode 100644
index 0000000..bb57dc2
--- /dev/null
+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
@@ -0,0 +1,692 @@
+#include "ExtentAllocator.h"
+#include "Chunk.h"
+
+
+CachedExtent*
+CachedExtent::Create(uint64 offset, uint64 length, uint64 flags)
+{
+ CachedExtent* self = new(std::nothrow) CachedExtent();
+ if (self == NULL)
+ return NULL;
+
+ self->offset = offset;
+ self->length = length;
+ self->refCount = 0;
+ if ((flags & BTRFS_EXTENT_FLAG_ALLOCATED) != 0)
+ self->refCount = 1;
+ self->flags = flags;
+ self->item = NULL;
+ return self;
+}
+
+
+void
+CachedExtent::Delete()
+{
+ if (item != NULL)
+ free(item);
+ item = NULL;
+ delete this;
+}
+
+
+bool
+CachedExtent::IsAllocated() const
+{
+ return (flags & BTRFS_EXTENT_FLAG_ALLOCATED) != 0;
+}
+
+
+bool
+CachedExtent::IsData() const
+{
+ return (flags & BTRFS_EXTENT_FLAG_DATA) != 0;
+}
+
+
+void
+CachedExtent::Info() const
+{
+ const char* extentType = "allocated tree block";
+ if (IsAllocated() == false && IsData() == false)
+ extentType = "free tree block";
+ else if (IsAllocated() == false && IsData() == true)
+ extentType = "free data extent";
+ else if (IsAllocated() == true && IsData() == true)
+ extentType = "allocated data extent";
+
+ TRACE("%s at %" B_PRIu64 " length %" B_PRIu64 " refCount %i\n",
+ extentType, offset, length, refCount);
+}
+
+
+// ExtentTree Implementation
+
+
+CachedExtentTree::CachedExtentTree(const TreeDefinition& definition)
+ :
+ AVLTree<TreeDefinition>(definition)
+{
+}
+
+
+CachedExtentTree::~CachedExtentTree()
+{
+ Delete();
+}
+
+
+/* Find extent that cover or after "offset" and has length >= "size"
+ * it must also satisfy the condition "type".
+ */
+status_t
+CachedExtentTree::FindNext(CachedExtent** chosen, uint64 offset, uint64 size,
+ uint64 type)
+{
+ CachedExtent* found = Find(offset);
+ while (found != NULL && (found->flags != type || found->length < size))
+ found = Next(found);
+
+ if (found == NULL)
+ return B_ENTRY_NOT_FOUND;
+ *chosen = found;
+ return B_OK;
+}
+
+
+/* this will insert all free extents that are holes,
+ * created by existed allocated extents in the tree
+ * from lowerBound to upperBound
+ */
+status_t
+CachedExtentTree::FillFreeExtents(uint64 lowerBound, uint64 upperBound)
+{
+ CachedExtent* node = FindClosest(lowerBound, false);
+ CachedExtent* hole = NULL;
+ status_t status = B_OK;
+ uint64 flags = node->flags & (~BTRFS_EXTENT_FLAG_ALLOCATED);
+ if (lowerBound < node->offset) {
+ hole = CachedExtent::Create(lowerBound, node->offset -
lowerBound,
+ flags);
+ status = _AddFreeExtent(hole);
+ if (status != B_OK)
+ return status;
+ }
+
+ CachedExtent* next = NULL;
+ while ((next = Next(node)) != NULL && next->End() < upperBound) {
+ if (node->End() == next->offset) {
+ node = next;
+ continue;
+ }
+
+ hole = CachedExtent::Create(node->End(), next->offset -
node->End(),
+ flags);
+ status = _AddFreeExtent(hole);
+ if (status != B_OK)
+ return status;
+ node = next;
+ }
+
+ // final node should be a right most node
+ if (upperBound > node->End()) {
+ hole = CachedExtent::Create(node->End(), upperBound -
node->End(),
+ flags);
+ status = _AddFreeExtent(hole);
+ }
+
+ return status;
+}
+
+
+void
+CachedExtentTree::_RemoveExtent(CachedExtent* node)
+{
+ node->refCount--;
+ if (node->refCount <= 0) {
+ Remove(node);
+ node->Delete();
+ }
+}
+
+
+status_t
+CachedExtentTree::_AddAllocatedExtent(CachedExtent* node)
+{
+ if (node == NULL || node->IsAllocated() == false)
+ return B_BAD_VALUE;
+
+ CachedExtent* found = Find(node->offset);
+ if (found == NULL) {
+ Insert(node);
+ return B_OK;
+ }
+
+ if ((found->IsData() && !node->IsData())
+ || (!found->IsData() && node->IsData())) {
+ // this shouldn't happen as because different type has
+ // its different region for locating.
+ node->Delete();
+ return B_BAD_VALUE;
+ }
+
+ if (found->IsAllocated() == false) {
+ // split free extents (found)
+ if (node->End() > found->End()) {
+ // TODO: when to handle this ?
+ node->Delete();
+ return B_BAD_VALUE;
+ }
+
+ // |----- found ------|
+ // |-- node ---|
+ uint64 diff = node->offset - found->offset;
+ found->offset += diff + node->length;
+ found->length -= diff + node->length;
+ // diff < 0 couldn't happen because of the Compare function
+ if (diff > 0) {
+ CachedExtent* leftEmpty = CachedExtent::Create(
+ node->offset - diff, diff, found->flags);
+ _AddFreeExtent(leftEmpty);
+ }
+
+ if (found->length == 0) {
+ // free-extent that has no space
+ _RemoveExtent(found);
+ }
+
+ Insert(node);
+ return B_OK;
+ }
+
+ if (found->length == node->length) {
+ found->refCount++;
+ } else {
+ // TODO: What should we do in this case ?
+ return B_BAD_VALUE;
+ }
+ node->Delete();
+
+ return B_OK;
+}
+
+
+status_t
+CachedExtentTree::_AddFreeExtent(CachedExtent* node)
+{
+ if (node == NULL || node->IsAllocated() == true)
+ return B_BAD_VALUE;
+
+ CachedExtent* found = Find(node->offset);
+ if (found == NULL) {
+ Insert(node);
+ _CombineFreeExtent(node);
+ return B_OK;
+ }
+
+ if ((found->IsData() && !node->IsData())
+ || (!found->IsData() && node->IsData())) {
+ // this shouldn't happen as because different type has
+ // its different region for locating.
+ node->Delete();
+ return B_BAD_VALUE;
+ }
+
+ if (found->End() < node->End()) {
+ // |---- found-----|
+ // |--- node ------|
+ CachedExtent* rightEmpty = CachedExtent::Create(found->End(),
+ node->End() - found->End(), node->flags);
+ _AddFreeExtent(rightEmpty);
+ node->length -= node->End() - found->End();
+ }
+
+ if (found->IsAllocated() == true) {
+ // free part of the allocated extents(found)
+ // |----- found ------|
+ // |-- node ---|
+ uint64 diff = node->offset - found->offset;
+ found->offset += diff + node->length;
+ found->length -= diff + node->length;
+ // diff < 0 couldn't happen because of the Compare function
+ if (diff > 0){
+ CachedExtent* left = CachedExtent::Create(node->offset
- diff,
+ diff, found->flags);
+ _AddAllocatedExtent(left);
+ }
+
+ if (found->length == 0)
+ _RemoveExtent(found);
+
+ Insert(node);
+ _CombineFreeExtent(node);
+ }
+
+ return B_OK;
+}
+
+
+status_t
+CachedExtentTree::AddExtent(CachedExtent* extent)
+{
+ if (extent->IsAllocated() == true)
+ return _AddAllocatedExtent(extent);
+ return _AddFreeExtent(extent);
+}
+
+
+void
+CachedExtentTree::_CombineFreeExtent(CachedExtent* node)
+{
+ // node should be inserted first to call this function,
+ // otherwise it will overdelete.
+ if (node->IsAllocated() == true)
+ return;
+
+ CachedExtent* other = Next(node);
+ if (other != NULL) {
+ if (node->End() == other->offset && node->flags ==
other->flags) {
+ node->length += other->length;
+ _RemoveExtent(other);
+ }
+ }
+
+ other = Previous(node);
+ if (other != NULL) {
+ if (other->End() == node->offset && node->flags ==
other->flags) {
+ other->length += node->length;
+ _RemoveExtent(node);
+ }
+ }
+}
+
+
+void
+CachedExtentTree::_DumpInOrder(CachedExtent* node) const
+{
+ if (node == NULL)
+ return;
+ _DumpInOrder(_GetValue(node->left));
+ node->Info();
+ _DumpInOrder(_GetValue(node->right));
+}
+
+
+void
+CachedExtentTree::DumpInOrder() const
+{
+ TRACE("\n");
+ _DumpInOrder(RootNode());
+ TRACE("\n");
+}
+
+
+void
+CachedExtentTree::Delete()
+{
+ _Delete(RootNode());
+ Clear();
+}
+
+
+void
+CachedExtentTree::_Delete(CachedExtent* node)
+{
+ if (node == NULL)
+ return;
+ _Delete(_GetValue(node->left));
+ _Delete(_GetValue(node->right));
+ node->Delete();
+}
+
+
+// BlockGroup
+
+
+BlockGroup::BlockGroup(BTree* extentTree)
+ :
+ fItem(NULL)
+{
+ fCurrentExtentTree = new(std::nothrow) BTree(extentTree->SystemVolume(),
+ extentTree->RootBlock());
+}
+
+
+BlockGroup::~BlockGroup()
+{
+ if (fItem != NULL) {
+ free(fItem);
+ fItem = NULL;
+ }
+
+ delete fCurrentExtentTree;
+ fCurrentExtentTree = NULL;
+}
+
+
+status_t
+BlockGroup::SetExtentTree(off_t rootAddress)
+{
+ status_t status = fCurrentExtentTree->SetRoot(rootAddress, NULL);
+ if (status != B_OK)
+ return status;
+
+ if (fItem != NULL) {
+ // re-allocate BlockGroup;
+ uint64 flags = Flags();
+ return Initialize(flags);
+ }
+
+ return B_OK;
+}
+
+
+/* Initialize BlockGroup that has flag
+ */
+status_t
+BlockGroup::Initialize(uint64 flag)
+{
+ if (fCurrentExtentTree == NULL)
+ return B_NO_MEMORY;
+
+ if (fItem != NULL)
+ free(fItem);
+
+ TRACE("BlockGroup::Initialize() find block group has flag: %"
+ B_PRIu64 "\n", flag);
+ BTree::Path path(fCurrentExtentTree);
+ fKey.SetObjectID(0);
+ // find first item in extent to get the ObjectID
+ // ignore type because block_group is not always the first item
+ fKey.SetType(BTRFS_KEY_TYPE_ANY);
+ fCurrentExtentTree->FindNext(&path, fKey, NULL);
+
+ fKey.SetType(BTRFS_KEY_TYPE_BLOCKGROUP_ITEM);
+ fKey.SetOffset(0);
+ status_t status;
+
+ while(true) {
+ status = fCurrentExtentTree->FindNext(&path, fKey,
(void**)&fItem);
+ if ((Flags() & flag) == flag || status != B_OK)
+ break;
+ fKey.SetObjectID(End());
+ fKey.SetOffset(0);
+ }
+
+ if (status != B_OK)
+ ERROR("BlockGroup::Initialize() cannot find block group\n");
+
+ return status;
+}
+
+
+status_t
+BlockGroup::LoadExtent(CachedExtentTree* tree, bool inverse)
+{
+ if (fItem == NULL)
+ return B_NO_INIT;
+
+ uint64 flags = (Flags() & BTRFS_BLOCKGROUP_FLAG_DATA) != 0 ?
+ BTRFS_EXTENT_FLAG_DATA : BTRFS_EXTENT_FLAG_TREE_BLOCK;
+ if (inverse == false)
+ flags |= BTRFS_EXTENT_FLAG_ALLOCATED;
+
+ uint64 start = Start();
+ CachedExtent* insert;
+ void* data;
+ uint64 extentSize = fCurrentExtentTree->SystemVolume()->BlockSize();
+
+ btrfs_key key;
+ key.SetType(BTRFS_KEY_TYPE_METADATA_ITEM);
+ if ((flags & BTRFS_EXTENT_FLAG_DATA) != 0)
+ key.SetType(BTRFS_KEY_TYPE_EXTENT_ITEM);
+ key.SetObjectID(start);
+ key.SetOffset(0);
+
+ TreeIterator iterator(fCurrentExtentTree, key);
+ status_t status;
+ while(true) {
+ status = iterator.GetNextEntry(&data);
+ key = iterator.Key();
+ if (status != B_OK) {
+ if (key.ObjectID() != Start())
+ break;
+ // When we couldn't find the item and key has
+ // objectid == BlockGroup's objectID, because
+ // key's type < BLOCKGROUP_ITEM
+ continue;
+ }
+
+ if (inverse == false) {
+ if ((flags & BTRFS_EXTENT_FLAG_DATA) != 0)
+ extentSize = key.Offset();
+ insert = CachedExtent::Create(key.ObjectID(),
extentSize, flags);
+ insert->item = (btrfs_extent*)data;
+ } else {
+ extentSize = key.ObjectID() - start;
+ insert = CachedExtent::Create(start, extentSize, flags);
+ free(data); // free extent doesn't have
data;
+ }
+ _InsertExtent(tree, insert);
+ start = key.ObjectID() + extentSize;
+ }
+
+ if (inverse == true)
+ _InsertExtent(tree, start, End() - start, flags);
+
+ return B_OK;
+}
+
+
+status_t
+BlockGroup::_InsertExtent(CachedExtentTree* tree, uint64 start, uint64 length,
+ uint64 flags)
+{
+ CachedExtent* extent = CachedExtent::Create(start, length, flags);
+ return _InsertExtent(tree, extent);
+}
+
+
+status_t
+BlockGroup::_InsertExtent(CachedExtentTree* tree, CachedExtent* extent)
+{
+ if (extent->length == 0)
+ return B_BAD_VALUE;
+
+ status_t status = tree->AddExtent(extent);
+ if (status != B_OK) {
+ return status;
+ }
+ return B_OK;
+}
+
+
+// ExtentAllocator
+
+
+ExtentAllocator::ExtentAllocator(Volume* volume)
+ :
+ fVolume(volume),
+ fTree(NULL),
+ fStart((uint64)-1),
+ fEnd(0)
+{
+ fTree = new(std::nothrow) CachedExtentTree(TreeDefinition());
+}
+
+
+ExtentAllocator::~ExtentAllocator()
+{
+ delete fTree;
+ fTree = NULL;
+}
+
+
+status_t
+ExtentAllocator::_LoadExtentTree(uint64 flags)
+{
+ TRACE("ExtentAllocator::_LoadExtentTree() flags: %" B_PRIu64 "\n",
flags);
+ BlockGroup blockGroup(fVolume->ExtentTree());
+ status_t status = blockGroup.Initialize(flags);
+ if (status != B_OK)
+ return status;
+
+ for (int i = 0; i < BTRFS_NUM_ROOT_BACKUPS; i++) {
+ uint64 extentRootAddr =
+ fVolume->SuperBlock().backup_roots[i].ExtentRoot();
+ if (extentRootAddr == 0)
+ continue; // new device has 0 root address
+
+ status = blockGroup.SetExtentTree(extentRootAddr);
+ if (status != B_OK)
+ return status;
+ status = blockGroup.LoadExtent(fTree, false);
+ if (status != B_OK)
+ return status;
+ }
+
+ if (fTree->IsEmpty()) // 4 backup roots is 0
+ return B_OK;
+
+ uint64 lowerBound = blockGroup.Start();
+ uint64 upperBound = blockGroup.End();
+ status = fTree->FillFreeExtents(lowerBound, upperBound);
+ if (status != B_OK) {
+ ERROR("ExtentAllocator::_LoadExtentTree() could not fill free
extents"
+ "start %" B_PRIu64 " end %" B_PRIu64 "\n", lowerBound,
+ upperBound);
+ return status;
+ }
+
+ if (fStart > lowerBound)
+ fStart = lowerBound;
+ if (fEnd < upperBound)
+ fEnd = upperBound;
+ return B_OK;
+}
+
+
+status_t
+ExtentAllocator::Initialize()
+{
+ TRACE("ExtentAllocator::Initialize()\n");
+ if (fTree == NULL)
+ return B_NO_MEMORY;
+
+ status_t status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_DATA);
+ if (status != B_OK) {
+ ERROR("ExtentAllocator:: could not load exent tree (data)\n");
+ return status;
+ }
+
+ status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_SYSTEM);
+ if (status != B_OK) {
+ ERROR("ExtentAllocator:: could not load exent tree (system)\n");
+ return status;
+ }
+
+ status = _LoadExtentTree(BTRFS_BLOCKGROUP_FLAG_METADATA);
+ if (status != B_OK) {
+ ERROR("ExtentAllocator:: could not load exent tree
(metadata)\n");
+ return status;
+ }
+
+ fTree->DumpInOrder();
+ return B_OK;
+}
+
+
+/* Allocate extent that
+ * startwith or after "start" and has size >= "size"
+ * For now the allocating strategy is "first fit"
+ */
+status_t
+ExtentAllocator::_Allocate(uint64& found, uint64 start, uint64 size,
+ uint64 type)
+{
+ TRACE("ExtentAllocator::_Allocate() start %" B_PRIu64 " size %"
B_PRIu64 " type %"
+ B_PRIu64 "\n", start, size, type);
+ CachedExtent* chosen;
+ status_t status;
+ while(true) {
+ status = fTree->FindNext(&chosen, start, size, type);
+ if (status != B_OK)
+ return status;
+
+ if (TreeDefinition().Compare(start, chosen) == 0) {
+ if (chosen->End() - start >= size) {
+ // if covered and have enough space for
allocating
+ break;
+ }
+ start = chosen->End(); // set new start and retry
+ } else
+ start = chosen->offset;
+ }
+
+ TRACE("ExtentAllocator::_Allocate() found %" B_PRIu64 "\n", start);
+ chosen = CachedExtent::Create(start, size,
+ type | BTRFS_EXTENT_FLAG_ALLOCATED);
+ status = fTree->AddExtent(chosen);
+ if (status != B_OK)
+ return status;
+
+ found = start;
+ return B_OK;
+}
+
+
+// Allocate block for metadata
+// flags is BLOCKGROUP's flags
+status_t
+ExtentAllocator::AllocateTreeBlock(uint64& found, uint64 start, uint64 flags)
+{
+ // TODO: implement more features here with flags, e.g DUP, RAID, etc
+
+ BlockGroup blockGroup(fVolume->ExtentTree());
+ status_t status = blockGroup.Initialize(flags);
+ if (status != B_OK)
+ return status;
+ if (start == (uint64)-1)
+ start = blockGroup.Start();
+
+ // normalize inputs
+ uint64 remainder = start % fVolume->BlockSize();
+ if (remainder != 0)
+ start += fVolume->BlockSize() - remainder;
+
+ status = _Allocate(found, start, fVolume->BlockSize(),
+ BTRFS_EXTENT_FLAG_TREE_BLOCK);
+ if (status != B_OK)
+ return status;
+
+ // check here because tree block locate in 2 blockgroups (system and
+ // metadata), and there might be a case one can get over the limit.
+ if (found >= blockGroup.End())
+ return B_BAD_DATA;
+ return B_OK;
+}
+
+
+// Allocate block for file data
+status_t
+ExtentAllocator::AllocateDataBlock(uint64& found, uint64 size, uint64 start,
+ uint64 flags)
+{
+ // TODO: implement more features here with flags, e.g DUP, RAID, etc
+
+ if (start == (uint64)-1) {
+ BlockGroup blockGroup(fVolume->ExtentTree());
+ status_t status = blockGroup.Initialize(flags);
+ if (status != B_OK)
+ return status;
+ start = blockGroup.Start();
+ }
+
+ // normalize inputs
+ uint64 remainder = start % fVolume->SectorSize();
+ if (remainder != 0)
+ start += fVolume->SectorSize() - remainder;
+ size = size / fVolume->SectorSize() * fVolume->SectorSize();
+
+ return _Allocate(found, start, size, BTRFS_EXTENT_FLAG_DATA);
+}
diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
new file mode 100644
index 0000000..310f8ac
--- /dev/null
+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
@@ -0,0 +1,153 @@
+#ifndef EXTENT_ALLOCATOR_H
+#define EXTENT_ALLOCATOR_H
+
+
+#include "Volume.h"
+#include "BTree.h"
+
+
+//#define TRACE_BTRFS
+#ifdef TRACE_BTRFS
+# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
+#else
+# define TRACE(x...) ;
+#endif
+
+#define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
+
+
+struct CachedExtent : AVLTreeNode {
+ uint64 offset;
+ uint64 length;
+ int refCount;
+ uint64 flags;
+ btrfs_extent* item;
+
+ static CachedExtent* Create(uint64 offset, uint64 length,
+ uint64
flags);
+ void Delete();
+
+ uint64 End() const { return
offset + length; }
+ bool IsAllocated() const;
+ bool IsData() const;
+
+ void Info() const;
+
+private:
+ CachedExtent()
{}
+
CachedExtent(const CachedExtent& other);
+};
+
+
+struct TreeDefinition {
+ typedef uint64 Key;
+ typedef CachedExtent Value;
+
+ AVLTreeNode* GetAVLTreeNode(Value* value) const
+ {
+ return value;
+ }
+
+ Value* GetValue(AVLTreeNode* node) const
+ {
+ return static_cast<Value*>(node);
+ }
+
+ int Compare(const Key& a, const Value* b) const
+ {
+ if (a < b->offset)
+ return -1;
+ if (a >= b->End())
+ return 1;
+ return 0;
+ }
+
+ int Compare(const Value* a, const Value* b) const
+ {
+ int comp = Compare(a->offset, b);
+ //TODO: check more conditions here if necessary
+ return comp;
+ }
+};
+
+
+struct CachedExtentTree : AVLTree<TreeDefinition> {
+public:
+
CachedExtentTree(
+ const
TreeDefinition& definition);
+
~CachedExtentTree();
+
+ status_t FindNext(CachedExtent**
chosen, uint64 offset,
+ uint64
size, uint64 type);
+ status_t AddExtent(CachedExtent*
extent);
+ status_t FillFreeExtents(uint64
lowerBound,
+ uint64
upperBound);
+ void DumpInOrder() const;
+ void Delete();
+private:
+ status_t
_AddAllocatedExtent(CachedExtent* node);
+ status_t
_AddFreeExtent(CachedExtent* node);
+ void
_CombineFreeExtent(CachedExtent* node);
+ void
_RemoveExtent(CachedExtent* node);
+ void
_DumpInOrder(CachedExtent* node) const;
+ void _Delete(CachedExtent*
node);
+};
+
+
+class BlockGroup {
+public:
+
BlockGroup(BTree* extentTree);
+ ~BlockGroup();
+
+ status_t SetExtentTree(off_t
rootAddress);
+ status_t Initialize(uint64 flag);
+ status_t
LoadExtent(CachedExtentTree* tree,
+ bool
inverse = false);
+
+ uint64 Flags() const { return
fItem->Flags(); }
+ uint64 Start() const { return
fKey.ObjectID(); }
+ uint64 End() const
+ {
return fKey.ObjectID() + fKey.Offset(); }
+
+private:
+
BlockGroup(const BlockGroup&);
+ BlockGroup&
operator=(const BlockGroup&);
+ status_t
_InsertExtent(CachedExtentTree* tree,
+ uint64
size, uint64 length, uint64 flags);
+ status_t
_InsertExtent(CachedExtentTree* tree,
+
CachedExtent* extent);
+
+private:
+ btrfs_key fKey;
+ btrfs_block_group* fItem;
+ BTree* fCurrentExtentTree;
+};
+
+
+class ExtentAllocator {
+public:
+
ExtentAllocator(Volume* volume);
+
~ExtentAllocator();
+
+ status_t Initialize();
+ status_t
AllocateTreeBlock(uint64& found,
+ uint64
start = (uint64)-1,
+ uint64
flags = BTRFS_BLOCKGROUP_FLAG_METADATA);
+ status_t
AllocateDataBlock(uint64& found, uint64 size,
+ uint64
start = (uint64)-1,
+ uint64
flags = BTRFS_BLOCKGROUP_FLAG_DATA);
+private:
+
ExtentAllocator(const ExtentAllocator&);
+
ExtentAllocator& operator=(const ExtentAllocator&);
+ status_t _LoadExtentTree(uint64
flags);
+ status_t _Allocate(uint64&
found, uint64 start,
+ uint64
size, uint64 type);
+private:
+ Volume* fVolume;
+ CachedExtentTree* fTree;
+ uint64 fStart;
+ uint64 fEnd;
+};
+
+
+#endif // EXTENT_ALLOCATOR_H
diff --git a/src/add-ons/kernel/file_systems/btrfs/Jamfile
b/src/add-ons/kernel/file_systems/btrfs/Jamfile
index d408e55..78ba20c 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Jamfile
+++ b/src/add-ons/kernel/file_systems/btrfs/Jamfile
@@ -16,6 +16,7 @@ KernelAddon btrfs :
Chunk.cpp
CRCTable.cpp
DirectoryIterator.cpp
+ ExtentAllocator.cpp
Inode.cpp
Volume.cpp
: kernel_libz.a
diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
index dc2fffe..c219d40 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
@@ -13,6 +13,7 @@
#include "CachedBlock.h"
#include "Chunk.h"
#include "Inode.h"
+#include "ExtentAllocator.h"
//#define TRACE_BTRFS
@@ -386,6 +387,16 @@ Volume::Mount(const char* deviceName, uint32 flags)
fChecksumTree->SetRoot(root->LogicalAddress(), NULL);
free(root);
+ // Initialize ExtentAllocator;
+ fExtentAllocator = new(std::nothrow) ExtentAllocator(this);
+ if (fExtentAllocator == NULL)
+ return B_NO_MEMORY;
+ status = fExtentAllocator->Initialize();
+ if (status != B_OK) {
+ ERROR("could not initalize extent allocator!\n");
+ return status;
+ }
+
// ready
status = get_vnode(fFSVolume, BTRFS_FIRST_SUBVOLUME,
(void**)&fRootNode);
@@ -432,10 +443,12 @@ Volume::Unmount()
delete fChecksumTree;
delete fFSTree;
delete fDevTree;
+ delete fExtentAllocator;
fExtentTree = NULL;
fChecksumTree = NULL;
fFSTree = NULL;
fDevTree = NULL;
+ fExtentAllocator = NULL;
TRACE("Volume::Unmount(): Putting root node\n");
put_vnode(fFSVolume, RootNode()->ID());
diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.h
b/src/add-ons/kernel/file_systems/btrfs/Volume.h
index d839dc0..a4b292c 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Volume.h
+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.h
@@ -17,6 +17,7 @@ enum volume_flags {
class BTree;
class Chunk;
class Inode;
+class ExtentAllocator;
class Volume {
@@ -45,6 +46,7 @@ public:
uint32 SectorSize() const {
return fSectorSize; }
uint32 BlockSize() const {
return fBlockSize; }
Chunk* SystemChunk() const {
return fChunk; }
+ ExtentAllocator* GetAllocator() const { return
fExtentAllocator; }
btrfs_super_block& SuperBlock() { return
fSuperBlock; }
@@ -72,6 +74,7 @@ private:
void* fBlockCache;
Inode* fRootNode;
+ ExtentAllocator* fExtentAllocator;
Chunk* fChunk;
BTree* fChunkTree;
BTree* fRootTree;
diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
index d2f4518..a6b4963 100644
--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
@@ -449,10 +449,11 @@ struct btrfs_extent_data_ref {
#define BTRFS_EXTENT_DATA_PRE 2
#define BTRFS_EXTENT_FLAG_DATA 1
#define BTRFS_EXTENT_FLAG_TREE_BLOCK 2
+#define BTRFS_EXTENT_FLAG_ALLOCATED 4
#define BTRFS_BLOCKGROUP_FLAG_DATA 1
#define BTRFS_BLOCKGROUP_FLAG_SYSTEM 2
-#define BTRFS_BLOCKGROUP_FLAG_METADA 4
+#define BTRFS_BLOCKGROUP_FLAG_METADATA 4
#define BTRFS_BLOCKGROUP_FLAG_RAID0 8
#define BTRFS_BLOCKGROUP_FLAG_RAID1 16
#define BTRFS_BLOCKGROUP_FLAG_DUP 32
diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
index 5029613..99231c8 100644
--- a/src/tools/btrfs_shell/Jamfile
+++ b/src/tools/btrfs_shell/Jamfile
@@ -42,6 +42,7 @@ local btrfsSources =
Chunk.cpp
CRCTable.cpp
DirectoryIterator.cpp
+ ExtentAllocator.cpp
Inode.cpp
Volume.cpp
kernel_interface.cpp
############################################################################
Commit: 0deb03560f570db9fff0159f2b46731281c20dae
URL: http://cgit.haiku-os.org/haiku/commit/?id=0deb03560f57
Author: hyche <cvghy116@xxxxxxxxx>
Date: Thu Aug 17 16:58:52 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:54 2017 UTC
BTRFS: Fix mismatched type of index in inode_ref item.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
index a6b4963..59f58e2 100644
--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
@@ -294,11 +294,11 @@ struct btrfs_inode {
struct btrfs_inode_ref {
- uint8 index;
+ uint64 index;
uint16 name_length;
uint8 name[];
- uint8 Index() const { return index; }
+ uint64 Index() const { return index; }
uint16 NameLength() const { return
B_LENDIAN_TO_HOST_INT16(name_length); }
} _PACKED;
############################################################################
Commit: 8137f447cb159923ca8238e136a40df5166743d8
URL: http://cgit.haiku-os.org/haiku/commit/?id=8137f447cb15
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sun Aug 20 17:36:07 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:55 2017 UTC
BTRFS: Fix memory leak
Missing delete for some tree roots.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
index c219d40..3ed2f2d 100644
--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
@@ -439,12 +439,16 @@ status_t
Volume::Unmount()
{
TRACE("Volume::Unmount()\n");
+ delete fRootTree;
delete fExtentTree;
+ delete fChunkTree;
delete fChecksumTree;
delete fFSTree;
delete fDevTree;
delete fExtentAllocator;
+ fRootTree = NULL;
fExtentTree = NULL;
+ fChunkTree = NULL;
fChecksumTree = NULL;
fFSTree = NULL;
fDevTree = NULL;
############################################################################
Commit: 1750cd1e92275f586b129483441ad3c8fd021369
URL: http://cgit.haiku-os.org/haiku/commit/?id=1750cd1e9227
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 23 18:25:09 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:56 2017 UTC
block_cache: Implement cache_has_block_in_transaction function that will check
the existence of block in one specific transaction.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/headers/os/drivers/fs_cache.h b/headers/os/drivers/fs_cache.h
index 9a71a5b..8c8193c 100644
--- a/headers/os/drivers/fs_cache.h
+++ b/headers/os/drivers/fs_cache.h
@@ -53,6 +53,7 @@ extern status_t cache_next_block_in_transaction(void *cache,
int32 id,
extern int32 cache_blocks_in_transaction(void *cache, int32 id);
extern int32 cache_blocks_in_main_transaction(void *cache, int32 id);
extern int32 cache_blocks_in_sub_transaction(void *cache, int32 id);
+extern bool cache_has_block_in_transaction(void* cache, int32 id, off_t
blockNumber);
/* block cache */
extern void block_cache_delete(void *cache, bool allowWrites);
diff --git a/headers/private/fs_shell/fssh_api_wrapper.h
b/headers/private/fs_shell/fssh_api_wrapper.h
index 233f8b4..7c1e0b3 100644
--- a/headers/private/fs_shell/fssh_api_wrapper.h
+++ b/headers/private/fs_shell/fssh_api_wrapper.h
@@ -835,6 +835,7 @@
#define cache_blocks_in_transaction fssh_cache_blocks_in_transaction
#define cache_blocks_in_main_transaction fssh_cache_blocks_in_main_transaction
#define cache_blocks_in_sub_transaction
fssh_cache_blocks_in_sub_transaction
+#define cache_has_block_in_transaction fssh_cache_has_block_in_transaction
/* block cache */
#define block_cache_delete fssh_block_cache_delete
diff --git a/headers/private/fs_shell/fssh_fs_cache.h
b/headers/private/fs_shell/fssh_fs_cache.h
index 88cc9a3..c27052c 100644
[ *** diff truncated: 62 lines dropped *** ]
############################################################################
Commit: c1320b3a33417a6702471014dac9d089c7036bc3
URL: http://cgit.haiku-os.org/haiku/commit/?id=c1320b3a3341
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 23 18:38:54 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:57 2017 UTC
BTRFS: Implement a simple journaling approach, this is not finished and mostly
satisfy the need for passing Transaction object for many functions.
Some details about the current Journal:
* Journal can only end transaction.
* It holds a transaction id of fs (fCurrentGeneration) that increments each
time a transaction starts.
* _TransactionWritten now just printing message.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 4368661f03c331391322659823f38d92ece893e7
URL: http://cgit.haiku-os.org/haiku/commit/?id=4368661f03c3
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 23 19:02:17 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:57 2017 UTC
BTRFS: Implement GetNewBlock() function that will find the logical address for
allocating and convert it to physical block.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 27ffe0583b71adcfb7814a3af1358271c1800877
URL: http://cgit.haiku-os.org/haiku/commit/?id=27ffe0583b71
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 23 19:22:02 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:58 2017 UTC
BTRFS: Implement some space relevant helpers.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 89484dc08d8e03fb458893ec0749f859b6bfd5f6
URL: http://cgit.haiku-os.org/haiku/commit/?id=89484dc08d8e
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 23 19:26:49 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:58 2017 UTC
BTRFS: Implement some copy relevant helpers.
Copy() copys data from other node, MoveEntries() changes data on the current
node.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 883b9bf29faede9fb578879f04e26cfca667e3df
URL: http://cgit.haiku-os.org/haiku/commit/?id=883b9bf29fae
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 23 20:09:00 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:59 2017 UTC
BTRFS: Implement CopyOnWrite relevant functions, and BTree holds new attribute
that record its root level.
CopyOnWrite works like this:
* Cache original node
* Allocating new block
* Cache new block to be writable
* Copy original node to new node, and changing.
Also if a node is already be COW-ed it cannot be COW-ed again, it will be
changed in-place instead.
InternalCopy does CopyOnWrite all the nodes that we don't need to change
anything on them.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 2b6c2ec3905e7cbf4385b93356a51737554e4092
URL: http://cgit.haiku-os.org/haiku/commit/?id=2b6c2ec3905e
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 26 22:13:22 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:02:59 2017 UTC
fs_shell: Added socket filetype.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 02bce792d84640327692fc044c24cf01162a04d9
URL: http://cgit.haiku-os.org/haiku/commit/?id=02bce792d846
Author: hyche <cvghy116@xxxxxxxxx>
Date: Sat Aug 26 22:18:04 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:00 2017 UTC
BTRFS: Added function to convert standard filetypes to btrfs filetypes.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 84bc447cae639842c6c3b7fe2d28bd52e2384eab
URL: http://cgit.haiku-os.org/haiku/commit/?id=84bc447cae63
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 19:07:52 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:00 2017 UTC
BTRFS: Implement InsertEntries() that will insert consecutive items and its
data.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 20185bb9c399a31ba2b509807c41d77ff62a52aa
URL: http://cgit.haiku-os.org/haiku/commit/?id=20185bb9c399
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 19:10:11 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:00 2017 UTC
BTRFS: Implement RemoveEntries() for BTree that will remove consecutive items
and its data.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 36a24fb34ef0f8cdfae1f25203ee3004390582d1
URL: http://cgit.haiku-os.org/haiku/commit/?id=36a24fb34ef0
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:08:43 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:01 2017 UTC
BTRFS: Implement Create() that allocate new Inode object.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 371935de1870f14564a49effc98d0a10a145ecae
URL: http://cgit.haiku-os.org/haiku/commit/?id=371935de1870
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:21:42 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:01 2017 UTC
BTRFS: Implement Insert() in Inode that inserts inode_item.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: b44d924df453be386d656805c53efe0f0dd0fe2f
URL: http://cgit.haiku-os.org/haiku/commit/?id=b44d924df453
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:38:42 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:02 2017 UTC
BTRFS: Implement MakeReference() in Inode that will link file name to inode.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 8042a045b0af37802c48e49a134af3583021650d
URL: http://cgit.haiku-os.org/haiku/commit/?id=8042a045b0af
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:41:56 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:02 2017 UTC
BTRFS: Implement Remove() in Inode that removes inode_item.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: a9e85cb62f27986fc58b31877713e1a64a38db8d
URL: http://cgit.haiku-os.org/haiku/commit/?id=a9e85cb62f27
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:43:21 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:03 2017 UTC
BTRFS: Implement Dereference() in Inode that remove the "name" and unlink it
with inode.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 166917c9cdf715d911f8de9415903718b075ee2c
URL: http://cgit.haiku-os.org/haiku/commit/?id=166917c9cdf7
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:47:02 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:03 2017 UTC
BTRFS: Implement btrfs_create_dir that can create directories in most case.
We need to handle a case when node is full, the solution should be split or
push data to another node.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Commit: 4896a3735e1cf5209686f3c78c8ac5935206ce7f
URL: http://cgit.haiku-os.org/haiku/commit/?id=4896a3735e1c
Author: hyche <cvghy116@xxxxxxxxx>
Date: Mon Aug 28 23:55:13 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:04 2017 UTC
BTRFS: Implement btrfs_remove_dir that can remove directories in most case.
We need to handle a case when node size is small reasonably it can be merged
with another node or push data from other node to this node.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
############################################################################
Revision: hrev51666
Commit: 99768086b1493648abee3f076683cc9fefa5923e
URL: http://cgit.haiku-os.org/haiku/commit/?id=99768086b149
Author: hyche <cvghy116@xxxxxxxxx>
Date: Wed Aug 30 00:40:57 2017 UTC
Committer: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Commit-Date: Sun Dec 10 16:03:56 2017 UTC
BTRFS: Add author and license.
Signed-off-by: Augustin Cavalier <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
