btrfs: tree-checker: Replace root parameter with fs_info
[sfrench/cifs-2.6.git] / 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 #include "hash.h"
34
35 /*
36  * Error message should follow the following format:
37  * corrupt <type>: <identifier>, <reason>[, <bad_value>]
38  *
39  * @type:       leaf or node
40  * @identifier: the necessary info to locate the leaf/node.
41  *              It's recommened to decode key.objecitd/offset if it's
42  *              meaningful.
43  * @reason:     describe the error
44  * @bad_value:  optional, it's recommened to output bad value and its
45  *              expected value (range).
46  *
47  * Since comma is used to separate the components, only space is allowed
48  * inside each component.
49  */
50
51 /*
52  * Append generic "corrupt leaf/node root=%llu block=%llu slot=%d: " to @fmt.
53  * Allows callers to customize the output.
54  */
55 __printf(4, 5)
56 static void generic_err(const struct btrfs_fs_info *fs_info,
57                         const struct extent_buffer *eb, int slot,
58                         const char *fmt, ...)
59 {
60         struct va_format vaf;
61         va_list args;
62
63         va_start(args, fmt);
64
65         vaf.fmt = fmt;
66         vaf.va = &args;
67
68         btrfs_crit(fs_info,
69                 "corrupt %s: root=%llu block=%llu slot=%d, %pV",
70                 btrfs_header_level(eb) == 0 ? "leaf" : "node",
71                 btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot, &vaf);
72         va_end(args);
73 }
74
75 /*
76  * Customized reporter for extent data item, since its key objectid and
77  * offset has its own meaning.
78  */
79 __printf(4, 5)
80 static void file_extent_err(const struct btrfs_fs_info *fs_info,
81                             const struct extent_buffer *eb, int slot,
82                             const char *fmt, ...)
83 {
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(fs_info, leaf, slot, fi, name, alignment)            \
107 ({                                                                            \
108         if (!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment))) \
109                 file_extent_err((fs_info), (leaf), (slot),                    \
110         "invalid %s for file extent, have %llu, should be aligned to %u",     \
111                         (#name), btrfs_file_extent_##name((leaf), (fi)),      \
112                         (alignment));                                         \
113         (!IS_ALIGNED(btrfs_file_extent_##name((leaf), (fi)), (alignment)));   \
114 })
115
116 static int check_extent_data_item(struct btrfs_fs_info *fs_info,
117                                   struct extent_buffer *leaf,
118                                   struct btrfs_key *key, int slot)
119 {
120         struct btrfs_file_extent_item *fi;
121         u32 sectorsize = fs_info->sectorsize;
122         u32 item_size = btrfs_item_size_nr(leaf, slot);
123
124         if (!IS_ALIGNED(key->offset, sectorsize)) {
125                 file_extent_err(fs_info, leaf, slot,
126 "unaligned file_offset for file extent, have %llu should be aligned to %u",
127                         key->offset, sectorsize);
128                 return -EUCLEAN;
129         }
130
131         fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
132
133         if (btrfs_file_extent_type(leaf, fi) > BTRFS_FILE_EXTENT_TYPES) {
134                 file_extent_err(fs_info, leaf, slot,
135                 "invalid type for file extent, have %u expect range [0, %u]",
136                         btrfs_file_extent_type(leaf, fi),
137                         BTRFS_FILE_EXTENT_TYPES);
138                 return -EUCLEAN;
139         }
140
141         /*
142          * Support for new compression/encrption must introduce incompat flag,
143          * and must be caught in open_ctree().
144          */
145         if (btrfs_file_extent_compression(leaf, fi) > BTRFS_COMPRESS_TYPES) {
146                 file_extent_err(fs_info, leaf, slot,
147         "invalid compression for file extent, have %u expect range [0, %u]",
148                         btrfs_file_extent_compression(leaf, fi),
149                         BTRFS_COMPRESS_TYPES);
150                 return -EUCLEAN;
151         }
152         if (btrfs_file_extent_encryption(leaf, fi)) {
153                 file_extent_err(fs_info, leaf, slot,
154                         "invalid encryption for file extent, have %u expect 0",
155                         btrfs_file_extent_encryption(leaf, fi));
156                 return -EUCLEAN;
157         }
158         if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
159                 /* Inline extent must have 0 as key offset */
160                 if (key->offset) {
161                         file_extent_err(fs_info, leaf, slot,
162                 "invalid file_offset for inline file extent, have %llu expect 0",
163                                 key->offset);
164                         return -EUCLEAN;
165                 }
166
167                 /* Compressed inline extent has no on-disk size, skip it */
168                 if (btrfs_file_extent_compression(leaf, fi) !=
169                     BTRFS_COMPRESS_NONE)
170                         return 0;
171
172                 /* Uncompressed inline extent size must match item size */
173                 if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
174                     btrfs_file_extent_ram_bytes(leaf, fi)) {
175                         file_extent_err(fs_info, leaf, slot,
176         "invalid ram_bytes for uncompressed inline extent, have %u expect %llu",
177                                 item_size, BTRFS_FILE_EXTENT_INLINE_DATA_START +
178                                 btrfs_file_extent_ram_bytes(leaf, fi));
179                         return -EUCLEAN;
180                 }
181                 return 0;
182         }
183
184         /* Regular or preallocated extent has fixed item size */
185         if (item_size != sizeof(*fi)) {
186                 file_extent_err(fs_info, leaf, slot,
187         "invalid item size for reg/prealloc file extent, have %u expect %zu",
188                         item_size, sizeof(*fi));
189                 return -EUCLEAN;
190         }
191         if (CHECK_FE_ALIGNED(fs_info, leaf, slot, fi, ram_bytes, sectorsize) ||
192             CHECK_FE_ALIGNED(fs_info, leaf, slot, fi, disk_bytenr, sectorsize) ||
193             CHECK_FE_ALIGNED(fs_info, leaf, slot, fi, disk_num_bytes, sectorsize) ||
194             CHECK_FE_ALIGNED(fs_info, leaf, slot, fi, offset, sectorsize) ||
195             CHECK_FE_ALIGNED(fs_info, leaf, slot, fi, num_bytes, sectorsize))
196                 return -EUCLEAN;
197         return 0;
198 }
199
200 static int check_csum_item(struct btrfs_fs_info *fs_info,
201                            struct extent_buffer *leaf, struct btrfs_key *key,
202                            int slot)
203 {
204         u32 sectorsize = fs_info->sectorsize;
205         u32 csumsize = btrfs_super_csum_size(fs_info->super_copy);
206
207         if (key->objectid != BTRFS_EXTENT_CSUM_OBJECTID) {
208                 generic_err(fs_info, leaf, slot,
209                 "invalid key objectid for csum item, have %llu expect %llu",
210                         key->objectid, BTRFS_EXTENT_CSUM_OBJECTID);
211                 return -EUCLEAN;
212         }
213         if (!IS_ALIGNED(key->offset, sectorsize)) {
214                 generic_err(fs_info, leaf, slot,
215         "unaligned key offset for csum item, have %llu should be aligned to %u",
216                         key->offset, sectorsize);
217                 return -EUCLEAN;
218         }
219         if (!IS_ALIGNED(btrfs_item_size_nr(leaf, slot), csumsize)) {
220                 generic_err(fs_info, leaf, slot,
221         "unaligned item size for csum item, have %u should be aligned to %u",
222                         btrfs_item_size_nr(leaf, slot), csumsize);
223                 return -EUCLEAN;
224         }
225         return 0;
226 }
227
228 /*
229  * Customized reported for dir_item, only important new info is key->objectid,
230  * which represents inode number
231  */
232 __printf(4, 5)
233 static void dir_item_err(const struct btrfs_fs_info *fs_info,
234                          const struct extent_buffer *eb, int slot,
235                          const char *fmt, ...)
236 {
237         struct btrfs_key key;
238         struct va_format vaf;
239         va_list args;
240
241         btrfs_item_key_to_cpu(eb, &key, slot);
242         va_start(args, fmt);
243
244         vaf.fmt = fmt;
245         vaf.va = &args;
246
247         btrfs_crit(fs_info,
248         "corrupt %s: root=%llu block=%llu slot=%d ino=%llu, %pV",
249                 btrfs_header_level(eb) == 0 ? "leaf" : "node",
250                 btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
251                 key.objectid, &vaf);
252         va_end(args);
253 }
254
255 static int check_dir_item(struct btrfs_fs_info *fs_info,
256                           struct extent_buffer *leaf,
257                           struct btrfs_key *key, int slot)
258 {
259         struct btrfs_dir_item *di;
260         u32 item_size = btrfs_item_size_nr(leaf, slot);
261         u32 cur = 0;
262
263         di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
264         while (cur < item_size) {
265                 u32 name_len;
266                 u32 data_len;
267                 u32 max_name_len;
268                 u32 total_size;
269                 u32 name_hash;
270                 u8 dir_type;
271
272                 /* header itself should not cross item boundary */
273                 if (cur + sizeof(*di) > item_size) {
274                         dir_item_err(fs_info, leaf, slot,
275                 "dir item header crosses item boundary, have %zu boundary %u",
276                                 cur + sizeof(*di), item_size);
277                         return -EUCLEAN;
278                 }
279
280                 /* dir type check */
281                 dir_type = btrfs_dir_type(leaf, di);
282                 if (dir_type >= BTRFS_FT_MAX) {
283                         dir_item_err(fs_info, leaf, slot,
284                         "invalid dir item type, have %u expect [0, %u)",
285                                 dir_type, BTRFS_FT_MAX);
286                         return -EUCLEAN;
287                 }
288
289                 if (key->type == BTRFS_XATTR_ITEM_KEY &&
290                     dir_type != BTRFS_FT_XATTR) {
291                         dir_item_err(fs_info, leaf, slot,
292                 "invalid dir item type for XATTR key, have %u expect %u",
293                                 dir_type, BTRFS_FT_XATTR);
294                         return -EUCLEAN;
295                 }
296                 if (dir_type == BTRFS_FT_XATTR &&
297                     key->type != BTRFS_XATTR_ITEM_KEY) {
298                         dir_item_err(fs_info, leaf, slot,
299                         "xattr dir type found for non-XATTR key");
300                         return -EUCLEAN;
301                 }
302                 if (dir_type == BTRFS_FT_XATTR)
303                         max_name_len = XATTR_NAME_MAX;
304                 else
305                         max_name_len = BTRFS_NAME_LEN;
306
307                 /* Name/data length check */
308                 name_len = btrfs_dir_name_len(leaf, di);
309                 data_len = btrfs_dir_data_len(leaf, di);
310                 if (name_len > max_name_len) {
311                         dir_item_err(fs_info, leaf, slot,
312                         "dir item name len too long, have %u max %u",
313                                 name_len, max_name_len);
314                         return -EUCLEAN;
315                 }
316                 if (name_len + data_len > BTRFS_MAX_XATTR_SIZE(fs_info)) {
317                         dir_item_err(fs_info, leaf, slot,
318                         "dir item name and data len too long, have %u max %u",
319                                 name_len + data_len,
320                                 BTRFS_MAX_XATTR_SIZE(fs_info));
321                         return -EUCLEAN;
322                 }
323
324                 if (data_len && dir_type != BTRFS_FT_XATTR) {
325                         dir_item_err(fs_info, leaf, slot,
326                         "dir item with invalid data len, have %u expect 0",
327                                 data_len);
328                         return -EUCLEAN;
329                 }
330
331                 total_size = sizeof(*di) + name_len + data_len;
332
333                 /* header and name/data should not cross item boundary */
334                 if (cur + total_size > item_size) {
335                         dir_item_err(fs_info, leaf, slot,
336                 "dir item data crosses item boundary, have %u boundary %u",
337                                 cur + total_size, item_size);
338                         return -EUCLEAN;
339                 }
340
341                 /*
342                  * Special check for XATTR/DIR_ITEM, as key->offset is name
343                  * hash, should match its name
344                  */
345                 if (key->type == BTRFS_DIR_ITEM_KEY ||
346                     key->type == BTRFS_XATTR_ITEM_KEY) {
347                         char namebuf[max(BTRFS_NAME_LEN, XATTR_NAME_MAX)];
348
349                         read_extent_buffer(leaf, namebuf,
350                                         (unsigned long)(di + 1), name_len);
351                         name_hash = btrfs_name_hash(namebuf, name_len);
352                         if (key->offset != name_hash) {
353                                 dir_item_err(fs_info, leaf, slot,
354                 "name hash mismatch with key, have 0x%016x expect 0x%016llx",
355                                         name_hash, key->offset);
356                                 return -EUCLEAN;
357                         }
358                 }
359                 cur += total_size;
360                 di = (struct btrfs_dir_item *)((void *)di + total_size);
361         }
362         return 0;
363 }
364
365 /*
366  * Common point to switch the item-specific validation.
367  */
368 static int check_leaf_item(struct btrfs_fs_info *fs_info,
369                            struct extent_buffer *leaf,
370                            struct btrfs_key *key, int slot)
371 {
372         int ret = 0;
373
374         switch (key->type) {
375         case BTRFS_EXTENT_DATA_KEY:
376                 ret = check_extent_data_item(fs_info, leaf, key, slot);
377                 break;
378         case BTRFS_EXTENT_CSUM_KEY:
379                 ret = check_csum_item(fs_info, leaf, key, slot);
380                 break;
381         case BTRFS_DIR_ITEM_KEY:
382         case BTRFS_DIR_INDEX_KEY:
383         case BTRFS_XATTR_ITEM_KEY:
384                 ret = check_dir_item(fs_info, leaf, key, slot);
385                 break;
386         }
387         return ret;
388 }
389
390 static int check_leaf(struct btrfs_fs_info *fs_info, struct extent_buffer *leaf,
391                       bool check_item_data)
392 {
393         /* No valid key type is 0, so all key should be larger than this key */
394         struct btrfs_key prev_key = {0, 0, 0};
395         struct btrfs_key key;
396         u32 nritems = btrfs_header_nritems(leaf);
397         int slot;
398
399         /*
400          * Extent buffers from a relocation tree have a owner field that
401          * corresponds to the subvolume tree they are based on. So just from an
402          * extent buffer alone we can not find out what is the id of the
403          * corresponding subvolume tree, so we can not figure out if the extent
404          * buffer corresponds to the root of the relocation tree or not. So
405          * skip this check for relocation trees.
406          */
407         if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
408                 struct btrfs_root *check_root;
409
410                 key.objectid = btrfs_header_owner(leaf);
411                 key.type = BTRFS_ROOT_ITEM_KEY;
412                 key.offset = (u64)-1;
413
414                 check_root = btrfs_get_fs_root(fs_info, &key, false);
415                 /*
416                  * The only reason we also check NULL here is that during
417                  * open_ctree() some roots has not yet been set up.
418                  */
419                 if (!IS_ERR_OR_NULL(check_root)) {
420                         struct extent_buffer *eb;
421
422                         eb = btrfs_root_node(check_root);
423                         /* if leaf is the root, then it's fine */
424                         if (leaf != eb) {
425                                 generic_err(fs_info, leaf, 0,
426                 "invalid nritems, have %u should not be 0 for non-root leaf",
427                                         nritems);
428                                 free_extent_buffer(eb);
429                                 return -EUCLEAN;
430                         }
431                         free_extent_buffer(eb);
432                 }
433                 return 0;
434         }
435
436         if (nritems == 0)
437                 return 0;
438
439         /*
440          * Check the following things to make sure this is a good leaf, and
441          * leaf users won't need to bother with similar sanity checks:
442          *
443          * 1) key ordering
444          * 2) item offset and size
445          *    No overlap, no hole, all inside the leaf.
446          * 3) item content
447          *    If possible, do comprehensive sanity check.
448          *    NOTE: All checks must only rely on the item data itself.
449          */
450         for (slot = 0; slot < nritems; slot++) {
451                 u32 item_end_expected;
452                 int ret;
453
454                 btrfs_item_key_to_cpu(leaf, &key, slot);
455
456                 /* Make sure the keys are in the right order */
457                 if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
458                         generic_err(fs_info, leaf, slot,
459         "bad key order, prev (%llu %u %llu) current (%llu %u %llu)",
460                                 prev_key.objectid, prev_key.type,
461                                 prev_key.offset, key.objectid, key.type,
462                                 key.offset);
463                         return -EUCLEAN;
464                 }
465
466                 /*
467                  * Make sure the offset and ends are right, remember that the
468                  * item data starts at the end of the leaf and grows towards the
469                  * front.
470                  */
471                 if (slot == 0)
472                         item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
473                 else
474                         item_end_expected = btrfs_item_offset_nr(leaf,
475                                                                  slot - 1);
476                 if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
477                         generic_err(fs_info, leaf, slot,
478                                 "unexpected item end, have %u expect %u",
479                                 btrfs_item_end_nr(leaf, slot),
480                                 item_end_expected);
481                         return -EUCLEAN;
482                 }
483
484                 /*
485                  * Check to make sure that we don't point outside of the leaf,
486                  * just in case all the items are consistent to each other, but
487                  * all point outside of the leaf.
488                  */
489                 if (btrfs_item_end_nr(leaf, slot) >
490                     BTRFS_LEAF_DATA_SIZE(fs_info)) {
491                         generic_err(fs_info, leaf, slot,
492                         "slot end outside of leaf, have %u expect range [0, %u]",
493                                 btrfs_item_end_nr(leaf, slot),
494                                 BTRFS_LEAF_DATA_SIZE(fs_info));
495                         return -EUCLEAN;
496                 }
497
498                 /* Also check if the item pointer overlaps with btrfs item. */
499                 if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
500                     btrfs_item_ptr_offset(leaf, slot)) {
501                         generic_err(fs_info, leaf, slot,
502                 "slot overlaps with its data, item end %lu data start %lu",
503                                 btrfs_item_nr_offset(slot) +
504                                 sizeof(struct btrfs_item),
505                                 btrfs_item_ptr_offset(leaf, slot));
506                         return -EUCLEAN;
507                 }
508
509                 if (check_item_data) {
510                         /*
511                          * Check if the item size and content meet other
512                          * criteria
513                          */
514                         ret = check_leaf_item(fs_info, leaf, &key, slot);
515                         if (ret < 0)
516                                 return ret;
517                 }
518
519                 prev_key.objectid = key.objectid;
520                 prev_key.type = key.type;
521                 prev_key.offset = key.offset;
522         }
523
524         return 0;
525 }
526
527 int btrfs_check_leaf_full(struct btrfs_fs_info *fs_info,
528                           struct extent_buffer *leaf)
529 {
530         return check_leaf(fs_info, leaf, true);
531 }
532
533 int btrfs_check_leaf_relaxed(struct btrfs_fs_info *fs_info,
534                              struct extent_buffer *leaf)
535 {
536         return check_leaf(fs_info, leaf, false);
537 }
538
539 int btrfs_check_node(struct btrfs_fs_info *fs_info, struct extent_buffer *node)
540 {
541         unsigned long nr = btrfs_header_nritems(node);
542         struct btrfs_key key, next_key;
543         int slot;
544         u64 bytenr;
545         int ret = 0;
546
547         if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(fs_info)) {
548                 btrfs_crit(fs_info,
549 "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%u]",
550                            btrfs_header_owner(node), node->start,
551                            nr == 0 ? "small" : "large", nr,
552                            BTRFS_NODEPTRS_PER_BLOCK(fs_info));
553                 return -EUCLEAN;
554         }
555
556         for (slot = 0; slot < nr - 1; slot++) {
557                 bytenr = btrfs_node_blockptr(node, slot);
558                 btrfs_node_key_to_cpu(node, &key, slot);
559                 btrfs_node_key_to_cpu(node, &next_key, slot + 1);
560
561                 if (!bytenr) {
562                         generic_err(fs_info, node, slot,
563                                 "invalid NULL node pointer");
564                         ret = -EUCLEAN;
565                         goto out;
566                 }
567                 if (!IS_ALIGNED(bytenr, fs_info->sectorsize)) {
568                         generic_err(fs_info, node, slot,
569                         "unaligned pointer, have %llu should be aligned to %u",
570                                 bytenr, fs_info->sectorsize);
571                         ret = -EUCLEAN;
572                         goto out;
573                 }
574
575                 if (btrfs_comp_cpu_keys(&key, &next_key) >= 0) {
576                         generic_err(fs_info, node, slot,
577         "bad key order, current (%llu %u %llu) next (%llu %u %llu)",
578                                 key.objectid, key.type, key.offset,
579                                 next_key.objectid, next_key.type,
580                                 next_key.offset);
581                         ret = -EUCLEAN;
582                         goto out;
583                 }
584         }
585 out:
586         return ret;
587 }