From 5e0136c94f4018a77e0e77c6dfbb705d516eec80 Mon Sep 17 00:00:00 2001 From: Francois Dumontet Date: Tue, 4 Oct 2022 16:26:19 +0200 Subject: [PATCH] lib: fix typesafe hash add with hash collision The typesafe hash data structure enforces items to be unique, but their hash values may still collide. To this extent, when two items have the same hash value, the compare function is called to see if it returns 0 (aka "equal"). While the _find() function handles this correctly, the _add() function mistakenly only checked the first item with a colliding hash value for equality, and if it was inequal proceeded to add the new item. There may however be additional items with the same hash value collision, one of which could still compare as equal. In that case, _add() would mistakenly add the new element, failing to notice the already added item. Breakage ensues. Fix by looking for an equal element among *all* existing items with the same hash value, not just the first. Signed-off-by: Francois Dumontet [DL: rewrote commit message, fixed whitespace/formatting] Signed-off-by: David Lamparter --- lib/typesafe.h | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/lib/typesafe.h b/lib/typesafe.h index 50c410ad24..8aeabb34e6 100644 --- a/lib/typesafe.h +++ b/lib/typesafe.h @@ -850,9 +850,12 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ struct thash_item **np = &h->hh.entries[hbits]; \ while (*np && (*np)->hashval < hval) \ np = &(*np)->next; \ - if (*np && cmpfn(container_of(*np, type, field.hi), item) == 0) { \ - h->hh.count--; \ - return container_of(*np, type, field.hi); \ + while (*np && (*np)->hashval == hval) { \ + if (cmpfn(container_of(*np, type, field.hi), item) == 0) { \ + h->hh.count--; \ + return container_of(*np, type, field.hi); \ + } \ + np = &(*np)->next; \ } \ item->field.hi.next = *np; \ *np = &item->field.hi; \ -- 2.39.5