xref: /linux/fs/btrfs/tree-checker.c (revision 8795a739e5c72abeec51caf36b6df2b37e5720c5)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) Qu Wenruo 2017.  All rights reserved.
4  */
5 
6 /*
7  * The module is used to catch unexpected/corrupted tree block data.
8  * Such behavior can be caused either by a fuzzed image or bugs.
9  *
10  * The objective is to do leaf/node validation checks when tree block is read
11  * from disk, and check *every* possible member, so other code won't
12  * need to checking them again.
13  *
14  * Due to the potential and unwanted damage, every checker needs to be
15  * carefully reviewed otherwise so it does not prevent mount of valid images.
16  */
17 
18 #include <linux/types.h>
19 #include <linux/stddef.h>
20 #include <linux/error-injection.h>
21 #include "ctree.h"
22 #include "tree-checker.h"
23 #include "disk-io.h"
24 #include "compression.h"
25 #include "volumes.h"
26 
27 /*
28  * Error message should follow the following format:
29  * corrupt <type>: <identifier>, <reason>[, <bad_value>]
30  *
31  * @type:	leaf or node
32  * @identifier:	the necessary info to locate the leaf/node.
33  * 		It's recommended to decode key.objecitd/offset if it's
34  * 		meaningful.
35  * @reason:	describe the error
36  * @bad_value:	optional, it's recommended to output bad value and its
37  *		expected value (range).
38  *
39  * Since comma is used to separate the components, only space is allowed
40  * inside each component.
41  */
42 
43 /*
44  * Append generic "corrupt leaf/node root=%llu block=%llu slot=%d: " to @fmt.
45  * Allows callers to customize the output.
46  */
47 __printf(3, 4)
48 __cold
49 static void generic_err(const struct extent_buffer *eb, int slot,
50 			const char *fmt, ...)
51 {
52 	const struct btrfs_fs_info *fs_info = eb->fs_info;
53 	struct va_format vaf;
54 	va_list args;
55 
56 	va_start(args, fmt);
57 
58 	vaf.fmt = fmt;
59 	vaf.va = &args;
60 
61 	btrfs_crit(fs_info,
62 		"corrupt %s: root=%llu block=%llu slot=%d, %pV",
63 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
64 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot, &vaf);
65 	va_end(args);
66 }
67 
68 /*
69  * Customized reporter for extent data item, since its key objectid and
70  * offset has its own meaning.
71  */
72 __printf(3, 4)
73 __cold
74 static void file_extent_err(const struct extent_buffer *eb, int slot,
75 			    const char *fmt, ...)
76 {
77 	const struct btrfs_fs_info *fs_info = eb->fs_info;
78 	struct btrfs_key key;
79 	struct va_format vaf;
80 	va_list args;
81 
82 	btrfs_item_key_to_cpu(eb, &key, slot);
83 	va_start(args, fmt);
84 
85 	vaf.fmt = fmt;
86 	vaf.va = &args;
87 
88 	btrfs_crit(fs_info,
89 	"corrupt %s: root=%llu block=%llu slot=%d ino=%llu file_offset=%llu, %pV",
90 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
91 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
92 		key.objectid, key.offset, &vaf);
93 	va_end(args);
94 }
95 
96 /*
97  * Return 0 if the btrfs_file_extent_##name is aligned to @alignment
98  * Else return 1
99  */
100 #define CHECK_FE_ALIGNED(leaf, slot, fi, name, alignment)		      \
101 ({									      \
102 	if (!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment))) \
103 		file_extent_err((leaf), (slot),				      \
104 	"invalid %s for file extent, have %llu, should be aligned to %u",     \
105 			(#name), btrfs_file_extent_##name((leaf), (fi)),      \
106 			(alignment));					      \
107 	(!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment)));   \
108 })
109 
110 static u64 file_extent_end(struct extent_buffer *leaf,
111 			   struct btrfs_key *key,
112 			   struct btrfs_file_extent_item *extent)
113 {
114 	u64 end;
115 	u64 len;
116 
117 	if (btrfs_file_extent_type(leaf, extent) == BTRFS_FILE_EXTENT_INLINE) {
118 		len = btrfs_file_extent_ram_bytes(leaf, extent);
119 		end = ALIGN(key->offset + len, leaf->fs_info->sectorsize);
120 	} else {
121 		len = btrfs_file_extent_num_bytes(leaf, extent);
122 		end = key->offset + len;
123 	}
124 	return end;
125 }
126 
127 static int check_extent_data_item(struct extent_buffer *leaf,
128 				  struct btrfs_key *key, int slot,
129 				  struct btrfs_key *prev_key)
130 {
131 	struct btrfs_fs_info *fs_info = leaf->fs_info;
132 	struct btrfs_file_extent_item *fi;
133 	u32 sectorsize = fs_info->sectorsize;
134 	u32 item_size = btrfs_item_size_nr(leaf, slot);
135 	u64 extent_end;
136 
137 	if (!IS_ALIGNED(key->offset, sectorsize)) {
138 		file_extent_err(leaf, slot,
139 "unaligned file_offset for file extent, have %llu should be aligned to %u",
140 			key->offset, sectorsize);
141 		return -EUCLEAN;
142 	}
143 
144 	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
145 
146 	if (btrfs_file_extent_type(leaf, fi) > BTRFS_FILE_EXTENT_TYPES) {
147 		file_extent_err(leaf, slot,
148 		"invalid type for file extent, have %u expect range [0, %u]",
149 			btrfs_file_extent_type(leaf, fi),
150 			BTRFS_FILE_EXTENT_TYPES);
151 		return -EUCLEAN;
152 	}
153 
154 	/*
155 	 * Support for new compression/encryption must introduce incompat flag,
156 	 * and must be caught in open_ctree().
157 	 */
158 	if (btrfs_file_extent_compression(leaf, fi) > BTRFS_COMPRESS_TYPES) {
159 		file_extent_err(leaf, slot,
160 	"invalid compression for file extent, have %u expect range [0, %u]",
161 			btrfs_file_extent_compression(leaf, fi),
162 			BTRFS_COMPRESS_TYPES);
163 		return -EUCLEAN;
164 	}
165 	if (btrfs_file_extent_encryption(leaf, fi)) {
166 		file_extent_err(leaf, slot,
167 			"invalid encryption for file extent, have %u expect 0",
168 			btrfs_file_extent_encryption(leaf, fi));
169 		return -EUCLEAN;
170 	}
171 	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
172 		/* Inline extent must have 0 as key offset */
173 		if (key->offset) {
174 			file_extent_err(leaf, slot,
175 		"invalid file_offset for inline file extent, have %llu expect 0",
176 				key->offset);
177 			return -EUCLEAN;
178 		}
179 
180 		/* Compressed inline extent has no on-disk size, skip it */
181 		if (btrfs_file_extent_compression(leaf, fi) !=
182 		    BTRFS_COMPRESS_NONE)
183 			return 0;
184 
185 		/* Uncompressed inline extent size must match item size */
186 		if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
187 		    btrfs_file_extent_ram_bytes(leaf, fi)) {
188 			file_extent_err(leaf, slot,
189 	"invalid ram_bytes for uncompressed inline extent, have %u expect %llu",
190 				item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START +
191 				btrfs_file_extent_ram_bytes(leaf, fi));
192 			return -EUCLEAN;
193 		}
194 		return 0;
195 	}
196 
197 	/* Regular or preallocated extent has fixed item size */
198 	if (item_size != sizeof(*fi)) {
199 		file_extent_err(leaf, slot,
200 	"invalid item size for reg/prealloc file extent, have %u expect %zu",
201 			item_size, sizeof(*fi));
202 		return -EUCLEAN;
203 	}
204 	if (CHECK_FE_ALIGNED(leaf, slot, fi, ram_bytes, sectorsize) ||
205 	    CHECK_FE_ALIGNED(leaf, slot, fi, disk_bytenr, sectorsize) ||
206 	    CHECK_FE_ALIGNED(leaf, slot, fi, disk_num_bytes, sectorsize) ||
207 	    CHECK_FE_ALIGNED(leaf, slot, fi, offset, sectorsize) ||
208 	    CHECK_FE_ALIGNED(leaf, slot, fi, num_bytes, sectorsize))
209 		return -EUCLEAN;
210 
211 	/* Catch extent end overflow */
212 	if (check_add_overflow(btrfs_file_extent_num_bytes(leaf, fi),
213 			       key->offset, &extent_end)) {
214 		file_extent_err(leaf, slot,
215 	"extent end overflow, have file offset %llu extent num bytes %llu",
216 				key->offset,
217 				btrfs_file_extent_num_bytes(leaf, fi));
218 		return -EUCLEAN;
219 	}
220 
221 	/*
222 	 * Check that no two consecutive file extent items, in the same leaf,
223 	 * present ranges that overlap each other.
224 	 */
225 	if (slot > 0 &&
226 	    prev_key->objectid == key->objectid &&
227 	    prev_key->type == BTRFS_EXTENT_DATA_KEY) {
228 		struct btrfs_file_extent_item *prev_fi;
229 		u64 prev_end;
230 
231 		prev_fi = btrfs_item_ptr(leaf, slot - 1,
232 					 struct btrfs_file_extent_item);
233 		prev_end = file_extent_end(leaf, prev_key, prev_fi);
234 		if (prev_end > key->offset) {
235 			file_extent_err(leaf, slot - 1,
236 "file extent end range (%llu) goes beyond start offset (%llu) of the next file extent",
237 					prev_end, key->offset);
238 			return -EUCLEAN;
239 		}
240 	}
241 
242 	return 0;
243 }
244 
245 static int check_csum_item(struct extent_buffer *leaf, struct btrfs_key *key,
246 			   int slot)
247 {
248 	struct btrfs_fs_info *fs_info = leaf->fs_info;
249 	u32 sectorsize = fs_info->sectorsize;
250 	u32 csumsize = btrfs_super_csum_size(fs_info->super_copy);
251 
252 	if (key->objectid != BTRFS_EXTENT_CSUM_OBJECTID) {
253 		generic_err(leaf, slot,
254 		"invalid key objectid for csum item, have %llu expect %llu",
255 			key->objectid, BTRFS_EXTENT_CSUM_OBJECTID);
256 		return -EUCLEAN;
257 	}
258 	if (!IS_ALIGNED(key->offset, sectorsize)) {
259 		generic_err(leaf, slot,
260 	"unaligned key offset for csum item, have %llu should be aligned to %u",
261 			key->offset, sectorsize);
262 		return -EUCLEAN;
263 	}
264 	if (!IS_ALIGNED(btrfs_item_size_nr(leaf, slot), csumsize)) {
265 		generic_err(leaf, slot,
266 	"unaligned item size for csum item, have %u should be aligned to %u",
267 			btrfs_item_size_nr(leaf, slot), csumsize);
268 		return -EUCLEAN;
269 	}
270 	return 0;
271 }
272 
273 /*
274  * Customized reported for dir_item, only important new info is key->objectid,
275  * which represents inode number
276  */
277 __printf(3, 4)
278 __cold
279 static void dir_item_err(const struct extent_buffer *eb, int slot,
280 			 const char *fmt, ...)
281 {
282 	const struct btrfs_fs_info *fs_info = eb->fs_info;
283 	struct btrfs_key key;
284 	struct va_format vaf;
285 	va_list args;
286 
287 	btrfs_item_key_to_cpu(eb, &key, slot);
288 	va_start(args, fmt);
289 
290 	vaf.fmt = fmt;
291 	vaf.va = &args;
292 
293 	btrfs_crit(fs_info,
294 	"corrupt %s: root=%llu block=%llu slot=%d ino=%llu, %pV",
295 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
296 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
297 		key.objectid, &vaf);
298 	va_end(args);
299 }
300 
301 static int check_dir_item(struct extent_buffer *leaf,
302 			  struct btrfs_key *key, int slot)
303 {
304 	struct btrfs_fs_info *fs_info = leaf->fs_info;
305 	struct btrfs_dir_item *di;
306 	u32 item_size = btrfs_item_size_nr(leaf, slot);
307 	u32 cur = 0;
308 
309 	di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
310 	while (cur < item_size) {
311 		u32 name_len;
312 		u32 data_len;
313 		u32 max_name_len;
314 		u32 total_size;
315 		u32 name_hash;
316 		u8 dir_type;
317 
318 		/* header itself should not cross item boundary */
319 		if (cur + sizeof(*di) > item_size) {
320 			dir_item_err(leaf, slot,
321 		"dir item header crosses item boundary, have %zu boundary %u",
322 				cur + sizeof(*di), item_size);
323 			return -EUCLEAN;
324 		}
325 
326 		/* dir type check */
327 		dir_type = btrfs_dir_type(leaf, di);
328 		if (dir_type >= BTRFS_FT_MAX) {
329 			dir_item_err(leaf, slot,
330 			"invalid dir item type, have %u expect [0, %u)",
331 				dir_type, BTRFS_FT_MAX);
332 			return -EUCLEAN;
333 		}
334 
335 		if (key->type == BTRFS_XATTR_ITEM_KEY &&
336 		    dir_type != BTRFS_FT_XATTR) {
337 			dir_item_err(leaf, slot,
338 		"invalid dir item type for XATTR key, have %u expect %u",
339 				dir_type, BTRFS_FT_XATTR);
340 			return -EUCLEAN;
341 		}
342 		if (dir_type == BTRFS_FT_XATTR &&
343 		    key->type != BTRFS_XATTR_ITEM_KEY) {
344 			dir_item_err(leaf, slot,
345 			"xattr dir type found for non-XATTR key");
346 			return -EUCLEAN;
347 		}
348 		if (dir_type == BTRFS_FT_XATTR)
349 			max_name_len = XATTR_NAME_MAX;
350 		else
351 			max_name_len = BTRFS_NAME_LEN;
352 
353 		/* Name/data length check */
354 		name_len = btrfs_dir_name_len(leaf, di);
355 		data_len = btrfs_dir_data_len(leaf, di);
356 		if (name_len > max_name_len) {
357 			dir_item_err(leaf, slot,
358 			"dir item name len too long, have %u max %u",
359 				name_len, max_name_len);
360 			return -EUCLEAN;
361 		}
362 		if (name_len + data_len > BTRFS_MAX_XATTR_SIZE(fs_info)) {
363 			dir_item_err(leaf, slot,
364 			"dir item name and data len too long, have %u max %u",
365 				name_len + data_len,
366 				BTRFS_MAX_XATTR_SIZE(fs_info));
367 			return -EUCLEAN;
368 		}
369 
370 		if (data_len && dir_type != BTRFS_FT_XATTR) {
371 			dir_item_err(leaf, slot,
372 			"dir item with invalid data len, have %u expect 0",
373 				data_len);
374 			return -EUCLEAN;
375 		}
376 
377 		total_size = sizeof(*di) + name_len + data_len;
378 
379 		/* header and name/data should not cross item boundary */
380 		if (cur + total_size > item_size) {
381 			dir_item_err(leaf, slot,
382 		"dir item data crosses item boundary, have %u boundary %u",
383 				cur + total_size, item_size);
384 			return -EUCLEAN;
385 		}
386 
387 		/*
388 		 * Special check for XATTR/DIR_ITEM, as key->offset is name
389 		 * hash, should match its name
390 		 */
391 		if (key->type == BTRFS_DIR_ITEM_KEY ||
392 		    key->type == BTRFS_XATTR_ITEM_KEY) {
393 			char namebuf[max(BTRFS_NAME_LEN, XATTR_NAME_MAX)];
394 
395 			read_extent_buffer(leaf, namebuf,
396 					(unsigned long)(di + 1), name_len);
397 			name_hash = btrfs_name_hash(namebuf, name_len);
398 			if (key->offset != name_hash) {
399 				dir_item_err(leaf, slot,
400 		"name hash mismatch with key, have 0x%016x expect 0x%016llx",
401 					name_hash, key->offset);
402 				return -EUCLEAN;
403 			}
404 		}
405 		cur += total_size;
406 		di = (struct btrfs_dir_item *)((void *)di + total_size);
407 	}
408 	return 0;
409 }
410 
411 __printf(3, 4)
412 __cold
413 static void block_group_err(const struct extent_buffer *eb, int slot,
414 			    const char *fmt, ...)
415 {
416 	const struct btrfs_fs_info *fs_info = eb->fs_info;
417 	struct btrfs_key key;
418 	struct va_format vaf;
419 	va_list args;
420 
421 	btrfs_item_key_to_cpu(eb, &key, slot);
422 	va_start(args, fmt);
423 
424 	vaf.fmt = fmt;
425 	vaf.va = &args;
426 
427 	btrfs_crit(fs_info,
428 	"corrupt %s: root=%llu block=%llu slot=%d bg_start=%llu bg_len=%llu, %pV",
429 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
430 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
431 		key.objectid, key.offset, &vaf);
432 	va_end(args);
433 }
434 
435 static int check_block_group_item(struct extent_buffer *leaf,
436 				  struct btrfs_key *key, int slot)
437 {
438 	struct btrfs_block_group_item bgi;
439 	u32 item_size = btrfs_item_size_nr(leaf, slot);
440 	u64 flags;
441 	u64 type;
442 
443 	/*
444 	 * Here we don't really care about alignment since extent allocator can
445 	 * handle it.  We care more about the size.
446 	 */
447 	if (key->offset == 0) {
448 		block_group_err(leaf, slot,
449 				"invalid block group size 0");
450 		return -EUCLEAN;
451 	}
452 
453 	if (item_size != sizeof(bgi)) {
454 		block_group_err(leaf, slot,
455 			"invalid item size, have %u expect %zu",
456 				item_size, sizeof(bgi));
457 		return -EUCLEAN;
458 	}
459 
460 	read_extent_buffer(leaf, &bgi, btrfs_item_ptr_offset(leaf, slot),
461 			   sizeof(bgi));
462 	if (btrfs_block_group_chunk_objectid(&bgi) !=
463 	    BTRFS_FIRST_CHUNK_TREE_OBJECTID) {
464 		block_group_err(leaf, slot,
465 		"invalid block group chunk objectid, have %llu expect %llu",
466 				btrfs_block_group_chunk_objectid(&bgi),
467 				BTRFS_FIRST_CHUNK_TREE_OBJECTID);
468 		return -EUCLEAN;
469 	}
470 
471 	if (btrfs_block_group_used(&bgi) > key->offset) {
472 		block_group_err(leaf, slot,
473 			"invalid block group used, have %llu expect [0, %llu)",
474 				btrfs_block_group_used(&bgi), key->offset);
475 		return -EUCLEAN;
476 	}
477 
478 	flags = btrfs_block_group_flags(&bgi);
479 	if (hweight64(flags & BTRFS_BLOCK_GROUP_PROFILE_MASK) > 1) {
480 		block_group_err(leaf, slot,
481 "invalid profile flags, have 0x%llx (%lu bits set) expect no more than 1 bit set",
482 			flags & BTRFS_BLOCK_GROUP_PROFILE_MASK,
483 			hweight64(flags & BTRFS_BLOCK_GROUP_PROFILE_MASK));
484 		return -EUCLEAN;
485 	}
486 
487 	type = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
488 	if (type != BTRFS_BLOCK_GROUP_DATA &&
489 	    type != BTRFS_BLOCK_GROUP_METADATA &&
490 	    type != BTRFS_BLOCK_GROUP_SYSTEM &&
491 	    type != (BTRFS_BLOCK_GROUP_METADATA |
492 			   BTRFS_BLOCK_GROUP_DATA)) {
493 		block_group_err(leaf, slot,
494 "invalid type, have 0x%llx (%lu bits set) expect either 0x%llx, 0x%llx, 0x%llx or 0x%llx",
495 			type, hweight64(type),
496 			BTRFS_BLOCK_GROUP_DATA, BTRFS_BLOCK_GROUP_METADATA,
497 			BTRFS_BLOCK_GROUP_SYSTEM,
498 			BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_DATA);
499 		return -EUCLEAN;
500 	}
501 	return 0;
502 }
503 
504 __printf(4, 5)
505 __cold
506 static void chunk_err(const struct extent_buffer *leaf,
507 		      const struct btrfs_chunk *chunk, u64 logical,
508 		      const char *fmt, ...)
509 {
510 	const struct btrfs_fs_info *fs_info = leaf->fs_info;
511 	bool is_sb;
512 	struct va_format vaf;
513 	va_list args;
514 	int i;
515 	int slot = -1;
516 
517 	/* Only superblock eb is able to have such small offset */
518 	is_sb = (leaf->start == BTRFS_SUPER_INFO_OFFSET);
519 
520 	if (!is_sb) {
521 		/*
522 		 * Get the slot number by iterating through all slots, this
523 		 * would provide better readability.
524 		 */
525 		for (i = 0; i < btrfs_header_nritems(leaf); i++) {
526 			if (btrfs_item_ptr_offset(leaf, i) ==
527 					(unsigned long)chunk) {
528 				slot = i;
529 				break;
530 			}
531 		}
532 	}
533 	va_start(args, fmt);
534 	vaf.fmt = fmt;
535 	vaf.va = &args;
536 
537 	if (is_sb)
538 		btrfs_crit(fs_info,
539 		"corrupt superblock syschunk array: chunk_start=%llu, %pV",
540 			   logical, &vaf);
541 	else
542 		btrfs_crit(fs_info,
543 	"corrupt leaf: root=%llu block=%llu slot=%d chunk_start=%llu, %pV",
544 			   BTRFS_CHUNK_TREE_OBJECTID, leaf->start, slot,
545 			   logical, &vaf);
546 	va_end(args);
547 }
548 
549 /*
550  * The common chunk check which could also work on super block sys chunk array.
551  *
552  * Return -EUCLEAN if anything is corrupted.
553  * Return 0 if everything is OK.
554  */
555 int btrfs_check_chunk_valid(struct extent_buffer *leaf,
556 			    struct btrfs_chunk *chunk, u64 logical)
557 {
558 	struct btrfs_fs_info *fs_info = leaf->fs_info;
559 	u64 length;
560 	u64 stripe_len;
561 	u16 num_stripes;
562 	u16 sub_stripes;
563 	u64 type;
564 	u64 features;
565 	bool mixed = false;
566 
567 	length = btrfs_chunk_length(leaf, chunk);
568 	stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
569 	num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
570 	sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
571 	type = btrfs_chunk_type(leaf, chunk);
572 
573 	if (!num_stripes) {
574 		chunk_err(leaf, chunk, logical,
575 			  "invalid chunk num_stripes, have %u", num_stripes);
576 		return -EUCLEAN;
577 	}
578 	if (!IS_ALIGNED(logical, fs_info->sectorsize)) {
579 		chunk_err(leaf, chunk, logical,
580 		"invalid chunk logical, have %llu should aligned to %u",
581 			  logical, fs_info->sectorsize);
582 		return -EUCLEAN;
583 	}
584 	if (btrfs_chunk_sector_size(leaf, chunk) != fs_info->sectorsize) {
585 		chunk_err(leaf, chunk, logical,
586 			  "invalid chunk sectorsize, have %u expect %u",
587 			  btrfs_chunk_sector_size(leaf, chunk),
588 			  fs_info->sectorsize);
589 		return -EUCLEAN;
590 	}
591 	if (!length || !IS_ALIGNED(length, fs_info->sectorsize)) {
592 		chunk_err(leaf, chunk, logical,
593 			  "invalid chunk length, have %llu", length);
594 		return -EUCLEAN;
595 	}
596 	if (!is_power_of_2(stripe_len) || stripe_len != BTRFS_STRIPE_LEN) {
597 		chunk_err(leaf, chunk, logical,
598 			  "invalid chunk stripe length: %llu",
599 			  stripe_len);
600 		return -EUCLEAN;
601 	}
602 	if (~(BTRFS_BLOCK_GROUP_TYPE_MASK | BTRFS_BLOCK_GROUP_PROFILE_MASK) &
603 	    type) {
604 		chunk_err(leaf, chunk, logical,
605 			  "unrecognized chunk type: 0x%llx",
606 			  ~(BTRFS_BLOCK_GROUP_TYPE_MASK |
607 			    BTRFS_BLOCK_GROUP_PROFILE_MASK) &
608 			  btrfs_chunk_type(leaf, chunk));
609 		return -EUCLEAN;
610 	}
611 
612 	if (!is_power_of_2(type & BTRFS_BLOCK_GROUP_PROFILE_MASK) &&
613 	    (type & BTRFS_BLOCK_GROUP_PROFILE_MASK) != 0) {
614 		chunk_err(leaf, chunk, logical,
615 		"invalid chunk profile flag: 0x%llx, expect 0 or 1 bit set",
616 			  type & BTRFS_BLOCK_GROUP_PROFILE_MASK);
617 		return -EUCLEAN;
618 	}
619 	if ((type & BTRFS_BLOCK_GROUP_TYPE_MASK) == 0) {
620 		chunk_err(leaf, chunk, logical,
621 	"missing chunk type flag, have 0x%llx one bit must be set in 0x%llx",
622 			  type, BTRFS_BLOCK_GROUP_TYPE_MASK);
623 		return -EUCLEAN;
624 	}
625 
626 	if ((type & BTRFS_BLOCK_GROUP_SYSTEM) &&
627 	    (type & (BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_DATA))) {
628 		chunk_err(leaf, chunk, logical,
629 			  "system chunk with data or metadata type: 0x%llx",
630 			  type);
631 		return -EUCLEAN;
632 	}
633 
634 	features = btrfs_super_incompat_flags(fs_info->super_copy);
635 	if (features & BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)
636 		mixed = true;
637 
638 	if (!mixed) {
639 		if ((type & BTRFS_BLOCK_GROUP_METADATA) &&
640 		    (type & BTRFS_BLOCK_GROUP_DATA)) {
641 			chunk_err(leaf, chunk, logical,
642 			"mixed chunk type in non-mixed mode: 0x%llx", type);
643 			return -EUCLEAN;
644 		}
645 	}
646 
647 	if ((type & BTRFS_BLOCK_GROUP_RAID10 && sub_stripes != 2) ||
648 	    (type & BTRFS_BLOCK_GROUP_RAID1 && num_stripes != 2) ||
649 	    (type & BTRFS_BLOCK_GROUP_RAID5 && num_stripes < 2) ||
650 	    (type & BTRFS_BLOCK_GROUP_RAID6 && num_stripes < 3) ||
651 	    (type & BTRFS_BLOCK_GROUP_DUP && num_stripes != 2) ||
652 	    ((type & BTRFS_BLOCK_GROUP_PROFILE_MASK) == 0 && num_stripes != 1)) {
653 		chunk_err(leaf, chunk, logical,
654 			"invalid num_stripes:sub_stripes %u:%u for profile %llu",
655 			num_stripes, sub_stripes,
656 			type & BTRFS_BLOCK_GROUP_PROFILE_MASK);
657 		return -EUCLEAN;
658 	}
659 
660 	return 0;
661 }
662 
663 __printf(3, 4)
664 __cold
665 static void dev_item_err(const struct extent_buffer *eb, int slot,
666 			 const char *fmt, ...)
667 {
668 	struct btrfs_key key;
669 	struct va_format vaf;
670 	va_list args;
671 
672 	btrfs_item_key_to_cpu(eb, &key, slot);
673 	va_start(args, fmt);
674 
675 	vaf.fmt = fmt;
676 	vaf.va = &args;
677 
678 	btrfs_crit(eb->fs_info,
679 	"corrupt %s: root=%llu block=%llu slot=%d devid=%llu %pV",
680 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
681 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
682 		key.objectid, &vaf);
683 	va_end(args);
684 }
685 
686 static int check_dev_item(struct extent_buffer *leaf,
687 			  struct btrfs_key *key, int slot)
688 {
689 	struct btrfs_fs_info *fs_info = leaf->fs_info;
690 	struct btrfs_dev_item *ditem;
691 	u64 max_devid = max(BTRFS_MAX_DEVS(fs_info), BTRFS_MAX_DEVS_SYS_CHUNK);
692 
693 	if (key->objectid != BTRFS_DEV_ITEMS_OBJECTID) {
694 		dev_item_err(leaf, slot,
695 			     "invalid objectid: has=%llu expect=%llu",
696 			     key->objectid, BTRFS_DEV_ITEMS_OBJECTID);
697 		return -EUCLEAN;
698 	}
699 	if (key->offset > max_devid) {
700 		dev_item_err(leaf, slot,
701 			     "invalid devid: has=%llu expect=[0, %llu]",
702 			     key->offset, max_devid);
703 		return -EUCLEAN;
704 	}
705 	ditem = btrfs_item_ptr(leaf, slot, struct btrfs_dev_item);
706 	if (btrfs_device_id(leaf, ditem) != key->offset) {
707 		dev_item_err(leaf, slot,
708 			     "devid mismatch: key has=%llu item has=%llu",
709 			     key->offset, btrfs_device_id(leaf, ditem));
710 		return -EUCLEAN;
711 	}
712 
713 	/*
714 	 * For device total_bytes, we don't have reliable way to check it, as
715 	 * it can be 0 for device removal. Device size check can only be done
716 	 * by dev extents check.
717 	 */
718 	if (btrfs_device_bytes_used(leaf, ditem) >
719 	    btrfs_device_total_bytes(leaf, ditem)) {
720 		dev_item_err(leaf, slot,
721 			     "invalid bytes used: have %llu expect [0, %llu]",
722 			     btrfs_device_bytes_used(leaf, ditem),
723 			     btrfs_device_total_bytes(leaf, ditem));
724 		return -EUCLEAN;
725 	}
726 	/*
727 	 * Remaining members like io_align/type/gen/dev_group aren't really
728 	 * utilized.  Skip them to make later usage of them easier.
729 	 */
730 	return 0;
731 }
732 
733 /* Inode item error output has the same format as dir_item_err() */
734 #define inode_item_err(fs_info, eb, slot, fmt, ...)			\
735 	dir_item_err(eb, slot, fmt, __VA_ARGS__)
736 
737 static int check_inode_item(struct extent_buffer *leaf,
738 			    struct btrfs_key *key, int slot)
739 {
740 	struct btrfs_fs_info *fs_info = leaf->fs_info;
741 	struct btrfs_inode_item *iitem;
742 	u64 super_gen = btrfs_super_generation(fs_info->super_copy);
743 	u32 valid_mask = (S_IFMT | S_ISUID | S_ISGID | S_ISVTX | 0777);
744 	u32 mode;
745 
746 	if ((key->objectid < BTRFS_FIRST_FREE_OBJECTID ||
747 	     key->objectid > BTRFS_LAST_FREE_OBJECTID) &&
748 	    key->objectid != BTRFS_ROOT_TREE_DIR_OBJECTID &&
749 	    key->objectid != BTRFS_FREE_INO_OBJECTID) {
750 		generic_err(leaf, slot,
751 	"invalid key objectid: has %llu expect %llu or [%llu, %llu] or %llu",
752 			    key->objectid, BTRFS_ROOT_TREE_DIR_OBJECTID,
753 			    BTRFS_FIRST_FREE_OBJECTID,
754 			    BTRFS_LAST_FREE_OBJECTID,
755 			    BTRFS_FREE_INO_OBJECTID);
756 		return -EUCLEAN;
757 	}
758 	if (key->offset != 0) {
759 		inode_item_err(fs_info, leaf, slot,
760 			"invalid key offset: has %llu expect 0",
761 			key->offset);
762 		return -EUCLEAN;
763 	}
764 	iitem = btrfs_item_ptr(leaf, slot, struct btrfs_inode_item);
765 
766 	/* Here we use super block generation + 1 to handle log tree */
767 	if (btrfs_inode_generation(leaf, iitem) > super_gen + 1) {
768 		inode_item_err(fs_info, leaf, slot,
769 			"invalid inode generation: has %llu expect (0, %llu]",
770 			       btrfs_inode_generation(leaf, iitem),
771 			       super_gen + 1);
772 		return -EUCLEAN;
773 	}
774 	/* Note for ROOT_TREE_DIR_ITEM, mkfs could set its transid 0 */
775 	if (btrfs_inode_transid(leaf, iitem) > super_gen + 1) {
776 		inode_item_err(fs_info, leaf, slot,
777 			"invalid inode generation: has %llu expect [0, %llu]",
778 			       btrfs_inode_transid(leaf, iitem), super_gen + 1);
779 		return -EUCLEAN;
780 	}
781 
782 	/*
783 	 * For size and nbytes it's better not to be too strict, as for dir
784 	 * item its size/nbytes can easily get wrong, but doesn't affect
785 	 * anything in the fs. So here we skip the check.
786 	 */
787 	mode = btrfs_inode_mode(leaf, iitem);
788 	if (mode & ~valid_mask) {
789 		inode_item_err(fs_info, leaf, slot,
790 			       "unknown mode bit detected: 0x%x",
791 			       mode & ~valid_mask);
792 		return -EUCLEAN;
793 	}
794 
795 	/*
796 	 * S_IFMT is not bit mapped so we can't completely rely on is_power_of_2,
797 	 * but is_power_of_2() can save us from checking FIFO/CHR/DIR/REG.
798 	 * Only needs to check BLK, LNK and SOCKS
799 	 */
800 	if (!is_power_of_2(mode & S_IFMT)) {
801 		if (!S_ISLNK(mode) && !S_ISBLK(mode) && !S_ISSOCK(mode)) {
802 			inode_item_err(fs_info, leaf, slot,
803 			"invalid mode: has 0%o expect valid S_IF* bit(s)",
804 				       mode & S_IFMT);
805 			return -EUCLEAN;
806 		}
807 	}
808 	if (S_ISDIR(mode) && btrfs_inode_nlink(leaf, iitem) > 1) {
809 		inode_item_err(fs_info, leaf, slot,
810 		       "invalid nlink: has %u expect no more than 1 for dir",
811 			btrfs_inode_nlink(leaf, iitem));
812 		return -EUCLEAN;
813 	}
814 	if (btrfs_inode_flags(leaf, iitem) & ~BTRFS_INODE_FLAG_MASK) {
815 		inode_item_err(fs_info, leaf, slot,
816 			       "unknown flags detected: 0x%llx",
817 			       btrfs_inode_flags(leaf, iitem) &
818 			       ~BTRFS_INODE_FLAG_MASK);
819 		return -EUCLEAN;
820 	}
821 	return 0;
822 }
823 
824 static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key,
825 			   int slot)
826 {
827 	struct btrfs_fs_info *fs_info = leaf->fs_info;
828 	struct btrfs_root_item ri;
829 	const u64 valid_root_flags = BTRFS_ROOT_SUBVOL_RDONLY |
830 				     BTRFS_ROOT_SUBVOL_DEAD;
831 
832 	/* No such tree id */
833 	if (key->objectid == 0) {
834 		generic_err(leaf, slot, "invalid root id 0");
835 		return -EUCLEAN;
836 	}
837 
838 	/*
839 	 * Some older kernel may create ROOT_ITEM with non-zero offset, so here
840 	 * we only check offset for reloc tree whose key->offset must be a
841 	 * valid tree.
842 	 */
843 	if (key->objectid == BTRFS_TREE_RELOC_OBJECTID && key->offset == 0) {
844 		generic_err(leaf, slot, "invalid root id 0 for reloc tree");
845 		return -EUCLEAN;
846 	}
847 
848 	if (btrfs_item_size_nr(leaf, slot) != sizeof(ri)) {
849 		generic_err(leaf, slot,
850 			    "invalid root item size, have %u expect %zu",
851 			    btrfs_item_size_nr(leaf, slot), sizeof(ri));
852 	}
853 
854 	read_extent_buffer(leaf, &ri, btrfs_item_ptr_offset(leaf, slot),
855 			   sizeof(ri));
856 
857 	/* Generation related */
858 	if (btrfs_root_generation(&ri) >
859 	    btrfs_super_generation(fs_info->super_copy) + 1) {
860 		generic_err(leaf, slot,
861 			"invalid root generation, have %llu expect (0, %llu]",
862 			    btrfs_root_generation(&ri),
863 			    btrfs_super_generation(fs_info->super_copy) + 1);
864 		return -EUCLEAN;
865 	}
866 	if (btrfs_root_generation_v2(&ri) >
867 	    btrfs_super_generation(fs_info->super_copy) + 1) {
868 		generic_err(leaf, slot,
869 		"invalid root v2 generation, have %llu expect (0, %llu]",
870 			    btrfs_root_generation_v2(&ri),
871 			    btrfs_super_generation(fs_info->super_copy) + 1);
872 		return -EUCLEAN;
873 	}
874 	if (btrfs_root_last_snapshot(&ri) >
875 	    btrfs_super_generation(fs_info->super_copy) + 1) {
876 		generic_err(leaf, slot,
877 		"invalid root last_snapshot, have %llu expect (0, %llu]",
878 			    btrfs_root_last_snapshot(&ri),
879 			    btrfs_super_generation(fs_info->super_copy) + 1);
880 		return -EUCLEAN;
881 	}
882 
883 	/* Alignment and level check */
884 	if (!IS_ALIGNED(btrfs_root_bytenr(&ri), fs_info->sectorsize)) {
885 		generic_err(leaf, slot,
886 		"invalid root bytenr, have %llu expect to be aligned to %u",
887 			    btrfs_root_bytenr(&ri), fs_info->sectorsize);
888 		return -EUCLEAN;
889 	}
890 	if (btrfs_root_level(&ri) >= BTRFS_MAX_LEVEL) {
891 		generic_err(leaf, slot,
892 			    "invalid root level, have %u expect [0, %u]",
893 			    btrfs_root_level(&ri), BTRFS_MAX_LEVEL - 1);
894 		return -EUCLEAN;
895 	}
896 	if (ri.drop_level >= BTRFS_MAX_LEVEL) {
897 		generic_err(leaf, slot,
898 			    "invalid root level, have %u expect [0, %u]",
899 			    ri.drop_level, BTRFS_MAX_LEVEL - 1);
900 		return -EUCLEAN;
901 	}
902 
903 	/* Flags check */
904 	if (btrfs_root_flags(&ri) & ~valid_root_flags) {
905 		generic_err(leaf, slot,
906 			    "invalid root flags, have 0x%llx expect mask 0x%llx",
907 			    btrfs_root_flags(&ri), valid_root_flags);
908 		return -EUCLEAN;
909 	}
910 	return 0;
911 }
912 
913 __printf(3,4)
914 __cold
915 static void extent_err(const struct extent_buffer *eb, int slot,
916 		       const char *fmt, ...)
917 {
918 	struct btrfs_key key;
919 	struct va_format vaf;
920 	va_list args;
921 	u64 bytenr;
922 	u64 len;
923 
924 	btrfs_item_key_to_cpu(eb, &key, slot);
925 	bytenr = key.objectid;
926 	if (key.type == BTRFS_METADATA_ITEM_KEY ||
927 	    key.type == BTRFS_TREE_BLOCK_REF_KEY ||
928 	    key.type == BTRFS_SHARED_BLOCK_REF_KEY)
929 		len = eb->fs_info->nodesize;
930 	else
931 		len = key.offset;
932 	va_start(args, fmt);
933 
934 	vaf.fmt = fmt;
935 	vaf.va = &args;
936 
937 	btrfs_crit(eb->fs_info,
938 	"corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV",
939 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
940 		eb->start, slot, bytenr, len, &vaf);
941 	va_end(args);
942 }
943 
944 static int check_extent_item(struct extent_buffer *leaf,
945 			     struct btrfs_key *key, int slot)
946 {
947 	struct btrfs_fs_info *fs_info = leaf->fs_info;
948 	struct btrfs_extent_item *ei;
949 	bool is_tree_block = false;
950 	unsigned long ptr;	/* Current pointer inside inline refs */
951 	unsigned long end;	/* Extent item end */
952 	const u32 item_size = btrfs_item_size_nr(leaf, slot);
953 	u64 flags;
954 	u64 generation;
955 	u64 total_refs;		/* Total refs in btrfs_extent_item */
956 	u64 inline_refs = 0;	/* found total inline refs */
957 
958 	if (key->type == BTRFS_METADATA_ITEM_KEY &&
959 	    !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
960 		generic_err(leaf, slot,
961 "invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled");
962 		return -EUCLEAN;
963 	}
964 	/* key->objectid is the bytenr for both key types */
965 	if (!IS_ALIGNED(key->objectid, fs_info->sectorsize)) {
966 		generic_err(leaf, slot,
967 		"invalid key objectid, have %llu expect to be aligned to %u",
968 			   key->objectid, fs_info->sectorsize);
969 		return -EUCLEAN;
970 	}
971 
972 	/* key->offset is tree level for METADATA_ITEM_KEY */
973 	if (key->type == BTRFS_METADATA_ITEM_KEY &&
974 	    key->offset >= BTRFS_MAX_LEVEL) {
975 		extent_err(leaf, slot,
976 			   "invalid tree level, have %llu expect [0, %u]",
977 			   key->offset, BTRFS_MAX_LEVEL - 1);
978 		return -EUCLEAN;
979 	}
980 
981 	/*
982 	 * EXTENT/METADATA_ITEM consists of:
983 	 * 1) One btrfs_extent_item
984 	 *    Records the total refs, type and generation of the extent.
985 	 *
986 	 * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only)
987 	 *    Records the first key and level of the tree block.
988 	 *
989 	 * 2) Zero or more btrfs_extent_inline_ref(s)
990 	 *    Each inline ref has one btrfs_extent_inline_ref shows:
991 	 *    2.1) The ref type, one of the 4
992 	 *         TREE_BLOCK_REF	Tree block only
993 	 *         SHARED_BLOCK_REF	Tree block only
994 	 *         EXTENT_DATA_REF	Data only
995 	 *         SHARED_DATA_REF	Data only
996 	 *    2.2) Ref type specific data
997 	 *         Either using btrfs_extent_inline_ref::offset, or specific
998 	 *         data structure.
999 	 */
1000 	if (item_size < sizeof(*ei)) {
1001 		extent_err(leaf, slot,
1002 			   "invalid item size, have %u expect [%zu, %u)",
1003 			   item_size, sizeof(*ei),
1004 			   BTRFS_LEAF_DATA_SIZE(fs_info));
1005 		return -EUCLEAN;
1006 	}
1007 	end = item_size + btrfs_item_ptr_offset(leaf, slot);
1008 
1009 	/* Checks against extent_item */
1010 	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
1011 	flags = btrfs_extent_flags(leaf, ei);
1012 	total_refs = btrfs_extent_refs(leaf, ei);
1013 	generation = btrfs_extent_generation(leaf, ei);
1014 	if (generation > btrfs_super_generation(fs_info->super_copy) + 1) {
1015 		extent_err(leaf, slot,
1016 			   "invalid generation, have %llu expect (0, %llu]",
1017 			   generation,
1018 			   btrfs_super_generation(fs_info->super_copy) + 1);
1019 		return -EUCLEAN;
1020 	}
1021 	if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA |
1022 				    BTRFS_EXTENT_FLAG_TREE_BLOCK))) {
1023 		extent_err(leaf, slot,
1024 		"invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx",
1025 			flags, BTRFS_EXTENT_FLAG_DATA |
1026 			BTRFS_EXTENT_FLAG_TREE_BLOCK);
1027 		return -EUCLEAN;
1028 	}
1029 	is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK);
1030 	if (is_tree_block) {
1031 		if (key->type == BTRFS_EXTENT_ITEM_KEY &&
1032 		    key->offset != fs_info->nodesize) {
1033 			extent_err(leaf, slot,
1034 				   "invalid extent length, have %llu expect %u",
1035 				   key->offset, fs_info->nodesize);
1036 			return -EUCLEAN;
1037 		}
1038 	} else {
1039 		if (key->type != BTRFS_EXTENT_ITEM_KEY) {
1040 			extent_err(leaf, slot,
1041 			"invalid key type, have %u expect %u for data backref",
1042 				   key->type, BTRFS_EXTENT_ITEM_KEY);
1043 			return -EUCLEAN;
1044 		}
1045 		if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) {
1046 			extent_err(leaf, slot,
1047 			"invalid extent length, have %llu expect aligned to %u",
1048 				   key->offset, fs_info->sectorsize);
1049 			return -EUCLEAN;
1050 		}
1051 	}
1052 	ptr = (unsigned long)(struct btrfs_extent_item *)(ei + 1);
1053 
1054 	/* Check the special case of btrfs_tree_block_info */
1055 	if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) {
1056 		struct btrfs_tree_block_info *info;
1057 
1058 		info = (struct btrfs_tree_block_info *)ptr;
1059 		if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) {
1060 			extent_err(leaf, slot,
1061 			"invalid tree block info level, have %u expect [0, %u]",
1062 				   btrfs_tree_block_level(leaf, info),
1063 				   BTRFS_MAX_LEVEL - 1);
1064 			return -EUCLEAN;
1065 		}
1066 		ptr = (unsigned long)(struct btrfs_tree_block_info *)(info + 1);
1067 	}
1068 
1069 	/* Check inline refs */
1070 	while (ptr < end) {
1071 		struct btrfs_extent_inline_ref *iref;
1072 		struct btrfs_extent_data_ref *dref;
1073 		struct btrfs_shared_data_ref *sref;
1074 		u64 dref_offset;
1075 		u64 inline_offset;
1076 		u8 inline_type;
1077 
1078 		if (ptr + sizeof(*iref) > end) {
1079 			extent_err(leaf, slot,
1080 "inline ref item overflows extent item, ptr %lu iref size %zu end %lu",
1081 				   ptr, sizeof(*iref), end);
1082 			return -EUCLEAN;
1083 		}
1084 		iref = (struct btrfs_extent_inline_ref *)ptr;
1085 		inline_type = btrfs_extent_inline_ref_type(leaf, iref);
1086 		inline_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1087 		if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) {
1088 			extent_err(leaf, slot,
1089 "inline ref item overflows extent item, ptr %lu iref size %u end %lu",
1090 				   ptr, inline_type, end);
1091 			return -EUCLEAN;
1092 		}
1093 
1094 		switch (inline_type) {
1095 		/* inline_offset is subvolid of the owner, no need to check */
1096 		case BTRFS_TREE_BLOCK_REF_KEY:
1097 			inline_refs++;
1098 			break;
1099 		/* Contains parent bytenr */
1100 		case BTRFS_SHARED_BLOCK_REF_KEY:
1101 			if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
1102 				extent_err(leaf, slot,
1103 		"invalid tree parent bytenr, have %llu expect aligned to %u",
1104 					   inline_offset, fs_info->sectorsize);
1105 				return -EUCLEAN;
1106 			}
1107 			inline_refs++;
1108 			break;
1109 		/*
1110 		 * Contains owner subvolid, owner key objectid, adjusted offset.
1111 		 * The only obvious corruption can happen in that offset.
1112 		 */
1113 		case BTRFS_EXTENT_DATA_REF_KEY:
1114 			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1115 			dref_offset = btrfs_extent_data_ref_offset(leaf, dref);
1116 			if (!IS_ALIGNED(dref_offset, fs_info->sectorsize)) {
1117 				extent_err(leaf, slot,
1118 		"invalid data ref offset, have %llu expect aligned to %u",
1119 					   dref_offset, fs_info->sectorsize);
1120 				return -EUCLEAN;
1121 			}
1122 			inline_refs += btrfs_extent_data_ref_count(leaf, dref);
1123 			break;
1124 		/* Contains parent bytenr and ref count */
1125 		case BTRFS_SHARED_DATA_REF_KEY:
1126 			sref = (struct btrfs_shared_data_ref *)(iref + 1);
1127 			if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
1128 				extent_err(leaf, slot,
1129 		"invalid data parent bytenr, have %llu expect aligned to %u",
1130 					   inline_offset, fs_info->sectorsize);
1131 				return -EUCLEAN;
1132 			}
1133 			inline_refs += btrfs_shared_data_ref_count(leaf, sref);
1134 			break;
1135 		default:
1136 			extent_err(leaf, slot, "unknown inline ref type: %u",
1137 				   inline_type);
1138 			return -EUCLEAN;
1139 		}
1140 		ptr += btrfs_extent_inline_ref_size(inline_type);
1141 	}
1142 	/* No padding is allowed */
1143 	if (ptr != end) {
1144 		extent_err(leaf, slot,
1145 			   "invalid extent item size, padding bytes found");
1146 		return -EUCLEAN;
1147 	}
1148 
1149 	/* Finally, check the inline refs against total refs */
1150 	if (inline_refs > total_refs) {
1151 		extent_err(leaf, slot,
1152 			"invalid extent refs, have %llu expect >= inline %llu",
1153 			   total_refs, inline_refs);
1154 		return -EUCLEAN;
1155 	}
1156 	return 0;
1157 }
1158 
1159 static int check_simple_keyed_refs(struct extent_buffer *leaf,
1160 				   struct btrfs_key *key, int slot)
1161 {
1162 	u32 expect_item_size = 0;
1163 
1164 	if (key->type == BTRFS_SHARED_DATA_REF_KEY)
1165 		expect_item_size = sizeof(struct btrfs_shared_data_ref);
1166 
1167 	if (btrfs_item_size_nr(leaf, slot) != expect_item_size) {
1168 		generic_err(leaf, slot,
1169 		"invalid item size, have %u expect %u for key type %u",
1170 			    btrfs_item_size_nr(leaf, slot),
1171 			    expect_item_size, key->type);
1172 		return -EUCLEAN;
1173 	}
1174 	if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) {
1175 		generic_err(leaf, slot,
1176 "invalid key objectid for shared block ref, have %llu expect aligned to %u",
1177 			    key->objectid, leaf->fs_info->sectorsize);
1178 		return -EUCLEAN;
1179 	}
1180 	if (key->type != BTRFS_TREE_BLOCK_REF_KEY &&
1181 	    !IS_ALIGNED(key->offset, leaf->fs_info->sectorsize)) {
1182 		extent_err(leaf, slot,
1183 		"invalid tree parent bytenr, have %llu expect aligned to %u",
1184 			   key->offset, leaf->fs_info->sectorsize);
1185 		return -EUCLEAN;
1186 	}
1187 	return 0;
1188 }
1189 
1190 static int check_extent_data_ref(struct extent_buffer *leaf,
1191 				 struct btrfs_key *key, int slot)
1192 {
1193 	struct btrfs_extent_data_ref *dref;
1194 	unsigned long ptr = btrfs_item_ptr_offset(leaf, slot);
1195 	const unsigned long end = ptr + btrfs_item_size_nr(leaf, slot);
1196 
1197 	if (btrfs_item_size_nr(leaf, slot) % sizeof(*dref) != 0) {
1198 		generic_err(leaf, slot,
1199 	"invalid item size, have %u expect aligned to %zu for key type %u",
1200 			    btrfs_item_size_nr(leaf, slot),
1201 			    sizeof(*dref), key->type);
1202 	}
1203 	if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) {
1204 		generic_err(leaf, slot,
1205 "invalid key objectid for shared block ref, have %llu expect aligned to %u",
1206 			    key->objectid, leaf->fs_info->sectorsize);
1207 		return -EUCLEAN;
1208 	}
1209 	for (; ptr < end; ptr += sizeof(*dref)) {
1210 		u64 root_objectid;
1211 		u64 owner;
1212 		u64 offset;
1213 		u64 hash;
1214 
1215 		dref = (struct btrfs_extent_data_ref *)ptr;
1216 		root_objectid = btrfs_extent_data_ref_root(leaf, dref);
1217 		owner = btrfs_extent_data_ref_objectid(leaf, dref);
1218 		offset = btrfs_extent_data_ref_offset(leaf, dref);
1219 		hash = hash_extent_data_ref(root_objectid, owner, offset);
1220 		if (hash != key->offset) {
1221 			extent_err(leaf, slot,
1222 	"invalid extent data ref hash, item has 0x%016llx key has 0x%016llx",
1223 				   hash, key->offset);
1224 			return -EUCLEAN;
1225 		}
1226 		if (!IS_ALIGNED(offset, leaf->fs_info->sectorsize)) {
1227 			extent_err(leaf, slot,
1228 	"invalid extent data backref offset, have %llu expect aligned to %u",
1229 				   offset, leaf->fs_info->sectorsize);
1230 		}
1231 	}
1232 	return 0;
1233 }
1234 
1235 /*
1236  * Common point to switch the item-specific validation.
1237  */
1238 static int check_leaf_item(struct extent_buffer *leaf,
1239 			   struct btrfs_key *key, int slot,
1240 			   struct btrfs_key *prev_key)
1241 {
1242 	int ret = 0;
1243 	struct btrfs_chunk *chunk;
1244 
1245 	switch (key->type) {
1246 	case BTRFS_EXTENT_DATA_KEY:
1247 		ret = check_extent_data_item(leaf, key, slot, prev_key);
1248 		break;
1249 	case BTRFS_EXTENT_CSUM_KEY:
1250 		ret = check_csum_item(leaf, key, slot);
1251 		break;
1252 	case BTRFS_DIR_ITEM_KEY:
1253 	case BTRFS_DIR_INDEX_KEY:
1254 	case BTRFS_XATTR_ITEM_KEY:
1255 		ret = check_dir_item(leaf, key, slot);
1256 		break;
1257 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
1258 		ret = check_block_group_item(leaf, key, slot);
1259 		break;
1260 	case BTRFS_CHUNK_ITEM_KEY:
1261 		chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
1262 		ret = btrfs_check_chunk_valid(leaf, chunk, key->offset);
1263 		break;
1264 	case BTRFS_DEV_ITEM_KEY:
1265 		ret = check_dev_item(leaf, key, slot);
1266 		break;
1267 	case BTRFS_INODE_ITEM_KEY:
1268 		ret = check_inode_item(leaf, key, slot);
1269 		break;
1270 	case BTRFS_ROOT_ITEM_KEY:
1271 		ret = check_root_item(leaf, key, slot);
1272 		break;
1273 	case BTRFS_EXTENT_ITEM_KEY:
1274 	case BTRFS_METADATA_ITEM_KEY:
1275 		ret = check_extent_item(leaf, key, slot);
1276 		break;
1277 	case BTRFS_TREE_BLOCK_REF_KEY:
1278 	case BTRFS_SHARED_DATA_REF_KEY:
1279 	case BTRFS_SHARED_BLOCK_REF_KEY:
1280 		ret = check_simple_keyed_refs(leaf, key, slot);
1281 		break;
1282 	case BTRFS_EXTENT_DATA_REF_KEY:
1283 		ret = check_extent_data_ref(leaf, key, slot);
1284 		break;
1285 	}
1286 	return ret;
1287 }
1288 
1289 static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
1290 {
1291 	struct btrfs_fs_info *fs_info = leaf->fs_info;
1292 	/* No valid key type is 0, so all key should be larger than this key */
1293 	struct btrfs_key prev_key = {0, 0, 0};
1294 	struct btrfs_key key;
1295 	u32 nritems = btrfs_header_nritems(leaf);
1296 	int slot;
1297 
1298 	if (btrfs_header_level(leaf) != 0) {
1299 		generic_err(leaf, 0,
1300 			"invalid level for leaf, have %d expect 0",
1301 			btrfs_header_level(leaf));
1302 		return -EUCLEAN;
1303 	}
1304 
1305 	/*
1306 	 * Extent buffers from a relocation tree have a owner field that
1307 	 * corresponds to the subvolume tree they are based on. So just from an
1308 	 * extent buffer alone we can not find out what is the id of the
1309 	 * corresponding subvolume tree, so we can not figure out if the extent
1310 	 * buffer corresponds to the root of the relocation tree or not. So
1311 	 * skip this check for relocation trees.
1312 	 */
1313 	if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
1314 		u64 owner = btrfs_header_owner(leaf);
1315 
1316 		/* These trees must never be empty */
1317 		if (owner == BTRFS_ROOT_TREE_OBJECTID ||
1318 		    owner == BTRFS_CHUNK_TREE_OBJECTID ||
1319 		    owner == BTRFS_EXTENT_TREE_OBJECTID ||
1320 		    owner == BTRFS_DEV_TREE_OBJECTID ||
1321 		    owner == BTRFS_FS_TREE_OBJECTID ||
1322 		    owner == BTRFS_DATA_RELOC_TREE_OBJECTID) {
1323 			generic_err(leaf, 0,
1324 			"invalid root, root %llu must never be empty",
1325 				    owner);
1326 			return -EUCLEAN;
1327 		}
1328 		/* Unknown tree */
1329 		if (owner == 0) {
1330 			generic_err(leaf, 0,
1331 				"invalid owner, root 0 is not defined");
1332 			return -EUCLEAN;
1333 		}
1334 		return 0;
1335 	}
1336 
1337 	if (nritems == 0)
1338 		return 0;
1339 
1340 	/*
1341 	 * Check the following things to make sure this is a good leaf, and
1342 	 * leaf users won't need to bother with similar sanity checks:
1343 	 *
1344 	 * 1) key ordering
1345 	 * 2) item offset and size
1346 	 *    No overlap, no hole, all inside the leaf.
1347 	 * 3) item content
1348 	 *    If possible, do comprehensive sanity check.
1349 	 *    NOTE: All checks must only rely on the item data itself.
1350 	 */
1351 	for (slot = 0; slot < nritems; slot++) {
1352 		u32 item_end_expected;
1353 		int ret;
1354 
1355 		btrfs_item_key_to_cpu(leaf, &key, slot);
1356 
1357 		/* Make sure the keys are in the right order */
1358 		if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
1359 			generic_err(leaf, slot,
1360 	"bad key order, prev (%llu %u %llu) current (%llu %u %llu)",
1361 				prev_key.objectid, prev_key.type,
1362 				prev_key.offset, key.objectid, key.type,
1363 				key.offset);
1364 			return -EUCLEAN;
1365 		}
1366 
1367 		/*
1368 		 * Make sure the offset and ends are right, remember that the
1369 		 * item data starts at the end of the leaf and grows towards the
1370 		 * front.
1371 		 */
1372 		if (slot == 0)
1373 			item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
1374 		else
1375 			item_end_expected = btrfs_item_offset_nr(leaf,
1376 								 slot - 1);
1377 		if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
1378 			generic_err(leaf, slot,
1379 				"unexpected item end, have %u expect %u",
1380 				btrfs_item_end_nr(leaf, slot),
1381 				item_end_expected);
1382 			return -EUCLEAN;
1383 		}
1384 
1385 		/*
1386 		 * Check to make sure that we don't point outside of the leaf,
1387 		 * just in case all the items are consistent to each other, but
1388 		 * all point outside of the leaf.
1389 		 */
1390 		if (btrfs_item_end_nr(leaf, slot) >
1391 		    BTRFS_LEAF_DATA_SIZE(fs_info)) {
1392 			generic_err(leaf, slot,
1393 			"slot end outside of leaf, have %u expect range [0, %u]",
1394 				btrfs_item_end_nr(leaf, slot),
1395 				BTRFS_LEAF_DATA_SIZE(fs_info));
1396 			return -EUCLEAN;
1397 		}
1398 
1399 		/* Also check if the item pointer overlaps with btrfs item. */
1400 		if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
1401 		    btrfs_item_ptr_offset(leaf, slot)) {
1402 			generic_err(leaf, slot,
1403 		"slot overlaps with its data, item end %lu data start %lu",
1404 				btrfs_item_nr_offset(slot) +
1405 				sizeof(struct btrfs_item),
1406 				btrfs_item_ptr_offset(leaf, slot));
1407 			return -EUCLEAN;
1408 		}
1409 
1410 		if (check_item_data) {
1411 			/*
1412 			 * Check if the item size and content meet other
1413 			 * criteria
1414 			 */
1415 			ret = check_leaf_item(leaf, &key, slot, &prev_key);
1416 			if (ret < 0)
1417 				return ret;
1418 		}
1419 
1420 		prev_key.objectid = key.objectid;
1421 		prev_key.type = key.type;
1422 		prev_key.offset = key.offset;
1423 	}
1424 
1425 	return 0;
1426 }
1427 
1428 int btrfs_check_leaf_full(struct extent_buffer *leaf)
1429 {
1430 	return check_leaf(leaf, true);
1431 }
1432 ALLOW_ERROR_INJECTION(btrfs_check_leaf_full, ERRNO);
1433 
1434 int btrfs_check_leaf_relaxed(struct extent_buffer *leaf)
1435 {
1436 	return check_leaf(leaf, false);
1437 }
1438 
1439 int btrfs_check_node(struct extent_buffer *node)
1440 {
1441 	struct btrfs_fs_info *fs_info = node->fs_info;
1442 	unsigned long nr = btrfs_header_nritems(node);
1443 	struct btrfs_key key, next_key;
1444 	int slot;
1445 	int level = btrfs_header_level(node);
1446 	u64 bytenr;
1447 	int ret = 0;
1448 
1449 	if (level <= 0 || level >= BTRFS_MAX_LEVEL) {
1450 		generic_err(node, 0,
1451 			"invalid level for node, have %d expect [1, %d]",
1452 			level, BTRFS_MAX_LEVEL - 1);
1453 		return -EUCLEAN;
1454 	}
1455 	if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(fs_info)) {
1456 		btrfs_crit(fs_info,
1457 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]",
1458 			   btrfs_header_owner(node), node->start,
1459 			   nr == 0 ? "small" : "large", nr,
1460 			   BTRFS_NODEPTRS_PER_BLOCK(fs_info));
1461 		return -EUCLEAN;
1462 	}
1463 
1464 	for (slot = 0; slot < nr - 1; slot++) {
1465 		bytenr = btrfs_node_blockptr(node, slot);
1466 		btrfs_node_key_to_cpu(node, &key, slot);
1467 		btrfs_node_key_to_cpu(node, &next_key, slot + 1);
1468 
1469 		if (!bytenr) {
1470 			generic_err(node, slot,
1471 				"invalid NULL node pointer");
1472 			ret = -EUCLEAN;
1473 			goto out;
1474 		}
1475 		if (!IS_ALIGNED(bytenr, fs_info->sectorsize)) {
1476 			generic_err(node, slot,
1477 			"unaligned pointer, have %llu should be aligned to %u",
1478 				bytenr, fs_info->sectorsize);
1479 			ret = -EUCLEAN;
1480 			goto out;
1481 		}
1482 
1483 		if (btrfs_comp_cpu_keys(&key, &next_key) >= 0) {
1484 			generic_err(node, slot,
1485 	"bad key order, current (%llu %u %llu) next (%llu %u %llu)",
1486 				key.objectid, key.type, key.offset,
1487 				next_key.objectid, next_key.type,
1488 				next_key.offset);
1489 			ret = -EUCLEAN;
1490 			goto out;
1491 		}
1492 	}
1493 out:
1494 	return ret;
1495 }
1496 ALLOW_ERROR_INJECTION(btrfs_check_node, ERRNO);
1497