2 * Copyright (C) 2007 Oracle. All rights reserved.
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.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
23 #include <sys/types.h>
27 #include <uuid/uuid.h>
32 #include "print-tree.h"
33 #include "task-utils.h"
34 #include "transaction.h"
37 #include "free-space-cache.h"
38 #include "free-space-tree.h"
40 #include "qgroup-verify.h"
41 #include "rbtree-utils.h"
43 #include "kernel-shared/ulist.h"
46 #include "check/mode-common.h"
47 #include "check/mode-original.h"
48 #include "check/mode-lowmem.h"
54 TASK_NOTHING, /* have to be the last element */
59 enum task_position tp;
61 struct task_info *info;
65 u64 total_csum_bytes = 0;
66 u64 total_btree_bytes = 0;
67 u64 total_fs_tree_bytes = 0;
68 u64 total_extent_tree_bytes = 0;
69 u64 btree_space_waste = 0;
70 u64 data_bytes_allocated = 0;
71 u64 data_bytes_referenced = 0;
72 LIST_HEAD(duplicate_extents);
73 LIST_HEAD(delete_items);
75 int init_extent_tree = 0;
76 int check_data_csum = 0;
77 struct btrfs_fs_info *global_info;
78 struct task_ctx ctx = { 0 };
79 struct cache_tree *roots_info_cache = NULL;
81 enum btrfs_check_mode {
85 CHECK_MODE_DEFAULT = CHECK_MODE_ORIGINAL
88 static enum btrfs_check_mode check_mode = CHECK_MODE_DEFAULT;
90 static int compare_data_backref(struct rb_node *node1, struct rb_node *node2)
92 struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
93 struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
94 struct data_backref *back1 = to_data_backref(ext1);
95 struct data_backref *back2 = to_data_backref(ext2);
97 WARN_ON(!ext1->is_data);
98 WARN_ON(!ext2->is_data);
100 /* parent and root are a union, so this covers both */
101 if (back1->parent > back2->parent)
103 if (back1->parent < back2->parent)
106 /* This is a full backref and the parents match. */
107 if (back1->node.full_backref)
110 if (back1->owner > back2->owner)
112 if (back1->owner < back2->owner)
115 if (back1->offset > back2->offset)
117 if (back1->offset < back2->offset)
120 if (back1->found_ref && back2->found_ref) {
121 if (back1->disk_bytenr > back2->disk_bytenr)
123 if (back1->disk_bytenr < back2->disk_bytenr)
126 if (back1->bytes > back2->bytes)
128 if (back1->bytes < back2->bytes)
135 static int compare_tree_backref(struct rb_node *node1, struct rb_node *node2)
137 struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
138 struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
139 struct tree_backref *back1 = to_tree_backref(ext1);
140 struct tree_backref *back2 = to_tree_backref(ext2);
142 WARN_ON(ext1->is_data);
143 WARN_ON(ext2->is_data);
145 /* parent and root are a union, so this covers both */
146 if (back1->parent > back2->parent)
148 if (back1->parent < back2->parent)
154 static int compare_extent_backref(struct rb_node *node1, struct rb_node *node2)
156 struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
157 struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
159 if (ext1->is_data > ext2->is_data)
162 if (ext1->is_data < ext2->is_data)
165 if (ext1->full_backref > ext2->full_backref)
167 if (ext1->full_backref < ext2->full_backref)
171 return compare_data_backref(node1, node2);
173 return compare_tree_backref(node1, node2);
177 static void *print_status_check(void *p)
179 struct task_ctx *priv = p;
180 const char work_indicator[] = { '.', 'o', 'O', 'o' };
182 static char *task_position_string[] = {
184 "checking free space cache",
188 task_period_start(priv->info, 1000 /* 1s */);
190 if (priv->tp == TASK_NOTHING)
194 printf("%s [%c]\r", task_position_string[priv->tp],
195 work_indicator[count % 4]);
198 task_period_wait(priv->info);
203 static int print_status_return(void *p)
211 static enum btrfs_check_mode parse_check_mode(const char *str)
213 if (strcmp(str, "lowmem") == 0)
214 return CHECK_MODE_LOWMEM;
215 if (strcmp(str, "orig") == 0)
216 return CHECK_MODE_ORIGINAL;
217 if (strcmp(str, "original") == 0)
218 return CHECK_MODE_ORIGINAL;
220 return CHECK_MODE_UNKNOWN;
223 /* Compatible function to allow reuse of old codes */
224 static u64 first_extent_gap(struct rb_root *holes)
226 struct file_extent_hole *hole;
228 if (RB_EMPTY_ROOT(holes))
231 hole = rb_entry(rb_first(holes), struct file_extent_hole, node);
235 static int compare_hole(struct rb_node *node1, struct rb_node *node2)
237 struct file_extent_hole *hole1;
238 struct file_extent_hole *hole2;
240 hole1 = rb_entry(node1, struct file_extent_hole, node);
241 hole2 = rb_entry(node2, struct file_extent_hole, node);
243 if (hole1->start > hole2->start)
245 if (hole1->start < hole2->start)
247 /* Now hole1->start == hole2->start */
248 if (hole1->len >= hole2->len)
250 * Hole 1 will be merge center
251 * Same hole will be merged later
254 /* Hole 2 will be merge center */
259 * Add a hole to the record
261 * This will do hole merge for copy_file_extent_holes(),
262 * which will ensure there won't be continuous holes.
264 static int add_file_extent_hole(struct rb_root *holes,
267 struct file_extent_hole *hole;
268 struct file_extent_hole *prev = NULL;
269 struct file_extent_hole *next = NULL;
271 hole = malloc(sizeof(*hole));
276 /* Since compare will not return 0, no -EEXIST will happen */
277 rb_insert(holes, &hole->node, compare_hole);
279 /* simple merge with previous hole */
280 if (rb_prev(&hole->node))
281 prev = rb_entry(rb_prev(&hole->node), struct file_extent_hole,
283 if (prev && prev->start + prev->len >= hole->start) {
284 hole->len = hole->start + hole->len - prev->start;
285 hole->start = prev->start;
286 rb_erase(&prev->node, holes);
291 /* iterate merge with next holes */
293 if (!rb_next(&hole->node))
295 next = rb_entry(rb_next(&hole->node), struct file_extent_hole,
297 if (hole->start + hole->len >= next->start) {
298 if (hole->start + hole->len <= next->start + next->len)
299 hole->len = next->start + next->len -
301 rb_erase(&next->node, holes);
310 static int compare_hole_range(struct rb_node *node, void *data)
312 struct file_extent_hole *hole;
315 hole = (struct file_extent_hole *)data;
318 hole = rb_entry(node, struct file_extent_hole, node);
319 if (start < hole->start)
321 if (start >= hole->start && start < hole->start + hole->len)
327 * Delete a hole in the record
329 * This will do the hole split and is much restrict than add.
331 static int del_file_extent_hole(struct rb_root *holes,
334 struct file_extent_hole *hole;
335 struct file_extent_hole tmp;
340 struct rb_node *node;
347 node = rb_search(holes, &tmp, compare_hole_range, NULL);
350 hole = rb_entry(node, struct file_extent_hole, node);
351 if (start + len > hole->start + hole->len)
355 * Now there will be no overlap, delete the hole and re-add the
356 * split(s) if they exists.
358 if (start > hole->start) {
359 prev_start = hole->start;
360 prev_len = start - hole->start;
363 if (hole->start + hole->len > start + len) {
364 next_start = start + len;
365 next_len = hole->start + hole->len - start - len;
368 rb_erase(node, holes);
371 ret = add_file_extent_hole(holes, prev_start, prev_len);
376 ret = add_file_extent_hole(holes, next_start, next_len);
383 static int copy_file_extent_holes(struct rb_root *dst,
386 struct file_extent_hole *hole;
387 struct rb_node *node;
390 node = rb_first(src);
392 hole = rb_entry(node, struct file_extent_hole, node);
393 ret = add_file_extent_hole(dst, hole->start, hole->len);
396 node = rb_next(node);
401 static void free_file_extent_holes(struct rb_root *holes)
403 struct rb_node *node;
404 struct file_extent_hole *hole;
406 node = rb_first(holes);
408 hole = rb_entry(node, struct file_extent_hole, node);
409 rb_erase(node, holes);
411 node = rb_first(holes);
415 static void record_root_in_trans(struct btrfs_trans_handle *trans,
416 struct btrfs_root *root)
418 if (root->last_trans != trans->transid) {
419 root->track_dirty = 1;
420 root->last_trans = trans->transid;
421 root->commit_root = root->node;
422 extent_buffer_get(root->node);
426 static int device_record_compare(struct rb_node *node1, struct rb_node *node2)
428 struct device_record *rec1;
429 struct device_record *rec2;
431 rec1 = rb_entry(node1, struct device_record, node);
432 rec2 = rb_entry(node2, struct device_record, node);
433 if (rec1->devid > rec2->devid)
435 else if (rec1->devid < rec2->devid)
441 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
443 struct inode_record *rec;
444 struct inode_backref *backref;
445 struct inode_backref *orig;
446 struct inode_backref *tmp;
447 struct orphan_data_extent *src_orphan;
448 struct orphan_data_extent *dst_orphan;
453 rec = malloc(sizeof(*rec));
455 return ERR_PTR(-ENOMEM);
456 memcpy(rec, orig_rec, sizeof(*rec));
458 INIT_LIST_HEAD(&rec->backrefs);
459 INIT_LIST_HEAD(&rec->orphan_extents);
460 rec->holes = RB_ROOT;
462 list_for_each_entry(orig, &orig_rec->backrefs, list) {
463 size = sizeof(*orig) + orig->namelen + 1;
464 backref = malloc(size);
469 memcpy(backref, orig, size);
470 list_add_tail(&backref->list, &rec->backrefs);
472 list_for_each_entry(src_orphan, &orig_rec->orphan_extents, list) {
473 dst_orphan = malloc(sizeof(*dst_orphan));
478 memcpy(dst_orphan, src_orphan, sizeof(*src_orphan));
479 list_add_tail(&dst_orphan->list, &rec->orphan_extents);
481 ret = copy_file_extent_holes(&rec->holes, &orig_rec->holes);
488 rb = rb_first(&rec->holes);
490 struct file_extent_hole *hole;
492 hole = rb_entry(rb, struct file_extent_hole, node);
498 if (!list_empty(&rec->backrefs))
499 list_for_each_entry_safe(orig, tmp, &rec->backrefs, list) {
500 list_del(&orig->list);
504 if (!list_empty(&rec->orphan_extents))
505 list_for_each_entry_safe(orig, tmp, &rec->orphan_extents, list) {
506 list_del(&orig->list);
515 static void print_orphan_data_extents(struct list_head *orphan_extents,
518 struct orphan_data_extent *orphan;
520 if (list_empty(orphan_extents))
522 printf("The following data extent is lost in tree %llu:\n",
524 list_for_each_entry(orphan, orphan_extents, list) {
525 printf("\tinode: %llu, offset:%llu, disk_bytenr: %llu, disk_len: %llu\n",
526 orphan->objectid, orphan->offset, orphan->disk_bytenr,
531 static void print_inode_error(struct btrfs_root *root, struct inode_record *rec)
533 u64 root_objectid = root->root_key.objectid;
534 int errors = rec->errors;
538 /* reloc root errors, we print its corresponding fs root objectid*/
539 if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
540 root_objectid = root->root_key.offset;
541 fprintf(stderr, "reloc");
543 fprintf(stderr, "root %llu inode %llu errors %x",
544 (unsigned long long) root_objectid,
545 (unsigned long long) rec->ino, rec->errors);
547 if (errors & I_ERR_NO_INODE_ITEM)
548 fprintf(stderr, ", no inode item");
549 if (errors & I_ERR_NO_ORPHAN_ITEM)
550 fprintf(stderr, ", no orphan item");
551 if (errors & I_ERR_DUP_INODE_ITEM)
552 fprintf(stderr, ", dup inode item");
553 if (errors & I_ERR_DUP_DIR_INDEX)
554 fprintf(stderr, ", dup dir index");
555 if (errors & I_ERR_ODD_DIR_ITEM)
556 fprintf(stderr, ", odd dir item");
557 if (errors & I_ERR_ODD_FILE_EXTENT)
558 fprintf(stderr, ", odd file extent");
559 if (errors & I_ERR_BAD_FILE_EXTENT)
560 fprintf(stderr, ", bad file extent");
561 if (errors & I_ERR_FILE_EXTENT_OVERLAP)
562 fprintf(stderr, ", file extent overlap");
563 if (errors & I_ERR_FILE_EXTENT_DISCOUNT)
564 fprintf(stderr, ", file extent discount");
565 if (errors & I_ERR_DIR_ISIZE_WRONG)
566 fprintf(stderr, ", dir isize wrong");
567 if (errors & I_ERR_FILE_NBYTES_WRONG)
568 fprintf(stderr, ", nbytes wrong");
569 if (errors & I_ERR_ODD_CSUM_ITEM)
570 fprintf(stderr, ", odd csum item");
571 if (errors & I_ERR_SOME_CSUM_MISSING)
572 fprintf(stderr, ", some csum missing");
573 if (errors & I_ERR_LINK_COUNT_WRONG)
574 fprintf(stderr, ", link count wrong");
575 if (errors & I_ERR_FILE_EXTENT_ORPHAN)
576 fprintf(stderr, ", orphan file extent");
577 fprintf(stderr, "\n");
578 /* Print the orphan extents if needed */
579 if (errors & I_ERR_FILE_EXTENT_ORPHAN)
580 print_orphan_data_extents(&rec->orphan_extents, root->objectid);
582 /* Print the holes if needed */
583 if (errors & I_ERR_FILE_EXTENT_DISCOUNT) {
584 struct file_extent_hole *hole;
585 struct rb_node *node;
588 node = rb_first(&rec->holes);
589 fprintf(stderr, "Found file extent holes:\n");
592 hole = rb_entry(node, struct file_extent_hole, node);
593 fprintf(stderr, "\tstart: %llu, len: %llu\n",
594 hole->start, hole->len);
595 node = rb_next(node);
598 fprintf(stderr, "\tstart: 0, len: %llu\n",
600 root->fs_info->sectorsize));
604 static void print_ref_error(int errors)
606 if (errors & REF_ERR_NO_DIR_ITEM)
607 fprintf(stderr, ", no dir item");
608 if (errors & REF_ERR_NO_DIR_INDEX)
609 fprintf(stderr, ", no dir index");
610 if (errors & REF_ERR_NO_INODE_REF)
611 fprintf(stderr, ", no inode ref");
612 if (errors & REF_ERR_DUP_DIR_ITEM)
613 fprintf(stderr, ", dup dir item");
614 if (errors & REF_ERR_DUP_DIR_INDEX)
615 fprintf(stderr, ", dup dir index");
616 if (errors & REF_ERR_DUP_INODE_REF)
617 fprintf(stderr, ", dup inode ref");
618 if (errors & REF_ERR_INDEX_UNMATCH)
619 fprintf(stderr, ", index mismatch");
620 if (errors & REF_ERR_FILETYPE_UNMATCH)
621 fprintf(stderr, ", filetype mismatch");
622 if (errors & REF_ERR_NAME_TOO_LONG)
623 fprintf(stderr, ", name too long");
624 if (errors & REF_ERR_NO_ROOT_REF)
625 fprintf(stderr, ", no root ref");
626 if (errors & REF_ERR_NO_ROOT_BACKREF)
627 fprintf(stderr, ", no root backref");
628 if (errors & REF_ERR_DUP_ROOT_REF)
629 fprintf(stderr, ", dup root ref");
630 if (errors & REF_ERR_DUP_ROOT_BACKREF)
631 fprintf(stderr, ", dup root backref");
632 fprintf(stderr, "\n");
635 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
638 struct ptr_node *node;
639 struct cache_extent *cache;
640 struct inode_record *rec = NULL;
643 cache = lookup_cache_extent(inode_cache, ino, 1);
645 node = container_of(cache, struct ptr_node, cache);
647 if (mod && rec->refs > 1) {
648 node->data = clone_inode_rec(rec);
649 if (IS_ERR(node->data))
655 rec = calloc(1, sizeof(*rec));
657 return ERR_PTR(-ENOMEM);
659 rec->extent_start = (u64)-1;
661 INIT_LIST_HEAD(&rec->backrefs);
662 INIT_LIST_HEAD(&rec->orphan_extents);
663 rec->holes = RB_ROOT;
665 node = malloc(sizeof(*node));
668 return ERR_PTR(-ENOMEM);
670 node->cache.start = ino;
671 node->cache.size = 1;
674 if (ino == BTRFS_FREE_INO_OBJECTID)
677 ret = insert_cache_extent(inode_cache, &node->cache);
679 return ERR_PTR(-EEXIST);
684 static void free_orphan_data_extents(struct list_head *orphan_extents)
686 struct orphan_data_extent *orphan;
688 while (!list_empty(orphan_extents)) {
689 orphan = list_entry(orphan_extents->next,
690 struct orphan_data_extent, list);
691 list_del(&orphan->list);
696 static void free_inode_rec(struct inode_record *rec)
698 struct inode_backref *backref;
703 while (!list_empty(&rec->backrefs)) {
704 backref = to_inode_backref(rec->backrefs.next);
705 list_del(&backref->list);
708 free_orphan_data_extents(&rec->orphan_extents);
709 free_file_extent_holes(&rec->holes);
713 static int can_free_inode_rec(struct inode_record *rec)
715 if (!rec->errors && rec->checked && rec->found_inode_item &&
716 rec->nlink == rec->found_link && list_empty(&rec->backrefs))
721 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
722 struct inode_record *rec)
724 struct cache_extent *cache;
725 struct inode_backref *tmp, *backref;
726 struct ptr_node *node;
729 if (!rec->found_inode_item)
732 filetype = imode_to_type(rec->imode);
733 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
734 if (backref->found_dir_item && backref->found_dir_index) {
735 if (backref->filetype != filetype)
736 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
737 if (!backref->errors && backref->found_inode_ref &&
738 rec->nlink == rec->found_link) {
739 list_del(&backref->list);
745 if (!rec->checked || rec->merging)
748 if (S_ISDIR(rec->imode)) {
749 if (rec->found_size != rec->isize)
750 rec->errors |= I_ERR_DIR_ISIZE_WRONG;
751 if (rec->found_file_extent)
752 rec->errors |= I_ERR_ODD_FILE_EXTENT;
753 } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
754 if (rec->found_dir_item)
755 rec->errors |= I_ERR_ODD_DIR_ITEM;
756 if (rec->found_size != rec->nbytes)
757 rec->errors |= I_ERR_FILE_NBYTES_WRONG;
758 if (rec->nlink > 0 && !no_holes &&
759 (rec->extent_end < rec->isize ||
760 first_extent_gap(&rec->holes) < rec->isize))
761 rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
764 if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
765 if (rec->found_csum_item && rec->nodatasum)
766 rec->errors |= I_ERR_ODD_CSUM_ITEM;
767 if (rec->some_csum_missing && !rec->nodatasum)
768 rec->errors |= I_ERR_SOME_CSUM_MISSING;
771 BUG_ON(rec->refs != 1);
772 if (can_free_inode_rec(rec)) {
773 cache = lookup_cache_extent(inode_cache, rec->ino, 1);
774 node = container_of(cache, struct ptr_node, cache);
775 BUG_ON(node->data != rec);
776 remove_cache_extent(inode_cache, &node->cache);
782 static int check_orphan_item(struct btrfs_root *root, u64 ino)
784 struct btrfs_path path;
785 struct btrfs_key key;
788 key.objectid = BTRFS_ORPHAN_OBJECTID;
789 key.type = BTRFS_ORPHAN_ITEM_KEY;
792 btrfs_init_path(&path);
793 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
794 btrfs_release_path(&path);
800 static int process_inode_item(struct extent_buffer *eb,
801 int slot, struct btrfs_key *key,
802 struct shared_node *active_node)
804 struct inode_record *rec;
805 struct btrfs_inode_item *item;
807 rec = active_node->current;
808 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
809 if (rec->found_inode_item) {
810 rec->errors |= I_ERR_DUP_INODE_ITEM;
813 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
814 rec->nlink = btrfs_inode_nlink(eb, item);
815 rec->isize = btrfs_inode_size(eb, item);
816 rec->nbytes = btrfs_inode_nbytes(eb, item);
817 rec->imode = btrfs_inode_mode(eb, item);
818 if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
820 rec->found_inode_item = 1;
822 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
823 maybe_free_inode_rec(&active_node->inode_cache, rec);
827 static struct inode_backref *get_inode_backref(struct inode_record *rec,
829 int namelen, u64 dir)
831 struct inode_backref *backref;
833 list_for_each_entry(backref, &rec->backrefs, list) {
834 if (rec->ino == BTRFS_MULTIPLE_OBJECTIDS)
836 if (backref->dir != dir || backref->namelen != namelen)
838 if (memcmp(name, backref->name, namelen))
843 backref = malloc(sizeof(*backref) + namelen + 1);
846 memset(backref, 0, sizeof(*backref));
848 backref->namelen = namelen;
849 memcpy(backref->name, name, namelen);
850 backref->name[namelen] = '\0';
851 list_add_tail(&backref->list, &rec->backrefs);
855 static int add_inode_backref(struct cache_tree *inode_cache,
856 u64 ino, u64 dir, u64 index,
857 const char *name, int namelen,
858 u8 filetype, u8 itemtype, int errors)
860 struct inode_record *rec;
861 struct inode_backref *backref;
863 rec = get_inode_rec(inode_cache, ino, 1);
865 backref = get_inode_backref(rec, name, namelen, dir);
868 backref->errors |= errors;
869 if (itemtype == BTRFS_DIR_INDEX_KEY) {
870 if (backref->found_dir_index)
871 backref->errors |= REF_ERR_DUP_DIR_INDEX;
872 if (backref->found_inode_ref && backref->index != index)
873 backref->errors |= REF_ERR_INDEX_UNMATCH;
874 if (backref->found_dir_item && backref->filetype != filetype)
875 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
877 backref->index = index;
878 backref->filetype = filetype;
879 backref->found_dir_index = 1;
880 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
882 if (backref->found_dir_item)
883 backref->errors |= REF_ERR_DUP_DIR_ITEM;
884 if (backref->found_dir_index && backref->filetype != filetype)
885 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
887 backref->filetype = filetype;
888 backref->found_dir_item = 1;
889 } else if ((itemtype == BTRFS_INODE_REF_KEY) ||
890 (itemtype == BTRFS_INODE_EXTREF_KEY)) {
891 if (backref->found_inode_ref)
892 backref->errors |= REF_ERR_DUP_INODE_REF;
893 if (backref->found_dir_index && backref->index != index)
894 backref->errors |= REF_ERR_INDEX_UNMATCH;
896 backref->index = index;
898 backref->ref_type = itemtype;
899 backref->found_inode_ref = 1;
904 maybe_free_inode_rec(inode_cache, rec);
908 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
909 struct cache_tree *dst_cache)
911 struct inode_backref *backref;
916 list_for_each_entry(backref, &src->backrefs, list) {
917 if (backref->found_dir_index) {
918 add_inode_backref(dst_cache, dst->ino, backref->dir,
919 backref->index, backref->name,
920 backref->namelen, backref->filetype,
921 BTRFS_DIR_INDEX_KEY, backref->errors);
923 if (backref->found_dir_item) {
925 add_inode_backref(dst_cache, dst->ino,
926 backref->dir, 0, backref->name,
927 backref->namelen, backref->filetype,
928 BTRFS_DIR_ITEM_KEY, backref->errors);
930 if (backref->found_inode_ref) {
931 add_inode_backref(dst_cache, dst->ino,
932 backref->dir, backref->index,
933 backref->name, backref->namelen, 0,
934 backref->ref_type, backref->errors);
938 if (src->found_dir_item)
939 dst->found_dir_item = 1;
940 if (src->found_file_extent)
941 dst->found_file_extent = 1;
942 if (src->found_csum_item)
943 dst->found_csum_item = 1;
944 if (src->some_csum_missing)
945 dst->some_csum_missing = 1;
946 if (first_extent_gap(&dst->holes) > first_extent_gap(&src->holes)) {
947 ret = copy_file_extent_holes(&dst->holes, &src->holes);
952 BUG_ON(src->found_link < dir_count);
953 dst->found_link += src->found_link - dir_count;
954 dst->found_size += src->found_size;
955 if (src->extent_start != (u64)-1) {
956 if (dst->extent_start == (u64)-1) {
957 dst->extent_start = src->extent_start;
958 dst->extent_end = src->extent_end;
960 if (dst->extent_end > src->extent_start)
961 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
962 else if (dst->extent_end < src->extent_start) {
963 ret = add_file_extent_hole(&dst->holes,
965 src->extent_start - dst->extent_end);
967 if (dst->extent_end < src->extent_end)
968 dst->extent_end = src->extent_end;
972 dst->errors |= src->errors;
973 if (src->found_inode_item) {
974 if (!dst->found_inode_item) {
975 dst->nlink = src->nlink;
976 dst->isize = src->isize;
977 dst->nbytes = src->nbytes;
978 dst->imode = src->imode;
979 dst->nodatasum = src->nodatasum;
980 dst->found_inode_item = 1;
982 dst->errors |= I_ERR_DUP_INODE_ITEM;
990 static int splice_shared_node(struct shared_node *src_node,
991 struct shared_node *dst_node)
993 struct cache_extent *cache;
994 struct ptr_node *node, *ins;
995 struct cache_tree *src, *dst;
996 struct inode_record *rec, *conflict;
1001 if (--src_node->refs == 0)
1003 if (src_node->current)
1004 current_ino = src_node->current->ino;
1006 src = &src_node->root_cache;
1007 dst = &dst_node->root_cache;
1009 cache = search_cache_extent(src, 0);
1011 node = container_of(cache, struct ptr_node, cache);
1013 cache = next_cache_extent(cache);
1016 remove_cache_extent(src, &node->cache);
1019 ins = malloc(sizeof(*ins));
1021 ins->cache.start = node->cache.start;
1022 ins->cache.size = node->cache.size;
1026 ret = insert_cache_extent(dst, &ins->cache);
1027 if (ret == -EEXIST) {
1028 conflict = get_inode_rec(dst, rec->ino, 1);
1029 BUG_ON(IS_ERR(conflict));
1030 merge_inode_recs(rec, conflict, dst);
1032 conflict->checked = 1;
1033 if (dst_node->current == conflict)
1034 dst_node->current = NULL;
1036 maybe_free_inode_rec(dst, conflict);
1037 free_inode_rec(rec);
1044 if (src == &src_node->root_cache) {
1045 src = &src_node->inode_cache;
1046 dst = &dst_node->inode_cache;
1050 if (current_ino > 0 && (!dst_node->current ||
1051 current_ino > dst_node->current->ino)) {
1052 if (dst_node->current) {
1053 dst_node->current->checked = 1;
1054 maybe_free_inode_rec(dst, dst_node->current);
1056 dst_node->current = get_inode_rec(dst, current_ino, 1);
1057 BUG_ON(IS_ERR(dst_node->current));
1062 static void free_inode_ptr(struct cache_extent *cache)
1064 struct ptr_node *node;
1065 struct inode_record *rec;
1067 node = container_of(cache, struct ptr_node, cache);
1069 free_inode_rec(rec);
1073 FREE_EXTENT_CACHE_BASED_TREE(inode_recs, free_inode_ptr);
1075 static struct shared_node *find_shared_node(struct cache_tree *shared,
1078 struct cache_extent *cache;
1079 struct shared_node *node;
1081 cache = lookup_cache_extent(shared, bytenr, 1);
1083 node = container_of(cache, struct shared_node, cache);
1089 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
1092 struct shared_node *node;
1094 node = calloc(1, sizeof(*node));
1097 node->cache.start = bytenr;
1098 node->cache.size = 1;
1099 cache_tree_init(&node->root_cache);
1100 cache_tree_init(&node->inode_cache);
1103 ret = insert_cache_extent(shared, &node->cache);
1108 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
1109 struct walk_control *wc, int level)
1111 struct shared_node *node;
1112 struct shared_node *dest;
1115 if (level == wc->active_node)
1118 BUG_ON(wc->active_node <= level);
1119 node = find_shared_node(&wc->shared, bytenr);
1121 ret = add_shared_node(&wc->shared, bytenr, refs);
1123 node = find_shared_node(&wc->shared, bytenr);
1124 wc->nodes[level] = node;
1125 wc->active_node = level;
1129 if (wc->root_level == wc->active_node &&
1130 btrfs_root_refs(&root->root_item) == 0) {
1131 if (--node->refs == 0) {
1132 free_inode_recs_tree(&node->root_cache);
1133 free_inode_recs_tree(&node->inode_cache);
1134 remove_cache_extent(&wc->shared, &node->cache);
1140 dest = wc->nodes[wc->active_node];
1141 splice_shared_node(node, dest);
1142 if (node->refs == 0) {
1143 remove_cache_extent(&wc->shared, &node->cache);
1149 static int leave_shared_node(struct btrfs_root *root,
1150 struct walk_control *wc, int level)
1152 struct shared_node *node;
1153 struct shared_node *dest;
1156 if (level == wc->root_level)
1159 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
1163 BUG_ON(i >= BTRFS_MAX_LEVEL);
1165 node = wc->nodes[wc->active_node];
1166 wc->nodes[wc->active_node] = NULL;
1167 wc->active_node = i;
1169 dest = wc->nodes[wc->active_node];
1170 if (wc->active_node < wc->root_level ||
1171 btrfs_root_refs(&root->root_item) > 0) {
1172 BUG_ON(node->refs <= 1);
1173 splice_shared_node(node, dest);
1175 BUG_ON(node->refs < 2);
1184 * 1 - if the root with id child_root_id is a child of root parent_root_id
1185 * 0 - if the root child_root_id isn't a child of the root parent_root_id but
1186 * has other root(s) as parent(s)
1187 * 2 - if the root child_root_id doesn't have any parent roots
1189 static int is_child_root(struct btrfs_root *root, u64 parent_root_id,
1192 struct btrfs_path path;
1193 struct btrfs_key key;
1194 struct extent_buffer *leaf;
1198 btrfs_init_path(&path);
1200 key.objectid = parent_root_id;
1201 key.type = BTRFS_ROOT_REF_KEY;
1202 key.offset = child_root_id;
1203 ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
1207 btrfs_release_path(&path);
1211 key.objectid = child_root_id;
1212 key.type = BTRFS_ROOT_BACKREF_KEY;
1214 ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
1220 leaf = path.nodes[0];
1221 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1222 ret = btrfs_next_leaf(root->fs_info->tree_root, &path);
1225 leaf = path.nodes[0];
1228 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1229 if (key.objectid != child_root_id ||
1230 key.type != BTRFS_ROOT_BACKREF_KEY)
1235 if (key.offset == parent_root_id) {
1236 btrfs_release_path(&path);
1243 btrfs_release_path(&path);
1246 return has_parent ? 0 : 2;
1249 static int process_dir_item(struct extent_buffer *eb,
1250 int slot, struct btrfs_key *key,
1251 struct shared_node *active_node)
1261 struct btrfs_dir_item *di;
1262 struct inode_record *rec;
1263 struct cache_tree *root_cache;
1264 struct cache_tree *inode_cache;
1265 struct btrfs_key location;
1266 char namebuf[BTRFS_NAME_LEN];
1268 root_cache = &active_node->root_cache;
1269 inode_cache = &active_node->inode_cache;
1270 rec = active_node->current;
1271 rec->found_dir_item = 1;
1273 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
1274 total = btrfs_item_size_nr(eb, slot);
1275 while (cur < total) {
1277 btrfs_dir_item_key_to_cpu(eb, di, &location);
1278 name_len = btrfs_dir_name_len(eb, di);
1279 data_len = btrfs_dir_data_len(eb, di);
1280 filetype = btrfs_dir_type(eb, di);
1282 rec->found_size += name_len;
1283 if (cur + sizeof(*di) + name_len > total ||
1284 name_len > BTRFS_NAME_LEN) {
1285 error = REF_ERR_NAME_TOO_LONG;
1287 if (cur + sizeof(*di) > total)
1289 len = min_t(u32, total - cur - sizeof(*di),
1296 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
1298 if (key->type == BTRFS_DIR_ITEM_KEY &&
1299 key->offset != btrfs_name_hash(namebuf, len)) {
1300 rec->errors |= I_ERR_ODD_DIR_ITEM;
1301 error("DIR_ITEM[%llu %llu] name %s namelen %u filetype %u mismatch with its hash, wanted %llu have %llu",
1302 key->objectid, key->offset, namebuf, len, filetype,
1303 key->offset, btrfs_name_hash(namebuf, len));
1306 if (location.type == BTRFS_INODE_ITEM_KEY) {
1307 add_inode_backref(inode_cache, location.objectid,
1308 key->objectid, key->offset, namebuf,
1309 len, filetype, key->type, error);
1310 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
1311 add_inode_backref(root_cache, location.objectid,
1312 key->objectid, key->offset,
1313 namebuf, len, filetype,
1317 "unknown location type %d in DIR_ITEM[%llu %llu]\n",
1318 location.type, key->objectid, key->offset);
1319 add_inode_backref(inode_cache, BTRFS_MULTIPLE_OBJECTIDS,
1320 key->objectid, key->offset, namebuf,
1321 len, filetype, key->type, error);
1324 len = sizeof(*di) + name_len + data_len;
1325 di = (struct btrfs_dir_item *)((char *)di + len);
1328 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
1329 rec->errors |= I_ERR_DUP_DIR_INDEX;
1334 static int process_inode_ref(struct extent_buffer *eb,
1335 int slot, struct btrfs_key *key,
1336 struct shared_node *active_node)
1344 struct cache_tree *inode_cache;
1345 struct btrfs_inode_ref *ref;
1346 char namebuf[BTRFS_NAME_LEN];
1348 inode_cache = &active_node->inode_cache;
1350 ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1351 total = btrfs_item_size_nr(eb, slot);
1352 while (cur < total) {
1353 name_len = btrfs_inode_ref_name_len(eb, ref);
1354 index = btrfs_inode_ref_index(eb, ref);
1356 /* inode_ref + namelen should not cross item boundary */
1357 if (cur + sizeof(*ref) + name_len > total ||
1358 name_len > BTRFS_NAME_LEN) {
1359 if (total < cur + sizeof(*ref))
1362 /* Still try to read out the remaining part */
1363 len = min_t(u32, total - cur - sizeof(*ref),
1365 error = REF_ERR_NAME_TOO_LONG;
1371 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1372 add_inode_backref(inode_cache, key->objectid, key->offset,
1373 index, namebuf, len, 0, key->type, error);
1375 len = sizeof(*ref) + name_len;
1376 ref = (struct btrfs_inode_ref *)((char *)ref + len);
1382 static int process_inode_extref(struct extent_buffer *eb,
1383 int slot, struct btrfs_key *key,
1384 struct shared_node *active_node)
1393 struct cache_tree *inode_cache;
1394 struct btrfs_inode_extref *extref;
1395 char namebuf[BTRFS_NAME_LEN];
1397 inode_cache = &active_node->inode_cache;
1399 extref = btrfs_item_ptr(eb, slot, struct btrfs_inode_extref);
1400 total = btrfs_item_size_nr(eb, slot);
1401 while (cur < total) {
1402 name_len = btrfs_inode_extref_name_len(eb, extref);
1403 index = btrfs_inode_extref_index(eb, extref);
1404 parent = btrfs_inode_extref_parent(eb, extref);
1405 if (name_len <= BTRFS_NAME_LEN) {
1409 len = BTRFS_NAME_LEN;
1410 error = REF_ERR_NAME_TOO_LONG;
1412 read_extent_buffer(eb, namebuf,
1413 (unsigned long)(extref + 1), len);
1414 add_inode_backref(inode_cache, key->objectid, parent,
1415 index, namebuf, len, 0, key->type, error);
1417 len = sizeof(*extref) + name_len;
1418 extref = (struct btrfs_inode_extref *)((char *)extref + len);
1425 static int process_file_extent(struct btrfs_root *root,
1426 struct extent_buffer *eb,
1427 int slot, struct btrfs_key *key,
1428 struct shared_node *active_node)
1430 struct inode_record *rec;
1431 struct btrfs_file_extent_item *fi;
1433 u64 disk_bytenr = 0;
1434 u64 extent_offset = 0;
1435 u64 mask = root->fs_info->sectorsize - 1;
1439 rec = active_node->current;
1440 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
1441 rec->found_file_extent = 1;
1443 if (rec->extent_start == (u64)-1) {
1444 rec->extent_start = key->offset;
1445 rec->extent_end = key->offset;
1448 if (rec->extent_end > key->offset)
1449 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
1450 else if (rec->extent_end < key->offset) {
1451 ret = add_file_extent_hole(&rec->holes, rec->extent_end,
1452 key->offset - rec->extent_end);
1457 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
1458 extent_type = btrfs_file_extent_type(eb, fi);
1460 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1461 num_bytes = btrfs_file_extent_inline_len(eb, slot, fi);
1463 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1464 rec->found_size += num_bytes;
1465 num_bytes = (num_bytes + mask) & ~mask;
1466 } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
1467 extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1468 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1469 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
1470 extent_offset = btrfs_file_extent_offset(eb, fi);
1471 if (num_bytes == 0 || (num_bytes & mask))
1472 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1473 if (num_bytes + extent_offset >
1474 btrfs_file_extent_ram_bytes(eb, fi))
1475 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1476 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
1477 (btrfs_file_extent_compression(eb, fi) ||
1478 btrfs_file_extent_encryption(eb, fi) ||
1479 btrfs_file_extent_other_encoding(eb, fi)))
1480 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1481 if (disk_bytenr > 0)
1482 rec->found_size += num_bytes;
1484 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1486 rec->extent_end = key->offset + num_bytes;
1489 * The data reloc tree will copy full extents into its inode and then
1490 * copy the corresponding csums. Because the extent it copied could be
1491 * a preallocated extent that hasn't been written to yet there may be no
1492 * csums to copy, ergo we won't have csums for our file extent. This is
1493 * ok so just don't bother checking csums if the inode belongs to the
1496 if (disk_bytenr > 0 &&
1497 btrfs_header_owner(eb) != BTRFS_DATA_RELOC_TREE_OBJECTID) {
1499 if (btrfs_file_extent_compression(eb, fi))
1500 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
1502 disk_bytenr += extent_offset;
1504 ret = count_csum_range(root->fs_info, disk_bytenr, num_bytes,
1508 if (extent_type == BTRFS_FILE_EXTENT_REG) {
1510 rec->found_csum_item = 1;
1511 if (found < num_bytes)
1512 rec->some_csum_missing = 1;
1513 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1515 rec->errors |= I_ERR_ODD_CSUM_ITEM;
1521 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
1522 struct walk_control *wc)
1524 struct btrfs_key key;
1528 struct cache_tree *inode_cache;
1529 struct shared_node *active_node;
1531 if (wc->root_level == wc->active_node &&
1532 btrfs_root_refs(&root->root_item) == 0)
1535 active_node = wc->nodes[wc->active_node];
1536 inode_cache = &active_node->inode_cache;
1537 nritems = btrfs_header_nritems(eb);
1538 for (i = 0; i < nritems; i++) {
1539 btrfs_item_key_to_cpu(eb, &key, i);
1541 if (key.objectid == BTRFS_FREE_SPACE_OBJECTID)
1543 if (key.type == BTRFS_ORPHAN_ITEM_KEY)
1546 if (active_node->current == NULL ||
1547 active_node->current->ino < key.objectid) {
1548 if (active_node->current) {
1549 active_node->current->checked = 1;
1550 maybe_free_inode_rec(inode_cache,
1551 active_node->current);
1553 active_node->current = get_inode_rec(inode_cache,
1555 BUG_ON(IS_ERR(active_node->current));
1558 case BTRFS_DIR_ITEM_KEY:
1559 case BTRFS_DIR_INDEX_KEY:
1560 ret = process_dir_item(eb, i, &key, active_node);
1562 case BTRFS_INODE_REF_KEY:
1563 ret = process_inode_ref(eb, i, &key, active_node);
1565 case BTRFS_INODE_EXTREF_KEY:
1566 ret = process_inode_extref(eb, i, &key, active_node);
1568 case BTRFS_INODE_ITEM_KEY:
1569 ret = process_inode_item(eb, i, &key, active_node);
1571 case BTRFS_EXTENT_DATA_KEY:
1572 ret = process_file_extent(root, eb, i, &key,
1582 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1583 struct walk_control *wc, int *level,
1584 struct node_refs *nrefs)
1586 enum btrfs_tree_block_status status;
1589 struct btrfs_fs_info *fs_info = root->fs_info;
1590 struct extent_buffer *next;
1591 struct extent_buffer *cur;
1595 WARN_ON(*level < 0);
1596 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1598 if (path->nodes[*level]->start == nrefs->bytenr[*level]) {
1599 refs = nrefs->refs[*level];
1602 ret = btrfs_lookup_extent_info(NULL, root,
1603 path->nodes[*level]->start,
1604 *level, 1, &refs, NULL);
1609 nrefs->bytenr[*level] = path->nodes[*level]->start;
1610 nrefs->refs[*level] = refs;
1614 ret = enter_shared_node(root, path->nodes[*level]->start,
1622 while (*level >= 0) {
1623 WARN_ON(*level < 0);
1624 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1625 cur = path->nodes[*level];
1627 if (btrfs_header_level(cur) != *level)
1630 if (path->slots[*level] >= btrfs_header_nritems(cur))
1633 ret = process_one_leaf(root, cur, wc);
1638 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1639 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1641 if (bytenr == nrefs->bytenr[*level - 1]) {
1642 refs = nrefs->refs[*level - 1];
1644 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
1645 *level - 1, 1, &refs, NULL);
1649 nrefs->bytenr[*level - 1] = bytenr;
1650 nrefs->refs[*level - 1] = refs;
1655 ret = enter_shared_node(root, bytenr, refs,
1658 path->slots[*level]++;
1663 next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize);
1664 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1665 free_extent_buffer(next);
1666 reada_walk_down(root, cur, path->slots[*level]);
1667 next = read_tree_block(root->fs_info, bytenr, ptr_gen);
1668 if (!extent_buffer_uptodate(next)) {
1669 struct btrfs_key node_key;
1671 btrfs_node_key_to_cpu(path->nodes[*level],
1673 path->slots[*level]);
1674 btrfs_add_corrupt_extent_record(root->fs_info,
1676 path->nodes[*level]->start,
1677 root->fs_info->nodesize,
1684 ret = check_child_node(cur, path->slots[*level], next);
1686 free_extent_buffer(next);
1691 if (btrfs_is_leaf(next))
1692 status = btrfs_check_leaf(root, NULL, next);
1694 status = btrfs_check_node(root, NULL, next);
1695 if (status != BTRFS_TREE_BLOCK_CLEAN) {
1696 free_extent_buffer(next);
1701 *level = *level - 1;
1702 free_extent_buffer(path->nodes[*level]);
1703 path->nodes[*level] = next;
1704 path->slots[*level] = 0;
1707 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1711 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1712 struct walk_control *wc, int *level)
1715 struct extent_buffer *leaf;
1717 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1718 leaf = path->nodes[i];
1719 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1724 free_extent_buffer(path->nodes[*level]);
1725 path->nodes[*level] = NULL;
1726 BUG_ON(*level > wc->active_node);
1727 if (*level == wc->active_node)
1728 leave_shared_node(root, wc, *level);
1734 static int check_root_dir(struct inode_record *rec)
1736 struct inode_backref *backref;
1739 if (!rec->found_inode_item || rec->errors)
1741 if (rec->nlink != 1 || rec->found_link != 0)
1743 if (list_empty(&rec->backrefs))
1745 backref = to_inode_backref(rec->backrefs.next);
1746 if (!backref->found_inode_ref)
1748 if (backref->index != 0 || backref->namelen != 2 ||
1749 memcmp(backref->name, "..", 2))
1751 if (backref->found_dir_index || backref->found_dir_item)
1758 static int repair_inode_isize(struct btrfs_trans_handle *trans,
1759 struct btrfs_root *root, struct btrfs_path *path,
1760 struct inode_record *rec)
1762 struct btrfs_inode_item *ei;
1763 struct btrfs_key key;
1766 key.objectid = rec->ino;
1767 key.type = BTRFS_INODE_ITEM_KEY;
1768 key.offset = (u64)-1;
1770 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1774 if (!path->slots[0]) {
1781 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1782 if (key.objectid != rec->ino) {
1787 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1788 struct btrfs_inode_item);
1789 btrfs_set_inode_size(path->nodes[0], ei, rec->found_size);
1790 btrfs_mark_buffer_dirty(path->nodes[0]);
1791 rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
1792 printf("reset isize for dir %llu root %llu\n", rec->ino,
1793 root->root_key.objectid);
1795 btrfs_release_path(path);
1799 static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
1800 struct btrfs_root *root,
1801 struct btrfs_path *path,
1802 struct inode_record *rec)
1806 ret = btrfs_add_orphan_item(trans, root, path, rec->ino);
1807 btrfs_release_path(path);
1809 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1813 static int repair_inode_nbytes(struct btrfs_trans_handle *trans,
1814 struct btrfs_root *root,
1815 struct btrfs_path *path,
1816 struct inode_record *rec)
1818 struct btrfs_inode_item *ei;
1819 struct btrfs_key key;
1822 key.objectid = rec->ino;
1823 key.type = BTRFS_INODE_ITEM_KEY;
1826 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1833 /* Since ret == 0, no need to check anything */
1834 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1835 struct btrfs_inode_item);
1836 btrfs_set_inode_nbytes(path->nodes[0], ei, rec->found_size);
1837 btrfs_mark_buffer_dirty(path->nodes[0]);
1838 rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
1839 printf("reset nbytes for ino %llu root %llu\n",
1840 rec->ino, root->root_key.objectid);
1842 btrfs_release_path(path);
1846 static int add_missing_dir_index(struct btrfs_root *root,
1847 struct cache_tree *inode_cache,
1848 struct inode_record *rec,
1849 struct inode_backref *backref)
1851 struct btrfs_path path;
1852 struct btrfs_trans_handle *trans;
1853 struct btrfs_dir_item *dir_item;
1854 struct extent_buffer *leaf;
1855 struct btrfs_key key;
1856 struct btrfs_disk_key disk_key;
1857 struct inode_record *dir_rec;
1858 unsigned long name_ptr;
1859 u32 data_size = sizeof(*dir_item) + backref->namelen;
1862 trans = btrfs_start_transaction(root, 1);
1864 return PTR_ERR(trans);
1866 fprintf(stderr, "repairing missing dir index item for inode %llu\n",
1867 (unsigned long long)rec->ino);
1869 btrfs_init_path(&path);
1870 key.objectid = backref->dir;
1871 key.type = BTRFS_DIR_INDEX_KEY;
1872 key.offset = backref->index;
1873 ret = btrfs_insert_empty_item(trans, root, &path, &key, data_size);
1876 leaf = path.nodes[0];
1877 dir_item = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_dir_item);
1879 disk_key.objectid = cpu_to_le64(rec->ino);
1880 disk_key.type = BTRFS_INODE_ITEM_KEY;
1881 disk_key.offset = 0;
1883 btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
1884 btrfs_set_dir_type(leaf, dir_item, imode_to_type(rec->imode));
1885 btrfs_set_dir_data_len(leaf, dir_item, 0);
1886 btrfs_set_dir_name_len(leaf, dir_item, backref->namelen);
1887 name_ptr = (unsigned long)(dir_item + 1);
1888 write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen);
1889 btrfs_mark_buffer_dirty(leaf);
1890 btrfs_release_path(&path);
1891 btrfs_commit_transaction(trans, root);
1893 backref->found_dir_index = 1;
1894 dir_rec = get_inode_rec(inode_cache, backref->dir, 0);
1895 BUG_ON(IS_ERR(dir_rec));
1898 dir_rec->found_size += backref->namelen;
1899 if (dir_rec->found_size == dir_rec->isize &&
1900 (dir_rec->errors & I_ERR_DIR_ISIZE_WRONG))
1901 dir_rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
1902 if (dir_rec->found_size != dir_rec->isize)
1903 dir_rec->errors |= I_ERR_DIR_ISIZE_WRONG;
1908 static int delete_dir_index(struct btrfs_root *root,
1909 struct inode_backref *backref)
1911 struct btrfs_trans_handle *trans;
1912 struct btrfs_dir_item *di;
1913 struct btrfs_path path;
1916 trans = btrfs_start_transaction(root, 1);
1918 return PTR_ERR(trans);
1920 fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
1921 (unsigned long long)backref->dir,
1922 BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index,
1923 (unsigned long long)root->objectid);
1925 btrfs_init_path(&path);
1926 di = btrfs_lookup_dir_index(trans, root, &path, backref->dir,
1927 backref->name, backref->namelen,
1928 backref->index, -1);
1931 btrfs_release_path(&path);
1932 btrfs_commit_transaction(trans, root);
1939 ret = btrfs_del_item(trans, root, &path);
1941 ret = btrfs_delete_one_dir_name(trans, root, &path, di);
1943 btrfs_release_path(&path);
1944 btrfs_commit_transaction(trans, root);
1948 static int create_inode_item(struct btrfs_root *root,
1949 struct inode_record *rec, int root_dir)
1951 struct btrfs_trans_handle *trans;
1957 trans = btrfs_start_transaction(root, 1);
1958 if (IS_ERR(trans)) {
1959 ret = PTR_ERR(trans);
1963 nlink = root_dir ? 1 : rec->found_link;
1964 if (rec->found_dir_item) {
1965 if (rec->found_file_extent)
1966 fprintf(stderr, "root %llu inode %llu has both a dir "
1967 "item and extents, unsure if it is a dir or a "
1968 "regular file so setting it as a directory\n",
1969 (unsigned long long)root->objectid,
1970 (unsigned long long)rec->ino);
1971 mode = S_IFDIR | 0755;
1972 size = rec->found_size;
1973 } else if (!rec->found_dir_item) {
1974 size = rec->extent_end;
1975 mode = S_IFREG | 0755;
1978 ret = insert_inode_item(trans, root, rec->ino, size, rec->nbytes,
1980 btrfs_commit_transaction(trans, root);
1984 static int repair_inode_backrefs(struct btrfs_root *root,
1985 struct inode_record *rec,
1986 struct cache_tree *inode_cache,
1989 struct inode_backref *tmp, *backref;
1990 u64 root_dirid = btrfs_root_dirid(&root->root_item);
1994 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
1995 if (!delete && rec->ino == root_dirid) {
1996 if (!rec->found_inode_item) {
1997 ret = create_inode_item(root, rec, 1);
2004 /* Index 0 for root dir's are special, don't mess with it */
2005 if (rec->ino == root_dirid && backref->index == 0)
2009 ((backref->found_dir_index && !backref->found_inode_ref) ||
2010 (backref->found_dir_index && backref->found_inode_ref &&
2011 (backref->errors & REF_ERR_INDEX_UNMATCH)))) {
2012 ret = delete_dir_index(root, backref);
2016 list_del(&backref->list);
2021 if (!delete && !backref->found_dir_index &&
2022 backref->found_dir_item && backref->found_inode_ref) {
2023 ret = add_missing_dir_index(root, inode_cache, rec,
2028 if (backref->found_dir_item &&
2029 backref->found_dir_index) {
2030 if (!backref->errors &&
2031 backref->found_inode_ref) {
2032 list_del(&backref->list);
2039 if (!delete && (!backref->found_dir_index &&
2040 !backref->found_dir_item &&
2041 backref->found_inode_ref)) {
2042 struct btrfs_trans_handle *trans;
2043 struct btrfs_key location;
2045 ret = check_dir_conflict(root, backref->name,
2051 * let nlink fixing routine to handle it,
2052 * which can do it better.
2057 location.objectid = rec->ino;
2058 location.type = BTRFS_INODE_ITEM_KEY;
2059 location.offset = 0;
2061 trans = btrfs_start_transaction(root, 1);
2062 if (IS_ERR(trans)) {
2063 ret = PTR_ERR(trans);
2066 fprintf(stderr, "adding missing dir index/item pair "
2068 (unsigned long long)rec->ino);
2069 ret = btrfs_insert_dir_item(trans, root, backref->name,
2071 backref->dir, &location,
2072 imode_to_type(rec->imode),
2075 btrfs_commit_transaction(trans, root);
2079 if (!delete && (backref->found_inode_ref &&
2080 backref->found_dir_index &&
2081 backref->found_dir_item &&
2082 !(backref->errors & REF_ERR_INDEX_UNMATCH) &&
2083 !rec->found_inode_item)) {
2084 ret = create_inode_item(root, rec, 0);
2091 return ret ? ret : repaired;
2095 * To determine the file type for nlink/inode_item repair
2097 * Return 0 if file type is found and BTRFS_FT_* is stored into type.
2098 * Return -ENOENT if file type is not found.
2100 static int find_file_type(struct inode_record *rec, u8 *type)
2102 struct inode_backref *backref;
2104 /* For inode item recovered case */
2105 if (rec->found_inode_item) {
2106 *type = imode_to_type(rec->imode);
2110 list_for_each_entry(backref, &rec->backrefs, list) {
2111 if (backref->found_dir_index || backref->found_dir_item) {
2112 *type = backref->filetype;
2120 * To determine the file name for nlink repair
2122 * Return 0 if file name is found, set name and namelen.
2123 * Return -ENOENT if file name is not found.
2125 static int find_file_name(struct inode_record *rec,
2126 char *name, int *namelen)
2128 struct inode_backref *backref;
2130 list_for_each_entry(backref, &rec->backrefs, list) {
2131 if (backref->found_dir_index || backref->found_dir_item ||
2132 backref->found_inode_ref) {
2133 memcpy(name, backref->name, backref->namelen);
2134 *namelen = backref->namelen;
2141 /* Reset the nlink of the inode to the correct one */
2142 static int reset_nlink(struct btrfs_trans_handle *trans,
2143 struct btrfs_root *root,
2144 struct btrfs_path *path,
2145 struct inode_record *rec)
2147 struct inode_backref *backref;
2148 struct inode_backref *tmp;
2149 struct btrfs_key key;
2150 struct btrfs_inode_item *inode_item;
2153 /* We don't believe this either, reset it and iterate backref */
2154 rec->found_link = 0;
2156 /* Remove all backref including the valid ones */
2157 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
2158 ret = btrfs_unlink(trans, root, rec->ino, backref->dir,
2159 backref->index, backref->name,
2160 backref->namelen, 0);
2164 /* remove invalid backref, so it won't be added back */
2165 if (!(backref->found_dir_index &&
2166 backref->found_dir_item &&
2167 backref->found_inode_ref)) {
2168 list_del(&backref->list);
2175 /* Set nlink to 0 */
2176 key.objectid = rec->ino;
2177 key.type = BTRFS_INODE_ITEM_KEY;
2179 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2186 inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2187 struct btrfs_inode_item);
2188 btrfs_set_inode_nlink(path->nodes[0], inode_item, 0);
2189 btrfs_mark_buffer_dirty(path->nodes[0]);
2190 btrfs_release_path(path);
2193 * Add back valid inode_ref/dir_item/dir_index,
2194 * add_link() will handle the nlink inc, so new nlink must be correct
2196 list_for_each_entry(backref, &rec->backrefs, list) {
2197 ret = btrfs_add_link(trans, root, rec->ino, backref->dir,
2198 backref->name, backref->namelen,
2199 backref->filetype, &backref->index, 1, 0);
2204 btrfs_release_path(path);
2208 static int repair_inode_nlinks(struct btrfs_trans_handle *trans,
2209 struct btrfs_root *root,
2210 struct btrfs_path *path,
2211 struct inode_record *rec)
2213 char namebuf[BTRFS_NAME_LEN] = {0};
2216 int name_recovered = 0;
2217 int type_recovered = 0;
2221 * Get file name and type first before these invalid inode ref
2222 * are deleted by remove_all_invalid_backref()
2224 name_recovered = !find_file_name(rec, namebuf, &namelen);
2225 type_recovered = !find_file_type(rec, &type);
2227 if (!name_recovered) {
2228 printf("Can't get file name for inode %llu, using '%llu' as fallback\n",
2229 rec->ino, rec->ino);
2230 namelen = count_digits(rec->ino);
2231 sprintf(namebuf, "%llu", rec->ino);
2234 if (!type_recovered) {
2235 printf("Can't get file type for inode %llu, using FILE as fallback\n",
2237 type = BTRFS_FT_REG_FILE;
2241 ret = reset_nlink(trans, root, path, rec);
2244 "Failed to reset nlink for inode %llu: %s\n",
2245 rec->ino, strerror(-ret));
2249 if (rec->found_link == 0) {
2250 ret = link_inode_to_lostfound(trans, root, path, rec->ino,
2251 namebuf, namelen, type,
2252 (u64 *)&rec->found_link);
2256 printf("Fixed the nlink of inode %llu\n", rec->ino);
2259 * Clear the flag anyway, or we will loop forever for the same inode
2260 * as it will not be removed from the bad inode list and the dead loop
2263 rec->errors &= ~I_ERR_LINK_COUNT_WRONG;
2264 btrfs_release_path(path);
2269 * Check if there is any normal(reg or prealloc) file extent for given
2271 * This is used to determine the file type when neither its dir_index/item or
2272 * inode_item exists.
2274 * This will *NOT* report error, if any error happens, just consider it does
2275 * not have any normal file extent.
2277 static int find_normal_file_extent(struct btrfs_root *root, u64 ino)
2279 struct btrfs_path path;
2280 struct btrfs_key key;
2281 struct btrfs_key found_key;
2282 struct btrfs_file_extent_item *fi;
2286 btrfs_init_path(&path);
2288 key.type = BTRFS_EXTENT_DATA_KEY;
2291 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
2296 if (ret && path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
2297 ret = btrfs_next_leaf(root, &path);
2304 btrfs_item_key_to_cpu(path.nodes[0], &found_key,
2306 if (found_key.objectid != ino ||
2307 found_key.type != BTRFS_EXTENT_DATA_KEY)
2309 fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
2310 struct btrfs_file_extent_item);
2311 type = btrfs_file_extent_type(path.nodes[0], fi);
2312 if (type != BTRFS_FILE_EXTENT_INLINE) {
2318 btrfs_release_path(&path);
2322 static u32 btrfs_type_to_imode(u8 type)
2324 static u32 imode_by_btrfs_type[] = {
2325 [BTRFS_FT_REG_FILE] = S_IFREG,
2326 [BTRFS_FT_DIR] = S_IFDIR,
2327 [BTRFS_FT_CHRDEV] = S_IFCHR,
2328 [BTRFS_FT_BLKDEV] = S_IFBLK,
2329 [BTRFS_FT_FIFO] = S_IFIFO,
2330 [BTRFS_FT_SOCK] = S_IFSOCK,
2331 [BTRFS_FT_SYMLINK] = S_IFLNK,
2334 return imode_by_btrfs_type[(type)];
2337 static int repair_inode_no_item(struct btrfs_trans_handle *trans,
2338 struct btrfs_root *root,
2339 struct btrfs_path *path,
2340 struct inode_record *rec)
2344 int type_recovered = 0;
2347 printf("Trying to rebuild inode:%llu\n", rec->ino);
2349 type_recovered = !find_file_type(rec, &filetype);
2352 * Try to determine inode type if type not found.
2354 * For found regular file extent, it must be FILE.
2355 * For found dir_item/index, it must be DIR.
2357 * For undetermined one, use FILE as fallback.
2360 * 1. If found backref(inode_index/item is already handled) to it,
2362 * Need new inode-inode ref structure to allow search for that.
2364 if (!type_recovered) {
2365 if (rec->found_file_extent &&
2366 find_normal_file_extent(root, rec->ino)) {
2368 filetype = BTRFS_FT_REG_FILE;
2369 } else if (rec->found_dir_item) {
2371 filetype = BTRFS_FT_DIR;
2372 } else if (!list_empty(&rec->orphan_extents)) {
2374 filetype = BTRFS_FT_REG_FILE;
2376 printf("Can't determine the filetype for inode %llu, assume it is a normal file\n",
2379 filetype = BTRFS_FT_REG_FILE;
2383 ret = btrfs_new_inode(trans, root, rec->ino,
2384 mode | btrfs_type_to_imode(filetype));
2389 * Here inode rebuild is done, we only rebuild the inode item,
2390 * don't repair the nlink(like move to lost+found).
2391 * That is the job of nlink repair.
2393 * We just fill the record and return
2395 rec->found_dir_item = 1;
2396 rec->imode = mode | btrfs_type_to_imode(filetype);
2398 rec->errors &= ~I_ERR_NO_INODE_ITEM;
2399 /* Ensure the inode_nlinks repair function will be called */
2400 rec->errors |= I_ERR_LINK_COUNT_WRONG;
2405 static int repair_inode_orphan_extent(struct btrfs_trans_handle *trans,
2406 struct btrfs_root *root,
2407 struct btrfs_path *path,
2408 struct inode_record *rec)
2410 struct orphan_data_extent *orphan;
2411 struct orphan_data_extent *tmp;
2414 list_for_each_entry_safe(orphan, tmp, &rec->orphan_extents, list) {
2416 * Check for conflicting file extents
2418 * Here we don't know whether the extents is compressed or not,
2419 * so we can only assume it not compressed nor data offset,
2420 * and use its disk_len as extent length.
2422 ret = btrfs_get_extent(NULL, root, path, orphan->objectid,
2423 orphan->offset, orphan->disk_len, 0);
2424 btrfs_release_path(path);
2429 "orphan extent (%llu, %llu) conflicts, delete the orphan\n",
2430 orphan->disk_bytenr, orphan->disk_len);
2431 ret = btrfs_free_extent(trans,
2432 root->fs_info->extent_root,
2433 orphan->disk_bytenr, orphan->disk_len,
2434 0, root->objectid, orphan->objectid,
2439 ret = btrfs_insert_file_extent(trans, root, orphan->objectid,
2440 orphan->offset, orphan->disk_bytenr,
2441 orphan->disk_len, orphan->disk_len);
2445 /* Update file size info */
2446 rec->found_size += orphan->disk_len;
2447 if (rec->found_size == rec->nbytes)
2448 rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
2450 /* Update the file extent hole info too */
2451 ret = del_file_extent_hole(&rec->holes, orphan->offset,
2455 if (RB_EMPTY_ROOT(&rec->holes))
2456 rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
2458 list_del(&orphan->list);
2461 rec->errors &= ~I_ERR_FILE_EXTENT_ORPHAN;
2466 static int repair_inode_discount_extent(struct btrfs_trans_handle *trans,
2467 struct btrfs_root *root,
2468 struct btrfs_path *path,
2469 struct inode_record *rec)
2471 struct rb_node *node;
2472 struct file_extent_hole *hole;
2476 node = rb_first(&rec->holes);
2480 hole = rb_entry(node, struct file_extent_hole, node);
2481 ret = btrfs_punch_hole(trans, root, rec->ino,
2482 hole->start, hole->len);
2485 ret = del_file_extent_hole(&rec->holes, hole->start,
2489 if (RB_EMPTY_ROOT(&rec->holes))
2490 rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
2491 node = rb_first(&rec->holes);
2493 /* special case for a file losing all its file extent */
2495 ret = btrfs_punch_hole(trans, root, rec->ino, 0,
2496 round_up(rec->isize,
2497 root->fs_info->sectorsize));
2501 printf("Fixed discount file extents for inode: %llu in root: %llu\n",
2502 rec->ino, root->objectid);
2507 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
2509 struct btrfs_trans_handle *trans;
2510 struct btrfs_path path;
2513 if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG |
2514 I_ERR_NO_ORPHAN_ITEM |
2515 I_ERR_LINK_COUNT_WRONG |
2516 I_ERR_NO_INODE_ITEM |
2517 I_ERR_FILE_EXTENT_ORPHAN |
2518 I_ERR_FILE_EXTENT_DISCOUNT|
2519 I_ERR_FILE_NBYTES_WRONG)))
2523 * For nlink repair, it may create a dir and add link, so
2524 * 2 for parent(256)'s dir_index and dir_item
2525 * 2 for lost+found dir's inode_item and inode_ref
2526 * 1 for the new inode_ref of the file
2527 * 2 for lost+found dir's dir_index and dir_item for the file
2529 trans = btrfs_start_transaction(root, 7);
2531 return PTR_ERR(trans);
2533 btrfs_init_path(&path);
2534 if (rec->errors & I_ERR_NO_INODE_ITEM)
2535 ret = repair_inode_no_item(trans, root, &path, rec);
2536 if (!ret && rec->errors & I_ERR_FILE_EXTENT_ORPHAN)
2537 ret = repair_inode_orphan_extent(trans, root, &path, rec);
2538 if (!ret && rec->errors & I_ERR_FILE_EXTENT_DISCOUNT)
2539 ret = repair_inode_discount_extent(trans, root, &path, rec);
2540 if (!ret && rec->errors & I_ERR_DIR_ISIZE_WRONG)
2541 ret = repair_inode_isize(trans, root, &path, rec);
2542 if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
2543 ret = repair_inode_orphan_item(trans, root, &path, rec);
2544 if (!ret && rec->errors & I_ERR_LINK_COUNT_WRONG)
2545 ret = repair_inode_nlinks(trans, root, &path, rec);
2546 if (!ret && rec->errors & I_ERR_FILE_NBYTES_WRONG)
2547 ret = repair_inode_nbytes(trans, root, &path, rec);
2548 btrfs_commit_transaction(trans, root);
2549 btrfs_release_path(&path);
2553 static int check_inode_recs(struct btrfs_root *root,
2554 struct cache_tree *inode_cache)
2556 struct cache_extent *cache;
2557 struct ptr_node *node;
2558 struct inode_record *rec;
2559 struct inode_backref *backref;
2564 u64 root_dirid = btrfs_root_dirid(&root->root_item);
2566 if (btrfs_root_refs(&root->root_item) == 0) {
2567 if (!cache_tree_empty(inode_cache))
2568 fprintf(stderr, "warning line %d\n", __LINE__);
2573 * We need to repair backrefs first because we could change some of the
2574 * errors in the inode recs.
2576 * We also need to go through and delete invalid backrefs first and then
2577 * add the correct ones second. We do this because we may get EEXIST
2578 * when adding back the correct index because we hadn't yet deleted the
2581 * For example, if we were missing a dir index then the directories
2582 * isize would be wrong, so if we fixed the isize to what we thought it
2583 * would be and then fixed the backref we'd still have a invalid fs, so
2584 * we need to add back the dir index and then check to see if the isize
2589 if (stage == 3 && !err)
2592 cache = search_cache_extent(inode_cache, 0);
2593 while (repair && cache) {
2594 node = container_of(cache, struct ptr_node, cache);
2596 cache = next_cache_extent(cache);
2598 /* Need to free everything up and rescan */
2600 remove_cache_extent(inode_cache, &node->cache);
2602 free_inode_rec(rec);
2606 if (list_empty(&rec->backrefs))
2609 ret = repair_inode_backrefs(root, rec, inode_cache,
2623 rec = get_inode_rec(inode_cache, root_dirid, 0);
2624 BUG_ON(IS_ERR(rec));
2626 ret = check_root_dir(rec);
2628 fprintf(stderr, "root %llu root dir %llu error\n",
2629 (unsigned long long)root->root_key.objectid,
2630 (unsigned long long)root_dirid);
2631 print_inode_error(root, rec);
2636 struct btrfs_trans_handle *trans;
2638 trans = btrfs_start_transaction(root, 1);
2639 if (IS_ERR(trans)) {
2640 err = PTR_ERR(trans);
2645 "root %llu missing its root dir, recreating\n",
2646 (unsigned long long)root->objectid);
2648 ret = btrfs_make_root_dir(trans, root, root_dirid);
2651 btrfs_commit_transaction(trans, root);
2655 fprintf(stderr, "root %llu root dir %llu not found\n",
2656 (unsigned long long)root->root_key.objectid,
2657 (unsigned long long)root_dirid);
2661 cache = search_cache_extent(inode_cache, 0);
2664 node = container_of(cache, struct ptr_node, cache);
2666 remove_cache_extent(inode_cache, &node->cache);
2668 if (rec->ino == root_dirid ||
2669 rec->ino == BTRFS_ORPHAN_OBJECTID) {
2670 free_inode_rec(rec);
2674 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
2675 ret = check_orphan_item(root, rec->ino);
2677 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
2678 if (can_free_inode_rec(rec)) {
2679 free_inode_rec(rec);
2684 if (!rec->found_inode_item)
2685 rec->errors |= I_ERR_NO_INODE_ITEM;
2686 if (rec->found_link != rec->nlink)
2687 rec->errors |= I_ERR_LINK_COUNT_WRONG;
2689 ret = try_repair_inode(root, rec);
2690 if (ret == 0 && can_free_inode_rec(rec)) {
2691 free_inode_rec(rec);
2697 if (!(repair && ret == 0))
2699 print_inode_error(root, rec);
2700 list_for_each_entry(backref, &rec->backrefs, list) {
2701 if (!backref->found_dir_item)
2702 backref->errors |= REF_ERR_NO_DIR_ITEM;
2703 if (!backref->found_dir_index)
2704 backref->errors |= REF_ERR_NO_DIR_INDEX;
2705 if (!backref->found_inode_ref)
2706 backref->errors |= REF_ERR_NO_INODE_REF;
2707 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
2708 " namelen %u name %s filetype %d errors %x",
2709 (unsigned long long)backref->dir,
2710 (unsigned long long)backref->index,
2711 backref->namelen, backref->name,
2712 backref->filetype, backref->errors);
2713 print_ref_error(backref->errors);
2715 free_inode_rec(rec);
2717 return (error > 0) ? -1 : 0;
2720 static struct root_record *get_root_rec(struct cache_tree *root_cache,
2723 struct cache_extent *cache;
2724 struct root_record *rec = NULL;
2727 cache = lookup_cache_extent(root_cache, objectid, 1);
2729 rec = container_of(cache, struct root_record, cache);
2731 rec = calloc(1, sizeof(*rec));
2733 return ERR_PTR(-ENOMEM);
2734 rec->objectid = objectid;
2735 INIT_LIST_HEAD(&rec->backrefs);
2736 rec->cache.start = objectid;
2737 rec->cache.size = 1;
2739 ret = insert_cache_extent(root_cache, &rec->cache);
2741 return ERR_PTR(-EEXIST);
2746 static struct root_backref *get_root_backref(struct root_record *rec,
2747 u64 ref_root, u64 dir, u64 index,
2748 const char *name, int namelen)
2750 struct root_backref *backref;
2752 list_for_each_entry(backref, &rec->backrefs, list) {
2753 if (backref->ref_root != ref_root || backref->dir != dir ||
2754 backref->namelen != namelen)
2756 if (memcmp(name, backref->name, namelen))
2761 backref = calloc(1, sizeof(*backref) + namelen + 1);
2764 backref->ref_root = ref_root;
2766 backref->index = index;
2767 backref->namelen = namelen;
2768 memcpy(backref->name, name, namelen);
2769 backref->name[namelen] = '\0';
2770 list_add_tail(&backref->list, &rec->backrefs);
2774 static void free_root_record(struct cache_extent *cache)
2776 struct root_record *rec;
2777 struct root_backref *backref;
2779 rec = container_of(cache, struct root_record, cache);
2780 while (!list_empty(&rec->backrefs)) {
2781 backref = to_root_backref(rec->backrefs.next);
2782 list_del(&backref->list);
2789 FREE_EXTENT_CACHE_BASED_TREE(root_recs, free_root_record);
2791 static int add_root_backref(struct cache_tree *root_cache,
2792 u64 root_id, u64 ref_root, u64 dir, u64 index,
2793 const char *name, int namelen,
2794 int item_type, int errors)
2796 struct root_record *rec;
2797 struct root_backref *backref;
2799 rec = get_root_rec(root_cache, root_id);
2800 BUG_ON(IS_ERR(rec));
2801 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
2804 backref->errors |= errors;
2806 if (item_type != BTRFS_DIR_ITEM_KEY) {
2807 if (backref->found_dir_index || backref->found_back_ref ||
2808 backref->found_forward_ref) {
2809 if (backref->index != index)
2810 backref->errors |= REF_ERR_INDEX_UNMATCH;
2812 backref->index = index;
2816 if (item_type == BTRFS_DIR_ITEM_KEY) {
2817 if (backref->found_forward_ref)
2819 backref->found_dir_item = 1;
2820 } else if (item_type == BTRFS_DIR_INDEX_KEY) {
2821 backref->found_dir_index = 1;
2822 } else if (item_type == BTRFS_ROOT_REF_KEY) {
2823 if (backref->found_forward_ref)
2824 backref->errors |= REF_ERR_DUP_ROOT_REF;
2825 else if (backref->found_dir_item)
2827 backref->found_forward_ref = 1;
2828 } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
2829 if (backref->found_back_ref)
2830 backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
2831 backref->found_back_ref = 1;
2836 if (backref->found_forward_ref && backref->found_dir_item)
2837 backref->reachable = 1;
2841 static int merge_root_recs(struct btrfs_root *root,
2842 struct cache_tree *src_cache,
2843 struct cache_tree *dst_cache)
2845 struct cache_extent *cache;
2846 struct ptr_node *node;
2847 struct inode_record *rec;
2848 struct inode_backref *backref;
2851 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
2852 free_inode_recs_tree(src_cache);
2857 cache = search_cache_extent(src_cache, 0);
2860 node = container_of(cache, struct ptr_node, cache);
2862 remove_cache_extent(src_cache, &node->cache);
2865 ret = is_child_root(root, root->objectid, rec->ino);
2871 list_for_each_entry(backref, &rec->backrefs, list) {
2872 BUG_ON(backref->found_inode_ref);
2873 if (backref->found_dir_item)
2874 add_root_backref(dst_cache, rec->ino,
2875 root->root_key.objectid, backref->dir,
2876 backref->index, backref->name,
2877 backref->namelen, BTRFS_DIR_ITEM_KEY,
2879 if (backref->found_dir_index)
2880 add_root_backref(dst_cache, rec->ino,
2881 root->root_key.objectid, backref->dir,
2882 backref->index, backref->name,
2883 backref->namelen, BTRFS_DIR_INDEX_KEY,
2887 free_inode_rec(rec);
2894 static int check_root_refs(struct btrfs_root *root,
2895 struct cache_tree *root_cache)
2897 struct root_record *rec;
2898 struct root_record *ref_root;
2899 struct root_backref *backref;
2900 struct cache_extent *cache;
2906 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
2907 BUG_ON(IS_ERR(rec));
2910 /* fixme: this can not detect circular references */
2913 cache = search_cache_extent(root_cache, 0);
2917 rec = container_of(cache, struct root_record, cache);
2918 cache = next_cache_extent(cache);
2920 if (rec->found_ref == 0)
2923 list_for_each_entry(backref, &rec->backrefs, list) {
2924 if (!backref->reachable)
2927 ref_root = get_root_rec(root_cache,
2929 BUG_ON(IS_ERR(ref_root));
2930 if (ref_root->found_ref > 0)
2933 backref->reachable = 0;
2935 if (rec->found_ref == 0)
2941 cache = search_cache_extent(root_cache, 0);
2945 rec = container_of(cache, struct root_record, cache);
2946 cache = next_cache_extent(cache);
2948 if (rec->found_ref == 0 &&
2949 rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
2950 rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
2951 ret = check_orphan_item(root->fs_info->tree_root,
2957 * If we don't have a root item then we likely just have
2958 * a dir item in a snapshot for this root but no actual
2959 * ref key or anything so it's meaningless.
2961 if (!rec->found_root_item)
2964 fprintf(stderr, "fs tree %llu not referenced\n",
2965 (unsigned long long)rec->objectid);
2969 if (rec->found_ref > 0 && !rec->found_root_item)
2971 list_for_each_entry(backref, &rec->backrefs, list) {
2972 if (!backref->found_dir_item)
2973 backref->errors |= REF_ERR_NO_DIR_ITEM;
2974 if (!backref->found_dir_index)
2975 backref->errors |= REF_ERR_NO_DIR_INDEX;
2976 if (!backref->found_back_ref)
2977 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
2978 if (!backref->found_forward_ref)
2979 backref->errors |= REF_ERR_NO_ROOT_REF;
2980 if (backref->reachable && backref->errors)
2987 fprintf(stderr, "fs tree %llu refs %u %s\n",
2988 (unsigned long long)rec->objectid, rec->found_ref,
2989 rec->found_root_item ? "" : "not found");
2991 list_for_each_entry(backref, &rec->backrefs, list) {
2992 if (!backref->reachable)
2994 if (!backref->errors && rec->found_root_item)
2996 fprintf(stderr, "\tunresolved ref root %llu dir %llu"
2997 " index %llu namelen %u name %s errors %x\n",
2998 (unsigned long long)backref->ref_root,
2999 (unsigned long long)backref->dir,
3000 (unsigned long long)backref->index,
3001 backref->namelen, backref->name,
3003 print_ref_error(backref->errors);
3006 return errors > 0 ? 1 : 0;
3009 static int process_root_ref(struct extent_buffer *eb, int slot,
3010 struct btrfs_key *key,
3011 struct cache_tree *root_cache)
3017 struct btrfs_root_ref *ref;
3018 char namebuf[BTRFS_NAME_LEN];
3021 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
3023 dirid = btrfs_root_ref_dirid(eb, ref);
3024 index = btrfs_root_ref_sequence(eb, ref);
3025 name_len = btrfs_root_ref_name_len(eb, ref);
3027 if (name_len <= BTRFS_NAME_LEN) {
3031 len = BTRFS_NAME_LEN;
3032 error = REF_ERR_NAME_TOO_LONG;
3034 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
3036 if (key->type == BTRFS_ROOT_REF_KEY) {
3037 add_root_backref(root_cache, key->offset, key->objectid, dirid,
3038 index, namebuf, len, key->type, error);
3040 add_root_backref(root_cache, key->objectid, key->offset, dirid,
3041 index, namebuf, len, key->type, error);
3046 static void free_corrupt_block(struct cache_extent *cache)
3048 struct btrfs_corrupt_block *corrupt;
3050 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
3054 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
3057 * Repair the btree of the given root.
3059 * The fix is to remove the node key in corrupt_blocks cache_tree.
3060 * and rebalance the tree.
3061 * After the fix, the btree should be writeable.
3063 static int repair_btree(struct btrfs_root *root,
3064 struct cache_tree *corrupt_blocks)
3066 struct btrfs_trans_handle *trans;
3067 struct btrfs_path path;
3068 struct btrfs_corrupt_block *corrupt;
3069 struct cache_extent *cache;
3070 struct btrfs_key key;
3075 if (cache_tree_empty(corrupt_blocks))
3078 trans = btrfs_start_transaction(root, 1);
3079 if (IS_ERR(trans)) {
3080 ret = PTR_ERR(trans);
3081 fprintf(stderr, "Error starting transaction: %s\n",
3085 btrfs_init_path(&path);
3086 cache = first_cache_extent(corrupt_blocks);
3088 corrupt = container_of(cache, struct btrfs_corrupt_block,
3090 level = corrupt->level;
3091 path.lowest_level = level;
3092 key.objectid = corrupt->key.objectid;
3093 key.type = corrupt->key.type;
3094 key.offset = corrupt->key.offset;
3097 * Here we don't want to do any tree balance, since it may
3098 * cause a balance with corrupted brother leaf/node,
3099 * so ins_len set to 0 here.
3100 * Balance will be done after all corrupt node/leaf is deleted.
3102 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
3105 offset = btrfs_node_blockptr(path.nodes[level],
3108 /* Remove the ptr */
3109 ret = btrfs_del_ptr(root, &path, level, path.slots[level]);
3113 * Remove the corresponding extent
3114 * return value is not concerned.
3116 btrfs_release_path(&path);
3117 ret = btrfs_free_extent(trans, root, offset,
3118 root->fs_info->nodesize, 0,
3119 root->root_key.objectid, level - 1, 0);
3120 cache = next_cache_extent(cache);
3123 /* Balance the btree using btrfs_search_slot() */
3124 cache = first_cache_extent(corrupt_blocks);
3126 corrupt = container_of(cache, struct btrfs_corrupt_block,
3128 memcpy(&key, &corrupt->key, sizeof(key));
3129 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
3132 /* return will always >0 since it won't find the item */
3134 btrfs_release_path(&path);
3135 cache = next_cache_extent(cache);
3138 btrfs_commit_transaction(trans, root);
3139 btrfs_release_path(&path);
3143 static int check_fs_root(struct btrfs_root *root,
3144 struct cache_tree *root_cache,
3145 struct walk_control *wc)
3151 struct btrfs_path path;
3152 struct shared_node root_node;
3153 struct root_record *rec;
3154 struct btrfs_root_item *root_item = &root->root_item;
3155 struct cache_tree corrupt_blocks;
3156 struct orphan_data_extent *orphan;
3157 struct orphan_data_extent *tmp;
3158 enum btrfs_tree_block_status status;
3159 struct node_refs nrefs;
3162 * Reuse the corrupt_block cache tree to record corrupted tree block
3164 * Unlike the usage in extent tree check, here we do it in a per
3165 * fs/subvol tree base.
3167 cache_tree_init(&corrupt_blocks);
3168 root->fs_info->corrupt_blocks = &corrupt_blocks;
3170 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
3171 rec = get_root_rec(root_cache, root->root_key.objectid);
3172 BUG_ON(IS_ERR(rec));
3173 if (btrfs_root_refs(root_item) > 0)
3174 rec->found_root_item = 1;
3177 btrfs_init_path(&path);
3178 memset(&root_node, 0, sizeof(root_node));
3179 cache_tree_init(&root_node.root_cache);
3180 cache_tree_init(&root_node.inode_cache);
3181 memset(&nrefs, 0, sizeof(nrefs));
3183 /* Move the orphan extent record to corresponding inode_record */
3184 list_for_each_entry_safe(orphan, tmp,
3185 &root->orphan_data_extents, list) {
3186 struct inode_record *inode;
3188 inode = get_inode_rec(&root_node.inode_cache, orphan->objectid,
3190 BUG_ON(IS_ERR(inode));
3191 inode->errors |= I_ERR_FILE_EXTENT_ORPHAN;
3192 list_move(&orphan->list, &inode->orphan_extents);
3195 level = btrfs_header_level(root->node);
3196 memset(wc->nodes, 0, sizeof(wc->nodes));
3197 wc->nodes[level] = &root_node;
3198 wc->active_node = level;
3199 wc->root_level = level;
3201 /* We may not have checked the root block, lets do that now */
3202 if (btrfs_is_leaf(root->node))
3203 status = btrfs_check_leaf(root, NULL, root->node);
3205 status = btrfs_check_node(root, NULL, root->node);
3206 if (status != BTRFS_TREE_BLOCK_CLEAN)
3209 if (btrfs_root_refs(root_item) > 0 ||
3210 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
3211 path.nodes[level] = root->node;
3212 extent_buffer_get(root->node);
3213 path.slots[level] = 0;
3215 struct btrfs_key key;
3216 struct btrfs_disk_key found_key;
3218 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3219 level = root_item->drop_level;
3220 path.lowest_level = level;
3221 if (level > btrfs_header_level(root->node) ||
3222 level >= BTRFS_MAX_LEVEL) {
3223 error("ignoring invalid drop level: %u", level);
3226 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3229 btrfs_node_key(path.nodes[level], &found_key,
3231 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
3232 sizeof(found_key)));
3236 wret = walk_down_tree(root, &path, wc, &level, &nrefs);
3242 wret = walk_up_tree(root, &path, wc, &level);
3249 btrfs_release_path(&path);
3251 if (!cache_tree_empty(&corrupt_blocks)) {
3252 struct cache_extent *cache;
3253 struct btrfs_corrupt_block *corrupt;
3255 printf("The following tree block(s) is corrupted in tree %llu:\n",
3256 root->root_key.objectid);
3257 cache = first_cache_extent(&corrupt_blocks);
3259 corrupt = container_of(cache,
3260 struct btrfs_corrupt_block,
3262 printf("\ttree block bytenr: %llu, level: %d, node key: (%llu, %u, %llu)\n",
3263 cache->start, corrupt->level,
3264 corrupt->key.objectid, corrupt->key.type,
3265 corrupt->key.offset);
3266 cache = next_cache_extent(cache);
3269 printf("Try to repair the btree for root %llu\n",
3270 root->root_key.objectid);
3271 ret = repair_btree(root, &corrupt_blocks);
3273 fprintf(stderr, "Failed to repair btree: %s\n",
3276 printf("Btree for root %llu is fixed\n",
3277 root->root_key.objectid);
3281 err = merge_root_recs(root, &root_node.root_cache, root_cache);
3285 if (root_node.current) {
3286 root_node.current->checked = 1;
3287 maybe_free_inode_rec(&root_node.inode_cache,
3291 err = check_inode_recs(root, &root_node.inode_cache);
3295 free_corrupt_blocks_tree(&corrupt_blocks);
3296 root->fs_info->corrupt_blocks = NULL;
3297 free_orphan_data_extents(&root->orphan_data_extents);
3301 static int check_fs_roots(struct btrfs_fs_info *fs_info,
3302 struct cache_tree *root_cache)
3304 struct btrfs_path path;
3305 struct btrfs_key key;
3306 struct walk_control wc;
3307 struct extent_buffer *leaf, *tree_node;
3308 struct btrfs_root *tmp_root;
3309 struct btrfs_root *tree_root = fs_info->tree_root;
3313 if (ctx.progress_enabled) {
3314 ctx.tp = TASK_FS_ROOTS;
3315 task_start(ctx.info);
3319 * Just in case we made any changes to the extent tree that weren't
3320 * reflected into the free space cache yet.
3323 reset_cached_block_groups(fs_info);
3324 memset(&wc, 0, sizeof(wc));
3325 cache_tree_init(&wc.shared);
3326 btrfs_init_path(&path);
3331 key.type = BTRFS_ROOT_ITEM_KEY;
3332 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
3337 tree_node = tree_root->node;
3339 if (tree_node != tree_root->node) {
3340 free_root_recs_tree(root_cache);
3341 btrfs_release_path(&path);
3344 leaf = path.nodes[0];
3345 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
3346 ret = btrfs_next_leaf(tree_root, &path);
3352 leaf = path.nodes[0];
3354 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
3355 if (key.type == BTRFS_ROOT_ITEM_KEY &&
3356 fs_root_objectid(key.objectid)) {
3357 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
3358 tmp_root = btrfs_read_fs_root_no_cache(
3361 key.offset = (u64)-1;
3362 tmp_root = btrfs_read_fs_root(
3365 if (IS_ERR(tmp_root)) {
3369 ret = check_fs_root(tmp_root, root_cache, &wc);
3370 if (ret == -EAGAIN) {
3371 free_root_recs_tree(root_cache);
3372 btrfs_release_path(&path);
3377 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
3378 btrfs_free_fs_root(tmp_root);
3379 } else if (key.type == BTRFS_ROOT_REF_KEY ||
3380 key.type == BTRFS_ROOT_BACKREF_KEY) {
3381 process_root_ref(leaf, path.slots[0], &key,
3388 btrfs_release_path(&path);
3390 free_extent_cache_tree(&wc.shared);
3391 if (!cache_tree_empty(&wc.shared))
3392 fprintf(stderr, "warning line %d\n", __LINE__);
3394 task_stop(ctx.info);
3399 static struct tree_backref *find_tree_backref(struct extent_record *rec,
3400 u64 parent, u64 root)
3402 struct rb_node *node;
3403 struct tree_backref *back = NULL;
3404 struct tree_backref match = {
3411 match.parent = parent;
3412 match.node.full_backref = 1;
3417 node = rb_search(&rec->backref_tree, &match.node.node,
3418 (rb_compare_keys)compare_extent_backref, NULL);
3420 back = to_tree_backref(rb_node_to_extent_backref(node));
3425 static struct data_backref *find_data_backref(struct extent_record *rec,
3426 u64 parent, u64 root,
3427 u64 owner, u64 offset,
3429 u64 disk_bytenr, u64 bytes)
3431 struct rb_node *node;
3432 struct data_backref *back = NULL;
3433 struct data_backref match = {
3440 .found_ref = found_ref,
3441 .disk_bytenr = disk_bytenr,
3445 match.parent = parent;
3446 match.node.full_backref = 1;
3451 node = rb_search(&rec->backref_tree, &match.node.node,
3452 (rb_compare_keys)compare_extent_backref, NULL);
3454 back = to_data_backref(rb_node_to_extent_backref(node));
3459 static int do_check_fs_roots(struct btrfs_fs_info *fs_info,
3460 struct cache_tree *root_cache)
3464 if (!ctx.progress_enabled)
3465 fprintf(stderr, "checking fs roots\n");
3466 if (check_mode == CHECK_MODE_LOWMEM)
3467 ret = check_fs_roots_lowmem(fs_info);
3469 ret = check_fs_roots(fs_info, root_cache);
3474 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
3476 struct extent_backref *back, *tmp;
3477 struct tree_backref *tback;
3478 struct data_backref *dback;
3482 rbtree_postorder_for_each_entry_safe(back, tmp,
3483 &rec->backref_tree, node) {
3484 if (!back->found_extent_tree) {
3488 if (back->is_data) {
3489 dback = to_data_backref(back);
3491 "data backref %llu %s %llu owner %llu offset %llu num_refs %lu not found in extent tree\n",
3492 (unsigned long long)rec->start,
3493 back->full_backref ?
3495 back->full_backref ?
3496 (unsigned long long)dback->parent :
3497 (unsigned long long)dback->root,
3498 (unsigned long long)dback->owner,
3499 (unsigned long long)dback->offset,
3500 (unsigned long)dback->num_refs);
3502 tback = to_tree_backref(back);
3504 "tree backref %llu parent %llu root %llu not found in extent tree\n",
3505 (unsigned long long)rec->start,
3506 (unsigned long long)tback->parent,
3507 (unsigned long long)tback->root);
3510 if (!back->is_data && !back->found_ref) {
3514 tback = to_tree_backref(back);
3516 "backref %llu %s %llu not referenced back %p\n",
3517 (unsigned long long)rec->start,
3518 back->full_backref ? "parent" : "root",
3519 back->full_backref ?
3520 (unsigned long long)tback->parent :
3521 (unsigned long long)tback->root, back);
3523 if (back->is_data) {
3524 dback = to_data_backref(back);
3525 if (dback->found_ref != dback->num_refs) {
3530 "incorrect local backref count on %llu %s %llu owner %llu offset %llu found %u wanted %u back %p\n",
3531 (unsigned long long)rec->start,
3532 back->full_backref ?
3534 back->full_backref ?
3535 (unsigned long long)dback->parent :
3536 (unsigned long long)dback->root,
3537 (unsigned long long)dback->owner,
3538 (unsigned long long)dback->offset,
3539 dback->found_ref, dback->num_refs,
3542 if (dback->disk_bytenr != rec->start) {
3547 "backref disk bytenr does not match extent record, bytenr=%llu, ref bytenr=%llu\n",
3548 (unsigned long long)rec->start,
3549 (unsigned long long)dback->disk_bytenr);
3552 if (dback->bytes != rec->nr) {
3557 "backref bytes do not match extent backref, bytenr=%llu, ref bytes=%llu, backref bytes=%llu\n",
3558 (unsigned long long)rec->start,
3559 (unsigned long long)rec->nr,
3560 (unsigned long long)dback->bytes);
3563 if (!back->is_data) {
3566 dback = to_data_backref(back);
3567 found += dback->found_ref;
3570 if (found != rec->refs) {
3575 "incorrect global backref count on %llu found %llu wanted %llu\n",
3576 (unsigned long long)rec->start,
3577 (unsigned long long)found,
3578 (unsigned long long)rec->refs);
3584 static void __free_one_backref(struct rb_node *node)
3586 struct extent_backref *back = rb_node_to_extent_backref(node);
3591 static void free_all_extent_backrefs(struct extent_record *rec)
3593 rb_free_nodes(&rec->backref_tree, __free_one_backref);
3596 static void free_extent_record_cache(struct cache_tree *extent_cache)
3598 struct cache_extent *cache;
3599 struct extent_record *rec;
3602 cache = first_cache_extent(extent_cache);
3605 rec = container_of(cache, struct extent_record, cache);
3606 remove_cache_extent(extent_cache, cache);
3607 free_all_extent_backrefs(rec);
3612 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
3613 struct extent_record *rec)
3615 if (rec->content_checked && rec->owner_ref_checked &&
3616 rec->extent_item_refs == rec->refs && rec->refs > 0 &&
3617 rec->num_duplicates == 0 && !all_backpointers_checked(rec, 0) &&
3618 !rec->bad_full_backref && !rec->crossing_stripes &&
3619 !rec->wrong_chunk_type) {
3620 remove_cache_extent(extent_cache, &rec->cache);
3621 free_all_extent_backrefs(rec);
3622 list_del_init(&rec->list);
3628 static int check_owner_ref(struct btrfs_root *root,
3629 struct extent_record *rec,
3630 struct extent_buffer *buf)
3632 struct extent_backref *node, *tmp;
3633 struct tree_backref *back;
3634 struct btrfs_root *ref_root;
3635 struct btrfs_key key;
3636 struct btrfs_path path;
3637 struct extent_buffer *parent;
3642 rbtree_postorder_for_each_entry_safe(node, tmp,
3643 &rec->backref_tree, node) {
3646 if (!node->found_ref)
3648 if (node->full_backref)
3650 back = to_tree_backref(node);
3651 if (btrfs_header_owner(buf) == back->root)
3654 BUG_ON(rec->is_root);
3656 /* try to find the block by search corresponding fs tree */
3657 key.objectid = btrfs_header_owner(buf);
3658 key.type = BTRFS_ROOT_ITEM_KEY;
3659 key.offset = (u64)-1;
3661 ref_root = btrfs_read_fs_root(root->fs_info, &key);
3662 if (IS_ERR(ref_root))
3665 level = btrfs_header_level(buf);
3667 btrfs_item_key_to_cpu(buf, &key, 0);
3669 btrfs_node_key_to_cpu(buf, &key, 0);
3671 btrfs_init_path(&path);
3672 path.lowest_level = level + 1;
3673 ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
3677 parent = path.nodes[level + 1];
3678 if (parent && buf->start == btrfs_node_blockptr(parent,
3679 path.slots[level + 1]))
3682 btrfs_release_path(&path);
3683 return found ? 0 : 1;
3686 static int is_extent_tree_record(struct extent_record *rec)
3688 struct extent_backref *node, *tmp;
3689 struct tree_backref *back;
3692 rbtree_postorder_for_each_entry_safe(node, tmp,
3693 &rec->backref_tree, node) {
3696 back = to_tree_backref(node);
3697 if (node->full_backref)
3699 if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
3706 static int record_bad_block_io(struct btrfs_fs_info *info,
3707 struct cache_tree *extent_cache,
3710 struct extent_record *rec;
3711 struct cache_extent *cache;
3712 struct btrfs_key key;
3714 cache = lookup_cache_extent(extent_cache, start, len);
3718 rec = container_of(cache, struct extent_record, cache);
3719 if (!is_extent_tree_record(rec))
3722 btrfs_disk_key_to_cpu(&key, &rec->parent_key);
3723 return btrfs_add_corrupt_extent_record(info, &key, start, len, 0);
3726 static int swap_values(struct btrfs_root *root, struct btrfs_path *path,
3727 struct extent_buffer *buf, int slot)
3729 if (btrfs_header_level(buf)) {
3730 struct btrfs_key_ptr ptr1, ptr2;
3732 read_extent_buffer(buf, &ptr1, btrfs_node_key_ptr_offset(slot),
3733 sizeof(struct btrfs_key_ptr));
3734 read_extent_buffer(buf, &ptr2,
3735 btrfs_node_key_ptr_offset(slot + 1),
3736 sizeof(struct btrfs_key_ptr));
3737 write_extent_buffer(buf, &ptr1,
3738 btrfs_node_key_ptr_offset(slot + 1),
3739 sizeof(struct btrfs_key_ptr));
3740 write_extent_buffer(buf, &ptr2,
3741 btrfs_node_key_ptr_offset(slot),
3742 sizeof(struct btrfs_key_ptr));
3744 struct btrfs_disk_key key;
3746 btrfs_node_key(buf, &key, 0);
3747 btrfs_fixup_low_keys(root, path, &key,
3748 btrfs_header_level(buf) + 1);
3751 struct btrfs_item *item1, *item2;
3752 struct btrfs_key k1, k2;
3753 char *item1_data, *item2_data;
3754 u32 item1_offset, item2_offset, item1_size, item2_size;
3756 item1 = btrfs_item_nr(slot);
3757 item2 = btrfs_item_nr(slot + 1);
3758 btrfs_item_key_to_cpu(buf, &k1, slot);
3759 btrfs_item_key_to_cpu(buf, &k2, slot + 1);
3760 item1_offset = btrfs_item_offset(buf, item1);
3761 item2_offset = btrfs_item_offset(buf, item2);
3762 item1_size = btrfs_item_size(buf, item1);
3763 item2_size = btrfs_item_size(buf, item2);
3765 item1_data = malloc(item1_size);
3768 item2_data = malloc(item2_size);
3774 read_extent_buffer(buf, item1_data, item1_offset, item1_size);
3775 read_extent_buffer(buf, item2_data, item2_offset, item2_size);
3777 write_extent_buffer(buf, item1_data, item2_offset, item2_size);
3778 write_extent_buffer(buf, item2_data, item1_offset, item1_size);
3782 btrfs_set_item_offset(buf, item1, item2_offset);
3783 btrfs_set_item_offset(buf, item2, item1_offset);
3784 btrfs_set_item_size(buf, item1, item2_size);
3785 btrfs_set_item_size(buf, item2, item1_size);
3787 path->slots[0] = slot;
3788 btrfs_set_item_key_unsafe(root, path, &k2);
3789 path->slots[0] = slot + 1;
3790 btrfs_set_item_key_unsafe(root, path, &k1);
3795 static int fix_key_order(struct btrfs_root *root, struct btrfs_path *path)
3797 struct extent_buffer *buf;
3798 struct btrfs_key k1, k2;
3800 int level = path->lowest_level;
3803 buf = path->nodes[level];
3804 for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
3806 btrfs_node_key_to_cpu(buf, &k1, i);
3807 btrfs_node_key_to_cpu(buf, &k2, i + 1);
3809 btrfs_item_key_to_cpu(buf, &k1, i);
3810 btrfs_item_key_to_cpu(buf, &k2, i + 1);
3812 if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
3814 ret = swap_values(root, path, buf, i);
3817 btrfs_mark_buffer_dirty(buf);
3823 static int delete_bogus_item(struct btrfs_root *root,
3824 struct btrfs_path *path,
3825 struct extent_buffer *buf, int slot)
3827 struct btrfs_key key;
3828 int nritems = btrfs_header_nritems(buf);
3830 btrfs_item_key_to_cpu(buf, &key, slot);
3832 /* These are all the keys we can deal with missing. */
3833 if (key.type != BTRFS_DIR_INDEX_KEY &&
3834 key.type != BTRFS_EXTENT_ITEM_KEY &&
3835 key.type != BTRFS_METADATA_ITEM_KEY &&
3836 key.type != BTRFS_TREE_BLOCK_REF_KEY &&
3837 key.type != BTRFS_EXTENT_DATA_REF_KEY)
3840 printf("Deleting bogus item [%llu,%u,%llu] at slot %d on block %llu\n",
3841 (unsigned long long)key.objectid, key.type,
3842 (unsigned long long)key.offset, slot, buf->start);
3843 memmove_extent_buffer(buf, btrfs_item_nr_offset(slot),
3844 btrfs_item_nr_offset(slot + 1),
3845 sizeof(struct btrfs_item) *
3846 (nritems - slot - 1));
3847 btrfs_set_header_nritems(buf, nritems - 1);
3849 struct btrfs_disk_key disk_key;
3851 btrfs_item_key(buf, &disk_key, 0);
3852 btrfs_fixup_low_keys(root, path, &disk_key, 1);
3854 btrfs_mark_buffer_dirty(buf);
3858 static int fix_item_offset(struct btrfs_root *root, struct btrfs_path *path)
3860 struct extent_buffer *buf;
3864 /* We should only get this for leaves */
3865 BUG_ON(path->lowest_level);
3866 buf = path->nodes[0];
3868 for (i = 0; i < btrfs_header_nritems(buf); i++) {
3869 unsigned int shift = 0, offset;
3871 if (i == 0 && btrfs_item_end_nr(buf, i) !=
3872 BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
3873 if (btrfs_item_end_nr(buf, i) >
3874 BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
3875 ret = delete_bogus_item(root, path, buf, i);
3879 "item is off the end of the leaf, can't fix\n");
3883 shift = BTRFS_LEAF_DATA_SIZE(root->fs_info) -
3884 btrfs_item_end_nr(buf, i);
3885 } else if (i > 0 && btrfs_item_end_nr(buf, i) !=
3886 btrfs_item_offset_nr(buf, i - 1)) {
3887 if (btrfs_item_end_nr(buf, i) >
3888 btrfs_item_offset_nr(buf, i - 1)) {
3889 ret = delete_bogus_item(root, path, buf, i);
3892 fprintf(stderr, "items overlap, can't fix\n");
3896 shift = btrfs_item_offset_nr(buf, i - 1) -
3897 btrfs_item_end_nr(buf, i);
3902 printf("Shifting item nr %d by %u bytes in block %llu\n",
3903 i, shift, (unsigned long long)buf->start);
3904 offset = btrfs_item_offset_nr(buf, i);
3905 memmove_extent_buffer(buf,
3906 btrfs_leaf_data(buf) + offset + shift,
3907 btrfs_leaf_data(buf) + offset,
3908 btrfs_item_size_nr(buf, i));
3909 btrfs_set_item_offset(buf, btrfs_item_nr(i),
3911 btrfs_mark_buffer_dirty(buf);
3915 * We may have moved things, in which case we want to exit so we don't
3916 * write those changes out. Once we have proper abort functionality in
3917 * progs this can be changed to something nicer.
3924 * Attempt to fix basic block failures. If we can't fix it for whatever reason
3925 * then just return -EIO.
3927 static int try_to_fix_bad_block(struct btrfs_root *root,
3928 struct extent_buffer *buf,
3929 enum btrfs_tree_block_status status)
3931 struct btrfs_trans_handle *trans;
3932 struct ulist *roots;
3933 struct ulist_node *node;
3934 struct btrfs_root *search_root;
3935 struct btrfs_path path;
3936 struct ulist_iterator iter;
3937 struct btrfs_key root_key, key;
3940 if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER &&
3941 status != BTRFS_TREE_BLOCK_INVALID_OFFSETS)
3944 ret = btrfs_find_all_roots(NULL, root->fs_info, buf->start, 0, &roots);
3948 btrfs_init_path(&path);
3949 ULIST_ITER_INIT(&iter);
3950 while ((node = ulist_next(roots, &iter))) {
3951 root_key.objectid = node->val;
3952 root_key.type = BTRFS_ROOT_ITEM_KEY;
3953 root_key.offset = (u64)-1;
3955 search_root = btrfs_read_fs_root(root->fs_info, &root_key);
3962 trans = btrfs_start_transaction(search_root, 0);
3963 if (IS_ERR(trans)) {
3964 ret = PTR_ERR(trans);
3968 path.lowest_level = btrfs_header_level(buf);
3969 path.skip_check_block = 1;
3970 if (path.lowest_level)
3971 btrfs_node_key_to_cpu(buf, &key, 0);
3973 btrfs_item_key_to_cpu(buf, &key, 0);
3974 ret = btrfs_search_slot(trans, search_root, &key, &path, 0, 1);
3977 btrfs_commit_transaction(trans, search_root);
3980 if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
3981 ret = fix_key_order(search_root, &path);
3982 else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
3983 ret = fix_item_offset(search_root, &path);
3985 btrfs_commit_transaction(trans, search_root);
3988 btrfs_release_path(&path);
3989 btrfs_commit_transaction(trans, search_root);
3992 btrfs_release_path(&path);
3996 static int check_block(struct btrfs_root *root,
3997 struct cache_tree *extent_cache,
3998 struct extent_buffer *buf, u64 flags)
4000 struct extent_record *rec;
4001 struct cache_extent *cache;
4002 struct btrfs_key key;
4003 enum btrfs_tree_block_status status;
4007 cache = lookup_cache_extent(extent_cache, buf->start, buf->len);
4010 rec = container_of(cache, struct extent_record, cache);
4011 rec->generation = btrfs_header_generation(buf);
4013 level = btrfs_header_level(buf);
4014 if (btrfs_header_nritems(buf) > 0) {
4017 btrfs_item_key_to_cpu(buf, &key, 0);
4019 btrfs_node_key_to_cpu(buf, &key, 0);
4021 rec->info_objectid = key.objectid;
4023 rec->info_level = level;
4025 if (btrfs_is_leaf(buf))
4026 status = btrfs_check_leaf(root, &rec->parent_key, buf);
4028 status = btrfs_check_node(root, &rec->parent_key, buf);
4030 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4032 status = try_to_fix_bad_block(root, buf, status);
4033 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4035 fprintf(stderr, "bad block %llu\n",
4036 (unsigned long long)buf->start);
4039 * Signal to callers we need to start the scan over
4040 * again since we'll have cowed blocks.
4045 rec->content_checked = 1;
4046 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
4047 rec->owner_ref_checked = 1;
4049 ret = check_owner_ref(root, rec, buf);
4051 rec->owner_ref_checked = 1;
4055 maybe_free_extent_rec(extent_cache, rec);
4060 static struct tree_backref *find_tree_backref(struct extent_record *rec,
4061 u64 parent, u64 root)
4063 struct list_head *cur = rec->backrefs.next;
4064 struct extent_backref *node;
4065 struct tree_backref *back;
4067 while (cur != &rec->backrefs) {
4068 node = to_extent_backref(cur);
4072 back = to_tree_backref(node);
4074 if (!node->full_backref)
4076 if (parent == back->parent)
4079 if (node->full_backref)
4081 if (back->root == root)
4089 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
4090 u64 parent, u64 root)
4092 struct tree_backref *ref = malloc(sizeof(*ref));
4096 memset(&ref->node, 0, sizeof(ref->node));
4098 ref->parent = parent;
4099 ref->node.full_backref = 1;
4102 ref->node.full_backref = 0;
4109 static struct data_backref *find_data_backref(struct extent_record *rec,
4110 u64 parent, u64 root,
4111 u64 owner, u64 offset,
4113 u64 disk_bytenr, u64 bytes)
4115 struct list_head *cur = rec->backrefs.next;
4116 struct extent_backref *node;
4117 struct data_backref *back;
4119 while (cur != &rec->backrefs) {
4120 node = to_extent_backref(cur);
4124 back = to_data_backref(node);
4126 if (!node->full_backref)
4128 if (parent == back->parent)
4131 if (node->full_backref)
4133 if (back->root == root && back->owner == owner &&
4134 back->offset == offset) {
4135 if (found_ref && node->found_ref &&
4136 (back->bytes != bytes ||
4137 back->disk_bytenr != disk_bytenr))
4147 static struct data_backref *alloc_data_backref(struct extent_record *rec,
4148 u64 parent, u64 root,
4149 u64 owner, u64 offset,
4152 struct data_backref *ref = malloc(sizeof(*ref));
4156 memset(&ref->node, 0, sizeof(ref->node));
4157 ref->node.is_data = 1;
4160 ref->parent = parent;
4163 ref->node.full_backref = 1;
4167 ref->offset = offset;
4168 ref->node.full_backref = 0;
4170 ref->bytes = max_size;
4173 if (max_size > rec->max_size)
4174 rec->max_size = max_size;
4178 /* Check if the type of extent matches with its chunk */
4179 static void check_extent_type(struct extent_record *rec)
4181 struct btrfs_block_group_cache *bg_cache;
4183 bg_cache = btrfs_lookup_first_block_group(global_info, rec->start);
4187 /* data extent, check chunk directly*/
4188 if (!rec->metadata) {
4189 if (!(bg_cache->flags & BTRFS_BLOCK_GROUP_DATA))
4190 rec->wrong_chunk_type = 1;
4194 /* metadata extent, check the obvious case first */
4195 if (!(bg_cache->flags & (BTRFS_BLOCK_GROUP_SYSTEM |
4196 BTRFS_BLOCK_GROUP_METADATA))) {
4197 rec->wrong_chunk_type = 1;
4202 * Check SYSTEM extent, as it's also marked as metadata, we can only
4203 * make sure it's a SYSTEM extent by its backref
4205 if (!RB_EMPTY_ROOT(&rec->backref_tree)) {
4206 struct extent_backref *node;
4207 struct tree_backref *tback;
4210 node = rb_node_to_extent_backref(rb_first(&rec->backref_tree));
4211 if (node->is_data) {
4212 /* tree block shouldn't have data backref */
4213 rec->wrong_chunk_type = 1;
4216 tback = container_of(node, struct tree_backref, node);
4218 if (tback->root == BTRFS_CHUNK_TREE_OBJECTID)
4219 bg_type = BTRFS_BLOCK_GROUP_SYSTEM;
4221 bg_type = BTRFS_BLOCK_GROUP_METADATA;
4222 if (!(bg_cache->flags & bg_type))
4223 rec->wrong_chunk_type = 1;
4228 * Allocate a new extent record, fill default values from @tmpl and insert int
4229 * @extent_cache. Caller is supposed to make sure the [start,nr) is not in
4230 * the cache, otherwise it fails.
4232 static int add_extent_rec_nolookup(struct cache_tree *extent_cache,
4233 struct extent_record *tmpl)
4235 struct extent_record *rec;
4238 BUG_ON(tmpl->max_size == 0);
4239 rec = malloc(sizeof(*rec));
4242 rec->start = tmpl->start;
4243 rec->max_size = tmpl->max_size;
4244 rec->nr = max(tmpl->nr, tmpl->max_size);
4245 rec->found_rec = tmpl->found_rec;
4246 rec->content_checked = tmpl->content_checked;
4247 rec->owner_ref_checked = tmpl->owner_ref_checked;
4248 rec->num_duplicates = 0;
4249 rec->metadata = tmpl->metadata;
4250 rec->flag_block_full_backref = FLAG_UNSET;
4251 rec->bad_full_backref = 0;
4252 rec->crossing_stripes = 0;
4253 rec->wrong_chunk_type = 0;
4254 rec->is_root = tmpl->is_root;
4255 rec->refs = tmpl->refs;
4256 rec->extent_item_refs = tmpl->extent_item_refs;
4257 rec->parent_generation = tmpl->parent_generation;
4258 INIT_LIST_HEAD(&rec->backrefs);
4259 INIT_LIST_HEAD(&rec->dups);
4260 INIT_LIST_HEAD(&rec->list);
4261 rec->backref_tree = RB_ROOT;
4262 memcpy(&rec->parent_key, &tmpl->parent_key, sizeof(tmpl->parent_key));
4263 rec->cache.start = tmpl->start;
4264 rec->cache.size = tmpl->nr;
4265 ret = insert_cache_extent(extent_cache, &rec->cache);
4270 bytes_used += rec->nr;
4273 rec->crossing_stripes = check_crossing_stripes(global_info,
4274 rec->start, global_info->nodesize);
4275 check_extent_type(rec);
4280 * Lookup and modify an extent, some values of @tmpl are interpreted verbatim,
4282 * - refs - if found, increase refs
4283 * - is_root - if found, set
4284 * - content_checked - if found, set
4285 * - owner_ref_checked - if found, set
4287 * If not found, create a new one, initialize and insert.
4289 static int add_extent_rec(struct cache_tree *extent_cache,
4290 struct extent_record *tmpl)
4292 struct extent_record *rec;
4293 struct cache_extent *cache;
4297 cache = lookup_cache_extent(extent_cache, tmpl->start, tmpl->nr);
4299 rec = container_of(cache, struct extent_record, cache);
4303 rec->nr = max(tmpl->nr, tmpl->max_size);
4306 * We need to make sure to reset nr to whatever the extent
4307 * record says was the real size, this way we can compare it to
4310 if (tmpl->found_rec) {
4311 if (tmpl->start != rec->start || rec->found_rec) {
4312 struct extent_record *tmp;
4315 if (list_empty(&rec->list))
4316 list_add_tail(&rec->list,
4317 &duplicate_extents);
4320 * We have to do this song and dance in case we
4321 * find an extent record that falls inside of
4322 * our current extent record but does not have
4323 * the same objectid.
4325 tmp = malloc(sizeof(*tmp));
4328 tmp->start = tmpl->start;
4329 tmp->max_size = tmpl->max_size;
4332 tmp->metadata = tmpl->metadata;
4333 tmp->extent_item_refs = tmpl->extent_item_refs;
4334 INIT_LIST_HEAD(&tmp->list);
4335 list_add_tail(&tmp->list, &rec->dups);
4336 rec->num_duplicates++;
4343 if (tmpl->extent_item_refs && !dup) {
4344 if (rec->extent_item_refs) {
4346 "block %llu rec extent_item_refs %llu, passed %llu\n",
4347 (unsigned long long)tmpl->start,
4348 (unsigned long long)
4349 rec->extent_item_refs,
4350 (unsigned long long)
4351 tmpl->extent_item_refs);
4353 rec->extent_item_refs = tmpl->extent_item_refs;
4357 if (tmpl->content_checked)
4358 rec->content_checked = 1;
4359 if (tmpl->owner_ref_checked)
4360 rec->owner_ref_checked = 1;
4361 memcpy(&rec->parent_key, &tmpl->parent_key,
4362 sizeof(tmpl->parent_key));
4363 if (tmpl->parent_generation)
4364 rec->parent_generation = tmpl->parent_generation;
4365 if (rec->max_size < tmpl->max_size)
4366 rec->max_size = tmpl->max_size;
4369 * A metadata extent can't cross stripe_len boundary, otherwise
4370 * kernel scrub won't be able to handle it.
4371 * As now stripe_len is fixed to BTRFS_STRIPE_LEN, just check
4375 rec->crossing_stripes = check_crossing_stripes(
4376 global_info, rec->start,
4377 global_info->nodesize);
4378 check_extent_type(rec);
4379 maybe_free_extent_rec(extent_cache, rec);
4383 ret = add_extent_rec_nolookup(extent_cache, tmpl);
4388 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
4389 u64 parent, u64 root, int found_ref)
4391 struct extent_record *rec;
4392 struct tree_backref *back;
4393 struct cache_extent *cache;
4395 bool insert = false;
4397 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4399 struct extent_record tmpl;
4401 memset(&tmpl, 0, sizeof(tmpl));
4402 tmpl.start = bytenr;
4407 ret = add_extent_rec_nolookup(extent_cache, &tmpl);
4411 /* really a bug in cache_extent implement now */
4412 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4417 rec = container_of(cache, struct extent_record, cache);
4418 if (rec->start != bytenr) {
4420 * Several cause, from unaligned bytenr to over lapping extents
4425 back = find_tree_backref(rec, parent, root);
4427 back = alloc_tree_backref(rec, parent, root);
4434 if (back->node.found_ref) {
4436 "Extent back ref already exists for %llu parent %llu root %llu\n",
4437 (unsigned long long)bytenr,
4438 (unsigned long long)parent,
4439 (unsigned long long)root);
4441 back->node.found_ref = 1;
4443 if (back->node.found_extent_tree) {
4445 "extent back ref already exists for %llu parent %llu root %llu\n",
4446 (unsigned long long)bytenr,
4447 (unsigned long long)parent,
4448 (unsigned long long)root);
4450 back->node.found_extent_tree = 1;
4453 WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
4454 compare_extent_backref));
4455 check_extent_type(rec);
4456 maybe_free_extent_rec(extent_cache, rec);
4460 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
4461 u64 parent, u64 root, u64 owner, u64 offset,
4462 u32 num_refs, int found_ref, u64 max_size)
4464 struct extent_record *rec;
4465 struct data_backref *back;
4466 struct cache_extent *cache;
4468 bool insert = false;
4470 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4472 struct extent_record tmpl;
4474 memset(&tmpl, 0, sizeof(tmpl));
4475 tmpl.start = bytenr;
4477 tmpl.max_size = max_size;
4479 ret = add_extent_rec_nolookup(extent_cache, &tmpl);
4483 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4488 rec = container_of(cache, struct extent_record, cache);
4489 if (rec->max_size < max_size)
4490 rec->max_size = max_size;
4493 * If found_ref is set then max_size is the real size and must match the
4494 * existing refs. So if we have already found a ref then we need to
4495 * make sure that this ref matches the existing one, otherwise we need
4496 * to add a new backref so we can notice that the backrefs don't match
4497 * and we need to figure out who is telling the truth. This is to
4498 * account for that awful fsync bug I introduced where we'd end up with
4499 * a btrfs_file_extent_item that would have its length include multiple
4500 * prealloc extents or point inside of a prealloc extent.
4502 back = find_data_backref(rec, parent, root, owner, offset, found_ref,
4505 back = alloc_data_backref(rec, parent, root, owner, offset,
4512 BUG_ON(num_refs != 1);
4513 if (back->node.found_ref)
4514 BUG_ON(back->bytes != max_size);
4515 back->node.found_ref = 1;
4516 back->found_ref += 1;
4517 if (back->bytes != max_size || back->disk_bytenr != bytenr) {
4518 back->bytes = max_size;
4519 back->disk_bytenr = bytenr;
4521 /* Need to reinsert if not already in the tree */
4523 rb_erase(&back->node.node, &rec->backref_tree);
4528 rec->content_checked = 1;
4529 rec->owner_ref_checked = 1;
4531 if (back->node.found_extent_tree) {
4533 "Extent back ref already exists for %llu parent %llu root %llu owner %llu offset %llu num_refs %lu\n",
4534 (unsigned long long)bytenr,
4535 (unsigned long long)parent,
4536 (unsigned long long)root,
4537 (unsigned long long)owner,
4538 (unsigned long long)offset,
4539 (unsigned long)num_refs);
4541 back->num_refs = num_refs;
4542 back->node.found_extent_tree = 1;
4545 WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
4546 compare_extent_backref));
4548 maybe_free_extent_rec(extent_cache, rec);
4552 static int add_pending(struct cache_tree *pending,
4553 struct cache_tree *seen, u64 bytenr, u32 size)
4557 ret = add_cache_extent(seen, bytenr, size);
4560 add_cache_extent(pending, bytenr, size);
4564 static int pick_next_pending(struct cache_tree *pending,
4565 struct cache_tree *reada,
4566 struct cache_tree *nodes,
4567 u64 last, struct block_info *bits, int bits_nr,
4570 unsigned long node_start = last;
4571 struct cache_extent *cache;
4574 cache = search_cache_extent(reada, 0);
4576 bits[0].start = cache->start;
4577 bits[0].size = cache->size;
4582 if (node_start > 32768)
4583 node_start -= 32768;
4585 cache = search_cache_extent(nodes, node_start);
4587 cache = search_cache_extent(nodes, 0);
4590 cache = search_cache_extent(pending, 0);
4595 bits[ret].start = cache->start;
4596 bits[ret].size = cache->size;
4597 cache = next_cache_extent(cache);
4599 } while (cache && ret < bits_nr);
4605 bits[ret].start = cache->start;
4606 bits[ret].size = cache->size;
4607 cache = next_cache_extent(cache);
4609 } while (cache && ret < bits_nr);
4611 if (bits_nr - ret > 8) {
4612 u64 lookup = bits[0].start + bits[0].size;
4613 struct cache_extent *next;
4615 next = search_cache_extent(pending, lookup);
4617 if (next->start - lookup > 32768)
4619 bits[ret].start = next->start;
4620 bits[ret].size = next->size;
4621 lookup = next->start + next->size;
4625 next = next_cache_extent(next);
4633 static void free_chunk_record(struct cache_extent *cache)
4635 struct chunk_record *rec;
4637 rec = container_of(cache, struct chunk_record, cache);
4638 list_del_init(&rec->list);
4639 list_del_init(&rec->dextents);
4643 void free_chunk_cache_tree(struct cache_tree *chunk_cache)
4645 cache_tree_free_extents(chunk_cache, free_chunk_record);
4648 static void free_device_record(struct rb_node *node)
4650 struct device_record *rec;
4652 rec = container_of(node, struct device_record, node);
4656 FREE_RB_BASED_TREE(device_cache, free_device_record);
4658 int insert_block_group_record(struct block_group_tree *tree,
4659 struct block_group_record *bg_rec)
4663 ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
4667 list_add_tail(&bg_rec->list, &tree->block_groups);
4671 static void free_block_group_record(struct cache_extent *cache)
4673 struct block_group_record *rec;
4675 rec = container_of(cache, struct block_group_record, cache);
4676 list_del_init(&rec->list);
4680 void free_block_group_tree(struct block_group_tree *tree)
4682 cache_tree_free_extents(&tree->tree, free_block_group_record);
4685 int insert_device_extent_record(struct device_extent_tree *tree,
4686 struct device_extent_record *de_rec)
4691 * Device extent is a bit different from the other extents, because
4692 * the extents which belong to the different devices may have the
4693 * same start and size, so we need use the special extent cache
4694 * search/insert functions.
4696 ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
4700 list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
4701 list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
4705 static void free_device_extent_record(struct cache_extent *cache)
4707 struct device_extent_record *rec;
4709 rec = container_of(cache, struct device_extent_record, cache);
4710 if (!list_empty(&rec->chunk_list))
4711 list_del_init(&rec->chunk_list);
4712 if (!list_empty(&rec->device_list))
4713 list_del_init(&rec->device_list);
4717 void free_device_extent_tree(struct device_extent_tree *tree)
4719 cache_tree_free_extents(&tree->tree, free_device_extent_record);
4722 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4723 static int process_extent_ref_v0(struct cache_tree *extent_cache,
4724 struct extent_buffer *leaf, int slot)
4726 struct btrfs_extent_ref_v0 *ref0;
4727 struct btrfs_key key;
4730 btrfs_item_key_to_cpu(leaf, &key, slot);
4731 ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
4732 if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
4733 ret = add_tree_backref(extent_cache, key.objectid, key.offset,
4736 ret = add_data_backref(extent_cache, key.objectid, key.offset,
4737 0, 0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
4743 struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
4744 struct btrfs_key *key,
4747 struct btrfs_chunk *ptr;
4748 struct chunk_record *rec;
4751 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
4752 num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
4754 rec = calloc(1, btrfs_chunk_record_size(num_stripes));
4756 fprintf(stderr, "memory allocation failed\n");
4760 INIT_LIST_HEAD(&rec->list);
4761 INIT_LIST_HEAD(&rec->dextents);
4764 rec->cache.start = key->offset;
4765 rec->cache.size = btrfs_chunk_length(leaf, ptr);
4767 rec->generation = btrfs_header_generation(leaf);
4769 rec->objectid = key->objectid;
4770 rec->type = key->type;
4771 rec->offset = key->offset;
4773 rec->length = rec->cache.size;
4774 rec->owner = btrfs_chunk_owner(leaf, ptr);
4775 rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
4776 rec->type_flags = btrfs_chunk_type(leaf, ptr);
4777 rec->io_width = btrfs_chunk_io_width(leaf, ptr);
4778 rec->io_align = btrfs_chunk_io_align(leaf, ptr);
4779 rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
4780 rec->num_stripes = num_stripes;
4781 rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
4783 for (i = 0; i < rec->num_stripes; ++i) {
4784 rec->stripes[i].devid =
4785 btrfs_stripe_devid_nr(leaf, ptr, i);
4786 rec->stripes[i].offset =
4787 btrfs_stripe_offset_nr(leaf, ptr, i);
4788 read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
4789 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
4796 static int process_chunk_item(struct cache_tree *chunk_cache,
4797 struct btrfs_key *key, struct extent_buffer *eb,
4800 struct chunk_record *rec;
4801 struct btrfs_chunk *chunk;
4804 chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
4806 * Do extra check for this chunk item,
4808 * It's still possible one can craft a leaf with CHUNK_ITEM, with
4809 * wrong onwer(3) out of chunk tree, to pass both chunk tree check
4810 * and owner<->key_type check.
4812 ret = btrfs_check_chunk_valid(global_info, eb, chunk, slot,
4815 error("chunk(%llu, %llu) is not valid, ignore it",
4816 key->offset, btrfs_chunk_length(eb, chunk));
4819 rec = btrfs_new_chunk_record(eb, key, slot);
4820 ret = insert_cache_extent(chunk_cache, &rec->cache);
4822 fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
4823 rec->offset, rec->length);
4830 static int process_device_item(struct rb_root *dev_cache,
4831 struct btrfs_key *key, struct extent_buffer *eb, int slot)
4833 struct btrfs_dev_item *ptr;
4834 struct device_record *rec;
4837 ptr = btrfs_item_ptr(eb,
4838 slot, struct btrfs_dev_item);
4840 rec = malloc(sizeof(*rec));
4842 fprintf(stderr, "memory allocation failed\n");
4846 rec->devid = key->offset;
4847 rec->generation = btrfs_header_generation(eb);
4849 rec->objectid = key->objectid;
4850 rec->type = key->type;
4851 rec->offset = key->offset;
4853 rec->devid = btrfs_device_id(eb, ptr);
4854 rec->total_byte = btrfs_device_total_bytes(eb, ptr);
4855 rec->byte_used = btrfs_device_bytes_used(eb, ptr);
4857 ret = rb_insert(dev_cache, &rec->node, device_record_compare);
4859 fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
4866 struct block_group_record *
4867 btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,
4870 struct btrfs_block_group_item *ptr;
4871 struct block_group_record *rec;
4873 rec = calloc(1, sizeof(*rec));
4875 fprintf(stderr, "memory allocation failed\n");
4879 rec->cache.start = key->objectid;
4880 rec->cache.size = key->offset;
4882 rec->generation = btrfs_header_generation(leaf);
4884 rec->objectid = key->objectid;
4885 rec->type = key->type;
4886 rec->offset = key->offset;
4888 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_block_group_item);
4889 rec->flags = btrfs_disk_block_group_flags(leaf, ptr);
4891 INIT_LIST_HEAD(&rec->list);
4896 static int process_block_group_item(struct block_group_tree *block_group_cache,
4897 struct btrfs_key *key,
4898 struct extent_buffer *eb, int slot)
4900 struct block_group_record *rec;
4903 rec = btrfs_new_block_group_record(eb, key, slot);
4904 ret = insert_block_group_record(block_group_cache, rec);
4906 fprintf(stderr, "Block Group[%llu, %llu] existed.\n",
4907 rec->objectid, rec->offset);
4914 struct device_extent_record *
4915 btrfs_new_device_extent_record(struct extent_buffer *leaf,
4916 struct btrfs_key *key, int slot)
4918 struct device_extent_record *rec;
4919 struct btrfs_dev_extent *ptr;
4921 rec = calloc(1, sizeof(*rec));
4923 fprintf(stderr, "memory allocation failed\n");
4927 rec->cache.objectid = key->objectid;
4928 rec->cache.start = key->offset;
4930 rec->generation = btrfs_header_generation(leaf);
4932 rec->objectid = key->objectid;
4933 rec->type = key->type;
4934 rec->offset = key->offset;
4936 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
4937 rec->chunk_objecteid =
4938 btrfs_dev_extent_chunk_objectid(leaf, ptr);
4940 btrfs_dev_extent_chunk_offset(leaf, ptr);
4941 rec->length = btrfs_dev_extent_length(leaf, ptr);
4942 rec->cache.size = rec->length;
4944 INIT_LIST_HEAD(&rec->chunk_list);
4945 INIT_LIST_HEAD(&rec->device_list);
4951 process_device_extent_item(struct device_extent_tree *dev_extent_cache,
4952 struct btrfs_key *key, struct extent_buffer *eb,
4955 struct device_extent_record *rec;
4958 rec = btrfs_new_device_extent_record(eb, key, slot);
4959 ret = insert_device_extent_record(dev_extent_cache, rec);
4962 "Device extent[%llu, %llu, %llu] existed.\n",
4963 rec->objectid, rec->offset, rec->length);
4970 static int process_extent_item(struct btrfs_root *root,
4971 struct cache_tree *extent_cache,
4972 struct extent_buffer *eb, int slot)
4974 struct btrfs_extent_item *ei;
4975 struct btrfs_extent_inline_ref *iref;
4976 struct btrfs_extent_data_ref *dref;
4977 struct btrfs_shared_data_ref *sref;
4978 struct btrfs_key key;
4979 struct extent_record tmpl;
4984 u32 item_size = btrfs_item_size_nr(eb, slot);
4990 btrfs_item_key_to_cpu(eb, &key, slot);
4992 if (key.type == BTRFS_METADATA_ITEM_KEY) {
4994 num_bytes = root->fs_info->nodesize;
4996 num_bytes = key.offset;
4999 if (!IS_ALIGNED(key.objectid, root->fs_info->sectorsize)) {
5000 error("ignoring invalid extent, bytenr %llu is not aligned to %u",
5001 key.objectid, root->fs_info->sectorsize);
5004 if (item_size < sizeof(*ei)) {
5005 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5006 struct btrfs_extent_item_v0 *ei0;
5008 if (item_size != sizeof(*ei0)) {
5010 "invalid extent item format: ITEM[%llu %u %llu] leaf: %llu slot: %d",
5011 key.objectid, key.type, key.offset,
5012 btrfs_header_bytenr(eb), slot);
5015 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
5016 refs = btrfs_extent_refs_v0(eb, ei0);
5020 memset(&tmpl, 0, sizeof(tmpl));
5021 tmpl.start = key.objectid;
5022 tmpl.nr = num_bytes;
5023 tmpl.extent_item_refs = refs;
5024 tmpl.metadata = metadata;
5026 tmpl.max_size = num_bytes;
5028 return add_extent_rec(extent_cache, &tmpl);
5031 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
5032 refs = btrfs_extent_refs(eb, ei);
5033 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
5037 if (metadata && num_bytes != root->fs_info->nodesize) {
5038 error("ignore invalid metadata extent, length %llu does not equal to %u",
5039 num_bytes, root->fs_info->nodesize);
5042 if (!metadata && !IS_ALIGNED(num_bytes, root->fs_info->sectorsize)) {
5043 error("ignore invalid data extent, length %llu is not aligned to %u",
5044 num_bytes, root->fs_info->sectorsize);
5048 memset(&tmpl, 0, sizeof(tmpl));
5049 tmpl.start = key.objectid;
5050 tmpl.nr = num_bytes;
5051 tmpl.extent_item_refs = refs;
5052 tmpl.metadata = metadata;
5054 tmpl.max_size = num_bytes;
5055 add_extent_rec(extent_cache, &tmpl);
5057 ptr = (unsigned long)(ei + 1);
5058 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
5059 key.type == BTRFS_EXTENT_ITEM_KEY)
5060 ptr += sizeof(struct btrfs_tree_block_info);
5062 end = (unsigned long)ei + item_size;
5064 iref = (struct btrfs_extent_inline_ref *)ptr;
5065 type = btrfs_extent_inline_ref_type(eb, iref);
5066 offset = btrfs_extent_inline_ref_offset(eb, iref);
5068 case BTRFS_TREE_BLOCK_REF_KEY:
5069 ret = add_tree_backref(extent_cache, key.objectid,
5073 "add_tree_backref failed (extent items tree block): %s",
5076 case BTRFS_SHARED_BLOCK_REF_KEY:
5077 ret = add_tree_backref(extent_cache, key.objectid,
5081 "add_tree_backref failed (extent items shared block): %s",
5084 case BTRFS_EXTENT_DATA_REF_KEY:
5085 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
5086 add_data_backref(extent_cache, key.objectid, 0,
5087 btrfs_extent_data_ref_root(eb, dref),
5088 btrfs_extent_data_ref_objectid(eb,
5090 btrfs_extent_data_ref_offset(eb, dref),
5091 btrfs_extent_data_ref_count(eb, dref),
5094 case BTRFS_SHARED_DATA_REF_KEY:
5095 sref = (struct btrfs_shared_data_ref *)(iref + 1);
5096 add_data_backref(extent_cache, key.objectid, offset,
5098 btrfs_shared_data_ref_count(eb, sref),
5103 "corrupt extent record: key [%llu,%u,%llu]\n",
5104 key.objectid, key.type, num_bytes);
5107 ptr += btrfs_extent_inline_ref_size(type);
5114 static int check_cache_range(struct btrfs_root *root,
5115 struct btrfs_block_group_cache *cache,
5116 u64 offset, u64 bytes)
5118 struct btrfs_free_space *entry;
5124 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
5125 bytenr = btrfs_sb_offset(i);
5126 ret = btrfs_rmap_block(root->fs_info,
5127 cache->key.objectid, bytenr, 0,
5128 &logical, &nr, &stripe_len);
5133 if (logical[nr] + stripe_len <= offset)
5135 if (offset + bytes <= logical[nr])
5137 if (logical[nr] == offset) {
5138 if (stripe_len >= bytes) {
5142 bytes -= stripe_len;
5143 offset += stripe_len;
5144 } else if (logical[nr] < offset) {
5145 if (logical[nr] + stripe_len >=
5150 bytes = (offset + bytes) -
5151 (logical[nr] + stripe_len);
5152 offset = logical[nr] + stripe_len;
5155 * Could be tricky, the super may land in the
5156 * middle of the area we're checking. First
5157 * check the easiest case, it's at the end.
5159 if (logical[nr] + stripe_len >=
5161 bytes = logical[nr] - offset;
5165 /* Check the left side */
5166 ret = check_cache_range(root, cache,
5168 logical[nr] - offset);
5174 /* Now we continue with the right side */
5175 bytes = (offset + bytes) -
5176 (logical[nr] + stripe_len);
5177 offset = logical[nr] + stripe_len;
5184 entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes);
5186 fprintf(stderr, "there is no free space entry for %llu-%llu\n",
5187 offset, offset+bytes);
5191 if (entry->offset != offset) {
5192 fprintf(stderr, "wanted offset %llu, found %llu\n", offset,
5197 if (entry->bytes != bytes) {
5198 fprintf(stderr, "wanted bytes %llu, found %llu for off %llu\n",
5199 bytes, entry->bytes, offset);
5203 unlink_free_space(cache->free_space_ctl, entry);
5208 static int verify_space_cache(struct btrfs_root *root,
5209 struct btrfs_block_group_cache *cache)
5211 struct btrfs_path path;
5212 struct extent_buffer *leaf;
5213 struct btrfs_key key;
5217 root = root->fs_info->extent_root;
5219 last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
5221 btrfs_init_path(&path);
5222 key.objectid = last;
5224 key.type = BTRFS_EXTENT_ITEM_KEY;
5225 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
5230 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5231 ret = btrfs_next_leaf(root, &path);
5239 leaf = path.nodes[0];
5240 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5241 if (key.objectid >= cache->key.offset + cache->key.objectid)
5243 if (key.type != BTRFS_EXTENT_ITEM_KEY &&
5244 key.type != BTRFS_METADATA_ITEM_KEY) {
5249 if (last == key.objectid) {
5250 if (key.type == BTRFS_EXTENT_ITEM_KEY)
5251 last = key.objectid + key.offset;
5253 last = key.objectid + root->fs_info->nodesize;
5258 ret = check_cache_range(root, cache, last,
5259 key.objectid - last);
5262 if (key.type == BTRFS_EXTENT_ITEM_KEY)
5263 last = key.objectid + key.offset;
5265 last = key.objectid + root->fs_info->nodesize;
5269 if (last < cache->key.objectid + cache->key.offset)
5270 ret = check_cache_range(root, cache, last,
5271 cache->key.objectid +
5272 cache->key.offset - last);
5275 btrfs_release_path(&path);
5278 !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) {
5279 fprintf(stderr, "There are still entries left in the space "
5287 static int check_space_cache(struct btrfs_root *root)
5289 struct btrfs_block_group_cache *cache;
5290 u64 start = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
5294 if (btrfs_super_cache_generation(root->fs_info->super_copy) != -1ULL &&
5295 btrfs_super_generation(root->fs_info->super_copy) !=
5296 btrfs_super_cache_generation(root->fs_info->super_copy)) {
5297 printf("cache and super generation don't match, space cache "
5298 "will be invalidated\n");
5302 if (ctx.progress_enabled) {
5303 ctx.tp = TASK_FREE_SPACE;
5304 task_start(ctx.info);
5308 cache = btrfs_lookup_first_block_group(root->fs_info, start);
5312 start = cache->key.objectid + cache->key.offset;
5313 if (!cache->free_space_ctl) {
5314 if (btrfs_init_free_space_ctl(cache,
5315 root->fs_info->sectorsize)) {
5320 btrfs_remove_free_space_cache(cache);
5323 if (btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE)) {
5324 ret = exclude_super_stripes(root, cache);
5326 fprintf(stderr, "could not exclude super stripes: %s\n",
5331 ret = load_free_space_tree(root->fs_info, cache);
5332 free_excluded_extents(root, cache);
5334 fprintf(stderr, "could not load free space tree: %s\n",
5341 ret = load_free_space_cache(root->fs_info, cache);
5346 ret = verify_space_cache(root, cache);
5348 fprintf(stderr, "cache appears valid but isn't %llu\n",
5349 cache->key.objectid);
5354 task_stop(ctx.info);
5356 return error ? -EINVAL : 0;
5359 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
5360 u64 num_bytes, unsigned long leaf_offset,
5361 struct extent_buffer *eb)
5363 struct btrfs_fs_info *fs_info = root->fs_info;
5365 u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
5367 unsigned long csum_offset;
5371 u64 data_checked = 0;
5377 if (num_bytes % fs_info->sectorsize)
5380 data = malloc(num_bytes);
5384 while (offset < num_bytes) {
5387 read_len = num_bytes - offset;
5388 /* read as much space once a time */
5389 ret = read_extent_data(fs_info, data + offset,
5390 bytenr + offset, &read_len, mirror);
5394 /* verify every 4k data's checksum */
5395 while (data_checked < read_len) {
5397 tmp = offset + data_checked;
5399 csum = btrfs_csum_data((char *)data + tmp,
5400 csum, fs_info->sectorsize);
5401 btrfs_csum_final(csum, (u8 *)&csum);
5403 csum_offset = leaf_offset +
5404 tmp / fs_info->sectorsize * csum_size;
5405 read_extent_buffer(eb, (char *)&csum_expected,
5406 csum_offset, csum_size);
5407 /* try another mirror */
5408 if (csum != csum_expected) {
5409 fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
5410 mirror, bytenr + tmp,
5411 csum, csum_expected);
5412 num_copies = btrfs_num_copies(root->fs_info,
5414 if (mirror < num_copies - 1) {
5419 data_checked += fs_info->sectorsize;
5428 static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
5431 struct btrfs_path path;
5432 struct extent_buffer *leaf;
5433 struct btrfs_key key;
5436 btrfs_init_path(&path);
5437 key.objectid = bytenr;
5438 key.type = BTRFS_EXTENT_ITEM_KEY;
5439 key.offset = (u64)-1;
5442 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
5445 fprintf(stderr, "Error looking up extent record %d\n", ret);
5446 btrfs_release_path(&path);
5449 if (path.slots[0] > 0) {
5452 ret = btrfs_prev_leaf(root, &path);
5455 } else if (ret > 0) {
5462 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5465 * Block group items come before extent items if they have the same
5466 * bytenr, so walk back one more just in case. Dear future traveller,
5467 * first congrats on mastering time travel. Now if it's not too much
5468 * trouble could you go back to 2006 and tell Chris to make the
5469 * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
5470 * EXTENT_ITEM_KEY please?
5472 while (key.type > BTRFS_EXTENT_ITEM_KEY) {
5473 if (path.slots[0] > 0) {
5476 ret = btrfs_prev_leaf(root, &path);
5479 } else if (ret > 0) {
5484 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5488 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5489 ret = btrfs_next_leaf(root, &path);
5491 fprintf(stderr, "Error going to next leaf "
5493 btrfs_release_path(&path);
5499 leaf = path.nodes[0];
5500 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5501 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
5505 if (key.objectid + key.offset < bytenr) {
5509 if (key.objectid > bytenr + num_bytes)
5512 if (key.objectid == bytenr) {
5513 if (key.offset >= num_bytes) {
5517 num_bytes -= key.offset;
5518 bytenr += key.offset;
5519 } else if (key.objectid < bytenr) {
5520 if (key.objectid + key.offset >= bytenr + num_bytes) {
5524 num_bytes = (bytenr + num_bytes) -
5525 (key.objectid + key.offset);
5526 bytenr = key.objectid + key.offset;
5528 if (key.objectid + key.offset < bytenr + num_bytes) {
5529 u64 new_start = key.objectid + key.offset;
5530 u64 new_bytes = bytenr + num_bytes - new_start;
5533 * Weird case, the extent is in the middle of
5534 * our range, we'll have to search one side
5535 * and then the other. Not sure if this happens
5536 * in real life, but no harm in coding it up
5537 * anyway just in case.
5539 btrfs_release_path(&path);
5540 ret = check_extent_exists(root, new_start,
5543 fprintf(stderr, "Right section didn't "
5547 num_bytes = key.objectid - bytenr;
5550 num_bytes = key.objectid - bytenr;
5557 if (num_bytes && !ret) {
5559 "there are no extents for csum range %llu-%llu\n",
5560 bytenr, bytenr+num_bytes);
5564 btrfs_release_path(&path);
5568 static int check_csums(struct btrfs_root *root)
5570 struct btrfs_path path;
5571 struct extent_buffer *leaf;
5572 struct btrfs_key key;
5573 u64 offset = 0, num_bytes = 0;
5574 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
5578 unsigned long leaf_offset;
5580 root = root->fs_info->csum_root;
5581 if (!extent_buffer_uptodate(root->node)) {
5582 fprintf(stderr, "No valid csum tree found\n");
5586 btrfs_init_path(&path);
5587 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
5588 key.type = BTRFS_EXTENT_CSUM_KEY;
5590 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
5592 fprintf(stderr, "Error searching csum tree %d\n", ret);
5593 btrfs_release_path(&path);
5597 if (ret > 0 && path.slots[0])
5602 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5603 ret = btrfs_next_leaf(root, &path);
5605 fprintf(stderr, "Error going to next leaf "
5612 leaf = path.nodes[0];
5614 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5615 if (key.type != BTRFS_EXTENT_CSUM_KEY) {
5620 data_len = (btrfs_item_size_nr(leaf, path.slots[0]) /
5621 csum_size) * root->fs_info->sectorsize;
5622 if (!check_data_csum)
5623 goto skip_csum_check;
5624 leaf_offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
5625 ret = check_extent_csums(root, key.offset, data_len,
5631 offset = key.offset;
5632 } else if (key.offset != offset + num_bytes) {
5633 ret = check_extent_exists(root, offset, num_bytes);
5636 "csum exists for %llu-%llu but there is no extent record\n",
5637 offset, offset+num_bytes);
5640 offset = key.offset;
5643 num_bytes += data_len;
5647 btrfs_release_path(&path);
5651 static int is_dropped_key(struct btrfs_key *key,
5652 struct btrfs_key *drop_key)
5654 if (key->objectid < drop_key->objectid)
5656 else if (key->objectid == drop_key->objectid) {
5657 if (key->type < drop_key->type)
5659 else if (key->type == drop_key->type) {
5660 if (key->offset < drop_key->offset)
5668 * Here are the rules for FULL_BACKREF.
5670 * 1) If BTRFS_HEADER_FLAG_RELOC is set then we have FULL_BACKREF set.
5671 * 2) If btrfs_header_owner(buf) no longer points to buf then we have
5673 * 3) We cowed the block walking down a reloc tree. This is impossible to tell
5674 * if it happened after the relocation occurred since we'll have dropped the
5675 * reloc root, so it's entirely possible to have FULL_BACKREF set on buf and
5676 * have no real way to know for sure.
5678 * We process the blocks one root at a time, and we start from the lowest root
5679 * objectid and go to the highest. So we can just lookup the owner backref for
5680 * the record and if we don't find it then we know it doesn't exist and we have
5683 * FIXME: if we ever start reclaiming root objectid's then we need to fix this
5684 * assumption and simply indicate that we _think_ that the FULL BACKREF needs to
5685 * be set or not and then we can check later once we've gathered all the refs.
5687 static int calc_extent_flag(struct cache_tree *extent_cache,
5688 struct extent_buffer *buf,
5689 struct root_item_record *ri,
5692 struct extent_record *rec;
5693 struct cache_extent *cache;
5694 struct tree_backref *tback;
5697 cache = lookup_cache_extent(extent_cache, buf->start, 1);
5698 /* we have added this extent before */
5702 rec = container_of(cache, struct extent_record, cache);
5705 * Except file/reloc tree, we can not have
5708 if (ri->objectid < BTRFS_FIRST_FREE_OBJECTID)
5713 if (buf->start == ri->bytenr)
5716 if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
5719 owner = btrfs_header_owner(buf);
5720 if (owner == ri->objectid)
5723 tback = find_tree_backref(rec, 0, owner);
5728 if (rec->flag_block_full_backref != FLAG_UNSET &&
5729 rec->flag_block_full_backref != 0)
5730 rec->bad_full_backref = 1;
5733 *flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5734 if (rec->flag_block_full_backref != FLAG_UNSET &&
5735 rec->flag_block_full_backref != 1)
5736 rec->bad_full_backref = 1;
5740 static void report_mismatch_key_root(u8 key_type, u64 rootid)
5742 fprintf(stderr, "Invalid key type(");
5743 print_key_type(stderr, 0, key_type);
5744 fprintf(stderr, ") found in root(");
5745 print_objectid(stderr, rootid, 0);
5746 fprintf(stderr, ")\n");
5750 * Check if the key is valid with its extent buffer.
5752 * This is a early check in case invalid key exists in a extent buffer
5753 * This is not comprehensive yet, but should prevent wrong key/item passed
5756 static int check_type_with_root(u64 rootid, u8 key_type)
5759 /* Only valid in chunk tree */
5760 case BTRFS_DEV_ITEM_KEY:
5761 case BTRFS_CHUNK_ITEM_KEY:
5762 if (rootid != BTRFS_CHUNK_TREE_OBJECTID)
5765 /* valid in csum and log tree */
5766 case BTRFS_CSUM_TREE_OBJECTID:
5767 if (!(rootid == BTRFS_TREE_LOG_OBJECTID ||
5771 case BTRFS_EXTENT_ITEM_KEY:
5772 case BTRFS_METADATA_ITEM_KEY:
5773 case BTRFS_BLOCK_GROUP_ITEM_KEY:
5774 if (rootid != BTRFS_EXTENT_TREE_OBJECTID)
5777 case BTRFS_ROOT_ITEM_KEY:
5778 if (rootid != BTRFS_ROOT_TREE_OBJECTID)
5781 case BTRFS_DEV_EXTENT_KEY:
5782 if (rootid != BTRFS_DEV_TREE_OBJECTID)
5788 report_mismatch_key_root(key_type, rootid);
5792 static int run_next_block(struct btrfs_root *root,
5793 struct block_info *bits,
5796 struct cache_tree *pending,
5797 struct cache_tree *seen,
5798 struct cache_tree *reada,
5799 struct cache_tree *nodes,
5800 struct cache_tree *extent_cache,
5801 struct cache_tree *chunk_cache,
5802 struct rb_root *dev_cache,
5803 struct block_group_tree *block_group_cache,
5804 struct device_extent_tree *dev_extent_cache,
5805 struct root_item_record *ri)
5807 struct btrfs_fs_info *fs_info = root->fs_info;
5808 struct extent_buffer *buf;
5809 struct extent_record *rec = NULL;
5820 struct btrfs_key key;
5821 struct cache_extent *cache;
5824 nritems = pick_next_pending(pending, reada, nodes, *last, bits,
5825 bits_nr, &reada_bits);
5830 for (i = 0; i < nritems; i++) {
5831 ret = add_cache_extent(reada, bits[i].start,
5836 /* fixme, get the parent transid */
5837 readahead_tree_block(fs_info, bits[i].start, 0);
5840 *last = bits[0].start;
5841 bytenr = bits[0].start;
5842 size = bits[0].size;
5844 cache = lookup_cache_extent(pending, bytenr, size);
5846 remove_cache_extent(pending, cache);
5849 cache = lookup_cache_extent(reada, bytenr, size);
5851 remove_cache_extent(reada, cache);
5854 cache = lookup_cache_extent(nodes, bytenr, size);
5856 remove_cache_extent(nodes, cache);
5859 cache = lookup_cache_extent(extent_cache, bytenr, size);
5861 rec = container_of(cache, struct extent_record, cache);
5862 gen = rec->parent_generation;
5865 /* fixme, get the real parent transid */
5866 buf = read_tree_block(root->fs_info, bytenr, gen);
5867 if (!extent_buffer_uptodate(buf)) {
5868 record_bad_block_io(root->fs_info,
5869 extent_cache, bytenr, size);
5873 nritems = btrfs_header_nritems(buf);
5876 if (!init_extent_tree) {
5877 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
5878 btrfs_header_level(buf), 1, NULL,
5881 ret = calc_extent_flag(extent_cache, buf, ri, &flags);
5883 fprintf(stderr, "Couldn't calc extent flags\n");
5884 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5889 ret = calc_extent_flag(extent_cache, buf, ri, &flags);
5891 fprintf(stderr, "Couldn't calc extent flags\n");
5892 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5896 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5898 ri->objectid != BTRFS_TREE_RELOC_OBJECTID &&
5899 ri->objectid == btrfs_header_owner(buf)) {
5901 * Ok we got to this block from it's original owner and
5902 * we have FULL_BACKREF set. Relocation can leave
5903 * converted blocks over so this is altogether possible,
5904 * however it's not possible if the generation > the
5905 * last snapshot, so check for this case.
5907 if (!btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC) &&
5908 btrfs_header_generation(buf) > ri->last_snapshot) {
5909 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
5910 rec->bad_full_backref = 1;
5915 (ri->objectid == BTRFS_TREE_RELOC_OBJECTID ||
5916 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) {
5917 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5918 rec->bad_full_backref = 1;
5922 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5923 rec->flag_block_full_backref = 1;
5927 rec->flag_block_full_backref = 0;
5929 owner = btrfs_header_owner(buf);
5932 ret = check_block(root, extent_cache, buf, flags);
5936 if (btrfs_is_leaf(buf)) {
5937 btree_space_waste += btrfs_leaf_free_space(root, buf);
5938 for (i = 0; i < nritems; i++) {
5939 struct btrfs_file_extent_item *fi;
5941 btrfs_item_key_to_cpu(buf, &key, i);
5943 * Check key type against the leaf owner.
5944 * Could filter quite a lot of early error if
5947 if (check_type_with_root(btrfs_header_owner(buf),
5949 fprintf(stderr, "ignoring invalid key\n");
5952 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
5953 process_extent_item(root, extent_cache, buf,
5957 if (key.type == BTRFS_METADATA_ITEM_KEY) {
5958 process_extent_item(root, extent_cache, buf,
5962 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
5964 btrfs_item_size_nr(buf, i);
5967 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
5968 process_chunk_item(chunk_cache, &key, buf, i);
5971 if (key.type == BTRFS_DEV_ITEM_KEY) {
5972 process_device_item(dev_cache, &key, buf, i);
5975 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
5976 process_block_group_item(block_group_cache,
5980 if (key.type == BTRFS_DEV_EXTENT_KEY) {
5981 process_device_extent_item(dev_extent_cache,
5986 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
5987 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5988 process_extent_ref_v0(extent_cache, buf, i);
5995 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
5996 ret = add_tree_backref(extent_cache,
5997 key.objectid, 0, key.offset, 0);
6000 "add_tree_backref failed (leaf tree block): %s",
6004 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
6005 ret = add_tree_backref(extent_cache,
6006 key.objectid, key.offset, 0, 0);
6009 "add_tree_backref failed (leaf shared block): %s",
6013 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
6014 struct btrfs_extent_data_ref *ref;
6016 ref = btrfs_item_ptr(buf, i,
6017 struct btrfs_extent_data_ref);
6018 add_data_backref(extent_cache,
6020 btrfs_extent_data_ref_root(buf, ref),
6021 btrfs_extent_data_ref_objectid(buf,
6023 btrfs_extent_data_ref_offset(buf, ref),
6024 btrfs_extent_data_ref_count(buf, ref),
6025 0, root->fs_info->sectorsize);
6028 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
6029 struct btrfs_shared_data_ref *ref;
6031 ref = btrfs_item_ptr(buf, i,
6032 struct btrfs_shared_data_ref);
6033 add_data_backref(extent_cache,
6034 key.objectid, key.offset, 0, 0, 0,
6035 btrfs_shared_data_ref_count(buf, ref),
6036 0, root->fs_info->sectorsize);
6039 if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
6040 struct bad_item *bad;
6042 if (key.objectid == BTRFS_ORPHAN_OBJECTID)
6046 bad = malloc(sizeof(struct bad_item));
6049 INIT_LIST_HEAD(&bad->list);
6050 memcpy(&bad->key, &key,
6051 sizeof(struct btrfs_key));
6052 bad->root_id = owner;
6053 list_add_tail(&bad->list, &delete_items);
6056 if (key.type != BTRFS_EXTENT_DATA_KEY)
6058 fi = btrfs_item_ptr(buf, i,
6059 struct btrfs_file_extent_item);
6060 if (btrfs_file_extent_type(buf, fi) ==
6061 BTRFS_FILE_EXTENT_INLINE)
6063 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
6066 data_bytes_allocated +=
6067 btrfs_file_extent_disk_num_bytes(buf, fi);
6068 if (data_bytes_allocated < root->fs_info->sectorsize)
6071 data_bytes_referenced +=
6072 btrfs_file_extent_num_bytes(buf, fi);
6073 add_data_backref(extent_cache,
6074 btrfs_file_extent_disk_bytenr(buf, fi),
6075 parent, owner, key.objectid, key.offset -
6076 btrfs_file_extent_offset(buf, fi), 1, 1,
6077 btrfs_file_extent_disk_num_bytes(buf, fi));
6081 struct btrfs_key first_key;
6083 first_key.objectid = 0;
6086 btrfs_item_key_to_cpu(buf, &first_key, 0);
6087 level = btrfs_header_level(buf);
6088 for (i = 0; i < nritems; i++) {
6089 struct extent_record tmpl;
6091 ptr = btrfs_node_blockptr(buf, i);
6092 size = root->fs_info->nodesize;
6093 btrfs_node_key_to_cpu(buf, &key, i);
6095 if ((level == ri->drop_level)
6096 && is_dropped_key(&key, &ri->drop_key)) {
6101 memset(&tmpl, 0, sizeof(tmpl));
6102 btrfs_cpu_key_to_disk(&tmpl.parent_key, &key);
6103 tmpl.parent_generation =
6104 btrfs_node_ptr_generation(buf, i);
6109 tmpl.max_size = size;
6110 ret = add_extent_rec(extent_cache, &tmpl);
6114 ret = add_tree_backref(extent_cache, ptr, parent,
6118 "add_tree_backref failed (non-leaf block): %s",
6124 add_pending(nodes, seen, ptr, size);
6126 add_pending(pending, seen, ptr, size);
6128 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(fs_info) -
6129 nritems) * sizeof(struct btrfs_key_ptr);
6131 total_btree_bytes += buf->len;
6132 if (fs_root_objectid(btrfs_header_owner(buf)))
6133 total_fs_tree_bytes += buf->len;
6134 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
6135 total_extent_tree_bytes += buf->len;
6137 free_extent_buffer(buf);
6141 static int add_root_to_pending(struct extent_buffer *buf,
6142 struct cache_tree *extent_cache,
6143 struct cache_tree *pending,
6144 struct cache_tree *seen,
6145 struct cache_tree *nodes,
6148 struct extent_record tmpl;
6151 if (btrfs_header_level(buf) > 0)
6152 add_pending(nodes, seen, buf->start, buf->len);
6154 add_pending(pending, seen, buf->start, buf->len);
6156 memset(&tmpl, 0, sizeof(tmpl));
6157 tmpl.start = buf->start;
6162 tmpl.max_size = buf->len;
6163 add_extent_rec(extent_cache, &tmpl);
6165 if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
6166 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
6167 ret = add_tree_backref(extent_cache, buf->start, buf->start,
6170 ret = add_tree_backref(extent_cache, buf->start, 0, objectid,
6175 /* as we fix the tree, we might be deleting blocks that
6176 * we're tracking for repair. This hook makes sure we
6177 * remove any backrefs for blocks as we are fixing them.
6179 static int free_extent_hook(struct btrfs_trans_handle *trans,
6180 struct btrfs_root *root,
6181 u64 bytenr, u64 num_bytes, u64 parent,
6182 u64 root_objectid, u64 owner, u64 offset,
6185 struct extent_record *rec;
6186 struct cache_extent *cache;
6188 struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
6190 is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
6191 cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
6195 rec = container_of(cache, struct extent_record, cache);
6197 struct data_backref *back;
6199 back = find_data_backref(rec, parent, root_objectid, owner,
6200 offset, 1, bytenr, num_bytes);
6203 if (back->node.found_ref) {
6204 back->found_ref -= refs_to_drop;
6206 rec->refs -= refs_to_drop;
6208 if (back->node.found_extent_tree) {
6209 back->num_refs -= refs_to_drop;
6210 if (rec->extent_item_refs)
6211 rec->extent_item_refs -= refs_to_drop;
6213 if (back->found_ref == 0)
6214 back->node.found_ref = 0;
6215 if (back->num_refs == 0)
6216 back->node.found_extent_tree = 0;
6218 if (!back->node.found_extent_tree && back->node.found_ref) {
6219 rb_erase(&back->node.node, &rec->backref_tree);
6223 struct tree_backref *back;
6225 back = find_tree_backref(rec, parent, root_objectid);
6228 if (back->node.found_ref) {
6231 back->node.found_ref = 0;
6233 if (back->node.found_extent_tree) {
6234 if (rec->extent_item_refs)
6235 rec->extent_item_refs--;
6236 back->node.found_extent_tree = 0;
6238 if (!back->node.found_extent_tree && back->node.found_ref) {
6239 rb_erase(&back->node.node, &rec->backref_tree);
6243 maybe_free_extent_rec(extent_cache, rec);
6248 static int delete_extent_records(struct btrfs_trans_handle *trans,
6249 struct btrfs_root *root,
6250 struct btrfs_path *path,
6253 struct btrfs_key key;
6254 struct btrfs_key found_key;
6255 struct extent_buffer *leaf;
6260 key.objectid = bytenr;
6262 key.offset = (u64)-1;
6265 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
6272 if (path->slots[0] == 0)
6278 leaf = path->nodes[0];
6279 slot = path->slots[0];
6281 btrfs_item_key_to_cpu(leaf, &found_key, slot);
6282 if (found_key.objectid != bytenr)
6285 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
6286 found_key.type != BTRFS_METADATA_ITEM_KEY &&
6287 found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
6288 found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
6289 found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
6290 found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
6291 found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
6292 btrfs_release_path(path);
6293 if (found_key.type == 0) {
6294 if (found_key.offset == 0)
6296 key.offset = found_key.offset - 1;
6297 key.type = found_key.type;
6299 key.type = found_key.type - 1;
6300 key.offset = (u64)-1;
6305 "repair deleting extent record: key [%llu,%u,%llu]\n",
6306 found_key.objectid, found_key.type, found_key.offset);
6308 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
6311 btrfs_release_path(path);
6313 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
6314 found_key.type == BTRFS_METADATA_ITEM_KEY) {
6315 u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
6316 found_key.offset : root->fs_info->nodesize;
6318 ret = btrfs_update_block_group(root, bytenr,
6325 btrfs_release_path(path);
6330 * for a single backref, this will allocate a new extent
6331 * and add the backref to it.
6333 static int record_extent(struct btrfs_trans_handle *trans,
6334 struct btrfs_fs_info *info,
6335 struct btrfs_path *path,
6336 struct extent_record *rec,
6337 struct extent_backref *back,
6338 int allocated, u64 flags)
6341 struct btrfs_root *extent_root = info->extent_root;
6342 struct extent_buffer *leaf;
6343 struct btrfs_key ins_key;
6344 struct btrfs_extent_item *ei;
6345 struct data_backref *dback;
6346 struct btrfs_tree_block_info *bi;
6349 rec->max_size = max_t(u64, rec->max_size,
6353 u32 item_size = sizeof(*ei);
6356 item_size += sizeof(*bi);
6358 ins_key.objectid = rec->start;
6359 ins_key.offset = rec->max_size;
6360 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
6362 ret = btrfs_insert_empty_item(trans, extent_root, path,
6363 &ins_key, item_size);
6367 leaf = path->nodes[0];
6368 ei = btrfs_item_ptr(leaf, path->slots[0],
6369 struct btrfs_extent_item);
6371 btrfs_set_extent_refs(leaf, ei, 0);
6372 btrfs_set_extent_generation(leaf, ei, rec->generation);
6374 if (back->is_data) {
6375 btrfs_set_extent_flags(leaf, ei,
6376 BTRFS_EXTENT_FLAG_DATA);
6378 struct btrfs_disk_key copy_key;
6380 bi = (struct btrfs_tree_block_info *)(ei + 1);
6381 memset_extent_buffer(leaf, 0, (unsigned long)bi,
6384 btrfs_set_disk_key_objectid(©_key,
6385 rec->info_objectid);
6386 btrfs_set_disk_key_type(©_key, 0);
6387 btrfs_set_disk_key_offset(©_key, 0);
6389 btrfs_set_tree_block_level(leaf, bi, rec->info_level);
6390 btrfs_set_tree_block_key(leaf, bi, ©_key);
6392 btrfs_set_extent_flags(leaf, ei,
6393 flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
6396 btrfs_mark_buffer_dirty(leaf);
6397 ret = btrfs_update_block_group(extent_root, rec->start,
6398 rec->max_size, 1, 0);
6401 btrfs_release_path(path);
6404 if (back->is_data) {
6408 dback = to_data_backref(back);
6409 if (back->full_backref)
6410 parent = dback->parent;
6414 for (i = 0; i < dback->found_ref; i++) {
6415 /* if parent != 0, we're doing a full backref
6416 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
6417 * just makes the backref allocator create a data
6420 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6421 rec->start, rec->max_size,
6425 BTRFS_FIRST_FREE_OBJECTID :
6432 "adding new data backref on %llu %s %llu owner %llu offset %llu found %d\n",
6433 (unsigned long long)rec->start,
6434 back->full_backref ? "parent" : "root",
6435 back->full_backref ? (unsigned long long)parent :
6436 (unsigned long long)dback->root,
6437 (unsigned long long)dback->owner,
6438 (unsigned long long)dback->offset, dback->found_ref);
6441 struct tree_backref *tback;
6443 tback = to_tree_backref(back);
6444 if (back->full_backref)
6445 parent = tback->parent;
6449 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6450 rec->start, rec->max_size,
6451 parent, tback->root, 0, 0);
6453 "adding new tree backref on start %llu len %llu parent %llu root %llu\n",
6454 rec->start, rec->max_size, parent, tback->root);
6457 btrfs_release_path(path);
6461 static struct extent_entry *find_entry(struct list_head *entries,
6462 u64 bytenr, u64 bytes)
6464 struct extent_entry *entry = NULL;
6466 list_for_each_entry(entry, entries, list) {
6467 if (entry->bytenr == bytenr && entry->bytes == bytes)
6474 static struct extent_entry *find_most_right_entry(struct list_head *entries)
6476 struct extent_entry *entry, *best = NULL, *prev = NULL;
6478 list_for_each_entry(entry, entries, list) {
6480 * If there are as many broken entries as entries then we know
6481 * not to trust this particular entry.
6483 if (entry->broken == entry->count)
6487 * Special case, when there are only two entries and 'best' is
6497 * If our current entry == best then we can't be sure our best
6498 * is really the best, so we need to keep searching.
6500 if (best && best->count == entry->count) {
6506 /* Prev == entry, not good enough, have to keep searching */
6507 if (!prev->broken && prev->count == entry->count)
6511 best = (prev->count > entry->count) ? prev : entry;
6512 else if (best->count < entry->count)
6520 static int repair_ref(struct btrfs_fs_info *info, struct btrfs_path *path,
6521 struct data_backref *dback, struct extent_entry *entry)
6523 struct btrfs_trans_handle *trans;
6524 struct btrfs_root *root;
6525 struct btrfs_file_extent_item *fi;
6526 struct extent_buffer *leaf;
6527 struct btrfs_key key;
6531 key.objectid = dback->root;
6532 key.type = BTRFS_ROOT_ITEM_KEY;
6533 key.offset = (u64)-1;
6534 root = btrfs_read_fs_root(info, &key);
6536 fprintf(stderr, "Couldn't find root for our ref\n");
6541 * The backref points to the original offset of the extent if it was
6542 * split, so we need to search down to the offset we have and then walk
6543 * forward until we find the backref we're looking for.
6545 key.objectid = dback->owner;
6546 key.type = BTRFS_EXTENT_DATA_KEY;
6547 key.offset = dback->offset;
6548 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6550 fprintf(stderr, "Error looking up ref %d\n", ret);
6555 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6556 ret = btrfs_next_leaf(root, path);
6558 fprintf(stderr, "Couldn't find our ref, next\n");
6562 leaf = path->nodes[0];
6563 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6564 if (key.objectid != dback->owner ||
6565 key.type != BTRFS_EXTENT_DATA_KEY) {
6566 fprintf(stderr, "Couldn't find our ref, search\n");
6569 fi = btrfs_item_ptr(leaf, path->slots[0],
6570 struct btrfs_file_extent_item);
6571 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
6572 bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
6574 if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
6579 btrfs_release_path(path);
6581 trans = btrfs_start_transaction(root, 1);
6583 return PTR_ERR(trans);
6586 * Ok we have the key of the file extent we want to fix, now we can cow
6587 * down to the thing and fix it.
6589 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
6591 fprintf(stderr, "error cowing down to ref [%llu,%u,%llu]: %d\n",
6592 key.objectid, key.type, key.offset, ret);
6597 "well that's odd, we just found this key [%llu,%u,%llu]\n",
6598 key.objectid, key.type, key.offset);
6602 leaf = path->nodes[0];
6603 fi = btrfs_item_ptr(leaf, path->slots[0],
6604 struct btrfs_file_extent_item);
6606 if (btrfs_file_extent_compression(leaf, fi) &&
6607 dback->disk_bytenr != entry->bytenr) {
6609 "ref doesn't match the record start and is compressed, please take a btrfs-image of this file system and send it to a btrfs developer so they can complete this functionality for bytenr %llu\n",
6610 dback->disk_bytenr);
6615 if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
6616 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6617 } else if (dback->disk_bytenr > entry->bytenr) {
6618 u64 off_diff, offset;
6620 off_diff = dback->disk_bytenr - entry->bytenr;
6621 offset = btrfs_file_extent_offset(leaf, fi);
6622 if (dback->disk_bytenr + offset +
6623 btrfs_file_extent_num_bytes(leaf, fi) >
6624 entry->bytenr + entry->bytes) {
6626 "ref is past the entry end, please take a btrfs-image of this file system and send it to a btrfs developer, ref %llu\n",
6627 dback->disk_bytenr);
6632 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6633 btrfs_set_file_extent_offset(leaf, fi, offset);
6634 } else if (dback->disk_bytenr < entry->bytenr) {
6637 offset = btrfs_file_extent_offset(leaf, fi);
6638 if (dback->disk_bytenr + offset < entry->bytenr) {
6640 "ref is before the entry start, please take a btrfs-image of this file system and send it to a btrfs developer, ref %llu\n",
6641 dback->disk_bytenr);
6646 offset += dback->disk_bytenr;
6647 offset -= entry->bytenr;
6648 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6649 btrfs_set_file_extent_offset(leaf, fi, offset);
6652 btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
6655 * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
6656 * only do this if we aren't using compression, otherwise it's a
6659 if (!btrfs_file_extent_compression(leaf, fi))
6660 btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
6662 printf("ram bytes may be wrong?\n");
6663 btrfs_mark_buffer_dirty(leaf);
6665 err = btrfs_commit_transaction(trans, root);
6666 btrfs_release_path(path);
6667 return ret ? ret : err;
6670 static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
6671 struct extent_record *rec)
6673 struct extent_backref *back, *tmp;
6674 struct data_backref *dback;
6675 struct extent_entry *entry, *best = NULL;
6678 int broken_entries = 0;
6683 * Metadata is easy and the backrefs should always agree on bytenr and
6684 * size, if not we've got bigger issues.
6689 rbtree_postorder_for_each_entry_safe(back, tmp,
6690 &rec->backref_tree, node) {
6691 if (back->full_backref || !back->is_data)
6694 dback = to_data_backref(back);
6697 * We only pay attention to backrefs that we found a real
6700 if (dback->found_ref == 0)
6704 * For now we only catch when the bytes don't match, not the
6705 * bytenr. We can easily do this at the same time, but I want
6706 * to have a fs image to test on before we just add repair
6707 * functionality willy-nilly so we know we won't screw up the
6711 entry = find_entry(&entries, dback->disk_bytenr,
6714 entry = malloc(sizeof(struct extent_entry));
6719 memset(entry, 0, sizeof(*entry));
6720 entry->bytenr = dback->disk_bytenr;
6721 entry->bytes = dback->bytes;
6722 list_add_tail(&entry->list, &entries);
6727 * If we only have on entry we may think the entries agree when
6728 * in reality they don't so we have to do some extra checking.
6730 if (dback->disk_bytenr != rec->start ||
6731 dback->bytes != rec->nr || back->broken)
6742 /* Yay all the backrefs agree, carry on good sir */
6743 if (nr_entries <= 1 && !mismatch)
6747 "attempting to repair backref discrepency for bytenr %llu\n",
6751 * First we want to see if the backrefs can agree amongst themselves who
6752 * is right, so figure out which one of the entries has the highest
6755 best = find_most_right_entry(&entries);
6758 * Ok so we may have an even split between what the backrefs think, so
6759 * this is where we use the extent ref to see what it thinks.
6762 entry = find_entry(&entries, rec->start, rec->nr);
6763 if (!entry && (!broken_entries || !rec->found_rec)) {
6765 "backrefs don't agree with each other and extent record doesn't agree with anybody, so we can't fix bytenr %llu bytes %llu\n",
6766 rec->start, rec->nr);
6769 } else if (!entry) {
6771 * Ok our backrefs were broken, we'll assume this is the
6772 * correct value and add an entry for this range.
6774 entry = malloc(sizeof(struct extent_entry));
6779 memset(entry, 0, sizeof(*entry));
6780 entry->bytenr = rec->start;
6781 entry->bytes = rec->nr;
6782 list_add_tail(&entry->list, &entries);
6786 best = find_most_right_entry(&entries);
6789 "backrefs and extent record evenly split on who is right, this is going to require user input to fix bytenr %llu bytes %llu\n",
6790 rec->start, rec->nr);
6797 * I don't think this can happen currently as we'll abort() if we catch
6798 * this case higher up, but in case somebody removes that we still can't
6799 * deal with it properly here yet, so just bail out of that's the case.
6801 if (best->bytenr != rec->start) {
6803 "extent start and backref starts don't match, please use btrfs-image on this file system and send it to a btrfs developer so they can make fsck fix this particular case. bytenr is %llu, bytes is %llu\n",
6804 rec->start, rec->nr);
6810 * Ok great we all agreed on an extent record, let's go find the real
6811 * references and fix up the ones that don't match.
6813 rbtree_postorder_for_each_entry_safe(back, tmp,
6814 &rec->backref_tree, node) {
6815 if (back->full_backref || !back->is_data)
6818 dback = to_data_backref(back);
6821 * Still ignoring backrefs that don't have a real ref attached
6824 if (dback->found_ref == 0)
6827 if (dback->bytes == best->bytes &&
6828 dback->disk_bytenr == best->bytenr)
6831 ret = repair_ref(info, path, dback, best);
6837 * Ok we messed with the actual refs, which means we need to drop our
6838 * entire cache and go back and rescan. I know this is a huge pain and
6839 * adds a lot of extra work, but it's the only way to be safe. Once all
6840 * the backrefs agree we may not need to do anything to the extent
6845 while (!list_empty(&entries)) {
6846 entry = list_entry(entries.next, struct extent_entry, list);
6847 list_del_init(&entry->list);
6853 static int process_duplicates(struct cache_tree *extent_cache,
6854 struct extent_record *rec)
6856 struct extent_record *good, *tmp;
6857 struct cache_extent *cache;
6861 * If we found a extent record for this extent then return, or if we
6862 * have more than one duplicate we are likely going to need to delete
6865 if (rec->found_rec || rec->num_duplicates > 1)
6868 /* Shouldn't happen but just in case */
6869 BUG_ON(!rec->num_duplicates);
6872 * So this happens if we end up with a backref that doesn't match the
6873 * actual extent entry. So either the backref is bad or the extent
6874 * entry is bad. Either way we want to have the extent_record actually
6875 * reflect what we found in the extent_tree, so we need to take the
6876 * duplicate out and use that as the extent_record since the only way we
6877 * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
6879 remove_cache_extent(extent_cache, &rec->cache);
6881 good = to_extent_record(rec->dups.next);
6882 list_del_init(&good->list);
6883 INIT_LIST_HEAD(&good->backrefs);
6884 INIT_LIST_HEAD(&good->dups);
6885 good->cache.start = good->start;
6886 good->cache.size = good->nr;
6887 good->content_checked = 0;
6888 good->owner_ref_checked = 0;
6889 good->num_duplicates = 0;
6890 good->refs = rec->refs;
6891 list_splice_init(&rec->backrefs, &good->backrefs);
6893 cache = lookup_cache_extent(extent_cache, good->start,
6897 tmp = container_of(cache, struct extent_record, cache);
6900 * If we find another overlapping extent and it's found_rec is
6901 * set then it's a duplicate and we need to try and delete
6904 if (tmp->found_rec || tmp->num_duplicates > 0) {
6905 if (list_empty(&good->list))
6906 list_add_tail(&good->list,
6907 &duplicate_extents);
6908 good->num_duplicates += tmp->num_duplicates + 1;
6909 list_splice_init(&tmp->dups, &good->dups);
6910 list_del_init(&tmp->list);
6911 list_add_tail(&tmp->list, &good->dups);
6912 remove_cache_extent(extent_cache, &tmp->cache);
6917 * Ok we have another non extent item backed extent rec, so lets
6918 * just add it to this extent and carry on like we did above.
6920 good->refs += tmp->refs;
6921 list_splice_init(&tmp->backrefs, &good->backrefs);
6922 remove_cache_extent(extent_cache, &tmp->cache);
6925 ret = insert_cache_extent(extent_cache, &good->cache);
6928 return good->num_duplicates ? 0 : 1;
6931 static int delete_duplicate_records(struct btrfs_root *root,
6932 struct extent_record *rec)
6934 struct btrfs_trans_handle *trans;
6935 LIST_HEAD(delete_list);
6936 struct btrfs_path path;
6937 struct extent_record *tmp, *good, *n;
6940 struct btrfs_key key;
6942 btrfs_init_path(&path);
6945 /* Find the record that covers all of the duplicates. */
6946 list_for_each_entry(tmp, &rec->dups, list) {
6947 if (good->start < tmp->start)
6949 if (good->nr > tmp->nr)
6952 if (tmp->start + tmp->nr < good->start + good->nr) {
6954 "Ok we have overlapping extents that aren't completely covered by each other, this is going to require more careful thought. The extents are [%llu-%llu] and [%llu-%llu]\n",
6955 tmp->start, tmp->nr, good->start, good->nr);
6962 list_add_tail(&rec->list, &delete_list);
6964 list_for_each_entry_safe(tmp, n, &rec->dups, list) {
6967 list_move_tail(&tmp->list, &delete_list);
6970 root = root->fs_info->extent_root;
6971 trans = btrfs_start_transaction(root, 1);
6972 if (IS_ERR(trans)) {
6973 ret = PTR_ERR(trans);
6977 list_for_each_entry(tmp, &delete_list, list) {
6978 if (tmp->found_rec == 0)
6980 key.objectid = tmp->start;
6981 key.type = BTRFS_EXTENT_ITEM_KEY;
6982 key.offset = tmp->nr;
6984 /* Shouldn't happen but just in case */
6985 if (tmp->metadata) {
6987 "well this shouldn't happen, extent record overlaps but is metadata? [%llu, %llu]\n",
6988 tmp->start, tmp->nr);
6992 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
6998 ret = btrfs_del_item(trans, root, &path);
7001 btrfs_release_path(&path);
7004 err = btrfs_commit_transaction(trans, root);
7008 while (!list_empty(&delete_list)) {
7009 tmp = to_extent_record(delete_list.next);
7010 list_del_init(&tmp->list);
7016 while (!list_empty(&rec->dups)) {
7017 tmp = to_extent_record(rec->dups.next);
7018 list_del_init(&tmp->list);
7022 btrfs_release_path(&path);
7024 if (!ret && !nr_del)
7025 rec->num_duplicates = 0;
7027 return ret ? ret : nr_del;
7030 static int find_possible_backrefs(struct btrfs_fs_info *info,
7031 struct btrfs_path *path,
7032 struct cache_tree *extent_cache,
7033 struct extent_record *rec)
7035 struct btrfs_root *root;
7036 struct extent_backref *back, *tmp;
7037 struct data_backref *dback;
7038 struct cache_extent *cache;
7039 struct btrfs_file_extent_item *fi;
7040 struct btrfs_key key;
7044 rbtree_postorder_for_each_entry_safe(back, tmp,
7045 &rec->backref_tree, node) {
7046 /* Don't care about full backrefs (poor unloved backrefs) */
7047 if (back->full_backref || !back->is_data)
7050 dback = to_data_backref(back);
7052 /* We found this one, we don't need to do a lookup */
7053 if (dback->found_ref)
7056 key.objectid = dback->root;
7057 key.type = BTRFS_ROOT_ITEM_KEY;
7058 key.offset = (u64)-1;
7060 root = btrfs_read_fs_root(info, &key);
7062 /* No root, definitely a bad ref, skip */
7063 if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
7065 /* Other err, exit */
7067 return PTR_ERR(root);
7069 key.objectid = dback->owner;
7070 key.type = BTRFS_EXTENT_DATA_KEY;
7071 key.offset = dback->offset;
7072 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
7074 btrfs_release_path(path);
7077 /* Didn't find it, we can carry on */
7082 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
7083 struct btrfs_file_extent_item);
7084 bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
7085 bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
7086 btrfs_release_path(path);
7087 cache = lookup_cache_extent(extent_cache, bytenr, 1);
7089 struct extent_record *tmp;
7091 tmp = container_of(cache, struct extent_record, cache);
7094 * If we found an extent record for the bytenr for this
7095 * particular backref then we can't add it to our
7096 * current extent record. We only want to add backrefs
7097 * that don't have a corresponding extent item in the
7098 * extent tree since they likely belong to this record
7099 * and we need to fix it if it doesn't match bytenrs.
7105 dback->found_ref += 1;
7106 dback->disk_bytenr = bytenr;
7107 dback->bytes = bytes;
7110 * Set this so the verify backref code knows not to trust the
7111 * values in this backref.
7120 * Record orphan data ref into corresponding root.
7122 * Return 0 if the extent item contains data ref and recorded.
7123 * Return 1 if the extent item contains no useful data ref
7124 * On that case, it may contains only shared_dataref or metadata backref
7125 * or the file extent exists(this should be handled by the extent bytenr
7127 * Return <0 if something goes wrong.
7129 static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
7130 struct extent_record *rec)
7132 struct btrfs_key key;
7133 struct btrfs_root *dest_root;
7134 struct extent_backref *back, *tmp;
7135 struct data_backref *dback;
7136 struct orphan_data_extent *orphan;
7137 struct btrfs_path path;
7138 int recorded_data_ref = 0;
7143 btrfs_init_path(&path);
7144 rbtree_postorder_for_each_entry_safe(back, tmp,
7145 &rec->backref_tree, node) {
7146 if (back->full_backref || !back->is_data ||
7147 !back->found_extent_tree)
7149 dback = to_data_backref(back);
7150 if (dback->found_ref)
7152 key.objectid = dback->root;
7153 key.type = BTRFS_ROOT_ITEM_KEY;
7154 key.offset = (u64)-1;
7156 dest_root = btrfs_read_fs_root(fs_info, &key);
7158 /* For non-exist root we just skip it */
7159 if (IS_ERR(dest_root) || !dest_root)
7162 key.objectid = dback->owner;
7163 key.type = BTRFS_EXTENT_DATA_KEY;
7164 key.offset = dback->offset;
7166 ret = btrfs_search_slot(NULL, dest_root, &key, &path, 0, 0);
7167 btrfs_release_path(&path);
7169 * For ret < 0, it's OK since the fs-tree may be corrupted,
7170 * we need to record it for inode/file extent rebuild.
7171 * For ret > 0, we record it only for file extent rebuild.
7172 * For ret == 0, the file extent exists but only bytenr
7173 * mismatch, let the original bytenr fix routine to handle,
7179 orphan = malloc(sizeof(*orphan));
7184 INIT_LIST_HEAD(&orphan->list);
7185 orphan->root = dback->root;
7186 orphan->objectid = dback->owner;
7187 orphan->offset = dback->offset;
7188 orphan->disk_bytenr = rec->cache.start;
7189 orphan->disk_len = rec->cache.size;
7190 list_add(&dest_root->orphan_data_extents, &orphan->list);
7191 recorded_data_ref = 1;
7194 btrfs_release_path(&path);
7196 return !recorded_data_ref;
7202 * when an incorrect extent item is found, this will delete
7203 * all of the existing entries for it and recreate them
7204 * based on what the tree scan found.
7206 static int fixup_extent_refs(struct btrfs_fs_info *info,
7207 struct cache_tree *extent_cache,
7208 struct extent_record *rec)
7210 struct btrfs_trans_handle *trans = NULL;
7212 struct btrfs_path path;
7213 struct cache_extent *cache;
7214 struct extent_backref *back, *tmp;
7218 if (rec->flag_block_full_backref)
7219 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7221 btrfs_init_path(&path);
7222 if (rec->refs != rec->extent_item_refs && !rec->metadata) {
7224 * Sometimes the backrefs themselves are so broken they don't
7225 * get attached to any meaningful rec, so first go back and
7226 * check any of our backrefs that we couldn't find and throw
7227 * them into the list if we find the backref so that
7228 * verify_backrefs can figure out what to do.
7230 ret = find_possible_backrefs(info, &path, extent_cache, rec);
7235 /* step one, make sure all of the backrefs agree */
7236 ret = verify_backrefs(info, &path, rec);
7240 trans = btrfs_start_transaction(info->extent_root, 1);
7241 if (IS_ERR(trans)) {
7242 ret = PTR_ERR(trans);
7246 /* step two, delete all the existing records */
7247 ret = delete_extent_records(trans, info->extent_root, &path,
7253 /* was this block corrupt? If so, don't add references to it */
7254 cache = lookup_cache_extent(info->corrupt_blocks,
7255 rec->start, rec->max_size);
7261 /* step three, recreate all the refs we did find */
7262 rbtree_postorder_for_each_entry_safe(back, tmp,
7263 &rec->backref_tree, node) {
7265 * if we didn't find any references, don't create a
7268 if (!back->found_ref)
7271 rec->bad_full_backref = 0;
7272 ret = record_extent(trans, info, &path, rec, back, allocated,
7281 int err = btrfs_commit_transaction(trans, info->extent_root);
7288 fprintf(stderr, "Repaired extent references for %llu\n",
7289 (unsigned long long)rec->start);
7291 btrfs_release_path(&path);
7295 static int fixup_extent_flags(struct btrfs_fs_info *fs_info,
7296 struct extent_record *rec)
7298 struct btrfs_trans_handle *trans;
7299 struct btrfs_root *root = fs_info->extent_root;
7300 struct btrfs_path path;
7301 struct btrfs_extent_item *ei;
7302 struct btrfs_key key;
7306 key.objectid = rec->start;
7307 if (rec->metadata) {
7308 key.type = BTRFS_METADATA_ITEM_KEY;
7309 key.offset = rec->info_level;
7311 key.type = BTRFS_EXTENT_ITEM_KEY;
7312 key.offset = rec->max_size;
7315 trans = btrfs_start_transaction(root, 0);
7317 return PTR_ERR(trans);
7319 btrfs_init_path(&path);
7320 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
7322 btrfs_release_path(&path);
7323 btrfs_commit_transaction(trans, root);
7326 fprintf(stderr, "Didn't find extent for %llu\n",
7327 (unsigned long long)rec->start);
7328 btrfs_release_path(&path);
7329 btrfs_commit_transaction(trans, root);
7333 ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
7334 struct btrfs_extent_item);
7335 flags = btrfs_extent_flags(path.nodes[0], ei);
7336 if (rec->flag_block_full_backref) {
7337 fprintf(stderr, "setting full backref on %llu\n",
7338 (unsigned long long)key.objectid);
7339 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7341 fprintf(stderr, "clearing full backref on %llu\n",
7342 (unsigned long long)key.objectid);
7343 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
7345 btrfs_set_extent_flags(path.nodes[0], ei, flags);
7346 btrfs_mark_buffer_dirty(path.nodes[0]);
7347 btrfs_release_path(&path);
7348 ret = btrfs_commit_transaction(trans, root);
7350 fprintf(stderr, "Repaired extent flags for %llu\n",
7351 (unsigned long long)rec->start);
7356 /* right now we only prune from the extent allocation tree */
7357 static int prune_one_block(struct btrfs_trans_handle *trans,
7358 struct btrfs_fs_info *info,
7359 struct btrfs_corrupt_block *corrupt)
7362 struct btrfs_path path;
7363 struct extent_buffer *eb;
7367 int level = corrupt->level + 1;
7369 btrfs_init_path(&path);
7371 /* we want to stop at the parent to our busted block */
7372 path.lowest_level = level;
7374 ret = btrfs_search_slot(trans, info->extent_root,
7375 &corrupt->key, &path, -1, 1);
7380 eb = path.nodes[level];
7387 * hopefully the search gave us the block we want to prune,
7388 * lets try that first
7390 slot = path.slots[level];
7391 found = btrfs_node_blockptr(eb, slot);
7392 if (found == corrupt->cache.start)
7395 nritems = btrfs_header_nritems(eb);
7397 /* the search failed, lets scan this node and hope we find it */
7398 for (slot = 0; slot < nritems; slot++) {
7399 found = btrfs_node_blockptr(eb, slot);
7400 if (found == corrupt->cache.start)
7404 * We couldn't find the bad block.
7405 * TODO: search all the nodes for pointers to this block
7407 if (eb == info->extent_root->node) {
7412 btrfs_release_path(&path);
7417 printk("deleting pointer to block %llu\n", corrupt->cache.start);
7418 ret = btrfs_del_ptr(info->extent_root, &path, level, slot);
7421 btrfs_release_path(&path);
7425 static int prune_corrupt_blocks(struct btrfs_fs_info *info)
7427 struct btrfs_trans_handle *trans = NULL;
7428 struct cache_extent *cache;
7429 struct btrfs_corrupt_block *corrupt;
7432 cache = search_cache_extent(info->corrupt_blocks, 0);
7436 trans = btrfs_start_transaction(info->extent_root, 1);
7438 return PTR_ERR(trans);
7440 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
7441 prune_one_block(trans, info, corrupt);
7442 remove_cache_extent(info->corrupt_blocks, cache);
7445 return btrfs_commit_transaction(trans, info->extent_root);
7449 static int check_extent_refs(struct btrfs_root *root,
7450 struct cache_tree *extent_cache)
7452 struct extent_record *rec;
7453 struct cache_extent *cache;
7460 * if we're doing a repair, we have to make sure
7461 * we don't allocate from the problem extents.
7462 * In the worst case, this will be all the
7465 cache = search_cache_extent(extent_cache, 0);
7467 rec = container_of(cache, struct extent_record, cache);
7468 set_extent_dirty(root->fs_info->excluded_extents,
7470 rec->start + rec->max_size - 1);
7471 cache = next_cache_extent(cache);
7474 /* pin down all the corrupted blocks too */
7475 cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
7477 set_extent_dirty(root->fs_info->excluded_extents,
7479 cache->start + cache->size - 1);
7480 cache = next_cache_extent(cache);
7482 prune_corrupt_blocks(root->fs_info);
7483 reset_cached_block_groups(root->fs_info);
7486 reset_cached_block_groups(root->fs_info);
7489 * We need to delete any duplicate entries we find first otherwise we
7490 * could mess up the extent tree when we have backrefs that actually
7491 * belong to a different extent item and not the weird duplicate one.
7493 while (repair && !list_empty(&duplicate_extents)) {
7494 rec = to_extent_record(duplicate_extents.next);
7495 list_del_init(&rec->list);
7497 /* Sometimes we can find a backref before we find an actual
7498 * extent, so we need to process it a little bit to see if there
7499 * truly are multiple EXTENT_ITEM_KEY's for the same range, or
7500 * if this is a backref screwup. If we need to delete stuff
7501 * process_duplicates() will return 0, otherwise it will return
7504 if (process_duplicates(extent_cache, rec))
7506 ret = delete_duplicate_records(root, rec);
7510 * delete_duplicate_records will return the number of entries
7511 * deleted, so if it's greater than 0 then we know we actually
7512 * did something and we need to remove.
7525 cache = search_cache_extent(extent_cache, 0);
7528 rec = container_of(cache, struct extent_record, cache);
7529 if (rec->num_duplicates) {
7531 "extent item %llu has multiple extent items\n",
7532 (unsigned long long)rec->start);
7536 if (rec->refs != rec->extent_item_refs) {
7537 fprintf(stderr, "ref mismatch on [%llu %llu] ",
7538 (unsigned long long)rec->start,
7539 (unsigned long long)rec->nr);
7540 fprintf(stderr, "extent item %llu, found %llu\n",
7541 (unsigned long long)rec->extent_item_refs,
7542 (unsigned long long)rec->refs);
7543 ret = record_orphan_data_extents(root->fs_info, rec);
7549 if (all_backpointers_checked(rec, 1)) {
7550 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
7551 (unsigned long long)rec->start,
7552 (unsigned long long)rec->nr);
7556 if (!rec->owner_ref_checked) {
7557 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
7558 (unsigned long long)rec->start,
7559 (unsigned long long)rec->nr);
7564 if (repair && fix) {
7565 ret = fixup_extent_refs(root->fs_info, extent_cache,
7572 if (rec->bad_full_backref) {
7573 fprintf(stderr, "bad full backref, on [%llu]\n",
7574 (unsigned long long)rec->start);
7576 ret = fixup_extent_flags(root->fs_info, rec);
7584 * Although it's not a extent ref's problem, we reuse this
7585 * routine for error reporting.
7586 * No repair function yet.
7588 if (rec->crossing_stripes) {
7590 "bad metadata [%llu, %llu) crossing stripe boundary\n",
7591 rec->start, rec->start + rec->max_size);
7595 if (rec->wrong_chunk_type) {
7597 "bad extent [%llu, %llu), type mismatch with chunk\n",
7598 rec->start, rec->start + rec->max_size);
7603 remove_cache_extent(extent_cache, cache);
7604 free_all_extent_backrefs(rec);
7605 if (!init_extent_tree && repair && (!cur_err || fix))
7606 clear_extent_dirty(root->fs_info->excluded_extents,
7608 rec->start + rec->max_size - 1);
7613 if (ret && ret != -EAGAIN) {
7614 fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
7617 struct btrfs_trans_handle *trans;
7619 root = root->fs_info->extent_root;
7620 trans = btrfs_start_transaction(root, 1);
7621 if (IS_ERR(trans)) {
7622 ret = PTR_ERR(trans);
7626 ret = btrfs_fix_block_accounting(trans, root);
7629 ret = btrfs_commit_transaction(trans, root);
7642 * Check the chunk with its block group/dev list ref:
7643 * Return 0 if all refs seems valid.
7644 * Return 1 if part of refs seems valid, need later check for rebuild ref
7645 * like missing block group and needs to search extent tree to rebuild them.
7646 * Return -1 if essential refs are missing and unable to rebuild.
7648 static int check_chunk_refs(struct chunk_record *chunk_rec,
7649 struct block_group_tree *block_group_cache,
7650 struct device_extent_tree *dev_extent_cache,
7653 struct cache_extent *block_group_item;
7654 struct block_group_record *block_group_rec;
7655 struct cache_extent *dev_extent_item;
7656 struct device_extent_record *dev_extent_rec;
7660 int metadump_v2 = 0;
7664 block_group_item = lookup_cache_extent(&block_group_cache->tree,
7667 if (block_group_item) {
7668 block_group_rec = container_of(block_group_item,
7669 struct block_group_record,
7671 if (chunk_rec->length != block_group_rec->offset ||
7672 chunk_rec->offset != block_group_rec->objectid ||
7674 chunk_rec->type_flags != block_group_rec->flags)) {
7677 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
7678 chunk_rec->objectid,
7683 chunk_rec->type_flags,
7684 block_group_rec->objectid,
7685 block_group_rec->type,
7686 block_group_rec->offset,
7687 block_group_rec->offset,
7688 block_group_rec->objectid,
7689 block_group_rec->flags);
7692 list_del_init(&block_group_rec->list);
7693 chunk_rec->bg_rec = block_group_rec;
7698 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
7699 chunk_rec->objectid,
7704 chunk_rec->type_flags);
7711 length = calc_stripe_length(chunk_rec->type_flags, chunk_rec->length,
7712 chunk_rec->num_stripes);
7713 for (i = 0; i < chunk_rec->num_stripes; ++i) {
7714 devid = chunk_rec->stripes[i].devid;
7715 offset = chunk_rec->stripes[i].offset;
7716 dev_extent_item = lookup_cache_extent2(&dev_extent_cache->tree,
7717 devid, offset, length);
7718 if (dev_extent_item) {
7719 dev_extent_rec = container_of(dev_extent_item,
7720 struct device_extent_record,
7722 if (dev_extent_rec->objectid != devid ||
7723 dev_extent_rec->offset != offset ||
7724 dev_extent_rec->chunk_offset != chunk_rec->offset ||
7725 dev_extent_rec->length != length) {
7728 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
7729 chunk_rec->objectid,
7732 chunk_rec->stripes[i].devid,
7733 chunk_rec->stripes[i].offset,
7734 dev_extent_rec->objectid,
7735 dev_extent_rec->offset,
7736 dev_extent_rec->length);
7739 list_move(&dev_extent_rec->chunk_list,
7740 &chunk_rec->dextents);
7745 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
7746 chunk_rec->objectid,
7749 chunk_rec->stripes[i].devid,
7750 chunk_rec->stripes[i].offset);
7757 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
7758 int check_chunks(struct cache_tree *chunk_cache,
7759 struct block_group_tree *block_group_cache,
7760 struct device_extent_tree *dev_extent_cache,
7761 struct list_head *good, struct list_head *bad,
7762 struct list_head *rebuild, int silent)
7764 struct cache_extent *chunk_item;
7765 struct chunk_record *chunk_rec;
7766 struct block_group_record *bg_rec;
7767 struct device_extent_record *dext_rec;
7771 chunk_item = first_cache_extent(chunk_cache);
7772 while (chunk_item) {
7773 chunk_rec = container_of(chunk_item, struct chunk_record,
7775 err = check_chunk_refs(chunk_rec, block_group_cache,
7776 dev_extent_cache, silent);
7779 if (err == 0 && good)
7780 list_add_tail(&chunk_rec->list, good);
7781 if (err > 0 && rebuild)
7782 list_add_tail(&chunk_rec->list, rebuild);
7784 list_add_tail(&chunk_rec->list, bad);
7785 chunk_item = next_cache_extent(chunk_item);
7788 list_for_each_entry(bg_rec, &block_group_cache->block_groups, list) {
7791 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
7799 list_for_each_entry(dext_rec, &dev_extent_cache->no_chunk_orphans,
7803 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
7814 static int check_device_used(struct device_record *dev_rec,
7815 struct device_extent_tree *dext_cache)
7817 struct cache_extent *cache;
7818 struct device_extent_record *dev_extent_rec;
7821 cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
7823 dev_extent_rec = container_of(cache,
7824 struct device_extent_record,
7826 if (dev_extent_rec->objectid != dev_rec->devid)
7829 list_del_init(&dev_extent_rec->device_list);
7830 total_byte += dev_extent_rec->length;
7831 cache = next_cache_extent(cache);
7834 if (total_byte != dev_rec->byte_used) {
7836 "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
7837 total_byte, dev_rec->byte_used, dev_rec->objectid,
7838 dev_rec->type, dev_rec->offset);
7846 * Unlike device size alignment check above, some super total_bytes check
7847 * failure can lead to mount failure for newer kernel.
7849 * So this function will return the error for a fatal super total_bytes problem.
7851 static bool is_super_size_valid(struct btrfs_fs_info *fs_info)
7853 struct btrfs_device *dev;
7854 struct list_head *dev_list = &fs_info->fs_devices->devices;
7855 u64 total_bytes = 0;
7856 u64 super_bytes = btrfs_super_total_bytes(fs_info->super_copy);
7858 list_for_each_entry(dev, dev_list, dev_list)
7859 total_bytes += dev->total_bytes;
7861 /* Important check, which can cause unmountable fs */
7862 if (super_bytes < total_bytes) {
7863 error("super total bytes %llu smaller than real device(s) size %llu",
7864 super_bytes, total_bytes);
7865 error("mounting this fs may fail for newer kernels");
7866 error("this can be fixed by 'btrfs rescue fix-device-size'");
7871 * Optional check, just to make everything aligned and match with each
7874 * For a btrfs-image restored fs, we don't need to check it anyway.
7876 if (btrfs_super_flags(fs_info->super_copy) &
7877 (BTRFS_SUPER_FLAG_METADUMP | BTRFS_SUPER_FLAG_METADUMP_V2))
7879 if (!IS_ALIGNED(super_bytes, fs_info->sectorsize) ||
7880 !IS_ALIGNED(total_bytes, fs_info->sectorsize) ||
7881 super_bytes != total_bytes) {
7882 warning("minor unaligned/mismatch device size detected");
7884 "recommended to use 'btrfs rescue fix-device-size' to fix it");
7889 /* check btrfs_dev_item -> btrfs_dev_extent */
7890 static int check_devices(struct rb_root *dev_cache,
7891 struct device_extent_tree *dev_extent_cache)
7893 struct rb_node *dev_node;
7894 struct device_record *dev_rec;
7895 struct device_extent_record *dext_rec;
7899 dev_node = rb_first(dev_cache);
7901 dev_rec = container_of(dev_node, struct device_record, node);
7902 err = check_device_used(dev_rec, dev_extent_cache);
7906 check_dev_size_alignment(dev_rec->devid, dev_rec->total_byte,
7907 global_info->sectorsize);
7908 dev_node = rb_next(dev_node);
7910 list_for_each_entry(dext_rec, &dev_extent_cache->no_device_orphans,
7913 "Device extent[%llu, %llu, %llu] didn't find its device.\n",
7914 dext_rec->objectid, dext_rec->offset, dext_rec->length);
7921 static int add_root_item_to_list(struct list_head *head,
7922 u64 objectid, u64 bytenr, u64 last_snapshot,
7923 u8 level, u8 drop_level,
7924 struct btrfs_key *drop_key)
7926 struct root_item_record *ri_rec;
7928 ri_rec = malloc(sizeof(*ri_rec));
7931 ri_rec->bytenr = bytenr;
7932 ri_rec->objectid = objectid;
7933 ri_rec->level = level;
7934 ri_rec->drop_level = drop_level;
7935 ri_rec->last_snapshot = last_snapshot;
7937 memcpy(&ri_rec->drop_key, drop_key, sizeof(*drop_key));
7938 list_add_tail(&ri_rec->list, head);
7943 static void free_root_item_list(struct list_head *list)
7945 struct root_item_record *ri_rec;
7947 while (!list_empty(list)) {
7948 ri_rec = list_first_entry(list, struct root_item_record,
7950 list_del_init(&ri_rec->list);
7955 static int deal_root_from_list(struct list_head *list,
7956 struct btrfs_root *root,
7957 struct block_info *bits,
7959 struct cache_tree *pending,
7960 struct cache_tree *seen,
7961 struct cache_tree *reada,
7962 struct cache_tree *nodes,
7963 struct cache_tree *extent_cache,
7964 struct cache_tree *chunk_cache,
7965 struct rb_root *dev_cache,
7966 struct block_group_tree *block_group_cache,
7967 struct device_extent_tree *dev_extent_cache)
7972 while (!list_empty(list)) {
7973 struct root_item_record *rec;
7974 struct extent_buffer *buf;
7976 rec = list_entry(list->next,
7977 struct root_item_record, list);
7979 buf = read_tree_block(root->fs_info, rec->bytenr, 0);
7980 if (!extent_buffer_uptodate(buf)) {
7981 free_extent_buffer(buf);
7985 ret = add_root_to_pending(buf, extent_cache, pending,
7986 seen, nodes, rec->objectid);
7990 * To rebuild extent tree, we need deal with snapshot
7991 * one by one, otherwise we deal with node firstly which
7992 * can maximize readahead.
7995 ret = run_next_block(root, bits, bits_nr, &last,
7996 pending, seen, reada, nodes,
7997 extent_cache, chunk_cache,
7998 dev_cache, block_group_cache,
7999 dev_extent_cache, rec);
8003 free_extent_buffer(buf);
8004 list_del(&rec->list);
8010 ret = run_next_block(root, bits, bits_nr, &last, pending, seen,
8011 reada, nodes, extent_cache, chunk_cache,
8012 dev_cache, block_group_cache,
8013 dev_extent_cache, NULL);
8023 static int check_chunks_and_extents(struct btrfs_fs_info *fs_info)
8025 struct rb_root dev_cache;
8026 struct cache_tree chunk_cache;
8027 struct block_group_tree block_group_cache;
8028 struct device_extent_tree dev_extent_cache;
8029 struct cache_tree extent_cache;
8030 struct cache_tree seen;
8031 struct cache_tree pending;
8032 struct cache_tree reada;
8033 struct cache_tree nodes;
8034 struct extent_io_tree excluded_extents;
8035 struct cache_tree corrupt_blocks;
8036 struct btrfs_path path;
8037 struct btrfs_key key;
8038 struct btrfs_key found_key;
8040 struct block_info *bits;
8042 struct extent_buffer *leaf;
8044 struct btrfs_root_item ri;
8045 struct list_head dropping_trees;
8046 struct list_head normal_trees;
8047 struct btrfs_root *root1;
8048 struct btrfs_root *root;
8052 root = fs_info->fs_root;
8053 dev_cache = RB_ROOT;
8054 cache_tree_init(&chunk_cache);
8055 block_group_tree_init(&block_group_cache);
8056 device_extent_tree_init(&dev_extent_cache);
8058 cache_tree_init(&extent_cache);
8059 cache_tree_init(&seen);
8060 cache_tree_init(&pending);
8061 cache_tree_init(&nodes);
8062 cache_tree_init(&reada);
8063 cache_tree_init(&corrupt_blocks);
8064 extent_io_tree_init(&excluded_extents);
8065 INIT_LIST_HEAD(&dropping_trees);
8066 INIT_LIST_HEAD(&normal_trees);
8069 fs_info->excluded_extents = &excluded_extents;
8070 fs_info->fsck_extent_cache = &extent_cache;
8071 fs_info->free_extent_hook = free_extent_hook;
8072 fs_info->corrupt_blocks = &corrupt_blocks;
8076 bits = malloc(bits_nr * sizeof(struct block_info));
8082 if (ctx.progress_enabled) {
8083 ctx.tp = TASK_EXTENTS;
8084 task_start(ctx.info);
8088 root1 = fs_info->tree_root;
8089 level = btrfs_header_level(root1->node);
8090 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8091 root1->node->start, 0, level, 0, NULL);
8094 root1 = fs_info->chunk_root;
8095 level = btrfs_header_level(root1->node);
8096 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8097 root1->node->start, 0, level, 0, NULL);
8100 btrfs_init_path(&path);
8103 key.type = BTRFS_ROOT_ITEM_KEY;
8104 ret = btrfs_search_slot(NULL, fs_info->tree_root, &key, &path, 0, 0);
8108 leaf = path.nodes[0];
8109 slot = path.slots[0];
8110 if (slot >= btrfs_header_nritems(path.nodes[0])) {
8111 ret = btrfs_next_leaf(root, &path);
8114 leaf = path.nodes[0];
8115 slot = path.slots[0];
8117 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
8118 if (found_key.type == BTRFS_ROOT_ITEM_KEY) {
8119 unsigned long offset;
8122 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
8123 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
8124 last_snapshot = btrfs_root_last_snapshot(&ri);
8125 if (btrfs_disk_key_objectid(&ri.drop_progress) == 0) {
8126 level = btrfs_root_level(&ri);
8127 ret = add_root_item_to_list(&normal_trees,
8129 btrfs_root_bytenr(&ri),
8130 last_snapshot, level,
8135 level = btrfs_root_level(&ri);
8136 objectid = found_key.objectid;
8137 btrfs_disk_key_to_cpu(&found_key,
8139 ret = add_root_item_to_list(&dropping_trees,
8141 btrfs_root_bytenr(&ri),
8142 last_snapshot, level,
8143 ri.drop_level, &found_key);
8150 btrfs_release_path(&path);
8153 * check_block can return -EAGAIN if it fixes something, please keep
8154 * this in mind when dealing with return values from these functions, if
8155 * we get -EAGAIN we want to fall through and restart the loop.
8157 ret = deal_root_from_list(&normal_trees, root, bits, bits_nr, &pending,
8158 &seen, &reada, &nodes, &extent_cache,
8159 &chunk_cache, &dev_cache, &block_group_cache,
8166 ret = deal_root_from_list(&dropping_trees, root, bits, bits_nr,
8167 &pending, &seen, &reada, &nodes,
8168 &extent_cache, &chunk_cache, &dev_cache,
8169 &block_group_cache, &dev_extent_cache);
8176 ret = check_chunks(&chunk_cache, &block_group_cache,
8177 &dev_extent_cache, NULL, NULL, NULL, 0);
8184 ret = check_extent_refs(root, &extent_cache);
8191 ret = check_devices(&dev_cache, &dev_extent_cache);
8196 task_stop(ctx.info);
8198 free_corrupt_blocks_tree(fs_info->corrupt_blocks);
8199 extent_io_tree_cleanup(&excluded_extents);
8200 fs_info->fsck_extent_cache = NULL;
8201 fs_info->free_extent_hook = NULL;
8202 fs_info->corrupt_blocks = NULL;
8203 fs_info->excluded_extents = NULL;
8206 free_chunk_cache_tree(&chunk_cache);
8207 free_device_cache_tree(&dev_cache);
8208 free_block_group_tree(&block_group_cache);
8209 free_device_extent_tree(&dev_extent_cache);
8210 free_extent_cache_tree(&seen);
8211 free_extent_cache_tree(&pending);
8212 free_extent_cache_tree(&reada);
8213 free_extent_cache_tree(&nodes);
8214 free_root_item_list(&normal_trees);
8215 free_root_item_list(&dropping_trees);
8218 free_corrupt_blocks_tree(fs_info->corrupt_blocks);
8219 free_extent_cache_tree(&seen);
8220 free_extent_cache_tree(&pending);
8221 free_extent_cache_tree(&reada);
8222 free_extent_cache_tree(&nodes);
8223 free_chunk_cache_tree(&chunk_cache);
8224 free_block_group_tree(&block_group_cache);
8225 free_device_cache_tree(&dev_cache);
8226 free_device_extent_tree(&dev_extent_cache);
8227 free_extent_record_cache(&extent_cache);
8228 free_root_item_list(&normal_trees);
8229 free_root_item_list(&dropping_trees);
8230 extent_io_tree_cleanup(&excluded_extents);
8234 static int do_check_chunks_and_extents(struct btrfs_fs_info *fs_info)
8238 if (!ctx.progress_enabled)
8239 fprintf(stderr, "checking extents\n");
8240 if (check_mode == CHECK_MODE_LOWMEM)
8241 ret = check_chunks_and_extents_lowmem(fs_info);
8243 ret = check_chunks_and_extents(fs_info);
8245 /* Also repair device size related problems */
8246 if (repair && !ret) {
8247 ret = btrfs_fix_device_and_super_size(fs_info);
8254 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
8255 struct btrfs_root *root, int overwrite)
8257 struct extent_buffer *c;
8258 struct extent_buffer *old = root->node;
8261 struct btrfs_disk_key disk_key = {0,0,0};
8267 extent_buffer_get(c);
8270 c = btrfs_alloc_free_block(trans, root,
8271 root->fs_info->nodesize,
8272 root->root_key.objectid,
8273 &disk_key, level, 0, 0);
8276 extent_buffer_get(c);
8280 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
8281 btrfs_set_header_level(c, level);
8282 btrfs_set_header_bytenr(c, c->start);
8283 btrfs_set_header_generation(c, trans->transid);
8284 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
8285 btrfs_set_header_owner(c, root->root_key.objectid);
8287 write_extent_buffer(c, root->fs_info->fsid,
8288 btrfs_header_fsid(), BTRFS_FSID_SIZE);
8290 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
8291 btrfs_header_chunk_tree_uuid(c),
8294 btrfs_mark_buffer_dirty(c);
8296 * this case can happen in the following case:
8298 * 1.overwrite previous root.
8300 * 2.reinit reloc data root, this is because we skip pin
8301 * down reloc data tree before which means we can allocate
8302 * same block bytenr here.
8304 if (old->start == c->start) {
8305 btrfs_set_root_generation(&root->root_item,
8307 root->root_item.level = btrfs_header_level(root->node);
8308 ret = btrfs_update_root(trans, root->fs_info->tree_root,
8309 &root->root_key, &root->root_item);
8311 free_extent_buffer(c);
8315 free_extent_buffer(old);
8317 add_root_to_dirty_list(root);
8321 static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
8322 struct extent_buffer *eb, int tree_root)
8324 struct extent_buffer *tmp;
8325 struct btrfs_root_item *ri;
8326 struct btrfs_key key;
8328 int level = btrfs_header_level(eb);
8334 * If we have pinned this block before, don't pin it again.
8335 * This can not only avoid forever loop with broken filesystem
8336 * but also give us some speedups.
8338 if (test_range_bit(&fs_info->pinned_extents, eb->start,
8339 eb->start + eb->len - 1, EXTENT_DIRTY, 0))
8342 btrfs_pin_extent(fs_info, eb->start, eb->len);
8344 nritems = btrfs_header_nritems(eb);
8345 for (i = 0; i < nritems; i++) {
8347 btrfs_item_key_to_cpu(eb, &key, i);
8348 if (key.type != BTRFS_ROOT_ITEM_KEY)
8350 /* Skip the extent root and reloc roots */
8351 if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
8352 key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
8353 key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
8355 ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
8356 bytenr = btrfs_disk_root_bytenr(eb, ri);
8359 * If at any point we start needing the real root we
8360 * will have to build a stump root for the root we are
8361 * in, but for now this doesn't actually use the root so
8362 * just pass in extent_root.
8364 tmp = read_tree_block(fs_info, bytenr, 0);
8365 if (!extent_buffer_uptodate(tmp)) {
8366 fprintf(stderr, "Error reading root block\n");
8369 ret = pin_down_tree_blocks(fs_info, tmp, 0);
8370 free_extent_buffer(tmp);
8374 bytenr = btrfs_node_blockptr(eb, i);
8376 /* If we aren't the tree root don't read the block */
8377 if (level == 1 && !tree_root) {
8378 btrfs_pin_extent(fs_info, bytenr,
8383 tmp = read_tree_block(fs_info, bytenr, 0);
8384 if (!extent_buffer_uptodate(tmp)) {
8385 fprintf(stderr, "Error reading tree block\n");
8388 ret = pin_down_tree_blocks(fs_info, tmp, tree_root);
8389 free_extent_buffer(tmp);
8398 static int pin_metadata_blocks(struct btrfs_fs_info *fs_info)
8402 ret = pin_down_tree_blocks(fs_info, fs_info->chunk_root->node, 0);
8406 return pin_down_tree_blocks(fs_info, fs_info->tree_root->node, 1);
8409 static int reset_block_groups(struct btrfs_fs_info *fs_info)
8411 struct btrfs_block_group_cache *cache;
8412 struct btrfs_path path;
8413 struct extent_buffer *leaf;
8414 struct btrfs_chunk *chunk;
8415 struct btrfs_key key;
8419 btrfs_init_path(&path);
8421 key.type = BTRFS_CHUNK_ITEM_KEY;
8423 ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, &path, 0, 0);
8425 btrfs_release_path(&path);
8430 * We do this in case the block groups were screwed up and had alloc
8431 * bits that aren't actually set on the chunks. This happens with
8432 * restored images every time and could happen in real life I guess.
8434 fs_info->avail_data_alloc_bits = 0;
8435 fs_info->avail_metadata_alloc_bits = 0;
8436 fs_info->avail_system_alloc_bits = 0;
8438 /* First we need to create the in-memory block groups */
8440 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8441 ret = btrfs_next_leaf(fs_info->chunk_root, &path);
8443 btrfs_release_path(&path);
8451 leaf = path.nodes[0];
8452 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8453 if (key.type != BTRFS_CHUNK_ITEM_KEY) {
8458 chunk = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_chunk);
8459 btrfs_add_block_group(fs_info, 0,
8460 btrfs_chunk_type(leaf, chunk), key.offset,
8461 btrfs_chunk_length(leaf, chunk));
8462 set_extent_dirty(&fs_info->free_space_cache, key.offset,
8463 key.offset + btrfs_chunk_length(leaf, chunk));
8468 cache = btrfs_lookup_first_block_group(fs_info, start);
8472 start = cache->key.objectid + cache->key.offset;
8475 btrfs_release_path(&path);
8479 static int reset_balance(struct btrfs_trans_handle *trans,
8480 struct btrfs_fs_info *fs_info)
8482 struct btrfs_root *root = fs_info->tree_root;
8483 struct btrfs_path path;
8484 struct extent_buffer *leaf;
8485 struct btrfs_key key;
8486 int del_slot, del_nr = 0;
8490 btrfs_init_path(&path);
8491 key.objectid = BTRFS_BALANCE_OBJECTID;
8492 key.type = BTRFS_BALANCE_ITEM_KEY;
8494 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
8499 goto reinit_data_reloc;
8504 ret = btrfs_del_item(trans, root, &path);
8507 btrfs_release_path(&path);
8509 key.objectid = BTRFS_TREE_RELOC_OBJECTID;
8510 key.type = BTRFS_ROOT_ITEM_KEY;
8512 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
8516 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8521 ret = btrfs_del_items(trans, root, &path,
8528 btrfs_release_path(&path);
8531 ret = btrfs_search_slot(trans, root, &key, &path,
8538 leaf = path.nodes[0];
8539 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8540 if (key.objectid > BTRFS_TREE_RELOC_OBJECTID)
8542 if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
8547 del_slot = path.slots[0];
8556 ret = btrfs_del_items(trans, root, &path, del_slot, del_nr);
8560 btrfs_release_path(&path);
8563 key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
8564 key.type = BTRFS_ROOT_ITEM_KEY;
8565 key.offset = (u64)-1;
8566 root = btrfs_read_fs_root(fs_info, &key);
8568 fprintf(stderr, "Error reading data reloc tree\n");
8569 ret = PTR_ERR(root);
8572 record_root_in_trans(trans, root);
8573 ret = btrfs_fsck_reinit_root(trans, root, 0);
8576 ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID);
8578 btrfs_release_path(&path);
8582 static int reinit_extent_tree(struct btrfs_trans_handle *trans,
8583 struct btrfs_fs_info *fs_info)
8589 * The only reason we don't do this is because right now we're just
8590 * walking the trees we find and pinning down their bytes, we don't look
8591 * at any of the leaves. In order to do mixed groups we'd have to check
8592 * the leaves of any fs roots and pin down the bytes for any file
8593 * extents we find. Not hard but why do it if we don't have to?
8595 if (btrfs_fs_incompat(fs_info, MIXED_GROUPS)) {
8596 fprintf(stderr, "We don't support re-initing the extent tree "
8597 "for mixed block groups yet, please notify a btrfs "
8598 "developer you want to do this so they can add this "
8599 "functionality.\n");
8604 * first we need to walk all of the trees except the extent tree and pin
8605 * down the bytes that are in use so we don't overwrite any existing
8608 ret = pin_metadata_blocks(fs_info);
8610 fprintf(stderr, "error pinning down used bytes\n");
8615 * Need to drop all the block groups since we're going to recreate all
8618 btrfs_free_block_groups(fs_info);
8619 ret = reset_block_groups(fs_info);
8621 fprintf(stderr, "error resetting the block groups\n");
8625 /* Ok we can allocate now, reinit the extent root */
8626 ret = btrfs_fsck_reinit_root(trans, fs_info->extent_root, 0);
8628 fprintf(stderr, "extent root initialization failed\n");
8630 * When the transaction code is updated we should end the
8631 * transaction, but for now progs only knows about commit so
8632 * just return an error.
8638 * Now we have all the in-memory block groups setup so we can make
8639 * allocations properly, and the metadata we care about is safe since we
8640 * pinned all of it above.
8643 struct btrfs_block_group_cache *cache;
8645 cache = btrfs_lookup_first_block_group(fs_info, start);
8648 start = cache->key.objectid + cache->key.offset;
8649 ret = btrfs_insert_item(trans, fs_info->extent_root,
8650 &cache->key, &cache->item,
8651 sizeof(cache->item));
8653 fprintf(stderr, "Error adding block group\n");
8656 btrfs_extent_post_op(trans, fs_info->extent_root);
8659 ret = reset_balance(trans, fs_info);
8661 fprintf(stderr, "error resetting the pending balance\n");
8666 static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb)
8668 struct btrfs_path path;
8669 struct btrfs_trans_handle *trans;
8670 struct btrfs_key key;
8673 printf("Recowing metadata block %llu\n", eb->start);
8674 key.objectid = btrfs_header_owner(eb);
8675 key.type = BTRFS_ROOT_ITEM_KEY;
8676 key.offset = (u64)-1;
8678 root = btrfs_read_fs_root(root->fs_info, &key);
8680 fprintf(stderr, "Couldn't find owner root %llu\n",
8682 return PTR_ERR(root);
8685 trans = btrfs_start_transaction(root, 1);
8687 return PTR_ERR(trans);
8689 btrfs_init_path(&path);
8690 path.lowest_level = btrfs_header_level(eb);
8691 if (path.lowest_level)
8692 btrfs_node_key_to_cpu(eb, &key, 0);
8694 btrfs_item_key_to_cpu(eb, &key, 0);
8696 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
8697 btrfs_commit_transaction(trans, root);
8698 btrfs_release_path(&path);
8702 static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad)
8704 struct btrfs_path path;
8705 struct btrfs_trans_handle *trans;
8706 struct btrfs_key key;
8709 printf("Deleting bad item [%llu,%u,%llu]\n", bad->key.objectid,
8710 bad->key.type, bad->key.offset);
8711 key.objectid = bad->root_id;
8712 key.type = BTRFS_ROOT_ITEM_KEY;
8713 key.offset = (u64)-1;
8715 root = btrfs_read_fs_root(root->fs_info, &key);
8717 fprintf(stderr, "Couldn't find owner root %llu\n",
8719 return PTR_ERR(root);
8722 trans = btrfs_start_transaction(root, 1);
8724 return PTR_ERR(trans);
8726 btrfs_init_path(&path);
8727 ret = btrfs_search_slot(trans, root, &bad->key, &path, -1, 1);
8733 ret = btrfs_del_item(trans, root, &path);
8735 btrfs_commit_transaction(trans, root);
8736 btrfs_release_path(&path);
8740 static int zero_log_tree(struct btrfs_root *root)
8742 struct btrfs_trans_handle *trans;
8745 trans = btrfs_start_transaction(root, 1);
8746 if (IS_ERR(trans)) {
8747 ret = PTR_ERR(trans);
8750 btrfs_set_super_log_root(root->fs_info->super_copy, 0);
8751 btrfs_set_super_log_root_level(root->fs_info->super_copy, 0);
8752 ret = btrfs_commit_transaction(trans, root);
8756 static int populate_csum(struct btrfs_trans_handle *trans,
8757 struct btrfs_root *csum_root, char *buf, u64 start,
8760 struct btrfs_fs_info *fs_info = csum_root->fs_info;
8765 while (offset < len) {
8766 sectorsize = fs_info->sectorsize;
8767 ret = read_extent_data(fs_info, buf, start + offset,
8771 ret = btrfs_csum_file_block(trans, csum_root, start + len,
8772 start + offset, buf, sectorsize);
8775 offset += sectorsize;
8780 static int fill_csum_tree_from_one_fs_root(struct btrfs_trans_handle *trans,
8781 struct btrfs_root *csum_root,
8782 struct btrfs_root *cur_root)
8784 struct btrfs_path path;
8785 struct btrfs_key key;
8786 struct extent_buffer *node;
8787 struct btrfs_file_extent_item *fi;
8794 buf = malloc(cur_root->fs_info->sectorsize);
8798 btrfs_init_path(&path);
8802 ret = btrfs_search_slot(NULL, cur_root, &key, &path, 0, 0);
8805 /* Iterate all regular file extents and fill its csum */
8807 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
8809 if (key.type != BTRFS_EXTENT_DATA_KEY)
8811 node = path.nodes[0];
8812 slot = path.slots[0];
8813 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
8814 if (btrfs_file_extent_type(node, fi) != BTRFS_FILE_EXTENT_REG)
8816 start = btrfs_file_extent_disk_bytenr(node, fi);
8817 len = btrfs_file_extent_disk_num_bytes(node, fi);
8819 ret = populate_csum(trans, csum_root, buf, start, len);
8826 * TODO: if next leaf is corrupted, jump to nearest next valid
8829 ret = btrfs_next_item(cur_root, &path);
8839 btrfs_release_path(&path);
8844 static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans,
8845 struct btrfs_root *csum_root)
8847 struct btrfs_fs_info *fs_info = csum_root->fs_info;
8848 struct btrfs_path path;
8849 struct btrfs_root *tree_root = fs_info->tree_root;
8850 struct btrfs_root *cur_root;
8851 struct extent_buffer *node;
8852 struct btrfs_key key;
8856 btrfs_init_path(&path);
8857 key.objectid = BTRFS_FS_TREE_OBJECTID;
8859 key.type = BTRFS_ROOT_ITEM_KEY;
8860 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
8869 node = path.nodes[0];
8870 slot = path.slots[0];
8871 btrfs_item_key_to_cpu(node, &key, slot);
8872 if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
8874 if (key.type != BTRFS_ROOT_ITEM_KEY)
8876 if (!is_fstree(key.objectid))
8878 key.offset = (u64)-1;
8880 cur_root = btrfs_read_fs_root(fs_info, &key);
8881 if (IS_ERR(cur_root) || !cur_root) {
8882 fprintf(stderr, "Fail to read fs/subvol tree: %lld\n",
8886 ret = fill_csum_tree_from_one_fs_root(trans, csum_root,
8891 ret = btrfs_next_item(tree_root, &path);
8901 btrfs_release_path(&path);
8905 static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans,
8906 struct btrfs_root *csum_root)
8908 struct btrfs_root *extent_root = csum_root->fs_info->extent_root;
8909 struct btrfs_path path;
8910 struct btrfs_extent_item *ei;
8911 struct extent_buffer *leaf;
8913 struct btrfs_key key;
8916 btrfs_init_path(&path);
8918 key.type = BTRFS_EXTENT_ITEM_KEY;
8920 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
8922 btrfs_release_path(&path);
8926 buf = malloc(csum_root->fs_info->sectorsize);
8928 btrfs_release_path(&path);
8933 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8934 ret = btrfs_next_leaf(extent_root, &path);
8942 leaf = path.nodes[0];
8944 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8945 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
8950 ei = btrfs_item_ptr(leaf, path.slots[0],
8951 struct btrfs_extent_item);
8952 if (!(btrfs_extent_flags(leaf, ei) &
8953 BTRFS_EXTENT_FLAG_DATA)) {
8958 ret = populate_csum(trans, csum_root, buf, key.objectid,
8965 btrfs_release_path(&path);
8971 * Recalculate the csum and put it into the csum tree.
8973 * Extent tree init will wipe out all the extent info, so in that case, we
8974 * can't depend on extent tree, but use fs tree. If search_fs_tree is set, we
8975 * will use fs/subvol trees to init the csum tree.
8977 static int fill_csum_tree(struct btrfs_trans_handle *trans,
8978 struct btrfs_root *csum_root,
8982 return fill_csum_tree_from_fs(trans, csum_root);
8984 return fill_csum_tree_from_extent(trans, csum_root);
8987 static void free_roots_info_cache(void)
8989 if (!roots_info_cache)
8992 while (!cache_tree_empty(roots_info_cache)) {
8993 struct cache_extent *entry;
8994 struct root_item_info *rii;
8996 entry = first_cache_extent(roots_info_cache);
8999 remove_cache_extent(roots_info_cache, entry);
9000 rii = container_of(entry, struct root_item_info, cache_extent);
9004 free(roots_info_cache);
9005 roots_info_cache = NULL;
9008 static int build_roots_info_cache(struct btrfs_fs_info *info)
9011 struct btrfs_key key;
9012 struct extent_buffer *leaf;
9013 struct btrfs_path path;
9015 if (!roots_info_cache) {
9016 roots_info_cache = malloc(sizeof(*roots_info_cache));
9017 if (!roots_info_cache)
9019 cache_tree_init(roots_info_cache);
9022 btrfs_init_path(&path);
9024 key.type = BTRFS_EXTENT_ITEM_KEY;
9026 ret = btrfs_search_slot(NULL, info->extent_root, &key, &path, 0, 0);
9029 leaf = path.nodes[0];
9032 struct btrfs_key found_key;
9033 struct btrfs_extent_item *ei;
9034 struct btrfs_extent_inline_ref *iref;
9035 unsigned long item_end;
9036 int slot = path.slots[0];
9041 struct cache_extent *entry;
9042 struct root_item_info *rii;
9044 if (slot >= btrfs_header_nritems(leaf)) {
9045 ret = btrfs_next_leaf(info->extent_root, &path);
9052 leaf = path.nodes[0];
9053 slot = path.slots[0];
9056 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
9058 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
9059 found_key.type != BTRFS_METADATA_ITEM_KEY)
9062 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
9063 flags = btrfs_extent_flags(leaf, ei);
9064 item_end = (unsigned long)ei + btrfs_item_size_nr(leaf, slot);
9066 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
9067 !(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))
9070 if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
9071 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
9072 level = found_key.offset;
9074 struct btrfs_tree_block_info *binfo;
9076 binfo = (struct btrfs_tree_block_info *)(ei + 1);
9077 iref = (struct btrfs_extent_inline_ref *)(binfo + 1);
9078 level = btrfs_tree_block_level(leaf, binfo);
9082 * It's a valid extent/metadata item that has no inline ref,
9083 * but SHARED_BLOCK_REF or other shared references.
9084 * So we need to do extra check to avoid reading beyond leaf
9087 if ((unsigned long)iref >= item_end)
9091 * For a root extent, it must be of the following type and the
9092 * first (and only one) iref in the item.
9094 type = btrfs_extent_inline_ref_type(leaf, iref);
9095 if (type != BTRFS_TREE_BLOCK_REF_KEY)
9098 root_id = btrfs_extent_inline_ref_offset(leaf, iref);
9099 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9101 rii = malloc(sizeof(struct root_item_info));
9106 rii->cache_extent.start = root_id;
9107 rii->cache_extent.size = 1;
9108 rii->level = (u8)-1;
9109 entry = &rii->cache_extent;
9110 ret = insert_cache_extent(roots_info_cache, entry);
9113 rii = container_of(entry, struct root_item_info,
9117 ASSERT(rii->cache_extent.start == root_id);
9118 ASSERT(rii->cache_extent.size == 1);
9120 if (level > rii->level || rii->level == (u8)-1) {
9122 rii->bytenr = found_key.objectid;
9123 rii->gen = btrfs_extent_generation(leaf, ei);
9124 rii->node_count = 1;
9125 } else if (level == rii->level) {
9133 btrfs_release_path(&path);
9138 static int maybe_repair_root_item(struct btrfs_path *path,
9139 const struct btrfs_key *root_key,
9140 const int read_only_mode)
9142 const u64 root_id = root_key->objectid;
9143 struct cache_extent *entry;
9144 struct root_item_info *rii;
9145 struct btrfs_root_item ri;
9146 unsigned long offset;
9148 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9151 "Error: could not find extent items for root %llu\n",
9152 root_key->objectid);
9156 rii = container_of(entry, struct root_item_info, cache_extent);
9157 ASSERT(rii->cache_extent.start == root_id);
9158 ASSERT(rii->cache_extent.size == 1);
9160 if (rii->node_count != 1) {
9162 "Error: could not find btree root extent for root %llu\n",
9167 offset = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
9168 read_extent_buffer(path->nodes[0], &ri, offset, sizeof(ri));
9170 if (btrfs_root_bytenr(&ri) != rii->bytenr ||
9171 btrfs_root_level(&ri) != rii->level ||
9172 btrfs_root_generation(&ri) != rii->gen) {
9175 * If we're in repair mode but our caller told us to not update
9176 * the root item, i.e. just check if it needs to be updated, don't
9177 * print this message, since the caller will call us again shortly
9178 * for the same root item without read only mode (the caller will
9179 * open a transaction first).
9181 if (!(read_only_mode && repair))
9183 "%sroot item for root %llu,"
9184 " current bytenr %llu, current gen %llu, current level %u,"
9185 " new bytenr %llu, new gen %llu, new level %u\n",
9186 (read_only_mode ? "" : "fixing "),
9188 btrfs_root_bytenr(&ri), btrfs_root_generation(&ri),
9189 btrfs_root_level(&ri),
9190 rii->bytenr, rii->gen, rii->level);
9192 if (btrfs_root_generation(&ri) > rii->gen) {
9194 "root %llu has a root item with a more recent gen (%llu) compared to the found root node (%llu)\n",
9195 root_id, btrfs_root_generation(&ri), rii->gen);
9199 if (!read_only_mode) {
9200 btrfs_set_root_bytenr(&ri, rii->bytenr);
9201 btrfs_set_root_level(&ri, rii->level);
9202 btrfs_set_root_generation(&ri, rii->gen);
9203 write_extent_buffer(path->nodes[0], &ri,
9204 offset, sizeof(ri));
9214 * A regression introduced in the 3.17 kernel (more specifically in 3.17-rc2),
9215 * caused read-only snapshots to be corrupted if they were created at a moment
9216 * when the source subvolume/snapshot had orphan items. The issue was that the
9217 * on-disk root items became incorrect, referring to the pre orphan cleanup root
9218 * node instead of the post orphan cleanup root node.
9219 * So this function, and its callees, just detects and fixes those cases. Even
9220 * though the regression was for read-only snapshots, this function applies to
9221 * any snapshot/subvolume root.
9222 * This must be run before any other repair code - not doing it so, makes other
9223 * repair code delete or modify backrefs in the extent tree for example, which
9224 * will result in an inconsistent fs after repairing the root items.
9226 static int repair_root_items(struct btrfs_fs_info *info)
9228 struct btrfs_path path;
9229 struct btrfs_key key;
9230 struct extent_buffer *leaf;
9231 struct btrfs_trans_handle *trans = NULL;
9236 btrfs_init_path(&path);
9238 ret = build_roots_info_cache(info);
9242 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
9243 key.type = BTRFS_ROOT_ITEM_KEY;
9248 * Avoid opening and committing transactions if a leaf doesn't have
9249 * any root items that need to be fixed, so that we avoid rotating
9250 * backup roots unnecessarily.
9253 trans = btrfs_start_transaction(info->tree_root, 1);
9254 if (IS_ERR(trans)) {
9255 ret = PTR_ERR(trans);
9260 ret = btrfs_search_slot(trans, info->tree_root, &key, &path,
9264 leaf = path.nodes[0];
9267 struct btrfs_key found_key;
9269 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
9270 int no_more_keys = find_next_key(&path, &key);
9272 btrfs_release_path(&path);
9274 ret = btrfs_commit_transaction(trans,
9286 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
9288 if (found_key.type != BTRFS_ROOT_ITEM_KEY)
9290 if (found_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
9293 ret = maybe_repair_root_item(&path, &found_key, trans ? 0 : 1);
9297 if (!trans && repair) {
9300 btrfs_release_path(&path);
9310 free_roots_info_cache();
9311 btrfs_release_path(&path);
9313 btrfs_commit_transaction(trans, info->tree_root);
9320 static int clear_free_space_cache(struct btrfs_fs_info *fs_info)
9322 struct btrfs_trans_handle *trans;
9323 struct btrfs_block_group_cache *bg_cache;
9327 /* Clear all free space cache inodes and its extent data */
9329 bg_cache = btrfs_lookup_first_block_group(fs_info, current);
9332 ret = btrfs_clear_free_space_cache(fs_info, bg_cache);
9335 current = bg_cache->key.objectid + bg_cache->key.offset;
9338 /* Don't forget to set cache_generation to -1 */
9339 trans = btrfs_start_transaction(fs_info->tree_root, 0);
9340 if (IS_ERR(trans)) {
9341 error("failed to update super block cache generation");
9342 return PTR_ERR(trans);
9344 btrfs_set_super_cache_generation(fs_info->super_copy, (u64)-1);
9345 btrfs_commit_transaction(trans, fs_info->tree_root);
9350 static int do_clear_free_space_cache(struct btrfs_fs_info *fs_info,
9355 if (clear_version == 1) {
9356 if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
9358 "free space cache v2 detected, use --clear-space-cache v2");
9362 printf("Clearing free space cache\n");
9363 ret = clear_free_space_cache(fs_info);
9365 error("failed to clear free space cache");
9368 printf("Free space cache cleared\n");
9370 } else if (clear_version == 2) {
9371 if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
9372 printf("no free space cache v2 to clear\n");
9376 printf("Clear free space cache v2\n");
9377 ret = btrfs_clear_free_space_tree(fs_info);
9379 error("failed to clear free space cache v2: %d", ret);
9382 printf("free space cache v2 cleared\n");
9389 const char * const cmd_check_usage[] = {
9390 "btrfs check [options] <device>",
9391 "Check structural integrity of a filesystem (unmounted).",
9392 "Check structural integrity of an unmounted filesystem. Verify internal",
9393 "trees' consistency and item connectivity. In the repair mode try to",
9394 "fix the problems found. ",
9395 "WARNING: the repair mode is considered dangerous",
9397 "-s|--super <superblock> use this superblock copy",
9398 "-b|--backup use the first valid backup root copy",
9399 "--force skip mount checks, repair is not possible",
9400 "--repair try to repair the filesystem",
9401 "--readonly run in read-only mode (default)",
9402 "--init-csum-tree create a new CRC tree",
9403 "--init-extent-tree create a new extent tree",
9404 "--mode <MODE> allows choice of memory/IO trade-offs",
9405 " where MODE is one of:",
9406 " original - read inodes and extents to memory (requires",
9407 " more memory, does less IO)",
9408 " lowmem - try to use less memory but read blocks again",
9410 "--check-data-csum verify checksums of data blocks",
9411 "-Q|--qgroup-report print a report on qgroup consistency",
9412 "-E|--subvol-extents <subvolid>",
9413 " print subvolume extents and sharing state",
9414 "-r|--tree-root <bytenr> use the given bytenr for the tree root",
9415 "--chunk-root <bytenr> use the given bytenr for the chunk tree root",
9416 "-p|--progress indicate progress",
9417 "--clear-space-cache v1|v2 clear space cache for v1 or v2",
9421 int cmd_check(int argc, char **argv)
9423 struct cache_tree root_cache;
9424 struct btrfs_root *root;
9425 struct btrfs_fs_info *info;
9428 u64 tree_root_bytenr = 0;
9429 u64 chunk_root_bytenr = 0;
9430 char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
9434 int init_csum_tree = 0;
9436 int clear_space_cache = 0;
9437 int qgroup_report = 0;
9438 int qgroups_repaired = 0;
9439 unsigned ctree_flags = OPEN_CTREE_EXCLUSIVE;
9444 enum { GETOPT_VAL_REPAIR = 257, GETOPT_VAL_INIT_CSUM,
9445 GETOPT_VAL_INIT_EXTENT, GETOPT_VAL_CHECK_CSUM,
9446 GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE,
9447 GETOPT_VAL_MODE, GETOPT_VAL_CLEAR_SPACE_CACHE,
9449 static const struct option long_options[] = {
9450 { "super", required_argument, NULL, 's' },
9451 { "repair", no_argument, NULL, GETOPT_VAL_REPAIR },
9452 { "readonly", no_argument, NULL, GETOPT_VAL_READONLY },
9453 { "init-csum-tree", no_argument, NULL,
9454 GETOPT_VAL_INIT_CSUM },
9455 { "init-extent-tree", no_argument, NULL,
9456 GETOPT_VAL_INIT_EXTENT },
9457 { "check-data-csum", no_argument, NULL,
9458 GETOPT_VAL_CHECK_CSUM },
9459 { "backup", no_argument, NULL, 'b' },
9460 { "subvol-extents", required_argument, NULL, 'E' },
9461 { "qgroup-report", no_argument, NULL, 'Q' },
9462 { "tree-root", required_argument, NULL, 'r' },
9463 { "chunk-root", required_argument, NULL,
9464 GETOPT_VAL_CHUNK_TREE },
9465 { "progress", no_argument, NULL, 'p' },
9466 { "mode", required_argument, NULL,
9468 { "clear-space-cache", required_argument, NULL,
9469 GETOPT_VAL_CLEAR_SPACE_CACHE},
9470 { "force", no_argument, NULL, GETOPT_VAL_FORCE },
9474 c = getopt_long(argc, argv, "as:br:pEQ", long_options, NULL);
9478 case 'a': /* ignored */ break;
9480 ctree_flags |= OPEN_CTREE_BACKUP_ROOT;
9483 num = arg_strtou64(optarg);
9484 if (num >= BTRFS_SUPER_MIRROR_MAX) {
9486 "super mirror should be less than %d",
9487 BTRFS_SUPER_MIRROR_MAX);
9490 bytenr = btrfs_sb_offset(((int)num));
9491 printf("using SB copy %llu, bytenr %llu\n", num,
9492 (unsigned long long)bytenr);
9498 subvolid = arg_strtou64(optarg);
9501 tree_root_bytenr = arg_strtou64(optarg);
9503 case GETOPT_VAL_CHUNK_TREE:
9504 chunk_root_bytenr = arg_strtou64(optarg);
9507 ctx.progress_enabled = true;
9511 usage(cmd_check_usage);
9512 case GETOPT_VAL_REPAIR:
9513 printf("enabling repair mode\n");
9515 ctree_flags |= OPEN_CTREE_WRITES;
9517 case GETOPT_VAL_READONLY:
9520 case GETOPT_VAL_INIT_CSUM:
9521 printf("Creating a new CRC tree\n");
9524 ctree_flags |= OPEN_CTREE_WRITES;
9526 case GETOPT_VAL_INIT_EXTENT:
9527 init_extent_tree = 1;
9528 ctree_flags |= (OPEN_CTREE_WRITES |
9529 OPEN_CTREE_NO_BLOCK_GROUPS);
9532 case GETOPT_VAL_CHECK_CSUM:
9533 check_data_csum = 1;
9535 case GETOPT_VAL_MODE:
9536 check_mode = parse_check_mode(optarg);
9537 if (check_mode == CHECK_MODE_UNKNOWN) {
9538 error("unknown mode: %s", optarg);
9542 case GETOPT_VAL_CLEAR_SPACE_CACHE:
9543 if (strcmp(optarg, "v1") == 0) {
9544 clear_space_cache = 1;
9545 } else if (strcmp(optarg, "v2") == 0) {
9546 clear_space_cache = 2;
9547 ctree_flags |= OPEN_CTREE_INVALIDATE_FST;
9550 "invalid argument to --clear-space-cache, must be v1 or v2");
9553 ctree_flags |= OPEN_CTREE_WRITES;
9555 case GETOPT_VAL_FORCE:
9561 if (check_argc_exact(argc - optind, 1))
9562 usage(cmd_check_usage);
9564 if (ctx.progress_enabled) {
9565 ctx.tp = TASK_NOTHING;
9566 ctx.info = task_init(print_status_check, print_status_return, &ctx);
9569 /* This check is the only reason for --readonly to exist */
9570 if (readonly && repair) {
9571 error("repair options are not compatible with --readonly");
9576 * experimental and dangerous
9578 if (repair && check_mode == CHECK_MODE_LOWMEM)
9579 warning("low-memory mode repair support is only partial");
9582 cache_tree_init(&root_cache);
9584 ret = check_mounted(argv[optind]);
9587 error("could not check mount status: %s",
9593 "%s is currently mounted, use --force if you really intend to check the filesystem",
9601 error("repair and --force is not yet supported");
9608 "cannot check mount status of %s, the filesystem could be mounted, continuing because of --force",
9612 "filesystem mounted, continuing because of --force");
9614 /* A block device is mounted in exclusive mode by kernel */
9615 ctree_flags &= ~OPEN_CTREE_EXCLUSIVE;
9618 /* only allow partial opening under repair mode */
9620 ctree_flags |= OPEN_CTREE_PARTIAL;
9622 info = open_ctree_fs_info(argv[optind], bytenr, tree_root_bytenr,
9623 chunk_root_bytenr, ctree_flags);
9625 error("cannot open file system");
9632 root = info->fs_root;
9633 uuid_unparse(info->super_copy->fsid, uuidbuf);
9635 printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
9638 * Check the bare minimum before starting anything else that could rely
9639 * on it, namely the tree roots, any local consistency checks
9641 if (!extent_buffer_uptodate(info->tree_root->node) ||
9642 !extent_buffer_uptodate(info->dev_root->node) ||
9643 !extent_buffer_uptodate(info->chunk_root->node)) {
9644 error("critical roots corrupted, unable to check the filesystem");
9650 if (clear_space_cache) {
9651 ret = do_clear_free_space_cache(info, clear_space_cache);
9657 * repair mode will force us to commit transaction which
9658 * will make us fail to load log tree when mounting.
9660 if (repair && btrfs_super_log_root(info->super_copy)) {
9661 ret = ask_user("repair mode will force to clear out log tree, are you sure?");
9667 ret = zero_log_tree(root);
9670 error("failed to zero log tree: %d", ret);
9675 if (qgroup_report) {
9676 printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
9678 ret = qgroup_verify_all(info);
9685 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
9686 subvolid, argv[optind], uuidbuf);
9687 ret = print_extent_state(info, subvolid);
9692 if (init_extent_tree || init_csum_tree) {
9693 struct btrfs_trans_handle *trans;
9695 trans = btrfs_start_transaction(info->extent_root, 0);
9696 if (IS_ERR(trans)) {
9697 error("error starting transaction");
9698 ret = PTR_ERR(trans);
9703 if (init_extent_tree) {
9704 printf("Creating a new extent tree\n");
9705 ret = reinit_extent_tree(trans, info);
9711 if (init_csum_tree) {
9712 printf("Reinitialize checksum tree\n");
9713 ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0);
9715 error("checksum tree initialization failed: %d",
9722 ret = fill_csum_tree(trans, info->csum_root,
9726 error("checksum tree refilling failed: %d", ret);
9731 * Ok now we commit and run the normal fsck, which will add
9732 * extent entries for all of the items it finds.
9734 ret = btrfs_commit_transaction(trans, info->extent_root);
9739 if (!extent_buffer_uptodate(info->extent_root->node)) {
9740 error("critical: extent_root, unable to check the filesystem");
9745 if (!extent_buffer_uptodate(info->csum_root->node)) {
9746 error("critical: csum_root, unable to check the filesystem");
9752 if (!init_extent_tree) {
9753 ret = repair_root_items(info);
9756 error("failed to repair root items: %s", strerror(-ret));
9760 fprintf(stderr, "Fixed %d roots.\n", ret);
9762 } else if (ret > 0) {
9764 "Found %d roots with an outdated root item.\n",
9767 "Please run a filesystem check with the option --repair to fix them.\n");
9774 ret = do_check_chunks_and_extents(info);
9778 "errors found in extent allocation tree or chunk allocation");
9780 /* Only re-check super size after we checked and repaired the fs */
9781 err |= !is_super_size_valid(info);
9783 if (!ctx.progress_enabled) {
9784 if (btrfs_fs_compat_ro(info, FREE_SPACE_TREE))
9785 fprintf(stderr, "checking free space tree\n");
9787 fprintf(stderr, "checking free space cache\n");
9789 ret = check_space_cache(root);
9792 if (btrfs_fs_compat_ro(info, FREE_SPACE_TREE))
9793 error("errors found in free space tree");
9795 error("errors found in free space cache");
9800 * We used to have to have these hole extents in between our real
9801 * extents so if we don't have this flag set we need to make sure there
9802 * are no gaps in the file extents for inodes, otherwise we can just
9803 * ignore it when this happens.
9805 no_holes = btrfs_fs_incompat(root->fs_info, NO_HOLES);
9806 ret = do_check_fs_roots(info, &root_cache);
9809 error("errors found in fs roots");
9813 fprintf(stderr, "checking csums\n");
9814 ret = check_csums(root);
9817 error("errors found in csum tree");
9821 fprintf(stderr, "checking root refs\n");
9822 /* For low memory mode, check_fs_roots_v2 handles root refs */
9823 if (check_mode != CHECK_MODE_LOWMEM) {
9824 ret = check_root_refs(root, &root_cache);
9827 error("errors found in root refs");
9832 while (repair && !list_empty(&root->fs_info->recow_ebs)) {
9833 struct extent_buffer *eb;
9835 eb = list_first_entry(&root->fs_info->recow_ebs,
9836 struct extent_buffer, recow);
9837 list_del_init(&eb->recow);
9838 ret = recow_extent_buffer(root, eb);
9841 error("fails to fix transid errors");
9846 while (!list_empty(&delete_items)) {
9847 struct bad_item *bad;
9849 bad = list_first_entry(&delete_items, struct bad_item, list);
9850 list_del_init(&bad->list);
9852 ret = delete_bad_item(root, bad);
9858 if (info->quota_enabled) {
9859 fprintf(stderr, "checking quota groups\n");
9860 ret = qgroup_verify_all(info);
9863 error("failed to check quota groups");
9867 ret = repair_qgroups(info, &qgroups_repaired);
9870 error("failed to repair quota groups");
9876 if (!list_empty(&root->fs_info->recow_ebs)) {
9877 error("transid errors in file system");
9882 printf("found %llu bytes used, ",
9883 (unsigned long long)bytes_used);
9885 printf("error(s) found\n");
9887 printf("no error found\n");
9888 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
9889 printf("total tree bytes: %llu\n",
9890 (unsigned long long)total_btree_bytes);
9891 printf("total fs tree bytes: %llu\n",
9892 (unsigned long long)total_fs_tree_bytes);
9893 printf("total extent tree bytes: %llu\n",
9894 (unsigned long long)total_extent_tree_bytes);
9895 printf("btree space waste bytes: %llu\n",
9896 (unsigned long long)btree_space_waste);
9897 printf("file data blocks allocated: %llu\n referenced %llu\n",
9898 (unsigned long long)data_bytes_allocated,
9899 (unsigned long long)data_bytes_referenced);
9901 free_qgroup_counts();
9902 free_root_recs_tree(&root_cache);
9906 if (ctx.progress_enabled)
9907 task_deinit(ctx.info);