X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Fbkey.c;h=ee7ba700e75f4ee3afbac3ab241c7d6d9b1278c3;hb=bafc817a3f33adbf2ff701bf8f6757aedb0a1458;hp=ed7ca5b0636d8efd98ff8c9fdcff36c99bc0cb06;hpb=6016d33b801a5fe13e86e5be3abf68ed166c0796;p=bcachefs-tools-debian diff --git a/libbcachefs/bkey.c b/libbcachefs/bkey.c index ed7ca5b..ee7ba70 100644 --- a/libbcachefs/bkey.c +++ b/libbcachefs/bkey.c @@ -2,6 +2,7 @@ #include "bcachefs.h" #include "bkey.h" +#include "bkey_cmp.h" #include "bkey_methods.h" #include "bset.h" #include "util.h" @@ -16,36 +17,49 @@ const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT; -struct bkey __bch2_bkey_unpack_key(const struct bkey_format *, - const struct bkey_packed *); - -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; @@ -57,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]; + struct printbuf buf = PRINTBUF; - bch2_bkey_to_text(&PBUF(buf1), unpacked); - bch2_bkey_to_text(&PBUF(buf2), &tmp); - bch2_to_binary(buf3, (void *) unpacked, 80); - bch2_to_binary(buf4, high_word(format, packed), 80); - - 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); } } @@ -201,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))) @@ -234,14 +262,6 @@ bool bch2_bkey_transform(const struct bkey_format *out_f, return true; } -#define bkey_fields() \ - x(BKEY_FIELD_INODE, p.inode) \ - x(BKEY_FIELD_OFFSET, p.offset) \ - x(BKEY_FIELD_SNAPSHOT, p.snapshot) \ - x(BKEY_FIELD_SIZE, size) \ - x(BKEY_FIELD_VERSION_HI, version.hi) \ - x(BKEY_FIELD_VERSION_LO, version.lo) - struct bkey __bch2_bkey_unpack_key(const struct bkey_format *format, const struct bkey_packed *in) { @@ -292,25 +312,17 @@ 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() #undef x - - /* - * Extents - we have to guarantee that if an extent is packed, a trimmed - * version will also pack: - */ - if (bkey_start_offset(in) < - le64_to_cpu(format->field_offset[BKEY_FIELD_OFFSET])) - return false; - pack_state_finish(&state, out); out->u64s = format->key_u64s + in->u64s - BKEY_U64s; out->format = KEY_FORMAT_LOCAL_BTREE; @@ -348,7 +360,7 @@ bool bch2_bkey_pack(struct bkey_packed *out, const struct bkey_i *in, memmove_u64s((u64 *) out + format->key_u64s, &in->v, bkey_val_u64s(&in->k)); - memcpy_u64s(out, &tmp, format->key_u64s); + memcpy_u64s_small(out, &tmp, format->key_u64s); return true; } @@ -411,7 +423,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; } @@ -439,12 +451,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]))) { @@ -468,18 +488,18 @@ enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out, le64_to_cpu(f->field_offset[BKEY_FIELD_INODE]))) return BKEY_PACK_POS_FAIL; - if (!set_inc_field_lossy(&state, BKEY_FIELD_INODE, in.inode)) { + if (unlikely(!set_inc_field_lossy(&state, BKEY_FIELD_INODE, in.inode))) { in.offset = KEY_OFFSET_MAX; in.snapshot = KEY_SNAPSHOT_MAX; exact = false; } - if (!set_inc_field_lossy(&state, BKEY_FIELD_OFFSET, in.offset)) { + if (unlikely(!set_inc_field_lossy(&state, BKEY_FIELD_OFFSET, in.offset))) { in.snapshot = KEY_SNAPSHOT_MAX; exact = false; } - if (!set_inc_field_lossy(&state, BKEY_FIELD_SNAPSHOT, in.snapshot)) + if (unlikely(!set_inc_field_lossy(&state, BKEY_FIELD_SNAPSHOT, in.snapshot))) exact = false; pack_state_finish(&state, out); @@ -516,24 +536,6 @@ void bch2_bkey_format_init(struct bkey_format_state *s) s->field_min[BKEY_FIELD_SIZE] = 0; } -static void __bkey_format_add(struct bkey_format_state *s, - unsigned field, u64 v) -{ - s->field_min[field] = min(s->field_min[field], v); - s->field_max[field] = max(s->field_max[field], v); -} - -/* - * Changes @format so that @k can be successfully packed with @format - */ -void bch2_bkey_format_add_key(struct bkey_format_state *s, const struct bkey *k) -{ -#define x(id, field) __bkey_format_add(s, id, k->field); - bkey_fields() -#undef x - __bkey_format_add(s, BKEY_FIELD_OFFSET, bkey_start_offset(k)); -} - void bch2_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p) { unsigned field = 0; @@ -551,7 +553,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); @@ -608,18 +615,22 @@ const char *bch2_bkey_format_validate(struct bkey_format *f) if (f->nr_fields != BKEY_NR_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) + if (packed_max + field_offset < packed_max || + packed_max + field_offset > unpacked_max) return "field too large"; - if (field_offset && - (f->bits_per_field[i] == 64 || - (field_offset + ((1ULL << f->bits_per_field[i]) - 1) < - field_offset))) - return "offset + bits overflow"; - bits += f->bits_per_field[i]; } @@ -713,51 +724,7 @@ unsigned bch2_bkey_ffs(const struct btree *b, const struct bkey_packed *k) return 0; } -#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; -} +#ifdef HAVE_BCACHEFS_COMPILED_UNPACK #define I(_x) (*(out)++ = (_x)) #define I1(i0) I(i0) @@ -989,40 +956,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 (!nr_key_bits || l_v != r_v) - break; - - l = next_word(l); - r = next_word(r); - - l_v = *l; - r_v = *r; - } - - return cmp_int(l_v, r_v); -} #endif __pure @@ -1030,19 +963,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_pos(b, l), - bkey_unpack_pos(b, r))); - return ret; + return __bch2_bkey_cmp_packed_format_checked_inlined(l, r, b); } __pure __flatten @@ -1050,34 +971,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 @@ -1088,7 +990,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); } @@ -1124,11 +1026,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, }, };