1118 lines · c
1// SPDX-License-Identifier: GPL-2.02 3#include "bcachefs.h"4#include "bkey.h"5#include "bkey_cmp.h"6#include "bkey_methods.h"7#include "bset.h"8#include "util.h"9 10const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT;11 12void bch2_bkey_packed_to_binary_text(struct printbuf *out,13 const struct bkey_format *f,14 const struct bkey_packed *k)15{16 const u64 *p = high_word(f, k);17 unsigned word_bits = 64 - high_bit_offset;18 unsigned nr_key_bits = bkey_format_key_bits(f) + high_bit_offset;19 u64 v = *p & (~0ULL >> high_bit_offset);20 21 if (!nr_key_bits) {22 prt_str(out, "(empty)");23 return;24 }25 26 while (1) {27 unsigned next_key_bits = nr_key_bits;28 29 if (nr_key_bits < 64) {30 v >>= 64 - nr_key_bits;31 next_key_bits = 0;32 } else {33 next_key_bits -= 64;34 }35 36 bch2_prt_u64_base2_nbits(out, v, min(word_bits, nr_key_bits));37 38 if (!next_key_bits)39 break;40 41 prt_char(out, ' ');42 43 p = next_word(p);44 v = *p;45 word_bits = 64;46 nr_key_bits = next_key_bits;47 }48}49 50#ifdef CONFIG_BCACHEFS_DEBUG51 52static void bch2_bkey_pack_verify(const struct bkey_packed *packed,53 const struct bkey *unpacked,54 const struct bkey_format *format)55{56 struct bkey tmp;57 58 BUG_ON(bkeyp_val_u64s(format, packed) !=59 bkey_val_u64s(unpacked));60 61 BUG_ON(packed->u64s < bkeyp_key_u64s(format, packed));62 63 tmp = __bch2_bkey_unpack_key(format, packed);64 65 if (memcmp(&tmp, unpacked, sizeof(struct bkey))) {66 struct printbuf buf = PRINTBUF;67 68 prt_printf(&buf, "keys differ: format u64s %u fields %u %u %u %u %u\n",69 format->key_u64s,70 format->bits_per_field[0],71 format->bits_per_field[1],72 format->bits_per_field[2],73 format->bits_per_field[3],74 format->bits_per_field[4]);75 76 prt_printf(&buf, "compiled unpack: ");77 bch2_bkey_to_text(&buf, unpacked);78 prt_newline(&buf);79 80 prt_printf(&buf, "c unpack: ");81 bch2_bkey_to_text(&buf, &tmp);82 prt_newline(&buf);83 84 prt_printf(&buf, "compiled unpack: ");85 bch2_bkey_packed_to_binary_text(&buf, &bch2_bkey_format_current,86 (struct bkey_packed *) unpacked);87 prt_newline(&buf);88 89 prt_printf(&buf, "c unpack: ");90 bch2_bkey_packed_to_binary_text(&buf, &bch2_bkey_format_current,91 (struct bkey_packed *) &tmp);92 prt_newline(&buf);93 94 panic("%s", buf.buf);95 }96}97 98#else99static inline void bch2_bkey_pack_verify(const struct bkey_packed *packed,100 const struct bkey *unpacked,101 const struct bkey_format *format) {}102#endif103 104struct pack_state {105 const struct bkey_format *format;106 unsigned bits; /* bits remaining in current word */107 u64 w; /* current word */108 u64 *p; /* pointer to next word */109};110 111__always_inline112static struct pack_state pack_state_init(const struct bkey_format *format,113 struct bkey_packed *k)114{115 u64 *p = high_word(format, k);116 117 return (struct pack_state) {118 .format = format,119 .bits = 64 - high_bit_offset,120 .w = 0,121 .p = p,122 };123}124 125__always_inline126static void pack_state_finish(struct pack_state *state,127 struct bkey_packed *k)128{129 EBUG_ON(state->p < k->_data);130 EBUG_ON(state->p >= (u64 *) k->_data + state->format->key_u64s);131 132 *state->p = state->w;133}134 135struct unpack_state {136 const struct bkey_format *format;137 unsigned bits; /* bits remaining in current word */138 u64 w; /* current word */139 const u64 *p; /* pointer to next word */140};141 142__always_inline143static struct unpack_state unpack_state_init(const struct bkey_format *format,144 const struct bkey_packed *k)145{146 const u64 *p = high_word(format, k);147 148 return (struct unpack_state) {149 .format = format,150 .bits = 64 - high_bit_offset,151 .w = *p << high_bit_offset,152 .p = p,153 };154}155 156__always_inline157static u64 get_inc_field(struct unpack_state *state, unsigned field)158{159 unsigned bits = state->format->bits_per_field[field];160 u64 v = 0, offset = le64_to_cpu(state->format->field_offset[field]);161 162 if (bits >= state->bits) {163 v = state->w >> (64 - bits);164 bits -= state->bits;165 166 state->p = next_word(state->p);167 state->w = *state->p;168 state->bits = 64;169 }170 171 /* avoid shift by 64 if bits is 0 - bits is never 64 here: */172 v |= (state->w >> 1) >> (63 - bits);173 state->w <<= bits;174 state->bits -= bits;175 176 return v + offset;177}178 179__always_inline180static void __set_inc_field(struct pack_state *state, unsigned field, u64 v)181{182 unsigned bits = state->format->bits_per_field[field];183 184 if (bits) {185 if (bits > state->bits) {186 bits -= state->bits;187 /* avoid shift by 64 if bits is 64 - bits is never 0 here: */188 state->w |= (v >> 1) >> (bits - 1);189 190 *state->p = state->w;191 state->p = next_word(state->p);192 state->w = 0;193 state->bits = 64;194 }195 196 state->bits -= bits;197 state->w |= v << state->bits;198 }199}200 201__always_inline202static bool set_inc_field(struct pack_state *state, unsigned field, u64 v)203{204 unsigned bits = state->format->bits_per_field[field];205 u64 offset = le64_to_cpu(state->format->field_offset[field]);206 207 if (v < offset)208 return false;209 210 v -= offset;211 212 if (fls64(v) > bits)213 return false;214 215 __set_inc_field(state, field, v);216 return true;217}218 219/*220 * Note: does NOT set out->format (we don't know what it should be here!)221 *222 * Also: doesn't work on extents - it doesn't preserve the invariant that223 * if k is packed bkey_start_pos(k) will successfully pack224 */225static bool bch2_bkey_transform_key(const struct bkey_format *out_f,226 struct bkey_packed *out,227 const struct bkey_format *in_f,228 const struct bkey_packed *in)229{230 struct pack_state out_s = pack_state_init(out_f, out);231 struct unpack_state in_s = unpack_state_init(in_f, in);232 u64 *w = out->_data;233 unsigned i;234 235 *w = 0;236 237 for (i = 0; i < BKEY_NR_FIELDS; i++)238 if (!set_inc_field(&out_s, i, get_inc_field(&in_s, i)))239 return false;240 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);243 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;248 249 return true;250}251 252bool 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)256{257 if (!bch2_bkey_transform_key(out_f, out, in_f, in))258 return false;259 260 memcpy_u64s((u64 *) out + out_f->key_u64s,261 (u64 *) in + in_f->key_u64s,262 (in->u64s - in_f->key_u64s));263 return true;264}265 266struct bkey __bch2_bkey_unpack_key(const struct bkey_format *format,267 const struct bkey_packed *in)268{269 struct unpack_state state = unpack_state_init(format, in);270 struct bkey out;271 272 EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);273 EBUG_ON(in->u64s < format->key_u64s);274 EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);275 EBUG_ON(in->u64s - format->key_u64s + BKEY_U64s > U8_MAX);276 277 out.u64s = BKEY_U64s + in->u64s - format->key_u64s;278 out.format = KEY_FORMAT_CURRENT;279 out.needs_whiteout = in->needs_whiteout;280 out.type = in->type;281 out.pad[0] = 0;282 283#define x(id, field) out.field = get_inc_field(&state, id);284 bkey_fields()285#undef x286 287 return out;288}289 290#ifndef HAVE_BCACHEFS_COMPILED_UNPACK291struct bpos __bkey_unpack_pos(const struct bkey_format *format,292 const struct bkey_packed *in)293{294 struct unpack_state state = unpack_state_init(format, in);295 struct bpos out;296 297 EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);298 EBUG_ON(in->u64s < format->key_u64s);299 EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);300 301 out.inode = get_inc_field(&state, BKEY_FIELD_INODE);302 out.offset = get_inc_field(&state, BKEY_FIELD_OFFSET);303 out.snapshot = get_inc_field(&state, BKEY_FIELD_SNAPSHOT);304 305 return out;306}307#endif308 309/**310 * bch2_bkey_pack_key -- pack just the key, not the value311 * @out: packed result312 * @in: key to pack313 * @format: format of packed result314 *315 * Returns: true on success, false on failure316 */317bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in,318 const struct bkey_format *format)319{320 struct pack_state state = pack_state_init(format, out);321 u64 *w = out->_data;322 323 EBUG_ON((void *) in == (void *) out);324 EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);325 EBUG_ON(in->format != KEY_FORMAT_CURRENT);326 327 *w = 0;328 329#define x(id, field) if (!set_inc_field(&state, id, in->field)) return false;330 bkey_fields()331#undef x332 pack_state_finish(&state, out);333 out->u64s = format->key_u64s + in->u64s - BKEY_U64s;334 out->format = KEY_FORMAT_LOCAL_BTREE;335 out->needs_whiteout = in->needs_whiteout;336 out->type = in->type;337 338 bch2_bkey_pack_verify(out, in, format);339 return true;340}341 342/**343 * bch2_bkey_unpack -- unpack the key and the value344 * @b: btree node of @src key (for packed format)345 * @dst: unpacked result346 * @src: packed input347 */348void bch2_bkey_unpack(const struct btree *b, struct bkey_i *dst,349 const struct bkey_packed *src)350{351 __bkey_unpack_key(b, &dst->k, src);352 353 memcpy_u64s(&dst->v,354 bkeyp_val(&b->format, src),355 bkeyp_val_u64s(&b->format, src));356}357 358/**359 * bch2_bkey_pack -- pack the key and the value360 * @dst: packed result361 * @src: unpacked input362 * @format: format of packed result363 *364 * Returns: true on success, false on failure365 */366bool bch2_bkey_pack(struct bkey_packed *dst, const struct bkey_i *src,367 const struct bkey_format *format)368{369 struct bkey_packed tmp;370 371 if (!bch2_bkey_pack_key(&tmp, &src->k, format))372 return false;373 374 memmove_u64s((u64 *) dst + format->key_u64s,375 &src->v,376 bkey_val_u64s(&src->k));377 memcpy_u64s_small(dst, &tmp, format->key_u64s);378 379 return true;380}381 382__always_inline383static bool set_inc_field_lossy(struct pack_state *state, unsigned field, u64 v)384{385 unsigned bits = state->format->bits_per_field[field];386 u64 offset = le64_to_cpu(state->format->field_offset[field]);387 bool ret = true;388 389 EBUG_ON(v < offset);390 v -= offset;391 392 if (fls64(v) > bits) {393 v = ~(~0ULL << bits);394 ret = false;395 }396 397 __set_inc_field(state, field, v);398 return ret;399}400 401#ifdef CONFIG_BCACHEFS_DEBUG402static bool bkey_packed_successor(struct bkey_packed *out,403 const struct btree *b,404 struct bkey_packed k)405{406 const struct bkey_format *f = &b->format;407 unsigned nr_key_bits = b->nr_key_bits;408 unsigned first_bit, offset;409 u64 *p;410 411 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(f));412 413 if (!nr_key_bits)414 return false;415 416 *out = k;417 418 first_bit = high_bit_offset + nr_key_bits - 1;419 p = nth_word(high_word(f, out), first_bit >> 6);420 offset = 63 - (first_bit & 63);421 422 while (nr_key_bits) {423 unsigned bits = min(64 - offset, nr_key_bits);424 u64 mask = (~0ULL >> (64 - bits)) << offset;425 426 if ((*p & mask) != mask) {427 *p += 1ULL << offset;428 EBUG_ON(bch2_bkey_cmp_packed(b, out, &k) <= 0);429 return true;430 }431 432 *p &= ~mask;433 p = prev_word(p);434 nr_key_bits -= bits;435 offset = 0;436 }437 438 return false;439}440 441static bool bkey_format_has_too_big_fields(const struct bkey_format *f)442{443 for (unsigned i = 0; i < f->nr_fields; i++) {444 unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i];445 u64 unpacked_max = ~((~0ULL << 1) << (unpacked_bits - 1));446 u64 packed_max = f->bits_per_field[i]447 ? ~((~0ULL << 1) << (f->bits_per_field[i] - 1))448 : 0;449 u64 field_offset = le64_to_cpu(f->field_offset[i]);450 451 if (packed_max + field_offset < packed_max ||452 packed_max + field_offset > unpacked_max)453 return true;454 }455 456 return false;457}458#endif459 460/*461 * Returns a packed key that compares <= in462 *463 * This is used in bset_search_tree(), where we need a packed pos in order to be464 * able to compare against the keys in the auxiliary search tree - and it's465 * legal to use a packed pos that isn't equivalent to the original pos,466 * _provided_ it compares <= to the original pos.467 */468enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out,469 struct bpos in,470 const struct btree *b)471{472 const struct bkey_format *f = &b->format;473 struct pack_state state = pack_state_init(f, out);474 u64 *w = out->_data;475#ifdef CONFIG_BCACHEFS_DEBUG476 struct bpos orig = in;477#endif478 bool exact = true;479 unsigned i;480 481 /*482 * bch2_bkey_pack_key() will write to all of f->key_u64s, minus the 3483 * byte header, but pack_pos() won't if the len/version fields are big484 * enough - we need to make sure to zero them out:485 */486 for (i = 0; i < f->key_u64s; i++)487 w[i] = 0;488 489 if (unlikely(in.snapshot <490 le64_to_cpu(f->field_offset[BKEY_FIELD_SNAPSHOT]))) {491 if (!in.offset-- &&492 !in.inode--)493 return BKEY_PACK_POS_FAIL;494 in.snapshot = KEY_SNAPSHOT_MAX;495 exact = false;496 }497 498 if (unlikely(in.offset <499 le64_to_cpu(f->field_offset[BKEY_FIELD_OFFSET]))) {500 if (!in.inode--)501 return BKEY_PACK_POS_FAIL;502 in.offset = KEY_OFFSET_MAX;503 in.snapshot = KEY_SNAPSHOT_MAX;504 exact = false;505 }506 507 if (unlikely(in.inode <508 le64_to_cpu(f->field_offset[BKEY_FIELD_INODE])))509 return BKEY_PACK_POS_FAIL;510 511 if (unlikely(!set_inc_field_lossy(&state, BKEY_FIELD_INODE, in.inode))) {512 in.offset = KEY_OFFSET_MAX;513 in.snapshot = KEY_SNAPSHOT_MAX;514 exact = false;515 }516 517 if (unlikely(!set_inc_field_lossy(&state, BKEY_FIELD_OFFSET, in.offset))) {518 in.snapshot = KEY_SNAPSHOT_MAX;519 exact = false;520 }521 522 if (unlikely(!set_inc_field_lossy(&state, BKEY_FIELD_SNAPSHOT, in.snapshot)))523 exact = false;524 525 pack_state_finish(&state, out);526 out->u64s = f->key_u64s;527 out->format = KEY_FORMAT_LOCAL_BTREE;528 out->type = KEY_TYPE_deleted;529 530#ifdef CONFIG_BCACHEFS_DEBUG531 if (exact) {532 BUG_ON(bkey_cmp_left_packed(b, out, &orig));533 } else {534 struct bkey_packed successor;535 536 BUG_ON(bkey_cmp_left_packed(b, out, &orig) >= 0);537 BUG_ON(bkey_packed_successor(&successor, b, *out) &&538 bkey_cmp_left_packed(b, &successor, &orig) < 0 &&539 !bkey_format_has_too_big_fields(f));540 }541#endif542 543 return exact ? BKEY_PACK_POS_EXACT : BKEY_PACK_POS_SMALLER;544}545 546void bch2_bkey_format_init(struct bkey_format_state *s)547{548 unsigned i;549 550 for (i = 0; i < ARRAY_SIZE(s->field_min); i++)551 s->field_min[i] = U64_MAX;552 553 for (i = 0; i < ARRAY_SIZE(s->field_max); i++)554 s->field_max[i] = 0;555 556 /* Make sure we can store a size of 0: */557 s->field_min[BKEY_FIELD_SIZE] = 0;558}559 560void bch2_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p)561{562 unsigned field = 0;563 564 __bkey_format_add(s, field++, p.inode);565 __bkey_format_add(s, field++, p.offset);566 __bkey_format_add(s, field++, p.snapshot);567}568 569/*570 * We don't want it to be possible for the packed format to represent fields571 * bigger than a u64... that will cause confusion and issues (like with572 * bkey_packed_successor())573 */574static void set_format_field(struct bkey_format *f, enum bch_bkey_fields i,575 unsigned bits, u64 offset)576{577 unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i];578 u64 unpacked_max = ~((~0ULL << 1) << (unpacked_bits - 1));579 580 bits = min(bits, unpacked_bits);581 582 offset = bits == unpacked_bits ? 0 : min(offset, unpacked_max - ((1ULL << bits) - 1));583 584 f->bits_per_field[i] = bits;585 f->field_offset[i] = cpu_to_le64(offset);586}587 588struct bkey_format bch2_bkey_format_done(struct bkey_format_state *s)589{590 unsigned i, bits = KEY_PACKED_BITS_START;591 struct bkey_format ret = {592 .nr_fields = BKEY_NR_FIELDS,593 };594 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]);597 598 set_format_field(&ret, i,599 fls64(s->field_max[i] - s->field_min[i]),600 s->field_min[i]);601 602 bits += ret.bits_per_field[i];603 }604 605 /* allow for extent merging: */606 if (ret.bits_per_field[BKEY_FIELD_SIZE]) {607 unsigned b = min(4U, 32U - ret.bits_per_field[BKEY_FIELD_SIZE]);608 609 ret.bits_per_field[BKEY_FIELD_SIZE] += b;610 bits += b;611 }612 613 ret.key_u64s = DIV_ROUND_UP(bits, 64);614 615 /* if we have enough spare bits, round fields up to nearest byte */616 bits = ret.key_u64s * 64 - bits;617 618 for (i = 0; i < ARRAY_SIZE(ret.bits_per_field); i++) {619 unsigned r = round_up(ret.bits_per_field[i], 8) -620 ret.bits_per_field[i];621 622 if (r <= bits) {623 set_format_field(&ret, i,624 ret.bits_per_field[i] + r,625 le64_to_cpu(ret.field_offset[i]));626 bits -= r;627 }628 }629 630#ifdef CONFIG_BCACHEFS_DEBUG631 {632 struct printbuf buf = PRINTBUF;633 634 BUG_ON(bch2_bkey_format_invalid(NULL, &ret, 0, &buf));635 printbuf_exit(&buf);636 }637#endif638 return ret;639}640 641int bch2_bkey_format_invalid(struct bch_fs *c,642 struct bkey_format *f,643 enum bch_validate_flags flags,644 struct printbuf *err)645{646 unsigned bits = KEY_PACKED_BITS_START;647 648 if (f->nr_fields != BKEY_NR_FIELDS) {649 prt_printf(err, "incorrect number of fields: got %u, should be %u",650 f->nr_fields, BKEY_NR_FIELDS);651 return -BCH_ERR_invalid;652 }653 654 /*655 * Verify that the packed format can't represent fields larger than the656 * unpacked format:657 */658 for (unsigned i = 0; i < f->nr_fields; i++) {659 if (bch2_bkey_format_field_overflows(f, i)) {660 unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i];661 u64 unpacked_max = ~((~0ULL << 1) << (unpacked_bits - 1));662 unsigned packed_bits = min(64, f->bits_per_field[i]);663 u64 packed_max = packed_bits664 ? ~((~0ULL << 1) << (packed_bits - 1))665 : 0;666 667 prt_printf(err, "field %u too large: %llu + %llu > %llu",668 i, packed_max, le64_to_cpu(f->field_offset[i]), unpacked_max);669 return -BCH_ERR_invalid;670 }671 672 bits += f->bits_per_field[i];673 }674 675 if (f->key_u64s != DIV_ROUND_UP(bits, 64)) {676 prt_printf(err, "incorrect key_u64s: got %u, should be %u",677 f->key_u64s, DIV_ROUND_UP(bits, 64));678 return -BCH_ERR_invalid;679 }680 681 return 0;682}683 684void bch2_bkey_format_to_text(struct printbuf *out, const struct bkey_format *f)685{686 prt_printf(out, "u64s %u fields ", f->key_u64s);687 688 for (unsigned i = 0; i < ARRAY_SIZE(f->bits_per_field); i++) {689 if (i)690 prt_str(out, ", ");691 prt_printf(out, "%u:%llu",692 f->bits_per_field[i],693 le64_to_cpu(f->field_offset[i]));694 }695}696 697/*698 * Most significant differing bit699 * Bits are indexed from 0 - return is [0, nr_key_bits)700 */701__pure702unsigned bch2_bkey_greatest_differing_bit(const struct btree *b,703 const struct bkey_packed *l_k,704 const struct bkey_packed *r_k)705{706 const u64 *l = high_word(&b->format, l_k);707 const u64 *r = high_word(&b->format, r_k);708 unsigned nr_key_bits = b->nr_key_bits;709 unsigned word_bits = 64 - high_bit_offset;710 u64 l_v, r_v;711 712 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(&b->format));713 714 /* for big endian, skip past header */715 l_v = *l & (~0ULL >> high_bit_offset);716 r_v = *r & (~0ULL >> high_bit_offset);717 718 while (nr_key_bits) {719 if (nr_key_bits < word_bits) {720 l_v >>= word_bits - nr_key_bits;721 r_v >>= word_bits - nr_key_bits;722 nr_key_bits = 0;723 } else {724 nr_key_bits -= word_bits;725 }726 727 if (l_v != r_v)728 return fls64(l_v ^ r_v) - 1 + nr_key_bits;729 730 l = next_word(l);731 r = next_word(r);732 733 l_v = *l;734 r_v = *r;735 word_bits = 64;736 }737 738 return 0;739}740 741/*742 * First set bit743 * Bits are indexed from 0 - return is [0, nr_key_bits)744 */745__pure746unsigned bch2_bkey_ffs(const struct btree *b, const struct bkey_packed *k)747{748 const u64 *p = high_word(&b->format, k);749 unsigned nr_key_bits = b->nr_key_bits;750 unsigned ret = 0, offset;751 752 EBUG_ON(b->nr_key_bits != bkey_format_key_bits(&b->format));753 754 offset = nr_key_bits;755 while (offset > 64) {756 p = next_word(p);757 offset -= 64;758 }759 760 offset = 64 - offset;761 762 while (nr_key_bits) {763 unsigned bits = nr_key_bits + offset < 64764 ? nr_key_bits765 : 64 - offset;766 767 u64 mask = (~0ULL >> (64 - bits)) << offset;768 769 if (*p & mask)770 return ret + __ffs64(*p & mask) - offset;771 772 p = prev_word(p);773 nr_key_bits -= bits;774 ret += bits;775 offset = 0;776 }777 778 return 0;779}780 781#ifdef HAVE_BCACHEFS_COMPILED_UNPACK782 783#define I(_x) (*(out)++ = (_x))784#define I1(i0) I(i0)785#define I2(i0, i1) (I1(i0), I(i1))786#define I3(i0, i1, i2) (I2(i0, i1), I(i2))787#define I4(i0, i1, i2, i3) (I3(i0, i1, i2), I(i3))788#define I5(i0, i1, i2, i3, i4) (I4(i0, i1, i2, i3), I(i4))789 790static u8 *compile_bkey_field(const struct bkey_format *format, u8 *out,791 enum bch_bkey_fields field,792 unsigned dst_offset, unsigned dst_size,793 bool *eax_zeroed)794{795 unsigned bits = format->bits_per_field[field];796 u64 offset = le64_to_cpu(format->field_offset[field]);797 unsigned i, byte, bit_offset, align, shl, shr;798 799 if (!bits && !offset) {800 if (!*eax_zeroed) {801 /* xor eax, eax */802 I2(0x31, 0xc0);803 }804 805 *eax_zeroed = true;806 goto set_field;807 }808 809 if (!bits) {810 /* just return offset: */811 812 switch (dst_size) {813 case 8:814 if (offset > S32_MAX) {815 /* mov [rdi + dst_offset], offset */816 I3(0xc7, 0x47, dst_offset);817 memcpy(out, &offset, 4);818 out += 4;819 820 I3(0xc7, 0x47, dst_offset + 4);821 memcpy(out, (void *) &offset + 4, 4);822 out += 4;823 } else {824 /* mov [rdi + dst_offset], offset */825 /* sign extended */826 I4(0x48, 0xc7, 0x47, dst_offset);827 memcpy(out, &offset, 4);828 out += 4;829 }830 break;831 case 4:832 /* mov [rdi + dst_offset], offset */833 I3(0xc7, 0x47, dst_offset);834 memcpy(out, &offset, 4);835 out += 4;836 break;837 default:838 BUG();839 }840 841 return out;842 }843 844 bit_offset = format->key_u64s * 64;845 for (i = 0; i <= field; i++)846 bit_offset -= format->bits_per_field[i];847 848 byte = bit_offset / 8;849 bit_offset -= byte * 8;850 851 *eax_zeroed = false;852 853 if (bit_offset == 0 && bits == 8) {854 /* movzx eax, BYTE PTR [rsi + imm8] */855 I4(0x0f, 0xb6, 0x46, byte);856 } else if (bit_offset == 0 && bits == 16) {857 /* movzx eax, WORD PTR [rsi + imm8] */858 I4(0x0f, 0xb7, 0x46, byte);859 } else if (bit_offset + bits <= 32) {860 align = min(4 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 3);861 byte -= align;862 bit_offset += align * 8;863 864 BUG_ON(bit_offset + bits > 32);865 866 /* mov eax, [rsi + imm8] */867 I3(0x8b, 0x46, byte);868 869 if (bit_offset) {870 /* shr eax, imm8 */871 I3(0xc1, 0xe8, bit_offset);872 }873 874 if (bit_offset + bits < 32) {875 unsigned mask = ~0U >> (32 - bits);876 877 /* and eax, imm32 */878 I1(0x25);879 memcpy(out, &mask, 4);880 out += 4;881 }882 } else if (bit_offset + bits <= 64) {883 align = min(8 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 7);884 byte -= align;885 bit_offset += align * 8;886 887 BUG_ON(bit_offset + bits > 64);888 889 /* mov rax, [rsi + imm8] */890 I4(0x48, 0x8b, 0x46, byte);891 892 shl = 64 - bit_offset - bits;893 shr = bit_offset + shl;894 895 if (shl) {896 /* shl rax, imm8 */897 I4(0x48, 0xc1, 0xe0, shl);898 }899 900 if (shr) {901 /* shr rax, imm8 */902 I4(0x48, 0xc1, 0xe8, shr);903 }904 } else {905 align = min(4 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 3);906 byte -= align;907 bit_offset += align * 8;908 909 BUG_ON(bit_offset + bits > 96);910 911 /* mov rax, [rsi + byte] */912 I4(0x48, 0x8b, 0x46, byte);913 914 /* mov edx, [rsi + byte + 8] */915 I3(0x8b, 0x56, byte + 8);916 917 /* bits from next word: */918 shr = bit_offset + bits - 64;919 BUG_ON(shr > bit_offset);920 921 /* shr rax, bit_offset */922 I4(0x48, 0xc1, 0xe8, shr);923 924 /* shl rdx, imm8 */925 I4(0x48, 0xc1, 0xe2, 64 - shr);926 927 /* or rax, rdx */928 I3(0x48, 0x09, 0xd0);929 930 shr = bit_offset - shr;931 932 if (shr) {933 /* shr rax, imm8 */934 I4(0x48, 0xc1, 0xe8, shr);935 }936 }937 938 /* rax += offset: */939 if (offset > S32_MAX) {940 /* mov rdx, imm64 */941 I2(0x48, 0xba);942 memcpy(out, &offset, 8);943 out += 8;944 /* add %rdx, %rax */945 I3(0x48, 0x01, 0xd0);946 } else if (offset + (~0ULL >> (64 - bits)) > U32_MAX) {947 /* add rax, imm32 */948 I2(0x48, 0x05);949 memcpy(out, &offset, 4);950 out += 4;951 } else if (offset) {952 /* add eax, imm32 */953 I1(0x05);954 memcpy(out, &offset, 4);955 out += 4;956 }957set_field:958 switch (dst_size) {959 case 8:960 /* mov [rdi + dst_offset], rax */961 I4(0x48, 0x89, 0x47, dst_offset);962 break;963 case 4:964 /* mov [rdi + dst_offset], eax */965 I3(0x89, 0x47, dst_offset);966 break;967 default:968 BUG();969 }970 971 return out;972}973 974int bch2_compile_bkey_format(const struct bkey_format *format, void *_out)975{976 bool eax_zeroed = false;977 u8 *out = _out;978 979 /*980 * rdi: dst - unpacked key981 * rsi: src - packed key982 */983 984 /* k->u64s, k->format, k->type */985 986 /* mov eax, [rsi] */987 I2(0x8b, 0x06);988 989 /* add eax, BKEY_U64s - format->key_u64s */990 I5(0x05, BKEY_U64s - format->key_u64s, KEY_FORMAT_CURRENT, 0, 0);991 992 /* and eax, imm32: mask out k->pad: */993 I5(0x25, 0xff, 0xff, 0xff, 0);994 995 /* mov [rdi], eax */996 I2(0x89, 0x07);997 998#define x(id, field) \999 out = compile_bkey_field(format, out, id, \1000 offsetof(struct bkey, field), \1001 sizeof(((struct bkey *) NULL)->field), \1002 &eax_zeroed);1003 bkey_fields()1004#undef x1005 1006 /* retq */1007 I1(0xc3);1008 1009 return (void *) out - _out;1010}1011 1012#else1013#endif1014 1015__pure1016int __bch2_bkey_cmp_packed_format_checked(const struct bkey_packed *l,1017 const struct bkey_packed *r,1018 const struct btree *b)1019{1020 return __bch2_bkey_cmp_packed_format_checked_inlined(l, r, b);1021}1022 1023__pure __flatten1024int __bch2_bkey_cmp_left_packed_format_checked(const struct btree *b,1025 const struct bkey_packed *l,1026 const struct bpos *r)1027{1028 return bpos_cmp(bkey_unpack_pos_format_checked(b, l), *r);1029}1030 1031__pure __flatten1032int bch2_bkey_cmp_packed(const struct btree *b,1033 const struct bkey_packed *l,1034 const struct bkey_packed *r)1035{1036 return bch2_bkey_cmp_packed_inlined(b, l, r);1037}1038 1039__pure __flatten1040int __bch2_bkey_cmp_left_packed(const struct btree *b,1041 const struct bkey_packed *l,1042 const struct bpos *r)1043{1044 const struct bkey *l_unpacked;1045 1046 return unlikely(l_unpacked = packed_to_bkey_c(l))1047 ? bpos_cmp(l_unpacked->p, *r)1048 : __bch2_bkey_cmp_left_packed_format_checked(b, l, r);1049}1050 1051void bch2_bpos_swab(struct bpos *p)1052{1053 u8 *l = (u8 *) p;1054 u8 *h = ((u8 *) &p[1]) - 1;1055 1056 while (l < h) {1057 swap(*l, *h);1058 l++;1059 --h;1060 }1061}1062 1063void bch2_bkey_swab_key(const struct bkey_format *_f, struct bkey_packed *k)1064{1065 const struct bkey_format *f = bkey_packed(k) ? _f : &bch2_bkey_format_current;1066 u8 *l = k->key_start;1067 u8 *h = (u8 *) ((u64 *) k->_data + f->key_u64s) - 1;1068 1069 while (l < h) {1070 swap(*l, *h);1071 l++;1072 --h;1073 }1074}1075 1076#ifdef CONFIG_BCACHEFS_DEBUG1077void bch2_bkey_pack_test(void)1078{1079 struct bkey t = KEY(4134ULL, 1250629070527416633ULL, 0);1080 struct bkey_packed p;1081 1082 struct bkey_format test_format = {1083 .key_u64s = 3,1084 .nr_fields = BKEY_NR_FIELDS,1085 .bits_per_field = {1086 13,1087 64,1088 32,1089 },1090 };1091 1092 struct unpack_state in_s =1093 unpack_state_init(&bch2_bkey_format_current, (void *) &t);1094 struct pack_state out_s = pack_state_init(&test_format, &p);1095 unsigned i;1096 1097 for (i = 0; i < out_s.format->nr_fields; i++) {1098 u64 a, v = get_inc_field(&in_s, i);1099 1100 switch (i) {1101#define x(id, field) case id: a = t.field; break;1102 bkey_fields()1103#undef x1104 default:1105 BUG();1106 }1107 1108 if (a != v)1109 panic("got %llu actual %llu i %u\n", v, a, i);1110 1111 if (!set_inc_field(&out_s, i, v))1112 panic("failed at %u\n", i);1113 }1114 1115 BUG_ON(!bch2_bkey_pack_key(&p, &t, &test_format));1116}1117#endif1118