fs/btrfs/tree-checker.c

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