1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Implementation of the hash table type. 4 * 5 * Author : Stephen Smalley, <stephen.smalley.work@gmail.com> 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 #ifdef CONFIG_SECURITY_SELINUX_DEBUG 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 #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ 133 134 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig, 135 int (*copy)(struct hashtab_node *new, 136 struct hashtab_node *orig, void *args), 137 int (*destroy)(void *k, void *d, void *args), 138 void *args) 139 { 140 struct hashtab_node *cur, *tmp, *tail; 141 u32 i; 142 int rc; 143 144 memset(new, 0, sizeof(*new)); 145 146 new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL); 147 if (!new->htable) 148 return -ENOMEM; 149 150 new->size = orig->size; 151 152 for (i = 0; i < orig->size; i++) { 153 tail = NULL; 154 for (cur = orig->htable[i]; cur; cur = cur->next) { 155 tmp = kmem_cache_zalloc(hashtab_node_cachep, 156 GFP_KERNEL); 157 if (!tmp) 158 goto error; 159 rc = copy(tmp, cur, args); 160 if (rc) { 161 kmem_cache_free(hashtab_node_cachep, tmp); 162 goto error; 163 } 164 tmp->next = NULL; 165 if (!tail) 166 new->htable[i] = tmp; 167 else 168 tail->next = tmp; 169 tail = tmp; 170 new->nel++; 171 } 172 } 173 174 return 0; 175 176 error: 177 for (i = 0; i < new->size; i++) { 178 for (cur = new->htable[i]; cur; cur = tmp) { 179 tmp = cur->next; 180 destroy(cur->key, cur->datum, args); 181 kmem_cache_free(hashtab_node_cachep, cur); 182 } 183 } 184 kfree(new->htable); 185 memset(new, 0, sizeof(*new)); 186 return -ENOMEM; 187 } 188 189 void __init hashtab_cache_init(void) 190 { 191 hashtab_node_cachep = kmem_cache_create("hashtab_node", 192 sizeof(struct hashtab_node), 193 0, SLAB_PANIC, NULL); 194 } 195