1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * Test cases for <linux/hash.h> and <linux/stringhash.h> |
4 | * This just verifies that various ways of computing a hash |
5 | * produce the same thing and, for cases where a k-bit hash |
6 | * value is requested, is of the requested size. |
7 | * |
8 | * We fill a buffer with a 255-byte null-terminated string, |
9 | * and use both full_name_hash() and hashlen_string() to hash the |
10 | * substrings from i to j, where 0 <= i < j < 256. |
11 | * |
12 | * The returned values are used to check that __hash_32() and |
13 | * __hash_32_generic() compute the same thing. Likewise hash_32() |
14 | * and hash_64(). |
15 | */ |
16 | |
17 | #include <linux/compiler.h> |
18 | #include <linux/types.h> |
19 | #include <linux/module.h> |
20 | #include <linux/hash.h> |
21 | #include <linux/stringhash.h> |
22 | #include <kunit/test.h> |
23 | |
24 | /* 32-bit XORSHIFT generator. Seed must not be zero. */ |
25 | static u32 __attribute_const__ |
26 | xorshift(u32 seed) |
27 | { |
28 | seed ^= seed << 13; |
29 | seed ^= seed >> 17; |
30 | seed ^= seed << 5; |
31 | return seed; |
32 | } |
33 | |
34 | /* Given a non-zero x, returns a non-zero byte. */ |
35 | static u8 __attribute_const__ |
36 | mod255(u32 x) |
37 | { |
38 | x = (x & 0xffff) + (x >> 16); /* 1 <= x <= 0x1fffe */ |
39 | x = (x & 0xff) + (x >> 8); /* 1 <= x <= 0x2fd */ |
40 | x = (x & 0xff) + (x >> 8); /* 1 <= x <= 0x100 */ |
41 | x = (x & 0xff) + (x >> 8); /* 1 <= x <= 0xff */ |
42 | return x; |
43 | } |
44 | |
45 | /* Fill the buffer with non-zero bytes. */ |
46 | static void fill_buf(char *buf, size_t len, u32 seed) |
47 | { |
48 | size_t i; |
49 | |
50 | for (i = 0; i < len; i++) { |
51 | seed = xorshift(seed); |
52 | buf[i] = mod255(x: seed); |
53 | } |
54 | } |
55 | |
56 | /* Holds most testing variables for the int test. */ |
57 | struct test_hash_params { |
58 | /* Pointer to integer to be hashed. */ |
59 | unsigned long long *h64; |
60 | /* Low 32-bits of integer to be hashed. */ |
61 | u32 h0; |
62 | /* Arch-specific hash result. */ |
63 | u32 h1; |
64 | /* Generic hash result. */ |
65 | u32 h2; |
66 | /* ORed hashes of given size (in bits). */ |
67 | u32 (*hash_or)[33]; |
68 | }; |
69 | |
70 | #ifdef HAVE_ARCH__HASH_32 |
71 | static void |
72 | test_int__hash_32(struct kunit *test, struct test_hash_params *params) |
73 | { |
74 | params->hash_or[1][0] |= params->h2 = __hash_32_generic(params->h0); |
75 | #if HAVE_ARCH__HASH_32 == 1 |
76 | KUNIT_EXPECT_EQ_MSG(test, params->h1, params->h2, |
77 | "__hash_32(%#x) = %#x != __hash_32_generic() = %#x" , |
78 | params->h0, params->h1, params->h2); |
79 | #endif |
80 | } |
81 | #endif |
82 | |
83 | #ifdef HAVE_ARCH_HASH_64 |
84 | static void |
85 | test_int_hash_64(struct kunit *test, struct test_hash_params *params, u32 const *m, int *k) |
86 | { |
87 | params->h2 = hash_64_generic(*params->h64, *k); |
88 | #if HAVE_ARCH_HASH_64 == 1 |
89 | KUNIT_EXPECT_EQ_MSG(test, params->h1, params->h2, |
90 | "hash_64(%#llx, %d) = %#x != hash_64_generic() = %#x" , |
91 | *params->h64, *k, params->h1, params->h2); |
92 | #else |
93 | KUNIT_EXPECT_LE_MSG(test, params->h1, params->h2, |
94 | "hash_64_generic(%#llx, %d) = %#x > %#x" , |
95 | *params->h64, *k, params->h1, *m); |
96 | #endif |
97 | } |
98 | #endif |
99 | |
100 | /* |
101 | * Test the various integer hash functions. h64 (or its low-order bits) |
102 | * is the integer to hash. hash_or accumulates the OR of the hash values, |
103 | * which are later checked to see that they cover all the requested bits. |
104 | * |
105 | * Because these functions (as opposed to the string hashes) are all |
106 | * inline, the code being tested is actually in the module, and you can |
107 | * recompile and re-test the module without rebooting. |
108 | */ |
109 | static void |
110 | test_int_hash(struct kunit *test, unsigned long long h64, u32 hash_or[2][33]) |
111 | { |
112 | int k; |
113 | struct test_hash_params params = { &h64, (u32)h64, 0, 0, hash_or }; |
114 | |
115 | /* Test __hash32 */ |
116 | hash_or[0][0] |= params.h1 = __hash_32(val: params.h0); |
117 | #ifdef HAVE_ARCH__HASH_32 |
118 | test_int__hash_32(test, ¶ms); |
119 | #endif |
120 | |
121 | /* Test k = 1..32 bits */ |
122 | for (k = 1; k <= 32; k++) { |
123 | u32 const m = ((u32)2 << (k-1)) - 1; /* Low k bits set */ |
124 | |
125 | /* Test hash_32 */ |
126 | hash_or[0][k] |= params.h1 = hash_32(val: params.h0, bits: k); |
127 | KUNIT_EXPECT_LE_MSG(test, params.h1, m, |
128 | "hash_32(%#x, %d) = %#x > %#x" , |
129 | params.h0, k, params.h1, m); |
130 | |
131 | /* Test hash_64 */ |
132 | hash_or[1][k] |= params.h1 = hash_64(val: h64, bits: k); |
133 | KUNIT_EXPECT_LE_MSG(test, params.h1, m, |
134 | "hash_64(%#llx, %d) = %#x > %#x" , |
135 | h64, k, params.h1, m); |
136 | #ifdef HAVE_ARCH_HASH_64 |
137 | test_int_hash_64(test, ¶ms, &m, &k); |
138 | #endif |
139 | } |
140 | } |
141 | |
142 | #define SIZE 256 /* Run time is cubic in SIZE */ |
143 | |
144 | static void test_string_or(struct kunit *test) |
145 | { |
146 | char buf[SIZE+1]; |
147 | u32 string_or = 0; |
148 | int i, j; |
149 | |
150 | fill_buf(buf, SIZE, seed: 1); |
151 | |
152 | /* Test every possible non-empty substring in the buffer. */ |
153 | for (j = SIZE; j > 0; --j) { |
154 | buf[j] = '\0'; |
155 | |
156 | for (i = 0; i <= j; i++) { |
157 | u32 h0 = full_name_hash(salt: buf+i, buf+i, j-i); |
158 | |
159 | string_or |= h0; |
160 | } /* i */ |
161 | } /* j */ |
162 | |
163 | /* The OR of all the hash values should cover all the bits */ |
164 | KUNIT_EXPECT_EQ_MSG(test, string_or, -1u, |
165 | "OR of all string hash results = %#x != %#x" , |
166 | string_or, -1u); |
167 | } |
168 | |
169 | static void test_hash_or(struct kunit *test) |
170 | { |
171 | char buf[SIZE+1]; |
172 | u32 hash_or[2][33] = { { 0, } }; |
173 | unsigned long long h64 = 0; |
174 | int i, j; |
175 | |
176 | fill_buf(buf, SIZE, seed: 1); |
177 | |
178 | /* Test every possible non-empty substring in the buffer. */ |
179 | for (j = SIZE; j > 0; --j) { |
180 | buf[j] = '\0'; |
181 | |
182 | for (i = 0; i <= j; i++) { |
183 | u64 hashlen = hashlen_string(salt: buf+i, name: buf+i); |
184 | u32 h0 = full_name_hash(salt: buf+i, buf+i, j-i); |
185 | |
186 | /* Check that hashlen_string gets the length right */ |
187 | KUNIT_EXPECT_EQ_MSG(test, hashlen_len(hashlen), j-i, |
188 | "hashlen_string(%d..%d) returned length %u, expected %d" , |
189 | i, j, hashlen_len(hashlen), j-i); |
190 | /* Check that the hashes match */ |
191 | KUNIT_EXPECT_EQ_MSG(test, hashlen_hash(hashlen), h0, |
192 | "hashlen_string(%d..%d) = %08x != full_name_hash() = %08x" , |
193 | i, j, hashlen_hash(hashlen), h0); |
194 | |
195 | h64 = h64 << 32 | h0; /* For use with hash_64 */ |
196 | test_int_hash(test, h64, hash_or); |
197 | } /* i */ |
198 | } /* j */ |
199 | |
200 | KUNIT_EXPECT_EQ_MSG(test, hash_or[0][0], -1u, |
201 | "OR of all __hash_32 results = %#x != %#x" , |
202 | hash_or[0][0], -1u); |
203 | #ifdef HAVE_ARCH__HASH_32 |
204 | #if HAVE_ARCH__HASH_32 != 1 /* Test is pointless if results match */ |
205 | KUNIT_EXPECT_EQ_MSG(test, hash_or[1][0], -1u, |
206 | "OR of all __hash_32_generic results = %#x != %#x" , |
207 | hash_or[1][0], -1u); |
208 | #endif |
209 | #endif |
210 | |
211 | /* Likewise for all the i-bit hash values */ |
212 | for (i = 1; i <= 32; i++) { |
213 | u32 const m = ((u32)2 << (i-1)) - 1; /* Low i bits set */ |
214 | |
215 | KUNIT_EXPECT_EQ_MSG(test, hash_or[0][i], m, |
216 | "OR of all hash_32(%d) results = %#x (%#x expected)" , |
217 | i, hash_or[0][i], m); |
218 | KUNIT_EXPECT_EQ_MSG(test, hash_or[1][i], m, |
219 | "OR of all hash_64(%d) results = %#x (%#x expected)" , |
220 | i, hash_or[1][i], m); |
221 | } |
222 | } |
223 | |
224 | static struct kunit_case hash_test_cases[] __refdata = { |
225 | KUNIT_CASE(test_string_or), |
226 | KUNIT_CASE(test_hash_or), |
227 | {} |
228 | }; |
229 | |
230 | static struct kunit_suite hash_test_suite = { |
231 | .name = "hash" , |
232 | .test_cases = hash_test_cases, |
233 | }; |
234 | |
235 | |
236 | kunit_test_suite(hash_test_suite); |
237 | |
238 | MODULE_LICENSE("GPL" ); |
239 | |