xref: /linux/fs/btrfs/tree-checker.c (revision 42b16d3ac371a2fac9b6f08fd75f23f34ba3955a)
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 "messages.h"
22 #include "ctree.h"
23 #include "tree-checker.h"
24 #include "compression.h"
25 #include "volumes.h"
26 #include "misc.h"
27 #include "fs.h"
28 #include "accessors.h"
29 #include "file-item.h"
30 #include "inode-item.h"
31 #include "dir-item.h"
32 #include "extent-tree.h"
33 
34 /*
35  * Error message should follow the following format:
36  * corrupt <type>: <identifier>, <reason>[, <bad_value>]
37  *
38  * @type:	leaf or node
39  * @identifier:	the necessary info to locate the leaf/node.
40  * 		It's recommended to decode key.objecitd/offset if it's
41  * 		meaningful.
42  * @reason:	describe the error
43  * @bad_value:	optional, it's recommended to output bad value and its
44  *		expected value (range).
45  *
46  * Since comma is used to separate the components, only space is allowed
47  * inside each component.
48  */
49 
50 /*
51  * Append generic "corrupt leaf/node root=%llu block=%llu slot=%d: " to @fmt.
52  * Allows callers to customize the output.
53  */
54 __printf(3, 4)
55 __cold
generic_err(const struct extent_buffer * eb,int slot,const char * fmt,...)56 static void generic_err(const struct extent_buffer *eb, int slot,
57 			const char *fmt, ...)
58 {
59 	const struct btrfs_fs_info *fs_info = eb->fs_info;
60 	struct va_format vaf;
61 	va_list args;
62 
63 	va_start(args, fmt);
64 
65 	vaf.fmt = fmt;
66 	vaf.va = &args;
67 
68 	dump_page(folio_page(eb->folios[0], 0), "eb page dump");
69 	btrfs_crit(fs_info,
70 		"corrupt %s: root=%llu block=%llu slot=%d, %pV",
71 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
72 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot, &vaf);
73 	va_end(args);
74 }
75 
76 /*
77  * Customized reporter for extent data item, since its key objectid and
78  * offset has its own meaning.
79  */
80 __printf(3, 4)
81 __cold
file_extent_err(const struct extent_buffer * eb,int slot,const char * fmt,...)82 static void file_extent_err(const struct extent_buffer *eb, int slot,
83 			    const char *fmt, ...)
84 {
85 	const struct btrfs_fs_info *fs_info = eb->fs_info;
86 	struct btrfs_key key;
87 	struct va_format vaf;
88 	va_list args;
89 
90 	btrfs_item_key_to_cpu(eb, &key, slot);
91 	va_start(args, fmt);
92 
93 	vaf.fmt = fmt;
94 	vaf.va = &args;
95 
96 	dump_page(folio_page(eb->folios[0], 0), "eb page dump");
97 	btrfs_crit(fs_info,
98 	"corrupt %s: root=%llu block=%llu slot=%d ino=%llu file_offset=%llu, %pV",
99 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
100 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
101 		key.objectid, key.offset, &vaf);
102 	va_end(args);
103 }
104 
105 /*
106  * Return 0 if the btrfs_file_extent_##name is aligned to @alignment
107  * Else return 1
108  */
109 #define CHECK_FE_ALIGNED(leaf, slot, fi, name, alignment)		      \
110 ({									      \
111 	if (unlikely(!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)),      \
112 				 (alignment))))				      \
113 		file_extent_err((leaf), (slot),				      \
114 	"invalid %s for file extent, have %llu, should be aligned to %u",     \
115 			(#name), btrfs_file_extent_##name((leaf), (fi)),      \
116 			(alignment));					      \
117 	(!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment)));   \
118 })
119 
file_extent_end(struct extent_buffer * leaf,struct btrfs_key * key,struct btrfs_file_extent_item * extent)120 static u64 file_extent_end(struct extent_buffer *leaf,
121 			   struct btrfs_key *key,
122 			   struct btrfs_file_extent_item *extent)
123 {
124 	u64 end;
125 	u64 len;
126 
127 	if (btrfs_file_extent_type(leaf, extent) == BTRFS_FILE_EXTENT_INLINE) {
128 		len = btrfs_file_extent_ram_bytes(leaf, extent);
129 		end = ALIGN(key->offset + len, leaf->fs_info->sectorsize);
130 	} else {
131 		len = btrfs_file_extent_num_bytes(leaf, extent);
132 		end = key->offset + len;
133 	}
134 	return end;
135 }
136 
137 /*
138  * Customized report for dir_item, the only new important information is
139  * key->objectid, which represents inode number
140  */
141 __printf(3, 4)
142 __cold
dir_item_err(const struct extent_buffer * eb,int slot,const char * fmt,...)143 static void dir_item_err(const struct extent_buffer *eb, int slot,
144 			 const char *fmt, ...)
145 {
146 	const struct btrfs_fs_info *fs_info = eb->fs_info;
147 	struct btrfs_key key;
148 	struct va_format vaf;
149 	va_list args;
150 
151 	btrfs_item_key_to_cpu(eb, &key, slot);
152 	va_start(args, fmt);
153 
154 	vaf.fmt = fmt;
155 	vaf.va = &args;
156 
157 	dump_page(folio_page(eb->folios[0], 0), "eb page dump");
158 	btrfs_crit(fs_info,
159 		"corrupt %s: root=%llu block=%llu slot=%d ino=%llu, %pV",
160 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
161 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
162 		key.objectid, &vaf);
163 	va_end(args);
164 }
165 
166 /*
167  * This functions checks prev_key->objectid, to ensure current key and prev_key
168  * share the same objectid as inode number.
169  *
170  * This is to detect missing INODE_ITEM in subvolume trees.
171  *
172  * Return true if everything is OK or we don't need to check.
173  * Return false if anything is wrong.
174  */
check_prev_ino(struct extent_buffer * leaf,struct btrfs_key * key,int slot,struct btrfs_key * prev_key)175 static bool check_prev_ino(struct extent_buffer *leaf,
176 			   struct btrfs_key *key, int slot,
177 			   struct btrfs_key *prev_key)
178 {
179 	/* No prev key, skip check */
180 	if (slot == 0)
181 		return true;
182 
183 	/* Only these key->types needs to be checked */
184 	ASSERT(key->type == BTRFS_XATTR_ITEM_KEY ||
185 	       key->type == BTRFS_INODE_REF_KEY ||
186 	       key->type == BTRFS_DIR_INDEX_KEY ||
187 	       key->type == BTRFS_DIR_ITEM_KEY ||
188 	       key->type == BTRFS_EXTENT_DATA_KEY);
189 
190 	/*
191 	 * Only subvolume trees along with their reloc trees need this check.
192 	 * Things like log tree doesn't follow this ino requirement.
193 	 */
194 	if (!is_fstree(btrfs_header_owner(leaf)))
195 		return true;
196 
197 	if (key->objectid == prev_key->objectid)
198 		return true;
199 
200 	/* Error found */
201 	dir_item_err(leaf, slot,
202 		"invalid previous key objectid, have %llu expect %llu",
203 		prev_key->objectid, key->objectid);
204 	return false;
205 }
check_extent_data_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot,struct btrfs_key * prev_key)206 static int check_extent_data_item(struct extent_buffer *leaf,
207 				  struct btrfs_key *key, int slot,
208 				  struct btrfs_key *prev_key)
209 {
210 	struct btrfs_fs_info *fs_info = leaf->fs_info;
211 	struct btrfs_file_extent_item *fi;
212 	u32 sectorsize = fs_info->sectorsize;
213 	u32 item_size = btrfs_item_size(leaf, slot);
214 	u64 extent_end;
215 
216 	if (unlikely(!IS_ALIGNED(key->offset, sectorsize))) {
217 		file_extent_err(leaf, slot,
218 "unaligned file_offset for file extent, have %llu should be aligned to %u",
219 			key->offset, sectorsize);
220 		return -EUCLEAN;
221 	}
222 
223 	/*
224 	 * Previous key must have the same key->objectid (ino).
225 	 * It can be XATTR_ITEM, INODE_ITEM or just another EXTENT_DATA.
226 	 * But if objectids mismatch, it means we have a missing
227 	 * INODE_ITEM.
228 	 */
229 	if (unlikely(!check_prev_ino(leaf, key, slot, prev_key)))
230 		return -EUCLEAN;
231 
232 	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
233 
234 	/*
235 	 * Make sure the item contains at least inline header, so the file
236 	 * extent type is not some garbage.
237 	 */
238 	if (unlikely(item_size < BTRFS_FILE_EXTENT_INLINE_DATA_START)) {
239 		file_extent_err(leaf, slot,
240 				"invalid item size, have %u expect [%zu, %u)",
241 				item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START,
242 				SZ_4K);
243 		return -EUCLEAN;
244 	}
245 	if (unlikely(btrfs_file_extent_type(leaf, fi) >=
246 		     BTRFS_NR_FILE_EXTENT_TYPES)) {
247 		file_extent_err(leaf, slot,
248 		"invalid type for file extent, have %u expect range [0, %u]",
249 			btrfs_file_extent_type(leaf, fi),
250 			BTRFS_NR_FILE_EXTENT_TYPES - 1);
251 		return -EUCLEAN;
252 	}
253 
254 	/*
255 	 * Support for new compression/encryption must introduce incompat flag,
256 	 * and must be caught in open_ctree().
257 	 */
258 	if (unlikely(btrfs_file_extent_compression(leaf, fi) >=
259 		     BTRFS_NR_COMPRESS_TYPES)) {
260 		file_extent_err(leaf, slot,
261 	"invalid compression for file extent, have %u expect range [0, %u]",
262 			btrfs_file_extent_compression(leaf, fi),
263 			BTRFS_NR_COMPRESS_TYPES - 1);
264 		return -EUCLEAN;
265 	}
266 	if (unlikely(btrfs_file_extent_encryption(leaf, fi))) {
267 		file_extent_err(leaf, slot,
268 			"invalid encryption for file extent, have %u expect 0",
269 			btrfs_file_extent_encryption(leaf, fi));
270 		return -EUCLEAN;
271 	}
272 	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
273 		/* Inline extent must have 0 as key offset */
274 		if (unlikely(key->offset)) {
275 			file_extent_err(leaf, slot,
276 		"invalid file_offset for inline file extent, have %llu expect 0",
277 				key->offset);
278 			return -EUCLEAN;
279 		}
280 
281 		/* Compressed inline extent has no on-disk size, skip it */
282 		if (btrfs_file_extent_compression(leaf, fi) !=
283 		    BTRFS_COMPRESS_NONE)
284 			return 0;
285 
286 		/* Uncompressed inline extent size must match item size */
287 		if (unlikely(item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
288 					  btrfs_file_extent_ram_bytes(leaf, fi))) {
289 			file_extent_err(leaf, slot,
290 	"invalid ram_bytes for uncompressed inline extent, have %u expect %llu",
291 				item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START +
292 				btrfs_file_extent_ram_bytes(leaf, fi));
293 			return -EUCLEAN;
294 		}
295 		return 0;
296 	}
297 
298 	/* Regular or preallocated extent has fixed item size */
299 	if (unlikely(item_size != sizeof(*fi))) {
300 		file_extent_err(leaf, slot,
301 	"invalid item size for reg/prealloc file extent, have %u expect %zu",
302 			item_size, sizeof(*fi));
303 		return -EUCLEAN;
304 	}
305 	if (unlikely(CHECK_FE_ALIGNED(leaf, slot, fi, ram_bytes, sectorsize) ||
306 		     CHECK_FE_ALIGNED(leaf, slot, fi, disk_bytenr, sectorsize) ||
307 		     CHECK_FE_ALIGNED(leaf, slot, fi, disk_num_bytes, sectorsize) ||
308 		     CHECK_FE_ALIGNED(leaf, slot, fi, offset, sectorsize) ||
309 		     CHECK_FE_ALIGNED(leaf, slot, fi, num_bytes, sectorsize)))
310 		return -EUCLEAN;
311 
312 	/* Catch extent end overflow */
313 	if (unlikely(check_add_overflow(btrfs_file_extent_num_bytes(leaf, fi),
314 					key->offset, &extent_end))) {
315 		file_extent_err(leaf, slot,
316 	"extent end overflow, have file offset %llu extent num bytes %llu",
317 				key->offset,
318 				btrfs_file_extent_num_bytes(leaf, fi));
319 		return -EUCLEAN;
320 	}
321 
322 	/*
323 	 * Check that no two consecutive file extent items, in the same leaf,
324 	 * present ranges that overlap each other.
325 	 */
326 	if (slot > 0 &&
327 	    prev_key->objectid == key->objectid &&
328 	    prev_key->type == BTRFS_EXTENT_DATA_KEY) {
329 		struct btrfs_file_extent_item *prev_fi;
330 		u64 prev_end;
331 
332 		prev_fi = btrfs_item_ptr(leaf, slot - 1,
333 					 struct btrfs_file_extent_item);
334 		prev_end = file_extent_end(leaf, prev_key, prev_fi);
335 		if (unlikely(prev_end > key->offset)) {
336 			file_extent_err(leaf, slot - 1,
337 "file extent end range (%llu) goes beyond start offset (%llu) of the next file extent",
338 					prev_end, key->offset);
339 			return -EUCLEAN;
340 		}
341 	}
342 
343 	/*
344 	 * For non-compressed data extents, ram_bytes should match its
345 	 * disk_num_bytes.
346 	 * However we do not really utilize ram_bytes in this case, so this check
347 	 * is only optional for DEBUG builds for developers to catch the
348 	 * unexpected behaviors.
349 	 */
350 	if (IS_ENABLED(CONFIG_BTRFS_DEBUG) &&
351 	    btrfs_file_extent_compression(leaf, fi) == BTRFS_COMPRESS_NONE &&
352 	    btrfs_file_extent_disk_bytenr(leaf, fi)) {
353 		if (WARN_ON(btrfs_file_extent_ram_bytes(leaf, fi) !=
354 			    btrfs_file_extent_disk_num_bytes(leaf, fi)))
355 			file_extent_err(leaf, slot,
356 "mismatch ram_bytes (%llu) and disk_num_bytes (%llu) for non-compressed extent",
357 					btrfs_file_extent_ram_bytes(leaf, fi),
358 					btrfs_file_extent_disk_num_bytes(leaf, fi));
359 	}
360 
361 	return 0;
362 }
363 
check_csum_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot,struct btrfs_key * prev_key)364 static int check_csum_item(struct extent_buffer *leaf, struct btrfs_key *key,
365 			   int slot, struct btrfs_key *prev_key)
366 {
367 	struct btrfs_fs_info *fs_info = leaf->fs_info;
368 	u32 sectorsize = fs_info->sectorsize;
369 	const u32 csumsize = fs_info->csum_size;
370 
371 	if (unlikely(key->objectid != BTRFS_EXTENT_CSUM_OBJECTID)) {
372 		generic_err(leaf, slot,
373 		"invalid key objectid for csum item, have %llu expect %llu",
374 			key->objectid, BTRFS_EXTENT_CSUM_OBJECTID);
375 		return -EUCLEAN;
376 	}
377 	if (unlikely(!IS_ALIGNED(key->offset, sectorsize))) {
378 		generic_err(leaf, slot,
379 	"unaligned key offset for csum item, have %llu should be aligned to %u",
380 			key->offset, sectorsize);
381 		return -EUCLEAN;
382 	}
383 	if (unlikely(!IS_ALIGNED(btrfs_item_size(leaf, slot), csumsize))) {
384 		generic_err(leaf, slot,
385 	"unaligned item size for csum item, have %u should be aligned to %u",
386 			btrfs_item_size(leaf, slot), csumsize);
387 		return -EUCLEAN;
388 	}
389 	if (slot > 0 && prev_key->type == BTRFS_EXTENT_CSUM_KEY) {
390 		u64 prev_csum_end;
391 		u32 prev_item_size;
392 
393 		prev_item_size = btrfs_item_size(leaf, slot - 1);
394 		prev_csum_end = (prev_item_size / csumsize) * sectorsize;
395 		prev_csum_end += prev_key->offset;
396 		if (unlikely(prev_csum_end > key->offset)) {
397 			generic_err(leaf, slot - 1,
398 "csum end range (%llu) goes beyond the start range (%llu) of the next csum item",
399 				    prev_csum_end, key->offset);
400 			return -EUCLEAN;
401 		}
402 	}
403 	return 0;
404 }
405 
406 /* Inode item error output has the same format as dir_item_err() */
407 #define inode_item_err(eb, slot, fmt, ...)			\
408 	dir_item_err(eb, slot, fmt, __VA_ARGS__)
409 
check_inode_key(struct extent_buffer * leaf,struct btrfs_key * key,int slot)410 static int check_inode_key(struct extent_buffer *leaf, struct btrfs_key *key,
411 			   int slot)
412 {
413 	struct btrfs_key item_key;
414 	bool is_inode_item;
415 
416 	btrfs_item_key_to_cpu(leaf, &item_key, slot);
417 	is_inode_item = (item_key.type == BTRFS_INODE_ITEM_KEY);
418 
419 	/* For XATTR_ITEM, location key should be all 0 */
420 	if (item_key.type == BTRFS_XATTR_ITEM_KEY) {
421 		if (unlikely(key->objectid != 0 || key->type != 0 ||
422 			     key->offset != 0))
423 			return -EUCLEAN;
424 		return 0;
425 	}
426 
427 	if (unlikely((key->objectid < BTRFS_FIRST_FREE_OBJECTID ||
428 		      key->objectid > BTRFS_LAST_FREE_OBJECTID) &&
429 		     key->objectid != BTRFS_ROOT_TREE_DIR_OBJECTID &&
430 		     key->objectid != BTRFS_FREE_INO_OBJECTID)) {
431 		if (is_inode_item) {
432 			generic_err(leaf, slot,
433 	"invalid key objectid: has %llu expect %llu or [%llu, %llu] or %llu",
434 				key->objectid, BTRFS_ROOT_TREE_DIR_OBJECTID,
435 				BTRFS_FIRST_FREE_OBJECTID,
436 				BTRFS_LAST_FREE_OBJECTID,
437 				BTRFS_FREE_INO_OBJECTID);
438 		} else {
439 			dir_item_err(leaf, slot,
440 "invalid location key objectid: has %llu expect %llu or [%llu, %llu] or %llu",
441 				key->objectid, BTRFS_ROOT_TREE_DIR_OBJECTID,
442 				BTRFS_FIRST_FREE_OBJECTID,
443 				BTRFS_LAST_FREE_OBJECTID,
444 				BTRFS_FREE_INO_OBJECTID);
445 		}
446 		return -EUCLEAN;
447 	}
448 	if (unlikely(key->offset != 0)) {
449 		if (is_inode_item)
450 			inode_item_err(leaf, slot,
451 				       "invalid key offset: has %llu expect 0",
452 				       key->offset);
453 		else
454 			dir_item_err(leaf, slot,
455 				"invalid location key offset:has %llu expect 0",
456 				key->offset);
457 		return -EUCLEAN;
458 	}
459 	return 0;
460 }
461 
check_root_key(struct extent_buffer * leaf,struct btrfs_key * key,int slot)462 static int check_root_key(struct extent_buffer *leaf, struct btrfs_key *key,
463 			  int slot)
464 {
465 	struct btrfs_key item_key;
466 	bool is_root_item;
467 
468 	btrfs_item_key_to_cpu(leaf, &item_key, slot);
469 	is_root_item = (item_key.type == BTRFS_ROOT_ITEM_KEY);
470 
471 	/*
472 	 * Bad rootid for reloc trees.
473 	 *
474 	 * Reloc trees are only for subvolume trees, other trees only need
475 	 * to be COWed to be relocated.
476 	 */
477 	if (unlikely(is_root_item && key->objectid == BTRFS_TREE_RELOC_OBJECTID &&
478 		     !is_fstree(key->offset))) {
479 		generic_err(leaf, slot,
480 		"invalid reloc tree for root %lld, root id is not a subvolume tree",
481 			    key->offset);
482 		return -EUCLEAN;
483 	}
484 
485 	/* No such tree id */
486 	if (unlikely(key->objectid == 0)) {
487 		if (is_root_item)
488 			generic_err(leaf, slot, "invalid root id 0");
489 		else
490 			dir_item_err(leaf, slot,
491 				     "invalid location key root id 0");
492 		return -EUCLEAN;
493 	}
494 
495 	/* DIR_ITEM/INDEX/INODE_REF is not allowed to point to non-fs trees */
496 	if (unlikely(!is_fstree(key->objectid) && !is_root_item)) {
497 		dir_item_err(leaf, slot,
498 		"invalid location key objectid, have %llu expect [%llu, %llu]",
499 				key->objectid, BTRFS_FIRST_FREE_OBJECTID,
500 				BTRFS_LAST_FREE_OBJECTID);
501 		return -EUCLEAN;
502 	}
503 
504 	/*
505 	 * ROOT_ITEM with non-zero offset means this is a snapshot, created at
506 	 * @offset transid.
507 	 * Furthermore, for location key in DIR_ITEM, its offset is always -1.
508 	 *
509 	 * So here we only check offset for reloc tree whose key->offset must
510 	 * be a valid tree.
511 	 */
512 	if (unlikely(key->objectid == BTRFS_TREE_RELOC_OBJECTID &&
513 		     key->offset == 0)) {
514 		generic_err(leaf, slot, "invalid root id 0 for reloc tree");
515 		return -EUCLEAN;
516 	}
517 	return 0;
518 }
519 
check_dir_item(struct extent_buffer * leaf,struct btrfs_key * key,struct btrfs_key * prev_key,int slot)520 static int check_dir_item(struct extent_buffer *leaf,
521 			  struct btrfs_key *key, struct btrfs_key *prev_key,
522 			  int slot)
523 {
524 	struct btrfs_fs_info *fs_info = leaf->fs_info;
525 	struct btrfs_dir_item *di;
526 	u32 item_size = btrfs_item_size(leaf, slot);
527 	u32 cur = 0;
528 
529 	if (unlikely(!check_prev_ino(leaf, key, slot, prev_key)))
530 		return -EUCLEAN;
531 
532 	di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
533 	while (cur < item_size) {
534 		struct btrfs_key location_key;
535 		u32 name_len;
536 		u32 data_len;
537 		u32 max_name_len;
538 		u32 total_size;
539 		u32 name_hash;
540 		u8 dir_type;
541 		int ret;
542 
543 		/* header itself should not cross item boundary */
544 		if (unlikely(cur + sizeof(*di) > item_size)) {
545 			dir_item_err(leaf, slot,
546 		"dir item header crosses item boundary, have %zu boundary %u",
547 				cur + sizeof(*di), item_size);
548 			return -EUCLEAN;
549 		}
550 
551 		/* Location key check */
552 		btrfs_dir_item_key_to_cpu(leaf, di, &location_key);
553 		if (location_key.type == BTRFS_ROOT_ITEM_KEY) {
554 			ret = check_root_key(leaf, &location_key, slot);
555 			if (unlikely(ret < 0))
556 				return ret;
557 		} else if (location_key.type == BTRFS_INODE_ITEM_KEY ||
558 			   location_key.type == 0) {
559 			ret = check_inode_key(leaf, &location_key, slot);
560 			if (unlikely(ret < 0))
561 				return ret;
562 		} else {
563 			dir_item_err(leaf, slot,
564 			"invalid location key type, have %u, expect %u or %u",
565 				     location_key.type, BTRFS_ROOT_ITEM_KEY,
566 				     BTRFS_INODE_ITEM_KEY);
567 			return -EUCLEAN;
568 		}
569 
570 		/* dir type check */
571 		dir_type = btrfs_dir_ftype(leaf, di);
572 		if (unlikely(dir_type <= BTRFS_FT_UNKNOWN ||
573 			     dir_type >= BTRFS_FT_MAX)) {
574 			dir_item_err(leaf, slot,
575 			"invalid dir item type, have %u expect (0, %u)",
576 				dir_type, BTRFS_FT_MAX);
577 			return -EUCLEAN;
578 		}
579 
580 		if (unlikely(key->type == BTRFS_XATTR_ITEM_KEY &&
581 			     dir_type != BTRFS_FT_XATTR)) {
582 			dir_item_err(leaf, slot,
583 		"invalid dir item type for XATTR key, have %u expect %u",
584 				dir_type, BTRFS_FT_XATTR);
585 			return -EUCLEAN;
586 		}
587 		if (unlikely(dir_type == BTRFS_FT_XATTR &&
588 			     key->type != BTRFS_XATTR_ITEM_KEY)) {
589 			dir_item_err(leaf, slot,
590 			"xattr dir type found for non-XATTR key");
591 			return -EUCLEAN;
592 		}
593 		if (dir_type == BTRFS_FT_XATTR)
594 			max_name_len = XATTR_NAME_MAX;
595 		else
596 			max_name_len = BTRFS_NAME_LEN;
597 
598 		/* Name/data length check */
599 		name_len = btrfs_dir_name_len(leaf, di);
600 		data_len = btrfs_dir_data_len(leaf, di);
601 		if (unlikely(name_len > max_name_len)) {
602 			dir_item_err(leaf, slot,
603 			"dir item name len too long, have %u max %u",
604 				name_len, max_name_len);
605 			return -EUCLEAN;
606 		}
607 		if (unlikely(name_len + data_len > BTRFS_MAX_XATTR_SIZE(fs_info))) {
608 			dir_item_err(leaf, slot,
609 			"dir item name and data len too long, have %u max %u",
610 				name_len + data_len,
611 				BTRFS_MAX_XATTR_SIZE(fs_info));
612 			return -EUCLEAN;
613 		}
614 
615 		if (unlikely(data_len && dir_type != BTRFS_FT_XATTR)) {
616 			dir_item_err(leaf, slot,
617 			"dir item with invalid data len, have %u expect 0",
618 				data_len);
619 			return -EUCLEAN;
620 		}
621 
622 		total_size = sizeof(*di) + name_len + data_len;
623 
624 		/* header and name/data should not cross item boundary */
625 		if (unlikely(cur + total_size > item_size)) {
626 			dir_item_err(leaf, slot,
627 		"dir item data crosses item boundary, have %u boundary %u",
628 				cur + total_size, item_size);
629 			return -EUCLEAN;
630 		}
631 
632 		/*
633 		 * Special check for XATTR/DIR_ITEM, as key->offset is name
634 		 * hash, should match its name
635 		 */
636 		if (key->type == BTRFS_DIR_ITEM_KEY ||
637 		    key->type == BTRFS_XATTR_ITEM_KEY) {
638 			char namebuf[MAX(BTRFS_NAME_LEN, XATTR_NAME_MAX)];
639 
640 			read_extent_buffer(leaf, namebuf,
641 					(unsigned long)(di + 1), name_len);
642 			name_hash = btrfs_name_hash(namebuf, name_len);
643 			if (unlikely(key->offset != name_hash)) {
644 				dir_item_err(leaf, slot,
645 		"name hash mismatch with key, have 0x%016x expect 0x%016llx",
646 					name_hash, key->offset);
647 				return -EUCLEAN;
648 			}
649 		}
650 		cur += total_size;
651 		di = (struct btrfs_dir_item *)((void *)di + total_size);
652 	}
653 	return 0;
654 }
655 
656 __printf(3, 4)
657 __cold
block_group_err(const struct extent_buffer * eb,int slot,const char * fmt,...)658 static void block_group_err(const struct extent_buffer *eb, int slot,
659 			    const char *fmt, ...)
660 {
661 	const struct btrfs_fs_info *fs_info = eb->fs_info;
662 	struct btrfs_key key;
663 	struct va_format vaf;
664 	va_list args;
665 
666 	btrfs_item_key_to_cpu(eb, &key, slot);
667 	va_start(args, fmt);
668 
669 	vaf.fmt = fmt;
670 	vaf.va = &args;
671 
672 	dump_page(folio_page(eb->folios[0], 0), "eb page dump");
673 	btrfs_crit(fs_info,
674 	"corrupt %s: root=%llu block=%llu slot=%d bg_start=%llu bg_len=%llu, %pV",
675 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
676 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
677 		key.objectid, key.offset, &vaf);
678 	va_end(args);
679 }
680 
check_block_group_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot)681 static int check_block_group_item(struct extent_buffer *leaf,
682 				  struct btrfs_key *key, int slot)
683 {
684 	struct btrfs_fs_info *fs_info = leaf->fs_info;
685 	struct btrfs_block_group_item bgi;
686 	u32 item_size = btrfs_item_size(leaf, slot);
687 	u64 chunk_objectid;
688 	u64 flags;
689 	u64 type;
690 
691 	/*
692 	 * Here we don't really care about alignment since extent allocator can
693 	 * handle it.  We care more about the size.
694 	 */
695 	if (unlikely(key->offset == 0)) {
696 		block_group_err(leaf, slot,
697 				"invalid block group size 0");
698 		return -EUCLEAN;
699 	}
700 
701 	if (unlikely(item_size != sizeof(bgi))) {
702 		block_group_err(leaf, slot,
703 			"invalid item size, have %u expect %zu",
704 				item_size, sizeof(bgi));
705 		return -EUCLEAN;
706 	}
707 
708 	read_extent_buffer(leaf, &bgi, btrfs_item_ptr_offset(leaf, slot),
709 			   sizeof(bgi));
710 	chunk_objectid = btrfs_stack_block_group_chunk_objectid(&bgi);
711 	if (btrfs_fs_incompat(fs_info, EXTENT_TREE_V2)) {
712 		/*
713 		 * We don't init the nr_global_roots until we load the global
714 		 * roots, so this could be 0 at mount time.  If it's 0 we'll
715 		 * just assume we're fine, and later we'll check against our
716 		 * actual value.
717 		 */
718 		if (unlikely(fs_info->nr_global_roots &&
719 			     chunk_objectid >= fs_info->nr_global_roots)) {
720 			block_group_err(leaf, slot,
721 	"invalid block group global root id, have %llu, needs to be <= %llu",
722 					chunk_objectid,
723 					fs_info->nr_global_roots);
724 			return -EUCLEAN;
725 		}
726 	} else if (unlikely(chunk_objectid != BTRFS_FIRST_CHUNK_TREE_OBJECTID)) {
727 		block_group_err(leaf, slot,
728 		"invalid block group chunk objectid, have %llu expect %llu",
729 				btrfs_stack_block_group_chunk_objectid(&bgi),
730 				BTRFS_FIRST_CHUNK_TREE_OBJECTID);
731 		return -EUCLEAN;
732 	}
733 
734 	if (unlikely(btrfs_stack_block_group_used(&bgi) > key->offset)) {
735 		block_group_err(leaf, slot,
736 			"invalid block group used, have %llu expect [0, %llu)",
737 				btrfs_stack_block_group_used(&bgi), key->offset);
738 		return -EUCLEAN;
739 	}
740 
741 	flags = btrfs_stack_block_group_flags(&bgi);
742 	if (unlikely(hweight64(flags & BTRFS_BLOCK_GROUP_PROFILE_MASK) > 1)) {
743 		block_group_err(leaf, slot,
744 "invalid profile flags, have 0x%llx (%lu bits set) expect no more than 1 bit set",
745 			flags & BTRFS_BLOCK_GROUP_PROFILE_MASK,
746 			hweight64(flags & BTRFS_BLOCK_GROUP_PROFILE_MASK));
747 		return -EUCLEAN;
748 	}
749 
750 	type = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
751 	if (unlikely(type != BTRFS_BLOCK_GROUP_DATA &&
752 		     type != BTRFS_BLOCK_GROUP_METADATA &&
753 		     type != BTRFS_BLOCK_GROUP_SYSTEM &&
754 		     type != (BTRFS_BLOCK_GROUP_METADATA |
755 			      BTRFS_BLOCK_GROUP_DATA))) {
756 		block_group_err(leaf, slot,
757 "invalid type, have 0x%llx (%lu bits set) expect either 0x%llx, 0x%llx, 0x%llx or 0x%llx",
758 			type, hweight64(type),
759 			BTRFS_BLOCK_GROUP_DATA, BTRFS_BLOCK_GROUP_METADATA,
760 			BTRFS_BLOCK_GROUP_SYSTEM,
761 			BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_DATA);
762 		return -EUCLEAN;
763 	}
764 	return 0;
765 }
766 
767 __printf(4, 5)
768 __cold
chunk_err(const struct extent_buffer * leaf,const struct btrfs_chunk * chunk,u64 logical,const char * fmt,...)769 static void chunk_err(const struct extent_buffer *leaf,
770 		      const struct btrfs_chunk *chunk, u64 logical,
771 		      const char *fmt, ...)
772 {
773 	const struct btrfs_fs_info *fs_info = leaf->fs_info;
774 	bool is_sb;
775 	struct va_format vaf;
776 	va_list args;
777 	int i;
778 	int slot = -1;
779 
780 	/* Only superblock eb is able to have such small offset */
781 	is_sb = (leaf->start == BTRFS_SUPER_INFO_OFFSET);
782 
783 	if (!is_sb) {
784 		/*
785 		 * Get the slot number by iterating through all slots, this
786 		 * would provide better readability.
787 		 */
788 		for (i = 0; i < btrfs_header_nritems(leaf); i++) {
789 			if (btrfs_item_ptr_offset(leaf, i) ==
790 					(unsigned long)chunk) {
791 				slot = i;
792 				break;
793 			}
794 		}
795 	}
796 	va_start(args, fmt);
797 	vaf.fmt = fmt;
798 	vaf.va = &args;
799 
800 	if (is_sb)
801 		btrfs_crit(fs_info,
802 		"corrupt superblock syschunk array: chunk_start=%llu, %pV",
803 			   logical, &vaf);
804 	else
805 		btrfs_crit(fs_info,
806 	"corrupt leaf: root=%llu block=%llu slot=%d chunk_start=%llu, %pV",
807 			   BTRFS_CHUNK_TREE_OBJECTID, leaf->start, slot,
808 			   logical, &vaf);
809 	va_end(args);
810 }
811 
812 /*
813  * The common chunk check which could also work on super block sys chunk array.
814  *
815  * Return -EUCLEAN if anything is corrupted.
816  * Return 0 if everything is OK.
817  */
btrfs_check_chunk_valid(struct extent_buffer * leaf,struct btrfs_chunk * chunk,u64 logical)818 int btrfs_check_chunk_valid(struct extent_buffer *leaf,
819 			    struct btrfs_chunk *chunk, u64 logical)
820 {
821 	struct btrfs_fs_info *fs_info = leaf->fs_info;
822 	u64 length;
823 	u64 chunk_end;
824 	u64 stripe_len;
825 	u16 num_stripes;
826 	u16 sub_stripes;
827 	u64 type;
828 	u64 features;
829 	bool mixed = false;
830 	int raid_index;
831 	int nparity;
832 	int ncopies;
833 
834 	length = btrfs_chunk_length(leaf, chunk);
835 	stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
836 	num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
837 	sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
838 	type = btrfs_chunk_type(leaf, chunk);
839 	raid_index = btrfs_bg_flags_to_raid_index(type);
840 	ncopies = btrfs_raid_array[raid_index].ncopies;
841 	nparity = btrfs_raid_array[raid_index].nparity;
842 
843 	if (unlikely(!num_stripes)) {
844 		chunk_err(leaf, chunk, logical,
845 			  "invalid chunk num_stripes, have %u", num_stripes);
846 		return -EUCLEAN;
847 	}
848 	if (unlikely(num_stripes < ncopies)) {
849 		chunk_err(leaf, chunk, logical,
850 			  "invalid chunk num_stripes < ncopies, have %u < %d",
851 			  num_stripes, ncopies);
852 		return -EUCLEAN;
853 	}
854 	if (unlikely(nparity && num_stripes == nparity)) {
855 		chunk_err(leaf, chunk, logical,
856 			  "invalid chunk num_stripes == nparity, have %u == %d",
857 			  num_stripes, nparity);
858 		return -EUCLEAN;
859 	}
860 	if (unlikely(!IS_ALIGNED(logical, fs_info->sectorsize))) {
861 		chunk_err(leaf, chunk, logical,
862 		"invalid chunk logical, have %llu should aligned to %u",
863 			  logical, fs_info->sectorsize);
864 		return -EUCLEAN;
865 	}
866 	if (unlikely(btrfs_chunk_sector_size(leaf, chunk) != fs_info->sectorsize)) {
867 		chunk_err(leaf, chunk, logical,
868 			  "invalid chunk sectorsize, have %u expect %u",
869 			  btrfs_chunk_sector_size(leaf, chunk),
870 			  fs_info->sectorsize);
871 		return -EUCLEAN;
872 	}
873 	if (unlikely(!length || !IS_ALIGNED(length, fs_info->sectorsize))) {
874 		chunk_err(leaf, chunk, logical,
875 			  "invalid chunk length, have %llu", length);
876 		return -EUCLEAN;
877 	}
878 	if (unlikely(check_add_overflow(logical, length, &chunk_end))) {
879 		chunk_err(leaf, chunk, logical,
880 "invalid chunk logical start and length, have logical start %llu length %llu",
881 			  logical, length);
882 		return -EUCLEAN;
883 	}
884 	if (unlikely(!is_power_of_2(stripe_len) || stripe_len != BTRFS_STRIPE_LEN)) {
885 		chunk_err(leaf, chunk, logical,
886 			  "invalid chunk stripe length: %llu",
887 			  stripe_len);
888 		return -EUCLEAN;
889 	}
890 	/*
891 	 * We artificially limit the chunk size, so that the number of stripes
892 	 * inside a chunk can be fit into a U32.  The current limit (256G) is
893 	 * way too large for real world usage anyway, and it's also much larger
894 	 * than our existing limit (10G).
895 	 *
896 	 * Thus it should be a good way to catch obvious bitflips.
897 	 */
898 	if (unlikely(length >= btrfs_stripe_nr_to_offset(U32_MAX))) {
899 		chunk_err(leaf, chunk, logical,
900 			  "chunk length too large: have %llu limit %llu",
901 			  length, btrfs_stripe_nr_to_offset(U32_MAX));
902 		return -EUCLEAN;
903 	}
904 	if (unlikely(type & ~(BTRFS_BLOCK_GROUP_TYPE_MASK |
905 			      BTRFS_BLOCK_GROUP_PROFILE_MASK))) {
906 		chunk_err(leaf, chunk, logical,
907 			  "unrecognized chunk type: 0x%llx",
908 			  ~(BTRFS_BLOCK_GROUP_TYPE_MASK |
909 			    BTRFS_BLOCK_GROUP_PROFILE_MASK) &
910 			  btrfs_chunk_type(leaf, chunk));
911 		return -EUCLEAN;
912 	}
913 
914 	if (unlikely(!has_single_bit_set(type & BTRFS_BLOCK_GROUP_PROFILE_MASK) &&
915 		     (type & BTRFS_BLOCK_GROUP_PROFILE_MASK) != 0)) {
916 		chunk_err(leaf, chunk, logical,
917 		"invalid chunk profile flag: 0x%llx, expect 0 or 1 bit set",
918 			  type & BTRFS_BLOCK_GROUP_PROFILE_MASK);
919 		return -EUCLEAN;
920 	}
921 	if (unlikely((type & BTRFS_BLOCK_GROUP_TYPE_MASK) == 0)) {
922 		chunk_err(leaf, chunk, logical,
923 	"missing chunk type flag, have 0x%llx one bit must be set in 0x%llx",
924 			  type, BTRFS_BLOCK_GROUP_TYPE_MASK);
925 		return -EUCLEAN;
926 	}
927 
928 	if (unlikely((type & BTRFS_BLOCK_GROUP_SYSTEM) &&
929 		     (type & (BTRFS_BLOCK_GROUP_METADATA |
930 			      BTRFS_BLOCK_GROUP_DATA)))) {
931 		chunk_err(leaf, chunk, logical,
932 			  "system chunk with data or metadata type: 0x%llx",
933 			  type);
934 		return -EUCLEAN;
935 	}
936 
937 	features = btrfs_super_incompat_flags(fs_info->super_copy);
938 	if (features & BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)
939 		mixed = true;
940 
941 	if (!mixed) {
942 		if (unlikely((type & BTRFS_BLOCK_GROUP_METADATA) &&
943 			     (type & BTRFS_BLOCK_GROUP_DATA))) {
944 			chunk_err(leaf, chunk, logical,
945 			"mixed chunk type in non-mixed mode: 0x%llx", type);
946 			return -EUCLEAN;
947 		}
948 	}
949 
950 	if (unlikely((type & BTRFS_BLOCK_GROUP_RAID10 &&
951 		      sub_stripes != btrfs_raid_array[BTRFS_RAID_RAID10].sub_stripes) ||
952 		     (type & BTRFS_BLOCK_GROUP_RAID1 &&
953 		      num_stripes != btrfs_raid_array[BTRFS_RAID_RAID1].devs_min) ||
954 		     (type & BTRFS_BLOCK_GROUP_RAID1C3 &&
955 		      num_stripes != btrfs_raid_array[BTRFS_RAID_RAID1C3].devs_min) ||
956 		     (type & BTRFS_BLOCK_GROUP_RAID1C4 &&
957 		      num_stripes != btrfs_raid_array[BTRFS_RAID_RAID1C4].devs_min) ||
958 		     (type & BTRFS_BLOCK_GROUP_RAID5 &&
959 		      num_stripes < btrfs_raid_array[BTRFS_RAID_RAID5].devs_min) ||
960 		     (type & BTRFS_BLOCK_GROUP_RAID6 &&
961 		      num_stripes < btrfs_raid_array[BTRFS_RAID_RAID6].devs_min) ||
962 		     (type & BTRFS_BLOCK_GROUP_DUP &&
963 		      num_stripes != btrfs_raid_array[BTRFS_RAID_DUP].dev_stripes) ||
964 		     ((type & BTRFS_BLOCK_GROUP_PROFILE_MASK) == 0 &&
965 		      num_stripes != btrfs_raid_array[BTRFS_RAID_SINGLE].dev_stripes))) {
966 		chunk_err(leaf, chunk, logical,
967 			"invalid num_stripes:sub_stripes %u:%u for profile %llu",
968 			num_stripes, sub_stripes,
969 			type & BTRFS_BLOCK_GROUP_PROFILE_MASK);
970 		return -EUCLEAN;
971 	}
972 
973 	return 0;
974 }
975 
976 /*
977  * Enhanced version of chunk item checker.
978  *
979  * The common btrfs_check_chunk_valid() doesn't check item size since it needs
980  * to work on super block sys_chunk_array which doesn't have full item ptr.
981  */
check_leaf_chunk_item(struct extent_buffer * leaf,struct btrfs_chunk * chunk,struct btrfs_key * key,int slot)982 static int check_leaf_chunk_item(struct extent_buffer *leaf,
983 				 struct btrfs_chunk *chunk,
984 				 struct btrfs_key *key, int slot)
985 {
986 	int num_stripes;
987 
988 	if (unlikely(btrfs_item_size(leaf, slot) < sizeof(struct btrfs_chunk))) {
989 		chunk_err(leaf, chunk, key->offset,
990 			"invalid chunk item size: have %u expect [%zu, %u)",
991 			btrfs_item_size(leaf, slot),
992 			sizeof(struct btrfs_chunk),
993 			BTRFS_LEAF_DATA_SIZE(leaf->fs_info));
994 		return -EUCLEAN;
995 	}
996 
997 	num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
998 	/* Let btrfs_check_chunk_valid() handle this error type */
999 	if (num_stripes == 0)
1000 		goto out;
1001 
1002 	if (unlikely(btrfs_chunk_item_size(num_stripes) !=
1003 		     btrfs_item_size(leaf, slot))) {
1004 		chunk_err(leaf, chunk, key->offset,
1005 			"invalid chunk item size: have %u expect %lu",
1006 			btrfs_item_size(leaf, slot),
1007 			btrfs_chunk_item_size(num_stripes));
1008 		return -EUCLEAN;
1009 	}
1010 out:
1011 	return btrfs_check_chunk_valid(leaf, chunk, key->offset);
1012 }
1013 
1014 __printf(3, 4)
1015 __cold
dev_item_err(const struct extent_buffer * eb,int slot,const char * fmt,...)1016 static void dev_item_err(const struct extent_buffer *eb, int slot,
1017 			 const char *fmt, ...)
1018 {
1019 	struct btrfs_key key;
1020 	struct va_format vaf;
1021 	va_list args;
1022 
1023 	btrfs_item_key_to_cpu(eb, &key, slot);
1024 	va_start(args, fmt);
1025 
1026 	vaf.fmt = fmt;
1027 	vaf.va = &args;
1028 
1029 	dump_page(folio_page(eb->folios[0], 0), "eb page dump");
1030 	btrfs_crit(eb->fs_info,
1031 	"corrupt %s: root=%llu block=%llu slot=%d devid=%llu %pV",
1032 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
1033 		btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
1034 		key.objectid, &vaf);
1035 	va_end(args);
1036 }
1037 
check_dev_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot)1038 static int check_dev_item(struct extent_buffer *leaf,
1039 			  struct btrfs_key *key, int slot)
1040 {
1041 	struct btrfs_dev_item *ditem;
1042 	const u32 item_size = btrfs_item_size(leaf, slot);
1043 
1044 	if (unlikely(key->objectid != BTRFS_DEV_ITEMS_OBJECTID)) {
1045 		dev_item_err(leaf, slot,
1046 			     "invalid objectid: has=%llu expect=%llu",
1047 			     key->objectid, BTRFS_DEV_ITEMS_OBJECTID);
1048 		return -EUCLEAN;
1049 	}
1050 
1051 	if (unlikely(item_size != sizeof(*ditem))) {
1052 		dev_item_err(leaf, slot, "invalid item size: has %u expect %zu",
1053 			     item_size, sizeof(*ditem));
1054 		return -EUCLEAN;
1055 	}
1056 
1057 	ditem = btrfs_item_ptr(leaf, slot, struct btrfs_dev_item);
1058 	if (unlikely(btrfs_device_id(leaf, ditem) != key->offset)) {
1059 		dev_item_err(leaf, slot,
1060 			     "devid mismatch: key has=%llu item has=%llu",
1061 			     key->offset, btrfs_device_id(leaf, ditem));
1062 		return -EUCLEAN;
1063 	}
1064 
1065 	/*
1066 	 * For device total_bytes, we don't have reliable way to check it, as
1067 	 * it can be 0 for device removal. Device size check can only be done
1068 	 * by dev extents check.
1069 	 */
1070 	if (unlikely(btrfs_device_bytes_used(leaf, ditem) >
1071 		     btrfs_device_total_bytes(leaf, ditem))) {
1072 		dev_item_err(leaf, slot,
1073 			     "invalid bytes used: have %llu expect [0, %llu]",
1074 			     btrfs_device_bytes_used(leaf, ditem),
1075 			     btrfs_device_total_bytes(leaf, ditem));
1076 		return -EUCLEAN;
1077 	}
1078 	/*
1079 	 * Remaining members like io_align/type/gen/dev_group aren't really
1080 	 * utilized.  Skip them to make later usage of them easier.
1081 	 */
1082 	return 0;
1083 }
1084 
check_inode_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot)1085 static int check_inode_item(struct extent_buffer *leaf,
1086 			    struct btrfs_key *key, int slot)
1087 {
1088 	struct btrfs_fs_info *fs_info = leaf->fs_info;
1089 	struct btrfs_inode_item *iitem;
1090 	u64 super_gen = btrfs_super_generation(fs_info->super_copy);
1091 	u32 valid_mask = (S_IFMT | S_ISUID | S_ISGID | S_ISVTX | 0777);
1092 	const u32 item_size = btrfs_item_size(leaf, slot);
1093 	u32 mode;
1094 	int ret;
1095 	u32 flags;
1096 	u32 ro_flags;
1097 
1098 	ret = check_inode_key(leaf, key, slot);
1099 	if (unlikely(ret < 0))
1100 		return ret;
1101 
1102 	if (unlikely(item_size != sizeof(*iitem))) {
1103 		generic_err(leaf, slot, "invalid item size: has %u expect %zu",
1104 			    item_size, sizeof(*iitem));
1105 		return -EUCLEAN;
1106 	}
1107 
1108 	iitem = btrfs_item_ptr(leaf, slot, struct btrfs_inode_item);
1109 
1110 	/* Here we use super block generation + 1 to handle log tree */
1111 	if (unlikely(btrfs_inode_generation(leaf, iitem) > super_gen + 1)) {
1112 		inode_item_err(leaf, slot,
1113 			"invalid inode generation: has %llu expect (0, %llu]",
1114 			       btrfs_inode_generation(leaf, iitem),
1115 			       super_gen + 1);
1116 		return -EUCLEAN;
1117 	}
1118 	/* Note for ROOT_TREE_DIR_ITEM, mkfs could set its transid 0 */
1119 	if (unlikely(btrfs_inode_transid(leaf, iitem) > super_gen + 1)) {
1120 		inode_item_err(leaf, slot,
1121 			"invalid inode transid: has %llu expect [0, %llu]",
1122 			       btrfs_inode_transid(leaf, iitem), super_gen + 1);
1123 		return -EUCLEAN;
1124 	}
1125 
1126 	/*
1127 	 * For size and nbytes it's better not to be too strict, as for dir
1128 	 * item its size/nbytes can easily get wrong, but doesn't affect
1129 	 * anything in the fs. So here we skip the check.
1130 	 */
1131 	mode = btrfs_inode_mode(leaf, iitem);
1132 	if (unlikely(mode & ~valid_mask)) {
1133 		inode_item_err(leaf, slot,
1134 			       "unknown mode bit detected: 0x%x",
1135 			       mode & ~valid_mask);
1136 		return -EUCLEAN;
1137 	}
1138 
1139 	/*
1140 	 * S_IFMT is not bit mapped so we can't completely rely on
1141 	 * is_power_of_2/has_single_bit_set, but it can save us from checking
1142 	 * FIFO/CHR/DIR/REG.  Only needs to check BLK, LNK and SOCKS
1143 	 */
1144 	if (!has_single_bit_set(mode & S_IFMT)) {
1145 		if (unlikely(!S_ISLNK(mode) && !S_ISBLK(mode) && !S_ISSOCK(mode))) {
1146 			inode_item_err(leaf, slot,
1147 			"invalid mode: has 0%o expect valid S_IF* bit(s)",
1148 				       mode & S_IFMT);
1149 			return -EUCLEAN;
1150 		}
1151 	}
1152 	if (unlikely(S_ISDIR(mode) && btrfs_inode_nlink(leaf, iitem) > 1)) {
1153 		inode_item_err(leaf, slot,
1154 		       "invalid nlink: has %u expect no more than 1 for dir",
1155 			btrfs_inode_nlink(leaf, iitem));
1156 		return -EUCLEAN;
1157 	}
1158 	btrfs_inode_split_flags(btrfs_inode_flags(leaf, iitem), &flags, &ro_flags);
1159 	if (unlikely(flags & ~BTRFS_INODE_FLAG_MASK)) {
1160 		inode_item_err(leaf, slot,
1161 			       "unknown incompat flags detected: 0x%x", flags);
1162 		return -EUCLEAN;
1163 	}
1164 	if (unlikely(!sb_rdonly(fs_info->sb) &&
1165 		     (ro_flags & ~BTRFS_INODE_RO_FLAG_MASK))) {
1166 		inode_item_err(leaf, slot,
1167 			"unknown ro-compat flags detected on writeable mount: 0x%x",
1168 			ro_flags);
1169 		return -EUCLEAN;
1170 	}
1171 	return 0;
1172 }
1173 
check_root_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot)1174 static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key,
1175 			   int slot)
1176 {
1177 	struct btrfs_fs_info *fs_info = leaf->fs_info;
1178 	struct btrfs_root_item ri = { 0 };
1179 	const u64 valid_root_flags = BTRFS_ROOT_SUBVOL_RDONLY |
1180 				     BTRFS_ROOT_SUBVOL_DEAD;
1181 	int ret;
1182 
1183 	ret = check_root_key(leaf, key, slot);
1184 	if (unlikely(ret < 0))
1185 		return ret;
1186 
1187 	if (unlikely(btrfs_item_size(leaf, slot) != sizeof(ri) &&
1188 		     btrfs_item_size(leaf, slot) !=
1189 		     btrfs_legacy_root_item_size())) {
1190 		generic_err(leaf, slot,
1191 			    "invalid root item size, have %u expect %zu or %u",
1192 			    btrfs_item_size(leaf, slot), sizeof(ri),
1193 			    btrfs_legacy_root_item_size());
1194 		return -EUCLEAN;
1195 	}
1196 
1197 	/*
1198 	 * For legacy root item, the members starting at generation_v2 will be
1199 	 * all filled with 0.
1200 	 * And since we allow geneartion_v2 as 0, it will still pass the check.
1201 	 */
1202 	read_extent_buffer(leaf, &ri, btrfs_item_ptr_offset(leaf, slot),
1203 			   btrfs_item_size(leaf, slot));
1204 
1205 	/* Generation related */
1206 	if (unlikely(btrfs_root_generation(&ri) >
1207 		     btrfs_super_generation(fs_info->super_copy) + 1)) {
1208 		generic_err(leaf, slot,
1209 			"invalid root generation, have %llu expect (0, %llu]",
1210 			    btrfs_root_generation(&ri),
1211 			    btrfs_super_generation(fs_info->super_copy) + 1);
1212 		return -EUCLEAN;
1213 	}
1214 	if (unlikely(btrfs_root_generation_v2(&ri) >
1215 		     btrfs_super_generation(fs_info->super_copy) + 1)) {
1216 		generic_err(leaf, slot,
1217 		"invalid root v2 generation, have %llu expect (0, %llu]",
1218 			    btrfs_root_generation_v2(&ri),
1219 			    btrfs_super_generation(fs_info->super_copy) + 1);
1220 		return -EUCLEAN;
1221 	}
1222 	if (unlikely(btrfs_root_last_snapshot(&ri) >
1223 		     btrfs_super_generation(fs_info->super_copy) + 1)) {
1224 		generic_err(leaf, slot,
1225 		"invalid root last_snapshot, have %llu expect (0, %llu]",
1226 			    btrfs_root_last_snapshot(&ri),
1227 			    btrfs_super_generation(fs_info->super_copy) + 1);
1228 		return -EUCLEAN;
1229 	}
1230 
1231 	/* Alignment and level check */
1232 	if (unlikely(!IS_ALIGNED(btrfs_root_bytenr(&ri), fs_info->sectorsize))) {
1233 		generic_err(leaf, slot,
1234 		"invalid root bytenr, have %llu expect to be aligned to %u",
1235 			    btrfs_root_bytenr(&ri), fs_info->sectorsize);
1236 		return -EUCLEAN;
1237 	}
1238 	if (unlikely(btrfs_root_level(&ri) >= BTRFS_MAX_LEVEL)) {
1239 		generic_err(leaf, slot,
1240 			    "invalid root level, have %u expect [0, %u]",
1241 			    btrfs_root_level(&ri), BTRFS_MAX_LEVEL - 1);
1242 		return -EUCLEAN;
1243 	}
1244 	if (unlikely(btrfs_root_drop_level(&ri) >= BTRFS_MAX_LEVEL)) {
1245 		generic_err(leaf, slot,
1246 			    "invalid root level, have %u expect [0, %u]",
1247 			    btrfs_root_drop_level(&ri), BTRFS_MAX_LEVEL - 1);
1248 		return -EUCLEAN;
1249 	}
1250 
1251 	/* Flags check */
1252 	if (unlikely(btrfs_root_flags(&ri) & ~valid_root_flags)) {
1253 		generic_err(leaf, slot,
1254 			    "invalid root flags, have 0x%llx expect mask 0x%llx",
1255 			    btrfs_root_flags(&ri), valid_root_flags);
1256 		return -EUCLEAN;
1257 	}
1258 	return 0;
1259 }
1260 
1261 __printf(3,4)
1262 __cold
extent_err(const struct extent_buffer * eb,int slot,const char * fmt,...)1263 static void extent_err(const struct extent_buffer *eb, int slot,
1264 		       const char *fmt, ...)
1265 {
1266 	struct btrfs_key key;
1267 	struct va_format vaf;
1268 	va_list args;
1269 	u64 bytenr;
1270 	u64 len;
1271 
1272 	btrfs_item_key_to_cpu(eb, &key, slot);
1273 	bytenr = key.objectid;
1274 	if (key.type == BTRFS_METADATA_ITEM_KEY ||
1275 	    key.type == BTRFS_TREE_BLOCK_REF_KEY ||
1276 	    key.type == BTRFS_SHARED_BLOCK_REF_KEY)
1277 		len = eb->fs_info->nodesize;
1278 	else
1279 		len = key.offset;
1280 	va_start(args, fmt);
1281 
1282 	vaf.fmt = fmt;
1283 	vaf.va = &args;
1284 
1285 	dump_page(folio_page(eb->folios[0], 0), "eb page dump");
1286 	btrfs_crit(eb->fs_info,
1287 	"corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV",
1288 		btrfs_header_level(eb) == 0 ? "leaf" : "node",
1289 		eb->start, slot, bytenr, len, &vaf);
1290 	va_end(args);
1291 }
1292 
is_valid_dref_root(u64 rootid)1293 static bool is_valid_dref_root(u64 rootid)
1294 {
1295 	/*
1296 	 * The following tree root objectids are allowed to have a data backref:
1297 	 * - subvolume trees
1298 	 * - data reloc tree
1299 	 * - tree root
1300 	 *   For v1 space cache
1301 	 */
1302 	return is_fstree(rootid) || rootid == BTRFS_DATA_RELOC_TREE_OBJECTID ||
1303 	       rootid == BTRFS_ROOT_TREE_OBJECTID;
1304 }
1305 
check_extent_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot,struct btrfs_key * prev_key)1306 static int check_extent_item(struct extent_buffer *leaf,
1307 			     struct btrfs_key *key, int slot,
1308 			     struct btrfs_key *prev_key)
1309 {
1310 	struct btrfs_fs_info *fs_info = leaf->fs_info;
1311 	struct btrfs_extent_item *ei;
1312 	bool is_tree_block = false;
1313 	unsigned long ptr;	/* Current pointer inside inline refs */
1314 	unsigned long end;	/* Extent item end */
1315 	const u32 item_size = btrfs_item_size(leaf, slot);
1316 	u8 last_type = 0;
1317 	u64 last_seq = U64_MAX;
1318 	u64 flags;
1319 	u64 generation;
1320 	u64 total_refs;		/* Total refs in btrfs_extent_item */
1321 	u64 inline_refs = 0;	/* found total inline refs */
1322 
1323 	if (unlikely(key->type == BTRFS_METADATA_ITEM_KEY &&
1324 		     !btrfs_fs_incompat(fs_info, SKINNY_METADATA))) {
1325 		generic_err(leaf, slot,
1326 "invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled");
1327 		return -EUCLEAN;
1328 	}
1329 	/* key->objectid is the bytenr for both key types */
1330 	if (unlikely(!IS_ALIGNED(key->objectid, fs_info->sectorsize))) {
1331 		generic_err(leaf, slot,
1332 		"invalid key objectid, have %llu expect to be aligned to %u",
1333 			   key->objectid, fs_info->sectorsize);
1334 		return -EUCLEAN;
1335 	}
1336 
1337 	/* key->offset is tree level for METADATA_ITEM_KEY */
1338 	if (unlikely(key->type == BTRFS_METADATA_ITEM_KEY &&
1339 		     key->offset >= BTRFS_MAX_LEVEL)) {
1340 		extent_err(leaf, slot,
1341 			   "invalid tree level, have %llu expect [0, %u]",
1342 			   key->offset, BTRFS_MAX_LEVEL - 1);
1343 		return -EUCLEAN;
1344 	}
1345 
1346 	/*
1347 	 * EXTENT/METADATA_ITEM consists of:
1348 	 * 1) One btrfs_extent_item
1349 	 *    Records the total refs, type and generation of the extent.
1350 	 *
1351 	 * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only)
1352 	 *    Records the first key and level of the tree block.
1353 	 *
1354 	 * 2) Zero or more btrfs_extent_inline_ref(s)
1355 	 *    Each inline ref has one btrfs_extent_inline_ref shows:
1356 	 *    2.1) The ref type, one of the 4
1357 	 *         TREE_BLOCK_REF	Tree block only
1358 	 *         SHARED_BLOCK_REF	Tree block only
1359 	 *         EXTENT_DATA_REF	Data only
1360 	 *         SHARED_DATA_REF	Data only
1361 	 *    2.2) Ref type specific data
1362 	 *         Either using btrfs_extent_inline_ref::offset, or specific
1363 	 *         data structure.
1364 	 *
1365 	 *    All above inline items should follow the order:
1366 	 *
1367 	 *    - All btrfs_extent_inline_ref::type should be in an ascending
1368 	 *      order
1369 	 *
1370 	 *    - Within the same type, the items should follow a descending
1371 	 *      order by their sequence number. The sequence number is
1372 	 *      determined by:
1373 	 *      * btrfs_extent_inline_ref::offset for all types  other than
1374 	 *        EXTENT_DATA_REF
1375 	 *      * hash_extent_data_ref() for EXTENT_DATA_REF
1376 	 */
1377 	if (unlikely(item_size < sizeof(*ei))) {
1378 		extent_err(leaf, slot,
1379 			   "invalid item size, have %u expect [%zu, %u)",
1380 			   item_size, sizeof(*ei),
1381 			   BTRFS_LEAF_DATA_SIZE(fs_info));
1382 		return -EUCLEAN;
1383 	}
1384 	end = item_size + btrfs_item_ptr_offset(leaf, slot);
1385 
1386 	/* Checks against extent_item */
1387 	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
1388 	flags = btrfs_extent_flags(leaf, ei);
1389 	total_refs = btrfs_extent_refs(leaf, ei);
1390 	generation = btrfs_extent_generation(leaf, ei);
1391 	if (unlikely(generation >
1392 		     btrfs_super_generation(fs_info->super_copy) + 1)) {
1393 		extent_err(leaf, slot,
1394 			   "invalid generation, have %llu expect (0, %llu]",
1395 			   generation,
1396 			   btrfs_super_generation(fs_info->super_copy) + 1);
1397 		return -EUCLEAN;
1398 	}
1399 	if (unlikely(!has_single_bit_set(flags & (BTRFS_EXTENT_FLAG_DATA |
1400 						  BTRFS_EXTENT_FLAG_TREE_BLOCK)))) {
1401 		extent_err(leaf, slot,
1402 		"invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx",
1403 			flags, BTRFS_EXTENT_FLAG_DATA |
1404 			BTRFS_EXTENT_FLAG_TREE_BLOCK);
1405 		return -EUCLEAN;
1406 	}
1407 	is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK);
1408 	if (is_tree_block) {
1409 		if (unlikely(key->type == BTRFS_EXTENT_ITEM_KEY &&
1410 			     key->offset != fs_info->nodesize)) {
1411 			extent_err(leaf, slot,
1412 				   "invalid extent length, have %llu expect %u",
1413 				   key->offset, fs_info->nodesize);
1414 			return -EUCLEAN;
1415 		}
1416 	} else {
1417 		if (unlikely(key->type != BTRFS_EXTENT_ITEM_KEY)) {
1418 			extent_err(leaf, slot,
1419 			"invalid key type, have %u expect %u for data backref",
1420 				   key->type, BTRFS_EXTENT_ITEM_KEY);
1421 			return -EUCLEAN;
1422 		}
1423 		if (unlikely(!IS_ALIGNED(key->offset, fs_info->sectorsize))) {
1424 			extent_err(leaf, slot,
1425 			"invalid extent length, have %llu expect aligned to %u",
1426 				   key->offset, fs_info->sectorsize);
1427 			return -EUCLEAN;
1428 		}
1429 		if (unlikely(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
1430 			extent_err(leaf, slot,
1431 			"invalid extent flag, data has full backref set");
1432 			return -EUCLEAN;
1433 		}
1434 	}
1435 	ptr = (unsigned long)(struct btrfs_extent_item *)(ei + 1);
1436 
1437 	/* Check the special case of btrfs_tree_block_info */
1438 	if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) {
1439 		struct btrfs_tree_block_info *info;
1440 
1441 		info = (struct btrfs_tree_block_info *)ptr;
1442 		if (unlikely(btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL)) {
1443 			extent_err(leaf, slot,
1444 			"invalid tree block info level, have %u expect [0, %u]",
1445 				   btrfs_tree_block_level(leaf, info),
1446 				   BTRFS_MAX_LEVEL - 1);
1447 			return -EUCLEAN;
1448 		}
1449 		ptr = (unsigned long)(struct btrfs_tree_block_info *)(info + 1);
1450 	}
1451 
1452 	/* Check inline refs */
1453 	while (ptr < end) {
1454 		struct btrfs_extent_inline_ref *iref;
1455 		struct btrfs_extent_data_ref *dref;
1456 		struct btrfs_shared_data_ref *sref;
1457 		u64 seq;
1458 		u64 dref_root;
1459 		u64 dref_objectid;
1460 		u64 dref_offset;
1461 		u64 inline_offset;
1462 		u8 inline_type;
1463 
1464 		if (unlikely(ptr + sizeof(*iref) > end)) {
1465 			extent_err(leaf, slot,
1466 "inline ref item overflows extent item, ptr %lu iref size %zu end %lu",
1467 				   ptr, sizeof(*iref), end);
1468 			return -EUCLEAN;
1469 		}
1470 		iref = (struct btrfs_extent_inline_ref *)ptr;
1471 		inline_type = btrfs_extent_inline_ref_type(leaf, iref);
1472 		inline_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1473 		seq = inline_offset;
1474 		if (unlikely(ptr + btrfs_extent_inline_ref_size(inline_type) > end)) {
1475 			extent_err(leaf, slot,
1476 "inline ref item overflows extent item, ptr %lu iref size %u end %lu",
1477 				   ptr, btrfs_extent_inline_ref_size(inline_type), end);
1478 			return -EUCLEAN;
1479 		}
1480 
1481 		switch (inline_type) {
1482 		/* inline_offset is subvolid of the owner, no need to check */
1483 		case BTRFS_TREE_BLOCK_REF_KEY:
1484 			inline_refs++;
1485 			break;
1486 		/* Contains parent bytenr */
1487 		case BTRFS_SHARED_BLOCK_REF_KEY:
1488 			if (unlikely(!IS_ALIGNED(inline_offset,
1489 						 fs_info->sectorsize))) {
1490 				extent_err(leaf, slot,
1491 		"invalid tree parent bytenr, have %llu expect aligned to %u",
1492 					   inline_offset, fs_info->sectorsize);
1493 				return -EUCLEAN;
1494 			}
1495 			inline_refs++;
1496 			break;
1497 		/*
1498 		 * Contains owner subvolid, owner key objectid, adjusted offset.
1499 		 * The only obvious corruption can happen in that offset.
1500 		 */
1501 		case BTRFS_EXTENT_DATA_REF_KEY:
1502 			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1503 			dref_root = btrfs_extent_data_ref_root(leaf, dref);
1504 			dref_objectid = btrfs_extent_data_ref_objectid(leaf, dref);
1505 			dref_offset = btrfs_extent_data_ref_offset(leaf, dref);
1506 			seq = hash_extent_data_ref(
1507 					btrfs_extent_data_ref_root(leaf, dref),
1508 					btrfs_extent_data_ref_objectid(leaf, dref),
1509 					btrfs_extent_data_ref_offset(leaf, dref));
1510 			if (unlikely(!is_valid_dref_root(dref_root))) {
1511 				extent_err(leaf, slot,
1512 					   "invalid data ref root value %llu",
1513 					   dref_root);
1514 				return -EUCLEAN;
1515 			}
1516 			if (unlikely(dref_objectid < BTRFS_FIRST_FREE_OBJECTID ||
1517 				     dref_objectid > BTRFS_LAST_FREE_OBJECTID)) {
1518 				extent_err(leaf, slot,
1519 					   "invalid data ref objectid value %llu",
1520 					   dref_objectid);
1521 				return -EUCLEAN;
1522 			}
1523 			if (unlikely(!IS_ALIGNED(dref_offset,
1524 						 fs_info->sectorsize))) {
1525 				extent_err(leaf, slot,
1526 		"invalid data ref offset, have %llu expect aligned to %u",
1527 					   dref_offset, fs_info->sectorsize);
1528 				return -EUCLEAN;
1529 			}
1530 			inline_refs += btrfs_extent_data_ref_count(leaf, dref);
1531 			break;
1532 		/* Contains parent bytenr and ref count */
1533 		case BTRFS_SHARED_DATA_REF_KEY:
1534 			sref = (struct btrfs_shared_data_ref *)(iref + 1);
1535 			if (unlikely(!IS_ALIGNED(inline_offset,
1536 						 fs_info->sectorsize))) {
1537 				extent_err(leaf, slot,
1538 		"invalid data parent bytenr, have %llu expect aligned to %u",
1539 					   inline_offset, fs_info->sectorsize);
1540 				return -EUCLEAN;
1541 			}
1542 			inline_refs += btrfs_shared_data_ref_count(leaf, sref);
1543 			break;
1544 		case BTRFS_EXTENT_OWNER_REF_KEY:
1545 			WARN_ON(!btrfs_fs_incompat(fs_info, SIMPLE_QUOTA));
1546 			break;
1547 		default:
1548 			extent_err(leaf, slot, "unknown inline ref type: %u",
1549 				   inline_type);
1550 			return -EUCLEAN;
1551 		}
1552 		if (inline_type < last_type) {
1553 			extent_err(leaf, slot,
1554 				   "inline ref out-of-order: has type %u, prev type %u",
1555 				   inline_type, last_type);
1556 			return -EUCLEAN;
1557 		}
1558 		/* Type changed, allow the sequence starts from U64_MAX again. */
1559 		if (inline_type > last_type)
1560 			last_seq = U64_MAX;
1561 		if (seq > last_seq) {
1562 			extent_err(leaf, slot,
1563 "inline ref out-of-order: has type %u offset %llu seq 0x%llx, prev type %u seq 0x%llx",
1564 				   inline_type, inline_offset, seq,
1565 				   last_type, last_seq);
1566 			return -EUCLEAN;
1567 		}
1568 		last_type = inline_type;
1569 		last_seq = seq;
1570 		ptr += btrfs_extent_inline_ref_size(inline_type);
1571 	}
1572 	/* No padding is allowed */
1573 	if (unlikely(ptr != end)) {
1574 		extent_err(leaf, slot,
1575 			   "invalid extent item size, padding bytes found");
1576 		return -EUCLEAN;
1577 	}
1578 
1579 	/* Finally, check the inline refs against total refs */
1580 	if (unlikely(inline_refs > total_refs)) {
1581 		extent_err(leaf, slot,
1582 			"invalid extent refs, have %llu expect >= inline %llu",
1583 			   total_refs, inline_refs);
1584 		return -EUCLEAN;
1585 	}
1586 
1587 	if ((prev_key->type == BTRFS_EXTENT_ITEM_KEY) ||
1588 	    (prev_key->type == BTRFS_METADATA_ITEM_KEY)) {
1589 		u64 prev_end = prev_key->objectid;
1590 
1591 		if (prev_key->type == BTRFS_METADATA_ITEM_KEY)
1592 			prev_end += fs_info->nodesize;
1593 		else
1594 			prev_end += prev_key->offset;
1595 
1596 		if (unlikely(prev_end > key->objectid)) {
1597 			extent_err(leaf, slot,
1598 	"previous extent [%llu %u %llu] overlaps current extent [%llu %u %llu]",
1599 				   prev_key->objectid, prev_key->type,
1600 				   prev_key->offset, key->objectid, key->type,
1601 				   key->offset);
1602 			return -EUCLEAN;
1603 		}
1604 	}
1605 
1606 	return 0;
1607 }
1608 
check_simple_keyed_refs(struct extent_buffer * leaf,struct btrfs_key * key,int slot)1609 static int check_simple_keyed_refs(struct extent_buffer *leaf,
1610 				   struct btrfs_key *key, int slot)
1611 {
1612 	u32 expect_item_size = 0;
1613 
1614 	if (key->type == BTRFS_SHARED_DATA_REF_KEY)
1615 		expect_item_size = sizeof(struct btrfs_shared_data_ref);
1616 
1617 	if (unlikely(btrfs_item_size(leaf, slot) != expect_item_size)) {
1618 		generic_err(leaf, slot,
1619 		"invalid item size, have %u expect %u for key type %u",
1620 			    btrfs_item_size(leaf, slot),
1621 			    expect_item_size, key->type);
1622 		return -EUCLEAN;
1623 	}
1624 	if (unlikely(!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize))) {
1625 		generic_err(leaf, slot,
1626 "invalid key objectid for shared block ref, have %llu expect aligned to %u",
1627 			    key->objectid, leaf->fs_info->sectorsize);
1628 		return -EUCLEAN;
1629 	}
1630 	if (unlikely(key->type != BTRFS_TREE_BLOCK_REF_KEY &&
1631 		     !IS_ALIGNED(key->offset, leaf->fs_info->sectorsize))) {
1632 		extent_err(leaf, slot,
1633 		"invalid tree parent bytenr, have %llu expect aligned to %u",
1634 			   key->offset, leaf->fs_info->sectorsize);
1635 		return -EUCLEAN;
1636 	}
1637 	return 0;
1638 }
1639 
check_extent_data_ref(struct extent_buffer * leaf,struct btrfs_key * key,int slot)1640 static int check_extent_data_ref(struct extent_buffer *leaf,
1641 				 struct btrfs_key *key, int slot)
1642 {
1643 	struct btrfs_extent_data_ref *dref;
1644 	unsigned long ptr = btrfs_item_ptr_offset(leaf, slot);
1645 	const unsigned long end = ptr + btrfs_item_size(leaf, slot);
1646 
1647 	if (unlikely(btrfs_item_size(leaf, slot) % sizeof(*dref) != 0)) {
1648 		generic_err(leaf, slot,
1649 	"invalid item size, have %u expect aligned to %zu for key type %u",
1650 			    btrfs_item_size(leaf, slot),
1651 			    sizeof(*dref), key->type);
1652 		return -EUCLEAN;
1653 	}
1654 	if (unlikely(!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize))) {
1655 		generic_err(leaf, slot,
1656 "invalid key objectid for shared block ref, have %llu expect aligned to %u",
1657 			    key->objectid, leaf->fs_info->sectorsize);
1658 		return -EUCLEAN;
1659 	}
1660 	for (; ptr < end; ptr += sizeof(*dref)) {
1661 		u64 root;
1662 		u64 objectid;
1663 		u64 offset;
1664 
1665 		/*
1666 		 * We cannot check the extent_data_ref hash due to possible
1667 		 * overflow from the leaf due to hash collisions.
1668 		 */
1669 		dref = (struct btrfs_extent_data_ref *)ptr;
1670 		root = btrfs_extent_data_ref_root(leaf, dref);
1671 		objectid = btrfs_extent_data_ref_objectid(leaf, dref);
1672 		offset = btrfs_extent_data_ref_offset(leaf, dref);
1673 		if (unlikely(!is_valid_dref_root(root))) {
1674 			extent_err(leaf, slot,
1675 				   "invalid extent data backref root value %llu",
1676 				   root);
1677 			return -EUCLEAN;
1678 		}
1679 		if (unlikely(objectid < BTRFS_FIRST_FREE_OBJECTID ||
1680 			     objectid > BTRFS_LAST_FREE_OBJECTID)) {
1681 			extent_err(leaf, slot,
1682 				   "invalid extent data backref objectid value %llu",
1683 				   root);
1684 			return -EUCLEAN;
1685 		}
1686 		if (unlikely(!IS_ALIGNED(offset, leaf->fs_info->sectorsize))) {
1687 			extent_err(leaf, slot,
1688 	"invalid extent data backref offset, have %llu expect aligned to %u",
1689 				   offset, leaf->fs_info->sectorsize);
1690 			return -EUCLEAN;
1691 		}
1692 	}
1693 	return 0;
1694 }
1695 
1696 #define inode_ref_err(eb, slot, fmt, args...)			\
1697 	inode_item_err(eb, slot, fmt, ##args)
check_inode_ref(struct extent_buffer * leaf,struct btrfs_key * key,struct btrfs_key * prev_key,int slot)1698 static int check_inode_ref(struct extent_buffer *leaf,
1699 			   struct btrfs_key *key, struct btrfs_key *prev_key,
1700 			   int slot)
1701 {
1702 	struct btrfs_inode_ref *iref;
1703 	unsigned long ptr;
1704 	unsigned long end;
1705 
1706 	if (unlikely(!check_prev_ino(leaf, key, slot, prev_key)))
1707 		return -EUCLEAN;
1708 	/* namelen can't be 0, so item_size == sizeof() is also invalid */
1709 	if (unlikely(btrfs_item_size(leaf, slot) <= sizeof(*iref))) {
1710 		inode_ref_err(leaf, slot,
1711 			"invalid item size, have %u expect (%zu, %u)",
1712 			btrfs_item_size(leaf, slot),
1713 			sizeof(*iref), BTRFS_LEAF_DATA_SIZE(leaf->fs_info));
1714 		return -EUCLEAN;
1715 	}
1716 
1717 	ptr = btrfs_item_ptr_offset(leaf, slot);
1718 	end = ptr + btrfs_item_size(leaf, slot);
1719 	while (ptr < end) {
1720 		u16 namelen;
1721 
1722 		if (unlikely(ptr + sizeof(iref) > end)) {
1723 			inode_ref_err(leaf, slot,
1724 			"inode ref overflow, ptr %lu end %lu inode_ref_size %zu",
1725 				ptr, end, sizeof(iref));
1726 			return -EUCLEAN;
1727 		}
1728 
1729 		iref = (struct btrfs_inode_ref *)ptr;
1730 		namelen = btrfs_inode_ref_name_len(leaf, iref);
1731 		if (unlikely(ptr + sizeof(*iref) + namelen > end)) {
1732 			inode_ref_err(leaf, slot,
1733 				"inode ref overflow, ptr %lu end %lu namelen %u",
1734 				ptr, end, namelen);
1735 			return -EUCLEAN;
1736 		}
1737 
1738 		/*
1739 		 * NOTE: In theory we should record all found index numbers
1740 		 * to find any duplicated indexes, but that will be too time
1741 		 * consuming for inodes with too many hard links.
1742 		 */
1743 		ptr += sizeof(*iref) + namelen;
1744 	}
1745 	return 0;
1746 }
1747 
check_raid_stripe_extent(const struct extent_buffer * leaf,const struct btrfs_key * key,int slot)1748 static int check_raid_stripe_extent(const struct extent_buffer *leaf,
1749 				    const struct btrfs_key *key, int slot)
1750 {
1751 	if (unlikely(!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize))) {
1752 		generic_err(leaf, slot,
1753 "invalid key objectid for raid stripe extent, have %llu expect aligned to %u",
1754 			    key->objectid, leaf->fs_info->sectorsize);
1755 		return -EUCLEAN;
1756 	}
1757 
1758 	if (unlikely(!btrfs_fs_incompat(leaf->fs_info, RAID_STRIPE_TREE))) {
1759 		generic_err(leaf, slot,
1760 	"RAID_STRIPE_EXTENT present but RAID_STRIPE_TREE incompat bit unset");
1761 		return -EUCLEAN;
1762 	}
1763 
1764 	return 0;
1765 }
1766 
check_dev_extent_item(const struct extent_buffer * leaf,const struct btrfs_key * key,int slot,struct btrfs_key * prev_key)1767 static int check_dev_extent_item(const struct extent_buffer *leaf,
1768 				 const struct btrfs_key *key,
1769 				 int slot,
1770 				 struct btrfs_key *prev_key)
1771 {
1772 	struct btrfs_dev_extent *de;
1773 	const u32 sectorsize = leaf->fs_info->sectorsize;
1774 
1775 	de = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
1776 	/* Basic fixed member checks. */
1777 	if (unlikely(btrfs_dev_extent_chunk_tree(leaf, de) !=
1778 		     BTRFS_CHUNK_TREE_OBJECTID)) {
1779 		generic_err(leaf, slot,
1780 			    "invalid dev extent chunk tree id, has %llu expect %llu",
1781 			    btrfs_dev_extent_chunk_tree(leaf, de),
1782 			    BTRFS_CHUNK_TREE_OBJECTID);
1783 		return -EUCLEAN;
1784 	}
1785 	if (unlikely(btrfs_dev_extent_chunk_objectid(leaf, de) !=
1786 		     BTRFS_FIRST_CHUNK_TREE_OBJECTID)) {
1787 		generic_err(leaf, slot,
1788 			    "invalid dev extent chunk objectid, has %llu expect %llu",
1789 			    btrfs_dev_extent_chunk_objectid(leaf, de),
1790 			    BTRFS_FIRST_CHUNK_TREE_OBJECTID);
1791 		return -EUCLEAN;
1792 	}
1793 	/* Alignment check. */
1794 	if (unlikely(!IS_ALIGNED(key->offset, sectorsize))) {
1795 		generic_err(leaf, slot,
1796 			    "invalid dev extent key.offset, has %llu not aligned to %u",
1797 			    key->offset, sectorsize);
1798 		return -EUCLEAN;
1799 	}
1800 	if (unlikely(!IS_ALIGNED(btrfs_dev_extent_chunk_offset(leaf, de),
1801 				 sectorsize))) {
1802 		generic_err(leaf, slot,
1803 			    "invalid dev extent chunk offset, has %llu not aligned to %u",
1804 			    btrfs_dev_extent_chunk_objectid(leaf, de),
1805 			    sectorsize);
1806 		return -EUCLEAN;
1807 	}
1808 	if (unlikely(!IS_ALIGNED(btrfs_dev_extent_length(leaf, de),
1809 				 sectorsize))) {
1810 		generic_err(leaf, slot,
1811 			    "invalid dev extent length, has %llu not aligned to %u",
1812 			    btrfs_dev_extent_length(leaf, de), sectorsize);
1813 		return -EUCLEAN;
1814 	}
1815 	/* Overlap check with previous dev extent. */
1816 	if (slot && prev_key->objectid == key->objectid &&
1817 	    prev_key->type == key->type) {
1818 		struct btrfs_dev_extent *prev_de;
1819 		u64 prev_len;
1820 
1821 		prev_de = btrfs_item_ptr(leaf, slot - 1, struct btrfs_dev_extent);
1822 		prev_len = btrfs_dev_extent_length(leaf, prev_de);
1823 		if (unlikely(prev_key->offset + prev_len > key->offset)) {
1824 			generic_err(leaf, slot,
1825 		"dev extent overlap, prev offset %llu len %llu current offset %llu",
1826 				    prev_key->objectid, prev_len, key->offset);
1827 			return -EUCLEAN;
1828 		}
1829 	}
1830 	return 0;
1831 }
1832 
1833 /*
1834  * Common point to switch the item-specific validation.
1835  */
check_leaf_item(struct extent_buffer * leaf,struct btrfs_key * key,int slot,struct btrfs_key * prev_key)1836 static enum btrfs_tree_block_status check_leaf_item(struct extent_buffer *leaf,
1837 						    struct btrfs_key *key,
1838 						    int slot,
1839 						    struct btrfs_key *prev_key)
1840 {
1841 	int ret = 0;
1842 	struct btrfs_chunk *chunk;
1843 
1844 	switch (key->type) {
1845 	case BTRFS_EXTENT_DATA_KEY:
1846 		ret = check_extent_data_item(leaf, key, slot, prev_key);
1847 		break;
1848 	case BTRFS_EXTENT_CSUM_KEY:
1849 		ret = check_csum_item(leaf, key, slot, prev_key);
1850 		break;
1851 	case BTRFS_DIR_ITEM_KEY:
1852 	case BTRFS_DIR_INDEX_KEY:
1853 	case BTRFS_XATTR_ITEM_KEY:
1854 		ret = check_dir_item(leaf, key, prev_key, slot);
1855 		break;
1856 	case BTRFS_INODE_REF_KEY:
1857 		ret = check_inode_ref(leaf, key, prev_key, slot);
1858 		break;
1859 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
1860 		ret = check_block_group_item(leaf, key, slot);
1861 		break;
1862 	case BTRFS_CHUNK_ITEM_KEY:
1863 		chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
1864 		ret = check_leaf_chunk_item(leaf, chunk, key, slot);
1865 		break;
1866 	case BTRFS_DEV_ITEM_KEY:
1867 		ret = check_dev_item(leaf, key, slot);
1868 		break;
1869 	case BTRFS_DEV_EXTENT_KEY:
1870 		ret = check_dev_extent_item(leaf, key, slot, prev_key);
1871 		break;
1872 	case BTRFS_INODE_ITEM_KEY:
1873 		ret = check_inode_item(leaf, key, slot);
1874 		break;
1875 	case BTRFS_ROOT_ITEM_KEY:
1876 		ret = check_root_item(leaf, key, slot);
1877 		break;
1878 	case BTRFS_EXTENT_ITEM_KEY:
1879 	case BTRFS_METADATA_ITEM_KEY:
1880 		ret = check_extent_item(leaf, key, slot, prev_key);
1881 		break;
1882 	case BTRFS_TREE_BLOCK_REF_KEY:
1883 	case BTRFS_SHARED_DATA_REF_KEY:
1884 	case BTRFS_SHARED_BLOCK_REF_KEY:
1885 		ret = check_simple_keyed_refs(leaf, key, slot);
1886 		break;
1887 	case BTRFS_EXTENT_DATA_REF_KEY:
1888 		ret = check_extent_data_ref(leaf, key, slot);
1889 		break;
1890 	case BTRFS_RAID_STRIPE_KEY:
1891 		ret = check_raid_stripe_extent(leaf, key, slot);
1892 		break;
1893 	}
1894 
1895 	if (ret)
1896 		return BTRFS_TREE_BLOCK_INVALID_ITEM;
1897 	return BTRFS_TREE_BLOCK_CLEAN;
1898 }
1899 
__btrfs_check_leaf(struct extent_buffer * leaf)1900 enum btrfs_tree_block_status __btrfs_check_leaf(struct extent_buffer *leaf)
1901 {
1902 	struct btrfs_fs_info *fs_info = leaf->fs_info;
1903 	/* No valid key type is 0, so all key should be larger than this key */
1904 	struct btrfs_key prev_key = {0, 0, 0};
1905 	struct btrfs_key key;
1906 	u32 nritems = btrfs_header_nritems(leaf);
1907 	int slot;
1908 
1909 	if (unlikely(btrfs_header_level(leaf) != 0)) {
1910 		generic_err(leaf, 0,
1911 			"invalid level for leaf, have %d expect 0",
1912 			btrfs_header_level(leaf));
1913 		return BTRFS_TREE_BLOCK_INVALID_LEVEL;
1914 	}
1915 
1916 	if (unlikely(!btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_WRITTEN))) {
1917 		generic_err(leaf, 0, "invalid flag for leaf, WRITTEN not set");
1918 		return BTRFS_TREE_BLOCK_WRITTEN_NOT_SET;
1919 	}
1920 
1921 	/*
1922 	 * Extent buffers from a relocation tree have a owner field that
1923 	 * corresponds to the subvolume tree they are based on. So just from an
1924 	 * extent buffer alone we can not find out what is the id of the
1925 	 * corresponding subvolume tree, so we can not figure out if the extent
1926 	 * buffer corresponds to the root of the relocation tree or not. So
1927 	 * skip this check for relocation trees.
1928 	 */
1929 	if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
1930 		u64 owner = btrfs_header_owner(leaf);
1931 
1932 		/* These trees must never be empty */
1933 		if (unlikely(owner == BTRFS_ROOT_TREE_OBJECTID ||
1934 			     owner == BTRFS_CHUNK_TREE_OBJECTID ||
1935 			     owner == BTRFS_DEV_TREE_OBJECTID ||
1936 			     owner == BTRFS_FS_TREE_OBJECTID ||
1937 			     owner == BTRFS_DATA_RELOC_TREE_OBJECTID)) {
1938 			generic_err(leaf, 0,
1939 			"invalid root, root %llu must never be empty",
1940 				    owner);
1941 			return BTRFS_TREE_BLOCK_INVALID_NRITEMS;
1942 		}
1943 
1944 		/* Unknown tree */
1945 		if (unlikely(owner == 0)) {
1946 			generic_err(leaf, 0,
1947 				"invalid owner, root 0 is not defined");
1948 			return BTRFS_TREE_BLOCK_INVALID_OWNER;
1949 		}
1950 
1951 		/* EXTENT_TREE_V2 can have empty extent trees. */
1952 		if (btrfs_fs_incompat(fs_info, EXTENT_TREE_V2))
1953 			return BTRFS_TREE_BLOCK_CLEAN;
1954 
1955 		if (unlikely(owner == BTRFS_EXTENT_TREE_OBJECTID)) {
1956 			generic_err(leaf, 0,
1957 			"invalid root, root %llu must never be empty",
1958 				    owner);
1959 			return BTRFS_TREE_BLOCK_INVALID_NRITEMS;
1960 		}
1961 
1962 		return BTRFS_TREE_BLOCK_CLEAN;
1963 	}
1964 
1965 	if (unlikely(nritems == 0))
1966 		return BTRFS_TREE_BLOCK_CLEAN;
1967 
1968 	/*
1969 	 * Check the following things to make sure this is a good leaf, and
1970 	 * leaf users won't need to bother with similar sanity checks:
1971 	 *
1972 	 * 1) key ordering
1973 	 * 2) item offset and size
1974 	 *    No overlap, no hole, all inside the leaf.
1975 	 * 3) item content
1976 	 *    If possible, do comprehensive sanity check.
1977 	 *    NOTE: All checks must only rely on the item data itself.
1978 	 */
1979 	for (slot = 0; slot < nritems; slot++) {
1980 		u32 item_end_expected;
1981 		u64 item_data_end;
1982 		enum btrfs_tree_block_status ret;
1983 
1984 		btrfs_item_key_to_cpu(leaf, &key, slot);
1985 
1986 		/* Make sure the keys are in the right order */
1987 		if (unlikely(btrfs_comp_cpu_keys(&prev_key, &key) >= 0)) {
1988 			generic_err(leaf, slot,
1989 	"bad key order, prev (%llu %u %llu) current (%llu %u %llu)",
1990 				prev_key.objectid, prev_key.type,
1991 				prev_key.offset, key.objectid, key.type,
1992 				key.offset);
1993 			return BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
1994 		}
1995 
1996 		item_data_end = (u64)btrfs_item_offset(leaf, slot) +
1997 				btrfs_item_size(leaf, slot);
1998 		/*
1999 		 * Make sure the offset and ends are right, remember that the
2000 		 * item data starts at the end of the leaf and grows towards the
2001 		 * front.
2002 		 */
2003 		if (slot == 0)
2004 			item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
2005 		else
2006 			item_end_expected = btrfs_item_offset(leaf,
2007 								 slot - 1);
2008 		if (unlikely(item_data_end != item_end_expected)) {
2009 			generic_err(leaf, slot,
2010 				"unexpected item end, have %llu expect %u",
2011 				item_data_end, item_end_expected);
2012 			return BTRFS_TREE_BLOCK_INVALID_OFFSETS;
2013 		}
2014 
2015 		/*
2016 		 * Check to make sure that we don't point outside of the leaf,
2017 		 * just in case all the items are consistent to each other, but
2018 		 * all point outside of the leaf.
2019 		 */
2020 		if (unlikely(item_data_end > BTRFS_LEAF_DATA_SIZE(fs_info))) {
2021 			generic_err(leaf, slot,
2022 			"slot end outside of leaf, have %llu expect range [0, %u]",
2023 				item_data_end, BTRFS_LEAF_DATA_SIZE(fs_info));
2024 			return BTRFS_TREE_BLOCK_INVALID_OFFSETS;
2025 		}
2026 
2027 		/* Also check if the item pointer overlaps with btrfs item. */
2028 		if (unlikely(btrfs_item_ptr_offset(leaf, slot) <
2029 			     btrfs_item_nr_offset(leaf, slot) + sizeof(struct btrfs_item))) {
2030 			generic_err(leaf, slot,
2031 		"slot overlaps with its data, item end %lu data start %lu",
2032 				btrfs_item_nr_offset(leaf, slot) +
2033 				sizeof(struct btrfs_item),
2034 				btrfs_item_ptr_offset(leaf, slot));
2035 			return BTRFS_TREE_BLOCK_INVALID_OFFSETS;
2036 		}
2037 
2038 		/* Check if the item size and content meet other criteria. */
2039 		ret = check_leaf_item(leaf, &key, slot, &prev_key);
2040 		if (unlikely(ret != BTRFS_TREE_BLOCK_CLEAN))
2041 			return ret;
2042 
2043 		prev_key.objectid = key.objectid;
2044 		prev_key.type = key.type;
2045 		prev_key.offset = key.offset;
2046 	}
2047 
2048 	return BTRFS_TREE_BLOCK_CLEAN;
2049 }
2050 
btrfs_check_leaf(struct extent_buffer * leaf)2051 int btrfs_check_leaf(struct extent_buffer *leaf)
2052 {
2053 	enum btrfs_tree_block_status ret;
2054 
2055 	ret = __btrfs_check_leaf(leaf);
2056 	if (unlikely(ret != BTRFS_TREE_BLOCK_CLEAN))
2057 		return -EUCLEAN;
2058 	return 0;
2059 }
2060 ALLOW_ERROR_INJECTION(btrfs_check_leaf, ERRNO);
2061 
__btrfs_check_node(struct extent_buffer * node)2062 enum btrfs_tree_block_status __btrfs_check_node(struct extent_buffer *node)
2063 {
2064 	struct btrfs_fs_info *fs_info = node->fs_info;
2065 	unsigned long nr = btrfs_header_nritems(node);
2066 	struct btrfs_key key, next_key;
2067 	int slot;
2068 	int level = btrfs_header_level(node);
2069 	u64 bytenr;
2070 
2071 	if (unlikely(!btrfs_header_flag(node, BTRFS_HEADER_FLAG_WRITTEN))) {
2072 		generic_err(node, 0, "invalid flag for node, WRITTEN not set");
2073 		return BTRFS_TREE_BLOCK_WRITTEN_NOT_SET;
2074 	}
2075 
2076 	if (unlikely(level <= 0 || level >= BTRFS_MAX_LEVEL)) {
2077 		generic_err(node, 0,
2078 			"invalid level for node, have %d expect [1, %d]",
2079 			level, BTRFS_MAX_LEVEL - 1);
2080 		return BTRFS_TREE_BLOCK_INVALID_LEVEL;
2081 	}
2082 	if (unlikely(nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(fs_info))) {
2083 		btrfs_crit(fs_info,
2084 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]",
2085 			   btrfs_header_owner(node), node->start,
2086 			   nr == 0 ? "small" : "large", nr,
2087 			   BTRFS_NODEPTRS_PER_BLOCK(fs_info));
2088 		return BTRFS_TREE_BLOCK_INVALID_NRITEMS;
2089 	}
2090 
2091 	for (slot = 0; slot < nr - 1; slot++) {
2092 		bytenr = btrfs_node_blockptr(node, slot);
2093 		btrfs_node_key_to_cpu(node, &key, slot);
2094 		btrfs_node_key_to_cpu(node, &next_key, slot + 1);
2095 
2096 		if (unlikely(!bytenr)) {
2097 			generic_err(node, slot,
2098 				"invalid NULL node pointer");
2099 			return BTRFS_TREE_BLOCK_INVALID_BLOCKPTR;
2100 		}
2101 		if (unlikely(!IS_ALIGNED(bytenr, fs_info->sectorsize))) {
2102 			generic_err(node, slot,
2103 			"unaligned pointer, have %llu should be aligned to %u",
2104 				bytenr, fs_info->sectorsize);
2105 			return BTRFS_TREE_BLOCK_INVALID_BLOCKPTR;
2106 		}
2107 
2108 		if (unlikely(btrfs_comp_cpu_keys(&key, &next_key) >= 0)) {
2109 			generic_err(node, slot,
2110 	"bad key order, current (%llu %u %llu) next (%llu %u %llu)",
2111 				key.objectid, key.type, key.offset,
2112 				next_key.objectid, next_key.type,
2113 				next_key.offset);
2114 			return BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
2115 		}
2116 	}
2117 	return BTRFS_TREE_BLOCK_CLEAN;
2118 }
2119 
btrfs_check_node(struct extent_buffer * node)2120 int btrfs_check_node(struct extent_buffer *node)
2121 {
2122 	enum btrfs_tree_block_status ret;
2123 
2124 	ret = __btrfs_check_node(node);
2125 	if (unlikely(ret != BTRFS_TREE_BLOCK_CLEAN))
2126 		return -EUCLEAN;
2127 	return 0;
2128 }
2129 ALLOW_ERROR_INJECTION(btrfs_check_node, ERRNO);
2130 
btrfs_check_eb_owner(const struct extent_buffer * eb,u64 root_owner)2131 int btrfs_check_eb_owner(const struct extent_buffer *eb, u64 root_owner)
2132 {
2133 	const bool is_subvol = is_fstree(root_owner);
2134 	const u64 eb_owner = btrfs_header_owner(eb);
2135 
2136 	/*
2137 	 * Skip dummy fs, as selftests don't create unique ebs for each dummy
2138 	 * root.
2139 	 */
2140 	if (btrfs_is_testing(eb->fs_info))
2141 		return 0;
2142 	/*
2143 	 * There are several call sites (backref walking, qgroup, and data
2144 	 * reloc) passing 0 as @root_owner, as they are not holding the
2145 	 * tree root.  In that case, we can not do a reliable ownership check,
2146 	 * so just exit.
2147 	 */
2148 	if (root_owner == 0)
2149 		return 0;
2150 	/*
2151 	 * These trees use key.offset as their owner, our callers don't have
2152 	 * the extra capacity to pass key.offset here.  So we just skip them.
2153 	 */
2154 	if (root_owner == BTRFS_TREE_LOG_OBJECTID ||
2155 	    root_owner == BTRFS_TREE_RELOC_OBJECTID)
2156 		return 0;
2157 
2158 	if (!is_subvol) {
2159 		/* For non-subvolume trees, the eb owner should match root owner */
2160 		if (unlikely(root_owner != eb_owner)) {
2161 			btrfs_crit(eb->fs_info,
2162 "corrupted %s, root=%llu block=%llu owner mismatch, have %llu expect %llu",
2163 				btrfs_header_level(eb) == 0 ? "leaf" : "node",
2164 				root_owner, btrfs_header_bytenr(eb), eb_owner,
2165 				root_owner);
2166 			return -EUCLEAN;
2167 		}
2168 		return 0;
2169 	}
2170 
2171 	/*
2172 	 * For subvolume trees, owners can mismatch, but they should all belong
2173 	 * to subvolume trees.
2174 	 */
2175 	if (unlikely(is_subvol != is_fstree(eb_owner))) {
2176 		btrfs_crit(eb->fs_info,
2177 "corrupted %s, root=%llu block=%llu owner mismatch, have %llu expect [%llu, %llu]",
2178 			btrfs_header_level(eb) == 0 ? "leaf" : "node",
2179 			root_owner, btrfs_header_bytenr(eb), eb_owner,
2180 			BTRFS_FIRST_FREE_OBJECTID, BTRFS_LAST_FREE_OBJECTID);
2181 		return -EUCLEAN;
2182 	}
2183 	return 0;
2184 }
2185 
btrfs_verify_level_key(struct extent_buffer * eb,int level,struct btrfs_key * first_key,u64 parent_transid)2186 int btrfs_verify_level_key(struct extent_buffer *eb, int level,
2187 			   struct btrfs_key *first_key, u64 parent_transid)
2188 {
2189 	struct btrfs_fs_info *fs_info = eb->fs_info;
2190 	int found_level;
2191 	struct btrfs_key found_key;
2192 	int ret;
2193 
2194 	found_level = btrfs_header_level(eb);
2195 	if (found_level != level) {
2196 		WARN(IS_ENABLED(CONFIG_BTRFS_DEBUG),
2197 		     KERN_ERR "BTRFS: tree level check failed\n");
2198 		btrfs_err(fs_info,
2199 "tree level mismatch detected, bytenr=%llu level expected=%u has=%u",
2200 			  eb->start, level, found_level);
2201 		return -EIO;
2202 	}
2203 
2204 	if (!first_key)
2205 		return 0;
2206 
2207 	/*
2208 	 * For live tree block (new tree blocks in current transaction),
2209 	 * we need proper lock context to avoid race, which is impossible here.
2210 	 * So we only checks tree blocks which is read from disk, whose
2211 	 * generation <= fs_info->last_trans_committed.
2212 	 */
2213 	if (btrfs_header_generation(eb) > btrfs_get_last_trans_committed(fs_info))
2214 		return 0;
2215 
2216 	/* We have @first_key, so this @eb must have at least one item */
2217 	if (btrfs_header_nritems(eb) == 0) {
2218 		btrfs_err(fs_info,
2219 		"invalid tree nritems, bytenr=%llu nritems=0 expect >0",
2220 			  eb->start);
2221 		WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
2222 		return -EUCLEAN;
2223 	}
2224 
2225 	if (found_level)
2226 		btrfs_node_key_to_cpu(eb, &found_key, 0);
2227 	else
2228 		btrfs_item_key_to_cpu(eb, &found_key, 0);
2229 	ret = btrfs_comp_cpu_keys(first_key, &found_key);
2230 
2231 	if (ret) {
2232 		WARN(IS_ENABLED(CONFIG_BTRFS_DEBUG),
2233 		     KERN_ERR "BTRFS: tree first key check failed\n");
2234 		btrfs_err(fs_info,
2235 "tree first key mismatch detected, bytenr=%llu parent_transid=%llu key expected=(%llu,%u,%llu) has=(%llu,%u,%llu)",
2236 			  eb->start, parent_transid, first_key->objectid,
2237 			  first_key->type, first_key->offset,
2238 			  found_key.objectid, found_key.type,
2239 			  found_key.offset);
2240 	}
2241 	return ret;
2242 }
2243