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

   1
   2 #include "bcachefs.h"
   3 #include "bkey.h"
   4 #include "bset.h"
   5 #include "util.h"
   6
   7 const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT;
   8
   9 struct bkey __bch2_bkey_unpack_key(const struct bkey_format *,
  10                               const struct bkey_packed *);
  11
  12 void bch2_to_binary(char *out, const u64 *p, unsigned nr_bits)
  13 {
  14         unsigned bit = high_bit_offset, done = 0;
  15
  16         while (1) {
  17                 while (bit < 64) {
  18                         if (done && !(done % 8))
  19                                 *out++ = ' ';
  20                         *out++ = *p & (1ULL << (63 - bit)) ? '1' : '0';
  21                         bit++;
  22                         done++;
  23                         if (done == nr_bits) {
  24                                 *out++ = '\0';
  25                                 return;
  26                         }
  27                 }
  28
  29                 p = next_word(p);
  30                 bit = 0;
  31         }
  32 }
  33
  34 #ifdef CONFIG_BCACHEFS_DEBUG
  35
  36 static void bch2_bkey_pack_verify(const struct bkey_packed *packed,
  37                                  const struct bkey *unpacked,
  38                                  const struct bkey_format *format)
  39 {
  40         struct bkey tmp;
  41
  42         BUG_ON(bkeyp_val_u64s(format, packed) !=
  43                bkey_val_u64s(unpacked));
  44
  45         BUG_ON(packed->u64s < bkeyp_key_u64s(format, packed));
  46
  47         tmp = __bch2_bkey_unpack_key(format, packed);
  48
  49         if (memcmp(&tmp, unpacked, sizeof(struct bkey))) {
  50                 char buf1[160], buf2[160];
  51                 char buf3[160], buf4[160];
  52
  53                 bch2_bkey_to_text(buf1, sizeof(buf1), unpacked);
  54                 bch2_bkey_to_text(buf2, sizeof(buf2), &tmp);
  55                 bch2_to_binary(buf3, (void *) unpacked, 80);
  56                 bch2_to_binary(buf4, high_word(format, packed), 80);
  57
  58                 panic("keys differ: format u64s %u fields %u %u %u %u %u\n%s\n%s\n%s\n%s\n",
  59                       format->key_u64s,
  60                       format->bits_per_field[0],
  61                       format->bits_per_field[1],
  62                       format->bits_per_field[2],
  63                       format->bits_per_field[3],
  64                       format->bits_per_field[4],
  65                       buf1, buf2, buf3, buf4);
  66         }
  67 }
  68
  69 #else
  70 static inline void bch2_bkey_pack_verify(const struct bkey_packed *packed,
  71                                         const struct bkey *unpacked,
  72                                         const struct bkey_format *format) {}
  73 #endif
  74
  75 int bch2_bkey_to_text(char *buf, size_t size, const struct bkey *k)
  76 {
  77         char *out = buf, *end = buf + size;
  78
  79 #define p(...)  (out += scnprintf(out, end - out, __VA_ARGS__))
  80
  81         p("u64s %u type %u %llu:%llu snap %u len %u ver %llu",
  82           k->u64s, k->type, k->p.inode, k->p.offset,
  83           k->p.snapshot, k->size, k->version.lo);
  84
  85         BUG_ON(bkey_packed(k));
  86
  87         switch (k->type) {
  88         case KEY_TYPE_DELETED:
  89                 p(" deleted");
  90                 break;
  91         case KEY_TYPE_DISCARD:
  92                 p(" discard");
  93                 break;
  94         case KEY_TYPE_ERROR:
  95                 p(" error");
  96                 break;
  97         case KEY_TYPE_COOKIE:
  98                 p(" cookie");
  99                 break;
 100         }
 101 #undef p
 102
 103         return out - buf;
 104 }
 105
 106 struct pack_state {
 107         const struct bkey_format *format;
 108         unsigned                bits;   /* bits remaining in current word */
 109         u64                     w;      /* current word */
 110         u64                     *p;     /* pointer to next word */
 111 };
 112
 113 __always_inline
 114 static struct pack_state pack_state_init(const struct bkey_format *format,
 115                                          struct bkey_packed *k)
 116 {
 117         u64 *p = high_word(format, k);
 118
 119         return (struct pack_state) {
 120                 .format = format,
 121                 .bits   = 64 - high_bit_offset,
 122                 .w      = 0,
 123                 .p      = p,
 124         };
 125 }
 126
 127 __always_inline
 128 static void pack_state_finish(struct pack_state *state,
 129                               struct bkey_packed *k)
 130 {
 131         EBUG_ON(state->p <  k->_data);
 132         EBUG_ON(state->p >= k->_data + state->format->key_u64s);
 133
 134         *state->p = state->w;
 135 }
 136
 137 struct unpack_state {
 138         const struct bkey_format *format;
 139         unsigned                bits;   /* bits remaining in current word */
 140         u64                     w;      /* current word */
 141         const u64               *p;     /* pointer to next word */
 142 };
 143
 144 __always_inline
 145 static struct unpack_state unpack_state_init(const struct bkey_format *format,
 146                                              const struct bkey_packed *k)
 147 {
 148         const u64 *p = high_word(format, k);
 149
 150         return (struct unpack_state) {
 151                 .format = format,
 152                 .bits   = 64 - high_bit_offset,
 153                 .w      = *p << high_bit_offset,
 154                 .p      = p,
 155         };
 156 }
 157
 158 __always_inline
 159 static u64 get_inc_field(struct unpack_state *state, unsigned field)
 160 {
 161         unsigned bits = state->format->bits_per_field[field];
 162         u64 v = 0, offset = le64_to_cpu(state->format->field_offset[field]);
 163
 164         if (bits >= state->bits) {
 165                 v = state->w >> (64 - bits);
 166                 bits -= state->bits;
 167
 168                 state->p = next_word(state->p);
 169                 state->w = *state->p;
 170                 state->bits = 64;
 171         }
 172
 173         /* avoid shift by 64 if bits is 0 - bits is never 64 here: */
 174         v |= (state->w >> 1) >> (63 - bits);
 175         state->w <<= bits;
 176         state->bits -= bits;
 177
 178         return v + offset;
 179 }
 180
 181 __always_inline
 182 static bool set_inc_field(struct pack_state *state, unsigned field, u64 v)
 183 {
 184         unsigned bits = state->format->bits_per_field[field];
 185         u64 offset = le64_to_cpu(state->format->field_offset[field]);
 186
 187         if (v < offset)
 188                 return false;
 189
 190         v -= offset;
 191
 192         if (fls64(v) > bits)
 193                 return false;
 194
 195         if (bits > state->bits) {
 196                 bits -= state->bits;
 197                 /* avoid shift by 64 if bits is 0 - bits is never 64 here: */
 198                 state->w |= (v >> 1) >> (bits - 1);
 199
 200                 *state->p = state->w;
 201                 state->p = next_word(state->p);
 202                 state->w = 0;
 203                 state->bits = 64;
 204         }
 205
 206         state->bits -= bits;
 207         state->w |= v << state->bits;
 208
 209         return true;
 210 }
 211
 212 /*
 213  * Note: does NOT set out->format (we don't know what it should be here!)
 214  *
 215  * Also: doesn't work on extents - it doesn't preserve the invariant that
 216  * if k is packed bkey_start_pos(k) will successfully pack
 217  */
 218 static bool bch2_bkey_transform_key(const struct bkey_format *out_f,
 219                                    struct bkey_packed *out,
 220                                    const struct bkey_format *in_f,
 221                                    const struct bkey_packed *in)
 222 {
 223         struct pack_state out_s = pack_state_init(out_f, out);
 224         struct unpack_state in_s = unpack_state_init(in_f, in);
 225         unsigned i;
 226
 227         out->_data[0] = 0;
 228
 229         for (i = 0; i < BKEY_NR_FIELDS; i++)
 230                 if (!set_inc_field(&out_s, i, get_inc_field(&in_s, i)))
 231                         return false;
 232
 233         /* Can't happen because the val would be too big to unpack: */
 234         EBUG_ON(in->u64s - in_f->key_u64s + out_f->key_u64s > U8_MAX);
 235
 236         pack_state_finish(&out_s, out);
 237         out->u64s       = out_f->key_u64s + in->u64s - in_f->key_u64s;
 238         out->needs_whiteout = in->needs_whiteout;
 239         out->type       = in->type;
 240
 241         return true;
 242 }
 243
 244 bool bch2_bkey_transform(const struct bkey_format *out_f,
 245                         struct bkey_packed *out,
 246                         const struct bkey_format *in_f,
 247                         const struct bkey_packed *in)
 248 {
 249         if (!bch2_bkey_transform_key(out_f, out, in_f, in))
 250                 return false;
 251
 252         memcpy_u64s((u64 *) out + out_f->key_u64s,
 253                     (u64 *) in + in_f->key_u64s,
 254                     (in->u64s - in_f->key_u64s));
 255         return true;
 256 }
 257
 258 #define bkey_fields()                                                   \
 259         x(BKEY_FIELD_INODE,             p.inode)                        \
 260         x(BKEY_FIELD_OFFSET,            p.offset)                       \
 261         x(BKEY_FIELD_SNAPSHOT,          p.snapshot)                     \
 262         x(BKEY_FIELD_SIZE,              size)                           \
 263         x(BKEY_FIELD_VERSION_HI,        version.hi)                     \
 264         x(BKEY_FIELD_VERSION_LO,        version.lo)
 265
 266 struct bkey __bch2_bkey_unpack_key(const struct bkey_format *format,
 267                               const struct bkey_packed *in)
 268 {
 269         struct unpack_state state = unpack_state_init(format, in);
 270         struct bkey out;
 271
 272         EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
 273         EBUG_ON(in->u64s < format->key_u64s);
 274         EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);
 275         EBUG_ON(in->u64s - format->key_u64s + BKEY_U64s > U8_MAX);
 276
 277         out.u64s        = BKEY_U64s + in->u64s - format->key_u64s;
 278         out.format      = KEY_FORMAT_CURRENT;
 279         out.needs_whiteout = in->needs_whiteout;
 280         out.type        = in->type;
 281         out.pad[0]      = 0;
 282
 283 #define x(id, field)    out.field = get_inc_field(&state, id);
 284         bkey_fields()
 285 #undef x
 286
 287         return out;
 288 }
 289
 290 #ifndef HAVE_BCACHEFS_COMPILED_UNPACK
 291 struct bpos __bkey_unpack_pos(const struct bkey_format *format,
 292                                      const struct bkey_packed *in)
 293 {
 294         struct unpack_state state = unpack_state_init(format, in);
 295         struct bpos out;
 296
 297         EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
 298         EBUG_ON(in->u64s < format->key_u64s);
 299         EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);
 300
 301         out.inode       = get_inc_field(&state, BKEY_FIELD_INODE);
 302         out.offset      = get_inc_field(&state, BKEY_FIELD_OFFSET);
 303         out.snapshot    = get_inc_field(&state, BKEY_FIELD_SNAPSHOT);
 304
 305         return out;
 306 }
 307 #endif
 308
 309 /**
 310  * bch2_bkey_pack_key -- pack just the key, not the value
 311  */
 312 bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in,
 313                    const struct bkey_format *format)
 314 {
 315         struct pack_state state = pack_state_init(format, out);
 316
 317         EBUG_ON((void *) in == (void *) out);
 318         EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
 319         EBUG_ON(in->format != KEY_FORMAT_CURRENT);
 320
 321         out->_data[0] = 0;
 322
 323 #define x(id, field)    if (!set_inc_field(&state, id, in->field)) return false;
 324         bkey_fields()
 325 #undef x
 326
 327         /*
 328          * Extents - we have to guarantee that if an extent is packed, a trimmed
 329          * version will also pack:
 330          */
 331         if (bkey_start_offset(in) < format->field_offset[BKEY_FIELD_OFFSET])
 332                 return false;
 333
 334         pack_state_finish(&state, out);
 335         out->u64s       = format->key_u64s + in->u64s - BKEY_U64s;
 336         out->format     = KEY_FORMAT_LOCAL_BTREE;
 337         out->needs_whiteout = in->needs_whiteout;
 338         out->type       = in->type;
 339
 340         bch2_bkey_pack_verify(out, in, format);
 341         return true;
 342 }
 343
 344 /**
 345  * bch2_bkey_unpack -- unpack the key and the value
 346  */
 347 void bch2_bkey_unpack(const struct btree *b, struct bkey_i *dst,
 348                  const struct bkey_packed *src)
 349 {
 350         dst->k = bkey_unpack_key(b, src);
 351
 352         memcpy_u64s(&dst->v,
 353                     bkeyp_val(&b->format, src),
 354                     bkeyp_val_u64s(&b->format, src));
 355 }
 356
 357 /**
 358  * bch2_bkey_pack -- pack the key and the value
 359  */
 360 bool bch2_bkey_pack(struct bkey_packed *out, const struct bkey_i *in,
 361                const struct bkey_format *format)
 362 {
 363         struct bkey_packed tmp;
 364
 365         if (!bch2_bkey_pack_key(&tmp, &in->k, format))
 366                 return false;
 367
 368         memmove_u64s((u64 *) out + format->key_u64s,
 369                      &in->v,
 370                      bkey_val_u64s(&in->k));
 371         memcpy_u64s(out, &tmp, format->key_u64s);
 372
 373         return true;
 374 }
 375
 376 __always_inline
 377 static bool set_inc_field_lossy(struct pack_state *state, unsigned field, u64 v)
 378 {
 379         unsigned bits = state->format->bits_per_field[field];
 380         u64 offset = le64_to_cpu(state->format->field_offset[field]);
 381         bool ret = true;
 382
 383         EBUG_ON(v < offset);
 384         v -= offset;
 385
 386         if (fls64(v) > bits) {
 387                 v = ~(~0ULL << bits);
 388                 ret = false;
 389         }
 390
 391         if (bits > state->bits) {
 392                 bits -= state->bits;
 393                 state->w |= (v >> 1) >> (bits - 1);
 394
 395                 *state->p = state->w;
 396                 state->p = next_word(state->p);
 397                 state->w = 0;
 398                 state->bits = 64;
 399         }
 400
 401         state->bits -= bits;
 402         state->w |= v << state->bits;
 403
 404         return ret;
 405 }
 406
 407 #ifdef CONFIG_BCACHEFS_DEBUG
 408 static bool bkey_packed_successor(struct bkey_packed *out,
 409                                   const struct btree *b,
 410                                   struct bkey_packed k)
 411 {
 412         const struct bkey_format *f = &b->format;
 413         unsigned nr_key_bits = b->nr_key_bits;
 414         unsigned first_bit, offset;
 415         u64 *p;
 416
 417         EBUG_ON(b->nr_key_bits != bkey_format_key_bits(f));
 418
 419         if (!nr_key_bits)
 420                 return false;
 421
 422         *out = k;
 423
 424         first_bit = high_bit_offset + nr_key_bits - 1;
 425         p = nth_word(high_word(f, out), first_bit >> 6);
 426         offset = 63 - (first_bit & 63);
 427
 428         while (nr_key_bits) {
 429                 unsigned bits = min(64 - offset, nr_key_bits);
 430                 u64 mask = (~0ULL >> (64 - bits)) << offset;
 431
 432                 if ((*p & mask) != mask) {
 433                         *p += 1ULL << offset;
 434                         EBUG_ON(bkey_cmp_packed(b, out, &k) <= 0);
 435                         return true;
 436                 }
 437
 438                 *p &= ~mask;
 439                 p = prev_word(p);
 440                 nr_key_bits -= bits;
 441                 offset = 0;
 442         }
 443
 444         return false;
 445 }
 446 #endif
 447
 448 /*
 449  * Returns a packed key that compares <= in
 450  *
 451  * This is used in bset_search_tree(), where we need a packed pos in order to be
 452  * able to compare against the keys in the auxiliary search tree - and it's
 453  * legal to use a packed pos that isn't equivalent to the original pos,
 454  * _provided_ it compares <= to the original pos.
 455  */
 456 enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out,
 457                                            struct bpos in,
 458                                            const struct btree *b)
 459 {
 460         const struct bkey_format *f = &b->format;
 461         struct pack_state state = pack_state_init(f, out);
 462 #ifdef CONFIG_BCACHEFS_DEBUG
 463         struct bpos orig = in;
 464 #endif
 465         bool exact = true;
 466
 467         out->_data[0] = 0;
 468
 469         if (unlikely(in.snapshot <
 470                      le64_to_cpu(f->field_offset[BKEY_FIELD_SNAPSHOT]))) {
 471                 if (!in.offset-- &&
 472                     !in.inode--)
 473                         return BKEY_PACK_POS_FAIL;
 474                 in.snapshot     = KEY_SNAPSHOT_MAX;
 475                 exact = false;
 476         }
 477
 478         if (unlikely(in.offset <
 479                      le64_to_cpu(f->field_offset[BKEY_FIELD_OFFSET]))) {
 480                 if (!in.inode--)
 481                         return BKEY_PACK_POS_FAIL;
 482                 in.offset       = KEY_OFFSET_MAX;
 483                 in.snapshot     = KEY_SNAPSHOT_MAX;
 484                 exact = false;
 485         }
 486
 487         if (unlikely(in.inode <
 488                      le64_to_cpu(f->field_offset[BKEY_FIELD_INODE])))
 489                 return BKEY_PACK_POS_FAIL;
 490
 491         if (!set_inc_field_lossy(&state, BKEY_FIELD_INODE, in.inode)) {
 492                 in.offset       = KEY_OFFSET_MAX;
 493                 in.snapshot     = KEY_SNAPSHOT_MAX;
 494                 exact = false;
 495         }
 496
 497         if (!set_inc_field_lossy(&state, BKEY_FIELD_OFFSET, in.offset)) {
 498                 in.snapshot     = KEY_SNAPSHOT_MAX;
 499                 exact = false;
 500         }
 501
 502         if (!set_inc_field_lossy(&state, BKEY_FIELD_SNAPSHOT, in.snapshot))
 503                 exact = false;
 504
 505         pack_state_finish(&state, out);
 506         out->u64s       = f->key_u64s;
 507         out->format     = KEY_FORMAT_LOCAL_BTREE;
 508         out->type       = KEY_TYPE_DELETED;
 509
 510 #ifdef CONFIG_BCACHEFS_DEBUG
 511         if (exact) {
 512                 BUG_ON(bkey_cmp_left_packed(b, out, &orig));
 513         } else {
 514                 struct bkey_packed successor;
 515
 516                 BUG_ON(bkey_cmp_left_packed(b, out, &orig) >= 0);
 517                 BUG_ON(bkey_packed_successor(&successor, b, *out) &&
 518                        bkey_cmp_left_packed(b, &successor, &orig) < 0);
 519         }
 520 #endif
 521
 522         return exact ? BKEY_PACK_POS_EXACT : BKEY_PACK_POS_SMALLER;
 523 }
 524
 525 void bch2_bkey_format_init(struct bkey_format_state *s)
 526 {
 527         unsigned i;
 528
 529         for (i = 0; i < ARRAY_SIZE(s->field_min); i++)
 530                 s->field_min[i] = U64_MAX;
 531
 532         for (i = 0; i < ARRAY_SIZE(s->field_max); i++)
 533                 s->field_max[i] = 0;
 534
 535         /* Make sure we can store a size of 0: */
 536         s->field_min[BKEY_FIELD_SIZE] = 0;
 537 }
 538
 539 static void __bkey_format_add(struct bkey_format_state *s,
 540                               unsigned field, u64 v)
 541 {
 542         s->field_min[field] = min(s->field_min[field], v);
 543         s->field_max[field] = max(s->field_max[field], v);
 544 }
 545
 546 /*
 547  * Changes @format so that @k can be successfully packed with @format
 548  */
 549 void bch2_bkey_format_add_key(struct bkey_format_state *s, const struct bkey *k)
 550 {
 551 #define x(id, field) __bkey_format_add(s, id, k->field);
 552         bkey_fields()
 553 #undef x
 554         __bkey_format_add(s, BKEY_FIELD_OFFSET, bkey_start_offset(k));
 555 }
 556
 557 void bch2_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p)
 558 {
 559         unsigned field = 0;
 560
 561         __bkey_format_add(s, field++, p.inode);
 562         __bkey_format_add(s, field++, p.offset);
 563         __bkey_format_add(s, field++, p.snapshot);
 564 }
 565
 566 /*
 567  * We don't want it to be possible for the packed format to represent fields
 568  * bigger than a u64... that will cause confusion and issues (like with
 569  * bkey_packed_successor())
 570  */
 571 static void set_format_field(struct bkey_format *f, enum bch_bkey_fields i,
 572                              unsigned bits, u64 offset)
 573 {
 574         offset = bits == 64 ? 0 : min(offset, U64_MAX - ((1ULL << bits) - 1));
 575
 576         f->bits_per_field[i]    = bits;
 577         f->field_offset[i]      = cpu_to_le64(offset);
 578 }
 579
 580 struct bkey_format bch2_bkey_format_done(struct bkey_format_state *s)
 581 {
 582         unsigned i, bits = KEY_PACKED_BITS_START;
 583         struct bkey_format ret = {
 584                 .nr_fields = BKEY_NR_FIELDS,
 585         };
 586
 587         for (i = 0; i < ARRAY_SIZE(s->field_min); i++) {
 588                 s->field_min[i] = min(s->field_min[i], s->field_max[i]);
 589
 590                 set_format_field(&ret, i,
 591                                  fls64(s->field_max[i] - s->field_min[i]),
 592                                  s->field_min[i]);
 593
 594                 bits += ret.bits_per_field[i];
 595         }
 596
 597         /* allow for extent merging: */
 598         if (ret.bits_per_field[BKEY_FIELD_SIZE]) {
 599                 ret.bits_per_field[BKEY_FIELD_SIZE] += 4;
 600                 bits += 4;
 601         }
 602
 603         ret.key_u64s = DIV_ROUND_UP(bits, 64);
 604
 605         /* if we have enough spare bits, round fields up to nearest byte */
 606         bits = ret.key_u64s * 64 - bits;
 607
 608         for (i = 0; i < ARRAY_SIZE(ret.bits_per_field); i++) {
 609                 unsigned r = round_up(ret.bits_per_field[i], 8) -
 610                         ret.bits_per_field[i];
 611
 612                 if (r <= bits) {
 613                         set_format_field(&ret, i,
 614                                          ret.bits_per_field[i] + r,
 615                                          le64_to_cpu(ret.field_offset[i]));
 616                         bits -= r;
 617                 }
 618         }
 619
 620         EBUG_ON(bch2_bkey_format_validate(&ret));
 621         return ret;
 622 }
 623
 624 const char *bch2_bkey_format_validate(struct bkey_format *f)
 625 {
 626         unsigned i, bits = KEY_PACKED_BITS_START;
 627
 628         if (f->nr_fields != BKEY_NR_FIELDS)
 629                 return "incorrect number of fields";
 630
 631         for (i = 0; i < f->nr_fields; i++) {
 632                 u64 field_offset = le64_to_cpu(f->field_offset[i]);
 633
 634                 if (f->bits_per_field[i] > 64)
 635                         return "field too large";
 636
 637                 if (field_offset &&
 638                     (f->bits_per_field[i] == 64 ||
 639                     (field_offset + ((1ULL << f->bits_per_field[i]) - 1) <
 640                      field_offset)))
 641                         return "offset + bits overflow";
 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 = 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 (l_v != r_v)
1035                         return l_v < r_v ? -1 : 1;
1036
1037                 if (!nr_key_bits)
1038                         return 0;
1039
1040                 l = next_word(l);
1041                 r = next_word(r);
1042
1043                 l_v = *l;
1044                 r_v = *r;
1045         }
1046 }
1047 #endif
1048
1049 __pure
1050 int __bch2_bkey_cmp_packed_format_checked(const struct bkey_packed *l,
1051                                           const struct bkey_packed *r,
1052                                           const struct btree *b)
1053 {
1054         const struct bkey_format *f = &b->format;
1055         int ret;
1056
1057         EBUG_ON(!bkey_packed(l) || !bkey_packed(r));
1058         EBUG_ON(b->nr_key_bits != bkey_format_key_bits(f));
1059
1060         ret = __bkey_cmp_bits(high_word(f, l),
1061                               high_word(f, r),
1062                               b->nr_key_bits);
1063
1064         EBUG_ON(ret != bkey_cmp(bkey_unpack_key_format_checked(b, l).p,
1065                                 bkey_unpack_key_format_checked(b, r).p));
1066         return ret;
1067 }
1068
1069 __pure __flatten
1070 int __bch2_bkey_cmp_left_packed_format_checked(const struct btree *b,
1071                                                const struct bkey_packed *l,
1072                                                const struct bpos *r)
1073 {
1074         return bkey_cmp(bkey_unpack_pos_format_checked(b, l), *r);
1075 }
1076
1077 __pure __flatten
1078 int __bch2_bkey_cmp_packed(const struct bkey_packed *l,
1079                            const struct bkey_packed *r,
1080                            const struct btree *b)
1081 {
1082         int packed = bkey_lr_packed(l, r);
1083
1084         if (likely(packed == BKEY_PACKED_BOTH))
1085                 return __bch2_bkey_cmp_packed_format_checked(l, r, b);
1086
1087         switch (packed) {
1088         case BKEY_PACKED_NONE:
1089                 return bkey_cmp(((struct bkey *) l)->p,
1090                                 ((struct bkey *) r)->p);
1091         case BKEY_PACKED_LEFT:
1092                 return __bch2_bkey_cmp_left_packed_format_checked(b,
1093                                   (struct bkey_packed *) l,
1094                                   &((struct bkey *) r)->p);
1095         case BKEY_PACKED_RIGHT:
1096                 return -__bch2_bkey_cmp_left_packed_format_checked(b,
1097                                   (struct bkey_packed *) r,
1098                                   &((struct bkey *) l)->p);
1099         default:
1100                 unreachable();
1101         }
1102 }
1103
1104 __pure __flatten
1105 int __bch2_bkey_cmp_left_packed(const struct btree *b,
1106                                 const struct bkey_packed *l,
1107                                 const struct bpos *r)
1108 {
1109         const struct bkey *l_unpacked;
1110
1111         return unlikely(l_unpacked = packed_to_bkey_c(l))
1112                 ? bkey_cmp(l_unpacked->p, *r)
1113                 : __bch2_bkey_cmp_left_packed_format_checked(b, l, r);
1114 }
1115
1116 void bch2_bpos_swab(struct bpos *p)
1117 {
1118         u8 *l = (u8 *) p;
1119         u8 *h = ((u8 *) &p[1]) - 1;
1120
1121         while (l < h) {
1122                 swap(*l, *h);
1123                 l++;
1124                 --h;
1125         }
1126 }
1127
1128 void bch2_bkey_swab_key(const struct bkey_format *_f, struct bkey_packed *k)
1129 {
1130         const struct bkey_format *f = bkey_packed(k) ? _f : &bch2_bkey_format_current;
1131         u8 *l = k->key_start;
1132         u8 *h = (u8 *) (k->_data + f->key_u64s) - 1;
1133
1134         while (l < h) {
1135                 swap(*l, *h);
1136                 l++;
1137                 --h;
1138         }
1139 }
1140
1141 #ifdef CONFIG_BCACHEFS_DEBUG
1142 void bch2_bkey_pack_test(void)
1143 {
1144         struct bkey t = KEY(4134ULL, 1250629070527416633ULL, 0);
1145         struct bkey_packed p;
1146
1147         struct bkey_format test_format = {
1148                 .key_u64s       = 2,
1149                 .nr_fields      = BKEY_NR_FIELDS,
1150                 .bits_per_field = {
1151                         13,
1152                         64,
1153                 },
1154         };
1155
1156         struct unpack_state in_s =
1157                 unpack_state_init(&bch2_bkey_format_current, (void *) &t);
1158         struct pack_state out_s = pack_state_init(&test_format, &p);
1159         unsigned i;
1160
1161         for (i = 0; i < out_s.format->nr_fields; i++) {
1162                 u64 a, v = get_inc_field(&in_s, i);
1163
1164                 switch (i) {
1165 #define x(id, field)    case id: a = t.field; break;
1166         bkey_fields()
1167 #undef x
1168                 default:
1169                         BUG();
1170                 }
1171
1172                 if (a != v)
1173                         panic("got %llu actual %llu i %u\n", v, a, i);
1174
1175                 if (!set_inc_field(&out_s, i, v))
1176                         panic("failed at %u\n", i);
1177         }
1178
1179         BUG_ON(!bch2_bkey_pack_key(&p, &t, &test_format));
1180 }
1181 #endif