^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: GPL-2.0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #ifndef _BCACHE_BSET_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) #define _BCACHE_BSET_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) #include <linux/bcache.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/types.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include "util.h" /* for time_stats */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * BKEYS:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * A bkey contains a key, a size field, a variable number of pointers, and some
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * ancillary flag bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * We use two different functions for validating bkeys, bch_ptr_invalid and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * bch_ptr_bad().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * bch_ptr_invalid() primarily filters out keys and pointers that would be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * invalid due to some sort of bug, whereas bch_ptr_bad() filters out keys and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * pointer that occur in normal practice but don't point to real data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * The one exception to the rule that ptr_invalid() filters out invalid keys is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * that it also filters out keys of size 0 - these are keys that have been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * completely overwritten. It'd be safe to delete these in memory while leaving
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * them on disk, just unnecessary work - so we filter them out when resorting
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * instead.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * We can't filter out stale keys when we're resorting, because garbage
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * collection needs to find them to ensure bucket gens don't wrap around -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * unless we're rewriting the btree node those stale keys still exist on disk.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * We also implement functions here for removing some number of sectors from the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * front or the back of a bkey - this is mainly used for fixing overlapping
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * extents, by removing the overlapping sectors from the older key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) * BSETS:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * A bset is an array of bkeys laid out contiguously in memory in sorted order,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * along with a header. A btree node is made up of a number of these, written at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * different times.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * There could be many of them on disk, but we never allow there to be more than
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) * 4 in memory - we lazily resort as needed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * We implement code here for creating and maintaining auxiliary search trees
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * (described below) for searching an individial bset, and on top of that we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * implement a btree iterator.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * BTREE ITERATOR:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * Most of the code in bcache doesn't care about an individual bset - it needs
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * to search entire btree nodes and iterate over them in sorted order.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * The btree iterator code serves both functions; it iterates through the keys
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) * in a btree node in sorted order, starting from either keys after a specific
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * point (if you pass it a search key) or the start of the btree node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * AUXILIARY SEARCH TREES:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * Since keys are variable length, we can't use a binary search on a bset - we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * wouldn't be able to find the start of the next key. But binary searches are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * slow anyways, due to terrible cache behaviour; bcache originally used binary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * searches and that code topped out at under 50k lookups/second.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * So we need to construct some sort of lookup table. Since we only insert keys
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * into the last (unwritten) set, most of the keys within a given btree node are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * usually in sets that are mostly constant. We use two different types of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) * lookup tables to take advantage of this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * Both lookup tables share in common that they don't index every key in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * set; they index one key every BSET_CACHELINE bytes, and then a linear search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * is used for the rest.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) * For sets that have been written to disk and are no longer being inserted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * into, we construct a binary search tree in an array - traversing a binary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) * search tree in an array gives excellent locality of reference and is very
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) * fast, since both children of any node are adjacent to each other in memory
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) * (and their grandchildren, and great grandchildren...) - this means
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) * prefetching can be used to great effect.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * It's quite useful performance wise to keep these nodes small - not just
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * because they're more likely to be in L2, but also because we can prefetch
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * more nodes on a single cacheline and thus prefetch more iterations in advance
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * when traversing this tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) * Nodes in the auxiliary search tree must contain both a key to compare against
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * (we don't want to fetch the key from the set, that would defeat the purpose),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * and a pointer to the key. We use a few tricks to compress both of these.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * To compress the pointer, we take advantage of the fact that one node in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * search tree corresponds to precisely BSET_CACHELINE bytes in the set. We have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * a function (to_inorder()) that takes the index of a node in a binary tree and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) * returns what its index would be in an inorder traversal, so we only have to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * store the low bits of the offset.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * The key is 84 bits (KEY_DEV + key->key, the offset on the device). To
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * compress that, we take advantage of the fact that when we're traversing the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) * search tree at every iteration we know that both our search key and the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * we're looking for lie within some range - bounded by our previous
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) * comparisons. (We special case the start of a search so that this is true even
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * at the root of the tree).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * So we know the key we're looking for is between a and b, and a and b don't
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) * differ higher than bit 50, we don't need to check anything higher than bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) * 50.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) * We don't usually need the rest of the bits, either; we only need enough bits
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) * to partition the key range we're currently checking. Consider key n - the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) * key our auxiliary search tree node corresponds to, and key p, the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) * immediately preceding n. The lowest bit we need to store in the auxiliary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) * search tree is the highest bit that differs between n and p.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) * Note that this could be bit 0 - we might sometimes need all 80 bits to do the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) * comparison. But we'd really like our nodes in the auxiliary search tree to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) * of fixed size.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) * The solution is to make them fixed size, and when we're constructing a node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) * check if p and n differed in the bits we needed them to. If they don't we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) * flag that node, and when doing lookups we fallback to comparing against the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) * real key. As long as this doesn't happen to often (and it seems to reliably
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) * happen a bit less than 1% of the time), we win - even on failures, that key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) * is then more likely to be in cache than if we were doing binary searches all
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) * the way, since we're touching so much less memory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) * The keys in the auxiliary search tree are stored in (software) floating
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) * point, with an exponent and a mantissa. The exponent needs to be big enough
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) * to address all the bits in the original key, but the number of bits in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) * mantissa is somewhat arbitrary; more bits just gets us fewer failures.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) * We need 7 bits for the exponent and 3 bits for the key's offset (since keys
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) * are 8 byte aligned); using 22 bits for the mantissa means a node is 4 bytes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) * We need one node per 128 bytes in the btree node, which means the auxiliary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) * search trees take up 3% as much memory as the btree itself.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) * Constructing these auxiliary search trees is moderately expensive, and we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) * don't want to be constantly rebuilding the search tree for the last set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) * whenever we insert another key into it. For the unwritten set, we use a much
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) * simpler lookup table - it's just a flat array, so index i in the lookup table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) * corresponds to the i range of BSET_CACHELINE bytes in the set. Indexing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) * within each byte range works the same as with the auxiliary search trees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) * These are much easier to keep up to date when we insert a key - we do it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) * somewhat lazily; when we shift a key up we usually just increment the pointer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) * to it, only when it would overflow do we go to the trouble of finding the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) * first key in that range of bytes again.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) struct btree_keys;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) struct btree_iter;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) struct btree_iter_set;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) struct bkey_float;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) #define MAX_BSETS 4U
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) struct bset_tree {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) * We construct a binary tree in an array as if the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) * started at 1, so that things line up on the same cachelines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) * better: see comments in bset.c at cacheline_to_bkey() for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) * details
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) /* size of the binary tree and prev array */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) unsigned int size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) /* function of size - precalculated for to_inorder() */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) unsigned int extra;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) /* copy of the last key in the set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) struct bkey end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) struct bkey_float *tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) * The nodes in the bset tree point to specific keys - this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) * array holds the sizes of the previous key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) * Conceptually it's a member of struct bkey_float, but we want
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) * to keep bkey_float to 4 bytes and prev isn't used in the fast
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) * path.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) uint8_t *prev;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) /* The actual btree node, with pointers to each sorted set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) struct bset *data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) struct btree_keys_ops {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) bool (*sort_cmp)(struct btree_iter_set l,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) struct btree_iter_set r);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) struct bkey *(*sort_fixup)(struct btree_iter *iter,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) struct bkey *tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) bool (*insert_fixup)(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) struct bkey *insert,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) struct btree_iter *iter,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) struct bkey *replace_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) bool (*key_invalid)(struct btree_keys *bk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) const struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) bool (*key_bad)(struct btree_keys *bk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) const struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) bool (*key_merge)(struct btree_keys *bk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) struct bkey *l, struct bkey *r);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) void (*key_to_text)(char *buf,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) size_t size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) const struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) void (*key_dump)(struct btree_keys *keys,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) const struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) * Only used for deciding whether to use START_KEY(k) or just the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) * itself in a couple places
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) bool is_extents;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) struct btree_keys {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) const struct btree_keys_ops *ops;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) uint8_t page_order;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) uint8_t nsets;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) unsigned int last_set_unwritten:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) bool *expensive_debug_checks;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) * Sets of sorted keys - the real btree node - plus a binary search tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) * to the memory we have allocated for this btree node. Additionally,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) * set[0]->data points to the entire btree node as it exists on disk.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) struct bset_tree set[MAX_BSETS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) static inline struct bset_tree *bset_tree_last(struct btree_keys *b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) return b->set + b->nsets;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) static inline bool bset_written(struct btree_keys *b, struct bset_tree *t)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) return t <= b->set + b->nsets - b->last_set_unwritten;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) static inline bool bkey_written(struct btree_keys *b, struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) return !b->last_set_unwritten || k < b->set[b->nsets].data->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) static inline unsigned int bset_byte_offset(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) struct bset *i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) return ((size_t) i) - ((size_t) b->set->data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) static inline unsigned int bset_sector_offset(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) struct bset *i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) return bset_byte_offset(b, i) >> 9;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) #define __set_bytes(i, k) (sizeof(*(i)) + (k) * sizeof(uint64_t))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) #define set_bytes(i) __set_bytes(i, i->keys)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) #define __set_blocks(i, k, block_bytes) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) DIV_ROUND_UP(__set_bytes(i, k), block_bytes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) #define set_blocks(i, block_bytes) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) __set_blocks(i, (i)->keys, block_bytes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) static inline size_t bch_btree_keys_u64s_remaining(struct btree_keys *b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) struct bset_tree *t = bset_tree_last(b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) BUG_ON((PAGE_SIZE << b->page_order) <
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) (bset_byte_offset(b, t->data) + set_bytes(t->data)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) if (!b->last_set_unwritten)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) return ((PAGE_SIZE << b->page_order) -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) (bset_byte_offset(b, t->data) + set_bytes(t->data))) /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) sizeof(u64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) static inline struct bset *bset_next_set(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) unsigned int block_bytes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) struct bset *i = bset_tree_last(b)->data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) return ((void *) i) + roundup(set_bytes(i), block_bytes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) void bch_btree_keys_free(struct btree_keys *b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) int bch_btree_keys_alloc(struct btree_keys *b, unsigned int page_order,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) gfp_t gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) bool *expensive_debug_checks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) void bch_bset_build_written_tree(struct btree_keys *b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) void bch_bset_insert(struct btree_keys *b, struct bkey *where,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) struct bkey *insert);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) struct bkey *replace_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) enum {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) BTREE_INSERT_STATUS_NO_INSERT = 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) BTREE_INSERT_STATUS_INSERT,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) BTREE_INSERT_STATUS_BACK_MERGE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) BTREE_INSERT_STATUS_OVERWROTE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) BTREE_INSERT_STATUS_FRONT_MERGE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) /* Btree key iteration */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) struct btree_iter {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) size_t size, used;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) #ifdef CONFIG_BCACHE_DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) struct btree_keys *b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) struct btree_iter_set {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) struct bkey *k, *end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) } data[MAX_BSETS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) struct bkey *bch_btree_iter_next(struct btree_iter *iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) ptr_filter_fn fn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) struct bkey *end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) struct bkey *bch_btree_iter_init(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) struct btree_iter *iter,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) struct bkey *search);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) const struct bkey *search);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) * Returns the first key that is strictly greater than search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) static inline struct bkey *bch_bset_search(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) struct bset_tree *t,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) const struct bkey *search)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) return search ? __bch_bset_search(b, t, search) : t->data->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) #define for_each_key_filter(b, k, iter, filter) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) for (bch_btree_iter_init((b), (iter), NULL); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) ((k) = bch_btree_iter_next_filter((iter), (b), filter));)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) #define for_each_key(b, k, iter) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) for (bch_btree_iter_init((b), (iter), NULL); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) ((k) = bch_btree_iter_next(iter));)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) /* Sorting */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) struct bset_sort_state {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) mempool_t pool;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) unsigned int page_order;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) unsigned int crit_factor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) struct time_stats time;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) void bch_bset_sort_state_free(struct bset_sort_state *state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) int bch_bset_sort_state_init(struct bset_sort_state *state,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) unsigned int page_order);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) struct bset_sort_state *state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) void bch_btree_sort_and_fix_extents(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) struct btree_iter *iter,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) struct bset_sort_state *state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) void bch_btree_sort_partial(struct btree_keys *b, unsigned int start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) struct bset_sort_state *state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) static inline void bch_btree_sort(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) struct bset_sort_state *state)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) bch_btree_sort_partial(b, 0, state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) struct bset_stats {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) size_t sets_written, sets_unwritten;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) size_t bytes_written, bytes_unwritten;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) size_t floats, failed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *state);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) /* Bkey utility code */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) #define bset_bkey_last(i) bkey_idx((struct bkey *) (i)->d, \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) (unsigned int)(i)->keys)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) static inline struct bkey *bset_bkey_idx(struct bset *i, unsigned int idx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) return bkey_idx(i->start, idx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) static inline void bkey_init(struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) *k = ZERO_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) static __always_inline int64_t bkey_cmp(const struct bkey *l,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) const struct bkey *r)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) return unlikely(KEY_INODE(l) != KEY_INODE(r))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) ? (int64_t) KEY_INODE(l) - (int64_t) KEY_INODE(r)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) : (int64_t) KEY_OFFSET(l) - (int64_t) KEY_OFFSET(r);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) unsigned int i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) bool __bch_cut_front(const struct bkey *where, struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) bool __bch_cut_back(const struct bkey *where, struct bkey *k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) static inline bool bch_cut_front(const struct bkey *where, struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) BUG_ON(bkey_cmp(where, k) > 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) return __bch_cut_front(where, k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) static inline bool bch_cut_back(const struct bkey *where, struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) BUG_ON(bkey_cmp(where, &START_KEY(k)) < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) return __bch_cut_back(where, k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) * Pointer '*preceding_key_p' points to a memory object to store preceding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) * key of k. If the preceding key does not exist, set '*preceding_key_p' to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) * NULL. So the caller of preceding_key() needs to take care of memory
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) * which '*preceding_key_p' pointed to before calling preceding_key().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) * Currently the only caller of preceding_key() is bch_btree_insert_key(),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) * and it points to an on-stack variable, so the memory release is handled
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) * by stackframe itself.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) static inline void preceding_key(struct bkey *k, struct bkey **preceding_key_p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) if (KEY_INODE(k) || KEY_OFFSET(k)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) (**preceding_key_p) = KEY(KEY_INODE(k), KEY_OFFSET(k), 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) if (!(*preceding_key_p)->low)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) (*preceding_key_p)->high--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) (*preceding_key_p)->low--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) (*preceding_key_p) = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) static inline bool bch_ptr_invalid(struct btree_keys *b, const struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) return b->ops->key_invalid(b, k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) static inline bool bch_ptr_bad(struct btree_keys *b, const struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) return b->ops->key_bad(b, k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) static inline void bch_bkey_to_text(struct btree_keys *b, char *buf,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) size_t size, const struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) return b->ops->key_to_text(buf, size, k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) static inline bool bch_bkey_equal_header(const struct bkey *l,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) const struct bkey *r)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) return (KEY_DIRTY(l) == KEY_DIRTY(r) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) KEY_PTRS(l) == KEY_PTRS(r) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) KEY_CSUM(l) == KEY_CSUM(r));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) /* Keylists */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) struct keylist {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) union {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) struct bkey *keys;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) uint64_t *keys_p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) union {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) struct bkey *top;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) uint64_t *top_p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) /* Enough room for btree_split's keys without realloc */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) #define KEYLIST_INLINE 16
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) uint64_t inline_keys[KEYLIST_INLINE];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) static inline void bch_keylist_init(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) l->top_p = l->keys_p = l->inline_keys;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) static inline void bch_keylist_init_single(struct keylist *l, struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) l->keys = k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) l->top = bkey_next(k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) static inline void bch_keylist_push(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) l->top = bkey_next(l->top);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) static inline void bch_keylist_add(struct keylist *l, struct bkey *k)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) bkey_copy(l->top, k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) bch_keylist_push(l);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) static inline bool bch_keylist_empty(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) return l->top == l->keys;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) static inline void bch_keylist_reset(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) l->top = l->keys;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) static inline void bch_keylist_free(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) if (l->keys_p != l->inline_keys)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) kfree(l->keys_p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) static inline size_t bch_keylist_nkeys(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) return l->top_p - l->keys_p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) static inline size_t bch_keylist_bytes(struct keylist *l)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) return bch_keylist_nkeys(l) * sizeof(uint64_t);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) struct bkey *bch_keylist_pop(struct keylist *l);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) void bch_keylist_pop_front(struct keylist *l);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) int __bch_keylist_realloc(struct keylist *l, unsigned int u64s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) /* Debug stuff */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) #ifdef CONFIG_BCACHE_DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) int __bch_count_data(struct btree_keys *b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) void __printf(2, 3) __bch_check_keys(struct btree_keys *b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) const char *fmt,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) ...);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) void bch_dump_bucket(struct btree_keys *b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) static inline int __bch_count_data(struct btree_keys *b) { return -1; }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) static inline void __printf(2, 3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) __bch_check_keys(struct btree_keys *b, const char *fmt, ...) {}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) static inline void bch_dump_bucket(struct btree_keys *b) {}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) static inline bool btree_keys_expensive_checks(struct btree_keys *b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) #ifdef CONFIG_BCACHE_DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) return *b->expensive_debug_checks;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) static inline int bch_count_data(struct btree_keys *b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) return btree_keys_expensive_checks(b) ? __bch_count_data(b) : -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) #define bch_check_keys(b, ...) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) if (btree_keys_expensive_checks(b)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) __bch_check_keys(b, __VA_ARGS__); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) #endif
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags