Skip to content

Commit cdd4de3

Browse files
Florian Westphaldavem330
Florian Westphal
authored and
davem330
committed
test_rhashtable: add test case for rhl_table interface
also test rhltable. rhltable remove operations are slow as deletions require a list walk, thus test with 1/16th of the given entry count number to get a run duration similar to rhashtable one. Signed-off-by: Florian Westphal <fw@strlen.de> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent a6359bd commit cdd4de3

File tree

1 file changed

+194
-2
lines changed

1 file changed

+194
-2
lines changed

‎lib/test_rhashtable.c

Lines changed: 194 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
#include <linux/semaphore.h>
2424
#include <linux/slab.h>
2525
#include <linux/sched.h>
26+
#include <linux/random.h>
2627
#include <linux/vmalloc.h>
2728

2829
#define MAX_ENTRIES 1000000
@@ -66,6 +67,11 @@ struct test_obj {
6667
struct rhash_head node;
6768
};
6869

70+
struct test_obj_rhl {
71+
struct test_obj_val value;
72+
struct rhlist_head list_node;
73+
};
74+
6975
struct thread_data {
7076
unsigned int entries;
7177
int id;
@@ -245,6 +251,186 @@ static s64 __init test_rhashtable(struct rhashtable *ht, struct test_obj *array,
245251
}
246252

247253
static struct rhashtable ht;
254+
static struct rhltable rhlt __initdata;
255+
256+
static int __init test_rhltable(unsigned int entries)
257+
{
258+
struct test_obj_rhl *rhl_test_objects;
259+
unsigned long *obj_in_table;
260+
unsigned int i, j, k;
261+
int ret, err;
262+
263+
if (entries == 0)
264+
entries = 1;
265+
266+
rhl_test_objects = vzalloc(sizeof(*rhl_test_objects) * entries);
267+
if (!rhl_test_objects)
268+
return -ENOMEM;
269+
270+
ret = -ENOMEM;
271+
obj_in_table = vzalloc(BITS_TO_LONGS(entries) * sizeof(unsigned long));
272+
if (!obj_in_table)
273+
goto out_free;
274+
275+
/* nulls_base not supported in rhlist interface */
276+
test_rht_params.nulls_base = 0;
277+
err = rhltable_init(&rhlt, &test_rht_params);
278+
if (WARN_ON(err))
279+
goto out_free;
280+
281+
k = prandom_u32();
282+
ret = 0;
283+
for (i = 0; i < entries; i++) {
284+
rhl_test_objects[i].value.id = k;
285+
err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
286+
test_rht_params);
287+
if (WARN(err, "error %d on element %d\n", err, i))
288+
break;
289+
if (err == 0)
290+
set_bit(i, obj_in_table);
291+
}
292+
293+
if (err)
294+
ret = err;
295+
296+
pr_info("test %d add/delete pairs into rhlist\n", entries);
297+
for (i = 0; i < entries; i++) {
298+
struct rhlist_head *h, *pos;
299+
struct test_obj_rhl *obj;
300+
struct test_obj_val key = {
301+
.id = k,
302+
};
303+
bool found;
304+
305+
rcu_read_lock();
306+
h = rhltable_lookup(&rhlt, &key, test_rht_params);
307+
if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
308+
rcu_read_unlock();
309+
break;
310+
}
311+
312+
if (i) {
313+
j = i - 1;
314+
rhl_for_each_entry_rcu(obj, pos, h, list_node) {
315+
if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
316+
break;
317+
}
318+
}
319+
320+
cond_resched_rcu();
321+
322+
found = false;
323+
324+
rhl_for_each_entry_rcu(obj, pos, h, list_node) {
325+
if (pos == &rhl_test_objects[i].list_node) {
326+
found = true;
327+
break;
328+
}
329+
}
330+
331+
rcu_read_unlock();
332+
333+
if (WARN(!found, "element %d not found", i))
334+
break;
335+
336+
err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
337+
WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
338+
if (err == 0)
339+
clear_bit(i, obj_in_table);
340+
}
341+
342+
if (ret == 0 && err)
343+
ret = err;
344+
345+
for (i = 0; i < entries; i++) {
346+
WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);
347+
348+
err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
349+
test_rht_params);
350+
if (WARN(err, "error %d on element %d\n", err, i))
351+
break;
352+
if (err == 0)
353+
set_bit(i, obj_in_table);
354+
}
355+
356+
pr_info("test %d random rhlist add/delete operations\n", entries);
357+
for (j = 0; j < entries; j++) {
358+
u32 i = prandom_u32_max(entries);
359+
u32 prand = prandom_u32();
360+
361+
cond_resched();
362+
363+
if (prand == 0)
364+
prand = prandom_u32();
365+
366+
if (prand & 1) {
367+
prand >>= 1;
368+
continue;
369+
}
370+
371+
err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
372+
if (test_bit(i, obj_in_table)) {
373+
clear_bit(i, obj_in_table);
374+
if (WARN(err, "cannot remove element at slot %d", i))
375+
continue;
376+
} else {
377+
if (WARN(err != -ENOENT, "removed non-existant element %d, error %d not %d",
378+
i, err, -ENOENT))
379+
continue;
380+
}
381+
382+
if (prand & 1) {
383+
prand >>= 1;
384+
continue;
385+
}
386+
387+
err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
388+
if (err == 0) {
389+
if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
390+
continue;
391+
} else {
392+
if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
393+
continue;
394+
}
395+
396+
if (prand & 1) {
397+
prand >>= 1;
398+
continue;
399+
}
400+
401+
i = prandom_u32_max(entries);
402+
if (test_bit(i, obj_in_table)) {
403+
err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
404+
WARN(err, "cannot remove element at slot %d", i);
405+
if (err == 0)
406+
clear_bit(i, obj_in_table);
407+
} else {
408+
err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
409+
WARN(err, "failed to insert object %d", i);
410+
if (err == 0)
411+
set_bit(i, obj_in_table);
412+
}
413+
}
414+
415+
for (i = 0; i < entries; i++) {
416+
cond_resched();
417+
err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
418+
if (test_bit(i, obj_in_table)) {
419+
if (WARN(err, "cannot remove element at slot %d", i))
420+
continue;
421+
} else {
422+
if (WARN(err != -ENOENT, "removed non-existant element, error %d not %d",
423+
err, -ENOENT))
424+
continue;
425+
}
426+
}
427+
428+
rhltable_destroy(&rhlt);
429+
out_free:
430+
vfree(rhl_test_objects);
431+
vfree(obj_in_table);
432+
return ret;
433+
}
248434

249435
static int __init test_rhashtable_max(struct test_obj *array,
250436
unsigned int entries)
@@ -480,11 +666,17 @@ static int __init test_rht_init(void)
480666
failed_threads++;
481667
}
482668
}
483-
pr_info("Started %d threads, %d failed\n",
484-
started_threads, failed_threads);
485669
rhashtable_destroy(&ht);
486670
vfree(tdata);
487671
vfree(objs);
672+
673+
/*
674+
* rhltable_remove is very expensive, default values can cause test
675+
* to run for 2 minutes or more, use a smaller number instead.
676+
*/
677+
err = test_rhltable(entries / 16);
678+
pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
679+
started_threads, failed_threads, err);
488680
return 0;
489681
}
490682

0 commit comments

Comments
 (0)