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
26 #include "kerncompat.h"
29 #include "print-tree.h"
30 #include "transaction.h"
35 static u64 bytes_used = 0;
36 static u64 total_csum_bytes = 0;
37 static u64 total_btree_bytes = 0;
38 static u64 total_fs_tree_bytes = 0;
39 static u64 btree_space_waste = 0;
40 static u64 data_bytes_allocated = 0;
41 static u64 data_bytes_referenced = 0;
42 static int found_old_backref = 0;
44 struct extent_backref {
45 struct list_head list;
46 unsigned int is_data:1;
47 unsigned int found_extent_tree:1;
48 unsigned int full_backref:1;
49 unsigned int found_ref:1;
53 struct extent_backref node;
65 struct extent_backref node;
72 struct extent_record {
73 struct list_head backrefs;
74 struct cache_extent cache;
75 struct btrfs_disk_key parent_key;
80 unsigned int content_checked:1;
81 unsigned int owner_ref_checked:1;
82 unsigned int is_root:1;
85 struct inode_backref {
86 struct list_head list;
87 unsigned int found_dir_item:1;
88 unsigned int found_dir_index:1;
89 unsigned int found_inode_ref:1;
90 unsigned int filetype:8;
98 #define REF_ERR_NO_DIR_ITEM (1 << 0)
99 #define REF_ERR_NO_DIR_INDEX (1 << 1)
100 #define REF_ERR_NO_INODE_REF (1 << 2)
101 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
102 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
103 #define REF_ERR_DUP_INODE_REF (1 << 5)
104 #define REF_ERR_INDEX_UNMATCH (1 << 6)
105 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
106 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
107 #define REF_ERR_NO_ROOT_REF (1 << 9)
108 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
109 #define REF_ERR_DUP_ROOT_REF (1 << 11)
110 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
112 struct inode_record {
113 struct list_head backrefs;
114 unsigned int checked:1;
115 unsigned int merging:1;
116 unsigned int found_inode_item:1;
117 unsigned int found_dir_item:1;
118 unsigned int found_file_extent:1;
119 unsigned int found_csum_item:1;
120 unsigned int some_csum_missing:1;
121 unsigned int nodatasum:1;
134 u64 first_extent_gap;
139 #define I_ERR_NO_INODE_ITEM (1 << 0)
140 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
141 #define I_ERR_DUP_INODE_ITEM (1 << 2)
142 #define I_ERR_DUP_DIR_INDEX (1 << 3)
143 #define I_ERR_ODD_DIR_ITEM (1 << 4)
144 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
145 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
146 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
147 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
148 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
149 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
150 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
151 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
152 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
154 struct root_backref {
155 struct list_head list;
156 unsigned int found_dir_item:1;
157 unsigned int found_dir_index:1;
158 unsigned int found_back_ref:1;
159 unsigned int found_forward_ref:1;
160 unsigned int reachable:1;
170 struct list_head backrefs;
171 struct cache_extent cache;
172 unsigned int found_root_item:1;
178 struct cache_extent cache;
183 struct cache_extent cache;
184 struct cache_tree root_cache;
185 struct cache_tree inode_cache;
186 struct inode_record *current;
195 struct walk_control {
196 struct cache_tree shared;
197 struct shared_node *nodes[BTRFS_MAX_LEVEL];
202 static u8 imode_to_type(u32 imode)
205 static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
206 [S_IFREG >> S_SHIFT] = BTRFS_FT_REG_FILE,
207 [S_IFDIR >> S_SHIFT] = BTRFS_FT_DIR,
208 [S_IFCHR >> S_SHIFT] = BTRFS_FT_CHRDEV,
209 [S_IFBLK >> S_SHIFT] = BTRFS_FT_BLKDEV,
210 [S_IFIFO >> S_SHIFT] = BTRFS_FT_FIFO,
211 [S_IFSOCK >> S_SHIFT] = BTRFS_FT_SOCK,
212 [S_IFLNK >> S_SHIFT] = BTRFS_FT_SYMLINK,
215 return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
219 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
221 struct inode_record *rec;
222 struct inode_backref *backref;
223 struct inode_backref *orig;
226 rec = malloc(sizeof(*rec));
227 memcpy(rec, orig_rec, sizeof(*rec));
229 INIT_LIST_HEAD(&rec->backrefs);
231 list_for_each_entry(orig, &orig_rec->backrefs, list) {
232 size = sizeof(*orig) + orig->namelen + 1;
233 backref = malloc(size);
234 memcpy(backref, orig, size);
235 list_add_tail(&backref->list, &rec->backrefs);
240 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
243 struct ptr_node *node;
244 struct cache_extent *cache;
245 struct inode_record *rec = NULL;
248 cache = find_cache_extent(inode_cache, ino, 1);
250 node = container_of(cache, struct ptr_node, cache);
252 if (mod && rec->refs > 1) {
253 node->data = clone_inode_rec(rec);
258 rec = calloc(1, sizeof(*rec));
260 rec->extent_start = (u64)-1;
261 rec->first_extent_gap = (u64)-1;
263 INIT_LIST_HEAD(&rec->backrefs);
265 node = malloc(sizeof(*node));
266 node->cache.start = ino;
267 node->cache.size = 1;
270 ret = insert_existing_cache_extent(inode_cache, &node->cache);
276 static void free_inode_rec(struct inode_record *rec)
278 struct inode_backref *backref;
283 while (!list_empty(&rec->backrefs)) {
284 backref = list_entry(rec->backrefs.next,
285 struct inode_backref, list);
286 list_del(&backref->list);
292 static int can_free_inode_rec(struct inode_record *rec)
294 if (!rec->errors && rec->checked && rec->found_inode_item &&
295 rec->nlink == rec->found_link && list_empty(&rec->backrefs))
300 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
301 struct inode_record *rec)
303 struct cache_extent *cache;
304 struct inode_backref *tmp, *backref;
305 struct ptr_node *node;
306 unsigned char filetype;
308 if (!rec->found_inode_item)
311 filetype = imode_to_type(rec->imode);
312 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
313 if (backref->found_dir_item && backref->found_dir_index) {
314 if (backref->filetype != filetype)
315 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
316 if (!backref->errors && backref->found_inode_ref) {
317 list_del(&backref->list);
323 if (!rec->checked || rec->merging)
326 if (S_ISDIR(rec->imode)) {
327 if (rec->found_size != rec->isize)
328 rec->errors |= I_ERR_DIR_ISIZE_WRONG;
329 if (rec->found_file_extent)
330 rec->errors |= I_ERR_ODD_FILE_EXTENT;
331 } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
332 if (rec->found_dir_item)
333 rec->errors |= I_ERR_ODD_DIR_ITEM;
334 if (rec->found_size != rec->nbytes)
335 rec->errors |= I_ERR_FILE_NBYTES_WRONG;
336 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
337 rec->first_extent_gap = 0;
338 if (rec->nlink > 0 && (rec->extent_end < rec->isize ||
339 rec->first_extent_gap < rec->isize))
340 rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
343 if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
344 if (rec->found_csum_item && rec->nodatasum)
345 rec->errors |= I_ERR_ODD_CSUM_ITEM;
346 if (rec->some_csum_missing && !rec->nodatasum)
347 rec->errors |= I_ERR_SOME_CSUM_MISSING;
350 BUG_ON(rec->refs != 1);
351 if (can_free_inode_rec(rec)) {
352 cache = find_cache_extent(inode_cache, rec->ino, 1);
353 node = container_of(cache, struct ptr_node, cache);
354 BUG_ON(node->data != rec);
355 remove_cache_extent(inode_cache, &node->cache);
361 static int check_orphan_item(struct btrfs_root *root, u64 ino)
363 struct btrfs_path path;
364 struct btrfs_key key;
367 key.objectid = BTRFS_ORPHAN_OBJECTID;
368 key.type = BTRFS_ORPHAN_ITEM_KEY;
371 btrfs_init_path(&path);
372 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
373 btrfs_release_path(root, &path);
379 static int process_inode_item(struct extent_buffer *eb,
380 int slot, struct btrfs_key *key,
381 struct shared_node *active_node)
383 struct inode_record *rec;
384 struct btrfs_inode_item *item;
386 rec = active_node->current;
387 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
388 if (rec->found_inode_item) {
389 rec->errors |= I_ERR_DUP_INODE_ITEM;
392 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
393 rec->nlink = btrfs_inode_nlink(eb, item);
394 rec->isize = btrfs_inode_size(eb, item);
395 rec->nbytes = btrfs_inode_nbytes(eb, item);
396 rec->imode = btrfs_inode_mode(eb, item);
397 if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
399 rec->found_inode_item = 1;
401 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
402 maybe_free_inode_rec(&active_node->inode_cache, rec);
406 static struct inode_backref *get_inode_backref(struct inode_record *rec,
408 int namelen, u64 dir)
410 struct inode_backref *backref;
412 list_for_each_entry(backref, &rec->backrefs, list) {
413 if (backref->dir != dir || backref->namelen != namelen)
415 if (memcmp(name, backref->name, namelen))
420 backref = malloc(sizeof(*backref) + namelen + 1);
421 memset(backref, 0, sizeof(*backref));
423 backref->namelen = namelen;
424 memcpy(backref->name, name, namelen);
425 backref->name[namelen] = '\0';
426 list_add_tail(&backref->list, &rec->backrefs);
430 static int add_inode_backref(struct cache_tree *inode_cache,
431 u64 ino, u64 dir, u64 index,
432 const char *name, int namelen,
433 int filetype, int itemtype, int errors)
435 struct inode_record *rec;
436 struct inode_backref *backref;
438 rec = get_inode_rec(inode_cache, ino, 1);
439 backref = get_inode_backref(rec, name, namelen, dir);
441 backref->errors |= errors;
442 if (itemtype == BTRFS_DIR_INDEX_KEY) {
443 if (backref->found_dir_index)
444 backref->errors |= REF_ERR_DUP_DIR_INDEX;
445 if (backref->found_inode_ref && backref->index != index)
446 backref->errors |= REF_ERR_INDEX_UNMATCH;
447 if (backref->found_dir_item && backref->filetype != filetype)
448 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
450 backref->index = index;
451 backref->filetype = filetype;
452 backref->found_dir_index = 1;
453 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
455 if (backref->found_dir_item)
456 backref->errors |= REF_ERR_DUP_DIR_ITEM;
457 if (backref->found_dir_index && backref->filetype != filetype)
458 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
460 backref->filetype = filetype;
461 backref->found_dir_item = 1;
462 } else if (itemtype == BTRFS_INODE_REF_KEY) {
463 if (backref->found_inode_ref)
464 backref->errors |= REF_ERR_DUP_INODE_REF;
465 if (backref->found_dir_index && backref->index != index)
466 backref->errors |= REF_ERR_INDEX_UNMATCH;
468 backref->index = index;
469 backref->found_inode_ref = 1;
474 maybe_free_inode_rec(inode_cache, rec);
478 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
479 struct cache_tree *dst_cache)
481 struct inode_backref *backref;
485 list_for_each_entry(backref, &src->backrefs, list) {
486 if (backref->found_dir_index) {
487 add_inode_backref(dst_cache, dst->ino, backref->dir,
488 backref->index, backref->name,
489 backref->namelen, backref->filetype,
490 BTRFS_DIR_INDEX_KEY, backref->errors);
492 if (backref->found_dir_item) {
494 add_inode_backref(dst_cache, dst->ino,
495 backref->dir, 0, backref->name,
496 backref->namelen, backref->filetype,
497 BTRFS_DIR_ITEM_KEY, backref->errors);
499 if (backref->found_inode_ref) {
500 add_inode_backref(dst_cache, dst->ino,
501 backref->dir, backref->index,
502 backref->name, backref->namelen, 0,
503 BTRFS_INODE_REF_KEY, backref->errors);
507 if (src->found_dir_item)
508 dst->found_dir_item = 1;
509 if (src->found_file_extent)
510 dst->found_file_extent = 1;
511 if (src->found_csum_item)
512 dst->found_csum_item = 1;
513 if (src->some_csum_missing)
514 dst->some_csum_missing = 1;
515 if (dst->first_extent_gap > src->first_extent_gap)
516 dst->first_extent_gap = src->first_extent_gap;
518 BUG_ON(src->found_link < dir_count);
519 dst->found_link += src->found_link - dir_count;
520 dst->found_size += src->found_size;
521 if (src->extent_start != (u64)-1) {
522 if (dst->extent_start == (u64)-1) {
523 dst->extent_start = src->extent_start;
524 dst->extent_end = src->extent_end;
526 if (dst->extent_end > src->extent_start)
527 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
528 else if (dst->extent_end < src->extent_start &&
529 dst->extent_end < dst->first_extent_gap)
530 dst->first_extent_gap = dst->extent_end;
531 if (dst->extent_end < src->extent_end)
532 dst->extent_end = src->extent_end;
536 dst->errors |= src->errors;
537 if (src->found_inode_item) {
538 if (!dst->found_inode_item) {
539 dst->nlink = src->nlink;
540 dst->isize = src->isize;
541 dst->nbytes = src->nbytes;
542 dst->imode = src->imode;
543 dst->nodatasum = src->nodatasum;
544 dst->found_inode_item = 1;
546 dst->errors |= I_ERR_DUP_INODE_ITEM;
554 static int splice_shared_node(struct shared_node *src_node,
555 struct shared_node *dst_node)
557 struct cache_extent *cache;
558 struct ptr_node *node, *ins;
559 struct cache_tree *src, *dst;
560 struct inode_record *rec, *conflict;
565 if (--src_node->refs == 0)
567 if (src_node->current)
568 current_ino = src_node->current->ino;
570 src = &src_node->root_cache;
571 dst = &dst_node->root_cache;
573 cache = find_first_cache_extent(src, 0);
575 node = container_of(cache, struct ptr_node, cache);
577 cache = next_cache_extent(cache);
580 remove_cache_extent(src, &node->cache);
583 ins = malloc(sizeof(*ins));
584 ins->cache.start = node->cache.start;
585 ins->cache.size = node->cache.size;
589 ret = insert_existing_cache_extent(dst, &ins->cache);
590 if (ret == -EEXIST) {
591 conflict = get_inode_rec(dst, rec->ino, 1);
592 merge_inode_recs(rec, conflict, dst);
594 conflict->checked = 1;
595 if (dst_node->current == conflict)
596 dst_node->current = NULL;
598 maybe_free_inode_rec(dst, conflict);
606 if (src == &src_node->root_cache) {
607 src = &src_node->inode_cache;
608 dst = &dst_node->inode_cache;
612 if (current_ino > 0 && (!dst_node->current ||
613 current_ino > dst_node->current->ino)) {
614 if (dst_node->current) {
615 dst_node->current->checked = 1;
616 maybe_free_inode_rec(dst, dst_node->current);
618 dst_node->current = get_inode_rec(dst, current_ino, 1);
623 static void free_inode_recs(struct cache_tree *inode_cache)
625 struct cache_extent *cache;
626 struct ptr_node *node;
627 struct inode_record *rec;
630 cache = find_first_cache_extent(inode_cache, 0);
633 node = container_of(cache, struct ptr_node, cache);
635 remove_cache_extent(inode_cache, &node->cache);
641 static struct shared_node *find_shared_node(struct cache_tree *shared,
644 struct cache_extent *cache;
645 struct shared_node *node;
647 cache = find_cache_extent(shared, bytenr, 1);
649 node = container_of(cache, struct shared_node, cache);
655 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
658 struct shared_node *node;
660 node = calloc(1, sizeof(*node));
661 node->cache.start = bytenr;
662 node->cache.size = 1;
663 cache_tree_init(&node->root_cache);
664 cache_tree_init(&node->inode_cache);
667 ret = insert_existing_cache_extent(shared, &node->cache);
672 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
673 struct walk_control *wc, int level)
675 struct shared_node *node;
676 struct shared_node *dest;
678 if (level == wc->active_node)
681 BUG_ON(wc->active_node <= level);
682 node = find_shared_node(&wc->shared, bytenr);
684 add_shared_node(&wc->shared, bytenr, refs);
685 node = find_shared_node(&wc->shared, bytenr);
686 wc->nodes[level] = node;
687 wc->active_node = level;
691 if (wc->root_level == wc->active_node &&
692 btrfs_root_refs(&root->root_item) == 0) {
693 if (--node->refs == 0) {
694 free_inode_recs(&node->root_cache);
695 free_inode_recs(&node->inode_cache);
696 remove_cache_extent(&wc->shared, &node->cache);
702 dest = wc->nodes[wc->active_node];
703 splice_shared_node(node, dest);
704 if (node->refs == 0) {
705 remove_cache_extent(&wc->shared, &node->cache);
711 static int leave_shared_node(struct btrfs_root *root,
712 struct walk_control *wc, int level)
714 struct shared_node *node;
715 struct shared_node *dest;
718 if (level == wc->root_level)
721 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
725 BUG_ON(i >= BTRFS_MAX_LEVEL);
727 node = wc->nodes[wc->active_node];
728 wc->nodes[wc->active_node] = NULL;
731 dest = wc->nodes[wc->active_node];
732 if (wc->active_node < wc->root_level ||
733 btrfs_root_refs(&root->root_item) > 0) {
734 BUG_ON(node->refs <= 1);
735 splice_shared_node(node, dest);
737 BUG_ON(node->refs < 2);
743 static int process_dir_item(struct extent_buffer *eb,
744 int slot, struct btrfs_key *key,
745 struct shared_node *active_node)
755 struct btrfs_dir_item *di;
756 struct inode_record *rec;
757 struct cache_tree *root_cache;
758 struct cache_tree *inode_cache;
759 struct btrfs_key location;
760 char namebuf[BTRFS_NAME_LEN];
762 root_cache = &active_node->root_cache;
763 inode_cache = &active_node->inode_cache;
764 rec = active_node->current;
765 rec->found_dir_item = 1;
767 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
768 total = btrfs_item_size_nr(eb, slot);
769 while (cur < total) {
771 btrfs_dir_item_key_to_cpu(eb, di, &location);
772 name_len = btrfs_dir_name_len(eb, di);
773 data_len = btrfs_dir_data_len(eb, di);
774 filetype = btrfs_dir_type(eb, di);
776 rec->found_size += name_len;
777 if (name_len <= BTRFS_NAME_LEN) {
781 len = BTRFS_NAME_LEN;
782 error = REF_ERR_NAME_TOO_LONG;
784 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
786 if (location.type == BTRFS_INODE_ITEM_KEY) {
787 add_inode_backref(inode_cache, location.objectid,
788 key->objectid, key->offset, namebuf,
789 len, filetype, key->type, error);
790 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
791 add_inode_backref(root_cache, location.objectid,
792 key->objectid, key->offset, namebuf,
793 len, filetype, key->type, error);
795 fprintf(stderr, "warning line %d\n", __LINE__);
798 len = sizeof(*di) + name_len + data_len;
799 di = (struct btrfs_dir_item *)((char *)di + len);
802 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
803 rec->errors |= I_ERR_DUP_DIR_INDEX;
808 static int process_inode_ref(struct extent_buffer *eb,
809 int slot, struct btrfs_key *key,
810 struct shared_node *active_node)
818 struct cache_tree *inode_cache;
819 struct btrfs_inode_ref *ref;
820 char namebuf[BTRFS_NAME_LEN];
822 inode_cache = &active_node->inode_cache;
824 ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
825 total = btrfs_item_size_nr(eb, slot);
826 while (cur < total) {
827 name_len = btrfs_inode_ref_name_len(eb, ref);
828 index = btrfs_inode_ref_index(eb, ref);
829 if (name_len <= BTRFS_NAME_LEN) {
833 len = BTRFS_NAME_LEN;
834 error = REF_ERR_NAME_TOO_LONG;
836 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
837 add_inode_backref(inode_cache, key->objectid, key->offset,
838 index, namebuf, len, 0, key->type, error);
840 len = sizeof(*ref) + name_len;
841 ref = (struct btrfs_inode_ref *)((char *)ref + len);
847 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
849 struct btrfs_key key;
850 struct btrfs_path path;
851 struct extent_buffer *leaf;
856 u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
858 btrfs_init_path(&path);
860 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
862 key.type = BTRFS_EXTENT_CSUM_KEY;
864 ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
867 if (ret > 0 && path.slots[0] > 0) {
868 leaf = path.nodes[0];
869 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
870 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
871 key.type == BTRFS_EXTENT_CSUM_KEY)
876 leaf = path.nodes[0];
877 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
878 ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
882 leaf = path.nodes[0];
885 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
886 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
887 key.type != BTRFS_EXTENT_CSUM_KEY)
890 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
891 if (key.offset >= start + len)
894 if (key.offset > start)
897 size = btrfs_item_size_nr(leaf, path.slots[0]);
898 csum_end = key.offset + (size / csum_size) * root->sectorsize;
899 if (csum_end > start) {
900 size = min(csum_end - start, len);
908 btrfs_release_path(root->fs_info->csum_root, &path);
912 static int process_file_extent(struct btrfs_root *root,
913 struct extent_buffer *eb,
914 int slot, struct btrfs_key *key,
915 struct shared_node *active_node)
917 struct inode_record *rec;
918 struct btrfs_file_extent_item *fi;
921 u64 extent_offset = 0;
922 u64 mask = root->sectorsize - 1;
925 rec = active_node->current;
926 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
927 rec->found_file_extent = 1;
929 if (rec->extent_start == (u64)-1) {
930 rec->extent_start = key->offset;
931 rec->extent_end = key->offset;
934 if (rec->extent_end > key->offset)
935 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
936 else if (rec->extent_end < key->offset &&
937 rec->extent_end < rec->first_extent_gap)
938 rec->first_extent_gap = rec->extent_end;
940 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
941 extent_type = btrfs_file_extent_type(eb, fi);
943 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
944 num_bytes = btrfs_file_extent_inline_len(eb, fi);
946 rec->errors |= I_ERR_BAD_FILE_EXTENT;
947 rec->found_size += num_bytes;
948 num_bytes = (num_bytes + mask) & ~mask;
949 } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
950 extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
951 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
952 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
953 extent_offset = btrfs_file_extent_offset(eb, fi);
954 if (num_bytes == 0 || (num_bytes & mask))
955 rec->errors |= I_ERR_BAD_FILE_EXTENT;
956 if (num_bytes + extent_offset >
957 btrfs_file_extent_ram_bytes(eb, fi))
958 rec->errors |= I_ERR_BAD_FILE_EXTENT;
959 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
960 (btrfs_file_extent_compression(eb, fi) ||
961 btrfs_file_extent_encryption(eb, fi) ||
962 btrfs_file_extent_other_encoding(eb, fi)))
963 rec->errors |= I_ERR_BAD_FILE_EXTENT;
965 rec->found_size += num_bytes;
967 rec->errors |= I_ERR_BAD_FILE_EXTENT;
969 rec->extent_end = key->offset + num_bytes;
971 if (disk_bytenr > 0) {
973 if (btrfs_file_extent_compression(eb, fi))
974 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
976 disk_bytenr += extent_offset;
978 found = count_csum_range(root, disk_bytenr, num_bytes);
979 if (extent_type == BTRFS_FILE_EXTENT_REG) {
981 rec->found_csum_item = 1;
982 if (found < num_bytes)
983 rec->some_csum_missing = 1;
984 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
986 rec->errors |= I_ERR_ODD_CSUM_ITEM;
992 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
993 struct walk_control *wc)
995 struct btrfs_key key;
999 struct cache_tree *inode_cache;
1000 struct shared_node *active_node;
1002 if (wc->root_level == wc->active_node &&
1003 btrfs_root_refs(&root->root_item) == 0)
1006 active_node = wc->nodes[wc->active_node];
1007 inode_cache = &active_node->inode_cache;
1008 nritems = btrfs_header_nritems(eb);
1009 for (i = 0; i < nritems; i++) {
1010 btrfs_item_key_to_cpu(eb, &key, i);
1011 if (active_node->current == NULL ||
1012 active_node->current->ino < key.objectid) {
1013 if (active_node->current) {
1014 active_node->current->checked = 1;
1015 maybe_free_inode_rec(inode_cache,
1016 active_node->current);
1018 active_node->current = get_inode_rec(inode_cache,
1022 case BTRFS_DIR_ITEM_KEY:
1023 case BTRFS_DIR_INDEX_KEY:
1024 ret = process_dir_item(eb, i, &key, active_node);
1026 case BTRFS_INODE_REF_KEY:
1027 ret = process_inode_ref(eb, i, &key, active_node);
1029 case BTRFS_INODE_ITEM_KEY:
1030 ret = process_inode_item(eb, i, &key, active_node);
1032 case BTRFS_EXTENT_DATA_KEY:
1033 ret = process_file_extent(root, eb, i, &key,
1043 static void reada_walk_down(struct btrfs_root *root,
1044 struct extent_buffer *node, int slot)
1054 level = btrfs_header_level(node);
1058 nritems = btrfs_header_nritems(node);
1059 blocksize = btrfs_level_size(root, level - 1);
1060 for (i = slot; i < nritems; i++) {
1061 bytenr = btrfs_node_blockptr(node, i);
1062 ptr_gen = btrfs_node_ptr_generation(node, i);
1063 ret = readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1069 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1070 struct walk_control *wc, int *level)
1074 struct extent_buffer *next;
1075 struct extent_buffer *cur;
1080 WARN_ON(*level < 0);
1081 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1082 ret = btrfs_lookup_extent_info(NULL, root,
1083 path->nodes[*level]->start,
1084 path->nodes[*level]->len, &refs, NULL);
1087 ret = enter_shared_node(root, path->nodes[*level]->start,
1093 while (*level >= 0) {
1094 WARN_ON(*level < 0);
1095 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1096 cur = path->nodes[*level];
1098 if (btrfs_header_level(cur) != *level)
1101 if (path->slots[*level] >= btrfs_header_nritems(cur))
1104 ret = process_one_leaf(root, cur, wc);
1107 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1108 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1109 blocksize = btrfs_level_size(root, *level - 1);
1110 ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize,
1115 ret = enter_shared_node(root, bytenr, refs,
1118 path->slots[*level]++;
1123 next = btrfs_find_tree_block(root, bytenr, blocksize);
1124 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1125 free_extent_buffer(next);
1126 reada_walk_down(root, cur, path->slots[*level]);
1127 next = read_tree_block(root, bytenr, blocksize,
1131 *level = *level - 1;
1132 free_extent_buffer(path->nodes[*level]);
1133 path->nodes[*level] = next;
1134 path->slots[*level] = 0;
1137 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1141 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1142 struct walk_control *wc, int *level)
1145 struct extent_buffer *leaf;
1147 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1148 leaf = path->nodes[i];
1149 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1154 free_extent_buffer(path->nodes[*level]);
1155 path->nodes[*level] = NULL;
1156 BUG_ON(*level > wc->active_node);
1157 if (*level == wc->active_node)
1158 leave_shared_node(root, wc, *level);
1165 static int check_root_dir(struct inode_record *rec)
1167 struct inode_backref *backref;
1170 if (!rec->found_inode_item || rec->errors)
1172 if (rec->nlink != 1 || rec->found_link != 0)
1174 if (list_empty(&rec->backrefs))
1176 backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1177 if (!backref->found_inode_ref)
1179 if (backref->index != 0 || backref->namelen != 2 ||
1180 memcmp(backref->name, "..", 2))
1182 if (backref->found_dir_index || backref->found_dir_item)
1189 static int check_inode_recs(struct btrfs_root *root,
1190 struct cache_tree *inode_cache)
1192 struct cache_extent *cache;
1193 struct ptr_node *node;
1194 struct inode_record *rec;
1195 struct inode_backref *backref;
1198 u64 root_dirid = btrfs_root_dirid(&root->root_item);
1200 if (btrfs_root_refs(&root->root_item) == 0) {
1201 if (!cache_tree_empty(inode_cache))
1202 fprintf(stderr, "warning line %d\n", __LINE__);
1206 rec = get_inode_rec(inode_cache, root_dirid, 0);
1208 ret = check_root_dir(rec);
1210 fprintf(stderr, "root %llu root dir %llu error\n",
1211 (unsigned long long)root->root_key.objectid,
1212 (unsigned long long)root_dirid);
1216 fprintf(stderr, "root %llu root dir %llu not found\n",
1217 (unsigned long long)root->root_key.objectid,
1218 (unsigned long long)root_dirid);
1222 cache = find_first_cache_extent(inode_cache, 0);
1225 node = container_of(cache, struct ptr_node, cache);
1227 remove_cache_extent(inode_cache, &node->cache);
1229 if (rec->ino == root_dirid ||
1230 rec->ino == BTRFS_ORPHAN_OBJECTID) {
1231 free_inode_rec(rec);
1235 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1236 ret = check_orphan_item(root, rec->ino);
1238 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1239 if (can_free_inode_rec(rec)) {
1240 free_inode_rec(rec);
1246 if (!rec->found_inode_item)
1247 rec->errors |= I_ERR_NO_INODE_ITEM;
1248 if (rec->found_link != rec->nlink)
1249 rec->errors |= I_ERR_LINK_COUNT_WRONG;
1250 fprintf(stderr, "root %llu inode %llu errors %x\n",
1251 (unsigned long long) root->root_key.objectid,
1252 (unsigned long long) rec->ino, rec->errors);
1253 list_for_each_entry(backref, &rec->backrefs, list) {
1254 if (!backref->found_dir_item)
1255 backref->errors |= REF_ERR_NO_DIR_ITEM;
1256 if (!backref->found_dir_index)
1257 backref->errors |= REF_ERR_NO_DIR_INDEX;
1258 if (!backref->found_inode_ref)
1259 backref->errors |= REF_ERR_NO_INODE_REF;
1260 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1261 " namelen %u name %s filetype %d error %x\n",
1262 (unsigned long long)backref->dir,
1263 (unsigned long long)backref->index,
1264 backref->namelen, backref->name,
1265 backref->filetype, backref->errors);
1267 free_inode_rec(rec);
1269 return (error > 0) ? -1 : 0;
1272 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1275 struct cache_extent *cache;
1276 struct root_record *rec = NULL;
1279 cache = find_cache_extent(root_cache, objectid, 1);
1281 rec = container_of(cache, struct root_record, cache);
1283 rec = calloc(1, sizeof(*rec));
1284 rec->objectid = objectid;
1285 INIT_LIST_HEAD(&rec->backrefs);
1286 rec->cache.start = objectid;
1287 rec->cache.size = 1;
1289 ret = insert_existing_cache_extent(root_cache, &rec->cache);
1295 static struct root_backref *get_root_backref(struct root_record *rec,
1296 u64 ref_root, u64 dir, u64 index,
1297 const char *name, int namelen)
1299 struct root_backref *backref;
1301 list_for_each_entry(backref, &rec->backrefs, list) {
1302 if (backref->ref_root != ref_root || backref->dir != dir ||
1303 backref->namelen != namelen)
1305 if (memcmp(name, backref->name, namelen))
1310 backref = malloc(sizeof(*backref) + namelen + 1);
1311 memset(backref, 0, sizeof(*backref));
1312 backref->ref_root = ref_root;
1314 backref->index = index;
1315 backref->namelen = namelen;
1316 memcpy(backref->name, name, namelen);
1317 backref->name[namelen] = '\0';
1318 list_add_tail(&backref->list, &rec->backrefs);
1322 static void free_root_recs(struct cache_tree *root_cache)
1324 struct cache_extent *cache;
1325 struct root_record *rec;
1326 struct root_backref *backref;
1329 cache = find_first_cache_extent(root_cache, 0);
1332 rec = container_of(cache, struct root_record, cache);
1333 remove_cache_extent(root_cache, &rec->cache);
1335 while (!list_empty(&rec->backrefs)) {
1336 backref = list_entry(rec->backrefs.next,
1337 struct root_backref, list);
1338 list_del(&backref->list);
1345 static int add_root_backref(struct cache_tree *root_cache,
1346 u64 root_id, u64 ref_root, u64 dir, u64 index,
1347 const char *name, int namelen,
1348 int item_type, int errors)
1350 struct root_record *rec;
1351 struct root_backref *backref;
1353 rec = get_root_rec(root_cache, root_id);
1354 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
1356 backref->errors |= errors;
1358 if (item_type != BTRFS_DIR_ITEM_KEY) {
1359 if (backref->found_dir_index || backref->found_back_ref ||
1360 backref->found_forward_ref) {
1361 if (backref->index != index)
1362 backref->errors |= REF_ERR_INDEX_UNMATCH;
1364 backref->index = index;
1368 if (item_type == BTRFS_DIR_ITEM_KEY) {
1369 backref->found_dir_item = 1;
1370 backref->reachable = 1;
1372 } else if (item_type == BTRFS_DIR_INDEX_KEY) {
1373 backref->found_dir_index = 1;
1374 } else if (item_type == BTRFS_ROOT_REF_KEY) {
1375 if (backref->found_forward_ref)
1376 backref->errors |= REF_ERR_DUP_ROOT_REF;
1377 backref->found_forward_ref = 1;
1378 } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
1379 if (backref->found_back_ref)
1380 backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
1381 backref->found_back_ref = 1;
1389 static int merge_root_recs(struct btrfs_root *root,
1390 struct cache_tree *src_cache,
1391 struct cache_tree *dst_cache)
1393 struct cache_extent *cache;
1394 struct ptr_node *node;
1395 struct inode_record *rec;
1396 struct inode_backref *backref;
1398 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1399 free_inode_recs(src_cache);
1404 cache = find_first_cache_extent(src_cache, 0);
1407 node = container_of(cache, struct ptr_node, cache);
1409 remove_cache_extent(src_cache, &node->cache);
1412 list_for_each_entry(backref, &rec->backrefs, list) {
1413 BUG_ON(backref->found_inode_ref);
1414 if (backref->found_dir_item)
1415 add_root_backref(dst_cache, rec->ino,
1416 root->root_key.objectid, backref->dir,
1417 backref->index, backref->name,
1418 backref->namelen, BTRFS_DIR_ITEM_KEY,
1420 if (backref->found_dir_index)
1421 add_root_backref(dst_cache, rec->ino,
1422 root->root_key.objectid, backref->dir,
1423 backref->index, backref->name,
1424 backref->namelen, BTRFS_DIR_INDEX_KEY,
1427 free_inode_rec(rec);
1432 static int check_root_refs(struct btrfs_root *root,
1433 struct cache_tree *root_cache)
1435 struct root_record *rec;
1436 struct root_record *ref_root;
1437 struct root_backref *backref;
1438 struct cache_extent *cache;
1444 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
1447 /* fixme: this can not detect circular references */
1450 cache = find_first_cache_extent(root_cache, 0);
1454 rec = container_of(cache, struct root_record, cache);
1455 cache = next_cache_extent(cache);
1457 if (rec->found_ref == 0)
1460 list_for_each_entry(backref, &rec->backrefs, list) {
1461 if (!backref->reachable)
1464 ref_root = get_root_rec(root_cache,
1466 if (ref_root->found_ref > 0)
1469 backref->reachable = 0;
1471 if (rec->found_ref == 0)
1477 cache = find_first_cache_extent(root_cache, 0);
1481 rec = container_of(cache, struct root_record, cache);
1482 cache = next_cache_extent(cache);
1484 if (rec->found_ref == 0 &&
1485 rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1486 rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
1487 ret = check_orphan_item(root->fs_info->tree_root,
1492 fprintf(stderr, "fs tree %llu not referenced\n",
1493 (unsigned long long)rec->objectid);
1497 if (rec->found_ref > 0 && !rec->found_root_item)
1499 list_for_each_entry(backref, &rec->backrefs, list) {
1500 if (!backref->found_dir_item)
1501 backref->errors |= REF_ERR_NO_DIR_ITEM;
1502 if (!backref->found_dir_index)
1503 backref->errors |= REF_ERR_NO_DIR_INDEX;
1504 if (!backref->found_back_ref)
1505 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
1506 if (!backref->found_forward_ref)
1507 backref->errors |= REF_ERR_NO_ROOT_REF;
1508 if (backref->reachable && backref->errors)
1515 fprintf(stderr, "fs tree %llu refs %u %s\n",
1516 (unsigned long long)rec->objectid, rec->found_ref,
1517 rec->found_root_item ? "" : "not found");
1519 list_for_each_entry(backref, &rec->backrefs, list) {
1520 if (!backref->reachable)
1522 if (!backref->errors && rec->found_root_item)
1524 fprintf(stderr, "\tunresolved ref root %llu dir %llu"
1525 " index %llu namelen %u name %s error %x\n",
1526 (unsigned long long)backref->ref_root,
1527 (unsigned long long)backref->dir,
1528 (unsigned long long)backref->index,
1529 backref->namelen, backref->name,
1533 return errors > 0 ? 1 : 0;
1536 static int process_root_ref(struct extent_buffer *eb, int slot,
1537 struct btrfs_key *key,
1538 struct cache_tree *root_cache)
1544 struct btrfs_root_ref *ref;
1545 char namebuf[BTRFS_NAME_LEN];
1548 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
1550 dirid = btrfs_root_ref_dirid(eb, ref);
1551 index = btrfs_root_ref_sequence(eb, ref);
1552 name_len = btrfs_root_ref_name_len(eb, ref);
1554 if (name_len <= BTRFS_NAME_LEN) {
1558 len = BTRFS_NAME_LEN;
1559 error = REF_ERR_NAME_TOO_LONG;
1561 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1563 if (key->type == BTRFS_ROOT_REF_KEY) {
1564 add_root_backref(root_cache, key->offset, key->objectid, dirid,
1565 index, namebuf, len, key->type, error);
1567 add_root_backref(root_cache, key->objectid, key->offset, dirid,
1568 index, namebuf, len, key->type, error);
1573 static int check_fs_root(struct btrfs_root *root,
1574 struct cache_tree *root_cache,
1575 struct walk_control *wc)
1580 struct btrfs_path path;
1581 struct shared_node root_node;
1582 struct root_record *rec;
1583 struct btrfs_root_item *root_item = &root->root_item;
1585 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1586 rec = get_root_rec(root_cache, root->root_key.objectid);
1587 if (btrfs_root_refs(root_item) > 0)
1588 rec->found_root_item = 1;
1591 btrfs_init_path(&path);
1592 memset(&root_node, 0, sizeof(root_node));
1593 cache_tree_init(&root_node.root_cache);
1594 cache_tree_init(&root_node.inode_cache);
1596 level = btrfs_header_level(root->node);
1597 memset(wc->nodes, 0, sizeof(wc->nodes));
1598 wc->nodes[level] = &root_node;
1599 wc->active_node = level;
1600 wc->root_level = level;
1602 if (btrfs_root_refs(root_item) > 0 ||
1603 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1604 path.nodes[level] = root->node;
1605 extent_buffer_get(root->node);
1606 path.slots[level] = 0;
1608 struct btrfs_key key;
1609 struct btrfs_disk_key found_key;
1611 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1612 level = root_item->drop_level;
1613 path.lowest_level = level;
1614 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1616 btrfs_node_key(path.nodes[level], &found_key,
1618 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1619 sizeof(found_key)));
1623 wret = walk_down_tree(root, &path, wc, &level);
1629 wret = walk_up_tree(root, &path, wc, &level);
1635 btrfs_release_path(root, &path);
1637 merge_root_recs(root, &root_node.root_cache, root_cache);
1639 if (root_node.current) {
1640 root_node.current->checked = 1;
1641 maybe_free_inode_rec(&root_node.inode_cache,
1645 ret = check_inode_recs(root, &root_node.inode_cache);
1649 static int fs_root_objectid(u64 objectid)
1651 if (objectid == BTRFS_FS_TREE_OBJECTID ||
1652 objectid == BTRFS_TREE_RELOC_OBJECTID ||
1653 objectid == BTRFS_DATA_RELOC_TREE_OBJECTID ||
1654 (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1655 objectid <= BTRFS_LAST_FREE_OBJECTID))
1660 static int check_fs_roots(struct btrfs_root *root,
1661 struct cache_tree *root_cache)
1663 struct btrfs_path path;
1664 struct btrfs_key key;
1665 struct walk_control wc;
1666 struct extent_buffer *leaf;
1667 struct btrfs_root *tmp_root;
1668 struct btrfs_root *tree_root = root->fs_info->tree_root;
1672 memset(&wc, 0, sizeof(wc));
1673 cache_tree_init(&wc.shared);
1674 btrfs_init_path(&path);
1678 key.type = BTRFS_ROOT_ITEM_KEY;
1679 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1682 leaf = path.nodes[0];
1683 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1684 ret = btrfs_next_leaf(tree_root, &path);
1687 leaf = path.nodes[0];
1689 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1690 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1691 fs_root_objectid(key.objectid)) {
1692 tmp_root = btrfs_read_fs_root_no_cache(root->fs_info,
1694 ret = check_fs_root(tmp_root, root_cache, &wc);
1697 btrfs_free_fs_root(root->fs_info, tmp_root);
1698 } else if (key.type == BTRFS_ROOT_REF_KEY ||
1699 key.type == BTRFS_ROOT_BACKREF_KEY) {
1700 process_root_ref(leaf, path.slots[0], &key,
1705 btrfs_release_path(tree_root, &path);
1707 if (!cache_tree_empty(&wc.shared))
1708 fprintf(stderr, "warning line %d\n", __LINE__);
1713 static int check_node(struct btrfs_root *root,
1714 struct btrfs_disk_key *parent_key,
1715 struct extent_buffer *buf)
1718 struct btrfs_key cpukey;
1719 struct btrfs_disk_key key;
1720 u32 nritems = btrfs_header_nritems(buf);
1722 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1724 if (parent_key->type) {
1725 btrfs_node_key(buf, &key, 0);
1726 if (memcmp(parent_key, &key, sizeof(key)))
1729 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1730 btrfs_node_key(buf, &key, i);
1731 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
1732 if (btrfs_comp_keys(&key, &cpukey) >= 0)
1738 static int check_leaf(struct btrfs_root *root,
1739 struct btrfs_disk_key *parent_key,
1740 struct extent_buffer *buf)
1743 struct btrfs_key cpukey;
1744 struct btrfs_disk_key key;
1745 u32 nritems = btrfs_header_nritems(buf);
1747 if (btrfs_header_level(buf) != 0) {
1748 fprintf(stderr, "leaf is not a leaf %llu\n",
1749 (unsigned long long)btrfs_header_bytenr(buf));
1752 if (btrfs_leaf_free_space(root, buf) < 0) {
1753 fprintf(stderr, "leaf free space incorrect %llu %d\n",
1754 (unsigned long long)btrfs_header_bytenr(buf),
1755 btrfs_leaf_free_space(root, buf));
1762 btrfs_item_key(buf, &key, 0);
1763 if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
1764 fprintf(stderr, "leaf parent key incorrect %llu\n",
1765 (unsigned long long)btrfs_header_bytenr(buf));
1768 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1769 btrfs_item_key(buf, &key, i);
1770 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
1771 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
1772 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
1775 if (btrfs_item_offset_nr(buf, i) !=
1776 btrfs_item_end_nr(buf, i + 1)) {
1777 fprintf(stderr, "incorrect offsets %u %u\n",
1778 btrfs_item_offset_nr(buf, i),
1779 btrfs_item_end_nr(buf, i + 1));
1782 if (i == 0 && btrfs_item_end_nr(buf, i) !=
1783 BTRFS_LEAF_DATA_SIZE(root)) {
1784 fprintf(stderr, "bad item end %u wanted %u\n",
1785 btrfs_item_end_nr(buf, i),
1786 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
1793 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1795 struct list_head *cur = rec->backrefs.next;
1796 struct extent_backref *back;
1797 struct tree_backref *tback;
1798 struct data_backref *dback;
1802 while(cur != &rec->backrefs) {
1803 back = list_entry(cur, struct extent_backref, list);
1805 if (!back->found_extent_tree) {
1809 if (back->is_data) {
1810 dback = (struct data_backref *)back;
1811 fprintf(stderr, "Backref %llu %s %llu"
1812 " owner %llu offset %llu num_refs %lu"
1813 " not found in extent tree\n",
1814 (unsigned long long)rec->start,
1815 back->full_backref ?
1817 back->full_backref ?
1818 (unsigned long long)dback->parent:
1819 (unsigned long long)dback->root,
1820 (unsigned long long)dback->owner,
1821 (unsigned long long)dback->offset,
1822 (unsigned long)dback->num_refs);
1824 tback = (struct tree_backref *)back;
1825 fprintf(stderr, "Backref %llu parent %llu"
1826 " root %llu not found in extent tree\n",
1827 (unsigned long long)rec->start,
1828 (unsigned long long)tback->parent,
1829 (unsigned long long)tback->root);
1832 if (!back->is_data && !back->found_ref) {
1836 tback = (struct tree_backref *)back;
1837 fprintf(stderr, "Backref %llu %s %llu not referenced\n",
1838 (unsigned long long)rec->start,
1839 back->full_backref ? "parent" : "root",
1840 back->full_backref ?
1841 (unsigned long long)tback->parent :
1842 (unsigned long long)tback->root);
1844 if (back->is_data) {
1845 dback = (struct data_backref *)back;
1846 if (dback->found_ref != dback->num_refs) {
1850 fprintf(stderr, "Incorrect local backref count"
1851 " on %llu %s %llu owner %llu"
1852 " offset %llu found %u wanted %u\n",
1853 (unsigned long long)rec->start,
1854 back->full_backref ?
1856 back->full_backref ?
1857 (unsigned long long)dback->parent:
1858 (unsigned long long)dback->root,
1859 (unsigned long long)dback->owner,
1860 (unsigned long long)dback->offset,
1861 dback->found_ref, dback->num_refs);
1864 if (!back->is_data) {
1867 dback = (struct data_backref *)back;
1868 found += dback->found_ref;
1871 if (found != rec->refs) {
1875 fprintf(stderr, "Incorrect global backref count "
1876 "on %llu found %llu wanted %llu\n",
1877 (unsigned long long)rec->start,
1878 (unsigned long long)found,
1879 (unsigned long long)rec->refs);
1885 static int free_all_extent_backrefs(struct extent_record *rec)
1887 struct extent_backref *back;
1888 struct list_head *cur;
1889 while (!list_empty(&rec->backrefs)) {
1890 cur = rec->backrefs.next;
1891 back = list_entry(cur, struct extent_backref, list);
1898 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1899 struct extent_record *rec)
1901 if (rec->content_checked && rec->owner_ref_checked &&
1902 rec->extent_item_refs == rec->refs && rec->refs > 0 &&
1903 !all_backpointers_checked(rec, 0)) {
1904 remove_cache_extent(extent_cache, &rec->cache);
1905 free_all_extent_backrefs(rec);
1911 static int check_owner_ref(struct btrfs_root *root,
1912 struct extent_record *rec,
1913 struct extent_buffer *buf)
1915 struct extent_backref *node;
1916 struct tree_backref *back;
1917 struct btrfs_root *ref_root;
1918 struct btrfs_key key;
1919 struct btrfs_path path;
1923 list_for_each_entry(node, &rec->backrefs, list) {
1926 if (!node->found_ref)
1928 if (node->full_backref)
1930 back = (struct tree_backref *)node;
1931 if (btrfs_header_owner(buf) == back->root)
1934 BUG_ON(rec->is_root);
1936 /* try to find the block by search corresponding fs tree */
1937 key.objectid = btrfs_header_owner(buf);
1938 key.type = BTRFS_ROOT_ITEM_KEY;
1939 key.offset = (u64)-1;
1941 ref_root = btrfs_read_fs_root(root->fs_info, &key);
1942 BUG_ON(IS_ERR(ref_root));
1944 level = btrfs_header_level(buf);
1946 btrfs_item_key_to_cpu(buf, &key, 0);
1948 btrfs_node_key_to_cpu(buf, &key, 0);
1950 btrfs_init_path(&path);
1951 path.lowest_level = level + 1;
1952 btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
1954 if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
1955 path.slots[level + 1]))
1956 rec->owner_ref_checked = 1;
1958 btrfs_release_path(ref_root, &path);
1959 return found ? 0 : 1;
1962 static int check_block(struct btrfs_root *root,
1963 struct cache_tree *extent_cache,
1964 struct extent_buffer *buf, u64 flags)
1966 struct extent_record *rec;
1967 struct cache_extent *cache;
1970 cache = find_cache_extent(extent_cache, buf->start, buf->len);
1973 rec = container_of(cache, struct extent_record, cache);
1974 if (btrfs_is_leaf(buf)) {
1975 ret = check_leaf(root, &rec->parent_key, buf);
1977 ret = check_node(root, &rec->parent_key, buf);
1980 fprintf(stderr, "bad block %llu\n",
1981 (unsigned long long)buf->start);
1983 rec->content_checked = 1;
1984 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
1985 rec->owner_ref_checked = 1;
1987 ret = check_owner_ref(root, rec, buf);
1989 rec->owner_ref_checked = 1;
1993 maybe_free_extent_rec(extent_cache, rec);
1997 static struct tree_backref *find_tree_backref(struct extent_record *rec,
1998 u64 parent, u64 root)
2000 struct list_head *cur = rec->backrefs.next;
2001 struct extent_backref *node;
2002 struct tree_backref *back;
2004 while(cur != &rec->backrefs) {
2005 node = list_entry(cur, struct extent_backref, list);
2009 back = (struct tree_backref *)node;
2011 if (!node->full_backref)
2013 if (parent == back->parent)
2016 if (node->full_backref)
2018 if (back->root == root)
2025 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2026 u64 parent, u64 root)
2028 struct tree_backref *ref = malloc(sizeof(*ref));
2029 memset(&ref->node, 0, sizeof(ref->node));
2031 ref->parent = parent;
2032 ref->node.full_backref = 1;
2035 ref->node.full_backref = 0;
2037 list_add_tail(&ref->node.list, &rec->backrefs);
2041 static struct data_backref *find_data_backref(struct extent_record *rec,
2042 u64 parent, u64 root,
2043 u64 owner, u64 offset)
2045 struct list_head *cur = rec->backrefs.next;
2046 struct extent_backref *node;
2047 struct data_backref *back;
2049 while(cur != &rec->backrefs) {
2050 node = list_entry(cur, struct extent_backref, list);
2054 back = (struct data_backref *)node;
2056 if (!node->full_backref)
2058 if (parent == back->parent)
2061 if (node->full_backref)
2063 if (back->root == root && back->owner == owner &&
2064 back->offset == offset)
2071 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2072 u64 parent, u64 root,
2073 u64 owner, u64 offset)
2075 struct data_backref *ref = malloc(sizeof(*ref));
2076 memset(&ref->node, 0, sizeof(ref->node));
2077 ref->node.is_data = 1;
2079 ref->parent = parent;
2082 ref->node.full_backref = 1;
2086 ref->offset = offset;
2087 ref->node.full_backref = 0;
2091 list_add_tail(&ref->node.list, &rec->backrefs);
2095 static int add_extent_rec(struct cache_tree *extent_cache,
2096 struct btrfs_key *parent_key,
2097 u64 start, u64 nr, u64 extent_item_refs,
2098 int is_root, int inc_ref, int set_checked)
2100 struct extent_record *rec;
2101 struct cache_extent *cache;
2104 cache = find_cache_extent(extent_cache, start, nr);
2106 rec = container_of(cache, struct extent_record, cache);
2112 if (start != rec->start) {
2113 fprintf(stderr, "warning, start mismatch %llu %llu\n",
2114 (unsigned long long)rec->start,
2115 (unsigned long long)start);
2118 if (extent_item_refs) {
2119 if (rec->extent_item_refs) {
2120 fprintf(stderr, "block %llu rec "
2121 "extent_item_refs %llu, passed %llu\n",
2122 (unsigned long long)start,
2123 (unsigned long long)
2124 rec->extent_item_refs,
2125 (unsigned long long)extent_item_refs);
2127 rec->extent_item_refs = extent_item_refs;
2132 rec->content_checked = 1;
2133 rec->owner_ref_checked = 1;
2137 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2139 maybe_free_extent_rec(extent_cache, rec);
2142 rec = malloc(sizeof(*rec));
2145 rec->content_checked = 0;
2146 rec->owner_ref_checked = 0;
2147 INIT_LIST_HEAD(&rec->backrefs);
2159 if (extent_item_refs)
2160 rec->extent_item_refs = extent_item_refs;
2162 rec->extent_item_refs = 0;
2165 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2167 memset(&rec->parent_key, 0, sizeof(*parent_key));
2169 rec->cache.start = start;
2170 rec->cache.size = nr;
2171 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
2175 rec->content_checked = 1;
2176 rec->owner_ref_checked = 1;
2181 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
2182 u64 parent, u64 root, int found_ref)
2184 struct extent_record *rec;
2185 struct tree_backref *back;
2186 struct cache_extent *cache;
2188 cache = find_cache_extent(extent_cache, bytenr, 1);
2190 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2191 cache = find_cache_extent(extent_cache, bytenr, 1);
2196 rec = container_of(cache, struct extent_record, cache);
2197 if (rec->start != bytenr) {
2201 back = find_tree_backref(rec, parent, root);
2203 back = alloc_tree_backref(rec, parent, root);
2206 if (back->node.found_ref) {
2207 fprintf(stderr, "Extent back ref already exists "
2208 "for %llu parent %llu root %llu \n",
2209 (unsigned long long)bytenr,
2210 (unsigned long long)parent,
2211 (unsigned long long)root);
2213 back->node.found_ref = 1;
2215 if (back->node.found_extent_tree) {
2216 fprintf(stderr, "Extent back ref already exists "
2217 "for %llu parent %llu root %llu \n",
2218 (unsigned long long)bytenr,
2219 (unsigned long long)parent,
2220 (unsigned long long)root);
2222 back->node.found_extent_tree = 1;
2227 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
2228 u64 parent, u64 root, u64 owner, u64 offset,
2229 u32 num_refs, int found_ref)
2231 struct extent_record *rec;
2232 struct data_backref *back;
2233 struct cache_extent *cache;
2235 cache = find_cache_extent(extent_cache, bytenr, 1);
2237 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2238 cache = find_cache_extent(extent_cache, bytenr, 1);
2243 rec = container_of(cache, struct extent_record, cache);
2244 if (rec->start != bytenr) {
2247 back = find_data_backref(rec, parent, root, owner, offset);
2249 back = alloc_data_backref(rec, parent, root, owner, offset);
2252 BUG_ON(num_refs != 1);
2253 back->node.found_ref = 1;
2254 back->found_ref += 1;
2256 if (back->node.found_extent_tree) {
2257 fprintf(stderr, "Extent back ref already exists "
2258 "for %llu parent %llu root %llu"
2259 "owner %llu offset %llu num_refs %lu\n",
2260 (unsigned long long)bytenr,
2261 (unsigned long long)parent,
2262 (unsigned long long)root,
2263 (unsigned long long)owner,
2264 (unsigned long long)offset,
2265 (unsigned long)num_refs);
2267 back->num_refs = num_refs;
2268 back->node.found_extent_tree = 1;
2273 static int add_pending(struct cache_tree *pending,
2274 struct cache_tree *seen, u64 bytenr, u32 size)
2277 ret = insert_cache_extent(seen, bytenr, size);
2280 insert_cache_extent(pending, bytenr, size);
2284 static int pick_next_pending(struct cache_tree *pending,
2285 struct cache_tree *reada,
2286 struct cache_tree *nodes,
2287 u64 last, struct block_info *bits, int bits_nr,
2290 unsigned long node_start = last;
2291 struct cache_extent *cache;
2294 cache = find_first_cache_extent(reada, 0);
2296 bits[0].start = cache->start;
2297 bits[1].size = cache->size;
2302 if (node_start > 32768)
2303 node_start -= 32768;
2305 cache = find_first_cache_extent(nodes, node_start);
2307 cache = find_first_cache_extent(nodes, 0);
2310 cache = find_first_cache_extent(pending, 0);
2315 bits[ret].start = cache->start;
2316 bits[ret].size = cache->size;
2317 cache = next_cache_extent(cache);
2319 } while (cache && ret < bits_nr);
2325 bits[ret].start = cache->start;
2326 bits[ret].size = cache->size;
2327 cache = next_cache_extent(cache);
2329 } while (cache && ret < bits_nr);
2331 if (bits_nr - ret > 8) {
2332 u64 lookup = bits[0].start + bits[0].size;
2333 struct cache_extent *next;
2334 next = find_first_cache_extent(pending, lookup);
2336 if (next->start - lookup > 32768)
2338 bits[ret].start = next->start;
2339 bits[ret].size = next->size;
2340 lookup = next->start + next->size;
2344 next = next_cache_extent(next);
2352 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2353 static int process_extent_ref_v0(struct cache_tree *extent_cache,
2354 struct extent_buffer *leaf, int slot)
2356 struct btrfs_extent_ref_v0 *ref0;
2357 struct btrfs_key key;
2359 btrfs_item_key_to_cpu(leaf, &key, slot);
2360 ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
2361 if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
2362 add_tree_backref(extent_cache, key.objectid, key.offset,
2365 add_data_backref(extent_cache, key.objectid, key.offset, 0,
2366 0, 0, btrfs_ref_count_v0(leaf, ref0), 0);
2372 static int process_extent_item(struct cache_tree *extent_cache,
2373 struct extent_buffer *eb, int slot)
2375 struct btrfs_extent_item *ei;
2376 struct btrfs_extent_inline_ref *iref;
2377 struct btrfs_extent_data_ref *dref;
2378 struct btrfs_shared_data_ref *sref;
2379 struct btrfs_key key;
2383 u32 item_size = btrfs_item_size_nr(eb, slot);
2387 btrfs_item_key_to_cpu(eb, &key, slot);
2389 if (item_size < sizeof(*ei)) {
2390 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2391 struct btrfs_extent_item_v0 *ei0;
2392 BUG_ON(item_size != sizeof(*ei0));
2393 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
2394 refs = btrfs_extent_refs_v0(eb, ei0);
2398 return add_extent_rec(extent_cache, NULL, key.objectid,
2399 key.offset, refs, 0, 0, 0);
2402 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
2403 refs = btrfs_extent_refs(eb, ei);
2405 add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
2408 ptr = (unsigned long)(ei + 1);
2409 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2410 ptr += sizeof(struct btrfs_tree_block_info);
2412 end = (unsigned long)ei + item_size;
2414 iref = (struct btrfs_extent_inline_ref *)ptr;
2415 type = btrfs_extent_inline_ref_type(eb, iref);
2416 offset = btrfs_extent_inline_ref_offset(eb, iref);
2418 case BTRFS_TREE_BLOCK_REF_KEY:
2419 add_tree_backref(extent_cache, key.objectid,
2422 case BTRFS_SHARED_BLOCK_REF_KEY:
2423 add_tree_backref(extent_cache, key.objectid,
2426 case BTRFS_EXTENT_DATA_REF_KEY:
2427 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
2428 add_data_backref(extent_cache, key.objectid, 0,
2429 btrfs_extent_data_ref_root(eb, dref),
2430 btrfs_extent_data_ref_objectid(eb,
2432 btrfs_extent_data_ref_offset(eb, dref),
2433 btrfs_extent_data_ref_count(eb, dref),
2436 case BTRFS_SHARED_DATA_REF_KEY:
2437 sref = (struct btrfs_shared_data_ref *)(iref + 1);
2438 add_data_backref(extent_cache, key.objectid, offset,
2440 btrfs_shared_data_ref_count(eb, sref),
2446 ptr += btrfs_extent_inline_ref_size(type);
2452 static int run_next_block(struct btrfs_root *root,
2453 struct block_info *bits,
2456 struct cache_tree *pending,
2457 struct cache_tree *seen,
2458 struct cache_tree *reada,
2459 struct cache_tree *nodes,
2460 struct cache_tree *extent_cache)
2462 struct extent_buffer *buf;
2471 struct btrfs_key key;
2472 struct cache_extent *cache;
2475 ret = pick_next_pending(pending, reada, nodes, *last, bits,
2476 bits_nr, &reada_bits);
2481 for(i = 0; i < ret; i++) {
2482 insert_cache_extent(reada, bits[i].start,
2485 /* fixme, get the parent transid */
2486 readahead_tree_block(root, bits[i].start,
2490 *last = bits[0].start;
2491 bytenr = bits[0].start;
2492 size = bits[0].size;
2494 cache = find_cache_extent(pending, bytenr, size);
2496 remove_cache_extent(pending, cache);
2499 cache = find_cache_extent(reada, bytenr, size);
2501 remove_cache_extent(reada, cache);
2504 cache = find_cache_extent(nodes, bytenr, size);
2506 remove_cache_extent(nodes, cache);
2510 /* fixme, get the real parent transid */
2511 buf = read_tree_block(root, bytenr, size, 0);
2512 nritems = btrfs_header_nritems(buf);
2514 ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
2516 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
2521 owner = btrfs_header_owner(buf);
2524 ret = check_block(root, extent_cache, buf, flags);
2526 if (btrfs_is_leaf(buf)) {
2527 btree_space_waste += btrfs_leaf_free_space(root, buf);
2528 for (i = 0; i < nritems; i++) {
2529 struct btrfs_file_extent_item *fi;
2530 btrfs_item_key_to_cpu(buf, &key, i);
2531 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
2532 process_extent_item(extent_cache, buf, i);
2535 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
2537 btrfs_item_size_nr(buf, i);
2540 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
2543 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
2544 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2545 process_extent_ref_v0(extent_cache, buf, i);
2552 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2553 add_tree_backref(extent_cache, key.objectid, 0,
2557 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2558 add_tree_backref(extent_cache, key.objectid,
2562 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
2563 struct btrfs_extent_data_ref *ref;
2564 ref = btrfs_item_ptr(buf, i,
2565 struct btrfs_extent_data_ref);
2566 add_data_backref(extent_cache,
2568 btrfs_extent_data_ref_root(buf, ref),
2569 btrfs_extent_data_ref_objectid(buf,
2571 btrfs_extent_data_ref_offset(buf, ref),
2572 btrfs_extent_data_ref_count(buf, ref),
2576 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
2577 struct btrfs_shared_data_ref *ref;
2578 ref = btrfs_item_ptr(buf, i,
2579 struct btrfs_shared_data_ref);
2580 add_data_backref(extent_cache,
2581 key.objectid, key.offset, 0, 0, 0,
2582 btrfs_shared_data_ref_count(buf, ref),
2586 if (key.type != BTRFS_EXTENT_DATA_KEY)
2588 fi = btrfs_item_ptr(buf, i,
2589 struct btrfs_file_extent_item);
2590 if (btrfs_file_extent_type(buf, fi) ==
2591 BTRFS_FILE_EXTENT_INLINE)
2593 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2596 data_bytes_allocated +=
2597 btrfs_file_extent_disk_num_bytes(buf, fi);
2598 if (data_bytes_allocated < root->sectorsize) {
2601 data_bytes_referenced +=
2602 btrfs_file_extent_num_bytes(buf, fi);
2603 ret = add_extent_rec(extent_cache, NULL,
2604 btrfs_file_extent_disk_bytenr(buf, fi),
2605 btrfs_file_extent_disk_num_bytes(buf, fi),
2607 add_data_backref(extent_cache,
2608 btrfs_file_extent_disk_bytenr(buf, fi),
2609 parent, owner, key.objectid, key.offset -
2610 btrfs_file_extent_offset(buf, fi), 1, 1);
2615 level = btrfs_header_level(buf);
2616 for (i = 0; i < nritems; i++) {
2617 u64 ptr = btrfs_node_blockptr(buf, i);
2618 u32 size = btrfs_level_size(root, level - 1);
2619 btrfs_node_key_to_cpu(buf, &key, i);
2620 ret = add_extent_rec(extent_cache, &key,
2621 ptr, size, 0, 0, 1, 0);
2624 add_tree_backref(extent_cache, ptr, parent,
2628 add_pending(nodes, seen, ptr, size);
2630 add_pending(pending, seen, ptr, size);
2633 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2634 nritems) * sizeof(struct btrfs_key_ptr);
2636 total_btree_bytes += buf->len;
2637 if (fs_root_objectid(btrfs_header_owner(buf)))
2638 total_fs_tree_bytes += buf->len;
2639 if (!found_old_backref &&
2640 btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
2641 btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
2642 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
2643 found_old_backref = 1;
2644 free_extent_buffer(buf);
2648 static int add_root_to_pending(struct extent_buffer *buf,
2649 struct block_info *bits,
2651 struct cache_tree *extent_cache,
2652 struct cache_tree *pending,
2653 struct cache_tree *seen,
2654 struct cache_tree *reada,
2655 struct cache_tree *nodes,
2656 struct btrfs_key *root_key)
2658 if (btrfs_header_level(buf) > 0)
2659 add_pending(nodes, seen, buf->start, buf->len);
2661 add_pending(pending, seen, buf->start, buf->len);
2662 add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2665 if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
2666 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2667 add_tree_backref(extent_cache, buf->start, buf->start, 0, 1);
2669 add_tree_backref(extent_cache, buf->start, 0,
2670 root_key->objectid, 1);
2674 static int check_extent_refs(struct btrfs_root *root,
2675 struct cache_tree *extent_cache)
2677 struct extent_record *rec;
2678 struct cache_extent *cache;
2682 cache = find_first_cache_extent(extent_cache, 0);
2685 rec = container_of(cache, struct extent_record, cache);
2686 if (rec->refs != rec->extent_item_refs) {
2687 fprintf(stderr, "ref mismatch on [%llu %llu] ",
2688 (unsigned long long)rec->start,
2689 (unsigned long long)rec->nr);
2690 fprintf(stderr, "extent item %llu, found %llu\n",
2691 (unsigned long long)rec->extent_item_refs,
2692 (unsigned long long)rec->refs);
2695 if (all_backpointers_checked(rec, 1)) {
2696 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
2697 (unsigned long long)rec->start,
2698 (unsigned long long)rec->nr);
2702 if (!rec->owner_ref_checked) {
2703 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
2704 (unsigned long long)rec->start,
2705 (unsigned long long)rec->nr);
2709 remove_cache_extent(extent_cache, cache);
2710 free_all_extent_backrefs(rec);
2716 static int check_extents(struct btrfs_root *root)
2718 struct cache_tree extent_cache;
2719 struct cache_tree seen;
2720 struct cache_tree pending;
2721 struct cache_tree reada;
2722 struct cache_tree nodes;
2723 struct btrfs_path path;
2724 struct btrfs_key key;
2725 struct btrfs_key found_key;
2728 struct block_info *bits;
2730 struct extent_buffer *leaf;
2732 struct btrfs_root_item ri;
2734 cache_tree_init(&extent_cache);
2735 cache_tree_init(&seen);
2736 cache_tree_init(&pending);
2737 cache_tree_init(&nodes);
2738 cache_tree_init(&reada);
2741 bits = malloc(bits_nr * sizeof(struct block_info));
2747 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2748 &extent_cache, &pending, &seen, &reada, &nodes,
2749 &root->fs_info->tree_root->root_key);
2751 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2752 &extent_cache, &pending, &seen, &reada, &nodes,
2753 &root->fs_info->chunk_root->root_key);
2755 btrfs_init_path(&path);
2758 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2759 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2763 leaf = path.nodes[0];
2764 slot = path.slots[0];
2765 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2766 ret = btrfs_next_leaf(root, &path);
2769 leaf = path.nodes[0];
2770 slot = path.slots[0];
2772 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2773 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2774 unsigned long offset;
2775 struct extent_buffer *buf;
2777 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2778 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2779 buf = read_tree_block(root->fs_info->tree_root,
2780 btrfs_root_bytenr(&ri),
2781 btrfs_level_size(root,
2782 btrfs_root_level(&ri)), 0);
2783 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2784 &pending, &seen, &reada, &nodes,
2786 free_extent_buffer(buf);
2790 btrfs_release_path(root, &path);
2792 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2793 &seen, &reada, &nodes, &extent_cache);
2797 ret = check_extent_refs(root, &extent_cache);
2801 static void print_usage(void)
2803 fprintf(stderr, "usage: btrfsck dev\n");
2804 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2808 int main(int ac, char **av)
2810 struct cache_tree root_cache;
2811 struct btrfs_root *root;
2818 c = getopt(ac, av, "s:");
2824 bytenr = btrfs_sb_offset(num);
2825 printf("using SB copy %d, bytenr %llu\n", num,
2826 (unsigned long long)bytenr);
2838 cache_tree_init(&root_cache);
2840 if((ret = check_mounted(av[optind])) < 0) {
2841 fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret));
2844 fprintf(stderr, "%s is currently mounted. Aborting.\n", av[optind]);
2848 root = open_ctree(av[optind], bytenr, 0);
2853 ret = check_extents(root);
2856 ret = check_fs_roots(root, &root_cache);
2860 ret = check_root_refs(root, &root_cache);
2862 free_root_recs(&root_cache);
2865 if (found_old_backref) {
2867 * there was a disk format change when mixed
2868 * backref was in testing tree. The old format
2869 * existed about one week.
2871 printf("\n * Found old mixed backref format. "
2872 "The old format is not supported! *"
2873 "\n * Please mount the FS in readonly mode, "
2874 "backup data and re-format the FS. *\n\n");
2877 printf("found %llu bytes used err is %d\n",
2878 (unsigned long long)bytes_used, ret);
2879 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2880 printf("total tree bytes: %llu\n",
2881 (unsigned long long)total_btree_bytes);
2882 printf("total fs tree bytes: %llu\n",
2883 (unsigned long long)total_fs_tree_bytes);
2884 printf("btree space waste bytes: %llu\n",
2885 (unsigned long long)btree_space_waste);
2886 printf("file data blocks allocated: %llu\n referenced %llu\n",
2887 (unsigned long long)data_bytes_allocated,
2888 (unsigned long long)data_bytes_referenced);
2889 printf("%s\n", BTRFS_BUILD_VERSION);