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 "hashtab.h"
  11
  12 static struct kmem_cache *hashtab_node_cachep __ro_after_init;
  13
  14 /*
  15  * Here we simply round the number of elements up to the nearest power of two.
  16  * I tried also other options like rounding down or rounding to the closest
  17  * power of two (up or down based on which is closer), but I was unable to
  18  * find any significant difference in lookup/insert performance that would
  19  * justify switching to a different (less intuitive) formula. It could be that
  20  * a different formula is actually more optimal, but any future changes here
  21  * should be supported with performance/memory usage data.
  22  *
  23  * The total memory used by the htable arrays (only) with Fedora policy loaded
  24  * is approximately 163 KB at the time of writing.
  25  */
  26 static u32 hashtab_compute_size(u32 nel)
  27 {
  28         return nel == 0 ? 0 : roundup_pow_of_two(nel);
  29 }
  30
  31 int hashtab_init(struct hashtab *h, u32 nel_hint)
  32 {
  33         h->size = hashtab_compute_size(nel_hint);
  34         h->nel = 0;
  35         if (!h->size)
  36                 return 0;
  37
  38         h->htable = kcalloc(h->size, sizeof(*h->htable), GFP_KERNEL);
  39         return h->htable ? 0 : -ENOMEM;
  40 }
  41
  42 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
  43                      void *key, void *datum)
  44 {
  45         struct hashtab_node *newnode;
  46
  47         newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
  48         if (!newnode)
  49                 return -ENOMEM;
  50         newnode->key = key;
  51         newnode->datum = datum;
  52         newnode->next = *dst;
  53         *dst = newnode;
  54
  55         h->nel++;
  56         return 0;
  57 }
  58
  59 void hashtab_destroy(struct hashtab *h)
  60 {
  61         u32 i;
  62         struct hashtab_node *cur, *temp;
  63
  64         for (i = 0; i < h->size; i++) {
  65                 cur = h->htable[i];
  66                 while (cur) {
  67                         temp = cur;
  68                         cur = cur->next;
  69                         kmem_cache_free(hashtab_node_cachep, temp);
  70                 }
  71                 h->htable[i] = NULL;
  72         }
  73
  74         kfree(h->htable);
  75         h->htable = NULL;
  76 }
  77
  78 int hashtab_map(struct hashtab *h,
  79                 int (*apply)(void *k, void *d, void *args),
  80                 void *args)
  81 {
  82         u32 i;
  83         int ret;
  84         struct hashtab_node *cur;
  85
  86         for (i = 0; i < h->size; i++) {
  87                 cur = h->htable[i];
  88                 while (cur) {
  89                         ret = apply(cur->key, cur->datum, args);
  90                         if (ret)
  91                                 return ret;
  92                         cur = cur->next;
  93                 }
  94         }
  95         return 0;
  96 }
  97
  98
  99 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 100 {
 101         u32 i, chain_len, slots_used, max_chain_len;
 102         struct hashtab_node *cur;
 103
 104         slots_used = 0;
 105         max_chain_len = 0;
 106         for (i = 0; i < h->size; i++) {
 107                 cur = h->htable[i];
 108                 if (cur) {
 109                         slots_used++;
 110                         chain_len = 0;
 111                         while (cur) {
 112                                 chain_len++;
 113                                 cur = cur->next;
 114                         }
 115
 116                         if (chain_len > max_chain_len)
 117                                 max_chain_len = chain_len;
 118                 }
 119         }
 120
 121         info->slots_used = slots_used;
 122         info->max_chain_len = max_chain_len;
 123 }
 124
 125 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
 126                 int (*copy)(struct hashtab_node *new,
 127                         struct hashtab_node *orig, void *args),
 128                 int (*destroy)(void *k, void *d, void *args),
 129                 void *args)
 130 {
 131         struct hashtab_node *cur, *tmp, *tail;
 132         int i, rc;
 133
 134         memset(new, 0, sizeof(*new));
 135
 136         new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
 137         if (!new->htable)
 138                 return -ENOMEM;
 139
 140         new->size = orig->size;
 141
 142         for (i = 0; i < orig->size; i++) {
 143                 tail = NULL;
 144                 for (cur = orig->htable[i]; cur; cur = cur->next) {
 145                         tmp = kmem_cache_zalloc(hashtab_node_cachep,
 146                                                 GFP_KERNEL);
 147                         if (!tmp)
 148                                 goto error;
 149                         rc = copy(tmp, cur, args);
 150                         if (rc) {
 151                                 kmem_cache_free(hashtab_node_cachep, tmp);
 152                                 goto error;
 153                         }
 154                         tmp->next = NULL;
 155                         if (!tail)
 156                                 new->htable[i] = tmp;
 157                         else
 158                                 tail->next = tmp;
 159                         tail = tmp;
 160                         new->nel++;
 161                 }
 162         }
 163
 164         return 0;
 165
 166  error:
 167         for (i = 0; i < new->size; i++) {
 168                 for (cur = new->htable[i]; cur; cur = tmp) {
 169                         tmp = cur->next;
 170                         destroy(cur->key, cur->datum, args);
 171                         kmem_cache_free(hashtab_node_cachep, cur);
 172                 }
 173         }
 174         kmem_cache_free(hashtab_node_cachep, new);
 175         return -ENOMEM;
 176 }
 177
 178 void __init hashtab_cache_init(void)
 179 {
 180                 hashtab_node_cachep = kmem_cache_create("hashtab_node",
 181                         sizeof(struct hashtab_node),
 182                         0, SLAB_PANIC, NULL);
 183 }