2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #define _XOPEN_SOURCE 500
25 #include <sys/types.h>
29 #include <uuid/uuid.h>
34 #include "print-tree.h"
35 #include "transaction.h"
39 #include "free-space-cache.h"
41 #include "qgroup-verify.h"
43 static u64 bytes_used
= 0;
44 static u64 total_csum_bytes
= 0;
45 static u64 total_btree_bytes
= 0;
46 static u64 total_fs_tree_bytes
= 0;
47 static u64 total_extent_tree_bytes
= 0;
48 static u64 btree_space_waste
= 0;
49 static u64 data_bytes_allocated
= 0;
50 static u64 data_bytes_referenced
= 0;
51 static int found_old_backref
= 0;
52 static LIST_HEAD(duplicate_extents
);
53 static LIST_HEAD(delete_items
);
54 static int repair
= 0;
55 static int no_holes
= 0;
56 static int init_extent_tree
= 0;
57 static int check_data_csum
= 0;
59 struct extent_backref
{
60 struct list_head list
;
61 unsigned int is_data
:1;
62 unsigned int found_extent_tree
:1;
63 unsigned int full_backref
:1;
64 unsigned int found_ref
:1;
65 unsigned int broken
:1;
69 struct extent_backref node
;
84 struct extent_backref node
;
91 struct extent_record
{
92 struct list_head backrefs
;
93 struct list_head dups
;
94 struct list_head list
;
95 struct cache_extent cache
;
96 struct btrfs_disk_key parent_key
;
101 u64 extent_item_refs
;
103 u64 parent_generation
;
107 unsigned int found_rec
:1;
108 unsigned int content_checked
:1;
109 unsigned int owner_ref_checked
:1;
110 unsigned int is_root
:1;
111 unsigned int metadata
:1;
114 struct inode_backref
{
115 struct list_head list
;
116 unsigned int found_dir_item
:1;
117 unsigned int found_dir_index
:1;
118 unsigned int found_inode_ref
:1;
119 unsigned int filetype
:8;
121 unsigned int ref_type
;
128 struct dropping_root_item_record
{
129 struct list_head list
;
130 struct btrfs_root_item ri
;
131 struct btrfs_key found_key
;
134 #define REF_ERR_NO_DIR_ITEM (1 << 0)
135 #define REF_ERR_NO_DIR_INDEX (1 << 1)
136 #define REF_ERR_NO_INODE_REF (1 << 2)
137 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
138 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
139 #define REF_ERR_DUP_INODE_REF (1 << 5)
140 #define REF_ERR_INDEX_UNMATCH (1 << 6)
141 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
142 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
143 #define REF_ERR_NO_ROOT_REF (1 << 9)
144 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
145 #define REF_ERR_DUP_ROOT_REF (1 << 11)
146 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
148 struct inode_record
{
149 struct list_head backrefs
;
150 unsigned int checked
:1;
151 unsigned int merging
:1;
152 unsigned int found_inode_item
:1;
153 unsigned int found_dir_item
:1;
154 unsigned int found_file_extent
:1;
155 unsigned int found_csum_item
:1;
156 unsigned int some_csum_missing
:1;
157 unsigned int nodatasum
:1;
170 u64 first_extent_gap
;
175 #define I_ERR_NO_INODE_ITEM (1 << 0)
176 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
177 #define I_ERR_DUP_INODE_ITEM (1 << 2)
178 #define I_ERR_DUP_DIR_INDEX (1 << 3)
179 #define I_ERR_ODD_DIR_ITEM (1 << 4)
180 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
181 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
182 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
183 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
184 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
185 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
186 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
187 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
188 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
190 struct root_backref
{
191 struct list_head list
;
192 unsigned int found_dir_item
:1;
193 unsigned int found_dir_index
:1;
194 unsigned int found_back_ref
:1;
195 unsigned int found_forward_ref
:1;
196 unsigned int reachable
:1;
206 struct list_head backrefs
;
207 struct cache_extent cache
;
208 unsigned int found_root_item
:1;
214 struct cache_extent cache
;
219 struct cache_extent cache
;
220 struct cache_tree root_cache
;
221 struct cache_tree inode_cache
;
222 struct inode_record
*current
;
231 struct walk_control
{
232 struct cache_tree shared
;
233 struct shared_node
*nodes
[BTRFS_MAX_LEVEL
];
239 struct btrfs_key key
;
241 struct list_head list
;
244 static void reset_cached_block_groups(struct btrfs_fs_info
*fs_info
);
246 static u8
imode_to_type(u32 imode
)
249 static unsigned char btrfs_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
250 [S_IFREG
>> S_SHIFT
] = BTRFS_FT_REG_FILE
,
251 [S_IFDIR
>> S_SHIFT
] = BTRFS_FT_DIR
,
252 [S_IFCHR
>> S_SHIFT
] = BTRFS_FT_CHRDEV
,
253 [S_IFBLK
>> S_SHIFT
] = BTRFS_FT_BLKDEV
,
254 [S_IFIFO
>> S_SHIFT
] = BTRFS_FT_FIFO
,
255 [S_IFSOCK
>> S_SHIFT
] = BTRFS_FT_SOCK
,
256 [S_IFLNK
>> S_SHIFT
] = BTRFS_FT_SYMLINK
,
259 return btrfs_type_by_mode
[(imode
& S_IFMT
) >> S_SHIFT
];
263 static int device_record_compare(struct rb_node
*node1
, struct rb_node
*node2
)
265 struct device_record
*rec1
;
266 struct device_record
*rec2
;
268 rec1
= rb_entry(node1
, struct device_record
, node
);
269 rec2
= rb_entry(node2
, struct device_record
, node
);
270 if (rec1
->devid
> rec2
->devid
)
272 else if (rec1
->devid
< rec2
->devid
)
278 static struct inode_record
*clone_inode_rec(struct inode_record
*orig_rec
)
280 struct inode_record
*rec
;
281 struct inode_backref
*backref
;
282 struct inode_backref
*orig
;
285 rec
= malloc(sizeof(*rec
));
286 memcpy(rec
, orig_rec
, sizeof(*rec
));
288 INIT_LIST_HEAD(&rec
->backrefs
);
290 list_for_each_entry(orig
, &orig_rec
->backrefs
, list
) {
291 size
= sizeof(*orig
) + orig
->namelen
+ 1;
292 backref
= malloc(size
);
293 memcpy(backref
, orig
, size
);
294 list_add_tail(&backref
->list
, &rec
->backrefs
);
299 static void print_inode_error(int errors
)
301 if (errors
& I_ERR_NO_INODE_ITEM
)
302 fprintf(stderr
, ", no inode item");
303 if (errors
& I_ERR_NO_ORPHAN_ITEM
)
304 fprintf(stderr
, ", no orphan item");
305 if (errors
& I_ERR_DUP_INODE_ITEM
)
306 fprintf(stderr
, ", dup inode item");
307 if (errors
& I_ERR_DUP_DIR_INDEX
)
308 fprintf(stderr
, ", dup dir index");
309 if (errors
& I_ERR_ODD_DIR_ITEM
)
310 fprintf(stderr
, ", odd dir item");
311 if (errors
& I_ERR_ODD_FILE_EXTENT
)
312 fprintf(stderr
, ", odd file extent");
313 if (errors
& I_ERR_BAD_FILE_EXTENT
)
314 fprintf(stderr
, ", bad file extent");
315 if (errors
& I_ERR_FILE_EXTENT_OVERLAP
)
316 fprintf(stderr
, ", file extent overlap");
317 if (errors
& I_ERR_FILE_EXTENT_DISCOUNT
)
318 fprintf(stderr
, ", file extent discount");
319 if (errors
& I_ERR_DIR_ISIZE_WRONG
)
320 fprintf(stderr
, ", dir isize wrong");
321 if (errors
& I_ERR_FILE_NBYTES_WRONG
)
322 fprintf(stderr
, ", nbytes wrong");
323 if (errors
& I_ERR_ODD_CSUM_ITEM
)
324 fprintf(stderr
, ", odd csum item");
325 if (errors
& I_ERR_SOME_CSUM_MISSING
)
326 fprintf(stderr
, ", some csum missing");
327 if (errors
& I_ERR_LINK_COUNT_WRONG
)
328 fprintf(stderr
, ", link count wrong");
329 fprintf(stderr
, "\n");
332 static void print_ref_error(int errors
)
334 if (errors
& REF_ERR_NO_DIR_ITEM
)
335 fprintf(stderr
, ", no dir item");
336 if (errors
& REF_ERR_NO_DIR_INDEX
)
337 fprintf(stderr
, ", no dir index");
338 if (errors
& REF_ERR_NO_INODE_REF
)
339 fprintf(stderr
, ", no inode ref");
340 if (errors
& REF_ERR_DUP_DIR_ITEM
)
341 fprintf(stderr
, ", dup dir item");
342 if (errors
& REF_ERR_DUP_DIR_INDEX
)
343 fprintf(stderr
, ", dup dir index");
344 if (errors
& REF_ERR_DUP_INODE_REF
)
345 fprintf(stderr
, ", dup inode ref");
346 if (errors
& REF_ERR_INDEX_UNMATCH
)
347 fprintf(stderr
, ", index unmatch");
348 if (errors
& REF_ERR_FILETYPE_UNMATCH
)
349 fprintf(stderr
, ", filetype unmatch");
350 if (errors
& REF_ERR_NAME_TOO_LONG
)
351 fprintf(stderr
, ", name too long");
352 if (errors
& REF_ERR_NO_ROOT_REF
)
353 fprintf(stderr
, ", no root ref");
354 if (errors
& REF_ERR_NO_ROOT_BACKREF
)
355 fprintf(stderr
, ", no root backref");
356 if (errors
& REF_ERR_DUP_ROOT_REF
)
357 fprintf(stderr
, ", dup root ref");
358 if (errors
& REF_ERR_DUP_ROOT_BACKREF
)
359 fprintf(stderr
, ", dup root backref");
360 fprintf(stderr
, "\n");
363 static struct inode_record
*get_inode_rec(struct cache_tree
*inode_cache
,
366 struct ptr_node
*node
;
367 struct cache_extent
*cache
;
368 struct inode_record
*rec
= NULL
;
371 cache
= lookup_cache_extent(inode_cache
, ino
, 1);
373 node
= container_of(cache
, struct ptr_node
, cache
);
375 if (mod
&& rec
->refs
> 1) {
376 node
->data
= clone_inode_rec(rec
);
381 rec
= calloc(1, sizeof(*rec
));
383 rec
->extent_start
= (u64
)-1;
384 rec
->first_extent_gap
= (u64
)-1;
386 INIT_LIST_HEAD(&rec
->backrefs
);
388 node
= malloc(sizeof(*node
));
389 node
->cache
.start
= ino
;
390 node
->cache
.size
= 1;
393 if (ino
== BTRFS_FREE_INO_OBJECTID
)
396 ret
= insert_cache_extent(inode_cache
, &node
->cache
);
402 static void free_inode_rec(struct inode_record
*rec
)
404 struct inode_backref
*backref
;
409 while (!list_empty(&rec
->backrefs
)) {
410 backref
= list_entry(rec
->backrefs
.next
,
411 struct inode_backref
, list
);
412 list_del(&backref
->list
);
418 static int can_free_inode_rec(struct inode_record
*rec
)
420 if (!rec
->errors
&& rec
->checked
&& rec
->found_inode_item
&&
421 rec
->nlink
== rec
->found_link
&& list_empty(&rec
->backrefs
))
426 static void maybe_free_inode_rec(struct cache_tree
*inode_cache
,
427 struct inode_record
*rec
)
429 struct cache_extent
*cache
;
430 struct inode_backref
*tmp
, *backref
;
431 struct ptr_node
*node
;
432 unsigned char filetype
;
434 if (!rec
->found_inode_item
)
437 filetype
= imode_to_type(rec
->imode
);
438 list_for_each_entry_safe(backref
, tmp
, &rec
->backrefs
, list
) {
439 if (backref
->found_dir_item
&& backref
->found_dir_index
) {
440 if (backref
->filetype
!= filetype
)
441 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
442 if (!backref
->errors
&& backref
->found_inode_ref
) {
443 list_del(&backref
->list
);
449 if (!rec
->checked
|| rec
->merging
)
452 if (S_ISDIR(rec
->imode
)) {
453 if (rec
->found_size
!= rec
->isize
)
454 rec
->errors
|= I_ERR_DIR_ISIZE_WRONG
;
455 if (rec
->found_file_extent
)
456 rec
->errors
|= I_ERR_ODD_FILE_EXTENT
;
457 } else if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
458 if (rec
->found_dir_item
)
459 rec
->errors
|= I_ERR_ODD_DIR_ITEM
;
460 if (rec
->found_size
!= rec
->nbytes
)
461 rec
->errors
|= I_ERR_FILE_NBYTES_WRONG
;
462 if (rec
->extent_start
== (u64
)-1 || rec
->extent_start
> 0)
463 rec
->first_extent_gap
= 0;
464 if (rec
->nlink
> 0 && !no_holes
&&
465 (rec
->extent_end
< rec
->isize
||
466 rec
->first_extent_gap
< rec
->isize
))
467 rec
->errors
|= I_ERR_FILE_EXTENT_DISCOUNT
;
470 if (S_ISREG(rec
->imode
) || S_ISLNK(rec
->imode
)) {
471 if (rec
->found_csum_item
&& rec
->nodatasum
)
472 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
473 if (rec
->some_csum_missing
&& !rec
->nodatasum
)
474 rec
->errors
|= I_ERR_SOME_CSUM_MISSING
;
477 BUG_ON(rec
->refs
!= 1);
478 if (can_free_inode_rec(rec
)) {
479 cache
= lookup_cache_extent(inode_cache
, rec
->ino
, 1);
480 node
= container_of(cache
, struct ptr_node
, cache
);
481 BUG_ON(node
->data
!= rec
);
482 remove_cache_extent(inode_cache
, &node
->cache
);
488 static int check_orphan_item(struct btrfs_root
*root
, u64 ino
)
490 struct btrfs_path path
;
491 struct btrfs_key key
;
494 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
495 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
498 btrfs_init_path(&path
);
499 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
500 btrfs_release_path(&path
);
506 static int process_inode_item(struct extent_buffer
*eb
,
507 int slot
, struct btrfs_key
*key
,
508 struct shared_node
*active_node
)
510 struct inode_record
*rec
;
511 struct btrfs_inode_item
*item
;
513 rec
= active_node
->current
;
514 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
515 if (rec
->found_inode_item
) {
516 rec
->errors
|= I_ERR_DUP_INODE_ITEM
;
519 item
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_item
);
520 rec
->nlink
= btrfs_inode_nlink(eb
, item
);
521 rec
->isize
= btrfs_inode_size(eb
, item
);
522 rec
->nbytes
= btrfs_inode_nbytes(eb
, item
);
523 rec
->imode
= btrfs_inode_mode(eb
, item
);
524 if (btrfs_inode_flags(eb
, item
) & BTRFS_INODE_NODATASUM
)
526 rec
->found_inode_item
= 1;
528 rec
->errors
|= I_ERR_NO_ORPHAN_ITEM
;
529 maybe_free_inode_rec(&active_node
->inode_cache
, rec
);
533 static struct inode_backref
*get_inode_backref(struct inode_record
*rec
,
535 int namelen
, u64 dir
)
537 struct inode_backref
*backref
;
539 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
540 if (backref
->dir
!= dir
|| backref
->namelen
!= namelen
)
542 if (memcmp(name
, backref
->name
, namelen
))
547 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
548 memset(backref
, 0, sizeof(*backref
));
550 backref
->namelen
= namelen
;
551 memcpy(backref
->name
, name
, namelen
);
552 backref
->name
[namelen
] = '\0';
553 list_add_tail(&backref
->list
, &rec
->backrefs
);
557 static int add_inode_backref(struct cache_tree
*inode_cache
,
558 u64 ino
, u64 dir
, u64 index
,
559 const char *name
, int namelen
,
560 int filetype
, int itemtype
, int errors
)
562 struct inode_record
*rec
;
563 struct inode_backref
*backref
;
565 rec
= get_inode_rec(inode_cache
, ino
, 1);
566 backref
= get_inode_backref(rec
, name
, namelen
, dir
);
568 backref
->errors
|= errors
;
569 if (itemtype
== BTRFS_DIR_INDEX_KEY
) {
570 if (backref
->found_dir_index
)
571 backref
->errors
|= REF_ERR_DUP_DIR_INDEX
;
572 if (backref
->found_inode_ref
&& backref
->index
!= index
)
573 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
574 if (backref
->found_dir_item
&& backref
->filetype
!= filetype
)
575 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
577 backref
->index
= index
;
578 backref
->filetype
= filetype
;
579 backref
->found_dir_index
= 1;
580 } else if (itemtype
== BTRFS_DIR_ITEM_KEY
) {
582 if (backref
->found_dir_item
)
583 backref
->errors
|= REF_ERR_DUP_DIR_ITEM
;
584 if (backref
->found_dir_index
&& backref
->filetype
!= filetype
)
585 backref
->errors
|= REF_ERR_FILETYPE_UNMATCH
;
587 backref
->filetype
= filetype
;
588 backref
->found_dir_item
= 1;
589 } else if ((itemtype
== BTRFS_INODE_REF_KEY
) ||
590 (itemtype
== BTRFS_INODE_EXTREF_KEY
)) {
591 if (backref
->found_inode_ref
)
592 backref
->errors
|= REF_ERR_DUP_INODE_REF
;
593 if (backref
->found_dir_index
&& backref
->index
!= index
)
594 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
596 backref
->ref_type
= itemtype
;
597 backref
->index
= index
;
598 backref
->found_inode_ref
= 1;
603 maybe_free_inode_rec(inode_cache
, rec
);
607 static int merge_inode_recs(struct inode_record
*src
, struct inode_record
*dst
,
608 struct cache_tree
*dst_cache
)
610 struct inode_backref
*backref
;
614 list_for_each_entry(backref
, &src
->backrefs
, list
) {
615 if (backref
->found_dir_index
) {
616 add_inode_backref(dst_cache
, dst
->ino
, backref
->dir
,
617 backref
->index
, backref
->name
,
618 backref
->namelen
, backref
->filetype
,
619 BTRFS_DIR_INDEX_KEY
, backref
->errors
);
621 if (backref
->found_dir_item
) {
623 add_inode_backref(dst_cache
, dst
->ino
,
624 backref
->dir
, 0, backref
->name
,
625 backref
->namelen
, backref
->filetype
,
626 BTRFS_DIR_ITEM_KEY
, backref
->errors
);
628 if (backref
->found_inode_ref
) {
629 add_inode_backref(dst_cache
, dst
->ino
,
630 backref
->dir
, backref
->index
,
631 backref
->name
, backref
->namelen
, 0,
632 backref
->ref_type
, backref
->errors
);
636 if (src
->found_dir_item
)
637 dst
->found_dir_item
= 1;
638 if (src
->found_file_extent
)
639 dst
->found_file_extent
= 1;
640 if (src
->found_csum_item
)
641 dst
->found_csum_item
= 1;
642 if (src
->some_csum_missing
)
643 dst
->some_csum_missing
= 1;
644 if (dst
->first_extent_gap
> src
->first_extent_gap
)
645 dst
->first_extent_gap
= src
->first_extent_gap
;
647 BUG_ON(src
->found_link
< dir_count
);
648 dst
->found_link
+= src
->found_link
- dir_count
;
649 dst
->found_size
+= src
->found_size
;
650 if (src
->extent_start
!= (u64
)-1) {
651 if (dst
->extent_start
== (u64
)-1) {
652 dst
->extent_start
= src
->extent_start
;
653 dst
->extent_end
= src
->extent_end
;
655 if (dst
->extent_end
> src
->extent_start
)
656 dst
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
657 else if (dst
->extent_end
< src
->extent_start
&&
658 dst
->extent_end
< dst
->first_extent_gap
)
659 dst
->first_extent_gap
= dst
->extent_end
;
660 if (dst
->extent_end
< src
->extent_end
)
661 dst
->extent_end
= src
->extent_end
;
665 dst
->errors
|= src
->errors
;
666 if (src
->found_inode_item
) {
667 if (!dst
->found_inode_item
) {
668 dst
->nlink
= src
->nlink
;
669 dst
->isize
= src
->isize
;
670 dst
->nbytes
= src
->nbytes
;
671 dst
->imode
= src
->imode
;
672 dst
->nodatasum
= src
->nodatasum
;
673 dst
->found_inode_item
= 1;
675 dst
->errors
|= I_ERR_DUP_INODE_ITEM
;
683 static int splice_shared_node(struct shared_node
*src_node
,
684 struct shared_node
*dst_node
)
686 struct cache_extent
*cache
;
687 struct ptr_node
*node
, *ins
;
688 struct cache_tree
*src
, *dst
;
689 struct inode_record
*rec
, *conflict
;
694 if (--src_node
->refs
== 0)
696 if (src_node
->current
)
697 current_ino
= src_node
->current
->ino
;
699 src
= &src_node
->root_cache
;
700 dst
= &dst_node
->root_cache
;
702 cache
= search_cache_extent(src
, 0);
704 node
= container_of(cache
, struct ptr_node
, cache
);
706 cache
= next_cache_extent(cache
);
709 remove_cache_extent(src
, &node
->cache
);
712 ins
= malloc(sizeof(*ins
));
713 ins
->cache
.start
= node
->cache
.start
;
714 ins
->cache
.size
= node
->cache
.size
;
718 ret
= insert_cache_extent(dst
, &ins
->cache
);
719 if (ret
== -EEXIST
) {
720 conflict
= get_inode_rec(dst
, rec
->ino
, 1);
721 merge_inode_recs(rec
, conflict
, dst
);
723 conflict
->checked
= 1;
724 if (dst_node
->current
== conflict
)
725 dst_node
->current
= NULL
;
727 maybe_free_inode_rec(dst
, conflict
);
735 if (src
== &src_node
->root_cache
) {
736 src
= &src_node
->inode_cache
;
737 dst
= &dst_node
->inode_cache
;
741 if (current_ino
> 0 && (!dst_node
->current
||
742 current_ino
> dst_node
->current
->ino
)) {
743 if (dst_node
->current
) {
744 dst_node
->current
->checked
= 1;
745 maybe_free_inode_rec(dst
, dst_node
->current
);
747 dst_node
->current
= get_inode_rec(dst
, current_ino
, 1);
752 static void free_inode_ptr(struct cache_extent
*cache
)
754 struct ptr_node
*node
;
755 struct inode_record
*rec
;
757 node
= container_of(cache
, struct ptr_node
, cache
);
763 FREE_EXTENT_CACHE_BASED_TREE(inode_recs
, free_inode_ptr
);
765 static struct shared_node
*find_shared_node(struct cache_tree
*shared
,
768 struct cache_extent
*cache
;
769 struct shared_node
*node
;
771 cache
= lookup_cache_extent(shared
, bytenr
, 1);
773 node
= container_of(cache
, struct shared_node
, cache
);
779 static int add_shared_node(struct cache_tree
*shared
, u64 bytenr
, u32 refs
)
782 struct shared_node
*node
;
784 node
= calloc(1, sizeof(*node
));
785 node
->cache
.start
= bytenr
;
786 node
->cache
.size
= 1;
787 cache_tree_init(&node
->root_cache
);
788 cache_tree_init(&node
->inode_cache
);
791 ret
= insert_cache_extent(shared
, &node
->cache
);
796 static int enter_shared_node(struct btrfs_root
*root
, u64 bytenr
, u32 refs
,
797 struct walk_control
*wc
, int level
)
799 struct shared_node
*node
;
800 struct shared_node
*dest
;
802 if (level
== wc
->active_node
)
805 BUG_ON(wc
->active_node
<= level
);
806 node
= find_shared_node(&wc
->shared
, bytenr
);
808 add_shared_node(&wc
->shared
, bytenr
, refs
);
809 node
= find_shared_node(&wc
->shared
, bytenr
);
810 wc
->nodes
[level
] = node
;
811 wc
->active_node
= level
;
815 if (wc
->root_level
== wc
->active_node
&&
816 btrfs_root_refs(&root
->root_item
) == 0) {
817 if (--node
->refs
== 0) {
818 free_inode_recs_tree(&node
->root_cache
);
819 free_inode_recs_tree(&node
->inode_cache
);
820 remove_cache_extent(&wc
->shared
, &node
->cache
);
826 dest
= wc
->nodes
[wc
->active_node
];
827 splice_shared_node(node
, dest
);
828 if (node
->refs
== 0) {
829 remove_cache_extent(&wc
->shared
, &node
->cache
);
835 static int leave_shared_node(struct btrfs_root
*root
,
836 struct walk_control
*wc
, int level
)
838 struct shared_node
*node
;
839 struct shared_node
*dest
;
842 if (level
== wc
->root_level
)
845 for (i
= level
+ 1; i
< BTRFS_MAX_LEVEL
; i
++) {
849 BUG_ON(i
>= BTRFS_MAX_LEVEL
);
851 node
= wc
->nodes
[wc
->active_node
];
852 wc
->nodes
[wc
->active_node
] = NULL
;
855 dest
= wc
->nodes
[wc
->active_node
];
856 if (wc
->active_node
< wc
->root_level
||
857 btrfs_root_refs(&root
->root_item
) > 0) {
858 BUG_ON(node
->refs
<= 1);
859 splice_shared_node(node
, dest
);
861 BUG_ON(node
->refs
< 2);
867 static int is_child_root(struct btrfs_root
*root
, u64 parent_root_id
,
870 struct btrfs_path path
;
871 struct btrfs_key key
;
872 struct extent_buffer
*leaf
;
876 btrfs_init_path(&path
);
878 key
.objectid
= parent_root_id
;
879 key
.type
= BTRFS_ROOT_REF_KEY
;
880 key
.offset
= child_root_id
;
881 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
, &key
, &path
,
884 btrfs_release_path(&path
);
888 key
.objectid
= child_root_id
;
889 key
.type
= BTRFS_ROOT_BACKREF_KEY
;
891 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
, &key
, &path
,
896 leaf
= path
.nodes
[0];
897 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
898 ret
= btrfs_next_leaf(root
->fs_info
->tree_root
, &path
);
903 leaf
= path
.nodes
[0];
906 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
907 if (key
.objectid
!= child_root_id
||
908 key
.type
!= BTRFS_ROOT_BACKREF_KEY
)
913 if (key
.offset
== parent_root_id
) {
914 btrfs_release_path(&path
);
921 btrfs_release_path(&path
);
922 return has_parent
? 0 : -1;
925 static int process_dir_item(struct btrfs_root
*root
,
926 struct extent_buffer
*eb
,
927 int slot
, struct btrfs_key
*key
,
928 struct shared_node
*active_node
)
938 struct btrfs_dir_item
*di
;
939 struct inode_record
*rec
;
940 struct cache_tree
*root_cache
;
941 struct cache_tree
*inode_cache
;
942 struct btrfs_key location
;
943 char namebuf
[BTRFS_NAME_LEN
];
945 root_cache
= &active_node
->root_cache
;
946 inode_cache
= &active_node
->inode_cache
;
947 rec
= active_node
->current
;
948 rec
->found_dir_item
= 1;
950 di
= btrfs_item_ptr(eb
, slot
, struct btrfs_dir_item
);
951 total
= btrfs_item_size_nr(eb
, slot
);
952 while (cur
< total
) {
954 btrfs_dir_item_key_to_cpu(eb
, di
, &location
);
955 name_len
= btrfs_dir_name_len(eb
, di
);
956 data_len
= btrfs_dir_data_len(eb
, di
);
957 filetype
= btrfs_dir_type(eb
, di
);
959 rec
->found_size
+= name_len
;
960 if (name_len
<= BTRFS_NAME_LEN
) {
964 len
= BTRFS_NAME_LEN
;
965 error
= REF_ERR_NAME_TOO_LONG
;
967 read_extent_buffer(eb
, namebuf
, (unsigned long)(di
+ 1), len
);
969 if (location
.type
== BTRFS_INODE_ITEM_KEY
) {
970 add_inode_backref(inode_cache
, location
.objectid
,
971 key
->objectid
, key
->offset
, namebuf
,
972 len
, filetype
, key
->type
, error
);
973 } else if (location
.type
== BTRFS_ROOT_ITEM_KEY
) {
974 add_inode_backref(root_cache
, location
.objectid
,
975 key
->objectid
, key
->offset
,
976 namebuf
, len
, filetype
,
979 fprintf(stderr
, "warning line %d\n", __LINE__
);
982 len
= sizeof(*di
) + name_len
+ data_len
;
983 di
= (struct btrfs_dir_item
*)((char *)di
+ len
);
986 if (key
->type
== BTRFS_DIR_INDEX_KEY
&& nritems
> 1)
987 rec
->errors
|= I_ERR_DUP_DIR_INDEX
;
992 static int process_inode_ref(struct extent_buffer
*eb
,
993 int slot
, struct btrfs_key
*key
,
994 struct shared_node
*active_node
)
1002 struct cache_tree
*inode_cache
;
1003 struct btrfs_inode_ref
*ref
;
1004 char namebuf
[BTRFS_NAME_LEN
];
1006 inode_cache
= &active_node
->inode_cache
;
1008 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
1009 total
= btrfs_item_size_nr(eb
, slot
);
1010 while (cur
< total
) {
1011 name_len
= btrfs_inode_ref_name_len(eb
, ref
);
1012 index
= btrfs_inode_ref_index(eb
, ref
);
1013 if (name_len
<= BTRFS_NAME_LEN
) {
1017 len
= BTRFS_NAME_LEN
;
1018 error
= REF_ERR_NAME_TOO_LONG
;
1020 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
1021 add_inode_backref(inode_cache
, key
->objectid
, key
->offset
,
1022 index
, namebuf
, len
, 0, key
->type
, error
);
1024 len
= sizeof(*ref
) + name_len
;
1025 ref
= (struct btrfs_inode_ref
*)((char *)ref
+ len
);
1031 static int process_inode_extref(struct extent_buffer
*eb
,
1032 int slot
, struct btrfs_key
*key
,
1033 struct shared_node
*active_node
)
1042 struct cache_tree
*inode_cache
;
1043 struct btrfs_inode_extref
*extref
;
1044 char namebuf
[BTRFS_NAME_LEN
];
1046 inode_cache
= &active_node
->inode_cache
;
1048 extref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_extref
);
1049 total
= btrfs_item_size_nr(eb
, slot
);
1050 while (cur
< total
) {
1051 name_len
= btrfs_inode_extref_name_len(eb
, extref
);
1052 index
= btrfs_inode_extref_index(eb
, extref
);
1053 parent
= btrfs_inode_extref_parent(eb
, extref
);
1054 if (name_len
<= BTRFS_NAME_LEN
) {
1058 len
= BTRFS_NAME_LEN
;
1059 error
= REF_ERR_NAME_TOO_LONG
;
1061 read_extent_buffer(eb
, namebuf
,
1062 (unsigned long)(extref
+ 1), len
);
1063 add_inode_backref(inode_cache
, key
->objectid
, parent
,
1064 index
, namebuf
, len
, 0, key
->type
, error
);
1066 len
= sizeof(*extref
) + name_len
;
1067 extref
= (struct btrfs_inode_extref
*)((char *)extref
+ len
);
1074 static u64
count_csum_range(struct btrfs_root
*root
, u64 start
, u64 len
)
1076 struct btrfs_key key
;
1077 struct btrfs_path path
;
1078 struct extent_buffer
*leaf
;
1083 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
1085 btrfs_init_path(&path
);
1087 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
1089 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
1091 ret
= btrfs_search_slot(NULL
, root
->fs_info
->csum_root
,
1094 if (ret
> 0 && path
.slots
[0] > 0) {
1095 leaf
= path
.nodes
[0];
1096 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0] - 1);
1097 if (key
.objectid
== BTRFS_EXTENT_CSUM_OBJECTID
&&
1098 key
.type
== BTRFS_EXTENT_CSUM_KEY
)
1103 leaf
= path
.nodes
[0];
1104 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
1105 ret
= btrfs_next_leaf(root
->fs_info
->csum_root
, &path
);
1109 leaf
= path
.nodes
[0];
1112 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
1113 if (key
.objectid
!= BTRFS_EXTENT_CSUM_OBJECTID
||
1114 key
.type
!= BTRFS_EXTENT_CSUM_KEY
)
1117 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
1118 if (key
.offset
>= start
+ len
)
1121 if (key
.offset
> start
)
1124 size
= btrfs_item_size_nr(leaf
, path
.slots
[0]);
1125 csum_end
= key
.offset
+ (size
/ csum_size
) * root
->sectorsize
;
1126 if (csum_end
> start
) {
1127 size
= min(csum_end
- start
, len
);
1135 btrfs_release_path(&path
);
1139 static int process_file_extent(struct btrfs_root
*root
,
1140 struct extent_buffer
*eb
,
1141 int slot
, struct btrfs_key
*key
,
1142 struct shared_node
*active_node
)
1144 struct inode_record
*rec
;
1145 struct btrfs_file_extent_item
*fi
;
1147 u64 disk_bytenr
= 0;
1148 u64 extent_offset
= 0;
1149 u64 mask
= root
->sectorsize
- 1;
1152 rec
= active_node
->current
;
1153 BUG_ON(rec
->ino
!= key
->objectid
|| rec
->refs
> 1);
1154 rec
->found_file_extent
= 1;
1156 if (rec
->extent_start
== (u64
)-1) {
1157 rec
->extent_start
= key
->offset
;
1158 rec
->extent_end
= key
->offset
;
1161 if (rec
->extent_end
> key
->offset
)
1162 rec
->errors
|= I_ERR_FILE_EXTENT_OVERLAP
;
1163 else if (rec
->extent_end
< key
->offset
&&
1164 rec
->extent_end
< rec
->first_extent_gap
)
1165 rec
->first_extent_gap
= rec
->extent_end
;
1167 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
1168 extent_type
= btrfs_file_extent_type(eb
, fi
);
1170 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
1171 num_bytes
= btrfs_file_extent_inline_len(eb
, slot
, fi
);
1173 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1174 rec
->found_size
+= num_bytes
;
1175 num_bytes
= (num_bytes
+ mask
) & ~mask
;
1176 } else if (extent_type
== BTRFS_FILE_EXTENT_REG
||
1177 extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1178 num_bytes
= btrfs_file_extent_num_bytes(eb
, fi
);
1179 disk_bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
1180 extent_offset
= btrfs_file_extent_offset(eb
, fi
);
1181 if (num_bytes
== 0 || (num_bytes
& mask
))
1182 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1183 if (num_bytes
+ extent_offset
>
1184 btrfs_file_extent_ram_bytes(eb
, fi
))
1185 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1186 if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
&&
1187 (btrfs_file_extent_compression(eb
, fi
) ||
1188 btrfs_file_extent_encryption(eb
, fi
) ||
1189 btrfs_file_extent_other_encoding(eb
, fi
)))
1190 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1191 if (disk_bytenr
> 0)
1192 rec
->found_size
+= num_bytes
;
1194 rec
->errors
|= I_ERR_BAD_FILE_EXTENT
;
1196 rec
->extent_end
= key
->offset
+ num_bytes
;
1198 if (disk_bytenr
> 0) {
1200 if (btrfs_file_extent_compression(eb
, fi
))
1201 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
1203 disk_bytenr
+= extent_offset
;
1205 found
= count_csum_range(root
, disk_bytenr
, num_bytes
);
1206 if (extent_type
== BTRFS_FILE_EXTENT_REG
) {
1208 rec
->found_csum_item
= 1;
1209 if (found
< num_bytes
)
1210 rec
->some_csum_missing
= 1;
1211 } else if (extent_type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1213 rec
->errors
|= I_ERR_ODD_CSUM_ITEM
;
1219 static int process_one_leaf(struct btrfs_root
*root
, struct extent_buffer
*eb
,
1220 struct walk_control
*wc
)
1222 struct btrfs_key key
;
1227 struct cache_tree
*inode_cache
;
1228 struct shared_node
*active_node
;
1230 if (wc
->root_level
== wc
->active_node
&&
1231 btrfs_root_refs(&root
->root_item
) == 0)
1234 active_node
= wc
->nodes
[wc
->active_node
];
1235 inode_cache
= &active_node
->inode_cache
;
1236 nritems
= btrfs_header_nritems(eb
);
1237 for (i
= 0; i
< nritems
; i
++) {
1238 btrfs_item_key_to_cpu(eb
, &key
, i
);
1240 if (key
.objectid
== BTRFS_FREE_SPACE_OBJECTID
)
1242 if (key
.type
== BTRFS_ORPHAN_ITEM_KEY
)
1245 if (active_node
->current
== NULL
||
1246 active_node
->current
->ino
< key
.objectid
) {
1247 if (active_node
->current
) {
1248 active_node
->current
->checked
= 1;
1249 maybe_free_inode_rec(inode_cache
,
1250 active_node
->current
);
1252 active_node
->current
= get_inode_rec(inode_cache
,
1256 case BTRFS_DIR_ITEM_KEY
:
1257 case BTRFS_DIR_INDEX_KEY
:
1258 ret
= process_dir_item(root
, eb
, i
, &key
, active_node
);
1260 case BTRFS_INODE_REF_KEY
:
1261 ret
= process_inode_ref(eb
, i
, &key
, active_node
);
1263 case BTRFS_INODE_EXTREF_KEY
:
1264 ret
= process_inode_extref(eb
, i
, &key
, active_node
);
1266 case BTRFS_INODE_ITEM_KEY
:
1267 ret
= process_inode_item(eb
, i
, &key
, active_node
);
1269 case BTRFS_EXTENT_DATA_KEY
:
1270 ret
= process_file_extent(root
, eb
, i
, &key
,
1282 static void reada_walk_down(struct btrfs_root
*root
,
1283 struct extent_buffer
*node
, int slot
)
1293 level
= btrfs_header_level(node
);
1297 nritems
= btrfs_header_nritems(node
);
1298 blocksize
= btrfs_level_size(root
, level
- 1);
1299 for (i
= slot
; i
< nritems
; i
++) {
1300 bytenr
= btrfs_node_blockptr(node
, i
);
1301 ptr_gen
= btrfs_node_ptr_generation(node
, i
);
1302 ret
= readahead_tree_block(root
, bytenr
, blocksize
, ptr_gen
);
1308 static int walk_down_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1309 struct walk_control
*wc
, int *level
)
1313 struct extent_buffer
*next
;
1314 struct extent_buffer
*cur
;
1319 WARN_ON(*level
< 0);
1320 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1321 ret
= btrfs_lookup_extent_info(NULL
, root
,
1322 path
->nodes
[*level
]->start
,
1323 *level
, 1, &refs
, NULL
);
1330 ret
= enter_shared_node(root
, path
->nodes
[*level
]->start
,
1338 while (*level
>= 0) {
1339 WARN_ON(*level
< 0);
1340 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1341 cur
= path
->nodes
[*level
];
1343 if (btrfs_header_level(cur
) != *level
)
1346 if (path
->slots
[*level
] >= btrfs_header_nritems(cur
))
1349 ret
= process_one_leaf(root
, cur
, wc
);
1352 bytenr
= btrfs_node_blockptr(cur
, path
->slots
[*level
]);
1353 ptr_gen
= btrfs_node_ptr_generation(cur
, path
->slots
[*level
]);
1354 blocksize
= btrfs_level_size(root
, *level
- 1);
1355 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
, *level
- 1,
1361 ret
= enter_shared_node(root
, bytenr
, refs
,
1364 path
->slots
[*level
]++;
1369 next
= btrfs_find_tree_block(root
, bytenr
, blocksize
);
1370 if (!next
|| !btrfs_buffer_uptodate(next
, ptr_gen
)) {
1371 free_extent_buffer(next
);
1372 reada_walk_down(root
, cur
, path
->slots
[*level
]);
1373 next
= read_tree_block(root
, bytenr
, blocksize
,
1381 *level
= *level
- 1;
1382 free_extent_buffer(path
->nodes
[*level
]);
1383 path
->nodes
[*level
] = next
;
1384 path
->slots
[*level
] = 0;
1387 path
->slots
[*level
] = btrfs_header_nritems(path
->nodes
[*level
]);
1391 static int walk_up_tree(struct btrfs_root
*root
, struct btrfs_path
*path
,
1392 struct walk_control
*wc
, int *level
)
1395 struct extent_buffer
*leaf
;
1397 for (i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
1398 leaf
= path
->nodes
[i
];
1399 if (path
->slots
[i
] + 1 < btrfs_header_nritems(leaf
)) {
1404 free_extent_buffer(path
->nodes
[*level
]);
1405 path
->nodes
[*level
] = NULL
;
1406 BUG_ON(*level
> wc
->active_node
);
1407 if (*level
== wc
->active_node
)
1408 leave_shared_node(root
, wc
, *level
);
1415 static int check_root_dir(struct inode_record
*rec
)
1417 struct inode_backref
*backref
;
1420 if (!rec
->found_inode_item
|| rec
->errors
)
1422 if (rec
->nlink
!= 1 || rec
->found_link
!= 0)
1424 if (list_empty(&rec
->backrefs
))
1426 backref
= list_entry(rec
->backrefs
.next
, struct inode_backref
, list
);
1427 if (!backref
->found_inode_ref
)
1429 if (backref
->index
!= 0 || backref
->namelen
!= 2 ||
1430 memcmp(backref
->name
, "..", 2))
1432 if (backref
->found_dir_index
|| backref
->found_dir_item
)
1439 static int repair_inode_isize(struct btrfs_trans_handle
*trans
,
1440 struct btrfs_root
*root
, struct btrfs_path
*path
,
1441 struct inode_record
*rec
)
1443 struct btrfs_inode_item
*ei
;
1444 struct btrfs_key key
;
1447 key
.objectid
= rec
->ino
;
1448 key
.type
= BTRFS_INODE_ITEM_KEY
;
1449 key
.offset
= (u64
)-1;
1451 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
1455 if (!path
->slots
[0]) {
1462 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
1463 if (key
.objectid
!= rec
->ino
) {
1468 ei
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
1469 struct btrfs_inode_item
);
1470 btrfs_set_inode_size(path
->nodes
[0], ei
, rec
->found_size
);
1471 btrfs_mark_buffer_dirty(path
->nodes
[0]);
1472 rec
->errors
&= ~I_ERR_DIR_ISIZE_WRONG
;
1473 printf("reset isize for dir %Lu root %Lu\n", rec
->ino
,
1474 root
->root_key
.objectid
);
1476 btrfs_release_path(path
);
1480 static int repair_inode_orphan_item(struct btrfs_trans_handle
*trans
,
1481 struct btrfs_root
*root
,
1482 struct btrfs_path
*path
,
1483 struct inode_record
*rec
)
1485 struct btrfs_key key
;
1488 key
.objectid
= BTRFS_ORPHAN_OBJECTID
;
1489 key
.type
= BTRFS_ORPHAN_ITEM_KEY
;
1490 key
.offset
= rec
->ino
;
1492 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, 0);
1493 btrfs_release_path(path
);
1495 rec
->errors
&= ~I_ERR_NO_ORPHAN_ITEM
;
1499 static int try_repair_inode(struct btrfs_root
*root
, struct inode_record
*rec
)
1501 struct btrfs_trans_handle
*trans
;
1502 struct btrfs_path
*path
;
1505 /* So far we just fix dir isize wrong */
1506 if (!(rec
->errors
& (I_ERR_DIR_ISIZE_WRONG
| I_ERR_NO_ORPHAN_ITEM
)))
1509 path
= btrfs_alloc_path();
1513 trans
= btrfs_start_transaction(root
, 1);
1514 if (IS_ERR(trans
)) {
1515 btrfs_free_path(path
);
1516 return PTR_ERR(trans
);
1519 if (rec
->errors
& I_ERR_DIR_ISIZE_WRONG
)
1520 ret
= repair_inode_isize(trans
, root
, path
, rec
);
1521 if (!ret
&& rec
->errors
& I_ERR_NO_ORPHAN_ITEM
)
1522 ret
= repair_inode_orphan_item(trans
, root
, path
, rec
);
1523 btrfs_commit_transaction(trans
, root
);
1524 btrfs_free_path(path
);
1528 static int check_inode_recs(struct btrfs_root
*root
,
1529 struct cache_tree
*inode_cache
)
1531 struct cache_extent
*cache
;
1532 struct ptr_node
*node
;
1533 struct inode_record
*rec
;
1534 struct inode_backref
*backref
;
1537 u64 root_dirid
= btrfs_root_dirid(&root
->root_item
);
1539 if (btrfs_root_refs(&root
->root_item
) == 0) {
1540 if (!cache_tree_empty(inode_cache
))
1541 fprintf(stderr
, "warning line %d\n", __LINE__
);
1545 rec
= get_inode_rec(inode_cache
, root_dirid
, 0);
1547 ret
= check_root_dir(rec
);
1549 fprintf(stderr
, "root %llu root dir %llu error\n",
1550 (unsigned long long)root
->root_key
.objectid
,
1551 (unsigned long long)root_dirid
);
1555 fprintf(stderr
, "root %llu root dir %llu not found\n",
1556 (unsigned long long)root
->root_key
.objectid
,
1557 (unsigned long long)root_dirid
);
1561 cache
= search_cache_extent(inode_cache
, 0);
1564 node
= container_of(cache
, struct ptr_node
, cache
);
1566 remove_cache_extent(inode_cache
, &node
->cache
);
1568 if (rec
->ino
== root_dirid
||
1569 rec
->ino
== BTRFS_ORPHAN_OBJECTID
) {
1570 free_inode_rec(rec
);
1574 if (rec
->errors
& I_ERR_NO_ORPHAN_ITEM
) {
1575 ret
= check_orphan_item(root
, rec
->ino
);
1577 rec
->errors
&= ~I_ERR_NO_ORPHAN_ITEM
;
1578 if (can_free_inode_rec(rec
)) {
1579 free_inode_rec(rec
);
1585 ret
= try_repair_inode(root
, rec
);
1586 if (ret
== 0 && can_free_inode_rec(rec
)) {
1587 free_inode_rec(rec
);
1594 if (!rec
->found_inode_item
)
1595 rec
->errors
|= I_ERR_NO_INODE_ITEM
;
1596 if (rec
->found_link
!= rec
->nlink
)
1597 rec
->errors
|= I_ERR_LINK_COUNT_WRONG
;
1598 fprintf(stderr
, "root %llu inode %llu errors %x",
1599 (unsigned long long) root
->root_key
.objectid
,
1600 (unsigned long long) rec
->ino
, rec
->errors
);
1601 print_inode_error(rec
->errors
);
1602 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1603 if (!backref
->found_dir_item
)
1604 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1605 if (!backref
->found_dir_index
)
1606 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1607 if (!backref
->found_inode_ref
)
1608 backref
->errors
|= REF_ERR_NO_INODE_REF
;
1609 fprintf(stderr
, "\tunresolved ref dir %llu index %llu"
1610 " namelen %u name %s filetype %d errors %x",
1611 (unsigned long long)backref
->dir
,
1612 (unsigned long long)backref
->index
,
1613 backref
->namelen
, backref
->name
,
1614 backref
->filetype
, backref
->errors
);
1615 print_ref_error(backref
->errors
);
1617 free_inode_rec(rec
);
1619 return (error
> 0) ? -1 : 0;
1622 static struct root_record
*get_root_rec(struct cache_tree
*root_cache
,
1625 struct cache_extent
*cache
;
1626 struct root_record
*rec
= NULL
;
1629 cache
= lookup_cache_extent(root_cache
, objectid
, 1);
1631 rec
= container_of(cache
, struct root_record
, cache
);
1633 rec
= calloc(1, sizeof(*rec
));
1634 rec
->objectid
= objectid
;
1635 INIT_LIST_HEAD(&rec
->backrefs
);
1636 rec
->cache
.start
= objectid
;
1637 rec
->cache
.size
= 1;
1639 ret
= insert_cache_extent(root_cache
, &rec
->cache
);
1645 static struct root_backref
*get_root_backref(struct root_record
*rec
,
1646 u64 ref_root
, u64 dir
, u64 index
,
1647 const char *name
, int namelen
)
1649 struct root_backref
*backref
;
1651 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1652 if (backref
->ref_root
!= ref_root
|| backref
->dir
!= dir
||
1653 backref
->namelen
!= namelen
)
1655 if (memcmp(name
, backref
->name
, namelen
))
1660 backref
= malloc(sizeof(*backref
) + namelen
+ 1);
1661 memset(backref
, 0, sizeof(*backref
));
1662 backref
->ref_root
= ref_root
;
1664 backref
->index
= index
;
1665 backref
->namelen
= namelen
;
1666 memcpy(backref
->name
, name
, namelen
);
1667 backref
->name
[namelen
] = '\0';
1668 list_add_tail(&backref
->list
, &rec
->backrefs
);
1672 static void free_root_record(struct cache_extent
*cache
)
1674 struct root_record
*rec
;
1675 struct root_backref
*backref
;
1677 rec
= container_of(cache
, struct root_record
, cache
);
1678 while (!list_empty(&rec
->backrefs
)) {
1679 backref
= list_entry(rec
->backrefs
.next
,
1680 struct root_backref
, list
);
1681 list_del(&backref
->list
);
1688 FREE_EXTENT_CACHE_BASED_TREE(root_recs
, free_root_record
);
1690 static int add_root_backref(struct cache_tree
*root_cache
,
1691 u64 root_id
, u64 ref_root
, u64 dir
, u64 index
,
1692 const char *name
, int namelen
,
1693 int item_type
, int errors
)
1695 struct root_record
*rec
;
1696 struct root_backref
*backref
;
1698 rec
= get_root_rec(root_cache
, root_id
);
1699 backref
= get_root_backref(rec
, ref_root
, dir
, index
, name
, namelen
);
1701 backref
->errors
|= errors
;
1703 if (item_type
!= BTRFS_DIR_ITEM_KEY
) {
1704 if (backref
->found_dir_index
|| backref
->found_back_ref
||
1705 backref
->found_forward_ref
) {
1706 if (backref
->index
!= index
)
1707 backref
->errors
|= REF_ERR_INDEX_UNMATCH
;
1709 backref
->index
= index
;
1713 if (item_type
== BTRFS_DIR_ITEM_KEY
) {
1714 if (backref
->found_forward_ref
)
1716 backref
->found_dir_item
= 1;
1717 } else if (item_type
== BTRFS_DIR_INDEX_KEY
) {
1718 backref
->found_dir_index
= 1;
1719 } else if (item_type
== BTRFS_ROOT_REF_KEY
) {
1720 if (backref
->found_forward_ref
)
1721 backref
->errors
|= REF_ERR_DUP_ROOT_REF
;
1722 else if (backref
->found_dir_item
)
1724 backref
->found_forward_ref
= 1;
1725 } else if (item_type
== BTRFS_ROOT_BACKREF_KEY
) {
1726 if (backref
->found_back_ref
)
1727 backref
->errors
|= REF_ERR_DUP_ROOT_BACKREF
;
1728 backref
->found_back_ref
= 1;
1733 if (backref
->found_forward_ref
&& backref
->found_dir_item
)
1734 backref
->reachable
= 1;
1738 static int merge_root_recs(struct btrfs_root
*root
,
1739 struct cache_tree
*src_cache
,
1740 struct cache_tree
*dst_cache
)
1742 struct cache_extent
*cache
;
1743 struct ptr_node
*node
;
1744 struct inode_record
*rec
;
1745 struct inode_backref
*backref
;
1747 if (root
->root_key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
1748 free_inode_recs_tree(src_cache
);
1753 cache
= search_cache_extent(src_cache
, 0);
1756 node
= container_of(cache
, struct ptr_node
, cache
);
1758 remove_cache_extent(src_cache
, &node
->cache
);
1761 if (!is_child_root(root
, root
->objectid
, rec
->ino
))
1764 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1765 BUG_ON(backref
->found_inode_ref
);
1766 if (backref
->found_dir_item
)
1767 add_root_backref(dst_cache
, rec
->ino
,
1768 root
->root_key
.objectid
, backref
->dir
,
1769 backref
->index
, backref
->name
,
1770 backref
->namelen
, BTRFS_DIR_ITEM_KEY
,
1772 if (backref
->found_dir_index
)
1773 add_root_backref(dst_cache
, rec
->ino
,
1774 root
->root_key
.objectid
, backref
->dir
,
1775 backref
->index
, backref
->name
,
1776 backref
->namelen
, BTRFS_DIR_INDEX_KEY
,
1780 free_inode_rec(rec
);
1785 static int check_root_refs(struct btrfs_root
*root
,
1786 struct cache_tree
*root_cache
)
1788 struct root_record
*rec
;
1789 struct root_record
*ref_root
;
1790 struct root_backref
*backref
;
1791 struct cache_extent
*cache
;
1797 rec
= get_root_rec(root_cache
, BTRFS_FS_TREE_OBJECTID
);
1800 /* fixme: this can not detect circular references */
1803 cache
= search_cache_extent(root_cache
, 0);
1807 rec
= container_of(cache
, struct root_record
, cache
);
1808 cache
= next_cache_extent(cache
);
1810 if (rec
->found_ref
== 0)
1813 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1814 if (!backref
->reachable
)
1817 ref_root
= get_root_rec(root_cache
,
1819 if (ref_root
->found_ref
> 0)
1822 backref
->reachable
= 0;
1824 if (rec
->found_ref
== 0)
1830 cache
= search_cache_extent(root_cache
, 0);
1834 rec
= container_of(cache
, struct root_record
, cache
);
1835 cache
= next_cache_extent(cache
);
1837 if (rec
->found_ref
== 0 &&
1838 rec
->objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
1839 rec
->objectid
<= BTRFS_LAST_FREE_OBJECTID
) {
1840 ret
= check_orphan_item(root
->fs_info
->tree_root
,
1846 * If we don't have a root item then we likely just have
1847 * a dir item in a snapshot for this root but no actual
1848 * ref key or anything so it's meaningless.
1850 if (!rec
->found_root_item
)
1853 fprintf(stderr
, "fs tree %llu not referenced\n",
1854 (unsigned long long)rec
->objectid
);
1858 if (rec
->found_ref
> 0 && !rec
->found_root_item
)
1860 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1861 if (!backref
->found_dir_item
)
1862 backref
->errors
|= REF_ERR_NO_DIR_ITEM
;
1863 if (!backref
->found_dir_index
)
1864 backref
->errors
|= REF_ERR_NO_DIR_INDEX
;
1865 if (!backref
->found_back_ref
)
1866 backref
->errors
|= REF_ERR_NO_ROOT_BACKREF
;
1867 if (!backref
->found_forward_ref
)
1868 backref
->errors
|= REF_ERR_NO_ROOT_REF
;
1869 if (backref
->reachable
&& backref
->errors
)
1876 fprintf(stderr
, "fs tree %llu refs %u %s\n",
1877 (unsigned long long)rec
->objectid
, rec
->found_ref
,
1878 rec
->found_root_item
? "" : "not found");
1880 list_for_each_entry(backref
, &rec
->backrefs
, list
) {
1881 if (!backref
->reachable
)
1883 if (!backref
->errors
&& rec
->found_root_item
)
1885 fprintf(stderr
, "\tunresolved ref root %llu dir %llu"
1886 " index %llu namelen %u name %s errors %x\n",
1887 (unsigned long long)backref
->ref_root
,
1888 (unsigned long long)backref
->dir
,
1889 (unsigned long long)backref
->index
,
1890 backref
->namelen
, backref
->name
,
1892 print_ref_error(backref
->errors
);
1895 return errors
> 0 ? 1 : 0;
1898 static int process_root_ref(struct extent_buffer
*eb
, int slot
,
1899 struct btrfs_key
*key
,
1900 struct cache_tree
*root_cache
)
1906 struct btrfs_root_ref
*ref
;
1907 char namebuf
[BTRFS_NAME_LEN
];
1910 ref
= btrfs_item_ptr(eb
, slot
, struct btrfs_root_ref
);
1912 dirid
= btrfs_root_ref_dirid(eb
, ref
);
1913 index
= btrfs_root_ref_sequence(eb
, ref
);
1914 name_len
= btrfs_root_ref_name_len(eb
, ref
);
1916 if (name_len
<= BTRFS_NAME_LEN
) {
1920 len
= BTRFS_NAME_LEN
;
1921 error
= REF_ERR_NAME_TOO_LONG
;
1923 read_extent_buffer(eb
, namebuf
, (unsigned long)(ref
+ 1), len
);
1925 if (key
->type
== BTRFS_ROOT_REF_KEY
) {
1926 add_root_backref(root_cache
, key
->offset
, key
->objectid
, dirid
,
1927 index
, namebuf
, len
, key
->type
, error
);
1929 add_root_backref(root_cache
, key
->objectid
, key
->offset
, dirid
,
1930 index
, namebuf
, len
, key
->type
, error
);
1935 static int check_fs_root(struct btrfs_root
*root
,
1936 struct cache_tree
*root_cache
,
1937 struct walk_control
*wc
)
1942 struct btrfs_path path
;
1943 struct shared_node root_node
;
1944 struct root_record
*rec
;
1945 struct btrfs_root_item
*root_item
= &root
->root_item
;
1947 if (root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
1948 rec
= get_root_rec(root_cache
, root
->root_key
.objectid
);
1949 if (btrfs_root_refs(root_item
) > 0)
1950 rec
->found_root_item
= 1;
1953 btrfs_init_path(&path
);
1954 memset(&root_node
, 0, sizeof(root_node
));
1955 cache_tree_init(&root_node
.root_cache
);
1956 cache_tree_init(&root_node
.inode_cache
);
1958 level
= btrfs_header_level(root
->node
);
1959 memset(wc
->nodes
, 0, sizeof(wc
->nodes
));
1960 wc
->nodes
[level
] = &root_node
;
1961 wc
->active_node
= level
;
1962 wc
->root_level
= level
;
1964 if (btrfs_root_refs(root_item
) > 0 ||
1965 btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
1966 path
.nodes
[level
] = root
->node
;
1967 extent_buffer_get(root
->node
);
1968 path
.slots
[level
] = 0;
1970 struct btrfs_key key
;
1971 struct btrfs_disk_key found_key
;
1973 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
1974 level
= root_item
->drop_level
;
1975 path
.lowest_level
= level
;
1976 wret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
1978 btrfs_node_key(path
.nodes
[level
], &found_key
,
1980 WARN_ON(memcmp(&found_key
, &root_item
->drop_progress
,
1981 sizeof(found_key
)));
1985 wret
= walk_down_tree(root
, &path
, wc
, &level
);
1991 wret
= walk_up_tree(root
, &path
, wc
, &level
);
1997 btrfs_release_path(&path
);
1999 merge_root_recs(root
, &root_node
.root_cache
, root_cache
);
2001 if (root_node
.current
) {
2002 root_node
.current
->checked
= 1;
2003 maybe_free_inode_rec(&root_node
.inode_cache
,
2007 ret
= check_inode_recs(root
, &root_node
.inode_cache
);
2011 static int fs_root_objectid(u64 objectid
)
2013 if (objectid
== BTRFS_FS_TREE_OBJECTID
||
2014 objectid
== BTRFS_TREE_RELOC_OBJECTID
||
2015 objectid
== BTRFS_DATA_RELOC_TREE_OBJECTID
||
2016 (objectid
>= BTRFS_FIRST_FREE_OBJECTID
&&
2017 objectid
<= BTRFS_LAST_FREE_OBJECTID
))
2022 static int check_fs_roots(struct btrfs_root
*root
,
2023 struct cache_tree
*root_cache
)
2025 struct btrfs_path path
;
2026 struct btrfs_key key
;
2027 struct walk_control wc
;
2028 struct extent_buffer
*leaf
;
2029 struct btrfs_root
*tmp_root
;
2030 struct btrfs_root
*tree_root
= root
->fs_info
->tree_root
;
2035 * Just in case we made any changes to the extent tree that weren't
2036 * reflected into the free space cache yet.
2039 reset_cached_block_groups(root
->fs_info
);
2040 memset(&wc
, 0, sizeof(wc
));
2041 cache_tree_init(&wc
.shared
);
2042 btrfs_init_path(&path
);
2046 key
.type
= BTRFS_ROOT_ITEM_KEY
;
2047 ret
= btrfs_search_slot(NULL
, tree_root
, &key
, &path
, 0, 0);
2050 leaf
= path
.nodes
[0];
2051 if (path
.slots
[0] >= btrfs_header_nritems(leaf
)) {
2052 ret
= btrfs_next_leaf(tree_root
, &path
);
2055 leaf
= path
.nodes
[0];
2057 btrfs_item_key_to_cpu(leaf
, &key
, path
.slots
[0]);
2058 if (key
.type
== BTRFS_ROOT_ITEM_KEY
&&
2059 fs_root_objectid(key
.objectid
)) {
2060 key
.offset
= (u64
)-1;
2061 tmp_root
= btrfs_read_fs_root(root
->fs_info
, &key
);
2062 if (IS_ERR(tmp_root
)) {
2066 ret
= check_fs_root(tmp_root
, root_cache
, &wc
);
2069 } else if (key
.type
== BTRFS_ROOT_REF_KEY
||
2070 key
.type
== BTRFS_ROOT_BACKREF_KEY
) {
2071 process_root_ref(leaf
, path
.slots
[0], &key
,
2077 btrfs_release_path(&path
);
2079 if (!cache_tree_empty(&wc
.shared
))
2080 fprintf(stderr
, "warning line %d\n", __LINE__
);
2085 static int all_backpointers_checked(struct extent_record
*rec
, int print_errs
)
2087 struct list_head
*cur
= rec
->backrefs
.next
;
2088 struct extent_backref
*back
;
2089 struct tree_backref
*tback
;
2090 struct data_backref
*dback
;
2094 while(cur
!= &rec
->backrefs
) {
2095 back
= list_entry(cur
, struct extent_backref
, list
);
2097 if (!back
->found_extent_tree
) {
2101 if (back
->is_data
) {
2102 dback
= (struct data_backref
*)back
;
2103 fprintf(stderr
, "Backref %llu %s %llu"
2104 " owner %llu offset %llu num_refs %lu"
2105 " not found in extent tree\n",
2106 (unsigned long long)rec
->start
,
2107 back
->full_backref
?
2109 back
->full_backref
?
2110 (unsigned long long)dback
->parent
:
2111 (unsigned long long)dback
->root
,
2112 (unsigned long long)dback
->owner
,
2113 (unsigned long long)dback
->offset
,
2114 (unsigned long)dback
->num_refs
);
2116 tback
= (struct tree_backref
*)back
;
2117 fprintf(stderr
, "Backref %llu parent %llu"
2118 " root %llu not found in extent tree\n",
2119 (unsigned long long)rec
->start
,
2120 (unsigned long long)tback
->parent
,
2121 (unsigned long long)tback
->root
);
2124 if (!back
->is_data
&& !back
->found_ref
) {
2128 tback
= (struct tree_backref
*)back
;
2129 fprintf(stderr
, "Backref %llu %s %llu not referenced back %p\n",
2130 (unsigned long long)rec
->start
,
2131 back
->full_backref
? "parent" : "root",
2132 back
->full_backref
?
2133 (unsigned long long)tback
->parent
:
2134 (unsigned long long)tback
->root
, back
);
2136 if (back
->is_data
) {
2137 dback
= (struct data_backref
*)back
;
2138 if (dback
->found_ref
!= dback
->num_refs
) {
2142 fprintf(stderr
, "Incorrect local backref count"
2143 " on %llu %s %llu owner %llu"
2144 " offset %llu found %u wanted %u back %p\n",
2145 (unsigned long long)rec
->start
,
2146 back
->full_backref
?
2148 back
->full_backref
?
2149 (unsigned long long)dback
->parent
:
2150 (unsigned long long)dback
->root
,
2151 (unsigned long long)dback
->owner
,
2152 (unsigned long long)dback
->offset
,
2153 dback
->found_ref
, dback
->num_refs
, back
);
2155 if (dback
->disk_bytenr
!= rec
->start
) {
2159 fprintf(stderr
, "Backref disk bytenr does not"
2160 " match extent record, bytenr=%llu, "
2161 "ref bytenr=%llu\n",
2162 (unsigned long long)rec
->start
,
2163 (unsigned long long)dback
->disk_bytenr
);
2166 if (dback
->bytes
!= rec
->nr
) {
2170 fprintf(stderr
, "Backref bytes do not match "
2171 "extent backref, bytenr=%llu, ref "
2172 "bytes=%llu, backref bytes=%llu\n",
2173 (unsigned long long)rec
->start
,
2174 (unsigned long long)rec
->nr
,
2175 (unsigned long long)dback
->bytes
);
2178 if (!back
->is_data
) {
2181 dback
= (struct data_backref
*)back
;
2182 found
+= dback
->found_ref
;
2185 if (found
!= rec
->refs
) {
2189 fprintf(stderr
, "Incorrect global backref count "
2190 "on %llu found %llu wanted %llu\n",
2191 (unsigned long long)rec
->start
,
2192 (unsigned long long)found
,
2193 (unsigned long long)rec
->refs
);
2199 static int free_all_extent_backrefs(struct extent_record
*rec
)
2201 struct extent_backref
*back
;
2202 struct list_head
*cur
;
2203 while (!list_empty(&rec
->backrefs
)) {
2204 cur
= rec
->backrefs
.next
;
2205 back
= list_entry(cur
, struct extent_backref
, list
);
2212 static void free_extent_record_cache(struct btrfs_fs_info
*fs_info
,
2213 struct cache_tree
*extent_cache
)
2215 struct cache_extent
*cache
;
2216 struct extent_record
*rec
;
2219 cache
= first_cache_extent(extent_cache
);
2222 rec
= container_of(cache
, struct extent_record
, cache
);
2223 btrfs_unpin_extent(fs_info
, rec
->start
, rec
->max_size
);
2224 remove_cache_extent(extent_cache
, cache
);
2225 free_all_extent_backrefs(rec
);
2230 static int maybe_free_extent_rec(struct cache_tree
*extent_cache
,
2231 struct extent_record
*rec
)
2233 if (rec
->content_checked
&& rec
->owner_ref_checked
&&
2234 rec
->extent_item_refs
== rec
->refs
&& rec
->refs
> 0 &&
2235 rec
->num_duplicates
== 0 && !all_backpointers_checked(rec
, 0)) {
2236 remove_cache_extent(extent_cache
, &rec
->cache
);
2237 free_all_extent_backrefs(rec
);
2238 list_del_init(&rec
->list
);
2244 static int check_owner_ref(struct btrfs_root
*root
,
2245 struct extent_record
*rec
,
2246 struct extent_buffer
*buf
)
2248 struct extent_backref
*node
;
2249 struct tree_backref
*back
;
2250 struct btrfs_root
*ref_root
;
2251 struct btrfs_key key
;
2252 struct btrfs_path path
;
2253 struct extent_buffer
*parent
;
2258 list_for_each_entry(node
, &rec
->backrefs
, list
) {
2261 if (!node
->found_ref
)
2263 if (node
->full_backref
)
2265 back
= (struct tree_backref
*)node
;
2266 if (btrfs_header_owner(buf
) == back
->root
)
2269 BUG_ON(rec
->is_root
);
2271 /* try to find the block by search corresponding fs tree */
2272 key
.objectid
= btrfs_header_owner(buf
);
2273 key
.type
= BTRFS_ROOT_ITEM_KEY
;
2274 key
.offset
= (u64
)-1;
2276 ref_root
= btrfs_read_fs_root(root
->fs_info
, &key
);
2277 if (IS_ERR(ref_root
))
2280 level
= btrfs_header_level(buf
);
2282 btrfs_item_key_to_cpu(buf
, &key
, 0);
2284 btrfs_node_key_to_cpu(buf
, &key
, 0);
2286 btrfs_init_path(&path
);
2287 path
.lowest_level
= level
+ 1;
2288 ret
= btrfs_search_slot(NULL
, ref_root
, &key
, &path
, 0, 0);
2292 parent
= path
.nodes
[level
+ 1];
2293 if (parent
&& buf
->start
== btrfs_node_blockptr(parent
,
2294 path
.slots
[level
+ 1]))
2297 btrfs_release_path(&path
);
2298 return found
? 0 : 1;
2301 static int is_extent_tree_record(struct extent_record
*rec
)
2303 struct list_head
*cur
= rec
->backrefs
.next
;
2304 struct extent_backref
*node
;
2305 struct tree_backref
*back
;
2308 while(cur
!= &rec
->backrefs
) {
2309 node
= list_entry(cur
, struct extent_backref
, list
);
2313 back
= (struct tree_backref
*)node
;
2314 if (node
->full_backref
)
2316 if (back
->root
== BTRFS_EXTENT_TREE_OBJECTID
)
2323 static int record_bad_block_io(struct btrfs_fs_info
*info
,
2324 struct cache_tree
*extent_cache
,
2327 struct extent_record
*rec
;
2328 struct cache_extent
*cache
;
2329 struct btrfs_key key
;
2331 cache
= lookup_cache_extent(extent_cache
, start
, len
);
2335 rec
= container_of(cache
, struct extent_record
, cache
);
2336 if (!is_extent_tree_record(rec
))
2339 btrfs_disk_key_to_cpu(&key
, &rec
->parent_key
);
2340 return btrfs_add_corrupt_extent_record(info
, &key
, start
, len
, 0);
2343 static int swap_values(struct btrfs_root
*root
, struct btrfs_path
*path
,
2344 struct extent_buffer
*buf
, int slot
)
2346 if (btrfs_header_level(buf
)) {
2347 struct btrfs_key_ptr ptr1
, ptr2
;
2349 read_extent_buffer(buf
, &ptr1
, btrfs_node_key_ptr_offset(slot
),
2350 sizeof(struct btrfs_key_ptr
));
2351 read_extent_buffer(buf
, &ptr2
,
2352 btrfs_node_key_ptr_offset(slot
+ 1),
2353 sizeof(struct btrfs_key_ptr
));
2354 write_extent_buffer(buf
, &ptr1
,
2355 btrfs_node_key_ptr_offset(slot
+ 1),
2356 sizeof(struct btrfs_key_ptr
));
2357 write_extent_buffer(buf
, &ptr2
,
2358 btrfs_node_key_ptr_offset(slot
),
2359 sizeof(struct btrfs_key_ptr
));
2361 struct btrfs_disk_key key
;
2362 btrfs_node_key(buf
, &key
, 0);
2363 btrfs_fixup_low_keys(root
, path
, &key
,
2364 btrfs_header_level(buf
) + 1);
2367 struct btrfs_item
*item1
, *item2
;
2368 struct btrfs_key k1
, k2
;
2369 char *item1_data
, *item2_data
;
2370 u32 item1_offset
, item2_offset
, item1_size
, item2_size
;
2372 item1
= btrfs_item_nr(slot
);
2373 item2
= btrfs_item_nr(slot
+ 1);
2374 btrfs_item_key_to_cpu(buf
, &k1
, slot
);
2375 btrfs_item_key_to_cpu(buf
, &k2
, slot
+ 1);
2376 item1_offset
= btrfs_item_offset(buf
, item1
);
2377 item2_offset
= btrfs_item_offset(buf
, item2
);
2378 item1_size
= btrfs_item_size(buf
, item1
);
2379 item2_size
= btrfs_item_size(buf
, item2
);
2381 item1_data
= malloc(item1_size
);
2384 item2_data
= malloc(item2_size
);
2390 read_extent_buffer(buf
, item1_data
, item1_offset
, item1_size
);
2391 read_extent_buffer(buf
, item2_data
, item2_offset
, item2_size
);
2393 write_extent_buffer(buf
, item1_data
, item2_offset
, item2_size
);
2394 write_extent_buffer(buf
, item2_data
, item1_offset
, item1_size
);
2398 btrfs_set_item_offset(buf
, item1
, item2_offset
);
2399 btrfs_set_item_offset(buf
, item2
, item1_offset
);
2400 btrfs_set_item_size(buf
, item1
, item2_size
);
2401 btrfs_set_item_size(buf
, item2
, item1_size
);
2403 path
->slots
[0] = slot
;
2404 btrfs_set_item_key_unsafe(root
, path
, &k2
);
2405 path
->slots
[0] = slot
+ 1;
2406 btrfs_set_item_key_unsafe(root
, path
, &k1
);
2412 * Attempt to fix basic block failures. Currently we only handle bad key
2413 * orders, we will cycle through the keys and swap them if necessary.
2415 static int try_to_fix_bad_block(struct btrfs_trans_handle
*trans
,
2416 struct btrfs_root
*root
,
2417 struct extent_buffer
*buf
,
2418 struct btrfs_disk_key
*parent_key
,
2419 enum btrfs_tree_block_status status
)
2421 struct btrfs_path
*path
;
2422 struct btrfs_key k1
, k2
;
2426 if (status
!= BTRFS_TREE_BLOCK_BAD_KEY_ORDER
)
2429 k1
.objectid
= btrfs_header_owner(buf
);
2430 k1
.type
= BTRFS_ROOT_ITEM_KEY
;
2431 k1
.offset
= (u64
)-1;
2433 root
= btrfs_read_fs_root(root
->fs_info
, &k1
);
2437 path
= btrfs_alloc_path();
2441 path
->lowest_level
= btrfs_header_level(buf
);
2442 path
->skip_check_block
= 1;
2443 if (btrfs_header_level(buf
))
2444 btrfs_node_key_to_cpu(buf
, &k1
, 0);
2446 btrfs_item_key_to_cpu(buf
, &k1
, 0);
2448 ret
= btrfs_search_slot(trans
, root
, &k1
, path
, 0, 1);
2450 btrfs_free_path(path
);
2454 buf
= path
->nodes
[0];
2455 for (i
= 0; i
< btrfs_header_nritems(buf
) - 1; i
++) {
2456 if (btrfs_header_level(buf
)) {
2457 btrfs_node_key_to_cpu(buf
, &k1
, i
);
2458 btrfs_node_key_to_cpu(buf
, &k2
, i
+ 1);
2460 btrfs_item_key_to_cpu(buf
, &k1
, i
);
2461 btrfs_item_key_to_cpu(buf
, &k2
, i
+ 1);
2463 if (btrfs_comp_cpu_keys(&k1
, &k2
) < 0)
2465 ret
= swap_values(root
, path
, buf
, i
);
2468 btrfs_mark_buffer_dirty(buf
);
2472 btrfs_free_path(path
);
2476 static int check_block(struct btrfs_trans_handle
*trans
,
2477 struct btrfs_root
*root
,
2478 struct cache_tree
*extent_cache
,
2479 struct extent_buffer
*buf
, u64 flags
)
2481 struct extent_record
*rec
;
2482 struct cache_extent
*cache
;
2483 struct btrfs_key key
;
2484 enum btrfs_tree_block_status status
;
2488 cache
= lookup_cache_extent(extent_cache
, buf
->start
, buf
->len
);
2491 rec
= container_of(cache
, struct extent_record
, cache
);
2492 rec
->generation
= btrfs_header_generation(buf
);
2494 level
= btrfs_header_level(buf
);
2495 if (btrfs_header_nritems(buf
) > 0) {
2498 btrfs_item_key_to_cpu(buf
, &key
, 0);
2500 btrfs_node_key_to_cpu(buf
, &key
, 0);
2502 rec
->info_objectid
= key
.objectid
;
2504 rec
->info_level
= level
;
2506 if (btrfs_is_leaf(buf
))
2507 status
= btrfs_check_leaf(root
, &rec
->parent_key
, buf
);
2509 status
= btrfs_check_node(root
, &rec
->parent_key
, buf
);
2511 if (status
!= BTRFS_TREE_BLOCK_CLEAN
) {
2513 status
= try_to_fix_bad_block(trans
, root
, buf
,
2516 if (status
!= BTRFS_TREE_BLOCK_CLEAN
) {
2518 fprintf(stderr
, "bad block %llu\n",
2519 (unsigned long long)buf
->start
);
2522 * Signal to callers we need to start the scan over
2523 * again since we'll have cow'ed blocks.
2528 rec
->content_checked
= 1;
2529 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
)
2530 rec
->owner_ref_checked
= 1;
2532 ret
= check_owner_ref(root
, rec
, buf
);
2534 rec
->owner_ref_checked
= 1;
2538 maybe_free_extent_rec(extent_cache
, rec
);
2542 static struct tree_backref
*find_tree_backref(struct extent_record
*rec
,
2543 u64 parent
, u64 root
)
2545 struct list_head
*cur
= rec
->backrefs
.next
;
2546 struct extent_backref
*node
;
2547 struct tree_backref
*back
;
2549 while(cur
!= &rec
->backrefs
) {
2550 node
= list_entry(cur
, struct extent_backref
, list
);
2554 back
= (struct tree_backref
*)node
;
2556 if (!node
->full_backref
)
2558 if (parent
== back
->parent
)
2561 if (node
->full_backref
)
2563 if (back
->root
== root
)
2570 static struct tree_backref
*alloc_tree_backref(struct extent_record
*rec
,
2571 u64 parent
, u64 root
)
2573 struct tree_backref
*ref
= malloc(sizeof(*ref
));
2574 memset(&ref
->node
, 0, sizeof(ref
->node
));
2576 ref
->parent
= parent
;
2577 ref
->node
.full_backref
= 1;
2580 ref
->node
.full_backref
= 0;
2582 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
2587 static struct data_backref
*find_data_backref(struct extent_record
*rec
,
2588 u64 parent
, u64 root
,
2589 u64 owner
, u64 offset
,
2591 u64 disk_bytenr
, u64 bytes
)
2593 struct list_head
*cur
= rec
->backrefs
.next
;
2594 struct extent_backref
*node
;
2595 struct data_backref
*back
;
2597 while(cur
!= &rec
->backrefs
) {
2598 node
= list_entry(cur
, struct extent_backref
, list
);
2602 back
= (struct data_backref
*)node
;
2604 if (!node
->full_backref
)
2606 if (parent
== back
->parent
)
2609 if (node
->full_backref
)
2611 if (back
->root
== root
&& back
->owner
== owner
&&
2612 back
->offset
== offset
) {
2613 if (found_ref
&& node
->found_ref
&&
2614 (back
->bytes
!= bytes
||
2615 back
->disk_bytenr
!= disk_bytenr
))
2624 static struct data_backref
*alloc_data_backref(struct extent_record
*rec
,
2625 u64 parent
, u64 root
,
2626 u64 owner
, u64 offset
,
2629 struct data_backref
*ref
= malloc(sizeof(*ref
));
2630 memset(&ref
->node
, 0, sizeof(ref
->node
));
2631 ref
->node
.is_data
= 1;
2634 ref
->parent
= parent
;
2637 ref
->node
.full_backref
= 1;
2641 ref
->offset
= offset
;
2642 ref
->node
.full_backref
= 0;
2644 ref
->bytes
= max_size
;
2647 list_add_tail(&ref
->node
.list
, &rec
->backrefs
);
2648 if (max_size
> rec
->max_size
)
2649 rec
->max_size
= max_size
;
2653 static int add_extent_rec(struct cache_tree
*extent_cache
,
2654 struct btrfs_key
*parent_key
, u64 parent_gen
,
2655 u64 start
, u64 nr
, u64 extent_item_refs
,
2656 int is_root
, int inc_ref
, int set_checked
,
2657 int metadata
, int extent_rec
, u64 max_size
)
2659 struct extent_record
*rec
;
2660 struct cache_extent
*cache
;
2664 cache
= lookup_cache_extent(extent_cache
, start
, nr
);
2666 rec
= container_of(cache
, struct extent_record
, cache
);
2670 rec
->nr
= max(nr
, max_size
);
2673 * We need to make sure to reset nr to whatever the extent
2674 * record says was the real size, this way we can compare it to
2678 if (start
!= rec
->start
|| rec
->found_rec
) {
2679 struct extent_record
*tmp
;
2682 if (list_empty(&rec
->list
))
2683 list_add_tail(&rec
->list
,
2684 &duplicate_extents
);
2687 * We have to do this song and dance in case we
2688 * find an extent record that falls inside of
2689 * our current extent record but does not have
2690 * the same objectid.
2692 tmp
= malloc(sizeof(*tmp
));
2696 tmp
->max_size
= max_size
;
2699 tmp
->metadata
= metadata
;
2700 tmp
->extent_item_refs
= extent_item_refs
;
2701 INIT_LIST_HEAD(&tmp
->list
);
2702 list_add_tail(&tmp
->list
, &rec
->dups
);
2703 rec
->num_duplicates
++;
2710 if (extent_item_refs
&& !dup
) {
2711 if (rec
->extent_item_refs
) {
2712 fprintf(stderr
, "block %llu rec "
2713 "extent_item_refs %llu, passed %llu\n",
2714 (unsigned long long)start
,
2715 (unsigned long long)
2716 rec
->extent_item_refs
,
2717 (unsigned long long)extent_item_refs
);
2719 rec
->extent_item_refs
= extent_item_refs
;
2724 rec
->content_checked
= 1;
2725 rec
->owner_ref_checked
= 1;
2729 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
2731 rec
->parent_generation
= parent_gen
;
2733 if (rec
->max_size
< max_size
)
2734 rec
->max_size
= max_size
;
2736 maybe_free_extent_rec(extent_cache
, rec
);
2739 rec
= malloc(sizeof(*rec
));
2741 rec
->max_size
= max_size
;
2742 rec
->nr
= max(nr
, max_size
);
2743 rec
->found_rec
= !!extent_rec
;
2744 rec
->content_checked
= 0;
2745 rec
->owner_ref_checked
= 0;
2746 rec
->num_duplicates
= 0;
2747 rec
->metadata
= metadata
;
2748 INIT_LIST_HEAD(&rec
->backrefs
);
2749 INIT_LIST_HEAD(&rec
->dups
);
2750 INIT_LIST_HEAD(&rec
->list
);
2762 if (extent_item_refs
)
2763 rec
->extent_item_refs
= extent_item_refs
;
2765 rec
->extent_item_refs
= 0;
2768 btrfs_cpu_key_to_disk(&rec
->parent_key
, parent_key
);
2770 memset(&rec
->parent_key
, 0, sizeof(*parent_key
));
2773 rec
->parent_generation
= parent_gen
;
2775 rec
->parent_generation
= 0;
2777 rec
->cache
.start
= start
;
2778 rec
->cache
.size
= nr
;
2779 ret
= insert_cache_extent(extent_cache
, &rec
->cache
);
2783 rec
->content_checked
= 1;
2784 rec
->owner_ref_checked
= 1;
2789 static int add_tree_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
2790 u64 parent
, u64 root
, int found_ref
)
2792 struct extent_record
*rec
;
2793 struct tree_backref
*back
;
2794 struct cache_extent
*cache
;
2796 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
2798 add_extent_rec(extent_cache
, NULL
, 0, bytenr
,
2799 1, 0, 0, 0, 0, 1, 0, 0);
2800 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
2805 rec
= container_of(cache
, struct extent_record
, cache
);
2806 if (rec
->start
!= bytenr
) {
2810 back
= find_tree_backref(rec
, parent
, root
);
2812 back
= alloc_tree_backref(rec
, parent
, root
);
2815 if (back
->node
.found_ref
) {
2816 fprintf(stderr
, "Extent back ref already exists "
2817 "for %llu parent %llu root %llu \n",
2818 (unsigned long long)bytenr
,
2819 (unsigned long long)parent
,
2820 (unsigned long long)root
);
2822 back
->node
.found_ref
= 1;
2824 if (back
->node
.found_extent_tree
) {
2825 fprintf(stderr
, "Extent back ref already exists "
2826 "for %llu parent %llu root %llu \n",
2827 (unsigned long long)bytenr
,
2828 (unsigned long long)parent
,
2829 (unsigned long long)root
);
2831 back
->node
.found_extent_tree
= 1;
2836 static int add_data_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
2837 u64 parent
, u64 root
, u64 owner
, u64 offset
,
2838 u32 num_refs
, int found_ref
, u64 max_size
)
2840 struct extent_record
*rec
;
2841 struct data_backref
*back
;
2842 struct cache_extent
*cache
;
2844 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
2846 add_extent_rec(extent_cache
, NULL
, 0, bytenr
, 1, 0, 0, 0, 0,
2848 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
2853 rec
= container_of(cache
, struct extent_record
, cache
);
2854 if (rec
->max_size
< max_size
)
2855 rec
->max_size
= max_size
;
2858 * If found_ref is set then max_size is the real size and must match the
2859 * existing refs. So if we have already found a ref then we need to
2860 * make sure that this ref matches the existing one, otherwise we need
2861 * to add a new backref so we can notice that the backrefs don't match
2862 * and we need to figure out who is telling the truth. This is to
2863 * account for that awful fsync bug I introduced where we'd end up with
2864 * a btrfs_file_extent_item that would have its length include multiple
2865 * prealloc extents or point inside of a prealloc extent.
2867 back
= find_data_backref(rec
, parent
, root
, owner
, offset
, found_ref
,
2870 back
= alloc_data_backref(rec
, parent
, root
, owner
, offset
,
2874 BUG_ON(num_refs
!= 1);
2875 if (back
->node
.found_ref
)
2876 BUG_ON(back
->bytes
!= max_size
);
2877 back
->node
.found_ref
= 1;
2878 back
->found_ref
+= 1;
2879 back
->bytes
= max_size
;
2880 back
->disk_bytenr
= bytenr
;
2882 rec
->content_checked
= 1;
2883 rec
->owner_ref_checked
= 1;
2885 if (back
->node
.found_extent_tree
) {
2886 fprintf(stderr
, "Extent back ref already exists "
2887 "for %llu parent %llu root %llu "
2888 "owner %llu offset %llu num_refs %lu\n",
2889 (unsigned long long)bytenr
,
2890 (unsigned long long)parent
,
2891 (unsigned long long)root
,
2892 (unsigned long long)owner
,
2893 (unsigned long long)offset
,
2894 (unsigned long)num_refs
);
2896 back
->num_refs
= num_refs
;
2897 back
->node
.found_extent_tree
= 1;
2902 static int add_pending(struct cache_tree
*pending
,
2903 struct cache_tree
*seen
, u64 bytenr
, u32 size
)
2906 ret
= add_cache_extent(seen
, bytenr
, size
);
2909 add_cache_extent(pending
, bytenr
, size
);
2913 static int pick_next_pending(struct cache_tree
*pending
,
2914 struct cache_tree
*reada
,
2915 struct cache_tree
*nodes
,
2916 u64 last
, struct block_info
*bits
, int bits_nr
,
2919 unsigned long node_start
= last
;
2920 struct cache_extent
*cache
;
2923 cache
= search_cache_extent(reada
, 0);
2925 bits
[0].start
= cache
->start
;
2926 bits
[0].size
= cache
->size
;
2931 if (node_start
> 32768)
2932 node_start
-= 32768;
2934 cache
= search_cache_extent(nodes
, node_start
);
2936 cache
= search_cache_extent(nodes
, 0);
2939 cache
= search_cache_extent(pending
, 0);
2944 bits
[ret
].start
= cache
->start
;
2945 bits
[ret
].size
= cache
->size
;
2946 cache
= next_cache_extent(cache
);
2948 } while (cache
&& ret
< bits_nr
);
2954 bits
[ret
].start
= cache
->start
;
2955 bits
[ret
].size
= cache
->size
;
2956 cache
= next_cache_extent(cache
);
2958 } while (cache
&& ret
< bits_nr
);
2960 if (bits_nr
- ret
> 8) {
2961 u64 lookup
= bits
[0].start
+ bits
[0].size
;
2962 struct cache_extent
*next
;
2963 next
= search_cache_extent(pending
, lookup
);
2965 if (next
->start
- lookup
> 32768)
2967 bits
[ret
].start
= next
->start
;
2968 bits
[ret
].size
= next
->size
;
2969 lookup
= next
->start
+ next
->size
;
2973 next
= next_cache_extent(next
);
2981 static void free_chunk_record(struct cache_extent
*cache
)
2983 struct chunk_record
*rec
;
2985 rec
= container_of(cache
, struct chunk_record
, cache
);
2989 void free_chunk_cache_tree(struct cache_tree
*chunk_cache
)
2991 cache_tree_free_extents(chunk_cache
, free_chunk_record
);
2994 static void free_device_record(struct rb_node
*node
)
2996 struct device_record
*rec
;
2998 rec
= container_of(node
, struct device_record
, node
);
3002 FREE_RB_BASED_TREE(device_cache
, free_device_record
);
3004 int insert_block_group_record(struct block_group_tree
*tree
,
3005 struct block_group_record
*bg_rec
)
3009 ret
= insert_cache_extent(&tree
->tree
, &bg_rec
->cache
);
3013 list_add_tail(&bg_rec
->list
, &tree
->block_groups
);
3017 static void free_block_group_record(struct cache_extent
*cache
)
3019 struct block_group_record
*rec
;
3021 rec
= container_of(cache
, struct block_group_record
, cache
);
3025 void free_block_group_tree(struct block_group_tree
*tree
)
3027 cache_tree_free_extents(&tree
->tree
, free_block_group_record
);
3030 int insert_device_extent_record(struct device_extent_tree
*tree
,
3031 struct device_extent_record
*de_rec
)
3036 * Device extent is a bit different from the other extents, because
3037 * the extents which belong to the different devices may have the
3038 * same start and size, so we need use the special extent cache
3039 * search/insert functions.
3041 ret
= insert_cache_extent2(&tree
->tree
, &de_rec
->cache
);
3045 list_add_tail(&de_rec
->chunk_list
, &tree
->no_chunk_orphans
);
3046 list_add_tail(&de_rec
->device_list
, &tree
->no_device_orphans
);
3050 static void free_device_extent_record(struct cache_extent
*cache
)
3052 struct device_extent_record
*rec
;
3054 rec
= container_of(cache
, struct device_extent_record
, cache
);
3058 void free_device_extent_tree(struct device_extent_tree
*tree
)
3060 cache_tree_free_extents(&tree
->tree
, free_device_extent_record
);
3063 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3064 static int process_extent_ref_v0(struct cache_tree
*extent_cache
,
3065 struct extent_buffer
*leaf
, int slot
)
3067 struct btrfs_extent_ref_v0
*ref0
;
3068 struct btrfs_key key
;
3070 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
3071 ref0
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_ref_v0
);
3072 if (btrfs_ref_objectid_v0(leaf
, ref0
) < BTRFS_FIRST_FREE_OBJECTID
) {
3073 add_tree_backref(extent_cache
, key
.objectid
, key
.offset
, 0, 0);
3075 add_data_backref(extent_cache
, key
.objectid
, key
.offset
, 0,
3076 0, 0, btrfs_ref_count_v0(leaf
, ref0
), 0, 0);
3082 struct chunk_record
*btrfs_new_chunk_record(struct extent_buffer
*leaf
,
3083 struct btrfs_key
*key
,
3086 struct btrfs_chunk
*ptr
;
3087 struct chunk_record
*rec
;
3090 ptr
= btrfs_item_ptr(leaf
, slot
, struct btrfs_chunk
);
3091 num_stripes
= btrfs_chunk_num_stripes(leaf
, ptr
);
3093 rec
= malloc(btrfs_chunk_record_size(num_stripes
));
3095 fprintf(stderr
, "memory allocation failed\n");
3099 memset(rec
, 0, btrfs_chunk_record_size(num_stripes
));
3101 INIT_LIST_HEAD(&rec
->list
);
3102 INIT_LIST_HEAD(&rec
->dextents
);
3105 rec
->cache
.start
= key
->offset
;
3106 rec
->cache
.size
= btrfs_chunk_length(leaf
, ptr
);
3108 rec
->generation
= btrfs_header_generation(leaf
);
3110 rec
->objectid
= key
->objectid
;
3111 rec
->type
= key
->type
;
3112 rec
->offset
= key
->offset
;
3114 rec
->length
= rec
->cache
.size
;
3115 rec
->owner
= btrfs_chunk_owner(leaf
, ptr
);
3116 rec
->stripe_len
= btrfs_chunk_stripe_len(leaf
, ptr
);
3117 rec
->type_flags
= btrfs_chunk_type(leaf
, ptr
);
3118 rec
->io_width
= btrfs_chunk_io_width(leaf
, ptr
);
3119 rec
->io_align
= btrfs_chunk_io_align(leaf
, ptr
);
3120 rec
->sector_size
= btrfs_chunk_sector_size(leaf
, ptr
);
3121 rec
->num_stripes
= num_stripes
;
3122 rec
->sub_stripes
= btrfs_chunk_sub_stripes(leaf
, ptr
);
3124 for (i
= 0; i
< rec
->num_stripes
; ++i
) {
3125 rec
->stripes
[i
].devid
=
3126 btrfs_stripe_devid_nr(leaf
, ptr
, i
);
3127 rec
->stripes
[i
].offset
=
3128 btrfs_stripe_offset_nr(leaf
, ptr
, i
);
3129 read_extent_buffer(leaf
, rec
->stripes
[i
].dev_uuid
,
3130 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr
, i
),
3137 static int process_chunk_item(struct cache_tree
*chunk_cache
,
3138 struct btrfs_key
*key
, struct extent_buffer
*eb
,
3141 struct chunk_record
*rec
;
3144 rec
= btrfs_new_chunk_record(eb
, key
, slot
);
3145 ret
= insert_cache_extent(chunk_cache
, &rec
->cache
);
3147 fprintf(stderr
, "Chunk[%llu, %llu] existed.\n",
3148 rec
->offset
, rec
->length
);
3155 static int process_device_item(struct rb_root
*dev_cache
,
3156 struct btrfs_key
*key
, struct extent_buffer
*eb
, int slot
)
3158 struct btrfs_dev_item
*ptr
;
3159 struct device_record
*rec
;
3162 ptr
= btrfs_item_ptr(eb
,
3163 slot
, struct btrfs_dev_item
);
3165 rec
= malloc(sizeof(*rec
));
3167 fprintf(stderr
, "memory allocation failed\n");
3171 rec
->devid
= key
->offset
;
3172 rec
->generation
= btrfs_header_generation(eb
);
3174 rec
->objectid
= key
->objectid
;
3175 rec
->type
= key
->type
;
3176 rec
->offset
= key
->offset
;
3178 rec
->devid
= btrfs_device_id(eb
, ptr
);
3179 rec
->total_byte
= btrfs_device_total_bytes(eb
, ptr
);
3180 rec
->byte_used
= btrfs_device_bytes_used(eb
, ptr
);
3182 ret
= rb_insert(dev_cache
, &rec
->node
, device_record_compare
);
3184 fprintf(stderr
, "Device[%llu] existed.\n", rec
->devid
);
3191 struct block_group_record
*
3192 btrfs_new_block_group_record(struct extent_buffer
*leaf
, struct btrfs_key
*key
,
3195 struct btrfs_block_group_item
*ptr
;
3196 struct block_group_record
*rec
;
3198 rec
= malloc(sizeof(*rec
));
3200 fprintf(stderr
, "memory allocation failed\n");
3203 memset(rec
, 0, sizeof(*rec
));
3205 rec
->cache
.start
= key
->objectid
;
3206 rec
->cache
.size
= key
->offset
;
3208 rec
->generation
= btrfs_header_generation(leaf
);
3210 rec
->objectid
= key
->objectid
;
3211 rec
->type
= key
->type
;
3212 rec
->offset
= key
->offset
;
3214 ptr
= btrfs_item_ptr(leaf
, slot
, struct btrfs_block_group_item
);
3215 rec
->flags
= btrfs_disk_block_group_flags(leaf
, ptr
);
3217 INIT_LIST_HEAD(&rec
->list
);
3222 static int process_block_group_item(struct block_group_tree
*block_group_cache
,
3223 struct btrfs_key
*key
,
3224 struct extent_buffer
*eb
, int slot
)
3226 struct block_group_record
*rec
;
3229 rec
= btrfs_new_block_group_record(eb
, key
, slot
);
3230 ret
= insert_block_group_record(block_group_cache
, rec
);
3232 fprintf(stderr
, "Block Group[%llu, %llu] existed.\n",
3233 rec
->objectid
, rec
->offset
);
3240 struct device_extent_record
*
3241 btrfs_new_device_extent_record(struct extent_buffer
*leaf
,
3242 struct btrfs_key
*key
, int slot
)
3244 struct device_extent_record
*rec
;
3245 struct btrfs_dev_extent
*ptr
;
3247 rec
= malloc(sizeof(*rec
));
3249 fprintf(stderr
, "memory allocation failed\n");
3252 memset(rec
, 0, sizeof(*rec
));
3254 rec
->cache
.objectid
= key
->objectid
;
3255 rec
->cache
.start
= key
->offset
;
3257 rec
->generation
= btrfs_header_generation(leaf
);
3259 rec
->objectid
= key
->objectid
;
3260 rec
->type
= key
->type
;
3261 rec
->offset
= key
->offset
;
3263 ptr
= btrfs_item_ptr(leaf
, slot
, struct btrfs_dev_extent
);
3264 rec
->chunk_objecteid
=
3265 btrfs_dev_extent_chunk_objectid(leaf
, ptr
);
3267 btrfs_dev_extent_chunk_offset(leaf
, ptr
);
3268 rec
->length
= btrfs_dev_extent_length(leaf
, ptr
);
3269 rec
->cache
.size
= rec
->length
;
3271 INIT_LIST_HEAD(&rec
->chunk_list
);
3272 INIT_LIST_HEAD(&rec
->device_list
);
3278 process_device_extent_item(struct device_extent_tree
*dev_extent_cache
,
3279 struct btrfs_key
*key
, struct extent_buffer
*eb
,
3282 struct device_extent_record
*rec
;
3285 rec
= btrfs_new_device_extent_record(eb
, key
, slot
);
3286 ret
= insert_device_extent_record(dev_extent_cache
, rec
);
3289 "Device extent[%llu, %llu, %llu] existed.\n",
3290 rec
->objectid
, rec
->offset
, rec
->length
);
3297 static int process_extent_item(struct btrfs_root
*root
,
3298 struct cache_tree
*extent_cache
,
3299 struct extent_buffer
*eb
, int slot
)
3301 struct btrfs_extent_item
*ei
;
3302 struct btrfs_extent_inline_ref
*iref
;
3303 struct btrfs_extent_data_ref
*dref
;
3304 struct btrfs_shared_data_ref
*sref
;
3305 struct btrfs_key key
;
3309 u32 item_size
= btrfs_item_size_nr(eb
, slot
);
3315 btrfs_item_key_to_cpu(eb
, &key
, slot
);
3317 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
3319 num_bytes
= root
->leafsize
;
3321 num_bytes
= key
.offset
;
3324 if (item_size
< sizeof(*ei
)) {
3325 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3326 struct btrfs_extent_item_v0
*ei0
;
3327 BUG_ON(item_size
!= sizeof(*ei0
));
3328 ei0
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item_v0
);
3329 refs
= btrfs_extent_refs_v0(eb
, ei0
);
3333 return add_extent_rec(extent_cache
, NULL
, 0, key
.objectid
,
3334 num_bytes
, refs
, 0, 0, 0, metadata
, 1,
3338 ei
= btrfs_item_ptr(eb
, slot
, struct btrfs_extent_item
);
3339 refs
= btrfs_extent_refs(eb
, ei
);
3341 add_extent_rec(extent_cache
, NULL
, 0, key
.objectid
, num_bytes
,
3342 refs
, 0, 0, 0, metadata
, 1, num_bytes
);
3344 ptr
= (unsigned long)(ei
+ 1);
3345 if (btrfs_extent_flags(eb
, ei
) & BTRFS_EXTENT_FLAG_TREE_BLOCK
&&
3346 key
.type
== BTRFS_EXTENT_ITEM_KEY
)
3347 ptr
+= sizeof(struct btrfs_tree_block_info
);
3349 end
= (unsigned long)ei
+ item_size
;
3351 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
3352 type
= btrfs_extent_inline_ref_type(eb
, iref
);
3353 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
3355 case BTRFS_TREE_BLOCK_REF_KEY
:
3356 add_tree_backref(extent_cache
, key
.objectid
,
3359 case BTRFS_SHARED_BLOCK_REF_KEY
:
3360 add_tree_backref(extent_cache
, key
.objectid
,
3363 case BTRFS_EXTENT_DATA_REF_KEY
:
3364 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
3365 add_data_backref(extent_cache
, key
.objectid
, 0,
3366 btrfs_extent_data_ref_root(eb
, dref
),
3367 btrfs_extent_data_ref_objectid(eb
,
3369 btrfs_extent_data_ref_offset(eb
, dref
),
3370 btrfs_extent_data_ref_count(eb
, dref
),
3373 case BTRFS_SHARED_DATA_REF_KEY
:
3374 sref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
3375 add_data_backref(extent_cache
, key
.objectid
, offset
,
3377 btrfs_shared_data_ref_count(eb
, sref
),
3381 fprintf(stderr
, "corrupt extent record: key %Lu %u %Lu\n",
3382 key
.objectid
, key
.type
, num_bytes
);
3385 ptr
+= btrfs_extent_inline_ref_size(type
);
3392 static int check_cache_range(struct btrfs_root
*root
,
3393 struct btrfs_block_group_cache
*cache
,
3394 u64 offset
, u64 bytes
)
3396 struct btrfs_free_space
*entry
;
3402 for (i
= 0; i
< BTRFS_SUPER_MIRROR_MAX
; i
++) {
3403 bytenr
= btrfs_sb_offset(i
);
3404 ret
= btrfs_rmap_block(&root
->fs_info
->mapping_tree
,
3405 cache
->key
.objectid
, bytenr
, 0,
3406 &logical
, &nr
, &stripe_len
);
3411 if (logical
[nr
] + stripe_len
<= offset
)
3413 if (offset
+ bytes
<= logical
[nr
])
3415 if (logical
[nr
] == offset
) {
3416 if (stripe_len
>= bytes
) {
3420 bytes
-= stripe_len
;
3421 offset
+= stripe_len
;
3422 } else if (logical
[nr
] < offset
) {
3423 if (logical
[nr
] + stripe_len
>=
3428 bytes
= (offset
+ bytes
) -
3429 (logical
[nr
] + stripe_len
);
3430 offset
= logical
[nr
] + stripe_len
;
3433 * Could be tricky, the super may land in the
3434 * middle of the area we're checking. First
3435 * check the easiest case, it's at the end.
3437 if (logical
[nr
] + stripe_len
>=
3439 bytes
= logical
[nr
] - offset
;
3443 /* Check the left side */
3444 ret
= check_cache_range(root
, cache
,
3446 logical
[nr
] - offset
);
3452 /* Now we continue with the right side */
3453 bytes
= (offset
+ bytes
) -
3454 (logical
[nr
] + stripe_len
);
3455 offset
= logical
[nr
] + stripe_len
;
3462 entry
= btrfs_find_free_space(cache
->free_space_ctl
, offset
, bytes
);
3464 fprintf(stderr
, "There is no free space entry for %Lu-%Lu\n",
3465 offset
, offset
+bytes
);
3469 if (entry
->offset
!= offset
) {
3470 fprintf(stderr
, "Wanted offset %Lu, found %Lu\n", offset
,
3475 if (entry
->bytes
!= bytes
) {
3476 fprintf(stderr
, "Wanted bytes %Lu, found %Lu for off %Lu\n",
3477 bytes
, entry
->bytes
, offset
);
3481 unlink_free_space(cache
->free_space_ctl
, entry
);
3486 static int verify_space_cache(struct btrfs_root
*root
,
3487 struct btrfs_block_group_cache
*cache
)
3489 struct btrfs_path
*path
;
3490 struct extent_buffer
*leaf
;
3491 struct btrfs_key key
;
3495 path
= btrfs_alloc_path();
3499 root
= root
->fs_info
->extent_root
;
3501 last
= max_t(u64
, cache
->key
.objectid
, BTRFS_SUPER_INFO_OFFSET
);
3503 key
.objectid
= last
;
3505 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
3507 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
3512 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
3513 ret
= btrfs_next_leaf(root
, path
);
3521 leaf
= path
->nodes
[0];
3522 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
3523 if (key
.objectid
>= cache
->key
.offset
+ cache
->key
.objectid
)
3525 if (key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
3526 key
.type
!= BTRFS_METADATA_ITEM_KEY
) {
3531 if (last
== key
.objectid
) {
3532 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
)
3533 last
= key
.objectid
+ key
.offset
;
3535 last
= key
.objectid
+ root
->leafsize
;
3540 ret
= check_cache_range(root
, cache
, last
,
3541 key
.objectid
- last
);
3544 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
)
3545 last
= key
.objectid
+ key
.offset
;
3547 last
= key
.objectid
+ root
->leafsize
;
3551 if (last
< cache
->key
.objectid
+ cache
->key
.offset
)
3552 ret
= check_cache_range(root
, cache
, last
,
3553 cache
->key
.objectid
+
3554 cache
->key
.offset
- last
);
3557 btrfs_free_path(path
);
3560 !RB_EMPTY_ROOT(&cache
->free_space_ctl
->free_space_offset
)) {
3561 fprintf(stderr
, "There are still entries left in the space "
3569 static int check_space_cache(struct btrfs_root
*root
)
3571 struct btrfs_block_group_cache
*cache
;
3572 u64 start
= BTRFS_SUPER_INFO_OFFSET
+ BTRFS_SUPER_INFO_SIZE
;
3576 if (btrfs_super_cache_generation(root
->fs_info
->super_copy
) != -1ULL &&
3577 btrfs_super_generation(root
->fs_info
->super_copy
) !=
3578 btrfs_super_cache_generation(root
->fs_info
->super_copy
)) {
3579 printf("cache and super generation don't match, space cache "
3580 "will be invalidated\n");
3585 cache
= btrfs_lookup_first_block_group(root
->fs_info
, start
);
3589 start
= cache
->key
.objectid
+ cache
->key
.offset
;
3590 if (!cache
->free_space_ctl
) {
3591 if (btrfs_init_free_space_ctl(cache
,
3592 root
->sectorsize
)) {
3597 btrfs_remove_free_space_cache(cache
);
3600 ret
= load_free_space_cache(root
->fs_info
, cache
);
3604 ret
= verify_space_cache(root
, cache
);
3606 fprintf(stderr
, "cache appears valid but isnt %Lu\n",
3607 cache
->key
.objectid
);
3612 return error
? -EINVAL
: 0;
3615 static int read_extent_data(struct btrfs_root
*root
, char *data
,
3616 u64 logical
, u64
*len
, int mirror
)
3619 struct btrfs_multi_bio
*multi
= NULL
;
3620 struct btrfs_fs_info
*info
= root
->fs_info
;
3621 struct btrfs_device
*device
;
3625 ret
= btrfs_map_block(&info
->mapping_tree
, READ
, logical
, len
,
3626 &multi
, mirror
, NULL
);
3628 fprintf(stderr
, "Couldn't map the block %llu\n",
3632 device
= multi
->stripes
[0].dev
;
3634 if (device
->fd
== 0)
3639 ret
= pread64(device
->fd
, data
, *len
, multi
->stripes
[0].physical
);
3649 static int check_extent_csums(struct btrfs_root
*root
, u64 bytenr
,
3650 u64 num_bytes
, unsigned long leaf_offset
,
3651 struct extent_buffer
*eb
) {
3654 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
3656 unsigned long csum_offset
;
3660 u64 data_checked
= 0;
3666 if (num_bytes
% root
->sectorsize
)
3669 data
= malloc(num_bytes
);
3673 while (offset
< num_bytes
) {
3676 read_len
= num_bytes
- offset
;
3677 /* read as much space once a time */
3678 ret
= read_extent_data(root
, data
+ offset
,
3679 bytenr
+ offset
, &read_len
, mirror
);
3683 /* verify every 4k data's checksum */
3684 while (data_checked
< read_len
) {
3686 tmp
= offset
+ data_checked
;
3688 csum
= btrfs_csum_data(NULL
, (char *)data
+ tmp
,
3689 csum
, root
->sectorsize
);
3690 btrfs_csum_final(csum
, (char *)&csum
);
3692 csum_offset
= leaf_offset
+
3693 tmp
/ root
->sectorsize
* csum_size
;
3694 read_extent_buffer(eb
, (char *)&csum_expected
,
3695 csum_offset
, csum_size
);
3696 /* try another mirror */
3697 if (csum
!= csum_expected
) {
3698 fprintf(stderr
, "mirror %d bytenr %llu csum %u expected csum %u\n",
3699 mirror
, bytenr
+ tmp
,
3700 csum
, csum_expected
);
3701 num_copies
= btrfs_num_copies(
3702 &root
->fs_info
->mapping_tree
,
3704 if (mirror
< num_copies
- 1) {
3709 data_checked
+= root
->sectorsize
;
3718 static int check_extent_exists(struct btrfs_root
*root
, u64 bytenr
,
3721 struct btrfs_path
*path
;
3722 struct extent_buffer
*leaf
;
3723 struct btrfs_key key
;
3726 path
= btrfs_alloc_path();
3728 fprintf(stderr
, "Error allocing path\n");
3732 key
.objectid
= bytenr
;
3733 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
3738 ret
= btrfs_search_slot(NULL
, root
->fs_info
->extent_root
, &key
, path
,
3741 fprintf(stderr
, "Error looking up extent record %d\n", ret
);
3742 btrfs_free_path(path
);
3748 btrfs_prev_leaf(root
, path
);
3751 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
3754 * Block group items come before extent items if they have the same
3755 * bytenr, so walk back one more just in case. Dear future traveler,
3756 * first congrats on mastering time travel. Now if it's not too much
3757 * trouble could you go back to 2006 and tell Chris to make the
3758 * BLOCK_GROUP_ITEM_KEY lower than the EXTENT_ITEM_KEY please?
3760 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
3764 btrfs_prev_leaf(root
, path
);
3768 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
3769 ret
= btrfs_next_leaf(root
, path
);
3771 fprintf(stderr
, "Error going to next leaf "
3773 btrfs_free_path(path
);
3779 leaf
= path
->nodes
[0];
3780 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
3781 if (key
.type
!= BTRFS_EXTENT_ITEM_KEY
) {
3785 if (key
.objectid
+ key
.offset
< bytenr
) {
3789 if (key
.objectid
> bytenr
+ num_bytes
)
3792 if (key
.objectid
== bytenr
) {
3793 if (key
.offset
>= num_bytes
) {
3797 num_bytes
-= key
.offset
;
3798 bytenr
+= key
.offset
;
3799 } else if (key
.objectid
< bytenr
) {
3800 if (key
.objectid
+ key
.offset
>= bytenr
+ num_bytes
) {
3804 num_bytes
= (bytenr
+ num_bytes
) -
3805 (key
.objectid
+ key
.offset
);
3806 bytenr
= key
.objectid
+ key
.offset
;
3808 if (key
.objectid
+ key
.offset
< bytenr
+ num_bytes
) {
3809 u64 new_start
= key
.objectid
+ key
.offset
;
3810 u64 new_bytes
= bytenr
+ num_bytes
- new_start
;
3813 * Weird case, the extent is in the middle of
3814 * our range, we'll have to search one side
3815 * and then the other. Not sure if this happens
3816 * in real life, but no harm in coding it up
3817 * anyway just in case.
3819 btrfs_release_path(path
);
3820 ret
= check_extent_exists(root
, new_start
,
3823 fprintf(stderr
, "Right section didn't "
3827 num_bytes
= key
.objectid
- bytenr
;
3830 num_bytes
= key
.objectid
- bytenr
;
3837 fprintf(stderr
, "There are no extents for csum range "
3838 "%Lu-%Lu\n", bytenr
, bytenr
+num_bytes
);
3842 btrfs_free_path(path
);
3846 static int check_csums(struct btrfs_root
*root
)
3848 struct btrfs_path
*path
;
3849 struct extent_buffer
*leaf
;
3850 struct btrfs_key key
;
3851 u64 offset
= 0, num_bytes
= 0;
3852 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
3856 unsigned long leaf_offset
;
3858 root
= root
->fs_info
->csum_root
;
3860 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
3861 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
3864 path
= btrfs_alloc_path();
3868 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
3870 fprintf(stderr
, "Error searching csum tree %d\n", ret
);
3871 btrfs_free_path(path
);
3875 if (ret
> 0 && path
->slots
[0])
3880 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
3881 ret
= btrfs_next_leaf(root
, path
);
3883 fprintf(stderr
, "Error going to next leaf "
3890 leaf
= path
->nodes
[0];
3892 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
3893 if (key
.type
!= BTRFS_EXTENT_CSUM_KEY
) {
3898 data_len
= (btrfs_item_size_nr(leaf
, path
->slots
[0]) /
3899 csum_size
) * root
->sectorsize
;
3900 if (!check_data_csum
)
3901 goto skip_csum_check
;
3902 leaf_offset
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
3903 ret
= check_extent_csums(root
, key
.offset
, data_len
,
3909 offset
= key
.offset
;
3910 } else if (key
.offset
!= offset
+ num_bytes
) {
3911 ret
= check_extent_exists(root
, offset
, num_bytes
);
3913 fprintf(stderr
, "Csum exists for %Lu-%Lu but "
3914 "there is no extent record\n",
3915 offset
, offset
+num_bytes
);
3918 offset
= key
.offset
;
3921 num_bytes
+= data_len
;
3925 btrfs_free_path(path
);
3929 static int is_dropped_key(struct btrfs_key
*key
,
3930 struct btrfs_key
*drop_key
) {
3931 if (key
->objectid
< drop_key
->objectid
)
3933 else if (key
->objectid
== drop_key
->objectid
) {
3934 if (key
->type
< drop_key
->type
)
3936 else if (key
->type
== drop_key
->type
) {
3937 if (key
->offset
< drop_key
->offset
)
3944 static int run_next_block(struct btrfs_trans_handle
*trans
,
3945 struct btrfs_root
*root
,
3946 struct block_info
*bits
,
3949 struct cache_tree
*pending
,
3950 struct cache_tree
*seen
,
3951 struct cache_tree
*reada
,
3952 struct cache_tree
*nodes
,
3953 struct cache_tree
*extent_cache
,
3954 struct cache_tree
*chunk_cache
,
3955 struct rb_root
*dev_cache
,
3956 struct block_group_tree
*block_group_cache
,
3957 struct device_extent_tree
*dev_extent_cache
,
3958 struct btrfs_root_item
*ri
)
3960 struct extent_buffer
*buf
;
3971 struct btrfs_key key
;
3972 struct cache_extent
*cache
;
3975 nritems
= pick_next_pending(pending
, reada
, nodes
, *last
, bits
,
3976 bits_nr
, &reada_bits
);
3981 for(i
= 0; i
< nritems
; i
++) {
3982 ret
= add_cache_extent(reada
, bits
[i
].start
,
3987 /* fixme, get the parent transid */
3988 readahead_tree_block(root
, bits
[i
].start
,
3992 *last
= bits
[0].start
;
3993 bytenr
= bits
[0].start
;
3994 size
= bits
[0].size
;
3996 cache
= lookup_cache_extent(pending
, bytenr
, size
);
3998 remove_cache_extent(pending
, cache
);
4001 cache
= lookup_cache_extent(reada
, bytenr
, size
);
4003 remove_cache_extent(reada
, cache
);
4006 cache
= lookup_cache_extent(nodes
, bytenr
, size
);
4008 remove_cache_extent(nodes
, cache
);
4011 cache
= lookup_cache_extent(extent_cache
, bytenr
, size
);
4013 struct extent_record
*rec
;
4015 rec
= container_of(cache
, struct extent_record
, cache
);
4016 gen
= rec
->parent_generation
;
4019 /* fixme, get the real parent transid */
4020 buf
= read_tree_block(root
, bytenr
, size
, gen
);
4021 if (!extent_buffer_uptodate(buf
)) {
4022 record_bad_block_io(root
->fs_info
,
4023 extent_cache
, bytenr
, size
);
4027 nritems
= btrfs_header_nritems(buf
);
4030 * FIXME, this only works only if we don't have any full
4033 if (!init_extent_tree
) {
4034 ret
= btrfs_lookup_extent_info(NULL
, root
, bytenr
,
4035 btrfs_header_level(buf
), 1, NULL
,
4043 if (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
) {
4048 owner
= btrfs_header_owner(buf
);
4051 ret
= check_block(trans
, root
, extent_cache
, buf
, flags
);
4055 if (btrfs_is_leaf(buf
)) {
4056 btree_space_waste
+= btrfs_leaf_free_space(root
, buf
);
4057 for (i
= 0; i
< nritems
; i
++) {
4058 struct btrfs_file_extent_item
*fi
;
4059 btrfs_item_key_to_cpu(buf
, &key
, i
);
4060 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
4061 process_extent_item(root
, extent_cache
, buf
,
4065 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
4066 process_extent_item(root
, extent_cache
, buf
,
4070 if (key
.type
== BTRFS_EXTENT_CSUM_KEY
) {
4072 btrfs_item_size_nr(buf
, i
);
4075 if (key
.type
== BTRFS_CHUNK_ITEM_KEY
) {
4076 process_chunk_item(chunk_cache
, &key
, buf
, i
);
4079 if (key
.type
== BTRFS_DEV_ITEM_KEY
) {
4080 process_device_item(dev_cache
, &key
, buf
, i
);
4083 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
4084 process_block_group_item(block_group_cache
,
4088 if (key
.type
== BTRFS_DEV_EXTENT_KEY
) {
4089 process_device_extent_item(dev_extent_cache
,
4094 if (key
.type
== BTRFS_EXTENT_REF_V0_KEY
) {
4095 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4096 process_extent_ref_v0(extent_cache
, buf
, i
);
4103 if (key
.type
== BTRFS_TREE_BLOCK_REF_KEY
) {
4104 add_tree_backref(extent_cache
, key
.objectid
, 0,
4108 if (key
.type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
4109 add_tree_backref(extent_cache
, key
.objectid
,
4113 if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
) {
4114 struct btrfs_extent_data_ref
*ref
;
4115 ref
= btrfs_item_ptr(buf
, i
,
4116 struct btrfs_extent_data_ref
);
4117 add_data_backref(extent_cache
,
4119 btrfs_extent_data_ref_root(buf
, ref
),
4120 btrfs_extent_data_ref_objectid(buf
,
4122 btrfs_extent_data_ref_offset(buf
, ref
),
4123 btrfs_extent_data_ref_count(buf
, ref
),
4124 0, root
->sectorsize
);
4127 if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
) {
4128 struct btrfs_shared_data_ref
*ref
;
4129 ref
= btrfs_item_ptr(buf
, i
,
4130 struct btrfs_shared_data_ref
);
4131 add_data_backref(extent_cache
,
4132 key
.objectid
, key
.offset
, 0, 0, 0,
4133 btrfs_shared_data_ref_count(buf
, ref
),
4134 0, root
->sectorsize
);
4137 if (key
.type
== BTRFS_ORPHAN_ITEM_KEY
) {
4138 struct bad_item
*bad
;
4140 if (key
.objectid
== BTRFS_ORPHAN_OBJECTID
)
4144 bad
= malloc(sizeof(struct bad_item
));
4147 INIT_LIST_HEAD(&bad
->list
);
4148 memcpy(&bad
->key
, &key
,
4149 sizeof(struct btrfs_key
));
4150 bad
->root_id
= owner
;
4151 list_add_tail(&bad
->list
, &delete_items
);
4154 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
4156 fi
= btrfs_item_ptr(buf
, i
,
4157 struct btrfs_file_extent_item
);
4158 if (btrfs_file_extent_type(buf
, fi
) ==
4159 BTRFS_FILE_EXTENT_INLINE
)
4161 if (btrfs_file_extent_disk_bytenr(buf
, fi
) == 0)
4164 data_bytes_allocated
+=
4165 btrfs_file_extent_disk_num_bytes(buf
, fi
);
4166 if (data_bytes_allocated
< root
->sectorsize
) {
4169 data_bytes_referenced
+=
4170 btrfs_file_extent_num_bytes(buf
, fi
);
4171 add_data_backref(extent_cache
,
4172 btrfs_file_extent_disk_bytenr(buf
, fi
),
4173 parent
, owner
, key
.objectid
, key
.offset
-
4174 btrfs_file_extent_offset(buf
, fi
), 1, 1,
4175 btrfs_file_extent_disk_num_bytes(buf
, fi
));
4179 struct btrfs_key first_key
;
4181 first_key
.objectid
= 0;
4184 btrfs_item_key_to_cpu(buf
, &first_key
, 0);
4185 level
= btrfs_header_level(buf
);
4186 for (i
= 0; i
< nritems
; i
++) {
4187 ptr
= btrfs_node_blockptr(buf
, i
);
4188 size
= btrfs_level_size(root
, level
- 1);
4189 btrfs_node_key_to_cpu(buf
, &key
, i
);
4191 struct btrfs_key drop_key
;
4192 btrfs_disk_key_to_cpu(&drop_key
,
4193 &ri
->drop_progress
);
4194 if ((level
== ri
->drop_level
)
4195 && is_dropped_key(&key
, &drop_key
)) {
4199 ret
= add_extent_rec(extent_cache
, &key
,
4200 btrfs_node_ptr_generation(buf
, i
),
4201 ptr
, size
, 0, 0, 1, 0, 1, 0,
4205 add_tree_backref(extent_cache
, ptr
, parent
, owner
, 1);
4208 add_pending(nodes
, seen
, ptr
, size
);
4210 add_pending(pending
, seen
, ptr
, size
);
4213 btree_space_waste
+= (BTRFS_NODEPTRS_PER_BLOCK(root
) -
4214 nritems
) * sizeof(struct btrfs_key_ptr
);
4216 total_btree_bytes
+= buf
->len
;
4217 if (fs_root_objectid(btrfs_header_owner(buf
)))
4218 total_fs_tree_bytes
+= buf
->len
;
4219 if (btrfs_header_owner(buf
) == BTRFS_EXTENT_TREE_OBJECTID
)
4220 total_extent_tree_bytes
+= buf
->len
;
4221 if (!found_old_backref
&&
4222 btrfs_header_owner(buf
) == BTRFS_TREE_RELOC_OBJECTID
&&
4223 btrfs_header_backref_rev(buf
) == BTRFS_MIXED_BACKREF_REV
&&
4224 !btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_RELOC
))
4225 found_old_backref
= 1;
4227 free_extent_buffer(buf
);
4231 static int add_root_to_pending(struct extent_buffer
*buf
,
4232 struct cache_tree
*extent_cache
,
4233 struct cache_tree
*pending
,
4234 struct cache_tree
*seen
,
4235 struct cache_tree
*nodes
,
4236 struct btrfs_key
*root_key
)
4238 if (btrfs_header_level(buf
) > 0)
4239 add_pending(nodes
, seen
, buf
->start
, buf
->len
);
4241 add_pending(pending
, seen
, buf
->start
, buf
->len
);
4242 add_extent_rec(extent_cache
, NULL
, 0, buf
->start
, buf
->len
,
4243 0, 1, 1, 0, 1, 0, buf
->len
);
4245 if (root_key
->objectid
== BTRFS_TREE_RELOC_OBJECTID
||
4246 btrfs_header_backref_rev(buf
) < BTRFS_MIXED_BACKREF_REV
)
4247 add_tree_backref(extent_cache
, buf
->start
, buf
->start
,
4250 add_tree_backref(extent_cache
, buf
->start
, 0,
4251 root_key
->objectid
, 1);
4255 /* as we fix the tree, we might be deleting blocks that
4256 * we're tracking for repair. This hook makes sure we
4257 * remove any backrefs for blocks as we are fixing them.
4259 static int free_extent_hook(struct btrfs_trans_handle
*trans
,
4260 struct btrfs_root
*root
,
4261 u64 bytenr
, u64 num_bytes
, u64 parent
,
4262 u64 root_objectid
, u64 owner
, u64 offset
,
4265 struct extent_record
*rec
;
4266 struct cache_extent
*cache
;
4268 struct cache_tree
*extent_cache
= root
->fs_info
->fsck_extent_cache
;
4270 is_data
= owner
>= BTRFS_FIRST_FREE_OBJECTID
;
4271 cache
= lookup_cache_extent(extent_cache
, bytenr
, num_bytes
);
4275 rec
= container_of(cache
, struct extent_record
, cache
);
4277 struct data_backref
*back
;
4278 back
= find_data_backref(rec
, parent
, root_objectid
, owner
,
4279 offset
, 1, bytenr
, num_bytes
);
4282 if (back
->node
.found_ref
) {
4283 back
->found_ref
-= refs_to_drop
;
4285 rec
->refs
-= refs_to_drop
;
4287 if (back
->node
.found_extent_tree
) {
4288 back
->num_refs
-= refs_to_drop
;
4289 if (rec
->extent_item_refs
)
4290 rec
->extent_item_refs
-= refs_to_drop
;
4292 if (back
->found_ref
== 0)
4293 back
->node
.found_ref
= 0;
4294 if (back
->num_refs
== 0)
4295 back
->node
.found_extent_tree
= 0;
4297 if (!back
->node
.found_extent_tree
&& back
->node
.found_ref
) {
4298 list_del(&back
->node
.list
);
4302 struct tree_backref
*back
;
4303 back
= find_tree_backref(rec
, parent
, root_objectid
);
4306 if (back
->node
.found_ref
) {
4309 back
->node
.found_ref
= 0;
4311 if (back
->node
.found_extent_tree
) {
4312 if (rec
->extent_item_refs
)
4313 rec
->extent_item_refs
--;
4314 back
->node
.found_extent_tree
= 0;
4316 if (!back
->node
.found_extent_tree
&& back
->node
.found_ref
) {
4317 list_del(&back
->node
.list
);
4321 maybe_free_extent_rec(extent_cache
, rec
);
4326 static int delete_extent_records(struct btrfs_trans_handle
*trans
,
4327 struct btrfs_root
*root
,
4328 struct btrfs_path
*path
,
4329 u64 bytenr
, u64 new_len
)
4331 struct btrfs_key key
;
4332 struct btrfs_key found_key
;
4333 struct extent_buffer
*leaf
;
4338 key
.objectid
= bytenr
;
4340 key
.offset
= (u64
)-1;
4343 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
,
4350 if (path
->slots
[0] == 0)
4356 leaf
= path
->nodes
[0];
4357 slot
= path
->slots
[0];
4359 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
4360 if (found_key
.objectid
!= bytenr
)
4363 if (found_key
.type
!= BTRFS_EXTENT_ITEM_KEY
&&
4364 found_key
.type
!= BTRFS_METADATA_ITEM_KEY
&&
4365 found_key
.type
!= BTRFS_TREE_BLOCK_REF_KEY
&&
4366 found_key
.type
!= BTRFS_EXTENT_DATA_REF_KEY
&&
4367 found_key
.type
!= BTRFS_EXTENT_REF_V0_KEY
&&
4368 found_key
.type
!= BTRFS_SHARED_BLOCK_REF_KEY
&&
4369 found_key
.type
!= BTRFS_SHARED_DATA_REF_KEY
) {
4370 btrfs_release_path(path
);
4371 if (found_key
.type
== 0) {
4372 if (found_key
.offset
== 0)
4374 key
.offset
= found_key
.offset
- 1;
4375 key
.type
= found_key
.type
;
4377 key
.type
= found_key
.type
- 1;
4378 key
.offset
= (u64
)-1;
4382 fprintf(stderr
, "repair deleting extent record: key %Lu %u %Lu\n",
4383 found_key
.objectid
, found_key
.type
, found_key
.offset
);
4385 ret
= btrfs_del_item(trans
, root
->fs_info
->extent_root
, path
);
4388 btrfs_release_path(path
);
4390 if (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
||
4391 found_key
.type
== BTRFS_METADATA_ITEM_KEY
) {
4392 u64 bytes
= (found_key
.type
== BTRFS_EXTENT_ITEM_KEY
) ?
4393 found_key
.offset
: root
->leafsize
;
4395 ret
= btrfs_update_block_group(trans
, root
, bytenr
,
4402 btrfs_release_path(path
);
4407 * for a single backref, this will allocate a new extent
4408 * and add the backref to it.
4410 static int record_extent(struct btrfs_trans_handle
*trans
,
4411 struct btrfs_fs_info
*info
,
4412 struct btrfs_path
*path
,
4413 struct extent_record
*rec
,
4414 struct extent_backref
*back
,
4415 int allocated
, u64 flags
)
4418 struct btrfs_root
*extent_root
= info
->extent_root
;
4419 struct extent_buffer
*leaf
;
4420 struct btrfs_key ins_key
;
4421 struct btrfs_extent_item
*ei
;
4422 struct tree_backref
*tback
;
4423 struct data_backref
*dback
;
4424 struct btrfs_tree_block_info
*bi
;
4427 rec
->max_size
= max_t(u64
, rec
->max_size
,
4428 info
->extent_root
->leafsize
);
4431 u32 item_size
= sizeof(*ei
);
4434 item_size
+= sizeof(*bi
);
4436 ins_key
.objectid
= rec
->start
;
4437 ins_key
.offset
= rec
->max_size
;
4438 ins_key
.type
= BTRFS_EXTENT_ITEM_KEY
;
4440 ret
= btrfs_insert_empty_item(trans
, extent_root
, path
,
4441 &ins_key
, item_size
);
4445 leaf
= path
->nodes
[0];
4446 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
4447 struct btrfs_extent_item
);
4449 btrfs_set_extent_refs(leaf
, ei
, 0);
4450 btrfs_set_extent_generation(leaf
, ei
, rec
->generation
);
4452 if (back
->is_data
) {
4453 btrfs_set_extent_flags(leaf
, ei
,
4454 BTRFS_EXTENT_FLAG_DATA
);
4456 struct btrfs_disk_key copy_key
;;
4458 tback
= (struct tree_backref
*)back
;
4459 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
4460 memset_extent_buffer(leaf
, 0, (unsigned long)bi
,
4463 btrfs_set_disk_key_objectid(©_key
,
4464 rec
->info_objectid
);
4465 btrfs_set_disk_key_type(©_key
, 0);
4466 btrfs_set_disk_key_offset(©_key
, 0);
4468 btrfs_set_tree_block_level(leaf
, bi
, rec
->info_level
);
4469 btrfs_set_tree_block_key(leaf
, bi
, ©_key
);
4471 btrfs_set_extent_flags(leaf
, ei
,
4472 BTRFS_EXTENT_FLAG_TREE_BLOCK
| flags
);
4475 btrfs_mark_buffer_dirty(leaf
);
4476 ret
= btrfs_update_block_group(trans
, extent_root
, rec
->start
,
4477 rec
->max_size
, 1, 0);
4480 btrfs_release_path(path
);
4483 if (back
->is_data
) {
4487 dback
= (struct data_backref
*)back
;
4488 if (back
->full_backref
)
4489 parent
= dback
->parent
;
4493 for (i
= 0; i
< dback
->found_ref
; i
++) {
4494 /* if parent != 0, we're doing a full backref
4495 * passing BTRFS_FIRST_FREE_OBJECTID as the owner
4496 * just makes the backref allocator create a data
4499 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
4500 rec
->start
, rec
->max_size
,
4504 BTRFS_FIRST_FREE_OBJECTID
:
4510 fprintf(stderr
, "adding new data backref"
4511 " on %llu %s %llu owner %llu"
4512 " offset %llu found %d\n",
4513 (unsigned long long)rec
->start
,
4514 back
->full_backref
?
4516 back
->full_backref
?
4517 (unsigned long long)parent
:
4518 (unsigned long long)dback
->root
,
4519 (unsigned long long)dback
->owner
,
4520 (unsigned long long)dback
->offset
,
4525 tback
= (struct tree_backref
*)back
;
4526 if (back
->full_backref
)
4527 parent
= tback
->parent
;
4531 ret
= btrfs_inc_extent_ref(trans
, info
->extent_root
,
4532 rec
->start
, rec
->max_size
,
4533 parent
, tback
->root
, 0, 0);
4534 fprintf(stderr
, "adding new tree backref on "
4535 "start %llu len %llu parent %llu root %llu\n",
4536 rec
->start
, rec
->max_size
, tback
->parent
, tback
->root
);
4541 btrfs_release_path(path
);
4545 struct extent_entry
{
4550 struct list_head list
;
4553 static struct extent_entry
*find_entry(struct list_head
*entries
,
4554 u64 bytenr
, u64 bytes
)
4556 struct extent_entry
*entry
= NULL
;
4558 list_for_each_entry(entry
, entries
, list
) {
4559 if (entry
->bytenr
== bytenr
&& entry
->bytes
== bytes
)
4566 static struct extent_entry
*find_most_right_entry(struct list_head
*entries
)
4568 struct extent_entry
*entry
, *best
= NULL
, *prev
= NULL
;
4570 list_for_each_entry(entry
, entries
, list
) {
4577 * If there are as many broken entries as entries then we know
4578 * not to trust this particular entry.
4580 if (entry
->broken
== entry
->count
)
4584 * If our current entry == best then we can't be sure our best
4585 * is really the best, so we need to keep searching.
4587 if (best
&& best
->count
== entry
->count
) {
4593 /* Prev == entry, not good enough, have to keep searching */
4594 if (!prev
->broken
&& prev
->count
== entry
->count
)
4598 best
= (prev
->count
> entry
->count
) ? prev
: entry
;
4599 else if (best
->count
< entry
->count
)
4607 static int repair_ref(struct btrfs_trans_handle
*trans
,
4608 struct btrfs_fs_info
*info
, struct btrfs_path
*path
,
4609 struct data_backref
*dback
, struct extent_entry
*entry
)
4611 struct btrfs_root
*root
;
4612 struct btrfs_file_extent_item
*fi
;
4613 struct extent_buffer
*leaf
;
4614 struct btrfs_key key
;
4618 key
.objectid
= dback
->root
;
4619 key
.type
= BTRFS_ROOT_ITEM_KEY
;
4620 key
.offset
= (u64
)-1;
4621 root
= btrfs_read_fs_root(info
, &key
);
4623 fprintf(stderr
, "Couldn't find root for our ref\n");
4628 * The backref points to the original offset of the extent if it was
4629 * split, so we need to search down to the offset we have and then walk
4630 * forward until we find the backref we're looking for.
4632 key
.objectid
= dback
->owner
;
4633 key
.type
= BTRFS_EXTENT_DATA_KEY
;
4634 key
.offset
= dback
->offset
;
4635 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
4637 fprintf(stderr
, "Error looking up ref %d\n", ret
);
4642 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
4643 ret
= btrfs_next_leaf(root
, path
);
4645 fprintf(stderr
, "Couldn't find our ref, next\n");
4649 leaf
= path
->nodes
[0];
4650 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
4651 if (key
.objectid
!= dback
->owner
||
4652 key
.type
!= BTRFS_EXTENT_DATA_KEY
) {
4653 fprintf(stderr
, "Couldn't find our ref, search\n");
4656 fi
= btrfs_item_ptr(leaf
, path
->slots
[0],
4657 struct btrfs_file_extent_item
);
4658 bytenr
= btrfs_file_extent_disk_bytenr(leaf
, fi
);
4659 bytes
= btrfs_file_extent_disk_num_bytes(leaf
, fi
);
4661 if (bytenr
== dback
->disk_bytenr
&& bytes
== dback
->bytes
)
4666 btrfs_release_path(path
);
4669 * Have to make sure that this root gets updated when we commit the
4672 root
->track_dirty
= 1;
4673 if (root
->last_trans
!= trans
->transid
) {
4674 root
->last_trans
= trans
->transid
;
4675 root
->commit_root
= root
->node
;
4676 extent_buffer_get(root
->node
);
4680 * Ok we have the key of the file extent we want to fix, now we can cow
4681 * down to the thing and fix it.
4683 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
4685 fprintf(stderr
, "Error cowing down to ref [%Lu, %u, %Lu]: %d\n",
4686 key
.objectid
, key
.type
, key
.offset
, ret
);
4690 fprintf(stderr
, "Well that's odd, we just found this key "
4691 "[%Lu, %u, %Lu]\n", key
.objectid
, key
.type
,
4695 leaf
= path
->nodes
[0];
4696 fi
= btrfs_item_ptr(leaf
, path
->slots
[0],
4697 struct btrfs_file_extent_item
);
4699 if (btrfs_file_extent_compression(leaf
, fi
) &&
4700 dback
->disk_bytenr
!= entry
->bytenr
) {
4701 fprintf(stderr
, "Ref doesn't match the record start and is "
4702 "compressed, please take a btrfs-image of this file "
4703 "system and send it to a btrfs developer so they can "
4704 "complete this functionality for bytenr %Lu\n",
4705 dback
->disk_bytenr
);
4709 if (dback
->node
.broken
&& dback
->disk_bytenr
!= entry
->bytenr
) {
4710 btrfs_set_file_extent_disk_bytenr(leaf
, fi
, entry
->bytenr
);
4711 } else if (dback
->disk_bytenr
> entry
->bytenr
) {
4712 u64 off_diff
, offset
;
4714 off_diff
= dback
->disk_bytenr
- entry
->bytenr
;
4715 offset
= btrfs_file_extent_offset(leaf
, fi
);
4716 if (dback
->disk_bytenr
+ offset
+
4717 btrfs_file_extent_num_bytes(leaf
, fi
) >
4718 entry
->bytenr
+ entry
->bytes
) {
4719 fprintf(stderr
, "Ref is past the entry end, please "
4720 "take a btrfs-image of this file system and "
4721 "send it to a btrfs developer, ref %Lu\n",
4722 dback
->disk_bytenr
);
4726 btrfs_set_file_extent_disk_bytenr(leaf
, fi
, entry
->bytenr
);
4727 btrfs_set_file_extent_offset(leaf
, fi
, offset
);
4728 } else if (dback
->disk_bytenr
< entry
->bytenr
) {
4731 offset
= btrfs_file_extent_offset(leaf
, fi
);
4732 if (dback
->disk_bytenr
+ offset
< entry
->bytenr
) {
4733 fprintf(stderr
, "Ref is before the entry start, please"
4734 " take a btrfs-image of this file system and "
4735 "send it to a btrfs developer, ref %Lu\n",
4736 dback
->disk_bytenr
);
4740 offset
+= dback
->disk_bytenr
;
4741 offset
-= entry
->bytenr
;
4742 btrfs_set_file_extent_disk_bytenr(leaf
, fi
, entry
->bytenr
);
4743 btrfs_set_file_extent_offset(leaf
, fi
, offset
);
4746 btrfs_set_file_extent_disk_num_bytes(leaf
, fi
, entry
->bytes
);
4749 * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
4750 * only do this if we aren't using compression, otherwise it's a
4753 if (!btrfs_file_extent_compression(leaf
, fi
))
4754 btrfs_set_file_extent_ram_bytes(leaf
, fi
, entry
->bytes
);
4756 printf("ram bytes may be wrong?\n");
4757 btrfs_mark_buffer_dirty(leaf
);
4758 btrfs_release_path(path
);
4762 static int verify_backrefs(struct btrfs_trans_handle
*trans
,
4763 struct btrfs_fs_info
*info
, struct btrfs_path
*path
,
4764 struct extent_record
*rec
)
4766 struct extent_backref
*back
;
4767 struct data_backref
*dback
;
4768 struct extent_entry
*entry
, *best
= NULL
;
4771 int broken_entries
= 0;
4776 * Metadata is easy and the backrefs should always agree on bytenr and
4777 * size, if not we've got bigger issues.
4782 list_for_each_entry(back
, &rec
->backrefs
, list
) {
4783 dback
= (struct data_backref
*)back
;
4785 * We only pay attention to backrefs that we found a real
4788 if (dback
->found_ref
== 0)
4790 if (back
->full_backref
)
4794 * For now we only catch when the bytes don't match, not the
4795 * bytenr. We can easily do this at the same time, but I want
4796 * to have a fs image to test on before we just add repair
4797 * functionality willy-nilly so we know we won't screw up the
4801 entry
= find_entry(&entries
, dback
->disk_bytenr
,
4804 entry
= malloc(sizeof(struct extent_entry
));
4809 memset(entry
, 0, sizeof(*entry
));
4810 entry
->bytenr
= dback
->disk_bytenr
;
4811 entry
->bytes
= dback
->bytes
;
4812 list_add_tail(&entry
->list
, &entries
);
4817 * If we only have on entry we may think the entries agree when
4818 * in reality they don't so we have to do some extra checking.
4820 if (dback
->disk_bytenr
!= rec
->start
||
4821 dback
->bytes
!= rec
->nr
|| back
->broken
)
4832 /* Yay all the backrefs agree, carry on good sir */
4833 if (nr_entries
<= 1 && !mismatch
)
4836 fprintf(stderr
, "attempting to repair backref discrepency for bytenr "
4837 "%Lu\n", rec
->start
);
4840 * First we want to see if the backrefs can agree amongst themselves who
4841 * is right, so figure out which one of the entries has the highest
4844 best
= find_most_right_entry(&entries
);
4847 * Ok so we may have an even split between what the backrefs think, so
4848 * this is where we use the extent ref to see what it thinks.
4851 entry
= find_entry(&entries
, rec
->start
, rec
->nr
);
4852 if (!entry
&& (!broken_entries
|| !rec
->found_rec
)) {
4853 fprintf(stderr
, "Backrefs don't agree with each other "
4854 "and extent record doesn't agree with anybody,"
4855 " so we can't fix bytenr %Lu bytes %Lu\n",
4856 rec
->start
, rec
->nr
);
4859 } else if (!entry
) {
4861 * Ok our backrefs were broken, we'll assume this is the
4862 * correct value and add an entry for this range.
4864 entry
= malloc(sizeof(struct extent_entry
));
4869 memset(entry
, 0, sizeof(*entry
));
4870 entry
->bytenr
= rec
->start
;
4871 entry
->bytes
= rec
->nr
;
4872 list_add_tail(&entry
->list
, &entries
);
4876 best
= find_most_right_entry(&entries
);
4878 fprintf(stderr
, "Backrefs and extent record evenly "
4879 "split on who is right, this is going to "
4880 "require user input to fix bytenr %Lu bytes "
4881 "%Lu\n", rec
->start
, rec
->nr
);
4888 * I don't think this can happen currently as we'll abort() if we catch
4889 * this case higher up, but in case somebody removes that we still can't
4890 * deal with it properly here yet, so just bail out of that's the case.
4892 if (best
->bytenr
!= rec
->start
) {
4893 fprintf(stderr
, "Extent start and backref starts don't match, "
4894 "please use btrfs-image on this file system and send "
4895 "it to a btrfs developer so they can make fsck fix "
4896 "this particular case. bytenr is %Lu, bytes is %Lu\n",
4897 rec
->start
, rec
->nr
);
4903 * Ok great we all agreed on an extent record, let's go find the real
4904 * references and fix up the ones that don't match.
4906 list_for_each_entry(back
, &rec
->backrefs
, list
) {
4907 dback
= (struct data_backref
*)back
;
4910 * Still ignoring backrefs that don't have a real ref attached
4913 if (dback
->found_ref
== 0)
4915 if (back
->full_backref
)
4918 if (dback
->bytes
== best
->bytes
&&
4919 dback
->disk_bytenr
== best
->bytenr
)
4922 ret
= repair_ref(trans
, info
, path
, dback
, best
);
4928 * Ok we messed with the actual refs, which means we need to drop our
4929 * entire cache and go back and rescan. I know this is a huge pain and
4930 * adds a lot of extra work, but it's the only way to be safe. Once all
4931 * the backrefs agree we may not need to do anything to the extent
4936 while (!list_empty(&entries
)) {
4937 entry
= list_entry(entries
.next
, struct extent_entry
, list
);
4938 list_del_init(&entry
->list
);
4944 static int process_duplicates(struct btrfs_root
*root
,
4945 struct cache_tree
*extent_cache
,
4946 struct extent_record
*rec
)
4948 struct extent_record
*good
, *tmp
;
4949 struct cache_extent
*cache
;
4953 * If we found a extent record for this extent then return, or if we
4954 * have more than one duplicate we are likely going to need to delete
4957 if (rec
->found_rec
|| rec
->num_duplicates
> 1)
4960 /* Shouldn't happen but just in case */
4961 BUG_ON(!rec
->num_duplicates
);
4964 * So this happens if we end up with a backref that doesn't match the
4965 * actual extent entry. So either the backref is bad or the extent
4966 * entry is bad. Either way we want to have the extent_record actually
4967 * reflect what we found in the extent_tree, so we need to take the
4968 * duplicate out and use that as the extent_record since the only way we
4969 * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
4971 remove_cache_extent(extent_cache
, &rec
->cache
);
4973 good
= list_entry(rec
->dups
.next
, struct extent_record
, list
);
4974 list_del_init(&good
->list
);
4975 INIT_LIST_HEAD(&good
->backrefs
);
4976 INIT_LIST_HEAD(&good
->dups
);
4977 good
->cache
.start
= good
->start
;
4978 good
->cache
.size
= good
->nr
;
4979 good
->content_checked
= 0;
4980 good
->owner_ref_checked
= 0;
4981 good
->num_duplicates
= 0;
4982 good
->refs
= rec
->refs
;
4983 list_splice_init(&rec
->backrefs
, &good
->backrefs
);
4985 cache
= lookup_cache_extent(extent_cache
, good
->start
,
4989 tmp
= container_of(cache
, struct extent_record
, cache
);
4992 * If we find another overlapping extent and it's found_rec is
4993 * set then it's a duplicate and we need to try and delete
4996 if (tmp
->found_rec
|| tmp
->num_duplicates
> 0) {
4997 if (list_empty(&good
->list
))
4998 list_add_tail(&good
->list
,
4999 &duplicate_extents
);
5000 good
->num_duplicates
+= tmp
->num_duplicates
+ 1;
5001 list_splice_init(&tmp
->dups
, &good
->dups
);
5002 list_del_init(&tmp
->list
);
5003 list_add_tail(&tmp
->list
, &good
->dups
);
5004 remove_cache_extent(extent_cache
, &tmp
->cache
);
5009 * Ok we have another non extent item backed extent rec, so lets
5010 * just add it to this extent and carry on like we did above.
5012 good
->refs
+= tmp
->refs
;
5013 list_splice_init(&tmp
->backrefs
, &good
->backrefs
);
5014 remove_cache_extent(extent_cache
, &tmp
->cache
);
5017 ret
= insert_cache_extent(extent_cache
, &good
->cache
);
5020 return good
->num_duplicates
? 0 : 1;
5023 static int delete_duplicate_records(struct btrfs_trans_handle
*trans
,
5024 struct btrfs_root
*root
,
5025 struct extent_record
*rec
)
5027 LIST_HEAD(delete_list
);
5028 struct btrfs_path
*path
;
5029 struct extent_record
*tmp
, *good
, *n
;
5032 struct btrfs_key key
;
5034 path
= btrfs_alloc_path();
5041 /* Find the record that covers all of the duplicates. */
5042 list_for_each_entry(tmp
, &rec
->dups
, list
) {
5043 if (good
->start
< tmp
->start
)
5045 if (good
->nr
> tmp
->nr
)
5048 if (tmp
->start
+ tmp
->nr
< good
->start
+ good
->nr
) {
5049 fprintf(stderr
, "Ok we have overlapping extents that "
5050 "aren't completely covered by eachother, this "
5051 "is going to require more careful thought. "
5052 "The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
5053 tmp
->start
, tmp
->nr
, good
->start
, good
->nr
);
5060 list_add_tail(&rec
->list
, &delete_list
);
5062 list_for_each_entry_safe(tmp
, n
, &rec
->dups
, list
) {
5065 list_move_tail(&tmp
->list
, &delete_list
);
5068 root
= root
->fs_info
->extent_root
;
5069 list_for_each_entry(tmp
, &delete_list
, list
) {
5070 if (tmp
->found_rec
== 0)
5072 key
.objectid
= tmp
->start
;
5073 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
5074 key
.offset
= tmp
->nr
;
5076 /* Shouldn't happen but just in case */
5077 if (tmp
->metadata
) {
5078 fprintf(stderr
, "Well this shouldn't happen, extent "
5079 "record overlaps but is metadata? "
5080 "[%Lu, %Lu]\n", tmp
->start
, tmp
->nr
);
5084 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
5090 ret
= btrfs_del_item(trans
, root
, path
);
5093 btrfs_release_path(path
);
5098 while (!list_empty(&delete_list
)) {
5099 tmp
= list_entry(delete_list
.next
, struct extent_record
, list
);
5100 list_del_init(&tmp
->list
);
5106 while (!list_empty(&rec
->dups
)) {
5107 tmp
= list_entry(rec
->dups
.next
, struct extent_record
, list
);
5108 list_del_init(&tmp
->list
);
5112 btrfs_free_path(path
);
5114 if (!ret
&& !nr_del
)
5115 rec
->num_duplicates
= 0;
5117 return ret
? ret
: nr_del
;
5120 static int find_possible_backrefs(struct btrfs_trans_handle
*trans
,
5121 struct btrfs_fs_info
*info
,
5122 struct btrfs_path
*path
,
5123 struct cache_tree
*extent_cache
,
5124 struct extent_record
*rec
)
5126 struct btrfs_root
*root
;
5127 struct extent_backref
*back
;
5128 struct data_backref
*dback
;
5129 struct cache_extent
*cache
;
5130 struct btrfs_file_extent_item
*fi
;
5131 struct btrfs_key key
;
5135 list_for_each_entry(back
, &rec
->backrefs
, list
) {
5136 dback
= (struct data_backref
*)back
;
5138 /* We found this one, we don't need to do a lookup */
5139 if (dback
->found_ref
)
5141 /* Don't care about full backrefs (poor unloved backrefs) */
5142 if (back
->full_backref
)
5144 key
.objectid
= dback
->root
;
5145 key
.type
= BTRFS_ROOT_ITEM_KEY
;
5146 key
.offset
= (u64
)-1;
5148 root
= btrfs_read_fs_root(info
, &key
);
5150 /* No root, definitely a bad ref, skip */
5151 if (IS_ERR(root
) && PTR_ERR(root
) == -ENOENT
)
5153 /* Other err, exit */
5155 return PTR_ERR(root
);
5157 key
.objectid
= dback
->owner
;
5158 key
.type
= BTRFS_EXTENT_DATA_KEY
;
5159 key
.offset
= dback
->offset
;
5160 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
5162 btrfs_release_path(path
);
5165 /* Didn't find it, we can carry on */
5170 fi
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
5171 struct btrfs_file_extent_item
);
5172 bytenr
= btrfs_file_extent_disk_bytenr(path
->nodes
[0], fi
);
5173 bytes
= btrfs_file_extent_disk_num_bytes(path
->nodes
[0], fi
);
5174 btrfs_release_path(path
);
5175 cache
= lookup_cache_extent(extent_cache
, bytenr
, 1);
5177 struct extent_record
*tmp
;
5178 tmp
= container_of(cache
, struct extent_record
, cache
);
5181 * If we found an extent record for the bytenr for this
5182 * particular backref then we can't add it to our
5183 * current extent record. We only want to add backrefs
5184 * that don't have a corresponding extent item in the
5185 * extent tree since they likely belong to this record
5186 * and we need to fix it if it doesn't match bytenrs.
5192 dback
->found_ref
+= 1;
5193 dback
->disk_bytenr
= bytenr
;
5194 dback
->bytes
= bytes
;
5197 * Set this so the verify backref code knows not to trust the
5198 * values in this backref.
5207 * when an incorrect extent item is found, this will delete
5208 * all of the existing entries for it and recreate them
5209 * based on what the tree scan found.
5211 static int fixup_extent_refs(struct btrfs_trans_handle
*trans
,
5212 struct btrfs_fs_info
*info
,
5213 struct cache_tree
*extent_cache
,
5214 struct extent_record
*rec
)
5217 struct btrfs_path
*path
;
5218 struct list_head
*cur
= rec
->backrefs
.next
;
5219 struct cache_extent
*cache
;
5220 struct extent_backref
*back
;
5225 * remember our flags for recreating the extent.
5226 * FIXME, if we have cleared extent tree, we can not
5227 * lookup extent info in extent tree.
5229 if (!init_extent_tree
) {
5230 ret
= btrfs_lookup_extent_info(NULL
, info
->extent_root
,
5231 rec
->start
, rec
->max_size
,
5232 rec
->metadata
, NULL
, &flags
);
5239 path
= btrfs_alloc_path();
5243 if (rec
->refs
!= rec
->extent_item_refs
&& !rec
->metadata
) {
5245 * Sometimes the backrefs themselves are so broken they don't
5246 * get attached to any meaningful rec, so first go back and
5247 * check any of our backrefs that we couldn't find and throw
5248 * them into the list if we find the backref so that
5249 * verify_backrefs can figure out what to do.
5251 ret
= find_possible_backrefs(trans
, info
, path
, extent_cache
,
5257 /* step one, make sure all of the backrefs agree */
5258 ret
= verify_backrefs(trans
, info
, path
, rec
);
5262 /* step two, delete all the existing records */
5263 ret
= delete_extent_records(trans
, info
->extent_root
, path
,
5264 rec
->start
, rec
->max_size
);
5269 /* was this block corrupt? If so, don't add references to it */
5270 cache
= lookup_cache_extent(info
->corrupt_blocks
,
5271 rec
->start
, rec
->max_size
);
5277 /* step three, recreate all the refs we did find */
5278 while(cur
!= &rec
->backrefs
) {
5279 back
= list_entry(cur
, struct extent_backref
, list
);
5283 * if we didn't find any references, don't create a
5286 if (!back
->found_ref
)
5289 ret
= record_extent(trans
, info
, path
, rec
, back
, allocated
, flags
);
5296 btrfs_free_path(path
);
5300 /* right now we only prune from the extent allocation tree */
5301 static int prune_one_block(struct btrfs_trans_handle
*trans
,
5302 struct btrfs_fs_info
*info
,
5303 struct btrfs_corrupt_block
*corrupt
)
5306 struct btrfs_path path
;
5307 struct extent_buffer
*eb
;
5311 int level
= corrupt
->level
+ 1;
5313 btrfs_init_path(&path
);
5315 /* we want to stop at the parent to our busted block */
5316 path
.lowest_level
= level
;
5318 ret
= btrfs_search_slot(trans
, info
->extent_root
,
5319 &corrupt
->key
, &path
, -1, 1);
5324 eb
= path
.nodes
[level
];
5331 * hopefully the search gave us the block we want to prune,
5332 * lets try that first
5334 slot
= path
.slots
[level
];
5335 found
= btrfs_node_blockptr(eb
, slot
);
5336 if (found
== corrupt
->cache
.start
)
5339 nritems
= btrfs_header_nritems(eb
);
5341 /* the search failed, lets scan this node and hope we find it */
5342 for (slot
= 0; slot
< nritems
; slot
++) {
5343 found
= btrfs_node_blockptr(eb
, slot
);
5344 if (found
== corrupt
->cache
.start
)
5348 * we couldn't find the bad block. TODO, search all the nodes for pointers
5351 if (eb
== info
->extent_root
->node
) {
5356 btrfs_release_path(&path
);
5361 printk("deleting pointer to block %Lu\n", corrupt
->cache
.start
);
5362 ret
= btrfs_del_ptr(trans
, info
->extent_root
, &path
, level
, slot
);
5365 btrfs_release_path(&path
);
5369 static int prune_corrupt_blocks(struct btrfs_trans_handle
*trans
,
5370 struct btrfs_fs_info
*info
)
5372 struct cache_extent
*cache
;
5373 struct btrfs_corrupt_block
*corrupt
;
5375 cache
= search_cache_extent(info
->corrupt_blocks
, 0);
5379 corrupt
= container_of(cache
, struct btrfs_corrupt_block
, cache
);
5380 prune_one_block(trans
, info
, corrupt
);
5381 cache
= next_cache_extent(cache
);
5386 static void free_corrupt_block(struct cache_extent
*cache
)
5388 struct btrfs_corrupt_block
*corrupt
;
5390 corrupt
= container_of(cache
, struct btrfs_corrupt_block
, cache
);
5394 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks
, free_corrupt_block
);
5396 static void reset_cached_block_groups(struct btrfs_fs_info
*fs_info
)
5398 struct btrfs_block_group_cache
*cache
;
5403 ret
= find_first_extent_bit(&fs_info
->free_space_cache
, 0,
5404 &start
, &end
, EXTENT_DIRTY
);
5407 clear_extent_dirty(&fs_info
->free_space_cache
, start
, end
,
5413 cache
= btrfs_lookup_first_block_group(fs_info
, start
);
5418 start
= cache
->key
.objectid
+ cache
->key
.offset
;
5422 static int check_extent_refs(struct btrfs_trans_handle
*trans
,
5423 struct btrfs_root
*root
,
5424 struct cache_tree
*extent_cache
)
5426 struct extent_record
*rec
;
5427 struct cache_extent
*cache
;
5435 * if we're doing a repair, we have to make sure
5436 * we don't allocate from the problem extents.
5437 * In the worst case, this will be all the
5440 cache
= search_cache_extent(extent_cache
, 0);
5442 rec
= container_of(cache
, struct extent_record
, cache
);
5443 btrfs_pin_extent(root
->fs_info
,
5444 rec
->start
, rec
->max_size
);
5445 cache
= next_cache_extent(cache
);
5448 /* pin down all the corrupted blocks too */
5449 cache
= search_cache_extent(root
->fs_info
->corrupt_blocks
, 0);
5451 btrfs_pin_extent(root
->fs_info
,
5452 cache
->start
, cache
->size
);
5453 cache
= next_cache_extent(cache
);
5455 prune_corrupt_blocks(trans
, root
->fs_info
);
5456 reset_cached_block_groups(root
->fs_info
);
5460 * We need to delete any duplicate entries we find first otherwise we
5461 * could mess up the extent tree when we have backrefs that actually
5462 * belong to a different extent item and not the weird duplicate one.
5464 while (repair
&& !list_empty(&duplicate_extents
)) {
5465 rec
= list_entry(duplicate_extents
.next
, struct extent_record
,
5467 list_del_init(&rec
->list
);
5469 /* Sometimes we can find a backref before we find an actual
5470 * extent, so we need to process it a little bit to see if there
5471 * truly are multiple EXTENT_ITEM_KEY's for the same range, or
5472 * if this is a backref screwup. If we need to delete stuff
5473 * process_duplicates() will return 0, otherwise it will return
5476 if (process_duplicates(root
, extent_cache
, rec
))
5478 ret
= delete_duplicate_records(trans
, root
, rec
);
5482 * delete_duplicate_records will return the number of entries
5483 * deleted, so if it's greater than 0 then we know we actually
5484 * did something and we need to remove.
5495 cache
= search_cache_extent(extent_cache
, 0);
5498 rec
= container_of(cache
, struct extent_record
, cache
);
5499 if (rec
->num_duplicates
) {
5500 fprintf(stderr
, "extent item %llu has multiple extent "
5501 "items\n", (unsigned long long)rec
->start
);
5505 if (rec
->refs
!= rec
->extent_item_refs
) {
5506 fprintf(stderr
, "ref mismatch on [%llu %llu] ",
5507 (unsigned long long)rec
->start
,
5508 (unsigned long long)rec
->nr
);
5509 fprintf(stderr
, "extent item %llu, found %llu\n",
5510 (unsigned long long)rec
->extent_item_refs
,
5511 (unsigned long long)rec
->refs
);
5512 if (!fixed
&& repair
) {
5513 ret
= fixup_extent_refs(trans
, root
->fs_info
,
5522 if (all_backpointers_checked(rec
, 1)) {
5523 fprintf(stderr
, "backpointer mismatch on [%llu %llu]\n",
5524 (unsigned long long)rec
->start
,
5525 (unsigned long long)rec
->nr
);
5527 if (!fixed
&& repair
) {
5528 ret
= fixup_extent_refs(trans
, root
->fs_info
,
5537 if (!rec
->owner_ref_checked
) {
5538 fprintf(stderr
, "owner ref check failed [%llu %llu]\n",
5539 (unsigned long long)rec
->start
,
5540 (unsigned long long)rec
->nr
);
5541 if (!fixed
&& repair
) {
5542 ret
= fixup_extent_refs(trans
, root
->fs_info
,
5551 remove_cache_extent(extent_cache
, cache
);
5552 free_all_extent_backrefs(rec
);
5557 if (ret
&& ret
!= -EAGAIN
) {
5558 fprintf(stderr
, "failed to repair damaged filesystem, aborting\n");
5561 btrfs_fix_block_accounting(trans
, root
);
5564 fprintf(stderr
, "repaired damaged extent references\n");
5570 u64
calc_stripe_length(u64 type
, u64 length
, int num_stripes
)
5574 if (type
& BTRFS_BLOCK_GROUP_RAID0
) {
5575 stripe_size
= length
;
5576 stripe_size
/= num_stripes
;
5577 } else if (type
& BTRFS_BLOCK_GROUP_RAID10
) {
5578 stripe_size
= length
* 2;
5579 stripe_size
/= num_stripes
;
5580 } else if (type
& BTRFS_BLOCK_GROUP_RAID5
) {
5581 stripe_size
= length
;
5582 stripe_size
/= (num_stripes
- 1);
5583 } else if (type
& BTRFS_BLOCK_GROUP_RAID6
) {
5584 stripe_size
= length
;
5585 stripe_size
/= (num_stripes
- 2);
5587 stripe_size
= length
;
5592 static int check_chunk_refs(struct chunk_record
*chunk_rec
,
5593 struct block_group_tree
*block_group_cache
,
5594 struct device_extent_tree
*dev_extent_cache
,
5597 struct cache_extent
*block_group_item
;
5598 struct block_group_record
*block_group_rec
;
5599 struct cache_extent
*dev_extent_item
;
5600 struct device_extent_record
*dev_extent_rec
;
5607 block_group_item
= lookup_cache_extent(&block_group_cache
->tree
,
5610 if (block_group_item
) {
5611 block_group_rec
= container_of(block_group_item
,
5612 struct block_group_record
,
5614 if (chunk_rec
->length
!= block_group_rec
->offset
||
5615 chunk_rec
->offset
!= block_group_rec
->objectid
||
5616 chunk_rec
->type_flags
!= block_group_rec
->flags
) {
5619 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
5620 chunk_rec
->objectid
,
5625 chunk_rec
->type_flags
,
5626 block_group_rec
->objectid
,
5627 block_group_rec
->type
,
5628 block_group_rec
->offset
,
5629 block_group_rec
->offset
,
5630 block_group_rec
->objectid
,
5631 block_group_rec
->flags
);
5634 list_del_init(&block_group_rec
->list
);
5635 chunk_rec
->bg_rec
= block_group_rec
;
5640 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
5641 chunk_rec
->objectid
,
5646 chunk_rec
->type_flags
);
5650 length
= calc_stripe_length(chunk_rec
->type_flags
, chunk_rec
->length
,
5651 chunk_rec
->num_stripes
);
5652 for (i
= 0; i
< chunk_rec
->num_stripes
; ++i
) {
5653 devid
= chunk_rec
->stripes
[i
].devid
;
5654 offset
= chunk_rec
->stripes
[i
].offset
;
5655 dev_extent_item
= lookup_cache_extent2(&dev_extent_cache
->tree
,
5656 devid
, offset
, length
);
5657 if (dev_extent_item
) {
5658 dev_extent_rec
= container_of(dev_extent_item
,
5659 struct device_extent_record
,
5661 if (dev_extent_rec
->objectid
!= devid
||
5662 dev_extent_rec
->offset
!= offset
||
5663 dev_extent_rec
->chunk_offset
!= chunk_rec
->offset
||
5664 dev_extent_rec
->length
!= length
) {
5667 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
5668 chunk_rec
->objectid
,
5671 chunk_rec
->stripes
[i
].devid
,
5672 chunk_rec
->stripes
[i
].offset
,
5673 dev_extent_rec
->objectid
,
5674 dev_extent_rec
->offset
,
5675 dev_extent_rec
->length
);
5678 list_move(&dev_extent_rec
->chunk_list
,
5679 &chunk_rec
->dextents
);
5684 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
5685 chunk_rec
->objectid
,
5688 chunk_rec
->stripes
[i
].devid
,
5689 chunk_rec
->stripes
[i
].offset
);
5696 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
5697 int check_chunks(struct cache_tree
*chunk_cache
,
5698 struct block_group_tree
*block_group_cache
,
5699 struct device_extent_tree
*dev_extent_cache
,
5700 struct list_head
*good
, struct list_head
*bad
, int silent
)
5702 struct cache_extent
*chunk_item
;
5703 struct chunk_record
*chunk_rec
;
5704 struct block_group_record
*bg_rec
;
5705 struct device_extent_record
*dext_rec
;
5709 chunk_item
= first_cache_extent(chunk_cache
);
5710 while (chunk_item
) {
5711 chunk_rec
= container_of(chunk_item
, struct chunk_record
,
5713 err
= check_chunk_refs(chunk_rec
, block_group_cache
,
5714 dev_extent_cache
, silent
);
5718 list_add_tail(&chunk_rec
->list
, bad
);
5721 list_add_tail(&chunk_rec
->list
, good
);
5724 chunk_item
= next_cache_extent(chunk_item
);
5727 list_for_each_entry(bg_rec
, &block_group_cache
->block_groups
, list
) {
5730 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
5738 list_for_each_entry(dext_rec
, &dev_extent_cache
->no_chunk_orphans
,
5742 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
5753 static int check_device_used(struct device_record
*dev_rec
,
5754 struct device_extent_tree
*dext_cache
)
5756 struct cache_extent
*cache
;
5757 struct device_extent_record
*dev_extent_rec
;
5760 cache
= search_cache_extent2(&dext_cache
->tree
, dev_rec
->devid
, 0);
5762 dev_extent_rec
= container_of(cache
,
5763 struct device_extent_record
,
5765 if (dev_extent_rec
->objectid
!= dev_rec
->devid
)
5768 list_del(&dev_extent_rec
->device_list
);
5769 total_byte
+= dev_extent_rec
->length
;
5770 cache
= next_cache_extent(cache
);
5773 if (total_byte
!= dev_rec
->byte_used
) {
5775 "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
5776 total_byte
, dev_rec
->byte_used
, dev_rec
->objectid
,
5777 dev_rec
->type
, dev_rec
->offset
);
5784 /* check btrfs_dev_item -> btrfs_dev_extent */
5785 static int check_devices(struct rb_root
*dev_cache
,
5786 struct device_extent_tree
*dev_extent_cache
)
5788 struct rb_node
*dev_node
;
5789 struct device_record
*dev_rec
;
5790 struct device_extent_record
*dext_rec
;
5794 dev_node
= rb_first(dev_cache
);
5796 dev_rec
= container_of(dev_node
, struct device_record
, node
);
5797 err
= check_device_used(dev_rec
, dev_extent_cache
);
5801 dev_node
= rb_next(dev_node
);
5803 list_for_each_entry(dext_rec
, &dev_extent_cache
->no_device_orphans
,
5806 "Device extent[%llu, %llu, %llu] didn't find its device.\n",
5807 dext_rec
->objectid
, dext_rec
->offset
, dext_rec
->length
);
5814 static int check_chunks_and_extents(struct btrfs_root
*root
)
5816 struct rb_root dev_cache
;
5817 struct cache_tree chunk_cache
;
5818 struct block_group_tree block_group_cache
;
5819 struct device_extent_tree dev_extent_cache
;
5820 struct cache_tree extent_cache
;
5821 struct cache_tree seen
;
5822 struct cache_tree pending
;
5823 struct cache_tree reada
;
5824 struct cache_tree nodes
;
5825 struct cache_tree corrupt_blocks
;
5826 struct btrfs_path path
;
5827 struct btrfs_key key
;
5828 struct btrfs_key found_key
;
5831 struct block_info
*bits
;
5833 struct extent_buffer
*leaf
;
5834 struct btrfs_trans_handle
*trans
= NULL
;
5836 struct btrfs_root_item ri
;
5837 struct list_head dropping_trees
;
5839 dev_cache
= RB_ROOT
;
5840 cache_tree_init(&chunk_cache
);
5841 block_group_tree_init(&block_group_cache
);
5842 device_extent_tree_init(&dev_extent_cache
);
5844 cache_tree_init(&extent_cache
);
5845 cache_tree_init(&seen
);
5846 cache_tree_init(&pending
);
5847 cache_tree_init(&nodes
);
5848 cache_tree_init(&reada
);
5849 cache_tree_init(&corrupt_blocks
);
5850 INIT_LIST_HEAD(&dropping_trees
);
5853 trans
= btrfs_start_transaction(root
, 1);
5854 if (IS_ERR(trans
)) {
5855 fprintf(stderr
, "Error starting transaction\n");
5856 return PTR_ERR(trans
);
5858 root
->fs_info
->fsck_extent_cache
= &extent_cache
;
5859 root
->fs_info
->free_extent_hook
= free_extent_hook
;
5860 root
->fs_info
->corrupt_blocks
= &corrupt_blocks
;
5864 bits
= malloc(bits_nr
* sizeof(struct block_info
));
5871 add_root_to_pending(root
->fs_info
->tree_root
->node
,
5872 &extent_cache
, &pending
, &seen
, &nodes
,
5873 &root
->fs_info
->tree_root
->root_key
);
5875 add_root_to_pending(root
->fs_info
->chunk_root
->node
,
5876 &extent_cache
, &pending
, &seen
, &nodes
,
5877 &root
->fs_info
->chunk_root
->root_key
);
5879 btrfs_init_path(&path
);
5882 btrfs_set_key_type(&key
, BTRFS_ROOT_ITEM_KEY
);
5883 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
,
5887 leaf
= path
.nodes
[0];
5888 slot
= path
.slots
[0];
5889 if (slot
>= btrfs_header_nritems(path
.nodes
[0])) {
5890 ret
= btrfs_next_leaf(root
, &path
);
5893 leaf
= path
.nodes
[0];
5894 slot
= path
.slots
[0];
5896 btrfs_item_key_to_cpu(leaf
, &found_key
, path
.slots
[0]);
5897 if (btrfs_key_type(&found_key
) == BTRFS_ROOT_ITEM_KEY
) {
5898 unsigned long offset
;
5899 struct extent_buffer
*buf
;
5901 offset
= btrfs_item_ptr_offset(leaf
, path
.slots
[0]);
5902 read_extent_buffer(leaf
, &ri
, offset
, sizeof(ri
));
5903 if (btrfs_disk_key_objectid(&ri
.drop_progress
) == 0) {
5904 buf
= read_tree_block(root
->fs_info
->tree_root
,
5905 btrfs_root_bytenr(&ri
),
5906 btrfs_level_size(root
,
5907 btrfs_root_level(&ri
)),
5913 add_root_to_pending(buf
, &extent_cache
,
5914 &pending
, &seen
, &nodes
,
5916 free_extent_buffer(buf
);
5918 struct dropping_root_item_record
*dri_rec
;
5919 dri_rec
= malloc(sizeof(*dri_rec
));
5924 memcpy(&dri_rec
->ri
, &ri
, sizeof(ri
));
5925 memcpy(&dri_rec
->found_key
, &found_key
,
5927 list_add_tail(&dri_rec
->list
, &dropping_trees
);
5932 btrfs_release_path(&path
);
5934 ret
= run_next_block(trans
, root
, bits
, bits_nr
, &last
,
5935 &pending
, &seen
, &reada
, &nodes
,
5936 &extent_cache
, &chunk_cache
, &dev_cache
,
5937 &block_group_cache
, &dev_extent_cache
,
5943 while (!list_empty(&dropping_trees
)) {
5944 struct dropping_root_item_record
*rec
;
5945 struct extent_buffer
*buf
;
5946 rec
= list_entry(dropping_trees
.next
,
5947 struct dropping_root_item_record
, list
);
5953 buf
= read_tree_block(root
->fs_info
->tree_root
,
5954 btrfs_root_bytenr(&rec
->ri
),
5955 btrfs_level_size(root
,
5956 btrfs_root_level(&rec
->ri
)), 0);
5961 add_root_to_pending(buf
, &extent_cache
, &pending
,
5962 &seen
, &nodes
, &rec
->found_key
);
5964 ret
= run_next_block(trans
, root
, bits
, bits_nr
, &last
,
5965 &pending
, &seen
, &reada
,
5966 &nodes
, &extent_cache
,
5967 &chunk_cache
, &dev_cache
,
5974 free_extent_buffer(buf
);
5975 list_del(&rec
->list
);
5980 ret
= check_extent_refs(trans
, root
, &extent_cache
);
5981 if (ret
== -EAGAIN
) {
5982 ret
= btrfs_commit_transaction(trans
, root
);
5986 trans
= btrfs_start_transaction(root
, 1);
5987 if (IS_ERR(trans
)) {
5988 ret
= PTR_ERR(trans
);
5992 free_corrupt_blocks_tree(root
->fs_info
->corrupt_blocks
);
5993 free_extent_cache_tree(&seen
);
5994 free_extent_cache_tree(&pending
);
5995 free_extent_cache_tree(&reada
);
5996 free_extent_cache_tree(&nodes
);
5997 free_extent_record_cache(root
->fs_info
, &extent_cache
);
6001 err
= check_chunks(&chunk_cache
, &block_group_cache
,
6002 &dev_extent_cache
, NULL
, NULL
, 0);
6006 err
= check_devices(&dev_cache
, &dev_extent_cache
);
6011 err
= btrfs_commit_transaction(trans
, root
);
6017 free_corrupt_blocks_tree(root
->fs_info
->corrupt_blocks
);
6018 root
->fs_info
->fsck_extent_cache
= NULL
;
6019 root
->fs_info
->free_extent_hook
= NULL
;
6020 root
->fs_info
->corrupt_blocks
= NULL
;
6023 free_chunk_cache_tree(&chunk_cache
);
6024 free_device_cache_tree(&dev_cache
);
6025 free_block_group_tree(&block_group_cache
);
6026 free_device_extent_tree(&dev_extent_cache
);
6027 free_extent_cache_tree(&seen
);
6028 free_extent_cache_tree(&pending
);
6029 free_extent_cache_tree(&reada
);
6030 free_extent_cache_tree(&nodes
);
6034 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle
*trans
,
6035 struct btrfs_root
*root
, int overwrite
)
6037 struct extent_buffer
*c
;
6038 struct extent_buffer
*old
= root
->node
;
6041 struct btrfs_disk_key disk_key
= {0,0,0};
6047 extent_buffer_get(c
);
6050 c
= btrfs_alloc_free_block(trans
, root
,
6051 btrfs_level_size(root
, 0),
6052 root
->root_key
.objectid
,
6053 &disk_key
, level
, 0, 0);
6056 extent_buffer_get(c
);
6060 memset_extent_buffer(c
, 0, 0, sizeof(struct btrfs_header
));
6061 btrfs_set_header_level(c
, level
);
6062 btrfs_set_header_bytenr(c
, c
->start
);
6063 btrfs_set_header_generation(c
, trans
->transid
);
6064 btrfs_set_header_backref_rev(c
, BTRFS_MIXED_BACKREF_REV
);
6065 btrfs_set_header_owner(c
, root
->root_key
.objectid
);
6067 write_extent_buffer(c
, root
->fs_info
->fsid
,
6068 btrfs_header_fsid(), BTRFS_FSID_SIZE
);
6070 write_extent_buffer(c
, root
->fs_info
->chunk_tree_uuid
,
6071 btrfs_header_chunk_tree_uuid(c
),
6074 btrfs_mark_buffer_dirty(c
);
6076 * this case can happen in the following case:
6078 * 1.overwrite previous root.
6080 * 2.reinit reloc data root, this is because we skip pin
6081 * down reloc data tree before which means we can allocate
6082 * same block bytenr here.
6084 if (old
->start
== c
->start
) {
6085 btrfs_set_root_generation(&root
->root_item
,
6087 root
->root_item
.level
= btrfs_header_level(root
->node
);
6088 ret
= btrfs_update_root(trans
, root
->fs_info
->tree_root
,
6089 &root
->root_key
, &root
->root_item
);
6091 free_extent_buffer(c
);
6095 free_extent_buffer(old
);
6097 add_root_to_dirty_list(root
);
6101 static int pin_down_tree_blocks(struct btrfs_fs_info
*fs_info
,
6102 struct extent_buffer
*eb
, int tree_root
)
6104 struct extent_buffer
*tmp
;
6105 struct btrfs_root_item
*ri
;
6106 struct btrfs_key key
;
6109 int level
= btrfs_header_level(eb
);
6114 btrfs_pin_extent(fs_info
, eb
->start
, eb
->len
);
6116 leafsize
= btrfs_super_leafsize(fs_info
->super_copy
);
6117 nritems
= btrfs_header_nritems(eb
);
6118 for (i
= 0; i
< nritems
; i
++) {
6120 btrfs_item_key_to_cpu(eb
, &key
, i
);
6121 if (key
.type
!= BTRFS_ROOT_ITEM_KEY
)
6123 /* Skip the extent root and reloc roots */
6124 if (key
.objectid
== BTRFS_EXTENT_TREE_OBJECTID
||
6125 key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
||
6126 key
.objectid
== BTRFS_DATA_RELOC_TREE_OBJECTID
)
6128 ri
= btrfs_item_ptr(eb
, i
, struct btrfs_root_item
);
6129 bytenr
= btrfs_disk_root_bytenr(eb
, ri
);
6132 * If at any point we start needing the real root we
6133 * will have to build a stump root for the root we are
6134 * in, but for now this doesn't actually use the root so
6135 * just pass in extent_root.
6137 tmp
= read_tree_block(fs_info
->extent_root
, bytenr
,
6140 fprintf(stderr
, "Error reading root block\n");
6143 ret
= pin_down_tree_blocks(fs_info
, tmp
, 0);
6144 free_extent_buffer(tmp
);
6148 bytenr
= btrfs_node_blockptr(eb
, i
);
6150 /* If we aren't the tree root don't read the block */
6151 if (level
== 1 && !tree_root
) {
6152 btrfs_pin_extent(fs_info
, bytenr
, leafsize
);
6156 tmp
= read_tree_block(fs_info
->extent_root
, bytenr
,
6159 fprintf(stderr
, "Error reading tree block\n");
6162 ret
= pin_down_tree_blocks(fs_info
, tmp
, tree_root
);
6163 free_extent_buffer(tmp
);
6172 static int pin_metadata_blocks(struct btrfs_fs_info
*fs_info
)
6176 ret
= pin_down_tree_blocks(fs_info
, fs_info
->chunk_root
->node
, 0);
6180 return pin_down_tree_blocks(fs_info
, fs_info
->tree_root
->node
, 1);
6183 static int reset_block_groups(struct btrfs_fs_info
*fs_info
)
6185 struct btrfs_block_group_cache
*cache
;
6186 struct btrfs_path
*path
;
6187 struct extent_buffer
*leaf
;
6188 struct btrfs_chunk
*chunk
;
6189 struct btrfs_key key
;
6193 path
= btrfs_alloc_path();
6198 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
6201 ret
= btrfs_search_slot(NULL
, fs_info
->chunk_root
, &key
, path
, 0, 0);
6203 btrfs_free_path(path
);
6208 * We do this in case the block groups were screwed up and had alloc
6209 * bits that aren't actually set on the chunks. This happens with
6210 * restored images every time and could happen in real life I guess.
6212 fs_info
->avail_data_alloc_bits
= 0;
6213 fs_info
->avail_metadata_alloc_bits
= 0;
6214 fs_info
->avail_system_alloc_bits
= 0;
6216 /* First we need to create the in-memory block groups */
6218 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
6219 ret
= btrfs_next_leaf(fs_info
->chunk_root
, path
);
6221 btrfs_free_path(path
);
6229 leaf
= path
->nodes
[0];
6230 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
6231 if (key
.type
!= BTRFS_CHUNK_ITEM_KEY
) {
6236 chunk
= btrfs_item_ptr(leaf
, path
->slots
[0],
6237 struct btrfs_chunk
);
6238 btrfs_add_block_group(fs_info
, 0,
6239 btrfs_chunk_type(leaf
, chunk
),
6240 key
.objectid
, key
.offset
,
6241 btrfs_chunk_length(leaf
, chunk
));
6242 set_extent_dirty(&fs_info
->free_space_cache
, key
.offset
,
6243 key
.offset
+ btrfs_chunk_length(leaf
, chunk
),
6249 cache
= btrfs_lookup_first_block_group(fs_info
, start
);
6253 start
= cache
->key
.objectid
+ cache
->key
.offset
;
6256 btrfs_free_path(path
);
6260 static int reset_balance(struct btrfs_trans_handle
*trans
,
6261 struct btrfs_fs_info
*fs_info
)
6263 struct btrfs_root
*root
= fs_info
->tree_root
;
6264 struct btrfs_path
*path
;
6265 struct extent_buffer
*leaf
;
6266 struct btrfs_key key
;
6267 int del_slot
, del_nr
= 0;
6271 path
= btrfs_alloc_path();
6275 key
.objectid
= BTRFS_BALANCE_OBJECTID
;
6276 key
.type
= BTRFS_BALANCE_ITEM_KEY
;
6279 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
6284 goto reinit_data_reloc
;
6289 ret
= btrfs_del_item(trans
, root
, path
);
6292 btrfs_release_path(path
);
6294 key
.objectid
= BTRFS_TREE_RELOC_OBJECTID
;
6295 key
.type
= BTRFS_ROOT_ITEM_KEY
;
6298 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
6302 if (path
->slots
[0] >= btrfs_header_nritems(path
->nodes
[0])) {
6307 ret
= btrfs_del_items(trans
, root
, path
,
6314 btrfs_release_path(path
);
6317 ret
= btrfs_search_slot(trans
, root
, &key
, path
,
6324 leaf
= path
->nodes
[0];
6325 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
6326 if (key
.objectid
> BTRFS_TREE_RELOC_OBJECTID
)
6328 if (key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
6333 del_slot
= path
->slots
[0];
6342 ret
= btrfs_del_items(trans
, root
, path
, del_slot
, del_nr
);
6346 btrfs_release_path(path
);
6349 key
.objectid
= BTRFS_DATA_RELOC_TREE_OBJECTID
;
6350 key
.type
= BTRFS_ROOT_ITEM_KEY
;
6351 key
.offset
= (u64
)-1;
6352 root
= btrfs_read_fs_root(fs_info
, &key
);
6354 fprintf(stderr
, "Error reading data reloc tree\n");
6355 return PTR_ERR(root
);
6357 root
->track_dirty
= 1;
6358 if (root
->last_trans
!= trans
->transid
) {
6359 root
->last_trans
= trans
->transid
;
6360 root
->commit_root
= root
->node
;
6361 extent_buffer_get(root
->node
);
6363 ret
= btrfs_fsck_reinit_root(trans
, root
, 0);
6366 ret
= btrfs_make_root_dir(trans
, root
, BTRFS_FIRST_FREE_OBJECTID
);
6368 btrfs_free_path(path
);
6372 static int reinit_extent_tree(struct btrfs_trans_handle
*trans
,
6373 struct btrfs_fs_info
*fs_info
)
6379 * The only reason we don't do this is because right now we're just
6380 * walking the trees we find and pinning down their bytes, we don't look
6381 * at any of the leaves. In order to do mixed groups we'd have to check
6382 * the leaves of any fs roots and pin down the bytes for any file
6383 * extents we find. Not hard but why do it if we don't have to?
6385 if (btrfs_fs_incompat(fs_info
, BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS
)) {
6386 fprintf(stderr
, "We don't support re-initing the extent tree "
6387 "for mixed block groups yet, please notify a btrfs "
6388 "developer you want to do this so they can add this "
6389 "functionality.\n");
6394 * first we need to walk all of the trees except the extent tree and pin
6395 * down the bytes that are in use so we don't overwrite any existing
6398 ret
= pin_metadata_blocks(fs_info
);
6400 fprintf(stderr
, "error pinning down used bytes\n");
6405 * Need to drop all the block groups since we're going to recreate all
6408 btrfs_free_block_groups(fs_info
);
6409 ret
= reset_block_groups(fs_info
);
6411 fprintf(stderr
, "error resetting the block groups\n");
6415 /* Ok we can allocate now, reinit the extent root */
6416 ret
= btrfs_fsck_reinit_root(trans
, fs_info
->extent_root
, 0);
6418 fprintf(stderr
, "extent root initialization failed\n");
6420 * When the transaction code is updated we should end the
6421 * transaction, but for now progs only knows about commit so
6422 * just return an error.
6428 * Now we have all the in-memory block groups setup so we can make
6429 * allocations properly, and the metadata we care about is safe since we
6430 * pinned all of it above.
6433 struct btrfs_block_group_cache
*cache
;
6435 cache
= btrfs_lookup_first_block_group(fs_info
, start
);
6438 start
= cache
->key
.objectid
+ cache
->key
.offset
;
6439 ret
= btrfs_insert_item(trans
, fs_info
->extent_root
,
6440 &cache
->key
, &cache
->item
,
6441 sizeof(cache
->item
));
6443 fprintf(stderr
, "Error adding block group\n");
6446 btrfs_extent_post_op(trans
, fs_info
->extent_root
);
6449 ret
= reset_balance(trans
, fs_info
);
6451 fprintf(stderr
, "error reseting the pending balance\n");
6456 static int recow_extent_buffer(struct btrfs_root
*root
, struct extent_buffer
*eb
)
6458 struct btrfs_path
*path
;
6459 struct btrfs_trans_handle
*trans
;
6460 struct btrfs_key key
;
6463 printf("Recowing metadata block %llu\n", eb
->start
);
6464 key
.objectid
= btrfs_header_owner(eb
);
6465 key
.type
= BTRFS_ROOT_ITEM_KEY
;
6466 key
.offset
= (u64
)-1;
6468 root
= btrfs_read_fs_root(root
->fs_info
, &key
);
6470 fprintf(stderr
, "Couldn't find owner root %llu\n",
6472 return PTR_ERR(root
);
6475 path
= btrfs_alloc_path();
6479 trans
= btrfs_start_transaction(root
, 1);
6480 if (IS_ERR(trans
)) {
6481 btrfs_free_path(path
);
6482 return PTR_ERR(trans
);
6485 path
->lowest_level
= btrfs_header_level(eb
);
6486 if (path
->lowest_level
)
6487 btrfs_node_key_to_cpu(eb
, &key
, 0);
6489 btrfs_item_key_to_cpu(eb
, &key
, 0);
6491 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
6492 btrfs_commit_transaction(trans
, root
);
6493 btrfs_free_path(path
);
6497 static int delete_bad_item(struct btrfs_root
*root
, struct bad_item
*bad
)
6499 struct btrfs_path
*path
;
6500 struct btrfs_trans_handle
*trans
;
6501 struct btrfs_key key
;
6504 printf("Deleting bad item [%llu,%u,%llu]\n", bad
->key
.objectid
,
6505 bad
->key
.type
, bad
->key
.offset
);
6506 key
.objectid
= bad
->root_id
;
6507 key
.type
= BTRFS_ROOT_ITEM_KEY
;
6508 key
.offset
= (u64
)-1;
6510 root
= btrfs_read_fs_root(root
->fs_info
, &key
);
6512 fprintf(stderr
, "Couldn't find owner root %llu\n",
6514 return PTR_ERR(root
);
6517 path
= btrfs_alloc_path();
6521 trans
= btrfs_start_transaction(root
, 1);
6522 if (IS_ERR(trans
)) {
6523 btrfs_free_path(path
);
6524 return PTR_ERR(trans
);
6527 ret
= btrfs_search_slot(trans
, root
, &bad
->key
, path
, -1, 1);
6533 ret
= btrfs_del_item(trans
, root
, path
);
6535 btrfs_commit_transaction(trans
, root
);
6536 btrfs_free_path(path
);
6540 static struct option long_options
[] = {
6541 { "super", 1, NULL
, 's' },
6542 { "repair", 0, NULL
, 0 },
6543 { "init-csum-tree", 0, NULL
, 0 },
6544 { "init-extent-tree", 0, NULL
, 0 },
6545 { "check-data-csum", 0, NULL
, 0 },
6546 { "backup", 0, NULL
, 0 },
6547 { "qgroup-report", 0, NULL
, 'Q' },
6551 const char * const cmd_check_usage
[] = {
6552 "btrfs check [options] <device>",
6553 "Check an unmounted btrfs filesystem.",
6555 "-s|--super <superblock> use this superblock copy",
6556 "-b|--backup use the backup root copy",
6557 "--repair try to repair the filesystem",
6558 "--init-csum-tree create a new CRC tree",
6559 "--init-extent-tree create a new extent tree",
6560 "--check-data-csum verify checkums of data blocks",
6561 "--qgroup-report print a report on qgroup consistency",
6565 int cmd_check(int argc
, char **argv
)
6567 struct cache_tree root_cache
;
6568 struct btrfs_root
*root
;
6569 struct btrfs_fs_info
*info
;
6571 char uuidbuf
[BTRFS_UUID_UNPARSED_SIZE
];
6574 int option_index
= 0;
6575 int init_csum_tree
= 0;
6576 int qgroup_report
= 0;
6577 enum btrfs_open_ctree_flags ctree_flags
=
6578 OPEN_CTREE_PARTIAL
| OPEN_CTREE_EXCLUSIVE
;
6582 c
= getopt_long(argc
, argv
, "as:b", long_options
,
6587 case 'a': /* ignored */ break;
6589 ctree_flags
|= OPEN_CTREE_BACKUP_ROOT
;
6592 num
= arg_strtou64(optarg
);
6593 if (num
>= BTRFS_SUPER_MIRROR_MAX
) {
6595 "ERROR: super mirror should be less than: %d\n",
6596 BTRFS_SUPER_MIRROR_MAX
);
6599 bytenr
= btrfs_sb_offset(((int)num
));
6600 printf("using SB copy %llu, bytenr %llu\n", num
,
6601 (unsigned long long)bytenr
);
6608 usage(cmd_check_usage
);
6610 if (option_index
== 1) {
6611 printf("enabling repair mode\n");
6613 ctree_flags
|= OPEN_CTREE_WRITES
;
6614 } else if (option_index
== 2) {
6615 printf("Creating a new CRC tree\n");
6618 ctree_flags
|= OPEN_CTREE_WRITES
;
6619 } else if (option_index
== 3) {
6620 init_extent_tree
= 1;
6621 ctree_flags
|= (OPEN_CTREE_WRITES
|
6622 OPEN_CTREE_NO_BLOCK_GROUPS
);
6624 } else if (option_index
== 4) {
6625 check_data_csum
= 1;
6628 argc
= argc
- optind
;
6631 usage(cmd_check_usage
);
6634 cache_tree_init(&root_cache
);
6636 if((ret
= check_mounted(argv
[optind
])) < 0) {
6637 fprintf(stderr
, "Could not check mount status: %s\n", strerror(-ret
));
6640 fprintf(stderr
, "%s is currently mounted. Aborting.\n", argv
[optind
]);
6645 info
= open_ctree_fs_info(argv
[optind
], bytenr
, 0, ctree_flags
);
6647 fprintf(stderr
, "Couldn't open file system\n");
6652 root
= info
->fs_root
;
6653 uuid_unparse(info
->super_copy
->fsid
, uuidbuf
);
6654 if (qgroup_report
) {
6655 printf("Print quota groups for %s\nUUID: %s\n", argv
[optind
],
6657 ret
= qgroup_verify_all(info
);
6659 print_qgroup_report(1);
6662 printf("Checking filesystem on %s\nUUID: %s\n", argv
[optind
], uuidbuf
);
6664 if (!extent_buffer_uptodate(info
->tree_root
->node
) ||
6665 !extent_buffer_uptodate(info
->dev_root
->node
) ||
6666 !extent_buffer_uptodate(info
->chunk_root
->node
)) {
6667 fprintf(stderr
, "Critical roots corrupted, unable to fsck the FS\n");
6672 if (init_extent_tree
|| init_csum_tree
) {
6673 struct btrfs_trans_handle
*trans
;
6675 trans
= btrfs_start_transaction(info
->extent_root
, 0);
6676 if (IS_ERR(trans
)) {
6677 fprintf(stderr
, "Error starting transaction\n");
6678 ret
= PTR_ERR(trans
);
6682 if (init_extent_tree
) {
6683 printf("Creating a new extent tree\n");
6684 ret
= reinit_extent_tree(trans
, info
);
6689 if (init_csum_tree
) {
6690 fprintf(stderr
, "Reinit crc root\n");
6691 ret
= btrfs_fsck_reinit_root(trans
, info
->csum_root
, 0);
6693 fprintf(stderr
, "crc root initialization failed\n");
6699 * Ok now we commit and run the normal fsck, which will add
6700 * extent entries for all of the items it finds.
6702 ret
= btrfs_commit_transaction(trans
, info
->extent_root
);
6706 if (!extent_buffer_uptodate(info
->extent_root
->node
)) {
6707 fprintf(stderr
, "Critical roots corrupted, unable to fsck the FS\n");
6712 fprintf(stderr
, "checking extents\n");
6713 ret
= check_chunks_and_extents(root
);
6715 fprintf(stderr
, "Errors found in extent allocation tree or chunk allocation\n");
6717 fprintf(stderr
, "checking free space cache\n");
6718 ret
= check_space_cache(root
);
6723 * We used to have to have these hole extents in between our real
6724 * extents so if we don't have this flag set we need to make sure there
6725 * are no gaps in the file extents for inodes, otherwise we can just
6726 * ignore it when this happens.
6728 no_holes
= btrfs_fs_incompat(root
->fs_info
,
6729 BTRFS_FEATURE_INCOMPAT_NO_HOLES
);
6730 fprintf(stderr
, "checking fs roots\n");
6731 ret
= check_fs_roots(root
, &root_cache
);
6735 fprintf(stderr
, "checking csums\n");
6736 ret
= check_csums(root
);
6740 fprintf(stderr
, "checking root refs\n");
6741 ret
= check_root_refs(root
, &root_cache
);
6745 while (repair
&& !list_empty(&root
->fs_info
->recow_ebs
)) {
6746 struct extent_buffer
*eb
;
6748 eb
= list_first_entry(&root
->fs_info
->recow_ebs
,
6749 struct extent_buffer
, recow
);
6750 ret
= recow_extent_buffer(root
, eb
);
6755 while (!list_empty(&delete_items
)) {
6756 struct bad_item
*bad
;
6758 bad
= list_first_entry(&delete_items
, struct bad_item
, list
);
6759 list_del_init(&bad
->list
);
6761 ret
= delete_bad_item(root
, bad
);
6765 if (info
->quota_enabled
) {
6767 fprintf(stderr
, "checking quota groups\n");
6768 err
= qgroup_verify_all(info
);
6773 if (!list_empty(&root
->fs_info
->recow_ebs
)) {
6774 fprintf(stderr
, "Transid errors in file system\n");
6778 print_qgroup_report(0);
6779 if (found_old_backref
) { /*
6780 * there was a disk format change when mixed
6781 * backref was in testing tree. The old format
6782 * existed about one week.
6784 printf("\n * Found old mixed backref format. "
6785 "The old format is not supported! *"
6786 "\n * Please mount the FS in readonly mode, "
6787 "backup data and re-format the FS. *\n\n");
6790 printf("found %llu bytes used err is %d\n",
6791 (unsigned long long)bytes_used
, ret
);
6792 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes
);
6793 printf("total tree bytes: %llu\n",
6794 (unsigned long long)total_btree_bytes
);
6795 printf("total fs tree bytes: %llu\n",
6796 (unsigned long long)total_fs_tree_bytes
);
6797 printf("total extent tree bytes: %llu\n",
6798 (unsigned long long)total_extent_tree_bytes
);
6799 printf("btree space waste bytes: %llu\n",
6800 (unsigned long long)btree_space_waste
);
6801 printf("file data blocks allocated: %llu\n referenced %llu\n",
6802 (unsigned long long)data_bytes_allocated
,
6803 (unsigned long long)data_bytes_referenced
);
6804 printf("%s\n", BTRFS_BUILD_VERSION
);
6806 free_root_recs_tree(&root_cache
);