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)(const struct btree *, 10 const struct bkey_packed *, 11 const 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(const struct btree *b, 74 const struct bkey_packed *l, 75 const 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 keep_unwritten_whiteouts_cmp(const struct btree *b, 158 const struct bkey_packed *l, 159 const 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 (long) l - (long) r; 164 } 165 166 #include "btree_update_interior.h" 167 168 /* 169 * For sorting in the btree node write path: whiteouts not in the unwritten 170 * whiteouts area are dropped, whiteouts in the unwritten whiteouts area are 171 * dropped if overwritten by real keys: 172 */ 173 unsigned bch2_sort_keys_keep_unwritten_whiteouts(struct bkey_packed *dst, struct sort_iter *iter) 174 { 175 struct bkey_packed *in, *next, *out = dst; 176 177 sort_iter_sort(iter, keep_unwritten_whiteouts_cmp); 178 179 while ((in = sort_iter_next(iter, keep_unwritten_whiteouts_cmp))) { 180 if (bkey_deleted(in) && in < unwritten_whiteouts_start(iter->b)) 181 continue; 182 183 if ((next = sort_iter_peek(iter)) && 184 !bch2_bkey_cmp_packed_inlined(iter->b, in, next)) 185 continue; 186 187 bkey_p_copy(out, in); 188 out = bkey_p_next(out); 189 } 190 191 return (u64 *) out - (u64 *) dst; 192 } 193 194 /* 195 * Main sort routine for compacting a btree node in memory: we always drop 196 * whiteouts because any whiteouts that need to be written are in the unwritten 197 * whiteouts area: 198 */ 199 unsigned bch2_sort_keys(struct bkey_packed *dst, struct sort_iter *iter) 200 { 201 struct bkey_packed *in, *out = dst; 202 203 sort_iter_sort(iter, bch2_bkey_cmp_packed_inlined); 204 205 while ((in = sort_iter_next(iter, bch2_bkey_cmp_packed_inlined))) { 206 if (bkey_deleted(in)) 207 continue; 208 209 bkey_p_copy(out, in); 210 out = bkey_p_next(out); 211 } 212 213 return (u64 *) out - (u64 *) dst; 214 } 215