1 #ifndef _BCACHEFS_BTREE_ITER_H
2 #define _BCACHEFS_BTREE_ITER_H
4 #include <linux/dynamic_fault.h>
6 #include "btree_types.h"
8 static inline void btree_iter_set_dirty(struct btree_iter *iter,
9 enum btree_iter_uptodate u)
11 iter->uptodate = max_t(unsigned, iter->uptodate, u);
14 static inline struct btree *btree_iter_node(struct btree_iter *iter,
17 return level < BTREE_MAX_DEPTH ? iter->l[level].b : NULL;
20 static inline struct btree *btree_node_parent(struct btree_iter *iter,
23 return btree_iter_node(iter, b->level + 1);
26 static inline bool btree_iter_linked(const struct btree_iter *iter)
28 return iter->next != iter;
31 static inline bool __iter_has_node(const struct btree_iter *iter,
32 const struct btree *b)
35 * We don't compare the low bits of the lock sequence numbers because
36 * @iter might have taken a write lock on @b, and we don't want to skip
37 * the linked iterator if the sequence numbers were equal before taking
38 * that write lock. The lock sequence number is incremented by taking
39 * and releasing write locks and is even when unlocked:
42 return iter->l[b->level].b == b &&
43 iter->lock_seq[b->level] >> 1 == b->lock.state.seq >> 1;
46 static inline struct btree_iter *
47 __next_linked_iter(struct btree_iter *iter, struct btree_iter *linked)
49 return linked->next != iter ? linked->next : NULL;
52 static inline struct btree_iter *
53 __next_iter_with_node(struct btree_iter *iter, struct btree *b,
54 struct btree_iter *linked)
56 while (linked && !__iter_has_node(linked, b))
57 linked = __next_linked_iter(iter, linked);
63 * for_each_btree_iter - iterate over all iterators linked with @_iter,
66 #define for_each_btree_iter(_iter, _linked) \
67 for ((_linked) = (_iter); (_linked); \
68 (_linked) = __next_linked_iter(_iter, _linked))
71 * for_each_btree_iter_with_node - iterate over all iterators linked with @_iter
72 * that also point to @_b
74 * @_b is assumed to be locked by @_iter
76 * Filters out iterators that don't have a valid btree_node iterator for @_b -
77 * i.e. iterators for which bch2_btree_node_relock() would not succeed.
79 #define for_each_btree_iter_with_node(_iter, _b, _linked) \
80 for ((_linked) = (_iter); \
81 ((_linked) = __next_iter_with_node(_iter, _b, _linked)); \
82 (_linked) = __next_linked_iter(_iter, _linked))
85 * for_each_linked_btree_iter - iterate over all iterators linked with @_iter,
86 * _not_ including @_iter
88 #define for_each_linked_btree_iter(_iter, _linked) \
89 for ((_linked) = (_iter)->next; \
90 (_linked) != (_iter); \
91 (_linked) = (_linked)->next)
93 #ifdef CONFIG_BCACHEFS_DEBUG
94 void bch2_btree_iter_verify(struct btree_iter *, struct btree *);
95 void bch2_btree_iter_verify_locks(struct btree_iter *);
97 static inline void bch2_btree_iter_verify(struct btree_iter *iter,
99 static inline void bch2_btree_iter_verify_locks(struct btree_iter *iter) {}
102 void bch2_btree_node_iter_fix(struct btree_iter *, struct btree *,
103 struct btree_node_iter *, struct bset_tree *,
104 struct bkey_packed *, unsigned, unsigned);
106 int bch2_btree_iter_unlock(struct btree_iter *);
108 bool __bch2_btree_iter_upgrade(struct btree_iter *, unsigned);
109 bool __bch2_btree_iter_upgrade_nounlock(struct btree_iter *, unsigned);
111 static inline bool bch2_btree_iter_upgrade(struct btree_iter *iter,
112 unsigned new_locks_want,
115 new_locks_want = min(new_locks_want, BTREE_MAX_DEPTH);
117 return iter->locks_want < new_locks_want
119 ? __bch2_btree_iter_upgrade(iter, new_locks_want)
120 : __bch2_btree_iter_upgrade_nounlock(iter, new_locks_want))
121 : iter->uptodate <= BTREE_ITER_NEED_PEEK;
124 void __bch2_btree_iter_downgrade(struct btree_iter *, unsigned);
126 static inline void bch2_btree_iter_downgrade(struct btree_iter *iter)
128 if (iter->locks_want > (iter->flags & BTREE_ITER_INTENT) ? 1 : 0)
129 __bch2_btree_iter_downgrade(iter, 0);
132 void bch2_btree_iter_node_replace(struct btree_iter *, struct btree *);
133 void bch2_btree_iter_node_drop(struct btree_iter *, struct btree *);
135 void bch2_btree_iter_reinit_node(struct btree_iter *, struct btree *);
137 int __must_check bch2_btree_iter_traverse(struct btree_iter *);
139 struct btree *bch2_btree_iter_peek_node(struct btree_iter *);
140 struct btree *bch2_btree_iter_next_node(struct btree_iter *, unsigned);
142 struct bkey_s_c bch2_btree_iter_peek(struct btree_iter *);
143 struct bkey_s_c bch2_btree_iter_next(struct btree_iter *);
144 struct bkey_s_c bch2_btree_iter_prev(struct btree_iter *);
146 struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *);
147 struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *);
149 void bch2_btree_iter_set_pos_same_leaf(struct btree_iter *, struct bpos);
150 void bch2_btree_iter_set_pos(struct btree_iter *, struct bpos);
152 void __bch2_btree_iter_init(struct btree_iter *, struct bch_fs *,
153 enum btree_id, struct bpos,
154 unsigned , unsigned, unsigned);
156 static inline void bch2_btree_iter_init(struct btree_iter *iter,
157 struct bch_fs *c, enum btree_id btree_id,
158 struct bpos pos, unsigned flags)
160 __bch2_btree_iter_init(iter, c, btree_id, pos,
161 flags & BTREE_ITER_INTENT ? 1 : 0, 0,
162 (btree_id == BTREE_ID_EXTENTS
163 ? BTREE_ITER_IS_EXTENTS : 0)|flags);
166 void bch2_btree_iter_link(struct btree_iter *, struct btree_iter *);
167 void bch2_btree_iter_unlink(struct btree_iter *);
168 void bch2_btree_iter_copy(struct btree_iter *, struct btree_iter *);
170 static inline struct bpos btree_type_successor(enum btree_id id,
173 if (id == BTREE_ID_INODES) {
176 } else if (id != BTREE_ID_EXTENTS) {
177 pos = bkey_successor(pos);
183 static inline struct bpos btree_type_predecessor(enum btree_id id,
186 if (id == BTREE_ID_INODES) {
189 } else /* if (id != BTREE_ID_EXTENTS) */ {
190 pos = bkey_predecessor(pos);
196 static inline int __btree_iter_cmp(enum btree_id id,
198 const struct btree_iter *r)
200 if (id != r->btree_id)
201 return id < r->btree_id ? -1 : 1;
202 return bkey_cmp(pos, r->pos);
205 static inline int btree_iter_cmp(const struct btree_iter *l,
206 const struct btree_iter *r)
208 return __btree_iter_cmp(l->btree_id, l->pos, r);
212 * Unlocks before scheduling
213 * Note: does not revalidate iterator
215 static inline void bch2_btree_iter_cond_resched(struct btree_iter *iter)
217 if (need_resched()) {
218 bch2_btree_iter_unlock(iter);
220 } else if (race_fault()) {
221 bch2_btree_iter_unlock(iter);
225 #define __for_each_btree_node(_iter, _c, _btree_id, _start, \
226 _locks_want, _depth, _flags, _b) \
227 for (__bch2_btree_iter_init((_iter), (_c), (_btree_id), _start, \
228 _locks_want, _depth, \
229 _flags|BTREE_ITER_NODES), \
230 _b = bch2_btree_iter_peek_node(_iter); \
232 (_b) = bch2_btree_iter_next_node(_iter, _depth))
234 #define for_each_btree_node(_iter, _c, _btree_id, _start, _flags, _b) \
235 __for_each_btree_node(_iter, _c, _btree_id, _start, 0, 0, _flags, _b)
237 static inline struct bkey_s_c __bch2_btree_iter_peek(struct btree_iter *iter,
240 return flags & BTREE_ITER_SLOTS
241 ? bch2_btree_iter_peek_slot(iter)
242 : bch2_btree_iter_peek(iter);
245 static inline struct bkey_s_c __bch2_btree_iter_next(struct btree_iter *iter,
248 bch2_btree_iter_cond_resched(iter);
250 return flags & BTREE_ITER_SLOTS
251 ? bch2_btree_iter_next_slot(iter)
252 : bch2_btree_iter_next(iter);
255 #define for_each_btree_key(_iter, _c, _btree_id, _start, _flags, _k) \
256 for (bch2_btree_iter_init((_iter), (_c), (_btree_id), \
257 (_start), (_flags)), \
258 (_k) = __bch2_btree_iter_peek(_iter, _flags); \
259 !IS_ERR_OR_NULL((_k).k); \
260 (_k) = __bch2_btree_iter_next(_iter, _flags))
262 #define for_each_btree_key_continue(_iter, _flags, _k) \
263 for ((_k) = __bch2_btree_iter_peek(_iter, _flags); \
264 !IS_ERR_OR_NULL((_k).k); \
265 (_k) = __bch2_btree_iter_next(_iter, _flags))
267 static inline int btree_iter_err(struct bkey_s_c k)
269 return PTR_ERR_OR_ZERO(k.k);
272 #endif /* _BCACHEFS_BTREE_ITER_H */