19888c340SDavid Sterba /* SPDX-License-Identifier: GPL-2.0 */ 2a542ad1bSJan Schmidt /* 3a542ad1bSJan Schmidt * Copyright (C) 2011 STRATO. All rights reserved. 4a542ad1bSJan Schmidt */ 5a542ad1bSJan Schmidt 69888c340SDavid Sterba #ifndef BTRFS_BACKREF_H 79888c340SDavid Sterba #define BTRFS_BACKREF_H 8a542ad1bSJan Schmidt 955e301fdSFilipe Brandenburger #include <linux/btrfs.h> 109b569ea0SJosef Bacik #include "messages.h" 118da6d581SJan Schmidt #include "ulist.h" 12741188d3SQu Wenruo #include "disk-io.h" 1391cb916cSAlexander Block #include "extent_io.h" 14a542ad1bSJan Schmidt 15*6ce6ba53SFilipe Manana /* 16*6ce6ba53SFilipe Manana * Pass to backref walking functions to tell them to include references from 17*6ce6ba53SFilipe Manana * all file extent items that point to the target data extent, regardless if 18*6ce6ba53SFilipe Manana * they refer to the whole extent or just sections of it (bookend extents). 19*6ce6ba53SFilipe Manana */ 20*6ce6ba53SFilipe Manana #define BTRFS_IGNORE_EXTENT_OFFSET ((u64)-1) 21*6ce6ba53SFilipe Manana 22a542ad1bSJan Schmidt struct inode_fs_paths { 23a542ad1bSJan Schmidt struct btrfs_path *btrfs_path; 24a542ad1bSJan Schmidt struct btrfs_root *fs_root; 25a542ad1bSJan Schmidt struct btrfs_data_container *fspath; 26a542ad1bSJan Schmidt }; 27a542ad1bSJan Schmidt 2812a824dcSFilipe Manana struct btrfs_backref_shared_cache_entry { 2912a824dcSFilipe Manana u64 bytenr; 3012a824dcSFilipe Manana u64 gen; 3112a824dcSFilipe Manana bool is_shared; 3212a824dcSFilipe Manana }; 3312a824dcSFilipe Manana 3473e339e6SFilipe Manana #define BTRFS_BACKREF_CTX_PREV_EXTENTS_SIZE 8 3573e339e6SFilipe Manana 3661dbb952SFilipe Manana struct btrfs_backref_share_check_ctx { 3784a7949dSFilipe Manana /* Ulists used during backref walking. */ 3884a7949dSFilipe Manana struct ulist refs; 3912a824dcSFilipe Manana /* 40877c1476SFilipe Manana * The current leaf the caller of btrfs_is_data_extent_shared() is at. 41877c1476SFilipe Manana * Typically the caller (at the moment only fiemap) tries to determine 42877c1476SFilipe Manana * the sharedness of data extents point by file extent items from entire 43877c1476SFilipe Manana * leaves. 44877c1476SFilipe Manana */ 45877c1476SFilipe Manana u64 curr_leaf_bytenr; 46877c1476SFilipe Manana /* 47877c1476SFilipe Manana * The previous leaf the caller was at in the previous call to 48877c1476SFilipe Manana * btrfs_is_data_extent_shared(). This may be the same as the current 49877c1476SFilipe Manana * leaf. On the first call it must be 0. 50877c1476SFilipe Manana */ 51877c1476SFilipe Manana u64 prev_leaf_bytenr; 52877c1476SFilipe Manana /* 5312a824dcSFilipe Manana * A path from a root to a leaf that has a file extent item pointing to 5412a824dcSFilipe Manana * a given data extent should never exceed the maximum b+tree height. 5512a824dcSFilipe Manana */ 5661dbb952SFilipe Manana struct btrfs_backref_shared_cache_entry path_cache_entries[BTRFS_MAX_LEVEL]; 5761dbb952SFilipe Manana bool use_path_cache; 5873e339e6SFilipe Manana /* 5973e339e6SFilipe Manana * Cache the sharedness result for the last few extents we have found, 6073e339e6SFilipe Manana * but only for extents for which we have multiple file extent items 6173e339e6SFilipe Manana * that point to them. 6273e339e6SFilipe Manana * It's very common to have several file extent items that point to the 6373e339e6SFilipe Manana * same extent (bytenr) but with different offsets and lengths. This 6473e339e6SFilipe Manana * typically happens for COW writes, partial writes into prealloc 6573e339e6SFilipe Manana * extents, NOCOW writes after snapshoting a root, hole punching or 6673e339e6SFilipe Manana * reflinking within the same file (less common perhaps). 6773e339e6SFilipe Manana * So keep a small cache with the lookup results for the extent pointed 6873e339e6SFilipe Manana * by the last few file extent items. This cache is checked, with a 6973e339e6SFilipe Manana * linear scan, whenever btrfs_is_data_extent_shared() is called, so 7073e339e6SFilipe Manana * it must be small so that it does not negatively affect performance in 7173e339e6SFilipe Manana * case we don't have multiple file extent items that point to the same 7273e339e6SFilipe Manana * data extent. 7373e339e6SFilipe Manana */ 7473e339e6SFilipe Manana struct { 7573e339e6SFilipe Manana u64 bytenr; 7673e339e6SFilipe Manana bool is_shared; 7773e339e6SFilipe Manana } prev_extents_cache[BTRFS_BACKREF_CTX_PREV_EXTENTS_SIZE]; 7873e339e6SFilipe Manana /* 7973e339e6SFilipe Manana * The slot in the prev_extents_cache array that will be used for 8073e339e6SFilipe Manana * storing the sharedness result of a new data extent. 8173e339e6SFilipe Manana */ 8273e339e6SFilipe Manana int prev_extents_cache_slot; 8312a824dcSFilipe Manana }; 8412a824dcSFilipe Manana 85c7499a64SFilipe Manana typedef int (iterate_extent_inodes_t)(u64 inum, u64 offset, u64 num_bytes, 86c7499a64SFilipe Manana u64 root, void *ctx); 87a542ad1bSJan Schmidt 8884a7949dSFilipe Manana struct btrfs_backref_share_check_ctx *btrfs_alloc_backref_share_check_ctx(void); 8984a7949dSFilipe Manana void btrfs_free_backref_share_ctx(struct btrfs_backref_share_check_ctx *ctx); 9084a7949dSFilipe Manana 91a542ad1bSJan Schmidt int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical, 9269917e43SLiu Bo struct btrfs_path *path, struct btrfs_key *found_key, 9369917e43SLiu Bo u64 *flags); 94a542ad1bSJan Schmidt 95a542ad1bSJan Schmidt int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb, 966eda71d0SLiu Bo struct btrfs_key *key, struct btrfs_extent_item *ei, 976eda71d0SLiu Bo u32 item_size, u64 *out_root, u8 *out_level); 98a542ad1bSJan Schmidt 99a542ad1bSJan Schmidt int iterate_extent_inodes(struct btrfs_fs_info *fs_info, 100a542ad1bSJan Schmidt u64 extent_item_objectid, 1017a3ae2f8SJan Schmidt u64 extent_offset, int search_commit_root, 102*6ce6ba53SFilipe Manana iterate_extent_inodes_t *iterate, void *ctx); 103a542ad1bSJan Schmidt 104a542ad1bSJan Schmidt int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info, 105e3059ec0SDavid Sterba struct btrfs_path *path, void *ctx, 106c995ab3cSZygo Blaxell bool ignore_offset); 107a542ad1bSJan Schmidt 108a542ad1bSJan Schmidt int paths_from_inode(u64 inum, struct inode_fs_paths *ipath); 109a542ad1bSJan Schmidt 11019b546d7SQu Wenruo int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, 11119b546d7SQu Wenruo struct btrfs_fs_info *fs_info, u64 bytenr, 11219b546d7SQu Wenruo u64 time_seq, struct ulist **leafs, 113*6ce6ba53SFilipe Manana u64 extent_item_pos); 1148da6d581SJan Schmidt int btrfs_find_all_roots(struct btrfs_trans_handle *trans, 1158da6d581SJan Schmidt struct btrfs_fs_info *fs_info, u64 bytenr, 116c7bcbb21SFilipe Manana u64 time_seq, struct ulist **roots, 1178949b9a1SFilipe Manana bool skip_commit_root_sem); 11896b5bd77SJan Schmidt char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path, 11996b5bd77SJan Schmidt u32 name_len, unsigned long name_off, 12096b5bd77SJan Schmidt struct extent_buffer *eb_in, u64 parent, 12196b5bd77SJan Schmidt char *dest, u32 size); 1228da6d581SJan Schmidt 123a542ad1bSJan Schmidt struct btrfs_data_container *init_data_container(u32 total_bytes); 124a542ad1bSJan Schmidt struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root, 125a542ad1bSJan Schmidt struct btrfs_path *path); 126a542ad1bSJan Schmidt void free_ipath(struct inode_fs_paths *ipath); 127a542ad1bSJan Schmidt 128f186373fSMark Fasheh int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid, 129f186373fSMark Fasheh u64 start_off, struct btrfs_path *path, 130f186373fSMark Fasheh struct btrfs_inode_extref **ret_extref, 131f186373fSMark Fasheh u64 *found_off); 132ceb707daSFilipe Manana int btrfs_is_data_extent_shared(struct btrfs_inode *inode, u64 bytenr, 133b8f164e3SFilipe Manana u64 extent_gen, 13461dbb952SFilipe Manana struct btrfs_backref_share_check_ctx *ctx); 135f186373fSMark Fasheh 136b9e9a6cbSWang Shilong int __init btrfs_prelim_ref_init(void); 137e67c718bSDavid Sterba void __cold btrfs_prelim_ref_exit(void); 13800142756SJeff Mahoney 13900142756SJeff Mahoney struct prelim_ref { 14000142756SJeff Mahoney struct rb_node rbnode; 14100142756SJeff Mahoney u64 root_id; 14200142756SJeff Mahoney struct btrfs_key key_for_search; 14300142756SJeff Mahoney int level; 14400142756SJeff Mahoney int count; 14500142756SJeff Mahoney struct extent_inode_elem *inode_list; 14600142756SJeff Mahoney u64 parent; 14700142756SJeff Mahoney u64 wanted_disk_byte; 14800142756SJeff Mahoney }; 14900142756SJeff Mahoney 150a37f232bSQu Wenruo /* 151a37f232bSQu Wenruo * Iterate backrefs of one extent. 152a37f232bSQu Wenruo * 153a37f232bSQu Wenruo * Now it only supports iteration of tree block in commit root. 154a37f232bSQu Wenruo */ 155a37f232bSQu Wenruo struct btrfs_backref_iter { 156a37f232bSQu Wenruo u64 bytenr; 157a37f232bSQu Wenruo struct btrfs_path *path; 158a37f232bSQu Wenruo struct btrfs_fs_info *fs_info; 159a37f232bSQu Wenruo struct btrfs_key cur_key; 160a37f232bSQu Wenruo u32 item_ptr; 161a37f232bSQu Wenruo u32 cur_ptr; 162a37f232bSQu Wenruo u32 end_ptr; 163a37f232bSQu Wenruo }; 164a37f232bSQu Wenruo 165d68194b2SDavid Sterba struct btrfs_backref_iter *btrfs_backref_iter_alloc(struct btrfs_fs_info *fs_info); 166a37f232bSQu Wenruo 167a37f232bSQu Wenruo static inline void btrfs_backref_iter_free(struct btrfs_backref_iter *iter) 168a37f232bSQu Wenruo { 169a37f232bSQu Wenruo if (!iter) 170a37f232bSQu Wenruo return; 171a37f232bSQu Wenruo btrfs_free_path(iter->path); 172a37f232bSQu Wenruo kfree(iter); 173a37f232bSQu Wenruo } 174a37f232bSQu Wenruo 175c39c2ddcSQu Wenruo static inline struct extent_buffer *btrfs_backref_get_eb( 176c39c2ddcSQu Wenruo struct btrfs_backref_iter *iter) 177c39c2ddcSQu Wenruo { 178c39c2ddcSQu Wenruo if (!iter) 179c39c2ddcSQu Wenruo return NULL; 180c39c2ddcSQu Wenruo return iter->path->nodes[0]; 181c39c2ddcSQu Wenruo } 182c39c2ddcSQu Wenruo 183c39c2ddcSQu Wenruo /* 184c39c2ddcSQu Wenruo * For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data 185c39c2ddcSQu Wenruo * is btrfs_tree_block_info, without a btrfs_extent_inline_ref header. 186c39c2ddcSQu Wenruo * 187c39c2ddcSQu Wenruo * This helper determines if that's the case. 188c39c2ddcSQu Wenruo */ 189c39c2ddcSQu Wenruo static inline bool btrfs_backref_has_tree_block_info( 190c39c2ddcSQu Wenruo struct btrfs_backref_iter *iter) 191c39c2ddcSQu Wenruo { 192c39c2ddcSQu Wenruo if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY && 193c39c2ddcSQu Wenruo iter->cur_ptr - iter->item_ptr == sizeof(struct btrfs_extent_item)) 194c39c2ddcSQu Wenruo return true; 195c39c2ddcSQu Wenruo return false; 196c39c2ddcSQu Wenruo } 197c39c2ddcSQu Wenruo 198a37f232bSQu Wenruo int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr); 199a37f232bSQu Wenruo 200c39c2ddcSQu Wenruo int btrfs_backref_iter_next(struct btrfs_backref_iter *iter); 201c39c2ddcSQu Wenruo 202c39c2ddcSQu Wenruo static inline bool btrfs_backref_iter_is_inline_ref( 203c39c2ddcSQu Wenruo struct btrfs_backref_iter *iter) 204c39c2ddcSQu Wenruo { 205c39c2ddcSQu Wenruo if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY || 206c39c2ddcSQu Wenruo iter->cur_key.type == BTRFS_METADATA_ITEM_KEY) 207c39c2ddcSQu Wenruo return true; 208c39c2ddcSQu Wenruo return false; 209c39c2ddcSQu Wenruo } 210c39c2ddcSQu Wenruo 211a37f232bSQu Wenruo static inline void btrfs_backref_iter_release(struct btrfs_backref_iter *iter) 212a37f232bSQu Wenruo { 213a37f232bSQu Wenruo iter->bytenr = 0; 214a37f232bSQu Wenruo iter->item_ptr = 0; 215a37f232bSQu Wenruo iter->cur_ptr = 0; 216a37f232bSQu Wenruo iter->end_ptr = 0; 217a37f232bSQu Wenruo btrfs_release_path(iter->path); 218a37f232bSQu Wenruo memset(&iter->cur_key, 0, sizeof(iter->cur_key)); 219a37f232bSQu Wenruo } 220a37f232bSQu Wenruo 22170535441SQu Wenruo /* 22270535441SQu Wenruo * Backref cache related structures 22370535441SQu Wenruo * 22470535441SQu Wenruo * The whole objective of backref_cache is to build a bi-directional map 22570535441SQu Wenruo * of tree blocks (represented by backref_node) and all their parents. 22670535441SQu Wenruo */ 22770535441SQu Wenruo 22870535441SQu Wenruo /* 22970535441SQu Wenruo * Represent a tree block in the backref cache 23070535441SQu Wenruo */ 23170535441SQu Wenruo struct btrfs_backref_node { 232e9a28dc5SQu Wenruo struct { 23370535441SQu Wenruo struct rb_node rb_node; 23470535441SQu Wenruo u64 bytenr; 235e9a28dc5SQu Wenruo }; /* Use rb_simple_node for search/insert */ 23670535441SQu Wenruo 23770535441SQu Wenruo u64 new_bytenr; 23870535441SQu Wenruo /* Objectid of tree block owner, can be not uptodate */ 23970535441SQu Wenruo u64 owner; 24070535441SQu Wenruo /* Link to pending, changed or detached list */ 24170535441SQu Wenruo struct list_head list; 24270535441SQu Wenruo 24370535441SQu Wenruo /* List of upper level edges, which link this node to its parents */ 24470535441SQu Wenruo struct list_head upper; 24570535441SQu Wenruo /* List of lower level edges, which link this node to its children */ 24670535441SQu Wenruo struct list_head lower; 24770535441SQu Wenruo 24870535441SQu Wenruo /* NULL if this node is not tree root */ 24970535441SQu Wenruo struct btrfs_root *root; 25070535441SQu Wenruo /* Extent buffer got by COWing the block */ 25170535441SQu Wenruo struct extent_buffer *eb; 25270535441SQu Wenruo /* Level of the tree block */ 25370535441SQu Wenruo unsigned int level:8; 25492a7cc42SQu Wenruo /* Is the block in a non-shareable tree */ 25570535441SQu Wenruo unsigned int cowonly:1; 25670535441SQu Wenruo /* 1 if no child node is in the cache */ 25770535441SQu Wenruo unsigned int lowest:1; 25870535441SQu Wenruo /* Is the extent buffer locked */ 25970535441SQu Wenruo unsigned int locked:1; 26070535441SQu Wenruo /* Has the block been processed */ 26170535441SQu Wenruo unsigned int processed:1; 26270535441SQu Wenruo /* Have backrefs of this block been checked */ 26370535441SQu Wenruo unsigned int checked:1; 26470535441SQu Wenruo /* 26570535441SQu Wenruo * 1 if corresponding block has been COWed but some upper level block 26670535441SQu Wenruo * pointers may not point to the new location 26770535441SQu Wenruo */ 26870535441SQu Wenruo unsigned int pending:1; 26970535441SQu Wenruo /* 1 if the backref node isn't connected to any other backref node */ 27070535441SQu Wenruo unsigned int detached:1; 27170535441SQu Wenruo 27270535441SQu Wenruo /* 27370535441SQu Wenruo * For generic purpose backref cache, where we only care if it's a reloc 27470535441SQu Wenruo * root, doesn't care the source subvolid. 27570535441SQu Wenruo */ 27670535441SQu Wenruo unsigned int is_reloc_root:1; 27770535441SQu Wenruo }; 27870535441SQu Wenruo 27970535441SQu Wenruo #define LOWER 0 28070535441SQu Wenruo #define UPPER 1 28170535441SQu Wenruo 28270535441SQu Wenruo /* 28370535441SQu Wenruo * Represent an edge connecting upper and lower backref nodes. 28470535441SQu Wenruo */ 28570535441SQu Wenruo struct btrfs_backref_edge { 28670535441SQu Wenruo /* 28770535441SQu Wenruo * list[LOWER] is linked to btrfs_backref_node::upper of lower level 28870535441SQu Wenruo * node, and list[UPPER] is linked to btrfs_backref_node::lower of 28970535441SQu Wenruo * upper level node. 29070535441SQu Wenruo * 29170535441SQu Wenruo * Also, build_backref_tree() uses list[UPPER] for pending edges, before 29270535441SQu Wenruo * linking list[UPPER] to its upper level nodes. 29370535441SQu Wenruo */ 29470535441SQu Wenruo struct list_head list[2]; 29570535441SQu Wenruo 29670535441SQu Wenruo /* Two related nodes */ 29770535441SQu Wenruo struct btrfs_backref_node *node[2]; 29870535441SQu Wenruo }; 29970535441SQu Wenruo 30070535441SQu Wenruo struct btrfs_backref_cache { 30170535441SQu Wenruo /* Red black tree of all backref nodes in the cache */ 30270535441SQu Wenruo struct rb_root rb_root; 30370535441SQu Wenruo /* For passing backref nodes to btrfs_reloc_cow_block */ 30470535441SQu Wenruo struct btrfs_backref_node *path[BTRFS_MAX_LEVEL]; 30570535441SQu Wenruo /* 30670535441SQu Wenruo * List of blocks that have been COWed but some block pointers in upper 30770535441SQu Wenruo * level blocks may not reflect the new location 30870535441SQu Wenruo */ 30970535441SQu Wenruo struct list_head pending[BTRFS_MAX_LEVEL]; 31070535441SQu Wenruo /* List of backref nodes with no child node */ 31170535441SQu Wenruo struct list_head leaves; 31270535441SQu Wenruo /* List of blocks that have been COWed in current transaction */ 31370535441SQu Wenruo struct list_head changed; 31470535441SQu Wenruo /* List of detached backref node. */ 31570535441SQu Wenruo struct list_head detached; 31670535441SQu Wenruo 31770535441SQu Wenruo u64 last_trans; 31870535441SQu Wenruo 31970535441SQu Wenruo int nr_nodes; 32070535441SQu Wenruo int nr_edges; 32170535441SQu Wenruo 32270535441SQu Wenruo /* List of unchecked backref edges during backref cache build */ 32370535441SQu Wenruo struct list_head pending_edge; 32470535441SQu Wenruo 32570535441SQu Wenruo /* List of useless backref nodes during backref cache build */ 32670535441SQu Wenruo struct list_head useless_node; 32770535441SQu Wenruo 32870535441SQu Wenruo struct btrfs_fs_info *fs_info; 32970535441SQu Wenruo 33070535441SQu Wenruo /* 33170535441SQu Wenruo * Whether this cache is for relocation 33270535441SQu Wenruo * 33370535441SQu Wenruo * Reloction backref cache require more info for reloc root compared 33470535441SQu Wenruo * to generic backref cache. 33570535441SQu Wenruo */ 33670535441SQu Wenruo unsigned int is_reloc; 33770535441SQu Wenruo }; 33870535441SQu Wenruo 339584fb121SQu Wenruo void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info, 340584fb121SQu Wenruo struct btrfs_backref_cache *cache, int is_reloc); 341b1818dabSQu Wenruo struct btrfs_backref_node *btrfs_backref_alloc_node( 342b1818dabSQu Wenruo struct btrfs_backref_cache *cache, u64 bytenr, int level); 34347254d07SQu Wenruo struct btrfs_backref_edge *btrfs_backref_alloc_edge( 34447254d07SQu Wenruo struct btrfs_backref_cache *cache); 345584fb121SQu Wenruo 346f39911e5SQu Wenruo #define LINK_LOWER (1 << 0) 347f39911e5SQu Wenruo #define LINK_UPPER (1 << 1) 348f39911e5SQu Wenruo static inline void btrfs_backref_link_edge(struct btrfs_backref_edge *edge, 349f39911e5SQu Wenruo struct btrfs_backref_node *lower, 350f39911e5SQu Wenruo struct btrfs_backref_node *upper, 351f39911e5SQu Wenruo int link_which) 352f39911e5SQu Wenruo { 353f39911e5SQu Wenruo ASSERT(upper && lower && upper->level == lower->level + 1); 354f39911e5SQu Wenruo edge->node[LOWER] = lower; 355f39911e5SQu Wenruo edge->node[UPPER] = upper; 356f39911e5SQu Wenruo if (link_which & LINK_LOWER) 357f39911e5SQu Wenruo list_add_tail(&edge->list[LOWER], &lower->upper); 358f39911e5SQu Wenruo if (link_which & LINK_UPPER) 359f39911e5SQu Wenruo list_add_tail(&edge->list[UPPER], &upper->lower); 360f39911e5SQu Wenruo } 361f39911e5SQu Wenruo 362741188d3SQu Wenruo static inline void btrfs_backref_free_node(struct btrfs_backref_cache *cache, 363741188d3SQu Wenruo struct btrfs_backref_node *node) 364741188d3SQu Wenruo { 365741188d3SQu Wenruo if (node) { 366eddda68dSJosef Bacik ASSERT(list_empty(&node->list)); 367eddda68dSJosef Bacik ASSERT(list_empty(&node->lower)); 368eddda68dSJosef Bacik ASSERT(node->eb == NULL); 369741188d3SQu Wenruo cache->nr_nodes--; 370741188d3SQu Wenruo btrfs_put_root(node->root); 371741188d3SQu Wenruo kfree(node); 372741188d3SQu Wenruo } 373741188d3SQu Wenruo } 374741188d3SQu Wenruo 375741188d3SQu Wenruo static inline void btrfs_backref_free_edge(struct btrfs_backref_cache *cache, 376741188d3SQu Wenruo struct btrfs_backref_edge *edge) 377741188d3SQu Wenruo { 378741188d3SQu Wenruo if (edge) { 379741188d3SQu Wenruo cache->nr_edges--; 380741188d3SQu Wenruo kfree(edge); 381741188d3SQu Wenruo } 382741188d3SQu Wenruo } 383741188d3SQu Wenruo 384b0fe7078SQu Wenruo static inline void btrfs_backref_unlock_node_buffer( 385b0fe7078SQu Wenruo struct btrfs_backref_node *node) 386b0fe7078SQu Wenruo { 387b0fe7078SQu Wenruo if (node->locked) { 388b0fe7078SQu Wenruo btrfs_tree_unlock(node->eb); 389b0fe7078SQu Wenruo node->locked = 0; 390b0fe7078SQu Wenruo } 391b0fe7078SQu Wenruo } 392b0fe7078SQu Wenruo 393b0fe7078SQu Wenruo static inline void btrfs_backref_drop_node_buffer( 394b0fe7078SQu Wenruo struct btrfs_backref_node *node) 395b0fe7078SQu Wenruo { 396b0fe7078SQu Wenruo if (node->eb) { 397b0fe7078SQu Wenruo btrfs_backref_unlock_node_buffer(node); 398b0fe7078SQu Wenruo free_extent_buffer(node->eb); 399b0fe7078SQu Wenruo node->eb = NULL; 400b0fe7078SQu Wenruo } 401b0fe7078SQu Wenruo } 402b0fe7078SQu Wenruo 403b0fe7078SQu Wenruo /* 404b0fe7078SQu Wenruo * Drop the backref node from cache without cleaning up its children 405b0fe7078SQu Wenruo * edges. 406b0fe7078SQu Wenruo * 407b0fe7078SQu Wenruo * This can only be called on node without parent edges. 408b0fe7078SQu Wenruo * The children edges are still kept as is. 409b0fe7078SQu Wenruo */ 410b0fe7078SQu Wenruo static inline void btrfs_backref_drop_node(struct btrfs_backref_cache *tree, 411b0fe7078SQu Wenruo struct btrfs_backref_node *node) 412b0fe7078SQu Wenruo { 413eddda68dSJosef Bacik ASSERT(list_empty(&node->upper)); 414b0fe7078SQu Wenruo 415b0fe7078SQu Wenruo btrfs_backref_drop_node_buffer(node); 416eddda68dSJosef Bacik list_del_init(&node->list); 417eddda68dSJosef Bacik list_del_init(&node->lower); 418b0fe7078SQu Wenruo if (!RB_EMPTY_NODE(&node->rb_node)) 419b0fe7078SQu Wenruo rb_erase(&node->rb_node, &tree->rb_root); 420b0fe7078SQu Wenruo btrfs_backref_free_node(tree, node); 421b0fe7078SQu Wenruo } 422b0fe7078SQu Wenruo 423023acb07SQu Wenruo void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache, 424023acb07SQu Wenruo struct btrfs_backref_node *node); 425023acb07SQu Wenruo 42613fe1bdbSQu Wenruo void btrfs_backref_release_cache(struct btrfs_backref_cache *cache); 42713fe1bdbSQu Wenruo 428982c92cbSQu Wenruo static inline void btrfs_backref_panic(struct btrfs_fs_info *fs_info, 429982c92cbSQu Wenruo u64 bytenr, int errno) 430982c92cbSQu Wenruo { 431982c92cbSQu Wenruo btrfs_panic(fs_info, errno, 432982c92cbSQu Wenruo "Inconsistency in backref cache found at offset %llu", 433982c92cbSQu Wenruo bytenr); 434982c92cbSQu Wenruo } 435982c92cbSQu Wenruo 4361b60d2ecSQu Wenruo int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache, 4371b60d2ecSQu Wenruo struct btrfs_path *path, 4381b60d2ecSQu Wenruo struct btrfs_backref_iter *iter, 4391b60d2ecSQu Wenruo struct btrfs_key *node_key, 4401b60d2ecSQu Wenruo struct btrfs_backref_node *cur); 4411b60d2ecSQu Wenruo 442fc997ed0SQu Wenruo int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache, 443fc997ed0SQu Wenruo struct btrfs_backref_node *start); 444fc997ed0SQu Wenruo 4451b23ea18SQu Wenruo void btrfs_backref_error_cleanup(struct btrfs_backref_cache *cache, 4461b23ea18SQu Wenruo struct btrfs_backref_node *node); 4471b23ea18SQu Wenruo 448a542ad1bSJan Schmidt #endif 449