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