test_rhashtable.c (188933ac139a6f8ab06cad369bd0200af947b00d) test_rhashtable.c (b824478b2145be78ac19e1cf44e2b9036c7a9608)
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

--- 24 unchanged lines hidden (view full) ---

33#define TEST_NEXPANDS 4
34
35struct test_obj {
36 void *ptr;
37 int value;
38 struct rhash_head node;
39};
40
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

--- 24 unchanged lines hidden (view full) ---

33#define TEST_NEXPANDS 4
34
35struct test_obj {
36 void *ptr;
37 int value;
38 struct rhash_head node;
39};
40
41static 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,
47 .max_size = 2, /* we expand/shrink manually here */
48 .nulls_base = (3U << RHT_BASE_SHIFT),
49};
50
41static int __init test_rht_lookup(struct rhashtable *ht)
42{
43 unsigned int i;
44
45 for (i = 0; i < TEST_ENTRIES * 2; i++) {
46 struct test_obj *obj;
47 bool expected = !(i % 2);
48 u32 key = i;
49
51static int __init test_rht_lookup(struct rhashtable *ht)
52{
53 unsigned int i;
54
55 for (i = 0; i < TEST_ENTRIES * 2; i++) {
56 struct test_obj *obj;
57 bool expected = !(i % 2);
58 u32 key = i;
59
50 obj = rhashtable_lookup(ht, &key);
60 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
51
52 if (expected && !obj) {
53 pr_warn("Test failed: Could not find key %u\n", key);
54 return -ENOENT;
55 } else if (!expected && obj) {
56 pr_warn("Test failed: Unexpected entry found for key %u\n",
57 key);
58 return -EEXIST;

--- 16 unchanged lines hidden (view full) ---

75 struct test_obj *obj;
76 struct bucket_table *tbl;
77
78 tbl = rht_dereference_rcu(ht->tbl, ht);
79 for (i = 0; i < tbl->size; i++) {
80 rcu_cnt = cnt = 0;
81
82 if (!quiet)
61
62 if (expected && !obj) {
63 pr_warn("Test failed: Could not find key %u\n", key);
64 return -ENOENT;
65 } else if (!expected && obj) {
66 pr_warn("Test failed: Unexpected entry found for key %u\n",
67 key);
68 return -EEXIST;

--- 16 unchanged lines hidden (view full) ---

85 struct test_obj *obj;
86 struct bucket_table *tbl;
87
88 tbl = rht_dereference_rcu(ht->tbl, ht);
89 for (i = 0; i < tbl->size; i++) {
90 rcu_cnt = cnt = 0;
91
92 if (!quiet)
83 pr_info(" [%#4x/%zu]", i, tbl->size);
93 pr_info(" [%#4x/%u]", i, tbl->size);
84
85 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
86 cnt++;
87 total++;
88 if (!quiet)
89 pr_cont(" [%p],", obj);
90 }
91

--- 36 unchanged lines hidden (view full) ---

128 if (!obj) {
129 err = -ENOMEM;
130 goto error;
131 }
132
133 obj->ptr = TEST_PTR;
134 obj->value = i * 2;
135
94
95 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
96 cnt++;
97 total++;
98 if (!quiet)
99 pr_cont(" [%p],", obj);
100 }
101

--- 36 unchanged lines hidden (view full) ---

138 if (!obj) {
139 err = -ENOMEM;
140 goto error;
141 }
142
143 obj->ptr = TEST_PTR;
144 obj->value = i * 2;
145
136 rhashtable_insert(ht, &obj->node);
146 err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
147 if (err) {
148 kfree(obj);
149 goto error;
150 }
137 }
138
139 rcu_read_lock();
140 test_bucket_stats(ht, true);
141 test_rht_lookup(ht);
142 rcu_read_unlock();
143
151 }
152
153 rcu_read_lock();
154 test_bucket_stats(ht, true);
155 test_rht_lookup(ht);
156 rcu_read_unlock();
157
144 for (i = 0; i < TEST_NEXPANDS; i++) {
145 pr_info(" Table expansion iteration %u...\n", i);
146 mutex_lock(&ht->mutex);
147 rhashtable_expand(ht);
148 mutex_unlock(&ht->mutex);
149
150 rcu_read_lock();
151 pr_info(" Verifying lookups...\n");
152 test_rht_lookup(ht);
153 rcu_read_unlock();
154 }
155
156 for (i = 0; i < TEST_NEXPANDS; i++) {
157 pr_info(" Table shrinkage iteration %u...\n", i);
158 mutex_lock(&ht->mutex);
159 rhashtable_shrink(ht);
160 mutex_unlock(&ht->mutex);
161
162 rcu_read_lock();
163 pr_info(" Verifying lookups...\n");
164 test_rht_lookup(ht);
165 rcu_read_unlock();
166 }
167
168 rcu_read_lock();
169 test_bucket_stats(ht, true);
170 rcu_read_unlock();
171
172 pr_info(" Deleting %d keys\n", TEST_ENTRIES);
173 for (i = 0; i < TEST_ENTRIES; i++) {
174 u32 key = i * 2;
175
158 rcu_read_lock();
159 test_bucket_stats(ht, true);
160 rcu_read_unlock();
161
162 pr_info(" Deleting %d keys\n", TEST_ENTRIES);
163 for (i = 0; i < TEST_ENTRIES; i++) {
164 u32 key = i * 2;
165
176 obj = rhashtable_lookup(ht, &key);
166 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
177 BUG_ON(!obj);
178
167 BUG_ON(!obj);
168
179 rhashtable_remove(ht, &obj->node);
169 rhashtable_remove_fast(ht, &obj->node, test_rht_params);
180 kfree(obj);
181 }
182
183 return 0;
184
185error:
186 tbl = rht_dereference_rcu(ht->tbl, ht);
187 for (i = 0; i < tbl->size; i++)
188 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
189 kfree(obj);
190
191 return err;
192}
193
194static struct rhashtable ht;
195
196static int __init test_rht_init(void)
197{
170 kfree(obj);
171 }
172
173 return 0;
174
175error:
176 tbl = rht_dereference_rcu(ht->tbl, ht);
177 for (i = 0; i < tbl->size; i++)
178 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
179 kfree(obj);
180
181 return err;
182}
183
184static struct rhashtable ht;
185
186static int __init test_rht_init(void)
187{
198 struct rhashtable_params params = {
199 .nelem_hint = TEST_HT_SIZE,
200 .head_offset = offsetof(struct test_obj, node),
201 .key_offset = offsetof(struct test_obj, value),
202 .key_len = sizeof(int),
203 .hashfn = jhash,
204 .max_shift = 1, /* we expand/shrink manually here */
205 .nulls_base = (3U << RHT_BASE_SHIFT),
206 };
207 int err;
208
209 pr_info("Running resizable hashtable tests...\n");
210
188 int err;
189
190 pr_info("Running resizable hashtable tests...\n");
191
211 err = rhashtable_init(&ht, &params);
192 err = rhashtable_init(&ht, &test_rht_params);
212 if (err < 0) {
213 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
214 err);
215 return err;
216 }
217
218 err = test_rhashtable(&ht);
219

--- 13 unchanged lines hidden --- 		193 if (err < 0) {
194 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
195 err);
196 return err;
197 }
198
199 err = test_rhashtable(&ht);
200

--- 13 unchanged lines hidden ---