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 #include "security.h" 12 13 static struct kmem_cache *hashtab_node_cachep __ro_after_init; 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 rounding 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 int hashtab_init(struct hashtab *h, u32 nel_hint) 33 { 34 h->size = hashtab_compute_size(nel_hint); 35 h->nel = 0; 36 if (!h->size) 37 return 0; 38 39 h->htable = kcalloc(h->size, sizeof(*h->htable), GFP_KERNEL); 40 return h->htable ? 0 : -ENOMEM; 41 } 42 43 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, 44 void *key, void *datum) 45 { 46 struct hashtab_node *newnode; 47 48 newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 49 if (!newnode) 50 return -ENOMEM; 51 newnode->key = key; 52 newnode->datum = datum; 53 newnode->next = *dst; 54 *dst = newnode; 55 56 h->nel++; 57 return 0; 58 } 59 60 void hashtab_destroy(struct hashtab *h) 61 { 62 u32 i; 63 struct hashtab_node *cur, *temp; 64 65 for (i = 0; i < h->size; i++) { 66 cur = h->htable[i]; 67 while (cur) { 68 temp = cur; 69 cur = cur->next; 70 kmem_cache_free(hashtab_node_cachep, temp); 71 } 72 h->htable[i] = NULL; 73 } 74 75 kfree(h->htable); 76 h->htable = NULL; 77 } 78 79 int hashtab_map(struct hashtab *h, 80 int (*apply)(void *k, void *d, void *args), 81 void *args) 82 { 83 u32 i; 84 int ret; 85 struct hashtab_node *cur; 86 87 for (i = 0; i < h->size; i++) { 88 cur = h->htable[i]; 89 while (cur) { 90 ret = apply(cur->key, cur->datum, args); 91 if (ret) 92 return ret; 93 cur = cur->next; 94 } 95 } 96 return 0; 97 } 98 99 100 void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 101 { 102 u32 i, chain_len, slots_used, max_chain_len; 103 struct hashtab_node *cur; 104 105 slots_used = 0; 106 max_chain_len = 0; 107 for (i = 0; i < h->size; i++) { 108 cur = h->htable[i]; 109 if (cur) { 110 slots_used++; 111 chain_len = 0; 112 while (cur) { 113 chain_len++; 114 cur = cur->next; 115 } 116 117 if (chain_len > max_chain_len) 118 max_chain_len = chain_len; 119 } 120 } 121 122 info->slots_used = slots_used; 123 info->max_chain_len = max_chain_len; 124 } 125 126 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig, 127 int (*copy)(struct hashtab_node *new, 128 struct hashtab_node *orig, void *args), 129 int (*destroy)(void *k, void *d, void *args), 130 void *args) 131 { 132 struct hashtab_node *cur, *tmp, *tail; 133 int i, rc; 134 135 memset(new, 0, sizeof(*new)); 136 137 new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL); 138 if (!new->htable) 139 return -ENOMEM; 140 141 new->size = orig->size; 142 143 for (i = 0; i < orig->size; i++) { 144 tail = NULL; 145 for (cur = orig->htable[i]; cur; cur = cur->next) { 146 tmp = kmem_cache_zalloc(hashtab_node_cachep, 147 GFP_KERNEL); 148 if (!tmp) 149 goto error; 150 rc = copy(tmp, cur, args); 151 if (rc) { 152 kmem_cache_free(hashtab_node_cachep, tmp); 153 goto error; 154 } 155 tmp->next = NULL; 156 if (!tail) 157 new->htable[i] = tmp; 158 else 159 tail->next = tmp; 160 tail = tmp; 161 new->nel++; 162 } 163 } 164 165 return 0; 166 167 error: 168 for (i = 0; i < new->size; i++) { 169 for (cur = new->htable[i]; cur; cur = tmp) { 170 tmp = cur->next; 171 destroy(cur->key, cur->datum, args); 172 kmem_cache_free(hashtab_node_cachep, cur); 173 } 174 } 175 kmem_cache_free(hashtab_node_cachep, new); 176 return -ENOMEM; 177 } 178 179 void __init hashtab_cache_init(void) 180 { 181 hashtab_node_cachep = kmem_cache_create("hashtab_node", 182 sizeof(struct hashtab_node), 183 0, SLAB_PANIC, NULL); 184 } 185