+// 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;
-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_base2_nbits(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;
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(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);
-
- 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);
}
}
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 */
struct bkey_packed *k)
{
EBUG_ON(state->p < k->_data);
- EBUG_ON(state->p >= k->_data + state->format->key_u64s);
+ EBUG_ON(state->p >= (u64 *) k->_data + state->format->key_u64s);
*state->p = state->w;
}
return v + offset;
}
+__always_inline
+static void __set_inc_field(struct pack_state *state, unsigned field, u64 v)
+{
+ unsigned bits = state->format->bits_per_field[field];
+
+ if (bits) {
+ if (bits > state->bits) {
+ bits -= state->bits;
+ /* avoid shift by 64 if bits is 64 - bits is never 0 here: */
+ state->w |= (v >> 1) >> (bits - 1);
+
+ *state->p = state->w;
+ state->p = next_word(state->p);
+ state->w = 0;
+ state->bits = 64;
+ }
+
+ state->bits -= bits;
+ state->w |= v << state->bits;
+ }
+}
+
__always_inline
static bool set_inc_field(struct pack_state *state, unsigned field, u64 v)
{
if (fls64(v) > bits)
return false;
- if (bits > state->bits) {
- bits -= state->bits;
- /* avoid shift by 64 if bits is 0 - bits is never 64 here: */
- state->w |= (v >> 1) >> (bits - 1);
-
- *state->p = state->w;
- state->p = next_word(state->p);
- state->w = 0;
- state->bits = 64;
- }
-
- state->bits -= bits;
- state->w |= v << state->bits;
-
+ __set_inc_field(state, field, v);
return true;
}
{
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)))
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)
{
/**
* bch2_bkey_pack_key -- pack just the key, not the value
+ * @out: packed result
+ * @in: key to pack
+ * @format: format of packed result
+ *
+ * Returns: true on success, false on failure
*/
bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in,
- const struct bkey_format *format)
+ 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) < 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;
/**
* bch2_bkey_unpack -- unpack the key and the value
+ * @b: btree node of @src key (for packed format)
+ * @dst: unpacked result
+ * @src: packed input
*/
void bch2_bkey_unpack(const struct btree *b, struct bkey_i *dst,
- const struct bkey_packed *src)
+ 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),
/**
* bch2_bkey_pack -- pack the key and the value
+ * @dst: packed result
+ * @src: unpacked input
+ * @format: format of packed result
+ *
+ * Returns: true on success, false on failure
*/
-bool bch2_bkey_pack(struct bkey_packed *out, const struct bkey_i *in,
- const struct bkey_format *format)
+bool bch2_bkey_pack(struct bkey_packed *dst, const struct bkey_i *src,
+ const struct bkey_format *format)
{
struct bkey_packed tmp;
- if (!bch2_bkey_pack_key(&tmp, &in->k, format))
+ if (!bch2_bkey_pack_key(&tmp, &src->k, format))
return false;
- memmove_u64s((u64 *) out + format->key_u64s,
- &in->v,
- bkey_val_u64s(&in->k));
- memcpy_u64s(out, &tmp, format->key_u64s);
+ memmove_u64s((u64 *) dst + format->key_u64s,
+ &src->v,
+ bkey_val_u64s(&src->k));
+ memcpy_u64s_small(dst, &tmp, format->key_u64s);
return true;
}
ret = false;
}
- if (bits > state->bits) {
- bits -= state->bits;
- state->w |= (v >> 1) >> (bits - 1);
-
- *state->p = state->w;
- state->p = next_word(state->p);
- state->w = 0;
- state->bits = 64;
- }
-
- state->bits -= bits;
- state->w |= v << state->bits;
-
+ __set_inc_field(state, field, v);
return ret;
}
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;
}
return false;
}
+
+static bool bkey_format_has_too_big_fields(const struct bkey_format *f)
+{
+ for (unsigned 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 (packed_max + field_offset < packed_max ||
+ packed_max + field_offset > unpacked_max)
+ return true;
+ }
+
+ return false;
+}
#endif
/*
{
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]))) {
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);
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) {
BUG_ON(bkey_cmp_left_packed(b, out, &orig) >= 0);
BUG_ON(bkey_packed_successor(&successor, b, *out) &&
- bkey_cmp_left_packed(b, &successor, &orig) < 0);
+ bkey_cmp_left_packed(b, &successor, &orig) < 0 &&
+ !bkey_format_has_too_big_fields(f));
}
#endif
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;
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);
/* allow for extent merging: */
if (ret.bits_per_field[BKEY_FIELD_SIZE]) {
- ret.bits_per_field[BKEY_FIELD_SIZE] += 4;
- bits += 4;
+ unsigned b = min(4U, 32U - ret.bits_per_field[BKEY_FIELD_SIZE]);
+
+ ret.bits_per_field[BKEY_FIELD_SIZE] += b;
+ bits += b;
}
ret.key_u64s = DIV_ROUND_UP(bits, 64);
}
}
- EBUG_ON(bch2_bkey_format_validate(&ret));
+#ifdef CONFIG_BCACHEFS_DEBUG
+ {
+ struct printbuf buf = PRINTBUF;
+
+ BUG_ON(bch2_bkey_format_invalid(NULL, &ret, 0, &buf));
+ printbuf_exit(&buf);
+ }
+#endif
return ret;
}
-const char *bch2_bkey_format_validate(struct bkey_format *f)
+int bch2_bkey_format_invalid(struct bch_fs *c,
+ struct bkey_format *f,
+ enum bkey_invalid_flags flags,
+ struct printbuf *err)
{
unsigned i, bits = KEY_PACKED_BITS_START;
- if (f->nr_fields != BKEY_NR_FIELDS)
- return "invalid format: incorrect number of fields";
+ if (f->nr_fields != BKEY_NR_FIELDS) {
+ prt_printf(err, "incorrect number of fields: got %u, should be %u",
+ f->nr_fields, BKEY_NR_FIELDS);
+ return -BCH_ERR_invalid;
+ }
+ /*
+ * Verify that the packed format can't represent fields larger than the
+ * unpacked format:
+ */
for (i = 0; i < f->nr_fields; i++) {
- 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 (!c || c->sb.version_min >= bcachefs_metadata_version_snapshot) {
+ 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 (packed_max + field_offset < packed_max ||
+ packed_max + field_offset > unpacked_max) {
+ prt_printf(err, "field %u too large: %llu + %llu > %llu",
+ i, packed_max, field_offset, unpacked_max);
+ return -BCH_ERR_invalid;
+ }
+ }
bits += f->bits_per_field[i];
}
- if (f->key_u64s != DIV_ROUND_UP(bits, 64))
- return "invalid format: incorrect key_u64s";
+ if (f->key_u64s != DIV_ROUND_UP(bits, 64)) {
+ prt_printf(err, "incorrect key_u64s: got %u, should be %u",
+ f->key_u64s, DIV_ROUND_UP(bits, 64));
+ return -BCH_ERR_invalid;
+ }
- return NULL;
+ return 0;
+}
+
+void bch2_bkey_format_to_text(struct printbuf *out, const struct bkey_format *f)
+{
+ prt_printf(out, "u64s %u fields ", f->key_u64s);
+
+ for (unsigned i = 0; i < ARRAY_SIZE(f->bits_per_field); i++) {
+ if (i)
+ prt_str(out, ", ");
+ prt_printf(out, "%u:%llu",
+ f->bits_per_field[i],
+ le64_to_cpu(f->field_offset[i]));
+ }
}
/*
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)
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) {
}
#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
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
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
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);
}
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,
},
};
projects / bcachefs-tools-debian / blobdiff