On Sat, 11 Nov 2023 at 08:10, Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
>
> Using full_name_hash() instead of partial_name_hash() should result
> in cleaner and better performing code.
This looks obviously good to me, but I don't actually know what that
hash is used for and whether it all matters.
Also, looking at the actual use of this all, I suspect the *real*
issue that started this all is that in hashtab_search(), we have
hvalue = key_params.hash(key) & (h->size - 1);
cur = h->htable[hvalue];
and it's that "& (h->size - 1)" thing in that hash search function
that caused problems in the first place, and that made Christian then
do that commit 37b7ea3ca306 ("selinux: improve role transition
hashing") that in turn made me look at it all.
That "just use the low bits of the hash" really ends up being the
simplest model, but it's also the worst possible thing if the hash
itself isn't spreading out all bits optimally.
We have a much better function for this, so instead of doing "x &
(size-1)" to get a hash value, you do "hash_32(x, bits)".
But that requires 'bits' instead of 'size'.
So here's a *TOTALLY UNTESTED* patch that tries to remove the use of
"h->size' for the hash table size, and replace it with an
almost-equivalent 'h->hbits' for the size of the table in bits.
I say _almost_ equivalent, because I kept the "zero means no table"
behavior, so it turns out that you cannot have a hash table of just
one entry (h->hbits would be zero). So the minimal hash table size is
2 (hbits = 1).
Honestly, I doubt that matters.
Now, that actually makes this patch somewhat intrusive, because there
were quite a bit of places that used h->size, for obvious reasons.
Also, while at it, I removed the pattern that I absolutely *detest*
that the list handling in the hashing code used, which was that
disgusting "what is the previous pointer to be filled in" pattern.
The trivial - and *horrible* - way to do it is
prev = NULL;
cur = h->htable[hvalue];
... walk the list ...
prev = cur;
...
prev ? &prev->next : &h->htable[hvalue],
which shows that people don't understand the power of pointers.
The *proper* way to do this with pointers is:
pprev = hashtab_entry(h, key, key_params);
.. walk the list with (cur = *pprev) != NULL) ...
pprev = &cur->next;
...
pprev
which doesn't have that unnecessary conditional for "is this the first
entry". It not only generates better code, it shows that you
understand pointers.
Yes, this is the smallest hill I'll die on. It's literally a pet peeve of mine.
I also moved variable declarations into the blocks where they are
used, rather than at the top level.
Now, I want to state this very clearly once again: this attached patch
is ENTIRELY UNTESTED. It might have some completely stupid thinko in
it, and may be entirely broken.
I test-compiled it, and I've looked through it a couple of times for
sanity, and I do think it's better to keep "hbits" around instead of
"size", but I'm not going to force this on you.
Anyway, I guess I should test this, but here is that untested patch if
you want to consider it.
Linus
security/selinux/ss/hashtab.c | 78 ++++++++++++++++++++++--------------------
security/selinux/ss/hashtab.h | 41 ++++++++++++----------
security/selinux/ss/policydb.c | 2 +-
3 files changed, 64 insertions(+), 57 deletions(-)
diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
index c05d8346a94a..b4bc1aebebe6 100644
--- a/security/selinux/ss/hashtab.c
+++ b/security/selinux/ss/hashtab.c
@@ -24,25 +24,27 @@ static struct kmem_cache *hashtab_node_cachep __ro_after_init;
* The total memory used by the htable arrays (only) with Fedora policy loaded
* is approximately 163 KB at the time of writing.
*/
-static u32 hashtab_compute_size(u32 nel)
+static u32 hashtab_compute_hbits(u32 nel)
{
- return nel == 0 ? 0 : roundup_pow_of_two(nel);
+ if (nel <= 1)
+ return nel;
+ return ilog2(nel - 1) + 1;
}
int hashtab_init(struct hashtab *h, u32 nel_hint)
{
- u32 size = hashtab_compute_size(nel_hint);
+ u32 hbits = hashtab_compute_hbits(nel_hint);
/* should already be zeroed, but better be safe */
h->nel = 0;
- h->size = 0;
+ h->hbits = 0;
h->htable = NULL;
- if (size) {
- h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
+ if (hbits) {
+ h->htable = kcalloc(1 << hbits, sizeof(*h->htable), GFP_KERNEL);
if (!h->htable)
return -ENOMEM;
- h->size = size;
+ h->hbits = hbits;
}
return 0;
}
@@ -66,10 +68,11 @@ int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
void hashtab_destroy(struct hashtab *h)
{
- u32 i;
- struct hashtab_node *cur, *temp;
+ u32 size = hashtab_size(h);
+
+ for (u32 i = 0; i < size; i++) {
+ struct hashtab_node *cur, *temp;
- for (i = 0; i < h->size; i++) {
cur = h->htable[i];
while (cur) {
temp = cur;
@@ -81,20 +84,19 @@ void hashtab_destroy(struct hashtab *h)
kfree(h->htable);
h->htable = NULL;
+ h->hbits = 0;
}
int hashtab_map(struct hashtab *h,
int (*apply)(void *k, void *d, void *args),
void *args)
{
- u32 i;
- int ret;
- struct hashtab_node *cur;
+ u32 size = hashtab_size(h);
- for (i = 0; i < h->size; i++) {
- cur = h->htable[i];
+ for (u32 i = 0; i < size; i++) {
+ struct hashtab_node *cur = cur = h->htable[i];
while (cur) {
- ret = apply(cur->key, cur->datum, args);
+ int ret = apply(cur->key, cur->datum, args);
if (ret)
return ret;
cur = cur->next;
@@ -106,18 +108,18 @@ int hashtab_map(struct hashtab *h,
#ifdef CONFIG_SECURITY_SELINUX_DEBUG
void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
{
- u32 i, chain_len, slots_used, max_chain_len;
+ u32 size = hashtab_size(h);
+ u32 slots_used, max_chain_len;
u64 chain2_len_sum;
- struct hashtab_node *cur;
slots_used = 0;
max_chain_len = 0;
chain2_len_sum = 0;
- for (i = 0; i < h->size; i++) {
- cur = h->htable[i];
+ for (u32 i = 0; i < size; i++) {
+ struct hashtab_node *cur = h->htable[i];
if (cur) {
+ u32 chain_len = 0;
slots_used++;
- chain_len = 0;
while (cur) {
chain_len++;
cur = cur->next;
@@ -142,36 +144,35 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
int (*destroy)(void *k, void *d, void *args),
void *args)
{
- struct hashtab_node *cur, *tmp, *tail;
- u32 i;
- int rc;
+ u32 size = hashtab_size(orig);
memset(new, 0, sizeof(*new));
- new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
- if (!new->htable)
- return -ENOMEM;
+ if (size) {
+ new->htable = kcalloc(size, sizeof(*new->htable), GFP_KERNEL);
+ if (!new->htable)
+ return -ENOMEM;
+ new->hbits = orig->hbits;
+ }
- new->size = orig->size;
+ for (u32 i = 0; i < size; i++) {
+ struct hashtab_node *cur, **tailp;
+ tailp = new->htable + i;
- for (i = 0; i < orig->size; i++) {
- tail = NULL;
for (cur = orig->htable[i]; cur; cur = cur->next) {
+ struct hashtab_node *tmp;
+
tmp = kmem_cache_zalloc(hashtab_node_cachep,
GFP_KERNEL);
if (!tmp)
goto error;
- rc = copy(tmp, cur, args);
- if (rc) {
+ if (copy(tmp, cur, args)) {
kmem_cache_free(hashtab_node_cachep, tmp);
goto error;
}
tmp->next = NULL;
- if (!tail)
- new->htable[i] = tmp;
- else
- tail->next = tmp;
- tail = tmp;
+ *tailp = tmp;
+ tailp = &tmp->next;
new->nel++;
}
}
@@ -179,7 +180,8 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
return 0;
error:
- for (i = 0; i < new->size; i++) {
+ for (u32 i = 0; i < size; i++) {
+ struct hashtab_node *cur, *tmp;
for (cur = new->htable[i]; cur; cur = tmp) {
tmp = cur->next;
destroy(cur->key, cur->datum, args);
diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
index 09b0a3744937..6b65c9a52559 100644
--- a/security/selinux/ss/hashtab.h
+++ b/security/selinux/ss/hashtab.h
@@ -14,6 +14,7 @@
#include <linux/types.h>
#include <linux/errno.h>
#include <linux/sched.h>
+#include <linux/hash.h>
#define HASHTAB_MAX_NODES U32_MAX
@@ -31,7 +32,7 @@ struct hashtab_node {
struct hashtab {
struct hashtab_node **htable; /* hash table */
- u32 size; /* number of slots in hash table */
+ u32 hbits; /* number of slots in hash table */
u32 nel; /* number of elements in hash table */
};
@@ -41,6 +42,11 @@ struct hashtab_info {
u64 chain2_len_sum;
};
+static inline u32 hashtab_size(const struct hashtab *h)
+{
+ return h->hbits ? 1 << h->hbits : 0;
+}
+
/*
* Initializes a new hash table with the specified characteristics.
*
@@ -51,6 +57,12 @@ int hashtab_init(struct hashtab *h, u32 nel_hint);
int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
void *key, void *datum);
+static inline struct hashtab_node **hashtab_entry(struct hashtab *h,
+ const void *key, const struct hashtab_key_params key_params)
+{
+ return h->htable + hash_32(key_params.hash(key), h->hbits);
+}
+
/*
* Inserts the specified (key, datum) pair into the specified hash table.
*
@@ -60,32 +72,27 @@ int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
0 otherwise.
*/
static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
- struct hashtab_key_params key_params)
+ const struct hashtab_key_params key_params)
{
- u32 hvalue;
- struct hashtab_node *prev, *cur;
+ struct hashtab_node **pprev;
cond_resched();
- if (!h->size || h->nel == HASHTAB_MAX_NODES)
+ if (!h->hbits || h->nel == HASHTAB_MAX_NODES)
return -EINVAL;
- hvalue = key_params.hash(key) & (h->size - 1);
- prev = NULL;
- cur = h->htable[hvalue];
- while (cur) {
+ pprev = hashtab_entry(h, key, key_params);
+ for (struct hashtab_node *cur; (cur = *pprev) != NULL; ) {
int cmp = key_params.cmp(key, cur->key);
if (cmp == 0)
return -EEXIST;
if (cmp < 0)
break;
- prev = cur;
- cur = cur->next;
+ pprev = &cur->next;
}
- return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
- key, datum);
+ return __hashtab_insert(h, pprev, key, datum);
}
/*
@@ -95,16 +102,14 @@ static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
* the datum of the entry otherwise.
*/
static inline void *hashtab_search(struct hashtab *h, const void *key,
- struct hashtab_key_params key_params)
+ const struct hashtab_key_params key_params)
{
- u32 hvalue;
struct hashtab_node *cur;
- if (!h->size)
+ if (!h->hbits)
return NULL;
- hvalue = key_params.hash(key) & (h->size - 1);
- cur = h->htable[hvalue];
+ cur = *hashtab_entry(h, key, key_params);
while (cur) {
int cmp = key_params.cmp(key, cur->key);
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 595a435ea9c8..61bc82b2cea6 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -685,7 +685,7 @@ static void hash_eval(struct hashtab *h, const char *hash_name)
hashtab_stat(h, &info);
pr_debug("SELinux: %s: %d entries and %d/%d buckets used, longest chain length %d, sum of chain length^2 %llu\n",
- hash_name, h->nel, info.slots_used, h->size,
+ hash_name, h->nel, info.slots_used, hashtab_size(h),
info.max_chain_len, info.chain2_len_sum);
}
