1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
21da177e4SLinus Torvalds /*
31da177e4SLinus Torvalds * Implementation of the hash table type.
41da177e4SLinus Torvalds *
50fe53224SStephen Smalley * Author : Stephen Smalley, <stephen.smalley.work@gmail.com>
61da177e4SLinus Torvalds */
71da177e4SLinus Torvalds #include <linux/kernel.h>
81da177e4SLinus Torvalds #include <linux/slab.h>
91da177e4SLinus Torvalds #include <linux/errno.h>
101da177e4SLinus Torvalds #include "hashtab.h"
11e9fd7292SPaul Moore #include "security.h"
121da177e4SLinus Torvalds
13cd2bb4cbSOndrej Mosnacek static struct kmem_cache *hashtab_node_cachep __ro_after_init;
147c620eceSKyeongdon Kim
15e0ac568dSOndrej Mosnacek /*
16e0ac568dSOndrej Mosnacek * Here we simply round the number of elements up to the nearest power of two.
1763ddf1baSXiong Zhenwu * I tried also other options like rounding down or rounding to the closest
18e0ac568dSOndrej Mosnacek * power of two (up or down based on which is closer), but I was unable to
19e0ac568dSOndrej Mosnacek * find any significant difference in lookup/insert performance that would
20e0ac568dSOndrej Mosnacek * justify switching to a different (less intuitive) formula. It could be that
21e0ac568dSOndrej Mosnacek * a different formula is actually more optimal, but any future changes here
22e0ac568dSOndrej Mosnacek * should be supported with performance/memory usage data.
23e0ac568dSOndrej Mosnacek *
24e0ac568dSOndrej Mosnacek * The total memory used by the htable arrays (only) with Fedora policy loaded
25e0ac568dSOndrej Mosnacek * is approximately 163 KB at the time of writing.
26e0ac568dSOndrej Mosnacek */
hashtab_compute_size(u32 nel)27e0ac568dSOndrej Mosnacek static u32 hashtab_compute_size(u32 nel)
28e0ac568dSOndrej Mosnacek {
29e0ac568dSOndrej Mosnacek return nel == 0 ? 0 : roundup_pow_of_two(nel);
30e0ac568dSOndrej Mosnacek }
31e0ac568dSOndrej Mosnacek
hashtab_init(struct hashtab * h,u32 nel_hint)3224def7bbSOndrej Mosnacek int hashtab_init(struct hashtab *h, u32 nel_hint)
331da177e4SLinus Torvalds {
34dc27f3c5SOndrej Mosnacek u32 size = hashtab_compute_size(nel_hint);
351da177e4SLinus Torvalds
36dc27f3c5SOndrej Mosnacek /* should already be zeroed, but better be safe */
37dc27f3c5SOndrej Mosnacek h->nel = 0;
38dc27f3c5SOndrej Mosnacek h->size = 0;
39dc27f3c5SOndrej Mosnacek h->htable = NULL;
40dc27f3c5SOndrej Mosnacek
41dc27f3c5SOndrej Mosnacek if (size) {
42dc27f3c5SOndrej Mosnacek h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
43dc27f3c5SOndrej Mosnacek if (!h->htable)
44dc27f3c5SOndrej Mosnacek return -ENOMEM;
45dc27f3c5SOndrej Mosnacek h->size = size;
46dc27f3c5SOndrej Mosnacek }
47dc27f3c5SOndrej Mosnacek return 0;
481da177e4SLinus Torvalds }
491da177e4SLinus Torvalds
__hashtab_insert(struct hashtab * h,struct hashtab_node ** dst,void * key,void * datum)5054b27f92SOndrej Mosnacek int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
5154b27f92SOndrej Mosnacek void *key, void *datum)
521da177e4SLinus Torvalds {
5354b27f92SOndrej Mosnacek struct hashtab_node *newnode;
541da177e4SLinus Torvalds
557c620eceSKyeongdon Kim newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
56cb8d21e3SMarkus Elfring if (!newnode)
571da177e4SLinus Torvalds return -ENOMEM;
581da177e4SLinus Torvalds newnode->key = key;
591da177e4SLinus Torvalds newnode->datum = datum;
6054b27f92SOndrej Mosnacek newnode->next = *dst;
6154b27f92SOndrej Mosnacek *dst = newnode;
621da177e4SLinus Torvalds
631da177e4SLinus Torvalds h->nel++;
641da177e4SLinus Torvalds return 0;
651da177e4SLinus Torvalds }
661da177e4SLinus Torvalds
hashtab_destroy(struct hashtab * h)671da177e4SLinus Torvalds void hashtab_destroy(struct hashtab *h)
681da177e4SLinus Torvalds {
691da177e4SLinus Torvalds u32 i;
701da177e4SLinus Torvalds struct hashtab_node *cur, *temp;
711da177e4SLinus Torvalds
721da177e4SLinus Torvalds for (i = 0; i < h->size; i++) {
731da177e4SLinus Torvalds cur = h->htable[i];
74dbc74c65SVesa-Matti Kari while (cur) {
751da177e4SLinus Torvalds temp = cur;
761da177e4SLinus Torvalds cur = cur->next;
777c620eceSKyeongdon Kim kmem_cache_free(hashtab_node_cachep, temp);
781da177e4SLinus Torvalds }
791da177e4SLinus Torvalds h->htable[i] = NULL;
801da177e4SLinus Torvalds }
811da177e4SLinus Torvalds
821da177e4SLinus Torvalds kfree(h->htable);
831da177e4SLinus Torvalds h->htable = NULL;
841da177e4SLinus Torvalds }
851da177e4SLinus Torvalds
hashtab_map(struct hashtab * h,int (* apply)(void * k,void * d,void * args),void * args)861da177e4SLinus Torvalds int hashtab_map(struct hashtab *h,
871da177e4SLinus Torvalds int (*apply)(void *k, void *d, void *args),
881da177e4SLinus Torvalds void *args)
891da177e4SLinus Torvalds {
901da177e4SLinus Torvalds u32 i;
911da177e4SLinus Torvalds int ret;
921da177e4SLinus Torvalds struct hashtab_node *cur;
931da177e4SLinus Torvalds
941da177e4SLinus Torvalds for (i = 0; i < h->size; i++) {
951da177e4SLinus Torvalds cur = h->htable[i];
96dbc74c65SVesa-Matti Kari while (cur) {
971da177e4SLinus Torvalds ret = apply(cur->key, cur->datum, args);
981da177e4SLinus Torvalds if (ret)
991da177e4SLinus Torvalds return ret;
1001da177e4SLinus Torvalds cur = cur->next;
1011da177e4SLinus Torvalds }
1021da177e4SLinus Torvalds }
1031da177e4SLinus Torvalds return 0;
1041da177e4SLinus Torvalds }
1051da177e4SLinus Torvalds
106f01dd590SChristian Göttsche #ifdef CONFIG_SECURITY_SELINUX_DEBUG
hashtab_stat(struct hashtab * h,struct hashtab_info * info)1071da177e4SLinus Torvalds void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
1081da177e4SLinus Torvalds {
1091da177e4SLinus Torvalds u32 i, chain_len, slots_used, max_chain_len;
1101da177e4SLinus Torvalds struct hashtab_node *cur;
1111da177e4SLinus Torvalds
1121da177e4SLinus Torvalds slots_used = 0;
1131da177e4SLinus Torvalds max_chain_len = 0;
1145794ed76SColin Ian King for (i = 0; i < h->size; i++) {
1151da177e4SLinus Torvalds cur = h->htable[i];
1161da177e4SLinus Torvalds if (cur) {
1171da177e4SLinus Torvalds slots_used++;
1181da177e4SLinus Torvalds chain_len = 0;
1191da177e4SLinus Torvalds while (cur) {
1201da177e4SLinus Torvalds chain_len++;
1211da177e4SLinus Torvalds cur = cur->next;
1221da177e4SLinus Torvalds }
1231da177e4SLinus Torvalds
1241da177e4SLinus Torvalds if (chain_len > max_chain_len)
1251da177e4SLinus Torvalds max_chain_len = chain_len;
1261da177e4SLinus Torvalds }
1271da177e4SLinus Torvalds }
1281da177e4SLinus Torvalds
1291da177e4SLinus Torvalds info->slots_used = slots_used;
1301da177e4SLinus Torvalds info->max_chain_len = max_chain_len;
1311da177e4SLinus Torvalds }
132f01dd590SChristian Göttsche #endif /* CONFIG_SECURITY_SELINUX_DEBUG */
133aa8e712cSStephen Smalley
hashtab_duplicate(struct hashtab * new,struct hashtab * orig,int (* copy)(struct hashtab_node * new,struct hashtab_node * orig,void * args),int (* destroy)(void * k,void * d,void * args),void * args)134c7c556f1SStephen Smalley int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
135c7c556f1SStephen Smalley int (*copy)(struct hashtab_node *new,
136c7c556f1SStephen Smalley struct hashtab_node *orig, void *args),
137c7c556f1SStephen Smalley int (*destroy)(void *k, void *d, void *args),
138c7c556f1SStephen Smalley void *args)
139c7c556f1SStephen Smalley {
140c7c556f1SStephen Smalley struct hashtab_node *cur, *tmp, *tail;
141*c17c55c2SChristian Göttsche u32 i;
142*c17c55c2SChristian Göttsche int rc;
143c7c556f1SStephen Smalley
144c7c556f1SStephen Smalley memset(new, 0, sizeof(*new));
145c7c556f1SStephen Smalley
146c7c556f1SStephen Smalley new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
147c7c556f1SStephen Smalley if (!new->htable)
148c7c556f1SStephen Smalley return -ENOMEM;
149c7c556f1SStephen Smalley
150c7c556f1SStephen Smalley new->size = orig->size;
151c7c556f1SStephen Smalley
152c7c556f1SStephen Smalley for (i = 0; i < orig->size; i++) {
153c7c556f1SStephen Smalley tail = NULL;
154c7c556f1SStephen Smalley for (cur = orig->htable[i]; cur; cur = cur->next) {
155c7c556f1SStephen Smalley tmp = kmem_cache_zalloc(hashtab_node_cachep,
156c7c556f1SStephen Smalley GFP_KERNEL);
157c7c556f1SStephen Smalley if (!tmp)
158c7c556f1SStephen Smalley goto error;
159c7c556f1SStephen Smalley rc = copy(tmp, cur, args);
160c7c556f1SStephen Smalley if (rc) {
161c7c556f1SStephen Smalley kmem_cache_free(hashtab_node_cachep, tmp);
162c7c556f1SStephen Smalley goto error;
163c7c556f1SStephen Smalley }
164c7c556f1SStephen Smalley tmp->next = NULL;
165c7c556f1SStephen Smalley if (!tail)
166c7c556f1SStephen Smalley new->htable[i] = tmp;
167c7c556f1SStephen Smalley else
168c7c556f1SStephen Smalley tail->next = tmp;
169c7c556f1SStephen Smalley tail = tmp;
170c7c556f1SStephen Smalley new->nel++;
171c7c556f1SStephen Smalley }
172c7c556f1SStephen Smalley }
173c7c556f1SStephen Smalley
174c7c556f1SStephen Smalley return 0;
175c7c556f1SStephen Smalley
176c7c556f1SStephen Smalley error:
177c7c556f1SStephen Smalley for (i = 0; i < new->size; i++) {
178c7c556f1SStephen Smalley for (cur = new->htable[i]; cur; cur = tmp) {
179c7c556f1SStephen Smalley tmp = cur->next;
180c7c556f1SStephen Smalley destroy(cur->key, cur->datum, args);
181c7c556f1SStephen Smalley kmem_cache_free(hashtab_node_cachep, cur);
182c7c556f1SStephen Smalley }
183c7c556f1SStephen Smalley }
1846254bd3dSOndrej Mosnacek kfree(new->htable);
1856254bd3dSOndrej Mosnacek memset(new, 0, sizeof(*new));
186c7c556f1SStephen Smalley return -ENOMEM;
187c7c556f1SStephen Smalley }
188c7c556f1SStephen Smalley
hashtab_cache_init(void)189aa8e712cSStephen Smalley void __init hashtab_cache_init(void)
1907c620eceSKyeongdon Kim {
1917c620eceSKyeongdon Kim hashtab_node_cachep = kmem_cache_create("hashtab_node",
1927c620eceSKyeongdon Kim sizeof(struct hashtab_node),
1937c620eceSKyeongdon Kim 0, SLAB_PANIC, NULL);
1947c620eceSKyeongdon Kim }
195