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