X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Fbkey.c;h=630df060fbe934b5ff8d936eed91b13b792f8f81;hb=ae43a58d97fc00e31770142da832fb8a249808eb;hp=19bf1b8fec890af3badc65cdef3568e2212070fb;hpb=85ee972555948337bb1a58f0702a4da95db6758f;p=bcachefs-tools-debian diff --git a/libbcachefs/bkey.c b/libbcachefs/bkey.c index 19bf1b8..630df06 100644 --- a/libbcachefs/bkey.c +++ b/libbcachefs/bkey.c @@ -1,41 +1,65 @@ +// SPDX-License-Identifier: GPL-2.0 #include "bcachefs.h" #include "bkey.h" +#include "bkey_cmp.h" +#include "bkey_methods.h" #include "bset.h" #include "util.h" -const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT; +#undef EBUG_ON -struct bkey __bch2_bkey_unpack_key(const struct bkey_format *, - const struct bkey_packed *); +#ifdef DEBUG_BKEYS +#define EBUG_ON(cond) BUG_ON(cond) +#else +#define EBUG_ON(cond) +#endif + +const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT; -void bch2_to_binary(char *out, const u64 *p, unsigned nr_bits) +void bch2_bkey_packed_to_binary_text(struct printbuf *out, + const struct bkey_format *f, + const struct bkey_packed *k) { - unsigned bit = high_bit_offset, done = 0; + const u64 *p = high_word(f, k); + unsigned word_bits = 64 - high_bit_offset; + unsigned nr_key_bits = bkey_format_key_bits(f) + high_bit_offset; + u64 v = *p & (~0ULL >> high_bit_offset); + + if (!nr_key_bits) { + prt_str(out, "(empty)"); + return; + } while (1) { - while (bit < 64) { - if (done && !(done % 8)) - *out++ = ' '; - *out++ = *p & (1ULL << (63 - bit)) ? '1' : '0'; - bit++; - done++; - if (done == nr_bits) { - *out++ = '\0'; - return; - } + unsigned next_key_bits = nr_key_bits; + + if (nr_key_bits < 64) { + v >>= 64 - nr_key_bits; + next_key_bits = 0; + } else { + next_key_bits -= 64; } + bch2_prt_u64_binary(out, v, min(word_bits, nr_key_bits)); + + if (!next_key_bits) + break; + + prt_char(out, ' '); + p = next_word(p); - bit = 0; + v = *p; + word_bits = 64; + nr_key_bits = next_key_bits; } } #ifdef CONFIG_BCACHEFS_DEBUG static void bch2_bkey_pack_verify(const struct bkey_packed *packed, - const struct bkey *unpacked, - const struct bkey_format *format) + const struct bkey *unpacked, + const struct bkey_format *format) { struct bkey tmp; @@ -47,22 +71,35 @@ static void bch2_bkey_pack_verify(const struct bkey_packed *packed, tmp = __bch2_bkey_unpack_key(format, packed); if (memcmp(&tmp, unpacked, sizeof(struct bkey))) { - char buf1[160], buf2[160]; - char buf3[160], buf4[160]; - - bch2_bkey_to_text(buf1, sizeof(buf1), unpacked); - bch2_bkey_to_text(buf2, sizeof(buf2), &tmp); - bch2_to_binary(buf3, (void *) unpacked, 80); - bch2_to_binary(buf4, high_word(format, packed), 80); + struct printbuf buf = PRINTBUF; - panic("keys differ: format u64s %u fields %u %u %u %u %u\n%s\n%s\n%s\n%s\n", + prt_printf(&buf, "keys differ: format u64s %u fields %u %u %u %u %u\n", format->key_u64s, format->bits_per_field[0], format->bits_per_field[1], format->bits_per_field[2], format->bits_per_field[3], - format->bits_per_field[4], - buf1, buf2, buf3, buf4); + format->bits_per_field[4]); + + prt_printf(&buf, "compiled unpack: "); + bch2_bkey_to_text(&buf, unpacked); + prt_newline(&buf); + + prt_printf(&buf, "c unpack: "); + bch2_bkey_to_text(&buf, &tmp); + prt_newline(&buf); + + prt_printf(&buf, "compiled unpack: "); + bch2_bkey_packed_to_binary_text(&buf, &bch2_bkey_format_current, + (struct bkey_packed *) unpacked); + prt_newline(&buf); + + prt_printf(&buf, "c unpack: "); + bch2_bkey_packed_to_binary_text(&buf, &bch2_bkey_format_current, + (struct bkey_packed *) &tmp); + prt_newline(&buf); + + panic("%s", buf.buf); } } @@ -72,37 +109,6 @@ static inline void bch2_bkey_pack_verify(const struct bkey_packed *packed, const struct bkey_format *format) {} #endif -int bch2_bkey_to_text(char *buf, size_t size, const struct bkey *k) -{ - char *out = buf, *end = buf + size; - -#define p(...) (out += scnprintf(out, end - out, __VA_ARGS__)) - - p("u64s %u type %u %llu:%llu snap %u len %u ver %llu", - k->u64s, k->type, k->p.inode, k->p.offset, - k->p.snapshot, k->size, k->version.lo); - - BUG_ON(bkey_packed(k)); - - switch (k->type) { - case KEY_TYPE_DELETED: - p(" deleted"); - break; - case KEY_TYPE_DISCARD: - p(" discard"); - break; - case KEY_TYPE_ERROR: - p(" error"); - break; - case KEY_TYPE_COOKIE: - p(" cookie"); - break; - } -#undef p - - return out - buf; -} - struct pack_state { const struct bkey_format *format; unsigned bits; /* bits remaining in current word */ @@ -222,9 +228,10 @@ static bool bch2_bkey_transform_key(const struct bkey_format *out_f, { struct pack_state out_s = pack_state_init(out_f, out); struct unpack_state in_s = unpack_state_init(in_f, in); + u64 *w = out->_data; unsigned i; - out->_data[0] = 0; + *w = 0; for (i = 0; i < BKEY_NR_FIELDS; i++) if (!set_inc_field(&out_s, i, get_inc_field(&in_s, i))) @@ -313,12 +320,13 @@ bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in, const struct bkey_format *format) { struct pack_state state = pack_state_init(format, out); + u64 *w = out->_data; EBUG_ON((void *) in == (void *) out); EBUG_ON(format->nr_fields != BKEY_NR_FIELDS); EBUG_ON(in->format != KEY_FORMAT_CURRENT); - out->_data[0] = 0; + *w = 0; #define x(id, field) if (!set_inc_field(&state, id, in->field)) return false; bkey_fields() @@ -328,7 +336,8 @@ bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in, * Extents - we have to guarantee that if an extent is packed, a trimmed * version will also pack: */ - if (bkey_start_offset(in) < format->field_offset[BKEY_FIELD_OFFSET]) + if (bkey_start_offset(in) < + le64_to_cpu(format->field_offset[BKEY_FIELD_OFFSET])) return false; pack_state_finish(&state, out); @@ -347,7 +356,7 @@ bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in, void bch2_bkey_unpack(const struct btree *b, struct bkey_i *dst, const struct bkey_packed *src) { - dst->k = bkey_unpack_key(b, src); + __bkey_unpack_key(b, &dst->k, src); memcpy_u64s(&dst->v, bkeyp_val(&b->format, src), @@ -431,7 +440,7 @@ static bool bkey_packed_successor(struct bkey_packed *out, if ((*p & mask) != mask) { *p += 1ULL << offset; - EBUG_ON(bkey_cmp_packed(b, out, &k) <= 0); + EBUG_ON(bch2_bkey_cmp_packed(b, out, &k) <= 0); return true; } @@ -459,12 +468,20 @@ enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out, { const struct bkey_format *f = &b->format; struct pack_state state = pack_state_init(f, out); + u64 *w = out->_data; #ifdef CONFIG_BCACHEFS_DEBUG struct bpos orig = in; #endif bool exact = true; + unsigned i; - out->_data[0] = 0; + /* + * bch2_bkey_pack_key() will write to all of f->key_u64s, minus the 3 + * byte header, but pack_pos() won't if the len/version fields are big + * enough - we need to make sure to zero them out: + */ + for (i = 0; i < f->key_u64s; i++) + w[i] = 0; if (unlikely(in.snapshot < le64_to_cpu(f->field_offset[BKEY_FIELD_SNAPSHOT]))) { @@ -505,7 +522,7 @@ enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out, pack_state_finish(&state, out); out->u64s = f->key_u64s; out->format = KEY_FORMAT_LOCAL_BTREE; - out->type = KEY_TYPE_DELETED; + out->type = KEY_TYPE_deleted; #ifdef CONFIG_BCACHEFS_DEBUG if (exact) { @@ -571,7 +588,12 @@ void bch2_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p) static void set_format_field(struct bkey_format *f, enum bch_bkey_fields i, unsigned bits, u64 offset) { - offset = bits == 64 ? 0 : min(offset, U64_MAX - ((1ULL << bits) - 1)); + unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i]; + u64 unpacked_max = ~((~0ULL << 1) << (unpacked_bits - 1)); + + bits = min(bits, unpacked_bits); + + offset = bits == unpacked_bits ? 0 : min(offset, unpacked_max - ((1ULL << bits) - 1)); f->bits_per_field[i] = bits; f->field_offset[i] = cpu_to_le64(offset); @@ -626,25 +648,29 @@ const char *bch2_bkey_format_validate(struct bkey_format *f) unsigned i, bits = KEY_PACKED_BITS_START; if (f->nr_fields != BKEY_NR_FIELDS) - return "invalid format: incorrect number of fields"; + return "incorrect number of fields"; + /* + * Verify that the packed format can't represent fields larger than the + * unpacked format: + */ for (i = 0; i < f->nr_fields; i++) { + unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i]; + u64 unpacked_max = ~((~0ULL << 1) << (unpacked_bits - 1)); + u64 packed_max = f->bits_per_field[i] + ? ~((~0ULL << 1) << (f->bits_per_field[i] - 1)) + : 0; u64 field_offset = le64_to_cpu(f->field_offset[i]); - if (f->bits_per_field[i] > 64) - return "invalid format: field too large"; - - if (field_offset && - (f->bits_per_field[i] == 64 || - (field_offset + ((1ULL << f->bits_per_field[i]) - 1) < - field_offset))) - return "invalid format: offset + bits overflow"; + if (packed_max + field_offset < packed_max || + packed_max + field_offset > unpacked_max) + return "field too large"; bits += f->bits_per_field[i]; } if (f->key_u64s != DIV_ROUND_UP(bits, 64)) - return "invalid format: incorrect key_u64s"; + return "incorrect key_u64s"; return NULL; } @@ -735,50 +761,6 @@ unsigned bch2_bkey_ffs(const struct btree *b, const struct bkey_packed *k) #ifdef CONFIG_X86_64 -static inline int __bkey_cmp_bits(const u64 *l, const u64 *r, - unsigned nr_key_bits) -{ - long d0, d1, d2, d3; - int cmp; - - /* we shouldn't need asm for this, but gcc is being retarded: */ - - asm(".intel_syntax noprefix;" - "xor eax, eax;" - "xor edx, edx;" - "1:;" - "mov r8, [rdi];" - "mov r9, [rsi];" - "sub ecx, 64;" - "jl 2f;" - - "cmp r8, r9;" - "jnz 3f;" - - "lea rdi, [rdi - 8];" - "lea rsi, [rsi - 8];" - "jmp 1b;" - - "2:;" - "not ecx;" - "shr r8, 1;" - "shr r9, 1;" - "shr r8, cl;" - "shr r9, cl;" - "cmp r8, r9;" - - "3:\n" - "seta al;" - "setb dl;" - "sub eax, edx;" - ".att_syntax prefix;" - : "=&D" (d0), "=&S" (d1), "=&d" (d2), "=&c" (d3), "=&a" (cmp) - : "0" (l), "1" (r), "3" (nr_key_bits) - : "r8", "r9", "cc", "memory"); - - return cmp; -} - #define I(_x) (*(out)++ = (_x)) #define I1(i0) I(i0) #define I2(i0, i1) (I1(i0), I(i1)) @@ -792,7 +774,7 @@ static u8 *compile_bkey_field(const struct bkey_format *format, u8 *out, bool *eax_zeroed) { unsigned bits = format->bits_per_field[field]; - u64 offset = format->field_offset[field]; + u64 offset = le64_to_cpu(format->field_offset[field]); unsigned i, byte, bit_offset, align, shl, shr; if (!bits && !offset) { @@ -1009,41 +991,6 @@ int bch2_compile_bkey_format(const struct bkey_format *format, void *_out) } #else -static inline int __bkey_cmp_bits(const u64 *l, const u64 *r, - unsigned nr_key_bits) -{ - u64 l_v, r_v; - - if (!nr_key_bits) - return 0; - - /* for big endian, skip past header */ - nr_key_bits += high_bit_offset; - l_v = *l & (~0ULL >> high_bit_offset); - r_v = *r & (~0ULL >> high_bit_offset); - - while (1) { - if (nr_key_bits < 64) { - l_v >>= 64 - nr_key_bits; - r_v >>= 64 - nr_key_bits; - nr_key_bits = 0; - } else { - nr_key_bits -= 64; - } - - if (l_v != r_v) - return l_v < r_v ? -1 : 1; - - if (!nr_key_bits) - return 0; - - l = next_word(l); - r = next_word(r); - - l_v = *l; - r_v = *r; - } -} #endif __pure @@ -1051,19 +998,7 @@ int __bch2_bkey_cmp_packed_format_checked(const struct bkey_packed *l, const struct bkey_packed *r, const struct btree *b) { - const struct bkey_format *f = &b->format; - int ret; - - EBUG_ON(!bkey_packed(l) || !bkey_packed(r)); - EBUG_ON(b->nr_key_bits != bkey_format_key_bits(f)); - - ret = __bkey_cmp_bits(high_word(f, l), - high_word(f, r), - b->nr_key_bits); - - EBUG_ON(ret != bkey_cmp(bkey_unpack_key_format_checked(b, l).p, - bkey_unpack_key_format_checked(b, r).p)); - return ret; + return __bch2_bkey_cmp_packed_format_checked_inlined(l, r, b); } __pure __flatten @@ -1071,34 +1006,15 @@ int __bch2_bkey_cmp_left_packed_format_checked(const struct btree *b, const struct bkey_packed *l, const struct bpos *r) { - return bkey_cmp(bkey_unpack_pos_format_checked(b, l), *r); + return bpos_cmp(bkey_unpack_pos_format_checked(b, l), *r); } __pure __flatten -int __bch2_bkey_cmp_packed(const struct bkey_packed *l, - const struct bkey_packed *r, - const struct btree *b) +int bch2_bkey_cmp_packed(const struct btree *b, + const struct bkey_packed *l, + const struct bkey_packed *r) { - int packed = bkey_lr_packed(l, r); - - if (likely(packed == BKEY_PACKED_BOTH)) - return __bch2_bkey_cmp_packed_format_checked(l, r, b); - - switch (packed) { - case BKEY_PACKED_NONE: - return bkey_cmp(((struct bkey *) l)->p, - ((struct bkey *) r)->p); - case BKEY_PACKED_LEFT: - return __bch2_bkey_cmp_left_packed_format_checked(b, - (struct bkey_packed *) l, - &((struct bkey *) r)->p); - case BKEY_PACKED_RIGHT: - return -__bch2_bkey_cmp_left_packed_format_checked(b, - (struct bkey_packed *) r, - &((struct bkey *) l)->p); - default: - unreachable(); - } + return bch2_bkey_cmp_packed_inlined(b, l, r); } __pure __flatten @@ -1109,7 +1025,7 @@ int __bch2_bkey_cmp_left_packed(const struct btree *b, const struct bkey *l_unpacked; return unlikely(l_unpacked = packed_to_bkey_c(l)) - ? bkey_cmp(l_unpacked->p, *r) + ? bpos_cmp(l_unpacked->p, *r) : __bch2_bkey_cmp_left_packed_format_checked(b, l, r); } @@ -1145,11 +1061,12 @@ void bch2_bkey_pack_test(void) struct bkey_packed p; struct bkey_format test_format = { - .key_u64s = 2, + .key_u64s = 3, .nr_fields = BKEY_NR_FIELDS, .bits_per_field = { 13, 64, + 32, }, };