diff options
author | Kent Overstreet <kent.overstreet@gmail.com> | 2016-07-21 19:05:06 -0800 |
---|---|---|
committer | Kent Overstreet <kent.overstreet@linux.dev> | 2023-10-22 17:08:09 -0400 |
commit | 271a3d3a4b30dcd9fd274a923fb382f5f113d279 (patch) | |
tree | b16887dfafd9b011a14ae842f1029ce1211c9aa5 /fs/bcachefs/bset.h | |
parent | 0fdf18047fd38e7b5cc6adba3a81704c88333e1c (diff) | |
download | linux-stable-271a3d3a4b30dcd9fd274a923fb382f5f113d279.tar.gz linux-stable-271a3d3a4b30dcd9fd274a923fb382f5f113d279.tar.bz2 linux-stable-271a3d3a4b30dcd9fd274a923fb382f5f113d279.zip |
bcachefs: lift ordering restriction on 0 size extents
This lifts the restriction that 0 size extents must not overlap with
other extents, which means we can now sort extents and non extents the
same way, and will let us simplify a bunch of other stuff as well.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Diffstat (limited to 'fs/bcachefs/bset.h')
-rw-r--r-- | fs/bcachefs/bset.h | 68 |
1 files changed, 29 insertions, 39 deletions
diff --git a/fs/bcachefs/bset.h b/fs/bcachefs/bset.h index 2fa71d7c0e8a..0787030ccc7e 100644 --- a/fs/bcachefs/bset.h +++ b/fs/bcachefs/bset.h @@ -370,6 +370,17 @@ static inline int bkey_cmp_p_or_unp(const struct btree *b, } /* Returns true if @k is after iterator position @pos */ +static inline bool btree_iter_pos_cmp(struct btree_iter *iter, + const struct bkey *k) +{ + int cmp = bkey_cmp(k->p, iter->pos); + + return cmp > 0 || + (cmp == 0 && + !(iter->flags & BTREE_ITER_IS_EXTENTS) && !bkey_deleted(k)); +} + +/* Returns true if @k is after iterator position @pos */ static inline bool btree_iter_pos_cmp_packed(const struct btree *b, struct bpos *pos, const struct bkey_packed *k, @@ -419,7 +430,7 @@ enum bch_extent_overlap { /* Returns how k overlaps with m */ static inline enum bch_extent_overlap bch2_extent_overlap(const struct bkey *k, - const struct bkey *m) + const struct bkey *m) { int cmp1 = bkey_cmp(k->p, m->p) < 0; int cmp2 = bkey_cmp(bkey_start_pos(k), @@ -430,20 +441,13 @@ static inline enum bch_extent_overlap bch2_extent_overlap(const struct bkey *k, /* Btree key iteration */ -static inline void __bch2_btree_node_iter_init(struct btree_node_iter *iter, - bool is_extents) -{ - iter->is_extents = is_extents; - memset(iter->data, 0, sizeof(iter->data)); -} - void bch2_btree_node_iter_push(struct btree_node_iter *, struct btree *, const struct bkey_packed *, const struct bkey_packed *); void bch2_btree_node_iter_init(struct btree_node_iter *, struct btree *, - struct bpos, bool, bool); + struct bpos, bool); void bch2_btree_node_iter_init_from_start(struct btree_node_iter *, - struct btree *, bool); + struct btree *); struct bkey_packed *bch2_btree_node_iter_bset_pos(struct btree_node_iter *, struct btree *, struct bset_tree *); @@ -470,32 +474,21 @@ static inline bool bch2_btree_node_iter_end(struct btree_node_iter *iter) return __btree_node_iter_set_end(iter, 0); } -static inline int __btree_node_iter_cmp(bool is_extents, - struct btree *b, - struct bkey_packed *l, - struct bkey_packed *r) +static inline int __btree_node_iter_cmp(struct btree *b, + const struct bkey_packed *l, + const struct bkey_packed *r) { - /* - * For non extents, when keys compare equal the deleted keys have to - * come first - so that bch2_btree_node_iter_next_check() can detect - * duplicate nondeleted keys (and possibly other reasons?) - * - * For extents, bkey_deleted() is used as a proxy for k->size == 0, so - * deleted keys have to sort last. - */ + /* When keys compare equal deleted keys come first */ return bkey_cmp_packed(b, l, r) - ?: (is_extents - ? (int) bkey_deleted(l) - (int) bkey_deleted(r) - : (int) bkey_deleted(r) - (int) bkey_deleted(l)) + ?: (int) bkey_deleted(r) - (int) bkey_deleted(l) ?: (l > r) - (l < r); } -static inline int btree_node_iter_cmp(struct btree_node_iter *iter, - struct btree *b, +static inline int btree_node_iter_cmp(struct btree *b, struct btree_node_iter_set l, struct btree_node_iter_set r) { - return __btree_node_iter_cmp(iter->is_extents, b, + return __btree_node_iter_cmp(b, __btree_node_offset_to_key(b, l.k), __btree_node_offset_to_key(b, r.k)); } @@ -582,21 +575,12 @@ bch2_btree_node_iter_prev(struct btree_node_iter *iter, struct btree *b) return bch2_btree_node_iter_prev_filter(iter, b, KEY_TYPE_DISCARD + 1); } -/* - * Iterates over all _live_ keys - skipping deleted (and potentially - * overlapping) keys - */ -#define for_each_btree_node_key(b, k, iter, _is_extents) \ - for (bch2_btree_node_iter_init_from_start((iter), (b), (_is_extents));\ - ((k) = bch2_btree_node_iter_peek(iter, b)); \ - bch2_btree_node_iter_advance(iter, b)) - struct bkey_s_c bch2_btree_node_iter_peek_unpack(struct btree_node_iter *, struct btree *, struct bkey *); -#define for_each_btree_node_key_unpack(b, k, iter, _is_extents, unpacked)\ - for (bch2_btree_node_iter_init_from_start((iter), (b), (_is_extents));\ +#define for_each_btree_node_key_unpack(b, k, iter, unpacked) \ + for (bch2_btree_node_iter_init_from_start((iter), (b)); \ (k = bch2_btree_node_iter_peek_unpack((iter), (b), (unpacked))).k;\ bch2_btree_node_iter_advance(iter, b)) @@ -646,6 +630,8 @@ void bch2_dump_btree_node_iter(struct btree *, struct btree_node_iter *); void __bch2_verify_btree_nr_keys(struct btree *); void bch2_btree_node_iter_verify(struct btree_node_iter *, struct btree *); +void bch2_verify_insert_pos(struct btree *, struct bkey_packed *, + struct bkey_packed *, unsigned); void bch2_verify_key_order(struct btree *, struct btree_node_iter *, struct bkey_packed *); @@ -654,6 +640,10 @@ void bch2_verify_key_order(struct btree *, struct btree_node_iter *, static inline void __bch2_verify_btree_nr_keys(struct btree *b) {} static inline void bch2_btree_node_iter_verify(struct btree_node_iter *iter, struct btree *b) {} +static inline void bch2_verify_insert_pos(struct btree *b, + struct bkey_packed *where, + struct bkey_packed *insert, + unsigned clobber_u64s) {} static inline void bch2_verify_key_order(struct btree *b, struct btree_node_iter *iter, struct bkey_packed *where) {} |