blob: b2957540d3c722d5c7b3d9f94e5b5a1d6c9d7975 [file] [log] [blame]
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +01001/*
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
35struct test_obj {
36 void *ptr;
37 int value;
38 struct rhash_head node;
39};
40
Herbert Xub182aa62015-03-20 21:57:04 +110041static 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,
Herbert Xub182aa62015-03-20 21:57:04 +110047 .nulls_base = (3U << RHT_BASE_SHIFT),
48};
49
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +010050static 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
Herbert Xub182aa62015-03-20 21:57:04 +110059 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +010060
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
80static 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)
Herbert Xu63d512d2015-03-14 13:57:24 +110092 pr_info(" [%#4x/%u]", i, tbl->size);
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +010093
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
120static 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
Herbert Xub182aa62015-03-20 21:57:04 +1100145 err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
146 if (err) {
147 kfree(obj);
148 goto error;
149 }
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100150 }
151
152 rcu_read_lock();
153 test_bucket_stats(ht, true);
154 test_rht_lookup(ht);
155 rcu_read_unlock();
156
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100157 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
Herbert Xub182aa62015-03-20 21:57:04 +1100165 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100166 BUG_ON(!obj);
167
Herbert Xub182aa62015-03-20 21:57:04 +1100168 rhashtable_remove_fast(ht, &obj->node, test_rht_params);
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100169 kfree(obj);
170 }
171
172 return 0;
173
174error:
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
Daniel Borkmannb7f5e5c2015-02-20 21:14:21 +0100183static struct rhashtable ht;
184
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100185static int __init test_rht_init(void)
186{
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100187 int err;
188
189 pr_info("Running resizable hashtable tests...\n");
190
Herbert Xub182aa62015-03-20 21:57:04 +1100191 err = rhashtable_init(&ht, &test_rht_params);
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100192 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
Daniel Borkmann6dd0c162015-02-20 00:53:39 +0100205static void __exit test_rht_exit(void)
206{
207}
208
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100209module_init(test_rht_init);
Daniel Borkmann6dd0c162015-02-20 00:53:39 +0100210module_exit(test_rht_exit);
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +0100211
212MODULE_LICENSE("GPL v2");