1 // SPDX-License-Identifier: GPL-2.0
3 #include "bkey_on_stack.h"
8 typedef int (*sort_cmp_fn)(struct btree *,
10 struct bkey_packed *);
12 static inline bool sort_iter_end(struct sort_iter *iter)
17 static inline void __sort_iter_sift(struct sort_iter *iter,
25 cmp(iter->b, iter->data[i].k, iter->data[i + 1].k) > 0;
27 swap(iter->data[i], iter->data[i + 1]);
30 static inline void sort_iter_sift(struct sort_iter *iter, sort_cmp_fn cmp)
33 __sort_iter_sift(iter, 0, cmp);
36 static inline void sort_iter_sort(struct sort_iter *iter, sort_cmp_fn cmp)
38 unsigned i = iter->used;
41 __sort_iter_sift(iter, i, cmp);
44 static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter)
46 return !sort_iter_end(iter) ? iter->data->k : NULL;
49 static inline void __sort_iter_advance(struct sort_iter *iter,
50 unsigned idx, sort_cmp_fn cmp)
52 struct sort_iter_set *i = iter->data + idx;
54 BUG_ON(idx >= iter->used);
56 i->k = bkey_next_skip_noops(i->k, i->end);
58 BUG_ON(i->k > i->end);
61 array_remove_item(iter->data, iter->used, idx);
63 __sort_iter_sift(iter, idx, cmp);
66 static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp)
68 __sort_iter_advance(iter, 0, cmp);
71 static inline struct bkey_packed *sort_iter_next(struct sort_iter *iter,
74 struct bkey_packed *ret = sort_iter_peek(iter);
77 sort_iter_advance(iter, cmp);
83 * If keys compare equal, compare by pointer order:
85 static inline int key_sort_fix_overlapping_cmp(struct btree *b,
86 struct bkey_packed *l,
87 struct bkey_packed *r)
89 return bkey_cmp_packed(b, l, r) ?:
90 cmp_int((unsigned long) l, (unsigned long) r);
93 static inline bool should_drop_next_key(struct sort_iter *iter)
96 * key_sort_cmp() ensures that when keys compare equal the older key
97 * comes first; so if l->k compares equal to r->k then l->k is older
98 * and should be dropped.
100 return iter->used >= 2 &&
101 !bkey_cmp_packed(iter->b,
107 bch2_key_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
108 struct sort_iter *iter)
110 struct bkey_packed *out = dst->start;
111 struct bkey_packed *k;
112 struct btree_nr_keys nr;
114 memset(&nr, 0, sizeof(nr));
116 sort_iter_sort(iter, key_sort_fix_overlapping_cmp);
118 while ((k = sort_iter_peek(iter))) {
119 if (!bkey_whiteout(k) &&
120 !should_drop_next_key(iter)) {
122 btree_keys_account_key_add(&nr, 0, out);
123 out = bkey_next(out);
126 sort_iter_advance(iter, key_sort_fix_overlapping_cmp);
129 dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
133 static void extent_sort_append(struct bch_fs *c,
134 struct bkey_format *f,
135 struct btree_nr_keys *nr,
136 struct bkey_packed **out,
139 if (!bkey_whiteout(k.k)) {
140 if (!bch2_bkey_pack_key(*out, k.k, f))
141 memcpy_u64s_small(*out, k.k, BKEY_U64s);
143 memcpy_u64s_small(bkeyp_val(f, *out), k.v, bkey_val_u64s(k.k));
145 btree_keys_account_key_add(nr, 0, *out);
146 *out = bkey_next(*out);
150 /* Sort + repack in a new format: */
152 bch2_sort_repack(struct bset *dst, struct btree *src,
153 struct btree_node_iter *src_iter,
154 struct bkey_format *out_f,
155 bool filter_whiteouts)
157 struct bkey_format *in_f = &src->format;
158 struct bkey_packed *in, *out = vstruct_last(dst);
159 struct btree_nr_keys nr;
161 memset(&nr, 0, sizeof(nr));
163 while ((in = bch2_btree_node_iter_next_all(src_iter, src))) {
164 if (filter_whiteouts && bkey_whiteout(in))
167 if (bch2_bkey_transform(out_f, out, bkey_packed(in)
168 ? in_f : &bch2_bkey_format_current, in))
169 out->format = KEY_FORMAT_LOCAL_BTREE;
171 bch2_bkey_unpack(src, (void *) out, in);
173 btree_keys_account_key_add(&nr, 0, out);
174 out = bkey_next(out);
177 dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
181 /* Sort, repack, and call bch2_bkey_normalize() to drop stale pointers: */
183 bch2_sort_repack_merge(struct bch_fs *c,
184 struct bset *dst, struct btree *src,
185 struct btree_node_iter *iter,
186 struct bkey_format *out_f,
187 bool filter_whiteouts)
189 struct bkey_packed *out = vstruct_last(dst), *k_packed;
190 struct bkey_on_stack k;
191 struct btree_nr_keys nr;
193 memset(&nr, 0, sizeof(nr));
194 bkey_on_stack_init(&k);
196 while ((k_packed = bch2_btree_node_iter_next_all(iter, src))) {
197 if (filter_whiteouts && bkey_whiteout(k_packed))
202 * bch2_bkey_normalize may modify the key we pass it (dropping
203 * stale pointers) and we don't have a write lock on the src
204 * node; we have to make a copy of the entire key before calling
207 bkey_on_stack_realloc(&k, c, k_packed->u64s + BKEY_U64s);
208 bch2_bkey_unpack(src, k.k, k_packed);
210 if (filter_whiteouts &&
211 bch2_bkey_normalize(c, bkey_i_to_s(k.k)))
214 extent_sort_append(c, out_f, &nr, &out, bkey_i_to_s(k.k));
217 dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
218 bkey_on_stack_exit(&k, c);
222 static inline int sort_keys_cmp(struct btree *b,
223 struct bkey_packed *l,
224 struct bkey_packed *r)
226 return bkey_cmp_packed(b, l, r) ?:
227 (int) bkey_deleted(r) - (int) bkey_deleted(l) ?:
228 (int) l->needs_whiteout - (int) r->needs_whiteout;
231 unsigned bch2_sort_keys(struct bkey_packed *dst,
232 struct sort_iter *iter,
233 bool filter_whiteouts)
235 const struct bkey_format *f = &iter->b->format;
236 struct bkey_packed *in, *next, *out = dst;
238 sort_iter_sort(iter, sort_keys_cmp);
240 while ((in = sort_iter_next(iter, sort_keys_cmp))) {
241 bool needs_whiteout = false;
243 if (bkey_whiteout(in) &&
244 (filter_whiteouts || !in->needs_whiteout))
247 while ((next = sort_iter_peek(iter)) &&
248 !bkey_cmp_packed(iter->b, in, next)) {
249 BUG_ON(in->needs_whiteout &&
250 next->needs_whiteout);
251 needs_whiteout |= in->needs_whiteout;
252 in = sort_iter_next(iter, sort_keys_cmp);
255 if (bkey_whiteout(in)) {
256 memcpy_u64s(out, in, bkeyp_key_u64s(f, in));
257 set_bkeyp_val_u64s(f, out, 0);
261 out->needs_whiteout |= needs_whiteout;
262 out = bkey_next(out);
265 return (u64 *) out - (u64 *) dst;
268 /* Compat code for btree_node_old_extent_overwrite: */
271 * If keys compare equal, compare by pointer order:
273 * Necessary for sort_fix_overlapping() - if there are multiple keys that
274 * compare equal in different sets, we have to process them newest to oldest.
276 static inline int extent_sort_fix_overlapping_cmp(struct btree *b,
277 struct bkey_packed *l,
278 struct bkey_packed *r)
280 struct bkey ul = bkey_unpack_key(b, l);
281 struct bkey ur = bkey_unpack_key(b, r);
283 return bkey_cmp(bkey_start_pos(&ul),
284 bkey_start_pos(&ur)) ?:
285 cmp_int((unsigned long) r, (unsigned long) l);
289 * The algorithm in extent_sort_fix_overlapping() relies on keys in the same
290 * bset being ordered by start offset - but 0 size whiteouts (which are always
291 * KEY_TYPE_deleted) break this ordering, so we need to skip over them:
293 static void extent_iter_advance(struct sort_iter *iter, unsigned idx)
295 struct sort_iter_set *i = iter->data + idx;
298 i->k = bkey_next_skip_noops(i->k, i->end);
299 } while (i->k != i->end && bkey_deleted(i->k));
302 array_remove_item(iter->data, iter->used, idx);
304 __sort_iter_sift(iter, idx, extent_sort_fix_overlapping_cmp);
308 bch2_extent_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
309 struct sort_iter *iter)
311 struct btree *b = iter->b;
312 struct bkey_format *f = &b->format;
313 struct sort_iter_set *_l = iter->data, *_r = iter->data + 1;
314 struct bkey_packed *out = dst->start;
315 struct bkey l_unpacked, r_unpacked;
317 struct btree_nr_keys nr;
318 struct bkey_on_stack split;
321 memset(&nr, 0, sizeof(nr));
322 bkey_on_stack_init(&split);
324 sort_iter_sort(iter, extent_sort_fix_overlapping_cmp);
325 for (i = 0; i < iter->used;) {
326 if (bkey_deleted(iter->data[i].k))
327 __sort_iter_advance(iter, i,
328 extent_sort_fix_overlapping_cmp);
333 while (!sort_iter_end(iter)) {
334 l = __bkey_disassemble(b, _l->k, &l_unpacked);
336 if (iter->used == 1) {
337 extent_sort_append(c, f, &nr, &out, l);
338 extent_iter_advance(iter, 0);
342 r = __bkey_disassemble(b, _r->k, &r_unpacked);
344 /* If current key and next key don't overlap, just append */
345 if (bkey_cmp(l.k->p, bkey_start_pos(r.k)) <= 0) {
346 extent_sort_append(c, f, &nr, &out, l);
347 extent_iter_advance(iter, 0);
351 /* Skip 0 size keys */
353 extent_iter_advance(iter, 1);
358 * overlap: keep the newer key and trim the older key so they
359 * don't overlap. comparing pointers tells us which one is
360 * newer, since the bsets are appended one after the other.
363 /* can't happen because of comparison func */
364 BUG_ON(_l->k < _r->k &&
365 !bkey_cmp(bkey_start_pos(l.k), bkey_start_pos(r.k)));
369 if (bkey_cmp(l.k->p, r.k->p) >= 0) {
370 extent_iter_advance(iter, 1);
372 bch2_cut_front_s(l.k->p, r);
373 extent_save(b, _r->k, r.k);
374 __sort_iter_sift(iter, 1,
375 extent_sort_fix_overlapping_cmp);
377 } else if (bkey_cmp(l.k->p, r.k->p) > 0) {
380 * r wins, but it overlaps in the middle of l - split l:
382 bkey_on_stack_reassemble(&split, c, l.s_c);
383 bch2_cut_back(bkey_start_pos(r.k), split.k);
385 bch2_cut_front_s(r.k->p, l);
386 extent_save(b, _l->k, l.k);
388 __sort_iter_sift(iter, 0,
389 extent_sort_fix_overlapping_cmp);
391 extent_sort_append(c, f, &nr, &out,
392 bkey_i_to_s(split.k));
394 bch2_cut_back_s(bkey_start_pos(r.k), l);
395 extent_save(b, _l->k, l.k);
399 dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
401 bkey_on_stack_exit(&split, c);
405 static inline int sort_extents_cmp(struct btree *b,
406 struct bkey_packed *l,
407 struct bkey_packed *r)
409 return bkey_cmp_packed(b, l, r) ?:
410 (int) bkey_deleted(l) - (int) bkey_deleted(r);
413 unsigned bch2_sort_extents(struct bkey_packed *dst,
414 struct sort_iter *iter,
415 bool filter_whiteouts)
417 struct bkey_packed *in, *out = dst;
419 sort_iter_sort(iter, sort_extents_cmp);
421 while ((in = sort_iter_next(iter, sort_extents_cmp))) {
422 if (bkey_deleted(in))
425 if (bkey_whiteout(in) &&
426 (filter_whiteouts || !in->needs_whiteout))
430 out = bkey_next(out);
433 return (u64 *) out - (u64 *) dst;
436 static inline int sort_extent_whiteouts_cmp(struct btree *b,
437 struct bkey_packed *l,
438 struct bkey_packed *r)
440 struct bkey ul = bkey_unpack_key(b, l);
441 struct bkey ur = bkey_unpack_key(b, r);
443 return bkey_cmp(bkey_start_pos(&ul), bkey_start_pos(&ur));
446 unsigned bch2_sort_extent_whiteouts(struct bkey_packed *dst,
447 struct sort_iter *iter)
449 const struct bkey_format *f = &iter->b->format;
450 struct bkey_packed *in, *out = dst;
452 bool prev = false, l_packed = false;
453 u64 max_packed_size = bkey_field_max(f, BKEY_FIELD_SIZE);
454 u64 max_packed_offset = bkey_field_max(f, BKEY_FIELD_OFFSET);
457 max_packed_size = min_t(u64, max_packed_size, KEY_SIZE_MAX);
459 sort_iter_sort(iter, sort_extent_whiteouts_cmp);
461 while ((in = sort_iter_next(iter, sort_extent_whiteouts_cmp))) {
462 if (bkey_deleted(in))
465 EBUG_ON(bkeyp_val_u64s(f, in));
466 EBUG_ON(in->type != KEY_TYPE_discard);
468 r.k = bkey_unpack_key(iter->b, in);
471 bkey_cmp(l.k.p, bkey_start_pos(&r.k)) >= 0) {
472 if (bkey_cmp(l.k.p, r.k.p) >= 0)
476 ? min(max_packed_size, max_packed_offset -
477 bkey_start_offset(&l.k))
480 new_size = min(new_size, r.k.p.offset -
481 bkey_start_offset(&l.k));
483 BUG_ON(new_size < l.k.size);
485 bch2_key_resize(&l.k, new_size);
487 if (bkey_cmp(l.k.p, r.k.p) >= 0)
490 bch2_cut_front(l.k.p, &r);
494 if (!bch2_bkey_pack(out, &l, f)) {
498 out = bkey_next(out);
503 l_packed = bkey_packed(in);
507 if (!bch2_bkey_pack(out, &l, f)) {
511 out = bkey_next(out);
514 return (u64 *) out - (u64 *) dst;