linux-imx

/*

 * 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) {