fs/bcachefs/bkey.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   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
  10 const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT;
  11
  12 void 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_DEBUG
  51
  52 static 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 #else
  99 static inline void bch2_bkey_pack_verify(const struct bkey_packed *packed,
 100                                         const struct bkey *unpacked,
 101                                         const struct bkey_format *format) {}
 102 #endif
 103
 104 struct 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_inline
 112 static 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_inline
 126 static 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
 135 struct 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_inline
 143 static 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_inline
 157 static 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_inline
 180 static 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_inline
 202 static 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 that
 223  * if k is packed bkey_start_pos(k) will successfully pack
 224  */
 225 static 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
 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)
 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
 266 struct 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 x
 286
 287         return out;
 288 }
 289
 290 #ifndef HAVE_BCACHEFS_COMPILED_UNPACK
 291 struct 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 #endif
 308
 309 /**
 310  * bch2_bkey_pack_key -- pack just the key, not the value
 311  * @out:        packed result
 312  * @in:         key to pack
 313  * @format:     format of packed result
 314  *
 315  * Returns: true on success, false on failure
 316  */
 317 bool 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 x
 332         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 value
 344  * @b:          btree node of @src key (for packed format)
 345  * @dst:        unpacked result
 346  * @src:        packed input
 347  */
 348 void 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 value
 360  * @dst:        packed result
 361  * @src:        unpacked input
 362  * @format:     format of packed result
 363  *
 364  * Returns: true on success, false on failure
 365  */
 366 bool 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_inline
 383 static 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_DEBUG
 402 static 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
 441 static 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 #endif
 459
 460 /*
 461  * Returns a packed key that compares <= in
 462  *
 463  * This is used in bset_search_tree(), where we need a packed pos in order to be
 464  * able to compare against the keys in the auxiliary search tree - and it's
 465  * legal to use a packed pos that isn't equivalent to the original pos,
 466  * _provided_ it compares <= to the original pos.
 467  */
 468 enum 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_DEBUG
 476         struct bpos orig = in;
 477 #endif
 478         bool exact = true;
 479         unsigned i;
 480
 481         /*
 482          * bch2_bkey_pack_key() will write to all of f->key_u64s, minus the 3
 483          * byte header, but pack_pos() won't if the len/version fields are big
 484          * 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_DEBUG
 531         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 #endif
 542
 543         return exact ? BKEY_PACK_POS_EXACT : BKEY_PACK_POS_SMALLER;
 544 }
 545
 546 void 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
 560 void 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 fields
 571  * bigger than a u64... that will cause confusion and issues (like with
 572  * bkey_packed_successor())
 573  */
 574 static 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
 588 struct 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_DEBUG
 631         {
 632                 struct printbuf buf = PRINTBUF;
 633
 634                 BUG_ON(bch2_bkey_format_invalid(NULL, &ret, 0, &buf));
 635                 printbuf_exit(&buf);
 636         }
 637 #endif
 638         return ret;
 639 }
 640
 641 int 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 i, 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 the
 656          * unpacked format:
 657          */
 658         for (i = 0; i < f->nr_fields; i++) {
 659                 if ((!c || c->sb.version_min >= bcachefs_metadata_version_snapshot) &&
 660                     bch2_bkey_format_field_overflows(f, i)) {
 661                         unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i];
 662                         u64 unpacked_max = ~((~0ULL << 1) << (unpacked_bits - 1));
 663                         u64 packed_max = f->bits_per_field[i]
 664                                 ? ~((~0ULL << 1) << (f->bits_per_field[i] - 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
 684 void 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 bit
 699  * Bits are indexed from 0 - return is [0, nr_key_bits)
 700  */
 701 __pure
 702 unsigned 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 bit
 743  * Bits are indexed from 0 - return is [0, nr_key_bits)
 744  */
 745 __pure
 746 unsigned 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 < 64
 764                         ? nr_key_bits
 765                         : 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_UNPACK
 782
 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
 790 static 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         }
 957 set_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
 974 int 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 key
 981          * rsi: src - packed key
 982          */
 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 x
1005
1006         /* retq */
1007         I1(0xc3);
1008
1009         return (void *) out - _out;
1010 }
1011
1012 #else
1013 #endif
1014
1015 __pure
1016 int __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 __flatten
1024 int __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 __flatten
1032 int 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 __flatten
1040 int __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
1051 void 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
1063 void 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_DEBUG
1077 void 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 x
1104                 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 #endif