2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #define _XOPEN_SOURCE 500
25 #include <sys/types.h>
29 #include <uuid/uuid.h>
34 #include "print-tree.h"
35 #include "transaction.h"
39 #include "free-space-cache.h"
41 #include "qgroup-verify.h"
42 #include "rbtree-utils.h"
46 static u64 bytes_used
= 0;
47 static u64 total_csum_bytes
= 0;
48 static u64 total_btree_bytes
= 0;
49 static u64 total_fs_tree_bytes
= 0;
50 static u64 total_extent_tree_bytes
= 0;
51 static u64 btree_space_waste
= 0;
52 static u64 data_bytes_allocated
= 0;
53 static u64 data_bytes_referenced
= 0;
54 static int found_old_backref
= 0;
55 static LIST_HEAD(duplicate_extents
);
56 static LIST_HEAD(delete_items
);
57 static int repair
= 0;
58 static int no_holes
= 0;
59 static int init_extent_tree
= 0;
60 static int check_data_csum
= 0;
62 struct extent_backref
{
63 struct list_head list
;
64 unsigned int is_data
:1;
65 unsigned int found_extent_tree
:1;
66 unsigned int full_backref
:1;
67 unsigned int found_ref
:1;
68 unsigned int broken
:1;
72 struct extent_backref node
;
87 struct extent_backref node
;
94 struct extent_record
{
95 struct list_head backrefs
;
96 struct list_head dups
;
97 struct list_head list
;
98 struct cache_extent cache
;
99 struct btrfs_disk_key parent_key
;
104 u64 extent_item_refs
;
106 u64 parent_generation
;
110 unsigned int found_rec
:1;
111 unsigned int content_checked
:1;
112 unsigned int owner_ref_checked
:1;
113 unsigned int is_root
:1;
114 unsigned int metadata
:1;
117 struct inode_backref
{
118 struct list_head list
;
119 unsigned int found_dir_item
:1;
120 unsigned int found_dir_index
:1;
121 unsigned int found_inode_ref
:1;
122 unsigned int filetype
:8;
124 unsigned int ref_type
;
131 struct dropping_root_item_record
{
132 struct list_head list
;
133 struct btrfs_root_item ri
;
134 struct btrfs_key found_key
;
137 #define REF_ERR_NO_DIR_ITEM (1 << 0)
138 #define REF_ERR_NO_DIR_INDEX (1 << 1)
139 #define REF_ERR_NO_INODE_REF (1 << 2)
140 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
141 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
142 #define REF_ERR_DUP_INODE_REF (1 << 5)
143 #define REF_ERR_INDEX_UNMATCH (1 << 6)
144 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
145 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
146 #define REF_ERR_NO_ROOT_REF (1 << 9)
147 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
148 #define REF_ERR_DUP_ROOT_REF (1 << 11)
149 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
151 struct inode_record
{
152 struct list_head backrefs
;
153 unsigned int checked
:1;
154 unsigned int merging
:1;
155 unsigned int found_inode_item
:1;
156 unsigned int found_dir_item
:1;
157 unsigned int found_file_extent
:1;
158 unsigned int found_csum_item
:1;
159 unsigned int some_csum_missing
:1;
160 unsigned int nodatasum
:1;
173 u64 first_extent_gap
;
178 #define I_ERR_NO_INODE_ITEM (1 << 0)
179 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
180 #define I_ERR_DUP_INODE_ITEM (1 << 2)
181 #define I_ERR_DUP_DIR_INDEX (1 << 3)
182 #define I_ERR_ODD_DIR_ITEM (1 << 4)
183 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
184 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
185 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
186 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
187 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
188 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
189 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
190 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
191 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
193 struct root_backref
{
194 struct list_head list
;
195 unsigned int found_dir_item
:1;
196 unsigned int found_dir_index
:1;
197 unsigned int found_back_ref
:1;
198 unsigned int found_forward_ref
:1;
199 unsigned int reachable
:1;
209 struct list_head backrefs
;
210 struct cache_extent cache
;
211 unsigned int found_root_item
:1;
217 struct cache_extent cache
;
222 struct cache_extent cache
;
223 struct cache_tree root_cache
;
224 struct cache_tree inode_cache
;
225 struct inode_record
*current
;
234 struct walk_control
{
235 struct cache_tree shared
;
236 struct shared_node
*nodes
[BTRFS_MAX_LEVEL
];
242 struct btrfs_key key
;
244 struct list_head list
;
247 static void reset_cached_block_groups(struct btrfs_fs_info
*fs_info
);
249 static void record_root_in_trans(struct btrfs_trans_handle
*trans
,
250 struct btrfs_root
*root
)
252 if (root
->last_trans
!= trans
->transid
) {
253 root
->track_dirty
= 1;
254 root
->last_trans
= trans
->transid
;
255 root
->commit_root
= root
->node
;
256 extent_buffer_get(root
->node
);
260 static u8
imode_to_type(u32 imode
)
263 static unsigned char btrfs_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
264 [S_IFREG
>> S_SHIFT
] = BTRFS_FT_REG_FILE
,
265 [S_IFDIR
>> S_SHIFT
] = BTRFS_FT_DIR
,
266 [S_IFCHR
>> S_SHIFT
] = BTRFS_FT_CHRDEV
,
267 [S_IFBLK
>> S_SHIFT
] = BTRFS_FT_BLKDEV
,
268 [S_IFIFO
>> S_SHIFT
] = BTRFS_FT_FIFO
,
269 [S_IFSOCK
>> S_SHIFT
] = BTRFS_FT_SOCK
,
270 [S_IFLNK
>> S_SHIFT
] = BTRFS_FT_SYMLINK
,
273 return btrfs_type_by_mode
[(imode
& S_IFMT
) >> S_SHIFT
];
277 static int device_record_compare(struct rb_node
*node1
, struct rb_node
*node2
)
279 struct device_record
*rec1
;
280 struct device_record
*rec2
;
282 rec1
= rb_entry(node1
, struct device_record
, node
);
283 rec2
= rb_entry(node2
, struct device_record
, node
);
284 if (rec1
->devid
> rec2
->devid
)
286 else if (rec1
->devid
< rec2
->devid
)
292 static struct inode_record
*clone_inode_rec(struct inode_record
*orig_rec
)
294 struct inode_record
*rec
;
295 struct inode_backref
*backref
;
296 struct inode_backref
*orig
;
299 rec
= malloc(sizeof(*rec
));
300 memcpy(rec
, orig_rec
, sizeof(*rec
));
302 INIT_LIST_HEAD(&rec
->backrefs
);
304 list_for_each_entry(orig
, &orig_rec
->backrefs
, list
) {
305 size
= sizeof(*orig
) + orig
->namelen
+ 1;
306 backref
= malloc(size
);
307 memcpy(backref
, orig
, size
);
308 list_add_tail(&backref
->list
, &rec
->backrefs
);
313 static void print_inode_error(struct btrfs_root
*root
, struct inode_record
*rec
)
315 u64 root_objectid
= root
->root_key
.objectid
;
316 int errors
= rec
->errors
;
320 /* reloc root errors, we print its corresponding fs root objectid*/
321 if (root_objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
322 root_objectid
= root
->root_key
.offset
;
323 fprintf(stderr
, "reloc");
325 fprintf(stderr
, "root %llu inode %llu errors %x",
326 (unsigned long long) root_objectid
,
327 (unsigned long long) rec
->ino
, rec
->errors
);
329 if (errors
& I_ERR_NO_INODE_ITEM
)
330 fprintf(stderr
, ", no inode item");
331 if (errors
& I_ERR_NO_ORPHAN_ITEM
)
332 fprintf(stderr
, ", no orphan item");
333 if (errors
& I_ERR_DUP_INODE_ITEM
)
334 fprintf(stderr
, ", dup inode item");
335 if (errors
& I_ERR_DUP_DIR_INDEX
)
336 fprintf(stderr
, ", dup dir index");
337 if (errors
& I_ERR_ODD_DIR_ITEM
)
338 fprintf(stderr
, ", odd dir item");
339 if (errors
& I_ERR_ODD_FILE_EXTENT
)
340 fprintf(stderr
, ", odd file extent");
341 if (errors
& I_ERR_BAD_FILE_EXTENT
)
342 fprintf(stderr
, ", bad file extent");
343 if (errors
& I_ERR_FILE_EXTENT_OVERLAP
)
344 fprintf(stderr
, ", file extent overlap");
345 if (errors
& I_ERR_FILE_EXTENT_DISCOUNT
)
346 fprintf(stderr
, ", file extent discount");
347 if (errors
& I_ERR_DIR_ISIZE_WRONG
)
348 fprintf(stderr
, ", dir isize wrong");
349 if (errors
& I_ERR_FILE_NBYTES_WRONG
)
350 fprintf(stderr
, ", nbytes wrong");
351 if (errors
& I_ERR_ODD_CSUM_ITEM
)
352 fprintf(stderr
, ", odd csum item");
353 if (errors
& I_ERR_SOME_CSUM_MISSING
)
354 fprintf(stderr
, ", some csum missing");
355 if (errors
& I_ERR_LINK_COUNT_WRONG
)
356 fprintf(stderr
, ", link count wrong");
357 fprintf(stderr
, "\n");
360 static void print_ref_error(int errors
)
362 if (errors
& REF_ERR_NO_DIR_ITEM
)
363 fprintf(stderr
, ", no dir item");
364 if (errors
& REF_ERR_NO_DIR_INDEX
)
365 fprintf(stderr
, ", no dir index");
366 if (errors
& REF_ERR_NO_INODE_REF
)
367 fprintf(stderr
, ", no inode ref");
368 if (errors
& REF_ERR_DUP_DIR_ITEM
)
369 fprintf(stderr
, ", dup dir item");
370 if (errors
& REF_ERR_DUP_DIR_INDEX
)
371 fprintf(stderr
, ", dup dir index");
372 if (errors
& REF_ERR_DUP_INODE_REF
)
373 fprintf(stderr
, ", dup inode ref");
374 if (errors
& REF_ERR_INDEX_UNMATCH
)
375 fprintf(stderr
, ", index unmatch");
376 if (errors
& REF_ERR_FILETYPE_UNMATCH
)
377 fprintf(stderr
, ", filetype unmatch");
378 if (errors
& REF_ERR_NAME_TOO_LONG
)
379 fprintf(stderr
, ", name too long");
380 if (errors
& REF_ERR_NO_ROOT_REF
)
381 fprintf(stderr
, ", no root ref");
382 if (errors
& REF_ERR_NO_ROOT_BACKREF
)
383 fprintf(stderr
, ", no root backref");
384 if (errors
& REF_ERR_DUP_ROOT_REF
)
385 fprintf(stderr
, ", dup root ref");
386 if (errors
& REF_ERR_DUP_ROOT_BACKREF
)
387 fprintf(stderr
, ", dup root backref");
388 fprintf(stderr
, "\n");
391 static struct inode_record
*get_inode_rec(struct cache_tree
*inode_cache
,
394 struct ptr_node
*node
;
395 struct cache_extent
*cache
;
396 struct inode_record
*rec
= NULL
;
399 cache
= lookup_cache_extent(inode_cache
, ino
, 1);
401 node
= container_of(cache
, struct ptr_node
, cache
);
403 if (mod
&& rec
->refs
> 1) {
404 node
->data
= clone_inode_rec(rec
);
409 rec
= calloc(1, sizeof(*rec
));
411 rec
->extent_start
= (u64
)-1;
412 rec
->first_extent_gap
= (u64
)-1;
414 INIT_LIST_HEAD(&rec
->backrefs
);
416 node
= malloc(sizeof(*node
));
417 node
->cache
.start
= ino
;
418 node
->cache
.size
= 1;
421 if (ino
== BTRFS_FREE_INO_OBJECTID
)
424 ret
= insert_cache_extent(inode_cache
, &node
->cache
);
430 static void free_inode_rec(struct inode_record
*rec
)
432 struct inode_backref
*backref
;
437 while (!list_empty(&rec
->backrefs
)) {
438 backref
= list_entry(rec
->backrefs
.next
,
439 struct inode_backref
, list
);
440 list_del(&backref
->list
);
446 static int can_free_inode_rec(struct inode_record
*rec
)
448 if (!rec
->errors
&& rec
->checked
&& rec
->found_inode_item
&&
449 rec
->nlink
== rec
->found_link
&& list_empty(&rec
->backrefs
))
454 static void maybe_free_inode_rec(struct cache_tree
*inode_cache
,
455 struct inode_record
*rec
)
457 struct cache_extent
*cache
;
458 struct inode_backref
*tmp
, *backref
;
459 struct ptr_node
*node
;
460 unsigned char filetype
;
462 if (!rec
->found_inode_item
)
465 filetype
= imode_to_type(rec
->imode
);
466 list_for_each_entry_safe(backref
, tmp
, &rec
->backrefs
, list
) {
467 if (backref
->found_dir_item
&& backref
->found_dir_index
) {
468 if (backref
->filetype
!= filetype
)
469 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
470 if (!backref
->errors
&& backref
->found_inode_ref
) {
471 list_del(&backref
->list
);
477 if (!rec
->checked
|| rec
->merging
)
480 if (S_ISDIR(rec
->imode
)) {
481 if (rec
->found_size
!= rec
->isize
)
482 rec
->errors
|= I_ERR_DIR_ISIZE_WRONG
;
483 if (rec
->found_file_extent
)
484 rec
->errors
|= I_ERR_ODD_FILE_EXTENT
;
485 } else if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
486 if (rec
->found_dir_item
)
487 rec
->errors
|= I_ERR_ODD_DIR_ITEM
;
488 if (rec
->found_size
!= rec
->nbytes
)
489 rec
->errors
|= I_ERR_FILE_NBYTES_WRONG
;
490 if (rec
->extent_start
== (u64
)-1 || rec
->extent_start
> 0)
491 rec
->first_extent_gap
= 0;
492 if (rec
->nlink
> 0 && !no_holes
&&
493 (rec
->extent_end
< rec
->isize
||
494 rec
->first_extent_gap
< rec
->isize
))
495 rec
->errors
|= I_ERR_FILE_EXTENT_DISCOUNT
;
498 if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
499 if (rec
->found_csum_item
&& rec
->nodatasum
)
500 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
501 if (rec
->some_csum_missing
&& !rec
->nodatasum
)
502 rec
->errors
|= I_ERR_SOME_CSUM_MISSING
;
505 BUG_ON(rec
->refs
!= 1);
506 if (can_free_inode_rec(rec
)) {
507 cache
= lookup_cache_extent(inode_cache
, rec
->ino
, 1);
508 node
= container_of(cache
, struct ptr_node
, cache
);
509 BUG_ON(node
->data
!= rec
);
510 remove_cache_extent(inode_cache
, &node
->cache
);
516 static int check_orphan_item(struct btrfs_root
*root
, u64 ino
)
518 struct btrfs_path path
;
519 struct btrfs_key key
;
522 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
523 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
526 btrfs_init_path(&path
);
527 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
528 btrfs_release_path(&path
);
534 static int process_inode_item(struct extent_buffer
*eb
,
535 int slot
, struct btrfs_key
*key
,
536 struct shared_node
*active_node
)
538 struct inode_record
*rec
;
539 struct btrfs_inode_item
*item
;
541 rec
= active_node
->current
;
542 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
543 if (rec
->found_inode_item
) {
544 rec
->errors
|= I_ERR_DUP_INODE_ITEM
;
547 item
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_item
);
548 rec
->nlink
= btrfs_inode_nlink(eb
, item
);
549 rec
->isize
= btrfs_inode_size(eb
, item
);
550 rec
->nbytes
= btrfs_inode_nbytes(eb
, item
);
551 rec
->imode
= btrfs_inode_mode(eb
, item
);
552 if (btrfs_inode_flags(eb
, item
) & BTRFS_INODE_NODATASUM
)
554 rec
->found_inode_item
= 1;
556 rec
->errors
|= I_ERR_NO_ORPHAN_ITEM
;
557 maybe_free_inode_rec(&active_node
->inode_cache
, rec
);
561 static struct inode_backref
*get_inode_backref(struct inode_record
*rec
,
563 int namelen
, u64 dir
)
565 struct inode_backref
*backref
;
567 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
568 if (rec
->ino
== BTRFS_MULTIPLE_OBJECTIDS
)
570 if (backref
->dir
!= dir
|| backref
->namelen
!= namelen
)
572 if (memcmp(name
, backref
->name
, namelen
))
577 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
578 memset(backref
, 0, sizeof(*backref
));
580 backref
->namelen
= namelen
;
581 memcpy(backref
->name
, name
, namelen
);
582 backref
->name
[namelen
] = '\0';
583 list_add_tail(&backref
->list
, &rec
->backrefs
);
587 static int add_inode_backref(struct cache_tree
*inode_cache
,
588 u64 ino
, u64 dir
, u64 index
,
589 const char *name
, int namelen
,
590 int filetype
, int itemtype
, int errors
)
592 struct inode_record
*rec
;
593 struct inode_backref
*backref
;
595 rec
= get_inode_rec(inode_cache
, ino
, 1);
596 backref
= get_inode_backref(rec
, name
, namelen
, dir
);
598 backref
->errors
|= errors
;
599 if (itemtype
== BTRFS_DIR_INDEX_KEY
) {
600 if (backref
->found_dir_index
)
601 backref
->errors
|= REF_ERR_DUP_DIR_INDEX
;
602 if (backref
->found_inode_ref
&& backref
->index
!= index
)
603 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
604 if (backref
->found_dir_item
&& backref
->filetype
!= filetype
)
605 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
607 backref
->index
= index
;
608 backref
->filetype
= filetype
;
609 backref
->found_dir_index
= 1;
610 } else if (itemtype
== BTRFS_DIR_ITEM_KEY
) {
612 if (backref
->found_dir_item
)
613 backref
->errors
|= REF_ERR_DUP_DIR_ITEM
;
614 if (backref
->found_dir_index
&& backref
->filetype
!= filetype
)
615 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
617 backref
->filetype
= filetype
;
618 backref
->found_dir_item
= 1;
619 } else if ((itemtype
== BTRFS_INODE_REF_KEY
) ||
620 (itemtype
== BTRFS_INODE_EXTREF_KEY
)) {
621 if (backref
->found_inode_ref
)
622 backref
->errors
|= REF_ERR_DUP_INODE_REF
;
623 if (backref
->found_dir_index
&& backref
->index
!= index
)
624 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
626 backref
->index
= index
;
628 backref
->ref_type
= itemtype
;
629 backref
->found_inode_ref
= 1;
634 maybe_free_inode_rec(inode_cache
, rec
);
638 static int merge_inode_recs(struct inode_record
*src
, struct inode_record
*dst
,
639 struct cache_tree
*dst_cache
)
641 struct inode_backref
*backref
;
645 list_for_each_entry(backref
, &src
->backrefs
, list
) {
646 if (backref
->found_dir_index
) {
647 add_inode_backref(dst_cache
, dst
->ino
, backref
->dir
,
648 backref
->index
, backref
->name
,
649 backref
->namelen
, backref
->filetype
,
650 BTRFS_DIR_INDEX_KEY
, backref
->errors
);
652 if (backref
->found_dir_item
) {
654 add_inode_backref(dst_cache
, dst
->ino
,
655 backref
->dir
, 0, backref
->name
,
656 backref
->namelen
, backref
->filetype
,
657 BTRFS_DIR_ITEM_KEY
, backref
->errors
);
659 if (backref
->found_inode_ref
) {
660 add_inode_backref(dst_cache
, dst
->ino
,
661 backref
->dir
, backref
->index
,
662 backref
->name
, backref
->namelen
, 0,
663 backref
->ref_type
, backref
->errors
);
667 if (src
->found_dir_item
)
668 dst
->found_dir_item
= 1;
669 if (src
->found_file_extent
)
670 dst
->found_file_extent
= 1;
671 if (src
->found_csum_item
)
672 dst
->found_csum_item
= 1;
673 if (src
->some_csum_missing
)
674 dst
->some_csum_missing
= 1;
675 if (dst
->first_extent_gap
> src
->first_extent_gap
)
676 dst
->first_extent_gap
= src
->first_extent_gap
;
678 BUG_ON(src
->found_link
< dir_count
);
679 dst
->found_link
+= src
->found_link
- dir_count
;
680 dst
->found_size
+= src
->found_size
;
681 if (src
->extent_start
!= (u64
)-1) {
682 if (dst
->extent_start
== (u64
)-1) {
683 dst
->extent_start
= src
->extent_start
;
684 dst
->extent_end
= src
->extent_end
;
686 if (dst
->extent_end
> src
->extent_start
)
687 dst
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
688 else if (dst
->extent_end
< src
->extent_start
&&
689 dst
->extent_end
< dst
->first_extent_gap
)
690 dst
->first_extent_gap
= dst
->extent_end
;
691 if (dst
->extent_end
< src
->extent_end
)
692 dst
->extent_end
= src
->extent_end
;
696 dst
->errors
|= src
->errors
;
697 if (src
->found_inode_item
) {
698 if (!dst
->found_inode_item
) {
699 dst
->nlink
= src
->nlink
;
700 dst
->isize
= src
->isize
;
701 dst
->nbytes
= src
->nbytes
;
702 dst
->imode
= src
->imode
;
703 dst
->nodatasum
= src
->nodatasum
;
704 dst
->found_inode_item
= 1;
706 dst
->errors
|= I_ERR_DUP_INODE_ITEM
;
714 static int splice_shared_node(struct shared_node
*src_node
,
715 struct shared_node
*dst_node
)
717 struct cache_extent
*cache
;
718 struct ptr_node
*node
, *ins
;
719 struct cache_tree
*src
, *dst
;
720 struct inode_record
*rec
, *conflict
;
725 if (--src_node
->refs
== 0)
727 if (src_node
->current
)
728 current_ino
= src_node
->current
->ino
;
730 src
= &src_node
->root_cache
;
731 dst
= &dst_node
->root_cache
;
733 cache
= search_cache_extent(src
, 0);
735 node
= container_of(cache
, struct ptr_node
, cache
);
737 cache
= next_cache_extent(cache
);
740 remove_cache_extent(src
, &node
->cache
);
743 ins
= malloc(sizeof(*ins
));
744 ins
->cache
.start
= node
->cache
.start
;
745 ins
->cache
.size
= node
->cache
.size
;
749 ret
= insert_cache_extent(dst
, &ins
->cache
);
750 if (ret
== -EEXIST
) {
751 conflict
= get_inode_rec(dst
, rec
->ino
, 1);
752 merge_inode_recs(rec
, conflict
, dst
);
754 conflict
->checked
= 1;
755 if (dst_node
->current
== conflict
)
756 dst_node
->current
= NULL
;
758 maybe_free_inode_rec(dst
, conflict
);
766 if (src
== &src_node
->root_cache
) {
767 src
= &src_node
->inode_cache
;
768 dst
= &dst_node
->inode_cache
;
772 if (current_ino
> 0 && (!dst_node
->current
||
773 current_ino
> dst_node
->current
->ino
)) {
774 if (dst_node
->current
) {
775 dst_node
->current
->checked
= 1;
776 maybe_free_inode_rec(dst
, dst_node
->current
);
778 dst_node
->current
= get_inode_rec(dst
, current_ino
, 1);
783 static void free_inode_ptr(struct cache_extent
*cache
)
785 struct ptr_node
*node
;
786 struct inode_record
*rec
;
788 node
= container_of(cache
, struct ptr_node
, cache
);
794 FREE_EXTENT_CACHE_BASED_TREE(inode_recs
, free_inode_ptr
);
796 static struct shared_node
*find_shared_node(struct cache_tree
*shared
,
799 struct cache_extent
*cache
;
800 struct shared_node
*node
;
802 cache
= lookup_cache_extent(shared
, bytenr
, 1);
804 node
= container_of(cache
, struct shared_node
, cache
);
810 static int add_shared_node(struct cache_tree
*shared
, u64 bytenr
, u32 refs
)
813 struct shared_node
*node
;
815 node
= calloc(1, sizeof(*node
));
816 node
->cache
.start
= bytenr
;
817 node
->cache
.size
= 1;
818 cache_tree_init(&node
->root_cache
);
819 cache_tree_init(&node
->inode_cache
);
822 ret
= insert_cache_extent(shared
, &node
->cache
);
827 static int enter_shared_node(struct btrfs_root
*root
, u64 bytenr
, u32 refs
,
828 struct walk_control
*wc
, int level
)
830 struct shared_node
*node
;
831 struct shared_node
*dest
;
833 if (level
== wc
->active_node
)
836 BUG_ON(wc
->active_node
<= level
);
837 node
= find_shared_node(&wc
->shared
, bytenr
);
839 add_shared_node(&wc
->shared
, bytenr
, refs
);
840 node
= find_shared_node(&wc
->shared
, bytenr
);
841 wc
->nodes
[level
] = node
;
842 wc
->active_node
= level
;
846 if (wc
->root_level
== wc
->active_node
&&
847 btrfs_root_refs(&root
->root_item
) == 0) {
848 if (--node
->refs
== 0) {
849 free_inode_recs_tree(&node
->root_cache
);
850 free_inode_recs_tree(&node
->inode_cache
);
851 remove_cache_extent(&wc
->shared
, &node
->cache
);
857 dest
= wc
->nodes
[wc
->active_node
];
858 splice_shared_node(node
, dest
);
859 if (node
->refs
== 0) {
860 remove_cache_extent(&wc
->shared
, &node
->cache
);
866 static int leave_shared_node(struct btrfs_root
*root
,
867 struct walk_control
*wc
, int level
)
869 struct shared_node
*node
;
870 struct shared_node
*dest
;
873 if (level
== wc
->root_level
)
876 for (i
= level
+ 1; i
< BTRFS_MAX_LEVEL
; i
++) {
880 BUG_ON(i
>= BTRFS_MAX_LEVEL
);
882 node
= wc
->nodes
[wc
->active_node
];
883 wc
->nodes
[wc
->active_node
] = NULL
;
886 dest
= wc
->nodes
[wc
->active_node
];
887 if (wc
->active_node
< wc
->root_level
||
888 btrfs_root_refs(&root
->root_item
) > 0) {
889 BUG_ON(node
->refs
<= 1);
890 splice_shared_node(node
, dest
);
892 BUG_ON(node
->refs
< 2);
901 * 1 - if the root with id child_root_id is a child of root parent_root_id
902 * 0 - if the root child_root_id isn't a child of the root parent_root_id but
903 * has other root(s) as parent(s)
904 * 2 - if the root child_root_id doesn't have any parent roots
906 static int is_child_root(struct btrfs_root
*root
, u64 parent_root_id
,
909 struct btrfs_path path
;
910 struct btrfs_key key
;
911 struct extent_buffer
*leaf
;
915 btrfs_init_path(&path
);
917 key
.objectid
= parent_root_id
;
918 key
.type
= BTRFS_ROOT_REF_KEY
;
919 key
.offset
= child_root_id
;
920 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
, &key
, &path
,
924 btrfs_release_path(&path
);
928 key
.objectid
= child_root_id
;
929 key
.type
= BTRFS_ROOT_BACKREF_KEY
;
931 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
, &key
, &path
,
937 leaf
= path
.nodes
[0];
938 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
939 ret
= btrfs_next_leaf(root
->fs_info
->tree_root
, &path
);
942 leaf
= path
.nodes
[0];
945 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
946 if (key
.objectid
!= child_root_id
||
947 key
.type
!= BTRFS_ROOT_BACKREF_KEY
)
952 if (key
.offset
== parent_root_id
) {
953 btrfs_release_path(&path
);
960 btrfs_release_path(&path
);
963 return has_parent
? 0 : 2;
966 static int process_dir_item(struct btrfs_root
*root
,
967 struct extent_buffer
*eb
,
968 int slot
, struct btrfs_key
*key
,
969 struct shared_node
*active_node
)
979 struct btrfs_dir_item
*di
;
980 struct inode_record
*rec
;
981 struct cache_tree
*root_cache
;
982 struct cache_tree
*inode_cache
;
983 struct btrfs_key location
;
984 char namebuf
[BTRFS_NAME_LEN
];
986 root_cache
= &active_node
->root_cache
;
987 inode_cache
= &active_node
->inode_cache
;
988 rec
= active_node
->current
;
989 rec
->found_dir_item
= 1;
991 di
= btrfs_item_ptr(eb
, slot
, struct btrfs_dir_item
);
992 total
= btrfs_item_size_nr(eb
, slot
);
993 while (cur
< total
) {
995 btrfs_dir_item_key_to_cpu(eb
, di
, &location
);
996 name_len
= btrfs_dir_name_len(eb
, di
);
997 data_len
= btrfs_dir_data_len(eb
, di
);
998 filetype
= btrfs_dir_type(eb
, di
);
1000 rec
->found_size
+= name_len
;
1001 if (name_len
<= BTRFS_NAME_LEN
) {
1005 len
= BTRFS_NAME_LEN
;
1006 error
= REF_ERR_NAME_TOO_LONG
;
1008 read_extent_buffer(eb
, namebuf
, (unsigned long)(di
+ 1), len
);
1010 if (location
.type
== BTRFS_INODE_ITEM_KEY
) {
1011 add_inode_backref(inode_cache
, location
.objectid
,
1012 key
->objectid
, key
->offset
, namebuf
,
1013 len
, filetype
, key
->type
, error
);
1014 } else if (location
.type
== BTRFS_ROOT_ITEM_KEY
) {
1015 add_inode_backref(root_cache
, location
.objectid
,
1016 key
->objectid
, key
->offset
,
1017 namebuf
, len
, filetype
,
1020 fprintf(stderr
, "invalid location in dir item %u\n",
1022 add_inode_backref(inode_cache
, BTRFS_MULTIPLE_OBJECTIDS
,
1023 key
->objectid
, key
->offset
, namebuf
,
1024 len
, filetype
, key
->type
, error
);
1027 len
= sizeof(*di
) + name_len
+ data_len
;
1028 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
1031 if (key
->type
== BTRFS_DIR_INDEX_KEY
&& nritems
> 1)
1032 rec
->errors
|= I_ERR_DUP_DIR_INDEX
;
1037 static int process_inode_ref(struct extent_buffer
*eb
,
1038 int slot
, struct btrfs_key
*key
,
1039 struct shared_node
*active_node
)
1047 struct cache_tree
*inode_cache
;
1048 struct btrfs_inode_ref
*ref
;
1049 char namebuf
[BTRFS_NAME_LEN
];
1051 inode_cache
= &active_node
->inode_cache
;
1053 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
1054 total
= btrfs_item_size_nr(eb
, slot
);
1055 while (cur
< total
) {
1056 name_len
= btrfs_inode_ref_name_len(eb
, ref
);
1057 index
= btrfs_inode_ref_index(eb
, ref
);
1058 if (name_len
<= BTRFS_NAME_LEN
) {
1062 len
= BTRFS_NAME_LEN
;
1063 error
= REF_ERR_NAME_TOO_LONG
;
1065 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
1066 add_inode_backref(inode_cache
, key
->objectid
, key
->offset
,
1067 index
, namebuf
, len
, 0, key
->type
, error
);
1069 len
= sizeof(*ref
) + name_len
;
1070 ref
= (struct btrfs_inode_ref
*)((char *)ref
+ len
);
1076 static int process_inode_extref(struct extent_buffer
*eb
,
1077 int slot
, struct btrfs_key
*key
,
1078 struct shared_node
*active_node
)
1087 struct cache_tree
*inode_cache
;
1088 struct btrfs_inode_extref
*extref
;
1089 char namebuf
[BTRFS_NAME_LEN
];
1091 inode_cache
= &active_node
->inode_cache
;
1093 extref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_extref
);
1094 total
= btrfs_item_size_nr(eb
, slot
);
1095 while (cur
< total
) {
1096 name_len
= btrfs_inode_extref_name_len(eb
, extref
);
1097 index
= btrfs_inode_extref_index(eb
, extref
);
1098 parent
= btrfs_inode_extref_parent(eb
, extref
);
1099 if (name_len
<= BTRFS_NAME_LEN
) {
1103 len
= BTRFS_NAME_LEN
;
1104 error
= REF_ERR_NAME_TOO_LONG
;
1106 read_extent_buffer(eb
, namebuf
,
1107 (unsigned long)(extref
+ 1), len
);
1108 add_inode_backref(inode_cache
, key
->objectid
, parent
,
1109 index
, namebuf
, len
, 0, key
->type
, error
);
1111 len
= sizeof(*extref
) + name_len
;
1112 extref
= (struct btrfs_inode_extref
*)((char *)extref
+ len
);
1119 static int count_csum_range(struct btrfs_root
*root
, u64 start
,
1120 u64 len
, u64
*found
)
1122 struct btrfs_key key
;
1123 struct btrfs_path path
;
1124 struct extent_buffer
*leaf
;
1129 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
1131 btrfs_init_path(&path
);
1133 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
1135 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
1137 ret
= btrfs_search_slot(NULL
, root
->fs_info
->csum_root
,
1141 if (ret
> 0 && path
.slots
[0] > 0) {
1142 leaf
= path
.nodes
[0];
1143 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0] - 1);
1144 if (key
.objectid
== BTRFS_EXTENT_CSUM_OBJECTID
&&
1145 key
.type
== BTRFS_EXTENT_CSUM_KEY
)
1150 leaf
= path
.nodes
[0];
1151 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
1152 ret
= btrfs_next_leaf(root
->fs_info
->csum_root
, &path
);
1157 leaf
= path
.nodes
[0];
1160 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
1161 if (key
.objectid
!= BTRFS_EXTENT_CSUM_OBJECTID
||
1162 key
.type
!= BTRFS_EXTENT_CSUM_KEY
)
1165 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
1166 if (key
.offset
>= start
+ len
)
1169 if (key
.offset
> start
)
1172 size
= btrfs_item_size_nr(leaf
, path
.slots
[0]);
1173 csum_end
= key
.offset
+ (size
/ csum_size
) * root
->sectorsize
;
1174 if (csum_end
> start
) {
1175 size
= min(csum_end
- start
, len
);
1186 btrfs_release_path(&path
);
1190 static int process_file_extent(struct btrfs_root
*root
,
1191 struct extent_buffer
*eb
,
1192 int slot
, struct btrfs_key
*key
,
1193 struct shared_node
*active_node
)
1195 struct inode_record
*rec
;
1196 struct btrfs_file_extent_item
*fi
;
1198 u64 disk_bytenr
= 0;
1199 u64 extent_offset
= 0;
1200 u64 mask
= root
->sectorsize
- 1;
1204 rec
= active_node
->current
;
1205 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
1206 rec
->found_file_extent
= 1;
1208 if (rec
->extent_start
== (u64
)-1) {
1209 rec
->extent_start
= key
->offset
;
1210 rec
->extent_end
= key
->offset
;
1213 if (rec
->extent_end
> key
->offset
)
1214 rec
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
1215 else if (rec
->extent_end
< key
->offset
&&
1216 rec
->extent_end
< rec
->first_extent_gap
)
1217 rec
->first_extent_gap
= rec
->extent_end
;
1219 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
1220 extent_type
= btrfs_file_extent_type(eb
, fi
);
1222 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
1223 num_bytes
= btrfs_file_extent_inline_len(eb
, slot
, fi
);
1225 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1226 rec
->found_size
+= num_bytes
;
1227 num_bytes
= (num_bytes
+ mask
) & ~mask
;
1228 } else if (extent_type
== BTRFS_FILE_EXTENT_REG
||
1229 extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1230 num_bytes
= btrfs_file_extent_num_bytes(eb
, fi
);
1231 disk_bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
1232 extent_offset
= btrfs_file_extent_offset(eb
, fi
);
1233 if (num_bytes
== 0 || (num_bytes
& mask
))
1234 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1235 if (num_bytes
+ extent_offset
>
1236 btrfs_file_extent_ram_bytes(eb
, fi
))
1237 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1238 if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
&&
1239 (btrfs_file_extent_compression(eb
, fi
) ||
1240 btrfs_file_extent_encryption(eb
, fi
) ||
1241 btrfs_file_extent_other_encoding(eb
, fi
)))
1242 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1243 if (disk_bytenr
> 0)
1244 rec
->found_size
+= num_bytes
;
1246 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1248 rec
->extent_end
= key
->offset
+ num_bytes
;
1250 if (disk_bytenr
> 0) {
1252 if (btrfs_file_extent_compression(eb
, fi
))
1253 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
1255 disk_bytenr
+= extent_offset
;
1257 ret
= count_csum_range(root
, disk_bytenr
, num_bytes
, &found
);
1260 if (extent_type
== BTRFS_FILE_EXTENT_REG
) {
1262 rec
->found_csum_item
= 1;
1263 if (found
< num_bytes
)
1264 rec
->some_csum_missing
= 1;
1265 } else if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1267 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
1273 static int process_one_leaf(struct btrfs_root
*root
, struct extent_buffer
*eb
,
1274 struct walk_control
*wc
)
1276 struct btrfs_key key
;
1280 struct cache_tree
*inode_cache
;
1281 struct shared_node
*active_node
;
1283 if (wc
->root_level
== wc
->active_node
&&
1284 btrfs_root_refs(&root
->root_item
) == 0)
1287 active_node
= wc
->nodes
[wc
->active_node
];
1288 inode_cache
= &active_node
->inode_cache
;
1289 nritems
= btrfs_header_nritems(eb
);
1290 for (i
= 0; i
< nritems
; i
++) {
1291 btrfs_item_key_to_cpu(eb
, &key
, i
);
1293 if (key
.objectid
== BTRFS_FREE_SPACE_OBJECTID
)
1295 if (key
.type
== BTRFS_ORPHAN_ITEM_KEY
)
1298 if (active_node
->current
== NULL
||
1299 active_node
->current
->ino
< key
.objectid
) {
1300 if (active_node
->current
) {
1301 active_node
->current
->checked
= 1;
1302 maybe_free_inode_rec(inode_cache
,
1303 active_node
->current
);
1305 active_node
->current
= get_inode_rec(inode_cache
,
1309 case BTRFS_DIR_ITEM_KEY
:
1310 case BTRFS_DIR_INDEX_KEY
:
1311 ret
= process_dir_item(root
, eb
, i
, &key
, active_node
);
1313 case BTRFS_INODE_REF_KEY
:
1314 ret
= process_inode_ref(eb
, i
, &key
, active_node
);
1316 case BTRFS_INODE_EXTREF_KEY
:
1317 ret
= process_inode_extref(eb
, i
, &key
, active_node
);
1319 case BTRFS_INODE_ITEM_KEY
:
1320 ret
= process_inode_item(eb
, i
, &key
, active_node
);
1322 case BTRFS_EXTENT_DATA_KEY
:
1323 ret
= process_file_extent(root
, eb
, i
, &key
,
1333 static void reada_walk_down(struct btrfs_root
*root
,
1334 struct extent_buffer
*node
, int slot
)
1343 level
= btrfs_header_level(node
);
1347 nritems
= btrfs_header_nritems(node
);
1348 blocksize
= btrfs_level_size(root
, level
- 1);
1349 for (i
= slot
; i
< nritems
; i
++) {
1350 bytenr
= btrfs_node_blockptr(node
, i
);
1351 ptr_gen
= btrfs_node_ptr_generation(node
, i
);
1352 readahead_tree_block(root
, bytenr
, blocksize
, ptr_gen
);
1357 * Check the child node/leaf by the following condition:
1358 * 1. the first item key of the node/leaf should be the same with the one
1360 * 2. block in parent node should match the child node/leaf.
1361 * 3. generation of parent node and child's header should be consistent.
1363 * Or the child node/leaf pointed by the key in parent is not valid.
1365 * We hope to check leaf owner too, but since subvol may share leaves,
1366 * which makes leaf owner check not so strong, key check should be
1367 * sufficient enough for that case.
1369 static int check_child_node(struct btrfs_root
*root
,
1370 struct extent_buffer
*parent
, int slot
,
1371 struct extent_buffer
*child
)
1373 struct btrfs_key parent_key
;
1374 struct btrfs_key child_key
;
1377 btrfs_node_key_to_cpu(parent
, &parent_key
, slot
);
1378 if (btrfs_header_level(child
) == 0)
1379 btrfs_item_key_to_cpu(child
, &child_key
, 0);
1381 btrfs_node_key_to_cpu(child
, &child_key
, 0);
1383 if (memcmp(&parent_key
, &child_key
, sizeof(parent_key
))) {
1386 "Wrong key of child node/leaf, wanted: (%llu, %u, %llu), have: (%llu, %u, %llu)\n",
1387 parent_key
.objectid
, parent_key
.type
, parent_key
.offset
,
1388 child_key
.objectid
, child_key
.type
, child_key
.offset
);
1390 if (btrfs_header_bytenr(child
) != btrfs_node_blockptr(parent
, slot
)) {
1392 fprintf(stderr
, "Wrong block of child node/leaf, wanted: %llu, have: %llu\n",
1393 btrfs_node_blockptr(parent
, slot
),
1394 btrfs_header_bytenr(child
));
1396 if (btrfs_node_ptr_generation(parent
, slot
) !=
1397 btrfs_header_generation(child
)) {
1399 fprintf(stderr
, "Wrong generation of child node/leaf, wanted: %llu, have: %llu\n",
1400 btrfs_header_generation(child
),
1401 btrfs_node_ptr_generation(parent
, slot
));
1406 static int walk_down_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1407 struct walk_control
*wc
, int *level
)
1409 enum btrfs_tree_block_status status
;
1412 struct extent_buffer
*next
;
1413 struct extent_buffer
*cur
;
1418 WARN_ON(*level
< 0);
1419 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1420 ret
= btrfs_lookup_extent_info(NULL
, root
,
1421 path
->nodes
[*level
]->start
,
1422 *level
, 1, &refs
, NULL
);
1429 ret
= enter_shared_node(root
, path
->nodes
[*level
]->start
,
1437 while (*level
>= 0) {
1438 WARN_ON(*level
< 0);
1439 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1440 cur
= path
->nodes
[*level
];
1442 if (btrfs_header_level(cur
) != *level
)
1445 if (path
->slots
[*level
] >= btrfs_header_nritems(cur
))
1448 ret
= process_one_leaf(root
, cur
, wc
);
1453 bytenr
= btrfs_node_blockptr(cur
, path
->slots
[*level
]);
1454 ptr_gen
= btrfs_node_ptr_generation(cur
, path
->slots
[*level
]);
1455 blocksize
= btrfs_level_size(root
, *level
- 1);
1456 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
, *level
- 1,
1462 ret
= enter_shared_node(root
, bytenr
, refs
,
1465 path
->slots
[*level
]++;
1470 next
= btrfs_find_tree_block(root
, bytenr
, blocksize
);
1471 if (!next
|| !btrfs_buffer_uptodate(next
, ptr_gen
)) {
1472 free_extent_buffer(next
);
1473 reada_walk_down(root
, cur
, path
->slots
[*level
]);
1474 next
= read_tree_block(root
, bytenr
, blocksize
,
1482 ret
= check_child_node(root
, cur
, path
->slots
[*level
], next
);
1488 if (btrfs_is_leaf(next
))
1489 status
= btrfs_check_leaf(root
, NULL
, next
);
1491 status
= btrfs_check_node(root
, NULL
, next
);
1492 if (status
!= BTRFS_TREE_BLOCK_CLEAN
) {
1493 free_extent_buffer(next
);
1498 *level
= *level
- 1;
1499 free_extent_buffer(path
->nodes
[*level
]);
1500 path
->nodes
[*level
] = next
;
1501 path
->slots
[*level
] = 0;
1504 path
->slots
[*level
] = btrfs_header_nritems(path
->nodes
[*level
]);
1508 static int walk_up_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1509 struct walk_control
*wc
, int *level
)
1512 struct extent_buffer
*leaf
;
1514 for (i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
1515 leaf
= path
->nodes
[i
];
1516 if (path
->slots
[i
] + 1 < btrfs_header_nritems(leaf
)) {
1521 free_extent_buffer(path
->nodes
[*level
]);
1522 path
->nodes
[*level
] = NULL
;
1523 BUG_ON(*level
> wc
->active_node
);
1524 if (*level
== wc
->active_node
)
1525 leave_shared_node(root
, wc
, *level
);
1532 static int check_root_dir(struct inode_record
*rec
)
1534 struct inode_backref
*backref
;
1537 if (!rec
->found_inode_item
|| rec
->errors
)
1539 if (rec
->nlink
!= 1 || rec
->found_link
!= 0)
1541 if (list_empty(&rec
->backrefs
))
1543 backref
= list_entry(rec
->backrefs
.next
, struct inode_backref
, list
);
1544 if (!backref
->found_inode_ref
)
1546 if (backref
->index
!= 0 || backref
->namelen
!= 2 ||
1547 memcmp(backref
->name
, "..", 2))
1549 if (backref
->found_dir_index
|| backref
->found_dir_item
)
1556 static int repair_inode_isize(struct btrfs_trans_handle
*trans
,
1557 struct btrfs_root
*root
, struct btrfs_path
*path
,
1558 struct inode_record
*rec
)
1560 struct btrfs_inode_item
*ei
;
1561 struct btrfs_key key
;
1564 key
.objectid
= rec
->ino
;
1565 key
.type
= BTRFS_INODE_ITEM_KEY
;
1566 key
.offset
= (u64
)-1;
1568 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
1572 if (!path
->slots
[0]) {
1579 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
1580 if (key
.objectid
!= rec
->ino
) {
1585 ei
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
1586 struct btrfs_inode_item
);
1587 btrfs_set_inode_size(path
->nodes
[0], ei
, rec
->found_size
);
1588 btrfs_mark_buffer_dirty(path
->nodes
[0]);
1589 rec
->errors
&= ~I_ERR_DIR_ISIZE_WRONG
;
1590 printf("reset isize for dir %Lu root %Lu\n", rec
->ino
,
1591 root
->root_key
.objectid
);
1593 btrfs_release_path(path
);
1597 static int repair_inode_orphan_item(struct btrfs_trans_handle
*trans
,
1598 struct btrfs_root
*root
,
1599 struct btrfs_path
*path
,
1600 struct inode_record
*rec
)
1602 struct btrfs_key key
;
1605 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
1606 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
1607 key
.offset
= rec
->ino
;
1609 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, 0);
1610 btrfs_release_path(path
);
1612 rec
->errors
&= ~I_ERR_NO_ORPHAN_ITEM
;
1616 static int add_missing_dir_index(struct btrfs_root
*root
,
1617 struct cache_tree
*inode_cache
,
1618 struct inode_record
*rec
,
1619 struct inode_backref
*backref
)
1621 struct btrfs_path
*path
;
1622 struct btrfs_trans_handle
*trans
;
1623 struct btrfs_dir_item
*dir_item
;
1624 struct extent_buffer
*leaf
;
1625 struct btrfs_key key
;
1626 struct btrfs_disk_key disk_key
;
1627 struct inode_record
*dir_rec
;
1628 unsigned long name_ptr
;
1629 u32 data_size
= sizeof(*dir_item
) + backref
->namelen
;
1632 path
= btrfs_alloc_path();
1636 trans
= btrfs_start_transaction(root
, 1);
1637 if (IS_ERR(trans
)) {
1638 btrfs_free_path(path
);
1639 return PTR_ERR(trans
);
1642 fprintf(stderr
, "repairing missing dir index item for inode %llu\n",
1643 (unsigned long long)rec
->ino
);
1644 key
.objectid
= backref
->dir
;
1645 key
.type
= BTRFS_DIR_INDEX_KEY
;
1646 key
.offset
= backref
->index
;
1648 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, data_size
);
1651 leaf
= path
->nodes
[0];
1652 dir_item
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_dir_item
);
1654 disk_key
.objectid
= cpu_to_le64(rec
->ino
);
1655 disk_key
.type
= BTRFS_INODE_ITEM_KEY
;
1656 disk_key
.offset
= 0;
1658 btrfs_set_dir_item_key(leaf
, dir_item
, &disk_key
);
1659 btrfs_set_dir_type(leaf
, dir_item
, imode_to_type(rec
->imode
));
1660 btrfs_set_dir_data_len(leaf
, dir_item
, 0);
1661 btrfs_set_dir_name_len(leaf
, dir_item
, backref
->namelen
);
1662 name_ptr
= (unsigned long)(dir_item
+ 1);
1663 write_extent_buffer(leaf
, backref
->name
, name_ptr
, backref
->namelen
);
1664 btrfs_mark_buffer_dirty(leaf
);
1665 btrfs_free_path(path
);
1666 btrfs_commit_transaction(trans
, root
);
1668 backref
->found_dir_index
= 1;
1669 dir_rec
= get_inode_rec(inode_cache
, backref
->dir
, 0);
1672 dir_rec
->found_size
+= backref
->namelen
;
1673 if (dir_rec
->found_size
== dir_rec
->isize
&&
1674 (dir_rec
->errors
& I_ERR_DIR_ISIZE_WRONG
))
1675 dir_rec
->errors
&= ~I_ERR_DIR_ISIZE_WRONG
;
1676 if (dir_rec
->found_size
!= dir_rec
->isize
)
1677 dir_rec
->errors
|= I_ERR_DIR_ISIZE_WRONG
;
1682 static int delete_dir_index(struct btrfs_root
*root
,
1683 struct cache_tree
*inode_cache
,
1684 struct inode_record
*rec
,
1685 struct inode_backref
*backref
)
1687 struct btrfs_trans_handle
*trans
;
1688 struct btrfs_dir_item
*di
;
1689 struct btrfs_path
*path
;
1692 path
= btrfs_alloc_path();
1696 trans
= btrfs_start_transaction(root
, 1);
1697 if (IS_ERR(trans
)) {
1698 btrfs_free_path(path
);
1699 return PTR_ERR(trans
);
1703 fprintf(stderr
, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
1704 (unsigned long long)backref
->dir
,
1705 BTRFS_DIR_INDEX_KEY
, (unsigned long long)backref
->index
,
1706 (unsigned long long)root
->objectid
);
1708 di
= btrfs_lookup_dir_index(trans
, root
, path
, backref
->dir
,
1709 backref
->name
, backref
->namelen
,
1710 backref
->index
, -1);
1713 btrfs_free_path(path
);
1714 btrfs_commit_transaction(trans
, root
);
1721 ret
= btrfs_del_item(trans
, root
, path
);
1723 ret
= btrfs_delete_one_dir_name(trans
, root
, path
, di
);
1725 btrfs_free_path(path
);
1726 btrfs_commit_transaction(trans
, root
);
1730 static int repair_inode_backrefs(struct btrfs_root
*root
,
1731 struct inode_record
*rec
,
1732 struct cache_tree
*inode_cache
,
1735 struct inode_backref
*tmp
, *backref
;
1736 u64 root_dirid
= btrfs_root_dirid(&root
->root_item
);
1740 list_for_each_entry_safe(backref
, tmp
, &rec
->backrefs
, list
) {
1741 /* Index 0 for root dir's are special, don't mess with it */
1742 if (rec
->ino
== root_dirid
&& backref
->index
== 0)
1746 ((backref
->found_dir_index
&& !backref
->found_inode_ref
) ||
1747 (backref
->found_dir_index
&& backref
->found_inode_ref
&&
1748 (backref
->errors
& REF_ERR_INDEX_UNMATCH
)))) {
1749 ret
= delete_dir_index(root
, inode_cache
, rec
, backref
);
1753 list_del(&backref
->list
);
1757 if (!delete && !backref
->found_dir_index
&&
1758 backref
->found_dir_item
&& backref
->found_inode_ref
) {
1759 ret
= add_missing_dir_index(root
, inode_cache
, rec
,
1764 if (backref
->found_dir_item
&&
1765 backref
->found_dir_index
&&
1766 backref
->found_dir_index
) {
1767 if (!backref
->errors
&&
1768 backref
->found_inode_ref
) {
1769 list_del(&backref
->list
);
1776 return ret
? ret
: repaired
;
1779 static int try_repair_inode(struct btrfs_root
*root
, struct inode_record
*rec
)
1781 struct btrfs_trans_handle
*trans
;
1782 struct btrfs_path
*path
;
1785 if (!(rec
->errors
& (I_ERR_DIR_ISIZE_WRONG
| I_ERR_NO_ORPHAN_ITEM
)))
1788 path
= btrfs_alloc_path();
1792 trans
= btrfs_start_transaction(root
, 1);
1793 if (IS_ERR(trans
)) {
1794 btrfs_free_path(path
);
1795 return PTR_ERR(trans
);
1798 if (rec
->errors
& I_ERR_DIR_ISIZE_WRONG
)
1799 ret
= repair_inode_isize(trans
, root
, path
, rec
);
1800 if (!ret
&& rec
->errors
& I_ERR_NO_ORPHAN_ITEM
)
1801 ret
= repair_inode_orphan_item(trans
, root
, path
, rec
);
1802 btrfs_commit_transaction(trans
, root
);
1803 btrfs_free_path(path
);
1807 static int check_inode_recs(struct btrfs_root
*root
,
1808 struct cache_tree
*inode_cache
)
1810 struct cache_extent
*cache
;
1811 struct ptr_node
*node
;
1812 struct inode_record
*rec
;
1813 struct inode_backref
*backref
;
1818 u64 root_dirid
= btrfs_root_dirid(&root
->root_item
);
1820 if (btrfs_root_refs(&root
->root_item
) == 0) {
1821 if (!cache_tree_empty(inode_cache
))
1822 fprintf(stderr
, "warning line %d\n", __LINE__
);
1827 * We need to repair backrefs first because we could change some of the
1828 * errors in the inode recs.
1830 * We also need to go through and delete invalid backrefs first and then
1831 * add the correct ones second. We do this because we may get EEXIST
1832 * when adding back the correct index because we hadn't yet deleted the
1835 * For example, if we were missing a dir index then the directories
1836 * isize would be wrong, so if we fixed the isize to what we thought it
1837 * would be and then fixed the backref we'd still have a invalid fs, so
1838 * we need to add back the dir index and then check to see if the isize
1843 if (stage
== 3 && !err
)
1846 cache
= search_cache_extent(inode_cache
, 0);
1847 while (repair
&& cache
) {
1848 node
= container_of(cache
, struct ptr_node
, cache
);
1850 cache
= next_cache_extent(cache
);
1852 /* Need to free everything up and rescan */
1854 remove_cache_extent(inode_cache
, &node
->cache
);
1856 free_inode_rec(rec
);
1860 if (list_empty(&rec
->backrefs
))
1863 ret
= repair_inode_backrefs(root
, rec
, inode_cache
,
1877 rec
= get_inode_rec(inode_cache
, root_dirid
, 0);
1879 ret
= check_root_dir(rec
);
1881 fprintf(stderr
, "root %llu root dir %llu error\n",
1882 (unsigned long long)root
->root_key
.objectid
,
1883 (unsigned long long)root_dirid
);
1887 fprintf(stderr
, "root %llu root dir %llu not found\n",
1888 (unsigned long long)root
->root_key
.objectid
,
1889 (unsigned long long)root_dirid
);
1893 cache
= search_cache_extent(inode_cache
, 0);
1896 node
= container_of(cache
, struct ptr_node
, cache
);
1898 remove_cache_extent(inode_cache
, &node
->cache
);
1900 if (rec
->ino
== root_dirid
||
1901 rec
->ino
== BTRFS_ORPHAN_OBJECTID
) {
1902 free_inode_rec(rec
);
1906 if (rec
->errors
& I_ERR_NO_ORPHAN_ITEM
) {
1907 ret
= check_orphan_item(root
, rec
->ino
);
1909 rec
->errors
&= ~I_ERR_NO_ORPHAN_ITEM
;
1910 if (can_free_inode_rec(rec
)) {
1911 free_inode_rec(rec
);
1917 ret
= try_repair_inode(root
, rec
);
1918 if (ret
== 0 && can_free_inode_rec(rec
)) {
1919 free_inode_rec(rec
);
1926 if (!rec
->found_inode_item
)
1927 rec
->errors
|= I_ERR_NO_INODE_ITEM
;
1928 if (rec
->found_link
!= rec
->nlink
)
1929 rec
->errors
|= I_ERR_LINK_COUNT_WRONG
;
1930 print_inode_error(root
, rec
);
1931 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1932 if (!backref
->found_dir_item
)
1933 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1934 if (!backref
->found_dir_index
)
1935 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1936 if (!backref
->found_inode_ref
)
1937 backref
->errors
|= REF_ERR_NO_INODE_REF
;
1938 fprintf(stderr
, "\tunresolved ref dir %llu index %llu"
1939 " namelen %u name %s filetype %d errors %x",
1940 (unsigned long long)backref
->dir
,
1941 (unsigned long long)backref
->index
,
1942 backref
->namelen
, backref
->name
,
1943 backref
->filetype
, backref
->errors
);
1944 print_ref_error(backref
->errors
);
1946 free_inode_rec(rec
);
1948 return (error
> 0) ? -1 : 0;
1951 static struct root_record
*get_root_rec(struct cache_tree
*root_cache
,
1954 struct cache_extent
*cache
;
1955 struct root_record
*rec
= NULL
;
1958 cache
= lookup_cache_extent(root_cache
, objectid
, 1);
1960 rec
= container_of(cache
, struct root_record
, cache
);
1962 rec
= calloc(1, sizeof(*rec
));
1963 rec
->objectid
= objectid
;
1964 INIT_LIST_HEAD(&rec
->backrefs
);
1965 rec
->cache
.start
= objectid
;
1966 rec
->cache
.size
= 1;
1968 ret
= insert_cache_extent(root_cache
, &rec
->cache
);
1974 static struct root_backref
*get_root_backref(struct root_record
*rec
,
1975 u64 ref_root
, u64 dir
, u64 index
,
1976 const char *name
, int namelen
)
1978 struct root_backref
*backref
;
1980 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1981 if (backref
->ref_root
!= ref_root
|| backref
->dir
!= dir
||
1982 backref
->namelen
!= namelen
)
1984 if (memcmp(name
, backref
->name
, namelen
))
1989 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
1990 memset(backref
, 0, sizeof(*backref
));
1991 backref
->ref_root
= ref_root
;
1993 backref
->index
= index
;
1994 backref
->namelen
= namelen
;
1995 memcpy(backref
->name
, name
, namelen
);
1996 backref
->name
[namelen
] = '\0';
1997 list_add_tail(&backref
->list
, &rec
->backrefs
);
2001 static void free_root_record(struct cache_extent
*cache
)
2003 struct root_record
*rec
;
2004 struct root_backref
*backref
;
2006 rec
= container_of(cache
, struct root_record
, cache
);
2007 while (!list_empty(&rec
->backrefs
)) {
2008 backref
= list_entry(rec
->backrefs
.next
,
2009 struct root_backref
, list
);
2010 list_del(&backref
->list
);
2017 FREE_EXTENT_CACHE_BASED_TREE(root_recs
, free_root_record
);
2019 static int add_root_backref(struct cache_tree
*root_cache
,
2020 u64 root_id
, u64 ref_root
, u64 dir
, u64 index
,
2021 const char *name
, int namelen
,
2022 int item_type
, int errors
)
2024 struct root_record
*rec
;
2025 struct root_backref
*backref
;
2027 rec
= get_root_rec(root_cache
, root_id
);
2028 backref
= get_root_backref(rec
, ref_root
, dir
, index
, name
, namelen
);
2030 backref
->errors
|= errors
;
2032 if (item_type
!= BTRFS_DIR_ITEM_KEY
) {
2033 if (backref
->found_dir_index
|| backref
->found_back_ref
||
2034 backref
->found_forward_ref
) {
2035 if (backref
->index
!= index
)
2036 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
2038 backref
->index
= index
;
2042 if (item_type
== BTRFS_DIR_ITEM_KEY
) {
2043 if (backref
->found_forward_ref
)
2045 backref
->found_dir_item
= 1;
2046 } else if (item_type
== BTRFS_DIR_INDEX_KEY
) {
2047 backref
->found_dir_index
= 1;
2048 } else if (item_type
== BTRFS_ROOT_REF_KEY
) {
2049 if (backref
->found_forward_ref
)
2050 backref
->errors
|= REF_ERR_DUP_ROOT_REF
;
2051 else if (backref
->found_dir_item
)
2053 backref
->found_forward_ref
= 1;
2054 } else if (item_type
== BTRFS_ROOT_BACKREF_KEY
) {
2055 if (backref
->found_back_ref
)
2056 backref
->errors
|= REF_ERR_DUP_ROOT_BACKREF
;
2057 backref
->found_back_ref
= 1;
2062 if (backref
->found_forward_ref
&& backref
->found_dir_item
)
2063 backref
->reachable
= 1;
2067 static int merge_root_recs(struct btrfs_root
*root
,
2068 struct cache_tree
*src_cache
,
2069 struct cache_tree
*dst_cache
)
2071 struct cache_extent
*cache
;
2072 struct ptr_node
*node
;
2073 struct inode_record
*rec
;
2074 struct inode_backref
*backref
;
2077 if (root
->root_key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
2078 free_inode_recs_tree(src_cache
);
2083 cache
= search_cache_extent(src_cache
, 0);
2086 node
= container_of(cache
, struct ptr_node
, cache
);
2088 remove_cache_extent(src_cache
, &node
->cache
);
2091 ret
= is_child_root(root
, root
->objectid
, rec
->ino
);
2097 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
2098 BUG_ON(backref
->found_inode_ref
);
2099 if (backref
->found_dir_item
)
2100 add_root_backref(dst_cache
, rec
->ino
,
2101 root
->root_key
.objectid
, backref
->dir
,
2102 backref
->index
, backref
->name
,
2103 backref
->namelen
, BTRFS_DIR_ITEM_KEY
,
2105 if (backref
->found_dir_index
)
2106 add_root_backref(dst_cache
, rec
->ino
,
2107 root
->root_key
.objectid
, backref
->dir
,
2108 backref
->index
, backref
->name
,
2109 backref
->namelen
, BTRFS_DIR_INDEX_KEY
,
2113 free_inode_rec(rec
);
2120 static int check_root_refs(struct btrfs_root
*root
,
2121 struct cache_tree
*root_cache
)
2123 struct root_record
*rec
;
2124 struct root_record
*ref_root
;
2125 struct root_backref
*backref
;
2126 struct cache_extent
*cache
;
2132 rec
= get_root_rec(root_cache
, BTRFS_FS_TREE_OBJECTID
);
2135 /* fixme: this can not detect circular references */
2138 cache
= search_cache_extent(root_cache
, 0);
2142 rec
= container_of(cache
, struct root_record
, cache
);
2143 cache
= next_cache_extent(cache
);
2145 if (rec
->found_ref
== 0)
2148 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
2149 if (!backref
->reachable
)
2152 ref_root
= get_root_rec(root_cache
,
2154 if (ref_root
->found_ref
> 0)
2157 backref
->reachable
= 0;
2159 if (rec
->found_ref
== 0)
2165 cache
= search_cache_extent(root_cache
, 0);
2169 rec
= container_of(cache
, struct root_record
, cache
);
2170 cache
= next_cache_extent(cache
);
2172 if (rec
->found_ref
== 0 &&
2173 rec
->objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
2174 rec
->objectid
<= BTRFS_LAST_FREE_OBJECTID
) {
2175 ret
= check_orphan_item(root
->fs_info
->tree_root
,
2181 * If we don't have a root item then we likely just have
2182 * a dir item in a snapshot for this root but no actual
2183 * ref key or anything so it's meaningless.
2185 if (!rec
->found_root_item
)
2188 fprintf(stderr
, "fs tree %llu not referenced\n",
2189 (unsigned long long)rec
->objectid
);
2193 if (rec
->found_ref
> 0 && !rec
->found_root_item
)
2195 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
2196 if (!backref
->found_dir_item
)
2197 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
2198 if (!backref
->found_dir_index
)
2199 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
2200 if (!backref
->found_back_ref
)
2201 backref
->errors
|= REF_ERR_NO_ROOT_BACKREF
;
2202 if (!backref
->found_forward_ref
)
2203 backref
->errors
|= REF_ERR_NO_ROOT_REF
;
2204 if (backref
->reachable
&& backref
->errors
)
2211 fprintf(stderr
, "fs tree %llu refs %u %s\n",
2212 (unsigned long long)rec
->objectid
, rec
->found_ref
,
2213 rec
->found_root_item
? "" : "not found");
2215 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
2216 if (!backref
->reachable
)
2218 if (!backref
->errors
&& rec
->found_root_item
)
2220 fprintf(stderr
, "\tunresolved ref root %llu dir %llu"
2221 " index %llu namelen %u name %s errors %x\n",
2222 (unsigned long long)backref
->ref_root
,
2223 (unsigned long long)backref
->dir
,
2224 (unsigned long long)backref
->index
,
2225 backref
->namelen
, backref
->name
,
2227 print_ref_error(backref
->errors
);
2230 return errors
> 0 ? 1 : 0;
2233 static int process_root_ref(struct extent_buffer
*eb
, int slot
,
2234 struct btrfs_key
*key
,
2235 struct cache_tree
*root_cache
)
2241 struct btrfs_root_ref
*ref
;
2242 char namebuf
[BTRFS_NAME_LEN
];
2245 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_root_ref
);
2247 dirid
= btrfs_root_ref_dirid(eb
, ref
);
2248 index
= btrfs_root_ref_sequence(eb
, ref
);
2249 name_len
= btrfs_root_ref_name_len(eb
, ref
);
2251 if (name_len
<= BTRFS_NAME_LEN
) {
2255 len
= BTRFS_NAME_LEN
;
2256 error
= REF_ERR_NAME_TOO_LONG
;
2258 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
2260 if (key
->type
== BTRFS_ROOT_REF_KEY
) {
2261 add_root_backref(root_cache
, key
->offset
, key
->objectid
, dirid
,
2262 index
, namebuf
, len
, key
->type
, error
);
2264 add_root_backref(root_cache
, key
->objectid
, key
->offset
, dirid
,
2265 index
, namebuf
, len
, key
->type
, error
);
2270 static int check_fs_root(struct btrfs_root
*root
,
2271 struct cache_tree
*root_cache
,
2272 struct walk_control
*wc
)
2278 struct btrfs_path path
;
2279 struct shared_node root_node
;
2280 struct root_record
*rec
;
2281 struct btrfs_root_item
*root_item
= &root
->root_item
;
2282 enum btrfs_tree_block_status status
;
2284 if (root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
2285 rec
= get_root_rec(root_cache
, root
->root_key
.objectid
);
2286 if (btrfs_root_refs(root_item
) > 0)
2287 rec
->found_root_item
= 1;
2290 btrfs_init_path(&path
);
2291 memset(&root_node
, 0, sizeof(root_node
));
2292 cache_tree_init(&root_node
.root_cache
);
2293 cache_tree_init(&root_node
.inode_cache
);
2295 level
= btrfs_header_level(root
->node
);
2296 memset(wc
->nodes
, 0, sizeof(wc
->nodes
));
2297 wc
->nodes
[level
] = &root_node
;
2298 wc
->active_node
= level
;
2299 wc
->root_level
= level
;
2301 /* We may not have checked the root block, lets do that now */
2302 if (btrfs_is_leaf(root
->node
))
2303 status
= btrfs_check_leaf(root
, NULL
, root
->node
);
2305 status
= btrfs_check_node(root
, NULL
, root
->node
);
2306 if (status
!= BTRFS_TREE_BLOCK_CLEAN
)
2309 if (btrfs_root_refs(root_item
) > 0 ||
2310 btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
2311 path
.nodes
[level
] = root
->node
;
2312 extent_buffer_get(root
->node
);
2313 path
.slots
[level
] = 0;
2315 struct btrfs_key key
;
2316 struct btrfs_disk_key found_key
;
2318 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
2319 level
= root_item
->drop_level
;
2320 path
.lowest_level
= level
;
2321 wret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
2324 btrfs_node_key(path
.nodes
[level
], &found_key
,
2326 WARN_ON(memcmp(&found_key
, &root_item
->drop_progress
,
2327 sizeof(found_key
)));
2331 wret
= walk_down_tree(root
, &path
, wc
, &level
);
2337 wret
= walk_up_tree(root
, &path
, wc
, &level
);
2344 btrfs_release_path(&path
);
2346 err
= merge_root_recs(root
, &root_node
.root_cache
, root_cache
);
2350 if (root_node
.current
) {
2351 root_node
.current
->checked
= 1;
2352 maybe_free_inode_rec(&root_node
.inode_cache
,
2356 err
= check_inode_recs(root
, &root_node
.inode_cache
);
2362 static int fs_root_objectid(u64 objectid
)
2364 if (objectid
== BTRFS_TREE_RELOC_OBJECTID
||
2365 objectid
== BTRFS_DATA_RELOC_TREE_OBJECTID
)
2367 return is_fstree(objectid
);
2370 static int check_fs_roots(struct btrfs_root
*root
,
2371 struct cache_tree
*root_cache
)
2373 struct btrfs_path path
;
2374 struct btrfs_key key
;
2375 struct walk_control wc
;
2376 struct extent_buffer
*leaf
, *tree_node
;
2377 struct btrfs_root
*tmp_root
;
2378 struct btrfs_root
*tree_root
= root
->fs_info
->tree_root
;
2383 * Just in case we made any changes to the extent tree that weren't
2384 * reflected into the free space cache yet.
2387 reset_cached_block_groups(root
->fs_info
);
2388 memset(&wc
, 0, sizeof(wc
));
2389 cache_tree_init(&wc
.shared
);
2390 btrfs_init_path(&path
);
2395 key
.type
= BTRFS_ROOT_ITEM_KEY
;
2396 ret
= btrfs_search_slot(NULL
, tree_root
, &key
, &path
, 0, 0);
2401 tree_node
= tree_root
->node
;
2403 if (tree_node
!= tree_root
->node
) {
2404 free_root_recs_tree(root_cache
);
2405 btrfs_release_path(&path
);
2408 leaf
= path
.nodes
[0];
2409 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
2410 ret
= btrfs_next_leaf(tree_root
, &path
);
2416 leaf
= path
.nodes
[0];
2418 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
2419 if (key
.type
== BTRFS_ROOT_ITEM_KEY
&&
2420 fs_root_objectid(key
.objectid
)) {
2421 if (key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
2422 tmp_root
= btrfs_read_fs_root_no_cache(
2423 root
->fs_info
, &key
);
2425 key
.offset
= (u64
)-1;
2426 tmp_root
= btrfs_read_fs_root(
2427 root
->fs_info
, &key
);
2429 if (IS_ERR(tmp_root
)) {
2433 ret
= check_fs_root(tmp_root
, root_cache
, &wc
);
2434 if (ret
== -EAGAIN
) {
2435 free_root_recs_tree(root_cache
);
2436 btrfs_release_path(&path
);
2441 if (key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
)
2442 btrfs_free_fs_root(tmp_root
);
2443 } else if (key
.type
== BTRFS_ROOT_REF_KEY
||
2444 key
.type
== BTRFS_ROOT_BACKREF_KEY
) {
2445 process_root_ref(leaf
, path
.slots
[0], &key
,
2452 btrfs_release_path(&path
);
2454 free_extent_cache_tree(&wc
.shared
);
2455 if (!cache_tree_empty(&wc
.shared
))
2456 fprintf(stderr
, "warning line %d\n", __LINE__
);
2461 static int all_backpointers_checked(struct extent_record
*rec
, int print_errs
)
2463 struct list_head
*cur
= rec
->backrefs
.next
;
2464 struct extent_backref
*back
;
2465 struct tree_backref
*tback
;
2466 struct data_backref
*dback
;
2470 while(cur
!= &rec
->backrefs
) {
2471 back
= list_entry(cur
, struct extent_backref
, list
);
2473 if (!back
->found_extent_tree
) {
2477 if (back
->is_data
) {
2478 dback
= (struct data_backref
*)back
;
2479 fprintf(stderr
, "Backref %llu %s %llu"
2480 " owner %llu offset %llu num_refs %lu"
2481 " not found in extent tree\n",
2482 (unsigned long long)rec
->start
,
2483 back
->full_backref
?
2485 back
->full_backref
?
2486 (unsigned long long)dback
->parent
:
2487 (unsigned long long)dback
->root
,
2488 (unsigned long long)dback
->owner
,
2489 (unsigned long long)dback
->offset
,
2490 (unsigned long)dback
->num_refs
);
2492 tback
= (struct tree_backref
*)back
;
2493 fprintf(stderr
, "Backref %llu parent %llu"
2494 " root %llu not found in extent tree\n",
2495 (unsigned long long)rec
->start
,
2496 (unsigned long long)tback
->parent
,
2497 (unsigned long long)tback
->root
);
2500 if (!back
->is_data
&& !back
->found_ref
) {
2504 tback
= (struct tree_backref
*)back
;
2505 fprintf(stderr
, "Backref %llu %s %llu not referenced back %p\n",
2506 (unsigned long long)rec
->start
,
2507 back
->full_backref
? "parent" : "root",
2508 back
->full_backref
?
2509 (unsigned long long)tback
->parent
:
2510 (unsigned long long)tback
->root
, back
);
2512 if (back
->is_data
) {
2513 dback
= (struct data_backref
*)back
;
2514 if (dback
->found_ref
!= dback
->num_refs
) {
2518 fprintf(stderr
, "Incorrect local backref count"
2519 " on %llu %s %llu owner %llu"
2520 " offset %llu found %u wanted %u back %p\n",
2521 (unsigned long long)rec
->start
,
2522 back
->full_backref
?
2524 back
->full_backref
?
2525 (unsigned long long)dback
->parent
:
2526 (unsigned long long)dback
->root
,
2527 (unsigned long long)dback
->owner
,
2528 (unsigned long long)dback
->offset
,
2529 dback
->found_ref
, dback
->num_refs
, back
);
2531 if (dback
->disk_bytenr
!= rec
->start
) {
2535 fprintf(stderr
, "Backref disk bytenr does not"
2536 " match extent record, bytenr=%llu, "
2537 "ref bytenr=%llu\n",
2538 (unsigned long long)rec
->start
,
2539 (unsigned long long)dback
->disk_bytenr
);
2542 if (dback
->bytes
!= rec
->nr
) {
2546 fprintf(stderr
, "Backref bytes do not match "
2547 "extent backref, bytenr=%llu, ref "
2548 "bytes=%llu, backref bytes=%llu\n",
2549 (unsigned long long)rec
->start
,
2550 (unsigned long long)rec
->nr
,
2551 (unsigned long long)dback
->bytes
);
2554 if (!back
->is_data
) {
2557 dback
= (struct data_backref
*)back
;
2558 found
+= dback
->found_ref
;
2561 if (found
!= rec
->refs
) {
2565 fprintf(stderr
, "Incorrect global backref count "
2566 "on %llu found %llu wanted %llu\n",
2567 (unsigned long long)rec
->start
,
2568 (unsigned long long)found
,
2569 (unsigned long long)rec
->refs
);
2575 static int free_all_extent_backrefs(struct extent_record
*rec
)
2577 struct extent_backref
*back
;
2578 struct list_head
*cur
;
2579 while (!list_empty(&rec
->backrefs
)) {
2580 cur
= rec
->backrefs
.next
;
2581 back
= list_entry(cur
, struct extent_backref
, list
);
2588 static void free_extent_record_cache(struct btrfs_fs_info
*fs_info
,
2589 struct cache_tree
*extent_cache
)
2591 struct cache_extent
*cache
;
2592 struct extent_record
*rec
;
2595 cache
= first_cache_extent(extent_cache
);
2598 rec
= container_of(cache
, struct extent_record
, cache
);
2599 btrfs_unpin_extent(fs_info
, rec
->start
, rec
->max_size
);
2600 remove_cache_extent(extent_cache
, cache
);
2601 free_all_extent_backrefs(rec
);
2606 static int maybe_free_extent_rec(struct cache_tree
*extent_cache
,
2607 struct extent_record
*rec
)
2609 if (rec
->content_checked
&& rec
->owner_ref_checked
&&
2610 rec
->extent_item_refs
== rec
->refs
&& rec
->refs
> 0 &&
2611 rec
->num_duplicates
== 0 && !all_backpointers_checked(rec
, 0)) {
2612 remove_cache_extent(extent_cache
, &rec
->cache
);
2613 free_all_extent_backrefs(rec
);
2614 list_del_init(&rec
->list
);
2620 static int check_owner_ref(struct btrfs_root
*root
,
2621 struct extent_record
*rec
,
2622 struct extent_buffer
*buf
)
2624 struct extent_backref
*node
;
2625 struct tree_backref
*back
;
2626 struct btrfs_root
*ref_root
;
2627 struct btrfs_key key
;
2628 struct btrfs_path path
;
2629 struct extent_buffer
*parent
;
2634 list_for_each_entry(node
, &rec
->backrefs
, list
) {
2637 if (!node
->found_ref
)
2639 if (node
->full_backref
)
2641 back
= (struct tree_backref
*)node
;
2642 if (btrfs_header_owner(buf
) == back
->root
)
2645 BUG_ON(rec
->is_root
);
2647 /* try to find the block by search corresponding fs tree */
2648 key
.objectid
= btrfs_header_owner(buf
);
2649 key
.type
= BTRFS_ROOT_ITEM_KEY
;
2650 key
.offset
= (u64
)-1;
2652 ref_root
= btrfs_read_fs_root(root
->fs_info
, &key
);
2653 if (IS_ERR(ref_root
))
2656 level
= btrfs_header_level(buf
);
2658 btrfs_item_key_to_cpu(buf
, &key
, 0);
2660 btrfs_node_key_to_cpu(buf
, &key
, 0);
2662 btrfs_init_path(&path
);
2663 path
.lowest_level
= level
+ 1;
2664 ret
= btrfs_search_slot(NULL
, ref_root
, &key
, &path
, 0, 0);
2668 parent
= path
.nodes
[level
+ 1];
2669 if (parent
&& buf
->start
== btrfs_node_blockptr(parent
,
2670 path
.slots
[level
+ 1]))
2673 btrfs_release_path(&path
);
2674 return found
? 0 : 1;
2677 static int is_extent_tree_record(struct extent_record
*rec
)
2679 struct list_head
*cur
= rec
->backrefs
.next
;
2680 struct extent_backref
*node
;
2681 struct tree_backref
*back
;
2684 while(cur
!= &rec
->backrefs
) {
2685 node
= list_entry(cur
, struct extent_backref
, list
);
2689 back
= (struct tree_backref
*)node
;
2690 if (node
->full_backref
)
2692 if (back
->root
== BTRFS_EXTENT_TREE_OBJECTID
)
2699 static int record_bad_block_io(struct btrfs_fs_info
*info
,
2700 struct cache_tree
*extent_cache
,
2703 struct extent_record
*rec
;
2704 struct cache_extent
*cache
;
2705 struct btrfs_key key
;
2707 cache
= lookup_cache_extent(extent_cache
, start
, len
);
2711 rec
= container_of(cache
, struct extent_record
, cache
);
2712 if (!is_extent_tree_record(rec
))
2715 btrfs_disk_key_to_cpu(&key
, &rec
->parent_key
);
2716 return btrfs_add_corrupt_extent_record(info
, &key
, start
, len
, 0);
2719 static int swap_values(struct btrfs_root
*root
, struct btrfs_path
*path
,
2720 struct extent_buffer
*buf
, int slot
)
2722 if (btrfs_header_level(buf
)) {
2723 struct btrfs_key_ptr ptr1
, ptr2
;
2725 read_extent_buffer(buf
, &ptr1
, btrfs_node_key_ptr_offset(slot
),
2726 sizeof(struct btrfs_key_ptr
));
2727 read_extent_buffer(buf
, &ptr2
,
2728 btrfs_node_key_ptr_offset(slot
+ 1),
2729 sizeof(struct btrfs_key_ptr
));
2730 write_extent_buffer(buf
, &ptr1
,
2731 btrfs_node_key_ptr_offset(slot
+ 1),
2732 sizeof(struct btrfs_key_ptr
));
2733 write_extent_buffer(buf
, &ptr2
,
2734 btrfs_node_key_ptr_offset(slot
),
2735 sizeof(struct btrfs_key_ptr
));
2737 struct btrfs_disk_key key
;
2738 btrfs_node_key(buf
, &key
, 0);
2739 btrfs_fixup_low_keys(root
, path
, &key
,
2740 btrfs_header_level(buf
) + 1);
2743 struct btrfs_item
*item1
, *item2
;
2744 struct btrfs_key k1
, k2
;
2745 char *item1_data
, *item2_data
;
2746 u32 item1_offset
, item2_offset
, item1_size
, item2_size
;
2748 item1
= btrfs_item_nr(slot
);
2749 item2
= btrfs_item_nr(slot
+ 1);
2750 btrfs_item_key_to_cpu(buf
, &k1
, slot
);
2751 btrfs_item_key_to_cpu(buf
, &k2
, slot
+ 1);
2752 item1_offset
= btrfs_item_offset(buf
, item1
);
2753 item2_offset
= btrfs_item_offset(buf
, item2
);
2754 item1_size
= btrfs_item_size(buf
, item1
);
2755 item2_size
= btrfs_item_size(buf
, item2
);
2757 item1_data
= malloc(item1_size
);
2760 item2_data
= malloc(item2_size
);
2766 read_extent_buffer(buf
, item1_data
, item1_offset
, item1_size
);
2767 read_extent_buffer(buf
, item2_data
, item2_offset
, item2_size
);
2769 write_extent_buffer(buf
, item1_data
, item2_offset
, item2_size
);
2770 write_extent_buffer(buf
, item2_data
, item1_offset
, item1_size
);
2774 btrfs_set_item_offset(buf
, item1
, item2_offset
);
2775 btrfs_set_item_offset(buf
, item2
, item1_offset
);
2776 btrfs_set_item_size(buf
, item1
, item2_size
);
2777 btrfs_set_item_size(buf
, item2
, item1_size
);
2779 path
->slots
[0] = slot
;
2780 btrfs_set_item_key_unsafe(root
, path
, &k2
);
2781 path
->slots
[0] = slot
+ 1;
2782 btrfs_set_item_key_unsafe(root
, path
, &k1
);
2787 static int fix_key_order(struct btrfs_trans_handle
*trans
,
2788 struct btrfs_root
*root
,
2789 struct btrfs_path
*path
)
2791 struct extent_buffer
*buf
;
2792 struct btrfs_key k1
, k2
;
2794 int level
= path
->lowest_level
;
2797 buf
= path
->nodes
[level
];
2798 for (i
= 0; i
< btrfs_header_nritems(buf
) - 1; i
++) {
2800 btrfs_node_key_to_cpu(buf
, &k1
, i
);
2801 btrfs_node_key_to_cpu(buf
, &k2
, i
+ 1);
2803 btrfs_item_key_to_cpu(buf
, &k1
, i
);
2804 btrfs_item_key_to_cpu(buf
, &k2
, i
+ 1);
2806 if (btrfs_comp_cpu_keys(&k1
, &k2
) < 0)
2808 ret
= swap_values(root
, path
, buf
, i
);
2811 btrfs_mark_buffer_dirty(buf
);
2817 static int delete_bogus_item(struct btrfs_trans_handle
*trans
,
2818 struct btrfs_root
*root
,
2819 struct btrfs_path
*path
,
2820 struct extent_buffer
*buf
, int slot
)
2822 struct btrfs_key key
;
2823 int nritems
= btrfs_header_nritems(buf
);
2825 btrfs_item_key_to_cpu(buf
, &key
, slot
);
2827 /* These are all the keys we can deal with missing. */
2828 if (key
.type
!= BTRFS_DIR_INDEX_KEY
&&
2829 key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
2830 key
.type
!= BTRFS_METADATA_ITEM_KEY
&&
2831 key
.type
!= BTRFS_TREE_BLOCK_REF_KEY
&&
2832 key
.type
!= BTRFS_EXTENT_DATA_REF_KEY
)
2835 printf("Deleting bogus item [%llu,%u,%llu] at slot %d on block %llu\n",
2836 (unsigned long long)key
.objectid
, key
.type
,
2837 (unsigned long long)key
.offset
, slot
, buf
->start
);
2838 memmove_extent_buffer(buf
, btrfs_item_nr_offset(slot
),
2839 btrfs_item_nr_offset(slot
+ 1),
2840 sizeof(struct btrfs_item
) *
2841 (nritems
- slot
- 1));
2842 btrfs_set_header_nritems(buf
, nritems
- 1);
2844 struct btrfs_disk_key disk_key
;
2846 btrfs_item_key(buf
, &disk_key
, 0);
2847 btrfs_fixup_low_keys(root
, path
, &disk_key
, 1);
2849 btrfs_mark_buffer_dirty(buf
);
2853 static int fix_item_offset(struct btrfs_trans_handle
*trans
,
2854 struct btrfs_root
*root
,
2855 struct btrfs_path
*path
)
2857 struct extent_buffer
*buf
;
2861 /* We should only get this for leaves */
2862 BUG_ON(path
->lowest_level
);
2863 buf
= path
->nodes
[0];
2865 for (i
= 0; i
< btrfs_header_nritems(buf
); i
++) {
2866 unsigned int shift
= 0, offset
;
2868 if (i
== 0 && btrfs_item_end_nr(buf
, i
) !=
2869 BTRFS_LEAF_DATA_SIZE(root
)) {
2870 if (btrfs_item_end_nr(buf
, i
) >
2871 BTRFS_LEAF_DATA_SIZE(root
)) {
2872 ret
= delete_bogus_item(trans
, root
, path
,
2876 fprintf(stderr
, "item is off the end of the "
2877 "leaf, can't fix\n");
2881 shift
= BTRFS_LEAF_DATA_SIZE(root
) -
2882 btrfs_item_end_nr(buf
, i
);
2883 } else if (i
> 0 && btrfs_item_end_nr(buf
, i
) !=
2884 btrfs_item_offset_nr(buf
, i
- 1)) {
2885 if (btrfs_item_end_nr(buf
, i
) >
2886 btrfs_item_offset_nr(buf
, i
- 1)) {
2887 ret
= delete_bogus_item(trans
, root
, path
,
2891 fprintf(stderr
, "items overlap, can't fix\n");
2895 shift
= btrfs_item_offset_nr(buf
, i
- 1) -
2896 btrfs_item_end_nr(buf
, i
);
2901 printf("Shifting item nr %d by %u bytes in block %llu\n",
2902 i
, shift
, (unsigned long long)buf
->start
);
2903 offset
= btrfs_item_offset_nr(buf
, i
);
2904 memmove_extent_buffer(buf
,
2905 btrfs_leaf_data(buf
) + offset
+ shift
,
2906 btrfs_leaf_data(buf
) + offset
,
2907 btrfs_item_size_nr(buf
, i
));
2908 btrfs_set_item_offset(buf
, btrfs_item_nr(i
),
2910 btrfs_mark_buffer_dirty(buf
);
2914 * We may have moved things, in which case we want to exit so we don't
2915 * write those changes out. Once we have proper abort functionality in
2916 * progs this can be changed to something nicer.
2923 * Attempt to fix basic block failures. If we can't fix it for whatever reason
2924 * then just return -EIO.
2926 static int try_to_fix_bad_block(struct btrfs_trans_handle
*trans
,
2927 struct btrfs_root
*root
,
2928 struct extent_buffer
*buf
,
2929 enum btrfs_tree_block_status status
)
2931 struct ulist
*roots
;
2932 struct ulist_node
*node
;
2933 struct btrfs_root
*search_root
;
2934 struct btrfs_path
*path
;
2935 struct ulist_iterator iter
;
2936 struct btrfs_key root_key
, key
;
2939 if (status
!= BTRFS_TREE_BLOCK_BAD_KEY_ORDER
&&
2940 status
!= BTRFS_TREE_BLOCK_INVALID_OFFSETS
)
2943 path
= btrfs_alloc_path();
2947 ret
= btrfs_find_all_roots(trans
, root
->fs_info
, buf
->start
,
2950 btrfs_free_path(path
);
2954 ULIST_ITER_INIT(&iter
);
2955 while ((node
= ulist_next(roots
, &iter
))) {
2956 root_key
.objectid
= node
->val
;
2957 root_key
.type
= BTRFS_ROOT_ITEM_KEY
;
2958 root_key
.offset
= (u64
)-1;
2960 search_root
= btrfs_read_fs_root(root
->fs_info
, &root_key
);
2966 record_root_in_trans(trans
, search_root
);
2968 path
->lowest_level
= btrfs_header_level(buf
);
2969 path
->skip_check_block
= 1;
2970 if (path
->lowest_level
)
2971 btrfs_node_key_to_cpu(buf
, &key
, 0);
2973 btrfs_item_key_to_cpu(buf
, &key
, 0);
2974 ret
= btrfs_search_slot(trans
, search_root
, &key
, path
, 0, 1);
2979 if (status
== BTRFS_TREE_BLOCK_BAD_KEY_ORDER
)
2980 ret
= fix_key_order(trans
, search_root
, path
);
2981 else if (status
== BTRFS_TREE_BLOCK_INVALID_OFFSETS
)
2982 ret
= fix_item_offset(trans
, search_root
, path
);
2985 btrfs_release_path(path
);
2988 btrfs_free_path(path
);
2992 static int check_block(struct btrfs_trans_handle
*trans
,
2993 struct btrfs_root
*root
,
2994 struct cache_tree
*extent_cache
,
2995 struct extent_buffer
*buf
, u64 flags
)
2997 struct extent_record
*rec
;
2998 struct cache_extent
*cache
;
2999 struct btrfs_key key
;
3000 enum btrfs_tree_block_status status
;
3004 cache
= lookup_cache_extent(extent_cache
, buf
->start
, buf
->len
);
3007 rec
= container_of(cache
, struct extent_record
, cache
);
3008 rec
->generation
= btrfs_header_generation(buf
);
3010 level
= btrfs_header_level(buf
);
3011 if (btrfs_header_nritems(buf
) > 0) {
3014 btrfs_item_key_to_cpu(buf
, &key
, 0);
3016 btrfs_node_key_to_cpu(buf
, &key
, 0);
3018 rec
->info_objectid
= key
.objectid
;
3020 rec
->info_level
= level
;
3022 if (btrfs_is_leaf(buf
))
3023 status
= btrfs_check_leaf(root
, &rec
->parent_key
, buf
);
3025 status
= btrfs_check_node(root
, &rec
->parent_key
, buf
);
3027 if (status
!= BTRFS_TREE_BLOCK_CLEAN
) {
3029 status
= try_to_fix_bad_block(trans
, root
, buf
,
3031 if (status
!= BTRFS_TREE_BLOCK_CLEAN
) {
3033 fprintf(stderr
, "bad block %llu\n",
3034 (unsigned long long)buf
->start
);
3037 * Signal to callers we need to start the scan over
3038 * again since we'll have cow'ed blocks.
3043 rec
->content_checked
= 1;
3044 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
)
3045 rec
->owner_ref_checked
= 1;
3047 ret
= check_owner_ref(root
, rec
, buf
);
3049 rec
->owner_ref_checked
= 1;
3053 maybe_free_extent_rec(extent_cache
, rec
);
3057 static struct tree_backref
*find_tree_backref(struct extent_record
*rec
,
3058 u64 parent
, u64 root
)
3060 struct list_head
*cur
= rec
->backrefs
.next
;
3061 struct extent_backref
*node
;
3062 struct tree_backref
*back
;
3064 while(cur
!= &rec
->backrefs
) {
3065 node
= list_entry(cur
, struct extent_backref
, list
);
3069 back
= (struct tree_backref
*)node
;
3071 if (!node
->full_backref
)
3073 if (parent
== back
->parent
)
3076 if (node
->full_backref
)
3078 if (back
->root
== root
)
3085 static struct tree_backref
*alloc_tree_backref(struct extent_record
*rec
,
3086 u64 parent
, u64 root
)
3088 struct tree_backref
*ref
= malloc(sizeof(*ref
));
3089 memset(&ref
->node
, 0, sizeof(ref
->node
));
3091 ref
->parent
= parent
;
3092 ref
->node
.full_backref
= 1;
3095 ref
->node
.full_backref
= 0;
3097 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
3102 static struct data_backref
*find_data_backref(struct extent_record
*rec
,
3103 u64 parent
, u64 root
,
3104 u64 owner
, u64 offset
,
3106 u64 disk_bytenr
, u64 bytes
)
3108 struct list_head
*cur
= rec
->backrefs
.next
;
3109 struct extent_backref
*node
;
3110 struct data_backref
*back
;
3112 while(cur
!= &rec
->backrefs
) {
3113 node
= list_entry(cur
, struct extent_backref
, list
);
3117 back
= (struct data_backref
*)node
;
3119 if (!node
->full_backref
)
3121 if (parent
== back
->parent
)
3124 if (node
->full_backref
)
3126 if (back
->root
== root
&& back
->owner
== owner
&&
3127 back
->offset
== offset
) {
3128 if (found_ref
&& node
->found_ref
&&
3129 (back
->bytes
!= bytes
||
3130 back
->disk_bytenr
!= disk_bytenr
))
3139 static struct data_backref
*alloc_data_backref(struct extent_record
*rec
,
3140 u64 parent
, u64 root
,
3141 u64 owner
, u64 offset
,
3144 struct data_backref
*ref
= malloc(sizeof(*ref
));
3145 memset(&ref
->node
, 0, sizeof(ref
->node
));
3146 ref
->node
.is_data
= 1;
3149 ref
->parent
= parent
;
3152 ref
->node
.full_backref
= 1;
3156 ref
->offset
= offset
;
3157 ref
->node
.full_backref
= 0;
3159 ref
->bytes
= max_size
;
3162 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
3163 if (max_size
> rec
->max_size
)
3164 rec
->max_size
= max_size
;
3168 static int add_extent_rec(struct cache_tree
*extent_cache
,
3169 struct btrfs_key
*parent_key
, u64 parent_gen
,
3170 u64 start
, u64 nr
, u64 extent_item_refs
,
3171 int is_root
, int inc_ref
, int set_checked
,
3172 int metadata
, int extent_rec
, u64 max_size
)
3174 struct extent_record
*rec
;
3175 struct cache_extent
*cache
;
3179 cache
= lookup_cache_extent(extent_cache
, start
, nr
);
3181 rec
= container_of(cache
, struct extent_record
, cache
);
3185 rec
->nr
= max(nr
, max_size
);
3188 * We need to make sure to reset nr to whatever the extent
3189 * record says was the real size, this way we can compare it to
3193 if (start
!= rec
->start
|| rec
->found_rec
) {
3194 struct extent_record
*tmp
;
3197 if (list_empty(&rec
->list
))
3198 list_add_tail(&rec
->list
,
3199 &duplicate_extents
);
3202 * We have to do this song and dance in case we
3203 * find an extent record that falls inside of
3204 * our current extent record but does not have
3205 * the same objectid.
3207 tmp
= malloc(sizeof(*tmp
));
3211 tmp
->max_size
= max_size
;
3214 tmp
->metadata
= metadata
;
3215 tmp
->extent_item_refs
= extent_item_refs
;
3216 INIT_LIST_HEAD(&tmp
->list
);
3217 list_add_tail(&tmp
->list
, &rec
->dups
);
3218 rec
->num_duplicates
++;
3225 if (extent_item_refs
&& !dup
) {
3226 if (rec
->extent_item_refs
) {
3227 fprintf(stderr
, "block %llu rec "
3228 "extent_item_refs %llu, passed %llu\n",
3229 (unsigned long long)start
,
3230 (unsigned long long)
3231 rec
->extent_item_refs
,
3232 (unsigned long long)extent_item_refs
);
3234 rec
->extent_item_refs
= extent_item_refs
;
3239 rec
->content_checked
= 1;
3240 rec
->owner_ref_checked
= 1;
3244 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
3246 rec
->parent_generation
= parent_gen
;
3248 if (rec
->max_size
< max_size
)
3249 rec
->max_size
= max_size
;
3251 maybe_free_extent_rec(extent_cache
, rec
);
3254 rec
= malloc(sizeof(*rec
));
3256 rec
->max_size
= max_size
;
3257 rec
->nr
= max(nr
, max_size
);
3258 rec
->found_rec
= !!extent_rec
;
3259 rec
->content_checked
= 0;
3260 rec
->owner_ref_checked
= 0;
3261 rec
->num_duplicates
= 0;
3262 rec
->metadata
= metadata
;
3263 INIT_LIST_HEAD(&rec
->backrefs
);
3264 INIT_LIST_HEAD(&rec
->dups
);
3265 INIT_LIST_HEAD(&rec
->list
);
3277 if (extent_item_refs
)
3278 rec
->extent_item_refs
= extent_item_refs
;
3280 rec
->extent_item_refs
= 0;
3283 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
3285 memset(&rec
->parent_key
, 0, sizeof(*parent_key
));
3288 rec
->parent_generation
= parent_gen
;
3290 rec
->parent_generation
= 0;
3292 rec
->cache
.start
= start
;
3293 rec
->cache
.size
= nr
;
3294 ret
= insert_cache_extent(extent_cache
, &rec
->cache
);
3298 rec
->content_checked
= 1;
3299 rec
->owner_ref_checked
= 1;
3304 static int add_tree_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
3305 u64 parent
, u64 root
, int found_ref
)
3307 struct extent_record
*rec
;
3308 struct tree_backref
*back
;
3309 struct cache_extent
*cache
;
3311 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
3313 add_extent_rec(extent_cache
, NULL
, 0, bytenr
,
3314 1, 0, 0, 0, 0, 1, 0, 0);
3315 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
3320 rec
= container_of(cache
, struct extent_record
, cache
);
3321 if (rec
->start
!= bytenr
) {
3325 back
= find_tree_backref(rec
, parent
, root
);
3327 back
= alloc_tree_backref(rec
, parent
, root
);
3330 if (back
->node
.found_ref
) {
3331 fprintf(stderr
, "Extent back ref already exists "
3332 "for %llu parent %llu root %llu \n",
3333 (unsigned long long)bytenr
,
3334 (unsigned long long)parent
,
3335 (unsigned long long)root
);
3337 back
->node
.found_ref
= 1;
3339 if (back
->node
.found_extent_tree
) {
3340 fprintf(stderr
, "Extent back ref already exists "
3341 "for %llu parent %llu root %llu \n",
3342 (unsigned long long)bytenr
,
3343 (unsigned long long)parent
,
3344 (unsigned long long)root
);
3346 back
->node
.found_extent_tree
= 1;
3348 maybe_free_extent_rec(extent_cache
, rec
);
3352 static int add_data_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
3353 u64 parent
, u64 root
, u64 owner
, u64 offset
,
3354 u32 num_refs
, int found_ref
, u64 max_size
)
3356 struct extent_record
*rec
;
3357 struct data_backref
*back
;
3358 struct cache_extent
*cache
;
3360 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
3362 add_extent_rec(extent_cache
, NULL
, 0, bytenr
, 1, 0, 0, 0, 0,
3364 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
3369 rec
= container_of(cache
, struct extent_record
, cache
);
3370 if (rec
->max_size
< max_size
)
3371 rec
->max_size
= max_size
;
3374 * If found_ref is set then max_size is the real size and must match the
3375 * existing refs. So if we have already found a ref then we need to
3376 * make sure that this ref matches the existing one, otherwise we need
3377 * to add a new backref so we can notice that the backrefs don't match
3378 * and we need to figure out who is telling the truth. This is to
3379 * account for that awful fsync bug I introduced where we'd end up with
3380 * a btrfs_file_extent_item that would have its length include multiple
3381 * prealloc extents or point inside of a prealloc extent.
3383 back
= find_data_backref(rec
, parent
, root
, owner
, offset
, found_ref
,
3386 back
= alloc_data_backref(rec
, parent
, root
, owner
, offset
,
3390 BUG_ON(num_refs
!= 1);
3391 if (back
->node
.found_ref
)
3392 BUG_ON(back
->bytes
!= max_size
);
3393 back
->node
.found_ref
= 1;
3394 back
->found_ref
+= 1;
3395 back
->bytes
= max_size
;
3396 back
->disk_bytenr
= bytenr
;
3398 rec
->content_checked
= 1;
3399 rec
->owner_ref_checked
= 1;
3401 if (back
->node
.found_extent_tree
) {
3402 fprintf(stderr
, "Extent back ref already exists "
3403 "for %llu parent %llu root %llu "
3404 "owner %llu offset %llu num_refs %lu\n",
3405 (unsigned long long)bytenr
,
3406 (unsigned long long)parent
,
3407 (unsigned long long)root
,
3408 (unsigned long long)owner
,
3409 (unsigned long long)offset
,
3410 (unsigned long)num_refs
);
3412 back
->num_refs
= num_refs
;
3413 back
->node
.found_extent_tree
= 1;
3415 maybe_free_extent_rec(extent_cache
, rec
);
3419 static int add_pending(struct cache_tree
*pending
,
3420 struct cache_tree
*seen
, u64 bytenr
, u32 size
)
3423 ret
= add_cache_extent(seen
, bytenr
, size
);
3426 add_cache_extent(pending
, bytenr
, size
);
3430 static int pick_next_pending(struct cache_tree
*pending
,
3431 struct cache_tree
*reada
,
3432 struct cache_tree
*nodes
,
3433 u64 last
, struct block_info
*bits
, int bits_nr
,
3436 unsigned long node_start
= last
;
3437 struct cache_extent
*cache
;
3440 cache
= search_cache_extent(reada
, 0);
3442 bits
[0].start
= cache
->start
;
3443 bits
[0].size
= cache
->size
;
3448 if (node_start
> 32768)
3449 node_start
-= 32768;
3451 cache
= search_cache_extent(nodes
, node_start
);
3453 cache
= search_cache_extent(nodes
, 0);
3456 cache
= search_cache_extent(pending
, 0);
3461 bits
[ret
].start
= cache
->start
;
3462 bits
[ret
].size
= cache
->size
;
3463 cache
= next_cache_extent(cache
);
3465 } while (cache
&& ret
< bits_nr
);
3471 bits
[ret
].start
= cache
->start
;
3472 bits
[ret
].size
= cache
->size
;
3473 cache
= next_cache_extent(cache
);
3475 } while (cache
&& ret
< bits_nr
);
3477 if (bits_nr
- ret
> 8) {
3478 u64 lookup
= bits
[0].start
+ bits
[0].size
;
3479 struct cache_extent
*next
;
3480 next
= search_cache_extent(pending
, lookup
);
3482 if (next
->start
- lookup
> 32768)
3484 bits
[ret
].start
= next
->start
;
3485 bits
[ret
].size
= next
->size
;
3486 lookup
= next
->start
+ next
->size
;
3490 next
= next_cache_extent(next
);
3498 static void free_chunk_record(struct cache_extent
*cache
)
3500 struct chunk_record
*rec
;
3502 rec
= container_of(cache
, struct chunk_record
, cache
);
3503 list_del_init(&rec
->list
);
3504 list_del_init(&rec
->dextents
);
3508 void free_chunk_cache_tree(struct cache_tree
*chunk_cache
)
3510 cache_tree_free_extents(chunk_cache
, free_chunk_record
);
3513 static void free_device_record(struct rb_node
*node
)
3515 struct device_record
*rec
;
3517 rec
= container_of(node
, struct device_record
, node
);
3521 FREE_RB_BASED_TREE(device_cache
, free_device_record
);
3523 int insert_block_group_record(struct block_group_tree
*tree
,
3524 struct block_group_record
*bg_rec
)
3528 ret
= insert_cache_extent(&tree
->tree
, &bg_rec
->cache
);
3532 list_add_tail(&bg_rec
->list
, &tree
->block_groups
);
3536 static void free_block_group_record(struct cache_extent
*cache
)
3538 struct block_group_record
*rec
;
3540 rec
= container_of(cache
, struct block_group_record
, cache
);
3541 list_del_init(&rec
->list
);
3545 void free_block_group_tree(struct block_group_tree
*tree
)
3547 cache_tree_free_extents(&tree
->tree
, free_block_group_record
);
3550 int insert_device_extent_record(struct device_extent_tree
*tree
,
3551 struct device_extent_record
*de_rec
)
3556 * Device extent is a bit different from the other extents, because
3557 * the extents which belong to the different devices may have the
3558 * same start and size, so we need use the special extent cache
3559 * search/insert functions.
3561 ret
= insert_cache_extent2(&tree
->tree
, &de_rec
->cache
);
3565 list_add_tail(&de_rec
->chunk_list
, &tree
->no_chunk_orphans
);
3566 list_add_tail(&de_rec
->device_list
, &tree
->no_device_orphans
);
3570 static void free_device_extent_record(struct cache_extent
*cache
)
3572 struct device_extent_record
*rec
;
3574 rec
= container_of(cache
, struct device_extent_record
, cache
);
3575 if (!list_empty(&rec
->chunk_list
))
3576 list_del_init(&rec
->chunk_list
);
3577 if (!list_empty(&rec
->device_list
))
3578 list_del_init(&rec
->device_list
);
3582 void free_device_extent_tree(struct device_extent_tree
*tree
)
3584 cache_tree_free_extents(&tree
->tree
, free_device_extent_record
);
3587 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3588 static int process_extent_ref_v0(struct cache_tree
*extent_cache
,
3589 struct extent_buffer
*leaf
, int slot
)
3591 struct btrfs_extent_ref_v0
*ref0
;
3592 struct btrfs_key key
;
3594 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
3595 ref0
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_ref_v0
);
3596 if (btrfs_ref_objectid_v0(leaf
, ref0
) < BTRFS_FIRST_FREE_OBJECTID
) {
3597 add_tree_backref(extent_cache
, key
.objectid
, key
.offset
, 0, 0);
3599 add_data_backref(extent_cache
, key
.objectid
, key
.offset
, 0,
3600 0, 0, btrfs_ref_count_v0(leaf
, ref0
), 0, 0);
3606 struct chunk_record
*btrfs_new_chunk_record(struct extent_buffer
*leaf
,
3607 struct btrfs_key
*key
,
3610 struct btrfs_chunk
*ptr
;
3611 struct chunk_record
*rec
;
3614 ptr
= btrfs_item_ptr(leaf
, slot
, struct btrfs_chunk
);
3615 num_stripes
= btrfs_chunk_num_stripes(leaf
, ptr
);
3617 rec
= malloc(btrfs_chunk_record_size(num_stripes
));
3619 fprintf(stderr
, "memory allocation failed\n");
3623 memset(rec
, 0, btrfs_chunk_record_size(num_stripes
));
3625 INIT_LIST_HEAD(&rec
->list
);
3626 INIT_LIST_HEAD(&rec
->dextents
);
3629 rec
->cache
.start
= key
->offset
;
3630 rec
->cache
.size
= btrfs_chunk_length(leaf
, ptr
);
3632 rec
->generation
= btrfs_header_generation(leaf
);
3634 rec
->objectid
= key
->objectid
;
3635 rec
->type
= key
->type
;
3636 rec
->offset
= key
->offset
;
3638 rec
->length
= rec
->cache
.size
;
3639 rec
->owner
= btrfs_chunk_owner(leaf
, ptr
);
3640 rec
->stripe_len
= btrfs_chunk_stripe_len(leaf
, ptr
);
3641 rec
->type_flags
= btrfs_chunk_type(leaf
, ptr
);
3642 rec
->io_width
= btrfs_chunk_io_width(leaf
, ptr
);
3643 rec
->io_align
= btrfs_chunk_io_align(leaf
, ptr
);
3644 rec
->sector_size
= btrfs_chunk_sector_size(leaf
, ptr
);
3645 rec
->num_stripes
= num_stripes
;
3646 rec
->sub_stripes
= btrfs_chunk_sub_stripes(leaf
, ptr
);
3648 for (i
= 0; i
< rec
->num_stripes
; ++i
) {
3649 rec
->stripes
[i
].devid
=
3650 btrfs_stripe_devid_nr(leaf
, ptr
, i
);
3651 rec
->stripes
[i
].offset
=
3652 btrfs_stripe_offset_nr(leaf
, ptr
, i
);
3653 read_extent_buffer(leaf
, rec
->stripes
[i
].dev_uuid
,
3654 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr
, i
),
3661 static int process_chunk_item(struct cache_tree
*chunk_cache
,
3662 struct btrfs_key
*key
, struct extent_buffer
*eb
,
3665 struct chunk_record
*rec
;
3668 rec
= btrfs_new_chunk_record(eb
, key
, slot
);
3669 ret
= insert_cache_extent(chunk_cache
, &rec
->cache
);
3671 fprintf(stderr
, "Chunk[%llu, %llu] existed.\n",
3672 rec
->offset
, rec
->length
);
3679 static int process_device_item(struct rb_root
*dev_cache
,
3680 struct btrfs_key
*key
, struct extent_buffer
*eb
, int slot
)
3682 struct btrfs_dev_item
*ptr
;
3683 struct device_record
*rec
;
3686 ptr
= btrfs_item_ptr(eb
,
3687 slot
, struct btrfs_dev_item
);
3689 rec
= malloc(sizeof(*rec
));
3691 fprintf(stderr
, "memory allocation failed\n");
3695 rec
->devid
= key
->offset
;
3696 rec
->generation
= btrfs_header_generation(eb
);
3698 rec
->objectid
= key
->objectid
;
3699 rec
->type
= key
->type
;
3700 rec
->offset
= key
->offset
;
3702 rec
->devid
= btrfs_device_id(eb
, ptr
);
3703 rec
->total_byte
= btrfs_device_total_bytes(eb
, ptr
);
3704 rec
->byte_used
= btrfs_device_bytes_used(eb
, ptr
);
3706 ret
= rb_insert(dev_cache
, &rec
->node
, device_record_compare
);
3708 fprintf(stderr
, "Device[%llu] existed.\n", rec
->devid
);
3715 struct block_group_record
*
3716 btrfs_new_block_group_record(struct extent_buffer
*leaf
, struct btrfs_key
*key
,
3719 struct btrfs_block_group_item
*ptr
;
3720 struct block_group_record
*rec
;
3722 rec
= malloc(sizeof(*rec
));
3724 fprintf(stderr
, "memory allocation failed\n");
3727 memset(rec
, 0, sizeof(*rec
));
3729 rec
->cache
.start
= key
->objectid
;
3730 rec
->cache
.size
= key
->offset
;
3732 rec
->generation
= btrfs_header_generation(leaf
);
3734 rec
->objectid
= key
->objectid
;
3735 rec
->type
= key
->type
;
3736 rec
->offset
= key
->offset
;
3738 ptr
= btrfs_item_ptr(leaf
, slot
, struct btrfs_block_group_item
);
3739 rec
->flags
= btrfs_disk_block_group_flags(leaf
, ptr
);
3741 INIT_LIST_HEAD(&rec
->list
);
3746 static int process_block_group_item(struct block_group_tree
*block_group_cache
,
3747 struct btrfs_key
*key
,
3748 struct extent_buffer
*eb
, int slot
)
3750 struct block_group_record
*rec
;
3753 rec
= btrfs_new_block_group_record(eb
, key
, slot
);
3754 ret
= insert_block_group_record(block_group_cache
, rec
);
3756 fprintf(stderr
, "Block Group[%llu, %llu] existed.\n",
3757 rec
->objectid
, rec
->offset
);
3764 struct device_extent_record
*
3765 btrfs_new_device_extent_record(struct extent_buffer
*leaf
,
3766 struct btrfs_key
*key
, int slot
)
3768 struct device_extent_record
*rec
;
3769 struct btrfs_dev_extent
*ptr
;
3771 rec
= malloc(sizeof(*rec
));
3773 fprintf(stderr
, "memory allocation failed\n");
3776 memset(rec
, 0, sizeof(*rec
));
3778 rec
->cache
.objectid
= key
->objectid
;
3779 rec
->cache
.start
= key
->offset
;
3781 rec
->generation
= btrfs_header_generation(leaf
);
3783 rec
->objectid
= key
->objectid
;
3784 rec
->type
= key
->type
;
3785 rec
->offset
= key
->offset
;
3787 ptr
= btrfs_item_ptr(leaf
, slot
, struct btrfs_dev_extent
);
3788 rec
->chunk_objecteid
=
3789 btrfs_dev_extent_chunk_objectid(leaf
, ptr
);
3791 btrfs_dev_extent_chunk_offset(leaf
, ptr
);
3792 rec
->length
= btrfs_dev_extent_length(leaf
, ptr
);
3793 rec
->cache
.size
= rec
->length
;
3795 INIT_LIST_HEAD(&rec
->chunk_list
);
3796 INIT_LIST_HEAD(&rec
->device_list
);
3802 process_device_extent_item(struct device_extent_tree
*dev_extent_cache
,
3803 struct btrfs_key
*key
, struct extent_buffer
*eb
,
3806 struct device_extent_record
*rec
;
3809 rec
= btrfs_new_device_extent_record(eb
, key
, slot
);
3810 ret
= insert_device_extent_record(dev_extent_cache
, rec
);
3813 "Device extent[%llu, %llu, %llu] existed.\n",
3814 rec
->objectid
, rec
->offset
, rec
->length
);
3821 static int process_extent_item(struct btrfs_root
*root
,
3822 struct cache_tree
*extent_cache
,
3823 struct extent_buffer
*eb
, int slot
)
3825 struct btrfs_extent_item
*ei
;
3826 struct btrfs_extent_inline_ref
*iref
;
3827 struct btrfs_extent_data_ref
*dref
;
3828 struct btrfs_shared_data_ref
*sref
;
3829 struct btrfs_key key
;
3833 u32 item_size
= btrfs_item_size_nr(eb
, slot
);
3839 btrfs_item_key_to_cpu(eb
, &key
, slot
);
3841 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
3843 num_bytes
= root
->leafsize
;
3845 num_bytes
= key
.offset
;
3848 if (item_size
< sizeof(*ei
)) {
3849 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3850 struct btrfs_extent_item_v0
*ei0
;
3851 BUG_ON(item_size
!= sizeof(*ei0
));
3852 ei0
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item_v0
);
3853 refs
= btrfs_extent_refs_v0(eb
, ei0
);
3857 return add_extent_rec(extent_cache
, NULL
, 0, key
.objectid
,
3858 num_bytes
, refs
, 0, 0, 0, metadata
, 1,
3862 ei
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item
);
3863 refs
= btrfs_extent_refs(eb
, ei
);
3865 add_extent_rec(extent_cache
, NULL
, 0, key
.objectid
, num_bytes
,
3866 refs
, 0, 0, 0, metadata
, 1, num_bytes
);
3868 ptr
= (unsigned long)(ei
+ 1);
3869 if (btrfs_extent_flags(eb
, ei
) & BTRFS_EXTENT_FLAG_TREE_BLOCK
&&
3870 key
.type
== BTRFS_EXTENT_ITEM_KEY
)
3871 ptr
+= sizeof(struct btrfs_tree_block_info
);
3873 end
= (unsigned long)ei
+ item_size
;
3875 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
3876 type
= btrfs_extent_inline_ref_type(eb
, iref
);
3877 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
3879 case BTRFS_TREE_BLOCK_REF_KEY
:
3880 add_tree_backref(extent_cache
, key
.objectid
,
3883 case BTRFS_SHARED_BLOCK_REF_KEY
:
3884 add_tree_backref(extent_cache
, key
.objectid
,
3887 case BTRFS_EXTENT_DATA_REF_KEY
:
3888 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
3889 add_data_backref(extent_cache
, key
.objectid
, 0,
3890 btrfs_extent_data_ref_root(eb
, dref
),
3891 btrfs_extent_data_ref_objectid(eb
,
3893 btrfs_extent_data_ref_offset(eb
, dref
),
3894 btrfs_extent_data_ref_count(eb
, dref
),
3897 case BTRFS_SHARED_DATA_REF_KEY
:
3898 sref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
3899 add_data_backref(extent_cache
, key
.objectid
, offset
,
3901 btrfs_shared_data_ref_count(eb
, sref
),
3905 fprintf(stderr
, "corrupt extent record: key %Lu %u %Lu\n",
3906 key
.objectid
, key
.type
, num_bytes
);
3909 ptr
+= btrfs_extent_inline_ref_size(type
);
3916 static int check_cache_range(struct btrfs_root
*root
,
3917 struct btrfs_block_group_cache
*cache
,
3918 u64 offset
, u64 bytes
)
3920 struct btrfs_free_space
*entry
;
3926 for (i
= 0; i
< BTRFS_SUPER_MIRROR_MAX
; i
++) {
3927 bytenr
= btrfs_sb_offset(i
);
3928 ret
= btrfs_rmap_block(&root
->fs_info
->mapping_tree
,
3929 cache
->key
.objectid
, bytenr
, 0,
3930 &logical
, &nr
, &stripe_len
);
3935 if (logical
[nr
] + stripe_len
<= offset
)
3937 if (offset
+ bytes
<= logical
[nr
])
3939 if (logical
[nr
] == offset
) {
3940 if (stripe_len
>= bytes
) {
3944 bytes
-= stripe_len
;
3945 offset
+= stripe_len
;
3946 } else if (logical
[nr
] < offset
) {
3947 if (logical
[nr
] + stripe_len
>=
3952 bytes
= (offset
+ bytes
) -
3953 (logical
[nr
] + stripe_len
);
3954 offset
= logical
[nr
] + stripe_len
;
3957 * Could be tricky, the super may land in the
3958 * middle of the area we're checking. First
3959 * check the easiest case, it's at the end.
3961 if (logical
[nr
] + stripe_len
>=
3963 bytes
= logical
[nr
] - offset
;
3967 /* Check the left side */
3968 ret
= check_cache_range(root
, cache
,
3970 logical
[nr
] - offset
);
3976 /* Now we continue with the right side */
3977 bytes
= (offset
+ bytes
) -
3978 (logical
[nr
] + stripe_len
);
3979 offset
= logical
[nr
] + stripe_len
;
3986 entry
= btrfs_find_free_space(cache
->free_space_ctl
, offset
, bytes
);
3988 fprintf(stderr
, "There is no free space entry for %Lu-%Lu\n",
3989 offset
, offset
+bytes
);
3993 if (entry
->offset
!= offset
) {
3994 fprintf(stderr
, "Wanted offset %Lu, found %Lu\n", offset
,
3999 if (entry
->bytes
!= bytes
) {
4000 fprintf(stderr
, "Wanted bytes %Lu, found %Lu for off %Lu\n",
4001 bytes
, entry
->bytes
, offset
);
4005 unlink_free_space(cache
->free_space_ctl
, entry
);
4010 static int verify_space_cache(struct btrfs_root
*root
,
4011 struct btrfs_block_group_cache
*cache
)
4013 struct btrfs_path
*path
;
4014 struct extent_buffer
*leaf
;
4015 struct btrfs_key key
;
4019 path
= btrfs_alloc_path();
4023 root
= root
->fs_info
->extent_root
;
4025 last
= max_t(u64
, cache
->key
.objectid
, BTRFS_SUPER_INFO_OFFSET
);
4027 key
.objectid
= last
;
4029 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
4031 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
4036 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
4037 ret
= btrfs_next_leaf(root
, path
);
4045 leaf
= path
->nodes
[0];
4046 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
4047 if (key
.objectid
>= cache
->key
.offset
+ cache
->key
.objectid
)
4049 if (key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
4050 key
.type
!= BTRFS_METADATA_ITEM_KEY
) {
4055 if (last
== key
.objectid
) {
4056 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
)
4057 last
= key
.objectid
+ key
.offset
;
4059 last
= key
.objectid
+ root
->leafsize
;
4064 ret
= check_cache_range(root
, cache
, last
,
4065 key
.objectid
- last
);
4068 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
)
4069 last
= key
.objectid
+ key
.offset
;
4071 last
= key
.objectid
+ root
->leafsize
;
4075 if (last
< cache
->key
.objectid
+ cache
->key
.offset
)
4076 ret
= check_cache_range(root
, cache
, last
,
4077 cache
->key
.objectid
+
4078 cache
->key
.offset
- last
);
4081 btrfs_free_path(path
);
4084 !RB_EMPTY_ROOT(&cache
->free_space_ctl
->free_space_offset
)) {
4085 fprintf(stderr
, "There are still entries left in the space "
4093 static int check_space_cache(struct btrfs_root
*root
)
4095 struct btrfs_block_group_cache
*cache
;
4096 u64 start
= BTRFS_SUPER_INFO_OFFSET
+ BTRFS_SUPER_INFO_SIZE
;
4100 if (btrfs_super_cache_generation(root
->fs_info
->super_copy
) != -1ULL &&
4101 btrfs_super_generation(root
->fs_info
->super_copy
) !=
4102 btrfs_super_cache_generation(root
->fs_info
->super_copy
)) {
4103 printf("cache and super generation don't match, space cache "
4104 "will be invalidated\n");
4109 cache
= btrfs_lookup_first_block_group(root
->fs_info
, start
);
4113 start
= cache
->key
.objectid
+ cache
->key
.offset
;
4114 if (!cache
->free_space_ctl
) {
4115 if (btrfs_init_free_space_ctl(cache
,
4116 root
->sectorsize
)) {
4121 btrfs_remove_free_space_cache(cache
);
4124 ret
= load_free_space_cache(root
->fs_info
, cache
);
4128 ret
= verify_space_cache(root
, cache
);
4130 fprintf(stderr
, "cache appears valid but isnt %Lu\n",
4131 cache
->key
.objectid
);
4136 return error
? -EINVAL
: 0;
4139 static int read_extent_data(struct btrfs_root
*root
, char *data
,
4140 u64 logical
, u64
*len
, int mirror
)
4143 struct btrfs_multi_bio
*multi
= NULL
;
4144 struct btrfs_fs_info
*info
= root
->fs_info
;
4145 struct btrfs_device
*device
;
4149 ret
= btrfs_map_block(&info
->mapping_tree
, READ
, logical
, len
,
4150 &multi
, mirror
, NULL
);
4152 fprintf(stderr
, "Couldn't map the block %llu\n",
4156 device
= multi
->stripes
[0].dev
;
4158 if (device
->fd
== 0)
4163 ret
= pread64(device
->fd
, data
, *len
, multi
->stripes
[0].physical
);
4173 static int check_extent_csums(struct btrfs_root
*root
, u64 bytenr
,
4174 u64 num_bytes
, unsigned long leaf_offset
,
4175 struct extent_buffer
*eb
) {
4178 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
4180 unsigned long csum_offset
;
4184 u64 data_checked
= 0;
4190 if (num_bytes
% root
->sectorsize
)
4193 data
= malloc(num_bytes
);
4197 while (offset
< num_bytes
) {
4200 read_len
= num_bytes
- offset
;
4201 /* read as much space once a time */
4202 ret
= read_extent_data(root
, data
+ offset
,
4203 bytenr
+ offset
, &read_len
, mirror
);
4207 /* verify every 4k data's checksum */
4208 while (data_checked
< read_len
) {
4210 tmp
= offset
+ data_checked
;
4212 csum
= btrfs_csum_data(NULL
, (char *)data
+ tmp
,
4213 csum
, root
->sectorsize
);
4214 btrfs_csum_final(csum
, (char *)&csum
);
4216 csum_offset
= leaf_offset
+
4217 tmp
/ root
->sectorsize
* csum_size
;
4218 read_extent_buffer(eb
, (char *)&csum_expected
,
4219 csum_offset
, csum_size
);
4220 /* try another mirror */
4221 if (csum
!= csum_expected
) {
4222 fprintf(stderr
, "mirror %d bytenr %llu csum %u expected csum %u\n",
4223 mirror
, bytenr
+ tmp
,
4224 csum
, csum_expected
);
4225 num_copies
= btrfs_num_copies(
4226 &root
->fs_info
->mapping_tree
,
4228 if (mirror
< num_copies
- 1) {
4233 data_checked
+= root
->sectorsize
;
4242 static int check_extent_exists(struct btrfs_root
*root
, u64 bytenr
,
4245 struct btrfs_path
*path
;
4246 struct extent_buffer
*leaf
;
4247 struct btrfs_key key
;
4250 path
= btrfs_alloc_path();
4252 fprintf(stderr
, "Error allocing path\n");
4256 key
.objectid
= bytenr
;
4257 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
4258 key
.offset
= (u64
)-1;
4261 ret
= btrfs_search_slot(NULL
, root
->fs_info
->extent_root
, &key
, path
,
4264 fprintf(stderr
, "Error looking up extent record %d\n", ret
);
4265 btrfs_free_path(path
);
4268 if (path
->slots
[0] > 0) {
4271 ret
= btrfs_prev_leaf(root
, path
);
4274 } else if (ret
> 0) {
4281 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
4284 * Block group items come before extent items if they have the same
4285 * bytenr, so walk back one more just in case. Dear future traveler,
4286 * first congrats on mastering time travel. Now if it's not too much
4287 * trouble could you go back to 2006 and tell Chris to make the
4288 * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
4289 * EXTENT_ITEM_KEY please?
4291 while (key
.type
> BTRFS_EXTENT_ITEM_KEY
) {
4292 if (path
->slots
[0] > 0) {
4295 ret
= btrfs_prev_leaf(root
, path
);
4298 } else if (ret
> 0) {
4303 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
4307 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
4308 ret
= btrfs_next_leaf(root
, path
);
4310 fprintf(stderr
, "Error going to next leaf "
4312 btrfs_free_path(path
);
4318 leaf
= path
->nodes
[0];
4319 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
4320 if (key
.type
!= BTRFS_EXTENT_ITEM_KEY
) {
4324 if (key
.objectid
+ key
.offset
< bytenr
) {
4328 if (key
.objectid
> bytenr
+ num_bytes
)
4331 if (key
.objectid
== bytenr
) {
4332 if (key
.offset
>= num_bytes
) {
4336 num_bytes
-= key
.offset
;
4337 bytenr
+= key
.offset
;
4338 } else if (key
.objectid
< bytenr
) {
4339 if (key
.objectid
+ key
.offset
>= bytenr
+ num_bytes
) {
4343 num_bytes
= (bytenr
+ num_bytes
) -
4344 (key
.objectid
+ key
.offset
);
4345 bytenr
= key
.objectid
+ key
.offset
;
4347 if (key
.objectid
+ key
.offset
< bytenr
+ num_bytes
) {
4348 u64 new_start
= key
.objectid
+ key
.offset
;
4349 u64 new_bytes
= bytenr
+ num_bytes
- new_start
;
4352 * Weird case, the extent is in the middle of
4353 * our range, we'll have to search one side
4354 * and then the other. Not sure if this happens
4355 * in real life, but no harm in coding it up
4356 * anyway just in case.
4358 btrfs_release_path(path
);
4359 ret
= check_extent_exists(root
, new_start
,
4362 fprintf(stderr
, "Right section didn't "
4366 num_bytes
= key
.objectid
- bytenr
;
4369 num_bytes
= key
.objectid
- bytenr
;
4376 if (num_bytes
&& !ret
) {
4377 fprintf(stderr
, "There are no extents for csum range "
4378 "%Lu-%Lu\n", bytenr
, bytenr
+num_bytes
);
4382 btrfs_free_path(path
);
4386 static int check_csums(struct btrfs_root
*root
)
4388 struct btrfs_path
*path
;
4389 struct extent_buffer
*leaf
;
4390 struct btrfs_key key
;
4391 u64 offset
= 0, num_bytes
= 0;
4392 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
4396 unsigned long leaf_offset
;
4398 root
= root
->fs_info
->csum_root
;
4399 if (!extent_buffer_uptodate(root
->node
)) {
4400 fprintf(stderr
, "No valid csum tree found\n");
4404 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
4405 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
4408 path
= btrfs_alloc_path();
4412 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
4414 fprintf(stderr
, "Error searching csum tree %d\n", ret
);
4415 btrfs_free_path(path
);
4419 if (ret
> 0 && path
->slots
[0])
4424 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
4425 ret
= btrfs_next_leaf(root
, path
);
4427 fprintf(stderr
, "Error going to next leaf "
4434 leaf
= path
->nodes
[0];
4436 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
4437 if (key
.type
!= BTRFS_EXTENT_CSUM_KEY
) {
4442 data_len
= (btrfs_item_size_nr(leaf
, path
->slots
[0]) /
4443 csum_size
) * root
->sectorsize
;
4444 if (!check_data_csum
)
4445 goto skip_csum_check
;
4446 leaf_offset
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
4447 ret
= check_extent_csums(root
, key
.offset
, data_len
,
4453 offset
= key
.offset
;
4454 } else if (key
.offset
!= offset
+ num_bytes
) {
4455 ret
= check_extent_exists(root
, offset
, num_bytes
);
4457 fprintf(stderr
, "Csum exists for %Lu-%Lu but "
4458 "there is no extent record\n",
4459 offset
, offset
+num_bytes
);
4462 offset
= key
.offset
;
4465 num_bytes
+= data_len
;
4469 btrfs_free_path(path
);
4473 static int is_dropped_key(struct btrfs_key
*key
,
4474 struct btrfs_key
*drop_key
) {
4475 if (key
->objectid
< drop_key
->objectid
)
4477 else if (key
->objectid
== drop_key
->objectid
) {
4478 if (key
->type
< drop_key
->type
)
4480 else if (key
->type
== drop_key
->type
) {
4481 if (key
->offset
< drop_key
->offset
)
4488 static int run_next_block(struct btrfs_trans_handle
*trans
,
4489 struct btrfs_root
*root
,
4490 struct block_info
*bits
,
4493 struct cache_tree
*pending
,
4494 struct cache_tree
*seen
,
4495 struct cache_tree
*reada
,
4496 struct cache_tree
*nodes
,
4497 struct cache_tree
*extent_cache
,
4498 struct cache_tree
*chunk_cache
,
4499 struct rb_root
*dev_cache
,
4500 struct block_group_tree
*block_group_cache
,
4501 struct device_extent_tree
*dev_extent_cache
,
4502 struct btrfs_root_item
*ri
)
4504 struct extent_buffer
*buf
;
4515 struct btrfs_key key
;
4516 struct cache_extent
*cache
;
4519 nritems
= pick_next_pending(pending
, reada
, nodes
, *last
, bits
,
4520 bits_nr
, &reada_bits
);
4525 for(i
= 0; i
< nritems
; i
++) {
4526 ret
= add_cache_extent(reada
, bits
[i
].start
,
4531 /* fixme, get the parent transid */
4532 readahead_tree_block(root
, bits
[i
].start
,
4536 *last
= bits
[0].start
;
4537 bytenr
= bits
[0].start
;
4538 size
= bits
[0].size
;
4540 cache
= lookup_cache_extent(pending
, bytenr
, size
);
4542 remove_cache_extent(pending
, cache
);
4545 cache
= lookup_cache_extent(reada
, bytenr
, size
);
4547 remove_cache_extent(reada
, cache
);
4550 cache
= lookup_cache_extent(nodes
, bytenr
, size
);
4552 remove_cache_extent(nodes
, cache
);
4555 cache
= lookup_cache_extent(extent_cache
, bytenr
, size
);
4557 struct extent_record
*rec
;
4559 rec
= container_of(cache
, struct extent_record
, cache
);
4560 gen
= rec
->parent_generation
;
4563 /* fixme, get the real parent transid */
4564 buf
= read_tree_block(root
, bytenr
, size
, gen
);
4565 if (!extent_buffer_uptodate(buf
)) {
4566 record_bad_block_io(root
->fs_info
,
4567 extent_cache
, bytenr
, size
);
4571 nritems
= btrfs_header_nritems(buf
);
4574 * FIXME, this only works only if we don't have any full
4577 if (!init_extent_tree
) {
4578 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
,
4579 btrfs_header_level(buf
), 1, NULL
,
4587 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
) {
4592 owner
= btrfs_header_owner(buf
);
4595 ret
= check_block(trans
, root
, extent_cache
, buf
, flags
);
4599 if (btrfs_is_leaf(buf
)) {
4600 btree_space_waste
+= btrfs_leaf_free_space(root
, buf
);
4601 for (i
= 0; i
< nritems
; i
++) {
4602 struct btrfs_file_extent_item
*fi
;
4603 btrfs_item_key_to_cpu(buf
, &key
, i
);
4604 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
4605 process_extent_item(root
, extent_cache
, buf
,
4609 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
4610 process_extent_item(root
, extent_cache
, buf
,
4614 if (key
.type
== BTRFS_EXTENT_CSUM_KEY
) {
4616 btrfs_item_size_nr(buf
, i
);
4619 if (key
.type
== BTRFS_CHUNK_ITEM_KEY
) {
4620 process_chunk_item(chunk_cache
, &key
, buf
, i
);
4623 if (key
.type
== BTRFS_DEV_ITEM_KEY
) {
4624 process_device_item(dev_cache
, &key
, buf
, i
);
4627 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
4628 process_block_group_item(block_group_cache
,
4632 if (key
.type
== BTRFS_DEV_EXTENT_KEY
) {
4633 process_device_extent_item(dev_extent_cache
,
4638 if (key
.type
== BTRFS_EXTENT_REF_V0_KEY
) {
4639 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4640 process_extent_ref_v0(extent_cache
, buf
, i
);
4647 if (key
.type
== BTRFS_TREE_BLOCK_REF_KEY
) {
4648 add_tree_backref(extent_cache
, key
.objectid
, 0,
4652 if (key
.type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
4653 add_tree_backref(extent_cache
, key
.objectid
,
4657 if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
) {
4658 struct btrfs_extent_data_ref
*ref
;
4659 ref
= btrfs_item_ptr(buf
, i
,
4660 struct btrfs_extent_data_ref
);
4661 add_data_backref(extent_cache
,
4663 btrfs_extent_data_ref_root(buf
, ref
),
4664 btrfs_extent_data_ref_objectid(buf
,
4666 btrfs_extent_data_ref_offset(buf
, ref
),
4667 btrfs_extent_data_ref_count(buf
, ref
),
4668 0, root
->sectorsize
);
4671 if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
) {
4672 struct btrfs_shared_data_ref
*ref
;
4673 ref
= btrfs_item_ptr(buf
, i
,
4674 struct btrfs_shared_data_ref
);
4675 add_data_backref(extent_cache
,
4676 key
.objectid
, key
.offset
, 0, 0, 0,
4677 btrfs_shared_data_ref_count(buf
, ref
),
4678 0, root
->sectorsize
);
4681 if (key
.type
== BTRFS_ORPHAN_ITEM_KEY
) {
4682 struct bad_item
*bad
;
4684 if (key
.objectid
== BTRFS_ORPHAN_OBJECTID
)
4688 bad
= malloc(sizeof(struct bad_item
));
4691 INIT_LIST_HEAD(&bad
->list
);
4692 memcpy(&bad
->key
, &key
,
4693 sizeof(struct btrfs_key
));
4694 bad
->root_id
= owner
;
4695 list_add_tail(&bad
->list
, &delete_items
);
4698 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
4700 fi
= btrfs_item_ptr(buf
, i
,
4701 struct btrfs_file_extent_item
);
4702 if (btrfs_file_extent_type(buf
, fi
) ==
4703 BTRFS_FILE_EXTENT_INLINE
)
4705 if (btrfs_file_extent_disk_bytenr(buf
, fi
) == 0)
4708 data_bytes_allocated
+=
4709 btrfs_file_extent_disk_num_bytes(buf
, fi
);
4710 if (data_bytes_allocated
< root
->sectorsize
) {
4713 data_bytes_referenced
+=
4714 btrfs_file_extent_num_bytes(buf
, fi
);
4715 add_data_backref(extent_cache
,
4716 btrfs_file_extent_disk_bytenr(buf
, fi
),
4717 parent
, owner
, key
.objectid
, key
.offset
-
4718 btrfs_file_extent_offset(buf
, fi
), 1, 1,
4719 btrfs_file_extent_disk_num_bytes(buf
, fi
));
4723 struct btrfs_key first_key
;
4725 first_key
.objectid
= 0;
4728 btrfs_item_key_to_cpu(buf
, &first_key
, 0);
4729 level
= btrfs_header_level(buf
);
4730 for (i
= 0; i
< nritems
; i
++) {
4731 ptr
= btrfs_node_blockptr(buf
, i
);
4732 size
= btrfs_level_size(root
, level
- 1);
4733 btrfs_node_key_to_cpu(buf
, &key
, i
);
4735 struct btrfs_key drop_key
;
4736 btrfs_disk_key_to_cpu(&drop_key
,
4737 &ri
->drop_progress
);
4738 if ((level
== ri
->drop_level
)
4739 && is_dropped_key(&key
, &drop_key
)) {
4743 ret
= add_extent_rec(extent_cache
, &key
,
4744 btrfs_node_ptr_generation(buf
, i
),
4745 ptr
, size
, 0, 0, 1, 0, 1, 0,
4749 add_tree_backref(extent_cache
, ptr
, parent
, owner
, 1);
4752 add_pending(nodes
, seen
, ptr
, size
);
4754 add_pending(pending
, seen
, ptr
, size
);
4757 btree_space_waste
+= (BTRFS_NODEPTRS_PER_BLOCK(root
) -
4758 nritems
) * sizeof(struct btrfs_key_ptr
);
4760 total_btree_bytes
+= buf
->len
;
4761 if (fs_root_objectid(btrfs_header_owner(buf
)))
4762 total_fs_tree_bytes
+= buf
->len
;
4763 if (btrfs_header_owner(buf
) == BTRFS_EXTENT_TREE_OBJECTID
)
4764 total_extent_tree_bytes
+= buf
->len
;
4765 if (!found_old_backref
&&
4766 btrfs_header_owner(buf
) == BTRFS_TREE_RELOC_OBJECTID
&&
4767 btrfs_header_backref_rev(buf
) == BTRFS_MIXED_BACKREF_REV
&&
4768 !btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_RELOC
))
4769 found_old_backref
= 1;
4771 free_extent_buffer(buf
);
4775 static int add_root_to_pending(struct extent_buffer
*buf
,
4776 struct cache_tree
*extent_cache
,
4777 struct cache_tree
*pending
,
4778 struct cache_tree
*seen
,
4779 struct cache_tree
*nodes
,
4780 struct btrfs_key
*root_key
)
4782 if (btrfs_header_level(buf
) > 0)
4783 add_pending(nodes
, seen
, buf
->start
, buf
->len
);
4785 add_pending(pending
, seen
, buf
->start
, buf
->len
);
4786 add_extent_rec(extent_cache
, NULL
, 0, buf
->start
, buf
->len
,
4787 0, 1, 1, 0, 1, 0, buf
->len
);
4789 if (root_key
->objectid
== BTRFS_TREE_RELOC_OBJECTID
||
4790 btrfs_header_backref_rev(buf
) < BTRFS_MIXED_BACKREF_REV
)
4791 add_tree_backref(extent_cache
, buf
->start
, buf
->start
,
4794 add_tree_backref(extent_cache
, buf
->start
, 0,
4795 root_key
->objectid
, 1);
4799 /* as we fix the tree, we might be deleting blocks that
4800 * we're tracking for repair. This hook makes sure we
4801 * remove any backrefs for blocks as we are fixing them.
4803 static int free_extent_hook(struct btrfs_trans_handle
*trans
,
4804 struct btrfs_root
*root
,
4805 u64 bytenr
, u64 num_bytes
, u64 parent
,
4806 u64 root_objectid
, u64 owner
, u64 offset
,
4809 struct extent_record
*rec
;
4810 struct cache_extent
*cache
;
4812 struct cache_tree
*extent_cache
= root
->fs_info
->fsck_extent_cache
;
4814 is_data
= owner
>= BTRFS_FIRST_FREE_OBJECTID
;
4815 cache
= lookup_cache_extent(extent_cache
, bytenr
, num_bytes
);
4819 rec
= container_of(cache
, struct extent_record
, cache
);
4821 struct data_backref
*back
;
4822 back
= find_data_backref(rec
, parent
, root_objectid
, owner
,
4823 offset
, 1, bytenr
, num_bytes
);
4826 if (back
->node
.found_ref
) {
4827 back
->found_ref
-= refs_to_drop
;
4829 rec
->refs
-= refs_to_drop
;
4831 if (back
->node
.found_extent_tree
) {
4832 back
->num_refs
-= refs_to_drop
;
4833 if (rec
->extent_item_refs
)
4834 rec
->extent_item_refs
-= refs_to_drop
;
4836 if (back
->found_ref
== 0)
4837 back
->node
.found_ref
= 0;
4838 if (back
->num_refs
== 0)
4839 back
->node
.found_extent_tree
= 0;
4841 if (!back
->node
.found_extent_tree
&& back
->node
.found_ref
) {
4842 list_del(&back
->node
.list
);
4846 struct tree_backref
*back
;
4847 back
= find_tree_backref(rec
, parent
, root_objectid
);
4850 if (back
->node
.found_ref
) {
4853 back
->node
.found_ref
= 0;
4855 if (back
->node
.found_extent_tree
) {
4856 if (rec
->extent_item_refs
)
4857 rec
->extent_item_refs
--;
4858 back
->node
.found_extent_tree
= 0;
4860 if (!back
->node
.found_extent_tree
&& back
->node
.found_ref
) {
4861 list_del(&back
->node
.list
);
4865 maybe_free_extent_rec(extent_cache
, rec
);
4870 static int delete_extent_records(struct btrfs_trans_handle
*trans
,
4871 struct btrfs_root
*root
,
4872 struct btrfs_path
*path
,
4873 u64 bytenr
, u64 new_len
)
4875 struct btrfs_key key
;
4876 struct btrfs_key found_key
;
4877 struct extent_buffer
*leaf
;
4882 key
.objectid
= bytenr
;
4884 key
.offset
= (u64
)-1;
4887 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
,
4894 if (path
->slots
[0] == 0)
4900 leaf
= path
->nodes
[0];
4901 slot
= path
->slots
[0];
4903 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
4904 if (found_key
.objectid
!= bytenr
)
4907 if (found_key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
4908 found_key
.type
!= BTRFS_METADATA_ITEM_KEY
&&
4909 found_key
.type
!= BTRFS_TREE_BLOCK_REF_KEY
&&
4910 found_key
.type
!= BTRFS_EXTENT_DATA_REF_KEY
&&
4911 found_key
.type
!= BTRFS_EXTENT_REF_V0_KEY
&&
4912 found_key
.type
!= BTRFS_SHARED_BLOCK_REF_KEY
&&
4913 found_key
.type
!= BTRFS_SHARED_DATA_REF_KEY
) {
4914 btrfs_release_path(path
);
4915 if (found_key
.type
== 0) {
4916 if (found_key
.offset
== 0)
4918 key
.offset
= found_key
.offset
- 1;
4919 key
.type
= found_key
.type
;
4921 key
.type
= found_key
.type
- 1;
4922 key
.offset
= (u64
)-1;
4926 fprintf(stderr
, "repair deleting extent record: key %Lu %u %Lu\n",
4927 found_key
.objectid
, found_key
.type
, found_key
.offset
);
4929 ret
= btrfs_del_item(trans
, root
->fs_info
->extent_root
, path
);
4932 btrfs_release_path(path
);
4934 if (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
||
4935 found_key
.type
== BTRFS_METADATA_ITEM_KEY
) {
4936 u64 bytes
= (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
) ?
4937 found_key
.offset
: root
->leafsize
;
4939 ret
= btrfs_update_block_group(trans
, root
, bytenr
,
4946 btrfs_release_path(path
);
4951 * for a single backref, this will allocate a new extent
4952 * and add the backref to it.
4954 static int record_extent(struct btrfs_trans_handle
*trans
,
4955 struct btrfs_fs_info
*info
,
4956 struct btrfs_path
*path
,
4957 struct extent_record
*rec
,
4958 struct extent_backref
*back
,
4959 int allocated
, u64 flags
)
4962 struct btrfs_root
*extent_root
= info
->extent_root
;
4963 struct extent_buffer
*leaf
;
4964 struct btrfs_key ins_key
;
4965 struct btrfs_extent_item
*ei
;
4966 struct tree_backref
*tback
;
4967 struct data_backref
*dback
;
4968 struct btrfs_tree_block_info
*bi
;
4971 rec
->max_size
= max_t(u64
, rec
->max_size
,
4972 info
->extent_root
->leafsize
);
4975 u32 item_size
= sizeof(*ei
);
4978 item_size
+= sizeof(*bi
);
4980 ins_key
.objectid
= rec
->start
;
4981 ins_key
.offset
= rec
->max_size
;
4982 ins_key
.type
= BTRFS_EXTENT_ITEM_KEY
;
4984 ret
= btrfs_insert_empty_item(trans
, extent_root
, path
,
4985 &ins_key
, item_size
);
4989 leaf
= path
->nodes
[0];
4990 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
4991 struct btrfs_extent_item
);
4993 btrfs_set_extent_refs(leaf
, ei
, 0);
4994 btrfs_set_extent_generation(leaf
, ei
, rec
->generation
);
4996 if (back
->is_data
) {
4997 btrfs_set_extent_flags(leaf
, ei
,
4998 BTRFS_EXTENT_FLAG_DATA
);
5000 struct btrfs_disk_key copy_key
;;
5002 tback
= (struct tree_backref
*)back
;
5003 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
5004 memset_extent_buffer(leaf
, 0, (unsigned long)bi
,
5007 btrfs_set_disk_key_objectid(©_key
,
5008 rec
->info_objectid
);
5009 btrfs_set_disk_key_type(©_key
, 0);
5010 btrfs_set_disk_key_offset(©_key
, 0);
5012 btrfs_set_tree_block_level(leaf
, bi
, rec
->info_level
);
5013 btrfs_set_tree_block_key(leaf
, bi
, ©_key
);
5015 btrfs_set_extent_flags(leaf
, ei
,
5016 BTRFS_EXTENT_FLAG_TREE_BLOCK
| flags
);
5019 btrfs_mark_buffer_dirty(leaf
);
5020 ret
= btrfs_update_block_group(trans
, extent_root
, rec
->start
,
5021 rec
->max_size
, 1, 0);
5024 btrfs_release_path(path
);
5027 if (back
->is_data
) {
5031 dback
= (struct data_backref
*)back
;
5032 if (back
->full_backref
)
5033 parent
= dback
->parent
;
5037 for (i
= 0; i
< dback
->found_ref
; i
++) {
5038 /* if parent != 0, we're doing a full backref
5039 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
5040 * just makes the backref allocator create a data
5043 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
5044 rec
->start
, rec
->max_size
,
5048 BTRFS_FIRST_FREE_OBJECTID
:
5054 fprintf(stderr
, "adding new data backref"
5055 " on %llu %s %llu owner %llu"
5056 " offset %llu found %d\n",
5057 (unsigned long long)rec
->start
,
5058 back
->full_backref
?
5060 back
->full_backref
?
5061 (unsigned long long)parent
:
5062 (unsigned long long)dback
->root
,
5063 (unsigned long long)dback
->owner
,
5064 (unsigned long long)dback
->offset
,
5069 tback
= (struct tree_backref
*)back
;
5070 if (back
->full_backref
)
5071 parent
= tback
->parent
;
5075 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
5076 rec
->start
, rec
->max_size
,
5077 parent
, tback
->root
, 0, 0);
5078 fprintf(stderr
, "adding new tree backref on "
5079 "start %llu len %llu parent %llu root %llu\n",
5080 rec
->start
, rec
->max_size
, tback
->parent
, tback
->root
);
5085 btrfs_release_path(path
);
5089 struct extent_entry
{
5094 struct list_head list
;
5097 static struct extent_entry
*find_entry(struct list_head
*entries
,
5098 u64 bytenr
, u64 bytes
)
5100 struct extent_entry
*entry
= NULL
;
5102 list_for_each_entry(entry
, entries
, list
) {
5103 if (entry
->bytenr
== bytenr
&& entry
->bytes
== bytes
)
5110 static struct extent_entry
*find_most_right_entry(struct list_head
*entries
)
5112 struct extent_entry
*entry
, *best
= NULL
, *prev
= NULL
;
5114 list_for_each_entry(entry
, entries
, list
) {
5121 * If there are as many broken entries as entries then we know
5122 * not to trust this particular entry.
5124 if (entry
->broken
== entry
->count
)
5128 * If our current entry == best then we can't be sure our best
5129 * is really the best, so we need to keep searching.
5131 if (best
&& best
->count
== entry
->count
) {
5137 /* Prev == entry, not good enough, have to keep searching */
5138 if (!prev
->broken
&& prev
->count
== entry
->count
)
5142 best
= (prev
->count
> entry
->count
) ? prev
: entry
;
5143 else if (best
->count
< entry
->count
)
5151 static int repair_ref(struct btrfs_trans_handle
*trans
,
5152 struct btrfs_fs_info
*info
, struct btrfs_path
*path
,
5153 struct data_backref
*dback
, struct extent_entry
*entry
)
5155 struct btrfs_root
*root
;
5156 struct btrfs_file_extent_item
*fi
;
5157 struct extent_buffer
*leaf
;
5158 struct btrfs_key key
;
5162 key
.objectid
= dback
->root
;
5163 key
.type
= BTRFS_ROOT_ITEM_KEY
;
5164 key
.offset
= (u64
)-1;
5165 root
= btrfs_read_fs_root(info
, &key
);
5167 fprintf(stderr
, "Couldn't find root for our ref\n");
5172 * The backref points to the original offset of the extent if it was
5173 * split, so we need to search down to the offset we have and then walk
5174 * forward until we find the backref we're looking for.
5176 key
.objectid
= dback
->owner
;
5177 key
.type
= BTRFS_EXTENT_DATA_KEY
;
5178 key
.offset
= dback
->offset
;
5179 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
5181 fprintf(stderr
, "Error looking up ref %d\n", ret
);
5186 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
5187 ret
= btrfs_next_leaf(root
, path
);
5189 fprintf(stderr
, "Couldn't find our ref, next\n");
5193 leaf
= path
->nodes
[0];
5194 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
5195 if (key
.objectid
!= dback
->owner
||
5196 key
.type
!= BTRFS_EXTENT_DATA_KEY
) {
5197 fprintf(stderr
, "Couldn't find our ref, search\n");
5200 fi
= btrfs_item_ptr(leaf
, path
->slots
[0],
5201 struct btrfs_file_extent_item
);
5202 bytenr
= btrfs_file_extent_disk_bytenr(leaf
, fi
);
5203 bytes
= btrfs_file_extent_disk_num_bytes(leaf
, fi
);
5205 if (bytenr
== dback
->disk_bytenr
&& bytes
== dback
->bytes
)
5210 btrfs_release_path(path
);
5213 * Have to make sure that this root gets updated when we commit the
5216 record_root_in_trans(trans
, root
);
5219 * Ok we have the key of the file extent we want to fix, now we can cow
5220 * down to the thing and fix it.
5222 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
5224 fprintf(stderr
, "Error cowing down to ref [%Lu, %u, %Lu]: %d\n",
5225 key
.objectid
, key
.type
, key
.offset
, ret
);
5229 fprintf(stderr
, "Well that's odd, we just found this key "
5230 "[%Lu, %u, %Lu]\n", key
.objectid
, key
.type
,
5234 leaf
= path
->nodes
[0];
5235 fi
= btrfs_item_ptr(leaf
, path
->slots
[0],
5236 struct btrfs_file_extent_item
);
5238 if (btrfs_file_extent_compression(leaf
, fi
) &&
5239 dback
->disk_bytenr
!= entry
->bytenr
) {
5240 fprintf(stderr
, "Ref doesn't match the record start and is "
5241 "compressed, please take a btrfs-image of this file "
5242 "system and send it to a btrfs developer so they can "
5243 "complete this functionality for bytenr %Lu\n",
5244 dback
->disk_bytenr
);
5248 if (dback
->node
.broken
&& dback
->disk_bytenr
!= entry
->bytenr
) {
5249 btrfs_set_file_extent_disk_bytenr(leaf
, fi
, entry
->bytenr
);
5250 } else if (dback
->disk_bytenr
> entry
->bytenr
) {
5251 u64 off_diff
, offset
;
5253 off_diff
= dback
->disk_bytenr
- entry
->bytenr
;
5254 offset
= btrfs_file_extent_offset(leaf
, fi
);
5255 if (dback
->disk_bytenr
+ offset
+
5256 btrfs_file_extent_num_bytes(leaf
, fi
) >
5257 entry
->bytenr
+ entry
->bytes
) {
5258 fprintf(stderr
, "Ref is past the entry end, please "
5259 "take a btrfs-image of this file system and "
5260 "send it to a btrfs developer, ref %Lu\n",
5261 dback
->disk_bytenr
);
5265 btrfs_set_file_extent_disk_bytenr(leaf
, fi
, entry
->bytenr
);
5266 btrfs_set_file_extent_offset(leaf
, fi
, offset
);
5267 } else if (dback
->disk_bytenr
< entry
->bytenr
) {
5270 offset
= btrfs_file_extent_offset(leaf
, fi
);
5271 if (dback
->disk_bytenr
+ offset
< entry
->bytenr
) {
5272 fprintf(stderr
, "Ref is before the entry start, please"
5273 " take a btrfs-image of this file system and "
5274 "send it to a btrfs developer, ref %Lu\n",
5275 dback
->disk_bytenr
);
5279 offset
+= dback
->disk_bytenr
;
5280 offset
-= entry
->bytenr
;
5281 btrfs_set_file_extent_disk_bytenr(leaf
, fi
, entry
->bytenr
);
5282 btrfs_set_file_extent_offset(leaf
, fi
, offset
);
5285 btrfs_set_file_extent_disk_num_bytes(leaf
, fi
, entry
->bytes
);
5288 * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
5289 * only do this if we aren't using compression, otherwise it's a
5292 if (!btrfs_file_extent_compression(leaf
, fi
))
5293 btrfs_set_file_extent_ram_bytes(leaf
, fi
, entry
->bytes
);
5295 printf("ram bytes may be wrong?\n");
5296 btrfs_mark_buffer_dirty(leaf
);
5297 btrfs_release_path(path
);
5301 static int verify_backrefs(struct btrfs_trans_handle
*trans
,
5302 struct btrfs_fs_info
*info
, struct btrfs_path
*path
,
5303 struct extent_record
*rec
)
5305 struct extent_backref
*back
;
5306 struct data_backref
*dback
;
5307 struct extent_entry
*entry
, *best
= NULL
;
5310 int broken_entries
= 0;
5315 * Metadata is easy and the backrefs should always agree on bytenr and
5316 * size, if not we've got bigger issues.
5321 list_for_each_entry(back
, &rec
->backrefs
, list
) {
5322 if (back
->full_backref
|| !back
->is_data
)
5325 dback
= (struct data_backref
*)back
;
5328 * We only pay attention to backrefs that we found a real
5331 if (dback
->found_ref
== 0)
5335 * For now we only catch when the bytes don't match, not the
5336 * bytenr. We can easily do this at the same time, but I want
5337 * to have a fs image to test on before we just add repair
5338 * functionality willy-nilly so we know we won't screw up the
5342 entry
= find_entry(&entries
, dback
->disk_bytenr
,
5345 entry
= malloc(sizeof(struct extent_entry
));
5350 memset(entry
, 0, sizeof(*entry
));
5351 entry
->bytenr
= dback
->disk_bytenr
;
5352 entry
->bytes
= dback
->bytes
;
5353 list_add_tail(&entry
->list
, &entries
);
5358 * If we only have on entry we may think the entries agree when
5359 * in reality they don't so we have to do some extra checking.
5361 if (dback
->disk_bytenr
!= rec
->start
||
5362 dback
->bytes
!= rec
->nr
|| back
->broken
)
5373 /* Yay all the backrefs agree, carry on good sir */
5374 if (nr_entries
<= 1 && !mismatch
)
5377 fprintf(stderr
, "attempting to repair backref discrepency for bytenr "
5378 "%Lu\n", rec
->start
);
5381 * First we want to see if the backrefs can agree amongst themselves who
5382 * is right, so figure out which one of the entries has the highest
5385 best
= find_most_right_entry(&entries
);
5388 * Ok so we may have an even split between what the backrefs think, so
5389 * this is where we use the extent ref to see what it thinks.
5392 entry
= find_entry(&entries
, rec
->start
, rec
->nr
);
5393 if (!entry
&& (!broken_entries
|| !rec
->found_rec
)) {
5394 fprintf(stderr
, "Backrefs don't agree with each other "
5395 "and extent record doesn't agree with anybody,"
5396 " so we can't fix bytenr %Lu bytes %Lu\n",
5397 rec
->start
, rec
->nr
);
5400 } else if (!entry
) {
5402 * Ok our backrefs were broken, we'll assume this is the
5403 * correct value and add an entry for this range.
5405 entry
= malloc(sizeof(struct extent_entry
));
5410 memset(entry
, 0, sizeof(*entry
));
5411 entry
->bytenr
= rec
->start
;
5412 entry
->bytes
= rec
->nr
;
5413 list_add_tail(&entry
->list
, &entries
);
5417 best
= find_most_right_entry(&entries
);
5419 fprintf(stderr
, "Backrefs and extent record evenly "
5420 "split on who is right, this is going to "
5421 "require user input to fix bytenr %Lu bytes "
5422 "%Lu\n", rec
->start
, rec
->nr
);
5429 * I don't think this can happen currently as we'll abort() if we catch
5430 * this case higher up, but in case somebody removes that we still can't
5431 * deal with it properly here yet, so just bail out of that's the case.
5433 if (best
->bytenr
!= rec
->start
) {
5434 fprintf(stderr
, "Extent start and backref starts don't match, "
5435 "please use btrfs-image on this file system and send "
5436 "it to a btrfs developer so they can make fsck fix "
5437 "this particular case. bytenr is %Lu, bytes is %Lu\n",
5438 rec
->start
, rec
->nr
);
5444 * Ok great we all agreed on an extent record, let's go find the real
5445 * references and fix up the ones that don't match.
5447 list_for_each_entry(back
, &rec
->backrefs
, list
) {
5448 if (back
->full_backref
|| !back
->is_data
)
5451 dback
= (struct data_backref
*)back
;
5454 * Still ignoring backrefs that don't have a real ref attached
5457 if (dback
->found_ref
== 0)
5460 if (dback
->bytes
== best
->bytes
&&
5461 dback
->disk_bytenr
== best
->bytenr
)
5464 ret
= repair_ref(trans
, info
, path
, dback
, best
);
5470 * Ok we messed with the actual refs, which means we need to drop our
5471 * entire cache and go back and rescan. I know this is a huge pain and
5472 * adds a lot of extra work, but it's the only way to be safe. Once all
5473 * the backrefs agree we may not need to do anything to the extent
5478 while (!list_empty(&entries
)) {
5479 entry
= list_entry(entries
.next
, struct extent_entry
, list
);
5480 list_del_init(&entry
->list
);
5486 static int process_duplicates(struct btrfs_root
*root
,
5487 struct cache_tree
*extent_cache
,
5488 struct extent_record
*rec
)
5490 struct extent_record
*good
, *tmp
;
5491 struct cache_extent
*cache
;
5495 * If we found a extent record for this extent then return, or if we
5496 * have more than one duplicate we are likely going to need to delete
5499 if (rec
->found_rec
|| rec
->num_duplicates
> 1)
5502 /* Shouldn't happen but just in case */
5503 BUG_ON(!rec
->num_duplicates
);
5506 * So this happens if we end up with a backref that doesn't match the
5507 * actual extent entry. So either the backref is bad or the extent
5508 * entry is bad. Either way we want to have the extent_record actually
5509 * reflect what we found in the extent_tree, so we need to take the
5510 * duplicate out and use that as the extent_record since the only way we
5511 * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
5513 remove_cache_extent(extent_cache
, &rec
->cache
);
5515 good
= list_entry(rec
->dups
.next
, struct extent_record
, list
);
5516 list_del_init(&good
->list
);
5517 INIT_LIST_HEAD(&good
->backrefs
);
5518 INIT_LIST_HEAD(&good
->dups
);
5519 good
->cache
.start
= good
->start
;
5520 good
->cache
.size
= good
->nr
;
5521 good
->content_checked
= 0;
5522 good
->owner_ref_checked
= 0;
5523 good
->num_duplicates
= 0;
5524 good
->refs
= rec
->refs
;
5525 list_splice_init(&rec
->backrefs
, &good
->backrefs
);
5527 cache
= lookup_cache_extent(extent_cache
, good
->start
,
5531 tmp
= container_of(cache
, struct extent_record
, cache
);
5534 * If we find another overlapping extent and it's found_rec is
5535 * set then it's a duplicate and we need to try and delete
5538 if (tmp
->found_rec
|| tmp
->num_duplicates
> 0) {
5539 if (list_empty(&good
->list
))
5540 list_add_tail(&good
->list
,
5541 &duplicate_extents
);
5542 good
->num_duplicates
+= tmp
->num_duplicates
+ 1;
5543 list_splice_init(&tmp
->dups
, &good
->dups
);
5544 list_del_init(&tmp
->list
);
5545 list_add_tail(&tmp
->list
, &good
->dups
);
5546 remove_cache_extent(extent_cache
, &tmp
->cache
);
5551 * Ok we have another non extent item backed extent rec, so lets
5552 * just add it to this extent and carry on like we did above.
5554 good
->refs
+= tmp
->refs
;
5555 list_splice_init(&tmp
->backrefs
, &good
->backrefs
);
5556 remove_cache_extent(extent_cache
, &tmp
->cache
);
5559 ret
= insert_cache_extent(extent_cache
, &good
->cache
);
5562 return good
->num_duplicates
? 0 : 1;
5565 static int delete_duplicate_records(struct btrfs_trans_handle
*trans
,
5566 struct btrfs_root
*root
,
5567 struct extent_record
*rec
)
5569 LIST_HEAD(delete_list
);
5570 struct btrfs_path
*path
;
5571 struct extent_record
*tmp
, *good
, *n
;
5574 struct btrfs_key key
;
5576 path
= btrfs_alloc_path();
5583 /* Find the record that covers all of the duplicates. */
5584 list_for_each_entry(tmp
, &rec
->dups
, list
) {
5585 if (good
->start
< tmp
->start
)
5587 if (good
->nr
> tmp
->nr
)
5590 if (tmp
->start
+ tmp
->nr
< good
->start
+ good
->nr
) {
5591 fprintf(stderr
, "Ok we have overlapping extents that "
5592 "aren't completely covered by eachother, this "
5593 "is going to require more careful thought. "
5594 "The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
5595 tmp
->start
, tmp
->nr
, good
->start
, good
->nr
);
5602 list_add_tail(&rec
->list
, &delete_list
);
5604 list_for_each_entry_safe(tmp
, n
, &rec
->dups
, list
) {
5607 list_move_tail(&tmp
->list
, &delete_list
);
5610 root
= root
->fs_info
->extent_root
;
5611 list_for_each_entry(tmp
, &delete_list
, list
) {
5612 if (tmp
->found_rec
== 0)
5614 key
.objectid
= tmp
->start
;
5615 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
5616 key
.offset
= tmp
->nr
;
5618 /* Shouldn't happen but just in case */
5619 if (tmp
->metadata
) {
5620 fprintf(stderr
, "Well this shouldn't happen, extent "
5621 "record overlaps but is metadata? "
5622 "[%Lu, %Lu]\n", tmp
->start
, tmp
->nr
);
5626 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
5632 ret
= btrfs_del_item(trans
, root
, path
);
5635 btrfs_release_path(path
);
5640 while (!list_empty(&delete_list
)) {
5641 tmp
= list_entry(delete_list
.next
, struct extent_record
, list
);
5642 list_del_init(&tmp
->list
);
5648 while (!list_empty(&rec
->dups
)) {
5649 tmp
= list_entry(rec
->dups
.next
, struct extent_record
, list
);
5650 list_del_init(&tmp
->list
);
5654 btrfs_free_path(path
);
5656 if (!ret
&& !nr_del
)
5657 rec
->num_duplicates
= 0;
5659 return ret
? ret
: nr_del
;
5662 static int find_possible_backrefs(struct btrfs_trans_handle
*trans
,
5663 struct btrfs_fs_info
*info
,
5664 struct btrfs_path
*path
,
5665 struct cache_tree
*extent_cache
,
5666 struct extent_record
*rec
)
5668 struct btrfs_root
*root
;
5669 struct extent_backref
*back
;
5670 struct data_backref
*dback
;
5671 struct cache_extent
*cache
;
5672 struct btrfs_file_extent_item
*fi
;
5673 struct btrfs_key key
;
5677 list_for_each_entry(back
, &rec
->backrefs
, list
) {
5678 /* Don't care about full backrefs (poor unloved backrefs) */
5679 if (back
->full_backref
|| !back
->is_data
)
5682 dback
= (struct data_backref
*)back
;
5684 /* We found this one, we don't need to do a lookup */
5685 if (dback
->found_ref
)
5688 key
.objectid
= dback
->root
;
5689 key
.type
= BTRFS_ROOT_ITEM_KEY
;
5690 key
.offset
= (u64
)-1;
5692 root
= btrfs_read_fs_root(info
, &key
);
5694 /* No root, definitely a bad ref, skip */
5695 if (IS_ERR(root
) && PTR_ERR(root
) == -ENOENT
)
5697 /* Other err, exit */
5699 return PTR_ERR(root
);
5701 key
.objectid
= dback
->owner
;
5702 key
.type
= BTRFS_EXTENT_DATA_KEY
;
5703 key
.offset
= dback
->offset
;
5704 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
5706 btrfs_release_path(path
);
5709 /* Didn't find it, we can carry on */
5714 fi
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
5715 struct btrfs_file_extent_item
);
5716 bytenr
= btrfs_file_extent_disk_bytenr(path
->nodes
[0], fi
);
5717 bytes
= btrfs_file_extent_disk_num_bytes(path
->nodes
[0], fi
);
5718 btrfs_release_path(path
);
5719 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
5721 struct extent_record
*tmp
;
5722 tmp
= container_of(cache
, struct extent_record
, cache
);
5725 * If we found an extent record for the bytenr for this
5726 * particular backref then we can't add it to our
5727 * current extent record. We only want to add backrefs
5728 * that don't have a corresponding extent item in the
5729 * extent tree since they likely belong to this record
5730 * and we need to fix it if it doesn't match bytenrs.
5736 dback
->found_ref
+= 1;
5737 dback
->disk_bytenr
= bytenr
;
5738 dback
->bytes
= bytes
;
5741 * Set this so the verify backref code knows not to trust the
5742 * values in this backref.
5751 * when an incorrect extent item is found, this will delete
5752 * all of the existing entries for it and recreate them
5753 * based on what the tree scan found.
5755 static int fixup_extent_refs(struct btrfs_trans_handle
*trans
,
5756 struct btrfs_fs_info
*info
,
5757 struct cache_tree
*extent_cache
,
5758 struct extent_record
*rec
)
5761 struct btrfs_path
*path
;
5762 struct list_head
*cur
= rec
->backrefs
.next
;
5763 struct cache_extent
*cache
;
5764 struct extent_backref
*back
;
5769 * remember our flags for recreating the extent.
5770 * FIXME, if we have cleared extent tree, we can not
5771 * lookup extent info in extent tree.
5773 if (!init_extent_tree
) {
5774 ret
= btrfs_lookup_extent_info(NULL
, info
->extent_root
,
5775 rec
->start
, rec
->max_size
,
5776 rec
->metadata
, NULL
, &flags
);
5783 path
= btrfs_alloc_path();
5787 if (rec
->refs
!= rec
->extent_item_refs
&& !rec
->metadata
) {
5789 * Sometimes the backrefs themselves are so broken they don't
5790 * get attached to any meaningful rec, so first go back and
5791 * check any of our backrefs that we couldn't find and throw
5792 * them into the list if we find the backref so that
5793 * verify_backrefs can figure out what to do.
5795 ret
= find_possible_backrefs(trans
, info
, path
, extent_cache
,
5801 /* step one, make sure all of the backrefs agree */
5802 ret
= verify_backrefs(trans
, info
, path
, rec
);
5806 /* step two, delete all the existing records */
5807 ret
= delete_extent_records(trans
, info
->extent_root
, path
,
5808 rec
->start
, rec
->max_size
);
5813 /* was this block corrupt? If so, don't add references to it */
5814 cache
= lookup_cache_extent(info
->corrupt_blocks
,
5815 rec
->start
, rec
->max_size
);
5821 /* step three, recreate all the refs we did find */
5822 while(cur
!= &rec
->backrefs
) {
5823 back
= list_entry(cur
, struct extent_backref
, list
);
5827 * if we didn't find any references, don't create a
5830 if (!back
->found_ref
)
5833 ret
= record_extent(trans
, info
, path
, rec
, back
, allocated
, flags
);
5840 btrfs_free_path(path
);
5844 /* right now we only prune from the extent allocation tree */
5845 static int prune_one_block(struct btrfs_trans_handle
*trans
,
5846 struct btrfs_fs_info
*info
,
5847 struct btrfs_corrupt_block
*corrupt
)
5850 struct btrfs_path path
;
5851 struct extent_buffer
*eb
;
5855 int level
= corrupt
->level
+ 1;
5857 btrfs_init_path(&path
);
5859 /* we want to stop at the parent to our busted block */
5860 path
.lowest_level
= level
;
5862 ret
= btrfs_search_slot(trans
, info
->extent_root
,
5863 &corrupt
->key
, &path
, -1, 1);
5868 eb
= path
.nodes
[level
];
5875 * hopefully the search gave us the block we want to prune,
5876 * lets try that first
5878 slot
= path
.slots
[level
];
5879 found
= btrfs_node_blockptr(eb
, slot
);
5880 if (found
== corrupt
->cache
.start
)
5883 nritems
= btrfs_header_nritems(eb
);
5885 /* the search failed, lets scan this node and hope we find it */
5886 for (slot
= 0; slot
< nritems
; slot
++) {
5887 found
= btrfs_node_blockptr(eb
, slot
);
5888 if (found
== corrupt
->cache
.start
)
5892 * we couldn't find the bad block. TODO, search all the nodes for pointers
5895 if (eb
== info
->extent_root
->node
) {
5900 btrfs_release_path(&path
);
5905 printk("deleting pointer to block %Lu\n", corrupt
->cache
.start
);
5906 ret
= btrfs_del_ptr(trans
, info
->extent_root
, &path
, level
, slot
);
5909 btrfs_release_path(&path
);
5913 static int prune_corrupt_blocks(struct btrfs_trans_handle
*trans
,
5914 struct btrfs_fs_info
*info
)
5916 struct cache_extent
*cache
;
5917 struct btrfs_corrupt_block
*corrupt
;
5919 cache
= search_cache_extent(info
->corrupt_blocks
, 0);
5923 corrupt
= container_of(cache
, struct btrfs_corrupt_block
, cache
);
5924 prune_one_block(trans
, info
, corrupt
);
5925 cache
= next_cache_extent(cache
);
5930 static void free_corrupt_block(struct cache_extent
*cache
)
5932 struct btrfs_corrupt_block
*corrupt
;
5934 corrupt
= container_of(cache
, struct btrfs_corrupt_block
, cache
);
5938 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks
, free_corrupt_block
);
5940 static void reset_cached_block_groups(struct btrfs_fs_info
*fs_info
)
5942 struct btrfs_block_group_cache
*cache
;
5947 ret
= find_first_extent_bit(&fs_info
->free_space_cache
, 0,
5948 &start
, &end
, EXTENT_DIRTY
);
5951 clear_extent_dirty(&fs_info
->free_space_cache
, start
, end
,
5957 cache
= btrfs_lookup_first_block_group(fs_info
, start
);
5962 start
= cache
->key
.objectid
+ cache
->key
.offset
;
5966 static int check_extent_refs(struct btrfs_trans_handle
*trans
,
5967 struct btrfs_root
*root
,
5968 struct cache_tree
*extent_cache
)
5970 struct extent_record
*rec
;
5971 struct cache_extent
*cache
;
5979 * if we're doing a repair, we have to make sure
5980 * we don't allocate from the problem extents.
5981 * In the worst case, this will be all the
5984 cache
= search_cache_extent(extent_cache
, 0);
5986 rec
= container_of(cache
, struct extent_record
, cache
);
5987 btrfs_pin_extent(root
->fs_info
,
5988 rec
->start
, rec
->max_size
);
5989 cache
= next_cache_extent(cache
);
5992 /* pin down all the corrupted blocks too */
5993 cache
= search_cache_extent(root
->fs_info
->corrupt_blocks
, 0);
5995 btrfs_pin_extent(root
->fs_info
,
5996 cache
->start
, cache
->size
);
5997 cache
= next_cache_extent(cache
);
5999 prune_corrupt_blocks(trans
, root
->fs_info
);
6000 reset_cached_block_groups(root
->fs_info
);
6004 * We need to delete any duplicate entries we find first otherwise we
6005 * could mess up the extent tree when we have backrefs that actually
6006 * belong to a different extent item and not the weird duplicate one.
6008 while (repair
&& !list_empty(&duplicate_extents
)) {
6009 rec
= list_entry(duplicate_extents
.next
, struct extent_record
,
6011 list_del_init(&rec
->list
);
6013 /* Sometimes we can find a backref before we find an actual
6014 * extent, so we need to process it a little bit to see if there
6015 * truly are multiple EXTENT_ITEM_KEY's for the same range, or
6016 * if this is a backref screwup. If we need to delete stuff
6017 * process_duplicates() will return 0, otherwise it will return
6020 if (process_duplicates(root
, extent_cache
, rec
))
6022 ret
= delete_duplicate_records(trans
, root
, rec
);
6026 * delete_duplicate_records will return the number of entries
6027 * deleted, so if it's greater than 0 then we know we actually
6028 * did something and we need to remove.
6039 cache
= search_cache_extent(extent_cache
, 0);
6042 rec
= container_of(cache
, struct extent_record
, cache
);
6043 if (rec
->num_duplicates
) {
6044 fprintf(stderr
, "extent item %llu has multiple extent "
6045 "items\n", (unsigned long long)rec
->start
);
6049 if (rec
->refs
!= rec
->extent_item_refs
) {
6050 fprintf(stderr
, "ref mismatch on [%llu %llu] ",
6051 (unsigned long long)rec
->start
,
6052 (unsigned long long)rec
->nr
);
6053 fprintf(stderr
, "extent item %llu, found %llu\n",
6054 (unsigned long long)rec
->extent_item_refs
,
6055 (unsigned long long)rec
->refs
);
6056 if (!fixed
&& repair
) {
6057 ret
= fixup_extent_refs(trans
, root
->fs_info
,
6066 if (all_backpointers_checked(rec
, 1)) {
6067 fprintf(stderr
, "backpointer mismatch on [%llu %llu]\n",
6068 (unsigned long long)rec
->start
,
6069 (unsigned long long)rec
->nr
);
6071 if (!fixed
&& repair
) {
6072 ret
= fixup_extent_refs(trans
, root
->fs_info
,
6081 if (!rec
->owner_ref_checked
) {
6082 fprintf(stderr
, "owner ref check failed [%llu %llu]\n",
6083 (unsigned long long)rec
->start
,
6084 (unsigned long long)rec
->nr
);
6085 if (!fixed
&& repair
) {
6086 ret
= fixup_extent_refs(trans
, root
->fs_info
,
6095 remove_cache_extent(extent_cache
, cache
);
6096 free_all_extent_backrefs(rec
);
6101 if (ret
&& ret
!= -EAGAIN
) {
6102 fprintf(stderr
, "failed to repair damaged filesystem, aborting\n");
6105 btrfs_fix_block_accounting(trans
, root
);
6108 fprintf(stderr
, "repaired damaged extent references\n");
6114 u64
calc_stripe_length(u64 type
, u64 length
, int num_stripes
)
6118 if (type
& BTRFS_BLOCK_GROUP_RAID0
) {
6119 stripe_size
= length
;
6120 stripe_size
/= num_stripes
;
6121 } else if (type
& BTRFS_BLOCK_GROUP_RAID10
) {
6122 stripe_size
= length
* 2;
6123 stripe_size
/= num_stripes
;
6124 } else if (type
& BTRFS_BLOCK_GROUP_RAID5
) {
6125 stripe_size
= length
;
6126 stripe_size
/= (num_stripes
- 1);
6127 } else if (type
& BTRFS_BLOCK_GROUP_RAID6
) {
6128 stripe_size
= length
;
6129 stripe_size
/= (num_stripes
- 2);
6131 stripe_size
= length
;
6136 static int check_chunk_refs(struct chunk_record
*chunk_rec
,
6137 struct block_group_tree
*block_group_cache
,
6138 struct device_extent_tree
*dev_extent_cache
,
6141 struct cache_extent
*block_group_item
;
6142 struct block_group_record
*block_group_rec
;
6143 struct cache_extent
*dev_extent_item
;
6144 struct device_extent_record
*dev_extent_rec
;
6151 block_group_item
= lookup_cache_extent(&block_group_cache
->tree
,
6154 if (block_group_item
) {
6155 block_group_rec
= container_of(block_group_item
,
6156 struct block_group_record
,
6158 if (chunk_rec
->length
!= block_group_rec
->offset
||
6159 chunk_rec
->offset
!= block_group_rec
->objectid
||
6160 chunk_rec
->type_flags
!= block_group_rec
->flags
) {
6163 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
6164 chunk_rec
->objectid
,
6169 chunk_rec
->type_flags
,
6170 block_group_rec
->objectid
,
6171 block_group_rec
->type
,
6172 block_group_rec
->offset
,
6173 block_group_rec
->offset
,
6174 block_group_rec
->objectid
,
6175 block_group_rec
->flags
);
6178 list_del_init(&block_group_rec
->list
);
6179 chunk_rec
->bg_rec
= block_group_rec
;
6184 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
6185 chunk_rec
->objectid
,
6190 chunk_rec
->type_flags
);
6194 length
= calc_stripe_length(chunk_rec
->type_flags
, chunk_rec
->length
,
6195 chunk_rec
->num_stripes
);
6196 for (i
= 0; i
< chunk_rec
->num_stripes
; ++i
) {
6197 devid
= chunk_rec
->stripes
[i
].devid
;
6198 offset
= chunk_rec
->stripes
[i
].offset
;
6199 dev_extent_item
= lookup_cache_extent2(&dev_extent_cache
->tree
,
6200 devid
, offset
, length
);
6201 if (dev_extent_item
) {
6202 dev_extent_rec
= container_of(dev_extent_item
,
6203 struct device_extent_record
,
6205 if (dev_extent_rec
->objectid
!= devid
||
6206 dev_extent_rec
->offset
!= offset
||
6207 dev_extent_rec
->chunk_offset
!= chunk_rec
->offset
||
6208 dev_extent_rec
->length
!= length
) {
6211 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
6212 chunk_rec
->objectid
,
6215 chunk_rec
->stripes
[i
].devid
,
6216 chunk_rec
->stripes
[i
].offset
,
6217 dev_extent_rec
->objectid
,
6218 dev_extent_rec
->offset
,
6219 dev_extent_rec
->length
);
6222 list_move(&dev_extent_rec
->chunk_list
,
6223 &chunk_rec
->dextents
);
6228 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
6229 chunk_rec
->objectid
,
6232 chunk_rec
->stripes
[i
].devid
,
6233 chunk_rec
->stripes
[i
].offset
);
6240 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
6241 int check_chunks(struct cache_tree
*chunk_cache
,
6242 struct block_group_tree
*block_group_cache
,
6243 struct device_extent_tree
*dev_extent_cache
,
6244 struct list_head
*good
, struct list_head
*bad
, int silent
)
6246 struct cache_extent
*chunk_item
;
6247 struct chunk_record
*chunk_rec
;
6248 struct block_group_record
*bg_rec
;
6249 struct device_extent_record
*dext_rec
;
6253 chunk_item
= first_cache_extent(chunk_cache
);
6254 while (chunk_item
) {
6255 chunk_rec
= container_of(chunk_item
, struct chunk_record
,
6257 err
= check_chunk_refs(chunk_rec
, block_group_cache
,
6258 dev_extent_cache
, silent
);
6262 list_add_tail(&chunk_rec
->list
, bad
);
6265 list_add_tail(&chunk_rec
->list
, good
);
6268 chunk_item
= next_cache_extent(chunk_item
);
6271 list_for_each_entry(bg_rec
, &block_group_cache
->block_groups
, list
) {
6274 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
6282 list_for_each_entry(dext_rec
, &dev_extent_cache
->no_chunk_orphans
,
6286 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
6297 static int check_device_used(struct device_record
*dev_rec
,
6298 struct device_extent_tree
*dext_cache
)
6300 struct cache_extent
*cache
;
6301 struct device_extent_record
*dev_extent_rec
;
6304 cache
= search_cache_extent2(&dext_cache
->tree
, dev_rec
->devid
, 0);
6306 dev_extent_rec
= container_of(cache
,
6307 struct device_extent_record
,
6309 if (dev_extent_rec
->objectid
!= dev_rec
->devid
)
6312 list_del_init(&dev_extent_rec
->device_list
);
6313 total_byte
+= dev_extent_rec
->length
;
6314 cache
= next_cache_extent(cache
);
6317 if (total_byte
!= dev_rec
->byte_used
) {
6319 "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
6320 total_byte
, dev_rec
->byte_used
, dev_rec
->objectid
,
6321 dev_rec
->type
, dev_rec
->offset
);
6328 /* check btrfs_dev_item -> btrfs_dev_extent */
6329 static int check_devices(struct rb_root
*dev_cache
,
6330 struct device_extent_tree
*dev_extent_cache
)
6332 struct rb_node
*dev_node
;
6333 struct device_record
*dev_rec
;
6334 struct device_extent_record
*dext_rec
;
6338 dev_node
= rb_first(dev_cache
);
6340 dev_rec
= container_of(dev_node
, struct device_record
, node
);
6341 err
= check_device_used(dev_rec
, dev_extent_cache
);
6345 dev_node
= rb_next(dev_node
);
6347 list_for_each_entry(dext_rec
, &dev_extent_cache
->no_device_orphans
,
6350 "Device extent[%llu, %llu, %llu] didn't find its device.\n",
6351 dext_rec
->objectid
, dext_rec
->offset
, dext_rec
->length
);
6358 static int check_chunks_and_extents(struct btrfs_root
*root
)
6360 struct rb_root dev_cache
;
6361 struct cache_tree chunk_cache
;
6362 struct block_group_tree block_group_cache
;
6363 struct device_extent_tree dev_extent_cache
;
6364 struct cache_tree extent_cache
;
6365 struct cache_tree seen
;
6366 struct cache_tree pending
;
6367 struct cache_tree reada
;
6368 struct cache_tree nodes
;
6369 struct cache_tree corrupt_blocks
;
6370 struct btrfs_path path
;
6371 struct btrfs_key key
;
6372 struct btrfs_key found_key
;
6375 struct block_info
*bits
;
6377 struct extent_buffer
*leaf
;
6378 struct btrfs_trans_handle
*trans
= NULL
;
6380 struct btrfs_root_item ri
;
6381 struct list_head dropping_trees
;
6383 dev_cache
= RB_ROOT
;
6384 cache_tree_init(&chunk_cache
);
6385 block_group_tree_init(&block_group_cache
);
6386 device_extent_tree_init(&dev_extent_cache
);
6388 cache_tree_init(&extent_cache
);
6389 cache_tree_init(&seen
);
6390 cache_tree_init(&pending
);
6391 cache_tree_init(&nodes
);
6392 cache_tree_init(&reada
);
6393 cache_tree_init(&corrupt_blocks
);
6394 INIT_LIST_HEAD(&dropping_trees
);
6397 trans
= btrfs_start_transaction(root
, 1);
6398 if (IS_ERR(trans
)) {
6399 fprintf(stderr
, "Error starting transaction\n");
6400 return PTR_ERR(trans
);
6402 root
->fs_info
->fsck_extent_cache
= &extent_cache
;
6403 root
->fs_info
->free_extent_hook
= free_extent_hook
;
6404 root
->fs_info
->corrupt_blocks
= &corrupt_blocks
;
6408 bits
= malloc(bits_nr
* sizeof(struct block_info
));
6415 add_root_to_pending(root
->fs_info
->tree_root
->node
,
6416 &extent_cache
, &pending
, &seen
, &nodes
,
6417 &root
->fs_info
->tree_root
->root_key
);
6419 add_root_to_pending(root
->fs_info
->chunk_root
->node
,
6420 &extent_cache
, &pending
, &seen
, &nodes
,
6421 &root
->fs_info
->chunk_root
->root_key
);
6423 btrfs_init_path(&path
);
6426 btrfs_set_key_type(&key
, BTRFS_ROOT_ITEM_KEY
);
6427 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
,
6432 leaf
= path
.nodes
[0];
6433 slot
= path
.slots
[0];
6434 if (slot
>= btrfs_header_nritems(path
.nodes
[0])) {
6435 ret
= btrfs_next_leaf(root
, &path
);
6438 leaf
= path
.nodes
[0];
6439 slot
= path
.slots
[0];
6441 btrfs_item_key_to_cpu(leaf
, &found_key
, path
.slots
[0]);
6442 if (btrfs_key_type(&found_key
) == BTRFS_ROOT_ITEM_KEY
) {
6443 unsigned long offset
;
6444 struct extent_buffer
*buf
;
6446 offset
= btrfs_item_ptr_offset(leaf
, path
.slots
[0]);
6447 read_extent_buffer(leaf
, &ri
, offset
, sizeof(ri
));
6448 if (btrfs_disk_key_objectid(&ri
.drop_progress
) == 0) {
6449 buf
= read_tree_block(root
->fs_info
->tree_root
,
6450 btrfs_root_bytenr(&ri
),
6451 btrfs_level_size(root
,
6452 btrfs_root_level(&ri
)),
6458 add_root_to_pending(buf
, &extent_cache
,
6459 &pending
, &seen
, &nodes
,
6461 free_extent_buffer(buf
);
6463 struct dropping_root_item_record
*dri_rec
;
6464 dri_rec
= malloc(sizeof(*dri_rec
));
6469 memcpy(&dri_rec
->ri
, &ri
, sizeof(ri
));
6470 memcpy(&dri_rec
->found_key
, &found_key
,
6472 list_add_tail(&dri_rec
->list
, &dropping_trees
);
6477 btrfs_release_path(&path
);
6479 ret
= run_next_block(trans
, root
, bits
, bits_nr
, &last
,
6480 &pending
, &seen
, &reada
, &nodes
,
6481 &extent_cache
, &chunk_cache
, &dev_cache
,
6482 &block_group_cache
, &dev_extent_cache
,
6488 while (!list_empty(&dropping_trees
)) {
6489 struct dropping_root_item_record
*rec
;
6490 struct extent_buffer
*buf
;
6491 rec
= list_entry(dropping_trees
.next
,
6492 struct dropping_root_item_record
, list
);
6498 buf
= read_tree_block(root
->fs_info
->tree_root
,
6499 btrfs_root_bytenr(&rec
->ri
),
6500 btrfs_level_size(root
,
6501 btrfs_root_level(&rec
->ri
)), 0);
6506 add_root_to_pending(buf
, &extent_cache
, &pending
,
6507 &seen
, &nodes
, &rec
->found_key
);
6509 ret
= run_next_block(trans
, root
, bits
, bits_nr
, &last
,
6510 &pending
, &seen
, &reada
,
6511 &nodes
, &extent_cache
,
6512 &chunk_cache
, &dev_cache
,
6519 free_extent_buffer(buf
);
6520 list_del(&rec
->list
);
6525 ret
= check_extent_refs(trans
, root
, &extent_cache
);
6526 if (ret
== -EAGAIN
) {
6527 ret
= btrfs_commit_transaction(trans
, root
);
6531 trans
= btrfs_start_transaction(root
, 1);
6532 if (IS_ERR(trans
)) {
6533 ret
= PTR_ERR(trans
);
6537 free_corrupt_blocks_tree(root
->fs_info
->corrupt_blocks
);
6538 free_extent_cache_tree(&seen
);
6539 free_extent_cache_tree(&pending
);
6540 free_extent_cache_tree(&reada
);
6541 free_extent_cache_tree(&nodes
);
6542 free_chunk_cache_tree(&chunk_cache
);
6543 free_block_group_tree(&block_group_cache
);
6544 free_device_cache_tree(&dev_cache
);
6545 free_device_extent_tree(&dev_extent_cache
);
6546 free_extent_record_cache(root
->fs_info
, &extent_cache
);
6550 err
= check_chunks(&chunk_cache
, &block_group_cache
,
6551 &dev_extent_cache
, NULL
, NULL
, 0);
6555 err
= check_devices(&dev_cache
, &dev_extent_cache
);
6561 err
= btrfs_commit_transaction(trans
, root
);
6566 free_corrupt_blocks_tree(root
->fs_info
->corrupt_blocks
);
6567 root
->fs_info
->fsck_extent_cache
= NULL
;
6568 root
->fs_info
->free_extent_hook
= NULL
;
6569 root
->fs_info
->corrupt_blocks
= NULL
;
6572 free_chunk_cache_tree(&chunk_cache
);
6573 free_device_cache_tree(&dev_cache
);
6574 free_block_group_tree(&block_group_cache
);
6575 free_device_extent_tree(&dev_extent_cache
);
6576 free_extent_cache_tree(&seen
);
6577 free_extent_cache_tree(&pending
);
6578 free_extent_cache_tree(&reada
);
6579 free_extent_cache_tree(&nodes
);
6583 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle
*trans
,
6584 struct btrfs_root
*root
, int overwrite
)
6586 struct extent_buffer
*c
;
6587 struct extent_buffer
*old
= root
->node
;
6590 struct btrfs_disk_key disk_key
= {0,0,0};
6596 extent_buffer_get(c
);
6599 c
= btrfs_alloc_free_block(trans
, root
,
6600 btrfs_level_size(root
, 0),
6601 root
->root_key
.objectid
,
6602 &disk_key
, level
, 0, 0);
6605 extent_buffer_get(c
);
6609 memset_extent_buffer(c
, 0, 0, sizeof(struct btrfs_header
));
6610 btrfs_set_header_level(c
, level
);
6611 btrfs_set_header_bytenr(c
, c
->start
);
6612 btrfs_set_header_generation(c
, trans
->transid
);
6613 btrfs_set_header_backref_rev(c
, BTRFS_MIXED_BACKREF_REV
);
6614 btrfs_set_header_owner(c
, root
->root_key
.objectid
);
6616 write_extent_buffer(c
, root
->fs_info
->fsid
,
6617 btrfs_header_fsid(), BTRFS_FSID_SIZE
);
6619 write_extent_buffer(c
, root
->fs_info
->chunk_tree_uuid
,
6620 btrfs_header_chunk_tree_uuid(c
),
6623 btrfs_mark_buffer_dirty(c
);
6625 * this case can happen in the following case:
6627 * 1.overwrite previous root.
6629 * 2.reinit reloc data root, this is because we skip pin
6630 * down reloc data tree before which means we can allocate
6631 * same block bytenr here.
6633 if (old
->start
== c
->start
) {
6634 btrfs_set_root_generation(&root
->root_item
,
6636 root
->root_item
.level
= btrfs_header_level(root
->node
);
6637 ret
= btrfs_update_root(trans
, root
->fs_info
->tree_root
,
6638 &root
->root_key
, &root
->root_item
);
6640 free_extent_buffer(c
);
6644 free_extent_buffer(old
);
6646 add_root_to_dirty_list(root
);
6650 static int pin_down_tree_blocks(struct btrfs_fs_info
*fs_info
,
6651 struct extent_buffer
*eb
, int tree_root
)
6653 struct extent_buffer
*tmp
;
6654 struct btrfs_root_item
*ri
;
6655 struct btrfs_key key
;
6658 int level
= btrfs_header_level(eb
);
6664 * If we have pinned this block before, don't pin it again.
6665 * This can not only avoid forever loop with broken filesystem
6666 * but also give us some speedups.
6668 if (test_range_bit(&fs_info
->pinned_extents
, eb
->start
,
6669 eb
->start
+ eb
->len
- 1, EXTENT_DIRTY
, 0))
6672 btrfs_pin_extent(fs_info
, eb
->start
, eb
->len
);
6674 leafsize
= btrfs_super_leafsize(fs_info
->super_copy
);
6675 nritems
= btrfs_header_nritems(eb
);
6676 for (i
= 0; i
< nritems
; i
++) {
6678 btrfs_item_key_to_cpu(eb
, &key
, i
);
6679 if (key
.type
!= BTRFS_ROOT_ITEM_KEY
)
6681 /* Skip the extent root and reloc roots */
6682 if (key
.objectid
== BTRFS_EXTENT_TREE_OBJECTID
||
6683 key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
||
6684 key
.objectid
== BTRFS_DATA_RELOC_TREE_OBJECTID
)
6686 ri
= btrfs_item_ptr(eb
, i
, struct btrfs_root_item
);
6687 bytenr
= btrfs_disk_root_bytenr(eb
, ri
);
6690 * If at any point we start needing the real root we
6691 * will have to build a stump root for the root we are
6692 * in, but for now this doesn't actually use the root so
6693 * just pass in extent_root.
6695 tmp
= read_tree_block(fs_info
->extent_root
, bytenr
,
6698 fprintf(stderr
, "Error reading root block\n");
6701 ret
= pin_down_tree_blocks(fs_info
, tmp
, 0);
6702 free_extent_buffer(tmp
);
6706 bytenr
= btrfs_node_blockptr(eb
, i
);
6708 /* If we aren't the tree root don't read the block */
6709 if (level
== 1 && !tree_root
) {
6710 btrfs_pin_extent(fs_info
, bytenr
, leafsize
);
6714 tmp
= read_tree_block(fs_info
->extent_root
, bytenr
,
6717 fprintf(stderr
, "Error reading tree block\n");
6720 ret
= pin_down_tree_blocks(fs_info
, tmp
, tree_root
);
6721 free_extent_buffer(tmp
);
6730 static int pin_metadata_blocks(struct btrfs_fs_info
*fs_info
)
6734 ret
= pin_down_tree_blocks(fs_info
, fs_info
->chunk_root
->node
, 0);
6738 return pin_down_tree_blocks(fs_info
, fs_info
->tree_root
->node
, 1);
6741 static int reset_block_groups(struct btrfs_fs_info
*fs_info
)
6743 struct btrfs_block_group_cache
*cache
;
6744 struct btrfs_path
*path
;
6745 struct extent_buffer
*leaf
;
6746 struct btrfs_chunk
*chunk
;
6747 struct btrfs_key key
;
6751 path
= btrfs_alloc_path();
6756 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
6759 ret
= btrfs_search_slot(NULL
, fs_info
->chunk_root
, &key
, path
, 0, 0);
6761 btrfs_free_path(path
);
6766 * We do this in case the block groups were screwed up and had alloc
6767 * bits that aren't actually set on the chunks. This happens with
6768 * restored images every time and could happen in real life I guess.
6770 fs_info
->avail_data_alloc_bits
= 0;
6771 fs_info
->avail_metadata_alloc_bits
= 0;
6772 fs_info
->avail_system_alloc_bits
= 0;
6774 /* First we need to create the in-memory block groups */
6776 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
6777 ret
= btrfs_next_leaf(fs_info
->chunk_root
, path
);
6779 btrfs_free_path(path
);
6787 leaf
= path
->nodes
[0];
6788 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
6789 if (key
.type
!= BTRFS_CHUNK_ITEM_KEY
) {
6794 chunk
= btrfs_item_ptr(leaf
, path
->slots
[0],
6795 struct btrfs_chunk
);
6796 btrfs_add_block_group(fs_info
, 0,
6797 btrfs_chunk_type(leaf
, chunk
),
6798 key
.objectid
, key
.offset
,
6799 btrfs_chunk_length(leaf
, chunk
));
6800 set_extent_dirty(&fs_info
->free_space_cache
, key
.offset
,
6801 key
.offset
+ btrfs_chunk_length(leaf
, chunk
),
6807 cache
= btrfs_lookup_first_block_group(fs_info
, start
);
6811 start
= cache
->key
.objectid
+ cache
->key
.offset
;
6814 btrfs_free_path(path
);
6818 static int reset_balance(struct btrfs_trans_handle
*trans
,
6819 struct btrfs_fs_info
*fs_info
)
6821 struct btrfs_root
*root
= fs_info
->tree_root
;
6822 struct btrfs_path
*path
;
6823 struct extent_buffer
*leaf
;
6824 struct btrfs_key key
;
6825 int del_slot
, del_nr
= 0;
6829 path
= btrfs_alloc_path();
6833 key
.objectid
= BTRFS_BALANCE_OBJECTID
;
6834 key
.type
= BTRFS_BALANCE_ITEM_KEY
;
6837 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
6842 goto reinit_data_reloc
;
6847 ret
= btrfs_del_item(trans
, root
, path
);
6850 btrfs_release_path(path
);
6852 key
.objectid
= BTRFS_TREE_RELOC_OBJECTID
;
6853 key
.type
= BTRFS_ROOT_ITEM_KEY
;
6856 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
6860 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
6865 ret
= btrfs_del_items(trans
, root
, path
,
6872 btrfs_release_path(path
);
6875 ret
= btrfs_search_slot(trans
, root
, &key
, path
,
6882 leaf
= path
->nodes
[0];
6883 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
6884 if (key
.objectid
> BTRFS_TREE_RELOC_OBJECTID
)
6886 if (key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
6891 del_slot
= path
->slots
[0];
6900 ret
= btrfs_del_items(trans
, root
, path
, del_slot
, del_nr
);
6904 btrfs_release_path(path
);
6907 key
.objectid
= BTRFS_DATA_RELOC_TREE_OBJECTID
;
6908 key
.type
= BTRFS_ROOT_ITEM_KEY
;
6909 key
.offset
= (u64
)-1;
6910 root
= btrfs_read_fs_root(fs_info
, &key
);
6912 fprintf(stderr
, "Error reading data reloc tree\n");
6913 return PTR_ERR(root
);
6915 record_root_in_trans(trans
, root
);
6916 ret
= btrfs_fsck_reinit_root(trans
, root
, 0);
6919 ret
= btrfs_make_root_dir(trans
, root
, BTRFS_FIRST_FREE_OBJECTID
);
6921 btrfs_free_path(path
);
6925 static int reinit_extent_tree(struct btrfs_trans_handle
*trans
,
6926 struct btrfs_fs_info
*fs_info
)
6932 * The only reason we don't do this is because right now we're just
6933 * walking the trees we find and pinning down their bytes, we don't look
6934 * at any of the leaves. In order to do mixed groups we'd have to check
6935 * the leaves of any fs roots and pin down the bytes for any file
6936 * extents we find. Not hard but why do it if we don't have to?
6938 if (btrfs_fs_incompat(fs_info
, BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS
)) {
6939 fprintf(stderr
, "We don't support re-initing the extent tree "
6940 "for mixed block groups yet, please notify a btrfs "
6941 "developer you want to do this so they can add this "
6942 "functionality.\n");
6947 * first we need to walk all of the trees except the extent tree and pin
6948 * down the bytes that are in use so we don't overwrite any existing
6951 ret
= pin_metadata_blocks(fs_info
);
6953 fprintf(stderr
, "error pinning down used bytes\n");
6958 * Need to drop all the block groups since we're going to recreate all
6961 btrfs_free_block_groups(fs_info
);
6962 ret
= reset_block_groups(fs_info
);
6964 fprintf(stderr
, "error resetting the block groups\n");
6968 /* Ok we can allocate now, reinit the extent root */
6969 ret
= btrfs_fsck_reinit_root(trans
, fs_info
->extent_root
, 0);
6971 fprintf(stderr
, "extent root initialization failed\n");
6973 * When the transaction code is updated we should end the
6974 * transaction, but for now progs only knows about commit so
6975 * just return an error.
6981 * Now we have all the in-memory block groups setup so we can make
6982 * allocations properly, and the metadata we care about is safe since we
6983 * pinned all of it above.
6986 struct btrfs_block_group_cache
*cache
;
6988 cache
= btrfs_lookup_first_block_group(fs_info
, start
);
6991 start
= cache
->key
.objectid
+ cache
->key
.offset
;
6992 ret
= btrfs_insert_item(trans
, fs_info
->extent_root
,
6993 &cache
->key
, &cache
->item
,
6994 sizeof(cache
->item
));
6996 fprintf(stderr
, "Error adding block group\n");
6999 btrfs_extent_post_op(trans
, fs_info
->extent_root
);
7002 ret
= reset_balance(trans
, fs_info
);
7004 fprintf(stderr
, "error reseting the pending balance\n");
7009 static int recow_extent_buffer(struct btrfs_root
*root
, struct extent_buffer
*eb
)
7011 struct btrfs_path
*path
;
7012 struct btrfs_trans_handle
*trans
;
7013 struct btrfs_key key
;
7016 printf("Recowing metadata block %llu\n", eb
->start
);
7017 key
.objectid
= btrfs_header_owner(eb
);
7018 key
.type
= BTRFS_ROOT_ITEM_KEY
;
7019 key
.offset
= (u64
)-1;
7021 root
= btrfs_read_fs_root(root
->fs_info
, &key
);
7023 fprintf(stderr
, "Couldn't find owner root %llu\n",
7025 return PTR_ERR(root
);
7028 path
= btrfs_alloc_path();
7032 trans
= btrfs_start_transaction(root
, 1);
7033 if (IS_ERR(trans
)) {
7034 btrfs_free_path(path
);
7035 return PTR_ERR(trans
);
7038 path
->lowest_level
= btrfs_header_level(eb
);
7039 if (path
->lowest_level
)
7040 btrfs_node_key_to_cpu(eb
, &key
, 0);
7042 btrfs_item_key_to_cpu(eb
, &key
, 0);
7044 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
7045 btrfs_commit_transaction(trans
, root
);
7046 btrfs_free_path(path
);
7050 static int delete_bad_item(struct btrfs_root
*root
, struct bad_item
*bad
)
7052 struct btrfs_path
*path
;
7053 struct btrfs_trans_handle
*trans
;
7054 struct btrfs_key key
;
7057 printf("Deleting bad item [%llu,%u,%llu]\n", bad
->key
.objectid
,
7058 bad
->key
.type
, bad
->key
.offset
);
7059 key
.objectid
= bad
->root_id
;
7060 key
.type
= BTRFS_ROOT_ITEM_KEY
;
7061 key
.offset
= (u64
)-1;
7063 root
= btrfs_read_fs_root(root
->fs_info
, &key
);
7065 fprintf(stderr
, "Couldn't find owner root %llu\n",
7067 return PTR_ERR(root
);
7070 path
= btrfs_alloc_path();
7074 trans
= btrfs_start_transaction(root
, 1);
7075 if (IS_ERR(trans
)) {
7076 btrfs_free_path(path
);
7077 return PTR_ERR(trans
);
7080 ret
= btrfs_search_slot(trans
, root
, &bad
->key
, path
, -1, 1);
7086 ret
= btrfs_del_item(trans
, root
, path
);
7088 btrfs_commit_transaction(trans
, root
);
7089 btrfs_free_path(path
);
7093 static int zero_log_tree(struct btrfs_root
*root
)
7095 struct btrfs_trans_handle
*trans
;
7098 trans
= btrfs_start_transaction(root
, 1);
7099 if (IS_ERR(trans
)) {
7100 ret
= PTR_ERR(trans
);
7103 btrfs_set_super_log_root(root
->fs_info
->super_copy
, 0);
7104 btrfs_set_super_log_root_level(root
->fs_info
->super_copy
, 0);
7105 ret
= btrfs_commit_transaction(trans
, root
);
7109 static int populate_csum(struct btrfs_trans_handle
*trans
,
7110 struct btrfs_root
*csum_root
, char *buf
, u64 start
,
7117 while (offset
< len
) {
7118 sectorsize
= csum_root
->sectorsize
;
7119 ret
= read_extent_data(csum_root
, buf
, start
+ offset
,
7123 ret
= btrfs_csum_file_block(trans
, csum_root
, start
+ len
,
7124 start
+ offset
, buf
, sectorsize
);
7127 offset
+= sectorsize
;
7132 static int fill_csum_tree(struct btrfs_trans_handle
*trans
,
7133 struct btrfs_root
*csum_root
)
7135 struct btrfs_root
*extent_root
= csum_root
->fs_info
->extent_root
;
7136 struct btrfs_path
*path
;
7137 struct btrfs_extent_item
*ei
;
7138 struct extent_buffer
*leaf
;
7140 struct btrfs_key key
;
7143 path
= btrfs_alloc_path();
7148 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
7151 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, path
, 0, 0);
7153 btrfs_free_path(path
);
7157 buf
= malloc(csum_root
->sectorsize
);
7159 btrfs_free_path(path
);
7164 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
7165 ret
= btrfs_next_leaf(extent_root
, path
);
7173 leaf
= path
->nodes
[0];
7175 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
7176 if (key
.type
!= BTRFS_EXTENT_ITEM_KEY
) {
7181 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
7182 struct btrfs_extent_item
);
7183 if (!(btrfs_extent_flags(leaf
, ei
) &
7184 BTRFS_EXTENT_FLAG_DATA
)) {
7189 ret
= populate_csum(trans
, csum_root
, buf
, key
.objectid
,
7196 btrfs_free_path(path
);
7201 struct root_item_info
{
7202 /* level of the root */
7204 /* number of nodes at this level, must be 1 for a root */
7208 struct cache_extent cache_extent
;
7211 static struct cache_tree
*roots_info_cache
= NULL
;
7213 static void free_roots_info_cache(void)
7215 if (!roots_info_cache
)
7218 while (!cache_tree_empty(roots_info_cache
)) {
7219 struct cache_extent
*entry
;
7220 struct root_item_info
*rii
;
7222 entry
= first_cache_extent(roots_info_cache
);
7223 remove_cache_extent(roots_info_cache
, entry
);
7224 rii
= container_of(entry
, struct root_item_info
, cache_extent
);
7228 free(roots_info_cache
);
7229 roots_info_cache
= NULL
;
7232 static int build_roots_info_cache(struct btrfs_fs_info
*info
)
7235 struct btrfs_key key
;
7236 struct extent_buffer
*leaf
;
7237 struct btrfs_path
*path
;
7239 if (!roots_info_cache
) {
7240 roots_info_cache
= malloc(sizeof(*roots_info_cache
));
7241 if (!roots_info_cache
)
7243 cache_tree_init(roots_info_cache
);
7246 path
= btrfs_alloc_path();
7251 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
7254 ret
= btrfs_search_slot(NULL
, info
->extent_root
, &key
, path
, 0, 0);
7257 leaf
= path
->nodes
[0];
7260 struct btrfs_key found_key
;
7261 struct btrfs_extent_item
*ei
;
7262 struct btrfs_extent_inline_ref
*iref
;
7263 int slot
= path
->slots
[0];
7268 struct cache_extent
*entry
;
7269 struct root_item_info
*rii
;
7271 if (slot
>= btrfs_header_nritems(leaf
)) {
7272 ret
= btrfs_next_leaf(info
->extent_root
, path
);
7279 leaf
= path
->nodes
[0];
7280 slot
= path
->slots
[0];
7283 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0]);
7285 if (found_key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
7286 found_key
.type
!= BTRFS_METADATA_ITEM_KEY
)
7289 ei
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_item
);
7290 flags
= btrfs_extent_flags(leaf
, ei
);
7292 if (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
&&
7293 !(flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
))
7296 if (found_key
.type
== BTRFS_METADATA_ITEM_KEY
) {
7297 iref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
7298 level
= found_key
.offset
;
7300 struct btrfs_tree_block_info
*info
;
7302 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
7303 iref
= (struct btrfs_extent_inline_ref
*)(info
+ 1);
7304 level
= btrfs_tree_block_level(leaf
, info
);
7308 * For a root extent, it must be of the following type and the
7309 * first (and only one) iref in the item.
7311 type
= btrfs_extent_inline_ref_type(leaf
, iref
);
7312 if (type
!= BTRFS_TREE_BLOCK_REF_KEY
)
7315 root_id
= btrfs_extent_inline_ref_offset(leaf
, iref
);
7316 entry
= lookup_cache_extent(roots_info_cache
, root_id
, 1);
7318 rii
= malloc(sizeof(struct root_item_info
));
7323 rii
->cache_extent
.start
= root_id
;
7324 rii
->cache_extent
.size
= 1;
7325 rii
->level
= (u8
)-1;
7326 entry
= &rii
->cache_extent
;
7327 ret
= insert_cache_extent(roots_info_cache
, entry
);
7330 rii
= container_of(entry
, struct root_item_info
,
7334 ASSERT(rii
->cache_extent
.start
== root_id
);
7335 ASSERT(rii
->cache_extent
.size
== 1);
7337 if (level
> rii
->level
|| rii
->level
== (u8
)-1) {
7339 rii
->bytenr
= found_key
.objectid
;
7340 rii
->gen
= btrfs_extent_generation(leaf
, ei
);
7341 rii
->node_count
= 1;
7342 } else if (level
== rii
->level
) {
7350 btrfs_free_path(path
);
7355 static int maybe_repair_root_item(struct btrfs_fs_info
*info
,
7356 struct btrfs_path
*path
,
7357 const struct btrfs_key
*root_key
,
7358 const int read_only_mode
)
7360 const u64 root_id
= root_key
->objectid
;
7361 struct cache_extent
*entry
;
7362 struct root_item_info
*rii
;
7363 struct btrfs_root_item ri
;
7364 unsigned long offset
;
7366 entry
= lookup_cache_extent(roots_info_cache
, root_id
, 1);
7369 "Error: could not find extent items for root %llu\n",
7370 root_key
->objectid
);
7374 rii
= container_of(entry
, struct root_item_info
, cache_extent
);
7375 ASSERT(rii
->cache_extent
.start
== root_id
);
7376 ASSERT(rii
->cache_extent
.size
== 1);
7378 if (rii
->node_count
!= 1) {
7380 "Error: could not find btree root extent for root %llu\n",
7385 offset
= btrfs_item_ptr_offset(path
->nodes
[0], path
->slots
[0]);
7386 read_extent_buffer(path
->nodes
[0], &ri
, offset
, sizeof(ri
));
7388 if (btrfs_root_bytenr(&ri
) != rii
->bytenr
||
7389 btrfs_root_level(&ri
) != rii
->level
||
7390 btrfs_root_generation(&ri
) != rii
->gen
) {
7393 * If we're in repair mode but our caller told us to not update
7394 * the root item, i.e. just check if it needs to be updated, don't
7395 * print this message, since the caller will call us again shortly
7396 * for the same root item without read only mode (the caller will
7397 * open a transaction first).
7399 if (!(read_only_mode
&& repair
))
7401 "%sroot item for root %llu,"
7402 " current bytenr %llu, current gen %llu, current level %u,"
7403 " new bytenr %llu, new gen %llu, new level %u\n",
7404 (read_only_mode
? "" : "fixing "),
7406 btrfs_root_bytenr(&ri
), btrfs_root_generation(&ri
),
7407 btrfs_root_level(&ri
),
7408 rii
->bytenr
, rii
->gen
, rii
->level
);
7410 if (btrfs_root_generation(&ri
) > rii
->gen
) {
7412 "root %llu has a root item with a more recent gen (%llu) compared to the found root node (%llu)\n",
7413 root_id
, btrfs_root_generation(&ri
), rii
->gen
);
7417 if (!read_only_mode
) {
7418 btrfs_set_root_bytenr(&ri
, rii
->bytenr
);
7419 btrfs_set_root_level(&ri
, rii
->level
);
7420 btrfs_set_root_generation(&ri
, rii
->gen
);
7421 write_extent_buffer(path
->nodes
[0], &ri
,
7422 offset
, sizeof(ri
));
7432 * A regression introduced in the 3.17 kernel (more specifically in 3.17-rc2),
7433 * caused read-only snapshots to be corrupted if they were created at a moment
7434 * when the source subvolume/snapshot had orphan items. The issue was that the
7435 * on-disk root items became incorrect, referring to the pre orphan cleanup root
7436 * node instead of the post orphan cleanup root node.
7437 * So this function, and its callees, just detects and fixes those cases. Even
7438 * though the regression was for read-only snapshots, this function applies to
7439 * any snapshot/subvolume root.
7440 * This must be run before any other repair code - not doing it so, makes other
7441 * repair code delete or modify backrefs in the extent tree for example, which
7442 * will result in an inconsistent fs after repairing the root items.
7444 static int repair_root_items(struct btrfs_fs_info
*info
)
7446 struct btrfs_path
*path
= NULL
;
7447 struct btrfs_key key
;
7448 struct extent_buffer
*leaf
;
7449 struct btrfs_trans_handle
*trans
= NULL
;
7454 ret
= build_roots_info_cache(info
);
7458 path
= btrfs_alloc_path();
7464 key
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
7465 key
.type
= BTRFS_ROOT_ITEM_KEY
;
7470 * Avoid opening and committing transactions if a leaf doesn't have
7471 * any root items that need to be fixed, so that we avoid rotating
7472 * backup roots unnecessarily.
7475 trans
= btrfs_start_transaction(info
->tree_root
, 1);
7476 if (IS_ERR(trans
)) {
7477 ret
= PTR_ERR(trans
);
7482 ret
= btrfs_search_slot(trans
, info
->tree_root
, &key
, path
,
7486 leaf
= path
->nodes
[0];
7489 struct btrfs_key found_key
;
7491 if (path
->slots
[0] >= btrfs_header_nritems(leaf
)) {
7492 int no_more_keys
= find_next_key(path
, &key
);
7494 btrfs_release_path(path
);
7496 ret
= btrfs_commit_transaction(trans
,
7508 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0]);
7510 if (found_key
.type
!= BTRFS_ROOT_ITEM_KEY
)
7513 ret
= maybe_repair_root_item(info
, path
, &found_key
,
7518 if (!trans
&& repair
) {
7521 btrfs_release_path(path
);
7531 free_roots_info_cache();
7533 btrfs_free_path(path
);
7540 static struct option long_options
[] = {
7541 { "super", 1, NULL
, 's' },
7542 { "repair", 0, NULL
, 0 },
7543 { "init-csum-tree", 0, NULL
, 0 },
7544 { "init-extent-tree", 0, NULL
, 0 },
7545 { "check-data-csum", 0, NULL
, 0 },
7546 { "backup", 0, NULL
, 0 },
7547 { "subvol-extents", 1, NULL
, 'E' },
7548 { "qgroup-report", 0, NULL
, 'Q' },
7552 const char * const cmd_check_usage
[] = {
7553 "btrfs check [options] <device>",
7554 "Check an unmounted btrfs filesystem.",
7556 "-s|--super <superblock> use this superblock copy",
7557 "-b|--backup use the backup root copy",
7558 "--repair try to repair the filesystem",
7559 "--init-csum-tree create a new CRC tree",
7560 "--init-extent-tree create a new extent tree",
7561 "--check-data-csum verify checkums of data blocks",
7562 "--qgroup-report print a report on qgroup consistency",
7563 "--subvol-extents <subvolid> print subvolume extents and sharing state",
7567 int cmd_check(int argc
, char **argv
)
7569 struct cache_tree root_cache
;
7570 struct btrfs_root
*root
;
7571 struct btrfs_fs_info
*info
;
7574 char uuidbuf
[BTRFS_UUID_UNPARSED_SIZE
];
7577 int option_index
= 0;
7578 int init_csum_tree
= 0;
7579 int qgroup_report
= 0;
7580 enum btrfs_open_ctree_flags ctree_flags
= OPEN_CTREE_EXCLUSIVE
;
7584 c
= getopt_long(argc
, argv
, "as:b", long_options
,
7589 case 'a': /* ignored */ break;
7591 ctree_flags
|= OPEN_CTREE_BACKUP_ROOT
;
7594 num
= arg_strtou64(optarg
);
7595 if (num
>= BTRFS_SUPER_MIRROR_MAX
) {
7597 "ERROR: super mirror should be less than: %d\n",
7598 BTRFS_SUPER_MIRROR_MAX
);
7601 bytenr
= btrfs_sb_offset(((int)num
));
7602 printf("using SB copy %llu, bytenr %llu\n", num
,
7603 (unsigned long long)bytenr
);
7609 subvolid
= arg_strtou64(optarg
);
7613 usage(cmd_check_usage
);
7615 if (option_index
== 1) {
7616 printf("enabling repair mode\n");
7618 ctree_flags
|= OPEN_CTREE_WRITES
;
7619 } else if (option_index
== 2) {
7620 printf("Creating a new CRC tree\n");
7623 ctree_flags
|= OPEN_CTREE_WRITES
;
7624 } else if (option_index
== 3) {
7625 init_extent_tree
= 1;
7626 ctree_flags
|= (OPEN_CTREE_WRITES
|
7627 OPEN_CTREE_NO_BLOCK_GROUPS
);
7629 } else if (option_index
== 4) {
7630 check_data_csum
= 1;
7633 argc
= argc
- optind
;
7635 if (check_argc_exact(argc
, 1))
7636 usage(cmd_check_usage
);
7639 cache_tree_init(&root_cache
);
7641 if((ret
= check_mounted(argv
[optind
])) < 0) {
7642 fprintf(stderr
, "Could not check mount status: %s\n", strerror(-ret
));
7645 fprintf(stderr
, "%s is currently mounted. Aborting.\n", argv
[optind
]);
7650 /* only allow partial opening under repair mode */
7652 ctree_flags
|= OPEN_CTREE_PARTIAL
;
7654 info
= open_ctree_fs_info(argv
[optind
], bytenr
, 0, ctree_flags
);
7656 fprintf(stderr
, "Couldn't open file system\n");
7661 root
= info
->fs_root
;
7663 ret
= repair_root_items(info
);
7667 fprintf(stderr
, "Fixed %d roots.\n", ret
);
7669 } else if (ret
> 0) {
7671 "Found %d roots with an outdated root item.\n",
7674 "Please run a filesystem check with the option --repair to fix them.\n");
7680 * repair mode will force us to commit transaction which
7681 * will make us fail to load log tree when mounting.
7683 if (repair
&& btrfs_super_log_root(info
->super_copy
)) {
7684 ret
= ask_user("repair mode will force to clear out log tree, Are you sure?");
7689 ret
= zero_log_tree(root
);
7691 fprintf(stderr
, "fail to zero log tree\n");
7696 uuid_unparse(info
->super_copy
->fsid
, uuidbuf
);
7697 if (qgroup_report
) {
7698 printf("Print quota groups for %s\nUUID: %s\n", argv
[optind
],
7700 ret
= qgroup_verify_all(info
);
7702 print_qgroup_report(1);
7706 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
7707 subvolid
, argv
[optind
], uuidbuf
);
7708 ret
= print_extent_state(info
, subvolid
);
7711 printf("Checking filesystem on %s\nUUID: %s\n", argv
[optind
], uuidbuf
);
7713 if (!extent_buffer_uptodate(info
->tree_root
->node
) ||
7714 !extent_buffer_uptodate(info
->dev_root
->node
) ||
7715 !extent_buffer_uptodate(info
->chunk_root
->node
)) {
7716 fprintf(stderr
, "Critical roots corrupted, unable to fsck the FS\n");
7721 if (init_extent_tree
|| init_csum_tree
) {
7722 struct btrfs_trans_handle
*trans
;
7724 trans
= btrfs_start_transaction(info
->extent_root
, 0);
7725 if (IS_ERR(trans
)) {
7726 fprintf(stderr
, "Error starting transaction\n");
7727 ret
= PTR_ERR(trans
);
7731 if (init_extent_tree
) {
7732 printf("Creating a new extent tree\n");
7733 ret
= reinit_extent_tree(trans
, info
);
7738 if (init_csum_tree
) {
7739 fprintf(stderr
, "Reinit crc root\n");
7740 ret
= btrfs_fsck_reinit_root(trans
, info
->csum_root
, 0);
7742 fprintf(stderr
, "crc root initialization failed\n");
7747 ret
= fill_csum_tree(trans
, info
->csum_root
);
7749 fprintf(stderr
, "crc refilling failed\n");
7754 * Ok now we commit and run the normal fsck, which will add
7755 * extent entries for all of the items it finds.
7757 ret
= btrfs_commit_transaction(trans
, info
->extent_root
);
7761 if (!extent_buffer_uptodate(info
->extent_root
->node
)) {
7762 fprintf(stderr
, "Critical roots corrupted, unable to fsck the FS\n");
7766 if (!extent_buffer_uptodate(info
->csum_root
->node
)) {
7767 fprintf(stderr
, "Checksum root corrupted, rerun with --init-csum-tree option\n");
7772 fprintf(stderr
, "checking extents\n");
7773 ret
= check_chunks_and_extents(root
);
7775 fprintf(stderr
, "Errors found in extent allocation tree or chunk allocation\n");
7777 fprintf(stderr
, "checking free space cache\n");
7778 ret
= check_space_cache(root
);
7783 * We used to have to have these hole extents in between our real
7784 * extents so if we don't have this flag set we need to make sure there
7785 * are no gaps in the file extents for inodes, otherwise we can just
7786 * ignore it when this happens.
7788 no_holes
= btrfs_fs_incompat(root
->fs_info
,
7789 BTRFS_FEATURE_INCOMPAT_NO_HOLES
);
7790 fprintf(stderr
, "checking fs roots\n");
7791 ret
= check_fs_roots(root
, &root_cache
);
7795 fprintf(stderr
, "checking csums\n");
7796 ret
= check_csums(root
);
7800 fprintf(stderr
, "checking root refs\n");
7801 ret
= check_root_refs(root
, &root_cache
);
7805 while (repair
&& !list_empty(&root
->fs_info
->recow_ebs
)) {
7806 struct extent_buffer
*eb
;
7808 eb
= list_first_entry(&root
->fs_info
->recow_ebs
,
7809 struct extent_buffer
, recow
);
7810 list_del_init(&eb
->recow
);
7811 ret
= recow_extent_buffer(root
, eb
);
7816 while (!list_empty(&delete_items
)) {
7817 struct bad_item
*bad
;
7819 bad
= list_first_entry(&delete_items
, struct bad_item
, list
);
7820 list_del_init(&bad
->list
);
7822 ret
= delete_bad_item(root
, bad
);
7826 if (info
->quota_enabled
) {
7828 fprintf(stderr
, "checking quota groups\n");
7829 err
= qgroup_verify_all(info
);
7834 if (!list_empty(&root
->fs_info
->recow_ebs
)) {
7835 fprintf(stderr
, "Transid errors in file system\n");
7839 print_qgroup_report(0);
7840 if (found_old_backref
) { /*
7841 * there was a disk format change when mixed
7842 * backref was in testing tree. The old format
7843 * existed about one week.
7845 printf("\n * Found old mixed backref format. "
7846 "The old format is not supported! *"
7847 "\n * Please mount the FS in readonly mode, "
7848 "backup data and re-format the FS. *\n\n");
7851 printf("found %llu bytes used err is %d\n",
7852 (unsigned long long)bytes_used
, ret
);
7853 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes
);
7854 printf("total tree bytes: %llu\n",
7855 (unsigned long long)total_btree_bytes
);
7856 printf("total fs tree bytes: %llu\n",
7857 (unsigned long long)total_fs_tree_bytes
);
7858 printf("total extent tree bytes: %llu\n",
7859 (unsigned long long)total_extent_tree_bytes
);
7860 printf("btree space waste bytes: %llu\n",
7861 (unsigned long long)btree_space_waste
);
7862 printf("file data blocks allocated: %llu\n referenced %llu\n",
7863 (unsigned long long)data_bytes_allocated
,
7864 (unsigned long long)data_bytes_referenced
);
7865 printf("%s\n", BTRFS_BUILD_VERSION
);
7867 free_root_recs_tree(&root_cache
);