security/selinux/ss/hashtab.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Implementation of the hash table type.
   4  *
   5  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
   6  */
   7 #include <linux/kernel.h>
   8 #include <linux/slab.h>
   9 #include <linux/errno.h>
  10 #include <linux/sched.h>
  11 #include "hashtab.h"
  12
  13 static struct kmem_cache *hashtab_node_cachep;
  14
  15 /*
  16  * Here we simply round the number of elements up to the nearest power of two.
  17  * I tried also other options like rouding down or rounding to the closest
  18  * power of two (up or down based on which is closer), but I was unable to
  19  * find any significant difference in lookup/insert performance that would
  20  * justify switching to a different (less intuitive) formula. It could be that
  21  * a different formula is actually more optimal, but any future changes here
  22  * should be supported with performance/memory usage data.
  23  *
  24  * The total memory used by the htable arrays (only) with Fedora policy loaded
  25  * is approximately 163 KB at the time of writing.
  26  */
  27 static u32 hashtab_compute_size(u32 nel)
  28 {
  29         return nel == 0 ? 0 : roundup_pow_of_two(nel);
  30 }
  31
  32 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
  33                                int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
  34                                u32 nel_hint)
  35 {
  36         struct hashtab *p;
  37         u32 i, size = hashtab_compute_size(nel_hint);
  38
  39         p = kzalloc(sizeof(*p), GFP_KERNEL);
  40         if (!p)
  41                 return p;
  42
  43         p->size = size;
  44         p->nel = 0;
  45         p->hash_value = hash_value;
  46         p->keycmp = keycmp;
  47         if (!size)
  48                 return p;
  49
  50         p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL);
  51         if (!p->htable) {
  52                 kfree(p);
  53                 return NULL;
  54         }
  55
  56         for (i = 0; i < size; i++)
  57                 p->htable[i] = NULL;
  58
  59         return p;
  60 }
  61
  62 int hashtab_insert(struct hashtab *h, void *key, void *datum)
  63 {
  64         u32 hvalue;
  65         struct hashtab_node *prev, *cur, *newnode;
  66
  67         cond_resched();
  68
  69         if (!h || !h->size || h->nel == HASHTAB_MAX_NODES)
  70                 return -EINVAL;
  71
  72         hvalue = h->hash_value(h, key);
  73         prev = NULL;
  74         cur = h->htable[hvalue];
  75         while (cur && h->keycmp(h, key, cur->key) > 0) {
  76                 prev = cur;
  77                 cur = cur->next;
  78         }
  79
  80         if (cur && (h->keycmp(h, key, cur->key) == 0))
  81                 return -EEXIST;
  82
  83         newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
  84         if (!newnode)
  85                 return -ENOMEM;
  86         newnode->key = key;
  87         newnode->datum = datum;
  88         if (prev) {
  89                 newnode->next = prev->next;
  90                 prev->next = newnode;
  91         } else {
  92                 newnode->next = h->htable[hvalue];
  93                 h->htable[hvalue] = newnode;
  94         }
  95
  96         h->nel++;
  97         return 0;
  98 }
  99
 100 void *hashtab_search(struct hashtab *h, const void *key)
 101 {
 102         u32 hvalue;
 103         struct hashtab_node *cur;
 104
 105         if (!h || !h->size)
 106                 return NULL;
 107
 108         hvalue = h->hash_value(h, key);
 109         cur = h->htable[hvalue];
 110         while (cur && h->keycmp(h, key, cur->key) > 0)
 111                 cur = cur->next;
 112
 113         if (!cur || (h->keycmp(h, key, cur->key) != 0))
 114                 return NULL;
 115
 116         return cur->datum;
 117 }
 118
 119 void hashtab_destroy(struct hashtab *h)
 120 {
 121         u32 i;
 122         struct hashtab_node *cur, *temp;
 123
 124         if (!h)
 125                 return;
 126
 127         for (i = 0; i < h->size; i++) {
 128                 cur = h->htable[i];
 129                 while (cur) {
 130                         temp = cur;
 131                         cur = cur->next;
 132                         kmem_cache_free(hashtab_node_cachep, temp);
 133                 }
 134                 h->htable[i] = NULL;
 135         }
 136
 137         kfree(h->htable);
 138         h->htable = NULL;
 139
 140         kfree(h);
 141 }
 142
 143 int hashtab_map(struct hashtab *h,
 144                 int (*apply)(void *k, void *d, void *args),
 145                 void *args)
 146 {
 147         u32 i;
 148         int ret;
 149         struct hashtab_node *cur;
 150
 151         if (!h)
 152                 return 0;
 153
 154         for (i = 0; i < h->size; i++) {
 155                 cur = h->htable[i];
 156                 while (cur) {
 157                         ret = apply(cur->key, cur->datum, args);
 158                         if (ret)
 159                                 return ret;
 160                         cur = cur->next;
 161                 }
 162         }
 163         return 0;
 164 }
 165
 166
 167 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 168 {
 169         u32 i, chain_len, slots_used, max_chain_len;
 170         struct hashtab_node *cur;
 171
 172         slots_used = 0;
 173         max_chain_len = 0;
 174         for (i = 0; i < h->size; i++) {
 175                 cur = h->htable[i];
 176                 if (cur) {
 177                         slots_used++;
 178                         chain_len = 0;
 179                         while (cur) {
 180                                 chain_len++;
 181                                 cur = cur->next;
 182                         }
 183
 184                         if (chain_len > max_chain_len)
 185                                 max_chain_len = chain_len;
 186                 }
 187         }
 188
 189         info->slots_used = slots_used;
 190         info->max_chain_len = max_chain_len;
 191 }
 192
 193 void __init hashtab_cache_init(void)
 194 {
 195                 hashtab_node_cachep = kmem_cache_create("hashtab_node",
 196                         sizeof(struct hashtab_node),
 197                         0, SLAB_PANIC, NULL);
 198 }