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