security/selinux/ss/hashtab.c

   1 /*
   2  * Implementation of the hash table type.
   3  *
   4  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
   5  */
   6 #include <linux/kernel.h>
   7 #include <linux/slab.h>
   8 #include <linux/errno.h>
   9 #include <linux/sched.h>
  10 #include "hashtab.h"
  11
  12 static struct kmem_cache *hashtab_node_cachep;
  13
  14 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
  15                                int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
  16                                u32 size)
  17 {
  18         struct hashtab *p;
  19         u32 i;
  20
  21         p = kzalloc(sizeof(*p), GFP_KERNEL);
  22         if (!p)
  23                 return p;
  24
  25         p->size = size;
  26         p->nel = 0;
  27         p->hash_value = hash_value;
  28         p->keycmp = keycmp;
  29         p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL);
  30         if (!p->htable) {
  31                 kfree(p);
  32                 return NULL;
  33         }
  34
  35         for (i = 0; i < size; i++)
  36                 p->htable[i] = NULL;
  37
  38         return p;
  39 }
  40
  41 int hashtab_insert(struct hashtab *h, void *key, void *datum)
  42 {
  43         u32 hvalue;
  44         struct hashtab_node *prev, *cur, *newnode;
  45
  46         cond_resched();
  47
  48         if (!h || h->nel == HASHTAB_MAX_NODES)
  49                 return -EINVAL;
  50
  51         hvalue = h->hash_value(h, key);
  52         prev = NULL;
  53         cur = h->htable[hvalue];
  54         while (cur && h->keycmp(h, key, cur->key) > 0) {
  55                 prev = cur;
  56                 cur = cur->next;
  57         }
  58
  59         if (cur && (h->keycmp(h, key, cur->key) == 0))
  60                 return -EEXIST;
  61
  62         newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
  63         if (!newnode)
  64                 return -ENOMEM;
  65         newnode->key = key;
  66         newnode->datum = datum;
  67         if (prev) {
  68                 newnode->next = prev->next;
  69                 prev->next = newnode;
  70         } else {
  71                 newnode->next = h->htable[hvalue];
  72                 h->htable[hvalue] = newnode;
  73         }
  74
  75         h->nel++;
  76         return 0;
  77 }
  78
  79 void *hashtab_search(struct hashtab *h, const void *key)
  80 {
  81         u32 hvalue;
  82         struct hashtab_node *cur;
  83
  84         if (!h)
  85                 return NULL;
  86
  87         hvalue = h->hash_value(h, key);
  88         cur = h->htable[hvalue];
  89         while (cur && h->keycmp(h, key, cur->key) > 0)
  90                 cur = cur->next;
  91
  92         if (!cur || (h->keycmp(h, key, cur->key) != 0))
  93                 return NULL;
  94
  95         return cur->datum;
  96 }
  97
  98 void hashtab_destroy(struct hashtab *h)
  99 {
 100         u32 i;
 101         struct hashtab_node *cur, *temp;
 102
 103         if (!h)
 104                 return;
 105
 106         for (i = 0; i < h->size; i++) {
 107                 cur = h->htable[i];
 108                 while (cur) {
 109                         temp = cur;
 110                         cur = cur->next;
 111                         kmem_cache_free(hashtab_node_cachep, temp);
 112                 }
 113                 h->htable[i] = NULL;
 114         }
 115
 116         kfree(h->htable);
 117         h->htable = NULL;
 118
 119         kfree(h);
 120 }
 121
 122 int hashtab_map(struct hashtab *h,
 123                 int (*apply)(void *k, void *d, void *args),
 124                 void *args)
 125 {
 126         u32 i;
 127         int ret;
 128         struct hashtab_node *cur;
 129
 130         if (!h)
 131                 return 0;
 132
 133         for (i = 0; i < h->size; i++) {
 134                 cur = h->htable[i];
 135                 while (cur) {
 136                         ret = apply(cur->key, cur->datum, args);
 137                         if (ret)
 138                                 return ret;
 139                         cur = cur->next;
 140                 }
 141         }
 142         return 0;
 143 }
 144
 145
 146 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 147 {
 148         u32 i, chain_len, slots_used, max_chain_len;
 149         struct hashtab_node *cur;
 150
 151         slots_used = 0;
 152         max_chain_len = 0;
 153         for (i = 0; i < h->size; i++) {
 154                 cur = h->htable[i];
 155                 if (cur) {
 156                         slots_used++;
 157                         chain_len = 0;
 158                         while (cur) {
 159                                 chain_len++;
 160                                 cur = cur->next;
 161                         }
 162
 163                         if (chain_len > max_chain_len)
 164                                 max_chain_len = chain_len;
 165                 }
 166         }
 167
 168         info->slots_used = slots_used;
 169         info->max_chain_len = max_chain_len;
 170 }
 171 void hashtab_cache_init(void)
 172 {
 173                 hashtab_node_cachep = kmem_cache_create("hashtab_node",
 174                         sizeof(struct hashtab_node),
 175                         0, SLAB_PANIC, NULL);
 176 }
 177
 178 void hashtab_cache_destroy(void)
 179 {
 180                 kmem_cache_destroy(hashtab_node_cachep);
 181 }