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

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