]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1da177e4 LT |
2 | /* |
3 | * Implementation of the hash table type. | |
4 | * | |
0fe53224 | 5 | * Author : Stephen Smalley, <stephen.smalley.work@gmail.com> |
1da177e4 | 6 | */ |
dfd9bb40 | 7 | |
1da177e4 LT |
8 | #include <linux/kernel.h> |
9 | #include <linux/slab.h> | |
10 | #include <linux/errno.h> | |
11 | #include "hashtab.h" | |
e9fd7292 | 12 | #include "security.h" |
1da177e4 | 13 | |
cd2bb4cb | 14 | static struct kmem_cache *hashtab_node_cachep __ro_after_init; |
7c620ece | 15 | |
e0ac568d OM |
16 | /* |
17 | * Here we simply round the number of elements up to the nearest power of two. | |
63ddf1ba | 18 | * I tried also other options like rounding down or rounding to the closest |
e0ac568d OM |
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 | ||
24def7bb | 33 | int hashtab_init(struct hashtab *h, u32 nel_hint) |
1da177e4 | 34 | { |
dc27f3c5 OM |
35 | u32 size = hashtab_compute_size(nel_hint); |
36 | ||
37 | /* should already be zeroed, but better be safe */ | |
03414a49 | 38 | h->nel = 0; |
dc27f3c5 OM |
39 | h->size = 0; |
40 | h->htable = NULL; | |
1da177e4 | 41 | |
dc27f3c5 OM |
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; | |
1da177e4 LT |
49 | } |
50 | ||
dfd9bb40 PM |
51 | int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, void *key, |
52 | void *datum) | |
1da177e4 | 53 | { |
54b27f92 | 54 | struct hashtab_node *newnode; |
1da177e4 | 55 | |
7c620ece | 56 | newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); |
cb8d21e3 | 57 | if (!newnode) |
1da177e4 | 58 | return -ENOMEM; |
1da177e4 LT |
59 | newnode->key = key; |
60 | newnode->datum = datum; | |
54b27f92 OM |
61 | newnode->next = *dst; |
62 | *dst = newnode; | |
1da177e4 LT |
63 | |
64 | h->nel++; | |
65 | return 0; | |
66 | } | |
67 | ||
1da177e4 LT |
68 | void hashtab_destroy(struct hashtab *h) |
69 | { | |
70 | u32 i; | |
71 | struct hashtab_node *cur, *temp; | |
72 | ||
1da177e4 LT |
73 | for (i = 0; i < h->size; i++) { |
74 | cur = h->htable[i]; | |
dbc74c65 | 75 | while (cur) { |
1da177e4 LT |
76 | temp = cur; |
77 | cur = cur->next; | |
7c620ece | 78 | kmem_cache_free(hashtab_node_cachep, temp); |
1da177e4 LT |
79 | } |
80 | h->htable[i] = NULL; | |
81 | } | |
82 | ||
83 | kfree(h->htable); | |
84 | h->htable = NULL; | |
1da177e4 LT |
85 | } |
86 | ||
dfd9bb40 | 87 | int hashtab_map(struct hashtab *h, int (*apply)(void *k, void *d, void *args), |
1da177e4 LT |
88 | void *args) |
89 | { | |
90 | u32 i; | |
91 | int ret; | |
92 | struct hashtab_node *cur; | |
93 | ||
1da177e4 LT |
94 | for (i = 0; i < h->size; i++) { |
95 | cur = h->htable[i]; | |
dbc74c65 | 96 | while (cur) { |
1da177e4 LT |
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 | ||
f01dd590 | 106 | #ifdef CONFIG_SECURITY_SELINUX_DEBUG |
1da177e4 LT |
107 | void hashtab_stat(struct hashtab *h, struct hashtab_info *info) |
108 | { | |
109 | u32 i, chain_len, slots_used, max_chain_len; | |
fb8142ff | 110 | u64 chain2_len_sum; |
1da177e4 LT |
111 | struct hashtab_node *cur; |
112 | ||
113 | slots_used = 0; | |
114 | max_chain_len = 0; | |
fb8142ff | 115 | chain2_len_sum = 0; |
5794ed76 | 116 | for (i = 0; i < h->size; i++) { |
1da177e4 LT |
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; | |
fb8142ff CG |
128 | |
129 | chain2_len_sum += (u64)chain_len * chain_len; | |
1da177e4 LT |
130 | } |
131 | } | |
132 | ||
133 | info->slots_used = slots_used; | |
134 | info->max_chain_len = max_chain_len; | |
fb8142ff | 135 | info->chain2_len_sum = chain2_len_sum; |
1da177e4 | 136 | } |
f01dd590 | 137 | #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ |
aa8e712c | 138 | |
581646c3 | 139 | int hashtab_duplicate(struct hashtab *new, const struct hashtab *orig, |
dfd9bb40 | 140 | int (*copy)(struct hashtab_node *new, |
581646c3 | 141 | const struct hashtab_node *orig, void *args), |
dfd9bb40 | 142 | int (*destroy)(void *k, void *d, void *args), void *args) |
c7c556f1 | 143 | { |
581646c3 | 144 | const struct hashtab_node *orig_cur; |
c7c556f1 | 145 | struct hashtab_node *cur, *tmp, *tail; |
c17c55c2 CG |
146 | u32 i; |
147 | int rc; | |
c7c556f1 SS |
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; | |
581646c3 CG |
159 | for (orig_cur = orig->htable[i]; orig_cur; |
160 | orig_cur = orig_cur->next) { | |
c7c556f1 SS |
161 | tmp = kmem_cache_zalloc(hashtab_node_cachep, |
162 | GFP_KERNEL); | |
163 | if (!tmp) | |
164 | goto error; | |
581646c3 | 165 | rc = copy(tmp, orig_cur, args); |
c7c556f1 SS |
166 | if (rc) { |
167 | kmem_cache_free(hashtab_node_cachep, tmp); | |
168 | goto error; | |
169 | } | |
170 | tmp->next = NULL; | |
171 | if (!tail) | |
172 | new->htable[i] = tmp; | |
173 | else | |
174 | tail->next = tmp; | |
175 | tail = tmp; | |
176 | new->nel++; | |
177 | } | |
178 | } | |
179 | ||
180 | return 0; | |
181 | ||
dfd9bb40 | 182 | error: |
c7c556f1 SS |
183 | for (i = 0; i < new->size; i++) { |
184 | for (cur = new->htable[i]; cur; cur = tmp) { | |
185 | tmp = cur->next; | |
186 | destroy(cur->key, cur->datum, args); | |
187 | kmem_cache_free(hashtab_node_cachep, cur); | |
188 | } | |
189 | } | |
6254bd3d OM |
190 | kfree(new->htable); |
191 | memset(new, 0, sizeof(*new)); | |
c7c556f1 SS |
192 | return -ENOMEM; |
193 | } | |
194 | ||
aa8e712c | 195 | void __init hashtab_cache_init(void) |
7c620ece | 196 | { |
dfd9bb40 PM |
197 | hashtab_node_cachep = kmem_cache_create("hashtab_node", |
198 | sizeof(struct hashtab_node), 0, | |
199 | SLAB_PANIC, NULL); | |
7c620ece | 200 | } |