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