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, from: 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, from: 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, cmp: 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(dst: out, src: k); |
110 | btree_keys_account_key_add(&nr, 0, out); |
111 | out = bkey_p_next(out); |
112 | } |
113 | |
114 | sort_iter_advance(iter, cmp: 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(p: out_f, q: &src->format, size: sizeof(*out_f)); |
132 | |
133 | memset(&nr, 0, sizeof(nr)); |
134 | |
135 | while ((in = bch2_btree_node_iter_next_all(iter: src_iter, b: src))) { |
136 | if (filter_whiteouts && bkey_deleted(in)) |
137 | continue; |
138 | |
139 | if (!transform) |
140 | bkey_p_copy(dst: out, src: 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, cmp: sort_keys_cmp); |
174 | |
175 | while ((in = sort_iter_next(iter, cmp: 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(b: iter->b, l: in, r: next)) { |
184 | BUG_ON(in->needs_whiteout && |
185 | next->needs_whiteout); |
186 | needs_whiteout |= in->needs_whiteout; |
187 | in = sort_iter_next(iter, cmp: sort_keys_cmp); |
188 | } |
189 | |
190 | if (bkey_deleted(in)) { |
191 | memcpy_u64s_small(dst: out, src: in, u64s: bkeyp_key_u64s(format: f, k: in)); |
192 | set_bkeyp_val_u64s(format: f, k: out, val_u64s: 0); |
193 | } else { |
194 | bkey_p_copy(dst: out, src: in); |
195 | } |
196 | out->needs_whiteout |= needs_whiteout; |
197 | out = bkey_p_next(out); |
198 | } |
199 | |
200 | return (u64 *) out - (u64 *) dst; |
201 | } |
202 | |