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