1 // SPDX-License-Identifier: CDDL-1.0
2 /*
3 * This file and its contents are supplied under the terms of the
4 * Common Development and Distribution License ("CDDL"), version 1.0.
5 * You may only use this file in accordance with the terms of version
6 * 1.0 of the CDDL.
7 *
8 * A full copy of the text of the CDDL should have accompanied this
9 * source. A copy of the CDDL is also available via the Internet at
10 * https://opensource.org/license/CDDL-1.0.
11 */
12 /*
13 * Copyright (c) 2018 Intel Corporation.
14 * Copyright (c) 2020 by Lawrence Livermore National Security, LLC.
15 */
16
17 #include <stdio.h>
18 #include <zlib.h>
19 #include <zfs_fletcher.h>
20 #include <sys/vdev_draid.h>
21 #include <sys/nvpair.h>
22 #include <sys/stat.h>
23
24 /*
25 * The number of rows to generate for new permutation maps.
26 */
27 #define MAP_ROWS_DEFAULT 256
28
29 /*
30 * Key values for dRAID maps when stored as nvlists.
31 */
32 #define MAP_SEED "seed"
33 #define MAP_CHECKSUM "checksum"
34 #define MAP_WORST_RATIO "worst_ratio"
35 #define MAP_AVG_RATIO "avg_ratio"
36 #define MAP_CHILDREN "children"
37 #define MAP_NPERMS "nperms"
38 #define MAP_PERMS "perms"
39
40 static void
draid_usage(void)41 draid_usage(void)
42 {
43 (void) fprintf(stderr,
44 "usage: draid command args ...\n"
45 "Available commands are:\n"
46 "\n"
47 "\tdraid generate [-cv] [-m min] [-n max] [-p passes] FILE\n"
48 "\tdraid verify [-rv] FILE\n"
49 "\tdraid dump [-v] [-m min] [-n max] FILE\n"
50 "\tdraid table FILE\n"
51 "\tdraid merge FILE SRC SRC...\n");
52 exit(1);
53 }
54
55 static int
read_map(const char * filename,nvlist_t ** allcfgs)56 read_map(const char *filename, nvlist_t **allcfgs)
57 {
58 int block_size = 131072;
59 int buf_size = 131072;
60 int tmp_size, error;
61 char *tmp_buf;
62
63 struct stat64 stat;
64 if (lstat64(filename, &stat) != 0)
65 return (errno);
66
67 if (stat.st_size == 0 ||
68 !(S_ISREG(stat.st_mode) || S_ISLNK(stat.st_mode))) {
69 return (EINVAL);
70 }
71
72 gzFile fp = gzopen(filename, "rb");
73 if (fp == Z_NULL)
74 return (errno);
75
76 char *buf = malloc(buf_size);
77 if (buf == NULL) {
78 (void) gzclose(fp);
79 return (ENOMEM);
80 }
81
82 ssize_t rc, bytes = 0;
83 while (!gzeof(fp)) {
84 rc = gzread(fp, buf + bytes, block_size);
85 if ((rc < 0) || (rc == 0 && !gzeof(fp))) {
86 free(buf);
87 (void) gzerror(fp, &error);
88 (void) gzclose(fp);
89 return (error);
90 } else {
91 bytes += rc;
92
93 if (bytes + block_size >= buf_size) {
94 tmp_size = 2 * buf_size;
95 tmp_buf = malloc(tmp_size);
96 if (tmp_buf == NULL) {
97 free(buf);
98 (void) gzclose(fp);
99 return (ENOMEM);
100 }
101
102 memcpy(tmp_buf, buf, bytes);
103 free(buf);
104 buf = tmp_buf;
105 buf_size = tmp_size;
106 }
107 }
108 }
109
110 (void) gzclose(fp);
111
112 error = nvlist_unpack(buf, bytes, allcfgs, 0);
113 free(buf);
114
115 return (error);
116 }
117
118 /*
119 * Read a map from the specified filename. A file contains multiple maps
120 * which are indexed by the number of children. The caller is responsible
121 * for freeing the configuration returned.
122 */
123 static int
read_map_key(const char * filename,const char * key,nvlist_t ** cfg)124 read_map_key(const char *filename, const char *key, nvlist_t **cfg)
125 {
126 nvlist_t *allcfgs, *foundcfg = NULL;
127 int error;
128
129 error = read_map(filename, &allcfgs);
130 if (error != 0)
131 return (error);
132
133 (void) nvlist_lookup_nvlist(allcfgs, key, &foundcfg);
134 if (foundcfg != NULL) {
135 nvlist_dup(foundcfg, cfg, KM_SLEEP);
136 error = 0;
137 } else {
138 error = ENOENT;
139 }
140
141 nvlist_free(allcfgs);
142
143 return (error);
144 }
145
146 /*
147 * Write all mappings to the map file.
148 */
149 static int
write_map(const char * filename,nvlist_t * allcfgs)150 write_map(const char *filename, nvlist_t *allcfgs)
151 {
152 size_t buflen = 0;
153 int error;
154
155 error = nvlist_size(allcfgs, &buflen, NV_ENCODE_XDR);
156 if (error)
157 return (error);
158
159 char *buf = malloc(buflen);
160 if (buf == NULL)
161 return (ENOMEM);
162
163 error = nvlist_pack(allcfgs, &buf, &buflen, NV_ENCODE_XDR, KM_SLEEP);
164 if (error) {
165 free(buf);
166 return (error);
167 }
168
169 /*
170 * Atomically update the file using a temporary file and the
171 * traditional unlink then rename steps. This code provides
172 * no locking, it only guarantees the packed nvlist on disk
173 * is updated atomically and is internally consistent.
174 */
175 char *tmpname = calloc(1, MAXPATHLEN);
176 if (tmpname == NULL) {
177 free(buf);
178 return (ENOMEM);
179 }
180
181 snprintf(tmpname, MAXPATHLEN - 1, "%s.XXXXXX", filename);
182
183 int fd = mkstemp(tmpname);
184 if (fd < 0) {
185 error = errno;
186 free(buf);
187 free(tmpname);
188 return (error);
189 }
190 (void) close(fd);
191
192 gzFile fp = gzopen(tmpname, "w9b");
193 if (fp == Z_NULL) {
194 error = errno;
195 free(buf);
196 free(tmpname);
197 return (error);
198 }
199
200 ssize_t rc, bytes = 0;
201 while (bytes < buflen) {
202 size_t size = MIN(buflen - bytes, 131072);
203 rc = gzwrite(fp, buf + bytes, size);
204 if (rc < 0) {
205 free(buf);
206 (void) gzerror(fp, &error);
207 (void) gzclose(fp);
208 (void) unlink(tmpname);
209 free(tmpname);
210 return (error);
211 } else if (rc == 0) {
212 break;
213 } else {
214 bytes += rc;
215 }
216 }
217
218 free(buf);
219 (void) gzclose(fp);
220
221 if (bytes != buflen) {
222 (void) unlink(tmpname);
223 free(tmpname);
224 return (EIO);
225 }
226
227 /*
228 * Unlink the previous config file and replace it with the updated
229 * version. If we're able to unlink the file then directory is
230 * writable by us and the subsequent rename should never fail.
231 */
232 error = unlink(filename);
233 if (error != 0 && errno != ENOENT) {
234 error = errno;
235 (void) unlink(tmpname);
236 free(tmpname);
237 return (error);
238 }
239
240 error = rename(tmpname, filename);
241 if (error != 0) {
242 error = errno;
243 (void) unlink(tmpname);
244 free(tmpname);
245 return (error);
246 }
247
248 free(tmpname);
249
250 return (0);
251 }
252
253 /*
254 * Add the dRAID map to the file and write it out.
255 */
256 static int
write_map_key(const char * filename,char * key,draid_map_t * map,double worst_ratio,double avg_ratio)257 write_map_key(const char *filename, char *key, draid_map_t *map,
258 double worst_ratio, double avg_ratio)
259 {
260 nvlist_t *nv_cfg, *allcfgs;
261 int error;
262
263 /*
264 * Add the configuration to an existing or new file. The new
265 * configuration will replace an existing configuration with the
266 * same key if it has a lower ratio and is therefore better.
267 */
268 error = read_map(filename, &allcfgs);
269 if (error == ENOENT) {
270 allcfgs = fnvlist_alloc();
271 } else if (error != 0) {
272 return (error);
273 }
274
275 error = nvlist_lookup_nvlist(allcfgs, key, &nv_cfg);
276 if (error == 0) {
277 uint64_t nv_cfg_worst_ratio = fnvlist_lookup_uint64(nv_cfg,
278 MAP_WORST_RATIO);
279 double nv_worst_ratio = (double)nv_cfg_worst_ratio / 1000.0;
280
281 if (worst_ratio < nv_worst_ratio) {
282 /* Replace old map with the more balanced new map. */
283 fnvlist_remove(allcfgs, key);
284 } else {
285 /* The old map is preferable, keep it. */
286 nvlist_free(allcfgs);
287 return (EEXIST);
288 }
289 }
290
291 nvlist_t *cfg = fnvlist_alloc();
292 fnvlist_add_uint64(cfg, MAP_SEED, map->dm_seed);
293 fnvlist_add_uint64(cfg, MAP_CHECKSUM, map->dm_checksum);
294 fnvlist_add_uint64(cfg, MAP_CHILDREN, map->dm_children);
295 fnvlist_add_uint64(cfg, MAP_NPERMS, map->dm_nperms);
296 fnvlist_add_uint8_array(cfg, MAP_PERMS, map->dm_perms,
297 map->dm_children * map->dm_nperms * sizeof (uint8_t));
298
299 fnvlist_add_uint64(cfg, MAP_WORST_RATIO,
300 (uint64_t)(worst_ratio * 1000.0));
301 fnvlist_add_uint64(cfg, MAP_AVG_RATIO,
302 (uint64_t)(avg_ratio * 1000.0));
303
304 error = nvlist_add_nvlist(allcfgs, key, cfg);
305 if (error == 0)
306 error = write_map(filename, allcfgs);
307
308 nvlist_free(cfg);
309 nvlist_free(allcfgs);
310 return (error);
311 }
312
313 static void
dump_map(draid_map_t * map,const char * key,double worst_ratio,double avg_ratio,int verbose)314 dump_map(draid_map_t *map, const char *key, double worst_ratio,
315 double avg_ratio, int verbose)
316 {
317 if (verbose == 0) {
318 return;
319 } else if (verbose == 1) {
320 printf(" \"%s\": seed: 0x%016llx worst_ratio: %2.03f "
321 "avg_ratio: %2.03f\n", key, (u_longlong_t)map->dm_seed,
322 worst_ratio, avg_ratio);
323 return;
324 } else {
325 printf(" \"%s\":\n"
326 " seed: 0x%016llx\n"
327 " checksum: 0x%016llx\n"
328 " worst_ratio: %2.03f\n"
329 " avg_ratio: %2.03f\n"
330 " children: %llu\n"
331 " nperms: %llu\n",
332 key, (u_longlong_t)map->dm_seed,
333 (u_longlong_t)map->dm_checksum, worst_ratio, avg_ratio,
334 (u_longlong_t)map->dm_children,
335 (u_longlong_t)map->dm_nperms);
336
337 if (verbose > 2) {
338 printf(" perms = {\n");
339 for (int i = 0; i < map->dm_nperms; i++) {
340 printf(" { ");
341 for (int j = 0; j < map->dm_children; j++) {
342 printf("%3d%s ", map->dm_perms[
343 i * map->dm_children + j],
344 j < map->dm_children - 1 ?
345 "," : "");
346 }
347 printf(" },\n");
348 }
349 printf(" }\n");
350 } else if (verbose == 2) {
351 printf(" draid_perms = <omitted>\n");
352 }
353 }
354 }
355
356 static void
dump_map_nv(const char * key,nvlist_t * cfg,int verbose)357 dump_map_nv(const char *key, nvlist_t *cfg, int verbose)
358 {
359 draid_map_t map;
360 uint_t c;
361
362 uint64_t worst_ratio = fnvlist_lookup_uint64(cfg, MAP_WORST_RATIO);
363 uint64_t avg_ratio = fnvlist_lookup_uint64(cfg, MAP_AVG_RATIO);
364
365 map.dm_seed = fnvlist_lookup_uint64(cfg, MAP_SEED);
366 map.dm_checksum = fnvlist_lookup_uint64(cfg, MAP_CHECKSUM);
367 map.dm_children = fnvlist_lookup_uint64(cfg, MAP_CHILDREN);
368 map.dm_nperms = fnvlist_lookup_uint64(cfg, MAP_NPERMS);
369 map.dm_perms = fnvlist_lookup_uint8_array(cfg, MAP_PERMS, &c);
370
371 dump_map(&map, key, (double)worst_ratio / 1000.0,
372 avg_ratio / 1000.0, verbose);
373 }
374
375 /*
376 * Print a summary of the mapping.
377 */
378 static int
dump_map_key(const char * filename,const char * key,int verbose)379 dump_map_key(const char *filename, const char *key, int verbose)
380 {
381 nvlist_t *cfg;
382 int error;
383
384 error = read_map_key(filename, key, &cfg);
385 if (error != 0)
386 return (error);
387
388 dump_map_nv(key, cfg, verbose);
389
390 return (0);
391 }
392
393 /*
394 * Allocate a new permutation map for evaluation.
395 */
396 static int
alloc_new_map(uint64_t children,uint64_t nperms,uint64_t seed,draid_map_t ** mapp)397 alloc_new_map(uint64_t children, uint64_t nperms, uint64_t seed,
398 draid_map_t **mapp)
399 {
400 draid_map_t *map;
401 int error;
402
403 map = malloc(sizeof (draid_map_t));
404 if (map == NULL)
405 return (ENOMEM);
406
407 map->dm_children = children;
408 map->dm_nperms = nperms;
409 map->dm_seed = seed;
410 map->dm_checksum = 0;
411
412 error = vdev_draid_generate_perms(map, &map->dm_perms);
413 if (error) {
414 free(map);
415 return (error);
416 }
417
418 *mapp = map;
419
420 return (0);
421 }
422
423 /*
424 * Allocate the fixed permutation map for N children.
425 */
426 static int
alloc_fixed_map(uint64_t children,draid_map_t ** mapp)427 alloc_fixed_map(uint64_t children, draid_map_t **mapp)
428 {
429 const draid_map_t *fixed_map;
430 draid_map_t *map;
431 int error;
432
433 error = vdev_draid_lookup_map(children, &fixed_map);
434 if (error)
435 return (error);
436
437 map = malloc(sizeof (draid_map_t));
438 if (map == NULL)
439 return (ENOMEM);
440
441 memcpy(map, fixed_map, sizeof (draid_map_t));
442 VERIFY3U(map->dm_checksum, !=, 0);
443
444 error = vdev_draid_generate_perms(map, &map->dm_perms);
445 if (error) {
446 free(map);
447 return (error);
448 }
449
450 *mapp = map;
451
452 return (0);
453 }
454
455 /*
456 * Free a permutation map.
457 */
458 static void
free_map(draid_map_t * map)459 free_map(draid_map_t *map)
460 {
461 free(map->dm_perms);
462 free(map);
463 }
464
465 /*
466 * Check if dev is in the provided list of faulted devices.
467 */
468 static inline boolean_t
is_faulted(int * faulted_devs,int nfaulted,int dev)469 is_faulted(int *faulted_devs, int nfaulted, int dev)
470 {
471 for (int i = 0; i < nfaulted; i++)
472 if (faulted_devs[i] == dev)
473 return (B_TRUE);
474
475 return (B_FALSE);
476 }
477
478 /*
479 * Evaluate how resilvering I/O will be distributed given a list of faulted
480 * vdevs. As a simplification we assume one IO is sufficient to repair each
481 * damaged device in a group.
482 */
483 static double
eval_resilver(draid_map_t * map,uint64_t groupwidth,uint64_t nspares,int * faulted_devs,int nfaulted,int * min_child_ios,int * max_child_ios)484 eval_resilver(draid_map_t *map, uint64_t groupwidth, uint64_t nspares,
485 int *faulted_devs, int nfaulted, int *min_child_ios, int *max_child_ios)
486 {
487 uint64_t children = map->dm_children;
488 uint64_t ngroups = 1;
489 uint64_t ndisks = children - nspares;
490
491 /*
492 * Calculate the minimum number of groups required to fill a slice.
493 */
494 while (ngroups * (groupwidth) % (children - nspares) != 0)
495 ngroups++;
496
497 int *ios = calloc(map->dm_children, sizeof (uint64_t));
498
499 ASSERT3P(ios, !=, NULL);
500
501 /* Resilver all rows */
502 for (int i = 0; i < map->dm_nperms; i++) {
503 uint8_t *row = &map->dm_perms[i * map->dm_children];
504
505 /* Resilver all groups with faulted drives */
506 for (int j = 0; j < ngroups; j++) {
507 uint64_t spareidx = map->dm_children - nspares;
508 boolean_t repair_needed = B_FALSE;
509
510 /* See if any devices in this group are faulted */
511 uint64_t groupstart = (j * groupwidth) % ndisks;
512
513 for (int k = 0; k < groupwidth; k++) {
514 uint64_t groupidx = (groupstart + k) % ndisks;
515
516 repair_needed = is_faulted(faulted_devs,
517 nfaulted, row[groupidx]);
518 if (repair_needed)
519 break;
520 }
521
522 if (repair_needed == B_FALSE)
523 continue;
524
525 /*
526 * This group is degraded. Calculate the number of
527 * reads the non-faulted drives require and the number
528 * of writes to the distributed hot spare for this row.
529 */
530 for (int k = 0; k < groupwidth; k++) {
531 uint64_t groupidx = (groupstart + k) % ndisks;
532
533 if (!is_faulted(faulted_devs, nfaulted,
534 row[groupidx])) {
535 ios[row[groupidx]]++;
536 } else if (nspares > 0) {
537 while (is_faulted(faulted_devs,
538 nfaulted, row[spareidx])) {
539 spareidx++;
540 }
541
542 ASSERT3U(spareidx, <, map->dm_children);
543 ios[row[spareidx]]++;
544 spareidx++;
545 }
546 }
547 }
548 }
549
550 *min_child_ios = INT_MAX;
551 *max_child_ios = 0;
552
553 /*
554 * Find the drives with fewest and most required I/O. These values
555 * are used to calculate the imbalance ratio. To avoid returning an
556 * infinite value for permutations which have children that perform
557 * no IO a floor of 1 IO per child is set. This ensures a meaningful
558 * ratio is returned for comparison and it is not an uncommon when
559 * there are a large number of children.
560 */
561 for (int i = 0; i < map->dm_children; i++) {
562
563 if (is_faulted(faulted_devs, nfaulted, i)) {
564 ASSERT0(ios[i]);
565 continue;
566 }
567
568 if (ios[i] == 0)
569 ios[i] = 1;
570
571 if (ios[i] < *min_child_ios)
572 *min_child_ios = ios[i];
573
574 if (ios[i] > *max_child_ios)
575 *max_child_ios = ios[i];
576 }
577
578 ASSERT3S(*min_child_ios, !=, INT_MAX);
579 ASSERT3S(*max_child_ios, !=, 0);
580
581 double ratio = (double)(*max_child_ios) / (double)(*min_child_ios);
582
583 free(ios);
584
585 return (ratio);
586 }
587
588 /*
589 * Evaluate the quality of the permutation mapping by considering possible
590 * device failures. Returns the imbalance ratio for the worst mapping which
591 * is defined to be the largest number of child IOs over the fewest number
592 * child IOs. A value of 1.0 indicates the mapping is perfectly balance and
593 * all children perform an equal amount of work during reconstruction.
594 */
595 static void
eval_decluster(draid_map_t * map,double * worst_ratiop,double * avg_ratiop)596 eval_decluster(draid_map_t *map, double *worst_ratiop, double *avg_ratiop)
597 {
598 uint64_t children = map->dm_children;
599 double worst_ratio = 1.0;
600 double sum = 0;
601 int worst_min_ios = 0, worst_max_ios = 0;
602 int n = 0;
603
604 /*
605 * When there are only 2 children there can be no distributed
606 * spare and no resilver to evaluate. Default to a ratio of 1.0
607 * for this degenerate case.
608 */
609 if (children == VDEV_DRAID_MIN_CHILDREN) {
610 *worst_ratiop = 1.0;
611 *avg_ratiop = 1.0;
612 return;
613 }
614
615 /*
616 * Score the mapping as if it had either 1 or 2 distributed spares.
617 */
618 for (int nspares = 1; nspares <= 2; nspares++) {
619 uint64_t faults = nspares;
620
621 /*
622 * Score groupwidths up to 19. This value was chosen as the
623 * largest reasonable width (16d+3p). dRAID pools may be still
624 * be created with wider stripes but they are not considered in
625 * this analysis in order to optimize for the most common cases.
626 */
627 for (uint64_t groupwidth = 2;
628 groupwidth <= MIN(children - nspares, 19);
629 groupwidth++) {
630 int faulted_devs[2];
631 int min_ios, max_ios;
632
633 /*
634 * Score possible devices faults. This is limited
635 * to exactly one fault per distributed spare for
636 * the purposes of this similation.
637 */
638 for (int f1 = 0; f1 < children; f1++) {
639 faulted_devs[0] = f1;
640 double ratio;
641
642 if (faults == 1) {
643 ratio = eval_resilver(map, groupwidth,
644 nspares, faulted_devs, faults,
645 &min_ios, &max_ios);
646
647 if (ratio > worst_ratio) {
648 worst_ratio = ratio;
649 worst_min_ios = min_ios;
650 worst_max_ios = max_ios;
651 }
652
653 sum += ratio;
654 n++;
655 } else if (faults == 2) {
656 for (int f2 = f1 + 1; f2 < children;
657 f2++) {
658 faulted_devs[1] = f2;
659
660 ratio = eval_resilver(map,
661 groupwidth, nspares,
662 faulted_devs, faults,
663 &min_ios, &max_ios);
664
665 if (ratio > worst_ratio) {
666 worst_ratio = ratio;
667 worst_min_ios = min_ios;
668 worst_max_ios = max_ios;
669 }
670
671 sum += ratio;
672 n++;
673 }
674 }
675 }
676 }
677 }
678
679 *worst_ratiop = worst_ratio;
680 *avg_ratiop = sum / n;
681
682 /*
683 * Log the min/max io values for particularly unbalanced maps.
684 * Since the maps are generated entirely randomly these are possible
685 * be exceedingly unlikely. We log it for possible investigation.
686 */
687 if (worst_ratio > 100.0) {
688 dump_map(map, "DEBUG", worst_ratio, *avg_ratiop, 2);
689 printf("worst_min_ios=%d worst_max_ios=%d\n",
690 worst_min_ios, worst_max_ios);
691 }
692 }
693
694 static int
eval_maps(uint64_t children,int passes,uint64_t * map_seed,draid_map_t ** best_mapp,double * best_ratiop,double * avg_ratiop)695 eval_maps(uint64_t children, int passes, uint64_t *map_seed,
696 draid_map_t **best_mapp, double *best_ratiop, double *avg_ratiop)
697 {
698 draid_map_t *best_map = NULL;
699 double best_worst_ratio = 1000.0;
700 double best_avg_ratio = 1000.0;
701
702 /*
703 * Perform the requested number of passes evaluating randomly
704 * generated permutation maps. Only the best version is kept.
705 */
706 for (int i = 0; i < passes; i++) {
707 double worst_ratio, avg_ratio;
708 draid_map_t *map;
709 int error;
710
711 /*
712 * Calculate the next seed and generate a new candidate map.
713 */
714 error = alloc_new_map(children, MAP_ROWS_DEFAULT,
715 vdev_draid_rand(map_seed), &map);
716 if (error) {
717 if (best_map != NULL)
718 free_map(best_map);
719 return (error);
720 }
721
722 /*
723 * Consider maps with a lower worst_ratio to be of higher
724 * quality. Some maps may have a lower avg_ratio but they
725 * are discarded since they might include some particularly
726 * imbalanced permutations. The average is tracked to in
727 * order to get a sense of the average permutation quality.
728 */
729 eval_decluster(map, &worst_ratio, &avg_ratio);
730
731 if (best_map == NULL || worst_ratio < best_worst_ratio) {
732
733 if (best_map != NULL)
734 free_map(best_map);
735
736 best_map = map;
737 best_worst_ratio = worst_ratio;
738 best_avg_ratio = avg_ratio;
739 } else {
740 free_map(map);
741 }
742 }
743
744 /*
745 * After determining the best map generate a checksum over the full
746 * permutation array. This checksum is verified when opening a dRAID
747 * pool to ensure the generated in memory permutations are correct.
748 */
749 zio_cksum_t cksum;
750 fletcher_4_native_varsize(best_map->dm_perms,
751 sizeof (uint8_t) * best_map->dm_children * best_map->dm_nperms,
752 &cksum);
753 best_map->dm_checksum = cksum.zc_word[0];
754
755 *best_mapp = best_map;
756 *best_ratiop = best_worst_ratio;
757 *avg_ratiop = best_avg_ratio;
758
759 return (0);
760 }
761
762 static int
draid_generate(int argc,char * argv[])763 draid_generate(int argc, char *argv[])
764 {
765 char filename[MAXPATHLEN] = {0};
766 uint64_t map_seed[2];
767 int c, fd, error, verbose = 0, passes = 1, continuous = 0;
768 int min_children = VDEV_DRAID_MIN_CHILDREN;
769 int max_children = VDEV_DRAID_MAX_CHILDREN;
770 int restarts = 0;
771
772 while ((c = getopt(argc, argv, ":cm:n:p:v")) != -1) {
773 switch (c) {
774 case 'c':
775 continuous++;
776 break;
777 case 'm':
778 min_children = (int)strtol(optarg, NULL, 0);
779 if (min_children < VDEV_DRAID_MIN_CHILDREN) {
780 (void) fprintf(stderr, "A minimum of 2 "
781 "children are required.\n");
782 return (1);
783 }
784
785 break;
786 case 'n':
787 max_children = (int)strtol(optarg, NULL, 0);
788 if (max_children > VDEV_DRAID_MAX_CHILDREN) {
789 (void) fprintf(stderr, "A maximum of %d "
790 "children are allowed.\n",
791 VDEV_DRAID_MAX_CHILDREN);
792 return (1);
793 }
794 break;
795 case 'p':
796 passes = (int)strtol(optarg, NULL, 0);
797 break;
798 case 'v':
799 /*
800 * 0 - Only log when a better map is added to the file.
801 * 1 - Log the current best map for each child count.
802 * Minimal output on a single summary line.
803 * 2 - Log the current best map for each child count.
804 * More verbose includes most map fields.
805 * 3 - Log the current best map for each child count.
806 * Very verbose all fields including the full map.
807 */
808 verbose++;
809 break;
810 case ':':
811 (void) fprintf(stderr,
812 "missing argument for '%c' option\n", optopt);
813 draid_usage();
814 break;
815 case '?':
816 (void) fprintf(stderr, "invalid option '%c'\n",
817 optopt);
818 draid_usage();
819 break;
820 }
821 }
822
823 if (argc > optind)
824 strlcpy(filename, argv[optind], sizeof (filename));
825 else {
826 (void) fprintf(stderr, "A FILE must be specified.\n");
827 return (1);
828 }
829
830 restart:
831 /*
832 * Start with a fresh seed from /dev/urandom.
833 */
834 fd = open("/dev/urandom", O_RDONLY);
835 if (fd < 0) {
836 printf("Unable to open /dev/urandom: %s\n:", strerror(errno));
837 return (1);
838 } else {
839 ssize_t bytes = sizeof (map_seed);
840 ssize_t bytes_read = 0;
841
842 while (bytes_read < bytes) {
843 ssize_t rc = read(fd, ((char *)map_seed) + bytes_read,
844 bytes - bytes_read);
845 if (rc < 0) {
846 printf("Unable to read /dev/urandom: %s\n:",
847 strerror(errno));
848 close(fd);
849 return (1);
850 }
851 bytes_read += rc;
852 }
853
854 (void) close(fd);
855 }
856
857 if (restarts == 0)
858 printf("Writing generated mappings to '%s':\n", filename);
859
860 /*
861 * Generate maps for all requested child counts. The best map for
862 * each child count is written out to the specified file. If the file
863 * already contains a better mapping this map will not be added.
864 */
865 for (uint64_t children = min_children;
866 children <= max_children; children++) {
867 char key[8] = { 0 };
868 draid_map_t *map;
869 double worst_ratio = 1000.0;
870 double avg_ratio = 1000.0;
871
872 error = eval_maps(children, passes, map_seed, &map,
873 &worst_ratio, &avg_ratio);
874 if (error) {
875 printf("Error eval_maps(): %s\n", strerror(error));
876 return (1);
877 }
878
879 if (worst_ratio < 1.0 || avg_ratio < 1.0) {
880 printf("Error ratio < 1.0: worst_ratio = %2.03f "
881 "avg_ratio = %2.03f\n", worst_ratio, avg_ratio);
882 return (1);
883 }
884
885 snprintf(key, 7, "%llu", (u_longlong_t)children);
886 error = write_map_key(filename, key, map, worst_ratio,
887 avg_ratio);
888 if (error == 0) {
889 /* The new map was added to the file. */
890 dump_map(map, key, worst_ratio, avg_ratio,
891 MAX(verbose, 1));
892 } else if (error == EEXIST) {
893 /* The existing map was preferable and kept. */
894 if (verbose > 0)
895 dump_map_key(filename, key, verbose);
896 } else {
897 printf("Error write_map_key(): %s\n", strerror(error));
898 return (1);
899 }
900
901 free_map(map);
902 }
903
904 /*
905 * When the continuous option is set restart at the minimum number of
906 * children instead of exiting. This option is useful as a mechanism
907 * to continuous try and refine the discovered permutations.
908 */
909 if (continuous) {
910 restarts++;
911 printf("Restarting by request (-c): %d\n", restarts);
912 goto restart;
913 }
914
915 return (0);
916 }
917
918 /*
919 * Verify each map in the file by generating its in-memory permutation array
920 * and comfirming its checksum is correct.
921 */
922 static int
draid_verify(int argc,char * argv[])923 draid_verify(int argc, char *argv[])
924 {
925 char filename[MAXPATHLEN] = {0};
926 int n = 0, c, error, verbose = 1;
927 int check_ratios = 0;
928
929 while ((c = getopt(argc, argv, ":rv")) != -1) {
930 switch (c) {
931 case 'r':
932 check_ratios++;
933 break;
934 case 'v':
935 verbose++;
936 break;
937 case ':':
938 (void) fprintf(stderr,
939 "missing argument for '%c' option\n", optopt);
940 draid_usage();
941 break;
942 case '?':
943 (void) fprintf(stderr, "invalid option '%c'\n",
944 optopt);
945 draid_usage();
946 break;
947 }
948 }
949
950 if (argc > optind) {
951 char *abspath = malloc(MAXPATHLEN);
952 if (abspath == NULL)
953 return (ENOMEM);
954
955 if (realpath(argv[optind], abspath) != NULL)
956 strlcpy(filename, abspath, sizeof (filename));
957 else
958 strlcpy(filename, argv[optind], sizeof (filename));
959
960 free(abspath);
961 } else {
962 (void) fprintf(stderr, "A FILE must be specified.\n");
963 return (1);
964 }
965
966 printf("Verifying permutation maps: '%s'\n", filename);
967
968 /*
969 * Lookup hardcoded permutation map for each valid number of children
970 * and verify a generated map has the correct checksum. Then compare
971 * the generated map values with the nvlist map values read from the
972 * reference file to cross-check the permutation.
973 */
974 for (uint64_t children = VDEV_DRAID_MIN_CHILDREN;
975 children <= VDEV_DRAID_MAX_CHILDREN;
976 children++) {
977 draid_map_t *map;
978 char key[8] = {0};
979
980 snprintf(key, 8, "%llu", (u_longlong_t)children);
981
982 error = alloc_fixed_map(children, &map);
983 if (error) {
984 printf("Error alloc_fixed_map() failed: %s\n",
985 error == ECKSUM ? "Invalid checksum" :
986 strerror(error));
987 return (1);
988 }
989
990 uint64_t nv_seed, nv_checksum, nv_children, nv_nperms;
991 uint8_t *nv_perms;
992 nvlist_t *cfg;
993 uint_t c;
994
995 error = read_map_key(filename, key, &cfg);
996 if (error != 0) {
997 printf("Error read_map_key() failed: %s\n",
998 strerror(error));
999 free_map(map);
1000 return (1);
1001 }
1002
1003 nv_seed = fnvlist_lookup_uint64(cfg, MAP_SEED);
1004 nv_checksum = fnvlist_lookup_uint64(cfg, MAP_CHECKSUM);
1005 nv_children = fnvlist_lookup_uint64(cfg, MAP_CHILDREN);
1006 nv_nperms = fnvlist_lookup_uint64(cfg, MAP_NPERMS);
1007 nvlist_lookup_uint8_array(cfg, MAP_PERMS, &nv_perms, &c);
1008
1009 /*
1010 * Compare draid_map_t and nvlist reference values.
1011 */
1012 if (map->dm_seed != nv_seed) {
1013 printf("Error different seeds: 0x%016llx != "
1014 "0x%016llx\n", (u_longlong_t)map->dm_seed,
1015 (u_longlong_t)nv_seed);
1016 error = EINVAL;
1017 }
1018
1019 if (map->dm_checksum != nv_checksum) {
1020 printf("Error different checksums: 0x%016llx "
1021 "!= 0x%016llx\n",
1022 (u_longlong_t)map->dm_checksum,
1023 (u_longlong_t)nv_checksum);
1024 error = EINVAL;
1025 }
1026
1027 if (map->dm_children != nv_children) {
1028 printf("Error different children: %llu "
1029 "!= %llu\n", (u_longlong_t)map->dm_children,
1030 (u_longlong_t)nv_children);
1031 error = EINVAL;
1032 }
1033
1034 if (map->dm_nperms != nv_nperms) {
1035 printf("Error different nperms: %llu "
1036 "!= %llu\n", (u_longlong_t)map->dm_nperms,
1037 (u_longlong_t)nv_nperms);
1038 error = EINVAL;
1039 }
1040
1041 for (uint64_t i = 0; i < nv_children * nv_nperms; i++) {
1042 if (map->dm_perms[i] != nv_perms[i]) {
1043 printf("Error different perms[%llu]: "
1044 "%d != %d\n", (u_longlong_t)i,
1045 (int)map->dm_perms[i],
1046 (int)nv_perms[i]);
1047 error = EINVAL;
1048 break;
1049 }
1050 }
1051
1052 /*
1053 * For good measure recalculate the worst and average
1054 * ratios and confirm they match the nvlist values.
1055 */
1056 if (check_ratios) {
1057 uint64_t nv_worst_ratio, nv_avg_ratio;
1058 double worst_ratio, avg_ratio;
1059
1060 eval_decluster(map, &worst_ratio, &avg_ratio);
1061
1062 nv_worst_ratio = fnvlist_lookup_uint64(cfg,
1063 MAP_WORST_RATIO);
1064 nv_avg_ratio = fnvlist_lookup_uint64(cfg,
1065 MAP_AVG_RATIO);
1066
1067 if (worst_ratio < 1.0 || avg_ratio < 1.0) {
1068 printf("Error ratio out of range %2.03f, "
1069 "%2.03f\n", worst_ratio, avg_ratio);
1070 error = EINVAL;
1071 }
1072
1073 if ((uint64_t)(worst_ratio * 1000.0) !=
1074 nv_worst_ratio) {
1075 printf("Error different worst_ratio %2.03f "
1076 "!= %2.03f\n", (double)nv_worst_ratio /
1077 1000.0, worst_ratio);
1078 error = EINVAL;
1079 }
1080
1081 if ((uint64_t)(avg_ratio * 1000.0) != nv_avg_ratio) {
1082 printf("Error different average_ratio %2.03f "
1083 "!= %2.03f\n", (double)nv_avg_ratio /
1084 1000.0, avg_ratio);
1085 error = EINVAL;
1086 }
1087 }
1088
1089 if (error) {
1090 free_map(map);
1091 nvlist_free(cfg);
1092 return (1);
1093 }
1094
1095 if (verbose > 0) {
1096 printf("- %llu children: good\n",
1097 (u_longlong_t)children);
1098 }
1099 n++;
1100
1101 free_map(map);
1102 nvlist_free(cfg);
1103 }
1104
1105 if (n != (VDEV_DRAID_MAX_CHILDREN - 1)) {
1106 printf("Error permutation maps missing: %d / %d checked\n",
1107 n, VDEV_DRAID_MAX_CHILDREN - 1);
1108 return (1);
1109 }
1110
1111 printf("Successfully verified %d / %d permutation maps\n",
1112 n, VDEV_DRAID_MAX_CHILDREN - 1);
1113
1114 return (0);
1115 }
1116
1117 /*
1118 * Dump the contents of the specified mapping(s) for inspection.
1119 */
1120 static int
draid_dump(int argc,char * argv[])1121 draid_dump(int argc, char *argv[])
1122 {
1123 char filename[MAXPATHLEN] = {0};
1124 int c, error, verbose = 1;
1125 int min_children = VDEV_DRAID_MIN_CHILDREN;
1126 int max_children = VDEV_DRAID_MAX_CHILDREN;
1127
1128 while ((c = getopt(argc, argv, ":vm:n:")) != -1) {
1129 switch (c) {
1130 case 'm':
1131 min_children = (int)strtol(optarg, NULL, 0);
1132 if (min_children < 2) {
1133 (void) fprintf(stderr, "A minimum of 2 "
1134 "children are required.\n");
1135 return (1);
1136 }
1137
1138 break;
1139 case 'n':
1140 max_children = (int)strtol(optarg, NULL, 0);
1141 if (max_children > VDEV_DRAID_MAX_CHILDREN) {
1142 (void) fprintf(stderr, "A maximum of %d "
1143 "children are allowed.\n",
1144 VDEV_DRAID_MAX_CHILDREN);
1145 return (1);
1146 }
1147 break;
1148 case 'v':
1149 verbose++;
1150 break;
1151 case ':':
1152 (void) fprintf(stderr,
1153 "missing argument for '%c' option\n", optopt);
1154 draid_usage();
1155 break;
1156 case '?':
1157 (void) fprintf(stderr, "invalid option '%c'\n",
1158 optopt);
1159 draid_usage();
1160 break;
1161 }
1162 }
1163
1164 if (argc > optind)
1165 strlcpy(filename, argv[optind], sizeof (filename));
1166 else {
1167 (void) fprintf(stderr, "A FILE must be specified.\n");
1168 return (1);
1169 }
1170
1171 /*
1172 * Dump maps for the requested child counts.
1173 */
1174 for (uint64_t children = min_children;
1175 children <= max_children; children++) {
1176 char key[8] = { 0 };
1177
1178 snprintf(key, 7, "%llu", (u_longlong_t)children);
1179 error = dump_map_key(filename, key, verbose);
1180 if (error) {
1181 printf("Error dump_map_key(): %s\n", strerror(error));
1182 return (1);
1183 }
1184 }
1185
1186 return (0);
1187 }
1188
1189 /*
1190 * Print all of the mappings as a C formatted draid_map_t array. This table
1191 * is found in the module/zcommon/zfs_draid.c file and is the definitive
1192 * source for all mapping used by dRAID. It cannot be updated without
1193 * changing the dRAID on disk format.
1194 */
1195 static int
draid_table(int argc,char * argv[])1196 draid_table(int argc, char *argv[])
1197 {
1198 char filename[MAXPATHLEN] = {0};
1199 int error;
1200
1201 if (argc > optind)
1202 strlcpy(filename, argv[optind], sizeof (filename));
1203 else {
1204 (void) fprintf(stderr, "A FILE must be specified.\n");
1205 return (1);
1206 }
1207
1208 printf("static const draid_map_t "
1209 "draid_maps[VDEV_DRAID_MAX_MAPS] = {\n");
1210
1211 for (uint64_t children = VDEV_DRAID_MIN_CHILDREN;
1212 children <= VDEV_DRAID_MAX_CHILDREN;
1213 children++) {
1214 uint64_t seed, checksum, nperms, avg_ratio;
1215 nvlist_t *cfg;
1216 char key[8] = {0};
1217
1218 snprintf(key, 8, "%llu", (u_longlong_t)children);
1219
1220 error = read_map_key(filename, key, &cfg);
1221 if (error != 0) {
1222 printf("Error read_map_key() failed: %s\n",
1223 strerror(error));
1224 return (1);
1225 }
1226
1227 seed = fnvlist_lookup_uint64(cfg, MAP_SEED);
1228 checksum = fnvlist_lookup_uint64(cfg, MAP_CHECKSUM);
1229 children = fnvlist_lookup_uint64(cfg, MAP_CHILDREN);
1230 nperms = fnvlist_lookup_uint64(cfg, MAP_NPERMS);
1231 avg_ratio = fnvlist_lookup_uint64(cfg, MAP_AVG_RATIO);
1232
1233 printf("\t{ %3llu, %3llu, 0x%016llx, 0x%016llx },\t"
1234 "/* %2.03f */\n", (u_longlong_t)children,
1235 (u_longlong_t)nperms, (u_longlong_t)seed,
1236 (u_longlong_t)checksum, (double)avg_ratio / 1000.0);
1237
1238 nvlist_free(cfg);
1239 }
1240
1241 printf("};\n");
1242
1243 return (0);
1244 }
1245
1246 static int
draid_merge_impl(nvlist_t * allcfgs,const char * srcfilename,int * mergedp)1247 draid_merge_impl(nvlist_t *allcfgs, const char *srcfilename, int *mergedp)
1248 {
1249 nvlist_t *srccfgs;
1250 nvpair_t *elem = NULL;
1251 int error, merged = 0;
1252
1253 error = read_map(srcfilename, &srccfgs);
1254 if (error != 0)
1255 return (error);
1256
1257 while ((elem = nvlist_next_nvpair(srccfgs, elem)) != NULL) {
1258 uint64_t nv_worst_ratio;
1259 uint64_t allcfg_worst_ratio;
1260 nvlist_t *cfg, *allcfg;
1261 const char *key;
1262
1263 switch (nvpair_type(elem)) {
1264 case DATA_TYPE_NVLIST:
1265
1266 (void) nvpair_value_nvlist(elem, &cfg);
1267 key = nvpair_name(elem);
1268
1269 nv_worst_ratio = fnvlist_lookup_uint64(cfg,
1270 MAP_WORST_RATIO);
1271
1272 error = nvlist_lookup_nvlist(allcfgs, key, &allcfg);
1273 if (error == 0) {
1274 allcfg_worst_ratio = fnvlist_lookup_uint64(
1275 allcfg, MAP_WORST_RATIO);
1276
1277 if (nv_worst_ratio < allcfg_worst_ratio) {
1278 fnvlist_remove(allcfgs, key);
1279 fnvlist_add_nvlist(allcfgs, key, cfg);
1280 merged++;
1281 }
1282 } else if (error == ENOENT) {
1283 fnvlist_add_nvlist(allcfgs, key, cfg);
1284 merged++;
1285 } else {
1286 return (error);
1287 }
1288
1289 break;
1290 default:
1291 continue;
1292 }
1293 }
1294
1295 nvlist_free(srccfgs);
1296
1297 *mergedp = merged;
1298
1299 return (0);
1300 }
1301
1302 /*
1303 * Merge the best map for each child count found in the listed files into
1304 * a new file. This allows 'draid generate' to be run in parallel and for
1305 * the results maps to be combined.
1306 */
1307 static int
draid_merge(int argc,char * argv[])1308 draid_merge(int argc, char *argv[])
1309 {
1310 char filename[MAXPATHLEN] = {0};
1311 int c, error, total_merged = 0;
1312 nvlist_t *allcfgs;
1313
1314 while ((c = getopt(argc, argv, ":")) != -1) {
1315 switch (c) {
1316 case ':':
1317 (void) fprintf(stderr,
1318 "missing argument for '%c' option\n", optopt);
1319 draid_usage();
1320 break;
1321 case '?':
1322 (void) fprintf(stderr, "invalid option '%c'\n",
1323 optopt);
1324 draid_usage();
1325 break;
1326 }
1327 }
1328
1329 if (argc < 4) {
1330 (void) fprintf(stderr,
1331 "A FILE and multiple SRCs must be specified.\n");
1332 return (1);
1333 }
1334
1335 strlcpy(filename, argv[optind], sizeof (filename));
1336 optind++;
1337
1338 error = read_map(filename, &allcfgs);
1339 if (error == ENOENT) {
1340 allcfgs = fnvlist_alloc();
1341 } else if (error != 0) {
1342 printf("Error read_map(): %s\n", strerror(error));
1343 return (error);
1344 }
1345
1346 while (optind < argc) {
1347 char srcfilename[MAXPATHLEN] = {0};
1348 int merged = 0;
1349
1350 strlcpy(srcfilename, argv[optind], sizeof (srcfilename));
1351
1352 error = draid_merge_impl(allcfgs, srcfilename, &merged);
1353 if (error) {
1354 printf("Error draid_merge_impl(): %s\n",
1355 strerror(error));
1356 nvlist_free(allcfgs);
1357 return (1);
1358 }
1359
1360 total_merged += merged;
1361 printf("Merged %d key(s) from '%s' into '%s'\n", merged,
1362 srcfilename, filename);
1363
1364 optind++;
1365 }
1366
1367 if (total_merged > 0)
1368 write_map(filename, allcfgs);
1369
1370 printf("Merged a total of %d key(s) into '%s'\n", total_merged,
1371 filename);
1372
1373 nvlist_free(allcfgs);
1374
1375 return (0);
1376 }
1377
1378 int
main(int argc,char * argv[])1379 main(int argc, char *argv[])
1380 {
1381 if (argc < 2)
1382 draid_usage();
1383
1384 char *subcommand = argv[1];
1385
1386 if (strcmp(subcommand, "generate") == 0) {
1387 return (draid_generate(argc - 1, argv + 1));
1388 } else if (strcmp(subcommand, "verify") == 0) {
1389 return (draid_verify(argc - 1, argv + 1));
1390 } else if (strcmp(subcommand, "dump") == 0) {
1391 return (draid_dump(argc - 1, argv + 1));
1392 } else if (strcmp(subcommand, "table") == 0) {
1393 return (draid_table(argc - 1, argv + 1));
1394 } else if (strcmp(subcommand, "merge") == 0) {
1395 return (draid_merge(argc - 1, argv + 1));
1396 } else {
1397 draid_usage();
1398 }
1399 }
1400