Generic wear-leveling algorithm (#16996)

* Initial import of wear-leveling algorithm.

* Alignment.

* Docs tweaks.

* Lock/unlock.

* Update quantum/wear_leveling/wear_leveling_internal.h

Co-authored-by: Stefan Kerkmann <karlk90@pm.me>

* More tests, fix issue with consolidation when unlocked.

* More tests.

* Review comments.

* Add plumbing for FNV1a.

* Another test checking that checksum mismatch clears the cache.

* Check that the write log still gets played back.

Co-authored-by: Stefan Kerkmann <karlk90@pm.me>

1 files changed, 591 insertions, 0 deletions

diff --git a/lib/fnv/fnv64.c b/lib/fnv/fnv64.c
new file mode 100644
index 0000000000..0662d4d657
--- /dev/null
+++ b/lib/fnv/fnv64.c
@@ -0,0 +1,591 @@
+/*
+ * fnv_64 - 64 bit Fowler/Noll/Vo hash of a buffer or string
+ *
+ * @(#) $Revision: 5.5 $
+ * @(#) $Id: fnv64.c,v 5.5 2012/03/21 01:38:12 chongo Exp $
+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv64.c,v $
+ *
+ ***
+ *
+ * Fowler/Noll/Vo hash
+ *
+ * The basis of this hash algorithm was taken from an idea sent
+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
+ *
+ *      Phong Vo (http://www.research.att.com/info/kpv/)
+ *      Glenn Fowler (http://www.research.att.com/~gsf/)
+ *
+ * In a subsequent ballot round:
+ *
+ *      Landon Curt Noll (http://www.isthe.com/chongo/)
+ *
+ * improved on their algorithm.  Some people tried this hash
+ * and found that it worked rather well.  In an EMail message
+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
+ *
+ * FNV hashes are designed to be fast while maintaining a low
+ * collision rate. The FNV speed allows one to quickly hash lots
+ * of data while maintaining a reasonable collision rate.  See:
+ *
+ *      http://www.isthe.com/chongo/tech/comp/fnv/index.html
+ *
+ * for more details as well as other forms of the FNV hash.
+ *
+ ***
+ *
+ * Please do not copyright this code.  This code is in the public domain.
+ *
+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ *
+ * By:
+ *	chongo <Landon Curt Noll> /\oo/\
+ *      http://www.isthe.com/chongo/
+ *
+ * Share and Enjoy!	:-)
+ */
+
+#include <stdio.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <string.h>
+#include "longlong.h"
+#include "fnv.h"
+
+#define WIDTH 64	/* bit width of hash */
+
+#define BUF_SIZE (32*1024)	/* number of bytes to hash at a time */
+
+static char *usage =
+"usage: %s [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]\n"
+"\n"
+"\t-b bcnt\tmask off all but the lower bcnt bits (default 64)\n"
+"\t-m\tmultiple hashes, one per line for each arg\n"
+"\t-s\thash arg as a string (ignoring terminating NUL bytes)\n"
+"\t-t code\t  test hash code: (0 ==> generate test vectors\n"
+"\t\t\t\t   1 ==> validate against FNV test vectors)\n"
+"\t-v\tverbose mode, print arg after hash (implies -m)\n"
+"\targ\tstring (if -s was given) or filename (default stdin)\n"
+"\n"
+"\tNOTE: Programs that begin with fnv0 implement the FNV-0 hash.\n"
+"\t      The FNV-0 hash is historic FNV algorithm that is now deprecated.\n"
+"\n"
+"\tSee http://www.isthe.com/chongo/tech/comp/fnv/index.html for more info.\n"
+"\n"
+"\t@(#) FNV Version: %s\n";
+static char *program;	/* our name */
+
+
+/*
+ * test_fnv64 - test the FNV64 hash
+ *
+ * given:
+ *	hash_type	type of FNV hash to test
+ *	init_hval	initial hash value
+ *	mask	  	lower bit mask
+ *	v_flag	  	1 => print test failure info on stderr
+ *	code	  0 ==> generate FNV test vectors
+ *		  1 ==> validate against FNV test vectors
+ *
+ * returns:	0 ==> OK, else test vector failure number
+ */
+static int
+test_fnv64(enum fnv_type hash_type, Fnv64_t init_hval,
+	   Fnv64_t mask, int v_flag, int code)
+{
+    struct test_vector *t;	/* FNV test vestor */
+    Fnv64_t hval;		/* current hash value */
+    int tstnum;			/* test vector that failed, starting at 1 */
+
+    /*
+     * print preamble if generating test vectors
+     */
+    if (code == 0) {
+	switch (hash_type) {
+	case FNV0_64:
+	    printf("struct fnv0_64_test_vector fnv0_64_vector[] = {\n");
+	    break;
+	case FNV1_64:
+	    printf("struct fnv1_64_test_vector fnv1_64_vector[] = {\n");
+	    break;
+	case FNV1a_64:
+	    printf("struct fnv1a_64_test_vector fnv1a_64_vector[] = {\n");
+	    break;
+	default:
+	    unknown_hash_type(program, hash_type, 12);	/* exit(12) */
+	    /*NOTREACHED*/
+    	}
+    }
+
+    /*
+     * loop thru all test vectors
+     */
+    for (t = fnv_test_str, tstnum = 1; t->buf != NULL; ++t, ++tstnum) {
+
+        /*
+	 * compute the FNV hash
+	 */
+	hval = init_hval;
+	switch (hash_type) {
+	case FNV0_64:
+	case FNV1_64:
+	    hval = fnv_64_buf(t->buf, t->len, hval);
+	    break;
+	case FNV1a_64:
+	    hval = fnv_64a_buf(t->buf, t->len, hval);
+	    break;
+	default:
+	    unknown_hash_type(program, hash_type, 13);	/* exit(13) */
+	    /*NOTREACHED*/
+	}
+
+	/*
+	 * print the vector
+	 */
+#if defined(HAVE_64BIT_LONG_LONG)
+	/*
+	 * HAVE_64BIT_LONG_LONG testing
+	 */
+	switch (code) {
+	case 0:		/* generate the test vector */
+	    printf("    { &fnv_test_str[%d], (Fnv64_t) 0x%016llxULL },\n",
+	    	   tstnum-1, hval & mask);
+	    break;
+
+	case 1:		/* validate against test vector */
+	    switch (hash_type) {
+	    case FNV0_64:
+		if ((hval&mask) != (fnv0_64_vector[tstnum-1].fnv0_64 & mask)) {
+		    if (v_flag) {
+		    	fprintf(stderr, "%s: failed fnv0_64 test # %d\n",
+				program, tstnum);
+		    	fprintf(stderr, "%s: test # 1 is 1st test\n", program);
+			fprintf(stderr,
+			    "%s: expected 0x%016llx != generated: 0x%016llx\n",
+			    program,
+			    (hval&mask),
+			    (fnv0_64_vector[tstnum-1].fnv0_64 & mask));
+		    }
+		    return tstnum;
+		}
+	    	break;
+	    case FNV1_64:
+		if ((hval&mask) != (fnv1_64_vector[tstnum-1].fnv1_64 & mask)) {
+		    if (v_flag) {
+		    	fprintf(stderr, "%s: failed fnv1_64 test # %d\n",
+				program, tstnum);
+		    	fprintf(stderr, "%s: test # 1 is 1st test\n", program);
+			fprintf(stderr,
+			    "%s: expected 0x%016llx != generated: 0x%016llx\n",
+			    program,
+			    (hval&mask),
+			    (fnv1_64_vector[tstnum-1].fnv1_64 & mask));
+		    }
+		    return tstnum;
+		}
+	    	break;
+	    case FNV1a_64:
+		if ((hval&mask) != (fnv1a_64_vector[tstnum-1].fnv1a_64 &mask)) {
+		    if (v_flag) {
+		    	fprintf(stderr, "%s: failed fnv1a_64 test # %d\n",
+				program, tstnum);
+		    	fprintf(stderr, "%s: test # 1 is 1st test\n", program);
+			fprintf(stderr,
+			    "%s: expected 0x%016llx != generated: 0x%016llx\n",
+			    program,
+			    (hval&mask),
+			    (fnv1a_64_vector[tstnum-1].fnv1a_64 & mask));
+		    }
+		    return tstnum;
+		}
+	    	break;
+	    }
+	    break;
+
+    	default:
+	    fprintf(stderr, "%s: -m %d not implemented yet\n", program, code);
+	    exit(14);
+    	}
+#else /* HAVE_64BIT_LONG_LONG */
+	/*
+	 * non HAVE_64BIT_LONG_LONG testing
+	 */
+	switch (code) {
+	case 0:		/* generate the test vector */
+	    printf("    { &fnv_test_str[%d], "
+	    	   "(Fnv64_t) {0x%08lxUL, 0x%08lxUL} },\n",
+	    	   tstnum-1,
+		   (hval.w32[0] & mask.w32[0]),
+		   (hval.w32[1] & mask.w32[1]));
+	    break;
+
+	case 1:		/* validate against test vector */
+	    switch (hash_type) {
+	    case FNV0_64:
+		if (((hval.w32[0] & mask.w32[0]) !=
+		     (fnv0_64_vector[tstnum-1].fnv0_64.w32[0] &
+		      mask.w32[0])) &&
+		    ((hval.w32[1] & mask.w32[1]) !=
+		     (fnv0_64_vector[tstnum-1].fnv0_64.w32[1] &
+		      mask.w32[1]))) {
+		    if (v_flag) {
+		    	fprintf(stderr, "%s: failed fnv0_64 test # %d\n",
+				program, tstnum);
+		    	fprintf(stderr, "%s: test # 1 is 1st test\n", program);
+			fprintf(stderr,
+			    "%s: expected 0x%08llx%08llx != "
+			    "generated: 0x%08llx%08llx\n",
+			    program,
+			    (hval.w32[0] & mask.w32[0]),
+			    (hval.w32[1] & mask.w32[1]),
+			    ((fnv0_64_vector[tstnum-1].fnv0_64.w32[0] &
+			     mask.w32[0])),
+			    ((fnv0_64_vector[tstnum-1].fnv0_64.w32[1] &
+			     mask.w32[1])));
+		    }
+		    return tstnum;
+		}
+	    	break;
+	    case FNV1_64:
+		if (((hval.w32[0] & mask.w32[0]) !=
+		     (fnv1_64_vector[tstnum-1].fnv1_64.w32[0] &
+		      mask.w32[0])) &&
+		    ((hval.w32[1] & mask.w32[1]) !=
+		     (fnv1_64_vector[tstnum-1].fnv1_64.w32[1] &
+		      mask.w32[1]))) {
+		    if (v_flag) {
+		    	fprintf(stderr, "%s: failed fnv1_64 test # %d\n",
+				program, tstnum);
+		    	fprintf(stderr, "%s: test # 1 is 1st test\n", program);
+			fprintf(stderr,
+			    "%s: expected 0x%08llx%08llx != "
+			    "generated: 0x%08llx%08llx\n",
+			    program,
+			    (hval.w32[0] & mask.w32[0]),
+			    (hval.w32[1] & mask.w32[1]),
+			    ((fnv1_64_vector[tstnum-1].fnv1_64.w32[0] &
+			     mask.w32[0])),
+			    ((fnv1_64_vector[tstnum-1].fnv1_64.w32[1] &
+			     mask.w32[1])));
+		    }
+		    return tstnum;
+		}
+	    	break;
+	    case FNV1a_64:
+		if (((hval.w32[0] & mask.w32[0]) !=
+		     (fnv1a_64_vector[tstnum-1].fnv1a_64.w32[0] &
+		      mask.w32[0])) &&
+		    ((hval.w32[1] & mask.w32[1]) !=
+		     (fnv1a_64_vector[tstnum-1].fnv1a_64.w32[1] &
+		      mask.w32[1]))) {
+		    if (v_flag) {
+		    	fprintf(stderr, "%s: failed fnv1a_64 test # %d\n",
+				program, tstnum);
+		    	fprintf(stderr, "%s: test # 1 is 1st test\n", program);
+			fprintf(stderr,
+			    "%s: expected 0x%08llx%08llx != "
+			    "generated: 0x%08llx%08llx\n",
+			    program,
+			    (hval.w32[0] & mask.w32[0]),
+			    (hval.w32[1] & mask.w32[1]),
+			    ((fnv1a_64_vector[tstnum-1].fnv1a_64.w32[0] &
+			     mask.w32[0])),
+			    ((fnv1a_64_vector[tstnum-1].fnv1a_64.w32[1] &
+			     mask.w32[1])));
+		    }
+		    return tstnum;
+		}
+	    	break;
+	    }
+	    break;
+
+    	default:
+	    fprintf(stderr, "%s: -m %d not implemented yet\n", program, code);
+	    exit(15);
+    	}
+#endif /* HAVE_64BIT_LONG_LONG */
+    }
+
+    /*
+     * print completion if generating test vectors
+     */
+    if (code == 0) {
+#if defined(HAVE_64BIT_LONG_LONG)
+	printf("    { NULL, (Fnv64_t) 0 }\n");
+#else /* HAVE_64BIT_LONG_LONG */
+	printf("    { NULL, (Fnv64_t) {0,0} }\n");
+#endif /* HAVE_64BIT_LONG_LONG */
+	printf("};\n");
+    }
+
+    /*
+     * no failures, return code 0 ==> all OK
+     */
+    return 0;
+}
+
+
+/*
+ * main - the main function
+ *
+ * See the above usage for details.
+ */
+int
+main(int argc, char *argv[])
+{
+    char buf[BUF_SIZE+1];	/* read buffer */
+    int readcnt;		/* number of characters written */
+    Fnv64_t hval;		/* current hash value */
+    int s_flag = 0;		/* 1 => -s was given, hash args as strings */
+    int m_flag = 0;		/* 1 => print multiple hashes, one per arg */
+    int v_flag = 0;		/* 1 => verbose hash print */
+    int b_flag = WIDTH;		/* -b flag value */
+    int t_flag = -1;		/* FNV test vector code (0=>print, 1=>test) */
+    enum fnv_type hash_type = FNV_NONE;	/* type of FNV hash to perform */
+    Fnv64_t bmask;		/* mask to apply to output */
+    extern char *optarg;	/* option argument */
+    extern int optind;		/* argv index of the next arg */
+    int fd;			/* open file to process */
+    char *p;
+    int i;
+
+    /*
+     * parse args
+     */
+    program = argv[0];
+    while ((i = getopt(argc, argv, "b:mst:v")) != -1) {
+	switch (i) {
+	case 'b':	/* bcnt bit mask count */
+	    b_flag = atoi(optarg);
+	    break;
+	case 'm':	/* print multiple hashes, one per arg */
+	    m_flag = 1;
+	    break;
+	case 's':	/* hash args as strings */
+	    s_flag = 1;
+	    break;
+	case 't':	/* FNV test vector code */
+	    t_flag = atoi(optarg);
+	    if (t_flag < 0 || t_flag > 1) {
+		fprintf(stderr, "%s: -t code must be 0 or 1\n", program);
+		fprintf(stderr, usage, program, FNV_VERSION);
+		exit(1);
+	    }
+	    m_flag = 1;
+	    break;
+	case 'v':	/* verbose hash print */
+	    m_flag = 1;
+	    v_flag = 1;
+	    break;
+	default:
+	    fprintf(stderr, usage, program, FNV_VERSION);
+	    exit(1);
+	}
+    }
+    /* -t code incompatible with -b, -m and args */
+    if (t_flag >= 0) {
+    	if (b_flag != WIDTH) {
+	    fprintf(stderr, "%s: -t code incompatible with -b\n", program);
+	    exit(2);
+	}
+    	if (s_flag != 0) {
+	    fprintf(stderr, "%s: -t code incompatible with -s\n", program);
+	    exit(3);
+	}
+	if (optind < argc) {
+	    fprintf(stderr, "%s: -t code incompatible args\n", program);
+	    exit(4);
+	}
+    }
+    /* -s requires at least 1 arg */
+    if (s_flag && optind >= argc) {
+	fprintf(stderr, usage, program, FNV_VERSION);
+	exit(5);
+    }
+    /* limit -b values */
+    if (b_flag < 0 || b_flag > WIDTH) {
+	fprintf(stderr, "%s: -b bcnt: %d must be >= 0 and < %d\n",
+		program, b_flag, WIDTH);
+	exit(6);
+    }
+#if defined(HAVE_64BIT_LONG_LONG)
+    if (b_flag == WIDTH) {
+	bmask = (Fnv64_t)0xffffffffffffffffULL;
+    } else {
+	bmask = (Fnv64_t)((1ULL << b_flag) - 1ULL);
+    }
+#else /* HAVE_64BIT_LONG_LONG */
+    if (b_flag == WIDTH) {
+	bmask.w32[0] = 0xffffffffUL;
+	bmask.w32[1] = 0xffffffffUL;
+    } else if (b_flag >= WIDTH/2) {
+	bmask.w32[0] = 0xffffffffUL;
+	bmask.w32[1] = ((1UL << (b_flag-(WIDTH/2))) - 1UL);
+    } else {
+	bmask.w32[0] = ((1UL << b_flag) - 1UL);
+	bmask.w32[1] = 0UL;
+    }
+#endif /* HAVE_64BIT_LONG_LONG */
+
+    /*
+     * start with the initial basis depending on the hash type
+     */
+    p = strrchr(program, '/');
+    if (p == NULL) {
+	p = program;
+    } else {
+	++p;
+    }
+    if (strcmp(p, "fnv064") == 0 || strcmp(p, "no64bit_fnv064") == 0) {
+	/* using non-recommended FNV-0 and zero initial basis */
+	hval = FNV0_64_INIT;
+	hash_type = FNV0_64;
+    } else if (strcmp(p, "fnv164") == 0 || strcmp(p, "no64bit_fnv164") == 0) {
+	/* using FNV-1 and non-zero initial basis */
+	hval = FNV1_64_INIT;
+	hash_type = FNV1_64;
+    } else if (strcmp(p, "fnv1a64") == 0 || strcmp(p, "no64bit_fnv1a64") == 0) {
+	 /* start with the FNV-1a initial basis */
+	hval = FNV1A_64_INIT;
+	hash_type = FNV1a_64;
+    } else {
+	fprintf(stderr, "%s: unknown program name, unknown hash type\n",
+		program);
+	exit(7);
+    }
+
+    /*
+     * FNV test vector processing, if needed
+     */
+    if (t_flag >= 0) {
+	int code;		/* test vector that failed, starting at 1 */
+
+	/*
+	 * perform all tests
+	 */
+	code = test_fnv64(hash_type, hval, bmask, v_flag, t_flag);
+
+	/*
+	 * evaluate the tests
+	 */
+	if (code == 0) {
+	    if (v_flag) {
+	    	printf("passed\n");
+	    }
+	    exit(0);
+	} else {
+	    printf("failed vector (1 is 1st test): %d\n", code);
+	    exit(8);
+	}
+    }
+
+    /*
+     * string hashing
+     */
+    if (s_flag) {
+
+	/* hash any other strings */
+	for (i=optind; i < argc; ++i) {
+	    switch (hash_type) {
+	    case FNV0_64:
+	    case FNV1_64:
+		hval = fnv_64_str(argv[i], hval);
+	    	break;
+	    case FNV1a_64:
+		hval = fnv_64a_str(argv[i], hval);
+		break;
+	    default:
+		unknown_hash_type(program, hash_type, 9);	/* exit(9) */
+		/*NOTREACHED*/
+	    }
+	    if (m_flag) {
+		print_fnv64(hval, bmask, v_flag, argv[i]);
+	    }
+	}
+
+
+    /*
+     * file hashing
+     */
+    } else {
+
+	/*
+	 * case: process only stdin
+	 */
+	if (optind >= argc) {
+
+	    /* case: process only stdin */
+	    while ((readcnt = read(0, buf, BUF_SIZE)) > 0) {
+		switch (hash_type) {
+		case FNV0_64:
+		case FNV1_64:
+		    hval = fnv_64_buf(buf, readcnt, hval);
+		    break;
+		case FNV1a_64:
+		    hval = fnv_64a_buf(buf, readcnt, hval);
+		    break;
+		default:
+		    unknown_hash_type(program, hash_type, 10);	/* exit(10) */
+		    /*NOTREACHED*/
+		}
+	    }
+	    if (m_flag) {
+		print_fnv64(hval, bmask, v_flag, "(stdin)");
+	    }
+
+	} else {
+
+	    /*
+	     * process any other files
+	     */
+	    for (i=optind; i < argc; ++i) {
+
+		/* open the file */
+		fd = open(argv[i], O_RDONLY);
+		if (fd < 0) {
+		    fprintf(stderr, "%s: unable to open file: %s\n",
+			    program, argv[i]);
+		    exit(4);
+		}
+
+		/*  hash the file */
+		while ((readcnt = read(fd, buf, BUF_SIZE)) > 0) {
+		    switch (hash_type) {
+		    case FNV0_64:
+		    case FNV1_64:
+			hval = fnv_64_buf(buf, readcnt, hval);
+			break;
+		    case FNV1a_64:
+			hval = fnv_64a_buf(buf, readcnt, hval);
+			break;
+		    default:
+			unknown_hash_type(program, hash_type, 11);/* exit(11) */
+			/*NOTREACHED*/
+		    }
+		}
+
+		/* finish processing the file */
+		if (m_flag) {
+		    print_fnv64(hval, bmask, v_flag, argv[i]);
+		}
+		close(fd);
+	    }
+	}
+    }
+
+    /*
+     * report hash and exit
+     */
+    if (!m_flag) {
+	print_fnv64(hval, bmask, v_flag, "");
+    }
+    return 0;	/* exit(0); */
+}