xref: /openbmc/linux/fs/btrfs/tree-checker.c (revision fb8d6c8d)
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_dev_item *ditem;
690 
691 	if (key->objectid != BTRFS_DEV_ITEMS_OBJECTID) {
692 		dev_item_err(leaf, slot,
693 			     "invalid objectid: has=%llu expect=%llu",
694 			     key->objectid, BTRFS_DEV_ITEMS_OBJECTID);
695 		return -EUCLEAN;
696 	}
697 	ditem = btrfs_item_ptr(leaf, slot, struct btrfs_dev_item);
698 	if (btrfs_device_id(leaf, ditem) != key->offset) {
699 		dev_item_err(leaf, slot,
700 			     "devid mismatch: key has=%llu item has=%llu",
701 			     key->offset, btrfs_device_id(leaf, ditem));
702 		return -EUCLEAN;
703 	}
704 
705 	/*
706 	 * For device total_bytes, we don't have reliable way to check it, as
707 	 * it can be 0 for device removal. Device size check can only be done
708 	 * by dev extents check.
709 	 */
710 	if (btrfs_device_bytes_used(leaf, ditem) >
711 	    btrfs_device_total_bytes(leaf, ditem)) {
712 		dev_item_err(leaf, slot,
713 			     "invalid bytes used: have %llu expect [0, %llu]",
714 			     btrfs_device_bytes_used(leaf, ditem),
715 			     btrfs_device_total_bytes(leaf, ditem));
716 		return -EUCLEAN;
717 	}
718 	/*
719 	 * Remaining members like io_align/type/gen/dev_group aren't really
720 	 * utilized.  Skip them to make later usage of them easier.
721 	 */
722 	return 0;
723 }
724 
725 /* Inode item error output has the same format as dir_item_err() */
726 #define inode_item_err(fs_info, eb, slot, fmt, ...)			\
727 	dir_item_err(eb, slot, fmt, __VA_ARGS__)
728 
729 static int check_inode_item(struct extent_buffer *leaf,
730 			    struct btrfs_key *key, int slot)
731 {
732 	struct btrfs_fs_info *fs_info = leaf->fs_info;
733 	struct btrfs_inode_item *iitem;
734 	u64 super_gen = btrfs_super_generation(fs_info->super_copy);
735 	u32 valid_mask = (S_IFMT | S_ISUID | S_ISGID | S_ISVTX | 0777);
736 	u32 mode;
737 
738 	if ((key->objectid < BTRFS_FIRST_FREE_OBJECTID ||
739 	     key->objectid > BTRFS_LAST_FREE_OBJECTID) &&
740 	    key->objectid != BTRFS_ROOT_TREE_DIR_OBJECTID &&
741 	    key->objectid != BTRFS_FREE_INO_OBJECTID) {
742 		generic_err(leaf, slot,
743 	"invalid key objectid: has %llu expect %llu or [%llu, %llu] or %llu",
744 			    key->objectid, BTRFS_ROOT_TREE_DIR_OBJECTID,
745 			    BTRFS_FIRST_FREE_OBJECTID,
746 			    BTRFS_LAST_FREE_OBJECTID,
747 			    BTRFS_FREE_INO_OBJECTID);
748 		return -EUCLEAN;
749 	}
750 	if (key->offset != 0) {
751 		inode_item_err(fs_info, leaf, slot,
752 			"invalid key offset: has %llu expect 0",
753 			key->offset);
754 		return -EUCLEAN;
755 	}
756 	iitem = btrfs_item_ptr(leaf, slot, struct btrfs_inode_item);
757 
758 	/* Here we use super block generation + 1 to handle log tree */
759 	if (btrfs_inode_generation(leaf, iitem) > super_gen + 1) {
760 		inode_item_err(fs_info, leaf, slot,
761 			"invalid inode generation: has %llu expect (0, %llu]",
762 			       btrfs_inode_generation(leaf, iitem),
763 			       super_gen + 1);
764 		return -EUCLEAN;
765 	}
766 	/* Note for ROOT_TREE_DIR_ITEM, mkfs could set its transid 0 */
767 	if (btrfs_inode_transid(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_transid(leaf, iitem), super_gen + 1);
771 		return -EUCLEAN;
772 	}
773 
774 	/*
775 	 * For size and nbytes it's better not to be too strict, as for dir
776 	 * item its size/nbytes can easily get wrong, but doesn't affect
777 	 * anything in the fs. So here we skip the check.
778 	 */
779 	mode = btrfs_inode_mode(leaf, iitem);
780 	if (mode & ~valid_mask) {
781 		inode_item_err(fs_info, leaf, slot,
782 			       "unknown mode bit detected: 0x%x",
783 			       mode & ~valid_mask);
784 		return -EUCLEAN;
785 	}
786 
787 	/*
788 	 * S_IFMT is not bit mapped so we can't completely rely on is_power_of_2,
789 	 * but is_power_of_2() can save us from checking FIFO/CHR/DIR/REG.
790 	 * Only needs to check BLK, LNK and SOCKS
791 	 */
792 	if (!is_power_of_2(mode & S_IFMT)) {
793 		if (!S_ISLNK(mode) && !S_ISBLK(mode) && !S_ISSOCK(mode)) {
794 			inode_item_err(fs_info, leaf, slot,
795 			"invalid mode: has 0%o expect valid S_IF* bit(s)",
796 				       mode & S_IFMT);
797 			return -EUCLEAN;
798 		}
799 	}
800 	if (S_ISDIR(mode) && btrfs_inode_nlink(leaf, iitem) > 1) {
801 		inode_item_err(fs_info, leaf, slot,
802 		       "invalid nlink: has %u expect no more than 1 for dir",
803 			btrfs_inode_nlink(leaf, iitem));
804 		return -EUCLEAN;
805 	}
806 	if (btrfs_inode_flags(leaf, iitem) & ~BTRFS_INODE_FLAG_MASK) {
807 		inode_item_err(fs_info, leaf, slot,
808 			       "unknown flags detected: 0x%llx",
809 			       btrfs_inode_flags(leaf, iitem) &
810 			       ~BTRFS_INODE_FLAG_MASK);
811 		return -EUCLEAN;
812 	}
813 	return 0;
814 }
815 
816 static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key,
817 			   int slot)
818 {
819 	struct btrfs_fs_info *fs_info = leaf->fs_info;
820 	struct btrfs_root_item ri;
821 	const u64 valid_root_flags = BTRFS_ROOT_SUBVOL_RDONLY |
822 				     BTRFS_ROOT_SUBVOL_DEAD;
823 
824 	/* No such tree id */
825 	if (key->objectid == 0) {
826 		generic_err(leaf, slot, "invalid root id 0");
827 		return -EUCLEAN;
828 	}
829 
830 	/*
831 	 * Some older kernel may create ROOT_ITEM with non-zero offset, so here
832 	 * we only check offset for reloc tree whose key->offset must be a
833 	 * valid tree.
834 	 */
835 	if (key->objectid == BTRFS_TREE_RELOC_OBJECTID && key->offset == 0) {
836 		generic_err(leaf, slot, "invalid root id 0 for reloc tree");
837 		return -EUCLEAN;
838 	}
839 
840 	if (btrfs_item_size_nr(leaf, slot) != sizeof(ri)) {
841 		generic_err(leaf, slot,
842 			    "invalid root item size, have %u expect %zu",
843 			    btrfs_item_size_nr(leaf, slot), sizeof(ri));
844 	}
845 
846 	read_extent_buffer(leaf, &ri, btrfs_item_ptr_offset(leaf, slot),
847 			   sizeof(ri));
848 
849 	/* Generation related */
850 	if (btrfs_root_generation(&ri) >
851 	    btrfs_super_generation(fs_info->super_copy) + 1) {
852 		generic_err(leaf, slot,
853 			"invalid root generation, have %llu expect (0, %llu]",
854 			    btrfs_root_generation(&ri),
855 			    btrfs_super_generation(fs_info->super_copy) + 1);
856 		return -EUCLEAN;
857 	}
858 	if (btrfs_root_generation_v2(&ri) >
859 	    btrfs_super_generation(fs_info->super_copy) + 1) {
860 		generic_err(leaf, slot,
861 		"invalid root v2 generation, have %llu expect (0, %llu]",
862 			    btrfs_root_generation_v2(&ri),
863 			    btrfs_super_generation(fs_info->super_copy) + 1);
864 		return -EUCLEAN;
865 	}
866 	if (btrfs_root_last_snapshot(&ri) >
867 	    btrfs_super_generation(fs_info->super_copy) + 1) {
868 		generic_err(leaf, slot,
869 		"invalid root last_snapshot, have %llu expect (0, %llu]",
870 			    btrfs_root_last_snapshot(&ri),
871 			    btrfs_super_generation(fs_info->super_copy) + 1);
872 		return -EUCLEAN;
873 	}
874 
875 	/* Alignment and level check */
876 	if (!IS_ALIGNED(btrfs_root_bytenr(&ri), fs_info->sectorsize)) {
877 		generic_err(leaf, slot,
878 		"invalid root bytenr, have %llu expect to be aligned to %u",
879 			    btrfs_root_bytenr(&ri), fs_info->sectorsize);
880 		return -EUCLEAN;
881 	}
882 	if (btrfs_root_level(&ri) >= BTRFS_MAX_LEVEL) {
883 		generic_err(leaf, slot,
884 			    "invalid root level, have %u expect [0, %u]",
885 			    btrfs_root_level(&ri), BTRFS_MAX_LEVEL - 1);
886 		return -EUCLEAN;
887 	}
888 	if (ri.drop_level >= BTRFS_MAX_LEVEL) {
889 		generic_err(leaf, slot,
890 			    "invalid root level, have %u expect [0, %u]",
891 			    ri.drop_level, BTRFS_MAX_LEVEL - 1);
892 		return -EUCLEAN;
893 	}
894 
895 	/* Flags check */
896 	if (btrfs_root_flags(&ri) & ~valid_root_flags) {
897 		generic_err(leaf, slot,
898 			    "invalid root flags, have 0x%llx expect mask 0x%llx",
899 			    btrfs_root_flags(&ri), valid_root_flags);
900 		return -EUCLEAN;
901 	}
902 	return 0;
903 }
904 
905 __printf(3,4)
906 __cold
907 static void extent_err(const struct extent_buffer *eb, int slot,
908 		       const char *fmt, ...)
909 {
910 	struct btrfs_key key;
911 	struct va_format vaf;
912 	va_list args;
913 	u64 bytenr;
914 	u64 len;
915 
916 	btrfs_item_key_to_cpu(eb, &key, slot);
917 	bytenr = key.objectid;
918 	if (key.type == BTRFS_METADATA_ITEM_KEY ||
919 	    key.type == BTRFS_TREE_BLOCK_REF_KEY ||
920 	    key.type == BTRFS_SHARED_BLOCK_REF_KEY)
921 		len = eb->fs_info->nodesize;
922 	else
923 		len = key.offset;
924 	va_start(args, fmt);
925 
926 	vaf.fmt = fmt;
927 	vaf.va = &args;
928 
929 	btrfs_crit(eb->fs_info,
930 	"corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV",
931 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
932 		eb->start, slot, bytenr, len, &vaf);
933 	va_end(args);
934 }
935 
936 static int check_extent_item(struct extent_buffer *leaf,
937 			     struct btrfs_key *key, int slot)
938 {
939 	struct btrfs_fs_info *fs_info = leaf->fs_info;
940 	struct btrfs_extent_item *ei;
941 	bool is_tree_block = false;
942 	unsigned long ptr;	/* Current pointer inside inline refs */
943 	unsigned long end;	/* Extent item end */
944 	const u32 item_size = btrfs_item_size_nr(leaf, slot);
945 	u64 flags;
946 	u64 generation;
947 	u64 total_refs;		/* Total refs in btrfs_extent_item */
948 	u64 inline_refs = 0;	/* found total inline refs */
949 
950 	if (key->type == BTRFS_METADATA_ITEM_KEY &&
951 	    !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
952 		generic_err(leaf, slot,
953 "invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled");
954 		return -EUCLEAN;
955 	}
956 	/* key->objectid is the bytenr for both key types */
957 	if (!IS_ALIGNED(key->objectid, fs_info->sectorsize)) {
958 		generic_err(leaf, slot,
959 		"invalid key objectid, have %llu expect to be aligned to %u",
960 			   key->objectid, fs_info->sectorsize);
961 		return -EUCLEAN;
962 	}
963 
964 	/* key->offset is tree level for METADATA_ITEM_KEY */
965 	if (key->type == BTRFS_METADATA_ITEM_KEY &&
966 	    key->offset >= BTRFS_MAX_LEVEL) {
967 		extent_err(leaf, slot,
968 			   "invalid tree level, have %llu expect [0, %u]",
969 			   key->offset, BTRFS_MAX_LEVEL - 1);
970 		return -EUCLEAN;
971 	}
972 
973 	/*
974 	 * EXTENT/METADATA_ITEM consists of:
975 	 * 1) One btrfs_extent_item
976 	 *    Records the total refs, type and generation of the extent.
977 	 *
978 	 * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only)
979 	 *    Records the first key and level of the tree block.
980 	 *
981 	 * 2) Zero or more btrfs_extent_inline_ref(s)
982 	 *    Each inline ref has one btrfs_extent_inline_ref shows:
983 	 *    2.1) The ref type, one of the 4
984 	 *         TREE_BLOCK_REF	Tree block only
985 	 *         SHARED_BLOCK_REF	Tree block only
986 	 *         EXTENT_DATA_REF	Data only
987 	 *         SHARED_DATA_REF	Data only
988 	 *    2.2) Ref type specific data
989 	 *         Either using btrfs_extent_inline_ref::offset, or specific
990 	 *         data structure.
991 	 */
992 	if (item_size < sizeof(*ei)) {
993 		extent_err(leaf, slot,
994 			   "invalid item size, have %u expect [%zu, %u)",
995 			   item_size, sizeof(*ei),
996 			   BTRFS_LEAF_DATA_SIZE(fs_info));
997 		return -EUCLEAN;
998 	}
999 	end = item_size + btrfs_item_ptr_offset(leaf, slot);
1000 
1001 	/* Checks against extent_item */
1002 	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
1003 	flags = btrfs_extent_flags(leaf, ei);
1004 	total_refs = btrfs_extent_refs(leaf, ei);
1005 	generation = btrfs_extent_generation(leaf, ei);
1006 	if (generation > btrfs_super_generation(fs_info->super_copy) + 1) {
1007 		extent_err(leaf, slot,
1008 			   "invalid generation, have %llu expect (0, %llu]",
1009 			   generation,
1010 			   btrfs_super_generation(fs_info->super_copy) + 1);
1011 		return -EUCLEAN;
1012 	}
1013 	if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA |
1014 				    BTRFS_EXTENT_FLAG_TREE_BLOCK))) {
1015 		extent_err(leaf, slot,
1016 		"invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx",
1017 			flags, BTRFS_EXTENT_FLAG_DATA |
1018 			BTRFS_EXTENT_FLAG_TREE_BLOCK);
1019 		return -EUCLEAN;
1020 	}
1021 	is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK);
1022 	if (is_tree_block) {
1023 		if (key->type == BTRFS_EXTENT_ITEM_KEY &&
1024 		    key->offset != fs_info->nodesize) {
1025 			extent_err(leaf, slot,
1026 				   "invalid extent length, have %llu expect %u",
1027 				   key->offset, fs_info->nodesize);
1028 			return -EUCLEAN;
1029 		}
1030 	} else {
1031 		if (key->type != BTRFS_EXTENT_ITEM_KEY) {
1032 			extent_err(leaf, slot,
1033 			"invalid key type, have %u expect %u for data backref",
1034 				   key->type, BTRFS_EXTENT_ITEM_KEY);
1035 			return -EUCLEAN;
1036 		}
1037 		if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) {
1038 			extent_err(leaf, slot,
1039 			"invalid extent length, have %llu expect aligned to %u",
1040 				   key->offset, fs_info->sectorsize);
1041 			return -EUCLEAN;
1042 		}
1043 	}
1044 	ptr = (unsigned long)(struct btrfs_extent_item *)(ei + 1);
1045 
1046 	/* Check the special case of btrfs_tree_block_info */
1047 	if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) {
1048 		struct btrfs_tree_block_info *info;
1049 
1050 		info = (struct btrfs_tree_block_info *)ptr;
1051 		if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) {
1052 			extent_err(leaf, slot,
1053 			"invalid tree block info level, have %u expect [0, %u]",
1054 				   btrfs_tree_block_level(leaf, info),
1055 				   BTRFS_MAX_LEVEL - 1);
1056 			return -EUCLEAN;
1057 		}
1058 		ptr = (unsigned long)(struct btrfs_tree_block_info *)(info + 1);
1059 	}
1060 
1061 	/* Check inline refs */
1062 	while (ptr < end) {
1063 		struct btrfs_extent_inline_ref *iref;
1064 		struct btrfs_extent_data_ref *dref;
1065 		struct btrfs_shared_data_ref *sref;
1066 		u64 dref_offset;
1067 		u64 inline_offset;
1068 		u8 inline_type;
1069 
1070 		if (ptr + sizeof(*iref) > end) {
1071 			extent_err(leaf, slot,
1072 "inline ref item overflows extent item, ptr %lu iref size %zu end %lu",
1073 				   ptr, sizeof(*iref), end);
1074 			return -EUCLEAN;
1075 		}
1076 		iref = (struct btrfs_extent_inline_ref *)ptr;
1077 		inline_type = btrfs_extent_inline_ref_type(leaf, iref);
1078 		inline_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1079 		if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) {
1080 			extent_err(leaf, slot,
1081 "inline ref item overflows extent item, ptr %lu iref size %u end %lu",
1082 				   ptr, inline_type, end);
1083 			return -EUCLEAN;
1084 		}
1085 
1086 		switch (inline_type) {
1087 		/* inline_offset is subvolid of the owner, no need to check */
1088 		case BTRFS_TREE_BLOCK_REF_KEY:
1089 			inline_refs++;
1090 			break;
1091 		/* Contains parent bytenr */
1092 		case BTRFS_SHARED_BLOCK_REF_KEY:
1093 			if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
1094 				extent_err(leaf, slot,
1095 		"invalid tree parent bytenr, have %llu expect aligned to %u",
1096 					   inline_offset, fs_info->sectorsize);
1097 				return -EUCLEAN;
1098 			}
1099 			inline_refs++;
1100 			break;
1101 		/*
1102 		 * Contains owner subvolid, owner key objectid, adjusted offset.
1103 		 * The only obvious corruption can happen in that offset.
1104 		 */
1105 		case BTRFS_EXTENT_DATA_REF_KEY:
1106 			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1107 			dref_offset = btrfs_extent_data_ref_offset(leaf, dref);
1108 			if (!IS_ALIGNED(dref_offset, fs_info->sectorsize)) {
1109 				extent_err(leaf, slot,
1110 		"invalid data ref offset, have %llu expect aligned to %u",
1111 					   dref_offset, fs_info->sectorsize);
1112 				return -EUCLEAN;
1113 			}
1114 			inline_refs += btrfs_extent_data_ref_count(leaf, dref);
1115 			break;
1116 		/* Contains parent bytenr and ref count */
1117 		case BTRFS_SHARED_DATA_REF_KEY:
1118 			sref = (struct btrfs_shared_data_ref *)(iref + 1);
1119 			if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
1120 				extent_err(leaf, slot,
1121 		"invalid data parent bytenr, have %llu expect aligned to %u",
1122 					   inline_offset, fs_info->sectorsize);
1123 				return -EUCLEAN;
1124 			}
1125 			inline_refs += btrfs_shared_data_ref_count(leaf, sref);
1126 			break;
1127 		default:
1128 			extent_err(leaf, slot, "unknown inline ref type: %u",
1129 				   inline_type);
1130 			return -EUCLEAN;
1131 		}
1132 		ptr += btrfs_extent_inline_ref_size(inline_type);
1133 	}
1134 	/* No padding is allowed */
1135 	if (ptr != end) {
1136 		extent_err(leaf, slot,
1137 			   "invalid extent item size, padding bytes found");
1138 		return -EUCLEAN;
1139 	}
1140 
1141 	/* Finally, check the inline refs against total refs */
1142 	if (inline_refs > total_refs) {
1143 		extent_err(leaf, slot,
1144 			"invalid extent refs, have %llu expect >= inline %llu",
1145 			   total_refs, inline_refs);
1146 		return -EUCLEAN;
1147 	}
1148 	return 0;
1149 }
1150 
1151 static int check_simple_keyed_refs(struct extent_buffer *leaf,
1152 				   struct btrfs_key *key, int slot)
1153 {
1154 	u32 expect_item_size = 0;
1155 
1156 	if (key->type == BTRFS_SHARED_DATA_REF_KEY)
1157 		expect_item_size = sizeof(struct btrfs_shared_data_ref);
1158 
1159 	if (btrfs_item_size_nr(leaf, slot) != expect_item_size) {
1160 		generic_err(leaf, slot,
1161 		"invalid item size, have %u expect %u for key type %u",
1162 			    btrfs_item_size_nr(leaf, slot),
1163 			    expect_item_size, key->type);
1164 		return -EUCLEAN;
1165 	}
1166 	if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) {
1167 		generic_err(leaf, slot,
1168 "invalid key objectid for shared block ref, have %llu expect aligned to %u",
1169 			    key->objectid, leaf->fs_info->sectorsize);
1170 		return -EUCLEAN;
1171 	}
1172 	if (key->type != BTRFS_TREE_BLOCK_REF_KEY &&
1173 	    !IS_ALIGNED(key->offset, leaf->fs_info->sectorsize)) {
1174 		extent_err(leaf, slot,
1175 		"invalid tree parent bytenr, have %llu expect aligned to %u",
1176 			   key->offset, leaf->fs_info->sectorsize);
1177 		return -EUCLEAN;
1178 	}
1179 	return 0;
1180 }
1181 
1182 static int check_extent_data_ref(struct extent_buffer *leaf,
1183 				 struct btrfs_key *key, int slot)
1184 {
1185 	struct btrfs_extent_data_ref *dref;
1186 	unsigned long ptr = btrfs_item_ptr_offset(leaf, slot);
1187 	const unsigned long end = ptr + btrfs_item_size_nr(leaf, slot);
1188 
1189 	if (btrfs_item_size_nr(leaf, slot) % sizeof(*dref) != 0) {
1190 		generic_err(leaf, slot,
1191 	"invalid item size, have %u expect aligned to %zu for key type %u",
1192 			    btrfs_item_size_nr(leaf, slot),
1193 			    sizeof(*dref), key->type);
1194 	}
1195 	if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) {
1196 		generic_err(leaf, slot,
1197 "invalid key objectid for shared block ref, have %llu expect aligned to %u",
1198 			    key->objectid, leaf->fs_info->sectorsize);
1199 		return -EUCLEAN;
1200 	}
1201 	for (; ptr < end; ptr += sizeof(*dref)) {
1202 		u64 root_objectid;
1203 		u64 owner;
1204 		u64 offset;
1205 		u64 hash;
1206 
1207 		dref = (struct btrfs_extent_data_ref *)ptr;
1208 		root_objectid = btrfs_extent_data_ref_root(leaf, dref);
1209 		owner = btrfs_extent_data_ref_objectid(leaf, dref);
1210 		offset = btrfs_extent_data_ref_offset(leaf, dref);
1211 		hash = hash_extent_data_ref(root_objectid, owner, offset);
1212 		if (hash != key->offset) {
1213 			extent_err(leaf, slot,
1214 	"invalid extent data ref hash, item has 0x%016llx key has 0x%016llx",
1215 				   hash, key->offset);
1216 			return -EUCLEAN;
1217 		}
1218 		if (!IS_ALIGNED(offset, leaf->fs_info->sectorsize)) {
1219 			extent_err(leaf, slot,
1220 	"invalid extent data backref offset, have %llu expect aligned to %u",
1221 				   offset, leaf->fs_info->sectorsize);
1222 		}
1223 	}
1224 	return 0;
1225 }
1226 
1227 /*
1228  * Common point to switch the item-specific validation.
1229  */
1230 static int check_leaf_item(struct extent_buffer *leaf,
1231 			   struct btrfs_key *key, int slot,
1232 			   struct btrfs_key *prev_key)
1233 {
1234 	int ret = 0;
1235 	struct btrfs_chunk *chunk;
1236 
1237 	switch (key->type) {
1238 	case BTRFS_EXTENT_DATA_KEY:
1239 		ret = check_extent_data_item(leaf, key, slot, prev_key);
1240 		break;
1241 	case BTRFS_EXTENT_CSUM_KEY:
1242 		ret = check_csum_item(leaf, key, slot);
1243 		break;
1244 	case BTRFS_DIR_ITEM_KEY:
1245 	case BTRFS_DIR_INDEX_KEY:
1246 	case BTRFS_XATTR_ITEM_KEY:
1247 		ret = check_dir_item(leaf, key, slot);
1248 		break;
1249 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
1250 		ret = check_block_group_item(leaf, key, slot);
1251 		break;
1252 	case BTRFS_CHUNK_ITEM_KEY:
1253 		chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
1254 		ret = btrfs_check_chunk_valid(leaf, chunk, key->offset);
1255 		break;
1256 	case BTRFS_DEV_ITEM_KEY:
1257 		ret = check_dev_item(leaf, key, slot);
1258 		break;
1259 	case BTRFS_INODE_ITEM_KEY:
1260 		ret = check_inode_item(leaf, key, slot);
1261 		break;
1262 	case BTRFS_ROOT_ITEM_KEY:
1263 		ret = check_root_item(leaf, key, slot);
1264 		break;
1265 	case BTRFS_EXTENT_ITEM_KEY:
1266 	case BTRFS_METADATA_ITEM_KEY:
1267 		ret = check_extent_item(leaf, key, slot);
1268 		break;
1269 	case BTRFS_TREE_BLOCK_REF_KEY:
1270 	case BTRFS_SHARED_DATA_REF_KEY:
1271 	case BTRFS_SHARED_BLOCK_REF_KEY:
1272 		ret = check_simple_keyed_refs(leaf, key, slot);
1273 		break;
1274 	case BTRFS_EXTENT_DATA_REF_KEY:
1275 		ret = check_extent_data_ref(leaf, key, slot);
1276 		break;
1277 	}
1278 	return ret;
1279 }
1280 
1281 static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
1282 {
1283 	struct btrfs_fs_info *fs_info = leaf->fs_info;
1284 	/* No valid key type is 0, so all key should be larger than this key */
1285 	struct btrfs_key prev_key = {0, 0, 0};
1286 	struct btrfs_key key;
1287 	u32 nritems = btrfs_header_nritems(leaf);
1288 	int slot;
1289 
1290 	if (btrfs_header_level(leaf) != 0) {
1291 		generic_err(leaf, 0,
1292 			"invalid level for leaf, have %d expect 0",
1293 			btrfs_header_level(leaf));
1294 		return -EUCLEAN;
1295 	}
1296 
1297 	/*
1298 	 * Extent buffers from a relocation tree have a owner field that
1299 	 * corresponds to the subvolume tree they are based on. So just from an
1300 	 * extent buffer alone we can not find out what is the id of the
1301 	 * corresponding subvolume tree, so we can not figure out if the extent
1302 	 * buffer corresponds to the root of the relocation tree or not. So
1303 	 * skip this check for relocation trees.
1304 	 */
1305 	if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
1306 		u64 owner = btrfs_header_owner(leaf);
1307 
1308 		/* These trees must never be empty */
1309 		if (owner == BTRFS_ROOT_TREE_OBJECTID ||
1310 		    owner == BTRFS_CHUNK_TREE_OBJECTID ||
1311 		    owner == BTRFS_EXTENT_TREE_OBJECTID ||
1312 		    owner == BTRFS_DEV_TREE_OBJECTID ||
1313 		    owner == BTRFS_FS_TREE_OBJECTID ||
1314 		    owner == BTRFS_DATA_RELOC_TREE_OBJECTID) {
1315 			generic_err(leaf, 0,
1316 			"invalid root, root %llu must never be empty",
1317 				    owner);
1318 			return -EUCLEAN;
1319 		}
1320 		/* Unknown tree */
1321 		if (owner == 0) {
1322 			generic_err(leaf, 0,
1323 				"invalid owner, root 0 is not defined");
1324 			return -EUCLEAN;
1325 		}
1326 		return 0;
1327 	}
1328 
1329 	if (nritems == 0)
1330 		return 0;
1331 
1332 	/*
1333 	 * Check the following things to make sure this is a good leaf, and
1334 	 * leaf users won't need to bother with similar sanity checks:
1335 	 *
1336 	 * 1) key ordering
1337 	 * 2) item offset and size
1338 	 *    No overlap, no hole, all inside the leaf.
1339 	 * 3) item content
1340 	 *    If possible, do comprehensive sanity check.
1341 	 *    NOTE: All checks must only rely on the item data itself.
1342 	 */
1343 	for (slot = 0; slot < nritems; slot++) {
1344 		u32 item_end_expected;
1345 		int ret;
1346 
1347 		btrfs_item_key_to_cpu(leaf, &key, slot);
1348 
1349 		/* Make sure the keys are in the right order */
1350 		if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
1351 			generic_err(leaf, slot,
1352 	"bad key order, prev (%llu %u %llu) current (%llu %u %llu)",
1353 				prev_key.objectid, prev_key.type,
1354 				prev_key.offset, key.objectid, key.type,
1355 				key.offset);
1356 			return -EUCLEAN;
1357 		}
1358 
1359 		/*
1360 		 * Make sure the offset and ends are right, remember that the
1361 		 * item data starts at the end of the leaf and grows towards the
1362 		 * front.
1363 		 */
1364 		if (slot == 0)
1365 			item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
1366 		else
1367 			item_end_expected = btrfs_item_offset_nr(leaf,
1368 								 slot - 1);
1369 		if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
1370 			generic_err(leaf, slot,
1371 				"unexpected item end, have %u expect %u",
1372 				btrfs_item_end_nr(leaf, slot),
1373 				item_end_expected);
1374 			return -EUCLEAN;
1375 		}
1376 
1377 		/*
1378 		 * Check to make sure that we don't point outside of the leaf,
1379 		 * just in case all the items are consistent to each other, but
1380 		 * all point outside of the leaf.
1381 		 */
1382 		if (btrfs_item_end_nr(leaf, slot) >
1383 		    BTRFS_LEAF_DATA_SIZE(fs_info)) {
1384 			generic_err(leaf, slot,
1385 			"slot end outside of leaf, have %u expect range [0, %u]",
1386 				btrfs_item_end_nr(leaf, slot),
1387 				BTRFS_LEAF_DATA_SIZE(fs_info));
1388 			return -EUCLEAN;
1389 		}
1390 
1391 		/* Also check if the item pointer overlaps with btrfs item. */
1392 		if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
1393 		    btrfs_item_ptr_offset(leaf, slot)) {
1394 			generic_err(leaf, slot,
1395 		"slot overlaps with its data, item end %lu data start %lu",
1396 				btrfs_item_nr_offset(slot) +
1397 				sizeof(struct btrfs_item),
1398 				btrfs_item_ptr_offset(leaf, slot));
1399 			return -EUCLEAN;
1400 		}
1401 
1402 		if (check_item_data) {
1403 			/*
1404 			 * Check if the item size and content meet other
1405 			 * criteria
1406 			 */
1407 			ret = check_leaf_item(leaf, &key, slot, &prev_key);
1408 			if (ret < 0)
1409 				return ret;
1410 		}
1411 
1412 		prev_key.objectid = key.objectid;
1413 		prev_key.type = key.type;
1414 		prev_key.offset = key.offset;
1415 	}
1416 
1417 	return 0;
1418 }
1419 
1420 int btrfs_check_leaf_full(struct extent_buffer *leaf)
1421 {
1422 	return check_leaf(leaf, true);
1423 }
1424 ALLOW_ERROR_INJECTION(btrfs_check_leaf_full, ERRNO);
1425 
1426 int btrfs_check_leaf_relaxed(struct extent_buffer *leaf)
1427 {
1428 	return check_leaf(leaf, false);
1429 }
1430 
1431 int btrfs_check_node(struct extent_buffer *node)
1432 {
1433 	struct btrfs_fs_info *fs_info = node->fs_info;
1434 	unsigned long nr = btrfs_header_nritems(node);
1435 	struct btrfs_key key, next_key;
1436 	int slot;
1437 	int level = btrfs_header_level(node);
1438 	u64 bytenr;
1439 	int ret = 0;
1440 
1441 	if (level <= 0 || level >= BTRFS_MAX_LEVEL) {
1442 		generic_err(node, 0,
1443 			"invalid level for node, have %d expect [1, %d]",
1444 			level, BTRFS_MAX_LEVEL - 1);
1445 		return -EUCLEAN;
1446 	}
1447 	if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(fs_info)) {
1448 		btrfs_crit(fs_info,
1449 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]",
1450 			   btrfs_header_owner(node), node->start,
1451 			   nr == 0 ? "small" : "large", nr,
1452 			   BTRFS_NODEPTRS_PER_BLOCK(fs_info));
1453 		return -EUCLEAN;
1454 	}
1455 
1456 	for (slot = 0; slot < nr - 1; slot++) {
1457 		bytenr = btrfs_node_blockptr(node, slot);
1458 		btrfs_node_key_to_cpu(node, &key, slot);
1459 		btrfs_node_key_to_cpu(node, &next_key, slot + 1);
1460 
1461 		if (!bytenr) {
1462 			generic_err(node, slot,
1463 				"invalid NULL node pointer");
1464 			ret = -EUCLEAN;
1465 			goto out;
1466 		}
1467 		if (!IS_ALIGNED(bytenr, fs_info->sectorsize)) {
1468 			generic_err(node, slot,
1469 			"unaligned pointer, have %llu should be aligned to %u",
1470 				bytenr, fs_info->sectorsize);
1471 			ret = -EUCLEAN;
1472 			goto out;
1473 		}
1474 
1475 		if (btrfs_comp_cpu_keys(&key, &next_key) >= 0) {
1476 			generic_err(node, slot,
1477 	"bad key order, current (%llu %u %llu) next (%llu %u %llu)",
1478 				key.objectid, key.type, key.offset,
1479 				next_key.objectid, next_key.type,
1480 				next_key.offset);
1481 			ret = -EUCLEAN;
1482 			goto out;
1483 		}
1484 	}
1485 out:
1486 	return ret;
1487 }
1488 ALLOW_ERROR_INJECTION(btrfs_check_node, ERRNO);
1489