1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Implementation of the hash table type. 4 * 5 * Author : Stephen Smalley, <sds@tycho.nsa.gov> 6 */ 7 #include <linux/kernel.h> 8 #include <linux/slab.h> 9 #include <linux/errno.h> 10 #include "hashtab.h" 11 12 static struct kmem_cache *hashtab_node_cachep; 13 14 /* 15 * Here we simply round the number of elements up to the nearest power of two. 16 * I tried also other options like rouding down or rounding to the closest 17 * power of two (up or down based on which is closer), but I was unable to 18 * find any significant difference in lookup/insert performance that would 19 * justify switching to a different (less intuitive) formula. It could be that 20 * a different formula is actually more optimal, but any future changes here 21 * should be supported with performance/memory usage data. 22 * 23 * The total memory used by the htable arrays (only) with Fedora policy loaded 24 * is approximately 163 KB at the time of writing. 25 */ 26 static u32 hashtab_compute_size(u32 nel) 27 { 28 return nel == 0 ? 0 : roundup_pow_of_two(nel); 29 } 30 31 int hashtab_init(struct hashtab *h, u32 nel_hint) 32 { 33 h->size = hashtab_compute_size(nel_hint); 34 h->nel = 0; 35 if (!h->size) 36 return 0; 37 38 h->htable = kcalloc(h->size, sizeof(*h->htable), GFP_KERNEL); 39 return h->htable ? 0 : -ENOMEM; 40 } 41 42 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, 43 void *key, void *datum) 44 { 45 struct hashtab_node *newnode; 46 47 newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 48 if (!newnode) 49 return -ENOMEM; 50 newnode->key = key; 51 newnode->datum = datum; 52 newnode->next = *dst; 53 *dst = newnode; 54 55 h->nel++; 56 return 0; 57 } 58 59 void hashtab_destroy(struct hashtab *h) 60 { 61 u32 i; 62 struct hashtab_node *cur, *temp; 63 64 for (i = 0; i < h->size; i++) { 65 cur = h->htable[i]; 66 while (cur) { 67 temp = cur; 68 cur = cur->next; 69 kmem_cache_free(hashtab_node_cachep, temp); 70 } 71 h->htable[i] = NULL; 72 } 73 74 kfree(h->htable); 75 h->htable = NULL; 76 } 77 78 int hashtab_map(struct hashtab *h, 79 int (*apply)(void *k, void *d, void *args), 80 void *args) 81 { 82 u32 i; 83 int ret; 84 struct hashtab_node *cur; 85 86 for (i = 0; i < h->size; i++) { 87 cur = h->htable[i]; 88 while (cur) { 89 ret = apply(cur->key, cur->datum, args); 90 if (ret) 91 return ret; 92 cur = cur->next; 93 } 94 } 95 return 0; 96 } 97 98 99 void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 100 { 101 u32 i, chain_len, slots_used, max_chain_len; 102 struct hashtab_node *cur; 103 104 slots_used = 0; 105 max_chain_len = 0; 106 for (i = 0; i < h->size; i++) { 107 cur = h->htable[i]; 108 if (cur) { 109 slots_used++; 110 chain_len = 0; 111 while (cur) { 112 chain_len++; 113 cur = cur->next; 114 } 115 116 if (chain_len > max_chain_len) 117 max_chain_len = chain_len; 118 } 119 } 120 121 info->slots_used = slots_used; 122 info->max_chain_len = max_chain_len; 123 } 124 125 void __init hashtab_cache_init(void) 126 { 127 hashtab_node_cachep = kmem_cache_create("hashtab_node", 128 sizeof(struct hashtab_node), 129 0, SLAB_PANIC, NULL); 130 } 131