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