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 "dir-item.h" 33 #include "raid-stripe-tree.h" 34 35 /* 36 * Error message should follow the following format: 37 * corrupt <type>: <identifier>, <reason>[, <bad_value>] 38 * 39 * @type: leaf or node 40 * @identifier: the necessary info to locate the leaf/node. 41 * It's recommended to decode key.objecitd/offset if it's 42 * meaningful. 43 * @reason: describe the error 44 * @bad_value: optional, it's recommended to output bad value and its 45 * expected value (range). 46 * 47 * Since comma is used to separate the components, only space is allowed 48 * inside each component. 49 */ 50 51 /* 52 * Append generic "corrupt leaf/node root=%llu block=%llu slot=%d: " to @fmt. 53 * Allows callers to customize the output. 54 */ 55 __printf(3, 4) 56 __cold 57 static void generic_err(const struct extent_buffer *eb, int slot, 58 const char *fmt, ...) 59 { 60 const struct btrfs_fs_info *fs_info = eb->fs_info; 61 struct va_format vaf; 62 va_list args; 63 64 va_start(args, fmt); 65 66 vaf.fmt = fmt; 67 vaf.va = &args; 68 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 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 btrfs_crit(fs_info, 97 "corrupt %s: root=%llu block=%llu slot=%d ino=%llu file_offset=%llu, %pV", 98 btrfs_header_level(eb) == 0 ? "leaf" : "node", 99 btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot, 100 key.objectid, key.offset, &vaf); 101 va_end(args); 102 } 103 104 /* 105 * Return 0 if the btrfs_file_extent_##name is aligned to @alignment 106 * Else return 1 107 */ 108 #define CHECK_FE_ALIGNED(leaf, slot, fi, name, alignment) \ 109 ({ \ 110 if (unlikely(!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), \ 111 (alignment)))) \ 112 file_extent_err((leaf), (slot), \ 113 "invalid %s for file extent, have %llu, should be aligned to %u", \ 114 (#name), btrfs_file_extent_##name((leaf), (fi)), \ 115 (alignment)); \ 116 (!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment))); \ 117 }) 118 119 static u64 file_extent_end(struct extent_buffer *leaf, 120 struct btrfs_key *key, 121 struct btrfs_file_extent_item *extent) 122 { 123 u64 end; 124 u64 len; 125 126 if (btrfs_file_extent_type(leaf, extent) == BTRFS_FILE_EXTENT_INLINE) { 127 len = btrfs_file_extent_ram_bytes(leaf, extent); 128 end = ALIGN(key->offset + len, leaf->fs_info->sectorsize); 129 } else { 130 len = btrfs_file_extent_num_bytes(leaf, extent); 131 end = key->offset + len; 132 } 133 return end; 134 } 135 136 /* 137 * Customized report for dir_item, the only new important information is 138 * key->objectid, which represents inode number 139 */ 140 __printf(3, 4) 141 __cold 142 static void dir_item_err(const struct extent_buffer *eb, int slot, 143 const char *fmt, ...) 144 { 145 const struct btrfs_fs_info *fs_info = eb->fs_info; 146 struct btrfs_key key; 147 struct va_format vaf; 148 va_list args; 149 150 btrfs_item_key_to_cpu(eb, &key, slot); 151 va_start(args, fmt); 152 153 vaf.fmt = fmt; 154 vaf.va = &args; 155 156 btrfs_crit(fs_info, 157 "corrupt %s: root=%llu block=%llu slot=%d ino=%llu, %pV", 158 btrfs_header_level(eb) == 0 ? "leaf" : "node", 159 btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot, 160 key.objectid, &vaf); 161 va_end(args); 162 } 163 164 /* 165 * This functions checks prev_key->objectid, to ensure current key and prev_key 166 * share the same objectid as inode number. 167 * 168 * This is to detect missing INODE_ITEM in subvolume trees. 169 * 170 * Return true if everything is OK or we don't need to check. 171 * Return false if anything is wrong. 172 */ 173 static bool check_prev_ino(struct extent_buffer *leaf, 174 struct btrfs_key *key, int slot, 175 struct btrfs_key *prev_key) 176 { 177 /* No prev key, skip check */ 178 if (slot == 0) 179 return true; 180 181 /* Only these key->types needs to be checked */ 182 ASSERT(key->type == BTRFS_XATTR_ITEM_KEY || 183 key->type == BTRFS_INODE_REF_KEY || 184 key->type == BTRFS_DIR_INDEX_KEY || 185 key->type == BTRFS_DIR_ITEM_KEY || 186 key->type == BTRFS_EXTENT_DATA_KEY); 187 188 /* 189 * Only subvolume trees along with their reloc trees need this check. 190 * Things like log tree doesn't follow this ino requirement. 191 */ 192 if (!is_fstree(btrfs_header_owner(leaf))) 193 return true; 194 195 if (key->objectid == prev_key->objectid) 196 return true; 197 198 /* Error found */ 199 dir_item_err(leaf, slot, 200 "invalid previous key objectid, have %llu expect %llu", 201 prev_key->objectid, key->objectid); 202 return false; 203 } 204 static int check_extent_data_item(struct extent_buffer *leaf, 205 struct btrfs_key *key, int slot, 206 struct btrfs_key *prev_key) 207 { 208 struct btrfs_fs_info *fs_info = leaf->fs_info; 209 struct btrfs_file_extent_item *fi; 210 u32 sectorsize = fs_info->sectorsize; 211 u32 item_size = btrfs_item_size(leaf, slot); 212 u64 extent_end; 213 214 if (unlikely(!IS_ALIGNED(key->offset, sectorsize))) { 215 file_extent_err(leaf, slot, 216 "unaligned file_offset for file extent, have %llu should be aligned to %u", 217 key->offset, sectorsize); 218 return -EUCLEAN; 219 } 220 221 /* 222 * Previous key must have the same key->objectid (ino). 223 * It can be XATTR_ITEM, INODE_ITEM or just another EXTENT_DATA. 224 * But if objectids mismatch, it means we have a missing 225 * INODE_ITEM. 226 */ 227 if (unlikely(!check_prev_ino(leaf, key, slot, prev_key))) 228 return -EUCLEAN; 229 230 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item); 231 232 /* 233 * Make sure the item contains at least inline header, so the file 234 * extent type is not some garbage. 235 */ 236 if (unlikely(item_size < BTRFS_FILE_EXTENT_INLINE_DATA_START)) { 237 file_extent_err(leaf, slot, 238 "invalid item size, have %u expect [%zu, %u)", 239 item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START, 240 SZ_4K); 241 return -EUCLEAN; 242 } 243 if (unlikely(btrfs_file_extent_type(leaf, fi) >= 244 BTRFS_NR_FILE_EXTENT_TYPES)) { 245 file_extent_err(leaf, slot, 246 "invalid type for file extent, have %u expect range [0, %u]", 247 btrfs_file_extent_type(leaf, fi), 248 BTRFS_NR_FILE_EXTENT_TYPES - 1); 249 return -EUCLEAN; 250 } 251 252 /* 253 * Support for new compression/encryption must introduce incompat flag, 254 * and must be caught in open_ctree(). 255 */ 256 if (unlikely(btrfs_file_extent_compression(leaf, fi) >= 257 BTRFS_NR_COMPRESS_TYPES)) { 258 file_extent_err(leaf, slot, 259 "invalid compression for file extent, have %u expect range [0, %u]", 260 btrfs_file_extent_compression(leaf, fi), 261 BTRFS_NR_COMPRESS_TYPES - 1); 262 return -EUCLEAN; 263 } 264 if (unlikely(btrfs_file_extent_encryption(leaf, fi))) { 265 file_extent_err(leaf, slot, 266 "invalid encryption for file extent, have %u expect 0", 267 btrfs_file_extent_encryption(leaf, fi)); 268 return -EUCLEAN; 269 } 270 if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) { 271 /* Inline extent must have 0 as key offset */ 272 if (unlikely(key->offset)) { 273 file_extent_err(leaf, slot, 274 "invalid file_offset for inline file extent, have %llu expect 0", 275 key->offset); 276 return -EUCLEAN; 277 } 278 279 /* Compressed inline extent has no on-disk size, skip it */ 280 if (btrfs_file_extent_compression(leaf, fi) != 281 BTRFS_COMPRESS_NONE) 282 return 0; 283 284 /* Uncompressed inline extent size must match item size */ 285 if (unlikely(item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START + 286 btrfs_file_extent_ram_bytes(leaf, fi))) { 287 file_extent_err(leaf, slot, 288 "invalid ram_bytes for uncompressed inline extent, have %u expect %llu", 289 item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START + 290 btrfs_file_extent_ram_bytes(leaf, fi)); 291 return -EUCLEAN; 292 } 293 return 0; 294 } 295 296 /* Regular or preallocated extent has fixed item size */ 297 if (unlikely(item_size != sizeof(*fi))) { 298 file_extent_err(leaf, slot, 299 "invalid item size for reg/prealloc file extent, have %u expect %zu", 300 item_size, sizeof(*fi)); 301 return -EUCLEAN; 302 } 303 if (unlikely(CHECK_FE_ALIGNED(leaf, slot, fi, ram_bytes, sectorsize) || 304 CHECK_FE_ALIGNED(leaf, slot, fi, disk_bytenr, sectorsize) || 305 CHECK_FE_ALIGNED(leaf, slot, fi, disk_num_bytes, sectorsize) || 306 CHECK_FE_ALIGNED(leaf, slot, fi, offset, sectorsize) || 307 CHECK_FE_ALIGNED(leaf, slot, fi, num_bytes, sectorsize))) 308 return -EUCLEAN; 309 310 /* Catch extent end overflow */ 311 if (unlikely(check_add_overflow(btrfs_file_extent_num_bytes(leaf, fi), 312 key->offset, &extent_end))) { 313 file_extent_err(leaf, slot, 314 "extent end overflow, have file offset %llu extent num bytes %llu", 315 key->offset, 316 btrfs_file_extent_num_bytes(leaf, fi)); 317 return -EUCLEAN; 318 } 319 320 /* 321 * Check that no two consecutive file extent items, in the same leaf, 322 * present ranges that overlap each other. 323 */ 324 if (slot > 0 && 325 prev_key->objectid == key->objectid && 326 prev_key->type == BTRFS_EXTENT_DATA_KEY) { 327 struct btrfs_file_extent_item *prev_fi; 328 u64 prev_end; 329 330 prev_fi = btrfs_item_ptr(leaf, slot - 1, 331 struct btrfs_file_extent_item); 332 prev_end = file_extent_end(leaf, prev_key, prev_fi); 333 if (unlikely(prev_end > key->offset)) { 334 file_extent_err(leaf, slot - 1, 335 "file extent end range (%llu) goes beyond start offset (%llu) of the next file extent", 336 prev_end, key->offset); 337 return -EUCLEAN; 338 } 339 } 340 341 return 0; 342 } 343 344 static int check_csum_item(struct extent_buffer *leaf, struct btrfs_key *key, 345 int slot, struct btrfs_key *prev_key) 346 { 347 struct btrfs_fs_info *fs_info = leaf->fs_info; 348 u32 sectorsize = fs_info->sectorsize; 349 const u32 csumsize = fs_info->csum_size; 350 351 if (unlikely(key->objectid != BTRFS_EXTENT_CSUM_OBJECTID)) { 352 generic_err(leaf, slot, 353 "invalid key objectid for csum item, have %llu expect %llu", 354 key->objectid, BTRFS_EXTENT_CSUM_OBJECTID); 355 return -EUCLEAN; 356 } 357 if (unlikely(!IS_ALIGNED(key->offset, sectorsize))) { 358 generic_err(leaf, slot, 359 "unaligned key offset for csum item, have %llu should be aligned to %u", 360 key->offset, sectorsize); 361 return -EUCLEAN; 362 } 363 if (unlikely(!IS_ALIGNED(btrfs_item_size(leaf, slot), csumsize))) { 364 generic_err(leaf, slot, 365 "unaligned item size for csum item, have %u should be aligned to %u", 366 btrfs_item_size(leaf, slot), csumsize); 367 return -EUCLEAN; 368 } 369 if (slot > 0 && prev_key->type == BTRFS_EXTENT_CSUM_KEY) { 370 u64 prev_csum_end; 371 u32 prev_item_size; 372 373 prev_item_size = btrfs_item_size(leaf, slot - 1); 374 prev_csum_end = (prev_item_size / csumsize) * sectorsize; 375 prev_csum_end += prev_key->offset; 376 if (unlikely(prev_csum_end > key->offset)) { 377 generic_err(leaf, slot - 1, 378 "csum end range (%llu) goes beyond the start range (%llu) of the next csum item", 379 prev_csum_end, key->offset); 380 return -EUCLEAN; 381 } 382 } 383 return 0; 384 } 385 386 /* Inode item error output has the same format as dir_item_err() */ 387 #define inode_item_err(eb, slot, fmt, ...) \ 388 dir_item_err(eb, slot, fmt, __VA_ARGS__) 389 390 static int check_inode_key(struct extent_buffer *leaf, struct btrfs_key *key, 391 int slot) 392 { 393 struct btrfs_key item_key; 394 bool is_inode_item; 395 396 btrfs_item_key_to_cpu(leaf, &item_key, slot); 397 is_inode_item = (item_key.type == BTRFS_INODE_ITEM_KEY); 398 399 /* For XATTR_ITEM, location key should be all 0 */ 400 if (item_key.type == BTRFS_XATTR_ITEM_KEY) { 401 if (unlikely(key->objectid != 0 || key->type != 0 || 402 key->offset != 0)) 403 return -EUCLEAN; 404 return 0; 405 } 406 407 if (unlikely((key->objectid < BTRFS_FIRST_FREE_OBJECTID || 408 key->objectid > BTRFS_LAST_FREE_OBJECTID) && 409 key->objectid != BTRFS_ROOT_TREE_DIR_OBJECTID && 410 key->objectid != BTRFS_FREE_INO_OBJECTID)) { 411 if (is_inode_item) { 412 generic_err(leaf, slot, 413 "invalid key objectid: has %llu expect %llu or [%llu, %llu] or %llu", 414 key->objectid, BTRFS_ROOT_TREE_DIR_OBJECTID, 415 BTRFS_FIRST_FREE_OBJECTID, 416 BTRFS_LAST_FREE_OBJECTID, 417 BTRFS_FREE_INO_OBJECTID); 418 } else { 419 dir_item_err(leaf, slot, 420 "invalid location key objectid: has %llu expect %llu or [%llu, %llu] or %llu", 421 key->objectid, BTRFS_ROOT_TREE_DIR_OBJECTID, 422 BTRFS_FIRST_FREE_OBJECTID, 423 BTRFS_LAST_FREE_OBJECTID, 424 BTRFS_FREE_INO_OBJECTID); 425 } 426 return -EUCLEAN; 427 } 428 if (unlikely(key->offset != 0)) { 429 if (is_inode_item) 430 inode_item_err(leaf, slot, 431 "invalid key offset: has %llu expect 0", 432 key->offset); 433 else 434 dir_item_err(leaf, slot, 435 "invalid location key offset:has %llu expect 0", 436 key->offset); 437 return -EUCLEAN; 438 } 439 return 0; 440 } 441 442 static int check_root_key(struct extent_buffer *leaf, struct btrfs_key *key, 443 int slot) 444 { 445 struct btrfs_key item_key; 446 bool is_root_item; 447 448 btrfs_item_key_to_cpu(leaf, &item_key, slot); 449 is_root_item = (item_key.type == BTRFS_ROOT_ITEM_KEY); 450 451 /* 452 * Bad rootid for reloc trees. 453 * 454 * Reloc trees are only for subvolume trees, other trees only need 455 * to be COWed to be relocated. 456 */ 457 if (unlikely(is_root_item && key->objectid == BTRFS_TREE_RELOC_OBJECTID && 458 !is_fstree(key->offset))) { 459 generic_err(leaf, slot, 460 "invalid reloc tree for root %lld, root id is not a subvolume tree", 461 key->offset); 462 return -EUCLEAN; 463 } 464 465 /* No such tree id */ 466 if (unlikely(key->objectid == 0)) { 467 if (is_root_item) 468 generic_err(leaf, slot, "invalid root id 0"); 469 else 470 dir_item_err(leaf, slot, 471 "invalid location key root id 0"); 472 return -EUCLEAN; 473 } 474 475 /* DIR_ITEM/INDEX/INODE_REF is not allowed to point to non-fs trees */ 476 if (unlikely(!is_fstree(key->objectid) && !is_root_item)) { 477 dir_item_err(leaf, slot, 478 "invalid location key objectid, have %llu expect [%llu, %llu]", 479 key->objectid, BTRFS_FIRST_FREE_OBJECTID, 480 BTRFS_LAST_FREE_OBJECTID); 481 return -EUCLEAN; 482 } 483 484 /* 485 * ROOT_ITEM with non-zero offset means this is a snapshot, created at 486 * @offset transid. 487 * Furthermore, for location key in DIR_ITEM, its offset is always -1. 488 * 489 * So here we only check offset for reloc tree whose key->offset must 490 * be a valid tree. 491 */ 492 if (unlikely(key->objectid == BTRFS_TREE_RELOC_OBJECTID && 493 key->offset == 0)) { 494 generic_err(leaf, slot, "invalid root id 0 for reloc tree"); 495 return -EUCLEAN; 496 } 497 return 0; 498 } 499 500 static int check_dir_item(struct extent_buffer *leaf, 501 struct btrfs_key *key, struct btrfs_key *prev_key, 502 int slot) 503 { 504 struct btrfs_fs_info *fs_info = leaf->fs_info; 505 struct btrfs_dir_item *di; 506 u32 item_size = btrfs_item_size(leaf, slot); 507 u32 cur = 0; 508 509 if (unlikely(!check_prev_ino(leaf, key, slot, prev_key))) 510 return -EUCLEAN; 511 512 di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item); 513 while (cur < item_size) { 514 struct btrfs_key location_key; 515 u32 name_len; 516 u32 data_len; 517 u32 max_name_len; 518 u32 total_size; 519 u32 name_hash; 520 u8 dir_type; 521 int ret; 522 523 /* header itself should not cross item boundary */ 524 if (unlikely(cur + sizeof(*di) > item_size)) { 525 dir_item_err(leaf, slot, 526 "dir item header crosses item boundary, have %zu boundary %u", 527 cur + sizeof(*di), item_size); 528 return -EUCLEAN; 529 } 530 531 /* Location key check */ 532 btrfs_dir_item_key_to_cpu(leaf, di, &location_key); 533 if (location_key.type == BTRFS_ROOT_ITEM_KEY) { 534 ret = check_root_key(leaf, &location_key, slot); 535 if (unlikely(ret < 0)) 536 return ret; 537 } else if (location_key.type == BTRFS_INODE_ITEM_KEY || 538 location_key.type == 0) { 539 ret = check_inode_key(leaf, &location_key, slot); 540 if (unlikely(ret < 0)) 541 return ret; 542 } else { 543 dir_item_err(leaf, slot, 544 "invalid location key type, have %u, expect %u or %u", 545 location_key.type, BTRFS_ROOT_ITEM_KEY, 546 BTRFS_INODE_ITEM_KEY); 547 return -EUCLEAN; 548 } 549 550 /* dir type check */ 551 dir_type = btrfs_dir_ftype(leaf, di); 552 if (unlikely(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 int check_extent_item(struct extent_buffer *leaf, 1270 struct btrfs_key *key, int slot, 1271 struct btrfs_key *prev_key) 1272 { 1273 struct btrfs_fs_info *fs_info = leaf->fs_info; 1274 struct btrfs_extent_item *ei; 1275 bool is_tree_block = false; 1276 unsigned long ptr; /* Current pointer inside inline refs */ 1277 unsigned long end; /* Extent item end */ 1278 const u32 item_size = btrfs_item_size(leaf, slot); 1279 u64 flags; 1280 u64 generation; 1281 u64 total_refs; /* Total refs in btrfs_extent_item */ 1282 u64 inline_refs = 0; /* found total inline refs */ 1283 1284 if (unlikely(key->type == BTRFS_METADATA_ITEM_KEY && 1285 !btrfs_fs_incompat(fs_info, SKINNY_METADATA))) { 1286 generic_err(leaf, slot, 1287 "invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled"); 1288 return -EUCLEAN; 1289 } 1290 /* key->objectid is the bytenr for both key types */ 1291 if (unlikely(!IS_ALIGNED(key->objectid, fs_info->sectorsize))) { 1292 generic_err(leaf, slot, 1293 "invalid key objectid, have %llu expect to be aligned to %u", 1294 key->objectid, fs_info->sectorsize); 1295 return -EUCLEAN; 1296 } 1297 1298 /* key->offset is tree level for METADATA_ITEM_KEY */ 1299 if (unlikely(key->type == BTRFS_METADATA_ITEM_KEY && 1300 key->offset >= BTRFS_MAX_LEVEL)) { 1301 extent_err(leaf, slot, 1302 "invalid tree level, have %llu expect [0, %u]", 1303 key->offset, BTRFS_MAX_LEVEL - 1); 1304 return -EUCLEAN; 1305 } 1306 1307 /* 1308 * EXTENT/METADATA_ITEM consists of: 1309 * 1) One btrfs_extent_item 1310 * Records the total refs, type and generation of the extent. 1311 * 1312 * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only) 1313 * Records the first key and level of the tree block. 1314 * 1315 * 2) Zero or more btrfs_extent_inline_ref(s) 1316 * Each inline ref has one btrfs_extent_inline_ref shows: 1317 * 2.1) The ref type, one of the 4 1318 * TREE_BLOCK_REF Tree block only 1319 * SHARED_BLOCK_REF Tree block only 1320 * EXTENT_DATA_REF Data only 1321 * SHARED_DATA_REF Data only 1322 * 2.2) Ref type specific data 1323 * Either using btrfs_extent_inline_ref::offset, or specific 1324 * data structure. 1325 */ 1326 if (unlikely(item_size < sizeof(*ei))) { 1327 extent_err(leaf, slot, 1328 "invalid item size, have %u expect [%zu, %u)", 1329 item_size, sizeof(*ei), 1330 BTRFS_LEAF_DATA_SIZE(fs_info)); 1331 return -EUCLEAN; 1332 } 1333 end = item_size + btrfs_item_ptr_offset(leaf, slot); 1334 1335 /* Checks against extent_item */ 1336 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); 1337 flags = btrfs_extent_flags(leaf, ei); 1338 total_refs = btrfs_extent_refs(leaf, ei); 1339 generation = btrfs_extent_generation(leaf, ei); 1340 if (unlikely(generation > 1341 btrfs_super_generation(fs_info->super_copy) + 1)) { 1342 extent_err(leaf, slot, 1343 "invalid generation, have %llu expect (0, %llu]", 1344 generation, 1345 btrfs_super_generation(fs_info->super_copy) + 1); 1346 return -EUCLEAN; 1347 } 1348 if (unlikely(!has_single_bit_set(flags & (BTRFS_EXTENT_FLAG_DATA | 1349 BTRFS_EXTENT_FLAG_TREE_BLOCK)))) { 1350 extent_err(leaf, slot, 1351 "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx", 1352 flags, BTRFS_EXTENT_FLAG_DATA | 1353 BTRFS_EXTENT_FLAG_TREE_BLOCK); 1354 return -EUCLEAN; 1355 } 1356 is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK); 1357 if (is_tree_block) { 1358 if (unlikely(key->type == BTRFS_EXTENT_ITEM_KEY && 1359 key->offset != fs_info->nodesize)) { 1360 extent_err(leaf, slot, 1361 "invalid extent length, have %llu expect %u", 1362 key->offset, fs_info->nodesize); 1363 return -EUCLEAN; 1364 } 1365 } else { 1366 if (unlikely(key->type != BTRFS_EXTENT_ITEM_KEY)) { 1367 extent_err(leaf, slot, 1368 "invalid key type, have %u expect %u for data backref", 1369 key->type, BTRFS_EXTENT_ITEM_KEY); 1370 return -EUCLEAN; 1371 } 1372 if (unlikely(!IS_ALIGNED(key->offset, fs_info->sectorsize))) { 1373 extent_err(leaf, slot, 1374 "invalid extent length, have %llu expect aligned to %u", 1375 key->offset, fs_info->sectorsize); 1376 return -EUCLEAN; 1377 } 1378 if (unlikely(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 1379 extent_err(leaf, slot, 1380 "invalid extent flag, data has full backref set"); 1381 return -EUCLEAN; 1382 } 1383 } 1384 ptr = (unsigned long)(struct btrfs_extent_item *)(ei + 1); 1385 1386 /* Check the special case of btrfs_tree_block_info */ 1387 if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) { 1388 struct btrfs_tree_block_info *info; 1389 1390 info = (struct btrfs_tree_block_info *)ptr; 1391 if (unlikely(btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL)) { 1392 extent_err(leaf, slot, 1393 "invalid tree block info level, have %u expect [0, %u]", 1394 btrfs_tree_block_level(leaf, info), 1395 BTRFS_MAX_LEVEL - 1); 1396 return -EUCLEAN; 1397 } 1398 ptr = (unsigned long)(struct btrfs_tree_block_info *)(info + 1); 1399 } 1400 1401 /* Check inline refs */ 1402 while (ptr < end) { 1403 struct btrfs_extent_inline_ref *iref; 1404 struct btrfs_extent_data_ref *dref; 1405 struct btrfs_shared_data_ref *sref; 1406 u64 dref_offset; 1407 u64 inline_offset; 1408 u8 inline_type; 1409 1410 if (unlikely(ptr + sizeof(*iref) > end)) { 1411 extent_err(leaf, slot, 1412 "inline ref item overflows extent item, ptr %lu iref size %zu end %lu", 1413 ptr, sizeof(*iref), end); 1414 return -EUCLEAN; 1415 } 1416 iref = (struct btrfs_extent_inline_ref *)ptr; 1417 inline_type = btrfs_extent_inline_ref_type(leaf, iref); 1418 inline_offset = btrfs_extent_inline_ref_offset(leaf, iref); 1419 if (unlikely(ptr + btrfs_extent_inline_ref_size(inline_type) > end)) { 1420 extent_err(leaf, slot, 1421 "inline ref item overflows extent item, ptr %lu iref size %u end %lu", 1422 ptr, inline_type, end); 1423 return -EUCLEAN; 1424 } 1425 1426 switch (inline_type) { 1427 /* inline_offset is subvolid of the owner, no need to check */ 1428 case BTRFS_TREE_BLOCK_REF_KEY: 1429 inline_refs++; 1430 break; 1431 /* Contains parent bytenr */ 1432 case BTRFS_SHARED_BLOCK_REF_KEY: 1433 if (unlikely(!IS_ALIGNED(inline_offset, 1434 fs_info->sectorsize))) { 1435 extent_err(leaf, slot, 1436 "invalid tree parent bytenr, have %llu expect aligned to %u", 1437 inline_offset, fs_info->sectorsize); 1438 return -EUCLEAN; 1439 } 1440 inline_refs++; 1441 break; 1442 /* 1443 * Contains owner subvolid, owner key objectid, adjusted offset. 1444 * The only obvious corruption can happen in that offset. 1445 */ 1446 case BTRFS_EXTENT_DATA_REF_KEY: 1447 dref = (struct btrfs_extent_data_ref *)(&iref->offset); 1448 dref_offset = btrfs_extent_data_ref_offset(leaf, dref); 1449 if (unlikely(!IS_ALIGNED(dref_offset, 1450 fs_info->sectorsize))) { 1451 extent_err(leaf, slot, 1452 "invalid data ref offset, have %llu expect aligned to %u", 1453 dref_offset, fs_info->sectorsize); 1454 return -EUCLEAN; 1455 } 1456 inline_refs += btrfs_extent_data_ref_count(leaf, dref); 1457 break; 1458 /* Contains parent bytenr and ref count */ 1459 case BTRFS_SHARED_DATA_REF_KEY: 1460 sref = (struct btrfs_shared_data_ref *)(iref + 1); 1461 if (unlikely(!IS_ALIGNED(inline_offset, 1462 fs_info->sectorsize))) { 1463 extent_err(leaf, slot, 1464 "invalid data parent bytenr, have %llu expect aligned to %u", 1465 inline_offset, fs_info->sectorsize); 1466 return -EUCLEAN; 1467 } 1468 inline_refs += btrfs_shared_data_ref_count(leaf, sref); 1469 break; 1470 case BTRFS_EXTENT_OWNER_REF_KEY: 1471 WARN_ON(!btrfs_fs_incompat(fs_info, SIMPLE_QUOTA)); 1472 break; 1473 default: 1474 extent_err(leaf, slot, "unknown inline ref type: %u", 1475 inline_type); 1476 return -EUCLEAN; 1477 } 1478 ptr += btrfs_extent_inline_ref_size(inline_type); 1479 } 1480 /* No padding is allowed */ 1481 if (unlikely(ptr != end)) { 1482 extent_err(leaf, slot, 1483 "invalid extent item size, padding bytes found"); 1484 return -EUCLEAN; 1485 } 1486 1487 /* Finally, check the inline refs against total refs */ 1488 if (unlikely(inline_refs > total_refs)) { 1489 extent_err(leaf, slot, 1490 "invalid extent refs, have %llu expect >= inline %llu", 1491 total_refs, inline_refs); 1492 return -EUCLEAN; 1493 } 1494 1495 if ((prev_key->type == BTRFS_EXTENT_ITEM_KEY) || 1496 (prev_key->type == BTRFS_METADATA_ITEM_KEY)) { 1497 u64 prev_end = prev_key->objectid; 1498 1499 if (prev_key->type == BTRFS_METADATA_ITEM_KEY) 1500 prev_end += fs_info->nodesize; 1501 else 1502 prev_end += prev_key->offset; 1503 1504 if (unlikely(prev_end > key->objectid)) { 1505 extent_err(leaf, slot, 1506 "previous extent [%llu %u %llu] overlaps current extent [%llu %u %llu]", 1507 prev_key->objectid, prev_key->type, 1508 prev_key->offset, key->objectid, key->type, 1509 key->offset); 1510 return -EUCLEAN; 1511 } 1512 } 1513 1514 return 0; 1515 } 1516 1517 static int check_simple_keyed_refs(struct extent_buffer *leaf, 1518 struct btrfs_key *key, int slot) 1519 { 1520 u32 expect_item_size = 0; 1521 1522 if (key->type == BTRFS_SHARED_DATA_REF_KEY) 1523 expect_item_size = sizeof(struct btrfs_shared_data_ref); 1524 1525 if (unlikely(btrfs_item_size(leaf, slot) != expect_item_size)) { 1526 generic_err(leaf, slot, 1527 "invalid item size, have %u expect %u for key type %u", 1528 btrfs_item_size(leaf, slot), 1529 expect_item_size, key->type); 1530 return -EUCLEAN; 1531 } 1532 if (unlikely(!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize))) { 1533 generic_err(leaf, slot, 1534 "invalid key objectid for shared block ref, have %llu expect aligned to %u", 1535 key->objectid, leaf->fs_info->sectorsize); 1536 return -EUCLEAN; 1537 } 1538 if (unlikely(key->type != BTRFS_TREE_BLOCK_REF_KEY && 1539 !IS_ALIGNED(key->offset, leaf->fs_info->sectorsize))) { 1540 extent_err(leaf, slot, 1541 "invalid tree parent bytenr, have %llu expect aligned to %u", 1542 key->offset, leaf->fs_info->sectorsize); 1543 return -EUCLEAN; 1544 } 1545 return 0; 1546 } 1547 1548 static int check_extent_data_ref(struct extent_buffer *leaf, 1549 struct btrfs_key *key, int slot) 1550 { 1551 struct btrfs_extent_data_ref *dref; 1552 unsigned long ptr = btrfs_item_ptr_offset(leaf, slot); 1553 const unsigned long end = ptr + btrfs_item_size(leaf, slot); 1554 1555 if (unlikely(btrfs_item_size(leaf, slot) % sizeof(*dref) != 0)) { 1556 generic_err(leaf, slot, 1557 "invalid item size, have %u expect aligned to %zu for key type %u", 1558 btrfs_item_size(leaf, slot), 1559 sizeof(*dref), key->type); 1560 return -EUCLEAN; 1561 } 1562 if (unlikely(!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize))) { 1563 generic_err(leaf, slot, 1564 "invalid key objectid for shared block ref, have %llu expect aligned to %u", 1565 key->objectid, leaf->fs_info->sectorsize); 1566 return -EUCLEAN; 1567 } 1568 for (; ptr < end; ptr += sizeof(*dref)) { 1569 u64 offset; 1570 1571 /* 1572 * We cannot check the extent_data_ref hash due to possible 1573 * overflow from the leaf due to hash collisions. 1574 */ 1575 dref = (struct btrfs_extent_data_ref *)ptr; 1576 offset = btrfs_extent_data_ref_offset(leaf, dref); 1577 if (unlikely(!IS_ALIGNED(offset, leaf->fs_info->sectorsize))) { 1578 extent_err(leaf, slot, 1579 "invalid extent data backref offset, have %llu expect aligned to %u", 1580 offset, leaf->fs_info->sectorsize); 1581 return -EUCLEAN; 1582 } 1583 } 1584 return 0; 1585 } 1586 1587 #define inode_ref_err(eb, slot, fmt, args...) \ 1588 inode_item_err(eb, slot, fmt, ##args) 1589 static int check_inode_ref(struct extent_buffer *leaf, 1590 struct btrfs_key *key, struct btrfs_key *prev_key, 1591 int slot) 1592 { 1593 struct btrfs_inode_ref *iref; 1594 unsigned long ptr; 1595 unsigned long end; 1596 1597 if (unlikely(!check_prev_ino(leaf, key, slot, prev_key))) 1598 return -EUCLEAN; 1599 /* namelen can't be 0, so item_size == sizeof() is also invalid */ 1600 if (unlikely(btrfs_item_size(leaf, slot) <= sizeof(*iref))) { 1601 inode_ref_err(leaf, slot, 1602 "invalid item size, have %u expect (%zu, %u)", 1603 btrfs_item_size(leaf, slot), 1604 sizeof(*iref), BTRFS_LEAF_DATA_SIZE(leaf->fs_info)); 1605 return -EUCLEAN; 1606 } 1607 1608 ptr = btrfs_item_ptr_offset(leaf, slot); 1609 end = ptr + btrfs_item_size(leaf, slot); 1610 while (ptr < end) { 1611 u16 namelen; 1612 1613 if (unlikely(ptr + sizeof(iref) > end)) { 1614 inode_ref_err(leaf, slot, 1615 "inode ref overflow, ptr %lu end %lu inode_ref_size %zu", 1616 ptr, end, sizeof(iref)); 1617 return -EUCLEAN; 1618 } 1619 1620 iref = (struct btrfs_inode_ref *)ptr; 1621 namelen = btrfs_inode_ref_name_len(leaf, iref); 1622 if (unlikely(ptr + sizeof(*iref) + namelen > end)) { 1623 inode_ref_err(leaf, slot, 1624 "inode ref overflow, ptr %lu end %lu namelen %u", 1625 ptr, end, namelen); 1626 return -EUCLEAN; 1627 } 1628 1629 /* 1630 * NOTE: In theory we should record all found index numbers 1631 * to find any duplicated indexes, but that will be too time 1632 * consuming for inodes with too many hard links. 1633 */ 1634 ptr += sizeof(*iref) + namelen; 1635 } 1636 return 0; 1637 } 1638 1639 static int check_raid_stripe_extent(const struct extent_buffer *leaf, 1640 const struct btrfs_key *key, int slot) 1641 { 1642 struct btrfs_stripe_extent *stripe_extent = 1643 btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent); 1644 1645 if (unlikely(!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize))) { 1646 generic_err(leaf, slot, 1647 "invalid key objectid for raid stripe extent, have %llu expect aligned to %u", 1648 key->objectid, leaf->fs_info->sectorsize); 1649 return -EUCLEAN; 1650 } 1651 1652 if (unlikely(!btrfs_fs_incompat(leaf->fs_info, RAID_STRIPE_TREE))) { 1653 generic_err(leaf, slot, 1654 "RAID_STRIPE_EXTENT present but RAID_STRIPE_TREE incompat bit unset"); 1655 return -EUCLEAN; 1656 } 1657 1658 switch (btrfs_stripe_extent_encoding(leaf, stripe_extent)) { 1659 case BTRFS_STRIPE_RAID0: 1660 case BTRFS_STRIPE_RAID1: 1661 case BTRFS_STRIPE_DUP: 1662 case BTRFS_STRIPE_RAID10: 1663 case BTRFS_STRIPE_RAID5: 1664 case BTRFS_STRIPE_RAID6: 1665 case BTRFS_STRIPE_RAID1C3: 1666 case BTRFS_STRIPE_RAID1C4: 1667 break; 1668 default: 1669 generic_err(leaf, slot, "invalid raid stripe encoding %u", 1670 btrfs_stripe_extent_encoding(leaf, stripe_extent)); 1671 return -EUCLEAN; 1672 } 1673 1674 return 0; 1675 } 1676 1677 /* 1678 * Common point to switch the item-specific validation. 1679 */ 1680 static enum btrfs_tree_block_status check_leaf_item(struct extent_buffer *leaf, 1681 struct btrfs_key *key, 1682 int slot, 1683 struct btrfs_key *prev_key) 1684 { 1685 int ret = 0; 1686 struct btrfs_chunk *chunk; 1687 1688 switch (key->type) { 1689 case BTRFS_EXTENT_DATA_KEY: 1690 ret = check_extent_data_item(leaf, key, slot, prev_key); 1691 break; 1692 case BTRFS_EXTENT_CSUM_KEY: 1693 ret = check_csum_item(leaf, key, slot, prev_key); 1694 break; 1695 case BTRFS_DIR_ITEM_KEY: 1696 case BTRFS_DIR_INDEX_KEY: 1697 case BTRFS_XATTR_ITEM_KEY: 1698 ret = check_dir_item(leaf, key, prev_key, slot); 1699 break; 1700 case BTRFS_INODE_REF_KEY: 1701 ret = check_inode_ref(leaf, key, prev_key, slot); 1702 break; 1703 case BTRFS_BLOCK_GROUP_ITEM_KEY: 1704 ret = check_block_group_item(leaf, key, slot); 1705 break; 1706 case BTRFS_CHUNK_ITEM_KEY: 1707 chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk); 1708 ret = check_leaf_chunk_item(leaf, chunk, key, slot); 1709 break; 1710 case BTRFS_DEV_ITEM_KEY: 1711 ret = check_dev_item(leaf, key, slot); 1712 break; 1713 case BTRFS_INODE_ITEM_KEY: 1714 ret = check_inode_item(leaf, key, slot); 1715 break; 1716 case BTRFS_ROOT_ITEM_KEY: 1717 ret = check_root_item(leaf, key, slot); 1718 break; 1719 case BTRFS_EXTENT_ITEM_KEY: 1720 case BTRFS_METADATA_ITEM_KEY: 1721 ret = check_extent_item(leaf, key, slot, prev_key); 1722 break; 1723 case BTRFS_TREE_BLOCK_REF_KEY: 1724 case BTRFS_SHARED_DATA_REF_KEY: 1725 case BTRFS_SHARED_BLOCK_REF_KEY: 1726 ret = check_simple_keyed_refs(leaf, key, slot); 1727 break; 1728 case BTRFS_EXTENT_DATA_REF_KEY: 1729 ret = check_extent_data_ref(leaf, key, slot); 1730 break; 1731 case BTRFS_RAID_STRIPE_KEY: 1732 ret = check_raid_stripe_extent(leaf, key, slot); 1733 break; 1734 } 1735 1736 if (ret) 1737 return BTRFS_TREE_BLOCK_INVALID_ITEM; 1738 return BTRFS_TREE_BLOCK_CLEAN; 1739 } 1740 1741 enum btrfs_tree_block_status __btrfs_check_leaf(struct extent_buffer *leaf) 1742 { 1743 struct btrfs_fs_info *fs_info = leaf->fs_info; 1744 /* No valid key type is 0, so all key should be larger than this key */ 1745 struct btrfs_key prev_key = {0, 0, 0}; 1746 struct btrfs_key key; 1747 u32 nritems = btrfs_header_nritems(leaf); 1748 int slot; 1749 1750 if (unlikely(btrfs_header_level(leaf) != 0)) { 1751 generic_err(leaf, 0, 1752 "invalid level for leaf, have %d expect 0", 1753 btrfs_header_level(leaf)); 1754 return BTRFS_TREE_BLOCK_INVALID_LEVEL; 1755 } 1756 1757 /* 1758 * Extent buffers from a relocation tree have a owner field that 1759 * corresponds to the subvolume tree they are based on. So just from an 1760 * extent buffer alone we can not find out what is the id of the 1761 * corresponding subvolume tree, so we can not figure out if the extent 1762 * buffer corresponds to the root of the relocation tree or not. So 1763 * skip this check for relocation trees. 1764 */ 1765 if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) { 1766 u64 owner = btrfs_header_owner(leaf); 1767 1768 /* These trees must never be empty */ 1769 if (unlikely(owner == BTRFS_ROOT_TREE_OBJECTID || 1770 owner == BTRFS_CHUNK_TREE_OBJECTID || 1771 owner == BTRFS_DEV_TREE_OBJECTID || 1772 owner == BTRFS_FS_TREE_OBJECTID || 1773 owner == BTRFS_DATA_RELOC_TREE_OBJECTID)) { 1774 generic_err(leaf, 0, 1775 "invalid root, root %llu must never be empty", 1776 owner); 1777 return BTRFS_TREE_BLOCK_INVALID_NRITEMS; 1778 } 1779 1780 /* Unknown tree */ 1781 if (unlikely(owner == 0)) { 1782 generic_err(leaf, 0, 1783 "invalid owner, root 0 is not defined"); 1784 return BTRFS_TREE_BLOCK_INVALID_OWNER; 1785 } 1786 1787 /* EXTENT_TREE_V2 can have empty extent trees. */ 1788 if (btrfs_fs_incompat(fs_info, EXTENT_TREE_V2)) 1789 return BTRFS_TREE_BLOCK_CLEAN; 1790 1791 if (unlikely(owner == BTRFS_EXTENT_TREE_OBJECTID)) { 1792 generic_err(leaf, 0, 1793 "invalid root, root %llu must never be empty", 1794 owner); 1795 return BTRFS_TREE_BLOCK_INVALID_NRITEMS; 1796 } 1797 1798 return BTRFS_TREE_BLOCK_CLEAN; 1799 } 1800 1801 if (unlikely(nritems == 0)) 1802 return BTRFS_TREE_BLOCK_CLEAN; 1803 1804 /* 1805 * Check the following things to make sure this is a good leaf, and 1806 * leaf users won't need to bother with similar sanity checks: 1807 * 1808 * 1) key ordering 1809 * 2) item offset and size 1810 * No overlap, no hole, all inside the leaf. 1811 * 3) item content 1812 * If possible, do comprehensive sanity check. 1813 * NOTE: All checks must only rely on the item data itself. 1814 */ 1815 for (slot = 0; slot < nritems; slot++) { 1816 u32 item_end_expected; 1817 u64 item_data_end; 1818 1819 btrfs_item_key_to_cpu(leaf, &key, slot); 1820 1821 /* Make sure the keys are in the right order */ 1822 if (unlikely(btrfs_comp_cpu_keys(&prev_key, &key) >= 0)) { 1823 generic_err(leaf, slot, 1824 "bad key order, prev (%llu %u %llu) current (%llu %u %llu)", 1825 prev_key.objectid, prev_key.type, 1826 prev_key.offset, key.objectid, key.type, 1827 key.offset); 1828 return BTRFS_TREE_BLOCK_BAD_KEY_ORDER; 1829 } 1830 1831 item_data_end = (u64)btrfs_item_offset(leaf, slot) + 1832 btrfs_item_size(leaf, slot); 1833 /* 1834 * Make sure the offset and ends are right, remember that the 1835 * item data starts at the end of the leaf and grows towards the 1836 * front. 1837 */ 1838 if (slot == 0) 1839 item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info); 1840 else 1841 item_end_expected = btrfs_item_offset(leaf, 1842 slot - 1); 1843 if (unlikely(item_data_end != item_end_expected)) { 1844 generic_err(leaf, slot, 1845 "unexpected item end, have %llu expect %u", 1846 item_data_end, item_end_expected); 1847 return BTRFS_TREE_BLOCK_INVALID_OFFSETS; 1848 } 1849 1850 /* 1851 * Check to make sure that we don't point outside of the leaf, 1852 * just in case all the items are consistent to each other, but 1853 * all point outside of the leaf. 1854 */ 1855 if (unlikely(item_data_end > BTRFS_LEAF_DATA_SIZE(fs_info))) { 1856 generic_err(leaf, slot, 1857 "slot end outside of leaf, have %llu expect range [0, %u]", 1858 item_data_end, BTRFS_LEAF_DATA_SIZE(fs_info)); 1859 return BTRFS_TREE_BLOCK_INVALID_OFFSETS; 1860 } 1861 1862 /* Also check if the item pointer overlaps with btrfs item. */ 1863 if (unlikely(btrfs_item_ptr_offset(leaf, slot) < 1864 btrfs_item_nr_offset(leaf, slot) + sizeof(struct btrfs_item))) { 1865 generic_err(leaf, slot, 1866 "slot overlaps with its data, item end %lu data start %lu", 1867 btrfs_item_nr_offset(leaf, slot) + 1868 sizeof(struct btrfs_item), 1869 btrfs_item_ptr_offset(leaf, slot)); 1870 return BTRFS_TREE_BLOCK_INVALID_OFFSETS; 1871 } 1872 1873 /* 1874 * We only want to do this if WRITTEN is set, otherwise the leaf 1875 * may be in some intermediate state and won't appear valid. 1876 */ 1877 if (btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_WRITTEN)) { 1878 enum btrfs_tree_block_status ret; 1879 1880 /* 1881 * Check if the item size and content meet other 1882 * criteria 1883 */ 1884 ret = check_leaf_item(leaf, &key, slot, &prev_key); 1885 if (unlikely(ret != BTRFS_TREE_BLOCK_CLEAN)) 1886 return ret; 1887 } 1888 1889 prev_key.objectid = key.objectid; 1890 prev_key.type = key.type; 1891 prev_key.offset = key.offset; 1892 } 1893 1894 return BTRFS_TREE_BLOCK_CLEAN; 1895 } 1896 1897 int btrfs_check_leaf(struct extent_buffer *leaf) 1898 { 1899 enum btrfs_tree_block_status ret; 1900 1901 ret = __btrfs_check_leaf(leaf); 1902 if (unlikely(ret != BTRFS_TREE_BLOCK_CLEAN)) 1903 return -EUCLEAN; 1904 return 0; 1905 } 1906 ALLOW_ERROR_INJECTION(btrfs_check_leaf, ERRNO); 1907 1908 enum btrfs_tree_block_status __btrfs_check_node(struct extent_buffer *node) 1909 { 1910 struct btrfs_fs_info *fs_info = node->fs_info; 1911 unsigned long nr = btrfs_header_nritems(node); 1912 struct btrfs_key key, next_key; 1913 int slot; 1914 int level = btrfs_header_level(node); 1915 u64 bytenr; 1916 1917 if (unlikely(level <= 0 || level >= BTRFS_MAX_LEVEL)) { 1918 generic_err(node, 0, 1919 "invalid level for node, have %d expect [1, %d]", 1920 level, BTRFS_MAX_LEVEL - 1); 1921 return BTRFS_TREE_BLOCK_INVALID_LEVEL; 1922 } 1923 if (unlikely(nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(fs_info))) { 1924 btrfs_crit(fs_info, 1925 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]", 1926 btrfs_header_owner(node), node->start, 1927 nr == 0 ? "small" : "large", nr, 1928 BTRFS_NODEPTRS_PER_BLOCK(fs_info)); 1929 return BTRFS_TREE_BLOCK_INVALID_NRITEMS; 1930 } 1931 1932 for (slot = 0; slot < nr - 1; slot++) { 1933 bytenr = btrfs_node_blockptr(node, slot); 1934 btrfs_node_key_to_cpu(node, &key, slot); 1935 btrfs_node_key_to_cpu(node, &next_key, slot + 1); 1936 1937 if (unlikely(!bytenr)) { 1938 generic_err(node, slot, 1939 "invalid NULL node pointer"); 1940 return BTRFS_TREE_BLOCK_INVALID_BLOCKPTR; 1941 } 1942 if (unlikely(!IS_ALIGNED(bytenr, fs_info->sectorsize))) { 1943 generic_err(node, slot, 1944 "unaligned pointer, have %llu should be aligned to %u", 1945 bytenr, fs_info->sectorsize); 1946 return BTRFS_TREE_BLOCK_INVALID_BLOCKPTR; 1947 } 1948 1949 if (unlikely(btrfs_comp_cpu_keys(&key, &next_key) >= 0)) { 1950 generic_err(node, slot, 1951 "bad key order, current (%llu %u %llu) next (%llu %u %llu)", 1952 key.objectid, key.type, key.offset, 1953 next_key.objectid, next_key.type, 1954 next_key.offset); 1955 return BTRFS_TREE_BLOCK_BAD_KEY_ORDER; 1956 } 1957 } 1958 return BTRFS_TREE_BLOCK_CLEAN; 1959 } 1960 1961 int btrfs_check_node(struct extent_buffer *node) 1962 { 1963 enum btrfs_tree_block_status ret; 1964 1965 ret = __btrfs_check_node(node); 1966 if (unlikely(ret != BTRFS_TREE_BLOCK_CLEAN)) 1967 return -EUCLEAN; 1968 return 0; 1969 } 1970 ALLOW_ERROR_INJECTION(btrfs_check_node, ERRNO); 1971 1972 int btrfs_check_eb_owner(const struct extent_buffer *eb, u64 root_owner) 1973 { 1974 const bool is_subvol = is_fstree(root_owner); 1975 const u64 eb_owner = btrfs_header_owner(eb); 1976 1977 /* 1978 * Skip dummy fs, as selftests don't create unique ebs for each dummy 1979 * root. 1980 */ 1981 if (test_bit(BTRFS_FS_STATE_DUMMY_FS_INFO, &eb->fs_info->fs_state)) 1982 return 0; 1983 /* 1984 * There are several call sites (backref walking, qgroup, and data 1985 * reloc) passing 0 as @root_owner, as they are not holding the 1986 * tree root. In that case, we can not do a reliable ownership check, 1987 * so just exit. 1988 */ 1989 if (root_owner == 0) 1990 return 0; 1991 /* 1992 * These trees use key.offset as their owner, our callers don't have 1993 * the extra capacity to pass key.offset here. So we just skip them. 1994 */ 1995 if (root_owner == BTRFS_TREE_LOG_OBJECTID || 1996 root_owner == BTRFS_TREE_RELOC_OBJECTID) 1997 return 0; 1998 1999 if (!is_subvol) { 2000 /* For non-subvolume trees, the eb owner should match root owner */ 2001 if (unlikely(root_owner != eb_owner)) { 2002 btrfs_crit(eb->fs_info, 2003 "corrupted %s, root=%llu block=%llu owner mismatch, have %llu expect %llu", 2004 btrfs_header_level(eb) == 0 ? "leaf" : "node", 2005 root_owner, btrfs_header_bytenr(eb), eb_owner, 2006 root_owner); 2007 return -EUCLEAN; 2008 } 2009 return 0; 2010 } 2011 2012 /* 2013 * For subvolume trees, owners can mismatch, but they should all belong 2014 * to subvolume trees. 2015 */ 2016 if (unlikely(is_subvol != is_fstree(eb_owner))) { 2017 btrfs_crit(eb->fs_info, 2018 "corrupted %s, root=%llu block=%llu owner mismatch, have %llu expect [%llu, %llu]", 2019 btrfs_header_level(eb) == 0 ? "leaf" : "node", 2020 root_owner, btrfs_header_bytenr(eb), eb_owner, 2021 BTRFS_FIRST_FREE_OBJECTID, BTRFS_LAST_FREE_OBJECTID); 2022 return -EUCLEAN; 2023 } 2024 return 0; 2025 } 2026 2027 int btrfs_verify_level_key(struct extent_buffer *eb, int level, 2028 struct btrfs_key *first_key, u64 parent_transid) 2029 { 2030 struct btrfs_fs_info *fs_info = eb->fs_info; 2031 int found_level; 2032 struct btrfs_key found_key; 2033 int ret; 2034 2035 found_level = btrfs_header_level(eb); 2036 if (found_level != level) { 2037 WARN(IS_ENABLED(CONFIG_BTRFS_DEBUG), 2038 KERN_ERR "BTRFS: tree level check failed\n"); 2039 btrfs_err(fs_info, 2040 "tree level mismatch detected, bytenr=%llu level expected=%u has=%u", 2041 eb->start, level, found_level); 2042 return -EIO; 2043 } 2044 2045 if (!first_key) 2046 return 0; 2047 2048 /* 2049 * For live tree block (new tree blocks in current transaction), 2050 * we need proper lock context to avoid race, which is impossible here. 2051 * So we only checks tree blocks which is read from disk, whose 2052 * generation <= fs_info->last_trans_committed. 2053 */ 2054 if (btrfs_header_generation(eb) > btrfs_get_last_trans_committed(fs_info)) 2055 return 0; 2056 2057 /* We have @first_key, so this @eb must have at least one item */ 2058 if (btrfs_header_nritems(eb) == 0) { 2059 btrfs_err(fs_info, 2060 "invalid tree nritems, bytenr=%llu nritems=0 expect >0", 2061 eb->start); 2062 WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG)); 2063 return -EUCLEAN; 2064 } 2065 2066 if (found_level) 2067 btrfs_node_key_to_cpu(eb, &found_key, 0); 2068 else 2069 btrfs_item_key_to_cpu(eb, &found_key, 0); 2070 ret = btrfs_comp_cpu_keys(first_key, &found_key); 2071 2072 if (ret) { 2073 WARN(IS_ENABLED(CONFIG_BTRFS_DEBUG), 2074 KERN_ERR "BTRFS: tree first key check failed\n"); 2075 btrfs_err(fs_info, 2076 "tree first key mismatch detected, bytenr=%llu parent_transid=%llu key expected=(%llu,%u,%llu) has=(%llu,%u,%llu)", 2077 eb->start, parent_transid, first_key->objectid, 2078 first_key->type, first_key->offset, 2079 found_key.objectid, found_key.type, 2080 found_key.offset); 2081 } 2082 return ret; 2083 } 2084