The hash table implementation uses `& (h->size - 1)` to truncate
generated hashes to the number of buckets. This operation is equal to
`% h->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.
Benchmark of building Reference Policy:
# Current
Benchmark 1: /tmp/destdir/usr/bin/checkpolicy -c 33 -U deny -S -O -E policy.conf -o policy.33
Time (mean ± σ): 2.521 s ± 0.025 s [User: 2.442 s, System: 0.076 s]
Range (min … max): 2.467 s … 2.550 s 10 runs
# Patch
Benchmark 1: /tmp/destdir/usr/bin/checkpolicy -c 33 -U deny -S -O -E policy.conf -o policy.33
Time (mean ± σ): 2.385 s ± 0.031 s [User: 2.303 s, System: 0.081 s]
Range (min … max): 2.353 s … 2.446 s 10 runs
Signed-off-by: Christian Göttsche <cgzones@xxxxxxxxxxxxxx>
---
libsepol/src/symtab.c | 18 +++++++-----------
1 file changed, 7 insertions(+), 11 deletions(-)
diff --git a/libsepol/src/symtab.c b/libsepol/src/symtab.c
index 78567dbf..4b45c549 100644
--- a/libsepol/src/symtab.c
+++ b/libsepol/src/symtab.c
@@ -17,17 +17,13 @@
ignore_unsigned_overflow_
static unsigned int symhash(hashtab_t h, const_hashtab_key_t key)
{
- const char *p, *keyp;
- size_t size;
- unsigned int val;
-
- val = 0;
- keyp = (const char *)key;
- size = strlen(keyp);
- for (p = keyp; ((size_t) (p - keyp)) < size; p++)
- val =
- (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p);
- return val & (h->size - 1);
+ unsigned int hash = 5381;
+ unsigned char c;
+
+ while ((c = *(unsigned const char *)key++))
+ hash = ((hash << 5) + hash) ^ c;
+
+ return hash & (h->size - 1);
}
static int symcmp(hashtab_t h
--
2.40.1
