Skip to content

Commit 6f22c07

Browse files
davem330davem330
committed
Merge branch 'rhltable-dups'
Paul Blakey says: ==================== rhashtable: Fix rhltable duplicates insertion On our mlx5 driver fs_core.c, we use the rhltable interface to store flow groups. We noticed that sometimes we get a warning that flow group isn't found at removal. This rare case was caused when a specific scenario happened, insertion of a flow group with a similar match criteria (a duplicate), but only where the flow group rhash_head was second (or not first) on the relevant rhashtable bucket list. The first patch fixes it, and the second one adds a test that show it is now working. Paul. v3 --> v2 changes: * added missing fix in rhashtable_lookup_one code path as well. v1 --> v2 changes: * Changed commit messages to better reflect the change ==================== Signed-off-by: David S. Miller <davem@davemloft.net>
2 parents 25b5cdf + 499ac3b commit 6f22c07

File tree

3 files changed

+140
-2
lines changed

3 files changed

+140
-2
lines changed

‎include/linux/rhashtable.h

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -766,8 +766,10 @@ static inline void *__rhashtable_insert_fast(
766766
if (!key ||
767767
(params.obj_cmpfn ?
768768
params.obj_cmpfn(&arg, rht_obj(ht, head)) :
769-
rhashtable_compare(&arg, rht_obj(ht, head))))
769+
rhashtable_compare(&arg, rht_obj(ht, head)))) {
770+
pprev = &head->next;
770771
continue;
772+
}
771773

772774
data = rht_obj(ht, head);
773775

‎lib/rhashtable.c

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -506,8 +506,10 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
506506
if (!key ||
507507
(ht->p.obj_cmpfn ?
508508
ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
509-
rhashtable_compare(&arg, rht_obj(ht, head))))
509+
rhashtable_compare(&arg, rht_obj(ht, head)))) {
510+
pprev = &head->next;
510511
continue;
512+
}
511513

512514
if (!ht->rhlist)
513515
return rht_obj(ht, head);

‎lib/test_rhashtable.c

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,21 @@ struct thread_data {
7979
struct test_obj *objs;
8080
};
8181

82+
static u32 my_hashfn(const void *data, u32 len, u32 seed)
83+
{
84+
const struct test_obj_rhl *obj = data;
85+
86+
return (obj->value.id % 10) << RHT_HASH_RESERVED_SPACE;
87+
}
88+
89+
static int my_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
90+
{
91+
const struct test_obj_rhl *test_obj = obj;
92+
const struct test_obj_val *val = arg->key;
93+
94+
return test_obj->value.id - val->id;
95+
}
96+
8297
static struct rhashtable_params test_rht_params = {
8398
.head_offset = offsetof(struct test_obj, node),
8499
.key_offset = offsetof(struct test_obj, value),
@@ -87,6 +102,17 @@ static struct rhashtable_params test_rht_params = {
87102
.nulls_base = (3U << RHT_BASE_SHIFT),
88103
};
89104

105+
static struct rhashtable_params test_rht_params_dup = {
106+
.head_offset = offsetof(struct test_obj_rhl, list_node),
107+
.key_offset = offsetof(struct test_obj_rhl, value),
108+
.key_len = sizeof(struct test_obj_val),
109+
.hashfn = jhash,
110+
.obj_hashfn = my_hashfn,
111+
.obj_cmpfn = my_cmpfn,
112+
.nelem_hint = 128,
113+
.automatic_shrinking = false,
114+
};
115+
90116
static struct semaphore prestart_sem;
91117
static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);
92118

@@ -465,6 +491,112 @@ static int __init test_rhashtable_max(struct test_obj *array,
465491
return err;
466492
}
467493

494+
static unsigned int __init print_ht(struct rhltable *rhlt)
495+
{
496+
struct rhashtable *ht;
497+
const struct bucket_table *tbl;
498+
char buff[512] = "";
499+
unsigned int i, cnt = 0;
500+
501+
ht = &rhlt->ht;
502+
tbl = rht_dereference(ht->tbl, ht);
503+
for (i = 0; i < tbl->size; i++) {
504+
struct rhash_head *pos, *next;
505+
struct test_obj_rhl *p;
506+
507+
pos = rht_dereference(tbl->buckets[i], ht);
508+
next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
509+
510+
if (!rht_is_a_nulls(pos)) {
511+
sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
512+
}
513+
514+
while (!rht_is_a_nulls(pos)) {
515+
struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
516+
sprintf(buff, "%s[[", buff);
517+
do {
518+
pos = &list->rhead;
519+
list = rht_dereference(list->next, ht);
520+
p = rht_obj(ht, pos);
521+
522+
sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
523+
list? ", " : " ");
524+
cnt++;
525+
} while (list);
526+
527+
pos = next,
528+
next = !rht_is_a_nulls(pos) ?
529+
rht_dereference(pos->next, ht) : NULL;
530+
531+
sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
532+
}
533+
}
534+
printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
535+
536+
return cnt;
537+
}
538+
539+
static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
540+
int cnt, bool slow)
541+
{
542+
struct rhltable rhlt;
543+
unsigned int i, ret;
544+
const char *key;
545+
int err = 0;
546+
547+
err = rhltable_init(&rhlt, &test_rht_params_dup);
548+
if (WARN_ON(err))
549+
return err;
550+
551+
for (i = 0; i < cnt; i++) {
552+
rhl_test_objects[i].value.tid = i;
553+
key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead);
554+
key += test_rht_params_dup.key_offset;
555+
556+
if (slow) {
557+
err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key,
558+
&rhl_test_objects[i].list_node.rhead));
559+
if (err == -EAGAIN)
560+
err = 0;
561+
} else
562+
err = rhltable_insert(&rhlt,
563+
&rhl_test_objects[i].list_node,
564+
test_rht_params_dup);
565+
if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
566+
goto skip_print;
567+
}
568+
569+
ret = print_ht(&rhlt);
570+
WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
571+
572+
skip_print:
573+
rhltable_destroy(&rhlt);
574+
575+
return 0;
576+
}
577+
578+
static int __init test_insert_duplicates_run(void)
579+
{
580+
struct test_obj_rhl rhl_test_objects[3] = {};
581+
582+
pr_info("test inserting duplicates\n");
583+
584+
/* two different values that map to same bucket */
585+
rhl_test_objects[0].value.id = 1;
586+
rhl_test_objects[1].value.id = 21;
587+
588+
/* and another duplicate with same as [0] value
589+
* which will be second on the bucket list */
590+
rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;
591+
592+
test_insert_dup(rhl_test_objects, 2, false);
593+
test_insert_dup(rhl_test_objects, 3, false);
594+
test_insert_dup(rhl_test_objects, 2, true);
595+
test_insert_dup(rhl_test_objects, 3, true);
596+
597+
return 0;
598+
}
599+
468600
static int thread_lookup_test(struct thread_data *tdata)
469601
{
470602
unsigned int entries = tdata->entries;
@@ -613,6 +745,8 @@ static int __init test_rht_init(void)
613745
do_div(total_time, runs);
614746
pr_info("Average test time: %llu\n", total_time);
615747

748+
test_insert_duplicates_run();
749+
616750
if (!tcount)
617751
return 0;
618752

0 commit comments

Comments
 (0)