1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 21da177e4SLinus Torvalds /* 31da177e4SLinus Torvalds * Implementation of the hash table type. 41da177e4SLinus Torvalds * 57efbb60bSStephen Smalley * Author : Stephen Smalley, <sds@tycho.nsa.gov> 61da177e4SLinus Torvalds */ 71da177e4SLinus Torvalds #include <linux/kernel.h> 81da177e4SLinus Torvalds #include <linux/slab.h> 91da177e4SLinus Torvalds #include <linux/errno.h> 10ed1c9642SDave Jones #include <linux/sched.h> 111da177e4SLinus Torvalds #include "hashtab.h" 121da177e4SLinus Torvalds 137c620eceSKyeongdon Kim static struct kmem_cache *hashtab_node_cachep; 147c620eceSKyeongdon Kim 15e0ac568dSOndrej Mosnacek /* 16e0ac568dSOndrej Mosnacek * Here we simply round the number of elements up to the nearest power of two. 17e0ac568dSOndrej Mosnacek * I tried also other options like rouding 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 { 3403414a49SOndrej Mosnacek h->size = hashtab_compute_size(nel_hint); 3503414a49SOndrej Mosnacek h->nel = 0; 3603414a49SOndrej Mosnacek if (!h->size) 3703414a49SOndrej Mosnacek return 0; 381da177e4SLinus Torvalds 3903414a49SOndrej Mosnacek h->htable = kcalloc(h->size, sizeof(*h->htable), GFP_KERNEL); 4003414a49SOndrej Mosnacek return h->htable ? 0 : -ENOMEM; 411da177e4SLinus Torvalds } 421da177e4SLinus Torvalds 4324def7bbSOndrej Mosnacek int hashtab_insert(struct hashtab *h, void *key, void *datum, 4424def7bbSOndrej Mosnacek struct hashtab_key_params key_params) 451da177e4SLinus Torvalds { 461da177e4SLinus Torvalds u32 hvalue; 471da177e4SLinus Torvalds struct hashtab_node *prev, *cur, *newnode; 481da177e4SLinus Torvalds 49ed1c9642SDave Jones cond_resched(); 50ed1c9642SDave Jones 5103414a49SOndrej Mosnacek if (!h->size || h->nel == HASHTAB_MAX_NODES) 521da177e4SLinus Torvalds return -EINVAL; 531da177e4SLinus Torvalds 5424def7bbSOndrej Mosnacek hvalue = key_params.hash(key) & (h->size - 1); 551da177e4SLinus Torvalds prev = NULL; 561da177e4SLinus Torvalds cur = h->htable[hvalue]; 5724def7bbSOndrej Mosnacek while (cur) { 5824def7bbSOndrej Mosnacek int cmp = key_params.cmp(key, cur->key); 5924def7bbSOndrej Mosnacek 6024def7bbSOndrej Mosnacek if (cmp == 0) 6124def7bbSOndrej Mosnacek return -EEXIST; 6224def7bbSOndrej Mosnacek if (cmp < 0) 6324def7bbSOndrej Mosnacek break; 641da177e4SLinus Torvalds prev = cur; 651da177e4SLinus Torvalds cur = cur->next; 661da177e4SLinus Torvalds } 671da177e4SLinus Torvalds 687c620eceSKyeongdon Kim newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 69cb8d21e3SMarkus Elfring if (!newnode) 701da177e4SLinus Torvalds return -ENOMEM; 711da177e4SLinus Torvalds newnode->key = key; 721da177e4SLinus Torvalds newnode->datum = datum; 731da177e4SLinus Torvalds if (prev) { 741da177e4SLinus Torvalds newnode->next = prev->next; 751da177e4SLinus Torvalds prev->next = newnode; 761da177e4SLinus Torvalds } else { 771da177e4SLinus Torvalds newnode->next = h->htable[hvalue]; 781da177e4SLinus Torvalds h->htable[hvalue] = newnode; 791da177e4SLinus Torvalds } 801da177e4SLinus Torvalds 811da177e4SLinus Torvalds h->nel++; 821da177e4SLinus Torvalds return 0; 831da177e4SLinus Torvalds } 841da177e4SLinus Torvalds 8524def7bbSOndrej Mosnacek void *hashtab_search(struct hashtab *h, const void *key, 8624def7bbSOndrej Mosnacek struct hashtab_key_params key_params) 871da177e4SLinus Torvalds { 881da177e4SLinus Torvalds u32 hvalue; 891da177e4SLinus Torvalds struct hashtab_node *cur; 901da177e4SLinus Torvalds 9103414a49SOndrej Mosnacek if (!h->size) 921da177e4SLinus Torvalds return NULL; 931da177e4SLinus Torvalds 9424def7bbSOndrej Mosnacek hvalue = key_params.hash(key) & (h->size - 1); 951da177e4SLinus Torvalds cur = h->htable[hvalue]; 9624def7bbSOndrej Mosnacek while (cur) { 9724def7bbSOndrej Mosnacek int cmp = key_params.cmp(key, cur->key); 981da177e4SLinus Torvalds 9924def7bbSOndrej Mosnacek if (cmp == 0) 1001da177e4SLinus Torvalds return cur->datum; 10124def7bbSOndrej Mosnacek if (cmp < 0) 10224def7bbSOndrej Mosnacek break; 10324def7bbSOndrej Mosnacek cur = cur->next; 10424def7bbSOndrej Mosnacek } 10524def7bbSOndrej Mosnacek return NULL; 1061da177e4SLinus Torvalds } 1071da177e4SLinus Torvalds 1081da177e4SLinus Torvalds void hashtab_destroy(struct hashtab *h) 1091da177e4SLinus Torvalds { 1101da177e4SLinus Torvalds u32 i; 1111da177e4SLinus Torvalds struct hashtab_node *cur, *temp; 1121da177e4SLinus Torvalds 1131da177e4SLinus Torvalds for (i = 0; i < h->size; i++) { 1141da177e4SLinus Torvalds cur = h->htable[i]; 115dbc74c65SVesa-Matti Kari while (cur) { 1161da177e4SLinus Torvalds temp = cur; 1171da177e4SLinus Torvalds cur = cur->next; 1187c620eceSKyeongdon Kim kmem_cache_free(hashtab_node_cachep, temp); 1191da177e4SLinus Torvalds } 1201da177e4SLinus Torvalds h->htable[i] = NULL; 1211da177e4SLinus Torvalds } 1221da177e4SLinus Torvalds 1231da177e4SLinus Torvalds kfree(h->htable); 1241da177e4SLinus Torvalds h->htable = NULL; 1251da177e4SLinus Torvalds } 1261da177e4SLinus Torvalds 1271da177e4SLinus Torvalds int hashtab_map(struct hashtab *h, 1281da177e4SLinus Torvalds int (*apply)(void *k, void *d, void *args), 1291da177e4SLinus Torvalds void *args) 1301da177e4SLinus Torvalds { 1311da177e4SLinus Torvalds u32 i; 1321da177e4SLinus Torvalds int ret; 1331da177e4SLinus Torvalds struct hashtab_node *cur; 1341da177e4SLinus Torvalds 1351da177e4SLinus Torvalds for (i = 0; i < h->size; i++) { 1361da177e4SLinus Torvalds cur = h->htable[i]; 137dbc74c65SVesa-Matti Kari while (cur) { 1381da177e4SLinus Torvalds ret = apply(cur->key, cur->datum, args); 1391da177e4SLinus Torvalds if (ret) 1401da177e4SLinus Torvalds return ret; 1411da177e4SLinus Torvalds cur = cur->next; 1421da177e4SLinus Torvalds } 1431da177e4SLinus Torvalds } 1441da177e4SLinus Torvalds return 0; 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds 1471da177e4SLinus Torvalds 1481da177e4SLinus Torvalds void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 1491da177e4SLinus Torvalds { 1501da177e4SLinus Torvalds u32 i, chain_len, slots_used, max_chain_len; 1511da177e4SLinus Torvalds struct hashtab_node *cur; 1521da177e4SLinus Torvalds 1531da177e4SLinus Torvalds slots_used = 0; 1541da177e4SLinus Torvalds max_chain_len = 0; 1555794ed76SColin Ian King for (i = 0; i < h->size; i++) { 1561da177e4SLinus Torvalds cur = h->htable[i]; 1571da177e4SLinus Torvalds if (cur) { 1581da177e4SLinus Torvalds slots_used++; 1591da177e4SLinus Torvalds chain_len = 0; 1601da177e4SLinus Torvalds while (cur) { 1611da177e4SLinus Torvalds chain_len++; 1621da177e4SLinus Torvalds cur = cur->next; 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds if (chain_len > max_chain_len) 1661da177e4SLinus Torvalds max_chain_len = chain_len; 1671da177e4SLinus Torvalds } 1681da177e4SLinus Torvalds } 1691da177e4SLinus Torvalds 1701da177e4SLinus Torvalds info->slots_used = slots_used; 1711da177e4SLinus Torvalds info->max_chain_len = max_chain_len; 1721da177e4SLinus Torvalds } 173aa8e712cSStephen Smalley 174aa8e712cSStephen Smalley void __init hashtab_cache_init(void) 1757c620eceSKyeongdon Kim { 1767c620eceSKyeongdon Kim hashtab_node_cachep = kmem_cache_create("hashtab_node", 1777c620eceSKyeongdon Kim sizeof(struct hashtab_node), 1787c620eceSKyeongdon Kim 0, SLAB_PANIC, NULL); 1797c620eceSKyeongdon Kim } 180