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, dst: 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 | |