2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public
4 * License v2 as published by the Free Software Foundation.
6 * This program is distributed in the hope that it will be useful,
7 * but WITHOUT ANY WARRANTY; without even the implied warranty of
8 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
9 * General Public License for more details.
11 * You should have received a copy of the GNU General Public
12 * License along with this program; if not, write to the
13 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
14 * Boston, MA 021110-1307, USA.
20 #include "transaction.h"
28 #include "check/mode-common.h"
29 #include "check/mode-lowmem.h"
31 static u64 last_allocated_chunk
;
33 static int calc_extent_flag(struct btrfs_root
*root
, struct extent_buffer
*eb
,
36 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
37 struct btrfs_root_item
*ri
= &root
->root_item
;
38 struct btrfs_extent_inline_ref
*iref
;
39 struct btrfs_extent_item
*ei
;
41 struct btrfs_path
*path
= NULL
;
52 * Except file/reloc tree, we can not have FULL BACKREF MODE
54 if (root
->objectid
< BTRFS_FIRST_FREE_OBJECTID
)
58 if (eb
->start
== btrfs_root_bytenr(ri
))
61 if (btrfs_header_flag(eb
, BTRFS_HEADER_FLAG_RELOC
))
64 owner
= btrfs_header_owner(eb
);
65 if (owner
== root
->objectid
)
68 path
= btrfs_alloc_path();
72 key
.objectid
= btrfs_header_bytenr(eb
);
76 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, path
, 0, 0);
83 ret
= btrfs_previous_extent_item(extent_root
, path
,
89 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
92 slot
= path
->slots
[0];
93 ei
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item
);
95 flags
= btrfs_extent_flags(eb
, ei
);
96 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
)
99 ptr
= (unsigned long)(ei
+ 1);
100 end
= (unsigned long)ei
+ btrfs_item_size_nr(eb
, slot
);
102 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
)
103 ptr
+= sizeof(struct btrfs_tree_block_info
);
106 /* Reached extent item ends normally */
110 /* Beyond extent item end, wrong item size */
112 error("extent item at bytenr %llu slot %d has wrong size",
117 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
118 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
119 type
= btrfs_extent_inline_ref_type(eb
, iref
);
121 if (type
== BTRFS_TREE_BLOCK_REF_KEY
&& offset
== owner
)
123 ptr
+= btrfs_extent_inline_ref_size(type
);
127 *flags_ret
&= ~BTRFS_BLOCK_FLAG_FULL_BACKREF
;
131 *flags_ret
|= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
133 btrfs_free_path(path
);
138 * for a tree node or leaf, if it's shared, indeed we don't need to iterate it
139 * in every fs or file tree check. Here we find its all root ids, and only check
140 * it in the fs or file tree which has the smallest root id.
142 static int need_check(struct btrfs_root
*root
, struct ulist
*roots
)
144 struct rb_node
*node
;
145 struct ulist_node
*u
;
148 * @roots can be empty if it belongs to tree reloc tree
149 * In that case, we should always check the leaf, as we can't use
150 * the tree owner to ensure some other root will check it.
152 if (roots
->nnodes
== 1 || roots
->nnodes
== 0)
155 node
= rb_first(&roots
->root
);
156 u
= rb_entry(node
, struct ulist_node
, rb_node
);
158 * current root id is not smallest, we skip it and let it be checked
159 * in the fs or file tree who hash the smallest root id.
161 if (root
->objectid
!= u
->val
)
168 * for a tree node or leaf, we record its reference count, so later if we still
169 * process this node or leaf, don't need to compute its reference count again.
171 * @bytenr if @bytenr == (u64)-1, only update nrefs->full_backref[level]
173 static int update_nodes_refs(struct btrfs_root
*root
, u64 bytenr
,
174 struct extent_buffer
*eb
, struct node_refs
*nrefs
,
175 u64 level
, int check_all
)
180 int root_level
= btrfs_header_level(root
->node
);
184 if (nrefs
->bytenr
[level
] == bytenr
)
187 if (bytenr
!= (u64
)-1) {
188 /* the return value of this function seems a mistake */
189 ret
= btrfs_lookup_extent_info(NULL
, root
->fs_info
, bytenr
,
190 level
, 1, &refs
, &flags
);
192 if (ret
< 0 && !check_all
)
195 nrefs
->bytenr
[level
] = bytenr
;
196 nrefs
->refs
[level
] = refs
;
197 nrefs
->full_backref
[level
] = 0;
198 nrefs
->checked
[level
] = 0;
201 ret
= btrfs_find_all_roots(NULL
, root
->fs_info
, bytenr
,
206 check
= need_check(root
, roots
);
208 nrefs
->need_check
[level
] = check
;
211 nrefs
->need_check
[level
] = 1;
213 if (level
== root_level
) {
214 nrefs
->need_check
[level
] = 1;
217 * The node refs may have not been
218 * updated if upper needs checking (the
219 * lowest root_objectid) the node can
222 nrefs
->need_check
[level
] =
223 nrefs
->need_check
[level
+ 1];
229 if (check_all
&& eb
) {
230 calc_extent_flag(root
, eb
, &flags
);
231 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
)
232 nrefs
->full_backref
[level
] = 1;
239 * Mark all extents unfree in the block group. And set @block_group->cached
240 * according to @cache.
242 static int modify_block_group_cache(struct btrfs_fs_info
*fs_info
,
243 struct btrfs_block_group_cache
*block_group
, int cache
)
245 struct extent_io_tree
*free_space_cache
= &fs_info
->free_space_cache
;
246 u64 start
= block_group
->key
.objectid
;
247 u64 end
= start
+ block_group
->key
.offset
;
249 if (cache
&& !block_group
->cached
) {
250 block_group
->cached
= 1;
251 clear_extent_dirty(free_space_cache
, start
, end
- 1);
254 if (!cache
&& block_group
->cached
) {
255 block_group
->cached
= 0;
256 clear_extent_dirty(free_space_cache
, start
, end
- 1);
262 * Modify block groups which have @flags unfree in free space cache.
264 * @cache: if 0, clear block groups cache state;
265 * not 0, mark blocks groups cached.
267 static int modify_block_groups_cache(struct btrfs_fs_info
*fs_info
, u64 flags
,
270 struct btrfs_root
*root
= fs_info
->extent_root
;
271 struct btrfs_key key
;
272 struct btrfs_path path
;
273 struct btrfs_block_group_cache
*bg_cache
;
274 struct btrfs_block_group_item
*bi
;
275 struct btrfs_block_group_item bg_item
;
276 struct extent_buffer
*eb
;
281 key
.type
= BTRFS_BLOCK_GROUP_ITEM_KEY
;
284 btrfs_init_path(&path
);
285 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
287 error("fail to search block groups due to %s", strerror(-ret
));
293 slot
= path
.slots
[0];
294 btrfs_item_key_to_cpu(eb
, &key
, slot
);
295 bg_cache
= btrfs_lookup_block_group(fs_info
, key
.objectid
);
301 bi
= btrfs_item_ptr(eb
, slot
, struct btrfs_block_group_item
);
302 read_extent_buffer(eb
, &bg_item
, (unsigned long)bi
,
304 if (btrfs_block_group_flags(&bg_item
) & flags
)
305 modify_block_group_cache(fs_info
, bg_cache
, cache
);
307 ret
= btrfs_next_item(root
, &path
);
317 btrfs_release_path(&path
);
321 static int mark_block_groups_full(struct btrfs_fs_info
*fs_info
, u64 flags
)
323 return modify_block_groups_cache(fs_info
, flags
, 1);
326 static int clear_block_groups_full(struct btrfs_fs_info
*fs_info
, u64 flags
)
328 return modify_block_groups_cache(fs_info
, flags
, 0);
331 static int create_chunk_and_block_group(struct btrfs_fs_info
*fs_info
,
332 u64 flags
, u64
*start
, u64
*nbytes
)
334 struct btrfs_trans_handle
*trans
;
335 struct btrfs_root
*root
= fs_info
->extent_root
;
338 if ((flags
& BTRFS_BLOCK_GROUP_TYPE_MASK
) == 0)
341 trans
= btrfs_start_transaction(root
, 1);
343 ret
= PTR_ERR(trans
);
344 error("error starting transaction %s", strerror(-ret
));
347 ret
= btrfs_alloc_chunk(trans
, fs_info
, start
, nbytes
, flags
);
349 error("fail to allocate new chunk %s", strerror(-ret
));
352 ret
= btrfs_make_block_group(trans
, fs_info
, 0, flags
, *start
,
355 error("fail to make block group for chunk %llu %llu %s",
356 *start
, *nbytes
, strerror(-ret
));
360 btrfs_commit_transaction(trans
, root
);
364 static int force_cow_in_new_chunk(struct btrfs_fs_info
*fs_info
,
367 struct btrfs_block_group_cache
*bg
;
374 alloc_profile
= (fs_info
->avail_metadata_alloc_bits
&
375 fs_info
->metadata_alloc_profile
);
376 flags
= BTRFS_BLOCK_GROUP_METADATA
| alloc_profile
;
377 if (btrfs_fs_incompat(fs_info
, MIXED_GROUPS
))
378 flags
|= BTRFS_BLOCK_GROUP_DATA
;
380 ret
= create_chunk_and_block_group(fs_info
, flags
, &start
, &nbytes
);
383 printf("Created new chunk [%llu %llu]\n", start
, nbytes
);
385 flags
= BTRFS_BLOCK_GROUP_METADATA
;
386 /* Mark all metadata block groups cached and full in free space*/
387 ret
= mark_block_groups_full(fs_info
, flags
);
391 bg
= btrfs_lookup_block_group(fs_info
, start
);
394 error("fail to look up block group %llu %llu", start
, nbytes
);
398 /* Clear block group cache just allocated */
399 ret
= modify_block_group_cache(fs_info
, bg
, 0);
407 clear_block_groups_full(fs_info
, flags
);
413 * Returns 0 means not almost full.
414 * Returns >0 means almost full.
415 * Returns <0 means fatal error.
417 static int is_chunk_almost_full(struct btrfs_fs_info
*fs_info
, u64 start
)
419 struct btrfs_path path
;
420 struct btrfs_key key
;
421 struct btrfs_root
*root
= fs_info
->extent_root
;
422 struct btrfs_block_group_item
*bi
;
423 struct btrfs_block_group_item bg_item
;
424 struct extent_buffer
*eb
;
431 key
.objectid
= start
;
432 key
.type
= BTRFS_BLOCK_GROUP_ITEM_KEY
;
433 key
.offset
= (u64
)-1;
435 btrfs_init_path(&path
);
436 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
441 ret
= btrfs_previous_item(root
, &path
, start
,
442 BTRFS_BLOCK_GROUP_ITEM_KEY
);
444 error("failed to find block group %llu", start
);
450 slot
= path
.slots
[0];
451 btrfs_item_key_to_cpu(eb
, &key
, slot
);
452 if (key
.objectid
!= start
) {
458 bi
= btrfs_item_ptr(eb
, slot
, struct btrfs_block_group_item
);
459 read_extent_buffer(eb
, &bg_item
, (unsigned long)bi
, sizeof(bg_item
));
460 used
= btrfs_block_group_used(&bg_item
);
463 * if the free space in the chunk is less than %10 of total,
464 * or not not enough for CoW once, we think the chunk is almost full.
466 min_free
= max_t(u64
, (BTRFS_MAX_LEVEL
+ 1) * fs_info
->nodesize
,
467 div_factor(total
, 1));
469 if ((total
- used
) > min_free
)
474 btrfs_release_path(&path
);
479 * Returns <0 for error.
480 * Returns 0 for success.
482 static int try_to_force_cow_in_new_chunk(struct btrfs_fs_info
*fs_info
,
483 u64 old_start
, u64
*new_start
)
488 ret
= is_chunk_almost_full(fs_info
, old_start
);
492 ret
= force_cow_in_new_chunk(fs_info
, new_start
);
496 static int avoid_extents_overwrite(struct btrfs_fs_info
*fs_info
)
499 int mixed
= btrfs_fs_incompat(fs_info
, MIXED_GROUPS
);
501 if (fs_info
->excluded_extents
)
504 if (last_allocated_chunk
!= (u64
)-1) {
505 ret
= try_to_force_cow_in_new_chunk(fs_info
,
506 last_allocated_chunk
, &last_allocated_chunk
);
510 * If failed, do not try to allocate chunk again in
512 * If there is no space left to allocate, try to exclude all
513 * metadata blocks. Mixed filesystem is unsupported.
515 last_allocated_chunk
= (u64
)-1;
516 if (ret
!= -ENOSPC
|| mixed
)
521 "Try to exclude all metadata blcoks and extents, it may be slow\n");
522 ret
= exclude_metadata_blocks(fs_info
);
525 error("failed to avoid extents overwrite %s", strerror(-ret
));
529 static int end_avoid_extents_overwrite(struct btrfs_fs_info
*fs_info
)
533 cleanup_excluded_extents(fs_info
);
534 if (last_allocated_chunk
)
535 ret
= clear_block_groups_full(fs_info
,
536 BTRFS_BLOCK_GROUP_METADATA
);
541 * Wrapper function for btrfs_fix_block_accounting().
543 * Returns 0 on success.
544 * Returns != 0 on error.
546 static int repair_block_accounting(struct btrfs_fs_info
*fs_info
)
548 struct btrfs_trans_handle
*trans
= NULL
;
549 struct btrfs_root
*root
= fs_info
->extent_root
;
552 trans
= btrfs_start_transaction(root
, 1);
554 ret
= PTR_ERR(trans
);
555 error("fail to start transaction %s", strerror(-ret
));
559 ret
= btrfs_fix_block_accounting(trans
);
560 btrfs_commit_transaction(trans
, root
);
565 * This function only handles BACKREF_MISSING,
566 * If corresponding extent item exists, increase the ref, else insert an extent
569 * Returns error bits after repair.
571 static int repair_tree_block_ref(struct btrfs_root
*root
,
572 struct extent_buffer
*node
,
573 struct node_refs
*nrefs
, int level
, int err
)
575 struct btrfs_trans_handle
*trans
= NULL
;
576 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
577 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
578 struct btrfs_path path
;
579 struct btrfs_extent_item
*ei
;
580 struct btrfs_tree_block_info
*bi
;
581 struct btrfs_key key
;
582 struct extent_buffer
*eb
;
583 u32 size
= sizeof(*ei
);
584 u32 node_size
= root
->fs_info
->nodesize
;
585 int insert_extent
= 0;
586 int skinny_metadata
= btrfs_fs_incompat(fs_info
, SKINNY_METADATA
);
587 int root_level
= btrfs_header_level(root
->node
);
592 u64 flags
= BTRFS_EXTENT_FLAG_TREE_BLOCK
;
595 if ((err
& BACKREF_MISSING
) == 0)
598 WARN_ON(level
> BTRFS_MAX_LEVEL
);
601 btrfs_init_path(&path
);
602 bytenr
= btrfs_header_bytenr(node
);
603 owner
= btrfs_header_owner(node
);
604 generation
= btrfs_header_generation(node
);
606 key
.objectid
= bytenr
;
608 key
.offset
= (u64
)-1;
610 /* Search for the extent item */
611 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, &path
, 0, 0);
617 ret
= btrfs_previous_extent_item(extent_root
, &path
, bytenr
);
621 /* calculate if the extent item flag is full backref or not */
622 if (nrefs
->full_backref
[level
] != 0)
623 flags
|= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
625 ret
= avoid_extents_overwrite(root
->fs_info
);
628 trans
= btrfs_start_transaction(extent_root
, 1);
630 ret
= PTR_ERR(trans
);
632 error("fail to start transaction %s", strerror(-ret
));
635 /* insert an extent item */
637 struct btrfs_disk_key copy_key
;
639 generation
= btrfs_header_generation(node
);
641 if (level
< root_level
&& nrefs
->full_backref
[level
+ 1] &&
642 owner
!= root
->objectid
) {
643 flags
|= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
646 key
.objectid
= bytenr
;
647 if (!skinny_metadata
) {
648 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
649 key
.offset
= node_size
;
652 key
.type
= BTRFS_METADATA_ITEM_KEY
;
656 btrfs_release_path(&path
);
657 ret
= btrfs_insert_empty_item(trans
, extent_root
, &path
, &key
,
663 ei
= btrfs_item_ptr(eb
, path
.slots
[0], struct btrfs_extent_item
);
665 btrfs_set_extent_refs(eb
, ei
, 0);
666 btrfs_set_extent_generation(eb
, ei
, generation
);
667 btrfs_set_extent_flags(eb
, ei
, flags
);
669 if (!skinny_metadata
) {
670 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
671 memset_extent_buffer(eb
, 0, (unsigned long)bi
,
673 btrfs_set_disk_key_objectid(©_key
, root
->objectid
);
674 btrfs_set_disk_key_type(©_key
, 0);
675 btrfs_set_disk_key_offset(©_key
, 0);
677 btrfs_set_tree_block_level(eb
, bi
, level
);
678 btrfs_set_tree_block_key(eb
, bi
, ©_key
);
680 btrfs_mark_buffer_dirty(eb
);
681 printf("Added an extent item [%llu %u]\n", bytenr
, node_size
);
682 btrfs_update_block_group(extent_root
, bytenr
, node_size
, 1, 0);
684 nrefs
->refs
[level
] = 0;
685 nrefs
->full_backref
[level
] =
686 flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
;
687 btrfs_release_path(&path
);
690 if (level
< root_level
&& nrefs
->full_backref
[level
+ 1] &&
691 owner
!= root
->objectid
)
692 parent
= nrefs
->bytenr
[level
+ 1];
694 /* increase the ref */
695 ret
= btrfs_inc_extent_ref(trans
, extent_root
, bytenr
, node_size
,
696 parent
, root
->objectid
, level
, 0);
698 nrefs
->refs
[level
]++;
701 btrfs_commit_transaction(trans
, extent_root
);
702 btrfs_release_path(&path
);
705 "failed to repair tree block ref start %llu root %llu due to %s",
706 bytenr
, root
->objectid
, strerror(-ret
));
708 printf("Added one tree block ref start %llu %s %llu\n",
709 bytenr
, parent
? "parent" : "root",
710 parent
? parent
: root
->objectid
);
711 err
&= ~BACKREF_MISSING
;
718 * Update global fs information.
720 static void account_bytes(struct btrfs_root
*root
, struct btrfs_path
*path
,
724 struct extent_buffer
*eb
= path
->nodes
[level
];
726 total_btree_bytes
+= eb
->len
;
727 if (fs_root_objectid(root
->objectid
))
728 total_fs_tree_bytes
+= eb
->len
;
729 if (btrfs_header_owner(eb
) == BTRFS_EXTENT_TREE_OBJECTID
)
730 total_extent_tree_bytes
+= eb
->len
;
733 btree_space_waste
+= btrfs_leaf_free_space(eb
);
735 free_nrs
= (BTRFS_NODEPTRS_PER_BLOCK(root
->fs_info
) -
736 btrfs_header_nritems(eb
));
737 btree_space_waste
+= free_nrs
* sizeof(struct btrfs_key_ptr
);
742 * Find the @index according by @ino and name.
743 * Notice:time efficiency is O(N)
745 * @root: the root of the fs/file tree
746 * @index_ret: the index as return value
747 * @namebuf: the name to match
748 * @name_len: the length of name to match
749 * @file_type: the file_type of INODE_ITEM to match
751 * Returns 0 if found and *@index_ret will be modified with right value
752 * Returns< 0 not found and *@index_ret will be (u64)-1
754 static int find_dir_index(struct btrfs_root
*root
, u64 dirid
, u64 location_id
,
755 u64
*index_ret
, char *namebuf
, u32 name_len
,
758 struct btrfs_path path
;
759 struct extent_buffer
*node
;
760 struct btrfs_dir_item
*di
;
761 struct btrfs_key key
;
762 struct btrfs_key location
;
763 char name
[BTRFS_NAME_LEN
] = {0};
775 /* search from the last index */
776 key
.objectid
= dirid
;
777 key
.offset
= (u64
)-1;
778 key
.type
= BTRFS_DIR_INDEX_KEY
;
780 btrfs_init_path(&path
);
781 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
786 ret
= btrfs_previous_item(root
, &path
, dirid
, BTRFS_DIR_INDEX_KEY
);
792 /* Check whether inode_id/filetype/name match */
793 node
= path
.nodes
[0];
794 slot
= path
.slots
[0];
795 di
= btrfs_item_ptr(node
, slot
, struct btrfs_dir_item
);
796 total
= btrfs_item_size_nr(node
, slot
);
797 while (cur
< total
) {
799 len
= btrfs_dir_name_len(node
, di
);
800 data_len
= btrfs_dir_data_len(node
, di
);
802 btrfs_dir_item_key_to_cpu(node
, di
, &location
);
803 if (location
.objectid
!= location_id
||
804 location
.type
!= BTRFS_INODE_ITEM_KEY
||
805 location
.offset
!= 0)
808 filetype
= btrfs_dir_type(node
, di
);
809 if (file_type
!= filetype
)
812 if (len
> BTRFS_NAME_LEN
)
813 len
= BTRFS_NAME_LEN
;
815 read_extent_buffer(node
, name
, (unsigned long)(di
+ 1), len
);
816 if (len
!= name_len
|| strncmp(namebuf
, name
, len
))
819 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
820 *index_ret
= key
.offset
;
824 len
+= sizeof(*di
) + data_len
;
825 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
831 btrfs_release_path(&path
);
836 * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
837 * INODE_REF/INODE_EXTREF match.
839 * @root: the root of the fs/file tree
840 * @key: the key of the DIR_ITEM/DIR_INDEX, key->offset will be right
841 * value while find index
842 * @location_key: location key of the struct btrfs_dir_item to match
843 * @name: the name to match
844 * @namelen: the length of name
845 * @file_type: the type of file to math
847 * Return 0 if no error occurred.
848 * Return DIR_ITEM_MISSING/DIR_INDEX_MISSING if couldn't find
850 * Return DIR_ITEM_MISMATCH/DIR_INDEX_MISMATCH if INODE_REF/INODE_EXTREF
851 * and DIR_ITEM/DIR_INDEX mismatch
853 static int find_dir_item(struct btrfs_root
*root
, struct btrfs_key
*key
,
854 struct btrfs_key
*location_key
, char *name
,
855 u32 namelen
, u8 file_type
)
857 struct btrfs_path path
;
858 struct extent_buffer
*node
;
859 struct btrfs_dir_item
*di
;
860 struct btrfs_key location
;
861 char namebuf
[BTRFS_NAME_LEN
] = {0};
870 /* get the index by traversing all index */
871 if (key
->type
== BTRFS_DIR_INDEX_KEY
&& key
->offset
== (u64
)-1) {
872 ret
= find_dir_index(root
, key
->objectid
,
873 location_key
->objectid
, &key
->offset
,
874 name
, namelen
, file_type
);
876 ret
= DIR_INDEX_MISSING
;
880 btrfs_init_path(&path
);
881 ret
= btrfs_search_slot(NULL
, root
, key
, &path
, 0, 0);
883 ret
= key
->type
== BTRFS_DIR_ITEM_KEY
? DIR_ITEM_MISSING
:
888 /* Check whether inode_id/filetype/name match */
889 node
= path
.nodes
[0];
890 slot
= path
.slots
[0];
891 di
= btrfs_item_ptr(node
, slot
, struct btrfs_dir_item
);
892 total
= btrfs_item_size_nr(node
, slot
);
893 while (cur
< total
) {
894 ret
= key
->type
== BTRFS_DIR_ITEM_KEY
?
895 DIR_ITEM_MISMATCH
: DIR_INDEX_MISMATCH
;
897 len
= btrfs_dir_name_len(node
, di
);
898 data_len
= btrfs_dir_data_len(node
, di
);
900 btrfs_dir_item_key_to_cpu(node
, di
, &location
);
901 if (location
.objectid
!= location_key
->objectid
||
902 location
.type
!= location_key
->type
||
903 location
.offset
!= location_key
->offset
)
906 filetype
= btrfs_dir_type(node
, di
);
907 if (file_type
!= filetype
)
910 if (len
> BTRFS_NAME_LEN
) {
911 len
= BTRFS_NAME_LEN
;
912 warning("root %llu %s[%llu %llu] name too long %u, trimmed",
914 key
->type
== BTRFS_DIR_ITEM_KEY
?
915 "DIR_ITEM" : "DIR_INDEX",
916 key
->objectid
, key
->offset
, len
);
918 read_extent_buffer(node
, namebuf
, (unsigned long)(di
+ 1),
920 if (len
!= namelen
|| strncmp(namebuf
, name
, len
))
926 len
+= sizeof(*di
) + data_len
;
927 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
932 btrfs_release_path(&path
);
937 * The ternary means dir item, dir index and relative inode ref.
938 * The function handles errs: INODE_MISSING, DIR_INDEX_MISSING
939 * DIR_INDEX_MISMATCH, DIR_ITEM_MISSING, DIR_ITEM_MISMATCH by the follow
941 * If two of three is missing or mismatched, delete the existing one.
942 * If one of three is missing or mismatched, add the missing one.
944 * returns 0 means success.
945 * returns not 0 means on error;
947 int repair_ternary_lowmem(struct btrfs_root
*root
, u64 dir_ino
, u64 ino
,
948 u64 index
, char *name
, int name_len
, u8 filetype
,
951 struct btrfs_trans_handle
*trans
;
956 * stage shall be one of following valild values:
957 * 0: Fine, nothing to do.
958 * 1: One of three is wrong, so add missing one.
959 * 2: Two of three is wrong, so delete existed one.
961 if (err
& (DIR_INDEX_MISMATCH
| DIR_INDEX_MISSING
))
963 if (err
& (DIR_ITEM_MISMATCH
| DIR_ITEM_MISSING
))
965 if (err
& (INODE_REF_MISSING
))
968 /* stage must be smllarer than 3 */
971 trans
= btrfs_start_transaction(root
, 1);
973 ret
= btrfs_unlink(trans
, root
, ino
, dir_ino
, index
, name
,
978 ret
= btrfs_unlink(trans
, root
, ino
, dir_ino
, index
, name
,
982 ret
= btrfs_add_link(trans
, root
, ino
, dir_ino
, name
, name_len
,
983 filetype
, &index
, 1, 1);
987 btrfs_commit_transaction(trans
, root
);
990 error("fail to repair inode %llu name %s filetype %u",
991 ino
, name
, filetype
);
993 printf("%s ref/dir_item of inode %llu name %s filetype %u\n",
994 stage
== 2 ? "Delete" : "Add",
995 ino
, name
, filetype
);
1001 * Prints inode ref error message
1003 static void print_inode_ref_err(struct btrfs_root
*root
, struct btrfs_key
*key
,
1004 u64 index
, const char *namebuf
, int name_len
,
1005 u8 filetype
, int err
)
1010 /* root dir error */
1011 if (key
->objectid
== BTRFS_FIRST_FREE_OBJECTID
) {
1013 "root %llu root dir shouldn't have INODE REF[%llu %llu] name %s",
1014 root
->objectid
, key
->objectid
, key
->offset
, namebuf
);
1019 if (err
& (DIR_ITEM_MISMATCH
| DIR_ITEM_MISSING
))
1020 error("root %llu DIR ITEM[%llu %llu] %s name %s filetype %u",
1021 root
->objectid
, key
->offset
,
1022 btrfs_name_hash(namebuf
, name_len
),
1023 err
& DIR_ITEM_MISMATCH
? "mismatch" : "missing",
1025 if (err
& (DIR_INDEX_MISMATCH
| DIR_INDEX_MISSING
))
1026 error("root %llu DIR INDEX[%llu %llu] %s name %s filetype %u",
1027 root
->objectid
, key
->offset
, index
,
1028 err
& DIR_ITEM_MISMATCH
? "mismatch" : "missing",
1033 * Traverse the given INODE_REF and call find_dir_item() to find related
1034 * DIR_ITEM/DIR_INDEX.
1036 * @root: the root of the fs/file tree
1037 * @ref_key: the key of the INODE_REF
1038 * @path the path provides node and slot
1039 * @refs: the count of INODE_REF
1040 * @mode: the st_mode of INODE_ITEM
1041 * @name_ret: returns with the first ref's name
1042 * @name_len_ret: len of the name_ret
1044 * Return 0 if no error occurred.
1046 static int check_inode_ref(struct btrfs_root
*root
, struct btrfs_key
*ref_key
,
1047 struct btrfs_path
*path
, char *name_ret
,
1048 u32
*namelen_ret
, u64
*refs_ret
, int mode
)
1050 struct btrfs_key key
;
1051 struct btrfs_key location
;
1052 struct btrfs_inode_ref
*ref
;
1053 struct extent_buffer
*node
;
1054 char namebuf
[BTRFS_NAME_LEN
] = {0};
1064 int need_research
= 0;
1072 /* since after repair, path and the dir item may be changed */
1073 if (need_research
) {
1075 btrfs_release_path(path
);
1076 ret
= btrfs_search_slot(NULL
, root
, ref_key
, path
, 0, 0);
1078 * The item was deleted, let the path point to the last checked
1082 if (path
->slots
[0] == 0)
1083 btrfs_prev_leaf(root
, path
);
1091 location
.objectid
= ref_key
->objectid
;
1092 location
.type
= BTRFS_INODE_ITEM_KEY
;
1093 location
.offset
= 0;
1094 node
= path
->nodes
[0];
1095 slot
= path
->slots
[0];
1097 memset(namebuf
, 0, sizeof(namebuf
) / sizeof(*namebuf
));
1098 ref
= btrfs_item_ptr(node
, slot
, struct btrfs_inode_ref
);
1099 total
= btrfs_item_size_nr(node
, slot
);
1102 /* Update inode ref count */
1105 index
= btrfs_inode_ref_index(node
, ref
);
1106 name_len
= btrfs_inode_ref_name_len(node
, ref
);
1108 if (name_len
<= BTRFS_NAME_LEN
) {
1111 len
= BTRFS_NAME_LEN
;
1112 warning("root %llu INODE_REF[%llu %llu] name too long",
1113 root
->objectid
, ref_key
->objectid
, ref_key
->offset
);
1116 read_extent_buffer(node
, namebuf
, (unsigned long)(ref
+ 1), len
);
1118 /* copy the first name found to name_ret */
1119 if (refs
== 1 && name_ret
) {
1120 memcpy(name_ret
, namebuf
, len
);
1124 /* Check root dir ref */
1125 if (ref_key
->objectid
== BTRFS_FIRST_FREE_OBJECTID
) {
1126 if (index
!= 0 || len
!= strlen("..") ||
1127 strncmp("..", namebuf
, len
) ||
1128 ref_key
->offset
!= BTRFS_FIRST_FREE_OBJECTID
) {
1129 /* set err bits then repair will delete the ref */
1130 err
|= DIR_INDEX_MISSING
;
1131 err
|= DIR_ITEM_MISSING
;
1136 /* Find related DIR_INDEX */
1137 key
.objectid
= ref_key
->offset
;
1138 key
.type
= BTRFS_DIR_INDEX_KEY
;
1140 tmp_err
|= find_dir_item(root
, &key
, &location
, namebuf
, len
,
1141 imode_to_type(mode
));
1143 /* Find related dir_item */
1144 key
.objectid
= ref_key
->offset
;
1145 key
.type
= BTRFS_DIR_ITEM_KEY
;
1146 key
.offset
= btrfs_name_hash(namebuf
, len
);
1147 tmp_err
|= find_dir_item(root
, &key
, &location
, namebuf
, len
,
1148 imode_to_type(mode
));
1150 if (tmp_err
&& repair
) {
1151 ret
= repair_ternary_lowmem(root
, ref_key
->offset
,
1152 ref_key
->objectid
, index
, namebuf
,
1153 name_len
, imode_to_type(mode
),
1160 print_inode_ref_err(root
, ref_key
, index
, namebuf
, name_len
,
1161 imode_to_type(mode
), tmp_err
);
1163 len
= sizeof(*ref
) + name_len
;
1164 ref
= (struct btrfs_inode_ref
*)((char *)ref
+ len
);
1175 * Traverse the given INODE_EXTREF and call find_dir_item() to find related
1176 * DIR_ITEM/DIR_INDEX.
1178 * @root: the root of the fs/file tree
1179 * @ref_key: the key of the INODE_EXTREF
1180 * @refs: the count of INODE_EXTREF
1181 * @mode: the st_mode of INODE_ITEM
1183 * Return 0 if no error occurred.
1185 static int check_inode_extref(struct btrfs_root
*root
,
1186 struct btrfs_key
*ref_key
,
1187 struct extent_buffer
*node
, int slot
, u64
*refs
,
1190 struct btrfs_key key
;
1191 struct btrfs_key location
;
1192 struct btrfs_inode_extref
*extref
;
1193 char namebuf
[BTRFS_NAME_LEN
] = {0};
1203 location
.objectid
= ref_key
->objectid
;
1204 location
.type
= BTRFS_INODE_ITEM_KEY
;
1205 location
.offset
= 0;
1207 extref
= btrfs_item_ptr(node
, slot
, struct btrfs_inode_extref
);
1208 total
= btrfs_item_size_nr(node
, slot
);
1211 /* update inode ref count */
1213 name_len
= btrfs_inode_extref_name_len(node
, extref
);
1214 index
= btrfs_inode_extref_index(node
, extref
);
1215 parent
= btrfs_inode_extref_parent(node
, extref
);
1216 if (name_len
<= BTRFS_NAME_LEN
) {
1219 len
= BTRFS_NAME_LEN
;
1220 warning("root %llu INODE_EXTREF[%llu %llu] name too long",
1221 root
->objectid
, ref_key
->objectid
, ref_key
->offset
);
1223 read_extent_buffer(node
, namebuf
, (unsigned long)(extref
+ 1), len
);
1225 /* Check root dir ref name */
1226 if (index
== 0 && strncmp(namebuf
, "..", name_len
)) {
1227 error("root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s",
1228 root
->objectid
, ref_key
->objectid
, ref_key
->offset
,
1230 err
|= ROOT_DIR_ERROR
;
1233 /* find related dir_index */
1234 key
.objectid
= parent
;
1235 key
.type
= BTRFS_DIR_INDEX_KEY
;
1237 ret
= find_dir_item(root
, &key
, &location
, namebuf
, len
, mode
);
1240 /* find related dir_item */
1241 key
.objectid
= parent
;
1242 key
.type
= BTRFS_DIR_ITEM_KEY
;
1243 key
.offset
= btrfs_name_hash(namebuf
, len
);
1244 ret
= find_dir_item(root
, &key
, &location
, namebuf
, len
, mode
);
1247 len
= sizeof(*extref
) + name_len
;
1248 extref
= (struct btrfs_inode_extref
*)((char *)extref
+ len
);
1258 * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified
1259 * DIR_ITEM/DIR_INDEX match.
1260 * Return with @index_ret.
1262 * @root: the root of the fs/file tree
1263 * @key: the key of the INODE_REF/INODE_EXTREF
1264 * @name: the name in the INODE_REF/INODE_EXTREF
1265 * @namelen: the length of name in the INODE_REF/INODE_EXTREF
1266 * @index_ret: the index in the INODE_REF/INODE_EXTREF,
1267 * value (64)-1 means do not check index
1269 * Return 0 if no error occurred.
1270 * Return >0 for error bitmap
1272 static int find_inode_ref(struct btrfs_root
*root
, struct btrfs_key
*key
,
1273 char *name
, int namelen
, u64
*index_ret
)
1276 struct btrfs_path path
;
1277 struct btrfs_inode_ref
*ref
;
1278 struct btrfs_inode_extref
*extref
;
1279 struct extent_buffer
*node
;
1280 char ref_namebuf
[BTRFS_NAME_LEN
] = {0};
1293 btrfs_init_path(&path
);
1294 ret
= btrfs_search_slot(NULL
, root
, key
, &path
, 0, 0);
1296 ret
= INODE_REF_MISSING
;
1300 node
= path
.nodes
[0];
1301 slot
= path
.slots
[0];
1303 ref
= btrfs_item_ptr(node
, slot
, struct btrfs_inode_ref
);
1304 total
= btrfs_item_size_nr(node
, slot
);
1306 /* Iterate all entry of INODE_REF */
1307 while (cur
< total
) {
1308 ret
= INODE_REF_MISSING
;
1310 ref_namelen
= btrfs_inode_ref_name_len(node
, ref
);
1311 ref_index
= btrfs_inode_ref_index(node
, ref
);
1312 if (*index_ret
!= (u64
)-1 && *index_ret
!= ref_index
)
1315 if (cur
+ sizeof(*ref
) + ref_namelen
> total
||
1316 ref_namelen
> BTRFS_NAME_LEN
) {
1317 warning("root %llu INODE %s[%llu %llu] name too long",
1319 key
->type
== BTRFS_INODE_REF_KEY
?
1321 key
->objectid
, key
->offset
);
1323 if (cur
+ sizeof(*ref
) > total
)
1325 len
= min_t(u32
, total
- cur
- sizeof(*ref
),
1331 read_extent_buffer(node
, ref_namebuf
, (unsigned long)(ref
+ 1),
1334 if (len
!= namelen
|| strncmp(ref_namebuf
, name
, len
))
1337 *index_ret
= ref_index
;
1341 len
= sizeof(*ref
) + ref_namelen
;
1342 ref
= (struct btrfs_inode_ref
*)((char *)ref
+ len
);
1348 /* Skip if not support EXTENDED_IREF feature */
1349 if (!btrfs_fs_incompat(root
->fs_info
, EXTENDED_IREF
))
1352 btrfs_release_path(&path
);
1353 btrfs_init_path(&path
);
1355 dir_id
= key
->offset
;
1356 key
->type
= BTRFS_INODE_EXTREF_KEY
;
1357 key
->offset
= btrfs_extref_hash(dir_id
, name
, namelen
);
1359 ret
= btrfs_search_slot(NULL
, root
, key
, &path
, 0, 0);
1361 ret
= INODE_REF_MISSING
;
1365 node
= path
.nodes
[0];
1366 slot
= path
.slots
[0];
1368 extref
= btrfs_item_ptr(node
, slot
, struct btrfs_inode_extref
);
1370 total
= btrfs_item_size_nr(node
, slot
);
1372 /* Iterate all entry of INODE_EXTREF */
1373 while (cur
< total
) {
1374 ret
= INODE_REF_MISSING
;
1376 ref_namelen
= btrfs_inode_extref_name_len(node
, extref
);
1377 ref_index
= btrfs_inode_extref_index(node
, extref
);
1378 parent
= btrfs_inode_extref_parent(node
, extref
);
1379 if (*index_ret
!= (u64
)-1 && *index_ret
!= ref_index
)
1382 if (parent
!= dir_id
)
1385 if (ref_namelen
<= BTRFS_NAME_LEN
) {
1388 len
= BTRFS_NAME_LEN
;
1389 warning("root %llu INODE %s[%llu %llu] name too long",
1391 key
->type
== BTRFS_INODE_REF_KEY
?
1393 key
->objectid
, key
->offset
);
1395 read_extent_buffer(node
, ref_namebuf
,
1396 (unsigned long)(extref
+ 1), len
);
1398 if (len
!= namelen
|| strncmp(ref_namebuf
, name
, len
))
1401 *index_ret
= ref_index
;
1406 len
= sizeof(*extref
) + ref_namelen
;
1407 extref
= (struct btrfs_inode_extref
*)((char *)extref
+ len
);
1412 btrfs_release_path(&path
);
1416 static int create_inode_item_lowmem(struct btrfs_trans_handle
*trans
,
1417 struct btrfs_root
*root
, u64 ino
,
1420 u32 mode
= (filetype
== BTRFS_FT_DIR
? S_IFDIR
: S_IFREG
) | 0755;
1422 return insert_inode_item(trans
, root
, ino
, 0, 0, 0, mode
);
1426 * Insert the missing inode item.
1428 * Returns 0 means success.
1429 * Returns <0 means error.
1431 static int repair_inode_item_missing(struct btrfs_root
*root
, u64 ino
,
1434 struct btrfs_key key
;
1435 struct btrfs_trans_handle
*trans
;
1436 struct btrfs_path path
;
1440 key
.type
= BTRFS_INODE_ITEM_KEY
;
1443 btrfs_init_path(&path
);
1444 trans
= btrfs_start_transaction(root
, 1);
1445 if (IS_ERR(trans
)) {
1450 ret
= btrfs_search_slot(trans
, root
, &key
, &path
, 1, 1);
1451 if (ret
< 0 || !ret
)
1454 /* insert inode item */
1455 create_inode_item_lowmem(trans
, root
, ino
, filetype
);
1458 btrfs_commit_transaction(trans
, root
);
1461 error("failed to repair root %llu INODE ITEM[%llu] missing",
1462 root
->objectid
, ino
);
1463 btrfs_release_path(&path
);
1468 * Call repair_inode_item_missing and repair_ternary_lowmem to repair
1470 * Returns error after repair
1472 static int repair_dir_item(struct btrfs_root
*root
, u64 dirid
, u64 ino
,
1473 u64 index
, u8 filetype
, char *namebuf
, u32 name_len
,
1478 if (err
& INODE_ITEM_MISSING
) {
1479 ret
= repair_inode_item_missing(root
, ino
, filetype
);
1481 err
&= ~(INODE_ITEM_MISMATCH
| INODE_ITEM_MISSING
);
1484 if (err
& ~(INODE_ITEM_MISMATCH
| INODE_ITEM_MISSING
)) {
1485 ret
= repair_ternary_lowmem(root
, dirid
, ino
, index
, namebuf
,
1486 name_len
, filetype
, err
);
1488 err
&= ~(DIR_INDEX_MISMATCH
| DIR_INDEX_MISSING
);
1489 err
&= ~(DIR_ITEM_MISMATCH
| DIR_ITEM_MISSING
);
1490 err
&= ~(INODE_REF_MISSING
);
1496 static void print_dir_item_err(struct btrfs_root
*root
, struct btrfs_key
*key
,
1497 u64 ino
, u64 index
, const char *namebuf
,
1498 int name_len
, u8 filetype
, int err
)
1500 if (err
& (DIR_ITEM_MISMATCH
| DIR_ITEM_MISSING
)) {
1501 error("root %llu DIR ITEM[%llu %llu] name %s filetype %d %s",
1502 root
->objectid
, key
->objectid
, key
->offset
, namebuf
,
1504 err
& DIR_ITEM_MISMATCH
? "mismath" : "missing");
1507 if (err
& (DIR_INDEX_MISMATCH
| DIR_INDEX_MISSING
)) {
1508 error("root %llu DIR INDEX[%llu %llu] name %s filetype %d %s",
1509 root
->objectid
, key
->objectid
, index
, namebuf
, filetype
,
1510 err
& DIR_ITEM_MISMATCH
? "mismath" : "missing");
1513 if (err
& (INODE_ITEM_MISSING
| INODE_ITEM_MISMATCH
)) {
1515 "root %llu INODE_ITEM[%llu] index %llu name %s filetype %d %s",
1516 root
->objectid
, ino
, index
, namebuf
, filetype
,
1517 err
& INODE_ITEM_MISMATCH
? "mismath" : "missing");
1520 if (err
& INODE_REF_MISSING
)
1522 "root %llu INODE REF[%llu, %llu] name %s filetype %u missing",
1523 root
->objectid
, ino
, key
->objectid
, namebuf
, filetype
);
1528 * Traverse the given DIR_ITEM/DIR_INDEX and check related INODE_ITEM and
1529 * call find_inode_ref() to check related INODE_REF/INODE_EXTREF.
1531 * @root: the root of the fs/file tree
1532 * @key: the key of the INODE_REF/INODE_EXTREF
1534 * @size: the st_size of the INODE_ITEM
1536 * Return 0 if no error occurred.
1537 * Return DIR_COUNT_AGAIN if the isize of the inode should be recalculated.
1539 static int check_dir_item(struct btrfs_root
*root
, struct btrfs_key
*di_key
,
1540 struct btrfs_path
*path
, u64
*size
)
1542 struct btrfs_dir_item
*di
;
1543 struct btrfs_inode_item
*ii
;
1544 struct btrfs_key key
;
1545 struct btrfs_key location
;
1546 struct extent_buffer
*node
;
1548 char namebuf
[BTRFS_NAME_LEN
] = {0};
1560 int need_research
= 0;
1566 /* since after repair, path and the dir item may be changed */
1567 if (need_research
) {
1569 err
|= DIR_COUNT_AGAIN
;
1570 btrfs_release_path(path
);
1571 ret
= btrfs_search_slot(NULL
, root
, di_key
, path
, 0, 0);
1572 /* the item was deleted, let path point the last checked item */
1574 if (path
->slots
[0] == 0)
1575 btrfs_prev_leaf(root
, path
);
1583 node
= path
->nodes
[0];
1584 slot
= path
->slots
[0];
1586 di
= btrfs_item_ptr(node
, slot
, struct btrfs_dir_item
);
1587 total
= btrfs_item_size_nr(node
, slot
);
1588 memset(namebuf
, 0, sizeof(namebuf
) / sizeof(*namebuf
));
1590 while (cur
< total
) {
1592 * For DIR_ITEM set index to (u64)-1, so that find_inode_ref
1593 * ignore index check.
1595 if (di_key
->type
== BTRFS_DIR_INDEX_KEY
)
1596 index
= di_key
->offset
;
1600 data_len
= btrfs_dir_data_len(node
, di
);
1603 error("root %llu %s[%llu %llu] data_len shouldn't be %u",
1605 di_key
->type
== BTRFS_DIR_ITEM_KEY
? "DIR_ITEM" : "DIR_INDEX",
1606 di_key
->objectid
, di_key
->offset
, data_len
);
1608 name_len
= btrfs_dir_name_len(node
, di
);
1609 if (name_len
<= BTRFS_NAME_LEN
) {
1612 len
= BTRFS_NAME_LEN
;
1613 warning("root %llu %s[%llu %llu] name too long",
1615 di_key
->type
== BTRFS_DIR_ITEM_KEY
? "DIR_ITEM" : "DIR_INDEX",
1616 di_key
->objectid
, di_key
->offset
);
1618 (*size
) += name_len
;
1619 read_extent_buffer(node
, namebuf
, (unsigned long)(di
+ 1),
1621 filetype
= btrfs_dir_type(node
, di
);
1623 if (di_key
->type
== BTRFS_DIR_ITEM_KEY
&&
1624 di_key
->offset
!= btrfs_name_hash(namebuf
, len
)) {
1626 error("root %llu DIR_ITEM[%llu %llu] name %s namelen %u filetype %u mismatch with its hash, wanted %llu have %llu",
1627 root
->objectid
, di_key
->objectid
, di_key
->offset
,
1628 namebuf
, len
, filetype
, di_key
->offset
,
1629 btrfs_name_hash(namebuf
, len
));
1632 btrfs_dir_item_key_to_cpu(node
, di
, &location
);
1633 /* Ignore related ROOT_ITEM check */
1634 if (location
.type
== BTRFS_ROOT_ITEM_KEY
)
1637 btrfs_release_path(path
);
1638 /* Check relative INODE_ITEM(existence/filetype) */
1639 ret
= btrfs_search_slot(NULL
, root
, &location
, path
, 0, 0);
1641 tmp_err
|= INODE_ITEM_MISSING
;
1645 ii
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
1646 struct btrfs_inode_item
);
1647 mode
= btrfs_inode_mode(path
->nodes
[0], ii
);
1648 if (imode_to_type(mode
) != filetype
) {
1649 tmp_err
|= INODE_ITEM_MISMATCH
;
1653 /* Check relative INODE_REF/INODE_EXTREF */
1654 key
.objectid
= location
.objectid
;
1655 key
.type
= BTRFS_INODE_REF_KEY
;
1656 key
.offset
= di_key
->objectid
;
1657 tmp_err
|= find_inode_ref(root
, &key
, namebuf
, len
, &index
);
1659 /* check relative INDEX/ITEM */
1660 key
.objectid
= di_key
->objectid
;
1661 if (key
.type
== BTRFS_DIR_ITEM_KEY
) {
1662 key
.type
= BTRFS_DIR_INDEX_KEY
;
1665 key
.type
= BTRFS_DIR_ITEM_KEY
;
1666 key
.offset
= btrfs_name_hash(namebuf
, name_len
);
1669 tmp_err
|= find_dir_item(root
, &key
, &location
, namebuf
,
1670 name_len
, filetype
);
1671 /* find_dir_item may find index */
1672 if (key
.type
== BTRFS_DIR_INDEX_KEY
)
1676 if (tmp_err
&& repair
) {
1677 ret
= repair_dir_item(root
, di_key
->objectid
,
1678 location
.objectid
, index
,
1679 imode_to_type(mode
), namebuf
,
1681 if (ret
!= tmp_err
) {
1686 btrfs_release_path(path
);
1687 print_dir_item_err(root
, di_key
, location
.objectid
, index
,
1688 namebuf
, name_len
, filetype
, tmp_err
);
1690 len
= sizeof(*di
) + name_len
+ data_len
;
1691 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
1694 if (di_key
->type
== BTRFS_DIR_INDEX_KEY
&& cur
< total
) {
1695 error("root %llu DIR_INDEX[%llu %llu] should contain only one entry",
1696 root
->objectid
, di_key
->objectid
,
1703 btrfs_release_path(path
);
1704 ret
= btrfs_search_slot(NULL
, root
, di_key
, path
, 0, 0);
1706 err
|= ret
> 0 ? -ENOENT
: ret
;
1711 * Wrapper function of btrfs_punch_hole.
1713 * Returns 0 means success.
1714 * Returns not 0 means error.
1716 static int punch_extent_hole(struct btrfs_root
*root
, u64 ino
, u64 start
,
1719 struct btrfs_trans_handle
*trans
;
1722 trans
= btrfs_start_transaction(root
, 1);
1724 return PTR_ERR(trans
);
1726 ret
= btrfs_punch_hole(trans
, root
, ino
, start
, len
);
1728 error("failed to add hole [%llu, %llu] in inode [%llu]",
1731 printf("Add a hole [%llu, %llu] in inode [%llu]\n", start
, len
,
1734 btrfs_commit_transaction(trans
, root
);
1739 * Check file extent datasum/hole, update the size of the file extents,
1740 * check and update the last offset of the file extent.
1742 * @root: the root of fs/file tree.
1743 * @fkey: the key of the file extent.
1744 * @nodatasum: INODE_NODATASUM feature.
1745 * @size: the sum of all EXTENT_DATA items size for this inode.
1746 * @end: the offset of the last extent.
1748 * Return 0 if no error occurred.
1750 static int check_file_extent(struct btrfs_root
*root
, struct btrfs_key
*fkey
,
1751 struct extent_buffer
*node
, int slot
,
1752 unsigned int nodatasum
, u64
*size
, u64
*end
)
1754 struct btrfs_file_extent_item
*fi
;
1757 u64 extent_num_bytes
;
1759 u64 csum_found
; /* In byte size, sectorsize aligned */
1760 u64 search_start
; /* Logical range start we search for csum */
1761 u64 search_len
; /* Logical range len we search for csum */
1762 u32 max_inline_extent_size
= min_t(u32
, root
->fs_info
->sectorsize
- 1,
1763 BTRFS_MAX_INLINE_DATA_SIZE(root
->fs_info
));
1764 unsigned int extent_type
;
1765 unsigned int is_hole
;
1770 fi
= btrfs_item_ptr(node
, slot
, struct btrfs_file_extent_item
);
1772 /* Check inline extent */
1773 extent_type
= btrfs_file_extent_type(node
, fi
);
1774 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
1775 struct btrfs_item
*e
= btrfs_item_nr(slot
);
1776 u32 item_inline_len
;
1778 item_inline_len
= btrfs_file_extent_inline_item_len(node
, e
);
1779 extent_num_bytes
= btrfs_file_extent_ram_bytes(node
, fi
);
1780 compressed
= btrfs_file_extent_compression(node
, fi
);
1781 if (extent_num_bytes
== 0) {
1783 "root %llu EXTENT_DATA[%llu %llu] has empty inline extent",
1784 root
->objectid
, fkey
->objectid
, fkey
->offset
);
1785 err
|= FILE_EXTENT_ERROR
;
1788 if (extent_num_bytes
> root
->fs_info
->sectorsize
) {
1790 "root %llu EXTENT_DATA[%llu %llu] too large inline extent ram size, have %llu, max: %u",
1791 root
->objectid
, fkey
->objectid
,
1792 fkey
->offset
, extent_num_bytes
,
1793 root
->fs_info
->sectorsize
- 1);
1794 err
|= FILE_EXTENT_ERROR
;
1796 if (item_inline_len
> max_inline_extent_size
) {
1798 "root %llu EXTENT_DATA[%llu %llu] too large inline extent on-disk size, have %u, max: %u",
1799 root
->objectid
, fkey
->objectid
,
1800 fkey
->offset
, item_inline_len
,
1801 max_inline_extent_size
);
1802 err
|= FILE_EXTENT_ERROR
;
1805 if (extent_num_bytes
> max_inline_extent_size
) {
1807 "root %llu EXTENT_DATA[%llu %llu] too large inline extent size, have %llu, max: %u",
1808 root
->objectid
, fkey
->objectid
, fkey
->offset
,
1809 extent_num_bytes
, max_inline_extent_size
);
1810 err
|= FILE_EXTENT_ERROR
;
1813 if (!compressed
&& extent_num_bytes
!= item_inline_len
) {
1815 "root %llu EXTENT_DATA[%llu %llu] wrong inline size, have: %llu, expected: %u",
1816 root
->objectid
, fkey
->objectid
, fkey
->offset
,
1817 extent_num_bytes
, item_inline_len
);
1818 err
|= FILE_EXTENT_ERROR
;
1820 *end
+= extent_num_bytes
;
1821 *size
+= extent_num_bytes
;
1825 /* Check extent type */
1826 if (extent_type
!= BTRFS_FILE_EXTENT_REG
&&
1827 extent_type
!= BTRFS_FILE_EXTENT_PREALLOC
) {
1828 err
|= FILE_EXTENT_ERROR
;
1829 error("root %llu EXTENT_DATA[%llu %llu] type bad",
1830 root
->objectid
, fkey
->objectid
, fkey
->offset
);
1834 /* Check REG_EXTENT/PREALLOC_EXTENT */
1835 disk_bytenr
= btrfs_file_extent_disk_bytenr(node
, fi
);
1836 disk_num_bytes
= btrfs_file_extent_disk_num_bytes(node
, fi
);
1837 extent_num_bytes
= btrfs_file_extent_num_bytes(node
, fi
);
1838 extent_offset
= btrfs_file_extent_offset(node
, fi
);
1839 compressed
= btrfs_file_extent_compression(node
, fi
);
1840 is_hole
= (disk_bytenr
== 0) && (disk_num_bytes
== 0);
1843 * Check EXTENT_DATA csum
1845 * For plain (uncompressed) extent, we should only check the range
1846 * we're referring to, as it's possible that part of prealloc extent
1847 * has been written, and has csum:
1849 * |<--- Original large preallocated extent A ---->|
1850 * |<- Prealloc File Extent ->|<- Regular Extent ->|
1853 * For compressed extent, we should check the whole range.
1856 search_start
= disk_bytenr
+ extent_offset
;
1857 search_len
= extent_num_bytes
;
1859 search_start
= disk_bytenr
;
1860 search_len
= disk_num_bytes
;
1862 ret
= count_csum_range(root
->fs_info
, search_start
, search_len
,
1864 if (csum_found
> 0 && nodatasum
) {
1865 err
|= ODD_CSUM_ITEM
;
1866 error("root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum",
1867 root
->objectid
, fkey
->objectid
, fkey
->offset
);
1868 } else if (extent_type
== BTRFS_FILE_EXTENT_REG
&& !nodatasum
&&
1869 !is_hole
&& (ret
< 0 || csum_found
< search_len
)) {
1870 err
|= CSUM_ITEM_MISSING
;
1871 error("root %llu EXTENT_DATA[%llu %llu] csum missing, have: %llu, expected: %llu",
1872 root
->objectid
, fkey
->objectid
, fkey
->offset
,
1873 csum_found
, search_len
);
1874 } else if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
&&
1876 ret
= check_prealloc_extent_written(root
->fs_info
,
1877 disk_bytenr
, disk_num_bytes
);
1881 err
|= ODD_CSUM_ITEM
;
1883 "root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have csum, but has: %llu",
1884 root
->objectid
, fkey
->objectid
, fkey
->offset
,
1889 /* Check EXTENT_DATA hole */
1890 if (!no_holes
&& *end
!= fkey
->offset
) {
1892 ret
= punch_extent_hole(root
, fkey
->objectid
,
1893 *end
, fkey
->offset
- *end
);
1894 if (!repair
|| ret
) {
1895 err
|= FILE_EXTENT_ERROR
;
1897 "root %llu EXTENT_DATA[%llu %llu] gap exists, expected: EXTENT_DATA[%llu %llu]",
1898 root
->objectid
, fkey
->objectid
, fkey
->offset
,
1899 fkey
->objectid
, *end
);
1903 *end
+= extent_num_bytes
;
1905 *size
+= extent_num_bytes
;
1910 static int __count_dir_isize(struct btrfs_root
*root
, u64 ino
, int type
,
1913 struct btrfs_key key
;
1914 struct btrfs_path path
;
1916 struct btrfs_dir_item
*di
;
1926 key
.offset
= (u64
)-1;
1928 btrfs_init_path(&path
);
1929 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
1934 /* if found, go to spacial case */
1939 ret
= btrfs_previous_item(root
, &path
, ino
, type
);
1947 di
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0], struct btrfs_dir_item
);
1949 total
= btrfs_item_size_nr(path
.nodes
[0], path
.slots
[0]);
1951 while (cur
< total
) {
1952 len
= btrfs_dir_name_len(path
.nodes
[0], di
);
1953 if (len
> BTRFS_NAME_LEN
)
1954 len
= BTRFS_NAME_LEN
;
1957 len
+= btrfs_dir_data_len(path
.nodes
[0], di
);
1959 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
1965 btrfs_release_path(&path
);
1969 static int count_dir_isize(struct btrfs_root
*root
, u64 ino
, u64
*size
)
1976 ret
= __count_dir_isize(root
, ino
, BTRFS_DIR_ITEM_KEY
, &item_size
);
1980 ret
= __count_dir_isize(root
, ino
, BTRFS_DIR_INDEX_KEY
, &index_size
);
1984 *size
= item_size
+ index_size
;
1988 error("failed to count root %llu INODE[%llu] root size",
1989 root
->objectid
, ino
);
1994 * Set inode item nbytes to @nbytes
1996 * Returns 0 on success
1997 * Returns != 0 on error
1999 static int repair_inode_nbytes_lowmem(struct btrfs_root
*root
,
2000 struct btrfs_path
*path
,
2001 u64 ino
, u64 nbytes
)
2003 struct btrfs_trans_handle
*trans
;
2004 struct btrfs_inode_item
*ii
;
2005 struct btrfs_key key
;
2006 struct btrfs_key research_key
;
2010 btrfs_item_key_to_cpu(path
->nodes
[0], &research_key
, path
->slots
[0]);
2013 key
.type
= BTRFS_INODE_ITEM_KEY
;
2016 trans
= btrfs_start_transaction(root
, 1);
2017 if (IS_ERR(trans
)) {
2018 ret
= PTR_ERR(trans
);
2023 btrfs_release_path(path
);
2024 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
2032 ii
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
2033 struct btrfs_inode_item
);
2034 btrfs_set_inode_nbytes(path
->nodes
[0], ii
, nbytes
);
2035 btrfs_mark_buffer_dirty(path
->nodes
[0]);
2037 btrfs_commit_transaction(trans
, root
);
2040 error("failed to set nbytes in inode %llu root %llu",
2041 ino
, root
->root_key
.objectid
);
2043 printf("Set nbytes in inode item %llu root %llu\n to %llu", ino
,
2044 root
->root_key
.objectid
, nbytes
);
2047 btrfs_release_path(path
);
2048 ret
= btrfs_search_slot(NULL
, root
, &research_key
, path
, 0, 0);
2055 * Set directory inode isize to @isize.
2057 * Returns 0 on success.
2058 * Returns != 0 on error.
2060 static int repair_dir_isize_lowmem(struct btrfs_root
*root
,
2061 struct btrfs_path
*path
,
2064 struct btrfs_trans_handle
*trans
;
2065 struct btrfs_inode_item
*ii
;
2066 struct btrfs_key key
;
2067 struct btrfs_key research_key
;
2071 btrfs_item_key_to_cpu(path
->nodes
[0], &research_key
, path
->slots
[0]);
2074 key
.type
= BTRFS_INODE_ITEM_KEY
;
2077 trans
= btrfs_start_transaction(root
, 1);
2078 if (IS_ERR(trans
)) {
2079 ret
= PTR_ERR(trans
);
2084 btrfs_release_path(path
);
2085 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
2093 ii
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
2094 struct btrfs_inode_item
);
2095 btrfs_set_inode_size(path
->nodes
[0], ii
, isize
);
2096 btrfs_mark_buffer_dirty(path
->nodes
[0]);
2098 btrfs_commit_transaction(trans
, root
);
2101 error("failed to set isize in inode %llu root %llu",
2102 ino
, root
->root_key
.objectid
);
2104 printf("Set isize in inode %llu root %llu to %llu\n",
2105 ino
, root
->root_key
.objectid
, isize
);
2107 btrfs_release_path(path
);
2108 ret
= btrfs_search_slot(NULL
, root
, &research_key
, path
, 0, 0);
2115 * Wrapper function for btrfs_add_orphan_item().
2117 * Returns 0 on success.
2118 * Returns != 0 on error.
2120 static int repair_inode_orphan_item_lowmem(struct btrfs_root
*root
,
2121 struct btrfs_path
*path
, u64 ino
)
2123 struct btrfs_trans_handle
*trans
;
2124 struct btrfs_key research_key
;
2128 btrfs_item_key_to_cpu(path
->nodes
[0], &research_key
, path
->slots
[0]);
2130 trans
= btrfs_start_transaction(root
, 1);
2131 if (IS_ERR(trans
)) {
2132 ret
= PTR_ERR(trans
);
2137 btrfs_release_path(path
);
2138 ret
= btrfs_add_orphan_item(trans
, root
, path
, ino
);
2140 btrfs_commit_transaction(trans
, root
);
2143 error("failed to add inode %llu as orphan item root %llu",
2144 ino
, root
->root_key
.objectid
);
2146 printf("Added inode %llu as orphan item root %llu\n",
2147 ino
, root
->root_key
.objectid
);
2149 btrfs_release_path(path
);
2150 ret
= btrfs_search_slot(NULL
, root
, &research_key
, path
, 0, 0);
2156 /* Set inode_item nlink to @ref_count.
2157 * If @ref_count == 0, move it to "lost+found" and increase @ref_count.
2159 * Returns 0 on success
2161 static int repair_inode_nlinks_lowmem(struct btrfs_root
*root
,
2162 struct btrfs_path
*path
, u64 ino
,
2163 const char *name
, u32 namelen
,
2164 u64 ref_count
, u8 filetype
, u64
*nlink
)
2166 struct btrfs_trans_handle
*trans
;
2167 struct btrfs_inode_item
*ii
;
2168 struct btrfs_key key
;
2169 struct btrfs_key old_key
;
2170 char namebuf
[BTRFS_NAME_LEN
] = {0};
2176 btrfs_item_key_to_cpu(path
->nodes
[0], &old_key
, path
->slots
[0]);
2178 if (name
&& namelen
) {
2179 ASSERT(namelen
<= BTRFS_NAME_LEN
);
2180 memcpy(namebuf
, name
, namelen
);
2183 sprintf(namebuf
, "%llu", ino
);
2184 name_len
= count_digits(ino
);
2185 printf("Can't find file name for inode %llu, use %s instead\n",
2189 trans
= btrfs_start_transaction(root
, 1);
2190 if (IS_ERR(trans
)) {
2191 ret
= PTR_ERR(trans
);
2195 btrfs_release_path(path
);
2196 /* if refs is 0, put it into lostfound */
2197 if (ref_count
== 0) {
2198 ret
= link_inode_to_lostfound(trans
, root
, path
, ino
, namebuf
,
2199 name_len
, filetype
, &ref_count
);
2204 /* reset inode_item's nlink to ref_count */
2206 key
.type
= BTRFS_INODE_ITEM_KEY
;
2209 btrfs_release_path(path
);
2210 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
2216 ii
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
2217 struct btrfs_inode_item
);
2218 btrfs_set_inode_nlink(path
->nodes
[0], ii
, ref_count
);
2219 btrfs_mark_buffer_dirty(path
->nodes
[0]);
2224 btrfs_commit_transaction(trans
, root
);
2228 "fail to repair nlink of inode %llu root %llu name %s filetype %u",
2229 root
->objectid
, ino
, namebuf
, filetype
);
2231 printf("Fixed nlink of inode %llu root %llu name %s filetype %u\n",
2232 root
->objectid
, ino
, namebuf
, filetype
);
2235 btrfs_release_path(path
);
2236 ret2
= btrfs_search_slot(NULL
, root
, &old_key
, path
, 0, 0);
2242 static bool has_orphan_item(struct btrfs_root
*root
, u64 ino
)
2244 struct btrfs_path path
;
2245 struct btrfs_key key
;
2248 btrfs_init_path(&path
);
2249 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
2250 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
2253 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
2254 btrfs_release_path(&path
);
2261 * Check INODE_ITEM and related ITEMs (the same inode number)
2262 * 1. check link count
2263 * 2. check inode ref/extref
2264 * 3. check dir item/index
2266 * Return 0 if no error occurred.
2267 * Return >0 for error or hit the traversal is done(by error bitmap)
2269 static int check_inode_item(struct btrfs_root
*root
, struct btrfs_path
*path
)
2271 struct extent_buffer
*node
;
2272 struct btrfs_inode_item
*ii
;
2273 struct btrfs_key key
;
2274 struct btrfs_key last_key
;
2284 u64 extent_size
= 0;
2286 unsigned int nodatasum
;
2287 bool is_orphan
= false;
2291 char namebuf
[BTRFS_NAME_LEN
] = {0};
2294 node
= path
->nodes
[0];
2295 slot
= path
->slots
[0];
2297 btrfs_item_key_to_cpu(node
, &key
, slot
);
2298 inode_id
= key
.objectid
;
2300 if (inode_id
== BTRFS_ORPHAN_OBJECTID
) {
2301 ret
= btrfs_next_item(root
, path
);
2307 ii
= btrfs_item_ptr(node
, slot
, struct btrfs_inode_item
);
2308 isize
= btrfs_inode_size(node
, ii
);
2309 nbytes
= btrfs_inode_nbytes(node
, ii
);
2310 mode
= btrfs_inode_mode(node
, ii
);
2311 flags
= btrfs_inode_flags(node
, ii
);
2312 dir
= imode_to_type(mode
) == BTRFS_FT_DIR
;
2313 nlink
= btrfs_inode_nlink(node
, ii
);
2314 nodatasum
= btrfs_inode_flags(node
, ii
) & BTRFS_INODE_NODATASUM
;
2316 if (S_ISLNK(mode
) &&
2317 flags
& (BTRFS_INODE_IMMUTABLE
| BTRFS_INODE_APPEND
)) {
2318 err
|= INODE_FLAGS_ERROR
;
2320 "symlinks must never have immutable/append flags set, root %llu inode item %llu flags %llu may be corrupted",
2321 root
->objectid
, inode_id
, flags
);
2325 btrfs_item_key_to_cpu(path
->nodes
[0], &last_key
, path
->slots
[0]);
2326 ret
= btrfs_next_item(root
, path
);
2328 /* out will fill 'err' rusing current statistics */
2330 } else if (ret
> 0) {
2335 node
= path
->nodes
[0];
2336 slot
= path
->slots
[0];
2337 btrfs_item_key_to_cpu(node
, &key
, slot
);
2338 if (key
.objectid
!= inode_id
)
2342 case BTRFS_INODE_REF_KEY
:
2343 ret
= check_inode_ref(root
, &key
, path
, namebuf
,
2344 &name_len
, &refs
, mode
);
2347 case BTRFS_INODE_EXTREF_KEY
:
2349 bool ext_ref
= btrfs_fs_incompat(root
->fs_info
,
2351 if (key
.type
== BTRFS_INODE_EXTREF_KEY
&& !ext_ref
)
2352 warning("root %llu EXTREF[%llu %llu] isn't supported",
2353 root
->objectid
, key
.objectid
,
2355 ret
= check_inode_extref(root
, &key
, node
, slot
, &refs
,
2360 case BTRFS_DIR_ITEM_KEY
:
2361 case BTRFS_DIR_INDEX_KEY
:
2363 warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]",
2364 root
->objectid
, inode_id
,
2365 imode_to_type(mode
), key
.objectid
,
2368 ret
= check_dir_item(root
, &key
, path
, &size
);
2371 case BTRFS_EXTENT_DATA_KEY
:
2373 warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]",
2374 root
->objectid
, inode_id
, key
.objectid
,
2377 ret
= check_file_extent(root
, &key
, node
, slot
,
2378 nodatasum
, &extent_size
,
2382 case BTRFS_XATTR_ITEM_KEY
:
2385 error("ITEM[%llu %u %llu] UNKNOWN TYPE",
2386 key
.objectid
, key
.type
, key
.offset
);
2391 if (err
& LAST_ITEM
) {
2392 btrfs_release_path(path
);
2393 ret
= btrfs_search_slot(NULL
, root
, &last_key
, path
, 0, 0);
2398 /* verify INODE_ITEM nlink/isize/nbytes */
2400 if (repair
&& (err
& DIR_COUNT_AGAIN
)) {
2401 err
&= ~DIR_COUNT_AGAIN
;
2402 count_dir_isize(root
, inode_id
, &size
);
2405 if ((nlink
!= 1 || refs
!= 1) && repair
) {
2406 ret
= repair_inode_nlinks_lowmem(root
, path
, inode_id
,
2407 namebuf
, name_len
, refs
, imode_to_type(mode
),
2412 err
|= LINK_COUNT_ERROR
;
2413 error("root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)",
2414 root
->objectid
, inode_id
, nlink
);
2418 * Just a warning, as dir inode nbytes is just an
2419 * instructive value.
2421 if (!IS_ALIGNED(nbytes
, root
->fs_info
->nodesize
)) {
2422 warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u",
2423 root
->objectid
, inode_id
,
2424 root
->fs_info
->nodesize
);
2427 if (isize
!= size
) {
2429 ret
= repair_dir_isize_lowmem(root
, path
,
2431 if (!repair
|| ret
) {
2434 "root %llu DIR INODE [%llu] size %llu not equal to %llu",
2435 root
->objectid
, inode_id
, isize
, size
);
2439 if (nlink
!= refs
) {
2441 ret
= repair_inode_nlinks_lowmem(root
, path
,
2442 inode_id
, namebuf
, name_len
, refs
,
2443 imode_to_type(mode
), &nlink
);
2444 if (!repair
|| ret
) {
2445 err
|= LINK_COUNT_ERROR
;
2447 "root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)",
2448 root
->objectid
, inode_id
, nlink
, refs
);
2450 } else if (!nlink
) {
2451 is_orphan
= has_orphan_item(root
, inode_id
);
2452 if (!is_orphan
&& repair
)
2453 ret
= repair_inode_orphan_item_lowmem(root
,
2455 if (!is_orphan
&& (!repair
|| ret
)) {
2457 error("root %llu INODE[%llu] is orphan item",
2458 root
->objectid
, inode_id
);
2462 if (!nbytes
&& !no_holes
&& extent_end
< isize
) {
2464 ret
= punch_extent_hole(root
, inode_id
,
2465 extent_end
, isize
- extent_end
);
2466 if (!repair
|| ret
) {
2467 err
|= NBYTES_ERROR
;
2469 "root %llu INODE[%llu] size %llu should have a file extent hole",
2470 root
->objectid
, inode_id
, isize
);
2474 if (nbytes
!= extent_size
) {
2476 ret
= repair_inode_nbytes_lowmem(root
, path
,
2477 inode_id
, extent_size
);
2478 if (!repair
|| ret
) {
2479 err
|= NBYTES_ERROR
;
2481 "root %llu INODE[%llu] nbytes %llu not equal to extent_size %llu",
2482 root
->objectid
, inode_id
, nbytes
,
2488 if (err
& LAST_ITEM
)
2489 btrfs_next_item(root
, path
);
2494 * Returns >0 Found error, not fatal, should continue
2495 * Returns <0 Fatal error, must exit the whole check
2496 * Returns 0 No errors found
2498 static int process_one_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
,
2499 struct node_refs
*nrefs
, int *level
)
2501 struct extent_buffer
*cur
= path
->nodes
[0];
2502 struct btrfs_key key
;
2506 int root_level
= btrfs_header_level(root
->node
);
2508 int ret
= 0; /* Final return value */
2509 int err
= 0; /* Positive error bitmap */
2511 cur_bytenr
= cur
->start
;
2513 /* skip to first inode item or the first inode number change */
2514 nritems
= btrfs_header_nritems(cur
);
2515 for (i
= 0; i
< nritems
; i
++) {
2516 btrfs_item_key_to_cpu(cur
, &key
, i
);
2518 first_ino
= key
.objectid
;
2519 if (key
.type
== BTRFS_INODE_ITEM_KEY
||
2520 (first_ino
&& first_ino
!= key
.objectid
))
2524 path
->slots
[0] = nritems
;
2530 err
|= check_inode_item(root
, path
);
2532 /* modify cur since check_inode_item may change path */
2533 cur
= path
->nodes
[0];
2535 if (err
& LAST_ITEM
)
2538 /* still have inode items in thie leaf */
2539 if (cur
->start
== cur_bytenr
)
2543 * we have switched to another leaf, above nodes may
2544 * have changed, here walk down the path, if a node
2545 * or leaf is shared, check whether we can skip this
2548 for (i
= root_level
; i
>= 0; i
--) {
2549 if (path
->nodes
[i
]->start
== nrefs
->bytenr
[i
])
2552 ret
= update_nodes_refs(root
, path
->nodes
[i
]->start
,
2553 path
->nodes
[i
], nrefs
, i
, 0);
2557 if (!nrefs
->need_check
[i
]) {
2563 for (i
= 0; i
< *level
; i
++) {
2564 free_extent_buffer(path
->nodes
[i
]);
2565 path
->nodes
[i
] = NULL
;
2575 * @level if @level == -1 means extent data item
2576 * else normal treeblocl.
2578 static int should_check_extent_strictly(struct btrfs_root
*root
,
2579 struct node_refs
*nrefs
, int level
)
2581 int root_level
= btrfs_header_level(root
->node
);
2583 if (level
> root_level
|| level
< -1)
2585 if (level
== root_level
)
2588 * if the upper node is marked full backref, it should contain shared
2589 * backref of the parent (except owner == root->objectid).
2591 while (++level
<= root_level
)
2592 if (nrefs
->refs
[level
] > 1)
2598 static int check_extent_inline_ref(struct extent_buffer
*eb
,
2599 struct btrfs_key
*key
, struct btrfs_extent_inline_ref
*iref
)
2602 u8 type
= btrfs_extent_inline_ref_type(eb
, iref
);
2605 case BTRFS_TREE_BLOCK_REF_KEY
:
2606 case BTRFS_EXTENT_DATA_REF_KEY
:
2607 case BTRFS_SHARED_BLOCK_REF_KEY
:
2608 case BTRFS_SHARED_DATA_REF_KEY
:
2612 error("extent[%llu %u %llu] has unknown ref type: %d",
2613 key
->objectid
, key
->type
, key
->offset
, type
);
2622 * Check backrefs of a tree block given by @bytenr or @eb.
2624 * @root: the root containing the @bytenr or @eb
2625 * @eb: tree block extent buffer, can be NULL
2626 * @bytenr: bytenr of the tree block to search
2627 * @level: tree level of the tree block
2628 * @owner: owner of the tree block
2630 * Return >0 for any error found and output error message
2631 * Return 0 for no error found
2633 static int check_tree_block_ref(struct btrfs_root
*root
,
2634 struct extent_buffer
*eb
, u64 bytenr
,
2635 int level
, u64 owner
, struct node_refs
*nrefs
)
2637 struct btrfs_key key
;
2638 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
2639 struct btrfs_path path
;
2640 struct btrfs_extent_item
*ei
;
2641 struct btrfs_extent_inline_ref
*iref
;
2642 struct extent_buffer
*leaf
;
2647 int root_level
= btrfs_header_level(root
->node
);
2649 u32 nodesize
= root
->fs_info
->nodesize
;
2658 btrfs_init_path(&path
);
2659 key
.objectid
= bytenr
;
2660 if (btrfs_fs_incompat(root
->fs_info
, SKINNY_METADATA
))
2661 key
.type
= BTRFS_METADATA_ITEM_KEY
;
2663 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
2664 key
.offset
= (u64
)-1;
2666 /* Search for the backref in extent tree */
2667 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, &path
, 0, 0);
2669 err
|= BACKREF_MISSING
;
2672 ret
= btrfs_previous_extent_item(extent_root
, &path
, bytenr
);
2674 err
|= BACKREF_MISSING
;
2678 leaf
= path
.nodes
[0];
2679 slot
= path
.slots
[0];
2680 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
2682 ei
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_item
);
2684 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
2685 skinny_level
= (int)key
.offset
;
2686 iref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
2688 struct btrfs_tree_block_info
*info
;
2690 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
2691 skinny_level
= btrfs_tree_block_level(leaf
, info
);
2692 iref
= (struct btrfs_extent_inline_ref
*)(info
+ 1);
2701 * Due to the feature of shared tree blocks, if the upper node
2702 * is a fs root or shared node, the extent of checked node may
2703 * not be updated until the next CoW.
2706 strict
= should_check_extent_strictly(root
, nrefs
,
2708 if (!(btrfs_extent_flags(leaf
, ei
) &
2709 BTRFS_EXTENT_FLAG_TREE_BLOCK
)) {
2711 "extent[%llu %u] backref type mismatch, missing bit: %llx",
2712 key
.objectid
, nodesize
,
2713 BTRFS_EXTENT_FLAG_TREE_BLOCK
);
2714 err
= BACKREF_MISMATCH
;
2716 header_gen
= btrfs_header_generation(eb
);
2717 extent_gen
= btrfs_extent_generation(leaf
, ei
);
2718 if (header_gen
!= extent_gen
) {
2720 "extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu",
2721 key
.objectid
, nodesize
, header_gen
,
2723 err
= BACKREF_MISMATCH
;
2725 if (level
!= skinny_level
) {
2727 "extent[%llu %u] level mismatch, wanted: %u, have: %u",
2728 key
.objectid
, nodesize
, level
, skinny_level
);
2729 err
= BACKREF_MISMATCH
;
2731 if (!is_fstree(owner
) && btrfs_extent_refs(leaf
, ei
) != 1) {
2733 "extent[%llu %u] is referred by other roots than %llu",
2734 key
.objectid
, nodesize
, root
->objectid
);
2735 err
= BACKREF_MISMATCH
;
2740 * Iterate the extent/metadata item to find the exact backref
2742 item_size
= btrfs_item_size_nr(leaf
, slot
);
2743 ptr
= (unsigned long)iref
;
2744 end
= (unsigned long)ei
+ item_size
;
2747 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
2748 type
= btrfs_extent_inline_ref_type(leaf
, iref
);
2749 offset
= btrfs_extent_inline_ref_offset(leaf
, iref
);
2751 ret
= check_extent_inline_ref(leaf
, &key
, iref
);
2756 if (type
== BTRFS_TREE_BLOCK_REF_KEY
) {
2757 if (offset
== root
->objectid
)
2759 if (!strict
&& owner
== offset
)
2761 } else if (type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
2763 * Backref of tree reloc root points to itself, no need
2764 * to check backref any more.
2766 * This may be an error of loop backref, but extent tree
2767 * checker should have already handled it.
2768 * Here we only need to avoid infinite iteration.
2770 if (offset
== bytenr
) {
2774 * Check if the backref points to valid
2777 found_ref
= !check_tree_block_ref(root
, NULL
,
2778 offset
, level
+ 1, owner
, NULL
);
2784 ptr
+= btrfs_extent_inline_ref_size(type
);
2788 * Inlined extent item doesn't have what we need, check
2789 * TREE_BLOCK_REF_KEY
2792 btrfs_release_path(&path
);
2793 key
.objectid
= bytenr
;
2794 key
.type
= BTRFS_TREE_BLOCK_REF_KEY
;
2795 key
.offset
= root
->objectid
;
2797 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, &path
, 0, 0);
2802 * Finally check SHARED BLOCK REF, any found will be good
2803 * Here we're not doing comprehensive extent backref checking,
2804 * only need to ensure there is some extent referring to this
2808 btrfs_release_path(&path
);
2809 key
.objectid
= bytenr
;
2810 key
.type
= BTRFS_SHARED_BLOCK_REF_KEY
;
2811 key
.offset
= (u64
)-1;
2813 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, &path
, 0, 0);
2815 err
|= BACKREF_MISSING
;
2818 ret
= btrfs_previous_extent_item(extent_root
, &path
, bytenr
);
2820 err
|= BACKREF_MISSING
;
2826 err
|= BACKREF_MISSING
;
2828 btrfs_release_path(&path
);
2829 if (nrefs
&& strict
&&
2830 level
< root_level
&& nrefs
->full_backref
[level
+ 1])
2831 parent
= nrefs
->bytenr
[level
+ 1];
2832 if (eb
&& (err
& BACKREF_MISSING
))
2834 "extent[%llu %u] backref lost (owner: %llu, level: %u) %s %llu",
2835 bytenr
, nodesize
, owner
, level
,
2836 parent
? "parent" : "root",
2837 parent
? parent
: root
->objectid
);
2842 * If @err contains BACKREF_MISSING then add extent of the
2843 * file_extent_data_item.
2845 * Returns error bits after reapir.
2847 static int repair_extent_data_item(struct btrfs_root
*root
,
2848 struct btrfs_path
*pathp
,
2849 struct node_refs
*nrefs
,
2852 struct btrfs_trans_handle
*trans
= NULL
;
2853 struct btrfs_file_extent_item
*fi
;
2854 struct btrfs_key fi_key
;
2855 struct btrfs_key key
;
2856 struct btrfs_extent_item
*ei
;
2857 struct btrfs_path path
;
2858 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
2859 struct extent_buffer
*eb
;
2869 int need_insert
= 0;
2872 eb
= pathp
->nodes
[0];
2873 slot
= pathp
->slots
[0];
2874 btrfs_item_key_to_cpu(eb
, &fi_key
, slot
);
2875 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
2877 if (btrfs_file_extent_type(eb
, fi
) == BTRFS_FILE_EXTENT_INLINE
||
2878 btrfs_file_extent_disk_bytenr(eb
, fi
) == 0)
2881 file_offset
= fi_key
.offset
;
2882 generation
= btrfs_file_extent_generation(eb
, fi
);
2883 disk_bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
2884 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
2885 extent_offset
= btrfs_file_extent_offset(eb
, fi
);
2886 offset
= file_offset
- extent_offset
;
2888 if (nrefs
->full_backref
[0])
2889 parent
= btrfs_header_bytenr(eb
);
2893 /* now repair only adds backref */
2894 if ((err
& BACKREF_MISSING
) == 0)
2897 /* search extent item */
2898 key
.objectid
= disk_bytenr
;
2899 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
2900 key
.offset
= num_bytes
;
2902 btrfs_init_path(&path
);
2903 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, &path
, 0, 0);
2910 ret
= avoid_extents_overwrite(root
->fs_info
);
2913 trans
= btrfs_start_transaction(root
, 1);
2914 if (IS_ERR(trans
)) {
2915 ret
= PTR_ERR(trans
);
2917 error("fail to start transaction %s", strerror(-ret
));
2920 /* insert an extent item */
2922 key
.objectid
= disk_bytenr
;
2923 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
2924 key
.offset
= num_bytes
;
2927 btrfs_release_path(&path
);
2928 ret
= btrfs_insert_empty_item(trans
, extent_root
, &path
, &key
,
2933 ei
= btrfs_item_ptr(eb
, path
.slots
[0], struct btrfs_extent_item
);
2935 btrfs_set_extent_refs(eb
, ei
, 0);
2936 btrfs_set_extent_generation(eb
, ei
, generation
);
2937 btrfs_set_extent_flags(eb
, ei
, BTRFS_EXTENT_FLAG_DATA
);
2939 btrfs_mark_buffer_dirty(eb
);
2940 ret
= btrfs_update_block_group(extent_root
, disk_bytenr
,
2942 btrfs_release_path(&path
);
2945 ret
= btrfs_inc_extent_ref(trans
, root
, disk_bytenr
, num_bytes
, parent
,
2947 parent
? BTRFS_FIRST_FREE_OBJECTID
: fi_key
.objectid
,
2951 "failed to increase extent data backref[%llu %llu] root %llu",
2952 disk_bytenr
, num_bytes
, root
->objectid
);
2955 printf("Add one extent data backref [%llu %llu]\n",
2956 disk_bytenr
, num_bytes
);
2959 err
&= ~BACKREF_MISSING
;
2962 btrfs_commit_transaction(trans
, root
);
2963 btrfs_release_path(&path
);
2965 error("can't repair root %llu extent data item[%llu %llu]",
2966 root
->objectid
, disk_bytenr
, num_bytes
);
2971 * Check EXTENT_DATA item, mainly for its dbackref in extent tree
2973 * Return >0 any error found and output error message
2974 * Return 0 for no error found
2976 static int check_extent_data_item(struct btrfs_root
*root
,
2977 struct btrfs_path
*pathp
,
2978 struct node_refs
*nrefs
, int account_bytes
)
2980 struct btrfs_file_extent_item
*fi
;
2981 struct extent_buffer
*eb
= pathp
->nodes
[0];
2982 struct btrfs_path path
;
2983 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
2984 struct btrfs_key fi_key
;
2985 struct btrfs_key dbref_key
;
2986 struct extent_buffer
*leaf
;
2987 struct btrfs_extent_item
*ei
;
2988 struct btrfs_extent_inline_ref
*iref
;
2989 struct btrfs_extent_data_ref
*dref
;
2993 u64 extent_num_bytes
;
3000 int found_dbackref
= 0;
3001 int slot
= pathp
->slots
[0];
3006 btrfs_item_key_to_cpu(eb
, &fi_key
, slot
);
3007 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
3009 /* Nothing to check for hole and inline data extents */
3010 if (btrfs_file_extent_type(eb
, fi
) == BTRFS_FILE_EXTENT_INLINE
||
3011 btrfs_file_extent_disk_bytenr(eb
, fi
) == 0)
3014 disk_bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
3015 disk_num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
3016 extent_num_bytes
= btrfs_file_extent_num_bytes(eb
, fi
);
3017 offset
= btrfs_file_extent_offset(eb
, fi
);
3019 /* Check unaligned disk_num_bytes and num_bytes */
3020 if (!IS_ALIGNED(disk_num_bytes
, root
->fs_info
->sectorsize
)) {
3022 "file extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
3023 fi_key
.objectid
, fi_key
.offset
, disk_num_bytes
,
3024 root
->fs_info
->sectorsize
);
3025 err
|= BYTES_UNALIGNED
;
3026 } else if (account_bytes
) {
3027 data_bytes_allocated
+= disk_num_bytes
;
3029 if (!IS_ALIGNED(extent_num_bytes
, root
->fs_info
->sectorsize
)) {
3031 "file extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u",
3032 fi_key
.objectid
, fi_key
.offset
, extent_num_bytes
,
3033 root
->fs_info
->sectorsize
);
3034 err
|= BYTES_UNALIGNED
;
3035 } else if (account_bytes
) {
3036 data_bytes_referenced
+= extent_num_bytes
;
3038 owner
= btrfs_header_owner(eb
);
3040 /* Check the extent item of the file extent in extent tree */
3041 btrfs_init_path(&path
);
3042 dbref_key
.objectid
= btrfs_file_extent_disk_bytenr(eb
, fi
);
3043 dbref_key
.type
= BTRFS_EXTENT_ITEM_KEY
;
3044 dbref_key
.offset
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
3046 ret
= btrfs_search_slot(NULL
, extent_root
, &dbref_key
, &path
, 0, 0);
3050 leaf
= path
.nodes
[0];
3051 slot
= path
.slots
[0];
3052 ei
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_item
);
3054 extent_flags
= btrfs_extent_flags(leaf
, ei
);
3056 if (!(extent_flags
& BTRFS_EXTENT_FLAG_DATA
)) {
3058 "file extent[%llu %llu] root %llu owner %llu backref type mismatch, wanted bit: %llx",
3059 fi_key
.objectid
, fi_key
.offset
, root
->objectid
, owner
,
3060 BTRFS_EXTENT_FLAG_DATA
);
3061 err
|= BACKREF_MISMATCH
;
3064 /* Check data backref inside that extent item */
3065 item_size
= btrfs_item_size_nr(leaf
, path
.slots
[0]);
3066 iref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
3067 ptr
= (unsigned long)iref
;
3068 end
= (unsigned long)ei
+ item_size
;
3069 strict
= should_check_extent_strictly(root
, nrefs
, -1);
3077 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
3078 type
= btrfs_extent_inline_ref_type(leaf
, iref
);
3079 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
3081 ret
= check_extent_inline_ref(leaf
, &dbref_key
, iref
);
3086 if (type
== BTRFS_EXTENT_DATA_REF_KEY
) {
3087 ref_root
= btrfs_extent_data_ref_root(leaf
, dref
);
3088 ref_objectid
= btrfs_extent_data_ref_objectid(leaf
,
3090 ref_offset
= btrfs_extent_data_ref_offset(leaf
, dref
);
3092 if (ref_objectid
== fi_key
.objectid
&&
3093 ref_offset
== fi_key
.offset
- offset
)
3095 if (ref_root
== root
->objectid
&& match
)
3097 else if (!strict
&& owner
== ref_root
&& match
)
3099 } else if (type
== BTRFS_SHARED_DATA_REF_KEY
) {
3100 found_dbackref
= !check_tree_block_ref(root
, NULL
,
3101 btrfs_extent_inline_ref_offset(leaf
, iref
),
3107 ptr
+= btrfs_extent_inline_ref_size(type
);
3110 if (!found_dbackref
) {
3111 btrfs_release_path(&path
);
3113 /* Didn't find inlined data backref, try EXTENT_DATA_REF_KEY */
3114 dbref_key
.objectid
= btrfs_file_extent_disk_bytenr(eb
, fi
);
3115 dbref_key
.type
= BTRFS_EXTENT_DATA_REF_KEY
;
3116 dbref_key
.offset
= hash_extent_data_ref(owner
, fi_key
.objectid
,
3117 fi_key
.offset
- offset
);
3119 ret
= btrfs_search_slot(NULL
, root
->fs_info
->extent_root
,
3120 &dbref_key
, &path
, 0, 0);
3126 btrfs_release_path(&path
);
3129 * Neither inlined nor EXTENT_DATA_REF found, try
3130 * SHARED_DATA_REF as last chance.
3132 dbref_key
.objectid
= disk_bytenr
;
3133 dbref_key
.type
= BTRFS_SHARED_DATA_REF_KEY
;
3134 dbref_key
.offset
= eb
->start
;
3136 ret
= btrfs_search_slot(NULL
, root
->fs_info
->extent_root
,
3137 &dbref_key
, &path
, 0, 0);
3145 if (!found_dbackref
)
3146 err
|= BACKREF_MISSING
;
3147 btrfs_release_path(&path
);
3148 if (err
& BACKREF_MISSING
) {
3150 "file extent[%llu %llu] root %llu owner %llu backref lost",
3151 fi_key
.objectid
, fi_key
.offset
, root
->objectid
, owner
);
3157 * Check a block group item with its referener (chunk) and its used space
3158 * with extent/metadata item
3160 static int check_block_group_item(struct btrfs_fs_info
*fs_info
,
3161 struct extent_buffer
*eb
, int slot
)
3163 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
3164 struct btrfs_root
*chunk_root
= fs_info
->chunk_root
;
3165 struct btrfs_block_group_item
*bi
;
3166 struct btrfs_block_group_item bg_item
;
3167 struct btrfs_path path
;
3168 struct btrfs_key bg_key
;
3169 struct btrfs_key chunk_key
;
3170 struct btrfs_key extent_key
;
3171 struct btrfs_chunk
*chunk
;
3172 struct extent_buffer
*leaf
;
3173 struct btrfs_extent_item
*ei
;
3174 u32 nodesize
= btrfs_super_nodesize(fs_info
->super_copy
);
3182 btrfs_item_key_to_cpu(eb
, &bg_key
, slot
);
3183 bi
= btrfs_item_ptr(eb
, slot
, struct btrfs_block_group_item
);
3184 read_extent_buffer(eb
, &bg_item
, (unsigned long)bi
, sizeof(bg_item
));
3185 used
= btrfs_block_group_used(&bg_item
);
3186 bg_flags
= btrfs_block_group_flags(&bg_item
);
3188 chunk_key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
3189 chunk_key
.type
= BTRFS_CHUNK_ITEM_KEY
;
3190 chunk_key
.offset
= bg_key
.objectid
;
3192 btrfs_init_path(&path
);
3193 /* Search for the referencer chunk */
3194 ret
= btrfs_search_slot(NULL
, chunk_root
, &chunk_key
, &path
, 0, 0);
3197 "block group[%llu %llu] did not find the related chunk item",
3198 bg_key
.objectid
, bg_key
.offset
);
3199 err
|= REFERENCER_MISSING
;
3201 chunk
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
3202 struct btrfs_chunk
);
3203 if (btrfs_chunk_length(path
.nodes
[0], chunk
) !=
3206 "block group[%llu %llu] related chunk item length does not match",
3207 bg_key
.objectid
, bg_key
.offset
);
3208 err
|= REFERENCER_MISMATCH
;
3211 btrfs_release_path(&path
);
3213 /* Search from the block group bytenr */
3214 extent_key
.objectid
= bg_key
.objectid
;
3215 extent_key
.type
= 0;
3216 extent_key
.offset
= 0;
3218 btrfs_init_path(&path
);
3219 ret
= btrfs_search_slot(NULL
, extent_root
, &extent_key
, &path
, 0, 0);
3223 /* Iterate extent tree to account used space */
3225 leaf
= path
.nodes
[0];
3227 /* Search slot can point to the last item beyond leaf nritems */
3228 if (path
.slots
[0] >= btrfs_header_nritems(leaf
))
3231 btrfs_item_key_to_cpu(leaf
, &extent_key
, path
.slots
[0]);
3232 if (extent_key
.objectid
>= bg_key
.objectid
+ bg_key
.offset
)
3235 if (extent_key
.type
!= BTRFS_METADATA_ITEM_KEY
&&
3236 extent_key
.type
!= BTRFS_EXTENT_ITEM_KEY
)
3238 if (extent_key
.objectid
< bg_key
.objectid
)
3241 if (extent_key
.type
== BTRFS_METADATA_ITEM_KEY
)
3244 total
+= extent_key
.offset
;
3246 ei
= btrfs_item_ptr(leaf
, path
.slots
[0],
3247 struct btrfs_extent_item
);
3248 flags
= btrfs_extent_flags(leaf
, ei
);
3249 if (flags
& BTRFS_EXTENT_FLAG_DATA
) {
3250 if (!(bg_flags
& BTRFS_BLOCK_GROUP_DATA
)) {
3252 "bad extent[%llu, %llu) type mismatch with chunk",
3253 extent_key
.objectid
,
3254 extent_key
.objectid
+ extent_key
.offset
);
3255 err
|= CHUNK_TYPE_MISMATCH
;
3257 } else if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
) {
3258 if (!(bg_flags
& (BTRFS_BLOCK_GROUP_SYSTEM
|
3259 BTRFS_BLOCK_GROUP_METADATA
))) {
3261 "bad extent[%llu, %llu) type mismatch with chunk",
3262 extent_key
.objectid
,
3263 extent_key
.objectid
+ nodesize
);
3264 err
|= CHUNK_TYPE_MISMATCH
;
3268 ret
= btrfs_next_item(extent_root
, &path
);
3274 btrfs_release_path(&path
);
3276 if (total
!= used
) {
3278 "block group[%llu %llu] used %llu but extent items used %llu",
3279 bg_key
.objectid
, bg_key
.offset
, used
, total
);
3280 err
|= BG_ACCOUNTING_ERROR
;
3286 * Get real tree block level for the case like shared block
3287 * Return >= 0 as tree level
3288 * Return <0 for error
3290 static int query_tree_block_level(struct btrfs_fs_info
*fs_info
, u64 bytenr
)
3292 struct extent_buffer
*eb
;
3293 struct btrfs_path path
;
3294 struct btrfs_key key
;
3295 struct btrfs_extent_item
*ei
;
3302 /* Search extent tree for extent generation and level */
3303 key
.objectid
= bytenr
;
3304 key
.type
= BTRFS_METADATA_ITEM_KEY
;
3305 key
.offset
= (u64
)-1;
3307 btrfs_init_path(&path
);
3308 ret
= btrfs_search_slot(NULL
, fs_info
->extent_root
, &key
, &path
, 0, 0);
3311 ret
= btrfs_previous_extent_item(fs_info
->extent_root
, &path
, bytenr
);
3319 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
3320 ei
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
3321 struct btrfs_extent_item
);
3322 flags
= btrfs_extent_flags(path
.nodes
[0], ei
);
3323 if (!(flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
)) {
3328 /* Get transid for later read_tree_block() check */
3329 transid
= btrfs_extent_generation(path
.nodes
[0], ei
);
3331 /* Get backref level as one source */
3332 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
3333 backref_level
= key
.offset
;
3335 struct btrfs_tree_block_info
*info
;
3337 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
3338 backref_level
= btrfs_tree_block_level(path
.nodes
[0], info
);
3340 btrfs_release_path(&path
);
3342 /* Get level from tree block as an alternative source */
3343 eb
= read_tree_block(fs_info
, bytenr
, transid
);
3344 if (!extent_buffer_uptodate(eb
)) {
3345 free_extent_buffer(eb
);
3348 header_level
= btrfs_header_level(eb
);
3349 free_extent_buffer(eb
);
3351 if (header_level
!= backref_level
)
3353 return header_level
;
3356 btrfs_release_path(&path
);
3361 * Check if a tree block backref is valid (points to a valid tree block)
3362 * if level == -1, level will be resolved
3363 * Return >0 for any error found and print error message
3365 static int check_tree_block_backref(struct btrfs_fs_info
*fs_info
, u64 root_id
,
3366 u64 bytenr
, int level
)
3368 struct btrfs_root
*root
;
3369 struct btrfs_key key
;
3370 struct btrfs_path path
;
3371 struct extent_buffer
*eb
;
3372 struct extent_buffer
*node
;
3373 u32 nodesize
= btrfs_super_nodesize(fs_info
->super_copy
);
3377 /* Query level for level == -1 special case */
3379 level
= query_tree_block_level(fs_info
, bytenr
);
3381 err
|= REFERENCER_MISSING
;
3385 key
.objectid
= root_id
;
3386 key
.type
= BTRFS_ROOT_ITEM_KEY
;
3387 key
.offset
= (u64
)-1;
3389 root
= btrfs_read_fs_root(fs_info
, &key
);
3391 err
|= REFERENCER_MISSING
;
3395 /* Read out the tree block to get item/node key */
3396 eb
= read_tree_block(fs_info
, bytenr
, 0);
3397 if (!extent_buffer_uptodate(eb
)) {
3398 err
|= REFERENCER_MISSING
;
3399 free_extent_buffer(eb
);
3403 /* Empty tree, no need to check key */
3404 if (!btrfs_header_nritems(eb
) && !level
) {
3405 free_extent_buffer(eb
);
3410 btrfs_node_key_to_cpu(eb
, &key
, 0);
3412 btrfs_item_key_to_cpu(eb
, &key
, 0);
3414 free_extent_buffer(eb
);
3416 btrfs_init_path(&path
);
3417 path
.lowest_level
= level
;
3418 /* Search with the first key, to ensure we can reach it */
3419 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
3421 err
|= REFERENCER_MISSING
;
3425 node
= path
.nodes
[level
];
3426 if (btrfs_header_bytenr(node
) != bytenr
) {
3428 "extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu",
3429 bytenr
, nodesize
, bytenr
,
3430 btrfs_header_bytenr(node
));
3431 err
|= REFERENCER_MISMATCH
;
3433 if (btrfs_header_level(node
) != level
) {
3435 "extent [%llu %d] referencer level mismatch, wanted: %d, have: %d",
3436 bytenr
, nodesize
, level
,
3437 btrfs_header_level(node
));
3438 err
|= REFERENCER_MISMATCH
;
3442 btrfs_release_path(&path
);
3444 if (err
& REFERENCER_MISSING
) {
3446 error("extent [%llu %d] lost referencer (owner: %llu)",
3447 bytenr
, nodesize
, root_id
);
3450 "extent [%llu %d] lost referencer (owner: %llu, level: %u)",
3451 bytenr
, nodesize
, root_id
, level
);
3458 * Check if tree block @eb is tree reloc root.
3459 * Return 0 if it's not or any problem happens
3460 * Return 1 if it's a tree reloc root
3462 static int is_tree_reloc_root(struct btrfs_fs_info
*fs_info
,
3463 struct extent_buffer
*eb
)
3465 struct btrfs_root
*tree_reloc_root
;
3466 struct btrfs_key key
;
3467 u64 bytenr
= btrfs_header_bytenr(eb
);
3468 u64 owner
= btrfs_header_owner(eb
);
3471 key
.objectid
= BTRFS_TREE_RELOC_OBJECTID
;
3473 key
.type
= BTRFS_ROOT_ITEM_KEY
;
3475 tree_reloc_root
= btrfs_read_fs_root_no_cache(fs_info
, &key
);
3476 if (IS_ERR(tree_reloc_root
))
3479 if (bytenr
== btrfs_header_bytenr(tree_reloc_root
->node
))
3481 btrfs_free_fs_root(tree_reloc_root
);
3486 * Check referencer for shared block backref
3487 * If level == -1, this function will resolve the level.
3489 static int check_shared_block_backref(struct btrfs_fs_info
*fs_info
,
3490 u64 parent
, u64 bytenr
, int level
)
3492 struct extent_buffer
*eb
;
3494 int found_parent
= 0;
3497 eb
= read_tree_block(fs_info
, parent
, 0);
3498 if (!extent_buffer_uptodate(eb
))
3502 level
= query_tree_block_level(fs_info
, bytenr
);
3506 /* It's possible it's a tree reloc root */
3507 if (parent
== bytenr
) {
3508 if (is_tree_reloc_root(fs_info
, eb
))
3513 if (level
+ 1 != btrfs_header_level(eb
))
3516 nr
= btrfs_header_nritems(eb
);
3517 for (i
= 0; i
< nr
; i
++) {
3518 if (bytenr
== btrfs_node_blockptr(eb
, i
)) {
3524 free_extent_buffer(eb
);
3525 if (!found_parent
) {
3527 "shared extent[%llu %u] lost its parent (parent: %llu, level: %u)",
3528 bytenr
, fs_info
->nodesize
, parent
, level
);
3529 return REFERENCER_MISSING
;
3535 * Check referencer for normal (inlined) data ref
3536 * If len == 0, it will be resolved by searching in extent tree
3538 static int check_extent_data_backref(struct btrfs_fs_info
*fs_info
,
3539 u64 root_id
, u64 objectid
, u64 offset
,
3540 u64 bytenr
, u64 len
, u32 count
)
3542 struct btrfs_root
*root
;
3543 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
3544 struct btrfs_key key
;
3545 struct btrfs_path path
;
3546 struct extent_buffer
*leaf
;
3547 struct btrfs_file_extent_item
*fi
;
3548 u32 found_count
= 0;
3553 key
.objectid
= bytenr
;
3554 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
3555 key
.offset
= (u64
)-1;
3557 btrfs_init_path(&path
);
3558 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, &path
, 0, 0);
3561 ret
= btrfs_previous_extent_item(extent_root
, &path
, bytenr
);
3564 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
3565 if (key
.objectid
!= bytenr
||
3566 key
.type
!= BTRFS_EXTENT_ITEM_KEY
)
3569 btrfs_release_path(&path
);
3571 key
.objectid
= root_id
;
3572 key
.type
= BTRFS_ROOT_ITEM_KEY
;
3573 key
.offset
= (u64
)-1;
3574 btrfs_init_path(&path
);
3576 root
= btrfs_read_fs_root(fs_info
, &key
);
3580 key
.objectid
= objectid
;
3581 key
.type
= BTRFS_EXTENT_DATA_KEY
;
3583 * It can be nasty as data backref offset is
3584 * file offset - file extent offset, which is smaller or
3585 * equal to original backref offset. The only special case is
3586 * overflow. So we need to special check and do further search.
3588 key
.offset
= offset
& (1ULL << 63) ? 0 : offset
;
3590 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
3595 * Search afterwards to get correct one
3596 * NOTE: As we must do a comprehensive check on the data backref to
3597 * make sure the dref count also matches, we must iterate all file
3598 * extents for that inode.
3601 leaf
= path
.nodes
[0];
3602 slot
= path
.slots
[0];
3604 if (slot
>= btrfs_header_nritems(leaf
) ||
3605 btrfs_header_owner(leaf
) != root_id
)
3607 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
3608 if (key
.objectid
!= objectid
||
3609 key
.type
!= BTRFS_EXTENT_DATA_KEY
)
3611 fi
= btrfs_item_ptr(leaf
, slot
, struct btrfs_file_extent_item
);
3613 * Except normal disk bytenr and disk num bytes, we still
3614 * need to do extra check on dbackref offset as
3615 * dbackref offset = file_offset - file_extent_offset
3617 * Also, we must check the leaf owner.
3618 * In case of shared tree blocks (snapshots) we can inherit
3619 * leaves from source snapshot.
3620 * In that case, reference from source snapshot should not
3623 if (btrfs_file_extent_disk_bytenr(leaf
, fi
) == bytenr
&&
3624 btrfs_file_extent_disk_num_bytes(leaf
, fi
) == len
&&
3625 (u64
)(key
.offset
- btrfs_file_extent_offset(leaf
, fi
)) ==
3626 offset
&& btrfs_header_owner(leaf
) == root_id
)
3630 ret
= btrfs_next_item(root
, &path
);
3635 btrfs_release_path(&path
);
3636 if (found_count
!= count
) {
3638 "extent[%llu, %llu] referencer count mismatch (root: %llu, owner: %llu, offset: %llu) wanted: %u, have: %u",
3639 bytenr
, len
, root_id
, objectid
, offset
, count
,
3641 return REFERENCER_MISSING
;
3647 * Check if the referencer of a shared data backref exists
3649 static int check_shared_data_backref(struct btrfs_fs_info
*fs_info
,
3650 u64 parent
, u64 bytenr
)
3652 struct extent_buffer
*eb
;
3653 struct btrfs_key key
;
3654 struct btrfs_file_extent_item
*fi
;
3656 int found_parent
= 0;
3659 eb
= read_tree_block(fs_info
, parent
, 0);
3660 if (!extent_buffer_uptodate(eb
))
3663 nr
= btrfs_header_nritems(eb
);
3664 for (i
= 0; i
< nr
; i
++) {
3665 btrfs_item_key_to_cpu(eb
, &key
, i
);
3666 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
3669 fi
= btrfs_item_ptr(eb
, i
, struct btrfs_file_extent_item
);
3670 if (btrfs_file_extent_type(eb
, fi
) == BTRFS_FILE_EXTENT_INLINE
)
3673 if (btrfs_file_extent_disk_bytenr(eb
, fi
) == bytenr
) {
3680 free_extent_buffer(eb
);
3681 if (!found_parent
) {
3682 error("shared extent %llu referencer lost (parent: %llu)",
3684 return REFERENCER_MISSING
;
3690 * Only delete backref if REFERENCER_MISSING now
3692 * Returns <0 the extent was deleted
3693 * Returns >0 the backref was deleted but extent still exists, returned value
3694 * means error after repair
3695 * Returns 0 nothing happened
3697 static int repair_extent_item(struct btrfs_root
*root
, struct btrfs_path
*path
,
3698 u64 bytenr
, u64 num_bytes
, u64 parent
, u64 root_objectid
,
3699 u64 owner
, u64 offset
, int err
)
3701 struct btrfs_trans_handle
*trans
;
3702 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
3703 struct btrfs_key old_key
;
3707 btrfs_item_key_to_cpu(path
->nodes
[0], &old_key
, path
->slots
[0]);
3709 if ((err
& (REFERENCER_MISSING
| REFERENCER_MISMATCH
)) == 0)
3712 ret
= avoid_extents_overwrite(root
->fs_info
);
3716 trans
= btrfs_start_transaction(extent_root
, 1);
3717 if (IS_ERR(trans
)) {
3718 ret
= PTR_ERR(trans
);
3719 error("fail to start transaction %s", strerror(-ret
));
3720 /* nothing happened */
3724 /* delete the backref */
3725 ret
= btrfs_free_extent(trans
, root
->fs_info
->fs_root
, bytenr
,
3726 num_bytes
, parent
, root_objectid
, owner
, offset
);
3729 err
&= ~REFERENCER_MISSING
;
3730 printf("Delete backref in extent [%llu %llu]\n",
3733 error("fail to delete backref in extent [%llu %llu]",
3736 btrfs_commit_transaction(trans
, extent_root
);
3738 /* btrfs_free_extent may delete the extent */
3739 btrfs_release_path(path
);
3740 ret
= btrfs_search_slot(NULL
, root
, &old_key
, path
, 0, 0);
3750 * This function will check a given extent item, including its backref and
3751 * itself (like crossing stripe boundary and type)
3753 * Since we don't use extent_record anymore, introduce new error bit
3755 static int check_extent_item(struct btrfs_fs_info
*fs_info
,
3756 struct btrfs_path
*path
)
3758 struct btrfs_extent_item
*ei
;
3759 struct btrfs_extent_inline_ref
*iref
;
3760 struct btrfs_extent_data_ref
*dref
;
3761 struct extent_buffer
*eb
= path
->nodes
[0];
3764 int slot
= path
->slots
[0];
3766 u32 nodesize
= btrfs_super_nodesize(fs_info
->super_copy
);
3767 u32 item_size
= btrfs_item_size_nr(eb
, slot
);
3777 struct btrfs_key key
;
3781 btrfs_item_key_to_cpu(eb
, &key
, slot
);
3782 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
3783 bytes_used
+= key
.offset
;
3784 num_bytes
= key
.offset
;
3786 bytes_used
+= nodesize
;
3787 num_bytes
= nodesize
;
3790 if (item_size
< sizeof(*ei
)) {
3792 * COMPAT_EXTENT_TREE_V0 case, but it's already a super
3793 * old thing when on disk format is still un-determined.
3794 * No need to care about it anymore
3796 error("unsupported COMPAT_EXTENT_TREE_V0 detected");
3800 ei
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item
);
3801 flags
= btrfs_extent_flags(eb
, ei
);
3803 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
)
3805 if (metadata
&& check_crossing_stripes(global_info
, key
.objectid
,
3807 error("bad metadata [%llu, %llu) crossing stripe boundary",
3808 key
.objectid
, key
.objectid
+ nodesize
);
3809 err
|= CROSSING_STRIPE_BOUNDARY
;
3812 ptr
= (unsigned long)(ei
+ 1);
3814 if (metadata
&& key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
3815 /* Old EXTENT_ITEM metadata */
3816 struct btrfs_tree_block_info
*info
;
3818 info
= (struct btrfs_tree_block_info
*)ptr
;
3819 level
= btrfs_tree_block_level(eb
, info
);
3820 ptr
+= sizeof(struct btrfs_tree_block_info
);
3822 /* New METADATA_ITEM */
3825 end
= (unsigned long)ei
+ item_size
;
3828 /* Reached extent item end normally */
3832 /* Beyond extent item end, wrong item size */
3834 err
|= ITEM_SIZE_MISMATCH
;
3835 error("extent item at bytenr %llu slot %d has wrong size",
3844 /* Now check every backref in this extent item */
3845 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
3846 type
= btrfs_extent_inline_ref_type(eb
, iref
);
3847 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
3849 case BTRFS_TREE_BLOCK_REF_KEY
:
3850 root_objectid
= offset
;
3852 ret
= check_tree_block_backref(fs_info
, offset
, key
.objectid
,
3856 case BTRFS_SHARED_BLOCK_REF_KEY
:
3858 ret
= check_shared_block_backref(fs_info
, offset
, key
.objectid
,
3862 case BTRFS_EXTENT_DATA_REF_KEY
:
3863 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
3864 root_objectid
= btrfs_extent_data_ref_root(eb
, dref
);
3865 owner
= btrfs_extent_data_ref_objectid(eb
, dref
);
3866 owner_offset
= btrfs_extent_data_ref_offset(eb
, dref
);
3867 ret
= check_extent_data_backref(fs_info
, root_objectid
, owner
,
3868 owner_offset
, key
.objectid
, key
.offset
,
3869 btrfs_extent_data_ref_count(eb
, dref
));
3872 case BTRFS_SHARED_DATA_REF_KEY
:
3874 ret
= check_shared_data_backref(fs_info
, offset
, key
.objectid
);
3878 error("extent[%llu %d %llu] has unknown ref type: %d",
3879 key
.objectid
, key
.type
, key
.offset
, type
);
3885 if (err
&& repair
) {
3886 ret
= repair_extent_item(fs_info
->extent_root
, path
,
3887 key
.objectid
, num_bytes
, parent
, root_objectid
,
3888 owner
, owner_offset
, ret
);
3897 ptr
+= btrfs_extent_inline_ref_size(type
);
3905 * Check if a dev extent item is referred correctly by its chunk
3907 static int check_dev_extent_item(struct btrfs_fs_info
*fs_info
,
3908 struct extent_buffer
*eb
, int slot
)
3910 struct btrfs_root
*chunk_root
= fs_info
->chunk_root
;
3911 struct btrfs_dev_extent
*ptr
;
3912 struct btrfs_path path
;
3913 struct btrfs_key chunk_key
;
3914 struct btrfs_key devext_key
;
3915 struct btrfs_chunk
*chunk
;
3916 struct extent_buffer
*l
;
3920 int found_chunk
= 0;
3923 btrfs_item_key_to_cpu(eb
, &devext_key
, slot
);
3924 ptr
= btrfs_item_ptr(eb
, slot
, struct btrfs_dev_extent
);
3925 length
= btrfs_dev_extent_length(eb
, ptr
);
3927 chunk_key
.objectid
= btrfs_dev_extent_chunk_objectid(eb
, ptr
);
3928 chunk_key
.type
= BTRFS_CHUNK_ITEM_KEY
;
3929 chunk_key
.offset
= btrfs_dev_extent_chunk_offset(eb
, ptr
);
3931 btrfs_init_path(&path
);
3932 ret
= btrfs_search_slot(NULL
, chunk_root
, &chunk_key
, &path
, 0, 0);
3937 chunk
= btrfs_item_ptr(l
, path
.slots
[0], struct btrfs_chunk
);
3938 ret
= btrfs_check_chunk_valid(fs_info
, l
, chunk
, path
.slots
[0],
3943 if (btrfs_stripe_length(fs_info
, l
, chunk
) != length
)
3946 num_stripes
= btrfs_chunk_num_stripes(l
, chunk
);
3947 for (i
= 0; i
< num_stripes
; i
++) {
3948 u64 devid
= btrfs_stripe_devid_nr(l
, chunk
, i
);
3949 u64 offset
= btrfs_stripe_offset_nr(l
, chunk
, i
);
3951 if (devid
== devext_key
.objectid
&&
3952 offset
== devext_key
.offset
) {
3958 btrfs_release_path(&path
);
3961 "device extent[%llu, %llu, %llu] did not find the related chunk",
3962 devext_key
.objectid
, devext_key
.offset
, length
);
3963 return REFERENCER_MISSING
;
3969 * Check if the used space is correct with the dev item
3971 static int check_dev_item(struct btrfs_fs_info
*fs_info
,
3972 struct extent_buffer
*eb
, int slot
)
3974 struct btrfs_root
*dev_root
= fs_info
->dev_root
;
3975 struct btrfs_dev_item
*dev_item
;
3976 struct btrfs_path path
;
3977 struct btrfs_key key
;
3978 struct btrfs_dev_extent
*ptr
;
3985 dev_item
= btrfs_item_ptr(eb
, slot
, struct btrfs_dev_item
);
3986 dev_id
= btrfs_device_id(eb
, dev_item
);
3987 used
= btrfs_device_bytes_used(eb
, dev_item
);
3988 total_bytes
= btrfs_device_total_bytes(eb
, dev_item
);
3990 key
.objectid
= dev_id
;
3991 key
.type
= BTRFS_DEV_EXTENT_KEY
;
3994 btrfs_init_path(&path
);
3995 ret
= btrfs_search_slot(NULL
, dev_root
, &key
, &path
, 0, 0);
3997 btrfs_item_key_to_cpu(eb
, &key
, slot
);
3998 error("cannot find any related dev extent for dev[%llu, %u, %llu]",
3999 key
.objectid
, key
.type
, key
.offset
);
4000 btrfs_release_path(&path
);
4001 return REFERENCER_MISSING
;
4004 /* Iterate dev_extents to calculate the used space of a device */
4006 if (path
.slots
[0] >= btrfs_header_nritems(path
.nodes
[0]))
4009 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
4010 if (key
.objectid
> dev_id
)
4012 if (key
.type
!= BTRFS_DEV_EXTENT_KEY
|| key
.objectid
!= dev_id
)
4015 ptr
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
4016 struct btrfs_dev_extent
);
4017 total
+= btrfs_dev_extent_length(path
.nodes
[0], ptr
);
4019 ret
= btrfs_next_item(dev_root
, &path
);
4023 btrfs_release_path(&path
);
4025 if (used
!= total
) {
4026 btrfs_item_key_to_cpu(eb
, &key
, slot
);
4028 "Dev extent's total-byte %llu is not equal to bytes-used %llu in dev[%llu, %u, %llu]",
4029 total
, used
, BTRFS_ROOT_TREE_OBJECTID
,
4030 BTRFS_DEV_EXTENT_KEY
, dev_id
);
4031 return ACCOUNTING_MISMATCH
;
4033 check_dev_size_alignment(dev_id
, total_bytes
, fs_info
->sectorsize
);
4039 * Check a chunk item.
4040 * Including checking all referred dev_extents and block group
4042 static int check_chunk_item(struct btrfs_fs_info
*fs_info
,
4043 struct extent_buffer
*eb
, int slot
)
4045 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
4046 struct btrfs_root
*dev_root
= fs_info
->dev_root
;
4047 struct btrfs_path path
;
4048 struct btrfs_key chunk_key
;
4049 struct btrfs_key bg_key
;
4050 struct btrfs_key devext_key
;
4051 struct btrfs_chunk
*chunk
;
4052 struct extent_buffer
*leaf
;
4053 struct btrfs_block_group_item
*bi
;
4054 struct btrfs_block_group_item bg_item
;
4055 struct btrfs_dev_extent
*ptr
;
4067 btrfs_item_key_to_cpu(eb
, &chunk_key
, slot
);
4068 chunk
= btrfs_item_ptr(eb
, slot
, struct btrfs_chunk
);
4069 length
= btrfs_chunk_length(eb
, chunk
);
4070 chunk_end
= chunk_key
.offset
+ length
;
4071 ret
= btrfs_check_chunk_valid(fs_info
, eb
, chunk
, slot
,
4074 error("chunk[%llu %llu) is invalid", chunk_key
.offset
,
4076 err
|= BYTES_UNALIGNED
| UNKNOWN_TYPE
;
4079 type
= btrfs_chunk_type(eb
, chunk
);
4081 bg_key
.objectid
= chunk_key
.offset
;
4082 bg_key
.type
= BTRFS_BLOCK_GROUP_ITEM_KEY
;
4083 bg_key
.offset
= length
;
4085 btrfs_init_path(&path
);
4086 ret
= btrfs_search_slot(NULL
, extent_root
, &bg_key
, &path
, 0, 0);
4089 "chunk[%llu %llu) did not find the related block group item",
4090 chunk_key
.offset
, chunk_end
);
4091 err
|= REFERENCER_MISSING
;
4093 leaf
= path
.nodes
[0];
4094 bi
= btrfs_item_ptr(leaf
, path
.slots
[0],
4095 struct btrfs_block_group_item
);
4096 read_extent_buffer(leaf
, &bg_item
, (unsigned long)bi
,
4098 if (btrfs_block_group_flags(&bg_item
) != type
) {
4100 "chunk[%llu %llu) related block group item flags mismatch, wanted: %llu, have: %llu",
4101 chunk_key
.offset
, chunk_end
, type
,
4102 btrfs_block_group_flags(&bg_item
));
4103 err
|= REFERENCER_MISSING
;
4107 num_stripes
= btrfs_chunk_num_stripes(eb
, chunk
);
4108 stripe_len
= btrfs_stripe_length(fs_info
, eb
, chunk
);
4109 for (i
= 0; i
< num_stripes
; i
++) {
4110 btrfs_release_path(&path
);
4111 btrfs_init_path(&path
);
4112 devext_key
.objectid
= btrfs_stripe_devid_nr(eb
, chunk
, i
);
4113 devext_key
.type
= BTRFS_DEV_EXTENT_KEY
;
4114 devext_key
.offset
= btrfs_stripe_offset_nr(eb
, chunk
, i
);
4116 ret
= btrfs_search_slot(NULL
, dev_root
, &devext_key
, &path
,
4121 leaf
= path
.nodes
[0];
4122 ptr
= btrfs_item_ptr(leaf
, path
.slots
[0],
4123 struct btrfs_dev_extent
);
4124 objectid
= btrfs_dev_extent_chunk_objectid(leaf
, ptr
);
4125 offset
= btrfs_dev_extent_chunk_offset(leaf
, ptr
);
4126 if (objectid
!= chunk_key
.objectid
||
4127 offset
!= chunk_key
.offset
||
4128 btrfs_dev_extent_length(leaf
, ptr
) != stripe_len
)
4132 err
|= BACKREF_MISSING
;
4134 "chunk[%llu %llu) stripe %d did not find the related dev extent",
4135 chunk_key
.objectid
, chunk_end
, i
);
4138 btrfs_release_path(&path
);
4144 * Add block group item to the extent tree if @err contains REFERENCER_MISSING.
4145 * FIXME: We still need to repair error of dev_item.
4147 * Returns error after repair.
4149 static int repair_chunk_item(struct btrfs_root
*chunk_root
,
4150 struct btrfs_path
*path
, int err
)
4152 struct btrfs_chunk
*chunk
;
4153 struct btrfs_key chunk_key
;
4154 struct extent_buffer
*eb
= path
->nodes
[0];
4155 struct btrfs_root
*extent_root
= chunk_root
->fs_info
->extent_root
;
4156 struct btrfs_trans_handle
*trans
;
4158 int slot
= path
->slots
[0];
4162 btrfs_item_key_to_cpu(eb
, &chunk_key
, slot
);
4163 if (chunk_key
.type
!= BTRFS_CHUNK_ITEM_KEY
)
4165 chunk
= btrfs_item_ptr(eb
, slot
, struct btrfs_chunk
);
4166 type
= btrfs_chunk_type(path
->nodes
[0], chunk
);
4167 length
= btrfs_chunk_length(eb
, chunk
);
4169 /* now repair only adds block group */
4170 if ((err
& REFERENCER_MISSING
) == 0)
4173 ret
= avoid_extents_overwrite(chunk_root
->fs_info
);
4177 trans
= btrfs_start_transaction(extent_root
, 1);
4178 if (IS_ERR(trans
)) {
4179 ret
= PTR_ERR(trans
);
4180 error("fail to start transaction %s", strerror(-ret
));
4184 ret
= btrfs_make_block_group(trans
, chunk_root
->fs_info
, 0, type
,
4185 chunk_key
.offset
, length
);
4187 error("fail to add block group item [%llu %llu]",
4188 chunk_key
.offset
, length
);
4190 err
&= ~REFERENCER_MISSING
;
4191 printf("Added block group item[%llu %llu]\n", chunk_key
.offset
,
4195 btrfs_commit_transaction(trans
, extent_root
);
4197 error("fail to repair item(s) related to chunk item [%llu %llu]",
4198 chunk_key
.objectid
, chunk_key
.offset
);
4202 static int delete_extent_tree_item(struct btrfs_root
*root
,
4203 struct btrfs_path
*path
)
4205 struct btrfs_key key
;
4206 struct btrfs_trans_handle
*trans
;
4209 ret
= avoid_extents_overwrite(root
->fs_info
);
4212 trans
= btrfs_start_transaction(root
, 1);
4213 if (IS_ERR(trans
)) {
4214 ret
= PTR_ERR(trans
);
4215 error("fail to start transaction %s", strerror(-ret
));
4218 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
4219 btrfs_release_path(path
);
4220 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
4226 ret
= btrfs_del_item(trans
, root
, path
);
4230 if (path
->slots
[0] == 0)
4231 btrfs_prev_leaf(root
, path
);
4235 btrfs_commit_transaction(trans
, root
);
4237 error("failed to delete root %llu item[%llu, %u, %llu]",
4238 root
->objectid
, key
.objectid
, key
.type
, key
.offset
);
4240 printf("Deleted root %llu item[%llu, %u, %llu]\n",
4241 root
->objectid
, key
.objectid
, key
.type
, key
.offset
);
4246 * Main entry function to check known items and update related accounting info
4248 static int check_leaf_items(struct btrfs_root
*root
, struct btrfs_path
*path
,
4249 struct node_refs
*nrefs
, int account_bytes
)
4251 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4252 struct btrfs_key key
;
4253 struct extent_buffer
*eb
;
4256 struct btrfs_extent_data_ref
*dref
;
4261 eb
= path
->nodes
[0];
4262 slot
= path
->slots
[0];
4263 if (slot
>= btrfs_header_nritems(eb
)) {
4265 error("empty leaf [%llu %u] root %llu", eb
->start
,
4266 root
->fs_info
->nodesize
, root
->objectid
);
4272 btrfs_item_key_to_cpu(eb
, &key
, slot
);
4276 case BTRFS_EXTENT_DATA_KEY
:
4277 ret
= check_extent_data_item(root
, path
, nrefs
, account_bytes
);
4279 ret
= repair_extent_data_item(root
, path
, nrefs
, ret
);
4282 case BTRFS_BLOCK_GROUP_ITEM_KEY
:
4283 ret
= check_block_group_item(fs_info
, eb
, slot
);
4285 ret
& REFERENCER_MISSING
)
4286 ret
= delete_extent_tree_item(root
, path
);
4289 case BTRFS_DEV_ITEM_KEY
:
4290 ret
= check_dev_item(fs_info
, eb
, slot
);
4293 case BTRFS_CHUNK_ITEM_KEY
:
4294 ret
= check_chunk_item(fs_info
, eb
, slot
);
4296 ret
= repair_chunk_item(root
, path
, ret
);
4299 case BTRFS_DEV_EXTENT_KEY
:
4300 ret
= check_dev_extent_item(fs_info
, eb
, slot
);
4303 case BTRFS_EXTENT_ITEM_KEY
:
4304 case BTRFS_METADATA_ITEM_KEY
:
4305 ret
= check_extent_item(fs_info
, path
);
4308 case BTRFS_EXTENT_CSUM_KEY
:
4309 total_csum_bytes
+= btrfs_item_size_nr(eb
, slot
);
4312 case BTRFS_TREE_BLOCK_REF_KEY
:
4313 ret
= check_tree_block_backref(fs_info
, key
.offset
,
4316 ret
& (REFERENCER_MISMATCH
| REFERENCER_MISSING
))
4317 ret
= delete_extent_tree_item(root
, path
);
4320 case BTRFS_EXTENT_DATA_REF_KEY
:
4321 dref
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_data_ref
);
4322 ret
= check_extent_data_backref(fs_info
,
4323 btrfs_extent_data_ref_root(eb
, dref
),
4324 btrfs_extent_data_ref_objectid(eb
, dref
),
4325 btrfs_extent_data_ref_offset(eb
, dref
),
4327 btrfs_extent_data_ref_count(eb
, dref
));
4329 ret
& (REFERENCER_MISMATCH
| REFERENCER_MISSING
))
4330 ret
= delete_extent_tree_item(root
, path
);
4333 case BTRFS_SHARED_BLOCK_REF_KEY
:
4334 ret
= check_shared_block_backref(fs_info
, key
.offset
,
4337 ret
& (REFERENCER_MISMATCH
| REFERENCER_MISSING
))
4338 ret
= delete_extent_tree_item(root
, path
);
4341 case BTRFS_SHARED_DATA_REF_KEY
:
4342 ret
= check_shared_data_backref(fs_info
, key
.offset
,
4345 ret
& (REFERENCER_MISMATCH
| REFERENCER_MISSING
))
4346 ret
= delete_extent_tree_item(root
, path
);
4360 * @trans just for lowmem repair mode
4361 * @check all if not 0 then check all tree block backrefs and items
4362 * 0 then just check relationship of items in fs tree(s)
4364 * Returns >0 Found error, should continue
4365 * Returns <0 Fatal error, must exit the whole check
4366 * Returns 0 No errors found
4368 static int walk_down_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
4369 int *level
, struct node_refs
*nrefs
, int check_all
)
4371 enum btrfs_tree_block_status status
;
4374 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4375 struct extent_buffer
*next
;
4376 struct extent_buffer
*cur
;
4380 int account_file_data
= 0;
4382 WARN_ON(*level
< 0);
4383 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
4385 ret
= update_nodes_refs(root
, btrfs_header_bytenr(path
->nodes
[*level
]),
4386 path
->nodes
[*level
], nrefs
, *level
, check_all
);
4390 while (*level
>= 0) {
4391 WARN_ON(*level
< 0);
4392 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
4393 cur
= path
->nodes
[*level
];
4394 bytenr
= btrfs_header_bytenr(cur
);
4395 check
= nrefs
->need_check
[*level
];
4397 if (btrfs_header_level(cur
) != *level
)
4400 * Update bytes accounting and check tree block ref
4401 * NOTE: Doing accounting and check before checking nritems
4402 * is necessary because of empty node/leaf.
4404 if ((check_all
&& !nrefs
->checked
[*level
]) ||
4405 (!check_all
&& nrefs
->need_check
[*level
])) {
4406 ret
= check_tree_block_ref(root
, cur
,
4407 btrfs_header_bytenr(cur
), btrfs_header_level(cur
),
4408 btrfs_header_owner(cur
), nrefs
);
4411 ret
= repair_tree_block_ref(root
,
4412 path
->nodes
[*level
], nrefs
, *level
, ret
);
4415 if (check_all
&& nrefs
->need_check
[*level
] &&
4416 nrefs
->refs
[*level
]) {
4417 account_bytes(root
, path
, *level
);
4418 account_file_data
= 1;
4420 nrefs
->checked
[*level
] = 1;
4423 if (path
->slots
[*level
] >= btrfs_header_nritems(cur
))
4426 /* Don't forgot to check leaf/node validation */
4428 /* skip duplicate check */
4429 if (check
|| !check_all
) {
4430 ret
= btrfs_check_leaf(root
, NULL
, cur
);
4431 if (ret
!= BTRFS_TREE_BLOCK_CLEAN
) {
4439 ret
= process_one_leaf(root
, path
, nrefs
, level
);
4441 ret
= check_leaf_items(root
, path
,
4442 nrefs
, account_file_data
);
4446 if (check
|| !check_all
) {
4447 ret
= btrfs_check_node(root
, NULL
, cur
);
4448 if (ret
!= BTRFS_TREE_BLOCK_CLEAN
) {
4454 bytenr
= btrfs_node_blockptr(cur
, path
->slots
[*level
]);
4455 ptr_gen
= btrfs_node_ptr_generation(cur
, path
->slots
[*level
]);
4457 ret
= update_nodes_refs(root
, bytenr
, NULL
, nrefs
, *level
- 1,
4462 * check all trees in check_chunks_and_extent
4463 * check shared node once in check_fs_roots
4465 if (!check_all
&& !nrefs
->need_check
[*level
- 1]) {
4466 path
->slots
[*level
]++;
4470 next
= btrfs_find_tree_block(fs_info
, bytenr
, fs_info
->nodesize
);
4471 if (!next
|| !btrfs_buffer_uptodate(next
, ptr_gen
)) {
4472 free_extent_buffer(next
);
4473 reada_walk_down(root
, cur
, path
->slots
[*level
]);
4474 next
= read_tree_block(fs_info
, bytenr
, ptr_gen
);
4475 if (!extent_buffer_uptodate(next
)) {
4476 struct btrfs_key node_key
;
4478 btrfs_node_key_to_cpu(path
->nodes
[*level
],
4480 path
->slots
[*level
]);
4481 btrfs_add_corrupt_extent_record(fs_info
,
4482 &node_key
, path
->nodes
[*level
]->start
,
4483 fs_info
->nodesize
, *level
);
4489 ret
= check_child_node(cur
, path
->slots
[*level
], next
);
4494 if (btrfs_is_leaf(next
))
4495 status
= btrfs_check_leaf(root
, NULL
, next
);
4497 status
= btrfs_check_node(root
, NULL
, next
);
4498 if (status
!= BTRFS_TREE_BLOCK_CLEAN
) {
4499 free_extent_buffer(next
);
4504 *level
= *level
- 1;
4505 free_extent_buffer(path
->nodes
[*level
]);
4506 path
->nodes
[*level
] = next
;
4507 path
->slots
[*level
] = 0;
4508 account_file_data
= 0;
4510 update_nodes_refs(root
, (u64
)-1, next
, nrefs
, *level
, check_all
);
4515 static int walk_up_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
4519 struct extent_buffer
*leaf
;
4521 for (i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
4522 leaf
= path
->nodes
[i
];
4523 if (path
->slots
[i
] + 1 < btrfs_header_nritems(leaf
)) {
4528 free_extent_buffer(path
->nodes
[*level
]);
4529 path
->nodes
[*level
] = NULL
;
4536 * Insert the missing inode item and inode ref.
4538 * Normal INODE_ITEM_MISSING and INODE_REF_MISSING are handled in backref * dir.
4539 * Root dir should be handled specially because root dir is the root of fs.
4541 * returns err (>0 or 0) after repair
4543 static int repair_fs_first_inode(struct btrfs_root
*root
, int err
)
4545 struct btrfs_trans_handle
*trans
;
4546 struct btrfs_key key
;
4547 struct btrfs_path path
;
4548 int filetype
= BTRFS_FT_DIR
;
4551 btrfs_init_path(&path
);
4553 if (err
& INODE_REF_MISSING
) {
4554 key
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
4555 key
.type
= BTRFS_INODE_REF_KEY
;
4556 key
.offset
= BTRFS_FIRST_FREE_OBJECTID
;
4558 trans
= btrfs_start_transaction(root
, 1);
4559 if (IS_ERR(trans
)) {
4560 ret
= PTR_ERR(trans
);
4564 btrfs_release_path(&path
);
4565 ret
= btrfs_search_slot(trans
, root
, &key
, &path
, 1, 1);
4569 ret
= btrfs_insert_inode_ref(trans
, root
, "..", 2,
4570 BTRFS_FIRST_FREE_OBJECTID
,
4571 BTRFS_FIRST_FREE_OBJECTID
, 0);
4575 printf("Add INODE_REF[%llu %llu] name %s\n",
4576 BTRFS_FIRST_FREE_OBJECTID
, BTRFS_FIRST_FREE_OBJECTID
,
4578 err
&= ~INODE_REF_MISSING
;
4581 error("fail to insert first inode's ref");
4582 btrfs_commit_transaction(trans
, root
);
4585 if (err
& INODE_ITEM_MISSING
) {
4586 ret
= repair_inode_item_missing(root
,
4587 BTRFS_FIRST_FREE_OBJECTID
, filetype
);
4590 err
&= ~INODE_ITEM_MISSING
;
4594 error("fail to repair first inode");
4595 btrfs_release_path(&path
);
4600 * check first root dir's inode_item and inode_ref
4602 * returns 0 means no error
4603 * returns >0 means error
4604 * returns <0 means fatal error
4606 static int check_fs_first_inode(struct btrfs_root
*root
)
4608 struct btrfs_path path
;
4609 struct btrfs_key key
;
4610 struct btrfs_inode_item
*ii
;
4616 key
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
4617 key
.type
= BTRFS_INODE_ITEM_KEY
;
4620 /* For root being dropped, we don't need to check first inode */
4621 if (btrfs_root_refs(&root
->root_item
) == 0 &&
4622 btrfs_disk_key_objectid(&root
->root_item
.drop_progress
) >=
4623 BTRFS_FIRST_FREE_OBJECTID
)
4626 btrfs_init_path(&path
);
4627 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
4632 err
|= INODE_ITEM_MISSING
;
4634 ii
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
4635 struct btrfs_inode_item
);
4636 mode
= btrfs_inode_mode(path
.nodes
[0], ii
);
4637 if (imode_to_type(mode
) != BTRFS_FT_DIR
)
4638 err
|= INODE_ITEM_MISMATCH
;
4641 /* lookup first inode ref */
4642 key
.offset
= BTRFS_FIRST_FREE_OBJECTID
;
4643 key
.type
= BTRFS_INODE_REF_KEY
;
4644 /* special index value */
4647 ret
= find_inode_ref(root
, &key
, "..", strlen(".."), &index
);
4653 btrfs_release_path(&path
);
4656 err
= repair_fs_first_inode(root
, err
);
4658 if (err
& (INODE_ITEM_MISSING
| INODE_ITEM_MISMATCH
))
4659 error("root dir INODE_ITEM is %s",
4660 err
& INODE_ITEM_MISMATCH
? "mismatch" : "missing");
4661 if (err
& INODE_REF_MISSING
)
4662 error("root dir INODE_REF is missing");
4664 return ret
< 0 ? ret
: err
;
4668 * This function calls walk_down_tree and walk_up_tree to check tree
4669 * blocks and integrity of fs tree items.
4671 * @root: the root of the tree to be checked.
4672 * @account if NOT 0 means check the tree (including tree)'s treeblocks.
4673 * otherwise means check fs tree(s) items relationship and
4674 * @root MUST be a fs tree root.
4675 * Returns 0 represents OK.
4676 * Returns >0 represents error bits.
4678 static int check_btrfs_root(struct btrfs_root
*root
, int check_all
)
4680 struct btrfs_path path
;
4681 struct node_refs nrefs
;
4682 struct btrfs_root_item
*root_item
= &root
->root_item
;
4687 memset(&nrefs
, 0, sizeof(nrefs
));
4690 * We need to manually check the first inode item (256)
4691 * As the following traversal function will only start from
4692 * the first inode item in the leaf, if inode item (256) is
4693 * missing we will skip it forever.
4695 ret
= check_fs_first_inode(root
);
4701 level
= btrfs_header_level(root
->node
);
4702 btrfs_init_path(&path
);
4704 if (btrfs_root_refs(root_item
) > 0 ||
4705 btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
4706 path
.nodes
[level
] = root
->node
;
4707 path
.slots
[level
] = 0;
4708 extent_buffer_get(root
->node
);
4710 struct btrfs_key key
;
4712 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
4713 level
= root_item
->drop_level
;
4714 path
.lowest_level
= level
;
4715 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
4722 ret
= walk_down_tree(root
, &path
, &level
, &nrefs
, check_all
);
4726 /* if ret is negative, walk shall stop */
4728 ret
= err
| FATAL_ERROR
;
4732 ret
= walk_up_tree(root
, &path
, &level
);
4734 /* Normal exit, reset ret to err */
4741 btrfs_release_path(&path
);
4746 * Iterate all items in the tree and call check_inode_item() to check.
4748 * @root: the root of the tree to be checked.
4750 * Return 0 if no error found.
4751 * Return <0 for error.
4753 static int check_fs_root(struct btrfs_root
*root
)
4755 reset_cached_block_groups(root
->fs_info
);
4756 return check_btrfs_root(root
, 0);
4760 * Find the relative ref for root_ref and root_backref.
4762 * @root: the root of the root tree.
4763 * @ref_key: the key of the root ref.
4765 * Return 0 if no error occurred.
4767 static int check_root_ref(struct btrfs_root
*root
, struct btrfs_key
*ref_key
,
4768 struct extent_buffer
*node
, int slot
)
4770 struct btrfs_path path
;
4771 struct btrfs_key key
;
4772 struct btrfs_root_ref
*ref
;
4773 struct btrfs_root_ref
*backref
;
4774 char ref_name
[BTRFS_NAME_LEN
] = {0};
4775 char backref_name
[BTRFS_NAME_LEN
] = {0};
4781 u32 backref_namelen
;
4786 ref
= btrfs_item_ptr(node
, slot
, struct btrfs_root_ref
);
4787 ref_dirid
= btrfs_root_ref_dirid(node
, ref
);
4788 ref_seq
= btrfs_root_ref_sequence(node
, ref
);
4789 ref_namelen
= btrfs_root_ref_name_len(node
, ref
);
4791 if (ref_namelen
<= BTRFS_NAME_LEN
) {
4794 len
= BTRFS_NAME_LEN
;
4795 warning("%s[%llu %llu] ref_name too long",
4796 ref_key
->type
== BTRFS_ROOT_REF_KEY
?
4797 "ROOT_REF" : "ROOT_BACKREF", ref_key
->objectid
,
4800 read_extent_buffer(node
, ref_name
, (unsigned long)(ref
+ 1), len
);
4802 /* Find relative root_ref */
4803 key
.objectid
= ref_key
->offset
;
4804 key
.type
= BTRFS_ROOT_BACKREF_KEY
+ BTRFS_ROOT_REF_KEY
- ref_key
->type
;
4805 key
.offset
= ref_key
->objectid
;
4807 btrfs_init_path(&path
);
4808 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
4810 err
|= ROOT_REF_MISSING
;
4811 error("%s[%llu %llu] couldn't find relative ref",
4812 ref_key
->type
== BTRFS_ROOT_REF_KEY
?
4813 "ROOT_REF" : "ROOT_BACKREF",
4814 ref_key
->objectid
, ref_key
->offset
);
4818 backref
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
4819 struct btrfs_root_ref
);
4820 backref_dirid
= btrfs_root_ref_dirid(path
.nodes
[0], backref
);
4821 backref_seq
= btrfs_root_ref_sequence(path
.nodes
[0], backref
);
4822 backref_namelen
= btrfs_root_ref_name_len(path
.nodes
[0], backref
);
4824 if (backref_namelen
<= BTRFS_NAME_LEN
) {
4825 len
= backref_namelen
;
4827 len
= BTRFS_NAME_LEN
;
4828 warning("%s[%llu %llu] ref_name too long",
4829 key
.type
== BTRFS_ROOT_REF_KEY
?
4830 "ROOT_REF" : "ROOT_BACKREF",
4831 key
.objectid
, key
.offset
);
4833 read_extent_buffer(path
.nodes
[0], backref_name
,
4834 (unsigned long)(backref
+ 1), len
);
4836 if (ref_dirid
!= backref_dirid
|| ref_seq
!= backref_seq
||
4837 ref_namelen
!= backref_namelen
||
4838 strncmp(ref_name
, backref_name
, len
)) {
4839 err
|= ROOT_REF_MISMATCH
;
4840 error("%s[%llu %llu] mismatch relative ref",
4841 ref_key
->type
== BTRFS_ROOT_REF_KEY
?
4842 "ROOT_REF" : "ROOT_BACKREF",
4843 ref_key
->objectid
, ref_key
->offset
);
4846 btrfs_release_path(&path
);
4851 * Check all fs/file tree in low_memory mode.
4853 * 1. for fs tree root item, call check_fs_root()
4854 * 2. for fs tree root ref/backref, call check_root_ref()
4856 * Return 0 if no error occurred.
4858 int check_fs_roots_lowmem(struct btrfs_fs_info
*fs_info
)
4860 struct btrfs_root
*tree_root
= fs_info
->tree_root
;
4861 struct btrfs_root
*cur_root
= NULL
;
4862 struct btrfs_path path
;
4863 struct btrfs_key key
;
4864 struct extent_buffer
*node
;
4869 btrfs_init_path(&path
);
4870 key
.objectid
= BTRFS_FS_TREE_OBJECTID
;
4872 key
.type
= BTRFS_ROOT_ITEM_KEY
;
4874 ret
= btrfs_search_slot(NULL
, tree_root
, &key
, &path
, 0, 0);
4878 } else if (ret
> 0) {
4884 node
= path
.nodes
[0];
4885 slot
= path
.slots
[0];
4886 btrfs_item_key_to_cpu(node
, &key
, slot
);
4887 if (key
.objectid
> BTRFS_LAST_FREE_OBJECTID
)
4889 if (key
.type
== BTRFS_ROOT_ITEM_KEY
&&
4890 fs_root_objectid(key
.objectid
)) {
4891 if (key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
4892 cur_root
= btrfs_read_fs_root_no_cache(fs_info
,
4895 key
.offset
= (u64
)-1;
4896 cur_root
= btrfs_read_fs_root(fs_info
, &key
);
4899 if (IS_ERR(cur_root
)) {
4900 error("Fail to read fs/subvol tree: %lld",
4906 ret
= check_fs_root(cur_root
);
4909 if (key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
)
4910 btrfs_free_fs_root(cur_root
);
4911 } else if (key
.type
== BTRFS_ROOT_REF_KEY
||
4912 key
.type
== BTRFS_ROOT_BACKREF_KEY
) {
4913 ret
= check_root_ref(tree_root
, &key
, node
, slot
);
4917 ret
= btrfs_next_item(tree_root
, &path
);
4927 btrfs_release_path(&path
);
4932 * Low memory usage version check_chunks_and_extents.
4934 int check_chunks_and_extents_lowmem(struct btrfs_fs_info
*fs_info
)
4936 struct btrfs_path path
;
4937 struct btrfs_key old_key
;
4938 struct btrfs_key key
;
4939 struct btrfs_root
*root1
;
4940 struct btrfs_root
*root
;
4941 struct btrfs_root
*cur_root
;
4945 root
= fs_info
->fs_root
;
4947 root1
= root
->fs_info
->chunk_root
;
4948 ret
= check_btrfs_root(root1
, 1);
4951 root1
= root
->fs_info
->tree_root
;
4952 ret
= check_btrfs_root(root1
, 1);
4955 btrfs_init_path(&path
);
4956 key
.objectid
= BTRFS_EXTENT_TREE_OBJECTID
;
4958 key
.type
= BTRFS_ROOT_ITEM_KEY
;
4960 ret
= btrfs_search_slot(NULL
, root1
, &key
, &path
, 0, 0);
4962 error("cannot find extent tree in tree_root");
4967 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
4968 if (key
.type
!= BTRFS_ROOT_ITEM_KEY
)
4971 key
.offset
= (u64
)-1;
4973 if (key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
)
4974 cur_root
= btrfs_read_fs_root_no_cache(root
->fs_info
,
4977 cur_root
= btrfs_read_fs_root(root
->fs_info
, &key
);
4978 if (IS_ERR(cur_root
) || !cur_root
) {
4979 error("failed to read tree: %lld", key
.objectid
);
4983 ret
= check_btrfs_root(cur_root
, 1);
4986 if (key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
)
4987 btrfs_free_fs_root(cur_root
);
4989 btrfs_release_path(&path
);
4990 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
,
4991 &old_key
, &path
, 0, 0);
4995 ret
= btrfs_next_item(root1
, &path
);
5002 ret
= end_avoid_extents_overwrite(fs_info
);
5007 reset_cached_block_groups(fs_info
);
5008 /* update block accounting */
5009 ret
= repair_block_accounting(fs_info
);
5013 err
&= ~BG_ACCOUNTING_ERROR
;
5016 btrfs_release_path(&path
);