@@ -2252,3 +2252,61 @@ void free_ipath(struct inode_fs_paths *ipath)
kvfree(ipath->fspath);
kfree(ipath);
}
+
+int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator,
+ u64 bytenr)
+{
+ struct btrfs_fs_info *fs_info = iterator->fs_info;
+ struct btrfs_path *path = iterator->path;
+ struct btrfs_extent_item *ei;
+ struct btrfs_key key;
+ int ret;
+
+ key.objectid = bytenr;
+ key.type = BTRFS_METADATA_ITEM_KEY;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
+ if (ret < 0)
+ return ret;
+ if (ret == 0) {
+ ret = -EUCLEAN;
+ goto release;
+ }
+ if (path->slots[0] == 0) {
+ WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
+ ret = -EUCLEAN;
+ goto release;
+ }
+ path->slots[0]--;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+ if (!(key.type == BTRFS_EXTENT_ITEM_KEY ||
+ key.type == BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {
+ ret = -ENOENT;
+ goto release;
+ }
+ memcpy(&iterator->cur_key, &key, sizeof(key));
+ iterator->end_ptr = btrfs_item_end_nr(path->nodes[0], path->slots[0]);
+ iterator->item_ptr = btrfs_item_ptr_offset(path->nodes[0],
+ path->slots[0]);
+ ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_extent_item);
+
+ /*
+ * Only support iteration on tree backref yet.
+ *
+ * This is extra precaustion for non skinny-metadata, where
+ * EXTENT_ITEM is also used for tree blocks, that we can only use
+ * extent flags to determine if it's a tree block.
+ */
+ if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {
+ ret = -ENOTTY;
+ goto release;
+ }
+ iterator->cur_ptr = iterator->item_ptr + sizeof(*ei);
+ return 0;
+release:
+ btrfs_backref_iterator_release(iterator);
+ return ret;
+}
@@ -74,4 +74,66 @@ struct prelim_ref {
u64 wanted_disk_byte;
};
+/*
+ * Helper structure to help iterate backrefs of one extent.
+ *
+ * Now it only supports iteration for tree block in commit root.
+ */
+struct btrfs_backref_iterator {
+ u64 bytenr;
+ struct btrfs_path *path;
+ struct btrfs_fs_info *fs_info;
+ struct btrfs_key cur_key;
+ unsigned long item_ptr;
+ unsigned long cur_ptr;
+ unsigned long end_ptr;
+};
+
+static inline struct btrfs_backref_iterator *
+btrfs_backref_iterator_alloc(struct btrfs_fs_info *fs_info, gfp_t gfp_flag)
+{
+ struct btrfs_backref_iterator *ret;
+
+ ret = kzalloc(sizeof(*ret), gfp_flag);
+ if (!ret)
+ return NULL;
+
+ ret->path = btrfs_alloc_path();
+ if (!ret) {
+ kfree(ret);
+ return NULL;
+ }
+
+ /* Current backref iterator only supports iteration in commit root */
+ ret->path->search_commit_root = 1;
+ ret->path->skip_locking = 1;
+ ret->path->reada = READA_FORWARD;
+ ret->fs_info = fs_info;
+
+ return ret;
+}
+
+static inline void btrfs_backref_iterator_free(
+ struct btrfs_backref_iterator *iterator)
+{
+ if (!iterator)
+ return;
+ btrfs_free_path(iterator->path);
+ kfree(iterator);
+}
+
+int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator,
+ u64 bytenr);
+
+static inline void
+btrfs_backref_iterator_release(struct btrfs_backref_iterator *iterator)
+{
+ iterator->bytenr = 0;
+ iterator->item_ptr = 0;
+ iterator->cur_ptr = 0;
+ iterator->end_ptr = 0;
+ btrfs_release_path(iterator->path);
+ memset(&iterator->cur_key, 0, sizeof(iterator->cur_key));
+}
+
#endif
Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs. Normally this would result pretty complex code, something like: btrfs_search_slot() /* Ensure we are at EXTENT_ITEM/METADATA_ITEM */ while (1) { /* Loop for extent tree items */ while (ptr < end) { /* Loop for inlined items */ /* REAL WORK HERE */ } next: ret = btrfs_next_item() /* Ensure we're still at keyed item for specified bytenr */ } The idea of btrfs_backref_iterator is to avoid such complex and hard to read code structure, but something like the following: iterator = btrfs_backref_iterator_alloc(); ret = btrfs_backref_iterator_start(iterator, bytenr); if (ret < 0) goto out; for (; ; ret = btrfs_backref_iterator_next(iterator)) { /* REAL WORK HERE */ } out: btrfs_backref_iterator_free(iterator); This patch is just the skeleton + btrfs_backref_iterator_start() code. Signed-off-by: Qu Wenruo <wqu@suse.com> --- fs/btrfs/backref.c | 58 +++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 62 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 120 insertions(+)