?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
make btrfs cross compilation friendly
[btrfs-progs-unstable/devel.git] / btrfsck.c
blobe3cd43540f4e1f235b8dc394449c02d6b0b7037b
1 /*
2 * Copyright (C) 2007 Oracle. All rights reserved.
3 *
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.
7 *
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.
12 *
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.
17 */
18
19 #define _XOPEN_SOURCE 500
20 #define _GNU_SOURCE 1
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <unistd.h>
24 #include <fcntl.h>
25 #include <sys/stat.h>
26 #include "kerncompat.h"
27 #include "ctree.h"
28 #include "disk-io.h"
29 #include "print-tree.h"
30 #include "transaction.h"
31 #include "list.h"
32 #include "version.h"
33 #include "utils.h"
34
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;
43
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;
50 };
51
52 struct data_backref {
53 struct extent_backref node;
54 union {
55 u64 parent;
56 u64 root;
57 };
58 u64 owner;
59 u64 offset;
60 u32 num_refs;
61 u32 found_ref;
62 };
63
64 struct tree_backref {
65 struct extent_backref node;
66 union {
67 u64 parent;
68 u64 root;
69 };
70 };
71
72 struct extent_record {
73 struct list_head backrefs;
74 struct cache_extent cache;
75 struct btrfs_disk_key parent_key;
76 u64 start;
77 u64 nr;
78 u64 refs;
79 u64 extent_item_refs;
80 unsigned int content_checked:1;
81 unsigned int owner_ref_checked:1;
82 unsigned int is_root:1;
83 };
84
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;
91 int errors;
92 u64 dir;
93 u64 index;
94 u16 namelen;
95 char name[0];
96 };
97
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)
111
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;
122 int errors;
123
124 u64 ino;
125 u32 nlink;
126 u32 imode;
127 u64 isize;
128 u64 nbytes;
129
130 u32 found_link;
131 u64 found_size;
132 u64 extent_start;
133 u64 extent_end;
134 u64 first_extent_gap;
135
136 u32 refs;
137 };
138
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)
153
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;
161 int errors;
162 u64 ref_root;
163 u64 dir;
164 u64 index;
165 u16 namelen;
166 char name[0];
167 };
168
169 struct root_record {
170 struct list_head backrefs;
171 struct cache_extent cache;
172 unsigned int found_root_item:1;
173 u64 objectid;
174 u32 found_ref;
175 };
176
177 struct ptr_node {
178 struct cache_extent cache;
179 void *data;
180 };
181
182 struct shared_node {
183 struct cache_extent cache;
184 struct cache_tree root_cache;
185 struct cache_tree inode_cache;
186 struct inode_record *current;
187 u32 refs;
188 };
189
190 struct block_info {
191 u64 start;
192 u32 size;
193 };
194
195 struct walk_control {
196 struct cache_tree shared;
197 struct shared_node *nodes[BTRFS_MAX_LEVEL];
198 int active_node;
199 int root_level;
200 };
201
202 static u8 imode_to_type(u32 imode)
203 {
204 #define S_SHIFT 12
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,
213 };
214
215 return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
216 #undef S_SHIFT
217 }
218
219 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
220 {
221 struct inode_record *rec;
222 struct inode_backref *backref;
223 struct inode_backref *orig;
224 size_t size;
225
226 rec = malloc(sizeof(*rec));
227 memcpy(rec, orig_rec, sizeof(*rec));
228 rec->refs = 1;
229 INIT_LIST_HEAD(&rec->backrefs);
230
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);
236 }
237 return rec;
238 }
239
240 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
241 u64 ino, int mod)
242 {
243 struct ptr_node *node;
244 struct cache_extent *cache;
245 struct inode_record *rec = NULL;
246 int ret;
247
248 cache = find_cache_extent(inode_cache, ino, 1);
249 if (cache) {
250 node = container_of(cache, struct ptr_node, cache);
251 rec = node->data;
252 if (mod && rec->refs > 1) {
253 node->data = clone_inode_rec(rec);
254 rec->refs--;
255 rec = node->data;
256 }
257 } else if (mod) {
258 rec = calloc(1, sizeof(*rec));
259 rec->ino = ino;
260 rec->extent_start = (u64)-1;
261 rec->first_extent_gap = (u64)-1;
262 rec->refs = 1;
263 INIT_LIST_HEAD(&rec->backrefs);
264
265 node = malloc(sizeof(*node));
266 node->cache.start = ino;
267 node->cache.size = 1;
268 node->data = rec;
269
270 ret = insert_existing_cache_extent(inode_cache, &node->cache);
271 BUG_ON(ret);
272 }
273 return rec;
274 }
275
276 static void free_inode_rec(struct inode_record *rec)
277 {
278 struct inode_backref *backref;
279
280 if (--rec->refs > 0)
281 return;
282
283 while (!list_empty(&rec->backrefs)) {
284 backref = list_entry(rec->backrefs.next,
285 struct inode_backref, list);
286 list_del(&backref->list);
287 free(backref);
288 }
289 free(rec);
290 }
291
292 static int can_free_inode_rec(struct inode_record *rec)
293 {
294 if (!rec->errors && rec->checked && rec->found_inode_item &&
295 rec->nlink == rec->found_link && list_empty(&rec->backrefs))
296 return 1;
297 return 0;
298 }
299
300 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
301 struct inode_record *rec)
302 {
303 struct cache_extent *cache;
304 struct inode_backref *tmp, *backref;
305 struct ptr_node *node;
306 unsigned char filetype;
307
308 if (!rec->found_inode_item)
309 return;
310
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);
318 free(backref);
319 }
320 }
321 }
322
323 if (!rec->checked || rec->merging)
324 return;
325
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;
341 }
342
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;
348 }
349
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);
356 free(node);
357 free_inode_rec(rec);
358 }
359 }
360
361 static int check_orphan_item(struct btrfs_root *root, u64 ino)
362 {
363 struct btrfs_path path;
364 struct btrfs_key key;
365 int ret;
366
367 key.objectid = BTRFS_ORPHAN_OBJECTID;
368 key.type = BTRFS_ORPHAN_ITEM_KEY;
369 key.offset = ino;
370
371 btrfs_init_path(&path);
372 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
373 btrfs_release_path(root, &path);
374 if (ret > 0)
375 ret = -ENOENT;
376 return ret;
377 }
378
379 static int process_inode_item(struct extent_buffer *eb,
380 int slot, struct btrfs_key *key,
381 struct shared_node *active_node)
382 {
383 struct inode_record *rec;
384 struct btrfs_inode_item *item;
385
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;
390 return 1;
391 }
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)
398 rec->nodatasum = 1;
399 rec->found_inode_item = 1;
400 if (rec->nlink == 0)
401 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
402 maybe_free_inode_rec(&active_node->inode_cache, rec);
403 return 0;
404 }
405
406 static struct inode_backref *get_inode_backref(struct inode_record *rec,
407 const char *name,
408 int namelen, u64 dir)
409 {
410 struct inode_backref *backref;
411
412 list_for_each_entry(backref, &rec->backrefs, list) {
413 if (backref->dir != dir || backref->namelen != namelen)
414 continue;
415 if (memcmp(name, backref->name, namelen))
416 continue;
417 return backref;
418 }
419
420 backref = malloc(sizeof(*backref) + namelen + 1);
421 memset(backref, 0, sizeof(*backref));
422 backref->dir = dir;
423 backref->namelen = namelen;
424 memcpy(backref->name, name, namelen);
425 backref->name[namelen] = '\0';
426 list_add_tail(&backref->list, &rec->backrefs);
427 return backref;
428 }
429
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)
434 {
435 struct inode_record *rec;
436 struct inode_backref *backref;
437
438 rec = get_inode_rec(inode_cache, ino, 1);
439 backref = get_inode_backref(rec, name, namelen, dir);
440 if (errors)
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;
449
450 backref->index = index;
451 backref->filetype = filetype;
452 backref->found_dir_index = 1;
453 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
454 rec->found_link++;
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;
459
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;
467
468 backref->index = index;
469 backref->found_inode_ref = 1;
470 } else {
471 BUG_ON(1);
472 }
473
474 maybe_free_inode_rec(inode_cache, rec);
475 return 0;
476 }
477
478 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
479 struct cache_tree *dst_cache)
480 {
481 struct inode_backref *backref;
482 u32 dir_count = 0;
483
484 dst->merging = 1;
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);
491 }
492 if (backref->found_dir_item) {
493 dir_count++;
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);
498 }
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);
504 }
505 }
506
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;
517
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;
525 } else {
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;
533 }
534 }
535
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;
545 } else {
546 dst->errors |= I_ERR_DUP_INODE_ITEM;
547 }
548 }
549 dst->merging = 0;
550
551 return 0;
552 }
553
554 static int splice_shared_node(struct shared_node *src_node,
555 struct shared_node *dst_node)
556 {
557 struct cache_extent *cache;
558 struct ptr_node *node, *ins;
559 struct cache_tree *src, *dst;
560 struct inode_record *rec, *conflict;
561 u64 current_ino = 0;
562 int splice = 0;
563 int ret;
564
565 if (--src_node->refs == 0)
566 splice = 1;
567 if (src_node->current)
568 current_ino = src_node->current->ino;
569
570 src = &src_node->root_cache;
571 dst = &dst_node->root_cache;
572 again:
573 cache = find_first_cache_extent(src, 0);
574 while (cache) {
575 node = container_of(cache, struct ptr_node, cache);
576 rec = node->data;
577 cache = next_cache_extent(cache);
578
579 if (splice) {
580 remove_cache_extent(src, &node->cache);
581 ins = node;
582 } else {
583 ins = malloc(sizeof(*ins));
584 ins->cache.start = node->cache.start;
585 ins->cache.size = node->cache.size;
586 ins->data = rec;
587 rec->refs++;
588 }
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);
593 if (rec->checked) {
594 conflict->checked = 1;
595 if (dst_node->current == conflict)
596 dst_node->current = NULL;
597 }
598 maybe_free_inode_rec(dst, conflict);
599 free_inode_rec(rec);
600 free(ins);
601 } else {
602 BUG_ON(ret);
603 }
604 }
605
606 if (src == &src_node->root_cache) {
607 src = &src_node->inode_cache;
608 dst = &dst_node->inode_cache;
609 goto again;
610 }
611
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);
617 }
618 dst_node->current = get_inode_rec(dst, current_ino, 1);
619 }
620 return 0;
621 }
622
623 static void free_inode_recs(struct cache_tree *inode_cache)
624 {
625 struct cache_extent *cache;
626 struct ptr_node *node;
627 struct inode_record *rec;
628
629 while (1) {
630 cache = find_first_cache_extent(inode_cache, 0);
631 if (!cache)
632 break;
633 node = container_of(cache, struct ptr_node, cache);
634 rec = node->data;
635 remove_cache_extent(inode_cache, &node->cache);
636 free(node);
637 free_inode_rec(rec);
638 }
639 }
640
641 static struct shared_node *find_shared_node(struct cache_tree *shared,
642 u64 bytenr)
643 {
644 struct cache_extent *cache;
645 struct shared_node *node;
646
647 cache = find_cache_extent(shared, bytenr, 1);
648 if (cache) {
649 node = container_of(cache, struct shared_node, cache);
650 return node;
651 }
652 return NULL;
653 }
654
655 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
656 {
657 int ret;
658 struct shared_node *node;
659
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);
665 node->refs = refs;
666
667 ret = insert_existing_cache_extent(shared, &node->cache);
668 BUG_ON(ret);
669 return 0;
670 }
671
672 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
673 struct walk_control *wc, int level)
674 {
675 struct shared_node *node;
676 struct shared_node *dest;
677
678 if (level == wc->active_node)
679 return 0;
680
681 BUG_ON(wc->active_node <= level);
682 node = find_shared_node(&wc->shared, bytenr);
683 if (!node) {
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;
688 return 0;
689 }
690
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);
697 free(node);
698 }
699 return 1;
700 }
701
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);
706 free(node);
707 }
708 return 1;
709 }
710
711 static int leave_shared_node(struct btrfs_root *root,
712 struct walk_control *wc, int level)
713 {
714 struct shared_node *node;
715 struct shared_node *dest;
716 int i;
717
718 if (level == wc->root_level)
719 return 0;
720
721 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
722 if (wc->nodes[i])
723 break;
724 }
725 BUG_ON(i >= BTRFS_MAX_LEVEL);
726
727 node = wc->nodes[wc->active_node];
728 wc->nodes[wc->active_node] = NULL;
729 wc->active_node = i;
730
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);
736 } else {
737 BUG_ON(node->refs < 2);
738 node->refs--;
739 }
740 return 0;
741 }
742
743 static int process_dir_item(struct extent_buffer *eb,
744 int slot, struct btrfs_key *key,
745 struct shared_node *active_node)
746 {
747 u32 total;
748 u32 cur = 0;
749 u32 len;
750 u32 name_len;
751 u32 data_len;
752 int error;
753 int nritems = 0;
754 int filetype;
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];
761
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;
766
767 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
768 total = btrfs_item_size_nr(eb, slot);
769 while (cur < total) {
770 nritems++;
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);
775
776 rec->found_size += name_len;
777 if (name_len <= BTRFS_NAME_LEN) {
778 len = name_len;
779 error = 0;
780 } else {
781 len = BTRFS_NAME_LEN;
782 error = REF_ERR_NAME_TOO_LONG;
783 }
784 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
785
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);
794 } else {
795 fprintf(stderr, "warning line %d\n", __LINE__);
796 }
797
798 len = sizeof(*di) + name_len + data_len;
799 di = (struct btrfs_dir_item *)((char *)di + len);
800 cur += len;
801 }
802 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
803 rec->errors |= I_ERR_DUP_DIR_INDEX;
804
805 return 0;
806 }
807
808 static int process_inode_ref(struct extent_buffer *eb,
809 int slot, struct btrfs_key *key,
810 struct shared_node *active_node)
811 {
812 u32 total;
813 u32 cur = 0;
814 u32 len;
815 u32 name_len;
816 u64 index;
817 int error;
818 struct cache_tree *inode_cache;
819 struct btrfs_inode_ref *ref;
820 char namebuf[BTRFS_NAME_LEN];
821
822 inode_cache = &active_node->inode_cache;
823
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) {
830 len = name_len;
831 error = 0;
832 } else {
833 len = BTRFS_NAME_LEN;
834 error = REF_ERR_NAME_TOO_LONG;
835 }
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);
839
840 len = sizeof(*ref) + name_len;
841 ref = (struct btrfs_inode_ref *)((char *)ref + len);
842 cur += len;
843 }
844 return 0;
845 }
846
847 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
848 {
849 struct btrfs_key key;
850 struct btrfs_path path;
851 struct extent_buffer *leaf;
852 int ret ;
853 size_t size;
854 u64 found = 0;
855 u64 csum_end;
856 u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
857
858 btrfs_init_path(&path);
859
860 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
861 key.offset = start;
862 key.type = BTRFS_EXTENT_CSUM_KEY;
863
864 ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
865 &key, &path, 0, 0);
866 BUG_ON(ret < 0);
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)
872 path.slots[0]--;
873 }
874
875 while (len > 0) {
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);
879 BUG_ON(ret < 0);
880 if (ret > 0)
881 break;
882 leaf = path.nodes[0];
883 }
884
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)
888 break;
889
890 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
891 if (key.offset >= start + len)
892 break;
893
894 if (key.offset > start)
895 start = key.offset;
896
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);
901 len -= size;
902 start += size;
903 found += size;
904 }
905
906 path.slots[0]++;
907 }
908 btrfs_release_path(root->fs_info->csum_root, &path);
909 return found;
910 }
911
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)
916 {
917 struct inode_record *rec;
918 struct btrfs_file_extent_item *fi;
919 u64 num_bytes = 0;
920 u64 disk_bytenr = 0;
921 u64 extent_offset = 0;
922 u64 mask = root->sectorsize - 1;
923 int extent_type;
924
925 rec = active_node->current;
926 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
927 rec->found_file_extent = 1;
928
929 if (rec->extent_start == (u64)-1) {
930 rec->extent_start = key->offset;
931 rec->extent_end = key->offset;
932 }
933
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;
939
940 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
941 extent_type = btrfs_file_extent_type(eb, fi);
942
943 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
944 num_bytes = btrfs_file_extent_inline_len(eb, fi);
945 if (num_bytes == 0)
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;
964 if (disk_bytenr > 0)
965 rec->found_size += num_bytes;
966 } else {
967 rec->errors |= I_ERR_BAD_FILE_EXTENT;
968 }
969 rec->extent_end = key->offset + num_bytes;
970
971 if (disk_bytenr > 0) {
972 u64 found;
973 if (btrfs_file_extent_compression(eb, fi))
974 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
975 else
976 disk_bytenr += extent_offset;
977
978 found = count_csum_range(root, disk_bytenr, num_bytes);
979 if (extent_type == BTRFS_FILE_EXTENT_REG) {
980 if (found > 0)
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) {
985 if (found > 0)
986 rec->errors |= I_ERR_ODD_CSUM_ITEM;
987 }
988 }
989 return 0;
990 }
991
992 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
993 struct walk_control *wc)
994 {
995 struct btrfs_key key;
996 u32 nritems;
997 int i;
998 int ret;
999 struct cache_tree *inode_cache;
1000 struct shared_node *active_node;
1001
1002 if (wc->root_level == wc->active_node &&
1003 btrfs_root_refs(&root->root_item) == 0)
1004 return 0;
1005
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);
1017 }
1018 active_node->current = get_inode_rec(inode_cache,
1019 key.objectid, 1);
1020 }
1021 switch (key.type) {
1022 case BTRFS_DIR_ITEM_KEY:
1023 case BTRFS_DIR_INDEX_KEY:
1024 ret = process_dir_item(eb, i, &key, active_node);
1025 break;
1026 case BTRFS_INODE_REF_KEY:
1027 ret = process_inode_ref(eb, i, &key, active_node);
1028 break;
1029 case BTRFS_INODE_ITEM_KEY:
1030 ret = process_inode_item(eb, i, &key, active_node);
1031 break;
1032 case BTRFS_EXTENT_DATA_KEY:
1033 ret = process_file_extent(root, eb, i, &key,
1034 active_node);
1035 break;
1036 default:
1037 break;
1038 };
1039 }
1040 return ret;
1041 }
1042
1043 static void reada_walk_down(struct btrfs_root *root,
1044 struct extent_buffer *node, int slot)
1045 {
1046 u64 bytenr;
1047 u64 ptr_gen;
1048 u32 nritems;
1049 u32 blocksize;
1050 int i;
1051 int ret;
1052 int level;
1053
1054 level = btrfs_header_level(node);
1055 if (level != 1)
1056 return;
1057
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);
1064 if (ret)
1065 break;
1066 }
1067 }
1068
1069 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1070 struct walk_control *wc, int *level)
1071 {
1072 u64 bytenr;
1073 u64 ptr_gen;
1074 struct extent_buffer *next;
1075 struct extent_buffer *cur;
1076 u32 blocksize;
1077 int ret;
1078 u64 refs;
1079
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);
1085 BUG_ON(ret);
1086 if (refs > 1) {
1087 ret = enter_shared_node(root, path->nodes[*level]->start,
1088 refs, wc, *level);
1089 if (ret > 0)
1090 goto out;
1091 }
1092
1093 while (*level >= 0) {
1094 WARN_ON(*level < 0);
1095 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1096 cur = path->nodes[*level];
1097
1098 if (btrfs_header_level(cur) != *level)
1099 WARN_ON(1);
1100
1101 if (path->slots[*level] >= btrfs_header_nritems(cur))
1102 break;
1103 if (*level == 0) {
1104 ret = process_one_leaf(root, cur, wc);
1105 break;
1106 }
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,
1111 &refs, NULL);
1112 BUG_ON(ret);
1113
1114 if (refs > 1) {
1115 ret = enter_shared_node(root, bytenr, refs,
1116 wc, *level - 1);
1117 if (ret > 0) {
1118 path->slots[*level]++;
1119 continue;
1120 }
1121 }
1122
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,
1128 ptr_gen);
1129 }
1130
1131 *level = *level - 1;
1132 free_extent_buffer(path->nodes[*level]);
1133 path->nodes[*level] = next;
1134 path->slots[*level] = 0;
1135 }
1136 out:
1137 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1138 return 0;
1139 }
1140
1141 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1142 struct walk_control *wc, int *level)
1143 {
1144 int i;
1145 struct extent_buffer *leaf;
1146
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)) {
1150 path->slots[i]++;
1151 *level = i;
1152 return 0;
1153 } else {
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);
1159 *level = i + 1;
1160 }
1161 }
1162 return 1;
1163 }
1164
1165 static int check_root_dir(struct inode_record *rec)
1166 {
1167 struct inode_backref *backref;
1168 int ret = -1;
1169
1170 if (!rec->found_inode_item || rec->errors)
1171 goto out;
1172 if (rec->nlink != 1 || rec->found_link != 0)
1173 goto out;
1174 if (list_empty(&rec->backrefs))
1175 goto out;
1176 backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1177 if (!backref->found_inode_ref)
1178 goto out;
1179 if (backref->index != 0 || backref->namelen != 2 ||
1180 memcmp(backref->name, "..", 2))
1181 goto out;
1182 if (backref->found_dir_index || backref->found_dir_item)
1183 goto out;
1184 ret = 0;
1185 out:
1186 return ret;
1187 }
1188
1189 static int check_inode_recs(struct btrfs_root *root,
1190 struct cache_tree *inode_cache)
1191 {
1192 struct cache_extent *cache;
1193 struct ptr_node *node;
1194 struct inode_record *rec;
1195 struct inode_backref *backref;
1196 int ret;
1197 u64 error = 0;
1198 u64 root_dirid = btrfs_root_dirid(&root->root_item);
1199
1200 if (btrfs_root_refs(&root->root_item) == 0) {
1201 if (!cache_tree_empty(inode_cache))
1202 fprintf(stderr, "warning line %d\n", __LINE__);
1203 return 0;
1204 }
1205
1206 rec = get_inode_rec(inode_cache, root_dirid, 0);
1207 if (rec) {
1208 ret = check_root_dir(rec);
1209 if (ret) {
1210 fprintf(stderr, "root %llu root dir %llu error\n",
1211 (unsigned long long)root->root_key.objectid,
1212 (unsigned long long)root_dirid);
1213 error++;
1214 }
1215 } else {
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);
1219 }
1220
1221 while (1) {
1222 cache = find_first_cache_extent(inode_cache, 0);
1223 if (!cache)
1224 break;
1225 node = container_of(cache, struct ptr_node, cache);
1226 rec = node->data;
1227 remove_cache_extent(inode_cache, &node->cache);
1228 free(node);
1229 if (rec->ino == root_dirid ||
1230 rec->ino == BTRFS_ORPHAN_OBJECTID) {
1231 free_inode_rec(rec);
1232 continue;
1233 }
1234
1235 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1236 ret = check_orphan_item(root, rec->ino);
1237 if (ret == 0)
1238 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1239 if (can_free_inode_rec(rec)) {
1240 free_inode_rec(rec);
1241 continue;
1242 }
1243 }
1244
1245 error++;
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);
1266 }
1267 free_inode_rec(rec);
1268 }
1269 return (error > 0) ? -1 : 0;
1270 }
1271
1272 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1273 u64 objectid)
1274 {
1275 struct cache_extent *cache;
1276 struct root_record *rec = NULL;
1277 int ret;
1278
1279 cache = find_cache_extent(root_cache, objectid, 1);
1280 if (cache) {
1281 rec = container_of(cache, struct root_record, cache);
1282 } else {
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;
1288
1289 ret = insert_existing_cache_extent(root_cache, &rec->cache);
1290 BUG_ON(ret);
1291 }
1292 return rec;
1293 }
1294
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)
1298 {
1299 struct root_backref *backref;
1300
1301 list_for_each_entry(backref, &rec->backrefs, list) {
1302 if (backref->ref_root != ref_root || backref->dir != dir ||
1303 backref->namelen != namelen)
1304 continue;
1305 if (memcmp(name, backref->name, namelen))
1306 continue;
1307 return backref;
1308 }
1309
1310 backref = malloc(sizeof(*backref) + namelen + 1);
1311 memset(backref, 0, sizeof(*backref));
1312 backref->ref_root = ref_root;
1313 backref->dir = dir;
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);
1319 return backref;
1320 }
1321
1322 static void free_root_recs(struct cache_tree *root_cache)
1323 {
1324 struct cache_extent *cache;
1325 struct root_record *rec;
1326 struct root_backref *backref;
1327
1328 while (1) {
1329 cache = find_first_cache_extent(root_cache, 0);
1330 if (!cache)
1331 break;
1332 rec = container_of(cache, struct root_record, cache);
1333 remove_cache_extent(root_cache, &rec->cache);
1334
1335 while (!list_empty(&rec->backrefs)) {
1336 backref = list_entry(rec->backrefs.next,
1337 struct root_backref, list);
1338 list_del(&backref->list);
1339 free(backref);
1340 }
1341 kfree(rec);
1342 }
1343 }
1344
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)
1349 {
1350 struct root_record *rec;
1351 struct root_backref *backref;
1352
1353 rec = get_root_rec(root_cache, root_id);
1354 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
1355
1356 backref->errors |= errors;
1357
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;
1363 } else {
1364 backref->index = index;
1365 }
1366 }
1367
1368 if (item_type == BTRFS_DIR_ITEM_KEY) {
1369 backref->found_dir_item = 1;
1370 backref->reachable = 1;
1371 rec->found_ref++;
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;
1382 } else {
1383 BUG_ON(1);
1384 }
1385
1386 return 0;
1387 }
1388
1389 static int merge_root_recs(struct btrfs_root *root,
1390 struct cache_tree *src_cache,
1391 struct cache_tree *dst_cache)
1392 {
1393 struct cache_extent *cache;
1394 struct ptr_node *node;
1395 struct inode_record *rec;
1396 struct inode_backref *backref;
1397
1398 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1399 free_inode_recs(src_cache);
1400 return 0;
1401 }
1402
1403 while (1) {
1404 cache = find_first_cache_extent(src_cache, 0);
1405 if (!cache)
1406 break;
1407 node = container_of(cache, struct ptr_node, cache);
1408 rec = node->data;
1409 remove_cache_extent(src_cache, &node->cache);
1410 free(node);
1411
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,
1419 backref->errors);
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,
1425 backref->errors);
1426 }
1427 free_inode_rec(rec);
1428 }
1429 return 0;
1430 }
1431
1432 static int check_root_refs(struct btrfs_root *root,
1433 struct cache_tree *root_cache)
1434 {
1435 struct root_record *rec;
1436 struct root_record *ref_root;
1437 struct root_backref *backref;
1438 struct cache_extent *cache;
1439 int loop = 1;
1440 int ret;
1441 int error;
1442 int errors = 0;
1443
1444 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
1445 rec->found_ref = 1;
1446
1447 /* fixme: this can not detect circular references */
1448 while (loop) {
1449 loop = 0;
1450 cache = find_first_cache_extent(root_cache, 0);
1451 while (1) {
1452 if (!cache)
1453 break;
1454 rec = container_of(cache, struct root_record, cache);
1455 cache = next_cache_extent(cache);
1456
1457 if (rec->found_ref == 0)
1458 continue;
1459
1460 list_for_each_entry(backref, &rec->backrefs, list) {
1461 if (!backref->reachable)
1462 continue;
1463
1464 ref_root = get_root_rec(root_cache,
1465 backref->ref_root);
1466 if (ref_root->found_ref > 0)
1467 continue;
1468
1469 backref->reachable = 0;
1470 rec->found_ref--;
1471 if (rec->found_ref == 0)
1472 loop = 1;
1473 }
1474 }
1475 }
1476
1477 cache = find_first_cache_extent(root_cache, 0);
1478 while (1) {
1479 if (!cache)
1480 break;
1481 rec = container_of(cache, struct root_record, cache);
1482 cache = next_cache_extent(cache);
1483
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,
1488 rec->objectid);
1489 if (ret == 0)
1490 continue;
1491 errors++;
1492 fprintf(stderr, "fs tree %llu not referenced\n",
1493 (unsigned long long)rec->objectid);
1494 }
1495
1496 error = 0;
1497 if (rec->found_ref > 0 && !rec->found_root_item)
1498 error = 1;
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)
1509 error = 1;
1510 }
1511 if (!error)
1512 continue;
1513
1514 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");
1518
1519 list_for_each_entry(backref, &rec->backrefs, list) {
1520 if (!backref->reachable)
1521 continue;
1522 if (!backref->errors && rec->found_root_item)
1523 continue;
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,
1530 backref->errors);
1531 }
1532 }
1533 return errors > 0 ? 1 : 0;
1534 }
1535
1536 static int process_root_ref(struct extent_buffer *eb, int slot,
1537 struct btrfs_key *key,
1538 struct cache_tree *root_cache)
1539 {
1540 u64 dirid;
1541 u64 index;
1542 u32 len;
1543 u32 name_len;
1544 struct btrfs_root_ref *ref;
1545 char namebuf[BTRFS_NAME_LEN];
1546 int error;
1547
1548 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
1549
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);
1553
1554 if (name_len <= BTRFS_NAME_LEN) {
1555 len = name_len;
1556 error = 0;
1557 } else {
1558 len = BTRFS_NAME_LEN;
1559 error = REF_ERR_NAME_TOO_LONG;
1560 }
1561 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1562
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);
1566 } else {
1567 add_root_backref(root_cache, key->objectid, key->offset, dirid,
1568 index, namebuf, len, key->type, error);
1569 }
1570 return 0;
1571 }
1572
1573 static int check_fs_root(struct btrfs_root *root,
1574 struct cache_tree *root_cache,
1575 struct walk_control *wc)
1576 {
1577 int ret = 0;
1578 int wret;
1579 int level;
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;
1584
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;
1589 }
1590
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);
1595
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;
1601
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;
1607 } else {
1608 struct btrfs_key key;
1609 struct btrfs_disk_key found_key;
1610
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);
1615 BUG_ON(wret < 0);
1616 btrfs_node_key(path.nodes[level], &found_key,
1617 path.slots[level]);
1618 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1619 sizeof(found_key)));
1620 }
1621
1622 while (1) {
1623 wret = walk_down_tree(root, &path, wc, &level);
1624 if (wret < 0)
1625 ret = wret;
1626 if (wret != 0)
1627 break;
1628
1629 wret = walk_up_tree(root, &path, wc, &level);
1630 if (wret < 0)
1631 ret = wret;
1632 if (wret != 0)
1633 break;
1634 }
1635 btrfs_release_path(root, &path);
1636
1637 merge_root_recs(root, &root_node.root_cache, root_cache);
1638
1639 if (root_node.current) {
1640 root_node.current->checked = 1;
1641 maybe_free_inode_rec(&root_node.inode_cache,
1642 root_node.current);
1643 }
1644
1645 ret = check_inode_recs(root, &root_node.inode_cache);
1646 return ret;
1647 }
1648
1649 static int fs_root_objectid(u64 objectid)
1650 {
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))
1656 return 1;
1657 return 0;
1658 }
1659
1660 static int check_fs_roots(struct btrfs_root *root,
1661 struct cache_tree *root_cache)
1662 {
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;
1669 int ret;
1670 int err = 0;
1671
1672 memset(&wc, 0, sizeof(wc));
1673 cache_tree_init(&wc.shared);
1674 btrfs_init_path(&path);
1675
1676 key.offset = 0;
1677 key.objectid = 0;
1678 key.type = BTRFS_ROOT_ITEM_KEY;
1679 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1680 BUG_ON(ret < 0);
1681 while (1) {
1682 leaf = path.nodes[0];
1683 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1684 ret = btrfs_next_leaf(tree_root, &path);
1685 if (ret != 0)
1686 break;
1687 leaf = path.nodes[0];
1688 }
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,
1693 &key);
1694 ret = check_fs_root(tmp_root, root_cache, &wc);
1695 if (ret)
1696 err = 1;
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,
1701 root_cache);
1702 }
1703 path.slots[0]++;
1704 }
1705 btrfs_release_path(tree_root, &path);
1706
1707 if (!cache_tree_empty(&wc.shared))
1708 fprintf(stderr, "warning line %d\n", __LINE__);
1709
1710 return err;
1711 }
1712
1713 static int check_node(struct btrfs_root *root,
1714 struct btrfs_disk_key *parent_key,
1715 struct extent_buffer *buf)
1716 {
1717 int i;
1718 struct btrfs_key cpukey;
1719 struct btrfs_disk_key key;
1720 u32 nritems = btrfs_header_nritems(buf);
1721
1722 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1723 return 1;
1724 if (parent_key->type) {
1725 btrfs_node_key(buf, &key, 0);
1726 if (memcmp(parent_key, &key, sizeof(key)))
1727 return 1;
1728 }
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)
1733 return 1;
1734 }
1735 return 0;
1736 }
1737
1738 static int check_leaf(struct btrfs_root *root,
1739 struct btrfs_disk_key *parent_key,
1740 struct extent_buffer *buf)
1741 {
1742 int i;
1743 struct btrfs_key cpukey;
1744 struct btrfs_disk_key key;
1745 u32 nritems = btrfs_header_nritems(buf);
1746
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));
1750 return 1;
1751 }
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));
1756 return 1;
1757 }
1758
1759 if (nritems == 0)
1760 return 0;
1761
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));
1766 return 1;
1767 }
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);
1773 return 1;
1774 }
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));
1780 return 1;
1781 }
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));
1787 return 1;
1788 }
1789 }
1790 return 0;
1791 }
1792
1793 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1794 {
1795 struct list_head *cur = rec->backrefs.next;
1796 struct extent_backref *back;
1797 struct tree_backref *tback;
1798 struct data_backref *dback;
1799 u64 found = 0;
1800 int err = 0;
1801
1802 while(cur != &rec->backrefs) {
1803 back = list_entry(cur, struct extent_backref, list);
1804 cur = cur->next;
1805 if (!back->found_extent_tree) {
1806 err = 1;
1807 if (!print_errs)
1808 goto out;
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 ?
1816 "parent" : "root",
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);
1823 } else {
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);
1830 }
1831 }
1832 if (!back->is_data && !back->found_ref) {
1833 err = 1;
1834 if (!print_errs)
1835 goto out;
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);
1843 }
1844 if (back->is_data) {
1845 dback = (struct data_backref *)back;
1846 if (dback->found_ref != dback->num_refs) {
1847 err = 1;
1848 if (!print_errs)
1849 goto out;
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 ?
1855 "parent" : "root",
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);
1862 }
1863 }
1864 if (!back->is_data) {
1865 found += 1;
1866 } else {
1867 dback = (struct data_backref *)back;
1868 found += dback->found_ref;
1869 }
1870 }
1871 if (found != rec->refs) {
1872 err = 1;
1873 if (!print_errs)
1874 goto out;
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);
1880 }
1881 out:
1882 return err;
1883 }
1884
1885 static int free_all_extent_backrefs(struct extent_record *rec)
1886 {
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);
1892 list_del(cur);
1893 free(back);
1894 }
1895 return 0;
1896 }
1897
1898 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1899 struct extent_record *rec)
1900 {
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);
1906 free(rec);
1907 }
1908 return 0;
1909 }
1910
1911 static int check_owner_ref(struct btrfs_root *root,
1912 struct extent_record *rec,
1913 struct extent_buffer *buf)
1914 {
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;
1920 int level;
1921 int found = 0;
1922
1923 list_for_each_entry(node, &rec->backrefs, list) {
1924 if (node->is_data)
1925 continue;
1926 if (!node->found_ref)
1927 continue;
1928 if (node->full_backref)
1929 continue;
1930 back = (struct tree_backref *)node;
1931 if (btrfs_header_owner(buf) == back->root)
1932 return 0;
1933 }
1934 BUG_ON(rec->is_root);
1935
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;
1940
1941 ref_root = btrfs_read_fs_root(root->fs_info, &key);
1942 BUG_ON(IS_ERR(ref_root));
1943
1944 level = btrfs_header_level(buf);
1945 if (level == 0)
1946 btrfs_item_key_to_cpu(buf, &key, 0);
1947 else
1948 btrfs_node_key_to_cpu(buf, &key, 0);
1949
1950 btrfs_init_path(&path);
1951 path.lowest_level = level + 1;
1952 btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
1953
1954 if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
1955 path.slots[level + 1]))
1956 rec->owner_ref_checked = 1;
1957
1958 btrfs_release_path(ref_root, &path);
1959 return found ? 0 : 1;
1960 }
1961
1962 static int check_block(struct btrfs_root *root,
1963 struct cache_tree *extent_cache,
1964 struct extent_buffer *buf, u64 flags)
1965 {
1966 struct extent_record *rec;
1967 struct cache_extent *cache;
1968 int ret = 1;
1969
1970 cache = find_cache_extent(extent_cache, buf->start, buf->len);
1971 if (!cache)
1972 return 1;
1973 rec = container_of(cache, struct extent_record, cache);
1974 if (btrfs_is_leaf(buf)) {
1975 ret = check_leaf(root, &rec->parent_key, buf);
1976 } else {
1977 ret = check_node(root, &rec->parent_key, buf);
1978 }
1979 if (ret) {
1980 fprintf(stderr, "bad block %llu\n",
1981 (unsigned long long)buf->start);
1982 } else {
1983 rec->content_checked = 1;
1984 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
1985 rec->owner_ref_checked = 1;
1986 else {
1987 ret = check_owner_ref(root, rec, buf);
1988 if (!ret)
1989 rec->owner_ref_checked = 1;
1990 }
1991 }
1992 if (!ret)
1993 maybe_free_extent_rec(extent_cache, rec);
1994 return ret;
1995 }
1996
1997 static struct tree_backref *find_tree_backref(struct extent_record *rec,
1998 u64 parent, u64 root)
1999 {
2000 struct list_head *cur = rec->backrefs.next;
2001 struct extent_backref *node;
2002 struct tree_backref *back;
2003
2004 while(cur != &rec->backrefs) {
2005 node = list_entry(cur, struct extent_backref, list);
2006 cur = cur->next;
2007 if (node->is_data)
2008 continue;
2009 back = (struct tree_backref *)node;
2010 if (parent > 0) {
2011 if (!node->full_backref)
2012 continue;
2013 if (parent == back->parent)
2014 return back;
2015 } else {
2016 if (node->full_backref)
2017 continue;
2018 if (back->root == root)
2019 return back;
2020 }
2021 }
2022 return NULL;
2023 }
2024
2025 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2026 u64 parent, u64 root)
2027 {
2028 struct tree_backref *ref = malloc(sizeof(*ref));
2029 memset(&ref->node, 0, sizeof(ref->node));
2030 if (parent > 0) {
2031 ref->parent = parent;
2032 ref->node.full_backref = 1;
2033 } else {
2034 ref->root = root;
2035 ref->node.full_backref = 0;
2036 }
2037 list_add_tail(&ref->node.list, &rec->backrefs);
2038 return ref;
2039 }
2040
2041 static struct data_backref *find_data_backref(struct extent_record *rec,
2042 u64 parent, u64 root,
2043 u64 owner, u64 offset)
2044 {
2045 struct list_head *cur = rec->backrefs.next;
2046 struct extent_backref *node;
2047 struct data_backref *back;
2048
2049 while(cur != &rec->backrefs) {
2050 node = list_entry(cur, struct extent_backref, list);
2051 cur = cur->next;
2052 if (!node->is_data)
2053 continue;
2054 back = (struct data_backref *)node;
2055 if (parent > 0) {
2056 if (!node->full_backref)
2057 continue;
2058 if (parent == back->parent)
2059 return back;
2060 } else {
2061 if (node->full_backref)
2062 continue;
2063 if (back->root == root && back->owner == owner &&
2064 back->offset == offset)
2065 return back;
2066 }
2067 }
2068 return NULL;
2069 }
2070
2071 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2072 u64 parent, u64 root,
2073 u64 owner, u64 offset)
2074 {
2075 struct data_backref *ref = malloc(sizeof(*ref));
2076 memset(&ref->node, 0, sizeof(ref->node));
2077 ref->node.is_data = 1;
2078 if (parent > 0) {
2079 ref->parent = parent;
2080 ref->owner = 0;
2081 ref->offset = 0;
2082 ref->node.full_backref = 1;
2083 } else {
2084 ref->root = root;
2085 ref->owner = owner;
2086 ref->offset = offset;
2087 ref->node.full_backref = 0;
2088 }
2089 ref->found_ref = 0;
2090 ref->num_refs = 0;
2091 list_add_tail(&ref->node.list, &rec->backrefs);
2092 return ref;
2093 }
2094
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)
2099 {
2100 struct extent_record *rec;
2101 struct cache_extent *cache;
2102 int ret = 0;
2103
2104 cache = find_cache_extent(extent_cache, start, nr);
2105 if (cache) {
2106 rec = container_of(cache, struct extent_record, cache);
2107 if (inc_ref)
2108 rec->refs++;
2109 if (rec->nr == 1)
2110 rec->nr = nr;
2111
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);
2116 ret = 1;
2117 }
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);
2126 }
2127 rec->extent_item_refs = extent_item_refs;
2128 }
2129 if (is_root)
2130 rec->is_root = 1;
2131 if (set_checked) {
2132 rec->content_checked = 1;
2133 rec->owner_ref_checked = 1;
2134 }
2135
2136 if (parent_key)
2137 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2138
2139 maybe_free_extent_rec(extent_cache, rec);
2140 return ret;
2141 }
2142 rec = malloc(sizeof(*rec));
2143 rec->start = start;
2144 rec->nr = nr;
2145 rec->content_checked = 0;
2146 rec->owner_ref_checked = 0;
2147 INIT_LIST_HEAD(&rec->backrefs);
2148
2149 if (is_root)
2150 rec->is_root = 1;
2151 else
2152 rec->is_root = 0;
2153
2154 if (inc_ref)
2155 rec->refs = 1;
2156 else
2157 rec->refs = 0;
2158
2159 if (extent_item_refs)
2160 rec->extent_item_refs = extent_item_refs;
2161 else
2162 rec->extent_item_refs = 0;
2163
2164 if (parent_key)
2165 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2166 else
2167 memset(&rec->parent_key, 0, sizeof(*parent_key));
2168
2169 rec->cache.start = start;
2170 rec->cache.size = nr;
2171 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
2172 BUG_ON(ret);
2173 bytes_used += nr;
2174 if (set_checked) {
2175 rec->content_checked = 1;
2176 rec->owner_ref_checked = 1;
2177 }
2178 return ret;
2179 }
2180
2181 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
2182 u64 parent, u64 root, int found_ref)
2183 {
2184 struct extent_record *rec;
2185 struct tree_backref *back;
2186 struct cache_extent *cache;
2187
2188 cache = find_cache_extent(extent_cache, bytenr, 1);
2189 if (!cache) {
2190 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2191 cache = find_cache_extent(extent_cache, bytenr, 1);
2192 if (!cache)
2193 abort();
2194 }
2195
2196 rec = container_of(cache, struct extent_record, cache);
2197 if (rec->start != bytenr) {
2198 abort();
2199 }
2200
2201 back = find_tree_backref(rec, parent, root);
2202 if (!back)
2203 back = alloc_tree_backref(rec, parent, root);
2204
2205 if (found_ref) {
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);
2212 }
2213 back->node.found_ref = 1;
2214 } else {
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);
2221 }
2222 back->node.found_extent_tree = 1;
2223 }
2224 return 0;
2225 }
2226
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)
2230 {
2231 struct extent_record *rec;
2232 struct data_backref *back;
2233 struct cache_extent *cache;
2234
2235 cache = find_cache_extent(extent_cache, bytenr, 1);
2236 if (!cache) {
2237 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2238 cache = find_cache_extent(extent_cache, bytenr, 1);
2239 if (!cache)
2240 abort();
2241 }
2242
2243 rec = container_of(cache, struct extent_record, cache);
2244 if (rec->start != bytenr) {
2245 abort();
2246 }
2247 back = find_data_backref(rec, parent, root, owner, offset);
2248 if (!back)
2249 back = alloc_data_backref(rec, parent, root, owner, offset);
2250
2251 if (found_ref) {
2252 BUG_ON(num_refs != 1);
2253 back->node.found_ref = 1;
2254 back->found_ref += 1;
2255 } else {
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);
2266 }
2267 back->num_refs = num_refs;
2268 back->node.found_extent_tree = 1;
2269 }
2270 return 0;
2271 }
2272
2273 static int add_pending(struct cache_tree *pending,
2274 struct cache_tree *seen, u64 bytenr, u32 size)
2275 {
2276 int ret;
2277 ret = insert_cache_extent(seen, bytenr, size);
2278 if (ret)
2279 return ret;
2280 insert_cache_extent(pending, bytenr, size);
2281 return 0;
2282 }
2283
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,
2288 int *reada_bits)
2289 {
2290 unsigned long node_start = last;
2291 struct cache_extent *cache;
2292 int ret;
2293
2294 cache = find_first_cache_extent(reada, 0);
2295 if (cache) {
2296 bits[0].start = cache->start;
2297 bits[1].size = cache->size;
2298 *reada_bits = 1;
2299 return 1;
2300 }
2301 *reada_bits = 0;
2302 if (node_start > 32768)
2303 node_start -= 32768;
2304
2305 cache = find_first_cache_extent(nodes, node_start);
2306 if (!cache)
2307 cache = find_first_cache_extent(nodes, 0);
2308
2309 if (!cache) {
2310 cache = find_first_cache_extent(pending, 0);
2311 if (!cache)
2312 return 0;
2313 ret = 0;
2314 do {
2315 bits[ret].start = cache->start;
2316 bits[ret].size = cache->size;
2317 cache = next_cache_extent(cache);
2318 ret++;
2319 } while (cache && ret < bits_nr);
2320 return ret;
2321 }
2322
2323 ret = 0;
2324 do {
2325 bits[ret].start = cache->start;
2326 bits[ret].size = cache->size;
2327 cache = next_cache_extent(cache);
2328 ret++;
2329 } while (cache && ret < bits_nr);
2330
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);
2335 while(next) {
2336 if (next->start - lookup > 32768)
2337 break;
2338 bits[ret].start = next->start;
2339 bits[ret].size = next->size;
2340 lookup = next->start + next->size;
2341 ret++;
2342 if (ret == bits_nr)
2343 break;
2344 next = next_cache_extent(next);
2345 if (!next)
2346 break;
2347 }
2348 }
2349 return ret;
2350 }
2351
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)
2355 {
2356 struct btrfs_extent_ref_v0 *ref0;
2357 struct btrfs_key key;
2358
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,
2363 0, 0);
2364 } else {
2365 add_data_backref(extent_cache, key.objectid, key.offset, 0,
2366 0, 0, btrfs_ref_count_v0(leaf, ref0), 0);
2367 }
2368 return 0;
2369 }
2370 #endif
2371
2372 static int process_extent_item(struct cache_tree *extent_cache,
2373 struct extent_buffer *eb, int slot)
2374 {
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;
2380 unsigned long end;
2381 unsigned long ptr;
2382 int type;
2383 u32 item_size = btrfs_item_size_nr(eb, slot);
2384 u64 refs = 0;
2385 u64 offset;
2386
2387 btrfs_item_key_to_cpu(eb, &key, slot);
2388
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);
2395 #else
2396 BUG();
2397 #endif
2398 return add_extent_rec(extent_cache, NULL, key.objectid,
2399 key.offset, refs, 0, 0, 0);
2400 }
2401
2402 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
2403 refs = btrfs_extent_refs(eb, ei);
2404
2405 add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
2406 refs, 0, 0, 0);
2407
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);
2411
2412 end = (unsigned long)ei + item_size;
2413 while (ptr < end) {
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);
2417 switch (type) {
2418 case BTRFS_TREE_BLOCK_REF_KEY:
2419 add_tree_backref(extent_cache, key.objectid,
2420 0, offset, 0);
2421 break;
2422 case BTRFS_SHARED_BLOCK_REF_KEY:
2423 add_tree_backref(extent_cache, key.objectid,
2424 offset, 0, 0);
2425 break;
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,
2431 dref),
2432 btrfs_extent_data_ref_offset(eb, dref),
2433 btrfs_extent_data_ref_count(eb, dref),
2434 0);
2435 break;
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,
2439 0, 0, 0,
2440 btrfs_shared_data_ref_count(eb, sref),
2441 0);
2442 break;
2443 default:
2444 BUG();
2445 }
2446 ptr += btrfs_extent_inline_ref_size(type);
2447 }
2448 WARN_ON(ptr > end);
2449 return 0;
2450 }
2451
2452 static int run_next_block(struct btrfs_root *root,
2453 struct block_info *bits,
2454 int bits_nr,
2455 u64 *last,
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)
2461 {
2462 struct extent_buffer *buf;
2463 u64 bytenr;
2464 u32 size;
2465 u64 parent;
2466 u64 owner;
2467 u64 flags;
2468 int ret;
2469 int i;
2470 int nritems;
2471 struct btrfs_key key;
2472 struct cache_extent *cache;
2473 int reada_bits;
2474
2475 ret = pick_next_pending(pending, reada, nodes, *last, bits,
2476 bits_nr, &reada_bits);
2477 if (ret == 0) {
2478 return 1;
2479 }
2480 if (!reada_bits) {
2481 for(i = 0; i < ret; i++) {
2482 insert_cache_extent(reada, bits[i].start,
2483 bits[i].size);
2484
2485 /* fixme, get the parent transid */
2486 readahead_tree_block(root, bits[i].start,
2487 bits[i].size, 0);
2488 }
2489 }
2490 *last = bits[0].start;
2491 bytenr = bits[0].start;
2492 size = bits[0].size;
2493
2494 cache = find_cache_extent(pending, bytenr, size);
2495 if (cache) {
2496 remove_cache_extent(pending, cache);
2497 free(cache);
2498 }
2499 cache = find_cache_extent(reada, bytenr, size);
2500 if (cache) {
2501 remove_cache_extent(reada, cache);
2502 free(cache);
2503 }
2504 cache = find_cache_extent(nodes, bytenr, size);
2505 if (cache) {
2506 remove_cache_extent(nodes, cache);
2507 free(cache);
2508 }
2509
2510 /* fixme, get the real parent transid */
2511 buf = read_tree_block(root, bytenr, size, 0);
2512 nritems = btrfs_header_nritems(buf);
2513
2514 ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
2515
2516 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
2517 parent = bytenr;
2518 owner = 0;
2519 } else {
2520 parent = 0;
2521 owner = btrfs_header_owner(buf);
2522 }
2523
2524 ret = check_block(root, extent_cache, buf, flags);
2525
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);
2533 continue;
2534 }
2535 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
2536 total_csum_bytes +=
2537 btrfs_item_size_nr(buf, i);
2538 continue;
2539 }
2540 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
2541 continue;
2542 }
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);
2546 #else
2547 BUG();
2548 #endif
2549 continue;
2550 }
2551
2552 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2553 add_tree_backref(extent_cache, key.objectid, 0,
2554 key.offset, 0);
2555 continue;
2556 }
2557 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2558 add_tree_backref(extent_cache, key.objectid,
2559 key.offset, 0, 0);
2560 continue;
2561 }
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,
2567 key.objectid, 0,
2568 btrfs_extent_data_ref_root(buf, ref),
2569 btrfs_extent_data_ref_objectid(buf,
2570 ref),
2571 btrfs_extent_data_ref_offset(buf, ref),
2572 btrfs_extent_data_ref_count(buf, ref),
2573 0);
2574 continue;
2575 }
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),
2583 0);
2584 continue;
2585 }
2586 if (key.type != BTRFS_EXTENT_DATA_KEY)
2587 continue;
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)
2592 continue;
2593 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2594 continue;
2595
2596 data_bytes_allocated +=
2597 btrfs_file_extent_disk_num_bytes(buf, fi);
2598 if (data_bytes_allocated < root->sectorsize) {
2599 abort();
2600 }
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),
2606 0, 0, 1, 1);
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);
2611 BUG_ON(ret);
2612 }
2613 } else {
2614 int level;
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);
2622 BUG_ON(ret);
2623
2624 add_tree_backref(extent_cache, ptr, parent,
2625 owner, 1);
2626
2627 if (level > 1) {
2628 add_pending(nodes, seen, ptr, size);
2629 } else {
2630 add_pending(pending, seen, ptr, size);
2631 }
2632 }
2633 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2634 nritems) * sizeof(struct btrfs_key_ptr);
2635 }
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);
2645 return 0;
2646 }
2647
2648 static int add_root_to_pending(struct extent_buffer *buf,
2649 struct block_info *bits,
2650 int bits_nr,
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)
2657 {
2658 if (btrfs_header_level(buf) > 0)
2659 add_pending(nodes, seen, buf->start, buf->len);
2660 else
2661 add_pending(pending, seen, buf->start, buf->len);
2662 add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2663 0, 1, 1, 0);
2664
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);
2668 else
2669 add_tree_backref(extent_cache, buf->start, 0,
2670 root_key->objectid, 1);
2671 return 0;
2672 }
2673
2674 static int check_extent_refs(struct btrfs_root *root,
2675 struct cache_tree *extent_cache)
2676 {
2677 struct extent_record *rec;
2678 struct cache_extent *cache;
2679 int err = 0;
2680
2681 while(1) {
2682 cache = find_first_cache_extent(extent_cache, 0);
2683 if (!cache)
2684 break;
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);
2693 err = 1;
2694 }
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);
2699
2700 err = 1;
2701 }
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);
2706 err = 1;
2707 }
2708
2709 remove_cache_extent(extent_cache, cache);
2710 free_all_extent_backrefs(rec);
2711 free(rec);
2712 }
2713 return err;
2714 }
2715
2716 static int check_extents(struct btrfs_root *root)
2717 {
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;
2726 int ret;
2727 u64 last = 0;
2728 struct block_info *bits;
2729 int bits_nr;
2730 struct extent_buffer *leaf;
2731 int slot;
2732 struct btrfs_root_item ri;
2733
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);
2739
2740 bits_nr = 1024;
2741 bits = malloc(bits_nr * sizeof(struct block_info));
2742 if (!bits) {
2743 perror("malloc");
2744 exit(1);
2745 }
2746
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);
2750
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);
2754
2755 btrfs_init_path(&path);
2756 key.offset = 0;
2757 key.objectid = 0;
2758 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2759 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2760 &key, &path, 0, 0);
2761 BUG_ON(ret < 0);
2762 while(1) {
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);
2767 if (ret != 0)
2768 break;
2769 leaf = path.nodes[0];
2770 slot = path.slots[0];
2771 }
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;
2776
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,
2785 &found_key);
2786 free_extent_buffer(buf);
2787 }
2788 path.slots[0]++;
2789 }
2790 btrfs_release_path(root, &path);
2791 while(1) {
2792 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2793 &seen, &reada, &nodes, &extent_cache);
2794 if (ret != 0)
2795 break;
2796 }
2797 ret = check_extent_refs(root, &extent_cache);
2798 return ret;
2799 }
2800
2801 static void print_usage(void)
2802 {
2803 fprintf(stderr, "usage: btrfsck dev\n");
2804 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2805 exit(1);
2806 }
2807
2808 int main(int ac, char **av)
2809 {
2810 struct cache_tree root_cache;
2811 struct btrfs_root *root;
2812 u64 bytenr = 0;
2813 int ret;
2814 int num;
2815
2816 while(1) {
2817 int c;
2818 c = getopt(ac, av, "s:");
2819 if (c < 0)
2820 break;
2821 switch(c) {
2822 case 's':
2823 num = atol(optarg);
2824 bytenr = btrfs_sb_offset(num);
2825 printf("using SB copy %d, bytenr %llu\n", num,
2826 (unsigned long long)bytenr);
2827 break;
2828 default:
2829 print_usage();
2830 }
2831 }
2832 ac = ac - optind;
2833
2834 if (ac != 1)
2835 print_usage();
2836
2837 radix_tree_init();
2838 cache_tree_init(&root_cache);
2839
2840 if((ret = check_mounted(av[optind])) < 0) {
2841 fprintf(stderr, "Could not check mount status: %s\n", strerror(ret));
2842 return ret;
2843 } else if(ret) {
2844 fprintf(stderr, "%s is currently mounted. Aborting.\n", av[optind]);
2845 return -EBUSY;
2846 }
2847
2848 root = open_ctree(av[optind], bytenr, 0);
2849
2850 if (root == NULL)
2851 return 1;
2852
2853 ret = check_extents(root);
2854 if (ret)
2855 goto out;
2856 ret = check_fs_roots(root, &root_cache);
2857 if (ret)
2858 goto out;
2859
2860 ret = check_root_refs(root, &root_cache);
2861 out:
2862 free_root_recs(&root_cache);
2863 close_ctree(root);
2864
2865 if (found_old_backref) {
2866 /*
2867 * there was a disk format change when mixed
2868 * backref was in testing tree. The old format
2869 * existed about one week.
2870 */
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");
2875 ret = 1;
2876 }
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);
2890 return ret;
2891 }
(deprecated) Btrfs progs developments and patch integration