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