backref.c (088eef2219bd1e8cb82bfcb5b32c1c687aeea6d7) backref.c (8ca15e05e6ac2745725d2d62394cfbe4ac335e84)
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,

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

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,
36 u64 extent_item_pos,
37 struct extent_inode_elem **eie)
38{
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,

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

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,
36 u64 extent_item_pos,
37 struct extent_inode_elem **eie)
38{
39 u64 data_offset;
40 u64 data_len;
39 u64 offset = 0;
41 struct extent_inode_elem *e;
42
40 struct extent_inode_elem *e;
41
43 data_offset = btrfs_file_extent_offset(eb, fi);
44 data_len = btrfs_file_extent_num_bytes(eb, fi);
42 if (!btrfs_file_extent_compression(eb, fi) &&
43 !btrfs_file_extent_encryption(eb, fi) &&
44 !btrfs_file_extent_other_encoding(eb, fi)) {
45 u64 data_offset;
46 u64 data_len;
45
47
46 if (extent_item_pos < data_offset ||
47 extent_item_pos >= data_offset + data_len)
48 return 1;
48 data_offset = btrfs_file_extent_offset(eb, fi);
49 data_len = btrfs_file_extent_num_bytes(eb, fi);
49
50
51 if (extent_item_pos < data_offset ||
52 extent_item_pos >= data_offset + data_len)
53 return 1;
54 offset = extent_item_pos - data_offset;
55 }
56
50 e = kmalloc(sizeof(*e), GFP_NOFS);
51 if (!e)
52 return -ENOMEM;
53
54 e->next = *eie;
55 e->inum = key->objectid;
57 e = kmalloc(sizeof(*e), GFP_NOFS);
58 if (!e)
59 return -ENOMEM;
60
61 e->next = *eie;
62 e->inum = key->objectid;
56 e->offset = key->offset + (extent_item_pos - data_offset);
63 e->offset = key->offset + offset;
57 *eie = e;
58
59 return 0;
60}
61
62static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
63 u64 extent_item_pos,
64 struct extent_inode_elem **eie)

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

250 return ret;
251}
252
253/*
254 * resolve an indirect backref in the form (root_id, key, level)
255 * to a logical address
256 */
257static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
64 *eie = e;
65
66 return 0;
67}
68
69static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
70 u64 extent_item_pos,
71 struct extent_inode_elem **eie)

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

257 return ret;
258}
259
260/*
261 * resolve an indirect backref in the form (root_id, key, level)
262 * to a logical address
263 */
264static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
258 int search_commit_root,
259 u64 time_seq,
260 struct __prelim_ref *ref,
261 struct ulist *parents,
262 const u64 *extent_item_pos)
265 struct btrfs_path *path, u64 time_seq,
266 struct __prelim_ref *ref,
267 struct ulist *parents,
268 const u64 *extent_item_pos)
263{
269{
264 struct btrfs_path *path;
265 struct btrfs_root *root;
266 struct btrfs_key root_key;
267 struct extent_buffer *eb;
268 int ret = 0;
269 int root_level;
270 int level = ref->level;
271
270 struct btrfs_root *root;
271 struct btrfs_key root_key;
272 struct extent_buffer *eb;
273 int ret = 0;
274 int root_level;
275 int level = ref->level;
276
272 path = btrfs_alloc_path();
273 if (!path)
274 return -ENOMEM;
275 path->search_commit_root = !!search_commit_root;
276
277 root_key.objectid = ref->root_id;
278 root_key.type = BTRFS_ROOT_ITEM_KEY;
279 root_key.offset = (u64)-1;
280 root = btrfs_read_fs_root_no_name(fs_info, &root_key);
281 if (IS_ERR(root)) {
282 ret = PTR_ERR(root);
283 goto out;
284 }

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

309 level--;
310 eb = path->nodes[level];
311 }
312
313 ret = add_all_parents(root, path, parents, level, &ref->key_for_search,
314 time_seq, ref->wanted_disk_byte,
315 extent_item_pos);
316out:
277 root_key.objectid = ref->root_id;
278 root_key.type = BTRFS_ROOT_ITEM_KEY;
279 root_key.offset = (u64)-1;
280 root = btrfs_read_fs_root_no_name(fs_info, &root_key);
281 if (IS_ERR(root)) {
282 ret = PTR_ERR(root);
283 goto out;
284 }

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

309 level--;
310 eb = path->nodes[level];
311 }
312
313 ret = add_all_parents(root, path, parents, level, &ref->key_for_search,
314 time_seq, ref->wanted_disk_byte,
315 extent_item_pos);
316out:
317 btrfs_free_path(path);
317 path->lowest_level = 0;
318 btrfs_release_path(path);
318 return ret;
319}
320
321/*
322 * resolve all indirect backrefs from the list
323 */
324static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
319 return ret;
320}
321
322/*
323 * resolve all indirect backrefs from the list
324 */
325static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
325 int search_commit_root, u64 time_seq,
326 struct btrfs_path *path, u64 time_seq,
326 struct list_head *head,
327 const u64 *extent_item_pos)
328{
329 int err;
330 int ret = 0;
331 struct __prelim_ref *ref;
332 struct __prelim_ref *ref_safe;
333 struct __prelim_ref *new_ref;

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

344 * iterating over the newly inserted items.
345 * we're also allowed to re-assign ref during iteration.
346 */
347 list_for_each_entry_safe(ref, ref_safe, head, list) {
348 if (ref->parent) /* already direct */
349 continue;
350 if (ref->count == 0)
351 continue;
327 struct list_head *head,
328 const u64 *extent_item_pos)
329{
330 int err;
331 int ret = 0;
332 struct __prelim_ref *ref;
333 struct __prelim_ref *ref_safe;
334 struct __prelim_ref *new_ref;

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

345 * iterating over the newly inserted items.
346 * we're also allowed to re-assign ref during iteration.
347 */
348 list_for_each_entry_safe(ref, ref_safe, head, list) {
349 if (ref->parent) /* already direct */
350 continue;
351 if (ref->count == 0)
352 continue;
352 err = __resolve_indirect_ref(fs_info, search_commit_root,
353 time_seq, ref, parents,
354 extent_item_pos);
353 err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
354 parents, extent_item_pos);
355 if (err == -ENOMEM)
356 goto out;
357 if (err)
358 continue;
359
360 /* we put the first parent into the ref at hand */
361 ULIST_ITER_INIT(&uiter);
362 node = ulist_next(parents, &uiter);

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

599static int __add_inline_refs(struct btrfs_fs_info *fs_info,
600 struct btrfs_path *path, u64 bytenr,
601 int *info_level, struct list_head *prefs)
602{
603 int ret = 0;
604 int slot;
605 struct extent_buffer *leaf;
606 struct btrfs_key key;
355 if (err == -ENOMEM)
356 goto out;
357 if (err)
358 continue;
359
360 /* we put the first parent into the ref at hand */
361 ULIST_ITER_INIT(&uiter);
362 node = ulist_next(parents, &uiter);

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

599static int __add_inline_refs(struct btrfs_fs_info *fs_info,
600 struct btrfs_path *path, u64 bytenr,
601 int *info_level, struct list_head *prefs)
602{
603 int ret = 0;
604 int slot;
605 struct extent_buffer *leaf;
606 struct btrfs_key key;
607 struct btrfs_key found_key;
607 unsigned long ptr;
608 unsigned long end;
609 struct btrfs_extent_item *ei;
610 u64 flags;
611 u64 item_size;
612
613 /*
614 * enumerate all inline refs
615 */
616 leaf = path->nodes[0];
617 slot = path->slots[0];
618
619 item_size = btrfs_item_size_nr(leaf, slot);
620 BUG_ON(item_size < sizeof(*ei));
621
622 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
623 flags = btrfs_extent_flags(leaf, ei);
608 unsigned long ptr;
609 unsigned long end;
610 struct btrfs_extent_item *ei;
611 u64 flags;
612 u64 item_size;
613
614 /*
615 * enumerate all inline refs
616 */
617 leaf = path->nodes[0];
618 slot = path->slots[0];
619
620 item_size = btrfs_item_size_nr(leaf, slot);
621 BUG_ON(item_size < sizeof(*ei));
622
623 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
624 flags = btrfs_extent_flags(leaf, ei);
625 btrfs_item_key_to_cpu(leaf, &found_key, slot);
624
625 ptr = (unsigned long)(ei + 1);
626 end = (unsigned long)ei + item_size;
627
626
627 ptr = (unsigned long)(ei + 1);
628 end = (unsigned long)ei + item_size;
629
628 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
630 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
631 flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
629 struct btrfs_tree_block_info *info;
630
631 info = (struct btrfs_tree_block_info *)ptr;
632 *info_level = btrfs_tree_block_level(leaf, info);
633 ptr += sizeof(struct btrfs_tree_block_info);
634 BUG_ON(ptr > end);
632 struct btrfs_tree_block_info *info;
633
634 info = (struct btrfs_tree_block_info *)ptr;
635 *info_level = btrfs_tree_block_level(leaf, info);
636 ptr += sizeof(struct btrfs_tree_block_info);
637 BUG_ON(ptr > end);
638 } else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
639 *info_level = found_key.offset;
635 } else {
636 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
637 }
638
639 while (ptr < end) {
640 struct btrfs_extent_inline_ref *iref;
641 u64 offset;
642 int type;

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

790 struct ulist *roots, const u64 *extent_item_pos)
791{
792 struct btrfs_key key;
793 struct btrfs_path *path;
794 struct btrfs_delayed_ref_root *delayed_refs = NULL;
795 struct btrfs_delayed_ref_head *head;
796 int info_level = 0;
797 int ret;
640 } else {
641 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
642 }
643
644 while (ptr < end) {
645 struct btrfs_extent_inline_ref *iref;
646 u64 offset;
647 int type;

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

795 struct ulist *roots, const u64 *extent_item_pos)
796{
797 struct btrfs_key key;
798 struct btrfs_path *path;
799 struct btrfs_delayed_ref_root *delayed_refs = NULL;
800 struct btrfs_delayed_ref_head *head;
801 int info_level = 0;
802 int ret;
798 int search_commit_root = (trans == BTRFS_BACKREF_SEARCH_COMMIT_ROOT);
799 struct list_head prefs_delayed;
800 struct list_head prefs;
801 struct __prelim_ref *ref;
802
803 INIT_LIST_HEAD(&prefs);
804 INIT_LIST_HEAD(&prefs_delayed);
805
806 key.objectid = bytenr;
803 struct list_head prefs_delayed;
804 struct list_head prefs;
805 struct __prelim_ref *ref;
806
807 INIT_LIST_HEAD(&prefs);
808 INIT_LIST_HEAD(&prefs_delayed);
809
810 key.objectid = bytenr;
807 key.type = BTRFS_EXTENT_ITEM_KEY;
808 key.offset = (u64)-1;
811 key.offset = (u64)-1;
812 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
813 key.type = BTRFS_METADATA_ITEM_KEY;
814 else
815 key.type = BTRFS_EXTENT_ITEM_KEY;
809
810 path = btrfs_alloc_path();
811 if (!path)
812 return -ENOMEM;
816
817 path = btrfs_alloc_path();
818 if (!path)
819 return -ENOMEM;
813 path->search_commit_root = !!search_commit_root;
820 if (!trans)
821 path->search_commit_root = 1;
814
815 /*
816 * grab both a lock on the path and a lock on the delayed ref head.
817 * We need both to get a consistent picture of how the refs look
818 * at a specified point in time
819 */
820again:
821 head = NULL;
822
823 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
824 if (ret < 0)
825 goto out;
826 BUG_ON(ret == 0);
827
822
823 /*
824 * grab both a lock on the path and a lock on the delayed ref head.
825 * We need both to get a consistent picture of how the refs look
826 * at a specified point in time
827 */
828again:
829 head = NULL;
830
831 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
832 if (ret < 0)
833 goto out;
834 BUG_ON(ret == 0);
835
828 if (trans != BTRFS_BACKREF_SEARCH_COMMIT_ROOT) {
836 if (trans) {
829 /*
830 * look if there are updates for this ref queued and lock the
831 * head
832 */
833 delayed_refs = &trans->transaction->delayed_refs;
834 spin_lock(&delayed_refs->lock);
835 head = btrfs_find_delayed_ref_head(trans, bytenr);
836 if (head) {

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

864 struct extent_buffer *leaf;
865 int slot;
866
867 path->slots[0]--;
868 leaf = path->nodes[0];
869 slot = path->slots[0];
870 btrfs_item_key_to_cpu(leaf, &key, slot);
871 if (key.objectid == bytenr &&
837 /*
838 * look if there are updates for this ref queued and lock the
839 * head
840 */
841 delayed_refs = &trans->transaction->delayed_refs;
842 spin_lock(&delayed_refs->lock);
843 head = btrfs_find_delayed_ref_head(trans, bytenr);
844 if (head) {

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

872 struct extent_buffer *leaf;
873 int slot;
874
875 path->slots[0]--;
876 leaf = path->nodes[0];
877 slot = path->slots[0];
878 btrfs_item_key_to_cpu(leaf, &key, slot);
879 if (key.objectid == bytenr &&
872 key.type == BTRFS_EXTENT_ITEM_KEY) {
880 (key.type == BTRFS_EXTENT_ITEM_KEY ||
881 key.type == BTRFS_METADATA_ITEM_KEY)) {
873 ret = __add_inline_refs(fs_info, path, bytenr,
874 &info_level, &prefs);
875 if (ret)
876 goto out;
877 ret = __add_keyed_refs(fs_info, path, bytenr,
878 info_level, &prefs);
879 if (ret)
880 goto out;

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

885 list_splice_init(&prefs_delayed, &prefs);
886
887 ret = __add_missing_keys(fs_info, &prefs);
888 if (ret)
889 goto out;
890
891 __merge_refs(&prefs, 1);
892
882 ret = __add_inline_refs(fs_info, path, bytenr,
883 &info_level, &prefs);
884 if (ret)
885 goto out;
886 ret = __add_keyed_refs(fs_info, path, bytenr,
887 info_level, &prefs);
888 if (ret)
889 goto out;

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

894 list_splice_init(&prefs_delayed, &prefs);
895
896 ret = __add_missing_keys(fs_info, &prefs);
897 if (ret)
898 goto out;
899
900 __merge_refs(&prefs, 1);
901
893 ret = __resolve_indirect_refs(fs_info, search_commit_root, time_seq,
894 &prefs, extent_item_pos);
902 ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
903 extent_item_pos);
895 if (ret)
896 goto out;
897
898 __merge_refs(&prefs, 2);
899
900 while (!list_empty(&prefs)) {
901 ref = list_first_entry(&prefs, struct __prelim_ref, list);
902 list_del(&ref->list);

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

1278 * tree blocks and <0 on error.
1279 */
1280int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1281 struct btrfs_path *path, struct btrfs_key *found_key,
1282 u64 *flags_ret)
1283{
1284 int ret;
1285 u64 flags;
904 if (ret)
905 goto out;
906
907 __merge_refs(&prefs, 2);
908
909 while (!list_empty(&prefs)) {
910 ref = list_first_entry(&prefs, struct __prelim_ref, list);
911 list_del(&ref->list);

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

1287 * tree blocks and <0 on error.
1288 */
1289int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1290 struct btrfs_path *path, struct btrfs_key *found_key,
1291 u64 *flags_ret)
1292{
1293 int ret;
1294 u64 flags;
1295 u64 size = 0;
1286 u32 item_size;
1287 struct extent_buffer *eb;
1288 struct btrfs_extent_item *ei;
1289 struct btrfs_key key;
1290
1296 u32 item_size;
1297 struct extent_buffer *eb;
1298 struct btrfs_extent_item *ei;
1299 struct btrfs_key key;
1300
1291 key.type = BTRFS_EXTENT_ITEM_KEY;
1301 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1302 key.type = BTRFS_METADATA_ITEM_KEY;
1303 else
1304 key.type = BTRFS_EXTENT_ITEM_KEY;
1292 key.objectid = logical;
1293 key.offset = (u64)-1;
1294
1295 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
1296 if (ret < 0)
1297 return ret;
1298 ret = btrfs_previous_item(fs_info->extent_root, path,
1299 0, BTRFS_EXTENT_ITEM_KEY);
1300 if (ret < 0)
1301 return ret;
1302
1303 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1305 key.objectid = logical;
1306 key.offset = (u64)-1;
1307
1308 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
1309 if (ret < 0)
1310 return ret;
1311 ret = btrfs_previous_item(fs_info->extent_root, path,
1312 0, BTRFS_EXTENT_ITEM_KEY);
1313 if (ret < 0)
1314 return ret;
1315
1316 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1304 if (found_key->type != BTRFS_EXTENT_ITEM_KEY ||
1317 if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1318 size = fs_info->extent_root->leafsize;
1319 else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
1320 size = found_key->offset;
1321
1322 if ((found_key->type != BTRFS_EXTENT_ITEM_KEY &&
1323 found_key->type != BTRFS_METADATA_ITEM_KEY) ||
1305 found_key->objectid > logical ||
1324 found_key->objectid > logical ||
1306 found_key->objectid + found_key->offset <= logical) {
1325 found_key->objectid + size <= logical) {
1307 pr_debug("logical %llu is not within any extent\n",
1308 (unsigned long long)logical);
1309 return -ENOENT;
1310 }
1311
1312 eb = path->nodes[0];
1313 item_size = btrfs_item_size_nr(eb, path->slots[0]);
1314 BUG_ON(item_size < sizeof(*ei));

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

1454 * when the iterator function returns a non-zero value, iteration stops.
1455 */
1456int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
1457 u64 extent_item_objectid, u64 extent_item_pos,
1458 int search_commit_root,
1459 iterate_extent_inodes_t *iterate, void *ctx)
1460{
1461 int ret;
1326 pr_debug("logical %llu is not within any extent\n",
1327 (unsigned long long)logical);
1328 return -ENOENT;
1329 }
1330
1331 eb = path->nodes[0];
1332 item_size = btrfs_item_size_nr(eb, path->slots[0]);
1333 BUG_ON(item_size < sizeof(*ei));

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

1473 * when the iterator function returns a non-zero value, iteration stops.
1474 */
1475int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
1476 u64 extent_item_objectid, u64 extent_item_pos,
1477 int search_commit_root,
1478 iterate_extent_inodes_t *iterate, void *ctx)
1479{
1480 int ret;
1462 struct btrfs_trans_handle *trans;
1481 struct btrfs_trans_handle *trans = NULL;
1463 struct ulist *refs = NULL;
1464 struct ulist *roots = NULL;
1465 struct ulist_node *ref_node = NULL;
1466 struct ulist_node *root_node = NULL;
1467 struct seq_list tree_mod_seq_elem = {};
1468 struct ulist_iterator ref_uiter;
1469 struct ulist_iterator root_uiter;
1470
1471 pr_debug("resolving all inodes for extent %llu\n",
1472 extent_item_objectid);
1473
1482 struct ulist *refs = NULL;
1483 struct ulist *roots = NULL;
1484 struct ulist_node *ref_node = NULL;
1485 struct ulist_node *root_node = NULL;
1486 struct seq_list tree_mod_seq_elem = {};
1487 struct ulist_iterator ref_uiter;
1488 struct ulist_iterator root_uiter;
1489
1490 pr_debug("resolving all inodes for extent %llu\n",
1491 extent_item_objectid);
1492
1474 if (search_commit_root) {
1475 trans = BTRFS_BACKREF_SEARCH_COMMIT_ROOT;
1476 } else {
1493 if (!search_commit_root) {
1477 trans = btrfs_join_transaction(fs_info->extent_root);
1478 if (IS_ERR(trans))
1479 return PTR_ERR(trans);
1480 btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1481 }
1482
1483 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1484 tree_mod_seq_elem.seq, &refs,

--- 323 unchanged lines hidden --- 		1494 trans = btrfs_join_transaction(fs_info->extent_root);
1495 if (IS_ERR(trans))
1496 return PTR_ERR(trans);
1497 btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1498 }
1499
1500 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1501 tree_mod_seq_elem.seq, &refs,

--- 323 unchanged lines hidden ---