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 } 199