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