Skip to contentSkip to conversation

libsepol: include length squared in hashtab_hash_eval()

PATCH New Christian Göttsche 1 participant 5 messages Aug 16, 2023 SELinux security module

lore
Share & tools
lore
#0 lore raw

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
index b1a9bdc2..2af3a9bf 100644
@@ -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
#1 lore raw

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
index 78567dbf..4b45c549 100644
@@ -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
#2 lore raw

PATCH 3/5 libsepol/cil: use DJB2a string hash function

In reply to Christian Göttsche

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 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
index e32ee4e9..beea5c9d 100644
@@ -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
#3 lore raw

PATCH 4/5 libselinux: use DJB2a string hash function

In reply to Christian Göttsche

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.

---
 libselinux/src/avc_sidtab.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)
libselinux/src/avc_sidtab.c +7 -10
index f179d855..e396a938 100644
@@ -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
#4 lore raw

PATCH 5/5 newrole: use DJB2a string hash function

In reply to Christian Göttsche

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.

---
 policycoreutils/newrole/newrole.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)
policycoreutils/newrole/newrole.c +7 -10
index d9efa68a..5a1a1129 100644
@@ -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