?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
btrfs-debug-tree: add -d option to print only the device mapping
[btrfs-progs-unstable.git] / btrfsck.c
blob63e44d1dbc26f2ee9f6ef29c08ae0eb9d19e48db
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 0;
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 ret;
1921 int level;
1922 int found = 0;
1923
1924 list_for_each_entry(node, &rec->backrefs, list) {
1925 if (node->is_data)
1926 continue;
1927 if (!node->found_ref)
1928 continue;
1929 if (node->full_backref)
1930 continue;
1931 back = (struct tree_backref *)node;
1932 if (btrfs_header_owner(buf) == back->root)
1933 return 0;
1934 }
1935 BUG_ON(rec->is_root);
1936
1937 /* try to find the block by search corresponding fs tree */
1938 key.objectid = btrfs_header_owner(buf);
1939 key.type = BTRFS_ROOT_ITEM_KEY;
1940 key.offset = (u64)-1;
1941
1942 ref_root = btrfs_read_fs_root(root->fs_info, &key);
1943 BUG_ON(IS_ERR(ref_root));
1944
1945 level = btrfs_header_level(buf);
1946 if (level == 0)
1947 btrfs_item_key_to_cpu(buf, &key, 0);
1948 else
1949 btrfs_node_key_to_cpu(buf, &key, 0);
1950
1951 btrfs_init_path(&path);
1952 path.lowest_level = level + 1;
1953 ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
1954
1955 if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
1956 path.slots[level + 1]))
1957 rec->owner_ref_checked = 1;
1958
1959 btrfs_release_path(ref_root, &path);
1960 return found ? 0 : 1;
1961 }
1962
1963 static int check_block(struct btrfs_root *root,
1964 struct cache_tree *extent_cache,
1965 struct extent_buffer *buf, u64 flags)
1966 {
1967 struct extent_record *rec;
1968 struct cache_extent *cache;
1969 int ret = 1;
1970
1971 cache = find_cache_extent(extent_cache, buf->start, buf->len);
1972 if (!cache)
1973 return 1;
1974 rec = container_of(cache, struct extent_record, cache);
1975 if (btrfs_is_leaf(buf)) {
1976 ret = check_leaf(root, &rec->parent_key, buf);
1977 } else {
1978 ret = check_node(root, &rec->parent_key, buf);
1979 }
1980 if (ret) {
1981 fprintf(stderr, "bad block %llu\n",
1982 (unsigned long long)buf->start);
1983 } else {
1984 rec->content_checked = 1;
1985 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
1986 rec->owner_ref_checked = 1;
1987 else {
1988 ret = check_owner_ref(root, rec, buf);
1989 if (!ret)
1990 rec->owner_ref_checked = 1;
1991 }
1992 }
1993 if (!ret)
1994 maybe_free_extent_rec(extent_cache, rec);
1995 return ret;
1996 }
1997
1998 static struct tree_backref *find_tree_backref(struct extent_record *rec,
1999 u64 parent, u64 root)
2000 {
2001 struct list_head *cur = rec->backrefs.next;
2002 struct extent_backref *node;
2003 struct tree_backref *back;
2004
2005 while(cur != &rec->backrefs) {
2006 node = list_entry(cur, struct extent_backref, list);
2007 cur = cur->next;
2008 if (node->is_data)
2009 continue;
2010 back = (struct tree_backref *)node;
2011 if (parent > 0) {
2012 if (!node->full_backref)
2013 continue;
2014 if (parent == back->parent)
2015 return back;
2016 } else {
2017 if (node->full_backref)
2018 continue;
2019 if (back->root == root)
2020 return back;
2021 }
2022 }
2023 return NULL;
2024 }
2025
2026 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2027 u64 parent, u64 root)
2028 {
2029 struct tree_backref *ref = malloc(sizeof(*ref));
2030 memset(&ref->node, 0, sizeof(ref->node));
2031 if (parent > 0) {
2032 ref->parent = parent;
2033 ref->node.full_backref = 1;
2034 } else {
2035 ref->root = root;
2036 ref->node.full_backref = 0;
2037 }
2038 list_add_tail(&ref->node.list, &rec->backrefs);
2039 return ref;
2040 }
2041
2042 static struct data_backref *find_data_backref(struct extent_record *rec,
2043 u64 parent, u64 root,
2044 u64 owner, u64 offset)
2045 {
2046 struct list_head *cur = rec->backrefs.next;
2047 struct extent_backref *node;
2048 struct data_backref *back;
2049
2050 while(cur != &rec->backrefs) {
2051 node = list_entry(cur, struct extent_backref, list);
2052 cur = cur->next;
2053 if (!node->is_data)
2054 continue;
2055 back = (struct data_backref *)node;
2056 if (parent > 0) {
2057 if (!node->full_backref)
2058 continue;
2059 if (parent == back->parent)
2060 return back;
2061 } else {
2062 if (node->full_backref)
2063 continue;
2064 if (back->root == root && back->owner == owner &&
2065 back->offset == offset)
2066 return back;
2067 }
2068 }
2069 return NULL;
2070 }
2071
2072 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2073 u64 parent, u64 root,
2074 u64 owner, u64 offset)
2075 {
2076 struct data_backref *ref = malloc(sizeof(*ref));
2077 memset(&ref->node, 0, sizeof(ref->node));
2078 ref->node.is_data = 1;
2079 if (parent > 0) {
2080 ref->parent = parent;
2081 ref->owner = 0;
2082 ref->offset = 0;
2083 ref->node.full_backref = 1;
2084 } else {
2085 ref->root = root;
2086 ref->owner = owner;
2087 ref->offset = offset;
2088 ref->node.full_backref = 0;
2089 }
2090 ref->found_ref = 0;
2091 ref->num_refs = 0;
2092 list_add_tail(&ref->node.list, &rec->backrefs);
2093 return ref;
2094 }
2095
2096 static int add_extent_rec(struct cache_tree *extent_cache,
2097 struct btrfs_key *parent_key,
2098 u64 start, u64 nr, u64 extent_item_refs,
2099 int is_root, int inc_ref, int set_checked)
2100 {
2101 struct extent_record *rec;
2102 struct cache_extent *cache;
2103 int ret = 0;
2104
2105 cache = find_cache_extent(extent_cache, start, nr);
2106 if (cache) {
2107 rec = container_of(cache, struct extent_record, cache);
2108 if (inc_ref)
2109 rec->refs++;
2110 if (rec->nr == 1)
2111 rec->nr = nr;
2112
2113 if (start != rec->start) {
2114 fprintf(stderr, "warning, start mismatch %llu %llu\n",
2115 (unsigned long long)rec->start,
2116 (unsigned long long)start);
2117 ret = 1;
2118 }
2119 if (extent_item_refs) {
2120 if (rec->extent_item_refs) {
2121 fprintf(stderr, "block %llu rec "
2122 "extent_item_refs %llu, passed %llu\n",
2123 (unsigned long long)start,
2124 (unsigned long long)
2125 rec->extent_item_refs,
2126 (unsigned long long)extent_item_refs);
2127 }
2128 rec->extent_item_refs = extent_item_refs;
2129 }
2130 if (is_root)
2131 rec->is_root = 1;
2132 if (set_checked) {
2133 rec->content_checked = 1;
2134 rec->owner_ref_checked = 1;
2135 }
2136
2137 if (parent_key)
2138 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2139
2140 maybe_free_extent_rec(extent_cache, rec);
2141 return ret;
2142 }
2143 rec = malloc(sizeof(*rec));
2144 rec->start = start;
2145 rec->nr = nr;
2146 rec->content_checked = 0;
2147 rec->owner_ref_checked = 0;
2148 INIT_LIST_HEAD(&rec->backrefs);
2149
2150 if (is_root)
2151 rec->is_root = 1;
2152 else
2153 rec->is_root = 0;
2154
2155 if (inc_ref)
2156 rec->refs = 1;
2157 else
2158 rec->refs = 0;
2159
2160 if (extent_item_refs)
2161 rec->extent_item_refs = extent_item_refs;
2162 else
2163 rec->extent_item_refs = 0;
2164
2165 if (parent_key)
2166 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2167 else
2168 memset(&rec->parent_key, 0, sizeof(*parent_key));
2169
2170 rec->cache.start = start;
2171 rec->cache.size = nr;
2172 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
2173 BUG_ON(ret);
2174 bytes_used += nr;
2175 if (set_checked) {
2176 rec->content_checked = 1;
2177 rec->owner_ref_checked = 1;
2178 }
2179 return ret;
2180 }
2181
2182 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
2183 u64 parent, u64 root, int found_ref)
2184 {
2185 struct extent_record *rec;
2186 struct tree_backref *back;
2187 struct cache_extent *cache;
2188
2189 cache = find_cache_extent(extent_cache, bytenr, 1);
2190 if (!cache) {
2191 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2192 cache = find_cache_extent(extent_cache, bytenr, 1);
2193 if (!cache)
2194 abort();
2195 }
2196
2197 rec = container_of(cache, struct extent_record, cache);
2198 if (rec->start != bytenr) {
2199 abort();
2200 }
2201
2202 back = find_tree_backref(rec, parent, root);
2203 if (!back)
2204 back = alloc_tree_backref(rec, parent, root);
2205
2206 if (found_ref) {
2207 if (back->node.found_ref) {
2208 fprintf(stderr, "Extent back ref already exists "
2209 "for %llu parent %llu root %llu \n",
2210 (unsigned long long)bytenr,
2211 (unsigned long long)parent,
2212 (unsigned long long)root);
2213 }
2214 back->node.found_ref = 1;
2215 } else {
2216 if (back->node.found_extent_tree) {
2217 fprintf(stderr, "Extent back ref already exists "
2218 "for %llu parent %llu root %llu \n",
2219 (unsigned long long)bytenr,
2220 (unsigned long long)parent,
2221 (unsigned long long)root);
2222 }
2223 back->node.found_extent_tree = 1;
2224 }
2225 return 0;
2226 }
2227
2228 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
2229 u64 parent, u64 root, u64 owner, u64 offset,
2230 u32 num_refs, int found_ref)
2231 {
2232 struct extent_record *rec;
2233 struct data_backref *back;
2234 struct cache_extent *cache;
2235
2236 cache = find_cache_extent(extent_cache, bytenr, 1);
2237 if (!cache) {
2238 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2239 cache = find_cache_extent(extent_cache, bytenr, 1);
2240 if (!cache)
2241 abort();
2242 }
2243
2244 rec = container_of(cache, struct extent_record, cache);
2245 if (rec->start != bytenr) {
2246 abort();
2247 }
2248 back = find_data_backref(rec, parent, root, owner, offset);
2249 if (!back)
2250 back = alloc_data_backref(rec, parent, root, owner, offset);
2251
2252 if (found_ref) {
2253 BUG_ON(num_refs != 1);
2254 back->node.found_ref = 1;
2255 back->found_ref += 1;
2256 } else {
2257 if (back->node.found_extent_tree) {
2258 fprintf(stderr, "Extent back ref already exists "
2259 "for %llu parent %llu root %llu"
2260 "owner %llu offset %llu num_refs %lu\n",
2261 (unsigned long long)bytenr,
2262 (unsigned long long)parent,
2263 (unsigned long long)root,
2264 (unsigned long long)owner,
2265 (unsigned long long)offset,
2266 (unsigned long)num_refs);
2267 }
2268 back->num_refs = num_refs;
2269 back->node.found_extent_tree = 1;
2270 }
2271 return 0;
2272 }
2273
2274 static int add_pending(struct cache_tree *pending,
2275 struct cache_tree *seen, u64 bytenr, u32 size)
2276 {
2277 int ret;
2278 ret = insert_cache_extent(seen, bytenr, size);
2279 if (ret)
2280 return ret;
2281 insert_cache_extent(pending, bytenr, size);
2282 return 0;
2283 }
2284
2285 static int pick_next_pending(struct cache_tree *pending,
2286 struct cache_tree *reada,
2287 struct cache_tree *nodes,
2288 u64 last, struct block_info *bits, int bits_nr,
2289 int *reada_bits)
2290 {
2291 unsigned long node_start = last;
2292 struct cache_extent *cache;
2293 int ret;
2294
2295 cache = find_first_cache_extent(reada, 0);
2296 if (cache) {
2297 bits[0].start = cache->start;
2298 bits[1].size = cache->size;
2299 *reada_bits = 1;
2300 return 1;
2301 }
2302 *reada_bits = 0;
2303 if (node_start > 32768)
2304 node_start -= 32768;
2305
2306 cache = find_first_cache_extent(nodes, node_start);
2307 if (!cache)
2308 cache = find_first_cache_extent(nodes, 0);
2309
2310 if (!cache) {
2311 cache = find_first_cache_extent(pending, 0);
2312 if (!cache)
2313 return 0;
2314 ret = 0;
2315 do {
2316 bits[ret].start = cache->start;
2317 bits[ret].size = cache->size;
2318 cache = next_cache_extent(cache);
2319 ret++;
2320 } while (cache && ret < bits_nr);
2321 return ret;
2322 }
2323
2324 ret = 0;
2325 do {
2326 bits[ret].start = cache->start;
2327 bits[ret].size = cache->size;
2328 cache = next_cache_extent(cache);
2329 ret++;
2330 } while (cache && ret < bits_nr);
2331
2332 if (bits_nr - ret > 8) {
2333 u64 lookup = bits[0].start + bits[0].size;
2334 struct cache_extent *next;
2335 next = find_first_cache_extent(pending, lookup);
2336 while(next) {
2337 if (next->start - lookup > 32768)
2338 break;
2339 bits[ret].start = next->start;
2340 bits[ret].size = next->size;
2341 lookup = next->start + next->size;
2342 ret++;
2343 if (ret == bits_nr)
2344 break;
2345 next = next_cache_extent(next);
2346 if (!next)
2347 break;
2348 }
2349 }
2350 return ret;
2351 }
2352
2353 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2354 static int process_extent_ref_v0(struct cache_tree *extent_cache,
2355 struct extent_buffer *leaf, int slot)
2356 {
2357 struct btrfs_extent_ref_v0 *ref0;
2358 struct btrfs_key key;
2359
2360 btrfs_item_key_to_cpu(leaf, &key, slot);
2361 ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
2362 if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
2363 add_tree_backref(extent_cache, key.objectid, key.offset,
2364 0, 0);
2365 } else {
2366 add_data_backref(extent_cache, key.objectid, key.offset, 0,
2367 0, 0, btrfs_ref_count_v0(leaf, ref0), 0);
2368 }
2369 return 0;
2370 }
2371 #endif
2372
2373 static int process_extent_item(struct cache_tree *extent_cache,
2374 struct extent_buffer *eb, int slot)
2375 {
2376 struct btrfs_extent_item *ei;
2377 struct btrfs_extent_inline_ref *iref;
2378 struct btrfs_extent_data_ref *dref;
2379 struct btrfs_shared_data_ref *sref;
2380 struct btrfs_key key;
2381 unsigned long end;
2382 unsigned long ptr;
2383 int type;
2384 u32 item_size = btrfs_item_size_nr(eb, slot);
2385 u64 refs = 0;
2386 u64 offset;
2387
2388 btrfs_item_key_to_cpu(eb, &key, slot);
2389
2390 if (item_size < sizeof(*ei)) {
2391 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2392 struct btrfs_extent_item_v0 *ei0;
2393 BUG_ON(item_size != sizeof(*ei0));
2394 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
2395 refs = btrfs_extent_refs_v0(eb, ei0);
2396 #else
2397 BUG();
2398 #endif
2399 return add_extent_rec(extent_cache, NULL, key.objectid,
2400 key.offset, refs, 0, 0, 0);
2401 }
2402
2403 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
2404 refs = btrfs_extent_refs(eb, ei);
2405
2406 add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
2407 refs, 0, 0, 0);
2408
2409 ptr = (unsigned long)(ei + 1);
2410 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2411 ptr += sizeof(struct btrfs_tree_block_info);
2412
2413 end = (unsigned long)ei + item_size;
2414 while (ptr < end) {
2415 iref = (struct btrfs_extent_inline_ref *)ptr;
2416 type = btrfs_extent_inline_ref_type(eb, iref);
2417 offset = btrfs_extent_inline_ref_offset(eb, iref);
2418 switch (type) {
2419 case BTRFS_TREE_BLOCK_REF_KEY:
2420 add_tree_backref(extent_cache, key.objectid,
2421 0, offset, 0);
2422 break;
2423 case BTRFS_SHARED_BLOCK_REF_KEY:
2424 add_tree_backref(extent_cache, key.objectid,
2425 offset, 0, 0);
2426 break;
2427 case BTRFS_EXTENT_DATA_REF_KEY:
2428 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
2429 add_data_backref(extent_cache, key.objectid, 0,
2430 btrfs_extent_data_ref_root(eb, dref),
2431 btrfs_extent_data_ref_objectid(eb,
2432 dref),
2433 btrfs_extent_data_ref_offset(eb, dref),
2434 btrfs_extent_data_ref_count(eb, dref),
2435 0);
2436 break;
2437 case BTRFS_SHARED_DATA_REF_KEY:
2438 sref = (struct btrfs_shared_data_ref *)(iref + 1);
2439 add_data_backref(extent_cache, key.objectid, offset,
2440 0, 0, 0,
2441 btrfs_shared_data_ref_count(eb, sref),
2442 0);
2443 break;
2444 default:
2445 BUG();
2446 }
2447 ptr += btrfs_extent_inline_ref_size(type);
2448 }
2449 WARN_ON(ptr > end);
2450 return 0;
2451 }
2452
2453 static int run_next_block(struct btrfs_root *root,
2454 struct block_info *bits,
2455 int bits_nr,
2456 u64 *last,
2457 struct cache_tree *pending,
2458 struct cache_tree *seen,
2459 struct cache_tree *reada,
2460 struct cache_tree *nodes,
2461 struct cache_tree *extent_cache)
2462 {
2463 struct extent_buffer *buf;
2464 u64 bytenr;
2465 u32 size;
2466 u64 parent;
2467 u64 owner;
2468 u64 flags;
2469 int ret;
2470 int i;
2471 int nritems;
2472 struct btrfs_key key;
2473 struct cache_extent *cache;
2474 int reada_bits;
2475
2476 ret = pick_next_pending(pending, reada, nodes, *last, bits,
2477 bits_nr, &reada_bits);
2478 if (ret == 0) {
2479 return 1;
2480 }
2481 if (!reada_bits) {
2482 for(i = 0; i < ret; i++) {
2483 insert_cache_extent(reada, bits[i].start,
2484 bits[i].size);
2485
2486 /* fixme, get the parent transid */
2487 readahead_tree_block(root, bits[i].start,
2488 bits[i].size, 0);
2489 }
2490 }
2491 *last = bits[0].start;
2492 bytenr = bits[0].start;
2493 size = bits[0].size;
2494
2495 cache = find_cache_extent(pending, bytenr, size);
2496 if (cache) {
2497 remove_cache_extent(pending, cache);
2498 free(cache);
2499 }
2500 cache = find_cache_extent(reada, bytenr, size);
2501 if (cache) {
2502 remove_cache_extent(reada, cache);
2503 free(cache);
2504 }
2505 cache = find_cache_extent(nodes, bytenr, size);
2506 if (cache) {
2507 remove_cache_extent(nodes, cache);
2508 free(cache);
2509 }
2510
2511 /* fixme, get the real parent transid */
2512 buf = read_tree_block(root, bytenr, size, 0);
2513 nritems = btrfs_header_nritems(buf);
2514
2515 ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
2516
2517 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
2518 parent = bytenr;
2519 owner = 0;
2520 } else {
2521 parent = 0;
2522 owner = btrfs_header_owner(buf);
2523 }
2524
2525 ret = check_block(root, extent_cache, buf, flags);
2526
2527 if (btrfs_is_leaf(buf)) {
2528 btree_space_waste += btrfs_leaf_free_space(root, buf);
2529 for (i = 0; i < nritems; i++) {
2530 struct btrfs_file_extent_item *fi;
2531 btrfs_item_key_to_cpu(buf, &key, i);
2532 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
2533 process_extent_item(extent_cache, buf, i);
2534 continue;
2535 }
2536 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
2537 total_csum_bytes +=
2538 btrfs_item_size_nr(buf, i);
2539 continue;
2540 }
2541 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
2542 struct btrfs_block_group_item *bi;
2543 bi = btrfs_item_ptr(buf, i,
2544 struct btrfs_block_group_item);
2545 #if 0
2546 fprintf(stderr,"block group %Lu %Lu used %Lu ",
2547 btrfs_disk_key_objectid(disk_key),
2548 btrfs_disk_key_offset(disk_key),
2549 btrfs_block_group_used(bi));
2550 fprintf(stderr, "flags %x\n", bi->flags);
2551 #endif
2552 continue;
2553 }
2554 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
2555 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2556 process_extent_ref_v0(extent_cache, buf, i);
2557 #else
2558 BUG();
2559 #endif
2560 continue;
2561 }
2562
2563 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2564 add_tree_backref(extent_cache, key.objectid, 0,
2565 key.offset, 0);
2566 continue;
2567 }
2568 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2569 add_tree_backref(extent_cache, key.objectid,
2570 key.offset, 0, 0);
2571 continue;
2572 }
2573 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
2574 struct btrfs_extent_data_ref *ref;
2575 ref = btrfs_item_ptr(buf, i,
2576 struct btrfs_extent_data_ref);
2577 add_data_backref(extent_cache,
2578 key.objectid, 0,
2579 btrfs_extent_data_ref_root(buf, ref),
2580 btrfs_extent_data_ref_objectid(buf,
2581 ref),
2582 btrfs_extent_data_ref_offset(buf, ref),
2583 btrfs_extent_data_ref_count(buf, ref),
2584 0);
2585 continue;
2586 }
2587 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
2588 struct btrfs_shared_data_ref *ref;
2589 ref = btrfs_item_ptr(buf, i,
2590 struct btrfs_shared_data_ref);
2591 add_data_backref(extent_cache,
2592 key.objectid, key.offset, 0, 0, 0,
2593 btrfs_shared_data_ref_count(buf, ref),
2594 0);
2595 continue;
2596 }
2597 if (key.type != BTRFS_EXTENT_DATA_KEY)
2598 continue;
2599 fi = btrfs_item_ptr(buf, i,
2600 struct btrfs_file_extent_item);
2601 if (btrfs_file_extent_type(buf, fi) ==
2602 BTRFS_FILE_EXTENT_INLINE)
2603 continue;
2604 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2605 continue;
2606
2607 data_bytes_allocated +=
2608 btrfs_file_extent_disk_num_bytes(buf, fi);
2609 if (data_bytes_allocated < root->sectorsize) {
2610 abort();
2611 }
2612 data_bytes_referenced +=
2613 btrfs_file_extent_num_bytes(buf, fi);
2614 ret = add_extent_rec(extent_cache, NULL,
2615 btrfs_file_extent_disk_bytenr(buf, fi),
2616 btrfs_file_extent_disk_num_bytes(buf, fi),
2617 0, 0, 1, 1);
2618 add_data_backref(extent_cache,
2619 btrfs_file_extent_disk_bytenr(buf, fi),
2620 parent, owner, key.objectid, key.offset -
2621 btrfs_file_extent_offset(buf, fi), 1, 1);
2622 BUG_ON(ret);
2623 }
2624 } else {
2625 int level;
2626 level = btrfs_header_level(buf);
2627 for (i = 0; i < nritems; i++) {
2628 u64 ptr = btrfs_node_blockptr(buf, i);
2629 u32 size = btrfs_level_size(root, level - 1);
2630 btrfs_node_key_to_cpu(buf, &key, i);
2631 ret = add_extent_rec(extent_cache, &key,
2632 ptr, size, 0, 0, 1, 0);
2633 BUG_ON(ret);
2634
2635 add_tree_backref(extent_cache, ptr, parent,
2636 owner, 1);
2637
2638 if (level > 1) {
2639 add_pending(nodes, seen, ptr, size);
2640 } else {
2641 add_pending(pending, seen, ptr, size);
2642 }
2643 }
2644 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2645 nritems) * sizeof(struct btrfs_key_ptr);
2646 }
2647 total_btree_bytes += buf->len;
2648 if (fs_root_objectid(btrfs_header_owner(buf)))
2649 total_fs_tree_bytes += buf->len;
2650 if (!found_old_backref &&
2651 btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
2652 btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
2653 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
2654 found_old_backref = 1;
2655 free_extent_buffer(buf);
2656 return 0;
2657 }
2658
2659 static int add_root_to_pending(struct extent_buffer *buf,
2660 struct block_info *bits,
2661 int bits_nr,
2662 struct cache_tree *extent_cache,
2663 struct cache_tree *pending,
2664 struct cache_tree *seen,
2665 struct cache_tree *reada,
2666 struct cache_tree *nodes,
2667 struct btrfs_key *root_key)
2668 {
2669 if (btrfs_header_level(buf) > 0)
2670 add_pending(nodes, seen, buf->start, buf->len);
2671 else
2672 add_pending(pending, seen, buf->start, buf->len);
2673 add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2674 0, 1, 1, 0);
2675
2676 if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
2677 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2678 add_tree_backref(extent_cache, buf->start, buf->start, 0, 1);
2679 else
2680 add_tree_backref(extent_cache, buf->start, 0,
2681 root_key->objectid, 1);
2682 return 0;
2683 }
2684
2685 static int check_extent_refs(struct btrfs_root *root,
2686 struct cache_tree *extent_cache)
2687 {
2688 struct extent_record *rec;
2689 struct cache_extent *cache;
2690 int err = 0;
2691
2692 while(1) {
2693 cache = find_first_cache_extent(extent_cache, 0);
2694 if (!cache)
2695 break;
2696 rec = container_of(cache, struct extent_record, cache);
2697 if (rec->refs != rec->extent_item_refs) {
2698 fprintf(stderr, "ref mismatch on [%llu %llu] ",
2699 (unsigned long long)rec->start,
2700 (unsigned long long)rec->nr);
2701 fprintf(stderr, "extent item %llu, found %llu\n",
2702 (unsigned long long)rec->extent_item_refs,
2703 (unsigned long long)rec->refs);
2704 err = 1;
2705 }
2706 if (all_backpointers_checked(rec, 1)) {
2707 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
2708 (unsigned long long)rec->start,
2709 (unsigned long long)rec->nr);
2710
2711 err = 1;
2712 }
2713 if (!rec->owner_ref_checked) {
2714 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
2715 (unsigned long long)rec->start,
2716 (unsigned long long)rec->nr);
2717 err = 1;
2718 }
2719
2720 remove_cache_extent(extent_cache, cache);
2721 free_all_extent_backrefs(rec);
2722 free(rec);
2723 }
2724 return err;
2725 }
2726
2727 static int check_extents(struct btrfs_root *root)
2728 {
2729 struct cache_tree extent_cache;
2730 struct cache_tree seen;
2731 struct cache_tree pending;
2732 struct cache_tree reada;
2733 struct cache_tree nodes;
2734 struct btrfs_path path;
2735 struct btrfs_key key;
2736 struct btrfs_key found_key;
2737 int ret;
2738 u64 last = 0;
2739 struct block_info *bits;
2740 int bits_nr;
2741 struct extent_buffer *leaf;
2742 int slot;
2743 struct btrfs_root_item ri;
2744
2745 cache_tree_init(&extent_cache);
2746 cache_tree_init(&seen);
2747 cache_tree_init(&pending);
2748 cache_tree_init(&nodes);
2749 cache_tree_init(&reada);
2750
2751 bits_nr = 1024;
2752 bits = malloc(bits_nr * sizeof(struct block_info));
2753 if (!bits) {
2754 perror("malloc");
2755 exit(1);
2756 }
2757
2758 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2759 &extent_cache, &pending, &seen, &reada, &nodes,
2760 &root->fs_info->tree_root->root_key);
2761
2762 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2763 &extent_cache, &pending, &seen, &reada, &nodes,
2764 &root->fs_info->chunk_root->root_key);
2765
2766 btrfs_init_path(&path);
2767 key.offset = 0;
2768 key.objectid = 0;
2769 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2770 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2771 &key, &path, 0, 0);
2772 BUG_ON(ret < 0);
2773 while(1) {
2774 leaf = path.nodes[0];
2775 slot = path.slots[0];
2776 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2777 ret = btrfs_next_leaf(root, &path);
2778 if (ret != 0)
2779 break;
2780 leaf = path.nodes[0];
2781 slot = path.slots[0];
2782 }
2783 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2784 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2785 unsigned long offset;
2786 struct extent_buffer *buf;
2787
2788 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2789 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2790 buf = read_tree_block(root->fs_info->tree_root,
2791 btrfs_root_bytenr(&ri),
2792 btrfs_level_size(root,
2793 btrfs_root_level(&ri)), 0);
2794 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2795 &pending, &seen, &reada, &nodes,
2796 &found_key);
2797 free_extent_buffer(buf);
2798 }
2799 path.slots[0]++;
2800 }
2801 btrfs_release_path(root, &path);
2802 while(1) {
2803 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2804 &seen, &reada, &nodes, &extent_cache);
2805 if (ret != 0)
2806 break;
2807 }
2808 ret = check_extent_refs(root, &extent_cache);
2809 return ret;
2810 }
2811
2812 static void print_usage(void)
2813 {
2814 fprintf(stderr, "usage: btrfsck dev\n");
2815 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2816 exit(1);
2817 }
2818
2819 int main(int ac, char **av)
2820 {
2821 struct cache_tree root_cache;
2822 struct btrfs_root *root;
2823 u64 bytenr = 0;
2824 int ret;
2825 int num;
2826
2827 while(1) {
2828 int c;
2829 c = getopt(ac, av, "s:");
2830 if (c < 0)
2831 break;
2832 switch(c) {
2833 case 's':
2834 num = atol(optarg);
2835 bytenr = btrfs_sb_offset(num);
2836 printf("using SB copy %d, bytenr %llu\n", num,
2837 (unsigned long long)bytenr);
2838 break;
2839 default:
2840 print_usage();
2841 }
2842 }
2843 ac = ac - optind;
2844
2845 if (ac != 1)
2846 print_usage();
2847
2848 radix_tree_init();
2849 cache_tree_init(&root_cache);
2850
2851 if((ret = check_mounted(av[optind])) < 0) {
2852 fprintf(stderr, "Could not check mount status: %s\n", strerror(ret));
2853 return ret;
2854 } else if(ret) {
2855 fprintf(stderr, "%s is currently mounted. Aborting.\n", av[optind]);
2856 return -EBUSY;
2857 }
2858
2859 root = open_ctree(av[optind], bytenr, 0);
2860
2861 if (root == NULL)
2862 return 1;
2863
2864 ret = check_extents(root);
2865 if (ret)
2866 goto out;
2867 ret = check_fs_roots(root, &root_cache);
2868 if (ret)
2869 goto out;
2870
2871 ret = check_root_refs(root, &root_cache);
2872 out:
2873 free_root_recs(&root_cache);
2874 close_ctree(root);
2875
2876 if (found_old_backref) {
2877 /*
2878 * there was a disk format change when mixed
2879 * backref was in testing tree. The old format
2880 * existed about one week.
2881 */
2882 printf("\n * Found old mixed backref format. "
2883 "The old format is not supported! *"
2884 "\n * Please mount the FS in readonly mode, "
2885 "backup data and re-format the FS. *\n\n");
2886 ret = 1;
2887 }
2888 printf("found %llu bytes used err is %d\n",
2889 (unsigned long long)bytes_used, ret);
2890 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2891 printf("total tree bytes: %llu\n",
2892 (unsigned long long)total_btree_bytes);
2893 printf("total fs tree bytes: %llu\n",
2894 (unsigned long long)total_fs_tree_bytes);
2895 printf("btree space waste bytes: %llu\n",
2896 (unsigned long long)btree_space_waste);
2897 printf("file data blocks allocated: %llu\n referenced %llu\n",
2898 (unsigned long long)data_bytes_allocated,
2899 (unsigned long long)data_bytes_referenced);
2900 printf("%s\n", BTRFS_BUILD_VERSION);
2901 return ret;
2902 }
Btrfs-progs-unstable mirror