#include "btree_cache.h"
#include "bset.h"
#include "eytzinger.h"
+#include "trace.h"
#include "util.h"
#include <asm/unaligned.h>
#include <linux/random.h>
#include <linux/prefetch.h>
-/* hack.. */
-#include "alloc_types.h"
-#include <trace/events/bcachefs.h>
-
static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *,
struct btree *);
struct bset_tree *bch2_bkey_to_bset(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();
+ return bch2_bkey_to_bset_inlined(b, k);
}
/*
for (_k = i->start;
_k < vstruct_last(i);
_k = _n) {
- _n = bkey_next(_k);
+ _n = bkey_p_next(_k);
+
+ if (!_k->u64s) {
+ printk(KERN_ERR "block %u key %5zu - u64s 0? aieee!\n", set,
+ _k->_data - i->_data);
+ break;
+ }
k = bkey_disassemble(b, _k, &uk);
n = bkey_unpack_key(b, _n);
- if (bpos_cmp(n.p, k.k->p) < 0) {
+ if (bpos_lt(n.p, k.k->p)) {
printk(KERN_ERR "Key skipped backwards\n");
continue;
}
- if (!bkey_deleted(k.k) &&
- !bpos_cmp(n.p, k.k->p))
+ if (!bkey_deleted(k.k) && bpos_eq(n.p, k.k->p))
printk(KERN_ERR "Duplicate keys\n");
}
printk(KERN_ERR "iter was:");
btree_node_iter_for_each(_iter, set) {
- struct bkey_packed *k = __btree_node_offset_to_key(b, set->k);
- struct bset_tree *t = bch2_bkey_to_bset(b, k);
+ struct bkey_packed *k2 = __btree_node_offset_to_key(b, set->k);
+ struct bset_tree *t = bch2_bkey_to_bset(b, k2);
printk(" [%zi %zi]", t - b->set,
- k->_data - bset(b, t)->_data);
+ k2->_data - bset(b, t)->_data);
}
panic("\n");
}
{
struct bset_tree *t = bch2_bkey_to_bset(b, where);
struct bkey_packed *prev = bch2_bkey_prev_all(b, t, where);
- struct bkey_packed *next = (void *) (where->_data + clobber_u64s);
+ struct bkey_packed *next = (void *) ((u64 *) where->_data + clobber_u64s);
struct printbuf buf1 = PRINTBUF;
struct printbuf buf2 = PRINTBUF;
#if 0
}
struct ro_aux_tree {
- struct bkey_float f[0];
+ u8 nothing[0];
+ struct bkey_float f[];
};
struct rw_aux_tree {
{
unsigned prev_u64s = ro_aux_tree_prev(b, t)[j];
- return (void *) (tree_to_bkey(b, t, j)->_data - prev_u64s);
+ return (void *) ((u64 *) tree_to_bkey(b, t, j)->_data - prev_u64s);
}
static struct rw_aux_tree *rw_aux_tree(const struct btree *b,
goto start;
while (1) {
if (rw_aux_to_bkey(b, t, j) == k) {
- BUG_ON(bpos_cmp(rw_aux_tree(b, t)[j].k,
+ BUG_ON(!bpos_eq(rw_aux_tree(b, t)[j].k,
bkey_unpack_pos(b, k)));
start:
if (++j == t->size)
rw_aux_tree(b, t)[j - 1].offset);
}
- k = bkey_next(k);
+ k = bkey_p_next(k);
BUG_ON(k >= btree_bkey_last(b, t));
}
}
return (u16) v;
}
-__always_inline
-static inline void make_bfloat(struct btree *b, struct bset_tree *t,
- unsigned j,
- struct bkey_packed *min_key,
- struct bkey_packed *max_key)
+static __always_inline void make_bfloat(struct btree *b, struct bset_tree *t,
+ unsigned j,
+ struct bkey_packed *min_key,
+ struct bkey_packed *max_key)
{
struct bkey_float *f = bkey_float(b, t, j);
struct bkey_packed *m = tree_to_bkey(b, t, j);
/* First we figure out where the first key in each cacheline is */
eytzinger1_for_each(j, t->size - 1) {
while (bkey_to_cacheline(b, t, k) < cacheline)
- prev = k, k = bkey_next(k);
+ prev = k, k = bkey_p_next(k);
if (k >= btree_bkey_last(b, t)) {
/* XXX: this path sucks */
}
while (k != btree_bkey_last(b, t))
- prev = k, k = bkey_next(k);
+ prev = k, k = bkey_p_next(k);
if (!bkey_pack_pos(bkey_to_packed(&min_key), b->data->min_key, b)) {
bkey_init(&min_key.k);
struct bkey_packed *p, *i, *ret = NULL, *orig_k = k;
while ((p = __bkey_prev(b, t, k)) && !ret) {
- for (i = p; i != k; i = bkey_next(i))
+ for (i = p; i != k; i = bkey_p_next(i))
if (i->type >= min_key_type)
ret = i;
BUG_ON(ret >= orig_k);
for (i = ret
- ? bkey_next(ret)
+ ? bkey_p_next(ret)
: btree_bkey_first(b, t);
i != orig_k;
- i = bkey_next(i))
+ i = bkey_p_next(i))
BUG_ON(i->type >= min_key_type);
}
t->size -= j - l;
for (j = l; j < t->size; j++)
- rw_aux_tree(b, t)[j].offset += shift;
+ rw_aux_tree(b, t)[j].offset += shift;
EBUG_ON(l < t->size &&
rw_aux_tree(b, t)[l].offset ==
struct bkey_packed *k = start;
while (1) {
- k = bkey_next(k);
+ k = bkey_p_next(k);
if (k == end)
break;
btree_keys_account_key_add(&b->nr, t - b->set, src);
if (src->u64s != clobber_u64s) {
- u64 *src_p = where->_data + clobber_u64s;
- u64 *dst_p = where->_data + src->u64s;
+ u64 *src_p = (u64 *) where->_data + clobber_u64s;
+ u64 *dst_p = (u64 *) where->_data + src->u64s;
EBUG_ON((int) le16_to_cpu(bset(b, t)->u64s) <
(int) clobber_u64s - src->u64s);
set_btree_bset_end(b, t);
}
- memcpy_u64s(where, src,
+ memcpy_u64s_small(where, src,
bkeyp_key_u64s(f, src));
memcpy_u64s(bkeyp_val(f, where), &insert->v,
bkeyp_val_u64s(f, src));
unsigned clobber_u64s)
{
struct bset_tree *t = bset_tree_last(b);
- u64 *src_p = where->_data + clobber_u64s;
+ u64 *src_p = (u64 *) where->_data + clobber_u64s;
u64 *dst_p = where->_data;
bch2_bset_verify_rw_aux_tree(b, t);
while (l + 1 != r) {
unsigned m = (l + r) >> 1;
- if (bpos_cmp(rw_aux_tree(b, t)[m].k, *search) < 0)
+ if (bpos_lt(rw_aux_tree(b, t)[m].k, *search))
l = m;
else
r = m;
case BSET_RO_AUX_TREE:
return bset_search_tree(b, t, search, lossy_packed_search);
default:
- unreachable();
+ BUG();
}
}
while (m != btree_bkey_last(b, t) &&
bkey_iter_cmp_p_or_unp(b, m,
lossy_packed_search, search) < 0)
- m = bkey_next(m);
+ m = bkey_p_next(m);
if (!packed_search)
while (m != btree_bkey_last(b, t) &&
bkey_iter_pos_cmp(b, m, search) < 0)
- m = bkey_next(m);
+ m = bkey_p_next(m);
if (bch2_expensive_debug_checks) {
struct bkey_packed *prev = bch2_bkey_prev_all(b, t, m);
bch2_btree_node_iter_sort(iter, b);
}
-noinline __flatten __attribute__((cold))
+noinline __flatten __cold
static void btree_node_iter_init_pack_failed(struct btree_node_iter *iter,
struct btree *b, struct bpos *search)
{
}
/**
- * bch_btree_node_iter_init - initialize a btree node iterator, starting from a
+ * bch2_btree_node_iter_init - initialize a btree node iterator, starting from a
* given position
*
+ * @iter: iterator to initialize
+ * @b: btree node to search
+ * @search: search key
+ *
* Main entry point to the lookup code for individual btree nodes:
*
* NOTE:
struct bkey_packed *k[MAX_BSETS];
unsigned i;
- EBUG_ON(bpos_cmp(*search, b->data->min_key) < 0);
- EBUG_ON(bpos_cmp(*search, b->data->max_key) > 0);
+ EBUG_ON(bpos_lt(*search, b->data->min_key));
+ EBUG_ON(bpos_gt(*search, b->data->max_key));
bset_aux_tree_verify(b);
memset(iter, 0, sizeof(*iter));
EBUG_ON(iter->data->k > iter->data->end);
if (unlikely(__btree_node_iter_set_end(iter, 0))) {
- bch2_btree_node_iter_set_drop(iter, iter->data);
+ /* avoid an expensive memmove call: */
+ iter->data[0] = iter->data[1];
+ iter->data[1] = iter->data[2];
+ iter->data[2] = (struct btree_node_iter_set) { 0, 0 };
return;
}
/* Mergesort */
-void bch2_btree_keys_stats(struct btree *b, struct bset_stats *stats)
+void bch2_btree_keys_stats(const struct btree *b, struct bset_stats *stats)
{
- struct bset_tree *t;
+ const struct bset_tree *t;
for_each_bset(b, t) {
enum bset_aux_tree_type type = bset_aux_tree_type(t);
switch (bkey_float(b, t, j)->exponent) {
case BFLOAT_FAILED:
uk = bkey_unpack_key(b, k);
- pr_buf(out,
+ prt_printf(out,
" failed unpacked at depth %u\n"
"\t",
ilog2(j));
bch2_bpos_to_text(out, uk.p);
- pr_buf(out, "\n");
+ prt_printf(out, "\n");
break;
}
}