?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
btrfs-progs: do not merge tree block refs have different root_id
[btrfs-progs-unstable/devel.git] / check / mode-lowmem.c
blob9890180d1d3cada37c0e2e046072c8c0b78d6288
1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public
4 * License v2 as published by the Free Software Foundation.
5 *
6 * This program is distributed in the hope that it will be useful,
7 * but WITHOUT ANY WARRANTY; without even the implied warranty of
8 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
9 * General Public License for more details.
10 *
11 * You should have received a copy of the GNU General Public
12 * License along with this program; if not, write to the
13 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
14 * Boston, MA 021110-1307, USA.
15 */
16
17 #include <time.h>
18 #include "ctree.h"
19 #include "repair.h"
20 #include "transaction.h"
21 #include "messages.h"
22 #include "disk-io.h"
23 #include "backref.h"
24 #include "hash.h"
25 #include "internal.h"
26 #include "utils.h"
27 #include "volumes.h"
28 #include "check/mode-common.h"
29 #include "check/mode-lowmem.h"
30
31 static u64 last_allocated_chunk;
32
33 static int calc_extent_flag(struct btrfs_root *root, struct extent_buffer *eb,
34 u64 *flags_ret)
35 {
36 struct btrfs_root *extent_root = root->fs_info->extent_root;
37 struct btrfs_root_item *ri = &root->root_item;
38 struct btrfs_extent_inline_ref *iref;
39 struct btrfs_extent_item *ei;
40 struct btrfs_key key;
41 struct btrfs_path *path = NULL;
42 unsigned long ptr;
43 unsigned long end;
44 u64 flags;
45 u64 owner = 0;
46 u64 offset;
47 int slot;
48 int type;
49 int ret = 0;
50
51 /*
52 * Except file/reloc tree, we can not have FULL BACKREF MODE
53 */
54 if (root->objectid < BTRFS_FIRST_FREE_OBJECTID)
55 goto normal;
56
57 /* root node */
58 if (eb->start == btrfs_root_bytenr(ri))
59 goto normal;
60
61 if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC))
62 goto full_backref;
63
64 owner = btrfs_header_owner(eb);
65 if (owner == root->objectid)
66 goto normal;
67
68 path = btrfs_alloc_path();
69 if (!path)
70 return -ENOMEM;
71
72 key.objectid = btrfs_header_bytenr(eb);
73 key.type = (u8)-1;
74 key.offset = (u64)-1;
75
76 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
77 if (ret <= 0) {
78 ret = -EIO;
79 goto out;
80 }
81
82 if (ret > 0) {
83 ret = btrfs_previous_extent_item(extent_root, path,
84 key.objectid);
85 if (ret)
86 goto full_backref;
87
88 }
89 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
90
91 eb = path->nodes[0];
92 slot = path->slots[0];
93 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
94
95 flags = btrfs_extent_flags(eb, ei);
96 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
97 goto full_backref;
98
99 ptr = (unsigned long)(ei + 1);
100 end = (unsigned long)ei + btrfs_item_size_nr(eb, slot);
101
102 if (key.type == BTRFS_EXTENT_ITEM_KEY)
103 ptr += sizeof(struct btrfs_tree_block_info);
104
105 next:
106 /* Reached extent item ends normally */
107 if (ptr == end)
108 goto full_backref;
109
110 /* Beyond extent item end, wrong item size */
111 if (ptr > end) {
112 error("extent item at bytenr %llu slot %d has wrong size",
113 eb->start, slot);
114 goto full_backref;
115 }
116
117 iref = (struct btrfs_extent_inline_ref *)ptr;
118 offset = btrfs_extent_inline_ref_offset(eb, iref);
119 type = btrfs_extent_inline_ref_type(eb, iref);
120
121 if (type == BTRFS_TREE_BLOCK_REF_KEY && offset == owner)
122 goto normal;
123 ptr += btrfs_extent_inline_ref_size(type);
124 goto next;
125
126 normal:
127 *flags_ret &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
128 goto out;
129
130 full_backref:
131 *flags_ret |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
132 out:
133 btrfs_free_path(path);
134 return ret;
135 }
136
137 /*
138 * for a tree node or leaf, if it's shared, indeed we don't need to iterate it
139 * in every fs or file tree check. Here we find its all root ids, and only check
140 * it in the fs or file tree which has the smallest root id.
141 */
142 static int need_check(struct btrfs_root *root, struct ulist *roots)
143 {
144 struct rb_node *node;
145 struct ulist_node *u;
146
147 /*
148 * @roots can be empty if it belongs to tree reloc tree
149 * In that case, we should always check the leaf, as we can't use
150 * the tree owner to ensure some other root will check it.
151 */
152 if (roots->nnodes == 1 || roots->nnodes == 0)
153 return 1;
154
155 node = rb_first(&roots->root);
156 u = rb_entry(node, struct ulist_node, rb_node);
157 /*
158 * current root id is not smallest, we skip it and let it be checked
159 * in the fs or file tree who hash the smallest root id.
160 */
161 if (root->objectid != u->val)
162 return 0;
163
164 return 1;
165 }
166
167 /*
168 * for a tree node or leaf, we record its reference count, so later if we still
169 * process this node or leaf, don't need to compute its reference count again.
170 *
171 * @bytenr if @bytenr == (u64)-1, only update nrefs->full_backref[level]
172 */
173 static int update_nodes_refs(struct btrfs_root *root, u64 bytenr,
174 struct extent_buffer *eb, struct node_refs *nrefs,
175 u64 level, int check_all)
176 {
177 struct ulist *roots;
178 u64 refs = 0;
179 u64 flags = 0;
180 int root_level = btrfs_header_level(root->node);
181 int check;
182 int ret;
183
184 if (nrefs->bytenr[level] == bytenr)
185 return 0;
186
187 if (bytenr != (u64)-1) {
188 /* the return value of this function seems a mistake */
189 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
190 level, 1, &refs, &flags);
191 /* temporary fix */
192 if (ret < 0 && !check_all)
193 return ret;
194
195 nrefs->bytenr[level] = bytenr;
196 nrefs->refs[level] = refs;
197 nrefs->full_backref[level] = 0;
198 nrefs->checked[level] = 0;
199
200 if (refs > 1) {
201 ret = btrfs_find_all_roots(NULL, root->fs_info, bytenr,
202 0, &roots);
203 if (ret)
204 return -EIO;
205
206 check = need_check(root, roots);
207 ulist_free(roots);
208 nrefs->need_check[level] = check;
209 } else {
210 if (!check_all) {
211 nrefs->need_check[level] = 1;
212 } else {
213 if (level == root_level) {
214 nrefs->need_check[level] = 1;
215 } else {
216 /*
217 * The node refs may have not been
218 * updated if upper needs checking (the
219 * lowest root_objectid) the node can
220 * be checked.
221 */
222 nrefs->need_check[level] =
223 nrefs->need_check[level + 1];
224 }
225 }
226 }
227 }
228
229 if (check_all && eb) {
230 calc_extent_flag(root, eb, &flags);
231 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
232 nrefs->full_backref[level] = 1;
233 }
234
235 return 0;
236 }
237
238 /*
239 * Mark all extents unfree in the block group. And set @block_group->cached
240 * according to @cache.
241 */
242 static int modify_block_group_cache(struct btrfs_fs_info *fs_info,
243 struct btrfs_block_group_cache *block_group, int cache)
244 {
245 struct extent_io_tree *free_space_cache = &fs_info->free_space_cache;
246 u64 start = block_group->key.objectid;
247 u64 end = start + block_group->key.offset;
248
249 if (cache && !block_group->cached) {
250 block_group->cached = 1;
251 clear_extent_dirty(free_space_cache, start, end - 1);
252 }
253
254 if (!cache && block_group->cached) {
255 block_group->cached = 0;
256 clear_extent_dirty(free_space_cache, start, end - 1);
257 }
258 return 0;
259 }
260
261 /*
262 * Modify block groups which have @flags unfree in free space cache.
263 *
264 * @cache: if 0, clear block groups cache state;
265 * not 0, mark blocks groups cached.
266 */
267 static int modify_block_groups_cache(struct btrfs_fs_info *fs_info, u64 flags,
268 int cache)
269 {
270 struct btrfs_root *root = fs_info->extent_root;
271 struct btrfs_key key;
272 struct btrfs_path path;
273 struct btrfs_block_group_cache *bg_cache;
274 struct btrfs_block_group_item *bi;
275 struct btrfs_block_group_item bg_item;
276 struct extent_buffer *eb;
277 int slot;
278 int ret;
279
280 key.objectid = 0;
281 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
282 key.offset = 0;
283
284 btrfs_init_path(&path);
285 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
286 if (ret < 0) {
287 error("fail to search block groups due to %s", strerror(-ret));
288 goto out;
289 }
290
291 while (1) {
292 eb = path.nodes[0];
293 slot = path.slots[0];
294 btrfs_item_key_to_cpu(eb, &key, slot);
295 bg_cache = btrfs_lookup_block_group(fs_info, key.objectid);
296 if (!bg_cache) {
297 ret = -ENOENT;
298 goto out;
299 }
300
301 bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
302 read_extent_buffer(eb, &bg_item, (unsigned long)bi,
303 sizeof(bg_item));
304 if (btrfs_block_group_flags(&bg_item) & flags)
305 modify_block_group_cache(fs_info, bg_cache, cache);
306
307 ret = btrfs_next_item(root, &path);
308 if (ret > 0) {
309 ret = 0;
310 goto out;
311 }
312 if (ret < 0)
313 goto out;
314 }
315
316 out:
317 btrfs_release_path(&path);
318 return ret;
319 }
320
321 static int mark_block_groups_full(struct btrfs_fs_info *fs_info, u64 flags)
322 {
323 return modify_block_groups_cache(fs_info, flags, 1);
324 }
325
326 static int clear_block_groups_full(struct btrfs_fs_info *fs_info, u64 flags)
327 {
328 return modify_block_groups_cache(fs_info, flags, 0);
329 }
330
331 static int create_chunk_and_block_group(struct btrfs_fs_info *fs_info,
332 u64 flags, u64 *start, u64 *nbytes)
333 {
334 struct btrfs_trans_handle *trans;
335 struct btrfs_root *root = fs_info->extent_root;
336 int ret;
337
338 if ((flags & BTRFS_BLOCK_GROUP_TYPE_MASK) == 0)
339 return -EINVAL;
340
341 trans = btrfs_start_transaction(root, 1);
342 if (IS_ERR(trans)) {
343 ret = PTR_ERR(trans);
344 error("error starting transaction %s", strerror(-ret));
345 return ret;
346 }
347 ret = btrfs_alloc_chunk(trans, fs_info, start, nbytes, flags);
348 if (ret) {
349 error("fail to allocate new chunk %s", strerror(-ret));
350 goto out;
351 }
352 ret = btrfs_make_block_group(trans, fs_info, 0, flags, *start,
353 *nbytes);
354 if (ret) {
355 error("fail to make block group for chunk %llu %llu %s",
356 *start, *nbytes, strerror(-ret));
357 goto out;
358 }
359 out:
360 btrfs_commit_transaction(trans, root);
361 return ret;
362 }
363
364 static int force_cow_in_new_chunk(struct btrfs_fs_info *fs_info,
365 u64 *start_ret)
366 {
367 struct btrfs_block_group_cache *bg;
368 u64 start;
369 u64 nbytes;
370 u64 alloc_profile;
371 u64 flags;
372 int ret;
373
374 alloc_profile = (fs_info->avail_metadata_alloc_bits &
375 fs_info->metadata_alloc_profile);
376 flags = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
377 if (btrfs_fs_incompat(fs_info, MIXED_GROUPS))
378 flags |= BTRFS_BLOCK_GROUP_DATA;
379
380 ret = create_chunk_and_block_group(fs_info, flags, &start, &nbytes);
381 if (ret)
382 goto err;
383 printf("Created new chunk [%llu %llu]\n", start, nbytes);
384
385 flags = BTRFS_BLOCK_GROUP_METADATA;
386 /* Mark all metadata block groups cached and full in free space*/
387 ret = mark_block_groups_full(fs_info, flags);
388 if (ret)
389 goto clear_bgs_full;
390
391 bg = btrfs_lookup_block_group(fs_info, start);
392 if (!bg) {
393 ret = -ENOENT;
394 error("fail to look up block group %llu %llu", start, nbytes);
395 goto clear_bgs_full;
396 }
397
398 /* Clear block group cache just allocated */
399 ret = modify_block_group_cache(fs_info, bg, 0);
400 if (ret)
401 goto clear_bgs_full;
402 if (start_ret)
403 *start_ret = start;
404 return 0;
405
406 clear_bgs_full:
407 clear_block_groups_full(fs_info, flags);
408 err:
409 return ret;
410 }
411
412 /*
413 * Returns 0 means not almost full.
414 * Returns >0 means almost full.
415 * Returns <0 means fatal error.
416 */
417 static int is_chunk_almost_full(struct btrfs_fs_info *fs_info, u64 start)
418 {
419 struct btrfs_path path;
420 struct btrfs_key key;
421 struct btrfs_root *root = fs_info->extent_root;
422 struct btrfs_block_group_item *bi;
423 struct btrfs_block_group_item bg_item;
424 struct extent_buffer *eb;
425 u64 used;
426 u64 total;
427 u64 min_free;
428 int ret;
429 int slot;
430
431 key.objectid = start;
432 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
433 key.offset = (u64)-1;
434
435 btrfs_init_path(&path);
436 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
437 if (!ret)
438 ret = -EIO;
439 if (ret < 0)
440 goto out;
441 ret = btrfs_previous_item(root, &path, start,
442 BTRFS_BLOCK_GROUP_ITEM_KEY);
443 if (ret) {
444 error("failed to find block group %llu", start);
445 ret = -ENOENT;
446 goto out;
447 }
448
449 eb = path.nodes[0];
450 slot = path.slots[0];
451 btrfs_item_key_to_cpu(eb, &key, slot);
452 if (key.objectid != start) {
453 ret = -ENOENT;
454 goto out;
455 }
456
457 total = key.offset;
458 bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
459 read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item));
460 used = btrfs_block_group_used(&bg_item);
461
462 /*
463 * if the free space in the chunk is less than %10 of total,
464 * or not not enough for CoW once, we think the chunk is almost full.
465 */
466 min_free = max_t(u64, (BTRFS_MAX_LEVEL + 1) * fs_info->nodesize,
467 div_factor(total, 1));
468
469 if ((total - used) > min_free)
470 ret = 0;
471 else
472 ret = 1;
473 out:
474 btrfs_release_path(&path);
475 return ret;
476 }
477
478 /*
479 * Returns <0 for error.
480 * Returns 0 for success.
481 */
482 static int try_to_force_cow_in_new_chunk(struct btrfs_fs_info *fs_info,
483 u64 old_start, u64 *new_start)
484 {
485 int ret;
486
487 if (old_start) {
488 ret = is_chunk_almost_full(fs_info, old_start);
489 if (ret <= 0)
490 return ret;
491 }
492 ret = force_cow_in_new_chunk(fs_info, new_start);
493 return ret;
494 }
495
496 static int avoid_extents_overwrite(struct btrfs_fs_info *fs_info)
497 {
498 int ret;
499 int mixed = btrfs_fs_incompat(fs_info, MIXED_GROUPS);
500
501 if (fs_info->excluded_extents)
502 return 0;
503
504 if (last_allocated_chunk != (u64)-1) {
505 ret = try_to_force_cow_in_new_chunk(fs_info,
506 last_allocated_chunk, &last_allocated_chunk);
507 if (!ret)
508 goto out;
509 /*
510 * If failed, do not try to allocate chunk again in
511 * next call.
512 * If there is no space left to allocate, try to exclude all
513 * metadata blocks. Mixed filesystem is unsupported.
514 */
515 last_allocated_chunk = (u64)-1;
516 if (ret != -ENOSPC || mixed)
517 goto out;
518 }
519
520 printf(
521 "Try to exclude all metadata blcoks and extents, it may be slow\n");
522 ret = exclude_metadata_blocks(fs_info);
523 out:
524 if (ret)
525 error("failed to avoid extents overwrite %s", strerror(-ret));
526 return ret;
527 }
528
529 static int end_avoid_extents_overwrite(struct btrfs_fs_info *fs_info)
530 {
531 int ret = 0;
532
533 cleanup_excluded_extents(fs_info);
534 if (last_allocated_chunk)
535 ret = clear_block_groups_full(fs_info,
536 BTRFS_BLOCK_GROUP_METADATA);
537 return ret;
538 }
539
540 /*
541 * Wrapper function for btrfs_fix_block_accounting().
542 *
543 * Returns 0 on success.
544 * Returns != 0 on error.
545 */
546 static int repair_block_accounting(struct btrfs_fs_info *fs_info)
547 {
548 struct btrfs_trans_handle *trans = NULL;
549 struct btrfs_root *root = fs_info->extent_root;
550 int ret;
551
552 trans = btrfs_start_transaction(root, 1);
553 if (IS_ERR(trans)) {
554 ret = PTR_ERR(trans);
555 error("fail to start transaction %s", strerror(-ret));
556 return ret;
557 }
558
559 ret = btrfs_fix_block_accounting(trans, root);
560 btrfs_commit_transaction(trans, root);
561 return ret;
562 }
563
564 /*
565 * This function only handles BACKREF_MISSING,
566 * If corresponding extent item exists, increase the ref, else insert an extent
567 * item and backref.
568 *
569 * Returns error bits after repair.
570 */
571 static int repair_tree_block_ref(struct btrfs_root *root,
572 struct extent_buffer *node,
573 struct node_refs *nrefs, int level, int err)
574 {
575 struct btrfs_trans_handle *trans = NULL;
576 struct btrfs_fs_info *fs_info = root->fs_info;
577 struct btrfs_root *extent_root = fs_info->extent_root;
578 struct btrfs_path path;
579 struct btrfs_extent_item *ei;
580 struct btrfs_tree_block_info *bi;
581 struct btrfs_key key;
582 struct extent_buffer *eb;
583 u32 size = sizeof(*ei);
584 u32 node_size = root->fs_info->nodesize;
585 int insert_extent = 0;
586 int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
587 int root_level = btrfs_header_level(root->node);
588 int generation;
589 int ret;
590 u64 owner;
591 u64 bytenr;
592 u64 flags = BTRFS_EXTENT_FLAG_TREE_BLOCK;
593 u64 parent = 0;
594
595 if ((err & BACKREF_MISSING) == 0)
596 return err;
597
598 WARN_ON(level > BTRFS_MAX_LEVEL);
599 WARN_ON(level < 0);
600
601 btrfs_init_path(&path);
602 bytenr = btrfs_header_bytenr(node);
603 owner = btrfs_header_owner(node);
604 generation = btrfs_header_generation(node);
605
606 key.objectid = bytenr;
607 key.type = (u8)-1;
608 key.offset = (u64)-1;
609
610 /* Search for the extent item */
611 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
612 if (ret <= 0) {
613 ret = -EIO;
614 goto out;
615 }
616
617 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
618 if (ret)
619 insert_extent = 1;
620
621 /* calculate if the extent item flag is full backref or not */
622 if (nrefs->full_backref[level] != 0)
623 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
624
625 ret = avoid_extents_overwrite(root->fs_info);
626 if (ret)
627 goto out;
628 trans = btrfs_start_transaction(extent_root, 1);
629 if (IS_ERR(trans)) {
630 ret = PTR_ERR(trans);
631 trans = NULL;
632 error("fail to start transaction %s", strerror(-ret));
633 goto out;
634 }
635 /* insert an extent item */
636 if (insert_extent) {
637 struct btrfs_disk_key copy_key;
638
639 generation = btrfs_header_generation(node);
640
641 if (level < root_level && nrefs->full_backref[level + 1] &&
642 owner != root->objectid) {
643 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
644 }
645
646 key.objectid = bytenr;
647 if (!skinny_metadata) {
648 key.type = BTRFS_EXTENT_ITEM_KEY;
649 key.offset = node_size;
650 size += sizeof(*bi);
651 } else {
652 key.type = BTRFS_METADATA_ITEM_KEY;
653 key.offset = level;
654 }
655
656 btrfs_release_path(&path);
657 ret = btrfs_insert_empty_item(trans, extent_root, &path, &key,
658 size);
659 if (ret)
660 goto out;
661
662 eb = path.nodes[0];
663 ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item);
664
665 btrfs_set_extent_refs(eb, ei, 0);
666 btrfs_set_extent_generation(eb, ei, generation);
667 btrfs_set_extent_flags(eb, ei, flags);
668
669 if (!skinny_metadata) {
670 bi = (struct btrfs_tree_block_info *)(ei + 1);
671 memset_extent_buffer(eb, 0, (unsigned long)bi,
672 sizeof(*bi));
673 btrfs_set_disk_key_objectid(&copy_key, root->objectid);
674 btrfs_set_disk_key_type(&copy_key, 0);
675 btrfs_set_disk_key_offset(&copy_key, 0);
676
677 btrfs_set_tree_block_level(eb, bi, level);
678 btrfs_set_tree_block_key(eb, bi, &copy_key);
679 }
680 btrfs_mark_buffer_dirty(eb);
681 printf("Added an extent item [%llu %u]\n", bytenr, node_size);
682 btrfs_update_block_group(extent_root, bytenr, node_size, 1, 0);
683
684 nrefs->refs[level] = 0;
685 nrefs->full_backref[level] =
686 flags & BTRFS_BLOCK_FLAG_FULL_BACKREF;
687 btrfs_release_path(&path);
688 }
689
690 if (level < root_level && nrefs->full_backref[level + 1] &&
691 owner != root->objectid)
692 parent = nrefs->bytenr[level + 1];
693
694 /* increase the ref */
695 ret = btrfs_inc_extent_ref(trans, extent_root, bytenr, node_size,
696 parent, root->objectid, level, 0);
697
698 nrefs->refs[level]++;
699 out:
700 if (trans)
701 btrfs_commit_transaction(trans, extent_root);
702 btrfs_release_path(&path);
703 if (ret) {
704 error(
705 "failed to repair tree block ref start %llu root %llu due to %s",
706 bytenr, root->objectid, strerror(-ret));
707 } else {
708 printf("Added one tree block ref start %llu %s %llu\n",
709 bytenr, parent ? "parent" : "root",
710 parent ? parent : root->objectid);
711 err &= ~BACKREF_MISSING;
712 }
713
714 return err;
715 }
716
717 /*
718 * Update global fs information.
719 */
720 static void account_bytes(struct btrfs_root *root, struct btrfs_path *path,
721 int level)
722 {
723 u32 free_nrs;
724 struct extent_buffer *eb = path->nodes[level];
725
726 total_btree_bytes += eb->len;
727 if (fs_root_objectid(root->objectid))
728 total_fs_tree_bytes += eb->len;
729 if (btrfs_header_owner(eb) == BTRFS_EXTENT_TREE_OBJECTID)
730 total_extent_tree_bytes += eb->len;
731
732 if (level == 0) {
733 btree_space_waste += btrfs_leaf_free_space(eb);
734 } else {
735 free_nrs = (BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) -
736 btrfs_header_nritems(eb));
737 btree_space_waste += free_nrs * sizeof(struct btrfs_key_ptr);
738 }
739 }
740
741 /*
742 * Find the @index according by @ino and name.
743 * Notice:time efficiency is O(N)
744 *
745 * @root: the root of the fs/file tree
746 * @index_ret: the index as return value
747 * @namebuf: the name to match
748 * @name_len: the length of name to match
749 * @file_type: the file_type of INODE_ITEM to match
750 *
751 * Returns 0 if found and *@index_ret will be modified with right value
752 * Returns< 0 not found and *@index_ret will be (u64)-1
753 */
754 static int find_dir_index(struct btrfs_root *root, u64 dirid, u64 location_id,
755 u64 *index_ret, char *namebuf, u32 name_len,
756 u8 file_type)
757 {
758 struct btrfs_path path;
759 struct extent_buffer *node;
760 struct btrfs_dir_item *di;
761 struct btrfs_key key;
762 struct btrfs_key location;
763 char name[BTRFS_NAME_LEN] = {0};
764
765 u32 total;
766 u32 cur = 0;
767 u32 len;
768 u32 data_len;
769 u8 filetype;
770 int slot;
771 int ret;
772
773 ASSERT(index_ret);
774
775 /* search from the last index */
776 key.objectid = dirid;
777 key.offset = (u64)-1;
778 key.type = BTRFS_DIR_INDEX_KEY;
779
780 btrfs_init_path(&path);
781 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
782 if (ret < 0)
783 return ret;
784
785 loop:
786 ret = btrfs_previous_item(root, &path, dirid, BTRFS_DIR_INDEX_KEY);
787 if (ret) {
788 ret = -ENOENT;
789 *index_ret = (64)-1;
790 goto out;
791 }
792 /* Check whether inode_id/filetype/name match */
793 node = path.nodes[0];
794 slot = path.slots[0];
795 di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
796 total = btrfs_item_size_nr(node, slot);
797 while (cur < total) {
798 ret = -ENOENT;
799 len = btrfs_dir_name_len(node, di);
800 data_len = btrfs_dir_data_len(node, di);
801
802 btrfs_dir_item_key_to_cpu(node, di, &location);
803 if (location.objectid != location_id ||
804 location.type != BTRFS_INODE_ITEM_KEY ||
805 location.offset != 0)
806 goto next;
807
808 filetype = btrfs_dir_type(node, di);
809 if (file_type != filetype)
810 goto next;
811
812 if (len > BTRFS_NAME_LEN)
813 len = BTRFS_NAME_LEN;
814
815 read_extent_buffer(node, name, (unsigned long)(di + 1), len);
816 if (len != name_len || strncmp(namebuf, name, len))
817 goto next;
818
819 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
820 *index_ret = key.offset;
821 ret = 0;
822 goto out;
823 next:
824 len += sizeof(*di) + data_len;
825 di = (struct btrfs_dir_item *)((char *)di + len);
826 cur += len;
827 }
828 goto loop;
829
830 out:
831 btrfs_release_path(&path);
832 return ret;
833 }
834
835 /*
836 * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
837 * INODE_REF/INODE_EXTREF match.
838 *
839 * @root: the root of the fs/file tree
840 * @key: the key of the DIR_ITEM/DIR_INDEX, key->offset will be right
841 * value while find index
842 * @location_key: location key of the struct btrfs_dir_item to match
843 * @name: the name to match
844 * @namelen: the length of name
845 * @file_type: the type of file to math
846 *
847 * Return 0 if no error occurred.
848 * Return DIR_ITEM_MISSING/DIR_INDEX_MISSING if couldn't find
849 * DIR_ITEM/DIR_INDEX
850 * Return DIR_ITEM_MISMATCH/DIR_INDEX_MISMATCH if INODE_REF/INODE_EXTREF
851 * and DIR_ITEM/DIR_INDEX mismatch
852 */
853 static int find_dir_item(struct btrfs_root *root, struct btrfs_key *key,
854 struct btrfs_key *location_key, char *name,
855 u32 namelen, u8 file_type)
856 {
857 struct btrfs_path path;
858 struct extent_buffer *node;
859 struct btrfs_dir_item *di;
860 struct btrfs_key location;
861 char namebuf[BTRFS_NAME_LEN] = {0};
862 u32 total;
863 u32 cur = 0;
864 u32 len;
865 u32 data_len;
866 u8 filetype;
867 int slot;
868 int ret;
869
870 /* get the index by traversing all index */
871 if (key->type == BTRFS_DIR_INDEX_KEY && key->offset == (u64)-1) {
872 ret = find_dir_index(root, key->objectid,
873 location_key->objectid, &key->offset,
874 name, namelen, file_type);
875 if (ret)
876 ret = DIR_INDEX_MISSING;
877 return ret;
878 }
879
880 btrfs_init_path(&path);
881 ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
882 if (ret) {
883 ret = key->type == BTRFS_DIR_ITEM_KEY ? DIR_ITEM_MISSING :
884 DIR_INDEX_MISSING;
885 goto out;
886 }
887
888 /* Check whether inode_id/filetype/name match */
889 node = path.nodes[0];
890 slot = path.slots[0];
891 di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
892 total = btrfs_item_size_nr(node, slot);
893 while (cur < total) {
894 ret = key->type == BTRFS_DIR_ITEM_KEY ?
895 DIR_ITEM_MISMATCH : DIR_INDEX_MISMATCH;
896
897 len = btrfs_dir_name_len(node, di);
898 data_len = btrfs_dir_data_len(node, di);
899
900 btrfs_dir_item_key_to_cpu(node, di, &location);
901 if (location.objectid != location_key->objectid ||
902 location.type != location_key->type ||
903 location.offset != location_key->offset)
904 goto next;
905
906 filetype = btrfs_dir_type(node, di);
907 if (file_type != filetype)
908 goto next;
909
910 if (len > BTRFS_NAME_LEN) {
911 len = BTRFS_NAME_LEN;
912 warning("root %llu %s[%llu %llu] name too long %u, trimmed",
913 root->objectid,
914 key->type == BTRFS_DIR_ITEM_KEY ?
915 "DIR_ITEM" : "DIR_INDEX",
916 key->objectid, key->offset, len);
917 }
918 read_extent_buffer(node, namebuf, (unsigned long)(di + 1),
919 len);
920 if (len != namelen || strncmp(namebuf, name, len))
921 goto next;
922
923 ret = 0;
924 goto out;
925 next:
926 len += sizeof(*di) + data_len;
927 di = (struct btrfs_dir_item *)((char *)di + len);
928 cur += len;
929 }
930
931 out:
932 btrfs_release_path(&path);
933 return ret;
934 }
935
936 /*
937 * The ternary means dir item, dir index and relative inode ref.
938 * The function handles errs: INODE_MISSING, DIR_INDEX_MISSING
939 * DIR_INDEX_MISMATCH, DIR_ITEM_MISSING, DIR_ITEM_MISMATCH by the follow
940 * strategy:
941 * If two of three is missing or mismatched, delete the existing one.
942 * If one of three is missing or mismatched, add the missing one.
943 *
944 * returns 0 means success.
945 * returns not 0 means on error;
946 */
947 int repair_ternary_lowmem(struct btrfs_root *root, u64 dir_ino, u64 ino,
948 u64 index, char *name, int name_len, u8 filetype,
949 int err)
950 {
951 struct btrfs_trans_handle *trans;
952 int stage = 0;
953 int ret = 0;
954
955 /*
956 * stage shall be one of following valild values:
957 * 0: Fine, nothing to do.
958 * 1: One of three is wrong, so add missing one.
959 * 2: Two of three is wrong, so delete existed one.
960 */
961 if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING))
962 stage++;
963 if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING))
964 stage++;
965 if (err & (INODE_REF_MISSING))
966 stage++;
967
968 /* stage must be smllarer than 3 */
969 ASSERT(stage < 3);
970
971 trans = btrfs_start_transaction(root, 1);
972 if (stage == 2) {
973 ret = btrfs_unlink(trans, root, ino, dir_ino, index, name,
974 name_len, 0);
975 goto out;
976 }
977 if (stage == 1) {
978 ret = btrfs_unlink(trans, root, ino, dir_ino, index, name,
979 name_len, 0);
980 if (ret)
981 goto out;
982 ret = btrfs_add_link(trans, root, ino, dir_ino, name, name_len,
983 filetype, &index, 1, 1);
984 goto out;
985 }
986 out:
987 btrfs_commit_transaction(trans, root);
988
989 if (ret)
990 error("fail to repair inode %llu name %s filetype %u",
991 ino, name, filetype);
992 else
993 printf("%s ref/dir_item of inode %llu name %s filetype %u\n",
994 stage == 2 ? "Delete" : "Add",
995 ino, name, filetype);
996
997 return ret;
998 }
999
1000 /*
1001 * Prints inode ref error message
1002 */
1003 static void print_inode_ref_err(struct btrfs_root *root, struct btrfs_key *key,
1004 u64 index, const char *namebuf, int name_len,
1005 u8 filetype, int err)
1006 {
1007 if (!err)
1008 return;
1009
1010 /* root dir error */
1011 if (key->objectid == BTRFS_FIRST_FREE_OBJECTID) {
1012 error(
1013 "root %llu root dir shouldn't have INODE REF[%llu %llu] name %s",
1014 root->objectid, key->objectid, key->offset, namebuf);
1015 return;
1016 }
1017
1018 /* normal error */
1019 if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING))
1020 error("root %llu DIR ITEM[%llu %llu] %s name %s filetype %u",
1021 root->objectid, key->offset,
1022 btrfs_name_hash(namebuf, name_len),
1023 err & DIR_ITEM_MISMATCH ? "mismatch" : "missing",
1024 namebuf, filetype);
1025 if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING))
1026 error("root %llu DIR INDEX[%llu %llu] %s name %s filetype %u",
1027 root->objectid, key->offset, index,
1028 err & DIR_ITEM_MISMATCH ? "mismatch" : "missing",
1029 namebuf, filetype);
1030 }
1031
1032 /*
1033 * Traverse the given INODE_REF and call find_dir_item() to find related
1034 * DIR_ITEM/DIR_INDEX.
1035 *
1036 * @root: the root of the fs/file tree
1037 * @ref_key: the key of the INODE_REF
1038 * @path the path provides node and slot
1039 * @refs: the count of INODE_REF
1040 * @mode: the st_mode of INODE_ITEM
1041 * @name_ret: returns with the first ref's name
1042 * @name_len_ret: len of the name_ret
1043 *
1044 * Return 0 if no error occurred.
1045 */
1046 static int check_inode_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
1047 struct btrfs_path *path, char *name_ret,
1048 u32 *namelen_ret, u64 *refs_ret, int mode)
1049 {
1050 struct btrfs_key key;
1051 struct btrfs_key location;
1052 struct btrfs_inode_ref *ref;
1053 struct extent_buffer *node;
1054 char namebuf[BTRFS_NAME_LEN] = {0};
1055 u32 total;
1056 u32 cur = 0;
1057 u32 len;
1058 u32 name_len;
1059 u64 index;
1060 int ret;
1061 int err = 0;
1062 int tmp_err;
1063 int slot;
1064 int need_research = 0;
1065 u64 refs;
1066
1067 begin:
1068 err = 0;
1069 cur = 0;
1070 refs = *refs_ret;
1071
1072 /* since after repair, path and the dir item may be changed */
1073 if (need_research) {
1074 need_research = 0;
1075 btrfs_release_path(path);
1076 ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0);
1077 /*
1078 * The item was deleted, let the path point to the last checked
1079 * item.
1080 */
1081 if (ret > 0) {
1082 if (path->slots[0] == 0)
1083 btrfs_prev_leaf(root, path);
1084 else
1085 path->slots[0]--;
1086 }
1087 if (ret)
1088 goto out;
1089 }
1090
1091 location.objectid = ref_key->objectid;
1092 location.type = BTRFS_INODE_ITEM_KEY;
1093 location.offset = 0;
1094 node = path->nodes[0];
1095 slot = path->slots[0];
1096
1097 memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf));
1098 ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
1099 total = btrfs_item_size_nr(node, slot);
1100
1101 next:
1102 /* Update inode ref count */
1103 refs++;
1104 tmp_err = 0;
1105 index = btrfs_inode_ref_index(node, ref);
1106 name_len = btrfs_inode_ref_name_len(node, ref);
1107
1108 if (name_len <= BTRFS_NAME_LEN) {
1109 len = name_len;
1110 } else {
1111 len = BTRFS_NAME_LEN;
1112 warning("root %llu INODE_REF[%llu %llu] name too long",
1113 root->objectid, ref_key->objectid, ref_key->offset);
1114 }
1115
1116 read_extent_buffer(node, namebuf, (unsigned long)(ref + 1), len);
1117
1118 /* copy the first name found to name_ret */
1119 if (refs == 1 && name_ret) {
1120 memcpy(name_ret, namebuf, len);
1121 *namelen_ret = len;
1122 }
1123
1124 /* Check root dir ref */
1125 if (ref_key->objectid == BTRFS_FIRST_FREE_OBJECTID) {
1126 if (index != 0 || len != strlen("..") ||
1127 strncmp("..", namebuf, len) ||
1128 ref_key->offset != BTRFS_FIRST_FREE_OBJECTID) {
1129 /* set err bits then repair will delete the ref */
1130 err |= DIR_INDEX_MISSING;
1131 err |= DIR_ITEM_MISSING;
1132 }
1133 goto end;
1134 }
1135
1136 /* Find related DIR_INDEX */
1137 key.objectid = ref_key->offset;
1138 key.type = BTRFS_DIR_INDEX_KEY;
1139 key.offset = index;
1140 tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
1141 imode_to_type(mode));
1142
1143 /* Find related dir_item */
1144 key.objectid = ref_key->offset;
1145 key.type = BTRFS_DIR_ITEM_KEY;
1146 key.offset = btrfs_name_hash(namebuf, len);
1147 tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
1148 imode_to_type(mode));
1149 end:
1150 if (tmp_err && repair) {
1151 ret = repair_ternary_lowmem(root, ref_key->offset,
1152 ref_key->objectid, index, namebuf,
1153 name_len, imode_to_type(mode),
1154 tmp_err);
1155 if (!ret) {
1156 need_research = 1;
1157 goto begin;
1158 }
1159 }
1160 print_inode_ref_err(root, ref_key, index, namebuf, name_len,
1161 imode_to_type(mode), tmp_err);
1162 err |= tmp_err;
1163 len = sizeof(*ref) + name_len;
1164 ref = (struct btrfs_inode_ref *)((char *)ref + len);
1165 cur += len;
1166 if (cur < total)
1167 goto next;
1168
1169 out:
1170 *refs_ret = refs;
1171 return err;
1172 }
1173
1174 /*
1175 * Traverse the given INODE_EXTREF and call find_dir_item() to find related
1176 * DIR_ITEM/DIR_INDEX.
1177 *
1178 * @root: the root of the fs/file tree
1179 * @ref_key: the key of the INODE_EXTREF
1180 * @refs: the count of INODE_EXTREF
1181 * @mode: the st_mode of INODE_ITEM
1182 *
1183 * Return 0 if no error occurred.
1184 */
1185 static int check_inode_extref(struct btrfs_root *root,
1186 struct btrfs_key *ref_key,
1187 struct extent_buffer *node, int slot, u64 *refs,
1188 int mode)
1189 {
1190 struct btrfs_key key;
1191 struct btrfs_key location;
1192 struct btrfs_inode_extref *extref;
1193 char namebuf[BTRFS_NAME_LEN] = {0};
1194 u32 total;
1195 u32 cur = 0;
1196 u32 len;
1197 u32 name_len;
1198 u64 index;
1199 u64 parent;
1200 int ret;
1201 int err = 0;
1202
1203 location.objectid = ref_key->objectid;
1204 location.type = BTRFS_INODE_ITEM_KEY;
1205 location.offset = 0;
1206
1207 extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
1208 total = btrfs_item_size_nr(node, slot);
1209
1210 next:
1211 /* update inode ref count */
1212 (*refs)++;
1213 name_len = btrfs_inode_extref_name_len(node, extref);
1214 index = btrfs_inode_extref_index(node, extref);
1215 parent = btrfs_inode_extref_parent(node, extref);
1216 if (name_len <= BTRFS_NAME_LEN) {
1217 len = name_len;
1218 } else {
1219 len = BTRFS_NAME_LEN;
1220 warning("root %llu INODE_EXTREF[%llu %llu] name too long",
1221 root->objectid, ref_key->objectid, ref_key->offset);
1222 }
1223 read_extent_buffer(node, namebuf, (unsigned long)(extref + 1), len);
1224
1225 /* Check root dir ref name */
1226 if (index == 0 && strncmp(namebuf, "..", name_len)) {
1227 error("root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s",
1228 root->objectid, ref_key->objectid, ref_key->offset,
1229 namebuf);
1230 err |= ROOT_DIR_ERROR;
1231 }
1232
1233 /* find related dir_index */
1234 key.objectid = parent;
1235 key.type = BTRFS_DIR_INDEX_KEY;
1236 key.offset = index;
1237 ret = find_dir_item(root, &key, &location, namebuf, len, mode);
1238 err |= ret;
1239
1240 /* find related dir_item */
1241 key.objectid = parent;
1242 key.type = BTRFS_DIR_ITEM_KEY;
1243 key.offset = btrfs_name_hash(namebuf, len);
1244 ret = find_dir_item(root, &key, &location, namebuf, len, mode);
1245 err |= ret;
1246
1247 len = sizeof(*extref) + name_len;
1248 extref = (struct btrfs_inode_extref *)((char *)extref + len);
1249 cur += len;
1250
1251 if (cur < total)
1252 goto next;
1253
1254 return err;
1255 }
1256
1257 /*
1258 * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified
1259 * DIR_ITEM/DIR_INDEX match.
1260 * Return with @index_ret.
1261 *
1262 * @root: the root of the fs/file tree
1263 * @key: the key of the INODE_REF/INODE_EXTREF
1264 * @name: the name in the INODE_REF/INODE_EXTREF
1265 * @namelen: the length of name in the INODE_REF/INODE_EXTREF
1266 * @index_ret: the index in the INODE_REF/INODE_EXTREF,
1267 * value (64)-1 means do not check index
1268 *
1269 * Return 0 if no error occurred.
1270 * Return >0 for error bitmap
1271 */
1272 static int find_inode_ref(struct btrfs_root *root, struct btrfs_key *key,
1273 char *name, int namelen, u64 *index_ret)
1274
1275 {
1276 struct btrfs_path path;
1277 struct btrfs_inode_ref *ref;
1278 struct btrfs_inode_extref *extref;
1279 struct extent_buffer *node;
1280 char ref_namebuf[BTRFS_NAME_LEN] = {0};
1281 u32 total;
1282 u32 cur = 0;
1283 u32 len;
1284 u32 ref_namelen;
1285 u64 ref_index;
1286 u64 parent;
1287 u64 dir_id;
1288 int slot;
1289 int ret;
1290
1291 ASSERT(index_ret);
1292
1293 btrfs_init_path(&path);
1294 ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
1295 if (ret) {
1296 ret = INODE_REF_MISSING;
1297 goto extref;
1298 }
1299
1300 node = path.nodes[0];
1301 slot = path.slots[0];
1302
1303 ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
1304 total = btrfs_item_size_nr(node, slot);
1305
1306 /* Iterate all entry of INODE_REF */
1307 while (cur < total) {
1308 ret = INODE_REF_MISSING;
1309
1310 ref_namelen = btrfs_inode_ref_name_len(node, ref);
1311 ref_index = btrfs_inode_ref_index(node, ref);
1312 if (*index_ret != (u64)-1 && *index_ret != ref_index)
1313 goto next_ref;
1314
1315 if (cur + sizeof(*ref) + ref_namelen > total ||
1316 ref_namelen > BTRFS_NAME_LEN) {
1317 warning("root %llu INODE %s[%llu %llu] name too long",
1318 root->objectid,
1319 key->type == BTRFS_INODE_REF_KEY ?
1320 "REF" : "EXTREF",
1321 key->objectid, key->offset);
1322
1323 if (cur + sizeof(*ref) > total)
1324 break;
1325 len = min_t(u32, total - cur - sizeof(*ref),
1326 BTRFS_NAME_LEN);
1327 } else {
1328 len = ref_namelen;
1329 }
1330
1331 read_extent_buffer(node, ref_namebuf, (unsigned long)(ref + 1),
1332 len);
1333
1334 if (len != namelen || strncmp(ref_namebuf, name, len))
1335 goto next_ref;
1336
1337 *index_ret = ref_index;
1338 ret = 0;
1339 goto out;
1340 next_ref:
1341 len = sizeof(*ref) + ref_namelen;
1342 ref = (struct btrfs_inode_ref *)((char *)ref + len);
1343 cur += len;
1344 }
1345
1346 extref:
1347
1348 /* Skip if not support EXTENDED_IREF feature */
1349 if (!btrfs_fs_incompat(root->fs_info, EXTENDED_IREF))
1350 goto out;
1351
1352 btrfs_release_path(&path);
1353 btrfs_init_path(&path);
1354
1355 dir_id = key->offset;
1356 key->type = BTRFS_INODE_EXTREF_KEY;
1357 key->offset = btrfs_extref_hash(dir_id, name, namelen);
1358
1359 ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
1360 if (ret) {
1361 ret = INODE_REF_MISSING;
1362 goto out;
1363 }
1364
1365 node = path.nodes[0];
1366 slot = path.slots[0];
1367
1368 extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
1369 cur = 0;
1370 total = btrfs_item_size_nr(node, slot);
1371
1372 /* Iterate all entry of INODE_EXTREF */
1373 while (cur < total) {
1374 ret = INODE_REF_MISSING;
1375
1376 ref_namelen = btrfs_inode_extref_name_len(node, extref);
1377 ref_index = btrfs_inode_extref_index(node, extref);
1378 parent = btrfs_inode_extref_parent(node, extref);
1379 if (*index_ret != (u64)-1 && *index_ret != ref_index)
1380 goto next_extref;
1381
1382 if (parent != dir_id)
1383 goto next_extref;
1384
1385 if (ref_namelen <= BTRFS_NAME_LEN) {
1386 len = ref_namelen;
1387 } else {
1388 len = BTRFS_NAME_LEN;
1389 warning("root %llu INODE %s[%llu %llu] name too long",
1390 root->objectid,
1391 key->type == BTRFS_INODE_REF_KEY ?
1392 "REF" : "EXTREF",
1393 key->objectid, key->offset);
1394 }
1395 read_extent_buffer(node, ref_namebuf,
1396 (unsigned long)(extref + 1), len);
1397
1398 if (len != namelen || strncmp(ref_namebuf, name, len))
1399 goto next_extref;
1400
1401 *index_ret = ref_index;
1402 ret = 0;
1403 goto out;
1404
1405 next_extref:
1406 len = sizeof(*extref) + ref_namelen;
1407 extref = (struct btrfs_inode_extref *)((char *)extref + len);
1408 cur += len;
1409
1410 }
1411 out:
1412 btrfs_release_path(&path);
1413 return ret;
1414 }
1415
1416 static int create_inode_item_lowmem(struct btrfs_trans_handle *trans,
1417 struct btrfs_root *root, u64 ino,
1418 u8 filetype)
1419 {
1420 u32 mode = (filetype == BTRFS_FT_DIR ? S_IFDIR : S_IFREG) | 0755;
1421
1422 return insert_inode_item(trans, root, ino, 0, 0, 0, mode);
1423 }
1424
1425 /*
1426 * Insert the missing inode item.
1427 *
1428 * Returns 0 means success.
1429 * Returns <0 means error.
1430 */
1431 static int repair_inode_item_missing(struct btrfs_root *root, u64 ino,
1432 u8 filetype)
1433 {
1434 struct btrfs_key key;
1435 struct btrfs_trans_handle *trans;
1436 struct btrfs_path path;
1437 int ret;
1438
1439 key.objectid = ino;
1440 key.type = BTRFS_INODE_ITEM_KEY;
1441 key.offset = 0;
1442
1443 btrfs_init_path(&path);
1444 trans = btrfs_start_transaction(root, 1);
1445 if (IS_ERR(trans)) {
1446 ret = -EIO;
1447 goto out;
1448 }
1449
1450 ret = btrfs_search_slot(trans, root, &key, &path, 1, 1);
1451 if (ret < 0 || !ret)
1452 goto fail;
1453
1454 /* insert inode item */
1455 create_inode_item_lowmem(trans, root, ino, filetype);
1456 ret = 0;
1457 fail:
1458 btrfs_commit_transaction(trans, root);
1459 out:
1460 if (ret)
1461 error("failed to repair root %llu INODE ITEM[%llu] missing",
1462 root->objectid, ino);
1463 btrfs_release_path(&path);
1464 return ret;
1465 }
1466
1467 /*
1468 * Call repair_inode_item_missing and repair_ternary_lowmem to repair
1469 *
1470 * Returns error after repair
1471 */
1472 static int repair_dir_item(struct btrfs_root *root, u64 dirid, u64 ino,
1473 u64 index, u8 filetype, char *namebuf, u32 name_len,
1474 int err)
1475 {
1476 int ret;
1477
1478 if (err & INODE_ITEM_MISSING) {
1479 ret = repair_inode_item_missing(root, ino, filetype);
1480 if (!ret)
1481 err &= ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING);
1482 }
1483
1484 if (err & ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING)) {
1485 ret = repair_ternary_lowmem(root, dirid, ino, index, namebuf,
1486 name_len, filetype, err);
1487 if (!ret) {
1488 err &= ~(DIR_INDEX_MISMATCH | DIR_INDEX_MISSING);
1489 err &= ~(DIR_ITEM_MISMATCH | DIR_ITEM_MISSING);
1490 err &= ~(INODE_REF_MISSING);
1491 }
1492 }
1493 return err;
1494 }
1495
1496 static void print_dir_item_err(struct btrfs_root *root, struct btrfs_key *key,
1497 u64 ino, u64 index, const char *namebuf,
1498 int name_len, u8 filetype, int err)
1499 {
1500 if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) {
1501 error("root %llu DIR ITEM[%llu %llu] name %s filetype %d %s",
1502 root->objectid, key->objectid, key->offset, namebuf,
1503 filetype,
1504 err & DIR_ITEM_MISMATCH ? "mismath" : "missing");
1505 }
1506
1507 if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) {
1508 error("root %llu DIR INDEX[%llu %llu] name %s filetype %d %s",
1509 root->objectid, key->objectid, index, namebuf, filetype,
1510 err & DIR_ITEM_MISMATCH ? "mismath" : "missing");
1511 }
1512
1513 if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH)) {
1514 error(
1515 "root %llu INODE_ITEM[%llu] index %llu name %s filetype %d %s",
1516 root->objectid, ino, index, namebuf, filetype,
1517 err & INODE_ITEM_MISMATCH ? "mismath" : "missing");
1518 }
1519
1520 if (err & INODE_REF_MISSING)
1521 error(
1522 "root %llu INODE REF[%llu, %llu] name %s filetype %u missing",
1523 root->objectid, ino, key->objectid, namebuf, filetype);
1524
1525 }
1526
1527 /*
1528 * Traverse the given DIR_ITEM/DIR_INDEX and check related INODE_ITEM and
1529 * call find_inode_ref() to check related INODE_REF/INODE_EXTREF.
1530 *
1531 * @root: the root of the fs/file tree
1532 * @key: the key of the INODE_REF/INODE_EXTREF
1533 * @path: the path
1534 * @size: the st_size of the INODE_ITEM
1535 *
1536 * Return 0 if no error occurred.
1537 * Return DIR_COUNT_AGAIN if the isize of the inode should be recalculated.
1538 */
1539 static int check_dir_item(struct btrfs_root *root, struct btrfs_key *di_key,
1540 struct btrfs_path *path, u64 *size)
1541 {
1542 struct btrfs_dir_item *di;
1543 struct btrfs_inode_item *ii;
1544 struct btrfs_key key;
1545 struct btrfs_key location;
1546 struct extent_buffer *node;
1547 int slot;
1548 char namebuf[BTRFS_NAME_LEN] = {0};
1549 u32 total;
1550 u32 cur = 0;
1551 u32 len;
1552 u32 name_len;
1553 u32 data_len;
1554 u8 filetype;
1555 u32 mode = 0;
1556 u64 index;
1557 int ret;
1558 int err;
1559 int tmp_err;
1560 int need_research = 0;
1561
1562 begin:
1563 err = 0;
1564 cur = 0;
1565
1566 /* since after repair, path and the dir item may be changed */
1567 if (need_research) {
1568 need_research = 0;
1569 err |= DIR_COUNT_AGAIN;
1570 btrfs_release_path(path);
1571 ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0);
1572 /* the item was deleted, let path point the last checked item */
1573 if (ret > 0) {
1574 if (path->slots[0] == 0)
1575 btrfs_prev_leaf(root, path);
1576 else
1577 path->slots[0]--;
1578 }
1579 if (ret)
1580 goto out;
1581 }
1582
1583 node = path->nodes[0];
1584 slot = path->slots[0];
1585
1586 di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
1587 total = btrfs_item_size_nr(node, slot);
1588 memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf));
1589
1590 while (cur < total) {
1591 /*
1592 * For DIR_ITEM set index to (u64)-1, so that find_inode_ref
1593 * ignore index check.
1594 */
1595 if (di_key->type == BTRFS_DIR_INDEX_KEY)
1596 index = di_key->offset;
1597 else
1598 index = (u64)-1;
1599
1600 data_len = btrfs_dir_data_len(node, di);
1601 tmp_err = 0;
1602 if (data_len)
1603 error("root %llu %s[%llu %llu] data_len shouldn't be %u",
1604 root->objectid,
1605 di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX",
1606 di_key->objectid, di_key->offset, data_len);
1607
1608 name_len = btrfs_dir_name_len(node, di);
1609 if (name_len <= BTRFS_NAME_LEN) {
1610 len = name_len;
1611 } else {
1612 len = BTRFS_NAME_LEN;
1613 warning("root %llu %s[%llu %llu] name too long",
1614 root->objectid,
1615 di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX",
1616 di_key->objectid, di_key->offset);
1617 }
1618 (*size) += name_len;
1619 read_extent_buffer(node, namebuf, (unsigned long)(di + 1),
1620 len);
1621 filetype = btrfs_dir_type(node, di);
1622
1623 if (di_key->type == BTRFS_DIR_ITEM_KEY &&
1624 di_key->offset != btrfs_name_hash(namebuf, len)) {
1625 err |= -EIO;
1626 error("root %llu DIR_ITEM[%llu %llu] name %s namelen %u filetype %u mismatch with its hash, wanted %llu have %llu",
1627 root->objectid, di_key->objectid, di_key->offset,
1628 namebuf, len, filetype, di_key->offset,
1629 btrfs_name_hash(namebuf, len));
1630 }
1631
1632 btrfs_dir_item_key_to_cpu(node, di, &location);
1633 /* Ignore related ROOT_ITEM check */
1634 if (location.type == BTRFS_ROOT_ITEM_KEY)
1635 goto next;
1636
1637 btrfs_release_path(path);
1638 /* Check relative INODE_ITEM(existence/filetype) */
1639 ret = btrfs_search_slot(NULL, root, &location, path, 0, 0);
1640 if (ret) {
1641 tmp_err |= INODE_ITEM_MISSING;
1642 goto next;
1643 }
1644
1645 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
1646 struct btrfs_inode_item);
1647 mode = btrfs_inode_mode(path->nodes[0], ii);
1648 if (imode_to_type(mode) != filetype) {
1649 tmp_err |= INODE_ITEM_MISMATCH;
1650 goto next;
1651 }
1652
1653 /* Check relative INODE_REF/INODE_EXTREF */
1654 key.objectid = location.objectid;
1655 key.type = BTRFS_INODE_REF_KEY;
1656 key.offset = di_key->objectid;
1657 tmp_err |= find_inode_ref(root, &key, namebuf, len, &index);
1658
1659 /* check relative INDEX/ITEM */
1660 key.objectid = di_key->objectid;
1661 if (key.type == BTRFS_DIR_ITEM_KEY) {
1662 key.type = BTRFS_DIR_INDEX_KEY;
1663 key.offset = index;
1664 } else {
1665 key.type = BTRFS_DIR_ITEM_KEY;
1666 key.offset = btrfs_name_hash(namebuf, name_len);
1667 }
1668
1669 tmp_err |= find_dir_item(root, &key, &location, namebuf,
1670 name_len, filetype);
1671 /* find_dir_item may find index */
1672 if (key.type == BTRFS_DIR_INDEX_KEY)
1673 index = key.offset;
1674 next:
1675
1676 if (tmp_err && repair) {
1677 ret = repair_dir_item(root, di_key->objectid,
1678 location.objectid, index,
1679 imode_to_type(mode), namebuf,
1680 name_len, tmp_err);
1681 if (ret != tmp_err) {
1682 need_research = 1;
1683 goto begin;
1684 }
1685 }
1686 btrfs_release_path(path);
1687 print_dir_item_err(root, di_key, location.objectid, index,
1688 namebuf, name_len, filetype, tmp_err);
1689 err |= tmp_err;
1690 len = sizeof(*di) + name_len + data_len;
1691 di = (struct btrfs_dir_item *)((char *)di + len);
1692 cur += len;
1693
1694 if (di_key->type == BTRFS_DIR_INDEX_KEY && cur < total) {
1695 error("root %llu DIR_INDEX[%llu %llu] should contain only one entry",
1696 root->objectid, di_key->objectid,
1697 di_key->offset);
1698 break;
1699 }
1700 }
1701 out:
1702 /* research path */
1703 btrfs_release_path(path);
1704 ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0);
1705 if (ret)
1706 err |= ret > 0 ? -ENOENT : ret;
1707 return err;
1708 }
1709
1710 /*
1711 * Wrapper function of btrfs_punch_hole.
1712 *
1713 * Returns 0 means success.
1714 * Returns not 0 means error.
1715 */
1716 static int punch_extent_hole(struct btrfs_root *root, u64 ino, u64 start,
1717 u64 len)
1718 {
1719 struct btrfs_trans_handle *trans;
1720 int ret = 0;
1721
1722 trans = btrfs_start_transaction(root, 1);
1723 if (IS_ERR(trans))
1724 return PTR_ERR(trans);
1725
1726 ret = btrfs_punch_hole(trans, root, ino, start, len);
1727 if (ret)
1728 error("failed to add hole [%llu, %llu] in inode [%llu]",
1729 start, len, ino);
1730 else
1731 printf("Add a hole [%llu, %llu] in inode [%llu]\n", start, len,
1732 ino);
1733
1734 btrfs_commit_transaction(trans, root);
1735 return ret;
1736 }
1737
1738 /*
1739 * Check file extent datasum/hole, update the size of the file extents,
1740 * check and update the last offset of the file extent.
1741 *
1742 * @root: the root of fs/file tree.
1743 * @fkey: the key of the file extent.
1744 * @nodatasum: INODE_NODATASUM feature.
1745 * @size: the sum of all EXTENT_DATA items size for this inode.
1746 * @end: the offset of the last extent.
1747 *
1748 * Return 0 if no error occurred.
1749 */
1750 static int check_file_extent(struct btrfs_root *root, struct btrfs_key *fkey,
1751 struct extent_buffer *node, int slot,
1752 unsigned int nodatasum, u64 *size, u64 *end)
1753 {
1754 struct btrfs_file_extent_item *fi;
1755 u64 disk_bytenr;
1756 u64 disk_num_bytes;
1757 u64 extent_num_bytes;
1758 u64 extent_offset;
1759 u64 csum_found; /* In byte size, sectorsize aligned */
1760 u64 search_start; /* Logical range start we search for csum */
1761 u64 search_len; /* Logical range len we search for csum */
1762 u32 max_inline_extent_size = min_t(u32, root->fs_info->sectorsize - 1,
1763 BTRFS_MAX_INLINE_DATA_SIZE(root->fs_info));
1764 unsigned int extent_type;
1765 unsigned int is_hole;
1766 int compressed = 0;
1767 int ret;
1768 int err = 0;
1769
1770 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
1771
1772 /* Check inline extent */
1773 extent_type = btrfs_file_extent_type(node, fi);
1774 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1775 struct btrfs_item *e = btrfs_item_nr(slot);
1776 u32 item_inline_len;
1777
1778 item_inline_len = btrfs_file_extent_inline_item_len(node, e);
1779 extent_num_bytes = btrfs_file_extent_inline_len(node, slot, fi);
1780 compressed = btrfs_file_extent_compression(node, fi);
1781 if (extent_num_bytes == 0) {
1782 error(
1783 "root %llu EXTENT_DATA[%llu %llu] has empty inline extent",
1784 root->objectid, fkey->objectid, fkey->offset);
1785 err |= FILE_EXTENT_ERROR;
1786 }
1787 if (compressed) {
1788 if (extent_num_bytes > root->fs_info->sectorsize) {
1789 error(
1790 "root %llu EXTENT_DATA[%llu %llu] too large inline extent ram size, have %llu, max: %u",
1791 root->objectid, fkey->objectid,
1792 fkey->offset, extent_num_bytes,
1793 root->fs_info->sectorsize - 1);
1794 err |= FILE_EXTENT_ERROR;
1795 }
1796 if (item_inline_len > max_inline_extent_size) {
1797 error(
1798 "root %llu EXTENT_DATA[%llu %llu] too large inline extent on-disk size, have %u, max: %u",
1799 root->objectid, fkey->objectid,
1800 fkey->offset, item_inline_len,
1801 max_inline_extent_size);
1802 err |= FILE_EXTENT_ERROR;
1803 }
1804 } else {
1805 if (extent_num_bytes > max_inline_extent_size) {
1806 error(
1807 "root %llu EXTENT_DATA[%llu %llu] too large inline extent size, have %llu, max: %u",
1808 root->objectid, fkey->objectid, fkey->offset,
1809 extent_num_bytes, max_inline_extent_size);
1810 err |= FILE_EXTENT_ERROR;
1811 }
1812 }
1813 if (!compressed && extent_num_bytes != item_inline_len) {
1814 error(
1815 "root %llu EXTENT_DATA[%llu %llu] wrong inline size, have: %llu, expected: %u",
1816 root->objectid, fkey->objectid, fkey->offset,
1817 extent_num_bytes, item_inline_len);
1818 err |= FILE_EXTENT_ERROR;
1819 }
1820 *end += extent_num_bytes;
1821 *size += extent_num_bytes;
1822 return err;
1823 }
1824
1825 /* Check extent type */
1826 if (extent_type != BTRFS_FILE_EXTENT_REG &&
1827 extent_type != BTRFS_FILE_EXTENT_PREALLOC) {
1828 err |= FILE_EXTENT_ERROR;
1829 error("root %llu EXTENT_DATA[%llu %llu] type bad",
1830 root->objectid, fkey->objectid, fkey->offset);
1831 return err;
1832 }
1833
1834 /* Check REG_EXTENT/PREALLOC_EXTENT */
1835 disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
1836 disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
1837 extent_num_bytes = btrfs_file_extent_num_bytes(node, fi);
1838 extent_offset = btrfs_file_extent_offset(node, fi);
1839 compressed = btrfs_file_extent_compression(node, fi);
1840 is_hole = (disk_bytenr == 0) && (disk_num_bytes == 0);
1841
1842 /*
1843 * Check EXTENT_DATA csum
1844 *
1845 * For plain (uncompressed) extent, we should only check the range
1846 * we're referring to, as it's possible that part of prealloc extent
1847 * has been written, and has csum:
1848 *
1849 * |<--- Original large preallocated extent A ---->|
1850 * |<- Prealloc File Extent ->|<- Regular Extent ->|
1851 * No csum Has csum
1852 *
1853 * For compressed extent, we should check the whole range.
1854 */
1855 if (!compressed) {
1856 search_start = disk_bytenr + extent_offset;
1857 search_len = extent_num_bytes;
1858 } else {
1859 search_start = disk_bytenr;
1860 search_len = disk_num_bytes;
1861 }
1862 ret = count_csum_range(root->fs_info, search_start, search_len,
1863 &csum_found);
1864 if (csum_found > 0 && nodatasum) {
1865 err |= ODD_CSUM_ITEM;
1866 error("root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum",
1867 root->objectid, fkey->objectid, fkey->offset);
1868 } else if (extent_type == BTRFS_FILE_EXTENT_REG && !nodatasum &&
1869 !is_hole && (ret < 0 || csum_found < search_len)) {
1870 err |= CSUM_ITEM_MISSING;
1871 error("root %llu EXTENT_DATA[%llu %llu] csum missing, have: %llu, expected: %llu",
1872 root->objectid, fkey->objectid, fkey->offset,
1873 csum_found, search_len);
1874 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
1875 csum_found > 0) {
1876 ret = check_prealloc_extent_written(root->fs_info,
1877 disk_bytenr, disk_num_bytes);
1878 if (ret < 0)
1879 return ret;
1880 if (ret == 0) {
1881 err |= ODD_CSUM_ITEM;
1882 error(
1883 "root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have csum, but has: %llu",
1884 root->objectid, fkey->objectid, fkey->offset,
1885 csum_found);
1886 }
1887 }
1888
1889 /* Check EXTENT_DATA hole */
1890 if (!no_holes && *end != fkey->offset) {
1891 if (repair)
1892 ret = punch_extent_hole(root, fkey->objectid,
1893 *end, fkey->offset - *end);
1894 if (!repair || ret) {
1895 err |= FILE_EXTENT_ERROR;
1896 error(
1897 "root %llu EXTENT_DATA[%llu %llu] gap exists, expected: EXTENT_DATA[%llu %llu]",
1898 root->objectid, fkey->objectid, fkey->offset,
1899 fkey->objectid, *end);
1900 }
1901 }
1902
1903 *end += extent_num_bytes;
1904 if (!is_hole)
1905 *size += extent_num_bytes;
1906
1907 return err;
1908 }
1909
1910 static int __count_dir_isize(struct btrfs_root *root, u64 ino, int type,
1911 u64 *size_ret)
1912 {
1913 struct btrfs_key key;
1914 struct btrfs_path path;
1915 u32 len;
1916 struct btrfs_dir_item *di;
1917 int ret;
1918 int cur = 0;
1919 int total = 0;
1920
1921 ASSERT(size_ret);
1922 *size_ret = 0;
1923
1924 key.objectid = ino;
1925 key.type = type;
1926 key.offset = (u64)-1;
1927
1928 btrfs_init_path(&path);
1929 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1930 if (ret < 0) {
1931 ret = -EIO;
1932 goto out;
1933 }
1934 /* if found, go to spacial case */
1935 if (ret == 0)
1936 goto special_case;
1937
1938 loop:
1939 ret = btrfs_previous_item(root, &path, ino, type);
1940
1941 if (ret) {
1942 ret = 0;
1943 goto out;
1944 }
1945
1946 special_case:
1947 di = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_dir_item);
1948 cur = 0;
1949 total = btrfs_item_size_nr(path.nodes[0], path.slots[0]);
1950
1951 while (cur < total) {
1952 len = btrfs_dir_name_len(path.nodes[0], di);
1953 if (len > BTRFS_NAME_LEN)
1954 len = BTRFS_NAME_LEN;
1955 *size_ret += len;
1956
1957 len += btrfs_dir_data_len(path.nodes[0], di);
1958 len += sizeof(*di);
1959 di = (struct btrfs_dir_item *)((char *)di + len);
1960 cur += len;
1961 }
1962 goto loop;
1963
1964 out:
1965 btrfs_release_path(&path);
1966 return ret;
1967 }
1968
1969 static int count_dir_isize(struct btrfs_root *root, u64 ino, u64 *size)
1970 {
1971 u64 item_size;
1972 u64 index_size;
1973 int ret;
1974
1975 ASSERT(size);
1976 ret = __count_dir_isize(root, ino, BTRFS_DIR_ITEM_KEY, &item_size);
1977 if (ret)
1978 goto out;
1979
1980 ret = __count_dir_isize(root, ino, BTRFS_DIR_INDEX_KEY, &index_size);
1981 if (ret)
1982 goto out;
1983
1984 *size = item_size + index_size;
1985
1986 out:
1987 if (ret)
1988 error("failed to count root %llu INODE[%llu] root size",
1989 root->objectid, ino);
1990 return ret;
1991 }
1992
1993 /*
1994 * Set inode item nbytes to @nbytes
1995 *
1996 * Returns 0 on success
1997 * Returns != 0 on error
1998 */
1999 static int repair_inode_nbytes_lowmem(struct btrfs_root *root,
2000 struct btrfs_path *path,
2001 u64 ino, u64 nbytes)
2002 {
2003 struct btrfs_trans_handle *trans;
2004 struct btrfs_inode_item *ii;
2005 struct btrfs_key key;
2006 struct btrfs_key research_key;
2007 int err = 0;
2008 int ret;
2009
2010 btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
2011
2012 key.objectid = ino;
2013 key.type = BTRFS_INODE_ITEM_KEY;
2014 key.offset = 0;
2015
2016 trans = btrfs_start_transaction(root, 1);
2017 if (IS_ERR(trans)) {
2018 ret = PTR_ERR(trans);
2019 err |= ret;
2020 goto out;
2021 }
2022
2023 btrfs_release_path(path);
2024 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2025 if (ret > 0)
2026 ret = -ENOENT;
2027 if (ret) {
2028 err |= ret;
2029 goto fail;
2030 }
2031
2032 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
2033 struct btrfs_inode_item);
2034 btrfs_set_inode_nbytes(path->nodes[0], ii, nbytes);
2035 btrfs_mark_buffer_dirty(path->nodes[0]);
2036 fail:
2037 btrfs_commit_transaction(trans, root);
2038 out:
2039 if (ret)
2040 error("failed to set nbytes in inode %llu root %llu",
2041 ino, root->root_key.objectid);
2042 else
2043 printf("Set nbytes in inode item %llu root %llu\n to %llu", ino,
2044 root->root_key.objectid, nbytes);
2045
2046 /* research path */
2047 btrfs_release_path(path);
2048 ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
2049 err |= ret;
2050
2051 return err;
2052 }
2053
2054 /*
2055 * Set directory inode isize to @isize.
2056 *
2057 * Returns 0 on success.
2058 * Returns != 0 on error.
2059 */
2060 static int repair_dir_isize_lowmem(struct btrfs_root *root,
2061 struct btrfs_path *path,
2062 u64 ino, u64 isize)
2063 {
2064 struct btrfs_trans_handle *trans;
2065 struct btrfs_inode_item *ii;
2066 struct btrfs_key key;
2067 struct btrfs_key research_key;
2068 int ret;
2069 int err = 0;
2070
2071 btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
2072
2073 key.objectid = ino;
2074 key.type = BTRFS_INODE_ITEM_KEY;
2075 key.offset = 0;
2076
2077 trans = btrfs_start_transaction(root, 1);
2078 if (IS_ERR(trans)) {
2079 ret = PTR_ERR(trans);
2080 err |= ret;
2081 goto out;
2082 }
2083
2084 btrfs_release_path(path);
2085 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2086 if (ret > 0)
2087 ret = -ENOENT;
2088 if (ret) {
2089 err |= ret;
2090 goto fail;
2091 }
2092
2093 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
2094 struct btrfs_inode_item);
2095 btrfs_set_inode_size(path->nodes[0], ii, isize);
2096 btrfs_mark_buffer_dirty(path->nodes[0]);
2097 fail:
2098 btrfs_commit_transaction(trans, root);
2099 out:
2100 if (ret)
2101 error("failed to set isize in inode %llu root %llu",
2102 ino, root->root_key.objectid);
2103 else
2104 printf("Set isize in inode %llu root %llu to %llu\n",
2105 ino, root->root_key.objectid, isize);
2106
2107 btrfs_release_path(path);
2108 ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
2109 err |= ret;
2110
2111 return err;
2112 }
2113
2114 /*
2115 * Wrapper function for btrfs_add_orphan_item().
2116 *
2117 * Returns 0 on success.
2118 * Returns != 0 on error.
2119 */
2120 static int repair_inode_orphan_item_lowmem(struct btrfs_root *root,
2121 struct btrfs_path *path, u64 ino)
2122 {
2123 struct btrfs_trans_handle *trans;
2124 struct btrfs_key research_key;
2125 int ret;
2126 int err = 0;
2127
2128 btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
2129
2130 trans = btrfs_start_transaction(root, 1);
2131 if (IS_ERR(trans)) {
2132 ret = PTR_ERR(trans);
2133 err |= ret;
2134 goto out;
2135 }
2136
2137 btrfs_release_path(path);
2138 ret = btrfs_add_orphan_item(trans, root, path, ino);
2139 err |= ret;
2140 btrfs_commit_transaction(trans, root);
2141 out:
2142 if (ret)
2143 error("failed to add inode %llu as orphan item root %llu",
2144 ino, root->root_key.objectid);
2145 else
2146 printf("Added inode %llu as orphan item root %llu\n",
2147 ino, root->root_key.objectid);
2148
2149 btrfs_release_path(path);
2150 ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
2151 err |= ret;
2152
2153 return err;
2154 }
2155
2156 /* Set inode_item nlink to @ref_count.
2157 * If @ref_count == 0, move it to "lost+found" and increase @ref_count.
2158 *
2159 * Returns 0 on success
2160 */
2161 static int repair_inode_nlinks_lowmem(struct btrfs_root *root,
2162 struct btrfs_path *path, u64 ino,
2163 const char *name, u32 namelen,
2164 u64 ref_count, u8 filetype, u64 *nlink)
2165 {
2166 struct btrfs_trans_handle *trans;
2167 struct btrfs_inode_item *ii;
2168 struct btrfs_key key;
2169 struct btrfs_key old_key;
2170 char namebuf[BTRFS_NAME_LEN] = {0};
2171 int name_len;
2172 int ret;
2173 int ret2;
2174
2175 /* save the key */
2176 btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]);
2177
2178 if (name && namelen) {
2179 ASSERT(namelen <= BTRFS_NAME_LEN);
2180 memcpy(namebuf, name, namelen);
2181 name_len = namelen;
2182 } else {
2183 sprintf(namebuf, "%llu", ino);
2184 name_len = count_digits(ino);
2185 printf("Can't find file name for inode %llu, use %s instead\n",
2186 ino, namebuf);
2187 }
2188
2189 trans = btrfs_start_transaction(root, 1);
2190 if (IS_ERR(trans)) {
2191 ret = PTR_ERR(trans);
2192 goto out;
2193 }
2194
2195 btrfs_release_path(path);
2196 /* if refs is 0, put it into lostfound */
2197 if (ref_count == 0) {
2198 ret = link_inode_to_lostfound(trans, root, path, ino, namebuf,
2199 name_len, filetype, &ref_count);
2200 if (ret)
2201 goto fail;
2202 }
2203
2204 /* reset inode_item's nlink to ref_count */
2205 key.objectid = ino;
2206 key.type = BTRFS_INODE_ITEM_KEY;
2207 key.offset = 0;
2208
2209 btrfs_release_path(path);
2210 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2211 if (ret > 0)
2212 ret = -ENOENT;
2213 if (ret)
2214 goto fail;
2215
2216 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
2217 struct btrfs_inode_item);
2218 btrfs_set_inode_nlink(path->nodes[0], ii, ref_count);
2219 btrfs_mark_buffer_dirty(path->nodes[0]);
2220
2221 if (nlink)
2222 *nlink = ref_count;
2223 fail:
2224 btrfs_commit_transaction(trans, root);
2225 out:
2226 if (ret)
2227 error(
2228 "fail to repair nlink of inode %llu root %llu name %s filetype %u",
2229 root->objectid, ino, namebuf, filetype);
2230 else
2231 printf("Fixed nlink of inode %llu root %llu name %s filetype %u\n",
2232 root->objectid, ino, namebuf, filetype);
2233
2234 /* research */
2235 btrfs_release_path(path);
2236 ret2 = btrfs_search_slot(NULL, root, &old_key, path, 0, 0);
2237 if (ret2 < 0)
2238 return ret |= ret2;
2239 return ret;
2240 }
2241
2242 static bool has_orphan_item(struct btrfs_root *root, u64 ino)
2243 {
2244 struct btrfs_path path;
2245 struct btrfs_key key;
2246 int ret;
2247
2248 btrfs_init_path(&path);
2249 key.objectid = BTRFS_ORPHAN_OBJECTID;
2250 key.type = BTRFS_ORPHAN_ITEM_KEY;
2251 key.offset = ino;
2252
2253 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
2254 btrfs_release_path(&path);
2255 if (ret == 0)
2256 return true;
2257 return false;
2258 }
2259
2260 /*
2261 * Check INODE_ITEM and related ITEMs (the same inode number)
2262 * 1. check link count
2263 * 2. check inode ref/extref
2264 * 3. check dir item/index
2265 *
2266 * Return 0 if no error occurred.
2267 * Return >0 for error or hit the traversal is done(by error bitmap)
2268 */
2269 static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path)
2270 {
2271 struct extent_buffer *node;
2272 struct btrfs_inode_item *ii;
2273 struct btrfs_key key;
2274 struct btrfs_key last_key;
2275 u64 inode_id;
2276 u32 mode;
2277 u64 nlink;
2278 u64 nbytes;
2279 u64 isize;
2280 u64 size = 0;
2281 u64 refs = 0;
2282 u64 extent_end = 0;
2283 u64 extent_size = 0;
2284 unsigned int dir;
2285 unsigned int nodatasum;
2286 bool is_orphan = false;
2287 int slot;
2288 int ret;
2289 int err = 0;
2290 char namebuf[BTRFS_NAME_LEN] = {0};
2291 u32 name_len = 0;
2292
2293 node = path->nodes[0];
2294 slot = path->slots[0];
2295
2296 btrfs_item_key_to_cpu(node, &key, slot);
2297 inode_id = key.objectid;
2298
2299 if (inode_id == BTRFS_ORPHAN_OBJECTID) {
2300 ret = btrfs_next_item(root, path);
2301 if (ret > 0)
2302 err |= LAST_ITEM;
2303 return err;
2304 }
2305
2306 ii = btrfs_item_ptr(node, slot, struct btrfs_inode_item);
2307 isize = btrfs_inode_size(node, ii);
2308 nbytes = btrfs_inode_nbytes(node, ii);
2309 mode = btrfs_inode_mode(node, ii);
2310 dir = imode_to_type(mode) == BTRFS_FT_DIR;
2311 nlink = btrfs_inode_nlink(node, ii);
2312 nodatasum = btrfs_inode_flags(node, ii) & BTRFS_INODE_NODATASUM;
2313
2314 while (1) {
2315 btrfs_item_key_to_cpu(path->nodes[0], &last_key, path->slots[0]);
2316 ret = btrfs_next_item(root, path);
2317 if (ret < 0) {
2318 /* out will fill 'err' rusing current statistics */
2319 goto out;
2320 } else if (ret > 0) {
2321 err |= LAST_ITEM;
2322 goto out;
2323 }
2324
2325 node = path->nodes[0];
2326 slot = path->slots[0];
2327 btrfs_item_key_to_cpu(node, &key, slot);
2328 if (key.objectid != inode_id)
2329 goto out;
2330
2331 switch (key.type) {
2332 case BTRFS_INODE_REF_KEY:
2333 ret = check_inode_ref(root, &key, path, namebuf,
2334 &name_len, &refs, mode);
2335 err |= ret;
2336 break;
2337 case BTRFS_INODE_EXTREF_KEY:
2338 {
2339 bool ext_ref = btrfs_fs_incompat(root->fs_info,
2340 EXTENDED_IREF);
2341 if (key.type == BTRFS_INODE_EXTREF_KEY && !ext_ref)
2342 warning("root %llu EXTREF[%llu %llu] isn't supported",
2343 root->objectid, key.objectid,
2344 key.offset);
2345 ret = check_inode_extref(root, &key, node, slot, &refs,
2346 mode);
2347 err |= ret;
2348 break;
2349 }
2350 case BTRFS_DIR_ITEM_KEY:
2351 case BTRFS_DIR_INDEX_KEY:
2352 if (!dir) {
2353 warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]",
2354 root->objectid, inode_id,
2355 imode_to_type(mode), key.objectid,
2356 key.offset);
2357 }
2358 ret = check_dir_item(root, &key, path, &size);
2359 err |= ret;
2360 break;
2361 case BTRFS_EXTENT_DATA_KEY:
2362 if (dir) {
2363 warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]",
2364 root->objectid, inode_id, key.objectid,
2365 key.offset);
2366 }
2367 ret = check_file_extent(root, &key, node, slot,
2368 nodatasum, &extent_size,
2369 &extent_end);
2370 err |= ret;
2371 break;
2372 case BTRFS_XATTR_ITEM_KEY:
2373 break;
2374 default:
2375 error("ITEM[%llu %u %llu] UNKNOWN TYPE",
2376 key.objectid, key.type, key.offset);
2377 }
2378 }
2379
2380 out:
2381 if (err & LAST_ITEM) {
2382 btrfs_release_path(path);
2383 ret = btrfs_search_slot(NULL, root, &last_key, path, 0, 0);
2384 if (ret)
2385 return err;
2386 }
2387
2388 /* verify INODE_ITEM nlink/isize/nbytes */
2389 if (dir) {
2390 if (repair && (err & DIR_COUNT_AGAIN)) {
2391 err &= ~DIR_COUNT_AGAIN;
2392 count_dir_isize(root, inode_id, &size);
2393 }
2394
2395 if ((nlink != 1 || refs != 1) && repair) {
2396 ret = repair_inode_nlinks_lowmem(root, path, inode_id,
2397 namebuf, name_len, refs, imode_to_type(mode),
2398 &nlink);
2399 }
2400
2401 if (nlink != 1) {
2402 err |= LINK_COUNT_ERROR;
2403 error("root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)",
2404 root->objectid, inode_id, nlink);
2405 }
2406
2407 /*
2408 * Just a warning, as dir inode nbytes is just an
2409 * instructive value.
2410 */
2411 if (!IS_ALIGNED(nbytes, root->fs_info->nodesize)) {
2412 warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u",
2413 root->objectid, inode_id,
2414 root->fs_info->nodesize);
2415 }
2416
2417 if (isize != size) {
2418 if (repair)
2419 ret = repair_dir_isize_lowmem(root, path,
2420 inode_id, size);
2421 if (!repair || ret) {
2422 err |= ISIZE_ERROR;
2423 error(
2424 "root %llu DIR INODE [%llu] size %llu not equal to %llu",
2425 root->objectid, inode_id, isize, size);
2426 }
2427 }
2428 } else {
2429 if (nlink != refs) {
2430 if (repair)
2431 ret = repair_inode_nlinks_lowmem(root, path,
2432 inode_id, namebuf, name_len, refs,
2433 imode_to_type(mode), &nlink);
2434 if (!repair || ret) {
2435 err |= LINK_COUNT_ERROR;
2436 error(
2437 "root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)",
2438 root->objectid, inode_id, nlink, refs);
2439 }
2440 } else if (!nlink) {
2441 is_orphan = has_orphan_item(root, inode_id);
2442 if (!is_orphan && repair)
2443 ret = repair_inode_orphan_item_lowmem(root,
2444 path, inode_id);
2445 if (!is_orphan && (!repair || ret)) {
2446 err |= ORPHAN_ITEM;
2447 error("root %llu INODE[%llu] is orphan item",
2448 root->objectid, inode_id);
2449 }
2450 }
2451
2452 if (!nbytes && !no_holes && extent_end < isize) {
2453 if (repair)
2454 ret = punch_extent_hole(root, inode_id,
2455 extent_end, isize - extent_end);
2456 if (!repair || ret) {
2457 err |= NBYTES_ERROR;
2458 error(
2459 "root %llu INODE[%llu] size %llu should have a file extent hole",
2460 root->objectid, inode_id, isize);
2461 }
2462 }
2463
2464 if (nbytes != extent_size) {
2465 if (repair)
2466 ret = repair_inode_nbytes_lowmem(root, path,
2467 inode_id, extent_size);
2468 if (!repair || ret) {
2469 err |= NBYTES_ERROR;
2470 error(
2471 "root %llu INODE[%llu] nbytes %llu not equal to extent_size %llu",
2472 root->objectid, inode_id, nbytes,
2473 extent_size);
2474 }
2475 }
2476 }
2477
2478 if (err & LAST_ITEM)
2479 btrfs_next_item(root, path);
2480 return err;
2481 }
2482
2483 /*
2484 * Returns >0 Found error, not fatal, should continue
2485 * Returns <0 Fatal error, must exit the whole check
2486 * Returns 0 No errors found
2487 */
2488 static int process_one_leaf(struct btrfs_root *root, struct btrfs_path *path,
2489 struct node_refs *nrefs, int *level)
2490 {
2491 struct extent_buffer *cur = path->nodes[0];
2492 struct btrfs_key key;
2493 u64 cur_bytenr;
2494 u32 nritems;
2495 u64 first_ino = 0;
2496 int root_level = btrfs_header_level(root->node);
2497 int i;
2498 int ret = 0; /* Final return value */
2499 int err = 0; /* Positive error bitmap */
2500
2501 cur_bytenr = cur->start;
2502
2503 /* skip to first inode item or the first inode number change */
2504 nritems = btrfs_header_nritems(cur);
2505 for (i = 0; i < nritems; i++) {
2506 btrfs_item_key_to_cpu(cur, &key, i);
2507 if (i == 0)
2508 first_ino = key.objectid;
2509 if (key.type == BTRFS_INODE_ITEM_KEY ||
2510 (first_ino && first_ino != key.objectid))
2511 break;
2512 }
2513 if (i == nritems) {
2514 path->slots[0] = nritems;
2515 return 0;
2516 }
2517 path->slots[0] = i;
2518
2519 again:
2520 err |= check_inode_item(root, path);
2521
2522 /* modify cur since check_inode_item may change path */
2523 cur = path->nodes[0];
2524
2525 if (err & LAST_ITEM)
2526 goto out;
2527
2528 /* still have inode items in thie leaf */
2529 if (cur->start == cur_bytenr)
2530 goto again;
2531
2532 /*
2533 * we have switched to another leaf, above nodes may
2534 * have changed, here walk down the path, if a node
2535 * or leaf is shared, check whether we can skip this
2536 * node or leaf.
2537 */
2538 for (i = root_level; i >= 0; i--) {
2539 if (path->nodes[i]->start == nrefs->bytenr[i])
2540 continue;
2541
2542 ret = update_nodes_refs(root, path->nodes[i]->start,
2543 path->nodes[i], nrefs, i, 0);
2544 if (ret)
2545 goto out;
2546
2547 if (!nrefs->need_check[i]) {
2548 *level += 1;
2549 break;
2550 }
2551 }
2552
2553 for (i = 0; i < *level; i++) {
2554 free_extent_buffer(path->nodes[i]);
2555 path->nodes[i] = NULL;
2556 }
2557 out:
2558 err &= ~LAST_ITEM;
2559 if (err && !ret)
2560 ret = err;
2561 return ret;
2562 }
2563
2564 /*
2565 * @level if @level == -1 means extent data item
2566 * else normal treeblocl.
2567 */
2568 static int should_check_extent_strictly(struct btrfs_root *root,
2569 struct node_refs *nrefs, int level)
2570 {
2571 int root_level = btrfs_header_level(root->node);
2572
2573 if (level > root_level || level < -1)
2574 return 1;
2575 if (level == root_level)
2576 return 1;
2577 /*
2578 * if the upper node is marked full backref, it should contain shared
2579 * backref of the parent (except owner == root->objectid).
2580 */
2581 while (++level <= root_level)
2582 if (nrefs->refs[level] > 1)
2583 return 0;
2584
2585 return 1;
2586 }
2587
2588 static int check_extent_inline_ref(struct extent_buffer *eb,
2589 struct btrfs_key *key, struct btrfs_extent_inline_ref *iref)
2590 {
2591 int ret;
2592 u8 type = btrfs_extent_inline_ref_type(eb, iref);
2593
2594 switch (type) {
2595 case BTRFS_TREE_BLOCK_REF_KEY:
2596 case BTRFS_EXTENT_DATA_REF_KEY:
2597 case BTRFS_SHARED_BLOCK_REF_KEY:
2598 case BTRFS_SHARED_DATA_REF_KEY:
2599 ret = 0;
2600 break;
2601 default:
2602 error("extent[%llu %u %llu] has unknown ref type: %d",
2603 key->objectid, key->type, key->offset, type);
2604 ret = UNKNOWN_TYPE;
2605 break;
2606 }
2607
2608 return ret;
2609 }
2610
2611 /*
2612 * Check backrefs of a tree block given by @bytenr or @eb.
2613 *
2614 * @root: the root containing the @bytenr or @eb
2615 * @eb: tree block extent buffer, can be NULL
2616 * @bytenr: bytenr of the tree block to search
2617 * @level: tree level of the tree block
2618 * @owner: owner of the tree block
2619 *
2620 * Return >0 for any error found and output error message
2621 * Return 0 for no error found
2622 */
2623 static int check_tree_block_ref(struct btrfs_root *root,
2624 struct extent_buffer *eb, u64 bytenr,
2625 int level, u64 owner, struct node_refs *nrefs)
2626 {
2627 struct btrfs_key key;
2628 struct btrfs_root *extent_root = root->fs_info->extent_root;
2629 struct btrfs_path path;
2630 struct btrfs_extent_item *ei;
2631 struct btrfs_extent_inline_ref *iref;
2632 struct extent_buffer *leaf;
2633 unsigned long end;
2634 unsigned long ptr;
2635 int slot;
2636 int skinny_level;
2637 int root_level = btrfs_header_level(root->node);
2638 int type;
2639 u32 nodesize = root->fs_info->nodesize;
2640 u32 item_size;
2641 u64 offset;
2642 int found_ref = 0;
2643 int err = 0;
2644 int ret;
2645 int strict = 1;
2646 int parent = 0;
2647
2648 btrfs_init_path(&path);
2649 key.objectid = bytenr;
2650 if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA))
2651 key.type = BTRFS_METADATA_ITEM_KEY;
2652 else
2653 key.type = BTRFS_EXTENT_ITEM_KEY;
2654 key.offset = (u64)-1;
2655
2656 /* Search for the backref in extent tree */
2657 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2658 if (ret < 0) {
2659 err |= BACKREF_MISSING;
2660 goto out;
2661 }
2662 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
2663 if (ret) {
2664 err |= BACKREF_MISSING;
2665 goto out;
2666 }
2667
2668 leaf = path.nodes[0];
2669 slot = path.slots[0];
2670 btrfs_item_key_to_cpu(leaf, &key, slot);
2671
2672 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
2673
2674 if (key.type == BTRFS_METADATA_ITEM_KEY) {
2675 skinny_level = (int)key.offset;
2676 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2677 } else {
2678 struct btrfs_tree_block_info *info;
2679
2680 info = (struct btrfs_tree_block_info *)(ei + 1);
2681 skinny_level = btrfs_tree_block_level(leaf, info);
2682 iref = (struct btrfs_extent_inline_ref *)(info + 1);
2683 }
2684
2685
2686 if (eb) {
2687 u64 header_gen;
2688 u64 extent_gen;
2689
2690 /*
2691 * Due to the feature of shared tree blocks, if the upper node
2692 * is a fs root or shared node, the extent of checked node may
2693 * not be updated until the next CoW.
2694 */
2695 if (nrefs)
2696 strict = should_check_extent_strictly(root, nrefs,
2697 level);
2698 if (!(btrfs_extent_flags(leaf, ei) &
2699 BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
2700 error(
2701 "extent[%llu %u] backref type mismatch, missing bit: %llx",
2702 key.objectid, nodesize,
2703 BTRFS_EXTENT_FLAG_TREE_BLOCK);
2704 err = BACKREF_MISMATCH;
2705 }
2706 header_gen = btrfs_header_generation(eb);
2707 extent_gen = btrfs_extent_generation(leaf, ei);
2708 if (header_gen != extent_gen) {
2709 error(
2710 "extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu",
2711 key.objectid, nodesize, header_gen,
2712 extent_gen);
2713 err = BACKREF_MISMATCH;
2714 }
2715 if (level != skinny_level) {
2716 error(
2717 "extent[%llu %u] level mismatch, wanted: %u, have: %u",
2718 key.objectid, nodesize, level, skinny_level);
2719 err = BACKREF_MISMATCH;
2720 }
2721 if (!is_fstree(owner) && btrfs_extent_refs(leaf, ei) != 1) {
2722 error(
2723 "extent[%llu %u] is referred by other roots than %llu",
2724 key.objectid, nodesize, root->objectid);
2725 err = BACKREF_MISMATCH;
2726 }
2727 }
2728
2729 /*
2730 * Iterate the extent/metadata item to find the exact backref
2731 */
2732 item_size = btrfs_item_size_nr(leaf, slot);
2733 ptr = (unsigned long)iref;
2734 end = (unsigned long)ei + item_size;
2735
2736 while (ptr < end) {
2737 iref = (struct btrfs_extent_inline_ref *)ptr;
2738 type = btrfs_extent_inline_ref_type(leaf, iref);
2739 offset = btrfs_extent_inline_ref_offset(leaf, iref);
2740
2741 ret = check_extent_inline_ref(leaf, &key, iref);
2742 if (ret) {
2743 err |= ret;
2744 break;
2745 }
2746 if (type == BTRFS_TREE_BLOCK_REF_KEY) {
2747 if (offset == root->objectid)
2748 found_ref = 1;
2749 if (!strict && owner == offset)
2750 found_ref = 1;
2751 } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
2752 /*
2753 * Backref of tree reloc root points to itself, no need
2754 * to check backref any more.
2755 *
2756 * This may be an error of loop backref, but extent tree
2757 * checker should have already handled it.
2758 * Here we only need to avoid infinite iteration.
2759 */
2760 if (offset == bytenr) {
2761 found_ref = 1;
2762 } else {
2763 /*
2764 * Check if the backref points to valid
2765 * referencer
2766 */
2767 found_ref = !check_tree_block_ref(root, NULL,
2768 offset, level + 1, owner, NULL);
2769 }
2770 }
2771
2772 if (found_ref)
2773 break;
2774 ptr += btrfs_extent_inline_ref_size(type);
2775 }
2776
2777 /*
2778 * Inlined extent item doesn't have what we need, check
2779 * TREE_BLOCK_REF_KEY
2780 */
2781 if (!found_ref) {
2782 btrfs_release_path(&path);
2783 key.objectid = bytenr;
2784 key.type = BTRFS_TREE_BLOCK_REF_KEY;
2785 key.offset = root->objectid;
2786
2787 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2788 if (!ret)
2789 found_ref = 1;
2790 }
2791 /*
2792 * Finally check SHARED BLOCK REF, any found will be good
2793 * Here we're not doing comprehensive extent backref checking,
2794 * only need to ensure there is some extent referring to this
2795 * tree block.
2796 */
2797 if (!found_ref) {
2798 btrfs_release_path(&path);
2799 key.objectid = bytenr;
2800 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
2801 key.offset = (u64)-1;
2802
2803 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2804 if (ret < 0) {
2805 err |= BACKREF_MISSING;
2806 goto out;
2807 }
2808 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
2809 if (ret) {
2810 err |= BACKREF_MISSING;
2811 goto out;
2812 }
2813 found_ref = 1;
2814 }
2815 if (!found_ref)
2816 err |= BACKREF_MISSING;
2817 out:
2818 btrfs_release_path(&path);
2819 if (nrefs && strict &&
2820 level < root_level && nrefs->full_backref[level + 1])
2821 parent = nrefs->bytenr[level + 1];
2822 if (eb && (err & BACKREF_MISSING))
2823 error(
2824 "extent[%llu %u] backref lost (owner: %llu, level: %u) %s %llu",
2825 bytenr, nodesize, owner, level,
2826 parent ? "parent" : "root",
2827 parent ? parent : root->objectid);
2828 return err;
2829 }
2830
2831 /*
2832 * If @err contains BACKREF_MISSING then add extent of the
2833 * file_extent_data_item.
2834 *
2835 * Returns error bits after reapir.
2836 */
2837 static int repair_extent_data_item(struct btrfs_root *root,
2838 struct btrfs_path *pathp,
2839 struct node_refs *nrefs,
2840 int err)
2841 {
2842 struct btrfs_trans_handle *trans = NULL;
2843 struct btrfs_file_extent_item *fi;
2844 struct btrfs_key fi_key;
2845 struct btrfs_key key;
2846 struct btrfs_extent_item *ei;
2847 struct btrfs_path path;
2848 struct btrfs_root *extent_root = root->fs_info->extent_root;
2849 struct extent_buffer *eb;
2850 u64 size;
2851 u64 disk_bytenr;
2852 u64 num_bytes;
2853 u64 parent;
2854 u64 offset;
2855 u64 extent_offset;
2856 u64 file_offset;
2857 int generation;
2858 int slot;
2859 int need_insert = 0;
2860 int ret = 0;
2861
2862 eb = pathp->nodes[0];
2863 slot = pathp->slots[0];
2864 btrfs_item_key_to_cpu(eb, &fi_key, slot);
2865 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
2866
2867 if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
2868 btrfs_file_extent_disk_bytenr(eb, fi) == 0)
2869 return err;
2870
2871 file_offset = fi_key.offset;
2872 generation = btrfs_file_extent_generation(eb, fi);
2873 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
2874 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
2875 extent_offset = btrfs_file_extent_offset(eb, fi);
2876 offset = file_offset - extent_offset;
2877
2878 if (nrefs->full_backref[0])
2879 parent = btrfs_header_bytenr(eb);
2880 else
2881 parent = 0;
2882
2883 /* now repair only adds backref */
2884 if ((err & BACKREF_MISSING) == 0)
2885 return err;
2886
2887 /* search extent item */
2888 key.objectid = disk_bytenr;
2889 key.type = BTRFS_EXTENT_ITEM_KEY;
2890 key.offset = num_bytes;
2891
2892 btrfs_init_path(&path);
2893 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2894 if (ret < 0) {
2895 ret = -EIO;
2896 goto out;
2897 }
2898 need_insert = ret;
2899
2900 ret = avoid_extents_overwrite(root->fs_info);
2901 if (ret)
2902 goto out;
2903 trans = btrfs_start_transaction(root, 1);
2904 if (IS_ERR(trans)) {
2905 ret = PTR_ERR(trans);
2906 trans = NULL;
2907 error("fail to start transaction %s", strerror(-ret));
2908 goto out;
2909 }
2910 /* insert an extent item */
2911 if (need_insert) {
2912 key.objectid = disk_bytenr;
2913 key.type = BTRFS_EXTENT_ITEM_KEY;
2914 key.offset = num_bytes;
2915 size = sizeof(*ei);
2916
2917 btrfs_release_path(&path);
2918 ret = btrfs_insert_empty_item(trans, extent_root, &path, &key,
2919 size);
2920 if (ret)
2921 goto out;
2922 eb = path.nodes[0];
2923 ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item);
2924
2925 btrfs_set_extent_refs(eb, ei, 0);
2926 btrfs_set_extent_generation(eb, ei, generation);
2927 btrfs_set_extent_flags(eb, ei, BTRFS_EXTENT_FLAG_DATA);
2928
2929 btrfs_mark_buffer_dirty(eb);
2930 ret = btrfs_update_block_group(extent_root, disk_bytenr,
2931 num_bytes, 1, 0);
2932 btrfs_release_path(&path);
2933 }
2934
2935 ret = btrfs_inc_extent_ref(trans, root, disk_bytenr, num_bytes, parent,
2936 root->objectid,
2937 parent ? BTRFS_FIRST_FREE_OBJECTID : fi_key.objectid,
2938 offset);
2939 if (ret) {
2940 error(
2941 "failed to increase extent data backref[%llu %llu] root %llu",
2942 disk_bytenr, num_bytes, root->objectid);
2943 goto out;
2944 } else {
2945 printf("Add one extent data backref [%llu %llu]\n",
2946 disk_bytenr, num_bytes);
2947 }
2948
2949 err &= ~BACKREF_MISSING;
2950 out:
2951 if (trans)
2952 btrfs_commit_transaction(trans, root);
2953 btrfs_release_path(&path);
2954 if (ret)
2955 error("can't repair root %llu extent data item[%llu %llu]",
2956 root->objectid, disk_bytenr, num_bytes);
2957 return err;
2958 }
2959
2960 /*
2961 * Check EXTENT_DATA item, mainly for its dbackref in extent tree
2962 *
2963 * Return >0 any error found and output error message
2964 * Return 0 for no error found
2965 */
2966 static int check_extent_data_item(struct btrfs_root *root,
2967 struct btrfs_path *pathp,
2968 struct node_refs *nrefs, int account_bytes)
2969 {
2970 struct btrfs_file_extent_item *fi;
2971 struct extent_buffer *eb = pathp->nodes[0];
2972 struct btrfs_path path;
2973 struct btrfs_root *extent_root = root->fs_info->extent_root;
2974 struct btrfs_key fi_key;
2975 struct btrfs_key dbref_key;
2976 struct extent_buffer *leaf;
2977 struct btrfs_extent_item *ei;
2978 struct btrfs_extent_inline_ref *iref;
2979 struct btrfs_extent_data_ref *dref;
2980 u64 owner;
2981 u64 disk_bytenr;
2982 u64 disk_num_bytes;
2983 u64 extent_num_bytes;
2984 u64 extent_flags;
2985 u64 offset;
2986 u32 item_size;
2987 unsigned long end;
2988 unsigned long ptr;
2989 int type;
2990 int found_dbackref = 0;
2991 int slot = pathp->slots[0];
2992 int err = 0;
2993 int ret;
2994 int strict;
2995
2996 btrfs_item_key_to_cpu(eb, &fi_key, slot);
2997 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
2998
2999 /* Nothing to check for hole and inline data extents */
3000 if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
3001 btrfs_file_extent_disk_bytenr(eb, fi) == 0)
3002 return 0;
3003
3004 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
3005 disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
3006 extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
3007 offset = btrfs_file_extent_offset(eb, fi);
3008
3009 /* Check unaligned disk_num_bytes and num_bytes */
3010 if (!IS_ALIGNED(disk_num_bytes, root->fs_info->sectorsize)) {
3011 error(
3012 "file extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
3013 fi_key.objectid, fi_key.offset, disk_num_bytes,
3014 root->fs_info->sectorsize);
3015 err |= BYTES_UNALIGNED;
3016 } else if (account_bytes) {
3017 data_bytes_allocated += disk_num_bytes;
3018 }
3019 if (!IS_ALIGNED(extent_num_bytes, root->fs_info->sectorsize)) {
3020 error(
3021 "file extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u",
3022 fi_key.objectid, fi_key.offset, extent_num_bytes,
3023 root->fs_info->sectorsize);
3024 err |= BYTES_UNALIGNED;
3025 } else if (account_bytes) {
3026 data_bytes_referenced += extent_num_bytes;
3027 }
3028 owner = btrfs_header_owner(eb);
3029
3030 /* Check the extent item of the file extent in extent tree */
3031 btrfs_init_path(&path);
3032 dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
3033 dbref_key.type = BTRFS_EXTENT_ITEM_KEY;
3034 dbref_key.offset = btrfs_file_extent_disk_num_bytes(eb, fi);
3035
3036 ret = btrfs_search_slot(NULL, extent_root, &dbref_key, &path, 0, 0);
3037 if (ret)
3038 goto out;
3039
3040 leaf = path.nodes[0];
3041 slot = path.slots[0];
3042 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
3043
3044 extent_flags = btrfs_extent_flags(leaf, ei);
3045
3046 if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) {
3047 error(
3048 "file extent[%llu %llu] root %llu owner %llu backref type mismatch, wanted bit: %llx",
3049 fi_key.objectid, fi_key.offset, root->objectid, owner,
3050 BTRFS_EXTENT_FLAG_DATA);
3051 err |= BACKREF_MISMATCH;
3052 }
3053
3054 /* Check data backref inside that extent item */
3055 item_size = btrfs_item_size_nr(leaf, path.slots[0]);
3056 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
3057 ptr = (unsigned long)iref;
3058 end = (unsigned long)ei + item_size;
3059 strict = should_check_extent_strictly(root, nrefs, -1);
3060
3061 while (ptr < end) {
3062 u64 ref_root;
3063 u64 ref_objectid;
3064 u64 ref_offset;
3065 bool match = false;
3066
3067 iref = (struct btrfs_extent_inline_ref *)ptr;
3068 type = btrfs_extent_inline_ref_type(leaf, iref);
3069 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
3070
3071 ret = check_extent_inline_ref(leaf, &dbref_key, iref);
3072 if (ret) {
3073 err |= ret;
3074 break;
3075 }
3076 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
3077 ref_root = btrfs_extent_data_ref_root(leaf, dref);
3078 ref_objectid = btrfs_extent_data_ref_objectid(leaf,
3079 dref);
3080 ref_offset = btrfs_extent_data_ref_offset(leaf, dref);
3081
3082 if (ref_objectid == fi_key.objectid &&
3083 ref_offset == fi_key.offset - offset)
3084 match = true;
3085 if (ref_root == root->objectid && match)
3086 found_dbackref = 1;
3087 else if (!strict && owner == ref_root && match)
3088 found_dbackref = 1;
3089 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
3090 found_dbackref = !check_tree_block_ref(root, NULL,
3091 btrfs_extent_inline_ref_offset(leaf, iref),
3092 0, owner, NULL);
3093 }
3094
3095 if (found_dbackref)
3096 break;
3097 ptr += btrfs_extent_inline_ref_size(type);
3098 }
3099
3100 if (!found_dbackref) {
3101 btrfs_release_path(&path);
3102
3103 /* Didn't find inlined data backref, try EXTENT_DATA_REF_KEY */
3104 dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
3105 dbref_key.type = BTRFS_EXTENT_DATA_REF_KEY;
3106 dbref_key.offset = hash_extent_data_ref(owner, fi_key.objectid,
3107 fi_key.offset - offset);
3108
3109 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
3110 &dbref_key, &path, 0, 0);
3111 if (!ret) {
3112 found_dbackref = 1;
3113 goto out;
3114 }
3115
3116 btrfs_release_path(&path);
3117
3118 /*
3119 * Neither inlined nor EXTENT_DATA_REF found, try
3120 * SHARED_DATA_REF as last chance.
3121 */
3122 dbref_key.objectid = disk_bytenr;
3123 dbref_key.type = BTRFS_SHARED_DATA_REF_KEY;
3124 dbref_key.offset = eb->start;
3125
3126 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
3127 &dbref_key, &path, 0, 0);
3128 if (!ret) {
3129 found_dbackref = 1;
3130 goto out;
3131 }
3132 }
3133
3134 out:
3135 if (!found_dbackref)
3136 err |= BACKREF_MISSING;
3137 btrfs_release_path(&path);
3138 if (err & BACKREF_MISSING) {
3139 error(
3140 "file extent[%llu %llu] root %llu owner %llu backref lost",
3141 fi_key.objectid, fi_key.offset, root->objectid, owner);
3142 }
3143 return err;
3144 }
3145
3146 /*
3147 * Check a block group item with its referener (chunk) and its used space
3148 * with extent/metadata item
3149 */
3150 static int check_block_group_item(struct btrfs_fs_info *fs_info,
3151 struct extent_buffer *eb, int slot)
3152 {
3153 struct btrfs_root *extent_root = fs_info->extent_root;
3154 struct btrfs_root *chunk_root = fs_info->chunk_root;
3155 struct btrfs_block_group_item *bi;
3156 struct btrfs_block_group_item bg_item;
3157 struct btrfs_path path;
3158 struct btrfs_key bg_key;
3159 struct btrfs_key chunk_key;
3160 struct btrfs_key extent_key;
3161 struct btrfs_chunk *chunk;
3162 struct extent_buffer *leaf;
3163 struct btrfs_extent_item *ei;
3164 u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
3165 u64 flags;
3166 u64 bg_flags;
3167 u64 used;
3168 u64 total = 0;
3169 int ret;
3170 int err = 0;
3171
3172 btrfs_item_key_to_cpu(eb, &bg_key, slot);
3173 bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
3174 read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item));
3175 used = btrfs_block_group_used(&bg_item);
3176 bg_flags = btrfs_block_group_flags(&bg_item);
3177
3178 chunk_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3179 chunk_key.type = BTRFS_CHUNK_ITEM_KEY;
3180 chunk_key.offset = bg_key.objectid;
3181
3182 btrfs_init_path(&path);
3183 /* Search for the referencer chunk */
3184 ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0);
3185 if (ret) {
3186 error(
3187 "block group[%llu %llu] did not find the related chunk item",
3188 bg_key.objectid, bg_key.offset);
3189 err |= REFERENCER_MISSING;
3190 } else {
3191 chunk = btrfs_item_ptr(path.nodes[0], path.slots[0],
3192 struct btrfs_chunk);
3193 if (btrfs_chunk_length(path.nodes[0], chunk) !=
3194 bg_key.offset) {
3195 error(
3196 "block group[%llu %llu] related chunk item length does not match",
3197 bg_key.objectid, bg_key.offset);
3198 err |= REFERENCER_MISMATCH;
3199 }
3200 }
3201 btrfs_release_path(&path);
3202
3203 /* Search from the block group bytenr */
3204 extent_key.objectid = bg_key.objectid;
3205 extent_key.type = 0;
3206 extent_key.offset = 0;
3207
3208 btrfs_init_path(&path);
3209 ret = btrfs_search_slot(NULL, extent_root, &extent_key, &path, 0, 0);
3210 if (ret < 0)
3211 goto out;
3212
3213 /* Iterate extent tree to account used space */
3214 while (1) {
3215 leaf = path.nodes[0];
3216
3217 /* Search slot can point to the last item beyond leaf nritems */
3218 if (path.slots[0] >= btrfs_header_nritems(leaf))
3219 goto next;
3220
3221 btrfs_item_key_to_cpu(leaf, &extent_key, path.slots[0]);
3222 if (extent_key.objectid >= bg_key.objectid + bg_key.offset)
3223 break;
3224
3225 if (extent_key.type != BTRFS_METADATA_ITEM_KEY &&
3226 extent_key.type != BTRFS_EXTENT_ITEM_KEY)
3227 goto next;
3228 if (extent_key.objectid < bg_key.objectid)
3229 goto next;
3230
3231 if (extent_key.type == BTRFS_METADATA_ITEM_KEY)
3232 total += nodesize;
3233 else
3234 total += extent_key.offset;
3235
3236 ei = btrfs_item_ptr(leaf, path.slots[0],
3237 struct btrfs_extent_item);
3238 flags = btrfs_extent_flags(leaf, ei);
3239 if (flags & BTRFS_EXTENT_FLAG_DATA) {
3240 if (!(bg_flags & BTRFS_BLOCK_GROUP_DATA)) {
3241 error(
3242 "bad extent[%llu, %llu) type mismatch with chunk",
3243 extent_key.objectid,
3244 extent_key.objectid + extent_key.offset);
3245 err |= CHUNK_TYPE_MISMATCH;
3246 }
3247 } else if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
3248 if (!(bg_flags & (BTRFS_BLOCK_GROUP_SYSTEM |
3249 BTRFS_BLOCK_GROUP_METADATA))) {
3250 error(
3251 "bad extent[%llu, %llu) type mismatch with chunk",
3252 extent_key.objectid,
3253 extent_key.objectid + nodesize);
3254 err |= CHUNK_TYPE_MISMATCH;
3255 }
3256 }
3257 next:
3258 ret = btrfs_next_item(extent_root, &path);
3259 if (ret)
3260 break;
3261 }
3262
3263 out:
3264 btrfs_release_path(&path);
3265
3266 if (total != used) {
3267 error(
3268 "block group[%llu %llu] used %llu but extent items used %llu",
3269 bg_key.objectid, bg_key.offset, used, total);
3270 err |= BG_ACCOUNTING_ERROR;
3271 }
3272 return err;
3273 }
3274
3275 /*
3276 * Get real tree block level for the case like shared block
3277 * Return >= 0 as tree level
3278 * Return <0 for error
3279 */
3280 static int query_tree_block_level(struct btrfs_fs_info *fs_info, u64 bytenr)
3281 {
3282 struct extent_buffer *eb;
3283 struct btrfs_path path;
3284 struct btrfs_key key;
3285 struct btrfs_extent_item *ei;
3286 u64 flags;
3287 u64 transid;
3288 u8 backref_level;
3289 u8 header_level;
3290 int ret;
3291
3292 /* Search extent tree for extent generation and level */
3293 key.objectid = bytenr;
3294 key.type = BTRFS_METADATA_ITEM_KEY;
3295 key.offset = (u64)-1;
3296
3297 btrfs_init_path(&path);
3298 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, &path, 0, 0);
3299 if (ret < 0)
3300 goto release_out;
3301 ret = btrfs_previous_extent_item(fs_info->extent_root, &path, bytenr);
3302 if (ret < 0)
3303 goto release_out;
3304 if (ret > 0) {
3305 ret = -ENOENT;
3306 goto release_out;
3307 }
3308
3309 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
3310 ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
3311 struct btrfs_extent_item);
3312 flags = btrfs_extent_flags(path.nodes[0], ei);
3313 if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
3314 ret = -ENOENT;
3315 goto release_out;
3316 }
3317
3318 /* Get transid for later read_tree_block() check */
3319 transid = btrfs_extent_generation(path.nodes[0], ei);
3320
3321 /* Get backref level as one source */
3322 if (key.type == BTRFS_METADATA_ITEM_KEY) {
3323 backref_level = key.offset;
3324 } else {
3325 struct btrfs_tree_block_info *info;
3326
3327 info = (struct btrfs_tree_block_info *)(ei + 1);
3328 backref_level = btrfs_tree_block_level(path.nodes[0], info);
3329 }
3330 btrfs_release_path(&path);
3331
3332 /* Get level from tree block as an alternative source */
3333 eb = read_tree_block(fs_info, bytenr, transid);
3334 if (!extent_buffer_uptodate(eb)) {
3335 free_extent_buffer(eb);
3336 return -EIO;
3337 }
3338 header_level = btrfs_header_level(eb);
3339 free_extent_buffer(eb);
3340
3341 if (header_level != backref_level)
3342 return -EIO;
3343 return header_level;
3344
3345 release_out:
3346 btrfs_release_path(&path);
3347 return ret;
3348 }
3349
3350 /*
3351 * Check if a tree block backref is valid (points to a valid tree block)
3352 * if level == -1, level will be resolved
3353 * Return >0 for any error found and print error message
3354 */
3355 static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id,
3356 u64 bytenr, int level)
3357 {
3358 struct btrfs_root *root;
3359 struct btrfs_key key;
3360 struct btrfs_path path;
3361 struct extent_buffer *eb;
3362 struct extent_buffer *node;
3363 u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
3364 int err = 0;
3365 int ret;
3366
3367 /* Query level for level == -1 special case */
3368 if (level == -1)
3369 level = query_tree_block_level(fs_info, bytenr);
3370 if (level < 0) {
3371 err |= REFERENCER_MISSING;
3372 goto out;
3373 }
3374
3375 key.objectid = root_id;
3376 key.type = BTRFS_ROOT_ITEM_KEY;
3377 key.offset = (u64)-1;
3378
3379 root = btrfs_read_fs_root(fs_info, &key);
3380 if (IS_ERR(root)) {
3381 err |= REFERENCER_MISSING;
3382 goto out;
3383 }
3384
3385 /* Read out the tree block to get item/node key */
3386 eb = read_tree_block(fs_info, bytenr, 0);
3387 if (!extent_buffer_uptodate(eb)) {
3388 err |= REFERENCER_MISSING;
3389 free_extent_buffer(eb);
3390 goto out;
3391 }
3392
3393 /* Empty tree, no need to check key */
3394 if (!btrfs_header_nritems(eb) && !level) {
3395 free_extent_buffer(eb);
3396 goto out;
3397 }
3398
3399 if (level)
3400 btrfs_node_key_to_cpu(eb, &key, 0);
3401 else
3402 btrfs_item_key_to_cpu(eb, &key, 0);
3403
3404 free_extent_buffer(eb);
3405
3406 btrfs_init_path(&path);
3407 path.lowest_level = level;
3408 /* Search with the first key, to ensure we can reach it */
3409 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3410 if (ret < 0) {
3411 err |= REFERENCER_MISSING;
3412 goto release_out;
3413 }
3414
3415 node = path.nodes[level];
3416 if (btrfs_header_bytenr(node) != bytenr) {
3417 error(
3418 "extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu",
3419 bytenr, nodesize, bytenr,
3420 btrfs_header_bytenr(node));
3421 err |= REFERENCER_MISMATCH;
3422 }
3423 if (btrfs_header_level(node) != level) {
3424 error(
3425 "extent [%llu %d] referencer level mismatch, wanted: %d, have: %d",
3426 bytenr, nodesize, level,
3427 btrfs_header_level(node));
3428 err |= REFERENCER_MISMATCH;
3429 }
3430
3431 release_out:
3432 btrfs_release_path(&path);
3433 out:
3434 if (err & REFERENCER_MISSING) {
3435 if (level < 0)
3436 error("extent [%llu %d] lost referencer (owner: %llu)",
3437 bytenr, nodesize, root_id);
3438 else
3439 error(
3440 "extent [%llu %d] lost referencer (owner: %llu, level: %u)",
3441 bytenr, nodesize, root_id, level);
3442 }
3443
3444 return err;
3445 }
3446
3447 /*
3448 * Check if tree block @eb is tree reloc root.
3449 * Return 0 if it's not or any problem happens
3450 * Return 1 if it's a tree reloc root
3451 */
3452 static int is_tree_reloc_root(struct btrfs_fs_info *fs_info,
3453 struct extent_buffer *eb)
3454 {
3455 struct btrfs_root *tree_reloc_root;
3456 struct btrfs_key key;
3457 u64 bytenr = btrfs_header_bytenr(eb);
3458 u64 owner = btrfs_header_owner(eb);
3459 int ret = 0;
3460
3461 key.objectid = BTRFS_TREE_RELOC_OBJECTID;
3462 key.offset = owner;
3463 key.type = BTRFS_ROOT_ITEM_KEY;
3464
3465 tree_reloc_root = btrfs_read_fs_root_no_cache(fs_info, &key);
3466 if (IS_ERR(tree_reloc_root))
3467 return 0;
3468
3469 if (bytenr == btrfs_header_bytenr(tree_reloc_root->node))
3470 ret = 1;
3471 btrfs_free_fs_root(tree_reloc_root);
3472 return ret;
3473 }
3474
3475 /*
3476 * Check referencer for shared block backref
3477 * If level == -1, this function will resolve the level.
3478 */
3479 static int check_shared_block_backref(struct btrfs_fs_info *fs_info,
3480 u64 parent, u64 bytenr, int level)
3481 {
3482 struct extent_buffer *eb;
3483 u32 nr;
3484 int found_parent = 0;
3485 int i;
3486
3487 eb = read_tree_block(fs_info, parent, 0);
3488 if (!extent_buffer_uptodate(eb))
3489 goto out;
3490
3491 if (level == -1)
3492 level = query_tree_block_level(fs_info, bytenr);
3493 if (level < 0)
3494 goto out;
3495
3496 /* It's possible it's a tree reloc root */
3497 if (parent == bytenr) {
3498 if (is_tree_reloc_root(fs_info, eb))
3499 found_parent = 1;
3500 goto out;
3501 }
3502
3503 if (level + 1 != btrfs_header_level(eb))
3504 goto out;
3505
3506 nr = btrfs_header_nritems(eb);
3507 for (i = 0; i < nr; i++) {
3508 if (bytenr == btrfs_node_blockptr(eb, i)) {
3509 found_parent = 1;
3510 break;
3511 }
3512 }
3513 out:
3514 free_extent_buffer(eb);
3515 if (!found_parent) {
3516 error(
3517 "shared extent[%llu %u] lost its parent (parent: %llu, level: %u)",
3518 bytenr, fs_info->nodesize, parent, level);
3519 return REFERENCER_MISSING;
3520 }
3521 return 0;
3522 }
3523
3524 /*
3525 * Check referencer for normal (inlined) data ref
3526 * If len == 0, it will be resolved by searching in extent tree
3527 */
3528 static int check_extent_data_backref(struct btrfs_fs_info *fs_info,
3529 u64 root_id, u64 objectid, u64 offset,
3530 u64 bytenr, u64 len, u32 count)
3531 {
3532 struct btrfs_root *root;
3533 struct btrfs_root *extent_root = fs_info->extent_root;
3534 struct btrfs_key key;
3535 struct btrfs_path path;
3536 struct extent_buffer *leaf;
3537 struct btrfs_file_extent_item *fi;
3538 u32 found_count = 0;
3539 int slot;
3540 int ret = 0;
3541
3542 if (!len) {
3543 key.objectid = bytenr;
3544 key.type = BTRFS_EXTENT_ITEM_KEY;
3545 key.offset = (u64)-1;
3546
3547 btrfs_init_path(&path);
3548 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
3549 if (ret < 0)
3550 goto out;
3551 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
3552 if (ret)
3553 goto out;
3554 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
3555 if (key.objectid != bytenr ||
3556 key.type != BTRFS_EXTENT_ITEM_KEY)
3557 goto out;
3558 len = key.offset;
3559 btrfs_release_path(&path);
3560 }
3561 key.objectid = root_id;
3562 key.type = BTRFS_ROOT_ITEM_KEY;
3563 key.offset = (u64)-1;
3564 btrfs_init_path(&path);
3565
3566 root = btrfs_read_fs_root(fs_info, &key);
3567 if (IS_ERR(root))
3568 goto out;
3569
3570 key.objectid = objectid;
3571 key.type = BTRFS_EXTENT_DATA_KEY;
3572 /*
3573 * It can be nasty as data backref offset is
3574 * file offset - file extent offset, which is smaller or
3575 * equal to original backref offset. The only special case is
3576 * overflow. So we need to special check and do further search.
3577 */
3578 key.offset = offset & (1ULL << 63) ? 0 : offset;
3579
3580 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3581 if (ret < 0)
3582 goto out;
3583
3584 /*
3585 * Search afterwards to get correct one
3586 * NOTE: As we must do a comprehensive check on the data backref to
3587 * make sure the dref count also matches, we must iterate all file
3588 * extents for that inode.
3589 */
3590 while (1) {
3591 leaf = path.nodes[0];
3592 slot = path.slots[0];
3593
3594 if (slot >= btrfs_header_nritems(leaf) ||
3595 btrfs_header_owner(leaf) != root_id)
3596 goto next;
3597 btrfs_item_key_to_cpu(leaf, &key, slot);
3598 if (key.objectid != objectid ||
3599 key.type != BTRFS_EXTENT_DATA_KEY)
3600 break;
3601 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
3602 /*
3603 * Except normal disk bytenr and disk num bytes, we still
3604 * need to do extra check on dbackref offset as
3605 * dbackref offset = file_offset - file_extent_offset
3606 *
3607 * Also, we must check the leaf owner.
3608 * In case of shared tree blocks (snapshots) we can inherit
3609 * leaves from source snapshot.
3610 * In that case, reference from source snapshot should not
3611 * count.
3612 */
3613 if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr &&
3614 btrfs_file_extent_disk_num_bytes(leaf, fi) == len &&
3615 (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) ==
3616 offset && btrfs_header_owner(leaf) == root_id)
3617 found_count++;
3618
3619 next:
3620 ret = btrfs_next_item(root, &path);
3621 if (ret)
3622 break;
3623 }
3624 out:
3625 btrfs_release_path(&path);
3626 if (found_count != count) {
3627 error(
3628 "extent[%llu, %llu] referencer count mismatch (root: %llu, owner: %llu, offset: %llu) wanted: %u, have: %u",
3629 bytenr, len, root_id, objectid, offset, count,
3630 found_count);
3631 return REFERENCER_MISSING;
3632 }
3633 return 0;
3634 }
3635
3636 /*
3637 * Check if the referencer of a shared data backref exists
3638 */
3639 static int check_shared_data_backref(struct btrfs_fs_info *fs_info,
3640 u64 parent, u64 bytenr)
3641 {
3642 struct extent_buffer *eb;
3643 struct btrfs_key key;
3644 struct btrfs_file_extent_item *fi;
3645 u32 nr;
3646 int found_parent = 0;
3647 int i;
3648
3649 eb = read_tree_block(fs_info, parent, 0);
3650 if (!extent_buffer_uptodate(eb))
3651 goto out;
3652
3653 nr = btrfs_header_nritems(eb);
3654 for (i = 0; i < nr; i++) {
3655 btrfs_item_key_to_cpu(eb, &key, i);
3656 if (key.type != BTRFS_EXTENT_DATA_KEY)
3657 continue;
3658
3659 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
3660 if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE)
3661 continue;
3662
3663 if (btrfs_file_extent_disk_bytenr(eb, fi) == bytenr) {
3664 found_parent = 1;
3665 break;
3666 }
3667 }
3668
3669 out:
3670 free_extent_buffer(eb);
3671 if (!found_parent) {
3672 error("shared extent %llu referencer lost (parent: %llu)",
3673 bytenr, parent);
3674 return REFERENCER_MISSING;
3675 }
3676 return 0;
3677 }
3678
3679 /*
3680 * Only delete backref if REFERENCER_MISSING now
3681 *
3682 * Returns <0 the extent was deleted
3683 * Returns >0 the backref was deleted but extent still exists, returned value
3684 * means error after repair
3685 * Returns 0 nothing happened
3686 */
3687 static int repair_extent_item(struct btrfs_root *root, struct btrfs_path *path,
3688 u64 bytenr, u64 num_bytes, u64 parent, u64 root_objectid,
3689 u64 owner, u64 offset, int err)
3690 {
3691 struct btrfs_trans_handle *trans;
3692 struct btrfs_root *extent_root = root->fs_info->extent_root;
3693 struct btrfs_key old_key;
3694 int freed = 0;
3695 int ret;
3696
3697 btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]);
3698
3699 if ((err & (REFERENCER_MISSING | REFERENCER_MISMATCH)) == 0)
3700 return err;
3701
3702 ret = avoid_extents_overwrite(root->fs_info);
3703 if (ret)
3704 return err;
3705
3706 trans = btrfs_start_transaction(extent_root, 1);
3707 if (IS_ERR(trans)) {
3708 ret = PTR_ERR(trans);
3709 error("fail to start transaction %s", strerror(-ret));
3710 /* nothing happened */
3711 ret = 0;
3712 goto out;
3713 }
3714 /* delete the backref */
3715 ret = btrfs_free_extent(trans, root->fs_info->fs_root, bytenr,
3716 num_bytes, parent, root_objectid, owner, offset);
3717 if (!ret) {
3718 freed = 1;
3719 err &= ~REFERENCER_MISSING;
3720 printf("Delete backref in extent [%llu %llu]\n",
3721 bytenr, num_bytes);
3722 } else {
3723 error("fail to delete backref in extent [%llu %llu]",
3724 bytenr, num_bytes);
3725 }
3726 btrfs_commit_transaction(trans, extent_root);
3727
3728 /* btrfs_free_extent may delete the extent */
3729 btrfs_release_path(path);
3730 ret = btrfs_search_slot(NULL, root, &old_key, path, 0, 0);
3731 if (ret)
3732 ret = -ENOENT;
3733 else if (freed)
3734 ret = err;
3735 out:
3736 return ret;
3737 }
3738
3739 /*
3740 * This function will check a given extent item, including its backref and
3741 * itself (like crossing stripe boundary and type)
3742 *
3743 * Since we don't use extent_record anymore, introduce new error bit
3744 */
3745 static int check_extent_item(struct btrfs_fs_info *fs_info,
3746 struct btrfs_path *path)
3747 {
3748 struct btrfs_extent_item *ei;
3749 struct btrfs_extent_inline_ref *iref;
3750 struct btrfs_extent_data_ref *dref;
3751 struct extent_buffer *eb = path->nodes[0];
3752 unsigned long end;
3753 unsigned long ptr;
3754 int slot = path->slots[0];
3755 int type;
3756 u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
3757 u32 item_size = btrfs_item_size_nr(eb, slot);
3758 u64 flags;
3759 u64 offset;
3760 u64 parent;
3761 u64 num_bytes;
3762 u64 root_objectid;
3763 u64 owner;
3764 u64 owner_offset;
3765 int metadata = 0;
3766 int level;
3767 struct btrfs_key key;
3768 int ret;
3769 int err = 0;
3770
3771 btrfs_item_key_to_cpu(eb, &key, slot);
3772 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
3773 bytes_used += key.offset;
3774 num_bytes = key.offset;
3775 } else {
3776 bytes_used += nodesize;
3777 num_bytes = nodesize;
3778 }
3779
3780 if (item_size < sizeof(*ei)) {
3781 /*
3782 * COMPAT_EXTENT_TREE_V0 case, but it's already a super
3783 * old thing when on disk format is still un-determined.
3784 * No need to care about it anymore
3785 */
3786 error("unsupported COMPAT_EXTENT_TREE_V0 detected");
3787 return -ENOTTY;
3788 }
3789
3790 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
3791 flags = btrfs_extent_flags(eb, ei);
3792
3793 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
3794 metadata = 1;
3795 if (metadata && check_crossing_stripes(global_info, key.objectid,
3796 eb->len)) {
3797 error("bad metadata [%llu, %llu) crossing stripe boundary",
3798 key.objectid, key.objectid + nodesize);
3799 err |= CROSSING_STRIPE_BOUNDARY;
3800 }
3801
3802 ptr = (unsigned long)(ei + 1);
3803
3804 if (metadata && key.type == BTRFS_EXTENT_ITEM_KEY) {
3805 /* Old EXTENT_ITEM metadata */
3806 struct btrfs_tree_block_info *info;
3807
3808 info = (struct btrfs_tree_block_info *)ptr;
3809 level = btrfs_tree_block_level(eb, info);
3810 ptr += sizeof(struct btrfs_tree_block_info);
3811 } else {
3812 /* New METADATA_ITEM */
3813 level = key.offset;
3814 }
3815 end = (unsigned long)ei + item_size;
3816
3817 next:
3818 /* Reached extent item end normally */
3819 if (ptr == end)
3820 goto out;
3821
3822 /* Beyond extent item end, wrong item size */
3823 if (ptr > end) {
3824 err |= ITEM_SIZE_MISMATCH;
3825 error("extent item at bytenr %llu slot %d has wrong size",
3826 eb->start, slot);
3827 goto out;
3828 }
3829
3830 parent = 0;
3831 root_objectid = 0;
3832 owner = 0;
3833 owner_offset = 0;
3834 /* Now check every backref in this extent item */
3835 iref = (struct btrfs_extent_inline_ref *)ptr;
3836 type = btrfs_extent_inline_ref_type(eb, iref);
3837 offset = btrfs_extent_inline_ref_offset(eb, iref);
3838 switch (type) {
3839 case BTRFS_TREE_BLOCK_REF_KEY:
3840 root_objectid = offset;
3841 owner = level;
3842 ret = check_tree_block_backref(fs_info, offset, key.objectid,
3843 level);
3844 err |= ret;
3845 break;
3846 case BTRFS_SHARED_BLOCK_REF_KEY:
3847 parent = offset;
3848 ret = check_shared_block_backref(fs_info, offset, key.objectid,
3849 level);
3850 err |= ret;
3851 break;
3852 case BTRFS_EXTENT_DATA_REF_KEY:
3853 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
3854 root_objectid = btrfs_extent_data_ref_root(eb, dref);
3855 owner = btrfs_extent_data_ref_objectid(eb, dref);
3856 owner_offset = btrfs_extent_data_ref_offset(eb, dref);
3857 ret = check_extent_data_backref(fs_info, root_objectid, owner,
3858 owner_offset, key.objectid, key.offset,
3859 btrfs_extent_data_ref_count(eb, dref));
3860 err |= ret;
3861 break;
3862 case BTRFS_SHARED_DATA_REF_KEY:
3863 parent = offset;
3864 ret = check_shared_data_backref(fs_info, offset, key.objectid);
3865 err |= ret;
3866 break;
3867 default:
3868 error("extent[%llu %d %llu] has unknown ref type: %d",
3869 key.objectid, key.type, key.offset, type);
3870 ret = UNKNOWN_TYPE;
3871 err |= ret;
3872 goto out;
3873 }
3874
3875 if (err && repair) {
3876 ret = repair_extent_item(fs_info->extent_root, path,
3877 key.objectid, num_bytes, parent, root_objectid,
3878 owner, owner_offset, ret);
3879 if (ret < 0)
3880 goto out;
3881 if (ret) {
3882 goto next;
3883 err = ret;
3884 }
3885 }
3886
3887 ptr += btrfs_extent_inline_ref_size(type);
3888 goto next;
3889
3890 out:
3891 return err;
3892 }
3893
3894 /*
3895 * Check if a dev extent item is referred correctly by its chunk
3896 */
3897 static int check_dev_extent_item(struct btrfs_fs_info *fs_info,
3898 struct extent_buffer *eb, int slot)
3899 {
3900 struct btrfs_root *chunk_root = fs_info->chunk_root;
3901 struct btrfs_dev_extent *ptr;
3902 struct btrfs_path path;
3903 struct btrfs_key chunk_key;
3904 struct btrfs_key devext_key;
3905 struct btrfs_chunk *chunk;
3906 struct extent_buffer *l;
3907 int num_stripes;
3908 u64 length;
3909 int i;
3910 int found_chunk = 0;
3911 int ret;
3912
3913 btrfs_item_key_to_cpu(eb, &devext_key, slot);
3914 ptr = btrfs_item_ptr(eb, slot, struct btrfs_dev_extent);
3915 length = btrfs_dev_extent_length(eb, ptr);
3916
3917 chunk_key.objectid = btrfs_dev_extent_chunk_objectid(eb, ptr);
3918 chunk_key.type = BTRFS_CHUNK_ITEM_KEY;
3919 chunk_key.offset = btrfs_dev_extent_chunk_offset(eb, ptr);
3920
3921 btrfs_init_path(&path);
3922 ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0);
3923 if (ret)
3924 goto out;
3925
3926 l = path.nodes[0];
3927 chunk = btrfs_item_ptr(l, path.slots[0], struct btrfs_chunk);
3928 ret = btrfs_check_chunk_valid(fs_info, l, chunk, path.slots[0],
3929 chunk_key.offset);
3930 if (ret < 0)
3931 goto out;
3932
3933 if (btrfs_stripe_length(fs_info, l, chunk) != length)
3934 goto out;
3935
3936 num_stripes = btrfs_chunk_num_stripes(l, chunk);
3937 for (i = 0; i < num_stripes; i++) {
3938 u64 devid = btrfs_stripe_devid_nr(l, chunk, i);
3939 u64 offset = btrfs_stripe_offset_nr(l, chunk, i);
3940
3941 if (devid == devext_key.objectid &&
3942 offset == devext_key.offset) {
3943 found_chunk = 1;
3944 break;
3945 }
3946 }
3947 out:
3948 btrfs_release_path(&path);
3949 if (!found_chunk) {
3950 error(
3951 "device extent[%llu, %llu, %llu] did not find the related chunk",
3952 devext_key.objectid, devext_key.offset, length);
3953 return REFERENCER_MISSING;
3954 }
3955 return 0;
3956 }
3957
3958 /*
3959 * Check if the used space is correct with the dev item
3960 */
3961 static int check_dev_item(struct btrfs_fs_info *fs_info,
3962 struct extent_buffer *eb, int slot)
3963 {
3964 struct btrfs_root *dev_root = fs_info->dev_root;
3965 struct btrfs_dev_item *dev_item;
3966 struct btrfs_path path;
3967 struct btrfs_key key;
3968 struct btrfs_dev_extent *ptr;
3969 u64 total_bytes;
3970 u64 dev_id;
3971 u64 used;
3972 u64 total = 0;
3973 int ret;
3974
3975 dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
3976 dev_id = btrfs_device_id(eb, dev_item);
3977 used = btrfs_device_bytes_used(eb, dev_item);
3978 total_bytes = btrfs_device_total_bytes(eb, dev_item);
3979
3980 key.objectid = dev_id;
3981 key.type = BTRFS_DEV_EXTENT_KEY;
3982 key.offset = 0;
3983
3984 btrfs_init_path(&path);
3985 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
3986 if (ret < 0) {
3987 btrfs_item_key_to_cpu(eb, &key, slot);
3988 error("cannot find any related dev extent for dev[%llu, %u, %llu]",
3989 key.objectid, key.type, key.offset);
3990 btrfs_release_path(&path);
3991 return REFERENCER_MISSING;
3992 }
3993
3994 /* Iterate dev_extents to calculate the used space of a device */
3995 while (1) {
3996 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0]))
3997 goto next;
3998
3999 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
4000 if (key.objectid > dev_id)
4001 break;
4002 if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id)
4003 goto next;
4004
4005 ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
4006 struct btrfs_dev_extent);
4007 total += btrfs_dev_extent_length(path.nodes[0], ptr);
4008 next:
4009 ret = btrfs_next_item(dev_root, &path);
4010 if (ret)
4011 break;
4012 }
4013 btrfs_release_path(&path);
4014
4015 if (used != total) {
4016 btrfs_item_key_to_cpu(eb, &key, slot);
4017 error(
4018 "Dev extent's total-byte %llu is not equal to bytes-used %llu in dev[%llu, %u, %llu]",
4019 total, used, BTRFS_ROOT_TREE_OBJECTID,
4020 BTRFS_DEV_EXTENT_KEY, dev_id);
4021 return ACCOUNTING_MISMATCH;
4022 }
4023 check_dev_size_alignment(dev_id, total_bytes, fs_info->sectorsize);
4024
4025 return 0;
4026 }
4027
4028 /*
4029 * Check a chunk item.
4030 * Including checking all referred dev_extents and block group
4031 */
4032 static int check_chunk_item(struct btrfs_fs_info *fs_info,
4033 struct extent_buffer *eb, int slot)
4034 {
4035 struct btrfs_root *extent_root = fs_info->extent_root;
4036 struct btrfs_root *dev_root = fs_info->dev_root;
4037 struct btrfs_path path;
4038 struct btrfs_key chunk_key;
4039 struct btrfs_key bg_key;
4040 struct btrfs_key devext_key;
4041 struct btrfs_chunk *chunk;
4042 struct extent_buffer *leaf;
4043 struct btrfs_block_group_item *bi;
4044 struct btrfs_block_group_item bg_item;
4045 struct btrfs_dev_extent *ptr;
4046 u64 length;
4047 u64 chunk_end;
4048 u64 stripe_len;
4049 u64 type;
4050 int num_stripes;
4051 u64 offset;
4052 u64 objectid;
4053 int i;
4054 int ret;
4055 int err = 0;
4056
4057 btrfs_item_key_to_cpu(eb, &chunk_key, slot);
4058 chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
4059 length = btrfs_chunk_length(eb, chunk);
4060 chunk_end = chunk_key.offset + length;
4061 ret = btrfs_check_chunk_valid(fs_info, eb, chunk, slot,
4062 chunk_key.offset);
4063 if (ret < 0) {
4064 error("chunk[%llu %llu) is invalid", chunk_key.offset,
4065 chunk_end);
4066 err |= BYTES_UNALIGNED | UNKNOWN_TYPE;
4067 goto out;
4068 }
4069 type = btrfs_chunk_type(eb, chunk);
4070
4071 bg_key.objectid = chunk_key.offset;
4072 bg_key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
4073 bg_key.offset = length;
4074
4075 btrfs_init_path(&path);
4076 ret = btrfs_search_slot(NULL, extent_root, &bg_key, &path, 0, 0);
4077 if (ret) {
4078 error(
4079 "chunk[%llu %llu) did not find the related block group item",
4080 chunk_key.offset, chunk_end);
4081 err |= REFERENCER_MISSING;
4082 } else{
4083 leaf = path.nodes[0];
4084 bi = btrfs_item_ptr(leaf, path.slots[0],
4085 struct btrfs_block_group_item);
4086 read_extent_buffer(leaf, &bg_item, (unsigned long)bi,
4087 sizeof(bg_item));
4088 if (btrfs_block_group_flags(&bg_item) != type) {
4089 error(
4090 "chunk[%llu %llu) related block group item flags mismatch, wanted: %llu, have: %llu",
4091 chunk_key.offset, chunk_end, type,
4092 btrfs_block_group_flags(&bg_item));
4093 err |= REFERENCER_MISSING;
4094 }
4095 }
4096
4097 num_stripes = btrfs_chunk_num_stripes(eb, chunk);
4098 stripe_len = btrfs_stripe_length(fs_info, eb, chunk);
4099 for (i = 0; i < num_stripes; i++) {
4100 btrfs_release_path(&path);
4101 btrfs_init_path(&path);
4102 devext_key.objectid = btrfs_stripe_devid_nr(eb, chunk, i);
4103 devext_key.type = BTRFS_DEV_EXTENT_KEY;
4104 devext_key.offset = btrfs_stripe_offset_nr(eb, chunk, i);
4105
4106 ret = btrfs_search_slot(NULL, dev_root, &devext_key, &path,
4107 0, 0);
4108 if (ret)
4109 goto not_match_dev;
4110
4111 leaf = path.nodes[0];
4112 ptr = btrfs_item_ptr(leaf, path.slots[0],
4113 struct btrfs_dev_extent);
4114 objectid = btrfs_dev_extent_chunk_objectid(leaf, ptr);
4115 offset = btrfs_dev_extent_chunk_offset(leaf, ptr);
4116 if (objectid != chunk_key.objectid ||
4117 offset != chunk_key.offset ||
4118 btrfs_dev_extent_length(leaf, ptr) != stripe_len)
4119 goto not_match_dev;
4120 continue;
4121 not_match_dev:
4122 err |= BACKREF_MISSING;
4123 error(
4124 "chunk[%llu %llu) stripe %d did not find the related dev extent",
4125 chunk_key.objectid, chunk_end, i);
4126 continue;
4127 }
4128 btrfs_release_path(&path);
4129 out:
4130 return err;
4131 }
4132
4133 /*
4134 * Add block group item to the extent tree if @err contains REFERENCER_MISSING.
4135 * FIXME: We still need to repair error of dev_item.
4136 *
4137 * Returns error after repair.
4138 */
4139 static int repair_chunk_item(struct btrfs_root *chunk_root,
4140 struct btrfs_path *path, int err)
4141 {
4142 struct btrfs_chunk *chunk;
4143 struct btrfs_key chunk_key;
4144 struct extent_buffer *eb = path->nodes[0];
4145 struct btrfs_root *extent_root = chunk_root->fs_info->extent_root;
4146 struct btrfs_trans_handle *trans;
4147 u64 length;
4148 int slot = path->slots[0];
4149 u64 type;
4150 int ret = 0;
4151
4152 btrfs_item_key_to_cpu(eb, &chunk_key, slot);
4153 if (chunk_key.type != BTRFS_CHUNK_ITEM_KEY)
4154 return err;
4155 chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
4156 type = btrfs_chunk_type(path->nodes[0], chunk);
4157 length = btrfs_chunk_length(eb, chunk);
4158
4159 /* now repair only adds block group */
4160 if ((err & REFERENCER_MISSING) == 0)
4161 return err;
4162
4163 ret = avoid_extents_overwrite(chunk_root->fs_info);
4164 if (ret)
4165 return ret;
4166
4167 trans = btrfs_start_transaction(extent_root, 1);
4168 if (IS_ERR(trans)) {
4169 ret = PTR_ERR(trans);
4170 error("fail to start transaction %s", strerror(-ret));
4171 return ret;
4172 }
4173
4174 ret = btrfs_make_block_group(trans, chunk_root->fs_info, 0, type,
4175 chunk_key.offset, length);
4176 if (ret) {
4177 error("fail to add block group item [%llu %llu]",
4178 chunk_key.offset, length);
4179 } else {
4180 err &= ~REFERENCER_MISSING;
4181 printf("Added block group item[%llu %llu]\n", chunk_key.offset,
4182 length);
4183 }
4184
4185 btrfs_commit_transaction(trans, extent_root);
4186 if (ret)
4187 error("fail to repair item(s) related to chunk item [%llu %llu]",
4188 chunk_key.objectid, chunk_key.offset);
4189 return err;
4190 }
4191
4192 static int delete_extent_tree_item(struct btrfs_root *root,
4193 struct btrfs_path *path)
4194 {
4195 struct btrfs_key key;
4196 struct btrfs_trans_handle *trans;
4197 int ret = 0;
4198
4199 ret = avoid_extents_overwrite(root->fs_info);
4200 if (ret)
4201 return ret;
4202 trans = btrfs_start_transaction(root, 1);
4203 if (IS_ERR(trans)) {
4204 ret = PTR_ERR(trans);
4205 error("fail to start transaction %s", strerror(-ret));
4206 goto out;
4207 }
4208 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4209 btrfs_release_path(path);
4210 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
4211 if (ret) {
4212 ret = -ENOENT;
4213 goto out;
4214 }
4215
4216 ret = btrfs_del_item(trans, root, path);
4217 if (ret)
4218 goto out;
4219
4220 if (path->slots[0] == 0)
4221 btrfs_prev_leaf(root, path);
4222 else
4223 path->slots[0]--;
4224 out:
4225 btrfs_commit_transaction(trans, root);
4226 if (ret)
4227 error("failed to delete root %llu item[%llu, %u, %llu]",
4228 root->objectid, key.objectid, key.type, key.offset);
4229 else
4230 printf("Deleted root %llu item[%llu, %u, %llu]\n",
4231 root->objectid, key.objectid, key.type, key.offset);
4232 return ret;
4233 }
4234
4235 /*
4236 * Main entry function to check known items and update related accounting info
4237 */
4238 static int check_leaf_items(struct btrfs_root *root, struct btrfs_path *path,
4239 struct node_refs *nrefs, int account_bytes)
4240 {
4241 struct btrfs_fs_info *fs_info = root->fs_info;
4242 struct btrfs_key key;
4243 struct extent_buffer *eb;
4244 int slot;
4245 int type;
4246 struct btrfs_extent_data_ref *dref;
4247 int ret = 0;
4248 int err = 0;
4249
4250 again:
4251 eb = path->nodes[0];
4252 slot = path->slots[0];
4253 if (slot >= btrfs_header_nritems(eb)) {
4254 if (slot == 0) {
4255 error("empty leaf [%llu %u] root %llu", eb->start,
4256 root->fs_info->nodesize, root->objectid);
4257 err |= EIO;
4258 }
4259 goto out;
4260 }
4261
4262 btrfs_item_key_to_cpu(eb, &key, slot);
4263 type = key.type;
4264
4265 switch (type) {
4266 case BTRFS_EXTENT_DATA_KEY:
4267 ret = check_extent_data_item(root, path, nrefs, account_bytes);
4268 if (repair && ret)
4269 ret = repair_extent_data_item(root, path, nrefs, ret);
4270 err |= ret;
4271 break;
4272 case BTRFS_BLOCK_GROUP_ITEM_KEY:
4273 ret = check_block_group_item(fs_info, eb, slot);
4274 if (repair &&
4275 ret & REFERENCER_MISSING)
4276 ret = delete_extent_tree_item(root, path);
4277 err |= ret;
4278 break;
4279 case BTRFS_DEV_ITEM_KEY:
4280 ret = check_dev_item(fs_info, eb, slot);
4281 err |= ret;
4282 break;
4283 case BTRFS_CHUNK_ITEM_KEY:
4284 ret = check_chunk_item(fs_info, eb, slot);
4285 if (repair && ret)
4286 ret = repair_chunk_item(root, path, ret);
4287 err |= ret;
4288 break;
4289 case BTRFS_DEV_EXTENT_KEY:
4290 ret = check_dev_extent_item(fs_info, eb, slot);
4291 err |= ret;
4292 break;
4293 case BTRFS_EXTENT_ITEM_KEY:
4294 case BTRFS_METADATA_ITEM_KEY:
4295 ret = check_extent_item(fs_info, path);
4296 err |= ret;
4297 break;
4298 case BTRFS_EXTENT_CSUM_KEY:
4299 total_csum_bytes += btrfs_item_size_nr(eb, slot);
4300 err |= ret;
4301 break;
4302 case BTRFS_TREE_BLOCK_REF_KEY:
4303 ret = check_tree_block_backref(fs_info, key.offset,
4304 key.objectid, -1);
4305 if (repair &&
4306 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4307 ret = delete_extent_tree_item(root, path);
4308 err |= ret;
4309 break;
4310 case BTRFS_EXTENT_DATA_REF_KEY:
4311 dref = btrfs_item_ptr(eb, slot, struct btrfs_extent_data_ref);
4312 ret = check_extent_data_backref(fs_info,
4313 btrfs_extent_data_ref_root(eb, dref),
4314 btrfs_extent_data_ref_objectid(eb, dref),
4315 btrfs_extent_data_ref_offset(eb, dref),
4316 key.objectid, 0,
4317 btrfs_extent_data_ref_count(eb, dref));
4318 if (repair &&
4319 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4320 ret = delete_extent_tree_item(root, path);
4321 err |= ret;
4322 break;
4323 case BTRFS_SHARED_BLOCK_REF_KEY:
4324 ret = check_shared_block_backref(fs_info, key.offset,
4325 key.objectid, -1);
4326 if (repair &&
4327 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4328 ret = delete_extent_tree_item(root, path);
4329 err |= ret;
4330 break;
4331 case BTRFS_SHARED_DATA_REF_KEY:
4332 ret = check_shared_data_backref(fs_info, key.offset,
4333 key.objectid);
4334 if (repair &&
4335 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4336 ret = delete_extent_tree_item(root, path);
4337 err |= ret;
4338 break;
4339 default:
4340 break;
4341 }
4342
4343 ++path->slots[0];
4344 goto again;
4345 out:
4346 return err;
4347 }
4348
4349 /*
4350 * @trans just for lowmem repair mode
4351 * @check all if not 0 then check all tree block backrefs and items
4352 * 0 then just check relationship of items in fs tree(s)
4353 *
4354 * Returns >0 Found error, should continue
4355 * Returns <0 Fatal error, must exit the whole check
4356 * Returns 0 No errors found
4357 */
4358 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
4359 int *level, struct node_refs *nrefs, int check_all)
4360 {
4361 enum btrfs_tree_block_status status;
4362 u64 bytenr;
4363 u64 ptr_gen;
4364 struct btrfs_fs_info *fs_info = root->fs_info;
4365 struct extent_buffer *next;
4366 struct extent_buffer *cur;
4367 int ret;
4368 int err = 0;
4369 int check;
4370 int account_file_data = 0;
4371
4372 WARN_ON(*level < 0);
4373 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4374
4375 ret = update_nodes_refs(root, btrfs_header_bytenr(path->nodes[*level]),
4376 path->nodes[*level], nrefs, *level, check_all);
4377 if (ret < 0)
4378 return ret;
4379
4380 while (*level >= 0) {
4381 WARN_ON(*level < 0);
4382 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4383 cur = path->nodes[*level];
4384 bytenr = btrfs_header_bytenr(cur);
4385 check = nrefs->need_check[*level];
4386
4387 if (btrfs_header_level(cur) != *level)
4388 WARN_ON(1);
4389 /*
4390 * Update bytes accounting and check tree block ref
4391 * NOTE: Doing accounting and check before checking nritems
4392 * is necessary because of empty node/leaf.
4393 */
4394 if ((check_all && !nrefs->checked[*level]) ||
4395 (!check_all && nrefs->need_check[*level])) {
4396 ret = check_tree_block_ref(root, cur,
4397 btrfs_header_bytenr(cur), btrfs_header_level(cur),
4398 btrfs_header_owner(cur), nrefs);
4399
4400 if (repair && ret)
4401 ret = repair_tree_block_ref(root,
4402 path->nodes[*level], nrefs, *level, ret);
4403 err |= ret;
4404
4405 if (check_all && nrefs->need_check[*level] &&
4406 nrefs->refs[*level]) {
4407 account_bytes(root, path, *level);
4408 account_file_data = 1;
4409 }
4410 nrefs->checked[*level] = 1;
4411 }
4412
4413 if (path->slots[*level] >= btrfs_header_nritems(cur))
4414 break;
4415
4416 /* Don't forgot to check leaf/node validation */
4417 if (*level == 0) {
4418 /* skip duplicate check */
4419 if (check || !check_all) {
4420 ret = btrfs_check_leaf(root, NULL, cur);
4421 if (ret != BTRFS_TREE_BLOCK_CLEAN) {
4422 err |= -EIO;
4423 break;
4424 }
4425 }
4426
4427 ret = 0;
4428 if (!check_all)
4429 ret = process_one_leaf(root, path, nrefs, level);
4430 else
4431 ret = check_leaf_items(root, path,
4432 nrefs, account_file_data);
4433 err |= ret;
4434 break;
4435 }
4436 if (check || !check_all) {
4437 ret = btrfs_check_node(root, NULL, cur);
4438 if (ret != BTRFS_TREE_BLOCK_CLEAN) {
4439 err |= -EIO;
4440 break;
4441 }
4442 }
4443
4444 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4445 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4446
4447 ret = update_nodes_refs(root, bytenr, NULL, nrefs, *level - 1,
4448 check_all);
4449 if (ret < 0)
4450 break;
4451 /*
4452 * check all trees in check_chunks_and_extent
4453 * check shared node once in check_fs_roots
4454 */
4455 if (!check_all && !nrefs->need_check[*level - 1]) {
4456 path->slots[*level]++;
4457 continue;
4458 }
4459
4460 next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize);
4461 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
4462 free_extent_buffer(next);
4463 reada_walk_down(root, cur, path->slots[*level]);
4464 next = read_tree_block(fs_info, bytenr, ptr_gen);
4465 if (!extent_buffer_uptodate(next)) {
4466 struct btrfs_key node_key;
4467
4468 btrfs_node_key_to_cpu(path->nodes[*level],
4469 &node_key,
4470 path->slots[*level]);
4471 btrfs_add_corrupt_extent_record(fs_info,
4472 &node_key, path->nodes[*level]->start,
4473 fs_info->nodesize, *level);
4474 err |= -EIO;
4475 break;
4476 }
4477 }
4478
4479 ret = check_child_node(cur, path->slots[*level], next);
4480 err |= ret;
4481 if (ret < 0)
4482 break;
4483
4484 if (btrfs_is_leaf(next))
4485 status = btrfs_check_leaf(root, NULL, next);
4486 else
4487 status = btrfs_check_node(root, NULL, next);
4488 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4489 free_extent_buffer(next);
4490 err |= -EIO;
4491 break;
4492 }
4493
4494 *level = *level - 1;
4495 free_extent_buffer(path->nodes[*level]);
4496 path->nodes[*level] = next;
4497 path->slots[*level] = 0;
4498 account_file_data = 0;
4499
4500 update_nodes_refs(root, (u64)-1, next, nrefs, *level, check_all);
4501 }
4502 return err;
4503 }
4504
4505 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
4506 int *level)
4507 {
4508 int i;
4509 struct extent_buffer *leaf;
4510
4511 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
4512 leaf = path->nodes[i];
4513 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
4514 path->slots[i]++;
4515 *level = i;
4516 return 0;
4517 }
4518 free_extent_buffer(path->nodes[*level]);
4519 path->nodes[*level] = NULL;
4520 *level = i + 1;
4521 }
4522 return 1;
4523 }
4524
4525 /*
4526 * Insert the missing inode item and inode ref.
4527 *
4528 * Normal INODE_ITEM_MISSING and INODE_REF_MISSING are handled in backref * dir.
4529 * Root dir should be handled specially because root dir is the root of fs.
4530 *
4531 * returns err (>0 or 0) after repair
4532 */
4533 static int repair_fs_first_inode(struct btrfs_root *root, int err)
4534 {
4535 struct btrfs_trans_handle *trans;
4536 struct btrfs_key key;
4537 struct btrfs_path path;
4538 int filetype = BTRFS_FT_DIR;
4539 int ret = 0;
4540
4541 btrfs_init_path(&path);
4542
4543 if (err & INODE_REF_MISSING) {
4544 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
4545 key.type = BTRFS_INODE_REF_KEY;
4546 key.offset = BTRFS_FIRST_FREE_OBJECTID;
4547
4548 trans = btrfs_start_transaction(root, 1);
4549 if (IS_ERR(trans)) {
4550 ret = PTR_ERR(trans);
4551 goto out;
4552 }
4553
4554 btrfs_release_path(&path);
4555 ret = btrfs_search_slot(trans, root, &key, &path, 1, 1);
4556 if (ret)
4557 goto trans_fail;
4558
4559 ret = btrfs_insert_inode_ref(trans, root, "..", 2,
4560 BTRFS_FIRST_FREE_OBJECTID,
4561 BTRFS_FIRST_FREE_OBJECTID, 0);
4562 if (ret)
4563 goto trans_fail;
4564
4565 printf("Add INODE_REF[%llu %llu] name %s\n",
4566 BTRFS_FIRST_FREE_OBJECTID, BTRFS_FIRST_FREE_OBJECTID,
4567 "..");
4568 err &= ~INODE_REF_MISSING;
4569 trans_fail:
4570 if (ret)
4571 error("fail to insert first inode's ref");
4572 btrfs_commit_transaction(trans, root);
4573 }
4574
4575 if (err & INODE_ITEM_MISSING) {
4576 ret = repair_inode_item_missing(root,
4577 BTRFS_FIRST_FREE_OBJECTID, filetype);
4578 if (ret)
4579 goto out;
4580 err &= ~INODE_ITEM_MISSING;
4581 }
4582 out:
4583 if (ret)
4584 error("fail to repair first inode");
4585 btrfs_release_path(&path);
4586 return err;
4587 }
4588
4589 /*
4590 * check first root dir's inode_item and inode_ref
4591 *
4592 * returns 0 means no error
4593 * returns >0 means error
4594 * returns <0 means fatal error
4595 */
4596 static int check_fs_first_inode(struct btrfs_root *root)
4597 {
4598 struct btrfs_path path;
4599 struct btrfs_key key;
4600 struct btrfs_inode_item *ii;
4601 u64 index;
4602 u32 mode;
4603 int err = 0;
4604 int ret;
4605
4606 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
4607 key.type = BTRFS_INODE_ITEM_KEY;
4608 key.offset = 0;
4609
4610 /* For root being dropped, we don't need to check first inode */
4611 if (btrfs_root_refs(&root->root_item) == 0 &&
4612 btrfs_disk_key_objectid(&root->root_item.drop_progress) >=
4613 BTRFS_FIRST_FREE_OBJECTID)
4614 return 0;
4615
4616 btrfs_init_path(&path);
4617 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
4618 if (ret < 0)
4619 goto out;
4620 if (ret > 0) {
4621 ret = 0;
4622 err |= INODE_ITEM_MISSING;
4623 } else {
4624 ii = btrfs_item_ptr(path.nodes[0], path.slots[0],
4625 struct btrfs_inode_item);
4626 mode = btrfs_inode_mode(path.nodes[0], ii);
4627 if (imode_to_type(mode) != BTRFS_FT_DIR)
4628 err |= INODE_ITEM_MISMATCH;
4629 }
4630
4631 /* lookup first inode ref */
4632 key.offset = BTRFS_FIRST_FREE_OBJECTID;
4633 key.type = BTRFS_INODE_REF_KEY;
4634 /* special index value */
4635 index = 0;
4636
4637 ret = find_inode_ref(root, &key, "..", strlen(".."), &index);
4638 if (ret < 0)
4639 goto out;
4640 err |= ret;
4641
4642 out:
4643 btrfs_release_path(&path);
4644
4645 if (err && repair)
4646 err = repair_fs_first_inode(root, err);
4647
4648 if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH))
4649 error("root dir INODE_ITEM is %s",
4650 err & INODE_ITEM_MISMATCH ? "mismatch" : "missing");
4651 if (err & INODE_REF_MISSING)
4652 error("root dir INODE_REF is missing");
4653
4654 return ret < 0 ? ret : err;
4655 }
4656
4657 /*
4658 * This function calls walk_down_tree and walk_up_tree to check tree
4659 * blocks and integrity of fs tree items.
4660 *
4661 * @root: the root of the tree to be checked.
4662 * @account if NOT 0 means check the tree (including tree)'s treeblocks.
4663 * otherwise means check fs tree(s) items relationship and
4664 * @root MUST be a fs tree root.
4665 * Returns 0 represents OK.
4666 * Returns >0 represents error bits.
4667 */
4668 static int check_btrfs_root(struct btrfs_root *root, int check_all)
4669 {
4670 struct btrfs_path path;
4671 struct node_refs nrefs;
4672 struct btrfs_root_item *root_item = &root->root_item;
4673 int ret;
4674 int level;
4675 int err = 0;
4676
4677 memset(&nrefs, 0, sizeof(nrefs));
4678 if (!check_all) {
4679 /*
4680 * We need to manually check the first inode item (256)
4681 * As the following traversal function will only start from
4682 * the first inode item in the leaf, if inode item (256) is
4683 * missing we will skip it forever.
4684 */
4685 ret = check_fs_first_inode(root);
4686 if (ret < 0)
4687 return FATAL_ERROR;
4688 }
4689
4690
4691 level = btrfs_header_level(root->node);
4692 btrfs_init_path(&path);
4693
4694 if (btrfs_root_refs(root_item) > 0 ||
4695 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
4696 path.nodes[level] = root->node;
4697 path.slots[level] = 0;
4698 extent_buffer_get(root->node);
4699 } else {
4700 struct btrfs_key key;
4701
4702 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
4703 level = root_item->drop_level;
4704 path.lowest_level = level;
4705 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
4706 if (ret < 0)
4707 goto out;
4708 ret = 0;
4709 }
4710
4711 while (1) {
4712 ret = walk_down_tree(root, &path, &level, &nrefs, check_all);
4713
4714 if (ret > 0)
4715 err |= ret;
4716 /* if ret is negative, walk shall stop */
4717 if (ret < 0) {
4718 ret = err | FATAL_ERROR;
4719 break;
4720 }
4721
4722 ret = walk_up_tree(root, &path, &level);
4723 if (ret != 0) {
4724 /* Normal exit, reset ret to err */
4725 ret = err;
4726 break;
4727 }
4728 }
4729
4730 out:
4731 btrfs_release_path(&path);
4732 return ret;
4733 }
4734
4735 /*
4736 * Iterate all items in the tree and call check_inode_item() to check.
4737 *
4738 * @root: the root of the tree to be checked.
4739 *
4740 * Return 0 if no error found.
4741 * Return <0 for error.
4742 */
4743 static int check_fs_root(struct btrfs_root *root)
4744 {
4745 reset_cached_block_groups(root->fs_info);
4746 return check_btrfs_root(root, 0);
4747 }
4748
4749 /*
4750 * Find the relative ref for root_ref and root_backref.
4751 *
4752 * @root: the root of the root tree.
4753 * @ref_key: the key of the root ref.
4754 *
4755 * Return 0 if no error occurred.
4756 */
4757 static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
4758 struct extent_buffer *node, int slot)
4759 {
4760 struct btrfs_path path;
4761 struct btrfs_key key;
4762 struct btrfs_root_ref *ref;
4763 struct btrfs_root_ref *backref;
4764 char ref_name[BTRFS_NAME_LEN] = {0};
4765 char backref_name[BTRFS_NAME_LEN] = {0};
4766 u64 ref_dirid;
4767 u64 ref_seq;
4768 u32 ref_namelen;
4769 u64 backref_dirid;
4770 u64 backref_seq;
4771 u32 backref_namelen;
4772 u32 len;
4773 int ret;
4774 int err = 0;
4775
4776 ref = btrfs_item_ptr(node, slot, struct btrfs_root_ref);
4777 ref_dirid = btrfs_root_ref_dirid(node, ref);
4778 ref_seq = btrfs_root_ref_sequence(node, ref);
4779 ref_namelen = btrfs_root_ref_name_len(node, ref);
4780
4781 if (ref_namelen <= BTRFS_NAME_LEN) {
4782 len = ref_namelen;
4783 } else {
4784 len = BTRFS_NAME_LEN;
4785 warning("%s[%llu %llu] ref_name too long",
4786 ref_key->type == BTRFS_ROOT_REF_KEY ?
4787 "ROOT_REF" : "ROOT_BACKREF", ref_key->objectid,
4788 ref_key->offset);
4789 }
4790 read_extent_buffer(node, ref_name, (unsigned long)(ref + 1), len);
4791
4792 /* Find relative root_ref */
4793 key.objectid = ref_key->offset;
4794 key.type = BTRFS_ROOT_BACKREF_KEY + BTRFS_ROOT_REF_KEY - ref_key->type;
4795 key.offset = ref_key->objectid;
4796
4797 btrfs_init_path(&path);
4798 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
4799 if (ret) {
4800 err |= ROOT_REF_MISSING;
4801 error("%s[%llu %llu] couldn't find relative ref",
4802 ref_key->type == BTRFS_ROOT_REF_KEY ?
4803 "ROOT_REF" : "ROOT_BACKREF",
4804 ref_key->objectid, ref_key->offset);
4805 goto out;
4806 }
4807
4808 backref = btrfs_item_ptr(path.nodes[0], path.slots[0],
4809 struct btrfs_root_ref);
4810 backref_dirid = btrfs_root_ref_dirid(path.nodes[0], backref);
4811 backref_seq = btrfs_root_ref_sequence(path.nodes[0], backref);
4812 backref_namelen = btrfs_root_ref_name_len(path.nodes[0], backref);
4813
4814 if (backref_namelen <= BTRFS_NAME_LEN) {
4815 len = backref_namelen;
4816 } else {
4817 len = BTRFS_NAME_LEN;
4818 warning("%s[%llu %llu] ref_name too long",
4819 key.type == BTRFS_ROOT_REF_KEY ?
4820 "ROOT_REF" : "ROOT_BACKREF",
4821 key.objectid, key.offset);
4822 }
4823 read_extent_buffer(path.nodes[0], backref_name,
4824 (unsigned long)(backref + 1), len);
4825
4826 if (ref_dirid != backref_dirid || ref_seq != backref_seq ||
4827 ref_namelen != backref_namelen ||
4828 strncmp(ref_name, backref_name, len)) {
4829 err |= ROOT_REF_MISMATCH;
4830 error("%s[%llu %llu] mismatch relative ref",
4831 ref_key->type == BTRFS_ROOT_REF_KEY ?
4832 "ROOT_REF" : "ROOT_BACKREF",
4833 ref_key->objectid, ref_key->offset);
4834 }
4835 out:
4836 btrfs_release_path(&path);
4837 return err;
4838 }
4839
4840 /*
4841 * Check all fs/file tree in low_memory mode.
4842 *
4843 * 1. for fs tree root item, call check_fs_root()
4844 * 2. for fs tree root ref/backref, call check_root_ref()
4845 *
4846 * Return 0 if no error occurred.
4847 */
4848 int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
4849 {
4850 struct btrfs_root *tree_root = fs_info->tree_root;
4851 struct btrfs_root *cur_root = NULL;
4852 struct btrfs_path path;
4853 struct btrfs_key key;
4854 struct extent_buffer *node;
4855 int slot;
4856 int ret;
4857 int err = 0;
4858
4859 btrfs_init_path(&path);
4860 key.objectid = BTRFS_FS_TREE_OBJECTID;
4861 key.offset = 0;
4862 key.type = BTRFS_ROOT_ITEM_KEY;
4863
4864 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
4865 if (ret < 0) {
4866 err = ret;
4867 goto out;
4868 } else if (ret > 0) {
4869 err = -ENOENT;
4870 goto out;
4871 }
4872
4873 while (1) {
4874 node = path.nodes[0];
4875 slot = path.slots[0];
4876 btrfs_item_key_to_cpu(node, &key, slot);
4877 if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
4878 goto out;
4879 if (key.type == BTRFS_ROOT_ITEM_KEY &&
4880 fs_root_objectid(key.objectid)) {
4881 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
4882 cur_root = btrfs_read_fs_root_no_cache(fs_info,
4883 &key);
4884 } else {
4885 key.offset = (u64)-1;
4886 cur_root = btrfs_read_fs_root(fs_info, &key);
4887 }
4888
4889 if (IS_ERR(cur_root)) {
4890 error("Fail to read fs/subvol tree: %lld",
4891 key.objectid);
4892 err = -EIO;
4893 goto next;
4894 }
4895
4896 ret = check_fs_root(cur_root);
4897 err |= ret;
4898
4899 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
4900 btrfs_free_fs_root(cur_root);
4901 } else if (key.type == BTRFS_ROOT_REF_KEY ||
4902 key.type == BTRFS_ROOT_BACKREF_KEY) {
4903 ret = check_root_ref(tree_root, &key, node, slot);
4904 err |= ret;
4905 }
4906 next:
4907 ret = btrfs_next_item(tree_root, &path);
4908 if (ret > 0)
4909 goto out;
4910 if (ret < 0) {
4911 err = ret;
4912 goto out;
4913 }
4914 }
4915
4916 out:
4917 btrfs_release_path(&path);
4918 return err;
4919 }
4920
4921 /*
4922 * Low memory usage version check_chunks_and_extents.
4923 */
4924 int check_chunks_and_extents_lowmem(struct btrfs_fs_info *fs_info)
4925 {
4926 struct btrfs_path path;
4927 struct btrfs_key old_key;
4928 struct btrfs_key key;
4929 struct btrfs_root *root1;
4930 struct btrfs_root *root;
4931 struct btrfs_root *cur_root;
4932 int err = 0;
4933 int ret;
4934
4935 root = fs_info->fs_root;
4936
4937 root1 = root->fs_info->chunk_root;
4938 ret = check_btrfs_root(root1, 1);
4939 err |= ret;
4940
4941 root1 = root->fs_info->tree_root;
4942 ret = check_btrfs_root(root1, 1);
4943 err |= ret;
4944
4945 btrfs_init_path(&path);
4946 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
4947 key.offset = 0;
4948 key.type = BTRFS_ROOT_ITEM_KEY;
4949
4950 ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0);
4951 if (ret) {
4952 error("cannot find extent tree in tree_root");
4953 goto out;
4954 }
4955
4956 while (1) {
4957 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
4958 if (key.type != BTRFS_ROOT_ITEM_KEY)
4959 goto next;
4960 old_key = key;
4961 key.offset = (u64)-1;
4962
4963 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
4964 cur_root = btrfs_read_fs_root_no_cache(root->fs_info,
4965 &key);
4966 else
4967 cur_root = btrfs_read_fs_root(root->fs_info, &key);
4968 if (IS_ERR(cur_root) || !cur_root) {
4969 error("failed to read tree: %lld", key.objectid);
4970 goto next;
4971 }
4972
4973 ret = check_btrfs_root(cur_root, 1);
4974 err |= ret;
4975
4976 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
4977 btrfs_free_fs_root(cur_root);
4978
4979 btrfs_release_path(&path);
4980 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
4981 &old_key, &path, 0, 0);
4982 if (ret)
4983 goto out;
4984 next:
4985 ret = btrfs_next_item(root1, &path);
4986 if (ret)
4987 goto out;
4988 }
4989 out:
4990
4991 if (repair) {
4992 ret = end_avoid_extents_overwrite(fs_info);
4993 if (ret < 0)
4994 ret = FATAL_ERROR;
4995 err |= ret;
4996
4997 reset_cached_block_groups(fs_info);
4998 /* update block accounting */
4999 ret = repair_block_accounting(fs_info);
5000 if (ret)
5001 err |= ret;
5002 else
5003 err &= ~BG_ACCOUNTING_ERROR;
5004 }
5005
5006 btrfs_release_path(&path);
5007 return err;
5008 }
(deprecated) Btrfs progs developments and patch integration