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"
49 TASK_NOTHING, /* have to be the last element */
54 enum task_position tp;
56 struct task_info *info;
59 static u64 bytes_used = 0;
60 static u64 total_csum_bytes = 0;
61 static u64 total_btree_bytes = 0;
62 static u64 total_fs_tree_bytes = 0;
63 static u64 total_extent_tree_bytes = 0;
64 static u64 btree_space_waste = 0;
65 static u64 data_bytes_allocated = 0;
66 static u64 data_bytes_referenced = 0;
67 static int found_old_backref = 0;
68 static LIST_HEAD(duplicate_extents);
69 static LIST_HEAD(delete_items);
70 static int repair = 0;
71 static int no_holes = 0;
72 static int init_extent_tree = 0;
73 static int check_data_csum = 0;
74 static struct btrfs_fs_info *global_info;
75 static struct task_ctx ctx = { 0 };
76 static struct cache_tree *roots_info_cache = NULL;
78 struct extent_backref {
79 struct list_head list;
80 unsigned int is_data:1;
81 unsigned int found_extent_tree:1;
82 unsigned int full_backref:1;
83 unsigned int found_ref:1;
84 unsigned int broken:1;
88 struct extent_backref node;
103 * Much like data_backref, just removed the undetermined members
104 * and change it to use list_head.
105 * During extent scan, it is stored in root->orphan_data_extent.
106 * During fs tree scan, it is then moved to inode_rec->orphan_data_extents.
108 struct orphan_data_extent {
109 struct list_head list;
117 struct tree_backref {
118 struct extent_backref node;
125 struct extent_record {
126 struct list_head backrefs;
127 struct list_head dups;
128 struct list_head list;
129 struct cache_extent cache;
130 struct btrfs_disk_key parent_key;
135 u64 extent_item_refs;
137 u64 parent_generation;
141 int flag_block_full_backref;
142 unsigned int found_rec:1;
143 unsigned int content_checked:1;
144 unsigned int owner_ref_checked:1;
145 unsigned int is_root:1;
146 unsigned int metadata:1;
147 unsigned int bad_full_backref:1;
148 unsigned int crossing_stripes:1;
149 unsigned int wrong_chunk_type:1;
152 struct inode_backref {
153 struct list_head list;
154 unsigned int found_dir_item:1;
155 unsigned int found_dir_index:1;
156 unsigned int found_inode_ref:1;
157 unsigned int filetype:8;
159 unsigned int ref_type;
166 struct root_item_record {
167 struct list_head list;
174 struct btrfs_key drop_key;
177 #define REF_ERR_NO_DIR_ITEM (1 << 0)
178 #define REF_ERR_NO_DIR_INDEX (1 << 1)
179 #define REF_ERR_NO_INODE_REF (1 << 2)
180 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
181 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
182 #define REF_ERR_DUP_INODE_REF (1 << 5)
183 #define REF_ERR_INDEX_UNMATCH (1 << 6)
184 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
185 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
186 #define REF_ERR_NO_ROOT_REF (1 << 9)
187 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
188 #define REF_ERR_DUP_ROOT_REF (1 << 11)
189 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
191 struct file_extent_hole {
197 struct inode_record {
198 struct list_head backrefs;
199 unsigned int checked:1;
200 unsigned int merging:1;
201 unsigned int found_inode_item:1;
202 unsigned int found_dir_item:1;
203 unsigned int found_file_extent:1;
204 unsigned int found_csum_item:1;
205 unsigned int some_csum_missing:1;
206 unsigned int nodatasum:1;
219 struct rb_root holes;
220 struct list_head orphan_extents;
225 #define I_ERR_NO_INODE_ITEM (1 << 0)
226 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
227 #define I_ERR_DUP_INODE_ITEM (1 << 2)
228 #define I_ERR_DUP_DIR_INDEX (1 << 3)
229 #define I_ERR_ODD_DIR_ITEM (1 << 4)
230 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
231 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
232 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
233 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
234 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
235 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
236 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
237 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
238 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
239 #define I_ERR_FILE_EXTENT_ORPHAN (1 << 14)
241 struct root_backref {
242 struct list_head list;
243 unsigned int found_dir_item:1;
244 unsigned int found_dir_index:1;
245 unsigned int found_back_ref:1;
246 unsigned int found_forward_ref:1;
247 unsigned int reachable:1;
257 struct list_head backrefs;
258 struct cache_extent cache;
259 unsigned int found_root_item:1;
265 struct cache_extent cache;
270 struct cache_extent cache;
271 struct cache_tree root_cache;
272 struct cache_tree inode_cache;
273 struct inode_record *current;
282 struct walk_control {
283 struct cache_tree shared;
284 struct shared_node *nodes[BTRFS_MAX_LEVEL];
290 struct btrfs_key key;
292 struct list_head list;
295 struct extent_entry {
300 struct list_head list;
303 struct root_item_info {
304 /* level of the root */
306 /* number of nodes at this level, must be 1 for a root */
310 struct cache_extent cache_extent;
313 static void *print_status_check(void *p)
315 struct task_ctx *priv = p;
316 const char work_indicator[] = { '.', 'o', 'O', 'o' };
318 static char *task_position_string[] = {
320 "checking free space cache",
324 task_period_start(priv->info, 1000 /* 1s */);
326 if (priv->tp == TASK_NOTHING)
330 printf("%s [%c]\r", task_position_string[priv->tp],
331 work_indicator[count % 4]);
334 task_period_wait(priv->info);
339 static int print_status_return(void *p)
347 /* Compatible function to allow reuse of old codes */
348 static u64 first_extent_gap(struct rb_root *holes)
350 struct file_extent_hole *hole;
352 if (RB_EMPTY_ROOT(holes))
355 hole = rb_entry(rb_first(holes), struct file_extent_hole, node);
359 static int compare_hole(struct rb_node *node1, struct rb_node *node2)
361 struct file_extent_hole *hole1;
362 struct file_extent_hole *hole2;
364 hole1 = rb_entry(node1, struct file_extent_hole, node);
365 hole2 = rb_entry(node2, struct file_extent_hole, node);
367 if (hole1->start > hole2->start)
369 if (hole1->start < hole2->start)
371 /* Now hole1->start == hole2->start */
372 if (hole1->len >= hole2->len)
374 * Hole 1 will be merge center
375 * Same hole will be merged later
378 /* Hole 2 will be merge center */
383 * Add a hole to the record
385 * This will do hole merge for copy_file_extent_holes(),
386 * which will ensure there won't be continuous holes.
388 static int add_file_extent_hole(struct rb_root *holes,
391 struct file_extent_hole *hole;
392 struct file_extent_hole *prev = NULL;
393 struct file_extent_hole *next = NULL;
395 hole = malloc(sizeof(*hole));
400 /* Since compare will not return 0, no -EEXIST will happen */
401 rb_insert(holes, &hole->node, compare_hole);
403 /* simple merge with previous hole */
404 if (rb_prev(&hole->node))
405 prev = rb_entry(rb_prev(&hole->node), struct file_extent_hole,
407 if (prev && prev->start + prev->len >= hole->start) {
408 hole->len = hole->start + hole->len - prev->start;
409 hole->start = prev->start;
410 rb_erase(&prev->node, holes);
415 /* iterate merge with next holes */
417 if (!rb_next(&hole->node))
419 next = rb_entry(rb_next(&hole->node), struct file_extent_hole,
421 if (hole->start + hole->len >= next->start) {
422 if (hole->start + hole->len <= next->start + next->len)
423 hole->len = next->start + next->len -
425 rb_erase(&next->node, holes);
434 static int compare_hole_range(struct rb_node *node, void *data)
436 struct file_extent_hole *hole;
439 hole = (struct file_extent_hole *)data;
442 hole = rb_entry(node, struct file_extent_hole, node);
443 if (start < hole->start)
445 if (start >= hole->start && start < hole->start + hole->len)
451 * Delete a hole in the record
453 * This will do the hole split and is much restrict than add.
455 static int del_file_extent_hole(struct rb_root *holes,
458 struct file_extent_hole *hole;
459 struct file_extent_hole tmp;
464 struct rb_node *node;
471 node = rb_search(holes, &tmp, compare_hole_range, NULL);
474 hole = rb_entry(node, struct file_extent_hole, node);
475 if (start + len > hole->start + hole->len)
479 * Now there will be no overflap, delete the hole and re-add the
480 * split(s) if they exists.
482 if (start > hole->start) {
483 prev_start = hole->start;
484 prev_len = start - hole->start;
487 if (hole->start + hole->len > start + len) {
488 next_start = start + len;
489 next_len = hole->start + hole->len - start - len;
492 rb_erase(node, holes);
495 ret = add_file_extent_hole(holes, prev_start, prev_len);
500 ret = add_file_extent_hole(holes, next_start, next_len);
507 static int copy_file_extent_holes(struct rb_root *dst,
510 struct file_extent_hole *hole;
511 struct rb_node *node;
514 node = rb_first(src);
516 hole = rb_entry(node, struct file_extent_hole, node);
517 ret = add_file_extent_hole(dst, hole->start, hole->len);
520 node = rb_next(node);
525 static void free_file_extent_holes(struct rb_root *holes)
527 struct rb_node *node;
528 struct file_extent_hole *hole;
530 node = rb_first(holes);
532 hole = rb_entry(node, struct file_extent_hole, node);
533 rb_erase(node, holes);
535 node = rb_first(holes);
539 static void reset_cached_block_groups(struct btrfs_fs_info *fs_info);
541 static void record_root_in_trans(struct btrfs_trans_handle *trans,
542 struct btrfs_root *root)
544 if (root->last_trans != trans->transid) {
545 root->track_dirty = 1;
546 root->last_trans = trans->transid;
547 root->commit_root = root->node;
548 extent_buffer_get(root->node);
552 static u8 imode_to_type(u32 imode)
555 static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
556 [S_IFREG >> S_SHIFT] = BTRFS_FT_REG_FILE,
557 [S_IFDIR >> S_SHIFT] = BTRFS_FT_DIR,
558 [S_IFCHR >> S_SHIFT] = BTRFS_FT_CHRDEV,
559 [S_IFBLK >> S_SHIFT] = BTRFS_FT_BLKDEV,
560 [S_IFIFO >> S_SHIFT] = BTRFS_FT_FIFO,
561 [S_IFSOCK >> S_SHIFT] = BTRFS_FT_SOCK,
562 [S_IFLNK >> S_SHIFT] = BTRFS_FT_SYMLINK,
565 return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
569 static int device_record_compare(struct rb_node *node1, struct rb_node *node2)
571 struct device_record *rec1;
572 struct device_record *rec2;
574 rec1 = rb_entry(node1, struct device_record, node);
575 rec2 = rb_entry(node2, struct device_record, node);
576 if (rec1->devid > rec2->devid)
578 else if (rec1->devid < rec2->devid)
584 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
586 struct inode_record *rec;
587 struct inode_backref *backref;
588 struct inode_backref *orig;
589 struct inode_backref *tmp;
590 struct orphan_data_extent *src_orphan;
591 struct orphan_data_extent *dst_orphan;
595 rec = malloc(sizeof(*rec));
597 return ERR_PTR(-ENOMEM);
598 memcpy(rec, orig_rec, sizeof(*rec));
600 INIT_LIST_HEAD(&rec->backrefs);
601 INIT_LIST_HEAD(&rec->orphan_extents);
602 rec->holes = RB_ROOT;
604 list_for_each_entry(orig, &orig_rec->backrefs, list) {
605 size = sizeof(*orig) + orig->namelen + 1;
606 backref = malloc(size);
611 memcpy(backref, orig, size);
612 list_add_tail(&backref->list, &rec->backrefs);
614 list_for_each_entry(src_orphan, &orig_rec->orphan_extents, list) {
615 dst_orphan = malloc(sizeof(*dst_orphan));
620 memcpy(dst_orphan, src_orphan, sizeof(*src_orphan));
621 list_add_tail(&dst_orphan->list, &rec->orphan_extents);
623 ret = copy_file_extent_holes(&rec->holes, &orig_rec->holes);
629 if (!list_empty(&rec->backrefs))
630 list_for_each_entry_safe(orig, tmp, &rec->backrefs, list) {
631 list_del(&orig->list);
635 if (!list_empty(&rec->orphan_extents))
636 list_for_each_entry_safe(orig, tmp, &rec->orphan_extents, list) {
637 list_del(&orig->list);
646 static void print_orphan_data_extents(struct list_head *orphan_extents,
649 struct orphan_data_extent *orphan;
651 if (list_empty(orphan_extents))
653 printf("The following data extent is lost in tree %llu:\n",
655 list_for_each_entry(orphan, orphan_extents, list) {
656 printf("\tinode: %llu, offset:%llu, disk_bytenr: %llu, disk_len: %llu\n",
657 orphan->objectid, orphan->offset, orphan->disk_bytenr,
662 static void print_inode_error(struct btrfs_root *root, struct inode_record *rec)
664 u64 root_objectid = root->root_key.objectid;
665 int errors = rec->errors;
669 /* reloc root errors, we print its corresponding fs root objectid*/
670 if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
671 root_objectid = root->root_key.offset;
672 fprintf(stderr, "reloc");
674 fprintf(stderr, "root %llu inode %llu errors %x",
675 (unsigned long long) root_objectid,
676 (unsigned long long) rec->ino, rec->errors);
678 if (errors & I_ERR_NO_INODE_ITEM)
679 fprintf(stderr, ", no inode item");
680 if (errors & I_ERR_NO_ORPHAN_ITEM)
681 fprintf(stderr, ", no orphan item");
682 if (errors & I_ERR_DUP_INODE_ITEM)
683 fprintf(stderr, ", dup inode item");
684 if (errors & I_ERR_DUP_DIR_INDEX)
685 fprintf(stderr, ", dup dir index");
686 if (errors & I_ERR_ODD_DIR_ITEM)
687 fprintf(stderr, ", odd dir item");
688 if (errors & I_ERR_ODD_FILE_EXTENT)
689 fprintf(stderr, ", odd file extent");
690 if (errors & I_ERR_BAD_FILE_EXTENT)
691 fprintf(stderr, ", bad file extent");
692 if (errors & I_ERR_FILE_EXTENT_OVERLAP)
693 fprintf(stderr, ", file extent overlap");
694 if (errors & I_ERR_FILE_EXTENT_DISCOUNT)
695 fprintf(stderr, ", file extent discount");
696 if (errors & I_ERR_DIR_ISIZE_WRONG)
697 fprintf(stderr, ", dir isize wrong");
698 if (errors & I_ERR_FILE_NBYTES_WRONG)
699 fprintf(stderr, ", nbytes wrong");
700 if (errors & I_ERR_ODD_CSUM_ITEM)
701 fprintf(stderr, ", odd csum item");
702 if (errors & I_ERR_SOME_CSUM_MISSING)
703 fprintf(stderr, ", some csum missing");
704 if (errors & I_ERR_LINK_COUNT_WRONG)
705 fprintf(stderr, ", link count wrong");
706 if (errors & I_ERR_FILE_EXTENT_ORPHAN)
707 fprintf(stderr, ", orphan file extent");
708 fprintf(stderr, "\n");
709 /* Print the orphan extents if needed */
710 if (errors & I_ERR_FILE_EXTENT_ORPHAN)
711 print_orphan_data_extents(&rec->orphan_extents, root->objectid);
713 /* Print the holes if needed */
714 if (errors & I_ERR_FILE_EXTENT_DISCOUNT) {
715 struct file_extent_hole *hole;
716 struct rb_node *node;
719 node = rb_first(&rec->holes);
720 fprintf(stderr, "Found file extent holes:\n");
723 hole = rb_entry(node, struct file_extent_hole, node);
724 fprintf(stderr, "\tstart: %llu, len: %llu\n",
725 hole->start, hole->len);
726 node = rb_next(node);
729 fprintf(stderr, "\tstart: 0, len: %llu\n",
730 round_up(rec->isize, root->sectorsize));
734 static void print_ref_error(int errors)
736 if (errors & REF_ERR_NO_DIR_ITEM)
737 fprintf(stderr, ", no dir item");
738 if (errors & REF_ERR_NO_DIR_INDEX)
739 fprintf(stderr, ", no dir index");
740 if (errors & REF_ERR_NO_INODE_REF)
741 fprintf(stderr, ", no inode ref");
742 if (errors & REF_ERR_DUP_DIR_ITEM)
743 fprintf(stderr, ", dup dir item");
744 if (errors & REF_ERR_DUP_DIR_INDEX)
745 fprintf(stderr, ", dup dir index");
746 if (errors & REF_ERR_DUP_INODE_REF)
747 fprintf(stderr, ", dup inode ref");
748 if (errors & REF_ERR_INDEX_UNMATCH)
749 fprintf(stderr, ", index unmatch");
750 if (errors & REF_ERR_FILETYPE_UNMATCH)
751 fprintf(stderr, ", filetype unmatch");
752 if (errors & REF_ERR_NAME_TOO_LONG)
753 fprintf(stderr, ", name too long");
754 if (errors & REF_ERR_NO_ROOT_REF)
755 fprintf(stderr, ", no root ref");
756 if (errors & REF_ERR_NO_ROOT_BACKREF)
757 fprintf(stderr, ", no root backref");
758 if (errors & REF_ERR_DUP_ROOT_REF)
759 fprintf(stderr, ", dup root ref");
760 if (errors & REF_ERR_DUP_ROOT_BACKREF)
761 fprintf(stderr, ", dup root backref");
762 fprintf(stderr, "\n");
765 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
768 struct ptr_node *node;
769 struct cache_extent *cache;
770 struct inode_record *rec = NULL;
773 cache = lookup_cache_extent(inode_cache, ino, 1);
775 node = container_of(cache, struct ptr_node, cache);
777 if (mod && rec->refs > 1) {
778 node->data = clone_inode_rec(rec);
779 if (IS_ERR(node->data))
785 rec = calloc(1, sizeof(*rec));
787 return ERR_PTR(-ENOMEM);
789 rec->extent_start = (u64)-1;
791 INIT_LIST_HEAD(&rec->backrefs);
792 INIT_LIST_HEAD(&rec->orphan_extents);
793 rec->holes = RB_ROOT;
795 node = malloc(sizeof(*node));
798 return ERR_PTR(-ENOMEM);
800 node->cache.start = ino;
801 node->cache.size = 1;
804 if (ino == BTRFS_FREE_INO_OBJECTID)
807 ret = insert_cache_extent(inode_cache, &node->cache);
809 return ERR_PTR(-EEXIST);
814 static void free_orphan_data_extents(struct list_head *orphan_extents)
816 struct orphan_data_extent *orphan;
818 while (!list_empty(orphan_extents)) {
819 orphan = list_entry(orphan_extents->next,
820 struct orphan_data_extent, list);
821 list_del(&orphan->list);
826 static void free_inode_rec(struct inode_record *rec)
828 struct inode_backref *backref;
833 while (!list_empty(&rec->backrefs)) {
834 backref = list_entry(rec->backrefs.next,
835 struct inode_backref, list);
836 list_del(&backref->list);
839 free_orphan_data_extents(&rec->orphan_extents);
840 free_file_extent_holes(&rec->holes);
844 static int can_free_inode_rec(struct inode_record *rec)
846 if (!rec->errors && rec->checked && rec->found_inode_item &&
847 rec->nlink == rec->found_link && list_empty(&rec->backrefs))
852 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
853 struct inode_record *rec)
855 struct cache_extent *cache;
856 struct inode_backref *tmp, *backref;
857 struct ptr_node *node;
858 unsigned char filetype;
860 if (!rec->found_inode_item)
863 filetype = imode_to_type(rec->imode);
864 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
865 if (backref->found_dir_item && backref->found_dir_index) {
866 if (backref->filetype != filetype)
867 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
868 if (!backref->errors && backref->found_inode_ref &&
869 rec->nlink == rec->found_link) {
870 list_del(&backref->list);
876 if (!rec->checked || rec->merging)
879 if (S_ISDIR(rec->imode)) {
880 if (rec->found_size != rec->isize)
881 rec->errors |= I_ERR_DIR_ISIZE_WRONG;
882 if (rec->found_file_extent)
883 rec->errors |= I_ERR_ODD_FILE_EXTENT;
884 } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
885 if (rec->found_dir_item)
886 rec->errors |= I_ERR_ODD_DIR_ITEM;
887 if (rec->found_size != rec->nbytes)
888 rec->errors |= I_ERR_FILE_NBYTES_WRONG;
889 if (rec->nlink > 0 && !no_holes &&
890 (rec->extent_end < rec->isize ||
891 first_extent_gap(&rec->holes) < rec->isize))
892 rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
895 if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
896 if (rec->found_csum_item && rec->nodatasum)
897 rec->errors |= I_ERR_ODD_CSUM_ITEM;
898 if (rec->some_csum_missing && !rec->nodatasum)
899 rec->errors |= I_ERR_SOME_CSUM_MISSING;
902 BUG_ON(rec->refs != 1);
903 if (can_free_inode_rec(rec)) {
904 cache = lookup_cache_extent(inode_cache, rec->ino, 1);
905 node = container_of(cache, struct ptr_node, cache);
906 BUG_ON(node->data != rec);
907 remove_cache_extent(inode_cache, &node->cache);
913 static int check_orphan_item(struct btrfs_root *root, u64 ino)
915 struct btrfs_path path;
916 struct btrfs_key key;
919 key.objectid = BTRFS_ORPHAN_OBJECTID;
920 key.type = BTRFS_ORPHAN_ITEM_KEY;
923 btrfs_init_path(&path);
924 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
925 btrfs_release_path(&path);
931 static int process_inode_item(struct extent_buffer *eb,
932 int slot, struct btrfs_key *key,
933 struct shared_node *active_node)
935 struct inode_record *rec;
936 struct btrfs_inode_item *item;
938 rec = active_node->current;
939 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
940 if (rec->found_inode_item) {
941 rec->errors |= I_ERR_DUP_INODE_ITEM;
944 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
945 rec->nlink = btrfs_inode_nlink(eb, item);
946 rec->isize = btrfs_inode_size(eb, item);
947 rec->nbytes = btrfs_inode_nbytes(eb, item);
948 rec->imode = btrfs_inode_mode(eb, item);
949 if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
951 rec->found_inode_item = 1;
953 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
954 maybe_free_inode_rec(&active_node->inode_cache, rec);
958 static struct inode_backref *get_inode_backref(struct inode_record *rec,
960 int namelen, u64 dir)
962 struct inode_backref *backref;
964 list_for_each_entry(backref, &rec->backrefs, list) {
965 if (rec->ino == BTRFS_MULTIPLE_OBJECTIDS)
967 if (backref->dir != dir || backref->namelen != namelen)
969 if (memcmp(name, backref->name, namelen))
974 backref = malloc(sizeof(*backref) + namelen + 1);
977 memset(backref, 0, sizeof(*backref));
979 backref->namelen = namelen;
980 memcpy(backref->name, name, namelen);
981 backref->name[namelen] = '\0';
982 list_add_tail(&backref->list, &rec->backrefs);
986 static int add_inode_backref(struct cache_tree *inode_cache,
987 u64 ino, u64 dir, u64 index,
988 const char *name, int namelen,
989 int filetype, int itemtype, int errors)
991 struct inode_record *rec;
992 struct inode_backref *backref;
994 rec = get_inode_rec(inode_cache, ino, 1);
996 backref = get_inode_backref(rec, name, namelen, dir);
999 backref->errors |= errors;
1000 if (itemtype == BTRFS_DIR_INDEX_KEY) {
1001 if (backref->found_dir_index)
1002 backref->errors |= REF_ERR_DUP_DIR_INDEX;
1003 if (backref->found_inode_ref && backref->index != index)
1004 backref->errors |= REF_ERR_INDEX_UNMATCH;
1005 if (backref->found_dir_item && backref->filetype != filetype)
1006 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
1008 backref->index = index;
1009 backref->filetype = filetype;
1010 backref->found_dir_index = 1;
1011 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
1013 if (backref->found_dir_item)
1014 backref->errors |= REF_ERR_DUP_DIR_ITEM;
1015 if (backref->found_dir_index && backref->filetype != filetype)
1016 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
1018 backref->filetype = filetype;
1019 backref->found_dir_item = 1;
1020 } else if ((itemtype == BTRFS_INODE_REF_KEY) ||
1021 (itemtype == BTRFS_INODE_EXTREF_KEY)) {
1022 if (backref->found_inode_ref)
1023 backref->errors |= REF_ERR_DUP_INODE_REF;
1024 if (backref->found_dir_index && backref->index != index)
1025 backref->errors |= REF_ERR_INDEX_UNMATCH;
1027 backref->index = index;
1029 backref->ref_type = itemtype;
1030 backref->found_inode_ref = 1;
1035 maybe_free_inode_rec(inode_cache, rec);
1039 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
1040 struct cache_tree *dst_cache)
1042 struct inode_backref *backref;
1047 list_for_each_entry(backref, &src->backrefs, list) {
1048 if (backref->found_dir_index) {
1049 add_inode_backref(dst_cache, dst->ino, backref->dir,
1050 backref->index, backref->name,
1051 backref->namelen, backref->filetype,
1052 BTRFS_DIR_INDEX_KEY, backref->errors);
1054 if (backref->found_dir_item) {
1056 add_inode_backref(dst_cache, dst->ino,
1057 backref->dir, 0, backref->name,
1058 backref->namelen, backref->filetype,
1059 BTRFS_DIR_ITEM_KEY, backref->errors);
1061 if (backref->found_inode_ref) {
1062 add_inode_backref(dst_cache, dst->ino,
1063 backref->dir, backref->index,
1064 backref->name, backref->namelen, 0,
1065 backref->ref_type, backref->errors);
1069 if (src->found_dir_item)
1070 dst->found_dir_item = 1;
1071 if (src->found_file_extent)
1072 dst->found_file_extent = 1;
1073 if (src->found_csum_item)
1074 dst->found_csum_item = 1;
1075 if (src->some_csum_missing)
1076 dst->some_csum_missing = 1;
1077 if (first_extent_gap(&dst->holes) > first_extent_gap(&src->holes)) {
1078 ret = copy_file_extent_holes(&dst->holes, &src->holes);
1083 BUG_ON(src->found_link < dir_count);
1084 dst->found_link += src->found_link - dir_count;
1085 dst->found_size += src->found_size;
1086 if (src->extent_start != (u64)-1) {
1087 if (dst->extent_start == (u64)-1) {
1088 dst->extent_start = src->extent_start;
1089 dst->extent_end = src->extent_end;
1091 if (dst->extent_end > src->extent_start)
1092 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
1093 else if (dst->extent_end < src->extent_start) {
1094 ret = add_file_extent_hole(&dst->holes,
1096 src->extent_start - dst->extent_end);
1098 if (dst->extent_end < src->extent_end)
1099 dst->extent_end = src->extent_end;
1103 dst->errors |= src->errors;
1104 if (src->found_inode_item) {
1105 if (!dst->found_inode_item) {
1106 dst->nlink = src->nlink;
1107 dst->isize = src->isize;
1108 dst->nbytes = src->nbytes;
1109 dst->imode = src->imode;
1110 dst->nodatasum = src->nodatasum;
1111 dst->found_inode_item = 1;
1113 dst->errors |= I_ERR_DUP_INODE_ITEM;
1121 static int splice_shared_node(struct shared_node *src_node,
1122 struct shared_node *dst_node)
1124 struct cache_extent *cache;
1125 struct ptr_node *node, *ins;
1126 struct cache_tree *src, *dst;
1127 struct inode_record *rec, *conflict;
1128 u64 current_ino = 0;
1132 if (--src_node->refs == 0)
1134 if (src_node->current)
1135 current_ino = src_node->current->ino;
1137 src = &src_node->root_cache;
1138 dst = &dst_node->root_cache;
1140 cache = search_cache_extent(src, 0);
1142 node = container_of(cache, struct ptr_node, cache);
1144 cache = next_cache_extent(cache);
1147 remove_cache_extent(src, &node->cache);
1150 ins = malloc(sizeof(*ins));
1152 ins->cache.start = node->cache.start;
1153 ins->cache.size = node->cache.size;
1157 ret = insert_cache_extent(dst, &ins->cache);
1158 if (ret == -EEXIST) {
1159 conflict = get_inode_rec(dst, rec->ino, 1);
1160 BUG_ON(IS_ERR(conflict));
1161 merge_inode_recs(rec, conflict, dst);
1163 conflict->checked = 1;
1164 if (dst_node->current == conflict)
1165 dst_node->current = NULL;
1167 maybe_free_inode_rec(dst, conflict);
1168 free_inode_rec(rec);
1175 if (src == &src_node->root_cache) {
1176 src = &src_node->inode_cache;
1177 dst = &dst_node->inode_cache;
1181 if (current_ino > 0 && (!dst_node->current ||
1182 current_ino > dst_node->current->ino)) {
1183 if (dst_node->current) {
1184 dst_node->current->checked = 1;
1185 maybe_free_inode_rec(dst, dst_node->current);
1187 dst_node->current = get_inode_rec(dst, current_ino, 1);
1188 BUG_ON(IS_ERR(dst_node->current));
1193 static void free_inode_ptr(struct cache_extent *cache)
1195 struct ptr_node *node;
1196 struct inode_record *rec;
1198 node = container_of(cache, struct ptr_node, cache);
1200 free_inode_rec(rec);
1204 FREE_EXTENT_CACHE_BASED_TREE(inode_recs, free_inode_ptr);
1206 static struct shared_node *find_shared_node(struct cache_tree *shared,
1209 struct cache_extent *cache;
1210 struct shared_node *node;
1212 cache = lookup_cache_extent(shared, bytenr, 1);
1214 node = container_of(cache, struct shared_node, cache);
1220 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
1223 struct shared_node *node;
1225 node = calloc(1, sizeof(*node));
1228 node->cache.start = bytenr;
1229 node->cache.size = 1;
1230 cache_tree_init(&node->root_cache);
1231 cache_tree_init(&node->inode_cache);
1234 ret = insert_cache_extent(shared, &node->cache);
1239 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
1240 struct walk_control *wc, int level)
1242 struct shared_node *node;
1243 struct shared_node *dest;
1246 if (level == wc->active_node)
1249 BUG_ON(wc->active_node <= level);
1250 node = find_shared_node(&wc->shared, bytenr);
1252 ret = add_shared_node(&wc->shared, bytenr, refs);
1254 node = find_shared_node(&wc->shared, bytenr);
1255 wc->nodes[level] = node;
1256 wc->active_node = level;
1260 if (wc->root_level == wc->active_node &&
1261 btrfs_root_refs(&root->root_item) == 0) {
1262 if (--node->refs == 0) {
1263 free_inode_recs_tree(&node->root_cache);
1264 free_inode_recs_tree(&node->inode_cache);
1265 remove_cache_extent(&wc->shared, &node->cache);
1271 dest = wc->nodes[wc->active_node];
1272 splice_shared_node(node, dest);
1273 if (node->refs == 0) {
1274 remove_cache_extent(&wc->shared, &node->cache);
1280 static int leave_shared_node(struct btrfs_root *root,
1281 struct walk_control *wc, int level)
1283 struct shared_node *node;
1284 struct shared_node *dest;
1287 if (level == wc->root_level)
1290 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
1294 BUG_ON(i >= BTRFS_MAX_LEVEL);
1296 node = wc->nodes[wc->active_node];
1297 wc->nodes[wc->active_node] = NULL;
1298 wc->active_node = i;
1300 dest = wc->nodes[wc->active_node];
1301 if (wc->active_node < wc->root_level ||
1302 btrfs_root_refs(&root->root_item) > 0) {
1303 BUG_ON(node->refs <= 1);
1304 splice_shared_node(node, dest);
1306 BUG_ON(node->refs < 2);
1315 * 1 - if the root with id child_root_id is a child of root parent_root_id
1316 * 0 - if the root child_root_id isn't a child of the root parent_root_id but
1317 * has other root(s) as parent(s)
1318 * 2 - if the root child_root_id doesn't have any parent roots
1320 static int is_child_root(struct btrfs_root *root, u64 parent_root_id,
1323 struct btrfs_path path;
1324 struct btrfs_key key;
1325 struct extent_buffer *leaf;
1329 btrfs_init_path(&path);
1331 key.objectid = parent_root_id;
1332 key.type = BTRFS_ROOT_REF_KEY;
1333 key.offset = child_root_id;
1334 ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
1338 btrfs_release_path(&path);
1342 key.objectid = child_root_id;
1343 key.type = BTRFS_ROOT_BACKREF_KEY;
1345 ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
1351 leaf = path.nodes[0];
1352 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1353 ret = btrfs_next_leaf(root->fs_info->tree_root, &path);
1356 leaf = path.nodes[0];
1359 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1360 if (key.objectid != child_root_id ||
1361 key.type != BTRFS_ROOT_BACKREF_KEY)
1366 if (key.offset == parent_root_id) {
1367 btrfs_release_path(&path);
1374 btrfs_release_path(&path);
1377 return has_parent ? 0 : 2;
1380 static int process_dir_item(struct btrfs_root *root,
1381 struct extent_buffer *eb,
1382 int slot, struct btrfs_key *key,
1383 struct shared_node *active_node)
1393 struct btrfs_dir_item *di;
1394 struct inode_record *rec;
1395 struct cache_tree *root_cache;
1396 struct cache_tree *inode_cache;
1397 struct btrfs_key location;
1398 char namebuf[BTRFS_NAME_LEN];
1400 root_cache = &active_node->root_cache;
1401 inode_cache = &active_node->inode_cache;
1402 rec = active_node->current;
1403 rec->found_dir_item = 1;
1405 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
1406 total = btrfs_item_size_nr(eb, slot);
1407 while (cur < total) {
1409 btrfs_dir_item_key_to_cpu(eb, di, &location);
1410 name_len = btrfs_dir_name_len(eb, di);
1411 data_len = btrfs_dir_data_len(eb, di);
1412 filetype = btrfs_dir_type(eb, di);
1414 rec->found_size += name_len;
1415 if (name_len <= BTRFS_NAME_LEN) {
1419 len = BTRFS_NAME_LEN;
1420 error = REF_ERR_NAME_TOO_LONG;
1422 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
1424 if (location.type == BTRFS_INODE_ITEM_KEY) {
1425 add_inode_backref(inode_cache, location.objectid,
1426 key->objectid, key->offset, namebuf,
1427 len, filetype, key->type, error);
1428 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
1429 add_inode_backref(root_cache, location.objectid,
1430 key->objectid, key->offset,
1431 namebuf, len, filetype,
1434 fprintf(stderr, "invalid location in dir item %u\n",
1436 add_inode_backref(inode_cache, BTRFS_MULTIPLE_OBJECTIDS,
1437 key->objectid, key->offset, namebuf,
1438 len, filetype, key->type, error);
1441 len = sizeof(*di) + name_len + data_len;
1442 di = (struct btrfs_dir_item *)((char *)di + len);
1445 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
1446 rec->errors |= I_ERR_DUP_DIR_INDEX;
1451 static int process_inode_ref(struct extent_buffer *eb,
1452 int slot, struct btrfs_key *key,
1453 struct shared_node *active_node)
1461 struct cache_tree *inode_cache;
1462 struct btrfs_inode_ref *ref;
1463 char namebuf[BTRFS_NAME_LEN];
1465 inode_cache = &active_node->inode_cache;
1467 ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1468 total = btrfs_item_size_nr(eb, slot);
1469 while (cur < total) {
1470 name_len = btrfs_inode_ref_name_len(eb, ref);
1471 index = btrfs_inode_ref_index(eb, ref);
1472 if (name_len <= BTRFS_NAME_LEN) {
1476 len = BTRFS_NAME_LEN;
1477 error = REF_ERR_NAME_TOO_LONG;
1479 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1480 add_inode_backref(inode_cache, key->objectid, key->offset,
1481 index, namebuf, len, 0, key->type, error);
1483 len = sizeof(*ref) + name_len;
1484 ref = (struct btrfs_inode_ref *)((char *)ref + len);
1490 static int process_inode_extref(struct extent_buffer *eb,
1491 int slot, struct btrfs_key *key,
1492 struct shared_node *active_node)
1501 struct cache_tree *inode_cache;
1502 struct btrfs_inode_extref *extref;
1503 char namebuf[BTRFS_NAME_LEN];
1505 inode_cache = &active_node->inode_cache;
1507 extref = btrfs_item_ptr(eb, slot, struct btrfs_inode_extref);
1508 total = btrfs_item_size_nr(eb, slot);
1509 while (cur < total) {
1510 name_len = btrfs_inode_extref_name_len(eb, extref);
1511 index = btrfs_inode_extref_index(eb, extref);
1512 parent = btrfs_inode_extref_parent(eb, extref);
1513 if (name_len <= BTRFS_NAME_LEN) {
1517 len = BTRFS_NAME_LEN;
1518 error = REF_ERR_NAME_TOO_LONG;
1520 read_extent_buffer(eb, namebuf,
1521 (unsigned long)(extref + 1), len);
1522 add_inode_backref(inode_cache, key->objectid, parent,
1523 index, namebuf, len, 0, key->type, error);
1525 len = sizeof(*extref) + name_len;
1526 extref = (struct btrfs_inode_extref *)((char *)extref + len);
1533 static int count_csum_range(struct btrfs_root *root, u64 start,
1534 u64 len, u64 *found)
1536 struct btrfs_key key;
1537 struct btrfs_path path;
1538 struct extent_buffer *leaf;
1543 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1545 btrfs_init_path(&path);
1547 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
1549 key.type = BTRFS_EXTENT_CSUM_KEY;
1551 ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
1555 if (ret > 0 && path.slots[0] > 0) {
1556 leaf = path.nodes[0];
1557 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
1558 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
1559 key.type == BTRFS_EXTENT_CSUM_KEY)
1564 leaf = path.nodes[0];
1565 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1566 ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
1571 leaf = path.nodes[0];
1574 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1575 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
1576 key.type != BTRFS_EXTENT_CSUM_KEY)
1579 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1580 if (key.offset >= start + len)
1583 if (key.offset > start)
1586 size = btrfs_item_size_nr(leaf, path.slots[0]);
1587 csum_end = key.offset + (size / csum_size) * root->sectorsize;
1588 if (csum_end > start) {
1589 size = min(csum_end - start, len);
1598 btrfs_release_path(&path);
1604 static int process_file_extent(struct btrfs_root *root,
1605 struct extent_buffer *eb,
1606 int slot, struct btrfs_key *key,
1607 struct shared_node *active_node)
1609 struct inode_record *rec;
1610 struct btrfs_file_extent_item *fi;
1612 u64 disk_bytenr = 0;
1613 u64 extent_offset = 0;
1614 u64 mask = root->sectorsize - 1;
1618 rec = active_node->current;
1619 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
1620 rec->found_file_extent = 1;
1622 if (rec->extent_start == (u64)-1) {
1623 rec->extent_start = key->offset;
1624 rec->extent_end = key->offset;
1627 if (rec->extent_end > key->offset)
1628 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
1629 else if (rec->extent_end < key->offset) {
1630 ret = add_file_extent_hole(&rec->holes, rec->extent_end,
1631 key->offset - rec->extent_end);
1636 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
1637 extent_type = btrfs_file_extent_type(eb, fi);
1639 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1640 num_bytes = btrfs_file_extent_inline_len(eb, slot, fi);
1642 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1643 rec->found_size += num_bytes;
1644 num_bytes = (num_bytes + mask) & ~mask;
1645 } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
1646 extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1647 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1648 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
1649 extent_offset = btrfs_file_extent_offset(eb, fi);
1650 if (num_bytes == 0 || (num_bytes & mask))
1651 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1652 if (num_bytes + extent_offset >
1653 btrfs_file_extent_ram_bytes(eb, fi))
1654 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1655 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
1656 (btrfs_file_extent_compression(eb, fi) ||
1657 btrfs_file_extent_encryption(eb, fi) ||
1658 btrfs_file_extent_other_encoding(eb, fi)))
1659 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1660 if (disk_bytenr > 0)
1661 rec->found_size += num_bytes;
1663 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1665 rec->extent_end = key->offset + num_bytes;
1668 * The data reloc tree will copy full extents into its inode and then
1669 * copy the corresponding csums. Because the extent it copied could be
1670 * a preallocated extent that hasn't been written to yet there may be no
1671 * csums to copy, ergo we won't have csums for our file extent. This is
1672 * ok so just don't bother checking csums if the inode belongs to the
1675 if (disk_bytenr > 0 &&
1676 btrfs_header_owner(eb) != BTRFS_DATA_RELOC_TREE_OBJECTID) {
1678 if (btrfs_file_extent_compression(eb, fi))
1679 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
1681 disk_bytenr += extent_offset;
1683 ret = count_csum_range(root, disk_bytenr, num_bytes, &found);
1686 if (extent_type == BTRFS_FILE_EXTENT_REG) {
1688 rec->found_csum_item = 1;
1689 if (found < num_bytes)
1690 rec->some_csum_missing = 1;
1691 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1693 rec->errors |= I_ERR_ODD_CSUM_ITEM;
1699 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
1700 struct walk_control *wc)
1702 struct btrfs_key key;
1706 struct cache_tree *inode_cache;
1707 struct shared_node *active_node;
1709 if (wc->root_level == wc->active_node &&
1710 btrfs_root_refs(&root->root_item) == 0)
1713 active_node = wc->nodes[wc->active_node];
1714 inode_cache = &active_node->inode_cache;
1715 nritems = btrfs_header_nritems(eb);
1716 for (i = 0; i < nritems; i++) {
1717 btrfs_item_key_to_cpu(eb, &key, i);
1719 if (key.objectid == BTRFS_FREE_SPACE_OBJECTID)
1721 if (key.type == BTRFS_ORPHAN_ITEM_KEY)
1724 if (active_node->current == NULL ||
1725 active_node->current->ino < key.objectid) {
1726 if (active_node->current) {
1727 active_node->current->checked = 1;
1728 maybe_free_inode_rec(inode_cache,
1729 active_node->current);
1731 active_node->current = get_inode_rec(inode_cache,
1733 BUG_ON(IS_ERR(active_node->current));
1736 case BTRFS_DIR_ITEM_KEY:
1737 case BTRFS_DIR_INDEX_KEY:
1738 ret = process_dir_item(root, eb, i, &key, active_node);
1740 case BTRFS_INODE_REF_KEY:
1741 ret = process_inode_ref(eb, i, &key, active_node);
1743 case BTRFS_INODE_EXTREF_KEY:
1744 ret = process_inode_extref(eb, i, &key, active_node);
1746 case BTRFS_INODE_ITEM_KEY:
1747 ret = process_inode_item(eb, i, &key, active_node);
1749 case BTRFS_EXTENT_DATA_KEY:
1750 ret = process_file_extent(root, eb, i, &key,
1760 static void reada_walk_down(struct btrfs_root *root,
1761 struct extent_buffer *node, int slot)
1770 level = btrfs_header_level(node);
1774 nritems = btrfs_header_nritems(node);
1775 blocksize = root->nodesize;
1776 for (i = slot; i < nritems; i++) {
1777 bytenr = btrfs_node_blockptr(node, i);
1778 ptr_gen = btrfs_node_ptr_generation(node, i);
1779 readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1784 * Check the child node/leaf by the following condition:
1785 * 1. the first item key of the node/leaf should be the same with the one
1787 * 2. block in parent node should match the child node/leaf.
1788 * 3. generation of parent node and child's header should be consistent.
1790 * Or the child node/leaf pointed by the key in parent is not valid.
1792 * We hope to check leaf owner too, but since subvol may share leaves,
1793 * which makes leaf owner check not so strong, key check should be
1794 * sufficient enough for that case.
1796 static int check_child_node(struct btrfs_root *root,
1797 struct extent_buffer *parent, int slot,
1798 struct extent_buffer *child)
1800 struct btrfs_key parent_key;
1801 struct btrfs_key child_key;
1804 btrfs_node_key_to_cpu(parent, &parent_key, slot);
1805 if (btrfs_header_level(child) == 0)
1806 btrfs_item_key_to_cpu(child, &child_key, 0);
1808 btrfs_node_key_to_cpu(child, &child_key, 0);
1810 if (memcmp(&parent_key, &child_key, sizeof(parent_key))) {
1813 "Wrong key of child node/leaf, wanted: (%llu, %u, %llu), have: (%llu, %u, %llu)\n",
1814 parent_key.objectid, parent_key.type, parent_key.offset,
1815 child_key.objectid, child_key.type, child_key.offset);
1817 if (btrfs_header_bytenr(child) != btrfs_node_blockptr(parent, slot)) {
1819 fprintf(stderr, "Wrong block of child node/leaf, wanted: %llu, have: %llu\n",
1820 btrfs_node_blockptr(parent, slot),
1821 btrfs_header_bytenr(child));
1823 if (btrfs_node_ptr_generation(parent, slot) !=
1824 btrfs_header_generation(child)) {
1826 fprintf(stderr, "Wrong generation of child node/leaf, wanted: %llu, have: %llu\n",
1827 btrfs_header_generation(child),
1828 btrfs_node_ptr_generation(parent, slot));
1833 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1834 struct walk_control *wc, int *level)
1836 enum btrfs_tree_block_status status;
1839 struct extent_buffer *next;
1840 struct extent_buffer *cur;
1845 WARN_ON(*level < 0);
1846 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1847 ret = btrfs_lookup_extent_info(NULL, root,
1848 path->nodes[*level]->start,
1849 *level, 1, &refs, NULL);
1856 ret = enter_shared_node(root, path->nodes[*level]->start,
1864 while (*level >= 0) {
1865 WARN_ON(*level < 0);
1866 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1867 cur = path->nodes[*level];
1869 if (btrfs_header_level(cur) != *level)
1872 if (path->slots[*level] >= btrfs_header_nritems(cur))
1875 ret = process_one_leaf(root, cur, wc);
1880 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1881 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1882 blocksize = root->nodesize;
1883 ret = btrfs_lookup_extent_info(NULL, root, bytenr, *level - 1,
1889 ret = enter_shared_node(root, bytenr, refs,
1892 path->slots[*level]++;
1897 next = btrfs_find_tree_block(root, bytenr, blocksize);
1898 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1899 free_extent_buffer(next);
1900 reada_walk_down(root, cur, path->slots[*level]);
1901 next = read_tree_block(root, bytenr, blocksize,
1903 if (!extent_buffer_uptodate(next)) {
1904 struct btrfs_key node_key;
1906 btrfs_node_key_to_cpu(path->nodes[*level],
1908 path->slots[*level]);
1909 btrfs_add_corrupt_extent_record(root->fs_info,
1911 path->nodes[*level]->start,
1912 root->nodesize, *level);
1918 ret = check_child_node(root, cur, path->slots[*level], next);
1924 if (btrfs_is_leaf(next))
1925 status = btrfs_check_leaf(root, NULL, next);
1927 status = btrfs_check_node(root, NULL, next);
1928 if (status != BTRFS_TREE_BLOCK_CLEAN) {
1929 free_extent_buffer(next);
1934 *level = *level - 1;
1935 free_extent_buffer(path->nodes[*level]);
1936 path->nodes[*level] = next;
1937 path->slots[*level] = 0;
1940 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1944 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1945 struct walk_control *wc, int *level)
1948 struct extent_buffer *leaf;
1950 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1951 leaf = path->nodes[i];
1952 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1957 free_extent_buffer(path->nodes[*level]);
1958 path->nodes[*level] = NULL;
1959 BUG_ON(*level > wc->active_node);
1960 if (*level == wc->active_node)
1961 leave_shared_node(root, wc, *level);
1968 static int check_root_dir(struct inode_record *rec)
1970 struct inode_backref *backref;
1973 if (!rec->found_inode_item || rec->errors)
1975 if (rec->nlink != 1 || rec->found_link != 0)
1977 if (list_empty(&rec->backrefs))
1979 backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1980 if (!backref->found_inode_ref)
1982 if (backref->index != 0 || backref->namelen != 2 ||
1983 memcmp(backref->name, "..", 2))
1985 if (backref->found_dir_index || backref->found_dir_item)
1992 static int repair_inode_isize(struct btrfs_trans_handle *trans,
1993 struct btrfs_root *root, struct btrfs_path *path,
1994 struct inode_record *rec)
1996 struct btrfs_inode_item *ei;
1997 struct btrfs_key key;
2000 key.objectid = rec->ino;
2001 key.type = BTRFS_INODE_ITEM_KEY;
2002 key.offset = (u64)-1;
2004 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2008 if (!path->slots[0]) {
2015 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
2016 if (key.objectid != rec->ino) {
2021 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
2022 struct btrfs_inode_item);
2023 btrfs_set_inode_size(path->nodes[0], ei, rec->found_size);
2024 btrfs_mark_buffer_dirty(path->nodes[0]);
2025 rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
2026 printf("reset isize for dir %Lu root %Lu\n", rec->ino,
2027 root->root_key.objectid);
2029 btrfs_release_path(path);
2033 static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
2034 struct btrfs_root *root,
2035 struct btrfs_path *path,
2036 struct inode_record *rec)
2040 ret = btrfs_add_orphan_item(trans, root, path, rec->ino);
2041 btrfs_release_path(path);
2043 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
2047 static int repair_inode_nbytes(struct btrfs_trans_handle *trans,
2048 struct btrfs_root *root,
2049 struct btrfs_path *path,
2050 struct inode_record *rec)
2052 struct btrfs_inode_item *ei;
2053 struct btrfs_key key;
2056 key.objectid = rec->ino;
2057 key.type = BTRFS_INODE_ITEM_KEY;
2060 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2067 /* Since ret == 0, no need to check anything */
2068 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
2069 struct btrfs_inode_item);
2070 btrfs_set_inode_nbytes(path->nodes[0], ei, rec->found_size);
2071 btrfs_mark_buffer_dirty(path->nodes[0]);
2072 rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
2073 printf("reset nbytes for ino %llu root %llu\n",
2074 rec->ino, root->root_key.objectid);
2076 btrfs_release_path(path);
2080 static int add_missing_dir_index(struct btrfs_root *root,
2081 struct cache_tree *inode_cache,
2082 struct inode_record *rec,
2083 struct inode_backref *backref)
2085 struct btrfs_path *path;
2086 struct btrfs_trans_handle *trans;
2087 struct btrfs_dir_item *dir_item;
2088 struct extent_buffer *leaf;
2089 struct btrfs_key key;
2090 struct btrfs_disk_key disk_key;
2091 struct inode_record *dir_rec;
2092 unsigned long name_ptr;
2093 u32 data_size = sizeof(*dir_item) + backref->namelen;
2096 path = btrfs_alloc_path();
2100 trans = btrfs_start_transaction(root, 1);
2101 if (IS_ERR(trans)) {
2102 btrfs_free_path(path);
2103 return PTR_ERR(trans);
2106 fprintf(stderr, "repairing missing dir index item for inode %llu\n",
2107 (unsigned long long)rec->ino);
2108 key.objectid = backref->dir;
2109 key.type = BTRFS_DIR_INDEX_KEY;
2110 key.offset = backref->index;
2112 ret = btrfs_insert_empty_item(trans, root, path, &key, data_size);
2115 leaf = path->nodes[0];
2116 dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
2118 disk_key.objectid = cpu_to_le64(rec->ino);
2119 disk_key.type = BTRFS_INODE_ITEM_KEY;
2120 disk_key.offset = 0;
2122 btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
2123 btrfs_set_dir_type(leaf, dir_item, imode_to_type(rec->imode));
2124 btrfs_set_dir_data_len(leaf, dir_item, 0);
2125 btrfs_set_dir_name_len(leaf, dir_item, backref->namelen);
2126 name_ptr = (unsigned long)(dir_item + 1);
2127 write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen);
2128 btrfs_mark_buffer_dirty(leaf);
2129 btrfs_free_path(path);
2130 btrfs_commit_transaction(trans, root);
2132 backref->found_dir_index = 1;
2133 dir_rec = get_inode_rec(inode_cache, backref->dir, 0);
2134 BUG_ON(IS_ERR(dir_rec));
2137 dir_rec->found_size += backref->namelen;
2138 if (dir_rec->found_size == dir_rec->isize &&
2139 (dir_rec->errors & I_ERR_DIR_ISIZE_WRONG))
2140 dir_rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
2141 if (dir_rec->found_size != dir_rec->isize)
2142 dir_rec->errors |= I_ERR_DIR_ISIZE_WRONG;
2147 static int delete_dir_index(struct btrfs_root *root,
2148 struct cache_tree *inode_cache,
2149 struct inode_record *rec,
2150 struct inode_backref *backref)
2152 struct btrfs_trans_handle *trans;
2153 struct btrfs_dir_item *di;
2154 struct btrfs_path *path;
2157 path = btrfs_alloc_path();
2161 trans = btrfs_start_transaction(root, 1);
2162 if (IS_ERR(trans)) {
2163 btrfs_free_path(path);
2164 return PTR_ERR(trans);
2168 fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
2169 (unsigned long long)backref->dir,
2170 BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index,
2171 (unsigned long long)root->objectid);
2173 di = btrfs_lookup_dir_index(trans, root, path, backref->dir,
2174 backref->name, backref->namelen,
2175 backref->index, -1);
2178 btrfs_free_path(path);
2179 btrfs_commit_transaction(trans, root);
2186 ret = btrfs_del_item(trans, root, path);
2188 ret = btrfs_delete_one_dir_name(trans, root, path, di);
2190 btrfs_free_path(path);
2191 btrfs_commit_transaction(trans, root);
2195 static int create_inode_item(struct btrfs_root *root,
2196 struct inode_record *rec,
2197 struct inode_backref *backref, int root_dir)
2199 struct btrfs_trans_handle *trans;
2200 struct btrfs_inode_item inode_item;
2201 time_t now = time(NULL);
2204 trans = btrfs_start_transaction(root, 1);
2205 if (IS_ERR(trans)) {
2206 ret = PTR_ERR(trans);
2210 fprintf(stderr, "root %llu inode %llu recreating inode item, this may "
2211 "be incomplete, please check permissions and content after "
2212 "the fsck completes.\n", (unsigned long long)root->objectid,
2213 (unsigned long long)rec->ino);
2215 memset(&inode_item, 0, sizeof(inode_item));
2216 btrfs_set_stack_inode_generation(&inode_item, trans->transid);
2218 btrfs_set_stack_inode_nlink(&inode_item, 1);
2220 btrfs_set_stack_inode_nlink(&inode_item, rec->found_link);
2221 btrfs_set_stack_inode_nbytes(&inode_item, rec->found_size);
2222 if (rec->found_dir_item) {
2223 if (rec->found_file_extent)
2224 fprintf(stderr, "root %llu inode %llu has both a dir "
2225 "item and extents, unsure if it is a dir or a "
2226 "regular file so setting it as a directory\n",
2227 (unsigned long long)root->objectid,
2228 (unsigned long long)rec->ino);
2229 btrfs_set_stack_inode_mode(&inode_item, S_IFDIR | 0755);
2230 btrfs_set_stack_inode_size(&inode_item, rec->found_size);
2231 } else if (!rec->found_dir_item) {
2232 btrfs_set_stack_inode_size(&inode_item, rec->extent_end);
2233 btrfs_set_stack_inode_mode(&inode_item, S_IFREG | 0755);
2235 btrfs_set_stack_timespec_sec(&inode_item.atime, now);
2236 btrfs_set_stack_timespec_nsec(&inode_item.atime, 0);
2237 btrfs_set_stack_timespec_sec(&inode_item.ctime, now);
2238 btrfs_set_stack_timespec_nsec(&inode_item.ctime, 0);
2239 btrfs_set_stack_timespec_sec(&inode_item.mtime, now);
2240 btrfs_set_stack_timespec_nsec(&inode_item.mtime, 0);
2241 btrfs_set_stack_timespec_sec(&inode_item.otime, 0);
2242 btrfs_set_stack_timespec_nsec(&inode_item.otime, 0);
2244 ret = btrfs_insert_inode(trans, root, rec->ino, &inode_item);
2246 btrfs_commit_transaction(trans, root);
2250 static int repair_inode_backrefs(struct btrfs_root *root,
2251 struct inode_record *rec,
2252 struct cache_tree *inode_cache,
2255 struct inode_backref *tmp, *backref;
2256 u64 root_dirid = btrfs_root_dirid(&root->root_item);
2260 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
2261 if (!delete && rec->ino == root_dirid) {
2262 if (!rec->found_inode_item) {
2263 ret = create_inode_item(root, rec, backref, 1);
2270 /* Index 0 for root dir's are special, don't mess with it */
2271 if (rec->ino == root_dirid && backref->index == 0)
2275 ((backref->found_dir_index && !backref->found_inode_ref) ||
2276 (backref->found_dir_index && backref->found_inode_ref &&
2277 (backref->errors & REF_ERR_INDEX_UNMATCH)))) {
2278 ret = delete_dir_index(root, inode_cache, rec, backref);
2282 list_del(&backref->list);
2286 if (!delete && !backref->found_dir_index &&
2287 backref->found_dir_item && backref->found_inode_ref) {
2288 ret = add_missing_dir_index(root, inode_cache, rec,
2293 if (backref->found_dir_item &&
2294 backref->found_dir_index &&
2295 backref->found_dir_index) {
2296 if (!backref->errors &&
2297 backref->found_inode_ref) {
2298 list_del(&backref->list);
2304 if (!delete && (!backref->found_dir_index &&
2305 !backref->found_dir_item &&
2306 backref->found_inode_ref)) {
2307 struct btrfs_trans_handle *trans;
2308 struct btrfs_key location;
2310 ret = check_dir_conflict(root, backref->name,
2316 * let nlink fixing routine to handle it,
2317 * which can do it better.
2322 location.objectid = rec->ino;
2323 location.type = BTRFS_INODE_ITEM_KEY;
2324 location.offset = 0;
2326 trans = btrfs_start_transaction(root, 1);
2327 if (IS_ERR(trans)) {
2328 ret = PTR_ERR(trans);
2331 fprintf(stderr, "adding missing dir index/item pair "
2333 (unsigned long long)rec->ino);
2334 ret = btrfs_insert_dir_item(trans, root, backref->name,
2336 backref->dir, &location,
2337 imode_to_type(rec->imode),
2340 btrfs_commit_transaction(trans, root);
2344 if (!delete && (backref->found_inode_ref &&
2345 backref->found_dir_index &&
2346 backref->found_dir_item &&
2347 !(backref->errors & REF_ERR_INDEX_UNMATCH) &&
2348 !rec->found_inode_item)) {
2349 ret = create_inode_item(root, rec, backref, 0);
2356 return ret ? ret : repaired;
2360 * To determine the file type for nlink/inode_item repair
2362 * Return 0 if file type is found and BTRFS_FT_* is stored into type.
2363 * Return -ENOENT if file type is not found.
2365 static int find_file_type(struct inode_record *rec, u8 *type)
2367 struct inode_backref *backref;
2369 /* For inode item recovered case */
2370 if (rec->found_inode_item) {
2371 *type = imode_to_type(rec->imode);
2375 list_for_each_entry(backref, &rec->backrefs, list) {
2376 if (backref->found_dir_index || backref->found_dir_item) {
2377 *type = backref->filetype;
2385 * To determine the file name for nlink repair
2387 * Return 0 if file name is found, set name and namelen.
2388 * Return -ENOENT if file name is not found.
2390 static int find_file_name(struct inode_record *rec,
2391 char *name, int *namelen)
2393 struct inode_backref *backref;
2395 list_for_each_entry(backref, &rec->backrefs, list) {
2396 if (backref->found_dir_index || backref->found_dir_item ||
2397 backref->found_inode_ref) {
2398 memcpy(name, backref->name, backref->namelen);
2399 *namelen = backref->namelen;
2406 /* Reset the nlink of the inode to the correct one */
2407 static int reset_nlink(struct btrfs_trans_handle *trans,
2408 struct btrfs_root *root,
2409 struct btrfs_path *path,
2410 struct inode_record *rec)
2412 struct inode_backref *backref;
2413 struct inode_backref *tmp;
2414 struct btrfs_key key;
2415 struct btrfs_inode_item *inode_item;
2418 /* We don't believe this either, reset it and iterate backref */
2419 rec->found_link = 0;
2421 /* Remove all backref including the valid ones */
2422 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
2423 ret = btrfs_unlink(trans, root, rec->ino, backref->dir,
2424 backref->index, backref->name,
2425 backref->namelen, 0);
2429 /* remove invalid backref, so it won't be added back */
2430 if (!(backref->found_dir_index &&
2431 backref->found_dir_item &&
2432 backref->found_inode_ref)) {
2433 list_del(&backref->list);
2440 /* Set nlink to 0 */
2441 key.objectid = rec->ino;
2442 key.type = BTRFS_INODE_ITEM_KEY;
2444 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2451 inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2452 struct btrfs_inode_item);
2453 btrfs_set_inode_nlink(path->nodes[0], inode_item, 0);
2454 btrfs_mark_buffer_dirty(path->nodes[0]);
2455 btrfs_release_path(path);
2458 * Add back valid inode_ref/dir_item/dir_index,
2459 * add_link() will handle the nlink inc, so new nlink must be correct
2461 list_for_each_entry(backref, &rec->backrefs, list) {
2462 ret = btrfs_add_link(trans, root, rec->ino, backref->dir,
2463 backref->name, backref->namelen,
2464 backref->filetype, &backref->index, 1);
2469 btrfs_release_path(path);
2473 static int repair_inode_nlinks(struct btrfs_trans_handle *trans,
2474 struct btrfs_root *root,
2475 struct btrfs_path *path,
2476 struct inode_record *rec)
2478 char *dir_name = "lost+found";
2479 char namebuf[BTRFS_NAME_LEN] = {0};
2484 int name_recovered = 0;
2485 int type_recovered = 0;
2489 * Get file name and type first before these invalid inode ref
2490 * are deleted by remove_all_invalid_backref()
2492 name_recovered = !find_file_name(rec, namebuf, &namelen);
2493 type_recovered = !find_file_type(rec, &type);
2495 if (!name_recovered) {
2496 printf("Can't get file name for inode %llu, using '%llu' as fallback\n",
2497 rec->ino, rec->ino);
2498 namelen = count_digits(rec->ino);
2499 sprintf(namebuf, "%llu", rec->ino);
2502 if (!type_recovered) {
2503 printf("Can't get file type for inode %llu, using FILE as fallback\n",
2505 type = BTRFS_FT_REG_FILE;
2509 ret = reset_nlink(trans, root, path, rec);
2512 "Failed to reset nlink for inode %llu: %s\n",
2513 rec->ino, strerror(-ret));
2517 if (rec->found_link == 0) {
2518 lost_found_ino = root->highest_inode;
2519 if (lost_found_ino >= BTRFS_LAST_FREE_OBJECTID) {
2524 ret = btrfs_mkdir(trans, root, dir_name, strlen(dir_name),
2525 BTRFS_FIRST_FREE_OBJECTID, &lost_found_ino,
2528 fprintf(stderr, "Failed to create '%s' dir: %s\n",
2529 dir_name, strerror(-ret));
2532 ret = btrfs_add_link(trans, root, rec->ino, lost_found_ino,
2533 namebuf, namelen, type, NULL, 1);
2535 * Add ".INO" suffix several times to handle case where
2536 * "FILENAME.INO" is already taken by another file.
2538 while (ret == -EEXIST) {
2540 * Conflicting file name, add ".INO" as suffix * +1 for '.'
2542 if (namelen + count_digits(rec->ino) + 1 >
2547 snprintf(namebuf + namelen, BTRFS_NAME_LEN - namelen,
2549 namelen += count_digits(rec->ino) + 1;
2550 ret = btrfs_add_link(trans, root, rec->ino,
2551 lost_found_ino, namebuf,
2552 namelen, type, NULL, 1);
2556 "Failed to link the inode %llu to %s dir: %s\n",
2557 rec->ino, dir_name, strerror(-ret));
2561 * Just increase the found_link, don't actually add the
2562 * backref. This will make things easier and this inode
2563 * record will be freed after the repair is done.
2564 * So fsck will not report problem about this inode.
2567 printf("Moving file '%.*s' to '%s' dir since it has no valid backref\n",
2568 namelen, namebuf, dir_name);
2570 printf("Fixed the nlink of inode %llu\n", rec->ino);
2573 * Clear the flag anyway, or we will loop forever for the same inode
2574 * as it will not be removed from the bad inode list and the dead loop
2577 rec->errors &= ~I_ERR_LINK_COUNT_WRONG;
2578 btrfs_release_path(path);
2583 * Check if there is any normal(reg or prealloc) file extent for given
2585 * This is used to determine the file type when neither its dir_index/item or
2586 * inode_item exists.
2588 * This will *NOT* report error, if any error happens, just consider it does
2589 * not have any normal file extent.
2591 static int find_normal_file_extent(struct btrfs_root *root, u64 ino)
2593 struct btrfs_path *path;
2594 struct btrfs_key key;
2595 struct btrfs_key found_key;
2596 struct btrfs_file_extent_item *fi;
2600 path = btrfs_alloc_path();
2604 key.type = BTRFS_EXTENT_DATA_KEY;
2607 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2612 if (ret && path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
2613 ret = btrfs_next_leaf(root, path);
2620 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2622 if (found_key.objectid != ino ||
2623 found_key.type != BTRFS_EXTENT_DATA_KEY)
2625 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
2626 struct btrfs_file_extent_item);
2627 type = btrfs_file_extent_type(path->nodes[0], fi);
2628 if (type != BTRFS_FILE_EXTENT_INLINE) {
2634 btrfs_free_path(path);
2638 static u32 btrfs_type_to_imode(u8 type)
2640 static u32 imode_by_btrfs_type[] = {
2641 [BTRFS_FT_REG_FILE] = S_IFREG,
2642 [BTRFS_FT_DIR] = S_IFDIR,
2643 [BTRFS_FT_CHRDEV] = S_IFCHR,
2644 [BTRFS_FT_BLKDEV] = S_IFBLK,
2645 [BTRFS_FT_FIFO] = S_IFIFO,
2646 [BTRFS_FT_SOCK] = S_IFSOCK,
2647 [BTRFS_FT_SYMLINK] = S_IFLNK,
2650 return imode_by_btrfs_type[(type)];
2653 static int repair_inode_no_item(struct btrfs_trans_handle *trans,
2654 struct btrfs_root *root,
2655 struct btrfs_path *path,
2656 struct inode_record *rec)
2660 int type_recovered = 0;
2663 printf("Trying to rebuild inode:%llu\n", rec->ino);
2665 type_recovered = !find_file_type(rec, &filetype);
2668 * Try to determine inode type if type not found.
2670 * For found regular file extent, it must be FILE.
2671 * For found dir_item/index, it must be DIR.
2673 * For undetermined one, use FILE as fallback.
2676 * 1. If found backref(inode_index/item is already handled) to it,
2678 * Need new inode-inode ref structure to allow search for that.
2680 if (!type_recovered) {
2681 if (rec->found_file_extent &&
2682 find_normal_file_extent(root, rec->ino)) {
2684 filetype = BTRFS_FT_REG_FILE;
2685 } else if (rec->found_dir_item) {
2687 filetype = BTRFS_FT_DIR;
2688 } else if (!list_empty(&rec->orphan_extents)) {
2690 filetype = BTRFS_FT_REG_FILE;
2692 printf("Can't determint the filetype for inode %llu, assume it is a normal file\n",
2695 filetype = BTRFS_FT_REG_FILE;
2699 ret = btrfs_new_inode(trans, root, rec->ino,
2700 mode | btrfs_type_to_imode(filetype));
2705 * Here inode rebuild is done, we only rebuild the inode item,
2706 * don't repair the nlink(like move to lost+found).
2707 * That is the job of nlink repair.
2709 * We just fill the record and return
2711 rec->found_dir_item = 1;
2712 rec->imode = mode | btrfs_type_to_imode(filetype);
2714 rec->errors &= ~I_ERR_NO_INODE_ITEM;
2715 /* Ensure the inode_nlinks repair function will be called */
2716 rec->errors |= I_ERR_LINK_COUNT_WRONG;
2721 static int repair_inode_orphan_extent(struct btrfs_trans_handle *trans,
2722 struct btrfs_root *root,
2723 struct btrfs_path *path,
2724 struct inode_record *rec)
2726 struct orphan_data_extent *orphan;
2727 struct orphan_data_extent *tmp;
2730 list_for_each_entry_safe(orphan, tmp, &rec->orphan_extents, list) {
2732 * Check for conflicting file extents
2734 * Here we don't know whether the extents is compressed or not,
2735 * so we can only assume it not compressed nor data offset,
2736 * and use its disk_len as extent length.
2738 ret = btrfs_get_extent(NULL, root, path, orphan->objectid,
2739 orphan->offset, orphan->disk_len, 0);
2740 btrfs_release_path(path);
2745 "orphan extent (%llu, %llu) conflicts, delete the orphan\n",
2746 orphan->disk_bytenr, orphan->disk_len);
2747 ret = btrfs_free_extent(trans,
2748 root->fs_info->extent_root,
2749 orphan->disk_bytenr, orphan->disk_len,
2750 0, root->objectid, orphan->objectid,
2755 ret = btrfs_insert_file_extent(trans, root, orphan->objectid,
2756 orphan->offset, orphan->disk_bytenr,
2757 orphan->disk_len, orphan->disk_len);
2761 /* Update file size info */
2762 rec->found_size += orphan->disk_len;
2763 if (rec->found_size == rec->nbytes)
2764 rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
2766 /* Update the file extent hole info too */
2767 ret = del_file_extent_hole(&rec->holes, orphan->offset,
2771 if (RB_EMPTY_ROOT(&rec->holes))
2772 rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
2774 list_del(&orphan->list);
2777 rec->errors &= ~I_ERR_FILE_EXTENT_ORPHAN;
2782 static int repair_inode_discount_extent(struct btrfs_trans_handle *trans,
2783 struct btrfs_root *root,
2784 struct btrfs_path *path,
2785 struct inode_record *rec)
2787 struct rb_node *node;
2788 struct file_extent_hole *hole;
2792 node = rb_first(&rec->holes);
2796 hole = rb_entry(node, struct file_extent_hole, node);
2797 ret = btrfs_punch_hole(trans, root, rec->ino,
2798 hole->start, hole->len);
2801 ret = del_file_extent_hole(&rec->holes, hole->start,
2805 if (RB_EMPTY_ROOT(&rec->holes))
2806 rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
2807 node = rb_first(&rec->holes);
2809 /* special case for a file losing all its file extent */
2811 ret = btrfs_punch_hole(trans, root, rec->ino, 0,
2812 round_up(rec->isize, root->sectorsize));
2816 printf("Fixed discount file extents for inode: %llu in root: %llu\n",
2817 rec->ino, root->objectid);
2822 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
2824 struct btrfs_trans_handle *trans;
2825 struct btrfs_path *path;
2828 if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG |
2829 I_ERR_NO_ORPHAN_ITEM |
2830 I_ERR_LINK_COUNT_WRONG |
2831 I_ERR_NO_INODE_ITEM |
2832 I_ERR_FILE_EXTENT_ORPHAN |
2833 I_ERR_FILE_EXTENT_DISCOUNT|
2834 I_ERR_FILE_NBYTES_WRONG)))
2837 path = btrfs_alloc_path();
2842 * For nlink repair, it may create a dir and add link, so
2843 * 2 for parent(256)'s dir_index and dir_item
2844 * 2 for lost+found dir's inode_item and inode_ref
2845 * 1 for the new inode_ref of the file
2846 * 2 for lost+found dir's dir_index and dir_item for the file
2848 trans = btrfs_start_transaction(root, 7);
2849 if (IS_ERR(trans)) {
2850 btrfs_free_path(path);
2851 return PTR_ERR(trans);
2854 if (rec->errors & I_ERR_NO_INODE_ITEM)
2855 ret = repair_inode_no_item(trans, root, path, rec);
2856 if (!ret && rec->errors & I_ERR_FILE_EXTENT_ORPHAN)
2857 ret = repair_inode_orphan_extent(trans, root, path, rec);
2858 if (!ret && rec->errors & I_ERR_FILE_EXTENT_DISCOUNT)
2859 ret = repair_inode_discount_extent(trans, root, path, rec);
2860 if (!ret && rec->errors & I_ERR_DIR_ISIZE_WRONG)
2861 ret = repair_inode_isize(trans, root, path, rec);
2862 if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
2863 ret = repair_inode_orphan_item(trans, root, path, rec);
2864 if (!ret && rec->errors & I_ERR_LINK_COUNT_WRONG)
2865 ret = repair_inode_nlinks(trans, root, path, rec);
2866 if (!ret && rec->errors & I_ERR_FILE_NBYTES_WRONG)
2867 ret = repair_inode_nbytes(trans, root, path, rec);
2868 btrfs_commit_transaction(trans, root);
2869 btrfs_free_path(path);
2873 static int check_inode_recs(struct btrfs_root *root,
2874 struct cache_tree *inode_cache)
2876 struct cache_extent *cache;
2877 struct ptr_node *node;
2878 struct inode_record *rec;
2879 struct inode_backref *backref;
2884 u64 root_dirid = btrfs_root_dirid(&root->root_item);
2886 if (btrfs_root_refs(&root->root_item) == 0) {
2887 if (!cache_tree_empty(inode_cache))
2888 fprintf(stderr, "warning line %d\n", __LINE__);
2893 * We need to record the highest inode number for later 'lost+found'
2895 * We must select a ino not used/refered by any existing inode, or
2896 * 'lost+found' ino may be a missing ino in a corrupted leaf,
2897 * this may cause 'lost+found' dir has wrong nlinks.
2899 cache = last_cache_extent(inode_cache);
2901 node = container_of(cache, struct ptr_node, cache);
2903 if (rec->ino > root->highest_inode)
2904 root->highest_inode = rec->ino;
2908 * We need to repair backrefs first because we could change some of the
2909 * errors in the inode recs.
2911 * We also need to go through and delete invalid backrefs first and then
2912 * add the correct ones second. We do this because we may get EEXIST
2913 * when adding back the correct index because we hadn't yet deleted the
2916 * For example, if we were missing a dir index then the directories
2917 * isize would be wrong, so if we fixed the isize to what we thought it
2918 * would be and then fixed the backref we'd still have a invalid fs, so
2919 * we need to add back the dir index and then check to see if the isize
2924 if (stage == 3 && !err)
2927 cache = search_cache_extent(inode_cache, 0);
2928 while (repair && cache) {
2929 node = container_of(cache, struct ptr_node, cache);
2931 cache = next_cache_extent(cache);
2933 /* Need to free everything up and rescan */
2935 remove_cache_extent(inode_cache, &node->cache);
2937 free_inode_rec(rec);
2941 if (list_empty(&rec->backrefs))
2944 ret = repair_inode_backrefs(root, rec, inode_cache,
2958 rec = get_inode_rec(inode_cache, root_dirid, 0);
2959 BUG_ON(IS_ERR(rec));
2961 ret = check_root_dir(rec);
2963 fprintf(stderr, "root %llu root dir %llu error\n",
2964 (unsigned long long)root->root_key.objectid,
2965 (unsigned long long)root_dirid);
2966 print_inode_error(root, rec);
2971 struct btrfs_trans_handle *trans;
2973 trans = btrfs_start_transaction(root, 1);
2974 if (IS_ERR(trans)) {
2975 err = PTR_ERR(trans);
2980 "root %llu missing its root dir, recreating\n",
2981 (unsigned long long)root->objectid);
2983 ret = btrfs_make_root_dir(trans, root, root_dirid);
2986 btrfs_commit_transaction(trans, root);
2990 fprintf(stderr, "root %llu root dir %llu not found\n",
2991 (unsigned long long)root->root_key.objectid,
2992 (unsigned long long)root_dirid);
2996 cache = search_cache_extent(inode_cache, 0);
2999 node = container_of(cache, struct ptr_node, cache);
3001 remove_cache_extent(inode_cache, &node->cache);
3003 if (rec->ino == root_dirid ||
3004 rec->ino == BTRFS_ORPHAN_OBJECTID) {
3005 free_inode_rec(rec);
3009 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
3010 ret = check_orphan_item(root, rec->ino);
3012 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
3013 if (can_free_inode_rec(rec)) {
3014 free_inode_rec(rec);
3019 if (!rec->found_inode_item)
3020 rec->errors |= I_ERR_NO_INODE_ITEM;
3021 if (rec->found_link != rec->nlink)
3022 rec->errors |= I_ERR_LINK_COUNT_WRONG;
3024 ret = try_repair_inode(root, rec);
3025 if (ret == 0 && can_free_inode_rec(rec)) {
3026 free_inode_rec(rec);
3032 if (!(repair && ret == 0))
3034 print_inode_error(root, rec);
3035 list_for_each_entry(backref, &rec->backrefs, list) {
3036 if (!backref->found_dir_item)
3037 backref->errors |= REF_ERR_NO_DIR_ITEM;
3038 if (!backref->found_dir_index)
3039 backref->errors |= REF_ERR_NO_DIR_INDEX;
3040 if (!backref->found_inode_ref)
3041 backref->errors |= REF_ERR_NO_INODE_REF;
3042 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
3043 " namelen %u name %s filetype %d errors %x",
3044 (unsigned long long)backref->dir,
3045 (unsigned long long)backref->index,
3046 backref->namelen, backref->name,
3047 backref->filetype, backref->errors);
3048 print_ref_error(backref->errors);
3050 free_inode_rec(rec);
3052 return (error > 0) ? -1 : 0;
3055 static struct root_record *get_root_rec(struct cache_tree *root_cache,
3058 struct cache_extent *cache;
3059 struct root_record *rec = NULL;
3062 cache = lookup_cache_extent(root_cache, objectid, 1);
3064 rec = container_of(cache, struct root_record, cache);
3066 rec = calloc(1, sizeof(*rec));
3068 return ERR_PTR(-ENOMEM);
3069 rec->objectid = objectid;
3070 INIT_LIST_HEAD(&rec->backrefs);
3071 rec->cache.start = objectid;
3072 rec->cache.size = 1;
3074 ret = insert_cache_extent(root_cache, &rec->cache);
3076 return ERR_PTR(-EEXIST);
3081 static struct root_backref *get_root_backref(struct root_record *rec,
3082 u64 ref_root, u64 dir, u64 index,
3083 const char *name, int namelen)
3085 struct root_backref *backref;
3087 list_for_each_entry(backref, &rec->backrefs, list) {
3088 if (backref->ref_root != ref_root || backref->dir != dir ||
3089 backref->namelen != namelen)
3091 if (memcmp(name, backref->name, namelen))
3096 backref = calloc(1, sizeof(*backref) + namelen + 1);
3099 backref->ref_root = ref_root;
3101 backref->index = index;
3102 backref->namelen = namelen;
3103 memcpy(backref->name, name, namelen);
3104 backref->name[namelen] = '\0';
3105 list_add_tail(&backref->list, &rec->backrefs);
3109 static void free_root_record(struct cache_extent *cache)
3111 struct root_record *rec;
3112 struct root_backref *backref;
3114 rec = container_of(cache, struct root_record, cache);
3115 while (!list_empty(&rec->backrefs)) {
3116 backref = list_entry(rec->backrefs.next,
3117 struct root_backref, list);
3118 list_del(&backref->list);
3125 FREE_EXTENT_CACHE_BASED_TREE(root_recs, free_root_record);
3127 static int add_root_backref(struct cache_tree *root_cache,
3128 u64 root_id, u64 ref_root, u64 dir, u64 index,
3129 const char *name, int namelen,
3130 int item_type, int errors)
3132 struct root_record *rec;
3133 struct root_backref *backref;
3135 rec = get_root_rec(root_cache, root_id);
3136 BUG_ON(IS_ERR(rec));
3137 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
3140 backref->errors |= errors;
3142 if (item_type != BTRFS_DIR_ITEM_KEY) {
3143 if (backref->found_dir_index || backref->found_back_ref ||
3144 backref->found_forward_ref) {
3145 if (backref->index != index)
3146 backref->errors |= REF_ERR_INDEX_UNMATCH;
3148 backref->index = index;
3152 if (item_type == BTRFS_DIR_ITEM_KEY) {
3153 if (backref->found_forward_ref)
3155 backref->found_dir_item = 1;
3156 } else if (item_type == BTRFS_DIR_INDEX_KEY) {
3157 backref->found_dir_index = 1;
3158 } else if (item_type == BTRFS_ROOT_REF_KEY) {
3159 if (backref->found_forward_ref)
3160 backref->errors |= REF_ERR_DUP_ROOT_REF;
3161 else if (backref->found_dir_item)
3163 backref->found_forward_ref = 1;
3164 } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
3165 if (backref->found_back_ref)
3166 backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
3167 backref->found_back_ref = 1;
3172 if (backref->found_forward_ref && backref->found_dir_item)
3173 backref->reachable = 1;
3177 static int merge_root_recs(struct btrfs_root *root,
3178 struct cache_tree *src_cache,
3179 struct cache_tree *dst_cache)
3181 struct cache_extent *cache;
3182 struct ptr_node *node;
3183 struct inode_record *rec;
3184 struct inode_backref *backref;
3187 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
3188 free_inode_recs_tree(src_cache);
3193 cache = search_cache_extent(src_cache, 0);
3196 node = container_of(cache, struct ptr_node, cache);
3198 remove_cache_extent(src_cache, &node->cache);
3201 ret = is_child_root(root, root->objectid, rec->ino);
3207 list_for_each_entry(backref, &rec->backrefs, list) {
3208 BUG_ON(backref->found_inode_ref);
3209 if (backref->found_dir_item)
3210 add_root_backref(dst_cache, rec->ino,
3211 root->root_key.objectid, backref->dir,
3212 backref->index, backref->name,
3213 backref->namelen, BTRFS_DIR_ITEM_KEY,
3215 if (backref->found_dir_index)
3216 add_root_backref(dst_cache, rec->ino,
3217 root->root_key.objectid, backref->dir,
3218 backref->index, backref->name,
3219 backref->namelen, BTRFS_DIR_INDEX_KEY,
3223 free_inode_rec(rec);
3230 static int check_root_refs(struct btrfs_root *root,
3231 struct cache_tree *root_cache)
3233 struct root_record *rec;
3234 struct root_record *ref_root;
3235 struct root_backref *backref;
3236 struct cache_extent *cache;
3242 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
3243 BUG_ON(IS_ERR(rec));
3246 /* fixme: this can not detect circular references */
3249 cache = search_cache_extent(root_cache, 0);
3253 rec = container_of(cache, struct root_record, cache);
3254 cache = next_cache_extent(cache);
3256 if (rec->found_ref == 0)
3259 list_for_each_entry(backref, &rec->backrefs, list) {
3260 if (!backref->reachable)
3263 ref_root = get_root_rec(root_cache,
3265 BUG_ON(IS_ERR(ref_root));
3266 if (ref_root->found_ref > 0)
3269 backref->reachable = 0;
3271 if (rec->found_ref == 0)
3277 cache = search_cache_extent(root_cache, 0);
3281 rec = container_of(cache, struct root_record, cache);
3282 cache = next_cache_extent(cache);
3284 if (rec->found_ref == 0 &&
3285 rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
3286 rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
3287 ret = check_orphan_item(root->fs_info->tree_root,
3293 * If we don't have a root item then we likely just have
3294 * a dir item in a snapshot for this root but no actual
3295 * ref key or anything so it's meaningless.
3297 if (!rec->found_root_item)
3300 fprintf(stderr, "fs tree %llu not referenced\n",
3301 (unsigned long long)rec->objectid);
3305 if (rec->found_ref > 0 && !rec->found_root_item)
3307 list_for_each_entry(backref, &rec->backrefs, list) {
3308 if (!backref->found_dir_item)
3309 backref->errors |= REF_ERR_NO_DIR_ITEM;
3310 if (!backref->found_dir_index)
3311 backref->errors |= REF_ERR_NO_DIR_INDEX;
3312 if (!backref->found_back_ref)
3313 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
3314 if (!backref->found_forward_ref)
3315 backref->errors |= REF_ERR_NO_ROOT_REF;
3316 if (backref->reachable && backref->errors)
3323 fprintf(stderr, "fs tree %llu refs %u %s\n",
3324 (unsigned long long)rec->objectid, rec->found_ref,
3325 rec->found_root_item ? "" : "not found");
3327 list_for_each_entry(backref, &rec->backrefs, list) {
3328 if (!backref->reachable)
3330 if (!backref->errors && rec->found_root_item)
3332 fprintf(stderr, "\tunresolved ref root %llu dir %llu"
3333 " index %llu namelen %u name %s errors %x\n",
3334 (unsigned long long)backref->ref_root,
3335 (unsigned long long)backref->dir,
3336 (unsigned long long)backref->index,
3337 backref->namelen, backref->name,
3339 print_ref_error(backref->errors);
3342 return errors > 0 ? 1 : 0;
3345 static int process_root_ref(struct extent_buffer *eb, int slot,
3346 struct btrfs_key *key,
3347 struct cache_tree *root_cache)
3353 struct btrfs_root_ref *ref;
3354 char namebuf[BTRFS_NAME_LEN];
3357 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
3359 dirid = btrfs_root_ref_dirid(eb, ref);
3360 index = btrfs_root_ref_sequence(eb, ref);
3361 name_len = btrfs_root_ref_name_len(eb, ref);
3363 if (name_len <= BTRFS_NAME_LEN) {
3367 len = BTRFS_NAME_LEN;
3368 error = REF_ERR_NAME_TOO_LONG;
3370 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
3372 if (key->type == BTRFS_ROOT_REF_KEY) {
3373 add_root_backref(root_cache, key->offset, key->objectid, dirid,
3374 index, namebuf, len, key->type, error);
3376 add_root_backref(root_cache, key->objectid, key->offset, dirid,
3377 index, namebuf, len, key->type, error);
3382 static void free_corrupt_block(struct cache_extent *cache)
3384 struct btrfs_corrupt_block *corrupt;
3386 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
3390 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
3393 * Repair the btree of the given root.
3395 * The fix is to remove the node key in corrupt_blocks cache_tree.
3396 * and rebalance the tree.
3397 * After the fix, the btree should be writeable.
3399 static int repair_btree(struct btrfs_root *root,
3400 struct cache_tree *corrupt_blocks)
3402 struct btrfs_trans_handle *trans;
3403 struct btrfs_path *path;
3404 struct btrfs_corrupt_block *corrupt;
3405 struct cache_extent *cache;
3406 struct btrfs_key key;
3411 if (cache_tree_empty(corrupt_blocks))
3414 path = btrfs_alloc_path();
3418 trans = btrfs_start_transaction(root, 1);
3419 if (IS_ERR(trans)) {
3420 ret = PTR_ERR(trans);
3421 fprintf(stderr, "Error starting transaction: %s\n",
3425 cache = first_cache_extent(corrupt_blocks);
3427 corrupt = container_of(cache, struct btrfs_corrupt_block,
3429 level = corrupt->level;
3430 path->lowest_level = level;
3431 key.objectid = corrupt->key.objectid;
3432 key.type = corrupt->key.type;
3433 key.offset = corrupt->key.offset;
3436 * Here we don't want to do any tree balance, since it may
3437 * cause a balance with corrupted brother leaf/node,
3438 * so ins_len set to 0 here.
3439 * Balance will be done after all corrupt node/leaf is deleted.
3441 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3444 offset = btrfs_node_blockptr(path->nodes[level],
3445 path->slots[level]);
3447 /* Remove the ptr */
3448 ret = btrfs_del_ptr(trans, root, path, level,
3449 path->slots[level]);
3453 * Remove the corresponding extent
3454 * return value is not concerned.
3456 btrfs_release_path(path);
3457 ret = btrfs_free_extent(trans, root, offset, root->nodesize,
3458 0, root->root_key.objectid,
3460 cache = next_cache_extent(cache);
3463 /* Balance the btree using btrfs_search_slot() */
3464 cache = first_cache_extent(corrupt_blocks);
3466 corrupt = container_of(cache, struct btrfs_corrupt_block,
3468 memcpy(&key, &corrupt->key, sizeof(key));
3469 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3472 /* return will always >0 since it won't find the item */
3474 btrfs_release_path(path);
3475 cache = next_cache_extent(cache);
3478 btrfs_commit_transaction(trans, root);
3480 btrfs_free_path(path);
3484 static int check_fs_root(struct btrfs_root *root,
3485 struct cache_tree *root_cache,
3486 struct walk_control *wc)
3492 struct btrfs_path path;
3493 struct shared_node root_node;
3494 struct root_record *rec;
3495 struct btrfs_root_item *root_item = &root->root_item;
3496 struct cache_tree corrupt_blocks;
3497 struct orphan_data_extent *orphan;
3498 struct orphan_data_extent *tmp;
3499 enum btrfs_tree_block_status status;
3502 * Reuse the corrupt_block cache tree to record corrupted tree block
3504 * Unlike the usage in extent tree check, here we do it in a per
3505 * fs/subvol tree base.
3507 cache_tree_init(&corrupt_blocks);
3508 root->fs_info->corrupt_blocks = &corrupt_blocks;
3510 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
3511 rec = get_root_rec(root_cache, root->root_key.objectid);
3512 BUG_ON(IS_ERR(rec));
3513 if (btrfs_root_refs(root_item) > 0)
3514 rec->found_root_item = 1;
3517 btrfs_init_path(&path);
3518 memset(&root_node, 0, sizeof(root_node));
3519 cache_tree_init(&root_node.root_cache);
3520 cache_tree_init(&root_node.inode_cache);
3522 /* Move the orphan extent record to corresponding inode_record */
3523 list_for_each_entry_safe(orphan, tmp,
3524 &root->orphan_data_extents, list) {
3525 struct inode_record *inode;
3527 inode = get_inode_rec(&root_node.inode_cache, orphan->objectid,
3529 BUG_ON(IS_ERR(inode));
3530 inode->errors |= I_ERR_FILE_EXTENT_ORPHAN;
3531 list_move(&orphan->list, &inode->orphan_extents);
3534 level = btrfs_header_level(root->node);
3535 memset(wc->nodes, 0, sizeof(wc->nodes));
3536 wc->nodes[level] = &root_node;
3537 wc->active_node = level;
3538 wc->root_level = level;
3540 /* We may not have checked the root block, lets do that now */
3541 if (btrfs_is_leaf(root->node))
3542 status = btrfs_check_leaf(root, NULL, root->node);
3544 status = btrfs_check_node(root, NULL, root->node);
3545 if (status != BTRFS_TREE_BLOCK_CLEAN)
3548 if (btrfs_root_refs(root_item) > 0 ||
3549 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
3550 path.nodes[level] = root->node;
3551 extent_buffer_get(root->node);
3552 path.slots[level] = 0;
3554 struct btrfs_key key;
3555 struct btrfs_disk_key found_key;
3557 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3558 level = root_item->drop_level;
3559 path.lowest_level = level;
3560 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3563 btrfs_node_key(path.nodes[level], &found_key,
3565 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
3566 sizeof(found_key)));
3570 wret = walk_down_tree(root, &path, wc, &level);
3576 wret = walk_up_tree(root, &path, wc, &level);
3583 btrfs_release_path(&path);
3585 if (!cache_tree_empty(&corrupt_blocks)) {
3586 struct cache_extent *cache;
3587 struct btrfs_corrupt_block *corrupt;
3589 printf("The following tree block(s) is corrupted in tree %llu:\n",
3590 root->root_key.objectid);
3591 cache = first_cache_extent(&corrupt_blocks);
3593 corrupt = container_of(cache,
3594 struct btrfs_corrupt_block,
3596 printf("\ttree block bytenr: %llu, level: %d, node key: (%llu, %u, %llu)\n",
3597 cache->start, corrupt->level,
3598 corrupt->key.objectid, corrupt->key.type,
3599 corrupt->key.offset);
3600 cache = next_cache_extent(cache);
3603 printf("Try to repair the btree for root %llu\n",
3604 root->root_key.objectid);
3605 ret = repair_btree(root, &corrupt_blocks);
3607 fprintf(stderr, "Failed to repair btree: %s\n",
3610 printf("Btree for root %llu is fixed\n",
3611 root->root_key.objectid);
3615 err = merge_root_recs(root, &root_node.root_cache, root_cache);
3619 if (root_node.current) {
3620 root_node.current->checked = 1;
3621 maybe_free_inode_rec(&root_node.inode_cache,
3625 err = check_inode_recs(root, &root_node.inode_cache);
3629 free_corrupt_blocks_tree(&corrupt_blocks);
3630 root->fs_info->corrupt_blocks = NULL;
3631 free_orphan_data_extents(&root->orphan_data_extents);
3635 static int fs_root_objectid(u64 objectid)
3637 if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
3638 objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
3640 return is_fstree(objectid);
3643 static int check_fs_roots(struct btrfs_root *root,
3644 struct cache_tree *root_cache)
3646 struct btrfs_path path;
3647 struct btrfs_key key;
3648 struct walk_control wc;
3649 struct extent_buffer *leaf, *tree_node;
3650 struct btrfs_root *tmp_root;
3651 struct btrfs_root *tree_root = root->fs_info->tree_root;
3655 if (ctx.progress_enabled) {
3656 ctx.tp = TASK_FS_ROOTS;
3657 task_start(ctx.info);
3661 * Just in case we made any changes to the extent tree that weren't
3662 * reflected into the free space cache yet.
3665 reset_cached_block_groups(root->fs_info);
3666 memset(&wc, 0, sizeof(wc));
3667 cache_tree_init(&wc.shared);
3668 btrfs_init_path(&path);
3673 key.type = BTRFS_ROOT_ITEM_KEY;
3674 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
3679 tree_node = tree_root->node;
3681 if (tree_node != tree_root->node) {
3682 free_root_recs_tree(root_cache);
3683 btrfs_release_path(&path);
3686 leaf = path.nodes[0];
3687 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
3688 ret = btrfs_next_leaf(tree_root, &path);
3694 leaf = path.nodes[0];
3696 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
3697 if (key.type == BTRFS_ROOT_ITEM_KEY &&
3698 fs_root_objectid(key.objectid)) {
3699 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
3700 tmp_root = btrfs_read_fs_root_no_cache(
3701 root->fs_info, &key);
3703 key.offset = (u64)-1;
3704 tmp_root = btrfs_read_fs_root(
3705 root->fs_info, &key);
3707 if (IS_ERR(tmp_root)) {
3711 ret = check_fs_root(tmp_root, root_cache, &wc);
3712 if (ret == -EAGAIN) {
3713 free_root_recs_tree(root_cache);
3714 btrfs_release_path(&path);
3719 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
3720 btrfs_free_fs_root(tmp_root);
3721 } else if (key.type == BTRFS_ROOT_REF_KEY ||
3722 key.type == BTRFS_ROOT_BACKREF_KEY) {
3723 process_root_ref(leaf, path.slots[0], &key,
3730 btrfs_release_path(&path);
3732 free_extent_cache_tree(&wc.shared);
3733 if (!cache_tree_empty(&wc.shared))
3734 fprintf(stderr, "warning line %d\n", __LINE__);
3736 task_stop(ctx.info);
3741 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
3743 struct list_head *cur = rec->backrefs.next;
3744 struct extent_backref *back;
3745 struct tree_backref *tback;
3746 struct data_backref *dback;
3750 while(cur != &rec->backrefs) {
3751 back = list_entry(cur, struct extent_backref, list);
3753 if (!back->found_extent_tree) {
3757 if (back->is_data) {
3758 dback = (struct data_backref *)back;
3759 fprintf(stderr, "Backref %llu %s %llu"
3760 " owner %llu offset %llu num_refs %lu"
3761 " not found in extent tree\n",
3762 (unsigned long long)rec->start,
3763 back->full_backref ?
3765 back->full_backref ?
3766 (unsigned long long)dback->parent:
3767 (unsigned long long)dback->root,
3768 (unsigned long long)dback->owner,
3769 (unsigned long long)dback->offset,
3770 (unsigned long)dback->num_refs);
3772 tback = (struct tree_backref *)back;
3773 fprintf(stderr, "Backref %llu parent %llu"
3774 " root %llu not found in extent tree\n",
3775 (unsigned long long)rec->start,
3776 (unsigned long long)tback->parent,
3777 (unsigned long long)tback->root);
3780 if (!back->is_data && !back->found_ref) {
3784 tback = (struct tree_backref *)back;
3785 fprintf(stderr, "Backref %llu %s %llu not referenced back %p\n",
3786 (unsigned long long)rec->start,
3787 back->full_backref ? "parent" : "root",
3788 back->full_backref ?
3789 (unsigned long long)tback->parent :
3790 (unsigned long long)tback->root, back);
3792 if (back->is_data) {
3793 dback = (struct data_backref *)back;
3794 if (dback->found_ref != dback->num_refs) {
3798 fprintf(stderr, "Incorrect local backref count"
3799 " on %llu %s %llu owner %llu"
3800 " offset %llu found %u wanted %u back %p\n",
3801 (unsigned long long)rec->start,
3802 back->full_backref ?
3804 back->full_backref ?
3805 (unsigned long long)dback->parent:
3806 (unsigned long long)dback->root,
3807 (unsigned long long)dback->owner,
3808 (unsigned long long)dback->offset,
3809 dback->found_ref, dback->num_refs, back);
3811 if (dback->disk_bytenr != rec->start) {
3815 fprintf(stderr, "Backref disk bytenr does not"
3816 " match extent record, bytenr=%llu, "
3817 "ref bytenr=%llu\n",
3818 (unsigned long long)rec->start,
3819 (unsigned long long)dback->disk_bytenr);
3822 if (dback->bytes != rec->nr) {
3826 fprintf(stderr, "Backref bytes do not match "
3827 "extent backref, bytenr=%llu, ref "
3828 "bytes=%llu, backref bytes=%llu\n",
3829 (unsigned long long)rec->start,
3830 (unsigned long long)rec->nr,
3831 (unsigned long long)dback->bytes);
3834 if (!back->is_data) {
3837 dback = (struct data_backref *)back;
3838 found += dback->found_ref;
3841 if (found != rec->refs) {
3845 fprintf(stderr, "Incorrect global backref count "
3846 "on %llu found %llu wanted %llu\n",
3847 (unsigned long long)rec->start,
3848 (unsigned long long)found,
3849 (unsigned long long)rec->refs);
3855 static int free_all_extent_backrefs(struct extent_record *rec)
3857 struct extent_backref *back;
3858 struct list_head *cur;
3859 while (!list_empty(&rec->backrefs)) {
3860 cur = rec->backrefs.next;
3861 back = list_entry(cur, struct extent_backref, list);
3868 static void free_extent_record_cache(struct btrfs_fs_info *fs_info,
3869 struct cache_tree *extent_cache)
3871 struct cache_extent *cache;
3872 struct extent_record *rec;
3875 cache = first_cache_extent(extent_cache);
3878 rec = container_of(cache, struct extent_record, cache);
3879 remove_cache_extent(extent_cache, cache);
3880 free_all_extent_backrefs(rec);
3885 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
3886 struct extent_record *rec)
3888 if (rec->content_checked && rec->owner_ref_checked &&
3889 rec->extent_item_refs == rec->refs && rec->refs > 0 &&
3890 rec->num_duplicates == 0 && !all_backpointers_checked(rec, 0) &&
3891 !rec->bad_full_backref && !rec->crossing_stripes &&
3892 !rec->wrong_chunk_type) {
3893 remove_cache_extent(extent_cache, &rec->cache);
3894 free_all_extent_backrefs(rec);
3895 list_del_init(&rec->list);
3901 static int check_owner_ref(struct btrfs_root *root,
3902 struct extent_record *rec,
3903 struct extent_buffer *buf)
3905 struct extent_backref *node;
3906 struct tree_backref *back;
3907 struct btrfs_root *ref_root;
3908 struct btrfs_key key;
3909 struct btrfs_path path;
3910 struct extent_buffer *parent;
3915 list_for_each_entry(node, &rec->backrefs, list) {
3918 if (!node->found_ref)
3920 if (node->full_backref)
3922 back = (struct tree_backref *)node;
3923 if (btrfs_header_owner(buf) == back->root)
3926 BUG_ON(rec->is_root);
3928 /* try to find the block by search corresponding fs tree */
3929 key.objectid = btrfs_header_owner(buf);
3930 key.type = BTRFS_ROOT_ITEM_KEY;
3931 key.offset = (u64)-1;
3933 ref_root = btrfs_read_fs_root(root->fs_info, &key);
3934 if (IS_ERR(ref_root))
3937 level = btrfs_header_level(buf);
3939 btrfs_item_key_to_cpu(buf, &key, 0);
3941 btrfs_node_key_to_cpu(buf, &key, 0);
3943 btrfs_init_path(&path);
3944 path.lowest_level = level + 1;
3945 ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
3949 parent = path.nodes[level + 1];
3950 if (parent && buf->start == btrfs_node_blockptr(parent,
3951 path.slots[level + 1]))
3954 btrfs_release_path(&path);
3955 return found ? 0 : 1;
3958 static int is_extent_tree_record(struct extent_record *rec)
3960 struct list_head *cur = rec->backrefs.next;
3961 struct extent_backref *node;
3962 struct tree_backref *back;
3965 while(cur != &rec->backrefs) {
3966 node = list_entry(cur, struct extent_backref, list);
3970 back = (struct tree_backref *)node;
3971 if (node->full_backref)
3973 if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
3980 static int record_bad_block_io(struct btrfs_fs_info *info,
3981 struct cache_tree *extent_cache,
3984 struct extent_record *rec;
3985 struct cache_extent *cache;
3986 struct btrfs_key key;
3988 cache = lookup_cache_extent(extent_cache, start, len);
3992 rec = container_of(cache, struct extent_record, cache);
3993 if (!is_extent_tree_record(rec))
3996 btrfs_disk_key_to_cpu(&key, &rec->parent_key);
3997 return btrfs_add_corrupt_extent_record(info, &key, start, len, 0);
4000 static int swap_values(struct btrfs_root *root, struct btrfs_path *path,
4001 struct extent_buffer *buf, int slot)
4003 if (btrfs_header_level(buf)) {
4004 struct btrfs_key_ptr ptr1, ptr2;
4006 read_extent_buffer(buf, &ptr1, btrfs_node_key_ptr_offset(slot),
4007 sizeof(struct btrfs_key_ptr));
4008 read_extent_buffer(buf, &ptr2,
4009 btrfs_node_key_ptr_offset(slot + 1),
4010 sizeof(struct btrfs_key_ptr));
4011 write_extent_buffer(buf, &ptr1,
4012 btrfs_node_key_ptr_offset(slot + 1),
4013 sizeof(struct btrfs_key_ptr));
4014 write_extent_buffer(buf, &ptr2,
4015 btrfs_node_key_ptr_offset(slot),
4016 sizeof(struct btrfs_key_ptr));
4018 struct btrfs_disk_key key;
4019 btrfs_node_key(buf, &key, 0);
4020 btrfs_fixup_low_keys(root, path, &key,
4021 btrfs_header_level(buf) + 1);
4024 struct btrfs_item *item1, *item2;
4025 struct btrfs_key k1, k2;
4026 char *item1_data, *item2_data;
4027 u32 item1_offset, item2_offset, item1_size, item2_size;
4029 item1 = btrfs_item_nr(slot);
4030 item2 = btrfs_item_nr(slot + 1);
4031 btrfs_item_key_to_cpu(buf, &k1, slot);
4032 btrfs_item_key_to_cpu(buf, &k2, slot + 1);
4033 item1_offset = btrfs_item_offset(buf, item1);
4034 item2_offset = btrfs_item_offset(buf, item2);
4035 item1_size = btrfs_item_size(buf, item1);
4036 item2_size = btrfs_item_size(buf, item2);
4038 item1_data = malloc(item1_size);
4041 item2_data = malloc(item2_size);
4047 read_extent_buffer(buf, item1_data, item1_offset, item1_size);
4048 read_extent_buffer(buf, item2_data, item2_offset, item2_size);
4050 write_extent_buffer(buf, item1_data, item2_offset, item2_size);
4051 write_extent_buffer(buf, item2_data, item1_offset, item1_size);
4055 btrfs_set_item_offset(buf, item1, item2_offset);
4056 btrfs_set_item_offset(buf, item2, item1_offset);
4057 btrfs_set_item_size(buf, item1, item2_size);
4058 btrfs_set_item_size(buf, item2, item1_size);
4060 path->slots[0] = slot;
4061 btrfs_set_item_key_unsafe(root, path, &k2);
4062 path->slots[0] = slot + 1;
4063 btrfs_set_item_key_unsafe(root, path, &k1);
4068 static int fix_key_order(struct btrfs_trans_handle *trans,
4069 struct btrfs_root *root,
4070 struct btrfs_path *path)
4072 struct extent_buffer *buf;
4073 struct btrfs_key k1, k2;
4075 int level = path->lowest_level;
4078 buf = path->nodes[level];
4079 for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
4081 btrfs_node_key_to_cpu(buf, &k1, i);
4082 btrfs_node_key_to_cpu(buf, &k2, i + 1);
4084 btrfs_item_key_to_cpu(buf, &k1, i);
4085 btrfs_item_key_to_cpu(buf, &k2, i + 1);
4087 if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
4089 ret = swap_values(root, path, buf, i);
4092 btrfs_mark_buffer_dirty(buf);
4098 static int delete_bogus_item(struct btrfs_trans_handle *trans,
4099 struct btrfs_root *root,
4100 struct btrfs_path *path,
4101 struct extent_buffer *buf, int slot)
4103 struct btrfs_key key;
4104 int nritems = btrfs_header_nritems(buf);
4106 btrfs_item_key_to_cpu(buf, &key, slot);
4108 /* These are all the keys we can deal with missing. */
4109 if (key.type != BTRFS_DIR_INDEX_KEY &&
4110 key.type != BTRFS_EXTENT_ITEM_KEY &&
4111 key.type != BTRFS_METADATA_ITEM_KEY &&
4112 key.type != BTRFS_TREE_BLOCK_REF_KEY &&
4113 key.type != BTRFS_EXTENT_DATA_REF_KEY)
4116 printf("Deleting bogus item [%llu,%u,%llu] at slot %d on block %llu\n",
4117 (unsigned long long)key.objectid, key.type,
4118 (unsigned long long)key.offset, slot, buf->start);
4119 memmove_extent_buffer(buf, btrfs_item_nr_offset(slot),
4120 btrfs_item_nr_offset(slot + 1),
4121 sizeof(struct btrfs_item) *
4122 (nritems - slot - 1));
4123 btrfs_set_header_nritems(buf, nritems - 1);
4125 struct btrfs_disk_key disk_key;
4127 btrfs_item_key(buf, &disk_key, 0);
4128 btrfs_fixup_low_keys(root, path, &disk_key, 1);
4130 btrfs_mark_buffer_dirty(buf);
4134 static int fix_item_offset(struct btrfs_trans_handle *trans,
4135 struct btrfs_root *root,
4136 struct btrfs_path *path)
4138 struct extent_buffer *buf;
4142 /* We should only get this for leaves */
4143 BUG_ON(path->lowest_level);
4144 buf = path->nodes[0];
4146 for (i = 0; i < btrfs_header_nritems(buf); i++) {
4147 unsigned int shift = 0, offset;
4149 if (i == 0 && btrfs_item_end_nr(buf, i) !=
4150 BTRFS_LEAF_DATA_SIZE(root)) {
4151 if (btrfs_item_end_nr(buf, i) >
4152 BTRFS_LEAF_DATA_SIZE(root)) {
4153 ret = delete_bogus_item(trans, root, path,
4157 fprintf(stderr, "item is off the end of the "
4158 "leaf, can't fix\n");
4162 shift = BTRFS_LEAF_DATA_SIZE(root) -
4163 btrfs_item_end_nr(buf, i);
4164 } else if (i > 0 && btrfs_item_end_nr(buf, i) !=
4165 btrfs_item_offset_nr(buf, i - 1)) {
4166 if (btrfs_item_end_nr(buf, i) >
4167 btrfs_item_offset_nr(buf, i - 1)) {
4168 ret = delete_bogus_item(trans, root, path,
4172 fprintf(stderr, "items overlap, can't fix\n");
4176 shift = btrfs_item_offset_nr(buf, i - 1) -
4177 btrfs_item_end_nr(buf, i);
4182 printf("Shifting item nr %d by %u bytes in block %llu\n",
4183 i, shift, (unsigned long long)buf->start);
4184 offset = btrfs_item_offset_nr(buf, i);
4185 memmove_extent_buffer(buf,
4186 btrfs_leaf_data(buf) + offset + shift,
4187 btrfs_leaf_data(buf) + offset,
4188 btrfs_item_size_nr(buf, i));
4189 btrfs_set_item_offset(buf, btrfs_item_nr(i),
4191 btrfs_mark_buffer_dirty(buf);
4195 * We may have moved things, in which case we want to exit so we don't
4196 * write those changes out. Once we have proper abort functionality in
4197 * progs this can be changed to something nicer.
4204 * Attempt to fix basic block failures. If we can't fix it for whatever reason
4205 * then just return -EIO.
4207 static int try_to_fix_bad_block(struct btrfs_root *root,
4208 struct extent_buffer *buf,
4209 enum btrfs_tree_block_status status)
4211 struct btrfs_trans_handle *trans;
4212 struct ulist *roots;
4213 struct ulist_node *node;
4214 struct btrfs_root *search_root;
4215 struct btrfs_path *path;
4216 struct ulist_iterator iter;
4217 struct btrfs_key root_key, key;
4220 if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER &&
4221 status != BTRFS_TREE_BLOCK_INVALID_OFFSETS)
4224 path = btrfs_alloc_path();
4228 ret = btrfs_find_all_roots(NULL, root->fs_info, buf->start,
4231 btrfs_free_path(path);
4235 ULIST_ITER_INIT(&iter);
4236 while ((node = ulist_next(roots, &iter))) {
4237 root_key.objectid = node->val;
4238 root_key.type = BTRFS_ROOT_ITEM_KEY;
4239 root_key.offset = (u64)-1;
4241 search_root = btrfs_read_fs_root(root->fs_info, &root_key);
4248 trans = btrfs_start_transaction(search_root, 0);
4249 if (IS_ERR(trans)) {
4250 ret = PTR_ERR(trans);
4254 path->lowest_level = btrfs_header_level(buf);
4255 path->skip_check_block = 1;
4256 if (path->lowest_level)
4257 btrfs_node_key_to_cpu(buf, &key, 0);
4259 btrfs_item_key_to_cpu(buf, &key, 0);
4260 ret = btrfs_search_slot(trans, search_root, &key, path, 0, 1);
4263 btrfs_commit_transaction(trans, search_root);
4266 if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
4267 ret = fix_key_order(trans, search_root, path);
4268 else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
4269 ret = fix_item_offset(trans, search_root, path);
4271 btrfs_commit_transaction(trans, search_root);
4274 btrfs_release_path(path);
4275 btrfs_commit_transaction(trans, search_root);
4278 btrfs_free_path(path);
4282 static int check_block(struct btrfs_root *root,
4283 struct cache_tree *extent_cache,
4284 struct extent_buffer *buf, u64 flags)
4286 struct extent_record *rec;
4287 struct cache_extent *cache;
4288 struct btrfs_key key;
4289 enum btrfs_tree_block_status status;
4293 cache = lookup_cache_extent(extent_cache, buf->start, buf->len);
4296 rec = container_of(cache, struct extent_record, cache);
4297 rec->generation = btrfs_header_generation(buf);
4299 level = btrfs_header_level(buf);
4300 if (btrfs_header_nritems(buf) > 0) {
4303 btrfs_item_key_to_cpu(buf, &key, 0);
4305 btrfs_node_key_to_cpu(buf, &key, 0);
4307 rec->info_objectid = key.objectid;
4309 rec->info_level = level;
4311 if (btrfs_is_leaf(buf))
4312 status = btrfs_check_leaf(root, &rec->parent_key, buf);
4314 status = btrfs_check_node(root, &rec->parent_key, buf);
4316 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4318 status = try_to_fix_bad_block(root, buf, status);
4319 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4321 fprintf(stderr, "bad block %llu\n",
4322 (unsigned long long)buf->start);
4325 * Signal to callers we need to start the scan over
4326 * again since we'll have cow'ed blocks.
4331 rec->content_checked = 1;
4332 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
4333 rec->owner_ref_checked = 1;
4335 ret = check_owner_ref(root, rec, buf);
4337 rec->owner_ref_checked = 1;
4341 maybe_free_extent_rec(extent_cache, rec);
4345 static struct tree_backref *find_tree_backref(struct extent_record *rec,
4346 u64 parent, u64 root)
4348 struct list_head *cur = rec->backrefs.next;
4349 struct extent_backref *node;
4350 struct tree_backref *back;
4352 while(cur != &rec->backrefs) {
4353 node = list_entry(cur, struct extent_backref, list);
4357 back = (struct tree_backref *)node;
4359 if (!node->full_backref)
4361 if (parent == back->parent)
4364 if (node->full_backref)
4366 if (back->root == root)
4373 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
4374 u64 parent, u64 root)
4376 struct tree_backref *ref = malloc(sizeof(*ref));
4380 memset(&ref->node, 0, sizeof(ref->node));
4382 ref->parent = parent;
4383 ref->node.full_backref = 1;
4386 ref->node.full_backref = 0;
4388 list_add_tail(&ref->node.list, &rec->backrefs);
4393 static struct data_backref *find_data_backref(struct extent_record *rec,
4394 u64 parent, u64 root,
4395 u64 owner, u64 offset,
4397 u64 disk_bytenr, u64 bytes)
4399 struct list_head *cur = rec->backrefs.next;
4400 struct extent_backref *node;
4401 struct data_backref *back;
4403 while(cur != &rec->backrefs) {
4404 node = list_entry(cur, struct extent_backref, list);
4408 back = (struct data_backref *)node;
4410 if (!node->full_backref)
4412 if (parent == back->parent)
4415 if (node->full_backref)
4417 if (back->root == root && back->owner == owner &&
4418 back->offset == offset) {
4419 if (found_ref && node->found_ref &&
4420 (back->bytes != bytes ||
4421 back->disk_bytenr != disk_bytenr))
4430 static struct data_backref *alloc_data_backref(struct extent_record *rec,
4431 u64 parent, u64 root,
4432 u64 owner, u64 offset,
4435 struct data_backref *ref = malloc(sizeof(*ref));
4439 memset(&ref->node, 0, sizeof(ref->node));
4440 ref->node.is_data = 1;
4443 ref->parent = parent;
4446 ref->node.full_backref = 1;
4450 ref->offset = offset;
4451 ref->node.full_backref = 0;
4453 ref->bytes = max_size;
4456 list_add_tail(&ref->node.list, &rec->backrefs);
4457 if (max_size > rec->max_size)
4458 rec->max_size = max_size;
4462 /* Check if the type of extent matches with its chunk */
4463 static void check_extent_type(struct extent_record *rec)
4465 struct btrfs_block_group_cache *bg_cache;
4467 bg_cache = btrfs_lookup_first_block_group(global_info, rec->start);
4471 /* data extent, check chunk directly*/
4472 if (!rec->metadata) {
4473 if (!(bg_cache->flags & BTRFS_BLOCK_GROUP_DATA))
4474 rec->wrong_chunk_type = 1;
4478 /* metadata extent, check the obvious case first */
4479 if (!(bg_cache->flags & (BTRFS_BLOCK_GROUP_SYSTEM |
4480 BTRFS_BLOCK_GROUP_METADATA))) {
4481 rec->wrong_chunk_type = 1;
4486 * Check SYSTEM extent, as it's also marked as metadata, we can only
4487 * make sure it's a SYSTEM extent by its backref
4489 if (!list_empty(&rec->backrefs)) {
4490 struct extent_backref *node;
4491 struct tree_backref *tback;
4494 node = list_entry(rec->backrefs.next, struct extent_backref,
4496 if (node->is_data) {
4497 /* tree block shouldn't have data backref */
4498 rec->wrong_chunk_type = 1;
4501 tback = container_of(node, struct tree_backref, node);
4503 if (tback->root == BTRFS_CHUNK_TREE_OBJECTID)
4504 bg_type = BTRFS_BLOCK_GROUP_SYSTEM;
4506 bg_type = BTRFS_BLOCK_GROUP_METADATA;
4507 if (!(bg_cache->flags & bg_type))
4508 rec->wrong_chunk_type = 1;
4513 * Allocate a new extent record, fill default values from @tmpl and insert int
4514 * @extent_cache. Caller is supposed to make sure the [start,nr) is not in
4515 * the cache, otherwise it fails.
4517 static int add_extent_rec_nolookup(struct cache_tree *extent_cache,
4518 struct extent_record *tmpl)
4520 struct extent_record *rec;
4523 rec = malloc(sizeof(*rec));
4526 rec->start = tmpl->start;
4527 rec->max_size = tmpl->max_size;
4528 rec->nr = max(tmpl->nr, tmpl->max_size);
4529 rec->found_rec = tmpl->found_rec;
4530 rec->content_checked = tmpl->content_checked;
4531 rec->owner_ref_checked = tmpl->owner_ref_checked;
4532 rec->num_duplicates = 0;
4533 rec->metadata = tmpl->metadata;
4534 rec->flag_block_full_backref = -1;
4535 rec->bad_full_backref = 0;
4536 rec->crossing_stripes = 0;
4537 rec->wrong_chunk_type = 0;
4538 INIT_LIST_HEAD(&rec->backrefs);
4539 INIT_LIST_HEAD(&rec->dups);
4540 INIT_LIST_HEAD(&rec->list);
4547 rec->refs = tmpl->refs;
4549 if (tmpl->extent_item_refs)
4550 rec->extent_item_refs = tmpl->extent_item_refs;
4552 rec->extent_item_refs = 0;
4554 memcpy(&rec->parent_key, &tmpl->parent_key, sizeof(tmpl->parent_key));
4556 if (tmpl->parent_generation)
4557 rec->parent_generation = tmpl->parent_generation;
4559 rec->parent_generation = 0;
4561 rec->cache.start = tmpl->start;
4562 rec->cache.size = tmpl->nr;
4563 ret = insert_cache_extent(extent_cache, &rec->cache);
4565 bytes_used += tmpl->nr;
4568 rec->crossing_stripes = check_crossing_stripes(rec->start,
4570 check_extent_type(rec);
4574 static int add_extent_rec(struct cache_tree *extent_cache,
4575 struct btrfs_key *parent_key, u64 parent_gen,
4576 u64 start, u64 nr, u64 extent_item_refs,
4577 int is_root, int inc_ref, int set_checked,
4578 int metadata, int extent_rec, u64 max_size)
4580 struct extent_record *rec;
4581 struct cache_extent *cache;
4582 struct extent_record tmpl;
4586 cache = lookup_cache_extent(extent_cache, start, nr);
4588 rec = container_of(cache, struct extent_record, cache);
4592 rec->nr = max(nr, max_size);
4595 * We need to make sure to reset nr to whatever the extent
4596 * record says was the real size, this way we can compare it to
4600 if (start != rec->start || rec->found_rec) {
4601 struct extent_record *tmp;
4604 if (list_empty(&rec->list))
4605 list_add_tail(&rec->list,
4606 &duplicate_extents);
4609 * We have to do this song and dance in case we
4610 * find an extent record that falls inside of
4611 * our current extent record but does not have
4612 * the same objectid.
4614 tmp = malloc(sizeof(*tmp));
4618 tmp->max_size = max_size;
4621 tmp->metadata = metadata;
4622 tmp->extent_item_refs = extent_item_refs;
4623 INIT_LIST_HEAD(&tmp->list);
4624 list_add_tail(&tmp->list, &rec->dups);
4625 rec->num_duplicates++;
4632 if (extent_item_refs && !dup) {
4633 if (rec->extent_item_refs) {
4634 fprintf(stderr, "block %llu rec "
4635 "extent_item_refs %llu, passed %llu\n",
4636 (unsigned long long)start,
4637 (unsigned long long)
4638 rec->extent_item_refs,
4639 (unsigned long long)extent_item_refs);
4641 rec->extent_item_refs = extent_item_refs;
4646 rec->content_checked = 1;
4647 rec->owner_ref_checked = 1;
4651 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
4653 rec->parent_generation = parent_gen;
4655 if (rec->max_size < max_size)
4656 rec->max_size = max_size;
4659 * A metadata extent can't cross stripe_len boundary, otherwise
4660 * kernel scrub won't be able to handle it.
4661 * As now stripe_len is fixed to BTRFS_STRIPE_LEN, just check
4665 rec->crossing_stripes = check_crossing_stripes(
4666 rec->start, rec->max_size);
4667 check_extent_type(rec);
4668 maybe_free_extent_rec(extent_cache, rec);
4672 memset(&tmpl, 0, sizeof(tmpl));
4675 btrfs_cpu_key_to_disk(&tmpl.parent_key, parent_key);
4676 tmpl.parent_generation = parent_gen;
4679 tmpl.extent_item_refs = extent_item_refs;
4680 tmpl.is_root = is_root;
4681 tmpl.metadata = metadata;
4682 tmpl.found_rec = extent_rec;
4683 tmpl.max_size = max_size;
4684 tmpl.content_checked = set_checked;
4685 tmpl.owner_ref_checked = set_checked;
4686 tmpl.refs = !!inc_ref;
4688 ret = add_extent_rec_nolookup(extent_cache, &tmpl);
4693 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
4694 u64 parent, u64 root, int found_ref)
4696 struct extent_record *rec;
4697 struct tree_backref *back;
4698 struct cache_extent *cache;
4700 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4702 struct extent_record tmpl;
4704 memset(&tmpl, 0, sizeof(tmpl));
4705 tmpl.start = bytenr;
4709 add_extent_rec_nolookup(extent_cache, &tmpl);
4711 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4716 rec = container_of(cache, struct extent_record, cache);
4717 if (rec->start != bytenr) {
4721 back = find_tree_backref(rec, parent, root);
4723 back = alloc_tree_backref(rec, parent, root);
4728 if (back->node.found_ref) {
4729 fprintf(stderr, "Extent back ref already exists "
4730 "for %llu parent %llu root %llu \n",
4731 (unsigned long long)bytenr,
4732 (unsigned long long)parent,
4733 (unsigned long long)root);
4735 back->node.found_ref = 1;
4737 if (back->node.found_extent_tree) {
4738 fprintf(stderr, "Extent back ref already exists "
4739 "for %llu parent %llu root %llu \n",
4740 (unsigned long long)bytenr,
4741 (unsigned long long)parent,
4742 (unsigned long long)root);
4744 back->node.found_extent_tree = 1;
4746 check_extent_type(rec);
4747 maybe_free_extent_rec(extent_cache, rec);
4751 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
4752 u64 parent, u64 root, u64 owner, u64 offset,
4753 u32 num_refs, int found_ref, u64 max_size)
4755 struct extent_record *rec;
4756 struct data_backref *back;
4757 struct cache_extent *cache;
4759 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4761 struct extent_record tmpl;
4763 memset(&tmpl, 0, sizeof(tmpl));
4764 tmpl.start = bytenr;
4766 tmpl.max_size = max_size;
4768 add_extent_rec_nolookup(extent_cache, &tmpl);
4770 cache = lookup_cache_extent(extent_cache, bytenr, 1);
4775 rec = container_of(cache, struct extent_record, cache);
4776 if (rec->max_size < max_size)
4777 rec->max_size = max_size;
4780 * If found_ref is set then max_size is the real size and must match the
4781 * existing refs. So if we have already found a ref then we need to
4782 * make sure that this ref matches the existing one, otherwise we need
4783 * to add a new backref so we can notice that the backrefs don't match
4784 * and we need to figure out who is telling the truth. This is to
4785 * account for that awful fsync bug I introduced where we'd end up with
4786 * a btrfs_file_extent_item that would have its length include multiple
4787 * prealloc extents or point inside of a prealloc extent.
4789 back = find_data_backref(rec, parent, root, owner, offset, found_ref,
4792 back = alloc_data_backref(rec, parent, root, owner, offset,
4798 BUG_ON(num_refs != 1);
4799 if (back->node.found_ref)
4800 BUG_ON(back->bytes != max_size);
4801 back->node.found_ref = 1;
4802 back->found_ref += 1;
4803 back->bytes = max_size;
4804 back->disk_bytenr = bytenr;
4806 rec->content_checked = 1;
4807 rec->owner_ref_checked = 1;
4809 if (back->node.found_extent_tree) {
4810 fprintf(stderr, "Extent back ref already exists "
4811 "for %llu parent %llu root %llu "
4812 "owner %llu offset %llu num_refs %lu\n",
4813 (unsigned long long)bytenr,
4814 (unsigned long long)parent,
4815 (unsigned long long)root,
4816 (unsigned long long)owner,
4817 (unsigned long long)offset,
4818 (unsigned long)num_refs);
4820 back->num_refs = num_refs;
4821 back->node.found_extent_tree = 1;
4823 maybe_free_extent_rec(extent_cache, rec);
4827 static int add_pending(struct cache_tree *pending,
4828 struct cache_tree *seen, u64 bytenr, u32 size)
4831 ret = add_cache_extent(seen, bytenr, size);
4834 add_cache_extent(pending, bytenr, size);
4838 static int pick_next_pending(struct cache_tree *pending,
4839 struct cache_tree *reada,
4840 struct cache_tree *nodes,
4841 u64 last, struct block_info *bits, int bits_nr,
4844 unsigned long node_start = last;
4845 struct cache_extent *cache;
4848 cache = search_cache_extent(reada, 0);
4850 bits[0].start = cache->start;
4851 bits[0].size = cache->size;
4856 if (node_start > 32768)
4857 node_start -= 32768;
4859 cache = search_cache_extent(nodes, node_start);
4861 cache = search_cache_extent(nodes, 0);
4864 cache = search_cache_extent(pending, 0);
4869 bits[ret].start = cache->start;
4870 bits[ret].size = cache->size;
4871 cache = next_cache_extent(cache);
4873 } while (cache && ret < bits_nr);
4879 bits[ret].start = cache->start;
4880 bits[ret].size = cache->size;
4881 cache = next_cache_extent(cache);
4883 } while (cache && ret < bits_nr);
4885 if (bits_nr - ret > 8) {
4886 u64 lookup = bits[0].start + bits[0].size;
4887 struct cache_extent *next;
4888 next = search_cache_extent(pending, lookup);
4890 if (next->start - lookup > 32768)
4892 bits[ret].start = next->start;
4893 bits[ret].size = next->size;
4894 lookup = next->start + next->size;
4898 next = next_cache_extent(next);
4906 static void free_chunk_record(struct cache_extent *cache)
4908 struct chunk_record *rec;
4910 rec = container_of(cache, struct chunk_record, cache);
4911 list_del_init(&rec->list);
4912 list_del_init(&rec->dextents);
4916 void free_chunk_cache_tree(struct cache_tree *chunk_cache)
4918 cache_tree_free_extents(chunk_cache, free_chunk_record);
4921 static void free_device_record(struct rb_node *node)
4923 struct device_record *rec;
4925 rec = container_of(node, struct device_record, node);
4929 FREE_RB_BASED_TREE(device_cache, free_device_record);
4931 int insert_block_group_record(struct block_group_tree *tree,
4932 struct block_group_record *bg_rec)
4936 ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
4940 list_add_tail(&bg_rec->list, &tree->block_groups);
4944 static void free_block_group_record(struct cache_extent *cache)
4946 struct block_group_record *rec;
4948 rec = container_of(cache, struct block_group_record, cache);
4949 list_del_init(&rec->list);
4953 void free_block_group_tree(struct block_group_tree *tree)
4955 cache_tree_free_extents(&tree->tree, free_block_group_record);
4958 int insert_device_extent_record(struct device_extent_tree *tree,
4959 struct device_extent_record *de_rec)
4964 * Device extent is a bit different from the other extents, because
4965 * the extents which belong to the different devices may have the
4966 * same start and size, so we need use the special extent cache
4967 * search/insert functions.
4969 ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
4973 list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
4974 list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
4978 static void free_device_extent_record(struct cache_extent *cache)
4980 struct device_extent_record *rec;
4982 rec = container_of(cache, struct device_extent_record, cache);
4983 if (!list_empty(&rec->chunk_list))
4984 list_del_init(&rec->chunk_list);
4985 if (!list_empty(&rec->device_list))
4986 list_del_init(&rec->device_list);
4990 void free_device_extent_tree(struct device_extent_tree *tree)
4992 cache_tree_free_extents(&tree->tree, free_device_extent_record);
4995 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4996 static int process_extent_ref_v0(struct cache_tree *extent_cache,
4997 struct extent_buffer *leaf, int slot)
4999 struct btrfs_extent_ref_v0 *ref0;
5000 struct btrfs_key key;
5002 btrfs_item_key_to_cpu(leaf, &key, slot);
5003 ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
5004 if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
5005 add_tree_backref(extent_cache, key.objectid, key.offset, 0, 0);
5007 add_data_backref(extent_cache, key.objectid, key.offset, 0,
5008 0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
5014 struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
5015 struct btrfs_key *key,
5018 struct btrfs_chunk *ptr;
5019 struct chunk_record *rec;
5022 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
5023 num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
5025 rec = calloc(1, btrfs_chunk_record_size(num_stripes));
5027 fprintf(stderr, "memory allocation failed\n");
5031 INIT_LIST_HEAD(&rec->list);
5032 INIT_LIST_HEAD(&rec->dextents);
5035 rec->cache.start = key->offset;
5036 rec->cache.size = btrfs_chunk_length(leaf, ptr);
5038 rec->generation = btrfs_header_generation(leaf);
5040 rec->objectid = key->objectid;
5041 rec->type = key->type;
5042 rec->offset = key->offset;
5044 rec->length = rec->cache.size;
5045 rec->owner = btrfs_chunk_owner(leaf, ptr);
5046 rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
5047 rec->type_flags = btrfs_chunk_type(leaf, ptr);
5048 rec->io_width = btrfs_chunk_io_width(leaf, ptr);
5049 rec->io_align = btrfs_chunk_io_align(leaf, ptr);
5050 rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
5051 rec->num_stripes = num_stripes;
5052 rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
5054 for (i = 0; i < rec->num_stripes; ++i) {
5055 rec->stripes[i].devid =
5056 btrfs_stripe_devid_nr(leaf, ptr, i);
5057 rec->stripes[i].offset =
5058 btrfs_stripe_offset_nr(leaf, ptr, i);
5059 read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
5060 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
5067 static int process_chunk_item(struct cache_tree *chunk_cache,
5068 struct btrfs_key *key, struct extent_buffer *eb,
5071 struct chunk_record *rec;
5074 rec = btrfs_new_chunk_record(eb, key, slot);
5075 ret = insert_cache_extent(chunk_cache, &rec->cache);
5077 fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
5078 rec->offset, rec->length);
5085 static int process_device_item(struct rb_root *dev_cache,
5086 struct btrfs_key *key, struct extent_buffer *eb, int slot)
5088 struct btrfs_dev_item *ptr;
5089 struct device_record *rec;
5092 ptr = btrfs_item_ptr(eb,
5093 slot, struct btrfs_dev_item);
5095 rec = malloc(sizeof(*rec));
5097 fprintf(stderr, "memory allocation failed\n");
5101 rec->devid = key->offset;
5102 rec->generation = btrfs_header_generation(eb);
5104 rec->objectid = key->objectid;
5105 rec->type = key->type;
5106 rec->offset = key->offset;
5108 rec->devid = btrfs_device_id(eb, ptr);
5109 rec->total_byte = btrfs_device_total_bytes(eb, ptr);
5110 rec->byte_used = btrfs_device_bytes_used(eb, ptr);
5112 ret = rb_insert(dev_cache, &rec->node, device_record_compare);
5114 fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
5121 struct block_group_record *
5122 btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,
5125 struct btrfs_block_group_item *ptr;
5126 struct block_group_record *rec;
5128 rec = calloc(1, sizeof(*rec));
5130 fprintf(stderr, "memory allocation failed\n");
5134 rec->cache.start = key->objectid;
5135 rec->cache.size = key->offset;
5137 rec->generation = btrfs_header_generation(leaf);
5139 rec->objectid = key->objectid;
5140 rec->type = key->type;
5141 rec->offset = key->offset;
5143 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_block_group_item);
5144 rec->flags = btrfs_disk_block_group_flags(leaf, ptr);
5146 INIT_LIST_HEAD(&rec->list);
5151 static int process_block_group_item(struct block_group_tree *block_group_cache,
5152 struct btrfs_key *key,
5153 struct extent_buffer *eb, int slot)
5155 struct block_group_record *rec;
5158 rec = btrfs_new_block_group_record(eb, key, slot);
5159 ret = insert_block_group_record(block_group_cache, rec);
5161 fprintf(stderr, "Block Group[%llu, %llu] existed.\n",
5162 rec->objectid, rec->offset);
5169 struct device_extent_record *
5170 btrfs_new_device_extent_record(struct extent_buffer *leaf,
5171 struct btrfs_key *key, int slot)
5173 struct device_extent_record *rec;
5174 struct btrfs_dev_extent *ptr;
5176 rec = calloc(1, sizeof(*rec));
5178 fprintf(stderr, "memory allocation failed\n");
5182 rec->cache.objectid = key->objectid;
5183 rec->cache.start = key->offset;
5185 rec->generation = btrfs_header_generation(leaf);
5187 rec->objectid = key->objectid;
5188 rec->type = key->type;
5189 rec->offset = key->offset;
5191 ptr = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
5192 rec->chunk_objecteid =
5193 btrfs_dev_extent_chunk_objectid(leaf, ptr);
5195 btrfs_dev_extent_chunk_offset(leaf, ptr);
5196 rec->length = btrfs_dev_extent_length(leaf, ptr);
5197 rec->cache.size = rec->length;
5199 INIT_LIST_HEAD(&rec->chunk_list);
5200 INIT_LIST_HEAD(&rec->device_list);
5206 process_device_extent_item(struct device_extent_tree *dev_extent_cache,
5207 struct btrfs_key *key, struct extent_buffer *eb,
5210 struct device_extent_record *rec;
5213 rec = btrfs_new_device_extent_record(eb, key, slot);
5214 ret = insert_device_extent_record(dev_extent_cache, rec);
5217 "Device extent[%llu, %llu, %llu] existed.\n",
5218 rec->objectid, rec->offset, rec->length);
5225 static int process_extent_item(struct btrfs_root *root,
5226 struct cache_tree *extent_cache,
5227 struct extent_buffer *eb, int slot)
5229 struct btrfs_extent_item *ei;
5230 struct btrfs_extent_inline_ref *iref;
5231 struct btrfs_extent_data_ref *dref;
5232 struct btrfs_shared_data_ref *sref;
5233 struct btrfs_key key;
5237 u32 item_size = btrfs_item_size_nr(eb, slot);
5243 btrfs_item_key_to_cpu(eb, &key, slot);
5245 if (key.type == BTRFS_METADATA_ITEM_KEY) {
5247 num_bytes = root->nodesize;
5249 num_bytes = key.offset;
5252 if (item_size < sizeof(*ei)) {
5253 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5254 struct btrfs_extent_item_v0 *ei0;
5255 BUG_ON(item_size != sizeof(*ei0));
5256 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
5257 refs = btrfs_extent_refs_v0(eb, ei0);
5261 return add_extent_rec(extent_cache, NULL, 0, key.objectid,
5262 num_bytes, refs, 0, 0, 0, metadata, 1,
5266 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
5267 refs = btrfs_extent_refs(eb, ei);
5268 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
5273 add_extent_rec(extent_cache, NULL, 0, key.objectid, num_bytes,
5274 refs, 0, 0, 0, metadata, 1, num_bytes);
5276 ptr = (unsigned long)(ei + 1);
5277 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
5278 key.type == BTRFS_EXTENT_ITEM_KEY)
5279 ptr += sizeof(struct btrfs_tree_block_info);
5281 end = (unsigned long)ei + item_size;
5283 iref = (struct btrfs_extent_inline_ref *)ptr;
5284 type = btrfs_extent_inline_ref_type(eb, iref);
5285 offset = btrfs_extent_inline_ref_offset(eb, iref);
5287 case BTRFS_TREE_BLOCK_REF_KEY:
5288 add_tree_backref(extent_cache, key.objectid,
5291 case BTRFS_SHARED_BLOCK_REF_KEY:
5292 add_tree_backref(extent_cache, key.objectid,
5295 case BTRFS_EXTENT_DATA_REF_KEY:
5296 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
5297 add_data_backref(extent_cache, key.objectid, 0,
5298 btrfs_extent_data_ref_root(eb, dref),
5299 btrfs_extent_data_ref_objectid(eb,
5301 btrfs_extent_data_ref_offset(eb, dref),
5302 btrfs_extent_data_ref_count(eb, dref),
5305 case BTRFS_SHARED_DATA_REF_KEY:
5306 sref = (struct btrfs_shared_data_ref *)(iref + 1);
5307 add_data_backref(extent_cache, key.objectid, offset,
5309 btrfs_shared_data_ref_count(eb, sref),
5313 fprintf(stderr, "corrupt extent record: key %Lu %u %Lu\n",
5314 key.objectid, key.type, num_bytes);
5317 ptr += btrfs_extent_inline_ref_size(type);
5324 static int check_cache_range(struct btrfs_root *root,
5325 struct btrfs_block_group_cache *cache,
5326 u64 offset, u64 bytes)
5328 struct btrfs_free_space *entry;
5334 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
5335 bytenr = btrfs_sb_offset(i);
5336 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
5337 cache->key.objectid, bytenr, 0,
5338 &logical, &nr, &stripe_len);
5343 if (logical[nr] + stripe_len <= offset)
5345 if (offset + bytes <= logical[nr])
5347 if (logical[nr] == offset) {
5348 if (stripe_len >= bytes) {
5352 bytes -= stripe_len;
5353 offset += stripe_len;
5354 } else if (logical[nr] < offset) {
5355 if (logical[nr] + stripe_len >=
5360 bytes = (offset + bytes) -
5361 (logical[nr] + stripe_len);
5362 offset = logical[nr] + stripe_len;
5365 * Could be tricky, the super may land in the
5366 * middle of the area we're checking. First
5367 * check the easiest case, it's at the end.
5369 if (logical[nr] + stripe_len >=
5371 bytes = logical[nr] - offset;
5375 /* Check the left side */
5376 ret = check_cache_range(root, cache,
5378 logical[nr] - offset);
5384 /* Now we continue with the right side */
5385 bytes = (offset + bytes) -
5386 (logical[nr] + stripe_len);
5387 offset = logical[nr] + stripe_len;
5394 entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes);
5396 fprintf(stderr, "There is no free space entry for %Lu-%Lu\n",
5397 offset, offset+bytes);
5401 if (entry->offset != offset) {
5402 fprintf(stderr, "Wanted offset %Lu, found %Lu\n", offset,
5407 if (entry->bytes != bytes) {
5408 fprintf(stderr, "Wanted bytes %Lu, found %Lu for off %Lu\n",
5409 bytes, entry->bytes, offset);
5413 unlink_free_space(cache->free_space_ctl, entry);
5418 static int verify_space_cache(struct btrfs_root *root,
5419 struct btrfs_block_group_cache *cache)
5421 struct btrfs_path *path;
5422 struct extent_buffer *leaf;
5423 struct btrfs_key key;
5427 path = btrfs_alloc_path();
5431 root = root->fs_info->extent_root;
5433 last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
5435 key.objectid = last;
5437 key.type = BTRFS_EXTENT_ITEM_KEY;
5439 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5444 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
5445 ret = btrfs_next_leaf(root, path);
5453 leaf = path->nodes[0];
5454 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5455 if (key.objectid >= cache->key.offset + cache->key.objectid)
5457 if (key.type != BTRFS_EXTENT_ITEM_KEY &&
5458 key.type != BTRFS_METADATA_ITEM_KEY) {
5463 if (last == key.objectid) {
5464 if (key.type == BTRFS_EXTENT_ITEM_KEY)
5465 last = key.objectid + key.offset;
5467 last = key.objectid + root->nodesize;
5472 ret = check_cache_range(root, cache, last,
5473 key.objectid - last);
5476 if (key.type == BTRFS_EXTENT_ITEM_KEY)
5477 last = key.objectid + key.offset;
5479 last = key.objectid + root->nodesize;
5483 if (last < cache->key.objectid + cache->key.offset)
5484 ret = check_cache_range(root, cache, last,
5485 cache->key.objectid +
5486 cache->key.offset - last);
5489 btrfs_free_path(path);
5492 !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) {
5493 fprintf(stderr, "There are still entries left in the space "
5501 static int check_space_cache(struct btrfs_root *root)
5503 struct btrfs_block_group_cache *cache;
5504 u64 start = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
5508 if (btrfs_super_cache_generation(root->fs_info->super_copy) != -1ULL &&
5509 btrfs_super_generation(root->fs_info->super_copy) !=
5510 btrfs_super_cache_generation(root->fs_info->super_copy)) {
5511 printf("cache and super generation don't match, space cache "
5512 "will be invalidated\n");
5516 if (ctx.progress_enabled) {
5517 ctx.tp = TASK_FREE_SPACE;
5518 task_start(ctx.info);
5522 cache = btrfs_lookup_first_block_group(root->fs_info, start);
5526 start = cache->key.objectid + cache->key.offset;
5527 if (!cache->free_space_ctl) {
5528 if (btrfs_init_free_space_ctl(cache,
5529 root->sectorsize)) {
5534 btrfs_remove_free_space_cache(cache);
5537 if (btrfs_fs_compat_ro(root->fs_info,
5538 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) {
5539 ret = exclude_super_stripes(root, cache);
5541 fprintf(stderr, "could not exclude super stripes: %s\n",
5546 ret = load_free_space_tree(root->fs_info, cache);
5547 free_excluded_extents(root, cache);
5549 fprintf(stderr, "could not load free space tree: %s\n",
5556 ret = load_free_space_cache(root->fs_info, cache);
5561 ret = verify_space_cache(root, cache);
5563 fprintf(stderr, "cache appears valid but isnt %Lu\n",
5564 cache->key.objectid);
5569 task_stop(ctx.info);
5571 return error ? -EINVAL : 0;
5574 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
5575 u64 num_bytes, unsigned long leaf_offset,
5576 struct extent_buffer *eb) {
5579 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
5581 unsigned long csum_offset;
5585 u64 data_checked = 0;
5591 if (num_bytes % root->sectorsize)
5594 data = malloc(num_bytes);
5598 while (offset < num_bytes) {
5601 read_len = num_bytes - offset;
5602 /* read as much space once a time */
5603 ret = read_extent_data(root, data + offset,
5604 bytenr + offset, &read_len, mirror);
5608 /* verify every 4k data's checksum */
5609 while (data_checked < read_len) {
5611 tmp = offset + data_checked;
5613 csum = btrfs_csum_data(NULL, (char *)data + tmp,
5614 csum, root->sectorsize);
5615 btrfs_csum_final(csum, (char *)&csum);
5617 csum_offset = leaf_offset +
5618 tmp / root->sectorsize * csum_size;
5619 read_extent_buffer(eb, (char *)&csum_expected,
5620 csum_offset, csum_size);
5621 /* try another mirror */
5622 if (csum != csum_expected) {
5623 fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
5624 mirror, bytenr + tmp,
5625 csum, csum_expected);
5626 num_copies = btrfs_num_copies(
5627 &root->fs_info->mapping_tree,
5629 if (mirror < num_copies - 1) {
5634 data_checked += root->sectorsize;
5643 static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
5646 struct btrfs_path *path;
5647 struct extent_buffer *leaf;
5648 struct btrfs_key key;
5651 path = btrfs_alloc_path();
5653 fprintf(stderr, "Error allocing path\n");
5657 key.objectid = bytenr;
5658 key.type = BTRFS_EXTENT_ITEM_KEY;
5659 key.offset = (u64)-1;
5662 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
5665 fprintf(stderr, "Error looking up extent record %d\n", ret);
5666 btrfs_free_path(path);
5669 if (path->slots[0] > 0) {
5672 ret = btrfs_prev_leaf(root, path);
5675 } else if (ret > 0) {
5682 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
5685 * Block group items come before extent items if they have the same
5686 * bytenr, so walk back one more just in case. Dear future traveler,
5687 * first congrats on mastering time travel. Now if it's not too much
5688 * trouble could you go back to 2006 and tell Chris to make the
5689 * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
5690 * EXTENT_ITEM_KEY please?
5692 while (key.type > BTRFS_EXTENT_ITEM_KEY) {
5693 if (path->slots[0] > 0) {
5696 ret = btrfs_prev_leaf(root, path);
5699 } else if (ret > 0) {
5704 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
5708 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
5709 ret = btrfs_next_leaf(root, path);
5711 fprintf(stderr, "Error going to next leaf "
5713 btrfs_free_path(path);
5719 leaf = path->nodes[0];
5720 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5721 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
5725 if (key.objectid + key.offset < bytenr) {
5729 if (key.objectid > bytenr + num_bytes)
5732 if (key.objectid == bytenr) {
5733 if (key.offset >= num_bytes) {
5737 num_bytes -= key.offset;
5738 bytenr += key.offset;
5739 } else if (key.objectid < bytenr) {
5740 if (key.objectid + key.offset >= bytenr + num_bytes) {
5744 num_bytes = (bytenr + num_bytes) -
5745 (key.objectid + key.offset);
5746 bytenr = key.objectid + key.offset;
5748 if (key.objectid + key.offset < bytenr + num_bytes) {
5749 u64 new_start = key.objectid + key.offset;
5750 u64 new_bytes = bytenr + num_bytes - new_start;
5753 * Weird case, the extent is in the middle of
5754 * our range, we'll have to search one side
5755 * and then the other. Not sure if this happens
5756 * in real life, but no harm in coding it up
5757 * anyway just in case.
5759 btrfs_release_path(path);
5760 ret = check_extent_exists(root, new_start,
5763 fprintf(stderr, "Right section didn't "
5767 num_bytes = key.objectid - bytenr;
5770 num_bytes = key.objectid - bytenr;
5777 if (num_bytes && !ret) {
5778 fprintf(stderr, "There are no extents for csum range "
5779 "%Lu-%Lu\n", bytenr, bytenr+num_bytes);
5783 btrfs_free_path(path);
5787 static int check_csums(struct btrfs_root *root)
5789 struct btrfs_path *path;
5790 struct extent_buffer *leaf;
5791 struct btrfs_key key;
5792 u64 offset = 0, num_bytes = 0;
5793 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
5797 unsigned long leaf_offset;
5799 root = root->fs_info->csum_root;
5800 if (!extent_buffer_uptodate(root->node)) {
5801 fprintf(stderr, "No valid csum tree found\n");
5805 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
5806 key.type = BTRFS_EXTENT_CSUM_KEY;
5809 path = btrfs_alloc_path();
5813 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5815 fprintf(stderr, "Error searching csum tree %d\n", ret);
5816 btrfs_free_path(path);
5820 if (ret > 0 && path->slots[0])
5825 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
5826 ret = btrfs_next_leaf(root, path);
5828 fprintf(stderr, "Error going to next leaf "
5835 leaf = path->nodes[0];
5837 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5838 if (key.type != BTRFS_EXTENT_CSUM_KEY) {
5843 data_len = (btrfs_item_size_nr(leaf, path->slots[0]) /
5844 csum_size) * root->sectorsize;
5845 if (!check_data_csum)
5846 goto skip_csum_check;
5847 leaf_offset = btrfs_item_ptr_offset(leaf, path->slots[0]);
5848 ret = check_extent_csums(root, key.offset, data_len,
5854 offset = key.offset;
5855 } else if (key.offset != offset + num_bytes) {
5856 ret = check_extent_exists(root, offset, num_bytes);
5858 fprintf(stderr, "Csum exists for %Lu-%Lu but "
5859 "there is no extent record\n",
5860 offset, offset+num_bytes);
5863 offset = key.offset;
5866 num_bytes += data_len;
5870 btrfs_free_path(path);
5874 static int is_dropped_key(struct btrfs_key *key,
5875 struct btrfs_key *drop_key) {
5876 if (key->objectid < drop_key->objectid)
5878 else if (key->objectid == drop_key->objectid) {
5879 if (key->type < drop_key->type)
5881 else if (key->type == drop_key->type) {
5882 if (key->offset < drop_key->offset)
5890 * Here are the rules for FULL_BACKREF.
5892 * 1) If BTRFS_HEADER_FLAG_RELOC is set then we have FULL_BACKREF set.
5893 * 2) If btrfs_header_owner(buf) no longer points to buf then we have
5895 * 3) We cow'ed the block walking down a reloc tree. This is impossible to tell
5896 * if it happened after the relocation occurred since we'll have dropped the
5897 * reloc root, so it's entirely possible to have FULL_BACKREF set on buf and
5898 * have no real way to know for sure.
5900 * We process the blocks one root at a time, and we start from the lowest root
5901 * objectid and go to the highest. So we can just lookup the owner backref for
5902 * the record and if we don't find it then we know it doesn't exist and we have
5905 * FIXME: if we ever start reclaiming root objectid's then we need to fix this
5906 * assumption and simply indicate that we _think_ that the FULL BACKREF needs to
5907 * be set or not and then we can check later once we've gathered all the refs.
5909 static int calc_extent_flag(struct btrfs_root *root,
5910 struct cache_tree *extent_cache,
5911 struct extent_buffer *buf,
5912 struct root_item_record *ri,
5915 struct extent_record *rec;
5916 struct cache_extent *cache;
5917 struct tree_backref *tback;
5920 cache = lookup_cache_extent(extent_cache, buf->start, 1);
5921 /* we have added this extent before */
5923 rec = container_of(cache, struct extent_record, cache);
5926 * Except file/reloc tree, we can not have
5929 if (ri->objectid < BTRFS_FIRST_FREE_OBJECTID)
5934 if (buf->start == ri->bytenr)
5937 if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
5940 owner = btrfs_header_owner(buf);
5941 if (owner == ri->objectid)
5944 tback = find_tree_backref(rec, 0, owner);
5949 if (rec->flag_block_full_backref != -1 &&
5950 rec->flag_block_full_backref != 0)
5951 rec->bad_full_backref = 1;
5954 *flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5955 if (rec->flag_block_full_backref != -1 &&
5956 rec->flag_block_full_backref != 1)
5957 rec->bad_full_backref = 1;
5961 static int run_next_block(struct btrfs_root *root,
5962 struct block_info *bits,
5965 struct cache_tree *pending,
5966 struct cache_tree *seen,
5967 struct cache_tree *reada,
5968 struct cache_tree *nodes,
5969 struct cache_tree *extent_cache,
5970 struct cache_tree *chunk_cache,
5971 struct rb_root *dev_cache,
5972 struct block_group_tree *block_group_cache,
5973 struct device_extent_tree *dev_extent_cache,
5974 struct root_item_record *ri)
5976 struct extent_buffer *buf;
5977 struct extent_record *rec = NULL;
5988 struct btrfs_key key;
5989 struct cache_extent *cache;
5992 nritems = pick_next_pending(pending, reada, nodes, *last, bits,
5993 bits_nr, &reada_bits);
5998 for(i = 0; i < nritems; i++) {
5999 ret = add_cache_extent(reada, bits[i].start,
6004 /* fixme, get the parent transid */
6005 readahead_tree_block(root, bits[i].start,
6009 *last = bits[0].start;
6010 bytenr = bits[0].start;
6011 size = bits[0].size;
6013 cache = lookup_cache_extent(pending, bytenr, size);
6015 remove_cache_extent(pending, cache);
6018 cache = lookup_cache_extent(reada, bytenr, size);
6020 remove_cache_extent(reada, cache);
6023 cache = lookup_cache_extent(nodes, bytenr, size);
6025 remove_cache_extent(nodes, cache);
6028 cache = lookup_cache_extent(extent_cache, bytenr, size);
6030 rec = container_of(cache, struct extent_record, cache);
6031 gen = rec->parent_generation;
6034 /* fixme, get the real parent transid */
6035 buf = read_tree_block(root, bytenr, size, gen);
6036 if (!extent_buffer_uptodate(buf)) {
6037 record_bad_block_io(root->fs_info,
6038 extent_cache, bytenr, size);
6042 nritems = btrfs_header_nritems(buf);
6045 if (!init_extent_tree) {
6046 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
6047 btrfs_header_level(buf), 1, NULL,
6050 ret = calc_extent_flag(root, extent_cache, buf, ri, &flags);
6052 fprintf(stderr, "Couldn't calc extent flags\n");
6053 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
6058 ret = calc_extent_flag(root, extent_cache, buf, ri, &flags);
6060 fprintf(stderr, "Couldn't calc extent flags\n");
6061 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
6065 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
6067 ri->objectid != BTRFS_TREE_RELOC_OBJECTID &&
6068 ri->objectid == btrfs_header_owner(buf)) {
6070 * Ok we got to this block from it's original owner and
6071 * we have FULL_BACKREF set. Relocation can leave
6072 * converted blocks over so this is altogether possible,
6073 * however it's not possible if the generation > the
6074 * last snapshot, so check for this case.
6076 if (!btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC) &&
6077 btrfs_header_generation(buf) > ri->last_snapshot) {
6078 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
6079 rec->bad_full_backref = 1;
6084 (ri->objectid == BTRFS_TREE_RELOC_OBJECTID ||
6085 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) {
6086 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
6087 rec->bad_full_backref = 1;
6091 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
6092 rec->flag_block_full_backref = 1;
6096 rec->flag_block_full_backref = 0;
6098 owner = btrfs_header_owner(buf);
6101 ret = check_block(root, extent_cache, buf, flags);
6105 if (btrfs_is_leaf(buf)) {
6106 btree_space_waste += btrfs_leaf_free_space(root, buf);
6107 for (i = 0; i < nritems; i++) {
6108 struct btrfs_file_extent_item *fi;
6109 btrfs_item_key_to_cpu(buf, &key, i);
6110 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
6111 process_extent_item(root, extent_cache, buf,
6115 if (key.type == BTRFS_METADATA_ITEM_KEY) {
6116 process_extent_item(root, extent_cache, buf,
6120 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
6122 btrfs_item_size_nr(buf, i);
6125 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
6126 process_chunk_item(chunk_cache, &key, buf, i);
6129 if (key.type == BTRFS_DEV_ITEM_KEY) {
6130 process_device_item(dev_cache, &key, buf, i);
6133 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
6134 process_block_group_item(block_group_cache,
6138 if (key.type == BTRFS_DEV_EXTENT_KEY) {
6139 process_device_extent_item(dev_extent_cache,
6144 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
6145 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
6146 process_extent_ref_v0(extent_cache, buf, i);
6153 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
6154 add_tree_backref(extent_cache, key.objectid, 0,
6158 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
6159 add_tree_backref(extent_cache, key.objectid,
6163 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
6164 struct btrfs_extent_data_ref *ref;
6165 ref = btrfs_item_ptr(buf, i,
6166 struct btrfs_extent_data_ref);
6167 add_data_backref(extent_cache,
6169 btrfs_extent_data_ref_root(buf, ref),
6170 btrfs_extent_data_ref_objectid(buf,
6172 btrfs_extent_data_ref_offset(buf, ref),
6173 btrfs_extent_data_ref_count(buf, ref),
6174 0, root->sectorsize);
6177 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
6178 struct btrfs_shared_data_ref *ref;
6179 ref = btrfs_item_ptr(buf, i,
6180 struct btrfs_shared_data_ref);
6181 add_data_backref(extent_cache,
6182 key.objectid, key.offset, 0, 0, 0,
6183 btrfs_shared_data_ref_count(buf, ref),
6184 0, root->sectorsize);
6187 if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
6188 struct bad_item *bad;
6190 if (key.objectid == BTRFS_ORPHAN_OBJECTID)
6194 bad = malloc(sizeof(struct bad_item));
6197 INIT_LIST_HEAD(&bad->list);
6198 memcpy(&bad->key, &key,
6199 sizeof(struct btrfs_key));
6200 bad->root_id = owner;
6201 list_add_tail(&bad->list, &delete_items);
6204 if (key.type != BTRFS_EXTENT_DATA_KEY)
6206 fi = btrfs_item_ptr(buf, i,
6207 struct btrfs_file_extent_item);
6208 if (btrfs_file_extent_type(buf, fi) ==
6209 BTRFS_FILE_EXTENT_INLINE)
6211 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
6214 data_bytes_allocated +=
6215 btrfs_file_extent_disk_num_bytes(buf, fi);
6216 if (data_bytes_allocated < root->sectorsize) {
6219 data_bytes_referenced +=
6220 btrfs_file_extent_num_bytes(buf, fi);
6221 add_data_backref(extent_cache,
6222 btrfs_file_extent_disk_bytenr(buf, fi),
6223 parent, owner, key.objectid, key.offset -
6224 btrfs_file_extent_offset(buf, fi), 1, 1,
6225 btrfs_file_extent_disk_num_bytes(buf, fi));
6229 struct btrfs_key first_key;
6231 first_key.objectid = 0;
6234 btrfs_item_key_to_cpu(buf, &first_key, 0);
6235 level = btrfs_header_level(buf);
6236 for (i = 0; i < nritems; i++) {
6237 ptr = btrfs_node_blockptr(buf, i);
6238 size = root->nodesize;
6239 btrfs_node_key_to_cpu(buf, &key, i);
6241 if ((level == ri->drop_level)
6242 && is_dropped_key(&key, &ri->drop_key)) {
6246 ret = add_extent_rec(extent_cache, &key,
6247 btrfs_node_ptr_generation(buf, i),
6248 ptr, size, 0, 0, 1, 0, 1, 0,
6252 add_tree_backref(extent_cache, ptr, parent, owner, 1);
6255 add_pending(nodes, seen, ptr, size);
6257 add_pending(pending, seen, ptr, size);
6260 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
6261 nritems) * sizeof(struct btrfs_key_ptr);
6263 total_btree_bytes += buf->len;
6264 if (fs_root_objectid(btrfs_header_owner(buf)))
6265 total_fs_tree_bytes += buf->len;
6266 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
6267 total_extent_tree_bytes += buf->len;
6268 if (!found_old_backref &&
6269 btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
6270 btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
6271 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
6272 found_old_backref = 1;
6274 free_extent_buffer(buf);
6278 static int add_root_to_pending(struct extent_buffer *buf,
6279 struct cache_tree *extent_cache,
6280 struct cache_tree *pending,
6281 struct cache_tree *seen,
6282 struct cache_tree *nodes,
6285 if (btrfs_header_level(buf) > 0)
6286 add_pending(nodes, seen, buf->start, buf->len);
6288 add_pending(pending, seen, buf->start, buf->len);
6289 add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
6290 0, 1, 1, 0, 1, 0, buf->len);
6292 if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
6293 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
6294 add_tree_backref(extent_cache, buf->start, buf->start,
6297 add_tree_backref(extent_cache, buf->start, 0, objectid, 1);
6301 /* as we fix the tree, we might be deleting blocks that
6302 * we're tracking for repair. This hook makes sure we
6303 * remove any backrefs for blocks as we are fixing them.
6305 static int free_extent_hook(struct btrfs_trans_handle *trans,
6306 struct btrfs_root *root,
6307 u64 bytenr, u64 num_bytes, u64 parent,
6308 u64 root_objectid, u64 owner, u64 offset,
6311 struct extent_record *rec;
6312 struct cache_extent *cache;
6314 struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
6316 is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
6317 cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
6321 rec = container_of(cache, struct extent_record, cache);
6323 struct data_backref *back;
6324 back = find_data_backref(rec, parent, root_objectid, owner,
6325 offset, 1, bytenr, num_bytes);
6328 if (back->node.found_ref) {
6329 back->found_ref -= refs_to_drop;
6331 rec->refs -= refs_to_drop;
6333 if (back->node.found_extent_tree) {
6334 back->num_refs -= refs_to_drop;
6335 if (rec->extent_item_refs)
6336 rec->extent_item_refs -= refs_to_drop;
6338 if (back->found_ref == 0)
6339 back->node.found_ref = 0;
6340 if (back->num_refs == 0)
6341 back->node.found_extent_tree = 0;
6343 if (!back->node.found_extent_tree && back->node.found_ref) {
6344 list_del(&back->node.list);
6348 struct tree_backref *back;
6349 back = find_tree_backref(rec, parent, root_objectid);
6352 if (back->node.found_ref) {
6355 back->node.found_ref = 0;
6357 if (back->node.found_extent_tree) {
6358 if (rec->extent_item_refs)
6359 rec->extent_item_refs--;
6360 back->node.found_extent_tree = 0;
6362 if (!back->node.found_extent_tree && back->node.found_ref) {
6363 list_del(&back->node.list);
6367 maybe_free_extent_rec(extent_cache, rec);
6372 static int delete_extent_records(struct btrfs_trans_handle *trans,
6373 struct btrfs_root *root,
6374 struct btrfs_path *path,
6375 u64 bytenr, u64 new_len)
6377 struct btrfs_key key;
6378 struct btrfs_key found_key;
6379 struct extent_buffer *leaf;
6384 key.objectid = bytenr;
6386 key.offset = (u64)-1;
6389 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
6396 if (path->slots[0] == 0)
6402 leaf = path->nodes[0];
6403 slot = path->slots[0];
6405 btrfs_item_key_to_cpu(leaf, &found_key, slot);
6406 if (found_key.objectid != bytenr)
6409 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
6410 found_key.type != BTRFS_METADATA_ITEM_KEY &&
6411 found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
6412 found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
6413 found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
6414 found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
6415 found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
6416 btrfs_release_path(path);
6417 if (found_key.type == 0) {
6418 if (found_key.offset == 0)
6420 key.offset = found_key.offset - 1;
6421 key.type = found_key.type;
6423 key.type = found_key.type - 1;
6424 key.offset = (u64)-1;
6428 fprintf(stderr, "repair deleting extent record: key %Lu %u %Lu\n",
6429 found_key.objectid, found_key.type, found_key.offset);
6431 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
6434 btrfs_release_path(path);
6436 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
6437 found_key.type == BTRFS_METADATA_ITEM_KEY) {
6438 u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
6439 found_key.offset : root->nodesize;
6441 ret = btrfs_update_block_group(trans, root, bytenr,
6448 btrfs_release_path(path);
6453 * for a single backref, this will allocate a new extent
6454 * and add the backref to it.
6456 static int record_extent(struct btrfs_trans_handle *trans,
6457 struct btrfs_fs_info *info,
6458 struct btrfs_path *path,
6459 struct extent_record *rec,
6460 struct extent_backref *back,
6461 int allocated, u64 flags)
6464 struct btrfs_root *extent_root = info->extent_root;
6465 struct extent_buffer *leaf;
6466 struct btrfs_key ins_key;
6467 struct btrfs_extent_item *ei;
6468 struct tree_backref *tback;
6469 struct data_backref *dback;
6470 struct btrfs_tree_block_info *bi;
6473 rec->max_size = max_t(u64, rec->max_size,
6474 info->extent_root->nodesize);
6477 u32 item_size = sizeof(*ei);
6480 item_size += sizeof(*bi);
6482 ins_key.objectid = rec->start;
6483 ins_key.offset = rec->max_size;
6484 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
6486 ret = btrfs_insert_empty_item(trans, extent_root, path,
6487 &ins_key, item_size);
6491 leaf = path->nodes[0];
6492 ei = btrfs_item_ptr(leaf, path->slots[0],
6493 struct btrfs_extent_item);
6495 btrfs_set_extent_refs(leaf, ei, 0);
6496 btrfs_set_extent_generation(leaf, ei, rec->generation);
6498 if (back->is_data) {
6499 btrfs_set_extent_flags(leaf, ei,
6500 BTRFS_EXTENT_FLAG_DATA);
6502 struct btrfs_disk_key copy_key;;
6504 tback = (struct tree_backref *)back;
6505 bi = (struct btrfs_tree_block_info *)(ei + 1);
6506 memset_extent_buffer(leaf, 0, (unsigned long)bi,
6509 btrfs_set_disk_key_objectid(©_key,
6510 rec->info_objectid);
6511 btrfs_set_disk_key_type(©_key, 0);
6512 btrfs_set_disk_key_offset(©_key, 0);
6514 btrfs_set_tree_block_level(leaf, bi, rec->info_level);
6515 btrfs_set_tree_block_key(leaf, bi, ©_key);
6517 btrfs_set_extent_flags(leaf, ei,
6518 BTRFS_EXTENT_FLAG_TREE_BLOCK | flags);
6521 btrfs_mark_buffer_dirty(leaf);
6522 ret = btrfs_update_block_group(trans, extent_root, rec->start,
6523 rec->max_size, 1, 0);
6526 btrfs_release_path(path);
6529 if (back->is_data) {
6533 dback = (struct data_backref *)back;
6534 if (back->full_backref)
6535 parent = dback->parent;
6539 for (i = 0; i < dback->found_ref; i++) {
6540 /* if parent != 0, we're doing a full backref
6541 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
6542 * just makes the backref allocator create a data
6545 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6546 rec->start, rec->max_size,
6550 BTRFS_FIRST_FREE_OBJECTID :
6556 fprintf(stderr, "adding new data backref"
6557 " on %llu %s %llu owner %llu"
6558 " offset %llu found %d\n",
6559 (unsigned long long)rec->start,
6560 back->full_backref ?
6562 back->full_backref ?
6563 (unsigned long long)parent :
6564 (unsigned long long)dback->root,
6565 (unsigned long long)dback->owner,
6566 (unsigned long long)dback->offset,
6571 tback = (struct tree_backref *)back;
6572 if (back->full_backref)
6573 parent = tback->parent;
6577 ret = btrfs_inc_extent_ref(trans, info->extent_root,
6578 rec->start, rec->max_size,
6579 parent, tback->root, 0, 0);
6580 fprintf(stderr, "adding new tree backref on "
6581 "start %llu len %llu parent %llu root %llu\n",
6582 rec->start, rec->max_size, parent, tback->root);
6585 btrfs_release_path(path);
6589 static struct extent_entry *find_entry(struct list_head *entries,
6590 u64 bytenr, u64 bytes)
6592 struct extent_entry *entry = NULL;
6594 list_for_each_entry(entry, entries, list) {
6595 if (entry->bytenr == bytenr && entry->bytes == bytes)
6602 static struct extent_entry *find_most_right_entry(struct list_head *entries)
6604 struct extent_entry *entry, *best = NULL, *prev = NULL;
6606 list_for_each_entry(entry, entries, list) {
6613 * If there are as many broken entries as entries then we know
6614 * not to trust this particular entry.
6616 if (entry->broken == entry->count)
6620 * If our current entry == best then we can't be sure our best
6621 * is really the best, so we need to keep searching.
6623 if (best && best->count == entry->count) {
6629 /* Prev == entry, not good enough, have to keep searching */
6630 if (!prev->broken && prev->count == entry->count)
6634 best = (prev->count > entry->count) ? prev : entry;
6635 else if (best->count < entry->count)
6643 static int repair_ref(struct btrfs_fs_info *info, struct btrfs_path *path,
6644 struct data_backref *dback, struct extent_entry *entry)
6646 struct btrfs_trans_handle *trans;
6647 struct btrfs_root *root;
6648 struct btrfs_file_extent_item *fi;
6649 struct extent_buffer *leaf;
6650 struct btrfs_key key;
6654 key.objectid = dback->root;
6655 key.type = BTRFS_ROOT_ITEM_KEY;
6656 key.offset = (u64)-1;
6657 root = btrfs_read_fs_root(info, &key);
6659 fprintf(stderr, "Couldn't find root for our ref\n");
6664 * The backref points to the original offset of the extent if it was
6665 * split, so we need to search down to the offset we have and then walk
6666 * forward until we find the backref we're looking for.
6668 key.objectid = dback->owner;
6669 key.type = BTRFS_EXTENT_DATA_KEY;
6670 key.offset = dback->offset;
6671 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6673 fprintf(stderr, "Error looking up ref %d\n", ret);
6678 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6679 ret = btrfs_next_leaf(root, path);
6681 fprintf(stderr, "Couldn't find our ref, next\n");
6685 leaf = path->nodes[0];
6686 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6687 if (key.objectid != dback->owner ||
6688 key.type != BTRFS_EXTENT_DATA_KEY) {
6689 fprintf(stderr, "Couldn't find our ref, search\n");
6692 fi = btrfs_item_ptr(leaf, path->slots[0],
6693 struct btrfs_file_extent_item);
6694 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
6695 bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
6697 if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
6702 btrfs_release_path(path);
6704 trans = btrfs_start_transaction(root, 1);
6706 return PTR_ERR(trans);
6709 * Ok we have the key of the file extent we want to fix, now we can cow
6710 * down to the thing and fix it.
6712 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
6714 fprintf(stderr, "Error cowing down to ref [%Lu, %u, %Lu]: %d\n",
6715 key.objectid, key.type, key.offset, ret);
6719 fprintf(stderr, "Well that's odd, we just found this key "
6720 "[%Lu, %u, %Lu]\n", key.objectid, key.type,
6725 leaf = path->nodes[0];
6726 fi = btrfs_item_ptr(leaf, path->slots[0],
6727 struct btrfs_file_extent_item);
6729 if (btrfs_file_extent_compression(leaf, fi) &&
6730 dback->disk_bytenr != entry->bytenr) {
6731 fprintf(stderr, "Ref doesn't match the record start and is "
6732 "compressed, please take a btrfs-image of this file "
6733 "system and send it to a btrfs developer so they can "
6734 "complete this functionality for bytenr %Lu\n",
6735 dback->disk_bytenr);
6740 if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
6741 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6742 } else if (dback->disk_bytenr > entry->bytenr) {
6743 u64 off_diff, offset;
6745 off_diff = dback->disk_bytenr - entry->bytenr;
6746 offset = btrfs_file_extent_offset(leaf, fi);
6747 if (dback->disk_bytenr + offset +
6748 btrfs_file_extent_num_bytes(leaf, fi) >
6749 entry->bytenr + entry->bytes) {
6750 fprintf(stderr, "Ref is past the entry end, please "
6751 "take a btrfs-image of this file system and "
6752 "send it to a btrfs developer, ref %Lu\n",
6753 dback->disk_bytenr);
6758 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6759 btrfs_set_file_extent_offset(leaf, fi, offset);
6760 } else if (dback->disk_bytenr < entry->bytenr) {
6763 offset = btrfs_file_extent_offset(leaf, fi);
6764 if (dback->disk_bytenr + offset < entry->bytenr) {
6765 fprintf(stderr, "Ref is before the entry start, please"
6766 " take a btrfs-image of this file system and "
6767 "send it to a btrfs developer, ref %Lu\n",
6768 dback->disk_bytenr);
6773 offset += dback->disk_bytenr;
6774 offset -= entry->bytenr;
6775 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
6776 btrfs_set_file_extent_offset(leaf, fi, offset);
6779 btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
6782 * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
6783 * only do this if we aren't using compression, otherwise it's a
6786 if (!btrfs_file_extent_compression(leaf, fi))
6787 btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
6789 printf("ram bytes may be wrong?\n");
6790 btrfs_mark_buffer_dirty(leaf);
6792 err = btrfs_commit_transaction(trans, root);
6793 btrfs_release_path(path);
6794 return ret ? ret : err;
6797 static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
6798 struct extent_record *rec)
6800 struct extent_backref *back;
6801 struct data_backref *dback;
6802 struct extent_entry *entry, *best = NULL;
6805 int broken_entries = 0;
6810 * Metadata is easy and the backrefs should always agree on bytenr and
6811 * size, if not we've got bigger issues.
6816 list_for_each_entry(back, &rec->backrefs, list) {
6817 if (back->full_backref || !back->is_data)
6820 dback = (struct data_backref *)back;
6823 * We only pay attention to backrefs that we found a real
6826 if (dback->found_ref == 0)
6830 * For now we only catch when the bytes don't match, not the
6831 * bytenr. We can easily do this at the same time, but I want
6832 * to have a fs image to test on before we just add repair
6833 * functionality willy-nilly so we know we won't screw up the
6837 entry = find_entry(&entries, dback->disk_bytenr,
6840 entry = malloc(sizeof(struct extent_entry));
6845 memset(entry, 0, sizeof(*entry));
6846 entry->bytenr = dback->disk_bytenr;
6847 entry->bytes = dback->bytes;
6848 list_add_tail(&entry->list, &entries);
6853 * If we only have on entry we may think the entries agree when
6854 * in reality they don't so we have to do some extra checking.
6856 if (dback->disk_bytenr != rec->start ||
6857 dback->bytes != rec->nr || back->broken)
6868 /* Yay all the backrefs agree, carry on good sir */
6869 if (nr_entries <= 1 && !mismatch)
6872 fprintf(stderr, "attempting to repair backref discrepency for bytenr "
6873 "%Lu\n", rec->start);
6876 * First we want to see if the backrefs can agree amongst themselves who
6877 * is right, so figure out which one of the entries has the highest
6880 best = find_most_right_entry(&entries);
6883 * Ok so we may have an even split between what the backrefs think, so
6884 * this is where we use the extent ref to see what it thinks.
6887 entry = find_entry(&entries, rec->start, rec->nr);
6888 if (!entry && (!broken_entries || !rec->found_rec)) {
6889 fprintf(stderr, "Backrefs don't agree with each other "
6890 "and extent record doesn't agree with anybody,"
6891 " so we can't fix bytenr %Lu bytes %Lu\n",
6892 rec->start, rec->nr);
6895 } else if (!entry) {
6897 * Ok our backrefs were broken, we'll assume this is the
6898 * correct value and add an entry for this range.
6900 entry = malloc(sizeof(struct extent_entry));
6905 memset(entry, 0, sizeof(*entry));
6906 entry->bytenr = rec->start;
6907 entry->bytes = rec->nr;
6908 list_add_tail(&entry->list, &entries);
6912 best = find_most_right_entry(&entries);
6914 fprintf(stderr, "Backrefs and extent record evenly "
6915 "split on who is right, this is going to "
6916 "require user input to fix bytenr %Lu bytes "
6917 "%Lu\n", rec->start, rec->nr);
6924 * I don't think this can happen currently as we'll abort() if we catch
6925 * this case higher up, but in case somebody removes that we still can't
6926 * deal with it properly here yet, so just bail out of that's the case.
6928 if (best->bytenr != rec->start) {
6929 fprintf(stderr, "Extent start and backref starts don't match, "
6930 "please use btrfs-image on this file system and send "
6931 "it to a btrfs developer so they can make fsck fix "
6932 "this particular case. bytenr is %Lu, bytes is %Lu\n",
6933 rec->start, rec->nr);
6939 * Ok great we all agreed on an extent record, let's go find the real
6940 * references and fix up the ones that don't match.
6942 list_for_each_entry(back, &rec->backrefs, list) {
6943 if (back->full_backref || !back->is_data)
6946 dback = (struct data_backref *)back;
6949 * Still ignoring backrefs that don't have a real ref attached
6952 if (dback->found_ref == 0)
6955 if (dback->bytes == best->bytes &&
6956 dback->disk_bytenr == best->bytenr)
6959 ret = repair_ref(info, path, dback, best);
6965 * Ok we messed with the actual refs, which means we need to drop our
6966 * entire cache and go back and rescan. I know this is a huge pain and
6967 * adds a lot of extra work, but it's the only way to be safe. Once all
6968 * the backrefs agree we may not need to do anything to the extent
6973 while (!list_empty(&entries)) {
6974 entry = list_entry(entries.next, struct extent_entry, list);
6975 list_del_init(&entry->list);
6981 static int process_duplicates(struct btrfs_root *root,
6982 struct cache_tree *extent_cache,
6983 struct extent_record *rec)
6985 struct extent_record *good, *tmp;
6986 struct cache_extent *cache;
6990 * If we found a extent record for this extent then return, or if we
6991 * have more than one duplicate we are likely going to need to delete
6994 if (rec->found_rec || rec->num_duplicates > 1)
6997 /* Shouldn't happen but just in case */
6998 BUG_ON(!rec->num_duplicates);
7001 * So this happens if we end up with a backref that doesn't match the
7002 * actual extent entry. So either the backref is bad or the extent
7003 * entry is bad. Either way we want to have the extent_record actually
7004 * reflect what we found in the extent_tree, so we need to take the
7005 * duplicate out and use that as the extent_record since the only way we
7006 * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
7008 remove_cache_extent(extent_cache, &rec->cache);
7010 good = list_entry(rec->dups.next, struct extent_record, list);
7011 list_del_init(&good->list);
7012 INIT_LIST_HEAD(&good->backrefs);
7013 INIT_LIST_HEAD(&good->dups);
7014 good->cache.start = good->start;
7015 good->cache.size = good->nr;
7016 good->content_checked = 0;
7017 good->owner_ref_checked = 0;
7018 good->num_duplicates = 0;
7019 good->refs = rec->refs;
7020 list_splice_init(&rec->backrefs, &good->backrefs);
7022 cache = lookup_cache_extent(extent_cache, good->start,
7026 tmp = container_of(cache, struct extent_record, cache);
7029 * If we find another overlapping extent and it's found_rec is
7030 * set then it's a duplicate and we need to try and delete
7033 if (tmp->found_rec || tmp->num_duplicates > 0) {
7034 if (list_empty(&good->list))
7035 list_add_tail(&good->list,
7036 &duplicate_extents);
7037 good->num_duplicates += tmp->num_duplicates + 1;
7038 list_splice_init(&tmp->dups, &good->dups);
7039 list_del_init(&tmp->list);
7040 list_add_tail(&tmp->list, &good->dups);
7041 remove_cache_extent(extent_cache, &tmp->cache);
7046 * Ok we have another non extent item backed extent rec, so lets
7047 * just add it to this extent and carry on like we did above.
7049 good->refs += tmp->refs;
7050 list_splice_init(&tmp->backrefs, &good->backrefs);
7051 remove_cache_extent(extent_cache, &tmp->cache);
7054 ret = insert_cache_extent(extent_cache, &good->cache);
7057 return good->num_duplicates ? 0 : 1;
7060 static int delete_duplicate_records(struct btrfs_root *root,
7061 struct extent_record *rec)
7063 struct btrfs_trans_handle *trans;
7064 LIST_HEAD(delete_list);
7065 struct btrfs_path *path;
7066 struct extent_record *tmp, *good, *n;
7069 struct btrfs_key key;
7071 path = btrfs_alloc_path();
7078 /* Find the record that covers all of the duplicates. */
7079 list_for_each_entry(tmp, &rec->dups, list) {
7080 if (good->start < tmp->start)
7082 if (good->nr > tmp->nr)
7085 if (tmp->start + tmp->nr < good->start + good->nr) {
7086 fprintf(stderr, "Ok we have overlapping extents that "
7087 "aren't completely covered by eachother, this "
7088 "is going to require more careful thought. "
7089 "The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
7090 tmp->start, tmp->nr, good->start, good->nr);
7097 list_add_tail(&rec->list, &delete_list);
7099 list_for_each_entry_safe(tmp, n, &rec->dups, list) {
7102 list_move_tail(&tmp->list, &delete_list);
7105 root = root->fs_info->extent_root;
7106 trans = btrfs_start_transaction(root, 1);
7107 if (IS_ERR(trans)) {
7108 ret = PTR_ERR(trans);
7112 list_for_each_entry(tmp, &delete_list, list) {
7113 if (tmp->found_rec == 0)
7115 key.objectid = tmp->start;
7116 key.type = BTRFS_EXTENT_ITEM_KEY;
7117 key.offset = tmp->nr;
7119 /* Shouldn't happen but just in case */
7120 if (tmp->metadata) {
7121 fprintf(stderr, "Well this shouldn't happen, extent "
7122 "record overlaps but is metadata? "
7123 "[%Lu, %Lu]\n", tmp->start, tmp->nr);
7127 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
7133 ret = btrfs_del_item(trans, root, path);
7136 btrfs_release_path(path);
7139 err = btrfs_commit_transaction(trans, root);
7143 while (!list_empty(&delete_list)) {
7144 tmp = list_entry(delete_list.next, struct extent_record, list);
7145 list_del_init(&tmp->list);
7151 while (!list_empty(&rec->dups)) {
7152 tmp = list_entry(rec->dups.next, struct extent_record, list);
7153 list_del_init(&tmp->list);
7157 btrfs_free_path(path);
7159 if (!ret && !nr_del)
7160 rec->num_duplicates = 0;
7162 return ret ? ret : nr_del;
7165 static int find_possible_backrefs(struct btrfs_fs_info *info,
7166 struct btrfs_path *path,
7167 struct cache_tree *extent_cache,
7168 struct extent_record *rec)
7170 struct btrfs_root *root;
7171 struct extent_backref *back;
7172 struct data_backref *dback;
7173 struct cache_extent *cache;
7174 struct btrfs_file_extent_item *fi;
7175 struct btrfs_key key;
7179 list_for_each_entry(back, &rec->backrefs, list) {
7180 /* Don't care about full backrefs (poor unloved backrefs) */
7181 if (back->full_backref || !back->is_data)
7184 dback = (struct data_backref *)back;
7186 /* We found this one, we don't need to do a lookup */
7187 if (dback->found_ref)
7190 key.objectid = dback->root;
7191 key.type = BTRFS_ROOT_ITEM_KEY;
7192 key.offset = (u64)-1;
7194 root = btrfs_read_fs_root(info, &key);
7196 /* No root, definitely a bad ref, skip */
7197 if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
7199 /* Other err, exit */
7201 return PTR_ERR(root);
7203 key.objectid = dback->owner;
7204 key.type = BTRFS_EXTENT_DATA_KEY;
7205 key.offset = dback->offset;
7206 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
7208 btrfs_release_path(path);
7211 /* Didn't find it, we can carry on */
7216 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
7217 struct btrfs_file_extent_item);
7218 bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
7219 bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
7220 btrfs_release_path(path);
7221 cache = lookup_cache_extent(extent_cache, bytenr, 1);
7223 struct extent_record *tmp;
7224 tmp = container_of(cache, struct extent_record, cache);
7227 * If we found an extent record for the bytenr for this
7228 * particular backref then we can't add it to our
7229 * current extent record. We only want to add backrefs
7230 * that don't have a corresponding extent item in the
7231 * extent tree since they likely belong to this record
7232 * and we need to fix it if it doesn't match bytenrs.
7238 dback->found_ref += 1;
7239 dback->disk_bytenr = bytenr;
7240 dback->bytes = bytes;
7243 * Set this so the verify backref code knows not to trust the
7244 * values in this backref.
7253 * Record orphan data ref into corresponding root.
7255 * Return 0 if the extent item contains data ref and recorded.
7256 * Return 1 if the extent item contains no useful data ref
7257 * On that case, it may contains only shared_dataref or metadata backref
7258 * or the file extent exists(this should be handled by the extent bytenr
7260 * Return <0 if something goes wrong.
7262 static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
7263 struct extent_record *rec)
7265 struct btrfs_key key;
7266 struct btrfs_root *dest_root;
7267 struct extent_backref *back;
7268 struct data_backref *dback;
7269 struct orphan_data_extent *orphan;
7270 struct btrfs_path *path;
7271 int recorded_data_ref = 0;
7276 path = btrfs_alloc_path();
7279 list_for_each_entry(back, &rec->backrefs, list) {
7280 if (back->full_backref || !back->is_data ||
7281 !back->found_extent_tree)
7283 dback = (struct data_backref *)back;
7284 if (dback->found_ref)
7286 key.objectid = dback->root;
7287 key.type = BTRFS_ROOT_ITEM_KEY;
7288 key.offset = (u64)-1;
7290 dest_root = btrfs_read_fs_root(fs_info, &key);
7292 /* For non-exist root we just skip it */
7293 if (IS_ERR(dest_root) || !dest_root)
7296 key.objectid = dback->owner;
7297 key.type = BTRFS_EXTENT_DATA_KEY;
7298 key.offset = dback->offset;
7300 ret = btrfs_search_slot(NULL, dest_root, &key, path, 0, 0);
7302 * For ret < 0, it's OK since the fs-tree may be corrupted,
7303 * we need to record it for inode/file extent rebuild.
7304 * For ret > 0, we record it only for file extent rebuild.
7305 * For ret == 0, the file extent exists but only bytenr
7306 * mismatch, let the original bytenr fix routine to handle,
7312 orphan = malloc(sizeof(*orphan));
7317 INIT_LIST_HEAD(&orphan->list);
7318 orphan->root = dback->root;
7319 orphan->objectid = dback->owner;
7320 orphan->offset = dback->offset;
7321 orphan->disk_bytenr = rec->cache.start;
7322 orphan->disk_len = rec->cache.size;
7323 list_add(&dest_root->orphan_data_extents, &orphan->list);
7324 recorded_data_ref = 1;
7327 btrfs_free_path(path);
7329 return !recorded_data_ref;
7335 * when an incorrect extent item is found, this will delete
7336 * all of the existing entries for it and recreate them
7337 * based on what the tree scan found.
7339 static int fixup_extent_refs(struct btrfs_fs_info *info,
7340 struct cache_tree *extent_cache,
7341 struct extent_record *rec)
7343 struct btrfs_trans_handle *trans = NULL;
7345 struct btrfs_path *path;
7346 struct list_head *cur = rec->backrefs.next;
7347 struct cache_extent *cache;
7348 struct extent_backref *back;
7352 if (rec->flag_block_full_backref)
7353 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7355 path = btrfs_alloc_path();
7359 if (rec->refs != rec->extent_item_refs && !rec->metadata) {
7361 * Sometimes the backrefs themselves are so broken they don't
7362 * get attached to any meaningful rec, so first go back and
7363 * check any of our backrefs that we couldn't find and throw
7364 * them into the list if we find the backref so that
7365 * verify_backrefs can figure out what to do.
7367 ret = find_possible_backrefs(info, path, extent_cache, rec);
7372 /* step one, make sure all of the backrefs agree */
7373 ret = verify_backrefs(info, path, rec);
7377 trans = btrfs_start_transaction(info->extent_root, 1);
7378 if (IS_ERR(trans)) {
7379 ret = PTR_ERR(trans);
7383 /* step two, delete all the existing records */
7384 ret = delete_extent_records(trans, info->extent_root, path,
7385 rec->start, rec->max_size);
7390 /* was this block corrupt? If so, don't add references to it */
7391 cache = lookup_cache_extent(info->corrupt_blocks,
7392 rec->start, rec->max_size);
7398 /* step three, recreate all the refs we did find */
7399 while(cur != &rec->backrefs) {
7400 back = list_entry(cur, struct extent_backref, list);
7404 * if we didn't find any references, don't create a
7407 if (!back->found_ref)
7410 rec->bad_full_backref = 0;
7411 ret = record_extent(trans, info, path, rec, back, allocated, flags);
7419 int err = btrfs_commit_transaction(trans, info->extent_root);
7424 btrfs_free_path(path);
7428 static int fixup_extent_flags(struct btrfs_fs_info *fs_info,
7429 struct extent_record *rec)
7431 struct btrfs_trans_handle *trans;
7432 struct btrfs_root *root = fs_info->extent_root;
7433 struct btrfs_path *path;
7434 struct btrfs_extent_item *ei;
7435 struct btrfs_key key;
7439 key.objectid = rec->start;
7440 if (rec->metadata) {
7441 key.type = BTRFS_METADATA_ITEM_KEY;
7442 key.offset = rec->info_level;
7444 key.type = BTRFS_EXTENT_ITEM_KEY;
7445 key.offset = rec->max_size;
7448 path = btrfs_alloc_path();
7452 trans = btrfs_start_transaction(root, 0);
7453 if (IS_ERR(trans)) {
7454 btrfs_free_path(path);
7455 return PTR_ERR(trans);
7458 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
7460 btrfs_free_path(path);
7461 btrfs_commit_transaction(trans, root);
7464 fprintf(stderr, "Didn't find extent for %llu\n",
7465 (unsigned long long)rec->start);
7466 btrfs_free_path(path);
7467 btrfs_commit_transaction(trans, root);
7471 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
7472 struct btrfs_extent_item);
7473 flags = btrfs_extent_flags(path->nodes[0], ei);
7474 if (rec->flag_block_full_backref) {
7475 fprintf(stderr, "setting full backref on %llu\n",
7476 (unsigned long long)key.objectid);
7477 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
7479 fprintf(stderr, "clearing full backref on %llu\n",
7480 (unsigned long long)key.objectid);
7481 flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
7483 btrfs_set_extent_flags(path->nodes[0], ei, flags);
7484 btrfs_mark_buffer_dirty(path->nodes[0]);
7485 btrfs_free_path(path);
7486 return btrfs_commit_transaction(trans, root);
7489 /* right now we only prune from the extent allocation tree */
7490 static int prune_one_block(struct btrfs_trans_handle *trans,
7491 struct btrfs_fs_info *info,
7492 struct btrfs_corrupt_block *corrupt)
7495 struct btrfs_path path;
7496 struct extent_buffer *eb;
7500 int level = corrupt->level + 1;
7502 btrfs_init_path(&path);
7504 /* we want to stop at the parent to our busted block */
7505 path.lowest_level = level;
7507 ret = btrfs_search_slot(trans, info->extent_root,
7508 &corrupt->key, &path, -1, 1);
7513 eb = path.nodes[level];
7520 * hopefully the search gave us the block we want to prune,
7521 * lets try that first
7523 slot = path.slots[level];
7524 found = btrfs_node_blockptr(eb, slot);
7525 if (found == corrupt->cache.start)
7528 nritems = btrfs_header_nritems(eb);
7530 /* the search failed, lets scan this node and hope we find it */
7531 for (slot = 0; slot < nritems; slot++) {
7532 found = btrfs_node_blockptr(eb, slot);
7533 if (found == corrupt->cache.start)
7537 * we couldn't find the bad block. TODO, search all the nodes for pointers
7540 if (eb == info->extent_root->node) {
7545 btrfs_release_path(&path);
7550 printk("deleting pointer to block %Lu\n", corrupt->cache.start);
7551 ret = btrfs_del_ptr(trans, info->extent_root, &path, level, slot);
7554 btrfs_release_path(&path);
7558 static int prune_corrupt_blocks(struct btrfs_fs_info *info)
7560 struct btrfs_trans_handle *trans = NULL;
7561 struct cache_extent *cache;
7562 struct btrfs_corrupt_block *corrupt;
7565 cache = search_cache_extent(info->corrupt_blocks, 0);
7569 trans = btrfs_start_transaction(info->extent_root, 1);
7571 return PTR_ERR(trans);
7573 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
7574 prune_one_block(trans, info, corrupt);
7575 remove_cache_extent(info->corrupt_blocks, cache);
7578 return btrfs_commit_transaction(trans, info->extent_root);
7582 static void reset_cached_block_groups(struct btrfs_fs_info *fs_info)
7584 struct btrfs_block_group_cache *cache;
7589 ret = find_first_extent_bit(&fs_info->free_space_cache, 0,
7590 &start, &end, EXTENT_DIRTY);
7593 clear_extent_dirty(&fs_info->free_space_cache, start, end,
7599 cache = btrfs_lookup_first_block_group(fs_info, start);
7604 start = cache->key.objectid + cache->key.offset;
7608 static int check_extent_refs(struct btrfs_root *root,
7609 struct cache_tree *extent_cache)
7611 struct extent_record *rec;
7612 struct cache_extent *cache;
7621 * if we're doing a repair, we have to make sure
7622 * we don't allocate from the problem extents.
7623 * In the worst case, this will be all the
7626 cache = search_cache_extent(extent_cache, 0);
7628 rec = container_of(cache, struct extent_record, cache);
7629 set_extent_dirty(root->fs_info->excluded_extents,
7631 rec->start + rec->max_size - 1,
7633 cache = next_cache_extent(cache);
7636 /* pin down all the corrupted blocks too */
7637 cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
7639 set_extent_dirty(root->fs_info->excluded_extents,
7641 cache->start + cache->size - 1,
7643 cache = next_cache_extent(cache);
7645 prune_corrupt_blocks(root->fs_info);
7646 reset_cached_block_groups(root->fs_info);
7649 reset_cached_block_groups(root->fs_info);
7652 * We need to delete any duplicate entries we find first otherwise we
7653 * could mess up the extent tree when we have backrefs that actually
7654 * belong to a different extent item and not the weird duplicate one.
7656 while (repair && !list_empty(&duplicate_extents)) {
7657 rec = list_entry(duplicate_extents.next, struct extent_record,
7659 list_del_init(&rec->list);
7661 /* Sometimes we can find a backref before we find an actual
7662 * extent, so we need to process it a little bit to see if there
7663 * truly are multiple EXTENT_ITEM_KEY's for the same range, or
7664 * if this is a backref screwup. If we need to delete stuff
7665 * process_duplicates() will return 0, otherwise it will return
7668 if (process_duplicates(root, extent_cache, rec))
7670 ret = delete_duplicate_records(root, rec);
7674 * delete_duplicate_records will return the number of entries
7675 * deleted, so if it's greater than 0 then we know we actually
7676 * did something and we need to remove.
7690 cache = search_cache_extent(extent_cache, 0);
7693 rec = container_of(cache, struct extent_record, cache);
7694 if (rec->num_duplicates) {
7695 fprintf(stderr, "extent item %llu has multiple extent "
7696 "items\n", (unsigned long long)rec->start);
7701 if (rec->refs != rec->extent_item_refs) {
7702 fprintf(stderr, "ref mismatch on [%llu %llu] ",
7703 (unsigned long long)rec->start,
7704 (unsigned long long)rec->nr);
7705 fprintf(stderr, "extent item %llu, found %llu\n",
7706 (unsigned long long)rec->extent_item_refs,
7707 (unsigned long long)rec->refs);
7708 ret = record_orphan_data_extents(root->fs_info, rec);
7715 * we can't use the extent to repair file
7716 * extent, let the fallback method handle it.
7718 if (!fixed && repair) {
7719 ret = fixup_extent_refs(
7730 if (all_backpointers_checked(rec, 1)) {
7731 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
7732 (unsigned long long)rec->start,
7733 (unsigned long long)rec->nr);
7735 if (!fixed && !recorded && repair) {
7736 ret = fixup_extent_refs(root->fs_info,
7745 if (!rec->owner_ref_checked) {
7746 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
7747 (unsigned long long)rec->start,
7748 (unsigned long long)rec->nr);
7749 if (!fixed && !recorded && repair) {
7750 ret = fixup_extent_refs(root->fs_info,
7759 if (rec->bad_full_backref) {
7760 fprintf(stderr, "bad full backref, on [%llu]\n",
7761 (unsigned long long)rec->start);
7763 ret = fixup_extent_flags(root->fs_info, rec);
7772 * Although it's not a extent ref's problem, we reuse this
7773 * routine for error reporting.
7774 * No repair function yet.
7776 if (rec->crossing_stripes) {
7778 "bad metadata [%llu, %llu) crossing stripe boundary\n",
7779 rec->start, rec->start + rec->max_size);
7784 if (rec->wrong_chunk_type) {
7786 "bad extent [%llu, %llu), type mismatch with chunk\n",
7787 rec->start, rec->start + rec->max_size);
7792 remove_cache_extent(extent_cache, cache);
7793 free_all_extent_backrefs(rec);
7794 if (!init_extent_tree && repair && (!cur_err || fixed))
7795 clear_extent_dirty(root->fs_info->excluded_extents,
7797 rec->start + rec->max_size - 1,
7803 if (ret && ret != -EAGAIN) {
7804 fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
7807 struct btrfs_trans_handle *trans;
7809 root = root->fs_info->extent_root;
7810 trans = btrfs_start_transaction(root, 1);
7811 if (IS_ERR(trans)) {
7812 ret = PTR_ERR(trans);
7816 btrfs_fix_block_accounting(trans, root);
7817 ret = btrfs_commit_transaction(trans, root);
7822 fprintf(stderr, "repaired damaged extent references\n");
7828 u64 calc_stripe_length(u64 type, u64 length, int num_stripes)
7832 if (type & BTRFS_BLOCK_GROUP_RAID0) {
7833 stripe_size = length;
7834 stripe_size /= num_stripes;
7835 } else if (type & BTRFS_BLOCK_GROUP_RAID10) {
7836 stripe_size = length * 2;
7837 stripe_size /= num_stripes;
7838 } else if (type & BTRFS_BLOCK_GROUP_RAID5) {
7839 stripe_size = length;
7840 stripe_size /= (num_stripes - 1);
7841 } else if (type & BTRFS_BLOCK_GROUP_RAID6) {
7842 stripe_size = length;
7843 stripe_size /= (num_stripes - 2);
7845 stripe_size = length;
7851 * Check the chunk with its block group/dev list ref:
7852 * Return 0 if all refs seems valid.
7853 * Return 1 if part of refs seems valid, need later check for rebuild ref
7854 * like missing block group and needs to search extent tree to rebuild them.
7855 * Return -1 if essential refs are missing and unable to rebuild.
7857 static int check_chunk_refs(struct chunk_record *chunk_rec,
7858 struct block_group_tree *block_group_cache,
7859 struct device_extent_tree *dev_extent_cache,
7862 struct cache_extent *block_group_item;
7863 struct block_group_record *block_group_rec;
7864 struct cache_extent *dev_extent_item;
7865 struct device_extent_record *dev_extent_rec;
7869 int metadump_v2 = 0;
7873 block_group_item = lookup_cache_extent(&block_group_cache->tree,
7876 if (block_group_item) {
7877 block_group_rec = container_of(block_group_item,
7878 struct block_group_record,
7880 if (chunk_rec->length != block_group_rec->offset ||
7881 chunk_rec->offset != block_group_rec->objectid ||
7883 chunk_rec->type_flags != block_group_rec->flags)) {
7886 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
7887 chunk_rec->objectid,
7892 chunk_rec->type_flags,
7893 block_group_rec->objectid,
7894 block_group_rec->type,
7895 block_group_rec->offset,
7896 block_group_rec->offset,
7897 block_group_rec->objectid,
7898 block_group_rec->flags);
7901 list_del_init(&block_group_rec->list);
7902 chunk_rec->bg_rec = block_group_rec;
7907 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
7908 chunk_rec->objectid,
7913 chunk_rec->type_flags);
7920 length = calc_stripe_length(chunk_rec->type_flags, chunk_rec->length,
7921 chunk_rec->num_stripes);
7922 for (i = 0; i < chunk_rec->num_stripes; ++i) {
7923 devid = chunk_rec->stripes[i].devid;
7924 offset = chunk_rec->stripes[i].offset;
7925 dev_extent_item = lookup_cache_extent2(&dev_extent_cache->tree,
7926 devid, offset, length);
7927 if (dev_extent_item) {
7928 dev_extent_rec = container_of(dev_extent_item,
7929 struct device_extent_record,
7931 if (dev_extent_rec->objectid != devid ||
7932 dev_extent_rec->offset != offset ||
7933 dev_extent_rec->chunk_offset != chunk_rec->offset ||
7934 dev_extent_rec->length != length) {
7937 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
7938 chunk_rec->objectid,
7941 chunk_rec->stripes[i].devid,
7942 chunk_rec->stripes[i].offset,
7943 dev_extent_rec->objectid,
7944 dev_extent_rec->offset,
7945 dev_extent_rec->length);
7948 list_move(&dev_extent_rec->chunk_list,
7949 &chunk_rec->dextents);
7954 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
7955 chunk_rec->objectid,
7958 chunk_rec->stripes[i].devid,
7959 chunk_rec->stripes[i].offset);
7966 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
7967 int check_chunks(struct cache_tree *chunk_cache,
7968 struct block_group_tree *block_group_cache,
7969 struct device_extent_tree *dev_extent_cache,
7970 struct list_head *good, struct list_head *bad,
7971 struct list_head *rebuild, int silent)
7973 struct cache_extent *chunk_item;
7974 struct chunk_record *chunk_rec;
7975 struct block_group_record *bg_rec;
7976 struct device_extent_record *dext_rec;
7980 chunk_item = first_cache_extent(chunk_cache);
7981 while (chunk_item) {
7982 chunk_rec = container_of(chunk_item, struct chunk_record,
7984 err = check_chunk_refs(chunk_rec, block_group_cache,
7985 dev_extent_cache, silent);
7988 if (err == 0 && good)
7989 list_add_tail(&chunk_rec->list, good);
7990 if (err > 0 && rebuild)
7991 list_add_tail(&chunk_rec->list, rebuild);
7993 list_add_tail(&chunk_rec->list, bad);
7994 chunk_item = next_cache_extent(chunk_item);
7997 list_for_each_entry(bg_rec, &block_group_cache->block_groups, list) {
8000 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
8008 list_for_each_entry(dext_rec, &dev_extent_cache->no_chunk_orphans,
8012 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
8023 static int check_device_used(struct device_record *dev_rec,
8024 struct device_extent_tree *dext_cache)
8026 struct cache_extent *cache;
8027 struct device_extent_record *dev_extent_rec;
8030 cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
8032 dev_extent_rec = container_of(cache,
8033 struct device_extent_record,
8035 if (dev_extent_rec->objectid != dev_rec->devid)
8038 list_del_init(&dev_extent_rec->device_list);
8039 total_byte += dev_extent_rec->length;
8040 cache = next_cache_extent(cache);
8043 if (total_byte != dev_rec->byte_used) {
8045 "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
8046 total_byte, dev_rec->byte_used, dev_rec->objectid,
8047 dev_rec->type, dev_rec->offset);
8054 /* check btrfs_dev_item -> btrfs_dev_extent */
8055 static int check_devices(struct rb_root *dev_cache,
8056 struct device_extent_tree *dev_extent_cache)
8058 struct rb_node *dev_node;
8059 struct device_record *dev_rec;
8060 struct device_extent_record *dext_rec;
8064 dev_node = rb_first(dev_cache);
8066 dev_rec = container_of(dev_node, struct device_record, node);
8067 err = check_device_used(dev_rec, dev_extent_cache);
8071 dev_node = rb_next(dev_node);
8073 list_for_each_entry(dext_rec, &dev_extent_cache->no_device_orphans,
8076 "Device extent[%llu, %llu, %llu] didn't find its device.\n",
8077 dext_rec->objectid, dext_rec->offset, dext_rec->length);
8084 static int add_root_item_to_list(struct list_head *head,
8085 u64 objectid, u64 bytenr, u64 last_snapshot,
8086 u8 level, u8 drop_level,
8087 int level_size, struct btrfs_key *drop_key)
8090 struct root_item_record *ri_rec;
8091 ri_rec = malloc(sizeof(*ri_rec));
8094 ri_rec->bytenr = bytenr;
8095 ri_rec->objectid = objectid;
8096 ri_rec->level = level;
8097 ri_rec->level_size = level_size;
8098 ri_rec->drop_level = drop_level;
8099 ri_rec->last_snapshot = last_snapshot;
8101 memcpy(&ri_rec->drop_key, drop_key, sizeof(*drop_key));
8102 list_add_tail(&ri_rec->list, head);
8107 static void free_root_item_list(struct list_head *list)
8109 struct root_item_record *ri_rec;
8111 while (!list_empty(list)) {
8112 ri_rec = list_first_entry(list, struct root_item_record,
8114 list_del_init(&ri_rec->list);
8119 static int deal_root_from_list(struct list_head *list,
8120 struct btrfs_root *root,
8121 struct block_info *bits,
8123 struct cache_tree *pending,
8124 struct cache_tree *seen,
8125 struct cache_tree *reada,
8126 struct cache_tree *nodes,
8127 struct cache_tree *extent_cache,
8128 struct cache_tree *chunk_cache,
8129 struct rb_root *dev_cache,
8130 struct block_group_tree *block_group_cache,
8131 struct device_extent_tree *dev_extent_cache)
8136 while (!list_empty(list)) {
8137 struct root_item_record *rec;
8138 struct extent_buffer *buf;
8139 rec = list_entry(list->next,
8140 struct root_item_record, list);
8142 buf = read_tree_block(root->fs_info->tree_root,
8143 rec->bytenr, rec->level_size, 0);
8144 if (!extent_buffer_uptodate(buf)) {
8145 free_extent_buffer(buf);
8149 add_root_to_pending(buf, extent_cache, pending,
8150 seen, nodes, rec->objectid);
8152 * To rebuild extent tree, we need deal with snapshot
8153 * one by one, otherwise we deal with node firstly which
8154 * can maximize readahead.
8157 ret = run_next_block(root, bits, bits_nr, &last,
8158 pending, seen, reada, nodes,
8159 extent_cache, chunk_cache,
8160 dev_cache, block_group_cache,
8161 dev_extent_cache, rec);
8165 free_extent_buffer(buf);
8166 list_del(&rec->list);
8172 ret = run_next_block(root, bits, bits_nr, &last, pending, seen,
8173 reada, nodes, extent_cache, chunk_cache,
8174 dev_cache, block_group_cache,
8175 dev_extent_cache, NULL);
8185 static int check_chunks_and_extents(struct btrfs_root *root)
8187 struct rb_root dev_cache;
8188 struct cache_tree chunk_cache;
8189 struct block_group_tree block_group_cache;
8190 struct device_extent_tree dev_extent_cache;
8191 struct cache_tree extent_cache;
8192 struct cache_tree seen;
8193 struct cache_tree pending;
8194 struct cache_tree reada;
8195 struct cache_tree nodes;
8196 struct extent_io_tree excluded_extents;
8197 struct cache_tree corrupt_blocks;
8198 struct btrfs_path path;
8199 struct btrfs_key key;
8200 struct btrfs_key found_key;
8202 struct block_info *bits;
8204 struct extent_buffer *leaf;
8206 struct btrfs_root_item ri;
8207 struct list_head dropping_trees;
8208 struct list_head normal_trees;
8209 struct btrfs_root *root1;
8214 dev_cache = RB_ROOT;
8215 cache_tree_init(&chunk_cache);
8216 block_group_tree_init(&block_group_cache);
8217 device_extent_tree_init(&dev_extent_cache);
8219 cache_tree_init(&extent_cache);
8220 cache_tree_init(&seen);
8221 cache_tree_init(&pending);
8222 cache_tree_init(&nodes);
8223 cache_tree_init(&reada);
8224 cache_tree_init(&corrupt_blocks);
8225 extent_io_tree_init(&excluded_extents);
8226 INIT_LIST_HEAD(&dropping_trees);
8227 INIT_LIST_HEAD(&normal_trees);
8230 root->fs_info->excluded_extents = &excluded_extents;
8231 root->fs_info->fsck_extent_cache = &extent_cache;
8232 root->fs_info->free_extent_hook = free_extent_hook;
8233 root->fs_info->corrupt_blocks = &corrupt_blocks;
8237 bits = malloc(bits_nr * sizeof(struct block_info));
8243 if (ctx.progress_enabled) {
8244 ctx.tp = TASK_EXTENTS;
8245 task_start(ctx.info);
8249 root1 = root->fs_info->tree_root;
8250 level = btrfs_header_level(root1->node);
8251 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8252 root1->node->start, 0, level, 0,
8253 root1->nodesize, NULL);
8256 root1 = root->fs_info->chunk_root;
8257 level = btrfs_header_level(root1->node);
8258 ret = add_root_item_to_list(&normal_trees, root1->root_key.objectid,
8259 root1->node->start, 0, level, 0,
8260 root1->nodesize, NULL);
8263 btrfs_init_path(&path);
8266 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
8267 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
8272 leaf = path.nodes[0];
8273 slot = path.slots[0];
8274 if (slot >= btrfs_header_nritems(path.nodes[0])) {
8275 ret = btrfs_next_leaf(root, &path);
8278 leaf = path.nodes[0];
8279 slot = path.slots[0];
8281 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
8282 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
8283 unsigned long offset;
8286 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
8287 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
8288 last_snapshot = btrfs_root_last_snapshot(&ri);
8289 if (btrfs_disk_key_objectid(&ri.drop_progress) == 0) {
8290 level = btrfs_root_level(&ri);
8291 level_size = root->nodesize;
8292 ret = add_root_item_to_list(&normal_trees,
8294 btrfs_root_bytenr(&ri),
8295 last_snapshot, level,
8296 0, level_size, NULL);
8300 level = btrfs_root_level(&ri);
8301 level_size = root->nodesize;
8302 objectid = found_key.objectid;
8303 btrfs_disk_key_to_cpu(&found_key,
8305 ret = add_root_item_to_list(&dropping_trees,
8307 btrfs_root_bytenr(&ri),
8308 last_snapshot, level,
8310 level_size, &found_key);
8317 btrfs_release_path(&path);
8320 * check_block can return -EAGAIN if it fixes something, please keep
8321 * this in mind when dealing with return values from these functions, if
8322 * we get -EAGAIN we want to fall through and restart the loop.
8324 ret = deal_root_from_list(&normal_trees, root, bits, bits_nr, &pending,
8325 &seen, &reada, &nodes, &extent_cache,
8326 &chunk_cache, &dev_cache, &block_group_cache,
8333 ret = deal_root_from_list(&dropping_trees, root, bits, bits_nr,
8334 &pending, &seen, &reada, &nodes,
8335 &extent_cache, &chunk_cache, &dev_cache,
8336 &block_group_cache, &dev_extent_cache);
8343 ret = check_chunks(&chunk_cache, &block_group_cache,
8344 &dev_extent_cache, NULL, NULL, NULL, 0);
8351 ret = check_extent_refs(root, &extent_cache);
8358 ret = check_devices(&dev_cache, &dev_extent_cache);
8363 task_stop(ctx.info);
8365 free_corrupt_blocks_tree(root->fs_info->corrupt_blocks);
8366 extent_io_tree_cleanup(&excluded_extents);
8367 root->fs_info->fsck_extent_cache = NULL;
8368 root->fs_info->free_extent_hook = NULL;
8369 root->fs_info->corrupt_blocks = NULL;
8370 root->fs_info->excluded_extents = NULL;
8373 free_chunk_cache_tree(&chunk_cache);
8374 free_device_cache_tree(&dev_cache);
8375 free_block_group_tree(&block_group_cache);
8376 free_device_extent_tree(&dev_extent_cache);
8377 free_extent_cache_tree(&seen);
8378 free_extent_cache_tree(&pending);
8379 free_extent_cache_tree(&reada);
8380 free_extent_cache_tree(&nodes);
8383 free_corrupt_blocks_tree(root->fs_info->corrupt_blocks);
8384 free_extent_cache_tree(&seen);
8385 free_extent_cache_tree(&pending);
8386 free_extent_cache_tree(&reada);
8387 free_extent_cache_tree(&nodes);
8388 free_chunk_cache_tree(&chunk_cache);
8389 free_block_group_tree(&block_group_cache);
8390 free_device_cache_tree(&dev_cache);
8391 free_device_extent_tree(&dev_extent_cache);
8392 free_extent_record_cache(root->fs_info, &extent_cache);
8393 free_root_item_list(&normal_trees);
8394 free_root_item_list(&dropping_trees);
8395 extent_io_tree_cleanup(&excluded_extents);
8399 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
8400 struct btrfs_root *root, int overwrite)
8402 struct extent_buffer *c;
8403 struct extent_buffer *old = root->node;
8406 struct btrfs_disk_key disk_key = {0,0,0};
8412 extent_buffer_get(c);
8415 c = btrfs_alloc_free_block(trans, root,
8417 root->root_key.objectid,
8418 &disk_key, level, 0, 0);
8421 extent_buffer_get(c);
8425 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
8426 btrfs_set_header_level(c, level);
8427 btrfs_set_header_bytenr(c, c->start);
8428 btrfs_set_header_generation(c, trans->transid);
8429 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
8430 btrfs_set_header_owner(c, root->root_key.objectid);
8432 write_extent_buffer(c, root->fs_info->fsid,
8433 btrfs_header_fsid(), BTRFS_FSID_SIZE);
8435 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
8436 btrfs_header_chunk_tree_uuid(c),
8439 btrfs_mark_buffer_dirty(c);
8441 * this case can happen in the following case:
8443 * 1.overwrite previous root.
8445 * 2.reinit reloc data root, this is because we skip pin
8446 * down reloc data tree before which means we can allocate
8447 * same block bytenr here.
8449 if (old->start == c->start) {
8450 btrfs_set_root_generation(&root->root_item,
8452 root->root_item.level = btrfs_header_level(root->node);
8453 ret = btrfs_update_root(trans, root->fs_info->tree_root,
8454 &root->root_key, &root->root_item);
8456 free_extent_buffer(c);
8460 free_extent_buffer(old);
8462 add_root_to_dirty_list(root);
8466 static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
8467 struct extent_buffer *eb, int tree_root)
8469 struct extent_buffer *tmp;
8470 struct btrfs_root_item *ri;
8471 struct btrfs_key key;
8474 int level = btrfs_header_level(eb);
8480 * If we have pinned this block before, don't pin it again.
8481 * This can not only avoid forever loop with broken filesystem
8482 * but also give us some speedups.
8484 if (test_range_bit(&fs_info->pinned_extents, eb->start,
8485 eb->start + eb->len - 1, EXTENT_DIRTY, 0))
8488 btrfs_pin_extent(fs_info, eb->start, eb->len);
8490 nodesize = btrfs_super_nodesize(fs_info->super_copy);
8491 nritems = btrfs_header_nritems(eb);
8492 for (i = 0; i < nritems; i++) {
8494 btrfs_item_key_to_cpu(eb, &key, i);
8495 if (key.type != BTRFS_ROOT_ITEM_KEY)
8497 /* Skip the extent root and reloc roots */
8498 if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
8499 key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
8500 key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
8502 ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
8503 bytenr = btrfs_disk_root_bytenr(eb, ri);
8506 * If at any point we start needing the real root we
8507 * will have to build a stump root for the root we are
8508 * in, but for now this doesn't actually use the root so
8509 * just pass in extent_root.
8511 tmp = read_tree_block(fs_info->extent_root, bytenr,
8513 if (!extent_buffer_uptodate(tmp)) {
8514 fprintf(stderr, "Error reading root block\n");
8517 ret = pin_down_tree_blocks(fs_info, tmp, 0);
8518 free_extent_buffer(tmp);
8522 bytenr = btrfs_node_blockptr(eb, i);
8524 /* If we aren't the tree root don't read the block */
8525 if (level == 1 && !tree_root) {
8526 btrfs_pin_extent(fs_info, bytenr, nodesize);
8530 tmp = read_tree_block(fs_info->extent_root, bytenr,
8532 if (!extent_buffer_uptodate(tmp)) {
8533 fprintf(stderr, "Error reading tree block\n");
8536 ret = pin_down_tree_blocks(fs_info, tmp, tree_root);
8537 free_extent_buffer(tmp);
8546 static int pin_metadata_blocks(struct btrfs_fs_info *fs_info)
8550 ret = pin_down_tree_blocks(fs_info, fs_info->chunk_root->node, 0);
8554 return pin_down_tree_blocks(fs_info, fs_info->tree_root->node, 1);
8557 static int reset_block_groups(struct btrfs_fs_info *fs_info)
8559 struct btrfs_block_group_cache *cache;
8560 struct btrfs_path *path;
8561 struct extent_buffer *leaf;
8562 struct btrfs_chunk *chunk;
8563 struct btrfs_key key;
8567 path = btrfs_alloc_path();
8572 key.type = BTRFS_CHUNK_ITEM_KEY;
8575 ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, path, 0, 0);
8577 btrfs_free_path(path);
8582 * We do this in case the block groups were screwed up and had alloc
8583 * bits that aren't actually set on the chunks. This happens with
8584 * restored images every time and could happen in real life I guess.
8586 fs_info->avail_data_alloc_bits = 0;
8587 fs_info->avail_metadata_alloc_bits = 0;
8588 fs_info->avail_system_alloc_bits = 0;
8590 /* First we need to create the in-memory block groups */
8592 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
8593 ret = btrfs_next_leaf(fs_info->chunk_root, path);
8595 btrfs_free_path(path);
8603 leaf = path->nodes[0];
8604 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
8605 if (key.type != BTRFS_CHUNK_ITEM_KEY) {
8610 chunk = btrfs_item_ptr(leaf, path->slots[0],
8611 struct btrfs_chunk);
8612 btrfs_add_block_group(fs_info, 0,
8613 btrfs_chunk_type(leaf, chunk),
8614 key.objectid, key.offset,
8615 btrfs_chunk_length(leaf, chunk));
8616 set_extent_dirty(&fs_info->free_space_cache, key.offset,
8617 key.offset + btrfs_chunk_length(leaf, chunk),
8623 cache = btrfs_lookup_first_block_group(fs_info, start);
8627 start = cache->key.objectid + cache->key.offset;
8630 btrfs_free_path(path);
8634 static int reset_balance(struct btrfs_trans_handle *trans,
8635 struct btrfs_fs_info *fs_info)
8637 struct btrfs_root *root = fs_info->tree_root;
8638 struct btrfs_path *path;
8639 struct extent_buffer *leaf;
8640 struct btrfs_key key;
8641 int del_slot, del_nr = 0;
8645 path = btrfs_alloc_path();
8649 key.objectid = BTRFS_BALANCE_OBJECTID;
8650 key.type = BTRFS_BALANCE_ITEM_KEY;
8653 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
8658 goto reinit_data_reloc;
8663 ret = btrfs_del_item(trans, root, path);
8666 btrfs_release_path(path);
8668 key.objectid = BTRFS_TREE_RELOC_OBJECTID;
8669 key.type = BTRFS_ROOT_ITEM_KEY;
8672 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
8676 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
8681 ret = btrfs_del_items(trans, root, path,
8688 btrfs_release_path(path);
8691 ret = btrfs_search_slot(trans, root, &key, path,
8698 leaf = path->nodes[0];
8699 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
8700 if (key.objectid > BTRFS_TREE_RELOC_OBJECTID)
8702 if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
8707 del_slot = path->slots[0];
8716 ret = btrfs_del_items(trans, root, path, del_slot, del_nr);
8720 btrfs_release_path(path);
8723 key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
8724 key.type = BTRFS_ROOT_ITEM_KEY;
8725 key.offset = (u64)-1;
8726 root = btrfs_read_fs_root(fs_info, &key);
8728 fprintf(stderr, "Error reading data reloc tree\n");
8729 ret = PTR_ERR(root);
8732 record_root_in_trans(trans, root);
8733 ret = btrfs_fsck_reinit_root(trans, root, 0);
8736 ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID);
8738 btrfs_free_path(path);
8742 static int reinit_extent_tree(struct btrfs_trans_handle *trans,
8743 struct btrfs_fs_info *fs_info)
8749 * The only reason we don't do this is because right now we're just
8750 * walking the trees we find and pinning down their bytes, we don't look
8751 * at any of the leaves. In order to do mixed groups we'd have to check
8752 * the leaves of any fs roots and pin down the bytes for any file
8753 * extents we find. Not hard but why do it if we don't have to?
8755 if (btrfs_fs_incompat(fs_info, BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)) {
8756 fprintf(stderr, "We don't support re-initing the extent tree "
8757 "for mixed block groups yet, please notify a btrfs "
8758 "developer you want to do this so they can add this "
8759 "functionality.\n");
8764 * first we need to walk all of the trees except the extent tree and pin
8765 * down the bytes that are in use so we don't overwrite any existing
8768 ret = pin_metadata_blocks(fs_info);
8770 fprintf(stderr, "error pinning down used bytes\n");
8775 * Need to drop all the block groups since we're going to recreate all
8778 btrfs_free_block_groups(fs_info);
8779 ret = reset_block_groups(fs_info);
8781 fprintf(stderr, "error resetting the block groups\n");
8785 /* Ok we can allocate now, reinit the extent root */
8786 ret = btrfs_fsck_reinit_root(trans, fs_info->extent_root, 0);
8788 fprintf(stderr, "extent root initialization failed\n");
8790 * When the transaction code is updated we should end the
8791 * transaction, but for now progs only knows about commit so
8792 * just return an error.
8798 * Now we have all the in-memory block groups setup so we can make
8799 * allocations properly, and the metadata we care about is safe since we
8800 * pinned all of it above.
8803 struct btrfs_block_group_cache *cache;
8805 cache = btrfs_lookup_first_block_group(fs_info, start);
8808 start = cache->key.objectid + cache->key.offset;
8809 ret = btrfs_insert_item(trans, fs_info->extent_root,
8810 &cache->key, &cache->item,
8811 sizeof(cache->item));
8813 fprintf(stderr, "Error adding block group\n");
8816 btrfs_extent_post_op(trans, fs_info->extent_root);
8819 ret = reset_balance(trans, fs_info);
8821 fprintf(stderr, "error reseting the pending balance\n");
8826 static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb)
8828 struct btrfs_path *path;
8829 struct btrfs_trans_handle *trans;
8830 struct btrfs_key key;
8833 printf("Recowing metadata block %llu\n", eb->start);
8834 key.objectid = btrfs_header_owner(eb);
8835 key.type = BTRFS_ROOT_ITEM_KEY;
8836 key.offset = (u64)-1;
8838 root = btrfs_read_fs_root(root->fs_info, &key);
8840 fprintf(stderr, "Couldn't find owner root %llu\n",
8842 return PTR_ERR(root);
8845 path = btrfs_alloc_path();
8849 trans = btrfs_start_transaction(root, 1);
8850 if (IS_ERR(trans)) {
8851 btrfs_free_path(path);
8852 return PTR_ERR(trans);
8855 path->lowest_level = btrfs_header_level(eb);
8856 if (path->lowest_level)
8857 btrfs_node_key_to_cpu(eb, &key, 0);
8859 btrfs_item_key_to_cpu(eb, &key, 0);
8861 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
8862 btrfs_commit_transaction(trans, root);
8863 btrfs_free_path(path);
8867 static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad)
8869 struct btrfs_path *path;
8870 struct btrfs_trans_handle *trans;
8871 struct btrfs_key key;
8874 printf("Deleting bad item [%llu,%u,%llu]\n", bad->key.objectid,
8875 bad->key.type, bad->key.offset);
8876 key.objectid = bad->root_id;
8877 key.type = BTRFS_ROOT_ITEM_KEY;
8878 key.offset = (u64)-1;
8880 root = btrfs_read_fs_root(root->fs_info, &key);
8882 fprintf(stderr, "Couldn't find owner root %llu\n",
8884 return PTR_ERR(root);
8887 path = btrfs_alloc_path();
8891 trans = btrfs_start_transaction(root, 1);
8892 if (IS_ERR(trans)) {
8893 btrfs_free_path(path);
8894 return PTR_ERR(trans);
8897 ret = btrfs_search_slot(trans, root, &bad->key, path, -1, 1);
8903 ret = btrfs_del_item(trans, root, path);
8905 btrfs_commit_transaction(trans, root);
8906 btrfs_free_path(path);
8910 static int zero_log_tree(struct btrfs_root *root)
8912 struct btrfs_trans_handle *trans;
8915 trans = btrfs_start_transaction(root, 1);
8916 if (IS_ERR(trans)) {
8917 ret = PTR_ERR(trans);
8920 btrfs_set_super_log_root(root->fs_info->super_copy, 0);
8921 btrfs_set_super_log_root_level(root->fs_info->super_copy, 0);
8922 ret = btrfs_commit_transaction(trans, root);
8926 static int populate_csum(struct btrfs_trans_handle *trans,
8927 struct btrfs_root *csum_root, char *buf, u64 start,
8934 while (offset < len) {
8935 sectorsize = csum_root->sectorsize;
8936 ret = read_extent_data(csum_root, buf, start + offset,
8940 ret = btrfs_csum_file_block(trans, csum_root, start + len,
8941 start + offset, buf, sectorsize);
8944 offset += sectorsize;
8949 static int fill_csum_tree_from_one_fs_root(struct btrfs_trans_handle *trans,
8950 struct btrfs_root *csum_root,
8951 struct btrfs_root *cur_root)
8953 struct btrfs_path *path;
8954 struct btrfs_key key;
8955 struct extent_buffer *node;
8956 struct btrfs_file_extent_item *fi;
8963 path = btrfs_alloc_path();
8966 buf = malloc(cur_root->fs_info->csum_root->sectorsize);
8976 ret = btrfs_search_slot(NULL, cur_root, &key, path, 0, 0);
8979 /* Iterate all regular file extents and fill its csum */
8981 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
8983 if (key.type != BTRFS_EXTENT_DATA_KEY)
8985 node = path->nodes[0];
8986 slot = path->slots[0];
8987 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
8988 if (btrfs_file_extent_type(node, fi) != BTRFS_FILE_EXTENT_REG)
8990 start = btrfs_file_extent_disk_bytenr(node, fi);
8991 len = btrfs_file_extent_disk_num_bytes(node, fi);
8993 ret = populate_csum(trans, csum_root, buf, start, len);
9000 * TODO: if next leaf is corrupted, jump to nearest next valid
9003 ret = btrfs_next_item(cur_root, path);
9013 btrfs_free_path(path);
9018 static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans,
9019 struct btrfs_root *csum_root)
9021 struct btrfs_fs_info *fs_info = csum_root->fs_info;
9022 struct btrfs_path *path;
9023 struct btrfs_root *tree_root = fs_info->tree_root;
9024 struct btrfs_root *cur_root;
9025 struct extent_buffer *node;
9026 struct btrfs_key key;
9030 path = btrfs_alloc_path();
9034 key.objectid = BTRFS_FS_TREE_OBJECTID;
9036 key.type = BTRFS_ROOT_ITEM_KEY;
9038 ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0);
9047 node = path->nodes[0];
9048 slot = path->slots[0];
9049 btrfs_item_key_to_cpu(node, &key, slot);
9050 if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
9052 if (key.type != BTRFS_ROOT_ITEM_KEY)
9054 if (!is_fstree(key.objectid))
9056 key.offset = (u64)-1;
9058 cur_root = btrfs_read_fs_root(fs_info, &key);
9059 if (IS_ERR(cur_root) || !cur_root) {
9060 fprintf(stderr, "Fail to read fs/subvol tree: %lld\n",
9064 ret = fill_csum_tree_from_one_fs_root(trans, csum_root,
9069 ret = btrfs_next_item(tree_root, path);
9079 btrfs_free_path(path);
9083 static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans,
9084 struct btrfs_root *csum_root)
9086 struct btrfs_root *extent_root = csum_root->fs_info->extent_root;
9087 struct btrfs_path *path;
9088 struct btrfs_extent_item *ei;
9089 struct extent_buffer *leaf;
9091 struct btrfs_key key;
9094 path = btrfs_alloc_path();
9099 key.type = BTRFS_EXTENT_ITEM_KEY;
9102 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
9104 btrfs_free_path(path);
9108 buf = malloc(csum_root->sectorsize);
9110 btrfs_free_path(path);
9115 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
9116 ret = btrfs_next_leaf(extent_root, path);
9124 leaf = path->nodes[0];
9126 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
9127 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
9132 ei = btrfs_item_ptr(leaf, path->slots[0],
9133 struct btrfs_extent_item);
9134 if (!(btrfs_extent_flags(leaf, ei) &
9135 BTRFS_EXTENT_FLAG_DATA)) {
9140 ret = populate_csum(trans, csum_root, buf, key.objectid,
9147 btrfs_free_path(path);
9153 * Recalculate the csum and put it into the csum tree.
9155 * Extent tree init will wipe out all the extent info, so in that case, we
9156 * can't depend on extent tree, but use fs tree. If search_fs_tree is set, we
9157 * will use fs/subvol trees to init the csum tree.
9159 static int fill_csum_tree(struct btrfs_trans_handle *trans,
9160 struct btrfs_root *csum_root,
9164 return fill_csum_tree_from_fs(trans, csum_root);
9166 return fill_csum_tree_from_extent(trans, csum_root);
9169 static void free_roots_info_cache(void)
9171 if (!roots_info_cache)
9174 while (!cache_tree_empty(roots_info_cache)) {
9175 struct cache_extent *entry;
9176 struct root_item_info *rii;
9178 entry = first_cache_extent(roots_info_cache);
9181 remove_cache_extent(roots_info_cache, entry);
9182 rii = container_of(entry, struct root_item_info, cache_extent);
9186 free(roots_info_cache);
9187 roots_info_cache = NULL;
9190 static int build_roots_info_cache(struct btrfs_fs_info *info)
9193 struct btrfs_key key;
9194 struct extent_buffer *leaf;
9195 struct btrfs_path *path;
9197 if (!roots_info_cache) {
9198 roots_info_cache = malloc(sizeof(*roots_info_cache));
9199 if (!roots_info_cache)
9201 cache_tree_init(roots_info_cache);
9204 path = btrfs_alloc_path();
9209 key.type = BTRFS_EXTENT_ITEM_KEY;
9212 ret = btrfs_search_slot(NULL, info->extent_root, &key, path, 0, 0);
9215 leaf = path->nodes[0];
9218 struct btrfs_key found_key;
9219 struct btrfs_extent_item *ei;
9220 struct btrfs_extent_inline_ref *iref;
9221 int slot = path->slots[0];
9226 struct cache_extent *entry;
9227 struct root_item_info *rii;
9229 if (slot >= btrfs_header_nritems(leaf)) {
9230 ret = btrfs_next_leaf(info->extent_root, path);
9237 leaf = path->nodes[0];
9238 slot = path->slots[0];
9241 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
9243 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
9244 found_key.type != BTRFS_METADATA_ITEM_KEY)
9247 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
9248 flags = btrfs_extent_flags(leaf, ei);
9250 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
9251 !(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))
9254 if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
9255 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
9256 level = found_key.offset;
9258 struct btrfs_tree_block_info *binfo;
9260 binfo = (struct btrfs_tree_block_info *)(ei + 1);
9261 iref = (struct btrfs_extent_inline_ref *)(binfo + 1);
9262 level = btrfs_tree_block_level(leaf, binfo);
9266 * For a root extent, it must be of the following type and the
9267 * first (and only one) iref in the item.
9269 type = btrfs_extent_inline_ref_type(leaf, iref);
9270 if (type != BTRFS_TREE_BLOCK_REF_KEY)
9273 root_id = btrfs_extent_inline_ref_offset(leaf, iref);
9274 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9276 rii = malloc(sizeof(struct root_item_info));
9281 rii->cache_extent.start = root_id;
9282 rii->cache_extent.size = 1;
9283 rii->level = (u8)-1;
9284 entry = &rii->cache_extent;
9285 ret = insert_cache_extent(roots_info_cache, entry);
9288 rii = container_of(entry, struct root_item_info,
9292 ASSERT(rii->cache_extent.start == root_id);
9293 ASSERT(rii->cache_extent.size == 1);
9295 if (level > rii->level || rii->level == (u8)-1) {
9297 rii->bytenr = found_key.objectid;
9298 rii->gen = btrfs_extent_generation(leaf, ei);
9299 rii->node_count = 1;
9300 } else if (level == rii->level) {
9308 btrfs_free_path(path);
9313 static int maybe_repair_root_item(struct btrfs_fs_info *info,
9314 struct btrfs_path *path,
9315 const struct btrfs_key *root_key,
9316 const int read_only_mode)
9318 const u64 root_id = root_key->objectid;
9319 struct cache_extent *entry;
9320 struct root_item_info *rii;
9321 struct btrfs_root_item ri;
9322 unsigned long offset;
9324 entry = lookup_cache_extent(roots_info_cache, root_id, 1);
9327 "Error: could not find extent items for root %llu\n",
9328 root_key->objectid);
9332 rii = container_of(entry, struct root_item_info, cache_extent);
9333 ASSERT(rii->cache_extent.start == root_id);
9334 ASSERT(rii->cache_extent.size == 1);
9336 if (rii->node_count != 1) {
9338 "Error: could not find btree root extent for root %llu\n",
9343 offset = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
9344 read_extent_buffer(path->nodes[0], &ri, offset, sizeof(ri));
9346 if (btrfs_root_bytenr(&ri) != rii->bytenr ||
9347 btrfs_root_level(&ri) != rii->level ||
9348 btrfs_root_generation(&ri) != rii->gen) {
9351 * If we're in repair mode but our caller told us to not update
9352 * the root item, i.e. just check if it needs to be updated, don't
9353 * print this message, since the caller will call us again shortly
9354 * for the same root item without read only mode (the caller will
9355 * open a transaction first).
9357 if (!(read_only_mode && repair))
9359 "%sroot item for root %llu,"
9360 " current bytenr %llu, current gen %llu, current level %u,"
9361 " new bytenr %llu, new gen %llu, new level %u\n",
9362 (read_only_mode ? "" : "fixing "),
9364 btrfs_root_bytenr(&ri), btrfs_root_generation(&ri),
9365 btrfs_root_level(&ri),
9366 rii->bytenr, rii->gen, rii->level);
9368 if (btrfs_root_generation(&ri) > rii->gen) {
9370 "root %llu has a root item with a more recent gen (%llu) compared to the found root node (%llu)\n",
9371 root_id, btrfs_root_generation(&ri), rii->gen);
9375 if (!read_only_mode) {
9376 btrfs_set_root_bytenr(&ri, rii->bytenr);
9377 btrfs_set_root_level(&ri, rii->level);
9378 btrfs_set_root_generation(&ri, rii->gen);
9379 write_extent_buffer(path->nodes[0], &ri,
9380 offset, sizeof(ri));
9390 * A regression introduced in the 3.17 kernel (more specifically in 3.17-rc2),
9391 * caused read-only snapshots to be corrupted if they were created at a moment
9392 * when the source subvolume/snapshot had orphan items. The issue was that the
9393 * on-disk root items became incorrect, referring to the pre orphan cleanup root
9394 * node instead of the post orphan cleanup root node.
9395 * So this function, and its callees, just detects and fixes those cases. Even
9396 * though the regression was for read-only snapshots, this function applies to
9397 * any snapshot/subvolume root.
9398 * This must be run before any other repair code - not doing it so, makes other
9399 * repair code delete or modify backrefs in the extent tree for example, which
9400 * will result in an inconsistent fs after repairing the root items.
9402 static int repair_root_items(struct btrfs_fs_info *info)
9404 struct btrfs_path *path = NULL;
9405 struct btrfs_key key;
9406 struct extent_buffer *leaf;
9407 struct btrfs_trans_handle *trans = NULL;
9412 ret = build_roots_info_cache(info);
9416 path = btrfs_alloc_path();
9422 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
9423 key.type = BTRFS_ROOT_ITEM_KEY;
9428 * Avoid opening and committing transactions if a leaf doesn't have
9429 * any root items that need to be fixed, so that we avoid rotating
9430 * backup roots unnecessarily.
9433 trans = btrfs_start_transaction(info->tree_root, 1);
9434 if (IS_ERR(trans)) {
9435 ret = PTR_ERR(trans);
9440 ret = btrfs_search_slot(trans, info->tree_root, &key, path,
9444 leaf = path->nodes[0];
9447 struct btrfs_key found_key;
9449 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
9450 int no_more_keys = find_next_key(path, &key);
9452 btrfs_release_path(path);
9454 ret = btrfs_commit_transaction(trans,
9466 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
9468 if (found_key.type != BTRFS_ROOT_ITEM_KEY)
9470 if (found_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
9473 ret = maybe_repair_root_item(info, path, &found_key,
9478 if (!trans && repair) {
9481 btrfs_release_path(path);
9491 free_roots_info_cache();
9492 btrfs_free_path(path);
9494 btrfs_commit_transaction(trans, info->tree_root);
9501 const char * const cmd_check_usage[] = {
9502 "btrfs check [options] <device>",
9503 "Check structural inegrity of a filesystem (unmounted).",
9504 "Check structural inegrity of an unmounted filesystem. Verify internal",
9505 "trees' consistency and item connectivity. In the repair mode try to",
9506 "fix the problems found.",
9507 "WARNING: the repair mode is considered dangerous",
9509 "-s|--super <superblock> use this superblock copy",
9510 "-b|--backup use the first valid backup root copy",
9511 "--repair try to repair the filesystem",
9512 "--readonly run in read-only mode (default)",
9513 "--init-csum-tree create a new CRC tree",
9514 "--init-extent-tree create a new extent tree",
9515 "--check-data-csum verify checkums of data blocks",
9516 "-Q|--qgroup-report print a report on qgroup consistency",
9517 "-E|--subvol-extents <subvolid>",
9518 " print subvolume extents and sharing state",
9519 "-r|--tree-root <bytenr> use the given bytenr for the tree root",
9520 "--chunk-root <bytenr> use the given bytenr for the chunk tree root",
9521 "-p|--progress indicate progress",
9525 int cmd_check(int argc, char **argv)
9527 struct cache_tree root_cache;
9528 struct btrfs_root *root;
9529 struct btrfs_fs_info *info;
9532 u64 tree_root_bytenr = 0;
9533 u64 chunk_root_bytenr = 0;
9534 char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
9537 int init_csum_tree = 0;
9539 int qgroup_report = 0;
9540 enum btrfs_open_ctree_flags ctree_flags = OPEN_CTREE_EXCLUSIVE;
9544 enum { GETOPT_VAL_REPAIR = 257, GETOPT_VAL_INIT_CSUM,
9545 GETOPT_VAL_INIT_EXTENT, GETOPT_VAL_CHECK_CSUM,
9546 GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE };
9547 static const struct option long_options[] = {
9548 { "super", required_argument, NULL, 's' },
9549 { "repair", no_argument, NULL, GETOPT_VAL_REPAIR },
9550 { "readonly", no_argument, NULL, GETOPT_VAL_READONLY },
9551 { "init-csum-tree", no_argument, NULL,
9552 GETOPT_VAL_INIT_CSUM },
9553 { "init-extent-tree", no_argument, NULL,
9554 GETOPT_VAL_INIT_EXTENT },
9555 { "check-data-csum", no_argument, NULL,
9556 GETOPT_VAL_CHECK_CSUM },
9557 { "backup", no_argument, NULL, 'b' },
9558 { "subvol-extents", required_argument, NULL, 'E' },
9559 { "qgroup-report", no_argument, NULL, 'Q' },
9560 { "tree-root", required_argument, NULL, 'r' },
9561 { "chunk-root", required_argument, NULL,
9562 GETOPT_VAL_CHUNK_TREE },
9563 { "progress", no_argument, NULL, 'p' },
9567 c = getopt_long(argc, argv, "as:br:p", long_options, NULL);
9571 case 'a': /* ignored */ break;
9573 ctree_flags |= OPEN_CTREE_BACKUP_ROOT;
9576 num = arg_strtou64(optarg);
9577 if (num >= BTRFS_SUPER_MIRROR_MAX) {
9579 "ERROR: super mirror should be less than: %d\n",
9580 BTRFS_SUPER_MIRROR_MAX);
9583 bytenr = btrfs_sb_offset(((int)num));
9584 printf("using SB copy %llu, bytenr %llu\n", num,
9585 (unsigned long long)bytenr);
9591 subvolid = arg_strtou64(optarg);
9594 tree_root_bytenr = arg_strtou64(optarg);
9596 case GETOPT_VAL_CHUNK_TREE:
9597 chunk_root_bytenr = arg_strtou64(optarg);
9600 ctx.progress_enabled = true;
9604 usage(cmd_check_usage);
9605 case GETOPT_VAL_REPAIR:
9606 printf("enabling repair mode\n");
9608 ctree_flags |= OPEN_CTREE_WRITES;
9610 case GETOPT_VAL_READONLY:
9613 case GETOPT_VAL_INIT_CSUM:
9614 printf("Creating a new CRC tree\n");
9617 ctree_flags |= OPEN_CTREE_WRITES;
9619 case GETOPT_VAL_INIT_EXTENT:
9620 init_extent_tree = 1;
9621 ctree_flags |= (OPEN_CTREE_WRITES |
9622 OPEN_CTREE_NO_BLOCK_GROUPS);
9625 case GETOPT_VAL_CHECK_CSUM:
9626 check_data_csum = 1;
9631 if (check_argc_exact(argc - optind, 1))
9632 usage(cmd_check_usage);
9634 if (ctx.progress_enabled) {
9635 ctx.tp = TASK_NOTHING;
9636 ctx.info = task_init(print_status_check, print_status_return, &ctx);
9639 /* This check is the only reason for --readonly to exist */
9640 if (readonly && repair) {
9641 fprintf(stderr, "Repair options are not compatible with --readonly\n");
9646 cache_tree_init(&root_cache);
9648 if((ret = check_mounted(argv[optind])) < 0) {
9649 fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret));
9652 fprintf(stderr, "%s is currently mounted. Aborting.\n", argv[optind]);
9657 /* only allow partial opening under repair mode */
9659 ctree_flags |= OPEN_CTREE_PARTIAL;
9661 info = open_ctree_fs_info(argv[optind], bytenr, tree_root_bytenr,
9662 chunk_root_bytenr, ctree_flags);
9664 fprintf(stderr, "Couldn't open file system\n");
9670 root = info->fs_root;
9673 * repair mode will force us to commit transaction which
9674 * will make us fail to load log tree when mounting.
9676 if (repair && btrfs_super_log_root(info->super_copy)) {
9677 ret = ask_user("repair mode will force to clear out log tree, Are you sure?");
9682 ret = zero_log_tree(root);
9684 fprintf(stderr, "fail to zero log tree\n");
9689 uuid_unparse(info->super_copy->fsid, uuidbuf);
9690 if (qgroup_report) {
9691 printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
9693 ret = qgroup_verify_all(info);
9695 ret = report_qgroups(1);
9699 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
9700 subvolid, argv[optind], uuidbuf);
9701 ret = print_extent_state(info, subvolid);
9704 printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
9706 if (!extent_buffer_uptodate(info->tree_root->node) ||
9707 !extent_buffer_uptodate(info->dev_root->node) ||
9708 !extent_buffer_uptodate(info->chunk_root->node)) {
9709 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
9714 if (init_extent_tree || init_csum_tree) {
9715 struct btrfs_trans_handle *trans;
9717 trans = btrfs_start_transaction(info->extent_root, 0);
9718 if (IS_ERR(trans)) {
9719 fprintf(stderr, "Error starting transaction\n");
9720 ret = PTR_ERR(trans);
9724 if (init_extent_tree) {
9725 printf("Creating a new extent tree\n");
9726 ret = reinit_extent_tree(trans, info);
9731 if (init_csum_tree) {
9732 fprintf(stderr, "Reinit crc root\n");
9733 ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0);
9735 fprintf(stderr, "crc root initialization failed\n");
9740 ret = fill_csum_tree(trans, info->csum_root,
9743 fprintf(stderr, "crc refilling failed\n");
9748 * Ok now we commit and run the normal fsck, which will add
9749 * extent entries for all of the items it finds.
9751 ret = btrfs_commit_transaction(trans, info->extent_root);
9755 if (!extent_buffer_uptodate(info->extent_root->node)) {
9756 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
9760 if (!extent_buffer_uptodate(info->csum_root->node)) {
9761 fprintf(stderr, "Checksum root corrupted, rerun with --init-csum-tree option\n");
9766 if (!ctx.progress_enabled)
9767 fprintf(stderr, "checking extents\n");
9768 ret = check_chunks_and_extents(root);
9770 fprintf(stderr, "Errors found in extent allocation tree or chunk allocation\n");
9772 ret = repair_root_items(info);
9776 fprintf(stderr, "Fixed %d roots.\n", ret);
9778 } else if (ret > 0) {
9780 "Found %d roots with an outdated root item.\n",
9783 "Please run a filesystem check with the option --repair to fix them.\n");
9788 if (!ctx.progress_enabled) {
9789 if (btrfs_fs_compat_ro(info, BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE))
9790 fprintf(stderr, "checking free space tree\n");
9792 fprintf(stderr, "checking free space cache\n");
9794 ret = check_space_cache(root);
9799 * We used to have to have these hole extents in between our real
9800 * extents so if we don't have this flag set we need to make sure there
9801 * are no gaps in the file extents for inodes, otherwise we can just
9802 * ignore it when this happens.
9804 no_holes = btrfs_fs_incompat(root->fs_info,
9805 BTRFS_FEATURE_INCOMPAT_NO_HOLES);
9806 if (!ctx.progress_enabled)
9807 fprintf(stderr, "checking fs roots\n");
9808 ret = check_fs_roots(root, &root_cache);
9812 fprintf(stderr, "checking csums\n");
9813 ret = check_csums(root);
9817 fprintf(stderr, "checking root refs\n");
9818 ret = check_root_refs(root, &root_cache);
9822 while (repair && !list_empty(&root->fs_info->recow_ebs)) {
9823 struct extent_buffer *eb;
9825 eb = list_first_entry(&root->fs_info->recow_ebs,
9826 struct extent_buffer, recow);
9827 list_del_init(&eb->recow);
9828 ret = recow_extent_buffer(root, eb);
9833 while (!list_empty(&delete_items)) {
9834 struct bad_item *bad;
9836 bad = list_first_entry(&delete_items, struct bad_item, list);
9837 list_del_init(&bad->list);
9839 ret = delete_bad_item(root, bad);
9843 if (info->quota_enabled) {
9845 fprintf(stderr, "checking quota groups\n");
9846 err = qgroup_verify_all(info);
9851 if (!list_empty(&root->fs_info->recow_ebs)) {
9852 fprintf(stderr, "Transid errors in file system\n");
9856 /* Don't override original ret */
9860 ret = report_qgroups(0);
9861 if (found_old_backref) { /*
9862 * there was a disk format change when mixed
9863 * backref was in testing tree. The old format
9864 * existed about one week.
9866 printf("\n * Found old mixed backref format. "
9867 "The old format is not supported! *"
9868 "\n * Please mount the FS in readonly mode, "
9869 "backup data and re-format the FS. *\n\n");
9872 printf("found %llu bytes used err is %d\n",
9873 (unsigned long long)bytes_used, ret);
9874 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
9875 printf("total tree bytes: %llu\n",
9876 (unsigned long long)total_btree_bytes);
9877 printf("total fs tree bytes: %llu\n",
9878 (unsigned long long)total_fs_tree_bytes);
9879 printf("total extent tree bytes: %llu\n",
9880 (unsigned long long)total_extent_tree_bytes);
9881 printf("btree space waste bytes: %llu\n",
9882 (unsigned long long)btree_space_waste);
9883 printf("file data blocks allocated: %llu\n referenced %llu\n",
9884 (unsigned long long)data_bytes_allocated,
9885 (unsigned long long)data_bytes_referenced);
9887 free_root_recs_tree(&root_cache);
9891 if (ctx.progress_enabled)
9892 task_deinit(ctx.info);