1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * A hash table (hashtab) maintains associations between 4 * key values and datum values. The type of the key values 5 * and the type of the datum values is arbitrary. The 6 * functions for hash computation and key comparison are 7 * provided by the creator of the table. 8 * 9 * Author : Stephen Smalley, <stephen.smalley.work@gmail.com> 10 */ 11 #ifndef _SS_HASHTAB_H_ 12 #define _SS_HASHTAB_H_ 13 14 #include <linux/types.h> 15 #include <linux/errno.h> 16 #include <linux/sched.h> 17 18 #define HASHTAB_MAX_NODES U32_MAX 19 20 struct hashtab_key_params { 21 u32 (*hash)(const void *key); /* hash function */ 22 int (*cmp)(const void *key1, const void *key2); 23 /* key comparison function */ 24 }; 25 26 struct hashtab_node { 27 void *key; 28 void *datum; 29 struct hashtab_node *next; 30 }; 31 32 struct hashtab { 33 struct hashtab_node **htable; /* hash table */ 34 u32 size; /* number of slots in hash table */ 35 u32 nel; /* number of elements in hash table */ 36 }; 37 38 struct hashtab_info { 39 u32 slots_used; 40 u32 max_chain_len; 41 u64 chain2_len_sum; 42 }; 43 44 /* 45 * Initializes a new hash table with the specified characteristics. 46 * 47 * Returns -ENOMEM if insufficient space is available or 0 otherwise. 48 */ 49 int hashtab_init(struct hashtab *h, u32 nel_hint); 50 51 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, 52 void *key, void *datum); 53 54 /* 55 * Inserts the specified (key, datum) pair into the specified hash table. 56 * 57 * Returns -ENOMEM on memory allocation error, 58 * -EEXIST if there is already an entry with the same key, 59 * -EINVAL for general errors or 60 0 otherwise. 61 */ 62 static inline int hashtab_insert(struct hashtab *h, void *key, void *datum, 63 struct hashtab_key_params key_params) 64 { 65 u32 hvalue; 66 struct hashtab_node *prev, *cur; 67 68 cond_resched(); 69 70 if (!h->size || h->nel == HASHTAB_MAX_NODES) 71 return -EINVAL; 72 73 hvalue = key_params.hash(key) & (h->size - 1); 74 prev = NULL; 75 cur = h->htable[hvalue]; 76 while (cur) { 77 int cmp = key_params.cmp(key, cur->key); 78 79 if (cmp == 0) 80 return -EEXIST; 81 if (cmp < 0) 82 break; 83 prev = cur; 84 cur = cur->next; 85 } 86 87 return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue], 88 key, datum); 89 } 90 91 /* 92 * Searches for the entry with the specified key in the hash table. 93 * 94 * Returns NULL if no entry has the specified key or 95 * the datum of the entry otherwise. 96 */ 97 static inline void *hashtab_search(struct hashtab *h, const void *key, 98 struct hashtab_key_params key_params) 99 { 100 u32 hvalue; 101 struct hashtab_node *cur; 102 103 if (!h->size) 104 return NULL; 105 106 hvalue = key_params.hash(key) & (h->size - 1); 107 cur = h->htable[hvalue]; 108 while (cur) { 109 int cmp = key_params.cmp(key, cur->key); 110 111 if (cmp == 0) 112 return cur->datum; 113 if (cmp < 0) 114 break; 115 cur = cur->next; 116 } 117 return NULL; 118 } 119 120 /* 121 * Destroys the specified hash table. 122 */ 123 void hashtab_destroy(struct hashtab *h); 124 125 /* 126 * Applies the specified apply function to (key,datum,args) 127 * for each entry in the specified hash table. 128 * 129 * The order in which the function is applied to the entries 130 * is dependent upon the internal structure of the hash table. 131 * 132 * If apply returns a non-zero status, then hashtab_map will cease 133 * iterating through the hash table and will propagate the error 134 * return to its caller. 135 */ 136 int hashtab_map(struct hashtab *h, 137 int (*apply)(void *k, void *d, void *args), 138 void *args); 139 140 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig, 141 int (*copy)(struct hashtab_node *new, 142 struct hashtab_node *orig, void *args), 143 int (*destroy)(void *k, void *d, void *args), 144 void *args); 145 146 #ifdef CONFIG_SECURITY_SELINUX_DEBUG 147 /* Fill info with some hash table statistics */ 148 void hashtab_stat(struct hashtab *h, struct hashtab_info *info); 149 #else 150 static inline void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 151 { 152 } 153 #endif 154 155 #endif /* _SS_HASHTAB_H */ 156