1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _BCACHEFS_BKEY_H
3 #define _BCACHEFS_BKEY_H
4
5 #include <linux/bug.h>
6 #include "bcachefs_format.h"
7 #include "bkey_types.h"
8 #include "btree_types.h"
9 #include "util.h"
10 #include "vstructs.h"
11
12 enum bch_validate_flags {
13 BCH_VALIDATE_write = BIT(0),
14 BCH_VALIDATE_commit = BIT(1),
15 BCH_VALIDATE_journal = BIT(2),
16 BCH_VALIDATE_silent = BIT(3),
17 };
18
19 #if 0
20
21 /*
22 * compiled unpack functions are disabled, pending a new interface for
23 * dynamically allocating executable memory:
24 */
25
26 #ifdef CONFIG_X86_64
27 #define HAVE_BCACHEFS_COMPILED_UNPACK 1
28 #endif
29 #endif
30
31 void bch2_bkey_packed_to_binary_text(struct printbuf *,
32 const struct bkey_format *,
33 const struct bkey_packed *);
34
35 enum bkey_lr_packed {
36 BKEY_PACKED_BOTH,
37 BKEY_PACKED_RIGHT,
38 BKEY_PACKED_LEFT,
39 BKEY_PACKED_NONE,
40 };
41
42 #define bkey_lr_packed(_l, _r) \
43 ((_l)->format + ((_r)->format << 1))
44
45 static inline void bkey_p_copy(struct bkey_packed *dst, const struct bkey_packed *src)
46 {
47 memcpy_u64s_small(dst, src, src->u64s);
48 }
49
50 static inline void bkey_copy(struct bkey_i *dst, const struct bkey_i *src)
51 {
52 memcpy_u64s_small(dst, src, src->k.u64s);
53 }
54
55 struct btree;
56
57 __pure
58 unsigned bch2_bkey_greatest_differing_bit(const struct btree *,
59 const struct bkey_packed *,
60 const struct bkey_packed *);
61 __pure
62 unsigned bch2_bkey_ffs(const struct btree *, const struct bkey_packed *);
63
64 __pure
65 int __bch2_bkey_cmp_packed_format_checked(const struct bkey_packed *,
66 const struct bkey_packed *,
67 const struct btree *);
68
69 __pure
70 int __bch2_bkey_cmp_left_packed_format_checked(const struct btree *,
71 const struct bkey_packed *,
72 const struct bpos *);
73
74 __pure
75 int bch2_bkey_cmp_packed(const struct btree *,
76 const struct bkey_packed *,
77 const struct bkey_packed *);
78
79 __pure
80 int __bch2_bkey_cmp_left_packed(const struct btree *,
81 const struct bkey_packed *,
82 const struct bpos *);
83
84 static inline __pure
85 int bkey_cmp_left_packed(const struct btree *b,
86 const struct bkey_packed *l, const struct bpos *r)
87 {
88 return __bch2_bkey_cmp_left_packed(b, l, r);
89 }
90
91 /*
92 * The compiler generates better code when we pass bpos by ref, but it's often
93 * enough terribly convenient to pass it by val... as much as I hate c++, const
94 * ref would be nice here:
95 */
96 __pure __flatten
97 static inline int bkey_cmp_left_packed_byval(const struct btree *b,
98 const struct bkey_packed *l,
99 struct bpos r)
100 {
101 return bkey_cmp_left_packed(b, l, &r);
102 }
103
104 static __always_inline bool bpos_eq(struct bpos l, struct bpos r)
105 {
106 return !((l.inode ^ r.inode) |
107 (l.offset ^ r.offset) |
108 (l.snapshot ^ r.snapshot));
109 }
110
111 static __always_inline bool bpos_lt(struct bpos l, struct bpos r)
112 {
113 return l.inode != r.inode ? l.inode < r.inode :
114 l.offset != r.offset ? l.offset < r.offset :
115 l.snapshot != r.snapshot ? l.snapshot < r.snapshot : false;
116 }
117
118 static __always_inline bool bpos_le(struct bpos l, struct bpos r)
119 {
120 return l.inode != r.inode ? l.inode < r.inode :
121 l.offset != r.offset ? l.offset < r.offset :
122 l.snapshot != r.snapshot ? l.snapshot < r.snapshot : true;
123 }
124
125 static __always_inline bool bpos_gt(struct bpos l, struct bpos r)
126 {
127 return bpos_lt(r, l);
128 }
129
130 static __always_inline bool bpos_ge(struct bpos l, struct bpos r)
131 {
132 return bpos_le(r, l);
133 }
134
135 static __always_inline int bpos_cmp(struct bpos l, struct bpos r)
136 {
137 return cmp_int(l.inode, r.inode) ?:
138 cmp_int(l.offset, r.offset) ?:
139 cmp_int(l.snapshot, r.snapshot);
140 }
141
142 static inline struct bpos bpos_min(struct bpos l, struct bpos r)
143 {
144 return bpos_lt(l, r) ? l : r;
145 }
146
147 static inline struct bpos bpos_max(struct bpos l, struct bpos r)
148 {
149 return bpos_gt(l, r) ? l : r;
150 }
151
152 static __always_inline bool bkey_eq(struct bpos l, struct bpos r)
153 {
154 return !((l.inode ^ r.inode) |
155 (l.offset ^ r.offset));
156 }
157
158 static __always_inline bool bkey_lt(struct bpos l, struct bpos r)
159 {
160 return l.inode != r.inode
161 ? l.inode < r.inode
162 : l.offset < r.offset;
163 }
164
165 static __always_inline bool bkey_le(struct bpos l, struct bpos r)
166 {
167 return l.inode != r.inode
168 ? l.inode < r.inode
169 : l.offset <= r.offset;
170 }
171
172 static __always_inline bool bkey_gt(struct bpos l, struct bpos r)
173 {
174 return bkey_lt(r, l);
175 }
176
177 static __always_inline bool bkey_ge(struct bpos l, struct bpos r)
178 {
179 return bkey_le(r, l);
180 }
181
182 static __always_inline int bkey_cmp(struct bpos l, struct bpos r)
183 {
184 return cmp_int(l.inode, r.inode) ?:
185 cmp_int(l.offset, r.offset);
186 }
187
188 static inline struct bpos bkey_min(struct bpos l, struct bpos r)
189 {
190 return bkey_lt(l, r) ? l : r;
191 }
192
193 static inline struct bpos bkey_max(struct bpos l, struct bpos r)
194 {
195 return bkey_gt(l, r) ? l : r;
196 }
197
198 static inline bool bkey_and_val_eq(struct bkey_s_c l, struct bkey_s_c r)
199 {
200 return bpos_eq(l.k->p, r.k->p) &&
201 bkey_bytes(l.k) == bkey_bytes(r.k) &&
202 !memcmp(l.v, r.v, bkey_val_bytes(l.k));
203 }
204
205 void bch2_bpos_swab(struct bpos *);
206 void bch2_bkey_swab_key(const struct bkey_format *, struct bkey_packed *);
207
208 static __always_inline int bversion_cmp(struct bversion l, struct bversion r)
209 {
210 return cmp_int(l.hi, r.hi) ?:
211 cmp_int(l.lo, r.lo);
212 }
213
214 #define ZERO_VERSION ((struct bversion) { .hi = 0, .lo = 0 })
215 #define MAX_VERSION ((struct bversion) { .hi = ~0, .lo = ~0ULL })
216
217 static __always_inline int bversion_zero(struct bversion v)
218 {
219 return !bversion_cmp(v, ZERO_VERSION);
220 }
221
222 #ifdef CONFIG_BCACHEFS_DEBUG
223 /* statement expressions confusing unlikely()? */
224 #define bkey_packed(_k) \
225 ({ EBUG_ON((_k)->format > KEY_FORMAT_CURRENT); \
226 (_k)->format != KEY_FORMAT_CURRENT; })
227 #else
228 #define bkey_packed(_k) ((_k)->format != KEY_FORMAT_CURRENT)
229 #endif
230
231 /*
232 * It's safe to treat an unpacked bkey as a packed one, but not the reverse
233 */
234 static inline struct bkey_packed *bkey_to_packed(struct bkey_i *k)
235 {
236 return (struct bkey_packed *) k;
237 }
238
239 static inline const struct bkey_packed *bkey_to_packed_c(const struct bkey_i *k)
240 {
241 return (const struct bkey_packed *) k;
242 }
243
244 static inline struct bkey_i *packed_to_bkey(struct bkey_packed *k)
245 {
246 return bkey_packed(k) ? NULL : (struct bkey_i *) k;
247 }
248
249 static inline const struct bkey *packed_to_bkey_c(const struct bkey_packed *k)
250 {
251 return bkey_packed(k) ? NULL : (const struct bkey *) k;
252 }
253
254 static inline unsigned bkey_format_key_bits(const struct bkey_format *format)
255 {
256 return format->bits_per_field[BKEY_FIELD_INODE] +
257 format->bits_per_field[BKEY_FIELD_OFFSET] +
258 format->bits_per_field[BKEY_FIELD_SNAPSHOT];
259 }
260
261 static inline struct bpos bpos_successor(struct bpos p)
262 {
263 if (!++p.snapshot &&
264 !++p.offset &&
265 !++p.inode)
266 BUG();
267
268 return p;
269 }
270
271 static inline struct bpos bpos_predecessor(struct bpos p)
272 {
273 if (!p.snapshot-- &&
274 !p.offset-- &&
275 !p.inode--)
276 BUG();
277
278 return p;
279 }
280
281 static inline struct bpos bpos_nosnap_successor(struct bpos p)
282 {
283 p.snapshot = 0;
284
285 if (!++p.offset &&
286 !++p.inode)
287 BUG();
288
289 return p;
290 }
291
292 static inline struct bpos bpos_nosnap_predecessor(struct bpos p)
293 {
294 p.snapshot = 0;
295
296 if (!p.offset-- &&
297 !p.inode--)
298 BUG();
299
300 return p;
301 }
302
303 static inline u64 bkey_start_offset(const struct bkey *k)
304 {
305 return k->p.offset - k->size;
306 }
307
308 static inline struct bpos bkey_start_pos(const struct bkey *k)
309 {
310 return (struct bpos) {
311 .inode = k->p.inode,
312 .offset = bkey_start_offset(k),
313 .snapshot = k->p.snapshot,
314 };
315 }
316
317 /* Packed helpers */
318
319 static inline unsigned bkeyp_key_u64s(const struct bkey_format *format,
320 const struct bkey_packed *k)
321 {
322 return bkey_packed(k) ? format->key_u64s : BKEY_U64s;
323 }
324
325 static inline bool bkeyp_u64s_valid(const struct bkey_format *f,
326 const struct bkey_packed *k)
327 {
328 return ((unsigned) k->u64s - bkeyp_key_u64s(f, k) <= U8_MAX - BKEY_U64s);
329 }
330
331 static inline unsigned bkeyp_key_bytes(const struct bkey_format *format,
332 const struct bkey_packed *k)
333 {
334 return bkeyp_key_u64s(format, k) * sizeof(u64);
335 }
336
337 static inline unsigned bkeyp_val_u64s(const struct bkey_format *format,
338 const struct bkey_packed *k)
339 {
340 return k->u64s - bkeyp_key_u64s(format, k);
341 }
342
343 static inline size_t bkeyp_val_bytes(const struct bkey_format *format,
344 const struct bkey_packed *k)
345 {
346 return bkeyp_val_u64s(format, k) * sizeof(u64);
347 }
348
349 static inline void set_bkeyp_val_u64s(const struct bkey_format *format,
350 struct bkey_packed *k, unsigned val_u64s)
351 {
352 k->u64s = bkeyp_key_u64s(format, k) + val_u64s;
353 }
354
355 #define bkeyp_val(_format, _k) \
356 ((struct bch_val *) ((u64 *) (_k)->_data + bkeyp_key_u64s(_format, _k)))
357
358 extern const struct bkey_format bch2_bkey_format_current;
359
360 bool bch2_bkey_transform(const struct bkey_format *,
361 struct bkey_packed *,
362 const struct bkey_format *,
363 const struct bkey_packed *);
364
365 struct bkey __bch2_bkey_unpack_key(const struct bkey_format *,
366 const struct bkey_packed *);
367
368 #ifndef HAVE_BCACHEFS_COMPILED_UNPACK
369 struct bpos __bkey_unpack_pos(const struct bkey_format *,
370 const struct bkey_packed *);
371 #endif
372
373 bool bch2_bkey_pack_key(struct bkey_packed *, const struct bkey *,
374 const struct bkey_format *);
375
376 enum bkey_pack_pos_ret {
377 BKEY_PACK_POS_EXACT,
378 BKEY_PACK_POS_SMALLER,
379 BKEY_PACK_POS_FAIL,
380 };
381
382 enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *, struct bpos,
383 const struct btree *);
384
385 static inline bool bkey_pack_pos(struct bkey_packed *out, struct bpos in,
386 const struct btree *b)
387 {
388 return bch2_bkey_pack_pos_lossy(out, in, b) == BKEY_PACK_POS_EXACT;
389 }
390
391 void bch2_bkey_unpack(const struct btree *, struct bkey_i *,
392 const struct bkey_packed *);
393 bool bch2_bkey_pack(struct bkey_packed *, const struct bkey_i *,
394 const struct bkey_format *);
395
396 typedef void (*compiled_unpack_fn)(struct bkey *, const struct bkey_packed *);
397
398 static inline void
399 __bkey_unpack_key_format_checked(const struct btree *b,
400 struct bkey *dst,
401 const struct bkey_packed *src)
402 {
403 if (IS_ENABLED(HAVE_BCACHEFS_COMPILED_UNPACK)) {
404 compiled_unpack_fn unpack_fn = b->aux_data;
405 unpack_fn(dst, src);
406
407 if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG) &&
408 bch2_expensive_debug_checks) {
409 struct bkey dst2 = __bch2_bkey_unpack_key(&b->format, src);
410
411 BUG_ON(memcmp(dst, &dst2, sizeof(*dst)));
412 }
413 } else {
414 *dst = __bch2_bkey_unpack_key(&b->format, src);
415 }
416 }
417
418 static inline struct bkey
419 bkey_unpack_key_format_checked(const struct btree *b,
420 const struct bkey_packed *src)
421 {
422 struct bkey dst;
423
424 __bkey_unpack_key_format_checked(b, &dst, src);
425 return dst;
426 }
427
428 static inline void __bkey_unpack_key(const struct btree *b,
429 struct bkey *dst,
430 const struct bkey_packed *src)
431 {
432 if (likely(bkey_packed(src)))
433 __bkey_unpack_key_format_checked(b, dst, src);
434 else
435 *dst = *packed_to_bkey_c(src);
436 }
437
438 /**
439 * bkey_unpack_key -- unpack just the key, not the value
440 */
441 static inline struct bkey bkey_unpack_key(const struct btree *b,
442 const struct bkey_packed *src)
443 {
444 return likely(bkey_packed(src))
445 ? bkey_unpack_key_format_checked(b, src)
446 : *packed_to_bkey_c(src);
447 }
448
449 static inline struct bpos
450 bkey_unpack_pos_format_checked(const struct btree *b,
451 const struct bkey_packed *src)
452 {
453 #ifdef HAVE_BCACHEFS_COMPILED_UNPACK
454 return bkey_unpack_key_format_checked(b, src).p;
455 #else
456 return __bkey_unpack_pos(&b->format, src);
457 #endif
458 }
459
460 static inline struct bpos bkey_unpack_pos(const struct btree *b,
461 const struct bkey_packed *src)
462 {
463 return likely(bkey_packed(src))
464 ? bkey_unpack_pos_format_checked(b, src)
465 : packed_to_bkey_c(src)->p;
466 }
467
468 /* Disassembled bkeys */
469
470 static inline struct bkey_s_c bkey_disassemble(const struct btree *b,
471 const struct bkey_packed *k,
472 struct bkey *u)
473 {
474 __bkey_unpack_key(b, u, k);
475
476 return (struct bkey_s_c) { u, bkeyp_val(&b->format, k), };
477 }
478
479 /* non const version: */
480 static inline struct bkey_s __bkey_disassemble(const struct btree *b,
481 struct bkey_packed *k,
482 struct bkey *u)
483 {
484 __bkey_unpack_key(b, u, k);
485
486 return (struct bkey_s) { .k = u, .v = bkeyp_val(&b->format, k), };
487 }
488
489 static inline u64 bkey_field_max(const struct bkey_format *f,
490 enum bch_bkey_fields nr)
491 {
492 return f->bits_per_field[nr] < 64
493 ? (le64_to_cpu(f->field_offset[nr]) +
494 ~(~0ULL << f->bits_per_field[nr]))
495 : U64_MAX;
496 }
497
498 #ifdef HAVE_BCACHEFS_COMPILED_UNPACK
499
500 int bch2_compile_bkey_format(const struct bkey_format *, void *);
501
502 #else
503
504 static inline int bch2_compile_bkey_format(const struct bkey_format *format,
505 void *out) { return 0; }
506
507 #endif
508
509 static inline void bkey_reassemble(struct bkey_i *dst,
510 struct bkey_s_c src)
511 {
512 dst->k = *src.k;
513 memcpy_u64s_small(&dst->v, src.v, bkey_val_u64s(src.k));
514 }
515
516 /* byte order helpers */
517
518 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
519
520 static inline unsigned high_word_offset(const struct bkey_format *f)
521 {
522 return f->key_u64s - 1;
523 }
524
525 #define high_bit_offset 0
526 #define nth_word(p, n) ((p) - (n))
527
528 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
529
530 static inline unsigned high_word_offset(const struct bkey_format *f)
531 {
532 return 0;
533 }
534
535 #define high_bit_offset KEY_PACKED_BITS_START
536 #define nth_word(p, n) ((p) + (n))
537
538 #else
539 #error edit for your odd byteorder.
540 #endif
541
542 #define high_word(f, k) ((u64 *) (k)->_data + high_word_offset(f))
543 #define next_word(p) nth_word(p, 1)
544 #define prev_word(p) nth_word(p, -1)
545
546 #ifdef CONFIG_BCACHEFS_DEBUG
547 void bch2_bkey_pack_test(void);
548 #else
549 static inline void bch2_bkey_pack_test(void) {}
550 #endif
551
552 #define bkey_fields() \
553 x(BKEY_FIELD_INODE, p.inode) \
554 x(BKEY_FIELD_OFFSET, p.offset) \
555 x(BKEY_FIELD_SNAPSHOT, p.snapshot) \
556 x(BKEY_FIELD_SIZE, size) \
557 x(BKEY_FIELD_VERSION_HI, version.hi) \
558 x(BKEY_FIELD_VERSION_LO, version.lo)
559
560 struct bkey_format_state {
561 u64 field_min[BKEY_NR_FIELDS];
562 u64 field_max[BKEY_NR_FIELDS];
563 };
564
565 void bch2_bkey_format_init(struct bkey_format_state *);
566
567 static inline void __bkey_format_add(struct bkey_format_state *s, unsigned field, u64 v)
568 {
569 s->field_min[field] = min(s->field_min[field], v);
570 s->field_max[field] = max(s->field_max[field], v);
571 }
572
573 /*
574 * Changes @format so that @k can be successfully packed with @format
575 */
576 static inline void bch2_bkey_format_add_key(struct bkey_format_state *s, const struct bkey *k)
577 {
578 #define x(id, field) __bkey_format_add(s, id, k->field);
579 bkey_fields()
580 #undef x
581 }
582
583 void bch2_bkey_format_add_pos(struct bkey_format_state *, struct bpos);
584 struct bkey_format bch2_bkey_format_done(struct bkey_format_state *);
585
586 static inline bool bch2_bkey_format_field_overflows(struct bkey_format *f, unsigned i)
587 {
588 unsigned f_bits = f->bits_per_field[i];
589 unsigned unpacked_bits = bch2_bkey_format_current.bits_per_field[i];
590 u64 unpacked_mask = ~((~0ULL << 1) << (unpacked_bits - 1));
591 u64 field_offset = le64_to_cpu(f->field_offset[i]);
592
593 if (f_bits > unpacked_bits)
594 return true;
595
596 if ((f_bits == unpacked_bits) && field_offset)
597 return true;
598
599 u64 f_mask = f_bits
600 ? ~((~0ULL << (f_bits - 1)) << 1)
601 : 0;
602
603 if (((field_offset + f_mask) & unpacked_mask) < field_offset)
604 return true;
605 return false;
606 }
607
608 int bch2_bkey_format_invalid(struct bch_fs *, struct bkey_format *,
609 enum bch_validate_flags, struct printbuf *);
610 void bch2_bkey_format_to_text(struct printbuf *, const struct bkey_format *);
611
612 #endif /* _BCACHEFS_BKEY_H */
613
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.