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: 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(n: size, 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(k: 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(s: hashtab_node_cachep, objp: temp); |
78 | } |
79 | h->htable[i] = NULL; |
80 | } |
81 | |
82 | kfree(objp: 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(n: orig->size, 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(k: 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(s: hashtab_node_cachep, objp: 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(s: hashtab_node_cachep, objp: cur); |
187 | } |
188 | } |
189 | kfree(objp: 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(name: "hashtab_node" , |
197 | size: sizeof(struct hashtab_node), |
198 | align: 0, SLAB_PANIC, NULL); |
199 | } |
200 | |