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 u64 chain2_len_sum; 111 struct hashtab_node *cur; 112 113 slots_used = 0; 114 max_chain_len = 0; 115 chain2_len_sum = 0; 116 for (i = 0; i < h->size; i++) { 117 cur = h->htable[i]; 118 if (cur) { 119 slots_used++; 120 chain_len = 0; 121 while (cur) { 122 chain_len++; 123 cur = cur->next; 124 } 125 126 if (chain_len > max_chain_len) 127 max_chain_len = chain_len; 128 129 chain2_len_sum += (u64)chain_len * chain_len; 130 } 131 } 132 133 info->slots_used = slots_used; 134 info->max_chain_len = max_chain_len; 135 info->chain2_len_sum = chain2_len_sum; 136 } 137 #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ 138 139 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig, 140 int (*copy)(struct hashtab_node *new, 141 struct hashtab_node *orig, void *args), 142 int (*destroy)(void *k, void *d, void *args), 143 void *args) 144 { 145 struct hashtab_node *cur, *tmp, *tail; 146 u32 i; 147 int rc; 148 149 memset(new, 0, sizeof(*new)); 150 151 new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL); 152 if (!new->htable) 153 return -ENOMEM; 154 155 new->size = orig->size; 156 157 for (i = 0; i < orig->size; i++) { 158 tail = NULL; 159 for (cur = orig->htable[i]; cur; cur = cur->next) { 160 tmp = kmem_cache_zalloc(hashtab_node_cachep, 161 GFP_KERNEL); 162 if (!tmp) 163 goto error; 164 rc = copy(tmp, cur, args); 165 if (rc) { 166 kmem_cache_free(hashtab_node_cachep, tmp); 167 goto error; 168 } 169 tmp->next = NULL; 170 if (!tail) 171 new->htable[i] = tmp; 172 else 173 tail->next = tmp; 174 tail = tmp; 175 new->nel++; 176 } 177 } 178 179 return 0; 180 181 error: 182 for (i = 0; i < new->size; i++) { 183 for (cur = new->htable[i]; cur; cur = tmp) { 184 tmp = cur->next; 185 destroy(cur->key, cur->datum, args); 186 kmem_cache_free(hashtab_node_cachep, cur); 187 } 188 } 189 kfree(new->htable); 190 memset(new, 0, sizeof(*new)); 191 return -ENOMEM; 192 } 193 194 void __init hashtab_cache_init(void) 195 { 196 hashtab_node_cachep = kmem_cache_create("hashtab_node", 197 sizeof(struct hashtab_node), 198 0, SLAB_PANIC, NULL); 199 } 200