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 ret = check_prealloc_extent_written(root->fs_info,
1521 rec->errors |= I_ERR_ODD_CSUM_ITEM;
1528 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
1529 struct walk_control *wc)
1531 struct btrfs_key key;
1535 struct cache_tree *inode_cache;
1536 struct shared_node *active_node;
1538 if (wc->root_level == wc->active_node &&
1539 btrfs_root_refs(&root->root_item) == 0)
1542 active_node = wc->nodes[wc->active_node];
1543 inode_cache = &active_node->inode_cache;
1544 nritems = btrfs_header_nritems(eb);
1545 for (i = 0; i < nritems; i++) {
1546 btrfs_item_key_to_cpu(eb, &key, i);
1548 if (key.objectid == BTRFS_FREE_SPACE_OBJECTID)
1550 if (key.type == BTRFS_ORPHAN_ITEM_KEY)
1553 if (active_node->current == NULL ||
1554 active_node->current->ino < key.objectid) {
1555 if (active_node->current) {
1556 active_node->current->checked = 1;
1557 maybe_free_inode_rec(inode_cache,
1558 active_node->current);
1560 active_node->current = get_inode_rec(inode_cache,
1562 BUG_ON(IS_ERR(active_node->current));
1565 case BTRFS_DIR_ITEM_KEY:
1566 case BTRFS_DIR_INDEX_KEY:
1567 ret = process_dir_item(eb, i, &key, active_node);
1569 case BTRFS_INODE_REF_KEY:
1570 ret = process_inode_ref(eb, i, &key, active_node);
1572 case BTRFS_INODE_EXTREF_KEY:
1573 ret = process_inode_extref(eb, i, &key, active_node);
1575 case BTRFS_INODE_ITEM_KEY:
1576 ret = process_inode_item(eb, i, &key, active_node);
1578 case BTRFS_EXTENT_DATA_KEY:
1579 ret = process_file_extent(root, eb, i, &key,
1589 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1590 struct walk_control *wc, int *level,
1591 struct node_refs *nrefs)
1593 enum btrfs_tree_block_status status;
1596 struct btrfs_fs_info *fs_info = root->fs_info;
1597 struct extent_buffer *next;
1598 struct extent_buffer *cur;
1602 WARN_ON(*level < 0);
1603 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1605 if (path->nodes[*level]->start == nrefs->bytenr[*level]) {
1606 refs = nrefs->refs[*level];
1609 ret = btrfs_lookup_extent_info(NULL, root,
1610 path->nodes[*level]->start,
1611 *level, 1, &refs, NULL);
1616 nrefs->bytenr[*level] = path->nodes[*level]->start;
1617 nrefs->refs[*level] = refs;
1621 ret = enter_shared_node(root, path->nodes[*level]->start,
1629 while (*level >= 0) {
1630 WARN_ON(*level < 0);
1631 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1632 cur = path->nodes[*level];
1634 if (btrfs_header_level(cur) != *level)
1637 if (path->slots[*level] >= btrfs_header_nritems(cur))
1640 ret = process_one_leaf(root, cur, wc);
1645 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1646 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1648 if (bytenr == nrefs->bytenr[*level - 1]) {
1649 refs = nrefs->refs[*level - 1];
1651 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
1652 *level - 1, 1, &refs, NULL);
1656 nrefs->bytenr[*level - 1] = bytenr;
1657 nrefs->refs[*level - 1] = refs;
1662 ret = enter_shared_node(root, bytenr, refs,
1665 path->slots[*level]++;
1670 next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize);
1671 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1672 free_extent_buffer(next);
1673 reada_walk_down(root, cur, path->slots[*level]);
1674 next = read_tree_block(root->fs_info, bytenr, ptr_gen);
1675 if (!extent_buffer_uptodate(next)) {
1676 struct btrfs_key node_key;
1678 btrfs_node_key_to_cpu(path->nodes[*level],
1680 path->slots[*level]);
1681 btrfs_add_corrupt_extent_record(root->fs_info,
1683 path->nodes[*level]->start,
1684 root->fs_info->nodesize,
1691 ret = check_child_node(cur, path->slots[*level], next);
1693 free_extent_buffer(next);
1698 if (btrfs_is_leaf(next))
1699 status = btrfs_check_leaf(root, NULL, next);
1701 status = btrfs_check_node(root, NULL, next);
1702 if (status != BTRFS_TREE_BLOCK_CLEAN) {
1703 free_extent_buffer(next);
1708 *level = *level - 1;
1709 free_extent_buffer(path->nodes[*level]);
1710 path->nodes[*level] = next;
1711 path->slots[*level] = 0;
1714 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1718 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1719 struct walk_control *wc, int *level)
1722 struct extent_buffer *leaf;
1724 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1725 leaf = path->nodes[i];
1726 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1731 free_extent_buffer(path->nodes[*level]);
1732 path->nodes[*level] = NULL;
1733 BUG_ON(*level > wc->active_node);
1734 if (*level == wc->active_node)
1735 leave_shared_node(root, wc, *level);
1741 static int check_root_dir(struct inode_record *rec)
1743 struct inode_backref *backref;
1746 if (!rec->found_inode_item || rec->errors)
1748 if (rec->nlink != 1 || rec->found_link != 0)
1750 if (list_empty(&rec->backrefs))
1752 backref = to_inode_backref(rec->backrefs.next);
1753 if (!backref->found_inode_ref)
1755 if (backref->index != 0 || backref->namelen != 2 ||
1756 memcmp(backref->name, "..", 2))
1758 if (backref->found_dir_index || backref->found_dir_item)
1765 static int repair_inode_isize(struct btrfs_trans_handle *trans,
1766 struct btrfs_root *root, struct btrfs_path *path,
1767 struct inode_record *rec)
1769 struct btrfs_inode_item *ei;
1770 struct btrfs_key key;
1773 key.objectid = rec->ino;
1774 key.type = BTRFS_INODE_ITEM_KEY;
1775 key.offset = (u64)-1;
1777 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1781 if (!path->slots[0]) {
1788 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1789 if (key.objectid != rec->ino) {
1794 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1795 struct btrfs_inode_item);
1796 btrfs_set_inode_size(path->nodes[0], ei, rec->found_size);
1797 btrfs_mark_buffer_dirty(path->nodes[0]);
1798 rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
1799 printf("reset isize for dir %llu root %llu\n", rec->ino,
1800 root->root_key.objectid);
1802 btrfs_release_path(path);
1806 static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
1807 struct btrfs_root *root,
1808 struct btrfs_path *path,
1809 struct inode_record *rec)
1813 ret = btrfs_add_orphan_item(trans, root, path, rec->ino);
1814 btrfs_release_path(path);
1816 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1820 static int repair_inode_nbytes(struct btrfs_trans_handle *trans,
1821 struct btrfs_root *root,
1822 struct btrfs_path *path,
1823 struct inode_record *rec)
1825 struct btrfs_inode_item *ei;
1826 struct btrfs_key key;
1829 key.objectid = rec->ino;
1830 key.type = BTRFS_INODE_ITEM_KEY;
1833 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1840 /* Since ret == 0, no need to check anything */
1841 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1842 struct btrfs_inode_item);
1843 btrfs_set_inode_nbytes(path->nodes[0], ei, rec->found_size);
1844 btrfs_mark_buffer_dirty(path->nodes[0]);
1845 rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
1846 printf("reset nbytes for ino %llu root %llu\n",
1847 rec->ino, root->root_key.objectid);
1849 btrfs_release_path(path);
1853 static int add_missing_dir_index(struct btrfs_root *root,
1854 struct cache_tree *inode_cache,
1855 struct inode_record *rec,
1856 struct inode_backref *backref)
1858 struct btrfs_path path;
1859 struct btrfs_trans_handle *trans;
1860 struct btrfs_dir_item *dir_item;
1861 struct extent_buffer *leaf;
1862 struct btrfs_key key;
1863 struct btrfs_disk_key disk_key;
1864 struct inode_record *dir_rec;
1865 unsigned long name_ptr;
1866 u32 data_size = sizeof(*dir_item) + backref->namelen;
1869 trans = btrfs_start_transaction(root, 1);
1871 return PTR_ERR(trans);
1873 fprintf(stderr, "repairing missing dir index item for inode %llu\n",
1874 (unsigned long long)rec->ino);
1876 btrfs_init_path(&path);
1877 key.objectid = backref->dir;
1878 key.type = BTRFS_DIR_INDEX_KEY;
1879 key.offset = backref->index;
1880 ret = btrfs_insert_empty_item(trans, root, &path, &key, data_size);
1883 leaf = path.nodes[0];
1884 dir_item = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_dir_item);
1886 disk_key.objectid = cpu_to_le64(rec->ino);
1887 disk_key.type = BTRFS_INODE_ITEM_KEY;
1888 disk_key.offset = 0;
1890 btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
1891 btrfs_set_dir_type(leaf, dir_item, imode_to_type(rec->imode));
1892 btrfs_set_dir_data_len(leaf, dir_item, 0);
1893 btrfs_set_dir_name_len(leaf, dir_item, backref->namelen);
1894 name_ptr = (unsigned long)(dir_item + 1);
1895 write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen);
1896 btrfs_mark_buffer_dirty(leaf);
1897 btrfs_release_path(&path);
1898 btrfs_commit_transaction(trans, root);
1900 backref->found_dir_index = 1;
1901 dir_rec = get_inode_rec(inode_cache, backref->dir, 0);
1902 BUG_ON(IS_ERR(dir_rec));
1905 dir_rec->found_size += backref->namelen;
1906 if (dir_rec->found_size == dir_rec->isize &&
1907 (dir_rec->errors & I_ERR_DIR_ISIZE_WRONG))
1908 dir_rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
1909 if (dir_rec->found_size != dir_rec->isize)
1910 dir_rec->errors |= I_ERR_DIR_ISIZE_WRONG;
1915 static int delete_dir_index(struct btrfs_root *root,
1916 struct inode_backref *backref)
1918 struct btrfs_trans_handle *trans;
1919 struct btrfs_dir_item *di;
1920 struct btrfs_path path;
1923 trans = btrfs_start_transaction(root, 1);
1925 return PTR_ERR(trans);
1927 fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
1928 (unsigned long long)backref->dir,
1929 BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index,
1930 (unsigned long long)root->objectid);
1932 btrfs_init_path(&path);
1933 di = btrfs_lookup_dir_index(trans, root, &path, backref->dir,
1934 backref->name, backref->namelen,
1935 backref->index, -1);
1938 btrfs_release_path(&path);
1939 btrfs_commit_transaction(trans, root);
1946 ret = btrfs_del_item(trans, root, &path);
1948 ret = btrfs_delete_one_dir_name(trans, root, &path, di);
1950 btrfs_release_path(&path);
1951 btrfs_commit_transaction(trans, root);
1955 static int create_inode_item(struct btrfs_root *root,
1956 struct inode_record *rec, int root_dir)
1958 struct btrfs_trans_handle *trans;
1964 trans = btrfs_start_transaction(root, 1);
1965 if (IS_ERR(trans)) {
1966 ret = PTR_ERR(trans);
1970 nlink = root_dir ? 1 : rec->found_link;
1971 if (rec->found_dir_item) {
1972 if (rec->found_file_extent)
1973 fprintf(stderr, "root %llu inode %llu has both a dir "
1974 "item and extents, unsure if it is a dir or a "
1975 "regular file so setting it as a directory\n",
1976 (unsigned long long)root->objectid,
1977 (unsigned long long)rec->ino);
1978 mode = S_IFDIR | 0755;
1979 size = rec->found_size;
1980 } else if (!rec->found_dir_item) {
1981 size = rec->extent_end;
1982 mode = S_IFREG | 0755;
1985 ret = insert_inode_item(trans, root, rec->ino, size, rec->nbytes,
1987 btrfs_commit_transaction(trans, root);
1991 static int repair_inode_backrefs(struct btrfs_root *root,
1992 struct inode_record *rec,
1993 struct cache_tree *inode_cache,
1996 struct inode_backref *tmp, *backref;
1997 u64 root_dirid = btrfs_root_dirid(&root->root_item);
2001 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
2002 if (!delete && rec->ino == root_dirid) {
2003 if (!rec->found_inode_item) {
2004 ret = create_inode_item(root, rec, 1);
2011 /* Index 0 for root dir's are special, don't mess with it */
2012 if (rec->ino == root_dirid && backref->index == 0)
2016 ((backref->found_dir_index && !backref->found_inode_ref) ||
2017 (backref->found_dir_index && backref->found_inode_ref &&
2018 (backref->errors & REF_ERR_INDEX_UNMATCH)))) {
2019 ret = delete_dir_index(root, backref);
2023 list_del(&backref->list);
2028 if (!delete && !backref->found_dir_index &&
2029 backref->found_dir_item && backref->found_inode_ref) {
2030 ret = add_missing_dir_index(root, inode_cache, rec,
2035 if (backref->found_dir_item &&
2036 backref->found_dir_index) {
2037 if (!backref->errors &&
2038 backref->found_inode_ref) {
2039 list_del(&backref->list);
2046 if (!delete && (!backref->found_dir_index &&
2047 !backref->found_dir_item &&
2048 backref->found_inode_ref)) {
2049 struct btrfs_trans_handle *trans;
2050 struct btrfs_key location;
2052 ret = check_dir_conflict(root, backref->name,
2058 * let nlink fixing routine to handle it,
2059 * which can do it better.
2064 location.objectid = rec->ino;
2065 location.type = BTRFS_INODE_ITEM_KEY;
2066 location.offset = 0;
2068 trans = btrfs_start_transaction(root, 1);
2069 if (IS_ERR(trans)) {
2070 ret = PTR_ERR(trans);
2073 fprintf(stderr, "adding missing dir index/item pair "
2075 (unsigned long long)rec->ino);
2076 ret = btrfs_insert_dir_item(trans, root, backref->name,
2078 backref->dir, &location,
2079 imode_to_type(rec->imode),
2082 btrfs_commit_transaction(trans, root);
2086 if (!delete && (backref->found_inode_ref &&
2087 backref->found_dir_index &&
2088 backref->found_dir_item &&
2089 !(backref->errors & REF_ERR_INDEX_UNMATCH) &&
2090 !rec->found_inode_item)) {
2091 ret = create_inode_item(root, rec, 0);
2098 return ret ? ret : repaired;
2102 * To determine the file type for nlink/inode_item repair
2104 * Return 0 if file type is found and BTRFS_FT_* is stored into type.
2105 * Return -ENOENT if file type is not found.
2107 static int find_file_type(struct inode_record *rec, u8 *type)
2109 struct inode_backref *backref;
2111 /* For inode item recovered case */
2112 if (rec->found_inode_item) {
2113 *type = imode_to_type(rec->imode);
2117 list_for_each_entry(backref, &rec->backrefs, list) {
2118 if (backref->found_dir_index || backref->found_dir_item) {
2119 *type = backref->filetype;
2127 * To determine the file name for nlink repair
2129 * Return 0 if file name is found, set name and namelen.
2130 * Return -ENOENT if file name is not found.
2132 static int find_file_name(struct inode_record *rec,
2133 char *name, int *namelen)
2135 struct inode_backref *backref;
2137 list_for_each_entry(backref, &rec->backrefs, list) {
2138 if (backref->found_dir_index || backref->found_dir_item ||
2139 backref->found_inode_ref) {
2140 memcpy(name, backref->name, backref->namelen);
2141 *namelen = backref->namelen;
2148 /* Reset the nlink of the inode to the correct one */
2149 static int reset_nlink(struct btrfs_trans_handle *trans,
2150 struct btrfs_root *root,
2151 struct btrfs_path *path,
2152 struct inode_record *rec)
2154 struct inode_backref *backref;
2155 struct inode_backref *tmp;
2156 struct btrfs_key key;
2157 struct btrfs_inode_item *inode_item;
2160 /* We don't believe this either, reset it and iterate backref */
2161 rec->found_link = 0;
2163 /* Remove all backref including the valid ones */
2164 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
2165 ret = btrfs_unlink(trans, root, rec->ino, backref->dir,
2166 backref->index, backref->name,
2167 backref->namelen, 0);
2171 /* remove invalid backref, so it won't be added back */
2172 if (!(backref->found_dir_index &&
2173 backref->found_dir_item &&
2174 backref->found_inode_ref)) {
2175 list_del(&backref->list);
2182 /* Set nlink to 0 */
2183 key.objectid = rec->ino;
2184 key.type = BTRFS_INODE_ITEM_KEY;
2186 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2193 inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2194 struct btrfs_inode_item);
2195 btrfs_set_inode_nlink(path->nodes[0], inode_item, 0);
2196 btrfs_mark_buffer_dirty(path->nodes[0]);
2197 btrfs_release_path(path);
2200 * Add back valid inode_ref/dir_item/dir_index,
2201 * add_link() will handle the nlink inc, so new nlink must be correct
2203 list_for_each_entry(backref, &rec->backrefs, list) {
2204 ret = btrfs_add_link(trans, root, rec->ino, backref->dir,
2205 backref->name, backref->namelen,
2206 backref->filetype, &backref->index, 1, 0);
2211 btrfs_release_path(path);
2215 static int repair_inode_nlinks(struct btrfs_trans_handle *trans,
2216 struct btrfs_root *root,
2217 struct btrfs_path *path,
2218 struct inode_record *rec)
2220 char namebuf[BTRFS_NAME_LEN] = {0};
2223 int name_recovered = 0;
2224 int type_recovered = 0;
2228 * Get file name and type first before these invalid inode ref
2229 * are deleted by remove_all_invalid_backref()
2231 name_recovered = !find_file_name(rec, namebuf, &namelen);
2232 type_recovered = !find_file_type(rec, &type);
2234 if (!name_recovered) {
2235 printf("Can't get file name for inode %llu, using '%llu' as fallback\n",
2236 rec->ino, rec->ino);
2237 namelen = count_digits(rec->ino);
2238 sprintf(namebuf, "%llu", rec->ino);
2241 if (!type_recovered) {
2242 printf("Can't get file type for inode %llu, using FILE as fallback\n",
2244 type = BTRFS_FT_REG_FILE;
2248 ret = reset_nlink(trans, root, path, rec);
2251 "Failed to reset nlink for inode %llu: %s\n",
2252 rec->ino, strerror(-ret));
2256 if (rec->found_link == 0) {
2257 ret = link_inode_to_lostfound(trans, root, path, rec->ino,
2258 namebuf, namelen, type,
2259 (u64 *)&rec->found_link);
2263 printf("Fixed the nlink of inode %llu\n", rec->ino);
2266 * Clear the flag anyway, or we will loop forever for the same inode
2267 * as it will not be removed from the bad inode list and the dead loop
2270 rec->errors &= ~I_ERR_LINK_COUNT_WRONG;
2271 btrfs_release_path(path);
2276 * Check if there is any normal(reg or prealloc) file extent for given
2278 * This is used to determine the file type when neither its dir_index/item or
2279 * inode_item exists.
2281 * This will *NOT* report error, if any error happens, just consider it does
2282 * not have any normal file extent.
2284 static int find_normal_file_extent(struct btrfs_root *root, u64 ino)
2286 struct btrfs_path path;
2287 struct btrfs_key key;
2288 struct btrfs_key found_key;
2289 struct btrfs_file_extent_item *fi;
2293 btrfs_init_path(&path);
2295 key.type = BTRFS_EXTENT_DATA_KEY;
2298 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
2303 if (ret && path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
2304 ret = btrfs_next_leaf(root, &path);
2311 btrfs_item_key_to_cpu(path.nodes[0], &found_key,
2313 if (found_key.objectid != ino ||
2314 found_key.type != BTRFS_EXTENT_DATA_KEY)
2316 fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
2317 struct btrfs_file_extent_item);
2318 type = btrfs_file_extent_type(path.nodes[0], fi);
2319 if (type != BTRFS_FILE_EXTENT_INLINE) {
2325 btrfs_release_path(&path);
2329 static u32 btrfs_type_to_imode(u8 type)
2331 static u32 imode_by_btrfs_type[] = {
2332 [BTRFS_FT_REG_FILE] = S_IFREG,
2333 [BTRFS_FT_DIR] = S_IFDIR,
2334 [BTRFS_FT_CHRDEV] = S_IFCHR,
2335 [BTRFS_FT_BLKDEV] = S_IFBLK,
2336 [BTRFS_FT_FIFO] = S_IFIFO,
2337 [BTRFS_FT_SOCK] = S_IFSOCK,
2338 [BTRFS_FT_SYMLINK] = S_IFLNK,
2341 return imode_by_btrfs_type[(type)];
2344 static int repair_inode_no_item(struct btrfs_trans_handle *trans,
2345 struct btrfs_root *root,
2346 struct btrfs_path *path,
2347 struct inode_record *rec)
2351 int type_recovered = 0;
2354 printf("Trying to rebuild inode:%llu\n", rec->ino);
2356 type_recovered = !find_file_type(rec, &filetype);
2359 * Try to determine inode type if type not found.
2361 * For found regular file extent, it must be FILE.
2362 * For found dir_item/index, it must be DIR.
2364 * For undetermined one, use FILE as fallback.
2367 * 1. If found backref(inode_index/item is already handled) to it,
2369 * Need new inode-inode ref structure to allow search for that.
2371 if (!type_recovered) {
2372 if (rec->found_file_extent &&
2373 find_normal_file_extent(root, rec->ino)) {
2375 filetype = BTRFS_FT_REG_FILE;
2376 } else if (rec->found_dir_item) {
2378 filetype = BTRFS_FT_DIR;
2379 } else if (!list_empty(&rec->orphan_extents)) {
2381 filetype = BTRFS_FT_REG_FILE;
2383 printf("Can't determine the filetype for inode %llu, assume it is a normal file\n",
2386 filetype = BTRFS_FT_REG_FILE;
2390 ret = btrfs_new_inode(trans, root, rec->ino,
2391 mode | btrfs_type_to_imode(filetype));
2396 * Here inode rebuild is done, we only rebuild the inode item,
2397 * don't repair the nlink(like move to lost+found).
2398 * That is the job of nlink repair.
2400 * We just fill the record and return
2402 rec->found_dir_item = 1;
2403 rec->imode = mode | btrfs_type_to_imode(filetype);
2405 rec->errors &= ~I_ERR_NO_INODE_ITEM;
2406 /* Ensure the inode_nlinks repair function will be called */
2407 rec->errors |= I_ERR_LINK_COUNT_WRONG;
2412 static int repair_inode_orphan_extent(struct btrfs_trans_handle *trans,
2413 struct btrfs_root *root,
2414 struct btrfs_path *path,
2415 struct inode_record *rec)
2417 struct orphan_data_extent *orphan;
2418 struct orphan_data_extent *tmp;
2421 list_for_each_entry_safe(orphan, tmp, &rec->orphan_extents, list) {
2423 * Check for conflicting file extents
2425 * Here we don't know whether the extents is compressed or not,
2426 * so we can only assume it not compressed nor data offset,
2427 * and use its disk_len as extent length.
2429 ret = btrfs_get_extent(NULL, root, path, orphan->objectid,
2430 orphan->offset, orphan->disk_len, 0);
2431 btrfs_release_path(path);
2436 "orphan extent (%llu, %llu) conflicts, delete the orphan\n",
2437 orphan->disk_bytenr, orphan->disk_len);
2438 ret = btrfs_free_extent(trans,
2439 root->fs_info->extent_root,
2440 orphan->disk_bytenr, orphan->disk_len,
2441 0, root->objectid, orphan->objectid,
2446 ret = btrfs_insert_file_extent(trans, root, orphan->objectid,
2447 orphan->offset, orphan->disk_bytenr,
2448 orphan->disk_len, orphan->disk_len);
2452 /* Update file size info */
2453 rec->found_size += orphan->disk_len;
2454 if (rec->found_size == rec->nbytes)
2455 rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
2457 /* Update the file extent hole info too */
2458 ret = del_file_extent_hole(&rec->holes, orphan->offset,
2462 if (RB_EMPTY_ROOT(&rec->holes))
2463 rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
2465 list_del(&orphan->list);
2468 rec->errors &= ~I_ERR_FILE_EXTENT_ORPHAN;
2473 static int repair_inode_discount_extent(struct btrfs_trans_handle *trans,
2474 struct btrfs_root *root,
2475 struct btrfs_path *path,
2476 struct inode_record *rec)
2478 struct rb_node *node;
2479 struct file_extent_hole *hole;
2483 node = rb_first(&rec->holes);
2487 hole = rb_entry(node, struct file_extent_hole, node);
2488 ret = btrfs_punch_hole(trans, root, rec->ino,
2489 hole->start, hole->len);
2492 ret = del_file_extent_hole(&rec->holes, hole->start,
2496 if (RB_EMPTY_ROOT(&rec->holes))
2497 rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
2498 node = rb_first(&rec->holes);
2500 /* special case for a file losing all its file extent */
2502 ret = btrfs_punch_hole(trans, root, rec->ino, 0,
2503 round_up(rec->isize,
2504 root->fs_info->sectorsize));
2508 printf("Fixed discount file extents for inode: %llu in root: %llu\n",
2509 rec->ino, root->objectid);
2514 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
2516 struct btrfs_trans_handle *trans;
2517 struct btrfs_path path;
2520 if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG |
2521 I_ERR_NO_ORPHAN_ITEM |
2522 I_ERR_LINK_COUNT_WRONG |
2523 I_ERR_NO_INODE_ITEM |
2524 I_ERR_FILE_EXTENT_ORPHAN |
2525 I_ERR_FILE_EXTENT_DISCOUNT|
2526 I_ERR_FILE_NBYTES_WRONG)))
2530 * For nlink repair, it may create a dir and add link, so
2531 * 2 for parent(256)'s dir_index and dir_item
2532 * 2 for lost+found dir's inode_item and inode_ref
2533 * 1 for the new inode_ref of the file
2534 * 2 for lost+found dir's dir_index and dir_item for the file
2536 trans = btrfs_start_transaction(root, 7);
2538 return PTR_ERR(trans);
2540 btrfs_init_path(&path);
2541 if (rec->errors & I_ERR_NO_INODE_ITEM)
2542 ret = repair_inode_no_item(trans, root, &path, rec);
2543 if (!ret && rec->errors & I_ERR_FILE_EXTENT_ORPHAN)
2544 ret = repair_inode_orphan_extent(trans, root, &path, rec);
2545 if (!ret && rec->errors & I_ERR_FILE_EXTENT_DISCOUNT)
2546 ret = repair_inode_discount_extent(trans, root, &path, rec);
2547 if (!ret && rec->errors & I_ERR_DIR_ISIZE_WRONG)
2548 ret = repair_inode_isize(trans, root, &path, rec);
2549 if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
2550 ret = repair_inode_orphan_item(trans, root, &path, rec);
2551 if (!ret && rec->errors & I_ERR_LINK_COUNT_WRONG)
2552 ret = repair_inode_nlinks(trans, root, &path, rec);
2553 if (!ret && rec->errors & I_ERR_FILE_NBYTES_WRONG)
2554 ret = repair_inode_nbytes(trans, root, &path, rec);
2555 btrfs_commit_transaction(trans, root);
2556 btrfs_release_path(&path);
2560 static int check_inode_recs(struct btrfs_root *root,
2561 struct cache_tree *inode_cache)
2563 struct cache_extent *cache;
2564 struct ptr_node *node;
2565 struct inode_record *rec;
2566 struct inode_backref *backref;
2571 u64 root_dirid = btrfs_root_dirid(&root->root_item);
2573 if (btrfs_root_refs(&root->root_item) == 0) {
2574 if (!cache_tree_empty(inode_cache))
2575 fprintf(stderr, "warning line %d\n", __LINE__);
2580 * We need to repair backrefs first because we could change some of the
2581 * errors in the inode recs.
2583 * We also need to go through and delete invalid backrefs first and then
2584 * add the correct ones second. We do this because we may get EEXIST
2585 * when adding back the correct index because we hadn't yet deleted the
2588 * For example, if we were missing a dir index then the directories
2589 * isize would be wrong, so if we fixed the isize to what we thought it
2590 * would be and then fixed the backref we'd still have a invalid fs, so
2591 * we need to add back the dir index and then check to see if the isize
2596 if (stage == 3 && !err)
2599 cache = search_cache_extent(inode_cache, 0);
2600 while (repair && cache) {
2601 node = container_of(cache, struct ptr_node, cache);
2603 cache = next_cache_extent(cache);
2605 /* Need to free everything up and rescan */
2607 remove_cache_extent(inode_cache, &node->cache);
2609 free_inode_rec(rec);
2613 if (list_empty(&rec->backrefs))
2616 ret = repair_inode_backrefs(root, rec, inode_cache,
2630 rec = get_inode_rec(inode_cache, root_dirid, 0);
2631 BUG_ON(IS_ERR(rec));
2633 ret = check_root_dir(rec);
2635 fprintf(stderr, "root %llu root dir %llu error\n",
2636 (unsigned long long)root->root_key.objectid,
2637 (unsigned long long)root_dirid);
2638 print_inode_error(root, rec);
2643 struct btrfs_trans_handle *trans;
2645 trans = btrfs_start_transaction(root, 1);
2646 if (IS_ERR(trans)) {
2647 err = PTR_ERR(trans);
2652 "root %llu missing its root dir, recreating\n",
2653 (unsigned long long)root->objectid);
2655 ret = btrfs_make_root_dir(trans, root, root_dirid);
2658 btrfs_commit_transaction(trans, root);
2662 fprintf(stderr, "root %llu root dir %llu not found\n",
2663 (unsigned long long)root->root_key.objectid,
2664 (unsigned long long)root_dirid);
2668 cache = search_cache_extent(inode_cache, 0);
2671 node = container_of(cache, struct ptr_node, cache);
2673 remove_cache_extent(inode_cache, &node->cache);
2675 if (rec->ino == root_dirid ||
2676 rec->ino == BTRFS_ORPHAN_OBJECTID) {
2677 free_inode_rec(rec);
2681 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
2682 ret = check_orphan_item(root, rec->ino);
2684 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
2685 if (can_free_inode_rec(rec)) {
2686 free_inode_rec(rec);
2691 if (!rec->found_inode_item)
2692 rec->errors |= I_ERR_NO_INODE_ITEM;
2693 if (rec->found_link != rec->nlink)
2694 rec->errors |= I_ERR_LINK_COUNT_WRONG;
2696 ret = try_repair_inode(root, rec);
2697 if (ret == 0 && can_free_inode_rec(rec)) {
2698 free_inode_rec(rec);
2704 if (!(repair && ret == 0))
2706 print_inode_error(root, rec);
2707 list_for_each_entry(backref, &rec->backrefs, list) {
2708 if (!backref->found_dir_item)
2709 backref->errors |= REF_ERR_NO_DIR_ITEM;
2710 if (!backref->found_dir_index)
2711 backref->errors |= REF_ERR_NO_DIR_INDEX;
2712 if (!backref->found_inode_ref)
2713 backref->errors |= REF_ERR_NO_INODE_REF;
2714 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
2715 " namelen %u name %s filetype %d errors %x",
2716 (unsigned long long)backref->dir,
2717 (unsigned long long)backref->index,
2718 backref->namelen, backref->name,
2719 backref->filetype, backref->errors);
2720 print_ref_error(backref->errors);
2722 free_inode_rec(rec);
2724 return (error > 0) ? -1 : 0;
2727 static struct root_record *get_root_rec(struct cache_tree *root_cache,
2730 struct cache_extent *cache;
2731 struct root_record *rec = NULL;
2734 cache = lookup_cache_extent(root_cache, objectid, 1);
2736 rec = container_of(cache, struct root_record, cache);
2738 rec = calloc(1, sizeof(*rec));
2740 return ERR_PTR(-ENOMEM);
2741 rec->objectid = objectid;
2742 INIT_LIST_HEAD(&rec->backrefs);
2743 rec->cache.start = objectid;
2744 rec->cache.size = 1;
2746 ret = insert_cache_extent(root_cache, &rec->cache);
2748 return ERR_PTR(-EEXIST);
2753 static struct root_backref *get_root_backref(struct root_record *rec,
2754 u64 ref_root, u64 dir, u64 index,
2755 const char *name, int namelen)
2757 struct root_backref *backref;
2759 list_for_each_entry(backref, &rec->backrefs, list) {
2760 if (backref->ref_root != ref_root || backref->dir != dir ||
2761 backref->namelen != namelen)
2763 if (memcmp(name, backref->name, namelen))
2768 backref = calloc(1, sizeof(*backref) + namelen + 1);
2771 backref->ref_root = ref_root;
2773 backref->index = index;
2774 backref->namelen = namelen;
2775 memcpy(backref->name, name, namelen);
2776 backref->name[namelen] = '\0';
2777 list_add_tail(&backref->list, &rec->backrefs);
2781 static void free_root_record(struct cache_extent *cache)
2783 struct root_record *rec;
2784 struct root_backref *backref;
2786 rec = container_of(cache, struct root_record, cache);
2787 while (!list_empty(&rec->backrefs)) {
2788 backref = to_root_backref(rec->backrefs.next);
2789 list_del(&backref->list);
2796 FREE_EXTENT_CACHE_BASED_TREE(root_recs, free_root_record);
2798 static int add_root_backref(struct cache_tree *root_cache,
2799 u64 root_id, u64 ref_root, u64 dir, u64 index,
2800 const char *name, int namelen,
2801 int item_type, int errors)
2803 struct root_record *rec;
2804 struct root_backref *backref;
2806 rec = get_root_rec(root_cache, root_id);
2807 BUG_ON(IS_ERR(rec));
2808 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
2811 backref->errors |= errors;
2813 if (item_type != BTRFS_DIR_ITEM_KEY) {
2814 if (backref->found_dir_index || backref->found_back_ref ||
2815 backref->found_forward_ref) {
2816 if (backref->index != index)
2817 backref->errors |= REF_ERR_INDEX_UNMATCH;
2819 backref->index = index;
2823 if (item_type == BTRFS_DIR_ITEM_KEY) {
2824 if (backref->found_forward_ref)
2826 backref->found_dir_item = 1;
2827 } else if (item_type == BTRFS_DIR_INDEX_KEY) {
2828 backref->found_dir_index = 1;
2829 } else if (item_type == BTRFS_ROOT_REF_KEY) {
2830 if (backref->found_forward_ref)
2831 backref->errors |= REF_ERR_DUP_ROOT_REF;
2832 else if (backref->found_dir_item)
2834 backref->found_forward_ref = 1;
2835 } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
2836 if (backref->found_back_ref)
2837 backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
2838 backref->found_back_ref = 1;
2843 if (backref->found_forward_ref && backref->found_dir_item)
2844 backref->reachable = 1;
2848 static int merge_root_recs(struct btrfs_root *root,
2849 struct cache_tree *src_cache,
2850 struct cache_tree *dst_cache)
2852 struct cache_extent *cache;
2853 struct ptr_node *node;
2854 struct inode_record *rec;
2855 struct inode_backref *backref;
2858 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
2859 free_inode_recs_tree(src_cache);
2864 cache = search_cache_extent(src_cache, 0);
2867 node = container_of(cache, struct ptr_node, cache);
2869 remove_cache_extent(src_cache, &node->cache);
2872 ret = is_child_root(root, root->objectid, rec->ino);
2878 list_for_each_entry(backref, &rec->backrefs, list) {
2879 BUG_ON(backref->found_inode_ref);
2880 if (backref->found_dir_item)
2881 add_root_backref(dst_cache, rec->ino,
2882 root->root_key.objectid, backref->dir,
2883 backref->index, backref->name,
2884 backref->namelen, BTRFS_DIR_ITEM_KEY,
2886 if (backref->found_dir_index)
2887 add_root_backref(dst_cache, rec->ino,
2888 root->root_key.objectid, backref->dir,
2889 backref->index, backref->name,
2890 backref->namelen, BTRFS_DIR_INDEX_KEY,
2894 free_inode_rec(rec);
2901 static int check_root_refs(struct btrfs_root *root,
2902 struct cache_tree *root_cache)
2904 struct root_record *rec;
2905 struct root_record *ref_root;
2906 struct root_backref *backref;
2907 struct cache_extent *cache;
2913 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
2914 BUG_ON(IS_ERR(rec));
2917 /* fixme: this can not detect circular references */
2920 cache = search_cache_extent(root_cache, 0);
2924 rec = container_of(cache, struct root_record, cache);
2925 cache = next_cache_extent(cache);
2927 if (rec->found_ref == 0)
2930 list_for_each_entry(backref, &rec->backrefs, list) {
2931 if (!backref->reachable)
2934 ref_root = get_root_rec(root_cache,
2936 BUG_ON(IS_ERR(ref_root));
2937 if (ref_root->found_ref > 0)
2940 backref->reachable = 0;
2942 if (rec->found_ref == 0)
2948 cache = search_cache_extent(root_cache, 0);
2952 rec = container_of(cache, struct root_record, cache);
2953 cache = next_cache_extent(cache);
2955 if (rec->found_ref == 0 &&
2956 rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
2957 rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
2958 ret = check_orphan_item(root->fs_info->tree_root,
2964 * If we don't have a root item then we likely just have
2965 * a dir item in a snapshot for this root but no actual
2966 * ref key or anything so it's meaningless.
2968 if (!rec->found_root_item)
2971 fprintf(stderr, "fs tree %llu not referenced\n",
2972 (unsigned long long)rec->objectid);
2976 if (rec->found_ref > 0 && !rec->found_root_item)
2978 list_for_each_entry(backref, &rec->backrefs, list) {
2979 if (!backref->found_dir_item)
2980 backref->errors |= REF_ERR_NO_DIR_ITEM;
2981 if (!backref->found_dir_index)
2982 backref->errors |= REF_ERR_NO_DIR_INDEX;
2983 if (!backref->found_back_ref)
2984 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
2985 if (!backref->found_forward_ref)
2986 backref->errors |= REF_ERR_NO_ROOT_REF;
2987 if (backref->reachable && backref->errors)
2994 fprintf(stderr, "fs tree %llu refs %u %s\n",
2995 (unsigned long long)rec->objectid, rec->found_ref,
2996 rec->found_root_item ? "" : "not found");
2998 list_for_each_entry(backref, &rec->backrefs, list) {
2999 if (!backref->reachable)
3001 if (!backref->errors && rec->found_root_item)
3003 fprintf(stderr, "\tunresolved ref root %llu dir %llu"
3004 " index %llu namelen %u name %s errors %x\n",
3005 (unsigned long long)backref->ref_root,
3006 (unsigned long long)backref->dir,
3007 (unsigned long long)backref->index,
3008 backref->namelen, backref->name,
3010 print_ref_error(backref->errors);
3013 return errors > 0 ? 1 : 0;
3016 static int process_root_ref(struct extent_buffer *eb, int slot,
3017 struct btrfs_key *key,
3018 struct cache_tree *root_cache)
3024 struct btrfs_root_ref *ref;
3025 char namebuf[BTRFS_NAME_LEN];
3028 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
3030 dirid = btrfs_root_ref_dirid(eb, ref);
3031 index = btrfs_root_ref_sequence(eb, ref);
3032 name_len = btrfs_root_ref_name_len(eb, ref);
3034 if (name_len <= BTRFS_NAME_LEN) {
3038 len = BTRFS_NAME_LEN;
3039 error = REF_ERR_NAME_TOO_LONG;
3041 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
3043 if (key->type == BTRFS_ROOT_REF_KEY) {
3044 add_root_backref(root_cache, key->offset, key->objectid, dirid,
3045 index, namebuf, len, key->type, error);
3047 add_root_backref(root_cache, key->objectid, key->offset, dirid,
3048 index, namebuf, len, key->type, error);
3053 static void free_corrupt_block(struct cache_extent *cache)
3055 struct btrfs_corrupt_block *corrupt;
3057 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
3061 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
3064 * Repair the btree of the given root.
3066 * The fix is to remove the node key in corrupt_blocks cache_tree.
3067 * and rebalance the tree.
3068 * After the fix, the btree should be writeable.
3070 static int repair_btree(struct btrfs_root *root,
3071 struct cache_tree *corrupt_blocks)
3073 struct btrfs_trans_handle *trans;
3074 struct btrfs_path path;
3075 struct btrfs_corrupt_block *corrupt;
3076 struct cache_extent *cache;
3077 struct btrfs_key key;
3082 if (cache_tree_empty(corrupt_blocks))
3085 trans = btrfs_start_transaction(root, 1);
3086 if (IS_ERR(trans)) {
3087 ret = PTR_ERR(trans);
3088 fprintf(stderr, "Error starting transaction: %s\n",
3092 btrfs_init_path(&path);
3093 cache = first_cache_extent(corrupt_blocks);
3095 corrupt = container_of(cache, struct btrfs_corrupt_block,
3097 level = corrupt->level;
3098 path.lowest_level = level;
3099 key.objectid = corrupt->key.objectid;
3100 key.type = corrupt->key.type;
3101 key.offset = corrupt->key.offset;
3104 * Here we don't want to do any tree balance, since it may
3105 * cause a balance with corrupted brother leaf/node,
3106 * so ins_len set to 0 here.
3107 * Balance will be done after all corrupt node/leaf is deleted.
3109 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
3112 offset = btrfs_node_blockptr(path.nodes[level],
3115 /* Remove the ptr */
3116 ret = btrfs_del_ptr(root, &path, level, path.slots[level]);
3120 * Remove the corresponding extent
3121 * return value is not concerned.
3123 btrfs_release_path(&path);
3124 ret = btrfs_free_extent(trans, root, offset,
3125 root->fs_info->nodesize, 0,
3126 root->root_key.objectid, level - 1, 0);
3127 cache = next_cache_extent(cache);
3130 /* Balance the btree using btrfs_search_slot() */
3131 cache = first_cache_extent(corrupt_blocks);
3133 corrupt = container_of(cache, struct btrfs_corrupt_block,
3135 memcpy(&key, &corrupt->key, sizeof(key));
3136 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
3139 /* return will always >0 since it won't find the item */
3141 btrfs_release_path(&path);
3142 cache = next_cache_extent(cache);
3145 btrfs_commit_transaction(trans, root);
3146 btrfs_release_path(&path);
3150 static int check_fs_root(struct btrfs_root *root,
3151 struct cache_tree *root_cache,
3152 struct walk_control *wc)
3158 struct btrfs_path path;
3159 struct shared_node root_node;
3160 struct root_record *rec;
3161 struct btrfs_root_item *root_item = &root->root_item;
3162 struct cache_tree corrupt_blocks;
3163 struct orphan_data_extent *orphan;
3164 struct orphan_data_extent *tmp;
3165 enum btrfs_tree_block_status status;
3166 struct node_refs nrefs;
3169 * Reuse the corrupt_block cache tree to record corrupted tree block
3171 * Unlike the usage in extent tree check, here we do it in a per
3172 * fs/subvol tree base.
3174 cache_tree_init(&corrupt_blocks);
3175 root->fs_info->corrupt_blocks = &corrupt_blocks;
3177 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
3178 rec = get_root_rec(root_cache, root->root_key.objectid);
3179 BUG_ON(IS_ERR(rec));
3180 if (btrfs_root_refs(root_item) > 0)
3181 rec->found_root_item = 1;
3184 btrfs_init_path(&path);
3185 memset(&root_node, 0, sizeof(root_node));
3186 cache_tree_init(&root_node.root_cache);
3187 cache_tree_init(&root_node.inode_cache);
3188 memset(&nrefs, 0, sizeof(nrefs));
3190 /* Move the orphan extent record to corresponding inode_record */
3191 list_for_each_entry_safe(orphan, tmp,
3192 &root->orphan_data_extents, list) {
3193 struct inode_record *inode;
3195 inode = get_inode_rec(&root_node.inode_cache, orphan->objectid,
3197 BUG_ON(IS_ERR(inode));
3198 inode->errors |= I_ERR_FILE_EXTENT_ORPHAN;
3199 list_move(&orphan->list, &inode->orphan_extents);
3202 level = btrfs_header_level(root->node);
3203 memset(wc->nodes, 0, sizeof(wc->nodes));
3204 wc->nodes[level] = &root_node;
3205 wc->active_node = level;
3206 wc->root_level = level;
3208 /* We may not have checked the root block, lets do that now */
3209 if (btrfs_is_leaf(root->node))
3210 status = btrfs_check_leaf(root, NULL, root->node);
3212 status = btrfs_check_node(root, NULL, root->node);
3213 if (status != BTRFS_TREE_BLOCK_CLEAN)
3216 if (btrfs_root_refs(root_item) > 0 ||
3217 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
3218 path.nodes[level] = root->node;
3219 extent_buffer_get(root->node);
3220 path.slots[level] = 0;
3222 struct btrfs_key key;
3223 struct btrfs_disk_key found_key;
3225 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3226 level = root_item->drop_level;
3227 path.lowest_level = level;
3228 if (level > btrfs_header_level(root->node) ||
3229 level >= BTRFS_MAX_LEVEL) {
3230 error("ignoring invalid drop level: %u", level);
3233 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3236 btrfs_node_key(path.nodes[level], &found_key,
3238 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
3239 sizeof(found_key)));
3243 wret = walk_down_tree(root, &path, wc, &level, &nrefs);
3249 wret = walk_up_tree(root, &path, wc, &level);
3256 btrfs_release_path(&path);
3258 if (!cache_tree_empty(&corrupt_blocks)) {
3259 struct cache_extent *cache;
3260 struct btrfs_corrupt_block *corrupt;
3262 printf("The following tree block(s) is corrupted in tree %llu:\n",
3263 root->root_key.objectid);
3264 cache = first_cache_extent(&corrupt_blocks);
3266 corrupt = container_of(cache,
3267 struct btrfs_corrupt_block,
3269 printf("\ttree block bytenr: %llu, level: %d, node key: (%llu, %u, %llu)\n",
3270 cache->start, corrupt->level,
3271 corrupt->key.objectid, corrupt->key.type,
3272 corrupt->key.offset);
3273 cache = next_cache_extent(cache);
3276 printf("Try to repair the btree for root %llu\n",
3277 root->root_key.objectid);
3278 ret = repair_btree(root, &corrupt_blocks);
3280 fprintf(stderr, "Failed to repair btree: %s\n",
3283 printf("Btree for root %llu is fixed\n",
3284 root->root_key.objectid);
3288 err = merge_root_recs(root, &root_node.root_cache, root_cache);
3292 if (root_node.current) {
3293 root_node.current->checked = 1;
3294 maybe_free_inode_rec(&root_node.inode_cache,
3298 err = check_inode_recs(root, &root_node.inode_cache);
3302 free_corrupt_blocks_tree(&corrupt_blocks);
3303 root->fs_info->corrupt_blocks = NULL;
3304 free_orphan_data_extents(&root->orphan_data_extents);
3308 static int check_fs_roots(struct btrfs_fs_info *fs_info,
3309 struct cache_tree *root_cache)
3311 struct btrfs_path path;
3312 struct btrfs_key key;
3313 struct walk_control wc;
3314 struct extent_buffer *leaf, *tree_node;
3315 struct btrfs_root *tmp_root;
3316 struct btrfs_root *tree_root = fs_info->tree_root;
3320 if (ctx.progress_enabled) {
3321 ctx.tp = TASK_FS_ROOTS;
3322 task_start(ctx.info);
3326 * Just in case we made any changes to the extent tree that weren't
3327 * reflected into the free space cache yet.
3330 reset_cached_block_groups(fs_info);
3331 memset(&wc, 0, sizeof(wc));
3332 cache_tree_init(&wc.shared);
3333 btrfs_init_path(&path);
3338 key.type = BTRFS_ROOT_ITEM_KEY;
3339 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
3344 tree_node = tree_root->node;
3346 if (tree_node != tree_root->node) {
3347 free_root_recs_tree(root_cache);
3348 btrfs_release_path(&path);
3351 leaf = path.nodes[0];
3352 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
3353 ret = btrfs_next_leaf(tree_root, &path);
3359 leaf = path.nodes[0];
3361 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
3362 if (key.type == BTRFS_ROOT_ITEM_KEY &&
3363 fs_root_objectid(key.objectid)) {
3364 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
3365 tmp_root = btrfs_read_fs_root_no_cache(
3368 key.offset = (u64)-1;
3369 tmp_root = btrfs_read_fs_root(
3372 if (IS_ERR(tmp_root)) {
3376 ret = check_fs_root(tmp_root, root_cache, &wc);
3377 if (ret == -EAGAIN) {
3378 free_root_recs_tree(root_cache);
3379 btrfs_release_path(&path);
3384 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
3385 btrfs_free_fs_root(tmp_root);
3386 } else if (key.type == BTRFS_ROOT_REF_KEY ||
3387 key.type == BTRFS_ROOT_BACKREF_KEY) {
3388 process_root_ref(leaf, path.slots[0], &key,
3395 btrfs_release_path(&path);
3397 free_extent_cache_tree(&wc.shared);
3398 if (!cache_tree_empty(&wc.shared))
3399 fprintf(stderr, "warning line %d\n", __LINE__);
3401 task_stop(ctx.info);
3406 static struct tree_backref *find_tree_backref(struct extent_record *rec,
3407 u64 parent, u64 root)
3409 struct rb_node *node;
3410 struct tree_backref *back = NULL;
3411 struct tree_backref match = {
3418 match.parent = parent;
3419 match.node.full_backref = 1;
3424 node = rb_search(&rec->backref_tree, &match.node.node,
3425 (rb_compare_keys)compare_extent_backref, NULL);
3427 back = to_tree_backref(rb_node_to_extent_backref(node));
3432 static struct data_backref *find_data_backref(struct extent_record *rec,
3433 u64 parent, u64 root,
3434 u64 owner, u64 offset,
3436 u64 disk_bytenr, u64 bytes)
3438 struct rb_node *node;
3439 struct data_backref *back = NULL;
3440 struct data_backref match = {
3447 .found_ref = found_ref,
3448 .disk_bytenr = disk_bytenr,
3452 match.parent = parent;
3453 match.node.full_backref = 1;
3458 node = rb_search(&rec->backref_tree, &match.node.node,
3459 (rb_compare_keys)compare_extent_backref, NULL);
3461 back = to_data_backref(rb_node_to_extent_backref(node));
3466 static int do_check_fs_roots(struct btrfs_fs_info *fs_info,
3467 struct cache_tree *root_cache)
3471 if (!ctx.progress_enabled)
3472 fprintf(stderr, "checking fs roots\n");
3473 if (check_mode == CHECK_MODE_LOWMEM)
3474 ret = check_fs_roots_lowmem(fs_info);
3476 ret = check_fs_roots(fs_info, root_cache);
3481 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
3483 struct extent_backref *back, *tmp;
3484 struct tree_backref *tback;
3485 struct data_backref *dback;
3489 rbtree_postorder_for_each_entry_safe(back, tmp,
3490 &rec->backref_tree, node) {
3491 if (!back->found_extent_tree) {
3495 if (back->is_data) {
3496 dback = to_data_backref(back);
3498 "data backref %llu %s %llu owner %llu offset %llu num_refs %lu not found in extent tree\n",
3499 (unsigned long long)rec->start,
3500 back->full_backref ?
3502 back->full_backref ?
3503 (unsigned long long)dback->parent :
3504 (unsigned long long)dback->root,
3505 (unsigned long long)dback->owner,
3506 (unsigned long long)dback->offset,
3507 (unsigned long)dback->num_refs);
3509 tback = to_tree_backref(back);
3511 "tree backref %llu parent %llu root %llu not found in extent tree\n",
3512 (unsigned long long)rec->start,
3513 (unsigned long long)tback->parent,
3514 (unsigned long long)tback->root);
3517 if (!back->is_data && !back->found_ref) {
3521 tback = to_tree_backref(back);
3523 "backref %llu %s %llu not referenced back %p\n",
3524 (unsigned long long)rec->start,
3525 back->full_backref ? "parent" : "root",
3526 back->full_backref ?
3527 (unsigned long long)tback->parent :
3528 (unsigned long long)tback->root, back);
3530 if (back->is_data) {
3531 dback = to_data_backref(back);
3532 if (dback->found_ref != dback->num_refs) {
3537 "incorrect local backref count on %llu %s %llu owner %llu offset %llu found %u wanted %u back %p\n",
3538 (unsigned long long)rec->start,
3539 back->full_backref ?
3541 back->full_backref ?
3542 (unsigned long long)dback->parent :
3543 (unsigned long long)dback->root,
3544 (unsigned long long)dback->owner,
3545 (unsigned long long)dback->offset,
3546 dback->found_ref, dback->num_refs,
3549 if (dback->disk_bytenr != rec->start) {
3554 "backref disk bytenr does not match extent record, bytenr=%llu, ref bytenr=%llu\n",
3555 (unsigned long long)rec->start,
3556 (unsigned long long)dback->disk_bytenr);
3559 if (dback->bytes != rec->nr) {
3564 "backref bytes do not match extent backref, bytenr=%llu, ref bytes=%llu, backref bytes=%llu\n",
3565 (unsigned long long)rec->start,
3566 (unsigned long long)rec->nr,
3567 (unsigned long long)dback->bytes);
3570 if (!back->is_data) {
3573 dback = to_data_backref(back);
3574 found += dback->found_ref;
3577 if (found != rec->refs) {
3582 "incorrect global backref count on %llu found %llu wanted %llu\n",
3583 (unsigned long long)rec->start,
3584 (unsigned long long)found,
3585 (unsigned long long)rec->refs);
3591 static void __free_one_backref(struct rb_node *node)
3593 struct extent_backref *back = rb_node_to_extent_backref(node);
3598 static void free_all_extent_backrefs(struct extent_record *rec)
3600 rb_free_nodes(&rec->backref_tree, __free_one_backref);
3603 static void free_extent_record_cache(struct cache_tree *extent_cache)
3605 struct cache_extent *cache;
3606 struct extent_record *rec;
3609 cache = first_cache_extent(extent_cache);
3612 rec = container_of(cache, struct extent_record, cache);
3613 remove_cache_extent(extent_cache, cache);
3614 free_all_extent_backrefs(rec);
3619 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
3620 struct extent_record *rec)
3622 if (rec->content_checked && rec->owner_ref_checked &&
3623 rec->extent_item_refs == rec->refs && rec->refs > 0 &&
3624 rec->num_duplicates == 0 && !all_backpointers_checked(rec, 0) &&
3625 !rec->bad_full_backref && !rec->crossing_stripes &&
3626 !rec->wrong_chunk_type) {
3627 remove_cache_extent(extent_cache, &rec->cache);
3628 free_all_extent_backrefs(rec);
3629 list_del_init(&rec->list);
3635 static int check_owner_ref(struct btrfs_root *root,
3636 struct extent_record *rec,
3637 struct extent_buffer *buf)
3639 struct extent_backref *node, *tmp;
3640 struct tree_backref *back;
3641 struct btrfs_root *ref_root;
3642 struct btrfs_key key;
3643 struct btrfs_path path;
3644 struct extent_buffer *parent;
3649 rbtree_postorder_for_each_entry_safe(node, tmp,
3650 &rec->backref_tree, node) {
3653 if (!node->found_ref)
3655 if (node->full_backref)
3657 back = to_tree_backref(node);
3658 if (btrfs_header_owner(buf) == back->root)
3661 BUG_ON(rec->is_root);
3663 /* try to find the block by search corresponding fs tree */
3664 key.objectid = btrfs_header_owner(buf);
3665 key.type = BTRFS_ROOT_ITEM_KEY;
3666 key.offset = (u64)-1;
3668 ref_root = btrfs_read_fs_root(root->fs_info, &key);
3669 if (IS_ERR(ref_root))
3672 level = btrfs_header_level(buf);
3674 btrfs_item_key_to_cpu(buf, &key, 0);
3676 btrfs_node_key_to_cpu(buf, &key, 0);
3678 btrfs_init_path(&path);
3679 path.lowest_level = level + 1;
3680 ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
3684 parent = path.nodes[level + 1];
3685 if (parent && buf->start == btrfs_node_blockptr(parent,
3686 path.slots[level + 1]))
3689 btrfs_release_path(&path);
3690 return found ? 0 : 1;
3693 static int is_extent_tree_record(struct extent_record *rec)
3695 struct extent_backref *node, *tmp;
3696 struct tree_backref *back;
3699 rbtree_postorder_for_each_entry_safe(node, tmp,
3700 &rec->backref_tree, node) {
3703 back = to_tree_backref(node);
3704 if (node->full_backref)
3706 if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
3713 static int record_bad_block_io(struct btrfs_fs_info *info,
3714 struct cache_tree *extent_cache,
3717 struct extent_record *rec;
3718 struct cache_extent *cache;
3719 struct btrfs_key key;
3721 cache = lookup_cache_extent(extent_cache, start, len);
3725 rec = container_of(cache, struct extent_record, cache);
3726 if (!is_extent_tree_record(rec))
3729 btrfs_disk_key_to_cpu(&key, &rec->parent_key);
3730 return btrfs_add_corrupt_extent_record(info, &key, start, len, 0);
3733 static int swap_values(struct btrfs_root *root, struct btrfs_path *path,
3734 struct extent_buffer *buf, int slot)
3736 if (btrfs_header_level(buf)) {
3737 struct btrfs_key_ptr ptr1, ptr2;
3739 read_extent_buffer(buf, &ptr1, btrfs_node_key_ptr_offset(slot),
3740 sizeof(struct btrfs_key_ptr));
3741 read_extent_buffer(buf, &ptr2,
3742 btrfs_node_key_ptr_offset(slot + 1),
3743 sizeof(struct btrfs_key_ptr));
3744 write_extent_buffer(buf, &ptr1,
3745 btrfs_node_key_ptr_offset(slot + 1),
3746 sizeof(struct btrfs_key_ptr));
3747 write_extent_buffer(buf, &ptr2,
3748 btrfs_node_key_ptr_offset(slot),
3749 sizeof(struct btrfs_key_ptr));
3751 struct btrfs_disk_key key;
3753 btrfs_node_key(buf, &key, 0);
3754 btrfs_fixup_low_keys(root, path, &key,
3755 btrfs_header_level(buf) + 1);
3758 struct btrfs_item *item1, *item2;
3759 struct btrfs_key k1, k2;
3760 char *item1_data, *item2_data;
3761 u32 item1_offset, item2_offset, item1_size, item2_size;
3763 item1 = btrfs_item_nr(slot);
3764 item2 = btrfs_item_nr(slot + 1);
3765 btrfs_item_key_to_cpu(buf, &k1, slot);
3766 btrfs_item_key_to_cpu(buf, &k2, slot + 1);
3767 item1_offset = btrfs_item_offset(buf, item1);
3768 item2_offset = btrfs_item_offset(buf, item2);
3769 item1_size = btrfs_item_size(buf, item1);
3770 item2_size = btrfs_item_size(buf, item2);
3772 item1_data = malloc(item1_size);
3775 item2_data = malloc(item2_size);
3781 read_extent_buffer(buf, item1_data, item1_offset, item1_size);
3782 read_extent_buffer(buf, item2_data, item2_offset, item2_size);
3784 write_extent_buffer(buf, item1_data, item2_offset, item2_size);
3785 write_extent_buffer(buf, item2_data, item1_offset, item1_size);
3789 btrfs_set_item_offset(buf, item1, item2_offset);
3790 btrfs_set_item_offset(buf, item2, item1_offset);
3791 btrfs_set_item_size(buf, item1, item2_size);
3792 btrfs_set_item_size(buf, item2, item1_size);
3794 path->slots[0] = slot;
3795 btrfs_set_item_key_unsafe(root, path, &k2);
3796 path->slots[0] = slot + 1;
3797 btrfs_set_item_key_unsafe(root, path, &k1);
3802 static int fix_key_order(struct btrfs_root *root, struct btrfs_path *path)
3804 struct extent_buffer *buf;
3805 struct btrfs_key k1, k2;
3807 int level = path->lowest_level;
3810 buf = path->nodes[level];
3811 for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
3813 btrfs_node_key_to_cpu(buf, &k1, i);
3814 btrfs_node_key_to_cpu(buf, &k2, i + 1);
3816 btrfs_item_key_to_cpu(buf, &k1, i);
3817 btrfs_item_key_to_cpu(buf, &k2, i + 1);
3819 if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
3821 ret = swap_values(root, path, buf, i);
3824 btrfs_mark_buffer_dirty(buf);
3830 static int delete_bogus_item(struct btrfs_root *root,
3831 struct btrfs_path *path,
3832 struct extent_buffer *buf, int slot)
3834 struct btrfs_key key;
3835 int nritems = btrfs_header_nritems(buf);
3837 btrfs_item_key_to_cpu(buf, &key, slot);
3839 /* These are all the keys we can deal with missing. */
3840 if (key.type != BTRFS_DIR_INDEX_KEY &&
3841 key.type != BTRFS_EXTENT_ITEM_KEY &&
3842 key.type != BTRFS_METADATA_ITEM_KEY &&
3843 key.type != BTRFS_TREE_BLOCK_REF_KEY &&
3844 key.type != BTRFS_EXTENT_DATA_REF_KEY)
3847 printf("Deleting bogus item [%llu,%u,%llu] at slot %d on block %llu\n",
3848 (unsigned long long)key.objectid, key.type,
3849 (unsigned long long)key.offset, slot, buf->start);
3850 memmove_extent_buffer(buf, btrfs_item_nr_offset(slot),
3851 btrfs_item_nr_offset(slot + 1),
3852 sizeof(struct btrfs_item) *
3853 (nritems - slot - 1));
3854 btrfs_set_header_nritems(buf, nritems - 1);
3856 struct btrfs_disk_key disk_key;
3858 btrfs_item_key(buf, &disk_key, 0);
3859 btrfs_fixup_low_keys(root, path, &disk_key, 1);
3861 btrfs_mark_buffer_dirty(buf);
3865 static int fix_item_offset(struct btrfs_root *root, struct btrfs_path *path)
3867 struct extent_buffer *buf;
3871 /* We should only get this for leaves */
3872 BUG_ON(path->lowest_level);
3873 buf = path->nodes[0];
3875 for (i = 0; i < btrfs_header_nritems(buf); i++) {
3876 unsigned int shift = 0, offset;
3878 if (i == 0 && btrfs_item_end_nr(buf, i) !=
3879 BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
3880 if (btrfs_item_end_nr(buf, i) >
3881 BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
3882 ret = delete_bogus_item(root, path, buf, i);
3886 "item is off the end of the leaf, can't fix\n");
3890 shift = BTRFS_LEAF_DATA_SIZE(root->fs_info) -
3891 btrfs_item_end_nr(buf, i);
3892 } else if (i > 0 && btrfs_item_end_nr(buf, i) !=
3893 btrfs_item_offset_nr(buf, i - 1)) {
3894 if (btrfs_item_end_nr(buf, i) >
3895 btrfs_item_offset_nr(buf, i - 1)) {
3896 ret = delete_bogus_item(root, path, buf, i);
3899 fprintf(stderr, "items overlap, can't fix\n");
3903 shift = btrfs_item_offset_nr(buf, i - 1) -
3904 btrfs_item_end_nr(buf, i);
3909 printf("Shifting item nr %d by %u bytes in block %llu\n",
3910 i, shift, (unsigned long long)buf->start);
3911 offset = btrfs_item_offset_nr(buf, i);
3912 memmove_extent_buffer(buf,
3913 btrfs_leaf_data(buf) + offset + shift,
3914 btrfs_leaf_data(buf) + offset,
3915 btrfs_item_size_nr(buf, i));
3916 btrfs_set_item_offset(buf, btrfs_item_nr(i),
3918 btrfs_mark_buffer_dirty(buf);
3922 * We may have moved things, in which case we want to exit so we don't
3923 * write those changes out. Once we have proper abort functionality in
3924 * progs this can be changed to something nicer.
3931 * Attempt to fix basic block failures. If we can't fix it for whatever reason
3932 * then just return -EIO.
3934 static int try_to_fix_bad_block(struct btrfs_root *root,
3935 struct extent_buffer *buf,
3936 enum btrfs_tree_block_status status)
3938 struct btrfs_trans_handle *trans;
3939 struct ulist *roots;
3940 struct ulist_node *node;
3941 struct btrfs_root *search_root;
3942 struct btrfs_path path;
3943 struct ulist_iterator iter;
3944 struct btrfs_key root_key, key;
3947 if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER &&
3948 status != BTRFS_TREE_BLOCK_INVALID_OFFSETS)
3951 ret = btrfs_find_all_roots(NULL, root->fs_info, buf->start, 0, &roots);
3955 btrfs_init_path(&path);
3956 ULIST_ITER_INIT(&iter);
3957 while ((node = ulist_next(roots, &iter))) {
3958 root_key.objectid = node->val;
3959 root_key.type = BTRFS_ROOT_ITEM_KEY;
3960 root_key.offset = (u64)-1;
3962 search_root = btrfs_read_fs_root(root->fs_info, &root_key);
3969 trans = btrfs_start_transaction(search_root, 0);
3970 if (IS_ERR(trans)) {
3971 ret = PTR_ERR(trans);
3975 path.lowest_level = btrfs_header_level(buf);
3976 path.skip_check_block = 1;
3977 if (path.lowest_level)
3978 btrfs_node_key_to_cpu(buf, &key, 0);
3980 btrfs_item_key_to_cpu(buf, &key, 0);
3981 ret = btrfs_search_slot(trans, search_root, &key, &path, 0, 1);
3984 btrfs_commit_transaction(trans, search_root);
3987 if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
3988 ret = fix_key_order(search_root, &path);
3989 else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
3990 ret = fix_item_offset(search_root, &path);
3992 btrfs_commit_transaction(trans, search_root);
3995 btrfs_release_path(&path);
3996 btrfs_commit_transaction(trans, search_root);
3999 btrfs_release_path(&path);
4003 static int check_block(struct btrfs_root *root,
4004 struct cache_tree *extent_cache,
4005 struct extent_buffer *buf, u64 flags)
4007 struct extent_record *rec;
4008 struct cache_extent *cache;
4009 struct btrfs_key key;
4010 enum btrfs_tree_block_status status;
4014 cache = lookup_cache_extent(extent_cache, buf->start, buf->len);
4017 rec = container_of(cache, struct extent_record, cache);
4018 rec->generation = btrfs_header_generation(buf);
4020 level = btrfs_header_level(buf);
4021 if (btrfs_header_nritems(buf) > 0) {
4024 btrfs_item_key_to_cpu(buf, &key, 0);
4026 btrfs_node_key_to_cpu(buf, &key, 0);
4028 rec->info_objectid = key.objectid;
4030 rec->info_level = level;
4032 if (btrfs_is_leaf(buf))
4033 status = btrfs_check_leaf(root, &rec->parent_key, buf);
4035 status = btrfs_check_node(root, &rec->parent_key, buf);
4037 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4039 status = try_to_fix_bad_block(root, buf, status);
4040 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4042 fprintf(stderr, "bad block %llu\n",
4043 (unsigned long long)buf->start);
4046 * Signal to callers we need to start the scan over
4047 * again since we'll have cowed blocks.
4052 rec->content_checked = 1;
4053 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
4054 rec->owner_ref_checked = 1;
4056 ret = check_owner_ref(root, rec, buf);
4058 rec->owner_ref_checked = 1;
4062 maybe_free_extent_rec(extent_cache, rec);
4067 static struct tree_backref *find_tree_backref(struct extent_record *rec,
4068 u64 parent, u64 root)
4070 struct list_head *cur = rec->backrefs.next;
4071 struct extent_backref *node;
4072 struct tree_backref *back;
4074 while (cur != &rec->backrefs) {
4075 node = to_extent_backref(cur);
4079 back = to_tree_backref(node);
4081 if (!node->full_backref)
4083 if (parent == back->parent)
4086 if (node->full_backref)
4088 if (back->root == root)
4096 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
4097 u64 parent, u64 root)
4099 struct tree_backref *ref = malloc(sizeof(*ref));
4103 memset(&ref->node, 0, sizeof(ref->node));
4105 ref->parent = parent;
4106 ref->node.full_backref = 1;
4109 ref->node.full_backref = 0;
4116 static struct data_backref *find_data_backref(struct extent_record *rec,
4117 u64 parent, u64 root,
4118 u64 owner, u64 offset,
4120 u64 disk_bytenr, u64 bytes)
4122 struct list_head *cur = rec->backrefs.next;
4123 struct extent_backref *node;
4124 struct data_backref *back;
4126 while (cur != &rec->backrefs) {
4127 node = to_extent_backref(cur);
4131 back = to_data_backref(node);
4133 if (!node->full_backref)
4135 if (parent == back->parent)
4138 if (node->full_backref)
4140 if (back->root == root && back->owner == owner &&
4141 back->offset == offset) {
4142 if (found_ref && node->found_ref &&
4143 (back->bytes != bytes ||
4144 back->disk_bytenr != disk_bytenr))
4154 static struct data_backref *alloc_data_backref(struct extent_record *rec,
4155 u64 parent, u64 root,
4156 u64 owner, u64 offset,
4159 struct data_backref *ref = malloc(sizeof(*ref));
4163 memset(&ref->node, 0, sizeof(ref->node));
4164 ref->node.is_data = 1;
4167 ref->parent = parent;
4170 ref->node.full_backref = 1;
4174 ref->offset = offset;
4175 ref->node.full_backref = 0;
4177 ref->bytes = max_size;
4180 if (max_size > rec->max_size)
4181 rec->max_size = max_size;
4185 /* Check if the type of extent matches with its chunk */
4186 static void check_extent_type(struct extent_record *rec)
4188 struct btrfs_block_group_cache *bg_cache;
4190 bg_cache = btrfs_lookup_first_block_group(global_info, rec->start);
4194 /* data extent, check chunk directly*/
4195 if (!rec->metadata) {
4196 if (!(bg_cache->flags & BTRFS_BLOCK_GROUP_DATA))
4197 rec->wrong_chunk_type = 1;
4201 /* metadata extent, check the obvious case first */
4202 if (!(bg_cache->flags & (BTRFS_BLOCK_GROUP_SYSTEM |
4203 BTRFS_BLOCK_GROUP_METADATA))) {
4204 rec->wrong_chunk_type = 1;
4209 * Check SYSTEM extent, as it's also marked as metadata, we can only
4210 * make sure it's a SYSTEM extent by its backref
4212 if (!RB_EMPTY_ROOT(&rec->backref_tree)) {
4213 struct extent_backref *node;
4214 struct tree_backref *tback;
4217 node = rb_node_to_extent_backref(rb_first(&rec->backref_tree));
4218 if (node->is_data) {
4219 /* tree block shouldn't have data backref */
4220 rec->wrong_chunk_type = 1;
4223 tback = container_of(node, struct tree_backref, node);
4225 if (tback->root == BTRFS_CHUNK_TREE_OBJECTID)
4226 bg_type = BTRFS_BLOCK_GROUP_SYSTEM;
4228 bg_type = BTRFS_BLOCK_GROUP_METADATA;
4229 if (!(bg_cache->flags & bg_type))
4230 rec->wrong_chunk_type = 1;
4235 * Allocate a new extent record, fill default values from @tmpl and insert int
4236 * @extent_cache. Caller is supposed to make sure the [start,nr) is not in
4237 * the cache, otherwise it fails.
4239 static int add_extent_rec_nolookup(struct cache_tree *extent_cache,
4240 struct extent_record *tmpl)
4242 struct extent_record *rec;
4245 BUG_ON(tmpl->max_size == 0);
4246 rec = malloc(sizeof(*rec));
4249 rec->start = tmpl->start;
4250 rec->max_size = tmpl->max_size;
4251 rec->nr = max(tmpl->nr, tmpl->max_size);
4252 rec->found_rec = tmpl->found_rec;
4253 rec->content_checked = tmpl->content_checked;
4254 rec->owner_ref_checked = tmpl->owner_ref_checked;
4255 rec->num_duplicates = 0;
4256 rec->metadata = tmpl->metadata;
4257 rec->flag_block_full_backref = FLAG_UNSET;
4258 rec->bad_full_backref = 0;
4259 rec->crossing_stripes = 0;
4260 rec->wrong_chunk_type = 0;
4261 rec->is_root = tmpl->is_root;
4262 rec->refs = tmpl->refs;
4263 rec->extent_item_refs = tmpl->extent_item_refs;
4264 rec->parent_generation = tmpl->parent_generation;
4265 INIT_LIST_HEAD(&rec->backrefs);
4266 INIT_LIST_HEAD(&rec->dups);
4267 INIT_LIST_HEAD(&rec->list);
4268 rec->backref_tree = RB_ROOT;
4269 memcpy(&rec->parent_key, &tmpl->parent_key, sizeof(tmpl->parent_key));
4270 rec->cache.start = tmpl->start;
4271 rec->cache.size = tmpl->nr;
4272 ret = insert_cache_extent(extent_cache, &rec->cache);
4277 bytes_used += rec->nr;
4280 rec->crossing_stripes = check_crossing_stripes(global_info,
4281 rec->start, global_info->nodesize);
4282 check_extent_type(rec);
4287 * Lookup and modify an extent, some values of @tmpl are interpreted verbatim,
4289 * - refs - if found, increase refs
4290 * - is_root - if found, set
4291 * - content_checked - if found, set
4292 * - owner_ref_checked - if found, set
4294 * If not found, create a new one, initialize and insert.
4296 static int add_extent_rec(struct cache_tree *extent_cache,
4297 struct extent_record *tmpl)
4299 struct extent_record *rec;
4300 struct cache_extent *cache;
4304 cache = lookup_cache_extent(extent_cache, tmpl->start, tmpl->nr);
4306 rec = container_of(cache, struct extent_record, cache);
4310 rec->nr = max(tmpl->nr, tmpl->max_size);
4313 * We need to make sure to reset nr to whatever the extent
4314 * record says was the real size, this way we can compare it to
4317 if (tmpl->found_rec) {
4318 if (tmpl->start != rec->start || rec->found_rec) {
4319 struct extent_record *tmp;
4322 if (list_empty(&rec->list))
4323 list_add_tail(&rec->list,
4324 &duplicate_extents);
4327 * We have to do this song and dance in case we
4328 * find an extent record that falls inside of
4329 * our current extent record but does not have
4330 * the same objectid.
4332 tmp = malloc(sizeof(*tmp));
4335 tmp->start = tmpl->start;
4336 tmp->max_size = tmpl->max_size;
4339 tmp->metadata = tmpl->metadata;
4340 tmp->extent_item_refs = tmpl->extent_item_refs;
4341 INIT_LIST_HEAD(&tmp->list);
4342 list_add_tail(&tmp->list, &rec->dups);
4343 rec->num_duplicates++;
4350 if (tmpl->extent_item_refs && !dup) {
4351 if (rec->extent_item_refs) {
4353 "block %llu rec extent_item_refs %llu, passed %llu\n",
4354 (unsigned long long)tmpl->start,
4355 (unsigned long long)
4356 rec->extent_item_refs,
4357 (unsigned long long)
4358 tmpl->extent_item_refs);
4360 rec->extent_item_refs = tmpl->extent_item_refs;
4364 if (tmpl->content_checked)
4365 rec->content_checked = 1;
4366 if (tmpl->owner_ref_checked)
4367 rec->owner_ref_checked = 1;
4368 memcpy(&rec->parent_key, &tmpl->parent_key,
4369 sizeof(tmpl->parent_key));
4370 if (tmpl->parent_generation)
4371 rec->parent_generation = tmpl->parent_generation;
4372 if (rec->max_size < tmpl->max_size)
4373 rec->max_size = tmpl->max_size;
4376 * A metadata extent can't cross stripe_len boundary, otherwise
4377 * kernel scrub won't be able to handle it.
4378 * As now stripe_len is fixed to BTRFS_STRIPE_LEN, just check
4382 rec->crossing_stripes = check_crossing_stripes(
4383 global_info, rec->start,
4384 global_info->nodesize);
4385 check_extent_type(rec);
4386 maybe_free_extent_rec(extent_cache, rec);
4390 ret = add_extent_rec_nolookup(extent_cache, tmpl);
4395 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
4396 u64 parent, u64 root, int found_ref)
4398 struct extent_record *rec;
4399 struct tree_backref *back;
4400 struct cache_extent *cache;
4402 bool insert = false;
4404 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4406 struct extent_record tmpl;
4408 memset(&tmpl, 0, sizeof(tmpl));
4409 tmpl.start = bytenr;
4414 ret = add_extent_rec_nolookup(extent_cache, &tmpl);
4418 /* really a bug in cache_extent implement now */
4419 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4424 rec = container_of(cache, struct extent_record, cache);
4425 if (rec->start != bytenr) {
4427 * Several cause, from unaligned bytenr to over lapping extents
4432 back = find_tree_backref(rec, parent, root);
4434 back = alloc_tree_backref(rec, parent, root);
4441 if (back->node.found_ref) {
4443 "Extent back ref already exists for %llu parent %llu root %llu\n",
4444 (unsigned long long)bytenr,
4445 (unsigned long long)parent,
4446 (unsigned long long)root);
4448 back->node.found_ref = 1;
4450 if (back->node.found_extent_tree) {
4452 "extent back ref already exists for %llu parent %llu root %llu\n",
4453 (unsigned long long)bytenr,
4454 (unsigned long long)parent,
4455 (unsigned long long)root);
4457 back->node.found_extent_tree = 1;
4460 WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
4461 compare_extent_backref));
4462 check_extent_type(rec);
4463 maybe_free_extent_rec(extent_cache, rec);
4467 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
4468 u64 parent, u64 root, u64 owner, u64 offset,
4469 u32 num_refs, int found_ref, u64 max_size)
4471 struct extent_record *rec;
4472 struct data_backref *back;
4473 struct cache_extent *cache;
4475 bool insert = false;
4477 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4479 struct extent_record tmpl;
4481 memset(&tmpl, 0, sizeof(tmpl));
4482 tmpl.start = bytenr;
4484 tmpl.max_size = max_size;
4486 ret = add_extent_rec_nolookup(extent_cache, &tmpl);
4490 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4495 rec = container_of(cache, struct extent_record, cache);
4496 if (rec->max_size < max_size)
4497 rec->max_size = max_size;
4500 * If found_ref is set then max_size is the real size and must match the
4501 * existing refs. So if we have already found a ref then we need to
4502 * make sure that this ref matches the existing one, otherwise we need
4503 * to add a new backref so we can notice that the backrefs don't match
4504 * and we need to figure out who is telling the truth. This is to
4505 * account for that awful fsync bug I introduced where we'd end up with
4506 * a btrfs_file_extent_item that would have its length include multiple
4507 * prealloc extents or point inside of a prealloc extent.
4509 back = find_data_backref(rec, parent, root, owner, offset, found_ref,
4512 back = alloc_data_backref(rec, parent, root, owner, offset,
4519 BUG_ON(num_refs != 1);
4520 if (back->node.found_ref)
4521 BUG_ON(back->bytes != max_size);
4522 back->node.found_ref = 1;
4523 back->found_ref += 1;
4524 if (back->bytes != max_size || back->disk_bytenr != bytenr) {
4525 back->bytes = max_size;
4526 back->disk_bytenr = bytenr;
4528 /* Need to reinsert if not already in the tree */
4530 rb_erase(&back->node.node, &rec->backref_tree);
4535 rec->content_checked = 1;
4536 rec->owner_ref_checked = 1;
4538 if (back->node.found_extent_tree) {
4540 "Extent back ref already exists for %llu parent %llu root %llu owner %llu offset %llu num_refs %lu\n",
4541 (unsigned long long)bytenr,
4542 (unsigned long long)parent,
4543 (unsigned long long)root,
4544 (unsigned long long)owner,
4545 (unsigned long long)offset,
4546 (unsigned long)num_refs);
4548 back->num_refs = num_refs;
4549 back->node.found_extent_tree = 1;
4552 WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
4553 compare_extent_backref));
4555 maybe_free_extent_rec(extent_cache, rec);
4559 static int add_pending(struct cache_tree *pending,
4560 struct cache_tree *seen, u64 bytenr, u32 size)
4564 ret = add_cache_extent(seen, bytenr, size);
4567 add_cache_extent(pending, bytenr, size);
4571 static int pick_next_pending(struct cache_tree *pending,
4572 struct cache_tree *reada,
4573 struct cache_tree *nodes,
4574 u64 last, struct block_info *bits, int bits_nr,
4577 unsigned long node_start = last;
4578 struct cache_extent *cache;
4581 cache = search_cache_extent(reada, 0);
4583 bits[0].start = cache->start;
4584 bits[0].size = cache->size;
4589 if (node_start > 32768)
4590 node_start -= 32768;
4592 cache = search_cache_extent(nodes, node_start);
4594 cache = search_cache_extent(nodes, 0);
4597 cache = search_cache_extent(pending, 0);
4602 bits[ret].start = cache->start;
4603 bits[ret].size = cache->size;
4604 cache = next_cache_extent(cache);
4606 } while (cache && ret < bits_nr);
4612 bits[ret].start = cache->start;
4613 bits[ret].size = cache->size;
4614 cache = next_cache_extent(cache);
4616 } while (cache && ret < bits_nr);
4618 if (bits_nr - ret > 8) {
4619 u64 lookup = bits[0].start + bits[0].size;
4620 struct cache_extent *next;
4622 next = search_cache_extent(pending, lookup);
4624 if (next->start - lookup > 32768)
4626 bits[ret].start = next->start;
4627 bits[ret].size = next->size;
4628 lookup = next->start + next->size;
4632 next = next_cache_extent(next);
4640 static void free_chunk_record(struct cache_extent *cache)
4642 struct chunk_record *rec;
4644 rec = container_of(cache, struct chunk_record, cache);
4645 list_del_init(&rec->list);
4646 list_del_init(&rec->dextents);
4650 void free_chunk_cache_tree(struct cache_tree *chunk_cache)
4652 cache_tree_free_extents(chunk_cache, free_chunk_record);
4655 static void free_device_record(struct rb_node *node)
4657 struct device_record *rec;
4659 rec = container_of(node, struct device_record, node);
4663 FREE_RB_BASED_TREE(device_cache, free_device_record);
4665 int insert_block_group_record(struct block_group_tree *tree,
4666 struct block_group_record *bg_rec)
4670 ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
4674 list_add_tail(&bg_rec->list, &tree->block_groups);
4678 static void free_block_group_record(struct cache_extent *cache)
4680 struct block_group_record *rec;
4682 rec = container_of(cache, struct block_group_record, cache);
4683 list_del_init(&rec->list);
4687 void free_block_group_tree(struct block_group_tree *tree)
4689 cache_tree_free_extents(&tree->tree, free_block_group_record);
4692 int insert_device_extent_record(struct device_extent_tree *tree,
4693 struct device_extent_record *de_rec)
4698 * Device extent is a bit different from the other extents, because
4699 * the extents which belong to the different devices may have the
4700 * same start and size, so we need use the special extent cache
4701 * search/insert functions.
4703 ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
4707 list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
4708 list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
4712 static void free_device_extent_record(struct cache_extent *cache)
4714 struct device_extent_record *rec;
4716 rec = container_of(cache, struct device_extent_record, cache);
4717 if (!list_empty(&rec->chunk_list))
4718 list_del_init(&rec->chunk_list);
4719 if (!list_empty(&rec->device_list))
4720 list_del_init(&rec->device_list);
4724 void free_device_extent_tree(struct device_extent_tree *tree)
4726 cache_tree_free_extents(&tree->tree, free_device_extent_record);
4729 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4730 static int process_extent_ref_v0(struct cache_tree *extent_cache,
4731 struct extent_buffer *leaf, int slot)
4733 struct btrfs_extent_ref_v0 *ref0;
4734 struct btrfs_key key;
4737 btrfs_item_key_to_cpu(leaf, &key, slot);
4738 ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
4739 if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
4740 ret = add_tree_backref(extent_cache, key.objectid, key.offset,
4743 ret = add_data_backref(extent_cache, key.objectid, key.offset,
4744 0, 0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
4750 struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
4751 struct btrfs_key *key,
4754 struct btrfs_chunk *ptr;
4755 struct chunk_record *rec;
4758 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
4759 num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
4761 rec = calloc(1, btrfs_chunk_record_size(num_stripes));
4763 fprintf(stderr, "memory allocation failed\n");
4767 INIT_LIST_HEAD(&rec->list);
4768 INIT_LIST_HEAD(&rec->dextents);
4771 rec->cache.start = key->offset;
4772 rec->cache.size = btrfs_chunk_length(leaf, ptr);
4774 rec->generation = btrfs_header_generation(leaf);
4776 rec->objectid = key->objectid;
4777 rec->type = key->type;
4778 rec->offset = key->offset;
4780 rec->length = rec->cache.size;
4781 rec->owner = btrfs_chunk_owner(leaf, ptr);
4782 rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
4783 rec->type_flags = btrfs_chunk_type(leaf, ptr);
4784 rec->io_width = btrfs_chunk_io_width(leaf, ptr);
4785 rec->io_align = btrfs_chunk_io_align(leaf, ptr);
4786 rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
4787 rec->num_stripes = num_stripes;
4788 rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
4790 for (i = 0; i < rec->num_stripes; ++i) {
4791 rec->stripes[i].devid =
4792 btrfs_stripe_devid_nr(leaf, ptr, i);
4793 rec->stripes[i].offset =
4794 btrfs_stripe_offset_nr(leaf, ptr, i);
4795 read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
4796 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
4803 static int process_chunk_item(struct cache_tree *chunk_cache,
4804 struct btrfs_key *key, struct extent_buffer *eb,
4807 struct chunk_record *rec;
4808 struct btrfs_chunk *chunk;
4811 chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
4813 * Do extra check for this chunk item,
4815 * It's still possible one can craft a leaf with CHUNK_ITEM, with
4816 * wrong onwer(3) out of chunk tree, to pass both chunk tree check
4817 * and owner<->key_type check.
4819 ret = btrfs_check_chunk_valid(global_info, eb, chunk, slot,
4822 error("chunk(%llu, %llu) is not valid, ignore it",
4823 key->offset, btrfs_chunk_length(eb, chunk));
4826 rec = btrfs_new_chunk_record(eb, key, slot);
4827 ret = insert_cache_extent(chunk_cache, &rec->cache);
4829 fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
4830 rec->offset, rec->length);
4837 static int process_device_item(struct rb_root *dev_cache,
4838 struct btrfs_key *key, struct extent_buffer *eb, int slot)
4840 struct btrfs_dev_item *ptr;
4841 struct device_record *rec;
4844 ptr = btrfs_item_ptr(eb,
4845 slot, struct btrfs_dev_item);
4847 rec = malloc(sizeof(*rec));
4849 fprintf(stderr, "memory allocation failed\n");
4853 rec->devid = key->offset;
4854 rec->generation = btrfs_header_generation(eb);
4856 rec->objectid = key->objectid;
4857 rec->type = key->type;
4858 rec->offset = key->offset;
4860 rec->devid = btrfs_device_id(eb, ptr);
4861 rec->total_byte = btrfs_device_total_bytes(eb, ptr);
4862 rec->byte_used = btrfs_device_bytes_used(eb, ptr);
4864 ret = rb_insert(dev_cache, &rec->node, device_record_compare);
4866 fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
4873 struct block_group_record *
4874 btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,
4877 struct btrfs_block_group_item *ptr;
4878 struct block_group_record *rec;
4880 rec = calloc(1, sizeof(*rec));
4882 fprintf(stderr, "memory allocation failed\n");
4886 rec->cache.start = key->objectid;
4887 rec->cache.size = key->offset;
4889 rec->generation = btrfs_header_generation(leaf);
4891 rec->objectid = key->objectid;
4892 rec->type = key->type;
4893 rec->offset = key->offset;
4895 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_block_group_item);
4896 rec->flags = btrfs_disk_block_group_flags(leaf, ptr);
4898 INIT_LIST_HEAD(&rec->list);
4903 static int process_block_group_item(struct block_group_tree *block_group_cache,
4904 struct btrfs_key *key,
4905 struct extent_buffer *eb, int slot)
4907 struct block_group_record *rec;
4910 rec = btrfs_new_block_group_record(eb, key, slot);
4911 ret = insert_block_group_record(block_group_cache, rec);
4913 fprintf(stderr, "Block Group[%llu, %llu] existed.\n",
4914 rec->objectid, rec->offset);
4921 struct device_extent_record *
4922 btrfs_new_device_extent_record(struct extent_buffer *leaf,
4923 struct btrfs_key *key, int slot)
4925 struct device_extent_record *rec;
4926 struct btrfs_dev_extent *ptr;
4928 rec = calloc(1, sizeof(*rec));
4930 fprintf(stderr, "memory allocation failed\n");
4934 rec->cache.objectid = key->objectid;
4935 rec->cache.start = key->offset;
4937 rec->generation = btrfs_header_generation(leaf);
4939 rec->objectid = key->objectid;
4940 rec->type = key->type;
4941 rec->offset = key->offset;
4943 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
4944 rec->chunk_objecteid =
4945 btrfs_dev_extent_chunk_objectid(leaf, ptr);
4947 btrfs_dev_extent_chunk_offset(leaf, ptr);
4948 rec->length = btrfs_dev_extent_length(leaf, ptr);
4949 rec->cache.size = rec->length;
4951 INIT_LIST_HEAD(&rec->chunk_list);
4952 INIT_LIST_HEAD(&rec->device_list);
4958 process_device_extent_item(struct device_extent_tree *dev_extent_cache,
4959 struct btrfs_key *key, struct extent_buffer *eb,
4962 struct device_extent_record *rec;
4965 rec = btrfs_new_device_extent_record(eb, key, slot);
4966 ret = insert_device_extent_record(dev_extent_cache, rec);
4969 "Device extent[%llu, %llu, %llu] existed.\n",
4970 rec->objectid, rec->offset, rec->length);
4977 static int process_extent_item(struct btrfs_root *root,
4978 struct cache_tree *extent_cache,
4979 struct extent_buffer *eb, int slot)
4981 struct btrfs_extent_item *ei;
4982 struct btrfs_extent_inline_ref *iref;
4983 struct btrfs_extent_data_ref *dref;
4984 struct btrfs_shared_data_ref *sref;
4985 struct btrfs_key key;
4986 struct extent_record tmpl;
4991 u32 item_size = btrfs_item_size_nr(eb, slot);
4997 btrfs_item_key_to_cpu(eb, &key, slot);
4999 if (key.type == BTRFS_METADATA_ITEM_KEY) {
5001 num_bytes = root->fs_info->nodesize;
5003 num_bytes = key.offset;
5006 if (!IS_ALIGNED(key.objectid, root->fs_info->sectorsize)) {
5007 error("ignoring invalid extent, bytenr %llu is not aligned to %u",
5008 key.objectid, root->fs_info->sectorsize);
5011 if (item_size < sizeof(*ei)) {
5012 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5013 struct btrfs_extent_item_v0 *ei0;
5015 if (item_size != sizeof(*ei0)) {
5017 "invalid extent item format: ITEM[%llu %u %llu] leaf: %llu slot: %d",
5018 key.objectid, key.type, key.offset,
5019 btrfs_header_bytenr(eb), slot);
5022 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
5023 refs = btrfs_extent_refs_v0(eb, ei0);
5027 memset(&tmpl, 0, sizeof(tmpl));
5028 tmpl.start = key.objectid;
5029 tmpl.nr = num_bytes;
5030 tmpl.extent_item_refs = refs;
5031 tmpl.metadata = metadata;
5033 tmpl.max_size = num_bytes;
5035 return add_extent_rec(extent_cache, &tmpl);
5038 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
5039 refs = btrfs_extent_refs(eb, ei);
5040 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
5044 if (metadata && num_bytes != root->fs_info->nodesize) {
5045 error("ignore invalid metadata extent, length %llu does not equal to %u",
5046 num_bytes, root->fs_info->nodesize);
5049 if (!metadata && !IS_ALIGNED(num_bytes, root->fs_info->sectorsize)) {
5050 error("ignore invalid data extent, length %llu is not aligned to %u",
5051 num_bytes, root->fs_info->sectorsize);
5055 memset(&tmpl, 0, sizeof(tmpl));
5056 tmpl.start = key.objectid;
5057 tmpl.nr = num_bytes;
5058 tmpl.extent_item_refs = refs;
5059 tmpl.metadata = metadata;
5061 tmpl.max_size = num_bytes;
5062 add_extent_rec(extent_cache, &tmpl);
5064 ptr = (unsigned long)(ei + 1);
5065 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
5066 key.type == BTRFS_EXTENT_ITEM_KEY)
5067 ptr += sizeof(struct btrfs_tree_block_info);
5069 end = (unsigned long)ei + item_size;
5071 iref = (struct btrfs_extent_inline_ref *)ptr;
5072 type = btrfs_extent_inline_ref_type(eb, iref);
5073 offset = btrfs_extent_inline_ref_offset(eb, iref);
5075 case BTRFS_TREE_BLOCK_REF_KEY:
5076 ret = add_tree_backref(extent_cache, key.objectid,
5080 "add_tree_backref failed (extent items tree block): %s",
5083 case BTRFS_SHARED_BLOCK_REF_KEY:
5084 ret = add_tree_backref(extent_cache, key.objectid,
5088 "add_tree_backref failed (extent items shared block): %s",
5091 case BTRFS_EXTENT_DATA_REF_KEY:
5092 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
5093 add_data_backref(extent_cache, key.objectid, 0,
5094 btrfs_extent_data_ref_root(eb, dref),
5095 btrfs_extent_data_ref_objectid(eb,
5097 btrfs_extent_data_ref_offset(eb, dref),
5098 btrfs_extent_data_ref_count(eb, dref),
5101 case BTRFS_SHARED_DATA_REF_KEY:
5102 sref = (struct btrfs_shared_data_ref *)(iref + 1);
5103 add_data_backref(extent_cache, key.objectid, offset,
5105 btrfs_shared_data_ref_count(eb, sref),
5110 "corrupt extent record: key [%llu,%u,%llu]\n",
5111 key.objectid, key.type, num_bytes);
5114 ptr += btrfs_extent_inline_ref_size(type);
5121 static int check_cache_range(struct btrfs_root *root,
5122 struct btrfs_block_group_cache *cache,
5123 u64 offset, u64 bytes)
5125 struct btrfs_free_space *entry;
5131 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
5132 bytenr = btrfs_sb_offset(i);
5133 ret = btrfs_rmap_block(root->fs_info,
5134 cache->key.objectid, bytenr, 0,
5135 &logical, &nr, &stripe_len);
5140 if (logical[nr] + stripe_len <= offset)
5142 if (offset + bytes <= logical[nr])
5144 if (logical[nr] == offset) {
5145 if (stripe_len >= bytes) {
5149 bytes -= stripe_len;
5150 offset += stripe_len;
5151 } else if (logical[nr] < offset) {
5152 if (logical[nr] + stripe_len >=
5157 bytes = (offset + bytes) -
5158 (logical[nr] + stripe_len);
5159 offset = logical[nr] + stripe_len;
5162 * Could be tricky, the super may land in the
5163 * middle of the area we're checking. First
5164 * check the easiest case, it's at the end.
5166 if (logical[nr] + stripe_len >=
5168 bytes = logical[nr] - offset;
5172 /* Check the left side */
5173 ret = check_cache_range(root, cache,
5175 logical[nr] - offset);
5181 /* Now we continue with the right side */
5182 bytes = (offset + bytes) -
5183 (logical[nr] + stripe_len);
5184 offset = logical[nr] + stripe_len;
5191 entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes);
5193 fprintf(stderr, "there is no free space entry for %llu-%llu\n",
5194 offset, offset+bytes);
5198 if (entry->offset != offset) {
5199 fprintf(stderr, "wanted offset %llu, found %llu\n", offset,
5204 if (entry->bytes != bytes) {
5205 fprintf(stderr, "wanted bytes %llu, found %llu for off %llu\n",
5206 bytes, entry->bytes, offset);
5210 unlink_free_space(cache->free_space_ctl, entry);
5215 static int verify_space_cache(struct btrfs_root *root,
5216 struct btrfs_block_group_cache *cache)
5218 struct btrfs_path path;
5219 struct extent_buffer *leaf;
5220 struct btrfs_key key;
5224 root = root->fs_info->extent_root;
5226 last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
5228 btrfs_init_path(&path);
5229 key.objectid = last;
5231 key.type = BTRFS_EXTENT_ITEM_KEY;
5232 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
5237 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5238 ret = btrfs_next_leaf(root, &path);
5246 leaf = path.nodes[0];
5247 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5248 if (key.objectid >= cache->key.offset + cache->key.objectid)
5250 if (key.type != BTRFS_EXTENT_ITEM_KEY &&
5251 key.type != BTRFS_METADATA_ITEM_KEY) {
5256 if (last == key.objectid) {
5257 if (key.type == BTRFS_EXTENT_ITEM_KEY)
5258 last = key.objectid + key.offset;
5260 last = key.objectid + root->fs_info->nodesize;
5265 ret = check_cache_range(root, cache, last,
5266 key.objectid - last);
5269 if (key.type == BTRFS_EXTENT_ITEM_KEY)
5270 last = key.objectid + key.offset;
5272 last = key.objectid + root->fs_info->nodesize;
5276 if (last < cache->key.objectid + cache->key.offset)
5277 ret = check_cache_range(root, cache, last,
5278 cache->key.objectid +
5279 cache->key.offset - last);
5282 btrfs_release_path(&path);
5285 !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) {
5286 fprintf(stderr, "There are still entries left in the space "
5294 static int check_space_cache(struct btrfs_root *root)
5296 struct btrfs_block_group_cache *cache;
5297 u64 start = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
5301 if (btrfs_super_cache_generation(root->fs_info->super_copy) != -1ULL &&
5302 btrfs_super_generation(root->fs_info->super_copy) !=
5303 btrfs_super_cache_generation(root->fs_info->super_copy)) {
5304 printf("cache and super generation don't match, space cache "
5305 "will be invalidated\n");
5309 if (ctx.progress_enabled) {
5310 ctx.tp = TASK_FREE_SPACE;
5311 task_start(ctx.info);
5315 cache = btrfs_lookup_first_block_group(root->fs_info, start);
5319 start = cache->key.objectid + cache->key.offset;
5320 if (!cache->free_space_ctl) {
5321 if (btrfs_init_free_space_ctl(cache,
5322 root->fs_info->sectorsize)) {
5327 btrfs_remove_free_space_cache(cache);
5330 if (btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE)) {
5331 ret = exclude_super_stripes(root, cache);
5333 fprintf(stderr, "could not exclude super stripes: %s\n",
5338 ret = load_free_space_tree(root->fs_info, cache);
5339 free_excluded_extents(root, cache);
5341 fprintf(stderr, "could not load free space tree: %s\n",
5348 ret = load_free_space_cache(root->fs_info, cache);
5355 ret = verify_space_cache(root, cache);
5357 fprintf(stderr, "cache appears valid but isn't %llu\n",
5358 cache->key.objectid);
5363 task_stop(ctx.info);
5365 return error ? -EINVAL : 0;
5368 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
5369 u64 num_bytes, unsigned long leaf_offset,
5370 struct extent_buffer *eb)
5372 struct btrfs_fs_info *fs_info = root->fs_info;
5374 u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
5376 unsigned long csum_offset;
5380 u64 data_checked = 0;
5386 if (num_bytes % fs_info->sectorsize)
5389 data = malloc(num_bytes);
5393 while (offset < num_bytes) {
5396 read_len = num_bytes - offset;
5397 /* read as much space once a time */
5398 ret = read_extent_data(fs_info, data + offset,
5399 bytenr + offset, &read_len, mirror);
5403 /* verify every 4k data's checksum */
5404 while (data_checked < read_len) {
5406 tmp = offset + data_checked;
5408 csum = btrfs_csum_data((char *)data + tmp,
5409 csum, fs_info->sectorsize);
5410 btrfs_csum_final(csum, (u8 *)&csum);
5412 csum_offset = leaf_offset +
5413 tmp / fs_info->sectorsize * csum_size;
5414 read_extent_buffer(eb, (char *)&csum_expected,
5415 csum_offset, csum_size);
5416 /* try another mirror */
5417 if (csum != csum_expected) {
5418 fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
5419 mirror, bytenr + tmp,
5420 csum, csum_expected);
5421 num_copies = btrfs_num_copies(root->fs_info,
5423 if (mirror < num_copies - 1) {
5428 data_checked += fs_info->sectorsize;
5437 static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
5440 struct btrfs_path path;
5441 struct extent_buffer *leaf;
5442 struct btrfs_key key;
5445 btrfs_init_path(&path);
5446 key.objectid = bytenr;
5447 key.type = BTRFS_EXTENT_ITEM_KEY;
5448 key.offset = (u64)-1;
5451 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
5454 fprintf(stderr, "Error looking up extent record %d\n", ret);
5455 btrfs_release_path(&path);
5458 if (path.slots[0] > 0) {
5461 ret = btrfs_prev_leaf(root, &path);
5464 } else if (ret > 0) {
5471 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5474 * Block group items come before extent items if they have the same
5475 * bytenr, so walk back one more just in case. Dear future traveller,
5476 * first congrats on mastering time travel. Now if it's not too much
5477 * trouble could you go back to 2006 and tell Chris to make the
5478 * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
5479 * EXTENT_ITEM_KEY please?
5481 while (key.type > BTRFS_EXTENT_ITEM_KEY) {
5482 if (path.slots[0] > 0) {
5485 ret = btrfs_prev_leaf(root, &path);
5488 } else if (ret > 0) {
5493 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5497 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5498 ret = btrfs_next_leaf(root, &path);
5500 fprintf(stderr, "Error going to next leaf "
5502 btrfs_release_path(&path);
5508 leaf = path.nodes[0];
5509 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5510 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
5514 if (key.objectid + key.offset < bytenr) {
5518 if (key.objectid > bytenr + num_bytes)
5521 if (key.objectid == bytenr) {
5522 if (key.offset >= num_bytes) {
5526 num_bytes -= key.offset;
5527 bytenr += key.offset;
5528 } else if (key.objectid < bytenr) {
5529 if (key.objectid + key.offset >= bytenr + num_bytes) {
5533 num_bytes = (bytenr + num_bytes) -
5534 (key.objectid + key.offset);
5535 bytenr = key.objectid + key.offset;
5537 if (key.objectid + key.offset < bytenr + num_bytes) {
5538 u64 new_start = key.objectid + key.offset;
5539 u64 new_bytes = bytenr + num_bytes - new_start;
5542 * Weird case, the extent is in the middle of
5543 * our range, we'll have to search one side
5544 * and then the other. Not sure if this happens
5545 * in real life, but no harm in coding it up
5546 * anyway just in case.
5548 btrfs_release_path(&path);
5549 ret = check_extent_exists(root, new_start,
5552 fprintf(stderr, "Right section didn't "
5556 num_bytes = key.objectid - bytenr;
5559 num_bytes = key.objectid - bytenr;
5566 if (num_bytes && !ret) {
5568 "there are no extents for csum range %llu-%llu\n",
5569 bytenr, bytenr+num_bytes);
5573 btrfs_release_path(&path);
5577 static int check_csums(struct btrfs_root *root)
5579 struct btrfs_path path;
5580 struct extent_buffer *leaf;
5581 struct btrfs_key key;
5582 u64 offset = 0, num_bytes = 0;
5583 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
5587 unsigned long leaf_offset;
5589 root = root->fs_info->csum_root;
5590 if (!extent_buffer_uptodate(root->node)) {
5591 fprintf(stderr, "No valid csum tree found\n");
5595 btrfs_init_path(&path);
5596 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
5597 key.type = BTRFS_EXTENT_CSUM_KEY;
5599 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
5601 fprintf(stderr, "Error searching csum tree %d\n", ret);
5602 btrfs_release_path(&path);
5606 if (ret > 0 && path.slots[0])
5611 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
5612 ret = btrfs_next_leaf(root, &path);
5614 fprintf(stderr, "Error going to next leaf "
5621 leaf = path.nodes[0];
5623 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
5624 if (key.type != BTRFS_EXTENT_CSUM_KEY) {
5629 data_len = (btrfs_item_size_nr(leaf, path.slots[0]) /
5630 csum_size) * root->fs_info->sectorsize;
5631 if (!check_data_csum)
5632 goto skip_csum_check;
5633 leaf_offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
5634 ret = check_extent_csums(root, key.offset, data_len,
5640 offset = key.offset;
5641 } else if (key.offset != offset + num_bytes) {
5642 ret = check_extent_exists(root, offset, num_bytes);
5645 "csum exists for %llu-%llu but there is no extent record\n",
5646 offset, offset+num_bytes);
5649 offset = key.offset;
5652 num_bytes += data_len;
5656 btrfs_release_path(&path);
5660 static int is_dropped_key(struct btrfs_key *key,
5661 struct btrfs_key *drop_key)
5663 if (key->objectid < drop_key->objectid)
5665 else if (key->objectid == drop_key->objectid) {
5666 if (key->type < drop_key->type)
5668 else if (key->type == drop_key->type) {
5669 if (key->offset < drop_key->offset)
5677 * Here are the rules for FULL_BACKREF.
5679 * 1) If BTRFS_HEADER_FLAG_RELOC is set then we have FULL_BACKREF set.
5680 * 2) If btrfs_header_owner(buf) no longer points to buf then we have
5682 * 3) We cowed the block walking down a reloc tree. This is impossible to tell
5683 * if it happened after the relocation occurred since we'll have dropped the
5684 * reloc root, so it's entirely possible to have FULL_BACKREF set on buf and
5685 * have no real way to know for sure.
5687 * We process the blocks one root at a time, and we start from the lowest root
5688 * objectid and go to the highest. So we can just lookup the owner backref for
5689 * the record and if we don't find it then we know it doesn't exist and we have
5692 * FIXME: if we ever start reclaiming root objectid's then we need to fix this
5693 * assumption and simply indicate that we _think_ that the FULL BACKREF needs to
5694 * be set or not and then we can check later once we've gathered all the refs.
5696 static int calc_extent_flag(struct cache_tree *extent_cache,
5697 struct extent_buffer *buf,
5698 struct root_item_record *ri,
5701 struct extent_record *rec;
5702 struct cache_extent *cache;
5703 struct tree_backref *tback;
5706 cache = lookup_cache_extent(extent_cache, buf->start, 1);
5707 /* we have added this extent before */
5711 rec = container_of(cache, struct extent_record, cache);
5714 * Except file/reloc tree, we can not have
5717 if (ri->objectid < BTRFS_FIRST_FREE_OBJECTID)
5722 if (buf->start == ri->bytenr)
5725 if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
5728 owner = btrfs_header_owner(buf);
5729 if (owner == ri->objectid)
5732 tback = find_tree_backref(rec, 0, owner);
5737 if (rec->flag_block_full_backref != FLAG_UNSET &&
5738 rec->flag_block_full_backref != 0)
5739 rec->bad_full_backref = 1;
5742 *flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5743 if (rec->flag_block_full_backref != FLAG_UNSET &&
5744 rec->flag_block_full_backref != 1)
5745 rec->bad_full_backref = 1;
5749 static void report_mismatch_key_root(u8 key_type, u64 rootid)
5751 fprintf(stderr, "Invalid key type(");
5752 print_key_type(stderr, 0, key_type);
5753 fprintf(stderr, ") found in root(");
5754 print_objectid(stderr, rootid, 0);
5755 fprintf(stderr, ")\n");
5759 * Check if the key is valid with its extent buffer.
5761 * This is a early check in case invalid key exists in a extent buffer
5762 * This is not comprehensive yet, but should prevent wrong key/item passed
5765 static int check_type_with_root(u64 rootid, u8 key_type)
5768 /* Only valid in chunk tree */
5769 case BTRFS_DEV_ITEM_KEY:
5770 case BTRFS_CHUNK_ITEM_KEY:
5771 if (rootid != BTRFS_CHUNK_TREE_OBJECTID)
5774 /* valid in csum and log tree */
5775 case BTRFS_CSUM_TREE_OBJECTID:
5776 if (!(rootid == BTRFS_TREE_LOG_OBJECTID ||
5780 case BTRFS_EXTENT_ITEM_KEY:
5781 case BTRFS_METADATA_ITEM_KEY:
5782 case BTRFS_BLOCK_GROUP_ITEM_KEY:
5783 if (rootid != BTRFS_EXTENT_TREE_OBJECTID)
5786 case BTRFS_ROOT_ITEM_KEY:
5787 if (rootid != BTRFS_ROOT_TREE_OBJECTID)
5790 case BTRFS_DEV_EXTENT_KEY:
5791 if (rootid != BTRFS_DEV_TREE_OBJECTID)
5797 report_mismatch_key_root(key_type, rootid);
5801 static int run_next_block(struct btrfs_root *root,
5802 struct block_info *bits,
5805 struct cache_tree *pending,
5806 struct cache_tree *seen,
5807 struct cache_tree *reada,
5808 struct cache_tree *nodes,
5809 struct cache_tree *extent_cache,
5810 struct cache_tree *chunk_cache,
5811 struct rb_root *dev_cache,
5812 struct block_group_tree *block_group_cache,
5813 struct device_extent_tree *dev_extent_cache,
5814 struct root_item_record *ri)
5816 struct btrfs_fs_info *fs_info = root->fs_info;
5817 struct extent_buffer *buf;
5818 struct extent_record *rec = NULL;
5829 struct btrfs_key key;
5830 struct cache_extent *cache;
5833 nritems = pick_next_pending(pending, reada, nodes, *last, bits,
5834 bits_nr, &reada_bits);
5839 for (i = 0; i < nritems; i++) {
5840 ret = add_cache_extent(reada, bits[i].start,
5845 /* fixme, get the parent transid */
5846 readahead_tree_block(fs_info, bits[i].start, 0);
5849 *last = bits[0].start;
5850 bytenr = bits[0].start;
5851 size = bits[0].size;
5853 cache = lookup_cache_extent(pending, bytenr, size);
5855 remove_cache_extent(pending, cache);
5858 cache = lookup_cache_extent(reada, bytenr, size);
5860 remove_cache_extent(reada, cache);
5863 cache = lookup_cache_extent(nodes, bytenr, size);
5865 remove_cache_extent(nodes, cache);
5868 cache = lookup_cache_extent(extent_cache, bytenr, size);
5870 rec = container_of(cache, struct extent_record, cache);
5871 gen = rec->parent_generation;
5874 /* fixme, get the real parent transid */
5875 buf = read_tree_block(root->fs_info, bytenr, gen);
5876 if (!extent_buffer_uptodate(buf)) {
5877 record_bad_block_io(root->fs_info,
5878 extent_cache, bytenr, size);
5882 nritems = btrfs_header_nritems(buf);
5885 if (!init_extent_tree) {
5886 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
5887 btrfs_header_level(buf), 1, NULL,
5890 ret = calc_extent_flag(extent_cache, buf, ri, &flags);
5892 fprintf(stderr, "Couldn't calc extent flags\n");
5893 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5898 ret = calc_extent_flag(extent_cache, buf, ri, &flags);
5900 fprintf(stderr, "Couldn't calc extent flags\n");
5901 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5905 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5907 ri->objectid != BTRFS_TREE_RELOC_OBJECTID &&
5908 ri->objectid == btrfs_header_owner(buf)) {
5910 * Ok we got to this block from it's original owner and
5911 * we have FULL_BACKREF set. Relocation can leave
5912 * converted blocks over so this is altogether possible,
5913 * however it's not possible if the generation > the
5914 * last snapshot, so check for this case.
5916 if (!btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC) &&
5917 btrfs_header_generation(buf) > ri->last_snapshot) {
5918 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
5919 rec->bad_full_backref = 1;
5924 (ri->objectid == BTRFS_TREE_RELOC_OBJECTID ||
5925 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) {
5926 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5927 rec->bad_full_backref = 1;
5931 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5932 rec->flag_block_full_backref = 1;
5936 rec->flag_block_full_backref = 0;
5938 owner = btrfs_header_owner(buf);
5941 ret = check_block(root, extent_cache, buf, flags);
5945 if (btrfs_is_leaf(buf)) {
5946 btree_space_waste += btrfs_leaf_free_space(root, buf);
5947 for (i = 0; i < nritems; i++) {
5948 struct btrfs_file_extent_item *fi;
5950 btrfs_item_key_to_cpu(buf, &key, i);
5952 * Check key type against the leaf owner.
5953 * Could filter quite a lot of early error if
5956 if (check_type_with_root(btrfs_header_owner(buf),
5958 fprintf(stderr, "ignoring invalid key\n");
5961 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
5962 process_extent_item(root, extent_cache, buf,
5966 if (key.type == BTRFS_METADATA_ITEM_KEY) {
5967 process_extent_item(root, extent_cache, buf,
5971 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
5973 btrfs_item_size_nr(buf, i);
5976 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
5977 process_chunk_item(chunk_cache, &key, buf, i);
5980 if (key.type == BTRFS_DEV_ITEM_KEY) {
5981 process_device_item(dev_cache, &key, buf, i);
5984 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
5985 process_block_group_item(block_group_cache,
5989 if (key.type == BTRFS_DEV_EXTENT_KEY) {
5990 process_device_extent_item(dev_extent_cache,
5995 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
5996 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5997 process_extent_ref_v0(extent_cache, buf, i);
6004 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
6005 ret = add_tree_backref(extent_cache,
6006 key.objectid, 0, key.offset, 0);
6009 "add_tree_backref failed (leaf tree block): %s",
6013 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
6014 ret = add_tree_backref(extent_cache,
6015 key.objectid, key.offset, 0, 0);
6018 "add_tree_backref failed (leaf shared block): %s",
6022 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
6023 struct btrfs_extent_data_ref *ref;
6025 ref = btrfs_item_ptr(buf, i,
6026 struct btrfs_extent_data_ref);
6027 add_data_backref(extent_cache,
6029 btrfs_extent_data_ref_root(buf, ref),
6030 btrfs_extent_data_ref_objectid(buf,
6032 btrfs_extent_data_ref_offset(buf, ref),
6033 btrfs_extent_data_ref_count(buf, ref),
6034 0, root->fs_info->sectorsize);
6037 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
6038 struct btrfs_shared_data_ref *ref;
6040 ref = btrfs_item_ptr(buf, i,
6041 struct btrfs_shared_data_ref);
6042 add_data_backref(extent_cache,
6043 key.objectid, key.offset, 0, 0, 0,
6044 btrfs_shared_data_ref_count(buf, ref),
6045 0, root->fs_info->sectorsize);
6048 if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
6049 struct bad_item *bad;
6051 if (key.objectid == BTRFS_ORPHAN_OBJECTID)
6055 bad = malloc(sizeof(struct bad_item));
6058 INIT_LIST_HEAD(&bad->list);
6059 memcpy(&bad->key, &key,
6060 sizeof(struct btrfs_key));
6061 bad->root_id = owner;
6062 list_add_tail(&bad->list, &delete_items);
6065 if (key.type != BTRFS_EXTENT_DATA_KEY)
6067 fi = btrfs_item_ptr(buf, i,
6068 struct btrfs_file_extent_item);
6069 if (btrfs_file_extent_type(buf, fi) ==
6070 BTRFS_FILE_EXTENT_INLINE)
6072 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
6075 data_bytes_allocated +=
6076 btrfs_file_extent_disk_num_bytes(buf, fi);
6077 if (data_bytes_allocated < root->fs_info->sectorsize)
6080 data_bytes_referenced +=
6081 btrfs_file_extent_num_bytes(buf, fi);
6082 add_data_backref(extent_cache,
6083 btrfs_file_extent_disk_bytenr(buf, fi),
6084 parent, owner, key.objectid, key.offset -
6085 btrfs_file_extent_offset(buf, fi), 1, 1,
6086 btrfs_file_extent_disk_num_bytes(buf, fi));
6090 struct btrfs_key first_key;
6092 first_key.objectid = 0;
6095 btrfs_item_key_to_cpu(buf, &first_key, 0);
6096 level = btrfs_header_level(buf);
6097 for (i = 0; i < nritems; i++) {
6098 struct extent_record tmpl;
6100 ptr = btrfs_node_blockptr(buf, i);
6101 size = root->fs_info->nodesize;
6102 btrfs_node_key_to_cpu(buf, &key, i);
6104 if ((level == ri->drop_level)
6105 && is_dropped_key(&key, &ri->drop_key)) {
6110 memset(&tmpl, 0, sizeof(tmpl));
6111 btrfs_cpu_key_to_disk(&tmpl.parent_key, &key);
6112 tmpl.parent_generation =
6113 btrfs_node_ptr_generation(buf, i);
6118 tmpl.max_size = size;
6119 ret = add_extent_rec(extent_cache, &tmpl);
6123 ret = add_tree_backref(extent_cache, ptr, parent,
6127 "add_tree_backref failed (non-leaf block): %s",
6133 add_pending(nodes, seen, ptr, size);
6135 add_pending(pending, seen, ptr, size);
6137 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(fs_info) -
6138 nritems) * sizeof(struct btrfs_key_ptr);
6140 total_btree_bytes += buf->len;
6141 if (fs_root_objectid(btrfs_header_owner(buf)))
6142 total_fs_tree_bytes += buf->len;
6143 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
6144 total_extent_tree_bytes += buf->len;
6146 free_extent_buffer(buf);
6150 static int add_root_to_pending(struct extent_buffer *buf,
6151 struct cache_tree *extent_cache,
6152 struct cache_tree *pending,
6153 struct cache_tree *seen,
6154 struct cache_tree *nodes,
6157 struct extent_record tmpl;
6160 if (btrfs_header_level(buf) > 0)
6161 add_pending(nodes, seen, buf->start, buf->len);
6163 add_pending(pending, seen, buf->start, buf->len);
6165 memset(&tmpl, 0, sizeof(tmpl));
6166 tmpl.start = buf->start;
6171 tmpl.max_size = buf->len;
6172 add_extent_rec(extent_cache, &tmpl);
6174 if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
6175 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
6176 ret = add_tree_backref(extent_cache, buf->start, buf->start,
6179 ret = add_tree_backref(extent_cache, buf->start, 0, objectid,
6184 /* as we fix the tree, we might be deleting blocks that
6185 * we're tracking for repair. This hook makes sure we
6186 * remove any backrefs for blocks as we are fixing them.
6188 static int free_extent_hook(struct btrfs_trans_handle *trans,
6189 struct btrfs_root *root,
6190 u64 bytenr, u64 num_bytes, u64 parent,
6191 u64 root_objectid, u64 owner, u64 offset,
6194 struct extent_record *rec;
6195 struct cache_extent *cache;
6197 struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
6199 is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
6200 cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
6204 rec = container_of(cache, struct extent_record, cache);
6206 struct data_backref *back;
6208 back = find_data_backref(rec, parent, root_objectid, owner,
6209 offset, 1, bytenr, num_bytes);
6212 if (back->node.found_ref) {
6213 back->found_ref -= refs_to_drop;
6215 rec->refs -= refs_to_drop;
6217 if (back->node.found_extent_tree) {
6218 back->num_refs -= refs_to_drop;
6219 if (rec->extent_item_refs)
6220 rec->extent_item_refs -= refs_to_drop;
6222 if (back->found_ref == 0)
6223 back->node.found_ref = 0;
6224 if (back->num_refs == 0)
6225 back->node.found_extent_tree = 0;
6227 if (!back->node.found_extent_tree && back->node.found_ref) {
6228 rb_erase(&back->node.node, &rec->backref_tree);
6232 struct tree_backref *back;
6234 back = find_tree_backref(rec, parent, root_objectid);
6237 if (back->node.found_ref) {
6240 back->node.found_ref = 0;
6242 if (back->node.found_extent_tree) {
6243 if (rec->extent_item_refs)
6244 rec->extent_item_refs--;
6245 back->node.found_extent_tree = 0;
6247 if (!back->node.found_extent_tree && back->node.found_ref) {
6248 rb_erase(&back->node.node, &rec->backref_tree);
6252 maybe_free_extent_rec(extent_cache, rec);
6257 static int delete_extent_records(struct btrfs_trans_handle *trans,
6258 struct btrfs_root *root,
6259 struct btrfs_path *path,
6262 struct btrfs_key key;
6263 struct btrfs_key found_key;
6264 struct extent_buffer *leaf;
6269 key.objectid = bytenr;
6271 key.offset = (u64)-1;
6274 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
6281 if (path->slots[0] == 0)
6287 leaf = path->nodes[0];
6288 slot = path->slots[0];
6290 btrfs_item_key_to_cpu(leaf, &found_key, slot);
6291 if (found_key.objectid != bytenr)
6294 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
6295 found_key.type != BTRFS_METADATA_ITEM_KEY &&
6296 found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
6297 found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
6298 found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
6299 found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
6300 found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
6301 btrfs_release_path(path);
6302 if (found_key.type == 0) {
6303 if (found_key.offset == 0)
6305 key.offset = found_key.offset - 1;
6306 key.type = found_key.type;
6308 key.type = found_key.type - 1;
6309 key.offset = (u64)-1;
6314 "repair deleting extent record: key [%llu,%u,%llu]\n",
6315 found_key.objectid, found_key.type, found_key.offset);
6317 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
6320 btrfs_release_path(path);
6322 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
6323 found_key.type == BTRFS_METADATA_ITEM_KEY) {
6324 u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
6325 found_key.offset : root->fs_info->nodesize;
6327 ret = btrfs_update_block_group(root, bytenr,
6334 btrfs_release_path(path);
6339 * for a single backref, this will allocate a new extent
6340 * and add the backref to it.
6342 static int record_extent(struct btrfs_trans_handle *trans,
6343 struct btrfs_fs_info *info,
6344 struct btrfs_path *path,
6345 struct extent_record *rec,
6346 struct extent_backref *back,
6347 int allocated, u64 flags)
6350 struct btrfs_root *extent_root = info->extent_root;
6351 struct extent_buffer *leaf;
6352 struct btrfs_key ins_key;
6353 struct btrfs_extent_item *ei;
6354 struct data_backref *dback;
6355 struct btrfs_tree_block_info *bi;
6358 rec->max_size = max_t(u64, rec->max_size,
6362 u32 item_size = sizeof(*ei);
6365 item_size += sizeof(*bi);
6367 ins_key.objectid = rec->start;
6368 ins_key.offset = rec->max_size;
6369 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
6371 ret = btrfs_insert_empty_item(trans, extent_root, path,
6372 &ins_key, item_size);
6376 leaf = path->nodes[0];
6377 ei = btrfs_item_ptr(leaf, path->slots[0],
6378 struct btrfs_extent_item);
6380 btrfs_set_extent_refs(leaf, ei, 0);
6381 btrfs_set_extent_generation(leaf, ei, rec->generation);
6383 if (back->is_data) {
6384 btrfs_set_extent_flags(leaf, ei,
6385 BTRFS_EXTENT_FLAG_DATA);
6387 struct btrfs_disk_key copy_key;
6389 bi = (struct btrfs_tree_block_info *)(ei + 1);
6390 memset_extent_buffer(leaf, 0, (unsigned long)bi,
6393 btrfs_set_disk_key_objectid(©_key,
6394 rec->info_objectid);
6395 btrfs_set_disk_key_type(©_key, 0);
6396 btrfs_set_disk_key_offset(©_key, 0);
6398 btrfs_set_tree_block_level(leaf, bi, rec->info_level);
6399 btrfs_set_tree_block_key(leaf, bi, ©_key);
6401 btrfs_set_extent_flags(leaf, ei,
6402 flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
6405 btrfs_mark_buffer_dirty(leaf);
6406 ret = btrfs_update_block_group(extent_root, rec->start,
6407 rec->max_size, 1, 0);
6410 btrfs_release_path(path);
6413 if (back->is_data) {
6417 dback = to_data_backref(back);
6418 if (back->full_backref)
6419 parent = dback->parent;
6423 for (i = 0; i < dback->found_ref; i++) {
6424 /* if parent != 0, we're doing a full backref
6425 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
6426 * just makes the backref allocator create a data
6429 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6430 rec->start, rec->max_size,
6434 BTRFS_FIRST_FREE_OBJECTID :
6441 "adding new data backref on %llu %s %llu owner %llu offset %llu found %d\n",
6442 (unsigned long long)rec->start,
6443 back->full_backref ? "parent" : "root",
6444 back->full_backref ? (unsigned long long)parent :
6445 (unsigned long long)dback->root,
6446 (unsigned long long)dback->owner,
6447 (unsigned long long)dback->offset, dback->found_ref);
6450 struct tree_backref *tback;
6452 tback = to_tree_backref(back);
6453 if (back->full_backref)
6454 parent = tback->parent;
6458 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6459 rec->start, rec->max_size,
6460 parent, tback->root, 0, 0);
6462 "adding new tree backref on start %llu len %llu parent %llu root %llu\n",
6463 rec->start, rec->max_size, parent, tback->root);
6466 btrfs_release_path(path);
6470 static struct extent_entry *find_entry(struct list_head *entries,
6471 u64 bytenr, u64 bytes)
6473 struct extent_entry *entry = NULL;
6475 list_for_each_entry(entry, entries, list) {
6476 if (entry->bytenr == bytenr && entry->bytes == bytes)
6483 static struct extent_entry *find_most_right_entry(struct list_head *entries)
6485 struct extent_entry *entry, *best = NULL, *prev = NULL;
6487 list_for_each_entry(entry, entries, list) {
6489 * If there are as many broken entries as entries then we know
6490 * not to trust this particular entry.
6492 if (entry->broken == entry->count)
6496 * Special case, when there are only two entries and 'best' is
6506 * If our current entry == best then we can't be sure our best
6507 * is really the best, so we need to keep searching.
6509 if (best && best->count == entry->count) {
6515 /* Prev == entry, not good enough, have to keep searching */
6516 if (!prev->broken && prev->count == entry->count)
6520 best = (prev->count > entry->count) ? prev : entry;
6521 else if (best->count < entry->count)
6529 static int repair_ref(struct btrfs_fs_info *info, struct btrfs_path *path,
6530 struct data_backref *dback, struct extent_entry *entry)
6532 struct btrfs_trans_handle *trans;
6533 struct btrfs_root *root;
6534 struct btrfs_file_extent_item *fi;
6535 struct extent_buffer *leaf;
6536 struct btrfs_key key;
6540 key.objectid = dback->root;
6541 key.type = BTRFS_ROOT_ITEM_KEY;
6542 key.offset = (u64)-1;
6543 root = btrfs_read_fs_root(info, &key);
6545 fprintf(stderr, "Couldn't find root for our ref\n");
6550 * The backref points to the original offset of the extent if it was
6551 * split, so we need to search down to the offset we have and then walk
6552 * forward until we find the backref we're looking for.
6554 key.objectid = dback->owner;
6555 key.type = BTRFS_EXTENT_DATA_KEY;
6556 key.offset = dback->offset;
6557 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6559 fprintf(stderr, "Error looking up ref %d\n", ret);
6564 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6565 ret = btrfs_next_leaf(root, path);
6567 fprintf(stderr, "Couldn't find our ref, next\n");
6571 leaf = path->nodes[0];
6572 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6573 if (key.objectid != dback->owner ||
6574 key.type != BTRFS_EXTENT_DATA_KEY) {
6575 fprintf(stderr, "Couldn't find our ref, search\n");
6578 fi = btrfs_item_ptr(leaf, path->slots[0],
6579 struct btrfs_file_extent_item);
6580 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
6581 bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
6583 if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
6588 btrfs_release_path(path);
6590 trans = btrfs_start_transaction(root, 1);
6592 return PTR_ERR(trans);
6595 * Ok we have the key of the file extent we want to fix, now we can cow
6596 * down to the thing and fix it.
6598 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
6600 fprintf(stderr, "error cowing down to ref [%llu,%u,%llu]: %d\n",
6601 key.objectid, key.type, key.offset, ret);
6606 "well that's odd, we just found this key [%llu,%u,%llu]\n",
6607 key.objectid, key.type, key.offset);
6611 leaf = path->nodes[0];
6612 fi = btrfs_item_ptr(leaf, path->slots[0],
6613 struct btrfs_file_extent_item);
6615 if (btrfs_file_extent_compression(leaf, fi) &&
6616 dback->disk_bytenr != entry->bytenr) {
6618 "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",
6619 dback->disk_bytenr);
6624 if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
6625 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6626 } else if (dback->disk_bytenr > entry->bytenr) {
6627 u64 off_diff, offset;
6629 off_diff = dback->disk_bytenr - entry->bytenr;
6630 offset = btrfs_file_extent_offset(leaf, fi);
6631 if (dback->disk_bytenr + offset +
6632 btrfs_file_extent_num_bytes(leaf, fi) >
6633 entry->bytenr + entry->bytes) {
6635 "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",
6636 dback->disk_bytenr);
6641 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6642 btrfs_set_file_extent_offset(leaf, fi, offset);
6643 } else if (dback->disk_bytenr < entry->bytenr) {
6646 offset = btrfs_file_extent_offset(leaf, fi);
6647 if (dback->disk_bytenr + offset < entry->bytenr) {
6649 "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",
6650 dback->disk_bytenr);
6655 offset += dback->disk_bytenr;
6656 offset -= entry->bytenr;
6657 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6658 btrfs_set_file_extent_offset(leaf, fi, offset);
6661 btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
6664 * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
6665 * only do this if we aren't using compression, otherwise it's a
6668 if (!btrfs_file_extent_compression(leaf, fi))
6669 btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
6671 printf("ram bytes may be wrong?\n");
6672 btrfs_mark_buffer_dirty(leaf);
6674 err = btrfs_commit_transaction(trans, root);
6675 btrfs_release_path(path);
6676 return ret ? ret : err;
6679 static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
6680 struct extent_record *rec)
6682 struct extent_backref *back, *tmp;
6683 struct data_backref *dback;
6684 struct extent_entry *entry, *best = NULL;
6687 int broken_entries = 0;
6692 * Metadata is easy and the backrefs should always agree on bytenr and
6693 * size, if not we've got bigger issues.
6698 rbtree_postorder_for_each_entry_safe(back, tmp,
6699 &rec->backref_tree, node) {
6700 if (back->full_backref || !back->is_data)
6703 dback = to_data_backref(back);
6706 * We only pay attention to backrefs that we found a real
6709 if (dback->found_ref == 0)
6713 * For now we only catch when the bytes don't match, not the
6714 * bytenr. We can easily do this at the same time, but I want
6715 * to have a fs image to test on before we just add repair
6716 * functionality willy-nilly so we know we won't screw up the
6720 entry = find_entry(&entries, dback->disk_bytenr,
6723 entry = malloc(sizeof(struct extent_entry));
6728 memset(entry, 0, sizeof(*entry));
6729 entry->bytenr = dback->disk_bytenr;
6730 entry->bytes = dback->bytes;
6731 list_add_tail(&entry->list, &entries);
6736 * If we only have on entry we may think the entries agree when
6737 * in reality they don't so we have to do some extra checking.
6739 if (dback->disk_bytenr != rec->start ||
6740 dback->bytes != rec->nr || back->broken)
6751 /* Yay all the backrefs agree, carry on good sir */
6752 if (nr_entries <= 1 && !mismatch)
6756 "attempting to repair backref discrepency for bytenr %llu\n",
6760 * First we want to see if the backrefs can agree amongst themselves who
6761 * is right, so figure out which one of the entries has the highest
6764 best = find_most_right_entry(&entries);
6767 * Ok so we may have an even split between what the backrefs think, so
6768 * this is where we use the extent ref to see what it thinks.
6771 entry = find_entry(&entries, rec->start, rec->nr);
6772 if (!entry && (!broken_entries || !rec->found_rec)) {
6774 "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",
6775 rec->start, rec->nr);
6778 } else if (!entry) {
6780 * Ok our backrefs were broken, we'll assume this is the
6781 * correct value and add an entry for this range.
6783 entry = malloc(sizeof(struct extent_entry));
6788 memset(entry, 0, sizeof(*entry));
6789 entry->bytenr = rec->start;
6790 entry->bytes = rec->nr;
6791 list_add_tail(&entry->list, &entries);
6795 best = find_most_right_entry(&entries);
6798 "backrefs and extent record evenly split on who is right, this is going to require user input to fix bytenr %llu bytes %llu\n",
6799 rec->start, rec->nr);
6806 * I don't think this can happen currently as we'll abort() if we catch
6807 * this case higher up, but in case somebody removes that we still can't
6808 * deal with it properly here yet, so just bail out of that's the case.
6810 if (best->bytenr != rec->start) {
6812 "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",
6813 rec->start, rec->nr);
6819 * Ok great we all agreed on an extent record, let's go find the real
6820 * references and fix up the ones that don't match.
6822 rbtree_postorder_for_each_entry_safe(back, tmp,
6823 &rec->backref_tree, node) {
6824 if (back->full_backref || !back->is_data)
6827 dback = to_data_backref(back);
6830 * Still ignoring backrefs that don't have a real ref attached
6833 if (dback->found_ref == 0)
6836 if (dback->bytes == best->bytes &&
6837 dback->disk_bytenr == best->bytenr)
6840 ret = repair_ref(info, path, dback, best);
6846 * Ok we messed with the actual refs, which means we need to drop our
6847 * entire cache and go back and rescan. I know this is a huge pain and
6848 * adds a lot of extra work, but it's the only way to be safe. Once all
6849 * the backrefs agree we may not need to do anything to the extent
6854 while (!list_empty(&entries)) {
6855 entry = list_entry(entries.next, struct extent_entry, list);
6856 list_del_init(&entry->list);
6862 static int process_duplicates(struct cache_tree *extent_cache,
6863 struct extent_record *rec)
6865 struct extent_record *good, *tmp;
6866 struct cache_extent *cache;
6870 * If we found a extent record for this extent then return, or if we
6871 * have more than one duplicate we are likely going to need to delete
6874 if (rec->found_rec || rec->num_duplicates > 1)
6877 /* Shouldn't happen but just in case */
6878 BUG_ON(!rec->num_duplicates);
6881 * So this happens if we end up with a backref that doesn't match the
6882 * actual extent entry. So either the backref is bad or the extent
6883 * entry is bad. Either way we want to have the extent_record actually
6884 * reflect what we found in the extent_tree, so we need to take the
6885 * duplicate out and use that as the extent_record since the only way we
6886 * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
6888 remove_cache_extent(extent_cache, &rec->cache);
6890 good = to_extent_record(rec->dups.next);
6891 list_del_init(&good->list);
6892 INIT_LIST_HEAD(&good->backrefs);
6893 INIT_LIST_HEAD(&good->dups);
6894 good->cache.start = good->start;
6895 good->cache.size = good->nr;
6896 good->content_checked = 0;
6897 good->owner_ref_checked = 0;
6898 good->num_duplicates = 0;
6899 good->refs = rec->refs;
6900 list_splice_init(&rec->backrefs, &good->backrefs);
6902 cache = lookup_cache_extent(extent_cache, good->start,
6906 tmp = container_of(cache, struct extent_record, cache);
6909 * If we find another overlapping extent and it's found_rec is
6910 * set then it's a duplicate and we need to try and delete
6913 if (tmp->found_rec || tmp->num_duplicates > 0) {
6914 if (list_empty(&good->list))
6915 list_add_tail(&good->list,
6916 &duplicate_extents);
6917 good->num_duplicates += tmp->num_duplicates + 1;
6918 list_splice_init(&tmp->dups, &good->dups);
6919 list_del_init(&tmp->list);
6920 list_add_tail(&tmp->list, &good->dups);
6921 remove_cache_extent(extent_cache, &tmp->cache);
6926 * Ok we have another non extent item backed extent rec, so lets
6927 * just add it to this extent and carry on like we did above.
6929 good->refs += tmp->refs;
6930 list_splice_init(&tmp->backrefs, &good->backrefs);
6931 remove_cache_extent(extent_cache, &tmp->cache);
6934 ret = insert_cache_extent(extent_cache, &good->cache);
6937 return good->num_duplicates ? 0 : 1;
6940 static int delete_duplicate_records(struct btrfs_root *root,
6941 struct extent_record *rec)
6943 struct btrfs_trans_handle *trans;
6944 LIST_HEAD(delete_list);
6945 struct btrfs_path path;
6946 struct extent_record *tmp, *good, *n;
6949 struct btrfs_key key;
6951 btrfs_init_path(&path);
6954 /* Find the record that covers all of the duplicates. */
6955 list_for_each_entry(tmp, &rec->dups, list) {
6956 if (good->start < tmp->start)
6958 if (good->nr > tmp->nr)
6961 if (tmp->start + tmp->nr < good->start + good->nr) {
6963 "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",
6964 tmp->start, tmp->nr, good->start, good->nr);
6971 list_add_tail(&rec->list, &delete_list);
6973 list_for_each_entry_safe(tmp, n, &rec->dups, list) {
6976 list_move_tail(&tmp->list, &delete_list);
6979 root = root->fs_info->extent_root;
6980 trans = btrfs_start_transaction(root, 1);
6981 if (IS_ERR(trans)) {
6982 ret = PTR_ERR(trans);
6986 list_for_each_entry(tmp, &delete_list, list) {
6987 if (tmp->found_rec == 0)
6989 key.objectid = tmp->start;
6990 key.type = BTRFS_EXTENT_ITEM_KEY;
6991 key.offset = tmp->nr;
6993 /* Shouldn't happen but just in case */
6994 if (tmp->metadata) {
6996 "well this shouldn't happen, extent record overlaps but is metadata? [%llu, %llu]\n",
6997 tmp->start, tmp->nr);
7001 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
7007 ret = btrfs_del_item(trans, root, &path);
7010 btrfs_release_path(&path);
7013 err = btrfs_commit_transaction(trans, root);
7017 while (!list_empty(&delete_list)) {
7018 tmp = to_extent_record(delete_list.next);
7019 list_del_init(&tmp->list);
7025 while (!list_empty(&rec->dups)) {
7026 tmp = to_extent_record(rec->dups.next);
7027 list_del_init(&tmp->list);
7031 btrfs_release_path(&path);
7033 if (!ret && !nr_del)
7034 rec->num_duplicates = 0;
7036 return ret ? ret : nr_del;
7039 static int find_possible_backrefs(struct btrfs_fs_info *info,
7040 struct btrfs_path *path,
7041 struct cache_tree *extent_cache,
7042 struct extent_record *rec)
7044 struct btrfs_root *root;
7045 struct extent_backref *back, *tmp;
7046 struct data_backref *dback;
7047 struct cache_extent *cache;
7048 struct btrfs_file_extent_item *fi;
7049 struct btrfs_key key;
7053 rbtree_postorder_for_each_entry_safe(back, tmp,
7054 &rec->backref_tree, node) {
7055 /* Don't care about full backrefs (poor unloved backrefs) */
7056 if (back->full_backref || !back->is_data)
7059 dback = to_data_backref(back);
7061 /* We found this one, we don't need to do a lookup */
7062 if (dback->found_ref)
7065 key.objectid = dback->root;
7066 key.type = BTRFS_ROOT_ITEM_KEY;
7067 key.offset = (u64)-1;
7069 root = btrfs_read_fs_root(info, &key);
7071 /* No root, definitely a bad ref, skip */
7072 if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
7074 /* Other err, exit */
7076 return PTR_ERR(root);
7078 key.objectid = dback->owner;
7079 key.type = BTRFS_EXTENT_DATA_KEY;
7080 key.offset = dback->offset;
7081 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
7083 btrfs_release_path(path);
7086 /* Didn't find it, we can carry on */
7091 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
7092 struct btrfs_file_extent_item);
7093 bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
7094 bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
7095 btrfs_release_path(path);
7096 cache = lookup_cache_extent(extent_cache, bytenr, 1);
7098 struct extent_record *tmp;
7100 tmp = container_of(cache, struct extent_record, cache);
7103 * If we found an extent record for the bytenr for this
7104 * particular backref then we can't add it to our
7105 * current extent record. We only want to add backrefs
7106 * that don't have a corresponding extent item in the
7107 * extent tree since they likely belong to this record
7108 * and we need to fix it if it doesn't match bytenrs.
7114 dback->found_ref += 1;
7115 dback->disk_bytenr = bytenr;
7116 dback->bytes = bytes;
7119 * Set this so the verify backref code knows not to trust the
7120 * values in this backref.
7129 * Record orphan data ref into corresponding root.
7131 * Return 0 if the extent item contains data ref and recorded.
7132 * Return 1 if the extent item contains no useful data ref
7133 * On that case, it may contains only shared_dataref or metadata backref
7134 * or the file extent exists(this should be handled by the extent bytenr
7136 * Return <0 if something goes wrong.
7138 static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
7139 struct extent_record *rec)
7141 struct btrfs_key key;
7142 struct btrfs_root *dest_root;
7143 struct extent_backref *back, *tmp;
7144 struct data_backref *dback;
7145 struct orphan_data_extent *orphan;
7146 struct btrfs_path path;
7147 int recorded_data_ref = 0;
7152 btrfs_init_path(&path);
7153 rbtree_postorder_for_each_entry_safe(back, tmp,
7154 &rec->backref_tree, node) {
7155 if (back->full_backref || !back->is_data ||
7156 !back->found_extent_tree)
7158 dback = to_data_backref(back);
7159 if (dback->found_ref)
7161 key.objectid = dback->root;
7162 key.type = BTRFS_ROOT_ITEM_KEY;
7163 key.offset = (u64)-1;
7165 dest_root = btrfs_read_fs_root(fs_info, &key);
7167 /* For non-exist root we just skip it */
7168 if (IS_ERR(dest_root) || !dest_root)
7171 key.objectid = dback->owner;
7172 key.type = BTRFS_EXTENT_DATA_KEY;
7173 key.offset = dback->offset;
7175 ret = btrfs_search_slot(NULL, dest_root, &key, &path, 0, 0);
7176 btrfs_release_path(&path);
7178 * For ret < 0, it's OK since the fs-tree may be corrupted,
7179 * we need to record it for inode/file extent rebuild.
7180 * For ret > 0, we record it only for file extent rebuild.
7181 * For ret == 0, the file extent exists but only bytenr
7182 * mismatch, let the original bytenr fix routine to handle,
7188 orphan = malloc(sizeof(*orphan));
7193 INIT_LIST_HEAD(&orphan->list);
7194 orphan->root = dback->root;
7195 orphan->objectid = dback->owner;
7196 orphan->offset = dback->offset;
7197 orphan->disk_bytenr = rec->cache.start;
7198 orphan->disk_len = rec->cache.size;
7199 list_add(&dest_root->orphan_data_extents, &orphan->list);
7200 recorded_data_ref = 1;
7203 btrfs_release_path(&path);
7205 return !recorded_data_ref;
7211 * when an incorrect extent item is found, this will delete
7212 * all of the existing entries for it and recreate them
7213 * based on what the tree scan found.
7215 static int fixup_extent_refs(struct btrfs_fs_info *info,
7216 struct cache_tree *extent_cache,
7217 struct extent_record *rec)
7219 struct btrfs_trans_handle *trans = NULL;
7221 struct btrfs_path path;
7222 struct cache_extent *cache;
7223 struct extent_backref *back, *tmp;
7227 if (rec->flag_block_full_backref)
7228 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7230 btrfs_init_path(&path);
7231 if (rec->refs != rec->extent_item_refs && !rec->metadata) {
7233 * Sometimes the backrefs themselves are so broken they don't
7234 * get attached to any meaningful rec, so first go back and
7235 * check any of our backrefs that we couldn't find and throw
7236 * them into the list if we find the backref so that
7237 * verify_backrefs can figure out what to do.
7239 ret = find_possible_backrefs(info, &path, extent_cache, rec);
7244 /* step one, make sure all of the backrefs agree */
7245 ret = verify_backrefs(info, &path, rec);
7249 trans = btrfs_start_transaction(info->extent_root, 1);
7250 if (IS_ERR(trans)) {
7251 ret = PTR_ERR(trans);
7255 /* step two, delete all the existing records */
7256 ret = delete_extent_records(trans, info->extent_root, &path,
7262 /* was this block corrupt? If so, don't add references to it */
7263 cache = lookup_cache_extent(info->corrupt_blocks,
7264 rec->start, rec->max_size);
7270 /* step three, recreate all the refs we did find */
7271 rbtree_postorder_for_each_entry_safe(back, tmp,
7272 &rec->backref_tree, node) {
7274 * if we didn't find any references, don't create a
7277 if (!back->found_ref)
7280 rec->bad_full_backref = 0;
7281 ret = record_extent(trans, info, &path, rec, back, allocated,
7290 int err = btrfs_commit_transaction(trans, info->extent_root);
7297 fprintf(stderr, "Repaired extent references for %llu\n",
7298 (unsigned long long)rec->start);
7300 btrfs_release_path(&path);
7304 static int fixup_extent_flags(struct btrfs_fs_info *fs_info,
7305 struct extent_record *rec)
7307 struct btrfs_trans_handle *trans;
7308 struct btrfs_root *root = fs_info->extent_root;
7309 struct btrfs_path path;
7310 struct btrfs_extent_item *ei;
7311 struct btrfs_key key;
7315 key.objectid = rec->start;
7316 if (rec->metadata) {
7317 key.type = BTRFS_METADATA_ITEM_KEY;
7318 key.offset = rec->info_level;
7320 key.type = BTRFS_EXTENT_ITEM_KEY;
7321 key.offset = rec->max_size;
7324 trans = btrfs_start_transaction(root, 0);
7326 return PTR_ERR(trans);
7328 btrfs_init_path(&path);
7329 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
7331 btrfs_release_path(&path);
7332 btrfs_commit_transaction(trans, root);
7335 fprintf(stderr, "Didn't find extent for %llu\n",
7336 (unsigned long long)rec->start);
7337 btrfs_release_path(&path);
7338 btrfs_commit_transaction(trans, root);
7342 ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
7343 struct btrfs_extent_item);
7344 flags = btrfs_extent_flags(path.nodes[0], ei);
7345 if (rec->flag_block_full_backref) {
7346 fprintf(stderr, "setting full backref on %llu\n",
7347 (unsigned long long)key.objectid);
7348 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7350 fprintf(stderr, "clearing full backref on %llu\n",
7351 (unsigned long long)key.objectid);
7352 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
7354 btrfs_set_extent_flags(path.nodes[0], ei, flags);
7355 btrfs_mark_buffer_dirty(path.nodes[0]);
7356 btrfs_release_path(&path);
7357 ret = btrfs_commit_transaction(trans, root);
7359 fprintf(stderr, "Repaired extent flags for %llu\n",
7360 (unsigned long long)rec->start);
7365 /* right now we only prune from the extent allocation tree */
7366 static int prune_one_block(struct btrfs_trans_handle *trans,
7367 struct btrfs_fs_info *info,
7368 struct btrfs_corrupt_block *corrupt)
7371 struct btrfs_path path;
7372 struct extent_buffer *eb;
7376 int level = corrupt->level + 1;
7378 btrfs_init_path(&path);
7380 /* we want to stop at the parent to our busted block */
7381 path.lowest_level = level;
7383 ret = btrfs_search_slot(trans, info->extent_root,
7384 &corrupt->key, &path, -1, 1);
7389 eb = path.nodes[level];
7396 * hopefully the search gave us the block we want to prune,
7397 * lets try that first
7399 slot = path.slots[level];
7400 found = btrfs_node_blockptr(eb, slot);
7401 if (found == corrupt->cache.start)
7404 nritems = btrfs_header_nritems(eb);
7406 /* the search failed, lets scan this node and hope we find it */
7407 for (slot = 0; slot < nritems; slot++) {
7408 found = btrfs_node_blockptr(eb, slot);
7409 if (found == corrupt->cache.start)
7413 * We couldn't find the bad block.
7414 * TODO: search all the nodes for pointers to this block
7416 if (eb == info->extent_root->node) {
7421 btrfs_release_path(&path);
7426 printk("deleting pointer to block %llu\n", corrupt->cache.start);
7427 ret = btrfs_del_ptr(info->extent_root, &path, level, slot);
7430 btrfs_release_path(&path);
7434 static int prune_corrupt_blocks(struct btrfs_fs_info *info)
7436 struct btrfs_trans_handle *trans = NULL;
7437 struct cache_extent *cache;
7438 struct btrfs_corrupt_block *corrupt;
7441 cache = search_cache_extent(info->corrupt_blocks, 0);
7445 trans = btrfs_start_transaction(info->extent_root, 1);
7447 return PTR_ERR(trans);
7449 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
7450 prune_one_block(trans, info, corrupt);
7451 remove_cache_extent(info->corrupt_blocks, cache);
7454 return btrfs_commit_transaction(trans, info->extent_root);
7458 static int check_extent_refs(struct btrfs_root *root,
7459 struct cache_tree *extent_cache)
7461 struct extent_record *rec;
7462 struct cache_extent *cache;
7469 * if we're doing a repair, we have to make sure
7470 * we don't allocate from the problem extents.
7471 * In the worst case, this will be all the
7474 cache = search_cache_extent(extent_cache, 0);
7476 rec = container_of(cache, struct extent_record, cache);
7477 set_extent_dirty(root->fs_info->excluded_extents,
7479 rec->start + rec->max_size - 1);
7480 cache = next_cache_extent(cache);
7483 /* pin down all the corrupted blocks too */
7484 cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
7486 set_extent_dirty(root->fs_info->excluded_extents,
7488 cache->start + cache->size - 1);
7489 cache = next_cache_extent(cache);
7491 prune_corrupt_blocks(root->fs_info);
7492 reset_cached_block_groups(root->fs_info);
7495 reset_cached_block_groups(root->fs_info);
7498 * We need to delete any duplicate entries we find first otherwise we
7499 * could mess up the extent tree when we have backrefs that actually
7500 * belong to a different extent item and not the weird duplicate one.
7502 while (repair && !list_empty(&duplicate_extents)) {
7503 rec = to_extent_record(duplicate_extents.next);
7504 list_del_init(&rec->list);
7506 /* Sometimes we can find a backref before we find an actual
7507 * extent, so we need to process it a little bit to see if there
7508 * truly are multiple EXTENT_ITEM_KEY's for the same range, or
7509 * if this is a backref screwup. If we need to delete stuff
7510 * process_duplicates() will return 0, otherwise it will return
7513 if (process_duplicates(extent_cache, rec))
7515 ret = delete_duplicate_records(root, rec);
7519 * delete_duplicate_records will return the number of entries
7520 * deleted, so if it's greater than 0 then we know we actually
7521 * did something and we need to remove.
7534 cache = search_cache_extent(extent_cache, 0);
7537 rec = container_of(cache, struct extent_record, cache);
7538 if (rec->num_duplicates) {
7540 "extent item %llu has multiple extent items\n",
7541 (unsigned long long)rec->start);
7545 if (rec->refs != rec->extent_item_refs) {
7546 fprintf(stderr, "ref mismatch on [%llu %llu] ",
7547 (unsigned long long)rec->start,
7548 (unsigned long long)rec->nr);
7549 fprintf(stderr, "extent item %llu, found %llu\n",
7550 (unsigned long long)rec->extent_item_refs,
7551 (unsigned long long)rec->refs);
7552 ret = record_orphan_data_extents(root->fs_info, rec);
7558 if (all_backpointers_checked(rec, 1)) {
7559 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
7560 (unsigned long long)rec->start,
7561 (unsigned long long)rec->nr);
7565 if (!rec->owner_ref_checked) {
7566 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
7567 (unsigned long long)rec->start,
7568 (unsigned long long)rec->nr);
7573 if (repair && fix) {
7574 ret = fixup_extent_refs(root->fs_info, extent_cache,
7581 if (rec->bad_full_backref) {
7582 fprintf(stderr, "bad full backref, on [%llu]\n",
7583 (unsigned long long)rec->start);
7585 ret = fixup_extent_flags(root->fs_info, rec);
7593 * Although it's not a extent ref's problem, we reuse this
7594 * routine for error reporting.
7595 * No repair function yet.
7597 if (rec->crossing_stripes) {
7599 "bad metadata [%llu, %llu) crossing stripe boundary\n",
7600 rec->start, rec->start + rec->max_size);
7604 if (rec->wrong_chunk_type) {
7606 "bad extent [%llu, %llu), type mismatch with chunk\n",
7607 rec->start, rec->start + rec->max_size);
7612 remove_cache_extent(extent_cache, cache);
7613 free_all_extent_backrefs(rec);
7614 if (!init_extent_tree && repair && (!cur_err || fix))
7615 clear_extent_dirty(root->fs_info->excluded_extents,
7617 rec->start + rec->max_size - 1);
7622 if (ret && ret != -EAGAIN) {
7623 fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
7626 struct btrfs_trans_handle *trans;
7628 root = root->fs_info->extent_root;
7629 trans = btrfs_start_transaction(root, 1);
7630 if (IS_ERR(trans)) {
7631 ret = PTR_ERR(trans);
7635 ret = btrfs_fix_block_accounting(trans, root);
7638 ret = btrfs_commit_transaction(trans, root);
7651 * Check the chunk with its block group/dev list ref:
7652 * Return 0 if all refs seems valid.
7653 * Return 1 if part of refs seems valid, need later check for rebuild ref
7654 * like missing block group and needs to search extent tree to rebuild them.
7655 * Return -1 if essential refs are missing and unable to rebuild.
7657 static int check_chunk_refs(struct chunk_record *chunk_rec,
7658 struct block_group_tree *block_group_cache,
7659 struct device_extent_tree *dev_extent_cache,
7662 struct cache_extent *block_group_item;
7663 struct block_group_record *block_group_rec;
7664 struct cache_extent *dev_extent_item;
7665 struct device_extent_record *dev_extent_rec;
7669 int metadump_v2 = 0;
7673 block_group_item = lookup_cache_extent(&block_group_cache->tree,
7676 if (block_group_item) {
7677 block_group_rec = container_of(block_group_item,
7678 struct block_group_record,
7680 if (chunk_rec->length != block_group_rec->offset ||
7681 chunk_rec->offset != block_group_rec->objectid ||
7683 chunk_rec->type_flags != block_group_rec->flags)) {
7686 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
7687 chunk_rec->objectid,
7692 chunk_rec->type_flags,
7693 block_group_rec->objectid,
7694 block_group_rec->type,
7695 block_group_rec->offset,
7696 block_group_rec->offset,
7697 block_group_rec->objectid,
7698 block_group_rec->flags);
7701 list_del_init(&block_group_rec->list);
7702 chunk_rec->bg_rec = block_group_rec;
7707 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
7708 chunk_rec->objectid,
7713 chunk_rec->type_flags);
7720 length = calc_stripe_length(chunk_rec->type_flags, chunk_rec->length,
7721 chunk_rec->num_stripes);
7722 for (i = 0; i < chunk_rec->num_stripes; ++i) {
7723 devid = chunk_rec->stripes[i].devid;
7724 offset = chunk_rec->stripes[i].offset;
7725 dev_extent_item = lookup_cache_extent2(&dev_extent_cache->tree,
7726 devid, offset, length);
7727 if (dev_extent_item) {
7728 dev_extent_rec = container_of(dev_extent_item,
7729 struct device_extent_record,
7731 if (dev_extent_rec->objectid != devid ||
7732 dev_extent_rec->offset != offset ||
7733 dev_extent_rec->chunk_offset != chunk_rec->offset ||
7734 dev_extent_rec->length != length) {
7737 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
7738 chunk_rec->objectid,
7741 chunk_rec->stripes[i].devid,
7742 chunk_rec->stripes[i].offset,
7743 dev_extent_rec->objectid,
7744 dev_extent_rec->offset,
7745 dev_extent_rec->length);
7748 list_move(&dev_extent_rec->chunk_list,
7749 &chunk_rec->dextents);
7754 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
7755 chunk_rec->objectid,
7758 chunk_rec->stripes[i].devid,
7759 chunk_rec->stripes[i].offset);
7766 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
7767 int check_chunks(struct cache_tree *chunk_cache,
7768 struct block_group_tree *block_group_cache,
7769 struct device_extent_tree *dev_extent_cache,
7770 struct list_head *good, struct list_head *bad,
7771 struct list_head *rebuild, int silent)
7773 struct cache_extent *chunk_item;
7774 struct chunk_record *chunk_rec;
7775 struct block_group_record *bg_rec;
7776 struct device_extent_record *dext_rec;
7780 chunk_item = first_cache_extent(chunk_cache);
7781 while (chunk_item) {
7782 chunk_rec = container_of(chunk_item, struct chunk_record,
7784 err = check_chunk_refs(chunk_rec, block_group_cache,
7785 dev_extent_cache, silent);
7788 if (err == 0 && good)
7789 list_add_tail(&chunk_rec->list, good);
7790 if (err > 0 && rebuild)
7791 list_add_tail(&chunk_rec->list, rebuild);
7793 list_add_tail(&chunk_rec->list, bad);
7794 chunk_item = next_cache_extent(chunk_item);
7797 list_for_each_entry(bg_rec, &block_group_cache->block_groups, list) {
7800 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
7808 list_for_each_entry(dext_rec, &dev_extent_cache->no_chunk_orphans,
7812 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
7823 static int check_device_used(struct device_record *dev_rec,
7824 struct device_extent_tree *dext_cache)
7826 struct cache_extent *cache;
7827 struct device_extent_record *dev_extent_rec;
7830 cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
7832 dev_extent_rec = container_of(cache,
7833 struct device_extent_record,
7835 if (dev_extent_rec->objectid != dev_rec->devid)
7838 list_del_init(&dev_extent_rec->device_list);
7839 total_byte += dev_extent_rec->length;
7840 cache = next_cache_extent(cache);
7843 if (total_byte != dev_rec->byte_used) {
7845 "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
7846 total_byte, dev_rec->byte_used, dev_rec->objectid,
7847 dev_rec->type, dev_rec->offset);
7855 * Unlike device size alignment check above, some super total_bytes check
7856 * failure can lead to mount failure for newer kernel.
7858 * So this function will return the error for a fatal super total_bytes problem.
7860 static bool is_super_size_valid(struct btrfs_fs_info *fs_info)
7862 struct btrfs_device *dev;
7863 struct list_head *dev_list = &fs_info->fs_devices->devices;
7864 u64 total_bytes = 0;
7865 u64 super_bytes = btrfs_super_total_bytes(fs_info->super_copy);
7867 list_for_each_entry(dev, dev_list, dev_list)
7868 total_bytes += dev->total_bytes;
7870 /* Important check, which can cause unmountable fs */
7871 if (super_bytes < total_bytes) {
7872 error("super total bytes %llu smaller than real device(s) size %llu",
7873 super_bytes, total_bytes);
7874 error("mounting this fs may fail for newer kernels");
7875 error("this can be fixed by 'btrfs rescue fix-device-size'");
7880 * Optional check, just to make everything aligned and match with each
7883 * For a btrfs-image restored fs, we don't need to check it anyway.
7885 if (btrfs_super_flags(fs_info->super_copy) &
7886 (BTRFS_SUPER_FLAG_METADUMP | BTRFS_SUPER_FLAG_METADUMP_V2))
7888 if (!IS_ALIGNED(super_bytes, fs_info->sectorsize) ||
7889 !IS_ALIGNED(total_bytes, fs_info->sectorsize) ||
7890 super_bytes != total_bytes) {
7891 warning("minor unaligned/mismatch device size detected");
7893 "recommended to use 'btrfs rescue fix-device-size' to fix it");
7898 /* check btrfs_dev_item -> btrfs_dev_extent */
7899 static int check_devices(struct rb_root *dev_cache,
7900 struct device_extent_tree *dev_extent_cache)
7902 struct rb_node *dev_node;
7903 struct device_record *dev_rec;
7904 struct device_extent_record *dext_rec;
7908 dev_node = rb_first(dev_cache);
7910 dev_rec = container_of(dev_node, struct device_record, node);
7911 err = check_device_used(dev_rec, dev_extent_cache);
7915 check_dev_size_alignment(dev_rec->devid, dev_rec->total_byte,
7916 global_info->sectorsize);
7917 dev_node = rb_next(dev_node);
7919 list_for_each_entry(dext_rec, &dev_extent_cache->no_device_orphans,
7922 "Device extent[%llu, %llu, %llu] didn't find its device.\n",
7923 dext_rec->objectid, dext_rec->offset, dext_rec->length);
7930 static int add_root_item_to_list(struct list_head *head,
7931 u64 objectid, u64 bytenr, u64 last_snapshot,
7932 u8 level, u8 drop_level,
7933 struct btrfs_key *drop_key)
7935 struct root_item_record *ri_rec;
7937 ri_rec = malloc(sizeof(*ri_rec));
7940 ri_rec->bytenr = bytenr;
7941 ri_rec->objectid = objectid;
7942 ri_rec->level = level;
7943 ri_rec->drop_level = drop_level;
7944 ri_rec->last_snapshot = last_snapshot;
7946 memcpy(&ri_rec->drop_key, drop_key, sizeof(*drop_key));
7947 list_add_tail(&ri_rec->list, head);
7952 static void free_root_item_list(struct list_head *list)
7954 struct root_item_record *ri_rec;
7956 while (!list_empty(list)) {
7957 ri_rec = list_first_entry(list, struct root_item_record,
7959 list_del_init(&ri_rec->list);
7964 static int deal_root_from_list(struct list_head *list,
7965 struct btrfs_root *root,
7966 struct block_info *bits,
7968 struct cache_tree *pending,
7969 struct cache_tree *seen,
7970 struct cache_tree *reada,
7971 struct cache_tree *nodes,
7972 struct cache_tree *extent_cache,
7973 struct cache_tree *chunk_cache,
7974 struct rb_root *dev_cache,
7975 struct block_group_tree *block_group_cache,
7976 struct device_extent_tree *dev_extent_cache)
7981 while (!list_empty(list)) {
7982 struct root_item_record *rec;
7983 struct extent_buffer *buf;
7985 rec = list_entry(list->next,
7986 struct root_item_record, list);
7988 buf = read_tree_block(root->fs_info, rec->bytenr, 0);
7989 if (!extent_buffer_uptodate(buf)) {
7990 free_extent_buffer(buf);
7994 ret = add_root_to_pending(buf, extent_cache, pending,
7995 seen, nodes, rec->objectid);
7999 * To rebuild extent tree, we need deal with snapshot
8000 * one by one, otherwise we deal with node firstly which
8001 * can maximize readahead.
8004 ret = run_next_block(root, bits, bits_nr, &last,
8005 pending, seen, reada, nodes,
8006 extent_cache, chunk_cache,
8007 dev_cache, block_group_cache,
8008 dev_extent_cache, rec);
8012 free_extent_buffer(buf);
8013 list_del(&rec->list);
8019 ret = run_next_block(root, bits, bits_nr, &last, pending, seen,
8020 reada, nodes, extent_cache, chunk_cache,
8021 dev_cache, block_group_cache,
8022 dev_extent_cache, NULL);
8032 static int check_chunks_and_extents(struct btrfs_fs_info *fs_info)
8034 struct rb_root dev_cache;
8035 struct cache_tree chunk_cache;
8036 struct block_group_tree block_group_cache;
8037 struct device_extent_tree dev_extent_cache;
8038 struct cache_tree extent_cache;
8039 struct cache_tree seen;
8040 struct cache_tree pending;
8041 struct cache_tree reada;
8042 struct cache_tree nodes;
8043 struct extent_io_tree excluded_extents;
8044 struct cache_tree corrupt_blocks;
8045 struct btrfs_path path;
8046 struct btrfs_key key;
8047 struct btrfs_key found_key;
8049 struct block_info *bits;
8051 struct extent_buffer *leaf;
8053 struct btrfs_root_item ri;
8054 struct list_head dropping_trees;
8055 struct list_head normal_trees;
8056 struct btrfs_root *root1;
8057 struct btrfs_root *root;
8061 root = fs_info->fs_root;
8062 dev_cache = RB_ROOT;
8063 cache_tree_init(&chunk_cache);
8064 block_group_tree_init(&block_group_cache);
8065 device_extent_tree_init(&dev_extent_cache);
8067 cache_tree_init(&extent_cache);
8068 cache_tree_init(&seen);
8069 cache_tree_init(&pending);
8070 cache_tree_init(&nodes);
8071 cache_tree_init(&reada);
8072 cache_tree_init(&corrupt_blocks);
8073 extent_io_tree_init(&excluded_extents);
8074 INIT_LIST_HEAD(&dropping_trees);
8075 INIT_LIST_HEAD(&normal_trees);
8078 fs_info->excluded_extents = &excluded_extents;
8079 fs_info->fsck_extent_cache = &extent_cache;
8080 fs_info->free_extent_hook = free_extent_hook;
8081 fs_info->corrupt_blocks = &corrupt_blocks;
8085 bits = malloc(bits_nr * sizeof(struct block_info));
8091 if (ctx.progress_enabled) {
8092 ctx.tp = TASK_EXTENTS;
8093 task_start(ctx.info);
8097 root1 = fs_info->tree_root;
8098 level = btrfs_header_level(root1->node);
8099 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8100 root1->node->start, 0, level, 0, NULL);
8103 root1 = fs_info->chunk_root;
8104 level = btrfs_header_level(root1->node);
8105 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8106 root1->node->start, 0, level, 0, NULL);
8109 btrfs_init_path(&path);
8112 key.type = BTRFS_ROOT_ITEM_KEY;
8113 ret = btrfs_search_slot(NULL, fs_info->tree_root, &key, &path, 0, 0);
8117 leaf = path.nodes[0];
8118 slot = path.slots[0];
8119 if (slot >= btrfs_header_nritems(path.nodes[0])) {
8120 ret = btrfs_next_leaf(root, &path);
8123 leaf = path.nodes[0];
8124 slot = path.slots[0];
8126 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
8127 if (found_key.type == BTRFS_ROOT_ITEM_KEY) {
8128 unsigned long offset;
8131 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
8132 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
8133 last_snapshot = btrfs_root_last_snapshot(&ri);
8134 if (btrfs_disk_key_objectid(&ri.drop_progress) == 0) {
8135 level = btrfs_root_level(&ri);
8136 ret = add_root_item_to_list(&normal_trees,
8138 btrfs_root_bytenr(&ri),
8139 last_snapshot, level,
8144 level = btrfs_root_level(&ri);
8145 objectid = found_key.objectid;
8146 btrfs_disk_key_to_cpu(&found_key,
8148 ret = add_root_item_to_list(&dropping_trees,
8150 btrfs_root_bytenr(&ri),
8151 last_snapshot, level,
8152 ri.drop_level, &found_key);
8159 btrfs_release_path(&path);
8162 * check_block can return -EAGAIN if it fixes something, please keep
8163 * this in mind when dealing with return values from these functions, if
8164 * we get -EAGAIN we want to fall through and restart the loop.
8166 ret = deal_root_from_list(&normal_trees, root, bits, bits_nr, &pending,
8167 &seen, &reada, &nodes, &extent_cache,
8168 &chunk_cache, &dev_cache, &block_group_cache,
8175 ret = deal_root_from_list(&dropping_trees, root, bits, bits_nr,
8176 &pending, &seen, &reada, &nodes,
8177 &extent_cache, &chunk_cache, &dev_cache,
8178 &block_group_cache, &dev_extent_cache);
8185 ret = check_chunks(&chunk_cache, &block_group_cache,
8186 &dev_extent_cache, NULL, NULL, NULL, 0);
8193 ret = check_extent_refs(root, &extent_cache);
8200 ret = check_devices(&dev_cache, &dev_extent_cache);
8205 task_stop(ctx.info);
8207 free_corrupt_blocks_tree(fs_info->corrupt_blocks);
8208 extent_io_tree_cleanup(&excluded_extents);
8209 fs_info->fsck_extent_cache = NULL;
8210 fs_info->free_extent_hook = NULL;
8211 fs_info->corrupt_blocks = NULL;
8212 fs_info->excluded_extents = NULL;
8215 free_chunk_cache_tree(&chunk_cache);
8216 free_device_cache_tree(&dev_cache);
8217 free_block_group_tree(&block_group_cache);
8218 free_device_extent_tree(&dev_extent_cache);
8219 free_extent_cache_tree(&seen);
8220 free_extent_cache_tree(&pending);
8221 free_extent_cache_tree(&reada);
8222 free_extent_cache_tree(&nodes);
8223 free_root_item_list(&normal_trees);
8224 free_root_item_list(&dropping_trees);
8227 free_corrupt_blocks_tree(fs_info->corrupt_blocks);
8228 free_extent_cache_tree(&seen);
8229 free_extent_cache_tree(&pending);
8230 free_extent_cache_tree(&reada);
8231 free_extent_cache_tree(&nodes);
8232 free_chunk_cache_tree(&chunk_cache);
8233 free_block_group_tree(&block_group_cache);
8234 free_device_cache_tree(&dev_cache);
8235 free_device_extent_tree(&dev_extent_cache);
8236 free_extent_record_cache(&extent_cache);
8237 free_root_item_list(&normal_trees);
8238 free_root_item_list(&dropping_trees);
8239 extent_io_tree_cleanup(&excluded_extents);
8243 static int do_check_chunks_and_extents(struct btrfs_fs_info *fs_info)
8247 if (!ctx.progress_enabled)
8248 fprintf(stderr, "checking extents\n");
8249 if (check_mode == CHECK_MODE_LOWMEM)
8250 ret = check_chunks_and_extents_lowmem(fs_info);
8252 ret = check_chunks_and_extents(fs_info);
8254 /* Also repair device size related problems */
8255 if (repair && !ret) {
8256 ret = btrfs_fix_device_and_super_size(fs_info);
8263 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
8264 struct btrfs_root *root, int overwrite)
8266 struct extent_buffer *c;
8267 struct extent_buffer *old = root->node;
8270 struct btrfs_disk_key disk_key = {0,0,0};
8276 extent_buffer_get(c);
8279 c = btrfs_alloc_free_block(trans, root,
8280 root->fs_info->nodesize,
8281 root->root_key.objectid,
8282 &disk_key, level, 0, 0);
8285 extent_buffer_get(c);
8289 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
8290 btrfs_set_header_level(c, level);
8291 btrfs_set_header_bytenr(c, c->start);
8292 btrfs_set_header_generation(c, trans->transid);
8293 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
8294 btrfs_set_header_owner(c, root->root_key.objectid);
8296 write_extent_buffer(c, root->fs_info->fsid,
8297 btrfs_header_fsid(), BTRFS_FSID_SIZE);
8299 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
8300 btrfs_header_chunk_tree_uuid(c),
8303 btrfs_mark_buffer_dirty(c);
8305 * this case can happen in the following case:
8307 * 1.overwrite previous root.
8309 * 2.reinit reloc data root, this is because we skip pin
8310 * down reloc data tree before which means we can allocate
8311 * same block bytenr here.
8313 if (old->start == c->start) {
8314 btrfs_set_root_generation(&root->root_item,
8316 root->root_item.level = btrfs_header_level(root->node);
8317 ret = btrfs_update_root(trans, root->fs_info->tree_root,
8318 &root->root_key, &root->root_item);
8320 free_extent_buffer(c);
8324 free_extent_buffer(old);
8326 add_root_to_dirty_list(root);
8330 static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
8331 struct extent_buffer *eb, int tree_root)
8333 struct extent_buffer *tmp;
8334 struct btrfs_root_item *ri;
8335 struct btrfs_key key;
8337 int level = btrfs_header_level(eb);
8343 * If we have pinned this block before, don't pin it again.
8344 * This can not only avoid forever loop with broken filesystem
8345 * but also give us some speedups.
8347 if (test_range_bit(&fs_info->pinned_extents, eb->start,
8348 eb->start + eb->len - 1, EXTENT_DIRTY, 0))
8351 btrfs_pin_extent(fs_info, eb->start, eb->len);
8353 nritems = btrfs_header_nritems(eb);
8354 for (i = 0; i < nritems; i++) {
8356 btrfs_item_key_to_cpu(eb, &key, i);
8357 if (key.type != BTRFS_ROOT_ITEM_KEY)
8359 /* Skip the extent root and reloc roots */
8360 if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
8361 key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
8362 key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
8364 ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
8365 bytenr = btrfs_disk_root_bytenr(eb, ri);
8368 * If at any point we start needing the real root we
8369 * will have to build a stump root for the root we are
8370 * in, but for now this doesn't actually use the root so
8371 * just pass in extent_root.
8373 tmp = read_tree_block(fs_info, bytenr, 0);
8374 if (!extent_buffer_uptodate(tmp)) {
8375 fprintf(stderr, "Error reading root block\n");
8378 ret = pin_down_tree_blocks(fs_info, tmp, 0);
8379 free_extent_buffer(tmp);
8383 bytenr = btrfs_node_blockptr(eb, i);
8385 /* If we aren't the tree root don't read the block */
8386 if (level == 1 && !tree_root) {
8387 btrfs_pin_extent(fs_info, bytenr,
8392 tmp = read_tree_block(fs_info, bytenr, 0);
8393 if (!extent_buffer_uptodate(tmp)) {
8394 fprintf(stderr, "Error reading tree block\n");
8397 ret = pin_down_tree_blocks(fs_info, tmp, tree_root);
8398 free_extent_buffer(tmp);
8407 static int pin_metadata_blocks(struct btrfs_fs_info *fs_info)
8411 ret = pin_down_tree_blocks(fs_info, fs_info->chunk_root->node, 0);
8415 return pin_down_tree_blocks(fs_info, fs_info->tree_root->node, 1);
8418 static int reset_block_groups(struct btrfs_fs_info *fs_info)
8420 struct btrfs_block_group_cache *cache;
8421 struct btrfs_path path;
8422 struct extent_buffer *leaf;
8423 struct btrfs_chunk *chunk;
8424 struct btrfs_key key;
8428 btrfs_init_path(&path);
8430 key.type = BTRFS_CHUNK_ITEM_KEY;
8432 ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, &path, 0, 0);
8434 btrfs_release_path(&path);
8439 * We do this in case the block groups were screwed up and had alloc
8440 * bits that aren't actually set on the chunks. This happens with
8441 * restored images every time and could happen in real life I guess.
8443 fs_info->avail_data_alloc_bits = 0;
8444 fs_info->avail_metadata_alloc_bits = 0;
8445 fs_info->avail_system_alloc_bits = 0;
8447 /* First we need to create the in-memory block groups */
8449 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8450 ret = btrfs_next_leaf(fs_info->chunk_root, &path);
8452 btrfs_release_path(&path);
8460 leaf = path.nodes[0];
8461 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8462 if (key.type != BTRFS_CHUNK_ITEM_KEY) {
8467 chunk = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_chunk);
8468 btrfs_add_block_group(fs_info, 0,
8469 btrfs_chunk_type(leaf, chunk), key.offset,
8470 btrfs_chunk_length(leaf, chunk));
8471 set_extent_dirty(&fs_info->free_space_cache, key.offset,
8472 key.offset + btrfs_chunk_length(leaf, chunk));
8477 cache = btrfs_lookup_first_block_group(fs_info, start);
8481 start = cache->key.objectid + cache->key.offset;
8484 btrfs_release_path(&path);
8488 static int reset_balance(struct btrfs_trans_handle *trans,
8489 struct btrfs_fs_info *fs_info)
8491 struct btrfs_root *root = fs_info->tree_root;
8492 struct btrfs_path path;
8493 struct extent_buffer *leaf;
8494 struct btrfs_key key;
8495 int del_slot, del_nr = 0;
8499 btrfs_init_path(&path);
8500 key.objectid = BTRFS_BALANCE_OBJECTID;
8501 key.type = BTRFS_BALANCE_ITEM_KEY;
8503 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
8508 goto reinit_data_reloc;
8513 ret = btrfs_del_item(trans, root, &path);
8516 btrfs_release_path(&path);
8518 key.objectid = BTRFS_TREE_RELOC_OBJECTID;
8519 key.type = BTRFS_ROOT_ITEM_KEY;
8521 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
8525 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8530 ret = btrfs_del_items(trans, root, &path,
8537 btrfs_release_path(&path);
8540 ret = btrfs_search_slot(trans, root, &key, &path,
8547 leaf = path.nodes[0];
8548 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8549 if (key.objectid > BTRFS_TREE_RELOC_OBJECTID)
8551 if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
8556 del_slot = path.slots[0];
8565 ret = btrfs_del_items(trans, root, &path, del_slot, del_nr);
8569 btrfs_release_path(&path);
8572 key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
8573 key.type = BTRFS_ROOT_ITEM_KEY;
8574 key.offset = (u64)-1;
8575 root = btrfs_read_fs_root(fs_info, &key);
8577 fprintf(stderr, "Error reading data reloc tree\n");
8578 ret = PTR_ERR(root);
8581 record_root_in_trans(trans, root);
8582 ret = btrfs_fsck_reinit_root(trans, root, 0);
8585 ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID);
8587 btrfs_release_path(&path);
8591 static int reinit_extent_tree(struct btrfs_trans_handle *trans,
8592 struct btrfs_fs_info *fs_info)
8598 * The only reason we don't do this is because right now we're just
8599 * walking the trees we find and pinning down their bytes, we don't look
8600 * at any of the leaves. In order to do mixed groups we'd have to check
8601 * the leaves of any fs roots and pin down the bytes for any file
8602 * extents we find. Not hard but why do it if we don't have to?
8604 if (btrfs_fs_incompat(fs_info, MIXED_GROUPS)) {
8605 fprintf(stderr, "We don't support re-initing the extent tree "
8606 "for mixed block groups yet, please notify a btrfs "
8607 "developer you want to do this so they can add this "
8608 "functionality.\n");
8613 * first we need to walk all of the trees except the extent tree and pin
8614 * down the bytes that are in use so we don't overwrite any existing
8617 ret = pin_metadata_blocks(fs_info);
8619 fprintf(stderr, "error pinning down used bytes\n");
8624 * Need to drop all the block groups since we're going to recreate all
8627 btrfs_free_block_groups(fs_info);
8628 ret = reset_block_groups(fs_info);
8630 fprintf(stderr, "error resetting the block groups\n");
8634 /* Ok we can allocate now, reinit the extent root */
8635 ret = btrfs_fsck_reinit_root(trans, fs_info->extent_root, 0);
8637 fprintf(stderr, "extent root initialization failed\n");
8639 * When the transaction code is updated we should end the
8640 * transaction, but for now progs only knows about commit so
8641 * just return an error.
8647 * Now we have all the in-memory block groups setup so we can make
8648 * allocations properly, and the metadata we care about is safe since we
8649 * pinned all of it above.
8652 struct btrfs_block_group_cache *cache;
8654 cache = btrfs_lookup_first_block_group(fs_info, start);
8657 start = cache->key.objectid + cache->key.offset;
8658 ret = btrfs_insert_item(trans, fs_info->extent_root,
8659 &cache->key, &cache->item,
8660 sizeof(cache->item));
8662 fprintf(stderr, "Error adding block group\n");
8665 btrfs_extent_post_op(trans, fs_info->extent_root);
8668 ret = reset_balance(trans, fs_info);
8670 fprintf(stderr, "error resetting the pending balance\n");
8675 static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb)
8677 struct btrfs_path path;
8678 struct btrfs_trans_handle *trans;
8679 struct btrfs_key key;
8682 printf("Recowing metadata block %llu\n", eb->start);
8683 key.objectid = btrfs_header_owner(eb);
8684 key.type = BTRFS_ROOT_ITEM_KEY;
8685 key.offset = (u64)-1;
8687 root = btrfs_read_fs_root(root->fs_info, &key);
8689 fprintf(stderr, "Couldn't find owner root %llu\n",
8691 return PTR_ERR(root);
8694 trans = btrfs_start_transaction(root, 1);
8696 return PTR_ERR(trans);
8698 btrfs_init_path(&path);
8699 path.lowest_level = btrfs_header_level(eb);
8700 if (path.lowest_level)
8701 btrfs_node_key_to_cpu(eb, &key, 0);
8703 btrfs_item_key_to_cpu(eb, &key, 0);
8705 ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
8706 btrfs_commit_transaction(trans, root);
8707 btrfs_release_path(&path);
8711 static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad)
8713 struct btrfs_path path;
8714 struct btrfs_trans_handle *trans;
8715 struct btrfs_key key;
8718 printf("Deleting bad item [%llu,%u,%llu]\n", bad->key.objectid,
8719 bad->key.type, bad->key.offset);
8720 key.objectid = bad->root_id;
8721 key.type = BTRFS_ROOT_ITEM_KEY;
8722 key.offset = (u64)-1;
8724 root = btrfs_read_fs_root(root->fs_info, &key);
8726 fprintf(stderr, "Couldn't find owner root %llu\n",
8728 return PTR_ERR(root);
8731 trans = btrfs_start_transaction(root, 1);
8733 return PTR_ERR(trans);
8735 btrfs_init_path(&path);
8736 ret = btrfs_search_slot(trans, root, &bad->key, &path, -1, 1);
8742 ret = btrfs_del_item(trans, root, &path);
8744 btrfs_commit_transaction(trans, root);
8745 btrfs_release_path(&path);
8749 static int zero_log_tree(struct btrfs_root *root)
8751 struct btrfs_trans_handle *trans;
8754 trans = btrfs_start_transaction(root, 1);
8755 if (IS_ERR(trans)) {
8756 ret = PTR_ERR(trans);
8759 btrfs_set_super_log_root(root->fs_info->super_copy, 0);
8760 btrfs_set_super_log_root_level(root->fs_info->super_copy, 0);
8761 ret = btrfs_commit_transaction(trans, root);
8765 static int populate_csum(struct btrfs_trans_handle *trans,
8766 struct btrfs_root *csum_root, char *buf, u64 start,
8769 struct btrfs_fs_info *fs_info = csum_root->fs_info;
8774 while (offset < len) {
8775 sectorsize = fs_info->sectorsize;
8776 ret = read_extent_data(fs_info, buf, start + offset,
8780 ret = btrfs_csum_file_block(trans, csum_root, start + len,
8781 start + offset, buf, sectorsize);
8784 offset += sectorsize;
8789 static int fill_csum_tree_from_one_fs_root(struct btrfs_trans_handle *trans,
8790 struct btrfs_root *csum_root,
8791 struct btrfs_root *cur_root)
8793 struct btrfs_path path;
8794 struct btrfs_key key;
8795 struct extent_buffer *node;
8796 struct btrfs_file_extent_item *fi;
8803 buf = malloc(cur_root->fs_info->sectorsize);
8807 btrfs_init_path(&path);
8811 ret = btrfs_search_slot(NULL, cur_root, &key, &path, 0, 0);
8814 /* Iterate all regular file extents and fill its csum */
8816 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
8818 if (key.type != BTRFS_EXTENT_DATA_KEY)
8820 node = path.nodes[0];
8821 slot = path.slots[0];
8822 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
8823 if (btrfs_file_extent_type(node, fi) != BTRFS_FILE_EXTENT_REG)
8825 start = btrfs_file_extent_disk_bytenr(node, fi);
8826 len = btrfs_file_extent_disk_num_bytes(node, fi);
8828 ret = populate_csum(trans, csum_root, buf, start, len);
8835 * TODO: if next leaf is corrupted, jump to nearest next valid
8838 ret = btrfs_next_item(cur_root, &path);
8848 btrfs_release_path(&path);
8853 static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans,
8854 struct btrfs_root *csum_root)
8856 struct btrfs_fs_info *fs_info = csum_root->fs_info;
8857 struct btrfs_path path;
8858 struct btrfs_root *tree_root = fs_info->tree_root;
8859 struct btrfs_root *cur_root;
8860 struct extent_buffer *node;
8861 struct btrfs_key key;
8865 btrfs_init_path(&path);
8866 key.objectid = BTRFS_FS_TREE_OBJECTID;
8868 key.type = BTRFS_ROOT_ITEM_KEY;
8869 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
8878 node = path.nodes[0];
8879 slot = path.slots[0];
8880 btrfs_item_key_to_cpu(node, &key, slot);
8881 if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
8883 if (key.type != BTRFS_ROOT_ITEM_KEY)
8885 if (!is_fstree(key.objectid))
8887 key.offset = (u64)-1;
8889 cur_root = btrfs_read_fs_root(fs_info, &key);
8890 if (IS_ERR(cur_root) || !cur_root) {
8891 fprintf(stderr, "Fail to read fs/subvol tree: %lld\n",
8895 ret = fill_csum_tree_from_one_fs_root(trans, csum_root,
8900 ret = btrfs_next_item(tree_root, &path);
8910 btrfs_release_path(&path);
8914 static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans,
8915 struct btrfs_root *csum_root)
8917 struct btrfs_root *extent_root = csum_root->fs_info->extent_root;
8918 struct btrfs_path path;
8919 struct btrfs_extent_item *ei;
8920 struct extent_buffer *leaf;
8922 struct btrfs_key key;
8925 btrfs_init_path(&path);
8927 key.type = BTRFS_EXTENT_ITEM_KEY;
8929 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
8931 btrfs_release_path(&path);
8935 buf = malloc(csum_root->fs_info->sectorsize);
8937 btrfs_release_path(&path);
8942 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
8943 ret = btrfs_next_leaf(extent_root, &path);
8951 leaf = path.nodes[0];
8953 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
8954 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
8959 ei = btrfs_item_ptr(leaf, path.slots[0],
8960 struct btrfs_extent_item);
8961 if (!(btrfs_extent_flags(leaf, ei) &
8962 BTRFS_EXTENT_FLAG_DATA)) {
8967 ret = populate_csum(trans, csum_root, buf, key.objectid,
8974 btrfs_release_path(&path);
8980 * Recalculate the csum and put it into the csum tree.
8982 * Extent tree init will wipe out all the extent info, so in that case, we
8983 * can't depend on extent tree, but use fs tree. If search_fs_tree is set, we
8984 * will use fs/subvol trees to init the csum tree.
8986 static int fill_csum_tree(struct btrfs_trans_handle *trans,
8987 struct btrfs_root *csum_root,
8991 return fill_csum_tree_from_fs(trans, csum_root);
8993 return fill_csum_tree_from_extent(trans, csum_root);
8996 static void free_roots_info_cache(void)
8998 if (!roots_info_cache)
9001 while (!cache_tree_empty(roots_info_cache)) {
9002 struct cache_extent *entry;
9003 struct root_item_info *rii;
9005 entry = first_cache_extent(roots_info_cache);
9008 remove_cache_extent(roots_info_cache, entry);
9009 rii = container_of(entry, struct root_item_info, cache_extent);
9013 free(roots_info_cache);
9014 roots_info_cache = NULL;
9017 static int build_roots_info_cache(struct btrfs_fs_info *info)
9020 struct btrfs_key key;
9021 struct extent_buffer *leaf;
9022 struct btrfs_path path;
9024 if (!roots_info_cache) {
9025 roots_info_cache = malloc(sizeof(*roots_info_cache));
9026 if (!roots_info_cache)
9028 cache_tree_init(roots_info_cache);
9031 btrfs_init_path(&path);
9033 key.type = BTRFS_EXTENT_ITEM_KEY;
9035 ret = btrfs_search_slot(NULL, info->extent_root, &key, &path, 0, 0);
9038 leaf = path.nodes[0];
9041 struct btrfs_key found_key;
9042 struct btrfs_extent_item *ei;
9043 struct btrfs_extent_inline_ref *iref;
9044 unsigned long item_end;
9045 int slot = path.slots[0];
9050 struct cache_extent *entry;
9051 struct root_item_info *rii;
9053 if (slot >= btrfs_header_nritems(leaf)) {
9054 ret = btrfs_next_leaf(info->extent_root, &path);
9061 leaf = path.nodes[0];
9062 slot = path.slots[0];
9065 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
9067 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
9068 found_key.type != BTRFS_METADATA_ITEM_KEY)
9071 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
9072 flags = btrfs_extent_flags(leaf, ei);
9073 item_end = (unsigned long)ei + btrfs_item_size_nr(leaf, slot);
9075 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
9076 !(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))
9079 if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
9080 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
9081 level = found_key.offset;
9083 struct btrfs_tree_block_info *binfo;
9085 binfo = (struct btrfs_tree_block_info *)(ei + 1);
9086 iref = (struct btrfs_extent_inline_ref *)(binfo + 1);
9087 level = btrfs_tree_block_level(leaf, binfo);
9091 * It's a valid extent/metadata item that has no inline ref,
9092 * but SHARED_BLOCK_REF or other shared references.
9093 * So we need to do extra check to avoid reading beyond leaf
9096 if ((unsigned long)iref >= item_end)
9100 * For a root extent, it must be of the following type and the
9101 * first (and only one) iref in the item.
9103 type = btrfs_extent_inline_ref_type(leaf, iref);
9104 if (type != BTRFS_TREE_BLOCK_REF_KEY)
9107 root_id = btrfs_extent_inline_ref_offset(leaf, iref);
9108 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9110 rii = malloc(sizeof(struct root_item_info));
9115 rii->cache_extent.start = root_id;
9116 rii->cache_extent.size = 1;
9117 rii->level = (u8)-1;
9118 entry = &rii->cache_extent;
9119 ret = insert_cache_extent(roots_info_cache, entry);
9122 rii = container_of(entry, struct root_item_info,
9126 ASSERT(rii->cache_extent.start == root_id);
9127 ASSERT(rii->cache_extent.size == 1);
9129 if (level > rii->level || rii->level == (u8)-1) {
9131 rii->bytenr = found_key.objectid;
9132 rii->gen = btrfs_extent_generation(leaf, ei);
9133 rii->node_count = 1;
9134 } else if (level == rii->level) {
9142 btrfs_release_path(&path);
9147 static int maybe_repair_root_item(struct btrfs_path *path,
9148 const struct btrfs_key *root_key,
9149 const int read_only_mode)
9151 const u64 root_id = root_key->objectid;
9152 struct cache_extent *entry;
9153 struct root_item_info *rii;
9154 struct btrfs_root_item ri;
9155 unsigned long offset;
9157 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9160 "Error: could not find extent items for root %llu\n",
9161 root_key->objectid);
9165 rii = container_of(entry, struct root_item_info, cache_extent);
9166 ASSERT(rii->cache_extent.start == root_id);
9167 ASSERT(rii->cache_extent.size == 1);
9169 if (rii->node_count != 1) {
9171 "Error: could not find btree root extent for root %llu\n",
9176 offset = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
9177 read_extent_buffer(path->nodes[0], &ri, offset, sizeof(ri));
9179 if (btrfs_root_bytenr(&ri) != rii->bytenr ||
9180 btrfs_root_level(&ri) != rii->level ||
9181 btrfs_root_generation(&ri) != rii->gen) {
9184 * If we're in repair mode but our caller told us to not update
9185 * the root item, i.e. just check if it needs to be updated, don't
9186 * print this message, since the caller will call us again shortly
9187 * for the same root item without read only mode (the caller will
9188 * open a transaction first).
9190 if (!(read_only_mode && repair))
9192 "%sroot item for root %llu,"
9193 " current bytenr %llu, current gen %llu, current level %u,"
9194 " new bytenr %llu, new gen %llu, new level %u\n",
9195 (read_only_mode ? "" : "fixing "),
9197 btrfs_root_bytenr(&ri), btrfs_root_generation(&ri),
9198 btrfs_root_level(&ri),
9199 rii->bytenr, rii->gen, rii->level);
9201 if (btrfs_root_generation(&ri) > rii->gen) {
9203 "root %llu has a root item with a more recent gen (%llu) compared to the found root node (%llu)\n",
9204 root_id, btrfs_root_generation(&ri), rii->gen);
9208 if (!read_only_mode) {
9209 btrfs_set_root_bytenr(&ri, rii->bytenr);
9210 btrfs_set_root_level(&ri, rii->level);
9211 btrfs_set_root_generation(&ri, rii->gen);
9212 write_extent_buffer(path->nodes[0], &ri,
9213 offset, sizeof(ri));
9223 * A regression introduced in the 3.17 kernel (more specifically in 3.17-rc2),
9224 * caused read-only snapshots to be corrupted if they were created at a moment
9225 * when the source subvolume/snapshot had orphan items. The issue was that the
9226 * on-disk root items became incorrect, referring to the pre orphan cleanup root
9227 * node instead of the post orphan cleanup root node.
9228 * So this function, and its callees, just detects and fixes those cases. Even
9229 * though the regression was for read-only snapshots, this function applies to
9230 * any snapshot/subvolume root.
9231 * This must be run before any other repair code - not doing it so, makes other
9232 * repair code delete or modify backrefs in the extent tree for example, which
9233 * will result in an inconsistent fs after repairing the root items.
9235 static int repair_root_items(struct btrfs_fs_info *info)
9237 struct btrfs_path path;
9238 struct btrfs_key key;
9239 struct extent_buffer *leaf;
9240 struct btrfs_trans_handle *trans = NULL;
9245 btrfs_init_path(&path);
9247 ret = build_roots_info_cache(info);
9251 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
9252 key.type = BTRFS_ROOT_ITEM_KEY;
9257 * Avoid opening and committing transactions if a leaf doesn't have
9258 * any root items that need to be fixed, so that we avoid rotating
9259 * backup roots unnecessarily.
9262 trans = btrfs_start_transaction(info->tree_root, 1);
9263 if (IS_ERR(trans)) {
9264 ret = PTR_ERR(trans);
9269 ret = btrfs_search_slot(trans, info->tree_root, &key, &path,
9273 leaf = path.nodes[0];
9276 struct btrfs_key found_key;
9278 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
9279 int no_more_keys = find_next_key(&path, &key);
9281 btrfs_release_path(&path);
9283 ret = btrfs_commit_transaction(trans,
9295 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
9297 if (found_key.type != BTRFS_ROOT_ITEM_KEY)
9299 if (found_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
9302 ret = maybe_repair_root_item(&path, &found_key, trans ? 0 : 1);
9306 if (!trans && repair) {
9309 btrfs_release_path(&path);
9319 free_roots_info_cache();
9320 btrfs_release_path(&path);
9322 btrfs_commit_transaction(trans, info->tree_root);
9329 static int clear_free_space_cache(struct btrfs_fs_info *fs_info)
9331 struct btrfs_trans_handle *trans;
9332 struct btrfs_block_group_cache *bg_cache;
9336 /* Clear all free space cache inodes and its extent data */
9338 bg_cache = btrfs_lookup_first_block_group(fs_info, current);
9341 ret = btrfs_clear_free_space_cache(fs_info, bg_cache);
9344 current = bg_cache->key.objectid + bg_cache->key.offset;
9347 /* Don't forget to set cache_generation to -1 */
9348 trans = btrfs_start_transaction(fs_info->tree_root, 0);
9349 if (IS_ERR(trans)) {
9350 error("failed to update super block cache generation");
9351 return PTR_ERR(trans);
9353 btrfs_set_super_cache_generation(fs_info->super_copy, (u64)-1);
9354 btrfs_commit_transaction(trans, fs_info->tree_root);
9359 static int do_clear_free_space_cache(struct btrfs_fs_info *fs_info,
9364 if (clear_version == 1) {
9365 if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
9367 "free space cache v2 detected, use --clear-space-cache v2");
9371 printf("Clearing free space cache\n");
9372 ret = clear_free_space_cache(fs_info);
9374 error("failed to clear free space cache");
9377 printf("Free space cache cleared\n");
9379 } else if (clear_version == 2) {
9380 if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
9381 printf("no free space cache v2 to clear\n");
9385 printf("Clear free space cache v2\n");
9386 ret = btrfs_clear_free_space_tree(fs_info);
9388 error("failed to clear free space cache v2: %d", ret);
9391 printf("free space cache v2 cleared\n");
9398 const char * const cmd_check_usage[] = {
9399 "btrfs check [options] <device>",
9400 "Check structural integrity of a filesystem (unmounted).",
9401 "Check structural integrity of an unmounted filesystem. Verify internal",
9402 "trees' consistency and item connectivity. In the repair mode try to",
9403 "fix the problems found. ",
9404 "WARNING: the repair mode is considered dangerous",
9406 "-s|--super <superblock> use this superblock copy",
9407 "-b|--backup use the first valid backup root copy",
9408 "--force skip mount checks, repair is not possible",
9409 "--repair try to repair the filesystem",
9410 "--readonly run in read-only mode (default)",
9411 "--init-csum-tree create a new CRC tree",
9412 "--init-extent-tree create a new extent tree",
9413 "--mode <MODE> allows choice of memory/IO trade-offs",
9414 " where MODE is one of:",
9415 " original - read inodes and extents to memory (requires",
9416 " more memory, does less IO)",
9417 " lowmem - try to use less memory but read blocks again",
9419 "--check-data-csum verify checksums of data blocks",
9420 "-Q|--qgroup-report print a report on qgroup consistency",
9421 "-E|--subvol-extents <subvolid>",
9422 " print subvolume extents and sharing state",
9423 "-r|--tree-root <bytenr> use the given bytenr for the tree root",
9424 "--chunk-root <bytenr> use the given bytenr for the chunk tree root",
9425 "-p|--progress indicate progress",
9426 "--clear-space-cache v1|v2 clear space cache for v1 or v2",
9430 int cmd_check(int argc, char **argv)
9432 struct cache_tree root_cache;
9433 struct btrfs_root *root;
9434 struct btrfs_fs_info *info;
9437 u64 tree_root_bytenr = 0;
9438 u64 chunk_root_bytenr = 0;
9439 char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
9443 int init_csum_tree = 0;
9445 int clear_space_cache = 0;
9446 int qgroup_report = 0;
9447 int qgroups_repaired = 0;
9448 unsigned ctree_flags = OPEN_CTREE_EXCLUSIVE;
9453 enum { GETOPT_VAL_REPAIR = 257, GETOPT_VAL_INIT_CSUM,
9454 GETOPT_VAL_INIT_EXTENT, GETOPT_VAL_CHECK_CSUM,
9455 GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE,
9456 GETOPT_VAL_MODE, GETOPT_VAL_CLEAR_SPACE_CACHE,
9458 static const struct option long_options[] = {
9459 { "super", required_argument, NULL, 's' },
9460 { "repair", no_argument, NULL, GETOPT_VAL_REPAIR },
9461 { "readonly", no_argument, NULL, GETOPT_VAL_READONLY },
9462 { "init-csum-tree", no_argument, NULL,
9463 GETOPT_VAL_INIT_CSUM },
9464 { "init-extent-tree", no_argument, NULL,
9465 GETOPT_VAL_INIT_EXTENT },
9466 { "check-data-csum", no_argument, NULL,
9467 GETOPT_VAL_CHECK_CSUM },
9468 { "backup", no_argument, NULL, 'b' },
9469 { "subvol-extents", required_argument, NULL, 'E' },
9470 { "qgroup-report", no_argument, NULL, 'Q' },
9471 { "tree-root", required_argument, NULL, 'r' },
9472 { "chunk-root", required_argument, NULL,
9473 GETOPT_VAL_CHUNK_TREE },
9474 { "progress", no_argument, NULL, 'p' },
9475 { "mode", required_argument, NULL,
9477 { "clear-space-cache", required_argument, NULL,
9478 GETOPT_VAL_CLEAR_SPACE_CACHE},
9479 { "force", no_argument, NULL, GETOPT_VAL_FORCE },
9483 c = getopt_long(argc, argv, "as:br:pEQ", long_options, NULL);
9487 case 'a': /* ignored */ break;
9489 ctree_flags |= OPEN_CTREE_BACKUP_ROOT;
9492 num = arg_strtou64(optarg);
9493 if (num >= BTRFS_SUPER_MIRROR_MAX) {
9495 "super mirror should be less than %d",
9496 BTRFS_SUPER_MIRROR_MAX);
9499 bytenr = btrfs_sb_offset(((int)num));
9500 printf("using SB copy %llu, bytenr %llu\n", num,
9501 (unsigned long long)bytenr);
9507 subvolid = arg_strtou64(optarg);
9510 tree_root_bytenr = arg_strtou64(optarg);
9512 case GETOPT_VAL_CHUNK_TREE:
9513 chunk_root_bytenr = arg_strtou64(optarg);
9516 ctx.progress_enabled = true;
9520 usage(cmd_check_usage);
9521 case GETOPT_VAL_REPAIR:
9522 printf("enabling repair mode\n");
9524 ctree_flags |= OPEN_CTREE_WRITES;
9526 case GETOPT_VAL_READONLY:
9529 case GETOPT_VAL_INIT_CSUM:
9530 printf("Creating a new CRC tree\n");
9533 ctree_flags |= OPEN_CTREE_WRITES;
9535 case GETOPT_VAL_INIT_EXTENT:
9536 init_extent_tree = 1;
9537 ctree_flags |= (OPEN_CTREE_WRITES |
9538 OPEN_CTREE_NO_BLOCK_GROUPS);
9541 case GETOPT_VAL_CHECK_CSUM:
9542 check_data_csum = 1;
9544 case GETOPT_VAL_MODE:
9545 check_mode = parse_check_mode(optarg);
9546 if (check_mode == CHECK_MODE_UNKNOWN) {
9547 error("unknown mode: %s", optarg);
9551 case GETOPT_VAL_CLEAR_SPACE_CACHE:
9552 if (strcmp(optarg, "v1") == 0) {
9553 clear_space_cache = 1;
9554 } else if (strcmp(optarg, "v2") == 0) {
9555 clear_space_cache = 2;
9556 ctree_flags |= OPEN_CTREE_INVALIDATE_FST;
9559 "invalid argument to --clear-space-cache, must be v1 or v2");
9562 ctree_flags |= OPEN_CTREE_WRITES;
9564 case GETOPT_VAL_FORCE:
9570 if (check_argc_exact(argc - optind, 1))
9571 usage(cmd_check_usage);
9573 if (ctx.progress_enabled) {
9574 ctx.tp = TASK_NOTHING;
9575 ctx.info = task_init(print_status_check, print_status_return, &ctx);
9578 /* This check is the only reason for --readonly to exist */
9579 if (readonly && repair) {
9580 error("repair options are not compatible with --readonly");
9585 * experimental and dangerous
9587 if (repair && check_mode == CHECK_MODE_LOWMEM)
9588 warning("low-memory mode repair support is only partial");
9591 cache_tree_init(&root_cache);
9593 ret = check_mounted(argv[optind]);
9596 error("could not check mount status: %s",
9602 "%s is currently mounted, use --force if you really intend to check the filesystem",
9610 error("repair and --force is not yet supported");
9617 "cannot check mount status of %s, the filesystem could be mounted, continuing because of --force",
9621 "filesystem mounted, continuing because of --force");
9623 /* A block device is mounted in exclusive mode by kernel */
9624 ctree_flags &= ~OPEN_CTREE_EXCLUSIVE;
9627 /* only allow partial opening under repair mode */
9629 ctree_flags |= OPEN_CTREE_PARTIAL;
9631 info = open_ctree_fs_info(argv[optind], bytenr, tree_root_bytenr,
9632 chunk_root_bytenr, ctree_flags);
9634 error("cannot open file system");
9641 root = info->fs_root;
9642 uuid_unparse(info->super_copy->fsid, uuidbuf);
9644 printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
9647 * Check the bare minimum before starting anything else that could rely
9648 * on it, namely the tree roots, any local consistency checks
9650 if (!extent_buffer_uptodate(info->tree_root->node) ||
9651 !extent_buffer_uptodate(info->dev_root->node) ||
9652 !extent_buffer_uptodate(info->chunk_root->node)) {
9653 error("critical roots corrupted, unable to check the filesystem");
9659 if (clear_space_cache) {
9660 ret = do_clear_free_space_cache(info, clear_space_cache);
9666 * repair mode will force us to commit transaction which
9667 * will make us fail to load log tree when mounting.
9669 if (repair && btrfs_super_log_root(info->super_copy)) {
9670 ret = ask_user("repair mode will force to clear out log tree, are you sure?");
9676 ret = zero_log_tree(root);
9679 error("failed to zero log tree: %d", ret);
9684 if (qgroup_report) {
9685 printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
9687 ret = qgroup_verify_all(info);
9694 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
9695 subvolid, argv[optind], uuidbuf);
9696 ret = print_extent_state(info, subvolid);
9701 if (init_extent_tree || init_csum_tree) {
9702 struct btrfs_trans_handle *trans;
9704 trans = btrfs_start_transaction(info->extent_root, 0);
9705 if (IS_ERR(trans)) {
9706 error("error starting transaction");
9707 ret = PTR_ERR(trans);
9712 if (init_extent_tree) {
9713 printf("Creating a new extent tree\n");
9714 ret = reinit_extent_tree(trans, info);
9720 if (init_csum_tree) {
9721 printf("Reinitialize checksum tree\n");
9722 ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0);
9724 error("checksum tree initialization failed: %d",
9731 ret = fill_csum_tree(trans, info->csum_root,
9735 error("checksum tree refilling failed: %d", ret);
9740 * Ok now we commit and run the normal fsck, which will add
9741 * extent entries for all of the items it finds.
9743 ret = btrfs_commit_transaction(trans, info->extent_root);
9748 if (!extent_buffer_uptodate(info->extent_root->node)) {
9749 error("critical: extent_root, unable to check the filesystem");
9754 if (!extent_buffer_uptodate(info->csum_root->node)) {
9755 error("critical: csum_root, unable to check the filesystem");
9761 if (!init_extent_tree) {
9762 ret = repair_root_items(info);
9765 error("failed to repair root items: %s", strerror(-ret));
9769 fprintf(stderr, "Fixed %d roots.\n", ret);
9771 } else if (ret > 0) {
9773 "Found %d roots with an outdated root item.\n",
9776 "Please run a filesystem check with the option --repair to fix them.\n");
9783 ret = do_check_chunks_and_extents(info);
9787 "errors found in extent allocation tree or chunk allocation");
9789 /* Only re-check super size after we checked and repaired the fs */
9790 err |= !is_super_size_valid(info);
9792 if (!ctx.progress_enabled) {
9793 if (btrfs_fs_compat_ro(info, FREE_SPACE_TREE))
9794 fprintf(stderr, "checking free space tree\n");
9796 fprintf(stderr, "checking free space cache\n");
9798 ret = check_space_cache(root);
9801 if (btrfs_fs_compat_ro(info, FREE_SPACE_TREE))
9802 error("errors found in free space tree");
9804 error("errors found in free space cache");
9809 * We used to have to have these hole extents in between our real
9810 * extents so if we don't have this flag set we need to make sure there
9811 * are no gaps in the file extents for inodes, otherwise we can just
9812 * ignore it when this happens.
9814 no_holes = btrfs_fs_incompat(root->fs_info, NO_HOLES);
9815 ret = do_check_fs_roots(info, &root_cache);
9818 error("errors found in fs roots");
9822 fprintf(stderr, "checking csums\n");
9823 ret = check_csums(root);
9826 error("errors found in csum tree");
9830 fprintf(stderr, "checking root refs\n");
9831 /* For low memory mode, check_fs_roots_v2 handles root refs */
9832 if (check_mode != CHECK_MODE_LOWMEM) {
9833 ret = check_root_refs(root, &root_cache);
9836 error("errors found in root refs");
9841 while (repair && !list_empty(&root->fs_info->recow_ebs)) {
9842 struct extent_buffer *eb;
9844 eb = list_first_entry(&root->fs_info->recow_ebs,
9845 struct extent_buffer, recow);
9846 list_del_init(&eb->recow);
9847 ret = recow_extent_buffer(root, eb);
9850 error("fails to fix transid errors");
9855 while (!list_empty(&delete_items)) {
9856 struct bad_item *bad;
9858 bad = list_first_entry(&delete_items, struct bad_item, list);
9859 list_del_init(&bad->list);
9861 ret = delete_bad_item(root, bad);
9867 if (info->quota_enabled) {
9868 fprintf(stderr, "checking quota groups\n");
9869 ret = qgroup_verify_all(info);
9872 error("failed to check quota groups");
9876 ret = repair_qgroups(info, &qgroups_repaired);
9879 error("failed to repair quota groups");
9885 if (!list_empty(&root->fs_info->recow_ebs)) {
9886 error("transid errors in file system");
9891 printf("found %llu bytes used, ",
9892 (unsigned long long)bytes_used);
9894 printf("error(s) found\n");
9896 printf("no error found\n");
9897 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
9898 printf("total tree bytes: %llu\n",
9899 (unsigned long long)total_btree_bytes);
9900 printf("total fs tree bytes: %llu\n",
9901 (unsigned long long)total_fs_tree_bytes);
9902 printf("total extent tree bytes: %llu\n",
9903 (unsigned long long)total_extent_tree_bytes);
9904 printf("btree space waste bytes: %llu\n",
9905 (unsigned long long)btree_space_waste);
9906 printf("file data blocks allocated: %llu\n referenced %llu\n",
9907 (unsigned long long)data_bytes_allocated,
9908 (unsigned long long)data_bytes_referenced);
9910 free_qgroup_counts();
9911 free_root_recs_tree(&root_cache);
9915 if (ctx.progress_enabled)
9916 task_deinit(ctx.info);