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"
30 #include "print-tree.h"
31 #include "transaction.h"
36 static u64 bytes_used
= 0;
37 static u64 total_csum_bytes
= 0;
38 static u64 total_btree_bytes
= 0;
39 static u64 total_fs_tree_bytes
= 0;
40 static u64 btree_space_waste
= 0;
41 static u64 data_bytes_allocated
= 0;
42 static u64 data_bytes_referenced
= 0;
43 static int found_old_backref
= 0;
45 struct extent_backref
{
46 struct list_head list
;
47 unsigned int is_data
:1;
48 unsigned int found_extent_tree
:1;
49 unsigned int full_backref
:1;
50 unsigned int found_ref
:1;
54 struct extent_backref node
;
66 struct extent_backref node
;
73 struct extent_record
{
74 struct list_head backrefs
;
75 struct cache_extent cache
;
76 struct btrfs_disk_key parent_key
;
85 unsigned int content_checked
:1;
86 unsigned int owner_ref_checked
:1;
87 unsigned int is_root
:1;
90 struct inode_backref
{
91 struct list_head list
;
92 unsigned int found_dir_item
:1;
93 unsigned int found_dir_index
:1;
94 unsigned int found_inode_ref
:1;
95 unsigned int filetype
:8;
103 #define REF_ERR_NO_DIR_ITEM (1 << 0)
104 #define REF_ERR_NO_DIR_INDEX (1 << 1)
105 #define REF_ERR_NO_INODE_REF (1 << 2)
106 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
107 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
108 #define REF_ERR_DUP_INODE_REF (1 << 5)
109 #define REF_ERR_INDEX_UNMATCH (1 << 6)
110 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
111 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
112 #define REF_ERR_NO_ROOT_REF (1 << 9)
113 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
114 #define REF_ERR_DUP_ROOT_REF (1 << 11)
115 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
117 struct inode_record
{
118 struct list_head backrefs
;
119 unsigned int checked
:1;
120 unsigned int merging
:1;
121 unsigned int found_inode_item
:1;
122 unsigned int found_dir_item
:1;
123 unsigned int found_file_extent
:1;
124 unsigned int found_csum_item
:1;
125 unsigned int some_csum_missing
:1;
126 unsigned int nodatasum
:1;
139 u64 first_extent_gap
;
144 #define I_ERR_NO_INODE_ITEM (1 << 0)
145 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
146 #define I_ERR_DUP_INODE_ITEM (1 << 2)
147 #define I_ERR_DUP_DIR_INDEX (1 << 3)
148 #define I_ERR_ODD_DIR_ITEM (1 << 4)
149 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
150 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
151 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
152 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
153 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
154 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
155 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
156 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
157 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
159 struct root_backref
{
160 struct list_head list
;
161 unsigned int found_dir_item
:1;
162 unsigned int found_dir_index
:1;
163 unsigned int found_back_ref
:1;
164 unsigned int found_forward_ref
:1;
165 unsigned int reachable
:1;
175 struct list_head backrefs
;
176 struct cache_extent cache
;
177 unsigned int found_root_item
:1;
183 struct cache_extent cache
;
188 struct cache_extent cache
;
189 struct cache_tree root_cache
;
190 struct cache_tree inode_cache
;
191 struct inode_record
*current
;
200 struct walk_control
{
201 struct cache_tree shared
;
202 struct shared_node
*nodes
[BTRFS_MAX_LEVEL
];
207 static u8
imode_to_type(u32 imode
)
210 static unsigned char btrfs_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
211 [S_IFREG
>> S_SHIFT
] = BTRFS_FT_REG_FILE
,
212 [S_IFDIR
>> S_SHIFT
] = BTRFS_FT_DIR
,
213 [S_IFCHR
>> S_SHIFT
] = BTRFS_FT_CHRDEV
,
214 [S_IFBLK
>> S_SHIFT
] = BTRFS_FT_BLKDEV
,
215 [S_IFIFO
>> S_SHIFT
] = BTRFS_FT_FIFO
,
216 [S_IFSOCK
>> S_SHIFT
] = BTRFS_FT_SOCK
,
217 [S_IFLNK
>> S_SHIFT
] = BTRFS_FT_SYMLINK
,
220 return btrfs_type_by_mode
[(imode
& S_IFMT
) >> S_SHIFT
];
224 static struct inode_record
*clone_inode_rec(struct inode_record
*orig_rec
)
226 struct inode_record
*rec
;
227 struct inode_backref
*backref
;
228 struct inode_backref
*orig
;
231 rec
= malloc(sizeof(*rec
));
232 memcpy(rec
, orig_rec
, sizeof(*rec
));
234 INIT_LIST_HEAD(&rec
->backrefs
);
236 list_for_each_entry(orig
, &orig_rec
->backrefs
, list
) {
237 size
= sizeof(*orig
) + orig
->namelen
+ 1;
238 backref
= malloc(size
);
239 memcpy(backref
, orig
, size
);
240 list_add_tail(&backref
->list
, &rec
->backrefs
);
245 static struct inode_record
*get_inode_rec(struct cache_tree
*inode_cache
,
248 struct ptr_node
*node
;
249 struct cache_extent
*cache
;
250 struct inode_record
*rec
= NULL
;
253 cache
= find_cache_extent(inode_cache
, ino
, 1);
255 node
= container_of(cache
, struct ptr_node
, cache
);
257 if (mod
&& rec
->refs
> 1) {
258 node
->data
= clone_inode_rec(rec
);
263 rec
= calloc(1, sizeof(*rec
));
265 rec
->extent_start
= (u64
)-1;
266 rec
->first_extent_gap
= (u64
)-1;
268 INIT_LIST_HEAD(&rec
->backrefs
);
270 node
= malloc(sizeof(*node
));
271 node
->cache
.start
= ino
;
272 node
->cache
.size
= 1;
275 ret
= insert_existing_cache_extent(inode_cache
, &node
->cache
);
281 static void free_inode_rec(struct inode_record
*rec
)
283 struct inode_backref
*backref
;
288 while (!list_empty(&rec
->backrefs
)) {
289 backref
= list_entry(rec
->backrefs
.next
,
290 struct inode_backref
, list
);
291 list_del(&backref
->list
);
297 static int can_free_inode_rec(struct inode_record
*rec
)
299 if (!rec
->errors
&& rec
->checked
&& rec
->found_inode_item
&&
300 rec
->nlink
== rec
->found_link
&& list_empty(&rec
->backrefs
))
305 static void maybe_free_inode_rec(struct cache_tree
*inode_cache
,
306 struct inode_record
*rec
)
308 struct cache_extent
*cache
;
309 struct inode_backref
*tmp
, *backref
;
310 struct ptr_node
*node
;
311 unsigned char filetype
;
313 if (!rec
->found_inode_item
)
316 filetype
= imode_to_type(rec
->imode
);
317 list_for_each_entry_safe(backref
, tmp
, &rec
->backrefs
, list
) {
318 if (backref
->found_dir_item
&& backref
->found_dir_index
) {
319 if (backref
->filetype
!= filetype
)
320 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
321 if (!backref
->errors
&& backref
->found_inode_ref
) {
322 list_del(&backref
->list
);
328 if (!rec
->checked
|| rec
->merging
)
331 if (S_ISDIR(rec
->imode
)) {
332 if (rec
->found_size
!= rec
->isize
)
333 rec
->errors
|= I_ERR_DIR_ISIZE_WRONG
;
334 if (rec
->found_file_extent
)
335 rec
->errors
|= I_ERR_ODD_FILE_EXTENT
;
336 } else if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
337 if (rec
->found_dir_item
)
338 rec
->errors
|= I_ERR_ODD_DIR_ITEM
;
339 if (rec
->found_size
!= rec
->nbytes
)
340 rec
->errors
|= I_ERR_FILE_NBYTES_WRONG
;
341 if (rec
->extent_start
== (u64
)-1 || rec
->extent_start
> 0)
342 rec
->first_extent_gap
= 0;
343 if (rec
->nlink
> 0 && (rec
->extent_end
< rec
->isize
||
344 rec
->first_extent_gap
< rec
->isize
))
345 rec
->errors
|= I_ERR_FILE_EXTENT_DISCOUNT
;
348 if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
349 if (rec
->found_csum_item
&& rec
->nodatasum
)
350 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
351 if (rec
->some_csum_missing
&& !rec
->nodatasum
)
352 rec
->errors
|= I_ERR_SOME_CSUM_MISSING
;
355 BUG_ON(rec
->refs
!= 1);
356 if (can_free_inode_rec(rec
)) {
357 cache
= find_cache_extent(inode_cache
, rec
->ino
, 1);
358 node
= container_of(cache
, struct ptr_node
, cache
);
359 BUG_ON(node
->data
!= rec
);
360 remove_cache_extent(inode_cache
, &node
->cache
);
366 static int check_orphan_item(struct btrfs_root
*root
, u64 ino
)
368 struct btrfs_path path
;
369 struct btrfs_key key
;
372 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
373 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
376 btrfs_init_path(&path
);
377 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
378 btrfs_release_path(root
, &path
);
384 static int process_inode_item(struct extent_buffer
*eb
,
385 int slot
, struct btrfs_key
*key
,
386 struct shared_node
*active_node
)
388 struct inode_record
*rec
;
389 struct btrfs_inode_item
*item
;
391 rec
= active_node
->current
;
392 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
393 if (rec
->found_inode_item
) {
394 rec
->errors
|= I_ERR_DUP_INODE_ITEM
;
397 item
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_item
);
398 rec
->nlink
= btrfs_inode_nlink(eb
, item
);
399 rec
->isize
= btrfs_inode_size(eb
, item
);
400 rec
->nbytes
= btrfs_inode_nbytes(eb
, item
);
401 rec
->imode
= btrfs_inode_mode(eb
, item
);
402 if (btrfs_inode_flags(eb
, item
) & BTRFS_INODE_NODATASUM
)
404 rec
->found_inode_item
= 1;
406 rec
->errors
|= I_ERR_NO_ORPHAN_ITEM
;
407 maybe_free_inode_rec(&active_node
->inode_cache
, rec
);
411 static struct inode_backref
*get_inode_backref(struct inode_record
*rec
,
413 int namelen
, u64 dir
)
415 struct inode_backref
*backref
;
417 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
418 if (backref
->dir
!= dir
|| backref
->namelen
!= namelen
)
420 if (memcmp(name
, backref
->name
, namelen
))
425 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
426 memset(backref
, 0, sizeof(*backref
));
428 backref
->namelen
= namelen
;
429 memcpy(backref
->name
, name
, namelen
);
430 backref
->name
[namelen
] = '\0';
431 list_add_tail(&backref
->list
, &rec
->backrefs
);
435 static int add_inode_backref(struct cache_tree
*inode_cache
,
436 u64 ino
, u64 dir
, u64 index
,
437 const char *name
, int namelen
,
438 int filetype
, int itemtype
, int errors
)
440 struct inode_record
*rec
;
441 struct inode_backref
*backref
;
443 rec
= get_inode_rec(inode_cache
, ino
, 1);
444 backref
= get_inode_backref(rec
, name
, namelen
, dir
);
446 backref
->errors
|= errors
;
447 if (itemtype
== BTRFS_DIR_INDEX_KEY
) {
448 if (backref
->found_dir_index
)
449 backref
->errors
|= REF_ERR_DUP_DIR_INDEX
;
450 if (backref
->found_inode_ref
&& backref
->index
!= index
)
451 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
452 if (backref
->found_dir_item
&& backref
->filetype
!= filetype
)
453 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
455 backref
->index
= index
;
456 backref
->filetype
= filetype
;
457 backref
->found_dir_index
= 1;
458 } else if (itemtype
== BTRFS_DIR_ITEM_KEY
) {
460 if (backref
->found_dir_item
)
461 backref
->errors
|= REF_ERR_DUP_DIR_ITEM
;
462 if (backref
->found_dir_index
&& backref
->filetype
!= filetype
)
463 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
465 backref
->filetype
= filetype
;
466 backref
->found_dir_item
= 1;
467 } else if (itemtype
== BTRFS_INODE_REF_KEY
) {
468 if (backref
->found_inode_ref
)
469 backref
->errors
|= REF_ERR_DUP_INODE_REF
;
470 if (backref
->found_dir_index
&& backref
->index
!= index
)
471 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
473 backref
->index
= index
;
474 backref
->found_inode_ref
= 1;
479 maybe_free_inode_rec(inode_cache
, rec
);
483 static int merge_inode_recs(struct inode_record
*src
, struct inode_record
*dst
,
484 struct cache_tree
*dst_cache
)
486 struct inode_backref
*backref
;
490 list_for_each_entry(backref
, &src
->backrefs
, list
) {
491 if (backref
->found_dir_index
) {
492 add_inode_backref(dst_cache
, dst
->ino
, backref
->dir
,
493 backref
->index
, backref
->name
,
494 backref
->namelen
, backref
->filetype
,
495 BTRFS_DIR_INDEX_KEY
, backref
->errors
);
497 if (backref
->found_dir_item
) {
499 add_inode_backref(dst_cache
, dst
->ino
,
500 backref
->dir
, 0, backref
->name
,
501 backref
->namelen
, backref
->filetype
,
502 BTRFS_DIR_ITEM_KEY
, backref
->errors
);
504 if (backref
->found_inode_ref
) {
505 add_inode_backref(dst_cache
, dst
->ino
,
506 backref
->dir
, backref
->index
,
507 backref
->name
, backref
->namelen
, 0,
508 BTRFS_INODE_REF_KEY
, backref
->errors
);
512 if (src
->found_dir_item
)
513 dst
->found_dir_item
= 1;
514 if (src
->found_file_extent
)
515 dst
->found_file_extent
= 1;
516 if (src
->found_csum_item
)
517 dst
->found_csum_item
= 1;
518 if (src
->some_csum_missing
)
519 dst
->some_csum_missing
= 1;
520 if (dst
->first_extent_gap
> src
->first_extent_gap
)
521 dst
->first_extent_gap
= src
->first_extent_gap
;
523 BUG_ON(src
->found_link
< dir_count
);
524 dst
->found_link
+= src
->found_link
- dir_count
;
525 dst
->found_size
+= src
->found_size
;
526 if (src
->extent_start
!= (u64
)-1) {
527 if (dst
->extent_start
== (u64
)-1) {
528 dst
->extent_start
= src
->extent_start
;
529 dst
->extent_end
= src
->extent_end
;
531 if (dst
->extent_end
> src
->extent_start
)
532 dst
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
533 else if (dst
->extent_end
< src
->extent_start
&&
534 dst
->extent_end
< dst
->first_extent_gap
)
535 dst
->first_extent_gap
= dst
->extent_end
;
536 if (dst
->extent_end
< src
->extent_end
)
537 dst
->extent_end
= src
->extent_end
;
541 dst
->errors
|= src
->errors
;
542 if (src
->found_inode_item
) {
543 if (!dst
->found_inode_item
) {
544 dst
->nlink
= src
->nlink
;
545 dst
->isize
= src
->isize
;
546 dst
->nbytes
= src
->nbytes
;
547 dst
->imode
= src
->imode
;
548 dst
->nodatasum
= src
->nodatasum
;
549 dst
->found_inode_item
= 1;
551 dst
->errors
|= I_ERR_DUP_INODE_ITEM
;
559 static int splice_shared_node(struct shared_node
*src_node
,
560 struct shared_node
*dst_node
)
562 struct cache_extent
*cache
;
563 struct ptr_node
*node
, *ins
;
564 struct cache_tree
*src
, *dst
;
565 struct inode_record
*rec
, *conflict
;
570 if (--src_node
->refs
== 0)
572 if (src_node
->current
)
573 current_ino
= src_node
->current
->ino
;
575 src
= &src_node
->root_cache
;
576 dst
= &dst_node
->root_cache
;
578 cache
= find_first_cache_extent(src
, 0);
580 node
= container_of(cache
, struct ptr_node
, cache
);
582 cache
= next_cache_extent(cache
);
585 remove_cache_extent(src
, &node
->cache
);
588 ins
= malloc(sizeof(*ins
));
589 ins
->cache
.start
= node
->cache
.start
;
590 ins
->cache
.size
= node
->cache
.size
;
594 ret
= insert_existing_cache_extent(dst
, &ins
->cache
);
595 if (ret
== -EEXIST
) {
596 conflict
= get_inode_rec(dst
, rec
->ino
, 1);
597 merge_inode_recs(rec
, conflict
, dst
);
599 conflict
->checked
= 1;
600 if (dst_node
->current
== conflict
)
601 dst_node
->current
= NULL
;
603 maybe_free_inode_rec(dst
, conflict
);
611 if (src
== &src_node
->root_cache
) {
612 src
= &src_node
->inode_cache
;
613 dst
= &dst_node
->inode_cache
;
617 if (current_ino
> 0 && (!dst_node
->current
||
618 current_ino
> dst_node
->current
->ino
)) {
619 if (dst_node
->current
) {
620 dst_node
->current
->checked
= 1;
621 maybe_free_inode_rec(dst
, dst_node
->current
);
623 dst_node
->current
= get_inode_rec(dst
, current_ino
, 1);
628 static void free_inode_recs(struct cache_tree
*inode_cache
)
630 struct cache_extent
*cache
;
631 struct ptr_node
*node
;
632 struct inode_record
*rec
;
635 cache
= find_first_cache_extent(inode_cache
, 0);
638 node
= container_of(cache
, struct ptr_node
, cache
);
640 remove_cache_extent(inode_cache
, &node
->cache
);
646 static struct shared_node
*find_shared_node(struct cache_tree
*shared
,
649 struct cache_extent
*cache
;
650 struct shared_node
*node
;
652 cache
= find_cache_extent(shared
, bytenr
, 1);
654 node
= container_of(cache
, struct shared_node
, cache
);
660 static int add_shared_node(struct cache_tree
*shared
, u64 bytenr
, u32 refs
)
663 struct shared_node
*node
;
665 node
= calloc(1, sizeof(*node
));
666 node
->cache
.start
= bytenr
;
667 node
->cache
.size
= 1;
668 cache_tree_init(&node
->root_cache
);
669 cache_tree_init(&node
->inode_cache
);
672 ret
= insert_existing_cache_extent(shared
, &node
->cache
);
677 static int enter_shared_node(struct btrfs_root
*root
, u64 bytenr
, u32 refs
,
678 struct walk_control
*wc
, int level
)
680 struct shared_node
*node
;
681 struct shared_node
*dest
;
683 if (level
== wc
->active_node
)
686 BUG_ON(wc
->active_node
<= level
);
687 node
= find_shared_node(&wc
->shared
, bytenr
);
689 add_shared_node(&wc
->shared
, bytenr
, refs
);
690 node
= find_shared_node(&wc
->shared
, bytenr
);
691 wc
->nodes
[level
] = node
;
692 wc
->active_node
= level
;
696 if (wc
->root_level
== wc
->active_node
&&
697 btrfs_root_refs(&root
->root_item
) == 0) {
698 if (--node
->refs
== 0) {
699 free_inode_recs(&node
->root_cache
);
700 free_inode_recs(&node
->inode_cache
);
701 remove_cache_extent(&wc
->shared
, &node
->cache
);
707 dest
= wc
->nodes
[wc
->active_node
];
708 splice_shared_node(node
, dest
);
709 if (node
->refs
== 0) {
710 remove_cache_extent(&wc
->shared
, &node
->cache
);
716 static int leave_shared_node(struct btrfs_root
*root
,
717 struct walk_control
*wc
, int level
)
719 struct shared_node
*node
;
720 struct shared_node
*dest
;
723 if (level
== wc
->root_level
)
726 for (i
= level
+ 1; i
< BTRFS_MAX_LEVEL
; i
++) {
730 BUG_ON(i
>= BTRFS_MAX_LEVEL
);
732 node
= wc
->nodes
[wc
->active_node
];
733 wc
->nodes
[wc
->active_node
] = NULL
;
736 dest
= wc
->nodes
[wc
->active_node
];
737 if (wc
->active_node
< wc
->root_level
||
738 btrfs_root_refs(&root
->root_item
) > 0) {
739 BUG_ON(node
->refs
<= 1);
740 splice_shared_node(node
, dest
);
742 BUG_ON(node
->refs
< 2);
748 static int process_dir_item(struct extent_buffer
*eb
,
749 int slot
, struct btrfs_key
*key
,
750 struct shared_node
*active_node
)
760 struct btrfs_dir_item
*di
;
761 struct inode_record
*rec
;
762 struct cache_tree
*root_cache
;
763 struct cache_tree
*inode_cache
;
764 struct btrfs_key location
;
765 char namebuf
[BTRFS_NAME_LEN
];
767 root_cache
= &active_node
->root_cache
;
768 inode_cache
= &active_node
->inode_cache
;
769 rec
= active_node
->current
;
770 rec
->found_dir_item
= 1;
772 di
= btrfs_item_ptr(eb
, slot
, struct btrfs_dir_item
);
773 total
= btrfs_item_size_nr(eb
, slot
);
774 while (cur
< total
) {
776 btrfs_dir_item_key_to_cpu(eb
, di
, &location
);
777 name_len
= btrfs_dir_name_len(eb
, di
);
778 data_len
= btrfs_dir_data_len(eb
, di
);
779 filetype
= btrfs_dir_type(eb
, di
);
781 rec
->found_size
+= name_len
;
782 if (name_len
<= BTRFS_NAME_LEN
) {
786 len
= BTRFS_NAME_LEN
;
787 error
= REF_ERR_NAME_TOO_LONG
;
789 read_extent_buffer(eb
, namebuf
, (unsigned long)(di
+ 1), len
);
791 if (location
.type
== BTRFS_INODE_ITEM_KEY
) {
792 add_inode_backref(inode_cache
, location
.objectid
,
793 key
->objectid
, key
->offset
, namebuf
,
794 len
, filetype
, key
->type
, error
);
795 } else if (location
.type
== BTRFS_ROOT_ITEM_KEY
) {
796 add_inode_backref(root_cache
, location
.objectid
,
797 key
->objectid
, key
->offset
, namebuf
,
798 len
, filetype
, key
->type
, error
);
800 fprintf(stderr
, "warning line %d\n", __LINE__
);
803 len
= sizeof(*di
) + name_len
+ data_len
;
804 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
807 if (key
->type
== BTRFS_DIR_INDEX_KEY
&& nritems
> 1)
808 rec
->errors
|= I_ERR_DUP_DIR_INDEX
;
813 static int process_inode_ref(struct extent_buffer
*eb
,
814 int slot
, struct btrfs_key
*key
,
815 struct shared_node
*active_node
)
823 struct cache_tree
*inode_cache
;
824 struct btrfs_inode_ref
*ref
;
825 char namebuf
[BTRFS_NAME_LEN
];
827 inode_cache
= &active_node
->inode_cache
;
829 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
830 total
= btrfs_item_size_nr(eb
, slot
);
831 while (cur
< total
) {
832 name_len
= btrfs_inode_ref_name_len(eb
, ref
);
833 index
= btrfs_inode_ref_index(eb
, ref
);
834 if (name_len
<= BTRFS_NAME_LEN
) {
838 len
= BTRFS_NAME_LEN
;
839 error
= REF_ERR_NAME_TOO_LONG
;
841 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
842 add_inode_backref(inode_cache
, key
->objectid
, key
->offset
,
843 index
, namebuf
, len
, 0, key
->type
, error
);
845 len
= sizeof(*ref
) + name_len
;
846 ref
= (struct btrfs_inode_ref
*)((char *)ref
+ len
);
852 static u64
count_csum_range(struct btrfs_root
*root
, u64 start
, u64 len
)
854 struct btrfs_key key
;
855 struct btrfs_path path
;
856 struct extent_buffer
*leaf
;
861 u16 csum_size
= btrfs_super_csum_size(&root
->fs_info
->super_copy
);
863 btrfs_init_path(&path
);
865 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
867 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
869 ret
= btrfs_search_slot(NULL
, root
->fs_info
->csum_root
,
872 if (ret
> 0 && path
.slots
[0] > 0) {
873 leaf
= path
.nodes
[0];
874 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0] - 1);
875 if (key
.objectid
== BTRFS_EXTENT_CSUM_OBJECTID
&&
876 key
.type
== BTRFS_EXTENT_CSUM_KEY
)
881 leaf
= path
.nodes
[0];
882 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
883 ret
= btrfs_next_leaf(root
->fs_info
->csum_root
, &path
);
887 leaf
= path
.nodes
[0];
890 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
891 if (key
.objectid
!= BTRFS_EXTENT_CSUM_OBJECTID
||
892 key
.type
!= BTRFS_EXTENT_CSUM_KEY
)
895 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
896 if (key
.offset
>= start
+ len
)
899 if (key
.offset
> start
)
902 size
= btrfs_item_size_nr(leaf
, path
.slots
[0]);
903 csum_end
= key
.offset
+ (size
/ csum_size
) * root
->sectorsize
;
904 if (csum_end
> start
) {
905 size
= min(csum_end
- start
, len
);
913 btrfs_release_path(root
->fs_info
->csum_root
, &path
);
917 static int process_file_extent(struct btrfs_root
*root
,
918 struct extent_buffer
*eb
,
919 int slot
, struct btrfs_key
*key
,
920 struct shared_node
*active_node
)
922 struct inode_record
*rec
;
923 struct btrfs_file_extent_item
*fi
;
926 u64 extent_offset
= 0;
927 u64 mask
= root
->sectorsize
- 1;
930 rec
= active_node
->current
;
931 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
932 rec
->found_file_extent
= 1;
934 if (rec
->extent_start
== (u64
)-1) {
935 rec
->extent_start
= key
->offset
;
936 rec
->extent_end
= key
->offset
;
939 if (rec
->extent_end
> key
->offset
)
940 rec
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
941 else if (rec
->extent_end
< key
->offset
&&
942 rec
->extent_end
< rec
->first_extent_gap
)
943 rec
->first_extent_gap
= rec
->extent_end
;
945 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
946 extent_type
= btrfs_file_extent_type(eb
, fi
);
948 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
949 num_bytes
= btrfs_file_extent_inline_len(eb
, fi
);
951 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
952 rec
->found_size
+= num_bytes
;
953 num_bytes
= (num_bytes
+ mask
) & ~mask
;
954 } else if (extent_type
== BTRFS_FILE_EXTENT_REG
||
955 extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
956 num_bytes
= btrfs_file_extent_num_bytes(eb
, fi
);
957 disk_bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
958 extent_offset
= btrfs_file_extent_offset(eb
, fi
);
959 if (num_bytes
== 0 || (num_bytes
& mask
))
960 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
961 if (num_bytes
+ extent_offset
>
962 btrfs_file_extent_ram_bytes(eb
, fi
))
963 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
964 if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
&&
965 (btrfs_file_extent_compression(eb
, fi
) ||
966 btrfs_file_extent_encryption(eb
, fi
) ||
967 btrfs_file_extent_other_encoding(eb
, fi
)))
968 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
970 rec
->found_size
+= num_bytes
;
972 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
974 rec
->extent_end
= key
->offset
+ num_bytes
;
976 if (disk_bytenr
> 0) {
978 if (btrfs_file_extent_compression(eb
, fi
))
979 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
981 disk_bytenr
+= extent_offset
;
983 found
= count_csum_range(root
, disk_bytenr
, num_bytes
);
984 if (extent_type
== BTRFS_FILE_EXTENT_REG
) {
986 rec
->found_csum_item
= 1;
987 if (found
< num_bytes
)
988 rec
->some_csum_missing
= 1;
989 } else if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
991 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
997 static int process_one_leaf(struct btrfs_root
*root
, struct extent_buffer
*eb
,
998 struct walk_control
*wc
)
1000 struct btrfs_key key
;
1004 struct cache_tree
*inode_cache
;
1005 struct shared_node
*active_node
;
1007 if (wc
->root_level
== wc
->active_node
&&
1008 btrfs_root_refs(&root
->root_item
) == 0)
1011 active_node
= wc
->nodes
[wc
->active_node
];
1012 inode_cache
= &active_node
->inode_cache
;
1013 nritems
= btrfs_header_nritems(eb
);
1014 for (i
= 0; i
< nritems
; i
++) {
1015 btrfs_item_key_to_cpu(eb
, &key
, i
);
1016 if (active_node
->current
== NULL
||
1017 active_node
->current
->ino
< key
.objectid
) {
1018 if (active_node
->current
) {
1019 active_node
->current
->checked
= 1;
1020 maybe_free_inode_rec(inode_cache
,
1021 active_node
->current
);
1023 active_node
->current
= get_inode_rec(inode_cache
,
1027 case BTRFS_DIR_ITEM_KEY
:
1028 case BTRFS_DIR_INDEX_KEY
:
1029 ret
= process_dir_item(eb
, i
, &key
, active_node
);
1031 case BTRFS_INODE_REF_KEY
:
1032 ret
= process_inode_ref(eb
, i
, &key
, active_node
);
1034 case BTRFS_INODE_ITEM_KEY
:
1035 ret
= process_inode_item(eb
, i
, &key
, active_node
);
1037 case BTRFS_EXTENT_DATA_KEY
:
1038 ret
= process_file_extent(root
, eb
, i
, &key
,
1048 static void reada_walk_down(struct btrfs_root
*root
,
1049 struct extent_buffer
*node
, int slot
)
1059 level
= btrfs_header_level(node
);
1063 nritems
= btrfs_header_nritems(node
);
1064 blocksize
= btrfs_level_size(root
, level
- 1);
1065 for (i
= slot
; i
< nritems
; i
++) {
1066 bytenr
= btrfs_node_blockptr(node
, i
);
1067 ptr_gen
= btrfs_node_ptr_generation(node
, i
);
1068 ret
= readahead_tree_block(root
, bytenr
, blocksize
, ptr_gen
);
1074 static int walk_down_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1075 struct walk_control
*wc
, int *level
)
1079 struct extent_buffer
*next
;
1080 struct extent_buffer
*cur
;
1085 WARN_ON(*level
< 0);
1086 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1087 ret
= btrfs_lookup_extent_info(NULL
, root
,
1088 path
->nodes
[*level
]->start
,
1089 path
->nodes
[*level
]->len
, &refs
, NULL
);
1094 ret
= enter_shared_node(root
, path
->nodes
[*level
]->start
,
1100 while (*level
>= 0) {
1101 WARN_ON(*level
< 0);
1102 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1103 cur
= path
->nodes
[*level
];
1105 if (btrfs_header_level(cur
) != *level
)
1108 if (path
->slots
[*level
] >= btrfs_header_nritems(cur
))
1111 ret
= process_one_leaf(root
, cur
, wc
);
1114 bytenr
= btrfs_node_blockptr(cur
, path
->slots
[*level
]);
1115 ptr_gen
= btrfs_node_ptr_generation(cur
, path
->slots
[*level
]);
1116 blocksize
= btrfs_level_size(root
, *level
- 1);
1117 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
, blocksize
,
1123 ret
= enter_shared_node(root
, bytenr
, refs
,
1126 path
->slots
[*level
]++;
1131 next
= btrfs_find_tree_block(root
, bytenr
, blocksize
);
1132 if (!next
|| !btrfs_buffer_uptodate(next
, ptr_gen
)) {
1133 free_extent_buffer(next
);
1134 reada_walk_down(root
, cur
, path
->slots
[*level
]);
1135 next
= read_tree_block(root
, bytenr
, blocksize
,
1139 *level
= *level
- 1;
1140 free_extent_buffer(path
->nodes
[*level
]);
1141 path
->nodes
[*level
] = next
;
1142 path
->slots
[*level
] = 0;
1145 path
->slots
[*level
] = btrfs_header_nritems(path
->nodes
[*level
]);
1149 static int walk_up_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1150 struct walk_control
*wc
, int *level
)
1153 struct extent_buffer
*leaf
;
1155 for (i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
1156 leaf
= path
->nodes
[i
];
1157 if (path
->slots
[i
] + 1 < btrfs_header_nritems(leaf
)) {
1162 free_extent_buffer(path
->nodes
[*level
]);
1163 path
->nodes
[*level
] = NULL
;
1164 BUG_ON(*level
> wc
->active_node
);
1165 if (*level
== wc
->active_node
)
1166 leave_shared_node(root
, wc
, *level
);
1173 static int check_root_dir(struct inode_record
*rec
)
1175 struct inode_backref
*backref
;
1178 if (!rec
->found_inode_item
|| rec
->errors
)
1180 if (rec
->nlink
!= 1 || rec
->found_link
!= 0)
1182 if (list_empty(&rec
->backrefs
))
1184 backref
= list_entry(rec
->backrefs
.next
, struct inode_backref
, list
);
1185 if (!backref
->found_inode_ref
)
1187 if (backref
->index
!= 0 || backref
->namelen
!= 2 ||
1188 memcmp(backref
->name
, "..", 2))
1190 if (backref
->found_dir_index
|| backref
->found_dir_item
)
1197 static int check_inode_recs(struct btrfs_root
*root
,
1198 struct cache_tree
*inode_cache
)
1200 struct cache_extent
*cache
;
1201 struct ptr_node
*node
;
1202 struct inode_record
*rec
;
1203 struct inode_backref
*backref
;
1206 u64 root_dirid
= btrfs_root_dirid(&root
->root_item
);
1208 if (btrfs_root_refs(&root
->root_item
) == 0) {
1209 if (!cache_tree_empty(inode_cache
))
1210 fprintf(stderr
, "warning line %d\n", __LINE__
);
1214 rec
= get_inode_rec(inode_cache
, root_dirid
, 0);
1216 ret
= check_root_dir(rec
);
1218 fprintf(stderr
, "root %llu root dir %llu error\n",
1219 (unsigned long long)root
->root_key
.objectid
,
1220 (unsigned long long)root_dirid
);
1224 fprintf(stderr
, "root %llu root dir %llu not found\n",
1225 (unsigned long long)root
->root_key
.objectid
,
1226 (unsigned long long)root_dirid
);
1230 cache
= find_first_cache_extent(inode_cache
, 0);
1233 node
= container_of(cache
, struct ptr_node
, cache
);
1235 remove_cache_extent(inode_cache
, &node
->cache
);
1237 if (rec
->ino
== root_dirid
||
1238 rec
->ino
== BTRFS_ORPHAN_OBJECTID
) {
1239 free_inode_rec(rec
);
1243 if (rec
->errors
& I_ERR_NO_ORPHAN_ITEM
) {
1244 ret
= check_orphan_item(root
, rec
->ino
);
1246 rec
->errors
&= ~I_ERR_NO_ORPHAN_ITEM
;
1247 if (can_free_inode_rec(rec
)) {
1248 free_inode_rec(rec
);
1254 if (!rec
->found_inode_item
)
1255 rec
->errors
|= I_ERR_NO_INODE_ITEM
;
1256 if (rec
->found_link
!= rec
->nlink
)
1257 rec
->errors
|= I_ERR_LINK_COUNT_WRONG
;
1258 fprintf(stderr
, "root %llu inode %llu errors %x\n",
1259 (unsigned long long) root
->root_key
.objectid
,
1260 (unsigned long long) rec
->ino
, rec
->errors
);
1261 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1262 if (!backref
->found_dir_item
)
1263 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1264 if (!backref
->found_dir_index
)
1265 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1266 if (!backref
->found_inode_ref
)
1267 backref
->errors
|= REF_ERR_NO_INODE_REF
;
1268 fprintf(stderr
, "\tunresolved ref dir %llu index %llu"
1269 " namelen %u name %s filetype %d error %x\n",
1270 (unsigned long long)backref
->dir
,
1271 (unsigned long long)backref
->index
,
1272 backref
->namelen
, backref
->name
,
1273 backref
->filetype
, backref
->errors
);
1275 free_inode_rec(rec
);
1277 return (error
> 0) ? -1 : 0;
1280 static struct root_record
*get_root_rec(struct cache_tree
*root_cache
,
1283 struct cache_extent
*cache
;
1284 struct root_record
*rec
= NULL
;
1287 cache
= find_cache_extent(root_cache
, objectid
, 1);
1289 rec
= container_of(cache
, struct root_record
, cache
);
1291 rec
= calloc(1, sizeof(*rec
));
1292 rec
->objectid
= objectid
;
1293 INIT_LIST_HEAD(&rec
->backrefs
);
1294 rec
->cache
.start
= objectid
;
1295 rec
->cache
.size
= 1;
1297 ret
= insert_existing_cache_extent(root_cache
, &rec
->cache
);
1303 static struct root_backref
*get_root_backref(struct root_record
*rec
,
1304 u64 ref_root
, u64 dir
, u64 index
,
1305 const char *name
, int namelen
)
1307 struct root_backref
*backref
;
1309 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1310 if (backref
->ref_root
!= ref_root
|| backref
->dir
!= dir
||
1311 backref
->namelen
!= namelen
)
1313 if (memcmp(name
, backref
->name
, namelen
))
1318 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
1319 memset(backref
, 0, sizeof(*backref
));
1320 backref
->ref_root
= ref_root
;
1322 backref
->index
= index
;
1323 backref
->namelen
= namelen
;
1324 memcpy(backref
->name
, name
, namelen
);
1325 backref
->name
[namelen
] = '\0';
1326 list_add_tail(&backref
->list
, &rec
->backrefs
);
1330 static void free_root_recs(struct cache_tree
*root_cache
)
1332 struct cache_extent
*cache
;
1333 struct root_record
*rec
;
1334 struct root_backref
*backref
;
1337 cache
= find_first_cache_extent(root_cache
, 0);
1340 rec
= container_of(cache
, struct root_record
, cache
);
1341 remove_cache_extent(root_cache
, &rec
->cache
);
1343 while (!list_empty(&rec
->backrefs
)) {
1344 backref
= list_entry(rec
->backrefs
.next
,
1345 struct root_backref
, list
);
1346 list_del(&backref
->list
);
1353 static int add_root_backref(struct cache_tree
*root_cache
,
1354 u64 root_id
, u64 ref_root
, u64 dir
, u64 index
,
1355 const char *name
, int namelen
,
1356 int item_type
, int errors
)
1358 struct root_record
*rec
;
1359 struct root_backref
*backref
;
1361 rec
= get_root_rec(root_cache
, root_id
);
1362 backref
= get_root_backref(rec
, ref_root
, dir
, index
, name
, namelen
);
1364 backref
->errors
|= errors
;
1366 if (item_type
!= BTRFS_DIR_ITEM_KEY
) {
1367 if (backref
->found_dir_index
|| backref
->found_back_ref
||
1368 backref
->found_forward_ref
) {
1369 if (backref
->index
!= index
)
1370 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
1372 backref
->index
= index
;
1376 if (item_type
== BTRFS_DIR_ITEM_KEY
) {
1377 backref
->found_dir_item
= 1;
1378 backref
->reachable
= 1;
1380 } else if (item_type
== BTRFS_DIR_INDEX_KEY
) {
1381 backref
->found_dir_index
= 1;
1382 } else if (item_type
== BTRFS_ROOT_REF_KEY
) {
1383 if (backref
->found_forward_ref
)
1384 backref
->errors
|= REF_ERR_DUP_ROOT_REF
;
1385 backref
->found_forward_ref
= 1;
1386 } else if (item_type
== BTRFS_ROOT_BACKREF_KEY
) {
1387 if (backref
->found_back_ref
)
1388 backref
->errors
|= REF_ERR_DUP_ROOT_BACKREF
;
1389 backref
->found_back_ref
= 1;
1397 static int merge_root_recs(struct btrfs_root
*root
,
1398 struct cache_tree
*src_cache
,
1399 struct cache_tree
*dst_cache
)
1401 struct cache_extent
*cache
;
1402 struct ptr_node
*node
;
1403 struct inode_record
*rec
;
1404 struct inode_backref
*backref
;
1406 if (root
->root_key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
1407 free_inode_recs(src_cache
);
1412 cache
= find_first_cache_extent(src_cache
, 0);
1415 node
= container_of(cache
, struct ptr_node
, cache
);
1417 remove_cache_extent(src_cache
, &node
->cache
);
1420 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1421 BUG_ON(backref
->found_inode_ref
);
1422 if (backref
->found_dir_item
)
1423 add_root_backref(dst_cache
, rec
->ino
,
1424 root
->root_key
.objectid
, backref
->dir
,
1425 backref
->index
, backref
->name
,
1426 backref
->namelen
, BTRFS_DIR_ITEM_KEY
,
1428 if (backref
->found_dir_index
)
1429 add_root_backref(dst_cache
, rec
->ino
,
1430 root
->root_key
.objectid
, backref
->dir
,
1431 backref
->index
, backref
->name
,
1432 backref
->namelen
, BTRFS_DIR_INDEX_KEY
,
1435 free_inode_rec(rec
);
1440 static int check_root_refs(struct btrfs_root
*root
,
1441 struct cache_tree
*root_cache
)
1443 struct root_record
*rec
;
1444 struct root_record
*ref_root
;
1445 struct root_backref
*backref
;
1446 struct cache_extent
*cache
;
1452 rec
= get_root_rec(root_cache
, BTRFS_FS_TREE_OBJECTID
);
1455 /* fixme: this can not detect circular references */
1458 cache
= find_first_cache_extent(root_cache
, 0);
1462 rec
= container_of(cache
, struct root_record
, cache
);
1463 cache
= next_cache_extent(cache
);
1465 if (rec
->found_ref
== 0)
1468 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1469 if (!backref
->reachable
)
1472 ref_root
= get_root_rec(root_cache
,
1474 if (ref_root
->found_ref
> 0)
1477 backref
->reachable
= 0;
1479 if (rec
->found_ref
== 0)
1485 cache
= find_first_cache_extent(root_cache
, 0);
1489 rec
= container_of(cache
, struct root_record
, cache
);
1490 cache
= next_cache_extent(cache
);
1492 if (rec
->found_ref
== 0 &&
1493 rec
->objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
1494 rec
->objectid
<= BTRFS_LAST_FREE_OBJECTID
) {
1495 ret
= check_orphan_item(root
->fs_info
->tree_root
,
1500 fprintf(stderr
, "fs tree %llu not referenced\n",
1501 (unsigned long long)rec
->objectid
);
1505 if (rec
->found_ref
> 0 && !rec
->found_root_item
)
1507 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1508 if (!backref
->found_dir_item
)
1509 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1510 if (!backref
->found_dir_index
)
1511 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1512 if (!backref
->found_back_ref
)
1513 backref
->errors
|= REF_ERR_NO_ROOT_BACKREF
;
1514 if (!backref
->found_forward_ref
)
1515 backref
->errors
|= REF_ERR_NO_ROOT_REF
;
1516 if (backref
->reachable
&& backref
->errors
)
1523 fprintf(stderr
, "fs tree %llu refs %u %s\n",
1524 (unsigned long long)rec
->objectid
, rec
->found_ref
,
1525 rec
->found_root_item
? "" : "not found");
1527 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1528 if (!backref
->reachable
)
1530 if (!backref
->errors
&& rec
->found_root_item
)
1532 fprintf(stderr
, "\tunresolved ref root %llu dir %llu"
1533 " index %llu namelen %u name %s error %x\n",
1534 (unsigned long long)backref
->ref_root
,
1535 (unsigned long long)backref
->dir
,
1536 (unsigned long long)backref
->index
,
1537 backref
->namelen
, backref
->name
,
1541 return errors
> 0 ? 1 : 0;
1544 static int process_root_ref(struct extent_buffer
*eb
, int slot
,
1545 struct btrfs_key
*key
,
1546 struct cache_tree
*root_cache
)
1552 struct btrfs_root_ref
*ref
;
1553 char namebuf
[BTRFS_NAME_LEN
];
1556 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_root_ref
);
1558 dirid
= btrfs_root_ref_dirid(eb
, ref
);
1559 index
= btrfs_root_ref_sequence(eb
, ref
);
1560 name_len
= btrfs_root_ref_name_len(eb
, ref
);
1562 if (name_len
<= BTRFS_NAME_LEN
) {
1566 len
= BTRFS_NAME_LEN
;
1567 error
= REF_ERR_NAME_TOO_LONG
;
1569 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
1571 if (key
->type
== BTRFS_ROOT_REF_KEY
) {
1572 add_root_backref(root_cache
, key
->offset
, key
->objectid
, dirid
,
1573 index
, namebuf
, len
, key
->type
, error
);
1575 add_root_backref(root_cache
, key
->objectid
, key
->offset
, dirid
,
1576 index
, namebuf
, len
, key
->type
, error
);
1581 static int check_fs_root(struct btrfs_root
*root
,
1582 struct cache_tree
*root_cache
,
1583 struct walk_control
*wc
)
1588 struct btrfs_path path
;
1589 struct shared_node root_node
;
1590 struct root_record
*rec
;
1591 struct btrfs_root_item
*root_item
= &root
->root_item
;
1593 if (root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
1594 rec
= get_root_rec(root_cache
, root
->root_key
.objectid
);
1595 if (btrfs_root_refs(root_item
) > 0)
1596 rec
->found_root_item
= 1;
1599 btrfs_init_path(&path
);
1600 memset(&root_node
, 0, sizeof(root_node
));
1601 cache_tree_init(&root_node
.root_cache
);
1602 cache_tree_init(&root_node
.inode_cache
);
1604 level
= btrfs_header_level(root
->node
);
1605 memset(wc
->nodes
, 0, sizeof(wc
->nodes
));
1606 wc
->nodes
[level
] = &root_node
;
1607 wc
->active_node
= level
;
1608 wc
->root_level
= level
;
1610 if (btrfs_root_refs(root_item
) > 0 ||
1611 btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
1612 path
.nodes
[level
] = root
->node
;
1613 extent_buffer_get(root
->node
);
1614 path
.slots
[level
] = 0;
1616 struct btrfs_key key
;
1617 struct btrfs_disk_key found_key
;
1619 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
1620 level
= root_item
->drop_level
;
1621 path
.lowest_level
= level
;
1622 wret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
1624 btrfs_node_key(path
.nodes
[level
], &found_key
,
1626 WARN_ON(memcmp(&found_key
, &root_item
->drop_progress
,
1627 sizeof(found_key
)));
1631 wret
= walk_down_tree(root
, &path
, wc
, &level
);
1637 wret
= walk_up_tree(root
, &path
, wc
, &level
);
1643 btrfs_release_path(root
, &path
);
1645 merge_root_recs(root
, &root_node
.root_cache
, root_cache
);
1647 if (root_node
.current
) {
1648 root_node
.current
->checked
= 1;
1649 maybe_free_inode_rec(&root_node
.inode_cache
,
1653 ret
= check_inode_recs(root
, &root_node
.inode_cache
);
1657 static int fs_root_objectid(u64 objectid
)
1659 if (objectid
== BTRFS_FS_TREE_OBJECTID
||
1660 objectid
== BTRFS_TREE_RELOC_OBJECTID
||
1661 objectid
== BTRFS_DATA_RELOC_TREE_OBJECTID
||
1662 (objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
1663 objectid
<= BTRFS_LAST_FREE_OBJECTID
))
1668 static int check_fs_roots(struct btrfs_root
*root
,
1669 struct cache_tree
*root_cache
)
1671 struct btrfs_path path
;
1672 struct btrfs_key key
;
1673 struct walk_control wc
;
1674 struct extent_buffer
*leaf
;
1675 struct btrfs_root
*tmp_root
;
1676 struct btrfs_root
*tree_root
= root
->fs_info
->tree_root
;
1680 memset(&wc
, 0, sizeof(wc
));
1681 cache_tree_init(&wc
.shared
);
1682 btrfs_init_path(&path
);
1686 key
.type
= BTRFS_ROOT_ITEM_KEY
;
1687 ret
= btrfs_search_slot(NULL
, tree_root
, &key
, &path
, 0, 0);
1690 leaf
= path
.nodes
[0];
1691 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
1692 ret
= btrfs_next_leaf(tree_root
, &path
);
1695 leaf
= path
.nodes
[0];
1697 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
1698 if (key
.type
== BTRFS_ROOT_ITEM_KEY
&&
1699 fs_root_objectid(key
.objectid
)) {
1700 tmp_root
= btrfs_read_fs_root_no_cache(root
->fs_info
,
1702 ret
= check_fs_root(tmp_root
, root_cache
, &wc
);
1705 btrfs_free_fs_root(root
->fs_info
, tmp_root
);
1706 } else if (key
.type
== BTRFS_ROOT_REF_KEY
||
1707 key
.type
== BTRFS_ROOT_BACKREF_KEY
) {
1708 process_root_ref(leaf
, path
.slots
[0], &key
,
1713 btrfs_release_path(tree_root
, &path
);
1715 if (!cache_tree_empty(&wc
.shared
))
1716 fprintf(stderr
, "warning line %d\n", __LINE__
);
1721 static int check_node(struct btrfs_root
*root
,
1722 struct btrfs_disk_key
*parent_key
,
1723 struct extent_buffer
*buf
)
1726 struct btrfs_key cpukey
;
1727 struct btrfs_disk_key key
;
1728 u32 nritems
= btrfs_header_nritems(buf
);
1730 if (nritems
== 0 || nritems
> BTRFS_NODEPTRS_PER_BLOCK(root
))
1732 if (parent_key
->type
) {
1733 btrfs_node_key(buf
, &key
, 0);
1734 if (memcmp(parent_key
, &key
, sizeof(key
)))
1737 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
1738 btrfs_node_key(buf
, &key
, i
);
1739 btrfs_node_key_to_cpu(buf
, &cpukey
, i
+ 1);
1740 if (btrfs_comp_keys(&key
, &cpukey
) >= 0)
1746 static int check_leaf(struct btrfs_root
*root
,
1747 struct btrfs_disk_key
*parent_key
,
1748 struct extent_buffer
*buf
)
1751 struct btrfs_key cpukey
;
1752 struct btrfs_disk_key key
;
1753 u32 nritems
= btrfs_header_nritems(buf
);
1755 if (btrfs_header_level(buf
) != 0) {
1756 fprintf(stderr
, "leaf is not a leaf %llu\n",
1757 (unsigned long long)btrfs_header_bytenr(buf
));
1760 if (btrfs_leaf_free_space(root
, buf
) < 0) {
1761 fprintf(stderr
, "leaf free space incorrect %llu %d\n",
1762 (unsigned long long)btrfs_header_bytenr(buf
),
1763 btrfs_leaf_free_space(root
, buf
));
1770 btrfs_item_key(buf
, &key
, 0);
1771 if (parent_key
->type
&& memcmp(parent_key
, &key
, sizeof(key
))) {
1772 fprintf(stderr
, "leaf parent key incorrect %llu\n",
1773 (unsigned long long)btrfs_header_bytenr(buf
));
1776 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
1777 btrfs_item_key(buf
, &key
, i
);
1778 btrfs_item_key_to_cpu(buf
, &cpukey
, i
+ 1);
1779 if (btrfs_comp_keys(&key
, &cpukey
) >= 0) {
1780 fprintf(stderr
, "bad key ordering %d %d\n", i
, i
+1);
1783 if (btrfs_item_offset_nr(buf
, i
) !=
1784 btrfs_item_end_nr(buf
, i
+ 1)) {
1785 fprintf(stderr
, "incorrect offsets %u %u\n",
1786 btrfs_item_offset_nr(buf
, i
),
1787 btrfs_item_end_nr(buf
, i
+ 1));
1790 if (i
== 0 && btrfs_item_end_nr(buf
, i
) !=
1791 BTRFS_LEAF_DATA_SIZE(root
)) {
1792 fprintf(stderr
, "bad item end %u wanted %u\n",
1793 btrfs_item_end_nr(buf
, i
),
1794 (unsigned)BTRFS_LEAF_DATA_SIZE(root
));
1801 static int all_backpointers_checked(struct extent_record
*rec
, int print_errs
)
1803 struct list_head
*cur
= rec
->backrefs
.next
;
1804 struct extent_backref
*back
;
1805 struct tree_backref
*tback
;
1806 struct data_backref
*dback
;
1810 while(cur
!= &rec
->backrefs
) {
1811 back
= list_entry(cur
, struct extent_backref
, list
);
1813 if (!back
->found_extent_tree
) {
1817 if (back
->is_data
) {
1818 dback
= (struct data_backref
*)back
;
1819 fprintf(stderr
, "Backref %llu %s %llu"
1820 " owner %llu offset %llu num_refs %lu"
1821 " not found in extent tree\n",
1822 (unsigned long long)rec
->start
,
1823 back
->full_backref
?
1825 back
->full_backref
?
1826 (unsigned long long)dback
->parent
:
1827 (unsigned long long)dback
->root
,
1828 (unsigned long long)dback
->owner
,
1829 (unsigned long long)dback
->offset
,
1830 (unsigned long)dback
->num_refs
);
1832 tback
= (struct tree_backref
*)back
;
1833 fprintf(stderr
, "Backref %llu parent %llu"
1834 " root %llu not found in extent tree\n",
1835 (unsigned long long)rec
->start
,
1836 (unsigned long long)tback
->parent
,
1837 (unsigned long long)tback
->root
);
1840 if (!back
->is_data
&& !back
->found_ref
) {
1844 tback
= (struct tree_backref
*)back
;
1845 fprintf(stderr
, "Backref %llu %s %llu not referenced back %p\n",
1846 (unsigned long long)rec
->start
,
1847 back
->full_backref
? "parent" : "root",
1848 back
->full_backref
?
1849 (unsigned long long)tback
->parent
:
1850 (unsigned long long)tback
->root
, back
);
1852 if (back
->is_data
) {
1853 dback
= (struct data_backref
*)back
;
1854 if (dback
->found_ref
!= dback
->num_refs
) {
1858 fprintf(stderr
, "Incorrect local backref count"
1859 " on %llu %s %llu owner %llu"
1860 " offset %llu found %u wanted %u back %p\n",
1861 (unsigned long long)rec
->start
,
1862 back
->full_backref
?
1864 back
->full_backref
?
1865 (unsigned long long)dback
->parent
:
1866 (unsigned long long)dback
->root
,
1867 (unsigned long long)dback
->owner
,
1868 (unsigned long long)dback
->offset
,
1869 dback
->found_ref
, dback
->num_refs
, back
);
1872 if (!back
->is_data
) {
1875 dback
= (struct data_backref
*)back
;
1876 found
+= dback
->found_ref
;
1879 if (found
!= rec
->refs
) {
1883 fprintf(stderr
, "Incorrect global backref count "
1884 "on %llu found %llu wanted %llu\n",
1885 (unsigned long long)rec
->start
,
1886 (unsigned long long)found
,
1887 (unsigned long long)rec
->refs
);
1893 static int free_all_extent_backrefs(struct extent_record
*rec
)
1895 struct extent_backref
*back
;
1896 struct list_head
*cur
;
1897 while (!list_empty(&rec
->backrefs
)) {
1898 cur
= rec
->backrefs
.next
;
1899 back
= list_entry(cur
, struct extent_backref
, list
);
1906 static int maybe_free_extent_rec(struct cache_tree
*extent_cache
,
1907 struct extent_record
*rec
)
1909 if (rec
->content_checked
&& rec
->owner_ref_checked
&&
1910 rec
->extent_item_refs
== rec
->refs
&& rec
->refs
> 0 &&
1911 !all_backpointers_checked(rec
, 0)) {
1912 remove_cache_extent(extent_cache
, &rec
->cache
);
1913 free_all_extent_backrefs(rec
);
1919 static int check_owner_ref(struct btrfs_root
*root
,
1920 struct extent_record
*rec
,
1921 struct extent_buffer
*buf
)
1923 struct extent_backref
*node
;
1924 struct tree_backref
*back
;
1925 struct btrfs_root
*ref_root
;
1926 struct btrfs_key key
;
1927 struct btrfs_path path
;
1931 list_for_each_entry(node
, &rec
->backrefs
, list
) {
1934 if (!node
->found_ref
)
1936 if (node
->full_backref
)
1938 back
= (struct tree_backref
*)node
;
1939 if (btrfs_header_owner(buf
) == back
->root
)
1942 BUG_ON(rec
->is_root
);
1944 /* try to find the block by search corresponding fs tree */
1945 key
.objectid
= btrfs_header_owner(buf
);
1946 key
.type
= BTRFS_ROOT_ITEM_KEY
;
1947 key
.offset
= (u64
)-1;
1949 ref_root
= btrfs_read_fs_root(root
->fs_info
, &key
);
1950 BUG_ON(IS_ERR(ref_root
));
1952 level
= btrfs_header_level(buf
);
1954 btrfs_item_key_to_cpu(buf
, &key
, 0);
1956 btrfs_node_key_to_cpu(buf
, &key
, 0);
1958 btrfs_init_path(&path
);
1959 path
.lowest_level
= level
+ 1;
1960 btrfs_search_slot(NULL
, ref_root
, &key
, &path
, 0, 0);
1962 if (buf
->start
== btrfs_node_blockptr(path
.nodes
[level
+ 1],
1963 path
.slots
[level
+ 1]))
1964 rec
->owner_ref_checked
= 1;
1966 btrfs_release_path(ref_root
, &path
);
1967 return found
? 0 : 1;
1970 static int check_block(struct btrfs_root
*root
,
1971 struct cache_tree
*extent_cache
,
1972 struct extent_buffer
*buf
, u64 flags
)
1974 struct extent_record
*rec
;
1975 struct cache_extent
*cache
;
1976 struct btrfs_key key
;
1980 cache
= find_cache_extent(extent_cache
, buf
->start
, buf
->len
);
1983 rec
= container_of(cache
, struct extent_record
, cache
);
1984 rec
->generation
= btrfs_header_generation(buf
);
1986 level
= btrfs_header_level(buf
);
1987 if (btrfs_header_nritems(buf
) > 0) {
1990 btrfs_item_key_to_cpu(buf
, &key
, 0);
1992 btrfs_node_key_to_cpu(buf
, &key
, 0);
1994 rec
->info_objectid
= key
.objectid
;
1996 rec
->info_level
= level
;
1998 if (btrfs_is_leaf(buf
)) {
1999 ret
= check_leaf(root
, &rec
->parent_key
, buf
);
2001 ret
= check_node(root
, &rec
->parent_key
, buf
);
2004 fprintf(stderr
, "bad block %llu\n",
2005 (unsigned long long)buf
->start
);
2007 rec
->content_checked
= 1;
2008 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
)
2009 rec
->owner_ref_checked
= 1;
2011 ret
= check_owner_ref(root
, rec
, buf
);
2013 rec
->owner_ref_checked
= 1;
2017 maybe_free_extent_rec(extent_cache
, rec
);
2021 static struct tree_backref
*find_tree_backref(struct extent_record
*rec
,
2022 u64 parent
, u64 root
)
2024 struct list_head
*cur
= rec
->backrefs
.next
;
2025 struct extent_backref
*node
;
2026 struct tree_backref
*back
;
2028 while(cur
!= &rec
->backrefs
) {
2029 node
= list_entry(cur
, struct extent_backref
, list
);
2033 back
= (struct tree_backref
*)node
;
2035 if (!node
->full_backref
)
2037 if (parent
== back
->parent
)
2040 if (node
->full_backref
)
2042 if (back
->root
== root
)
2049 static struct tree_backref
*alloc_tree_backref(struct extent_record
*rec
,
2050 u64 parent
, u64 root
)
2052 struct tree_backref
*ref
= malloc(sizeof(*ref
));
2053 memset(&ref
->node
, 0, sizeof(ref
->node
));
2055 ref
->parent
= parent
;
2056 ref
->node
.full_backref
= 1;
2059 ref
->node
.full_backref
= 0;
2061 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
2066 static struct data_backref
*find_data_backref(struct extent_record
*rec
,
2067 u64 parent
, u64 root
,
2068 u64 owner
, u64 offset
)
2070 struct list_head
*cur
= rec
->backrefs
.next
;
2071 struct extent_backref
*node
;
2072 struct data_backref
*back
;
2074 while(cur
!= &rec
->backrefs
) {
2075 node
= list_entry(cur
, struct extent_backref
, list
);
2079 back
= (struct data_backref
*)node
;
2081 if (!node
->full_backref
)
2083 if (parent
== back
->parent
)
2086 if (node
->full_backref
)
2088 if (back
->root
== root
&& back
->owner
== owner
&&
2089 back
->offset
== offset
)
2096 static struct data_backref
*alloc_data_backref(struct extent_record
*rec
,
2097 u64 parent
, u64 root
,
2098 u64 owner
, u64 offset
,
2101 struct data_backref
*ref
= malloc(sizeof(*ref
));
2102 memset(&ref
->node
, 0, sizeof(ref
->node
));
2103 ref
->node
.is_data
= 1;
2106 ref
->parent
= parent
;
2109 ref
->node
.full_backref
= 1;
2113 ref
->offset
= offset
;
2114 ref
->node
.full_backref
= 0;
2118 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
2119 if (max_size
> rec
->max_size
)
2120 rec
->max_size
= max_size
;
2124 static int add_extent_rec(struct cache_tree
*extent_cache
,
2125 struct btrfs_key
*parent_key
,
2126 u64 start
, u64 nr
, u64 extent_item_refs
,
2127 int is_root
, int inc_ref
, int set_checked
,
2130 struct extent_record
*rec
;
2131 struct cache_extent
*cache
;
2134 cache
= find_cache_extent(extent_cache
, start
, nr
);
2136 rec
= container_of(cache
, struct extent_record
, cache
);
2142 if (start
!= rec
->start
) {
2143 fprintf(stderr
, "warning, start mismatch %llu %llu\n",
2144 (unsigned long long)rec
->start
,
2145 (unsigned long long)start
);
2148 if (extent_item_refs
) {
2149 if (rec
->extent_item_refs
) {
2150 fprintf(stderr
, "block %llu rec "
2151 "extent_item_refs %llu, passed %llu\n",
2152 (unsigned long long)start
,
2153 (unsigned long long)
2154 rec
->extent_item_refs
,
2155 (unsigned long long)extent_item_refs
);
2157 rec
->extent_item_refs
= extent_item_refs
;
2162 rec
->content_checked
= 1;
2163 rec
->owner_ref_checked
= 1;
2167 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
2169 if (rec
->max_size
< max_size
)
2170 rec
->max_size
= max_size
;
2172 maybe_free_extent_rec(extent_cache
, rec
);
2175 rec
= malloc(sizeof(*rec
));
2177 rec
->max_size
= max_size
;
2179 rec
->content_checked
= 0;
2180 rec
->owner_ref_checked
= 0;
2181 INIT_LIST_HEAD(&rec
->backrefs
);
2193 if (extent_item_refs
)
2194 rec
->extent_item_refs
= extent_item_refs
;
2196 rec
->extent_item_refs
= 0;
2199 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
2201 memset(&rec
->parent_key
, 0, sizeof(*parent_key
));
2203 rec
->cache
.start
= start
;
2204 rec
->cache
.size
= nr
;
2205 ret
= insert_existing_cache_extent(extent_cache
, &rec
->cache
);
2209 rec
->content_checked
= 1;
2210 rec
->owner_ref_checked
= 1;
2215 static int add_tree_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
2216 u64 parent
, u64 root
, int found_ref
)
2218 struct extent_record
*rec
;
2219 struct tree_backref
*back
;
2220 struct cache_extent
*cache
;
2222 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2224 add_extent_rec(extent_cache
, NULL
, bytenr
, 1, 0, 0, 0, 0, 0);
2225 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2230 rec
= container_of(cache
, struct extent_record
, cache
);
2231 if (rec
->start
!= bytenr
) {
2235 back
= find_tree_backref(rec
, parent
, root
);
2237 back
= alloc_tree_backref(rec
, parent
, root
);
2240 if (back
->node
.found_ref
) {
2241 fprintf(stderr
, "Extent back ref already exists "
2242 "for %llu parent %llu root %llu \n",
2243 (unsigned long long)bytenr
,
2244 (unsigned long long)parent
,
2245 (unsigned long long)root
);
2247 back
->node
.found_ref
= 1;
2249 if (back
->node
.found_extent_tree
) {
2250 fprintf(stderr
, "Extent back ref already exists "
2251 "for %llu parent %llu root %llu \n",
2252 (unsigned long long)bytenr
,
2253 (unsigned long long)parent
,
2254 (unsigned long long)root
);
2256 back
->node
.found_extent_tree
= 1;
2261 static int add_data_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
2262 u64 parent
, u64 root
, u64 owner
, u64 offset
,
2263 u32 num_refs
, int found_ref
, u64 max_size
)
2265 struct extent_record
*rec
;
2266 struct data_backref
*back
;
2267 struct cache_extent
*cache
;
2269 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2271 add_extent_rec(extent_cache
, NULL
, bytenr
, 1, 0, 0, 0, 0,
2273 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
2278 rec
= container_of(cache
, struct extent_record
, cache
);
2279 if (rec
->start
!= bytenr
) {
2282 if (rec
->max_size
< max_size
)
2283 rec
->max_size
= max_size
;
2285 back
= find_data_backref(rec
, parent
, root
, owner
, offset
);
2287 back
= alloc_data_backref(rec
, parent
, root
, owner
, offset
,
2291 BUG_ON(num_refs
!= 1);
2292 back
->node
.found_ref
= 1;
2293 back
->found_ref
+= 1;
2295 if (back
->node
.found_extent_tree
) {
2296 fprintf(stderr
, "Extent back ref already exists "
2297 "for %llu parent %llu root %llu"
2298 "owner %llu offset %llu num_refs %lu\n",
2299 (unsigned long long)bytenr
,
2300 (unsigned long long)parent
,
2301 (unsigned long long)root
,
2302 (unsigned long long)owner
,
2303 (unsigned long long)offset
,
2304 (unsigned long)num_refs
);
2306 back
->num_refs
= num_refs
;
2307 back
->node
.found_extent_tree
= 1;
2312 static int add_pending(struct cache_tree
*pending
,
2313 struct cache_tree
*seen
, u64 bytenr
, u32 size
)
2316 ret
= insert_cache_extent(seen
, bytenr
, size
);
2319 insert_cache_extent(pending
, bytenr
, size
);
2323 static int pick_next_pending(struct cache_tree
*pending
,
2324 struct cache_tree
*reada
,
2325 struct cache_tree
*nodes
,
2326 u64 last
, struct block_info
*bits
, int bits_nr
,
2329 unsigned long node_start
= last
;
2330 struct cache_extent
*cache
;
2333 cache
= find_first_cache_extent(reada
, 0);
2335 bits
[0].start
= cache
->start
;
2336 bits
[1].size
= cache
->size
;
2341 if (node_start
> 32768)
2342 node_start
-= 32768;
2344 cache
= find_first_cache_extent(nodes
, node_start
);
2346 cache
= find_first_cache_extent(nodes
, 0);
2349 cache
= find_first_cache_extent(pending
, 0);
2354 bits
[ret
].start
= cache
->start
;
2355 bits
[ret
].size
= cache
->size
;
2356 cache
= next_cache_extent(cache
);
2358 } while (cache
&& ret
< bits_nr
);
2364 bits
[ret
].start
= cache
->start
;
2365 bits
[ret
].size
= cache
->size
;
2366 cache
= next_cache_extent(cache
);
2368 } while (cache
&& ret
< bits_nr
);
2370 if (bits_nr
- ret
> 8) {
2371 u64 lookup
= bits
[0].start
+ bits
[0].size
;
2372 struct cache_extent
*next
;
2373 next
= find_first_cache_extent(pending
, lookup
);
2375 if (next
->start
- lookup
> 32768)
2377 bits
[ret
].start
= next
->start
;
2378 bits
[ret
].size
= next
->size
;
2379 lookup
= next
->start
+ next
->size
;
2383 next
= next_cache_extent(next
);
2391 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2392 static int process_extent_ref_v0(struct cache_tree
*extent_cache
,
2393 struct extent_buffer
*leaf
, int slot
)
2395 struct btrfs_extent_ref_v0
*ref0
;
2396 struct btrfs_key key
;
2398 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
2399 ref0
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_ref_v0
);
2400 if (btrfs_ref_objectid_v0(leaf
, ref0
) < BTRFS_FIRST_FREE_OBJECTID
) {
2401 add_tree_backref(extent_cache
, key
.objectid
, key
.offset
, 0, 0);
2403 add_data_backref(extent_cache
, key
.objectid
, key
.offset
, 0,
2404 0, 0, btrfs_ref_count_v0(leaf
, ref0
), 0, 0);
2410 static int process_extent_item(struct cache_tree
*extent_cache
,
2411 struct extent_buffer
*eb
, int slot
)
2413 struct btrfs_extent_item
*ei
;
2414 struct btrfs_extent_inline_ref
*iref
;
2415 struct btrfs_extent_data_ref
*dref
;
2416 struct btrfs_shared_data_ref
*sref
;
2417 struct btrfs_key key
;
2421 u32 item_size
= btrfs_item_size_nr(eb
, slot
);
2425 btrfs_item_key_to_cpu(eb
, &key
, slot
);
2427 if (item_size
< sizeof(*ei
)) {
2428 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2429 struct btrfs_extent_item_v0
*ei0
;
2430 BUG_ON(item_size
!= sizeof(*ei0
));
2431 ei0
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item_v0
);
2432 refs
= btrfs_extent_refs_v0(eb
, ei0
);
2436 return add_extent_rec(extent_cache
, NULL
, key
.objectid
,
2437 key
.offset
, refs
, 0, 0, 0, key
.offset
);
2440 ei
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item
);
2441 refs
= btrfs_extent_refs(eb
, ei
);
2443 add_extent_rec(extent_cache
, NULL
, key
.objectid
, key
.offset
,
2444 refs
, 0, 0, 0, key
.offset
);
2446 ptr
= (unsigned long)(ei
+ 1);
2447 if (btrfs_extent_flags(eb
, ei
) & BTRFS_EXTENT_FLAG_TREE_BLOCK
)
2448 ptr
+= sizeof(struct btrfs_tree_block_info
);
2450 end
= (unsigned long)ei
+ item_size
;
2452 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
2453 type
= btrfs_extent_inline_ref_type(eb
, iref
);
2454 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
2456 case BTRFS_TREE_BLOCK_REF_KEY
:
2457 add_tree_backref(extent_cache
, key
.objectid
,
2460 case BTRFS_SHARED_BLOCK_REF_KEY
:
2461 add_tree_backref(extent_cache
, key
.objectid
,
2464 case BTRFS_EXTENT_DATA_REF_KEY
:
2465 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
2466 add_data_backref(extent_cache
, key
.objectid
, 0,
2467 btrfs_extent_data_ref_root(eb
, dref
),
2468 btrfs_extent_data_ref_objectid(eb
,
2470 btrfs_extent_data_ref_offset(eb
, dref
),
2471 btrfs_extent_data_ref_count(eb
, dref
),
2474 case BTRFS_SHARED_DATA_REF_KEY
:
2475 sref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
2476 add_data_backref(extent_cache
, key
.objectid
, offset
,
2478 btrfs_shared_data_ref_count(eb
, sref
),
2482 fprintf(stderr
, "corrupt extent record: key %Lu %u %Lu\n",
2483 key
.objectid
, key
.type
, key
.offset
);
2486 ptr
+= btrfs_extent_inline_ref_size(type
);
2493 static int run_next_block(struct btrfs_root
*root
,
2494 struct block_info
*bits
,
2497 struct cache_tree
*pending
,
2498 struct cache_tree
*seen
,
2499 struct cache_tree
*reada
,
2500 struct cache_tree
*nodes
,
2501 struct cache_tree
*extent_cache
)
2503 struct extent_buffer
*buf
;
2512 struct btrfs_key key
;
2513 struct cache_extent
*cache
;
2516 ret
= pick_next_pending(pending
, reada
, nodes
, *last
, bits
,
2517 bits_nr
, &reada_bits
);
2522 for(i
= 0; i
< ret
; i
++) {
2523 insert_cache_extent(reada
, bits
[i
].start
,
2526 /* fixme, get the parent transid */
2527 readahead_tree_block(root
, bits
[i
].start
,
2531 *last
= bits
[0].start
;
2532 bytenr
= bits
[0].start
;
2533 size
= bits
[0].size
;
2535 cache
= find_cache_extent(pending
, bytenr
, size
);
2537 remove_cache_extent(pending
, cache
);
2540 cache
= find_cache_extent(reada
, bytenr
, size
);
2542 remove_cache_extent(reada
, cache
);
2545 cache
= find_cache_extent(nodes
, bytenr
, size
);
2547 remove_cache_extent(nodes
, cache
);
2551 /* fixme, get the real parent transid */
2552 buf
= read_tree_block(root
, bytenr
, size
, 0);
2553 nritems
= btrfs_header_nritems(buf
);
2555 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
, size
, NULL
, &flags
);
2557 flags
= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
2559 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
) {
2564 owner
= btrfs_header_owner(buf
);
2567 ret
= check_block(root
, extent_cache
, buf
, flags
);
2569 if (btrfs_is_leaf(buf
)) {
2570 btree_space_waste
+= btrfs_leaf_free_space(root
, buf
);
2571 for (i
= 0; i
< nritems
; i
++) {
2572 struct btrfs_file_extent_item
*fi
;
2573 btrfs_item_key_to_cpu(buf
, &key
, i
);
2574 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
2575 process_extent_item(extent_cache
, buf
, i
);
2578 if (key
.type
== BTRFS_EXTENT_CSUM_KEY
) {
2580 btrfs_item_size_nr(buf
, i
);
2583 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
2586 if (key
.type
== BTRFS_EXTENT_REF_V0_KEY
) {
2587 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2588 process_extent_ref_v0(extent_cache
, buf
, i
);
2595 if (key
.type
== BTRFS_TREE_BLOCK_REF_KEY
) {
2596 add_tree_backref(extent_cache
, key
.objectid
, 0,
2600 if (key
.type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
2601 add_tree_backref(extent_cache
, key
.objectid
,
2605 if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
) {
2606 struct btrfs_extent_data_ref
*ref
;
2607 ref
= btrfs_item_ptr(buf
, i
,
2608 struct btrfs_extent_data_ref
);
2609 add_data_backref(extent_cache
,
2611 btrfs_extent_data_ref_root(buf
, ref
),
2612 btrfs_extent_data_ref_objectid(buf
,
2614 btrfs_extent_data_ref_offset(buf
, ref
),
2615 btrfs_extent_data_ref_count(buf
, ref
),
2616 0, root
->sectorsize
);
2619 if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
) {
2620 struct btrfs_shared_data_ref
*ref
;
2621 ref
= btrfs_item_ptr(buf
, i
,
2622 struct btrfs_shared_data_ref
);
2623 add_data_backref(extent_cache
,
2624 key
.objectid
, key
.offset
, 0, 0, 0,
2625 btrfs_shared_data_ref_count(buf
, ref
),
2626 0, root
->sectorsize
);
2629 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
2631 fi
= btrfs_item_ptr(buf
, i
,
2632 struct btrfs_file_extent_item
);
2633 if (btrfs_file_extent_type(buf
, fi
) ==
2634 BTRFS_FILE_EXTENT_INLINE
)
2636 if (btrfs_file_extent_disk_bytenr(buf
, fi
) == 0)
2639 data_bytes_allocated
+=
2640 btrfs_file_extent_disk_num_bytes(buf
, fi
);
2641 if (data_bytes_allocated
< root
->sectorsize
) {
2644 data_bytes_referenced
+=
2645 btrfs_file_extent_num_bytes(buf
, fi
);
2646 ret
= add_extent_rec(extent_cache
, NULL
,
2647 btrfs_file_extent_disk_bytenr(buf
, fi
),
2648 btrfs_file_extent_disk_num_bytes(buf
, fi
),
2650 btrfs_file_extent_disk_num_bytes(buf
, fi
));
2651 add_data_backref(extent_cache
,
2652 btrfs_file_extent_disk_bytenr(buf
, fi
),
2653 parent
, owner
, key
.objectid
, key
.offset
-
2654 btrfs_file_extent_offset(buf
, fi
), 1, 1,
2655 btrfs_file_extent_disk_num_bytes(buf
, fi
));
2660 struct btrfs_key first_key
;
2662 first_key
.objectid
= 0;
2665 btrfs_item_key_to_cpu(buf
, &first_key
, 0);
2666 level
= btrfs_header_level(buf
);
2667 for (i
= 0; i
< nritems
; i
++) {
2668 u64 ptr
= btrfs_node_blockptr(buf
, i
);
2669 u32 size
= btrfs_level_size(root
, level
- 1);
2670 btrfs_node_key_to_cpu(buf
, &key
, i
);
2671 ret
= add_extent_rec(extent_cache
, &key
,
2672 ptr
, size
, 0, 0, 1, 0, size
);
2675 add_tree_backref(extent_cache
, ptr
, parent
, owner
, 1);
2678 add_pending(nodes
, seen
, ptr
, size
);
2680 add_pending(pending
, seen
, ptr
, size
);
2683 btree_space_waste
+= (BTRFS_NODEPTRS_PER_BLOCK(root
) -
2684 nritems
) * sizeof(struct btrfs_key_ptr
);
2686 total_btree_bytes
+= buf
->len
;
2687 if (fs_root_objectid(btrfs_header_owner(buf
)))
2688 total_fs_tree_bytes
+= buf
->len
;
2689 if (!found_old_backref
&&
2690 btrfs_header_owner(buf
) == BTRFS_TREE_RELOC_OBJECTID
&&
2691 btrfs_header_backref_rev(buf
) == BTRFS_MIXED_BACKREF_REV
&&
2692 !btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_RELOC
))
2693 found_old_backref
= 1;
2694 free_extent_buffer(buf
);
2698 static int add_root_to_pending(struct extent_buffer
*buf
,
2699 struct block_info
*bits
,
2701 struct cache_tree
*extent_cache
,
2702 struct cache_tree
*pending
,
2703 struct cache_tree
*seen
,
2704 struct cache_tree
*reada
,
2705 struct cache_tree
*nodes
,
2706 struct btrfs_key
*root_key
)
2708 if (btrfs_header_level(buf
) > 0)
2709 add_pending(nodes
, seen
, buf
->start
, buf
->len
);
2711 add_pending(pending
, seen
, buf
->start
, buf
->len
);
2712 add_extent_rec(extent_cache
, NULL
, buf
->start
, buf
->len
,
2713 0, 1, 1, 0, buf
->len
);
2715 if (root_key
->objectid
== BTRFS_TREE_RELOC_OBJECTID
||
2716 btrfs_header_backref_rev(buf
) < BTRFS_MIXED_BACKREF_REV
)
2717 add_tree_backref(extent_cache
, buf
->start
, buf
->start
,
2720 add_tree_backref(extent_cache
, buf
->start
, 0,
2721 root_key
->objectid
, 1);
2725 static int delete_extent_records(struct btrfs_trans_handle
*trans
,
2726 struct btrfs_root
*root
,
2727 struct btrfs_path
*path
,
2728 u64 bytenr
, u64 new_len
)
2730 struct btrfs_key key
;
2731 struct btrfs_key found_key
;
2732 struct extent_buffer
*leaf
;
2737 key
.objectid
= bytenr
;
2739 key
.offset
= (u64
)-1;
2742 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
,
2749 if (path
->slots
[0] == 0)
2755 leaf
= path
->nodes
[0];
2756 slot
= path
->slots
[0];
2758 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
2759 if (found_key
.objectid
!= bytenr
)
2762 if (found_key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
2763 found_key
.type
!= BTRFS_TREE_BLOCK_REF_KEY
&&
2764 found_key
.type
!= BTRFS_EXTENT_DATA_REF_KEY
&&
2765 found_key
.type
!= BTRFS_EXTENT_REF_V0_KEY
&&
2766 found_key
.type
!= BTRFS_SHARED_BLOCK_REF_KEY
&&
2767 found_key
.type
!= BTRFS_SHARED_DATA_REF_KEY
) {
2768 btrfs_release_path(NULL
, path
);
2769 if (found_key
.type
== 0) {
2770 if (found_key
.offset
== 0)
2772 key
.offset
= found_key
.offset
- 1;
2773 key
.type
= found_key
.type
;
2775 key
.type
= found_key
.type
- 1;
2776 key
.offset
= (u64
)-1;
2780 fprintf(stderr
, "repair deleting extent record: key %Lu %u %Lu\n",
2781 found_key
.objectid
, found_key
.type
, found_key
.offset
);
2783 ret
= btrfs_del_item(trans
, root
->fs_info
->extent_root
, path
);
2786 btrfs_release_path(NULL
, path
);
2788 if (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
2789 ret
= btrfs_update_block_group(trans
, root
, bytenr
,
2790 found_key
.offset
, 0, 0);
2796 btrfs_release_path(NULL
, path
);
2801 * for a single backref, this will allocate a new extent
2802 * and add the backref to it.
2804 static int record_extent(struct btrfs_trans_handle
*trans
,
2805 struct btrfs_fs_info
*info
,
2806 struct btrfs_path
*path
,
2807 struct extent_record
*rec
,
2808 struct extent_backref
*back
,
2809 int allocated
, u64 flags
)
2812 struct btrfs_root
*extent_root
= info
->extent_root
;
2813 struct extent_buffer
*leaf
;
2814 struct btrfs_key ins_key
;
2815 struct btrfs_extent_item
*ei
;
2816 struct tree_backref
*tback
;
2817 struct data_backref
*dback
;
2818 struct btrfs_tree_block_info
*bi
;
2821 rec
->max_size
= max_t(u64
, rec
->max_size
,
2822 info
->extent_root
->leafsize
);
2825 u32 item_size
= sizeof(*ei
);
2828 item_size
+= sizeof(*bi
);
2830 ins_key
.objectid
= rec
->start
;
2831 ins_key
.offset
= rec
->max_size
;
2832 ins_key
.type
= BTRFS_EXTENT_ITEM_KEY
;
2834 ret
= btrfs_insert_empty_item(trans
, extent_root
, path
,
2835 &ins_key
, item_size
);
2839 leaf
= path
->nodes
[0];
2840 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
2841 struct btrfs_extent_item
);
2843 btrfs_set_extent_refs(leaf
, ei
, 0);
2844 btrfs_set_extent_generation(leaf
, ei
, rec
->generation
);
2846 if (back
->is_data
) {
2847 btrfs_set_extent_flags(leaf
, ei
,
2848 BTRFS_EXTENT_FLAG_DATA
);
2850 struct btrfs_disk_key copy_key
;;
2852 tback
= (struct tree_backref
*)back
;
2853 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
2854 memset_extent_buffer(leaf
, 0, (unsigned long)bi
,
2856 memset(©_key
, 0, sizeof(copy_key
));
2858 copy_key
.objectid
= le64_to_cpu(rec
->info_objectid
);
2859 btrfs_set_tree_block_level(leaf
, bi
, rec
->info_level
);
2860 btrfs_set_tree_block_key(leaf
, bi
, ©_key
);
2862 btrfs_set_extent_flags(leaf
, ei
,
2863 BTRFS_EXTENT_FLAG_TREE_BLOCK
| flags
);
2866 btrfs_mark_buffer_dirty(leaf
);
2867 ret
= btrfs_update_block_group(trans
, extent_root
, rec
->start
,
2868 rec
->max_size
, 1, 0);
2871 btrfs_release_path(NULL
, path
);
2874 if (back
->is_data
) {
2878 dback
= (struct data_backref
*)back
;
2879 if (back
->full_backref
)
2880 parent
= dback
->parent
;
2884 for (i
= 0; i
< dback
->found_ref
; i
++) {
2885 /* if parent != 0, we're doing a full backref
2886 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
2887 * just makes the backref allocator create a data
2890 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
2891 rec
->start
, rec
->max_size
,
2895 BTRFS_FIRST_FREE_OBJECTID
:
2901 fprintf(stderr
, "adding new data backref"
2902 " on %llu %s %llu owner %llu"
2903 " offset %llu found %d\n",
2904 (unsigned long long)rec
->start
,
2905 back
->full_backref
?
2907 back
->full_backref
?
2908 (unsigned long long)parent
:
2909 (unsigned long long)dback
->root
,
2910 (unsigned long long)dback
->owner
,
2911 (unsigned long long)dback
->offset
,
2916 tback
= (struct tree_backref
*)back
;
2917 if (back
->full_backref
)
2918 parent
= tback
->parent
;
2922 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
2923 rec
->start
, rec
->max_size
,
2924 parent
, tback
->root
, 0, 0);
2925 fprintf(stderr
, "adding new tree backref on "
2926 "start %llu len %llu parent %llu root %llu\n",
2927 rec
->start
, rec
->max_size
, tback
->parent
, tback
->root
);
2932 btrfs_release_path(NULL
, path
);
2937 * when an incorrect extent item is found, this will delete
2938 * all of the existing entries for it and recreate them
2939 * based on what the tree scan found.
2941 static int fixup_extent_refs(struct btrfs_trans_handle
*trans
,
2942 struct btrfs_fs_info
*info
,
2943 struct extent_record
*rec
)
2946 struct btrfs_path
*path
;
2947 struct list_head
*cur
= rec
->backrefs
.next
;
2948 struct extent_backref
*back
;
2952 /* remember our flags for recreating the extent */
2953 ret
= btrfs_lookup_extent_info(NULL
, info
->extent_root
, rec
->start
,
2954 rec
->max_size
, NULL
, &flags
);
2956 flags
= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
2958 path
= btrfs_alloc_path();
2960 /* step one, delete all the existing records */
2961 ret
= delete_extent_records(trans
, info
->extent_root
, path
,
2962 rec
->start
, rec
->max_size
);
2967 /* step two, recreate all the refs we did find */
2968 while(cur
!= &rec
->backrefs
) {
2969 back
= list_entry(cur
, struct extent_backref
, list
);
2973 * if we didn't find any references, don't create a
2976 if (!back
->found_ref
)
2979 ret
= record_extent(trans
, info
, path
, rec
, back
, allocated
, flags
);
2986 btrfs_free_path(path
);
2990 static int check_extent_refs(struct btrfs_trans_handle
*trans
,
2991 struct btrfs_root
*root
,
2992 struct cache_tree
*extent_cache
, int repair
)
2994 struct extent_record
*rec
;
2995 struct cache_extent
*cache
;
3002 * if we're doing a repair, we have to make sure
3003 * we don't allocate from the problem extents.
3004 * In the worst case, this will be all the
3007 cache
= find_first_cache_extent(extent_cache
, 0);
3009 rec
= container_of(cache
, struct extent_record
, cache
);
3010 btrfs_pin_extent(root
->fs_info
,
3011 rec
->start
, rec
->nr
);
3012 cache
= next_cache_extent(cache
);
3017 cache
= find_first_cache_extent(extent_cache
, 0);
3020 rec
= container_of(cache
, struct extent_record
, cache
);
3021 if (rec
->refs
!= rec
->extent_item_refs
) {
3022 fprintf(stderr
, "ref mismatch on [%llu %llu] ",
3023 (unsigned long long)rec
->start
,
3024 (unsigned long long)rec
->nr
);
3025 fprintf(stderr
, "extent item %llu, found %llu\n",
3026 (unsigned long long)rec
->extent_item_refs
,
3027 (unsigned long long)rec
->refs
);
3028 if (!fixed
&& repair
) {
3029 ret
= fixup_extent_refs(trans
, root
->fs_info
, rec
);
3037 if (all_backpointers_checked(rec
, 1)) {
3038 fprintf(stderr
, "backpointer mismatch on [%llu %llu]\n",
3039 (unsigned long long)rec
->start
,
3040 (unsigned long long)rec
->nr
);
3042 if (!fixed
&& repair
) {
3043 ret
= fixup_extent_refs(trans
, root
->fs_info
, rec
);
3051 if (!rec
->owner_ref_checked
) {
3052 fprintf(stderr
, "owner ref check failed [%llu %llu]\n",
3053 (unsigned long long)rec
->start
,
3054 (unsigned long long)rec
->nr
);
3055 if (!fixed
&& repair
) {
3056 ret
= fixup_extent_refs(trans
, root
->fs_info
, rec
);
3064 remove_cache_extent(extent_cache
, cache
);
3065 free_all_extent_backrefs(rec
);
3071 fprintf(stderr
, "failed to repair damaged filesystem, aborting\n");
3078 static int check_extents(struct btrfs_trans_handle
*trans
,
3079 struct btrfs_root
*root
, int repair
)
3081 struct cache_tree extent_cache
;
3082 struct cache_tree seen
;
3083 struct cache_tree pending
;
3084 struct cache_tree reada
;
3085 struct cache_tree nodes
;
3086 struct btrfs_path path
;
3087 struct btrfs_key key
;
3088 struct btrfs_key found_key
;
3091 struct block_info
*bits
;
3093 struct extent_buffer
*leaf
;
3095 struct btrfs_root_item ri
;
3097 cache_tree_init(&extent_cache
);
3098 cache_tree_init(&seen
);
3099 cache_tree_init(&pending
);
3100 cache_tree_init(&nodes
);
3101 cache_tree_init(&reada
);
3104 bits
= malloc(bits_nr
* sizeof(struct block_info
));
3110 add_root_to_pending(root
->fs_info
->tree_root
->node
, bits
, bits_nr
,
3111 &extent_cache
, &pending
, &seen
, &reada
, &nodes
,
3112 &root
->fs_info
->tree_root
->root_key
);
3114 add_root_to_pending(root
->fs_info
->chunk_root
->node
, bits
, bits_nr
,
3115 &extent_cache
, &pending
, &seen
, &reada
, &nodes
,
3116 &root
->fs_info
->chunk_root
->root_key
);
3118 btrfs_init_path(&path
);
3121 btrfs_set_key_type(&key
, BTRFS_ROOT_ITEM_KEY
);
3122 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
,
3126 leaf
= path
.nodes
[0];
3127 slot
= path
.slots
[0];
3128 if (slot
>= btrfs_header_nritems(path
.nodes
[0])) {
3129 ret
= btrfs_next_leaf(root
, &path
);
3132 leaf
= path
.nodes
[0];
3133 slot
= path
.slots
[0];
3135 btrfs_item_key_to_cpu(leaf
, &found_key
, path
.slots
[0]);
3136 if (btrfs_key_type(&found_key
) == BTRFS_ROOT_ITEM_KEY
) {
3137 unsigned long offset
;
3138 struct extent_buffer
*buf
;
3140 offset
= btrfs_item_ptr_offset(leaf
, path
.slots
[0]);
3141 read_extent_buffer(leaf
, &ri
, offset
, sizeof(ri
));
3142 buf
= read_tree_block(root
->fs_info
->tree_root
,
3143 btrfs_root_bytenr(&ri
),
3144 btrfs_level_size(root
,
3145 btrfs_root_level(&ri
)), 0);
3146 add_root_to_pending(buf
, bits
, bits_nr
, &extent_cache
,
3147 &pending
, &seen
, &reada
, &nodes
,
3149 free_extent_buffer(buf
);
3153 btrfs_release_path(root
, &path
);
3155 ret
= run_next_block(root
, bits
, bits_nr
, &last
, &pending
,
3156 &seen
, &reada
, &nodes
, &extent_cache
);
3160 ret
= check_extent_refs(trans
, root
, &extent_cache
, repair
);
3164 static void print_usage(void)
3166 fprintf(stderr
, "usage: btrfsck dev\n");
3167 fprintf(stderr
, "%s\n", BTRFS_BUILD_VERSION
);
3171 static struct option long_options
[] = {
3172 { "super", 1, NULL
, 's' },
3173 { "repair", 0, NULL
, 0 },
3177 int main(int ac
, char **av
)
3179 struct cache_tree root_cache
;
3180 struct btrfs_root
*root
;
3181 struct btrfs_fs_info
*info
;
3182 struct btrfs_trans_handle
*trans
= NULL
;
3187 int option_index
= 0;
3191 c
= getopt_long(ac
, av
, "", long_options
,
3198 bytenr
= btrfs_sb_offset(num
);
3199 printf("using SB copy %d, bytenr %llu\n", num
,
3200 (unsigned long long)bytenr
);
3205 if (option_index
== 1) {
3206 printf("enabling repair mode\n");
3217 cache_tree_init(&root_cache
);
3219 if((ret
= check_mounted(av
[optind
])) < 0) {
3220 fprintf(stderr
, "Could not check mount status: %s\n", strerror(-ret
));
3223 fprintf(stderr
, "%s is currently mounted. Aborting.\n", av
[optind
]);
3227 info
= open_ctree_fs_info(av
[optind
], bytenr
, repair
, 1);
3232 if (!extent_buffer_uptodate(info
->tree_root
->node
) ||
3233 !extent_buffer_uptodate(info
->dev_root
->node
) ||
3234 !extent_buffer_uptodate(info
->extent_root
->node
) ||
3235 !extent_buffer_uptodate(info
->chunk_root
->node
)) {
3236 fprintf(stderr
, "Critical roots corrupted, unable to fsck the FS\n");
3240 root
= info
->fs_root
;
3242 fprintf(stderr
, "checking extents\n");
3244 trans
= btrfs_start_transaction(root
, 1);
3246 ret
= check_extents(trans
, root
, repair
);
3251 btrfs_fix_block_accounting(trans
, root
);
3253 fprintf(stderr
, "checking fs roots\n");
3254 ret
= check_fs_roots(root
, &root_cache
);
3258 fprintf(stderr
, "checking root refs\n");
3259 ret
= check_root_refs(root
, &root_cache
);
3261 free_root_recs(&root_cache
);
3263 ret
= btrfs_commit_transaction(trans
, root
);
3269 if (found_old_backref
) {
3271 * there was a disk format change when mixed
3272 * backref was in testing tree. The old format
3273 * existed about one week.
3275 printf("\n * Found old mixed backref format. "
3276 "The old format is not supported! *"
3277 "\n * Please mount the FS in readonly mode, "
3278 "backup data and re-format the FS. *\n\n");
3281 printf("found %llu bytes used err is %d\n",
3282 (unsigned long long)bytes_used
, ret
);
3283 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes
);
3284 printf("total tree bytes: %llu\n",
3285 (unsigned long long)total_btree_bytes
);
3286 printf("total fs tree bytes: %llu\n",
3287 (unsigned long long)total_fs_tree_bytes
);
3288 printf("btree space waste bytes: %llu\n",
3289 (unsigned long long)btree_space_waste
);
3290 printf("file data blocks allocated: %llu\n referenced %llu\n",
3291 (unsigned long long)data_bytes_allocated
,
3292 (unsigned long long)data_bytes_referenced
);
3293 printf("%s\n", BTRFS_BUILD_VERSION
);