[mirror_ubuntu-bionic-kernel.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)

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)
9d6dbe1b GU	33
	34	struct test_obj {
	35	void *ptr;
	36	int value;
	37	struct rhash_head node;
	38	};
	39
b182aa6e HX	40	static const struct rhashtable_params test_rht_params = {
	41	.nelem_hint = TEST_HT_SIZE,
	42	.head_offset = offsetof(struct test_obj, node),
	43	.key_offset = offsetof(struct test_obj, value),
	44	.key_len = sizeof(int),
	45	.hashfn = jhash,
b182aa6e HX	46	.nulls_base = (3U << RHT_BASE_SHIFT),
	47	};
	48
9d6dbe1b GU	49	static int __init test_rht_lookup(struct rhashtable *ht)
	50	{
	51	unsigned int i;
	52
	53	for (i = 0; i < TEST_ENTRIES * 2; i++) {
	54	struct test_obj *obj;
	55	bool expected = !(i % 2);
	56	u32 key = i;
	57
b182aa6e	58	obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
9d6dbe1b GU	59
	60	if (expected && !obj) {
	61	pr_warn("Test failed: Could not find key %u\n", key);
	62	return -ENOENT;
	63	} else if (!expected && obj) {
	64	pr_warn("Test failed: Unexpected entry found for key %u\n",
	65	key);
	66	return -EEXIST;
	67	} else if (expected && obj) {
	68	if (obj->ptr != TEST_PTR \|\| obj->value != i) {
	69	pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
	70	obj->ptr, TEST_PTR, obj->value, i);
	71	return -EINVAL;
	72	}
	73	}
	74	}
	75
	76	return 0;
	77	}
	78
	79	static void test_bucket_stats(struct rhashtable *ht, bool quiet)
	80	{
	81	unsigned int cnt, rcu_cnt, i, total = 0;
	82	struct rhash_head *pos;
	83	struct test_obj *obj;
	84	struct bucket_table *tbl;
	85
	86	tbl = rht_dereference_rcu(ht->tbl, ht);
	87	for (i = 0; i < tbl->size; i++) {
	88	rcu_cnt = cnt = 0;
	89
	90	if (!quiet)
63d512d0	91	pr_info(" [%#4x/%u]", i, tbl->size);
9d6dbe1b GU	92
	93	rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
	94	cnt++;
	95	total++;
	96	if (!quiet)
	97	pr_cont(" [%p],", obj);
	98	}
	99
	100	rht_for_each_entry_rcu(obj, pos, tbl, i, node)
	101	rcu_cnt++;
	102
	103	if (rcu_cnt != cnt)
	104	pr_warn("Test failed: Chain count mismach %d != %d",
	105	cnt, rcu_cnt);
	106
	107	if (!quiet)
	108	pr_cont("\n [%#x] first element: %p, chain length: %u\n",
	109	i, tbl->buckets[i], cnt);
	110	}
	111
	112	pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d\n",
	113	total, atomic_read(&ht->nelems), TEST_ENTRIES);
	114
	115	if (total != atomic_read(&ht->nelems) \|\| total != TEST_ENTRIES)
	116	pr_warn("Test failed: Total count mismatch ^^^");
	117	}
	118
	119	static int __init test_rhashtable(struct rhashtable *ht)
	120	{
	121	struct bucket_table *tbl;
	122	struct test_obj *obj;
	123	struct rhash_head pos, next;
	124	int err;
	125	unsigned int i;
	126
	127	/*
	128	* Insertion Test:
	129	* Insert TEST_ENTRIES into table with all keys even numbers
	130	*/
	131	pr_info(" Adding %d keys\n", TEST_ENTRIES);
	132	for (i = 0; i < TEST_ENTRIES; i++) {
	133	struct test_obj *obj;
	134
	135	obj = kzalloc(sizeof(*obj), GFP_KERNEL);
	136	if (!obj) {
	137	err = -ENOMEM;
	138	goto error;
	139	}
	140
	141	obj->ptr = TEST_PTR;
	142	obj->value = i * 2;
	143
b182aa6e HX	144	err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
	145	if (err) {
	146	kfree(obj);
	147	goto error;
	148	}
9d6dbe1b GU	149	}
	150
	151	rcu_read_lock();
	152	test_bucket_stats(ht, true);
	153	test_rht_lookup(ht);
	154	rcu_read_unlock();
	155
9d6dbe1b GU	156	rcu_read_lock();
	157	test_bucket_stats(ht, true);
	158	rcu_read_unlock();
	159
	160	pr_info(" Deleting %d keys\n", TEST_ENTRIES);
	161	for (i = 0; i < TEST_ENTRIES; i++) {
	162	u32 key = i * 2;
	163
b182aa6e	164	obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
9d6dbe1b GU	165	BUG_ON(!obj);
9d6dbe1b GU	166
b182aa6e	167	rhashtable_remove_fast(ht, &obj->node, test_rht_params);
9d6dbe1b GU	168	kfree(obj);
	169	}
	170
	171	return 0;
	172
	173	error:
	174	tbl = rht_dereference_rcu(ht->tbl, ht);
	175	for (i = 0; i < tbl->size; i++)
	176	rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
	177	kfree(obj);
	178
	179	return err;
	180	}
	181
b7f5e5c7 DB	182	static struct rhashtable ht;
b7f5e5c7 DB	183
9d6dbe1b GU	184	static int __init test_rht_init(void)
9d6dbe1b GU	185	{
9d6dbe1b GU	186	int err;
	187
	188	pr_info("Running resizable hashtable tests...\n");
	189
b182aa6e	190	err = rhashtable_init(&ht, &test_rht_params);
9d6dbe1b GU	191	if (err < 0) {
	192	pr_warn("Test failed: Unable to initialize hashtable: %d\n",
	193	err);
	194	return err;
	195	}
	196
	197	err = test_rhashtable(&ht);
	198
	199	rhashtable_destroy(&ht);
	200
	201	return err;
	202	}
	203
6dd0c165 DB	204	static void __exit test_rht_exit(void)
	205	{
	206	}
	207
9d6dbe1b	208	module_init(test_rht_init);
6dd0c165	209	module_exit(test_rht_exit);
9d6dbe1b GU	210
9d6dbe1b GU	211	MODULE_LICENSE("GPL v2");