@@ -7,7 +7,6 @@
#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;
@@ -40,71 +39,23 @@ int hashtab_init(struct hashtab *h, u32 nel_hint)
return h->htable ? 0 : -ENOMEM;
}
-int hashtab_insert(struct hashtab *h, void *key, void *datum,
- struct hashtab_key_params key_params)
+int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
+ void *key, void *datum)
{
- u32 hvalue;
- struct hashtab_node *prev, *cur, *newnode;
-
- cond_resched();
-
- if (!h->size || h->nel == HASHTAB_MAX_NODES)
- return -EINVAL;
-
- hvalue = key_params.hash(key) & (h->size - 1);
- prev = NULL;
- cur = h->htable[hvalue];
- while (cur) {
- int cmp = key_params.cmp(key, cur->key);
-
- if (cmp == 0)
- return -EEXIST;
- if (cmp < 0)
- break;
- prev = cur;
- cur = cur->next;
- }
+ 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,
- struct hashtab_key_params key_params)
-{
- u32 hvalue;
- struct hashtab_node *cur;
-
- if (!h->size)
- return NULL;
-
- hvalue = key_params.hash(key) & (h->size - 1);
- cur = h->htable[hvalue];
- while (cur) {
- int cmp = key_params.cmp(key, cur->key);
-
- if (cmp == 0)
- return cur->datum;
- if (cmp < 0)
- break;
- cur = cur->next;
- }
- return NULL;
-}
-
void hashtab_destroy(struct hashtab *h)
{
u32 i;
@@ -11,7 +11,11 @@
#ifndef _SS_HASHTAB_H_
#define _SS_HASHTAB_H_
-#define HASHTAB_MAX_NODES 0xffffffff
+#include <linux/types.h>
+#include <linux/errno.h>
+#include <linux/sched.h>
+
+#define HASHTAB_MAX_NODES U32_MAX
struct hashtab_key_params {
u32 (*hash)(const void *key); /* hash function */
@@ -43,6 +47,9 @@ struct hashtab_info {
*/
int hashtab_init(struct hashtab *h, u32 nel_hint);
+int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
+ void *key, void *datum);
+
/*
* Inserts the specified (key, datum) pair into the specified hash table.
*
@@ -51,8 +58,34 @@ int hashtab_init(struct hashtab *h, u32 nel_hint);
* -EINVAL for general errors or
0 otherwise.
*/
-int hashtab_insert(struct hashtab *h, void *k, void *d,
- struct hashtab_key_params key_params);
+static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
+ struct hashtab_key_params key_params)
+{
+ u32 hvalue;
+ struct hashtab_node *prev, *cur;
+
+ cond_resched();
+
+ if (!h->size || h->nel == HASHTAB_MAX_NODES)
+ return -EINVAL;
+
+ hvalue = key_params.hash(key) & (h->size - 1);
+ prev = NULL;
+ cur = h->htable[hvalue];
+ while (cur) {
+ int cmp = key_params.cmp(key, cur->key);
+
+ if (cmp == 0)
+ return -EEXIST;
+ if (cmp < 0)
+ break;
+ prev = cur;
+ cur = cur->next;
+ }
+
+ return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
+ key, datum);
+}
/*
* Searches for the entry with the specified key in the hash table.
@@ -60,8 +93,28 @@ int hashtab_insert(struct hashtab *h, void *k, void *d,
* Returns NULL if no entry has the specified key or
* the datum of the entry otherwise.
*/
-void *hashtab_search(struct hashtab *h, const void *k,
- struct hashtab_key_params key_params);
+static inline void *hashtab_search(struct hashtab *h, const void *key,
+ struct hashtab_key_params key_params)
+{
+ u32 hvalue;
+ struct hashtab_node *cur;
+
+ if (!h->size)
+ return NULL;
+
+ hvalue = key_params.hash(key) & (h->size - 1);
+ cur = h->htable[hvalue];
+ while (cur) {
+ int cmp = key_params.cmp(key, cur->key);
+
+ if (cmp == 0)
+ return cur->datum;
+ if (cmp < 0)
+ break;
+ cur = cur->next;
+ }
+ return NULL;
+}
/*
* Destroys the specified hash table.
Move (most of) the definitions of hashtab_search() and hashtab_insert() to the header file. In combination with the previous patch, this avoids calling the callbacks indirectly by function pointers and allows for better optimization, leading to a drastic performance improvement of these operations. With this patch, I measured a speed up in the following areas (measured on x86_64 F32 VM with 4 CPUs): 1. Policy load (`load_policy`) - takes ~150 ms instead of ~230 ms. 2. `chcon -R unconfined_u:object_r:user_tmp_t:s0:c381,c519 /tmp/linux-src` where /tmp/linux-src is an extracted linux-5.7 source tarball - takes ~522 ms instead of ~576 ms. This is because of many symtab_search() calls in string_to_context_struct() when there are many categories specified in the context. 3. `stress-ng --msg 1 --msg-ops 10000000` - takes 12.41 s instead of 13.95 s (consumes 18.6 s of kernel CPU time instead of 21.6 s). This is thanks to security_transition_sid() being ~43% faster after this patch. Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- security/selinux/ss/hashtab.c | 59 +++----------------------------- security/selinux/ss/hashtab.h | 63 ++++++++++++++++++++++++++++++++--- 2 files changed, 63 insertions(+), 59 deletions(-)