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 */
hashtab_compute_size(u32 nel)28 static u32 hashtab_compute_size(u32 nel)
29 {
30 return nel == 0 ? 0 : roundup_pow_of_two(nel);
31 }
32
hashtab_init(struct hashtab * h,u32 nel_hint)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
__hashtab_insert(struct hashtab * h,struct hashtab_node ** dst,void * key,void * datum)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
hashtab_destroy(struct hashtab * h)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
hashtab_map(struct hashtab * h,int (* apply)(void * k,void * d,void * args),void * args)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
hashtab_stat(struct hashtab * h,struct hashtab_info * info)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
hashtab_duplicate(struct hashtab * new,const struct hashtab * orig,int (* copy)(struct hashtab_node * new,const struct hashtab_node * orig,void * args),int (* destroy)(void * k,void * d,void * args),void * args)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
hashtab_cache_init(void)196 void __init hashtab_cache_init(void)
197 {
198 hashtab_node_cachep = KMEM_CACHE(hashtab_node, SLAB_PANIC);
199 }
200