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 9 typedef int (*sort_cmp_fn)(struct btree *, 10 struct bkey_packed *, 11 struct bkey_packed *); 12 13 static inline bool sort_iter_end(struct sort_iter *iter) 14 { 15 return !iter->used; 16 } 17 18 static 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 30 static 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 38 static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter) 39 { 40 return !sort_iter_end(iter) ? iter->data->k : NULL; 41 } 42 43 static 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 59 static 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 */ 73 static 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 81 static 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 94 struct btree_nr_keys 95 bch2_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: */ 122 struct btree_nr_keys 123 bch2_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 157 static 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 166 unsigned 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