summaryrefslogtreecommitdiff
path: root/security/selinux/ss/hashtab.c
diff options
context:
space:
mode:
authorOndrej Mosnacek <omosnace@redhat.com>2020-07-09 21:19:51 +0200
committerPaul Moore <paul@paul-moore.com>2020-07-09 19:05:36 -0400
commit24def7bb92c19337cee26d506f87dc4eeeba7a19 (patch)
tree1c33bb5b711918c8ffd0f45e3b97c7ac38a0d427 /security/selinux/ss/hashtab.c
parent237389e3015e0f4ceac7cf00c70a59746150561d (diff)
selinux: prepare for inlining of hashtab functions
Refactor searching and inserting into hashtabs to pave the way for converting hashtab_search() and hashtab_insert() to inline functions in the next patch. This will avoid indirect calls and allow the compiler to better optimize individual callers, leading to a significant performance improvement. In order to avoid the indirect calls, the key hashing and comparison callbacks need to be extracted from the hashtab struct and passed directly to hashtab_search()/_insert() by the callers so that the callback address is always known at compile time. The kernel's rhashtable library (<linux/rhashtable*.h>) does the same thing. This of course makes the hashtab functions slightly easier to misuse by passing a wrong callback set, but unfortunately there is no better way to implement a hash table that is both generic and efficient in C. This patch tries to somewhat mitigate this by only calling the hashtab functions in the same file where the corresponding callbacks are defined (wrapping them into more specialized functions as needed). Note that this patch doesn't bring any benefit without also moving the definitions of hashtab_search() and -_insert() to the header file, which is done in a follow-up patch for easier review of the hashtab.c changes in this patch. Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com> Signed-off-by: Paul Moore <paul@paul-moore.com>
Diffstat (limited to 'security/selinux/ss/hashtab.c')
-rw-r--r--security/selinux/ss/hashtab.c44
1 files changed, 23 insertions, 21 deletions
diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
index 5ee868116d70..8126b909a757 100644
--- a/security/selinux/ss/hashtab.c
+++ b/security/selinux/ss/hashtab.c
@@ -29,16 +29,10 @@ static u32 hashtab_compute_size(u32 nel)
return nel == 0 ? 0 : roundup_pow_of_two(nel);
}
-int hashtab_init(struct hashtab *h,
- u32 (*hash_value)(struct hashtab *h, const void *key),
- int (*keycmp)(struct hashtab *h, const void *key1,
- const void *key2),
- u32 nel_hint)
+int hashtab_init(struct hashtab *h, u32 nel_hint)
{
h->size = hashtab_compute_size(nel_hint);
h->nel = 0;
- h->hash_value = hash_value;
- h->keycmp = keycmp;
if (!h->size)
return 0;
@@ -46,7 +40,8 @@ int hashtab_init(struct hashtab *h,
return h->htable ? 0 : -ENOMEM;
}
-int hashtab_insert(struct hashtab *h, void *key, void *datum)
+int hashtab_insert(struct hashtab *h, void *key, void *datum,
+ struct hashtab_key_params key_params)
{
u32 hvalue;
struct hashtab_node *prev, *cur, *newnode;
@@ -56,17 +51,20 @@ int hashtab_insert(struct hashtab *h, void *key, void *datum)
if (!h->size || h->nel == HASHTAB_MAX_NODES)
return -EINVAL;
- hvalue = h->hash_value(h, key);
+ hvalue = key_params.hash(key) & (h->size - 1);
prev = NULL;
cur = h->htable[hvalue];
- while (cur && h->keycmp(h, key, cur->key) > 0) {
+ while (cur) {
+ int cmp = key_params.cmp(key, cur->key);
+
+ if (cmp == 0)
+ return -EEXIST;
+ if (cmp < 0)
+ break;
prev = cur;
cur = cur->next;
}
- if (cur && (h->keycmp(h, key, cur->key) == 0))
- return -EEXIST;
-
newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
if (!newnode)
return -ENOMEM;
@@ -84,7 +82,8 @@ int hashtab_insert(struct hashtab *h, void *key, void *datum)
return 0;
}
-void *hashtab_search(struct hashtab *h, const void *key)
+void *hashtab_search(struct hashtab *h, const void *key,
+ struct hashtab_key_params key_params)
{
u32 hvalue;
struct hashtab_node *cur;
@@ -92,15 +91,18 @@ void *hashtab_search(struct hashtab *h, const void *key)
if (!h->size)
return NULL;
- hvalue = h->hash_value(h, key);
+ hvalue = key_params.hash(key) & (h->size - 1);
cur = h->htable[hvalue];
- while (cur && h->keycmp(h, key, cur->key) > 0)
- cur = cur->next;
+ while (cur) {
+ int cmp = key_params.cmp(key, cur->key);
- if (!cur || (h->keycmp(h, key, cur->key) != 0))
- return NULL;
-
- return cur->datum;
+ if (cmp == 0)
+ return cur->datum;
+ if (cmp < 0)
+ break;
+ cur = cur->next;
+ }
+ return NULL;
}
void hashtab_destroy(struct hashtab *h)