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), GFP_KERNEL); 44 if (!h->htable) 45 return -ENOMEM; 46 h->size = size; 47 } 48 return 0; 49 } 50 51 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, void *key, 52 void *datum) 53 { 54 struct hashtab_node *newnode; 55 56 newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 57 if (!newnode) 58 return -ENOMEM; 59 newnode->key = key; 60 newnode->datum = datum; 61 newnode->next = *dst; 62 *dst = newnode; 63 64 h->nel++; 65 return 0; 66 } 67 68 void hashtab_destroy(struct hashtab *h) 69 { 70 u32 i; 71 struct hashtab_node *cur, *temp; 72 73 for (i = 0; i < h->size; i++) { 74 cur = h->htable[i]; 75 while (cur) { 76 temp = cur; 77 cur = cur->next; 78 kmem_cache_free(hashtab_node_cachep, temp); 79 } 80 h->htable[i] = NULL; 81 } 82 83 kfree(h->htable); 84 h->htable = NULL; 85 } 86 87 int hashtab_map(struct hashtab *h, 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), void *args) 143 { 144 struct hashtab_node *cur, *tmp, *tail; 145 u32 i; 146 int rc; 147 148 memset(new, 0, sizeof(*new)); 149 150 new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL); 151 if (!new->htable) 152 return -ENOMEM; 153 154 new->size = orig->size; 155 156 for (i = 0; i < orig->size; i++) { 157 tail = NULL; 158 for (cur = orig->htable[i]; cur; cur = cur->next) { 159 tmp = kmem_cache_zalloc(hashtab_node_cachep, 160 GFP_KERNEL); 161 if (!tmp) 162 goto error; 163 rc = copy(tmp, cur, args); 164 if (rc) { 165 kmem_cache_free(hashtab_node_cachep, tmp); 166 goto error; 167 } 168 tmp->next = NULL; 169 if (!tail) 170 new->htable[i] = tmp; 171 else 172 tail->next = tmp; 173 tail = tmp; 174 new->nel++; 175 } 176 } 177 178 return 0; 179 180 error: 181 for (i = 0; i < new->size; i++) { 182 for (cur = new->htable[i]; cur; cur = tmp) { 183 tmp = cur->next; 184 destroy(cur->key, cur->datum, args); 185 kmem_cache_free(hashtab_node_cachep, cur); 186 } 187 } 188 kfree(new->htable); 189 memset(new, 0, sizeof(*new)); 190 return -ENOMEM; 191 } 192 193 void __init hashtab_cache_init(void) 194 { 195 hashtab_node_cachep = kmem_cache_create("hashtab_node", 196 sizeof(struct hashtab_node), 0, 197 SLAB_PANIC, NULL); 198 } 199