^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Implementation of the hash table type.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Author : Stephen Smalley, <sds@tycho.nsa.gov>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include <linux/errno.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include "hashtab.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) static struct kmem_cache *hashtab_node_cachep;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * Here we simply round the number of elements up to the nearest power of two.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * I tried also other options like rouding down or rounding to the closest
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * power of two (up or down based on which is closer), but I was unable to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * find any significant difference in lookup/insert performance that would
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * justify switching to a different (less intuitive) formula. It could be that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * a different formula is actually more optimal, but any future changes here
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * should be supported with performance/memory usage data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * The total memory used by the htable arrays (only) with Fedora policy loaded
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * is approximately 163 KB at the time of writing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) static u32 hashtab_compute_size(u32 nel)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) return nel == 0 ? 0 : roundup_pow_of_two(nel);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) int hashtab_init(struct hashtab *h, u32 nel_hint)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) u32 size = hashtab_compute_size(nel_hint);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) /* should already be zeroed, but better be safe */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) h->nel = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) h->size = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) h->htable = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) if (size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) if (!h->htable)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) h->size = size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) void *key, void *datum)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) struct hashtab_node *newnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) if (!newnode)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) newnode->key = key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) newnode->datum = datum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) newnode->next = *dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) *dst = newnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) h->nel++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) void hashtab_destroy(struct hashtab *h)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) u32 i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) struct hashtab_node *cur, *temp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) for (i = 0; i < h->size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) cur = h->htable[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) while (cur) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) temp = cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) cur = cur->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) kmem_cache_free(hashtab_node_cachep, temp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) h->htable[i] = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) kfree(h->htable);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) h->htable = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) int hashtab_map(struct hashtab *h,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) int (*apply)(void *k, void *d, void *args),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) void *args)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) u32 i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) struct hashtab_node *cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) for (i = 0; i < h->size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) cur = h->htable[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) while (cur) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) ret = apply(cur->key, cur->datum, args);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) cur = cur->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) u32 i, chain_len, slots_used, max_chain_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) struct hashtab_node *cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) slots_used = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) max_chain_len = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) for (i = 0; i < h->size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) cur = h->htable[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) if (cur) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) slots_used++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) chain_len = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) while (cur) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) chain_len++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) cur = cur->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) if (chain_len > max_chain_len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) max_chain_len = chain_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) info->slots_used = slots_used;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) info->max_chain_len = max_chain_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) int (*copy)(struct hashtab_node *new,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) struct hashtab_node *orig, void *args),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) int (*destroy)(void *k, void *d, void *args),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) void *args)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) struct hashtab_node *cur, *tmp, *tail;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) int i, rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) memset(new, 0, sizeof(*new));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) if (!new->htable)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) new->size = orig->size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) for (i = 0; i < orig->size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) tail = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) for (cur = orig->htable[i]; cur; cur = cur->next) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) tmp = kmem_cache_zalloc(hashtab_node_cachep,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) if (!tmp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) rc = copy(tmp, cur, args);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) if (rc) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) kmem_cache_free(hashtab_node_cachep, tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) tmp->next = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) if (!tail)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) new->htable[i] = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) tail->next = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) tail = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) new->nel++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) for (i = 0; i < new->size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) for (cur = new->htable[i]; cur; cur = tmp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) tmp = cur->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) destroy(cur->key, cur->datum, args);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) kmem_cache_free(hashtab_node_cachep, cur);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) kmem_cache_free(hashtab_node_cachep, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) void __init hashtab_cache_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) hashtab_node_cachep = kmem_cache_create("hashtab_node",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) sizeof(struct hashtab_node),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) 0, SLAB_PANIC, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags