[linux-2.6-block.git] / lib / test_rhashtable.c

/*
 * Resizable, Scalable, Concurrent Hash Table
 *
 * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
 *
 * Based on the following paper:
 * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
 *
 * Code partially derived from nft_hash
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

/**************************************************************************
 * Self Test
 **************************************************************************/

#include <linux/init.h>
#include <linux/jhash.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/rcupdate.h>
#include <linux/rhashtable.h>
#include <linux/slab.h>


#define TEST_HT_SIZE	8
#define TEST_ENTRIES	2048
#define TEST_PTR	((void *) 0xdeadbeef)
#define TEST_NEXPANDS	4

struct test_obj {
	void			*ptr;
	int			value;
	struct rhash_head	node;
};

static const struct rhashtable_params test_rht_params = {
	.nelem_hint = TEST_HT_SIZE,
	.head_offset = offsetof(struct test_obj, node),
	.key_offset = offsetof(struct test_obj, value),
	.key_len = sizeof(int),
	.hashfn = jhash,
	.nulls_base = (3U << RHT_BASE_SHIFT),
};

static int __init test_rht_lookup(struct rhashtable *ht)
{
	unsigned int i;

	for (i = 0; i < TEST_ENTRIES * 2; i++) {
		struct test_obj *obj;
		bool expected = !(i % 2);
		u32 key = i;

		obj = rhashtable_lookup_fast(ht, &key, test_rht_params);

		if (expected && !obj) {
			pr_warn("Test failed: Could not find key %u\n", key);
			return -ENOENT;
		} else if (!expected && obj) {
			pr_warn("Test failed: Unexpected entry found for key %u\n",
				key);
			return -EEXIST;
		} else if (expected && obj) {
			if (obj->ptr != TEST_PTR || obj->value != i) {
				pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
					obj->ptr, TEST_PTR, obj->value, i);
				return -EINVAL;
			}
		}
	}

	return 0;
}

static void test_bucket_stats(struct rhashtable *ht, bool quiet)
{
	unsigned int cnt, rcu_cnt, i, total = 0;
	struct rhash_head *pos;
	struct test_obj *obj;
	struct bucket_table *tbl;

	tbl = rht_dereference_rcu(ht->tbl, ht);
	for (i = 0; i < tbl->size; i++) {
		rcu_cnt = cnt = 0;

		if (!quiet)
			pr_info(" [%#4x/%u]", i, tbl->size);

		rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
			cnt++;
			total++;
			if (!quiet)
				pr_cont(" [%p],", obj);
		}

		rht_for_each_entry_rcu(obj, pos, tbl, i, node)
			rcu_cnt++;

		if (rcu_cnt != cnt)
			pr_warn("Test failed: Chain count mismach %d != %d",
				cnt, rcu_cnt);

		if (!quiet)
			pr_cont("\n  [%#x] first element: %p, chain length: %u\n",
				i, tbl->buckets[i], cnt);
	}

	pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d\n",
		total, atomic_read(&ht->nelems), TEST_ENTRIES);

	if (total != atomic_read(&ht->nelems) || total != TEST_ENTRIES)
		pr_warn("Test failed: Total count mismatch ^^^");
}

static int __init test_rhashtable(struct rhashtable *ht)
{
	struct bucket_table *tbl;
	struct test_obj *obj;
	struct rhash_head *pos, *next;
	int err;
	unsigned int i;

	/*
	 * Insertion Test:
	 * Insert TEST_ENTRIES into table with all keys even numbers
	 */
	pr_info("  Adding %d keys\n", TEST_ENTRIES);
	for (i = 0; i < TEST_ENTRIES; i++) {
		struct test_obj *obj;

		obj = kzalloc(sizeof(*obj), GFP_KERNEL);
		if (!obj) {
			err = -ENOMEM;
			goto error;
		}

		obj->ptr = TEST_PTR;
		obj->value = i * 2;

		err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
		if (err) {
			kfree(obj);
			goto error;
		}
	}

	rcu_read_lock();
	test_bucket_stats(ht, true);
	test_rht_lookup(ht);
	rcu_read_unlock();

	rcu_read_lock();
	test_bucket_stats(ht, true);
	rcu_read_unlock();

	pr_info("  Deleting %d keys\n", TEST_ENTRIES);
	for (i = 0; i < TEST_ENTRIES; i++) {
		u32 key = i * 2;

		obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
		BUG_ON(!obj);

		rhashtable_remove_fast(ht, &obj->node, test_rht_params);
		kfree(obj);
	}

	return 0;

error:
	tbl = rht_dereference_rcu(ht->tbl, ht);
	for (i = 0; i < tbl->size; i++)
		rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
			kfree(obj);

	return err;
}

static struct rhashtable ht;

static int __init test_rht_init(void)
{
	int err;

	pr_info("Running resizable hashtable tests...\n");

	err = rhashtable_init(&ht, &test_rht_params);
	if (err < 0) {
		pr_warn("Test failed: Unable to initialize hashtable: %d\n",
			err);
		return err;
	}

	err = test_rhashtable(&ht);

	rhashtable_destroy(&ht);

	return err;
}

static void __exit test_rht_exit(void)
{
}

module_init(test_rht_init);
module_exit(test_rht_exit);

MODULE_LICENSE("GPL v2");
Commit	Line	Data
9d6dbe1b GU	1	/*
	2	* Resizable, Scalable, Concurrent Hash Table
	3	*
	4	* Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
	5	* Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
	6	*
	7	* Based on the following paper:
	8	* https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
	9	*
	10	* Code partially derived from nft_hash
	11	*
	12	* This program is free software; you can redistribute it and/or modify
	13	* it under the terms of the GNU General Public License version 2 as
	14	* published by the Free Software Foundation.
	15	*/
	16
	17	/**************************************************************************
	18	* Self Test
	19	**************************************************************************/
	20
	21	#include <linux/init.h>
	22	#include <linux/jhash.h>
	23	#include <linux/kernel.h>
	24	#include <linux/module.h>
	25	#include <linux/rcupdate.h>
	26	#include <linux/rhashtable.h>
	27	#include <linux/slab.h>
	28
	29
	30	#define TEST_HT_SIZE 8
	31	#define TEST_ENTRIES 2048
	32	#define TEST_PTR ((void *) 0xdeadbeef)
	33	#define TEST_NEXPANDS 4
	34
	35	struct test_obj {
	36	void *ptr;
	37	int value;
	38	struct rhash_head node;
	39	};
	40
b182aa6e HX	41	static const struct rhashtable_params test_rht_params = {
	42	.nelem_hint = TEST_HT_SIZE,
	43	.head_offset = offsetof(struct test_obj, node),
	44	.key_offset = offsetof(struct test_obj, value),
	45	.key_len = sizeof(int),
	46	.hashfn = jhash,
b182aa6e HX	47	.nulls_base = (3U << RHT_BASE_SHIFT),
	48	};
	49
9d6dbe1b GU	50	static int __init test_rht_lookup(struct rhashtable *ht)
	51	{
	52	unsigned int i;
	53
	54	for (i = 0; i < TEST_ENTRIES * 2; i++) {
	55	struct test_obj *obj;
	56	bool expected = !(i % 2);
	57	u32 key = i;
	58
b182aa6e	59	obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
9d6dbe1b GU	60
	61	if (expected && !obj) {
	62	pr_warn("Test failed: Could not find key %u\n", key);
	63	return -ENOENT;
	64	} else if (!expected && obj) {
	65	pr_warn("Test failed: Unexpected entry found for key %u\n",
	66	key);
	67	return -EEXIST;
	68	} else if (expected && obj) {
	69	if (obj->ptr != TEST_PTR \|\| obj->value != i) {
	70	pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
	71	obj->ptr, TEST_PTR, obj->value, i);
	72	return -EINVAL;
	73	}
	74	}
	75	}
	76
	77	return 0;
	78	}
	79
	80	static void test_bucket_stats(struct rhashtable *ht, bool quiet)
	81	{
	82	unsigned int cnt, rcu_cnt, i, total = 0;
	83	struct rhash_head *pos;
	84	struct test_obj *obj;
	85	struct bucket_table *tbl;
	86
	87	tbl = rht_dereference_rcu(ht->tbl, ht);
	88	for (i = 0; i < tbl->size; i++) {
	89	rcu_cnt = cnt = 0;
	90
	91	if (!quiet)
63d512d0	92	pr_info(" [%#4x/%u]", i, tbl->size);
9d6dbe1b GU	93
	94	rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
	95	cnt++;
	96	total++;
	97	if (!quiet)
	98	pr_cont(" [%p],", obj);
	99	}
	100
	101	rht_for_each_entry_rcu(obj, pos, tbl, i, node)
	102	rcu_cnt++;
	103
	104	if (rcu_cnt != cnt)
	105	pr_warn("Test failed: Chain count mismach %d != %d",
	106	cnt, rcu_cnt);
	107
	108	if (!quiet)
	109	pr_cont("\n [%#x] first element: %p, chain length: %u\n",
	110	i, tbl->buckets[i], cnt);
	111	}
	112
	113	pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d\n",
	114	total, atomic_read(&ht->nelems), TEST_ENTRIES);
	115
	116	if (total != atomic_read(&ht->nelems) \|\| total != TEST_ENTRIES)
	117	pr_warn("Test failed: Total count mismatch ^^^");
	118	}
	119
	120	static int __init test_rhashtable(struct rhashtable *ht)
	121	{
	122	struct bucket_table *tbl;
	123	struct test_obj *obj;
	124	struct rhash_head pos, next;
	125	int err;
	126	unsigned int i;
	127
	128	/*
	129	* Insertion Test:
	130	* Insert TEST_ENTRIES into table with all keys even numbers
	131	*/
	132	pr_info(" Adding %d keys\n", TEST_ENTRIES);
	133	for (i = 0; i < TEST_ENTRIES; i++) {
	134	struct test_obj *obj;
	135
	136	obj = kzalloc(sizeof(*obj), GFP_KERNEL);
	137	if (!obj) {
	138	err = -ENOMEM;
	139	goto error;
	140	}
	141
	142	obj->ptr = TEST_PTR;
	143	obj->value = i * 2;
	144
b182aa6e HX	145	err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
	146	if (err) {
	147	kfree(obj);
	148	goto error;
	149	}
9d6dbe1b GU	150	}
	151
	152	rcu_read_lock();
	153	test_bucket_stats(ht, true);
	154	test_rht_lookup(ht);
	155	rcu_read_unlock();
	156
9d6dbe1b GU	157	rcu_read_lock();
	158	test_bucket_stats(ht, true);
	159	rcu_read_unlock();
	160
	161	pr_info(" Deleting %d keys\n", TEST_ENTRIES);
	162	for (i = 0; i < TEST_ENTRIES; i++) {
	163	u32 key = i * 2;
	164
b182aa6e	165	obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
9d6dbe1b GU	166	BUG_ON(!obj);
9d6dbe1b GU	167
b182aa6e	168	rhashtable_remove_fast(ht, &obj->node, test_rht_params);
9d6dbe1b GU	169	kfree(obj);
	170	}
	171
	172	return 0;
	173
	174	error:
	175	tbl = rht_dereference_rcu(ht->tbl, ht);
	176	for (i = 0; i < tbl->size; i++)
	177	rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
	178	kfree(obj);
	179
	180	return err;
	181	}
	182
b7f5e5c7 DB	183	static struct rhashtable ht;
b7f5e5c7 DB	184
9d6dbe1b GU	185	static int __init test_rht_init(void)
9d6dbe1b GU	186	{
9d6dbe1b GU	187	int err;
	188
	189	pr_info("Running resizable hashtable tests...\n");
	190
b182aa6e	191	err = rhashtable_init(&ht, &test_rht_params);
9d6dbe1b GU	192	if (err < 0) {
	193	pr_warn("Test failed: Unable to initialize hashtable: %d\n",
	194	err);
	195	return err;
	196	}
	197
	198	err = test_rhashtable(&ht);
	199
	200	rhashtable_destroy(&ht);
	201
	202	return err;
	203	}
	204
6dd0c165 DB	205	static void __exit test_rht_exit(void)
	206	{
	207	}
	208
9d6dbe1b	209	module_init(test_rht_init);
6dd0c165	210	module_exit(test_rht_exit);
9d6dbe1b GU	211
9d6dbe1b GU	212	MODULE_LICENSE("GPL v2");