backref.c (b7f8f259896f669f131713b0c74ba4d008daa71d) backref.c (f3a84ccd28d0b04da0358cf1289706f3469ff9ad)
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2011 STRATO. All rights reserved.
4 */
5
6#include <linux/mm.h>
7#include <linux/rbtree.h>
8#include <trace/events/btrfs.h>
9#include "ctree.h"
10#include "disk-io.h"
11#include "backref.h"
12#include "ulist.h"
13#include "transaction.h"
14#include "delayed-ref.h"
15#include "locking.h"
16#include "misc.h"
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2011 STRATO. All rights reserved.
4 */
5
6#include <linux/mm.h>
7#include <linux/rbtree.h>
8#include <trace/events/btrfs.h>
9#include "ctree.h"
10#include "disk-io.h"
11#include "backref.h"
12#include "ulist.h"
13#include "transaction.h"
14#include "delayed-ref.h"
15#include "locking.h"
16#include "misc.h"
17#include "tree-mod-log.h"
17
18/* Just an arbitrary number so we can be sure this happened */
19#define BACKREF_FOUND_SHARED 6
20
21struct extent_inode_elem {
22 u64 inum;
23 u64 offset;
24 struct extent_inode_elem *next;

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

447 * 3. The leaf owner is not equal to the root we are searching
448 *
449 * For these cases, go to the next leaf before we continue.
450 */
451 eb = path->nodes[0];
452 if (path->slots[0] >= btrfs_header_nritems(eb) ||
453 is_shared_data_backref(preftrees, eb->start) ||
454 ref->root_id != btrfs_header_owner(eb)) {
18
19/* Just an arbitrary number so we can be sure this happened */
20#define BACKREF_FOUND_SHARED 6
21
22struct extent_inode_elem {
23 u64 inum;
24 u64 offset;
25 struct extent_inode_elem *next;

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

448 * 3. The leaf owner is not equal to the root we are searching
449 *
450 * For these cases, go to the next leaf before we continue.
451 */
452 eb = path->nodes[0];
453 if (path->slots[0] >= btrfs_header_nritems(eb) ||
454 is_shared_data_backref(preftrees, eb->start) ||
455 ref->root_id != btrfs_header_owner(eb)) {
455 if (time_seq == SEQ_LAST)
456 if (time_seq == BTRFS_SEQ_LAST)
456 ret = btrfs_next_leaf(root, path);
457 else
458 ret = btrfs_next_old_leaf(root, path, time_seq);
459 }
460
461 while (!ret && count < ref->count) {
462 eb = path->nodes[0];
463 slot = path->slots[0];

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

471 /*
472 * We are searching for normal backref but bytenr of this leaf
473 * matches shared data backref, OR
474 * the leaf owner is not equal to the root we are searching for
475 */
476 if (slot == 0 &&
477 (is_shared_data_backref(preftrees, eb->start) ||
478 ref->root_id != btrfs_header_owner(eb))) {
457 ret = btrfs_next_leaf(root, path);
458 else
459 ret = btrfs_next_old_leaf(root, path, time_seq);
460 }
461
462 while (!ret && count < ref->count) {
463 eb = path->nodes[0];
464 slot = path->slots[0];

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

472 /*
473 * We are searching for normal backref but bytenr of this leaf
474 * matches shared data backref, OR
475 * the leaf owner is not equal to the root we are searching for
476 */
477 if (slot == 0 &&
478 (is_shared_data_backref(preftrees, eb->start) ||
479 ref->root_id != btrfs_header_owner(eb))) {
479 if (time_seq == SEQ_LAST)
480 if (time_seq == BTRFS_SEQ_LAST)
480 ret = btrfs_next_leaf(root, path);
481 else
482 ret = btrfs_next_old_leaf(root, path, time_seq);
483 continue;
484 }
485 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
486 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
487 data_offset = btrfs_file_extent_offset(eb, fi);

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

509 if (!ret && extent_item_pos) {
510 while (old->next)
511 old = old->next;
512 old->next = eie;
513 }
514 eie = NULL;
515 }
516next:
481 ret = btrfs_next_leaf(root, path);
482 else
483 ret = btrfs_next_old_leaf(root, path, time_seq);
484 continue;
485 }
486 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
487 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
488 data_offset = btrfs_file_extent_offset(eb, fi);

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

510 if (!ret && extent_item_pos) {
511 while (old->next)
512 old = old->next;
513 old->next = eie;
514 }
515 eie = NULL;
516 }
517next:
517 if (time_seq == SEQ_LAST)
518 if (time_seq == BTRFS_SEQ_LAST)
518 ret = btrfs_next_item(root, path);
519 else
520 ret = btrfs_next_old_item(root, path, time_seq);
521 }
522
523 if (ret > 0)
524 ret = 0;
525 else if (ret < 0)

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

569
570 if (btrfs_is_testing(fs_info)) {
571 ret = -ENOENT;
572 goto out;
573 }
574
575 if (path->search_commit_root)
576 root_level = btrfs_header_level(root->commit_root);
519 ret = btrfs_next_item(root, path);
520 else
521 ret = btrfs_next_old_item(root, path, time_seq);
522 }
523
524 if (ret > 0)
525 ret = 0;
526 else if (ret < 0)

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

570
571 if (btrfs_is_testing(fs_info)) {
572 ret = -ENOENT;
573 goto out;
574 }
575
576 if (path->search_commit_root)
577 root_level = btrfs_header_level(root->commit_root);
577 else if (time_seq == SEQ_LAST)
578 else if (time_seq == BTRFS_SEQ_LAST)
578 root_level = btrfs_header_level(root->node);
579 else
580 root_level = btrfs_old_root_level(root, time_seq);
581
582 if (root_level + 1 == level)
583 goto out;
584
585 /*

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

600 * existed, but it does and a fix for the clone ioctl would touch a lot
601 * of places, cause backwards incompatibility and would not fix the
602 * problem for extents cloned with older kernels.
603 */
604 if (search_key.type == BTRFS_EXTENT_DATA_KEY &&
605 search_key.offset >= LLONG_MAX)
606 search_key.offset = 0;
607 path->lowest_level = level;
579 root_level = btrfs_header_level(root->node);
580 else
581 root_level = btrfs_old_root_level(root, time_seq);
582
583 if (root_level + 1 == level)
584 goto out;
585
586 /*

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

601 * existed, but it does and a fix for the clone ioctl would touch a lot
602 * of places, cause backwards incompatibility and would not fix the
603 * problem for extents cloned with older kernels.
604 */
605 if (search_key.type == BTRFS_EXTENT_DATA_KEY &&
606 search_key.offset >= LLONG_MAX)
607 search_key.offset = 0;
608 path->lowest_level = level;
608 if (time_seq == SEQ_LAST)
609 if (time_seq == BTRFS_SEQ_LAST)
609 ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
610 else
611 ret = btrfs_search_old_slot(root, &search_key, path, time_seq);
612
613 btrfs_debug(fs_info,
614 "search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
615 ref->root_id, level, ref->count, ret,
616 ref->key_for_search.objectid, ref->key_for_search.type,

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

1142}
1143
1144/*
1145 * this adds all existing backrefs (inline backrefs, backrefs and delayed
1146 * refs) for the given bytenr to the refs list, merges duplicates and resolves
1147 * indirect refs to their parent bytenr.
1148 * When roots are found, they're added to the roots list
1149 *
610 ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
611 else
612 ret = btrfs_search_old_slot(root, &search_key, path, time_seq);
613
614 btrfs_debug(fs_info,
615 "search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
616 ref->root_id, level, ref->count, ret,
617 ref->key_for_search.objectid, ref->key_for_search.type,

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

1143}
1144
1145/*
1146 * this adds all existing backrefs (inline backrefs, backrefs and delayed
1147 * refs) for the given bytenr to the refs list, merges duplicates and resolves
1148 * indirect refs to their parent bytenr.
1149 * When roots are found, they're added to the roots list
1150 *
1150 * If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave
1151 * much like trans == NULL case, the difference only lies in it will not
1151 * If time_seq is set to BTRFS_SEQ_LAST, it will not search delayed_refs, and
1152 * behave much like trans == NULL case, the difference only lies in it will not
1152 * commit root.
1153 * The special case is for qgroup to search roots in commit_transaction().
1154 *
1155 * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a
1156 * shared extent is detected.
1157 *
1158 * Otherwise this returns 0 for success and <0 for an error.
1159 *

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

1194 path = btrfs_alloc_path();
1195 if (!path)
1196 return -ENOMEM;
1197 if (!trans) {
1198 path->search_commit_root = 1;
1199 path->skip_locking = 1;
1200 }
1201
1153 * commit root.
1154 * The special case is for qgroup to search roots in commit_transaction().
1155 *
1156 * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a
1157 * shared extent is detected.
1158 *
1159 * Otherwise this returns 0 for success and <0 for an error.
1160 *

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

1195 path = btrfs_alloc_path();
1196 if (!path)
1197 return -ENOMEM;
1198 if (!trans) {
1199 path->search_commit_root = 1;
1200 path->skip_locking = 1;
1201 }
1202
1202 if (time_seq == SEQ_LAST)
1203 if (time_seq == BTRFS_SEQ_LAST)
1203 path->skip_locking = 1;
1204
1205 /*
1206 * grab both a lock on the path and a lock on the delayed ref head.
1207 * We need both to get a consistent picture of how the refs look
1208 * at a specified point in time
1209 */
1210again:
1211 head = NULL;
1212
1213 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
1214 if (ret < 0)
1215 goto out;
1216 BUG_ON(ret == 0);
1217
1218#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1219 if (trans && likely(trans->type != __TRANS_DUMMY) &&
1204 path->skip_locking = 1;
1205
1206 /*
1207 * grab both a lock on the path and a lock on the delayed ref head.
1208 * We need both to get a consistent picture of how the refs look
1209 * at a specified point in time
1210 */
1211again:
1212 head = NULL;
1213
1214 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
1215 if (ret < 0)
1216 goto out;
1217 BUG_ON(ret == 0);
1218
1219#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1220 if (trans && likely(trans->type != __TRANS_DUMMY) &&
1220 time_seq != SEQ_LAST) {
1221 time_seq != BTRFS_SEQ_LAST) {
1221#else
1222#else
1222 if (trans && time_seq != SEQ_LAST) {
1223 if (trans && time_seq != BTRFS_SEQ_LAST) {
1223#endif
1224 /*
1225 * look if there are updates for this ref queued and lock the
1226 * head
1227 */
1228 delayed_refs = &trans->transaction->delayed_refs;
1229 spin_lock(&delayed_refs->lock);
1230 head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);

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

1522 */
1523int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr,
1524 struct ulist *roots, struct ulist *tmp)
1525{
1526 struct btrfs_fs_info *fs_info = root->fs_info;
1527 struct btrfs_trans_handle *trans;
1528 struct ulist_iterator uiter;
1529 struct ulist_node *node;
1224#endif
1225 /*
1226 * look if there are updates for this ref queued and lock the
1227 * head
1228 */
1229 delayed_refs = &trans->transaction->delayed_refs;
1230 spin_lock(&delayed_refs->lock);
1231 head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);

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

1523 */
1524int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr,
1525 struct ulist *roots, struct ulist *tmp)
1526{
1527 struct btrfs_fs_info *fs_info = root->fs_info;
1528 struct btrfs_trans_handle *trans;
1529 struct ulist_iterator uiter;
1530 struct ulist_node *node;
1530 struct seq_list elem = SEQ_LIST_INIT(elem);
1531 struct btrfs_seq_list elem = BTRFS_SEQ_LIST_INIT(elem);
1531 int ret = 0;
1532 struct share_check shared = {
1533 .root_objectid = root->root_key.objectid,
1534 .inum = inum,
1535 .share_count = 0,
1536 };
1537
1538 ulist_init(roots);

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

1948 bool ignore_offset)
1949{
1950 int ret;
1951 struct btrfs_trans_handle *trans = NULL;
1952 struct ulist *refs = NULL;
1953 struct ulist *roots = NULL;
1954 struct ulist_node *ref_node = NULL;
1955 struct ulist_node *root_node = NULL;
1532 int ret = 0;
1533 struct share_check shared = {
1534 .root_objectid = root->root_key.objectid,
1535 .inum = inum,
1536 .share_count = 0,
1537 };
1538
1539 ulist_init(roots);

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

1949 bool ignore_offset)
1950{
1951 int ret;
1952 struct btrfs_trans_handle *trans = NULL;
1953 struct ulist *refs = NULL;
1954 struct ulist *roots = NULL;
1955 struct ulist_node *ref_node = NULL;
1956 struct ulist_node *root_node = NULL;
1956 struct seq_list tree_mod_seq_elem = SEQ_LIST_INIT(tree_mod_seq_elem);
1957 struct btrfs_seq_list seq_elem = BTRFS_SEQ_LIST_INIT(seq_elem);
1957 struct ulist_iterator ref_uiter;
1958 struct ulist_iterator root_uiter;
1959
1960 btrfs_debug(fs_info, "resolving all inodes for extent %llu",
1961 extent_item_objectid);
1962
1963 if (!search_commit_root) {
1964 trans = btrfs_attach_transaction(fs_info->extent_root);
1965 if (IS_ERR(trans)) {
1966 if (PTR_ERR(trans) != -ENOENT &&
1967 PTR_ERR(trans) != -EROFS)
1968 return PTR_ERR(trans);
1969 trans = NULL;
1970 }
1971 }
1972
1973 if (trans)
1958 struct ulist_iterator ref_uiter;
1959 struct ulist_iterator root_uiter;
1960
1961 btrfs_debug(fs_info, "resolving all inodes for extent %llu",
1962 extent_item_objectid);
1963
1964 if (!search_commit_root) {
1965 trans = btrfs_attach_transaction(fs_info->extent_root);
1966 if (IS_ERR(trans)) {
1967 if (PTR_ERR(trans) != -ENOENT &&
1968 PTR_ERR(trans) != -EROFS)
1969 return PTR_ERR(trans);
1970 trans = NULL;
1971 }
1972 }
1973
1974 if (trans)
1974 btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1975 btrfs_get_tree_mod_seq(fs_info, &seq_elem);
1975 else
1976 down_read(&fs_info->commit_root_sem);
1977
1978 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1976 else
1977 down_read(&fs_info->commit_root_sem);
1978
1979 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1979 tree_mod_seq_elem.seq, &refs,
1980 seq_elem.seq, &refs,
1980 &extent_item_pos, ignore_offset);
1981 if (ret)
1982 goto out;
1983
1984 ULIST_ITER_INIT(&ref_uiter);
1985 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
1986 ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val,
1981 &extent_item_pos, ignore_offset);
1982 if (ret)
1983 goto out;
1984
1985 ULIST_ITER_INIT(&ref_uiter);
1986 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
1987 ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val,
1987 tree_mod_seq_elem.seq, &roots,
1988 seq_elem.seq, &roots,
1988 ignore_offset);
1989 if (ret)
1990 break;
1991 ULIST_ITER_INIT(&root_uiter);
1992 while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
1993 btrfs_debug(fs_info,
1994 "root %llu references leaf %llu, data list %#llx",
1995 root_node->val, ref_node->val,

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

2002 iterate, ctx);
2003 }
2004 ulist_free(roots);
2005 }
2006
2007 free_leaf_list(refs);
2008out:
2009 if (trans) {
1989 ignore_offset);
1990 if (ret)
1991 break;
1992 ULIST_ITER_INIT(&root_uiter);
1993 while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
1994 btrfs_debug(fs_info,
1995 "root %llu references leaf %llu, data list %#llx",
1996 root_node->val, ref_node->val,

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

2003 iterate, ctx);
2004 }
2005 ulist_free(roots);
2006 }
2007
2008 free_leaf_list(refs);
2009out:
2010 if (trans) {
2010 btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2011 btrfs_put_tree_mod_seq(fs_info, &seq_elem);
2011 btrfs_end_transaction(trans);
2012 } else {
2013 up_read(&fs_info->commit_root_sem);
2014 }
2015
2016 return ret;
2017}
2018

--- 1107 unchanged lines hidden --- 		2012 btrfs_end_transaction(trans);
2013 } else {
2014 up_read(&fs_info->commit_root_sem);
2015 }
2016
2017 return ret;
2018}
2019

--- 1107 unchanged lines hidden ---