]> git.puffer.fish Git - matthieu/frr.git/commit
lib: fix typesafe hash add with hash collision
authorFrancois Dumontet <francois.dumontet@6wind.com>
Tue, 4 Oct 2022 14:26:19 +0000 (16:26 +0200)
committerDavid Lamparter <equinox@opensourcerouting.org>
Thu, 6 Oct 2022 13:09:15 +0000 (15:09 +0200)
commit5e0136c94f4018a77e0e77c6dfbb705d516eec80
treedc008c39c816e21148c349fdcbf6df33274d603b
parent4b72a7be697fcd69b0d17ebc5b28bb2b0fe55e0d
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>
lib/typesafe.h