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

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