^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: GPL-2.0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (C) 2011 STRATO. All rights reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #ifndef BTRFS_BACKREF_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #define BTRFS_BACKREF_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include <linux/btrfs.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include "ulist.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include "disk-io.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include "extent_io.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) struct inode_fs_paths {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) struct btrfs_path *btrfs_path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) struct btrfs_root *fs_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) struct btrfs_data_container *fspath;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) typedef int (iterate_extent_inodes_t)(u64 inum, u64 offset, u64 root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) void *ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) struct btrfs_path *path, struct btrfs_key *found_key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) u64 *flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) struct btrfs_key *key, struct btrfs_extent_item *ei,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) u32 item_size, u64 *out_root, u8 *out_level);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) u64 extent_item_objectid,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) u64 extent_offset, int search_commit_root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) iterate_extent_inodes_t *iterate, void *ctx,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) bool ignore_offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) iterate_extent_inodes_t *iterate, void *ctx,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) bool ignore_offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) struct btrfs_fs_info *fs_info, u64 bytenr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) u64 time_seq, struct ulist **leafs,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) const u64 *extent_item_pos, bool ignore_offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) struct btrfs_fs_info *fs_info, u64 bytenr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) u64 time_seq, struct ulist **roots, bool ignore_offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) u32 name_len, unsigned long name_off,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) struct extent_buffer *eb_in, u64 parent,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) char *dest, u32 size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) struct btrfs_data_container *init_data_container(u32 total_bytes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) struct btrfs_path *path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) void free_ipath(struct inode_fs_paths *ipath);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) u64 start_off, struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) struct btrfs_inode_extref **ret_extref,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) u64 *found_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) struct ulist *roots, struct ulist *tmp_ulist);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) int __init btrfs_prelim_ref_init(void);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) void __cold btrfs_prelim_ref_exit(void);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) struct prelim_ref {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) struct rb_node rbnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) u64 root_id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) struct btrfs_key key_for_search;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) int level;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) int count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) struct extent_inode_elem *inode_list;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) u64 parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) u64 wanted_disk_byte;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * Iterate backrefs of one extent.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * Now it only supports iteration of tree block in commit root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) struct btrfs_backref_iter {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) u64 bytenr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) struct btrfs_path *path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) struct btrfs_fs_info *fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) struct btrfs_key cur_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) u32 item_ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) u32 cur_ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) u32 end_ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) struct btrfs_backref_iter *btrfs_backref_iter_alloc(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) struct btrfs_fs_info *fs_info, gfp_t gfp_flag);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) static inline void btrfs_backref_iter_free(struct btrfs_backref_iter *iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) if (!iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) btrfs_free_path(iter->path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) kfree(iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) static inline struct extent_buffer *btrfs_backref_get_eb(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) struct btrfs_backref_iter *iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) if (!iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) return iter->path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) * For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) * is btrfs_tree_block_info, without a btrfs_extent_inline_ref header.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) * This helper determines if that's the case.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) static inline bool btrfs_backref_has_tree_block_info(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) struct btrfs_backref_iter *iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) iter->cur_ptr - iter->item_ptr == sizeof(struct btrfs_extent_item))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) int btrfs_backref_iter_next(struct btrfs_backref_iter *iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) static inline bool btrfs_backref_iter_is_inline_ref(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) struct btrfs_backref_iter *iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) iter->cur_key.type == BTRFS_METADATA_ITEM_KEY)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) static inline void btrfs_backref_iter_release(struct btrfs_backref_iter *iter)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) iter->bytenr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) iter->item_ptr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) iter->cur_ptr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) iter->end_ptr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) btrfs_release_path(iter->path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) memset(&iter->cur_key, 0, sizeof(iter->cur_key));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) * Backref cache related structures
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) * The whole objective of backref_cache is to build a bi-directional map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) * of tree blocks (represented by backref_node) and all their parents.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) * Represent a tree block in the backref cache
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) struct btrfs_backref_node {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) struct {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) struct rb_node rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) u64 bytenr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) }; /* Use rb_simple_node for search/insert */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) u64 new_bytenr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) /* Objectid of tree block owner, can be not uptodate */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) u64 owner;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) /* Link to pending, changed or detached list */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) struct list_head list;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) /* List of upper level edges, which link this node to its parents */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) struct list_head upper;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) /* List of lower level edges, which link this node to its children */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) struct list_head lower;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) /* NULL if this node is not tree root */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) struct btrfs_root *root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) /* Extent buffer got by COWing the block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) struct extent_buffer *eb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) /* Level of the tree block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) unsigned int level:8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) /* Is the block in a non-shareable tree */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) unsigned int cowonly:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) /* 1 if no child node is in the cache */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) unsigned int lowest:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) /* Is the extent buffer locked */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) unsigned int locked:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) /* Has the block been processed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) unsigned int processed:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) /* Have backrefs of this block been checked */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) unsigned int checked:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) * 1 if corresponding block has been COWed but some upper level block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) * pointers may not point to the new location
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) unsigned int pending:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) /* 1 if the backref node isn't connected to any other backref node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) unsigned int detached:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) * For generic purpose backref cache, where we only care if it's a reloc
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) * root, doesn't care the source subvolid.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) unsigned int is_reloc_root:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) #define LOWER 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) #define UPPER 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) * Represent an edge connecting upper and lower backref nodes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) struct btrfs_backref_edge {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) * list[LOWER] is linked to btrfs_backref_node::upper of lower level
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) * node, and list[UPPER] is linked to btrfs_backref_node::lower of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) * upper level node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) * Also, build_backref_tree() uses list[UPPER] for pending edges, before
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) * linking list[UPPER] to its upper level nodes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) struct list_head list[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) /* Two related nodes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) struct btrfs_backref_node *node[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) struct btrfs_backref_cache {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) /* Red black tree of all backref nodes in the cache */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) struct rb_root rb_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) /* For passing backref nodes to btrfs_reloc_cow_block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) struct btrfs_backref_node *path[BTRFS_MAX_LEVEL];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) * List of blocks that have been COWed but some block pointers in upper
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) * level blocks may not reflect the new location
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) struct list_head pending[BTRFS_MAX_LEVEL];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) /* List of backref nodes with no child node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) struct list_head leaves;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) /* List of blocks that have been COWed in current transaction */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) struct list_head changed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) /* List of detached backref node. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) struct list_head detached;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) u64 last_trans;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) int nr_nodes;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) int nr_edges;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) /* List of unchecked backref edges during backref cache build */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) struct list_head pending_edge;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) /* List of useless backref nodes during backref cache build */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) struct list_head useless_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) struct btrfs_fs_info *fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) * Whether this cache is for relocation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) * Reloction backref cache require more info for reloc root compared
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) * to generic backref cache.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) unsigned int is_reloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) struct btrfs_backref_cache *cache, int is_reloc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) struct btrfs_backref_node *btrfs_backref_alloc_node(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) struct btrfs_backref_cache *cache, u64 bytenr, int level);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) struct btrfs_backref_edge *btrfs_backref_alloc_edge(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) struct btrfs_backref_cache *cache);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) #define LINK_LOWER (1 << 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) #define LINK_UPPER (1 << 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) static inline void btrfs_backref_link_edge(struct btrfs_backref_edge *edge,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) struct btrfs_backref_node *lower,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) struct btrfs_backref_node *upper,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) int link_which)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) ASSERT(upper && lower && upper->level == lower->level + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) edge->node[LOWER] = lower;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) edge->node[UPPER] = upper;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) if (link_which & LINK_LOWER)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) list_add_tail(&edge->list[LOWER], &lower->upper);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) if (link_which & LINK_UPPER)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) list_add_tail(&edge->list[UPPER], &upper->lower);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) static inline void btrfs_backref_free_node(struct btrfs_backref_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) struct btrfs_backref_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) if (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) ASSERT(list_empty(&node->list));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) ASSERT(list_empty(&node->lower));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) ASSERT(node->eb == NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) cache->nr_nodes--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) btrfs_put_root(node->root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) kfree(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) static inline void btrfs_backref_free_edge(struct btrfs_backref_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) struct btrfs_backref_edge *edge)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) if (edge) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) cache->nr_edges--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) kfree(edge);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) static inline void btrfs_backref_unlock_node_buffer(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) struct btrfs_backref_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) if (node->locked) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) btrfs_tree_unlock(node->eb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) node->locked = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) static inline void btrfs_backref_drop_node_buffer(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) struct btrfs_backref_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) if (node->eb) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) btrfs_backref_unlock_node_buffer(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) free_extent_buffer(node->eb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) node->eb = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) * Drop the backref node from cache without cleaning up its children
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) * edges.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) * This can only be called on node without parent edges.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) * The children edges are still kept as is.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) static inline void btrfs_backref_drop_node(struct btrfs_backref_cache *tree,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) struct btrfs_backref_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) ASSERT(list_empty(&node->upper));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) btrfs_backref_drop_node_buffer(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) list_del_init(&node->list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) list_del_init(&node->lower);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) if (!RB_EMPTY_NODE(&node->rb_node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) rb_erase(&node->rb_node, &tree->rb_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) btrfs_backref_free_node(tree, node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) struct btrfs_backref_node *node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) void btrfs_backref_release_cache(struct btrfs_backref_cache *cache);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) static inline void btrfs_backref_panic(struct btrfs_fs_info *fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) u64 bytenr, int errno)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) btrfs_panic(fs_info, errno,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) "Inconsistency in backref cache found at offset %llu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) bytenr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) struct btrfs_backref_iter *iter,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) struct btrfs_key *node_key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) struct btrfs_backref_node *cur);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) struct btrfs_backref_node *start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) void btrfs_backref_error_cleanup(struct btrfs_backref_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) struct btrfs_backref_node *node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) #endif
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags