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 8 #include <linux/kernel.h> 9 #include <linux/slab.h> 10 #include <linux/errno.h> 11 #include "hashtab.h" 12 #include "security.h" 13 14 static struct kmem_cache *hashtab_node_cachep __ro_after_init; 15 16 /* 17 * Here we simply round the number of elements up to the nearest power of two. 18 * I tried also other options like rounding down or rounding to the closest 19 * power of two (up or down based on which is closer), but I was unable to 20 * find any significant difference in lookup/insert performance that would 21 * justify switching to a different (less intuitive) formula. It could be that 22 * a different formula is actually more optimal, but any future changes here 23 * should be supported with performance/memory usage data. 24 * 25 * The total memory used by the htable arrays (only) with Fedora policy loaded 26 * is approximately 163 KB at the time of writing. 27 */ 28 static u32 hashtab_compute_size(u32 nel) 29 { 30 return nel == 0 ? 0 : roundup_pow_of_two(nel); 31 } 32 33 int hashtab_init(struct hashtab *h, u32 nel_hint) 34 { 35 u32 size = hashtab_compute_size(nel_hint); 36 37 /* should already be zeroed, but better be safe */ 38 h->nel = 0; 39 h->size = 0; 40 h->htable = NULL; 41 42 if (size) { 43 h->htable = kcalloc(size, sizeof(*h->htable), 44 GFP_KERNEL | __GFP_NOWARN); 45 if (!h->htable) 46 return -ENOMEM; 47 h->size = size; 48 } 49 return 0; 50 } 51 52 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, void *key, 53 void *datum) 54 { 55 struct hashtab_node *newnode; 56 57 newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 58 if (!newnode) 59 return -ENOMEM; 60 newnode->key = key; 61 newnode->datum = datum; 62 newnode->next = *dst; 63 *dst = newnode; 64 65 h->nel++; 66 return 0; 67 } 68 69 void hashtab_destroy(struct hashtab *h) 70 { 71 u32 i; 72 struct hashtab_node *cur, *temp; 73 74 for (i = 0; i < h->size; i++) { 75 cur = h->htable[i]; 76 while (cur) { 77 temp = cur; 78 cur = cur->next; 79 kmem_cache_free(hashtab_node_cachep, temp); 80 } 81 h->htable[i] = NULL; 82 } 83 84 kfree(h->htable); 85 h->htable = NULL; 86 } 87 88 int hashtab_map(struct hashtab *h, int (*apply)(void *k, void *d, void *args), 89 void *args) 90 { 91 u32 i; 92 int ret; 93 struct hashtab_node *cur; 94 95 for (i = 0; i < h->size; i++) { 96 cur = h->htable[i]; 97 while (cur) { 98 ret = apply(cur->key, cur->datum, args); 99 if (ret) 100 return ret; 101 cur = cur->next; 102 } 103 } 104 return 0; 105 } 106 107 #ifdef CONFIG_SECURITY_SELINUX_DEBUG 108 void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 109 { 110 u32 i, chain_len, slots_used, max_chain_len; 111 u64 chain2_len_sum; 112 struct hashtab_node *cur; 113 114 slots_used = 0; 115 max_chain_len = 0; 116 chain2_len_sum = 0; 117 for (i = 0; i < h->size; i++) { 118 cur = h->htable[i]; 119 if (cur) { 120 slots_used++; 121 chain_len = 0; 122 while (cur) { 123 chain_len++; 124 cur = cur->next; 125 } 126 127 if (chain_len > max_chain_len) 128 max_chain_len = chain_len; 129 130 chain2_len_sum += (u64)chain_len * chain_len; 131 } 132 } 133 134 info->slots_used = slots_used; 135 info->max_chain_len = max_chain_len; 136 info->chain2_len_sum = chain2_len_sum; 137 } 138 #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ 139 140 int hashtab_duplicate(struct hashtab *new, const struct hashtab *orig, 141 int (*copy)(struct hashtab_node *new, 142 const struct hashtab_node *orig, void *args), 143 int (*destroy)(void *k, void *d, void *args), void *args) 144 { 145 const struct hashtab_node *orig_cur; 146 struct hashtab_node *cur, *tmp, *tail; 147 u32 i; 148 int rc; 149 150 memset(new, 0, sizeof(*new)); 151 152 new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL); 153 if (!new->htable) 154 return -ENOMEM; 155 156 new->size = orig->size; 157 158 for (i = 0; i < orig->size; i++) { 159 tail = NULL; 160 for (orig_cur = orig->htable[i]; orig_cur; 161 orig_cur = orig_cur->next) { 162 tmp = kmem_cache_zalloc(hashtab_node_cachep, 163 GFP_KERNEL); 164 if (!tmp) 165 goto error; 166 rc = copy(tmp, orig_cur, args); 167 if (rc) { 168 kmem_cache_free(hashtab_node_cachep, tmp); 169 goto error; 170 } 171 tmp->next = NULL; 172 if (!tail) 173 new->htable[i] = tmp; 174 else 175 tail->next = tmp; 176 tail = tmp; 177 new->nel++; 178 } 179 } 180 181 return 0; 182 183 error: 184 for (i = 0; i < new->size; i++) { 185 for (cur = new->htable[i]; cur; cur = tmp) { 186 tmp = cur->next; 187 destroy(cur->key, cur->datum, args); 188 kmem_cache_free(hashtab_node_cachep, cur); 189 } 190 } 191 kfree(new->htable); 192 memset(new, 0, sizeof(*new)); 193 return -ENOMEM; 194 } 195 196 void __init hashtab_cache_init(void) 197 { 198 hashtab_node_cachep = KMEM_CACHE(hashtab_node, SLAB_PANIC); 199 } 200