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