Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 :
3 : #include "messages.h"
4 : #include "tree-mod-log.h"
5 : #include "disk-io.h"
6 : #include "fs.h"
7 : #include "accessors.h"
8 : #include "tree-checker.h"
9 :
10 : struct tree_mod_root {
11 : u64 logical;
12 : u8 level;
13 : };
14 :
15 : struct tree_mod_elem {
16 : struct rb_node node;
17 : u64 logical;
18 : u64 seq;
19 : enum btrfs_mod_log_op op;
20 :
21 : /*
22 : * This is used for BTRFS_MOD_LOG_KEY_* and BTRFS_MOD_LOG_MOVE_KEYS
23 : * operations.
24 : */
25 : int slot;
26 :
27 : /* This is used for BTRFS_MOD_LOG_KEY* and BTRFS_MOD_LOG_ROOT_REPLACE. */
28 : u64 generation;
29 :
30 : /* Those are used for op == BTRFS_MOD_LOG_KEY_{REPLACE,REMOVE}. */
31 : struct btrfs_disk_key key;
32 : u64 blockptr;
33 :
34 : /* This is used for op == BTRFS_MOD_LOG_MOVE_KEYS. */
35 : struct {
36 : int dst_slot;
37 : int nr_items;
38 : } move;
39 :
40 : /* This is used for op == BTRFS_MOD_LOG_ROOT_REPLACE. */
41 : struct tree_mod_root old_root;
42 : };
43 :
44 : /*
45 : * Pull a new tree mod seq number for our operation.
46 : */
47 0 : static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info)
48 : {
49 0 : return atomic64_inc_return(&fs_info->tree_mod_seq);
50 : }
51 :
52 : /*
53 : * This adds a new blocker to the tree mod log's blocker list if the @elem
54 : * passed does not already have a sequence number set. So when a caller expects
55 : * to record tree modifications, it should ensure to set elem->seq to zero
56 : * before calling btrfs_get_tree_mod_seq.
57 : * Returns a fresh, unused tree log modification sequence number, even if no new
58 : * blocker was added.
59 : */
60 0 : u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info,
61 : struct btrfs_seq_list *elem)
62 : {
63 0 : write_lock(&fs_info->tree_mod_log_lock);
64 0 : if (!elem->seq) {
65 0 : elem->seq = btrfs_inc_tree_mod_seq(fs_info);
66 0 : list_add_tail(&elem->list, &fs_info->tree_mod_seq_list);
67 0 : set_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags);
68 : }
69 0 : write_unlock(&fs_info->tree_mod_log_lock);
70 :
71 0 : return elem->seq;
72 : }
73 :
74 0 : void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info,
75 : struct btrfs_seq_list *elem)
76 : {
77 0 : struct rb_root *tm_root;
78 0 : struct rb_node *node;
79 0 : struct rb_node *next;
80 0 : struct tree_mod_elem *tm;
81 0 : u64 min_seq = BTRFS_SEQ_LAST;
82 0 : u64 seq_putting = elem->seq;
83 :
84 0 : if (!seq_putting)
85 : return;
86 :
87 0 : write_lock(&fs_info->tree_mod_log_lock);
88 0 : list_del(&elem->list);
89 0 : elem->seq = 0;
90 :
91 0 : if (list_empty(&fs_info->tree_mod_seq_list)) {
92 0 : clear_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags);
93 : } else {
94 0 : struct btrfs_seq_list *first;
95 :
96 0 : first = list_first_entry(&fs_info->tree_mod_seq_list,
97 : struct btrfs_seq_list, list);
98 0 : if (seq_putting > first->seq) {
99 : /*
100 : * Blocker with lower sequence number exists, we cannot
101 : * remove anything from the log.
102 : */
103 0 : write_unlock(&fs_info->tree_mod_log_lock);
104 0 : return;
105 : }
106 : min_seq = first->seq;
107 : }
108 :
109 : /*
110 : * Anything that's lower than the lowest existing (read: blocked)
111 : * sequence number can be removed from the tree.
112 : */
113 0 : tm_root = &fs_info->tree_mod_log;
114 0 : for (node = rb_first(tm_root); node; node = next) {
115 0 : next = rb_next(node);
116 0 : tm = rb_entry(node, struct tree_mod_elem, node);
117 0 : if (tm->seq >= min_seq)
118 0 : continue;
119 0 : rb_erase(node, tm_root);
120 0 : kfree(tm);
121 : }
122 0 : write_unlock(&fs_info->tree_mod_log_lock);
123 : }
124 :
125 : /*
126 : * Key order of the log:
127 : * node/leaf start address -> sequence
128 : *
129 : * The 'start address' is the logical address of the *new* root node for root
130 : * replace operations, or the logical address of the affected block for all
131 : * other operations.
132 : */
133 0 : static noinline int tree_mod_log_insert(struct btrfs_fs_info *fs_info,
134 : struct tree_mod_elem *tm)
135 : {
136 0 : struct rb_root *tm_root;
137 0 : struct rb_node **new;
138 0 : struct rb_node *parent = NULL;
139 0 : struct tree_mod_elem *cur;
140 :
141 0 : lockdep_assert_held_write(&fs_info->tree_mod_log_lock);
142 :
143 0 : tm->seq = btrfs_inc_tree_mod_seq(fs_info);
144 :
145 0 : tm_root = &fs_info->tree_mod_log;
146 0 : new = &tm_root->rb_node;
147 0 : while (*new) {
148 0 : cur = rb_entry(*new, struct tree_mod_elem, node);
149 0 : parent = *new;
150 0 : if (cur->logical < tm->logical)
151 0 : new = &((*new)->rb_left);
152 0 : else if (cur->logical > tm->logical)
153 0 : new = &((*new)->rb_right);
154 0 : else if (cur->seq < tm->seq)
155 0 : new = &((*new)->rb_left);
156 0 : else if (cur->seq > tm->seq)
157 0 : new = &((*new)->rb_right);
158 : else
159 : return -EEXIST;
160 : }
161 :
162 0 : rb_link_node(&tm->node, parent, new);
163 0 : rb_insert_color(&tm->node, tm_root);
164 0 : return 0;
165 : }
166 :
167 : /*
168 : * Determines if logging can be omitted. Returns true if it can. Otherwise, it
169 : * returns false with the tree_mod_log_lock acquired. The caller must hold
170 : * this until all tree mod log insertions are recorded in the rb tree and then
171 : * write unlock fs_info::tree_mod_log_lock.
172 : */
173 0 : static inline bool tree_mod_dont_log(struct btrfs_fs_info *fs_info,
174 : struct extent_buffer *eb)
175 : {
176 0 : if (!test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags))
177 : return true;
178 0 : if (eb && btrfs_header_level(eb) == 0)
179 : return true;
180 :
181 0 : write_lock(&fs_info->tree_mod_log_lock);
182 0 : if (list_empty(&(fs_info)->tree_mod_seq_list)) {
183 0 : write_unlock(&fs_info->tree_mod_log_lock);
184 0 : return true;
185 : }
186 :
187 : return false;
188 : }
189 :
190 : /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
191 0 : static inline bool tree_mod_need_log(const struct btrfs_fs_info *fs_info,
192 : struct extent_buffer *eb)
193 : {
194 0 : if (!test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags))
195 : return false;
196 0 : if (eb && btrfs_header_level(eb) == 0)
197 0 : return false;
198 :
199 : return true;
200 : }
201 :
202 0 : static struct tree_mod_elem *alloc_tree_mod_elem(struct extent_buffer *eb,
203 : int slot,
204 : enum btrfs_mod_log_op op)
205 : {
206 0 : struct tree_mod_elem *tm;
207 :
208 0 : tm = kzalloc(sizeof(*tm), GFP_NOFS);
209 0 : if (!tm)
210 : return NULL;
211 :
212 0 : tm->logical = eb->start;
213 0 : if (op != BTRFS_MOD_LOG_KEY_ADD) {
214 0 : btrfs_node_key(eb, &tm->key, slot);
215 0 : tm->blockptr = btrfs_node_blockptr(eb, slot);
216 : }
217 0 : tm->op = op;
218 0 : tm->slot = slot;
219 0 : tm->generation = btrfs_node_ptr_generation(eb, slot);
220 0 : RB_CLEAR_NODE(&tm->node);
221 :
222 0 : return tm;
223 : }
224 :
225 0 : int btrfs_tree_mod_log_insert_key(struct extent_buffer *eb, int slot,
226 : enum btrfs_mod_log_op op)
227 : {
228 0 : struct tree_mod_elem *tm;
229 0 : int ret = 0;
230 :
231 0 : if (!tree_mod_need_log(eb->fs_info, eb))
232 : return 0;
233 :
234 0 : tm = alloc_tree_mod_elem(eb, slot, op);
235 0 : if (!tm)
236 0 : ret = -ENOMEM;
237 :
238 0 : if (tree_mod_dont_log(eb->fs_info, eb)) {
239 0 : kfree(tm);
240 : /*
241 : * Don't error if we failed to allocate memory because we don't
242 : * need to log.
243 : */
244 0 : return 0;
245 0 : } else if (ret != 0) {
246 : /*
247 : * We previously failed to allocate memory and we need to log,
248 : * so we have to fail.
249 : */
250 0 : goto out_unlock;
251 : }
252 :
253 0 : ret = tree_mod_log_insert(eb->fs_info, tm);
254 0 : out_unlock:
255 0 : write_unlock(&eb->fs_info->tree_mod_log_lock);
256 0 : if (ret)
257 0 : kfree(tm);
258 :
259 : return ret;
260 : }
261 :
262 0 : static struct tree_mod_elem *tree_mod_log_alloc_move(struct extent_buffer *eb,
263 : int dst_slot, int src_slot,
264 : int nr_items)
265 : {
266 0 : struct tree_mod_elem *tm;
267 :
268 0 : tm = kzalloc(sizeof(*tm), GFP_NOFS);
269 0 : if (!tm)
270 : return ERR_PTR(-ENOMEM);
271 :
272 0 : tm->logical = eb->start;
273 0 : tm->slot = src_slot;
274 0 : tm->move.dst_slot = dst_slot;
275 0 : tm->move.nr_items = nr_items;
276 0 : tm->op = BTRFS_MOD_LOG_MOVE_KEYS;
277 0 : RB_CLEAR_NODE(&tm->node);
278 :
279 0 : return tm;
280 : }
281 :
282 0 : int btrfs_tree_mod_log_insert_move(struct extent_buffer *eb,
283 : int dst_slot, int src_slot,
284 : int nr_items)
285 : {
286 0 : struct tree_mod_elem *tm = NULL;
287 0 : struct tree_mod_elem **tm_list = NULL;
288 0 : int ret = 0;
289 0 : int i;
290 0 : bool locked = false;
291 :
292 0 : if (!tree_mod_need_log(eb->fs_info, eb))
293 : return 0;
294 :
295 0 : tm_list = kcalloc(nr_items, sizeof(struct tree_mod_elem *), GFP_NOFS);
296 0 : if (!tm_list) {
297 0 : ret = -ENOMEM;
298 0 : goto lock;
299 : }
300 :
301 0 : tm = tree_mod_log_alloc_move(eb, dst_slot, src_slot, nr_items);
302 0 : if (IS_ERR(tm)) {
303 0 : ret = PTR_ERR(tm);
304 0 : tm = NULL;
305 0 : goto lock;
306 : }
307 :
308 0 : for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
309 0 : tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot,
310 : BTRFS_MOD_LOG_KEY_REMOVE_WHILE_MOVING);
311 0 : if (!tm_list[i]) {
312 0 : ret = -ENOMEM;
313 0 : goto lock;
314 : }
315 : }
316 :
317 0 : lock:
318 0 : if (tree_mod_dont_log(eb->fs_info, eb)) {
319 : /*
320 : * Don't error if we failed to allocate memory because we don't
321 : * need to log.
322 : */
323 0 : ret = 0;
324 0 : goto free_tms;
325 : }
326 0 : locked = true;
327 :
328 : /*
329 : * We previously failed to allocate memory and we need to log, so we
330 : * have to fail.
331 : */
332 0 : if (ret != 0)
333 0 : goto free_tms;
334 :
335 : /*
336 : * When we override something during the move, we log these removals.
337 : * This can only happen when we move towards the beginning of the
338 : * buffer, i.e. dst_slot < src_slot.
339 : */
340 0 : for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
341 0 : ret = tree_mod_log_insert(eb->fs_info, tm_list[i]);
342 0 : if (ret)
343 0 : goto free_tms;
344 : }
345 :
346 0 : ret = tree_mod_log_insert(eb->fs_info, tm);
347 0 : if (ret)
348 0 : goto free_tms;
349 0 : write_unlock(&eb->fs_info->tree_mod_log_lock);
350 0 : kfree(tm_list);
351 :
352 0 : return 0;
353 :
354 0 : free_tms:
355 0 : if (tm_list) {
356 0 : for (i = 0; i < nr_items; i++) {
357 0 : if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
358 0 : rb_erase(&tm_list[i]->node, &eb->fs_info->tree_mod_log);
359 0 : kfree(tm_list[i]);
360 : }
361 : }
362 0 : if (locked)
363 0 : write_unlock(&eb->fs_info->tree_mod_log_lock);
364 0 : kfree(tm_list);
365 0 : kfree(tm);
366 :
367 0 : return ret;
368 : }
369 :
370 0 : static inline int tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
371 : struct tree_mod_elem **tm_list,
372 : int nritems)
373 : {
374 0 : int i, j;
375 0 : int ret;
376 :
377 0 : for (i = nritems - 1; i >= 0; i--) {
378 0 : ret = tree_mod_log_insert(fs_info, tm_list[i]);
379 0 : if (ret) {
380 0 : for (j = nritems - 1; j > i; j--)
381 0 : rb_erase(&tm_list[j]->node,
382 : &fs_info->tree_mod_log);
383 : return ret;
384 : }
385 : }
386 :
387 : return 0;
388 : }
389 :
390 0 : int btrfs_tree_mod_log_insert_root(struct extent_buffer *old_root,
391 : struct extent_buffer *new_root,
392 : bool log_removal)
393 : {
394 0 : struct btrfs_fs_info *fs_info = old_root->fs_info;
395 0 : struct tree_mod_elem *tm = NULL;
396 0 : struct tree_mod_elem **tm_list = NULL;
397 0 : int nritems = 0;
398 0 : int ret = 0;
399 0 : int i;
400 :
401 0 : if (!tree_mod_need_log(fs_info, NULL))
402 : return 0;
403 :
404 0 : if (log_removal && btrfs_header_level(old_root) > 0) {
405 0 : nritems = btrfs_header_nritems(old_root);
406 0 : tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *),
407 : GFP_NOFS);
408 0 : if (!tm_list) {
409 0 : ret = -ENOMEM;
410 0 : goto lock;
411 : }
412 0 : for (i = 0; i < nritems; i++) {
413 0 : tm_list[i] = alloc_tree_mod_elem(old_root, i,
414 : BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING);
415 0 : if (!tm_list[i]) {
416 0 : ret = -ENOMEM;
417 0 : goto lock;
418 : }
419 : }
420 : }
421 :
422 0 : tm = kzalloc(sizeof(*tm), GFP_NOFS);
423 0 : if (!tm) {
424 0 : ret = -ENOMEM;
425 0 : goto lock;
426 : }
427 :
428 0 : tm->logical = new_root->start;
429 0 : tm->old_root.logical = old_root->start;
430 0 : tm->old_root.level = btrfs_header_level(old_root);
431 0 : tm->generation = btrfs_header_generation(old_root);
432 0 : tm->op = BTRFS_MOD_LOG_ROOT_REPLACE;
433 :
434 0 : lock:
435 0 : if (tree_mod_dont_log(fs_info, NULL)) {
436 : /*
437 : * Don't error if we failed to allocate memory because we don't
438 : * need to log.
439 : */
440 0 : ret = 0;
441 0 : goto free_tms;
442 0 : } else if (ret != 0) {
443 : /*
444 : * We previously failed to allocate memory and we need to log,
445 : * so we have to fail.
446 : */
447 0 : goto out_unlock;
448 : }
449 :
450 0 : if (tm_list)
451 0 : ret = tree_mod_log_free_eb(fs_info, tm_list, nritems);
452 0 : if (!ret)
453 0 : ret = tree_mod_log_insert(fs_info, tm);
454 :
455 0 : out_unlock:
456 0 : write_unlock(&fs_info->tree_mod_log_lock);
457 0 : if (ret)
458 0 : goto free_tms;
459 0 : kfree(tm_list);
460 :
461 0 : return ret;
462 :
463 0 : free_tms:
464 0 : if (tm_list) {
465 0 : for (i = 0; i < nritems; i++)
466 0 : kfree(tm_list[i]);
467 0 : kfree(tm_list);
468 : }
469 0 : kfree(tm);
470 :
471 0 : return ret;
472 : }
473 :
474 0 : static struct tree_mod_elem *__tree_mod_log_search(struct btrfs_fs_info *fs_info,
475 : u64 start, u64 min_seq,
476 : bool smallest)
477 : {
478 0 : struct rb_root *tm_root;
479 0 : struct rb_node *node;
480 0 : struct tree_mod_elem *cur = NULL;
481 0 : struct tree_mod_elem *found = NULL;
482 :
483 0 : read_lock(&fs_info->tree_mod_log_lock);
484 0 : tm_root = &fs_info->tree_mod_log;
485 0 : node = tm_root->rb_node;
486 0 : while (node) {
487 0 : cur = rb_entry(node, struct tree_mod_elem, node);
488 0 : if (cur->logical < start) {
489 0 : node = node->rb_left;
490 0 : } else if (cur->logical > start) {
491 0 : node = node->rb_right;
492 0 : } else if (cur->seq < min_seq) {
493 0 : node = node->rb_left;
494 0 : } else if (!smallest) {
495 : /* We want the node with the highest seq */
496 0 : if (found)
497 0 : BUG_ON(found->seq > cur->seq);
498 0 : found = cur;
499 0 : node = node->rb_left;
500 0 : } else if (cur->seq > min_seq) {
501 : /* We want the node with the smallest seq */
502 0 : if (found)
503 0 : BUG_ON(found->seq < cur->seq);
504 0 : found = cur;
505 0 : node = node->rb_right;
506 : } else {
507 : found = cur;
508 : break;
509 : }
510 : }
511 0 : read_unlock(&fs_info->tree_mod_log_lock);
512 :
513 0 : return found;
514 : }
515 :
516 : /*
517 : * This returns the element from the log with the smallest time sequence
518 : * value that's in the log (the oldest log item). Any element with a time
519 : * sequence lower than min_seq will be ignored.
520 : */
521 : static struct tree_mod_elem *tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info,
522 : u64 start, u64 min_seq)
523 : {
524 0 : return __tree_mod_log_search(fs_info, start, min_seq, true);
525 : }
526 :
527 : /*
528 : * This returns the element from the log with the largest time sequence
529 : * value that's in the log (the most recent log item). Any element with
530 : * a time sequence lower than min_seq will be ignored.
531 : */
532 : static struct tree_mod_elem *tree_mod_log_search(struct btrfs_fs_info *fs_info,
533 : u64 start, u64 min_seq)
534 : {
535 0 : return __tree_mod_log_search(fs_info, start, min_seq, false);
536 : }
537 :
538 0 : int btrfs_tree_mod_log_eb_copy(struct extent_buffer *dst,
539 : struct extent_buffer *src,
540 : unsigned long dst_offset,
541 : unsigned long src_offset,
542 : int nr_items)
543 : {
544 0 : struct btrfs_fs_info *fs_info = dst->fs_info;
545 0 : int ret = 0;
546 0 : struct tree_mod_elem **tm_list = NULL;
547 0 : struct tree_mod_elem **tm_list_add = NULL;
548 0 : struct tree_mod_elem **tm_list_rem = NULL;
549 0 : int i;
550 0 : bool locked = false;
551 0 : struct tree_mod_elem *dst_move_tm = NULL;
552 0 : struct tree_mod_elem *src_move_tm = NULL;
553 0 : u32 dst_move_nr_items = btrfs_header_nritems(dst) - dst_offset;
554 0 : u32 src_move_nr_items = btrfs_header_nritems(src) - (src_offset + nr_items);
555 :
556 0 : if (!tree_mod_need_log(fs_info, NULL))
557 : return 0;
558 :
559 0 : if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0)
560 : return 0;
561 :
562 0 : tm_list = kcalloc(nr_items * 2, sizeof(struct tree_mod_elem *),
563 : GFP_NOFS);
564 0 : if (!tm_list) {
565 0 : ret = -ENOMEM;
566 0 : goto lock;
567 : }
568 :
569 0 : if (dst_move_nr_items) {
570 0 : dst_move_tm = tree_mod_log_alloc_move(dst, dst_offset + nr_items,
571 : dst_offset, dst_move_nr_items);
572 0 : if (IS_ERR(dst_move_tm)) {
573 0 : ret = PTR_ERR(dst_move_tm);
574 0 : dst_move_tm = NULL;
575 0 : goto lock;
576 : }
577 : }
578 0 : if (src_move_nr_items) {
579 0 : src_move_tm = tree_mod_log_alloc_move(src, src_offset,
580 : src_offset + nr_items,
581 : src_move_nr_items);
582 0 : if (IS_ERR(src_move_tm)) {
583 0 : ret = PTR_ERR(src_move_tm);
584 0 : src_move_tm = NULL;
585 0 : goto lock;
586 : }
587 : }
588 :
589 0 : tm_list_add = tm_list;
590 0 : tm_list_rem = tm_list + nr_items;
591 0 : for (i = 0; i < nr_items; i++) {
592 0 : tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset,
593 : BTRFS_MOD_LOG_KEY_REMOVE);
594 0 : if (!tm_list_rem[i]) {
595 0 : ret = -ENOMEM;
596 0 : goto lock;
597 : }
598 :
599 0 : tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset,
600 : BTRFS_MOD_LOG_KEY_ADD);
601 0 : if (!tm_list_add[i]) {
602 0 : ret = -ENOMEM;
603 0 : goto lock;
604 : }
605 : }
606 :
607 0 : lock:
608 0 : if (tree_mod_dont_log(fs_info, NULL)) {
609 : /*
610 : * Don't error if we failed to allocate memory because we don't
611 : * need to log.
612 : */
613 0 : ret = 0;
614 0 : goto free_tms;
615 : }
616 0 : locked = true;
617 :
618 : /*
619 : * We previously failed to allocate memory and we need to log, so we
620 : * have to fail.
621 : */
622 0 : if (ret != 0)
623 0 : goto free_tms;
624 :
625 0 : if (dst_move_tm) {
626 0 : ret = tree_mod_log_insert(fs_info, dst_move_tm);
627 0 : if (ret)
628 0 : goto free_tms;
629 : }
630 0 : for (i = 0; i < nr_items; i++) {
631 0 : ret = tree_mod_log_insert(fs_info, tm_list_rem[i]);
632 0 : if (ret)
633 0 : goto free_tms;
634 0 : ret = tree_mod_log_insert(fs_info, tm_list_add[i]);
635 0 : if (ret)
636 0 : goto free_tms;
637 : }
638 0 : if (src_move_tm) {
639 0 : ret = tree_mod_log_insert(fs_info, src_move_tm);
640 0 : if (ret)
641 0 : goto free_tms;
642 : }
643 :
644 0 : write_unlock(&fs_info->tree_mod_log_lock);
645 0 : kfree(tm_list);
646 :
647 0 : return 0;
648 :
649 0 : free_tms:
650 0 : if (dst_move_tm && !RB_EMPTY_NODE(&dst_move_tm->node))
651 0 : rb_erase(&dst_move_tm->node, &fs_info->tree_mod_log);
652 0 : kfree(dst_move_tm);
653 0 : if (src_move_tm && !RB_EMPTY_NODE(&src_move_tm->node))
654 0 : rb_erase(&src_move_tm->node, &fs_info->tree_mod_log);
655 0 : kfree(src_move_tm);
656 0 : if (tm_list) {
657 0 : for (i = 0; i < nr_items * 2; i++) {
658 0 : if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
659 0 : rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
660 0 : kfree(tm_list[i]);
661 : }
662 : }
663 0 : if (locked)
664 0 : write_unlock(&fs_info->tree_mod_log_lock);
665 0 : kfree(tm_list);
666 :
667 0 : return ret;
668 : }
669 :
670 0 : int btrfs_tree_mod_log_free_eb(struct extent_buffer *eb)
671 : {
672 0 : struct tree_mod_elem **tm_list = NULL;
673 0 : int nritems = 0;
674 0 : int i;
675 0 : int ret = 0;
676 :
677 0 : if (!tree_mod_need_log(eb->fs_info, eb))
678 : return 0;
679 :
680 0 : nritems = btrfs_header_nritems(eb);
681 0 : tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), GFP_NOFS);
682 0 : if (!tm_list) {
683 0 : ret = -ENOMEM;
684 0 : goto lock;
685 : }
686 :
687 0 : for (i = 0; i < nritems; i++) {
688 0 : tm_list[i] = alloc_tree_mod_elem(eb, i,
689 : BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING);
690 0 : if (!tm_list[i]) {
691 0 : ret = -ENOMEM;
692 0 : goto lock;
693 : }
694 : }
695 :
696 0 : lock:
697 0 : if (tree_mod_dont_log(eb->fs_info, eb)) {
698 : /*
699 : * Don't error if we failed to allocate memory because we don't
700 : * need to log.
701 : */
702 0 : ret = 0;
703 0 : goto free_tms;
704 0 : } else if (ret != 0) {
705 : /*
706 : * We previously failed to allocate memory and we need to log,
707 : * so we have to fail.
708 : */
709 0 : goto out_unlock;
710 : }
711 :
712 0 : ret = tree_mod_log_free_eb(eb->fs_info, tm_list, nritems);
713 0 : out_unlock:
714 0 : write_unlock(&eb->fs_info->tree_mod_log_lock);
715 0 : if (ret)
716 0 : goto free_tms;
717 0 : kfree(tm_list);
718 :
719 0 : return 0;
720 :
721 0 : free_tms:
722 0 : if (tm_list) {
723 0 : for (i = 0; i < nritems; i++)
724 0 : kfree(tm_list[i]);
725 0 : kfree(tm_list);
726 : }
727 :
728 : return ret;
729 : }
730 :
731 : /*
732 : * Returns the logical address of the oldest predecessor of the given root.
733 : * Entries older than time_seq are ignored.
734 : */
735 0 : static struct tree_mod_elem *tree_mod_log_oldest_root(struct extent_buffer *eb_root,
736 : u64 time_seq)
737 : {
738 0 : struct tree_mod_elem *tm;
739 0 : struct tree_mod_elem *found = NULL;
740 0 : u64 root_logical = eb_root->start;
741 0 : bool looped = false;
742 :
743 0 : if (!time_seq)
744 : return NULL;
745 :
746 : /*
747 : * The very last operation that's logged for a root is the replacement
748 : * operation (if it is replaced at all). This has the logical address
749 : * of the *new* root, making it the very first operation that's logged
750 : * for this root.
751 : */
752 0 : while (1) {
753 0 : tm = tree_mod_log_search_oldest(eb_root->fs_info, root_logical,
754 : time_seq);
755 0 : if (!looped && !tm)
756 : return NULL;
757 : /*
758 : * If there are no tree operation for the oldest root, we simply
759 : * return it. This should only happen if that (old) root is at
760 : * level 0.
761 : */
762 0 : if (!tm)
763 : break;
764 :
765 : /*
766 : * If there's an operation that's not a root replacement, we
767 : * found the oldest version of our root. Normally, we'll find a
768 : * BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
769 : */
770 0 : if (tm->op != BTRFS_MOD_LOG_ROOT_REPLACE)
771 : break;
772 :
773 0 : found = tm;
774 0 : root_logical = tm->old_root.logical;
775 0 : looped = true;
776 : }
777 :
778 : /* If there's no old root to return, return what we found instead */
779 0 : if (!found)
780 0 : found = tm;
781 :
782 : return found;
783 : }
784 :
785 :
786 : /*
787 : * tm is a pointer to the first operation to rewind within eb. Then, all
788 : * previous operations will be rewound (until we reach something older than
789 : * time_seq).
790 : */
791 0 : static void tree_mod_log_rewind(struct btrfs_fs_info *fs_info,
792 : struct extent_buffer *eb,
793 : u64 time_seq,
794 : struct tree_mod_elem *first_tm)
795 : {
796 0 : u32 n;
797 0 : struct rb_node *next;
798 0 : struct tree_mod_elem *tm = first_tm;
799 0 : unsigned long o_dst;
800 0 : unsigned long o_src;
801 0 : unsigned long p_size = sizeof(struct btrfs_key_ptr);
802 : /*
803 : * max_slot tracks the maximum valid slot of the rewind eb at every
804 : * step of the rewind. This is in contrast with 'n' which eventually
805 : * matches the number of items, but can be wrong during moves or if
806 : * removes overlap on already valid slots (which is probably separately
807 : * a bug). We do this to validate the offsets of memmoves for rewinding
808 : * moves and detect invalid memmoves.
809 : *
810 : * Since a rewind eb can start empty, max_slot is a signed integer with
811 : * a special meaning for -1, which is that no slot is valid to move out
812 : * of. Any other negative value is invalid.
813 : */
814 0 : int max_slot;
815 0 : int move_src_end_slot;
816 0 : int move_dst_end_slot;
817 :
818 0 : n = btrfs_header_nritems(eb);
819 0 : max_slot = n - 1;
820 0 : read_lock(&fs_info->tree_mod_log_lock);
821 0 : while (tm && tm->seq >= time_seq) {
822 0 : ASSERT(max_slot >= -1);
823 : /*
824 : * All the operations are recorded with the operator used for
825 : * the modification. As we're going backwards, we do the
826 : * opposite of each operation here.
827 : */
828 0 : switch (tm->op) {
829 0 : case BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING:
830 0 : BUG_ON(tm->slot < n);
831 0 : fallthrough;
832 : case BTRFS_MOD_LOG_KEY_REMOVE_WHILE_MOVING:
833 : case BTRFS_MOD_LOG_KEY_REMOVE:
834 0 : btrfs_set_node_key(eb, &tm->key, tm->slot);
835 0 : btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
836 0 : btrfs_set_node_ptr_generation(eb, tm->slot,
837 : tm->generation);
838 0 : n++;
839 0 : if (tm->slot > max_slot)
840 : max_slot = tm->slot;
841 : break;
842 0 : case BTRFS_MOD_LOG_KEY_REPLACE:
843 0 : BUG_ON(tm->slot >= n);
844 0 : btrfs_set_node_key(eb, &tm->key, tm->slot);
845 0 : btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
846 0 : btrfs_set_node_ptr_generation(eb, tm->slot,
847 : tm->generation);
848 : break;
849 0 : case BTRFS_MOD_LOG_KEY_ADD:
850 : /*
851 : * It is possible we could have already removed keys
852 : * behind the known max slot, so this will be an
853 : * overestimate. In practice, the copy operation
854 : * inserts them in increasing order, and overestimating
855 : * just means we miss some warnings, so it's OK. It
856 : * isn't worth carefully tracking the full array of
857 : * valid slots to check against when moving.
858 : */
859 0 : if (tm->slot == max_slot)
860 0 : max_slot--;
861 : /* if a move operation is needed it's in the log */
862 0 : n--;
863 0 : break;
864 0 : case BTRFS_MOD_LOG_MOVE_KEYS:
865 0 : ASSERT(tm->move.nr_items > 0);
866 0 : move_src_end_slot = tm->move.dst_slot + tm->move.nr_items - 1;
867 0 : move_dst_end_slot = tm->slot + tm->move.nr_items - 1;
868 0 : o_dst = btrfs_node_key_ptr_offset(eb, tm->slot);
869 0 : o_src = btrfs_node_key_ptr_offset(eb, tm->move.dst_slot);
870 0 : if (WARN_ON(move_src_end_slot > max_slot ||
871 : tm->move.nr_items <= 0)) {
872 0 : btrfs_warn(fs_info,
873 : "move from invalid tree mod log slot eb %llu slot %d dst_slot %d nr_items %d seq %llu n %u max_slot %d",
874 : eb->start, tm->slot,
875 : tm->move.dst_slot, tm->move.nr_items,
876 : tm->seq, n, max_slot);
877 : }
878 0 : memmove_extent_buffer(eb, o_dst, o_src,
879 0 : tm->move.nr_items * p_size);
880 0 : max_slot = move_dst_end_slot;
881 0 : break;
882 : case BTRFS_MOD_LOG_ROOT_REPLACE:
883 : /*
884 : * This operation is special. For roots, this must be
885 : * handled explicitly before rewinding.
886 : * For non-roots, this operation may exist if the node
887 : * was a root: root A -> child B; then A gets empty and
888 : * B is promoted to the new root. In the mod log, we'll
889 : * have a root-replace operation for B, a tree block
890 : * that is no root. We simply ignore that operation.
891 : */
892 : break;
893 : }
894 0 : next = rb_next(&tm->node);
895 0 : if (!next)
896 : break;
897 0 : tm = rb_entry(next, struct tree_mod_elem, node);
898 0 : if (tm->logical != first_tm->logical)
899 : break;
900 : }
901 0 : read_unlock(&fs_info->tree_mod_log_lock);
902 0 : btrfs_set_header_nritems(eb, n);
903 0 : }
904 :
905 : /*
906 : * Called with eb read locked. If the buffer cannot be rewound, the same buffer
907 : * is returned. If rewind operations happen, a fresh buffer is returned. The
908 : * returned buffer is always read-locked. If the returned buffer is not the
909 : * input buffer, the lock on the input buffer is released and the input buffer
910 : * is freed (its refcount is decremented).
911 : */
912 0 : struct extent_buffer *btrfs_tree_mod_log_rewind(struct btrfs_fs_info *fs_info,
913 : struct btrfs_path *path,
914 : struct extent_buffer *eb,
915 : u64 time_seq)
916 : {
917 0 : struct extent_buffer *eb_rewin;
918 0 : struct tree_mod_elem *tm;
919 :
920 0 : if (!time_seq)
921 : return eb;
922 :
923 0 : if (btrfs_header_level(eb) == 0)
924 : return eb;
925 :
926 0 : tm = tree_mod_log_search(fs_info, eb->start, time_seq);
927 0 : if (!tm)
928 : return eb;
929 :
930 0 : if (tm->op == BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
931 0 : BUG_ON(tm->slot != 0);
932 0 : eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start);
933 0 : if (!eb_rewin) {
934 0 : btrfs_tree_read_unlock(eb);
935 0 : free_extent_buffer(eb);
936 0 : return NULL;
937 : }
938 0 : btrfs_set_header_bytenr(eb_rewin, eb->start);
939 0 : btrfs_set_header_backref_rev(eb_rewin,
940 : btrfs_header_backref_rev(eb));
941 0 : btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb));
942 0 : btrfs_set_header_level(eb_rewin, btrfs_header_level(eb));
943 : } else {
944 0 : eb_rewin = btrfs_clone_extent_buffer(eb);
945 0 : if (!eb_rewin) {
946 0 : btrfs_tree_read_unlock(eb);
947 0 : free_extent_buffer(eb);
948 0 : return NULL;
949 : }
950 : }
951 :
952 0 : btrfs_tree_read_unlock(eb);
953 0 : free_extent_buffer(eb);
954 :
955 0 : btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb_rewin),
956 : eb_rewin, btrfs_header_level(eb_rewin));
957 0 : btrfs_tree_read_lock(eb_rewin);
958 0 : tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm);
959 0 : WARN_ON(btrfs_header_nritems(eb_rewin) >
960 : BTRFS_NODEPTRS_PER_BLOCK(fs_info));
961 :
962 : return eb_rewin;
963 : }
964 :
965 : /*
966 : * Rewind the state of @root's root node to the given @time_seq value.
967 : * If there are no changes, the current root->root_node is returned. If anything
968 : * changed in between, there's a fresh buffer allocated on which the rewind
969 : * operations are done. In any case, the returned buffer is read locked.
970 : * Returns NULL on error (with no locks held).
971 : */
972 0 : struct extent_buffer *btrfs_get_old_root(struct btrfs_root *root, u64 time_seq)
973 : {
974 0 : struct btrfs_fs_info *fs_info = root->fs_info;
975 0 : struct tree_mod_elem *tm;
976 0 : struct extent_buffer *eb = NULL;
977 0 : struct extent_buffer *eb_root;
978 0 : u64 eb_root_owner = 0;
979 0 : struct extent_buffer *old;
980 0 : struct tree_mod_root *old_root = NULL;
981 0 : u64 old_generation = 0;
982 0 : u64 logical;
983 0 : int level;
984 :
985 0 : eb_root = btrfs_read_lock_root_node(root);
986 0 : tm = tree_mod_log_oldest_root(eb_root, time_seq);
987 0 : if (!tm)
988 : return eb_root;
989 :
990 0 : if (tm->op == BTRFS_MOD_LOG_ROOT_REPLACE) {
991 0 : old_root = &tm->old_root;
992 0 : old_generation = tm->generation;
993 0 : logical = old_root->logical;
994 0 : level = old_root->level;
995 : } else {
996 0 : logical = eb_root->start;
997 0 : level = btrfs_header_level(eb_root);
998 : }
999 :
1000 0 : tm = tree_mod_log_search(fs_info, logical, time_seq);
1001 0 : if (old_root && tm && tm->op != BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1002 0 : struct btrfs_tree_parent_check check = { 0 };
1003 :
1004 0 : btrfs_tree_read_unlock(eb_root);
1005 0 : free_extent_buffer(eb_root);
1006 :
1007 0 : check.level = level;
1008 0 : check.owner_root = root->root_key.objectid;
1009 :
1010 0 : old = read_tree_block(fs_info, logical, &check);
1011 0 : if (WARN_ON(IS_ERR(old) || !extent_buffer_uptodate(old))) {
1012 0 : if (!IS_ERR(old))
1013 0 : free_extent_buffer(old);
1014 0 : btrfs_warn(fs_info,
1015 : "failed to read tree block %llu from get_old_root",
1016 : logical);
1017 : } else {
1018 0 : struct tree_mod_elem *tm2;
1019 :
1020 0 : btrfs_tree_read_lock(old);
1021 0 : eb = btrfs_clone_extent_buffer(old);
1022 : /*
1023 : * After the lookup for the most recent tree mod operation
1024 : * above and before we locked and cloned the extent buffer
1025 : * 'old', a new tree mod log operation may have been added.
1026 : * So lookup for a more recent one to make sure the number
1027 : * of mod log operations we replay is consistent with the
1028 : * number of items we have in the cloned extent buffer,
1029 : * otherwise we can hit a BUG_ON when rewinding the extent
1030 : * buffer.
1031 : */
1032 0 : tm2 = tree_mod_log_search(fs_info, logical, time_seq);
1033 0 : btrfs_tree_read_unlock(old);
1034 0 : free_extent_buffer(old);
1035 0 : ASSERT(tm2);
1036 0 : ASSERT(tm2 == tm || tm2->seq > tm->seq);
1037 0 : if (!tm2 || tm2->seq < tm->seq) {
1038 0 : free_extent_buffer(eb);
1039 0 : return NULL;
1040 : }
1041 : tm = tm2;
1042 : }
1043 0 : } else if (old_root) {
1044 0 : eb_root_owner = btrfs_header_owner(eb_root);
1045 0 : btrfs_tree_read_unlock(eb_root);
1046 0 : free_extent_buffer(eb_root);
1047 0 : eb = alloc_dummy_extent_buffer(fs_info, logical);
1048 : } else {
1049 0 : eb = btrfs_clone_extent_buffer(eb_root);
1050 0 : btrfs_tree_read_unlock(eb_root);
1051 0 : free_extent_buffer(eb_root);
1052 : }
1053 :
1054 0 : if (!eb)
1055 : return NULL;
1056 0 : if (old_root) {
1057 0 : btrfs_set_header_bytenr(eb, eb->start);
1058 0 : btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
1059 0 : btrfs_set_header_owner(eb, eb_root_owner);
1060 0 : btrfs_set_header_level(eb, old_root->level);
1061 0 : btrfs_set_header_generation(eb, old_generation);
1062 : }
1063 0 : btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb), eb,
1064 : btrfs_header_level(eb));
1065 0 : btrfs_tree_read_lock(eb);
1066 0 : if (tm)
1067 0 : tree_mod_log_rewind(fs_info, eb, time_seq, tm);
1068 : else
1069 0 : WARN_ON(btrfs_header_level(eb) != 0);
1070 0 : WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(fs_info));
1071 :
1072 : return eb;
1073 : }
1074 :
1075 0 : int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq)
1076 : {
1077 0 : struct tree_mod_elem *tm;
1078 0 : int level;
1079 0 : struct extent_buffer *eb_root = btrfs_root_node(root);
1080 :
1081 0 : tm = tree_mod_log_oldest_root(eb_root, time_seq);
1082 0 : if (tm && tm->op == BTRFS_MOD_LOG_ROOT_REPLACE)
1083 0 : level = tm->old_root.level;
1084 : else
1085 0 : level = btrfs_header_level(eb_root);
1086 :
1087 0 : free_extent_buffer(eb_root);
1088 :
1089 0 : return level;
1090 : }
1091 :
1092 : /*
1093 : * Return the lowest sequence number in the tree modification log.
1094 : *
1095 : * Return the sequence number of the oldest tree modification log user, which
1096 : * corresponds to the lowest sequence number of all existing users. If there are
1097 : * no users it returns 0.
1098 : */
1099 0 : u64 btrfs_tree_mod_log_lowest_seq(struct btrfs_fs_info *fs_info)
1100 : {
1101 0 : u64 ret = 0;
1102 :
1103 0 : read_lock(&fs_info->tree_mod_log_lock);
1104 0 : if (!list_empty(&fs_info->tree_mod_seq_list)) {
1105 0 : struct btrfs_seq_list *elem;
1106 :
1107 0 : elem = list_first_entry(&fs_info->tree_mod_seq_list,
1108 : struct btrfs_seq_list, list);
1109 0 : ret = elem->seq;
1110 : }
1111 0 : read_unlock(&fs_info->tree_mod_log_lock);
1112 :
1113 0 : return ret;
1114 : }
|
