/* * 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 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(ht, &key); 		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/%zu]", 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; 		rhashtable_insert(ht, &obj->node);	} 	rcu_read_lock();	test_bucket_stats(ht, true);	test_rht_lookup(ht);	rcu_read_unlock(); 	for (i = 0; i < TEST_NEXPANDS; i++) {		pr_info("  Table expansion iteration %u...\n", i);		mutex_lock(&ht->mutex);		rhashtable_expand(ht);		mutex_unlock(&ht->mutex); 		rcu_read_lock();		pr_info("  Verifying lookups...\n");		test_rht_lookup(ht);		rcu_read_unlock();	} 	for (i = 0; i < TEST_NEXPANDS; i++) {		pr_info("  Table shrinkage iteration %u...\n", i);		mutex_lock(&ht->mutex);		rhashtable_shrink(ht);		mutex_unlock(&ht->mutex); 		rcu_read_lock();		pr_info("  Verifying lookups...\n");		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(ht, &key);		BUG_ON(!obj); 		rhashtable_remove(ht, &obj->node);		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){	struct rhashtable_params 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,		.max_shift = 1, /* we expand/shrink manually here */		.nulls_base = (3U << RHT_BASE_SHIFT),	};	int err; 	pr_info("Running resizable hashtable tests...\n"); 	err = rhashtable_init(&ht, &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");