1 /*
2  * CDDL HEADER START
3  *
4  * This file and its contents are supplied under the terms of the
5  * Common Development and Distribution License ("CDDL"), version 1.0.
6  * You may only use this file in accordance with the terms of version
7  * 1.0 of the CDDL.
8  *
9  * A full copy of the text of the CDDL should have accompanied this
10  * source.  A copy of the CDDL is also available via the Internet at
11  * http://www.illumos.org/license/CDDL.
12  *
13  * CDDL HEADER END
14  */
15 
16 /*
17  * Copyright (c) 2014, 2019 by Delphix. All rights reserved.
18  * Copyright 2019 Joyent, Inc.
19  */
20 
21 #include <sys/zfs_context.h>
22 #include <sys/spa.h>
23 #include <sys/spa_impl.h>
24 #include <sys/vdev_impl.h>
25 #include <sys/fs/zfs.h>
26 #include <sys/zio.h>
27 #include <sys/zio_checksum.h>
28 #include <sys/metaslab.h>
29 #include <sys/refcount.h>
30 #include <sys/dmu.h>
31 #include <sys/vdev_indirect_mapping.h>
32 #include <sys/dmu_tx.h>
33 #include <sys/dsl_synctask.h>
34 #include <sys/zap.h>
35 #include <sys/abd.h>
36 #include <sys/zthr.h>
37 
38 /*
39  * An indirect vdev corresponds to a vdev that has been removed.  Since
40  * we cannot rewrite block pointers of snapshots, etc., we keep a
41  * mapping from old location on the removed device to the new location
42  * on another device in the pool and use this mapping whenever we need
43  * to access the DVA.  Unfortunately, this mapping did not respect
44  * logical block boundaries when it was first created, and so a DVA on
45  * this indirect vdev may be "split" into multiple sections that each
46  * map to a different location.  As a consequence, not all DVAs can be
47  * translated to an equivalent new DVA.  Instead we must provide a
48  * "vdev_remap" operation that executes a callback on each contiguous
49  * segment of the new location.  This function is used in multiple ways:
50  *
51  *  - i/os to this vdev use the callback to determine where the
52  *    data is now located, and issue child i/os for each segment's new
53  *    location.
54  *
55  *  - frees and claims to this vdev use the callback to free or claim
56  *    each mapped segment.  (Note that we don't actually need to claim
57  *    log blocks on indirect vdevs, because we don't allocate to
58  *    removing vdevs.  However, zdb uses zio_claim() for its leak
59  *    detection.)
60  */
61 
62 /*
63  * "Big theory statement" for how we mark blocks obsolete.
64  *
65  * When a block on an indirect vdev is freed or remapped, a section of
66  * that vdev's mapping may no longer be referenced (aka "obsolete").  We
67  * keep track of how much of each mapping entry is obsolete.  When
68  * an entry becomes completely obsolete, we can remove it, thus reducing
69  * the memory used by the mapping.  The complete picture of obsolescence
70  * is given by the following data structures, described below:
71  *  - the entry-specific obsolete count
72  *  - the vdev-specific obsolete spacemap
73  *  - the pool-specific obsolete bpobj
74  *
75  * == On disk data structures used ==
76  *
77  * We track the obsolete space for the pool using several objects.  Each
78  * of these objects is created on demand and freed when no longer
79  * needed, and is assumed to be empty if it does not exist.
80  * SPA_FEATURE_OBSOLETE_COUNTS includes the count of these objects.
81  *
82  *  - Each vic_mapping_object (associated with an indirect vdev) can
83  *    have a vimp_counts_object.  This is an array of uint32_t's
84  *    with the same number of entries as the vic_mapping_object.  When
85  *    the mapping is condensed, entries from the vic_obsolete_sm_object
86  *    (see below) are folded into the counts.  Therefore, each
87  *    obsolete_counts entry tells us the number of bytes in the
88  *    corresponding mapping entry that were not referenced when the
89  *    mapping was last condensed.
90  *
91  *  - Each indirect or removing vdev can have a vic_obsolete_sm_object.
92  *    This is a space map containing an alloc entry for every DVA that
93  *    has been obsoleted since the last time this indirect vdev was
94  *    condensed.  We use this object in order to improve performance
95  *    when marking a DVA as obsolete.  Instead of modifying an arbitrary
96  *    offset of the vimp_counts_object, we only need to append an entry
97  *    to the end of this object.  When a DVA becomes obsolete, it is
98  *    added to the obsolete space map.  This happens when the DVA is
99  *    freed, remapped and not referenced by a snapshot, or the last
100  *    snapshot referencing it is destroyed.
101  *
102  *  - Each dataset can have a ds_remap_deadlist object.  This is a
103  *    deadlist object containing all blocks that were remapped in this
104  *    dataset but referenced in a previous snapshot.  Blocks can *only*
105  *    appear on this list if they were remapped (dsl_dataset_block_remapped);
106  *    blocks that were killed in a head dataset are put on the normal
107  *    ds_deadlist and marked obsolete when they are freed.
108  *
109  *  - The pool can have a dp_obsolete_bpobj.  This is a list of blocks
110  *    in the pool that need to be marked obsolete.  When a snapshot is
111  *    destroyed, we move some of the ds_remap_deadlist to the obsolete
112  *    bpobj (see dsl_destroy_snapshot_handle_remaps()).  We then
113  *    asynchronously process the obsolete bpobj, moving its entries to
114  *    the specific vdevs' obsolete space maps.
115  *
116  * == Summary of how we mark blocks as obsolete ==
117  *
118  * - When freeing a block: if any DVA is on an indirect vdev, append to
119  *   vic_obsolete_sm_object.
120  * - When remapping a block, add dva to ds_remap_deadlist (if prev snap
121  *   references; otherwise append to vic_obsolete_sm_object).
122  * - When freeing a snapshot: move parts of ds_remap_deadlist to
123  *   dp_obsolete_bpobj (same algorithm as ds_deadlist).
124  * - When syncing the spa: process dp_obsolete_bpobj, moving ranges to
125  *   individual vdev's vic_obsolete_sm_object.
126  */
127 
128 /*
129  * "Big theory statement" for how we condense indirect vdevs.
130  *
131  * Condensing an indirect vdev's mapping is the process of determining
132  * the precise counts of obsolete space for each mapping entry (by
133  * integrating the obsolete spacemap into the obsolete counts) and
134  * writing out a new mapping that contains only referenced entries.
135  *
136  * We condense a vdev when we expect the mapping to shrink (see
137  * vdev_indirect_should_condense()), but only perform one condense at a
138  * time to limit the memory usage.  In addition, we use a separate
139  * open-context thread (spa_condense_indirect_thread) to incrementally
140  * create the new mapping object in a way that minimizes the impact on
141  * the rest of the system.
142  *
143  * == Generating a new mapping ==
144  *
145  * To generate a new mapping, we follow these steps:
146  *
147  * 1. Save the old obsolete space map and create a new mapping object
148  *    (see spa_condense_indirect_start_sync()).  This initializes the
149  *    spa_condensing_indirect_phys with the "previous obsolete space map",
150  *    which is now read only.  Newly obsolete DVAs will be added to a
151  *    new (initially empty) obsolete space map, and will not be
152  *    considered as part of this condense operation.
153  *
154  * 2. Construct in memory the precise counts of obsolete space for each
155  *    mapping entry, by incorporating the obsolete space map into the
156  *    counts.  (See vdev_indirect_mapping_load_obsolete_{counts,spacemap}().)
157  *
158  * 3. Iterate through each mapping entry, writing to the new mapping any
159  *    entries that are not completely obsolete (i.e. which don't have
160  *    obsolete count == mapping length).  (See
161  *    spa_condense_indirect_generate_new_mapping().)
162  *
163  * 4. Destroy the old mapping object and switch over to the new one
164  *    (spa_condense_indirect_complete_sync).
165  *
166  * == Restarting from failure ==
167  *
168  * To restart the condense when we import/open the pool, we must start
169  * at the 2nd step above: reconstruct the precise counts in memory,
170  * based on the space map + counts.  Then in the 3rd step, we start
171  * iterating where we left off: at vimp_max_offset of the new mapping
172  * object.
173  */
174 
175 boolean_t zfs_condense_indirect_vdevs_enable = B_TRUE;
176 
177 /*
178  * Condense if at least this percent of the bytes in the mapping is
179  * obsolete.  With the default of 25%, the amount of space mapped
180  * will be reduced to 1% of its original size after at most 16
181  * condenses.  Higher values will condense less often (causing less
182  * i/o); lower values will reduce the mapping size more quickly.
183  */
184 int zfs_indirect_condense_obsolete_pct = 25;
185 
186 /*
187  * Condense if the obsolete space map takes up more than this amount of
188  * space on disk (logically).  This limits the amount of disk space
189  * consumed by the obsolete space map; the default of 1GB is small enough
190  * that we typically don't mind "wasting" it.
191  */
192 uint64_t zfs_condense_max_obsolete_bytes = 1024 * 1024 * 1024;
193 
194 /*
195  * Don't bother condensing if the mapping uses less than this amount of
196  * memory.  The default of 128KB is considered a "trivial" amount of
197  * memory and not worth reducing.
198  */
199 uint64_t zfs_condense_min_mapping_bytes = 128 * 1024;
200 
201 /*
202  * This is used by the test suite so that it can ensure that certain
203  * actions happen while in the middle of a condense (which might otherwise
204  * complete too quickly).  If used to reduce the performance impact of
205  * condensing in production, a maximum value of 1 should be sufficient.
206  */
207 int zfs_condense_indirect_commit_entry_delay_ticks = 0;
208 
209 /*
210  * If an indirect split block contains more than this many possible unique
211  * combinations when being reconstructed, consider it too computationally
212  * expensive to check them all. Instead, try at most 100 randomly-selected
213  * combinations each time the block is accessed.  This allows all segment
214  * copies to participate fairly in the reconstruction when all combinations
215  * cannot be checked and prevents repeated use of one bad copy.
216  */
217 int zfs_reconstruct_indirect_combinations_max = 256;
218 
219 
220 /*
221  * Enable to simulate damaged segments and validate reconstruction.
222  * Used by ztest
223  */
224 unsigned long zfs_reconstruct_indirect_damage_fraction = 0;
225 
226 /*
227  * The indirect_child_t represents the vdev that we will read from, when we
228  * need to read all copies of the data (e.g. for scrub or reconstruction).
229  * For plain (non-mirror) top-level vdevs (i.e. is_vdev is not a mirror),
230  * ic_vdev is the same as is_vdev.  However, for mirror top-level vdevs,
231  * ic_vdev is a child of the mirror.
232  */
233 typedef struct indirect_child {
234 	abd_t *ic_data;
235 	vdev_t *ic_vdev;
236 
237 	/*
238 	 * ic_duplicate is NULL when the ic_data contents are unique, when it
239 	 * is determined to be a duplicate it references the primary child.
240 	 */
241 	struct indirect_child *ic_duplicate;
242 	list_node_t ic_node; /* node on is_unique_child */
243 } indirect_child_t;
244 
245 /*
246  * The indirect_split_t represents one mapped segment of an i/o to the
247  * indirect vdev. For non-split (contiguously-mapped) blocks, there will be
248  * only one indirect_split_t, with is_split_offset==0 and is_size==io_size.
249  * For split blocks, there will be several of these.
250  */
251 typedef struct indirect_split {
252 	list_node_t is_node; /* link on iv_splits */
253 
254 	/*
255 	 * is_split_offset is the offset into the i/o.
256 	 * This is the sum of the previous splits' is_size's.
257 	 */
258 	uint64_t is_split_offset;
259 
260 	vdev_t *is_vdev; /* top-level vdev */
261 	uint64_t is_target_offset; /* offset on is_vdev */
262 	uint64_t is_size;
263 	int is_children; /* number of entries in is_child[] */
264 	int is_unique_children; /* number of entries in is_unique_child */
265 	list_t is_unique_child;
266 
267 	/*
268 	 * is_good_child is the child that we are currently using to
269 	 * attempt reconstruction.
270 	 */
271 	indirect_child_t *is_good_child;
272 
273 	indirect_child_t is_child[1]; /* variable-length */
274 } indirect_split_t;
275 
276 /*
277  * The indirect_vsd_t is associated with each i/o to the indirect vdev.
278  * It is the "Vdev-Specific Data" in the zio_t's io_vsd.
279  */
280 typedef struct indirect_vsd {
281 	boolean_t iv_split_block;
282 	boolean_t iv_reconstruct;
283 	uint64_t iv_unique_combinations;
284 	uint64_t iv_attempts;
285 	uint64_t iv_attempts_max;
286 
287 	list_t iv_splits; /* list of indirect_split_t's */
288 } indirect_vsd_t;
289 
290 static void
vdev_indirect_map_free(zio_t * zio)291 vdev_indirect_map_free(zio_t *zio)
292 {
293 	indirect_vsd_t *iv = zio->io_vsd;
294 
295 	indirect_split_t *is;
296 	while ((is = list_head(&iv->iv_splits)) != NULL) {
297 		for (int c = 0; c < is->is_children; c++) {
298 			indirect_child_t *ic = &is->is_child[c];
299 			if (ic->ic_data != NULL)
300 				abd_free(ic->ic_data);
301 		}
302 		list_remove(&iv->iv_splits, is);
303 
304 		indirect_child_t *ic;
305 		while ((ic = list_head(&is->is_unique_child)) != NULL)
306 			list_remove(&is->is_unique_child, ic);
307 
308 		list_destroy(&is->is_unique_child);
309 
310 		kmem_free(is,
311 		    offsetof(indirect_split_t, is_child[is->is_children]));
312 	}
313 	kmem_free(iv, sizeof (*iv));
314 }
315 
316 static const zio_vsd_ops_t vdev_indirect_vsd_ops = {
317 	vdev_indirect_map_free,
318 	zio_vsd_default_cksum_report
319 };
320 /*
321  * Mark the given offset and size as being obsolete.
322  */
323 void
vdev_indirect_mark_obsolete(vdev_t * vd,uint64_t offset,uint64_t size)324 vdev_indirect_mark_obsolete(vdev_t *vd, uint64_t offset, uint64_t size)
325 {
326 	spa_t *spa = vd->vdev_spa;
327 
328 	ASSERT3U(vd->vdev_indirect_config.vic_mapping_object, !=, 0);
329 	ASSERT(vd->vdev_removing || vd->vdev_ops == &vdev_indirect_ops);
330 	ASSERT(size > 0);
331 	VERIFY(vdev_indirect_mapping_entry_for_offset(
332 	    vd->vdev_indirect_mapping, offset) != NULL);
333 
334 	if (spa_feature_is_enabled(spa, SPA_FEATURE_OBSOLETE_COUNTS)) {
335 		mutex_enter(&vd->vdev_obsolete_lock);
336 		range_tree_add(vd->vdev_obsolete_segments, offset, size);
337 		mutex_exit(&vd->vdev_obsolete_lock);
338 		vdev_dirty(vd, 0, NULL, spa_syncing_txg(spa));
339 	}
340 }
341 
342 /*
343  * Mark the DVA vdev_id:offset:size as being obsolete in the given tx. This
344  * wrapper is provided because the DMU does not know about vdev_t's and
345  * cannot directly call vdev_indirect_mark_obsolete.
346  */
347 void
spa_vdev_indirect_mark_obsolete(spa_t * spa,uint64_t vdev_id,uint64_t offset,uint64_t size,dmu_tx_t * tx)348 spa_vdev_indirect_mark_obsolete(spa_t *spa, uint64_t vdev_id, uint64_t offset,
349     uint64_t size, dmu_tx_t *tx)
350 {
351 	vdev_t *vd = vdev_lookup_top(spa, vdev_id);
352 	ASSERT(dmu_tx_is_syncing(tx));
353 
354 	/* The DMU can only remap indirect vdevs. */
355 	ASSERT3P(vd->vdev_ops, ==, &vdev_indirect_ops);
356 	vdev_indirect_mark_obsolete(vd, offset, size);
357 }
358 
359 static spa_condensing_indirect_t *
spa_condensing_indirect_create(spa_t * spa)360 spa_condensing_indirect_create(spa_t *spa)
361 {
362 	spa_condensing_indirect_phys_t *scip =
363 	    &spa->spa_condensing_indirect_phys;
364 	spa_condensing_indirect_t *sci = kmem_zalloc(sizeof (*sci), KM_SLEEP);
365 	objset_t *mos = spa->spa_meta_objset;
366 
367 	for (int i = 0; i < TXG_SIZE; i++) {
368 		list_create(&sci->sci_new_mapping_entries[i],
369 		    sizeof (vdev_indirect_mapping_entry_t),
370 		    offsetof(vdev_indirect_mapping_entry_t, vime_node));
371 	}
372 
373 	sci->sci_new_mapping =
374 	    vdev_indirect_mapping_open(mos, scip->scip_next_mapping_object);
375 
376 	return (sci);
377 }
378 
379 static void
spa_condensing_indirect_destroy(spa_condensing_indirect_t * sci)380 spa_condensing_indirect_destroy(spa_condensing_indirect_t *sci)
381 {
382 	for (int i = 0; i < TXG_SIZE; i++)
383 		list_destroy(&sci->sci_new_mapping_entries[i]);
384 
385 	if (sci->sci_new_mapping != NULL)
386 		vdev_indirect_mapping_close(sci->sci_new_mapping);
387 
388 	kmem_free(sci, sizeof (*sci));
389 }
390 
391 boolean_t
vdev_indirect_should_condense(vdev_t * vd)392 vdev_indirect_should_condense(vdev_t *vd)
393 {
394 	vdev_indirect_mapping_t *vim = vd->vdev_indirect_mapping;
395 	spa_t *spa = vd->vdev_spa;
396 
397 	ASSERT(dsl_pool_sync_context(spa->spa_dsl_pool));
398 
399 	if (!zfs_condense_indirect_vdevs_enable)
400 		return (B_FALSE);
401 
402 	/*
403 	 * We can only condense one indirect vdev at a time.
404 	 */
405 	if (spa->spa_condensing_indirect != NULL)
406 		return (B_FALSE);
407 
408 	if (spa_shutting_down(spa))
409 		return (B_FALSE);
410 
411 	/*
412 	 * The mapping object size must not change while we are
413 	 * condensing, so we can only condense indirect vdevs
414 	 * (not vdevs that are still in the middle of being removed).
415 	 */
416 	if (vd->vdev_ops != &vdev_indirect_ops)
417 		return (B_FALSE);
418 
419 	/*
420 	 * If nothing new has been marked obsolete, there is no
421 	 * point in condensing.
422 	 */
423 	if (vd->vdev_obsolete_sm == NULL) {
424 		ASSERT0(vdev_obsolete_sm_object(vd));
425 		return (B_FALSE);
426 	}
427 
428 	ASSERT(vd->vdev_obsolete_sm != NULL);
429 
430 	ASSERT3U(vdev_obsolete_sm_object(vd), ==,
431 	    space_map_object(vd->vdev_obsolete_sm));
432 
433 	uint64_t bytes_mapped = vdev_indirect_mapping_bytes_mapped(vim);
434 	uint64_t bytes_obsolete = space_map_allocated(vd->vdev_obsolete_sm);
435 	uint64_t mapping_size = vdev_indirect_mapping_size(vim);
436 	uint64_t obsolete_sm_size = space_map_length(vd->vdev_obsolete_sm);
437 
438 	ASSERT3U(bytes_obsolete, <=, bytes_mapped);
439 
440 	/*
441 	 * If a high percentage of the bytes that are mapped have become
442 	 * obsolete, condense (unless the mapping is already small enough).
443 	 * This has a good chance of reducing the amount of memory used
444 	 * by the mapping.
445 	 */
446 	if (bytes_obsolete * 100 / bytes_mapped >=
447 	    zfs_indirect_condense_obsolete_pct &&
448 	    mapping_size > zfs_condense_min_mapping_bytes) {
449 		zfs_dbgmsg("should condense vdev %llu because obsolete "
450 		    "spacemap covers %d%% of %lluMB mapping",
451 		    (u_longlong_t)vd->vdev_id,
452 		    (int)(bytes_obsolete * 100 / bytes_mapped),
453 		    (u_longlong_t)bytes_mapped / 1024 / 1024);
454 		return (B_TRUE);
455 	}
456 
457 	/*
458 	 * If the obsolete space map takes up too much space on disk,
459 	 * condense in order to free up this disk space.
460 	 */
461 	if (obsolete_sm_size >= zfs_condense_max_obsolete_bytes) {
462 		zfs_dbgmsg("should condense vdev %llu because obsolete sm "
463 		    "length %lluMB >= max size %lluMB",
464 		    (u_longlong_t)vd->vdev_id,
465 		    (u_longlong_t)obsolete_sm_size / 1024 / 1024,
466 		    (u_longlong_t)zfs_condense_max_obsolete_bytes /
467 		    1024 / 1024);
468 		return (B_TRUE);
469 	}
470 
471 	return (B_FALSE);
472 }
473 
474 /*
475  * This sync task completes (finishes) a condense, deleting the old
476  * mapping and replacing it with the new one.
477  */
478 static void
spa_condense_indirect_complete_sync(void * arg,dmu_tx_t * tx)479 spa_condense_indirect_complete_sync(void *arg, dmu_tx_t *tx)
480 {
481 	spa_condensing_indirect_t *sci = arg;
482 	spa_t *spa = dmu_tx_pool(tx)->dp_spa;
483 	spa_condensing_indirect_phys_t *scip =
484 	    &spa->spa_condensing_indirect_phys;
485 	vdev_t *vd = vdev_lookup_top(spa, scip->scip_vdev);
486 	vdev_indirect_config_t *vic = &vd->vdev_indirect_config;
487 	objset_t *mos = spa->spa_meta_objset;
488 	vdev_indirect_mapping_t *old_mapping = vd->vdev_indirect_mapping;
489 	uint64_t old_count = vdev_indirect_mapping_num_entries(old_mapping);
490 	uint64_t new_count =
491 	    vdev_indirect_mapping_num_entries(sci->sci_new_mapping);
492 
493 	ASSERT(dmu_tx_is_syncing(tx));
494 	ASSERT3P(vd->vdev_ops, ==, &vdev_indirect_ops);
495 	ASSERT3P(sci, ==, spa->spa_condensing_indirect);
496 	for (int i = 0; i < TXG_SIZE; i++) {
497 		ASSERT(list_is_empty(&sci->sci_new_mapping_entries[i]));
498 	}
499 	ASSERT(vic->vic_mapping_object != 0);
500 	ASSERT3U(vd->vdev_id, ==, scip->scip_vdev);
501 	ASSERT(scip->scip_next_mapping_object != 0);
502 	ASSERT(scip->scip_prev_obsolete_sm_object != 0);
503 
504 	/*
505 	 * Reset vdev_indirect_mapping to refer to the new object.
506 	 */
507 	rw_enter(&vd->vdev_indirect_rwlock, RW_WRITER);
508 	vdev_indirect_mapping_close(vd->vdev_indirect_mapping);
509 	vd->vdev_indirect_mapping = sci->sci_new_mapping;
510 	rw_exit(&vd->vdev_indirect_rwlock);
511 
512 	sci->sci_new_mapping = NULL;
513 	vdev_indirect_mapping_free(mos, vic->vic_mapping_object, tx);
514 	vic->vic_mapping_object = scip->scip_next_mapping_object;
515 	scip->scip_next_mapping_object = 0;
516 
517 	space_map_free_obj(mos, scip->scip_prev_obsolete_sm_object, tx);
518 	spa_feature_decr(spa, SPA_FEATURE_OBSOLETE_COUNTS, tx);
519 	scip->scip_prev_obsolete_sm_object = 0;
520 
521 	scip->scip_vdev = 0;
522 
523 	VERIFY0(zap_remove(mos, DMU_POOL_DIRECTORY_OBJECT,
524 	    DMU_POOL_CONDENSING_INDIRECT, tx));
525 	spa_condensing_indirect_destroy(spa->spa_condensing_indirect);
526 	spa->spa_condensing_indirect = NULL;
527 
528 	zfs_dbgmsg("finished condense of vdev %llu in txg %llu: "
529 	    "new mapping object %llu has %llu entries "
530 	    "(was %llu entries)",
531 	    vd->vdev_id, dmu_tx_get_txg(tx), vic->vic_mapping_object,
532 	    new_count, old_count);
533 
534 	vdev_config_dirty(spa->spa_root_vdev);
535 }
536 
537 /*
538  * This sync task appends entries to the new mapping object.
539  */
540 static void
spa_condense_indirect_commit_sync(void * arg,dmu_tx_t * tx)541 spa_condense_indirect_commit_sync(void *arg, dmu_tx_t *tx)
542 {
543 	spa_condensing_indirect_t *sci = arg;
544 	uint64_t txg = dmu_tx_get_txg(tx);
545 	spa_t *spa = dmu_tx_pool(tx)->dp_spa;
546 
547 	ASSERT(dmu_tx_is_syncing(tx));
548 	ASSERT3P(sci, ==, spa->spa_condensing_indirect);
549 
550 	vdev_indirect_mapping_add_entries(sci->sci_new_mapping,
551 	    &sci->sci_new_mapping_entries[txg & TXG_MASK], tx);
552 	ASSERT(list_is_empty(&sci->sci_new_mapping_entries[txg & TXG_MASK]));
553 }
554 
555 /*
556  * Open-context function to add one entry to the new mapping.  The new
557  * entry will be remembered and written from syncing context.
558  */
559 static void
spa_condense_indirect_commit_entry(spa_t * spa,vdev_indirect_mapping_entry_phys_t * vimep,uint32_t count)560 spa_condense_indirect_commit_entry(spa_t *spa,
561     vdev_indirect_mapping_entry_phys_t *vimep, uint32_t count)
562 {
563 	spa_condensing_indirect_t *sci = spa->spa_condensing_indirect;
564 
565 	ASSERT3U(count, <, DVA_GET_ASIZE(&vimep->vimep_dst));
566 
567 	dmu_tx_t *tx = dmu_tx_create_dd(spa_get_dsl(spa)->dp_mos_dir);
568 	dmu_tx_hold_space(tx, sizeof (*vimep) + sizeof (count));
569 	VERIFY0(dmu_tx_assign(tx, TXG_WAIT));
570 	int txgoff = dmu_tx_get_txg(tx) & TXG_MASK;
571 
572 	/*
573 	 * If we are the first entry committed this txg, kick off the sync
574 	 * task to write to the MOS on our behalf.
575 	 */
576 	if (list_is_empty(&sci->sci_new_mapping_entries[txgoff])) {
577 		dsl_sync_task_nowait(dmu_tx_pool(tx),
578 		    spa_condense_indirect_commit_sync, sci,
579 		    0, ZFS_SPACE_CHECK_NONE, tx);
580 	}
581 
582 	vdev_indirect_mapping_entry_t *vime =
583 	    kmem_alloc(sizeof (*vime), KM_SLEEP);
584 	vime->vime_mapping = *vimep;
585 	vime->vime_obsolete_count = count;
586 	list_insert_tail(&sci->sci_new_mapping_entries[txgoff], vime);
587 
588 	dmu_tx_commit(tx);
589 }
590 
591 static void
spa_condense_indirect_generate_new_mapping(vdev_t * vd,uint32_t * obsolete_counts,uint64_t start_index,zthr_t * zthr)592 spa_condense_indirect_generate_new_mapping(vdev_t *vd,
593     uint32_t *obsolete_counts, uint64_t start_index, zthr_t *zthr)
594 {
595 	spa_t *spa = vd->vdev_spa;
596 	uint64_t mapi = start_index;
597 	vdev_indirect_mapping_t *old_mapping = vd->vdev_indirect_mapping;
598 	uint64_t old_num_entries =
599 	    vdev_indirect_mapping_num_entries(old_mapping);
600 
601 	ASSERT3P(vd->vdev_ops, ==, &vdev_indirect_ops);
602 	ASSERT3U(vd->vdev_id, ==, spa->spa_condensing_indirect_phys.scip_vdev);
603 
604 	zfs_dbgmsg("starting condense of vdev %llu from index %llu",
605 	    (u_longlong_t)vd->vdev_id,
606 	    (u_longlong_t)mapi);
607 
608 	while (mapi < old_num_entries) {
609 
610 		if (zthr_iscancelled(zthr)) {
611 			zfs_dbgmsg("pausing condense of vdev %llu "
612 			    "at index %llu", (u_longlong_t)vd->vdev_id,
613 			    (u_longlong_t)mapi);
614 			break;
615 		}
616 
617 		vdev_indirect_mapping_entry_phys_t *entry =
618 		    &old_mapping->vim_entries[mapi];
619 		uint64_t entry_size = DVA_GET_ASIZE(&entry->vimep_dst);
620 		ASSERT3U(obsolete_counts[mapi], <=, entry_size);
621 		if (obsolete_counts[mapi] < entry_size) {
622 			spa_condense_indirect_commit_entry(spa, entry,
623 			    obsolete_counts[mapi]);
624 
625 			/*
626 			 * This delay may be requested for testing, debugging,
627 			 * or performance reasons.
628 			 */
629 			delay(zfs_condense_indirect_commit_entry_delay_ticks);
630 		}
631 
632 		mapi++;
633 	}
634 }
635 
636 /* ARGSUSED */
637 static boolean_t
spa_condense_indirect_thread_check(void * arg,zthr_t * zthr)638 spa_condense_indirect_thread_check(void *arg, zthr_t *zthr)
639 {
640 	spa_t *spa = arg;
641 
642 	return (spa->spa_condensing_indirect != NULL);
643 }
644 
645 /* ARGSUSED */
646 static void
spa_condense_indirect_thread(void * arg,zthr_t * zthr)647 spa_condense_indirect_thread(void *arg, zthr_t *zthr)
648 {
649 	spa_t *spa = arg;
650 	vdev_t *vd;
651 
652 	ASSERT3P(spa->spa_condensing_indirect, !=, NULL);
653 	spa_config_enter(spa, SCL_VDEV, FTAG, RW_READER);
654 	vd = vdev_lookup_top(spa, spa->spa_condensing_indirect_phys.scip_vdev);
655 	ASSERT3P(vd, !=, NULL);
656 	spa_config_exit(spa, SCL_VDEV, FTAG);
657 
658 	spa_condensing_indirect_t *sci = spa->spa_condensing_indirect;
659 	spa_condensing_indirect_phys_t *scip =
660 	    &spa->spa_condensing_indirect_phys;
661 	uint32_t *counts;
662 	uint64_t start_index;
663 	vdev_indirect_mapping_t *old_mapping = vd->vdev_indirect_mapping;
664 	space_map_t *prev_obsolete_sm = NULL;
665 
666 	ASSERT3U(vd->vdev_id, ==, scip->scip_vdev);
667 	ASSERT(scip->scip_next_mapping_object != 0);
668 	ASSERT(scip->scip_prev_obsolete_sm_object != 0);
669 	ASSERT3P(vd->vdev_ops, ==, &vdev_indirect_ops);
670 
671 	for (int i = 0; i < TXG_SIZE; i++) {
672 		/*
673 		 * The list must start out empty in order for the
674 		 * _commit_sync() sync task to be properly registered
675 		 * on the first call to _commit_entry(); so it's wise
676 		 * to double check and ensure we actually are starting
677 		 * with empty lists.
678 		 */
679 		ASSERT(list_is_empty(&sci->sci_new_mapping_entries[i]));
680 	}
681 
682 	VERIFY0(space_map_open(&prev_obsolete_sm, spa->spa_meta_objset,
683 	    scip->scip_prev_obsolete_sm_object, 0, vd->vdev_asize, 0));
684 	counts = vdev_indirect_mapping_load_obsolete_counts(old_mapping);
685 	if (prev_obsolete_sm != NULL) {
686 		vdev_indirect_mapping_load_obsolete_spacemap(old_mapping,
687 		    counts, prev_obsolete_sm);
688 	}
689 	space_map_close(prev_obsolete_sm);
690 
691 	/*
692 	 * Generate new mapping.  Determine what index to continue from
693 	 * based on the max offset that we've already written in the
694 	 * new mapping.
695 	 */
696 	uint64_t max_offset =
697 	    vdev_indirect_mapping_max_offset(sci->sci_new_mapping);
698 	if (max_offset == 0) {
699 		/* We haven't written anything to the new mapping yet. */
700 		start_index = 0;
701 	} else {
702 		/*
703 		 * Pick up from where we left off. _entry_for_offset()
704 		 * returns a pointer into the vim_entries array. If
705 		 * max_offset is greater than any of the mappings
706 		 * contained in the table  NULL will be returned and
707 		 * that indicates we've exhausted our iteration of the
708 		 * old_mapping.
709 		 */
710 
711 		vdev_indirect_mapping_entry_phys_t *entry =
712 		    vdev_indirect_mapping_entry_for_offset_or_next(old_mapping,
713 		    max_offset);
714 
715 		if (entry == NULL) {
716 			/*
717 			 * We've already written the whole new mapping.
718 			 * This special value will cause us to skip the
719 			 * generate_new_mapping step and just do the sync
720 			 * task to complete the condense.
721 			 */
722 			start_index = UINT64_MAX;
723 		} else {
724 			start_index = entry - old_mapping->vim_entries;
725 			ASSERT3U(start_index, <,
726 			    vdev_indirect_mapping_num_entries(old_mapping));
727 		}
728 	}
729 
730 	spa_condense_indirect_generate_new_mapping(vd, counts,
731 	    start_index, zthr);
732 
733 	vdev_indirect_mapping_free_obsolete_counts(old_mapping, counts);
734 
735 	/*
736 	 * If the zthr has received a cancellation signal while running
737 	 * in generate_new_mapping() or at any point after that, then bail
738 	 * early. We don't want to complete the condense if the spa is
739 	 * shutting down.
740 	 */
741 	if (zthr_iscancelled(zthr))
742 		return;
743 
744 	VERIFY0(dsl_sync_task(spa_name(spa), NULL,
745 	    spa_condense_indirect_complete_sync, sci, 0,
746 	    ZFS_SPACE_CHECK_EXTRA_RESERVED));
747 }
748 
749 /*
750  * Sync task to begin the condensing process.
751  */
752 void
spa_condense_indirect_start_sync(vdev_t * vd,dmu_tx_t * tx)753 spa_condense_indirect_start_sync(vdev_t *vd, dmu_tx_t *tx)
754 {
755 	spa_t *spa = vd->vdev_spa;
756 	spa_condensing_indirect_phys_t *scip =
757 	    &spa->spa_condensing_indirect_phys;
758 
759 	ASSERT0(scip->scip_next_mapping_object);
760 	ASSERT0(scip->scip_prev_obsolete_sm_object);
761 	ASSERT0(scip->scip_vdev);
762 	ASSERT(dmu_tx_is_syncing(tx));
763 	ASSERT3P(vd->vdev_ops, ==, &vdev_indirect_ops);
764 	ASSERT(spa_feature_is_active(spa, SPA_FEATURE_OBSOLETE_COUNTS));
765 	ASSERT(vdev_indirect_mapping_num_entries(vd->vdev_indirect_mapping));
766 
767 	uint64_t obsolete_sm_obj = vdev_obsolete_sm_object(vd);
768 	ASSERT(obsolete_sm_obj != 0);
769 
770 	scip->scip_vdev = vd->vdev_id;
771 	scip->scip_next_mapping_object =
772 	    vdev_indirect_mapping_alloc(spa->spa_meta_objset, tx);
773 
774 	scip->scip_prev_obsolete_sm_object = obsolete_sm_obj;
775 
776 	/*
777 	 * We don't need to allocate a new space map object, since
778 	 * vdev_indirect_sync_obsolete will allocate one when needed.
779 	 */
780 	space_map_close(vd->vdev_obsolete_sm);
781 	vd->vdev_obsolete_sm = NULL;
782 	VERIFY0(zap_remove(spa->spa_meta_objset, vd->vdev_top_zap,
783 	    VDEV_TOP_ZAP_INDIRECT_OBSOLETE_SM, tx));
784 
785 	VERIFY0(zap_add(spa->spa_dsl_pool->dp_meta_objset,
786 	    DMU_POOL_DIRECTORY_OBJECT,
787 	    DMU_POOL_CONDENSING_INDIRECT, sizeof (uint64_t),
788 	    sizeof (*scip) / sizeof (uint64_t), scip, tx));
789 
790 	ASSERT3P(spa->spa_condensing_indirect, ==, NULL);
791 	spa->spa_condensing_indirect = spa_condensing_indirect_create(spa);
792 
793 	zfs_dbgmsg("starting condense of vdev %llu in txg %llu: "
794 	    "posm=%llu nm=%llu",
795 	    vd->vdev_id, dmu_tx_get_txg(tx),
796 	    (u_longlong_t)scip->scip_prev_obsolete_sm_object,
797 	    (u_longlong_t)scip->scip_next_mapping_object);
798 
799 	zthr_wakeup(spa->spa_condense_zthr);
800 }
801 
802 /*
803  * Sync to the given vdev's obsolete space map any segments that are no longer
804  * referenced as of the given txg.
805  *
806  * If the obsolete space map doesn't exist yet, create and open it.
807  */
808 void
vdev_indirect_sync_obsolete(vdev_t * vd,dmu_tx_t * tx)809 vdev_indirect_sync_obsolete(vdev_t *vd, dmu_tx_t *tx)
810 {
811 	spa_t *spa = vd->vdev_spa;
812 	vdev_indirect_config_t *vic = &vd->vdev_indirect_config;
813 
814 	ASSERT3U(vic->vic_mapping_object, !=, 0);
815 	ASSERT(range_tree_space(vd->vdev_obsolete_segments) > 0);
816 	ASSERT(vd->vdev_removing || vd->vdev_ops == &vdev_indirect_ops);
817 	ASSERT(spa_feature_is_enabled(spa, SPA_FEATURE_OBSOLETE_COUNTS));
818 
819 	if (vdev_obsolete_sm_object(vd) == 0) {
820 		uint64_t obsolete_sm_object =
821 		    space_map_alloc(spa->spa_meta_objset,
822 		    zfs_vdev_standard_sm_blksz, tx);
823 
824 		ASSERT(vd->vdev_top_zap != 0);
825 		VERIFY0(zap_add(vd->vdev_spa->spa_meta_objset, vd->vdev_top_zap,
826 		    VDEV_TOP_ZAP_INDIRECT_OBSOLETE_SM,
827 		    sizeof (obsolete_sm_object), 1, &obsolete_sm_object, tx));
828 		ASSERT3U(vdev_obsolete_sm_object(vd), !=, 0);
829 
830 		spa_feature_incr(spa, SPA_FEATURE_OBSOLETE_COUNTS, tx);
831 		VERIFY0(space_map_open(&vd->vdev_obsolete_sm,
832 		    spa->spa_meta_objset, obsolete_sm_object,
833 		    0, vd->vdev_asize, 0));
834 	}
835 
836 	ASSERT(vd->vdev_obsolete_sm != NULL);
837 	ASSERT3U(vdev_obsolete_sm_object(vd), ==,
838 	    space_map_object(vd->vdev_obsolete_sm));
839 
840 	space_map_write(vd->vdev_obsolete_sm,
841 	    vd->vdev_obsolete_segments, SM_ALLOC, SM_NO_VDEVID, tx);
842 	range_tree_vacate(vd->vdev_obsolete_segments, NULL, NULL);
843 }
844 
845 int
spa_condense_init(spa_t * spa)846 spa_condense_init(spa_t *spa)
847 {
848 	int error = zap_lookup(spa->spa_meta_objset,
849 	    DMU_POOL_DIRECTORY_OBJECT,
850 	    DMU_POOL_CONDENSING_INDIRECT, sizeof (uint64_t),
851 	    sizeof (spa->spa_condensing_indirect_phys) / sizeof (uint64_t),
852 	    &spa->spa_condensing_indirect_phys);
853 	if (error == 0) {
854 		if (spa_writeable(spa)) {
855 			spa->spa_condensing_indirect =
856 			    spa_condensing_indirect_create(spa);
857 		}
858 		return (0);
859 	} else if (error == ENOENT) {
860 		return (0);
861 	} else {
862 		return (error);
863 	}
864 }
865 
866 void
spa_condense_fini(spa_t * spa)867 spa_condense_fini(spa_t *spa)
868 {
869 	if (spa->spa_condensing_indirect != NULL) {
870 		spa_condensing_indirect_destroy(spa->spa_condensing_indirect);
871 		spa->spa_condensing_indirect = NULL;
872 	}
873 }
874 
875 void
spa_start_indirect_condensing_thread(spa_t * spa)876 spa_start_indirect_condensing_thread(spa_t *spa)
877 {
878 	ASSERT3P(spa->spa_condense_zthr, ==, NULL);
879 	spa->spa_condense_zthr = zthr_create(spa_condense_indirect_thread_check,
880 	    spa_condense_indirect_thread, spa);
881 }
882 
883 /*
884  * Gets the obsolete spacemap object from the vdev's ZAP.
885  * Returns the spacemap object, or 0 if it wasn't in the ZAP or the ZAP doesn't
886  * exist yet.
887  */
888 int
vdev_obsolete_sm_object(vdev_t * vd)889 vdev_obsolete_sm_object(vdev_t *vd)
890 {
891 	ASSERT0(spa_config_held(vd->vdev_spa, SCL_ALL, RW_WRITER));
892 	if (vd->vdev_top_zap == 0) {
893 		return (0);
894 	}
895 
896 	uint64_t sm_obj = 0;
897 	int err = zap_lookup(vd->vdev_spa->spa_meta_objset, vd->vdev_top_zap,
898 	    VDEV_TOP_ZAP_INDIRECT_OBSOLETE_SM, sizeof (sm_obj), 1, &sm_obj);
899 
900 	ASSERT(err == 0 || err == ENOENT);
901 
902 	return (sm_obj);
903 }
904 
905 boolean_t
vdev_obsolete_counts_are_precise(vdev_t * vd)906 vdev_obsolete_counts_are_precise(vdev_t *vd)
907 {
908 	ASSERT0(spa_config_held(vd->vdev_spa, SCL_ALL, RW_WRITER));
909 	if (vd->vdev_top_zap == 0) {
910 		return (B_FALSE);
911 	}
912 
913 	uint64_t val = 0;
914 	int err = zap_lookup(vd->vdev_spa->spa_meta_objset, vd->vdev_top_zap,
915 	    VDEV_TOP_ZAP_OBSOLETE_COUNTS_ARE_PRECISE, sizeof (val), 1, &val);
916 
917 	ASSERT(err == 0 || err == ENOENT);
918 
919 	return (val != 0);
920 }
921 
922 /* ARGSUSED */
923 static void
vdev_indirect_close(vdev_t * vd)924 vdev_indirect_close(vdev_t *vd)
925 {
926 }
927 
928 /* ARGSUSED */
929 static int
vdev_indirect_open(vdev_t * vd,uint64_t * psize,uint64_t * max_psize,uint64_t * ashift)930 vdev_indirect_open(vdev_t *vd, uint64_t *psize, uint64_t *max_psize,
931     uint64_t *ashift)
932 {
933 	*psize = *max_psize = vd->vdev_asize +
934 	    VDEV_LABEL_START_SIZE + VDEV_LABEL_END_SIZE;
935 	*ashift = vd->vdev_ashift;
936 	return (0);
937 }
938 
939 typedef struct remap_segment {
940 	vdev_t *rs_vd;
941 	uint64_t rs_offset;
942 	uint64_t rs_asize;
943 	uint64_t rs_split_offset;
944 	list_node_t rs_node;
945 } remap_segment_t;
946 
947 remap_segment_t *
rs_alloc(vdev_t * vd,uint64_t offset,uint64_t asize,uint64_t split_offset)948 rs_alloc(vdev_t *vd, uint64_t offset, uint64_t asize, uint64_t split_offset)
949 {
950 	remap_segment_t *rs = kmem_alloc(sizeof (remap_segment_t), KM_SLEEP);
951 	rs->rs_vd = vd;
952 	rs->rs_offset = offset;
953 	rs->rs_asize = asize;
954 	rs->rs_split_offset = split_offset;
955 	return (rs);
956 }
957 
958 /*
959  * Given an indirect vdev and an extent on that vdev, it duplicates the
960  * physical entries of the indirect mapping that correspond to the extent
961  * to a new array and returns a pointer to it. In addition, copied_entries
962  * is populated with the number of mapping entries that were duplicated.
963  *
964  * Note that the function assumes that the caller holds vdev_indirect_rwlock.
965  * This ensures that the mapping won't change due to condensing as we
966  * copy over its contents.
967  *
968  * Finally, since we are doing an allocation, it is up to the caller to
969  * free the array allocated in this function.
970  */
971 vdev_indirect_mapping_entry_phys_t *
vdev_indirect_mapping_duplicate_adjacent_entries(vdev_t * vd,uint64_t offset,uint64_t asize,uint64_t * copied_entries)972 vdev_indirect_mapping_duplicate_adjacent_entries(vdev_t *vd, uint64_t offset,
973     uint64_t asize, uint64_t *copied_entries)
974 {
975 	vdev_indirect_mapping_entry_phys_t *duplicate_mappings = NULL;
976 	vdev_indirect_mapping_t *vim = vd->vdev_indirect_mapping;
977 	uint64_t entries = 0;
978 
979 	ASSERT(RW_READ_HELD(&vd->vdev_indirect_rwlock));
980 
981 	vdev_indirect_mapping_entry_phys_t *first_mapping =
982 	    vdev_indirect_mapping_entry_for_offset(vim, offset);
983 	ASSERT3P(first_mapping, !=, NULL);
984 
985 	vdev_indirect_mapping_entry_phys_t *m = first_mapping;
986 	while (asize > 0) {
987 		uint64_t size = DVA_GET_ASIZE(&m->vimep_dst);
988 
989 		ASSERT3U(offset, >=, DVA_MAPPING_GET_SRC_OFFSET(m));
990 		ASSERT3U(offset, <, DVA_MAPPING_GET_SRC_OFFSET(m) + size);
991 
992 		uint64_t inner_offset = offset - DVA_MAPPING_GET_SRC_OFFSET(m);
993 		uint64_t inner_size = MIN(asize, size - inner_offset);
994 
995 		offset += inner_size;
996 		asize -= inner_size;
997 		entries++;
998 		m++;
999 	}
1000 
1001 	size_t copy_length = entries * sizeof (*first_mapping);
1002 	duplicate_mappings = kmem_alloc(copy_length, KM_SLEEP);
1003 	bcopy(first_mapping, duplicate_mappings, copy_length);
1004 	*copied_entries = entries;
1005 
1006 	return (duplicate_mappings);
1007 }
1008 
1009 /*
1010  * Goes through the relevant indirect mappings until it hits a concrete vdev
1011  * and issues the callback. On the way to the concrete vdev, if any other
1012  * indirect vdevs are encountered, then the callback will also be called on
1013  * each of those indirect vdevs. For example, if the segment is mapped to
1014  * segment A on indirect vdev 1, and then segment A on indirect vdev 1 is
1015  * mapped to segment B on concrete vdev 2, then the callback will be called on
1016  * both vdev 1 and vdev 2.
1017  *
1018  * While the callback passed to vdev_indirect_remap() is called on every vdev
1019  * the function encounters, certain callbacks only care about concrete vdevs.
1020  * These types of callbacks should return immediately and explicitly when they
1021  * are called on an indirect vdev.
1022  *
1023  * Because there is a possibility that a DVA section in the indirect device
1024  * has been split into multiple sections in our mapping, we keep track
1025  * of the relevant contiguous segments of the new location (remap_segment_t)
1026  * in a stack. This way we can call the callback for each of the new sections
1027  * created by a single section of the indirect device. Note though, that in
1028  * this scenario the callbacks in each split block won't occur in-order in
1029  * terms of offset, so callers should not make any assumptions about that.
1030  *
1031  * For callbacks that don't handle split blocks and immediately return when
1032  * they encounter them (as is the case for remap_blkptr_cb), the caller can
1033  * assume that its callback will be applied from the first indirect vdev
1034  * encountered to the last one and then the concrete vdev, in that order.
1035  */
1036 static void
vdev_indirect_remap(vdev_t * vd,uint64_t offset,uint64_t asize,void (* func)(uint64_t,vdev_t *,uint64_t,uint64_t,void *),void * arg)1037 vdev_indirect_remap(vdev_t *vd, uint64_t offset, uint64_t asize,
1038     void (*func)(uint64_t, vdev_t *, uint64_t, uint64_t, void *), void *arg)
1039 {
1040 	list_t stack;
1041 	spa_t *spa = vd->vdev_spa;
1042 
1043 	list_create(&stack, sizeof (remap_segment_t),
1044 	    offsetof(remap_segment_t, rs_node));
1045 
1046 	for (remap_segment_t *rs = rs_alloc(vd, offset, asize, 0);
1047 	    rs != NULL; rs = list_remove_head(&stack)) {
1048 		vdev_t *v = rs->rs_vd;
1049 		uint64_t num_entries = 0;
1050 
1051 		ASSERT(spa_config_held(spa, SCL_ALL, RW_READER) != 0);
1052 		ASSERT(rs->rs_asize > 0);
1053 
1054 		/*
1055 		 * Note: As this function can be called from open context
1056 		 * (e.g. zio_read()), we need the following rwlock to
1057 		 * prevent the mapping from being changed by condensing.
1058 		 *
1059 		 * So we grab the lock and we make a copy of the entries
1060 		 * that are relevant to the extent that we are working on.
1061 		 * Once that is done, we drop the lock and iterate over
1062 		 * our copy of the mapping. Once we are done with the with
1063 		 * the remap segment and we free it, we also free our copy
1064 		 * of the indirect mapping entries that are relevant to it.
1065 		 *
1066 		 * This way we don't need to wait until the function is
1067 		 * finished with a segment, to condense it. In addition, we
1068 		 * don't need a recursive rwlock for the case that a call to
1069 		 * vdev_indirect_remap() needs to call itself (through the
1070 		 * codepath of its callback) for the same vdev in the middle
1071 		 * of its execution.
1072 		 */
1073 		rw_enter(&v->vdev_indirect_rwlock, RW_READER);
1074 		vdev_indirect_mapping_t *vim = v->vdev_indirect_mapping;
1075 		ASSERT3P(vim, !=, NULL);
1076 
1077 		vdev_indirect_mapping_entry_phys_t *mapping =
1078 		    vdev_indirect_mapping_duplicate_adjacent_entries(v,
1079 		    rs->rs_offset, rs->rs_asize, &num_entries);
1080 		ASSERT3P(mapping, !=, NULL);
1081 		ASSERT3U(num_entries, >, 0);
1082 		rw_exit(&v->vdev_indirect_rwlock);
1083 
1084 		for (uint64_t i = 0; i < num_entries; i++) {
1085 			/*
1086 			 * Note: the vdev_indirect_mapping can not change
1087 			 * while we are running.  It only changes while the
1088 			 * removal is in progress, and then only from syncing
1089 			 * context. While a removal is in progress, this
1090 			 * function is only called for frees, which also only
1091 			 * happen from syncing context.
1092 			 */
1093 			vdev_indirect_mapping_entry_phys_t *m = &mapping[i];
1094 
1095 			ASSERT3P(m, !=, NULL);
1096 			ASSERT3U(rs->rs_asize, >, 0);
1097 
1098 			uint64_t size = DVA_GET_ASIZE(&m->vimep_dst);
1099 			uint64_t dst_offset = DVA_GET_OFFSET(&m->vimep_dst);
1100 			uint64_t dst_vdev = DVA_GET_VDEV(&m->vimep_dst);
1101 
1102 			ASSERT3U(rs->rs_offset, >=,
1103 			    DVA_MAPPING_GET_SRC_OFFSET(m));
1104 			ASSERT3U(rs->rs_offset, <,
1105 			    DVA_MAPPING_GET_SRC_OFFSET(m) + size);
1106 			ASSERT3U(dst_vdev, !=, v->vdev_id);
1107 
1108 			uint64_t inner_offset = rs->rs_offset -
1109 			    DVA_MAPPING_GET_SRC_OFFSET(m);
1110 			uint64_t inner_size =
1111 			    MIN(rs->rs_asize, size - inner_offset);
1112 
1113 			vdev_t *dst_v = vdev_lookup_top(spa, dst_vdev);
1114 			ASSERT3P(dst_v, !=, NULL);
1115 
1116 			if (dst_v->vdev_ops == &vdev_indirect_ops) {
1117 				list_insert_head(&stack,
1118 				    rs_alloc(dst_v, dst_offset + inner_offset,
1119 				    inner_size, rs->rs_split_offset));
1120 
1121 			}
1122 
1123 			if ((zfs_flags & ZFS_DEBUG_INDIRECT_REMAP) &&
1124 			    IS_P2ALIGNED(inner_size, 2 * SPA_MINBLOCKSIZE)) {
1125 				/*
1126 				 * Note: This clause exists only solely for
1127 				 * testing purposes. We use it to ensure that
1128 				 * split blocks work and that the callbacks
1129 				 * using them yield the same result if issued
1130 				 * in reverse order.
1131 				 */
1132 				uint64_t inner_half = inner_size / 2;
1133 
1134 				func(rs->rs_split_offset + inner_half, dst_v,
1135 				    dst_offset + inner_offset + inner_half,
1136 				    inner_half, arg);
1137 
1138 				func(rs->rs_split_offset, dst_v,
1139 				    dst_offset + inner_offset,
1140 				    inner_half, arg);
1141 			} else {
1142 				func(rs->rs_split_offset, dst_v,
1143 				    dst_offset + inner_offset,
1144 				    inner_size, arg);
1145 			}
1146 
1147 			rs->rs_offset += inner_size;
1148 			rs->rs_asize -= inner_size;
1149 			rs->rs_split_offset += inner_size;
1150 		}
1151 		VERIFY0(rs->rs_asize);
1152 
1153 		kmem_free(mapping, num_entries * sizeof (*mapping));
1154 		kmem_free(rs, sizeof (remap_segment_t));
1155 	}
1156 	list_destroy(&stack);
1157 }
1158 
1159 static void
vdev_indirect_child_io_done(zio_t * zio)1160 vdev_indirect_child_io_done(zio_t *zio)
1161 {
1162 	zio_t *pio = zio->io_private;
1163 
1164 	mutex_enter(&pio->io_lock);
1165 	pio->io_error = zio_worst_error(pio->io_error, zio->io_error);
1166 	mutex_exit(&pio->io_lock);
1167 
1168 	abd_put(zio->io_abd);
1169 }
1170 
1171 /*
1172  * This is a callback for vdev_indirect_remap() which allocates an
1173  * indirect_split_t for each split segment and adds it to iv_splits.
1174  */
1175 static void
vdev_indirect_gather_splits(uint64_t split_offset,vdev_t * vd,uint64_t offset,uint64_t size,void * arg)1176 vdev_indirect_gather_splits(uint64_t split_offset, vdev_t *vd, uint64_t offset,
1177     uint64_t size, void *arg)
1178 {
1179 	zio_t *zio = arg;
1180 	indirect_vsd_t *iv = zio->io_vsd;
1181 
1182 	ASSERT3P(vd, !=, NULL);
1183 
1184 	if (vd->vdev_ops == &vdev_indirect_ops)
1185 		return;
1186 
1187 	int n = 1;
1188 	if (vd->vdev_ops == &vdev_mirror_ops)
1189 		n = vd->vdev_children;
1190 
1191 	indirect_split_t *is =
1192 	    kmem_zalloc(offsetof(indirect_split_t, is_child[n]), KM_SLEEP);
1193 
1194 	is->is_children = n;
1195 	is->is_size = size;
1196 	is->is_split_offset = split_offset;
1197 	is->is_target_offset = offset;
1198 	is->is_vdev = vd;
1199 	list_create(&is->is_unique_child, sizeof (indirect_child_t),
1200 	    offsetof(indirect_child_t, ic_node));
1201 
1202 	/*
1203 	 * Note that we only consider multiple copies of the data for
1204 	 * *mirror* vdevs.  We don't for "replacing" or "spare" vdevs, even
1205 	 * though they use the same ops as mirror, because there's only one
1206 	 * "good" copy under the replacing/spare.
1207 	 */
1208 	if (vd->vdev_ops == &vdev_mirror_ops) {
1209 		for (int i = 0; i < n; i++) {
1210 			is->is_child[i].ic_vdev = vd->vdev_child[i];
1211 			list_link_init(&is->is_child[i].ic_node);
1212 		}
1213 	} else {
1214 		is->is_child[0].ic_vdev = vd;
1215 	}
1216 
1217 	list_insert_tail(&iv->iv_splits, is);
1218 }
1219 
1220 static void
vdev_indirect_read_split_done(zio_t * zio)1221 vdev_indirect_read_split_done(zio_t *zio)
1222 {
1223 	indirect_child_t *ic = zio->io_private;
1224 
1225 	if (zio->io_error != 0) {
1226 		/*
1227 		 * Clear ic_data to indicate that we do not have data for this
1228 		 * child.
1229 		 */
1230 		abd_free(ic->ic_data);
1231 		ic->ic_data = NULL;
1232 	}
1233 }
1234 
1235 /*
1236  * Issue reads for all copies (mirror children) of all splits.
1237  */
1238 static void
vdev_indirect_read_all(zio_t * zio)1239 vdev_indirect_read_all(zio_t *zio)
1240 {
1241 	indirect_vsd_t *iv = zio->io_vsd;
1242 
1243 	ASSERT3U(zio->io_type, ==, ZIO_TYPE_READ);
1244 
1245 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1246 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1247 		for (int i = 0; i < is->is_children; i++) {
1248 			indirect_child_t *ic = &is->is_child[i];
1249 
1250 			if (!vdev_readable(ic->ic_vdev))
1251 				continue;
1252 
1253 			/*
1254 			 * Note, we may read from a child whose DTL
1255 			 * indicates that the data may not be present here.
1256 			 * While this might result in a few i/os that will
1257 			 * likely return incorrect data, it simplifies the
1258 			 * code since we can treat scrub and resilver
1259 			 * identically.  (The incorrect data will be
1260 			 * detected and ignored when we verify the
1261 			 * checksum.)
1262 			 */
1263 
1264 			ic->ic_data = abd_alloc_sametype(zio->io_abd,
1265 			    is->is_size);
1266 			ic->ic_duplicate = NULL;
1267 
1268 			zio_nowait(zio_vdev_child_io(zio, NULL,
1269 			    ic->ic_vdev, is->is_target_offset, ic->ic_data,
1270 			    is->is_size, zio->io_type, zio->io_priority, 0,
1271 			    vdev_indirect_read_split_done, ic));
1272 		}
1273 	}
1274 	iv->iv_reconstruct = B_TRUE;
1275 }
1276 
1277 static void
vdev_indirect_io_start(zio_t * zio)1278 vdev_indirect_io_start(zio_t *zio)
1279 {
1280 	spa_t *spa = zio->io_spa;
1281 	indirect_vsd_t *iv = kmem_zalloc(sizeof (*iv), KM_SLEEP);
1282 	list_create(&iv->iv_splits,
1283 	    sizeof (indirect_split_t), offsetof(indirect_split_t, is_node));
1284 
1285 	zio->io_vsd = iv;
1286 	zio->io_vsd_ops = &vdev_indirect_vsd_ops;
1287 
1288 	ASSERT(spa_config_held(spa, SCL_ALL, RW_READER) != 0);
1289 	if (zio->io_type != ZIO_TYPE_READ) {
1290 		ASSERT3U(zio->io_type, ==, ZIO_TYPE_WRITE);
1291 		/*
1292 		 * Note: this code can handle other kinds of writes,
1293 		 * but we don't expect them.
1294 		 */
1295 		ASSERT((zio->io_flags & (ZIO_FLAG_SELF_HEAL |
1296 		    ZIO_FLAG_RESILVER | ZIO_FLAG_INDUCE_DAMAGE)) != 0);
1297 	}
1298 
1299 	vdev_indirect_remap(zio->io_vd, zio->io_offset, zio->io_size,
1300 	    vdev_indirect_gather_splits, zio);
1301 
1302 	indirect_split_t *first = list_head(&iv->iv_splits);
1303 	if (first->is_size == zio->io_size) {
1304 		/*
1305 		 * This is not a split block; we are pointing to the entire
1306 		 * data, which will checksum the same as the original data.
1307 		 * Pass the BP down so that the child i/o can verify the
1308 		 * checksum, and try a different location if available
1309 		 * (e.g. on a mirror).
1310 		 *
1311 		 * While this special case could be handled the same as the
1312 		 * general (split block) case, doing it this way ensures
1313 		 * that the vast majority of blocks on indirect vdevs
1314 		 * (which are not split) are handled identically to blocks
1315 		 * on non-indirect vdevs.  This allows us to be less strict
1316 		 * about performance in the general (but rare) case.
1317 		 */
1318 		ASSERT0(first->is_split_offset);
1319 		ASSERT3P(list_next(&iv->iv_splits, first), ==, NULL);
1320 		zio_nowait(zio_vdev_child_io(zio, zio->io_bp,
1321 		    first->is_vdev, first->is_target_offset,
1322 		    abd_get_offset(zio->io_abd, 0),
1323 		    zio->io_size, zio->io_type, zio->io_priority, 0,
1324 		    vdev_indirect_child_io_done, zio));
1325 	} else {
1326 		iv->iv_split_block = B_TRUE;
1327 		if (zio->io_type == ZIO_TYPE_READ &&
1328 		    zio->io_flags & (ZIO_FLAG_SCRUB | ZIO_FLAG_RESILVER)) {
1329 			/*
1330 			 * Read all copies.  Note that for simplicity,
1331 			 * we don't bother consulting the DTL in the
1332 			 * resilver case.
1333 			 */
1334 			vdev_indirect_read_all(zio);
1335 		} else {
1336 			/*
1337 			 * If this is a read zio, we read one copy of each
1338 			 * split segment, from the top-level vdev.  Since
1339 			 * we don't know the checksum of each split
1340 			 * individually, the child zio can't ensure that
1341 			 * we get the right data. E.g. if it's a mirror,
1342 			 * it will just read from a random (healthy) leaf
1343 			 * vdev. We have to verify the checksum in
1344 			 * vdev_indirect_io_done().
1345 			 *
1346 			 * For write zios, the vdev code will ensure we write
1347 			 * to all children.
1348 			 */
1349 			for (indirect_split_t *is = list_head(&iv->iv_splits);
1350 			    is != NULL; is = list_next(&iv->iv_splits, is)) {
1351 				zio_nowait(zio_vdev_child_io(zio, NULL,
1352 				    is->is_vdev, is->is_target_offset,
1353 				    abd_get_offset(zio->io_abd,
1354 				    is->is_split_offset),
1355 				    is->is_size, zio->io_type,
1356 				    zio->io_priority, 0,
1357 				    vdev_indirect_child_io_done, zio));
1358 			}
1359 		}
1360 	}
1361 
1362 	zio_execute(zio);
1363 }
1364 
1365 /*
1366  * Report a checksum error for a child.
1367  */
1368 static void
vdev_indirect_checksum_error(zio_t * zio,indirect_split_t * is,indirect_child_t * ic)1369 vdev_indirect_checksum_error(zio_t *zio,
1370     indirect_split_t *is, indirect_child_t *ic)
1371 {
1372 	vdev_t *vd = ic->ic_vdev;
1373 
1374 	if (zio->io_flags & ZIO_FLAG_SPECULATIVE)
1375 		return;
1376 
1377 	mutex_enter(&vd->vdev_stat_lock);
1378 	vd->vdev_stat.vs_checksum_errors++;
1379 	mutex_exit(&vd->vdev_stat_lock);
1380 
1381 	zio_bad_cksum_t zbc = { 0 };
1382 	void *bad_buf = abd_borrow_buf_copy(ic->ic_data, is->is_size);
1383 	abd_t *good_abd = is->is_good_child->ic_data;
1384 	void *good_buf = abd_borrow_buf_copy(good_abd, is->is_size);
1385 	(void) zfs_ereport_post_checksum(zio->io_spa, vd, &zio->io_bookmark,
1386 	    zio, is->is_target_offset, is->is_size, good_buf, bad_buf, &zbc);
1387 	abd_return_buf(ic->ic_data, bad_buf, is->is_size);
1388 	abd_return_buf(good_abd, good_buf, is->is_size);
1389 }
1390 
1391 /*
1392  * Issue repair i/os for any incorrect copies.  We do this by comparing
1393  * each split segment's correct data (is_good_child's ic_data) with each
1394  * other copy of the data.  If they differ, then we overwrite the bad data
1395  * with the good copy.  Note that we do this without regard for the DTL's,
1396  * which simplifies this code and also issues the optimal number of writes
1397  * (based on which copies actually read bad data, as opposed to which we
1398  * think might be wrong).  For the same reason, we always use
1399  * ZIO_FLAG_SELF_HEAL, to bypass the DTL check in zio_vdev_io_start().
1400  */
1401 static void
vdev_indirect_repair(zio_t * zio)1402 vdev_indirect_repair(zio_t *zio)
1403 {
1404 	indirect_vsd_t *iv = zio->io_vsd;
1405 
1406 	enum zio_flag flags = ZIO_FLAG_IO_REPAIR;
1407 
1408 	if (!(zio->io_flags & (ZIO_FLAG_SCRUB | ZIO_FLAG_RESILVER)))
1409 		flags |= ZIO_FLAG_SELF_HEAL;
1410 
1411 	if (!spa_writeable(zio->io_spa))
1412 		return;
1413 
1414 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1415 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1416 		for (int c = 0; c < is->is_children; c++) {
1417 			indirect_child_t *ic = &is->is_child[c];
1418 			if (ic == is->is_good_child)
1419 				continue;
1420 			if (ic->ic_data == NULL)
1421 				continue;
1422 			if (ic->ic_duplicate == is->is_good_child)
1423 				continue;
1424 
1425 			zio_nowait(zio_vdev_child_io(zio, NULL,
1426 			    ic->ic_vdev, is->is_target_offset,
1427 			    is->is_good_child->ic_data, is->is_size,
1428 			    ZIO_TYPE_WRITE, ZIO_PRIORITY_ASYNC_WRITE,
1429 			    ZIO_FLAG_IO_REPAIR | ZIO_FLAG_SELF_HEAL,
1430 			    NULL, NULL));
1431 
1432 			vdev_indirect_checksum_error(zio, is, ic);
1433 		}
1434 	}
1435 }
1436 
1437 /*
1438  * Report checksum errors on all children that we read from.
1439  */
1440 static void
vdev_indirect_all_checksum_errors(zio_t * zio)1441 vdev_indirect_all_checksum_errors(zio_t *zio)
1442 {
1443 	indirect_vsd_t *iv = zio->io_vsd;
1444 
1445 	if (zio->io_flags & ZIO_FLAG_SPECULATIVE)
1446 		return;
1447 
1448 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1449 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1450 		for (int c = 0; c < is->is_children; c++) {
1451 			indirect_child_t *ic = &is->is_child[c];
1452 
1453 			if (ic->ic_data == NULL)
1454 				continue;
1455 
1456 			vdev_t *vd = ic->ic_vdev;
1457 
1458 			mutex_enter(&vd->vdev_stat_lock);
1459 			vd->vdev_stat.vs_checksum_errors++;
1460 			mutex_exit(&vd->vdev_stat_lock);
1461 
1462 			(void) zfs_ereport_post_checksum(zio->io_spa, vd,
1463 			    &zio->io_bookmark, zio, is->is_target_offset,
1464 			    is->is_size, NULL, NULL, NULL);
1465 		}
1466 	}
1467 }
1468 
1469 /*
1470  * Copy data from all the splits to a main zio then validate the checksum.
1471  * If then checksum is successfully validated return success.
1472  */
1473 static int
vdev_indirect_splits_checksum_validate(indirect_vsd_t * iv,zio_t * zio)1474 vdev_indirect_splits_checksum_validate(indirect_vsd_t *iv, zio_t *zio)
1475 {
1476 	zio_bad_cksum_t zbc;
1477 
1478 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1479 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1480 
1481 		ASSERT3P(is->is_good_child->ic_data, !=, NULL);
1482 		ASSERT3P(is->is_good_child->ic_duplicate, ==, NULL);
1483 
1484 		abd_copy_off(zio->io_abd, is->is_good_child->ic_data,
1485 		    is->is_split_offset, 0, is->is_size);
1486 	}
1487 
1488 	return (zio_checksum_error(zio, &zbc));
1489 }
1490 
1491 /*
1492  * There are relatively few possible combinations making it feasible to
1493  * deterministically check them all.  We do this by setting the good_child
1494  * to the next unique split version.  If we reach the end of the list then
1495  * "carry over" to the next unique split version (like counting in base
1496  * is_unique_children, but each digit can have a different base).
1497  */
1498 static int
vdev_indirect_splits_enumerate_all(indirect_vsd_t * iv,zio_t * zio)1499 vdev_indirect_splits_enumerate_all(indirect_vsd_t *iv, zio_t *zio)
1500 {
1501 	boolean_t more = B_TRUE;
1502 
1503 	iv->iv_attempts = 0;
1504 
1505 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1506 	    is != NULL; is = list_next(&iv->iv_splits, is))
1507 		is->is_good_child = list_head(&is->is_unique_child);
1508 
1509 	while (more == B_TRUE) {
1510 		iv->iv_attempts++;
1511 		more = B_FALSE;
1512 
1513 		if (vdev_indirect_splits_checksum_validate(iv, zio) == 0)
1514 			return (0);
1515 
1516 		for (indirect_split_t *is = list_head(&iv->iv_splits);
1517 		    is != NULL; is = list_next(&iv->iv_splits, is)) {
1518 			is->is_good_child = list_next(&is->is_unique_child,
1519 			    is->is_good_child);
1520 			if (is->is_good_child != NULL) {
1521 				more = B_TRUE;
1522 				break;
1523 			}
1524 
1525 			is->is_good_child = list_head(&is->is_unique_child);
1526 		}
1527 	}
1528 
1529 	ASSERT3S(iv->iv_attempts, <=, iv->iv_unique_combinations);
1530 
1531 	return (SET_ERROR(ECKSUM));
1532 }
1533 
1534 /*
1535  * There are too many combinations to try all of them in a reasonable amount
1536  * of time.  So try a fixed number of random combinations from the unique
1537  * split versions, after which we'll consider the block unrecoverable.
1538  */
1539 static int
vdev_indirect_splits_enumerate_randomly(indirect_vsd_t * iv,zio_t * zio)1540 vdev_indirect_splits_enumerate_randomly(indirect_vsd_t *iv, zio_t *zio)
1541 {
1542 	iv->iv_attempts = 0;
1543 
1544 	while (iv->iv_attempts < iv->iv_attempts_max) {
1545 		iv->iv_attempts++;
1546 
1547 		for (indirect_split_t *is = list_head(&iv->iv_splits);
1548 		    is != NULL; is = list_next(&iv->iv_splits, is)) {
1549 			indirect_child_t *ic = list_head(&is->is_unique_child);
1550 			int children = is->is_unique_children;
1551 
1552 			for (int i = spa_get_random(children); i > 0; i--)
1553 				ic = list_next(&is->is_unique_child, ic);
1554 
1555 			ASSERT3P(ic, !=, NULL);
1556 			is->is_good_child = ic;
1557 		}
1558 
1559 		if (vdev_indirect_splits_checksum_validate(iv, zio) == 0)
1560 			return (0);
1561 	}
1562 
1563 	return (SET_ERROR(ECKSUM));
1564 }
1565 
1566 /*
1567  * This is a validation function for reconstruction.  It randomly selects
1568  * a good combination, if one can be found, and then it intentionally
1569  * damages all other segment copes by zeroing them.  This forces the
1570  * reconstruction algorithm to locate the one remaining known good copy.
1571  */
1572 static int
vdev_indirect_splits_damage(indirect_vsd_t * iv,zio_t * zio)1573 vdev_indirect_splits_damage(indirect_vsd_t *iv, zio_t *zio)
1574 {
1575 	/* Presume all the copies are unique for initial selection. */
1576 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1577 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1578 		is->is_unique_children = 0;
1579 
1580 		for (int i = 0; i < is->is_children; i++) {
1581 			indirect_child_t *ic = &is->is_child[i];
1582 			if (ic->ic_data != NULL) {
1583 				is->is_unique_children++;
1584 				list_insert_tail(&is->is_unique_child, ic);
1585 			}
1586 		}
1587 	}
1588 
1589 	/*
1590 	 * Set each is_good_child to a randomly-selected child which
1591 	 * is known to contain validated data.
1592 	 */
1593 	int error = vdev_indirect_splits_enumerate_randomly(iv, zio);
1594 	if (error)
1595 		goto out;
1596 
1597 	/*
1598 	 * Damage all but the known good copy by zeroing it.  This will
1599 	 * result in two or less unique copies per indirect_child_t.
1600 	 * Both may need to be checked in order to reconstruct the block.
1601 	 * Set iv->iv_attempts_max such that all unique combinations will
1602 	 * enumerated, but limit the damage to at most 16 indirect splits.
1603 	 */
1604 	iv->iv_attempts_max = 1;
1605 
1606 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1607 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1608 		for (int c = 0; c < is->is_children; c++) {
1609 			indirect_child_t *ic = &is->is_child[c];
1610 
1611 			if (ic == is->is_good_child)
1612 				continue;
1613 			if (ic->ic_data == NULL)
1614 				continue;
1615 
1616 			abd_zero(ic->ic_data, ic->ic_data->abd_size);
1617 		}
1618 
1619 		iv->iv_attempts_max *= 2;
1620 		if (iv->iv_attempts_max > (1ULL << 16)) {
1621 			iv->iv_attempts_max = UINT64_MAX;
1622 			break;
1623 		}
1624 	}
1625 
1626 out:
1627 	/* Empty the unique children lists so they can be reconstructed. */
1628 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1629 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1630 		indirect_child_t *ic;
1631 		while ((ic = list_head(&is->is_unique_child)) != NULL)
1632 			list_remove(&is->is_unique_child, ic);
1633 
1634 		is->is_unique_children = 0;
1635 	}
1636 
1637 	return (error);
1638 }
1639 
1640 /*
1641  * This function is called when we have read all copies of the data and need
1642  * to try to find a combination of copies that gives us the right checksum.
1643  *
1644  * If we pointed to any mirror vdevs, this effectively does the job of the
1645  * mirror.  The mirror vdev code can't do its own job because we don't know
1646  * the checksum of each split segment individually.
1647  *
1648  * We have to try every unique combination of copies of split segments, until
1649  * we find one that checksums correctly.  Duplicate segment copies are first
1650  * identified and latter skipped during reconstruction.  This optimization
1651  * reduces the search space and ensures that of the remaining combinations
1652  * at most one is correct.
1653  *
1654  * When the total number of combinations is small they can all be checked.
1655  * For example, if we have 3 segments in the split, and each points to a
1656  * 2-way mirror with unique copies, we will have the following pieces of data:
1657  *
1658  *       |     mirror child
1659  * split |     [0]        [1]
1660  * ======|=====================
1661  *   A   |  data_A_0   data_A_1
1662  *   B   |  data_B_0   data_B_1
1663  *   C   |  data_C_0   data_C_1
1664  *
1665  * We will try the following (mirror children)^(number of splits) (2^3=8)
1666  * combinations, which is similar to bitwise-little-endian counting in
1667  * binary.  In general each "digit" corresponds to a split segment, and the
1668  * base of each digit is is_children, which can be different for each
1669  * digit.
1670  *
1671  * "low bit"        "high bit"
1672  *        v                 v
1673  * data_A_0 data_B_0 data_C_0
1674  * data_A_1 data_B_0 data_C_0
1675  * data_A_0 data_B_1 data_C_0
1676  * data_A_1 data_B_1 data_C_0
1677  * data_A_0 data_B_0 data_C_1
1678  * data_A_1 data_B_0 data_C_1
1679  * data_A_0 data_B_1 data_C_1
1680  * data_A_1 data_B_1 data_C_1
1681  *
1682  * Note that the split segments may be on the same or different top-level
1683  * vdevs. In either case, we may need to try lots of combinations (see
1684  * zfs_reconstruct_indirect_combinations_max).  This ensures that if a mirror
1685  * has small silent errors on all of its children, we can still reconstruct
1686  * the correct data, as long as those errors are at sufficiently-separated
1687  * offsets (specifically, separated by the largest block size - default of
1688  * 128KB, but up to 16MB).
1689  */
1690 static void
vdev_indirect_reconstruct_io_done(zio_t * zio)1691 vdev_indirect_reconstruct_io_done(zio_t *zio)
1692 {
1693 	indirect_vsd_t *iv = zio->io_vsd;
1694 	boolean_t known_good = B_FALSE;
1695 	int error;
1696 
1697 	iv->iv_unique_combinations = 1;
1698 	iv->iv_attempts_max = UINT64_MAX;
1699 
1700 	if (zfs_reconstruct_indirect_combinations_max > 0)
1701 		iv->iv_attempts_max = zfs_reconstruct_indirect_combinations_max;
1702 
1703 	/*
1704 	 * If nonzero, every 1/x blocks will be damaged, in order to validate
1705 	 * reconstruction when there are split segments with damaged copies.
1706 	 * Known_good will TRUE when reconstruction is known to be possible.
1707 	 */
1708 	if (zfs_reconstruct_indirect_damage_fraction != 0 &&
1709 	    spa_get_random(zfs_reconstruct_indirect_damage_fraction) == 0)
1710 		known_good = (vdev_indirect_splits_damage(iv, zio) == 0);
1711 
1712 	/*
1713 	 * Determine the unique children for a split segment and add them
1714 	 * to the is_unique_child list.  By restricting reconstruction
1715 	 * to these children, only unique combinations will be considered.
1716 	 * This can vastly reduce the search space when there are a large
1717 	 * number of indirect splits.
1718 	 */
1719 	for (indirect_split_t *is = list_head(&iv->iv_splits);
1720 	    is != NULL; is = list_next(&iv->iv_splits, is)) {
1721 		is->is_unique_children = 0;
1722 
1723 		for (int i = 0; i < is->is_children; i++) {
1724 			indirect_child_t *ic_i = &is->is_child[i];
1725 
1726 			if (ic_i->ic_data == NULL ||
1727 			    ic_i->ic_duplicate != NULL)
1728 				continue;
1729 
1730 			for (int j = i + 1; j < is->is_children; j++) {
1731 				indirect_child_t *ic_j = &is->is_child[j];
1732 
1733 				if (ic_j->ic_data == NULL ||
1734 				    ic_j->ic_duplicate != NULL)
1735 					continue;
1736 
1737 				if (abd_cmp(ic_i->ic_data, ic_j->ic_data,
1738 				    is->is_size) == 0) {
1739 					ic_j->ic_duplicate = ic_i;
1740 				}
1741 			}
1742 
1743 			is->is_unique_children++;
1744 			list_insert_tail(&is->is_unique_child, ic_i);
1745 		}
1746 
1747 		/* Reconstruction is impossible, no valid children */
1748 		EQUIV(list_is_empty(&is->is_unique_child),
1749 		    is->is_unique_children == 0);
1750 		if (list_is_empty(&is->is_unique_child)) {
1751 			zio->io_error = EIO;
1752 			vdev_indirect_all_checksum_errors(zio);
1753 			zio_checksum_verified(zio);
1754 			return;
1755 		}
1756 
1757 		iv->iv_unique_combinations *= is->is_unique_children;
1758 	}
1759 
1760 	if (iv->iv_unique_combinations <= iv->iv_attempts_max)
1761 		error = vdev_indirect_splits_enumerate_all(iv, zio);
1762 	else
1763 		error = vdev_indirect_splits_enumerate_randomly(iv, zio);
1764 
1765 	if (error != 0) {
1766 		/* All attempted combinations failed. */
1767 		ASSERT3B(known_good, ==, B_FALSE);
1768 		zio->io_error = error;
1769 		vdev_indirect_all_checksum_errors(zio);
1770 	} else {
1771 		/*
1772 		 * The checksum has been successfully validated.  Issue
1773 		 * repair I/Os to any copies of splits which don't match
1774 		 * the validated version.
1775 		 */
1776 		ASSERT0(vdev_indirect_splits_checksum_validate(iv, zio));
1777 		vdev_indirect_repair(zio);
1778 		zio_checksum_verified(zio);
1779 	}
1780 }
1781 
1782 static void
vdev_indirect_io_done(zio_t * zio)1783 vdev_indirect_io_done(zio_t *zio)
1784 {
1785 	indirect_vsd_t *iv = zio->io_vsd;
1786 
1787 	if (iv->iv_reconstruct) {
1788 		/*
1789 		 * We have read all copies of the data (e.g. from mirrors),
1790 		 * either because this was a scrub/resilver, or because the
1791 		 * one-copy read didn't checksum correctly.
1792 		 */
1793 		vdev_indirect_reconstruct_io_done(zio);
1794 		return;
1795 	}
1796 
1797 	if (!iv->iv_split_block) {
1798 		/*
1799 		 * This was not a split block, so we passed the BP down,
1800 		 * and the checksum was handled by the (one) child zio.
1801 		 */
1802 		return;
1803 	}
1804 
1805 	zio_bad_cksum_t zbc;
1806 	int ret = zio_checksum_error(zio, &zbc);
1807 	if (ret == 0) {
1808 		zio_checksum_verified(zio);
1809 		return;
1810 	}
1811 
1812 	/*
1813 	 * The checksum didn't match.  Read all copies of all splits, and
1814 	 * then we will try to reconstruct.  The next time
1815 	 * vdev_indirect_io_done() is called, iv_reconstruct will be set.
1816 	 */
1817 	vdev_indirect_read_all(zio);
1818 
1819 	zio_vdev_io_redone(zio);
1820 }
1821 
1822 vdev_ops_t vdev_indirect_ops = {
1823 	.vdev_op_open = vdev_indirect_open,
1824 	.vdev_op_close = vdev_indirect_close,
1825 	.vdev_op_asize = vdev_default_asize,
1826 	.vdev_op_io_start = vdev_indirect_io_start,
1827 	.vdev_op_io_done = vdev_indirect_io_done,
1828 	.vdev_op_state_change = NULL,
1829 	.vdev_op_need_resilver = NULL,
1830 	.vdev_op_hold = NULL,
1831 	.vdev_op_rele = NULL,
1832 	.vdev_op_remap = vdev_indirect_remap,
1833 	.vdev_op_xlate = NULL,
1834 	.vdev_op_dumpio = NULL,
1835 	.vdev_op_type = VDEV_TYPE_INDIRECT,	/* name of this vdev type */
1836 	.vdev_op_leaf = B_FALSE			/* leaf vdev */
1837 };
1838