btree_io.c (ad44bdc351faeacb9b7294f1689ac76babf379ad) btree_io.c (c9bebae65eade6529f9d3068a6da42fc56664bfe)
1// SPDX-License-Identifier: GPL-2.0
2
3#include "bcachefs.h"
4#include "bkey_methods.h"
5#include "bkey_sort.h"
6#include "btree_cache.h"
7#include "btree_io.h"
8#include "btree_iter.h"

--- 65 unchanged lines hidden (view full) ---

74 p = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT, order);
75 if (p)
76 return p;
77
78 *used_mempool = true;
79 return mempool_alloc(&c->btree_bounce_pool, GFP_NOIO);
80}
81
1// SPDX-License-Identifier: GPL-2.0
2
3#include "bcachefs.h"
4#include "bkey_methods.h"
5#include "bkey_sort.h"
6#include "btree_cache.h"
7#include "btree_io.h"
8#include "btree_iter.h"

--- 65 unchanged lines hidden (view full) ---

74 p = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT, order);
75 if (p)
76 return p;
77
78 *used_mempool = true;
79 return mempool_alloc(&c->btree_bounce_pool, GFP_NOIO);
80}
81
82static void sort_bkey_ptrs(const struct btree *bt,
83 struct bkey_packed **ptrs, unsigned nr)
84{
85 unsigned n = nr, a = nr / 2, b, c, d;
86
87 if (!a)
88 return;
89
90 /* Heap sort: see lib/sort.c: */
91 while (1) {
92 if (a)
93 a--;
94 else if (--n)
95 swap(ptrs[0], ptrs[n]);
96 else
97 break;
98
99 for (b = a; c = 2 * b + 1, (d = c + 1) < n;)
100 b = bkey_cmp_packed(bt,
101 ptrs[c],
102 ptrs[d]) >= 0 ? c : d;
103 if (d == n)
104 b = c;
105
106 while (b != a &&
107 bkey_cmp_packed(bt,
108 ptrs[a],
109 ptrs[b]) >= 0)
110 b = (b - 1) / 2;
111 c = b;
112 while (b != a) {
113 b = (b - 1) / 2;
114 swap(ptrs[b], ptrs[c]);
115 }
116 }
117}
118
119static void bch2_sort_whiteouts(struct bch_fs *c, struct btree *b)
120{
121 struct bkey_packed *new_whiteouts, **whiteout_ptrs, *k;
122 bool used_mempool1 = false, used_mempool2 = false;
123 unsigned order, i, nr = 0;
124
125 if (!b->whiteout_u64s)
126 return;
127
128 order = get_order(b->whiteout_u64s * sizeof(u64));
129
130 new_whiteouts = btree_bounce_alloc(c, order, &used_mempool1);
131 whiteout_ptrs = btree_bounce_alloc(c, order, &used_mempool2);
132
133 for (k = unwritten_whiteouts_start(c, b);
134 k != unwritten_whiteouts_end(c, b);
135 k = bkey_next(k))
136 whiteout_ptrs[nr++] = k;
137
138 sort_bkey_ptrs(b, whiteout_ptrs, nr);
139
140 k = new_whiteouts;
141
142 for (i = 0; i < nr; i++) {
143 bkey_copy(k, whiteout_ptrs[i]);
144 k = bkey_next(k);
145 }
146
147 verify_no_dups(b, new_whiteouts,
148 (void *) ((u64 *) new_whiteouts + b->whiteout_u64s));
149
150 memcpy_u64s(unwritten_whiteouts_start(c, b),
151 new_whiteouts, b->whiteout_u64s);
152
153 btree_bounce_free(c, order, used_mempool2, whiteout_ptrs);
154 btree_bounce_free(c, order, used_mempool1, new_whiteouts);
155}
156
82static unsigned should_compact_bset(struct btree *b, struct bset_tree *t,
83 bool compacting,
84 enum compact_mode mode)
85{
86 unsigned bset_u64s = le16_to_cpu(bset(b, t)->u64s);
87 unsigned dead_u64s = bset_u64s - b->nr.bset_u64s[t - b->set];
88
89 if (mode == COMPACT_LAZY) {

--- 21 unchanged lines hidden (view full) ---

111
112 for_each_bset(b, t)
113 whiteout_u64s += should_compact_bset(b, t,
114 whiteout_u64s != 0, mode);
115
116 if (!whiteout_u64s)
117 return false;
118
157static unsigned should_compact_bset(struct btree *b, struct bset_tree *t,
158 bool compacting,
159 enum compact_mode mode)
160{
161 unsigned bset_u64s = le16_to_cpu(bset(b, t)->u64s);
162 unsigned dead_u64s = bset_u64s - b->nr.bset_u64s[t - b->set];
163
164 if (mode == COMPACT_LAZY) {

--- 21 unchanged lines hidden (view full) ---

186
187 for_each_bset(b, t)
188 whiteout_u64s += should_compact_bset(b, t,
189 whiteout_u64s != 0, mode);
190
191 if (!whiteout_u64s)
192 return false;
193
194 bch2_sort_whiteouts(c, b);
195
119 sort_iter_init(&sort_iter, b);
120
121 whiteout_u64s += b->whiteout_u64s;
122 order = get_order(whiteout_u64s * sizeof(u64));
123
124 whiteouts = btree_bounce_alloc(c, order, &used_mempool);
125 u_start = u_pos = whiteouts;
126

--- 39 unchanged lines hidden (view full) ---

166 out = i->start;
167
168 for (k = start; k != end; k = n) {
169 n = bkey_next_skip_noops(k, end);
170
171 if (bkey_deleted(k) && btree_node_is_extents(b))
172 continue;
173
196 sort_iter_init(&sort_iter, b);
197
198 whiteout_u64s += b->whiteout_u64s;
199 order = get_order(whiteout_u64s * sizeof(u64));
200
201 whiteouts = btree_bounce_alloc(c, order, &used_mempool);
202 u_start = u_pos = whiteouts;
203

--- 39 unchanged lines hidden (view full) ---

243 out = i->start;
244
245 for (k = start; k != end; k = n) {
246 n = bkey_next_skip_noops(k, end);
247
248 if (bkey_deleted(k) && btree_node_is_extents(b))
249 continue;
250
251 BUG_ON(bkey_whiteout(k) &&
252 k->needs_whiteout &&
253 bkey_written(b, k));
254
174 if (bkey_whiteout(k) && !k->needs_whiteout)
175 continue;
176
177 if (bkey_whiteout(k)) {
255 if (bkey_whiteout(k) && !k->needs_whiteout)
256 continue;
257
258 if (bkey_whiteout(k)) {
178 unreserve_whiteout(b, k);
179 memcpy_u64s(u_pos, k, bkeyp_key_u64s(f, k));
180 set_bkeyp_val_u64s(f, u_pos, 0);
181 u_pos = bkey_next(u_pos);
182 } else if (mode != COMPACT_WRITTEN_NO_WRITE_LOCK) {
183 bkey_copy(out, k);
184 out = bkey_next(out);
185 }
186 }

--- 1150 unchanged lines hidden (view full) ---

1337 BUG_ON((b->will_make_reachable != 0) != !b->written);
1338
1339 BUG_ON(b->written >= c->opts.btree_node_size);
1340 BUG_ON(b->written & (c->opts.block_size - 1));
1341 BUG_ON(bset_written(b, btree_bset_last(b)));
1342 BUG_ON(le64_to_cpu(b->data->magic) != bset_magic(c));
1343 BUG_ON(memcmp(&b->data->format, &b->format, sizeof(b->format)));
1344
259 memcpy_u64s(u_pos, k, bkeyp_key_u64s(f, k));
260 set_bkeyp_val_u64s(f, u_pos, 0);
261 u_pos = bkey_next(u_pos);
262 } else if (mode != COMPACT_WRITTEN_NO_WRITE_LOCK) {
263 bkey_copy(out, k);
264 out = bkey_next(out);
265 }
266 }

--- 1150 unchanged lines hidden (view full) ---

1417 BUG_ON((b->will_make_reachable != 0) != !b->written);
1418
1419 BUG_ON(b->written >= c->opts.btree_node_size);
1420 BUG_ON(b->written & (c->opts.block_size - 1));
1421 BUG_ON(bset_written(b, btree_bset_last(b)));
1422 BUG_ON(le64_to_cpu(b->data->magic) != bset_magic(c));
1423 BUG_ON(memcmp(&b->data->format, &b->format, sizeof(b->format)));
1424
1345 /*
1346 * We can't block on six_lock_write() here; another thread might be
1347 * trying to get a journal reservation with read locks held, and getting
1348 * a journal reservation might be blocked on flushing the journal and
1349 * doing btree writes:
1350 */
1351 if (lock_type_held == SIX_LOCK_intent &&
1352 six_trylock_write(&b->c.lock)) {
1353 __bch2_compact_whiteouts(c, b, COMPACT_WRITTEN);
1354 six_unlock_write(&b->c.lock);
1355 } else {
1356 __bch2_compact_whiteouts(c, b, COMPACT_WRITTEN_NO_WRITE_LOCK);
1357 }
1425 bch2_sort_whiteouts(c, b);
1358
1426
1359 BUG_ON(b->uncompacted_whiteout_u64s);
1360
1361 sort_iter_init(&sort_iter, b);
1362
1363 bytes = !b->written
1364 ? sizeof(struct btree_node)
1365 : sizeof(struct btree_node_entry);
1366
1367 bytes += b->whiteout_u64s * sizeof(u64);
1368

--- 171 unchanged lines hidden (view full) ---

1540 bool invalidated_iter = false;
1541 struct btree_node_entry *bne;
1542 struct bset_tree *t;
1543
1544 if (!btree_node_just_written(b))
1545 return false;
1546
1547 BUG_ON(b->whiteout_u64s);
1427 sort_iter_init(&sort_iter, b);
1428
1429 bytes = !b->written
1430 ? sizeof(struct btree_node)
1431 : sizeof(struct btree_node_entry);
1432
1433 bytes += b->whiteout_u64s * sizeof(u64);
1434

--- 171 unchanged lines hidden (view full) ---

1606 bool invalidated_iter = false;
1607 struct btree_node_entry *bne;
1608 struct bset_tree *t;
1609
1610 if (!btree_node_just_written(b))
1611 return false;
1612
1613 BUG_ON(b->whiteout_u64s);
1548 BUG_ON(b->uncompacted_whiteout_u64s);
1549
1550 clear_btree_node_just_written(b);
1551
1552 /*
1553 * Note: immediately after write, bset_written() doesn't work - the
1554 * amount of data we had to write after compaction might have been
1555 * smaller than the offset of the last bset.
1556 *

--- 138 unchanged lines hidden --- 		1614
1615 clear_btree_node_just_written(b);
1616
1617 /*
1618 * Note: immediately after write, bset_written() doesn't work - the
1619 * amount of data we had to write after compaction might have been
1620 * smaller than the offset of the last bset.
1621 *

--- 138 unchanged lines hidden ---