?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Btrfs progs v4.17.1
[btrfs-progs-unstable/devel.git] / check / mode-lowmem.c
blob1bce44f5658a926451da60a545e514addaffec0f
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->fs_info, 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);
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 static int repair_inline_ram_bytes(struct btrfs_root *root,
1739 struct btrfs_path *path, u64 *ram_bytes_ret)
1740 {
1741 struct btrfs_trans_handle *trans;
1742 struct btrfs_key key;
1743 struct btrfs_file_extent_item *fi;
1744 struct btrfs_item *item;
1745 u32 on_disk_data_len;
1746 int ret;
1747 int recover_ret;
1748
1749 trans = btrfs_start_transaction(root, 1);
1750 if (IS_ERR(trans)) {
1751 ret = PTR_ERR(trans);
1752 return ret;
1753 }
1754 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1755 btrfs_release_path(path);
1756 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1757 /* Not really possible */
1758 if (ret > 0) {
1759 ret = -ENOENT;
1760 btrfs_release_path(path);
1761 goto recover;
1762 }
1763 if (ret < 0)
1764 goto recover;
1765
1766 item = btrfs_item_nr(path->slots[0]);
1767 on_disk_data_len = btrfs_file_extent_inline_item_len(path->nodes[0],
1768 item);
1769
1770 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
1771 struct btrfs_file_extent_item);
1772 if (btrfs_file_extent_type(path->nodes[0], fi) !=
1773 BTRFS_FILE_EXTENT_INLINE ||
1774 btrfs_file_extent_compression(path->nodes[0], fi) !=
1775 BTRFS_COMPRESS_NONE)
1776 return -EINVAL;
1777 btrfs_set_file_extent_ram_bytes(path->nodes[0], fi, on_disk_data_len);
1778 btrfs_mark_buffer_dirty(path->nodes[0]);
1779
1780 ret = btrfs_commit_transaction(trans, root);
1781 if (!ret) {
1782 printf(
1783 "Successfully repaired inline ram_bytes for root %llu ino %llu\n",
1784 root->objectid, key.objectid);
1785 *ram_bytes_ret = on_disk_data_len;
1786 }
1787 return ret;
1788
1789 recover:
1790 /*
1791 * COW search failed, mostly due to the extra COW work (extent
1792 * allocation, etc). Since we have a good path from before, readonly
1793 * search should still work, or later checks will fail due to empty
1794 * path.
1795 */
1796 recover_ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1797
1798 /* This really shouldn't happen, or we have a big problem */
1799 ASSERT(recover_ret == 0);
1800 return ret;
1801 }
1802
1803 /*
1804 * Check file extent datasum/hole, update the size of the file extents,
1805 * check and update the last offset of the file extent.
1806 *
1807 * @root: the root of fs/file tree.
1808 * @nodatasum: INODE_NODATASUM feature.
1809 * @size: the sum of all EXTENT_DATA items size for this inode.
1810 * @end: the offset of the last extent.
1811 *
1812 * Return 0 if no error occurred.
1813 */
1814 static int check_file_extent(struct btrfs_root *root, struct btrfs_path *path,
1815 unsigned int nodatasum, u64 *size, u64 *end)
1816 {
1817 struct btrfs_file_extent_item *fi;
1818 struct btrfs_key fkey;
1819 struct extent_buffer *node = path->nodes[0];
1820 u64 disk_bytenr;
1821 u64 disk_num_bytes;
1822 u64 extent_num_bytes;
1823 u64 extent_offset;
1824 u64 csum_found; /* In byte size, sectorsize aligned */
1825 u64 search_start; /* Logical range start we search for csum */
1826 u64 search_len; /* Logical range len we search for csum */
1827 u32 max_inline_extent_size = min_t(u32, root->fs_info->sectorsize - 1,
1828 BTRFS_MAX_INLINE_DATA_SIZE(root->fs_info));
1829 unsigned int extent_type;
1830 unsigned int is_hole;
1831 int slot = path->slots[0];
1832 int compressed = 0;
1833 int ret;
1834 int err = 0;
1835
1836 btrfs_item_key_to_cpu(node, &fkey, slot);
1837 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
1838
1839 /* Check inline extent */
1840 extent_type = btrfs_file_extent_type(node, fi);
1841 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1842 struct btrfs_item *e = btrfs_item_nr(slot);
1843 u32 item_inline_len;
1844
1845 item_inline_len = btrfs_file_extent_inline_item_len(node, e);
1846 extent_num_bytes = btrfs_file_extent_ram_bytes(node, fi);
1847 compressed = btrfs_file_extent_compression(node, fi);
1848 if (extent_num_bytes == 0) {
1849 error(
1850 "root %llu EXTENT_DATA[%llu %llu] has empty inline extent",
1851 root->objectid, fkey.objectid, fkey.offset);
1852 err |= FILE_EXTENT_ERROR;
1853 }
1854 if (compressed) {
1855 if (extent_num_bytes > root->fs_info->sectorsize) {
1856 error(
1857 "root %llu EXTENT_DATA[%llu %llu] too large inline extent ram size, have %llu, max: %u",
1858 root->objectid, fkey.objectid,
1859 fkey.offset, extent_num_bytes,
1860 root->fs_info->sectorsize - 1);
1861 err |= FILE_EXTENT_ERROR;
1862 }
1863 if (item_inline_len > max_inline_extent_size) {
1864 error(
1865 "root %llu EXTENT_DATA[%llu %llu] too large inline extent on-disk size, have %u, max: %u",
1866 root->objectid, fkey.objectid,
1867 fkey.offset, item_inline_len,
1868 max_inline_extent_size);
1869 err |= FILE_EXTENT_ERROR;
1870 }
1871 } else {
1872 if (extent_num_bytes > max_inline_extent_size) {
1873 error(
1874 "root %llu EXTENT_DATA[%llu %llu] too large inline extent size, have %llu, max: %u",
1875 root->objectid, fkey.objectid, fkey.offset,
1876 extent_num_bytes, max_inline_extent_size);
1877 err |= FILE_EXTENT_ERROR;
1878 }
1879 }
1880 if (!compressed && extent_num_bytes != item_inline_len) {
1881 error(
1882 "root %llu EXTENT_DATA[%llu %llu] wrong inline size, have: %llu, expected: %u",
1883 root->objectid, fkey.objectid, fkey.offset,
1884 extent_num_bytes, item_inline_len);
1885 if (repair) {
1886 ret = repair_inline_ram_bytes(root, path,
1887 &extent_num_bytes);
1888 if (ret)
1889 err |= FILE_EXTENT_ERROR;
1890 } else {
1891 err |= FILE_EXTENT_ERROR;
1892 }
1893 }
1894 *end += extent_num_bytes;
1895 *size += extent_num_bytes;
1896 return err;
1897 }
1898
1899 /* Check extent type */
1900 if (extent_type != BTRFS_FILE_EXTENT_REG &&
1901 extent_type != BTRFS_FILE_EXTENT_PREALLOC) {
1902 err |= FILE_EXTENT_ERROR;
1903 error("root %llu EXTENT_DATA[%llu %llu] type bad",
1904 root->objectid, fkey.objectid, fkey.offset);
1905 return err;
1906 }
1907
1908 /* Check REG_EXTENT/PREALLOC_EXTENT */
1909 disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
1910 disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
1911 extent_num_bytes = btrfs_file_extent_num_bytes(node, fi);
1912 extent_offset = btrfs_file_extent_offset(node, fi);
1913 compressed = btrfs_file_extent_compression(node, fi);
1914 is_hole = (disk_bytenr == 0) && (disk_num_bytes == 0);
1915
1916 /*
1917 * Check EXTENT_DATA csum
1918 *
1919 * For plain (uncompressed) extent, we should only check the range
1920 * we're referring to, as it's possible that part of prealloc extent
1921 * has been written, and has csum:
1922 *
1923 * |<--- Original large preallocated extent A ---->|
1924 * |<- Prealloc File Extent ->|<- Regular Extent ->|
1925 * No csum Has csum
1926 *
1927 * For compressed extent, we should check the whole range.
1928 */
1929 if (!compressed) {
1930 search_start = disk_bytenr + extent_offset;
1931 search_len = extent_num_bytes;
1932 } else {
1933 search_start = disk_bytenr;
1934 search_len = disk_num_bytes;
1935 }
1936 ret = count_csum_range(root->fs_info, search_start, search_len,
1937 &csum_found);
1938 if (csum_found > 0 && nodatasum) {
1939 err |= ODD_CSUM_ITEM;
1940 error("root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum",
1941 root->objectid, fkey.objectid, fkey.offset);
1942 } else if (extent_type == BTRFS_FILE_EXTENT_REG && !nodatasum &&
1943 !is_hole && (ret < 0 || csum_found < search_len)) {
1944 err |= CSUM_ITEM_MISSING;
1945 error("root %llu EXTENT_DATA[%llu %llu] csum missing, have: %llu, expected: %llu",
1946 root->objectid, fkey.objectid, fkey.offset,
1947 csum_found, search_len);
1948 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
1949 csum_found > 0) {
1950 ret = check_prealloc_extent_written(root->fs_info,
1951 disk_bytenr, disk_num_bytes);
1952 if (ret < 0)
1953 return ret;
1954 if (ret == 0) {
1955 err |= ODD_CSUM_ITEM;
1956 error(
1957 "root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have csum, but has: %llu",
1958 root->objectid, fkey.objectid, fkey.offset,
1959 csum_found);
1960 }
1961 }
1962
1963 /* Check EXTENT_DATA hole */
1964 if (!no_holes && *end != fkey.offset) {
1965 if (repair)
1966 ret = punch_extent_hole(root, fkey.objectid,
1967 *end, fkey.offset - *end);
1968 if (!repair || ret) {
1969 err |= FILE_EXTENT_ERROR;
1970 error(
1971 "root %llu EXTENT_DATA[%llu %llu] gap exists, expected: EXTENT_DATA[%llu %llu]",
1972 root->objectid, fkey.objectid, fkey.offset,
1973 fkey.objectid, *end);
1974 }
1975 }
1976
1977 *end += extent_num_bytes;
1978 if (!is_hole)
1979 *size += extent_num_bytes;
1980
1981 return err;
1982 }
1983
1984 static int __count_dir_isize(struct btrfs_root *root, u64 ino, int type,
1985 u64 *size_ret)
1986 {
1987 struct btrfs_key key;
1988 struct btrfs_path path;
1989 u32 len;
1990 struct btrfs_dir_item *di;
1991 int ret;
1992 int cur = 0;
1993 int total = 0;
1994
1995 ASSERT(size_ret);
1996 *size_ret = 0;
1997
1998 key.objectid = ino;
1999 key.type = type;
2000 key.offset = (u64)-1;
2001
2002 btrfs_init_path(&path);
2003 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
2004 if (ret < 0) {
2005 ret = -EIO;
2006 goto out;
2007 }
2008 /* if found, go to spacial case */
2009 if (ret == 0)
2010 goto special_case;
2011
2012 loop:
2013 ret = btrfs_previous_item(root, &path, ino, type);
2014
2015 if (ret) {
2016 ret = 0;
2017 goto out;
2018 }
2019
2020 special_case:
2021 di = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_dir_item);
2022 cur = 0;
2023 total = btrfs_item_size_nr(path.nodes[0], path.slots[0]);
2024
2025 while (cur < total) {
2026 len = btrfs_dir_name_len(path.nodes[0], di);
2027 if (len > BTRFS_NAME_LEN)
2028 len = BTRFS_NAME_LEN;
2029 *size_ret += len;
2030
2031 len += btrfs_dir_data_len(path.nodes[0], di);
2032 len += sizeof(*di);
2033 di = (struct btrfs_dir_item *)((char *)di + len);
2034 cur += len;
2035 }
2036 goto loop;
2037
2038 out:
2039 btrfs_release_path(&path);
2040 return ret;
2041 }
2042
2043 static int count_dir_isize(struct btrfs_root *root, u64 ino, u64 *size)
2044 {
2045 u64 item_size;
2046 u64 index_size;
2047 int ret;
2048
2049 ASSERT(size);
2050 ret = __count_dir_isize(root, ino, BTRFS_DIR_ITEM_KEY, &item_size);
2051 if (ret)
2052 goto out;
2053
2054 ret = __count_dir_isize(root, ino, BTRFS_DIR_INDEX_KEY, &index_size);
2055 if (ret)
2056 goto out;
2057
2058 *size = item_size + index_size;
2059
2060 out:
2061 if (ret)
2062 error("failed to count root %llu INODE[%llu] root size",
2063 root->objectid, ino);
2064 return ret;
2065 }
2066
2067 /*
2068 * Set inode item nbytes to @nbytes
2069 *
2070 * Returns 0 on success
2071 * Returns != 0 on error
2072 */
2073 static int repair_inode_nbytes_lowmem(struct btrfs_root *root,
2074 struct btrfs_path *path,
2075 u64 ino, u64 nbytes)
2076 {
2077 struct btrfs_trans_handle *trans;
2078 struct btrfs_inode_item *ii;
2079 struct btrfs_key key;
2080 struct btrfs_key research_key;
2081 int err = 0;
2082 int ret;
2083
2084 btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
2085
2086 key.objectid = ino;
2087 key.type = BTRFS_INODE_ITEM_KEY;
2088 key.offset = 0;
2089
2090 trans = btrfs_start_transaction(root, 1);
2091 if (IS_ERR(trans)) {
2092 ret = PTR_ERR(trans);
2093 err |= ret;
2094 goto out;
2095 }
2096
2097 btrfs_release_path(path);
2098 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2099 if (ret > 0)
2100 ret = -ENOENT;
2101 if (ret) {
2102 err |= ret;
2103 goto fail;
2104 }
2105
2106 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
2107 struct btrfs_inode_item);
2108 btrfs_set_inode_nbytes(path->nodes[0], ii, nbytes);
2109 btrfs_mark_buffer_dirty(path->nodes[0]);
2110 fail:
2111 btrfs_commit_transaction(trans, root);
2112 out:
2113 if (ret)
2114 error("failed to set nbytes in inode %llu root %llu",
2115 ino, root->root_key.objectid);
2116 else
2117 printf("Set nbytes in inode item %llu root %llu\n to %llu", ino,
2118 root->root_key.objectid, nbytes);
2119
2120 /* research path */
2121 btrfs_release_path(path);
2122 ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
2123 err |= ret;
2124
2125 return err;
2126 }
2127
2128 /*
2129 * Set directory inode isize to @isize.
2130 *
2131 * Returns 0 on success.
2132 * Returns != 0 on error.
2133 */
2134 static int repair_dir_isize_lowmem(struct btrfs_root *root,
2135 struct btrfs_path *path,
2136 u64 ino, u64 isize)
2137 {
2138 struct btrfs_trans_handle *trans;
2139 struct btrfs_inode_item *ii;
2140 struct btrfs_key key;
2141 struct btrfs_key research_key;
2142 int ret;
2143 int err = 0;
2144
2145 btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
2146
2147 key.objectid = ino;
2148 key.type = BTRFS_INODE_ITEM_KEY;
2149 key.offset = 0;
2150
2151 trans = btrfs_start_transaction(root, 1);
2152 if (IS_ERR(trans)) {
2153 ret = PTR_ERR(trans);
2154 err |= ret;
2155 goto out;
2156 }
2157
2158 btrfs_release_path(path);
2159 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2160 if (ret > 0)
2161 ret = -ENOENT;
2162 if (ret) {
2163 err |= ret;
2164 goto fail;
2165 }
2166
2167 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
2168 struct btrfs_inode_item);
2169 btrfs_set_inode_size(path->nodes[0], ii, isize);
2170 btrfs_mark_buffer_dirty(path->nodes[0]);
2171 fail:
2172 btrfs_commit_transaction(trans, root);
2173 out:
2174 if (ret)
2175 error("failed to set isize in inode %llu root %llu",
2176 ino, root->root_key.objectid);
2177 else
2178 printf("Set isize in inode %llu root %llu to %llu\n",
2179 ino, root->root_key.objectid, isize);
2180
2181 btrfs_release_path(path);
2182 ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
2183 err |= ret;
2184
2185 return err;
2186 }
2187
2188 /*
2189 * Wrapper function for btrfs_add_orphan_item().
2190 *
2191 * Returns 0 on success.
2192 * Returns != 0 on error.
2193 */
2194 static int repair_inode_orphan_item_lowmem(struct btrfs_root *root,
2195 struct btrfs_path *path, u64 ino)
2196 {
2197 struct btrfs_trans_handle *trans;
2198 struct btrfs_key research_key;
2199 int ret;
2200 int err = 0;
2201
2202 btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
2203
2204 trans = btrfs_start_transaction(root, 1);
2205 if (IS_ERR(trans)) {
2206 ret = PTR_ERR(trans);
2207 err |= ret;
2208 goto out;
2209 }
2210
2211 btrfs_release_path(path);
2212 ret = btrfs_add_orphan_item(trans, root, path, ino);
2213 err |= ret;
2214 btrfs_commit_transaction(trans, root);
2215 out:
2216 if (ret)
2217 error("failed to add inode %llu as orphan item root %llu",
2218 ino, root->root_key.objectid);
2219 else
2220 printf("Added inode %llu as orphan item root %llu\n",
2221 ino, root->root_key.objectid);
2222
2223 btrfs_release_path(path);
2224 ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
2225 err |= ret;
2226
2227 return err;
2228 }
2229
2230 /* Set inode_item nlink to @ref_count.
2231 * If @ref_count == 0, move it to "lost+found" and increase @ref_count.
2232 *
2233 * Returns 0 on success
2234 */
2235 static int repair_inode_nlinks_lowmem(struct btrfs_root *root,
2236 struct btrfs_path *path, u64 ino,
2237 const char *name, u32 namelen,
2238 u64 ref_count, u8 filetype, u64 *nlink)
2239 {
2240 struct btrfs_trans_handle *trans;
2241 struct btrfs_inode_item *ii;
2242 struct btrfs_key key;
2243 struct btrfs_key old_key;
2244 char namebuf[BTRFS_NAME_LEN] = {0};
2245 int name_len;
2246 int ret;
2247 int ret2;
2248
2249 /* save the key */
2250 btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]);
2251
2252 if (name && namelen) {
2253 ASSERT(namelen <= BTRFS_NAME_LEN);
2254 memcpy(namebuf, name, namelen);
2255 name_len = namelen;
2256 } else {
2257 sprintf(namebuf, "%llu", ino);
2258 name_len = count_digits(ino);
2259 printf("Can't find file name for inode %llu, use %s instead\n",
2260 ino, namebuf);
2261 }
2262
2263 trans = btrfs_start_transaction(root, 1);
2264 if (IS_ERR(trans)) {
2265 ret = PTR_ERR(trans);
2266 goto out;
2267 }
2268
2269 btrfs_release_path(path);
2270 /* if refs is 0, put it into lostfound */
2271 if (ref_count == 0) {
2272 ret = link_inode_to_lostfound(trans, root, path, ino, namebuf,
2273 name_len, filetype, &ref_count);
2274 if (ret)
2275 goto fail;
2276 }
2277
2278 /* reset inode_item's nlink to ref_count */
2279 key.objectid = ino;
2280 key.type = BTRFS_INODE_ITEM_KEY;
2281 key.offset = 0;
2282
2283 btrfs_release_path(path);
2284 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2285 if (ret > 0)
2286 ret = -ENOENT;
2287 if (ret)
2288 goto fail;
2289
2290 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
2291 struct btrfs_inode_item);
2292 btrfs_set_inode_nlink(path->nodes[0], ii, ref_count);
2293 btrfs_mark_buffer_dirty(path->nodes[0]);
2294
2295 if (nlink)
2296 *nlink = ref_count;
2297 fail:
2298 btrfs_commit_transaction(trans, root);
2299 out:
2300 if (ret)
2301 error(
2302 "fail to repair nlink of inode %llu root %llu name %s filetype %u",
2303 root->objectid, ino, namebuf, filetype);
2304 else
2305 printf("Fixed nlink of inode %llu root %llu name %s filetype %u\n",
2306 root->objectid, ino, namebuf, filetype);
2307
2308 /* research */
2309 btrfs_release_path(path);
2310 ret2 = btrfs_search_slot(NULL, root, &old_key, path, 0, 0);
2311 if (ret2 < 0)
2312 return ret |= ret2;
2313 return ret;
2314 }
2315
2316 static bool has_orphan_item(struct btrfs_root *root, u64 ino)
2317 {
2318 struct btrfs_path path;
2319 struct btrfs_key key;
2320 int ret;
2321
2322 btrfs_init_path(&path);
2323 key.objectid = BTRFS_ORPHAN_OBJECTID;
2324 key.type = BTRFS_ORPHAN_ITEM_KEY;
2325 key.offset = ino;
2326
2327 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
2328 btrfs_release_path(&path);
2329 if (ret == 0)
2330 return true;
2331 return false;
2332 }
2333
2334 /*
2335 * Check INODE_ITEM and related ITEMs (the same inode number)
2336 * 1. check link count
2337 * 2. check inode ref/extref
2338 * 3. check dir item/index
2339 *
2340 * Return 0 if no error occurred.
2341 * Return >0 for error or hit the traversal is done(by error bitmap)
2342 */
2343 static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path)
2344 {
2345 struct extent_buffer *node;
2346 struct btrfs_inode_item *ii;
2347 struct btrfs_key key;
2348 struct btrfs_key last_key;
2349 u64 inode_id;
2350 u32 mode;
2351 u64 flags;
2352 u64 nlink;
2353 u64 nbytes;
2354 u64 isize;
2355 u64 size = 0;
2356 u64 refs = 0;
2357 u64 extent_end = 0;
2358 u64 extent_size = 0;
2359 unsigned int dir;
2360 unsigned int nodatasum;
2361 bool is_orphan = false;
2362 int slot;
2363 int ret;
2364 int err = 0;
2365 char namebuf[BTRFS_NAME_LEN] = {0};
2366 u32 name_len = 0;
2367
2368 node = path->nodes[0];
2369 slot = path->slots[0];
2370
2371 btrfs_item_key_to_cpu(node, &key, slot);
2372 inode_id = key.objectid;
2373
2374 if (inode_id == BTRFS_ORPHAN_OBJECTID) {
2375 ret = btrfs_next_item(root, path);
2376 if (ret > 0)
2377 err |= LAST_ITEM;
2378 return err;
2379 }
2380
2381 ii = btrfs_item_ptr(node, slot, struct btrfs_inode_item);
2382 isize = btrfs_inode_size(node, ii);
2383 nbytes = btrfs_inode_nbytes(node, ii);
2384 mode = btrfs_inode_mode(node, ii);
2385 flags = btrfs_inode_flags(node, ii);
2386 dir = imode_to_type(mode) == BTRFS_FT_DIR;
2387 nlink = btrfs_inode_nlink(node, ii);
2388 nodatasum = btrfs_inode_flags(node, ii) & BTRFS_INODE_NODATASUM;
2389
2390 if (S_ISLNK(mode) &&
2391 flags & (BTRFS_INODE_IMMUTABLE | BTRFS_INODE_APPEND)) {
2392 err |= INODE_FLAGS_ERROR;
2393 error(
2394 "symlinks must never have immutable/append flags set, root %llu inode item %llu flags %llu may be corrupted",
2395 root->objectid, inode_id, flags);
2396 }
2397
2398 while (1) {
2399 btrfs_item_key_to_cpu(path->nodes[0], &last_key, path->slots[0]);
2400 ret = btrfs_next_item(root, path);
2401 if (ret < 0) {
2402 /* out will fill 'err' rusing current statistics */
2403 goto out;
2404 } else if (ret > 0) {
2405 err |= LAST_ITEM;
2406 goto out;
2407 }
2408
2409 node = path->nodes[0];
2410 slot = path->slots[0];
2411 btrfs_item_key_to_cpu(node, &key, slot);
2412 if (key.objectid != inode_id)
2413 goto out;
2414
2415 switch (key.type) {
2416 case BTRFS_INODE_REF_KEY:
2417 ret = check_inode_ref(root, &key, path, namebuf,
2418 &name_len, &refs, mode);
2419 err |= ret;
2420 break;
2421 case BTRFS_INODE_EXTREF_KEY:
2422 {
2423 bool ext_ref = btrfs_fs_incompat(root->fs_info,
2424 EXTENDED_IREF);
2425 if (key.type == BTRFS_INODE_EXTREF_KEY && !ext_ref)
2426 warning("root %llu EXTREF[%llu %llu] isn't supported",
2427 root->objectid, key.objectid,
2428 key.offset);
2429 ret = check_inode_extref(root, &key, node, slot, &refs,
2430 mode);
2431 err |= ret;
2432 break;
2433 }
2434 case BTRFS_DIR_ITEM_KEY:
2435 case BTRFS_DIR_INDEX_KEY:
2436 if (!dir) {
2437 warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]",
2438 root->objectid, inode_id,
2439 imode_to_type(mode), key.objectid,
2440 key.offset);
2441 }
2442 ret = check_dir_item(root, &key, path, &size);
2443 err |= ret;
2444 break;
2445 case BTRFS_EXTENT_DATA_KEY:
2446 if (dir) {
2447 warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]",
2448 root->objectid, inode_id, key.objectid,
2449 key.offset);
2450 }
2451 ret = check_file_extent(root, path, nodatasum,
2452 &extent_size, &extent_end);
2453 err |= ret;
2454 break;
2455 case BTRFS_XATTR_ITEM_KEY:
2456 break;
2457 default:
2458 error("ITEM[%llu %u %llu] UNKNOWN TYPE",
2459 key.objectid, key.type, key.offset);
2460 }
2461 }
2462
2463 out:
2464 if (err & LAST_ITEM) {
2465 btrfs_release_path(path);
2466 ret = btrfs_search_slot(NULL, root, &last_key, path, 0, 0);
2467 if (ret)
2468 return err;
2469 }
2470
2471 /* verify INODE_ITEM nlink/isize/nbytes */
2472 if (dir) {
2473 if (repair && (err & DIR_COUNT_AGAIN)) {
2474 err &= ~DIR_COUNT_AGAIN;
2475 count_dir_isize(root, inode_id, &size);
2476 }
2477
2478 if ((nlink != 1 || refs != 1) && repair) {
2479 ret = repair_inode_nlinks_lowmem(root, path, inode_id,
2480 namebuf, name_len, refs, imode_to_type(mode),
2481 &nlink);
2482 }
2483
2484 if (nlink != 1) {
2485 err |= LINK_COUNT_ERROR;
2486 error("root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)",
2487 root->objectid, inode_id, nlink);
2488 }
2489
2490 /*
2491 * Just a warning, as dir inode nbytes is just an
2492 * instructive value.
2493 */
2494 if (!IS_ALIGNED(nbytes, root->fs_info->nodesize)) {
2495 warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u",
2496 root->objectid, inode_id,
2497 root->fs_info->nodesize);
2498 }
2499
2500 if (isize != size) {
2501 if (repair)
2502 ret = repair_dir_isize_lowmem(root, path,
2503 inode_id, size);
2504 if (!repair || ret) {
2505 err |= ISIZE_ERROR;
2506 error(
2507 "root %llu DIR INODE [%llu] size %llu not equal to %llu",
2508 root->objectid, inode_id, isize, size);
2509 }
2510 }
2511 } else {
2512 if (nlink != refs) {
2513 if (repair)
2514 ret = repair_inode_nlinks_lowmem(root, path,
2515 inode_id, namebuf, name_len, refs,
2516 imode_to_type(mode), &nlink);
2517 if (!repair || ret) {
2518 err |= LINK_COUNT_ERROR;
2519 error(
2520 "root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)",
2521 root->objectid, inode_id, nlink, refs);
2522 }
2523 } else if (!nlink) {
2524 is_orphan = has_orphan_item(root, inode_id);
2525 if (!is_orphan && repair)
2526 ret = repair_inode_orphan_item_lowmem(root,
2527 path, inode_id);
2528 if (!is_orphan && (!repair || ret)) {
2529 err |= ORPHAN_ITEM;
2530 error("root %llu INODE[%llu] is orphan item",
2531 root->objectid, inode_id);
2532 }
2533 }
2534
2535 if (!nbytes && !no_holes && extent_end < isize) {
2536 if (repair)
2537 ret = punch_extent_hole(root, inode_id,
2538 extent_end, isize - extent_end);
2539 if (!repair || ret) {
2540 err |= NBYTES_ERROR;
2541 error(
2542 "root %llu INODE[%llu] size %llu should have a file extent hole",
2543 root->objectid, inode_id, isize);
2544 }
2545 }
2546
2547 if (nbytes != extent_size) {
2548 if (repair)
2549 ret = repair_inode_nbytes_lowmem(root, path,
2550 inode_id, extent_size);
2551 if (!repair || ret) {
2552 err |= NBYTES_ERROR;
2553 error(
2554 "root %llu INODE[%llu] nbytes %llu not equal to extent_size %llu",
2555 root->objectid, inode_id, nbytes,
2556 extent_size);
2557 }
2558 }
2559 }
2560
2561 if (err & LAST_ITEM)
2562 btrfs_next_item(root, path);
2563 return err;
2564 }
2565
2566 /*
2567 * Returns >0 Found error, not fatal, should continue
2568 * Returns <0 Fatal error, must exit the whole check
2569 * Returns 0 No errors found
2570 */
2571 static int process_one_leaf(struct btrfs_root *root, struct btrfs_path *path,
2572 struct node_refs *nrefs, int *level)
2573 {
2574 struct extent_buffer *cur = path->nodes[0];
2575 struct btrfs_key key;
2576 u64 cur_bytenr;
2577 u32 nritems;
2578 u64 first_ino = 0;
2579 int root_level = btrfs_header_level(root->node);
2580 int i;
2581 int ret = 0; /* Final return value */
2582 int err = 0; /* Positive error bitmap */
2583
2584 cur_bytenr = cur->start;
2585
2586 /* skip to first inode item or the first inode number change */
2587 nritems = btrfs_header_nritems(cur);
2588 for (i = 0; i < nritems; i++) {
2589 btrfs_item_key_to_cpu(cur, &key, i);
2590 if (i == 0)
2591 first_ino = key.objectid;
2592 if (key.type == BTRFS_INODE_ITEM_KEY ||
2593 (first_ino && first_ino != key.objectid))
2594 break;
2595 }
2596 if (i == nritems) {
2597 path->slots[0] = nritems;
2598 return 0;
2599 }
2600 path->slots[0] = i;
2601
2602 again:
2603 err |= check_inode_item(root, path);
2604
2605 /* modify cur since check_inode_item may change path */
2606 cur = path->nodes[0];
2607
2608 if (err & LAST_ITEM)
2609 goto out;
2610
2611 /* still have inode items in thie leaf */
2612 if (cur->start == cur_bytenr)
2613 goto again;
2614
2615 /*
2616 * we have switched to another leaf, above nodes may
2617 * have changed, here walk down the path, if a node
2618 * or leaf is shared, check whether we can skip this
2619 * node or leaf.
2620 */
2621 for (i = root_level; i >= 0; i--) {
2622 if (path->nodes[i]->start == nrefs->bytenr[i])
2623 continue;
2624
2625 ret = update_nodes_refs(root, path->nodes[i]->start,
2626 path->nodes[i], nrefs, i, 0);
2627 if (ret)
2628 goto out;
2629
2630 if (!nrefs->need_check[i]) {
2631 *level += 1;
2632 break;
2633 }
2634 }
2635
2636 for (i = 0; i < *level; i++) {
2637 free_extent_buffer(path->nodes[i]);
2638 path->nodes[i] = NULL;
2639 }
2640 out:
2641 err &= ~LAST_ITEM;
2642 if (err && !ret)
2643 ret = err;
2644 return ret;
2645 }
2646
2647 /*
2648 * @level if @level == -1 means extent data item
2649 * else normal treeblocl.
2650 */
2651 static int should_check_extent_strictly(struct btrfs_root *root,
2652 struct node_refs *nrefs, int level)
2653 {
2654 int root_level = btrfs_header_level(root->node);
2655
2656 if (level > root_level || level < -1)
2657 return 1;
2658 if (level == root_level)
2659 return 1;
2660 /*
2661 * if the upper node is marked full backref, it should contain shared
2662 * backref of the parent (except owner == root->objectid).
2663 */
2664 while (++level <= root_level)
2665 if (nrefs->refs[level] > 1)
2666 return 0;
2667
2668 return 1;
2669 }
2670
2671 static int check_extent_inline_ref(struct extent_buffer *eb,
2672 struct btrfs_key *key, struct btrfs_extent_inline_ref *iref)
2673 {
2674 int ret;
2675 u8 type = btrfs_extent_inline_ref_type(eb, iref);
2676
2677 switch (type) {
2678 case BTRFS_TREE_BLOCK_REF_KEY:
2679 case BTRFS_EXTENT_DATA_REF_KEY:
2680 case BTRFS_SHARED_BLOCK_REF_KEY:
2681 case BTRFS_SHARED_DATA_REF_KEY:
2682 ret = 0;
2683 break;
2684 default:
2685 error("extent[%llu %u %llu] has unknown ref type: %d",
2686 key->objectid, key->type, key->offset, type);
2687 ret = UNKNOWN_TYPE;
2688 break;
2689 }
2690
2691 return ret;
2692 }
2693
2694 /*
2695 * Check backrefs of a tree block given by @bytenr or @eb.
2696 *
2697 * @root: the root containing the @bytenr or @eb
2698 * @eb: tree block extent buffer, can be NULL
2699 * @bytenr: bytenr of the tree block to search
2700 * @level: tree level of the tree block
2701 * @owner: owner of the tree block
2702 *
2703 * Return >0 for any error found and output error message
2704 * Return 0 for no error found
2705 */
2706 static int check_tree_block_ref(struct btrfs_root *root,
2707 struct extent_buffer *eb, u64 bytenr,
2708 int level, u64 owner, struct node_refs *nrefs)
2709 {
2710 struct btrfs_key key;
2711 struct btrfs_root *extent_root = root->fs_info->extent_root;
2712 struct btrfs_path path;
2713 struct btrfs_extent_item *ei;
2714 struct btrfs_extent_inline_ref *iref;
2715 struct extent_buffer *leaf;
2716 unsigned long end;
2717 unsigned long ptr;
2718 int slot;
2719 int skinny_level;
2720 int root_level = btrfs_header_level(root->node);
2721 int type;
2722 u32 nodesize = root->fs_info->nodesize;
2723 u32 item_size;
2724 u64 offset;
2725 int found_ref = 0;
2726 int err = 0;
2727 int ret;
2728 int strict = 1;
2729 int parent = 0;
2730
2731 btrfs_init_path(&path);
2732 key.objectid = bytenr;
2733 if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA))
2734 key.type = BTRFS_METADATA_ITEM_KEY;
2735 else
2736 key.type = BTRFS_EXTENT_ITEM_KEY;
2737 key.offset = (u64)-1;
2738
2739 /* Search for the backref in extent tree */
2740 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2741 if (ret < 0) {
2742 err |= BACKREF_MISSING;
2743 goto out;
2744 }
2745 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
2746 if (ret) {
2747 err |= BACKREF_MISSING;
2748 goto out;
2749 }
2750
2751 leaf = path.nodes[0];
2752 slot = path.slots[0];
2753 btrfs_item_key_to_cpu(leaf, &key, slot);
2754
2755 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
2756
2757 if (key.type == BTRFS_METADATA_ITEM_KEY) {
2758 skinny_level = (int)key.offset;
2759 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2760 } else {
2761 struct btrfs_tree_block_info *info;
2762
2763 info = (struct btrfs_tree_block_info *)(ei + 1);
2764 skinny_level = btrfs_tree_block_level(leaf, info);
2765 iref = (struct btrfs_extent_inline_ref *)(info + 1);
2766 }
2767
2768
2769 if (eb) {
2770 u64 header_gen;
2771 u64 extent_gen;
2772
2773 /*
2774 * Due to the feature of shared tree blocks, if the upper node
2775 * is a fs root or shared node, the extent of checked node may
2776 * not be updated until the next CoW.
2777 */
2778 if (nrefs)
2779 strict = should_check_extent_strictly(root, nrefs,
2780 level);
2781 if (!(btrfs_extent_flags(leaf, ei) &
2782 BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
2783 error(
2784 "extent[%llu %u] backref type mismatch, missing bit: %llx",
2785 key.objectid, nodesize,
2786 BTRFS_EXTENT_FLAG_TREE_BLOCK);
2787 err = BACKREF_MISMATCH;
2788 }
2789 header_gen = btrfs_header_generation(eb);
2790 extent_gen = btrfs_extent_generation(leaf, ei);
2791 if (header_gen != extent_gen) {
2792 error(
2793 "extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu",
2794 key.objectid, nodesize, header_gen,
2795 extent_gen);
2796 err = BACKREF_MISMATCH;
2797 }
2798 if (level != skinny_level) {
2799 error(
2800 "extent[%llu %u] level mismatch, wanted: %u, have: %u",
2801 key.objectid, nodesize, level, skinny_level);
2802 err = BACKREF_MISMATCH;
2803 }
2804 if (!is_fstree(owner) && btrfs_extent_refs(leaf, ei) != 1) {
2805 error(
2806 "extent[%llu %u] is referred by other roots than %llu",
2807 key.objectid, nodesize, root->objectid);
2808 err = BACKREF_MISMATCH;
2809 }
2810 }
2811
2812 /*
2813 * Iterate the extent/metadata item to find the exact backref
2814 */
2815 item_size = btrfs_item_size_nr(leaf, slot);
2816 ptr = (unsigned long)iref;
2817 end = (unsigned long)ei + item_size;
2818
2819 while (ptr < end) {
2820 iref = (struct btrfs_extent_inline_ref *)ptr;
2821 type = btrfs_extent_inline_ref_type(leaf, iref);
2822 offset = btrfs_extent_inline_ref_offset(leaf, iref);
2823
2824 ret = check_extent_inline_ref(leaf, &key, iref);
2825 if (ret) {
2826 err |= ret;
2827 break;
2828 }
2829 if (type == BTRFS_TREE_BLOCK_REF_KEY) {
2830 if (offset == root->objectid)
2831 found_ref = 1;
2832 if (!strict && owner == offset)
2833 found_ref = 1;
2834 } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
2835 /*
2836 * Backref of tree reloc root points to itself, no need
2837 * to check backref any more.
2838 *
2839 * This may be an error of loop backref, but extent tree
2840 * checker should have already handled it.
2841 * Here we only need to avoid infinite iteration.
2842 */
2843 if (offset == bytenr) {
2844 found_ref = 1;
2845 } else {
2846 /*
2847 * Check if the backref points to valid
2848 * referencer
2849 */
2850 found_ref = !check_tree_block_ref(root, NULL,
2851 offset, level + 1, owner, NULL);
2852 }
2853 }
2854
2855 if (found_ref)
2856 break;
2857 ptr += btrfs_extent_inline_ref_size(type);
2858 }
2859
2860 /*
2861 * Inlined extent item doesn't have what we need, check
2862 * TREE_BLOCK_REF_KEY
2863 */
2864 if (!found_ref) {
2865 btrfs_release_path(&path);
2866 key.objectid = bytenr;
2867 key.type = BTRFS_TREE_BLOCK_REF_KEY;
2868 key.offset = root->objectid;
2869
2870 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2871 if (!ret)
2872 found_ref = 1;
2873 }
2874 /*
2875 * Finally check SHARED BLOCK REF, any found will be good
2876 * Here we're not doing comprehensive extent backref checking,
2877 * only need to ensure there is some extent referring to this
2878 * tree block.
2879 */
2880 if (!found_ref) {
2881 btrfs_release_path(&path);
2882 key.objectid = bytenr;
2883 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
2884 key.offset = (u64)-1;
2885
2886 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2887 if (ret < 0) {
2888 err |= BACKREF_MISSING;
2889 goto out;
2890 }
2891 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
2892 if (ret) {
2893 err |= BACKREF_MISSING;
2894 goto out;
2895 }
2896 found_ref = 1;
2897 }
2898 if (!found_ref)
2899 err |= BACKREF_MISSING;
2900 out:
2901 btrfs_release_path(&path);
2902 if (nrefs && strict &&
2903 level < root_level && nrefs->full_backref[level + 1])
2904 parent = nrefs->bytenr[level + 1];
2905 if (eb && (err & BACKREF_MISSING))
2906 error(
2907 "extent[%llu %u] backref lost (owner: %llu, level: %u) %s %llu",
2908 bytenr, nodesize, owner, level,
2909 parent ? "parent" : "root",
2910 parent ? parent : root->objectid);
2911 return err;
2912 }
2913
2914 /*
2915 * If @err contains BACKREF_MISSING then add extent of the
2916 * file_extent_data_item.
2917 *
2918 * Returns error bits after reapir.
2919 */
2920 static int repair_extent_data_item(struct btrfs_root *root,
2921 struct btrfs_path *pathp,
2922 struct node_refs *nrefs,
2923 int err)
2924 {
2925 struct btrfs_trans_handle *trans = NULL;
2926 struct btrfs_file_extent_item *fi;
2927 struct btrfs_key fi_key;
2928 struct btrfs_key key;
2929 struct btrfs_extent_item *ei;
2930 struct btrfs_path path;
2931 struct btrfs_root *extent_root = root->fs_info->extent_root;
2932 struct extent_buffer *eb;
2933 u64 size;
2934 u64 disk_bytenr;
2935 u64 num_bytes;
2936 u64 parent;
2937 u64 offset;
2938 u64 extent_offset;
2939 u64 file_offset;
2940 int generation;
2941 int slot;
2942 int need_insert = 0;
2943 int ret = 0;
2944
2945 eb = pathp->nodes[0];
2946 slot = pathp->slots[0];
2947 btrfs_item_key_to_cpu(eb, &fi_key, slot);
2948 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
2949
2950 if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
2951 btrfs_file_extent_disk_bytenr(eb, fi) == 0)
2952 return err;
2953
2954 file_offset = fi_key.offset;
2955 generation = btrfs_file_extent_generation(eb, fi);
2956 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
2957 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
2958 extent_offset = btrfs_file_extent_offset(eb, fi);
2959 offset = file_offset - extent_offset;
2960
2961 if (nrefs->full_backref[0])
2962 parent = btrfs_header_bytenr(eb);
2963 else
2964 parent = 0;
2965
2966 /* now repair only adds backref */
2967 if ((err & BACKREF_MISSING) == 0)
2968 return err;
2969
2970 /* search extent item */
2971 key.objectid = disk_bytenr;
2972 key.type = BTRFS_EXTENT_ITEM_KEY;
2973 key.offset = num_bytes;
2974
2975 btrfs_init_path(&path);
2976 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
2977 if (ret < 0) {
2978 ret = -EIO;
2979 goto out;
2980 }
2981 need_insert = ret;
2982
2983 ret = avoid_extents_overwrite(root->fs_info);
2984 if (ret)
2985 goto out;
2986 trans = btrfs_start_transaction(root, 1);
2987 if (IS_ERR(trans)) {
2988 ret = PTR_ERR(trans);
2989 trans = NULL;
2990 error("fail to start transaction %s", strerror(-ret));
2991 goto out;
2992 }
2993 /* insert an extent item */
2994 if (need_insert) {
2995 key.objectid = disk_bytenr;
2996 key.type = BTRFS_EXTENT_ITEM_KEY;
2997 key.offset = num_bytes;
2998 size = sizeof(*ei);
2999
3000 btrfs_release_path(&path);
3001 ret = btrfs_insert_empty_item(trans, extent_root, &path, &key,
3002 size);
3003 if (ret)
3004 goto out;
3005 eb = path.nodes[0];
3006 ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item);
3007
3008 btrfs_set_extent_refs(eb, ei, 0);
3009 btrfs_set_extent_generation(eb, ei, generation);
3010 btrfs_set_extent_flags(eb, ei, BTRFS_EXTENT_FLAG_DATA);
3011
3012 btrfs_mark_buffer_dirty(eb);
3013 ret = btrfs_update_block_group(extent_root, disk_bytenr,
3014 num_bytes, 1, 0);
3015 btrfs_release_path(&path);
3016 }
3017
3018 ret = btrfs_inc_extent_ref(trans, root, disk_bytenr, num_bytes, parent,
3019 root->objectid,
3020 parent ? BTRFS_FIRST_FREE_OBJECTID : fi_key.objectid,
3021 offset);
3022 if (ret) {
3023 error(
3024 "failed to increase extent data backref[%llu %llu] root %llu",
3025 disk_bytenr, num_bytes, root->objectid);
3026 goto out;
3027 } else {
3028 printf("Add one extent data backref [%llu %llu]\n",
3029 disk_bytenr, num_bytes);
3030 }
3031
3032 err &= ~BACKREF_MISSING;
3033 out:
3034 if (trans)
3035 btrfs_commit_transaction(trans, root);
3036 btrfs_release_path(&path);
3037 if (ret)
3038 error("can't repair root %llu extent data item[%llu %llu]",
3039 root->objectid, disk_bytenr, num_bytes);
3040 return err;
3041 }
3042
3043 /*
3044 * Check EXTENT_DATA item, mainly for its dbackref in extent tree
3045 *
3046 * Return >0 any error found and output error message
3047 * Return 0 for no error found
3048 */
3049 static int check_extent_data_item(struct btrfs_root *root,
3050 struct btrfs_path *pathp,
3051 struct node_refs *nrefs, int account_bytes)
3052 {
3053 struct btrfs_file_extent_item *fi;
3054 struct extent_buffer *eb = pathp->nodes[0];
3055 struct btrfs_path path;
3056 struct btrfs_root *extent_root = root->fs_info->extent_root;
3057 struct btrfs_key fi_key;
3058 struct btrfs_key dbref_key;
3059 struct extent_buffer *leaf;
3060 struct btrfs_extent_item *ei;
3061 struct btrfs_extent_inline_ref *iref;
3062 struct btrfs_extent_data_ref *dref;
3063 u64 owner;
3064 u64 disk_bytenr;
3065 u64 disk_num_bytes;
3066 u64 extent_num_bytes;
3067 u64 extent_flags;
3068 u64 offset;
3069 u32 item_size;
3070 unsigned long end;
3071 unsigned long ptr;
3072 int type;
3073 int found_dbackref = 0;
3074 int slot = pathp->slots[0];
3075 int err = 0;
3076 int ret;
3077 int strict;
3078
3079 btrfs_item_key_to_cpu(eb, &fi_key, slot);
3080 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
3081
3082 /* Nothing to check for hole and inline data extents */
3083 if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
3084 btrfs_file_extent_disk_bytenr(eb, fi) == 0)
3085 return 0;
3086
3087 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
3088 disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
3089 extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
3090 offset = btrfs_file_extent_offset(eb, fi);
3091
3092 /* Check unaligned disk_num_bytes and num_bytes */
3093 if (!IS_ALIGNED(disk_num_bytes, root->fs_info->sectorsize)) {
3094 error(
3095 "file extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
3096 fi_key.objectid, fi_key.offset, disk_num_bytes,
3097 root->fs_info->sectorsize);
3098 err |= BYTES_UNALIGNED;
3099 } else if (account_bytes) {
3100 data_bytes_allocated += disk_num_bytes;
3101 }
3102 if (!IS_ALIGNED(extent_num_bytes, root->fs_info->sectorsize)) {
3103 error(
3104 "file extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u",
3105 fi_key.objectid, fi_key.offset, extent_num_bytes,
3106 root->fs_info->sectorsize);
3107 err |= BYTES_UNALIGNED;
3108 } else if (account_bytes) {
3109 data_bytes_referenced += extent_num_bytes;
3110 }
3111 owner = btrfs_header_owner(eb);
3112
3113 /* Check the extent item of the file extent in extent tree */
3114 btrfs_init_path(&path);
3115 dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
3116 dbref_key.type = BTRFS_EXTENT_ITEM_KEY;
3117 dbref_key.offset = btrfs_file_extent_disk_num_bytes(eb, fi);
3118
3119 ret = btrfs_search_slot(NULL, extent_root, &dbref_key, &path, 0, 0);
3120 if (ret)
3121 goto out;
3122
3123 leaf = path.nodes[0];
3124 slot = path.slots[0];
3125 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
3126
3127 extent_flags = btrfs_extent_flags(leaf, ei);
3128
3129 if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) {
3130 error(
3131 "file extent[%llu %llu] root %llu owner %llu backref type mismatch, wanted bit: %llx",
3132 fi_key.objectid, fi_key.offset, root->objectid, owner,
3133 BTRFS_EXTENT_FLAG_DATA);
3134 err |= BACKREF_MISMATCH;
3135 }
3136
3137 /* Check data backref inside that extent item */
3138 item_size = btrfs_item_size_nr(leaf, path.slots[0]);
3139 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
3140 ptr = (unsigned long)iref;
3141 end = (unsigned long)ei + item_size;
3142 strict = should_check_extent_strictly(root, nrefs, -1);
3143
3144 while (ptr < end) {
3145 u64 ref_root;
3146 u64 ref_objectid;
3147 u64 ref_offset;
3148 bool match = false;
3149
3150 iref = (struct btrfs_extent_inline_ref *)ptr;
3151 type = btrfs_extent_inline_ref_type(leaf, iref);
3152 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
3153
3154 ret = check_extent_inline_ref(leaf, &dbref_key, iref);
3155 if (ret) {
3156 err |= ret;
3157 break;
3158 }
3159 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
3160 ref_root = btrfs_extent_data_ref_root(leaf, dref);
3161 ref_objectid = btrfs_extent_data_ref_objectid(leaf,
3162 dref);
3163 ref_offset = btrfs_extent_data_ref_offset(leaf, dref);
3164
3165 if (ref_objectid == fi_key.objectid &&
3166 ref_offset == fi_key.offset - offset)
3167 match = true;
3168 if (ref_root == root->objectid && match)
3169 found_dbackref = 1;
3170 else if (!strict && owner == ref_root && match)
3171 found_dbackref = 1;
3172 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
3173 found_dbackref = !check_tree_block_ref(root, NULL,
3174 btrfs_extent_inline_ref_offset(leaf, iref),
3175 0, owner, NULL);
3176 }
3177
3178 if (found_dbackref)
3179 break;
3180 ptr += btrfs_extent_inline_ref_size(type);
3181 }
3182
3183 if (!found_dbackref) {
3184 btrfs_release_path(&path);
3185
3186 /* Didn't find inlined data backref, try EXTENT_DATA_REF_KEY */
3187 dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
3188 dbref_key.type = BTRFS_EXTENT_DATA_REF_KEY;
3189 dbref_key.offset = hash_extent_data_ref(owner, fi_key.objectid,
3190 fi_key.offset - offset);
3191
3192 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
3193 &dbref_key, &path, 0, 0);
3194 if (!ret) {
3195 found_dbackref = 1;
3196 goto out;
3197 }
3198
3199 btrfs_release_path(&path);
3200
3201 /*
3202 * Neither inlined nor EXTENT_DATA_REF found, try
3203 * SHARED_DATA_REF as last chance.
3204 */
3205 dbref_key.objectid = disk_bytenr;
3206 dbref_key.type = BTRFS_SHARED_DATA_REF_KEY;
3207 dbref_key.offset = eb->start;
3208
3209 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
3210 &dbref_key, &path, 0, 0);
3211 if (!ret) {
3212 found_dbackref = 1;
3213 goto out;
3214 }
3215 }
3216
3217 out:
3218 if (!found_dbackref)
3219 err |= BACKREF_MISSING;
3220 btrfs_release_path(&path);
3221 if (err & BACKREF_MISSING) {
3222 error(
3223 "file extent[%llu %llu] root %llu owner %llu backref lost",
3224 fi_key.objectid, fi_key.offset, root->objectid, owner);
3225 }
3226 return err;
3227 }
3228
3229 /*
3230 * Check a block group item with its referener (chunk) and its used space
3231 * with extent/metadata item
3232 */
3233 static int check_block_group_item(struct btrfs_fs_info *fs_info,
3234 struct extent_buffer *eb, int slot)
3235 {
3236 struct btrfs_root *extent_root = fs_info->extent_root;
3237 struct btrfs_root *chunk_root = fs_info->chunk_root;
3238 struct btrfs_block_group_item *bi;
3239 struct btrfs_block_group_item bg_item;
3240 struct btrfs_path path;
3241 struct btrfs_key bg_key;
3242 struct btrfs_key chunk_key;
3243 struct btrfs_key extent_key;
3244 struct btrfs_chunk *chunk;
3245 struct extent_buffer *leaf;
3246 struct btrfs_extent_item *ei;
3247 u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
3248 u64 flags;
3249 u64 bg_flags;
3250 u64 used;
3251 u64 total = 0;
3252 int ret;
3253 int err = 0;
3254
3255 btrfs_item_key_to_cpu(eb, &bg_key, slot);
3256 bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
3257 read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item));
3258 used = btrfs_block_group_used(&bg_item);
3259 bg_flags = btrfs_block_group_flags(&bg_item);
3260
3261 chunk_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3262 chunk_key.type = BTRFS_CHUNK_ITEM_KEY;
3263 chunk_key.offset = bg_key.objectid;
3264
3265 btrfs_init_path(&path);
3266 /* Search for the referencer chunk */
3267 ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0);
3268 if (ret) {
3269 error(
3270 "block group[%llu %llu] did not find the related chunk item",
3271 bg_key.objectid, bg_key.offset);
3272 err |= REFERENCER_MISSING;
3273 } else {
3274 chunk = btrfs_item_ptr(path.nodes[0], path.slots[0],
3275 struct btrfs_chunk);
3276 if (btrfs_chunk_length(path.nodes[0], chunk) !=
3277 bg_key.offset) {
3278 error(
3279 "block group[%llu %llu] related chunk item length does not match",
3280 bg_key.objectid, bg_key.offset);
3281 err |= REFERENCER_MISMATCH;
3282 }
3283 }
3284 btrfs_release_path(&path);
3285
3286 /* Search from the block group bytenr */
3287 extent_key.objectid = bg_key.objectid;
3288 extent_key.type = 0;
3289 extent_key.offset = 0;
3290
3291 btrfs_init_path(&path);
3292 ret = btrfs_search_slot(NULL, extent_root, &extent_key, &path, 0, 0);
3293 if (ret < 0)
3294 goto out;
3295
3296 /* Iterate extent tree to account used space */
3297 while (1) {
3298 leaf = path.nodes[0];
3299
3300 /* Search slot can point to the last item beyond leaf nritems */
3301 if (path.slots[0] >= btrfs_header_nritems(leaf))
3302 goto next;
3303
3304 btrfs_item_key_to_cpu(leaf, &extent_key, path.slots[0]);
3305 if (extent_key.objectid >= bg_key.objectid + bg_key.offset)
3306 break;
3307
3308 if (extent_key.type != BTRFS_METADATA_ITEM_KEY &&
3309 extent_key.type != BTRFS_EXTENT_ITEM_KEY)
3310 goto next;
3311 if (extent_key.objectid < bg_key.objectid)
3312 goto next;
3313
3314 if (extent_key.type == BTRFS_METADATA_ITEM_KEY)
3315 total += nodesize;
3316 else
3317 total += extent_key.offset;
3318
3319 ei = btrfs_item_ptr(leaf, path.slots[0],
3320 struct btrfs_extent_item);
3321 flags = btrfs_extent_flags(leaf, ei);
3322 if (flags & BTRFS_EXTENT_FLAG_DATA) {
3323 if (!(bg_flags & BTRFS_BLOCK_GROUP_DATA)) {
3324 error(
3325 "bad extent[%llu, %llu) type mismatch with chunk",
3326 extent_key.objectid,
3327 extent_key.objectid + extent_key.offset);
3328 err |= CHUNK_TYPE_MISMATCH;
3329 }
3330 } else if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
3331 if (!(bg_flags & (BTRFS_BLOCK_GROUP_SYSTEM |
3332 BTRFS_BLOCK_GROUP_METADATA))) {
3333 error(
3334 "bad extent[%llu, %llu) type mismatch with chunk",
3335 extent_key.objectid,
3336 extent_key.objectid + nodesize);
3337 err |= CHUNK_TYPE_MISMATCH;
3338 }
3339 }
3340 next:
3341 ret = btrfs_next_item(extent_root, &path);
3342 if (ret)
3343 break;
3344 }
3345
3346 out:
3347 btrfs_release_path(&path);
3348
3349 if (total != used) {
3350 error(
3351 "block group[%llu %llu] used %llu but extent items used %llu",
3352 bg_key.objectid, bg_key.offset, used, total);
3353 err |= BG_ACCOUNTING_ERROR;
3354 }
3355 return err;
3356 }
3357
3358 /*
3359 * Get real tree block level for the case like shared block
3360 * Return >= 0 as tree level
3361 * Return <0 for error
3362 */
3363 static int query_tree_block_level(struct btrfs_fs_info *fs_info, u64 bytenr)
3364 {
3365 struct extent_buffer *eb;
3366 struct btrfs_path path;
3367 struct btrfs_key key;
3368 struct btrfs_extent_item *ei;
3369 u64 flags;
3370 u64 transid;
3371 u8 backref_level;
3372 u8 header_level;
3373 int ret;
3374
3375 /* Search extent tree for extent generation and level */
3376 key.objectid = bytenr;
3377 key.type = BTRFS_METADATA_ITEM_KEY;
3378 key.offset = (u64)-1;
3379
3380 btrfs_init_path(&path);
3381 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, &path, 0, 0);
3382 if (ret < 0)
3383 goto release_out;
3384 ret = btrfs_previous_extent_item(fs_info->extent_root, &path, bytenr);
3385 if (ret < 0)
3386 goto release_out;
3387 if (ret > 0) {
3388 ret = -ENOENT;
3389 goto release_out;
3390 }
3391
3392 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
3393 ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
3394 struct btrfs_extent_item);
3395 flags = btrfs_extent_flags(path.nodes[0], ei);
3396 if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
3397 ret = -ENOENT;
3398 goto release_out;
3399 }
3400
3401 /* Get transid for later read_tree_block() check */
3402 transid = btrfs_extent_generation(path.nodes[0], ei);
3403
3404 /* Get backref level as one source */
3405 if (key.type == BTRFS_METADATA_ITEM_KEY) {
3406 backref_level = key.offset;
3407 } else {
3408 struct btrfs_tree_block_info *info;
3409
3410 info = (struct btrfs_tree_block_info *)(ei + 1);
3411 backref_level = btrfs_tree_block_level(path.nodes[0], info);
3412 }
3413 btrfs_release_path(&path);
3414
3415 /* Get level from tree block as an alternative source */
3416 eb = read_tree_block(fs_info, bytenr, transid);
3417 if (!extent_buffer_uptodate(eb)) {
3418 free_extent_buffer(eb);
3419 return -EIO;
3420 }
3421 header_level = btrfs_header_level(eb);
3422 free_extent_buffer(eb);
3423
3424 if (header_level != backref_level)
3425 return -EIO;
3426 return header_level;
3427
3428 release_out:
3429 btrfs_release_path(&path);
3430 return ret;
3431 }
3432
3433 /*
3434 * Check if a tree block backref is valid (points to a valid tree block)
3435 * if level == -1, level will be resolved
3436 * Return >0 for any error found and print error message
3437 */
3438 static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id,
3439 u64 bytenr, int level)
3440 {
3441 struct btrfs_root *root;
3442 struct btrfs_key key;
3443 struct btrfs_path path;
3444 struct extent_buffer *eb;
3445 struct extent_buffer *node;
3446 u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
3447 int err = 0;
3448 int ret;
3449
3450 /* Query level for level == -1 special case */
3451 if (level == -1)
3452 level = query_tree_block_level(fs_info, bytenr);
3453 if (level < 0) {
3454 err |= REFERENCER_MISSING;
3455 goto out;
3456 }
3457
3458 key.objectid = root_id;
3459 key.type = BTRFS_ROOT_ITEM_KEY;
3460 key.offset = (u64)-1;
3461
3462 root = btrfs_read_fs_root(fs_info, &key);
3463 if (IS_ERR(root)) {
3464 err |= REFERENCER_MISSING;
3465 goto out;
3466 }
3467
3468 /* Read out the tree block to get item/node key */
3469 eb = read_tree_block(fs_info, bytenr, 0);
3470 if (!extent_buffer_uptodate(eb)) {
3471 err |= REFERENCER_MISSING;
3472 free_extent_buffer(eb);
3473 goto out;
3474 }
3475
3476 /* Empty tree, no need to check key */
3477 if (!btrfs_header_nritems(eb) && !level) {
3478 free_extent_buffer(eb);
3479 goto out;
3480 }
3481
3482 if (level)
3483 btrfs_node_key_to_cpu(eb, &key, 0);
3484 else
3485 btrfs_item_key_to_cpu(eb, &key, 0);
3486
3487 free_extent_buffer(eb);
3488
3489 btrfs_init_path(&path);
3490 path.lowest_level = level;
3491 /* Search with the first key, to ensure we can reach it */
3492 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3493 if (ret < 0) {
3494 err |= REFERENCER_MISSING;
3495 goto release_out;
3496 }
3497
3498 node = path.nodes[level];
3499 if (btrfs_header_bytenr(node) != bytenr) {
3500 error(
3501 "extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu",
3502 bytenr, nodesize, bytenr,
3503 btrfs_header_bytenr(node));
3504 err |= REFERENCER_MISMATCH;
3505 }
3506 if (btrfs_header_level(node) != level) {
3507 error(
3508 "extent [%llu %d] referencer level mismatch, wanted: %d, have: %d",
3509 bytenr, nodesize, level,
3510 btrfs_header_level(node));
3511 err |= REFERENCER_MISMATCH;
3512 }
3513
3514 release_out:
3515 btrfs_release_path(&path);
3516 out:
3517 if (err & REFERENCER_MISSING) {
3518 if (level < 0)
3519 error("extent [%llu %d] lost referencer (owner: %llu)",
3520 bytenr, nodesize, root_id);
3521 else
3522 error(
3523 "extent [%llu %d] lost referencer (owner: %llu, level: %u)",
3524 bytenr, nodesize, root_id, level);
3525 }
3526
3527 return err;
3528 }
3529
3530 /*
3531 * Check if tree block @eb is tree reloc root.
3532 * Return 0 if it's not or any problem happens
3533 * Return 1 if it's a tree reloc root
3534 */
3535 static int is_tree_reloc_root(struct btrfs_fs_info *fs_info,
3536 struct extent_buffer *eb)
3537 {
3538 struct btrfs_root *tree_reloc_root;
3539 struct btrfs_key key;
3540 u64 bytenr = btrfs_header_bytenr(eb);
3541 u64 owner = btrfs_header_owner(eb);
3542 int ret = 0;
3543
3544 key.objectid = BTRFS_TREE_RELOC_OBJECTID;
3545 key.offset = owner;
3546 key.type = BTRFS_ROOT_ITEM_KEY;
3547
3548 tree_reloc_root = btrfs_read_fs_root_no_cache(fs_info, &key);
3549 if (IS_ERR(tree_reloc_root))
3550 return 0;
3551
3552 if (bytenr == btrfs_header_bytenr(tree_reloc_root->node))
3553 ret = 1;
3554 btrfs_free_fs_root(tree_reloc_root);
3555 return ret;
3556 }
3557
3558 /*
3559 * Check referencer for shared block backref
3560 * If level == -1, this function will resolve the level.
3561 */
3562 static int check_shared_block_backref(struct btrfs_fs_info *fs_info,
3563 u64 parent, u64 bytenr, int level)
3564 {
3565 struct extent_buffer *eb;
3566 u32 nr;
3567 int found_parent = 0;
3568 int i;
3569
3570 eb = read_tree_block(fs_info, parent, 0);
3571 if (!extent_buffer_uptodate(eb))
3572 goto out;
3573
3574 if (level == -1)
3575 level = query_tree_block_level(fs_info, bytenr);
3576 if (level < 0)
3577 goto out;
3578
3579 /* It's possible it's a tree reloc root */
3580 if (parent == bytenr) {
3581 if (is_tree_reloc_root(fs_info, eb))
3582 found_parent = 1;
3583 goto out;
3584 }
3585
3586 if (level + 1 != btrfs_header_level(eb))
3587 goto out;
3588
3589 nr = btrfs_header_nritems(eb);
3590 for (i = 0; i < nr; i++) {
3591 if (bytenr == btrfs_node_blockptr(eb, i)) {
3592 found_parent = 1;
3593 break;
3594 }
3595 }
3596 out:
3597 free_extent_buffer(eb);
3598 if (!found_parent) {
3599 error(
3600 "shared extent[%llu %u] lost its parent (parent: %llu, level: %u)",
3601 bytenr, fs_info->nodesize, parent, level);
3602 return REFERENCER_MISSING;
3603 }
3604 return 0;
3605 }
3606
3607 /*
3608 * Check referencer for normal (inlined) data ref
3609 * If len == 0, it will be resolved by searching in extent tree
3610 */
3611 static int check_extent_data_backref(struct btrfs_fs_info *fs_info,
3612 u64 root_id, u64 objectid, u64 offset,
3613 u64 bytenr, u64 len, u32 count)
3614 {
3615 struct btrfs_root *root;
3616 struct btrfs_root *extent_root = fs_info->extent_root;
3617 struct btrfs_key key;
3618 struct btrfs_path path;
3619 struct extent_buffer *leaf;
3620 struct btrfs_file_extent_item *fi;
3621 u32 found_count = 0;
3622 int slot;
3623 int ret = 0;
3624
3625 if (!len) {
3626 key.objectid = bytenr;
3627 key.type = BTRFS_EXTENT_ITEM_KEY;
3628 key.offset = (u64)-1;
3629
3630 btrfs_init_path(&path);
3631 ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
3632 if (ret < 0)
3633 goto out;
3634 ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
3635 if (ret)
3636 goto out;
3637 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
3638 if (key.objectid != bytenr ||
3639 key.type != BTRFS_EXTENT_ITEM_KEY)
3640 goto out;
3641 len = key.offset;
3642 btrfs_release_path(&path);
3643 }
3644 key.objectid = root_id;
3645 key.type = BTRFS_ROOT_ITEM_KEY;
3646 key.offset = (u64)-1;
3647 btrfs_init_path(&path);
3648
3649 root = btrfs_read_fs_root(fs_info, &key);
3650 if (IS_ERR(root))
3651 goto out;
3652
3653 key.objectid = objectid;
3654 key.type = BTRFS_EXTENT_DATA_KEY;
3655 /*
3656 * It can be nasty as data backref offset is
3657 * file offset - file extent offset, which is smaller or
3658 * equal to original backref offset. The only special case is
3659 * overflow. So we need to special check and do further search.
3660 */
3661 key.offset = offset & (1ULL << 63) ? 0 : offset;
3662
3663 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
3664 if (ret < 0)
3665 goto out;
3666
3667 /*
3668 * Search afterwards to get correct one
3669 * NOTE: As we must do a comprehensive check on the data backref to
3670 * make sure the dref count also matches, we must iterate all file
3671 * extents for that inode.
3672 */
3673 while (1) {
3674 leaf = path.nodes[0];
3675 slot = path.slots[0];
3676
3677 if (slot >= btrfs_header_nritems(leaf) ||
3678 btrfs_header_owner(leaf) != root_id)
3679 goto next;
3680 /*
3681 * For tree blocks have been relocated, data backref are
3682 * shared instead of keyed. Do not account it.
3683 */
3684 if (btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
3685 /*
3686 * skip the leaf to speed up.
3687 */
3688 slot = btrfs_header_nritems(leaf);
3689 goto next;
3690 }
3691
3692 btrfs_item_key_to_cpu(leaf, &key, slot);
3693 if (key.objectid != objectid ||
3694 key.type != BTRFS_EXTENT_DATA_KEY)
3695 break;
3696 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
3697 /*
3698 * Except normal disk bytenr and disk num bytes, we still
3699 * need to do extra check on dbackref offset as
3700 * dbackref offset = file_offset - file_extent_offset
3701 *
3702 * Also, we must check the leaf owner.
3703 * In case of shared tree blocks (snapshots) we can inherit
3704 * leaves from source snapshot.
3705 * In that case, reference from source snapshot should not
3706 * count.
3707 */
3708 if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr &&
3709 btrfs_file_extent_disk_num_bytes(leaf, fi) == len &&
3710 (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) ==
3711 offset && btrfs_header_owner(leaf) == root_id)
3712 found_count++;
3713
3714 next:
3715 ret = btrfs_next_item(root, &path);
3716 if (ret)
3717 break;
3718 }
3719 out:
3720 btrfs_release_path(&path);
3721 if (found_count != count) {
3722 error(
3723 "extent[%llu, %llu] referencer count mismatch (root: %llu, owner: %llu, offset: %llu) wanted: %u, have: %u",
3724 bytenr, len, root_id, objectid, offset, count,
3725 found_count);
3726 return REFERENCER_MISSING;
3727 }
3728 return 0;
3729 }
3730
3731 /*
3732 * Check if the referencer of a shared data backref exists
3733 */
3734 static int check_shared_data_backref(struct btrfs_fs_info *fs_info,
3735 u64 parent, u64 bytenr)
3736 {
3737 struct extent_buffer *eb;
3738 struct btrfs_key key;
3739 struct btrfs_file_extent_item *fi;
3740 u32 nr;
3741 int found_parent = 0;
3742 int i;
3743
3744 eb = read_tree_block(fs_info, parent, 0);
3745 if (!extent_buffer_uptodate(eb))
3746 goto out;
3747
3748 nr = btrfs_header_nritems(eb);
3749 for (i = 0; i < nr; i++) {
3750 btrfs_item_key_to_cpu(eb, &key, i);
3751 if (key.type != BTRFS_EXTENT_DATA_KEY)
3752 continue;
3753
3754 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
3755 if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE)
3756 continue;
3757
3758 if (btrfs_file_extent_disk_bytenr(eb, fi) == bytenr) {
3759 found_parent = 1;
3760 break;
3761 }
3762 }
3763
3764 out:
3765 free_extent_buffer(eb);
3766 if (!found_parent) {
3767 error("shared extent %llu referencer lost (parent: %llu)",
3768 bytenr, parent);
3769 return REFERENCER_MISSING;
3770 }
3771 return 0;
3772 }
3773
3774 /*
3775 * Only delete backref if REFERENCER_MISSING now
3776 *
3777 * Returns <0 the extent was deleted
3778 * Returns >0 the backref was deleted but extent still exists, returned value
3779 * means error after repair
3780 * Returns 0 nothing happened
3781 */
3782 static int repair_extent_item(struct btrfs_root *root, struct btrfs_path *path,
3783 u64 bytenr, u64 num_bytes, u64 parent, u64 root_objectid,
3784 u64 owner, u64 offset, int err)
3785 {
3786 struct btrfs_trans_handle *trans;
3787 struct btrfs_root *extent_root = root->fs_info->extent_root;
3788 struct btrfs_key old_key;
3789 int freed = 0;
3790 int ret;
3791
3792 btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]);
3793
3794 if ((err & (REFERENCER_MISSING | REFERENCER_MISMATCH)) == 0)
3795 return err;
3796
3797 ret = avoid_extents_overwrite(root->fs_info);
3798 if (ret)
3799 return err;
3800
3801 trans = btrfs_start_transaction(extent_root, 1);
3802 if (IS_ERR(trans)) {
3803 ret = PTR_ERR(trans);
3804 error("fail to start transaction %s", strerror(-ret));
3805 /* nothing happened */
3806 ret = 0;
3807 goto out;
3808 }
3809 /* delete the backref */
3810 ret = btrfs_free_extent(trans, root->fs_info->fs_root, bytenr,
3811 num_bytes, parent, root_objectid, owner, offset);
3812 if (!ret) {
3813 freed = 1;
3814 err &= ~REFERENCER_MISSING;
3815 printf("Delete backref in extent [%llu %llu]\n",
3816 bytenr, num_bytes);
3817 } else {
3818 error("fail to delete backref in extent [%llu %llu]",
3819 bytenr, num_bytes);
3820 }
3821 btrfs_commit_transaction(trans, extent_root);
3822
3823 /* btrfs_free_extent may delete the extent */
3824 btrfs_release_path(path);
3825 ret = btrfs_search_slot(NULL, root, &old_key, path, 0, 0);
3826 if (ret)
3827 ret = -ENOENT;
3828 else if (freed)
3829 ret = err;
3830 out:
3831 return ret;
3832 }
3833
3834 /*
3835 * This function will check a given extent item, including its backref and
3836 * itself (like crossing stripe boundary and type)
3837 *
3838 * Since we don't use extent_record anymore, introduce new error bit
3839 */
3840 static int check_extent_item(struct btrfs_fs_info *fs_info,
3841 struct btrfs_path *path)
3842 {
3843 struct btrfs_extent_item *ei;
3844 struct btrfs_extent_inline_ref *iref;
3845 struct btrfs_extent_data_ref *dref;
3846 struct extent_buffer *eb = path->nodes[0];
3847 unsigned long end;
3848 unsigned long ptr;
3849 int slot = path->slots[0];
3850 int type;
3851 u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
3852 u32 item_size = btrfs_item_size_nr(eb, slot);
3853 u64 flags;
3854 u64 offset;
3855 u64 parent;
3856 u64 num_bytes;
3857 u64 root_objectid;
3858 u64 owner;
3859 u64 owner_offset;
3860 int metadata = 0;
3861 int level;
3862 struct btrfs_key key;
3863 int ret;
3864 int err = 0;
3865
3866 btrfs_item_key_to_cpu(eb, &key, slot);
3867 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
3868 bytes_used += key.offset;
3869 num_bytes = key.offset;
3870 } else {
3871 bytes_used += nodesize;
3872 num_bytes = nodesize;
3873 }
3874
3875 if (item_size < sizeof(*ei)) {
3876 /*
3877 * COMPAT_EXTENT_TREE_V0 case, but it's already a super
3878 * old thing when on disk format is still un-determined.
3879 * No need to care about it anymore
3880 */
3881 error("unsupported COMPAT_EXTENT_TREE_V0 detected");
3882 return -ENOTTY;
3883 }
3884
3885 ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
3886 flags = btrfs_extent_flags(eb, ei);
3887
3888 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
3889 metadata = 1;
3890 if (metadata && check_crossing_stripes(global_info, key.objectid,
3891 eb->len)) {
3892 error("bad metadata [%llu, %llu) crossing stripe boundary",
3893 key.objectid, key.objectid + nodesize);
3894 err |= CROSSING_STRIPE_BOUNDARY;
3895 }
3896
3897 ptr = (unsigned long)(ei + 1);
3898
3899 if (metadata && key.type == BTRFS_EXTENT_ITEM_KEY) {
3900 /* Old EXTENT_ITEM metadata */
3901 struct btrfs_tree_block_info *info;
3902
3903 info = (struct btrfs_tree_block_info *)ptr;
3904 level = btrfs_tree_block_level(eb, info);
3905 ptr += sizeof(struct btrfs_tree_block_info);
3906 } else {
3907 /* New METADATA_ITEM */
3908 level = key.offset;
3909 }
3910 end = (unsigned long)ei + item_size;
3911
3912 next:
3913 /* Reached extent item end normally */
3914 if (ptr == end)
3915 goto out;
3916
3917 /* Beyond extent item end, wrong item size */
3918 if (ptr > end) {
3919 err |= ITEM_SIZE_MISMATCH;
3920 error("extent item at bytenr %llu slot %d has wrong size",
3921 eb->start, slot);
3922 goto out;
3923 }
3924
3925 parent = 0;
3926 root_objectid = 0;
3927 owner = 0;
3928 owner_offset = 0;
3929 /* Now check every backref in this extent item */
3930 iref = (struct btrfs_extent_inline_ref *)ptr;
3931 type = btrfs_extent_inline_ref_type(eb, iref);
3932 offset = btrfs_extent_inline_ref_offset(eb, iref);
3933 switch (type) {
3934 case BTRFS_TREE_BLOCK_REF_KEY:
3935 root_objectid = offset;
3936 owner = level;
3937 ret = check_tree_block_backref(fs_info, offset, key.objectid,
3938 level);
3939 err |= ret;
3940 break;
3941 case BTRFS_SHARED_BLOCK_REF_KEY:
3942 parent = offset;
3943 ret = check_shared_block_backref(fs_info, offset, key.objectid,
3944 level);
3945 err |= ret;
3946 break;
3947 case BTRFS_EXTENT_DATA_REF_KEY:
3948 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
3949 root_objectid = btrfs_extent_data_ref_root(eb, dref);
3950 owner = btrfs_extent_data_ref_objectid(eb, dref);
3951 owner_offset = btrfs_extent_data_ref_offset(eb, dref);
3952 ret = check_extent_data_backref(fs_info, root_objectid, owner,
3953 owner_offset, key.objectid, key.offset,
3954 btrfs_extent_data_ref_count(eb, dref));
3955 err |= ret;
3956 break;
3957 case BTRFS_SHARED_DATA_REF_KEY:
3958 parent = offset;
3959 ret = check_shared_data_backref(fs_info, offset, key.objectid);
3960 err |= ret;
3961 break;
3962 default:
3963 error("extent[%llu %d %llu] has unknown ref type: %d",
3964 key.objectid, key.type, key.offset, type);
3965 ret = UNKNOWN_TYPE;
3966 err |= ret;
3967 goto out;
3968 }
3969
3970 if (err && repair) {
3971 ret = repair_extent_item(fs_info->extent_root, path,
3972 key.objectid, num_bytes, parent, root_objectid,
3973 owner, owner_offset, ret);
3974 if (ret < 0)
3975 goto out;
3976 if (ret) {
3977 goto next;
3978 err = ret;
3979 }
3980 }
3981
3982 ptr += btrfs_extent_inline_ref_size(type);
3983 goto next;
3984
3985 out:
3986 return err;
3987 }
3988
3989 /*
3990 * Check if a dev extent item is referred correctly by its chunk
3991 */
3992 static int check_dev_extent_item(struct btrfs_fs_info *fs_info,
3993 struct extent_buffer *eb, int slot)
3994 {
3995 struct btrfs_root *chunk_root = fs_info->chunk_root;
3996 struct btrfs_dev_extent *ptr;
3997 struct btrfs_path path;
3998 struct btrfs_key chunk_key;
3999 struct btrfs_key devext_key;
4000 struct btrfs_chunk *chunk;
4001 struct extent_buffer *l;
4002 int num_stripes;
4003 u64 length;
4004 int i;
4005 int found_chunk = 0;
4006 int ret;
4007
4008 btrfs_item_key_to_cpu(eb, &devext_key, slot);
4009 ptr = btrfs_item_ptr(eb, slot, struct btrfs_dev_extent);
4010 length = btrfs_dev_extent_length(eb, ptr);
4011
4012 chunk_key.objectid = btrfs_dev_extent_chunk_objectid(eb, ptr);
4013 chunk_key.type = BTRFS_CHUNK_ITEM_KEY;
4014 chunk_key.offset = btrfs_dev_extent_chunk_offset(eb, ptr);
4015
4016 btrfs_init_path(&path);
4017 ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0);
4018 if (ret)
4019 goto out;
4020
4021 l = path.nodes[0];
4022 chunk = btrfs_item_ptr(l, path.slots[0], struct btrfs_chunk);
4023 ret = btrfs_check_chunk_valid(fs_info, l, chunk, path.slots[0],
4024 chunk_key.offset);
4025 if (ret < 0)
4026 goto out;
4027
4028 if (btrfs_stripe_length(fs_info, l, chunk) != length)
4029 goto out;
4030
4031 num_stripes = btrfs_chunk_num_stripes(l, chunk);
4032 for (i = 0; i < num_stripes; i++) {
4033 u64 devid = btrfs_stripe_devid_nr(l, chunk, i);
4034 u64 offset = btrfs_stripe_offset_nr(l, chunk, i);
4035
4036 if (devid == devext_key.objectid &&
4037 offset == devext_key.offset) {
4038 found_chunk = 1;
4039 break;
4040 }
4041 }
4042 out:
4043 btrfs_release_path(&path);
4044 if (!found_chunk) {
4045 error(
4046 "device extent[%llu, %llu, %llu] did not find the related chunk",
4047 devext_key.objectid, devext_key.offset, length);
4048 return REFERENCER_MISSING;
4049 }
4050 return 0;
4051 }
4052
4053 /*
4054 * Check if the used space is correct with the dev item
4055 */
4056 static int check_dev_item(struct btrfs_fs_info *fs_info,
4057 struct extent_buffer *eb, int slot)
4058 {
4059 struct btrfs_root *dev_root = fs_info->dev_root;
4060 struct btrfs_dev_item *dev_item;
4061 struct btrfs_path path;
4062 struct btrfs_key key;
4063 struct btrfs_dev_extent *ptr;
4064 u64 total_bytes;
4065 u64 dev_id;
4066 u64 used;
4067 u64 total = 0;
4068 int ret;
4069
4070 dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
4071 dev_id = btrfs_device_id(eb, dev_item);
4072 used = btrfs_device_bytes_used(eb, dev_item);
4073 total_bytes = btrfs_device_total_bytes(eb, dev_item);
4074
4075 key.objectid = dev_id;
4076 key.type = BTRFS_DEV_EXTENT_KEY;
4077 key.offset = 0;
4078
4079 btrfs_init_path(&path);
4080 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
4081 if (ret < 0) {
4082 btrfs_item_key_to_cpu(eb, &key, slot);
4083 error("cannot find any related dev extent for dev[%llu, %u, %llu]",
4084 key.objectid, key.type, key.offset);
4085 btrfs_release_path(&path);
4086 return REFERENCER_MISSING;
4087 }
4088
4089 /* Iterate dev_extents to calculate the used space of a device */
4090 while (1) {
4091 if (path.slots[0] >= btrfs_header_nritems(path.nodes[0]))
4092 goto next;
4093
4094 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
4095 if (key.objectid > dev_id)
4096 break;
4097 if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id)
4098 goto next;
4099
4100 ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
4101 struct btrfs_dev_extent);
4102 total += btrfs_dev_extent_length(path.nodes[0], ptr);
4103 next:
4104 ret = btrfs_next_item(dev_root, &path);
4105 if (ret)
4106 break;
4107 }
4108 btrfs_release_path(&path);
4109
4110 if (used != total) {
4111 btrfs_item_key_to_cpu(eb, &key, slot);
4112 error(
4113 "Dev extent's total-byte %llu is not equal to bytes-used %llu in dev[%llu, %u, %llu]",
4114 total, used, BTRFS_ROOT_TREE_OBJECTID,
4115 BTRFS_DEV_EXTENT_KEY, dev_id);
4116 return ACCOUNTING_MISMATCH;
4117 }
4118 check_dev_size_alignment(dev_id, total_bytes, fs_info->sectorsize);
4119
4120 return 0;
4121 }
4122
4123 /*
4124 * Check a chunk item.
4125 * Including checking all referred dev_extents and block group
4126 */
4127 static int check_chunk_item(struct btrfs_fs_info *fs_info,
4128 struct extent_buffer *eb, int slot)
4129 {
4130 struct btrfs_root *extent_root = fs_info->extent_root;
4131 struct btrfs_root *dev_root = fs_info->dev_root;
4132 struct btrfs_path path;
4133 struct btrfs_key chunk_key;
4134 struct btrfs_key bg_key;
4135 struct btrfs_key devext_key;
4136 struct btrfs_chunk *chunk;
4137 struct extent_buffer *leaf;
4138 struct btrfs_block_group_item *bi;
4139 struct btrfs_block_group_item bg_item;
4140 struct btrfs_dev_extent *ptr;
4141 u64 length;
4142 u64 chunk_end;
4143 u64 stripe_len;
4144 u64 type;
4145 int num_stripes;
4146 u64 offset;
4147 u64 objectid;
4148 int i;
4149 int ret;
4150 int err = 0;
4151
4152 btrfs_item_key_to_cpu(eb, &chunk_key, slot);
4153 chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
4154 length = btrfs_chunk_length(eb, chunk);
4155 chunk_end = chunk_key.offset + length;
4156 ret = btrfs_check_chunk_valid(fs_info, eb, chunk, slot,
4157 chunk_key.offset);
4158 if (ret < 0) {
4159 error("chunk[%llu %llu) is invalid", chunk_key.offset,
4160 chunk_end);
4161 err |= BYTES_UNALIGNED | UNKNOWN_TYPE;
4162 goto out;
4163 }
4164 type = btrfs_chunk_type(eb, chunk);
4165
4166 bg_key.objectid = chunk_key.offset;
4167 bg_key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
4168 bg_key.offset = length;
4169
4170 btrfs_init_path(&path);
4171 ret = btrfs_search_slot(NULL, extent_root, &bg_key, &path, 0, 0);
4172 if (ret) {
4173 error(
4174 "chunk[%llu %llu) did not find the related block group item",
4175 chunk_key.offset, chunk_end);
4176 err |= REFERENCER_MISSING;
4177 } else{
4178 leaf = path.nodes[0];
4179 bi = btrfs_item_ptr(leaf, path.slots[0],
4180 struct btrfs_block_group_item);
4181 read_extent_buffer(leaf, &bg_item, (unsigned long)bi,
4182 sizeof(bg_item));
4183 if (btrfs_block_group_flags(&bg_item) != type) {
4184 error(
4185 "chunk[%llu %llu) related block group item flags mismatch, wanted: %llu, have: %llu",
4186 chunk_key.offset, chunk_end, type,
4187 btrfs_block_group_flags(&bg_item));
4188 err |= REFERENCER_MISSING;
4189 }
4190 }
4191
4192 num_stripes = btrfs_chunk_num_stripes(eb, chunk);
4193 stripe_len = btrfs_stripe_length(fs_info, eb, chunk);
4194 for (i = 0; i < num_stripes; i++) {
4195 btrfs_release_path(&path);
4196 btrfs_init_path(&path);
4197 devext_key.objectid = btrfs_stripe_devid_nr(eb, chunk, i);
4198 devext_key.type = BTRFS_DEV_EXTENT_KEY;
4199 devext_key.offset = btrfs_stripe_offset_nr(eb, chunk, i);
4200
4201 ret = btrfs_search_slot(NULL, dev_root, &devext_key, &path,
4202 0, 0);
4203 if (ret)
4204 goto not_match_dev;
4205
4206 leaf = path.nodes[0];
4207 ptr = btrfs_item_ptr(leaf, path.slots[0],
4208 struct btrfs_dev_extent);
4209 objectid = btrfs_dev_extent_chunk_objectid(leaf, ptr);
4210 offset = btrfs_dev_extent_chunk_offset(leaf, ptr);
4211 if (objectid != chunk_key.objectid ||
4212 offset != chunk_key.offset ||
4213 btrfs_dev_extent_length(leaf, ptr) != stripe_len)
4214 goto not_match_dev;
4215 continue;
4216 not_match_dev:
4217 err |= BACKREF_MISSING;
4218 error(
4219 "chunk[%llu %llu) stripe %d did not find the related dev extent",
4220 chunk_key.objectid, chunk_end, i);
4221 continue;
4222 }
4223 btrfs_release_path(&path);
4224 out:
4225 return err;
4226 }
4227
4228 /*
4229 * Add block group item to the extent tree if @err contains REFERENCER_MISSING.
4230 * FIXME: We still need to repair error of dev_item.
4231 *
4232 * Returns error after repair.
4233 */
4234 static int repair_chunk_item(struct btrfs_root *chunk_root,
4235 struct btrfs_path *path, int err)
4236 {
4237 struct btrfs_chunk *chunk;
4238 struct btrfs_key chunk_key;
4239 struct extent_buffer *eb = path->nodes[0];
4240 struct btrfs_root *extent_root = chunk_root->fs_info->extent_root;
4241 struct btrfs_trans_handle *trans;
4242 u64 length;
4243 int slot = path->slots[0];
4244 u64 type;
4245 int ret = 0;
4246
4247 btrfs_item_key_to_cpu(eb, &chunk_key, slot);
4248 if (chunk_key.type != BTRFS_CHUNK_ITEM_KEY)
4249 return err;
4250 chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
4251 type = btrfs_chunk_type(path->nodes[0], chunk);
4252 length = btrfs_chunk_length(eb, chunk);
4253
4254 /* now repair only adds block group */
4255 if ((err & REFERENCER_MISSING) == 0)
4256 return err;
4257
4258 ret = avoid_extents_overwrite(chunk_root->fs_info);
4259 if (ret)
4260 return ret;
4261
4262 trans = btrfs_start_transaction(extent_root, 1);
4263 if (IS_ERR(trans)) {
4264 ret = PTR_ERR(trans);
4265 error("fail to start transaction %s", strerror(-ret));
4266 return ret;
4267 }
4268
4269 ret = btrfs_make_block_group(trans, chunk_root->fs_info, 0, type,
4270 chunk_key.offset, length);
4271 if (ret) {
4272 error("fail to add block group item [%llu %llu]",
4273 chunk_key.offset, length);
4274 } else {
4275 err &= ~REFERENCER_MISSING;
4276 printf("Added block group item[%llu %llu]\n", chunk_key.offset,
4277 length);
4278 }
4279
4280 btrfs_commit_transaction(trans, extent_root);
4281 if (ret)
4282 error("fail to repair item(s) related to chunk item [%llu %llu]",
4283 chunk_key.objectid, chunk_key.offset);
4284 return err;
4285 }
4286
4287 static int delete_extent_tree_item(struct btrfs_root *root,
4288 struct btrfs_path *path)
4289 {
4290 struct btrfs_key key;
4291 struct btrfs_trans_handle *trans;
4292 int ret = 0;
4293
4294 ret = avoid_extents_overwrite(root->fs_info);
4295 if (ret)
4296 return ret;
4297 trans = btrfs_start_transaction(root, 1);
4298 if (IS_ERR(trans)) {
4299 ret = PTR_ERR(trans);
4300 error("fail to start transaction %s", strerror(-ret));
4301 goto out;
4302 }
4303 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4304 btrfs_release_path(path);
4305 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
4306 if (ret) {
4307 ret = -ENOENT;
4308 goto out;
4309 }
4310
4311 ret = btrfs_del_item(trans, root, path);
4312 if (ret)
4313 goto out;
4314
4315 if (path->slots[0] == 0)
4316 btrfs_prev_leaf(root, path);
4317 else
4318 path->slots[0]--;
4319 out:
4320 btrfs_commit_transaction(trans, root);
4321 if (ret)
4322 error("failed to delete root %llu item[%llu, %u, %llu]",
4323 root->objectid, key.objectid, key.type, key.offset);
4324 else
4325 printf("Deleted root %llu item[%llu, %u, %llu]\n",
4326 root->objectid, key.objectid, key.type, key.offset);
4327 return ret;
4328 }
4329
4330 /*
4331 * Main entry function to check known items and update related accounting info
4332 */
4333 static int check_leaf_items(struct btrfs_root *root, struct btrfs_path *path,
4334 struct node_refs *nrefs, int account_bytes)
4335 {
4336 struct btrfs_fs_info *fs_info = root->fs_info;
4337 struct btrfs_key key;
4338 struct extent_buffer *eb;
4339 int slot;
4340 int type;
4341 struct btrfs_extent_data_ref *dref;
4342 int ret = 0;
4343 int err = 0;
4344
4345 again:
4346 eb = path->nodes[0];
4347 slot = path->slots[0];
4348 if (slot >= btrfs_header_nritems(eb)) {
4349 if (slot == 0) {
4350 error("empty leaf [%llu %u] root %llu", eb->start,
4351 root->fs_info->nodesize, root->objectid);
4352 err |= EIO;
4353 }
4354 goto out;
4355 }
4356
4357 btrfs_item_key_to_cpu(eb, &key, slot);
4358 type = key.type;
4359
4360 switch (type) {
4361 case BTRFS_EXTENT_DATA_KEY:
4362 ret = check_extent_data_item(root, path, nrefs, account_bytes);
4363 if (repair && ret)
4364 ret = repair_extent_data_item(root, path, nrefs, ret);
4365 err |= ret;
4366 break;
4367 case BTRFS_BLOCK_GROUP_ITEM_KEY:
4368 ret = check_block_group_item(fs_info, eb, slot);
4369 if (repair &&
4370 ret & REFERENCER_MISSING)
4371 ret = delete_extent_tree_item(root, path);
4372 err |= ret;
4373 break;
4374 case BTRFS_DEV_ITEM_KEY:
4375 ret = check_dev_item(fs_info, eb, slot);
4376 err |= ret;
4377 break;
4378 case BTRFS_CHUNK_ITEM_KEY:
4379 ret = check_chunk_item(fs_info, eb, slot);
4380 if (repair && ret)
4381 ret = repair_chunk_item(root, path, ret);
4382 err |= ret;
4383 break;
4384 case BTRFS_DEV_EXTENT_KEY:
4385 ret = check_dev_extent_item(fs_info, eb, slot);
4386 err |= ret;
4387 break;
4388 case BTRFS_EXTENT_ITEM_KEY:
4389 case BTRFS_METADATA_ITEM_KEY:
4390 ret = check_extent_item(fs_info, path);
4391 err |= ret;
4392 break;
4393 case BTRFS_EXTENT_CSUM_KEY:
4394 total_csum_bytes += btrfs_item_size_nr(eb, slot);
4395 err |= ret;
4396 break;
4397 case BTRFS_TREE_BLOCK_REF_KEY:
4398 ret = check_tree_block_backref(fs_info, key.offset,
4399 key.objectid, -1);
4400 if (repair &&
4401 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4402 ret = delete_extent_tree_item(root, path);
4403 err |= ret;
4404 break;
4405 case BTRFS_EXTENT_DATA_REF_KEY:
4406 dref = btrfs_item_ptr(eb, slot, struct btrfs_extent_data_ref);
4407 ret = check_extent_data_backref(fs_info,
4408 btrfs_extent_data_ref_root(eb, dref),
4409 btrfs_extent_data_ref_objectid(eb, dref),
4410 btrfs_extent_data_ref_offset(eb, dref),
4411 key.objectid, 0,
4412 btrfs_extent_data_ref_count(eb, dref));
4413 if (repair &&
4414 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4415 ret = delete_extent_tree_item(root, path);
4416 err |= ret;
4417 break;
4418 case BTRFS_SHARED_BLOCK_REF_KEY:
4419 ret = check_shared_block_backref(fs_info, key.offset,
4420 key.objectid, -1);
4421 if (repair &&
4422 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4423 ret = delete_extent_tree_item(root, path);
4424 err |= ret;
4425 break;
4426 case BTRFS_SHARED_DATA_REF_KEY:
4427 ret = check_shared_data_backref(fs_info, key.offset,
4428 key.objectid);
4429 if (repair &&
4430 ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
4431 ret = delete_extent_tree_item(root, path);
4432 err |= ret;
4433 break;
4434 default:
4435 break;
4436 }
4437
4438 ++path->slots[0];
4439 goto again;
4440 out:
4441 return err;
4442 }
4443
4444 /*
4445 * @trans just for lowmem repair mode
4446 * @check all if not 0 then check all tree block backrefs and items
4447 * 0 then just check relationship of items in fs tree(s)
4448 *
4449 * Returns >0 Found error, should continue
4450 * Returns <0 Fatal error, must exit the whole check
4451 * Returns 0 No errors found
4452 */
4453 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
4454 int *level, struct node_refs *nrefs, int check_all)
4455 {
4456 enum btrfs_tree_block_status status;
4457 u64 bytenr;
4458 u64 ptr_gen;
4459 struct btrfs_fs_info *fs_info = root->fs_info;
4460 struct extent_buffer *next;
4461 struct extent_buffer *cur;
4462 int ret;
4463 int err = 0;
4464 int check;
4465 int account_file_data = 0;
4466
4467 WARN_ON(*level < 0);
4468 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4469
4470 ret = update_nodes_refs(root, btrfs_header_bytenr(path->nodes[*level]),
4471 path->nodes[*level], nrefs, *level, check_all);
4472 if (ret < 0)
4473 return ret;
4474
4475 while (*level >= 0) {
4476 WARN_ON(*level < 0);
4477 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4478 cur = path->nodes[*level];
4479 bytenr = btrfs_header_bytenr(cur);
4480 check = nrefs->need_check[*level];
4481
4482 if (btrfs_header_level(cur) != *level)
4483 WARN_ON(1);
4484 /*
4485 * Update bytes accounting and check tree block ref
4486 * NOTE: Doing accounting and check before checking nritems
4487 * is necessary because of empty node/leaf.
4488 */
4489 if ((check_all && !nrefs->checked[*level]) ||
4490 (!check_all && nrefs->need_check[*level])) {
4491 ret = check_tree_block_ref(root, cur,
4492 btrfs_header_bytenr(cur), btrfs_header_level(cur),
4493 btrfs_header_owner(cur), nrefs);
4494
4495 if (repair && ret)
4496 ret = repair_tree_block_ref(root,
4497 path->nodes[*level], nrefs, *level, ret);
4498 err |= ret;
4499
4500 if (check_all && nrefs->need_check[*level] &&
4501 nrefs->refs[*level]) {
4502 account_bytes(root, path, *level);
4503 account_file_data = 1;
4504 }
4505 nrefs->checked[*level] = 1;
4506 }
4507
4508 if (path->slots[*level] >= btrfs_header_nritems(cur))
4509 break;
4510
4511 /* Don't forgot to check leaf/node validation */
4512 if (*level == 0) {
4513 /* skip duplicate check */
4514 if (check || !check_all) {
4515 ret = btrfs_check_leaf(root, NULL, cur);
4516 if (ret != BTRFS_TREE_BLOCK_CLEAN) {
4517 err |= -EIO;
4518 break;
4519 }
4520 }
4521
4522 ret = 0;
4523 if (!check_all)
4524 ret = process_one_leaf(root, path, nrefs, level);
4525 else
4526 ret = check_leaf_items(root, path,
4527 nrefs, account_file_data);
4528 err |= ret;
4529 break;
4530 }
4531 if (check || !check_all) {
4532 ret = btrfs_check_node(root, NULL, cur);
4533 if (ret != BTRFS_TREE_BLOCK_CLEAN) {
4534 err |= -EIO;
4535 break;
4536 }
4537 }
4538
4539 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4540 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4541
4542 ret = update_nodes_refs(root, bytenr, NULL, nrefs, *level - 1,
4543 check_all);
4544 if (ret < 0)
4545 break;
4546 /*
4547 * check all trees in check_chunks_and_extent
4548 * check shared node once in check_fs_roots
4549 */
4550 if (!check_all && !nrefs->need_check[*level - 1]) {
4551 path->slots[*level]++;
4552 continue;
4553 }
4554
4555 next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize);
4556 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
4557 free_extent_buffer(next);
4558 reada_walk_down(root, cur, path->slots[*level]);
4559 next = read_tree_block(fs_info, bytenr, ptr_gen);
4560 if (!extent_buffer_uptodate(next)) {
4561 struct btrfs_key node_key;
4562
4563 btrfs_node_key_to_cpu(path->nodes[*level],
4564 &node_key,
4565 path->slots[*level]);
4566 btrfs_add_corrupt_extent_record(fs_info,
4567 &node_key, path->nodes[*level]->start,
4568 fs_info->nodesize, *level);
4569 err |= -EIO;
4570 break;
4571 }
4572 }
4573
4574 ret = check_child_node(cur, path->slots[*level], next);
4575 err |= ret;
4576 if (ret < 0)
4577 break;
4578
4579 if (btrfs_is_leaf(next))
4580 status = btrfs_check_leaf(root, NULL, next);
4581 else
4582 status = btrfs_check_node(root, NULL, next);
4583 if (status != BTRFS_TREE_BLOCK_CLEAN) {
4584 free_extent_buffer(next);
4585 err |= -EIO;
4586 break;
4587 }
4588
4589 *level = *level - 1;
4590 free_extent_buffer(path->nodes[*level]);
4591 path->nodes[*level] = next;
4592 path->slots[*level] = 0;
4593 account_file_data = 0;
4594
4595 update_nodes_refs(root, (u64)-1, next, nrefs, *level, check_all);
4596 }
4597 return err;
4598 }
4599
4600 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
4601 int *level)
4602 {
4603 int i;
4604 struct extent_buffer *leaf;
4605
4606 for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
4607 leaf = path->nodes[i];
4608 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
4609 path->slots[i]++;
4610 *level = i;
4611 return 0;
4612 }
4613 free_extent_buffer(path->nodes[*level]);
4614 path->nodes[*level] = NULL;
4615 *level = i + 1;
4616 }
4617 return 1;
4618 }
4619
4620 /*
4621 * Insert the missing inode item and inode ref.
4622 *
4623 * Normal INODE_ITEM_MISSING and INODE_REF_MISSING are handled in backref * dir.
4624 * Root dir should be handled specially because root dir is the root of fs.
4625 *
4626 * returns err (>0 or 0) after repair
4627 */
4628 static int repair_fs_first_inode(struct btrfs_root *root, int err)
4629 {
4630 struct btrfs_trans_handle *trans;
4631 struct btrfs_key key;
4632 struct btrfs_path path;
4633 int filetype = BTRFS_FT_DIR;
4634 int ret = 0;
4635
4636 btrfs_init_path(&path);
4637
4638 if (err & INODE_REF_MISSING) {
4639 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
4640 key.type = BTRFS_INODE_REF_KEY;
4641 key.offset = BTRFS_FIRST_FREE_OBJECTID;
4642
4643 trans = btrfs_start_transaction(root, 1);
4644 if (IS_ERR(trans)) {
4645 ret = PTR_ERR(trans);
4646 goto out;
4647 }
4648
4649 btrfs_release_path(&path);
4650 ret = btrfs_search_slot(trans, root, &key, &path, 1, 1);
4651 if (ret)
4652 goto trans_fail;
4653
4654 ret = btrfs_insert_inode_ref(trans, root, "..", 2,
4655 BTRFS_FIRST_FREE_OBJECTID,
4656 BTRFS_FIRST_FREE_OBJECTID, 0);
4657 if (ret)
4658 goto trans_fail;
4659
4660 printf("Add INODE_REF[%llu %llu] name %s\n",
4661 BTRFS_FIRST_FREE_OBJECTID, BTRFS_FIRST_FREE_OBJECTID,
4662 "..");
4663 err &= ~INODE_REF_MISSING;
4664 trans_fail:
4665 if (ret)
4666 error("fail to insert first inode's ref");
4667 btrfs_commit_transaction(trans, root);
4668 }
4669
4670 if (err & INODE_ITEM_MISSING) {
4671 ret = repair_inode_item_missing(root,
4672 BTRFS_FIRST_FREE_OBJECTID, filetype);
4673 if (ret)
4674 goto out;
4675 err &= ~INODE_ITEM_MISSING;
4676 }
4677 out:
4678 if (ret)
4679 error("fail to repair first inode");
4680 btrfs_release_path(&path);
4681 return err;
4682 }
4683
4684 /*
4685 * check first root dir's inode_item and inode_ref
4686 *
4687 * returns 0 means no error
4688 * returns >0 means error
4689 * returns <0 means fatal error
4690 */
4691 static int check_fs_first_inode(struct btrfs_root *root)
4692 {
4693 struct btrfs_path path;
4694 struct btrfs_key key;
4695 struct btrfs_inode_item *ii;
4696 u64 index;
4697 u32 mode;
4698 int err = 0;
4699 int ret;
4700
4701 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
4702 key.type = BTRFS_INODE_ITEM_KEY;
4703 key.offset = 0;
4704
4705 /* For root being dropped, we don't need to check first inode */
4706 if (btrfs_root_refs(&root->root_item) == 0 &&
4707 btrfs_disk_key_objectid(&root->root_item.drop_progress) >=
4708 BTRFS_FIRST_FREE_OBJECTID)
4709 return 0;
4710
4711 btrfs_init_path(&path);
4712 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
4713 if (ret < 0)
4714 goto out;
4715 if (ret > 0) {
4716 ret = 0;
4717 err |= INODE_ITEM_MISSING;
4718 } else {
4719 ii = btrfs_item_ptr(path.nodes[0], path.slots[0],
4720 struct btrfs_inode_item);
4721 mode = btrfs_inode_mode(path.nodes[0], ii);
4722 if (imode_to_type(mode) != BTRFS_FT_DIR)
4723 err |= INODE_ITEM_MISMATCH;
4724 }
4725
4726 /* lookup first inode ref */
4727 key.offset = BTRFS_FIRST_FREE_OBJECTID;
4728 key.type = BTRFS_INODE_REF_KEY;
4729 /* special index value */
4730 index = 0;
4731
4732 ret = find_inode_ref(root, &key, "..", strlen(".."), &index);
4733 if (ret < 0)
4734 goto out;
4735 err |= ret;
4736
4737 out:
4738 btrfs_release_path(&path);
4739
4740 if (err && repair)
4741 err = repair_fs_first_inode(root, err);
4742
4743 if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH))
4744 error("root dir INODE_ITEM is %s",
4745 err & INODE_ITEM_MISMATCH ? "mismatch" : "missing");
4746 if (err & INODE_REF_MISSING)
4747 error("root dir INODE_REF is missing");
4748
4749 return ret < 0 ? ret : err;
4750 }
4751
4752 /*
4753 * This function calls walk_down_tree and walk_up_tree to check tree
4754 * blocks and integrity of fs tree items.
4755 *
4756 * @root: the root of the tree to be checked.
4757 * @account if NOT 0 means check the tree (including tree)'s treeblocks.
4758 * otherwise means check fs tree(s) items relationship and
4759 * @root MUST be a fs tree root.
4760 * Returns 0 represents OK.
4761 * Returns >0 represents error bits.
4762 */
4763 static int check_btrfs_root(struct btrfs_root *root, int check_all)
4764 {
4765 struct btrfs_path path;
4766 struct node_refs nrefs;
4767 struct btrfs_root_item *root_item = &root->root_item;
4768 int ret;
4769 int level;
4770 int err = 0;
4771
4772 memset(&nrefs, 0, sizeof(nrefs));
4773 if (!check_all) {
4774 /*
4775 * We need to manually check the first inode item (256)
4776 * As the following traversal function will only start from
4777 * the first inode item in the leaf, if inode item (256) is
4778 * missing we will skip it forever.
4779 */
4780 ret = check_fs_first_inode(root);
4781 if (ret < 0)
4782 return FATAL_ERROR;
4783 }
4784
4785
4786 level = btrfs_header_level(root->node);
4787 btrfs_init_path(&path);
4788
4789 if (btrfs_root_refs(root_item) > 0 ||
4790 btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
4791 path.nodes[level] = root->node;
4792 path.slots[level] = 0;
4793 extent_buffer_get(root->node);
4794 } else {
4795 struct btrfs_key key;
4796
4797 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
4798 level = root_item->drop_level;
4799 path.lowest_level = level;
4800 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
4801 if (ret < 0)
4802 goto out;
4803 ret = 0;
4804 }
4805
4806 while (1) {
4807 ctx.item_count++;
4808 ret = walk_down_tree(root, &path, &level, &nrefs, check_all);
4809
4810 if (ret > 0)
4811 err |= ret;
4812 /* if ret is negative, walk shall stop */
4813 if (ret < 0) {
4814 ret = err | FATAL_ERROR;
4815 break;
4816 }
4817
4818 ret = walk_up_tree(root, &path, &level);
4819 if (ret != 0) {
4820 /* Normal exit, reset ret to err */
4821 ret = err;
4822 break;
4823 }
4824 }
4825
4826 out:
4827 btrfs_release_path(&path);
4828 return ret;
4829 }
4830
4831 /*
4832 * Iterate all items in the tree and call check_inode_item() to check.
4833 *
4834 * @root: the root of the tree to be checked.
4835 *
4836 * Return 0 if no error found.
4837 * Return <0 for error.
4838 */
4839 static int check_fs_root(struct btrfs_root *root)
4840 {
4841 reset_cached_block_groups(root->fs_info);
4842 return check_btrfs_root(root, 0);
4843 }
4844
4845 /*
4846 * Find the relative ref for root_ref and root_backref.
4847 *
4848 * @root: the root of the root tree.
4849 * @ref_key: the key of the root ref.
4850 *
4851 * Return 0 if no error occurred.
4852 */
4853 static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
4854 struct extent_buffer *node, int slot)
4855 {
4856 struct btrfs_path path;
4857 struct btrfs_key key;
4858 struct btrfs_root_ref *ref;
4859 struct btrfs_root_ref *backref;
4860 char ref_name[BTRFS_NAME_LEN] = {0};
4861 char backref_name[BTRFS_NAME_LEN] = {0};
4862 u64 ref_dirid;
4863 u64 ref_seq;
4864 u32 ref_namelen;
4865 u64 backref_dirid;
4866 u64 backref_seq;
4867 u32 backref_namelen;
4868 u32 len;
4869 int ret;
4870 int err = 0;
4871
4872 ref = btrfs_item_ptr(node, slot, struct btrfs_root_ref);
4873 ref_dirid = btrfs_root_ref_dirid(node, ref);
4874 ref_seq = btrfs_root_ref_sequence(node, ref);
4875 ref_namelen = btrfs_root_ref_name_len(node, ref);
4876
4877 if (ref_namelen <= BTRFS_NAME_LEN) {
4878 len = ref_namelen;
4879 } else {
4880 len = BTRFS_NAME_LEN;
4881 warning("%s[%llu %llu] ref_name too long",
4882 ref_key->type == BTRFS_ROOT_REF_KEY ?
4883 "ROOT_REF" : "ROOT_BACKREF", ref_key->objectid,
4884 ref_key->offset);
4885 }
4886 read_extent_buffer(node, ref_name, (unsigned long)(ref + 1), len);
4887
4888 /* Find relative root_ref */
4889 key.objectid = ref_key->offset;
4890 key.type = BTRFS_ROOT_BACKREF_KEY + BTRFS_ROOT_REF_KEY - ref_key->type;
4891 key.offset = ref_key->objectid;
4892
4893 btrfs_init_path(&path);
4894 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
4895 if (ret) {
4896 err |= ROOT_REF_MISSING;
4897 error("%s[%llu %llu] couldn't find relative ref",
4898 ref_key->type == BTRFS_ROOT_REF_KEY ?
4899 "ROOT_REF" : "ROOT_BACKREF",
4900 ref_key->objectid, ref_key->offset);
4901 goto out;
4902 }
4903
4904 backref = btrfs_item_ptr(path.nodes[0], path.slots[0],
4905 struct btrfs_root_ref);
4906 backref_dirid = btrfs_root_ref_dirid(path.nodes[0], backref);
4907 backref_seq = btrfs_root_ref_sequence(path.nodes[0], backref);
4908 backref_namelen = btrfs_root_ref_name_len(path.nodes[0], backref);
4909
4910 if (backref_namelen <= BTRFS_NAME_LEN) {
4911 len = backref_namelen;
4912 } else {
4913 len = BTRFS_NAME_LEN;
4914 warning("%s[%llu %llu] ref_name too long",
4915 key.type == BTRFS_ROOT_REF_KEY ?
4916 "ROOT_REF" : "ROOT_BACKREF",
4917 key.objectid, key.offset);
4918 }
4919 read_extent_buffer(path.nodes[0], backref_name,
4920 (unsigned long)(backref + 1), len);
4921
4922 if (ref_dirid != backref_dirid || ref_seq != backref_seq ||
4923 ref_namelen != backref_namelen ||
4924 strncmp(ref_name, backref_name, len)) {
4925 err |= ROOT_REF_MISMATCH;
4926 error("%s[%llu %llu] mismatch relative ref",
4927 ref_key->type == BTRFS_ROOT_REF_KEY ?
4928 "ROOT_REF" : "ROOT_BACKREF",
4929 ref_key->objectid, ref_key->offset);
4930 }
4931 out:
4932 btrfs_release_path(&path);
4933 return err;
4934 }
4935
4936 /*
4937 * Check all fs/file tree in low_memory mode.
4938 *
4939 * 1. for fs tree root item, call check_fs_root()
4940 * 2. for fs tree root ref/backref, call check_root_ref()
4941 *
4942 * Return 0 if no error occurred.
4943 */
4944 int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
4945 {
4946 struct btrfs_root *tree_root = fs_info->tree_root;
4947 struct btrfs_root *cur_root = NULL;
4948 struct btrfs_path path;
4949 struct btrfs_key key;
4950 struct extent_buffer *node;
4951 int slot;
4952 int ret;
4953 int err = 0;
4954
4955 btrfs_init_path(&path);
4956 key.objectid = BTRFS_FS_TREE_OBJECTID;
4957 key.offset = 0;
4958 key.type = BTRFS_ROOT_ITEM_KEY;
4959
4960 ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
4961 if (ret < 0) {
4962 err = ret;
4963 goto out;
4964 } else if (ret > 0) {
4965 err = -ENOENT;
4966 goto out;
4967 }
4968
4969 while (1) {
4970 node = path.nodes[0];
4971 slot = path.slots[0];
4972 btrfs_item_key_to_cpu(node, &key, slot);
4973 if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
4974 goto out;
4975 if (key.type == BTRFS_ROOT_ITEM_KEY &&
4976 fs_root_objectid(key.objectid)) {
4977 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
4978 cur_root = btrfs_read_fs_root_no_cache(fs_info,
4979 &key);
4980 } else {
4981 key.offset = (u64)-1;
4982 cur_root = btrfs_read_fs_root(fs_info, &key);
4983 }
4984
4985 if (IS_ERR(cur_root)) {
4986 error("Fail to read fs/subvol tree: %lld",
4987 key.objectid);
4988 err = -EIO;
4989 goto next;
4990 }
4991
4992 ret = check_fs_root(cur_root);
4993 err |= ret;
4994
4995 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
4996 btrfs_free_fs_root(cur_root);
4997 } else if (key.type == BTRFS_ROOT_REF_KEY ||
4998 key.type == BTRFS_ROOT_BACKREF_KEY) {
4999 ret = check_root_ref(tree_root, &key, node, slot);
5000 err |= ret;
5001 }
5002 next:
5003 ret = btrfs_next_item(tree_root, &path);
5004 if (ret > 0)
5005 goto out;
5006 if (ret < 0) {
5007 err = ret;
5008 goto out;
5009 }
5010 }
5011
5012 out:
5013 btrfs_release_path(&path);
5014 return err;
5015 }
5016
5017 /*
5018 * Low memory usage version check_chunks_and_extents.
5019 */
5020 int check_chunks_and_extents_lowmem(struct btrfs_fs_info *fs_info)
5021 {
5022 struct btrfs_path path;
5023 struct btrfs_key old_key;
5024 struct btrfs_key key;
5025 struct btrfs_root *root1;
5026 struct btrfs_root *root;
5027 struct btrfs_root *cur_root;
5028 int err = 0;
5029 int ret;
5030
5031 root = fs_info->fs_root;
5032
5033 root1 = root->fs_info->chunk_root;
5034 ret = check_btrfs_root(root1, 1);
5035 err |= ret;
5036
5037 root1 = root->fs_info->tree_root;
5038 ret = check_btrfs_root(root1, 1);
5039 err |= ret;
5040
5041 btrfs_init_path(&path);
5042 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
5043 key.offset = 0;
5044 key.type = BTRFS_ROOT_ITEM_KEY;
5045
5046 ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0);
5047 if (ret) {
5048 error("cannot find extent tree in tree_root");
5049 goto out;
5050 }
5051
5052 while (1) {
5053 btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
5054 if (key.type != BTRFS_ROOT_ITEM_KEY)
5055 goto next;
5056 old_key = key;
5057 key.offset = (u64)-1;
5058
5059 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
5060 cur_root = btrfs_read_fs_root_no_cache(root->fs_info,
5061 &key);
5062 else
5063 cur_root = btrfs_read_fs_root(root->fs_info, &key);
5064 if (IS_ERR(cur_root) || !cur_root) {
5065 error("failed to read tree: %lld", key.objectid);
5066 goto next;
5067 }
5068
5069 ret = check_btrfs_root(cur_root, 1);
5070 err |= ret;
5071
5072 if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
5073 btrfs_free_fs_root(cur_root);
5074
5075 btrfs_release_path(&path);
5076 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
5077 &old_key, &path, 0, 0);
5078 if (ret)
5079 goto out;
5080 next:
5081 ret = btrfs_next_item(root1, &path);
5082 if (ret)
5083 goto out;
5084 }
5085 out:
5086
5087 if (repair) {
5088 ret = end_avoid_extents_overwrite(fs_info);
5089 if (ret < 0)
5090 ret = FATAL_ERROR;
5091 err |= ret;
5092
5093 reset_cached_block_groups(fs_info);
5094 /* update block accounting */
5095 ret = repair_block_accounting(fs_info);
5096 if (ret)
5097 err |= ret;
5098 else
5099 err &= ~BG_ACCOUNTING_ERROR;
5100 }
5101
5102 btrfs_release_path(&path);
5103 return err;
5104 }
(deprecated) Btrfs progs developments and patch integration