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

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