aboutsummaryrefslogtreecommitdiffstats
path: root/module/zfs/spa_log_spacemap.c
blob: f4c2910ad7fe47bc742c1c316d5cde2011b99292 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright (c) 2018, 2019 by Delphix. All rights reserved.
 */

#include <sys/dmu_objset.h>
#include <sys/metaslab.h>
#include <sys/metaslab_impl.h>
#include <sys/spa.h>
#include <sys/spa_impl.h>
#include <sys/spa_log_spacemap.h>
#include <sys/vdev_impl.h>
#include <sys/zap.h>

/*
 * Log Space Maps
 *
 * Log space maps are an optimization in ZFS metadata allocations for pools
 * whose workloads are primarily random-writes. Random-write workloads are also
 * typically random-free, meaning that they are freeing from locations scattered
 * throughout the pool. This means that each TXG we will have to append some
 * FREE records to almost every metaslab. With log space maps, we hold their
 * changes in memory and log them altogether in one pool-wide space map on-disk
 * for persistence. As more blocks are accumulated in the log space maps and
 * more unflushed changes are accounted in memory, we flush a selected group
 * of metaslabs every TXG to relieve memory pressure and potential overheads
 * when loading the pool. Flushing a metaslab to disk relieves memory as we
 * flush any unflushed changes from memory to disk (i.e. the metaslab's space
 * map) and saves import time by making old log space maps obsolete and
 * eventually destroying them. [A log space map is said to be obsolete when all
 * its entries have made it to their corresponding metaslab space maps].
 *
 * == On disk data structures used ==
 *
 * - The pool has a new feature flag and a new entry in the MOS. The feature
 *   is activated when we create the first log space map and remains active
 *   for the lifetime of the pool. The new entry in the MOS Directory [refer
 *   to DMU_POOL_LOG_SPACEMAP_ZAP] is populated with a ZAP whose key-value
 *   pairs are of the form <key: txg, value: log space map object for that txg>.
 *   This entry is our on-disk reference of the log space maps that exist in
 *   the pool for each TXG and it is used during import to load all the
 *   metaslab unflushed changes in memory. To see how this structure is first
 *   created and later populated refer to spa_generate_syncing_log_sm(). To see
 *   how it is used during import time refer to spa_ld_log_sm_metadata().
 *
 * - Each vdev has a new entry in its vdev_top_zap (see field
 *   VDEV_TOP_ZAP_MS_UNFLUSHED_PHYS_TXGS) which holds the msp_unflushed_txg of
 *   each metaslab in this vdev. This field is the on-disk counterpart of the
 *   in-memory field ms_unflushed_txg which tells us from which TXG and onwards
 *   the metaslab haven't had its changes flushed. During import, we use this
 *   to ignore any entries in the space map log that are for this metaslab but
 *   from a TXG before msp_unflushed_txg. At that point, we also populate its
 *   in-memory counterpart and from there both fields are updated every time
 *   we flush that metaslab.
 *
 * - A space map is created every TXG and, during that TXG, it is used to log
 *   all incoming changes (the log space map). When created, the log space map
 *   is referenced in memory by spa_syncing_log_sm and its object ID is inserted
 *   to the space map ZAP mentioned above. The log space map is closed at the
 *   end of the TXG and will be destroyed when it becomes fully obsolete. We
 *   know when a log space map has become obsolete by looking at the oldest
 *   (and smallest) ms_unflushed_txg in the pool. If the value of that is bigger
 *   than the log space map's TXG, then it means that there is no metaslab who
 *   doesn't have the changes from that log and we can therefore destroy it.
 *   [see spa_cleanup_old_sm_logs()].
 *
 * == Important in-memory structures ==
 *
 * - The per-spa field spa_metaslabs_by_flushed sorts all the metaslabs in
 *   the pool by their ms_unflushed_txg field. It is primarily used for three
 *   reasons. First of all, it is used during flushing where we try to flush
 *   metaslabs in-order from the oldest-flushed to the most recently flushed
 *   every TXG. Secondly, it helps us to lookup the ms_unflushed_txg of the
 *   oldest flushed metaslab to distinguish which log space maps have become
 *   obsolete and which ones are still relevant. Finally it tells us which
 *   metaslabs have unflushed changes in a pool where this feature was just
 *   enabled, as we don't immediately add all of the pool's metaslabs but we
 *   add them over time as they go through metaslab_sync(). The reason that
 *   we do that is to ease these pools into the behavior of the flushing
 *   algorithm (described later on).
 *
 * - The per-spa field spa_sm_logs_by_txg can be thought as the in-memory
 *   counterpart of the space map ZAP mentioned above. It's an AVL tree whose
 *   nodes represent the log space maps in the pool. This in-memory
 *   representation of log space maps in the pool sorts the log space maps by
 *   the TXG that they were created (which is also the TXG of their unflushed
 *   changes). It also contains the following extra information for each
 *   space map:
 *   [1] The number of metaslabs that were last flushed on that TXG. This is
 *       important because if that counter is zero and this is the oldest
 *       log then it means that it is also obsolete.
 *   [2] The number of blocks of that space map. This field is used by the
 *       block heuristic of our flushing algorithm (described later on).
 *       It represents how many blocks of metadata changes ZFS had to write
 *       to disk for that TXG.
 *
 * - The per-spa field spa_log_summary is a list of entries that summarizes
 *   the metaslab and block counts of all the nodes of the spa_sm_logs_by_txg
 *   AVL tree mentioned above. The reason this exists is that our flushing
 *   algorithm (described later) tries to estimate how many metaslabs to flush
 *   in each TXG by iterating over all the log space maps and looking at their
 *   block counts. Summarizing that information means that don't have to
 *   iterate through each space map, minimizing the runtime overhead of the
 *   flushing algorithm which would be induced in syncing context. In terms of
 *   implementation the log summary is used as a queue:
 *   * we modify or pop entries from its head when we flush metaslabs
 *   * we modify or append entries to its tail when we sync changes.
 *
 * - Each metaslab has two new range trees that hold its unflushed changes,
 *   ms_unflushed_allocs and ms_unflushed_frees. These are always disjoint.
 *
 * == Flushing algorithm ==
 *
 * The decision of how many metaslabs to flush on a give TXG is guided by
 * two heuristics:
 *
 * [1] The memory heuristic -
 * We keep track of the memory used by the unflushed trees from all the
 * metaslabs [see sus_memused of spa_unflushed_stats] and we ensure that it
 * stays below a certain threshold which is determined by an arbitrary hard
 * limit and an arbitrary percentage of the system's memory [see
 * spa_log_exceeds_memlimit()]. When we see that the memory usage of the
 * unflushed changes are passing that threshold, we flush metaslabs, which
 * empties their unflushed range trees, reducing the memory used.
 *
 * [2] The block heuristic -
 * We try to keep the total number of blocks in the log space maps in check
 * so the log doesn't grow indefinitely and we don't induce a lot of overhead
 * when loading the pool. At the same time we don't want to flush a lot of
 * metaslabs too often as this would defeat the purpose of the log space map.
 * As a result we set a limit in the amount of blocks that we think it's
 * acceptable for the log space maps to have and try not to cross it.
 * [see sus_blocklimit from spa_unflushed_stats].
 *
 * In order to stay below the block limit every TXG we have to estimate how
 * many metaslabs we need to flush based on the current rate of incoming blocks
 * and our history of log space map blocks. The main idea here is to answer
 * the question of how many metaslabs do we need to flush in order to get rid
 * at least an X amount of log space map blocks. We can answer this question
 * by iterating backwards from the oldest log space map to the newest one
 * and looking at their metaslab and block counts. At this point the log summary
 * mentioned above comes handy as it reduces the amount of things that we have
 * to iterate (even though it may reduce the preciseness of our estimates due
 * to its aggregation of data). So with that in mind, we project the incoming
 * rate of the current TXG into the future and attempt to approximate how many
 * metaslabs would we need to flush from now in order to avoid exceeding our
 * block limit in different points in the future (granted that we would keep
 * flushing the same number of metaslabs for every TXG). Then we take the
 * maximum number from all these estimates to be on the safe side. For the
 * exact implementation details of algorithm refer to
 * spa_estimate_metaslabs_to_flush.
 */

/*
 * This is used as the block size for the space maps used for the
 * log space map feature. These space maps benefit from a bigger
 * block size as we expect to be writing a lot of data to them at
 * once.
 */
unsigned long zfs_log_sm_blksz = 1ULL << 17;

/*
 * Percentage of the overall system's memory that ZFS allows to be
 * used for unflushed changes (e.g. the sum of size of all the nodes
 * in the unflushed trees).
 *
 * Note that this value is calculated over 1000000 for finer granularity
 * (thus the _ppm suffix; reads as "parts per million"). As an example,
 * the default of 1000 allows 0.1% of memory to be used.
 */
unsigned long zfs_unflushed_max_mem_ppm = 1000;

/*
 * Specific hard-limit in memory that ZFS allows to be used for
 * unflushed changes.
 */
unsigned long zfs_unflushed_max_mem_amt = 1ULL << 30;

/*
 * The following tunable determines the number of blocks that can be used for
 * the log space maps. It is expressed as a percentage of the total number of
 * metaslabs in the pool (i.e. the default of 400 means that the number of log
 * blocks is capped at 4 times the number of metaslabs).
 *
 * This value exists to tune our flushing algorithm, with higher values
 * flushing metaslabs less often (doing less I/Os) per TXG versus lower values
 * flushing metaslabs more aggressively with the upside of saving overheads
 * when loading the pool. Another factor in this tradeoff is that flushing
 * less often can potentially lead to better utilization of the metaslab space
 * map's block size as we accumulate more changes per flush.
 *
 * Given that this tunable indirectly controls the flush rate (metaslabs
 * flushed per txg) and that's why making it a percentage in terms of the
 * number of metaslabs in the pool makes sense here.
 *
 * As a rule of thumb we default this tunable to 400% based on the following:
 *
 * 1] Assuming a constant flush rate and a constant incoming rate of log blocks
 *    it is reasonable to expect that the amount of obsolete entries changes
 *    linearly from txg to txg (e.g. the oldest log should have the most
 *    obsolete entries, and the most recent one the least). With this we could
 *    say that, at any given time, about half of the entries in the whole space
 *    map log are obsolete. Thus for every two entries for a metaslab in the
 *    log space map, only one of them is valid and actually makes it to the
 *    metaslab's space map.
 *    [factor of 2]
 * 2] Each entry in the log space map is guaranteed to be two words while
 *    entries in metaslab space maps are generally single-word.
 *    [an extra factor of 2 - 400% overall]
 * 3] Even if [1] and [2] are slightly less than 2 each, we haven't taken into
 *    account any consolidation of segments from the log space map to the
 *    unflushed range trees nor their history (e.g. a segment being allocated,
 *    then freed, then allocated again means 3 log space map entries but 0
 *    metaslab space map entries). Depending on the workload, we've seen ~1.8
 *    non-obsolete log space map entries per metaslab entry, for a total of
 *    ~600%. Since most of these estimates though are workload dependent, we
 *    default on 400% to be conservative.
 *
 *    Thus we could say that even in the worst
 *    case of [1] and [2], the factor should end up being 4.
 *
 * That said, regardless of the number of metaslabs in the pool we need to
 * provide upper and lower bounds for the log block limit.
 * [see zfs_unflushed_log_block_{min,max}]
 */
unsigned long zfs_unflushed_log_block_pct = 400;

/*
 * If the number of metaslabs is small and our incoming rate is high, we could
 * get into a situation that we are flushing all our metaslabs every TXG. Thus
 * we always allow at least this many log blocks.
 */
unsigned long zfs_unflushed_log_block_min = 1000;

/*
 * If the log becomes too big, the import time of the pool can take a hit in
 * terms of performance. Thus we have a hard limit in the size of the log in
 * terms of blocks.
 */
unsigned long zfs_unflushed_log_block_max = (1ULL << 18);

/*
 * Max # of rows allowed for the log_summary. The tradeoff here is accuracy and
 * stability of the flushing algorithm (longer summary) vs its runtime overhead
 * (smaller summary is faster to traverse).
 */
unsigned long zfs_max_logsm_summary_length = 10;

/*
 * Tunable that sets the lower bound on the metaslabs to flush every TXG.
 *
 * Setting this to 0 has no effect since if the pool is idle we won't even be
 * creating log space maps and therefore we won't be flushing. On the other
 * hand if the pool has any incoming workload our block heuristic will start
 * flushing metaslabs anyway.
 *
 * The point of this tunable is to be used in extreme cases where we really
 * want to flush more metaslabs than our adaptable heuristic plans to flush.
 */
unsigned long zfs_min_metaslabs_to_flush = 1;

/*
 * Tunable that specifies how far in the past do we want to look when trying to
 * estimate the incoming log blocks for the current TXG.
 *
 * Setting this too high may not only increase runtime but also minimize the
 * effect of the incoming rates from the most recent TXGs as we take the
 * average over all the blocks that we walk
 * [see spa_estimate_incoming_log_blocks].
 */
unsigned long zfs_max_log_walking = 5;

/*
 * This tunable exists solely for testing purposes. It ensures that the log
 * spacemaps are not flushed and destroyed during export in order for the
 * relevant log spacemap import code paths to be tested (effectively simulating
 * a crash).
 */
int zfs_keep_log_spacemaps_at_export = 0;

static uint64_t
spa_estimate_incoming_log_blocks(spa_t *spa)
{
	ASSERT3U(spa_sync_pass(spa), ==, 1);
	uint64_t steps = 0, sum = 0;
	for (spa_log_sm_t *sls = avl_last(&spa->spa_sm_logs_by_txg);
	    sls != NULL && steps < zfs_max_log_walking;
	    sls = AVL_PREV(&spa->spa_sm_logs_by_txg, sls)) {
		if (sls->sls_txg == spa_syncing_txg(spa)) {
			/*
			 * skip the log created in this TXG as this would
			 * make our estimations inaccurate.
			 */
			continue;
		}
		sum += sls->sls_nblocks;
		steps++;
	}
	return ((steps > 0) ? DIV_ROUND_UP(sum, steps) : 0);
}

uint64_t
spa_log_sm_blocklimit(spa_t *spa)
{
	return (spa->spa_unflushed_stats.sus_blocklimit);
}

void
spa_log_sm_set_blocklimit(spa_t *spa)
{
	if (!spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP)) {
		ASSERT0(spa_log_sm_blocklimit(spa));
		return;
	}

	uint64_t calculated_limit =
	    (spa_total_metaslabs(spa) * zfs_unflushed_log_block_pct) / 100;
	spa->spa_unflushed_stats.sus_blocklimit = MIN(MAX(calculated_limit,
	    zfs_unflushed_log_block_min), zfs_unflushed_log_block_max);
}

uint64_t
spa_log_sm_nblocks(spa_t *spa)
{
	return (spa->spa_unflushed_stats.sus_nblocks);
}

/*
 * Ensure that the in-memory log space map structures and the summary
 * have the same block and metaslab counts.
 */
static void
spa_log_summary_verify_counts(spa_t *spa)
{
	ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP));

	if ((zfs_flags & ZFS_DEBUG_LOG_SPACEMAP) == 0)
		return;

	uint64_t ms_in_avl = avl_numnodes(&spa->spa_metaslabs_by_flushed);

	uint64_t ms_in_summary = 0, blk_in_summary = 0;
	for (log_summary_entry_t *e = list_head(&spa->spa_log_summary);
	    e; e = list_next(&spa->spa_log_summary, e)) {
		ms_in_summary += e->lse_mscount;
		blk_in_summary += e->lse_blkcount;
	}

	uint64_t ms_in_logs = 0, blk_in_logs = 0;
	for (spa_log_sm_t *sls = avl_first(&spa->spa_sm_logs_by_txg);
	    sls; sls = AVL_NEXT(&spa->spa_sm_logs_by_txg, sls)) {
		ms_in_logs += sls->sls_mscount;
		blk_in_logs += sls->sls_nblocks;
	}

	VERIFY3U(ms_in_logs, ==, ms_in_summary);
	VERIFY3U(ms_in_logs, ==, ms_in_avl);
	VERIFY3U(blk_in_logs, ==, blk_in_summary);
	VERIFY3U(blk_in_logs, ==, spa_log_sm_nblocks(spa));
}

static boolean_t
summary_entry_is_full(spa_t *spa, log_summary_entry_t *e)
{
	uint64_t blocks_per_row = MAX(1,
	    DIV_ROUND_UP(spa_log_sm_blocklimit(spa),
	    zfs_max_logsm_summary_length));
	return (blocks_per_row <= e->lse_blkcount);
}

/*
 * Update the log summary information to reflect the fact that a metaslab
 * was flushed or destroyed (e.g due to device removal or pool export/destroy).
 *
 * We typically flush the oldest flushed metaslab so the first (and oldest)
 * entry of the summary is updated. However if that metaslab is getting loaded
 * we may flush the second oldest one which may be part of an entry later in
 * the summary. Moreover, if we call into this function from metaslab_fini()
 * the metaslabs probably won't be ordered by ms_unflushed_txg. Thus we ask
 * for a txg as an argument so we can locate the appropriate summary entry for
 * the metaslab.
 */
void
spa_log_summary_decrement_mscount(spa_t *spa, uint64_t txg)
{
	/*
	 * We don't track summary data for read-only pools and this function
	 * can be called from metaslab_fini(). In that case return immediately.
	 */
	if (!spa_writeable(spa))
		return;

	log_summary_entry_t *target = NULL;
	for (log_summary_entry_t *e = list_head(&spa->spa_log_summary);
	    e != NULL; e = list_next(&spa->spa_log_summary, e)) {
		if (e->lse_start > txg)
			break;
		target = e;
	}

	if (target == NULL || target->lse_mscount == 0) {
		/*
		 * We didn't find a summary entry for this metaslab. We must be
		 * at the teardown of a spa_load() attempt that got an error
		 * while reading the log space maps.
		 */
		VERIFY3S(spa_load_state(spa), ==, SPA_LOAD_ERROR);
		return;
	}

	target->lse_mscount--;
}

/*
 * Update the log summary information to reflect the fact that we destroyed
 * old log space maps. Since we can only destroy the oldest log space maps,
 * we decrement the block count of the oldest summary entry and potentially
 * destroy it when that count hits 0.
 *
 * This function is called after a metaslab is flushed and typically that
 * metaslab is the oldest flushed, which means that this function will
 * typically decrement the block count of the first entry of the summary and
 * potentially free it if the block count gets to zero (its metaslab count
 * should be zero too at that point).
 *
 * There are certain scenarios though that don't work exactly like that so we
 * need to account for them:
 *
 * Scenario [1]: It is possible that after we flushed the oldest flushed
 * metaslab and we destroyed the oldest log space map, more recent logs had 0
 * metaslabs pointing to them so we got rid of them too. This can happen due
 * to metaslabs being destroyed through device removal, or because the oldest
 * flushed metaslab was loading but we kept flushing more recently flushed
 * metaslabs due to the memory pressure of unflushed changes. Because of that,
 * we always iterate from the beginning of the summary and if blocks_gone is
 * bigger than the block_count of the current entry we free that entry (we
 * expect its metaslab count to be zero), we decrement blocks_gone and on to
 * the next entry repeating this procedure until blocks_gone gets decremented
 * to 0. Doing this also works for the typical case mentioned above.
 *
 * Scenario [2]: The oldest flushed metaslab isn't necessarily accounted by
 * the first (and oldest) entry in the summary. If the first few entries of
 * the summary were only accounting metaslabs from a device that was just
 * removed, then the current oldest flushed metaslab could be accounted by an
 * entry somewhere in the middle of the summary. Moreover flushing that
 * metaslab will destroy all the log space maps older than its ms_unflushed_txg
 * because they became obsolete after the removal. Thus, iterating as we did
 * for scenario [1] works out for this case too.
 *
 * Scenario [3]: At times we decide to flush all the metaslabs in the pool
 * in one TXG (either because we are exporting the pool or because our flushing
 * heuristics decided to do so). When that happens all the log space maps get
 * destroyed except the one created for the current TXG which doesn't have
 * any log blocks yet. As log space maps get destroyed with every metaslab that
 * we flush, entries in the summary are also destroyed. This brings a weird
 * corner-case when we flush the last metaslab and the log space map of the
 * current TXG is in the same summary entry with other log space maps that
 * are older. When that happens we are eventually left with this one last
 * summary entry whose blocks are gone (blocks_gone equals the entry's block
 * count) but its metaslab count is non-zero (because it accounts all the
 * metaslabs in the pool as they all got flushed). Under this scenario we can't
 * free this last summary entry as it's referencing all the metaslabs in the
 * pool and its block count will get incremented at the end of this sync (when
 * we close the syncing log space map). Thus we just decrement its current
 * block count and leave it alone. In the case that the pool gets exported,
 * its metaslab count will be decremented over time as we call metaslab_fini()
 * for all the metaslabs in the pool and the entry will be freed at
 * spa_unload_log_sm_metadata().
 */
void
spa_log_summary_decrement_blkcount(spa_t *spa, uint64_t blocks_gone)
{
	for (log_summary_entry_t *e = list_head(&spa->spa_log_summary);
	    e != NULL; e = list_head(&spa->spa_log_summary)) {
		if (e->lse_blkcount > blocks_gone) {
			/*
			 * Assert that we stopped at an entry that is not
			 * obsolete.
			 */
			ASSERT(e->lse_mscount != 0);

			e->lse_blkcount -= blocks_gone;
			blocks_gone = 0;
			break;
		} else if (e->lse_mscount == 0) {
			/* remove obsolete entry */
			blocks_gone -= e->lse_blkcount;
			list_remove(&spa->spa_log_summary, e);
			kmem_free(e, sizeof (log_summary_entry_t));
		} else {
			/* Verify that this is scenario [3] mentioned above. */
			VERIFY3U(blocks_gone, ==, e->lse_blkcount);

			/*
			 * Assert that this is scenario [3] further by ensuring
			 * that this is the only entry in the summary.
			 */
			VERIFY3P(e, ==, list_tail(&spa->spa_log_summary));
			ASSERT3P(e, ==, list_head(&spa->spa_log_summary));

			blocks_gone = e->lse_blkcount = 0;
			break;
		}
	}

	/*
	 * Ensure that there is no way we are trying to remove more blocks
	 * than the # of blocks in the summary.
	 */
	ASSERT0(blocks_gone);
}

void
spa_log_sm_decrement_mscount(spa_t *spa, uint64_t txg)
{
	spa_log_sm_t target = { .sls_txg = txg };
	spa_log_sm_t *sls = avl_find(&spa->spa_sm_logs_by_txg,
	    &target, NULL);

	if (sls == NULL) {
		/*
		 * We must be at the teardown of a spa_load() attempt that
		 * got an error while reading the log space maps.
		 */
		VERIFY3S(spa_load_state(spa), ==, SPA_LOAD_ERROR);
		return;
	}

	ASSERT(sls->sls_mscount > 0);
	sls->sls_mscount--;
}

void
spa_log_sm_increment_current_mscount(spa_t *spa)
{
	spa_log_sm_t *last_sls = avl_last(&spa->spa_sm_logs_by_txg);
	ASSERT3U(last_sls->sls_txg, ==, spa_syncing_txg(spa));
	last_sls->sls_mscount++;
}

static void
summary_add_data(spa_t *spa, uint64_t txg, uint64_t metaslabs_flushed,
    uint64_t nblocks)
{
	log_summary_entry_t *e = list_tail(&spa->spa_log_summary);

	if (e == NULL || summary_entry_is_full(spa, e)) {
		e = kmem_zalloc(sizeof (log_summary_entry_t), KM_SLEEP);
		e->lse_start = txg;
		list_insert_tail(&spa->spa_log_summary, e);
	}

	ASSERT3U(e->lse_start, <=, txg);
	e->lse_mscount += metaslabs_flushed;
	e->lse_blkcount += nblocks;
}

static void
spa_log_summary_add_incoming_blocks(spa_t *spa, uint64_t nblocks)
{
	summary_add_data(spa, spa_syncing_txg(spa), 0, nblocks);
}

void
spa_log_summary_add_flushed_metaslab(spa_t *spa)
{
	summary_add_data(spa, spa_syncing_txg(spa), 1, 0);
}

/*
 * This function attempts to estimate how many metaslabs should
 * we flush to satisfy our block heuristic for the log spacemap
 * for the upcoming TXGs.
 *
 * Specifically, it first tries to estimate the number of incoming
 * blocks in this TXG. Then by projecting that incoming rate to
 * future TXGs and using the log summary, it figures out how many
 * flushes we would need to do for future TXGs individually to
 * stay below our block limit and returns the maximum number of
 * flushes from those estimates.
 */
static uint64_t
spa_estimate_metaslabs_to_flush(spa_t *spa)
{
	ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP));
	ASSERT3U(spa_sync_pass(spa), ==, 1);
	ASSERT(spa_log_sm_blocklimit(spa) != 0);

	/*
	 * This variable contains the incoming rate that will be projected
	 * and used for our flushing estimates in the future.
	 */
	uint64_t incoming = spa_estimate_incoming_log_blocks(spa);

	/*
	 * At any point in time this variable tells us how many
	 * TXGs in the future we are so we can make our estimations.
	 */
	uint64_t txgs_in_future = 1;

	/*
	 * This variable tells us how much room do we have until we hit
	 * our limit. When it goes negative, it means that we've exceeded
	 * our limit and we need to flush.
	 *
	 * Note that since we start at the first TXG in the future (i.e.
	 * txgs_in_future starts from 1) we already decrement this
	 * variable by the incoming rate.
	 */
	int64_t available_blocks =
	    spa_log_sm_blocklimit(spa) - spa_log_sm_nblocks(spa) - incoming;

	/*
	 * This variable tells us the total number of flushes needed to
	 * keep the log size within the limit when we reach txgs_in_future.
	 */
	uint64_t total_flushes = 0;

	/* Holds the current maximum of our estimates so far. */
	uint64_t max_flushes_pertxg =
	    MIN(avl_numnodes(&spa->spa_metaslabs_by_flushed),
	    zfs_min_metaslabs_to_flush);

	/*
	 * For our estimations we only look as far in the future
	 * as the summary allows us.
	 */
	for (log_summary_entry_t *e = list_head(&spa->spa_log_summary);
	    e; e = list_next(&spa->spa_log_summary, e)) {

		/*
		 * If there is still room before we exceed our limit
		 * then keep skipping TXGs accumulating more blocks
		 * based on the incoming rate until we exceed it.
		 */
		if (available_blocks >= 0) {
			uint64_t skip_txgs = (available_blocks / incoming) + 1;
			available_blocks -= (skip_txgs * incoming);
			txgs_in_future += skip_txgs;
			ASSERT3S(available_blocks, >=, -incoming);
		}

		/*
		 * At this point we're far enough into the future where
		 * the limit was just exceeded and we flush metaslabs
		 * based on the current entry in the summary, updating
		 * our available_blocks.
		 */
		ASSERT3S(available_blocks, <, 0);
		available_blocks += e->lse_blkcount;
		total_flushes += e->lse_mscount;

		/*
		 * Keep the running maximum of the total_flushes that
		 * we've done so far over the number of TXGs in the
		 * future that we are. The idea here is to estimate
		 * the average number of flushes that we should do
		 * every TXG so that when we are that many TXGs in the
		 * future we stay under the limit.
		 */
		max_flushes_pertxg = MAX(max_flushes_pertxg,
		    DIV_ROUND_UP(total_flushes, txgs_in_future));
		ASSERT3U(avl_numnodes(&spa->spa_metaslabs_by_flushed), >=,
		    max_flushes_pertxg);
	}
	return (max_flushes_pertxg);
}

uint64_t
spa_log_sm_memused(spa_t *spa)
{
	return (spa->spa_unflushed_stats.sus_memused);
}

static boolean_t
spa_log_exceeds_memlimit(spa_t *spa)
{
	if (spa_log_sm_memused(spa) > zfs_unflushed_max_mem_amt)
		return (B_TRUE);

	uint64_t system_mem_allowed = ((physmem * PAGESIZE) *
	    zfs_unflushed_max_mem_ppm) / 1000000;
	if (spa_log_sm_memused(spa) > system_mem_allowed)
		return (B_TRUE);

	return (B_FALSE);
}

boolean_t
spa_flush_all_logs_requested(spa_t *spa)
{
	return (spa->spa_log_flushall_txg != 0);
}

void
spa_flush_metaslabs(spa_t *spa, dmu_tx_t *tx)
{
	uint64_t txg = dmu_tx_get_txg(tx);

	if (spa_sync_pass(spa) != 1)
		return;

	if (!spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP))
		return;

	/*
	 * If we don't have any metaslabs with unflushed changes
	 * return immediately.
	 */
	if (avl_numnodes(&spa->spa_metaslabs_by_flushed) == 0)
		return;

	/*
	 * During SPA export we leave a few empty TXGs to go by [see
	 * spa_final_dirty_txg() to understand why]. For this specific
	 * case, it is important to not flush any metaslabs as that
	 * would dirty this TXG.
	 *
	 * That said, during one of these dirty TXGs that is less or
	 * equal to spa_final_dirty(), spa_unload() will request that
	 * we try to flush all the metaslabs for that TXG before
	 * exporting the pool, thus we ensure that we didn't get a
	 * request of flushing everything before we attempt to return
	 * immediately.
	 */
	if (spa->spa_uberblock.ub_rootbp.blk_birth < txg &&
	    !dmu_objset_is_dirty(spa_meta_objset(spa), txg) &&
	    !spa_flush_all_logs_requested(spa))
		return;

	/*
	 * We need to generate a log space map before flushing because this
	 * will set up the in-memory data (i.e. node in spa_sm_logs_by_txg)
	 * for this TXG's flushed metaslab count (aka sls_mscount which is
	 * manipulated in many ways down the metaslab_flush() codepath).
	 *
	 * That is not to say that we may generate a log space map when we
	 * don't need it. If we are flushing metaslabs, that means that we
	 * were going to write changes to disk anyway, so even if we were
	 * not flushing, a log space map would have been created anyway in
	 * metaslab_sync().
	 */
	spa_generate_syncing_log_sm(spa, tx);

	/*
	 * This variable tells us how many metaslabs we want to flush based
	 * on the block-heuristic of our flushing algorithm (see block comment
	 * of log space map feature). We also decrement this as we flush
	 * metaslabs and attempt to destroy old log space maps.
	 */
	uint64_t want_to_flush;
	if (spa_flush_all_logs_requested(spa)) {
		ASSERT3S(spa_state(spa), ==, POOL_STATE_EXPORTED);
		want_to_flush = avl_numnodes(&spa->spa_metaslabs_by_flushed);
	} else {
		want_to_flush = spa_estimate_metaslabs_to_flush(spa);
	}

	ASSERT3U(avl_numnodes(&spa->spa_metaslabs_by_flushed), >=,
	    want_to_flush);

	/* Used purely for verification purposes */
	uint64_t visited = 0;

	/*
	 * Ideally we would only iterate through spa_metaslabs_by_flushed
	 * using only one variable (curr). We can't do that because
	 * metaslab_flush() mutates position of curr in the AVL when
	 * it flushes that metaslab by moving it to the end of the tree.
	 * Thus we always keep track of the original next node of the
	 * current node (curr) in another variable (next).
	 */
	metaslab_t *next = NULL;
	for (metaslab_t *curr = avl_first(&spa->spa_metaslabs_by_flushed);
	    curr != NULL; curr = next) {
		next = AVL_NEXT(&spa->spa_metaslabs_by_flushed, curr);

		/*
		 * If this metaslab has been flushed this txg then we've done
		 * a full circle over the metaslabs.
		 */
		if (metaslab_unflushed_txg(curr) == txg)
			break;

		/*
		 * If we are done flushing for the block heuristic and the
		 * unflushed changes don't exceed the memory limit just stop.
		 */
		if (want_to_flush == 0 && !spa_log_exceeds_memlimit(spa))
			break;

		mutex_enter(&curr->ms_sync_lock);
		mutex_enter(&curr->ms_lock);
		boolean_t flushed = metaslab_flush(curr, tx);
		mutex_exit(&curr->ms_lock);
		mutex_exit(&curr->ms_sync_lock);

		/*
		 * If we failed to flush a metaslab (because it was loading),
		 * then we are done with the block heuristic as it's not
		 * possible to destroy any log space maps once you've skipped
		 * a metaslab. In that case we just set our counter to 0 but
		 * we continue looping in case there is still memory pressure
		 * due to unflushed changes. Note that, flushing a metaslab
		 * that is not the oldest flushed in the pool, will never
		 * destroy any log space maps [see spa_cleanup_old_sm_logs()].
		 */
		if (!flushed) {
			want_to_flush = 0;
		} else if (want_to_flush > 0) {
			want_to_flush--;
		}

		visited++;
	}
	ASSERT3U(avl_numnodes(&spa->spa_metaslabs_by_flushed), >=, visited);
}

/*
 * Close the log space map for this TXG and update the block counts
 * for the log's in-memory structure and the summary.
 */
void
spa_sync_close_syncing_log_sm(spa_t *spa)
{
	if (spa_syncing_log_sm(spa) == NULL)
		return;
	ASSERT(spa_feature_is_active(spa, SPA_FEATURE_LOG_SPACEMAP));

	spa_log_sm_t *sls = avl_last(&spa->spa_sm_logs_by_txg);
	ASSERT3U(sls->sls_txg, ==, spa_syncing_txg(spa));

	sls->sls_nblocks = space_map_nblocks(spa_syncing_log_sm(spa));
	spa->spa_unflushed_stats.sus_nblocks += sls->sls_nblocks;

	/*
	 * Note that we can't assert that sls_mscount is not 0,
	 * because there is the case where the first metaslab
	 * in spa_metaslabs_by_flushed is loading and we were
	 * not able to flush any metaslabs the current TXG.
	 */
	ASSERT(sls->sls_nblocks != 0);

	spa_log_summary_add_incoming_blocks(spa, sls->sls_nblocks);
	spa_log_summary_verify_counts(spa);

	space_map_close(spa->spa_syncing_log_sm);
	spa->spa_syncing_log_sm = NULL;

	/*
	 * At this point we tried to flush as many metaslabs as we
	 * can as the pool is getting exported. Reset the "flush all"
	 * so the last few TXGs before closing the pool can be empty
	 * (e.g. not dirty).
	 */
	if (spa_flush_all_logs_requested(spa)) {
		ASSERT3S(spa_state(spa), ==, POOL_STATE_EXPORTED);
		spa->spa_log_flushall_txg = 0;
	}
}

void
spa_cleanup_old_sm_logs(spa_t *spa, dmu_tx_t *tx)
{
	objset_t *mos = spa_meta_objset(spa);

	uint64_t spacemap_zap;
	int error = zap_lookup(mos, DMU_POOL_DIRECTORY_OBJECT,
	    DMU_POOL_LOG_SPACEMAP_ZAP, sizeof (spacemap_zap), 1, &spacemap_zap);
	if (error == ENOENT) {
		ASSERT(avl_is_empty(&spa->spa_sm_logs_by_txg));
		return;
	}
	VERIFY0(error);

	metaslab_t *oldest = avl_first(&spa->spa_metaslabs_by_flushed);
	uint64_t oldest_flushed_txg = metaslab_unflushed_txg(oldest);

	/* Free all log space maps older than the oldest_flushed_txg. */
	for (spa_log_sm_t *sls = avl_first(&spa->spa_sm_logs_by_txg);
	    sls && sls->sls_txg < oldest_flushed_txg;
	    sls = avl_first(&spa->spa_sm_logs_by_txg)) {
		ASSERT0(sls->sls_mscount);
		avl_remove(&spa->spa_sm_logs_by_txg, sls);
		space_map_free_obj(mos, sls->sls_sm_obj, tx);
		VERIFY0(zap_remove_int(mos, spacemap_zap, sls->sls_txg, tx));
		spa->spa_unflushed_stats.sus_nblocks -= sls->sls_nblocks;
		kmem_free(sls, sizeof (spa_log_sm_t));
	}
}

static spa_log_sm_t *
spa_log_sm_alloc(uint64_t sm_obj, uint64_t txg)
{
	spa_log_sm_t *sls = kmem_zalloc(sizeof (*sls), KM_SLEEP);
	sls->sls_sm_obj = sm_obj;
	sls->sls_txg = txg;
	return (sls);
}

void
spa_generate_syncing_log_sm(spa_t *spa, dmu_tx_t *tx)
{
	uint64_t txg = dmu_tx_get_txg(tx);
	objset_t *mos = spa_meta_objset(spa);

	if (spa_syncing_log_sm(spa) != NULL)
		return;

	if (!spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP))
		return;

	uint64_t spacemap_zap;
	int error = zap_lookup(mos, DMU_POOL_DIRECTORY_OBJECT,
	    DMU_POOL_LOG_SPACEMAP_ZAP, sizeof (spacemap_zap), 1, &spacemap_zap);
	if (error == ENOENT) {
		ASSERT(avl_is_empty(&spa->spa_sm_logs_by_txg));

		error = 0;
		spacemap_zap = zap_create(mos,
		    DMU_OTN_ZAP_METADATA, DMU_OT_NONE, 0, tx);
		VERIFY0(zap_add(mos, DMU_POOL_DIRECTORY_OBJECT,
		    DMU_POOL_LOG_SPACEMAP_ZAP, sizeof (spacemap_zap), 1,
		    &spacemap_zap, tx));
		spa_feature_incr(spa, SPA_FEATURE_LOG_SPACEMAP, tx);
	}
	VERIFY0(error);

	uint64_t sm_obj;
	ASSERT3U(zap_lookup_int_key(mos, spacemap_zap, txg, &sm_obj),
	    ==, ENOENT);
	sm_obj = space_map_alloc(mos, zfs_log_sm_blksz, tx);
	VERIFY0(zap_add_int_key(mos, spacemap_zap, txg, sm_obj, tx));
	avl_add(&spa->spa_sm_logs_by_txg, spa_log_sm_alloc(sm_obj, txg));

	/*
	 * We pass UINT64_MAX as the space map's representation size
	 * and SPA_MINBLOCKSHIFT as the shift, to make the space map
	 * accept any sorts of segments since there's no real advantage
	 * to being more restrictive (given that we're already going
	 * to be using 2-word entries).
	 */
	VERIFY0(space_map_open(&spa->spa_syncing_log_sm, mos, sm_obj,
	    0, UINT64_MAX, SPA_MINBLOCKSHIFT));

	/*
	 * If the log space map feature was just enabled, the blocklimit
	 * has not yet been set.
	 */
	if (spa_log_sm_blocklimit(spa) == 0)
		spa_log_sm_set_blocklimit(spa);
}

/*
 * Find all the log space maps stored in the space map ZAP and sort
 * them by their TXG in spa_sm_logs_by_txg.
 */
static int
spa_ld_log_sm_metadata(spa_t *spa)
{
	int error;
	uint64_t spacemap_zap;

	ASSERT(avl_is_empty(&spa->spa_sm_logs_by_txg));

	error = zap_lookup(spa_meta_objset(spa), DMU_POOL_DIRECTORY_OBJECT,
	    DMU_POOL_LOG_SPACEMAP_ZAP, sizeof (spacemap_zap), 1, &spacemap_zap);
	if (error == ENOENT) {
		/* the space map ZAP doesn't exist yet */
		return (0);
	} else if (error != 0) {
		spa_load_failed(spa, "spa_ld_log_sm_metadata(): failed at "
		    "zap_lookup(DMU_POOL_DIRECTORY_OBJECT) [error %d]",
		    error);
		return (error);
	}

	zap_cursor_t zc;
	zap_attribute_t za;
	for (zap_cursor_init(&zc, spa_meta_objset(spa), spacemap_zap);
	    (error = zap_cursor_retrieve(&zc, &za)) == 0;
	    zap_cursor_advance(&zc)) {
		uint64_t log_txg = zfs_strtonum(za.za_name, NULL);
		spa_log_sm_t *sls =
		    spa_log_sm_alloc(za.za_first_integer, log_txg);
		avl_add(&spa->spa_sm_logs_by_txg, sls);
	}
	zap_cursor_fini(&zc);
	if (error != ENOENT) {
		spa_load_failed(spa, "spa_ld_log_sm_metadata(): failed at "
		    "zap_cursor_retrieve(spacemap_zap) [error %d]",
		    error);
		return (error);
	}

	for (metaslab_t *m = avl_first(&spa->spa_metaslabs_by_flushed);
	    m; m = AVL_NEXT(&spa->spa_metaslabs_by_flushed, m)) {
		spa_log_sm_t target = { .sls_txg = metaslab_unflushed_txg(m) };
		spa_log_sm_t *sls = avl_find(&spa->spa_sm_logs_by_txg,
		    &target, NULL);

		/*
		 * At this point if sls is zero it means that a bug occurred
		 * in ZFS the last time the pool was open or earlier in the
		 * import code path. In general, we would have placed a
		 * VERIFY() here or in this case just let the kernel panic
		 * with NULL pointer dereference when incrementing sls_mscount,
		 * but since this is the import code path we can be a bit more
		 * lenient. Thus, for DEBUG bits we always cause a panic, while
		 * in production we log the error and just fail the import.
		 */
		ASSERT(sls != NULL);
		if (sls == NULL) {
			spa_load_failed(spa, "spa_ld_log_sm_metadata(): bug "
			    "encountered: could not find log spacemap for "
			    "TXG %ld [error %d]",
			    metaslab_unflushed_txg(m), ENOENT);
			return (ENOENT);
		}
		sls->sls_mscount++;
	}

	return (0);
}

typedef struct spa_ld_log_sm_arg {
	spa_t *slls_spa;
	uint64_t slls_txg;
} spa_ld_log_sm_arg_t;

static int
spa_ld_log_sm_cb(space_map_entry_t *sme, void *arg)
{
	uint64_t offset = sme->sme_offset;
	uint64_t size = sme->sme_run;
	uint32_t vdev_id = sme->sme_vdev;

	spa_ld_log_sm_arg_t *slls = arg;
	spa_t *spa = slls->slls_spa;

	vdev_t *vd = vdev_lookup_top(spa, vdev_id);

	/*
	 * If the vdev has been removed (i.e. it is indirect or a hole)
	 * skip this entry. The contents of this vdev have already moved
	 * elsewhere.
	 */
	if (!vdev_is_concrete(vd))
		return (0);

	metaslab_t *ms = vd->vdev_ms[offset >> vd->vdev_ms_shift];
	ASSERT(!ms->ms_loaded);

	/*
	 * If we have already flushed entries for this TXG to this
	 * metaslab's space map, then ignore it. Note that we flush
	 * before processing any allocations/frees for that TXG, so
	 * the metaslab's space map only has entries from *before*
	 * the unflushed TXG.
	 */
	if (slls->slls_txg < metaslab_unflushed_txg(ms))
		return (0);

	switch (sme->sme_type) {
	case SM_ALLOC:
		range_tree_remove_xor_add_segment(offset, offset + size,
		    ms->ms_unflushed_frees, ms->ms_unflushed_allocs);
		break;
	case SM_FREE:
		range_tree_remove_xor_add_segment(offset, offset + size,
		    ms->ms_unflushed_allocs, ms->ms_unflushed_frees);
		break;
	default:
		panic("invalid maptype_t");
		break;
	}
	return (0);
}

static int
spa_ld_log_sm_data(spa_t *spa)
{
	int error = 0;

	/*
	 * If we are not going to do any writes there is no need
	 * to read the log space maps.
	 */
	if (!spa_writeable(spa))
		return (0);

	ASSERT0(spa->spa_unflushed_stats.sus_nblocks);
	ASSERT0(spa->spa_unflushed_stats.sus_memused);

	hrtime_t read_logs_starttime = gethrtime();
	/* this is a no-op when we don't have space map logs */
	for (spa_log_sm_t *sls = avl_first(&spa->spa_sm_logs_by_txg);
	    sls; sls = AVL_NEXT(&spa->spa_sm_logs_by_txg, sls)) {
		space_map_t *sm = NULL;
		error = space_map_open(&sm, spa_meta_objset(spa),
		    sls->sls_sm_obj, 0, UINT64_MAX, SPA_MINBLOCKSHIFT);
		if (error != 0) {
			spa_load_failed(spa, "spa_ld_log_sm_data(): failed at "
			    "space_map_open(obj=%llu) [error %d]",
			    (u_longlong_t)sls->sls_sm_obj, error);
			goto out;
		}

		struct spa_ld_log_sm_arg vla = {
			.slls_spa = spa,
			.slls_txg = sls->sls_txg
		};
		error = space_map_iterate(sm, space_map_length(sm),
		    spa_ld_log_sm_cb, &vla);
		if (error != 0) {
			space_map_close(sm);
			spa_load_failed(spa, "spa_ld_log_sm_data(): failed "
			    "at space_map_iterate(obj=%llu) [error %d]",
			    (u_longlong_t)sls->sls_sm_obj, error);
			goto out;
		}

		ASSERT0(sls->sls_nblocks);
		sls->sls_nblocks = space_map_nblocks(sm);
		spa->spa_unflushed_stats.sus_nblocks += sls->sls_nblocks;
		summary_add_data(spa, sls->sls_txg,
		    sls->sls_mscount, sls->sls_nblocks);

		space_map_close(sm);
	}
	hrtime_t read_logs_endtime = gethrtime();
	spa_load_note(spa,
	    "read %llu log space maps (%llu total blocks - blksz = %llu bytes) "
	    "in %lld ms", (u_longlong_t)avl_numnodes(&spa->spa_sm_logs_by_txg),
	    (u_longlong_t)spa_log_sm_nblocks(spa),
	    (u_longlong_t)zfs_log_sm_blksz,
	    (longlong_t)((read_logs_endtime - read_logs_starttime) / 1000000));

out:
	/*
	 * Now that the metaslabs contain their unflushed changes:
	 * [1] recalculate their actual allocated space
	 * [2] recalculate their weights
	 * [3] sum up the memory usage of their unflushed range trees
	 * [4] optionally load them, if debug_load is set
	 *
	 * Note that even in the case where we get here because of an
	 * error (e.g. error != 0), we still want to update the fields
	 * below in order to have a proper teardown in spa_unload().
	 */
	for (metaslab_t *m = avl_first(&spa->spa_metaslabs_by_flushed);
	    m != NULL; m = AVL_NEXT(&spa->spa_metaslabs_by_flushed, m)) {
		mutex_enter(&m->ms_lock);
		m->ms_allocated_space = space_map_allocated(m->ms_sm) +
		    range_tree_space(m->ms_unflushed_allocs) -
		    range_tree_space(m->ms_unflushed_frees);

		vdev_t *vd = m->ms_group->mg_vd;
		metaslab_space_update(vd, m->ms_group->mg_class,
		    range_tree_space(m->ms_unflushed_allocs), 0, 0);
		metaslab_space_update(vd, m->ms_group->mg_class,
		    -range_tree_space(m->ms_unflushed_frees), 0, 0);

		ASSERT0(m->ms_weight & METASLAB_ACTIVE_MASK);
		metaslab_recalculate_weight_and_sort(m);

		spa->spa_unflushed_stats.sus_memused +=
		    metaslab_unflushed_changes_memused(m);

		if (metaslab_debug_load && m->ms_sm != NULL) {
			VERIFY0(metaslab_load(m));
			metaslab_set_selected_txg(m, 0);
		}
		mutex_exit(&m->ms_lock);
	}

	return (error);
}

static int
spa_ld_unflushed_txgs(vdev_t *vd)
{
	spa_t *spa = vd->vdev_spa;
	objset_t *mos = spa_meta_objset(spa);

	if (vd->vdev_top_zap == 0)
		return (0);

	uint64_t object = 0;
	int error = zap_lookup(mos, vd->vdev_top_zap,
	    VDEV_TOP_ZAP_MS_UNFLUSHED_PHYS_TXGS,
	    sizeof (uint64_t), 1, &object);
	if (error == ENOENT)
		return (0);
	else if (error != 0) {
		spa_load_failed(spa, "spa_ld_unflushed_txgs(): failed at "
		    "zap_lookup(vdev_top_zap=%llu) [error %d]",
		    (u_longlong_t)vd->vdev_top_zap, error);
		return (error);
	}

	for (uint64_t m = 0; m < vd->vdev_ms_count; m++) {
		metaslab_t *ms = vd->vdev_ms[m];
		ASSERT(ms != NULL);

		metaslab_unflushed_phys_t entry;
		uint64_t entry_size = sizeof (entry);
		uint64_t entry_offset = ms->ms_id * entry_size;

		error = dmu_read(mos, object,
		    entry_offset, entry_size, &entry, 0);
		if (error != 0) {
			spa_load_failed(spa, "spa_ld_unflushed_txgs(): "
			    "failed at dmu_read(obj=%llu) [error %d]",
			    (u_longlong_t)object, error);
			return (error);
		}

		ms->ms_unflushed_txg = entry.msp_unflushed_txg;
		if (ms->ms_unflushed_txg != 0) {
			mutex_enter(&spa->spa_flushed_ms_lock);
			avl_add(&spa->spa_metaslabs_by_flushed, ms);
			mutex_exit(&spa->spa_flushed_ms_lock);
		}
	}
	return (0);
}

/*
 * Read all the log space map entries into their respective
 * metaslab unflushed trees and keep them sorted by TXG in the
 * SPA's metadata. In addition, setup all the metadata for the
 * memory and the block heuristics.
 */
int
spa_ld_log_spacemaps(spa_t *spa)
{
	int error;

	spa_log_sm_set_blocklimit(spa);

	for (uint64_t c = 0; c < spa->spa_root_vdev->vdev_children; c++) {
		vdev_t *vd = spa->spa_root_vdev->vdev_child[c];
		error = spa_ld_unflushed_txgs(vd);
		if (error != 0)
			return (error);
	}

	error = spa_ld_log_sm_metadata(spa);
	if (error != 0)
		return (error);

	/*
	 * Note: we don't actually expect anything to change at this point
	 * but we grab the config lock so we don't fail any assertions
	 * when using vdev_lookup_top().
	 */
	spa_config_enter(spa, SCL_CONFIG, FTAG, RW_READER);
	error = spa_ld_log_sm_data(spa);
	spa_config_exit(spa, SCL_CONFIG, FTAG);

	return (error);
}

/* BEGIN CSTYLED */
ZFS_MODULE_PARAM(zfs, zfs_, unflushed_max_mem_amt, ULONG, ZMOD_RW,
    "Specific hard-limit in memory that ZFS allows to be used for "
    "unflushed changes");

ZFS_MODULE_PARAM(zfs, zfs_, unflushed_max_mem_ppm, ULONG, ZMOD_RW,
    "Percentage of the overall system memory that ZFS allows to be "
    "used for unflushed changes (value is calculated over 1000000 for "
    "finer granularity)");

ZFS_MODULE_PARAM(zfs, zfs_, unflushed_log_block_max, ULONG, ZMOD_RW,
    "Hard limit (upper-bound) in the size of the space map log "
    "in terms of blocks.");

ZFS_MODULE_PARAM(zfs, zfs_, unflushed_log_block_min, ULONG, ZMOD_RW,
    "Lower-bound limit for the maximum amount of blocks allowed in "
    "log spacemap (see zfs_unflushed_log_block_max)");

ZFS_MODULE_PARAM(zfs, zfs_, unflushed_log_block_pct, ULONG, ZMOD_RW,
    "Tunable used to determine the number of blocks that can be used for "
    "the spacemap log, expressed as a percentage of the total number of "
    "metaslabs in the pool (e.g. 400 means the number of log blocks is "
    "capped at 4 times the number of metaslabs)");

ZFS_MODULE_PARAM(zfs, zfs_, max_log_walking, ULONG, ZMOD_RW,
    "The number of past TXGs that the flushing algorithm of the log "
    "spacemap feature uses to estimate incoming log blocks");

ZFS_MODULE_PARAM(zfs, zfs_, max_logsm_summary_length, ULONG, ZMOD_RW,
    "Maximum number of rows allowed in the summary of the spacemap log");

ZFS_MODULE_PARAM(zfs, zfs_, min_metaslabs_to_flush, ULONG, ZMOD_RW,
    "Minimum number of metaslabs to flush per dirty TXG");

ZFS_MODULE_PARAM(zfs, zfs_, keep_log_spacemaps_at_export, INT, ZMOD_RW,
    "Prevent the log spacemaps from being flushed and destroyed "
    "during pool export/destroy");
/* END CSTYLED */