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 rouding 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 } 184