Back to home page

LXR

 
 

    


0001 /*
0002  * Test cases for <linux/hash.h> and <linux/stringhash.h>
0003  * This just verifies that various ways of computing a hash
0004  * produce the same thing and, for cases where a k-bit hash
0005  * value is requested, is of the requested size.
0006  *
0007  * We fill a buffer with a 255-byte null-terminated string,
0008  * and use both full_name_hash() and hashlen_string() to hash the
0009  * substrings from i to j, where 0 <= i < j < 256.
0010  *
0011  * The returned values are used to check that __hash_32() and
0012  * __hash_32_generic() compute the same thing.  Likewise hash_32()
0013  * and hash_64().
0014  */
0015 
0016 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt "\n"
0017 
0018 #include <linux/compiler.h>
0019 #include <linux/types.h>
0020 #include <linux/module.h>
0021 #include <linux/hash.h>
0022 #include <linux/stringhash.h>
0023 #include <linux/printk.h>
0024 
0025 /* 32-bit XORSHIFT generator.  Seed must not be zero. */
0026 static u32 __init __attribute_const__
0027 xorshift(u32 seed)
0028 {
0029     seed ^= seed << 13;
0030     seed ^= seed >> 17;
0031     seed ^= seed << 5;
0032     return seed;
0033 }
0034 
0035 /* Given a non-zero x, returns a non-zero byte. */
0036 static u8 __init __attribute_const__
0037 mod255(u32 x)
0038 {
0039     x = (x & 0xffff) + (x >> 16);   /* 1 <= x <= 0x1fffe */
0040     x = (x & 0xff) + (x >> 8);  /* 1 <= x <= 0x2fd */
0041     x = (x & 0xff) + (x >> 8);  /* 1 <= x <= 0x100 */
0042     x = (x & 0xff) + (x >> 8);  /* 1 <= x <= 0xff */
0043     return x;
0044 }
0045 
0046 /* Fill the buffer with non-zero bytes. */
0047 static void __init
0048 fill_buf(char *buf, size_t len, u32 seed)
0049 {
0050     size_t i;
0051 
0052     for (i = 0; i < len; i++) {
0053         seed = xorshift(seed);
0054         buf[i] = mod255(seed);
0055     }
0056 }
0057 
0058 /*
0059  * Test the various integer hash functions.  h64 (or its low-order bits)
0060  * is the integer to hash.  hash_or accumulates the OR of the hash values,
0061  * which are later checked to see that they cover all the requested bits.
0062  *
0063  * Because these functions (as opposed to the string hashes) are all
0064  * inline, the code being tested is actually in the module, and you can
0065  * recompile and re-test the module without rebooting.
0066  */
0067 static bool __init
0068 test_int_hash(unsigned long long h64, u32 hash_or[2][33])
0069 {
0070     int k;
0071     u32 h0 = (u32)h64, h1, h2;
0072 
0073     /* Test __hash32 */
0074     hash_or[0][0] |= h1 = __hash_32(h0);
0075 #ifdef HAVE_ARCH__HASH_32
0076     hash_or[1][0] |= h2 = __hash_32_generic(h0);
0077 #if HAVE_ARCH__HASH_32 == 1
0078     if (h1 != h2) {
0079         pr_err("__hash_32(%#x) = %#x != __hash_32_generic() = %#x",
0080             h0, h1, h2);
0081         return false;
0082     }
0083 #endif
0084 #endif
0085 
0086     /* Test k = 1..32 bits */
0087     for (k = 1; k <= 32; k++) {
0088         u32 const m = ((u32)2 << (k-1)) - 1;    /* Low k bits set */
0089 
0090         /* Test hash_32 */
0091         hash_or[0][k] |= h1 = hash_32(h0, k);
0092         if (h1 > m) {
0093             pr_err("hash_32(%#x, %d) = %#x > %#x", h0, k, h1, m);
0094             return false;
0095         }
0096 #ifdef HAVE_ARCH_HASH_32
0097         h2 = hash_32_generic(h0, k);
0098 #if HAVE_ARCH_HASH_32 == 1
0099         if (h1 != h2) {
0100             pr_err("hash_32(%#x, %d) = %#x != hash_32_generic() "
0101                 " = %#x", h0, k, h1, h2);
0102             return false;
0103         }
0104 #else
0105         if (h2 > m) {
0106             pr_err("hash_32_generic(%#x, %d) = %#x > %#x",
0107                 h0, k, h1, m);
0108             return false;
0109         }
0110 #endif
0111 #endif
0112         /* Test hash_64 */
0113         hash_or[1][k] |= h1 = hash_64(h64, k);
0114         if (h1 > m) {
0115             pr_err("hash_64(%#llx, %d) = %#x > %#x", h64, k, h1, m);
0116             return false;
0117         }
0118 #ifdef HAVE_ARCH_HASH_64
0119         h2 = hash_64_generic(h64, k);
0120 #if HAVE_ARCH_HASH_64 == 1
0121         if (h1 != h2) {
0122             pr_err("hash_64(%#llx, %d) = %#x != hash_64_generic() "
0123                 "= %#x", h64, k, h1, h2);
0124             return false;
0125         }
0126 #else
0127         if (h2 > m) {
0128             pr_err("hash_64_generic(%#llx, %d) = %#x > %#x",
0129                 h64, k, h1, m);
0130             return false;
0131         }
0132 #endif
0133 #endif
0134     }
0135 
0136     (void)h2;   /* Suppress unused variable warning */
0137     return true;
0138 }
0139 
0140 #define SIZE 256    /* Run time is cubic in SIZE */
0141 
0142 static int __init
0143 test_hash_init(void)
0144 {
0145     char buf[SIZE+1];
0146     u32 string_or = 0, hash_or[2][33] = { { 0, } };
0147     unsigned tests = 0;
0148     unsigned long long h64 = 0;
0149     int i, j;
0150 
0151     fill_buf(buf, SIZE, 1);
0152 
0153     /* Test every possible non-empty substring in the buffer. */
0154     for (j = SIZE; j > 0; --j) {
0155         buf[j] = '\0';
0156 
0157         for (i = 0; i <= j; i++) {
0158             u64 hashlen = hashlen_string(buf+i, buf+i);
0159             u32 h0 = full_name_hash(buf+i, buf+i, j-i);
0160 
0161             /* Check that hashlen_string gets the length right */
0162             if (hashlen_len(hashlen) != j-i) {
0163                 pr_err("hashlen_string(%d..%d) returned length"
0164                     " %u, expected %d",
0165                     i, j, hashlen_len(hashlen), j-i);
0166                 return -EINVAL;
0167             }
0168             /* Check that the hashes match */
0169             if (hashlen_hash(hashlen) != h0) {
0170                 pr_err("hashlen_string(%d..%d) = %08x != "
0171                     "full_name_hash() = %08x",
0172                     i, j, hashlen_hash(hashlen), h0);
0173                 return -EINVAL;
0174             }
0175 
0176             string_or |= h0;
0177             h64 = h64 << 32 | h0;   /* For use with hash_64 */
0178             if (!test_int_hash(h64, hash_or))
0179                 return -EINVAL;
0180             tests++;
0181         } /* i */
0182     } /* j */
0183 
0184     /* The OR of all the hash values should cover all the bits */
0185     if (~string_or) {
0186         pr_err("OR of all string hash results = %#x != %#x",
0187             string_or, -1u);
0188         return -EINVAL;
0189     }
0190     if (~hash_or[0][0]) {
0191         pr_err("OR of all __hash_32 results = %#x != %#x",
0192             hash_or[0][0], -1u);
0193         return -EINVAL;
0194     }
0195 #ifdef HAVE_ARCH__HASH_32
0196 #if HAVE_ARCH__HASH_32 != 1 /* Test is pointless if results match */
0197     if (~hash_or[1][0]) {
0198         pr_err("OR of all __hash_32_generic results = %#x != %#x",
0199             hash_or[1][0], -1u);
0200         return -EINVAL;
0201     }
0202 #endif
0203 #endif
0204 
0205     /* Likewise for all the i-bit hash values */
0206     for (i = 1; i <= 32; i++) {
0207         u32 const m = ((u32)2 << (i-1)) - 1;    /* Low i bits set */
0208 
0209         if (hash_or[0][i] != m) {
0210             pr_err("OR of all hash_32(%d) results = %#x "
0211                 "(%#x expected)", i, hash_or[0][i], m);
0212             return -EINVAL;
0213         }
0214         if (hash_or[1][i] != m) {
0215             pr_err("OR of all hash_64(%d) results = %#x "
0216                 "(%#x expected)", i, hash_or[1][i], m);
0217             return -EINVAL;
0218         }
0219     }
0220 
0221     /* Issue notices about skipped tests. */
0222 #ifdef HAVE_ARCH__HASH_32
0223 #if HAVE_ARCH__HASH_32 != 1
0224     pr_info("__hash_32() is arch-specific; not compared to generic.");
0225 #endif
0226 #else
0227     pr_info("__hash_32() has no arch implementation to test.");
0228 #endif
0229 #ifdef HAVE_ARCH_HASH_32
0230 #if HAVE_ARCH_HASH_32 != 1
0231     pr_info("hash_32() is arch-specific; not compared to generic.");
0232 #endif
0233 #else
0234     pr_info("hash_32() has no arch implementation to test.");
0235 #endif
0236 #ifdef HAVE_ARCH_HASH_64
0237 #if HAVE_ARCH_HASH_64 != 1
0238     pr_info("hash_64() is arch-specific; not compared to generic.");
0239 #endif
0240 #else
0241     pr_info("hash_64() has no arch implementation to test.");
0242 #endif
0243 
0244     pr_notice("%u tests passed.", tests);
0245 
0246     return 0;
0247 }
0248 
0249 static void __exit test_hash_exit(void)
0250 {
0251 }
0252 
0253 module_init(test_hash_init);    /* Does everything */
0254 module_exit(test_hash_exit);    /* Does nothing */
0255 
0256 MODULE_LICENSE("GPL");