test_hash.c 6.28 KB
Newer Older
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
/*
 * Test cases for <linux/hash.h> and <linux/stringhash.h>
 * This just verifies that various ways of computing a hash
 * produce the same thing and, for cases where a k-bit hash
 * value is requested, is of the requested size.
 *
 * We fill a buffer with a 255-byte null-terminated string,
 * and use both full_name_hash() and hashlen_string() to hash the
 * substrings from i to j, where 0 <= i < j < 256.
 *
 * The returned values are used to check that __hash_32() and
 * __hash_32_generic() compute the same thing.  Likewise hash_32()
 * and hash_64().
 */

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt "\n"

#include <linux/compiler.h>
#include <linux/types.h>
#include <linux/module.h>
#include <linux/hash.h>
#include <linux/stringhash.h>
#include <linux/printk.h>

/* 32-bit XORSHIFT generator.  Seed must not be zero. */
static u32 __init __attribute_const__
xorshift(u32 seed)
{
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

/* Given a non-zero x, returns a non-zero byte. */
static u8 __init __attribute_const__
mod255(u32 x)
{
	x = (x & 0xffff) + (x >> 16);	/* 1 <= x <= 0x1fffe */
	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0x2fd */
	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0x100 */
	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0xff */
	return x;
}

/* Fill the buffer with non-zero bytes. */
static void __init
fill_buf(char *buf, size_t len, u32 seed)
{
	size_t i;

	for (i = 0; i < len; i++) {
		seed = xorshift(seed);
		buf[i] = mod255(seed);
	}
}

/*
 * Test the various integer hash functions.  h64 (or its low-order bits)
 * is the integer to hash.  hash_or accumulates the OR of the hash values,
 * which are later checked to see that they cover all the requested bits.
 *
 * Because these functions (as opposed to the string hashes) are all
 * inline, the code being tested is actually in the module, and you can
 * recompile and re-test the module without rebooting.
 */
static bool __init
test_int_hash(unsigned long long h64, u32 hash_or[2][33])
{
	int k;
	u32 h0 = (u32)h64, h1, h2;

	/* Test __hash32 */
	hash_or[0][0] |= h1 = __hash_32(h0);
#ifdef HAVE_ARCH__HASH_32
	hash_or[1][0] |= h2 = __hash_32_generic(h0);
#if HAVE_ARCH__HASH_32 == 1
	if (h1 != h2) {
		pr_err("__hash_32(%#x) = %#x != __hash_32_generic() = %#x",
			h0, h1, h2);
		return false;
	}
#endif
#endif

	/* Test k = 1..32 bits */
	for (k = 1; k <= 32; k++) {
		u32 const m = ((u32)2 << (k-1)) - 1;	/* Low k bits set */

		/* Test hash_32 */
		hash_or[0][k] |= h1 = hash_32(h0, k);
		if (h1 > m) {
			pr_err("hash_32(%#x, %d) = %#x > %#x", h0, k, h1, m);
			return false;
		}
#ifdef HAVE_ARCH_HASH_32
		h2 = hash_32_generic(h0, k);
#if HAVE_ARCH_HASH_32 == 1
		if (h1 != h2) {
			pr_err("hash_32(%#x, %d) = %#x != hash_32_generic() "
				" = %#x", h0, k, h1, h2);
			return false;
		}
#else
		if (h2 > m) {
			pr_err("hash_32_generic(%#x, %d) = %#x > %#x",
				h0, k, h1, m);
			return false;
		}
#endif
#endif
		/* Test hash_64 */
		hash_or[1][k] |= h1 = hash_64(h64, k);
		if (h1 > m) {
			pr_err("hash_64(%#llx, %d) = %#x > %#x", h64, k, h1, m);
			return false;
		}
#ifdef HAVE_ARCH_HASH_64
		h2 = hash_64_generic(h64, k);
#if HAVE_ARCH_HASH_64 == 1
		if (h1 != h2) {
			pr_err("hash_64(%#llx, %d) = %#x != hash_64_generic() "
				"= %#x", h64, k, h1, h2);
			return false;
		}
#else
		if (h2 > m) {
			pr_err("hash_64_generic(%#llx, %d) = %#x > %#x",
				h64, k, h1, m);
			return false;
		}
#endif
#endif
	}

	(void)h2;	/* Suppress unused variable warning */
	return true;
}

#define SIZE 256	/* Run time is cubic in SIZE */

static int __init
test_hash_init(void)
{
	char buf[SIZE+1];
146
	u32 string_or = 0, hash_or[2][33] = { { 0, } };
147 148 149 150 151 152 153 154 155 156 157
	unsigned tests = 0;
	unsigned long long h64 = 0;
	int i, j;

	fill_buf(buf, SIZE, 1);

	/* Test every possible non-empty substring in the buffer. */
	for (j = SIZE; j > 0; --j) {
		buf[j] = '\0';

		for (i = 0; i <= j; i++) {
158 159
			u64 hashlen = hashlen_string(buf+i, buf+i);
			u32 h0 = full_name_hash(buf+i, buf+i, j-i);
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

			/* Check that hashlen_string gets the length right */
			if (hashlen_len(hashlen) != j-i) {
				pr_err("hashlen_string(%d..%d) returned length"
					" %u, expected %d",
					i, j, hashlen_len(hashlen), j-i);
				return -EINVAL;
			}
			/* Check that the hashes match */
			if (hashlen_hash(hashlen) != h0) {
				pr_err("hashlen_string(%d..%d) = %08x != "
					"full_name_hash() = %08x",
					i, j, hashlen_hash(hashlen), h0);
				return -EINVAL;
			}

			string_or |= h0;
			h64 = h64 << 32 | h0;	/* For use with hash_64 */
			if (!test_int_hash(h64, hash_or))
				return -EINVAL;
			tests++;
		} /* i */
	} /* j */

	/* The OR of all the hash values should cover all the bits */
	if (~string_or) {
		pr_err("OR of all string hash results = %#x != %#x",
			string_or, -1u);
		return -EINVAL;
	}
	if (~hash_or[0][0]) {
		pr_err("OR of all __hash_32 results = %#x != %#x",
			hash_or[0][0], -1u);
		return -EINVAL;
	}
#ifdef HAVE_ARCH__HASH_32
#if HAVE_ARCH__HASH_32 != 1	/* Test is pointless if results match */
	if (~hash_or[1][0]) {
		pr_err("OR of all __hash_32_generic results = %#x != %#x",
			hash_or[1][0], -1u);
		return -EINVAL;
	}
#endif
#endif

	/* Likewise for all the i-bit hash values */
	for (i = 1; i <= 32; i++) {
		u32 const m = ((u32)2 << (i-1)) - 1;	/* Low i bits set */

		if (hash_or[0][i] != m) {
			pr_err("OR of all hash_32(%d) results = %#x "
				"(%#x expected)", i, hash_or[0][i], m);
			return -EINVAL;
		}
		if (hash_or[1][i] != m) {
			pr_err("OR of all hash_64(%d) results = %#x "
				"(%#x expected)", i, hash_or[1][i], m);
			return -EINVAL;
		}
	}

	/* Issue notices about skipped tests. */
222 223
#ifdef HAVE_ARCH__HASH_32
#if HAVE_ARCH__HASH_32 != 1
224 225
	pr_info("__hash_32() is arch-specific; not compared to generic.");
#endif
226 227 228 229 230
#else
	pr_info("__hash_32() has no arch implementation to test.");
#endif
#ifdef HAVE_ARCH_HASH_32
#if HAVE_ARCH_HASH_32 != 1
231 232
	pr_info("hash_32() is arch-specific; not compared to generic.");
#endif
233 234 235 236 237
#else
	pr_info("hash_32() has no arch implementation to test.");
#endif
#ifdef HAVE_ARCH_HASH_64
#if HAVE_ARCH_HASH_64 != 1
238 239
	pr_info("hash_64() is arch-specific; not compared to generic.");
#endif
240 241 242
#else
	pr_info("hash_64() has no arch implementation to test.");
#endif
243 244 245 246 247 248 249 250 251 252 253 254 255 256

	pr_notice("%u tests passed.", tests);

	return 0;
}

static void __exit test_hash_exit(void)
{
}

module_init(test_hash_init);	/* Does everything */
module_exit(test_hash_exit);	/* Does nothing */

MODULE_LICENSE("GPL");