diff options
| author | Francois Dumontet <francois.dumontet@6wind.com> | 2022-10-04 16:26:19 +0200 |
|---|---|---|
| committer | David Lamparter <equinox@opensourcerouting.org> | 2022-10-06 15:09:15 +0200 |
| commit | 5e0136c94f4018a77e0e77c6dfbb705d516eec80 (patch) | |
| tree | dc008c39c816e21148c349fdcbf6df33274d603b /lib/typesafe.h | |
| parent | 4b72a7be697fcd69b0d17ebc5b28bb2b0fe55e0d (diff) | |
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 <francois.dumontet@6wind.com>
[DL: rewrote commit message, fixed whitespace/formatting]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Diffstat (limited to 'lib/typesafe.h')
| -rw-r--r-- | lib/typesafe.h | 9 |
1 files 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; \ |