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);
5348 ret = verify_space_cache(root, cache);
5350 fprintf(stderr, "cache appears valid but isn't %llu\n",
5351 cache->key.objectid);
5356 task_stop(ctx.info);
5358 return error ? -EINVAL : 0;
5361 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
5362 u64 num_bytes, unsigned long leaf_offset,
5363 struct extent_buffer *eb)
5365 struct btrfs_fs_info *fs_info = root->fs_info;
5367 u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
5369 unsigned long csum_offset;
5373 u64 data_checked = 0;
5379 if (num_bytes % fs_info->sectorsize)
5382 data = malloc(num_bytes);
5386 while (offset < num_bytes) {
5389 read_len = num_bytes - offset;
5390 /* read as much space once a time */
5391 ret = read_extent_data(fs_info, data + offset,
5392 bytenr + offset, &read_len, mirror);
5396 /* verify every 4k data's checksum */
5397 while (data_checked < read_len) {
5399 tmp = offset + data_checked;
5401 csum = btrfs_csum_data((char *)data + tmp,
5402 csum, fs_info->sectorsize);
5403 btrfs_csum_final(csum, (u8 *)&csum);
5405 csum_offset = leaf_offset +
5406 tmp / fs_info->sectorsize * csum_size;
5407 read_extent_buffer(eb, (char *)&csum_expected,
5408 csum_offset, csum_size);
5409 /* try another mirror */
5410 if (csum != csum_expected) {
5411 fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
5412 mirror, bytenr + tmp,
5413 csum, csum_expected);
5414 num_copies = btrfs_num_copies(root->fs_info,
5416 if (mirror < num_copies - 1) {
5421 data_checked += fs_info->sectorsize;
5430 static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
5433 struct btrfs_path path;
5434 struct extent_buffer *leaf;
5435 struct btrfs_key key;
5438 btrfs_init_path(&path);
5439 key.objectid = bytenr;
5440 key.type = BTRFS_EXTENT_ITEM_KEY;
5441 key.offset = (u64)-1;
5444 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
5447 fprintf(stderr, "Error looking up extent record %d\n", ret);
5448 btrfs_release_path(&path);
5451 if (path.slots[0] > 0) {
5454 ret = btrfs_prev_leaf(root, &path);
5457 } else if (ret > 0) {
5464 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5467 * Block group items come before extent items if they have the same
5468 * bytenr, so walk back one more just in case. Dear future traveller,
5469 * first congrats on mastering time travel. Now if it's not too much
5470 * trouble could you go back to 2006 and tell Chris to make the
5471 * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
5472 * EXTENT_ITEM_KEY please?
5474 while (key.type > BTRFS_EXTENT_ITEM_KEY) {
5475 if (path.slots[0] > 0) {
5478 ret = btrfs_prev_leaf(root, &path);
5481 } else if (ret > 0) {
5486 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5490 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5491 ret = btrfs_next_leaf(root, &path);
5493 fprintf(stderr, "Error going to next leaf "
5495 btrfs_release_path(&path);
5501 leaf = path.nodes[0];
5502 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5503 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
5507 if (key.objectid + key.offset < bytenr) {
5511 if (key.objectid > bytenr + num_bytes)
5514 if (key.objectid == bytenr) {
5515 if (key.offset >= num_bytes) {
5519 num_bytes -= key.offset;
5520 bytenr += key.offset;
5521 } else if (key.objectid < bytenr) {
5522 if (key.objectid + key.offset >= bytenr + num_bytes) {
5526 num_bytes = (bytenr + num_bytes) -
5527 (key.objectid + key.offset);
5528 bytenr = key.objectid + key.offset;
5530 if (key.objectid + key.offset < bytenr + num_bytes) {
5531 u64 new_start = key.objectid + key.offset;
5532 u64 new_bytes = bytenr + num_bytes - new_start;
5535 * Weird case, the extent is in the middle of
5536 * our range, we'll have to search one side
5537 * and then the other. Not sure if this happens
5538 * in real life, but no harm in coding it up
5539 * anyway just in case.
5541 btrfs_release_path(&path);
5542 ret = check_extent_exists(root, new_start,
5545 fprintf(stderr, "Right section didn't "
5549 num_bytes = key.objectid - bytenr;
5552 num_bytes = key.objectid - bytenr;
5559 if (num_bytes && !ret) {
5561 "there are no extents for csum range %llu-%llu\n",
5562 bytenr, bytenr+num_bytes);
5566 btrfs_release_path(&path);
5570 static int check_csums(struct btrfs_root *root)
5572 struct btrfs_path path;
5573 struct extent_buffer *leaf;
5574 struct btrfs_key key;
5575 u64 offset = 0, num_bytes = 0;
5576 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
5580 unsigned long leaf_offset;
5582 root = root->fs_info->csum_root;
5583 if (!extent_buffer_uptodate(root->node)) {
5584 fprintf(stderr, "No valid csum tree found\n");
5588 btrfs_init_path(&path);
5589 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
5590 key.type = BTRFS_EXTENT_CSUM_KEY;
5592 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
5594 fprintf(stderr, "Error searching csum tree %d\n", ret);
5595 btrfs_release_path(&path);
5599 if (ret > 0 && path.slots[0])
5604 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5605 ret = btrfs_next_leaf(root, &path);
5607 fprintf(stderr, "Error going to next leaf "
5614 leaf = path.nodes[0];
5616 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5617 if (key.type != BTRFS_EXTENT_CSUM_KEY) {
5622 data_len = (btrfs_item_size_nr(leaf, path.slots[0]) /
5623 csum_size) * root->fs_info->sectorsize;
5624 if (!check_data_csum)
5625 goto skip_csum_check;
5626 leaf_offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
5627 ret = check_extent_csums(root, key.offset, data_len,
5633 offset = key.offset;
5634 } else if (key.offset != offset + num_bytes) {
5635 ret = check_extent_exists(root, offset, num_bytes);
5638 "csum exists for %llu-%llu but there is no extent record\n",
5639 offset, offset+num_bytes);
5642 offset = key.offset;
5645 num_bytes += data_len;
5649 btrfs_release_path(&path);
5653 static int is_dropped_key(struct btrfs_key *key,
5654 struct btrfs_key *drop_key)
5656 if (key->objectid < drop_key->objectid)
5658 else if (key->objectid == drop_key->objectid) {
5659 if (key->type < drop_key->type)
5661 else if (key->type == drop_key->type) {
5662 if (key->offset < drop_key->offset)
5670 * Here are the rules for FULL_BACKREF.
5672 * 1) If BTRFS_HEADER_FLAG_RELOC is set then we have FULL_BACKREF set.
5673 * 2) If btrfs_header_owner(buf) no longer points to buf then we have
5675 * 3) We cowed the block walking down a reloc tree. This is impossible to tell
5676 * if it happened after the relocation occurred since we'll have dropped the
5677 * reloc root, so it's entirely possible to have FULL_BACKREF set on buf and
5678 * have no real way to know for sure.
5680 * We process the blocks one root at a time, and we start from the lowest root
5681 * objectid and go to the highest. So we can just lookup the owner backref for
5682 * the record and if we don't find it then we know it doesn't exist and we have
5685 * FIXME: if we ever start reclaiming root objectid's then we need to fix this
5686 * assumption and simply indicate that we _think_ that the FULL BACKREF needs to
5687 * be set or not and then we can check later once we've gathered all the refs.
5689 static int calc_extent_flag(struct cache_tree *extent_cache,
5690 struct extent_buffer *buf,
5691 struct root_item_record *ri,
5694 struct extent_record *rec;
5695 struct cache_extent *cache;
5696 struct tree_backref *tback;
5699 cache = lookup_cache_extent(extent_cache, buf->start, 1);
5700 /* we have added this extent before */
5704 rec = container_of(cache, struct extent_record, cache);
5707 * Except file/reloc tree, we can not have
5710 if (ri->objectid < BTRFS_FIRST_FREE_OBJECTID)
5715 if (buf->start == ri->bytenr)
5718 if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
5721 owner = btrfs_header_owner(buf);
5722 if (owner == ri->objectid)
5725 tback = find_tree_backref(rec, 0, owner);
5730 if (rec->flag_block_full_backref != FLAG_UNSET &&
5731 rec->flag_block_full_backref != 0)
5732 rec->bad_full_backref = 1;
5735 *flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5736 if (rec->flag_block_full_backref != FLAG_UNSET &&
5737 rec->flag_block_full_backref != 1)
5738 rec->bad_full_backref = 1;
5742 static void report_mismatch_key_root(u8 key_type, u64 rootid)
5744 fprintf(stderr, "Invalid key type(");
5745 print_key_type(stderr, 0, key_type);
5746 fprintf(stderr, ") found in root(");
5747 print_objectid(stderr, rootid, 0);
5748 fprintf(stderr, ")\n");
5752 * Check if the key is valid with its extent buffer.
5754 * This is a early check in case invalid key exists in a extent buffer
5755 * This is not comprehensive yet, but should prevent wrong key/item passed
5758 static int check_type_with_root(u64 rootid, u8 key_type)
5761 /* Only valid in chunk tree */
5762 case BTRFS_DEV_ITEM_KEY:
5763 case BTRFS_CHUNK_ITEM_KEY:
5764 if (rootid != BTRFS_CHUNK_TREE_OBJECTID)
5767 /* valid in csum and log tree */
5768 case BTRFS_CSUM_TREE_OBJECTID:
5769 if (!(rootid == BTRFS_TREE_LOG_OBJECTID ||
5773 case BTRFS_EXTENT_ITEM_KEY:
5774 case BTRFS_METADATA_ITEM_KEY:
5775 case BTRFS_BLOCK_GROUP_ITEM_KEY:
5776 if (rootid != BTRFS_EXTENT_TREE_OBJECTID)
5779 case BTRFS_ROOT_ITEM_KEY:
5780 if (rootid != BTRFS_ROOT_TREE_OBJECTID)
5783 case BTRFS_DEV_EXTENT_KEY:
5784 if (rootid != BTRFS_DEV_TREE_OBJECTID)
5790 report_mismatch_key_root(key_type, rootid);
5794 static int run_next_block(struct btrfs_root *root,
5795 struct block_info *bits,
5798 struct cache_tree *pending,
5799 struct cache_tree *seen,
5800 struct cache_tree *reada,
5801 struct cache_tree *nodes,
5802 struct cache_tree *extent_cache,
5803 struct cache_tree *chunk_cache,
5804 struct rb_root *dev_cache,
5805 struct block_group_tree *block_group_cache,
5806 struct device_extent_tree *dev_extent_cache,
5807 struct root_item_record *ri)
5809 struct btrfs_fs_info *fs_info = root->fs_info;
5810 struct extent_buffer *buf;
5811 struct extent_record *rec = NULL;
5822 struct btrfs_key key;
5823 struct cache_extent *cache;
5826 nritems = pick_next_pending(pending, reada, nodes, *last, bits,
5827 bits_nr, &reada_bits);
5832 for (i = 0; i < nritems; i++) {
5833 ret = add_cache_extent(reada, bits[i].start,
5838 /* fixme, get the parent transid */
5839 readahead_tree_block(fs_info, bits[i].start, 0);
5842 *last = bits[0].start;
5843 bytenr = bits[0].start;
5844 size = bits[0].size;
5846 cache = lookup_cache_extent(pending, bytenr, size);
5848 remove_cache_extent(pending, cache);
5851 cache = lookup_cache_extent(reada, bytenr, size);
5853 remove_cache_extent(reada, cache);
5856 cache = lookup_cache_extent(nodes, bytenr, size);
5858 remove_cache_extent(nodes, cache);
5861 cache = lookup_cache_extent(extent_cache, bytenr, size);
5863 rec = container_of(cache, struct extent_record, cache);
5864 gen = rec->parent_generation;
5867 /* fixme, get the real parent transid */
5868 buf = read_tree_block(root->fs_info, bytenr, gen);
5869 if (!extent_buffer_uptodate(buf)) {
5870 record_bad_block_io(root->fs_info,
5871 extent_cache, bytenr, size);
5875 nritems = btrfs_header_nritems(buf);
5878 if (!init_extent_tree) {
5879 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
5880 btrfs_header_level(buf), 1, NULL,
5883 ret = calc_extent_flag(extent_cache, buf, ri, &flags);
5885 fprintf(stderr, "Couldn't calc extent flags\n");
5886 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5891 ret = calc_extent_flag(extent_cache, buf, ri, &flags);
5893 fprintf(stderr, "Couldn't calc extent flags\n");
5894 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5898 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5900 ri->objectid != BTRFS_TREE_RELOC_OBJECTID &&
5901 ri->objectid == btrfs_header_owner(buf)) {
5903 * Ok we got to this block from it's original owner and
5904 * we have FULL_BACKREF set. Relocation can leave
5905 * converted blocks over so this is altogether possible,
5906 * however it's not possible if the generation > the
5907 * last snapshot, so check for this case.
5909 if (!btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC) &&
5910 btrfs_header_generation(buf) > ri->last_snapshot) {
5911 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
5912 rec->bad_full_backref = 1;
5917 (ri->objectid == BTRFS_TREE_RELOC_OBJECTID ||
5918 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) {
5919 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5920 rec->bad_full_backref = 1;
5924 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5925 rec->flag_block_full_backref = 1;
5929 rec->flag_block_full_backref = 0;
5931 owner = btrfs_header_owner(buf);
5934 ret = check_block(root, extent_cache, buf, flags);
5938 if (btrfs_is_leaf(buf)) {
5939 btree_space_waste += btrfs_leaf_free_space(root, buf);
5940 for (i = 0; i < nritems; i++) {
5941 struct btrfs_file_extent_item *fi;
5943 btrfs_item_key_to_cpu(buf, &key, i);
5945 * Check key type against the leaf owner.
5946 * Could filter quite a lot of early error if
5949 if (check_type_with_root(btrfs_header_owner(buf),
5951 fprintf(stderr, "ignoring invalid key\n");
5954 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
5955 process_extent_item(root, extent_cache, buf,
5959 if (key.type == BTRFS_METADATA_ITEM_KEY) {
5960 process_extent_item(root, extent_cache, buf,
5964 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
5966 btrfs_item_size_nr(buf, i);
5969 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
5970 process_chunk_item(chunk_cache, &key, buf, i);
5973 if (key.type == BTRFS_DEV_ITEM_KEY) {
5974 process_device_item(dev_cache, &key, buf, i);
5977 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
5978 process_block_group_item(block_group_cache,
5982 if (key.type == BTRFS_DEV_EXTENT_KEY) {
5983 process_device_extent_item(dev_extent_cache,
5988 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
5989 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5990 process_extent_ref_v0(extent_cache, buf, i);
5997 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
5998 ret = add_tree_backref(extent_cache,
5999 key.objectid, 0, key.offset, 0);
6002 "add_tree_backref failed (leaf tree block): %s",
6006 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
6007 ret = add_tree_backref(extent_cache,
6008 key.objectid, key.offset, 0, 0);
6011 "add_tree_backref failed (leaf shared block): %s",
6015 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
6016 struct btrfs_extent_data_ref *ref;
6018 ref = btrfs_item_ptr(buf, i,
6019 struct btrfs_extent_data_ref);
6020 add_data_backref(extent_cache,
6022 btrfs_extent_data_ref_root(buf, ref),
6023 btrfs_extent_data_ref_objectid(buf,
6025 btrfs_extent_data_ref_offset(buf, ref),
6026 btrfs_extent_data_ref_count(buf, ref),
6027 0, root->fs_info->sectorsize);
6030 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
6031 struct btrfs_shared_data_ref *ref;
6033 ref = btrfs_item_ptr(buf, i,
6034 struct btrfs_shared_data_ref);
6035 add_data_backref(extent_cache,
6036 key.objectid, key.offset, 0, 0, 0,
6037 btrfs_shared_data_ref_count(buf, ref),
6038 0, root->fs_info->sectorsize);
6041 if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
6042 struct bad_item *bad;
6044 if (key.objectid == BTRFS_ORPHAN_OBJECTID)
6048 bad = malloc(sizeof(struct bad_item));
6051 INIT_LIST_HEAD(&bad->list);
6052 memcpy(&bad->key, &key,
6053 sizeof(struct btrfs_key));
6054 bad->root_id = owner;
6055 list_add_tail(&bad->list, &delete_items);
6058 if (key.type != BTRFS_EXTENT_DATA_KEY)
6060 fi = btrfs_item_ptr(buf, i,
6061 struct btrfs_file_extent_item);
6062 if (btrfs_file_extent_type(buf, fi) ==
6063 BTRFS_FILE_EXTENT_INLINE)
6065 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
6068 data_bytes_allocated +=
6069 btrfs_file_extent_disk_num_bytes(buf, fi);
6070 if (data_bytes_allocated < root->fs_info->sectorsize)
6073 data_bytes_referenced +=
6074 btrfs_file_extent_num_bytes(buf, fi);
6075 add_data_backref(extent_cache,
6076 btrfs_file_extent_disk_bytenr(buf, fi),
6077 parent, owner, key.objectid, key.offset -
6078 btrfs_file_extent_offset(buf, fi), 1, 1,
6079 btrfs_file_extent_disk_num_bytes(buf, fi));
6083 struct btrfs_key first_key;
6085 first_key.objectid = 0;
6088 btrfs_item_key_to_cpu(buf, &first_key, 0);
6089 level = btrfs_header_level(buf);
6090 for (i = 0; i < nritems; i++) {
6091 struct extent_record tmpl;
6093 ptr = btrfs_node_blockptr(buf, i);
6094 size = root->fs_info->nodesize;
6095 btrfs_node_key_to_cpu(buf, &key, i);
6097 if ((level == ri->drop_level)
6098 && is_dropped_key(&key, &ri->drop_key)) {
6103 memset(&tmpl, 0, sizeof(tmpl));
6104 btrfs_cpu_key_to_disk(&tmpl.parent_key, &key);
6105 tmpl.parent_generation =
6106 btrfs_node_ptr_generation(buf, i);
6111 tmpl.max_size = size;
6112 ret = add_extent_rec(extent_cache, &tmpl);
6116 ret = add_tree_backref(extent_cache, ptr, parent,
6120 "add_tree_backref failed (non-leaf block): %s",
6126 add_pending(nodes, seen, ptr, size);
6128 add_pending(pending, seen, ptr, size);
6130 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(fs_info) -
6131 nritems) * sizeof(struct btrfs_key_ptr);
6133 total_btree_bytes += buf->len;
6134 if (fs_root_objectid(btrfs_header_owner(buf)))
6135 total_fs_tree_bytes += buf->len;
6136 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
6137 total_extent_tree_bytes += buf->len;
6139 free_extent_buffer(buf);
6143 static int add_root_to_pending(struct extent_buffer *buf,
6144 struct cache_tree *extent_cache,
6145 struct cache_tree *pending,
6146 struct cache_tree *seen,
6147 struct cache_tree *nodes,
6150 struct extent_record tmpl;
6153 if (btrfs_header_level(buf) > 0)
6154 add_pending(nodes, seen, buf->start, buf->len);
6156 add_pending(pending, seen, buf->start, buf->len);
6158 memset(&tmpl, 0, sizeof(tmpl));
6159 tmpl.start = buf->start;
6164 tmpl.max_size = buf->len;
6165 add_extent_rec(extent_cache, &tmpl);
6167 if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
6168 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
6169 ret = add_tree_backref(extent_cache, buf->start, buf->start,
6172 ret = add_tree_backref(extent_cache, buf->start, 0, objectid,
6177 /* as we fix the tree, we might be deleting blocks that
6178 * we're tracking for repair. This hook makes sure we
6179 * remove any backrefs for blocks as we are fixing them.
6181 static int free_extent_hook(struct btrfs_trans_handle *trans,
6182 struct btrfs_root *root,
6183 u64 bytenr, u64 num_bytes, u64 parent,
6184 u64 root_objectid, u64 owner, u64 offset,
6187 struct extent_record *rec;
6188 struct cache_extent *cache;
6190 struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
6192 is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
6193 cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
6197 rec = container_of(cache, struct extent_record, cache);
6199 struct data_backref *back;
6201 back = find_data_backref(rec, parent, root_objectid, owner,
6202 offset, 1, bytenr, num_bytes);
6205 if (back->node.found_ref) {
6206 back->found_ref -= refs_to_drop;
6208 rec->refs -= refs_to_drop;
6210 if (back->node.found_extent_tree) {
6211 back->num_refs -= refs_to_drop;
6212 if (rec->extent_item_refs)
6213 rec->extent_item_refs -= refs_to_drop;
6215 if (back->found_ref == 0)
6216 back->node.found_ref = 0;
6217 if (back->num_refs == 0)
6218 back->node.found_extent_tree = 0;
6220 if (!back->node.found_extent_tree && back->node.found_ref) {
6221 rb_erase(&back->node.node, &rec->backref_tree);
6225 struct tree_backref *back;
6227 back = find_tree_backref(rec, parent, root_objectid);
6230 if (back->node.found_ref) {
6233 back->node.found_ref = 0;
6235 if (back->node.found_extent_tree) {
6236 if (rec->extent_item_refs)
6237 rec->extent_item_refs--;
6238 back->node.found_extent_tree = 0;
6240 if (!back->node.found_extent_tree && back->node.found_ref) {
6241 rb_erase(&back->node.node, &rec->backref_tree);
6245 maybe_free_extent_rec(extent_cache, rec);
6250 static int delete_extent_records(struct btrfs_trans_handle *trans,
6251 struct btrfs_root *root,
6252 struct btrfs_path *path,
6255 struct btrfs_key key;
6256 struct btrfs_key found_key;
6257 struct extent_buffer *leaf;
6262 key.objectid = bytenr;
6264 key.offset = (u64)-1;
6267 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
6274 if (path->slots[0] == 0)
6280 leaf = path->nodes[0];
6281 slot = path->slots[0];
6283 btrfs_item_key_to_cpu(leaf, &found_key, slot);
6284 if (found_key.objectid != bytenr)
6287 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
6288 found_key.type != BTRFS_METADATA_ITEM_KEY &&
6289 found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
6290 found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
6291 found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
6292 found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
6293 found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
6294 btrfs_release_path(path);
6295 if (found_key.type == 0) {
6296 if (found_key.offset == 0)
6298 key.offset = found_key.offset - 1;
6299 key.type = found_key.type;
6301 key.type = found_key.type - 1;
6302 key.offset = (u64)-1;
6307 "repair deleting extent record: key [%llu,%u,%llu]\n",
6308 found_key.objectid, found_key.type, found_key.offset);
6310 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
6313 btrfs_release_path(path);
6315 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
6316 found_key.type == BTRFS_METADATA_ITEM_KEY) {
6317 u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
6318 found_key.offset : root->fs_info->nodesize;
6320 ret = btrfs_update_block_group(root, bytenr,
6327 btrfs_release_path(path);
6332 * for a single backref, this will allocate a new extent
6333 * and add the backref to it.
6335 static int record_extent(struct btrfs_trans_handle *trans,
6336 struct btrfs_fs_info *info,
6337 struct btrfs_path *path,
6338 struct extent_record *rec,
6339 struct extent_backref *back,
6340 int allocated, u64 flags)
6343 struct btrfs_root *extent_root = info->extent_root;
6344 struct extent_buffer *leaf;
6345 struct btrfs_key ins_key;
6346 struct btrfs_extent_item *ei;
6347 struct data_backref *dback;
6348 struct btrfs_tree_block_info *bi;
6351 rec->max_size = max_t(u64, rec->max_size,
6355 u32 item_size = sizeof(*ei);
6358 item_size += sizeof(*bi);
6360 ins_key.objectid = rec->start;
6361 ins_key.offset = rec->max_size;
6362 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
6364 ret = btrfs_insert_empty_item(trans, extent_root, path,
6365 &ins_key, item_size);
6369 leaf = path->nodes[0];
6370 ei = btrfs_item_ptr(leaf, path->slots[0],
6371 struct btrfs_extent_item);
6373 btrfs_set_extent_refs(leaf, ei, 0);
6374 btrfs_set_extent_generation(leaf, ei, rec->generation);
6376 if (back->is_data) {
6377 btrfs_set_extent_flags(leaf, ei,
6378 BTRFS_EXTENT_FLAG_DATA);
6380 struct btrfs_disk_key copy_key;
6382 bi = (struct btrfs_tree_block_info *)(ei + 1);
6383 memset_extent_buffer(leaf, 0, (unsigned long)bi,
6386 btrfs_set_disk_key_objectid(©_key,
6387 rec->info_objectid);
6388 btrfs_set_disk_key_type(©_key, 0);
6389 btrfs_set_disk_key_offset(©_key, 0);
6391 btrfs_set_tree_block_level(leaf, bi, rec->info_level);
6392 btrfs_set_tree_block_key(leaf, bi, ©_key);
6394 btrfs_set_extent_flags(leaf, ei,
6395 flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
6398 btrfs_mark_buffer_dirty(leaf);
6399 ret = btrfs_update_block_group(extent_root, rec->start,
6400 rec->max_size, 1, 0);
6403 btrfs_release_path(path);
6406 if (back->is_data) {
6410 dback = to_data_backref(back);
6411 if (back->full_backref)
6412 parent = dback->parent;
6416 for (i = 0; i < dback->found_ref; i++) {
6417 /* if parent != 0, we're doing a full backref
6418 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
6419 * just makes the backref allocator create a data
6422 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6423 rec->start, rec->max_size,
6427 BTRFS_FIRST_FREE_OBJECTID :
6434 "adding new data backref on %llu %s %llu owner %llu offset %llu found %d\n",
6435 (unsigned long long)rec->start,
6436 back->full_backref ? "parent" : "root",
6437 back->full_backref ? (unsigned long long)parent :
6438 (unsigned long long)dback->root,
6439 (unsigned long long)dback->owner,
6440 (unsigned long long)dback->offset, dback->found_ref);
6443 struct tree_backref *tback;
6445 tback = to_tree_backref(back);
6446 if (back->full_backref)
6447 parent = tback->parent;
6451 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6452 rec->start, rec->max_size,
6453 parent, tback->root, 0, 0);
6455 "adding new tree backref on start %llu len %llu parent %llu root %llu\n",
6456 rec->start, rec->max_size, parent, tback->root);
6459 btrfs_release_path(path);
6463 static struct extent_entry *find_entry(struct list_head *entries,
6464 u64 bytenr, u64 bytes)
6466 struct extent_entry *entry = NULL;
6468 list_for_each_entry(entry, entries, list) {
6469 if (entry->bytenr == bytenr && entry->bytes == bytes)
6476 static struct extent_entry *find_most_right_entry(struct list_head *entries)
6478 struct extent_entry *entry, *best = NULL, *prev = NULL;
6480 list_for_each_entry(entry, entries, list) {
6482 * If there are as many broken entries as entries then we know
6483 * not to trust this particular entry.
6485 if (entry->broken == entry->count)
6489 * Special case, when there are only two entries and 'best' is
6499 * If our current entry == best then we can't be sure our best
6500 * is really the best, so we need to keep searching.
6502 if (best && best->count == entry->count) {
6508 /* Prev == entry, not good enough, have to keep searching */
6509 if (!prev->broken && prev->count == entry->count)
6513 best = (prev->count > entry->count) ? prev : entry;
6514 else if (best->count < entry->count)
6522 static int repair_ref(struct btrfs_fs_info *info, struct btrfs_path *path,
6523 struct data_backref *dback, struct extent_entry *entry)
6525 struct btrfs_trans_handle *trans;
6526 struct btrfs_root *root;
6527 struct btrfs_file_extent_item *fi;
6528 struct extent_buffer *leaf;
6529 struct btrfs_key key;
6533 key.objectid = dback->root;
6534 key.type = BTRFS_ROOT_ITEM_KEY;
6535 key.offset = (u64)-1;
6536 root = btrfs_read_fs_root(info, &key);
6538 fprintf(stderr, "Couldn't find root for our ref\n");
6543 * The backref points to the original offset of the extent if it was
6544 * split, so we need to search down to the offset we have and then walk
6545 * forward until we find the backref we're looking for.
6547 key.objectid = dback->owner;
6548 key.type = BTRFS_EXTENT_DATA_KEY;
6549 key.offset = dback->offset;
6550 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6552 fprintf(stderr, "Error looking up ref %d\n", ret);
6557 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6558 ret = btrfs_next_leaf(root, path);
6560 fprintf(stderr, "Couldn't find our ref, next\n");
6564 leaf = path->nodes[0];
6565 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6566 if (key.objectid != dback->owner ||
6567 key.type != BTRFS_EXTENT_DATA_KEY) {
6568 fprintf(stderr, "Couldn't find our ref, search\n");
6571 fi = btrfs_item_ptr(leaf, path->slots[0],
6572 struct btrfs_file_extent_item);
6573 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
6574 bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
6576 if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
6581 btrfs_release_path(path);
6583 trans = btrfs_start_transaction(root, 1);
6585 return PTR_ERR(trans);
6588 * Ok we have the key of the file extent we want to fix, now we can cow
6589 * down to the thing and fix it.
6591 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
6593 fprintf(stderr, "error cowing down to ref [%llu,%u,%llu]: %d\n",
6594 key.objectid, key.type, key.offset, ret);
6599 "well that's odd, we just found this key [%llu,%u,%llu]\n",
6600 key.objectid, key.type, key.offset);
6604 leaf = path->nodes[0];
6605 fi = btrfs_item_ptr(leaf, path->slots[0],
6606 struct btrfs_file_extent_item);
6608 if (btrfs_file_extent_compression(leaf, fi) &&
6609 dback->disk_bytenr != entry->bytenr) {
6611 "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",
6612 dback->disk_bytenr);
6617 if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
6618 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6619 } else if (dback->disk_bytenr > entry->bytenr) {
6620 u64 off_diff, offset;
6622 off_diff = dback->disk_bytenr - entry->bytenr;
6623 offset = btrfs_file_extent_offset(leaf, fi);
6624 if (dback->disk_bytenr + offset +
6625 btrfs_file_extent_num_bytes(leaf, fi) >
6626 entry->bytenr + entry->bytes) {
6628 "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",
6629 dback->disk_bytenr);
6634 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6635 btrfs_set_file_extent_offset(leaf, fi, offset);
6636 } else if (dback->disk_bytenr < entry->bytenr) {
6639 offset = btrfs_file_extent_offset(leaf, fi);
6640 if (dback->disk_bytenr + offset < entry->bytenr) {
6642 "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",
6643 dback->disk_bytenr);
6648 offset += dback->disk_bytenr;
6649 offset -= entry->bytenr;
6650 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6651 btrfs_set_file_extent_offset(leaf, fi, offset);
6654 btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
6657 * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
6658 * only do this if we aren't using compression, otherwise it's a
6661 if (!btrfs_file_extent_compression(leaf, fi))
6662 btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
6664 printf("ram bytes may be wrong?\n");
6665 btrfs_mark_buffer_dirty(leaf);
6667 err = btrfs_commit_transaction(trans, root);
6668 btrfs_release_path(path);
6669 return ret ? ret : err;
6672 static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
6673 struct extent_record *rec)
6675 struct extent_backref *back, *tmp;
6676 struct data_backref *dback;
6677 struct extent_entry *entry, *best = NULL;
6680 int broken_entries = 0;
6685 * Metadata is easy and the backrefs should always agree on bytenr and
6686 * size, if not we've got bigger issues.
6691 rbtree_postorder_for_each_entry_safe(back, tmp,
6692 &rec->backref_tree, node) {
6693 if (back->full_backref || !back->is_data)
6696 dback = to_data_backref(back);
6699 * We only pay attention to backrefs that we found a real
6702 if (dback->found_ref == 0)
6706 * For now we only catch when the bytes don't match, not the
6707 * bytenr. We can easily do this at the same time, but I want
6708 * to have a fs image to test on before we just add repair
6709 * functionality willy-nilly so we know we won't screw up the
6713 entry = find_entry(&entries, dback->disk_bytenr,
6716 entry = malloc(sizeof(struct extent_entry));
6721 memset(entry, 0, sizeof(*entry));
6722 entry->bytenr = dback->disk_bytenr;
6723 entry->bytes = dback->bytes;
6724 list_add_tail(&entry->list, &entries);
6729 * If we only have on entry we may think the entries agree when
6730 * in reality they don't so we have to do some extra checking.
6732 if (dback->disk_bytenr != rec->start ||
6733 dback->bytes != rec->nr || back->broken)
6744 /* Yay all the backrefs agree, carry on good sir */
6745 if (nr_entries <= 1 && !mismatch)
6749 "attempting to repair backref discrepency for bytenr %llu\n",
6753 * First we want to see if the backrefs can agree amongst themselves who
6754 * is right, so figure out which one of the entries has the highest
6757 best = find_most_right_entry(&entries);
6760 * Ok so we may have an even split between what the backrefs think, so
6761 * this is where we use the extent ref to see what it thinks.
6764 entry = find_entry(&entries, rec->start, rec->nr);
6765 if (!entry && (!broken_entries || !rec->found_rec)) {
6767 "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",
6768 rec->start, rec->nr);
6771 } else if (!entry) {
6773 * Ok our backrefs were broken, we'll assume this is the
6774 * correct value and add an entry for this range.
6776 entry = malloc(sizeof(struct extent_entry));
6781 memset(entry, 0, sizeof(*entry));
6782 entry->bytenr = rec->start;
6783 entry->bytes = rec->nr;
6784 list_add_tail(&entry->list, &entries);
6788 best = find_most_right_entry(&entries);
6791 "backrefs and extent record evenly split on who is right, this is going to require user input to fix bytenr %llu bytes %llu\n",
6792 rec->start, rec->nr);
6799 * I don't think this can happen currently as we'll abort() if we catch
6800 * this case higher up, but in case somebody removes that we still can't
6801 * deal with it properly here yet, so just bail out of that's the case.
6803 if (best->bytenr != rec->start) {
6805 "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",
6806 rec->start, rec->nr);
6812 * Ok great we all agreed on an extent record, let's go find the real
6813 * references and fix up the ones that don't match.
6815 rbtree_postorder_for_each_entry_safe(back, tmp,
6816 &rec->backref_tree, node) {
6817 if (back->full_backref || !back->is_data)
6820 dback = to_data_backref(back);
6823 * Still ignoring backrefs that don't have a real ref attached
6826 if (dback->found_ref == 0)
6829 if (dback->bytes == best->bytes &&
6830 dback->disk_bytenr == best->bytenr)
6833 ret = repair_ref(info, path, dback, best);
6839 * Ok we messed with the actual refs, which means we need to drop our
6840 * entire cache and go back and rescan. I know this is a huge pain and
6841 * adds a lot of extra work, but it's the only way to be safe. Once all
6842 * the backrefs agree we may not need to do anything to the extent
6847 while (!list_empty(&entries)) {
6848 entry = list_entry(entries.next, struct extent_entry, list);
6849 list_del_init(&entry->list);
6855 static int process_duplicates(struct cache_tree *extent_cache,
6856 struct extent_record *rec)
6858 struct extent_record *good, *tmp;
6859 struct cache_extent *cache;
6863 * If we found a extent record for this extent then return, or if we
6864 * have more than one duplicate we are likely going to need to delete
6867 if (rec->found_rec || rec->num_duplicates > 1)
6870 /* Shouldn't happen but just in case */
6871 BUG_ON(!rec->num_duplicates);
6874 * So this happens if we end up with a backref that doesn't match the
6875 * actual extent entry. So either the backref is bad or the extent
6876 * entry is bad. Either way we want to have the extent_record actually
6877 * reflect what we found in the extent_tree, so we need to take the
6878 * duplicate out and use that as the extent_record since the only way we
6879 * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
6881 remove_cache_extent(extent_cache, &rec->cache);
6883 good = to_extent_record(rec->dups.next);
6884 list_del_init(&good->list);
6885 INIT_LIST_HEAD(&good->backrefs);
6886 INIT_LIST_HEAD(&good->dups);
6887 good->cache.start = good->start;
6888 good->cache.size = good->nr;
6889 good->content_checked = 0;
6890 good->owner_ref_checked = 0;
6891 good->num_duplicates = 0;
6892 good->refs = rec->refs;
6893 list_splice_init(&rec->backrefs, &good->backrefs);
6895 cache = lookup_cache_extent(extent_cache, good->start,
6899 tmp = container_of(cache, struct extent_record, cache);
6902 * If we find another overlapping extent and it's found_rec is
6903 * set then it's a duplicate and we need to try and delete
6906 if (tmp->found_rec || tmp->num_duplicates > 0) {
6907 if (list_empty(&good->list))
6908 list_add_tail(&good->list,
6909 &duplicate_extents);
6910 good->num_duplicates += tmp->num_duplicates + 1;
6911 list_splice_init(&tmp->dups, &good->dups);
6912 list_del_init(&tmp->list);
6913 list_add_tail(&tmp->list, &good->dups);
6914 remove_cache_extent(extent_cache, &tmp->cache);
6919 * Ok we have another non extent item backed extent rec, so lets
6920 * just add it to this extent and carry on like we did above.
6922 good->refs += tmp->refs;
6923 list_splice_init(&tmp->backrefs, &good->backrefs);
6924 remove_cache_extent(extent_cache, &tmp->cache);
6927 ret = insert_cache_extent(extent_cache, &good->cache);
6930 return good->num_duplicates ? 0 : 1;
6933 static int delete_duplicate_records(struct btrfs_root *root,
6934 struct extent_record *rec)
6936 struct btrfs_trans_handle *trans;
6937 LIST_HEAD(delete_list);
6938 struct btrfs_path path;
6939 struct extent_record *tmp, *good, *n;
6942 struct btrfs_key key;
6944 btrfs_init_path(&path);
6947 /* Find the record that covers all of the duplicates. */
6948 list_for_each_entry(tmp, &rec->dups, list) {
6949 if (good->start < tmp->start)
6951 if (good->nr > tmp->nr)
6954 if (tmp->start + tmp->nr < good->start + good->nr) {
6956 "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",
6957 tmp->start, tmp->nr, good->start, good->nr);
6964 list_add_tail(&rec->list, &delete_list);
6966 list_for_each_entry_safe(tmp, n, &rec->dups, list) {
6969 list_move_tail(&tmp->list, &delete_list);
6972 root = root->fs_info->extent_root;
6973 trans = btrfs_start_transaction(root, 1);
6974 if (IS_ERR(trans)) {
6975 ret = PTR_ERR(trans);
6979 list_for_each_entry(tmp, &delete_list, list) {
6980 if (tmp->found_rec == 0)
6982 key.objectid = tmp->start;
6983 key.type = BTRFS_EXTENT_ITEM_KEY;
6984 key.offset = tmp->nr;
6986 /* Shouldn't happen but just in case */
6987 if (tmp->metadata) {
6989 "well this shouldn't happen, extent record overlaps but is metadata? [%llu, %llu]\n",
6990 tmp->start, tmp->nr);
6994 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
7000 ret = btrfs_del_item(trans, root, &path);
7003 btrfs_release_path(&path);
7006 err = btrfs_commit_transaction(trans, root);
7010 while (!list_empty(&delete_list)) {
7011 tmp = to_extent_record(delete_list.next);
7012 list_del_init(&tmp->list);
7018 while (!list_empty(&rec->dups)) {
7019 tmp = to_extent_record(rec->dups.next);
7020 list_del_init(&tmp->list);
7024 btrfs_release_path(&path);
7026 if (!ret && !nr_del)
7027 rec->num_duplicates = 0;
7029 return ret ? ret : nr_del;
7032 static int find_possible_backrefs(struct btrfs_fs_info *info,
7033 struct btrfs_path *path,
7034 struct cache_tree *extent_cache,
7035 struct extent_record *rec)
7037 struct btrfs_root *root;
7038 struct extent_backref *back, *tmp;
7039 struct data_backref *dback;
7040 struct cache_extent *cache;
7041 struct btrfs_file_extent_item *fi;
7042 struct btrfs_key key;
7046 rbtree_postorder_for_each_entry_safe(back, tmp,
7047 &rec->backref_tree, node) {
7048 /* Don't care about full backrefs (poor unloved backrefs) */
7049 if (back->full_backref || !back->is_data)
7052 dback = to_data_backref(back);
7054 /* We found this one, we don't need to do a lookup */
7055 if (dback->found_ref)
7058 key.objectid = dback->root;
7059 key.type = BTRFS_ROOT_ITEM_KEY;
7060 key.offset = (u64)-1;
7062 root = btrfs_read_fs_root(info, &key);
7064 /* No root, definitely a bad ref, skip */
7065 if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
7067 /* Other err, exit */
7069 return PTR_ERR(root);
7071 key.objectid = dback->owner;
7072 key.type = BTRFS_EXTENT_DATA_KEY;
7073 key.offset = dback->offset;
7074 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
7076 btrfs_release_path(path);
7079 /* Didn't find it, we can carry on */
7084 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
7085 struct btrfs_file_extent_item);
7086 bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
7087 bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
7088 btrfs_release_path(path);
7089 cache = lookup_cache_extent(extent_cache, bytenr, 1);
7091 struct extent_record *tmp;
7093 tmp = container_of(cache, struct extent_record, cache);
7096 * If we found an extent record for the bytenr for this
7097 * particular backref then we can't add it to our
7098 * current extent record. We only want to add backrefs
7099 * that don't have a corresponding extent item in the
7100 * extent tree since they likely belong to this record
7101 * and we need to fix it if it doesn't match bytenrs.
7107 dback->found_ref += 1;
7108 dback->disk_bytenr = bytenr;
7109 dback->bytes = bytes;
7112 * Set this so the verify backref code knows not to trust the
7113 * values in this backref.
7122 * Record orphan data ref into corresponding root.
7124 * Return 0 if the extent item contains data ref and recorded.
7125 * Return 1 if the extent item contains no useful data ref
7126 * On that case, it may contains only shared_dataref or metadata backref
7127 * or the file extent exists(this should be handled by the extent bytenr
7129 * Return <0 if something goes wrong.
7131 static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
7132 struct extent_record *rec)
7134 struct btrfs_key key;
7135 struct btrfs_root *dest_root;
7136 struct extent_backref *back, *tmp;
7137 struct data_backref *dback;
7138 struct orphan_data_extent *orphan;
7139 struct btrfs_path path;
7140 int recorded_data_ref = 0;
7145 btrfs_init_path(&path);
7146 rbtree_postorder_for_each_entry_safe(back, tmp,
7147 &rec->backref_tree, node) {
7148 if (back->full_backref || !back->is_data ||
7149 !back->found_extent_tree)
7151 dback = to_data_backref(back);
7152 if (dback->found_ref)
7154 key.objectid = dback->root;
7155 key.type = BTRFS_ROOT_ITEM_KEY;
7156 key.offset = (u64)-1;
7158 dest_root = btrfs_read_fs_root(fs_info, &key);
7160 /* For non-exist root we just skip it */
7161 if (IS_ERR(dest_root) || !dest_root)
7164 key.objectid = dback->owner;
7165 key.type = BTRFS_EXTENT_DATA_KEY;
7166 key.offset = dback->offset;
7168 ret = btrfs_search_slot(NULL, dest_root, &key, &path, 0, 0);
7169 btrfs_release_path(&path);
7171 * For ret < 0, it's OK since the fs-tree may be corrupted,
7172 * we need to record it for inode/file extent rebuild.
7173 * For ret > 0, we record it only for file extent rebuild.
7174 * For ret == 0, the file extent exists but only bytenr
7175 * mismatch, let the original bytenr fix routine to handle,
7181 orphan = malloc(sizeof(*orphan));
7186 INIT_LIST_HEAD(&orphan->list);
7187 orphan->root = dback->root;
7188 orphan->objectid = dback->owner;
7189 orphan->offset = dback->offset;
7190 orphan->disk_bytenr = rec->cache.start;
7191 orphan->disk_len = rec->cache.size;
7192 list_add(&dest_root->orphan_data_extents, &orphan->list);
7193 recorded_data_ref = 1;
7196 btrfs_release_path(&path);
7198 return !recorded_data_ref;
7204 * when an incorrect extent item is found, this will delete
7205 * all of the existing entries for it and recreate them
7206 * based on what the tree scan found.
7208 static int fixup_extent_refs(struct btrfs_fs_info *info,
7209 struct cache_tree *extent_cache,
7210 struct extent_record *rec)
7212 struct btrfs_trans_handle *trans = NULL;
7214 struct btrfs_path path;
7215 struct cache_extent *cache;
7216 struct extent_backref *back, *tmp;
7220 if (rec->flag_block_full_backref)
7221 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7223 btrfs_init_path(&path);
7224 if (rec->refs != rec->extent_item_refs && !rec->metadata) {
7226 * Sometimes the backrefs themselves are so broken they don't
7227 * get attached to any meaningful rec, so first go back and
7228 * check any of our backrefs that we couldn't find and throw
7229 * them into the list if we find the backref so that
7230 * verify_backrefs can figure out what to do.
7232 ret = find_possible_backrefs(info, &path, extent_cache, rec);
7237 /* step one, make sure all of the backrefs agree */
7238 ret = verify_backrefs(info, &path, rec);
7242 trans = btrfs_start_transaction(info->extent_root, 1);
7243 if (IS_ERR(trans)) {
7244 ret = PTR_ERR(trans);
7248 /* step two, delete all the existing records */
7249 ret = delete_extent_records(trans, info->extent_root, &path,
7255 /* was this block corrupt? If so, don't add references to it */
7256 cache = lookup_cache_extent(info->corrupt_blocks,
7257 rec->start, rec->max_size);
7263 /* step three, recreate all the refs we did find */
7264 rbtree_postorder_for_each_entry_safe(back, tmp,
7265 &rec->backref_tree, node) {
7267 * if we didn't find any references, don't create a
7270 if (!back->found_ref)
7273 rec->bad_full_backref = 0;
7274 ret = record_extent(trans, info, &path, rec, back, allocated,
7283 int err = btrfs_commit_transaction(trans, info->extent_root);
7290 fprintf(stderr, "Repaired extent references for %llu\n",
7291 (unsigned long long)rec->start);
7293 btrfs_release_path(&path);
7297 static int fixup_extent_flags(struct btrfs_fs_info *fs_info,
7298 struct extent_record *rec)
7300 struct btrfs_trans_handle *trans;
7301 struct btrfs_root *root = fs_info->extent_root;
7302 struct btrfs_path path;
7303 struct btrfs_extent_item *ei;
7304 struct btrfs_key key;
7308 key.objectid = rec->start;
7309 if (rec->metadata) {
7310 key.type = BTRFS_METADATA_ITEM_KEY;
7311 key.offset = rec->info_level;
7313 key.type = BTRFS_EXTENT_ITEM_KEY;
7314 key.offset = rec->max_size;
7317 trans = btrfs_start_transaction(root, 0);
7319 return PTR_ERR(trans);
7321 btrfs_init_path(&path);
7322 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
7324 btrfs_release_path(&path);
7325 btrfs_commit_transaction(trans, root);
7328 fprintf(stderr, "Didn't find extent for %llu\n",
7329 (unsigned long long)rec->start);
7330 btrfs_release_path(&path);
7331 btrfs_commit_transaction(trans, root);
7335 ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
7336 struct btrfs_extent_item);
7337 flags = btrfs_extent_flags(path.nodes[0], ei);
7338 if (rec->flag_block_full_backref) {
7339 fprintf(stderr, "setting full backref on %llu\n",
7340 (unsigned long long)key.objectid);
7341 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7343 fprintf(stderr, "clearing full backref on %llu\n",
7344 (unsigned long long)key.objectid);
7345 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
7347 btrfs_set_extent_flags(path.nodes[0], ei, flags);
7348 btrfs_mark_buffer_dirty(path.nodes[0]);
7349 btrfs_release_path(&path);
7350 ret = btrfs_commit_transaction(trans, root);
7352 fprintf(stderr, "Repaired extent flags for %llu\n",
7353 (unsigned long long)rec->start);
7358 /* right now we only prune from the extent allocation tree */
7359 static int prune_one_block(struct btrfs_trans_handle *trans,
7360 struct btrfs_fs_info *info,
7361 struct btrfs_corrupt_block *corrupt)
7364 struct btrfs_path path;
7365 struct extent_buffer *eb;
7369 int level = corrupt->level + 1;
7371 btrfs_init_path(&path);
7373 /* we want to stop at the parent to our busted block */
7374 path.lowest_level = level;
7376 ret = btrfs_search_slot(trans, info->extent_root,
7377 &corrupt->key, &path, -1, 1);
7382 eb = path.nodes[level];
7389 * hopefully the search gave us the block we want to prune,
7390 * lets try that first
7392 slot = path.slots[level];
7393 found = btrfs_node_blockptr(eb, slot);
7394 if (found == corrupt->cache.start)
7397 nritems = btrfs_header_nritems(eb);
7399 /* the search failed, lets scan this node and hope we find it */
7400 for (slot = 0; slot < nritems; slot++) {
7401 found = btrfs_node_blockptr(eb, slot);
7402 if (found == corrupt->cache.start)
7406 * We couldn't find the bad block.
7407 * TODO: search all the nodes for pointers to this block
7409 if (eb == info->extent_root->node) {
7414 btrfs_release_path(&path);
7419 printk("deleting pointer to block %llu\n", corrupt->cache.start);
7420 ret = btrfs_del_ptr(info->extent_root, &path, level, slot);
7423 btrfs_release_path(&path);
7427 static int prune_corrupt_blocks(struct btrfs_fs_info *info)
7429 struct btrfs_trans_handle *trans = NULL;
7430 struct cache_extent *cache;
7431 struct btrfs_corrupt_block *corrupt;
7434 cache = search_cache_extent(info->corrupt_blocks, 0);
7438 trans = btrfs_start_transaction(info->extent_root, 1);
7440 return PTR_ERR(trans);
7442 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
7443 prune_one_block(trans, info, corrupt);
7444 remove_cache_extent(info->corrupt_blocks, cache);
7447 return btrfs_commit_transaction(trans, info->extent_root);
7451 static int check_extent_refs(struct btrfs_root *root,
7452 struct cache_tree *extent_cache)
7454 struct extent_record *rec;
7455 struct cache_extent *cache;
7462 * if we're doing a repair, we have to make sure
7463 * we don't allocate from the problem extents.
7464 * In the worst case, this will be all the
7467 cache = search_cache_extent(extent_cache, 0);
7469 rec = container_of(cache, struct extent_record, cache);
7470 set_extent_dirty(root->fs_info->excluded_extents,
7472 rec->start + rec->max_size - 1);
7473 cache = next_cache_extent(cache);
7476 /* pin down all the corrupted blocks too */
7477 cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
7479 set_extent_dirty(root->fs_info->excluded_extents,
7481 cache->start + cache->size - 1);
7482 cache = next_cache_extent(cache);
7484 prune_corrupt_blocks(root->fs_info);
7485 reset_cached_block_groups(root->fs_info);
7488 reset_cached_block_groups(root->fs_info);
7491 * We need to delete any duplicate entries we find first otherwise we
7492 * could mess up the extent tree when we have backrefs that actually
7493 * belong to a different extent item and not the weird duplicate one.
7495 while (repair && !list_empty(&duplicate_extents)) {
7496 rec = to_extent_record(duplicate_extents.next);
7497 list_del_init(&rec->list);
7499 /* Sometimes we can find a backref before we find an actual
7500 * extent, so we need to process it a little bit to see if there
7501 * truly are multiple EXTENT_ITEM_KEY's for the same range, or
7502 * if this is a backref screwup. If we need to delete stuff
7503 * process_duplicates() will return 0, otherwise it will return
7506 if (process_duplicates(extent_cache, rec))
7508 ret = delete_duplicate_records(root, rec);
7512 * delete_duplicate_records will return the number of entries
7513 * deleted, so if it's greater than 0 then we know we actually
7514 * did something and we need to remove.
7527 cache = search_cache_extent(extent_cache, 0);
7530 rec = container_of(cache, struct extent_record, cache);
7531 if (rec->num_duplicates) {
7533 "extent item %llu has multiple extent items\n",
7534 (unsigned long long)rec->start);
7538 if (rec->refs != rec->extent_item_refs) {
7539 fprintf(stderr, "ref mismatch on [%llu %llu] ",
7540 (unsigned long long)rec->start,
7541 (unsigned long long)rec->nr);
7542 fprintf(stderr, "extent item %llu, found %llu\n",
7543 (unsigned long long)rec->extent_item_refs,
7544 (unsigned long long)rec->refs);
7545 ret = record_orphan_data_extents(root->fs_info, rec);
7551 if (all_backpointers_checked(rec, 1)) {
7552 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
7553 (unsigned long long)rec->start,
7554 (unsigned long long)rec->nr);
7558 if (!rec->owner_ref_checked) {
7559 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
7560 (unsigned long long)rec->start,
7561 (unsigned long long)rec->nr);
7566 if (repair && fix) {
7567 ret = fixup_extent_refs(root->fs_info, extent_cache,
7574 if (rec->bad_full_backref) {
7575 fprintf(stderr, "bad full backref, on [%llu]\n",
7576 (unsigned long long)rec->start);
7578 ret = fixup_extent_flags(root->fs_info, rec);
7586 * Although it's not a extent ref's problem, we reuse this
7587 * routine for error reporting.
7588 * No repair function yet.
7590 if (rec->crossing_stripes) {
7592 "bad metadata [%llu, %llu) crossing stripe boundary\n",
7593 rec->start, rec->start + rec->max_size);
7597 if (rec->wrong_chunk_type) {
7599 "bad extent [%llu, %llu), type mismatch with chunk\n",
7600 rec->start, rec->start + rec->max_size);
7605 remove_cache_extent(extent_cache, cache);
7606 free_all_extent_backrefs(rec);
7607 if (!init_extent_tree && repair && (!cur_err || fix))
7608 clear_extent_dirty(root->fs_info->excluded_extents,
7610 rec->start + rec->max_size - 1);
7615 if (ret && ret != -EAGAIN) {
7616 fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
7619 struct btrfs_trans_handle *trans;
7621 root = root->fs_info->extent_root;
7622 trans = btrfs_start_transaction(root, 1);
7623 if (IS_ERR(trans)) {
7624 ret = PTR_ERR(trans);
7628 ret = btrfs_fix_block_accounting(trans, root);
7631 ret = btrfs_commit_transaction(trans, root);
7644 * Check the chunk with its block group/dev list ref:
7645 * Return 0 if all refs seems valid.
7646 * Return 1 if part of refs seems valid, need later check for rebuild ref
7647 * like missing block group and needs to search extent tree to rebuild them.
7648 * Return -1 if essential refs are missing and unable to rebuild.
7650 static int check_chunk_refs(struct chunk_record *chunk_rec,
7651 struct block_group_tree *block_group_cache,
7652 struct device_extent_tree *dev_extent_cache,
7655 struct cache_extent *block_group_item;
7656 struct block_group_record *block_group_rec;
7657 struct cache_extent *dev_extent_item;
7658 struct device_extent_record *dev_extent_rec;
7662 int metadump_v2 = 0;
7666 block_group_item = lookup_cache_extent(&block_group_cache->tree,
7669 if (block_group_item) {
7670 block_group_rec = container_of(block_group_item,
7671 struct block_group_record,
7673 if (chunk_rec->length != block_group_rec->offset ||
7674 chunk_rec->offset != block_group_rec->objectid ||
7676 chunk_rec->type_flags != block_group_rec->flags)) {
7679 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
7680 chunk_rec->objectid,
7685 chunk_rec->type_flags,
7686 block_group_rec->objectid,
7687 block_group_rec->type,
7688 block_group_rec->offset,
7689 block_group_rec->offset,
7690 block_group_rec->objectid,
7691 block_group_rec->flags);
7694 list_del_init(&block_group_rec->list);
7695 chunk_rec->bg_rec = block_group_rec;
7700 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
7701 chunk_rec->objectid,
7706 chunk_rec->type_flags);
7713 length = calc_stripe_length(chunk_rec->type_flags, chunk_rec->length,
7714 chunk_rec->num_stripes);
7715 for (i = 0; i < chunk_rec->num_stripes; ++i) {
7716 devid = chunk_rec->stripes[i].devid;
7717 offset = chunk_rec->stripes[i].offset;
7718 dev_extent_item = lookup_cache_extent2(&dev_extent_cache->tree,
7719 devid, offset, length);
7720 if (dev_extent_item) {
7721 dev_extent_rec = container_of(dev_extent_item,
7722 struct device_extent_record,
7724 if (dev_extent_rec->objectid != devid ||
7725 dev_extent_rec->offset != offset ||
7726 dev_extent_rec->chunk_offset != chunk_rec->offset ||
7727 dev_extent_rec->length != length) {
7730 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
7731 chunk_rec->objectid,
7734 chunk_rec->stripes[i].devid,
7735 chunk_rec->stripes[i].offset,
7736 dev_extent_rec->objectid,
7737 dev_extent_rec->offset,
7738 dev_extent_rec->length);
7741 list_move(&dev_extent_rec->chunk_list,
7742 &chunk_rec->dextents);
7747 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
7748 chunk_rec->objectid,
7751 chunk_rec->stripes[i].devid,
7752 chunk_rec->stripes[i].offset);
7759 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
7760 int check_chunks(struct cache_tree *chunk_cache,
7761 struct block_group_tree *block_group_cache,
7762 struct device_extent_tree *dev_extent_cache,
7763 struct list_head *good, struct list_head *bad,
7764 struct list_head *rebuild, int silent)
7766 struct cache_extent *chunk_item;
7767 struct chunk_record *chunk_rec;
7768 struct block_group_record *bg_rec;
7769 struct device_extent_record *dext_rec;
7773 chunk_item = first_cache_extent(chunk_cache);
7774 while (chunk_item) {
7775 chunk_rec = container_of(chunk_item, struct chunk_record,
7777 err = check_chunk_refs(chunk_rec, block_group_cache,
7778 dev_extent_cache, silent);
7781 if (err == 0 && good)
7782 list_add_tail(&chunk_rec->list, good);
7783 if (err > 0 && rebuild)
7784 list_add_tail(&chunk_rec->list, rebuild);
7786 list_add_tail(&chunk_rec->list, bad);
7787 chunk_item = next_cache_extent(chunk_item);
7790 list_for_each_entry(bg_rec, &block_group_cache->block_groups, list) {
7793 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
7801 list_for_each_entry(dext_rec, &dev_extent_cache->no_chunk_orphans,
7805 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
7816 static int check_device_used(struct device_record *dev_rec,
7817 struct device_extent_tree *dext_cache)
7819 struct cache_extent *cache;
7820 struct device_extent_record *dev_extent_rec;
7823 cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
7825 dev_extent_rec = container_of(cache,
7826 struct device_extent_record,
7828 if (dev_extent_rec->objectid != dev_rec->devid)
7831 list_del_init(&dev_extent_rec->device_list);
7832 total_byte += dev_extent_rec->length;
7833 cache = next_cache_extent(cache);
7836 if (total_byte != dev_rec->byte_used) {
7838 "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
7839 total_byte, dev_rec->byte_used, dev_rec->objectid,
7840 dev_rec->type, dev_rec->offset);
7848 * Unlike device size alignment check above, some super total_bytes check
7849 * failure can lead to mount failure for newer kernel.
7851 * So this function will return the error for a fatal super total_bytes problem.
7853 static bool is_super_size_valid(struct btrfs_fs_info *fs_info)
7855 struct btrfs_device *dev;
7856 struct list_head *dev_list = &fs_info->fs_devices->devices;
7857 u64 total_bytes = 0;
7858 u64 super_bytes = btrfs_super_total_bytes(fs_info->super_copy);
7860 list_for_each_entry(dev, dev_list, dev_list)
7861 total_bytes += dev->total_bytes;
7863 /* Important check, which can cause unmountable fs */
7864 if (super_bytes < total_bytes) {
7865 error("super total bytes %llu smaller than real device(s) size %llu",
7866 super_bytes, total_bytes);
7867 error("mounting this fs may fail for newer kernels");
7868 error("this can be fixed by 'btrfs rescue fix-device-size'");
7873 * Optional check, just to make everything aligned and match with each
7876 * For a btrfs-image restored fs, we don't need to check it anyway.
7878 if (btrfs_super_flags(fs_info->super_copy) &
7879 (BTRFS_SUPER_FLAG_METADUMP | BTRFS_SUPER_FLAG_METADUMP_V2))
7881 if (!IS_ALIGNED(super_bytes, fs_info->sectorsize) ||
7882 !IS_ALIGNED(total_bytes, fs_info->sectorsize) ||
7883 super_bytes != total_bytes) {
7884 warning("minor unaligned/mismatch device size detected");
7886 "recommended to use 'btrfs rescue fix-device-size' to fix it");
7891 /* check btrfs_dev_item -> btrfs_dev_extent */
7892 static int check_devices(struct rb_root *dev_cache,
7893 struct device_extent_tree *dev_extent_cache)
7895 struct rb_node *dev_node;
7896 struct device_record *dev_rec;
7897 struct device_extent_record *dext_rec;
7901 dev_node = rb_first(dev_cache);
7903 dev_rec = container_of(dev_node, struct device_record, node);
7904 err = check_device_used(dev_rec, dev_extent_cache);
7908 check_dev_size_alignment(dev_rec->devid, dev_rec->total_byte,
7909 global_info->sectorsize);
7910 dev_node = rb_next(dev_node);
7912 list_for_each_entry(dext_rec, &dev_extent_cache->no_device_orphans,
7915 "Device extent[%llu, %llu, %llu] didn't find its device.\n",
7916 dext_rec->objectid, dext_rec->offset, dext_rec->length);
7923 static int add_root_item_to_list(struct list_head *head,
7924 u64 objectid, u64 bytenr, u64 last_snapshot,
7925 u8 level, u8 drop_level,
7926 struct btrfs_key *drop_key)
7928 struct root_item_record *ri_rec;
7930 ri_rec = malloc(sizeof(*ri_rec));
7933 ri_rec->bytenr = bytenr;
7934 ri_rec->objectid = objectid;
7935 ri_rec->level = level;
7936 ri_rec->drop_level = drop_level;
7937 ri_rec->last_snapshot = last_snapshot;
7939 memcpy(&ri_rec->drop_key, drop_key, sizeof(*drop_key));
7940 list_add_tail(&ri_rec->list, head);
7945 static void free_root_item_list(struct list_head *list)
7947 struct root_item_record *ri_rec;
7949 while (!list_empty(list)) {
7950 ri_rec = list_first_entry(list, struct root_item_record,
7952 list_del_init(&ri_rec->list);
7957 static int deal_root_from_list(struct list_head *list,
7958 struct btrfs_root *root,
7959 struct block_info *bits,
7961 struct cache_tree *pending,
7962 struct cache_tree *seen,
7963 struct cache_tree *reada,
7964 struct cache_tree *nodes,
7965 struct cache_tree *extent_cache,
7966 struct cache_tree *chunk_cache,
7967 struct rb_root *dev_cache,
7968 struct block_group_tree *block_group_cache,
7969 struct device_extent_tree *dev_extent_cache)
7974 while (!list_empty(list)) {
7975 struct root_item_record *rec;
7976 struct extent_buffer *buf;
7978 rec = list_entry(list->next,
7979 struct root_item_record, list);
7981 buf = read_tree_block(root->fs_info, rec->bytenr, 0);
7982 if (!extent_buffer_uptodate(buf)) {
7983 free_extent_buffer(buf);
7987 ret = add_root_to_pending(buf, extent_cache, pending,
7988 seen, nodes, rec->objectid);
7992 * To rebuild extent tree, we need deal with snapshot
7993 * one by one, otherwise we deal with node firstly which
7994 * can maximize readahead.
7997 ret = run_next_block(root, bits, bits_nr, &last,
7998 pending, seen, reada, nodes,
7999 extent_cache, chunk_cache,
8000 dev_cache, block_group_cache,
8001 dev_extent_cache, rec);
8005 free_extent_buffer(buf);
8006 list_del(&rec->list);
8012 ret = run_next_block(root, bits, bits_nr, &last, pending, seen,
8013 reada, nodes, extent_cache, chunk_cache,
8014 dev_cache, block_group_cache,
8015 dev_extent_cache, NULL);
8025 static int check_chunks_and_extents(struct btrfs_fs_info *fs_info)
8027 struct rb_root dev_cache;
8028 struct cache_tree chunk_cache;
8029 struct block_group_tree block_group_cache;
8030 struct device_extent_tree dev_extent_cache;
8031 struct cache_tree extent_cache;
8032 struct cache_tree seen;
8033 struct cache_tree pending;
8034 struct cache_tree reada;
8035 struct cache_tree nodes;
8036 struct extent_io_tree excluded_extents;
8037 struct cache_tree corrupt_blocks;
8038 struct btrfs_path path;
8039 struct btrfs_key key;
8040 struct btrfs_key found_key;
8042 struct block_info *bits;
8044 struct extent_buffer *leaf;
8046 struct btrfs_root_item ri;
8047 struct list_head dropping_trees;
8048 struct list_head normal_trees;
8049 struct btrfs_root *root1;
8050 struct btrfs_root *root;
8054 root = fs_info->fs_root;
8055 dev_cache = RB_ROOT;
8056 cache_tree_init(&chunk_cache);
8057 block_group_tree_init(&block_group_cache);
8058 device_extent_tree_init(&dev_extent_cache);
8060 cache_tree_init(&extent_cache);
8061 cache_tree_init(&seen);
8062 cache_tree_init(&pending);
8063 cache_tree_init(&nodes);
8064 cache_tree_init(&reada);
8065 cache_tree_init(&corrupt_blocks);
8066 extent_io_tree_init(&excluded_extents);
8067 INIT_LIST_HEAD(&dropping_trees);
8068 INIT_LIST_HEAD(&normal_trees);
8071 fs_info->excluded_extents = &excluded_extents;
8072 fs_info->fsck_extent_cache = &extent_cache;
8073 fs_info->free_extent_hook = free_extent_hook;
8074 fs_info->corrupt_blocks = &corrupt_blocks;
8078 bits = malloc(bits_nr * sizeof(struct block_info));
8084 if (ctx.progress_enabled) {
8085 ctx.tp = TASK_EXTENTS;
8086 task_start(ctx.info);
8090 root1 = fs_info->tree_root;
8091 level = btrfs_header_level(root1->node);
8092 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8093 root1->node->start, 0, level, 0, NULL);
8096 root1 = fs_info->chunk_root;
8097 level = btrfs_header_level(root1->node);
8098 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8099 root1->node->start, 0, level, 0, NULL);
8102 btrfs_init_path(&path);
8105 key.type = BTRFS_ROOT_ITEM_KEY;
8106 ret = btrfs_search_slot(NULL, fs_info->tree_root, &key, &path, 0, 0);
8110 leaf = path.nodes[0];
8111 slot = path.slots[0];
8112 if (slot >= btrfs_header_nritems(path.nodes[0])) {
8113 ret = btrfs_next_leaf(root, &path);
8116 leaf = path.nodes[0];
8117 slot = path.slots[0];
8119 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
8120 if (found_key.type == BTRFS_ROOT_ITEM_KEY) {
8121 unsigned long offset;
8124 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
8125 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
8126 last_snapshot = btrfs_root_last_snapshot(&ri);
8127 if (btrfs_disk_key_objectid(&ri.drop_progress) == 0) {
8128 level = btrfs_root_level(&ri);
8129 ret = add_root_item_to_list(&normal_trees,
8131 btrfs_root_bytenr(&ri),
8132 last_snapshot, level,
8137 level = btrfs_root_level(&ri);
8138 objectid = found_key.objectid;
8139 btrfs_disk_key_to_cpu(&found_key,
8141 ret = add_root_item_to_list(&dropping_trees,
8143 btrfs_root_bytenr(&ri),
8144 last_snapshot, level,
8145 ri.drop_level, &found_key);
8152 btrfs_release_path(&path);
8155 * check_block can return -EAGAIN if it fixes something, please keep
8156 * this in mind when dealing with return values from these functions, if
8157 * we get -EAGAIN we want to fall through and restart the loop.
8159 ret = deal_root_from_list(&normal_trees, root, bits, bits_nr, &pending,
8160 &seen, &reada, &nodes, &extent_cache,
8161 &chunk_cache, &dev_cache, &block_group_cache,
8168 ret = deal_root_from_list(&dropping_trees, root, bits, bits_nr,
8169 &pending, &seen, &reada, &nodes,
8170 &extent_cache, &chunk_cache, &dev_cache,
8171 &block_group_cache, &dev_extent_cache);
8178 ret = check_chunks(&chunk_cache, &block_group_cache,
8179 &dev_extent_cache, NULL, NULL, NULL, 0);
8186 ret = check_extent_refs(root, &extent_cache);
8193 ret = check_devices(&dev_cache, &dev_extent_cache);
8198 task_stop(ctx.info);
8200 free_corrupt_blocks_tree(fs_info->corrupt_blocks);
8201 extent_io_tree_cleanup(&excluded_extents);
8202 fs_info->fsck_extent_cache = NULL;
8203 fs_info->free_extent_hook = NULL;
8204 fs_info->corrupt_blocks = NULL;
8205 fs_info->excluded_extents = NULL;
8208 free_chunk_cache_tree(&chunk_cache);
8209 free_device_cache_tree(&dev_cache);
8210 free_block_group_tree(&block_group_cache);
8211 free_device_extent_tree(&dev_extent_cache);
8212 free_extent_cache_tree(&seen);
8213 free_extent_cache_tree(&pending);
8214 free_extent_cache_tree(&reada);
8215 free_extent_cache_tree(&nodes);
8216 free_root_item_list(&normal_trees);
8217 free_root_item_list(&dropping_trees);
8220 free_corrupt_blocks_tree(fs_info->corrupt_blocks);
8221 free_extent_cache_tree(&seen);
8222 free_extent_cache_tree(&pending);
8223 free_extent_cache_tree(&reada);
8224 free_extent_cache_tree(&nodes);
8225 free_chunk_cache_tree(&chunk_cache);
8226 free_block_group_tree(&block_group_cache);
8227 free_device_cache_tree(&dev_cache);
8228 free_device_extent_tree(&dev_extent_cache);
8229 free_extent_record_cache(&extent_cache);
8230 free_root_item_list(&normal_trees);
8231 free_root_item_list(&dropping_trees);
8232 extent_io_tree_cleanup(&excluded_extents);
8236 static int do_check_chunks_and_extents(struct btrfs_fs_info *fs_info)
8240 if (!ctx.progress_enabled)
8241 fprintf(stderr, "checking extents\n");
8242 if (check_mode == CHECK_MODE_LOWMEM)
8243 ret = check_chunks_and_extents_lowmem(fs_info);
8245 ret = check_chunks_and_extents(fs_info);
8247 /* Also repair device size related problems */
8248 if (repair && !ret) {
8249 ret = btrfs_fix_device_and_super_size(fs_info);
8256 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
8257 struct btrfs_root *root, int overwrite)
8259 struct extent_buffer *c;
8260 struct extent_buffer *old = root->node;
8263 struct btrfs_disk_key disk_key = {0,0,0};
8269 extent_buffer_get(c);
8272 c = btrfs_alloc_free_block(trans, root,
8273 root->fs_info->nodesize,
8274 root->root_key.objectid,
8275 &disk_key, level, 0, 0);
8278 extent_buffer_get(c);
8282 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
8283 btrfs_set_header_level(c, level);
8284 btrfs_set_header_bytenr(c, c->start);
8285 btrfs_set_header_generation(c, trans->transid);
8286 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
8287 btrfs_set_header_owner(c, root->root_key.objectid);
8289 write_extent_buffer(c, root->fs_info->fsid,
8290 btrfs_header_fsid(), BTRFS_FSID_SIZE);
8292 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
8293 btrfs_header_chunk_tree_uuid(c),
8296 btrfs_mark_buffer_dirty(c);
8298 * this case can happen in the following case:
8300 * 1.overwrite previous root.
8302 * 2.reinit reloc data root, this is because we skip pin
8303 * down reloc data tree before which means we can allocate
8304 * same block bytenr here.
8306 if (old->start == c->start) {
8307 btrfs_set_root_generation(&root->root_item,
8309 root->root_item.level = btrfs_header_level(root->node);
8310 ret = btrfs_update_root(trans, root->fs_info->tree_root,
8311 &root->root_key, &root->root_item);
8313 free_extent_buffer(c);
8317 free_extent_buffer(old);
8319 add_root_to_dirty_list(root);
8323 static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
8324 struct extent_buffer *eb, int tree_root)
8326 struct extent_buffer *tmp;
8327 struct btrfs_root_item *ri;
8328 struct btrfs_key key;
8330 int level = btrfs_header_level(eb);
8336 * If we have pinned this block before, don't pin it again.
8337 * This can not only avoid forever loop with broken filesystem
8338 * but also give us some speedups.
8340 if (test_range_bit(&fs_info->pinned_extents, eb->start,
8341 eb->start + eb->len - 1, EXTENT_DIRTY, 0))
8344 btrfs_pin_extent(fs_info, eb->start, eb->len);
8346 nritems = btrfs_header_nritems(eb);
8347 for (i = 0; i < nritems; i++) {
8349 btrfs_item_key_to_cpu(eb, &key, i);
8350 if (key.type != BTRFS_ROOT_ITEM_KEY)
8352 /* Skip the extent root and reloc roots */
8353 if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
8354 key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
8355 key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
8357 ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
8358 bytenr = btrfs_disk_root_bytenr(eb, ri);
8361 * If at any point we start needing the real root we
8362 * will have to build a stump root for the root we are
8363 * in, but for now this doesn't actually use the root so
8364 * just pass in extent_root.
8366 tmp = read_tree_block(fs_info, bytenr, 0);
8367 if (!extent_buffer_uptodate(tmp)) {
8368 fprintf(stderr, "Error reading root block\n");
8371 ret = pin_down_tree_blocks(fs_info, tmp, 0);
8372 free_extent_buffer(tmp);
8376 bytenr = btrfs_node_blockptr(eb, i);
8378 /* If we aren't the tree root don't read the block */
8379 if (level == 1 && !tree_root) {
8380 btrfs_pin_extent(fs_info, bytenr,
8385 tmp = read_tree_block(fs_info, bytenr, 0);
8386 if (!extent_buffer_uptodate(tmp)) {
8387 fprintf(stderr, "Error reading tree block\n");
8390 ret = pin_down_tree_blocks(fs_info, tmp, tree_root);
8391 free_extent_buffer(tmp);
8400 static int pin_metadata_blocks(struct btrfs_fs_info *fs_info)
8404 ret = pin_down_tree_blocks(fs_info, fs_info->chunk_root->node, 0);
8408 return pin_down_tree_blocks(fs_info, fs_info->tree_root->node, 1);
8411 static int reset_block_groups(struct btrfs_fs_info *fs_info)
8413 struct btrfs_block_group_cache *cache;
8414 struct btrfs_path path;
8415 struct extent_buffer *leaf;
8416 struct btrfs_chunk *chunk;
8417 struct btrfs_key key;
8421 btrfs_init_path(&path);
8423 key.type = BTRFS_CHUNK_ITEM_KEY;
8425 ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, &path, 0, 0);
8427 btrfs_release_path(&path);
8432 * We do this in case the block groups were screwed up and had alloc
8433 * bits that aren't actually set on the chunks. This happens with
8434 * restored images every time and could happen in real life I guess.
8436 fs_info->avail_data_alloc_bits = 0;
8437 fs_info->avail_metadata_alloc_bits = 0;
8438 fs_info->avail_system_alloc_bits = 0;
8440 /* First we need to create the in-memory block groups */
8442 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8443 ret = btrfs_next_leaf(fs_info->chunk_root, &path);
8445 btrfs_release_path(&path);
8453 leaf = path.nodes[0];
8454 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8455 if (key.type != BTRFS_CHUNK_ITEM_KEY) {
8460 chunk = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_chunk);
8461 btrfs_add_block_group(fs_info, 0,
8462 btrfs_chunk_type(leaf, chunk), key.offset,
8463 btrfs_chunk_length(leaf, chunk));
8464 set_extent_dirty(&fs_info->free_space_cache, key.offset,
8465 key.offset + btrfs_chunk_length(leaf, chunk));
8470 cache = btrfs_lookup_first_block_group(fs_info, start);
8474 start = cache->key.objectid + cache->key.offset;
8477 btrfs_release_path(&path);
8481 static int reset_balance(struct btrfs_trans_handle *trans,
8482 struct btrfs_fs_info *fs_info)
8484 struct btrfs_root *root = fs_info->tree_root;
8485 struct btrfs_path path;
8486 struct extent_buffer *leaf;
8487 struct btrfs_key key;
8488 int del_slot, del_nr = 0;
8492 btrfs_init_path(&path);
8493 key.objectid = BTRFS_BALANCE_OBJECTID;
8494 key.type = BTRFS_BALANCE_ITEM_KEY;
8496 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
8501 goto reinit_data_reloc;
8506 ret = btrfs_del_item(trans, root, &path);
8509 btrfs_release_path(&path);
8511 key.objectid = BTRFS_TREE_RELOC_OBJECTID;
8512 key.type = BTRFS_ROOT_ITEM_KEY;
8514 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
8518 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8523 ret = btrfs_del_items(trans, root, &path,
8530 btrfs_release_path(&path);
8533 ret = btrfs_search_slot(trans, root, &key, &path,
8540 leaf = path.nodes[0];
8541 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8542 if (key.objectid > BTRFS_TREE_RELOC_OBJECTID)
8544 if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
8549 del_slot = path.slots[0];
8558 ret = btrfs_del_items(trans, root, &path, del_slot, del_nr);
8562 btrfs_release_path(&path);
8565 key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
8566 key.type = BTRFS_ROOT_ITEM_KEY;
8567 key.offset = (u64)-1;
8568 root = btrfs_read_fs_root(fs_info, &key);
8570 fprintf(stderr, "Error reading data reloc tree\n");
8571 ret = PTR_ERR(root);
8574 record_root_in_trans(trans, root);
8575 ret = btrfs_fsck_reinit_root(trans, root, 0);
8578 ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID);
8580 btrfs_release_path(&path);
8584 static int reinit_extent_tree(struct btrfs_trans_handle *trans,
8585 struct btrfs_fs_info *fs_info)
8591 * The only reason we don't do this is because right now we're just
8592 * walking the trees we find and pinning down their bytes, we don't look
8593 * at any of the leaves. In order to do mixed groups we'd have to check
8594 * the leaves of any fs roots and pin down the bytes for any file
8595 * extents we find. Not hard but why do it if we don't have to?
8597 if (btrfs_fs_incompat(fs_info, MIXED_GROUPS)) {
8598 fprintf(stderr, "We don't support re-initing the extent tree "
8599 "for mixed block groups yet, please notify a btrfs "
8600 "developer you want to do this so they can add this "
8601 "functionality.\n");
8606 * first we need to walk all of the trees except the extent tree and pin
8607 * down the bytes that are in use so we don't overwrite any existing
8610 ret = pin_metadata_blocks(fs_info);
8612 fprintf(stderr, "error pinning down used bytes\n");
8617 * Need to drop all the block groups since we're going to recreate all
8620 btrfs_free_block_groups(fs_info);
8621 ret = reset_block_groups(fs_info);
8623 fprintf(stderr, "error resetting the block groups\n");
8627 /* Ok we can allocate now, reinit the extent root */
8628 ret = btrfs_fsck_reinit_root(trans, fs_info->extent_root, 0);
8630 fprintf(stderr, "extent root initialization failed\n");
8632 * When the transaction code is updated we should end the
8633 * transaction, but for now progs only knows about commit so
8634 * just return an error.
8640 * Now we have all the in-memory block groups setup so we can make
8641 * allocations properly, and the metadata we care about is safe since we
8642 * pinned all of it above.
8645 struct btrfs_block_group_cache *cache;
8647 cache = btrfs_lookup_first_block_group(fs_info, start);
8650 start = cache->key.objectid + cache->key.offset;
8651 ret = btrfs_insert_item(trans, fs_info->extent_root,
8652 &cache->key, &cache->item,
8653 sizeof(cache->item));
8655 fprintf(stderr, "Error adding block group\n");
8658 btrfs_extent_post_op(trans, fs_info->extent_root);
8661 ret = reset_balance(trans, fs_info);
8663 fprintf(stderr, "error resetting the pending balance\n");
8668 static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb)
8670 struct btrfs_path path;
8671 struct btrfs_trans_handle *trans;
8672 struct btrfs_key key;
8675 printf("Recowing metadata block %llu\n", eb->start);
8676 key.objectid = btrfs_header_owner(eb);
8677 key.type = BTRFS_ROOT_ITEM_KEY;
8678 key.offset = (u64)-1;
8680 root = btrfs_read_fs_root(root->fs_info, &key);
8682 fprintf(stderr, "Couldn't find owner root %llu\n",
8684 return PTR_ERR(root);
8687 trans = btrfs_start_transaction(root, 1);
8689 return PTR_ERR(trans);
8691 btrfs_init_path(&path);
8692 path.lowest_level = btrfs_header_level(eb);
8693 if (path.lowest_level)
8694 btrfs_node_key_to_cpu(eb, &key, 0);
8696 btrfs_item_key_to_cpu(eb, &key, 0);
8698 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
8699 btrfs_commit_transaction(trans, root);
8700 btrfs_release_path(&path);
8704 static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad)
8706 struct btrfs_path path;
8707 struct btrfs_trans_handle *trans;
8708 struct btrfs_key key;
8711 printf("Deleting bad item [%llu,%u,%llu]\n", bad->key.objectid,
8712 bad->key.type, bad->key.offset);
8713 key.objectid = bad->root_id;
8714 key.type = BTRFS_ROOT_ITEM_KEY;
8715 key.offset = (u64)-1;
8717 root = btrfs_read_fs_root(root->fs_info, &key);
8719 fprintf(stderr, "Couldn't find owner root %llu\n",
8721 return PTR_ERR(root);
8724 trans = btrfs_start_transaction(root, 1);
8726 return PTR_ERR(trans);
8728 btrfs_init_path(&path);
8729 ret = btrfs_search_slot(trans, root, &bad->key, &path, -1, 1);
8735 ret = btrfs_del_item(trans, root, &path);
8737 btrfs_commit_transaction(trans, root);
8738 btrfs_release_path(&path);
8742 static int zero_log_tree(struct btrfs_root *root)
8744 struct btrfs_trans_handle *trans;
8747 trans = btrfs_start_transaction(root, 1);
8748 if (IS_ERR(trans)) {
8749 ret = PTR_ERR(trans);
8752 btrfs_set_super_log_root(root->fs_info->super_copy, 0);
8753 btrfs_set_super_log_root_level(root->fs_info->super_copy, 0);
8754 ret = btrfs_commit_transaction(trans, root);
8758 static int populate_csum(struct btrfs_trans_handle *trans,
8759 struct btrfs_root *csum_root, char *buf, u64 start,
8762 struct btrfs_fs_info *fs_info = csum_root->fs_info;
8767 while (offset < len) {
8768 sectorsize = fs_info->sectorsize;
8769 ret = read_extent_data(fs_info, buf, start + offset,
8773 ret = btrfs_csum_file_block(trans, csum_root, start + len,
8774 start + offset, buf, sectorsize);
8777 offset += sectorsize;
8782 static int fill_csum_tree_from_one_fs_root(struct btrfs_trans_handle *trans,
8783 struct btrfs_root *csum_root,
8784 struct btrfs_root *cur_root)
8786 struct btrfs_path path;
8787 struct btrfs_key key;
8788 struct extent_buffer *node;
8789 struct btrfs_file_extent_item *fi;
8796 buf = malloc(cur_root->fs_info->sectorsize);
8800 btrfs_init_path(&path);
8804 ret = btrfs_search_slot(NULL, cur_root, &key, &path, 0, 0);
8807 /* Iterate all regular file extents and fill its csum */
8809 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
8811 if (key.type != BTRFS_EXTENT_DATA_KEY)
8813 node = path.nodes[0];
8814 slot = path.slots[0];
8815 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
8816 if (btrfs_file_extent_type(node, fi) != BTRFS_FILE_EXTENT_REG)
8818 start = btrfs_file_extent_disk_bytenr(node, fi);
8819 len = btrfs_file_extent_disk_num_bytes(node, fi);
8821 ret = populate_csum(trans, csum_root, buf, start, len);
8828 * TODO: if next leaf is corrupted, jump to nearest next valid
8831 ret = btrfs_next_item(cur_root, &path);
8841 btrfs_release_path(&path);
8846 static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans,
8847 struct btrfs_root *csum_root)
8849 struct btrfs_fs_info *fs_info = csum_root->fs_info;
8850 struct btrfs_path path;
8851 struct btrfs_root *tree_root = fs_info->tree_root;
8852 struct btrfs_root *cur_root;
8853 struct extent_buffer *node;
8854 struct btrfs_key key;
8858 btrfs_init_path(&path);
8859 key.objectid = BTRFS_FS_TREE_OBJECTID;
8861 key.type = BTRFS_ROOT_ITEM_KEY;
8862 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
8871 node = path.nodes[0];
8872 slot = path.slots[0];
8873 btrfs_item_key_to_cpu(node, &key, slot);
8874 if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
8876 if (key.type != BTRFS_ROOT_ITEM_KEY)
8878 if (!is_fstree(key.objectid))
8880 key.offset = (u64)-1;
8882 cur_root = btrfs_read_fs_root(fs_info, &key);
8883 if (IS_ERR(cur_root) || !cur_root) {
8884 fprintf(stderr, "Fail to read fs/subvol tree: %lld\n",
8888 ret = fill_csum_tree_from_one_fs_root(trans, csum_root,
8893 ret = btrfs_next_item(tree_root, &path);
8903 btrfs_release_path(&path);
8907 static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans,
8908 struct btrfs_root *csum_root)
8910 struct btrfs_root *extent_root = csum_root->fs_info->extent_root;
8911 struct btrfs_path path;
8912 struct btrfs_extent_item *ei;
8913 struct extent_buffer *leaf;
8915 struct btrfs_key key;
8918 btrfs_init_path(&path);
8920 key.type = BTRFS_EXTENT_ITEM_KEY;
8922 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
8924 btrfs_release_path(&path);
8928 buf = malloc(csum_root->fs_info->sectorsize);
8930 btrfs_release_path(&path);
8935 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8936 ret = btrfs_next_leaf(extent_root, &path);
8944 leaf = path.nodes[0];
8946 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8947 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
8952 ei = btrfs_item_ptr(leaf, path.slots[0],
8953 struct btrfs_extent_item);
8954 if (!(btrfs_extent_flags(leaf, ei) &
8955 BTRFS_EXTENT_FLAG_DATA)) {
8960 ret = populate_csum(trans, csum_root, buf, key.objectid,
8967 btrfs_release_path(&path);
8973 * Recalculate the csum and put it into the csum tree.
8975 * Extent tree init will wipe out all the extent info, so in that case, we
8976 * can't depend on extent tree, but use fs tree. If search_fs_tree is set, we
8977 * will use fs/subvol trees to init the csum tree.
8979 static int fill_csum_tree(struct btrfs_trans_handle *trans,
8980 struct btrfs_root *csum_root,
8984 return fill_csum_tree_from_fs(trans, csum_root);
8986 return fill_csum_tree_from_extent(trans, csum_root);
8989 static void free_roots_info_cache(void)
8991 if (!roots_info_cache)
8994 while (!cache_tree_empty(roots_info_cache)) {
8995 struct cache_extent *entry;
8996 struct root_item_info *rii;
8998 entry = first_cache_extent(roots_info_cache);
9001 remove_cache_extent(roots_info_cache, entry);
9002 rii = container_of(entry, struct root_item_info, cache_extent);
9006 free(roots_info_cache);
9007 roots_info_cache = NULL;
9010 static int build_roots_info_cache(struct btrfs_fs_info *info)
9013 struct btrfs_key key;
9014 struct extent_buffer *leaf;
9015 struct btrfs_path path;
9017 if (!roots_info_cache) {
9018 roots_info_cache = malloc(sizeof(*roots_info_cache));
9019 if (!roots_info_cache)
9021 cache_tree_init(roots_info_cache);
9024 btrfs_init_path(&path);
9026 key.type = BTRFS_EXTENT_ITEM_KEY;
9028 ret = btrfs_search_slot(NULL, info->extent_root, &key, &path, 0, 0);
9031 leaf = path.nodes[0];
9034 struct btrfs_key found_key;
9035 struct btrfs_extent_item *ei;
9036 struct btrfs_extent_inline_ref *iref;
9037 unsigned long item_end;
9038 int slot = path.slots[0];
9043 struct cache_extent *entry;
9044 struct root_item_info *rii;
9046 if (slot >= btrfs_header_nritems(leaf)) {
9047 ret = btrfs_next_leaf(info->extent_root, &path);
9054 leaf = path.nodes[0];
9055 slot = path.slots[0];
9058 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
9060 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
9061 found_key.type != BTRFS_METADATA_ITEM_KEY)
9064 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
9065 flags = btrfs_extent_flags(leaf, ei);
9066 item_end = (unsigned long)ei + btrfs_item_size_nr(leaf, slot);
9068 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
9069 !(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))
9072 if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
9073 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
9074 level = found_key.offset;
9076 struct btrfs_tree_block_info *binfo;
9078 binfo = (struct btrfs_tree_block_info *)(ei + 1);
9079 iref = (struct btrfs_extent_inline_ref *)(binfo + 1);
9080 level = btrfs_tree_block_level(leaf, binfo);
9084 * It's a valid extent/metadata item that has no inline ref,
9085 * but SHARED_BLOCK_REF or other shared references.
9086 * So we need to do extra check to avoid reading beyond leaf
9089 if ((unsigned long)iref >= item_end)
9093 * For a root extent, it must be of the following type and the
9094 * first (and only one) iref in the item.
9096 type = btrfs_extent_inline_ref_type(leaf, iref);
9097 if (type != BTRFS_TREE_BLOCK_REF_KEY)
9100 root_id = btrfs_extent_inline_ref_offset(leaf, iref);
9101 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9103 rii = malloc(sizeof(struct root_item_info));
9108 rii->cache_extent.start = root_id;
9109 rii->cache_extent.size = 1;
9110 rii->level = (u8)-1;
9111 entry = &rii->cache_extent;
9112 ret = insert_cache_extent(roots_info_cache, entry);
9115 rii = container_of(entry, struct root_item_info,
9119 ASSERT(rii->cache_extent.start == root_id);
9120 ASSERT(rii->cache_extent.size == 1);
9122 if (level > rii->level || rii->level == (u8)-1) {
9124 rii->bytenr = found_key.objectid;
9125 rii->gen = btrfs_extent_generation(leaf, ei);
9126 rii->node_count = 1;
9127 } else if (level == rii->level) {
9135 btrfs_release_path(&path);
9140 static int maybe_repair_root_item(struct btrfs_path *path,
9141 const struct btrfs_key *root_key,
9142 const int read_only_mode)
9144 const u64 root_id = root_key->objectid;
9145 struct cache_extent *entry;
9146 struct root_item_info *rii;
9147 struct btrfs_root_item ri;
9148 unsigned long offset;
9150 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9153 "Error: could not find extent items for root %llu\n",
9154 root_key->objectid);
9158 rii = container_of(entry, struct root_item_info, cache_extent);
9159 ASSERT(rii->cache_extent.start == root_id);
9160 ASSERT(rii->cache_extent.size == 1);
9162 if (rii->node_count != 1) {
9164 "Error: could not find btree root extent for root %llu\n",
9169 offset = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
9170 read_extent_buffer(path->nodes[0], &ri, offset, sizeof(ri));
9172 if (btrfs_root_bytenr(&ri) != rii->bytenr ||
9173 btrfs_root_level(&ri) != rii->level ||
9174 btrfs_root_generation(&ri) != rii->gen) {
9177 * If we're in repair mode but our caller told us to not update
9178 * the root item, i.e. just check if it needs to be updated, don't
9179 * print this message, since the caller will call us again shortly
9180 * for the same root item without read only mode (the caller will
9181 * open a transaction first).
9183 if (!(read_only_mode && repair))
9185 "%sroot item for root %llu,"
9186 " current bytenr %llu, current gen %llu, current level %u,"
9187 " new bytenr %llu, new gen %llu, new level %u\n",
9188 (read_only_mode ? "" : "fixing "),
9190 btrfs_root_bytenr(&ri), btrfs_root_generation(&ri),
9191 btrfs_root_level(&ri),
9192 rii->bytenr, rii->gen, rii->level);
9194 if (btrfs_root_generation(&ri) > rii->gen) {
9196 "root %llu has a root item with a more recent gen (%llu) compared to the found root node (%llu)\n",
9197 root_id, btrfs_root_generation(&ri), rii->gen);
9201 if (!read_only_mode) {
9202 btrfs_set_root_bytenr(&ri, rii->bytenr);
9203 btrfs_set_root_level(&ri, rii->level);
9204 btrfs_set_root_generation(&ri, rii->gen);
9205 write_extent_buffer(path->nodes[0], &ri,
9206 offset, sizeof(ri));
9216 * A regression introduced in the 3.17 kernel (more specifically in 3.17-rc2),
9217 * caused read-only snapshots to be corrupted if they were created at a moment
9218 * when the source subvolume/snapshot had orphan items. The issue was that the
9219 * on-disk root items became incorrect, referring to the pre orphan cleanup root
9220 * node instead of the post orphan cleanup root node.
9221 * So this function, and its callees, just detects and fixes those cases. Even
9222 * though the regression was for read-only snapshots, this function applies to
9223 * any snapshot/subvolume root.
9224 * This must be run before any other repair code - not doing it so, makes other
9225 * repair code delete or modify backrefs in the extent tree for example, which
9226 * will result in an inconsistent fs after repairing the root items.
9228 static int repair_root_items(struct btrfs_fs_info *info)
9230 struct btrfs_path path;
9231 struct btrfs_key key;
9232 struct extent_buffer *leaf;
9233 struct btrfs_trans_handle *trans = NULL;
9238 btrfs_init_path(&path);
9240 ret = build_roots_info_cache(info);
9244 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
9245 key.type = BTRFS_ROOT_ITEM_KEY;
9250 * Avoid opening and committing transactions if a leaf doesn't have
9251 * any root items that need to be fixed, so that we avoid rotating
9252 * backup roots unnecessarily.
9255 trans = btrfs_start_transaction(info->tree_root, 1);
9256 if (IS_ERR(trans)) {
9257 ret = PTR_ERR(trans);
9262 ret = btrfs_search_slot(trans, info->tree_root, &key, &path,
9266 leaf = path.nodes[0];
9269 struct btrfs_key found_key;
9271 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
9272 int no_more_keys = find_next_key(&path, &key);
9274 btrfs_release_path(&path);
9276 ret = btrfs_commit_transaction(trans,
9288 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
9290 if (found_key.type != BTRFS_ROOT_ITEM_KEY)
9292 if (found_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
9295 ret = maybe_repair_root_item(&path, &found_key, trans ? 0 : 1);
9299 if (!trans && repair) {
9302 btrfs_release_path(&path);
9312 free_roots_info_cache();
9313 btrfs_release_path(&path);
9315 btrfs_commit_transaction(trans, info->tree_root);
9322 static int clear_free_space_cache(struct btrfs_fs_info *fs_info)
9324 struct btrfs_trans_handle *trans;
9325 struct btrfs_block_group_cache *bg_cache;
9329 /* Clear all free space cache inodes and its extent data */
9331 bg_cache = btrfs_lookup_first_block_group(fs_info, current);
9334 ret = btrfs_clear_free_space_cache(fs_info, bg_cache);
9337 current = bg_cache->key.objectid + bg_cache->key.offset;
9340 /* Don't forget to set cache_generation to -1 */
9341 trans = btrfs_start_transaction(fs_info->tree_root, 0);
9342 if (IS_ERR(trans)) {
9343 error("failed to update super block cache generation");
9344 return PTR_ERR(trans);
9346 btrfs_set_super_cache_generation(fs_info->super_copy, (u64)-1);
9347 btrfs_commit_transaction(trans, fs_info->tree_root);
9352 static int do_clear_free_space_cache(struct btrfs_fs_info *fs_info,
9357 if (clear_version == 1) {
9358 if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
9360 "free space cache v2 detected, use --clear-space-cache v2");
9364 printf("Clearing free space cache\n");
9365 ret = clear_free_space_cache(fs_info);
9367 error("failed to clear free space cache");
9370 printf("Free space cache cleared\n");
9372 } else if (clear_version == 2) {
9373 if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
9374 printf("no free space cache v2 to clear\n");
9378 printf("Clear free space cache v2\n");
9379 ret = btrfs_clear_free_space_tree(fs_info);
9381 error("failed to clear free space cache v2: %d", ret);
9384 printf("free space cache v2 cleared\n");
9391 const char * const cmd_check_usage[] = {
9392 "btrfs check [options] <device>",
9393 "Check structural integrity of a filesystem (unmounted).",
9394 "Check structural integrity of an unmounted filesystem. Verify internal",
9395 "trees' consistency and item connectivity. In the repair mode try to",
9396 "fix the problems found. ",
9397 "WARNING: the repair mode is considered dangerous",
9399 "-s|--super <superblock> use this superblock copy",
9400 "-b|--backup use the first valid backup root copy",
9401 "--force skip mount checks, repair is not possible",
9402 "--repair try to repair the filesystem",
9403 "--readonly run in read-only mode (default)",
9404 "--init-csum-tree create a new CRC tree",
9405 "--init-extent-tree create a new extent tree",
9406 "--mode <MODE> allows choice of memory/IO trade-offs",
9407 " where MODE is one of:",
9408 " original - read inodes and extents to memory (requires",
9409 " more memory, does less IO)",
9410 " lowmem - try to use less memory but read blocks again",
9412 "--check-data-csum verify checksums of data blocks",
9413 "-Q|--qgroup-report print a report on qgroup consistency",
9414 "-E|--subvol-extents <subvolid>",
9415 " print subvolume extents and sharing state",
9416 "-r|--tree-root <bytenr> use the given bytenr for the tree root",
9417 "--chunk-root <bytenr> use the given bytenr for the chunk tree root",
9418 "-p|--progress indicate progress",
9419 "--clear-space-cache v1|v2 clear space cache for v1 or v2",
9423 int cmd_check(int argc, char **argv)
9425 struct cache_tree root_cache;
9426 struct btrfs_root *root;
9427 struct btrfs_fs_info *info;
9430 u64 tree_root_bytenr = 0;
9431 u64 chunk_root_bytenr = 0;
9432 char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
9436 int init_csum_tree = 0;
9438 int clear_space_cache = 0;
9439 int qgroup_report = 0;
9440 int qgroups_repaired = 0;
9441 unsigned ctree_flags = OPEN_CTREE_EXCLUSIVE;
9446 enum { GETOPT_VAL_REPAIR = 257, GETOPT_VAL_INIT_CSUM,
9447 GETOPT_VAL_INIT_EXTENT, GETOPT_VAL_CHECK_CSUM,
9448 GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE,
9449 GETOPT_VAL_MODE, GETOPT_VAL_CLEAR_SPACE_CACHE,
9451 static const struct option long_options[] = {
9452 { "super", required_argument, NULL, 's' },
9453 { "repair", no_argument, NULL, GETOPT_VAL_REPAIR },
9454 { "readonly", no_argument, NULL, GETOPT_VAL_READONLY },
9455 { "init-csum-tree", no_argument, NULL,
9456 GETOPT_VAL_INIT_CSUM },
9457 { "init-extent-tree", no_argument, NULL,
9458 GETOPT_VAL_INIT_EXTENT },
9459 { "check-data-csum", no_argument, NULL,
9460 GETOPT_VAL_CHECK_CSUM },
9461 { "backup", no_argument, NULL, 'b' },
9462 { "subvol-extents", required_argument, NULL, 'E' },
9463 { "qgroup-report", no_argument, NULL, 'Q' },
9464 { "tree-root", required_argument, NULL, 'r' },
9465 { "chunk-root", required_argument, NULL,
9466 GETOPT_VAL_CHUNK_TREE },
9467 { "progress", no_argument, NULL, 'p' },
9468 { "mode", required_argument, NULL,
9470 { "clear-space-cache", required_argument, NULL,
9471 GETOPT_VAL_CLEAR_SPACE_CACHE},
9472 { "force", no_argument, NULL, GETOPT_VAL_FORCE },
9476 c = getopt_long(argc, argv, "as:br:pEQ", long_options, NULL);
9480 case 'a': /* ignored */ break;
9482 ctree_flags |= OPEN_CTREE_BACKUP_ROOT;
9485 num = arg_strtou64(optarg);
9486 if (num >= BTRFS_SUPER_MIRROR_MAX) {
9488 "super mirror should be less than %d",
9489 BTRFS_SUPER_MIRROR_MAX);
9492 bytenr = btrfs_sb_offset(((int)num));
9493 printf("using SB copy %llu, bytenr %llu\n", num,
9494 (unsigned long long)bytenr);
9500 subvolid = arg_strtou64(optarg);
9503 tree_root_bytenr = arg_strtou64(optarg);
9505 case GETOPT_VAL_CHUNK_TREE:
9506 chunk_root_bytenr = arg_strtou64(optarg);
9509 ctx.progress_enabled = true;
9513 usage(cmd_check_usage);
9514 case GETOPT_VAL_REPAIR:
9515 printf("enabling repair mode\n");
9517 ctree_flags |= OPEN_CTREE_WRITES;
9519 case GETOPT_VAL_READONLY:
9522 case GETOPT_VAL_INIT_CSUM:
9523 printf("Creating a new CRC tree\n");
9526 ctree_flags |= OPEN_CTREE_WRITES;
9528 case GETOPT_VAL_INIT_EXTENT:
9529 init_extent_tree = 1;
9530 ctree_flags |= (OPEN_CTREE_WRITES |
9531 OPEN_CTREE_NO_BLOCK_GROUPS);
9534 case GETOPT_VAL_CHECK_CSUM:
9535 check_data_csum = 1;
9537 case GETOPT_VAL_MODE:
9538 check_mode = parse_check_mode(optarg);
9539 if (check_mode == CHECK_MODE_UNKNOWN) {
9540 error("unknown mode: %s", optarg);
9544 case GETOPT_VAL_CLEAR_SPACE_CACHE:
9545 if (strcmp(optarg, "v1") == 0) {
9546 clear_space_cache = 1;
9547 } else if (strcmp(optarg, "v2") == 0) {
9548 clear_space_cache = 2;
9549 ctree_flags |= OPEN_CTREE_INVALIDATE_FST;
9552 "invalid argument to --clear-space-cache, must be v1 or v2");
9555 ctree_flags |= OPEN_CTREE_WRITES;
9557 case GETOPT_VAL_FORCE:
9563 if (check_argc_exact(argc - optind, 1))
9564 usage(cmd_check_usage);
9566 if (ctx.progress_enabled) {
9567 ctx.tp = TASK_NOTHING;
9568 ctx.info = task_init(print_status_check, print_status_return, &ctx);
9571 /* This check is the only reason for --readonly to exist */
9572 if (readonly && repair) {
9573 error("repair options are not compatible with --readonly");
9578 * experimental and dangerous
9580 if (repair && check_mode == CHECK_MODE_LOWMEM)
9581 warning("low-memory mode repair support is only partial");
9584 cache_tree_init(&root_cache);
9586 ret = check_mounted(argv[optind]);
9589 error("could not check mount status: %s",
9595 "%s is currently mounted, use --force if you really intend to check the filesystem",
9603 error("repair and --force is not yet supported");
9610 "cannot check mount status of %s, the filesystem could be mounted, continuing because of --force",
9614 "filesystem mounted, continuing because of --force");
9616 /* A block device is mounted in exclusive mode by kernel */
9617 ctree_flags &= ~OPEN_CTREE_EXCLUSIVE;
9620 /* only allow partial opening under repair mode */
9622 ctree_flags |= OPEN_CTREE_PARTIAL;
9624 info = open_ctree_fs_info(argv[optind], bytenr, tree_root_bytenr,
9625 chunk_root_bytenr, ctree_flags);
9627 error("cannot open file system");
9634 root = info->fs_root;
9635 uuid_unparse(info->super_copy->fsid, uuidbuf);
9637 printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
9640 * Check the bare minimum before starting anything else that could rely
9641 * on it, namely the tree roots, any local consistency checks
9643 if (!extent_buffer_uptodate(info->tree_root->node) ||
9644 !extent_buffer_uptodate(info->dev_root->node) ||
9645 !extent_buffer_uptodate(info->chunk_root->node)) {
9646 error("critical roots corrupted, unable to check the filesystem");
9652 if (clear_space_cache) {
9653 ret = do_clear_free_space_cache(info, clear_space_cache);
9659 * repair mode will force us to commit transaction which
9660 * will make us fail to load log tree when mounting.
9662 if (repair && btrfs_super_log_root(info->super_copy)) {
9663 ret = ask_user("repair mode will force to clear out log tree, are you sure?");
9669 ret = zero_log_tree(root);
9672 error("failed to zero log tree: %d", ret);
9677 if (qgroup_report) {
9678 printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
9680 ret = qgroup_verify_all(info);
9687 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
9688 subvolid, argv[optind], uuidbuf);
9689 ret = print_extent_state(info, subvolid);
9694 if (init_extent_tree || init_csum_tree) {
9695 struct btrfs_trans_handle *trans;
9697 trans = btrfs_start_transaction(info->extent_root, 0);
9698 if (IS_ERR(trans)) {
9699 error("error starting transaction");
9700 ret = PTR_ERR(trans);
9705 if (init_extent_tree) {
9706 printf("Creating a new extent tree\n");
9707 ret = reinit_extent_tree(trans, info);
9713 if (init_csum_tree) {
9714 printf("Reinitialize checksum tree\n");
9715 ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0);
9717 error("checksum tree initialization failed: %d",
9724 ret = fill_csum_tree(trans, info->csum_root,
9728 error("checksum tree refilling failed: %d", ret);
9733 * Ok now we commit and run the normal fsck, which will add
9734 * extent entries for all of the items it finds.
9736 ret = btrfs_commit_transaction(trans, info->extent_root);
9741 if (!extent_buffer_uptodate(info->extent_root->node)) {
9742 error("critical: extent_root, unable to check the filesystem");
9747 if (!extent_buffer_uptodate(info->csum_root->node)) {
9748 error("critical: csum_root, unable to check the filesystem");
9754 if (!init_extent_tree) {
9755 ret = repair_root_items(info);
9758 error("failed to repair root items: %s", strerror(-ret));
9762 fprintf(stderr, "Fixed %d roots.\n", ret);
9764 } else if (ret > 0) {
9766 "Found %d roots with an outdated root item.\n",
9769 "Please run a filesystem check with the option --repair to fix them.\n");
9776 ret = do_check_chunks_and_extents(info);
9780 "errors found in extent allocation tree or chunk allocation");
9782 /* Only re-check super size after we checked and repaired the fs */
9783 err |= !is_super_size_valid(info);
9785 if (!ctx.progress_enabled) {
9786 if (btrfs_fs_compat_ro(info, FREE_SPACE_TREE))
9787 fprintf(stderr, "checking free space tree\n");
9789 fprintf(stderr, "checking free space cache\n");
9791 ret = check_space_cache(root);
9794 if (btrfs_fs_compat_ro(info, FREE_SPACE_TREE))
9795 error("errors found in free space tree");
9797 error("errors found in free space cache");
9802 * We used to have to have these hole extents in between our real
9803 * extents so if we don't have this flag set we need to make sure there
9804 * are no gaps in the file extents for inodes, otherwise we can just
9805 * ignore it when this happens.
9807 no_holes = btrfs_fs_incompat(root->fs_info, NO_HOLES);
9808 ret = do_check_fs_roots(info, &root_cache);
9811 error("errors found in fs roots");
9815 fprintf(stderr, "checking csums\n");
9816 ret = check_csums(root);
9819 error("errors found in csum tree");
9823 fprintf(stderr, "checking root refs\n");
9824 /* For low memory mode, check_fs_roots_v2 handles root refs */
9825 if (check_mode != CHECK_MODE_LOWMEM) {
9826 ret = check_root_refs(root, &root_cache);
9829 error("errors found in root refs");
9834 while (repair && !list_empty(&root->fs_info->recow_ebs)) {
9835 struct extent_buffer *eb;
9837 eb = list_first_entry(&root->fs_info->recow_ebs,
9838 struct extent_buffer, recow);
9839 list_del_init(&eb->recow);
9840 ret = recow_extent_buffer(root, eb);
9843 error("fails to fix transid errors");
9848 while (!list_empty(&delete_items)) {
9849 struct bad_item *bad;
9851 bad = list_first_entry(&delete_items, struct bad_item, list);
9852 list_del_init(&bad->list);
9854 ret = delete_bad_item(root, bad);
9860 if (info->quota_enabled) {
9861 fprintf(stderr, "checking quota groups\n");
9862 ret = qgroup_verify_all(info);
9865 error("failed to check quota groups");
9869 ret = repair_qgroups(info, &qgroups_repaired);
9872 error("failed to repair quota groups");
9878 if (!list_empty(&root->fs_info->recow_ebs)) {
9879 error("transid errors in file system");
9884 printf("found %llu bytes used, ",
9885 (unsigned long long)bytes_used);
9887 printf("error(s) found\n");
9889 printf("no error found\n");
9890 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
9891 printf("total tree bytes: %llu\n",
9892 (unsigned long long)total_btree_bytes);
9893 printf("total fs tree bytes: %llu\n",
9894 (unsigned long long)total_fs_tree_bytes);
9895 printf("total extent tree bytes: %llu\n",
9896 (unsigned long long)total_extent_tree_bytes);
9897 printf("btree space waste bytes: %llu\n",
9898 (unsigned long long)btree_space_waste);
9899 printf("file data blocks allocated: %llu\n referenced %llu\n",
9900 (unsigned long long)data_bytes_allocated,
9901 (unsigned long long)data_bytes_referenced);
9903 free_qgroup_counts();
9904 free_root_recs_tree(&root_cache);
9908 if (ctx.progress_enabled)
9909 task_deinit(ctx.info);