?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add scan of the btrfs log tree to btrfs-debug-tree
[btrfs-progs-unstable/devel.git] / btrfsck.c
blobc5050888c9baf911e9b9d404e5b829b28e08cbd2
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 "kerncompat.h"
25 #include "ctree.h"
26 #include "disk-io.h"
27 #include "print-tree.h"
28 #include "transaction.h"
29 #include "list.h"
30 #include "version.h"
31
32 static u64 bytes_used = 0;
33 static u64 total_csum_bytes = 0;
34 static u64 total_btree_bytes = 0;
35 static u64 btree_space_waste = 0;
36 static u64 data_bytes_allocated = 0;
37 static u64 data_bytes_referenced = 0;
38
39 struct extent_backref {
40 struct list_head list;
41 u64 parent;
42 u64 root;
43 u64 generation;
44 u64 owner;
45 u32 num_refs;
46 u32 found_ref;
47 int found_extent_tree;
48 };
49
50 struct extent_record {
51 struct list_head backrefs;
52 struct cache_extent cache;
53 struct btrfs_disk_key parent_key;
54 u64 start;
55 u64 nr;
56 u32 refs;
57 u32 extent_item_refs;
58 int checked;
59 };
60
61 struct inode_backref {
62 struct list_head list;
63 unsigned int found_dir_item:1;
64 unsigned int found_dir_index:1;
65 unsigned int found_inode_ref:1;
66 unsigned int filetype:8;
67 int errors;
68 u64 dir;
69 u64 index;
70 u16 namelen;
71 char name[0];
72 };
73
74 #define REF_ERR_NO_DIR_ITEM (1 << 0)
75 #define REF_ERR_NO_DIR_INDEX (1 << 1)
76 #define REF_ERR_NO_INODE_REF (1 << 2)
77 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
78 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
79 #define REF_ERR_DUP_INODE_REF (1 << 5)
80 #define REF_ERR_INDEX_UNMATCH (1 << 6)
81 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
82 #define REF_ERR_NAME_TOO_LONG (1 << 8)
83
84 struct inode_record {
85 struct list_head backrefs;
86 unsigned int checked:1;
87 unsigned int found_inode_item:1;
88 unsigned int found_dir_item:1;
89 unsigned int found_file_extent:1;
90 unsigned int found_csum_item:1;
91 unsigned int some_csum_missing:1;
92 unsigned int nodatasum:1;
93 int errors;
94
95 u64 ino;
96 u32 nlink;
97 u32 imode;
98 u64 isize;
99 u64 nbytes;
100
101 u32 found_link;
102 u64 found_size;
103 u64 extent_start;
104 u64 extent_end;
105 u64 first_extent_gap;
106
107 u32 refs;
108 };
109
110 #define I_ERR_NO_INODE_ITEM (1 << 0)
111 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
112 #define I_ERR_DUP_INODE_ITEM (1 << 2)
113 #define I_ERR_DUP_DIR_INDEX (1 << 3)
114 #define I_ERR_ODD_DIR_ITEM (1 << 4)
115 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
116 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
117 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
118 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
119 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
120 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
121 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
122 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
123
124 struct ptr_node {
125 struct cache_extent cache;
126 void *data;
127 };
128
129 struct shared_node {
130 struct cache_extent cache;
131 struct cache_tree inode_cache;
132 struct inode_record *current;
133 u32 refs;
134 };
135
136 struct block_info {
137 u64 start;
138 u32 size;
139 };
140
141 struct walk_control {
142 struct cache_tree shared;
143 struct shared_node *nodes[BTRFS_MAX_LEVEL];
144 int active_node;
145 int root_level;
146 };
147
148 static u8 imode_to_type(u32 imode)
149 {
150 #define S_SHIFT 12
151 static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
152 [S_IFREG >> S_SHIFT] = BTRFS_FT_REG_FILE,
153 [S_IFDIR >> S_SHIFT] = BTRFS_FT_DIR,
154 [S_IFCHR >> S_SHIFT] = BTRFS_FT_CHRDEV,
155 [S_IFBLK >> S_SHIFT] = BTRFS_FT_BLKDEV,
156 [S_IFIFO >> S_SHIFT] = BTRFS_FT_FIFO,
157 [S_IFSOCK >> S_SHIFT] = BTRFS_FT_SOCK,
158 [S_IFLNK >> S_SHIFT] = BTRFS_FT_SYMLINK,
159 };
160
161 return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
162 #undef S_SHIFT
163 }
164
165 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
166 {
167 struct inode_record *rec;
168 struct inode_backref *backref;
169 struct inode_backref *orig;
170 size_t size;
171
172 rec = malloc(sizeof(*rec));
173 memcpy(rec, orig_rec, sizeof(*rec));
174 rec->refs = 1;
175 INIT_LIST_HEAD(&rec->backrefs);
176
177 list_for_each_entry(orig, &orig_rec->backrefs, list) {
178 size = sizeof(*orig) + orig->namelen + 1;
179 backref = malloc(size);
180 memcpy(backref, orig, size);
181 list_add_tail(&backref->list, &rec->backrefs);
182 }
183 return rec;
184 }
185
186 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
187 u64 ino, int mod)
188 {
189 struct ptr_node *node;
190 struct cache_extent *cache;
191 struct inode_record *rec = NULL;
192 int ret;
193
194 cache = find_cache_extent(inode_cache, ino, 1);
195 if (cache) {
196 node = container_of(cache, struct ptr_node, cache);
197 rec = node->data;
198 if (mod && rec->refs > 1) {
199 node->data = clone_inode_rec(rec);
200 rec->refs--;
201 rec = node->data;
202 }
203 } else if (mod) {
204 rec = calloc(1, sizeof(*rec));
205 rec->ino = ino;
206 rec->extent_start = (u64)-1;
207 rec->first_extent_gap = (u64)-1;
208 rec->refs = 1;
209 INIT_LIST_HEAD(&rec->backrefs);
210
211 node = malloc(sizeof(*node));
212 node->cache.start = ino;
213 node->cache.size = 1;
214 node->data = rec;
215
216 ret = insert_existing_cache_extent(inode_cache, &node->cache);
217 BUG_ON(ret);
218 }
219 return rec;
220 }
221
222 static void free_inode_rec(struct inode_record *rec)
223 {
224 struct inode_backref *backref;
225
226 if (--rec->refs > 0)
227 return;
228
229 while (!list_empty(&rec->backrefs)) {
230 backref = list_entry(rec->backrefs.next,
231 struct inode_backref, list);
232 list_del(&backref->list);
233 free(backref);
234 }
235 free(rec);
236 }
237
238 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
239 struct inode_record *rec)
240 {
241 struct cache_extent *cache;
242 struct inode_backref *tmp, *backref;
243 struct ptr_node *node;
244 unsigned char filetype;
245
246 if (!rec->found_inode_item)
247 return;
248
249 filetype = imode_to_type(rec->imode);
250 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
251 if (backref->found_dir_item && backref->found_dir_index) {
252 if (backref->filetype != filetype)
253 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
254 if (!backref->errors && backref->found_inode_ref) {
255 list_del(&backref->list);
256 free(backref);
257 }
258 }
259 }
260
261 if (!rec->checked)
262 return;
263
264 if (S_ISDIR(rec->imode)) {
265 if (rec->found_size != rec->isize)
266 rec->errors |= I_ERR_DIR_ISIZE_WRONG;
267 if (rec->found_file_extent)
268 rec->errors |= I_ERR_ODD_FILE_EXTENT;
269 } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
270 if (rec->found_dir_item)
271 rec->errors |= I_ERR_ODD_DIR_ITEM;
272 if (rec->found_size != rec->nbytes)
273 rec->errors |= I_ERR_FILE_NBYTES_WRONG;
274 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
275 rec->first_extent_gap = 0;
276 if (rec->nlink > 0 && (rec->extent_end < rec->isize ||
277 rec->first_extent_gap < rec->isize))
278 rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
279 }
280
281 if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
282 if (rec->found_csum_item && rec->nodatasum)
283 rec->errors |= I_ERR_ODD_CSUM_ITEM;
284 if (rec->some_csum_missing && !rec->nodatasum)
285 rec->errors |= I_ERR_SOME_CSUM_MISSING;
286 }
287
288 BUG_ON(rec->refs != 1);
289 if (!rec->errors && rec->nlink == rec->found_link &&
290 list_empty(&rec->backrefs)) {
291 cache = find_cache_extent(inode_cache, rec->ino, 1);
292 node = container_of(cache, struct ptr_node, cache);
293 BUG_ON(node->data != rec);
294 remove_cache_extent(inode_cache, &node->cache);
295 free(node);
296 free_inode_rec(rec);
297 }
298 }
299
300 static int check_orphan_item(struct btrfs_root *root, u64 ino)
301 {
302 struct btrfs_path path;
303 struct btrfs_key key;
304 int ret;
305
306 key.objectid = BTRFS_ORPHAN_OBJECTID;
307 key.type = BTRFS_ORPHAN_ITEM_KEY;
308 key.offset = ino;
309
310 btrfs_init_path(&path);
311 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
312 btrfs_release_path(root, &path);
313 if (ret > 0)
314 ret = -ENOENT;
315 return ret;
316 }
317
318 static int process_inode_item(struct btrfs_root *root,
319 struct extent_buffer *eb,
320 int slot, struct btrfs_key *key,
321 struct shared_node *active_node)
322 {
323 struct inode_record *rec;
324 struct btrfs_inode_item *item;
325 int ret;
326
327 rec = active_node->current;
328 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
329 if (rec->found_inode_item) {
330 rec->errors |= I_ERR_DUP_INODE_ITEM;
331 return 1;
332 }
333 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
334 rec->nlink = btrfs_inode_nlink(eb, item);
335 rec->isize = btrfs_inode_size(eb, item);
336 rec->nbytes = btrfs_inode_nbytes(eb, item);
337 rec->imode = btrfs_inode_mode(eb, item);
338 if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
339 rec->nodatasum = 1;
340 rec->found_inode_item = 1;
341 if (rec->nlink == 0) {
342 ret = check_orphan_item(root, rec->ino);
343 if (ret == -ENOENT)
344 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
345 }
346 maybe_free_inode_rec(&active_node->inode_cache, rec);
347 return 0;
348 }
349
350 static struct inode_backref *get_inode_backref(struct inode_record *rec,
351 const char *name,
352 int namelen, u64 dir)
353 {
354 struct inode_backref *backref;
355
356 list_for_each_entry(backref, &rec->backrefs, list) {
357 if (backref->dir != dir || backref->namelen != namelen)
358 continue;
359 if (memcmp(name, backref->name, namelen))
360 continue;
361 return backref;
362 }
363
364 backref = malloc(sizeof(*backref) + namelen + 1);
365 memset(backref, 0, sizeof(*backref));
366 backref->dir = dir;
367 backref->namelen = namelen;
368 memcpy(backref->name, name, namelen);
369 backref->name[namelen] = '\0';
370 list_add_tail(&backref->list, &rec->backrefs);
371 rec->found_link++;
372 return backref;
373 }
374
375 static int add_inode_backref(struct cache_tree *inode_cache,
376 u64 ino, u64 dir, u64 index,
377 const char *name, int namelen,
378 int filetype, int itemtype, int errors)
379 {
380 struct inode_record *rec;
381 struct inode_backref *backref;
382
383 rec = get_inode_rec(inode_cache, ino, 1);
384 backref = get_inode_backref(rec, name, namelen, dir);
385 if (errors)
386 backref->errors |= errors;
387 if (itemtype == BTRFS_DIR_INDEX_KEY) {
388 if (backref->found_dir_index)
389 backref->errors |= REF_ERR_DUP_DIR_INDEX;
390 if (backref->found_inode_ref && backref->index != index)
391 backref->errors |= REF_ERR_INDEX_UNMATCH;
392 if (backref->found_dir_item && backref->filetype != filetype)
393 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
394
395 backref->index = index;
396 backref->filetype = filetype;
397 backref->found_dir_index = 1;
398 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
399 if (backref->found_dir_item)
400 backref->errors |= REF_ERR_DUP_DIR_ITEM;
401 if (backref->found_dir_index && backref->filetype != filetype)
402 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
403
404 backref->filetype = filetype;
405 backref->found_dir_item = 1;
406 } else if (itemtype == BTRFS_INODE_REF_KEY) {
407 if (backref->found_inode_ref)
408 backref->errors |= REF_ERR_DUP_INODE_REF;
409 if (backref->found_dir_index && backref->index != index)
410 backref->errors |= REF_ERR_INDEX_UNMATCH;
411
412 backref->index = index;
413 backref->found_inode_ref = 1;
414 } else {
415 BUG_ON(1);
416 }
417
418 maybe_free_inode_rec(inode_cache, rec);
419 return 0;
420 }
421
422 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
423 struct shared_node *dst_node)
424 {
425 struct inode_backref *backref;
426 struct cache_tree *dst_cache = &dst_node->inode_cache;
427
428 list_for_each_entry(backref, &src->backrefs, list) {
429 if (backref->found_dir_index) {
430 add_inode_backref(dst_cache, dst->ino, backref->dir,
431 backref->index, backref->name,
432 backref->namelen, backref->filetype,
433 BTRFS_DIR_INDEX_KEY, backref->errors);
434 }
435 if (backref->found_dir_item) {
436 add_inode_backref(dst_cache, dst->ino,
437 backref->dir, 0, backref->name,
438 backref->namelen, backref->filetype,
439 BTRFS_DIR_ITEM_KEY, backref->errors);
440 }
441 if (backref->found_inode_ref) {
442 add_inode_backref(dst_cache, dst->ino,
443 backref->dir, backref->index,
444 backref->name, backref->namelen, 0,
445 BTRFS_INODE_REF_KEY, backref->errors);
446 }
447 }
448
449 if (src->found_dir_item)
450 dst->found_dir_item = 1;
451 if (src->found_file_extent)
452 dst->found_file_extent = 1;
453 if (src->found_csum_item)
454 dst->found_csum_item = 1;
455 if (src->some_csum_missing)
456 dst->some_csum_missing = 1;
457 if (dst->first_extent_gap > src->first_extent_gap)
458 dst->first_extent_gap = src->first_extent_gap;
459
460 dst->found_size += src->found_size;
461 if (src->extent_start != (u64)-1) {
462 if (dst->extent_start == (u64)-1) {
463 dst->extent_start = src->extent_start;
464 dst->extent_end = src->extent_end;
465 } else {
466 if (dst->extent_end > src->extent_start)
467 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
468 else if (dst->extent_end < src->extent_start &&
469 dst->extent_end < dst->first_extent_gap)
470 dst->first_extent_gap = dst->extent_end;
471 if (dst->extent_end < src->extent_end)
472 dst->extent_end = src->extent_end;
473 }
474 }
475
476 dst->errors |= src->errors;
477 if (src->found_inode_item) {
478 if (!dst->found_inode_item) {
479 dst->nlink = src->nlink;
480 dst->isize = src->isize;
481 dst->nbytes = src->nbytes;
482 dst->imode = src->imode;
483 dst->nodatasum = src->nodatasum;
484 dst->found_inode_item = 1;
485 } else {
486 dst->errors |= I_ERR_DUP_INODE_ITEM;
487 }
488 }
489
490 if (src->checked) {
491 dst->checked = 1;
492 if (dst_node->current == dst)
493 dst_node->current = NULL;
494 }
495 maybe_free_inode_rec(dst_cache, dst);
496 return 0;
497 }
498
499 static int splice_shared_node(struct shared_node *src_node,
500 struct shared_node *dst_node)
501 {
502 struct cache_extent *cache;
503 struct ptr_node *node, *ins;
504 struct cache_tree *src, *dst;
505 struct inode_record *rec, *conflict;
506 u64 current_ino = 0;
507 int splice = 0;
508 int ret;
509
510 if (--src_node->refs == 0)
511 splice = 1;
512 if (src_node->current)
513 current_ino = src_node->current->ino;
514
515 src = &src_node->inode_cache;
516 dst = &dst_node->inode_cache;
517 cache = find_first_cache_extent(src, 0);
518 while (cache) {
519 node = container_of(cache, struct ptr_node, cache);
520 rec = node->data;
521 cache = next_cache_extent(cache);
522
523 if (splice) {
524 remove_cache_extent(src, &node->cache);
525 ins = node;
526 } else {
527 ins = malloc(sizeof(*ins));
528 ins->cache.start = node->cache.start;
529 ins->cache.size = node->cache.size;
530 ins->data = rec;
531 rec->refs++;
532 }
533 ret = insert_existing_cache_extent(dst, &ins->cache);
534 if (ret == -EEXIST) {
535 conflict = get_inode_rec(dst, rec->ino, 1);
536 merge_inode_recs(rec, conflict, dst_node);
537 free_inode_rec(rec);
538 free(ins);
539 } else {
540 BUG_ON(ret);
541 }
542 }
543 if (current_ino > 0 && (!dst_node->current ||
544 current_ino > dst_node->current->ino)) {
545 if (dst_node->current) {
546 dst_node->current->checked = 1;
547 maybe_free_inode_rec(dst, dst_node->current);
548 }
549 dst_node->current = get_inode_rec(dst, current_ino, 1);
550 }
551 return 0;
552 }
553
554 static void free_inode_recs(struct cache_tree *inode_cache)
555 {
556 struct cache_extent *cache;
557 struct ptr_node *node;
558 struct inode_record *rec;
559
560 while (1) {
561 cache = find_first_cache_extent(inode_cache, 0);
562 if (!cache)
563 break;
564 node = container_of(cache, struct ptr_node, cache);
565 rec = node->data;
566 remove_cache_extent(inode_cache, &node->cache);
567 free(node);
568 free_inode_rec(rec);
569 }
570 }
571
572 static struct shared_node *find_shared_node(struct cache_tree *shared,
573 u64 bytenr)
574 {
575 struct cache_extent *cache;
576 struct shared_node *node;
577
578 cache = find_cache_extent(shared, bytenr, 1);
579 if (cache) {
580 node = container_of(cache, struct shared_node, cache);
581 return node;
582 }
583 return NULL;
584 }
585
586 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
587 {
588 int ret;
589 struct shared_node *node;
590
591 node = calloc(1, sizeof(*node));
592 node->cache.start = bytenr;
593 node->cache.size = 1;
594 cache_tree_init(&node->inode_cache);
595 node->refs = refs;
596
597 ret = insert_existing_cache_extent(shared, &node->cache);
598 BUG_ON(ret);
599 return 0;
600 }
601
602 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
603 struct walk_control *wc, int level)
604 {
605 struct shared_node *node;
606 struct shared_node *dest;
607
608 if (level == wc->active_node)
609 return 0;
610
611 BUG_ON(wc->active_node <= level);
612 node = find_shared_node(&wc->shared, bytenr);
613 if (!node) {
614 add_shared_node(&wc->shared, bytenr, refs);
615 node = find_shared_node(&wc->shared, bytenr);
616 wc->nodes[level] = node;
617 wc->active_node = level;
618 return 0;
619 }
620
621 if (wc->root_level == wc->active_node &&
622 btrfs_root_refs(&root->root_item) == 0) {
623 if (--node->refs == 0) {
624 free_inode_recs(&node->inode_cache);
625 remove_cache_extent(&wc->shared, &node->cache);
626 free(node);
627 }
628 return 1;
629 }
630
631 dest = wc->nodes[wc->active_node];
632 splice_shared_node(node, dest);
633 if (node->refs == 0) {
634 remove_cache_extent(&wc->shared, &node->cache);
635 free(node);
636 }
637 return 1;
638 }
639
640 static int leave_shared_node(struct btrfs_root *root,
641 struct walk_control *wc, int level)
642 {
643 struct shared_node *node;
644 struct shared_node *dest;
645 int i;
646
647 if (level == wc->root_level)
648 return 0;
649
650 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
651 if (wc->nodes[i])
652 break;
653 }
654 BUG_ON(i >= BTRFS_MAX_LEVEL);
655
656 node = wc->nodes[wc->active_node];
657 wc->nodes[wc->active_node] = NULL;
658 wc->active_node = i;
659
660 dest = wc->nodes[wc->active_node];
661 if (wc->active_node < wc->root_level ||
662 btrfs_root_refs(&root->root_item) > 0) {
663 BUG_ON(node->refs <= 1);
664 splice_shared_node(node, dest);
665 } else {
666 BUG_ON(node->refs < 2);
667 node->refs--;
668 }
669 return 0;
670 }
671
672 static int process_dir_item(struct extent_buffer *eb,
673 int slot, struct btrfs_key *key,
674 struct shared_node *active_node)
675 {
676 u32 total;
677 u32 cur = 0;
678 u32 len;
679 u32 name_len;
680 u32 data_len;
681 int error;
682 int nritems = 0;
683 int filetype;
684 struct btrfs_dir_item *di;
685 struct inode_record *rec;
686 struct cache_tree *inode_cache;
687 struct btrfs_key location;
688 char namebuf[BTRFS_NAME_LEN];
689
690 inode_cache = &active_node->inode_cache;
691 rec = active_node->current;
692 rec->found_dir_item = 1;
693
694 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
695 total = btrfs_item_size_nr(eb, slot);
696 while (cur < total) {
697 nritems++;
698 btrfs_dir_item_key_to_cpu(eb, di, &location);
699 name_len = btrfs_dir_name_len(eb, di);
700 data_len = btrfs_dir_data_len(eb, di);
701 filetype = btrfs_dir_type(eb, di);
702
703 rec->found_size += name_len;
704 if (name_len <= BTRFS_NAME_LEN) {
705 len = name_len;
706 error = 0;
707 } else {
708 len = BTRFS_NAME_LEN;
709 error = REF_ERR_NAME_TOO_LONG;
710 }
711 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
712
713 if (location.type == BTRFS_INODE_ITEM_KEY) {
714 add_inode_backref(inode_cache, location.objectid,
715 key->objectid, key->offset, namebuf,
716 len, filetype, key->type, error);
717 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
718 /* fixme: check root back & forward references */
719 } else {
720 fprintf(stderr, "warning line %d\n", __LINE__);
721 }
722
723 len = sizeof(*di) + name_len + data_len;
724 di = (struct btrfs_dir_item *)((char *)di + len);
725 cur += len;
726 }
727 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
728 rec->errors |= I_ERR_DUP_DIR_INDEX;
729
730 return 0;
731 }
732
733 static int process_inode_ref(struct extent_buffer *eb,
734 int slot, struct btrfs_key *key,
735 struct shared_node *active_node)
736 {
737 u32 total;
738 u32 cur = 0;
739 u32 len;
740 u32 name_len;
741 u64 index;
742 int error;
743 struct cache_tree *inode_cache;
744 struct btrfs_inode_ref *ref;
745 char namebuf[BTRFS_NAME_LEN];
746
747 inode_cache = &active_node->inode_cache;
748
749 ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
750 total = btrfs_item_size_nr(eb, slot);
751 while (cur < total) {
752 name_len = btrfs_inode_ref_name_len(eb, ref);
753 index = btrfs_inode_ref_index(eb, ref);
754 if (name_len <= BTRFS_NAME_LEN) {
755 len = name_len;
756 error = 0;
757 } else {
758 len = BTRFS_NAME_LEN;
759 error = REF_ERR_NAME_TOO_LONG;
760 }
761 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
762 add_inode_backref(inode_cache, key->objectid, key->offset,
763 index, namebuf, len, 0, key->type, error);
764
765 len = sizeof(*ref) + name_len;
766 ref = (struct btrfs_inode_ref *)((char *)ref + len);
767 cur += len;
768 }
769 return 0;
770 }
771
772 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
773 {
774 struct btrfs_key key;
775 struct btrfs_path path;
776 struct extent_buffer *leaf;
777 int ret ;
778 size_t size;
779 u64 found = 0;
780 u64 csum_end;
781 u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
782
783 btrfs_init_path(&path);
784
785 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
786 key.offset = start;
787 key.type = BTRFS_EXTENT_CSUM_KEY;
788
789 ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
790 &key, &path, 0, 0);
791 BUG_ON(ret < 0);
792 if (ret > 0 && path.slots[0] > 0) {
793 leaf = path.nodes[0];
794 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
795 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
796 key.type == BTRFS_EXTENT_CSUM_KEY)
797 path.slots[0]--;
798 }
799
800 while (len > 0) {
801 leaf = path.nodes[0];
802 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
803 ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
804 BUG_ON(ret < 0);
805 if (ret > 0)
806 break;
807 leaf = path.nodes[0];
808 }
809
810 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
811 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
812 key.type != BTRFS_EXTENT_CSUM_KEY)
813 break;
814
815 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
816 if (key.offset >= start + len)
817 break;
818
819 if (key.offset > start)
820 start = key.offset;
821
822 size = btrfs_item_size_nr(leaf, path.slots[0]);
823 csum_end = key.offset + (size / csum_size) * root->sectorsize;
824 if (csum_end > start) {
825 size = min(csum_end - start, len);
826 len -= size;
827 start += size;
828 found += size;
829 }
830
831 path.slots[0]++;
832 }
833 btrfs_release_path(root->fs_info->csum_root, &path);
834 return found;
835 }
836
837 static int process_file_extent(struct btrfs_root *root,
838 struct extent_buffer *eb,
839 int slot, struct btrfs_key *key,
840 struct shared_node *active_node)
841 {
842 struct inode_record *rec;
843 struct btrfs_file_extent_item *fi;
844 u64 num_bytes = 0;
845 u64 disk_bytenr = 0;
846 u64 extent_offset = 0;
847 u64 mask = root->sectorsize - 1;
848 int extent_type;
849
850 rec = active_node->current;
851 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
852 rec->found_file_extent = 1;
853
854 if (rec->extent_start == (u64)-1) {
855 rec->extent_start = key->offset;
856 rec->extent_end = key->offset;
857 }
858
859 if (rec->extent_end > key->offset)
860 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
861 else if (rec->extent_end < key->offset &&
862 rec->extent_end < rec->first_extent_gap)
863 rec->first_extent_gap = rec->extent_end;
864
865 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
866 extent_type = btrfs_file_extent_type(eb, fi);
867
868 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
869 num_bytes = btrfs_file_extent_inline_len(eb, fi);
870 if (num_bytes == 0)
871 rec->errors |= I_ERR_BAD_FILE_EXTENT;
872 rec->found_size += num_bytes;
873 num_bytes = (num_bytes + mask) & ~mask;
874 } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
875 extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
876 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
877 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
878 extent_offset = btrfs_file_extent_offset(eb, fi);
879 if (num_bytes == 0 || (num_bytes & mask))
880 rec->errors |= I_ERR_BAD_FILE_EXTENT;
881 if (num_bytes + extent_offset >
882 btrfs_file_extent_ram_bytes(eb, fi))
883 rec->errors |= I_ERR_BAD_FILE_EXTENT;
884 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
885 (btrfs_file_extent_compression(eb, fi) ||
886 btrfs_file_extent_encryption(eb, fi) ||
887 btrfs_file_extent_other_encoding(eb, fi)))
888 rec->errors |= I_ERR_BAD_FILE_EXTENT;
889 if (disk_bytenr > 0)
890 rec->found_size += num_bytes;
891 } else {
892 rec->errors |= I_ERR_BAD_FILE_EXTENT;
893 }
894 rec->extent_end = key->offset + num_bytes;
895
896 if (disk_bytenr > 0) {
897 u64 found;
898 if (btrfs_file_extent_compression(eb, fi))
899 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
900 else
901 disk_bytenr += extent_offset;
902
903 found = count_csum_range(root, disk_bytenr, num_bytes);
904 if (extent_type == BTRFS_FILE_EXTENT_REG) {
905 if (found > 0)
906 rec->found_csum_item = 1;
907 if (found < num_bytes)
908 rec->some_csum_missing = 1;
909 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
910 if (found > 0)
911 rec->errors |= I_ERR_ODD_CSUM_ITEM;
912 }
913 }
914 return 0;
915 }
916
917 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
918 struct walk_control *wc)
919 {
920 struct btrfs_key key;
921 u32 nritems;
922 int i;
923 int ret;
924 struct cache_tree *inode_cache;
925 struct shared_node *active_node;
926
927 if (wc->root_level == wc->active_node &&
928 btrfs_root_refs(&root->root_item) == 0)
929 return 0;
930
931 active_node = wc->nodes[wc->active_node];
932 inode_cache = &active_node->inode_cache;
933 nritems = btrfs_header_nritems(eb);
934 for (i = 0; i < nritems; i++) {
935 btrfs_item_key_to_cpu(eb, &key, i);
936 if (active_node->current == NULL ||
937 active_node->current->ino < key.objectid) {
938 if (active_node->current) {
939 active_node->current->checked = 1;
940 maybe_free_inode_rec(inode_cache,
941 active_node->current);
942 }
943 active_node->current = get_inode_rec(inode_cache,
944 key.objectid, 1);
945 }
946 switch (key.type) {
947 case BTRFS_DIR_ITEM_KEY:
948 case BTRFS_DIR_INDEX_KEY:
949 ret = process_dir_item(eb, i, &key, active_node);
950 break;
951 case BTRFS_INODE_REF_KEY:
952 ret = process_inode_ref(eb, i, &key, active_node);
953 break;
954 case BTRFS_INODE_ITEM_KEY:
955 ret = process_inode_item(root, eb, i, &key,
956 active_node);
957 break;
958 case BTRFS_EXTENT_DATA_KEY:
959 ret = process_file_extent(root, eb, i, &key,
960 active_node);
961 break;
962 default:
963 break;
964 };
965 }
966 return 0;
967 }
968
969 static void reada_walk_down(struct btrfs_root *root,
970 struct extent_buffer *node, int slot)
971 {
972 u64 bytenr;
973 u64 ptr_gen;
974 u32 nritems;
975 u32 blocksize;
976 int i;
977 int ret;
978 int level;
979
980 level = btrfs_header_level(node);
981 if (level != 1)
982 return;
983
984 nritems = btrfs_header_nritems(node);
985 blocksize = btrfs_level_size(root, level - 1);
986 for (i = slot; i < nritems; i++) {
987 bytenr = btrfs_node_blockptr(node, i);
988 ptr_gen = btrfs_node_ptr_generation(node, i);
989 ret = readahead_tree_block(root, bytenr, blocksize, ptr_gen);
990 if (ret)
991 break;
992 }
993 }
994
995 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
996 struct walk_control *wc, int *level)
997 {
998 u64 bytenr;
999 u64 ptr_gen;
1000 struct extent_buffer *next;
1001 struct extent_buffer *cur;
1002 u32 blocksize;
1003 int ret;
1004 u32 refs;
1005
1006 WARN_ON(*level < 0);
1007 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1008 ret = btrfs_lookup_extent_ref(NULL, root,
1009 path->nodes[*level]->start,
1010 path->nodes[*level]->len, &refs);
1011 BUG_ON(ret);
1012 if (refs > 1) {
1013 ret = enter_shared_node(root, path->nodes[*level]->start,
1014 refs, wc, *level);
1015 if (ret > 0)
1016 goto out;
1017 }
1018
1019 while (*level >= 0) {
1020 WARN_ON(*level < 0);
1021 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1022 cur = path->nodes[*level];
1023
1024 if (btrfs_header_level(cur) != *level)
1025 WARN_ON(1);
1026
1027 if (path->slots[*level] >= btrfs_header_nritems(cur))
1028 break;
1029 if (*level == 0) {
1030 ret = process_one_leaf(root, cur, wc);
1031 break;
1032 }
1033 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1034 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1035 blocksize = btrfs_level_size(root, *level - 1);
1036 ret = btrfs_lookup_extent_ref(NULL, root, bytenr, blocksize,
1037 &refs);
1038 BUG_ON(ret);
1039
1040 if (refs > 1) {
1041 ret = enter_shared_node(root, bytenr, refs,
1042 wc, *level - 1);
1043 if (ret > 0) {
1044 path->slots[*level]++;
1045 continue;
1046 }
1047 }
1048
1049 next = btrfs_find_tree_block(root, bytenr, blocksize);
1050 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1051 free_extent_buffer(next);
1052 reada_walk_down(root, cur, path->slots[*level]);
1053 next = read_tree_block(root, bytenr, blocksize,
1054 ptr_gen);
1055 }
1056
1057 *level = *level - 1;
1058 free_extent_buffer(path->nodes[*level]);
1059 path->nodes[*level] = next;
1060 path->slots[*level] = 0;
1061 }
1062 out:
1063 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1064 return 0;
1065 }
1066
1067 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1068 struct walk_control *wc, int *level)
1069 {
1070 int i;
1071 struct extent_buffer *leaf;
1072
1073 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1074 leaf = path->nodes[i];
1075 if (path->slots[i] < btrfs_header_nritems(leaf) - 1) {
1076 path->slots[i]++;
1077 *level = i;
1078 return 0;
1079 } else {
1080 free_extent_buffer(path->nodes[*level]);
1081 path->nodes[*level] = NULL;
1082 BUG_ON(*level > wc->active_node);
1083 if (*level == wc->active_node)
1084 leave_shared_node(root, wc, *level);
1085 *level = i + 1;
1086 }
1087 }
1088 return 1;
1089 }
1090
1091 static int check_root_dir(struct inode_record *rec)
1092 {
1093 struct inode_backref *backref;
1094 int ret = -1;
1095
1096 if (!rec->found_inode_item || rec->errors)
1097 goto out;
1098 if (rec->nlink != 1 || rec->found_link != 1)
1099 goto out;
1100 if (list_empty(&rec->backrefs))
1101 goto out;
1102 backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1103 if (!backref->found_inode_ref)
1104 goto out;
1105 if (backref->index != 0 || backref->namelen != 2 ||
1106 memcmp(backref->name, "..", 2))
1107 goto out;
1108 if (backref->found_dir_index || backref->found_dir_item)
1109 goto out;
1110 ret = 0;
1111 out:
1112 return ret;
1113 }
1114
1115 static int check_inode_recs(struct btrfs_root *root,
1116 struct cache_tree *inode_cache)
1117 {
1118 struct cache_extent *cache;
1119 struct ptr_node *node;
1120 struct inode_record *rec;
1121 struct inode_backref *backref;
1122 int ret;
1123 u64 error = 0;
1124 u64 root_dirid = btrfs_root_dirid(&root->root_item);
1125
1126 if (btrfs_root_refs(&root->root_item) == 0) {
1127 if (!cache_tree_empty(inode_cache))
1128 fprintf(stderr, "warning line %d\n", __LINE__);
1129 return 0;
1130 }
1131
1132 rec = get_inode_rec(inode_cache, root_dirid, 0);
1133 if (rec) {
1134 ret = check_root_dir(rec);
1135 if (ret) {
1136 fprintf(stderr, "root %llu root dir %llu error\n",
1137 root->root_key.objectid, root_dirid);
1138 error++;
1139 }
1140 } else {
1141 fprintf(stderr, "root %llu root dir %llu not found\n",
1142 root->root_key.objectid, root_dirid);
1143 }
1144
1145 while (1) {
1146 cache = find_first_cache_extent(inode_cache, 0);
1147 if (!cache)
1148 break;
1149 node = container_of(cache, struct ptr_node, cache);
1150 rec = node->data;
1151 remove_cache_extent(inode_cache, &node->cache);
1152 if (rec->ino == root_dirid ||
1153 rec->ino == BTRFS_ORPHAN_OBJECTID) {
1154 free(node);
1155 free_inode_rec(rec);
1156 continue;
1157 }
1158
1159 error++;
1160 if (!rec->found_inode_item)
1161 rec->errors |= I_ERR_NO_INODE_ITEM;
1162 fprintf(stderr, "root %llu inode %llu errors %x\n",
1163 root->root_key.objectid, rec->ino, rec->errors);
1164 list_for_each_entry(backref, &rec->backrefs, list) {
1165 if (!backref->found_dir_item)
1166 backref->errors |= REF_ERR_NO_DIR_ITEM;
1167 if (!backref->found_dir_index)
1168 backref->errors |= REF_ERR_NO_DIR_INDEX;
1169 if (!backref->found_inode_ref)
1170 backref->errors |= REF_ERR_NO_INODE_REF;
1171 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1172 " namelen %u name %s filetype %d error %x\n",
1173 backref->dir, backref->index,
1174 backref->namelen, backref->name,
1175 backref->filetype, backref->errors);
1176 }
1177 free(node);
1178 free_inode_rec(rec);
1179 }
1180 return (error > 0) ? -1 : 0;
1181 }
1182
1183 static int check_fs_root(struct btrfs_root *root,
1184 struct walk_control *wc)
1185 {
1186 int ret = 0;
1187 int wret;
1188 int level;
1189 struct btrfs_path path;
1190 struct shared_node root_node;
1191 struct btrfs_root_item *root_item = &root->root_item;
1192
1193 btrfs_init_path(&path);
1194 memset(&root_node, 0, sizeof(root_node));
1195 cache_tree_init(&root_node.inode_cache);
1196
1197 level = btrfs_header_level(root->node);
1198 memset(wc->nodes, 0, sizeof(wc->nodes));
1199 wc->nodes[level] = &root_node;
1200 wc->active_node = level;
1201 wc->root_level = level;
1202
1203 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1204 path.nodes[level] = root->node;
1205 extent_buffer_get(root->node);
1206 path.slots[level] = 0;
1207 } else {
1208 struct btrfs_key key;
1209 struct btrfs_disk_key found_key;
1210
1211 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1212 level = root_item->drop_level;
1213 path.lowest_level = level;
1214 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1215 BUG_ON(wret < 0);
1216 btrfs_node_key(path.nodes[level], &found_key,
1217 path.slots[level]);
1218 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1219 sizeof(found_key)));
1220 }
1221
1222 while (1) {
1223 wret = walk_down_tree(root, &path, wc, &level);
1224 if (wret < 0)
1225 ret = wret;
1226 if (wret != 0)
1227 break;
1228
1229 wret = walk_up_tree(root, &path, wc, &level);
1230 if (wret < 0)
1231 ret = wret;
1232 if (wret != 0)
1233 break;
1234 }
1235 btrfs_release_path(root, &path);
1236
1237 if (root_node.current) {
1238 root_node.current->checked = 1;
1239 maybe_free_inode_rec(&root_node.inode_cache,
1240 root_node.current);
1241 }
1242
1243 ret = check_inode_recs(root, &root_node.inode_cache);
1244 return ret;
1245 }
1246
1247 static int fs_root_objectid(u64 objectid)
1248 {
1249 if (objectid == BTRFS_FS_TREE_OBJECTID ||
1250 objectid == BTRFS_TREE_RELOC_OBJECTID ||
1251 (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1252 objectid < BTRFS_LAST_FREE_OBJECTID))
1253 return 1;
1254 return 0;
1255 }
1256
1257 static int check_fs_roots(struct btrfs_root *root)
1258 {
1259 struct btrfs_path path;
1260 struct btrfs_key key;
1261 struct walk_control wc;
1262 struct extent_buffer *leaf;
1263 struct btrfs_root *tmp_root;
1264 struct btrfs_root *tree_root = root->fs_info->tree_root;
1265 int ret;
1266 int err = 0;
1267
1268 memset(&wc, 0, sizeof(wc));
1269 cache_tree_init(&wc.shared);
1270 btrfs_init_path(&path);
1271
1272 key.offset = 0;
1273 key.objectid = 0;
1274 key.type = BTRFS_ROOT_ITEM_KEY;
1275 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1276 BUG_ON(ret < 0);
1277 while (1) {
1278 leaf = path.nodes[0];
1279 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1280 ret = btrfs_next_leaf(tree_root, &path);
1281 if (ret != 0)
1282 break;
1283 leaf = path.nodes[0];
1284 }
1285 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1286 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1287 fs_root_objectid(key.objectid)) {
1288 tmp_root = btrfs_read_fs_root(root->fs_info, &key);
1289 ret = check_fs_root(tmp_root, &wc);
1290 if (ret)
1291 err = 1;
1292 btrfs_free_fs_root(root->fs_info, tmp_root);
1293 }
1294 path.slots[0]++;
1295 }
1296 btrfs_release_path(tree_root, &path);
1297
1298 if (!cache_tree_empty(&wc.shared))
1299 fprintf(stderr, "warning line %d\n", __LINE__);
1300
1301 return err;
1302 }
1303
1304 static int check_node(struct btrfs_root *root,
1305 struct btrfs_disk_key *parent_key,
1306 struct extent_buffer *buf)
1307 {
1308 int i;
1309 struct btrfs_key cpukey;
1310 struct btrfs_disk_key key;
1311 u32 nritems = btrfs_header_nritems(buf);
1312
1313 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1314 return 1;
1315 if (parent_key->type) {
1316 btrfs_node_key(buf, &key, 0);
1317 if (memcmp(parent_key, &key, sizeof(key)))
1318 return 1;
1319 }
1320 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1321 btrfs_node_key(buf, &key, i);
1322 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
1323 if (btrfs_comp_keys(&key, &cpukey) >= 0)
1324 return 1;
1325 }
1326 return 0;
1327 }
1328
1329 static int check_leaf(struct btrfs_root *root,
1330 struct btrfs_disk_key *parent_key,
1331 struct extent_buffer *buf)
1332 {
1333 int i;
1334 struct btrfs_key cpukey;
1335 struct btrfs_disk_key key;
1336 u32 nritems = btrfs_header_nritems(buf);
1337
1338 if (btrfs_header_level(buf) != 0) {
1339 fprintf(stderr, "leaf is not a leaf %llu\n",
1340 (unsigned long long)btrfs_header_bytenr(buf));
1341 return 1;
1342 }
1343 if (btrfs_leaf_free_space(root, buf) < 0) {
1344 fprintf(stderr, "leaf free space incorrect %llu %d\n",
1345 (unsigned long long)btrfs_header_bytenr(buf),
1346 btrfs_leaf_free_space(root, buf));
1347 return 1;
1348 }
1349
1350 if (nritems == 0)
1351 return 0;
1352
1353 btrfs_item_key(buf, &key, 0);
1354 if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
1355 fprintf(stderr, "leaf parent key incorrect %llu\n",
1356 (unsigned long long)btrfs_header_bytenr(buf));
1357 return 1;
1358 }
1359 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1360 btrfs_item_key(buf, &key, i);
1361 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
1362 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
1363 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
1364 return 1;
1365 }
1366 if (btrfs_item_offset_nr(buf, i) !=
1367 btrfs_item_end_nr(buf, i + 1)) {
1368 fprintf(stderr, "incorrect offsets %u %u\n",
1369 btrfs_item_offset_nr(buf, i),
1370 btrfs_item_end_nr(buf, i + 1));
1371 return 1;
1372 }
1373 if (i == 0 && btrfs_item_end_nr(buf, i) !=
1374 BTRFS_LEAF_DATA_SIZE(root)) {
1375 fprintf(stderr, "bad item end %u wanted %u\n",
1376 btrfs_item_end_nr(buf, i),
1377 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
1378 return 1;
1379 }
1380 }
1381 return 0;
1382 }
1383
1384 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1385 {
1386 struct list_head *cur = rec->backrefs.next;
1387 struct extent_backref *back;
1388 u32 found = 0;
1389 int err = 0;
1390
1391 while(cur != &rec->backrefs) {
1392 back = list_entry(cur, struct extent_backref, list);
1393 cur = cur->next;
1394 if (!back->found_extent_tree) {
1395 err = 1;
1396 if (!print_errs)
1397 goto out;
1398 fprintf(stderr, "Backref %llu parent %llu"
1399 " [%llu %llu %llu %lu]"
1400 " not found in extent tree\n",
1401 (unsigned long long)rec->start,
1402 (unsigned long long)back->parent,
1403 (unsigned long long)back->root,
1404 (unsigned long long)back->generation,
1405 (unsigned long long)back->owner,
1406 (unsigned long)back->num_refs);
1407 }
1408 if (!back->found_ref) {
1409 err = 1;
1410 if (!print_errs)
1411 goto out;
1412 fprintf(stderr, "Backref %llu parent %llu"
1413 " [%llu %llu %llu %lu]"
1414 " not referenced\n",
1415 (unsigned long long)rec->start,
1416 (unsigned long long)back->parent,
1417 (unsigned long long)back->root,
1418 (unsigned long long)back->generation,
1419 (unsigned long long)back->owner,
1420 (unsigned long)back->num_refs);
1421 }
1422 if (back->found_ref != back->num_refs) {
1423 err = 1;
1424 if (!print_errs)
1425 goto out;
1426 fprintf(stderr, "Incorrect local backref count "
1427 "on %llu parent %llu found %u wanted %u\n",
1428 (unsigned long long)rec->start,
1429 (unsigned long long)back->parent,
1430 back->found_ref, back->num_refs);
1431 }
1432 found += back->found_ref;
1433 }
1434 if (found != rec->refs) {
1435 err = 1;
1436 if (!print_errs)
1437 goto out;
1438 fprintf(stderr, "Incorrect global backref count "
1439 "on %llu found %u wanted %u\n",
1440 (unsigned long long)rec->start,
1441 found, rec->refs);
1442 }
1443 out:
1444 return err;
1445 }
1446
1447 static int free_all_extent_backrefs(struct extent_record *rec)
1448 {
1449 struct extent_backref *back;
1450 struct list_head *cur;
1451 while (!list_empty(&rec->backrefs)) {
1452 cur = rec->backrefs.next;
1453 back = list_entry(cur, struct extent_backref, list);
1454 list_del(cur);
1455 free(back);
1456 }
1457 return 0;
1458 }
1459
1460 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1461 struct extent_record *rec)
1462 {
1463 if (rec->checked && rec->extent_item_refs == rec->refs &&
1464 rec->refs > 0 && !all_backpointers_checked(rec, 0)) {
1465 remove_cache_extent(extent_cache, &rec->cache);
1466 free_all_extent_backrefs(rec);
1467 free(rec);
1468 }
1469 return 0;
1470 }
1471
1472 static int check_block(struct btrfs_root *root,
1473 struct cache_tree *extent_cache,
1474 struct extent_buffer *buf)
1475 {
1476 struct extent_record *rec;
1477 struct cache_extent *cache;
1478 int ret = 1;
1479
1480 cache = find_cache_extent(extent_cache, buf->start, buf->len);
1481 if (!cache)
1482 return 1;
1483 rec = container_of(cache, struct extent_record, cache);
1484 if (btrfs_is_leaf(buf)) {
1485 ret = check_leaf(root, &rec->parent_key, buf);
1486 } else {
1487 ret = check_node(root, &rec->parent_key, buf);
1488 }
1489 rec->checked = 1;
1490 if (!ret)
1491 maybe_free_extent_rec(extent_cache, rec);
1492 return ret;
1493 }
1494
1495 static struct extent_backref *find_extent_backref(struct extent_record *rec,
1496 u64 parent, u64 root, u64 gen)
1497 {
1498 struct list_head *cur = rec->backrefs.next;
1499 struct extent_backref *back;
1500
1501 while(cur != &rec->backrefs) {
1502 back = list_entry(cur, struct extent_backref, list);
1503 cur = cur->next;
1504 if (back->parent != parent)
1505 continue;
1506 if (back->root != root || back->generation != gen)
1507 continue;
1508 return back;
1509 }
1510 return NULL;
1511 }
1512
1513 static struct extent_backref *alloc_extent_backref(struct extent_record *rec,
1514 u64 parent, u64 root,
1515 u64 gen, u64 owner)
1516 {
1517 struct extent_backref *ref = malloc(sizeof(*ref));
1518 ref->parent = parent;
1519 ref->root = root;
1520 ref->generation = gen;
1521 ref->owner = owner;
1522 ref->num_refs = 0;
1523 ref->found_extent_tree = 0;
1524 ref->found_ref = 0;
1525 list_add_tail(&ref->list, &rec->backrefs);
1526 return ref;
1527 }
1528
1529 static int add_extent_rec(struct cache_tree *extent_cache,
1530 struct btrfs_disk_key *parent_key,
1531 u64 ref, u64 start, u64 nr,
1532 u32 extent_item_refs, int inc_ref, int set_checked)
1533 {
1534 struct extent_record *rec;
1535 struct cache_extent *cache;
1536 int ret = 0;
1537
1538 cache = find_cache_extent(extent_cache, start, nr);
1539 if (cache) {
1540 rec = container_of(cache, struct extent_record, cache);
1541 if (inc_ref)
1542 rec->refs++;
1543 if (rec->nr == 1)
1544 rec->nr = nr;
1545
1546 if (start != rec->start) {
1547 fprintf(stderr, "warning, start mismatch %llu %llu\n",
1548 (unsigned long long)rec->start,
1549 (unsigned long long)start);
1550 ret = 1;
1551 }
1552 if (extent_item_refs) {
1553 if (rec->extent_item_refs) {
1554 fprintf(stderr, "block %llu rec "
1555 "extent_item_refs %u, passed %u\n",
1556 (unsigned long long)start,
1557 rec->extent_item_refs,
1558 extent_item_refs);
1559 }
1560 rec->extent_item_refs = extent_item_refs;
1561 }
1562 if (set_checked)
1563 rec->checked = 1;
1564
1565 if (parent_key)
1566 memcpy(&rec->parent_key, parent_key,
1567 sizeof(*parent_key));
1568
1569 maybe_free_extent_rec(extent_cache, rec);
1570 return ret;
1571 }
1572 rec = malloc(sizeof(*rec));
1573 if (start == 0)
1574 extent_item_refs = 0;
1575 rec->start = start;
1576 rec->nr = nr;
1577 rec->checked = 0;
1578 INIT_LIST_HEAD(&rec->backrefs);
1579
1580 if (inc_ref)
1581 rec->refs = 1;
1582 else
1583 rec->refs = 0;
1584
1585 if (extent_item_refs)
1586 rec->extent_item_refs = extent_item_refs;
1587 else
1588 rec->extent_item_refs = 0;
1589
1590 if (parent_key)
1591 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
1592 else
1593 memset(&rec->parent_key, 0, sizeof(*parent_key));
1594
1595 rec->cache.start = start;
1596 rec->cache.size = nr;
1597 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
1598 BUG_ON(ret);
1599 bytes_used += nr;
1600 if (set_checked)
1601 rec->checked = 1;
1602 return ret;
1603 }
1604
1605 static int add_extent_backref(struct cache_tree *extent_cache, u64 bytenr,
1606 u64 parent, u64 root, u64 gen, u64 owner,
1607 u32 num_refs, int found_ref)
1608 {
1609 struct extent_record *rec;
1610 struct extent_backref *back;
1611 struct cache_extent *cache;
1612
1613 cache = find_cache_extent(extent_cache, bytenr, 1);
1614 if (!cache) {
1615 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0);
1616 cache = find_cache_extent(extent_cache, bytenr, 1);
1617 if (!cache)
1618 abort();
1619 }
1620
1621 rec = container_of(cache, struct extent_record, cache);
1622 if (rec->start != bytenr) {
1623 abort();
1624 }
1625 back = find_extent_backref(rec, parent, root, gen);
1626 if (!back)
1627 back = alloc_extent_backref(rec, parent, root, gen, owner);
1628
1629 if (found_ref) {
1630 if (back->found_ref > 0 &&
1631 back->owner < BTRFS_FIRST_FREE_OBJECTID) {
1632 fprintf(stderr, "Extent back ref already exists "
1633 "for %llu parent %llu root %llu gen %llu "
1634 "owner %llu num_refs %lu\n",
1635 (unsigned long long)parent,
1636 (unsigned long long)bytenr,
1637 (unsigned long long)root,
1638 (unsigned long long)gen,
1639 (unsigned long long)owner,
1640 (unsigned long)num_refs);
1641 }
1642 BUG_ON(num_refs != 1);
1643 back->found_ref += 1;
1644 } else {
1645 if (back->found_extent_tree) {
1646 fprintf(stderr, "Extent back ref already exists "
1647 "for %llu parent %llu root %llu gen %llu "
1648 "owner %llu num_refs %lu\n",
1649 (unsigned long long)parent,
1650 (unsigned long long)bytenr,
1651 (unsigned long long)root,
1652 (unsigned long long)gen,
1653 (unsigned long long)owner,
1654 (unsigned long)num_refs);
1655 }
1656 back->num_refs = num_refs;
1657 back->found_extent_tree = 1;
1658 }
1659 return 0;
1660 }
1661
1662
1663 static int add_pending(struct cache_tree *pending,
1664 struct cache_tree *seen, u64 bytenr, u32 size)
1665 {
1666 int ret;
1667 ret = insert_cache_extent(seen, bytenr, size);
1668 if (ret)
1669 return ret;
1670 insert_cache_extent(pending, bytenr, size);
1671 return 0;
1672 }
1673 static int pick_next_pending(struct cache_tree *pending,
1674 struct cache_tree *reada,
1675 struct cache_tree *nodes,
1676 u64 last, struct block_info *bits, int bits_nr,
1677 int *reada_bits)
1678 {
1679 unsigned long node_start = last;
1680 struct cache_extent *cache;
1681 int ret;
1682
1683 cache = find_first_cache_extent(reada, 0);
1684 if (cache) {
1685 bits[0].start = cache->start;
1686 bits[1].size = cache->size;
1687 *reada_bits = 1;
1688 return 1;
1689 }
1690 *reada_bits = 0;
1691 if (node_start > 32768)
1692 node_start -= 32768;
1693
1694 cache = find_first_cache_extent(nodes, node_start);
1695 if (!cache)
1696 cache = find_first_cache_extent(nodes, 0);
1697
1698 if (!cache) {
1699 cache = find_first_cache_extent(pending, 0);
1700 if (!cache)
1701 return 0;
1702 ret = 0;
1703 do {
1704 bits[ret].start = cache->start;
1705 bits[ret].size = cache->size;
1706 cache = next_cache_extent(cache);
1707 ret++;
1708 } while (cache && ret < bits_nr);
1709 return ret;
1710 }
1711
1712 ret = 0;
1713 do {
1714 bits[ret].start = cache->start;
1715 bits[ret].size = cache->size;
1716 cache = next_cache_extent(cache);
1717 ret++;
1718 } while (cache && ret < bits_nr);
1719
1720 if (bits_nr - ret > 8) {
1721 u64 lookup = bits[0].start + bits[0].size;
1722 struct cache_extent *next;
1723 next = find_first_cache_extent(pending, lookup);
1724 while(next) {
1725 if (next->start - lookup > 32768)
1726 break;
1727 bits[ret].start = next->start;
1728 bits[ret].size = next->size;
1729 lookup = next->start + next->size;
1730 ret++;
1731 if (ret == bits_nr)
1732 break;
1733 next = next_cache_extent(next);
1734 if (!next)
1735 break;
1736 }
1737 }
1738 return ret;
1739 }
1740
1741 static int run_next_block(struct btrfs_root *root,
1742 struct block_info *bits,
1743 int bits_nr,
1744 u64 *last,
1745 struct cache_tree *pending,
1746 struct cache_tree *seen,
1747 struct cache_tree *reada,
1748 struct cache_tree *nodes,
1749 struct cache_tree *extent_cache)
1750 {
1751 struct extent_buffer *buf;
1752 u64 bytenr;
1753 u32 size;
1754 int ret;
1755 int i;
1756 int nritems;
1757 struct btrfs_extent_ref *ref;
1758 struct btrfs_disk_key disk_key;
1759 struct cache_extent *cache;
1760 int reada_bits;
1761
1762 ret = pick_next_pending(pending, reada, nodes, *last, bits,
1763 bits_nr, &reada_bits);
1764 if (ret == 0) {
1765 return 1;
1766 }
1767 if (!reada_bits) {
1768 for(i = 0; i < ret; i++) {
1769 insert_cache_extent(reada, bits[i].start,
1770 bits[i].size);
1771
1772 /* fixme, get the parent transid */
1773 readahead_tree_block(root, bits[i].start,
1774 bits[i].size, 0);
1775 }
1776 }
1777 *last = bits[0].start;
1778 bytenr = bits[0].start;
1779 size = bits[0].size;
1780
1781 cache = find_cache_extent(pending, bytenr, size);
1782 if (cache) {
1783 remove_cache_extent(pending, cache);
1784 free(cache);
1785 }
1786 cache = find_cache_extent(reada, bytenr, size);
1787 if (cache) {
1788 remove_cache_extent(reada, cache);
1789 free(cache);
1790 }
1791 cache = find_cache_extent(nodes, bytenr, size);
1792 if (cache) {
1793 remove_cache_extent(nodes, cache);
1794 free(cache);
1795 }
1796
1797 /* fixme, get the real parent transid */
1798 buf = read_tree_block(root, bytenr, size, 0);
1799 nritems = btrfs_header_nritems(buf);
1800 ret = check_block(root, extent_cache, buf);
1801 if (ret) {
1802 fprintf(stderr, "bad block %llu\n",
1803 (unsigned long long)bytenr);
1804 }
1805 if (btrfs_is_leaf(buf)) {
1806 btree_space_waste += btrfs_leaf_free_space(root, buf);
1807 for (i = 0; i < nritems; i++) {
1808 struct btrfs_file_extent_item *fi;
1809 btrfs_item_key(buf, &disk_key, i);
1810 if (btrfs_disk_key_type(&disk_key) ==
1811 BTRFS_EXTENT_ITEM_KEY) {
1812 struct btrfs_key found;
1813 struct btrfs_extent_item *ei;
1814 btrfs_disk_key_to_cpu(&found, &disk_key);
1815 ei = btrfs_item_ptr(buf, i,
1816 struct btrfs_extent_item);
1817 add_extent_rec(extent_cache, NULL, 0,
1818 found.objectid,
1819 found.offset,
1820 btrfs_extent_refs(buf, ei),
1821 0, 0);
1822 continue;
1823 }
1824 if (btrfs_disk_key_type(&disk_key) ==
1825 BTRFS_EXTENT_CSUM_KEY) {
1826 total_csum_bytes +=
1827 btrfs_item_size_nr(buf, i);
1828 continue;
1829 }
1830 if (btrfs_disk_key_type(&disk_key) ==
1831 BTRFS_BLOCK_GROUP_ITEM_KEY) {
1832 struct btrfs_block_group_item *bi;
1833 bi = btrfs_item_ptr(buf, i,
1834 struct btrfs_block_group_item);
1835 #if 0
1836 fprintf(stderr,"block group %Lu %Lu used %Lu ",
1837 btrfs_disk_key_objectid(disk_key),
1838 btrfs_disk_key_offset(disk_key),
1839 btrfs_block_group_used(bi));
1840 fprintf(stderr, "flags %x\n", bi->flags);
1841 #endif
1842 continue;
1843 }
1844 if (btrfs_disk_key_type(&disk_key) ==
1845 BTRFS_EXTENT_REF_KEY) {
1846 ref = btrfs_item_ptr(buf, i,
1847 struct btrfs_extent_ref);
1848 add_extent_backref(extent_cache,
1849 btrfs_disk_key_objectid(&disk_key),
1850 btrfs_disk_key_offset(&disk_key),
1851 btrfs_ref_root(buf, ref),
1852 btrfs_ref_generation(buf, ref),
1853 btrfs_ref_objectid(buf, ref),
1854 btrfs_ref_num_refs(buf, ref), 0);
1855 continue;
1856 }
1857 if (btrfs_disk_key_type(&disk_key) !=
1858 BTRFS_EXTENT_DATA_KEY)
1859 continue;
1860 fi = btrfs_item_ptr(buf, i,
1861 struct btrfs_file_extent_item);
1862 if (btrfs_file_extent_type(buf, fi) ==
1863 BTRFS_FILE_EXTENT_INLINE)
1864 continue;
1865 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
1866 continue;
1867
1868 data_bytes_allocated +=
1869 btrfs_file_extent_disk_num_bytes(buf, fi);
1870 if (data_bytes_allocated < root->sectorsize) {
1871 abort();
1872 }
1873 data_bytes_referenced +=
1874 btrfs_file_extent_num_bytes(buf, fi);
1875 ret = add_extent_rec(extent_cache, NULL, bytenr,
1876 btrfs_file_extent_disk_bytenr(buf, fi),
1877 btrfs_file_extent_disk_num_bytes(buf, fi),
1878 0, 1, 1);
1879 add_extent_backref(extent_cache,
1880 btrfs_file_extent_disk_bytenr(buf, fi),
1881 buf->start, btrfs_header_owner(buf),
1882 btrfs_header_generation(buf),
1883 btrfs_disk_key_objectid(&disk_key), 1, 1);
1884 BUG_ON(ret);
1885 }
1886 } else {
1887 int level;
1888 level = btrfs_header_level(buf);
1889 for (i = 0; i < nritems; i++) {
1890 u64 ptr = btrfs_node_blockptr(buf, i);
1891 u32 size = btrfs_level_size(root, level - 1);
1892 btrfs_node_key(buf, &disk_key, i);
1893 ret = add_extent_rec(extent_cache,
1894 &disk_key,
1895 bytenr, ptr, size,
1896 0, 1, 0);
1897 BUG_ON(ret);
1898
1899 add_extent_backref(extent_cache, ptr,
1900 buf->start, btrfs_header_owner(buf),
1901 btrfs_header_generation(buf),
1902 level - 1, 1, 1);
1903
1904 if (level > 1) {
1905 add_pending(nodes, seen, ptr, size);
1906 } else {
1907 add_pending(pending, seen, ptr, size);
1908 }
1909 }
1910 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
1911 nritems) * sizeof(struct btrfs_key_ptr);
1912 }
1913 total_btree_bytes += buf->len;
1914 free_extent_buffer(buf);
1915 return 0;
1916 }
1917
1918 static int add_root_to_pending(struct extent_buffer *buf,
1919 struct block_info *bits,
1920 int bits_nr,
1921 struct cache_tree *extent_cache,
1922 struct cache_tree *pending,
1923 struct cache_tree *seen,
1924 struct cache_tree *reada,
1925 struct cache_tree *nodes, u64 root_objectid)
1926 {
1927 if (btrfs_header_level(buf) > 0)
1928 add_pending(nodes, seen, buf->start, buf->len);
1929 else
1930 add_pending(pending, seen, buf->start, buf->len);
1931 add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
1932 0, 1, 0);
1933
1934 add_extent_backref(extent_cache, buf->start, buf->start,
1935 root_objectid, btrfs_header_generation(buf),
1936 btrfs_header_level(buf), 1, 1);
1937 return 0;
1938 }
1939
1940 static int check_extent_refs(struct btrfs_root *root,
1941 struct cache_tree *extent_cache)
1942 {
1943 struct extent_record *rec;
1944 struct cache_extent *cache;
1945 int err = 0;
1946
1947 while(1) {
1948 cache = find_first_cache_extent(extent_cache, 0);
1949 if (!cache)
1950 break;
1951 rec = container_of(cache, struct extent_record, cache);
1952 if (rec->refs != rec->extent_item_refs) {
1953 fprintf(stderr, "ref mismatch on [%llu %llu] ",
1954 (unsigned long long)rec->start,
1955 (unsigned long long)rec->nr);
1956 fprintf(stderr, "extent item %u, found %u\n",
1957 rec->extent_item_refs,
1958 rec->refs);
1959 err = 1;
1960 }
1961 if (all_backpointers_checked(rec, 1)) {
1962 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
1963 (unsigned long long)rec->start,
1964 (unsigned long long)rec->nr);
1965
1966 err = 1;
1967 }
1968 remove_cache_extent(extent_cache, cache);
1969 free_all_extent_backrefs(rec);
1970 free(rec);
1971 }
1972 return err;
1973 }
1974
1975 static int check_extents(struct btrfs_root *root)
1976 {
1977 struct cache_tree extent_cache;
1978 struct cache_tree seen;
1979 struct cache_tree pending;
1980 struct cache_tree reada;
1981 struct cache_tree nodes;
1982 struct btrfs_path path;
1983 struct btrfs_key key;
1984 struct btrfs_key found_key;
1985 int ret;
1986 u64 last = 0;
1987 struct block_info *bits;
1988 int bits_nr;
1989 struct extent_buffer *leaf;
1990 int slot;
1991 struct btrfs_root_item ri;
1992
1993 cache_tree_init(&extent_cache);
1994 cache_tree_init(&seen);
1995 cache_tree_init(&pending);
1996 cache_tree_init(&nodes);
1997 cache_tree_init(&reada);
1998
1999 bits_nr = 1024;
2000 bits = malloc(bits_nr * sizeof(struct block_info));
2001 if (!bits) {
2002 perror("malloc");
2003 exit(1);
2004 }
2005
2006 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2007 &extent_cache, &pending, &seen, &reada, &nodes,
2008 root->fs_info->tree_root->root_key.objectid);
2009
2010 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2011 &extent_cache, &pending, &seen, &reada, &nodes,
2012 root->fs_info->chunk_root->root_key.objectid);
2013
2014 btrfs_init_path(&path);
2015 key.offset = 0;
2016 key.objectid = 0;
2017 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2018 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2019 &key, &path, 0, 0);
2020 BUG_ON(ret < 0);
2021 while(1) {
2022 leaf = path.nodes[0];
2023 slot = path.slots[0];
2024 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2025 ret = btrfs_next_leaf(root, &path);
2026 if (ret != 0)
2027 break;
2028 leaf = path.nodes[0];
2029 slot = path.slots[0];
2030 }
2031 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2032 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2033 unsigned long offset;
2034 struct extent_buffer *buf;
2035
2036 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2037 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2038 buf = read_tree_block(root->fs_info->tree_root,
2039 btrfs_root_bytenr(&ri),
2040 btrfs_level_size(root,
2041 btrfs_root_level(&ri)), 0);
2042 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2043 &pending, &seen, &reada, &nodes,
2044 found_key.objectid);
2045 free_extent_buffer(buf);
2046 }
2047 path.slots[0]++;
2048 }
2049 btrfs_release_path(root, &path);
2050 while(1) {
2051 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2052 &seen, &reada, &nodes, &extent_cache);
2053 if (ret != 0)
2054 break;
2055 }
2056 ret = check_extent_refs(root, &extent_cache);
2057 return ret;
2058 }
2059
2060 static void print_usage(void)
2061 {
2062 fprintf(stderr, "usage: btrfsck dev\n");
2063 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2064 exit(1);
2065 }
2066
2067 int main(int ac, char **av)
2068 {
2069 struct btrfs_root *root;
2070 int ret;
2071
2072 if (ac < 2)
2073 print_usage();
2074
2075 radix_tree_init();
2076 root = open_ctree(av[1], 0, 0);
2077
2078 if (root == NULL)
2079 return 1;
2080
2081 ret = check_extents(root);
2082 if (ret)
2083 goto out;
2084 ret = check_fs_roots(root);
2085
2086 out:
2087 close_ctree(root);
2088 printf("found %llu bytes used err is %d\n",
2089 (unsigned long long)bytes_used, ret);
2090 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2091 printf("total tree bytes: %llu\n",
2092 (unsigned long long)total_btree_bytes);
2093 printf("btree space waste bytes: %llu\n",
2094 (unsigned long long)btree_space_waste);
2095 printf("file data blocks allocated: %llu\n referenced %llu\n",
2096 (unsigned long long)data_bytes_allocated,
2097 (unsigned long long)data_bytes_referenced);
2098 printf("%s\n", BTRFS_BUILD_VERSION);
2099 return ret;
2100 }
(deprecated) Btrfs progs developments and patch integration