Message ID | 20200214081354.56605-2-wqu@suse.com (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
Series | Btrfs: relocation: Refactor build_backref_tree() using btrfs_backref_iterator infrastructure | expand |
On 14/02/2020 09:14, Qu Wenruo wrote: > 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 works, like Nit: work ^ > search the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed ^ searching I think but a native English speaker might want to double check on that. [...] > 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); I personally like for each style macros to wrap these a lot, but seeing the loop is only used once in your patchset I'm not sure it's worth adding it.
On 14.02.20 г. 10:13 ч., Qu Wenruo wrote: > 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 works, like > search 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 | 76 ++++++++++++++++++++++++++++++++++++++++++++++ > 2 files changed, 134 insertions(+) > > diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c > index e5d85311d5d5..73c4829609c9 100644 > --- a/fs/btrfs/backref.c > +++ b/fs/btrfs/backref.c > @@ -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 */ > + if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) { > + ret = -ENOTTY; > + goto release; > + } Isn't this implied bye the fact you are searching for METADATA ITEMS to begin with ? Considering this shouldn't detecting EXTENT_FLAG_DATA in the backrefs of a METADATA_EXTENT be considered a corruption? > + iterator->cur_ptr = iterator->item_ptr + sizeof(*ei); > + return 0; > +release: > + iterator->end_ptr = 0; > + iterator->cur_ptr = 0; > + iterator->item_ptr = 0; > + iterator->cur_key.objectid = 0; > + iterator->cur_key.type = 0; > + iterator->cur_key.offset = 0; > + btrfs_release_path(path); > + return ret; > +} > diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h > index 777f61dc081e..b53301f2147f 100644 > --- a/fs/btrfs/backref.h > +++ b/fs/btrfs/backref.h > @@ -74,4 +74,80 @@ 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); > +} > + > +static inline struct extent_buffer * > +btrfs_backref_get_eb(struct btrfs_backref_iterator *iterator) > +{ > + if (!iterator) > + return NULL; > + return iterator->path->nodes[0]; > +} > + > +/* > + * For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data > + * is btrfs_tree_block_info, without a btrfs_extent_inline_ref header. > + * > + * This helper is here to determine if that's the case. > + */ > +static inline bool btrfs_backref_has_tree_block_info( > + struct btrfs_backref_iterator *iterator) > +{ > + if (iterator->cur_key.type == BTRFS_EXTENT_ITEM_KEY && > + iterator->cur_ptr - iterator->item_ptr == > + sizeof(struct btrfs_extent_item)) > + return true; > + return false; > +} > + > +int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator, > + u64 bytenr); > +int btrfs_backref_iterator_next(struct btrfs_backref_iterator *iterator); > + > #endif >
<snip> > + * This helper is here to determine if that's the case. > + */ > +static inline bool btrfs_backref_has_tree_block_info( > + struct btrfs_backref_iterator *iterator) > +{ > + if (iterator->cur_key.type == BTRFS_EXTENT_ITEM_KEY && > + iterator->cur_ptr - iterator->item_ptr == > + sizeof(struct btrfs_extent_item)) > + return true; > + return false; > +} > + > +int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator, > + u64 bytenr); > +int btrfs_backref_iterator_next(struct btrfs_backref_iterator *iterator); You are exposing a function here which is not implemented. Remove this line and add it in the next patch where you actually introduce iterator_next. > + > #endif >
On 2020/2/14 下午5:19, Nikolay Borisov wrote: > > > On 14.02.20 г. 10:13 ч., Qu Wenruo wrote: >> 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 works, like >> search 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 | 76 ++++++++++++++++++++++++++++++++++++++++++++++ >> 2 files changed, 134 insertions(+) >> >> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c >> index e5d85311d5d5..73c4829609c9 100644 >> --- a/fs/btrfs/backref.c >> +++ b/fs/btrfs/backref.c >> @@ -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 */ >> + if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) { >> + ret = -ENOTTY; >> + goto release; >> + } > > Isn't this implied bye the fact you are searching for METADATA ITEMS to > begin with ? Considering this shouldn't detecting EXTENT_FLAG_DATA in > the backrefs of a METADATA_EXTENT be considered a corruption? For non skinny-metadata fs, we can hit with EXTENT_ITEM. So it's still possible to hit a corruption undetected by tree-checker. But you're right, we shouldn't really hit a data extent here, as previous loops have excluded all data extents. But I'm just the guy who want to be extra cautious. Thanks, Qu > >> + iterator->cur_ptr = iterator->item_ptr + sizeof(*ei); >> + return 0; >> +release: >> + iterator->end_ptr = 0; >> + iterator->cur_ptr = 0; >> + iterator->item_ptr = 0; >> + iterator->cur_key.objectid = 0; >> + iterator->cur_key.type = 0; >> + iterator->cur_key.offset = 0; >> + btrfs_release_path(path); >> + return ret; >> +} >> diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h >> index 777f61dc081e..b53301f2147f 100644 >> --- a/fs/btrfs/backref.h >> +++ b/fs/btrfs/backref.h >> @@ -74,4 +74,80 @@ 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); >> +} >> + >> +static inline struct extent_buffer * >> +btrfs_backref_get_eb(struct btrfs_backref_iterator *iterator) >> +{ >> + if (!iterator) >> + return NULL; >> + return iterator->path->nodes[0]; >> +} >> + >> +/* >> + * For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data >> + * is btrfs_tree_block_info, without a btrfs_extent_inline_ref header. >> + * >> + * This helper is here to determine if that's the case. >> + */ >> +static inline bool btrfs_backref_has_tree_block_info( >> + struct btrfs_backref_iterator *iterator) >> +{ >> + if (iterator->cur_key.type == BTRFS_EXTENT_ITEM_KEY && >> + iterator->cur_ptr - iterator->item_ptr == >> + sizeof(struct btrfs_extent_item)) >> + return true; >> + return false; >> +} >> + >> +int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator, >> + u64 bytenr); >> +int btrfs_backref_iterator_next(struct btrfs_backref_iterator *iterator); >> + >> #endif >>
On 2020/2/14 下午5:24, Nikolay Borisov wrote: > <snip> > >> + * This helper is here to determine if that's the case. >> + */ >> +static inline bool btrfs_backref_has_tree_block_info( >> + struct btrfs_backref_iterator *iterator) >> +{ >> + if (iterator->cur_key.type == BTRFS_EXTENT_ITEM_KEY && >> + iterator->cur_ptr - iterator->item_ptr == >> + sizeof(struct btrfs_extent_item)) >> + return true; >> + return false; >> +} >> + >> +int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator, >> + u64 bytenr); >> +int btrfs_backref_iterator_next(struct btrfs_backref_iterator *iterator); > > You are exposing a function here which is not implemented. Remove this > line and add it in the next patch where you actually introduce > iterator_next. OK, I'll take this as a generic principle for later patches. Thanks, Qu > >> + >> #endif >>
On 14.02.20 г. 11:33 ч., Qu Wenruo wrote: > > > On 2020/2/14 下午5:19, Nikolay Borisov wrote: >> >> >> On 14.02.20 г. 10:13 ч., Qu Wenruo wrote: >>> 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 works, like >>> search 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 | 76 ++++++++++++++++++++++++++++++++++++++++++++++ >>> 2 files changed, 134 insertions(+) >>> >>> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c >>> index e5d85311d5d5..73c4829609c9 100644 >>> --- a/fs/btrfs/backref.c >>> +++ b/fs/btrfs/backref.c >>> @@ -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 */ >>> + if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) { >>> + ret = -ENOTTY; >>> + goto release; >>> + } >> >> Isn't this implied bye the fact you are searching for METADATA ITEMS to >> begin with ? Considering this shouldn't detecting EXTENT_FLAG_DATA in >> the backrefs of a METADATA_EXTENT be considered a corruption? > > For non skinny-metadata fs, we can hit with EXTENT_ITEM. > So it's still possible to hit a corruption undetected by tree-checker. > > But you're right, we shouldn't really hit a data extent here, as > previous loops have excluded all data extents. Then put a comment saying this is done as an extra precaution. <split>
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index e5d85311d5d5..73c4829609c9 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -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 */ + 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: + iterator->end_ptr = 0; + iterator->cur_ptr = 0; + iterator->item_ptr = 0; + iterator->cur_key.objectid = 0; + iterator->cur_key.type = 0; + iterator->cur_key.offset = 0; + btrfs_release_path(path); + return ret; +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 777f61dc081e..b53301f2147f 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -74,4 +74,80 @@ 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); +} + +static inline struct extent_buffer * +btrfs_backref_get_eb(struct btrfs_backref_iterator *iterator) +{ + if (!iterator) + return NULL; + return iterator->path->nodes[0]; +} + +/* + * For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data + * is btrfs_tree_block_info, without a btrfs_extent_inline_ref header. + * + * This helper is here to determine if that's the case. + */ +static inline bool btrfs_backref_has_tree_block_info( + struct btrfs_backref_iterator *iterator) +{ + if (iterator->cur_key.type == BTRFS_EXTENT_ITEM_KEY && + iterator->cur_ptr - iterator->item_ptr == + sizeof(struct btrfs_extent_item)) + return true; + return false; +} + +int btrfs_backref_iterator_start(struct btrfs_backref_iterator *iterator, + u64 bytenr); +int btrfs_backref_iterator_next(struct btrfs_backref_iterator *iterator); + #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 works, like search 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 | 76 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 134 insertions(+)