1// SPDX-License-Identifier: GPL-2.0 2#include "bcachefs.h" 3#include "bkey_buf.h" 4#include "bkey_cmp.h" 5#include "bkey_sort.h" 6#include "bset.h" 7#include "extents.h" 8 9typedef int (*sort_cmp_fn)(struct btree *, 10 struct bkey_packed *, 11 struct bkey_packed *); 12 13static inline bool sort_iter_end(struct sort_iter *iter) 14{ 15 return !iter->used; 16} 17 18static inline void sort_iter_sift(struct sort_iter *iter, unsigned from, 19 sort_cmp_fn cmp) 20{ 21 unsigned i; 22 23 for (i = from; 24 i + 1 < iter->used && 25 cmp(iter->b, iter->data[i].k, iter->data[i + 1].k) > 0; 26 i++) 27 swap(iter->data[i], iter->data[i + 1]); 28} 29 30static inline void sort_iter_sort(struct sort_iter *iter, sort_cmp_fn cmp) 31{ 32 unsigned i = iter->used; 33 34 while (i--) 35 sort_iter_sift(iter, i, cmp); 36} 37 38static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter) 39{ 40 return !sort_iter_end(iter) ? iter->data->k : NULL; 41} 42 43static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp) 44{ 45 struct sort_iter_set *i = iter->data; 46 47 BUG_ON(!iter->used); 48 49 i->k = bkey_p_next(i->k); 50 51 BUG_ON(i->k > i->end); 52 53 if (i->k == i->end) 54 array_remove_item(iter->data, iter->used, 0); 55 else 56 sort_iter_sift(iter, 0, cmp); 57} 58 59static inline struct bkey_packed *sort_iter_next(struct sort_iter *iter, 60 sort_cmp_fn cmp) 61{ 62 struct bkey_packed *ret = sort_iter_peek(iter); 63 64 if (ret) 65 sort_iter_advance(iter, cmp); 66 67 return ret; 68} 69 70/* 71 * If keys compare equal, compare by pointer order: 72 */ 73static inline int key_sort_fix_overlapping_cmp(struct btree *b, 74 struct bkey_packed *l, 75 struct bkey_packed *r) 76{ 77 return bch2_bkey_cmp_packed(b, l, r) ?: 78 cmp_int((unsigned long) l, (unsigned long) r); 79} 80 81static inline bool should_drop_next_key(struct sort_iter *iter) 82{ 83 /* 84 * key_sort_cmp() ensures that when keys compare equal the older key 85 * comes first; so if l->k compares equal to r->k then l->k is older 86 * and should be dropped. 87 */ 88 return iter->used >= 2 && 89 !bch2_bkey_cmp_packed(iter->b, 90 iter->data[0].k, 91 iter->data[1].k); 92} 93 94struct btree_nr_keys 95bch2_key_sort_fix_overlapping(struct bch_fs *c, struct bset *dst, 96 struct sort_iter *iter) 97{ 98 struct bkey_packed *out = dst->start; 99 struct bkey_packed *k; 100 struct btree_nr_keys nr; 101 102 memset(&nr, 0, sizeof(nr)); 103 104 sort_iter_sort(iter, key_sort_fix_overlapping_cmp); 105 106 while ((k = sort_iter_peek(iter))) { 107 if (!bkey_deleted(k) && 108 !should_drop_next_key(iter)) { 109 bkey_p_copy(out, k); 110 btree_keys_account_key_add(&nr, 0, out); 111 out = bkey_p_next(out); 112 } 113 114 sort_iter_advance(iter, key_sort_fix_overlapping_cmp); 115 } 116 117 dst->u64s = cpu_to_le16((u64 *) out - dst->_data); 118 return nr; 119} 120 121/* Sort + repack in a new format: */ 122struct btree_nr_keys 123bch2_sort_repack(struct bset *dst, struct btree *src, 124 struct btree_node_iter *src_iter, 125 struct bkey_format *out_f, 126 bool filter_whiteouts) 127{ 128 struct bkey_format *in_f = &src->format; 129 struct bkey_packed *in, *out = vstruct_last(dst); 130 struct btree_nr_keys nr; 131 bool transform = memcmp(out_f, &src->format, sizeof(*out_f)); 132 133 memset(&nr, 0, sizeof(nr)); 134 135 while ((in = bch2_btree_node_iter_next_all(src_iter, src))) { 136 if (filter_whiteouts && bkey_deleted(in)) 137 continue; 138 139 if (!transform) 140 bkey_p_copy(out, in); 141 else if (bch2_bkey_transform(out_f, out, bkey_packed(in) 142 ? in_f : &bch2_bkey_format_current, in)) 143 out->format = KEY_FORMAT_LOCAL_BTREE; 144 else 145 bch2_bkey_unpack(src, (void *) out, in); 146 147 out->needs_whiteout = false; 148 149 btree_keys_account_key_add(&nr, 0, out); 150 out = bkey_p_next(out); 151 } 152 153 dst->u64s = cpu_to_le16((u64 *) out - dst->_data); 154 return nr; 155} 156 157static inline int sort_keys_cmp(struct btree *b, 158 struct bkey_packed *l, 159 struct bkey_packed *r) 160{ 161 return bch2_bkey_cmp_packed_inlined(b, l, r) ?: 162 (int) bkey_deleted(r) - (int) bkey_deleted(l) ?: 163 (int) l->needs_whiteout - (int) r->needs_whiteout; 164} 165 166unsigned bch2_sort_keys(struct bkey_packed *dst, 167 struct sort_iter *iter, 168 bool filter_whiteouts) 169{ 170 const struct bkey_format *f = &iter->b->format; 171 struct bkey_packed *in, *next, *out = dst; 172 173 sort_iter_sort(iter, sort_keys_cmp); 174 175 while ((in = sort_iter_next(iter, sort_keys_cmp))) { 176 bool needs_whiteout = false; 177 178 if (bkey_deleted(in) && 179 (filter_whiteouts || !in->needs_whiteout)) 180 continue; 181 182 while ((next = sort_iter_peek(iter)) && 183 !bch2_bkey_cmp_packed_inlined(iter->b, in, next)) { 184 BUG_ON(in->needs_whiteout && 185 next->needs_whiteout); 186 needs_whiteout |= in->needs_whiteout; 187 in = sort_iter_next(iter, sort_keys_cmp); 188 } 189 190 if (bkey_deleted(in)) { 191 memcpy_u64s_small(out, in, bkeyp_key_u64s(f, in)); 192 set_bkeyp_val_u64s(f, out, 0); 193 } else { 194 bkey_p_copy(out, in); 195 } 196 out->needs_whiteout |= needs_whiteout; 197 out = bkey_p_next(out); 198 } 199 200 return (u64 *) out - (u64 *) dst; 201} 202