git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/bkey.c

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