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 int btrfs_check_leaf(struct btrfs_root *root, struct extent_buffer *leaf)
 246 {
 247         struct btrfs_fs_info *fs_info = root->fs_info;
 248         /* No valid key type is 0, so all key should be larger than this key */
 249         struct btrfs_key prev_key = {0, 0, 0};
 250         struct btrfs_key key;
 251         u32 nritems = btrfs_header_nritems(leaf);
 252         int slot;
 253
 254         /*
 255          * Extent buffers from a relocation tree have a owner field that
 256          * corresponds to the subvolume tree they are based on. So just from an
 257          * extent buffer alone we can not find out what is the id of the
 258          * corresponding subvolume tree, so we can not figure out if the extent
 259          * buffer corresponds to the root of the relocation tree or not. So
 260          * skip this check for relocation trees.
 261          */
 262         if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
 263                 struct btrfs_root *check_root;
 264
 265                 key.objectid = btrfs_header_owner(leaf);
 266                 key.type = BTRFS_ROOT_ITEM_KEY;
 267                 key.offset = (u64)-1;
 268
 269                 check_root = btrfs_get_fs_root(fs_info, &key, false);
 270                 /*
 271                  * The only reason we also check NULL here is that during
 272                  * open_ctree() some roots has not yet been set up.
 273                  */
 274                 if (!IS_ERR_OR_NULL(check_root)) {
 275                         struct extent_buffer *eb;
 276
 277                         eb = btrfs_root_node(check_root);
 278                         /* if leaf is the root, then it's fine */
 279                         if (leaf != eb) {
 280                                 generic_err(check_root, leaf, 0,
 281                 "invalid nritems, have %u should not be 0 for non-root leaf",
 282                                         nritems);
 283                                 free_extent_buffer(eb);
 284                                 return -EUCLEAN;
 285                         }
 286                         free_extent_buffer(eb);
 287                 }
 288                 return 0;
 289         }
 290
 291         if (nritems == 0)
 292                 return 0;
 293
 294         /*
 295          * Check the following things to make sure this is a good leaf, and
 296          * leaf users won't need to bother with similar sanity checks:
 297          *
 298          * 1) key ordering
 299          * 2) item offset and size
 300          *    No overlap, no hole, all inside the leaf.
 301          * 3) item content
 302          *    If possible, do comprehensive sanity check.
 303          *    NOTE: All checks must only rely on the item data itself.
 304          */
 305         for (slot = 0; slot < nritems; slot++) {
 306                 u32 item_end_expected;
 307                 int ret;
 308
 309                 btrfs_item_key_to_cpu(leaf, &key, slot);
 310
 311                 /* Make sure the keys are in the right order */
 312                 if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
 313                         generic_err(root, leaf, slot,
 314         "bad key order, prev (%llu %u %llu) current (%llu %u %llu)",
 315                                 prev_key.objectid, prev_key.type,
 316                                 prev_key.offset, key.objectid, key.type,
 317                                 key.offset);
 318                         return -EUCLEAN;
 319                 }
 320
 321                 /*
 322                  * Make sure the offset and ends are right, remember that the
 323                  * item data starts at the end of the leaf and grows towards the
 324                  * front.
 325                  */
 326                 if (slot == 0)
 327                         item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
 328                 else
 329                         item_end_expected = btrfs_item_offset_nr(leaf,
 330                                                                  slot - 1);
 331                 if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
 332                         generic_err(root, leaf, slot,
 333                                 "unexpected item end, have %u expect %u",
 334                                 btrfs_item_end_nr(leaf, slot),
 335                                 item_end_expected);
 336                         return -EUCLEAN;
 337                 }
 338
 339                 /*
 340                  * Check to make sure that we don't point outside of the leaf,
 341                  * just in case all the items are consistent to each other, but
 342                  * all point outside of the leaf.
 343                  */
 344                 if (btrfs_item_end_nr(leaf, slot) >
 345                     BTRFS_LEAF_DATA_SIZE(fs_info)) {
 346                         generic_err(root, leaf, slot,
 347                         "slot end outside of leaf, have %u expect range [0, %u]",
 348                                 btrfs_item_end_nr(leaf, slot),
 349                                 BTRFS_LEAF_DATA_SIZE(fs_info));
 350                         return -EUCLEAN;
 351                 }
 352
 353                 /* Also check if the item pointer overlaps with btrfs item. */
 354                 if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
 355                     btrfs_item_ptr_offset(leaf, slot)) {
 356                         generic_err(root, leaf, slot,
 357                 "slot overlaps with its data, item end %lu data start %lu",
 358                                 btrfs_item_nr_offset(slot) +
 359                                 sizeof(struct btrfs_item),
 360                                 btrfs_item_ptr_offset(leaf, slot));
 361                         return -EUCLEAN;
 362                 }
 363
 364                 /* Check if the item size and content meet other criteria */
 365                 ret = check_leaf_item(root, leaf, &key, slot);
 366                 if (ret < 0)
 367                         return ret;
 368
 369                 prev_key.objectid = key.objectid;
 370                 prev_key.type = key.type;
 371                 prev_key.offset = key.offset;
 372         }
 373
 374         return 0;
 375 }
 376
 377 int btrfs_check_node(struct btrfs_root *root, struct extent_buffer *node)
 378 {
 379         unsigned long nr = btrfs_header_nritems(node);
 380         struct btrfs_key key, next_key;
 381         int slot;
 382         u64 bytenr;
 383         int ret = 0;
 384
 385         if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(root->fs_info)) {
 386                 btrfs_crit(root->fs_info,
 387 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]",
 388                            root->objectid, node->start,
 389                            nr == 0 ? "small" : "large", nr,
 390                            BTRFS_NODEPTRS_PER_BLOCK(root->fs_info));
 391                 return -EUCLEAN;
 392         }
 393
 394         for (slot = 0; slot < nr - 1; slot++) {
 395                 bytenr = btrfs_node_blockptr(node, slot);
 396                 btrfs_node_key_to_cpu(node, &key, slot);
 397                 btrfs_node_key_to_cpu(node, &next_key, slot + 1);
 398
 399                 if (!bytenr) {
 400                         generic_err(root, node, slot,
 401                                 "invalid NULL node pointer");
 402                         ret = -EUCLEAN;
 403                         goto out;
 404                 }
 405                 if (!IS_ALIGNED(bytenr, root->fs_info->sectorsize)) {
 406                         generic_err(root, node, slot,
 407                         "unaligned pointer, have %llu should be aligned to %u",
 408                                 bytenr, root->fs_info->sectorsize);
 409                         ret = -EUCLEAN;
 410                         goto out;
 411                 }
 412
 413                 if (btrfs_comp_cpu_keys(&key, &next_key) >= 0) {
 414                         generic_err(root, node, slot,
 415         "bad key order, current (%llu %u %llu) next (%llu %u %llu)",
 416                                 key.objectid, key.type, key.offset,
 417                                 next_key.objectid, next_key.type,
 418                                 next_key.offset);
 419                         ret = -EUCLEAN;
 420                         goto out;
 421                 }
 422         }
 423 out:
 424         return ret;
 425 }