libsepol: include length squared in hashtab_hash_eval()
PATCH 1/5 libsepol: include length squared in hashtab_hash_eval()
Include the chain length squared sum as metric in the debug function hashtab_hash_eval(), adopted from the kernel avtab.
--- libsepol/src/hashtab.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-)
libsepol/src/hashtab.c +6 -3
@@ -243,11 +243,12 @@ int hashtab_map(hashtab_t h,void hashtab_hash_eval (hashtab_t h,const char *tag) {unsigned int i; -size_t chain_len, slots_used, max_chain_len; +size_t chain_len, slots_used, max_chain_len, chain2_len_sum;hashtab_ptr_t cur; slots_used =0 ; max_chain_len =0 ; + chain2_len_sum =0 ;for (i =0 ; i < h->size; i++) { cur = h->htable[i];if (cur) {
@@ -260,10 +261,12 @@ void hashtab_hash_eval(hashtab_t h, const char *tag)if (chain_len > max_chain_len) max_chain_len = chain_len; + chain2_len_sum += chain_len * chain_len; } }printf - ("%s: %d entries and %zu/%d buckets used, longest chain length %zu\n" , - tag, h->nel, slots_used, h->size, max_chain_len); + ("%s: %d entries and %zu/%d buckets used, longest chain length %zu, chain length^2 %zu, normalized chain length^2 %.2f\n" , + tag, h->nel, slots_used, h->size, max_chain_len, chain2_len_sum, + chain2_len_sum ? (float )chain2_len_sum / slots_used :0 ); }
Signature · 1 line
2.40.1
PATCH 2/5 libsepol: use DJB2a string hash function
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--- libsepol/src/symtab.c | 18 +++++++----------- 1 file changed, 7 insertions(+), 11 deletions(-)
libsepol/src/symtab.c +7 -11
@@ -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
Signature · 1 line
2.40.1
PATCH 3/5 libsepol/cil: use DJB2a string hash function
In reply to Christian GöttscheThe 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 dssp5:
# Current
Time (mean ± σ): 1.347 s ± 0.065 s [User: 1.207 s, System: 0.138 s]
Range (min … max): 1.274 s … 1.436 s 10 runs
# Patch
Time (mean ± σ): 1.336 s ± 0.029 s [User: 1.195 s, System: 0.140 s]
Range (min … max): 1.303 s … 1.376 s 10 runs--- libsepol/cil/src/cil_strpool.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-)
libsepol/cil/src/cil_strpool.c +6 -9
@@ -47,16 +47,13 @@ static hashtab_t cil_strpool_tab = NULL;static unsigned int cil_strpool_hash (hashtab_t h,const_hashtab_key_t key) { -const char *p; -size_t size; -unsigned int val; +unsigned int hash =5381 ; +unsigned char c; - val =0 ; - size =strlen (key); -for (p = key; ((size_t ) (p - key)) < size; p++) - val = - (val <<4 | (val >> (8 *sizeof (unsigned int ) -4 ))) ^ (*p); -return val & (h->size -1 ); +while ((c = *(unsigned const char *)key++)) + hash = ((hash <<5 ) + hash) ^ c; + +return hash & (h->size -1 ); }static int cil_strpool_compare (hashtab_t h __attribute__ ((unused)),const_hashtab_key_t key1,const_hashtab_key_t key2)
Signature · 1 line
2.40.1
PATCH 4/5 libselinux: use DJB2a string hash function
In reply to Christian GöttscheThe 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.
--- libselinux/src/avc_sidtab.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-)
libselinux/src/avc_sidtab.c +7 -10
@@ -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)
Signature · 1 line
2.40.1
PATCH 5/5 newrole: use DJB2a string hash function
In reply to Christian GöttscheThe 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.
--- policycoreutils/newrole/newrole.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-)
policycoreutils/newrole/newrole.c +7 -10
@@ -229,16 +229,13 @@ static int free_hashtab_entry(hashtab_key_t key, hashtab_datum_t d,static unsigned int reqsymhash (hashtab_t h,const_hashtab_key_t key) { -const char *p; -size_t size; -unsigned int val; - - val =0 ; - size =strlen (key); -for (p = key; ((size_t ) (p - key)) < 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 reqsymcmp(hashtab_t h
Signature · 1 line
2.40.1