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
27 #include "kerncompat.h"
32 #include "print-tree.h"
33 #include "transaction.h"
38 static u64 bytes_used
= 0;
39 static u64 total_csum_bytes
= 0;
40 static u64 total_btree_bytes
= 0;
41 static u64 total_fs_tree_bytes
= 0;
42 static u64 btree_space_waste
= 0;
43 static u64 data_bytes_allocated
= 0;
44 static u64 data_bytes_referenced
= 0;
45 static int found_old_backref
= 0;
47 struct extent_backref
{
48 struct list_head list
;
49 unsigned int is_data
:1;
50 unsigned int found_extent_tree
:1;
51 unsigned int full_backref
:1;
52 unsigned int found_ref
:1;
56 struct extent_backref node
;
68 struct extent_backref node
;
75 struct extent_record
{
76 struct list_head backrefs
;
77 struct cache_extent cache
;
78 struct btrfs_disk_key parent_key
;
87 unsigned int content_checked
:1;
88 unsigned int owner_ref_checked
:1;
89 unsigned int is_root
:1;
92 struct inode_backref
{
93 struct list_head list
;
94 unsigned int found_dir_item
:1;
95 unsigned int found_dir_index
:1;
96 unsigned int found_inode_ref
:1;
97 unsigned int filetype
:8;
105 #define REF_ERR_NO_DIR_ITEM (1 << 0)
106 #define REF_ERR_NO_DIR_INDEX (1 << 1)
107 #define REF_ERR_NO_INODE_REF (1 << 2)
108 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
109 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
110 #define REF_ERR_DUP_INODE_REF (1 << 5)
111 #define REF_ERR_INDEX_UNMATCH (1 << 6)
112 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
113 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
114 #define REF_ERR_NO_ROOT_REF (1 << 9)
115 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
116 #define REF_ERR_DUP_ROOT_REF (1 << 11)
117 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
119 struct inode_record
{
120 struct list_head backrefs
;
121 unsigned int checked
:1;
122 unsigned int merging
:1;
123 unsigned int found_inode_item
:1;
124 unsigned int found_dir_item
:1;
125 unsigned int found_file_extent
:1;
126 unsigned int found_csum_item
:1;
127 unsigned int some_csum_missing
:1;
128 unsigned int nodatasum
:1;
141 u64 first_extent_gap
;
146 #define I_ERR_NO_INODE_ITEM (1 << 0)
147 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
148 #define I_ERR_DUP_INODE_ITEM (1 << 2)
149 #define I_ERR_DUP_DIR_INDEX (1 << 3)
150 #define I_ERR_ODD_DIR_ITEM (1 << 4)
151 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
152 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
153 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
154 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
155 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
156 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
157 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
158 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
159 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
161 struct root_backref
{
162 struct list_head list
;
163 unsigned int found_dir_item
:1;
164 unsigned int found_dir_index
:1;
165 unsigned int found_back_ref
:1;
166 unsigned int found_forward_ref
:1;
167 unsigned int reachable
:1;
177 struct list_head backrefs
;
178 struct cache_extent cache
;
179 unsigned int found_root_item
:1;
185 struct cache_extent cache
;
190 struct cache_extent cache
;
191 struct cache_tree root_cache
;
192 struct cache_tree inode_cache
;
193 struct inode_record
*current
;
202 struct walk_control
{
203 struct cache_tree shared
;
204 struct shared_node
*nodes
[BTRFS_MAX_LEVEL
];
209 static u8
imode_to_type(u32 imode
)
212 static unsigned char btrfs_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
213 [S_IFREG
>> S_SHIFT
] = BTRFS_FT_REG_FILE
,
214 [S_IFDIR
>> S_SHIFT
] = BTRFS_FT_DIR
,
215 [S_IFCHR
>> S_SHIFT
] = BTRFS_FT_CHRDEV
,
216 [S_IFBLK
>> S_SHIFT
] = BTRFS_FT_BLKDEV
,
217 [S_IFIFO
>> S_SHIFT
] = BTRFS_FT_FIFO
,
218 [S_IFSOCK
>> S_SHIFT
] = BTRFS_FT_SOCK
,
219 [S_IFLNK
>> S_SHIFT
] = BTRFS_FT_SYMLINK
,
222 return btrfs_type_by_mode
[(imode
& S_IFMT
) >> S_SHIFT
];
226 static struct inode_record
*clone_inode_rec(struct inode_record
*orig_rec
)
228 struct inode_record
*rec
;
229 struct inode_backref
*backref
;
230 struct inode_backref
*orig
;
233 rec
= malloc(sizeof(*rec
));
234 memcpy(rec
, orig_rec
, sizeof(*rec
));
236 INIT_LIST_HEAD(&rec
->backrefs
);
238 list_for_each_entry(orig
, &orig_rec
->backrefs
, list
) {
239 size
= sizeof(*orig
) + orig
->namelen
+ 1;
240 backref
= malloc(size
);
241 memcpy(backref
, orig
, size
);
242 list_add_tail(&backref
->list
, &rec
->backrefs
);
247 static struct inode_record
*get_inode_rec(struct cache_tree
*inode_cache
,
250 struct ptr_node
*node
;
251 struct cache_extent
*cache
;
252 struct inode_record
*rec
= NULL
;
255 cache
= find_cache_extent(inode_cache
, ino
, 1);
257 node
= container_of(cache
, struct ptr_node
, cache
);
259 if (mod
&& rec
->refs
> 1) {
260 node
->data
= clone_inode_rec(rec
);
265 rec
= calloc(1, sizeof(*rec
));
267 rec
->extent_start
= (u64
)-1;
268 rec
->first_extent_gap
= (u64
)-1;
270 INIT_LIST_HEAD(&rec
->backrefs
);
272 node
= malloc(sizeof(*node
));
273 node
->cache
.start
= ino
;
274 node
->cache
.size
= 1;
277 if (ino
== BTRFS_FREE_INO_OBJECTID
)
280 ret
= insert_existing_cache_extent(inode_cache
, &node
->cache
);
286 static void free_inode_rec(struct inode_record
*rec
)
288 struct inode_backref
*backref
;
293 while (!list_empty(&rec
->backrefs
)) {
294 backref
= list_entry(rec
->backrefs
.next
,
295 struct inode_backref
, list
);
296 list_del(&backref
->list
);
302 static int can_free_inode_rec(struct inode_record
*rec
)
304 if (!rec
->errors
&& rec
->checked
&& rec
->found_inode_item
&&
305 rec
->nlink
== rec
->found_link
&& list_empty(&rec
->backrefs
))
310 static void maybe_free_inode_rec(struct cache_tree
*inode_cache
,
311 struct inode_record
*rec
)
313 struct cache_extent
*cache
;
314 struct inode_backref
*tmp
, *backref
;
315 struct ptr_node
*node
;
316 unsigned char filetype
;
318 if (!rec
->found_inode_item
)
321 filetype
= imode_to_type(rec
->imode
);
322 list_for_each_entry_safe(backref
, tmp
, &rec
->backrefs
, list
) {
323 if (backref
->found_dir_item
&& backref
->found_dir_index
) {
324 if (backref
->filetype
!= filetype
)
325 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
326 if (!backref
->errors
&& backref
->found_inode_ref
) {
327 list_del(&backref
->list
);
333 if (!rec
->checked
|| rec
->merging
)
336 if (S_ISDIR(rec
->imode
)) {
337 if (rec
->found_size
!= rec
->isize
)
338 rec
->errors
|= I_ERR_DIR_ISIZE_WRONG
;
339 if (rec
->found_file_extent
)
340 rec
->errors
|= I_ERR_ODD_FILE_EXTENT
;
341 } else if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
342 if (rec
->found_dir_item
)
343 rec
->errors
|= I_ERR_ODD_DIR_ITEM
;
344 if (rec
->found_size
!= rec
->nbytes
)
345 rec
->errors
|= I_ERR_FILE_NBYTES_WRONG
;
346 if (rec
->extent_start
== (u64
)-1 || rec
->extent_start
> 0)
347 rec
->first_extent_gap
= 0;
348 if (rec
->nlink
> 0 && (rec
->extent_end
< rec
->isize
||
349 rec
->first_extent_gap
< rec
->isize
))
350 rec
->errors
|= I_ERR_FILE_EXTENT_DISCOUNT
;
353 if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
354 if (rec
->found_csum_item
&& rec
->nodatasum
)
355 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
356 if (rec
->some_csum_missing
&& !rec
->nodatasum
)
357 rec
->errors
|= I_ERR_SOME_CSUM_MISSING
;
360 BUG_ON(rec
->refs
!= 1);
361 if (can_free_inode_rec(rec
)) {
362 cache
= find_cache_extent(inode_cache
, rec
->ino
, 1);
363 node
= container_of(cache
, struct ptr_node
, cache
);
364 BUG_ON(node
->data
!= rec
);
365 remove_cache_extent(inode_cache
, &node
->cache
);
371 static int check_orphan_item(struct btrfs_root
*root
, u64 ino
)
373 struct btrfs_path path
;
374 struct btrfs_key key
;
377 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
378 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
381 btrfs_init_path(&path
);
382 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
383 btrfs_release_path(root
, &path
);
389 static int process_inode_item(struct extent_buffer
*eb
,
390 int slot
, struct btrfs_key
*key
,
391 struct shared_node
*active_node
)
393 struct inode_record
*rec
;
394 struct btrfs_inode_item
*item
;
396 rec
= active_node
->current
;
397 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
398 if (rec
->found_inode_item
) {
399 rec
->errors
|= I_ERR_DUP_INODE_ITEM
;
402 item
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_item
);
403 rec
->nlink
= btrfs_inode_nlink(eb
, item
);
404 rec
->isize
= btrfs_inode_size(eb
, item
);
405 rec
->nbytes
= btrfs_inode_nbytes(eb
, item
);
406 rec
->imode
= btrfs_inode_mode(eb
, item
);
407 if (btrfs_inode_flags(eb
, item
) & BTRFS_INODE_NODATASUM
)
409 rec
->found_inode_item
= 1;
411 rec
->errors
|= I_ERR_NO_ORPHAN_ITEM
;
412 maybe_free_inode_rec(&active_node
->inode_cache
, rec
);
416 static struct inode_backref
*get_inode_backref(struct inode_record
*rec
,
418 int namelen
, u64 dir
)
420 struct inode_backref
*backref
;
422 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
423 if (backref
->dir
!= dir
|| backref
->namelen
!= namelen
)
425 if (memcmp(name
, backref
->name
, namelen
))
430 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
431 memset(backref
, 0, sizeof(*backref
));
433 backref
->namelen
= namelen
;
434 memcpy(backref
->name
, name
, namelen
);
435 backref
->name
[namelen
] = '\0';
436 list_add_tail(&backref
->list
, &rec
->backrefs
);
440 static int add_inode_backref(struct cache_tree
*inode_cache
,
441 u64 ino
, u64 dir
, u64 index
,
442 const char *name
, int namelen
,
443 int filetype
, int itemtype
, int errors
)
445 struct inode_record
*rec
;
446 struct inode_backref
*backref
;
448 rec
= get_inode_rec(inode_cache
, ino
, 1);
449 backref
= get_inode_backref(rec
, name
, namelen
, dir
);
451 backref
->errors
|= errors
;
452 if (itemtype
== BTRFS_DIR_INDEX_KEY
) {
453 if (backref
->found_dir_index
)
454 backref
->errors
|= REF_ERR_DUP_DIR_INDEX
;
455 if (backref
->found_inode_ref
&& backref
->index
!= index
)
456 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
457 if (backref
->found_dir_item
&& backref
->filetype
!= filetype
)
458 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
460 backref
->index
= index
;
461 backref
->filetype
= filetype
;
462 backref
->found_dir_index
= 1;
463 } else if (itemtype
== BTRFS_DIR_ITEM_KEY
) {
465 if (backref
->found_dir_item
)
466 backref
->errors
|= REF_ERR_DUP_DIR_ITEM
;
467 if (backref
->found_dir_index
&& backref
->filetype
!= filetype
)
468 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
470 backref
->filetype
= filetype
;
471 backref
->found_dir_item
= 1;
472 } else if (itemtype
== BTRFS_INODE_REF_KEY
) {
473 if (backref
->found_inode_ref
)
474 backref
->errors
|= REF_ERR_DUP_INODE_REF
;
475 if (backref
->found_dir_index
&& backref
->index
!= index
)
476 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
478 backref
->index
= index
;
479 backref
->found_inode_ref
= 1;
484 maybe_free_inode_rec(inode_cache
, rec
);
488 static int merge_inode_recs(struct inode_record
*src
, struct inode_record
*dst
,
489 struct cache_tree
*dst_cache
)
491 struct inode_backref
*backref
;
495 list_for_each_entry(backref
, &src
->backrefs
, list
) {
496 if (backref
->found_dir_index
) {
497 add_inode_backref(dst_cache
, dst
->ino
, backref
->dir
,
498 backref
->index
, backref
->name
,
499 backref
->namelen
, backref
->filetype
,
500 BTRFS_DIR_INDEX_KEY
, backref
->errors
);
502 if (backref
->found_dir_item
) {
504 add_inode_backref(dst_cache
, dst
->ino
,
505 backref
->dir
, 0, backref
->name
,
506 backref
->namelen
, backref
->filetype
,
507 BTRFS_DIR_ITEM_KEY
, backref
->errors
);
509 if (backref
->found_inode_ref
) {
510 add_inode_backref(dst_cache
, dst
->ino
,
511 backref
->dir
, backref
->index
,
512 backref
->name
, backref
->namelen
, 0,
513 BTRFS_INODE_REF_KEY
, backref
->errors
);
517 if (src
->found_dir_item
)
518 dst
->found_dir_item
= 1;
519 if (src
->found_file_extent
)
520 dst
->found_file_extent
= 1;
521 if (src
->found_csum_item
)
522 dst
->found_csum_item
= 1;
523 if (src
->some_csum_missing
)
524 dst
->some_csum_missing
= 1;
525 if (dst
->first_extent_gap
> src
->first_extent_gap
)
526 dst
->first_extent_gap
= src
->first_extent_gap
;
528 BUG_ON(src
->found_link
< dir_count
);
529 dst
->found_link
+= src
->found_link
- dir_count
;
530 dst
->found_size
+= src
->found_size
;
531 if (src
->extent_start
!= (u64
)-1) {
532 if (dst
->extent_start
== (u64
)-1) {
533 dst
->extent_start
= src
->extent_start
;
534 dst
->extent_end
= src
->extent_end
;
536 if (dst
->extent_end
> src
->extent_start
)
537 dst
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
538 else if (dst
->extent_end
< src
->extent_start
&&
539 dst
->extent_end
< dst
->first_extent_gap
)
540 dst
->first_extent_gap
= dst
->extent_end
;
541 if (dst
->extent_end
< src
->extent_end
)
542 dst
->extent_end
= src
->extent_end
;
546 dst
->errors
|= src
->errors
;
547 if (src
->found_inode_item
) {
548 if (!dst
->found_inode_item
) {
549 dst
->nlink
= src
->nlink
;
550 dst
->isize
= src
->isize
;
551 dst
->nbytes
= src
->nbytes
;
552 dst
->imode
= src
->imode
;
553 dst
->nodatasum
= src
->nodatasum
;
554 dst
->found_inode_item
= 1;
556 dst
->errors
|= I_ERR_DUP_INODE_ITEM
;
564 static int splice_shared_node(struct shared_node
*src_node
,
565 struct shared_node
*dst_node
)
567 struct cache_extent
*cache
;
568 struct ptr_node
*node
, *ins
;
569 struct cache_tree
*src
, *dst
;
570 struct inode_record
*rec
, *conflict
;
575 if (--src_node
->refs
== 0)
577 if (src_node
->current
)
578 current_ino
= src_node
->current
->ino
;
580 src
= &src_node
->root_cache
;
581 dst
= &dst_node
->root_cache
;
583 cache
= find_first_cache_extent(src
, 0);
585 node
= container_of(cache
, struct ptr_node
, cache
);
587 cache
= next_cache_extent(cache
);
590 remove_cache_extent(src
, &node
->cache
);
593 ins
= malloc(sizeof(*ins
));
594 ins
->cache
.start
= node
->cache
.start
;
595 ins
->cache
.size
= node
->cache
.size
;
599 ret
= insert_existing_cache_extent(dst
, &ins
->cache
);
600 if (ret
== -EEXIST
) {
601 conflict
= get_inode_rec(dst
, rec
->ino
, 1);
602 merge_inode_recs(rec
, conflict
, dst
);
604 conflict
->checked
= 1;
605 if (dst_node
->current
== conflict
)
606 dst_node
->current
= NULL
;
608 maybe_free_inode_rec(dst
, conflict
);
616 if (src
== &src_node
->root_cache
) {
617 src
= &src_node
->inode_cache
;
618 dst
= &dst_node
->inode_cache
;
622 if (current_ino
> 0 && (!dst_node
->current
||
623 current_ino
> dst_node
->current
->ino
)) {
624 if (dst_node
->current
) {
625 dst_node
->current
->checked
= 1;
626 maybe_free_inode_rec(dst
, dst_node
->current
);
628 dst_node
->current
= get_inode_rec(dst
, current_ino
, 1);
633 static void free_inode_recs(struct cache_tree
*inode_cache
)
635 struct cache_extent
*cache
;
636 struct ptr_node
*node
;
637 struct inode_record
*rec
;
640 cache
= find_first_cache_extent(inode_cache
, 0);
643 node
= container_of(cache
, struct ptr_node
, cache
);
645 remove_cache_extent(inode_cache
, &node
->cache
);
651 static struct shared_node
*find_shared_node(struct cache_tree
*shared
,
654 struct cache_extent
*cache
;
655 struct shared_node
*node
;
657 cache
= find_cache_extent(shared
, bytenr
, 1);
659 node
= container_of(cache
, struct shared_node
, cache
);
665 static int add_shared_node(struct cache_tree
*shared
, u64 bytenr
, u32 refs
)
668 struct shared_node
*node
;
670 node
= calloc(1, sizeof(*node
));
671 node
->cache
.start
= bytenr
;
672 node
->cache
.size
= 1;
673 cache_tree_init(&node
->root_cache
);
674 cache_tree_init(&node
->inode_cache
);
677 ret
= insert_existing_cache_extent(shared
, &node
->cache
);
682 static int enter_shared_node(struct btrfs_root
*root
, u64 bytenr
, u32 refs
,
683 struct walk_control
*wc
, int level
)
685 struct shared_node
*node
;
686 struct shared_node
*dest
;
688 if (level
== wc
->active_node
)
691 BUG_ON(wc
->active_node
<= level
);
692 node
= find_shared_node(&wc
->shared
, bytenr
);
694 add_shared_node(&wc
->shared
, bytenr
, refs
);
695 node
= find_shared_node(&wc
->shared
, bytenr
);
696 wc
->nodes
[level
] = node
;
697 wc
->active_node
= level
;
701 if (wc
->root_level
== wc
->active_node
&&
702 btrfs_root_refs(&root
->root_item
) == 0) {
703 if (--node
->refs
== 0) {
704 free_inode_recs(&node
->root_cache
);
705 free_inode_recs(&node
->inode_cache
);
706 remove_cache_extent(&wc
->shared
, &node
->cache
);
712 dest
= wc
->nodes
[wc
->active_node
];
713 splice_shared_node(node
, dest
);
714 if (node
->refs
== 0) {
715 remove_cache_extent(&wc
->shared
, &node
->cache
);
721 static int leave_shared_node(struct btrfs_root
*root
,
722 struct walk_control
*wc
, int level
)
724 struct shared_node
*node
;
725 struct shared_node
*dest
;
728 if (level
== wc
->root_level
)
731 for (i
= level
+ 1; i
< BTRFS_MAX_LEVEL
; i
++) {
735 BUG_ON(i
>= BTRFS_MAX_LEVEL
);
737 node
= wc
->nodes
[wc
->active_node
];
738 wc
->nodes
[wc
->active_node
] = NULL
;
741 dest
= wc
->nodes
[wc
->active_node
];
742 if (wc
->active_node
< wc
->root_level
||
743 btrfs_root_refs(&root
->root_item
) > 0) {
744 BUG_ON(node
->refs
<= 1);
745 splice_shared_node(node
, dest
);
747 BUG_ON(node
->refs
< 2);
753 static int is_child_root(struct btrfs_root
*root
, u64 parent_root_id
,
756 struct btrfs_path path
;
757 struct btrfs_key key
;
758 struct extent_buffer
*leaf
;
762 btrfs_init_path(&path
);
764 key
.objectid
= parent_root_id
;
765 key
.type
= BTRFS_ROOT_REF_KEY
;
766 key
.offset
= child_root_id
;
767 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
, &key
, &path
,
770 btrfs_release_path(root
, &path
);
774 key
.objectid
= child_root_id
;
775 key
.type
= BTRFS_ROOT_BACKREF_KEY
;
777 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
, &key
, &path
,
782 leaf
= path
.nodes
[0];
783 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
784 ret
= btrfs_next_leaf(root
->fs_info
->tree_root
, &path
);
791 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
792 if (key
.objectid
!= child_root_id
||
793 key
.type
!= BTRFS_ROOT_BACKREF_KEY
)
798 if (key
.offset
== parent_root_id
) {
799 btrfs_release_path(root
, &path
);
806 btrfs_release_path(root
, &path
);
807 return has_parent
? 0 : -1;
810 static int process_dir_item(struct btrfs_root
*root
,
811 struct extent_buffer
*eb
,
812 int slot
, struct btrfs_key
*key
,
813 struct shared_node
*active_node
)
823 struct btrfs_dir_item
*di
;
824 struct inode_record
*rec
;
825 struct cache_tree
*root_cache
;
826 struct cache_tree
*inode_cache
;
827 struct btrfs_key location
;
828 char namebuf
[BTRFS_NAME_LEN
];
830 root_cache
= &active_node
->root_cache
;
831 inode_cache
= &active_node
->inode_cache
;
832 rec
= active_node
->current
;
833 rec
->found_dir_item
= 1;
835 di
= btrfs_item_ptr(eb
, slot
, struct btrfs_dir_item
);
836 total
= btrfs_item_size_nr(eb
, slot
);
837 while (cur
< total
) {
839 btrfs_dir_item_key_to_cpu(eb
, di
, &location
);
840 name_len
= btrfs_dir_name_len(eb
, di
);
841 data_len
= btrfs_dir_data_len(eb
, di
);
842 filetype
= btrfs_dir_type(eb
, di
);
844 rec
->found_size
+= name_len
;
845 if (name_len
<= BTRFS_NAME_LEN
) {
849 len
= BTRFS_NAME_LEN
;
850 error
= REF_ERR_NAME_TOO_LONG
;
852 read_extent_buffer(eb
, namebuf
, (unsigned long)(di
+ 1), len
);
854 if (location
.type
== BTRFS_INODE_ITEM_KEY
) {
855 add_inode_backref(inode_cache
, location
.objectid
,
856 key
->objectid
, key
->offset
, namebuf
,
857 len
, filetype
, key
->type
, error
);
858 } else if (location
.type
== BTRFS_ROOT_ITEM_KEY
) {
859 u64 parent
= root
->objectid
;
861 if (is_child_root(root
, parent
, location
.objectid
))
862 add_inode_backref(root_cache
, location
.objectid
,
863 key
->objectid
, key
->offset
,
864 namebuf
, len
, filetype
,
867 fprintf(stderr
, "warning line %d\n", __LINE__
);
870 len
= sizeof(*di
) + name_len
+ data_len
;
871 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
874 if (key
->type
== BTRFS_DIR_INDEX_KEY
&& nritems
> 1)
875 rec
->errors
|= I_ERR_DUP_DIR_INDEX
;
880 static int process_inode_ref(struct extent_buffer
*eb
,
881 int slot
, struct btrfs_key
*key
,
882 struct shared_node
*active_node
)
890 struct cache_tree
*inode_cache
;
891 struct btrfs_inode_ref
*ref
;
892 char namebuf
[BTRFS_NAME_LEN
];
894 inode_cache
= &active_node
->inode_cache
;
896 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
897 total
= btrfs_item_size_nr(eb
, slot
);
898 while (cur
< total
) {
899 name_len
= btrfs_inode_ref_name_len(eb
, ref
);
900 index
= btrfs_inode_ref_index(eb
, ref
);
901 if (name_len
<= BTRFS_NAME_LEN
) {
905 len
= BTRFS_NAME_LEN
;
906 error
= REF_ERR_NAME_TOO_LONG
;
908 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
909 add_inode_backref(inode_cache
, key
->objectid
, key
->offset
,
910 index
, namebuf
, len
, 0, key
->type
, error
);
912 len
= sizeof(*ref
) + name_len
;
913 ref
= (struct btrfs_inode_ref
*)((char *)ref
+ len
);
919 static u64
count_csum_range(struct btrfs_root
*root
, u64 start
, u64 len
)
921 struct btrfs_key key
;
922 struct btrfs_path path
;
923 struct extent_buffer
*leaf
;
928 u16 csum_size
= btrfs_super_csum_size(&root
->fs_info
->super_copy
);
930 btrfs_init_path(&path
);
932 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
934 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
936 ret
= btrfs_search_slot(NULL
, root
->fs_info
->csum_root
,
939 if (ret
> 0 && path
.slots
[0] > 0) {
940 leaf
= path
.nodes
[0];
941 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0] - 1);
942 if (key
.objectid
== BTRFS_EXTENT_CSUM_OBJECTID
&&
943 key
.type
== BTRFS_EXTENT_CSUM_KEY
)
948 leaf
= path
.nodes
[0];
949 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
950 ret
= btrfs_next_leaf(root
->fs_info
->csum_root
, &path
);
954 leaf
= path
.nodes
[0];
957 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
958 if (key
.objectid
!= BTRFS_EXTENT_CSUM_OBJECTID
||
959 key
.type
!= BTRFS_EXTENT_CSUM_KEY
)
962 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
963 if (key
.offset
>= start
+ len
)
966 if (key
.offset
> start
)
969 size
= btrfs_item_size_nr(leaf
, path
.slots
[0]);
970 csum_end
= key
.offset
+ (size
/ csum_size
) * root
->sectorsize
;
971 if (csum_end
> start
) {
972 size
= min(csum_end
- start
, len
);
980 btrfs_release_path(root
->fs_info
->csum_root
, &path
);
984 static int process_file_extent(struct btrfs_root
*root
,
985 struct extent_buffer
*eb
,
986 int slot
, struct btrfs_key
*key
,
987 struct shared_node
*active_node
)
989 struct inode_record
*rec
;
990 struct btrfs_file_extent_item
*fi
;
993 u64 extent_offset
= 0;
994 u64 mask
= root
->sectorsize
- 1;
997 rec
= active_node
->current
;
998 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
999 rec
->found_file_extent
= 1;
1001 if (rec
->extent_start
== (u64
)-1) {
1002 rec
->extent_start
= key
->offset
;
1003 rec
->extent_end
= key
->offset
;
1006 if (rec
->extent_end
> key
->offset
)
1007 rec
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
1008 else if (rec
->extent_end
< key
->offset
&&
1009 rec
->extent_end
< rec
->first_extent_gap
)
1010 rec
->first_extent_gap
= rec
->extent_end
;
1012 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
1013 extent_type
= btrfs_file_extent_type(eb
, fi
);
1015 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
1016 num_bytes
= btrfs_file_extent_inline_len(eb
, fi
);
1018 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1019 rec
->found_size
+= num_bytes
;
1020 num_bytes
= (num_bytes
+ mask
) & ~mask
;
1021 } else if (extent_type
== BTRFS_FILE_EXTENT_REG
||
1022 extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1023 num_bytes
= btrfs_file_extent_num_bytes(eb
, fi
);
1024 disk_bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
1025 extent_offset
= btrfs_file_extent_offset(eb
, fi
);
1026 if (num_bytes
== 0 || (num_bytes
& mask
))
1027 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1028 if (num_bytes
+ extent_offset
>
1029 btrfs_file_extent_ram_bytes(eb
, fi
))
1030 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1031 if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
&&
1032 (btrfs_file_extent_compression(eb
, fi
) ||
1033 btrfs_file_extent_encryption(eb
, fi
) ||
1034 btrfs_file_extent_other_encoding(eb
, fi
)))
1035 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1036 if (disk_bytenr
> 0)
1037 rec
->found_size
+= num_bytes
;
1039 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1041 rec
->extent_end
= key
->offset
+ num_bytes
;
1043 if (disk_bytenr
> 0) {
1045 if (btrfs_file_extent_compression(eb
, fi
))
1046 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
1048 disk_bytenr
+= extent_offset
;
1050 found
= count_csum_range(root
, disk_bytenr
, num_bytes
);
1051 if (extent_type
== BTRFS_FILE_EXTENT_REG
) {
1053 rec
->found_csum_item
= 1;
1054 if (found
< num_bytes
)
1055 rec
->some_csum_missing
= 1;
1056 } else if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1058 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
1064 static int process_one_leaf(struct btrfs_root
*root
, struct extent_buffer
*eb
,
1065 struct walk_control
*wc
)
1067 struct btrfs_key key
;
1071 struct cache_tree
*inode_cache
;
1072 struct shared_node
*active_node
;
1074 if (wc
->root_level
== wc
->active_node
&&
1075 btrfs_root_refs(&root
->root_item
) == 0)
1078 active_node
= wc
->nodes
[wc
->active_node
];
1079 inode_cache
= &active_node
->inode_cache
;
1080 nritems
= btrfs_header_nritems(eb
);
1081 for (i
= 0; i
< nritems
; i
++) {
1082 btrfs_item_key_to_cpu(eb
, &key
, i
);
1084 if (key
.objectid
== BTRFS_FREE_SPACE_OBJECTID
)
1087 if (active_node
->current
== NULL
||
1088 active_node
->current
->ino
< key
.objectid
) {
1089 if (active_node
->current
) {
1090 active_node
->current
->checked
= 1;
1091 maybe_free_inode_rec(inode_cache
,
1092 active_node
->current
);
1094 active_node
->current
= get_inode_rec(inode_cache
,
1098 case BTRFS_DIR_ITEM_KEY
:
1099 case BTRFS_DIR_INDEX_KEY
:
1100 ret
= process_dir_item(root
, eb
, i
, &key
, active_node
);
1102 case BTRFS_INODE_REF_KEY
:
1103 ret
= process_inode_ref(eb
, i
, &key
, active_node
);
1105 case BTRFS_INODE_ITEM_KEY
:
1106 ret
= process_inode_item(eb
, i
, &key
, active_node
);
1108 case BTRFS_EXTENT_DATA_KEY
:
1109 ret
= process_file_extent(root
, eb
, i
, &key
,
1119 static void reada_walk_down(struct btrfs_root
*root
,
1120 struct extent_buffer
*node
, int slot
)
1130 level
= btrfs_header_level(node
);
1134 nritems
= btrfs_header_nritems(node
);
1135 blocksize
= btrfs_level_size(root
, level
- 1);
1136 for (i
= slot
; i
< nritems
; i
++) {
1137 bytenr
= btrfs_node_blockptr(node
, i
);
1138 ptr_gen
= btrfs_node_ptr_generation(node
, i
);
1139 ret
= readahead_tree_block(root
, bytenr
, blocksize
, ptr_gen
);
1145 static int walk_down_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1146 struct walk_control
*wc
, int *level
)
1150 struct extent_buffer
*next
;
1151 struct extent_buffer
*cur
;
1156 WARN_ON(*level
< 0);
1157 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1158 ret
= btrfs_lookup_extent_info(NULL
, root
,
1159 path
->nodes
[*level
]->start
,
1160 path
->nodes
[*level
]->len
, &refs
, NULL
);
1165 ret
= enter_shared_node(root
, path
->nodes
[*level
]->start
,
1171 while (*level
>= 0) {
1172 WARN_ON(*level
< 0);
1173 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1174 cur
= path
->nodes
[*level
];
1176 if (btrfs_header_level(cur
) != *level
)
1179 if (path
->slots
[*level
] >= btrfs_header_nritems(cur
))
1182 ret
= process_one_leaf(root
, cur
, wc
);
1185 bytenr
= btrfs_node_blockptr(cur
, path
->slots
[*level
]);
1186 ptr_gen
= btrfs_node_ptr_generation(cur
, path
->slots
[*level
]);
1187 blocksize
= btrfs_level_size(root
, *level
- 1);
1188 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
, blocksize
,
1194 ret
= enter_shared_node(root
, bytenr
, refs
,
1197 path
->slots
[*level
]++;
1202 next
= btrfs_find_tree_block(root
, bytenr
, blocksize
);
1203 if (!next
|| !btrfs_buffer_uptodate(next
, ptr_gen
)) {
1204 free_extent_buffer(next
);
1205 reada_walk_down(root
, cur
, path
->slots
[*level
]);
1206 next
= read_tree_block(root
, bytenr
, blocksize
,
1210 *level
= *level
- 1;
1211 free_extent_buffer(path
->nodes
[*level
]);
1212 path
->nodes
[*level
] = next
;
1213 path
->slots
[*level
] = 0;
1216 path
->slots
[*level
] = btrfs_header_nritems(path
->nodes
[*level
]);
1220 static int walk_up_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1221 struct walk_control
*wc
, int *level
)
1224 struct extent_buffer
*leaf
;
1226 for (i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
1227 leaf
= path
->nodes
[i
];
1228 if (path
->slots
[i
] + 1 < btrfs_header_nritems(leaf
)) {
1233 free_extent_buffer(path
->nodes
[*level
]);
1234 path
->nodes
[*level
] = NULL
;
1235 BUG_ON(*level
> wc
->active_node
);
1236 if (*level
== wc
->active_node
)
1237 leave_shared_node(root
, wc
, *level
);
1244 static int check_root_dir(struct inode_record
*rec
)
1246 struct inode_backref
*backref
;
1249 if (!rec
->found_inode_item
|| rec
->errors
)
1251 if (rec
->nlink
!= 1 || rec
->found_link
!= 0)
1253 if (list_empty(&rec
->backrefs
))
1255 backref
= list_entry(rec
->backrefs
.next
, struct inode_backref
, list
);
1256 if (!backref
->found_inode_ref
)
1258 if (backref
->index
!= 0 || backref
->namelen
!= 2 ||
1259 memcmp(backref
->name
, "..", 2))
1261 if (backref
->found_dir_index
|| backref
->found_dir_item
)
1268 static int check_inode_recs(struct btrfs_root
*root
,
1269 struct cache_tree
*inode_cache
)
1271 struct cache_extent
*cache
;
1272 struct ptr_node
*node
;
1273 struct inode_record
*rec
;
1274 struct inode_backref
*backref
;
1277 u64 root_dirid
= btrfs_root_dirid(&root
->root_item
);
1279 if (btrfs_root_refs(&root
->root_item
) == 0) {
1280 if (!cache_tree_empty(inode_cache
))
1281 fprintf(stderr
, "warning line %d\n", __LINE__
);
1285 rec
= get_inode_rec(inode_cache
, root_dirid
, 0);
1287 ret
= check_root_dir(rec
);
1289 fprintf(stderr
, "root %llu root dir %llu error\n",
1290 (unsigned long long)root
->root_key
.objectid
,
1291 (unsigned long long)root_dirid
);
1295 fprintf(stderr
, "root %llu root dir %llu not found\n",
1296 (unsigned long long)root
->root_key
.objectid
,
1297 (unsigned long long)root_dirid
);
1301 cache
= find_first_cache_extent(inode_cache
, 0);
1304 node
= container_of(cache
, struct ptr_node
, cache
);
1306 remove_cache_extent(inode_cache
, &node
->cache
);
1308 if (rec
->ino
== root_dirid
||
1309 rec
->ino
== BTRFS_ORPHAN_OBJECTID
) {
1310 free_inode_rec(rec
);
1314 if (rec
->errors
& I_ERR_NO_ORPHAN_ITEM
) {
1315 ret
= check_orphan_item(root
, rec
->ino
);
1317 rec
->errors
&= ~I_ERR_NO_ORPHAN_ITEM
;
1318 if (can_free_inode_rec(rec
)) {
1319 free_inode_rec(rec
);
1325 if (!rec
->found_inode_item
)
1326 rec
->errors
|= I_ERR_NO_INODE_ITEM
;
1327 if (rec
->found_link
!= rec
->nlink
)
1328 rec
->errors
|= I_ERR_LINK_COUNT_WRONG
;
1329 fprintf(stderr
, "root %llu inode %llu errors %x\n",
1330 (unsigned long long) root
->root_key
.objectid
,
1331 (unsigned long long) rec
->ino
, rec
->errors
);
1332 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1333 if (!backref
->found_dir_item
)
1334 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1335 if (!backref
->found_dir_index
)
1336 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1337 if (!backref
->found_inode_ref
)
1338 backref
->errors
|= REF_ERR_NO_INODE_REF
;
1339 fprintf(stderr
, "\tunresolved ref dir %llu index %llu"
1340 " namelen %u name %s filetype %d error %x\n",
1341 (unsigned long long)backref
->dir
,
1342 (unsigned long long)backref
->index
,
1343 backref
->namelen
, backref
->name
,
1344 backref
->filetype
, backref
->errors
);
1346 free_inode_rec(rec
);
1348 return (error
> 0) ? -1 : 0;
1351 static struct root_record
*get_root_rec(struct cache_tree
*root_cache
,
1354 struct cache_extent
*cache
;
1355 struct root_record
*rec
= NULL
;
1358 cache
= find_cache_extent(root_cache
, objectid
, 1);
1360 rec
= container_of(cache
, struct root_record
, cache
);
1362 rec
= calloc(1, sizeof(*rec
));
1363 rec
->objectid
= objectid
;
1364 INIT_LIST_HEAD(&rec
->backrefs
);
1365 rec
->cache
.start
= objectid
;
1366 rec
->cache
.size
= 1;
1368 ret
= insert_existing_cache_extent(root_cache
, &rec
->cache
);
1374 static struct root_backref
*get_root_backref(struct root_record
*rec
,
1375 u64 ref_root
, u64 dir
, u64 index
,
1376 const char *name
, int namelen
)
1378 struct root_backref
*backref
;
1380 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1381 if (backref
->ref_root
!= ref_root
|| backref
->dir
!= dir
||
1382 backref
->namelen
!= namelen
)
1384 if (memcmp(name
, backref
->name
, namelen
))
1389 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
1390 memset(backref
, 0, sizeof(*backref
));
1391 backref
->ref_root
= ref_root
;
1393 backref
->index
= index
;
1394 backref
->namelen
= namelen
;
1395 memcpy(backref
->name
, name
, namelen
);
1396 backref
->name
[namelen
] = '\0';
1397 list_add_tail(&backref
->list
, &rec
->backrefs
);
1401 static void free_root_recs(struct cache_tree
*root_cache
)
1403 struct cache_extent
*cache
;
1404 struct root_record
*rec
;
1405 struct root_backref
*backref
;
1408 cache
= find_first_cache_extent(root_cache
, 0);
1411 rec
= container_of(cache
, struct root_record
, cache
);
1412 remove_cache_extent(root_cache
, &rec
->cache
);
1414 while (!list_empty(&rec
->backrefs
)) {
1415 backref
= list_entry(rec
->backrefs
.next
,
1416 struct root_backref
, list
);
1417 list_del(&backref
->list
);
1424 static int add_root_backref(struct cache_tree
*root_cache
,
1425 u64 root_id
, u64 ref_root
, u64 dir
, u64 index
,
1426 const char *name
, int namelen
,
1427 int item_type
, int errors
)
1429 struct root_record
*rec
;
1430 struct root_backref
*backref
;
1432 rec
= get_root_rec(root_cache
, root_id
);
1433 backref
= get_root_backref(rec
, ref_root
, dir
, index
, name
, namelen
);
1435 backref
->errors
|= errors
;
1437 if (item_type
!= BTRFS_DIR_ITEM_KEY
) {
1438 if (backref
->found_dir_index
|| backref
->found_back_ref
||
1439 backref
->found_forward_ref
) {
1440 if (backref
->index
!= index
)
1441 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
1443 backref
->index
= index
;
1447 if (item_type
== BTRFS_DIR_ITEM_KEY
) {
1448 backref
->found_dir_item
= 1;
1449 backref
->reachable
= 1;
1451 } else if (item_type
== BTRFS_DIR_INDEX_KEY
) {
1452 backref
->found_dir_index
= 1;
1453 } else if (item_type
== BTRFS_ROOT_REF_KEY
) {
1454 if (backref
->found_forward_ref
)
1455 backref
->errors
|= REF_ERR_DUP_ROOT_REF
;
1456 backref
->found_forward_ref
= 1;
1457 } else if (item_type
== BTRFS_ROOT_BACKREF_KEY
) {
1458 if (backref
->found_back_ref
)
1459 backref
->errors
|= REF_ERR_DUP_ROOT_BACKREF
;
1460 backref
->found_back_ref
= 1;
1468 static int merge_root_recs(struct btrfs_root
*root
,
1469 struct cache_tree
*src_cache
,
1470 struct cache_tree
*dst_cache
)
1472 struct cache_extent
*cache
;
1473 struct ptr_node
*node
;
1474 struct inode_record
*rec
;
1475 struct inode_backref
*backref
;
1477 if (root
->root_key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
1478 free_inode_recs(src_cache
);
1483 cache
= find_first_cache_extent(src_cache
, 0);
1486 node
= container_of(cache
, struct ptr_node
, cache
);
1488 remove_cache_extent(src_cache
, &node
->cache
);
1491 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1492 BUG_ON(backref
->found_inode_ref
);
1493 if (backref
->found_dir_item
)
1494 add_root_backref(dst_cache
, rec
->ino
,
1495 root
->root_key
.objectid
, backref
->dir
,
1496 backref
->index
, backref
->name
,
1497 backref
->namelen
, BTRFS_DIR_ITEM_KEY
,
1499 if (backref
->found_dir_index
)
1500 add_root_backref(dst_cache
, rec
->ino
,
1501 root
->root_key
.objectid
, backref
->dir
,
1502 backref
->index
, backref
->name
,
1503 backref
->namelen
, BTRFS_DIR_INDEX_KEY
,
1506 free_inode_rec(rec
);
1511 static int check_root_refs(struct btrfs_root
*root
,
1512 struct cache_tree
*root_cache
)
1514 struct root_record
*rec
;
1515 struct root_record
*ref_root
;
1516 struct root_backref
*backref
;
1517 struct cache_extent
*cache
;
1523 rec
= get_root_rec(root_cache
, BTRFS_FS_TREE_OBJECTID
);
1526 /* fixme: this can not detect circular references */
1529 cache
= find_first_cache_extent(root_cache
, 0);
1533 rec
= container_of(cache
, struct root_record
, cache
);
1534 cache
= next_cache_extent(cache
);
1536 if (rec
->found_ref
== 0)
1539 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1540 if (!backref
->reachable
)
1543 ref_root
= get_root_rec(root_cache
,
1545 if (ref_root
->found_ref
> 0)
1548 backref
->reachable
= 0;
1550 if (rec
->found_ref
== 0)
1556 cache
= find_first_cache_extent(root_cache
, 0);
1560 rec
= container_of(cache
, struct root_record
, cache
);
1561 cache
= next_cache_extent(cache
);
1563 if (rec
->found_ref
== 0 &&
1564 rec
->objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
1565 rec
->objectid
<= BTRFS_LAST_FREE_OBJECTID
) {
1566 ret
= check_orphan_item(root
->fs_info
->tree_root
,
1571 fprintf(stderr
, "fs tree %llu not referenced\n",
1572 (unsigned long long)rec
->objectid
);
1576 if (rec
->found_ref
> 0 && !rec
->found_root_item
)
1578 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1579 if (!backref
->found_dir_item
)
1580 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1581 if (!backref
->found_dir_index
)
1582 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1583 if (!backref
->found_back_ref
)
1584 backref
->errors
|= REF_ERR_NO_ROOT_BACKREF
;
1585 if (!backref
->found_forward_ref
)
1586 backref
->errors
|= REF_ERR_NO_ROOT_REF
;
1587 if (backref
->reachable
&& backref
->errors
)
1594 fprintf(stderr
, "fs tree %llu refs %u %s\n",
1595 (unsigned long long)rec
->objectid
, rec
->found_ref
,
1596 rec
->found_root_item
? "" : "not found");
1598 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1599 if (!backref
->reachable
)
1601 if (!backref
->errors
&& rec
->found_root_item
)
1603 fprintf(stderr
, "\tunresolved ref root %llu dir %llu"
1604 " index %llu namelen %u name %s error %x\n",
1605 (unsigned long long)backref
->ref_root
,
1606 (unsigned long long)backref
->dir
,
1607 (unsigned long long)backref
->index
,
1608 backref
->namelen
, backref
->name
,
1612 return errors
> 0 ? 1 : 0;
1615 static int process_root_ref(struct extent_buffer
*eb
, int slot
,
1616 struct btrfs_key
*key
,
1617 struct cache_tree
*root_cache
)
1623 struct btrfs_root_ref
*ref
;
1624 char namebuf
[BTRFS_NAME_LEN
];
1627 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_root_ref
);
1629 dirid
= btrfs_root_ref_dirid(eb
, ref
);
1630 index
= btrfs_root_ref_sequence(eb
, ref
);
1631 name_len
= btrfs_root_ref_name_len(eb
, ref
);
1633 if (name_len
<= BTRFS_NAME_LEN
) {
1637 len
= BTRFS_NAME_LEN
;
1638 error
= REF_ERR_NAME_TOO_LONG
;
1640 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
1642 if (key
->type
== BTRFS_ROOT_REF_KEY
) {
1643 add_root_backref(root_cache
, key
->offset
, key
->objectid
, dirid
,
1644 index
, namebuf
, len
, key
->type
, error
);
1646 add_root_backref(root_cache
, key
->objectid
, key
->offset
, dirid
,
1647 index
, namebuf
, len
, key
->type
, error
);
1652 static int check_fs_root(struct btrfs_root
*root
,
1653 struct cache_tree
*root_cache
,
1654 struct walk_control
*wc
)
1659 struct btrfs_path path
;
1660 struct shared_node root_node
;
1661 struct root_record
*rec
;
1662 struct btrfs_root_item
*root_item
= &root
->root_item
;
1664 if (root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
1665 rec
= get_root_rec(root_cache
, root
->root_key
.objectid
);
1666 if (btrfs_root_refs(root_item
) > 0)
1667 rec
->found_root_item
= 1;
1670 btrfs_init_path(&path
);
1671 memset(&root_node
, 0, sizeof(root_node
));
1672 cache_tree_init(&root_node
.root_cache
);
1673 cache_tree_init(&root_node
.inode_cache
);
1675 level
= btrfs_header_level(root
->node
);
1676 memset(wc
->nodes
, 0, sizeof(wc
->nodes
));
1677 wc
->nodes
[level
] = &root_node
;
1678 wc
->active_node
= level
;
1679 wc
->root_level
= level
;
1681 if (btrfs_root_refs(root_item
) > 0 ||
1682 btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
1683 path
.nodes
[level
] = root
->node
;
1684 extent_buffer_get(root
->node
);
1685 path
.slots
[level
] = 0;
1687 struct btrfs_key key
;
1688 struct btrfs_disk_key found_key
;
1690 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
1691 level
= root_item
->drop_level
;
1692 path
.lowest_level
= level
;
1693 wret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
1695 btrfs_node_key(path
.nodes
[level
], &found_key
,
1697 WARN_ON(memcmp(&found_key
, &root_item
->drop_progress
,
1698 sizeof(found_key
)));
1702 wret
= walk_down_tree(root
, &path
, wc
, &level
);
1708 wret
= walk_up_tree(root
, &path
, wc
, &level
);
1714 btrfs_release_path(root
, &path
);
1716 merge_root_recs(root
, &root_node
.root_cache
, root_cache
);
1718 if (root_node
.current
) {
1719 root_node
.current
->checked
= 1;
1720 maybe_free_inode_rec(&root_node
.inode_cache
,
1724 ret
= check_inode_recs(root
, &root_node
.inode_cache
);
1728 static int fs_root_objectid(u64 objectid
)
1730 if (objectid
== BTRFS_FS_TREE_OBJECTID
||
1731 objectid
== BTRFS_TREE_RELOC_OBJECTID
||
1732 objectid
== BTRFS_DATA_RELOC_TREE_OBJECTID
||
1733 (objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
1734 objectid
<= BTRFS_LAST_FREE_OBJECTID
))
1739 static int check_fs_roots(struct btrfs_root
*root
,
1740 struct cache_tree
*root_cache
)
1742 struct btrfs_path path
;
1743 struct btrfs_key key
;
1744 struct walk_control wc
;
1745 struct extent_buffer
*leaf
;
1746 struct btrfs_root
*tmp_root
;
1747 struct btrfs_root
*tree_root
= root
->fs_info
->tree_root
;
1751 memset(&wc
, 0, sizeof(wc
));
1752 cache_tree_init(&wc
.shared
);
1753 btrfs_init_path(&path
);
1757 key
.type
= BTRFS_ROOT_ITEM_KEY
;
1758 ret
= btrfs_search_slot(NULL
, tree_root
, &key
, &path
, 0, 0);
1761 leaf
= path
.nodes
[0];
1762 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
1763 ret
= btrfs_next_leaf(tree_root
, &path
);
1766 leaf
= path
.nodes
[0];
1768 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
1769 if (key
.type
== BTRFS_ROOT_ITEM_KEY
&&
1770 fs_root_objectid(key
.objectid
)) {
1771 tmp_root
= btrfs_read_fs_root_no_cache(root
->fs_info
,
1773 ret
= check_fs_root(tmp_root
, root_cache
, &wc
);
1776 btrfs_free_fs_root(root
->fs_info
, tmp_root
);
1777 } else if (key
.type
== BTRFS_ROOT_REF_KEY
||
1778 key
.type
== BTRFS_ROOT_BACKREF_KEY
) {
1779 process_root_ref(leaf
, path
.slots
[0], &key
,
1784 btrfs_release_path(tree_root
, &path
);
1786 if (!cache_tree_empty(&wc
.shared
))
1787 fprintf(stderr
, "warning line %d\n", __LINE__
);
1792 static int all_backpointers_checked(struct extent_record
*rec
, int print_errs
)
1794 struct list_head
*cur
= rec
->backrefs
.next
;
1795 struct extent_backref
*back
;
1796 struct tree_backref
*tback
;
1797 struct data_backref
*dback
;
1801 while(cur
!= &rec
->backrefs
) {
1802 back
= list_entry(cur
, struct extent_backref
, list
);
1804 if (!back
->found_extent_tree
) {
1808 if (back
->is_data
) {
1809 dback
= (struct data_backref
*)back
;
1810 fprintf(stderr
, "Backref %llu %s %llu"
1811 " owner %llu offset %llu num_refs %lu"
1812 " not found in extent tree\n",
1813 (unsigned long long)rec
->start
,
1814 back
->full_backref
?
1816 back
->full_backref
?
1817 (unsigned long long)dback
->parent
:
1818 (unsigned long long)dback
->root
,
1819 (unsigned long long)dback
->owner
,
1820 (unsigned long long)dback
->offset
,
1821 (unsigned long)dback
->num_refs
);
1823 tback
= (struct tree_backref
*)back
;
1824 fprintf(stderr
, "Backref %llu parent %llu"
1825 " root %llu not found in extent tree\n",
1826 (unsigned long long)rec
->start
,
1827 (unsigned long long)tback
->parent
,
1828 (unsigned long long)tback
->root
);
1831 if (!back
->is_data
&& !back
->found_ref
) {
1835 tback
= (struct tree_backref
*)back
;
1836 fprintf(stderr
, "Backref %llu %s %llu not referenced back %p\n",
1837 (unsigned long long)rec
->start
,
1838 back
->full_backref
? "parent" : "root",
1839 back
->full_backref
?
1840 (unsigned long long)tback
->parent
:
1841 (unsigned long long)tback
->root
, back
);
1843 if (back
->is_data
) {
1844 dback
= (struct data_backref
*)back
;
1845 if (dback
->found_ref
!= dback
->num_refs
) {
1849 fprintf(stderr
, "Incorrect local backref count"
1850 " on %llu %s %llu owner %llu"
1851 " offset %llu found %u wanted %u back %p\n",
1852 (unsigned long long)rec
->start
,
1853 back
->full_backref
?
1855 back
->full_backref
?
1856 (unsigned long long)dback
->parent
:
1857 (unsigned long long)dback
->root
,
1858 (unsigned long long)dback
->owner
,
1859 (unsigned long long)dback
->offset
,
1860 dback
->found_ref
, dback
->num_refs
, back
);
1863 if (!back
->is_data
) {
1866 dback
= (struct data_backref
*)back
;
1867 found
+= dback
->found_ref
;
1870 if (found
!= rec
->refs
) {
1874 fprintf(stderr
, "Incorrect global backref count "
1875 "on %llu found %llu wanted %llu\n",
1876 (unsigned long long)rec
->start
,
1877 (unsigned long long)found
,
1878 (unsigned long long)rec
->refs
);
1884 static int free_all_extent_backrefs(struct extent_record
*rec
)
1886 struct extent_backref
*back
;
1887 struct list_head
*cur
;
1888 while (!list_empty(&rec
->backrefs
)) {
1889 cur
= rec
->backrefs
.next
;
1890 back
= list_entry(cur
, struct extent_backref
, list
);
1897 static int maybe_free_extent_rec(struct cache_tree
*extent_cache
,
1898 struct extent_record
*rec
)
1900 if (rec
->content_checked
&& rec
->owner_ref_checked
&&
1901 rec
->extent_item_refs
== rec
->refs
&& rec
->refs
> 0 &&
1902 !all_backpointers_checked(rec
, 0)) {
1903 remove_cache_extent(extent_cache
, &rec
->cache
);
1904 free_all_extent_backrefs(rec
);
1910 static int check_owner_ref(struct btrfs_root
*root
,
1911 struct extent_record
*rec
,
1912 struct extent_buffer
*buf
)
1914 struct extent_backref
*node
;
1915 struct tree_backref
*back
;
1916 struct btrfs_root
*ref_root
;
1917 struct btrfs_key key
;
1918 struct btrfs_path path
;
1922 list_for_each_entry(node
, &rec
->backrefs
, list
) {
1925 if (!node
->found_ref
)
1927 if (node
->full_backref
)
1929 back
= (struct tree_backref
*)node
;
1930 if (btrfs_header_owner(buf
) == back
->root
)
1933 BUG_ON(rec
->is_root
);
1935 /* try to find the block by search corresponding fs tree */
1936 key
.objectid
= btrfs_header_owner(buf
);
1937 key
.type
= BTRFS_ROOT_ITEM_KEY
;
1938 key
.offset
= (u64
)-1;
1940 ref_root
= btrfs_read_fs_root(root
->fs_info
, &key
);
1941 BUG_ON(IS_ERR(ref_root
));
1943 level
= btrfs_header_level(buf
);
1945 btrfs_item_key_to_cpu(buf
, &key
, 0);
1947 btrfs_node_key_to_cpu(buf
, &key
, 0);
1949 btrfs_init_path(&path
);
1950 path
.lowest_level
= level
+ 1;
1951 btrfs_search_slot(NULL
, ref_root
, &key
, &path
, 0, 0);
1953 if (buf
->start
== btrfs_node_blockptr(path
.nodes
[level
+ 1],
1954 path
.slots
[level
+ 1]))
1955 rec
->owner_ref_checked
= 1;
1957 btrfs_release_path(ref_root
, &path
);
1958 return found
? 0 : 1;
1961 static int is_extent_tree_record(struct extent_record
*rec
)
1963 struct list_head
*cur
= rec
->backrefs
.next
;
1964 struct extent_backref
*node
;
1965 struct tree_backref
*back
;
1968 while(cur
!= &rec
->backrefs
) {
1969 node
= list_entry(cur
, struct extent_backref
, list
);
1973 back
= (struct tree_backref
*)node
;
1974 if (node
->full_backref
)
1976 if (back
->root
== BTRFS_EXTENT_TREE_OBJECTID
)
1983 static int record_bad_block_io(struct btrfs_fs_info
*info
,
1984 struct cache_tree
*extent_cache
,
1987 struct extent_record
*rec
;
1988 struct cache_extent
*cache
;
1989 struct btrfs_key key
;
1991 cache
= find_cache_extent(extent_cache
, start
, len
);
1995 rec
= container_of(cache
, struct extent_record
, cache
);
1996 if (!is_extent_tree_record(rec
))
1999 btrfs_disk_key_to_cpu(&key
, &rec
->parent_key
);
2000 return btrfs_add_corrupt_extent_record(info
, &key
, start
, len
, 0);
2003 static int check_block(struct btrfs_root
*root
,
2004 struct cache_tree
*extent_cache
,
2005 struct extent_buffer
*buf
, u64 flags
)
2007 struct extent_record
*rec
;
2008 struct cache_extent
*cache
;
2009 struct btrfs_key key
;
2013 cache
= find_cache_extent(extent_cache
, buf
->start
, buf
->len
);
2016 rec
= container_of(cache
, struct extent_record
, cache
);
2017 rec
->generation
= btrfs_header_generation(buf
);
2019 level
= btrfs_header_level(buf
);
2020 if (btrfs_header_nritems(buf
) > 0) {
2023 btrfs_item_key_to_cpu(buf
, &key
, 0);
2025 btrfs_node_key_to_cpu(buf
, &key
, 0);
2027 rec
->info_objectid
= key
.objectid
;
2029 rec
->info_level
= level
;
2031 if (btrfs_is_leaf(buf
))
2032 ret
= btrfs_check_leaf(root
, &rec
->parent_key
, buf
);
2034 ret
= btrfs_check_node(root
, &rec
->parent_key
, buf
);
2037 fprintf(stderr
, "bad block %llu\n",
2038 (unsigned long long)buf
->start
);
2040 rec
->content_checked
= 1;
2041 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
)
2042 rec
->owner_ref_checked
= 1;
2044 ret
= check_owner_ref(root
, rec
, buf
);
2046 rec
->owner_ref_checked
= 1;
2050 maybe_free_extent_rec(extent_cache
, rec
);
2054 static struct tree_backref
*find_tree_backref(struct extent_record
*rec
,
2055 u64 parent
, u64 root
)
2057 struct list_head
*cur
= rec
->backrefs
.next
;
2058 struct extent_backref
*node
;
2059 struct tree_backref
*back
;
2061 while(cur
!= &rec
->backrefs
) {
2062 node
= list_entry(cur
, struct extent_backref
, list
);
2066 back
= (struct tree_backref
*)node
;
2068 if (!node
->full_backref
)
2070 if (parent
== back
->parent
)
2073 if (node
->full_backref
)
2075 if (back
->root
== root
)
2082 static struct tree_backref
*alloc_tree_backref(struct extent_record
*rec
,
2083 u64 parent
, u64 root
)
2085 struct tree_backref
*ref
= malloc(sizeof(*ref
));
2086 memset(&ref
->node
, 0, sizeof(ref
->node
));
2088 ref
->parent
= parent
;
2089 ref
->node
.full_backref
= 1;
2092 ref
->node
.full_backref
= 0;
2094 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
2099 static struct data_backref
*find_data_backref(struct extent_record
*rec
,
2100 u64 parent
, u64 root
,
2101 u64 owner
, u64 offset
)
2103 struct list_head
*cur
= rec
->backrefs
.next
;
2104 struct extent_backref
*node
;
2105 struct data_backref
*back
;
2107 while(cur
!= &rec
->backrefs
) {
2108 node
= list_entry(cur
, struct extent_backref
, list
);
2112 back
= (struct data_backref
*)node
;
2114 if (!node
->full_backref
)
2116 if (parent
== back
->parent
)
2119 if (node
->full_backref
)
2121 if (back
->root
== root
&& back
->owner
== owner
&&
2122 back
->offset
== offset
)
2129 static struct data_backref
*alloc_data_backref(struct extent_record
*rec
,
2130 u64 parent
, u64 root
,
2131 u64 owner
, u64 offset
,
2134 struct data_backref
*ref
= malloc(sizeof(*ref
));
2135 memset(&ref
->node
, 0, sizeof(ref
->node
));
2136 ref
->node
.is_data
= 1;
2139 ref
->parent
= parent
;
2142 ref
->node
.full_backref
= 1;
2146 ref
->offset
= offset
;
2147 ref
->node
.full_backref
= 0;
2151 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
2152 if (max_size
> rec
->max_size
)
2153 rec
->max_size
= max_size
;
2157 static int add_extent_rec(struct cache_tree
*extent_cache
,
2158 struct btrfs_key
*parent_key
,
2159 u64 start
, u64 nr
, u64 extent_item_refs
,
2160 int is_root
, int inc_ref
, int set_checked
,
2163 struct extent_record
*rec
;
2164 struct cache_extent
*cache
;
2167 cache
= find_cache_extent(extent_cache
, start
, nr
);
2169 rec
= container_of(cache
, struct extent_record
, cache
);
2173 rec
->nr
= max(nr
, max_size
);
2175 if (start
!= rec
->start
) {
2176 fprintf(stderr
, "warning, start mismatch %llu %llu\n",
2177 (unsigned long long)rec
->start
,
2178 (unsigned long long)start
);
2181 if (extent_item_refs
) {
2182 if (rec
->extent_item_refs
) {
2183 fprintf(stderr
, "block %llu rec "
2184 "extent_item_refs %llu, passed %llu\n",
2185 (unsigned long long)start
,
2186 (unsigned long long)
2187 rec
->extent_item_refs
,
2188 (unsigned long long)extent_item_refs
);
2190 rec
->extent_item_refs
= extent_item_refs
;
2195 rec
->content_checked
= 1;
2196 rec
->owner_ref_checked
= 1;
2200 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
2202 if (rec
->max_size
< max_size
)
2203 rec
->max_size
= max_size
;
2205 maybe_free_extent_rec(extent_cache
, rec
);
2208 rec
= malloc(sizeof(*rec
));
2210 rec
->max_size
= max_size
;
2211 rec
->nr
= max(nr
, max_size
);
2212 rec
->content_checked
= 0;
2213 rec
->owner_ref_checked
= 0;
2214 INIT_LIST_HEAD(&rec
->backrefs
);
2226 if (extent_item_refs
)
2227 rec
->extent_item_refs
= extent_item_refs
;
2229 rec
->extent_item_refs
= 0;
2232 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
2234 memset(&rec
->parent_key
, 0, sizeof(*parent_key
));
2236 rec
->cache
.start
= start
;
2237 rec
->cache
.size
= nr
;
2238 ret
= insert_existing_cache_extent(extent_cache
, &rec
->cache
);
2242 rec
->content_checked
= 1;
2243 rec
->owner_ref_checked
= 1;
2248 static int add_tree_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
2249 u64 parent
, u64 root
, int found_ref
)
2251 struct extent_record
*rec
;
2252 struct tree_backref
*back
;
2253 struct cache_extent
*cache
;
2255 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2257 add_extent_rec(extent_cache
, NULL
, bytenr
, 1, 0, 0, 0, 0, 0);
2258 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2263 rec
= container_of(cache
, struct extent_record
, cache
);
2264 if (rec
->start
!= bytenr
) {
2268 back
= find_tree_backref(rec
, parent
, root
);
2270 back
= alloc_tree_backref(rec
, parent
, root
);
2273 if (back
->node
.found_ref
) {
2274 fprintf(stderr
, "Extent back ref already exists "
2275 "for %llu parent %llu root %llu \n",
2276 (unsigned long long)bytenr
,
2277 (unsigned long long)parent
,
2278 (unsigned long long)root
);
2280 back
->node
.found_ref
= 1;
2282 if (back
->node
.found_extent_tree
) {
2283 fprintf(stderr
, "Extent back ref already exists "
2284 "for %llu parent %llu root %llu \n",
2285 (unsigned long long)bytenr
,
2286 (unsigned long long)parent
,
2287 (unsigned long long)root
);
2289 back
->node
.found_extent_tree
= 1;
2294 static int add_data_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
2295 u64 parent
, u64 root
, u64 owner
, u64 offset
,
2296 u32 num_refs
, int found_ref
, u64 max_size
)
2298 struct extent_record
*rec
;
2299 struct data_backref
*back
;
2300 struct cache_extent
*cache
;
2302 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2304 add_extent_rec(extent_cache
, NULL
, bytenr
, 1, 0, 0, 0, 0,
2306 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2311 rec
= container_of(cache
, struct extent_record
, cache
);
2312 if (rec
->start
!= bytenr
) {
2315 if (rec
->max_size
< max_size
)
2316 rec
->max_size
= max_size
;
2318 back
= find_data_backref(rec
, parent
, root
, owner
, offset
);
2320 back
= alloc_data_backref(rec
, parent
, root
, owner
, offset
,
2324 BUG_ON(num_refs
!= 1);
2325 back
->node
.found_ref
= 1;
2326 back
->found_ref
+= 1;
2328 if (back
->node
.found_extent_tree
) {
2329 fprintf(stderr
, "Extent back ref already exists "
2330 "for %llu parent %llu root %llu"
2331 "owner %llu offset %llu num_refs %lu\n",
2332 (unsigned long long)bytenr
,
2333 (unsigned long long)parent
,
2334 (unsigned long long)root
,
2335 (unsigned long long)owner
,
2336 (unsigned long long)offset
,
2337 (unsigned long)num_refs
);
2339 back
->num_refs
= num_refs
;
2340 back
->node
.found_extent_tree
= 1;
2345 static int add_pending(struct cache_tree
*pending
,
2346 struct cache_tree
*seen
, u64 bytenr
, u32 size
)
2349 ret
= insert_cache_extent(seen
, bytenr
, size
);
2352 insert_cache_extent(pending
, bytenr
, size
);
2356 static int pick_next_pending(struct cache_tree
*pending
,
2357 struct cache_tree
*reada
,
2358 struct cache_tree
*nodes
,
2359 u64 last
, struct block_info
*bits
, int bits_nr
,
2362 unsigned long node_start
= last
;
2363 struct cache_extent
*cache
;
2366 cache
= find_first_cache_extent(reada
, 0);
2368 bits
[0].start
= cache
->start
;
2369 bits
[1].size
= cache
->size
;
2374 if (node_start
> 32768)
2375 node_start
-= 32768;
2377 cache
= find_first_cache_extent(nodes
, node_start
);
2379 cache
= find_first_cache_extent(nodes
, 0);
2382 cache
= find_first_cache_extent(pending
, 0);
2387 bits
[ret
].start
= cache
->start
;
2388 bits
[ret
].size
= cache
->size
;
2389 cache
= next_cache_extent(cache
);
2391 } while (cache
&& ret
< bits_nr
);
2397 bits
[ret
].start
= cache
->start
;
2398 bits
[ret
].size
= cache
->size
;
2399 cache
= next_cache_extent(cache
);
2401 } while (cache
&& ret
< bits_nr
);
2403 if (bits_nr
- ret
> 8) {
2404 u64 lookup
= bits
[0].start
+ bits
[0].size
;
2405 struct cache_extent
*next
;
2406 next
= find_first_cache_extent(pending
, lookup
);
2408 if (next
->start
- lookup
> 32768)
2410 bits
[ret
].start
= next
->start
;
2411 bits
[ret
].size
= next
->size
;
2412 lookup
= next
->start
+ next
->size
;
2416 next
= next_cache_extent(next
);
2424 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2425 static int process_extent_ref_v0(struct cache_tree
*extent_cache
,
2426 struct extent_buffer
*leaf
, int slot
)
2428 struct btrfs_extent_ref_v0
*ref0
;
2429 struct btrfs_key key
;
2431 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
2432 ref0
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_ref_v0
);
2433 if (btrfs_ref_objectid_v0(leaf
, ref0
) < BTRFS_FIRST_FREE_OBJECTID
) {
2434 add_tree_backref(extent_cache
, key
.objectid
, key
.offset
, 0, 0);
2436 add_data_backref(extent_cache
, key
.objectid
, key
.offset
, 0,
2437 0, 0, btrfs_ref_count_v0(leaf
, ref0
), 0, 0);
2443 static int process_extent_item(struct cache_tree
*extent_cache
,
2444 struct extent_buffer
*eb
, int slot
)
2446 struct btrfs_extent_item
*ei
;
2447 struct btrfs_extent_inline_ref
*iref
;
2448 struct btrfs_extent_data_ref
*dref
;
2449 struct btrfs_shared_data_ref
*sref
;
2450 struct btrfs_key key
;
2454 u32 item_size
= btrfs_item_size_nr(eb
, slot
);
2458 btrfs_item_key_to_cpu(eb
, &key
, slot
);
2460 if (item_size
< sizeof(*ei
)) {
2461 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2462 struct btrfs_extent_item_v0
*ei0
;
2463 BUG_ON(item_size
!= sizeof(*ei0
));
2464 ei0
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item_v0
);
2465 refs
= btrfs_extent_refs_v0(eb
, ei0
);
2469 return add_extent_rec(extent_cache
, NULL
, key
.objectid
,
2470 key
.offset
, refs
, 0, 0, 0, key
.offset
);
2473 ei
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item
);
2474 refs
= btrfs_extent_refs(eb
, ei
);
2476 add_extent_rec(extent_cache
, NULL
, key
.objectid
, key
.offset
,
2477 refs
, 0, 0, 0, key
.offset
);
2479 ptr
= (unsigned long)(ei
+ 1);
2480 if (btrfs_extent_flags(eb
, ei
) & BTRFS_EXTENT_FLAG_TREE_BLOCK
)
2481 ptr
+= sizeof(struct btrfs_tree_block_info
);
2483 end
= (unsigned long)ei
+ item_size
;
2485 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
2486 type
= btrfs_extent_inline_ref_type(eb
, iref
);
2487 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
2489 case BTRFS_TREE_BLOCK_REF_KEY
:
2490 add_tree_backref(extent_cache
, key
.objectid
,
2493 case BTRFS_SHARED_BLOCK_REF_KEY
:
2494 add_tree_backref(extent_cache
, key
.objectid
,
2497 case BTRFS_EXTENT_DATA_REF_KEY
:
2498 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
2499 add_data_backref(extent_cache
, key
.objectid
, 0,
2500 btrfs_extent_data_ref_root(eb
, dref
),
2501 btrfs_extent_data_ref_objectid(eb
,
2503 btrfs_extent_data_ref_offset(eb
, dref
),
2504 btrfs_extent_data_ref_count(eb
, dref
),
2507 case BTRFS_SHARED_DATA_REF_KEY
:
2508 sref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
2509 add_data_backref(extent_cache
, key
.objectid
, offset
,
2511 btrfs_shared_data_ref_count(eb
, sref
),
2515 fprintf(stderr
, "corrupt extent record: key %Lu %u %Lu\n",
2516 key
.objectid
, key
.type
, key
.offset
);
2519 ptr
+= btrfs_extent_inline_ref_size(type
);
2526 static int run_next_block(struct btrfs_root
*root
,
2527 struct block_info
*bits
,
2530 struct cache_tree
*pending
,
2531 struct cache_tree
*seen
,
2532 struct cache_tree
*reada
,
2533 struct cache_tree
*nodes
,
2534 struct cache_tree
*extent_cache
)
2536 struct extent_buffer
*buf
;
2545 struct btrfs_key key
;
2546 struct cache_extent
*cache
;
2549 ret
= pick_next_pending(pending
, reada
, nodes
, *last
, bits
,
2550 bits_nr
, &reada_bits
);
2555 for(i
= 0; i
< ret
; i
++) {
2556 insert_cache_extent(reada
, bits
[i
].start
,
2559 /* fixme, get the parent transid */
2560 readahead_tree_block(root
, bits
[i
].start
,
2564 *last
= bits
[0].start
;
2565 bytenr
= bits
[0].start
;
2566 size
= bits
[0].size
;
2568 cache
= find_cache_extent(pending
, bytenr
, size
);
2570 remove_cache_extent(pending
, cache
);
2573 cache
= find_cache_extent(reada
, bytenr
, size
);
2575 remove_cache_extent(reada
, cache
);
2578 cache
= find_cache_extent(nodes
, bytenr
, size
);
2580 remove_cache_extent(nodes
, cache
);
2584 /* fixme, get the real parent transid */
2585 buf
= read_tree_block(root
, bytenr
, size
, 0);
2586 if (!extent_buffer_uptodate(buf
)) {
2587 record_bad_block_io(root
->fs_info
,
2588 extent_cache
, bytenr
, size
);
2589 free_extent_buffer(buf
);
2593 nritems
= btrfs_header_nritems(buf
);
2595 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
, size
, NULL
, &flags
);
2597 flags
= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
2599 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
) {
2604 owner
= btrfs_header_owner(buf
);
2607 ret
= check_block(root
, extent_cache
, buf
, flags
);
2611 if (btrfs_is_leaf(buf
)) {
2612 btree_space_waste
+= btrfs_leaf_free_space(root
, buf
);
2613 for (i
= 0; i
< nritems
; i
++) {
2614 struct btrfs_file_extent_item
*fi
;
2615 btrfs_item_key_to_cpu(buf
, &key
, i
);
2616 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
2617 process_extent_item(extent_cache
, buf
, i
);
2620 if (key
.type
== BTRFS_EXTENT_CSUM_KEY
) {
2622 btrfs_item_size_nr(buf
, i
);
2625 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
2628 if (key
.type
== BTRFS_EXTENT_REF_V0_KEY
) {
2629 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2630 process_extent_ref_v0(extent_cache
, buf
, i
);
2637 if (key
.type
== BTRFS_TREE_BLOCK_REF_KEY
) {
2638 add_tree_backref(extent_cache
, key
.objectid
, 0,
2642 if (key
.type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
2643 add_tree_backref(extent_cache
, key
.objectid
,
2647 if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
) {
2648 struct btrfs_extent_data_ref
*ref
;
2649 ref
= btrfs_item_ptr(buf
, i
,
2650 struct btrfs_extent_data_ref
);
2651 add_data_backref(extent_cache
,
2653 btrfs_extent_data_ref_root(buf
, ref
),
2654 btrfs_extent_data_ref_objectid(buf
,
2656 btrfs_extent_data_ref_offset(buf
, ref
),
2657 btrfs_extent_data_ref_count(buf
, ref
),
2658 0, root
->sectorsize
);
2661 if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
) {
2662 struct btrfs_shared_data_ref
*ref
;
2663 ref
= btrfs_item_ptr(buf
, i
,
2664 struct btrfs_shared_data_ref
);
2665 add_data_backref(extent_cache
,
2666 key
.objectid
, key
.offset
, 0, 0, 0,
2667 btrfs_shared_data_ref_count(buf
, ref
),
2668 0, root
->sectorsize
);
2671 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
2673 fi
= btrfs_item_ptr(buf
, i
,
2674 struct btrfs_file_extent_item
);
2675 if (btrfs_file_extent_type(buf
, fi
) ==
2676 BTRFS_FILE_EXTENT_INLINE
)
2678 if (btrfs_file_extent_disk_bytenr(buf
, fi
) == 0)
2681 data_bytes_allocated
+=
2682 btrfs_file_extent_disk_num_bytes(buf
, fi
);
2683 if (data_bytes_allocated
< root
->sectorsize
) {
2686 data_bytes_referenced
+=
2687 btrfs_file_extent_num_bytes(buf
, fi
);
2688 ret
= add_extent_rec(extent_cache
, NULL
,
2689 btrfs_file_extent_disk_bytenr(buf
, fi
),
2690 btrfs_file_extent_disk_num_bytes(buf
, fi
),
2692 btrfs_file_extent_disk_num_bytes(buf
, fi
));
2693 add_data_backref(extent_cache
,
2694 btrfs_file_extent_disk_bytenr(buf
, fi
),
2695 parent
, owner
, key
.objectid
, key
.offset
-
2696 btrfs_file_extent_offset(buf
, fi
), 1, 1,
2697 btrfs_file_extent_disk_num_bytes(buf
, fi
));
2702 struct btrfs_key first_key
;
2704 first_key
.objectid
= 0;
2707 btrfs_item_key_to_cpu(buf
, &first_key
, 0);
2708 level
= btrfs_header_level(buf
);
2709 for (i
= 0; i
< nritems
; i
++) {
2710 u64 ptr
= btrfs_node_blockptr(buf
, i
);
2711 u32 size
= btrfs_level_size(root
, level
- 1);
2712 btrfs_node_key_to_cpu(buf
, &key
, i
);
2713 ret
= add_extent_rec(extent_cache
, &key
,
2714 ptr
, size
, 0, 0, 1, 0, size
);
2717 add_tree_backref(extent_cache
, ptr
, parent
, owner
, 1);
2720 add_pending(nodes
, seen
, ptr
, size
);
2722 add_pending(pending
, seen
, ptr
, size
);
2725 btree_space_waste
+= (BTRFS_NODEPTRS_PER_BLOCK(root
) -
2726 nritems
) * sizeof(struct btrfs_key_ptr
);
2728 total_btree_bytes
+= buf
->len
;
2729 if (fs_root_objectid(btrfs_header_owner(buf
)))
2730 total_fs_tree_bytes
+= buf
->len
;
2731 if (!found_old_backref
&&
2732 btrfs_header_owner(buf
) == BTRFS_TREE_RELOC_OBJECTID
&&
2733 btrfs_header_backref_rev(buf
) == BTRFS_MIXED_BACKREF_REV
&&
2734 !btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_RELOC
))
2735 found_old_backref
= 1;
2737 free_extent_buffer(buf
);
2741 static int add_root_to_pending(struct extent_buffer
*buf
,
2742 struct block_info
*bits
,
2744 struct cache_tree
*extent_cache
,
2745 struct cache_tree
*pending
,
2746 struct cache_tree
*seen
,
2747 struct cache_tree
*reada
,
2748 struct cache_tree
*nodes
,
2749 struct btrfs_key
*root_key
)
2751 if (btrfs_header_level(buf
) > 0)
2752 add_pending(nodes
, seen
, buf
->start
, buf
->len
);
2754 add_pending(pending
, seen
, buf
->start
, buf
->len
);
2755 add_extent_rec(extent_cache
, NULL
, buf
->start
, buf
->len
,
2756 0, 1, 1, 0, buf
->len
);
2758 if (root_key
->objectid
== BTRFS_TREE_RELOC_OBJECTID
||
2759 btrfs_header_backref_rev(buf
) < BTRFS_MIXED_BACKREF_REV
)
2760 add_tree_backref(extent_cache
, buf
->start
, buf
->start
,
2763 add_tree_backref(extent_cache
, buf
->start
, 0,
2764 root_key
->objectid
, 1);
2768 /* as we fix the tree, we might be deleting blocks that
2769 * we're tracking for repair. This hook makes sure we
2770 * remove any backrefs for blocks as we are fixing them.
2772 static int free_extent_hook(struct btrfs_trans_handle
*trans
,
2773 struct btrfs_root
*root
,
2774 u64 bytenr
, u64 num_bytes
, u64 parent
,
2775 u64 root_objectid
, u64 owner
, u64 offset
,
2778 struct extent_record
*rec
;
2779 struct cache_extent
*cache
;
2781 struct cache_tree
*extent_cache
= root
->fs_info
->fsck_extent_cache
;
2783 is_data
= owner
>= BTRFS_FIRST_FREE_OBJECTID
;
2784 cache
= find_cache_extent(extent_cache
, bytenr
, num_bytes
);
2788 rec
= container_of(cache
, struct extent_record
, cache
);
2790 struct data_backref
*back
;
2791 back
= find_data_backref(rec
, parent
, root_objectid
, owner
,
2795 if (back
->node
.found_ref
) {
2796 back
->found_ref
-= refs_to_drop
;
2798 rec
->refs
-= refs_to_drop
;
2800 if (back
->node
.found_extent_tree
) {
2801 back
->num_refs
-= refs_to_drop
;
2802 if (rec
->extent_item_refs
)
2803 rec
->extent_item_refs
-= refs_to_drop
;
2805 if (back
->found_ref
== 0)
2806 back
->node
.found_ref
= 0;
2807 if (back
->num_refs
== 0)
2808 back
->node
.found_extent_tree
= 0;
2810 if (!back
->node
.found_extent_tree
&& back
->node
.found_ref
) {
2811 list_del(&back
->node
.list
);
2815 struct tree_backref
*back
;
2816 back
= find_tree_backref(rec
, parent
, root_objectid
);
2819 if (back
->node
.found_ref
) {
2822 back
->node
.found_ref
= 0;
2824 if (back
->node
.found_extent_tree
) {
2825 if (rec
->extent_item_refs
)
2826 rec
->extent_item_refs
--;
2827 back
->node
.found_extent_tree
= 0;
2829 if (!back
->node
.found_extent_tree
&& back
->node
.found_ref
) {
2830 list_del(&back
->node
.list
);
2834 maybe_free_extent_rec(extent_cache
, rec
);
2839 static int delete_extent_records(struct btrfs_trans_handle
*trans
,
2840 struct btrfs_root
*root
,
2841 struct btrfs_path
*path
,
2842 u64 bytenr
, u64 new_len
)
2844 struct btrfs_key key
;
2845 struct btrfs_key found_key
;
2846 struct extent_buffer
*leaf
;
2851 key
.objectid
= bytenr
;
2853 key
.offset
= (u64
)-1;
2856 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
,
2863 if (path
->slots
[0] == 0)
2869 leaf
= path
->nodes
[0];
2870 slot
= path
->slots
[0];
2872 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
2873 if (found_key
.objectid
!= bytenr
)
2876 if (found_key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
2877 found_key
.type
!= BTRFS_TREE_BLOCK_REF_KEY
&&
2878 found_key
.type
!= BTRFS_EXTENT_DATA_REF_KEY
&&
2879 found_key
.type
!= BTRFS_EXTENT_REF_V0_KEY
&&
2880 found_key
.type
!= BTRFS_SHARED_BLOCK_REF_KEY
&&
2881 found_key
.type
!= BTRFS_SHARED_DATA_REF_KEY
) {
2882 btrfs_release_path(NULL
, path
);
2883 if (found_key
.type
== 0) {
2884 if (found_key
.offset
== 0)
2886 key
.offset
= found_key
.offset
- 1;
2887 key
.type
= found_key
.type
;
2889 key
.type
= found_key
.type
- 1;
2890 key
.offset
= (u64
)-1;
2894 fprintf(stderr
, "repair deleting extent record: key %Lu %u %Lu\n",
2895 found_key
.objectid
, found_key
.type
, found_key
.offset
);
2897 ret
= btrfs_del_item(trans
, root
->fs_info
->extent_root
, path
);
2900 btrfs_release_path(NULL
, path
);
2902 if (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
2903 ret
= btrfs_update_block_group(trans
, root
, bytenr
,
2904 found_key
.offset
, 0, 0);
2910 btrfs_release_path(NULL
, path
);
2915 * for a single backref, this will allocate a new extent
2916 * and add the backref to it.
2918 static int record_extent(struct btrfs_trans_handle
*trans
,
2919 struct btrfs_fs_info
*info
,
2920 struct btrfs_path
*path
,
2921 struct extent_record
*rec
,
2922 struct extent_backref
*back
,
2923 int allocated
, u64 flags
)
2926 struct btrfs_root
*extent_root
= info
->extent_root
;
2927 struct extent_buffer
*leaf
;
2928 struct btrfs_key ins_key
;
2929 struct btrfs_extent_item
*ei
;
2930 struct tree_backref
*tback
;
2931 struct data_backref
*dback
;
2932 struct btrfs_tree_block_info
*bi
;
2935 rec
->max_size
= max_t(u64
, rec
->max_size
,
2936 info
->extent_root
->leafsize
);
2939 u32 item_size
= sizeof(*ei
);
2942 item_size
+= sizeof(*bi
);
2944 ins_key
.objectid
= rec
->start
;
2945 ins_key
.offset
= rec
->max_size
;
2946 ins_key
.type
= BTRFS_EXTENT_ITEM_KEY
;
2948 ret
= btrfs_insert_empty_item(trans
, extent_root
, path
,
2949 &ins_key
, item_size
);
2953 leaf
= path
->nodes
[0];
2954 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
2955 struct btrfs_extent_item
);
2957 btrfs_set_extent_refs(leaf
, ei
, 0);
2958 btrfs_set_extent_generation(leaf
, ei
, rec
->generation
);
2960 if (back
->is_data
) {
2961 btrfs_set_extent_flags(leaf
, ei
,
2962 BTRFS_EXTENT_FLAG_DATA
);
2964 struct btrfs_disk_key copy_key
;;
2966 tback
= (struct tree_backref
*)back
;
2967 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
2968 memset_extent_buffer(leaf
, 0, (unsigned long)bi
,
2970 memset(©_key
, 0, sizeof(copy_key
));
2972 copy_key
.objectid
= le64_to_cpu(rec
->info_objectid
);
2973 btrfs_set_tree_block_level(leaf
, bi
, rec
->info_level
);
2974 btrfs_set_tree_block_key(leaf
, bi
, ©_key
);
2976 btrfs_set_extent_flags(leaf
, ei
,
2977 BTRFS_EXTENT_FLAG_TREE_BLOCK
| flags
);
2980 btrfs_mark_buffer_dirty(leaf
);
2981 ret
= btrfs_update_block_group(trans
, extent_root
, rec
->start
,
2982 rec
->max_size
, 1, 0);
2985 btrfs_release_path(NULL
, path
);
2988 if (back
->is_data
) {
2992 dback
= (struct data_backref
*)back
;
2993 if (back
->full_backref
)
2994 parent
= dback
->parent
;
2998 for (i
= 0; i
< dback
->found_ref
; i
++) {
2999 /* if parent != 0, we're doing a full backref
3000 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
3001 * just makes the backref allocator create a data
3004 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
3005 rec
->start
, rec
->max_size
,
3009 BTRFS_FIRST_FREE_OBJECTID
:
3015 fprintf(stderr
, "adding new data backref"
3016 " on %llu %s %llu owner %llu"
3017 " offset %llu found %d\n",
3018 (unsigned long long)rec
->start
,
3019 back
->full_backref
?
3021 back
->full_backref
?
3022 (unsigned long long)parent
:
3023 (unsigned long long)dback
->root
,
3024 (unsigned long long)dback
->owner
,
3025 (unsigned long long)dback
->offset
,
3030 tback
= (struct tree_backref
*)back
;
3031 if (back
->full_backref
)
3032 parent
= tback
->parent
;
3036 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
3037 rec
->start
, rec
->max_size
,
3038 parent
, tback
->root
, 0, 0);
3039 fprintf(stderr
, "adding new tree backref on "
3040 "start %llu len %llu parent %llu root %llu\n",
3041 rec
->start
, rec
->max_size
, tback
->parent
, tback
->root
);
3046 btrfs_release_path(NULL
, path
);
3051 * when an incorrect extent item is found, this will delete
3052 * all of the existing entries for it and recreate them
3053 * based on what the tree scan found.
3055 static int fixup_extent_refs(struct btrfs_trans_handle
*trans
,
3056 struct btrfs_fs_info
*info
,
3057 struct extent_record
*rec
)
3060 struct btrfs_path
*path
;
3061 struct list_head
*cur
= rec
->backrefs
.next
;
3062 struct cache_extent
*cache
;
3063 struct extent_backref
*back
;
3067 /* remember our flags for recreating the extent */
3068 ret
= btrfs_lookup_extent_info(NULL
, info
->extent_root
, rec
->start
,
3069 rec
->max_size
, NULL
, &flags
);
3071 flags
= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
3073 path
= btrfs_alloc_path();
3075 /* step one, delete all the existing records */
3076 ret
= delete_extent_records(trans
, info
->extent_root
, path
,
3077 rec
->start
, rec
->max_size
);
3082 /* was this block corrupt? If so, don't add references to it */
3083 cache
= find_cache_extent(info
->corrupt_blocks
, rec
->start
, rec
->max_size
);
3089 /* step two, recreate all the refs we did find */
3090 while(cur
!= &rec
->backrefs
) {
3091 back
= list_entry(cur
, struct extent_backref
, list
);
3095 * if we didn't find any references, don't create a
3098 if (!back
->found_ref
)
3101 ret
= record_extent(trans
, info
, path
, rec
, back
, allocated
, flags
);
3108 btrfs_free_path(path
);
3112 /* right now we only prune from the extent allocation tree */
3113 static int prune_one_block(struct btrfs_trans_handle
*trans
,
3114 struct btrfs_fs_info
*info
,
3115 struct btrfs_corrupt_block
*corrupt
)
3118 struct btrfs_path path
;
3119 struct extent_buffer
*eb
;
3123 int level
= corrupt
->level
+ 1;
3125 btrfs_init_path(&path
);
3127 /* we want to stop at the parent to our busted block */
3128 path
.lowest_level
= level
;
3130 ret
= btrfs_search_slot(trans
, info
->extent_root
,
3131 &corrupt
->key
, &path
, -1, 1);
3136 eb
= path
.nodes
[level
];
3143 * hopefully the search gave us the block we want to prune,
3144 * lets try that first
3146 slot
= path
.slots
[level
];
3147 found
= btrfs_node_blockptr(eb
, slot
);
3148 if (found
== corrupt
->cache
.start
)
3151 nritems
= btrfs_header_nritems(eb
);
3153 /* the search failed, lets scan this node and hope we find it */
3154 for (slot
= 0; slot
< nritems
; slot
++) {
3155 found
= btrfs_node_blockptr(eb
, slot
);
3156 if (found
== corrupt
->cache
.start
)
3160 * we couldn't find the bad block. TODO, search all the nodes for pointers
3163 if (eb
== info
->extent_root
->node
) {
3168 btrfs_release_path(NULL
, &path
);
3173 printk("deleting pointer to block %Lu\n", corrupt
->cache
.start
);
3174 ret
= btrfs_del_ptr(trans
, info
->extent_root
, &path
, level
, slot
);
3177 btrfs_release_path(NULL
, &path
);
3181 static int prune_corrupt_blocks(struct btrfs_trans_handle
*trans
,
3182 struct btrfs_fs_info
*info
)
3184 struct cache_extent
*cache
;
3185 struct btrfs_corrupt_block
*corrupt
;
3187 cache
= find_first_cache_extent(info
->corrupt_blocks
, 0);
3191 corrupt
= container_of(cache
, struct btrfs_corrupt_block
, cache
);
3192 prune_one_block(trans
, info
, corrupt
);
3193 cache
= next_cache_extent(cache
);
3198 static void free_corrupt_blocks(struct btrfs_fs_info
*info
)
3200 struct cache_extent
*cache
;
3201 struct btrfs_corrupt_block
*corrupt
;
3204 cache
= find_first_cache_extent(info
->corrupt_blocks
, 0);
3207 corrupt
= container_of(cache
, struct btrfs_corrupt_block
, cache
);
3208 remove_cache_extent(info
->corrupt_blocks
, cache
);
3213 static int check_block_group(struct btrfs_trans_handle
*trans
,
3214 struct btrfs_fs_info
*info
,
3215 struct map_lookup
*map
,
3218 struct btrfs_key key
;
3219 struct btrfs_path path
;
3222 key
.objectid
= map
->ce
.start
;
3223 key
.offset
= map
->ce
.size
;
3224 key
.type
= BTRFS_BLOCK_GROUP_ITEM_KEY
;
3226 btrfs_init_path(&path
);
3227 ret
= btrfs_search_slot(NULL
, info
->extent_root
,
3229 btrfs_release_path(NULL
, &path
);
3233 ret
= btrfs_make_block_group(trans
, info
->extent_root
, 0, map
->type
,
3234 BTRFS_FIRST_CHUNK_TREE_OBJECTID
,
3235 key
.objectid
, key
.offset
);
3241 static int check_block_groups(struct btrfs_trans_handle
*trans
,
3242 struct btrfs_fs_info
*info
, int *reinit
)
3244 struct cache_extent
*ce
;
3245 struct map_lookup
*map
;
3246 struct btrfs_mapping_tree
*map_tree
= &info
->mapping_tree
;
3248 /* this isn't quite working */
3251 ce
= find_first_cache_extent(&map_tree
->cache_tree
, 0);
3255 map
= container_of(ce
, struct map_lookup
, ce
);
3256 check_block_group(trans
, info
, map
, reinit
);
3257 ce
= next_cache_extent(ce
);
3262 static int check_extent_refs(struct btrfs_trans_handle
*trans
,
3263 struct btrfs_root
*root
,
3264 struct cache_tree
*extent_cache
, int repair
)
3266 struct extent_record
*rec
;
3267 struct cache_extent
*cache
;
3275 * if we're doing a repair, we have to make sure
3276 * we don't allocate from the problem extents.
3277 * In the worst case, this will be all the
3280 cache
= find_first_cache_extent(extent_cache
, 0);
3282 rec
= container_of(cache
, struct extent_record
, cache
);
3283 btrfs_pin_extent(root
->fs_info
,
3284 rec
->start
, rec
->max_size
);
3285 cache
= next_cache_extent(cache
);
3288 /* pin down all the corrupted blocks too */
3289 cache
= find_first_cache_extent(root
->fs_info
->corrupt_blocks
, 0);
3291 rec
= container_of(cache
, struct extent_record
, cache
);
3292 btrfs_pin_extent(root
->fs_info
,
3293 rec
->start
, rec
->max_size
);
3294 cache
= next_cache_extent(cache
);
3296 prune_corrupt_blocks(trans
, root
->fs_info
);
3297 check_block_groups(trans
, root
->fs_info
, &reinit
);
3299 btrfs_read_block_groups(root
->fs_info
->extent_root
);
3303 cache
= find_first_cache_extent(extent_cache
, 0);
3306 rec
= container_of(cache
, struct extent_record
, cache
);
3307 if (rec
->refs
!= rec
->extent_item_refs
) {
3308 fprintf(stderr
, "ref mismatch on [%llu %llu] ",
3309 (unsigned long long)rec
->start
,
3310 (unsigned long long)rec
->nr
);
3311 fprintf(stderr
, "extent item %llu, found %llu\n",
3312 (unsigned long long)rec
->extent_item_refs
,
3313 (unsigned long long)rec
->refs
);
3314 if (!fixed
&& repair
) {
3315 ret
= fixup_extent_refs(trans
, root
->fs_info
, rec
);
3323 if (all_backpointers_checked(rec
, 1)) {
3324 fprintf(stderr
, "backpointer mismatch on [%llu %llu]\n",
3325 (unsigned long long)rec
->start
,
3326 (unsigned long long)rec
->nr
);
3328 if (!fixed
&& repair
) {
3329 ret
= fixup_extent_refs(trans
, root
->fs_info
, rec
);
3337 if (!rec
->owner_ref_checked
) {
3338 fprintf(stderr
, "owner ref check failed [%llu %llu]\n",
3339 (unsigned long long)rec
->start
,
3340 (unsigned long long)rec
->nr
);
3341 if (!fixed
&& repair
) {
3342 ret
= fixup_extent_refs(trans
, root
->fs_info
, rec
);
3350 remove_cache_extent(extent_cache
, cache
);
3351 free_all_extent_backrefs(rec
);
3357 fprintf(stderr
, "failed to repair damaged filesystem, aborting\n");
3360 btrfs_fix_block_accounting(trans
, root
);
3363 fprintf(stderr
, "repaired damaged extent references\n");
3369 static int check_extents(struct btrfs_trans_handle
*trans
,
3370 struct btrfs_root
*root
, int repair
)
3372 struct cache_tree extent_cache
;
3373 struct cache_tree seen
;
3374 struct cache_tree pending
;
3375 struct cache_tree reada
;
3376 struct cache_tree nodes
;
3377 struct cache_tree corrupt_blocks
;
3378 struct btrfs_path path
;
3379 struct btrfs_key key
;
3380 struct btrfs_key found_key
;
3383 struct block_info
*bits
;
3385 struct extent_buffer
*leaf
;
3387 struct btrfs_root_item ri
;
3389 cache_tree_init(&extent_cache
);
3390 cache_tree_init(&seen
);
3391 cache_tree_init(&pending
);
3392 cache_tree_init(&nodes
);
3393 cache_tree_init(&reada
);
3394 cache_tree_init(&corrupt_blocks
);
3397 root
->fs_info
->fsck_extent_cache
= &extent_cache
;
3398 root
->fs_info
->free_extent_hook
= free_extent_hook
;
3399 root
->fs_info
->corrupt_blocks
= &corrupt_blocks
;
3403 bits
= malloc(bits_nr
* sizeof(struct block_info
));
3409 add_root_to_pending(root
->fs_info
->tree_root
->node
, bits
, bits_nr
,
3410 &extent_cache
, &pending
, &seen
, &reada
, &nodes
,
3411 &root
->fs_info
->tree_root
->root_key
);
3413 add_root_to_pending(root
->fs_info
->chunk_root
->node
, bits
, bits_nr
,
3414 &extent_cache
, &pending
, &seen
, &reada
, &nodes
,
3415 &root
->fs_info
->chunk_root
->root_key
);
3417 btrfs_init_path(&path
);
3420 btrfs_set_key_type(&key
, BTRFS_ROOT_ITEM_KEY
);
3421 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
,
3425 leaf
= path
.nodes
[0];
3426 slot
= path
.slots
[0];
3427 if (slot
>= btrfs_header_nritems(path
.nodes
[0])) {
3428 ret
= btrfs_next_leaf(root
, &path
);
3431 leaf
= path
.nodes
[0];
3432 slot
= path
.slots
[0];
3434 btrfs_item_key_to_cpu(leaf
, &found_key
, path
.slots
[0]);
3435 if (btrfs_key_type(&found_key
) == BTRFS_ROOT_ITEM_KEY
) {
3436 unsigned long offset
;
3437 struct extent_buffer
*buf
;
3439 offset
= btrfs_item_ptr_offset(leaf
, path
.slots
[0]);
3440 read_extent_buffer(leaf
, &ri
, offset
, sizeof(ri
));
3441 buf
= read_tree_block(root
->fs_info
->tree_root
,
3442 btrfs_root_bytenr(&ri
),
3443 btrfs_level_size(root
,
3444 btrfs_root_level(&ri
)), 0);
3445 add_root_to_pending(buf
, bits
, bits_nr
, &extent_cache
,
3446 &pending
, &seen
, &reada
, &nodes
,
3448 free_extent_buffer(buf
);
3452 btrfs_release_path(root
, &path
);
3454 ret
= run_next_block(root
, bits
, bits_nr
, &last
, &pending
,
3455 &seen
, &reada
, &nodes
, &extent_cache
);
3459 ret
= check_extent_refs(trans
, root
, &extent_cache
, repair
);
3462 free_corrupt_blocks(root
->fs_info
);
3463 root
->fs_info
->fsck_extent_cache
= NULL
;
3464 root
->fs_info
->free_extent_hook
= NULL
;
3465 root
->fs_info
->corrupt_blocks
= NULL
;
3471 static void print_usage(void)
3473 fprintf(stderr
, "usage: btrfsck dev\n");
3474 fprintf(stderr
, "%s\n", BTRFS_BUILD_VERSION
);
3478 static struct option long_options
[] = {
3479 { "super", 1, NULL
, 's' },
3480 { "repair", 0, NULL
, 0 },
3481 { "init-csum-tree", 0, NULL
, 0 },
3482 { "init-extent-tree", 0, NULL
, 0 },
3486 int main(int ac
, char **av
)
3488 struct cache_tree root_cache
;
3489 struct btrfs_root
*root
;
3490 struct btrfs_fs_info
*info
;
3491 struct btrfs_trans_handle
*trans
= NULL
;
3496 int option_index
= 0;
3497 int init_csum_tree
= 0;
3502 c
= getopt_long(ac
, av
, "", long_options
,
3509 bytenr
= btrfs_sb_offset(num
);
3510 printf("using SB copy %d, bytenr %llu\n", num
,
3511 (unsigned long long)bytenr
);
3516 if (option_index
== 1) {
3517 printf("enabling repair mode\n");
3520 } else if (option_index
== 2) {
3521 printf("Creating a new CRC tree\n");
3533 cache_tree_init(&root_cache
);
3535 if((ret
= check_mounted(av
[optind
])) < 0) {
3536 fprintf(stderr
, "Could not check mount status: %s\n", strerror(-ret
));
3539 fprintf(stderr
, "%s is currently mounted. Aborting.\n", av
[optind
]);
3543 info
= open_ctree_fs_info(av
[optind
], bytenr
, rw
, 1);
3548 if (!extent_buffer_uptodate(info
->tree_root
->node
) ||
3549 !extent_buffer_uptodate(info
->dev_root
->node
) ||
3550 !extent_buffer_uptodate(info
->extent_root
->node
) ||
3551 !extent_buffer_uptodate(info
->chunk_root
->node
)) {
3552 fprintf(stderr
, "Critical roots corrupted, unable to fsck the FS\n");
3556 root
= info
->fs_root
;
3558 fprintf(stderr
, "checking extents\n");
3560 trans
= btrfs_start_transaction(root
, 1);
3562 if (init_csum_tree
) {
3563 fprintf(stderr
, "Reinit crc root\n");
3564 ret
= btrfs_fsck_reinit_root(trans
, info
->csum_root
);
3566 fprintf(stderr
, "crc root initialization failed\n");
3571 ret
= check_extents(trans
, root
, repair
);
3573 fprintf(stderr
, "Errors found in extent allocation tree\n");
3575 fprintf(stderr
, "checking fs roots\n");
3576 ret
= check_fs_roots(root
, &root_cache
);
3580 fprintf(stderr
, "checking root refs\n");
3581 ret
= check_root_refs(root
, &root_cache
);
3583 free_root_recs(&root_cache
);
3585 ret
= btrfs_commit_transaction(trans
, root
);
3591 if (found_old_backref
) { /*
3592 * there was a disk format change when mixed
3593 * backref was in testing tree. The old format
3594 * existed about one week.
3596 printf("\n * Found old mixed backref format. "
3597 "The old format is not supported! *"
3598 "\n * Please mount the FS in readonly mode, "
3599 "backup data and re-format the FS. *\n\n");
3602 printf("found %llu bytes used err is %d\n",
3603 (unsigned long long)bytes_used
, ret
);
3604 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes
);
3605 printf("total tree bytes: %llu\n",
3606 (unsigned long long)total_btree_bytes
);
3607 printf("total fs tree bytes: %llu\n",
3608 (unsigned long long)total_fs_tree_bytes
);
3609 printf("btree space waste bytes: %llu\n",
3610 (unsigned long long)btree_space_waste
);
3611 printf("file data blocks allocated: %llu\n referenced %llu\n",
3612 (unsigned long long)data_bytes_allocated
,
3613 (unsigned long long)data_bytes_referenced
);
3614 printf("%s\n", BTRFS_BUILD_VERSION
);