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

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