check-integrity.c 94.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
/*
 * Copyright (C) STRATO AG 2011.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License v2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 021110-1307, USA.
 */

/*
 * This module can be used to catch cases when the btrfs kernel
 * code executes write requests to the disk that bring the file
 * system in an inconsistent state. In such a state, a power-loss
 * or kernel panic event would cause that the data on disk is
 * lost or at least damaged.
 *
 * Code is added that examines all block write requests during
 * runtime (including writes of the super block). Three rules
 * are verified and an error is printed on violation of the
 * rules:
 * 1. It is not allowed to write a disk block which is
 *    currently referenced by the super block (either directly
 *    or indirectly).
 * 2. When a super block is written, it is verified that all
 *    referenced (directly or indirectly) blocks fulfill the
 *    following requirements:
 *    2a. All referenced blocks have either been present when
 *        the file system was mounted, (i.e., they have been
 *        referenced by the super block) or they have been
 *        written since then and the write completion callback
40 41 42
 *        was called and no write error was indicated and a
 *        FLUSH request to the device where these blocks are
 *        located was received and completed.
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
 *    2b. All referenced blocks need to have a generation
 *        number which is equal to the parent's number.
 *
 * One issue that was found using this module was that the log
 * tree on disk became temporarily corrupted because disk blocks
 * that had been in use for the log tree had been freed and
 * reused too early, while being referenced by the written super
 * block.
 *
 * The search term in the kernel log that can be used to filter
 * on the existence of detected integrity issues is
 * "btrfs: attempt".
 *
 * The integrity check is enabled via mount options. These
 * mount options are only supported if the integrity check
 * tool is compiled by defining BTRFS_FS_CHECK_INTEGRITY.
 *
 * Example #1, apply integrity checks to all metadata:
 * mount /dev/sdb1 /mnt -o check_int
 *
 * Example #2, apply integrity checks to all metadata and
 * to data extents:
 * mount /dev/sdb1 /mnt -o check_int_data
 *
 * Example #3, apply integrity checks to all metadata and dump
 * the tree that the super block references to kernel messages
 * each time after a super block was written:
 * mount /dev/sdb1 /mnt -o check_int,check_int_print_mask=263
 *
 * If the integrity check tool is included and activated in
 * the mount options, plenty of kernel memory is used, and
 * plenty of additional CPU cycles are spent. Enabling this
 * functionality is not intended for normal use. In most
 * cases, unless you are a btrfs developer who needs to verify
 * the integrity of (super)-block write requests, do not
 * enable the config option BTRFS_FS_CHECK_INTEGRITY to
 * include and compile the integrity check tool.
80 81 82 83 84 85 86 87 88
 *
 * Expect millions of lines of information in the kernel log with an
 * enabled check_int_print_mask. Therefore set LOG_BUF_SHIFT in the
 * kernel config to at least 26 (which is 64MB). Usually the value is
 * limited to 21 (which is 2MB) in init/Kconfig. The file needs to be
 * changed like this before LOG_BUF_SHIFT can be set to a high value:
 * config LOG_BUF_SHIFT
 *       int "Kernel log buffer size (16 => 64KB, 17 => 128KB)"
 *       range 12 30
89 90 91 92 93 94 95 96
 */

#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/buffer_head.h>
#include <linux/mutex.h>
#include <linux/genhd.h>
#include <linux/blkdev.h>
97
#include <linux/vmalloc.h>
98
#include <linux/string.h>
99 100
#include "ctree.h"
#include "disk-io.h"
101
#include "hash.h"
102 103 104 105 106 107
#include "transaction.h"
#include "extent_io.h"
#include "volumes.h"
#include "print-tree.h"
#include "locking.h"
#include "check-integrity.h"
108
#include "rcu-string.h"
109
#include "compression.h"
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

#define BTRFSIC_BLOCK_HASHTABLE_SIZE 0x10000
#define BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE 0x10000
#define BTRFSIC_DEV2STATE_HASHTABLE_SIZE 0x100
#define BTRFSIC_BLOCK_MAGIC_NUMBER 0x14491051
#define BTRFSIC_BLOCK_LINK_MAGIC_NUMBER 0x11070807
#define BTRFSIC_DEV2STATE_MAGIC_NUMBER 0x20111530
#define BTRFSIC_BLOCK_STACK_FRAME_MAGIC_NUMBER 20111300
#define BTRFSIC_TREE_DUMP_MAX_INDENT_LEVEL (200 - 6)	/* in characters,
							 * excluding " [...]" */
#define BTRFSIC_GENERATION_UNKNOWN ((u64)-1)

/*
 * The definition of the bitmask fields for the print_mask.
 * They are specified with the mount option check_integrity_print_mask.
 */
#define BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE			0x00000001
#define BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION		0x00000002
#define BTRFSIC_PRINT_MASK_TREE_AFTER_SB_WRITE			0x00000004
#define BTRFSIC_PRINT_MASK_TREE_BEFORE_SB_WRITE			0x00000008
#define BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH			0x00000010
#define BTRFSIC_PRINT_MASK_END_IO_BIO_BH			0x00000020
#define BTRFSIC_PRINT_MASK_VERBOSE				0x00000040
#define BTRFSIC_PRINT_MASK_VERY_VERBOSE				0x00000080
#define BTRFSIC_PRINT_MASK_INITIAL_TREE				0x00000100
#define BTRFSIC_PRINT_MASK_INITIAL_ALL_TREES			0x00000200
#define BTRFSIC_PRINT_MASK_INITIAL_DATABASE			0x00000400
#define BTRFSIC_PRINT_MASK_NUM_COPIES				0x00000800
#define BTRFSIC_PRINT_MASK_TREE_WITH_ALL_MIRRORS		0x00001000
139
#define BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH_VERBOSE		0x00002000
140 141 142 143 144 145 146 147 148 149 150 151 152

struct btrfsic_dev_state;
struct btrfsic_state;

struct btrfsic_block {
	u32 magic_num;		/* only used for debug purposes */
	unsigned int is_metadata:1;	/* if it is meta-data, not data-data */
	unsigned int is_superblock:1;	/* if it is one of the superblocks */
	unsigned int is_iodone:1;	/* if is done by lower subsystem */
	unsigned int iodone_w_error:1;	/* error was indicated to endio */
	unsigned int never_written:1;	/* block was added because it was
					 * referenced, not because it was
					 * written */
153
	unsigned int mirror_num;	/* large enough to hold
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
					 * BTRFS_SUPER_MIRROR_MAX */
	struct btrfsic_dev_state *dev_state;
	u64 dev_bytenr;		/* key, physical byte num on disk */
	u64 logical_bytenr;	/* logical byte num on disk */
	u64 generation;
	struct btrfs_disk_key disk_key;	/* extra info to print in case of
					 * issues, will not always be correct */
	struct list_head collision_resolving_node;	/* list node */
	struct list_head all_blocks_node;	/* list node */

	/* the following two lists contain block_link items */
	struct list_head ref_to_list;	/* list */
	struct list_head ref_from_list;	/* list */
	struct btrfsic_block *next_in_same_bio;
	void *orig_bio_bh_private;
	union {
		bio_end_io_t *bio;
		bh_end_io_t *bh;
	} orig_bio_bh_end_io;
	int submit_bio_bh_rw;
	u64 flush_gen; /* only valid if !never_written */
};

/*
 * Elements of this type are allocated dynamically and required because
 * each block object can refer to and can be ref from multiple blocks.
 * The key to lookup them in the hashtable is the dev_bytenr of
181
 * the block ref to plus the one from the block referred from.
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
 * The fact that they are searchable via a hashtable and that a
 * ref_cnt is maintained is not required for the btrfs integrity
 * check algorithm itself, it is only used to make the output more
 * beautiful in case that an error is detected (an error is defined
 * as a write operation to a block while that block is still referenced).
 */
struct btrfsic_block_link {
	u32 magic_num;		/* only used for debug purposes */
	u32 ref_cnt;
	struct list_head node_ref_to;	/* list node */
	struct list_head node_ref_from;	/* list node */
	struct list_head collision_resolving_node;	/* list node */
	struct btrfsic_block *block_ref_to;
	struct btrfsic_block *block_ref_from;
	u64 parent_generation;
};

struct btrfsic_dev_state {
	u32 magic_num;		/* only used for debug purposes */
	struct block_device *bdev;
	struct btrfsic_state *state;
	struct list_head collision_resolving_node;	/* list node */
	struct btrfsic_block dummy_block_for_bio_bh_flush;
	u64 last_flush_gen;
	char name[BDEVNAME_SIZE];
};

struct btrfsic_block_hashtable {
	struct list_head table[BTRFSIC_BLOCK_HASHTABLE_SIZE];
};

struct btrfsic_block_link_hashtable {
	struct list_head table[BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE];
};

struct btrfsic_dev_state_hashtable {
	struct list_head table[BTRFSIC_DEV2STATE_HASHTABLE_SIZE];
};

struct btrfsic_block_data_ctx {
	u64 start;		/* virtual bytenr */
	u64 dev_bytenr;		/* physical bytenr on device */
	u32 len;
	struct btrfsic_dev_state *dev;
226 227 228
	char **datav;
	struct page **pagev;
	void *mem_to_free;
229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
};

/* This structure is used to implement recursion without occupying
 * any stack space, refer to btrfsic_process_metablock() */
struct btrfsic_stack_frame {
	u32 magic;
	u32 nr;
	int error;
	int i;
	int limit_nesting;
	int num_copies;
	int mirror_num;
	struct btrfsic_block *block;
	struct btrfsic_block_data_ctx *block_ctx;
	struct btrfsic_block *next_block;
	struct btrfsic_block_data_ctx next_block_ctx;
	struct btrfs_header *hdr;
	struct btrfsic_stack_frame *prev;
};

/* Some state per mounted filesystem */
struct btrfsic_state {
	u32 print_mask;
	int include_extent_data;
	int csum_size;
	struct list_head all_blocks_list;
	struct btrfsic_block_hashtable block_hashtable;
	struct btrfsic_block_link_hashtable block_link_hashtable;
257
	struct btrfs_fs_info *fs_info;
258 259
	u64 max_superblock_generation;
	struct btrfsic_block *latest_superblock;
260 261
	u32 metablock_size;
	u32 datablock_size;
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
};

static void btrfsic_block_init(struct btrfsic_block *b);
static struct btrfsic_block *btrfsic_block_alloc(void);
static void btrfsic_block_free(struct btrfsic_block *b);
static void btrfsic_block_link_init(struct btrfsic_block_link *n);
static struct btrfsic_block_link *btrfsic_block_link_alloc(void);
static void btrfsic_block_link_free(struct btrfsic_block_link *n);
static void btrfsic_dev_state_init(struct btrfsic_dev_state *ds);
static struct btrfsic_dev_state *btrfsic_dev_state_alloc(void);
static void btrfsic_dev_state_free(struct btrfsic_dev_state *ds);
static void btrfsic_block_hashtable_init(struct btrfsic_block_hashtable *h);
static void btrfsic_block_hashtable_add(struct btrfsic_block *b,
					struct btrfsic_block_hashtable *h);
static void btrfsic_block_hashtable_remove(struct btrfsic_block *b);
static struct btrfsic_block *btrfsic_block_hashtable_lookup(
		struct block_device *bdev,
		u64 dev_bytenr,
		struct btrfsic_block_hashtable *h);
static void btrfsic_block_link_hashtable_init(
		struct btrfsic_block_link_hashtable *h);
static void btrfsic_block_link_hashtable_add(
		struct btrfsic_block_link *l,
		struct btrfsic_block_link_hashtable *h);
static void btrfsic_block_link_hashtable_remove(struct btrfsic_block_link *l);
static struct btrfsic_block_link *btrfsic_block_link_hashtable_lookup(
		struct block_device *bdev_ref_to,
		u64 dev_bytenr_ref_to,
		struct block_device *bdev_ref_from,
		u64 dev_bytenr_ref_from,
		struct btrfsic_block_link_hashtable *h);
static void btrfsic_dev_state_hashtable_init(
		struct btrfsic_dev_state_hashtable *h);
static void btrfsic_dev_state_hashtable_add(
		struct btrfsic_dev_state *ds,
		struct btrfsic_dev_state_hashtable *h);
static void btrfsic_dev_state_hashtable_remove(struct btrfsic_dev_state *ds);
static struct btrfsic_dev_state *btrfsic_dev_state_hashtable_lookup(
		struct block_device *bdev,
		struct btrfsic_dev_state_hashtable *h);
static struct btrfsic_stack_frame *btrfsic_stack_frame_alloc(void);
static void btrfsic_stack_frame_free(struct btrfsic_stack_frame *sf);
static int btrfsic_process_superblock(struct btrfsic_state *state,
				      struct btrfs_fs_devices *fs_devices);
static int btrfsic_process_metablock(struct btrfsic_state *state,
				     struct btrfsic_block *block,
				     struct btrfsic_block_data_ctx *block_ctx,
				     int limit_nesting, int force_iodone_flag);
310 311 312
static void btrfsic_read_from_block_data(
	struct btrfsic_block_data_ctx *block_ctx,
	void *dst, u32 offset, size_t len);
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336
static int btrfsic_create_link_to_next_block(
		struct btrfsic_state *state,
		struct btrfsic_block *block,
		struct btrfsic_block_data_ctx
		*block_ctx, u64 next_bytenr,
		int limit_nesting,
		struct btrfsic_block_data_ctx *next_block_ctx,
		struct btrfsic_block **next_blockp,
		int force_iodone_flag,
		int *num_copiesp, int *mirror_nump,
		struct btrfs_disk_key *disk_key,
		u64 parent_generation);
static int btrfsic_handle_extent_data(struct btrfsic_state *state,
				      struct btrfsic_block *block,
				      struct btrfsic_block_data_ctx *block_ctx,
				      u32 item_offset, int force_iodone_flag);
static int btrfsic_map_block(struct btrfsic_state *state, u64 bytenr, u32 len,
			     struct btrfsic_block_data_ctx *block_ctx_out,
			     int mirror_num);
static void btrfsic_release_block_ctx(struct btrfsic_block_data_ctx *block_ctx);
static int btrfsic_read_block(struct btrfsic_state *state,
			      struct btrfsic_block_data_ctx *block_ctx);
static void btrfsic_dump_database(struct btrfsic_state *state);
static int btrfsic_test_for_metadata(struct btrfsic_state *state,
337
				     char **datav, unsigned int num_pages);
338
static void btrfsic_process_written_block(struct btrfsic_dev_state *dev_state,
339 340 341
					  u64 dev_bytenr, char **mapped_datav,
					  unsigned int num_pages,
					  struct bio *bio, int *bio_is_patched,
342 343 344 345 346 347
					  struct buffer_head *bh,
					  int submit_bio_bh_rw);
static int btrfsic_process_written_superblock(
		struct btrfsic_state *state,
		struct btrfsic_block *const block,
		struct btrfs_super_block *const super_hdr);
348
static void btrfsic_bio_end_io(struct bio *bp);
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
static void btrfsic_bh_end_io(struct buffer_head *bh, int uptodate);
static int btrfsic_is_block_ref_by_superblock(const struct btrfsic_state *state,
					      const struct btrfsic_block *block,
					      int recursion_level);
static int btrfsic_check_all_ref_blocks(struct btrfsic_state *state,
					struct btrfsic_block *const block,
					int recursion_level);
static void btrfsic_print_add_link(const struct btrfsic_state *state,
				   const struct btrfsic_block_link *l);
static void btrfsic_print_rem_link(const struct btrfsic_state *state,
				   const struct btrfsic_block_link *l);
static char btrfsic_get_block_type(const struct btrfsic_state *state,
				   const struct btrfsic_block *block);
static void btrfsic_dump_tree(const struct btrfsic_state *state);
static void btrfsic_dump_tree_sub(const struct btrfsic_state *state,
				  const struct btrfsic_block *block,
				  int indent_level);
static struct btrfsic_block_link *btrfsic_block_link_lookup_or_add(
		struct btrfsic_state *state,
		struct btrfsic_block_data_ctx *next_block_ctx,
		struct btrfsic_block *next_block,
		struct btrfsic_block *from_block,
		u64 parent_generation);
static struct btrfsic_block *btrfsic_block_lookup_or_add(
		struct btrfsic_state *state,
		struct btrfsic_block_data_ctx *block_ctx,
		const char *additional_string,
		int is_metadata,
		int is_iodone,
		int never_written,
		int mirror_num,
		int *was_created);
static int btrfsic_process_superblock_dev_mirror(
		struct btrfsic_state *state,
		struct btrfsic_dev_state *dev_state,
		struct btrfs_device *device,
		int superblock_mirror_num,
		struct btrfsic_dev_state **selected_dev_state,
		struct btrfs_super_block *selected_super);
static struct btrfsic_dev_state *btrfsic_dev_state_lookup(
		struct block_device *bdev);
static void btrfsic_cmp_log_and_dev_bytenr(struct btrfsic_state *state,
					   u64 bytenr,
					   struct btrfsic_dev_state *dev_state,
393
					   u64 dev_bytenr);
394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535

static struct mutex btrfsic_mutex;
static int btrfsic_is_initialized;
static struct btrfsic_dev_state_hashtable btrfsic_dev_state_hashtable;


static void btrfsic_block_init(struct btrfsic_block *b)
{
	b->magic_num = BTRFSIC_BLOCK_MAGIC_NUMBER;
	b->dev_state = NULL;
	b->dev_bytenr = 0;
	b->logical_bytenr = 0;
	b->generation = BTRFSIC_GENERATION_UNKNOWN;
	b->disk_key.objectid = 0;
	b->disk_key.type = 0;
	b->disk_key.offset = 0;
	b->is_metadata = 0;
	b->is_superblock = 0;
	b->is_iodone = 0;
	b->iodone_w_error = 0;
	b->never_written = 0;
	b->mirror_num = 0;
	b->next_in_same_bio = NULL;
	b->orig_bio_bh_private = NULL;
	b->orig_bio_bh_end_io.bio = NULL;
	INIT_LIST_HEAD(&b->collision_resolving_node);
	INIT_LIST_HEAD(&b->all_blocks_node);
	INIT_LIST_HEAD(&b->ref_to_list);
	INIT_LIST_HEAD(&b->ref_from_list);
	b->submit_bio_bh_rw = 0;
	b->flush_gen = 0;
}

static struct btrfsic_block *btrfsic_block_alloc(void)
{
	struct btrfsic_block *b;

	b = kzalloc(sizeof(*b), GFP_NOFS);
	if (NULL != b)
		btrfsic_block_init(b);

	return b;
}

static void btrfsic_block_free(struct btrfsic_block *b)
{
	BUG_ON(!(NULL == b || BTRFSIC_BLOCK_MAGIC_NUMBER == b->magic_num));
	kfree(b);
}

static void btrfsic_block_link_init(struct btrfsic_block_link *l)
{
	l->magic_num = BTRFSIC_BLOCK_LINK_MAGIC_NUMBER;
	l->ref_cnt = 1;
	INIT_LIST_HEAD(&l->node_ref_to);
	INIT_LIST_HEAD(&l->node_ref_from);
	INIT_LIST_HEAD(&l->collision_resolving_node);
	l->block_ref_to = NULL;
	l->block_ref_from = NULL;
}

static struct btrfsic_block_link *btrfsic_block_link_alloc(void)
{
	struct btrfsic_block_link *l;

	l = kzalloc(sizeof(*l), GFP_NOFS);
	if (NULL != l)
		btrfsic_block_link_init(l);

	return l;
}

static void btrfsic_block_link_free(struct btrfsic_block_link *l)
{
	BUG_ON(!(NULL == l || BTRFSIC_BLOCK_LINK_MAGIC_NUMBER == l->magic_num));
	kfree(l);
}

static void btrfsic_dev_state_init(struct btrfsic_dev_state *ds)
{
	ds->magic_num = BTRFSIC_DEV2STATE_MAGIC_NUMBER;
	ds->bdev = NULL;
	ds->state = NULL;
	ds->name[0] = '\0';
	INIT_LIST_HEAD(&ds->collision_resolving_node);
	ds->last_flush_gen = 0;
	btrfsic_block_init(&ds->dummy_block_for_bio_bh_flush);
	ds->dummy_block_for_bio_bh_flush.is_iodone = 1;
	ds->dummy_block_for_bio_bh_flush.dev_state = ds;
}

static struct btrfsic_dev_state *btrfsic_dev_state_alloc(void)
{
	struct btrfsic_dev_state *ds;

	ds = kzalloc(sizeof(*ds), GFP_NOFS);
	if (NULL != ds)
		btrfsic_dev_state_init(ds);

	return ds;
}

static void btrfsic_dev_state_free(struct btrfsic_dev_state *ds)
{
	BUG_ON(!(NULL == ds ||
		 BTRFSIC_DEV2STATE_MAGIC_NUMBER == ds->magic_num));
	kfree(ds);
}

static void btrfsic_block_hashtable_init(struct btrfsic_block_hashtable *h)
{
	int i;

	for (i = 0; i < BTRFSIC_BLOCK_HASHTABLE_SIZE; i++)
		INIT_LIST_HEAD(h->table + i);
}

static void btrfsic_block_hashtable_add(struct btrfsic_block *b,
					struct btrfsic_block_hashtable *h)
{
	const unsigned int hashval =
	    (((unsigned int)(b->dev_bytenr >> 16)) ^
	     ((unsigned int)((uintptr_t)b->dev_state->bdev))) &
	     (BTRFSIC_BLOCK_HASHTABLE_SIZE - 1);

	list_add(&b->collision_resolving_node, h->table + hashval);
}

static void btrfsic_block_hashtable_remove(struct btrfsic_block *b)
{
	list_del(&b->collision_resolving_node);
}

static struct btrfsic_block *btrfsic_block_hashtable_lookup(
		struct block_device *bdev,
		u64 dev_bytenr,
		struct btrfsic_block_hashtable *h)
{
	const unsigned int hashval =
	    (((unsigned int)(dev_bytenr >> 16)) ^
	     ((unsigned int)((uintptr_t)bdev))) &
	     (BTRFSIC_BLOCK_HASHTABLE_SIZE - 1);
536
	struct btrfsic_block *b;
537

538
	list_for_each_entry(b, h->table + hashval, collision_resolving_node) {
539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
		if (b->dev_state->bdev == bdev && b->dev_bytenr == dev_bytenr)
			return b;
	}

	return NULL;
}

static void btrfsic_block_link_hashtable_init(
		struct btrfsic_block_link_hashtable *h)
{
	int i;

	for (i = 0; i < BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE; i++)
		INIT_LIST_HEAD(h->table + i);
}

static void btrfsic_block_link_hashtable_add(
		struct btrfsic_block_link *l,
		struct btrfsic_block_link_hashtable *h)
{
	const unsigned int hashval =
	    (((unsigned int)(l->block_ref_to->dev_bytenr >> 16)) ^
	     ((unsigned int)(l->block_ref_from->dev_bytenr >> 16)) ^
	     ((unsigned int)((uintptr_t)l->block_ref_to->dev_state->bdev)) ^
	     ((unsigned int)((uintptr_t)l->block_ref_from->dev_state->bdev)))
	     & (BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE - 1);

	BUG_ON(NULL == l->block_ref_to);
	BUG_ON(NULL == l->block_ref_from);
	list_add(&l->collision_resolving_node, h->table + hashval);
}

static void btrfsic_block_link_hashtable_remove(struct btrfsic_block_link *l)
{
	list_del(&l->collision_resolving_node);
}

static struct btrfsic_block_link *btrfsic_block_link_hashtable_lookup(
		struct block_device *bdev_ref_to,
		u64 dev_bytenr_ref_to,
		struct block_device *bdev_ref_from,
		u64 dev_bytenr_ref_from,
		struct btrfsic_block_link_hashtable *h)
{
	const unsigned int hashval =
	    (((unsigned int)(dev_bytenr_ref_to >> 16)) ^
	     ((unsigned int)(dev_bytenr_ref_from >> 16)) ^
	     ((unsigned int)((uintptr_t)bdev_ref_to)) ^
	     ((unsigned int)((uintptr_t)bdev_ref_from))) &
	     (BTRFSIC_BLOCK_LINK_HASHTABLE_SIZE - 1);
589
	struct btrfsic_block_link *l;
590

591
	list_for_each_entry(l, h->table + hashval, collision_resolving_node) {
592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635
		BUG_ON(NULL == l->block_ref_to);
		BUG_ON(NULL == l->block_ref_from);
		if (l->block_ref_to->dev_state->bdev == bdev_ref_to &&
		    l->block_ref_to->dev_bytenr == dev_bytenr_ref_to &&
		    l->block_ref_from->dev_state->bdev == bdev_ref_from &&
		    l->block_ref_from->dev_bytenr == dev_bytenr_ref_from)
			return l;
	}

	return NULL;
}

static void btrfsic_dev_state_hashtable_init(
		struct btrfsic_dev_state_hashtable *h)
{
	int i;

	for (i = 0; i < BTRFSIC_DEV2STATE_HASHTABLE_SIZE; i++)
		INIT_LIST_HEAD(h->table + i);
}

static void btrfsic_dev_state_hashtable_add(
		struct btrfsic_dev_state *ds,
		struct btrfsic_dev_state_hashtable *h)
{
	const unsigned int hashval =
	    (((unsigned int)((uintptr_t)ds->bdev)) &
	     (BTRFSIC_DEV2STATE_HASHTABLE_SIZE - 1));

	list_add(&ds->collision_resolving_node, h->table + hashval);
}

static void btrfsic_dev_state_hashtable_remove(struct btrfsic_dev_state *ds)
{
	list_del(&ds->collision_resolving_node);
}

static struct btrfsic_dev_state *btrfsic_dev_state_hashtable_lookup(
		struct block_device *bdev,
		struct btrfsic_dev_state_hashtable *h)
{
	const unsigned int hashval =
	    (((unsigned int)((uintptr_t)bdev)) &
	     (BTRFSIC_DEV2STATE_HASHTABLE_SIZE - 1));
636
	struct btrfsic_dev_state *ds;
637

638
	list_for_each_entry(ds, h->table + hashval, collision_resolving_node) {
639 640 641 642 643 644 645 646 647 648
		if (ds->bdev == bdev)
			return ds;
	}

	return NULL;
}

static int btrfsic_process_superblock(struct btrfsic_state *state,
				      struct btrfs_fs_devices *fs_devices)
{
649
	struct btrfs_fs_info *fs_info = state->fs_info;
650 651 652 653
	struct btrfs_super_block *selected_super;
	struct list_head *dev_head = &fs_devices->devices;
	struct btrfs_device *device;
	struct btrfsic_dev_state *selected_dev_state = NULL;
654
	int ret = 0;
655 656 657
	int pass;

	BUG_ON(NULL == state);
658
	selected_super = kzalloc(sizeof(*selected_super), GFP_NOFS);
659
	if (NULL == selected_super) {
660
		pr_info("btrfsic: error, kmalloc failed!\n");
661
		return -ENOMEM;
662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
	}

	list_for_each_entry(device, dev_head, dev_list) {
		int i;
		struct btrfsic_dev_state *dev_state;

		if (!device->bdev || !device->name)
			continue;

		dev_state = btrfsic_dev_state_lookup(device->bdev);
		BUG_ON(NULL == dev_state);
		for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
			ret = btrfsic_process_superblock_dev_mirror(
					state, dev_state, device, i,
					&selected_dev_state, selected_super);
			if (0 != ret && 0 == i) {
				kfree(selected_super);
				return ret;
			}
		}
	}

	if (NULL == state->latest_superblock) {
685
		pr_info("btrfsic: no superblock found!\n");
686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701
		kfree(selected_super);
		return -1;
	}

	state->csum_size = btrfs_super_csum_size(selected_super);

	for (pass = 0; pass < 3; pass++) {
		int num_copies;
		int mirror_num;
		u64 next_bytenr;

		switch (pass) {
		case 0:
			next_bytenr = btrfs_super_root(selected_super);
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
702
				pr_info("root@%llu\n", next_bytenr);
703 704 705 706 707
			break;
		case 1:
			next_bytenr = btrfs_super_chunk_root(selected_super);
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
708
				pr_info("chunk@%llu\n", next_bytenr);
709 710 711 712 713 714 715
			break;
		case 2:
			next_bytenr = btrfs_super_log_root(selected_super);
			if (0 == next_bytenr)
				continue;
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
716
				pr_info("log@%llu\n", next_bytenr);
717 718 719
			break;
		}

720 721
		num_copies = btrfs_num_copies(fs_info, next_bytenr,
					      state->metablock_size);
722
		if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
723
			pr_info("num_copies(log_bytenr=%llu) = %d\n",
724
			       next_bytenr, num_copies);
725 726 727 728 729 730

		for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
			struct btrfsic_block *next_block;
			struct btrfsic_block_data_ctx tmp_next_block_ctx;
			struct btrfsic_block_link *l;

731 732
			ret = btrfsic_map_block(state, next_bytenr,
						state->metablock_size,
733 734 735
						&tmp_next_block_ctx,
						mirror_num);
			if (ret) {
736
				pr_info("btrfsic: btrfsic_map_block(root @%llu, mirror %d) failed!\n",
737
				       next_bytenr, mirror_num);
738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757
				kfree(selected_super);
				return -1;
			}

			next_block = btrfsic_block_hashtable_lookup(
					tmp_next_block_ctx.dev->bdev,
					tmp_next_block_ctx.dev_bytenr,
					&state->block_hashtable);
			BUG_ON(NULL == next_block);

			l = btrfsic_block_link_hashtable_lookup(
					tmp_next_block_ctx.dev->bdev,
					tmp_next_block_ctx.dev_bytenr,
					state->latest_superblock->dev_state->
					bdev,
					state->latest_superblock->dev_bytenr,
					&state->block_link_hashtable);
			BUG_ON(NULL == l);

			ret = btrfsic_read_block(state, &tmp_next_block_ctx);
758
			if (ret < (int)PAGE_SIZE) {
759
				pr_info("btrfsic: read @logical %llu failed!\n",
760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785
				       tmp_next_block_ctx.start);
				btrfsic_release_block_ctx(&tmp_next_block_ctx);
				kfree(selected_super);
				return -1;
			}

			ret = btrfsic_process_metablock(state,
							next_block,
							&tmp_next_block_ctx,
							BTRFS_MAX_LEVEL + 3, 1);
			btrfsic_release_block_ctx(&tmp_next_block_ctx);
		}
	}

	kfree(selected_super);
	return ret;
}

static int btrfsic_process_superblock_dev_mirror(
		struct btrfsic_state *state,
		struct btrfsic_dev_state *dev_state,
		struct btrfs_device *device,
		int superblock_mirror_num,
		struct btrfsic_dev_state **selected_dev_state,
		struct btrfs_super_block *selected_super)
{
786
	struct btrfs_fs_info *fs_info = state->fs_info;
787 788 789 790 791 792 793 794 795
	struct btrfs_super_block *super_tmp;
	u64 dev_bytenr;
	struct buffer_head *bh;
	struct btrfsic_block *superblock_tmp;
	int pass;
	struct block_device *const superblock_bdev = device->bdev;

	/* super block bytenr is always the unmapped device bytenr */
	dev_bytenr = btrfs_sb_offset(superblock_mirror_num);
796
	if (dev_bytenr + BTRFS_SUPER_INFO_SIZE > device->commit_total_bytes)
797 798 799
		return -1;
	bh = __bread(superblock_bdev, dev_bytenr / 4096,
		     BTRFS_SUPER_INFO_SIZE);
800 801 802 803 804 805
	if (NULL == bh)
		return -1;
	super_tmp = (struct btrfs_super_block *)
	    (bh->b_data + (dev_bytenr & 4095));

	if (btrfs_super_bytenr(super_tmp) != dev_bytenr ||
806
	    btrfs_super_magic(super_tmp) != BTRFS_MAGIC ||
807 808 809
	    memcmp(device->uuid, super_tmp->dev_item.uuid, BTRFS_UUID_SIZE) ||
	    btrfs_super_nodesize(super_tmp) != state->metablock_size ||
	    btrfs_super_sectorsize(super_tmp) != state->datablock_size) {
810 811 812 813 814 815 816 817 818 819 820
		brelse(bh);
		return 0;
	}

	superblock_tmp =
	    btrfsic_block_hashtable_lookup(superblock_bdev,
					   dev_bytenr,
					   &state->block_hashtable);
	if (NULL == superblock_tmp) {
		superblock_tmp = btrfsic_block_alloc();
		if (NULL == superblock_tmp) {
821
			pr_info("btrfsic: error, kmalloc failed!\n");
822 823 824 825 826 827 828 829 830 831 832 833 834 835
			brelse(bh);
			return -1;
		}
		/* for superblock, only the dev_bytenr makes sense */
		superblock_tmp->dev_bytenr = dev_bytenr;
		superblock_tmp->dev_state = dev_state;
		superblock_tmp->logical_bytenr = dev_bytenr;
		superblock_tmp->generation = btrfs_super_generation(super_tmp);
		superblock_tmp->is_metadata = 1;
		superblock_tmp->is_superblock = 1;
		superblock_tmp->is_iodone = 1;
		superblock_tmp->never_written = 0;
		superblock_tmp->mirror_num = 1 + superblock_mirror_num;
		if (state->print_mask & BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE)
836
			btrfs_info_in_rcu(fs_info,
837
				"new initial S-block (bdev %p, %s) @%llu (%s/%llu/%d)",
838
				     superblock_bdev,
839 840
				     rcu_str_deref(device->name), dev_bytenr,
				     dev_state->name, dev_bytenr,
841
				     superblock_mirror_num);
842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869
		list_add(&superblock_tmp->all_blocks_node,
			 &state->all_blocks_list);
		btrfsic_block_hashtable_add(superblock_tmp,
					    &state->block_hashtable);
	}

	/* select the one with the highest generation field */
	if (btrfs_super_generation(super_tmp) >
	    state->max_superblock_generation ||
	    0 == state->max_superblock_generation) {
		memcpy(selected_super, super_tmp, sizeof(*selected_super));
		*selected_dev_state = dev_state;
		state->max_superblock_generation =
		    btrfs_super_generation(super_tmp);
		state->latest_superblock = superblock_tmp;
	}

	for (pass = 0; pass < 3; pass++) {
		u64 next_bytenr;
		int num_copies;
		int mirror_num;
		const char *additional_string = NULL;
		struct btrfs_disk_key tmp_disk_key;

		tmp_disk_key.type = BTRFS_ROOT_ITEM_KEY;
		tmp_disk_key.offset = 0;
		switch (pass) {
		case 0:
870 871
			btrfs_set_disk_key_objectid(&tmp_disk_key,
						    BTRFS_ROOT_TREE_OBJECTID);
872 873 874 875
			additional_string = "initial root ";
			next_bytenr = btrfs_super_root(super_tmp);
			break;
		case 1:
876 877
			btrfs_set_disk_key_objectid(&tmp_disk_key,
						    BTRFS_CHUNK_TREE_OBJECTID);
878 879 880 881
			additional_string = "initial chunk ";
			next_bytenr = btrfs_super_chunk_root(super_tmp);
			break;
		case 2:
882 883
			btrfs_set_disk_key_objectid(&tmp_disk_key,
						    BTRFS_TREE_LOG_OBJECTID);
884 885 886 887 888 889 890
			additional_string = "initial log ";
			next_bytenr = btrfs_super_log_root(super_tmp);
			if (0 == next_bytenr)
				continue;
			break;
		}

891 892
		num_copies = btrfs_num_copies(fs_info, next_bytenr,
					      state->metablock_size);
893
		if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
894
			pr_info("num_copies(log_bytenr=%llu) = %d\n",
895
			       next_bytenr, num_copies);
896 897 898 899 900
		for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
			struct btrfsic_block *next_block;
			struct btrfsic_block_data_ctx tmp_next_block_ctx;
			struct btrfsic_block_link *l;

901 902
			if (btrfsic_map_block(state, next_bytenr,
					      state->metablock_size,
903 904
					      &tmp_next_block_ctx,
					      mirror_num)) {
905
				pr_info("btrfsic: btrfsic_map_block(bytenr @%llu, mirror %d) failed!\n",
906
				       next_bytenr, mirror_num);
907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946
				brelse(bh);
				return -1;
			}

			next_block = btrfsic_block_lookup_or_add(
					state, &tmp_next_block_ctx,
					additional_string, 1, 1, 0,
					mirror_num, NULL);
			if (NULL == next_block) {
				btrfsic_release_block_ctx(&tmp_next_block_ctx);
				brelse(bh);
				return -1;
			}

			next_block->disk_key = tmp_disk_key;
			next_block->generation = BTRFSIC_GENERATION_UNKNOWN;
			l = btrfsic_block_link_lookup_or_add(
					state, &tmp_next_block_ctx,
					next_block, superblock_tmp,
					BTRFSIC_GENERATION_UNKNOWN);
			btrfsic_release_block_ctx(&tmp_next_block_ctx);
			if (NULL == l) {
				brelse(bh);
				return -1;
			}
		}
	}
	if (state->print_mask & BTRFSIC_PRINT_MASK_INITIAL_ALL_TREES)
		btrfsic_dump_tree_sub(state, superblock_tmp, 0);

	brelse(bh);
	return 0;
}

static struct btrfsic_stack_frame *btrfsic_stack_frame_alloc(void)
{
	struct btrfsic_stack_frame *sf;

	sf = kzalloc(sizeof(*sf), GFP_NOFS);
	if (NULL == sf)
947
		pr_info("btrfsic: alloc memory failed!\n");
948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968
	else
		sf->magic = BTRFSIC_BLOCK_STACK_FRAME_MAGIC_NUMBER;
	return sf;
}

static void btrfsic_stack_frame_free(struct btrfsic_stack_frame *sf)
{
	BUG_ON(!(NULL == sf ||
		 BTRFSIC_BLOCK_STACK_FRAME_MAGIC_NUMBER == sf->magic));
	kfree(sf);
}

static int btrfsic_process_metablock(
		struct btrfsic_state *state,
		struct btrfsic_block *const first_block,
		struct btrfsic_block_data_ctx *const first_block_ctx,
		int first_limit_nesting, int force_iodone_flag)
{
	struct btrfsic_stack_frame initial_stack_frame = { 0 };
	struct btrfsic_stack_frame *sf;
	struct btrfsic_stack_frame *next_stack;
969 970
	struct btrfs_header *const first_hdr =
		(struct btrfs_header *)first_block_ctx->datav[0];
971

972
	BUG_ON(!first_hdr);
973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989
	sf = &initial_stack_frame;
	sf->error = 0;
	sf->i = -1;
	sf->limit_nesting = first_limit_nesting;
	sf->block = first_block;
	sf->block_ctx = first_block_ctx;
	sf->next_block = NULL;
	sf->hdr = first_hdr;
	sf->prev = NULL;

continue_with_new_stack_frame:
	sf->block->generation = le64_to_cpu(sf->hdr->generation);
	if (0 == sf->hdr->level) {
		struct btrfs_leaf *const leafhdr =
		    (struct btrfs_leaf *)sf->hdr;

		if (-1 == sf->i) {
990
			sf->nr = btrfs_stack_header_nritems(&leafhdr->header);
991 992

			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
993
				pr_info("leaf %llu items %d generation %llu owner %llu\n",
994
				       sf->block_ctx->start, sf->nr,
995 996 997 998
				       btrfs_stack_header_generation(
					       &leafhdr->header),
				       btrfs_stack_header_owner(
					       &leafhdr->header));
999 1000 1001 1002 1003 1004 1005 1006 1007
		}

continue_with_current_leaf_stack_frame:
		if (0 == sf->num_copies || sf->mirror_num > sf->num_copies) {
			sf->i++;
			sf->num_copies = 0;
		}

		if (sf->i < sf->nr) {
1008 1009 1010 1011 1012
			struct btrfs_item disk_item;
			u32 disk_item_offset =
				(uintptr_t)(leafhdr->items + sf->i) -
				(uintptr_t)leafhdr;
			struct btrfs_disk_key *disk_key;
1013
			u8 type;
1014
			u32 item_offset;
1015
			u32 item_size;
1016

1017 1018 1019
			if (disk_item_offset + sizeof(struct btrfs_item) >
			    sf->block_ctx->len) {
leaf_item_out_of_bounce_error:
1020
				pr_info("btrfsic: leaf item out of bounce at logical %llu, dev %s\n",
1021 1022 1023 1024 1025 1026 1027 1028
				       sf->block_ctx->start,
				       sf->block_ctx->dev->name);
				goto one_stack_frame_backwards;
			}
			btrfsic_read_from_block_data(sf->block_ctx,
						     &disk_item,
						     disk_item_offset,
						     sizeof(struct btrfs_item));
1029
			item_offset = btrfs_stack_item_offset(&disk_item);
1030
			item_size = btrfs_stack_item_size(&disk_item);
1031
			disk_key = &disk_item.key;
1032
			type = btrfs_disk_key_type(disk_key);
1033 1034

			if (BTRFS_ROOT_ITEM_KEY == type) {
1035 1036 1037 1038 1039 1040
				struct btrfs_root_item root_item;
				u32 root_item_offset;
				u64 next_bytenr;

				root_item_offset = item_offset +
					offsetof(struct btrfs_leaf, items);
1041
				if (root_item_offset + item_size >
1042 1043 1044 1045 1046
				    sf->block_ctx->len)
					goto leaf_item_out_of_bounce_error;
				btrfsic_read_from_block_data(
					sf->block_ctx, &root_item,
					root_item_offset,
1047
					item_size);
1048
				next_bytenr = btrfs_root_bytenr(&root_item);
1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062

				sf->error =
				    btrfsic_create_link_to_next_block(
						state,
						sf->block,
						sf->block_ctx,
						next_bytenr,
						sf->limit_nesting,
						&sf->next_block_ctx,
						&sf->next_block,
						force_iodone_flag,
						&sf->num_copies,
						&sf->mirror_num,
						disk_key,
1063 1064
						btrfs_root_generation(
						&root_item));
1065 1066 1067 1068 1069 1070
				if (sf->error)
					goto one_stack_frame_backwards;

				if (NULL != sf->next_block) {
					struct btrfs_header *const next_hdr =
					    (struct btrfs_header *)
1071
					    sf->next_block_ctx.datav[0];
1072 1073 1074 1075

					next_stack =
					    btrfsic_stack_frame_alloc();
					if (NULL == next_stack) {
1076
						sf->error = -1;
1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112
						btrfsic_release_block_ctx(
								&sf->
								next_block_ctx);
						goto one_stack_frame_backwards;
					}

					next_stack->i = -1;
					next_stack->block = sf->next_block;
					next_stack->block_ctx =
					    &sf->next_block_ctx;
					next_stack->next_block = NULL;
					next_stack->hdr = next_hdr;
					next_stack->limit_nesting =
					    sf->limit_nesting - 1;
					next_stack->prev = sf;
					sf = next_stack;
					goto continue_with_new_stack_frame;
				}
			} else if (BTRFS_EXTENT_DATA_KEY == type &&
				   state->include_extent_data) {
				sf->error = btrfsic_handle_extent_data(
						state,
						sf->block,
						sf->block_ctx,
						item_offset,
						force_iodone_flag);
				if (sf->error)
					goto one_stack_frame_backwards;
			}

			goto continue_with_current_leaf_stack_frame;
		}
	} else {
		struct btrfs_node *const nodehdr = (struct btrfs_node *)sf->hdr;

		if (-1 == sf->i) {
1113
			sf->nr = btrfs_stack_header_nritems(&nodehdr->header);
1114 1115

			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1116
				pr_info("node %llu level %d items %d generation %llu owner %llu\n",
1117 1118
				       sf->block_ctx->start,
				       nodehdr->header.level, sf->nr,
1119 1120 1121 1122
				       btrfs_stack_header_generation(
				       &nodehdr->header),
				       btrfs_stack_header_owner(
				       &nodehdr->header));
1123 1124 1125 1126 1127 1128 1129 1130 1131
		}

continue_with_current_node_stack_frame:
		if (0 == sf->num_copies || sf->mirror_num > sf->num_copies) {
			sf->i++;
			sf->num_copies = 0;
		}

		if (sf->i < sf->nr) {
1132 1133 1134 1135 1136 1137 1138 1139
			struct btrfs_key_ptr key_ptr;
			u32 key_ptr_offset;
			u64 next_bytenr;

			key_ptr_offset = (uintptr_t)(nodehdr->ptrs + sf->i) -
					  (uintptr_t)nodehdr;
			if (key_ptr_offset + sizeof(struct btrfs_key_ptr) >
			    sf->block_ctx->len) {
1140
				pr_info("btrfsic: node item out of bounce at logical %llu, dev %s\n",
1141 1142 1143 1144 1145 1146 1147
				       sf->block_ctx->start,
				       sf->block_ctx->dev->name);
				goto one_stack_frame_backwards;
			}
			btrfsic_read_from_block_data(
				sf->block_ctx, &key_ptr, key_ptr_offset,
				sizeof(struct btrfs_key_ptr));
1148
			next_bytenr = btrfs_stack_key_blockptr(&key_ptr);
1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160

			sf->error = btrfsic_create_link_to_next_block(
					state,
					sf->block,
					sf->block_ctx,
					next_bytenr,
					sf->limit_nesting,
					&sf->next_block_ctx,
					&sf->next_block,
					force_iodone_flag,
					&sf->num_copies,
					&sf->mirror_num,
1161
					&key_ptr.key,
1162
					btrfs_stack_key_generation(&key_ptr));
1163 1164 1165 1166 1167 1168
			if (sf->error)
				goto one_stack_frame_backwards;

			if (NULL != sf->next_block) {
				struct btrfs_header *const next_hdr =
				    (struct btrfs_header *)
1169
				    sf->next_block_ctx.datav[0];
1170 1171

				next_stack = btrfsic_stack_frame_alloc();
1172 1173
				if (NULL == next_stack) {
					sf->error = -1;
1174
					goto one_stack_frame_backwards;
1175
				}
1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216

				next_stack->i = -1;
				next_stack->block = sf->next_block;
				next_stack->block_ctx = &sf->next_block_ctx;
				next_stack->next_block = NULL;
				next_stack->hdr = next_hdr;
				next_stack->limit_nesting =
				    sf->limit_nesting - 1;
				next_stack->prev = sf;
				sf = next_stack;
				goto continue_with_new_stack_frame;
			}

			goto continue_with_current_node_stack_frame;
		}
	}

one_stack_frame_backwards:
	if (NULL != sf->prev) {
		struct btrfsic_stack_frame *const prev = sf->prev;

		/* the one for the initial block is freed in the caller */
		btrfsic_release_block_ctx(sf->block_ctx);

		if (sf->error) {
			prev->error = sf->error;
			btrfsic_stack_frame_free(sf);
			sf = prev;
			goto one_stack_frame_backwards;
		}

		btrfsic_stack_frame_free(sf);
		sf = prev;
		goto continue_with_new_stack_frame;
	} else {
		BUG_ON(&initial_stack_frame != sf);
	}

	return sf->error;
}

1217 1218 1219 1220 1221 1222 1223 1224
static void btrfsic_read_from_block_data(
	struct btrfsic_block_data_ctx *block_ctx,
	void *dstv, u32 offset, size_t len)
{
	size_t cur;
	size_t offset_in_page;
	char *kaddr;
	char *dst = (char *)dstv;
1225 1226
	size_t start_offset = block_ctx->start & ((u64)PAGE_SIZE - 1);
	unsigned long i = (start_offset + offset) >> PAGE_SHIFT;
1227 1228

	WARN_ON(offset + len > block_ctx->len);
1229
	offset_in_page = (start_offset + offset) & (PAGE_SIZE - 1);
1230 1231

	while (len > 0) {
1232 1233
		cur = min(len, ((size_t)PAGE_SIZE - offset_in_page));
		BUG_ON(i >= DIV_ROUND_UP(block_ctx->len, PAGE_SIZE));
1234 1235 1236 1237 1238 1239 1240 1241 1242 1243
		kaddr = block_ctx->datav[i];
		memcpy(dst, kaddr + offset_in_page, cur);

		dst += cur;
		len -= cur;
		offset_in_page = 0;
		i++;
	}
}

1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256
static int btrfsic_create_link_to_next_block(
		struct btrfsic_state *state,
		struct btrfsic_block *block,
		struct btrfsic_block_data_ctx *block_ctx,
		u64 next_bytenr,
		int limit_nesting,
		struct btrfsic_block_data_ctx *next_block_ctx,
		struct btrfsic_block **next_blockp,
		int force_iodone_flag,
		int *num_copiesp, int *mirror_nump,
		struct btrfs_disk_key *disk_key,
		u64 parent_generation)
{
1257
	struct btrfs_fs_info *fs_info = state->fs_info;
1258 1259 1260 1261 1262 1263 1264 1265
	struct btrfsic_block *next_block = NULL;
	int ret;
	struct btrfsic_block_link *l;
	int did_alloc_block_link;
	int block_was_created;

	*next_blockp = NULL;
	if (0 == *num_copiesp) {
1266 1267
		*num_copiesp = btrfs_num_copies(fs_info, next_bytenr,
						state->metablock_size);
1268
		if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
1269
			pr_info("num_copies(log_bytenr=%llu) = %d\n",
1270
			       next_bytenr, *num_copiesp);
1271 1272 1273 1274 1275 1276 1277
		*mirror_nump = 1;
	}

	if (*mirror_nump > *num_copiesp)
		return 0;

	if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1278
		pr_info("btrfsic_create_link_to_next_block(mirror_num=%d)\n",
1279 1280
		       *mirror_nump);
	ret = btrfsic_map_block(state, next_bytenr,
1281
				state->metablock_size,
1282 1283
				next_block_ctx, *mirror_nump);
	if (ret) {
1284
		pr_info("btrfsic: btrfsic_map_block(@%llu, mirror=%d) failed!\n",
1285
		       next_bytenr, *mirror_nump);
1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305
		btrfsic_release_block_ctx(next_block_ctx);
		*next_blockp = NULL;
		return -1;
	}

	next_block = btrfsic_block_lookup_or_add(state,
						 next_block_ctx, "referenced ",
						 1, force_iodone_flag,
						 !force_iodone_flag,
						 *mirror_nump,
						 &block_was_created);
	if (NULL == next_block) {
		btrfsic_release_block_ctx(next_block_ctx);
		*next_blockp = NULL;
		return -1;
	}
	if (block_was_created) {
		l = NULL;
		next_block->generation = BTRFSIC_GENERATION_UNKNOWN;
	} else {
1306 1307 1308 1309
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE) {
			if (next_block->logical_bytenr != next_bytenr &&
			    !(!next_block->is_metadata &&
			      0 == next_block->logical_bytenr))
1310
				pr_info("Referenced block @%llu (%s/%llu/%d) found in hash table, %c, bytenr mismatch (!= stored %llu).\n",
1311 1312 1313 1314 1315 1316
				       next_bytenr, next_block_ctx->dev->name,
				       next_block_ctx->dev_bytenr, *mirror_nump,
				       btrfsic_get_block_type(state,
							      next_block),
				       next_block->logical_bytenr);
			else
1317
				pr_info("Referenced block @%llu (%s/%llu/%d) found in hash table, %c.\n",
1318 1319 1320 1321 1322
				       next_bytenr, next_block_ctx->dev->name,
				       next_block_ctx->dev_bytenr, *mirror_nump,
				       btrfsic_get_block_type(state,
							      next_block));
		}
1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337
		next_block->logical_bytenr = next_bytenr;

		next_block->mirror_num = *mirror_nump;
		l = btrfsic_block_link_hashtable_lookup(
				next_block_ctx->dev->bdev,
				next_block_ctx->dev_bytenr,
				block_ctx->dev->bdev,
				block_ctx->dev_bytenr,
				&state->block_link_hashtable);
	}

	next_block->disk_key = *disk_key;
	if (NULL == l) {
		l = btrfsic_block_link_alloc();
		if (NULL == l) {
1338
			pr_info("btrfsic: error, kmalloc failed!\n");
1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369
			btrfsic_release_block_ctx(next_block_ctx);
			*next_blockp = NULL;
			return -1;
		}

		did_alloc_block_link = 1;
		l->block_ref_to = next_block;
		l->block_ref_from = block;
		l->ref_cnt = 1;
		l->parent_generation = parent_generation;

		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
			btrfsic_print_add_link(state, l);

		list_add(&l->node_ref_to, &block->ref_to_list);
		list_add(&l->node_ref_from, &next_block->ref_from_list);

		btrfsic_block_link_hashtable_add(l,
						 &state->block_link_hashtable);
	} else {
		did_alloc_block_link = 0;
		if (0 == limit_nesting) {
			l->ref_cnt++;
			l->parent_generation = parent_generation;
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
				btrfsic_print_add_link(state, l);
		}
	}

	if (limit_nesting > 0 && did_alloc_block_link) {
		ret = btrfsic_read_block(state, next_block_ctx);
1370
		if (ret < (int)next_block_ctx->len) {
1371
			pr_info("btrfsic: read block @logical %llu failed!\n",
1372
			       next_bytenr);
1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392
			btrfsic_release_block_ctx(next_block_ctx);
			*next_blockp = NULL;
			return -1;
		}

		*next_blockp = next_block;
	} else {
		*next_blockp = NULL;
	}
	(*mirror_nump)++;

	return 0;
}

static int btrfsic_handle_extent_data(
		struct btrfsic_state *state,
		struct btrfsic_block *block,
		struct btrfsic_block_data_ctx *block_ctx,
		u32 item_offset, int force_iodone_flag)
{
1393
	struct btrfs_fs_info *fs_info = state->fs_info;
1394 1395 1396 1397 1398
	struct btrfs_file_extent_item file_extent_item;
	u64 file_extent_item_offset;
	u64 next_bytenr;
	u64 num_bytes;
	u64 generation;
1399
	struct btrfsic_block_link *l;
1400
	int ret;
1401

1402 1403
	file_extent_item_offset = offsetof(struct btrfs_leaf, items) +
				  item_offset;
1404 1405 1406
	if (file_extent_item_offset +
	    offsetof(struct btrfs_file_extent_item, disk_num_bytes) >
	    block_ctx->len) {
1407
		pr_info("btrfsic: file item out of bounce at logical %llu, dev %s\n",
1408 1409 1410 1411 1412 1413 1414 1415
		       block_ctx->start, block_ctx->dev->name);
		return -1;
	}

	btrfsic_read_from_block_data(block_ctx, &file_extent_item,
		file_extent_item_offset,
		offsetof(struct btrfs_file_extent_item, disk_num_bytes));
	if (BTRFS_FILE_EXTENT_REG != file_extent_item.type ||
1416
	    btrfs_stack_file_extent_disk_bytenr(&file_extent_item) == 0) {
1417
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERY_VERBOSE)
1418
			pr_info("extent_data: type %u, disk_bytenr = %llu\n",
1419
			       file_extent_item.type,
1420 1421
			       btrfs_stack_file_extent_disk_bytenr(
			       &file_extent_item));
1422 1423 1424
		return 0;
	}

1425 1426
	if (file_extent_item_offset + sizeof(struct btrfs_file_extent_item) >
	    block_ctx->len) {
1427
		pr_info("btrfsic: file item out of bounce at logical %llu, dev %s\n",
1428 1429 1430 1431 1432 1433
		       block_ctx->start, block_ctx->dev->name);
		return -1;
	}
	btrfsic_read_from_block_data(block_ctx, &file_extent_item,
				     file_extent_item_offset,
				     sizeof(struct btrfs_file_extent_item));
1434 1435 1436 1437 1438 1439 1440 1441
	next_bytenr = btrfs_stack_file_extent_disk_bytenr(&file_extent_item);
	if (btrfs_stack_file_extent_compression(&file_extent_item) ==
	    BTRFS_COMPRESS_NONE) {
		next_bytenr += btrfs_stack_file_extent_offset(&file_extent_item);
		num_bytes = btrfs_stack_file_extent_num_bytes(&file_extent_item);
	} else {
		num_bytes = btrfs_stack_file_extent_disk_num_bytes(&file_extent_item);
	}
1442
	generation = btrfs_stack_file_extent_generation(&file_extent_item);
1443

1444
	if (state->print_mask & BTRFSIC_PRINT_MASK_VERY_VERBOSE)
1445
		pr_info("extent_data: type %u, disk_bytenr = %llu, offset = %llu, num_bytes = %llu\n",
1446
		       file_extent_item.type,
1447 1448
		       btrfs_stack_file_extent_disk_bytenr(&file_extent_item),
		       btrfs_stack_file_extent_offset(&file_extent_item),
1449
		       num_bytes);
1450 1451 1452 1453 1454
	while (num_bytes > 0) {
		u32 chunk_len;
		int num_copies;
		int mirror_num;

1455 1456
		if (num_bytes > state->datablock_size)
			chunk_len = state->datablock_size;
1457 1458 1459
		else
			chunk_len = num_bytes;

1460 1461
		num_copies = btrfs_num_copies(fs_info, next_bytenr,
					      state->datablock_size);
1462
		if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
1463
			pr_info("num_copies(log_bytenr=%llu) = %d\n",
1464
			       next_bytenr, num_copies);
1465 1466 1467 1468 1469 1470
		for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
			struct btrfsic_block_data_ctx next_block_ctx;
			struct btrfsic_block *next_block;
			int block_was_created;

			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1471 1472
				pr_info("btrfsic_handle_extent_data(mirror_num=%d)\n",
					mirror_num);
1473
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERY_VERBOSE)
1474
				pr_info("\tdisk_bytenr = %llu, num_bytes %u\n",
1475
				       next_bytenr, chunk_len);
1476 1477 1478 1479
			ret = btrfsic_map_block(state, next_bytenr,
						chunk_len, &next_block_ctx,
						mirror_num);
			if (ret) {
1480
				pr_info("btrfsic: btrfsic_map_block(@%llu, mirror=%d) failed!\n",
1481
				       next_bytenr, mirror_num);
1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494
				return -1;
			}

			next_block = btrfsic_block_lookup_or_add(
					state,
					&next_block_ctx,
					"referenced ",
					0,
					force_iodone_flag,
					!force_iodone_flag,
					mirror_num,
					&block_was_created);
			if (NULL == next_block) {
1495
				pr_info("btrfsic: error, kmalloc failed!\n");
1496 1497 1498 1499
				btrfsic_release_block_ctx(&next_block_ctx);
				return -1;
			}
			if (!block_was_created) {
1500 1501 1502
				if ((state->print_mask &
				     BTRFSIC_PRINT_MASK_VERBOSE) &&
				    next_block->logical_bytenr != next_bytenr &&
1503 1504
				    !(!next_block->is_metadata &&
				      0 == next_block->logical_bytenr)) {
1505
					pr_info("Referenced block @%llu (%s/%llu/%d) found in hash table, D, bytenr mismatch (!= stored %llu).\n",
1506
					       next_bytenr,
1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535
					       next_block_ctx.dev->name,
					       next_block_ctx.dev_bytenr,
					       mirror_num,
					       next_block->logical_bytenr);
				}
				next_block->logical_bytenr = next_bytenr;
				next_block->mirror_num = mirror_num;
			}

			l = btrfsic_block_link_lookup_or_add(state,
							     &next_block_ctx,
							     next_block, block,
							     generation);
			btrfsic_release_block_ctx(&next_block_ctx);
			if (NULL == l)
				return -1;
		}

		next_bytenr += chunk_len;
		num_bytes -= chunk_len;
	}

	return 0;
}

static int btrfsic_map_block(struct btrfsic_state *state, u64 bytenr, u32 len,
			     struct btrfsic_block_data_ctx *block_ctx_out,
			     int mirror_num)
{
1536
	struct btrfs_fs_info *fs_info = state->fs_info;
1537 1538 1539 1540 1541 1542
	int ret;
	u64 length;
	struct btrfs_bio *multi = NULL;
	struct btrfs_device *device;

	length = len;
1543
	ret = btrfs_map_block(fs_info, BTRFS_MAP_READ,
1544 1545
			      bytenr, &length, &multi, mirror_num);

1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557
	if (ret) {
		block_ctx_out->start = 0;
		block_ctx_out->dev_bytenr = 0;
		block_ctx_out->len = 0;
		block_ctx_out->dev = NULL;
		block_ctx_out->datav = NULL;
		block_ctx_out->pagev = NULL;
		block_ctx_out->mem_to_free = NULL;

		return ret;
	}

1558 1559 1560 1561 1562
	device = multi->stripes[0].dev;
	block_ctx_out->dev = btrfsic_dev_state_lookup(device->bdev);
	block_ctx_out->dev_bytenr = multi->stripes[0].physical;
	block_ctx_out->start = bytenr;
	block_ctx_out->len = len;
1563 1564 1565
	block_ctx_out->datav = NULL;
	block_ctx_out->pagev = NULL;
	block_ctx_out->mem_to_free = NULL;
1566

1567
	kfree(multi);
1568 1569
	if (NULL == block_ctx_out->dev) {
		ret = -ENXIO;
1570
		pr_info("btrfsic: error, cannot lookup dev (#1)!\n");
1571 1572 1573 1574 1575 1576 1577
	}

	return ret;
}

static void btrfsic_release_block_ctx(struct btrfsic_block_data_ctx *block_ctx)
{
1578 1579 1580 1581 1582
	if (block_ctx->mem_to_free) {
		unsigned int num_pages;

		BUG_ON(!block_ctx->datav);
		BUG_ON(!block_ctx->pagev);
1583 1584
		num_pages = (block_ctx->len + (u64)PAGE_SIZE - 1) >>
			    PAGE_SHIFT;
1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600
		while (num_pages > 0) {
			num_pages--;
			if (block_ctx->datav[num_pages]) {
				kunmap(block_ctx->pagev[num_pages]);
				block_ctx->datav[num_pages] = NULL;
			}
			if (block_ctx->pagev[num_pages]) {
				__free_page(block_ctx->pagev[num_pages]);
				block_ctx->pagev[num_pages] = NULL;
			}
		}

		kfree(block_ctx->mem_to_free);
		block_ctx->mem_to_free = NULL;
		block_ctx->pagev = NULL;
		block_ctx->datav = NULL;
1601 1602 1603 1604 1605 1606
	}
}

static int btrfsic_read_block(struct btrfsic_state *state,
			      struct btrfsic_block_data_ctx *block_ctx)
{
1607 1608 1609 1610 1611 1612 1613 1614
	unsigned int num_pages;
	unsigned int i;
	u64 dev_bytenr;
	int ret;

	BUG_ON(block_ctx->datav);
	BUG_ON(block_ctx->pagev);
	BUG_ON(block_ctx->mem_to_free);
1615
	if (block_ctx->dev_bytenr & ((u64)PAGE_SIZE - 1)) {
1616
		pr_info("btrfsic: read_block() with unaligned bytenr %llu\n",
1617
		       block_ctx->dev_bytenr);
1618 1619
		return -1;
	}
1620

1621 1622
	num_pages = (block_ctx->len + (u64)PAGE_SIZE - 1) >>
		    PAGE_SHIFT;
1623 1624 1625 1626
	block_ctx->mem_to_free = kzalloc((sizeof(*block_ctx->datav) +
					  sizeof(*block_ctx->pagev)) *
					 num_pages, GFP_NOFS);
	if (!block_ctx->mem_to_free)
1627
		return -ENOMEM;
1628 1629 1630 1631 1632 1633
	block_ctx->datav = block_ctx->mem_to_free;
	block_ctx->pagev = (struct page **)(block_ctx->datav + num_pages);
	for (i = 0; i < num_pages; i++) {
		block_ctx->pagev[i] = alloc_page(GFP_NOFS);
		if (!block_ctx->pagev[i])
			return -1;
1634 1635
	}

1636 1637 1638 1639 1640
	dev_bytenr = block_ctx->dev_bytenr;
	for (i = 0; i < num_pages;) {
		struct bio *bio;
		unsigned int j;

1641
		bio = btrfs_io_bio_alloc(GFP_NOFS, num_pages - i);
1642
		if (!bio) {
1643
			pr_info("btrfsic: bio_alloc() for %u pages failed!\n",
1644 1645 1646 1647
			       num_pages - i);
			return -1;
		}
		bio->bi_bdev = block_ctx->dev->bdev;
1648
		bio->bi_iter.bi_sector = dev_bytenr >> 9;
M
Mike Christie 已提交
1649
		bio_set_op_attrs(bio, REQ_OP_READ, 0);
1650 1651 1652

		for (j = i; j < num_pages; j++) {
			ret = bio_add_page(bio, block_ctx->pagev[j],
1653 1654
					   PAGE_SIZE, 0);
			if (PAGE_SIZE != ret)
1655 1656 1657
				break;
		}
		if (j == i) {
1658
			pr_info("btrfsic: error, failed to add a single page!\n");
1659 1660
			return -1;
		}
1661
		if (submit_bio_wait(bio)) {
1662
			pr_info("btrfsic: read error at logical %llu dev %s!\n",
1663 1664 1665 1666 1667
			       block_ctx->start, block_ctx->dev->name);
			bio_put(bio);
			return -1;
		}
		bio_put(bio);
1668
		dev_bytenr += (j - i) * PAGE_SIZE;
1669 1670
		i = j;
	}
F
Fabian Frederick 已提交
1671
	for (i = 0; i < num_pages; i++)
1672
		block_ctx->datav[i] = kmap(block_ctx->pagev[i]);
1673 1674 1675 1676 1677 1678

	return block_ctx->len;
}

static void btrfsic_dump_database(struct btrfsic_state *state)
{
1679
	const struct btrfsic_block *b_all;
1680 1681 1682

	BUG_ON(NULL == state);

1683
	pr_info("all_blocks_list:\n");
1684 1685
	list_for_each_entry(b_all, &state->all_blocks_list, all_blocks_node) {
		const struct btrfsic_block_link *l;
1686

1687
		pr_info("%c-block @%llu (%s/%llu/%d)\n",
1688
		       btrfsic_get_block_type(state, b_all),
1689 1690
		       b_all->logical_bytenr, b_all->dev_state->name,
		       b_all->dev_bytenr, b_all->mirror_num);
1691

1692
		list_for_each_entry(l, &b_all->ref_to_list, node_ref_to) {
1693
			pr_info(" %c @%llu (%s/%llu/%d) refers %u* to %c @%llu (%s/%llu/%d)\n",
1694
			       btrfsic_get_block_type(state, b_all),
1695 1696
			       b_all->logical_bytenr, b_all->dev_state->name,
			       b_all->dev_bytenr, b_all->mirror_num,
1697 1698 1699 1700
			       l->ref_cnt,
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
1701
			       l->block_ref_to->dev_bytenr,
1702 1703 1704
			       l->block_ref_to->mirror_num);
		}

1705
		list_for_each_entry(l, &b_all->ref_from_list, node_ref_from) {
1706
			pr_info(" %c @%llu (%s/%llu/%d) is ref %u* from %c @%llu (%s/%llu/%d)\n",
1707
			       btrfsic_get_block_type(state, b_all),
1708 1709
			       b_all->logical_bytenr, b_all->dev_state->name,
			       b_all->dev_bytenr, b_all->mirror_num,
1710 1711 1712 1713 1714 1715 1716 1717
			       l->ref_cnt,
			       btrfsic_get_block_type(state, l->block_ref_from),
			       l->block_ref_from->logical_bytenr,
			       l->block_ref_from->dev_state->name,
			       l->block_ref_from->dev_bytenr,
			       l->block_ref_from->mirror_num);
		}

1718
		pr_info("\n");
1719 1720 1721 1722 1723 1724 1725 1726
	}
}

/*
 * Test whether the disk block contains a tree block (leaf or node)
 * (note that this test fails for the super block)
 */
static int btrfsic_test_for_metadata(struct btrfsic_state *state,
1727
				     char **datav, unsigned int num_pages)
1728
{
1729
	struct btrfs_fs_info *fs_info = state->fs_info;
1730 1731 1732
	struct btrfs_header *h;
	u8 csum[BTRFS_CSUM_SIZE];
	u32 crc = ~(u32)0;
1733
	unsigned int i;
1734

1735
	if (num_pages * PAGE_SIZE < state->metablock_size)
1736
		return 1; /* not metadata */
1737
	num_pages = state->metablock_size >> PAGE_SHIFT;
1738
	h = (struct btrfs_header *)datav[0];
1739

1740
	if (memcmp(h->fsid, fs_info->fsid, BTRFS_UUID_SIZE))
1741
		return 1;
1742

1743 1744
	for (i = 0; i < num_pages; i++) {
		u8 *data = i ? datav[i] : (datav[i] + BTRFS_CSUM_SIZE);
1745 1746
		size_t sublen = i ? PAGE_SIZE :
				    (PAGE_SIZE - BTRFS_CSUM_SIZE);
1747

1748
		crc = btrfs_crc32c(crc, data, sublen);
1749
	}
1750 1751
	btrfs_csum_final(crc, csum);
	if (memcmp(csum, h->csum, state->csum_size))
1752
		return 1;
1753

1754
	return 0; /* is metadata */
1755 1756 1757
}

static void btrfsic_process_written_block(struct btrfsic_dev_state *dev_state,
1758 1759 1760
					  u64 dev_bytenr, char **mapped_datav,
					  unsigned int num_pages,
					  struct bio *bio, int *bio_is_patched,
1761 1762 1763 1764 1765 1766 1767 1768 1769
					  struct buffer_head *bh,
					  int submit_bio_bh_rw)
{
	int is_metadata;
	struct btrfsic_block *block;
	struct btrfsic_block_data_ctx block_ctx;
	int ret;
	struct btrfsic_state *state = dev_state->state;
	struct block_device *bdev = dev_state->bdev;
1770
	unsigned int processed_len;
1771 1772 1773 1774

	if (NULL != bio_is_patched)
		*bio_is_patched = 0;

1775 1776 1777 1778 1779 1780 1781 1782
again:
	if (num_pages == 0)
		return;

	processed_len = 0;
	is_metadata = (0 == btrfsic_test_for_metadata(state, mapped_datav,
						      num_pages));

1783 1784 1785
	block = btrfsic_block_hashtable_lookup(bdev, dev_bytenr,
					       &state->block_hashtable);
	if (NULL != block) {
1786
		u64 bytenr = 0;
1787
		struct btrfsic_block_link *l, *tmp;
1788 1789

		if (block->is_superblock) {
1790 1791
			bytenr = btrfs_super_bytenr((struct btrfs_super_block *)
						    mapped_datav[0]);
1792
			if (num_pages * PAGE_SIZE <
1793
			    BTRFS_SUPER_INFO_SIZE) {
1794
				pr_info("btrfsic: cannot work with too short bios!\n");
1795 1796
				return;
			}
1797
			is_metadata = 1;
1798
			BUG_ON(BTRFS_SUPER_INFO_SIZE & (PAGE_SIZE - 1));
1799
			processed_len = BTRFS_SUPER_INFO_SIZE;
1800 1801
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_TREE_BEFORE_SB_WRITE) {
1802
				pr_info("[before new superblock is written]:\n");
1803 1804 1805 1806 1807
				btrfsic_dump_tree_sub(state, block, 0);
			}
		}
		if (is_metadata) {
			if (!block->is_superblock) {
1808
				if (num_pages * PAGE_SIZE <
1809
				    state->metablock_size) {
1810
					pr_info("btrfsic: cannot work with too short bios!\n");
1811 1812 1813
					return;
				}
				processed_len = state->metablock_size;
1814 1815 1816
				bytenr = btrfs_stack_header_bytenr(
						(struct btrfs_header *)
						mapped_datav[0]);
1817 1818
				btrfsic_cmp_log_and_dev_bytenr(state, bytenr,
							       dev_state,
1819
							       dev_bytenr);
1820
			}
1821 1822 1823 1824
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE) {
				if (block->logical_bytenr != bytenr &&
				    !(!block->is_metadata &&
				      block->logical_bytenr == 0))
1825
					pr_info("Written block @%llu (%s/%llu/%d) found in hash table, %c, bytenr mismatch (!= stored %llu).\n",
1826 1827 1828 1829 1830 1831 1832
					       bytenr, dev_state->name,
					       dev_bytenr,
					       block->mirror_num,
					       btrfsic_get_block_type(state,
								      block),
					       block->logical_bytenr);
				else
1833
					pr_info("Written block @%llu (%s/%llu/%d) found in hash table, %c.\n",
1834 1835 1836 1837 1838
					       bytenr, dev_state->name,
					       dev_bytenr, block->mirror_num,
					       btrfsic_get_block_type(state,
								      block));
			}
1839
			block->logical_bytenr = bytenr;
1840
		} else {
1841
			if (num_pages * PAGE_SIZE <
1842
			    state->datablock_size) {
1843
				pr_info("btrfsic: cannot work with too short bios!\n");
1844 1845 1846
				return;
			}
			processed_len = state->datablock_size;
1847 1848
			bytenr = block->logical_bytenr;
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1849
				pr_info("Written block @%llu (%s/%llu/%d) found in hash table, %c.\n",
1850
				       bytenr, dev_state->name, dev_bytenr,
1851 1852 1853 1854 1855
				       block->mirror_num,
				       btrfsic_get_block_type(state, block));
		}

		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
1856
			pr_info("ref_to_list: %cE, ref_from_list: %cE\n",
1857 1858 1859
			       list_empty(&block->ref_to_list) ? ' ' : '!',
			       list_empty(&block->ref_from_list) ? ' ' : '!');
		if (btrfsic_is_block_ref_by_superblock(state, block, 0)) {
1860
			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",
1861 1862 1863
			       btrfsic_get_block_type(state, block), bytenr,
			       dev_state->name, dev_bytenr, block->mirror_num,
			       block->generation,
1864
			       btrfs_disk_key_objectid(&block->disk_key),
1865
			       block->disk_key.type,
1866 1867 1868
			       btrfs_disk_key_offset(&block->disk_key),
			       btrfs_stack_header_generation(
				       (struct btrfs_header *) mapped_datav[0]),
1869 1870 1871 1872 1873
			       state->max_superblock_generation);
			btrfsic_dump_tree(state);
		}

		if (!block->is_iodone && !block->never_written) {
1874
			pr_info("btrfs: attempt to overwrite %c-block @%llu (%s/%llu/%d), oldgen=%llu, newgen=%llu, which is not yet iodone!\n",
1875 1876 1877
			       btrfsic_get_block_type(state, block), bytenr,
			       dev_state->name, dev_bytenr, block->mirror_num,
			       block->generation,
1878 1879 1880
			       btrfs_stack_header_generation(
				       (struct btrfs_header *)
				       mapped_datav[0]));
1881 1882
			/* it would not be safe to go on */
			btrfsic_dump_tree(state);
1883
			goto continue_loop;
1884 1885 1886 1887 1888
		}

		/*
		 * Clear all references of this block. Do not free
		 * the block itself even if is not referenced anymore
1889
		 * because it still carries valuable information
1890 1891
		 * like whether it was ever written and IO completed.
		 */
1892 1893
		list_for_each_entry_safe(l, tmp, &block->ref_to_list,
					 node_ref_to) {
1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
				btrfsic_print_rem_link(state, l);
			l->ref_cnt--;
			if (0 == l->ref_cnt) {
				list_del(&l->node_ref_to);
				list_del(&l->node_ref_from);
				btrfsic_block_link_hashtable_remove(l);
				btrfsic_block_link_free(l);
			}
		}

		block_ctx.dev = dev_state;
		block_ctx.dev_bytenr = dev_bytenr;
1907 1908 1909 1910 1911
		block_ctx.start = bytenr;
		block_ctx.len = processed_len;
		block_ctx.pagev = NULL;
		block_ctx.mem_to_free = NULL;
		block_ctx.datav = mapped_datav;
1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962

		if (is_metadata || state->include_extent_data) {
			block->never_written = 0;
			block->iodone_w_error = 0;
			if (NULL != bio) {
				block->is_iodone = 0;
				BUG_ON(NULL == bio_is_patched);
				if (!*bio_is_patched) {
					block->orig_bio_bh_private =
					    bio->bi_private;
					block->orig_bio_bh_end_io.bio =
					    bio->bi_end_io;
					block->next_in_same_bio = NULL;
					bio->bi_private = block;
					bio->bi_end_io = btrfsic_bio_end_io;
					*bio_is_patched = 1;
				} else {
					struct btrfsic_block *chained_block =
					    (struct btrfsic_block *)
					    bio->bi_private;

					BUG_ON(NULL == chained_block);
					block->orig_bio_bh_private =
					    chained_block->orig_bio_bh_private;
					block->orig_bio_bh_end_io.bio =
					    chained_block->orig_bio_bh_end_io.
					    bio;
					block->next_in_same_bio = chained_block;
					bio->bi_private = block;
				}
			} else if (NULL != bh) {
				block->is_iodone = 0;
				block->orig_bio_bh_private = bh->b_private;
				block->orig_bio_bh_end_io.bh = bh->b_end_io;
				block->next_in_same_bio = NULL;
				bh->b_private = block;
				bh->b_end_io = btrfsic_bh_end_io;
			} else {
				block->is_iodone = 1;
				block->orig_bio_bh_private = NULL;
				block->orig_bio_bh_end_io.bio = NULL;
				block->next_in_same_bio = NULL;
			}
		}

		block->flush_gen = dev_state->last_flush_gen + 1;
		block->submit_bio_bh_rw = submit_bio_bh_rw;
		if (is_metadata) {
			block->logical_bytenr = bytenr;
			block->is_metadata = 1;
			if (block->is_superblock) {
1963
				BUG_ON(PAGE_SIZE !=
1964
				       BTRFS_SUPER_INFO_SIZE);
1965 1966 1967 1968
				ret = btrfsic_process_written_superblock(
						state,
						block,
						(struct btrfs_super_block *)
1969
						mapped_datav[0]);
1970 1971
				if (state->print_mask &
				    BTRFSIC_PRINT_MASK_TREE_AFTER_SB_WRITE) {
1972
					pr_info("[after new superblock is written]:\n");
1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983
					btrfsic_dump_tree_sub(state, block, 0);
				}
			} else {
				block->mirror_num = 0;	/* unknown */
				ret = btrfsic_process_metablock(
						state,
						block,
						&block_ctx,
						0, 0);
			}
			if (ret)
1984
				pr_info("btrfsic: btrfsic_process_metablock(root @%llu) failed!\n",
1985
				       dev_bytenr);
1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
		} else {
			block->is_metadata = 0;
			block->mirror_num = 0;	/* unknown */
			block->generation = BTRFSIC_GENERATION_UNKNOWN;
			if (!state->include_extent_data
			    && list_empty(&block->ref_from_list)) {
				/*
				 * disk block is overwritten with extent
				 * data (not meta data) and we are configured
				 * to not include extent data: take the
				 * chance and free the block's memory
				 */
				btrfsic_block_hashtable_remove(block);
				list_del(&block->all_blocks_node);
				btrfsic_block_free(block);
			}
		}
		btrfsic_release_block_ctx(&block_ctx);
	} else {
		/* block has not been found in hash table */
		u64 bytenr;

		if (!is_metadata) {
2009
			processed_len = state->datablock_size;
2010
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2011
				pr_info("Written block (%s/%llu/?) !found in hash table, D.\n",
2012
				       dev_state->name, dev_bytenr);
2013 2014 2015 2016
			if (!state->include_extent_data) {
				/* ignore that written D block */
				goto continue_loop;
			}
2017 2018 2019 2020 2021

			/* this is getting ugly for the
			 * include_extent_data case... */
			bytenr = 0;	/* unknown */
		} else {
2022
			processed_len = state->metablock_size;
2023 2024 2025
			bytenr = btrfs_stack_header_bytenr(
					(struct btrfs_header *)
					mapped_datav[0]);
2026
			btrfsic_cmp_log_and_dev_bytenr(state, bytenr, dev_state,
2027
						       dev_bytenr);
2028
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2029
				pr_info("Written block @%llu (%s/%llu/?) !found in hash table, M.\n",
2030
				       bytenr, dev_state->name, dev_bytenr);
2031
		}
2032

2033 2034
		block_ctx.dev = dev_state;
		block_ctx.dev_bytenr = dev_bytenr;
2035 2036 2037 2038 2039
		block_ctx.start = bytenr;
		block_ctx.len = processed_len;
		block_ctx.pagev = NULL;
		block_ctx.mem_to_free = NULL;
		block_ctx.datav = mapped_datav;
2040 2041 2042

		block = btrfsic_block_alloc();
		if (NULL == block) {
2043
			pr_info("btrfsic: error, kmalloc failed!\n");
2044
			btrfsic_release_block_ctx(&block_ctx);
2045
			goto continue_loop;
2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092
		}
		block->dev_state = dev_state;
		block->dev_bytenr = dev_bytenr;
		block->logical_bytenr = bytenr;
		block->is_metadata = is_metadata;
		block->never_written = 0;
		block->iodone_w_error = 0;
		block->mirror_num = 0;	/* unknown */
		block->flush_gen = dev_state->last_flush_gen + 1;
		block->submit_bio_bh_rw = submit_bio_bh_rw;
		if (NULL != bio) {
			block->is_iodone = 0;
			BUG_ON(NULL == bio_is_patched);
			if (!*bio_is_patched) {
				block->orig_bio_bh_private = bio->bi_private;
				block->orig_bio_bh_end_io.bio = bio->bi_end_io;
				block->next_in_same_bio = NULL;
				bio->bi_private = block;
				bio->bi_end_io = btrfsic_bio_end_io;
				*bio_is_patched = 1;
			} else {
				struct btrfsic_block *chained_block =
				    (struct btrfsic_block *)
				    bio->bi_private;

				BUG_ON(NULL == chained_block);
				block->orig_bio_bh_private =
				    chained_block->orig_bio_bh_private;
				block->orig_bio_bh_end_io.bio =
				    chained_block->orig_bio_bh_end_io.bio;
				block->next_in_same_bio = chained_block;
				bio->bi_private = block;
			}
		} else if (NULL != bh) {
			block->is_iodone = 0;
			block->orig_bio_bh_private = bh->b_private;
			block->orig_bio_bh_end_io.bh = bh->b_end_io;
			block->next_in_same_bio = NULL;
			bh->b_private = block;
			bh->b_end_io = btrfsic_bh_end_io;
		} else {
			block->is_iodone = 1;
			block->orig_bio_bh_private = NULL;
			block->orig_bio_bh_end_io.bio = NULL;
			block->next_in_same_bio = NULL;
		}
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2093
			pr_info("New written %c-block @%llu (%s/%llu/%d)\n",
2094
			       is_metadata ? 'M' : 'D',
2095 2096
			       block->logical_bytenr, block->dev_state->name,
			       block->dev_bytenr, block->mirror_num);
2097 2098 2099 2100 2101
		list_add(&block->all_blocks_node, &state->all_blocks_list);
		btrfsic_block_hashtable_add(block, &state->block_hashtable);

		if (is_metadata) {
			ret = btrfsic_process_metablock(state, block,
2102
							&block_ctx, 0, 0);
2103
			if (ret)
2104
				pr_info("btrfsic: process_metablock(root @%llu) failed!\n",
2105
				       dev_bytenr);
2106 2107 2108
		}
		btrfsic_release_block_ctx(&block_ctx);
	}
2109 2110 2111 2112

continue_loop:
	BUG_ON(!processed_len);
	dev_bytenr += processed_len;
2113 2114
	mapped_datav += processed_len >> PAGE_SHIFT;
	num_pages -= processed_len >> PAGE_SHIFT;
2115
	goto again;
2116 2117
}

2118
static void btrfsic_bio_end_io(struct bio *bp)
2119 2120 2121 2122 2123 2124 2125
{
	struct btrfsic_block *block = (struct btrfsic_block *)bp->bi_private;
	int iodone_w_error;

	/* mutex is not held! This is not save if IO is not yet completed
	 * on umount */
	iodone_w_error = 0;
2126
	if (bp->bi_error)
2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138
		iodone_w_error = 1;

	BUG_ON(NULL == block);
	bp->bi_private = block->orig_bio_bh_private;
	bp->bi_end_io = block->orig_bio_bh_end_io.bio;

	do {
		struct btrfsic_block *next_block;
		struct btrfsic_dev_state *const dev_state = block->dev_state;

		if ((dev_state->state->print_mask &
		     BTRFSIC_PRINT_MASK_END_IO_BIO_BH))
2139
			pr_info("bio_end_io(err=%d) for %c @%llu (%s/%llu/%d)\n",
2140
			       bp->bi_error,
2141
			       btrfsic_get_block_type(dev_state->state, block),
2142 2143
			       block->logical_bytenr, dev_state->name,
			       block->dev_bytenr, block->mirror_num);
2144 2145
		next_block = block->next_in_same_bio;
		block->iodone_w_error = iodone_w_error;
2146
		if (block->submit_bio_bh_rw & REQ_PREFLUSH) {
2147 2148 2149
			dev_state->last_flush_gen++;
			if ((dev_state->state->print_mask &
			     BTRFSIC_PRINT_MASK_END_IO_BIO_BH))
2150
				pr_info("bio_end_io() new %s flush_gen=%llu\n",
2151 2152 2153 2154 2155 2156 2157 2158 2159 2160
				       dev_state->name,
				       dev_state->last_flush_gen);
		}
		if (block->submit_bio_bh_rw & REQ_FUA)
			block->flush_gen = 0; /* FUA completed means block is
					       * on disk */
		block->is_iodone = 1; /* for FLUSH, this releases the block */
		block = next_block;
	} while (NULL != block);

2161
	bp->bi_end_io(bp);
2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172
}

static void btrfsic_bh_end_io(struct buffer_head *bh, int uptodate)
{
	struct btrfsic_block *block = (struct btrfsic_block *)bh->b_private;
	int iodone_w_error = !uptodate;
	struct btrfsic_dev_state *dev_state;

	BUG_ON(NULL == block);
	dev_state = block->dev_state;
	if ((dev_state->state->print_mask & BTRFSIC_PRINT_MASK_END_IO_BIO_BH))
2173
		pr_info("bh_end_io(error=%d) for %c @%llu (%s/%llu/%d)\n",
2174 2175
		       iodone_w_error,
		       btrfsic_get_block_type(dev_state->state, block),
2176 2177
		       block->logical_bytenr, block->dev_state->name,
		       block->dev_bytenr, block->mirror_num);
2178 2179

	block->iodone_w_error = iodone_w_error;
2180
	if (block->submit_bio_bh_rw & REQ_PREFLUSH) {
2181 2182 2183
		dev_state->last_flush_gen++;
		if ((dev_state->state->print_mask &
		     BTRFSIC_PRINT_MASK_END_IO_BIO_BH))
2184
			pr_info("bh_end_io() new %s flush_gen=%llu\n",
2185
			       dev_state->name, dev_state->last_flush_gen);
2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200
	}
	if (block->submit_bio_bh_rw & REQ_FUA)
		block->flush_gen = 0; /* FUA completed means block is on disk */

	bh->b_private = block->orig_bio_bh_private;
	bh->b_end_io = block->orig_bio_bh_end_io.bh;
	block->is_iodone = 1; /* for FLUSH, this releases the block */
	bh->b_end_io(bh, uptodate);
}

static int btrfsic_process_written_superblock(
		struct btrfsic_state *state,
		struct btrfsic_block *const superblock,
		struct btrfs_super_block *const super_hdr)
{
2201
	struct btrfs_fs_info *fs_info = state->fs_info;
2202 2203 2204 2205 2206 2207
	int pass;

	superblock->generation = btrfs_super_generation(super_hdr);
	if (!(superblock->generation > state->max_superblock_generation ||
	      0 == state->max_superblock_generation)) {
		if (state->print_mask & BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE)
2208
			pr_info("btrfsic: superblock @%llu (%s/%llu/%d) with old gen %llu <= %llu\n",
2209
			       superblock->logical_bytenr,
2210
			       superblock->dev_state->name,
2211
			       superblock->dev_bytenr, superblock->mirror_num,
2212 2213 2214 2215
			       btrfs_super_generation(super_hdr),
			       state->max_superblock_generation);
	} else {
		if (state->print_mask & BTRFSIC_PRINT_MASK_SUPERBLOCK_WRITE)
2216
			pr_info("btrfsic: got new superblock @%llu (%s/%llu/%d) with new gen %llu > %llu\n",
2217
			       superblock->logical_bytenr,
2218
			       superblock->dev_state->name,
2219
			       superblock->dev_bytenr, superblock->mirror_num,
2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236
			       btrfs_super_generation(super_hdr),
			       state->max_superblock_generation);

		state->max_superblock_generation =
		    btrfs_super_generation(super_hdr);
		state->latest_superblock = superblock;
	}

	for (pass = 0; pass < 3; pass++) {
		int ret;
		u64 next_bytenr;
		struct btrfsic_block *next_block;
		struct btrfsic_block_data_ctx tmp_next_block_ctx;
		struct btrfsic_block_link *l;
		int num_copies;
		int mirror_num;
		const char *additional_string = NULL;
2237
		struct btrfs_disk_key tmp_disk_key = {0};
2238

2239 2240 2241
		btrfs_set_disk_key_objectid(&tmp_disk_key,
					    BTRFS_ROOT_ITEM_KEY);
		btrfs_set_disk_key_objectid(&tmp_disk_key, 0);
2242 2243 2244

		switch (pass) {
		case 0:
2245 2246
			btrfs_set_disk_key_objectid(&tmp_disk_key,
						    BTRFS_ROOT_TREE_OBJECTID);
2247 2248 2249 2250
			additional_string = "root ";
			next_bytenr = btrfs_super_root(super_hdr);
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
2251
				pr_info("root@%llu\n", next_bytenr);
2252 2253
			break;
		case 1:
2254 2255
			btrfs_set_disk_key_objectid(&tmp_disk_key,
						    BTRFS_CHUNK_TREE_OBJECTID);
2256 2257 2258 2259
			additional_string = "chunk ";
			next_bytenr = btrfs_super_chunk_root(super_hdr);
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
2260
				pr_info("chunk@%llu\n", next_bytenr);
2261 2262
			break;
		case 2:
2263 2264
			btrfs_set_disk_key_objectid(&tmp_disk_key,
						    BTRFS_TREE_LOG_OBJECTID);
2265 2266 2267 2268 2269 2270
			additional_string = "log ";
			next_bytenr = btrfs_super_log_root(super_hdr);
			if (0 == next_bytenr)
				continue;
			if (state->print_mask &
			    BTRFSIC_PRINT_MASK_ROOT_CHUNK_LOG_TREE_LOCATION)
2271
				pr_info("log@%llu\n", next_bytenr);
2272 2273 2274
			break;
		}

2275 2276
		num_copies = btrfs_num_copies(fs_info, next_bytenr,
					      BTRFS_SUPER_INFO_SIZE);
2277
		if (state->print_mask & BTRFSIC_PRINT_MASK_NUM_COPIES)
2278
			pr_info("num_copies(log_bytenr=%llu) = %d\n",
2279
			       next_bytenr, num_copies);
2280 2281 2282 2283
		for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
			int was_created;

			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2284
				pr_info("btrfsic_process_written_superblock(mirror_num=%d)\n", mirror_num);
2285 2286
			ret = btrfsic_map_block(state, next_bytenr,
						BTRFS_SUPER_INFO_SIZE,
2287 2288 2289
						&tmp_next_block_ctx,
						mirror_num);
			if (ret) {
2290
				pr_info("btrfsic: btrfsic_map_block(@%llu, mirror=%d) failed!\n",
2291
				       next_bytenr, mirror_num);
2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302
				return -1;
			}

			next_block = btrfsic_block_lookup_or_add(
					state,
					&tmp_next_block_ctx,
					additional_string,
					1, 0, 1,
					mirror_num,
					&was_created);
			if (NULL == next_block) {
2303
				pr_info("btrfsic: error, kmalloc failed!\n");
2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323
				btrfsic_release_block_ctx(&tmp_next_block_ctx);
				return -1;
			}

			next_block->disk_key = tmp_disk_key;
			if (was_created)
				next_block->generation =
				    BTRFSIC_GENERATION_UNKNOWN;
			l = btrfsic_block_link_lookup_or_add(
					state,
					&tmp_next_block_ctx,
					next_block,
					superblock,
					BTRFSIC_GENERATION_UNKNOWN);
			btrfsic_release_block_ctx(&tmp_next_block_ctx);
			if (NULL == l)
				return -1;
		}
	}

2324
	if (WARN_ON(-1 == btrfsic_check_all_ref_blocks(state, superblock, 0)))
2325 2326 2327 2328 2329 2330 2331 2332 2333
		btrfsic_dump_tree(state);

	return 0;
}

static int btrfsic_check_all_ref_blocks(struct btrfsic_state *state,
					struct btrfsic_block *const block,
					int recursion_level)
{
2334
	const struct btrfsic_block_link *l;
2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351
	int ret = 0;

	if (recursion_level >= 3 + BTRFS_MAX_LEVEL) {
		/*
		 * Note that this situation can happen and does not
		 * indicate an error in regular cases. It happens
		 * when disk blocks are freed and later reused.
		 * The check-integrity module is not aware of any
		 * block free operations, it just recognizes block
		 * write operations. Therefore it keeps the linkage
		 * information for a block until a block is
		 * rewritten. This can temporarily cause incorrect
		 * and even circular linkage informations. This
		 * causes no harm unless such blocks are referenced
		 * by the most recent super block.
		 */
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2352
			pr_info("btrfsic: abort cyclic linkage (case 1).\n");
2353 2354 2355 2356 2357 2358 2359 2360

		return ret;
	}

	/*
	 * This algorithm is recursive because the amount of used stack
	 * space is very small and the max recursion depth is limited.
	 */
2361
	list_for_each_entry(l, &block->ref_to_list, node_ref_to) {
2362
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2363
			pr_info("rl=%d, %c @%llu (%s/%llu/%d) %u* refers to %c @%llu (%s/%llu/%d)\n",
2364 2365
			       recursion_level,
			       btrfsic_get_block_type(state, block),
2366 2367
			       block->logical_bytenr, block->dev_state->name,
			       block->dev_bytenr, block->mirror_num,
2368 2369 2370 2371
			       l->ref_cnt,
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
2372
			       l->block_ref_to->dev_bytenr,
2373 2374
			       l->block_ref_to->mirror_num);
		if (l->block_ref_to->never_written) {
2375
			pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which is never written!\n",
2376 2377 2378
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
2379
			       l->block_ref_to->dev_bytenr,
2380 2381 2382
			       l->block_ref_to->mirror_num);
			ret = -1;
		} else if (!l->block_ref_to->is_iodone) {
2383
			pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which is not yet iodone!\n",
2384 2385 2386
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
2387
			       l->block_ref_to->dev_bytenr,
2388 2389
			       l->block_ref_to->mirror_num);
			ret = -1;
2390
		} else if (l->block_ref_to->iodone_w_error) {
2391
			pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) which has write error!\n",
2392 2393 2394
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
2395
			       l->block_ref_to->dev_bytenr,
2396 2397
			       l->block_ref_to->mirror_num);
			ret = -1;
2398 2399 2400 2401 2402 2403
		} else if (l->parent_generation !=
			   l->block_ref_to->generation &&
			   BTRFSIC_GENERATION_UNKNOWN !=
			   l->parent_generation &&
			   BTRFSIC_GENERATION_UNKNOWN !=
			   l->block_ref_to->generation) {
2404
			pr_info("btrfs: attempt to write superblock which references block %c @%llu (%s/%llu/%d) with generation %llu != parent generation %llu!\n",
2405 2406 2407
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
2408
			       l->block_ref_to->dev_bytenr,
2409
			       l->block_ref_to->mirror_num,
2410 2411
			       l->block_ref_to->generation,
			       l->parent_generation);
2412 2413 2414
			ret = -1;
		} else if (l->block_ref_to->flush_gen >
			   l->block_ref_to->dev_state->last_flush_gen) {
2415
			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",
2416 2417 2418
			       btrfsic_get_block_type(state, l->block_ref_to),
			       l->block_ref_to->logical_bytenr,
			       l->block_ref_to->dev_state->name,
2419 2420
			       l->block_ref_to->dev_bytenr,
			       l->block_ref_to->mirror_num, block->flush_gen,
2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438
			       l->block_ref_to->dev_state->last_flush_gen);
			ret = -1;
		} else if (-1 == btrfsic_check_all_ref_blocks(state,
							      l->block_ref_to,
							      recursion_level +
							      1)) {
			ret = -1;
		}
	}

	return ret;
}

static int btrfsic_is_block_ref_by_superblock(
		const struct btrfsic_state *state,
		const struct btrfsic_block *block,
		int recursion_level)
{
2439
	const struct btrfsic_block_link *l;
2440 2441 2442 2443

	if (recursion_level >= 3 + BTRFS_MAX_LEVEL) {
		/* refer to comment at "abort cyclic linkage (case 1)" */
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2444
			pr_info("btrfsic: abort cyclic linkage (case 2).\n");
2445 2446 2447 2448 2449 2450 2451 2452

		return 0;
	}

	/*
	 * This algorithm is recursive because the amount of used stack space
	 * is very small and the max recursion depth is limited.
	 */
2453
	list_for_each_entry(l, &block->ref_from_list, node_ref_from) {
2454
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2455
			pr_info("rl=%d, %c @%llu (%s/%llu/%d) is ref %u* from %c @%llu (%s/%llu/%d)\n",
2456 2457
			       recursion_level,
			       btrfsic_get_block_type(state, block),
2458 2459
			       block->logical_bytenr, block->dev_state->name,
			       block->dev_bytenr, block->mirror_num,
2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484
			       l->ref_cnt,
			       btrfsic_get_block_type(state, l->block_ref_from),
			       l->block_ref_from->logical_bytenr,
			       l->block_ref_from->dev_state->name,
			       l->block_ref_from->dev_bytenr,
			       l->block_ref_from->mirror_num);
		if (l->block_ref_from->is_superblock &&
		    state->latest_superblock->dev_bytenr ==
		    l->block_ref_from->dev_bytenr &&
		    state->latest_superblock->dev_state->bdev ==
		    l->block_ref_from->dev_state->bdev)
			return 1;
		else if (btrfsic_is_block_ref_by_superblock(state,
							    l->block_ref_from,
							    recursion_level +
							    1))
			return 1;
	}

	return 0;
}

static void btrfsic_print_add_link(const struct btrfsic_state *state,
				   const struct btrfsic_block_link *l)
{
2485
	pr_info("Add %u* link from %c @%llu (%s/%llu/%d) to %c @%llu (%s/%llu/%d).\n",
2486 2487
	       l->ref_cnt,
	       btrfsic_get_block_type(state, l->block_ref_from),
2488
	       l->block_ref_from->logical_bytenr,
2489
	       l->block_ref_from->dev_state->name,
2490
	       l->block_ref_from->dev_bytenr, l->block_ref_from->mirror_num,
2491
	       btrfsic_get_block_type(state, l->block_ref_to),
2492 2493
	       l->block_ref_to->logical_bytenr,
	       l->block_ref_to->dev_state->name, l->block_ref_to->dev_bytenr,
2494 2495 2496 2497 2498 2499
	       l->block_ref_to->mirror_num);
}

static void btrfsic_print_rem_link(const struct btrfsic_state *state,
				   const struct btrfsic_block_link *l)
{
2500
	pr_info("Rem %u* link from %c @%llu (%s/%llu/%d) to %c @%llu (%s/%llu/%d).\n",
2501 2502
	       l->ref_cnt,
	       btrfsic_get_block_type(state, l->block_ref_from),
2503
	       l->block_ref_from->logical_bytenr,
2504
	       l->block_ref_from->dev_state->name,
2505
	       l->block_ref_from->dev_bytenr, l->block_ref_from->mirror_num,
2506
	       btrfsic_get_block_type(state, l->block_ref_to),
2507 2508
	       l->block_ref_to->logical_bytenr,
	       l->block_ref_to->dev_state->name, l->block_ref_to->dev_bytenr,
2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535
	       l->block_ref_to->mirror_num);
}

static char btrfsic_get_block_type(const struct btrfsic_state *state,
				   const struct btrfsic_block *block)
{
	if (block->is_superblock &&
	    state->latest_superblock->dev_bytenr == block->dev_bytenr &&
	    state->latest_superblock->dev_state->bdev == block->dev_state->bdev)
		return 'S';
	else if (block->is_superblock)
		return 's';
	else if (block->is_metadata)
		return 'M';
	else
		return 'D';
}

static void btrfsic_dump_tree(const struct btrfsic_state *state)
{
	btrfsic_dump_tree_sub(state, state->latest_superblock, 0);
}

static void btrfsic_dump_tree_sub(const struct btrfsic_state *state,
				  const struct btrfsic_block *block,
				  int indent_level)
{
2536
	const struct btrfsic_block_link *l;
2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549
	int indent_add;
	static char buf[80];
	int cursor_position;

	/*
	 * Should better fill an on-stack buffer with a complete line and
	 * dump it at once when it is time to print a newline character.
	 */

	/*
	 * This algorithm is recursive because the amount of used stack space
	 * is very small and the max recursion depth is limited.
	 */
2550
	indent_add = sprintf(buf, "%c-%llu(%s/%llu/%u)",
2551
			     btrfsic_get_block_type(state, block),
2552 2553
			     block->logical_bytenr, block->dev_state->name,
			     block->dev_bytenr, block->mirror_num);
2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570
	if (indent_level + indent_add > BTRFSIC_TREE_DUMP_MAX_INDENT_LEVEL) {
		printk("[...]\n");
		return;
	}
	printk(buf);
	indent_level += indent_add;
	if (list_empty(&block->ref_to_list)) {
		printk("\n");
		return;
	}
	if (block->mirror_num > 1 &&
	    !(state->print_mask & BTRFSIC_PRINT_MASK_TREE_WITH_ALL_MIRRORS)) {
		printk(" [...]\n");
		return;
	}

	cursor_position = indent_level;
2571
	list_for_each_entry(l, &block->ref_to_list, node_ref_to) {
2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611
		while (cursor_position < indent_level) {
			printk(" ");
			cursor_position++;
		}
		if (l->ref_cnt > 1)
			indent_add = sprintf(buf, " %d*--> ", l->ref_cnt);
		else
			indent_add = sprintf(buf, " --> ");
		if (indent_level + indent_add >
		    BTRFSIC_TREE_DUMP_MAX_INDENT_LEVEL) {
			printk("[...]\n");
			cursor_position = 0;
			continue;
		}

		printk(buf);

		btrfsic_dump_tree_sub(state, l->block_ref_to,
				      indent_level + indent_add);
		cursor_position = 0;
	}
}

static struct btrfsic_block_link *btrfsic_block_link_lookup_or_add(
		struct btrfsic_state *state,
		struct btrfsic_block_data_ctx *next_block_ctx,
		struct btrfsic_block *next_block,
		struct btrfsic_block *from_block,
		u64 parent_generation)
{
	struct btrfsic_block_link *l;

	l = btrfsic_block_link_hashtable_lookup(next_block_ctx->dev->bdev,
						next_block_ctx->dev_bytenr,
						from_block->dev_state->bdev,
						from_block->dev_bytenr,
						&state->block_link_hashtable);
	if (NULL == l) {
		l = btrfsic_block_link_alloc();
		if (NULL == l) {
2612
			pr_info("btrfsic: error, kmalloc failed!\n");
2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658
			return NULL;
		}

		l->block_ref_to = next_block;
		l->block_ref_from = from_block;
		l->ref_cnt = 1;
		l->parent_generation = parent_generation;

		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
			btrfsic_print_add_link(state, l);

		list_add(&l->node_ref_to, &from_block->ref_to_list);
		list_add(&l->node_ref_from, &next_block->ref_from_list);

		btrfsic_block_link_hashtable_add(l,
						 &state->block_link_hashtable);
	} else {
		l->ref_cnt++;
		l->parent_generation = parent_generation;
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
			btrfsic_print_add_link(state, l);
	}

	return l;
}

static struct btrfsic_block *btrfsic_block_lookup_or_add(
		struct btrfsic_state *state,
		struct btrfsic_block_data_ctx *block_ctx,
		const char *additional_string,
		int is_metadata,
		int is_iodone,
		int never_written,
		int mirror_num,
		int *was_created)
{
	struct btrfsic_block *block;

	block = btrfsic_block_hashtable_lookup(block_ctx->dev->bdev,
					       block_ctx->dev_bytenr,
					       &state->block_hashtable);
	if (NULL == block) {
		struct btrfsic_dev_state *dev_state;

		block = btrfsic_block_alloc();
		if (NULL == block) {
2659
			pr_info("btrfsic: error, kmalloc failed!\n");
2660 2661 2662 2663
			return NULL;
		}
		dev_state = btrfsic_dev_state_lookup(block_ctx->dev->bdev);
		if (NULL == dev_state) {
2664
			pr_info("btrfsic: error, lookup dev_state failed!\n");
2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675
			btrfsic_block_free(block);
			return NULL;
		}
		block->dev_state = dev_state;
		block->dev_bytenr = block_ctx->dev_bytenr;
		block->logical_bytenr = block_ctx->start;
		block->is_metadata = is_metadata;
		block->is_iodone = is_iodone;
		block->never_written = never_written;
		block->mirror_num = mirror_num;
		if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
2676
			pr_info("New %s%c-block @%llu (%s/%llu/%d)\n",
2677 2678
			       additional_string,
			       btrfsic_get_block_type(state, block),
2679 2680
			       block->logical_bytenr, dev_state->name,
			       block->dev_bytenr, mirror_num);
2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695
		list_add(&block->all_blocks_node, &state->all_blocks_list);
		btrfsic_block_hashtable_add(block, &state->block_hashtable);
		if (NULL != was_created)
			*was_created = 1;
	} else {
		if (NULL != was_created)
			*was_created = 0;
	}

	return block;
}

static void btrfsic_cmp_log_and_dev_bytenr(struct btrfsic_state *state,
					   u64 bytenr,
					   struct btrfsic_dev_state *dev_state,
2696
					   u64 dev_bytenr)
2697
{
2698 2699
	struct btrfs_fs_info *fs_info = state->fs_info;
	struct btrfsic_block_data_ctx block_ctx;
2700 2701 2702
	int num_copies;
	int mirror_num;
	int match = 0;
2703
	int ret;
2704

2705
	num_copies = btrfs_num_copies(fs_info, bytenr, state->metablock_size);
2706 2707

	for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
2708
		ret = btrfsic_map_block(state, bytenr, state->metablock_size,
2709 2710
					&block_ctx, mirror_num);
		if (ret) {
2711
			pr_info("btrfsic: btrfsic_map_block(logical @%llu, mirror %d) failed!\n",
2712
			       bytenr, mirror_num);
2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724
			continue;
		}

		if (dev_state->bdev == block_ctx.dev->bdev &&
		    dev_bytenr == block_ctx.dev_bytenr) {
			match++;
			btrfsic_release_block_ctx(&block_ctx);
			break;
		}
		btrfsic_release_block_ctx(&block_ctx);
	}

2725
	if (WARN_ON(!match)) {
2726
		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",
2727
		       bytenr, dev_state->name, dev_bytenr);
2728
		for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
2729 2730
			ret = btrfsic_map_block(state, bytenr,
						state->metablock_size,
2731 2732 2733 2734
						&block_ctx, mirror_num);
			if (ret)
				continue;

2735
			pr_info("Read logical bytenr @%llu maps to (%s/%llu/%d)\n",
2736 2737
			       bytenr, block_ctx.dev->name,
			       block_ctx.dev_bytenr, mirror_num);
2738 2739 2740 2741 2742 2743 2744
		}
	}
}

static struct btrfsic_dev_state *btrfsic_dev_state_lookup(
		struct block_device *bdev)
{
2745 2746
	return btrfsic_dev_state_hashtable_lookup(bdev,
						  &btrfsic_dev_state_hashtable);
2747 2748
}

2749
int btrfsic_submit_bh(int op, int op_flags, struct buffer_head *bh)
2750 2751 2752 2753
{
	struct btrfsic_dev_state *dev_state;

	if (!btrfsic_is_initialized)
2754
		return submit_bh(op, op_flags, bh);
2755 2756 2757 2758 2759 2760 2761 2762

	mutex_lock(&btrfsic_mutex);
	/* since btrfsic_submit_bh() might also be called before
	 * btrfsic_mount(), this might return NULL */
	dev_state = btrfsic_dev_state_lookup(bh->b_bdev);

	/* Only called to write the superblock (incl. FLUSH/FUA) */
	if (NULL != dev_state &&
2763
	    (op == REQ_OP_WRITE) && bh->b_size > 0) {
2764 2765 2766 2767 2768
		u64 dev_bytenr;

		dev_bytenr = 4096 * bh->b_blocknr;
		if (dev_state->state->print_mask &
		    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH)
2769
			pr_info("submit_bh(op=0x%x,0x%x, blocknr=%llu (bytenr %llu), size=%zu, data=%p, bdev=%p)\n",
2770
			       op, op_flags, (unsigned long long)bh->b_blocknr,
2771
			       dev_bytenr, bh->b_size, bh->b_data, bh->b_bdev);
2772
		btrfsic_process_written_block(dev_state, dev_bytenr,
2773
					      &bh->b_data, 1, NULL,
2774
					      NULL, bh, op_flags);
2775
	} else if (NULL != dev_state && (op_flags & REQ_PREFLUSH)) {
2776 2777
		if (dev_state->state->print_mask &
		    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH)
2778
			pr_info("submit_bh(op=0x%x,0x%x FLUSH, bdev=%p)\n",
2779
			       op, op_flags, bh->b_bdev);
2780 2781 2782 2783
		if (!dev_state->dummy_block_for_bio_bh_flush.is_iodone) {
			if ((dev_state->state->print_mask &
			     (BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH |
			      BTRFSIC_PRINT_MASK_VERBOSE)))
2784
				pr_info("btrfsic_submit_bh(%s) with FLUSH but dummy block already in use (ignored)!\n",
2785 2786 2787 2788 2789 2790 2791 2792 2793
				       dev_state->name);
		} else {
			struct btrfsic_block *const block =
				&dev_state->dummy_block_for_bio_bh_flush;

			block->is_iodone = 0;
			block->never_written = 0;
			block->iodone_w_error = 0;
			block->flush_gen = dev_state->last_flush_gen + 1;
2794
			block->submit_bio_bh_rw = op_flags;
2795 2796 2797 2798 2799 2800 2801 2802
			block->orig_bio_bh_private = bh->b_private;
			block->orig_bio_bh_end_io.bh = bh->b_end_io;
			block->next_in_same_bio = NULL;
			bh->b_private = block;
			bh->b_end_io = btrfsic_bh_end_io;
		}
	}
	mutex_unlock(&btrfsic_mutex);
2803
	return submit_bh(op, op_flags, bh);
2804 2805
}

2806
static void __btrfsic_submit_bio(struct bio *bio)
2807 2808 2809
{
	struct btrfsic_dev_state *dev_state;

2810
	if (!btrfsic_is_initialized)
2811 2812 2813 2814 2815 2816 2817
		return;

	mutex_lock(&btrfsic_mutex);
	/* since btrfsic_submit_bio() is also called before
	 * btrfsic_mount(), this might return NULL */
	dev_state = btrfsic_dev_state_lookup(bio->bi_bdev);
	if (NULL != dev_state &&
2818
	    (bio_op(bio) == REQ_OP_WRITE) && bio_has_data(bio)) {
2819 2820
		unsigned int i;
		u64 dev_bytenr;
2821
		u64 cur_bytenr;
2822
		struct bio_vec *bvec;
2823
		int bio_is_patched;
2824
		char **mapped_datav;
2825

2826
		dev_bytenr = 512 * bio->bi_iter.bi_sector;
2827 2828 2829
		bio_is_patched = 0;
		if (dev_state->state->print_mask &
		    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH)
2830
			pr_info("submit_bio(rw=%d,0x%x, bi_vcnt=%u, bi_sector=%llu (bytenr %llu), bi_bdev=%p)\n",
J
Jens Axboe 已提交
2831
			       bio_op(bio), bio->bi_opf, bio->bi_vcnt,
2832 2833
			       (unsigned long long)bio->bi_iter.bi_sector,
			       dev_bytenr, bio->bi_bdev);
2834

2835 2836
		mapped_datav = kmalloc_array(bio->bi_vcnt,
					     sizeof(*mapped_datav), GFP_NOFS);
2837 2838
		if (!mapped_datav)
			goto leave;
2839
		cur_bytenr = dev_bytenr;
2840 2841 2842 2843 2844

		bio_for_each_segment_all(bvec, bio, i) {
			BUG_ON(bvec->bv_len != PAGE_SIZE);
			mapped_datav[i] = kmap(bvec->bv_page);

2845 2846
			if (dev_state->state->print_mask &
			    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH_VERBOSE)
2847
				pr_info("#%u: bytenr=%llu, len=%u, offset=%u\n",
2848 2849
				       i, cur_bytenr, bvec->bv_len, bvec->bv_offset);
			cur_bytenr += bvec->bv_len;
2850 2851 2852 2853
		}
		btrfsic_process_written_block(dev_state, dev_bytenr,
					      mapped_datav, bio->bi_vcnt,
					      bio, &bio_is_patched,
J
Jens Axboe 已提交
2854
					      NULL, bio->bi_opf);
2855 2856
		bio_for_each_segment_all(bvec, bio, i)
			kunmap(bvec->bv_page);
2857
		kfree(mapped_datav);
J
Jens Axboe 已提交
2858
	} else if (NULL != dev_state && (bio->bi_opf & REQ_PREFLUSH)) {
2859 2860
		if (dev_state->state->print_mask &
		    BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH)
2861
			pr_info("submit_bio(rw=%d,0x%x FLUSH, bdev=%p)\n",
J
Jens Axboe 已提交
2862
			       bio_op(bio), bio->bi_opf, bio->bi_bdev);
2863 2864 2865 2866
		if (!dev_state->dummy_block_for_bio_bh_flush.is_iodone) {
			if ((dev_state->state->print_mask &
			     (BTRFSIC_PRINT_MASK_SUBMIT_BIO_BH |
			      BTRFSIC_PRINT_MASK_VERBOSE)))
2867
				pr_info("btrfsic_submit_bio(%s) with FLUSH but dummy block already in use (ignored)!\n",
2868 2869 2870 2871 2872 2873 2874 2875 2876
				       dev_state->name);
		} else {
			struct btrfsic_block *const block =
				&dev_state->dummy_block_for_bio_bh_flush;

			block->is_iodone = 0;
			block->never_written = 0;
			block->iodone_w_error = 0;
			block->flush_gen = dev_state->last_flush_gen + 1;
J
Jens Axboe 已提交
2877
			block->submit_bio_bh_rw = bio->bi_opf;
2878 2879 2880 2881 2882 2883 2884
			block->orig_bio_bh_private = bio->bi_private;
			block->orig_bio_bh_end_io.bio = bio->bi_end_io;
			block->next_in_same_bio = NULL;
			bio->bi_private = block;
			bio->bi_end_io = btrfsic_bio_end_io;
		}
	}
2885
leave:
2886
	mutex_unlock(&btrfsic_mutex);
2887
}
2888

2889
void btrfsic_submit_bio(struct bio *bio)
2890
{
2891 2892
	__btrfsic_submit_bio(bio);
	submit_bio(bio);
2893 2894
}

2895
int btrfsic_submit_bio_wait(struct bio *bio)
2896
{
2897 2898
	__btrfsic_submit_bio(bio);
	return submit_bio_wait(bio);
2899 2900
}

2901
int btrfsic_mount(struct btrfs_fs_info *fs_info,
2902 2903 2904 2905 2906 2907 2908 2909
		  struct btrfs_fs_devices *fs_devices,
		  int including_extent_data, u32 print_mask)
{
	int ret;
	struct btrfsic_state *state;
	struct list_head *dev_head = &fs_devices->devices;
	struct btrfs_device *device;

2910
	if (fs_info->nodesize & ((u64)PAGE_SIZE - 1)) {
2911
		pr_info("btrfsic: cannot handle nodesize %d not being a multiple of PAGE_SIZE %ld!\n",
2912
		       fs_info->nodesize, PAGE_SIZE);
2913 2914
		return -1;
	}
2915
	if (fs_info->sectorsize & ((u64)PAGE_SIZE - 1)) {
2916
		pr_info("btrfsic: cannot handle sectorsize %d not being a multiple of PAGE_SIZE %ld!\n",
2917
		       fs_info->sectorsize, PAGE_SIZE);
2918 2919
		return -1;
	}
2920 2921 2922 2923
	state = kzalloc(sizeof(*state), GFP_KERNEL | __GFP_NOWARN | __GFP_REPEAT);
	if (!state) {
		state = vzalloc(sizeof(*state));
		if (!state) {
2924
			pr_info("btrfs check-integrity: vzalloc() failed!\n");
2925 2926
			return -1;
		}
2927 2928 2929 2930 2931 2932 2933 2934
	}

	if (!btrfsic_is_initialized) {
		mutex_init(&btrfsic_mutex);
		btrfsic_dev_state_hashtable_init(&btrfsic_dev_state_hashtable);
		btrfsic_is_initialized = 1;
	}
	mutex_lock(&btrfsic_mutex);
2935
	state->fs_info = fs_info;
2936 2937 2938
	state->print_mask = print_mask;
	state->include_extent_data = including_extent_data;
	state->csum_size = 0;
2939 2940
	state->metablock_size = fs_info->nodesize;
	state->datablock_size = fs_info->sectorsize;
2941 2942 2943 2944 2945 2946 2947 2948
	INIT_LIST_HEAD(&state->all_blocks_list);
	btrfsic_block_hashtable_init(&state->block_hashtable);
	btrfsic_block_link_hashtable_init(&state->block_link_hashtable);
	state->max_superblock_generation = 0;
	state->latest_superblock = NULL;

	list_for_each_entry(device, dev_head, dev_list) {
		struct btrfsic_dev_state *ds;
2949
		const char *p;
2950 2951 2952 2953 2954 2955

		if (!device->bdev || !device->name)
			continue;

		ds = btrfsic_dev_state_alloc();
		if (NULL == ds) {
2956
			pr_info("btrfs check-integrity: kmalloc() failed!\n");
2957 2958 2959 2960 2961 2962 2963
			mutex_unlock(&btrfsic_mutex);
			return -1;
		}
		ds->bdev = device->bdev;
		ds->state = state;
		bdevname(ds->bdev, ds->name);
		ds->name[BDEVNAME_SIZE - 1] = '\0';
2964
		p = kbasename(ds->name);
2965 2966 2967 2968 2969 2970 2971 2972
		strlcpy(ds->name, p, sizeof(ds->name));
		btrfsic_dev_state_hashtable_add(ds,
						&btrfsic_dev_state_hashtable);
	}

	ret = btrfsic_process_superblock(state, fs_devices);
	if (0 != ret) {
		mutex_unlock(&btrfsic_mutex);
2973
		btrfsic_unmount(fs_devices);
2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985
		return ret;
	}

	if (state->print_mask & BTRFSIC_PRINT_MASK_INITIAL_DATABASE)
		btrfsic_dump_database(state);
	if (state->print_mask & BTRFSIC_PRINT_MASK_INITIAL_TREE)
		btrfsic_dump_tree(state);

	mutex_unlock(&btrfsic_mutex);
	return 0;
}

2986
void btrfsic_unmount(struct btrfs_fs_devices *fs_devices)
2987
{
2988
	struct btrfsic_block *b_all, *tmp_all;
2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015
	struct btrfsic_state *state;
	struct list_head *dev_head = &fs_devices->devices;
	struct btrfs_device *device;

	if (!btrfsic_is_initialized)
		return;

	mutex_lock(&btrfsic_mutex);

	state = NULL;
	list_for_each_entry(device, dev_head, dev_list) {
		struct btrfsic_dev_state *ds;

		if (!device->bdev || !device->name)
			continue;

		ds = btrfsic_dev_state_hashtable_lookup(
				device->bdev,
				&btrfsic_dev_state_hashtable);
		if (NULL != ds) {
			state = ds->state;
			btrfsic_dev_state_hashtable_remove(ds);
			btrfsic_dev_state_free(ds);
		}
	}

	if (NULL == state) {
3016
		pr_info("btrfsic: error, cannot find state information on umount!\n");
3017 3018 3019 3020 3021 3022 3023 3024 3025
		mutex_unlock(&btrfsic_mutex);
		return;
	}

	/*
	 * Don't care about keeping the lists' state up to date,
	 * just free all memory that was allocated dynamically.
	 * Free the blocks and the block_links.
	 */
3026 3027 3028
	list_for_each_entry_safe(b_all, tmp_all, &state->all_blocks_list,
				 all_blocks_node) {
		struct btrfsic_block_link *l, *tmp;
3029

3030 3031
		list_for_each_entry_safe(l, tmp, &b_all->ref_to_list,
					 node_ref_to) {
3032 3033 3034 3035 3036 3037 3038 3039
			if (state->print_mask & BTRFSIC_PRINT_MASK_VERBOSE)
				btrfsic_print_rem_link(state, l);

			l->ref_cnt--;
			if (0 == l->ref_cnt)
				btrfsic_block_link_free(l);
		}

3040
		if (b_all->is_iodone || b_all->never_written)
3041 3042
			btrfsic_block_free(b_all);
		else
3043
			pr_info("btrfs: attempt to free %c-block @%llu (%s/%llu/%d) on umount which is not yet iodone!\n",
3044
			       btrfsic_get_block_type(state, b_all),
3045 3046
			       b_all->logical_bytenr, b_all->dev_state->name,
			       b_all->dev_bytenr, b_all->mirror_num);
3047 3048 3049 3050
	}

	mutex_unlock(&btrfsic_mutex);

W
Wang Shilong 已提交
3051
	kvfree(state);
3052
}