diff options
Diffstat (limited to 'drivers/md/bcache/bset.h')
| -rw-r--r-- | drivers/md/bcache/bset.h | 217 |
1 files changed, 128 insertions, 89 deletions
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index ae964624efb2..6ee2c6a506a2 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -1,10 +1,11 @@ +/* SPDX-License-Identifier: GPL-2.0 */ #ifndef _BCACHE_BSET_H #define _BCACHE_BSET_H -#include <linux/bcache.h> #include <linux/kernel.h> #include <linux/types.h> +#include "bcache_ondisk.h" #include "util.h" /* for time_stats */ /* @@ -162,10 +163,10 @@ struct bset_tree { */ /* size of the binary tree and prev array */ - unsigned size; + unsigned int size; /* function of size - precalculated for to_inorder() */ - unsigned extra; + unsigned int extra; /* copy of the last key in the set */ struct bkey end; @@ -186,18 +187,25 @@ struct bset_tree { }; struct btree_keys_ops { - bool (*sort_cmp)(struct btree_iter_set, - struct btree_iter_set); - struct bkey *(*sort_fixup)(struct btree_iter *, struct bkey *); - bool (*insert_fixup)(struct btree_keys *, struct bkey *, - struct btree_iter *, struct bkey *); - bool (*key_invalid)(struct btree_keys *, - const struct bkey *); - bool (*key_bad)(struct btree_keys *, const struct bkey *); - bool (*key_merge)(struct btree_keys *, - struct bkey *, struct bkey *); - void (*key_to_text)(char *, size_t, const struct bkey *); - void (*key_dump)(struct btree_keys *, const struct bkey *); + bool (*sort_cmp)(struct btree_iter_set l, + struct btree_iter_set r); + struct bkey *(*sort_fixup)(struct btree_iter *iter, + struct bkey *tmp); + bool (*insert_fixup)(struct btree_keys *b, + struct bkey *insert, + struct btree_iter *iter, + struct bkey *replace_key); + bool (*key_invalid)(struct btree_keys *bk, + const struct bkey *k); + bool (*key_bad)(struct btree_keys *bk, + const struct bkey *k); + bool (*key_merge)(struct btree_keys *bk, + struct bkey *l, struct bkey *r); + void (*key_to_text)(char *buf, + size_t size, + const struct bkey *k); + void (*key_dump)(struct btree_keys *keys, + const struct bkey *k); /* * Only used for deciding whether to use START_KEY(k) or just the key @@ -210,7 +218,7 @@ struct btree_keys { const struct btree_keys_ops *ops; uint8_t page_order; uint8_t nsets; - unsigned last_set_unwritten:1; + unsigned int last_set_unwritten:1; bool *expensive_debug_checks; /* @@ -238,12 +246,14 @@ static inline bool bkey_written(struct btree_keys *b, struct bkey *k) return !b->last_set_unwritten || k < b->set[b->nsets].data->start; } -static inline unsigned bset_byte_offset(struct btree_keys *b, struct bset *i) +static inline unsigned int bset_byte_offset(struct btree_keys *b, + struct bset *i) { return ((size_t) i) - ((size_t) b->set->data); } -static inline unsigned bset_sector_offset(struct btree_keys *b, struct bset *i) +static inline unsigned int bset_sector_offset(struct btree_keys *b, + struct bset *i) { return bset_byte_offset(b, i) >> 9; } @@ -272,25 +282,27 @@ static inline size_t bch_btree_keys_u64s_remaining(struct btree_keys *b) } static inline struct bset *bset_next_set(struct btree_keys *b, - unsigned block_bytes) + unsigned int block_bytes) { struct bset *i = bset_tree_last(b)->data; return ((void *) i) + roundup(set_bytes(i), block_bytes); } -void bch_btree_keys_free(struct btree_keys *); -int bch_btree_keys_alloc(struct btree_keys *, unsigned, gfp_t); -void bch_btree_keys_init(struct btree_keys *, const struct btree_keys_ops *, - bool *); - -void bch_bset_init_next(struct btree_keys *, struct bset *, uint64_t); -void bch_bset_build_written_tree(struct btree_keys *); -void bch_bset_fix_invalidated_key(struct btree_keys *, struct bkey *); -bool bch_bkey_try_merge(struct btree_keys *, struct bkey *, struct bkey *); -void bch_bset_insert(struct btree_keys *, struct bkey *, struct bkey *); -unsigned bch_btree_insert_key(struct btree_keys *, struct bkey *, - struct bkey *); +void bch_btree_keys_free(struct btree_keys *b); +int bch_btree_keys_alloc(struct btree_keys *b, unsigned int page_order, + gfp_t gfp); +void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops, + bool *expensive_debug_checks); + +void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic); +void bch_bset_build_written_tree(struct btree_keys *b); +void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k); +bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r); +void bch_bset_insert(struct btree_keys *b, struct bkey *where, + struct bkey *insert); +unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, + struct bkey *replace_key); enum { BTREE_INSERT_STATUS_NO_INSERT = 0, @@ -309,21 +321,35 @@ struct btree_iter { #endif struct btree_iter_set { struct bkey *k, *end; - } data[MAX_BSETS]; + } data[]; +}; + +/* Fixed-size btree_iter that can be allocated on the stack */ + +struct btree_iter_stack { + /* Must be last as it ends in a flexible-array member. */ + TRAILING_OVERLAP(struct btree_iter, iter, data, + struct btree_iter_set stack_data[MAX_BSETS]; + ); }; +static_assert(offsetof(struct btree_iter_stack, iter.data) == + offsetof(struct btree_iter_stack, stack_data)); -typedef bool (*ptr_filter_fn)(struct btree_keys *, const struct bkey *); +typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k); -struct bkey *bch_btree_iter_next(struct btree_iter *); -struct bkey *bch_btree_iter_next_filter(struct btree_iter *, - struct btree_keys *, ptr_filter_fn); +struct bkey *bch_btree_iter_next(struct btree_iter *iter); +struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter, + struct btree_keys *b, + ptr_filter_fn fn); -void bch_btree_iter_push(struct btree_iter *, struct bkey *, struct bkey *); -struct bkey *bch_btree_iter_init(struct btree_keys *, struct btree_iter *, - struct bkey *); +void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, + struct bkey *end); +struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, + struct btree_iter_stack *iter, + struct bkey *search); -struct bkey *__bch_bset_search(struct btree_keys *, struct bset_tree *, - const struct bkey *); +struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, + const struct bkey *search); /* * Returns the first key that is strictly greater than search @@ -335,34 +361,37 @@ static inline struct bkey *bch_bset_search(struct btree_keys *b, return search ? __bch_bset_search(b, t, search) : t->data->start; } -#define for_each_key_filter(b, k, iter, filter) \ - for (bch_btree_iter_init((b), (iter), NULL); \ - ((k) = bch_btree_iter_next_filter((iter), (b), filter));) +#define for_each_key_filter(b, k, stack_iter, filter) \ + for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ + ((k) = bch_btree_iter_next_filter(&((stack_iter)->iter), (b), \ + filter));) -#define for_each_key(b, k, iter) \ - for (bch_btree_iter_init((b), (iter), NULL); \ - ((k) = bch_btree_iter_next(iter));) +#define for_each_key(b, k, stack_iter) \ + for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ + ((k) = bch_btree_iter_next(&((stack_iter)->iter)));) /* Sorting */ struct bset_sort_state { - mempool_t *pool; + mempool_t pool; - unsigned page_order; - unsigned crit_factor; + unsigned int page_order; + unsigned int crit_factor; struct time_stats time; }; -void bch_bset_sort_state_free(struct bset_sort_state *); -int bch_bset_sort_state_init(struct bset_sort_state *, unsigned); -void bch_btree_sort_lazy(struct btree_keys *, struct bset_sort_state *); -void bch_btree_sort_into(struct btree_keys *, struct btree_keys *, - struct bset_sort_state *); -void bch_btree_sort_and_fix_extents(struct btree_keys *, struct btree_iter *, - struct bset_sort_state *); -void bch_btree_sort_partial(struct btree_keys *, unsigned, - struct bset_sort_state *); +void bch_bset_sort_state_free(struct bset_sort_state *state); +int bch_bset_sort_state_init(struct bset_sort_state *state, + unsigned int page_order); +void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state); +void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, + struct bset_sort_state *state); +void bch_btree_sort_and_fix_extents(struct btree_keys *b, + struct btree_iter *iter, + struct bset_sort_state *state); +void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, + struct bset_sort_state *state); static inline void bch_btree_sort(struct btree_keys *b, struct bset_sort_state *state) @@ -376,13 +405,14 @@ struct bset_stats { size_t floats, failed; }; -void bch_btree_keys_stats(struct btree_keys *, struct bset_stats *); +void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *state); /* Bkey utility code */ -#define bset_bkey_last(i) bkey_idx((struct bkey *) (i)->d, (i)->keys) +#define bset_bkey_last(i) bkey_idx((struct bkey *) (i)->d, \ + (unsigned int)(i)->keys) -static inline struct bkey *bset_bkey_idx(struct bset *i, unsigned idx) +static inline struct bkey *bset_bkey_idx(struct bset *i, unsigned int idx) { return bkey_idx(i->start, idx); } @@ -400,10 +430,10 @@ static __always_inline int64_t bkey_cmp(const struct bkey *l, : (int64_t) KEY_OFFSET(l) - (int64_t) KEY_OFFSET(r); } -void bch_bkey_copy_single_ptr(struct bkey *, const struct bkey *, - unsigned); -bool __bch_cut_front(const struct bkey *, struct bkey *); -bool __bch_cut_back(const struct bkey *, struct bkey *); +void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src, + unsigned int i); +bool __bch_cut_front(const struct bkey *where, struct bkey *k); +bool __bch_cut_back(const struct bkey *where, struct bkey *k); static inline bool bch_cut_front(const struct bkey *where, struct bkey *k) { @@ -417,20 +447,26 @@ static inline bool bch_cut_back(const struct bkey *where, struct bkey *k) return __bch_cut_back(where, k); } -#define PRECEDING_KEY(_k) \ -({ \ - struct bkey *_ret = NULL; \ - \ - if (KEY_INODE(_k) || KEY_OFFSET(_k)) { \ - _ret = &KEY(KEY_INODE(_k), KEY_OFFSET(_k), 0); \ - \ - if (!_ret->low) \ - _ret->high--; \ - _ret->low--; \ - } \ - \ - _ret; \ -}) +/* + * Pointer '*preceding_key_p' points to a memory object to store preceding + * key of k. If the preceding key does not exist, set '*preceding_key_p' to + * NULL. So the caller of preceding_key() needs to take care of memory + * which '*preceding_key_p' pointed to before calling preceding_key(). + * Currently the only caller of preceding_key() is bch_btree_insert_key(), + * and it points to an on-stack variable, so the memory release is handled + * by stackframe itself. + */ +static inline void preceding_key(struct bkey *k, struct bkey **preceding_key_p) +{ + if (KEY_INODE(k) || KEY_OFFSET(k)) { + (**preceding_key_p) = KEY(KEY_INODE(k), KEY_OFFSET(k), 0); + if (!(*preceding_key_p)->low) + (*preceding_key_p)->high--; + (*preceding_key_p)->low--; + } else { + (*preceding_key_p) = NULL; + } +} static inline bool bch_ptr_invalid(struct btree_keys *b, const struct bkey *k) { @@ -521,25 +557,28 @@ static inline size_t bch_keylist_bytes(struct keylist *l) return bch_keylist_nkeys(l) * sizeof(uint64_t); } -struct bkey *bch_keylist_pop(struct keylist *); -void bch_keylist_pop_front(struct keylist *); -int __bch_keylist_realloc(struct keylist *, unsigned); +struct bkey *bch_keylist_pop(struct keylist *l); +void bch_keylist_pop_front(struct keylist *l); +int __bch_keylist_realloc(struct keylist *l, unsigned int u64s); /* Debug stuff */ #ifdef CONFIG_BCACHE_DEBUG -int __bch_count_data(struct btree_keys *); -void __bch_check_keys(struct btree_keys *, const char *, ...); -void bch_dump_bset(struct btree_keys *, struct bset *, unsigned); -void bch_dump_bucket(struct btree_keys *); +int __bch_count_data(struct btree_keys *b); +void __printf(2, 3) __bch_check_keys(struct btree_keys *b, + const char *fmt, + ...); +void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set); +void bch_dump_bucket(struct btree_keys *b); #else static inline int __bch_count_data(struct btree_keys *b) { return -1; } -static inline void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) {} +static inline void __printf(2, 3) + __bch_check_keys(struct btree_keys *b, const char *fmt, ...) {} static inline void bch_dump_bucket(struct btree_keys *b) {} -void bch_dump_bset(struct btree_keys *, struct bset *, unsigned); +void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set); #endif |