diff options
author | Nikolay Borisov <nborisov@suse.com> | 2018-10-01 17:46:16 +0300 |
---|---|---|
committer | David Sterba <dsterba@suse.com> | 2018-10-25 16:11:39 +0200 |
commit | 8c028efe4a31e15c0d106daf6218dedc373273c6 (patch) | |
tree | 58d6efe31920b5112e8b6c4ab5bdcaf334b09626 /ctree.c | |
parent | a9ce9286f24b299ea2a8465d89cee659c3f5dcf1 (diff) |
btrfs-progs: Pull free space tree related code from kernel
To help implement free space tree checker in user space some kernel
function are necessary, namely iterating/deleting/adding freespace
items, some internal search functions. Functions to populate a block
group based on the extent tree. The code is largely copy/paste from
the kernel with locking eliminated (i.e free_space_lock). It supports
reading/writing of both bitmap and extent based FST trees.
Signed-off-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>
Diffstat (limited to 'ctree.c')
-rw-r--r-- | ctree.c | 74 |
1 files changed, 74 insertions, 0 deletions
@@ -1226,6 +1226,80 @@ again: } /* + * Helper to use instead of search slot if no exact match is needed but + * instead the next or previous item should be returned. + * When find_higher is true, the next higher item is returned, the next lower + * otherwise. + * When return_any and find_higher are both true, and no higher item is found, + * return the next lower instead. + * When return_any is true and find_higher is false, and no lower item is found, + * return the next higher instead. + * It returns 0 if any item is found, 1 if none is found (tree empty), and + * < 0 on error + */ +int btrfs_search_slot_for_read(struct btrfs_root *root, + const struct btrfs_key *key, + struct btrfs_path *p, int find_higher, + int return_any) +{ + int ret; + struct extent_buffer *leaf; + +again: + ret = btrfs_search_slot(NULL, root, key, p, 0, 0); + if (ret <= 0) + return ret; + /* + * A return value of 1 means the path is at the position where the item + * should be inserted. Normally this is the next bigger item, but in + * case the previous item is the last in a leaf, path points to the + * first free slot in the previous leaf, i.e. at an invalid item. + */ + leaf = p->nodes[0]; + + if (find_higher) { + if (p->slots[0] >= btrfs_header_nritems(leaf)) { + ret = btrfs_next_leaf(root, p); + if (ret <= 0) + return ret; + if (!return_any) + return 1; + /* + * No higher item found, return the next lower instead + */ + return_any = 0; + find_higher = 0; + btrfs_release_path(p); + goto again; + } + } else { + if (p->slots[0] == 0) { + ret = btrfs_prev_leaf(root, p); + if (ret < 0) + return ret; + if (!ret) { + leaf = p->nodes[0]; + if (p->slots[0] == btrfs_header_nritems(leaf)) + p->slots[0]--; + return 0; + } + if (!return_any) + return 1; + /* + * No lower item found, return the next higher instead + */ + return_any = 0; + find_higher = 1; + btrfs_release_path(p); + goto again; + } else { + --p->slots[0]; + } + } + return 0; +} + +/* * adjust the pointers going up the tree, starting at level * making sure the right key of each node is points to 'key'. * This is used after shifting pointers to the left, so it stops |