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