fs/btrfs/tree-checker.c

   1 /*
   2  * Copyright (C) Qu Wenruo 2017.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program.
  15  */
  16
  17 /*
  18  * The module is used to catch unexpected/corrupted tree block data.
  19  * Such behavior can be caused either by a fuzzed image or bugs.
  20  *
  21  * The objective is to do leaf/node validation checks when tree block is read
  22  * from disk, and check *every* possible member, so other code won't
  23  * need to checking them again.
  24  *
  25  * Due to the potential and unwanted damage, every checker needs to be
  26  * carefully reviewed otherwise so it does not prevent mount of valid images.
  27  */
  28
  29 #include "ctree.h"
  30 #include "tree-checker.h"
  31 #include "disk-io.h"
  32 #include "compression.h"
  33
  34 /*
  35  * Error message should follow the following format:
  36  * corrupt <type>: <identifier>, <reason>[, <bad_value>]
  37  *
  38  * @type:       leaf or node
  39  * @identifier: the necessary info to locate the leaf/node.
  40  *              It's recommened to decode key.objecitd/offset if it's
  41  *              meaningful.
  42  * @reason:     describe the error
  43  * @bad_value:  optional, it's recommened to output bad value and its
  44  *              expected value (range).
  45  *
  46  * Since comma is used to separate the components, only space is allowed
  47  * inside each component.
  48  */
  49
  50 /*
  51  * Append generic "corrupt leaf/node root=%llu block=%llu slot=%d: " to @fmt.
  52  * Allows callers to customize the output.
  53  */
  54 __printf(4, 5)
  55 static void generic_err(const struct btrfs_root *root,
  56                         const struct extent_buffer *eb, int slot,
  57                         const char *fmt, ...)
  58 {
  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(root->fs_info,
  68                 "corrupt %s: root=%llu block=%llu slot=%d, %pV",
  69                 btrfs_header_level(eb) == 0 ? "leaf" : "node",
  70                 root->objectid, 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(4, 5)
  79 static void file_extent_err(const struct btrfs_root *root,
  80                             const struct extent_buffer *eb, int slot,
  81                             const char *fmt, ...)
  82 {
  83         struct btrfs_key key;
  84         struct va_format vaf;
  85         va_list args;
  86
  87         btrfs_item_key_to_cpu(eb, &key, slot);
  88         va_start(args, fmt);
  89
  90         vaf.fmt = fmt;
  91         vaf.va = &args;
  92
  93         btrfs_crit(root->fs_info,
  94         "corrupt %s: root=%llu block=%llu slot=%d ino=%llu file_offset=%llu, %pV",
  95                 btrfs_header_level(eb) == 0 ? "leaf" : "node", root->objectid,
  96                 btrfs_header_bytenr(eb), slot, key.objectid, key.offset, &vaf);
  97         va_end(args);
  98 }
  99
 100 /*
 101  * Return 0 if the btrfs_file_extent_##name is aligned to @alignment
 102  * Else return 1
 103  */
 104 #define CHECK_FE_ALIGNED(root, leaf, slot, fi, name, alignment)               \
 105 ({                                                                            \
 106         if (!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment))) \
 107                 file_extent_err((root), (leaf), (slot),                       \
 108         "invalid %s for file extent, have %llu, should be aligned to %u",     \
 109                         (#name), btrfs_file_extent_##name((leaf), (fi)),      \
 110                         (alignment));                                         \
 111         (!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment)));   \
 112 })
 113
 114 static int check_extent_data_item(struct btrfs_root *root,
 115                                   struct extent_buffer *leaf,
 116                                   struct btrfs_key *key, int slot)
 117 {
 118         struct btrfs_file_extent_item *fi;
 119         u32 sectorsize = root->fs_info->sectorsize;
 120         u32 item_size = btrfs_item_size_nr(leaf, slot);
 121
 122         if (!IS_ALIGNED(key->offset, sectorsize)) {
 123                 file_extent_err(root, leaf, slot,
 124 "unaligned file_offset for file extent, have %llu should be aligned to %u",
 125                         key->offset, sectorsize);
 126                 return -EUCLEAN;
 127         }
 128
 129         fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
 130
 131         if (btrfs_file_extent_type(leaf, fi) > BTRFS_FILE_EXTENT_TYPES) {
 132                 file_extent_err(root, leaf, slot,
 133                 "invalid type for file extent, have %u expect range [0, %u]",
 134                         btrfs_file_extent_type(leaf, fi),
 135                         BTRFS_FILE_EXTENT_TYPES);
 136                 return -EUCLEAN;
 137         }
 138
 139         /*
 140          * Support for new compression/encrption must introduce incompat flag,
 141          * and must be caught in open_ctree().
 142          */
 143         if (btrfs_file_extent_compression(leaf, fi) > BTRFS_COMPRESS_TYPES) {
 144                 file_extent_err(root, leaf, slot,
 145         "invalid compression for file extent, have %u expect range [0, %u]",
 146                         btrfs_file_extent_compression(leaf, fi),
 147                         BTRFS_COMPRESS_TYPES);
 148                 return -EUCLEAN;
 149         }
 150         if (btrfs_file_extent_encryption(leaf, fi)) {
 151                 file_extent_err(root, leaf, slot,
 152                         "invalid encryption for file extent, have %u expect 0",
 153                         btrfs_file_extent_encryption(leaf, fi));
 154                 return -EUCLEAN;
 155         }
 156         if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
 157                 /* Inline extent must have 0 as key offset */
 158                 if (key->offset) {
 159                         file_extent_err(root, leaf, slot,
 160                 "invalid file_offset for inline file extent, have %llu expect 0",
 161                                 key->offset);
 162                         return -EUCLEAN;
 163                 }
 164
 165                 /* Compressed inline extent has no on-disk size, skip it */
 166                 if (btrfs_file_extent_compression(leaf, fi) !=
 167                     BTRFS_COMPRESS_NONE)
 168                         return 0;
 169
 170                 /* Uncompressed inline extent size must match item size */
 171                 if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
 172                     btrfs_file_extent_ram_bytes(leaf, fi)) {
 173                         file_extent_err(root, leaf, slot,
 174         "invalid ram_bytes for uncompressed inline extent, have %u expect %llu",
 175                                 item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START +
 176                                 btrfs_file_extent_ram_bytes(leaf, fi));
 177                         return -EUCLEAN;
 178                 }
 179                 return 0;
 180         }
 181
 182         /* Regular or preallocated extent has fixed item size */
 183         if (item_size != sizeof(*fi)) {
 184                 file_extent_err(root, leaf, slot,
 185         "invalid item size for reg/prealloc file extent, have %u expect %zu",
 186                         item_size, sizeof(*fi));
 187                 return -EUCLEAN;
 188         }
 189         if (CHECK_FE_ALIGNED(root, leaf, slot, fi, ram_bytes, sectorsize) ||
 190             CHECK_FE_ALIGNED(root, leaf, slot, fi, disk_bytenr, sectorsize) ||
 191             CHECK_FE_ALIGNED(root, leaf, slot, fi, disk_num_bytes, sectorsize) ||
 192             CHECK_FE_ALIGNED(root, leaf, slot, fi, offset, sectorsize) ||
 193             CHECK_FE_ALIGNED(root, leaf, slot, fi, num_bytes, sectorsize))
 194                 return -EUCLEAN;
 195         return 0;
 196 }
 197
 198 static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf,
 199                            struct btrfs_key *key, int slot)
 200 {
 201         u32 sectorsize = root->fs_info->sectorsize;
 202         u32 csumsize = btrfs_super_csum_size(root->fs_info->super_copy);
 203
 204         if (key->objectid != BTRFS_EXTENT_CSUM_OBJECTID) {
 205                 generic_err(root, leaf, slot,
 206                 "invalid key objectid for csum item, have %llu expect %llu",
 207                         key->objectid, BTRFS_EXTENT_CSUM_OBJECTID);
 208                 return -EUCLEAN;
 209         }
 210         if (!IS_ALIGNED(key->offset, sectorsize)) {
 211                 generic_err(root, leaf, slot,
 212         "unaligned key offset for csum item, have %llu should be aligned to %u",
 213                         key->offset, sectorsize);
 214                 return -EUCLEAN;
 215         }
 216         if (!IS_ALIGNED(btrfs_item_size_nr(leaf, slot), csumsize)) {
 217                 generic_err(root, leaf, slot,
 218         "unaligned item size for csum item, have %u should be aligned to %u",
 219                         btrfs_item_size_nr(leaf, slot), csumsize);
 220                 return -EUCLEAN;
 221         }
 222         return 0;
 223 }
 224
 225 /*
 226  * Common point to switch the item-specific validation.
 227  */
 228 static int check_leaf_item(struct btrfs_root *root,
 229                            struct extent_buffer *leaf,
 230                            struct btrfs_key *key, int slot)
 231 {
 232         int ret = 0;
 233
 234         switch (key->type) {
 235         case BTRFS_EXTENT_DATA_KEY:
 236                 ret = check_extent_data_item(root, leaf, key, slot);
 237                 break;
 238         case BTRFS_EXTENT_CSUM_KEY:
 239                 ret = check_csum_item(root, leaf, key, slot);
 240                 break;
 241         }
 242         return ret;
 243 }
 244
 245 static int check_leaf(struct btrfs_root *root, struct extent_buffer *leaf,
 246                       bool check_item_data)
 247 {
 248         struct btrfs_fs_info *fs_info = root->fs_info;
 249         /* No valid key type is 0, so all key should be larger than this key */
 250         struct btrfs_key prev_key = {0, 0, 0};
 251         struct btrfs_key key;
 252         u32 nritems = btrfs_header_nritems(leaf);
 253         int slot;
 254
 255         /*
 256          * Extent buffers from a relocation tree have a owner field that
 257          * corresponds to the subvolume tree they are based on. So just from an
 258          * extent buffer alone we can not find out what is the id of the
 259          * corresponding subvolume tree, so we can not figure out if the extent
 260          * buffer corresponds to the root of the relocation tree or not. So
 261          * skip this check for relocation trees.
 262          */
 263         if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
 264                 struct btrfs_root *check_root;
 265
 266                 key.objectid = btrfs_header_owner(leaf);
 267                 key.type = BTRFS_ROOT_ITEM_KEY;
 268                 key.offset = (u64)-1;
 269
 270                 check_root = btrfs_get_fs_root(fs_info, &key, false);
 271                 /*
 272                  * The only reason we also check NULL here is that during
 273                  * open_ctree() some roots has not yet been set up.
 274                  */
 275                 if (!IS_ERR_OR_NULL(check_root)) {
 276                         struct extent_buffer *eb;
 277
 278                         eb = btrfs_root_node(check_root);
 279                         /* if leaf is the root, then it's fine */
 280                         if (leaf != eb) {
 281                                 generic_err(check_root, leaf, 0,
 282                 "invalid nritems, have %u should not be 0 for non-root leaf",
 283                                         nritems);
 284                                 free_extent_buffer(eb);
 285                                 return -EUCLEAN;
 286                         }
 287                         free_extent_buffer(eb);
 288                 }
 289                 return 0;
 290         }
 291
 292         if (nritems == 0)
 293                 return 0;
 294
 295         /*
 296          * Check the following things to make sure this is a good leaf, and
 297          * leaf users won't need to bother with similar sanity checks:
 298          *
 299          * 1) key ordering
 300          * 2) item offset and size
 301          *    No overlap, no hole, all inside the leaf.
 302          * 3) item content
 303          *    If possible, do comprehensive sanity check.
 304          *    NOTE: All checks must only rely on the item data itself.
 305          */
 306         for (slot = 0; slot < nritems; slot++) {
 307                 u32 item_end_expected;
 308                 int ret;
 309
 310                 btrfs_item_key_to_cpu(leaf, &key, slot);
 311
 312                 /* Make sure the keys are in the right order */
 313                 if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
 314                         generic_err(root, leaf, slot,
 315         "bad key order, prev (%llu %u %llu) current (%llu %u %llu)",
 316                                 prev_key.objectid, prev_key.type,
 317                                 prev_key.offset, key.objectid, key.type,
 318                                 key.offset);
 319                         return -EUCLEAN;
 320                 }
 321
 322                 /*
 323                  * Make sure the offset and ends are right, remember that the
 324                  * item data starts at the end of the leaf and grows towards the
 325                  * front.
 326                  */
 327                 if (slot == 0)
 328                         item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
 329                 else
 330                         item_end_expected = btrfs_item_offset_nr(leaf,
 331                                                                  slot - 1);
 332                 if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
 333                         generic_err(root, leaf, slot,
 334                                 "unexpected item end, have %u expect %u",
 335                                 btrfs_item_end_nr(leaf, slot),
 336                                 item_end_expected);
 337                         return -EUCLEAN;
 338                 }
 339
 340                 /*
 341                  * Check to make sure that we don't point outside of the leaf,
 342                  * just in case all the items are consistent to each other, but
 343                  * all point outside of the leaf.
 344                  */
 345                 if (btrfs_item_end_nr(leaf, slot) >
 346                     BTRFS_LEAF_DATA_SIZE(fs_info)) {
 347                         generic_err(root, leaf, slot,
 348                         "slot end outside of leaf, have %u expect range [0, %u]",
 349                                 btrfs_item_end_nr(leaf, slot),
 350                                 BTRFS_LEAF_DATA_SIZE(fs_info));
 351                         return -EUCLEAN;
 352                 }
 353
 354                 /* Also check if the item pointer overlaps with btrfs item. */
 355                 if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
 356                     btrfs_item_ptr_offset(leaf, slot)) {
 357                         generic_err(root, leaf, slot,
 358                 "slot overlaps with its data, item end %lu data start %lu",
 359                                 btrfs_item_nr_offset(slot) +
 360                                 sizeof(struct btrfs_item),
 361                                 btrfs_item_ptr_offset(leaf, slot));
 362                         return -EUCLEAN;
 363                 }
 364
 365                 if (check_item_data) {
 366                         /*
 367                          * Check if the item size and content meet other
 368                          * criteria
 369                          */
 370                         ret = check_leaf_item(root, leaf, &key, slot);
 371                         if (ret < 0)
 372                                 return ret;
 373                 }
 374
 375                 prev_key.objectid = key.objectid;
 376                 prev_key.type = key.type;
 377                 prev_key.offset = key.offset;
 378         }
 379
 380         return 0;
 381 }
 382
 383 int btrfs_check_leaf_full(struct btrfs_root *root, struct extent_buffer *leaf)
 384 {
 385         return check_leaf(root, leaf, true);
 386 }
 387
 388 int btrfs_check_leaf_relaxed(struct btrfs_root *root,
 389                              struct extent_buffer *leaf)
 390 {
 391         return check_leaf(root, leaf, false);
 392 }
 393
 394 int btrfs_check_node(struct btrfs_root *root, struct extent_buffer *node)
 395 {
 396         unsigned long nr = btrfs_header_nritems(node);
 397         struct btrfs_key key, next_key;
 398         int slot;
 399         u64 bytenr;
 400         int ret = 0;
 401
 402         if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(root->fs_info)) {
 403                 btrfs_crit(root->fs_info,
 404 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]",
 405                            root->objectid, node->start,
 406                            nr == 0 ? "small" : "large", nr,
 407                            BTRFS_NODEPTRS_PER_BLOCK(root->fs_info));
 408                 return -EUCLEAN;
 409         }
 410
 411         for (slot = 0; slot < nr - 1; slot++) {
 412                 bytenr = btrfs_node_blockptr(node, slot);
 413                 btrfs_node_key_to_cpu(node, &key, slot);
 414                 btrfs_node_key_to_cpu(node, &next_key, slot + 1);
 415
 416                 if (!bytenr) {
 417                         generic_err(root, node, slot,
 418                                 "invalid NULL node pointer");
 419                         ret = -EUCLEAN;
 420                         goto out;
 421                 }
 422                 if (!IS_ALIGNED(bytenr, root->fs_info->sectorsize)) {
 423                         generic_err(root, node, slot,
 424                         "unaligned pointer, have %llu should be aligned to %u",
 425                                 bytenr, root->fs_info->sectorsize);
 426                         ret = -EUCLEAN;
 427                         goto out;
 428                 }
 429
 430                 if (btrfs_comp_cpu_keys(&key, &next_key) >= 0) {
 431                         generic_err(root, node, slot,
 432         "bad key order, current (%llu %u %llu) next (%llu %u %llu)",
 433                                 key.objectid, key.type, key.offset,
 434                                 next_key.objectid, next_key.type,
 435                                 next_key.offset);
 436                         ret = -EUCLEAN;
 437                         goto out;
 438                 }
 439         }
 440 out:
 441         return ret;
 442 }