test_rhashtable.c

/*
 * Resizable, Scalable, Concurrent Hash Table
 *
 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
 *
 * 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/kthread.h>
#include <linux/module.h>
#include <linux/rcupdate.h>
#include <linux/rhashtable.h>
#include <linux/semaphore.h>
#include <linux/slab.h>
#include <linux/sched.h>
#include <linux/random.h>
#include <linux/vmalloc.h>

#define MAX_ENTRIES	1000000
#define TEST_INSERT_FAIL INT_MAX

static int parm_entries = 50000;
module_param(parm_entries, int, 0);
MODULE_PARM_DESC(parm_entries, "Number of entries to add (default: 50000)");

static int runs = 4;
module_param(runs, int, 0);
MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");

static int max_size = 0;
module_param(max_size, int, 0);
MODULE_PARM_DESC(max_size, "Maximum table size (default: calculated)");

static bool shrinking = false;
module_param(shrinking, bool, 0);
MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");

static int size = 8;
module_param(size, int, 0);
MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");

static int tcount = 10;
module_param(tcount, int, 0);
MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");

static bool enomem_retry = false;
module_param(enomem_retry, bool, 0);
MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");

struct test_obj_val {
	int	id;
	int	tid;
};

struct test_obj {
	struct test_obj_val	value;
	struct rhash_head	node;
};

struct test_obj_rhl {
	struct test_obj_val	value;
	struct rhlist_head	list_node;
};

struct thread_data {
	unsigned int entries;
	int id;
	struct task_struct *task;
	struct test_obj *objs;
};

static u32 my_hashfn(const void *data, u32 len, u32 seed)
{
	const struct test_obj_rhl *obj = data;

	return (obj->value.id % 10);
}

static int my_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
{
	const struct test_obj_rhl *test_obj = obj;
	const struct test_obj_val *val = arg->key;

	return test_obj->value.id - val->id;
}

static struct rhashtable_params test_rht_params = {
	.head_offset = offsetof(struct test_obj, node),
	.key_offset = offsetof(struct test_obj, value),
	.key_len = sizeof(struct test_obj_val),
	.hashfn = jhash,
};

static struct rhashtable_params test_rht_params_dup = {
	.head_offset = offsetof(struct test_obj_rhl, list_node),
	.key_offset = offsetof(struct test_obj_rhl, value),
	.key_len = sizeof(struct test_obj_val),
	.hashfn = jhash,
	.obj_hashfn = my_hashfn,
	.obj_cmpfn = my_cmpfn,
	.nelem_hint = 128,
	.automatic_shrinking = false,
};

static struct semaphore prestart_sem;
static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);

static int insert_retry(struct rhashtable *ht, struct test_obj *obj,
                        const struct rhashtable_params params)
{
	int err, retries = -1, enomem_retries = 0;

	do {
		retries++;
		cond_resched();
		err = rhashtable_insert_fast(ht, &obj->node, params);
		if (err == -ENOMEM && enomem_retry) {
			enomem_retries++;
			err = -EBUSY;
		}
	} while (err == -EBUSY);

	if (enomem_retries)
		pr_info(" %u insertions retried after -ENOMEM\n",
			enomem_retries);

	return err ? : retries;
}

static int __init test_rht_lookup(struct rhashtable *ht, struct test_obj *array,
				  unsigned int entries)
{
	unsigned int i;

	for (i = 0; i < entries; i++) {
		struct test_obj *obj;
		bool expected = !(i % 2);
		struct test_obj_val key = {
			.id = i,
		};

		if (array[i / 2].value.id == TEST_INSERT_FAIL)
			expected = false;

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

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

		cond_resched_rcu();
	}

	return 0;
}

static void test_bucket_stats(struct rhashtable *ht, unsigned int entries)
{
	unsigned int err, total = 0, chain_len = 0;
	struct rhashtable_iter hti;
	struct rhash_head *pos;

	err = rhashtable_walk_init(ht, &hti, GFP_KERNEL);
	if (err) {
		pr_warn("Test failed: allocation error");
		return;
	}

	rhashtable_walk_start(&hti);

	while ((pos = rhashtable_walk_next(&hti))) {
		if (PTR_ERR(pos) == -EAGAIN) {
			pr_info("Info: encountered resize\n");
			chain_len++;
			continue;
		} else if (IS_ERR(pos)) {
			pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
				PTR_ERR(pos));
			break;
		}

		total++;
	}

	rhashtable_walk_stop(&hti);
	rhashtable_walk_exit(&hti);

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

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

static s64 __init test_rhashtable(struct rhashtable *ht, struct test_obj *array,
				  unsigned int entries)
{
	struct test_obj *obj;
	int err;
	unsigned int i, insert_retries = 0;
	s64 start, end;

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

		obj->value.id = i * 2;
		err = insert_retry(ht, obj, test_rht_params);
		if (err > 0)
			insert_retries += err;
		else if (err)
			return err;
	}

	if (insert_retries)
		pr_info("  %u insertions retried due to memory pressure\n",
			insert_retries);

	test_bucket_stats(ht, entries);
	rcu_read_lock();
	test_rht_lookup(ht, array, entries);
	rcu_read_unlock();

	test_bucket_stats(ht, entries);

	pr_info("  Deleting %d keys\n", entries);
	for (i = 0; i < entries; i++) {
		struct test_obj_val key = {
			.id = i * 2,
		};

		if (array[i].value.id != TEST_INSERT_FAIL) {
			obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
			BUG_ON(!obj);

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

		cond_resched();
	}

	end = ktime_get_ns();
	pr_info("  Duration of test: %lld ns\n", end - start);

	return end - start;
}

static struct rhashtable ht;
static struct rhltable rhlt;

static int __init test_rhltable(unsigned int entries)
{
	struct test_obj_rhl *rhl_test_objects;
	unsigned long *obj_in_table;
	unsigned int i, j, k;
	int ret, err;

	if (entries == 0)
		entries = 1;

	rhl_test_objects = vzalloc(array_size(entries,
					      sizeof(*rhl_test_objects)));
	if (!rhl_test_objects)
		return -ENOMEM;

	ret = -ENOMEM;
	obj_in_table = vzalloc(array_size(sizeof(unsigned long),
					  BITS_TO_LONGS(entries)));
	if (!obj_in_table)
		goto out_free;

	err = rhltable_init(&rhlt, &test_rht_params);
	if (WARN_ON(err))
		goto out_free;

	k = prandom_u32();
	ret = 0;
	for (i = 0; i < entries; i++) {
		rhl_test_objects[i].value.id = k;
		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
				      test_rht_params);
		if (WARN(err, "error %d on element %d\n", err, i))
			break;
		if (err == 0)
			set_bit(i, obj_in_table);
	}

	if (err)
		ret = err;

	pr_info("test %d add/delete pairs into rhlist\n", entries);
	for (i = 0; i < entries; i++) {
		struct rhlist_head *h, *pos;
		struct test_obj_rhl *obj;
		struct test_obj_val key = {
			.id = k,
		};
		bool found;

		rcu_read_lock();
		h = rhltable_lookup(&rhlt, &key, test_rht_params);
		if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
			rcu_read_unlock();
			break;
		}

		if (i) {
			j = i - 1;
			rhl_for_each_entry_rcu(obj, pos, h, list_node) {
				if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
					break;
			}
		}

		cond_resched_rcu();

		found = false;

		rhl_for_each_entry_rcu(obj, pos, h, list_node) {
			if (pos == &rhl_test_objects[i].list_node) {
				found = true;
				break;
			}
		}

		rcu_read_unlock();

		if (WARN(!found, "element %d not found", i))
			break;

		err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
		WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
		if (err == 0)
			clear_bit(i, obj_in_table);
	}

	if (ret == 0 && err)
		ret = err;

	for (i = 0; i < entries; i++) {
		WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);

		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
				      test_rht_params);
		if (WARN(err, "error %d on element %d\n", err, i))
			break;
		if (err == 0)
			set_bit(i, obj_in_table);
	}

	pr_info("test %d random rhlist add/delete operations\n", entries);
	for (j = 0; j < entries; j++) {
		u32 i = prandom_u32_max(entries);
		u32 prand = prandom_u32();

		cond_resched();

		if (prand == 0)
			prand = prandom_u32();

		if (prand & 1) {
			prand >>= 1;
			continue;
		}

		err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
		if (test_bit(i, obj_in_table)) {
			clear_bit(i, obj_in_table);
			if (WARN(err, "cannot remove element at slot %d", i))
				continue;
		} else {
			if (WARN(err != -ENOENT, "removed non-existant element %d, error %d not %d",
			     i, err, -ENOENT))
				continue;
		}

		if (prand & 1) {
			prand >>= 1;
			continue;
		}

		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
		if (err == 0) {
			if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
				continue;
		} else {
			if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
				continue;
		}

		if (prand & 1) {
			prand >>= 1;
			continue;
		}

		i = prandom_u32_max(entries);
		if (test_bit(i, obj_in_table)) {
			err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
			WARN(err, "cannot remove element at slot %d", i);
			if (err == 0)
				clear_bit(i, obj_in_table);
		} else {
			err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
			WARN(err, "failed to insert object %d", i);
			if (err == 0)
				set_bit(i, obj_in_table);
		}
	}

	for (i = 0; i < entries; i++) {
		cond_resched();
		err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
		if (test_bit(i, obj_in_table)) {
			if (WARN(err, "cannot remove element at slot %d", i))
				continue;
		} else {
			if (WARN(err != -ENOENT, "removed non-existant element, error %d not %d",
				 err, -ENOENT))
			continue;
		}
	}

	rhltable_destroy(&rhlt);
out_free:
	vfree(rhl_test_objects);
	vfree(obj_in_table);
	return ret;
}

static int __init test_rhashtable_max(struct test_obj *array,
				      unsigned int entries)
{
	unsigned int i, insert_retries = 0;
	int err;

	test_rht_params.max_size = roundup_pow_of_two(entries / 8);
	err = rhashtable_init(&ht, &test_rht_params);
	if (err)
		return err;

	for (i = 0; i < ht.max_elems; i++) {
		struct test_obj *obj = &array[i];

		obj->value.id = i * 2;
		err = insert_retry(&ht, obj, test_rht_params);
		if (err > 0)
			insert_retries += err;
		else if (err)
			return err;
	}

	err = insert_retry(&ht, &array[ht.max_elems], test_rht_params);
	if (err == -E2BIG) {
		err = 0;
	} else {
		pr_info("insert element %u should have failed with %d, got %d\n",
				ht.max_elems, -E2BIG, err);
		if (err == 0)
			err = -1;
	}

	rhashtable_destroy(&ht);

	return err;
}

static unsigned int __init print_ht(struct rhltable *rhlt)
{
	struct rhashtable *ht;
	const struct bucket_table *tbl;
	char buff[512] = "";
	unsigned int i, cnt = 0;

	ht = &rhlt->ht;
	/* Take the mutex to avoid RCU warning */
	mutex_lock(&ht->mutex);
	tbl = rht_dereference(ht->tbl, ht);
	for (i = 0; i < tbl->size; i++) {
		struct rhash_head *pos, *next;
		struct test_obj_rhl *p;

		pos = rht_dereference(tbl->buckets[i], ht);
		next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;

		if (!rht_is_a_nulls(pos)) {
			sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
		}

		while (!rht_is_a_nulls(pos)) {
			struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
			sprintf(buff, "%s[[", buff);
			do {
				pos = &list->rhead;
				list = rht_dereference(list->next, ht);
				p = rht_obj(ht, pos);

				sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
					list? ", " : " ");
				cnt++;
			} while (list);

			pos = next,
			next = !rht_is_a_nulls(pos) ?
				rht_dereference(pos->next, ht) : NULL;

			sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
		}
	}
	printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
	mutex_unlock(&ht->mutex);

	return cnt;
}

static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
				  int cnt, bool slow)
{
	struct rhltable rhlt;
	unsigned int i, ret;
	const char *key;
	int err = 0;

	err = rhltable_init(&rhlt, &test_rht_params_dup);
	if (WARN_ON(err))
		return err;

	for (i = 0; i < cnt; i++) {
		rhl_test_objects[i].value.tid = i;
		key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead);
		key += test_rht_params_dup.key_offset;

		if (slow) {
			err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key,
							     &rhl_test_objects[i].list_node.rhead));
			if (err == -EAGAIN)
				err = 0;
		} else
			err = rhltable_insert(&rhlt,
					      &rhl_test_objects[i].list_node,
					      test_rht_params_dup);
		if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
			goto skip_print;
	}

	ret = print_ht(&rhlt);
	WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");

skip_print:
	rhltable_destroy(&rhlt);

	return 0;
}

static int __init test_insert_duplicates_run(void)
{
	struct test_obj_rhl rhl_test_objects[3] = {};

	pr_info("test inserting duplicates\n");

	/* two different values that map to same bucket */
	rhl_test_objects[0].value.id = 1;
	rhl_test_objects[1].value.id = 21;

	/* and another duplicate with same as [0] value
	 * which will be second on the bucket list */
	rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;

	test_insert_dup(rhl_test_objects, 2, false);
	test_insert_dup(rhl_test_objects, 3, false);
	test_insert_dup(rhl_test_objects, 2, true);
	test_insert_dup(rhl_test_objects, 3, true);

	return 0;
}

static int thread_lookup_test(struct thread_data *tdata)
{
	unsigned int entries = tdata->entries;
	int i, err = 0;

	for (i = 0; i < entries; i++) {
		struct test_obj *obj;
		struct test_obj_val key = {
			.id = i,
			.tid = tdata->id,
		};

		obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
		if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
			pr_err("  found unexpected object %d-%d\n", key.tid, key.id);
			err++;
		} else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
			pr_err("  object %d-%d not found!\n", key.tid, key.id);
			err++;
		} else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
			pr_err("  wrong object returned (got %d-%d, expected %d-%d)\n",
			       obj->value.tid, obj->value.id, key.tid, key.id);
			err++;
		}

		cond_resched();
	}
	return err;
}

static int threadfunc(void *data)
{
	int i, step, err = 0, insert_retries = 0;
	struct thread_data *tdata = data;

	up(&prestart_sem);
	if (down_interruptible(&startup_sem))
		pr_err("  thread[%d]: down_interruptible failed\n", tdata->id);

	for (i = 0; i < tdata->entries; i++) {
		tdata->objs[i].value.id = i;
		tdata->objs[i].value.tid = tdata->id;
		err = insert_retry(&ht, &tdata->objs[i], test_rht_params);
		if (err > 0) {
			insert_retries += err;
		} else if (err) {
			pr_err("  thread[%d]: rhashtable_insert_fast failed\n",
			       tdata->id);
			goto out;
		}
	}
	if (insert_retries)
		pr_info("  thread[%d]: %u insertions retried due to memory pressure\n",
			tdata->id, insert_retries);

	err = thread_lookup_test(tdata);
	if (err) {
		pr_err("  thread[%d]: rhashtable_lookup_test failed\n",
		       tdata->id);
		goto out;
	}

	for (step = 10; step > 0; step--) {
		for (i = 0; i < tdata->entries; i += step) {
			if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
				continue;
			err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
			                             test_rht_params);
			if (err) {
				pr_err("  thread[%d]: rhashtable_remove_fast failed\n",
				       tdata->id);
				goto out;
			}
			tdata->objs[i].value.id = TEST_INSERT_FAIL;

			cond_resched();
		}
		err = thread_lookup_test(tdata);
		if (err) {
			pr_err("  thread[%d]: rhashtable_lookup_test (2) failed\n",
			       tdata->id);
			goto out;
		}
	}
out:
	while (!kthread_should_stop()) {
		set_current_state(TASK_INTERRUPTIBLE);
		schedule();
	}
	return err;
}

static int __init test_rht_init(void)
{
	unsigned int entries;
	int i, err, started_threads = 0, failed_threads = 0;
	u64 total_time = 0;
	struct thread_data *tdata;
	struct test_obj *objs;

	if (parm_entries < 0)
		parm_entries = 1;

	entries = min(parm_entries, MAX_ENTRIES);

	test_rht_params.automatic_shrinking = shrinking;
	test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
	test_rht_params.nelem_hint = size;

	objs = vzalloc(array_size(sizeof(struct test_obj),
				  test_rht_params.max_size + 1));
	if (!objs)
		return -ENOMEM;

	pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
		size, max_size, shrinking);

	for (i = 0; i < runs; i++) {
		s64 time;

		pr_info("Test %02d:\n", i);
		memset(objs, 0, test_rht_params.max_size * sizeof(struct test_obj));

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

		time = test_rhashtable(&ht, objs, entries);
		rhashtable_destroy(&ht);
		if (time < 0) {
			vfree(objs);
			pr_warn("Test failed: return code %lld\n", time);
			return -EINVAL;
		}

		total_time += time;
	}

	pr_info("test if its possible to exceed max_size %d: %s\n",
			test_rht_params.max_size, test_rhashtable_max(objs, entries) == 0 ?
			"no, ok" : "YES, failed");
	vfree(objs);

	do_div(total_time, runs);
	pr_info("Average test time: %llu\n", total_time);

	test_insert_duplicates_run();

	if (!tcount)
		return 0;

	pr_info("Testing concurrent rhashtable access from %d threads\n",
	        tcount);
	sema_init(&prestart_sem, 1 - tcount);
	tdata = vzalloc(array_size(tcount, sizeof(struct thread_data)));
	if (!tdata)
		return -ENOMEM;
	objs  = vzalloc(array3_size(sizeof(struct test_obj), tcount, entries));
	if (!objs) {
		vfree(tdata);
		return -ENOMEM;
	}

	test_rht_params.max_size = max_size ? :
	                           roundup_pow_of_two(tcount * entries);
	err = rhashtable_init(&ht, &test_rht_params);
	if (err < 0) {
		pr_warn("Test failed: Unable to initialize hashtable: %d\n",
			err);
		vfree(tdata);
		vfree(objs);
		return -EINVAL;
	}
	for (i = 0; i < tcount; i++) {
		tdata[i].id = i;
		tdata[i].entries = entries;
		tdata[i].objs = objs + i * entries;
		tdata[i].task = kthread_run(threadfunc, &tdata[i],
		                            "rhashtable_thrad[%d]", i);
		if (IS_ERR(tdata[i].task))
			pr_err(" kthread_run failed for thread %d\n", i);
		else
			started_threads++;
	}
	if (down_interruptible(&prestart_sem))
		pr_err("  down interruptible failed\n");
	for (i = 0; i < tcount; i++)
		up(&startup_sem);
	for (i = 0; i < tcount; i++) {
		if (IS_ERR(tdata[i].task))
			continue;
		if ((err = kthread_stop(tdata[i].task))) {
			pr_warn("Test failed: thread %d returned: %d\n",
			        i, err);
			failed_threads++;
		}
	}
	rhashtable_destroy(&ht);
	vfree(tdata);
	vfree(objs);

	/*
	 * rhltable_remove is very expensive, default values can cause test
	 * to run for 2 minutes or more,  use a smaller number instead.
	 */
	err = test_rhltable(entries / 16);
	pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
	        started_threads, failed_threads, err);
	return 0;
}

static void __exit test_rht_exit(void)
{
}

module_init(test_rht_init);
module_exit(test_rht_exit);

MODULE_LICENSE("GPL v2");