?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add new defrag range ioctl that can also compress files on demand.
[btrfs-progs-unstable/devel.git] / btrfsck.c
blob73f1836eb3b28e9e2428854b57573871ff57904f
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 total_fs_tree_bytes = 0;
36 static u64 btree_space_waste = 0;
37 static u64 data_bytes_allocated = 0;
38 static u64 data_bytes_referenced = 0;
39 static int found_old_backref = 0;
40
41 struct extent_backref {
42 struct list_head list;
43 unsigned int is_data:1;
44 unsigned int found_extent_tree:1;
45 unsigned int full_backref:1;
46 unsigned int found_ref:1;
47 };
48
49 struct data_backref {
50 struct extent_backref node;
51 union {
52 u64 parent;
53 u64 root;
54 };
55 u64 owner;
56 u64 offset;
57 u32 num_refs;
58 u32 found_ref;
59 };
60
61 struct tree_backref {
62 struct extent_backref node;
63 union {
64 u64 parent;
65 u64 root;
66 };
67 };
68
69 struct extent_record {
70 struct list_head backrefs;
71 struct cache_extent cache;
72 struct btrfs_disk_key parent_key;
73 u64 start;
74 u64 nr;
75 u64 refs;
76 u64 extent_item_refs;
77 unsigned int content_checked:1;
78 unsigned int owner_ref_checked:1;
79 unsigned int is_root:1;
80 };
81
82 struct inode_backref {
83 struct list_head list;
84 unsigned int found_dir_item:1;
85 unsigned int found_dir_index:1;
86 unsigned int found_inode_ref:1;
87 unsigned int filetype:8;
88 int errors;
89 u64 dir;
90 u64 index;
91 u16 namelen;
92 char name[0];
93 };
94
95 #define REF_ERR_NO_DIR_ITEM (1 << 0)
96 #define REF_ERR_NO_DIR_INDEX (1 << 1)
97 #define REF_ERR_NO_INODE_REF (1 << 2)
98 #define REF_ERR_DUP_DIR_ITEM (1 << 3)
99 #define REF_ERR_DUP_DIR_INDEX (1 << 4)
100 #define REF_ERR_DUP_INODE_REF (1 << 5)
101 #define REF_ERR_INDEX_UNMATCH (1 << 6)
102 #define REF_ERR_FILETYPE_UNMATCH (1 << 7)
103 #define REF_ERR_NAME_TOO_LONG (1 << 8) // 100
104 #define REF_ERR_NO_ROOT_REF (1 << 9)
105 #define REF_ERR_NO_ROOT_BACKREF (1 << 10)
106 #define REF_ERR_DUP_ROOT_REF (1 << 11)
107 #define REF_ERR_DUP_ROOT_BACKREF (1 << 12)
108
109 struct inode_record {
110 struct list_head backrefs;
111 unsigned int checked:1;
112 unsigned int merging:1;
113 unsigned int found_inode_item:1;
114 unsigned int found_dir_item:1;
115 unsigned int found_file_extent:1;
116 unsigned int found_csum_item:1;
117 unsigned int some_csum_missing:1;
118 unsigned int nodatasum:1;
119 int errors;
120
121 u64 ino;
122 u32 nlink;
123 u32 imode;
124 u64 isize;
125 u64 nbytes;
126
127 u32 found_link;
128 u64 found_size;
129 u64 extent_start;
130 u64 extent_end;
131 u64 first_extent_gap;
132
133 u32 refs;
134 };
135
136 #define I_ERR_NO_INODE_ITEM (1 << 0)
137 #define I_ERR_NO_ORPHAN_ITEM (1 << 1)
138 #define I_ERR_DUP_INODE_ITEM (1 << 2)
139 #define I_ERR_DUP_DIR_INDEX (1 << 3)
140 #define I_ERR_ODD_DIR_ITEM (1 << 4)
141 #define I_ERR_ODD_FILE_EXTENT (1 << 5)
142 #define I_ERR_BAD_FILE_EXTENT (1 << 6)
143 #define I_ERR_FILE_EXTENT_OVERLAP (1 << 7)
144 #define I_ERR_FILE_EXTENT_DISCOUNT (1 << 8) // 100
145 #define I_ERR_DIR_ISIZE_WRONG (1 << 9)
146 #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400
147 #define I_ERR_ODD_CSUM_ITEM (1 << 11)
148 #define I_ERR_SOME_CSUM_MISSING (1 << 12)
149 #define I_ERR_LINK_COUNT_WRONG (1 << 13)
150
151 struct root_backref {
152 struct list_head list;
153 unsigned int found_dir_item:1;
154 unsigned int found_dir_index:1;
155 unsigned int found_back_ref:1;
156 unsigned int found_forward_ref:1;
157 unsigned int reachable:1;
158 int errors;
159 u64 ref_root;
160 u64 dir;
161 u64 index;
162 u16 namelen;
163 char name[0];
164 };
165
166 struct root_record {
167 struct list_head backrefs;
168 struct cache_extent cache;
169 unsigned int found_root_item:1;
170 u64 objectid;
171 u32 found_ref;
172 };
173
174 struct ptr_node {
175 struct cache_extent cache;
176 void *data;
177 };
178
179 struct shared_node {
180 struct cache_extent cache;
181 struct cache_tree root_cache;
182 struct cache_tree inode_cache;
183 struct inode_record *current;
184 u32 refs;
185 };
186
187 struct block_info {
188 u64 start;
189 u32 size;
190 };
191
192 struct walk_control {
193 struct cache_tree shared;
194 struct shared_node *nodes[BTRFS_MAX_LEVEL];
195 int active_node;
196 int root_level;
197 };
198
199 static u8 imode_to_type(u32 imode)
200 {
201 #define S_SHIFT 12
202 static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
203 [S_IFREG >> S_SHIFT] = BTRFS_FT_REG_FILE,
204 [S_IFDIR >> S_SHIFT] = BTRFS_FT_DIR,
205 [S_IFCHR >> S_SHIFT] = BTRFS_FT_CHRDEV,
206 [S_IFBLK >> S_SHIFT] = BTRFS_FT_BLKDEV,
207 [S_IFIFO >> S_SHIFT] = BTRFS_FT_FIFO,
208 [S_IFSOCK >> S_SHIFT] = BTRFS_FT_SOCK,
209 [S_IFLNK >> S_SHIFT] = BTRFS_FT_SYMLINK,
210 };
211
212 return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
213 #undef S_SHIFT
214 }
215
216 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
217 {
218 struct inode_record *rec;
219 struct inode_backref *backref;
220 struct inode_backref *orig;
221 size_t size;
222
223 rec = malloc(sizeof(*rec));
224 memcpy(rec, orig_rec, sizeof(*rec));
225 rec->refs = 1;
226 INIT_LIST_HEAD(&rec->backrefs);
227
228 list_for_each_entry(orig, &orig_rec->backrefs, list) {
229 size = sizeof(*orig) + orig->namelen + 1;
230 backref = malloc(size);
231 memcpy(backref, orig, size);
232 list_add_tail(&backref->list, &rec->backrefs);
233 }
234 return rec;
235 }
236
237 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
238 u64 ino, int mod)
239 {
240 struct ptr_node *node;
241 struct cache_extent *cache;
242 struct inode_record *rec = NULL;
243 int ret;
244
245 cache = find_cache_extent(inode_cache, ino, 1);
246 if (cache) {
247 node = container_of(cache, struct ptr_node, cache);
248 rec = node->data;
249 if (mod && rec->refs > 1) {
250 node->data = clone_inode_rec(rec);
251 rec->refs--;
252 rec = node->data;
253 }
254 } else if (mod) {
255 rec = calloc(1, sizeof(*rec));
256 rec->ino = ino;
257 rec->extent_start = (u64)-1;
258 rec->first_extent_gap = (u64)-1;
259 rec->refs = 1;
260 INIT_LIST_HEAD(&rec->backrefs);
261
262 node = malloc(sizeof(*node));
263 node->cache.start = ino;
264 node->cache.size = 1;
265 node->data = rec;
266
267 ret = insert_existing_cache_extent(inode_cache, &node->cache);
268 BUG_ON(ret);
269 }
270 return rec;
271 }
272
273 static void free_inode_rec(struct inode_record *rec)
274 {
275 struct inode_backref *backref;
276
277 if (--rec->refs > 0)
278 return;
279
280 while (!list_empty(&rec->backrefs)) {
281 backref = list_entry(rec->backrefs.next,
282 struct inode_backref, list);
283 list_del(&backref->list);
284 free(backref);
285 }
286 free(rec);
287 }
288
289 static int can_free_inode_rec(struct inode_record *rec)
290 {
291 if (!rec->errors && rec->checked && rec->found_inode_item &&
292 rec->nlink == rec->found_link && list_empty(&rec->backrefs))
293 return 1;
294 return 0;
295 }
296
297 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
298 struct inode_record *rec)
299 {
300 struct cache_extent *cache;
301 struct inode_backref *tmp, *backref;
302 struct ptr_node *node;
303 unsigned char filetype;
304
305 if (!rec->found_inode_item)
306 return;
307
308 filetype = imode_to_type(rec->imode);
309 list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
310 if (backref->found_dir_item && backref->found_dir_index) {
311 if (backref->filetype != filetype)
312 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
313 if (!backref->errors && backref->found_inode_ref) {
314 list_del(&backref->list);
315 free(backref);
316 }
317 }
318 }
319
320 if (!rec->checked || rec->merging)
321 return;
322
323 if (S_ISDIR(rec->imode)) {
324 if (rec->found_size != rec->isize)
325 rec->errors |= I_ERR_DIR_ISIZE_WRONG;
326 if (rec->found_file_extent)
327 rec->errors |= I_ERR_ODD_FILE_EXTENT;
328 } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
329 if (rec->found_dir_item)
330 rec->errors |= I_ERR_ODD_DIR_ITEM;
331 if (rec->found_size != rec->nbytes)
332 rec->errors |= I_ERR_FILE_NBYTES_WRONG;
333 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
334 rec->first_extent_gap = 0;
335 if (rec->nlink > 0 && (rec->extent_end < rec->isize ||
336 rec->first_extent_gap < rec->isize))
337 rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
338 }
339
340 if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
341 if (rec->found_csum_item && rec->nodatasum)
342 rec->errors |= I_ERR_ODD_CSUM_ITEM;
343 if (rec->some_csum_missing && !rec->nodatasum)
344 rec->errors |= I_ERR_SOME_CSUM_MISSING;
345 }
346
347 BUG_ON(rec->refs != 1);
348 if (can_free_inode_rec(rec)) {
349 cache = find_cache_extent(inode_cache, rec->ino, 1);
350 node = container_of(cache, struct ptr_node, cache);
351 BUG_ON(node->data != rec);
352 remove_cache_extent(inode_cache, &node->cache);
353 free(node);
354 free_inode_rec(rec);
355 }
356 }
357
358 static int check_orphan_item(struct btrfs_root *root, u64 ino)
359 {
360 struct btrfs_path path;
361 struct btrfs_key key;
362 int ret;
363
364 key.objectid = BTRFS_ORPHAN_OBJECTID;
365 key.type = BTRFS_ORPHAN_ITEM_KEY;
366 key.offset = ino;
367
368 btrfs_init_path(&path);
369 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
370 btrfs_release_path(root, &path);
371 if (ret > 0)
372 ret = -ENOENT;
373 return ret;
374 }
375
376 static int process_inode_item(struct extent_buffer *eb,
377 int slot, struct btrfs_key *key,
378 struct shared_node *active_node)
379 {
380 struct inode_record *rec;
381 struct btrfs_inode_item *item;
382
383 rec = active_node->current;
384 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
385 if (rec->found_inode_item) {
386 rec->errors |= I_ERR_DUP_INODE_ITEM;
387 return 1;
388 }
389 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
390 rec->nlink = btrfs_inode_nlink(eb, item);
391 rec->isize = btrfs_inode_size(eb, item);
392 rec->nbytes = btrfs_inode_nbytes(eb, item);
393 rec->imode = btrfs_inode_mode(eb, item);
394 if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
395 rec->nodatasum = 1;
396 rec->found_inode_item = 1;
397 if (rec->nlink == 0)
398 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
399 maybe_free_inode_rec(&active_node->inode_cache, rec);
400 return 0;
401 }
402
403 static struct inode_backref *get_inode_backref(struct inode_record *rec,
404 const char *name,
405 int namelen, u64 dir)
406 {
407 struct inode_backref *backref;
408
409 list_for_each_entry(backref, &rec->backrefs, list) {
410 if (backref->dir != dir || backref->namelen != namelen)
411 continue;
412 if (memcmp(name, backref->name, namelen))
413 continue;
414 return backref;
415 }
416
417 backref = malloc(sizeof(*backref) + namelen + 1);
418 memset(backref, 0, sizeof(*backref));
419 backref->dir = dir;
420 backref->namelen = namelen;
421 memcpy(backref->name, name, namelen);
422 backref->name[namelen] = '\0';
423 list_add_tail(&backref->list, &rec->backrefs);
424 rec->found_link++;
425 return backref;
426 }
427
428 static int add_inode_backref(struct cache_tree *inode_cache,
429 u64 ino, u64 dir, u64 index,
430 const char *name, int namelen,
431 int filetype, int itemtype, int errors)
432 {
433 struct inode_record *rec;
434 struct inode_backref *backref;
435
436 rec = get_inode_rec(inode_cache, ino, 1);
437 backref = get_inode_backref(rec, name, namelen, dir);
438 if (errors)
439 backref->errors |= errors;
440 if (itemtype == BTRFS_DIR_INDEX_KEY) {
441 if (backref->found_dir_index)
442 backref->errors |= REF_ERR_DUP_DIR_INDEX;
443 if (backref->found_inode_ref && backref->index != index)
444 backref->errors |= REF_ERR_INDEX_UNMATCH;
445 if (backref->found_dir_item && backref->filetype != filetype)
446 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
447
448 backref->index = index;
449 backref->filetype = filetype;
450 backref->found_dir_index = 1;
451 } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
452 if (backref->found_dir_item)
453 backref->errors |= REF_ERR_DUP_DIR_ITEM;
454 if (backref->found_dir_index && backref->filetype != filetype)
455 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
456
457 backref->filetype = filetype;
458 backref->found_dir_item = 1;
459 } else if (itemtype == BTRFS_INODE_REF_KEY) {
460 if (backref->found_inode_ref)
461 backref->errors |= REF_ERR_DUP_INODE_REF;
462 if (backref->found_dir_index && backref->index != index)
463 backref->errors |= REF_ERR_INDEX_UNMATCH;
464
465 backref->index = index;
466 backref->found_inode_ref = 1;
467 } else {
468 BUG_ON(1);
469 }
470
471 maybe_free_inode_rec(inode_cache, rec);
472 return 0;
473 }
474
475 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
476 struct cache_tree *dst_cache)
477 {
478 struct inode_backref *backref;
479
480 dst->merging = 1;
481 list_for_each_entry(backref, &src->backrefs, list) {
482 if (backref->found_dir_index) {
483 add_inode_backref(dst_cache, dst->ino, backref->dir,
484 backref->index, backref->name,
485 backref->namelen, backref->filetype,
486 BTRFS_DIR_INDEX_KEY, backref->errors);
487 }
488 if (backref->found_dir_item) {
489 add_inode_backref(dst_cache, dst->ino,
490 backref->dir, 0, backref->name,
491 backref->namelen, backref->filetype,
492 BTRFS_DIR_ITEM_KEY, backref->errors);
493 }
494 if (backref->found_inode_ref) {
495 add_inode_backref(dst_cache, dst->ino,
496 backref->dir, backref->index,
497 backref->name, backref->namelen, 0,
498 BTRFS_INODE_REF_KEY, backref->errors);
499 }
500 }
501
502 if (src->found_dir_item)
503 dst->found_dir_item = 1;
504 if (src->found_file_extent)
505 dst->found_file_extent = 1;
506 if (src->found_csum_item)
507 dst->found_csum_item = 1;
508 if (src->some_csum_missing)
509 dst->some_csum_missing = 1;
510 if (dst->first_extent_gap > src->first_extent_gap)
511 dst->first_extent_gap = src->first_extent_gap;
512
513 dst->found_size += src->found_size;
514 if (src->extent_start != (u64)-1) {
515 if (dst->extent_start == (u64)-1) {
516 dst->extent_start = src->extent_start;
517 dst->extent_end = src->extent_end;
518 } else {
519 if (dst->extent_end > src->extent_start)
520 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
521 else if (dst->extent_end < src->extent_start &&
522 dst->extent_end < dst->first_extent_gap)
523 dst->first_extent_gap = dst->extent_end;
524 if (dst->extent_end < src->extent_end)
525 dst->extent_end = src->extent_end;
526 }
527 }
528
529 dst->errors |= src->errors;
530 if (src->found_inode_item) {
531 if (!dst->found_inode_item) {
532 dst->nlink = src->nlink;
533 dst->isize = src->isize;
534 dst->nbytes = src->nbytes;
535 dst->imode = src->imode;
536 dst->nodatasum = src->nodatasum;
537 dst->found_inode_item = 1;
538 } else {
539 dst->errors |= I_ERR_DUP_INODE_ITEM;
540 }
541 }
542 dst->merging = 0;
543
544 return 0;
545 }
546
547 static int splice_shared_node(struct shared_node *src_node,
548 struct shared_node *dst_node)
549 {
550 struct cache_extent *cache;
551 struct ptr_node *node, *ins;
552 struct cache_tree *src, *dst;
553 struct inode_record *rec, *conflict;
554 u64 current_ino = 0;
555 int splice = 0;
556 int ret;
557
558 if (--src_node->refs == 0)
559 splice = 1;
560 if (src_node->current)
561 current_ino = src_node->current->ino;
562
563 src = &src_node->root_cache;
564 dst = &dst_node->root_cache;
565 again:
566 cache = find_first_cache_extent(src, 0);
567 while (cache) {
568 node = container_of(cache, struct ptr_node, cache);
569 rec = node->data;
570 cache = next_cache_extent(cache);
571
572 if (splice) {
573 remove_cache_extent(src, &node->cache);
574 ins = node;
575 } else {
576 ins = malloc(sizeof(*ins));
577 ins->cache.start = node->cache.start;
578 ins->cache.size = node->cache.size;
579 ins->data = rec;
580 rec->refs++;
581 }
582 ret = insert_existing_cache_extent(dst, &ins->cache);
583 if (ret == -EEXIST) {
584 WARN_ON(src == &src_node->root_cache);
585 conflict = get_inode_rec(dst, rec->ino, 1);
586 merge_inode_recs(rec, conflict, dst);
587 if (rec->checked) {
588 conflict->checked = 1;
589 if (dst_node->current == conflict)
590 dst_node->current = NULL;
591 }
592 maybe_free_inode_rec(dst, conflict);
593 free_inode_rec(rec);
594 free(ins);
595 } else {
596 BUG_ON(ret);
597 }
598 }
599
600 if (src == &src_node->root_cache) {
601 src = &src_node->inode_cache;
602 dst = &dst_node->inode_cache;
603 goto again;
604 }
605
606 if (current_ino > 0 && (!dst_node->current ||
607 current_ino > dst_node->current->ino)) {
608 if (dst_node->current) {
609 dst_node->current->checked = 1;
610 maybe_free_inode_rec(dst, dst_node->current);
611 }
612 dst_node->current = get_inode_rec(dst, current_ino, 1);
613 }
614 return 0;
615 }
616
617 static void free_inode_recs(struct cache_tree *inode_cache)
618 {
619 struct cache_extent *cache;
620 struct ptr_node *node;
621 struct inode_record *rec;
622
623 while (1) {
624 cache = find_first_cache_extent(inode_cache, 0);
625 if (!cache)
626 break;
627 node = container_of(cache, struct ptr_node, cache);
628 rec = node->data;
629 remove_cache_extent(inode_cache, &node->cache);
630 free(node);
631 free_inode_rec(rec);
632 }
633 }
634
635 static struct shared_node *find_shared_node(struct cache_tree *shared,
636 u64 bytenr)
637 {
638 struct cache_extent *cache;
639 struct shared_node *node;
640
641 cache = find_cache_extent(shared, bytenr, 1);
642 if (cache) {
643 node = container_of(cache, struct shared_node, cache);
644 return node;
645 }
646 return NULL;
647 }
648
649 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
650 {
651 int ret;
652 struct shared_node *node;
653
654 node = calloc(1, sizeof(*node));
655 node->cache.start = bytenr;
656 node->cache.size = 1;
657 cache_tree_init(&node->root_cache);
658 cache_tree_init(&node->inode_cache);
659 node->refs = refs;
660
661 ret = insert_existing_cache_extent(shared, &node->cache);
662 BUG_ON(ret);
663 return 0;
664 }
665
666 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
667 struct walk_control *wc, int level)
668 {
669 struct shared_node *node;
670 struct shared_node *dest;
671
672 if (level == wc->active_node)
673 return 0;
674
675 BUG_ON(wc->active_node <= level);
676 node = find_shared_node(&wc->shared, bytenr);
677 if (!node) {
678 add_shared_node(&wc->shared, bytenr, refs);
679 node = find_shared_node(&wc->shared, bytenr);
680 wc->nodes[level] = node;
681 wc->active_node = level;
682 return 0;
683 }
684
685 if (wc->root_level == wc->active_node &&
686 btrfs_root_refs(&root->root_item) == 0) {
687 if (--node->refs == 0) {
688 free_inode_recs(&node->root_cache);
689 free_inode_recs(&node->inode_cache);
690 remove_cache_extent(&wc->shared, &node->cache);
691 free(node);
692 }
693 return 1;
694 }
695
696 dest = wc->nodes[wc->active_node];
697 splice_shared_node(node, dest);
698 if (node->refs == 0) {
699 remove_cache_extent(&wc->shared, &node->cache);
700 free(node);
701 }
702 return 1;
703 }
704
705 static int leave_shared_node(struct btrfs_root *root,
706 struct walk_control *wc, int level)
707 {
708 struct shared_node *node;
709 struct shared_node *dest;
710 int i;
711
712 if (level == wc->root_level)
713 return 0;
714
715 for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
716 if (wc->nodes[i])
717 break;
718 }
719 BUG_ON(i >= BTRFS_MAX_LEVEL);
720
721 node = wc->nodes[wc->active_node];
722 wc->nodes[wc->active_node] = NULL;
723 wc->active_node = i;
724
725 dest = wc->nodes[wc->active_node];
726 if (wc->active_node < wc->root_level ||
727 btrfs_root_refs(&root->root_item) > 0) {
728 BUG_ON(node->refs <= 1);
729 splice_shared_node(node, dest);
730 } else {
731 BUG_ON(node->refs < 2);
732 node->refs--;
733 }
734 return 0;
735 }
736
737 static int process_dir_item(struct extent_buffer *eb,
738 int slot, struct btrfs_key *key,
739 struct shared_node *active_node)
740 {
741 u32 total;
742 u32 cur = 0;
743 u32 len;
744 u32 name_len;
745 u32 data_len;
746 int error;
747 int nritems = 0;
748 int filetype;
749 struct btrfs_dir_item *di;
750 struct inode_record *rec;
751 struct cache_tree *root_cache;
752 struct cache_tree *inode_cache;
753 struct btrfs_key location;
754 char namebuf[BTRFS_NAME_LEN];
755
756 root_cache = &active_node->root_cache;
757 inode_cache = &active_node->inode_cache;
758 rec = active_node->current;
759 rec->found_dir_item = 1;
760
761 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
762 total = btrfs_item_size_nr(eb, slot);
763 while (cur < total) {
764 nritems++;
765 btrfs_dir_item_key_to_cpu(eb, di, &location);
766 name_len = btrfs_dir_name_len(eb, di);
767 data_len = btrfs_dir_data_len(eb, di);
768 filetype = btrfs_dir_type(eb, di);
769
770 rec->found_size += name_len;
771 if (name_len <= BTRFS_NAME_LEN) {
772 len = name_len;
773 error = 0;
774 } else {
775 len = BTRFS_NAME_LEN;
776 error = REF_ERR_NAME_TOO_LONG;
777 }
778 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
779
780 if (location.type == BTRFS_INODE_ITEM_KEY) {
781 add_inode_backref(inode_cache, location.objectid,
782 key->objectid, key->offset, namebuf,
783 len, filetype, key->type, error);
784 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
785 add_inode_backref(root_cache, location.objectid,
786 key->objectid, key->offset, namebuf,
787 len, filetype, key->type, error);
788 } else {
789 fprintf(stderr, "warning line %d\n", __LINE__);
790 }
791
792 len = sizeof(*di) + name_len + data_len;
793 di = (struct btrfs_dir_item *)((char *)di + len);
794 cur += len;
795 }
796 if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
797 rec->errors |= I_ERR_DUP_DIR_INDEX;
798
799 return 0;
800 }
801
802 static int process_inode_ref(struct extent_buffer *eb,
803 int slot, struct btrfs_key *key,
804 struct shared_node *active_node)
805 {
806 u32 total;
807 u32 cur = 0;
808 u32 len;
809 u32 name_len;
810 u64 index;
811 int error;
812 struct cache_tree *inode_cache;
813 struct btrfs_inode_ref *ref;
814 char namebuf[BTRFS_NAME_LEN];
815
816 inode_cache = &active_node->inode_cache;
817
818 ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
819 total = btrfs_item_size_nr(eb, slot);
820 while (cur < total) {
821 name_len = btrfs_inode_ref_name_len(eb, ref);
822 index = btrfs_inode_ref_index(eb, ref);
823 if (name_len <= BTRFS_NAME_LEN) {
824 len = name_len;
825 error = 0;
826 } else {
827 len = BTRFS_NAME_LEN;
828 error = REF_ERR_NAME_TOO_LONG;
829 }
830 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
831 add_inode_backref(inode_cache, key->objectid, key->offset,
832 index, namebuf, len, 0, key->type, error);
833
834 len = sizeof(*ref) + name_len;
835 ref = (struct btrfs_inode_ref *)((char *)ref + len);
836 cur += len;
837 }
838 return 0;
839 }
840
841 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
842 {
843 struct btrfs_key key;
844 struct btrfs_path path;
845 struct extent_buffer *leaf;
846 int ret ;
847 size_t size;
848 u64 found = 0;
849 u64 csum_end;
850 u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
851
852 btrfs_init_path(&path);
853
854 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
855 key.offset = start;
856 key.type = BTRFS_EXTENT_CSUM_KEY;
857
858 ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
859 &key, &path, 0, 0);
860 BUG_ON(ret < 0);
861 if (ret > 0 && path.slots[0] > 0) {
862 leaf = path.nodes[0];
863 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
864 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
865 key.type == BTRFS_EXTENT_CSUM_KEY)
866 path.slots[0]--;
867 }
868
869 while (len > 0) {
870 leaf = path.nodes[0];
871 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
872 ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
873 BUG_ON(ret < 0);
874 if (ret > 0)
875 break;
876 leaf = path.nodes[0];
877 }
878
879 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
880 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
881 key.type != BTRFS_EXTENT_CSUM_KEY)
882 break;
883
884 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
885 if (key.offset >= start + len)
886 break;
887
888 if (key.offset > start)
889 start = key.offset;
890
891 size = btrfs_item_size_nr(leaf, path.slots[0]);
892 csum_end = key.offset + (size / csum_size) * root->sectorsize;
893 if (csum_end > start) {
894 size = min(csum_end - start, len);
895 len -= size;
896 start += size;
897 found += size;
898 }
899
900 path.slots[0]++;
901 }
902 btrfs_release_path(root->fs_info->csum_root, &path);
903 return found;
904 }
905
906 static int process_file_extent(struct btrfs_root *root,
907 struct extent_buffer *eb,
908 int slot, struct btrfs_key *key,
909 struct shared_node *active_node)
910 {
911 struct inode_record *rec;
912 struct btrfs_file_extent_item *fi;
913 u64 num_bytes = 0;
914 u64 disk_bytenr = 0;
915 u64 extent_offset = 0;
916 u64 mask = root->sectorsize - 1;
917 int extent_type;
918
919 rec = active_node->current;
920 BUG_ON(rec->ino != key->objectid || rec->refs > 1);
921 rec->found_file_extent = 1;
922
923 if (rec->extent_start == (u64)-1) {
924 rec->extent_start = key->offset;
925 rec->extent_end = key->offset;
926 }
927
928 if (rec->extent_end > key->offset)
929 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
930 else if (rec->extent_end < key->offset &&
931 rec->extent_end < rec->first_extent_gap)
932 rec->first_extent_gap = rec->extent_end;
933
934 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
935 extent_type = btrfs_file_extent_type(eb, fi);
936
937 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
938 num_bytes = btrfs_file_extent_inline_len(eb, fi);
939 if (num_bytes == 0)
940 rec->errors |= I_ERR_BAD_FILE_EXTENT;
941 rec->found_size += num_bytes;
942 num_bytes = (num_bytes + mask) & ~mask;
943 } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
944 extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
945 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
946 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
947 extent_offset = btrfs_file_extent_offset(eb, fi);
948 if (num_bytes == 0 || (num_bytes & mask))
949 rec->errors |= I_ERR_BAD_FILE_EXTENT;
950 if (num_bytes + extent_offset >
951 btrfs_file_extent_ram_bytes(eb, fi))
952 rec->errors |= I_ERR_BAD_FILE_EXTENT;
953 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
954 (btrfs_file_extent_compression(eb, fi) ||
955 btrfs_file_extent_encryption(eb, fi) ||
956 btrfs_file_extent_other_encoding(eb, fi)))
957 rec->errors |= I_ERR_BAD_FILE_EXTENT;
958 if (disk_bytenr > 0)
959 rec->found_size += num_bytes;
960 } else {
961 rec->errors |= I_ERR_BAD_FILE_EXTENT;
962 }
963 rec->extent_end = key->offset + num_bytes;
964
965 if (disk_bytenr > 0) {
966 u64 found;
967 if (btrfs_file_extent_compression(eb, fi))
968 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
969 else
970 disk_bytenr += extent_offset;
971
972 found = count_csum_range(root, disk_bytenr, num_bytes);
973 if (extent_type == BTRFS_FILE_EXTENT_REG) {
974 if (found > 0)
975 rec->found_csum_item = 1;
976 if (found < num_bytes)
977 rec->some_csum_missing = 1;
978 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
979 if (found > 0)
980 rec->errors |= I_ERR_ODD_CSUM_ITEM;
981 }
982 }
983 return 0;
984 }
985
986 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
987 struct walk_control *wc)
988 {
989 struct btrfs_key key;
990 u32 nritems;
991 int i;
992 int ret;
993 struct cache_tree *inode_cache;
994 struct shared_node *active_node;
995
996 if (wc->root_level == wc->active_node &&
997 btrfs_root_refs(&root->root_item) == 0)
998 return 0;
999
1000 active_node = wc->nodes[wc->active_node];
1001 inode_cache = &active_node->inode_cache;
1002 nritems = btrfs_header_nritems(eb);
1003 for (i = 0; i < nritems; i++) {
1004 btrfs_item_key_to_cpu(eb, &key, i);
1005 if (active_node->current == NULL ||
1006 active_node->current->ino < key.objectid) {
1007 if (active_node->current) {
1008 active_node->current->checked = 1;
1009 maybe_free_inode_rec(inode_cache,
1010 active_node->current);
1011 }
1012 active_node->current = get_inode_rec(inode_cache,
1013 key.objectid, 1);
1014 }
1015 switch (key.type) {
1016 case BTRFS_DIR_ITEM_KEY:
1017 case BTRFS_DIR_INDEX_KEY:
1018 ret = process_dir_item(eb, i, &key, active_node);
1019 break;
1020 case BTRFS_INODE_REF_KEY:
1021 ret = process_inode_ref(eb, i, &key, active_node);
1022 break;
1023 case BTRFS_INODE_ITEM_KEY:
1024 ret = process_inode_item(eb, i, &key, active_node);
1025 break;
1026 case BTRFS_EXTENT_DATA_KEY:
1027 ret = process_file_extent(root, eb, i, &key,
1028 active_node);
1029 break;
1030 default:
1031 break;
1032 };
1033 }
1034 return 0;
1035 }
1036
1037 static void reada_walk_down(struct btrfs_root *root,
1038 struct extent_buffer *node, int slot)
1039 {
1040 u64 bytenr;
1041 u64 ptr_gen;
1042 u32 nritems;
1043 u32 blocksize;
1044 int i;
1045 int ret;
1046 int level;
1047
1048 level = btrfs_header_level(node);
1049 if (level != 1)
1050 return;
1051
1052 nritems = btrfs_header_nritems(node);
1053 blocksize = btrfs_level_size(root, level - 1);
1054 for (i = slot; i < nritems; i++) {
1055 bytenr = btrfs_node_blockptr(node, i);
1056 ptr_gen = btrfs_node_ptr_generation(node, i);
1057 ret = readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1058 if (ret)
1059 break;
1060 }
1061 }
1062
1063 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1064 struct walk_control *wc, int *level)
1065 {
1066 u64 bytenr;
1067 u64 ptr_gen;
1068 struct extent_buffer *next;
1069 struct extent_buffer *cur;
1070 u32 blocksize;
1071 int ret;
1072 u64 refs;
1073
1074 WARN_ON(*level < 0);
1075 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1076 ret = btrfs_lookup_extent_info(NULL, root,
1077 path->nodes[*level]->start,
1078 path->nodes[*level]->len, &refs, NULL);
1079 BUG_ON(ret);
1080 if (refs > 1) {
1081 ret = enter_shared_node(root, path->nodes[*level]->start,
1082 refs, wc, *level);
1083 if (ret > 0)
1084 goto out;
1085 }
1086
1087 while (*level >= 0) {
1088 WARN_ON(*level < 0);
1089 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1090 cur = path->nodes[*level];
1091
1092 if (btrfs_header_level(cur) != *level)
1093 WARN_ON(1);
1094
1095 if (path->slots[*level] >= btrfs_header_nritems(cur))
1096 break;
1097 if (*level == 0) {
1098 ret = process_one_leaf(root, cur, wc);
1099 break;
1100 }
1101 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1102 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1103 blocksize = btrfs_level_size(root, *level - 1);
1104 ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize,
1105 &refs, NULL);
1106 BUG_ON(ret);
1107
1108 if (refs > 1) {
1109 ret = enter_shared_node(root, bytenr, refs,
1110 wc, *level - 1);
1111 if (ret > 0) {
1112 path->slots[*level]++;
1113 continue;
1114 }
1115 }
1116
1117 next = btrfs_find_tree_block(root, bytenr, blocksize);
1118 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1119 free_extent_buffer(next);
1120 reada_walk_down(root, cur, path->slots[*level]);
1121 next = read_tree_block(root, bytenr, blocksize,
1122 ptr_gen);
1123 }
1124
1125 *level = *level - 1;
1126 free_extent_buffer(path->nodes[*level]);
1127 path->nodes[*level] = next;
1128 path->slots[*level] = 0;
1129 }
1130 out:
1131 path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1132 return 0;
1133 }
1134
1135 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1136 struct walk_control *wc, int *level)
1137 {
1138 int i;
1139 struct extent_buffer *leaf;
1140
1141 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1142 leaf = path->nodes[i];
1143 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1144 path->slots[i]++;
1145 *level = i;
1146 return 0;
1147 } else {
1148 free_extent_buffer(path->nodes[*level]);
1149 path->nodes[*level] = NULL;
1150 BUG_ON(*level > wc->active_node);
1151 if (*level == wc->active_node)
1152 leave_shared_node(root, wc, *level);
1153 *level = i + 1;
1154 }
1155 }
1156 return 1;
1157 }
1158
1159 static int check_root_dir(struct inode_record *rec)
1160 {
1161 struct inode_backref *backref;
1162 int ret = -1;
1163
1164 if (!rec->found_inode_item || rec->errors)
1165 goto out;
1166 if (rec->nlink != 1 || rec->found_link != 1)
1167 goto out;
1168 if (list_empty(&rec->backrefs))
1169 goto out;
1170 backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1171 if (!backref->found_inode_ref)
1172 goto out;
1173 if (backref->index != 0 || backref->namelen != 2 ||
1174 memcmp(backref->name, "..", 2))
1175 goto out;
1176 if (backref->found_dir_index || backref->found_dir_item)
1177 goto out;
1178 ret = 0;
1179 out:
1180 return ret;
1181 }
1182
1183 static int check_inode_recs(struct btrfs_root *root,
1184 struct cache_tree *inode_cache)
1185 {
1186 struct cache_extent *cache;
1187 struct ptr_node *node;
1188 struct inode_record *rec;
1189 struct inode_backref *backref;
1190 int ret;
1191 u64 error = 0;
1192 u64 root_dirid = btrfs_root_dirid(&root->root_item);
1193
1194 if (btrfs_root_refs(&root->root_item) == 0) {
1195 if (!cache_tree_empty(inode_cache))
1196 fprintf(stderr, "warning line %d\n", __LINE__);
1197 return 0;
1198 }
1199
1200 rec = get_inode_rec(inode_cache, root_dirid, 0);
1201 if (rec) {
1202 ret = check_root_dir(rec);
1203 if (ret) {
1204 fprintf(stderr, "root %llu root dir %llu error\n",
1205 (unsigned long long)root->root_key.objectid,
1206 (unsigned long long)root_dirid);
1207 error++;
1208 }
1209 } else {
1210 fprintf(stderr, "root %llu root dir %llu not found\n",
1211 (unsigned long long)root->root_key.objectid,
1212 (unsigned long long)root_dirid);
1213 }
1214
1215 while (1) {
1216 cache = find_first_cache_extent(inode_cache, 0);
1217 if (!cache)
1218 break;
1219 node = container_of(cache, struct ptr_node, cache);
1220 rec = node->data;
1221 remove_cache_extent(inode_cache, &node->cache);
1222 free(node);
1223 if (rec->ino == root_dirid ||
1224 rec->ino == BTRFS_ORPHAN_OBJECTID) {
1225 free_inode_rec(rec);
1226 continue;
1227 }
1228
1229 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1230 ret = check_orphan_item(root, rec->ino);
1231 if (ret == 0)
1232 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1233 if (can_free_inode_rec(rec)) {
1234 free_inode_rec(rec);
1235 continue;
1236 }
1237 }
1238
1239 error++;
1240 if (!rec->found_inode_item)
1241 rec->errors |= I_ERR_NO_INODE_ITEM;
1242 if (rec->found_link != rec->nlink)
1243 rec->errors |= I_ERR_LINK_COUNT_WRONG;
1244 fprintf(stderr, "root %llu inode %llu errors %x\n",
1245 (unsigned long long) root->root_key.objectid,
1246 (unsigned long long) rec->ino, rec->errors);
1247 list_for_each_entry(backref, &rec->backrefs, list) {
1248 if (!backref->found_dir_item)
1249 backref->errors |= REF_ERR_NO_DIR_ITEM;
1250 if (!backref->found_dir_index)
1251 backref->errors |= REF_ERR_NO_DIR_INDEX;
1252 if (!backref->found_inode_ref)
1253 backref->errors |= REF_ERR_NO_INODE_REF;
1254 fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1255 " namelen %u name %s filetype %d error %x\n",
1256 (unsigned long long)backref->dir,
1257 (unsigned long long)backref->index,
1258 backref->namelen, backref->name,
1259 backref->filetype, backref->errors);
1260 }
1261 free_inode_rec(rec);
1262 }
1263 return (error > 0) ? -1 : 0;
1264 }
1265
1266 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1267 u64 objectid)
1268 {
1269 struct cache_extent *cache;
1270 struct root_record *rec = NULL;
1271 int ret;
1272
1273 cache = find_cache_extent(root_cache, objectid, 1);
1274 if (cache) {
1275 rec = container_of(cache, struct root_record, cache);
1276 } else {
1277 rec = calloc(1, sizeof(*rec));
1278 rec->objectid = objectid;
1279 INIT_LIST_HEAD(&rec->backrefs);
1280 rec->cache.start = objectid;
1281 rec->cache.size = 1;
1282
1283 ret = insert_existing_cache_extent(root_cache, &rec->cache);
1284 BUG_ON(ret);
1285 }
1286 return rec;
1287 }
1288
1289 static struct root_backref *get_root_backref(struct root_record *rec,
1290 u64 ref_root, u64 dir, u64 index,
1291 const char *name, int namelen)
1292 {
1293 struct root_backref *backref;
1294
1295 list_for_each_entry(backref, &rec->backrefs, list) {
1296 if (backref->ref_root != ref_root || backref->dir != dir ||
1297 backref->namelen != namelen)
1298 continue;
1299 if (memcmp(name, backref->name, namelen))
1300 continue;
1301 return backref;
1302 }
1303
1304 backref = malloc(sizeof(*backref) + namelen + 1);
1305 memset(backref, 0, sizeof(*backref));
1306 backref->ref_root = ref_root;
1307 backref->dir = dir;
1308 backref->index = index;
1309 backref->namelen = namelen;
1310 memcpy(backref->name, name, namelen);
1311 backref->name[namelen] = '\0';
1312 list_add_tail(&backref->list, &rec->backrefs);
1313 return backref;
1314 }
1315
1316 static void free_root_recs(struct cache_tree *root_cache)
1317 {
1318 struct cache_extent *cache;
1319 struct root_record *rec;
1320 struct root_backref *backref;
1321
1322 while (1) {
1323 cache = find_first_cache_extent(root_cache, 0);
1324 if (!cache)
1325 break;
1326 rec = container_of(cache, struct root_record, cache);
1327 remove_cache_extent(root_cache, &rec->cache);
1328
1329 while (!list_empty(&rec->backrefs)) {
1330 backref = list_entry(rec->backrefs.next,
1331 struct root_backref, list);
1332 list_del(&backref->list);
1333 free(backref);
1334 }
1335 kfree(rec);
1336 }
1337 }
1338
1339 static int add_root_backref(struct cache_tree *root_cache,
1340 u64 root_id, u64 ref_root, u64 dir, u64 index,
1341 const char *name, int namelen,
1342 int item_type, int errors)
1343 {
1344 struct root_record *rec;
1345 struct root_backref *backref;
1346
1347 rec = get_root_rec(root_cache, root_id);
1348 backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
1349
1350 backref->errors |= errors;
1351
1352 if (item_type != BTRFS_DIR_ITEM_KEY) {
1353 if (backref->found_dir_index || backref->found_back_ref ||
1354 backref->found_forward_ref) {
1355 if (backref->index != index)
1356 backref->errors |= REF_ERR_INDEX_UNMATCH;
1357 } else {
1358 backref->index = index;
1359 }
1360 }
1361
1362 if (item_type == BTRFS_DIR_ITEM_KEY) {
1363 backref->found_dir_item = 1;
1364 backref->reachable = 1;
1365 rec->found_ref++;
1366 } else if (item_type == BTRFS_DIR_INDEX_KEY) {
1367 backref->found_dir_index = 1;
1368 } else if (item_type == BTRFS_ROOT_REF_KEY) {
1369 if (backref->found_forward_ref)
1370 backref->errors |= REF_ERR_DUP_ROOT_REF;
1371 backref->found_forward_ref = 1;
1372 } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
1373 if (backref->found_back_ref)
1374 backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
1375 backref->found_back_ref = 1;
1376 } else {
1377 BUG_ON(1);
1378 }
1379
1380 return 0;
1381 }
1382
1383 static int merge_root_recs(struct btrfs_root *root,
1384 struct cache_tree *src_cache,
1385 struct cache_tree *dst_cache)
1386 {
1387 struct cache_extent *cache;
1388 struct ptr_node *node;
1389 struct inode_record *rec;
1390 struct inode_backref *backref;
1391
1392 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1393 free_inode_recs(src_cache);
1394 return 0;
1395 }
1396
1397 while (1) {
1398 cache = find_first_cache_extent(src_cache, 0);
1399 if (!cache)
1400 break;
1401 node = container_of(cache, struct ptr_node, cache);
1402 rec = node->data;
1403 remove_cache_extent(src_cache, &node->cache);
1404 free(node);
1405
1406 list_for_each_entry(backref, &rec->backrefs, list) {
1407 BUG_ON(backref->found_inode_ref);
1408 if (backref->found_dir_item)
1409 add_root_backref(dst_cache, rec->ino,
1410 root->root_key.objectid, backref->dir,
1411 backref->index, backref->name,
1412 backref->namelen, BTRFS_DIR_ITEM_KEY,
1413 backref->errors);
1414 if (backref->found_dir_index)
1415 add_root_backref(dst_cache, rec->ino,
1416 root->root_key.objectid, backref->dir,
1417 backref->index, backref->name,
1418 backref->namelen, BTRFS_DIR_INDEX_KEY,
1419 backref->errors);
1420 }
1421 free_inode_rec(rec);
1422 }
1423 return 0;
1424 }
1425
1426 static int check_root_refs(struct btrfs_root *root,
1427 struct cache_tree *root_cache)
1428 {
1429 struct root_record *rec;
1430 struct root_record *ref_root;
1431 struct root_backref *backref;
1432 struct cache_extent *cache;
1433 int loop = 1;
1434 int ret;
1435 int error;
1436 int errors = 0;
1437
1438 rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
1439 rec->found_ref = 1;
1440
1441 /* fixme: this can not detect circular references */
1442 while (loop) {
1443 loop = 0;
1444 cache = find_first_cache_extent(root_cache, 0);
1445 while (1) {
1446 if (!cache)
1447 break;
1448 rec = container_of(cache, struct root_record, cache);
1449 cache = next_cache_extent(cache);
1450
1451 if (rec->found_ref == 0)
1452 continue;
1453
1454 list_for_each_entry(backref, &rec->backrefs, list) {
1455 if (!backref->reachable)
1456 continue;
1457
1458 ref_root = get_root_rec(root_cache,
1459 backref->ref_root);
1460 if (ref_root->found_ref > 0)
1461 continue;
1462
1463 backref->reachable = 0;
1464 rec->found_ref--;
1465 if (rec->found_ref == 0)
1466 loop = 1;
1467 }
1468 }
1469 }
1470
1471 cache = find_first_cache_extent(root_cache, 0);
1472 while (1) {
1473 if (!cache)
1474 break;
1475 rec = container_of(cache, struct root_record, cache);
1476 cache = next_cache_extent(cache);
1477
1478 if (rec->found_ref == 0 &&
1479 rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1480 rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
1481 ret = check_orphan_item(root->fs_info->tree_root,
1482 rec->objectid);
1483 if (ret == 0)
1484 continue;
1485 errors++;
1486 fprintf(stderr, "fs tree %llu not referenced\n",
1487 (unsigned long long)rec->objectid);
1488 }
1489
1490 error = 0;
1491 if (rec->found_ref > 0 && !rec->found_root_item)
1492 error = 1;
1493 list_for_each_entry(backref, &rec->backrefs, list) {
1494 if (!backref->found_dir_item)
1495 backref->errors |= REF_ERR_NO_DIR_ITEM;
1496 if (!backref->found_dir_index)
1497 backref->errors |= REF_ERR_NO_DIR_INDEX;
1498 if (!backref->found_back_ref)
1499 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
1500 if (!backref->found_forward_ref)
1501 backref->errors |= REF_ERR_NO_ROOT_REF;
1502 if (backref->reachable && backref->errors)
1503 error = 1;
1504 }
1505 if (!error)
1506 continue;
1507
1508 errors++;
1509 fprintf(stderr, "fs tree %llu refs %u %s\n",
1510 (unsigned long long)rec->objectid, rec->found_ref,
1511 rec->found_root_item ? "" : "not found");
1512
1513 list_for_each_entry(backref, &rec->backrefs, list) {
1514 if (!backref->reachable)
1515 continue;
1516 if (!backref->errors && rec->found_root_item)
1517 continue;
1518 fprintf(stderr, "\tunresolved ref root %llu dir %llu"
1519 " index %llu namelen %u name %s error %x\n",
1520 (unsigned long long)backref->ref_root,
1521 (unsigned long long)backref->dir,
1522 (unsigned long long)backref->index,
1523 backref->namelen, backref->name,
1524 backref->errors);
1525 }
1526 }
1527 return errors > 0 ? 1 : 0;
1528 }
1529
1530 static int process_root_ref(struct extent_buffer *eb, int slot,
1531 struct btrfs_key *key,
1532 struct cache_tree *root_cache)
1533 {
1534 u64 dirid;
1535 u64 index;
1536 u32 len;
1537 u32 name_len;
1538 struct btrfs_root_ref *ref;
1539 char namebuf[BTRFS_NAME_LEN];
1540 int error;
1541
1542 ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
1543
1544 dirid = btrfs_root_ref_dirid(eb, ref);
1545 index = btrfs_root_ref_sequence(eb, ref);
1546 name_len = btrfs_root_ref_name_len(eb, ref);
1547
1548 if (name_len <= BTRFS_NAME_LEN) {
1549 len = name_len;
1550 error = 0;
1551 } else {
1552 len = BTRFS_NAME_LEN;
1553 error = REF_ERR_NAME_TOO_LONG;
1554 }
1555 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1556
1557 if (key->type == BTRFS_ROOT_REF_KEY) {
1558 add_root_backref(root_cache, key->offset, key->objectid, dirid,
1559 index, namebuf, len, key->type, error);
1560 } else {
1561 add_root_backref(root_cache, key->objectid, key->offset, dirid,
1562 index, namebuf, len, key->type, error);
1563 }
1564 return 0;
1565 }
1566
1567 static int check_fs_root(struct btrfs_root *root,
1568 struct cache_tree *root_cache,
1569 struct walk_control *wc)
1570 {
1571 int ret = 0;
1572 int wret;
1573 int level;
1574 struct btrfs_path path;
1575 struct shared_node root_node;
1576 struct root_record *rec;
1577 struct btrfs_root_item *root_item = &root->root_item;
1578
1579 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1580 rec = get_root_rec(root_cache, root->root_key.objectid);
1581 if (btrfs_root_refs(root_item) > 0)
1582 rec->found_root_item = 1;
1583 }
1584
1585 btrfs_init_path(&path);
1586 memset(&root_node, 0, sizeof(root_node));
1587 cache_tree_init(&root_node.root_cache);
1588 cache_tree_init(&root_node.inode_cache);
1589
1590 level = btrfs_header_level(root->node);
1591 memset(wc->nodes, 0, sizeof(wc->nodes));
1592 wc->nodes[level] = &root_node;
1593 wc->active_node = level;
1594 wc->root_level = level;
1595
1596 if (btrfs_root_refs(root_item) > 0 ||
1597 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1598 path.nodes[level] = root->node;
1599 extent_buffer_get(root->node);
1600 path.slots[level] = 0;
1601 } else {
1602 struct btrfs_key key;
1603 struct btrfs_disk_key found_key;
1604
1605 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1606 level = root_item->drop_level;
1607 path.lowest_level = level;
1608 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1609 BUG_ON(wret < 0);
1610 btrfs_node_key(path.nodes[level], &found_key,
1611 path.slots[level]);
1612 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1613 sizeof(found_key)));
1614 }
1615
1616 while (1) {
1617 wret = walk_down_tree(root, &path, wc, &level);
1618 if (wret < 0)
1619 ret = wret;
1620 if (wret != 0)
1621 break;
1622
1623 wret = walk_up_tree(root, &path, wc, &level);
1624 if (wret < 0)
1625 ret = wret;
1626 if (wret != 0)
1627 break;
1628 }
1629 btrfs_release_path(root, &path);
1630
1631 merge_root_recs(root, &root_node.root_cache, root_cache);
1632
1633 if (root_node.current) {
1634 root_node.current->checked = 1;
1635 maybe_free_inode_rec(&root_node.inode_cache,
1636 root_node.current);
1637 }
1638
1639 ret = check_inode_recs(root, &root_node.inode_cache);
1640 return ret;
1641 }
1642
1643 static int fs_root_objectid(u64 objectid)
1644 {
1645 if (objectid == BTRFS_FS_TREE_OBJECTID ||
1646 objectid == BTRFS_TREE_RELOC_OBJECTID ||
1647 objectid == BTRFS_DATA_RELOC_TREE_OBJECTID ||
1648 (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1649 objectid <= BTRFS_LAST_FREE_OBJECTID))
1650 return 1;
1651 return 0;
1652 }
1653
1654 static int check_fs_roots(struct btrfs_root *root,
1655 struct cache_tree *root_cache)
1656 {
1657 struct btrfs_path path;
1658 struct btrfs_key key;
1659 struct walk_control wc;
1660 struct extent_buffer *leaf;
1661 struct btrfs_root *tmp_root;
1662 struct btrfs_root *tree_root = root->fs_info->tree_root;
1663 int ret;
1664 int err = 0;
1665
1666 memset(&wc, 0, sizeof(wc));
1667 cache_tree_init(&wc.shared);
1668 btrfs_init_path(&path);
1669
1670 key.offset = 0;
1671 key.objectid = 0;
1672 key.type = BTRFS_ROOT_ITEM_KEY;
1673 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1674 BUG_ON(ret < 0);
1675 while (1) {
1676 leaf = path.nodes[0];
1677 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1678 ret = btrfs_next_leaf(tree_root, &path);
1679 if (ret != 0)
1680 break;
1681 leaf = path.nodes[0];
1682 }
1683 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1684 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1685 fs_root_objectid(key.objectid)) {
1686 tmp_root = btrfs_read_fs_root_no_cache(root->fs_info,
1687 &key);
1688 ret = check_fs_root(tmp_root, root_cache, &wc);
1689 if (ret)
1690 err = 1;
1691 btrfs_free_fs_root(root->fs_info, tmp_root);
1692 } else if (key.type == BTRFS_ROOT_REF_KEY ||
1693 key.type == BTRFS_ROOT_BACKREF_KEY) {
1694 process_root_ref(leaf, path.slots[0], &key,
1695 root_cache);
1696 }
1697 path.slots[0]++;
1698 }
1699 btrfs_release_path(tree_root, &path);
1700
1701 if (!cache_tree_empty(&wc.shared))
1702 fprintf(stderr, "warning line %d\n", __LINE__);
1703
1704 return err;
1705 }
1706
1707 static int check_node(struct btrfs_root *root,
1708 struct btrfs_disk_key *parent_key,
1709 struct extent_buffer *buf)
1710 {
1711 int i;
1712 struct btrfs_key cpukey;
1713 struct btrfs_disk_key key;
1714 u32 nritems = btrfs_header_nritems(buf);
1715
1716 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1717 return 1;
1718 if (parent_key->type) {
1719 btrfs_node_key(buf, &key, 0);
1720 if (memcmp(parent_key, &key, sizeof(key)))
1721 return 1;
1722 }
1723 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1724 btrfs_node_key(buf, &key, i);
1725 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
1726 if (btrfs_comp_keys(&key, &cpukey) >= 0)
1727 return 1;
1728 }
1729 return 0;
1730 }
1731
1732 static int check_leaf(struct btrfs_root *root,
1733 struct btrfs_disk_key *parent_key,
1734 struct extent_buffer *buf)
1735 {
1736 int i;
1737 struct btrfs_key cpukey;
1738 struct btrfs_disk_key key;
1739 u32 nritems = btrfs_header_nritems(buf);
1740
1741 if (btrfs_header_level(buf) != 0) {
1742 fprintf(stderr, "leaf is not a leaf %llu\n",
1743 (unsigned long long)btrfs_header_bytenr(buf));
1744 return 1;
1745 }
1746 if (btrfs_leaf_free_space(root, buf) < 0) {
1747 fprintf(stderr, "leaf free space incorrect %llu %d\n",
1748 (unsigned long long)btrfs_header_bytenr(buf),
1749 btrfs_leaf_free_space(root, buf));
1750 return 1;
1751 }
1752
1753 if (nritems == 0)
1754 return 0;
1755
1756 btrfs_item_key(buf, &key, 0);
1757 if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
1758 fprintf(stderr, "leaf parent key incorrect %llu\n",
1759 (unsigned long long)btrfs_header_bytenr(buf));
1760 return 1;
1761 }
1762 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1763 btrfs_item_key(buf, &key, i);
1764 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
1765 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
1766 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
1767 return 1;
1768 }
1769 if (btrfs_item_offset_nr(buf, i) !=
1770 btrfs_item_end_nr(buf, i + 1)) {
1771 fprintf(stderr, "incorrect offsets %u %u\n",
1772 btrfs_item_offset_nr(buf, i),
1773 btrfs_item_end_nr(buf, i + 1));
1774 return 1;
1775 }
1776 if (i == 0 && btrfs_item_end_nr(buf, i) !=
1777 BTRFS_LEAF_DATA_SIZE(root)) {
1778 fprintf(stderr, "bad item end %u wanted %u\n",
1779 btrfs_item_end_nr(buf, i),
1780 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
1781 return 1;
1782 }
1783 }
1784 return 0;
1785 }
1786
1787 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1788 {
1789 struct list_head *cur = rec->backrefs.next;
1790 struct extent_backref *back;
1791 struct tree_backref *tback;
1792 struct data_backref *dback;
1793 u64 found = 0;
1794 int err = 0;
1795
1796 while(cur != &rec->backrefs) {
1797 back = list_entry(cur, struct extent_backref, list);
1798 cur = cur->next;
1799 if (!back->found_extent_tree) {
1800 err = 1;
1801 if (!print_errs)
1802 goto out;
1803 if (back->is_data) {
1804 dback = (struct data_backref *)back;
1805 fprintf(stderr, "Backref %llu %s %llu"
1806 " owner %llu offset %llu num_refs %lu"
1807 " not found in extent tree\n",
1808 (unsigned long long)rec->start,
1809 back->full_backref ?
1810 "parent" : "root",
1811 back->full_backref ?
1812 (unsigned long long)dback->parent:
1813 (unsigned long long)dback->root,
1814 (unsigned long long)dback->owner,
1815 (unsigned long long)dback->offset,
1816 (unsigned long)dback->num_refs);
1817 } else {
1818 tback = (struct tree_backref *)back;
1819 fprintf(stderr, "Backref %llu parent %llu"
1820 " root %llu not found in extent tree\n",
1821 (unsigned long long)rec->start,
1822 (unsigned long long)tback->parent,
1823 (unsigned long long)tback->root);
1824 }
1825 }
1826 if (!back->is_data && !back->found_ref) {
1827 err = 1;
1828 if (!print_errs)
1829 goto out;
1830 tback = (struct tree_backref *)back;
1831 fprintf(stderr, "Backref %llu %s %llu not referenced\n",
1832 (unsigned long long)rec->start,
1833 back->full_backref ? "parent" : "root",
1834 back->full_backref ?
1835 (unsigned long long)tback->parent :
1836 (unsigned long long)tback->root);
1837 }
1838 if (back->is_data) {
1839 dback = (struct data_backref *)back;
1840 if (dback->found_ref != dback->num_refs) {
1841 err = 1;
1842 if (!print_errs)
1843 goto out;
1844 fprintf(stderr, "Incorrect local backref count"
1845 " on %llu %s %llu owner %llu"
1846 " offset %llu found %u wanted %u\n",
1847 (unsigned long long)rec->start,
1848 back->full_backref ?
1849 "parent" : "root",
1850 back->full_backref ?
1851 (unsigned long long)dback->parent:
1852 (unsigned long long)dback->root,
1853 (unsigned long long)dback->owner,
1854 (unsigned long long)dback->offset,
1855 dback->found_ref, dback->num_refs);
1856 }
1857 }
1858 if (!back->is_data) {
1859 found += 1;
1860 } else {
1861 dback = (struct data_backref *)back;
1862 found += dback->found_ref;
1863 }
1864 }
1865 if (found != rec->refs) {
1866 err = 1;
1867 if (!print_errs)
1868 goto out;
1869 fprintf(stderr, "Incorrect global backref count "
1870 "on %llu found %llu wanted %llu\n",
1871 (unsigned long long)rec->start,
1872 (unsigned long long)found,
1873 (unsigned long long)rec->refs);
1874 }
1875 out:
1876 return err;
1877 }
1878
1879 static int free_all_extent_backrefs(struct extent_record *rec)
1880 {
1881 struct extent_backref *back;
1882 struct list_head *cur;
1883 while (!list_empty(&rec->backrefs)) {
1884 cur = rec->backrefs.next;
1885 back = list_entry(cur, struct extent_backref, list);
1886 list_del(cur);
1887 free(back);
1888 }
1889 return 0;
1890 }
1891
1892 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1893 struct extent_record *rec)
1894 {
1895 if (rec->content_checked && rec->owner_ref_checked &&
1896 rec->extent_item_refs == rec->refs && rec->refs > 0 &&
1897 !all_backpointers_checked(rec, 0)) {
1898 remove_cache_extent(extent_cache, &rec->cache);
1899 free_all_extent_backrefs(rec);
1900 free(rec);
1901 }
1902 return 0;
1903 }
1904
1905 static int check_owner_ref(struct btrfs_root *root,
1906 struct extent_record *rec,
1907 struct extent_buffer *buf)
1908 {
1909 struct extent_backref *node;
1910 struct tree_backref *back;
1911 struct btrfs_root *ref_root;
1912 struct btrfs_key key;
1913 struct btrfs_path path;
1914 int ret;
1915 int level;
1916 int found = 0;
1917
1918 list_for_each_entry(node, &rec->backrefs, list) {
1919 if (node->is_data)
1920 continue;
1921 if (!node->found_ref)
1922 continue;
1923 if (node->full_backref)
1924 continue;
1925 back = (struct tree_backref *)node;
1926 if (btrfs_header_owner(buf) == back->root)
1927 return 0;
1928 }
1929 BUG_ON(rec->is_root);
1930
1931 /* try to find the block by search corresponding fs tree */
1932 key.objectid = btrfs_header_owner(buf);
1933 key.type = BTRFS_ROOT_ITEM_KEY;
1934 key.offset = (u64)-1;
1935
1936 ref_root = btrfs_read_fs_root(root->fs_info, &key);
1937 BUG_ON(IS_ERR(ref_root));
1938
1939 level = btrfs_header_level(buf);
1940 if (level == 0)
1941 btrfs_item_key_to_cpu(buf, &key, 0);
1942 else
1943 btrfs_node_key_to_cpu(buf, &key, 0);
1944
1945 btrfs_init_path(&path);
1946 path.lowest_level = level + 1;
1947 ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
1948
1949 if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
1950 path.slots[level + 1]))
1951 rec->owner_ref_checked = 1;
1952
1953 btrfs_release_path(ref_root, &path);
1954 return found ? 0 : 1;
1955 }
1956
1957 static int check_block(struct btrfs_root *root,
1958 struct cache_tree *extent_cache,
1959 struct extent_buffer *buf, u64 flags)
1960 {
1961 struct extent_record *rec;
1962 struct cache_extent *cache;
1963 int ret = 1;
1964
1965 cache = find_cache_extent(extent_cache, buf->start, buf->len);
1966 if (!cache)
1967 return 1;
1968 rec = container_of(cache, struct extent_record, cache);
1969 if (btrfs_is_leaf(buf)) {
1970 ret = check_leaf(root, &rec->parent_key, buf);
1971 } else {
1972 ret = check_node(root, &rec->parent_key, buf);
1973 }
1974 if (ret) {
1975 fprintf(stderr, "bad block %llu\n",
1976 (unsigned long long)buf->start);
1977 } else {
1978 rec->content_checked = 1;
1979 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
1980 rec->owner_ref_checked = 1;
1981 else {
1982 ret = check_owner_ref(root, rec, buf);
1983 if (!ret)
1984 rec->owner_ref_checked = 1;
1985 }
1986 }
1987 if (!ret)
1988 maybe_free_extent_rec(extent_cache, rec);
1989 return ret;
1990 }
1991
1992 static struct tree_backref *find_tree_backref(struct extent_record *rec,
1993 u64 parent, u64 root)
1994 {
1995 struct list_head *cur = rec->backrefs.next;
1996 struct extent_backref *node;
1997 struct tree_backref *back;
1998
1999 while(cur != &rec->backrefs) {
2000 node = list_entry(cur, struct extent_backref, list);
2001 cur = cur->next;
2002 if (node->is_data)
2003 continue;
2004 back = (struct tree_backref *)node;
2005 if (parent > 0) {
2006 if (!node->full_backref)
2007 continue;
2008 if (parent == back->parent)
2009 return back;
2010 } else {
2011 if (node->full_backref)
2012 continue;
2013 if (back->root == root)
2014 return back;
2015 }
2016 }
2017 return NULL;
2018 }
2019
2020 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2021 u64 parent, u64 root)
2022 {
2023 struct tree_backref *ref = malloc(sizeof(*ref));
2024 memset(&ref->node, 0, sizeof(ref->node));
2025 if (parent > 0) {
2026 ref->parent = parent;
2027 ref->node.full_backref = 1;
2028 } else {
2029 ref->root = root;
2030 ref->node.full_backref = 0;
2031 }
2032 list_add_tail(&ref->node.list, &rec->backrefs);
2033 return ref;
2034 }
2035
2036 static struct data_backref *find_data_backref(struct extent_record *rec,
2037 u64 parent, u64 root,
2038 u64 owner, u64 offset)
2039 {
2040 struct list_head *cur = rec->backrefs.next;
2041 struct extent_backref *node;
2042 struct data_backref *back;
2043
2044 while(cur != &rec->backrefs) {
2045 node = list_entry(cur, struct extent_backref, list);
2046 cur = cur->next;
2047 if (!node->is_data)
2048 continue;
2049 back = (struct data_backref *)node;
2050 if (parent > 0) {
2051 if (!node->full_backref)
2052 continue;
2053 if (parent == back->parent)
2054 return back;
2055 } else {
2056 if (node->full_backref)
2057 continue;
2058 if (back->root == root && back->owner == owner &&
2059 back->offset == offset)
2060 return back;
2061 }
2062 }
2063 return NULL;
2064 }
2065
2066 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2067 u64 parent, u64 root,
2068 u64 owner, u64 offset)
2069 {
2070 struct data_backref *ref = malloc(sizeof(*ref));
2071 memset(&ref->node, 0, sizeof(ref->node));
2072 ref->node.is_data = 1;
2073 if (parent > 0) {
2074 ref->parent = parent;
2075 ref->owner = 0;
2076 ref->offset = 0;
2077 ref->node.full_backref = 1;
2078 } else {
2079 ref->root = root;
2080 ref->owner = owner;
2081 ref->offset = offset;
2082 ref->node.full_backref = 0;
2083 }
2084 ref->found_ref = 0;
2085 ref->num_refs = 0;
2086 list_add_tail(&ref->node.list, &rec->backrefs);
2087 return ref;
2088 }
2089
2090 static int add_extent_rec(struct cache_tree *extent_cache,
2091 struct btrfs_key *parent_key,
2092 u64 start, u64 nr, u64 extent_item_refs,
2093 int is_root, int inc_ref, int set_checked)
2094 {
2095 struct extent_record *rec;
2096 struct cache_extent *cache;
2097 int ret = 0;
2098
2099 cache = find_cache_extent(extent_cache, start, nr);
2100 if (cache) {
2101 rec = container_of(cache, struct extent_record, cache);
2102 if (inc_ref)
2103 rec->refs++;
2104 if (rec->nr == 1)
2105 rec->nr = nr;
2106
2107 if (start != rec->start) {
2108 fprintf(stderr, "warning, start mismatch %llu %llu\n",
2109 (unsigned long long)rec->start,
2110 (unsigned long long)start);
2111 ret = 1;
2112 }
2113 if (extent_item_refs) {
2114 if (rec->extent_item_refs) {
2115 fprintf(stderr, "block %llu rec "
2116 "extent_item_refs %llu, passed %llu\n",
2117 (unsigned long long)start,
2118 (unsigned long long)
2119 rec->extent_item_refs,
2120 (unsigned long long)extent_item_refs);
2121 }
2122 rec->extent_item_refs = extent_item_refs;
2123 }
2124 if (is_root)
2125 rec->is_root = 1;
2126 if (set_checked) {
2127 rec->content_checked = 1;
2128 rec->owner_ref_checked = 1;
2129 }
2130
2131 if (parent_key)
2132 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2133
2134 maybe_free_extent_rec(extent_cache, rec);
2135 return ret;
2136 }
2137 rec = malloc(sizeof(*rec));
2138 rec->start = start;
2139 rec->nr = nr;
2140 rec->content_checked = 0;
2141 rec->owner_ref_checked = 0;
2142 INIT_LIST_HEAD(&rec->backrefs);
2143
2144 if (is_root)
2145 rec->is_root = 1;
2146 else
2147 rec->is_root = 0;
2148
2149 if (inc_ref)
2150 rec->refs = 1;
2151 else
2152 rec->refs = 0;
2153
2154 if (extent_item_refs)
2155 rec->extent_item_refs = extent_item_refs;
2156 else
2157 rec->extent_item_refs = 0;
2158
2159 if (parent_key)
2160 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2161 else
2162 memset(&rec->parent_key, 0, sizeof(*parent_key));
2163
2164 rec->cache.start = start;
2165 rec->cache.size = nr;
2166 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
2167 BUG_ON(ret);
2168 bytes_used += nr;
2169 if (set_checked) {
2170 rec->content_checked = 1;
2171 rec->owner_ref_checked = 1;
2172 }
2173 return ret;
2174 }
2175
2176 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
2177 u64 parent, u64 root, int found_ref)
2178 {
2179 struct extent_record *rec;
2180 struct tree_backref *back;
2181 struct cache_extent *cache;
2182
2183 cache = find_cache_extent(extent_cache, bytenr, 1);
2184 if (!cache) {
2185 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2186 cache = find_cache_extent(extent_cache, bytenr, 1);
2187 if (!cache)
2188 abort();
2189 }
2190
2191 rec = container_of(cache, struct extent_record, cache);
2192 if (rec->start != bytenr) {
2193 abort();
2194 }
2195
2196 back = find_tree_backref(rec, parent, root);
2197 if (!back)
2198 back = alloc_tree_backref(rec, parent, root);
2199
2200 if (found_ref) {
2201 if (back->node.found_ref) {
2202 fprintf(stderr, "Extent back ref already exists "
2203 "for %llu parent %llu root %llu \n",
2204 (unsigned long long)bytenr,
2205 (unsigned long long)parent,
2206 (unsigned long long)root);
2207 }
2208 back->node.found_ref = 1;
2209 } else {
2210 if (back->node.found_extent_tree) {
2211 fprintf(stderr, "Extent back ref already exists "
2212 "for %llu parent %llu root %llu \n",
2213 (unsigned long long)bytenr,
2214 (unsigned long long)parent,
2215 (unsigned long long)root);
2216 }
2217 back->node.found_extent_tree = 1;
2218 }
2219 return 0;
2220 }
2221
2222 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
2223 u64 parent, u64 root, u64 owner, u64 offset,
2224 u32 num_refs, int found_ref)
2225 {
2226 struct extent_record *rec;
2227 struct data_backref *back;
2228 struct cache_extent *cache;
2229
2230 cache = find_cache_extent(extent_cache, bytenr, 1);
2231 if (!cache) {
2232 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2233 cache = find_cache_extent(extent_cache, bytenr, 1);
2234 if (!cache)
2235 abort();
2236 }
2237
2238 rec = container_of(cache, struct extent_record, cache);
2239 if (rec->start != bytenr) {
2240 abort();
2241 }
2242 back = find_data_backref(rec, parent, root, owner, offset);
2243 if (!back)
2244 back = alloc_data_backref(rec, parent, root, owner, offset);
2245
2246 if (found_ref) {
2247 BUG_ON(num_refs != 1);
2248 back->node.found_ref = 1;
2249 back->found_ref += 1;
2250 } else {
2251 if (back->node.found_extent_tree) {
2252 fprintf(stderr, "Extent back ref already exists "
2253 "for %llu parent %llu root %llu"
2254 "owner %llu offset %llu num_refs %lu\n",
2255 (unsigned long long)bytenr,
2256 (unsigned long long)parent,
2257 (unsigned long long)root,
2258 (unsigned long long)owner,
2259 (unsigned long long)offset,
2260 (unsigned long)num_refs);
2261 }
2262 back->num_refs = num_refs;
2263 back->node.found_extent_tree = 1;
2264 }
2265 return 0;
2266 }
2267
2268 static int add_pending(struct cache_tree *pending,
2269 struct cache_tree *seen, u64 bytenr, u32 size)
2270 {
2271 int ret;
2272 ret = insert_cache_extent(seen, bytenr, size);
2273 if (ret)
2274 return ret;
2275 insert_cache_extent(pending, bytenr, size);
2276 return 0;
2277 }
2278
2279 static int pick_next_pending(struct cache_tree *pending,
2280 struct cache_tree *reada,
2281 struct cache_tree *nodes,
2282 u64 last, struct block_info *bits, int bits_nr,
2283 int *reada_bits)
2284 {
2285 unsigned long node_start = last;
2286 struct cache_extent *cache;
2287 int ret;
2288
2289 cache = find_first_cache_extent(reada, 0);
2290 if (cache) {
2291 bits[0].start = cache->start;
2292 bits[1].size = cache->size;
2293 *reada_bits = 1;
2294 return 1;
2295 }
2296 *reada_bits = 0;
2297 if (node_start > 32768)
2298 node_start -= 32768;
2299
2300 cache = find_first_cache_extent(nodes, node_start);
2301 if (!cache)
2302 cache = find_first_cache_extent(nodes, 0);
2303
2304 if (!cache) {
2305 cache = find_first_cache_extent(pending, 0);
2306 if (!cache)
2307 return 0;
2308 ret = 0;
2309 do {
2310 bits[ret].start = cache->start;
2311 bits[ret].size = cache->size;
2312 cache = next_cache_extent(cache);
2313 ret++;
2314 } while (cache && ret < bits_nr);
2315 return ret;
2316 }
2317
2318 ret = 0;
2319 do {
2320 bits[ret].start = cache->start;
2321 bits[ret].size = cache->size;
2322 cache = next_cache_extent(cache);
2323 ret++;
2324 } while (cache && ret < bits_nr);
2325
2326 if (bits_nr - ret > 8) {
2327 u64 lookup = bits[0].start + bits[0].size;
2328 struct cache_extent *next;
2329 next = find_first_cache_extent(pending, lookup);
2330 while(next) {
2331 if (next->start - lookup > 32768)
2332 break;
2333 bits[ret].start = next->start;
2334 bits[ret].size = next->size;
2335 lookup = next->start + next->size;
2336 ret++;
2337 if (ret == bits_nr)
2338 break;
2339 next = next_cache_extent(next);
2340 if (!next)
2341 break;
2342 }
2343 }
2344 return ret;
2345 }
2346
2347 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2348 static int process_extent_ref_v0(struct cache_tree *extent_cache,
2349 struct extent_buffer *leaf, int slot)
2350 {
2351 struct btrfs_extent_ref_v0 *ref0;
2352 struct btrfs_key key;
2353
2354 btrfs_item_key_to_cpu(leaf, &key, slot);
2355 ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
2356 if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
2357 add_tree_backref(extent_cache, key.objectid, key.offset,
2358 0, 0);
2359 } else {
2360 add_data_backref(extent_cache, key.objectid, key.offset, 0,
2361 0, 0, btrfs_ref_count_v0(leaf, ref0), 0);
2362 }
2363 return 0;
2364 }
2365 #endif
2366
2367 static int process_extent_item(struct cache_tree *extent_cache,
2368 struct extent_buffer *eb, int slot)
2369 {
2370 struct btrfs_extent_item *ei;
2371 struct btrfs_extent_inline_ref *iref;
2372 struct btrfs_extent_data_ref *dref;
2373 struct btrfs_shared_data_ref *sref;
2374 struct btrfs_key key;
2375 unsigned long end;
2376 unsigned long ptr;
2377 int type;
2378 u32 item_size = btrfs_item_size_nr(eb, slot);
2379 u64 refs = 0;
2380 u64 offset;
2381
2382 btrfs_item_key_to_cpu(eb, &key, slot);
2383
2384 if (item_size < sizeof(*ei)) {
2385 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2386 struct btrfs_extent_item_v0 *ei0;
2387 BUG_ON(item_size != sizeof(*ei0));
2388 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
2389 refs = btrfs_extent_refs_v0(eb, ei0);
2390 #else
2391 BUG();
2392 #endif
2393 return add_extent_rec(extent_cache, NULL, key.objectid,
2394 key.offset, refs, 0, 0, 0);
2395 }
2396
2397 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
2398 refs = btrfs_extent_refs(eb, ei);
2399
2400 add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
2401 refs, 0, 0, 0);
2402
2403 ptr = (unsigned long)(ei + 1);
2404 if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2405 ptr += sizeof(struct btrfs_tree_block_info);
2406
2407 end = (unsigned long)ei + item_size;
2408 while (ptr < end) {
2409 iref = (struct btrfs_extent_inline_ref *)ptr;
2410 type = btrfs_extent_inline_ref_type(eb, iref);
2411 offset = btrfs_extent_inline_ref_offset(eb, iref);
2412 switch (type) {
2413 case BTRFS_TREE_BLOCK_REF_KEY:
2414 add_tree_backref(extent_cache, key.objectid,
2415 0, offset, 0);
2416 break;
2417 case BTRFS_SHARED_BLOCK_REF_KEY:
2418 add_tree_backref(extent_cache, key.objectid,
2419 offset, 0, 0);
2420 break;
2421 case BTRFS_EXTENT_DATA_REF_KEY:
2422 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
2423 add_data_backref(extent_cache, key.objectid, 0,
2424 btrfs_extent_data_ref_root(eb, dref),
2425 btrfs_extent_data_ref_objectid(eb,
2426 dref),
2427 btrfs_extent_data_ref_offset(eb, dref),
2428 btrfs_extent_data_ref_count(eb, dref),
2429 0);
2430 break;
2431 case BTRFS_SHARED_DATA_REF_KEY:
2432 sref = (struct btrfs_shared_data_ref *)(iref + 1);
2433 add_data_backref(extent_cache, key.objectid, offset,
2434 0, 0, 0,
2435 btrfs_shared_data_ref_count(eb, sref),
2436 0);
2437 break;
2438 default:
2439 BUG();
2440 }
2441 ptr += btrfs_extent_inline_ref_size(type);
2442 }
2443 WARN_ON(ptr > end);
2444 return 0;
2445 }
2446
2447 static int run_next_block(struct btrfs_root *root,
2448 struct block_info *bits,
2449 int bits_nr,
2450 u64 *last,
2451 struct cache_tree *pending,
2452 struct cache_tree *seen,
2453 struct cache_tree *reada,
2454 struct cache_tree *nodes,
2455 struct cache_tree *extent_cache)
2456 {
2457 struct extent_buffer *buf;
2458 u64 bytenr;
2459 u32 size;
2460 u64 parent;
2461 u64 owner;
2462 u64 flags;
2463 int ret;
2464 int i;
2465 int nritems;
2466 struct btrfs_key key;
2467 struct cache_extent *cache;
2468 int reada_bits;
2469
2470 ret = pick_next_pending(pending, reada, nodes, *last, bits,
2471 bits_nr, &reada_bits);
2472 if (ret == 0) {
2473 return 1;
2474 }
2475 if (!reada_bits) {
2476 for(i = 0; i < ret; i++) {
2477 insert_cache_extent(reada, bits[i].start,
2478 bits[i].size);
2479
2480 /* fixme, get the parent transid */
2481 readahead_tree_block(root, bits[i].start,
2482 bits[i].size, 0);
2483 }
2484 }
2485 *last = bits[0].start;
2486 bytenr = bits[0].start;
2487 size = bits[0].size;
2488
2489 cache = find_cache_extent(pending, bytenr, size);
2490 if (cache) {
2491 remove_cache_extent(pending, cache);
2492 free(cache);
2493 }
2494 cache = find_cache_extent(reada, bytenr, size);
2495 if (cache) {
2496 remove_cache_extent(reada, cache);
2497 free(cache);
2498 }
2499 cache = find_cache_extent(nodes, bytenr, size);
2500 if (cache) {
2501 remove_cache_extent(nodes, cache);
2502 free(cache);
2503 }
2504
2505 /* fixme, get the real parent transid */
2506 buf = read_tree_block(root, bytenr, size, 0);
2507 nritems = btrfs_header_nritems(buf);
2508
2509 ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
2510
2511 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
2512 parent = bytenr;
2513 owner = 0;
2514 } else {
2515 parent = 0;
2516 owner = btrfs_header_owner(buf);
2517 }
2518
2519 ret = check_block(root, extent_cache, buf, flags);
2520
2521 if (btrfs_is_leaf(buf)) {
2522 btree_space_waste += btrfs_leaf_free_space(root, buf);
2523 for (i = 0; i < nritems; i++) {
2524 struct btrfs_file_extent_item *fi;
2525 btrfs_item_key_to_cpu(buf, &key, i);
2526 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
2527 process_extent_item(extent_cache, buf, i);
2528 continue;
2529 }
2530 if (key.type == BTRFS_EXTENT_CSUM_KEY) {
2531 total_csum_bytes +=
2532 btrfs_item_size_nr(buf, i);
2533 continue;
2534 }
2535 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
2536 struct btrfs_block_group_item *bi;
2537 bi = btrfs_item_ptr(buf, i,
2538 struct btrfs_block_group_item);
2539 #if 0
2540 fprintf(stderr,"block group %Lu %Lu used %Lu ",
2541 btrfs_disk_key_objectid(disk_key),
2542 btrfs_disk_key_offset(disk_key),
2543 btrfs_block_group_used(bi));
2544 fprintf(stderr, "flags %x\n", bi->flags);
2545 #endif
2546 continue;
2547 }
2548 if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
2549 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2550 process_extent_ref_v0(extent_cache, buf, i);
2551 #else
2552 BUG();
2553 #endif
2554 continue;
2555 }
2556
2557 if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2558 add_tree_backref(extent_cache, key.objectid, 0,
2559 key.offset, 0);
2560 continue;
2561 }
2562 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2563 add_tree_backref(extent_cache, key.objectid,
2564 key.offset, 0, 0);
2565 continue;
2566 }
2567 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
2568 struct btrfs_extent_data_ref *ref;
2569 ref = btrfs_item_ptr(buf, i,
2570 struct btrfs_extent_data_ref);
2571 add_data_backref(extent_cache,
2572 key.objectid, 0,
2573 btrfs_extent_data_ref_root(buf, ref),
2574 btrfs_extent_data_ref_objectid(buf,
2575 ref),
2576 btrfs_extent_data_ref_offset(buf, ref),
2577 btrfs_extent_data_ref_count(buf, ref),
2578 0);
2579 continue;
2580 }
2581 if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
2582 struct btrfs_shared_data_ref *ref;
2583 ref = btrfs_item_ptr(buf, i,
2584 struct btrfs_shared_data_ref);
2585 add_data_backref(extent_cache,
2586 key.objectid, key.offset, 0, 0, 0,
2587 btrfs_shared_data_ref_count(buf, ref),
2588 0);
2589 continue;
2590 }
2591 if (key.type != BTRFS_EXTENT_DATA_KEY)
2592 continue;
2593 fi = btrfs_item_ptr(buf, i,
2594 struct btrfs_file_extent_item);
2595 if (btrfs_file_extent_type(buf, fi) ==
2596 BTRFS_FILE_EXTENT_INLINE)
2597 continue;
2598 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2599 continue;
2600
2601 data_bytes_allocated +=
2602 btrfs_file_extent_disk_num_bytes(buf, fi);
2603 if (data_bytes_allocated < root->sectorsize) {
2604 abort();
2605 }
2606 data_bytes_referenced +=
2607 btrfs_file_extent_num_bytes(buf, fi);
2608 ret = add_extent_rec(extent_cache, NULL,
2609 btrfs_file_extent_disk_bytenr(buf, fi),
2610 btrfs_file_extent_disk_num_bytes(buf, fi),
2611 0, 0, 1, 1);
2612 add_data_backref(extent_cache,
2613 btrfs_file_extent_disk_bytenr(buf, fi),
2614 parent, owner, key.objectid, key.offset -
2615 btrfs_file_extent_offset(buf, fi), 1, 1);
2616 BUG_ON(ret);
2617 }
2618 } else {
2619 int level;
2620 level = btrfs_header_level(buf);
2621 for (i = 0; i < nritems; i++) {
2622 u64 ptr = btrfs_node_blockptr(buf, i);
2623 u32 size = btrfs_level_size(root, level - 1);
2624 btrfs_node_key_to_cpu(buf, &key, i);
2625 ret = add_extent_rec(extent_cache, &key,
2626 ptr, size, 0, 0, 1, 0);
2627 BUG_ON(ret);
2628
2629 add_tree_backref(extent_cache, ptr, parent,
2630 owner, 1);
2631
2632 if (level > 1) {
2633 add_pending(nodes, seen, ptr, size);
2634 } else {
2635 add_pending(pending, seen, ptr, size);
2636 }
2637 }
2638 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2639 nritems) * sizeof(struct btrfs_key_ptr);
2640 }
2641 total_btree_bytes += buf->len;
2642 if (fs_root_objectid(btrfs_header_owner(buf)))
2643 total_fs_tree_bytes += buf->len;
2644 if (!found_old_backref &&
2645 btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
2646 btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
2647 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
2648 found_old_backref = 1;
2649 free_extent_buffer(buf);
2650 return 0;
2651 }
2652
2653 static int add_root_to_pending(struct extent_buffer *buf,
2654 struct block_info *bits,
2655 int bits_nr,
2656 struct cache_tree *extent_cache,
2657 struct cache_tree *pending,
2658 struct cache_tree *seen,
2659 struct cache_tree *reada,
2660 struct cache_tree *nodes,
2661 struct btrfs_key *root_key)
2662 {
2663 if (btrfs_header_level(buf) > 0)
2664 add_pending(nodes, seen, buf->start, buf->len);
2665 else
2666 add_pending(pending, seen, buf->start, buf->len);
2667 add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2668 0, 1, 1, 0);
2669
2670 if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
2671 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2672 add_tree_backref(extent_cache, buf->start, buf->start, 0, 1);
2673 else
2674 add_tree_backref(extent_cache, buf->start, 0,
2675 root_key->objectid, 1);
2676 return 0;
2677 }
2678
2679 static int check_extent_refs(struct btrfs_root *root,
2680 struct cache_tree *extent_cache)
2681 {
2682 struct extent_record *rec;
2683 struct cache_extent *cache;
2684 int err = 0;
2685
2686 while(1) {
2687 cache = find_first_cache_extent(extent_cache, 0);
2688 if (!cache)
2689 break;
2690 rec = container_of(cache, struct extent_record, cache);
2691 if (rec->refs != rec->extent_item_refs) {
2692 fprintf(stderr, "ref mismatch on [%llu %llu] ",
2693 (unsigned long long)rec->start,
2694 (unsigned long long)rec->nr);
2695 fprintf(stderr, "extent item %llu, found %llu\n",
2696 (unsigned long long)rec->extent_item_refs,
2697 (unsigned long long)rec->refs);
2698 err = 1;
2699 }
2700 if (all_backpointers_checked(rec, 1)) {
2701 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
2702 (unsigned long long)rec->start,
2703 (unsigned long long)rec->nr);
2704
2705 err = 1;
2706 }
2707 if (!rec->owner_ref_checked) {
2708 fprintf(stderr, "owner ref check failed [%llu %llu]\n",
2709 (unsigned long long)rec->start,
2710 (unsigned long long)rec->nr);
2711 err = 1;
2712 }
2713
2714 remove_cache_extent(extent_cache, cache);
2715 free_all_extent_backrefs(rec);
2716 free(rec);
2717 }
2718 return err;
2719 }
2720
2721 static int check_extents(struct btrfs_root *root)
2722 {
2723 struct cache_tree extent_cache;
2724 struct cache_tree seen;
2725 struct cache_tree pending;
2726 struct cache_tree reada;
2727 struct cache_tree nodes;
2728 struct btrfs_path path;
2729 struct btrfs_key key;
2730 struct btrfs_key found_key;
2731 int ret;
2732 u64 last = 0;
2733 struct block_info *bits;
2734 int bits_nr;
2735 struct extent_buffer *leaf;
2736 int slot;
2737 struct btrfs_root_item ri;
2738
2739 cache_tree_init(&extent_cache);
2740 cache_tree_init(&seen);
2741 cache_tree_init(&pending);
2742 cache_tree_init(&nodes);
2743 cache_tree_init(&reada);
2744
2745 bits_nr = 1024;
2746 bits = malloc(bits_nr * sizeof(struct block_info));
2747 if (!bits) {
2748 perror("malloc");
2749 exit(1);
2750 }
2751
2752 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2753 &extent_cache, &pending, &seen, &reada, &nodes,
2754 &root->fs_info->tree_root->root_key);
2755
2756 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2757 &extent_cache, &pending, &seen, &reada, &nodes,
2758 &root->fs_info->chunk_root->root_key);
2759
2760 btrfs_init_path(&path);
2761 key.offset = 0;
2762 key.objectid = 0;
2763 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2764 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2765 &key, &path, 0, 0);
2766 BUG_ON(ret < 0);
2767 while(1) {
2768 leaf = path.nodes[0];
2769 slot = path.slots[0];
2770 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2771 ret = btrfs_next_leaf(root, &path);
2772 if (ret != 0)
2773 break;
2774 leaf = path.nodes[0];
2775 slot = path.slots[0];
2776 }
2777 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2778 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2779 unsigned long offset;
2780 struct extent_buffer *buf;
2781
2782 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2783 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2784 buf = read_tree_block(root->fs_info->tree_root,
2785 btrfs_root_bytenr(&ri),
2786 btrfs_level_size(root,
2787 btrfs_root_level(&ri)), 0);
2788 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2789 &pending, &seen, &reada, &nodes,
2790 &found_key);
2791 free_extent_buffer(buf);
2792 }
2793 path.slots[0]++;
2794 }
2795 btrfs_release_path(root, &path);
2796 while(1) {
2797 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2798 &seen, &reada, &nodes, &extent_cache);
2799 if (ret != 0)
2800 break;
2801 }
2802 ret = check_extent_refs(root, &extent_cache);
2803 return ret;
2804 }
2805
2806 static void print_usage(void)
2807 {
2808 fprintf(stderr, "usage: btrfsck dev\n");
2809 fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2810 exit(1);
2811 }
2812
2813 int main(int ac, char **av)
2814 {
2815 struct cache_tree root_cache;
2816 struct btrfs_root *root;
2817 int ret;
2818
2819 if (ac < 2)
2820 print_usage();
2821
2822 radix_tree_init();
2823 cache_tree_init(&root_cache);
2824 root = open_ctree(av[1], 0, 0);
2825
2826 if (root == NULL)
2827 return 1;
2828
2829 ret = check_extents(root);
2830 if (ret)
2831 goto out;
2832 ret = check_fs_roots(root, &root_cache);
2833 if (ret)
2834 goto out;
2835
2836 ret = check_root_refs(root, &root_cache);
2837 out:
2838 free_root_recs(&root_cache);
2839 close_ctree(root);
2840
2841 if (found_old_backref) {
2842 /*
2843 * there was a disk format change when mixed
2844 * backref was in testing tree. The old format
2845 * existed about one week.
2846 */
2847 printf("\n * Found old mixed backref format. "
2848 "The old format is not supported! *"
2849 "\n * Please mount the FS in readonly mode, "
2850 "backup data and re-format the FS. *\n\n");
2851 ret = 1;
2852 }
2853 printf("found %llu bytes used err is %d\n",
2854 (unsigned long long)bytes_used, ret);
2855 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2856 printf("total tree bytes: %llu\n",
2857 (unsigned long long)total_btree_bytes);
2858 printf("total fs tree bytes: %llu\n",
2859 (unsigned long long)total_fs_tree_bytes);
2860 printf("btree space waste bytes: %llu\n",
2861 (unsigned long long)btree_space_waste);
2862 printf("file data blocks allocated: %llu\n referenced %llu\n",
2863 (unsigned long long)data_bytes_allocated,
2864 (unsigned long long)data_bytes_referenced);
2865 printf("%s\n", BTRFS_BUILD_VERSION);
2866 return ret;
2867 }
(deprecated) Btrfs progs developments and patch integration