10 #define EBUG_ON(cond) BUG_ON(cond)
15 const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT;
17 struct bkey __bch2_bkey_unpack_key(const struct bkey_format *,
18 const struct bkey_packed *);
20 void bch2_to_binary(char *out, const u64 *p, unsigned nr_bits)
22 unsigned bit = high_bit_offset, done = 0;
26 if (done && !(done % 8))
28 *out++ = *p & (1ULL << (63 - bit)) ? '1' : '0';
31 if (done == nr_bits) {
42 #ifdef CONFIG_BCACHEFS_DEBUG
44 static void bch2_bkey_pack_verify(const struct bkey_packed *packed,
45 const struct bkey *unpacked,
46 const struct bkey_format *format)
50 BUG_ON(bkeyp_val_u64s(format, packed) !=
51 bkey_val_u64s(unpacked));
53 BUG_ON(packed->u64s < bkeyp_key_u64s(format, packed));
55 tmp = __bch2_bkey_unpack_key(format, packed);
57 if (memcmp(&tmp, unpacked, sizeof(struct bkey))) {
58 char buf1[160], buf2[160];
59 char buf3[160], buf4[160];
61 bch2_bkey_to_text(buf1, sizeof(buf1), unpacked);
62 bch2_bkey_to_text(buf2, sizeof(buf2), &tmp);
63 bch2_to_binary(buf3, (void *) unpacked, 80);
64 bch2_to_binary(buf4, high_word(format, packed), 80);
66 panic("keys differ: format u64s %u fields %u %u %u %u %u\n%s\n%s\n%s\n%s\n",
68 format->bits_per_field[0],
69 format->bits_per_field[1],
70 format->bits_per_field[2],
71 format->bits_per_field[3],
72 format->bits_per_field[4],
73 buf1, buf2, buf3, buf4);
78 static inline void bch2_bkey_pack_verify(const struct bkey_packed *packed,
79 const struct bkey *unpacked,
80 const struct bkey_format *format) {}
83 int bch2_bkey_to_text(char *buf, size_t size, const struct bkey *k)
85 char *out = buf, *end = buf + size;
87 #define p(...) (out += scnprintf(out, end - out, __VA_ARGS__))
89 p("u64s %u type %u %llu:%llu snap %u len %u ver %llu",
90 k->u64s, k->type, k->p.inode, k->p.offset,
91 k->p.snapshot, k->size, k->version.lo);
93 BUG_ON(bkey_packed(k));
96 case KEY_TYPE_DELETED:
99 case KEY_TYPE_DISCARD:
105 case KEY_TYPE_COOKIE:
115 const struct bkey_format *format;
116 unsigned bits; /* bits remaining in current word */
117 u64 w; /* current word */
118 u64 *p; /* pointer to next word */
122 static struct pack_state pack_state_init(const struct bkey_format *format,
123 struct bkey_packed *k)
125 u64 *p = high_word(format, k);
127 return (struct pack_state) {
129 .bits = 64 - high_bit_offset,
136 static void pack_state_finish(struct pack_state *state,
137 struct bkey_packed *k)
139 EBUG_ON(state->p < k->_data);
140 EBUG_ON(state->p >= k->_data + state->format->key_u64s);
142 *state->p = state->w;
145 struct unpack_state {
146 const struct bkey_format *format;
147 unsigned bits; /* bits remaining in current word */
148 u64 w; /* current word */
149 const u64 *p; /* pointer to next word */
153 static struct unpack_state unpack_state_init(const struct bkey_format *format,
154 const struct bkey_packed *k)
156 const u64 *p = high_word(format, k);
158 return (struct unpack_state) {
160 .bits = 64 - high_bit_offset,
161 .w = *p << high_bit_offset,
167 static u64 get_inc_field(struct unpack_state *state, unsigned field)
169 unsigned bits = state->format->bits_per_field[field];
170 u64 v = 0, offset = le64_to_cpu(state->format->field_offset[field]);
172 if (bits >= state->bits) {
173 v = state->w >> (64 - bits);
176 state->p = next_word(state->p);
177 state->w = *state->p;
181 /* avoid shift by 64 if bits is 0 - bits is never 64 here: */
182 v |= (state->w >> 1) >> (63 - bits);
190 static bool set_inc_field(struct pack_state *state, unsigned field, u64 v)
192 unsigned bits = state->format->bits_per_field[field];
193 u64 offset = le64_to_cpu(state->format->field_offset[field]);
203 if (bits > state->bits) {
205 /* avoid shift by 64 if bits is 0 - bits is never 64 here: */
206 state->w |= (v >> 1) >> (bits - 1);
208 *state->p = state->w;
209 state->p = next_word(state->p);
215 state->w |= v << state->bits;
221 * Note: does NOT set out->format (we don't know what it should be here!)
223 * Also: doesn't work on extents - it doesn't preserve the invariant that
224 * if k is packed bkey_start_pos(k) will successfully pack
226 static bool bch2_bkey_transform_key(const struct bkey_format *out_f,
227 struct bkey_packed *out,
228 const struct bkey_format *in_f,
229 const struct bkey_packed *in)
231 struct pack_state out_s = pack_state_init(out_f, out);
232 struct unpack_state in_s = unpack_state_init(in_f, in);
237 for (i = 0; i < BKEY_NR_FIELDS; i++)
238 if (!set_inc_field(&out_s, i, get_inc_field(&in_s, i)))
241 /* Can't happen because the val would be too big to unpack: */
242 EBUG_ON(in->u64s - in_f->key_u64s + out_f->key_u64s > U8_MAX);
244 pack_state_finish(&out_s, out);
245 out->u64s = out_f->key_u64s + in->u64s - in_f->key_u64s;
246 out->needs_whiteout = in->needs_whiteout;
247 out->type = in->type;
252 bool bch2_bkey_transform(const struct bkey_format *out_f,
253 struct bkey_packed *out,
254 const struct bkey_format *in_f,
255 const struct bkey_packed *in)
257 if (!bch2_bkey_transform_key(out_f, out, in_f, in))
260 memcpy_u64s((u64 *) out + out_f->key_u64s,
261 (u64 *) in + in_f->key_u64s,
262 (in->u64s - in_f->key_u64s));
266 #define bkey_fields() \
267 x(BKEY_FIELD_INODE, p.inode) \
268 x(BKEY_FIELD_OFFSET, p.offset) \
269 x(BKEY_FIELD_SNAPSHOT, p.snapshot) \
270 x(BKEY_FIELD_SIZE, size) \
271 x(BKEY_FIELD_VERSION_HI, version.hi) \
272 x(BKEY_FIELD_VERSION_LO, version.lo)
274 struct bkey __bch2_bkey_unpack_key(const struct bkey_format *format,
275 const struct bkey_packed *in)
277 struct unpack_state state = unpack_state_init(format, in);
280 EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
281 EBUG_ON(in->u64s < format->key_u64s);
282 EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);
283 EBUG_ON(in->u64s - format->key_u64s + BKEY_U64s > U8_MAX);
285 out.u64s = BKEY_U64s + in->u64s - format->key_u64s;
286 out.format = KEY_FORMAT_CURRENT;
287 out.needs_whiteout = in->needs_whiteout;
291 #define x(id, field) out.field = get_inc_field(&state, id);
298 #ifndef HAVE_BCACHEFS_COMPILED_UNPACK
299 struct bpos __bkey_unpack_pos(const struct bkey_format *format,
300 const struct bkey_packed *in)
302 struct unpack_state state = unpack_state_init(format, in);
305 EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
306 EBUG_ON(in->u64s < format->key_u64s);
307 EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);
309 out.inode = get_inc_field(&state, BKEY_FIELD_INODE);
310 out.offset = get_inc_field(&state, BKEY_FIELD_OFFSET);
311 out.snapshot = get_inc_field(&state, BKEY_FIELD_SNAPSHOT);
318 * bch2_bkey_pack_key -- pack just the key, not the value
320 bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in,
321 const struct bkey_format *format)
323 struct pack_state state = pack_state_init(format, out);
325 EBUG_ON((void *) in == (void *) out);
326 EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
327 EBUG_ON(in->format != KEY_FORMAT_CURRENT);
331 #define x(id, field) if (!set_inc_field(&state, id, in->field)) return false;
336 * Extents - we have to guarantee that if an extent is packed, a trimmed
337 * version will also pack:
339 if (bkey_start_offset(in) < format->field_offset[BKEY_FIELD_OFFSET])
342 pack_state_finish(&state, out);
343 out->u64s = format->key_u64s + in->u64s - BKEY_U64s;
344 out->format = KEY_FORMAT_LOCAL_BTREE;
345 out->needs_whiteout = in->needs_whiteout;
346 out->type = in->type;
348 bch2_bkey_pack_verify(out, in, format);
353 * bch2_bkey_unpack -- unpack the key and the value
355 void bch2_bkey_unpack(const struct btree *b, struct bkey_i *dst,
356 const struct bkey_packed *src)
358 dst->k = bkey_unpack_key(b, src);
361 bkeyp_val(&b->format, src),
362 bkeyp_val_u64s(&b->format, src));
366 * bch2_bkey_pack -- pack the key and the value
368 bool bch2_bkey_pack(struct bkey_packed *out, const struct bkey_i *in,
369 const struct bkey_format *format)
371 struct bkey_packed tmp;
373 if (!bch2_bkey_pack_key(&tmp, &in->k, format))
376 memmove_u64s((u64 *) out + format->key_u64s,
378 bkey_val_u64s(&in->k));
379 memcpy_u64s(out, &tmp, format->key_u64s);
385 static bool set_inc_field_lossy(struct pack_state *state, unsigned field, u64 v)
387 unsigned bits = state->format->bits_per_field[field];
388 u64 offset = le64_to_cpu(state->format->field_offset[field]);
394 if (fls64(v) > bits) {
395 v = ~(~0ULL << bits);
399 if (bits > state->bits) {
401 state->w |= (v >> 1) >> (bits - 1);
403 *state->p = state->w;
404 state->p = next_word(state->p);
410 state->w |= v << state->bits;
415 #ifdef CONFIG_BCACHEFS_DEBUG
416 static bool bkey_packed_successor(struct bkey_packed *out,
417 const struct btree *b,
418 struct bkey_packed k)
420 const struct bkey_format *f = &b->format;
421 unsigned nr_key_bits = b->nr_key_bits;
422 unsigned first_bit, offset;
425 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(f));
432 first_bit = high_bit_offset + nr_key_bits - 1;
433 p = nth_word(high_word(f, out), first_bit >> 6);
434 offset = 63 - (first_bit & 63);
436 while (nr_key_bits) {
437 unsigned bits = min(64 - offset, nr_key_bits);
438 u64 mask = (~0ULL >> (64 - bits)) << offset;
440 if ((*p & mask) != mask) {
441 *p += 1ULL << offset;
442 EBUG_ON(bkey_cmp_packed(b, out, &k) <= 0);
457 * Returns a packed key that compares <= in
459 * This is used in bset_search_tree(), where we need a packed pos in order to be
460 * able to compare against the keys in the auxiliary search tree - and it's
461 * legal to use a packed pos that isn't equivalent to the original pos,
462 * _provided_ it compares <= to the original pos.
464 enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out,
466 const struct btree *b)
468 const struct bkey_format *f = &b->format;
469 struct pack_state state = pack_state_init(f, out);
470 #ifdef CONFIG_BCACHEFS_DEBUG
471 struct bpos orig = in;
477 if (unlikely(in.snapshot <
478 le64_to_cpu(f->field_offset[BKEY_FIELD_SNAPSHOT]))) {
481 return BKEY_PACK_POS_FAIL;
482 in.snapshot = KEY_SNAPSHOT_MAX;
486 if (unlikely(in.offset <
487 le64_to_cpu(f->field_offset[BKEY_FIELD_OFFSET]))) {
489 return BKEY_PACK_POS_FAIL;
490 in.offset = KEY_OFFSET_MAX;
491 in.snapshot = KEY_SNAPSHOT_MAX;
495 if (unlikely(in.inode <
496 le64_to_cpu(f->field_offset[BKEY_FIELD_INODE])))
497 return BKEY_PACK_POS_FAIL;
499 if (!set_inc_field_lossy(&state, BKEY_FIELD_INODE, in.inode)) {
500 in.offset = KEY_OFFSET_MAX;
501 in.snapshot = KEY_SNAPSHOT_MAX;
505 if (!set_inc_field_lossy(&state, BKEY_FIELD_OFFSET, in.offset)) {
506 in.snapshot = KEY_SNAPSHOT_MAX;
510 if (!set_inc_field_lossy(&state, BKEY_FIELD_SNAPSHOT, in.snapshot))
513 pack_state_finish(&state, out);
514 out->u64s = f->key_u64s;
515 out->format = KEY_FORMAT_LOCAL_BTREE;
516 out->type = KEY_TYPE_DELETED;
518 #ifdef CONFIG_BCACHEFS_DEBUG
520 BUG_ON(bkey_cmp_left_packed(b, out, &orig));
522 struct bkey_packed successor;
524 BUG_ON(bkey_cmp_left_packed(b, out, &orig) >= 0);
525 BUG_ON(bkey_packed_successor(&successor, b, *out) &&
526 bkey_cmp_left_packed(b, &successor, &orig) < 0);
530 return exact ? BKEY_PACK_POS_EXACT : BKEY_PACK_POS_SMALLER;
533 void bch2_bkey_format_init(struct bkey_format_state *s)
537 for (i = 0; i < ARRAY_SIZE(s->field_min); i++)
538 s->field_min[i] = U64_MAX;
540 for (i = 0; i < ARRAY_SIZE(s->field_max); i++)
543 /* Make sure we can store a size of 0: */
544 s->field_min[BKEY_FIELD_SIZE] = 0;
547 static void __bkey_format_add(struct bkey_format_state *s,
548 unsigned field, u64 v)
550 s->field_min[field] = min(s->field_min[field], v);
551 s->field_max[field] = max(s->field_max[field], v);
555 * Changes @format so that @k can be successfully packed with @format
557 void bch2_bkey_format_add_key(struct bkey_format_state *s, const struct bkey *k)
559 #define x(id, field) __bkey_format_add(s, id, k->field);
562 __bkey_format_add(s, BKEY_FIELD_OFFSET, bkey_start_offset(k));
565 void bch2_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p)
569 __bkey_format_add(s, field++, p.inode);
570 __bkey_format_add(s, field++, p.offset);
571 __bkey_format_add(s, field++, p.snapshot);
575 * We don't want it to be possible for the packed format to represent fields
576 * bigger than a u64... that will cause confusion and issues (like with
577 * bkey_packed_successor())
579 static void set_format_field(struct bkey_format *f, enum bch_bkey_fields i,
580 unsigned bits, u64 offset)
582 offset = bits == 64 ? 0 : min(offset, U64_MAX - ((1ULL << bits) - 1));
584 f->bits_per_field[i] = bits;
585 f->field_offset[i] = cpu_to_le64(offset);
588 struct bkey_format bch2_bkey_format_done(struct bkey_format_state *s)
590 unsigned i, bits = KEY_PACKED_BITS_START;
591 struct bkey_format ret = {
592 .nr_fields = BKEY_NR_FIELDS,
595 for (i = 0; i < ARRAY_SIZE(s->field_min); i++) {
596 s->field_min[i] = min(s->field_min[i], s->field_max[i]);
598 set_format_field(&ret, i,
599 fls64(s->field_max[i] - s->field_min[i]),
602 bits += ret.bits_per_field[i];
605 /* allow for extent merging: */
606 if (ret.bits_per_field[BKEY_FIELD_SIZE]) {
607 ret.bits_per_field[BKEY_FIELD_SIZE] += 4;
611 ret.key_u64s = DIV_ROUND_UP(bits, 64);
613 /* if we have enough spare bits, round fields up to nearest byte */
614 bits = ret.key_u64s * 64 - bits;
616 for (i = 0; i < ARRAY_SIZE(ret.bits_per_field); i++) {
617 unsigned r = round_up(ret.bits_per_field[i], 8) -
618 ret.bits_per_field[i];
621 set_format_field(&ret, i,
622 ret.bits_per_field[i] + r,
623 le64_to_cpu(ret.field_offset[i]));
628 EBUG_ON(bch2_bkey_format_validate(&ret));
632 const char *bch2_bkey_format_validate(struct bkey_format *f)
634 unsigned i, bits = KEY_PACKED_BITS_START;
636 if (f->nr_fields != BKEY_NR_FIELDS)
637 return "incorrect number of fields";
639 for (i = 0; i < f->nr_fields; i++) {
640 u64 field_offset = le64_to_cpu(f->field_offset[i]);
642 if (f->bits_per_field[i] > 64)
643 return "field too large";
646 (f->bits_per_field[i] == 64 ||
647 (field_offset + ((1ULL << f->bits_per_field[i]) - 1) <
649 return "offset + bits overflow";
651 bits += f->bits_per_field[i];
654 if (f->key_u64s != DIV_ROUND_UP(bits, 64))
655 return "incorrect key_u64s";
661 * Most significant differing bit
662 * Bits are indexed from 0 - return is [0, nr_key_bits)
665 unsigned bch2_bkey_greatest_differing_bit(const struct btree *b,
666 const struct bkey_packed *l_k,
667 const struct bkey_packed *r_k)
669 const u64 *l = high_word(&b->format, l_k);
670 const u64 *r = high_word(&b->format, r_k);
671 unsigned nr_key_bits = b->nr_key_bits;
672 unsigned word_bits = 64 - high_bit_offset;
675 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(&b->format));
677 /* for big endian, skip past header */
678 l_v = *l & (~0ULL >> high_bit_offset);
679 r_v = *r & (~0ULL >> high_bit_offset);
681 while (nr_key_bits) {
682 if (nr_key_bits < word_bits) {
683 l_v >>= word_bits - nr_key_bits;
684 r_v >>= word_bits - nr_key_bits;
687 nr_key_bits -= word_bits;
691 return fls64(l_v ^ r_v) - 1 + nr_key_bits;
706 * Bits are indexed from 0 - return is [0, nr_key_bits)
709 unsigned bch2_bkey_ffs(const struct btree *b, const struct bkey_packed *k)
711 const u64 *p = high_word(&b->format, k);
712 unsigned nr_key_bits = b->nr_key_bits;
713 unsigned ret = 0, offset;
715 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(&b->format));
717 offset = nr_key_bits;
718 while (offset > 64) {
723 offset = 64 - offset;
725 while (nr_key_bits) {
726 unsigned bits = nr_key_bits + offset < 64
730 u64 mask = (~0ULL >> (64 - bits)) << offset;
733 return ret + __ffs64(*p & mask) - offset;
746 static inline int __bkey_cmp_bits(const u64 *l, const u64 *r,
747 unsigned nr_key_bits)
752 /* we shouldn't need asm for this, but gcc is being retarded: */
754 asm(".intel_syntax noprefix;"
766 "lea rdi, [rdi - 8];"
767 "lea rsi, [rsi - 8];"
782 ".att_syntax prefix;"
783 : "=&D" (d0), "=&S" (d1), "=&d" (d2), "=&c" (d3), "=&a" (cmp)
784 : "0" (l), "1" (r), "3" (nr_key_bits)
785 : "r8", "r9", "cc", "memory");
790 #define I(_x) (*(out)++ = (_x))
792 #define I2(i0, i1) (I1(i0), I(i1))
793 #define I3(i0, i1, i2) (I2(i0, i1), I(i2))
794 #define I4(i0, i1, i2, i3) (I3(i0, i1, i2), I(i3))
795 #define I5(i0, i1, i2, i3, i4) (I4(i0, i1, i2, i3), I(i4))
797 static u8 *compile_bkey_field(const struct bkey_format *format, u8 *out,
798 enum bch_bkey_fields field,
799 unsigned dst_offset, unsigned dst_size,
802 unsigned bits = format->bits_per_field[field];
803 u64 offset = format->field_offset[field];
804 unsigned i, byte, bit_offset, align, shl, shr;
806 if (!bits && !offset) {
817 /* just return offset: */
821 if (offset > S32_MAX) {
822 /* mov [rdi + dst_offset], offset */
823 I3(0xc7, 0x47, dst_offset);
824 memcpy(out, &offset, 4);
827 I3(0xc7, 0x47, dst_offset + 4);
828 memcpy(out, (void *) &offset + 4, 4);
831 /* mov [rdi + dst_offset], offset */
833 I4(0x48, 0xc7, 0x47, dst_offset);
834 memcpy(out, &offset, 4);
839 /* mov [rdi + dst_offset], offset */
840 I3(0xc7, 0x47, dst_offset);
841 memcpy(out, &offset, 4);
851 bit_offset = format->key_u64s * 64;
852 for (i = 0; i <= field; i++)
853 bit_offset -= format->bits_per_field[i];
855 byte = bit_offset / 8;
856 bit_offset -= byte * 8;
860 if (bit_offset == 0 && bits == 8) {
861 /* movzx eax, BYTE PTR [rsi + imm8] */
862 I4(0x0f, 0xb6, 0x46, byte);
863 } else if (bit_offset == 0 && bits == 16) {
864 /* movzx eax, WORD PTR [rsi + imm8] */
865 I4(0x0f, 0xb7, 0x46, byte);
866 } else if (bit_offset + bits <= 32) {
867 align = min(4 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 3);
869 bit_offset += align * 8;
871 BUG_ON(bit_offset + bits > 32);
873 /* mov eax, [rsi + imm8] */
874 I3(0x8b, 0x46, byte);
878 I3(0xc1, 0xe8, bit_offset);
881 if (bit_offset + bits < 32) {
882 unsigned mask = ~0U >> (32 - bits);
886 memcpy(out, &mask, 4);
889 } else if (bit_offset + bits <= 64) {
890 align = min(8 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 7);
892 bit_offset += align * 8;
894 BUG_ON(bit_offset + bits > 64);
896 /* mov rax, [rsi + imm8] */
897 I4(0x48, 0x8b, 0x46, byte);
899 shl = 64 - bit_offset - bits;
900 shr = bit_offset + shl;
904 I4(0x48, 0xc1, 0xe0, shl);
909 I4(0x48, 0xc1, 0xe8, shr);
912 align = min(4 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 3);
914 bit_offset += align * 8;
916 BUG_ON(bit_offset + bits > 96);
918 /* mov rax, [rsi + byte] */
919 I4(0x48, 0x8b, 0x46, byte);
921 /* mov edx, [rsi + byte + 8] */
922 I3(0x8b, 0x56, byte + 8);
924 /* bits from next word: */
925 shr = bit_offset + bits - 64;
926 BUG_ON(shr > bit_offset);
928 /* shr rax, bit_offset */
929 I4(0x48, 0xc1, 0xe8, shr);
932 I4(0x48, 0xc1, 0xe2, 64 - shr);
935 I3(0x48, 0x09, 0xd0);
937 shr = bit_offset - shr;
941 I4(0x48, 0xc1, 0xe8, shr);
946 if (offset > S32_MAX) {
949 memcpy(out, &offset, 8);
952 I3(0x48, 0x01, 0xd0);
953 } else if (offset + (~0ULL >> (64 - bits)) > U32_MAX) {
956 memcpy(out, &offset, 4);
961 memcpy(out, &offset, 4);
967 /* mov [rdi + dst_offset], rax */
968 I4(0x48, 0x89, 0x47, dst_offset);
971 /* mov [rdi + dst_offset], eax */
972 I3(0x89, 0x47, dst_offset);
981 int bch2_compile_bkey_format(const struct bkey_format *format, void *_out)
983 bool eax_zeroed = false;
987 * rdi: dst - unpacked key
988 * rsi: src - packed key
991 /* k->u64s, k->format, k->type */
996 /* add eax, BKEY_U64s - format->key_u64s */
997 I5(0x05, BKEY_U64s - format->key_u64s, KEY_FORMAT_CURRENT, 0, 0);
999 /* and eax, imm32: mask out k->pad: */
1000 I5(0x25, 0xff, 0xff, 0xff, 0);
1002 /* mov [rdi], eax */
1005 #define x(id, field) \
1006 out = compile_bkey_field(format, out, id, \
1007 offsetof(struct bkey, field), \
1008 sizeof(((struct bkey *) NULL)->field), \
1016 return (void *) out - _out;
1020 static inline int __bkey_cmp_bits(const u64 *l, const u64 *r,
1021 unsigned nr_key_bits)
1028 /* for big endian, skip past header */
1029 nr_key_bits += high_bit_offset;
1030 l_v = *l & (~0ULL >> high_bit_offset);
1031 r_v = *r & (~0ULL >> high_bit_offset);
1034 if (nr_key_bits < 64) {
1035 l_v >>= 64 - nr_key_bits;
1036 r_v >>= 64 - nr_key_bits;
1043 return l_v < r_v ? -1 : 1;
1058 int __bch2_bkey_cmp_packed_format_checked(const struct bkey_packed *l,
1059 const struct bkey_packed *r,
1060 const struct btree *b)
1062 const struct bkey_format *f = &b->format;
1065 EBUG_ON(!bkey_packed(l) || !bkey_packed(r));
1066 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(f));
1068 ret = __bkey_cmp_bits(high_word(f, l),
1072 EBUG_ON(ret != bkey_cmp(bkey_unpack_key_format_checked(b, l).p,
1073 bkey_unpack_key_format_checked(b, r).p));
1078 int __bch2_bkey_cmp_left_packed_format_checked(const struct btree *b,
1079 const struct bkey_packed *l,
1080 const struct bpos *r)
1082 return bkey_cmp(bkey_unpack_pos_format_checked(b, l), *r);
1086 int __bch2_bkey_cmp_packed(const struct bkey_packed *l,
1087 const struct bkey_packed *r,
1088 const struct btree *b)
1090 int packed = bkey_lr_packed(l, r);
1092 if (likely(packed == BKEY_PACKED_BOTH))
1093 return __bch2_bkey_cmp_packed_format_checked(l, r, b);
1096 case BKEY_PACKED_NONE:
1097 return bkey_cmp(((struct bkey *) l)->p,
1098 ((struct bkey *) r)->p);
1099 case BKEY_PACKED_LEFT:
1100 return __bch2_bkey_cmp_left_packed_format_checked(b,
1101 (struct bkey_packed *) l,
1102 &((struct bkey *) r)->p);
1103 case BKEY_PACKED_RIGHT:
1104 return -__bch2_bkey_cmp_left_packed_format_checked(b,
1105 (struct bkey_packed *) r,
1106 &((struct bkey *) l)->p);
1113 int __bch2_bkey_cmp_left_packed(const struct btree *b,
1114 const struct bkey_packed *l,
1115 const struct bpos *r)
1117 const struct bkey *l_unpacked;
1119 return unlikely(l_unpacked = packed_to_bkey_c(l))
1120 ? bkey_cmp(l_unpacked->p, *r)
1121 : __bch2_bkey_cmp_left_packed_format_checked(b, l, r);
1124 void bch2_bpos_swab(struct bpos *p)
1127 u8 *h = ((u8 *) &p[1]) - 1;
1136 void bch2_bkey_swab_key(const struct bkey_format *_f, struct bkey_packed *k)
1138 const struct bkey_format *f = bkey_packed(k) ? _f : &bch2_bkey_format_current;
1139 u8 *l = k->key_start;
1140 u8 *h = (u8 *) (k->_data + f->key_u64s) - 1;
1149 #ifdef CONFIG_BCACHEFS_DEBUG
1150 void bch2_bkey_pack_test(void)
1152 struct bkey t = KEY(4134ULL, 1250629070527416633ULL, 0);
1153 struct bkey_packed p;
1155 struct bkey_format test_format = {
1157 .nr_fields = BKEY_NR_FIELDS,
1164 struct unpack_state in_s =
1165 unpack_state_init(&bch2_bkey_format_current, (void *) &t);
1166 struct pack_state out_s = pack_state_init(&test_format, &p);
1169 for (i = 0; i < out_s.format->nr_fields; i++) {
1170 u64 a, v = get_inc_field(&in_s, i);
1173 #define x(id, field) case id: a = t.field; break;
1181 panic("got %llu actual %llu i %u\n", v, a, i);
1183 if (!set_inc_field(&out_s, i, v))
1184 panic("failed at %u\n", i);
1187 BUG_ON(!bch2_bkey_pack_key(&p, &t, &test_format));