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 <linux/sched.h> 11 #include "hashtab.h" 12 13 static struct kmem_cache *hashtab_node_cachep; 14 15 /* 16 * Here we simply round the number of elements up to the nearest power of two. 17 * I tried also other options like rouding down or rounding to the closest 18 * power of two (up or down based on which is closer), but I was unable to 19 * find any significant difference in lookup/insert performance that would 20 * justify switching to a different (less intuitive) formula. It could be that 21 * a different formula is actually more optimal, but any future changes here 22 * should be supported with performance/memory usage data. 23 * 24 * The total memory used by the htable arrays (only) with Fedora policy loaded 25 * is approximately 163 KB at the time of writing. 26 */ 27 static u32 hashtab_compute_size(u32 nel) 28 { 29 return nel == 0 ? 0 : roundup_pow_of_two(nel); 30 } 31 32 int hashtab_init(struct hashtab *h, 33 u32 (*hash_value)(struct hashtab *h, const void *key), 34 int (*keycmp)(struct hashtab *h, const void *key1, 35 const void *key2), 36 u32 nel_hint) 37 { 38 h->size = hashtab_compute_size(nel_hint); 39 h->nel = 0; 40 h->hash_value = hash_value; 41 h->keycmp = keycmp; 42 if (!h->size) 43 return 0; 44 45 h->htable = kcalloc(h->size, sizeof(*h->htable), GFP_KERNEL); 46 return h->htable ? 0 : -ENOMEM; 47 } 48 49 int hashtab_insert(struct hashtab *h, void *key, void *datum) 50 { 51 u32 hvalue; 52 struct hashtab_node *prev, *cur, *newnode; 53 54 cond_resched(); 55 56 if (!h->size || h->nel == HASHTAB_MAX_NODES) 57 return -EINVAL; 58 59 hvalue = h->hash_value(h, key); 60 prev = NULL; 61 cur = h->htable[hvalue]; 62 while (cur && h->keycmp(h, key, cur->key) > 0) { 63 prev = cur; 64 cur = cur->next; 65 } 66 67 if (cur && (h->keycmp(h, key, cur->key) == 0)) 68 return -EEXIST; 69 70 newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 71 if (!newnode) 72 return -ENOMEM; 73 newnode->key = key; 74 newnode->datum = datum; 75 if (prev) { 76 newnode->next = prev->next; 77 prev->next = newnode; 78 } else { 79 newnode->next = h->htable[hvalue]; 80 h->htable[hvalue] = newnode; 81 } 82 83 h->nel++; 84 return 0; 85 } 86 87 void *hashtab_search(struct hashtab *h, const void *key) 88 { 89 u32 hvalue; 90 struct hashtab_node *cur; 91 92 if (!h->size) 93 return NULL; 94 95 hvalue = h->hash_value(h, key); 96 cur = h->htable[hvalue]; 97 while (cur && h->keycmp(h, key, cur->key) > 0) 98 cur = cur->next; 99 100 if (!cur || (h->keycmp(h, key, cur->key) != 0)) 101 return NULL; 102 103 return cur->datum; 104 } 105 106 void hashtab_destroy(struct hashtab *h) 107 { 108 u32 i; 109 struct hashtab_node *cur, *temp; 110 111 for (i = 0; i < h->size; i++) { 112 cur = h->htable[i]; 113 while (cur) { 114 temp = cur; 115 cur = cur->next; 116 kmem_cache_free(hashtab_node_cachep, temp); 117 } 118 h->htable[i] = NULL; 119 } 120 121 kfree(h->htable); 122 h->htable = NULL; 123 } 124 125 int hashtab_map(struct hashtab *h, 126 int (*apply)(void *k, void *d, void *args), 127 void *args) 128 { 129 u32 i; 130 int ret; 131 struct hashtab_node *cur; 132 133 for (i = 0; i < h->size; i++) { 134 cur = h->htable[i]; 135 while (cur) { 136 ret = apply(cur->key, cur->datum, args); 137 if (ret) 138 return ret; 139 cur = cur->next; 140 } 141 } 142 return 0; 143 } 144 145 146 void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 147 { 148 u32 i, chain_len, slots_used, max_chain_len; 149 struct hashtab_node *cur; 150 151 slots_used = 0; 152 max_chain_len = 0; 153 for (i = 0; i < h->size; i++) { 154 cur = h->htable[i]; 155 if (cur) { 156 slots_used++; 157 chain_len = 0; 158 while (cur) { 159 chain_len++; 160 cur = cur->next; 161 } 162 163 if (chain_len > max_chain_len) 164 max_chain_len = chain_len; 165 } 166 } 167 168 info->slots_used = slots_used; 169 info->max_chain_len = max_chain_len; 170 } 171 172 void __init hashtab_cache_init(void) 173 { 174 hashtab_node_cachep = kmem_cache_create("hashtab_node", 175 sizeof(struct hashtab_node), 176 0, SLAB_PANIC, NULL); 177 } 178