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