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 */ 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 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 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 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 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 106*f01dd590SChristian Göttsche #ifdef CONFIG_SECURITY_SELINUX_DEBUG 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 } 132*f01dd590SChristian Göttsche #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ 133aa8e712cSStephen Smalley 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; 141c7c556f1SStephen Smalley int i, rc; 142c7c556f1SStephen Smalley 143c7c556f1SStephen Smalley memset(new, 0, sizeof(*new)); 144c7c556f1SStephen Smalley 145c7c556f1SStephen Smalley new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL); 146c7c556f1SStephen Smalley if (!new->htable) 147c7c556f1SStephen Smalley return -ENOMEM; 148c7c556f1SStephen Smalley 149c7c556f1SStephen Smalley new->size = orig->size; 150c7c556f1SStephen Smalley 151c7c556f1SStephen Smalley for (i = 0; i < orig->size; i++) { 152c7c556f1SStephen Smalley tail = NULL; 153c7c556f1SStephen Smalley for (cur = orig->htable[i]; cur; cur = cur->next) { 154c7c556f1SStephen Smalley tmp = kmem_cache_zalloc(hashtab_node_cachep, 155c7c556f1SStephen Smalley GFP_KERNEL); 156c7c556f1SStephen Smalley if (!tmp) 157c7c556f1SStephen Smalley goto error; 158c7c556f1SStephen Smalley rc = copy(tmp, cur, args); 159c7c556f1SStephen Smalley if (rc) { 160c7c556f1SStephen Smalley kmem_cache_free(hashtab_node_cachep, tmp); 161c7c556f1SStephen Smalley goto error; 162c7c556f1SStephen Smalley } 163c7c556f1SStephen Smalley tmp->next = NULL; 164c7c556f1SStephen Smalley if (!tail) 165c7c556f1SStephen Smalley new->htable[i] = tmp; 166c7c556f1SStephen Smalley else 167c7c556f1SStephen Smalley tail->next = tmp; 168c7c556f1SStephen Smalley tail = tmp; 169c7c556f1SStephen Smalley new->nel++; 170c7c556f1SStephen Smalley } 171c7c556f1SStephen Smalley } 172c7c556f1SStephen Smalley 173c7c556f1SStephen Smalley return 0; 174c7c556f1SStephen Smalley 175c7c556f1SStephen Smalley error: 176c7c556f1SStephen Smalley for (i = 0; i < new->size; i++) { 177c7c556f1SStephen Smalley for (cur = new->htable[i]; cur; cur = tmp) { 178c7c556f1SStephen Smalley tmp = cur->next; 179c7c556f1SStephen Smalley destroy(cur->key, cur->datum, args); 180c7c556f1SStephen Smalley kmem_cache_free(hashtab_node_cachep, cur); 181c7c556f1SStephen Smalley } 182c7c556f1SStephen Smalley } 1836254bd3dSOndrej Mosnacek kfree(new->htable); 1846254bd3dSOndrej Mosnacek memset(new, 0, sizeof(*new)); 185c7c556f1SStephen Smalley return -ENOMEM; 186c7c556f1SStephen Smalley } 187c7c556f1SStephen Smalley 188aa8e712cSStephen Smalley void __init hashtab_cache_init(void) 1897c620eceSKyeongdon Kim { 1907c620eceSKyeongdon Kim hashtab_node_cachep = kmem_cache_create("hashtab_node", 1917c620eceSKyeongdon Kim sizeof(struct hashtab_node), 1927c620eceSKyeongdon Kim 0, SLAB_PANIC, NULL); 1937c620eceSKyeongdon Kim } 194