linux/fs/btrfs/check-integrity.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (C) STRATO AG 2011.  All rights reserved.
   4 */
   5
   6/*
   7 * This module can be used to catch cases when the btrfs kernel
   8 * code executes write requests to the disk that bring the file
   9 * system in an inconsistent state. In such a state, a power-loss
  10 * or kernel panic event would cause that the data on disk is
  11 * lost or at least damaged.
  12 *
  13 * Code is added that examines all block write requests during
  14 * runtime (including writes of the super block). Three rules
  15 * are verified and an error is printed on violation of the
  16 * rules:
  17 * 1. It is not allowed to write a disk block which is
  18 *    currently referenced by the super block (either directly
  19 *    or indirectly).
  20 * 2. When a super block is written, it is verified that all
  21 *    referenced (directly or indirectly) blocks fulfill the
  22 *    following requirements:
  23 *    2a. All referenced blocks have either been present when
  24 *        the file system was mounted, (i.e., they have been
  25 *        referenced by the super block) or they have been
  26 *        written since then and the write completion callback
  27 *        was called and no write error was indicated and a
  28 *        FLUSH request to the device where these blocks are
  29 *        located was received and completed.
  30 *    2b. All referenced blocks need to have a generation
  31 *        number which is equal to the parent's number.
  32 *
  33 * One issue that was found using this module was that the log
  34 * tree on disk became temporarily corrupted because disk blocks
  35 * that had been in use for the log tree had been freed and
  36 * reused too early, while being referenced by the written super
  37 * block.
  38 *
  39 * The search term in the kernel log that can be used to filter
  40 * on the existence of detected integrity issues is
  41 * "btrfs: attempt".
  42 *
  43 * The integrity check is enabled via mount options. These
  44 * mount options are only supported if the integrity check
  45 * tool is compiled by defining BTRFS_FS_CHECK_INTEGRITY.
  46 *
  47 * Example #1, apply integrity checks to all metadata:
  48 * mount /dev/sdb1 /mnt -o check_int
  49 *
  50 * Example #2, apply integrity checks to all metadata and
  51 * to data extents:
  52 * mount /dev/sdb1 /mnt -o check_int_data
  53 *
  54 * Example #3, apply integrity checks to all metadata and dump
  55 * the tree that the super block references to kernel messages
  56 * each time after a super block was written:
  57 * mount /dev/sdb1 /mnt -o check_int,check_int_print_mask=263
  58 *
  59 * If the integrity check tool is included and activated in
  60 * the mount options, plenty of kernel memory is used, and
  61 * plenty of additional CPU cycles are spent. Enabling this
  62 * functionality is not intended for normal use. In most
  63 * cases, unless you are a btrfs developer who needs to verify
  64 * the integrity of (super)-block write requests, do not
  65 * enable the config option BTRFS_FS_CHECK_INTEGRITY to
  66 * include and compile the integrity check tool.
  67 *
  68 * Expect millions of lines of information in the kernel log with an
  69 * enabled check_int_print_mask. Therefore set LOG_BUF_SHIFT in the
  70 * kernel config to at least 26 (which is 64MB). Usually the value is
  71 * limited to 21 (which is 2MB) in init/Kconfig. The file needs to be
  72 * changed like this before LOG_BUF_SHIFT can be set to a high value:
  73 * config LOG_BUF_SHIFT
  74 *       int "Kernel log buffer size (16 => 64KB, 17 => 128KB)"
  75 *       range 12 30
  76 */
  77
  78#include <linux/sched.h>
  79#include <linux/slab.h>
  80#include <linux/mutex.h>
  81#include <linux/genhd.h>
  82#include <linux/blkdev.h>
  83#include <linux/mm.h>
  84#include <linux/string.h>
  85#include <crypto/hash.h>
  86#include "ctree.h"
  87#include "disk-io.h"
  88#include "transaction.h"
  89#include "extent_io.h"
  90#include "volumes.h"
  91#include "print-tree.h"
  92#include "locking.h"
  93#include "check-integrity.h"
  94#include "rcu-string.h"
  95#include "compression.h"
  96
  97#define BTRFSIC_BLOCK_HASHTABLE_SIZE 0x10000
  98#define BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE 0x10000
  99#define BTRFSIC_DEV2STATE_HASHTABLE_SIZE 0x100
 100#define BTRFSIC_BLOCK_MAGIC_NUMBER 0x14491051
 101#define BTRFSIC_BLOCK_LINK_MAGIC_NUMBER 0x11070807
 102#define BTRFSIC_DEV2STATE_MAGIC_NUMBER 0x20111530
 103#define BTRFSIC_BLOCK_STACK_FRAME_MAGIC_NUMBER 20111300
 104#define BTRFSIC_TREE_DUMP_MAX_INDENT_LEVEL (200 - 6)    /* in characters,
 105                                                         * excluding " [...]" */
 106#define BTRFSIC_GENERATION_UNKNOWN ((u64)-1)
 107
 108/*
 109 * The definition of the bitmask fields for the print_mask.
 110 * They are specified with the mount option check_integrity_print_mask.
 111 */
 112#define BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE                     0x00000001
 113#define BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION         0x00000002
 114#define BTRFSIC_PRINT_MASK_TREE_AFTER_SB_WRITE                  0x00000004
 115#define BTRFSIC_PRINT_MASK_TREE_BEFORE_SB_WRITE                 0x00000008
 116#define BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH                        0x00000010
 117#define BTRFSIC_PRINT_MASK_END_IO_BIO_BH                        0x00000020
 118#define BTRFSIC_PRINT_MASK_VERBOSE                              0x00000040
 119#define BTRFSIC_PRINT_MASK_VERY_VERBOSE                         0x00000080
 120#define BTRFSIC_PRINT_MASK_INITIAL_TREE                         0x00000100
 121#define BTRFSIC_PRINT_MASK_INITIAL_ALL_TREES                    0x00000200
 122#define BTRFSIC_PRINT_MASK_INITIAL_DATABASE                     0x00000400
 123#define BTRFSIC_PRINT_MASK_NUM_COPIES                           0x00000800
 124#define BTRFSIC_PRINT_MASK_TREE_WITH_ALL_MIRRORS                0x00001000
 125#define BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH_VERBOSE                0x00002000
 126
 127struct btrfsic_dev_state;
 128struct btrfsic_state;
 129
 130struct btrfsic_block {
 131        u32 magic_num;          /* only used for debug purposes */
 132        unsigned int is_metadata:1;     /* if it is meta-data, not data-data */
 133        unsigned int is_superblock:1;   /* if it is one of the superblocks */
 134        unsigned int is_iodone:1;       /* if is done by lower subsystem */
 135        unsigned int iodone_w_error:1;  /* error was indicated to endio */
 136        unsigned int never_written:1;   /* block was added because it was
 137                                         * referenced, not because it was
 138                                         * written */
 139        unsigned int mirror_num;        /* large enough to hold
 140                                         * BTRFS_SUPER_MIRROR_MAX */
 141        struct btrfsic_dev_state *dev_state;
 142        u64 dev_bytenr;         /* key, physical byte num on disk */
 143        u64 logical_bytenr;     /* logical byte num on disk */
 144        u64 generation;
 145        struct btrfs_disk_key disk_key; /* extra info to print in case of
 146                                         * issues, will not always be correct */
 147        struct list_head collision_resolving_node;      /* list node */
 148        struct list_head all_blocks_node;       /* list node */
 149
 150        /* the following two lists contain block_link items */
 151        struct list_head ref_to_list;   /* list */
 152        struct list_head ref_from_list; /* list */
 153        struct btrfsic_block *next_in_same_bio;
 154        void *orig_bio_private;
 155        bio_end_io_t *orig_bio_end_io;
 156        int submit_bio_bh_rw;
 157        u64 flush_gen; /* only valid if !never_written */
 158};
 159
 160/*
 161 * Elements of this type are allocated dynamically and required because
 162 * each block object can refer to and can be ref from multiple blocks.
 163 * The key to lookup them in the hashtable is the dev_bytenr of
 164 * the block ref to plus the one from the block referred from.
 165 * The fact that they are searchable via a hashtable and that a
 166 * ref_cnt is maintained is not required for the btrfs integrity
 167 * check algorithm itself, it is only used to make the output more
 168 * beautiful in case that an error is detected (an error is defined
 169 * as a write operation to a block while that block is still referenced).
 170 */
 171struct btrfsic_block_link {
 172        u32 magic_num;          /* only used for debug purposes */
 173        u32 ref_cnt;
 174        struct list_head node_ref_to;   /* list node */
 175        struct list_head node_ref_from; /* list node */
 176        struct list_head collision_resolving_node;      /* list node */
 177        struct btrfsic_block *block_ref_to;
 178        struct btrfsic_block *block_ref_from;
 179        u64 parent_generation;
 180};
 181
 182struct btrfsic_dev_state {
 183        u32 magic_num;          /* only used for debug purposes */
 184        struct block_device *bdev;
 185        struct btrfsic_state *state;
 186        struct list_head collision_resolving_node;      /* list node */
 187        struct btrfsic_block dummy_block_for_bio_bh_flush;
 188        u64 last_flush_gen;
 189        char name[BDEVNAME_SIZE];
 190};
 191
 192struct btrfsic_block_hashtable {
 193        struct list_head table[BTRFSIC_BLOCK_HASHTABLE_SIZE];
 194};
 195
 196struct btrfsic_block_link_hashtable {
 197        struct list_head table[BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE];
 198};
 199
 200struct btrfsic_dev_state_hashtable {
 201        struct list_head table[BTRFSIC_DEV2STATE_HASHTABLE_SIZE];
 202};
 203
 204struct btrfsic_block_data_ctx {
 205        u64 start;              /* virtual bytenr */
 206        u64 dev_bytenr;         /* physical bytenr on device */
 207        u32 len;
 208        struct btrfsic_dev_state *dev;
 209        char **datav;
 210        struct page **pagev;
 211        void *mem_to_free;
 212};
 213
 214/* This structure is used to implement recursion without occupying
 215 * any stack space, refer to btrfsic_process_metablock() */
 216struct btrfsic_stack_frame {
 217        u32 magic;
 218        u32 nr;
 219        int error;
 220        int i;
 221        int limit_nesting;
 222        int num_copies;
 223        int mirror_num;
 224        struct btrfsic_block *block;
 225        struct btrfsic_block_data_ctx *block_ctx;
 226        struct btrfsic_block *next_block;
 227        struct btrfsic_block_data_ctx next_block_ctx;
 228        struct btrfs_header *hdr;
 229        struct btrfsic_stack_frame *prev;
 230};
 231
 232/* Some state per mounted filesystem */
 233struct btrfsic_state {
 234        u32 print_mask;
 235        int include_extent_data;
 236        struct list_head all_blocks_list;
 237        struct btrfsic_block_hashtable block_hashtable;
 238        struct btrfsic_block_link_hashtable block_link_hashtable;
 239        struct btrfs_fs_info *fs_info;
 240        u64 max_superblock_generation;
 241        struct btrfsic_block *latest_superblock;
 242        u32 metablock_size;
 243        u32 datablock_size;
 244};
 245
 246static void btrfsic_block_init(struct btrfsic_block *b);
 247static struct btrfsic_block *btrfsic_block_alloc(void);
 248static void btrfsic_block_free(struct btrfsic_block *b);
 249static void btrfsic_block_link_init(struct btrfsic_block_link *n);
 250static struct btrfsic_block_link *btrfsic_block_link_alloc(void);
 251static void btrfsic_block_link_free(struct btrfsic_block_link *n);
 252static void btrfsic_dev_state_init(struct btrfsic_dev_state *ds);
 253static struct btrfsic_dev_state *btrfsic_dev_state_alloc(void);
 254static void btrfsic_dev_state_free(struct btrfsic_dev_state *ds);
 255static void btrfsic_block_hashtable_init(struct btrfsic_block_hashtable *h);
 256static void btrfsic_block_hashtable_add(struct btrfsic_block *b,
 257                                        struct btrfsic_block_hashtable *h);
 258static void btrfsic_block_hashtable_remove(struct btrfsic_block *b);
 259static struct btrfsic_block *btrfsic_block_hashtable_lookup(
 260                struct block_device *bdev,
 261                u64 dev_bytenr,
 262                struct btrfsic_block_hashtable *h);
 263static void btrfsic_block_link_hashtable_init(
 264                struct btrfsic_block_link_hashtable *h);
 265static void btrfsic_block_link_hashtable_add(
 266                struct btrfsic_block_link *l,
 267                struct btrfsic_block_link_hashtable *h);
 268static void btrfsic_block_link_hashtable_remove(struct btrfsic_block_link *l);
 269static struct btrfsic_block_link *btrfsic_block_link_hashtable_lookup(
 270                struct block_device *bdev_ref_to,
 271                u64 dev_bytenr_ref_to,
 272                struct block_device *bdev_ref_from,
 273                u64 dev_bytenr_ref_from,
 274                struct btrfsic_block_link_hashtable *h);
 275static void btrfsic_dev_state_hashtable_init(
 276                struct btrfsic_dev_state_hashtable *h);
 277static void btrfsic_dev_state_hashtable_add(
 278                struct btrfsic_dev_state *ds,
 279                struct btrfsic_dev_state_hashtable *h);
 280static void btrfsic_dev_state_hashtable_remove(struct btrfsic_dev_state *ds);
 281static struct btrfsic_dev_state *btrfsic_dev_state_hashtable_lookup(dev_t dev,
 282                struct btrfsic_dev_state_hashtable *h);
 283static struct btrfsic_stack_frame *btrfsic_stack_frame_alloc(void);
 284static void btrfsic_stack_frame_free(struct btrfsic_stack_frame *sf);
 285static int btrfsic_process_superblock(struct btrfsic_state *state,
 286                                      struct btrfs_fs_devices *fs_devices);
 287static int btrfsic_process_metablock(struct btrfsic_state *state,
 288                                     struct btrfsic_block *block,
 289                                     struct btrfsic_block_data_ctx *block_ctx,
 290                                     int limit_nesting, int force_iodone_flag);
 291static void btrfsic_read_from_block_data(
 292        struct btrfsic_block_data_ctx *block_ctx,
 293        void *dst, u32 offset, size_t len);
 294static int btrfsic_create_link_to_next_block(
 295                struct btrfsic_state *state,
 296                struct btrfsic_block *block,
 297                struct btrfsic_block_data_ctx
 298                *block_ctx, u64 next_bytenr,
 299                int limit_nesting,
 300                struct btrfsic_block_data_ctx *next_block_ctx,
 301                struct btrfsic_block **next_blockp,
 302                int force_iodone_flag,
 303                int *num_copiesp, int *mirror_nump,
 304                struct btrfs_disk_key *disk_key,
 305                u64 parent_generation);
 306static int btrfsic_handle_extent_data(struct btrfsic_state *state,
 307                                      struct btrfsic_block *block,
 308                                      struct btrfsic_block_data_ctx *block_ctx,
 309                                      u32 item_offset, int force_iodone_flag);
 310static int btrfsic_map_block(struct btrfsic_state *state, u64 bytenr, u32 len,
 311                             struct btrfsic_block_data_ctx *block_ctx_out,
 312                             int mirror_num);
 313static void btrfsic_release_block_ctx(struct btrfsic_block_data_ctx *block_ctx);
 314static int btrfsic_read_block(struct btrfsic_state *state,
 315                              struct btrfsic_block_data_ctx *block_ctx);
 316static void btrfsic_dump_database(struct btrfsic_state *state);
 317static int btrfsic_test_for_metadata(struct btrfsic_state *state,
 318                                     char **datav, unsigned int num_pages);
 319static void btrfsic_process_written_block(struct btrfsic_dev_state *dev_state,
 320                                          u64 dev_bytenr, char **mapped_datav,
 321                                          unsigned int num_pages,
 322                                          struct bio *bio, int *bio_is_patched,
 323                                          int submit_bio_bh_rw);
 324static int btrfsic_process_written_superblock(
 325                struct btrfsic_state *state,
 326                struct btrfsic_block *const block,
 327                struct btrfs_super_block *const super_hdr);
 328static void btrfsic_bio_end_io(struct bio *bp);
 329static int btrfsic_is_block_ref_by_superblock(const struct btrfsic_state *state,
 330                                              const struct btrfsic_block *block,
 331                                              int recursion_level);
 332static int btrfsic_check_all_ref_blocks(struct btrfsic_state *state,
 333                                        struct btrfsic_block *const block,
 334                                        int recursion_level);
 335static void btrfsic_print_add_link(const struct btrfsic_state *state,
 336                                   const struct btrfsic_block_link *l);
 337static void btrfsic_print_rem_link(const struct btrfsic_state *state,
 338                                   const struct btrfsic_block_link *l);
 339static char btrfsic_get_block_type(const struct btrfsic_state *state,
 340                                   const struct btrfsic_block *block);
 341static void btrfsic_dump_tree(const struct btrfsic_state *state);
 342static void btrfsic_dump_tree_sub(const struct btrfsic_state *state,
 343                                  const struct btrfsic_block *block,
 344                                  int indent_level);
 345static struct btrfsic_block_link *btrfsic_block_link_lookup_or_add(
 346                struct btrfsic_state *state,
 347                struct btrfsic_block_data_ctx *next_block_ctx,
 348                struct btrfsic_block *next_block,
 349                struct btrfsic_block *from_block,
 350                u64 parent_generation);
 351static struct btrfsic_block *btrfsic_block_lookup_or_add(
 352                struct btrfsic_state *state,
 353                struct btrfsic_block_data_ctx *block_ctx,
 354                const char *additional_string,
 355                int is_metadata,
 356                int is_iodone,
 357                int never_written,
 358                int mirror_num,
 359                int *was_created);
 360static int btrfsic_process_superblock_dev_mirror(
 361                struct btrfsic_state *state,
 362                struct btrfsic_dev_state *dev_state,
 363                struct btrfs_device *device,
 364                int superblock_mirror_num,
 365                struct btrfsic_dev_state **selected_dev_state,
 366                struct btrfs_super_block *selected_super);
 367static struct btrfsic_dev_state *btrfsic_dev_state_lookup(dev_t dev);
 368static void btrfsic_cmp_log_and_dev_bytenr(struct btrfsic_state *state,
 369                                           u64 bytenr,
 370                                           struct btrfsic_dev_state *dev_state,
 371                                           u64 dev_bytenr);
 372
 373static struct mutex btrfsic_mutex;
 374static int btrfsic_is_initialized;
 375static struct btrfsic_dev_state_hashtable btrfsic_dev_state_hashtable;
 376
 377
 378static void btrfsic_block_init(struct btrfsic_block *b)
 379{
 380        b->magic_num = BTRFSIC_BLOCK_MAGIC_NUMBER;
 381        b->dev_state = NULL;
 382        b->dev_bytenr = 0;
 383        b->logical_bytenr = 0;
 384        b->generation = BTRFSIC_GENERATION_UNKNOWN;
 385        b->disk_key.objectid = 0;
 386        b->disk_key.type = 0;
 387        b->disk_key.offset = 0;
 388        b->is_metadata = 0;
 389        b->is_superblock = 0;
 390        b->is_iodone = 0;
 391        b->iodone_w_error = 0;
 392        b->never_written = 0;
 393        b->mirror_num = 0;
 394        b->next_in_same_bio = NULL;
 395        b->orig_bio_private = NULL;
 396        b->orig_bio_end_io = NULL;
 397        INIT_LIST_HEAD(&b->collision_resolving_node);
 398        INIT_LIST_HEAD(&b->all_blocks_node);
 399        INIT_LIST_HEAD(&b->ref_to_list);
 400        INIT_LIST_HEAD(&b->ref_from_list);
 401        b->submit_bio_bh_rw = 0;
 402        b->flush_gen = 0;
 403}
 404
 405static struct btrfsic_block *btrfsic_block_alloc(void)
 406{
 407        struct btrfsic_block *b;
 408
 409        b = kzalloc(sizeof(*b), GFP_NOFS);
 410        if (NULL != b)
 411                btrfsic_block_init(b);
 412
 413        return b;
 414}
 415
 416static void btrfsic_block_free(struct btrfsic_block *b)
 417{
 418        BUG_ON(!(NULL == b || BTRFSIC_BLOCK_MAGIC_NUMBER == b->magic_num));
 419        kfree(b);
 420}
 421
 422static void btrfsic_block_link_init(struct btrfsic_block_link *l)
 423{
 424        l->magic_num = BTRFSIC_BLOCK_LINK_MAGIC_NUMBER;
 425        l->ref_cnt = 1;
 426        INIT_LIST_HEAD(&l->node_ref_to);
 427        INIT_LIST_HEAD(&l->node_ref_from);
 428        INIT_LIST_HEAD(&l->collision_resolving_node);
 429        l->block_ref_to = NULL;
 430        l->block_ref_from = NULL;
 431}
 432
 433static struct btrfsic_block_link *btrfsic_block_link_alloc(void)
 434{
 435        struct btrfsic_block_link *l;
 436
 437        l = kzalloc(sizeof(*l), GFP_NOFS);
 438        if (NULL != l)
 439                btrfsic_block_link_init(l);
 440
 441        return l;
 442}
 443
 444static void btrfsic_block_link_free(struct btrfsic_block_link *l)
 445{
 446        BUG_ON(!(NULL == l || BTRFSIC_BLOCK_LINK_MAGIC_NUMBER == l->magic_num));
 447        kfree(l);
 448}
 449
 450static void btrfsic_dev_state_init(struct btrfsic_dev_state *ds)
 451{
 452        ds->magic_num = BTRFSIC_DEV2STATE_MAGIC_NUMBER;
 453        ds->bdev = NULL;
 454        ds->state = NULL;
 455        ds->name[0] = '\0';
 456        INIT_LIST_HEAD(&ds->collision_resolving_node);
 457        ds->last_flush_gen = 0;
 458        btrfsic_block_init(&ds->dummy_block_for_bio_bh_flush);
 459        ds->dummy_block_for_bio_bh_flush.is_iodone = 1;
 460        ds->dummy_block_for_bio_bh_flush.dev_state = ds;
 461}
 462
 463static struct btrfsic_dev_state *btrfsic_dev_state_alloc(void)
 464{
 465        struct btrfsic_dev_state *ds;
 466
 467        ds = kzalloc(sizeof(*ds), GFP_NOFS);
 468        if (NULL != ds)
 469                btrfsic_dev_state_init(ds);
 470
 471        return ds;
 472}
 473
 474static void btrfsic_dev_state_free(struct btrfsic_dev_state *ds)
 475{
 476        BUG_ON(!(NULL == ds ||
 477                 BTRFSIC_DEV2STATE_MAGIC_NUMBER == ds->magic_num));
 478        kfree(ds);
 479}
 480
 481static void btrfsic_block_hashtable_init(struct btrfsic_block_hashtable *h)
 482{
 483        int i;
 484
 485        for (i = 0; i < BTRFSIC_BLOCK_HASHTABLE_SIZE; i++)
 486                INIT_LIST_HEAD(h->table + i);
 487}
 488
 489static void btrfsic_block_hashtable_add(struct btrfsic_block *b,
 490                                        struct btrfsic_block_hashtable *h)
 491{
 492        const unsigned int hashval =
 493            (((unsigned int)(b->dev_bytenr >> 16)) ^
 494             ((unsigned int)((uintptr_t)b->dev_state->bdev))) &
 495             (BTRFSIC_BLOCK_HASHTABLE_SIZE - 1);
 496
 497        list_add(&b->collision_resolving_node, h->table + hashval);
 498}
 499
 500static void btrfsic_block_hashtable_remove(struct btrfsic_block *b)
 501{
 502        list_del(&b->collision_resolving_node);
 503}
 504
 505static struct btrfsic_block *btrfsic_block_hashtable_lookup(
 506                struct block_device *bdev,
 507                u64 dev_bytenr,
 508                struct btrfsic_block_hashtable *h)
 509{
 510        const unsigned int hashval =
 511            (((unsigned int)(dev_bytenr >> 16)) ^
 512             ((unsigned int)((uintptr_t)bdev))) &
 513             (BTRFSIC_BLOCK_HASHTABLE_SIZE - 1);
 514        struct btrfsic_block *b;
 515
 516        list_for_each_entry(b, h->table + hashval, collision_resolving_node) {
 517                if (b->dev_state->bdev == bdev && b->dev_bytenr == dev_bytenr)
 518                        return b;
 519        }
 520
 521        return NULL;
 522}
 523
 524static void btrfsic_block_link_hashtable_init(
 525                struct btrfsic_block_link_hashtable *h)
 526{
 527        int i;
 528
 529        for (i = 0; i < BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE; i++)
 530                INIT_LIST_HEAD(h->table + i);
 531}
 532
 533static void btrfsic_block_link_hashtable_add(
 534                struct btrfsic_block_link *l,
 535                struct btrfsic_block_link_hashtable *h)
 536{
 537        const unsigned int hashval =
 538            (((unsigned int)(l->block_ref_to->dev_bytenr >> 16)) ^
 539             ((unsigned int)(l->block_ref_from->dev_bytenr >> 16)) ^
 540             ((unsigned int)((uintptr_t)l->block_ref_to->dev_state->bdev)) ^
 541             ((unsigned int)((uintptr_t)l->block_ref_from->dev_state->bdev)))
 542             & (BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE - 1);
 543
 544        BUG_ON(NULL == l->block_ref_to);
 545        BUG_ON(NULL == l->block_ref_from);
 546        list_add(&l->collision_resolving_node, h->table + hashval);
 547}
 548
 549static void btrfsic_block_link_hashtable_remove(struct btrfsic_block_link *l)
 550{
 551        list_del(&l->collision_resolving_node);
 552}
 553
 554static struct btrfsic_block_link *btrfsic_block_link_hashtable_lookup(
 555                struct block_device *bdev_ref_to,
 556                u64 dev_bytenr_ref_to,
 557                struct block_device *bdev_ref_from,
 558                u64 dev_bytenr_ref_from,
 559                struct btrfsic_block_link_hashtable *h)
 560{
 561        const unsigned int hashval =
 562            (((unsigned int)(dev_bytenr_ref_to >> 16)) ^
 563             ((unsigned int)(dev_bytenr_ref_from >> 16)) ^
 564             ((unsigned int)((uintptr_t)bdev_ref_to)) ^
 565             ((unsigned int)((uintptr_t)bdev_ref_from))) &
 566             (BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE - 1);
 567        struct btrfsic_block_link *l;
 568
 569        list_for_each_entry(l, h->table + hashval, collision_resolving_node) {
 570                BUG_ON(NULL == l->block_ref_to);
 571                BUG_ON(NULL == l->block_ref_from);
 572                if (l->block_ref_to->dev_state->bdev == bdev_ref_to &&
 573                    l->block_ref_to->dev_bytenr == dev_bytenr_ref_to &&
 574                    l->block_ref_from->dev_state->bdev == bdev_ref_from &&
 575                    l->block_ref_from->dev_bytenr == dev_bytenr_ref_from)
 576                        return l;
 577        }
 578
 579        return NULL;
 580}
 581
 582static void btrfsic_dev_state_hashtable_init(
 583                struct btrfsic_dev_state_hashtable *h)
 584{
 585        int i;
 586
 587        for (i = 0; i < BTRFSIC_DEV2STATE_HASHTABLE_SIZE; i++)
 588                INIT_LIST_HEAD(h->table + i);
 589}
 590
 591static void btrfsic_dev_state_hashtable_add(
 592                struct btrfsic_dev_state *ds,
 593                struct btrfsic_dev_state_hashtable *h)
 594{
 595        const unsigned int hashval =
 596            (((unsigned int)((uintptr_t)ds->bdev->bd_dev)) &
 597             (BTRFSIC_DEV2STATE_HASHTABLE_SIZE - 1));
 598
 599        list_add(&ds->collision_resolving_node, h->table + hashval);
 600}
 601
 602static void btrfsic_dev_state_hashtable_remove(struct btrfsic_dev_state *ds)
 603{
 604        list_del(&ds->collision_resolving_node);
 605}
 606
 607static struct btrfsic_dev_state *btrfsic_dev_state_hashtable_lookup(dev_t dev,
 608                struct btrfsic_dev_state_hashtable *h)
 609{
 610        const unsigned int hashval =
 611                dev & (BTRFSIC_DEV2STATE_HASHTABLE_SIZE - 1);
 612        struct btrfsic_dev_state *ds;
 613
 614        list_for_each_entry(ds, h->table + hashval, collision_resolving_node) {
 615                if (ds->bdev->bd_dev == dev)
 616                        return ds;
 617        }
 618
 619        return NULL;
 620}
 621
 622static int btrfsic_process_superblock(struct btrfsic_state *state,
 623                                      struct btrfs_fs_devices *fs_devices)
 624{
 625        struct btrfs_super_block *selected_super;
 626        struct list_head *dev_head = &fs_devices->devices;
 627        struct btrfs_device *device;
 628        struct btrfsic_dev_state *selected_dev_state = NULL;
 629        int ret = 0;
 630        int pass;
 631
 632        selected_super = kzalloc(sizeof(*selected_super), GFP_NOFS);
 633        if (!selected_super)
 634                return -ENOMEM;
 635
 636        list_for_each_entry(device, dev_head, dev_list) {
 637                int i;
 638                struct btrfsic_dev_state *dev_state;
 639
 640                if (!device->bdev || !device->name)
 641                        continue;
 642
 643                dev_state = btrfsic_dev_state_lookup(device->bdev->bd_dev);
 644                BUG_ON(NULL == dev_state);
 645                for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
 646                        ret = btrfsic_process_superblock_dev_mirror(
 647                                        state, dev_state, device, i,
 648                                        &selected_dev_state, selected_super);
 649                        if (0 != ret && 0 == i) {
 650                                kfree(selected_super);
 651                                return ret;
 652                        }
 653                }
 654        }
 655
 656        if (NULL == state->latest_superblock) {
 657                pr_info("btrfsic: no superblock found!\n");
 658                kfree(selected_super);
 659                return -1;
 660        }
 661
 662        for (pass = 0; pass < 3; pass++) {
 663                int num_copies;
 664                int mirror_num;
 665                u64 next_bytenr;
 666
 667                switch (pass) {
 668                case 0:
 669                        next_bytenr = btrfs_super_root(selected_super);
 670                        if (state->print_mask &
 671                            BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
 672                                pr_info("root@%llu\n", next_bytenr);
 673                        break;
 674                case 1:
 675                        next_bytenr = btrfs_super_chunk_root(selected_super);
 676                        if (state->print_mask &
 677                            BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
 678                                pr_info("chunk@%llu\n", next_bytenr);
 679                        break;
 680                case 2:
 681                        next_bytenr = btrfs_super_log_root(selected_super);
 682                        if (0 == next_bytenr)
 683                                continue;
 684                        if (state->print_mask &
 685                            BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
 686                                pr_info("log@%llu\n", next_bytenr);
 687                        break;
 688                }
 689
 690                num_copies = btrfs_num_copies(state->fs_info, next_bytenr,
 691                                              state->metablock_size);
 692                if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
 693                        pr_info("num_copies(log_bytenr=%llu) = %d\n",
 694                               next_bytenr, num_copies);
 695
 696                for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
 697                        struct btrfsic_block *next_block;
 698                        struct btrfsic_block_data_ctx tmp_next_block_ctx;
 699                        struct btrfsic_block_link *l;
 700
 701                        ret = btrfsic_map_block(state, next_bytenr,
 702                                                state->metablock_size,
 703                                                &tmp_next_block_ctx,
 704                                                mirror_num);
 705                        if (ret) {
 706                                pr_info("btrfsic: btrfsic_map_block(root @%llu, mirror %d) failed!\n",
 707                                       next_bytenr, mirror_num);
 708                                kfree(selected_super);
 709                                return -1;
 710                        }
 711
 712                        next_block = btrfsic_block_hashtable_lookup(
 713                                        tmp_next_block_ctx.dev->bdev,
 714                                        tmp_next_block_ctx.dev_bytenr,
 715                                        &state->block_hashtable);
 716                        BUG_ON(NULL == next_block);
 717
 718                        l = btrfsic_block_link_hashtable_lookup(
 719                                        tmp_next_block_ctx.dev->bdev,
 720                                        tmp_next_block_ctx.dev_bytenr,
 721                                        state->latest_superblock->dev_state->
 722                                        bdev,
 723                                        state->latest_superblock->dev_bytenr,
 724                                        &state->block_link_hashtable);
 725                        BUG_ON(NULL == l);
 726
 727                        ret = btrfsic_read_block(state, &tmp_next_block_ctx);
 728                        if (ret < (int)PAGE_SIZE) {
 729                                pr_info("btrfsic: read @logical %llu failed!\n",
 730                                       tmp_next_block_ctx.start);
 731                                btrfsic_release_block_ctx(&tmp_next_block_ctx);
 732                                kfree(selected_super);
 733                                return -1;
 734                        }
 735
 736                        ret = btrfsic_process_metablock(state,
 737                                                        next_block,
 738                                                        &tmp_next_block_ctx,
 739                                                        BTRFS_MAX_LEVEL + 3, 1);
 740                        btrfsic_release_block_ctx(&tmp_next_block_ctx);
 741                }
 742        }
 743
 744        kfree(selected_super);
 745        return ret;
 746}
 747
 748static int btrfsic_process_superblock_dev_mirror(
 749                struct btrfsic_state *state,
 750                struct btrfsic_dev_state *dev_state,
 751                struct btrfs_device *device,
 752                int superblock_mirror_num,
 753                struct btrfsic_dev_state **selected_dev_state,
 754                struct btrfs_super_block *selected_super)
 755{
 756        struct btrfs_fs_info *fs_info = state->fs_info;
 757        struct btrfs_super_block *super_tmp;
 758        u64 dev_bytenr;
 759        struct btrfsic_block *superblock_tmp;
 760        int pass;
 761        struct block_device *const superblock_bdev = device->bdev;
 762        struct page *page;
 763        struct address_space *mapping = superblock_bdev->bd_inode->i_mapping;
 764        int ret = 0;
 765
 766        /* super block bytenr is always the unmapped device bytenr */
 767        dev_bytenr = btrfs_sb_offset(superblock_mirror_num);
 768        if (dev_bytenr + BTRFS_SUPER_INFO_SIZE > device->commit_total_bytes)
 769                return -1;
 770
 771        page = read_cache_page_gfp(mapping, dev_bytenr >> PAGE_SHIFT, GFP_NOFS);
 772        if (IS_ERR(page))
 773                return -1;
 774
 775        super_tmp = page_address(page);
 776
 777        if (btrfs_super_bytenr(super_tmp) != dev_bytenr ||
 778            btrfs_super_magic(super_tmp) != BTRFS_MAGIC ||
 779            memcmp(device->uuid, super_tmp->dev_item.uuid, BTRFS_UUID_SIZE) ||
 780            btrfs_super_nodesize(super_tmp) != state->metablock_size ||
 781            btrfs_super_sectorsize(super_tmp) != state->datablock_size) {
 782                ret = 0;
 783                goto out;
 784        }
 785
 786        superblock_tmp =
 787            btrfsic_block_hashtable_lookup(superblock_bdev,
 788                                           dev_bytenr,
 789                                           &state->block_hashtable);
 790        if (NULL == superblock_tmp) {
 791                superblock_tmp = btrfsic_block_alloc();
 792                if (NULL == superblock_tmp) {
 793                        ret = -1;
 794                        goto out;
 795                }
 796                /* for superblock, only the dev_bytenr makes sense */
 797                superblock_tmp->dev_bytenr = dev_bytenr;
 798                superblock_tmp->dev_state = dev_state;
 799                superblock_tmp->logical_bytenr = dev_bytenr;
 800                superblock_tmp->generation = btrfs_super_generation(super_tmp);
 801                superblock_tmp->is_metadata = 1;
 802                superblock_tmp->is_superblock = 1;
 803                superblock_tmp->is_iodone = 1;
 804                superblock_tmp->never_written = 0;
 805                superblock_tmp->mirror_num = 1 + superblock_mirror_num;
 806                if (state->print_mask & BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE)
 807                        btrfs_info_in_rcu(fs_info,
 808                                "new initial S-block (bdev %p, %s) @%llu (%s/%llu/%d)",
 809                                     superblock_bdev,
 810                                     rcu_str_deref(device->name), dev_bytenr,
 811                                     dev_state->name, dev_bytenr,
 812                                     superblock_mirror_num);
 813                list_add(&superblock_tmp->all_blocks_node,
 814                         &state->all_blocks_list);
 815                btrfsic_block_hashtable_add(superblock_tmp,
 816                                            &state->block_hashtable);
 817        }
 818
 819        /* select the one with the highest generation field */
 820        if (btrfs_super_generation(super_tmp) >
 821            state->max_superblock_generation ||
 822            0 == state->max_superblock_generation) {
 823                memcpy(selected_super, super_tmp, sizeof(*selected_super));
 824                *selected_dev_state = dev_state;
 825                state->max_superblock_generation =
 826                    btrfs_super_generation(super_tmp);
 827                state->latest_superblock = superblock_tmp;
 828        }
 829
 830        for (pass = 0; pass < 3; pass++) {
 831                u64 next_bytenr;
 832                int num_copies;
 833                int mirror_num;
 834                const char *additional_string = NULL;
 835                struct btrfs_disk_key tmp_disk_key;
 836
 837                tmp_disk_key.type = BTRFS_ROOT_ITEM_KEY;
 838                tmp_disk_key.offset = 0;
 839                switch (pass) {
 840                case 0:
 841                        btrfs_set_disk_key_objectid(&tmp_disk_key,
 842                                                    BTRFS_ROOT_TREE_OBJECTID);
 843                        additional_string = "initial root ";
 844                        next_bytenr = btrfs_super_root(super_tmp);
 845                        break;
 846                case 1:
 847                        btrfs_set_disk_key_objectid(&tmp_disk_key,
 848                                                    BTRFS_CHUNK_TREE_OBJECTID);
 849                        additional_string = "initial chunk ";
 850                        next_bytenr = btrfs_super_chunk_root(super_tmp);
 851                        break;
 852                case 2:
 853                        btrfs_set_disk_key_objectid(&tmp_disk_key,
 854                                                    BTRFS_TREE_LOG_OBJECTID);
 855                        additional_string = "initial log ";
 856                        next_bytenr = btrfs_super_log_root(super_tmp);
 857                        if (0 == next_bytenr)
 858                                continue;
 859                        break;
 860                }
 861
 862                num_copies = btrfs_num_copies(fs_info, next_bytenr,
 863                                              state->metablock_size);
 864                if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
 865                        pr_info("num_copies(log_bytenr=%llu) = %d\n",
 866                               next_bytenr, num_copies);
 867                for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
 868                        struct btrfsic_block *next_block;
 869                        struct btrfsic_block_data_ctx tmp_next_block_ctx;
 870                        struct btrfsic_block_link *l;
 871
 872                        if (btrfsic_map_block(state, next_bytenr,
 873                                              state->metablock_size,
 874                                              &tmp_next_block_ctx,
 875                                              mirror_num)) {
 876                                pr_info("btrfsic: btrfsic_map_block(bytenr @%llu, mirror %d) failed!\n",
 877                                       next_bytenr, mirror_num);
 878                                ret = -1;
 879                                goto out;
 880                        }
 881
 882                        next_block = btrfsic_block_lookup_or_add(
 883                                        state, &tmp_next_block_ctx,
 884                                        additional_string, 1, 1, 0,
 885                                        mirror_num, NULL);
 886                        if (NULL == next_block) {
 887                                btrfsic_release_block_ctx(&tmp_next_block_ctx);
 888                                ret = -1;
 889                                goto out;
 890                        }
 891
 892                        next_block->disk_key = tmp_disk_key;
 893                        next_block->generation = BTRFSIC_GENERATION_UNKNOWN;
 894                        l = btrfsic_block_link_lookup_or_add(
 895                                        state, &tmp_next_block_ctx,
 896                                        next_block, superblock_tmp,
 897                                        BTRFSIC_GENERATION_UNKNOWN);
 898                        btrfsic_release_block_ctx(&tmp_next_block_ctx);
 899                        if (NULL == l) {
 900                                ret = -1;
 901                                goto out;
 902                        }
 903                }
 904        }
 905        if (state->print_mask & BTRFSIC_PRINT_MASK_INITIAL_ALL_TREES)
 906                btrfsic_dump_tree_sub(state, superblock_tmp, 0);
 907
 908out:
 909        put_page(page);
 910        return ret;
 911}
 912
 913static struct btrfsic_stack_frame *btrfsic_stack_frame_alloc(void)
 914{
 915        struct btrfsic_stack_frame *sf;
 916
 917        sf = kzalloc(sizeof(*sf), GFP_NOFS);
 918        if (sf)
 919                sf->magic = BTRFSIC_BLOCK_STACK_FRAME_MAGIC_NUMBER;
 920        return sf;
 921}
 922
 923static void btrfsic_stack_frame_free(struct btrfsic_stack_frame *sf)
 924{
 925        BUG_ON(!(NULL == sf ||
 926                 BTRFSIC_BLOCK_STACK_FRAME_MAGIC_NUMBER == sf->magic));
 927        kfree(sf);
 928}
 929
 930static noinline_for_stack int btrfsic_process_metablock(
 931                struct btrfsic_state *state,
 932                struct btrfsic_block *const first_block,
 933                struct btrfsic_block_data_ctx *const first_block_ctx,
 934                int first_limit_nesting, int force_iodone_flag)
 935{
 936        struct btrfsic_stack_frame initial_stack_frame = { 0 };
 937        struct btrfsic_stack_frame *sf;
 938        struct btrfsic_stack_frame *next_stack;
 939        struct btrfs_header *const first_hdr =
 940                (struct btrfs_header *)first_block_ctx->datav[0];
 941
 942        BUG_ON(!first_hdr);
 943        sf = &initial_stack_frame;
 944        sf->error = 0;
 945        sf->i = -1;
 946        sf->limit_nesting = first_limit_nesting;
 947        sf->block = first_block;
 948        sf->block_ctx = first_block_ctx;
 949        sf->next_block = NULL;
 950        sf->hdr = first_hdr;
 951        sf->prev = NULL;
 952
 953continue_with_new_stack_frame:
 954        sf->block->generation = btrfs_stack_header_generation(sf->hdr);
 955        if (0 == sf->hdr->level) {
 956                struct btrfs_leaf *const leafhdr =
 957                    (struct btrfs_leaf *)sf->hdr;
 958
 959                if (-1 == sf->i) {
 960                        sf->nr = btrfs_stack_header_nritems(&leafhdr->header);
 961
 962                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
 963                                pr_info("leaf %llu items %d generation %llu owner %llu\n",
 964                                       sf->block_ctx->start, sf->nr,
 965                                       btrfs_stack_header_generation(
 966                                               &leafhdr->header),
 967                                       btrfs_stack_header_owner(
 968                                               &leafhdr->header));
 969                }
 970
 971continue_with_current_leaf_stack_frame:
 972                if (0 == sf->num_copies || sf->mirror_num > sf->num_copies) {
 973                        sf->i++;
 974                        sf->num_copies = 0;
 975                }
 976
 977                if (sf->i < sf->nr) {
 978                        struct btrfs_item disk_item;
 979                        u32 disk_item_offset =
 980                                (uintptr_t)(leafhdr->items + sf->i) -
 981                                (uintptr_t)leafhdr;
 982                        struct btrfs_disk_key *disk_key;
 983                        u8 type;
 984                        u32 item_offset;
 985                        u32 item_size;
 986
 987                        if (disk_item_offset + sizeof(struct btrfs_item) >
 988                            sf->block_ctx->len) {
 989leaf_item_out_of_bounce_error:
 990                                pr_info("btrfsic: leaf item out of bounce at logical %llu, dev %s\n",
 991                                       sf->block_ctx->start,
 992                                       sf->block_ctx->dev->name);
 993                                goto one_stack_frame_backwards;
 994                        }
 995                        btrfsic_read_from_block_data(sf->block_ctx,
 996                                                     &disk_item,
 997                                                     disk_item_offset,
 998                                                     sizeof(struct btrfs_item));
 999                        item_offset = btrfs_stack_item_offset(&disk_item);
1000                        item_size = btrfs_stack_item_size(&disk_item);
1001                        disk_key = &disk_item.key;
1002                        type = btrfs_disk_key_type(disk_key);
1003
1004                        if (BTRFS_ROOT_ITEM_KEY == type) {
1005                                struct btrfs_root_item root_item;
1006                                u32 root_item_offset;
1007                                u64 next_bytenr;
1008
1009                                root_item_offset = item_offset +
1010                                        offsetof(struct btrfs_leaf, items);
1011                                if (root_item_offset + item_size >
1012                                    sf->block_ctx->len)
1013                                        goto leaf_item_out_of_bounce_error;
1014                                btrfsic_read_from_block_data(
1015                                        sf->block_ctx, &root_item,
1016                                        root_item_offset,
1017                                        item_size);
1018                                next_bytenr = btrfs_root_bytenr(&root_item);
1019
1020                                sf->error =
1021                                    btrfsic_create_link_to_next_block(
1022                                                state,
1023                                                sf->block,
1024                                                sf->block_ctx,
1025                                                next_bytenr,
1026                                                sf->limit_nesting,
1027                                                &sf->next_block_ctx,
1028                                                &sf->next_block,
1029                                                force_iodone_flag,
1030                                                &sf->num_copies,
1031                                                &sf->mirror_num,
1032                                                disk_key,
1033                                                btrfs_root_generation(
1034                                                &root_item));
1035                                if (sf->error)
1036                                        goto one_stack_frame_backwards;
1037
1038                                if (NULL != sf->next_block) {
1039                                        struct btrfs_header *const next_hdr =
1040                                            (struct btrfs_header *)
1041                                            sf->next_block_ctx.datav[0];
1042
1043                                        next_stack =
1044                                            btrfsic_stack_frame_alloc();
1045                                        if (NULL == next_stack) {
1046                                                sf->error = -1;
1047                                                btrfsic_release_block_ctx(
1048                                                                &sf->
1049                                                                next_block_ctx);
1050                                                goto one_stack_frame_backwards;
1051                                        }
1052
1053                                        next_stack->i = -1;
1054                                        next_stack->block = sf->next_block;
1055                                        next_stack->block_ctx =
1056                                            &sf->next_block_ctx;
1057                                        next_stack->next_block = NULL;
1058                                        next_stack->hdr = next_hdr;
1059                                        next_stack->limit_nesting =
1060                                            sf->limit_nesting - 1;
1061                                        next_stack->prev = sf;
1062                                        sf = next_stack;
1063                                        goto continue_with_new_stack_frame;
1064                                }
1065                        } else if (BTRFS_EXTENT_DATA_KEY == type &&
1066                                   state->include_extent_data) {
1067                                sf->error = btrfsic_handle_extent_data(
1068                                                state,
1069                                                sf->block,
1070                                                sf->block_ctx,
1071                                                item_offset,
1072                                                force_iodone_flag);
1073                                if (sf->error)
1074                                        goto one_stack_frame_backwards;
1075                        }
1076
1077                        goto continue_with_current_leaf_stack_frame;
1078                }
1079        } else {
1080                struct btrfs_node *const nodehdr = (struct btrfs_node *)sf->hdr;
1081
1082                if (-1 == sf->i) {
1083                        sf->nr = btrfs_stack_header_nritems(&nodehdr->header);
1084
1085                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1086                                pr_info("node %llu level %d items %d generation %llu owner %llu\n",
1087                                       sf->block_ctx->start,
1088                                       nodehdr->header.level, sf->nr,
1089                                       btrfs_stack_header_generation(
1090                                       &nodehdr->header),
1091                                       btrfs_stack_header_owner(
1092                                       &nodehdr->header));
1093                }
1094
1095continue_with_current_node_stack_frame:
1096                if (0 == sf->num_copies || sf->mirror_num > sf->num_copies) {
1097                        sf->i++;
1098                        sf->num_copies = 0;
1099                }
1100
1101                if (sf->i < sf->nr) {
1102                        struct btrfs_key_ptr key_ptr;
1103                        u32 key_ptr_offset;
1104                        u64 next_bytenr;
1105
1106                        key_ptr_offset = (uintptr_t)(nodehdr->ptrs + sf->i) -
1107                                          (uintptr_t)nodehdr;
1108                        if (key_ptr_offset + sizeof(struct btrfs_key_ptr) >
1109                            sf->block_ctx->len) {
1110                                pr_info("btrfsic: node item out of bounce at logical %llu, dev %s\n",
1111                                       sf->block_ctx->start,
1112                                       sf->block_ctx->dev->name);
1113                                goto one_stack_frame_backwards;
1114                        }
1115                        btrfsic_read_from_block_data(
1116                                sf->block_ctx, &key_ptr, key_ptr_offset,
1117                                sizeof(struct btrfs_key_ptr));
1118                        next_bytenr = btrfs_stack_key_blockptr(&key_ptr);
1119
1120                        sf->error = btrfsic_create_link_to_next_block(
1121                                        state,
1122                                        sf->block,
1123                                        sf->block_ctx,
1124                                        next_bytenr,
1125                                        sf->limit_nesting,
1126                                        &sf->next_block_ctx,
1127                                        &sf->next_block,
1128                                        force_iodone_flag,
1129                                        &sf->num_copies,
1130                                        &sf->mirror_num,
1131                                        &key_ptr.key,
1132                                        btrfs_stack_key_generation(&key_ptr));
1133                        if (sf->error)
1134                                goto one_stack_frame_backwards;
1135
1136                        if (NULL != sf->next_block) {
1137                                struct btrfs_header *const next_hdr =
1138                                    (struct btrfs_header *)
1139                                    sf->next_block_ctx.datav[0];
1140
1141                                next_stack = btrfsic_stack_frame_alloc();
1142                                if (NULL == next_stack) {
1143                                        sf->error = -1;
1144                                        goto one_stack_frame_backwards;
1145                                }
1146
1147                                next_stack->i = -1;
1148                                next_stack->block = sf->next_block;
1149                                next_stack->block_ctx = &sf->next_block_ctx;
1150                                next_stack->next_block = NULL;
1151                                next_stack->hdr = next_hdr;
1152                                next_stack->limit_nesting =
1153                                    sf->limit_nesting - 1;
1154                                next_stack->prev = sf;
1155                                sf = next_stack;
1156                                goto continue_with_new_stack_frame;
1157                        }
1158
1159                        goto continue_with_current_node_stack_frame;
1160                }
1161        }
1162
1163one_stack_frame_backwards:
1164        if (NULL != sf->prev) {
1165                struct btrfsic_stack_frame *const prev = sf->prev;
1166
1167                /* the one for the initial block is freed in the caller */
1168                btrfsic_release_block_ctx(sf->block_ctx);
1169
1170                if (sf->error) {
1171                        prev->error = sf->error;
1172                        btrfsic_stack_frame_free(sf);
1173                        sf = prev;
1174                        goto one_stack_frame_backwards;
1175                }
1176
1177                btrfsic_stack_frame_free(sf);
1178                sf = prev;
1179                goto continue_with_new_stack_frame;
1180        } else {
1181                BUG_ON(&initial_stack_frame != sf);
1182        }
1183
1184        return sf->error;
1185}
1186
1187static void btrfsic_read_from_block_data(
1188        struct btrfsic_block_data_ctx *block_ctx,
1189        void *dstv, u32 offset, size_t len)
1190{
1191        size_t cur;
1192        size_t pgoff;
1193        char *kaddr;
1194        char *dst = (char *)dstv;
1195        size_t start_offset = offset_in_page(block_ctx->start);
1196        unsigned long i = (start_offset + offset) >> PAGE_SHIFT;
1197
1198        WARN_ON(offset + len > block_ctx->len);
1199        pgoff = offset_in_page(start_offset + offset);
1200
1201        while (len > 0) {
1202                cur = min(len, ((size_t)PAGE_SIZE - pgoff));
1203                BUG_ON(i >= DIV_ROUND_UP(block_ctx->len, PAGE_SIZE));
1204                kaddr = block_ctx->datav[i];
1205                memcpy(dst, kaddr + pgoff, cur);
1206
1207                dst += cur;
1208                len -= cur;
1209                pgoff = 0;
1210                i++;
1211        }
1212}
1213
1214static int btrfsic_create_link_to_next_block(
1215                struct btrfsic_state *state,
1216                struct btrfsic_block *block,
1217                struct btrfsic_block_data_ctx *block_ctx,
1218                u64 next_bytenr,
1219                int limit_nesting,
1220                struct btrfsic_block_data_ctx *next_block_ctx,
1221                struct btrfsic_block **next_blockp,
1222                int force_iodone_flag,
1223                int *num_copiesp, int *mirror_nump,
1224                struct btrfs_disk_key *disk_key,
1225                u64 parent_generation)
1226{
1227        struct btrfs_fs_info *fs_info = state->fs_info;
1228        struct btrfsic_block *next_block = NULL;
1229        int ret;
1230        struct btrfsic_block_link *l;
1231        int did_alloc_block_link;
1232        int block_was_created;
1233
1234        *next_blockp = NULL;
1235        if (0 == *num_copiesp) {
1236                *num_copiesp = btrfs_num_copies(fs_info, next_bytenr,
1237                                                state->metablock_size);
1238                if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
1239                        pr_info("num_copies(log_bytenr=%llu) = %d\n",
1240                               next_bytenr, *num_copiesp);
1241                *mirror_nump = 1;
1242        }
1243
1244        if (*mirror_nump > *num_copiesp)
1245                return 0;
1246
1247        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1248                pr_info("btrfsic_create_link_to_next_block(mirror_num=%d)\n",
1249                       *mirror_nump);
1250        ret = btrfsic_map_block(state, next_bytenr,
1251                                state->metablock_size,
1252                                next_block_ctx, *mirror_nump);
1253        if (ret) {
1254                pr_info("btrfsic: btrfsic_map_block(@%llu, mirror=%d) failed!\n",
1255                       next_bytenr, *mirror_nump);
1256                btrfsic_release_block_ctx(next_block_ctx);
1257                *next_blockp = NULL;
1258                return -1;
1259        }
1260
1261        next_block = btrfsic_block_lookup_or_add(state,
1262                                                 next_block_ctx, "referenced ",
1263                                                 1, force_iodone_flag,
1264                                                 !force_iodone_flag,
1265                                                 *mirror_nump,
1266                                                 &block_was_created);
1267        if (NULL == next_block) {
1268                btrfsic_release_block_ctx(next_block_ctx);
1269                *next_blockp = NULL;
1270                return -1;
1271        }
1272        if (block_was_created) {
1273                l = NULL;
1274                next_block->generation = BTRFSIC_GENERATION_UNKNOWN;
1275        } else {
1276                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE) {
1277                        if (next_block->logical_bytenr != next_bytenr &&
1278                            !(!next_block->is_metadata &&
1279                              0 == next_block->logical_bytenr))
1280                                pr_info("Referenced block @%llu (%s/%llu/%d) found in hash table, %c, bytenr mismatch (!= stored %llu).\n",
1281                                       next_bytenr, next_block_ctx->dev->name,
1282                                       next_block_ctx->dev_bytenr, *mirror_nump,
1283                                       btrfsic_get_block_type(state,
1284                                                              next_block),
1285                                       next_block->logical_bytenr);
1286                        else
1287                                pr_info("Referenced block @%llu (%s/%llu/%d) found in hash table, %c.\n",
1288                                       next_bytenr, next_block_ctx->dev->name,
1289                                       next_block_ctx->dev_bytenr, *mirror_nump,
1290                                       btrfsic_get_block_type(state,
1291                                                              next_block));
1292                }
1293                next_block->logical_bytenr = next_bytenr;
1294
1295                next_block->mirror_num = *mirror_nump;
1296                l = btrfsic_block_link_hashtable_lookup(
1297                                next_block_ctx->dev->bdev,
1298                                next_block_ctx->dev_bytenr,
1299                                block_ctx->dev->bdev,
1300                                block_ctx->dev_bytenr,
1301                                &state->block_link_hashtable);
1302        }
1303
1304        next_block->disk_key = *disk_key;
1305        if (NULL == l) {
1306                l = btrfsic_block_link_alloc();
1307                if (NULL == l) {
1308                        btrfsic_release_block_ctx(next_block_ctx);
1309                        *next_blockp = NULL;
1310                        return -1;
1311                }
1312
1313                did_alloc_block_link = 1;
1314                l->block_ref_to = next_block;
1315                l->block_ref_from = block;
1316                l->ref_cnt = 1;
1317                l->parent_generation = parent_generation;
1318
1319                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1320                        btrfsic_print_add_link(state, l);
1321
1322                list_add(&l->node_ref_to, &block->ref_to_list);
1323                list_add(&l->node_ref_from, &next_block->ref_from_list);
1324
1325                btrfsic_block_link_hashtable_add(l,
1326                                                 &state->block_link_hashtable);
1327        } else {
1328                did_alloc_block_link = 0;
1329                if (0 == limit_nesting) {
1330                        l->ref_cnt++;
1331                        l->parent_generation = parent_generation;
1332                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1333                                btrfsic_print_add_link(state, l);
1334                }
1335        }
1336
1337        if (limit_nesting > 0 && did_alloc_block_link) {
1338                ret = btrfsic_read_block(state, next_block_ctx);
1339                if (ret < (int)next_block_ctx->len) {
1340                        pr_info("btrfsic: read block @logical %llu failed!\n",
1341                               next_bytenr);
1342                        btrfsic_release_block_ctx(next_block_ctx);
1343                        *next_blockp = NULL;
1344                        return -1;
1345                }
1346
1347                *next_blockp = next_block;
1348        } else {
1349                *next_blockp = NULL;
1350        }
1351        (*mirror_nump)++;
1352
1353        return 0;
1354}
1355
1356static int btrfsic_handle_extent_data(
1357                struct btrfsic_state *state,
1358                struct btrfsic_block *block,
1359                struct btrfsic_block_data_ctx *block_ctx,
1360                u32 item_offset, int force_iodone_flag)
1361{
1362        struct btrfs_fs_info *fs_info = state->fs_info;
1363        struct btrfs_file_extent_item file_extent_item;
1364        u64 file_extent_item_offset;
1365        u64 next_bytenr;
1366        u64 num_bytes;
1367        u64 generation;
1368        struct btrfsic_block_link *l;
1369        int ret;
1370
1371        file_extent_item_offset = offsetof(struct btrfs_leaf, items) +
1372                                  item_offset;
1373        if (file_extent_item_offset +
1374            offsetof(struct btrfs_file_extent_item, disk_num_bytes) >
1375            block_ctx->len) {
1376                pr_info("btrfsic: file item out of bounce at logical %llu, dev %s\n",
1377                       block_ctx->start, block_ctx->dev->name);
1378                return -1;
1379        }
1380
1381        btrfsic_read_from_block_data(block_ctx, &file_extent_item,
1382                file_extent_item_offset,
1383                offsetof(struct btrfs_file_extent_item, disk_num_bytes));
1384        if (BTRFS_FILE_EXTENT_REG != file_extent_item.type ||
1385            btrfs_stack_file_extent_disk_bytenr(&file_extent_item) == 0) {
1386                if (state->print_mask & BTRFSIC_PRINT_MASK_VERY_VERBOSE)
1387                        pr_info("extent_data: type %u, disk_bytenr = %llu\n",
1388                               file_extent_item.type,
1389                               btrfs_stack_file_extent_disk_bytenr(
1390                               &file_extent_item));
1391                return 0;
1392        }
1393
1394        if (file_extent_item_offset + sizeof(struct btrfs_file_extent_item) >
1395            block_ctx->len) {
1396                pr_info("btrfsic: file item out of bounce at logical %llu, dev %s\n",
1397                       block_ctx->start, block_ctx->dev->name);
1398                return -1;
1399        }
1400        btrfsic_read_from_block_data(block_ctx, &file_extent_item,
1401                                     file_extent_item_offset,
1402                                     sizeof(struct btrfs_file_extent_item));
1403        next_bytenr = btrfs_stack_file_extent_disk_bytenr(&file_extent_item);
1404        if (btrfs_stack_file_extent_compression(&file_extent_item) ==
1405            BTRFS_COMPRESS_NONE) {
1406                next_bytenr += btrfs_stack_file_extent_offset(&file_extent_item);
1407                num_bytes = btrfs_stack_file_extent_num_bytes(&file_extent_item);
1408        } else {
1409                num_bytes = btrfs_stack_file_extent_disk_num_bytes(&file_extent_item);
1410        }
1411        generation = btrfs_stack_file_extent_generation(&file_extent_item);
1412
1413        if (state->print_mask & BTRFSIC_PRINT_MASK_VERY_VERBOSE)
1414                pr_info("extent_data: type %u, disk_bytenr = %llu, offset = %llu, num_bytes = %llu\n",
1415                       file_extent_item.type,
1416                       btrfs_stack_file_extent_disk_bytenr(&file_extent_item),
1417                       btrfs_stack_file_extent_offset(&file_extent_item),
1418                       num_bytes);
1419        while (num_bytes > 0) {
1420                u32 chunk_len;
1421                int num_copies;
1422                int mirror_num;
1423
1424                if (num_bytes > state->datablock_size)
1425                        chunk_len = state->datablock_size;
1426                else
1427                        chunk_len = num_bytes;
1428
1429                num_copies = btrfs_num_copies(fs_info, next_bytenr,
1430                                              state->datablock_size);
1431                if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
1432                        pr_info("num_copies(log_bytenr=%llu) = %d\n",
1433                               next_bytenr, num_copies);
1434                for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
1435                        struct btrfsic_block_data_ctx next_block_ctx;
1436                        struct btrfsic_block *next_block;
1437                        int block_was_created;
1438
1439                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1440                                pr_info("btrfsic_handle_extent_data(mirror_num=%d)\n",
1441                                        mirror_num);
1442                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERY_VERBOSE)
1443                                pr_info("\tdisk_bytenr = %llu, num_bytes %u\n",
1444                                       next_bytenr, chunk_len);
1445                        ret = btrfsic_map_block(state, next_bytenr,
1446                                                chunk_len, &next_block_ctx,
1447                                                mirror_num);
1448                        if (ret) {
1449                                pr_info("btrfsic: btrfsic_map_block(@%llu, mirror=%d) failed!\n",
1450                                       next_bytenr, mirror_num);
1451                                return -1;
1452                        }
1453
1454                        next_block = btrfsic_block_lookup_or_add(
1455                                        state,
1456                                        &next_block_ctx,
1457                                        "referenced ",
1458                                        0,
1459                                        force_iodone_flag,
1460                                        !force_iodone_flag,
1461                                        mirror_num,
1462                                        &block_was_created);
1463                        if (NULL == next_block) {
1464                                btrfsic_release_block_ctx(&next_block_ctx);
1465                                return -1;
1466                        }
1467                        if (!block_was_created) {
1468                                if ((state->print_mask &
1469                                     BTRFSIC_PRINT_MASK_VERBOSE) &&
1470                                    next_block->logical_bytenr != next_bytenr &&
1471                                    !(!next_block->is_metadata &&
1472                                      0 == next_block->logical_bytenr)) {
1473                                        pr_info("Referenced block @%llu (%s/%llu/%d) found in hash table, D, bytenr mismatch (!= stored %llu).\n",
1474                                               next_bytenr,
1475                                               next_block_ctx.dev->name,
1476                                               next_block_ctx.dev_bytenr,
1477                                               mirror_num,
1478                                               next_block->logical_bytenr);
1479                                }
1480                                next_block->logical_bytenr = next_bytenr;
1481                                next_block->mirror_num = mirror_num;
1482                        }
1483
1484                        l = btrfsic_block_link_lookup_or_add(state,
1485                                                             &next_block_ctx,
1486                                                             next_block, block,
1487                                                             generation);
1488                        btrfsic_release_block_ctx(&next_block_ctx);
1489                        if (NULL == l)
1490                                return -1;
1491                }
1492
1493                next_bytenr += chunk_len;
1494                num_bytes -= chunk_len;
1495        }
1496
1497        return 0;
1498}
1499
1500static int btrfsic_map_block(struct btrfsic_state *state, u64 bytenr, u32 len,
1501                             struct btrfsic_block_data_ctx *block_ctx_out,
1502                             int mirror_num)
1503{
1504        struct btrfs_fs_info *fs_info = state->fs_info;
1505        int ret;
1506        u64 length;
1507        struct btrfs_bio *multi = NULL;
1508        struct btrfs_device *device;
1509
1510        length = len;
1511        ret = btrfs_map_block(fs_info, BTRFS_MAP_READ,
1512                              bytenr, &length, &multi, mirror_num);
1513
1514        if (ret) {
1515                block_ctx_out->start = 0;
1516                block_ctx_out->dev_bytenr = 0;
1517                block_ctx_out->len = 0;
1518                block_ctx_out->dev = NULL;
1519                block_ctx_out->datav = NULL;
1520                block_ctx_out->pagev = NULL;
1521                block_ctx_out->mem_to_free = NULL;
1522
1523                return ret;
1524        }
1525
1526        device = multi->stripes[0].dev;
1527        if (test_bit(BTRFS_DEV_STATE_MISSING, &device->dev_state) ||
1528            !device->bdev || !device->name)
1529                block_ctx_out->dev = NULL;
1530        else
1531                block_ctx_out->dev = btrfsic_dev_state_lookup(
1532                                                        device->bdev->bd_dev);
1533        block_ctx_out->dev_bytenr = multi->stripes[0].physical;
1534        block_ctx_out->start = bytenr;
1535        block_ctx_out->len = len;
1536        block_ctx_out->datav = NULL;
1537        block_ctx_out->pagev = NULL;
1538        block_ctx_out->mem_to_free = NULL;
1539
1540        kfree(multi);
1541        if (NULL == block_ctx_out->dev) {
1542                ret = -ENXIO;
1543                pr_info("btrfsic: error, cannot lookup dev (#1)!\n");
1544        }
1545
1546        return ret;
1547}
1548
1549static void btrfsic_release_block_ctx(struct btrfsic_block_data_ctx *block_ctx)
1550{
1551        if (block_ctx->mem_to_free) {
1552                unsigned int num_pages;
1553
1554                BUG_ON(!block_ctx->datav);
1555                BUG_ON(!block_ctx->pagev);
1556                num_pages = (block_ctx->len + (u64)PAGE_SIZE - 1) >>
1557                            PAGE_SHIFT;
1558                /* Pages must be unmapped in reverse order */
1559                while (num_pages > 0) {
1560                        num_pages--;
1561                        if (block_ctx->datav[num_pages]) {
1562                                kunmap_local(block_ctx->datav[num_pages]);
1563                                block_ctx->datav[num_pages] = NULL;
1564                        }
1565                        if (block_ctx->pagev[num_pages]) {
1566                                __free_page(block_ctx->pagev[num_pages]);
1567                                block_ctx->pagev[num_pages] = NULL;
1568                        }
1569                }
1570
1571                kfree(block_ctx->mem_to_free);
1572                block_ctx->mem_to_free = NULL;
1573                block_ctx->pagev = NULL;
1574                block_ctx->datav = NULL;
1575        }
1576}
1577
1578static int btrfsic_read_block(struct btrfsic_state *state,
1579                              struct btrfsic_block_data_ctx *block_ctx)
1580{
1581        unsigned int num_pages;
1582        unsigned int i;
1583        size_t size;
1584        u64 dev_bytenr;
1585        int ret;
1586
1587        BUG_ON(block_ctx->datav);
1588        BUG_ON(block_ctx->pagev);
1589        BUG_ON(block_ctx->mem_to_free);
1590        if (!PAGE_ALIGNED(block_ctx->dev_bytenr)) {
1591                pr_info("btrfsic: read_block() with unaligned bytenr %llu\n",
1592                       block_ctx->dev_bytenr);
1593                return -1;
1594        }
1595
1596        num_pages = (block_ctx->len + (u64)PAGE_SIZE - 1) >>
1597                    PAGE_SHIFT;
1598        size = sizeof(*block_ctx->datav) + sizeof(*block_ctx->pagev);
1599        block_ctx->mem_to_free = kcalloc(num_pages, size, GFP_NOFS);
1600        if (!block_ctx->mem_to_free)
1601                return -ENOMEM;
1602        block_ctx->datav = block_ctx->mem_to_free;
1603        block_ctx->pagev = (struct page **)(block_ctx->datav + num_pages);
1604        for (i = 0; i < num_pages; i++) {
1605                block_ctx->pagev[i] = alloc_page(GFP_NOFS);
1606                if (!block_ctx->pagev[i])
1607                        return -1;
1608        }
1609
1610        dev_bytenr = block_ctx->dev_bytenr;
1611        for (i = 0; i < num_pages;) {
1612                struct bio *bio;
1613                unsigned int j;
1614
1615                bio = btrfs_io_bio_alloc(num_pages - i);
1616                bio_set_dev(bio, block_ctx->dev->bdev);
1617                bio->bi_iter.bi_sector = dev_bytenr >> 9;
1618                bio->bi_opf = REQ_OP_READ;
1619
1620                for (j = i; j < num_pages; j++) {
1621                        ret = bio_add_page(bio, block_ctx->pagev[j],
1622                                           PAGE_SIZE, 0);
1623                        if (PAGE_SIZE != ret)
1624                                break;
1625                }
1626                if (j == i) {
1627                        pr_info("btrfsic: error, failed to add a single page!\n");
1628                        return -1;
1629                }
1630                if (submit_bio_wait(bio)) {
1631                        pr_info("btrfsic: read error at logical %llu dev %s!\n",
1632                               block_ctx->start, block_ctx->dev->name);
1633                        bio_put(bio);
1634                        return -1;
1635                }
1636                bio_put(bio);
1637                dev_bytenr += (j - i) * PAGE_SIZE;
1638                i = j;
1639        }
1640        for (i = 0; i < num_pages; i++)
1641                block_ctx->datav[i] = kmap_local_page(block_ctx->pagev[i]);
1642
1643        return block_ctx->len;
1644}
1645
1646static void btrfsic_dump_database(struct btrfsic_state *state)
1647{
1648        const struct btrfsic_block *b_all;
1649
1650        BUG_ON(NULL == state);
1651
1652        pr_info("all_blocks_list:\n");
1653        list_for_each_entry(b_all, &state->all_blocks_list, all_blocks_node) {
1654                const struct btrfsic_block_link *l;
1655
1656                pr_info("%c-block @%llu (%s/%llu/%d)\n",
1657                       btrfsic_get_block_type(state, b_all),
1658                       b_all->logical_bytenr, b_all->dev_state->name,
1659                       b_all->dev_bytenr, b_all->mirror_num);
1660
1661                list_for_each_entry(l, &b_all->ref_to_list, node_ref_to) {
1662                        pr_info(" %c @%llu (%s/%llu/%d) refers %u* to %c @%llu (%s/%llu/%d)\n",
1663                               btrfsic_get_block_type(state, b_all),
1664                               b_all->logical_bytenr, b_all->dev_state->name,
1665                               b_all->dev_bytenr, b_all->mirror_num,
1666                               l->ref_cnt,
1667                               btrfsic_get_block_type(state, l->block_ref_to),
1668                               l->block_ref_to->logical_bytenr,
1669                               l->block_ref_to->dev_state->name,
1670                               l->block_ref_to->dev_bytenr,
1671                               l->block_ref_to->mirror_num);
1672                }
1673
1674                list_for_each_entry(l, &b_all->ref_from_list, node_ref_from) {
1675                        pr_info(" %c @%llu (%s/%llu/%d) is ref %u* from %c @%llu (%s/%llu/%d)\n",
1676                               btrfsic_get_block_type(state, b_all),
1677                               b_all->logical_bytenr, b_all->dev_state->name,
1678                               b_all->dev_bytenr, b_all->mirror_num,
1679                               l->ref_cnt,
1680                               btrfsic_get_block_type(state, l->block_ref_from),
1681                               l->block_ref_from->logical_bytenr,
1682                               l->block_ref_from->dev_state->name,
1683                               l->block_ref_from->dev_bytenr,
1684                               l->block_ref_from->mirror_num);
1685                }
1686
1687                pr_info("\n");
1688        }
1689}
1690
1691/*
1692 * Test whether the disk block contains a tree block (leaf or node)
1693 * (note that this test fails for the super block)
1694 */
1695static noinline_for_stack int btrfsic_test_for_metadata(
1696                struct btrfsic_state *state,
1697                char **datav, unsigned int num_pages)
1698{
1699        struct btrfs_fs_info *fs_info = state->fs_info;
1700        SHASH_DESC_ON_STACK(shash, fs_info->csum_shash);
1701        struct btrfs_header *h;
1702        u8 csum[BTRFS_CSUM_SIZE];
1703        unsigned int i;
1704
1705        if (num_pages * PAGE_SIZE < state->metablock_size)
1706                return 1; /* not metadata */
1707        num_pages = state->metablock_size >> PAGE_SHIFT;
1708        h = (struct btrfs_header *)datav[0];
1709
1710        if (memcmp(h->fsid, fs_info->fs_devices->fsid, BTRFS_FSID_SIZE))
1711                return 1;
1712
1713        shash->tfm = fs_info->csum_shash;
1714        crypto_shash_init(shash);
1715
1716        for (i = 0; i < num_pages; i++) {
1717                u8 *data = i ? datav[i] : (datav[i] + BTRFS_CSUM_SIZE);
1718                size_t sublen = i ? PAGE_SIZE :
1719                                    (PAGE_SIZE - BTRFS_CSUM_SIZE);
1720
1721                crypto_shash_update(shash, data, sublen);
1722        }
1723        crypto_shash_final(shash, csum);
1724        if (memcmp(csum, h->csum, fs_info->csum_size))
1725                return 1;
1726
1727        return 0; /* is metadata */
1728}
1729
1730static void btrfsic_process_written_block(struct btrfsic_dev_state *dev_state,
1731                                          u64 dev_bytenr, char **mapped_datav,
1732                                          unsigned int num_pages,
1733                                          struct bio *bio, int *bio_is_patched,
1734                                          int submit_bio_bh_rw)
1735{
1736        int is_metadata;
1737        struct btrfsic_block *block;
1738        struct btrfsic_block_data_ctx block_ctx;
1739        int ret;
1740        struct btrfsic_state *state = dev_state->state;
1741        struct block_device *bdev = dev_state->bdev;
1742        unsigned int processed_len;
1743
1744        if (NULL != bio_is_patched)
1745                *bio_is_patched = 0;
1746
1747again:
1748        if (num_pages == 0)
1749                return;
1750
1751        processed_len = 0;
1752        is_metadata = (0 == btrfsic_test_for_metadata(state, mapped_datav,
1753                                                      num_pages));
1754
1755        block = btrfsic_block_hashtable_lookup(bdev, dev_bytenr,
1756                                               &state->block_hashtable);
1757        if (NULL != block) {
1758                u64 bytenr = 0;
1759                struct btrfsic_block_link *l, *tmp;
1760
1761                if (block->is_superblock) {
1762                        bytenr = btrfs_super_bytenr((struct btrfs_super_block *)
1763                                                    mapped_datav[0]);
1764                        if (num_pages * PAGE_SIZE <
1765                            BTRFS_SUPER_INFO_SIZE) {
1766                                pr_info("btrfsic: cannot work with too short bios!\n");
1767                                return;
1768                        }
1769                        is_metadata = 1;
1770                        BUG_ON(!PAGE_ALIGNED(BTRFS_SUPER_INFO_SIZE));
1771                        processed_len = BTRFS_SUPER_INFO_SIZE;
1772                        if (state->print_mask &
1773                            BTRFSIC_PRINT_MASK_TREE_BEFORE_SB_WRITE) {
1774                                pr_info("[before new superblock is written]:\n");
1775                                btrfsic_dump_tree_sub(state, block, 0);
1776                        }
1777                }
1778                if (is_metadata) {
1779                        if (!block->is_superblock) {
1780                                if (num_pages * PAGE_SIZE <
1781                                    state->metablock_size) {
1782                                        pr_info("btrfsic: cannot work with too short bios!\n");
1783                                        return;
1784                                }
1785                                processed_len = state->metablock_size;
1786                                bytenr = btrfs_stack_header_bytenr(
1787                                                (struct btrfs_header *)
1788                                                mapped_datav[0]);
1789                                btrfsic_cmp_log_and_dev_bytenr(state, bytenr,
1790                                                               dev_state,
1791                                                               dev_bytenr);
1792                        }
1793                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE) {
1794                                if (block->logical_bytenr != bytenr &&
1795                                    !(!block->is_metadata &&
1796                                      block->logical_bytenr == 0))
1797                                        pr_info("Written block @%llu (%s/%llu/%d) found in hash table, %c, bytenr mismatch (!= stored %llu).\n",
1798                                               bytenr, dev_state->name,
1799                                               dev_bytenr,
1800                                               block->mirror_num,
1801                                               btrfsic_get_block_type(state,
1802                                                                      block),
1803                                               block->logical_bytenr);
1804                                else
1805                                        pr_info("Written block @%llu (%s/%llu/%d) found in hash table, %c.\n",
1806                                               bytenr, dev_state->name,
1807                                               dev_bytenr, block->mirror_num,
1808                                               btrfsic_get_block_type(state,
1809                                                                      block));
1810                        }
1811                        block->logical_bytenr = bytenr;
1812                } else {
1813                        if (num_pages * PAGE_SIZE <
1814                            state->datablock_size) {
1815                                pr_info("btrfsic: cannot work with too short bios!\n");
1816                                return;
1817                        }
1818                        processed_len = state->datablock_size;
1819                        bytenr = block->logical_bytenr;
1820                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1821                                pr_info("Written block @%llu (%s/%llu/%d) found in hash table, %c.\n",
1822                                       bytenr, dev_state->name, dev_bytenr,
1823                                       block->mirror_num,
1824                                       btrfsic_get_block_type(state, block));
1825                }
1826
1827                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1828                        pr_info("ref_to_list: %cE, ref_from_list: %cE\n",
1829                               list_empty(&block->ref_to_list) ? ' ' : '!',
1830                               list_empty(&block->ref_from_list) ? ' ' : '!');
1831                if (btrfsic_is_block_ref_by_superblock(state, block, 0)) {
1832                        pr_info("btrfs: attempt to overwrite %c-block @%llu (%s/%llu/%d), old(gen=%llu, objectid=%llu, type=%d, offset=%llu), new(gen=%llu), which is referenced by most recent superblock (superblockgen=%llu)!\n",
1833                               btrfsic_get_block_type(state, block), bytenr,
1834                               dev_state->name, dev_bytenr, block->mirror_num,
1835                               block->generation,
1836                               btrfs_disk_key_objectid(&block->disk_key),
1837                               block->disk_key.type,
1838                               btrfs_disk_key_offset(&block->disk_key),
1839                               btrfs_stack_header_generation(
1840                                       (struct btrfs_header *) mapped_datav[0]),
1841                               state->max_superblock_generation);
1842                        btrfsic_dump_tree(state);
1843                }
1844
1845                if (!block->is_iodone && !block->never_written) {
1846                        pr_info("btrfs: attempt to overwrite %c-block @%llu (%s/%llu/%d), oldgen=%llu, newgen=%llu, which is not yet iodone!\n",
1847                               btrfsic_get_block_type(state, block), bytenr,
1848                               dev_state->name, dev_bytenr, block->mirror_num,
1849                               block->generation,
1850                               btrfs_stack_header_generation(
1851                                       (struct btrfs_header *)
1852                                       mapped_datav[0]));
1853                        /* it would not be safe to go on */
1854                        btrfsic_dump_tree(state);
1855                        goto continue_loop;
1856                }
1857
1858                /*
1859                 * Clear all references of this block. Do not free
1860                 * the block itself even if is not referenced anymore
1861                 * because it still carries valuable information
1862                 * like whether it was ever written and IO completed.
1863                 */
1864                list_for_each_entry_safe(l, tmp, &block->ref_to_list,
1865                                         node_ref_to) {
1866                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1867                                btrfsic_print_rem_link(state, l);
1868                        l->ref_cnt--;
1869                        if (0 == l->ref_cnt) {
1870                                list_del(&l->node_ref_to);
1871                                list_del(&l->node_ref_from);
1872                                btrfsic_block_link_hashtable_remove(l);
1873                                btrfsic_block_link_free(l);
1874                        }
1875                }
1876
1877                block_ctx.dev = dev_state;
1878                block_ctx.dev_bytenr = dev_bytenr;
1879                block_ctx.start = bytenr;
1880                block_ctx.len = processed_len;
1881                block_ctx.pagev = NULL;
1882                block_ctx.mem_to_free = NULL;
1883                block_ctx.datav = mapped_datav;
1884
1885                if (is_metadata || state->include_extent_data) {
1886                        block->never_written = 0;
1887                        block->iodone_w_error = 0;
1888                        if (NULL != bio) {
1889                                block->is_iodone = 0;
1890                                BUG_ON(NULL == bio_is_patched);
1891                                if (!*bio_is_patched) {
1892                                        block->orig_bio_private =
1893                                            bio->bi_private;
1894                                        block->orig_bio_end_io =
1895                                            bio->bi_end_io;
1896                                        block->next_in_same_bio = NULL;
1897                                        bio->bi_private = block;
1898                                        bio->bi_end_io = btrfsic_bio_end_io;
1899                                        *bio_is_patched = 1;
1900                                } else {
1901                                        struct btrfsic_block *chained_block =
1902                                            (struct btrfsic_block *)
1903                                            bio->bi_private;
1904
1905                                        BUG_ON(NULL == chained_block);
1906                                        block->orig_bio_private =
1907                                            chained_block->orig_bio_private;
1908                                        block->orig_bio_end_io =
1909                                            chained_block->orig_bio_end_io;
1910                                        block->next_in_same_bio = chained_block;
1911                                        bio->bi_private = block;
1912                                }
1913                        } else {
1914                                block->is_iodone = 1;
1915                                block->orig_bio_private = NULL;
1916                                block->orig_bio_end_io = NULL;
1917                                block->next_in_same_bio = NULL;
1918                        }
1919                }
1920
1921                block->flush_gen = dev_state->last_flush_gen + 1;
1922                block->submit_bio_bh_rw = submit_bio_bh_rw;
1923                if (is_metadata) {
1924                        block->logical_bytenr = bytenr;
1925                        block->is_metadata = 1;
1926                        if (block->is_superblock) {
1927                                BUG_ON(PAGE_SIZE !=
1928                                       BTRFS_SUPER_INFO_SIZE);
1929                                ret = btrfsic_process_written_superblock(
1930                                                state,
1931                                                block,
1932                                                (struct btrfs_super_block *)
1933                                                mapped_datav[0]);
1934                                if (state->print_mask &
1935                                    BTRFSIC_PRINT_MASK_TREE_AFTER_SB_WRITE) {
1936                                        pr_info("[after new superblock is written]:\n");
1937                                        btrfsic_dump_tree_sub(state, block, 0);
1938                                }
1939                        } else {
1940                                block->mirror_num = 0;  /* unknown */
1941                                ret = btrfsic_process_metablock(
1942                                                state,
1943                                                block,
1944                                                &block_ctx,
1945                                                0, 0);
1946                        }
1947                        if (ret)
1948                                pr_info("btrfsic: btrfsic_process_metablock(root @%llu) failed!\n",
1949                                       dev_bytenr);
1950                } else {
1951                        block->is_metadata = 0;
1952                        block->mirror_num = 0;  /* unknown */
1953                        block->generation = BTRFSIC_GENERATION_UNKNOWN;
1954                        if (!state->include_extent_data
1955                            && list_empty(&block->ref_from_list)) {
1956                                /*
1957                                 * disk block is overwritten with extent
1958                                 * data (not meta data) and we are configured
1959                                 * to not include extent data: take the
1960                                 * chance and free the block's memory
1961                                 */
1962                                btrfsic_block_hashtable_remove(block);
1963                                list_del(&block->all_blocks_node);
1964                                btrfsic_block_free(block);
1965                        }
1966                }
1967                btrfsic_release_block_ctx(&block_ctx);
1968        } else {
1969                /* block has not been found in hash table */
1970                u64 bytenr;
1971
1972                if (!is_metadata) {
1973                        processed_len = state->datablock_size;
1974                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1975                                pr_info("Written block (%s/%llu/?) !found in hash table, D.\n",
1976                                       dev_state->name, dev_bytenr);
1977                        if (!state->include_extent_data) {
1978                                /* ignore that written D block */
1979                                goto continue_loop;
1980                        }
1981
1982                        /* this is getting ugly for the
1983                         * include_extent_data case... */
1984                        bytenr = 0;     /* unknown */
1985                } else {
1986                        processed_len = state->metablock_size;
1987                        bytenr = btrfs_stack_header_bytenr(
1988                                        (struct btrfs_header *)
1989                                        mapped_datav[0]);
1990                        btrfsic_cmp_log_and_dev_bytenr(state, bytenr, dev_state,
1991                                                       dev_bytenr);
1992                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1993                                pr_info("Written block @%llu (%s/%llu/?) !found in hash table, M.\n",
1994                                       bytenr, dev_state->name, dev_bytenr);
1995                }
1996
1997                block_ctx.dev = dev_state;
1998                block_ctx.dev_bytenr = dev_bytenr;
1999                block_ctx.start = bytenr;
2000                block_ctx.len = processed_len;
2001                block_ctx.pagev = NULL;
2002                block_ctx.mem_to_free = NULL;
2003                block_ctx.datav = mapped_datav;
2004
2005                block = btrfsic_block_alloc();
2006                if (NULL == block) {
2007                        btrfsic_release_block_ctx(&block_ctx);
2008                        goto continue_loop;
2009                }
2010                block->dev_state = dev_state;
2011                block->dev_bytenr = dev_bytenr;
2012                block->logical_bytenr = bytenr;
2013                block->is_metadata = is_metadata;
2014                block->never_written = 0;
2015                block->iodone_w_error = 0;
2016                block->mirror_num = 0;  /* unknown */
2017                block->flush_gen = dev_state->last_flush_gen + 1;
2018                block->submit_bio_bh_rw = submit_bio_bh_rw;
2019                if (NULL != bio) {
2020                        block->is_iodone = 0;
2021                        BUG_ON(NULL == bio_is_patched);
2022                        if (!*bio_is_patched) {
2023                                block->orig_bio_private = bio->bi_private;
2024                                block->orig_bio_end_io = bio->bi_end_io;
2025                                block->next_in_same_bio = NULL;
2026                                bio->bi_private = block;
2027                                bio->bi_end_io = btrfsic_bio_end_io;
2028                                *bio_is_patched = 1;
2029                        } else {
2030                                struct btrfsic_block *chained_block =
2031                                    (struct btrfsic_block *)
2032                                    bio->bi_private;
2033
2034                                BUG_ON(NULL == chained_block);
2035                                block->orig_bio_private =
2036                                    chained_block->orig_bio_private;
2037                                block->orig_bio_end_io =
2038                                    chained_block->orig_bio_end_io;
2039                                block->next_in_same_bio = chained_block;
2040                                bio->bi_private = block;
2041                        }
2042                } else {
2043                        block->is_iodone = 1;
2044                        block->orig_bio_private = NULL;
2045                        block->orig_bio_end_io = NULL;
2046                        block->next_in_same_bio = NULL;
2047                }
2048                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2049                        pr_info("New written %c-block @%llu (%s/%llu/%d)\n",
2050                               is_metadata ? 'M' : 'D',
2051                               block->logical_bytenr, block->dev_state->name,
2052                               block->dev_bytenr, block->mirror_num);
2053                list_add(&block->all_blocks_node, &state->all_blocks_list);
2054                btrfsic_block_hashtable_add(block, &state->block_hashtable);
2055
2056                if (is_metadata) {
2057                        ret = btrfsic_process_metablock(state, block,
2058                                                        &block_ctx, 0, 0);
2059                        if (ret)
2060                                pr_info("btrfsic: process_metablock(root @%llu) failed!\n",
2061                                       dev_bytenr);
2062                }
2063                btrfsic_release_block_ctx(&block_ctx);
2064        }
2065
2066continue_loop:
2067        BUG_ON(!processed_len);
2068        dev_bytenr += processed_len;
2069        mapped_datav += processed_len >> PAGE_SHIFT;
2070        num_pages -= processed_len >> PAGE_SHIFT;
2071        goto again;
2072}
2073
2074static void btrfsic_bio_end_io(struct bio *bp)
2075{
2076        struct btrfsic_block *block = (struct btrfsic_block *)bp->bi_private;
2077        int iodone_w_error;
2078
2079        /* mutex is not held! This is not save if IO is not yet completed
2080         * on umount */
2081        iodone_w_error = 0;
2082        if (bp->bi_status)
2083                iodone_w_error = 1;
2084
2085        BUG_ON(NULL == block);
2086        bp->bi_private = block->orig_bio_private;
2087        bp->bi_end_io = block->orig_bio_end_io;
2088
2089        do {
2090                struct btrfsic_block *next_block;
2091                struct btrfsic_dev_state *const dev_state = block->dev_state;
2092
2093                if ((dev_state->state->print_mask &
2094                     BTRFSIC_PRINT_MASK_END_IO_BIO_BH))
2095                        pr_info("bio_end_io(err=%d) for %c @%llu (%s/%llu/%d)\n",
2096                               bp->bi_status,
2097                               btrfsic_get_block_type(dev_state->state, block),
2098                               block->logical_bytenr, dev_state->name,
2099                               block->dev_bytenr, block->mirror_num);
2100                next_block = block->next_in_same_bio;
2101                block->iodone_w_error = iodone_w_error;
2102                if (block->submit_bio_bh_rw & REQ_PREFLUSH) {
2103                        dev_state->last_flush_gen++;
2104                        if ((dev_state->state->print_mask &
2105                             BTRFSIC_PRINT_MASK_END_IO_BIO_BH))
2106                                pr_info("bio_end_io() new %s flush_gen=%llu\n",
2107                                       dev_state->name,
2108                                       dev_state->last_flush_gen);
2109                }
2110                if (block->submit_bio_bh_rw & REQ_FUA)
2111                        block->flush_gen = 0; /* FUA completed means block is
2112                                               * on disk */
2113                block->is_iodone = 1; /* for FLUSH, this releases the block */
2114                block = next_block;
2115        } while (NULL != block);
2116
2117        bp->bi_end_io(bp);
2118}
2119
2120static int btrfsic_process_written_superblock(
2121                struct btrfsic_state *state,
2122                struct btrfsic_block *const superblock,
2123                struct btrfs_super_block *const super_hdr)
2124{
2125        struct btrfs_fs_info *fs_info = state->fs_info;
2126        int pass;
2127
2128        superblock->generation = btrfs_super_generation(super_hdr);
2129        if (!(superblock->generation > state->max_superblock_generation ||
2130              0 == state->max_superblock_generation)) {
2131                if (state->print_mask & BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE)
2132                        pr_info("btrfsic: superblock @%llu (%s/%llu/%d) with old gen %llu <= %llu\n",
2133                               superblock->logical_bytenr,
2134                               superblock->dev_state->name,
2135                               superblock->dev_bytenr, superblock->mirror_num,
2136                               btrfs_super_generation(super_hdr),
2137                               state->max_superblock_generation);
2138        } else {
2139                if (state->print_mask & BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE)
2140                        pr_info("btrfsic: got new superblock @%llu (%s/%llu/%d) with new gen %llu > %llu\n",
2141                               superblock->logical_bytenr,
2142                               superblock->dev_state->name,
2143                               superblock->dev_bytenr, superblock->mirror_num,
2144                               btrfs_super_generation(super_hdr),
2145                               state->max_superblock_generation);
2146
2147                state->max_superblock_generation =
2148                    btrfs_super_generation(super_hdr);
2149                state->latest_superblock = superblock;
2150        }
2151
2152        for (pass = 0; pass < 3; pass++) {
2153                int ret;
2154                u64 next_bytenr;
2155                struct btrfsic_block *next_block;
2156                struct btrfsic_block_data_ctx tmp_next_block_ctx;
2157                struct btrfsic_block_link *l;
2158                int num_copies;
2159                int mirror_num;
2160                const char *additional_string = NULL;
2161                struct btrfs_disk_key tmp_disk_key = {0};
2162
2163                btrfs_set_disk_key_objectid(&tmp_disk_key,
2164                                            BTRFS_ROOT_ITEM_KEY);
2165                btrfs_set_disk_key_objectid(&tmp_disk_key, 0);
2166
2167                switch (pass) {
2168                case 0:
2169                        btrfs_set_disk_key_objectid(&tmp_disk_key,
2170                                                    BTRFS_ROOT_TREE_OBJECTID);
2171                        additional_string = "root ";
2172                        next_bytenr = btrfs_super_root(super_hdr);
2173                        if (state->print_mask &
2174                            BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
2175                                pr_info("root@%llu\n", next_bytenr);
2176                        break;
2177                case 1:
2178                        btrfs_set_disk_key_objectid(&tmp_disk_key,
2179                                                    BTRFS_CHUNK_TREE_OBJECTID);
2180                        additional_string = "chunk ";
2181                        next_bytenr = btrfs_super_chunk_root(super_hdr);
2182                        if (state->print_mask &
2183                            BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
2184                                pr_info("chunk@%llu\n", next_bytenr);
2185                        break;
2186                case 2:
2187                        btrfs_set_disk_key_objectid(&tmp_disk_key,
2188                                                    BTRFS_TREE_LOG_OBJECTID);
2189                        additional_string = "log ";
2190                        next_bytenr = btrfs_super_log_root(super_hdr);
2191                        if (0 == next_bytenr)
2192                                continue;
2193                        if (state->print_mask &
2194                            BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
2195                                pr_info("log@%llu\n", next_bytenr);
2196                        break;
2197                }
2198
2199                num_copies = btrfs_num_copies(fs_info, next_bytenr,
2200                                              BTRFS_SUPER_INFO_SIZE);
2201                if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
2202                        pr_info("num_copies(log_bytenr=%llu) = %d\n",
2203                               next_bytenr, num_copies);
2204                for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
2205                        int was_created;
2206
2207                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2208                                pr_info("btrfsic_process_written_superblock(mirror_num=%d)\n", mirror_num);
2209                        ret = btrfsic_map_block(state, next_bytenr,
2210                                                BTRFS_SUPER_INFO_SIZE,
2211                                                &tmp_next_block_ctx,
2212                                                mirror_num);
2213                        if (ret) {
2214                                pr_info("btrfsic: btrfsic_map_block(@%llu, mirror=%d) failed!\n",
2215                                       next_bytenr, mirror_num);
2216                                return -1;
2217                        }
2218
2219                        next_block = btrfsic_block_lookup_or_add(
2220                                        state,
2221                                        &tmp_next_block_ctx,
2222                                        additional_string,
2223                                        1, 0, 1,
2224                                        mirror_num,
2225                                        &was_created);
2226                        if (NULL == next_block) {
2227                                btrfsic_release_block_ctx(&tmp_next_block_ctx);
2228                                return -1;
2229                        }
2230
2231                        next_block->disk_key = tmp_disk_key;
2232                        if (was_created)
2233                                next_block->generation =
2234                                    BTRFSIC_GENERATION_UNKNOWN;
2235                        l = btrfsic_block_link_lookup_or_add(
2236                                        state,
2237                                        &tmp_next_block_ctx,
2238                                        next_block,
2239                                        superblock,
2240                                        BTRFSIC_GENERATION_UNKNOWN);
2241                        btrfsic_release_block_ctx(&tmp_next_block_ctx);
2242                        if (NULL == l)
2243                                return -1;
2244                }
2245        }
2246
2247        if (WARN_ON(-1 == btrfsic_check_all_ref_blocks(state, superblock, 0)))
2248                btrfsic_dump_tree(state);
2249
2250        return 0;
2251}
2252
2253static int btrfsic_check_all_ref_blocks(struct btrfsic_state *state,
2254                                        struct btrfsic_block *const block,
2255                                        int recursion_level)
2256{
2257        const struct btrfsic_block_link *l;
2258        int ret = 0;
2259
2260        if (recursion_level >= 3 + BTRFS_MAX_LEVEL) {
2261                /*
2262                 * Note that this situation can happen and does not
2263                 * indicate an error in regular cases. It happens
2264                 * when disk blocks are freed and later reused.
2265                 * The check-integrity module is not aware of any
2266                 * block free operations, it just recognizes block
2267                 * write operations. Therefore it keeps the linkage
2268                 * information for a block until a block is
2269                 * rewritten. This can temporarily cause incorrect
2270                 * and even circular linkage information. This
2271                 * causes no harm unless such blocks are referenced
2272                 * by the most recent super block.
2273                 */
2274                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2275                        pr_info("btrfsic: abort cyclic linkage (case 1).\n");
2276
2277                return ret;
2278        }
2279
2280        /*
2281         * This algorithm is recursive because the amount of used stack
2282         * space is very small and the max recursion depth is limited.
2283         */
2284        list_for_each_entry(l, &block->ref_to_list, node_ref_to) {
2285                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2286                        pr_info("rl=%d, %c @%llu (%s/%llu/%d) %u* refers to %c @%llu (%s/%llu/%d)\n",
2287                               recursion_level,
2288                               btrfsic_get_block_type(state, block),
2289                               block->logical_bytenr, block->dev_state->name,
2290                               block->dev_bytenr, block->mirror_num,
2291                               l->ref_cnt,
2292                               btrfsic_get_block_type(state, l->block_ref_to),
2293                               l->block_ref_to->logical_bytenr,
2294                               l->block_ref_to->dev_state->name,
2295                               l->block_ref_to->dev_bytenr,
2296                               l->block_ref_to->mirror_num);
2297                if (l->block_ref_to->never_written) {
2298                        pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which is never written!\n",
2299                               btrfsic_get_block_type(state, l->block_ref_to),
2300                               l->block_ref_to->logical_bytenr,
2301                               l->block_ref_to->dev_state->name,
2302                               l->block_ref_to->dev_bytenr,
2303                               l->block_ref_to->mirror_num);
2304                        ret = -1;
2305                } else if (!l->block_ref_to->is_iodone) {
2306                        pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which is not yet iodone!\n",
2307                               btrfsic_get_block_type(state, l->block_ref_to),
2308                               l->block_ref_to->logical_bytenr,
2309                               l->block_ref_to->dev_state->name,
2310                               l->block_ref_to->dev_bytenr,
2311                               l->block_ref_to->mirror_num);
2312                        ret = -1;
2313                } else if (l->block_ref_to->iodone_w_error) {
2314                        pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which has write error!\n",
2315                               btrfsic_get_block_type(state, l->block_ref_to),
2316                               l->block_ref_to->logical_bytenr,
2317                               l->block_ref_to->dev_state->name,
2318                               l->block_ref_to->dev_bytenr,
2319                               l->block_ref_to->mirror_num);
2320                        ret = -1;
2321                } else if (l->parent_generation !=
2322                           l->block_ref_to->generation &&
2323                           BTRFSIC_GENERATION_UNKNOWN !=
2324                           l->parent_generation &&
2325                           BTRFSIC_GENERATION_UNKNOWN !=
2326                           l->block_ref_to->generation) {
2327                        pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) with generation %llu != parent generation %llu!\n",
2328                               btrfsic_get_block_type(state, l->block_ref_to),
2329                               l->block_ref_to->logical_bytenr,
2330                               l->block_ref_to->dev_state->name,
2331                               l->block_ref_to->dev_bytenr,
2332                               l->block_ref_to->mirror_num,
2333                               l->block_ref_to->generation,
2334                               l->parent_generation);
2335                        ret = -1;
2336                } else if (l->block_ref_to->flush_gen >
2337                           l->block_ref_to->dev_state->last_flush_gen) {
2338                        pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which is not flushed out of disk's write cache (block flush_gen=%llu, dev->flush_gen=%llu)!\n",
2339                               btrfsic_get_block_type(state, l->block_ref_to),
2340                               l->block_ref_to->logical_bytenr,
2341                               l->block_ref_to->dev_state->name,
2342                               l->block_ref_to->dev_bytenr,
2343                               l->block_ref_to->mirror_num, block->flush_gen,
2344                               l->block_ref_to->dev_state->last_flush_gen);
2345                        ret = -1;
2346                } else if (-1 == btrfsic_check_all_ref_blocks(state,
2347                                                              l->block_ref_to,
2348                                                              recursion_level +
2349                                                              1)) {
2350                        ret = -1;
2351                }
2352        }
2353
2354        return ret;
2355}
2356
2357static int btrfsic_is_block_ref_by_superblock(
2358                const struct btrfsic_state *state,
2359                const struct btrfsic_block *block,
2360                int recursion_level)
2361{
2362        const struct btrfsic_block_link *l;
2363
2364        if (recursion_level >= 3 + BTRFS_MAX_LEVEL) {
2365                /* refer to comment at "abort cyclic linkage (case 1)" */
2366                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2367                        pr_info("btrfsic: abort cyclic linkage (case 2).\n");
2368
2369                return 0;
2370        }
2371
2372        /*
2373         * This algorithm is recursive because the amount of used stack space
2374         * is very small and the max recursion depth is limited.
2375         */
2376        list_for_each_entry(l, &block->ref_from_list, node_ref_from) {
2377                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2378                        pr_info("rl=%d, %c @%llu (%s/%llu/%d) is ref %u* from %c @%llu (%s/%llu/%d)\n",
2379                               recursion_level,
2380                               btrfsic_get_block_type(state, block),
2381                               block->logical_bytenr, block->dev_state->name,
2382                               block->dev_bytenr, block->mirror_num,
2383                               l->ref_cnt,
2384                               btrfsic_get_block_type(state, l->block_ref_from),
2385                               l->block_ref_from->logical_bytenr,
2386                               l->block_ref_from->dev_state->name,
2387                               l->block_ref_from->dev_bytenr,
2388                               l->block_ref_from->mirror_num);
2389                if (l->block_ref_from->is_superblock &&
2390                    state->latest_superblock->dev_bytenr ==
2391                    l->block_ref_from->dev_bytenr &&
2392                    state->latest_superblock->dev_state->bdev ==
2393                    l->block_ref_from->dev_state->bdev)
2394                        return 1;
2395                else if (btrfsic_is_block_ref_by_superblock(state,
2396                                                            l->block_ref_from,
2397                                                            recursion_level +
2398                                                            1))
2399                        return 1;
2400        }
2401
2402        return 0;
2403}
2404
2405static void btrfsic_print_add_link(const struct btrfsic_state *state,
2406                                   const struct btrfsic_block_link *l)
2407{
2408        pr_info("Add %u* link from %c @%llu (%s/%llu/%d) to %c @%llu (%s/%llu/%d).\n",
2409               l->ref_cnt,
2410               btrfsic_get_block_type(state, l->block_ref_from),
2411               l->block_ref_from->logical_bytenr,
2412               l->block_ref_from->dev_state->name,
2413               l->block_ref_from->dev_bytenr, l->block_ref_from->mirror_num,
2414               btrfsic_get_block_type(state, l->block_ref_to),
2415               l->block_ref_to->logical_bytenr,
2416               l->block_ref_to->dev_state->name, l->block_ref_to->dev_bytenr,
2417               l->block_ref_to->mirror_num);
2418}
2419
2420static void btrfsic_print_rem_link(const struct btrfsic_state *state,
2421                                   const struct btrfsic_block_link *l)
2422{
2423        pr_info("Rem %u* link from %c @%llu (%s/%llu/%d) to %c @%llu (%s/%llu/%d).\n",
2424               l->ref_cnt,
2425               btrfsic_get_block_type(state, l->block_ref_from),
2426               l->block_ref_from->logical_bytenr,
2427               l->block_ref_from->dev_state->name,
2428               l->block_ref_from->dev_bytenr, l->block_ref_from->mirror_num,
2429               btrfsic_get_block_type(state, l->block_ref_to),
2430               l->block_ref_to->logical_bytenr,
2431               l->block_ref_to->dev_state->name, l->block_ref_to->dev_bytenr,
2432               l->block_ref_to->mirror_num);
2433}
2434
2435static char btrfsic_get_block_type(const struct btrfsic_state *state,
2436                                   const struct btrfsic_block *block)
2437{
2438        if (block->is_superblock &&
2439            state->latest_superblock->dev_bytenr == block->dev_bytenr &&
2440            state->latest_superblock->dev_state->bdev == block->dev_state->bdev)
2441                return 'S';
2442        else if (block->is_superblock)
2443                return 's';
2444        else if (block->is_metadata)
2445                return 'M';
2446        else
2447                return 'D';
2448}
2449
2450static void btrfsic_dump_tree(const struct btrfsic_state *state)
2451{
2452        btrfsic_dump_tree_sub(state, state->latest_superblock, 0);
2453}
2454
2455static void btrfsic_dump_tree_sub(const struct btrfsic_state *state,
2456                                  const struct btrfsic_block *block,
2457                                  int indent_level)
2458{
2459        const struct btrfsic_block_link *l;
2460        int indent_add;
2461        static char buf[80];
2462        int cursor_position;
2463
2464        /*
2465         * Should better fill an on-stack buffer with a complete line and
2466         * dump it at once when it is time to print a newline character.
2467         */
2468
2469        /*
2470         * This algorithm is recursive because the amount of used stack space
2471         * is very small and the max recursion depth is limited.
2472         */
2473        indent_add = sprintf(buf, "%c-%llu(%s/%llu/%u)",
2474                             btrfsic_get_block_type(state, block),
2475                             block->logical_bytenr, block->dev_state->name,
2476                             block->dev_bytenr, block->mirror_num);
2477        if (indent_level + indent_add > BTRFSIC_TREE_DUMP_MAX_INDENT_LEVEL) {
2478                printk("[...]\n");
2479                return;
2480        }
2481        printk(buf);
2482        indent_level += indent_add;
2483        if (list_empty(&block->ref_to_list)) {
2484                printk("\n");
2485                return;
2486        }
2487        if (block->mirror_num > 1 &&
2488            !(state->print_mask & BTRFSIC_PRINT_MASK_TREE_WITH_ALL_MIRRORS)) {
2489                printk(" [...]\n");
2490                return;
2491        }
2492
2493        cursor_position = indent_level;
2494        list_for_each_entry(l, &block->ref_to_list, node_ref_to) {
2495                while (cursor_position < indent_level) {
2496                        printk(" ");
2497                        cursor_position++;
2498                }
2499                if (l->ref_cnt > 1)
2500                        indent_add = sprintf(buf, " %d*--> ", l->ref_cnt);
2501                else
2502                        indent_add = sprintf(buf, " --> ");
2503                if (indent_level + indent_add >
2504                    BTRFSIC_TREE_DUMP_MAX_INDENT_LEVEL) {
2505                        printk("[...]\n");
2506                        cursor_position = 0;
2507                        continue;
2508                }
2509
2510                printk(buf);
2511
2512                btrfsic_dump_tree_sub(state, l->block_ref_to,
2513                                      indent_level + indent_add);
2514                cursor_position = 0;
2515        }
2516}
2517
2518static struct btrfsic_block_link *btrfsic_block_link_lookup_or_add(
2519                struct btrfsic_state *state,
2520                struct btrfsic_block_data_ctx *next_block_ctx,
2521                struct btrfsic_block *next_block,
2522                struct btrfsic_block *from_block,
2523                u64 parent_generation)
2524{
2525        struct btrfsic_block_link *l;
2526
2527        l = btrfsic_block_link_hashtable_lookup(next_block_ctx->dev->bdev,
2528                                                next_block_ctx->dev_bytenr,
2529                                                from_block->dev_state->bdev,
2530                                                from_block->dev_bytenr,
2531                                                &state->block_link_hashtable);
2532        if (NULL == l) {
2533                l = btrfsic_block_link_alloc();
2534                if (!l)
2535                        return NULL;
2536
2537                l->block_ref_to = next_block;
2538                l->block_ref_from = from_block;
2539                l->ref_cnt = 1;
2540                l->parent_generation = parent_generation;
2541
2542                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2543                        btrfsic_print_add_link(state, l);
2544
2545                list_add(&l->node_ref_to, &from_block->ref_to_list);
2546                list_add(&l->node_ref_from, &next_block->ref_from_list);
2547
2548                btrfsic_block_link_hashtable_add(l,
2549                                                 &state->block_link_hashtable);
2550        } else {
2551                l->ref_cnt++;
2552                l->parent_generation = parent_generation;
2553                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2554                        btrfsic_print_add_link(state, l);
2555        }
2556
2557        return l;
2558}
2559
2560static struct btrfsic_block *btrfsic_block_lookup_or_add(
2561                struct btrfsic_state *state,
2562                struct btrfsic_block_data_ctx *block_ctx,
2563                const char *additional_string,
2564                int is_metadata,
2565                int is_iodone,
2566                int never_written,
2567                int mirror_num,
2568                int *was_created)
2569{
2570        struct btrfsic_block *block;
2571
2572        block = btrfsic_block_hashtable_lookup(block_ctx->dev->bdev,
2573                                               block_ctx->dev_bytenr,
2574                                               &state->block_hashtable);
2575        if (NULL == block) {
2576                struct btrfsic_dev_state *dev_state;
2577
2578                block = btrfsic_block_alloc();
2579                if (!block)
2580                        return NULL;
2581
2582                dev_state = btrfsic_dev_state_lookup(block_ctx->dev->bdev->bd_dev);
2583                if (NULL == dev_state) {
2584                        pr_info("btrfsic: error, lookup dev_state failed!\n");
2585                        btrfsic_block_free(block);
2586                        return NULL;
2587                }
2588                block->dev_state = dev_state;
2589                block->dev_bytenr = block_ctx->dev_bytenr;
2590                block->logical_bytenr = block_ctx->start;
2591                block->is_metadata = is_metadata;
2592                block->is_iodone = is_iodone;
2593                block->never_written = never_written;
2594                block->mirror_num = mirror_num;
2595                if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2596                        pr_info("New %s%c-block @%llu (%s/%llu/%d)\n",
2597                               additional_string,
2598                               btrfsic_get_block_type(state, block),
2599                               block->logical_bytenr, dev_state->name,
2600                               block->dev_bytenr, mirror_num);
2601                list_add(&block->all_blocks_node, &state->all_blocks_list);
2602                btrfsic_block_hashtable_add(block, &state->block_hashtable);
2603                if (NULL != was_created)
2604                        *was_created = 1;
2605        } else {
2606                if (NULL != was_created)
2607                        *was_created = 0;
2608        }
2609
2610        return block;
2611}
2612
2613static void btrfsic_cmp_log_and_dev_bytenr(struct btrfsic_state *state,
2614                                           u64 bytenr,
2615                                           struct btrfsic_dev_state *dev_state,
2616                                           u64 dev_bytenr)
2617{
2618        struct btrfs_fs_info *fs_info = state->fs_info;
2619        struct btrfsic_block_data_ctx block_ctx;
2620        int num_copies;
2621        int mirror_num;
2622        int match = 0;
2623        int ret;
2624
2625        num_copies = btrfs_num_copies(fs_info, bytenr, state->metablock_size);
2626
2627        for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
2628                ret = btrfsic_map_block(state, bytenr, state->metablock_size,
2629                                        &block_ctx, mirror_num);
2630                if (ret) {
2631                        pr_info("btrfsic: btrfsic_map_block(logical @%llu, mirror %d) failed!\n",
2632                               bytenr, mirror_num);
2633                        continue;
2634                }
2635
2636                if (dev_state->bdev == block_ctx.dev->bdev &&
2637                    dev_bytenr == block_ctx.dev_bytenr) {
2638                        match++;
2639                        btrfsic_release_block_ctx(&block_ctx);
2640                        break;
2641                }
2642                btrfsic_release_block_ctx(&block_ctx);
2643        }
2644
2645        if (WARN_ON(!match)) {
2646                pr_info("btrfs: attempt to write M-block which contains logical bytenr that doesn't map to dev+physical bytenr of submit_bio, buffer->log_bytenr=%llu, submit_bio(bdev=%s, phys_bytenr=%llu)!\n",
2647                       bytenr, dev_state->name, dev_bytenr);
2648                for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
2649                        ret = btrfsic_map_block(state, bytenr,
2650                                                state->metablock_size,
2651                                                &block_ctx, mirror_num);
2652                        if (ret)
2653                                continue;
2654
2655                        pr_info("Read logical bytenr @%llu maps to (%s/%llu/%d)\n",
2656                               bytenr, block_ctx.dev->name,
2657                               block_ctx.dev_bytenr, mirror_num);
2658                }
2659        }
2660}
2661
2662static struct btrfsic_dev_state *btrfsic_dev_state_lookup(dev_t dev)
2663{
2664        return btrfsic_dev_state_hashtable_lookup(dev,
2665                                                  &btrfsic_dev_state_hashtable);
2666}
2667
2668static void __btrfsic_submit_bio(struct bio *bio)
2669{
2670        struct btrfsic_dev_state *dev_state;
2671
2672        if (!btrfsic_is_initialized)
2673                return;
2674
2675        mutex_lock(&btrfsic_mutex);
2676        /* since btrfsic_submit_bio() is also called before
2677         * btrfsic_mount(), this might return NULL */
2678        dev_state = btrfsic_dev_state_lookup(bio->bi_bdev->bd_dev);
2679        if (NULL != dev_state &&
2680            (bio_op(bio) == REQ_OP_WRITE) && bio_has_data(bio)) {
2681                int i = 0;
2682                u64 dev_bytenr;
2683                u64 cur_bytenr;
2684                struct bio_vec bvec;
2685                struct bvec_iter iter;
2686                int bio_is_patched;
2687                char **mapped_datav;
2688                unsigned int segs = bio_segments(bio);
2689
2690                dev_bytenr = 512 * bio->bi_iter.bi_sector;
2691                bio_is_patched = 0;
2692                if (dev_state->state->print_mask &
2693                    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH)
2694                        pr_info("submit_bio(rw=%d,0x%x, bi_vcnt=%u, bi_sector=%llu (bytenr %llu), bi_bdev=%p)\n",
2695                               bio_op(bio), bio->bi_opf, segs,
2696                               bio->bi_iter.bi_sector, dev_bytenr, bio->bi_bdev);
2697
2698                mapped_datav = kmalloc_array(segs,
2699                                             sizeof(*mapped_datav), GFP_NOFS);
2700                if (!mapped_datav)
2701                        goto leave;
2702                cur_bytenr = dev_bytenr;
2703
2704                bio_for_each_segment(bvec, bio, iter) {
2705                        BUG_ON(bvec.bv_len != PAGE_SIZE);
2706                        mapped_datav[i] = kmap_local_page(bvec.bv_page);
2707                        i++;
2708
2709                        if (dev_state->state->print_mask &
2710                            BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH_VERBOSE)
2711                                pr_info("#%u: bytenr=%llu, len=%u, offset=%u\n",
2712                                       i, cur_bytenr, bvec.bv_len, bvec.bv_offset);
2713                        cur_bytenr += bvec.bv_len;
2714                }
2715                btrfsic_process_written_block(dev_state, dev_bytenr,
2716                                              mapped_datav, segs,
2717                                              bio, &bio_is_patched,
2718                                              bio->bi_opf);
2719                /* Unmap in reverse order */
2720                for (--i; i >= 0; i--)
2721                        kunmap_local(mapped_datav[i]);
2722                kfree(mapped_datav);
2723        } else if (NULL != dev_state && (bio->bi_opf & REQ_PREFLUSH)) {
2724                if (dev_state->state->print_mask &
2725                    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH)
2726                        pr_info("submit_bio(rw=%d,0x%x FLUSH, bdev=%p)\n",
2727                               bio_op(bio), bio->bi_opf, bio->bi_bdev);
2728                if (!dev_state->dummy_block_for_bio_bh_flush.is_iodone) {
2729                        if ((dev_state->state->print_mask &
2730                             (BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH |
2731                              BTRFSIC_PRINT_MASK_VERBOSE)))
2732                                pr_info("btrfsic_submit_bio(%s) with FLUSH but dummy block already in use (ignored)!\n",
2733                                       dev_state->name);
2734                } else {
2735                        struct btrfsic_block *const block =
2736                                &dev_state->dummy_block_for_bio_bh_flush;
2737
2738                        block->is_iodone = 0;
2739                        block->never_written = 0;
2740                        block->iodone_w_error = 0;
2741                        block->flush_gen = dev_state->last_flush_gen + 1;
2742                        block->submit_bio_bh_rw = bio->bi_opf;
2743                        block->orig_bio_private = bio->bi_private;
2744                        block->orig_bio_end_io = bio->bi_end_io;
2745                        block->next_in_same_bio = NULL;
2746                        bio->bi_private = block;
2747                        bio->bi_end_io = btrfsic_bio_end_io;
2748                }
2749        }
2750leave:
2751        mutex_unlock(&btrfsic_mutex);
2752}
2753
2754void btrfsic_submit_bio(struct bio *bio)
2755{
2756        __btrfsic_submit_bio(bio);
2757        submit_bio(bio);
2758}
2759
2760int btrfsic_submit_bio_wait(struct bio *bio)
2761{
2762        __btrfsic_submit_bio(bio);
2763        return submit_bio_wait(bio);
2764}
2765
2766int btrfsic_mount(struct btrfs_fs_info *fs_info,
2767                  struct btrfs_fs_devices *fs_devices,
2768                  int including_extent_data, u32 print_mask)
2769{
2770        int ret;
2771        struct btrfsic_state *state;
2772        struct list_head *dev_head = &fs_devices->devices;
2773        struct btrfs_device *device;
2774
2775        if (!PAGE_ALIGNED(fs_info->nodesize)) {
2776                pr_info("btrfsic: cannot handle nodesize %d not being a multiple of PAGE_SIZE %ld!\n",
2777                       fs_info->nodesize, PAGE_SIZE);
2778                return -1;
2779        }
2780        if (!PAGE_ALIGNED(fs_info->sectorsize)) {
2781                pr_info("btrfsic: cannot handle sectorsize %d not being a multiple of PAGE_SIZE %ld!\n",
2782                       fs_info->sectorsize, PAGE_SIZE);
2783                return -1;
2784        }
2785        state = kvzalloc(sizeof(*state), GFP_KERNEL);
2786        if (!state)
2787                return -ENOMEM;
2788
2789        if (!btrfsic_is_initialized) {
2790                mutex_init(&btrfsic_mutex);
2791                btrfsic_dev_state_hashtable_init(&btrfsic_dev_state_hashtable);
2792                btrfsic_is_initialized = 1;
2793        }
2794        mutex_lock(&btrfsic_mutex);
2795        state->fs_info = fs_info;
2796        state->print_mask = print_mask;
2797        state->include_extent_data = including_extent_data;
2798        state->metablock_size = fs_info->nodesize;
2799        state->datablock_size = fs_info->sectorsize;
2800        INIT_LIST_HEAD(&state->all_blocks_list);
2801        btrfsic_block_hashtable_init(&state->block_hashtable);
2802        btrfsic_block_link_hashtable_init(&state->block_link_hashtable);
2803        state->max_superblock_generation = 0;
2804        state->latest_superblock = NULL;
2805
2806        list_for_each_entry(device, dev_head, dev_list) {
2807                struct btrfsic_dev_state *ds;
2808                const char *p;
2809
2810                if (!device->bdev || !device->name)
2811                        continue;
2812
2813                ds = btrfsic_dev_state_alloc();
2814                if (NULL == ds) {
2815                        mutex_unlock(&btrfsic_mutex);
2816                        return -ENOMEM;
2817                }
2818                ds->bdev = device->bdev;
2819                ds->state = state;
2820                bdevname(ds->bdev, ds->name);
2821                ds->name[BDEVNAME_SIZE - 1] = '\0';
2822                p = kbasename(ds->name);
2823                strlcpy(ds->name, p, sizeof(ds->name));
2824                btrfsic_dev_state_hashtable_add(ds,
2825                                                &btrfsic_dev_state_hashtable);
2826        }
2827
2828        ret = btrfsic_process_superblock(state, fs_devices);
2829        if (0 != ret) {
2830                mutex_unlock(&btrfsic_mutex);
2831                btrfsic_unmount(fs_devices);
2832                return ret;
2833        }
2834
2835        if (state->print_mask & BTRFSIC_PRINT_MASK_INITIAL_DATABASE)
2836                btrfsic_dump_database(state);
2837        if (state->print_mask & BTRFSIC_PRINT_MASK_INITIAL_TREE)
2838                btrfsic_dump_tree(state);
2839
2840        mutex_unlock(&btrfsic_mutex);
2841        return 0;
2842}
2843
2844void btrfsic_unmount(struct btrfs_fs_devices *fs_devices)
2845{
2846        struct btrfsic_block *b_all, *tmp_all;
2847        struct btrfsic_state *state;
2848        struct list_head *dev_head = &fs_devices->devices;
2849        struct btrfs_device *device;
2850
2851        if (!btrfsic_is_initialized)
2852                return;
2853
2854        mutex_lock(&btrfsic_mutex);
2855
2856        state = NULL;
2857        list_for_each_entry(device, dev_head, dev_list) {
2858                struct btrfsic_dev_state *ds;
2859
2860                if (!device->bdev || !device->name)
2861                        continue;
2862
2863                ds = btrfsic_dev_state_hashtable_lookup(
2864                                device->bdev->bd_dev,
2865                                &btrfsic_dev_state_hashtable);
2866                if (NULL != ds) {
2867                        state = ds->state;
2868                        btrfsic_dev_state_hashtable_remove(ds);
2869                        btrfsic_dev_state_free(ds);
2870                }
2871        }
2872
2873        if (NULL == state) {
2874                pr_info("btrfsic: error, cannot find state information on umount!\n");
2875                mutex_unlock(&btrfsic_mutex);
2876                return;
2877        }
2878
2879        /*
2880         * Don't care about keeping the lists' state up to date,
2881         * just free all memory that was allocated dynamically.
2882         * Free the blocks and the block_links.
2883         */
2884        list_for_each_entry_safe(b_all, tmp_all, &state->all_blocks_list,
2885                                 all_blocks_node) {
2886                struct btrfsic_block_link *l, *tmp;
2887
2888                list_for_each_entry_safe(l, tmp, &b_all->ref_to_list,
2889                                         node_ref_to) {
2890                        if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2891                                btrfsic_print_rem_link(state, l);
2892
2893                        l->ref_cnt--;
2894                        if (0 == l->ref_cnt)
2895                                btrfsic_block_link_free(l);
2896                }
2897
2898                if (b_all->is_iodone || b_all->never_written)
2899                        btrfsic_block_free(b_all);
2900                else
2901                        pr_info("btrfs: attempt to free %c-block @%llu (%s/%llu/%d) on umount which is not yet iodone!\n",
2902                               btrfsic_get_block_type(state, b_all),
2903                               b_all->logical_bytenr, b_all->dev_state->name,
2904                               b_all->dev_bytenr, b_all->mirror_num);
2905        }
2906
2907        mutex_unlock(&btrfsic_mutex);
2908
2909        kvfree(state);
2910}
2911