Commit | Line | Data |
---|---|---|
5b8a9227 KO |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #include "bcachefs.h" | |
07a1006a | 3 | #include "bkey_buf.h" |
e5baf3da | 4 | #include "bkey_cmp.h" |
5b8a9227 KO |
5 | #include "bkey_sort.h" |
6 | #include "bset.h" | |
7 | #include "extents.h" | |
8 | ||
5dfd3746 KO |
9 | typedef int (*sort_cmp_fn)(const struct btree *, |
10 | const struct bkey_packed *, | |
11 | const struct bkey_packed *); | |
5b8a9227 | 12 | |
ae2f17d5 | 13 | static inline bool sort_iter_end(struct sort_iter *iter) |
5b8a9227 KO |
14 | { |
15 | return !iter->used; | |
16 | } | |
17 | ||
f2785955 KO |
18 | static inline void sort_iter_sift(struct sort_iter *iter, unsigned from, |
19 | sort_cmp_fn cmp) | |
5b8a9227 KO |
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 | ||
5b8a9227 KO |
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--) | |
f2785955 | 35 | sort_iter_sift(iter, i, cmp); |
5b8a9227 KO |
36 | } |
37 | ||
38 | static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter) | |
39 | { | |
ae2f17d5 | 40 | return !sort_iter_end(iter) ? iter->data->k : NULL; |
5b8a9227 KO |
41 | } |
42 | ||
f2785955 | 43 | static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp) |
5b8a9227 | 44 | { |
f2785955 | 45 | struct sort_iter_set *i = iter->data; |
5b8a9227 | 46 | |
f2785955 | 47 | BUG_ON(!iter->used); |
5b8a9227 | 48 | |
ac2ccddc | 49 | i->k = bkey_p_next(i->k); |
ae2f17d5 KO |
50 | |
51 | BUG_ON(i->k > i->end); | |
52 | ||
53 | if (i->k == i->end) | |
f2785955 | 54 | array_remove_item(iter->data, iter->used, 0); |
5b8a9227 | 55 | else |
f2785955 | 56 | sort_iter_sift(iter, 0, cmp); |
5b8a9227 KO |
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 | /* | |
ae2f17d5 | 71 | * If keys compare equal, compare by pointer order: |
5b8a9227 | 72 | */ |
5dfd3746 KO |
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) | |
5b8a9227 | 76 | { |
811d2bcd | 77 | return bch2_bkey_cmp_packed(b, l, r) ?: |
ae2f17d5 KO |
78 | cmp_int((unsigned long) l, (unsigned long) r); |
79 | } | |
5b8a9227 | 80 | |
ae2f17d5 KO |
81 | static inline bool should_drop_next_key(struct sort_iter *iter) |
82 | { | |
5b8a9227 KO |
83 | /* |
84 | * key_sort_cmp() ensures that when keys compare equal the older key | |
ae2f17d5 KO |
85 | * comes first; so if l->k compares equal to r->k then l->k is older |
86 | * and should be dropped. | |
5b8a9227 | 87 | */ |
ae2f17d5 | 88 | return iter->used >= 2 && |
811d2bcd | 89 | !bch2_bkey_cmp_packed(iter->b, |
ae2f17d5 KO |
90 | iter->data[0].k, |
91 | iter->data[1].k); | |
5b8a9227 KO |
92 | } |
93 | ||
ae2f17d5 KO |
94 | struct btree_nr_keys |
95 | bch2_key_sort_fix_overlapping(struct bch_fs *c, struct bset *dst, | |
96 | struct sort_iter *iter) | |
5b8a9227 KO |
97 | { |
98 | struct bkey_packed *out = dst->start; | |
ae2f17d5 | 99 | struct bkey_packed *k; |
5b8a9227 KO |
100 | struct btree_nr_keys nr; |
101 | ||
102 | memset(&nr, 0, sizeof(nr)); | |
103 | ||
ae2f17d5 | 104 | sort_iter_sort(iter, key_sort_fix_overlapping_cmp); |
5b8a9227 | 105 | |
ae2f17d5 | 106 | while ((k = sort_iter_peek(iter))) { |
c052cf82 | 107 | if (!bkey_deleted(k) && |
ae2f17d5 | 108 | !should_drop_next_key(iter)) { |
a8958a1a | 109 | bkey_p_copy(out, k); |
5b8a9227 | 110 | btree_keys_account_key_add(&nr, 0, out); |
ac2ccddc | 111 | out = bkey_p_next(out); |
5b8a9227 KO |
112 | } |
113 | ||
ae2f17d5 | 114 | sort_iter_advance(iter, key_sort_fix_overlapping_cmp); |
5b8a9227 KO |
115 | } |
116 | ||
117 | dst->u64s = cpu_to_le16((u64 *) out - dst->_data); | |
118 | return nr; | |
119 | } | |
120 | ||
5b8a9227 | 121 | /* Sort + repack in a new format: */ |
26609b61 | 122 | struct btree_nr_keys |
5b8a9227 KO |
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; | |
7a0e4afb | 131 | bool transform = memcmp(out_f, &src->format, sizeof(*out_f)); |
5b8a9227 KO |
132 | |
133 | memset(&nr, 0, sizeof(nr)); | |
134 | ||
135 | while ((in = bch2_btree_node_iter_next_all(src_iter, src))) { | |
c052cf82 | 136 | if (filter_whiteouts && bkey_deleted(in)) |
5b8a9227 KO |
137 | continue; |
138 | ||
7a0e4afb | 139 | if (!transform) |
a8958a1a | 140 | bkey_p_copy(out, in); |
7a0e4afb KO |
141 | else if (bch2_bkey_transform(out_f, out, bkey_packed(in) |
142 | ? in_f : &bch2_bkey_format_current, in)) | |
5b8a9227 KO |
143 | out->format = KEY_FORMAT_LOCAL_BTREE; |
144 | else | |
145 | bch2_bkey_unpack(src, (void *) out, in); | |
146 | ||
4fcdd6ec KO |
147 | out->needs_whiteout = false; |
148 | ||
5b8a9227 | 149 | btree_keys_account_key_add(&nr, 0, out); |
ac2ccddc | 150 | out = bkey_p_next(out); |
5b8a9227 KO |
151 | } |
152 | ||
153 | dst->u64s = cpu_to_le16((u64 *) out - dst->_data); | |
154 | return nr; | |
155 | } | |
156 | ||
5dfd3746 KO |
157 | static inline int keep_unwritten_whiteouts_cmp(const struct btree *b, |
158 | const struct bkey_packed *l, | |
159 | const struct bkey_packed *r) | |
5b8a9227 | 160 | { |
e5baf3da | 161 | return bch2_bkey_cmp_packed_inlined(b, l, r) ?: |
bcd6f3e0 | 162 | (int) bkey_deleted(r) - (int) bkey_deleted(l) ?: |
5dfd3746 | 163 | (long) l - (long) r; |
5b8a9227 KO |
164 | } |
165 | ||
5dfd3746 KO |
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) | |
5b8a9227 | 174 | { |
5b8a9227 KO |
175 | struct bkey_packed *in, *next, *out = dst; |
176 | ||
5dfd3746 | 177 | sort_iter_sort(iter, keep_unwritten_whiteouts_cmp); |
5b8a9227 | 178 | |
5dfd3746 KO |
179 | while ((in = sort_iter_next(iter, keep_unwritten_whiteouts_cmp))) { |
180 | if (bkey_deleted(in) && in < unwritten_whiteouts_start(iter->b)) | |
181 | continue; | |
a965ef49 | 182 | |
5dfd3746 KO |
183 | if ((next = sort_iter_peek(iter)) && |
184 | !bch2_bkey_cmp_packed_inlined(iter->b, in, next)) | |
5b8a9227 KO |
185 | continue; |
186 | ||
5dfd3746 KO |
187 | bkey_p_copy(out, in); |
188 | out = bkey_p_next(out); | |
189 | } | |
5b8a9227 | 190 | |
5dfd3746 KO |
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); | |
ac2ccddc | 210 | out = bkey_p_next(out); |
5b8a9227 KO |
211 | } |
212 | ||
213 | return (u64 *) out - (u64 *) dst; | |
214 | } |