backref.c (707e8a071528385a87b63a72a37c2322e463c7b8) backref.c (dc046b10c8b7d4f40befe457acb82340bf8b0699)
1/*
2 * Copyright (C) 2011 STRATO. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,

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

20#include "ctree.h"
21#include "disk-io.h"
22#include "backref.h"
23#include "ulist.h"
24#include "transaction.h"
25#include "delayed-ref.h"
26#include "locking.h"
27
1/*
2 * Copyright (C) 2011 STRATO. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,

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

20#include "ctree.h"
21#include "disk-io.h"
22#include "backref.h"
23#include "ulist.h"
24#include "transaction.h"
25#include "delayed-ref.h"
26#include "locking.h"
27
28/* Just an arbitrary number so we can be sure this happened */
29#define BACKREF_FOUND_SHARED 6
30
28struct extent_inode_elem {
29 u64 inum;
30 u64 offset;
31 struct extent_inode_elem *next;
32};
33
34static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
35 struct btrfs_file_extent_item *fi,

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

372}
373
374/*
375 * resolve all indirect backrefs from the list
376 */
377static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
378 struct btrfs_path *path, u64 time_seq,
379 struct list_head *head,
31struct extent_inode_elem {
32 u64 inum;
33 u64 offset;
34 struct extent_inode_elem *next;
35};
36
37static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
38 struct btrfs_file_extent_item *fi,

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

375}
376
377/*
378 * resolve all indirect backrefs from the list
379 */
380static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
381 struct btrfs_path *path, u64 time_seq,
382 struct list_head *head,
380 const u64 *extent_item_pos, u64 total_refs)
383 const u64 *extent_item_pos, u64 total_refs,
384 u64 root_objectid)
381{
382 int err;
383 int ret = 0;
384 struct __prelim_ref *ref;
385 struct __prelim_ref *ref_safe;
386 struct __prelim_ref *new_ref;
387 struct ulist *parents;
388 struct ulist_node *node;

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

397 * iterating over the newly inserted items.
398 * we're also allowed to re-assign ref during iteration.
399 */
400 list_for_each_entry_safe(ref, ref_safe, head, list) {
401 if (ref->parent) /* already direct */
402 continue;
403 if (ref->count == 0)
404 continue;
385{
386 int err;
387 int ret = 0;
388 struct __prelim_ref *ref;
389 struct __prelim_ref *ref_safe;
390 struct __prelim_ref *new_ref;
391 struct ulist *parents;
392 struct ulist_node *node;

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

401 * iterating over the newly inserted items.
402 * we're also allowed to re-assign ref during iteration.
403 */
404 list_for_each_entry_safe(ref, ref_safe, head, list) {
405 if (ref->parent) /* already direct */
406 continue;
407 if (ref->count == 0)
408 continue;
409 if (root_objectid && ref->root_id != root_objectid) {
410 ret = BACKREF_FOUND_SHARED;
411 goto out;
412 }
405 err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
406 parents, extent_item_pos,
407 total_refs);
408 /*
409 * we can only tolerate ENOENT,otherwise,we should catch error
410 * and return directly.
411 */
412 if (err == -ENOENT) {

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

556 }
557}
558
559/*
560 * add all currently queued delayed refs from this head whose seq nr is
561 * smaller or equal that seq to the list
562 */
563static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
413 err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
414 parents, extent_item_pos,
415 total_refs);
416 /*
417 * we can only tolerate ENOENT,otherwise,we should catch error
418 * and return directly.
419 */
420 if (err == -ENOENT) {

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

564 }
565}
566
567/*
568 * add all currently queued delayed refs from this head whose seq nr is
569 * smaller or equal that seq to the list
570 */
571static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
564 struct list_head *prefs, u64 *total_refs)
572 struct list_head *prefs, u64 *total_refs,
573 u64 inum)
565{
566 struct btrfs_delayed_extent_op *extent_op = head->extent_op;
567 struct rb_node *n = &head->node.rb_node;
568 struct btrfs_key key;
569 struct btrfs_key op_key = {0};
570 int sgn;
571 int ret = 0;
572

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

620 }
621 case BTRFS_EXTENT_DATA_REF_KEY: {
622 struct btrfs_delayed_data_ref *ref;
623 ref = btrfs_delayed_node_to_data_ref(node);
624
625 key.objectid = ref->objectid;
626 key.type = BTRFS_EXTENT_DATA_KEY;
627 key.offset = ref->offset;
574{
575 struct btrfs_delayed_extent_op *extent_op = head->extent_op;
576 struct rb_node *n = &head->node.rb_node;
577 struct btrfs_key key;
578 struct btrfs_key op_key = {0};
579 int sgn;
580 int ret = 0;
581

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

629 }
630 case BTRFS_EXTENT_DATA_REF_KEY: {
631 struct btrfs_delayed_data_ref *ref;
632 ref = btrfs_delayed_node_to_data_ref(node);
633
634 key.objectid = ref->objectid;
635 key.type = BTRFS_EXTENT_DATA_KEY;
636 key.offset = ref->offset;
637
638 /*
639 * Found a inum that doesn't match our known inum, we
640 * know it's shared.
641 */
642 if (inum && ref->objectid != inum) {
643 ret = BACKREF_FOUND_SHARED;
644 break;
645 }
646
628 ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0,
629 node->bytenr,
630 node->ref_mod * sgn, GFP_ATOMIC);
631 break;
632 }
633 case BTRFS_SHARED_DATA_REF_KEY: {
634 struct btrfs_delayed_data_ref *ref;
635

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

654}
655
656/*
657 * add all inline backrefs for bytenr to the list
658 */
659static int __add_inline_refs(struct btrfs_fs_info *fs_info,
660 struct btrfs_path *path, u64 bytenr,
661 int *info_level, struct list_head *prefs,
647 ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0,
648 node->bytenr,
649 node->ref_mod * sgn, GFP_ATOMIC);
650 break;
651 }
652 case BTRFS_SHARED_DATA_REF_KEY: {
653 struct btrfs_delayed_data_ref *ref;
654

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

673}
674
675/*
676 * add all inline backrefs for bytenr to the list
677 */
678static int __add_inline_refs(struct btrfs_fs_info *fs_info,
679 struct btrfs_path *path, u64 bytenr,
680 int *info_level, struct list_head *prefs,
662 u64 *total_refs)
681 u64 *total_refs, u64 inum)
663{
664 int ret = 0;
665 int slot;
666 struct extent_buffer *leaf;
667 struct btrfs_key key;
668 struct btrfs_key found_key;
669 unsigned long ptr;
670 unsigned long end;

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

739 u64 root;
740
741 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
742 count = btrfs_extent_data_ref_count(leaf, dref);
743 key.objectid = btrfs_extent_data_ref_objectid(leaf,
744 dref);
745 key.type = BTRFS_EXTENT_DATA_KEY;
746 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
682{
683 int ret = 0;
684 int slot;
685 struct extent_buffer *leaf;
686 struct btrfs_key key;
687 struct btrfs_key found_key;
688 unsigned long ptr;
689 unsigned long end;

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

758 u64 root;
759
760 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
761 count = btrfs_extent_data_ref_count(leaf, dref);
762 key.objectid = btrfs_extent_data_ref_objectid(leaf,
763 dref);
764 key.type = BTRFS_EXTENT_DATA_KEY;
765 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
766
767 if (inum && key.objectid != inum) {
768 ret = BACKREF_FOUND_SHARED;
769 break;
770 }
771
747 root = btrfs_extent_data_ref_root(leaf, dref);
748 ret = __add_prelim_ref(prefs, root, &key, 0, 0,
749 bytenr, count, GFP_NOFS);
750 break;
751 }
752 default:
753 WARN_ON(1);
754 }

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

760 return 0;
761}
762
763/*
764 * add all non-inline backrefs for bytenr to the list
765 */
766static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
767 struct btrfs_path *path, u64 bytenr,
772 root = btrfs_extent_data_ref_root(leaf, dref);
773 ret = __add_prelim_ref(prefs, root, &key, 0, 0,
774 bytenr, count, GFP_NOFS);
775 break;
776 }
777 default:
778 WARN_ON(1);
779 }

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

785 return 0;
786}
787
788/*
789 * add all non-inline backrefs for bytenr to the list
790 */
791static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
792 struct btrfs_path *path, u64 bytenr,
768 int info_level, struct list_head *prefs)
793 int info_level, struct list_head *prefs, u64 inum)
769{
770 struct btrfs_root *extent_root = fs_info->extent_root;
771 int ret;
772 int slot;
773 struct extent_buffer *leaf;
774 struct btrfs_key key;
775
776 while (1) {

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

822
823 dref = btrfs_item_ptr(leaf, slot,
824 struct btrfs_extent_data_ref);
825 count = btrfs_extent_data_ref_count(leaf, dref);
826 key.objectid = btrfs_extent_data_ref_objectid(leaf,
827 dref);
828 key.type = BTRFS_EXTENT_DATA_KEY;
829 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
794{
795 struct btrfs_root *extent_root = fs_info->extent_root;
796 int ret;
797 int slot;
798 struct extent_buffer *leaf;
799 struct btrfs_key key;
800
801 while (1) {

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

847
848 dref = btrfs_item_ptr(leaf, slot,
849 struct btrfs_extent_data_ref);
850 count = btrfs_extent_data_ref_count(leaf, dref);
851 key.objectid = btrfs_extent_data_ref_objectid(leaf,
852 dref);
853 key.type = BTRFS_EXTENT_DATA_KEY;
854 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
855
856 if (inum && key.objectid != inum) {
857 ret = BACKREF_FOUND_SHARED;
858 break;
859 }
860
830 root = btrfs_extent_data_ref_root(leaf, dref);
831 ret = __add_prelim_ref(prefs, root, &key, 0, 0,
832 bytenr, count, GFP_NOFS);
833 break;
834 }
835 default:
836 WARN_ON(1);
837 }

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

849 * indirect refs to their parent bytenr.
850 * When roots are found, they're added to the roots list
851 *
852 * FIXME some caching might speed things up
853 */
854static int find_parent_nodes(struct btrfs_trans_handle *trans,
855 struct btrfs_fs_info *fs_info, u64 bytenr,
856 u64 time_seq, struct ulist *refs,
861 root = btrfs_extent_data_ref_root(leaf, dref);
862 ret = __add_prelim_ref(prefs, root, &key, 0, 0,
863 bytenr, count, GFP_NOFS);
864 break;
865 }
866 default:
867 WARN_ON(1);
868 }

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

880 * indirect refs to their parent bytenr.
881 * When roots are found, they're added to the roots list
882 *
883 * FIXME some caching might speed things up
884 */
885static int find_parent_nodes(struct btrfs_trans_handle *trans,
886 struct btrfs_fs_info *fs_info, u64 bytenr,
887 u64 time_seq, struct ulist *refs,
857 struct ulist *roots, const u64 *extent_item_pos)
888 struct ulist *roots, const u64 *extent_item_pos,
889 u64 root_objectid, u64 inum)
858{
859 struct btrfs_key key;
860 struct btrfs_path *path;
861 struct btrfs_delayed_ref_root *delayed_refs = NULL;
862 struct btrfs_delayed_ref_head *head;
863 int info_level = 0;
864 int ret;
865 struct list_head prefs_delayed;

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

924 */
925 mutex_lock(&head->mutex);
926 mutex_unlock(&head->mutex);
927 btrfs_put_delayed_ref(&head->node);
928 goto again;
929 }
930 spin_unlock(&delayed_refs->lock);
931 ret = __add_delayed_refs(head, time_seq,
890{
891 struct btrfs_key key;
892 struct btrfs_path *path;
893 struct btrfs_delayed_ref_root *delayed_refs = NULL;
894 struct btrfs_delayed_ref_head *head;
895 int info_level = 0;
896 int ret;
897 struct list_head prefs_delayed;

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

956 */
957 mutex_lock(&head->mutex);
958 mutex_unlock(&head->mutex);
959 btrfs_put_delayed_ref(&head->node);
960 goto again;
961 }
962 spin_unlock(&delayed_refs->lock);
963 ret = __add_delayed_refs(head, time_seq,
932 &prefs_delayed, &total_refs);
964 &prefs_delayed, &total_refs,
965 inum);
933 mutex_unlock(&head->mutex);
934 if (ret)
935 goto out;
936 } else {
937 spin_unlock(&delayed_refs->lock);
938 }
939 }
940

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

946 leaf = path->nodes[0];
947 slot = path->slots[0];
948 btrfs_item_key_to_cpu(leaf, &key, slot);
949 if (key.objectid == bytenr &&
950 (key.type == BTRFS_EXTENT_ITEM_KEY ||
951 key.type == BTRFS_METADATA_ITEM_KEY)) {
952 ret = __add_inline_refs(fs_info, path, bytenr,
953 &info_level, &prefs,
966 mutex_unlock(&head->mutex);
967 if (ret)
968 goto out;
969 } else {
970 spin_unlock(&delayed_refs->lock);
971 }
972 }
973

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

979 leaf = path->nodes[0];
980 slot = path->slots[0];
981 btrfs_item_key_to_cpu(leaf, &key, slot);
982 if (key.objectid == bytenr &&
983 (key.type == BTRFS_EXTENT_ITEM_KEY ||
984 key.type == BTRFS_METADATA_ITEM_KEY)) {
985 ret = __add_inline_refs(fs_info, path, bytenr,
986 &info_level, &prefs,
954 &total_refs);
987 &total_refs, inum);
955 if (ret)
956 goto out;
957 ret = __add_keyed_refs(fs_info, path, bytenr,
988 if (ret)
989 goto out;
990 ret = __add_keyed_refs(fs_info, path, bytenr,
958 info_level, &prefs);
991 info_level, &prefs, inum);
959 if (ret)
960 goto out;
961 }
962 }
963 btrfs_release_path(path);
964
965 list_splice_init(&prefs_delayed, &prefs);
966
967 ret = __add_missing_keys(fs_info, &prefs);
968 if (ret)
969 goto out;
970
971 __merge_refs(&prefs, 1);
972
973 ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
992 if (ret)
993 goto out;
994 }
995 }
996 btrfs_release_path(path);
997
998 list_splice_init(&prefs_delayed, &prefs);
999
1000 ret = __add_missing_keys(fs_info, &prefs);
1001 if (ret)
1002 goto out;
1003
1004 __merge_refs(&prefs, 1);
1005
1006 ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
974 extent_item_pos, total_refs);
1007 extent_item_pos, total_refs,
1008 root_objectid);
975 if (ret)
976 goto out;
977
978 __merge_refs(&prefs, 2);
979
980 while (!list_empty(&prefs)) {
981 ref = list_first_entry(&prefs, struct __prelim_ref, list);
982 WARN_ON(ref->count < 0);
983 if (roots && ref->count && ref->root_id && ref->parent == 0) {
1009 if (ret)
1010 goto out;
1011
1012 __merge_refs(&prefs, 2);
1013
1014 while (!list_empty(&prefs)) {
1015 ref = list_first_entry(&prefs, struct __prelim_ref, list);
1016 WARN_ON(ref->count < 0);
1017 if (roots && ref->count && ref->root_id && ref->parent == 0) {
1018 if (root_objectid && ref->root_id != root_objectid) {
1019 ret = BACKREF_FOUND_SHARED;
1020 goto out;
1021 }
1022
984 /* no parent == root of tree */
985 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
986 if (ret < 0)
987 goto out;
988 }
989 if (ref->count && ref->parent) {
990 if (extent_item_pos && !ref->inode_list &&
991 ref->level == 0) {

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

1082{
1083 int ret;
1084
1085 *leafs = ulist_alloc(GFP_NOFS);
1086 if (!*leafs)
1087 return -ENOMEM;
1088
1089 ret = find_parent_nodes(trans, fs_info, bytenr,
1023 /* no parent == root of tree */
1024 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
1025 if (ret < 0)
1026 goto out;
1027 }
1028 if (ref->count && ref->parent) {
1029 if (extent_item_pos && !ref->inode_list &&
1030 ref->level == 0) {

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

1121{
1122 int ret;
1123
1124 *leafs = ulist_alloc(GFP_NOFS);
1125 if (!*leafs)
1126 return -ENOMEM;
1127
1128 ret = find_parent_nodes(trans, fs_info, bytenr,
1090 time_seq, *leafs, NULL, extent_item_pos);
1129 time_seq, *leafs, NULL, extent_item_pos, 0, 0);
1091 if (ret < 0 && ret != -ENOENT) {
1092 free_leaf_list(*leafs);
1093 return ret;
1094 }
1095
1096 return 0;
1097}
1098

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

1125 if (!*roots) {
1126 ulist_free(tmp);
1127 return -ENOMEM;
1128 }
1129
1130 ULIST_ITER_INIT(&uiter);
1131 while (1) {
1132 ret = find_parent_nodes(trans, fs_info, bytenr,
1130 if (ret < 0 && ret != -ENOENT) {
1131 free_leaf_list(*leafs);
1132 return ret;
1133 }
1134
1135 return 0;
1136}
1137

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

1164 if (!*roots) {
1165 ulist_free(tmp);
1166 return -ENOMEM;
1167 }
1168
1169 ULIST_ITER_INIT(&uiter);
1170 while (1) {
1171 ret = find_parent_nodes(trans, fs_info, bytenr,
1133 time_seq, tmp, *roots, NULL);
1172 time_seq, tmp, *roots, NULL, 0, 0);
1134 if (ret < 0 && ret != -ENOENT) {
1135 ulist_free(tmp);
1136 ulist_free(*roots);
1137 return ret;
1138 }
1139 node = ulist_next(tmp, &uiter);
1140 if (!node)
1141 break;

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

1156 if (!trans)
1157 down_read(&fs_info->commit_root_sem);
1158 ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
1159 if (!trans)
1160 up_read(&fs_info->commit_root_sem);
1161 return ret;
1162}
1163
1173 if (ret < 0 && ret != -ENOENT) {
1174 ulist_free(tmp);
1175 ulist_free(*roots);
1176 return ret;
1177 }
1178 node = ulist_next(tmp, &uiter);
1179 if (!node)
1180 break;

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

1195 if (!trans)
1196 down_read(&fs_info->commit_root_sem);
1197 ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
1198 if (!trans)
1199 up_read(&fs_info->commit_root_sem);
1200 return ret;
1201}
1202
1203int btrfs_check_shared(struct btrfs_trans_handle *trans,
1204 struct btrfs_fs_info *fs_info, u64 root_objectid,
1205 u64 inum, u64 bytenr)
1206{
1207 struct ulist *tmp = NULL;
1208 struct ulist *roots = NULL;
1209 struct ulist_iterator uiter;
1210 struct ulist_node *node;
1211 struct seq_list elem = {};
1212 int ret = 0;
1213
1214 tmp = ulist_alloc(GFP_NOFS);
1215 roots = ulist_alloc(GFP_NOFS);
1216 if (!tmp || !roots) {
1217 ulist_free(tmp);
1218 ulist_free(roots);
1219 return -ENOMEM;
1220 }
1221
1222 if (trans)
1223 btrfs_get_tree_mod_seq(fs_info, &elem);
1224 else
1225 down_read(&fs_info->commit_root_sem);
1226 ULIST_ITER_INIT(&uiter);
1227 while (1) {
1228 ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
1229 roots, NULL, root_objectid, inum);
1230 if (ret == BACKREF_FOUND_SHARED) {
1231 ret = 1;
1232 break;
1233 }
1234 if (ret < 0 && ret != -ENOENT)
1235 break;
1236 node = ulist_next(tmp, &uiter);
1237 if (!node)
1238 break;
1239 bytenr = node->val;
1240 cond_resched();
1241 }
1242 if (trans)
1243 btrfs_put_tree_mod_seq(fs_info, &elem);
1244 else
1245 up_read(&fs_info->commit_root_sem);
1246 ulist_free(tmp);
1247 ulist_free(roots);
1248 return ret;
1249}
1250
1164/*
1165 * this makes the path point to (inum INODE_ITEM ioff)
1166 */
1167int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
1168 struct btrfs_path *path)
1169{
1170 struct btrfs_key key;
1171 return btrfs_find_item(fs_root, path, inum, ioff,

--- 714 unchanged lines hidden --- 		1251/*
1252 * this makes the path point to (inum INODE_ITEM ioff)
1253 */
1254int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
1255 struct btrfs_path *path)
1256{
1257 struct btrfs_key key;
1258 return btrfs_find_item(fs_root, path, inum, ioff,

--- 714 unchanged lines hidden ---