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