backref.c (1b60d2ec982a35c2953d81d035e1d7fc7c89f42a) backref.c (fc997ed05a9f9d2185b8804fb2d0273e6d9e921a)
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2011 STRATO. All rights reserved.
4 */
5
6#include <linux/mm.h>
7#include <linux/rbtree.h>
8#include <trace/events/btrfs.h>

--- 2816 unchanged lines hidden (view full) ---

2825 return ret;
2826}
2827
2828/*
2829 * Add backref node @cur into @cache.
2830 *
2831 * NOTE: Even if the function returned 0, @cur is not yet cached as its upper
2832 * links aren't yet bi-directional. Needs to finish such links.
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2011 STRATO. All rights reserved.
4 */
5
6#include <linux/mm.h>
7#include <linux/rbtree.h>
8#include <trace/events/btrfs.h>

--- 2816 unchanged lines hidden (view full) ---

2825 return ret;
2826}
2827
2828/*
2829 * Add backref node @cur into @cache.
2830 *
2831 * NOTE: Even if the function returned 0, @cur is not yet cached as its upper
2832 * links aren't yet bi-directional. Needs to finish such links.
2833 * Use btrfs_backref_finish_upper_links() to finish such linkage.
2833 *
2834 * @path: Released path for indirect tree backref lookup
2835 * @iter: Released backref iter for extent tree search
2836 * @node_key: The first key of the tree block
2837 */
2838int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,
2839 struct btrfs_path *path,
2840 struct btrfs_backref_iter *iter,

--- 111 unchanged lines hidden (view full) ---

2952 }
2953 ret = 0;
2954 cur->checked = 1;
2955 WARN_ON(exist);
2956out:
2957 btrfs_backref_iter_release(iter);
2958 return ret;
2959}
2834 *
2835 * @path: Released path for indirect tree backref lookup
2836 * @iter: Released backref iter for extent tree search
2837 * @node_key: The first key of the tree block
2838 */
2839int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,
2840 struct btrfs_path *path,
2841 struct btrfs_backref_iter *iter,

--- 111 unchanged lines hidden (view full) ---

2953 }
2954 ret = 0;
2955 cur->checked = 1;
2956 WARN_ON(exist);
2957out:
2958 btrfs_backref_iter_release(iter);
2959 return ret;
2960}
2961
2962/*
2963 * Finish the upwards linkage created by btrfs_backref_add_tree_node()
2964 */
2965int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
2966 struct btrfs_backref_node *start)
2967{
2968 struct list_head *useless_node = &cache->useless_node;
2969 struct btrfs_backref_edge *edge;
2970 struct rb_node *rb_node;
2971 LIST_HEAD(pending_edge);
2972
2973 ASSERT(start->checked);
2974
2975 /* Insert this node to cache if it's not COW-only */
2976 if (!start->cowonly) {
2977 rb_node = rb_simple_insert(&cache->rb_root, start->bytenr,
2978 &start->rb_node);
2979 if (rb_node)
2980 btrfs_backref_panic(cache->fs_info, start->bytenr,
2981 -EEXIST);
2982 list_add_tail(&start->lower, &cache->leaves);
2983 }
2984
2985 /*
2986 * Use breadth first search to iterate all related edges.
2987 *
2988 * The starting points are all the edges of this node
2989 */
2990 list_for_each_entry(edge, &start->upper, list[LOWER])
2991 list_add_tail(&edge->list[UPPER], &pending_edge);
2992
2993 while (!list_empty(&pending_edge)) {
2994 struct btrfs_backref_node *upper;
2995 struct btrfs_backref_node *lower;
2996 struct rb_node *rb_node;
2997
2998 edge = list_first_entry(&pending_edge,
2999 struct btrfs_backref_edge, list[UPPER]);
3000 list_del_init(&edge->list[UPPER]);
3001 upper = edge->node[UPPER];
3002 lower = edge->node[LOWER];
3003
3004 /* Parent is detached, no need to keep any edges */
3005 if (upper->detached) {
3006 list_del(&edge->list[LOWER]);
3007 btrfs_backref_free_edge(cache, edge);
3008
3009 /* Lower node is orphan, queue for cleanup */
3010 if (list_empty(&lower->upper))
3011 list_add(&lower->list, useless_node);
3012 continue;
3013 }
3014
3015 /*
3016 * All new nodes added in current build_backref_tree() haven't
3017 * been linked to the cache rb tree.
3018 * So if we have upper->rb_node populated, this means a cache
3019 * hit. We only need to link the edge, as @upper and all its
3020 * parents have already been linked.
3021 */
3022 if (!RB_EMPTY_NODE(&upper->rb_node)) {
3023 if (upper->lowest) {
3024 list_del_init(&upper->lower);
3025 upper->lowest = 0;
3026 }
3027
3028 list_add_tail(&edge->list[UPPER], &upper->lower);
3029 continue;
3030 }
3031
3032 /* Sanity check, we shouldn't have any unchecked nodes */
3033 if (!upper->checked) {
3034 ASSERT(0);
3035 return -EUCLEAN;
3036 }
3037
3038 /* Sanity check, COW-only node has non-COW-only parent */
3039 if (start->cowonly != upper->cowonly) {
3040 ASSERT(0);
3041 return -EUCLEAN;
3042 }
3043
3044 /* Only cache non-COW-only (subvolume trees) tree blocks */
3045 if (!upper->cowonly) {
3046 rb_node = rb_simple_insert(&cache->rb_root, upper->bytenr,
3047 &upper->rb_node);
3048 if (rb_node) {
3049 btrfs_backref_panic(cache->fs_info,
3050 upper->bytenr, -EEXIST);
3051 return -EUCLEAN;
3052 }
3053 }
3054
3055 list_add_tail(&edge->list[UPPER], &upper->lower);
3056
3057 /*
3058 * Also queue all the parent edges of this uncached node
3059 * to finish the upper linkage
3060 */
3061 list_for_each_entry(edge, &upper->upper, list[LOWER])
3062 list_add_tail(&edge->list[UPPER], &pending_edge);
3063 }
3064 return 0;
3065}