selinux/ss/hashtab.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Implementation of the hash table type.
0004  *
0005  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
0006  */
0007 #include <linux/kernel.h>
0008 #include <linux/slab.h>
0009 #include <linux/errno.h>
0010 #include "hashtab.h"
0011 #include "security.h"
0012
0013 static struct kmem_cache *hashtab_node_cachep __ro_after_init;
0014
0015 /*
0016  * Here we simply round the number of elements up to the nearest power of two.
0017  * I tried also other options like rounding down or rounding to the closest
0018  * power of two (up or down based on which is closer), but I was unable to
0019  * find any significant difference in lookup/insert performance that would
0020  * justify switching to a different (less intuitive) formula. It could be that
0021  * a different formula is actually more optimal, but any future changes here
0022  * should be supported with performance/memory usage data.
0023  *
0024  * The total memory used by the htable arrays (only) with Fedora policy loaded
0025  * is approximately 163 KB at the time of writing.
0026  */
0027 static u32 hashtab_compute_size(u32 nel)
0028 {
0029     return nel == 0 ? 0 : roundup_pow_of_two(nel);
0030 }
0031
0032 int hashtab_init(struct hashtab *h, u32 nel_hint)
0033 {
0034     u32 size = hashtab_compute_size(nel_hint);
0035
0036     /* should already be zeroed, but better be safe */
0037     h->nel = 0;
0038     h->size = 0;
0039     h->htable = NULL;
0040
0041     if (size) {
0042         h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
0043         if (!h->htable)
0044             return -ENOMEM;
0045         h->size = size;
0046     }
0047     return 0;
0048 }
0049
0050 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
0051              void *key, void *datum)
0052 {
0053     struct hashtab_node *newnode;
0054
0055     newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
0056     if (!newnode)
0057         return -ENOMEM;
0058     newnode->key = key;
0059     newnode->datum = datum;
0060     newnode->next = *dst;
0061     *dst = newnode;
0062
0063     h->nel++;
0064     return 0;
0065 }
0066
0067 void hashtab_destroy(struct hashtab *h)
0068 {
0069     u32 i;
0070     struct hashtab_node *cur, *temp;
0071
0072     for (i = 0; i < h->size; i++) {
0073         cur = h->htable[i];
0074         while (cur) {
0075             temp = cur;
0076             cur = cur->next;
0077             kmem_cache_free(hashtab_node_cachep, temp);
0078         }
0079         h->htable[i] = NULL;
0080     }
0081
0082     kfree(h->htable);
0083     h->htable = NULL;
0084 }
0085
0086 int hashtab_map(struct hashtab *h,
0087         int (*apply)(void *k, void *d, void *args),
0088         void *args)
0089 {
0090     u32 i;
0091     int ret;
0092     struct hashtab_node *cur;
0093
0094     for (i = 0; i < h->size; i++) {
0095         cur = h->htable[i];
0096         while (cur) {
0097             ret = apply(cur->key, cur->datum, args);
0098             if (ret)
0099                 return ret;
0100             cur = cur->next;
0101         }
0102     }
0103     return 0;
0104 }
0105
0106
0107 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
0108 {
0109     u32 i, chain_len, slots_used, max_chain_len;
0110     struct hashtab_node *cur;
0111
0112     slots_used = 0;
0113     max_chain_len = 0;
0114     for (i = 0; i < h->size; i++) {
0115         cur = h->htable[i];
0116         if (cur) {
0117             slots_used++;
0118             chain_len = 0;
0119             while (cur) {
0120                 chain_len++;
0121                 cur = cur->next;
0122             }
0123
0124             if (chain_len > max_chain_len)
0125                 max_chain_len = chain_len;
0126         }
0127     }
0128
0129     info->slots_used = slots_used;
0130     info->max_chain_len = max_chain_len;
0131 }
0132
0133 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
0134         int (*copy)(struct hashtab_node *new,
0135             struct hashtab_node *orig, void *args),
0136         int (*destroy)(void *k, void *d, void *args),
0137         void *args)
0138 {
0139     struct hashtab_node *cur, *tmp, *tail;
0140     int i, rc;
0141
0142     memset(new, 0, sizeof(*new));
0143
0144     new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
0145     if (!new->htable)
0146         return -ENOMEM;
0147
0148     new->size = orig->size;
0149
0150     for (i = 0; i < orig->size; i++) {
0151         tail = NULL;
0152         for (cur = orig->htable[i]; cur; cur = cur->next) {
0153             tmp = kmem_cache_zalloc(hashtab_node_cachep,
0154                         GFP_KERNEL);
0155             if (!tmp)
0156                 goto error;
0157             rc = copy(tmp, cur, args);
0158             if (rc) {
0159                 kmem_cache_free(hashtab_node_cachep, tmp);
0160                 goto error;
0161             }
0162             tmp->next = NULL;
0163             if (!tail)
0164                 new->htable[i] = tmp;
0165             else
0166                 tail->next = tmp;
0167             tail = tmp;
0168             new->nel++;
0169         }
0170     }
0171
0172     return 0;
0173
0174  error:
0175     for (i = 0; i < new->size; i++) {
0176         for (cur = new->htable[i]; cur; cur = tmp) {
0177             tmp = cur->next;
0178             destroy(cur->key, cur->datum, args);
0179             kmem_cache_free(hashtab_node_cachep, cur);
0180         }
0181     }
0182     kfree(new->htable);
0183     memset(new, 0, sizeof(*new));
0184     return -ENOMEM;
0185 }
0186
0187 void __init hashtab_cache_init(void)
0188 {
0189         hashtab_node_cachep = kmem_cache_create("hashtab_node",
0190             sizeof(struct hashtab_node),
0191             0, SLAB_PANIC, NULL);
0192 }