?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix man page headers to include the correct program name.
[btrfs-progs-unstable/devel.git] / btrfsck.c
bloba6d105ec9120055faadf298285172421f4efa31b
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 (unsigned long long)root->root_key.objectid,
1138 (unsigned long long)root_dirid);
1139 error++;
1140 }
1141 } else {
1142 fprintf(stderr, "root %llu root dir %llu not found\n",
1143 (unsigned long long)root->root_key.objectid,
1144 (unsigned long long)root_dirid);
1145 }
1146
1147 while (1) {
1148 cache = find_first_cache_extent(inode_cache, 0);
1149 if (!cache)
1150 break;
1151 node = container_of(cache, struct ptr_node, cache);
1152 rec = node->data;
1153 remove_cache_extent(inode_cache, &node->cache);
1154 if (rec->ino == root_dirid ||
1155 rec->ino == BTRFS_ORPHAN_OBJECTID) {
1156 free(node);
1157 free_inode_rec(rec);
1158 continue;
1159 }
1160
1161 error++;
1162 if (!rec->found_inode_item)
1163 rec->errors |= I_ERR_NO_INODE_ITEM;
1164 fprintf(stderr, "root %llu inode %llu errors %x\n",
1165 (unsigned long long) root->root_key.objectid,
1166 (unsigned long long) rec->ino, rec->errors);
1167 list_for_each_entry(backref, &rec->backrefs, list) {
1168 if (!backref->found_dir_item)
1169 backref->errors |= REF_ERR_NO_DIR_ITEM;
1170 if (!backref->found_dir_index)
1171 backref->errors |= REF_ERR_NO_DIR_INDEX;
1172 if (!backref->found_inode_ref)
1173 backref->errors |= REF_ERR_NO_INODE_REF;
1174 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1175 " namelen %u name %s filetype %d error %x\n",
1176 (unsigned long long)backref->dir,
1177 (unsigned long long)backref->index,
1178 backref->namelen, backref->name,
1179 backref->filetype, backref->errors);
1180 }
1181 free(node);
1182 free_inode_rec(rec);
1183 }
1184 return (error > 0) ? -1 : 0;
1185 }
1186
1187 static int check_fs_root(struct btrfs_root *root,
1188 struct walk_control *wc)
1189 {
1190 int ret = 0;
1191 int wret;
1192 int level;
1193 struct btrfs_path path;
1194 struct shared_node root_node;
1195 struct btrfs_root_item *root_item = &root->root_item;
1196
1197 btrfs_init_path(&path);
1198 memset(&root_node, 0, sizeof(root_node));
1199 cache_tree_init(&root_node.inode_cache);
1200
1201 level = btrfs_header_level(root->node);
1202 memset(wc->nodes, 0, sizeof(wc->nodes));
1203 wc->nodes[level] = &root_node;
1204 wc->active_node = level;
1205 wc->root_level = level;
1206
1207 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1208 path.nodes[level] = root->node;
1209 extent_buffer_get(root->node);
1210 path.slots[level] = 0;
1211 } else {
1212 struct btrfs_key key;
1213 struct btrfs_disk_key found_key;
1214
1215 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1216 level = root_item->drop_level;
1217 path.lowest_level = level;
1218 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1219 BUG_ON(wret < 0);
1220 btrfs_node_key(path.nodes[level], &found_key,
1221 path.slots[level]);
1222 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1223 sizeof(found_key)));
1224 }
1225
1226 while (1) {
1227 wret = walk_down_tree(root, &path, wc, &level);
1228 if (wret < 0)
1229 ret = wret;
1230 if (wret != 0)
1231 break;
1232
1233 wret = walk_up_tree(root, &path, wc, &level);
1234 if (wret < 0)
1235 ret = wret;
1236 if (wret != 0)
1237 break;
1238 }
1239 btrfs_release_path(root, &path);
1240
1241 if (root_node.current) {
1242 root_node.current->checked = 1;
1243 maybe_free_inode_rec(&root_node.inode_cache,
1244 root_node.current);
1245 }
1246
1247 ret = check_inode_recs(root, &root_node.inode_cache);
1248 return ret;
1249 }
1250
1251 static int fs_root_objectid(u64 objectid)
1252 {
1253 if (objectid == BTRFS_FS_TREE_OBJECTID ||
1254 objectid == BTRFS_TREE_RELOC_OBJECTID ||
1255 (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1256 objectid < BTRFS_LAST_FREE_OBJECTID))
1257 return 1;
1258 return 0;
1259 }
1260
1261 static int check_fs_roots(struct btrfs_root *root)
1262 {
1263 struct btrfs_path path;
1264 struct btrfs_key key;
1265 struct walk_control wc;
1266 struct extent_buffer *leaf;
1267 struct btrfs_root *tmp_root;
1268 struct btrfs_root *tree_root = root->fs_info->tree_root;
1269 int ret;
1270 int err = 0;
1271
1272 memset(&wc, 0, sizeof(wc));
1273 cache_tree_init(&wc.shared);
1274 btrfs_init_path(&path);
1275
1276 key.offset = 0;
1277 key.objectid = 0;
1278 key.type = BTRFS_ROOT_ITEM_KEY;
1279 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1280 BUG_ON(ret < 0);
1281 while (1) {
1282 leaf = path.nodes[0];
1283 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1284 ret = btrfs_next_leaf(tree_root, &path);
1285 if (ret != 0)
1286 break;
1287 leaf = path.nodes[0];
1288 }
1289 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1290 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1291 fs_root_objectid(key.objectid)) {
1292 tmp_root = btrfs_read_fs_root(root->fs_info, &key);
1293 ret = check_fs_root(tmp_root, &wc);
1294 if (ret)
1295 err = 1;
1296 btrfs_free_fs_root(root->fs_info, tmp_root);
1297 }
1298 path.slots[0]++;
1299 }
1300 btrfs_release_path(tree_root, &path);
1301
1302 if (!cache_tree_empty(&wc.shared))
1303 fprintf(stderr, "warning line %d\n", __LINE__);
1304
1305 return err;
1306 }
1307
1308 static int check_node(struct btrfs_root *root,
1309 struct btrfs_disk_key *parent_key,
1310 struct extent_buffer *buf)
1311 {
1312 int i;
1313 struct btrfs_key cpukey;
1314 struct btrfs_disk_key key;
1315 u32 nritems = btrfs_header_nritems(buf);
1316
1317 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1318 return 1;
1319 if (parent_key->type) {
1320 btrfs_node_key(buf, &key, 0);
1321 if (memcmp(parent_key, &key, sizeof(key)))
1322 return 1;
1323 }
1324 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1325 btrfs_node_key(buf, &key, i);
1326 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
1327 if (btrfs_comp_keys(&key, &cpukey) >= 0)
1328 return 1;
1329 }
1330 return 0;
1331 }
1332
1333 static int check_leaf(struct btrfs_root *root,
1334 struct btrfs_disk_key *parent_key,
1335 struct extent_buffer *buf)
1336 {
1337 int i;
1338 struct btrfs_key cpukey;
1339 struct btrfs_disk_key key;
1340 u32 nritems = btrfs_header_nritems(buf);
1341
1342 if (btrfs_header_level(buf) != 0) {
1343 fprintf(stderr, "leaf is not a leaf %llu\n",
1344 (unsigned long long)btrfs_header_bytenr(buf));
1345 return 1;
1346 }
1347 if (btrfs_leaf_free_space(root, buf) < 0) {
1348 fprintf(stderr, "leaf free space incorrect %llu %d\n",
1349 (unsigned long long)btrfs_header_bytenr(buf),
1350 btrfs_leaf_free_space(root, buf));
1351 return 1;
1352 }
1353
1354 if (nritems == 0)
1355 return 0;
1356
1357 btrfs_item_key(buf, &key, 0);
1358 if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
1359 fprintf(stderr, "leaf parent key incorrect %llu\n",
1360 (unsigned long long)btrfs_header_bytenr(buf));
1361 return 1;
1362 }
1363 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1364 btrfs_item_key(buf, &key, i);
1365 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
1366 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
1367 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
1368 return 1;
1369 }
1370 if (btrfs_item_offset_nr(buf, i) !=
1371 btrfs_item_end_nr(buf, i + 1)) {
1372 fprintf(stderr, "incorrect offsets %u %u\n",
1373 btrfs_item_offset_nr(buf, i),
1374 btrfs_item_end_nr(buf, i + 1));
1375 return 1;
1376 }
1377 if (i == 0 && btrfs_item_end_nr(buf, i) !=
1378 BTRFS_LEAF_DATA_SIZE(root)) {
1379 fprintf(stderr, "bad item end %u wanted %u\n",
1380 btrfs_item_end_nr(buf, i),
1381 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
1382 return 1;
1383 }
1384 }
1385 return 0;
1386 }
1387
1388 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1389 {
1390 struct list_head *cur = rec->backrefs.next;
1391 struct extent_backref *back;
1392 u32 found = 0;
1393 int err = 0;
1394
1395 while(cur != &rec->backrefs) {
1396 back = list_entry(cur, struct extent_backref, list);
1397 cur = cur->next;
1398 if (!back->found_extent_tree) {
1399 err = 1;
1400 if (!print_errs)
1401 goto out;
1402 fprintf(stderr, "Backref %llu parent %llu"
1403 " [%llu %llu %llu %lu]"
1404 " not found in extent tree\n",
1405 (unsigned long long)rec->start,
1406 (unsigned long long)back->parent,
1407 (unsigned long long)back->root,
1408 (unsigned long long)back->generation,
1409 (unsigned long long)back->owner,
1410 (unsigned long)back->num_refs);
1411 }
1412 if (!back->found_ref) {
1413 err = 1;
1414 if (!print_errs)
1415 goto out;
1416 fprintf(stderr, "Backref %llu parent %llu"
1417 " [%llu %llu %llu %lu]"
1418 " not referenced\n",
1419 (unsigned long long)rec->start,
1420 (unsigned long long)back->parent,
1421 (unsigned long long)back->root,
1422 (unsigned long long)back->generation,
1423 (unsigned long long)back->owner,
1424 (unsigned long)back->num_refs);
1425 }
1426 if (back->found_ref != back->num_refs) {
1427 err = 1;
1428 if (!print_errs)
1429 goto out;
1430 fprintf(stderr, "Incorrect local backref count "
1431 "on %llu parent %llu found %u wanted %u\n",
1432 (unsigned long long)rec->start,
1433 (unsigned long long)back->parent,
1434 back->found_ref, back->num_refs);
1435 }
1436 found += back->found_ref;
1437 }
1438 if (found != rec->refs) {
1439 err = 1;
1440 if (!print_errs)
1441 goto out;
1442 fprintf(stderr, "Incorrect global backref count "
1443 "on %llu found %u wanted %u\n",
1444 (unsigned long long)rec->start,
1445 found, rec->refs);
1446 }
1447 out:
1448 return err;
1449 }
1450
1451 static int free_all_extent_backrefs(struct extent_record *rec)
1452 {
1453 struct extent_backref *back;
1454 struct list_head *cur;
1455 while (!list_empty(&rec->backrefs)) {
1456 cur = rec->backrefs.next;
1457 back = list_entry(cur, struct extent_backref, list);
1458 list_del(cur);
1459 free(back);
1460 }
1461 return 0;
1462 }
1463
1464 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1465 struct extent_record *rec)
1466 {
1467 if (rec->checked && rec->extent_item_refs == rec->refs &&
1468 rec->refs > 0 && !all_backpointers_checked(rec, 0)) {
1469 remove_cache_extent(extent_cache, &rec->cache);
1470 free_all_extent_backrefs(rec);
1471 free(rec);
1472 }
1473 return 0;
1474 }
1475
1476 static int check_block(struct btrfs_root *root,
1477 struct cache_tree *extent_cache,
1478 struct extent_buffer *buf)
1479 {
1480 struct extent_record *rec;
1481 struct cache_extent *cache;
1482 int ret = 1;
1483
1484 cache = find_cache_extent(extent_cache, buf->start, buf->len);
1485 if (!cache)
1486 return 1;
1487 rec = container_of(cache, struct extent_record, cache);
1488 if (btrfs_is_leaf(buf)) {
1489 ret = check_leaf(root, &rec->parent_key, buf);
1490 } else {
1491 ret = check_node(root, &rec->parent_key, buf);
1492 }
1493 rec->checked = 1;
1494 if (!ret)
1495 maybe_free_extent_rec(extent_cache, rec);
1496 return ret;
1497 }
1498
1499 static struct extent_backref *find_extent_backref(struct extent_record *rec,
1500 u64 parent, u64 root, u64 gen)
1501 {
1502 struct list_head *cur = rec->backrefs.next;
1503 struct extent_backref *back;
1504
1505 while(cur != &rec->backrefs) {
1506 back = list_entry(cur, struct extent_backref, list);
1507 cur = cur->next;
1508 if (back->parent != parent)
1509 continue;
1510 if (back->root != root || back->generation != gen)
1511 continue;
1512 return back;
1513 }
1514 return NULL;
1515 }
1516
1517 static struct extent_backref *alloc_extent_backref(struct extent_record *rec,
1518 u64 parent, u64 root,
1519 u64 gen, u64 owner)
1520 {
1521 struct extent_backref *ref = malloc(sizeof(*ref));
1522 ref->parent = parent;
1523 ref->root = root;
1524 ref->generation = gen;
1525 ref->owner = owner;
1526 ref->num_refs = 0;
1527 ref->found_extent_tree = 0;
1528 ref->found_ref = 0;
1529 list_add_tail(&ref->list, &rec->backrefs);
1530 return ref;
1531 }
1532
1533 static int add_extent_rec(struct cache_tree *extent_cache,
1534 struct btrfs_disk_key *parent_key,
1535 u64 ref, u64 start, u64 nr,
1536 u32 extent_item_refs, int inc_ref, int set_checked)
1537 {
1538 struct extent_record *rec;
1539 struct cache_extent *cache;
1540 int ret = 0;
1541
1542 cache = find_cache_extent(extent_cache, start, nr);
1543 if (cache) {
1544 rec = container_of(cache, struct extent_record, cache);
1545 if (inc_ref)
1546 rec->refs++;
1547 if (rec->nr == 1)
1548 rec->nr = nr;
1549
1550 if (start != rec->start) {
1551 fprintf(stderr, "warning, start mismatch %llu %llu\n",
1552 (unsigned long long)rec->start,
1553 (unsigned long long)start);
1554 ret = 1;
1555 }
1556 if (extent_item_refs) {
1557 if (rec->extent_item_refs) {
1558 fprintf(stderr, "block %llu rec "
1559 "extent_item_refs %u, passed %u\n",
1560 (unsigned long long)start,
1561 rec->extent_item_refs,
1562 extent_item_refs);
1563 }
1564 rec->extent_item_refs = extent_item_refs;
1565 }
1566 if (set_checked)
1567 rec->checked = 1;
1568
1569 if (parent_key)
1570 memcpy(&rec->parent_key, parent_key,
1571 sizeof(*parent_key));
1572
1573 maybe_free_extent_rec(extent_cache, rec);
1574 return ret;
1575 }
1576 rec = malloc(sizeof(*rec));
1577 if (start == 0)
1578 extent_item_refs = 0;
1579 rec->start = start;
1580 rec->nr = nr;
1581 rec->checked = 0;
1582 INIT_LIST_HEAD(&rec->backrefs);
1583
1584 if (inc_ref)
1585 rec->refs = 1;
1586 else
1587 rec->refs = 0;
1588
1589 if (extent_item_refs)
1590 rec->extent_item_refs = extent_item_refs;
1591 else
1592 rec->extent_item_refs = 0;
1593
1594 if (parent_key)
1595 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
1596 else
1597 memset(&rec->parent_key, 0, sizeof(*parent_key));
1598
1599 rec->cache.start = start;
1600 rec->cache.size = nr;
1601 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
1602 BUG_ON(ret);
1603 bytes_used += nr;
1604 if (set_checked)
1605 rec->checked = 1;
1606 return ret;
1607 }
1608
1609 static int add_extent_backref(struct cache_tree *extent_cache, u64 bytenr,
1610 u64 parent, u64 root, u64 gen, u64 owner,
1611 u32 num_refs, int found_ref)
1612 {
1613 struct extent_record *rec;
1614 struct extent_backref *back;
1615 struct cache_extent *cache;
1616
1617 cache = find_cache_extent(extent_cache, bytenr, 1);
1618 if (!cache) {
1619 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0);
1620 cache = find_cache_extent(extent_cache, bytenr, 1);
1621 if (!cache)
1622 abort();
1623 }
1624
1625 rec = container_of(cache, struct extent_record, cache);
1626 if (rec->start != bytenr) {
1627 abort();
1628 }
1629 back = find_extent_backref(rec, parent, root, gen);
1630 if (!back)
1631 back = alloc_extent_backref(rec, parent, root, gen, owner);
1632
1633 if (found_ref) {
1634 if (back->found_ref > 0 &&
1635 back->owner < BTRFS_FIRST_FREE_OBJECTID) {
1636 fprintf(stderr, "Extent back ref already exists "
1637 "for %llu parent %llu root %llu gen %llu "
1638 "owner %llu num_refs %lu\n",
1639 (unsigned long long)parent,
1640 (unsigned long long)bytenr,
1641 (unsigned long long)root,
1642 (unsigned long long)gen,
1643 (unsigned long long)owner,
1644 (unsigned long)num_refs);
1645 }
1646 BUG_ON(num_refs != 1);
1647 back->found_ref += 1;
1648 } else {
1649 if (back->found_extent_tree) {
1650 fprintf(stderr, "Extent back ref already exists "
1651 "for %llu parent %llu root %llu gen %llu "
1652 "owner %llu num_refs %lu\n",
1653 (unsigned long long)parent,
1654 (unsigned long long)bytenr,
1655 (unsigned long long)root,
1656 (unsigned long long)gen,
1657 (unsigned long long)owner,
1658 (unsigned long)num_refs);
1659 }
1660 back->num_refs = num_refs;
1661 back->found_extent_tree = 1;
1662 }
1663 return 0;
1664 }
1665
1666
1667 static int add_pending(struct cache_tree *pending,
1668 struct cache_tree *seen, u64 bytenr, u32 size)
1669 {
1670 int ret;
1671 ret = insert_cache_extent(seen, bytenr, size);
1672 if (ret)
1673 return ret;
1674 insert_cache_extent(pending, bytenr, size);
1675 return 0;
1676 }
1677 static int pick_next_pending(struct cache_tree *pending,
1678 struct cache_tree *reada,
1679 struct cache_tree *nodes,
1680 u64 last, struct block_info *bits, int bits_nr,
1681 int *reada_bits)
1682 {
1683 unsigned long node_start = last;
1684 struct cache_extent *cache;
1685 int ret;
1686
1687 cache = find_first_cache_extent(reada, 0);
1688 if (cache) {
1689 bits[0].start = cache->start;
1690 bits[1].size = cache->size;
1691 *reada_bits = 1;
1692 return 1;
1693 }
1694 *reada_bits = 0;
1695 if (node_start > 32768)
1696 node_start -= 32768;
1697
1698 cache = find_first_cache_extent(nodes, node_start);
1699 if (!cache)
1700 cache = find_first_cache_extent(nodes, 0);
1701
1702 if (!cache) {
1703 cache = find_first_cache_extent(pending, 0);
1704 if (!cache)
1705 return 0;
1706 ret = 0;
1707 do {
1708 bits[ret].start = cache->start;
1709 bits[ret].size = cache->size;
1710 cache = next_cache_extent(cache);
1711 ret++;
1712 } while (cache && ret < bits_nr);
1713 return ret;
1714 }
1715
1716 ret = 0;
1717 do {
1718 bits[ret].start = cache->start;
1719 bits[ret].size = cache->size;
1720 cache = next_cache_extent(cache);
1721 ret++;
1722 } while (cache && ret < bits_nr);
1723
1724 if (bits_nr - ret > 8) {
1725 u64 lookup = bits[0].start + bits[0].size;
1726 struct cache_extent *next;
1727 next = find_first_cache_extent(pending, lookup);
1728 while(next) {
1729 if (next->start - lookup > 32768)
1730 break;
1731 bits[ret].start = next->start;
1732 bits[ret].size = next->size;
1733 lookup = next->start + next->size;
1734 ret++;
1735 if (ret == bits_nr)
1736 break;
1737 next = next_cache_extent(next);
1738 if (!next)
1739 break;
1740 }
1741 }
1742 return ret;
1743 }
1744
1745 static int run_next_block(struct btrfs_root *root,
1746 struct block_info *bits,
1747 int bits_nr,
1748 u64 *last,
1749 struct cache_tree *pending,
1750 struct cache_tree *seen,
1751 struct cache_tree *reada,
1752 struct cache_tree *nodes,
1753 struct cache_tree *extent_cache)
1754 {
1755 struct extent_buffer *buf;
1756 u64 bytenr;
1757 u32 size;
1758 int ret;
1759 int i;
1760 int nritems;
1761 struct btrfs_extent_ref *ref;
1762 struct btrfs_disk_key disk_key;
1763 struct cache_extent *cache;
1764 int reada_bits;
1765
1766 ret = pick_next_pending(pending, reada, nodes, *last, bits,
1767 bits_nr, &reada_bits);
1768 if (ret == 0) {
1769 return 1;
1770 }
1771 if (!reada_bits) {
1772 for(i = 0; i < ret; i++) {
1773 insert_cache_extent(reada, bits[i].start,
1774 bits[i].size);
1775
1776 /* fixme, get the parent transid */
1777 readahead_tree_block(root, bits[i].start,
1778 bits[i].size, 0);
1779 }
1780 }
1781 *last = bits[0].start;
1782 bytenr = bits[0].start;
1783 size = bits[0].size;
1784
1785 cache = find_cache_extent(pending, bytenr, size);
1786 if (cache) {
1787 remove_cache_extent(pending, cache);
1788 free(cache);
1789 }
1790 cache = find_cache_extent(reada, bytenr, size);
1791 if (cache) {
1792 remove_cache_extent(reada, cache);
1793 free(cache);
1794 }
1795 cache = find_cache_extent(nodes, bytenr, size);
1796 if (cache) {
1797 remove_cache_extent(nodes, cache);
1798 free(cache);
1799 }
1800
1801 /* fixme, get the real parent transid */
1802 buf = read_tree_block(root, bytenr, size, 0);
1803 nritems = btrfs_header_nritems(buf);
1804 ret = check_block(root, extent_cache, buf);
1805 if (ret) {
1806 fprintf(stderr, "bad block %llu\n",
1807 (unsigned long long)bytenr);
1808 }
1809 if (btrfs_is_leaf(buf)) {
1810 btree_space_waste += btrfs_leaf_free_space(root, buf);
1811 for (i = 0; i < nritems; i++) {
1812 struct btrfs_file_extent_item *fi;
1813 btrfs_item_key(buf, &disk_key, i);
1814 if (btrfs_disk_key_type(&disk_key) ==
1815 BTRFS_EXTENT_ITEM_KEY) {
1816 struct btrfs_key found;
1817 struct btrfs_extent_item *ei;
1818 btrfs_disk_key_to_cpu(&found, &disk_key);
1819 ei = btrfs_item_ptr(buf, i,
1820 struct btrfs_extent_item);
1821 add_extent_rec(extent_cache, NULL, 0,
1822 found.objectid,
1823 found.offset,
1824 btrfs_extent_refs(buf, ei),
1825 0, 0);
1826 continue;
1827 }
1828 if (btrfs_disk_key_type(&disk_key) ==
1829 BTRFS_EXTENT_CSUM_KEY) {
1830 total_csum_bytes +=
1831 btrfs_item_size_nr(buf, i);
1832 continue;
1833 }
1834 if (btrfs_disk_key_type(&disk_key) ==
1835 BTRFS_BLOCK_GROUP_ITEM_KEY) {
1836 struct btrfs_block_group_item *bi;
1837 bi = btrfs_item_ptr(buf, i,
1838 struct btrfs_block_group_item);
1839 #if 0
1840 fprintf(stderr,"block group %Lu %Lu used %Lu ",
1841 btrfs_disk_key_objectid(disk_key),
1842 btrfs_disk_key_offset(disk_key),
1843 btrfs_block_group_used(bi));
1844 fprintf(stderr, "flags %x\n", bi->flags);
1845 #endif
1846 continue;
1847 }
1848 if (btrfs_disk_key_type(&disk_key) ==
1849 BTRFS_EXTENT_REF_KEY) {
1850 ref = btrfs_item_ptr(buf, i,
1851 struct btrfs_extent_ref);
1852 add_extent_backref(extent_cache,
1853 btrfs_disk_key_objectid(&disk_key),
1854 btrfs_disk_key_offset(&disk_key),
1855 btrfs_ref_root(buf, ref),
1856 btrfs_ref_generation(buf, ref),
1857 btrfs_ref_objectid(buf, ref),
1858 btrfs_ref_num_refs(buf, ref), 0);
1859 continue;
1860 }
1861 if (btrfs_disk_key_type(&disk_key) !=
1862 BTRFS_EXTENT_DATA_KEY)
1863 continue;
1864 fi = btrfs_item_ptr(buf, i,
1865 struct btrfs_file_extent_item);
1866 if (btrfs_file_extent_type(buf, fi) ==
1867 BTRFS_FILE_EXTENT_INLINE)
1868 continue;
1869 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
1870 continue;
1871
1872 data_bytes_allocated +=
1873 btrfs_file_extent_disk_num_bytes(buf, fi);
1874 if (data_bytes_allocated < root->sectorsize) {
1875 abort();
1876 }
1877 data_bytes_referenced +=
1878 btrfs_file_extent_num_bytes(buf, fi);
1879 ret = add_extent_rec(extent_cache, NULL, bytenr,
1880 btrfs_file_extent_disk_bytenr(buf, fi),
1881 btrfs_file_extent_disk_num_bytes(buf, fi),
1882 0, 1, 1);
1883 add_extent_backref(extent_cache,
1884 btrfs_file_extent_disk_bytenr(buf, fi),
1885 buf->start, btrfs_header_owner(buf),
1886 btrfs_header_generation(buf),
1887 btrfs_disk_key_objectid(&disk_key), 1, 1);
1888 BUG_ON(ret);
1889 }
1890 } else {
1891 int level;
1892 level = btrfs_header_level(buf);
1893 for (i = 0; i < nritems; i++) {
1894 u64 ptr = btrfs_node_blockptr(buf, i);
1895 u32 size = btrfs_level_size(root, level - 1);
1896 btrfs_node_key(buf, &disk_key, i);
1897 ret = add_extent_rec(extent_cache,
1898 &disk_key,
1899 bytenr, ptr, size,
1900 0, 1, 0);
1901 BUG_ON(ret);
1902
1903 add_extent_backref(extent_cache, ptr,
1904 buf->start, btrfs_header_owner(buf),
1905 btrfs_header_generation(buf),
1906 level - 1, 1, 1);
1907
1908 if (level > 1) {
1909 add_pending(nodes, seen, ptr, size);
1910 } else {
1911 add_pending(pending, seen, ptr, size);
1912 }
1913 }
1914 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
1915 nritems) * sizeof(struct btrfs_key_ptr);
1916 }
1917 total_btree_bytes += buf->len;
1918 free_extent_buffer(buf);
1919 return 0;
1920 }
1921
1922 static int add_root_to_pending(struct extent_buffer *buf,
1923 struct block_info *bits,
1924 int bits_nr,
1925 struct cache_tree *extent_cache,
1926 struct cache_tree *pending,
1927 struct cache_tree *seen,
1928 struct cache_tree *reada,
1929 struct cache_tree *nodes, u64 root_objectid)
1930 {
1931 if (btrfs_header_level(buf) > 0)
1932 add_pending(nodes, seen, buf->start, buf->len);
1933 else
1934 add_pending(pending, seen, buf->start, buf->len);
1935 add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
1936 0, 1, 0);
1937
1938 add_extent_backref(extent_cache, buf->start, buf->start,
1939 root_objectid, btrfs_header_generation(buf),
1940 btrfs_header_level(buf), 1, 1);
1941 return 0;
1942 }
1943
1944 static int check_extent_refs(struct btrfs_root *root,
1945 struct cache_tree *extent_cache)
1946 {
1947 struct extent_record *rec;
1948 struct cache_extent *cache;
1949 int err = 0;
1950
1951 while(1) {
1952 cache = find_first_cache_extent(extent_cache, 0);
1953 if (!cache)
1954 break;
1955 rec = container_of(cache, struct extent_record, cache);
1956 if (rec->refs != rec->extent_item_refs) {
1957 fprintf(stderr, "ref mismatch on [%llu %llu] ",
1958 (unsigned long long)rec->start,
1959 (unsigned long long)rec->nr);
1960 fprintf(stderr, "extent item %u, found %u\n",
1961 rec->extent_item_refs,
1962 rec->refs);
1963 err = 1;
1964 }
1965 if (all_backpointers_checked(rec, 1)) {
1966 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
1967 (unsigned long long)rec->start,
1968 (unsigned long long)rec->nr);
1969
1970 err = 1;
1971 }
1972 remove_cache_extent(extent_cache, cache);
1973 free_all_extent_backrefs(rec);
1974 free(rec);
1975 }
1976 return err;
1977 }
1978
1979 static int check_extents(struct btrfs_root *root)
1980 {
1981 struct cache_tree extent_cache;
1982 struct cache_tree seen;
1983 struct cache_tree pending;
1984 struct cache_tree reada;
1985 struct cache_tree nodes;
1986 struct btrfs_path path;
1987 struct btrfs_key key;
1988 struct btrfs_key found_key;
1989 int ret;
1990 u64 last = 0;
1991 struct block_info *bits;
1992 int bits_nr;
1993 struct extent_buffer *leaf;
1994 int slot;
1995 struct btrfs_root_item ri;
1996
1997 cache_tree_init(&extent_cache);
1998 cache_tree_init(&seen);
1999 cache_tree_init(&pending);
2000 cache_tree_init(&nodes);
2001 cache_tree_init(&reada);
2002
2003 bits_nr = 1024;
2004 bits = malloc(bits_nr * sizeof(struct block_info));
2005 if (!bits) {
2006 perror("malloc");
2007 exit(1);
2008 }
2009
2010 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2011 &extent_cache, &pending, &seen, &reada, &nodes,
2012 root->fs_info->tree_root->root_key.objectid);
2013
2014 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2015 &extent_cache, &pending, &seen, &reada, &nodes,
2016 root->fs_info->chunk_root->root_key.objectid);
2017
2018 btrfs_init_path(&path);
2019 key.offset = 0;
2020 key.objectid = 0;
2021 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2022 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2023 &key, &path, 0, 0);
2024 BUG_ON(ret < 0);
2025 while(1) {
2026 leaf = path.nodes[0];
2027 slot = path.slots[0];
2028 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2029 ret = btrfs_next_leaf(root, &path);
2030 if (ret != 0)
2031 break;
2032 leaf = path.nodes[0];
2033 slot = path.slots[0];
2034 }
2035 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2036 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2037 unsigned long offset;
2038 struct extent_buffer *buf;
2039
2040 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2041 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2042 buf = read_tree_block(root->fs_info->tree_root,
2043 btrfs_root_bytenr(&ri),
2044 btrfs_level_size(root,
2045 btrfs_root_level(&ri)), 0);
2046 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2047 &pending, &seen, &reada, &nodes,
2048 found_key.objectid);
2049 free_extent_buffer(buf);
2050 }
2051 path.slots[0]++;
2052 }
2053 btrfs_release_path(root, &path);
2054 while(1) {
2055 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2056 &seen, &reada, &nodes, &extent_cache);
2057 if (ret != 0)
2058 break;
2059 }
2060 ret = check_extent_refs(root, &extent_cache);
2061 return ret;
2062 }
2063
2064 static void print_usage(void)
2065 {
2066 fprintf(stderr, "usage: btrfsck dev\n");
2067 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2068 exit(1);
2069 }
2070
2071 int main(int ac, char **av)
2072 {
2073 struct btrfs_root *root;
2074 int ret;
2075
2076 if (ac < 2)
2077 print_usage();
2078
2079 radix_tree_init();
2080 root = open_ctree(av[1], 0, 0);
2081
2082 if (root == NULL)
2083 return 1;
2084
2085 ret = check_extents(root);
2086 if (ret)
2087 goto out;
2088 ret = check_fs_roots(root);
2089
2090 out:
2091 close_ctree(root);
2092 printf("found %llu bytes used err is %d\n",
2093 (unsigned long long)bytes_used, ret);
2094 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2095 printf("total tree bytes: %llu\n",
2096 (unsigned long long)total_btree_bytes);
2097 printf("btree space waste bytes: %llu\n",
2098 (unsigned long long)btree_space_waste);
2099 printf("file data blocks allocated: %llu\n referenced %llu\n",
2100 (unsigned long long)data_bytes_allocated,
2101 (unsigned long long)data_bytes_referenced);
2102 printf("%s\n", BTRFS_BUILD_VERSION);
2103 return ret;
2104 }
(deprecated) Btrfs progs developments and patch integration