From: Siarhei Liakh <siarhei.liakh@xxxxxxxxxxxxxxxxx>
This change introduces a median() function which is then used to report
25th, 50th, and 75th percentile metrics within distributions of hash table
bucket chain lengths. This allows to better assess and compare relative
effectiveness of different hash functions. Specifically, it allows to
ensure new functions not only reduce the maximum, but also improve (or, at
least, have no negative impact) on the median.
Sample output before change:
avc:
entries: 508
buckets used: 213/512
longest chain: 10
policydb:
SELinux: roles: 14 entries and 6/16 buckets used, longest chain length 5
Sample output after the change:
avc:
entries: 508
buckets used: 217/512
longest chain: 9
non-zero chain Q1/Med/Q3: 1/2/3
policydb:
SELinux: roles: 14 entries and 6/16 buckets used, longest chain length 5
non-zero Q1/Med/Q3 1/2/4
Signed-off-by: Siarhei Liakh <siarhei.liakh@xxxxxxxxxxxxxxxxx>
---
Please CC me directly on all replies.
security/selinux/Kconfig | 10 +++++
security/selinux/avc.c | 42 ++++++++++++++++---
security/selinux/include/median.h | 67 +++++++++++++++++++++++++++++++
security/selinux/ss/avtab.c | 37 ++++++++++++++---
security/selinux/ss/hashtab.c | 28 ++++++++++++-
security/selinux/ss/hashtab.h | 5 +++
security/selinux/ss/policydb.c | 14 ++++---
7 files changed, 185 insertions(+), 18 deletions(-)
create mode 100644 security/selinux/include/median.h
diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 9e921fc72538..57c427e019c9 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -115,3 +115,13 @@ config SECURITY_SELINUX_SID2STR_CACHE_SIZE
conversion. Setting this option to 0 disables the cache completely.
If unsure, keep the default value.
+
+config SECURITY_SELINUX_DEBUG_HASHES
+ bool "Print additional information about hash tables"
+ depends on SECURITY_SELINUX
+ default n
+ help
+ This option allows to gather and display additional information about
+ some of the key hash tables within SELinux.
+
+ If unsure, keep the default value.
diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index d18cb32a242a..c3bbdb083371 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -31,6 +31,10 @@
#include "avc_ss.h"
#include "classmap.h"
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+#include "median.h"
+#endif
+
#define AVC_CACHE_SLOTS 512
#define AVC_DEF_CACHE_THRESHOLD 512
#define AVC_CACHE_RECLAIM 16
@@ -149,9 +153,13 @@ void __init avc_init(void)
int avc_get_hash_stats(struct selinux_avc *avc, char *page)
{
- int i, chain_len, max_chain_len, slots_used;
+ int i, chain_len, max_chain_len, slots_used, ret;
struct avc_node *node;
struct hlist_head *head;
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ u32 med_ct = 0;
+ u32 *counts = vmalloc(AVC_CACHE_SLOTS * sizeof(u32));
+#endif
rcu_read_lock();
@@ -164,6 +172,10 @@ int avc_get_hash_stats(struct selinux_avc *avc, char *page)
chain_len = 0;
hlist_for_each_entry_rcu(node, head, list)
chain_len++;
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ if (counts && chain_len)
+ counts[med_ct++] = chain_len;
+#endif
if (chain_len > max_chain_len)
max_chain_len = chain_len;
}
@@ -171,10 +183,30 @@ int avc_get_hash_stats(struct selinux_avc *avc, char *page)
rcu_read_unlock();
- return scnprintf(page, PAGE_SIZE, "entries: %d\nbuckets used: %d/%d\n"
- "longest chain: %d\n",
- atomic_read(&avc->avc_cache.active_nodes),
- slots_used, AVC_CACHE_SLOTS, max_chain_len);
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ if (counts) {
+ u32 q1 = 0;
+ u32 q3 = 0;
+ u32 med = median(counts, med_ct, &q1, &q3);
+
+ vfree(counts);
+ ret = scnprintf(page, PAGE_SIZE,
+ "entries: %d\nbuckets used: %d/%d\n"
+ "longest chain: %d\n"
+ "non-zero chain Q1/Med/Q3: %u/%u/%u\n",
+ atomic_read(&avc->avc_cache.active_nodes),
+ slots_used, AVC_CACHE_SLOTS, max_chain_len,
+ q1, med, q3);
+ } else /* Falling through! */
+#endif
+ {
+ ret = scnprintf(page, PAGE_SIZE,
+ "entries: %d\nbuckets used: %d/%d\n"
+ "longest chain: %d\n",
+ atomic_read(&avc->avc_cache.active_nodes),
+ slots_used, AVC_CACHE_SLOTS, max_chain_len);
+ }
+ return ret;
}
/*
diff --git a/security/selinux/include/median.h b/security/selinux/include/median.h
new file mode 100644
index 000000000000..e90565b9d7f6
--- /dev/null
+++ b/security/selinux/include/median.h
@@ -0,0 +1,67 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/* (C) Siarhei Liakh <Siarhei.Liakh@xxxxxxxxxxxxxxxxx>, 2020, GPL 2.0+ */
+
+#ifndef _LINUX_MEDIAN_H
+#define _LINUX_MEDIAN_H
+#include <linux/types.h>
+#include <linux/sort.h>
+
+/*
+ * Helper function to compare two u32s
+ */
+static int __cmp_u32(const void *a, const void *b)
+{
+ u32 x = *(const u32 *)(a);
+ u32 y = *(const u32 *)(b);
+
+ if (x < y)
+ return -1;
+
+ if (x > y)
+ return 1;
+
+ return 0;
+}
+
+/*
+ * median(): Find a median of an array containing "count" of u32s,
+ * optionally return 25th (q1) and 75th (q3) percentile.
+ */
+static inline u32 median(u32 val[], size_t count, u32 *q1, u32 *q3)
+{
+ u32 _q1 = 0;
+ u32 _q2 = 0;
+ u32 _q3 = 0;
+
+ if (count > 0) {
+ /*
+ * Using existing sort() functionality as the easiest way
+ * to get median with least amount of new code.
+ *
+ * This is not the most efficient way to find a median,
+ * so feel free to implement a better one if performance is
+ * of a primary concern. "Selection algorithm" Wikipedia
+ * article is a good start:
+ * https://en.m.wikipedia.org/wiki/Selection_algorithm
+ */
+ sort(val, count, sizeof(u32), &__cmp_u32, NULL);
+
+ /*
+ * Should really do some math if count is even,
+ * but this is close enough for our purposes.
+ */
+
+ _q1 = val[count / 4];
+ _q2 = val[count / 2];
+ _q3 = val[(count * 3) / 4];
+ }
+
+ if (q1)
+ *q1 = _q1;
+
+ if (q3)
+ *q3 = _q3;
+
+ return _q2;
+}
+#endif /* #ifndef _LINUX_MEAN_H */
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 01b300a4a882..8baaddb01a95 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -23,6 +23,10 @@
#include "avtab.h"
#include "policydb.h"
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+#include "median.h"
+#endif
+
static struct kmem_cache *avtab_node_cachep;
static struct kmem_cache *avtab_xperms_cachep;
@@ -345,6 +349,10 @@ void avtab_hash_eval(struct avtab *h, char *tag)
int i, chain_len, slots_used, max_chain_len;
unsigned long long chain2_len_sum;
struct avtab_node *cur;
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ u32 med_ct = 0;
+ u32 *counts = vmalloc(h->nslot * sizeof(u32));
+#endif
slots_used = 0;
max_chain_len = 0;
@@ -358,17 +366,36 @@ void avtab_hash_eval(struct avtab *h, char *tag)
chain_len++;
cur = cur->next;
}
-
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ if (counts && chain_len)
+ counts[med_ct++] = chain_len;
+#endif
if (chain_len > max_chain_len)
max_chain_len = chain_len;
chain2_len_sum += chain_len * chain_len;
}
}
- pr_debug("SELinux: %s: %d entries and %d/%d buckets used, "
- "longest chain length %d sum of chain length^2 %llu\n",
- tag, h->nel, slots_used, h->nslot, max_chain_len,
- chain2_len_sum);
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ if (counts) {
+ u32 q1 = 0;
+ u32 q3 = 0;
+ u32 med = median(counts, med_ct, &q1, &q3);
+
+ vfree(counts);
+ pr_debug("SELinux: %s: %d entries and %d/%d buckets used, "
+ "longest chain length %d non-zero Q1/Med/Q3 %u/%u/%u "
+ "sum of chain length^2 %llu\n",
+ tag, h->nel, slots_used, h->nslot, max_chain_len,
+ q1, med, q3, chain2_len_sum);
+ } else /* Falling through! */
+#endif
+ {
+ pr_debug("SELinux: %s: %d entries and %d/%d buckets used, "
+ "longest chain length %d sum of chain length^2 %llu\n",
+ tag, h->nel, slots_used, h->nslot, max_chain_len,
+ chain2_len_sum);
+ }
}
static uint16_t spec_order[] = {
diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
index 883f19d32c28..e42d814067ba 100644
--- a/security/selinux/ss/hashtab.c
+++ b/security/selinux/ss/hashtab.c
@@ -8,8 +8,13 @@
#include <linux/slab.h>
#include <linux/errno.h>
#include <linux/sched.h>
+#include <linux/vmalloc.h>
#include "hashtab.h"
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+#include "median.h"
+#endif
+
static struct kmem_cache *hashtab_node_cachep;
/*
@@ -168,7 +173,10 @@ void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
{
u32 i, chain_len, slots_used, max_chain_len;
struct hashtab_node *cur;
-
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ u32 med_ct = 0;
+ u32 *counts = vmalloc(h->size * sizeof(u32));
+#endif
slots_used = 0;
max_chain_len = 0;
for (i = 0; i < h->size; i++) {
@@ -180,7 +188,10 @@ void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
chain_len++;
cur = cur->next;
}
-
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ if (counts && chain_len)
+ counts[med_ct++] = chain_len;
+#endif
if (chain_len > max_chain_len)
max_chain_len = chain_len;
}
@@ -188,6 +199,19 @@ void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
info->slots_used = slots_used;
info->max_chain_len = max_chain_len;
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ if (counts) {
+ info->med_chain_len = median(counts, med_ct,
+ &(info->q1_chain_len),
+ &(info->q3_chain_len));
+
+ vfree(counts);
+ } else {
+ info->q1_chain_len = 0;
+ info->med_chain_len = 0;
+ info->q3_chain_len = 0;
+ }
+#endif
}
void __init hashtab_cache_init(void)
diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
index dde54d9ff01c..b660c0078dae 100644
--- a/security/selinux/ss/hashtab.h
+++ b/security/selinux/ss/hashtab.h
@@ -32,6 +32,11 @@ struct hashtab {
struct hashtab_info {
u32 slots_used;
u32 max_chain_len;
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+ u32 q1_chain_len;
+ u32 med_chain_len;
+ u32 q3_chain_len;
+#endif
};
/*
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index c21b922e5ebe..420e347ac77c 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -41,9 +41,9 @@
#include "mls.h"
#include "services.h"
-#define _DEBUG_HASHES
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
+#include "median.h"
-#ifdef DEBUG_HASHES
static const char *symtab_name[SYM_NUM] = {
"common prefixes",
"classes",
@@ -623,15 +623,17 @@ static int (*index_f[SYM_NUM]) (void *key, void *datum, void *datap) =
cat_index,
};
-#ifdef DEBUG_HASHES
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
static void hash_eval(struct hashtab *h, const char *hash_name)
{
struct hashtab_info info;
hashtab_stat(h, &info);
- pr_debug("SELinux: %s: %d entries and %d/%d buckets used, longest chain length %d\n",
+ pr_debug("SELinux: %s: %d entries and %d/%d buckets used, "
+ "longest chain length %d non-zero Q1/Med/Q3 %u/%u/%u\n",
hash_name, h->nel, info.slots_used, h->size,
- info.max_chain_len);
+ info.max_chain_len, info.q1_chain_len,
+ info.med_chain_len, info.q3_chain_len);
}
static void symtab_hash_eval(struct symtab *s)
@@ -670,7 +672,7 @@ static int policydb_index(struct policydb *p)
pr_debug("SELinux: %d classes, %d rules\n",
p->p_classes.nprim, p->te_avtab.nel);
-#ifdef DEBUG_HASHES
+#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
avtab_hash_eval(&p->te_avtab, "rules");
symtab_hash_eval(p->symtab);
#endif
--
2.17.1
