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