?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix inode link count checks in btrfsck
[btrfs-progs-unstable.git] / btrfsck.c
blobcd2cedd7a9a864841143c6d313e1111ef44876dc
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 <fcntl.h>
24 #include <sys/stat.h>
25 #include "kerncompat.h"
26 #include "ctree.h"
27 #include "disk-io.h"
28 #include "print-tree.h"
29 #include "transaction.h"
30 #include "list.h"
31 #include "version.h"
32 #include "utils.h"
33
34 static u64 bytes_used = 0;
35 static u64 total_csum_bytes = 0;
36 static u64 total_btree_bytes = 0;
37 static u64 total_fs_tree_bytes = 0;
38 static u64 btree_space_waste = 0;
39 static u64 data_bytes_allocated = 0;
40 static u64 data_bytes_referenced = 0;
41 static int found_old_backref = 0;
42
43 struct extent_backref {
44 struct list_head list;
45 unsigned int is_data:1;
46 unsigned int found_extent_tree:1;
47 unsigned int full_backref:1;
48 unsigned int found_ref:1;
49 };
50
51 struct data_backref {
52 struct extent_backref node;
53 union {
54 u64 parent;
55 u64 root;
56 };
57 u64 owner;
58 u64 offset;
59 u32 num_refs;
60 u32 found_ref;
61 };
62
63 struct tree_backref {
64 struct extent_backref node;
65 union {
66 u64 parent;
67 u64 root;
68 };
69 };
70
71 struct extent_record {
72 struct list_head backrefs;
73 struct cache_extent cache;
74 struct btrfs_disk_key parent_key;
75 u64 start;
76 u64 nr;
77 u64 refs;
78 u64 extent_item_refs;
79 unsigned int content_checked:1;
80 unsigned int owner_ref_checked:1;
81 unsigned int is_root:1;
82 };
83
84 struct inode_backref {
85 struct list_head list;
86 unsigned int found_dir_item:1;
87 unsigned int found_dir_index:1;
88 unsigned int found_inode_ref:1;
89 unsigned int filetype:8;
90 int errors;
91 u64 dir;
92 u64 index;
93 u16 namelen;
94 char name[0];
95 };
96
97 #define REF_ERR_NO_DIR_ITEM (1 << 0)
98 #define REF_ERR_NO_DIR_INDEX (1 << 1)
99 #define REF_ERR_NO_INODE_REF (1 << 2)
100 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
101 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
102 #define REF_ERR_DUP_INODE_REF (1 << 5)
103 #define REF_ERR_INDEX_UNMATCH (1 << 6)
104 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
105 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
106 #define REF_ERR_NO_ROOT_REF (1 << 9)
107 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
108 #define REF_ERR_DUP_ROOT_REF (1 << 11)
109 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
110
111 struct inode_record {
112 struct list_head backrefs;
113 unsigned int checked:1;
114 unsigned int merging:1;
115 unsigned int found_inode_item:1;
116 unsigned int found_dir_item:1;
117 unsigned int found_file_extent:1;
118 unsigned int found_csum_item:1;
119 unsigned int some_csum_missing:1;
120 unsigned int nodatasum:1;
121 int errors;
122
123 u64 ino;
124 u32 nlink;
125 u32 imode;
126 u64 isize;
127 u64 nbytes;
128
129 u32 found_link;
130 u64 found_size;
131 u64 extent_start;
132 u64 extent_end;
133 u64 first_extent_gap;
134
135 u32 refs;
136 };
137
138 #define I_ERR_NO_INODE_ITEM (1 << 0)
139 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
140 #define I_ERR_DUP_INODE_ITEM (1 << 2)
141 #define I_ERR_DUP_DIR_INDEX (1 << 3)
142 #define I_ERR_ODD_DIR_ITEM (1 << 4)
143 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
144 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
145 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
146 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
147 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
148 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
149 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
150 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
151 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
152
153 struct root_backref {
154 struct list_head list;
155 unsigned int found_dir_item:1;
156 unsigned int found_dir_index:1;
157 unsigned int found_back_ref:1;
158 unsigned int found_forward_ref:1;
159 unsigned int reachable:1;
160 int errors;
161 u64 ref_root;
162 u64 dir;
163 u64 index;
164 u16 namelen;
165 char name[0];
166 };
167
168 struct root_record {
169 struct list_head backrefs;
170 struct cache_extent cache;
171 unsigned int found_root_item:1;
172 u64 objectid;
173 u32 found_ref;
174 };
175
176 struct ptr_node {
177 struct cache_extent cache;
178 void *data;
179 };
180
181 struct shared_node {
182 struct cache_extent cache;
183 struct cache_tree root_cache;
184 struct cache_tree inode_cache;
185 struct inode_record *current;
186 u32 refs;
187 };
188
189 struct block_info {
190 u64 start;
191 u32 size;
192 };
193
194 struct walk_control {
195 struct cache_tree shared;
196 struct shared_node *nodes[BTRFS_MAX_LEVEL];
197 int active_node;
198 int root_level;
199 };
200
201 static u8 imode_to_type(u32 imode)
202 {
203 #define S_SHIFT 12
204 static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
205 [S_IFREG >> S_SHIFT] = BTRFS_FT_REG_FILE,
206 [S_IFDIR >> S_SHIFT] = BTRFS_FT_DIR,
207 [S_IFCHR >> S_SHIFT] = BTRFS_FT_CHRDEV,
208 [S_IFBLK >> S_SHIFT] = BTRFS_FT_BLKDEV,
209 [S_IFIFO >> S_SHIFT] = BTRFS_FT_FIFO,
210 [S_IFSOCK >> S_SHIFT] = BTRFS_FT_SOCK,
211 [S_IFLNK >> S_SHIFT] = BTRFS_FT_SYMLINK,
212 };
213
214 return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
215 #undef S_SHIFT
216 }
217
218 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
219 {
220 struct inode_record *rec;
221 struct inode_backref *backref;
222 struct inode_backref *orig;
223 size_t size;
224
225 rec = malloc(sizeof(*rec));
226 memcpy(rec, orig_rec, sizeof(*rec));
227 rec->refs = 1;
228 INIT_LIST_HEAD(&rec->backrefs);
229
230 list_for_each_entry(orig, &orig_rec->backrefs, list) {
231 size = sizeof(*orig) + orig->namelen + 1;
232 backref = malloc(size);
233 memcpy(backref, orig, size);
234 list_add_tail(&backref->list, &rec->backrefs);
235 }
236 return rec;
237 }
238
239 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
240 u64 ino, int mod)
241 {
242 struct ptr_node *node;
243 struct cache_extent *cache;
244 struct inode_record *rec = NULL;
245 int ret;
246
247 cache = find_cache_extent(inode_cache, ino, 1);
248 if (cache) {
249 node = container_of(cache, struct ptr_node, cache);
250 rec = node->data;
251 if (mod && rec->refs > 1) {
252 node->data = clone_inode_rec(rec);
253 rec->refs--;
254 rec = node->data;
255 }
256 } else if (mod) {
257 rec = calloc(1, sizeof(*rec));
258 rec->ino = ino;
259 rec->extent_start = (u64)-1;
260 rec->first_extent_gap = (u64)-1;
261 rec->refs = 1;
262 INIT_LIST_HEAD(&rec->backrefs);
263
264 node = malloc(sizeof(*node));
265 node->cache.start = ino;
266 node->cache.size = 1;
267 node->data = rec;
268
269 ret = insert_existing_cache_extent(inode_cache, &node->cache);
270 BUG_ON(ret);
271 }
272 return rec;
273 }
274
275 static void free_inode_rec(struct inode_record *rec)
276 {
277 struct inode_backref *backref;
278
279 if (--rec->refs > 0)
280 return;
281
282 while (!list_empty(&rec->backrefs)) {
283 backref = list_entry(rec->backrefs.next,
284 struct inode_backref, list);
285 list_del(&backref->list);
286 free(backref);
287 }
288 free(rec);
289 }
290
291 static int can_free_inode_rec(struct inode_record *rec)
292 {
293 if (!rec->errors && rec->checked && rec->found_inode_item &&
294 rec->nlink == rec->found_link && list_empty(&rec->backrefs))
295 return 1;
296 return 0;
297 }
298
299 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
300 struct inode_record *rec)
301 {
302 struct cache_extent *cache;
303 struct inode_backref *tmp, *backref;
304 struct ptr_node *node;
305 unsigned char filetype;
306
307 if (!rec->found_inode_item)
308 return;
309
310 filetype = imode_to_type(rec->imode);
311 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
312 if (backref->found_dir_item && backref->found_dir_index) {
313 if (backref->filetype != filetype)
314 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
315 if (!backref->errors && backref->found_inode_ref) {
316 list_del(&backref->list);
317 free(backref);
318 }
319 }
320 }
321
322 if (!rec->checked || rec->merging)
323 return;
324
325 if (S_ISDIR(rec->imode)) {
326 if (rec->found_size != rec->isize)
327 rec->errors |= I_ERR_DIR_ISIZE_WRONG;
328 if (rec->found_file_extent)
329 rec->errors |= I_ERR_ODD_FILE_EXTENT;
330 } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
331 if (rec->found_dir_item)
332 rec->errors |= I_ERR_ODD_DIR_ITEM;
333 if (rec->found_size != rec->nbytes)
334 rec->errors |= I_ERR_FILE_NBYTES_WRONG;
335 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
336 rec->first_extent_gap = 0;
337 if (rec->nlink > 0 && (rec->extent_end < rec->isize ||
338 rec->first_extent_gap < rec->isize))
339 rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
340 }
341
342 if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
343 if (rec->found_csum_item && rec->nodatasum)
344 rec->errors |= I_ERR_ODD_CSUM_ITEM;
345 if (rec->some_csum_missing && !rec->nodatasum)
346 rec->errors |= I_ERR_SOME_CSUM_MISSING;
347 }
348
349 BUG_ON(rec->refs != 1);
350 if (can_free_inode_rec(rec)) {
351 cache = find_cache_extent(inode_cache, rec->ino, 1);
352 node = container_of(cache, struct ptr_node, cache);
353 BUG_ON(node->data != rec);
354 remove_cache_extent(inode_cache, &node->cache);
355 free(node);
356 free_inode_rec(rec);
357 }
358 }
359
360 static int check_orphan_item(struct btrfs_root *root, u64 ino)
361 {
362 struct btrfs_path path;
363 struct btrfs_key key;
364 int ret;
365
366 key.objectid = BTRFS_ORPHAN_OBJECTID;
367 key.type = BTRFS_ORPHAN_ITEM_KEY;
368 key.offset = ino;
369
370 btrfs_init_path(&path);
371 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
372 btrfs_release_path(root, &path);
373 if (ret > 0)
374 ret = -ENOENT;
375 return ret;
376 }
377
378 static int process_inode_item(struct extent_buffer *eb,
379 int slot, struct btrfs_key *key,
380 struct shared_node *active_node)
381 {
382 struct inode_record *rec;
383 struct btrfs_inode_item *item;
384
385 rec = active_node->current;
386 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
387 if (rec->found_inode_item) {
388 rec->errors |= I_ERR_DUP_INODE_ITEM;
389 return 1;
390 }
391 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
392 rec->nlink = btrfs_inode_nlink(eb, item);
393 rec->isize = btrfs_inode_size(eb, item);
394 rec->nbytes = btrfs_inode_nbytes(eb, item);
395 rec->imode = btrfs_inode_mode(eb, item);
396 if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
397 rec->nodatasum = 1;
398 rec->found_inode_item = 1;
399 if (rec->nlink == 0)
400 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
401 maybe_free_inode_rec(&active_node->inode_cache, rec);
402 return 0;
403 }
404
405 static struct inode_backref *get_inode_backref(struct inode_record *rec,
406 const char *name,
407 int namelen, u64 dir)
408 {
409 struct inode_backref *backref;
410
411 list_for_each_entry(backref, &rec->backrefs, list) {
412 if (backref->dir != dir || backref->namelen != namelen)
413 continue;
414 if (memcmp(name, backref->name, namelen))
415 continue;
416 return backref;
417 }
418
419 backref = malloc(sizeof(*backref) + namelen + 1);
420 memset(backref, 0, sizeof(*backref));
421 backref->dir = dir;
422 backref->namelen = namelen;
423 memcpy(backref->name, name, namelen);
424 backref->name[namelen] = '\0';
425 list_add_tail(&backref->list, &rec->backrefs);
426 return backref;
427 }
428
429 static int add_inode_backref(struct cache_tree *inode_cache,
430 u64 ino, u64 dir, u64 index,
431 const char *name, int namelen,
432 int filetype, int itemtype, int errors)
433 {
434 struct inode_record *rec;
435 struct inode_backref *backref;
436
437 rec = get_inode_rec(inode_cache, ino, 1);
438 backref = get_inode_backref(rec, name, namelen, dir);
439 if (errors)
440 backref->errors |= errors;
441 if (itemtype == BTRFS_DIR_INDEX_KEY) {
442 if (backref->found_dir_index)
443 backref->errors |= REF_ERR_DUP_DIR_INDEX;
444 if (backref->found_inode_ref && backref->index != index)
445 backref->errors |= REF_ERR_INDEX_UNMATCH;
446 if (backref->found_dir_item && backref->filetype != filetype)
447 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
448
449 backref->index = index;
450 backref->filetype = filetype;
451 backref->found_dir_index = 1;
452 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
453 rec->found_link++;
454 if (backref->found_dir_item)
455 backref->errors |= REF_ERR_DUP_DIR_ITEM;
456 if (backref->found_dir_index && backref->filetype != filetype)
457 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
458
459 backref->filetype = filetype;
460 backref->found_dir_item = 1;
461 } else if (itemtype == BTRFS_INODE_REF_KEY) {
462 if (backref->found_inode_ref)
463 backref->errors |= REF_ERR_DUP_INODE_REF;
464 if (backref->found_dir_index && backref->index != index)
465 backref->errors |= REF_ERR_INDEX_UNMATCH;
466
467 backref->index = index;
468 backref->found_inode_ref = 1;
469 } else {
470 BUG_ON(1);
471 }
472
473 maybe_free_inode_rec(inode_cache, rec);
474 return 0;
475 }
476
477 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
478 struct cache_tree *dst_cache)
479 {
480 struct inode_backref *backref;
481 u32 dir_count = 0;
482
483 dst->merging = 1;
484 list_for_each_entry(backref, &src->backrefs, list) {
485 if (backref->found_dir_index) {
486 add_inode_backref(dst_cache, dst->ino, backref->dir,
487 backref->index, backref->name,
488 backref->namelen, backref->filetype,
489 BTRFS_DIR_INDEX_KEY, backref->errors);
490 }
491 if (backref->found_dir_item) {
492 dir_count++;
493 add_inode_backref(dst_cache, dst->ino,
494 backref->dir, 0, backref->name,
495 backref->namelen, backref->filetype,
496 BTRFS_DIR_ITEM_KEY, backref->errors);
497 }
498 if (backref->found_inode_ref) {
499 add_inode_backref(dst_cache, dst->ino,
500 backref->dir, backref->index,
501 backref->name, backref->namelen, 0,
502 BTRFS_INODE_REF_KEY, backref->errors);
503 }
504 }
505
506 if (src->found_dir_item)
507 dst->found_dir_item = 1;
508 if (src->found_file_extent)
509 dst->found_file_extent = 1;
510 if (src->found_csum_item)
511 dst->found_csum_item = 1;
512 if (src->some_csum_missing)
513 dst->some_csum_missing = 1;
514 if (dst->first_extent_gap > src->first_extent_gap)
515 dst->first_extent_gap = src->first_extent_gap;
516
517 BUG_ON(src->found_link < dir_count);
518 dst->found_link += src->found_link - dir_count;
519 dst->found_size += src->found_size;
520 if (src->extent_start != (u64)-1) {
521 if (dst->extent_start == (u64)-1) {
522 dst->extent_start = src->extent_start;
523 dst->extent_end = src->extent_end;
524 } else {
525 if (dst->extent_end > src->extent_start)
526 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
527 else if (dst->extent_end < src->extent_start &&
528 dst->extent_end < dst->first_extent_gap)
529 dst->first_extent_gap = dst->extent_end;
530 if (dst->extent_end < src->extent_end)
531 dst->extent_end = src->extent_end;
532 }
533 }
534
535 dst->errors |= src->errors;
536 if (src->found_inode_item) {
537 if (!dst->found_inode_item) {
538 dst->nlink = src->nlink;
539 dst->isize = src->isize;
540 dst->nbytes = src->nbytes;
541 dst->imode = src->imode;
542 dst->nodatasum = src->nodatasum;
543 dst->found_inode_item = 1;
544 } else {
545 dst->errors |= I_ERR_DUP_INODE_ITEM;
546 }
547 }
548 dst->merging = 0;
549
550 return 0;
551 }
552
553 static int splice_shared_node(struct shared_node *src_node,
554 struct shared_node *dst_node)
555 {
556 struct cache_extent *cache;
557 struct ptr_node *node, *ins;
558 struct cache_tree *src, *dst;
559 struct inode_record *rec, *conflict;
560 u64 current_ino = 0;
561 int splice = 0;
562 int ret;
563
564 if (--src_node->refs == 0)
565 splice = 1;
566 if (src_node->current)
567 current_ino = src_node->current->ino;
568
569 src = &src_node->root_cache;
570 dst = &dst_node->root_cache;
571 again:
572 cache = find_first_cache_extent(src, 0);
573 while (cache) {
574 node = container_of(cache, struct ptr_node, cache);
575 rec = node->data;
576 cache = next_cache_extent(cache);
577
578 if (splice) {
579 remove_cache_extent(src, &node->cache);
580 ins = node;
581 } else {
582 ins = malloc(sizeof(*ins));
583 ins->cache.start = node->cache.start;
584 ins->cache.size = node->cache.size;
585 ins->data = rec;
586 rec->refs++;
587 }
588 ret = insert_existing_cache_extent(dst, &ins->cache);
589 if (ret == -EEXIST) {
590 conflict = get_inode_rec(dst, rec->ino, 1);
591 merge_inode_recs(rec, conflict, dst);
592 if (rec->checked) {
593 conflict->checked = 1;
594 if (dst_node->current == conflict)
595 dst_node->current = NULL;
596 }
597 maybe_free_inode_rec(dst, conflict);
598 free_inode_rec(rec);
599 free(ins);
600 } else {
601 BUG_ON(ret);
602 }
603 }
604
605 if (src == &src_node->root_cache) {
606 src = &src_node->inode_cache;
607 dst = &dst_node->inode_cache;
608 goto again;
609 }
610
611 if (current_ino > 0 && (!dst_node->current ||
612 current_ino > dst_node->current->ino)) {
613 if (dst_node->current) {
614 dst_node->current->checked = 1;
615 maybe_free_inode_rec(dst, dst_node->current);
616 }
617 dst_node->current = get_inode_rec(dst, current_ino, 1);
618 }
619 return 0;
620 }
621
622 static void free_inode_recs(struct cache_tree *inode_cache)
623 {
624 struct cache_extent *cache;
625 struct ptr_node *node;
626 struct inode_record *rec;
627
628 while (1) {
629 cache = find_first_cache_extent(inode_cache, 0);
630 if (!cache)
631 break;
632 node = container_of(cache, struct ptr_node, cache);
633 rec = node->data;
634 remove_cache_extent(inode_cache, &node->cache);
635 free(node);
636 free_inode_rec(rec);
637 }
638 }
639
640 static struct shared_node *find_shared_node(struct cache_tree *shared,
641 u64 bytenr)
642 {
643 struct cache_extent *cache;
644 struct shared_node *node;
645
646 cache = find_cache_extent(shared, bytenr, 1);
647 if (cache) {
648 node = container_of(cache, struct shared_node, cache);
649 return node;
650 }
651 return NULL;
652 }
653
654 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
655 {
656 int ret;
657 struct shared_node *node;
658
659 node = calloc(1, sizeof(*node));
660 node->cache.start = bytenr;
661 node->cache.size = 1;
662 cache_tree_init(&node->root_cache);
663 cache_tree_init(&node->inode_cache);
664 node->refs = refs;
665
666 ret = insert_existing_cache_extent(shared, &node->cache);
667 BUG_ON(ret);
668 return 0;
669 }
670
671 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
672 struct walk_control *wc, int level)
673 {
674 struct shared_node *node;
675 struct shared_node *dest;
676
677 if (level == wc->active_node)
678 return 0;
679
680 BUG_ON(wc->active_node <= level);
681 node = find_shared_node(&wc->shared, bytenr);
682 if (!node) {
683 add_shared_node(&wc->shared, bytenr, refs);
684 node = find_shared_node(&wc->shared, bytenr);
685 wc->nodes[level] = node;
686 wc->active_node = level;
687 return 0;
688 }
689
690 if (wc->root_level == wc->active_node &&
691 btrfs_root_refs(&root->root_item) == 0) {
692 if (--node->refs == 0) {
693 free_inode_recs(&node->root_cache);
694 free_inode_recs(&node->inode_cache);
695 remove_cache_extent(&wc->shared, &node->cache);
696 free(node);
697 }
698 return 1;
699 }
700
701 dest = wc->nodes[wc->active_node];
702 splice_shared_node(node, dest);
703 if (node->refs == 0) {
704 remove_cache_extent(&wc->shared, &node->cache);
705 free(node);
706 }
707 return 1;
708 }
709
710 static int leave_shared_node(struct btrfs_root *root,
711 struct walk_control *wc, int level)
712 {
713 struct shared_node *node;
714 struct shared_node *dest;
715 int i;
716
717 if (level == wc->root_level)
718 return 0;
719
720 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
721 if (wc->nodes[i])
722 break;
723 }
724 BUG_ON(i >= BTRFS_MAX_LEVEL);
725
726 node = wc->nodes[wc->active_node];
727 wc->nodes[wc->active_node] = NULL;
728 wc->active_node = i;
729
730 dest = wc->nodes[wc->active_node];
731 if (wc->active_node < wc->root_level ||
732 btrfs_root_refs(&root->root_item) > 0) {
733 BUG_ON(node->refs <= 1);
734 splice_shared_node(node, dest);
735 } else {
736 BUG_ON(node->refs < 2);
737 node->refs--;
738 }
739 return 0;
740 }
741
742 static int process_dir_item(struct extent_buffer *eb,
743 int slot, struct btrfs_key *key,
744 struct shared_node *active_node)
745 {
746 u32 total;
747 u32 cur = 0;
748 u32 len;
749 u32 name_len;
750 u32 data_len;
751 int error;
752 int nritems = 0;
753 int filetype;
754 struct btrfs_dir_item *di;
755 struct inode_record *rec;
756 struct cache_tree *root_cache;
757 struct cache_tree *inode_cache;
758 struct btrfs_key location;
759 char namebuf[BTRFS_NAME_LEN];
760
761 root_cache = &active_node->root_cache;
762 inode_cache = &active_node->inode_cache;
763 rec = active_node->current;
764 rec->found_dir_item = 1;
765
766 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
767 total = btrfs_item_size_nr(eb, slot);
768 while (cur < total) {
769 nritems++;
770 btrfs_dir_item_key_to_cpu(eb, di, &location);
771 name_len = btrfs_dir_name_len(eb, di);
772 data_len = btrfs_dir_data_len(eb, di);
773 filetype = btrfs_dir_type(eb, di);
774
775 rec->found_size += name_len;
776 if (name_len <= BTRFS_NAME_LEN) {
777 len = name_len;
778 error = 0;
779 } else {
780 len = BTRFS_NAME_LEN;
781 error = REF_ERR_NAME_TOO_LONG;
782 }
783 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
784
785 if (location.type == BTRFS_INODE_ITEM_KEY) {
786 add_inode_backref(inode_cache, location.objectid,
787 key->objectid, key->offset, namebuf,
788 len, filetype, key->type, error);
789 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
790 add_inode_backref(root_cache, location.objectid,
791 key->objectid, key->offset, namebuf,
792 len, filetype, key->type, error);
793 } else {
794 fprintf(stderr, "warning line %d\n", __LINE__);
795 }
796
797 len = sizeof(*di) + name_len + data_len;
798 di = (struct btrfs_dir_item *)((char *)di + len);
799 cur += len;
800 }
801 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
802 rec->errors |= I_ERR_DUP_DIR_INDEX;
803
804 return 0;
805 }
806
807 static int process_inode_ref(struct extent_buffer *eb,
808 int slot, struct btrfs_key *key,
809 struct shared_node *active_node)
810 {
811 u32 total;
812 u32 cur = 0;
813 u32 len;
814 u32 name_len;
815 u64 index;
816 int error;
817 struct cache_tree *inode_cache;
818 struct btrfs_inode_ref *ref;
819 char namebuf[BTRFS_NAME_LEN];
820
821 inode_cache = &active_node->inode_cache;
822
823 ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
824 total = btrfs_item_size_nr(eb, slot);
825 while (cur < total) {
826 name_len = btrfs_inode_ref_name_len(eb, ref);
827 index = btrfs_inode_ref_index(eb, ref);
828 if (name_len <= BTRFS_NAME_LEN) {
829 len = name_len;
830 error = 0;
831 } else {
832 len = BTRFS_NAME_LEN;
833 error = REF_ERR_NAME_TOO_LONG;
834 }
835 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
836 add_inode_backref(inode_cache, key->objectid, key->offset,
837 index, namebuf, len, 0, key->type, error);
838
839 len = sizeof(*ref) + name_len;
840 ref = (struct btrfs_inode_ref *)((char *)ref + len);
841 cur += len;
842 }
843 return 0;
844 }
845
846 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
847 {
848 struct btrfs_key key;
849 struct btrfs_path path;
850 struct extent_buffer *leaf;
851 int ret ;
852 size_t size;
853 u64 found = 0;
854 u64 csum_end;
855 u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
856
857 btrfs_init_path(&path);
858
859 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
860 key.offset = start;
861 key.type = BTRFS_EXTENT_CSUM_KEY;
862
863 ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
864 &key, &path, 0, 0);
865 BUG_ON(ret < 0);
866 if (ret > 0 && path.slots[0] > 0) {
867 leaf = path.nodes[0];
868 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
869 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
870 key.type == BTRFS_EXTENT_CSUM_KEY)
871 path.slots[0]--;
872 }
873
874 while (len > 0) {
875 leaf = path.nodes[0];
876 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
877 ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
878 BUG_ON(ret < 0);
879 if (ret > 0)
880 break;
881 leaf = path.nodes[0];
882 }
883
884 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
885 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
886 key.type != BTRFS_EXTENT_CSUM_KEY)
887 break;
888
889 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
890 if (key.offset >= start + len)
891 break;
892
893 if (key.offset > start)
894 start = key.offset;
895
896 size = btrfs_item_size_nr(leaf, path.slots[0]);
897 csum_end = key.offset + (size / csum_size) * root->sectorsize;
898 if (csum_end > start) {
899 size = min(csum_end - start, len);
900 len -= size;
901 start += size;
902 found += size;
903 }
904
905 path.slots[0]++;
906 }
907 btrfs_release_path(root->fs_info->csum_root, &path);
908 return found;
909 }
910
911 static int process_file_extent(struct btrfs_root *root,
912 struct extent_buffer *eb,
913 int slot, struct btrfs_key *key,
914 struct shared_node *active_node)
915 {
916 struct inode_record *rec;
917 struct btrfs_file_extent_item *fi;
918 u64 num_bytes = 0;
919 u64 disk_bytenr = 0;
920 u64 extent_offset = 0;
921 u64 mask = root->sectorsize - 1;
922 int extent_type;
923
924 rec = active_node->current;
925 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
926 rec->found_file_extent = 1;
927
928 if (rec->extent_start == (u64)-1) {
929 rec->extent_start = key->offset;
930 rec->extent_end = key->offset;
931 }
932
933 if (rec->extent_end > key->offset)
934 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
935 else if (rec->extent_end < key->offset &&
936 rec->extent_end < rec->first_extent_gap)
937 rec->first_extent_gap = rec->extent_end;
938
939 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
940 extent_type = btrfs_file_extent_type(eb, fi);
941
942 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
943 num_bytes = btrfs_file_extent_inline_len(eb, fi);
944 if (num_bytes == 0)
945 rec->errors |= I_ERR_BAD_FILE_EXTENT;
946 rec->found_size += num_bytes;
947 num_bytes = (num_bytes + mask) & ~mask;
948 } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
949 extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
950 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
951 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
952 extent_offset = btrfs_file_extent_offset(eb, fi);
953 if (num_bytes == 0 || (num_bytes & mask))
954 rec->errors |= I_ERR_BAD_FILE_EXTENT;
955 if (num_bytes + extent_offset >
956 btrfs_file_extent_ram_bytes(eb, fi))
957 rec->errors |= I_ERR_BAD_FILE_EXTENT;
958 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
959 (btrfs_file_extent_compression(eb, fi) ||
960 btrfs_file_extent_encryption(eb, fi) ||
961 btrfs_file_extent_other_encoding(eb, fi)))
962 rec->errors |= I_ERR_BAD_FILE_EXTENT;
963 if (disk_bytenr > 0)
964 rec->found_size += num_bytes;
965 } else {
966 rec->errors |= I_ERR_BAD_FILE_EXTENT;
967 }
968 rec->extent_end = key->offset + num_bytes;
969
970 if (disk_bytenr > 0) {
971 u64 found;
972 if (btrfs_file_extent_compression(eb, fi))
973 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
974 else
975 disk_bytenr += extent_offset;
976
977 found = count_csum_range(root, disk_bytenr, num_bytes);
978 if (extent_type == BTRFS_FILE_EXTENT_REG) {
979 if (found > 0)
980 rec->found_csum_item = 1;
981 if (found < num_bytes)
982 rec->some_csum_missing = 1;
983 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
984 if (found > 0)
985 rec->errors |= I_ERR_ODD_CSUM_ITEM;
986 }
987 }
988 return 0;
989 }
990
991 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
992 struct walk_control *wc)
993 {
994 struct btrfs_key key;
995 u32 nritems;
996 int i;
997 int ret;
998 struct cache_tree *inode_cache;
999 struct shared_node *active_node;
1000
1001 if (wc->root_level == wc->active_node &&
1002 btrfs_root_refs(&root->root_item) == 0)
1003 return 0;
1004
1005 active_node = wc->nodes[wc->active_node];
1006 inode_cache = &active_node->inode_cache;
1007 nritems = btrfs_header_nritems(eb);
1008 for (i = 0; i < nritems; i++) {
1009 btrfs_item_key_to_cpu(eb, &key, i);
1010 if (active_node->current == NULL ||
1011 active_node->current->ino < key.objectid) {
1012 if (active_node->current) {
1013 active_node->current->checked = 1;
1014 maybe_free_inode_rec(inode_cache,
1015 active_node->current);
1016 }
1017 active_node->current = get_inode_rec(inode_cache,
1018 key.objectid, 1);
1019 }
1020 switch (key.type) {
1021 case BTRFS_DIR_ITEM_KEY:
1022 case BTRFS_DIR_INDEX_KEY:
1023 ret = process_dir_item(eb, i, &key, active_node);
1024 break;
1025 case BTRFS_INODE_REF_KEY:
1026 ret = process_inode_ref(eb, i, &key, active_node);
1027 break;
1028 case BTRFS_INODE_ITEM_KEY:
1029 ret = process_inode_item(eb, i, &key, active_node);
1030 break;
1031 case BTRFS_EXTENT_DATA_KEY:
1032 ret = process_file_extent(root, eb, i, &key,
1033 active_node);
1034 break;
1035 default:
1036 break;
1037 };
1038 }
1039 return 0;
1040 }
1041
1042 static void reada_walk_down(struct btrfs_root *root,
1043 struct extent_buffer *node, int slot)
1044 {
1045 u64 bytenr;
1046 u64 ptr_gen;
1047 u32 nritems;
1048 u32 blocksize;
1049 int i;
1050 int ret;
1051 int level;
1052
1053 level = btrfs_header_level(node);
1054 if (level != 1)
1055 return;
1056
1057 nritems = btrfs_header_nritems(node);
1058 blocksize = btrfs_level_size(root, level - 1);
1059 for (i = slot; i < nritems; i++) {
1060 bytenr = btrfs_node_blockptr(node, i);
1061 ptr_gen = btrfs_node_ptr_generation(node, i);
1062 ret = readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1063 if (ret)
1064 break;
1065 }
1066 }
1067
1068 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1069 struct walk_control *wc, int *level)
1070 {
1071 u64 bytenr;
1072 u64 ptr_gen;
1073 struct extent_buffer *next;
1074 struct extent_buffer *cur;
1075 u32 blocksize;
1076 int ret;
1077 u64 refs;
1078
1079 WARN_ON(*level < 0);
1080 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1081 ret = btrfs_lookup_extent_info(NULL, root,
1082 path->nodes[*level]->start,
1083 path->nodes[*level]->len, &refs, NULL);
1084 BUG_ON(ret);
1085 if (refs > 1) {
1086 ret = enter_shared_node(root, path->nodes[*level]->start,
1087 refs, wc, *level);
1088 if (ret > 0)
1089 goto out;
1090 }
1091
1092 while (*level >= 0) {
1093 WARN_ON(*level < 0);
1094 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1095 cur = path->nodes[*level];
1096
1097 if (btrfs_header_level(cur) != *level)
1098 WARN_ON(1);
1099
1100 if (path->slots[*level] >= btrfs_header_nritems(cur))
1101 break;
1102 if (*level == 0) {
1103 ret = process_one_leaf(root, cur, wc);
1104 break;
1105 }
1106 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1107 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1108 blocksize = btrfs_level_size(root, *level - 1);
1109 ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize,
1110 &refs, NULL);
1111 BUG_ON(ret);
1112
1113 if (refs > 1) {
1114 ret = enter_shared_node(root, bytenr, refs,
1115 wc, *level - 1);
1116 if (ret > 0) {
1117 path->slots[*level]++;
1118 continue;
1119 }
1120 }
1121
1122 next = btrfs_find_tree_block(root, bytenr, blocksize);
1123 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1124 free_extent_buffer(next);
1125 reada_walk_down(root, cur, path->slots[*level]);
1126 next = read_tree_block(root, bytenr, blocksize,
1127 ptr_gen);
1128 }
1129
1130 *level = *level - 1;
1131 free_extent_buffer(path->nodes[*level]);
1132 path->nodes[*level] = next;
1133 path->slots[*level] = 0;
1134 }
1135 out:
1136 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1137 return 0;
1138 }
1139
1140 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1141 struct walk_control *wc, int *level)
1142 {
1143 int i;
1144 struct extent_buffer *leaf;
1145
1146 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1147 leaf = path->nodes[i];
1148 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1149 path->slots[i]++;
1150 *level = i;
1151 return 0;
1152 } else {
1153 free_extent_buffer(path->nodes[*level]);
1154 path->nodes[*level] = NULL;
1155 BUG_ON(*level > wc->active_node);
1156 if (*level == wc->active_node)
1157 leave_shared_node(root, wc, *level);
1158 *level = i + 1;
1159 }
1160 }
1161 return 1;
1162 }
1163
1164 static int check_root_dir(struct inode_record *rec)
1165 {
1166 struct inode_backref *backref;
1167 int ret = -1;
1168
1169 if (!rec->found_inode_item || rec->errors)
1170 goto out;
1171 if (rec->nlink != 1 || rec->found_link != 0)
1172 goto out;
1173 if (list_empty(&rec->backrefs))
1174 goto out;
1175 backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1176 if (!backref->found_inode_ref)
1177 goto out;
1178 if (backref->index != 0 || backref->namelen != 2 ||
1179 memcmp(backref->name, "..", 2))
1180 goto out;
1181 if (backref->found_dir_index || backref->found_dir_item)
1182 goto out;
1183 ret = 0;
1184 out:
1185 return ret;
1186 }
1187
1188 static int check_inode_recs(struct btrfs_root *root,
1189 struct cache_tree *inode_cache)
1190 {
1191 struct cache_extent *cache;
1192 struct ptr_node *node;
1193 struct inode_record *rec;
1194 struct inode_backref *backref;
1195 int ret;
1196 u64 error = 0;
1197 u64 root_dirid = btrfs_root_dirid(&root->root_item);
1198
1199 if (btrfs_root_refs(&root->root_item) == 0) {
1200 if (!cache_tree_empty(inode_cache))
1201 fprintf(stderr, "warning line %d\n", __LINE__);
1202 return 0;
1203 }
1204
1205 rec = get_inode_rec(inode_cache, root_dirid, 0);
1206 if (rec) {
1207 ret = check_root_dir(rec);
1208 if (ret) {
1209 fprintf(stderr, "root %llu root dir %llu error\n",
1210 (unsigned long long)root->root_key.objectid,
1211 (unsigned long long)root_dirid);
1212 error++;
1213 }
1214 } else {
1215 fprintf(stderr, "root %llu root dir %llu not found\n",
1216 (unsigned long long)root->root_key.objectid,
1217 (unsigned long long)root_dirid);
1218 }
1219
1220 while (1) {
1221 cache = find_first_cache_extent(inode_cache, 0);
1222 if (!cache)
1223 break;
1224 node = container_of(cache, struct ptr_node, cache);
1225 rec = node->data;
1226 remove_cache_extent(inode_cache, &node->cache);
1227 free(node);
1228 if (rec->ino == root_dirid ||
1229 rec->ino == BTRFS_ORPHAN_OBJECTID) {
1230 free_inode_rec(rec);
1231 continue;
1232 }
1233
1234 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1235 ret = check_orphan_item(root, rec->ino);
1236 if (ret == 0)
1237 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1238 if (can_free_inode_rec(rec)) {
1239 free_inode_rec(rec);
1240 continue;
1241 }
1242 }
1243
1244 error++;
1245 if (!rec->found_inode_item)
1246 rec->errors |= I_ERR_NO_INODE_ITEM;
1247 if (rec->found_link != rec->nlink)
1248 rec->errors |= I_ERR_LINK_COUNT_WRONG;
1249 fprintf(stderr, "root %llu inode %llu errors %x\n",
1250 (unsigned long long) root->root_key.objectid,
1251 (unsigned long long) rec->ino, rec->errors);
1252 list_for_each_entry(backref, &rec->backrefs, list) {
1253 if (!backref->found_dir_item)
1254 backref->errors |= REF_ERR_NO_DIR_ITEM;
1255 if (!backref->found_dir_index)
1256 backref->errors |= REF_ERR_NO_DIR_INDEX;
1257 if (!backref->found_inode_ref)
1258 backref->errors |= REF_ERR_NO_INODE_REF;
1259 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1260 " namelen %u name %s filetype %d error %x\n",
1261 (unsigned long long)backref->dir,
1262 (unsigned long long)backref->index,
1263 backref->namelen, backref->name,
1264 backref->filetype, backref->errors);
1265 }
1266 free_inode_rec(rec);
1267 }
1268 return (error > 0) ? -1 : 0;
1269 }
1270
1271 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1272 u64 objectid)
1273 {
1274 struct cache_extent *cache;
1275 struct root_record *rec = NULL;
1276 int ret;
1277
1278 cache = find_cache_extent(root_cache, objectid, 1);
1279 if (cache) {
1280 rec = container_of(cache, struct root_record, cache);
1281 } else {
1282 rec = calloc(1, sizeof(*rec));
1283 rec->objectid = objectid;
1284 INIT_LIST_HEAD(&rec->backrefs);
1285 rec->cache.start = objectid;
1286 rec->cache.size = 1;
1287
1288 ret = insert_existing_cache_extent(root_cache, &rec->cache);
1289 BUG_ON(ret);
1290 }
1291 return rec;
1292 }
1293
1294 static struct root_backref *get_root_backref(struct root_record *rec,
1295 u64 ref_root, u64 dir, u64 index,
1296 const char *name, int namelen)
1297 {
1298 struct root_backref *backref;
1299
1300 list_for_each_entry(backref, &rec->backrefs, list) {
1301 if (backref->ref_root != ref_root || backref->dir != dir ||
1302 backref->namelen != namelen)
1303 continue;
1304 if (memcmp(name, backref->name, namelen))
1305 continue;
1306 return backref;
1307 }
1308
1309 backref = malloc(sizeof(*backref) + namelen + 1);
1310 memset(backref, 0, sizeof(*backref));
1311 backref->ref_root = ref_root;
1312 backref->dir = dir;
1313 backref->index = index;
1314 backref->namelen = namelen;
1315 memcpy(backref->name, name, namelen);
1316 backref->name[namelen] = '\0';
1317 list_add_tail(&backref->list, &rec->backrefs);
1318 return backref;
1319 }
1320
1321 static void free_root_recs(struct cache_tree *root_cache)
1322 {
1323 struct cache_extent *cache;
1324 struct root_record *rec;
1325 struct root_backref *backref;
1326
1327 while (1) {
1328 cache = find_first_cache_extent(root_cache, 0);
1329 if (!cache)
1330 break;
1331 rec = container_of(cache, struct root_record, cache);
1332 remove_cache_extent(root_cache, &rec->cache);
1333
1334 while (!list_empty(&rec->backrefs)) {
1335 backref = list_entry(rec->backrefs.next,
1336 struct root_backref, list);
1337 list_del(&backref->list);
1338 free(backref);
1339 }
1340 kfree(rec);
1341 }
1342 }
1343
1344 static int add_root_backref(struct cache_tree *root_cache,
1345 u64 root_id, u64 ref_root, u64 dir, u64 index,
1346 const char *name, int namelen,
1347 int item_type, int errors)
1348 {
1349 struct root_record *rec;
1350 struct root_backref *backref;
1351
1352 rec = get_root_rec(root_cache, root_id);
1353 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
1354
1355 backref->errors |= errors;
1356
1357 if (item_type != BTRFS_DIR_ITEM_KEY) {
1358 if (backref->found_dir_index || backref->found_back_ref ||
1359 backref->found_forward_ref) {
1360 if (backref->index != index)
1361 backref->errors |= REF_ERR_INDEX_UNMATCH;
1362 } else {
1363 backref->index = index;
1364 }
1365 }
1366
1367 if (item_type == BTRFS_DIR_ITEM_KEY) {
1368 backref->found_dir_item = 1;
1369 backref->reachable = 1;
1370 rec->found_ref++;
1371 } else if (item_type == BTRFS_DIR_INDEX_KEY) {
1372 backref->found_dir_index = 1;
1373 } else if (item_type == BTRFS_ROOT_REF_KEY) {
1374 if (backref->found_forward_ref)
1375 backref->errors |= REF_ERR_DUP_ROOT_REF;
1376 backref->found_forward_ref = 1;
1377 } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
1378 if (backref->found_back_ref)
1379 backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
1380 backref->found_back_ref = 1;
1381 } else {
1382 BUG_ON(1);
1383 }
1384
1385 return 0;
1386 }
1387
1388 static int merge_root_recs(struct btrfs_root *root,
1389 struct cache_tree *src_cache,
1390 struct cache_tree *dst_cache)
1391 {
1392 struct cache_extent *cache;
1393 struct ptr_node *node;
1394 struct inode_record *rec;
1395 struct inode_backref *backref;
1396
1397 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1398 free_inode_recs(src_cache);
1399 return 0;
1400 }
1401
1402 while (1) {
1403 cache = find_first_cache_extent(src_cache, 0);
1404 if (!cache)
1405 break;
1406 node = container_of(cache, struct ptr_node, cache);
1407 rec = node->data;
1408 remove_cache_extent(src_cache, &node->cache);
1409 free(node);
1410
1411 list_for_each_entry(backref, &rec->backrefs, list) {
1412 BUG_ON(backref->found_inode_ref);
1413 if (backref->found_dir_item)
1414 add_root_backref(dst_cache, rec->ino,
1415 root->root_key.objectid, backref->dir,
1416 backref->index, backref->name,
1417 backref->namelen, BTRFS_DIR_ITEM_KEY,
1418 backref->errors);
1419 if (backref->found_dir_index)
1420 add_root_backref(dst_cache, rec->ino,
1421 root->root_key.objectid, backref->dir,
1422 backref->index, backref->name,
1423 backref->namelen, BTRFS_DIR_INDEX_KEY,
1424 backref->errors);
1425 }
1426 free_inode_rec(rec);
1427 }
1428 return 0;
1429 }
1430
1431 static int check_root_refs(struct btrfs_root *root,
1432 struct cache_tree *root_cache)
1433 {
1434 struct root_record *rec;
1435 struct root_record *ref_root;
1436 struct root_backref *backref;
1437 struct cache_extent *cache;
1438 int loop = 1;
1439 int ret;
1440 int error;
1441 int errors = 0;
1442
1443 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
1444 rec->found_ref = 1;
1445
1446 /* fixme: this can not detect circular references */
1447 while (loop) {
1448 loop = 0;
1449 cache = find_first_cache_extent(root_cache, 0);
1450 while (1) {
1451 if (!cache)
1452 break;
1453 rec = container_of(cache, struct root_record, cache);
1454 cache = next_cache_extent(cache);
1455
1456 if (rec->found_ref == 0)
1457 continue;
1458
1459 list_for_each_entry(backref, &rec->backrefs, list) {
1460 if (!backref->reachable)
1461 continue;
1462
1463 ref_root = get_root_rec(root_cache,
1464 backref->ref_root);
1465 if (ref_root->found_ref > 0)
1466 continue;
1467
1468 backref->reachable = 0;
1469 rec->found_ref--;
1470 if (rec->found_ref == 0)
1471 loop = 1;
1472 }
1473 }
1474 }
1475
1476 cache = find_first_cache_extent(root_cache, 0);
1477 while (1) {
1478 if (!cache)
1479 break;
1480 rec = container_of(cache, struct root_record, cache);
1481 cache = next_cache_extent(cache);
1482
1483 if (rec->found_ref == 0 &&
1484 rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1485 rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
1486 ret = check_orphan_item(root->fs_info->tree_root,
1487 rec->objectid);
1488 if (ret == 0)
1489 continue;
1490 errors++;
1491 fprintf(stderr, "fs tree %llu not referenced\n",
1492 (unsigned long long)rec->objectid);
1493 }
1494
1495 error = 0;
1496 if (rec->found_ref > 0 && !rec->found_root_item)
1497 error = 1;
1498 list_for_each_entry(backref, &rec->backrefs, list) {
1499 if (!backref->found_dir_item)
1500 backref->errors |= REF_ERR_NO_DIR_ITEM;
1501 if (!backref->found_dir_index)
1502 backref->errors |= REF_ERR_NO_DIR_INDEX;
1503 if (!backref->found_back_ref)
1504 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
1505 if (!backref->found_forward_ref)
1506 backref->errors |= REF_ERR_NO_ROOT_REF;
1507 if (backref->reachable && backref->errors)
1508 error = 1;
1509 }
1510 if (!error)
1511 continue;
1512
1513 errors++;
1514 fprintf(stderr, "fs tree %llu refs %u %s\n",
1515 (unsigned long long)rec->objectid, rec->found_ref,
1516 rec->found_root_item ? "" : "not found");
1517
1518 list_for_each_entry(backref, &rec->backrefs, list) {
1519 if (!backref->reachable)
1520 continue;
1521 if (!backref->errors && rec->found_root_item)
1522 continue;
1523 fprintf(stderr, "\tunresolved ref root %llu dir %llu"
1524 " index %llu namelen %u name %s error %x\n",
1525 (unsigned long long)backref->ref_root,
1526 (unsigned long long)backref->dir,
1527 (unsigned long long)backref->index,
1528 backref->namelen, backref->name,
1529 backref->errors);
1530 }
1531 }
1532 return errors > 0 ? 1 : 0;
1533 }
1534
1535 static int process_root_ref(struct extent_buffer *eb, int slot,
1536 struct btrfs_key *key,
1537 struct cache_tree *root_cache)
1538 {
1539 u64 dirid;
1540 u64 index;
1541 u32 len;
1542 u32 name_len;
1543 struct btrfs_root_ref *ref;
1544 char namebuf[BTRFS_NAME_LEN];
1545 int error;
1546
1547 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
1548
1549 dirid = btrfs_root_ref_dirid(eb, ref);
1550 index = btrfs_root_ref_sequence(eb, ref);
1551 name_len = btrfs_root_ref_name_len(eb, ref);
1552
1553 if (name_len <= BTRFS_NAME_LEN) {
1554 len = name_len;
1555 error = 0;
1556 } else {
1557 len = BTRFS_NAME_LEN;
1558 error = REF_ERR_NAME_TOO_LONG;
1559 }
1560 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1561
1562 if (key->type == BTRFS_ROOT_REF_KEY) {
1563 add_root_backref(root_cache, key->offset, key->objectid, dirid,
1564 index, namebuf, len, key->type, error);
1565 } else {
1566 add_root_backref(root_cache, key->objectid, key->offset, dirid,
1567 index, namebuf, len, key->type, error);
1568 }
1569 return 0;
1570 }
1571
1572 static int check_fs_root(struct btrfs_root *root,
1573 struct cache_tree *root_cache,
1574 struct walk_control *wc)
1575 {
1576 int ret = 0;
1577 int wret;
1578 int level;
1579 struct btrfs_path path;
1580 struct shared_node root_node;
1581 struct root_record *rec;
1582 struct btrfs_root_item *root_item = &root->root_item;
1583
1584 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1585 rec = get_root_rec(root_cache, root->root_key.objectid);
1586 if (btrfs_root_refs(root_item) > 0)
1587 rec->found_root_item = 1;
1588 }
1589
1590 btrfs_init_path(&path);
1591 memset(&root_node, 0, sizeof(root_node));
1592 cache_tree_init(&root_node.root_cache);
1593 cache_tree_init(&root_node.inode_cache);
1594
1595 level = btrfs_header_level(root->node);
1596 memset(wc->nodes, 0, sizeof(wc->nodes));
1597 wc->nodes[level] = &root_node;
1598 wc->active_node = level;
1599 wc->root_level = level;
1600
1601 if (btrfs_root_refs(root_item) > 0 ||
1602 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1603 path.nodes[level] = root->node;
1604 extent_buffer_get(root->node);
1605 path.slots[level] = 0;
1606 } else {
1607 struct btrfs_key key;
1608 struct btrfs_disk_key found_key;
1609
1610 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1611 level = root_item->drop_level;
1612 path.lowest_level = level;
1613 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1614 BUG_ON(wret < 0);
1615 btrfs_node_key(path.nodes[level], &found_key,
1616 path.slots[level]);
1617 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1618 sizeof(found_key)));
1619 }
1620
1621 while (1) {
1622 wret = walk_down_tree(root, &path, wc, &level);
1623 if (wret < 0)
1624 ret = wret;
1625 if (wret != 0)
1626 break;
1627
1628 wret = walk_up_tree(root, &path, wc, &level);
1629 if (wret < 0)
1630 ret = wret;
1631 if (wret != 0)
1632 break;
1633 }
1634 btrfs_release_path(root, &path);
1635
1636 merge_root_recs(root, &root_node.root_cache, root_cache);
1637
1638 if (root_node.current) {
1639 root_node.current->checked = 1;
1640 maybe_free_inode_rec(&root_node.inode_cache,
1641 root_node.current);
1642 }
1643
1644 ret = check_inode_recs(root, &root_node.inode_cache);
1645 return ret;
1646 }
1647
1648 static int fs_root_objectid(u64 objectid)
1649 {
1650 if (objectid == BTRFS_FS_TREE_OBJECTID ||
1651 objectid == BTRFS_TREE_RELOC_OBJECTID ||
1652 objectid == BTRFS_DATA_RELOC_TREE_OBJECTID ||
1653 (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1654 objectid <= BTRFS_LAST_FREE_OBJECTID))
1655 return 1;
1656 return 0;
1657 }
1658
1659 static int check_fs_roots(struct btrfs_root *root,
1660 struct cache_tree *root_cache)
1661 {
1662 struct btrfs_path path;
1663 struct btrfs_key key;
1664 struct walk_control wc;
1665 struct extent_buffer *leaf;
1666 struct btrfs_root *tmp_root;
1667 struct btrfs_root *tree_root = root->fs_info->tree_root;
1668 int ret;
1669 int err = 0;
1670
1671 memset(&wc, 0, sizeof(wc));
1672 cache_tree_init(&wc.shared);
1673 btrfs_init_path(&path);
1674
1675 key.offset = 0;
1676 key.objectid = 0;
1677 key.type = BTRFS_ROOT_ITEM_KEY;
1678 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1679 BUG_ON(ret < 0);
1680 while (1) {
1681 leaf = path.nodes[0];
1682 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1683 ret = btrfs_next_leaf(tree_root, &path);
1684 if (ret != 0)
1685 break;
1686 leaf = path.nodes[0];
1687 }
1688 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1689 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1690 fs_root_objectid(key.objectid)) {
1691 tmp_root = btrfs_read_fs_root_no_cache(root->fs_info,
1692 &key);
1693 ret = check_fs_root(tmp_root, root_cache, &wc);
1694 if (ret)
1695 err = 1;
1696 btrfs_free_fs_root(root->fs_info, tmp_root);
1697 } else if (key.type == BTRFS_ROOT_REF_KEY ||
1698 key.type == BTRFS_ROOT_BACKREF_KEY) {
1699 process_root_ref(leaf, path.slots[0], &key,
1700 root_cache);
1701 }
1702 path.slots[0]++;
1703 }
1704 btrfs_release_path(tree_root, &path);
1705
1706 if (!cache_tree_empty(&wc.shared))
1707 fprintf(stderr, "warning line %d\n", __LINE__);
1708
1709 return err;
1710 }
1711
1712 static int check_node(struct btrfs_root *root,
1713 struct btrfs_disk_key *parent_key,
1714 struct extent_buffer *buf)
1715 {
1716 int i;
1717 struct btrfs_key cpukey;
1718 struct btrfs_disk_key key;
1719 u32 nritems = btrfs_header_nritems(buf);
1720
1721 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1722 return 1;
1723 if (parent_key->type) {
1724 btrfs_node_key(buf, &key, 0);
1725 if (memcmp(parent_key, &key, sizeof(key)))
1726 return 1;
1727 }
1728 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1729 btrfs_node_key(buf, &key, i);
1730 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
1731 if (btrfs_comp_keys(&key, &cpukey) >= 0)
1732 return 1;
1733 }
1734 return 0;
1735 }
1736
1737 static int check_leaf(struct btrfs_root *root,
1738 struct btrfs_disk_key *parent_key,
1739 struct extent_buffer *buf)
1740 {
1741 int i;
1742 struct btrfs_key cpukey;
1743 struct btrfs_disk_key key;
1744 u32 nritems = btrfs_header_nritems(buf);
1745
1746 if (btrfs_header_level(buf) != 0) {
1747 fprintf(stderr, "leaf is not a leaf %llu\n",
1748 (unsigned long long)btrfs_header_bytenr(buf));
1749 return 1;
1750 }
1751 if (btrfs_leaf_free_space(root, buf) < 0) {
1752 fprintf(stderr, "leaf free space incorrect %llu %d\n",
1753 (unsigned long long)btrfs_header_bytenr(buf),
1754 btrfs_leaf_free_space(root, buf));
1755 return 1;
1756 }
1757
1758 if (nritems == 0)
1759 return 0;
1760
1761 btrfs_item_key(buf, &key, 0);
1762 if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
1763 fprintf(stderr, "leaf parent key incorrect %llu\n",
1764 (unsigned long long)btrfs_header_bytenr(buf));
1765 return 1;
1766 }
1767 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1768 btrfs_item_key(buf, &key, i);
1769 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
1770 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
1771 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
1772 return 1;
1773 }
1774 if (btrfs_item_offset_nr(buf, i) !=
1775 btrfs_item_end_nr(buf, i + 1)) {
1776 fprintf(stderr, "incorrect offsets %u %u\n",
1777 btrfs_item_offset_nr(buf, i),
1778 btrfs_item_end_nr(buf, i + 1));
1779 return 1;
1780 }
1781 if (i == 0 && btrfs_item_end_nr(buf, i) !=
1782 BTRFS_LEAF_DATA_SIZE(root)) {
1783 fprintf(stderr, "bad item end %u wanted %u\n",
1784 btrfs_item_end_nr(buf, i),
1785 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
1786 return 1;
1787 }
1788 }
1789 return 0;
1790 }
1791
1792 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1793 {
1794 struct list_head *cur = rec->backrefs.next;
1795 struct extent_backref *back;
1796 struct tree_backref *tback;
1797 struct data_backref *dback;
1798 u64 found = 0;
1799 int err = 0;
1800
1801 while(cur != &rec->backrefs) {
1802 back = list_entry(cur, struct extent_backref, list);
1803 cur = cur->next;
1804 if (!back->found_extent_tree) {
1805 err = 1;
1806 if (!print_errs)
1807 goto out;
1808 if (back->is_data) {
1809 dback = (struct data_backref *)back;
1810 fprintf(stderr, "Backref %llu %s %llu"
1811 " owner %llu offset %llu num_refs %lu"
1812 " not found in extent tree\n",
1813 (unsigned long long)rec->start,
1814 back->full_backref ?
1815 "parent" : "root",
1816 back->full_backref ?
1817 (unsigned long long)dback->parent:
1818 (unsigned long long)dback->root,
1819 (unsigned long long)dback->owner,
1820 (unsigned long long)dback->offset,
1821 (unsigned long)dback->num_refs);
1822 } else {
1823 tback = (struct tree_backref *)back;
1824 fprintf(stderr, "Backref %llu parent %llu"
1825 " root %llu not found in extent tree\n",
1826 (unsigned long long)rec->start,
1827 (unsigned long long)tback->parent,
1828 (unsigned long long)tback->root);
1829 }
1830 }
1831 if (!back->is_data && !back->found_ref) {
1832 err = 1;
1833 if (!print_errs)
1834 goto out;
1835 tback = (struct tree_backref *)back;
1836 fprintf(stderr, "Backref %llu %s %llu not referenced\n",
1837 (unsigned long long)rec->start,
1838 back->full_backref ? "parent" : "root",
1839 back->full_backref ?
1840 (unsigned long long)tback->parent :
1841 (unsigned long long)tback->root);
1842 }
1843 if (back->is_data) {
1844 dback = (struct data_backref *)back;
1845 if (dback->found_ref != dback->num_refs) {
1846 err = 1;
1847 if (!print_errs)
1848 goto out;
1849 fprintf(stderr, "Incorrect local backref count"
1850 " on %llu %s %llu owner %llu"
1851 " offset %llu found %u wanted %u\n",
1852 (unsigned long long)rec->start,
1853 back->full_backref ?
1854 "parent" : "root",
1855 back->full_backref ?
1856 (unsigned long long)dback->parent:
1857 (unsigned long long)dback->root,
1858 (unsigned long long)dback->owner,
1859 (unsigned long long)dback->offset,
1860 dback->found_ref, dback->num_refs);
1861 }
1862 }
1863 if (!back->is_data) {
1864 found += 1;
1865 } else {
1866 dback = (struct data_backref *)back;
1867 found += dback->found_ref;
1868 }
1869 }
1870 if (found != rec->refs) {
1871 err = 1;
1872 if (!print_errs)
1873 goto out;
1874 fprintf(stderr, "Incorrect global backref count "
1875 "on %llu found %llu wanted %llu\n",
1876 (unsigned long long)rec->start,
1877 (unsigned long long)found,
1878 (unsigned long long)rec->refs);
1879 }
1880 out:
1881 return err;
1882 }
1883
1884 static int free_all_extent_backrefs(struct extent_record *rec)
1885 {
1886 struct extent_backref *back;
1887 struct list_head *cur;
1888 while (!list_empty(&rec->backrefs)) {
1889 cur = rec->backrefs.next;
1890 back = list_entry(cur, struct extent_backref, list);
1891 list_del(cur);
1892 free(back);
1893 }
1894 return 0;
1895 }
1896
1897 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1898 struct extent_record *rec)
1899 {
1900 if (rec->content_checked && rec->owner_ref_checked &&
1901 rec->extent_item_refs == rec->refs && rec->refs > 0 &&
1902 !all_backpointers_checked(rec, 0)) {
1903 remove_cache_extent(extent_cache, &rec->cache);
1904 free_all_extent_backrefs(rec);
1905 free(rec);
1906 }
1907 return 0;
1908 }
1909
1910 static int check_owner_ref(struct btrfs_root *root,
1911 struct extent_record *rec,
1912 struct extent_buffer *buf)
1913 {
1914 struct extent_backref *node;
1915 struct tree_backref *back;
1916 struct btrfs_root *ref_root;
1917 struct btrfs_key key;
1918 struct btrfs_path path;
1919 int ret;
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 ret = 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 struct btrfs_block_group_item *bi;
2542 bi = btrfs_item_ptr(buf, i,
2543 struct btrfs_block_group_item);
2544 #if 0
2545 fprintf(stderr,"block group %Lu %Lu used %Lu ",
2546 btrfs_disk_key_objectid(disk_key),
2547 btrfs_disk_key_offset(disk_key),
2548 btrfs_block_group_used(bi));
2549 fprintf(stderr, "flags %x\n", bi->flags);
2550 #endif
2551 continue;
2552 }
2553 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
2554 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2555 process_extent_ref_v0(extent_cache, buf, i);
2556 #else
2557 BUG();
2558 #endif
2559 continue;
2560 }
2561
2562 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2563 add_tree_backref(extent_cache, key.objectid, 0,
2564 key.offset, 0);
2565 continue;
2566 }
2567 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2568 add_tree_backref(extent_cache, key.objectid,
2569 key.offset, 0, 0);
2570 continue;
2571 }
2572 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
2573 struct btrfs_extent_data_ref *ref;
2574 ref = btrfs_item_ptr(buf, i,
2575 struct btrfs_extent_data_ref);
2576 add_data_backref(extent_cache,
2577 key.objectid, 0,
2578 btrfs_extent_data_ref_root(buf, ref),
2579 btrfs_extent_data_ref_objectid(buf,
2580 ref),
2581 btrfs_extent_data_ref_offset(buf, ref),
2582 btrfs_extent_data_ref_count(buf, ref),
2583 0);
2584 continue;
2585 }
2586 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
2587 struct btrfs_shared_data_ref *ref;
2588 ref = btrfs_item_ptr(buf, i,
2589 struct btrfs_shared_data_ref);
2590 add_data_backref(extent_cache,
2591 key.objectid, key.offset, 0, 0, 0,
2592 btrfs_shared_data_ref_count(buf, ref),
2593 0);
2594 continue;
2595 }
2596 if (key.type != BTRFS_EXTENT_DATA_KEY)
2597 continue;
2598 fi = btrfs_item_ptr(buf, i,
2599 struct btrfs_file_extent_item);
2600 if (btrfs_file_extent_type(buf, fi) ==
2601 BTRFS_FILE_EXTENT_INLINE)
2602 continue;
2603 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2604 continue;
2605
2606 data_bytes_allocated +=
2607 btrfs_file_extent_disk_num_bytes(buf, fi);
2608 if (data_bytes_allocated < root->sectorsize) {
2609 abort();
2610 }
2611 data_bytes_referenced +=
2612 btrfs_file_extent_num_bytes(buf, fi);
2613 ret = add_extent_rec(extent_cache, NULL,
2614 btrfs_file_extent_disk_bytenr(buf, fi),
2615 btrfs_file_extent_disk_num_bytes(buf, fi),
2616 0, 0, 1, 1);
2617 add_data_backref(extent_cache,
2618 btrfs_file_extent_disk_bytenr(buf, fi),
2619 parent, owner, key.objectid, key.offset -
2620 btrfs_file_extent_offset(buf, fi), 1, 1);
2621 BUG_ON(ret);
2622 }
2623 } else {
2624 int level;
2625 level = btrfs_header_level(buf);
2626 for (i = 0; i < nritems; i++) {
2627 u64 ptr = btrfs_node_blockptr(buf, i);
2628 u32 size = btrfs_level_size(root, level - 1);
2629 btrfs_node_key_to_cpu(buf, &key, i);
2630 ret = add_extent_rec(extent_cache, &key,
2631 ptr, size, 0, 0, 1, 0);
2632 BUG_ON(ret);
2633
2634 add_tree_backref(extent_cache, ptr, parent,
2635 owner, 1);
2636
2637 if (level > 1) {
2638 add_pending(nodes, seen, ptr, size);
2639 } else {
2640 add_pending(pending, seen, ptr, size);
2641 }
2642 }
2643 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2644 nritems) * sizeof(struct btrfs_key_ptr);
2645 }
2646 total_btree_bytes += buf->len;
2647 if (fs_root_objectid(btrfs_header_owner(buf)))
2648 total_fs_tree_bytes += buf->len;
2649 if (!found_old_backref &&
2650 btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
2651 btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
2652 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
2653 found_old_backref = 1;
2654 free_extent_buffer(buf);
2655 return 0;
2656 }
2657
2658 static int add_root_to_pending(struct extent_buffer *buf,
2659 struct block_info *bits,
2660 int bits_nr,
2661 struct cache_tree *extent_cache,
2662 struct cache_tree *pending,
2663 struct cache_tree *seen,
2664 struct cache_tree *reada,
2665 struct cache_tree *nodes,
2666 struct btrfs_key *root_key)
2667 {
2668 if (btrfs_header_level(buf) > 0)
2669 add_pending(nodes, seen, buf->start, buf->len);
2670 else
2671 add_pending(pending, seen, buf->start, buf->len);
2672 add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2673 0, 1, 1, 0);
2674
2675 if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
2676 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2677 add_tree_backref(extent_cache, buf->start, buf->start, 0, 1);
2678 else
2679 add_tree_backref(extent_cache, buf->start, 0,
2680 root_key->objectid, 1);
2681 return 0;
2682 }
2683
2684 static int check_extent_refs(struct btrfs_root *root,
2685 struct cache_tree *extent_cache)
2686 {
2687 struct extent_record *rec;
2688 struct cache_extent *cache;
2689 int err = 0;
2690
2691 while(1) {
2692 cache = find_first_cache_extent(extent_cache, 0);
2693 if (!cache)
2694 break;
2695 rec = container_of(cache, struct extent_record, cache);
2696 if (rec->refs != rec->extent_item_refs) {
2697 fprintf(stderr, "ref mismatch on [%llu %llu] ",
2698 (unsigned long long)rec->start,
2699 (unsigned long long)rec->nr);
2700 fprintf(stderr, "extent item %llu, found %llu\n",
2701 (unsigned long long)rec->extent_item_refs,
2702 (unsigned long long)rec->refs);
2703 err = 1;
2704 }
2705 if (all_backpointers_checked(rec, 1)) {
2706 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
2707 (unsigned long long)rec->start,
2708 (unsigned long long)rec->nr);
2709
2710 err = 1;
2711 }
2712 if (!rec->owner_ref_checked) {
2713 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
2714 (unsigned long long)rec->start,
2715 (unsigned long long)rec->nr);
2716 err = 1;
2717 }
2718
2719 remove_cache_extent(extent_cache, cache);
2720 free_all_extent_backrefs(rec);
2721 free(rec);
2722 }
2723 return err;
2724 }
2725
2726 static int check_extents(struct btrfs_root *root)
2727 {
2728 struct cache_tree extent_cache;
2729 struct cache_tree seen;
2730 struct cache_tree pending;
2731 struct cache_tree reada;
2732 struct cache_tree nodes;
2733 struct btrfs_path path;
2734 struct btrfs_key key;
2735 struct btrfs_key found_key;
2736 int ret;
2737 u64 last = 0;
2738 struct block_info *bits;
2739 int bits_nr;
2740 struct extent_buffer *leaf;
2741 int slot;
2742 struct btrfs_root_item ri;
2743
2744 cache_tree_init(&extent_cache);
2745 cache_tree_init(&seen);
2746 cache_tree_init(&pending);
2747 cache_tree_init(&nodes);
2748 cache_tree_init(&reada);
2749
2750 bits_nr = 1024;
2751 bits = malloc(bits_nr * sizeof(struct block_info));
2752 if (!bits) {
2753 perror("malloc");
2754 exit(1);
2755 }
2756
2757 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2758 &extent_cache, &pending, &seen, &reada, &nodes,
2759 &root->fs_info->tree_root->root_key);
2760
2761 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2762 &extent_cache, &pending, &seen, &reada, &nodes,
2763 &root->fs_info->chunk_root->root_key);
2764
2765 btrfs_init_path(&path);
2766 key.offset = 0;
2767 key.objectid = 0;
2768 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2769 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2770 &key, &path, 0, 0);
2771 BUG_ON(ret < 0);
2772 while(1) {
2773 leaf = path.nodes[0];
2774 slot = path.slots[0];
2775 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2776 ret = btrfs_next_leaf(root, &path);
2777 if (ret != 0)
2778 break;
2779 leaf = path.nodes[0];
2780 slot = path.slots[0];
2781 }
2782 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2783 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2784 unsigned long offset;
2785 struct extent_buffer *buf;
2786
2787 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2788 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2789 buf = read_tree_block(root->fs_info->tree_root,
2790 btrfs_root_bytenr(&ri),
2791 btrfs_level_size(root,
2792 btrfs_root_level(&ri)), 0);
2793 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2794 &pending, &seen, &reada, &nodes,
2795 &found_key);
2796 free_extent_buffer(buf);
2797 }
2798 path.slots[0]++;
2799 }
2800 btrfs_release_path(root, &path);
2801 while(1) {
2802 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2803 &seen, &reada, &nodes, &extent_cache);
2804 if (ret != 0)
2805 break;
2806 }
2807 ret = check_extent_refs(root, &extent_cache);
2808 return ret;
2809 }
2810
2811 static void print_usage(void)
2812 {
2813 fprintf(stderr, "usage: btrfsck dev\n");
2814 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2815 exit(1);
2816 }
2817
2818 int main(int ac, char **av)
2819 {
2820 struct cache_tree root_cache;
2821 struct btrfs_root *root;
2822 int ret;
2823
2824 if (ac < 2)
2825 print_usage();
2826
2827 radix_tree_init();
2828 cache_tree_init(&root_cache);
2829
2830 if((ret = check_mounted(av[1])) < 0) {
2831 fprintf(stderr, "Could not check mount status: %s\n", strerror(ret));
2832 return ret;
2833 } else if(ret) {
2834 fprintf(stderr, "%s is currently mounted. Aborting.\n", av[1]);
2835 return -EBUSY;
2836 }
2837
2838 root = open_ctree(av[1], 0, 0);
2839
2840 if (root == NULL)
2841 return 1;
2842
2843 ret = check_extents(root);
2844 if (ret)
2845 goto out;
2846 ret = check_fs_roots(root, &root_cache);
2847 if (ret)
2848 goto out;
2849
2850 ret = check_root_refs(root, &root_cache);
2851 out:
2852 free_root_recs(&root_cache);
2853 close_ctree(root);
2854
2855 if (found_old_backref) {
2856 /*
2857 * there was a disk format change when mixed
2858 * backref was in testing tree. The old format
2859 * existed about one week.
2860 */
2861 printf("\n * Found old mixed backref format. "
2862 "The old format is not supported! *"
2863 "\n * Please mount the FS in readonly mode, "
2864 "backup data and re-format the FS. *\n\n");
2865 ret = 1;
2866 }
2867 printf("found %llu bytes used err is %d\n",
2868 (unsigned long long)bytes_used, ret);
2869 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2870 printf("total tree bytes: %llu\n",
2871 (unsigned long long)total_btree_bytes);
2872 printf("total fs tree bytes: %llu\n",
2873 (unsigned long long)total_fs_tree_bytes);
2874 printf("btree space waste bytes: %llu\n",
2875 (unsigned long long)btree_space_waste);
2876 printf("file data blocks allocated: %llu\n referenced %llu\n",
2877 (unsigned long long)data_bytes_allocated,
2878 (unsigned long long)data_bytes_referenced);
2879 printf("%s\n", BTRFS_BUILD_VERSION);
2880 return ret;
2881 }
Btrfs-progs-unstable mirror