The hash table implementation uses `& (SIDTAB_SIZE - 1)` to truncate
generated hashes to the number of buckets. This operation is equal to
`% SIDTAB_SIZE` if and only if the size is a power of two (which seems
to be always the case). One property of the binary and with a power of
two (and probably a small one <=2048) is all higher bits are discarded.
Thus a hash function is needed with a good avalanche effect, which the
current one is not.
Signed-off-by: Christian Göttsche <cgzones@xxxxxxxxxxxxxx>
---
libselinux/src/avc_sidtab.c | 17 +++++++----------
1 file changed, 7 insertions(+), 10 deletions(-)
diff --git a/libselinux/src/avc_sidtab.c b/libselinux/src/avc_sidtab.c
index f179d855..e396a938 100644
--- a/libselinux/src/avc_sidtab.c
+++ b/libselinux/src/avc_sidtab.c
@@ -15,16 +15,13 @@
static inline unsigned sidtab_hash(const char * key)
{
- const char *p;
- unsigned int size;
- unsigned int val;
-
- val = 0;
- size = strlen(key);
- for (p = key; (unsigned int)(p - key) < size; p++)
- val =
- (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p);
- return val & (SIDTAB_SIZE - 1);
+ unsigned int hash = 5381;
+ unsigned char c;
+
+ while ((c = *(unsigned const char *)key++))
+ hash = ((hash << 5) + hash) ^ c;
+
+ return hash & (SIDTAB_SIZE - 1);
}
int sidtab_init(struct sidtab *s)
--
2.40.1
