X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Fbset.h;h=632c2b8c54609b4be37f11e18868e4c41dcb736b;hb=e3e7f67b3ed89f5b3158142c29e66bb98f868ce2;hp=2653a74b3b14ad5741d0ab15af4ef685c2c4455d;hpb=ffced87f08a9ff929f78fd941536d4f88507588a;p=bcachefs-tools-debian diff --git a/libbcachefs/bset.h b/libbcachefs/bset.h index 2653a74..632c2b8 100644 --- a/libbcachefs/bset.h +++ b/libbcachefs/bset.h @@ -5,7 +5,7 @@ #include #include -#include "bcachefs_format.h" +#include "bcachefs.h" #include "bkey.h" #include "bkey_methods.h" #include "btree_types.h" @@ -147,17 +147,6 @@ * first key in that range of bytes again. */ -extern bool bch2_expensive_debug_checks; - -static inline bool btree_keys_expensive_checks(const struct btree *b) -{ -#ifdef CONFIG_BCACHEFS_DEBUG - return bch2_expensive_debug_checks || *b->expensive_debug_checks; -#else - return false; -#endif -} - enum bset_aux_tree_type { BSET_NO_AUX_TREE, BSET_RO_AUX_TREE, @@ -184,104 +173,36 @@ static inline enum bset_aux_tree_type bset_aux_tree_type(const struct bset_tree } } -typedef void (*compiled_unpack_fn)(struct bkey *, const struct bkey_packed *); - -static inline void -__bkey_unpack_key_format_checked(const struct btree *b, - struct bkey *dst, - const struct bkey_packed *src) -{ -#ifdef HAVE_BCACHEFS_COMPILED_UNPACK - { - compiled_unpack_fn unpack_fn = b->aux_data; - unpack_fn(dst, src); - - if (btree_keys_expensive_checks(b)) { - struct bkey dst2 = __bch2_bkey_unpack_key(&b->format, src); - - /* - * hack around a harmless race when compacting whiteouts - * for a write: - */ - dst2.needs_whiteout = dst->needs_whiteout; - - BUG_ON(memcmp(dst, &dst2, sizeof(*dst))); - } - } -#else - *dst = __bch2_bkey_unpack_key(&b->format, src); -#endif -} - -static inline struct bkey -bkey_unpack_key_format_checked(const struct btree *b, - const struct bkey_packed *src) -{ - struct bkey dst; - - __bkey_unpack_key_format_checked(b, &dst, src); - return dst; -} - -static inline void __bkey_unpack_key(const struct btree *b, - struct bkey *dst, - const struct bkey_packed *src) -{ - if (likely(bkey_packed(src))) - __bkey_unpack_key_format_checked(b, dst, src); - else - *dst = *packed_to_bkey_c(src); -} - -/** - * bkey_unpack_key -- unpack just the key, not the value +/* + * BSET_CACHELINE was originally intended to match the hardware cacheline size - + * it used to be 64, but I realized the lookup code would touch slightly less + * memory if it was 128. + * + * It definites the number of bytes (in struct bset) per struct bkey_float in + * the auxiliar search tree - when we're done searching the bset_float tree we + * have this many bytes left that we do a linear search over. + * + * Since (after level 5) every level of the bset_tree is on a new cacheline, + * we're touching one fewer cacheline in the bset tree in exchange for one more + * cacheline in the linear search - but the linear search might stop before it + * gets to the second cacheline. */ -static inline struct bkey bkey_unpack_key(const struct btree *b, - const struct bkey_packed *src) -{ - return likely(bkey_packed(src)) - ? bkey_unpack_key_format_checked(b, src) - : *packed_to_bkey_c(src); -} -static inline struct bpos -bkey_unpack_pos_format_checked(const struct btree *b, - const struct bkey_packed *src) -{ -#ifdef HAVE_BCACHEFS_COMPILED_UNPACK - return bkey_unpack_key_format_checked(b, src).p; -#else - return __bkey_unpack_pos(&b->format, src); -#endif -} +#define BSET_CACHELINE 256 -static inline struct bpos bkey_unpack_pos(const struct btree *b, - const struct bkey_packed *src) +static inline size_t btree_keys_cachelines(const struct btree *b) { - return likely(bkey_packed(src)) - ? bkey_unpack_pos_format_checked(b, src) - : packed_to_bkey_c(src)->p; + return (1U << b->byte_order) / BSET_CACHELINE; } -/* Disassembled bkeys */ - -static inline struct bkey_s_c bkey_disassemble(struct btree *b, - const struct bkey_packed *k, - struct bkey *u) +static inline size_t btree_aux_data_bytes(const struct btree *b) { - __bkey_unpack_key(b, u, k); - - return (struct bkey_s_c) { u, bkeyp_val(&b->format, k), }; + return btree_keys_cachelines(b) * 8; } -/* non const version: */ -static inline struct bkey_s __bkey_disassemble(struct btree *b, - struct bkey_packed *k, - struct bkey *u) +static inline size_t btree_aux_data_u64s(const struct btree *b) { - __bkey_unpack_key(b, u, k); - - return (struct bkey_s) { .k = u, .v = bkeyp_val(&b->format, k), }; + return btree_aux_data_bytes(b) / sizeof(u64); } #define for_each_bset(_b, _t) \ @@ -290,9 +211,9 @@ static inline struct bkey_s __bkey_disassemble(struct btree *b, #define bset_tree_for_each_key(_b, _t, _k) \ for (_k = btree_bkey_first(_b, _t); \ _k != btree_bkey_last(_b, _t); \ - _k = bkey_next_skip_noops(_k, btree_bkey_last(_b, _t))) + _k = bkey_p_next(_k)) -static inline bool bset_has_ro_aux_tree(struct bset_tree *t) +static inline bool bset_has_ro_aux_tree(const struct bset_tree *t) { return bset_aux_tree_type(t) == BSET_RO_AUX_TREE; } @@ -340,15 +261,12 @@ static inline struct bset *bset_next_set(struct btree *b, return ((void *) i) + round_up(vstruct_bytes(i), block_bytes); } -void bch2_btree_keys_free(struct btree *); -int bch2_btree_keys_alloc(struct btree *, unsigned, gfp_t); -void bch2_btree_keys_init(struct btree *, bool *); +void bch2_btree_keys_init(struct btree *); void bch2_bset_init_first(struct btree *, struct bset *); void bch2_bset_init_next(struct bch_fs *, struct btree *, struct btree_node_entry *); void bch2_bset_build_aux_tree(struct btree *, struct bset_tree *, bool); -void bch2_bset_fix_invalidated_key(struct btree *, struct bkey_packed *); void bch2_bset_insert(struct btree *, struct btree_node_iter *, struct bkey_packed *, struct bkey_i *, unsigned); @@ -360,12 +278,12 @@ void bch2_bset_delete(struct btree *, struct bkey_packed *, unsigned); static inline int bkey_cmp_p_or_unp(const struct btree *b, const struct bkey_packed *l, const struct bkey_packed *r_packed, - struct bpos *r) + const struct bpos *r) { EBUG_ON(r_packed && !bkey_packed(r_packed)); if (unlikely(!bkey_packed(l))) - return bkey_cmp(packed_to_bkey_c(l)->p, *r); + return bpos_cmp(packed_to_bkey_c(l)->p, *r); if (likely(r_packed)) return __bch2_bkey_cmp_packed_format_checked(l, r_packed, b); @@ -373,6 +291,21 @@ static inline int bkey_cmp_p_or_unp(const struct btree *b, return __bch2_bkey_cmp_left_packed_format_checked(b, l, r); } +static inline struct bset_tree * +bch2_bkey_to_bset_inlined(struct btree *b, struct bkey_packed *k) +{ + unsigned offset = __btree_node_key_to_offset(b, k); + struct bset_tree *t; + + for_each_bset(b, t) + if (offset <= t->end_offset) { + EBUG_ON(offset < btree_bkey_first_offset(t)); + return t; + } + + BUG(); +} + struct bset_tree *bch2_bkey_to_bset(struct btree *, struct bkey_packed *); struct bkey_packed *bch2_bkey_prev_filter(struct btree *, struct bset_tree *, @@ -387,25 +320,7 @@ bch2_bkey_prev_all(struct btree *b, struct bset_tree *t, struct bkey_packed *k) static inline struct bkey_packed * bch2_bkey_prev(struct btree *b, struct bset_tree *t, struct bkey_packed *k) { - return bch2_bkey_prev_filter(b, t, k, KEY_TYPE_discard + 1); -} - -enum bch_extent_overlap { - BCH_EXTENT_OVERLAP_ALL = 0, - BCH_EXTENT_OVERLAP_BACK = 1, - BCH_EXTENT_OVERLAP_FRONT = 2, - BCH_EXTENT_OVERLAP_MIDDLE = 3, -}; - -/* Returns how k overlaps with m */ -static inline enum bch_extent_overlap bch2_extent_overlap(const struct bkey *k, - const struct bkey *m) -{ - int cmp1 = bkey_cmp(k->p, m->p) < 0; - int cmp2 = bkey_cmp(bkey_start_pos(k), - bkey_start_pos(m)) > 0; - - return (cmp1 << 1) + cmp2; + return bch2_bkey_prev_filter(b, t, k, 1); } /* Btree key iteration */ @@ -449,16 +364,16 @@ static inline bool bch2_btree_node_iter_end(struct btree_node_iter *iter) * XXX: only need to compare pointers for keys that are both within a * btree_node_iterator - we need to break ties for prev() to work correctly */ -static inline int bkey_iter_cmp(struct btree *b, +static inline int bkey_iter_cmp(const struct btree *b, const struct bkey_packed *l, const struct bkey_packed *r) { - return bkey_cmp_packed(b, l, r) + return bch2_bkey_cmp_packed(b, l, r) ?: (int) bkey_deleted(r) - (int) bkey_deleted(l) ?: cmp_int(l, r); } -static inline int btree_node_iter_cmp(struct btree *b, +static inline int btree_node_iter_cmp(const struct btree *b, struct btree_node_iter_set l, struct btree_node_iter_set r) { @@ -467,22 +382,22 @@ static inline int btree_node_iter_cmp(struct btree *b, __btree_node_offset_to_key(b, r.k)); } -/* These assume l (the search key) is not a deleted key: */ -static inline int bkey_iter_pos_cmp(struct btree *b, - struct bpos *l, - const struct bkey_packed *r) +/* These assume r (the search key) is not a deleted key: */ +static inline int bkey_iter_pos_cmp(const struct btree *b, + const struct bkey_packed *l, + const struct bpos *r) { - return -bkey_cmp_left_packed(b, r, l) - ?: (int) bkey_deleted(r); + return bkey_cmp_left_packed(b, l, r) + ?: -((int) bkey_deleted(l)); } -static inline int bkey_iter_cmp_p_or_unp(struct btree *b, - struct bpos *l, - const struct bkey_packed *l_packed, - const struct bkey_packed *r) +static inline int bkey_iter_cmp_p_or_unp(const struct btree *b, + const struct bkey_packed *l, + const struct bkey_packed *r_packed, + const struct bpos *r) { - return -bkey_cmp_p_or_unp(b, r, l_packed, l) - ?: (int) bkey_deleted(r); + return bkey_cmp_p_or_unp(b, l, r_packed, r) + ?: -((int) bkey_deleted(l)); } static inline struct bkey_packed * @@ -493,33 +408,23 @@ __bch2_btree_node_iter_peek_all(struct btree_node_iter *iter, } static inline struct bkey_packed * -bch2_btree_node_iter_peek_filter(struct btree_node_iter *iter, - struct btree *b, - unsigned min_key_type) +bch2_btree_node_iter_peek_all(struct btree_node_iter *iter, struct btree *b) { - while (!bch2_btree_node_iter_end(iter)) { - struct bkey_packed *k = __bch2_btree_node_iter_peek_all(iter, b); - - if (k->type >= min_key_type) - return k; - - bch2_btree_node_iter_advance(iter, b); - } - - return NULL; -} - -static inline struct bkey_packed * -bch2_btree_node_iter_peek_all(struct btree_node_iter *iter, - struct btree *b) -{ - return bch2_btree_node_iter_peek_filter(iter, b, 0); + return !bch2_btree_node_iter_end(iter) + ? __btree_node_offset_to_key(b, iter->data->k) + : NULL; } static inline struct bkey_packed * bch2_btree_node_iter_peek(struct btree_node_iter *iter, struct btree *b) { - return bch2_btree_node_iter_peek_filter(iter, b, KEY_TYPE_discard + 1); + struct bkey_packed *k; + + while ((k = bch2_btree_node_iter_peek_all(iter, b)) && + bkey_deleted(k)) + bch2_btree_node_iter_advance(iter, b); + + return k; } static inline struct bkey_packed * @@ -535,19 +440,18 @@ bch2_btree_node_iter_next_all(struct btree_node_iter *iter, struct btree *b) struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *, struct btree *); -struct bkey_packed *bch2_btree_node_iter_prev_filter(struct btree_node_iter *, - struct btree *, unsigned); - -static inline struct bkey_packed * -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); -} +struct bkey_packed *bch2_btree_node_iter_prev(struct btree_node_iter *, + struct btree *); struct bkey_s_c bch2_btree_node_iter_peek_unpack(struct btree_node_iter *, struct btree *, struct bkey *); +#define for_each_btree_node_key(b, k, iter) \ + for (bch2_btree_node_iter_init_from_start((iter), (b)); \ + (k = bch2_btree_node_iter_peek((iter), (b))); \ + bch2_btree_node_iter_advance(iter, b)) + #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;\ @@ -600,14 +504,14 @@ struct bset_stats { size_t failed; }; -void bch2_btree_keys_stats(struct btree *, struct bset_stats *); +void bch2_btree_keys_stats(const struct btree *, struct bset_stats *); void bch2_bfloat_to_text(struct printbuf *, struct btree *, struct bkey_packed *); /* Debug stuff */ -void bch2_dump_bset(struct btree *, struct bset *, unsigned); -void bch2_dump_btree_node(struct btree *); +void bch2_dump_bset(struct bch_fs *, struct btree *, struct bset *, unsigned); +void bch2_dump_btree_node(struct bch_fs *, struct btree *); void bch2_dump_btree_node_iter(struct btree *, struct btree_node_iter *); #ifdef CONFIG_BCACHEFS_DEBUG @@ -630,7 +534,7 @@ static inline void bch2_verify_insert_pos(struct btree *b, static inline void bch2_verify_btree_nr_keys(struct btree *b) { - if (btree_keys_expensive_checks(b)) + if (bch2_debug_check_btree_accounting) __bch2_verify_btree_nr_keys(b); }