backref.h 10 KB

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