From 068bcaa589e268fe0bca1f972b3a08a18be8c5dc Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Fri, 3 Sep 2021 17:18:57 -0400 Subject: [PATCH] bcachefs: Add more assertions for locking btree iterators out of order btree_path_traverse_all() traverses btree iterators in sorted order, and thus shouldn't see transaction restarts due to potential deadlocks - but sometimes we do. This patch adds some more assertions and tracks some more state to help track this down. Signed-off-by: Kent Overstreet --- fs/bcachefs/btree_iter.c | 50 ++++++++++++++++------------------- fs/bcachefs/btree_iter.h | 10 +++++++ fs/bcachefs/btree_key_cache.c | 4 +-- fs/bcachefs/btree_locking.h | 18 ++++++++++--- fs/bcachefs/btree_types.h | 2 ++ 5 files changed, 52 insertions(+), 32 deletions(-) diff --git a/fs/bcachefs/btree_iter.c b/fs/bcachefs/btree_iter.c index a856f5e907273..edb4084f7b909 100644 --- a/fs/bcachefs/btree_iter.c +++ b/fs/bcachefs/btree_iter.c @@ -17,8 +17,6 @@ #include -static inline void btree_trans_sort_paths(struct btree_trans *); - static inline void btree_path_list_remove(struct btree_trans *, struct btree_path *); static inline void btree_path_list_add(struct btree_trans *, struct btree_path *, struct btree_path *); @@ -159,7 +157,7 @@ bool __bch2_btree_node_relock(struct btree_trans *trans, if (six_relock_type(&b->c.lock, want, path->l[level].lock_seq) || (btree_node_lock_seq_matches(path, b, level) && btree_node_lock_increment(trans, b, level, want))) { - mark_btree_node_locked(path, level, want); + mark_btree_node_locked(trans, path, level, want); return true; } else { return false; @@ -195,7 +193,7 @@ static bool bch2_btree_node_upgrade(struct btree_trans *trans, return false; success: - mark_btree_node_intent_locked(path, level); + mark_btree_node_intent_locked(trans, path, level); return true; } @@ -1078,7 +1076,7 @@ void bch2_trans_node_add(struct btree_trans *trans, struct btree *b) t = btree_lock_want(path, b->c.level); if (t != BTREE_NODE_UNLOCKED) { six_lock_increment(&b->c.lock, (enum six_lock_type) t); - mark_btree_node_locked(path, b->c.level, (enum six_lock_type) t); + mark_btree_node_locked(trans, path, b->c.level, (enum six_lock_type) t); } btree_path_level_init(trans, path, b); @@ -1167,7 +1165,7 @@ static inline int btree_path_lock_root(struct btree_trans *trans, for (i = path->level + 1; i < BTREE_MAX_DEPTH; i++) path->l[i].b = NULL; - mark_btree_node_locked(path, path->level, lock_type); + mark_btree_node_locked(trans, path, path->level, lock_type); btree_path_level_init(trans, path, b); return 0; } @@ -1259,7 +1257,7 @@ static __always_inline int btree_path_down(struct btree_trans *trans, if (unlikely(ret)) goto err; - mark_btree_node_locked(path, level, lock_type); + mark_btree_node_locked(trans, path, level, lock_type); btree_path_level_init(trans, path, b); if (tmp.k->k.type == KEY_TYPE_btree_ptr_v2 && @@ -1340,6 +1338,9 @@ retry_all: path = trans->paths + trans->sorted[i]; EBUG_ON(!(trans->paths_allocated & (1ULL << path->idx))); +#ifdef CONFIG_BCACHEFS_DEBUG + trans->traverse_all_idx = path->idx; +#endif ret = btree_path_traverse_one(trans, path, 0, _THIS_IP_); if (ret) @@ -1361,6 +1362,9 @@ retry_all: out: bch2_btree_cache_cannibalize_unlock(c); +#ifdef CONFIG_BCACHEFS_DEBUG + trans->traverse_all_idx = U8_MAX; +#endif trans->in_traverse_all = false; trace_trans_traverse_all(trans->ip, trace_ip); @@ -2319,13 +2323,9 @@ static void btree_trans_verify_sorted_refs(struct btree_trans *trans) BUG_ON(trans->paths[idx].sorted_idx != i); } } -#else -static inline void btree_trans_verify_sorted_refs(struct btree_trans *trans) {} -#endif static void btree_trans_verify_sorted(struct btree_trans *trans) { -#ifdef CONFIG_BCACHEFS_DEBUG struct btree_path *path, *prev = NULL; unsigned i; @@ -2333,14 +2333,22 @@ static void btree_trans_verify_sorted(struct btree_trans *trans) BUG_ON(prev && btree_path_cmp(prev, path) > 0); prev = path; } -#endif } +#else +static inline void btree_trans_verify_sorted_refs(struct btree_trans *trans) {} +static inline void btree_trans_verify_sorted(struct btree_trans *trans) {} +#endif -static noinline void __btree_trans_sort_paths(struct btree_trans *trans) +void __bch2_btree_trans_sort_paths(struct btree_trans *trans) { int i, l = 0, r = trans->nr_sorted, inc = 1; bool swapped; + btree_trans_verify_sorted_refs(trans); + + if (trans->paths_sorted) + goto out; + /* * Cocktail shaker sort: this is efficient because iterators will be * mostly sorteda. @@ -2368,22 +2376,10 @@ static noinline void __btree_trans_sort_paths(struct btree_trans *trans) } while (swapped); trans->paths_sorted = true; - +out: btree_trans_verify_sorted(trans); } -static inline void btree_trans_sort_paths(struct btree_trans *trans) -{ - btree_trans_verify_sorted_refs(trans); - - if (trans->paths_sorted) { - if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) - btree_trans_verify_sorted(trans); - return; - } - __btree_trans_sort_paths(trans); -} - static inline void btree_path_list_remove(struct btree_trans *trans, struct btree_path *path) { @@ -2410,7 +2406,7 @@ static inline void btree_path_list_add(struct btree_trans *trans, { unsigned i; - path->sorted_idx = pos ? pos->sorted_idx + 1 : 0; + path->sorted_idx = pos ? pos->sorted_idx + 1 : trans->nr_sorted; #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS memmove_u64s_up_small(trans->sorted + path->sorted_idx + 1, diff --git a/fs/bcachefs/btree_iter.h b/fs/bcachefs/btree_iter.h index 983d611224580..19ce6a6ece7d5 100644 --- a/fs/bcachefs/btree_iter.h +++ b/fs/bcachefs/btree_iter.h @@ -57,6 +57,16 @@ static inline int btree_iter_err(const struct btree_iter *iter) /* Iterate over paths within a transaction: */ +void __bch2_btree_trans_sort_paths(struct btree_trans *); + +static inline void btree_trans_sort_paths(struct btree_trans *trans) +{ + if (!IS_ENABLED(CONFIG_BCACHEFS_DEBUG) && + trans->paths_sorted) + return; + __bch2_btree_trans_sort_paths(trans); +} + static inline struct btree_path * __trans_next_path(struct btree_trans *trans, unsigned idx) { diff --git a/fs/bcachefs/btree_key_cache.c b/fs/bcachefs/btree_key_cache.c index 9bdc2c3f21bf4..9d3a64f37f09a 100644 --- a/fs/bcachefs/btree_key_cache.c +++ b/fs/bcachefs/btree_key_cache.c @@ -297,7 +297,7 @@ retry: if (!ck) goto retry; - mark_btree_node_locked(path, 0, SIX_LOCK_intent); + mark_btree_node_locked(trans, path, 0, SIX_LOCK_intent); path->locks_want = 1; } else { enum six_lock_type lock_want = __btree_lock_want(path, 0); @@ -319,7 +319,7 @@ retry: goto retry; } - mark_btree_node_locked(path, 0, lock_want); + mark_btree_node_locked(trans, path, 0, lock_want); } path->l[0].lock_seq = ck->c.lock.state.seq; diff --git a/fs/bcachefs/btree_locking.h b/fs/bcachefs/btree_locking.h index d05689180c63e..ff58870311f35 100644 --- a/fs/bcachefs/btree_locking.h +++ b/fs/bcachefs/btree_locking.h @@ -57,7 +57,8 @@ static inline void mark_btree_node_unlocked(struct btree_path *path, path->nodes_intent_locked &= ~(1 << level); } -static inline void mark_btree_node_locked(struct btree_path *path, +static inline void mark_btree_node_locked(struct btree_trans *trans, + struct btree_path *path, unsigned level, enum six_lock_type type) { @@ -67,12 +68,20 @@ static inline void mark_btree_node_locked(struct btree_path *path, path->nodes_locked |= 1 << level; path->nodes_intent_locked |= type << level; +#ifdef CONFIG_BCACHEFS_DEBUG + path->ip_locked = _RET_IP_; + btree_trans_sort_paths(trans); + BUG_ON(trans->in_traverse_all && + trans->traverse_all_idx != U8_MAX && + path->sorted_idx > trans->paths[trans->traverse_all_idx].sorted_idx); +#endif } -static inline void mark_btree_node_intent_locked(struct btree_path *path, +static inline void mark_btree_node_intent_locked(struct btree_trans *trans, + struct btree_path *path, unsigned level) { - mark_btree_node_locked(path, level, SIX_LOCK_intent); + mark_btree_node_locked(trans, path, level, SIX_LOCK_intent); } static inline enum six_lock_type __btree_lock_want(struct btree_path *path, int level) @@ -111,6 +120,9 @@ static inline void __bch2_btree_path_unlock(struct btree_path *path) while (path->nodes_locked) btree_node_unlock(path, __ffs(path->nodes_locked)); +#ifdef CONFIG_BCACHEFS_DEBUG + path->ip_locked = 0; +#endif } static inline enum bch_time_stats lock_to_time_stat(enum six_lock_type type) diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h index b7cded2095fff..ce64d3ad768bb 100644 --- a/fs/bcachefs/btree_types.h +++ b/fs/bcachefs/btree_types.h @@ -255,6 +255,7 @@ struct btree_path { } l[BTREE_MAX_DEPTH]; #ifdef CONFIG_BCACHEFS_DEBUG unsigned long ip_allocated; + unsigned long ip_locked; #endif }; @@ -368,6 +369,7 @@ struct btree_trans { struct bpos locking_pos; u8 locking_btree_id; u8 locking_level; + u8 traverse_all_idx; pid_t pid; #endif unsigned long ip; -- 2.30.2