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