From 6778948f9de86c3cfaf36725a7c87dcff9ba247f Mon Sep 17 00:00:00 2001
From: hc <hc@nodka.com>
Date: Mon, 11 Dec 2023 08:20:59 +0000
Subject: [PATCH] kernel_5.10 no rt
---
kernel/security/selinux/ss/hashtab.c | 161 +++++++++++++++++++++++++++++------------------------
1 files changed, 87 insertions(+), 74 deletions(-)
diff --git a/kernel/security/selinux/ss/hashtab.c b/kernel/security/selinux/ss/hashtab.c
index ebfdaa3..e8960a5 100644
--- a/kernel/security/selinux/ss/hashtab.c
+++ b/kernel/security/selinux/ss/hashtab.c
@@ -7,102 +7,66 @@
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/errno.h>
-#include <linux/sched.h>
#include "hashtab.h"
static struct kmem_cache *hashtab_node_cachep;
-struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
- int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
- u32 size)
+/*
+ * Here we simply round the number of elements up to the nearest power of two.
+ * I tried also other options like rouding down or rounding to the closest
+ * power of two (up or down based on which is closer), but I was unable to
+ * find any significant difference in lookup/insert performance that would
+ * justify switching to a different (less intuitive) formula. It could be that
+ * a different formula is actually more optimal, but any future changes here
+ * should be supported with performance/memory usage data.
+ *
+ * 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)
{
- struct hashtab *p;
- u32 i;
-
- p = kzalloc(sizeof(*p), GFP_KERNEL);
- if (!p)
- return p;
-
- p->size = size;
- p->nel = 0;
- p->hash_value = hash_value;
- p->keycmp = keycmp;
- p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL);
- if (!p->htable) {
- kfree(p);
- return NULL;
- }
-
- for (i = 0; i < size; i++)
- p->htable[i] = NULL;
-
- return p;
+ return nel == 0 ? 0 : roundup_pow_of_two(nel);
}
-int hashtab_insert(struct hashtab *h, void *key, void *datum)
+int hashtab_init(struct hashtab *h, u32 nel_hint)
{
- u32 hvalue;
- struct hashtab_node *prev, *cur, *newnode;
+ u32 size = hashtab_compute_size(nel_hint);
- cond_resched();
+ /* should already be zeroed, but better be safe */
+ h->nel = 0;
+ h->size = 0;
+ h->htable = NULL;
- if (!h || h->nel == HASHTAB_MAX_NODES)
- return -EINVAL;
-
- hvalue = h->hash_value(h, key);
- prev = NULL;
- cur = h->htable[hvalue];
- while (cur && h->keycmp(h, key, cur->key) > 0) {
- prev = cur;
- cur = cur->next;
+ if (size) {
+ h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
+ if (!h->htable)
+ return -ENOMEM;
+ h->size = size;
}
+ return 0;
+}
- if (cur && (h->keycmp(h, key, cur->key) == 0))
- return -EEXIST;
+int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
+ void *key, void *datum)
+{
+ struct hashtab_node *newnode;
newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
if (!newnode)
return -ENOMEM;
newnode->key = key;
newnode->datum = datum;
- if (prev) {
- newnode->next = prev->next;
- prev->next = newnode;
- } else {
- newnode->next = h->htable[hvalue];
- h->htable[hvalue] = newnode;
- }
+ newnode->next = *dst;
+ *dst = newnode;
h->nel++;
return 0;
-}
-
-void *hashtab_search(struct hashtab *h, const void *key)
-{
- u32 hvalue;
- struct hashtab_node *cur;
-
- if (!h)
- return NULL;
-
- hvalue = h->hash_value(h, key);
- cur = h->htable[hvalue];
- while (cur && h->keycmp(h, key, cur->key) > 0)
- cur = cur->next;
-
- if (!cur || (h->keycmp(h, key, cur->key) != 0))
- return NULL;
-
- return cur->datum;
}
void hashtab_destroy(struct hashtab *h)
{
u32 i;
struct hashtab_node *cur, *temp;
-
- if (!h)
- return;
for (i = 0; i < h->size; i++) {
cur = h->htable[i];
@@ -116,8 +80,6 @@
kfree(h->htable);
h->htable = NULL;
-
- kfree(h);
}
int hashtab_map(struct hashtab *h,
@@ -127,9 +89,6 @@
u32 i;
int ret;
struct hashtab_node *cur;
-
- if (!h)
- return 0;
for (i = 0; i < h->size; i++) {
cur = h->htable[i];
@@ -170,6 +129,60 @@
info->max_chain_len = max_chain_len;
}
+int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
+ int (*copy)(struct hashtab_node *new,
+ struct hashtab_node *orig, void *args),
+ int (*destroy)(void *k, void *d, void *args),
+ void *args)
+{
+ struct hashtab_node *cur, *tmp, *tail;
+ int i, rc;
+
+ memset(new, 0, sizeof(*new));
+
+ new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
+ if (!new->htable)
+ return -ENOMEM;
+
+ new->size = orig->size;
+
+ for (i = 0; i < orig->size; i++) {
+ tail = NULL;
+ for (cur = orig->htable[i]; cur; cur = cur->next) {
+ tmp = kmem_cache_zalloc(hashtab_node_cachep,
+ GFP_KERNEL);
+ if (!tmp)
+ goto error;
+ rc = copy(tmp, cur, args);
+ if (rc) {
+ kmem_cache_free(hashtab_node_cachep, tmp);
+ goto error;
+ }
+ tmp->next = NULL;
+ if (!tail)
+ new->htable[i] = tmp;
+ else
+ tail->next = tmp;
+ tail = tmp;
+ new->nel++;
+ }
+ }
+
+ return 0;
+
+ error:
+ for (i = 0; i < new->size; i++) {
+ for (cur = new->htable[i]; cur; cur = tmp) {
+ tmp = cur->next;
+ destroy(cur->key, cur->datum, args);
+ kmem_cache_free(hashtab_node_cachep, cur);
+ }
+ }
+ kfree(new->htable);
+ memset(new, 0, sizeof(*new));
+ return -ENOMEM;
+}
+
void __init hashtab_cache_init(void)
{
hashtab_node_cachep = kmem_cache_create("hashtab_node",
--
Gitblit v1.6.2