xref: /wlan-driver/qca-wifi-host-cmn/qdf/inc/qdf_ptr_hash.h (revision 5113495b16420b49004c444715d2daae2066e7dc)
1 /*
2  * Copyright (c) 2019 The Linux Foundation. All rights reserved.
3  * Copyright (c) 2022-2024 Qualcomm Innovation Center, Inc. All rights reserved.
4  *
5  * Permission to use, copy, modify, and/or distribute this software for
6  * any purpose with or without fee is hereby granted, provided that the
7  * above copyright notice and this permission notice appear in all
8  * copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
11  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
12  * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
13  * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
15  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
16  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17  * PERFORMANCE OF THIS SOFTWARE.
18  */
19 
20 /**
21  * DOC: qdf_ptr_hash.h
22  *
23  * A minimal hashtable implementation for doing fast lookups via pointer.
24  *
25  * qdf_ptr_hash also has the benefit of knowing its own size, allowing a pointer
26  * to the hashtable to be passed around and embedded in other structs. Since
27  * every hashtable is not necessarily of the same size, this allows using hash
28  * tables in a lot of new places which would be impossible with the current
29  * kernel hashtable implementation.
30  *
31  * Because the size of the hashtable varies with the number of bits used in the
32  * hash, declaring a qdf_ptr_hash is a bit different. If you want to embed a
33  * qdf_ptr_hash in another type, use a combination of qdf_ptr_hash_declare() and
34  * qdf_ptr_hash_ptr(). If you just want to declare and use a qdf_ptr_hash, use
35  * qdf_ptr_hash_declare_ptr() instead. Either method will ensure the appropriate
36  * number of bytes is accounted for using an internal union, and provides the
37  * consumer with a pointer to a qdf_ptr_hash type which can be used with all of
38  * the other qdf_ptr_hash APIs. Alternatively, you can skip these complexities
39  * by simply dynamically allocating the qdf_ptr_hash via qdf_ptr_hash_create().
40  */
41 
42 #ifndef __QDF_PTR_HASH_H
43 #define __QDF_PTR_HASH_H
44 
45 #include "i_qdf_ptr_hash.h"
46 #include "qdf_mem.h"
47 #include "qdf_slist.h"
48 #include "qdf_types.h"
49 #include "qdf_util.h"
50 
51 /**
52  * struct qdf_ptr_hash_bucket - a type representing a hash bucket
53  * @list: the list used for hash chaining
54  */
55 struct qdf_ptr_hash_bucket {
56 	struct qdf_slist list;
57 };
58 
59 /**
60  * struct qdf_ptr_hash - a hash table type for doing fast lookups via pointer
61  * @bits: the number of bits to use when hashing keys
62  * @count: the number of buckets, always equal to 2^@bits
63  * @buckets: empty bucket array for accessing a variable length array of buckets
64  */
65 struct qdf_ptr_hash {
66 	int8_t bits;
67 	int16_t count;
68 	struct qdf_ptr_hash_bucket buckets[];
69 };
70 
71 /**
72  * struct qdf_ptr_hash_entry - entry type of membership in a qdf_ptr_hash
73  * @key: the value used as the key for insertion/lookup
74  * @node: the list node used for hash chaining
75  */
76 struct qdf_ptr_hash_entry {
77 	uintptr_t key;
78 	struct qdf_slist_node node;
79 };
80 
81 #define __qdf_ptr_hash_size(bits) (sizeof(struct qdf_ptr_hash) + \
82 	sizeof(((struct qdf_ptr_hash *)0)->buckets[0]) * (1 << bits))
83 
84 /**
85  * qdf_ptr_hash_declare() - declare a new qdf_ptr_hash
86  * @name: the C identifier to use for the new hash table
87  * @_bits: The number of bits to use for hashing
88  *
89  * Return: None
90  */
91 #define qdf_ptr_hash_declare(name, _bits) \
92 union { \
93 	struct qdf_ptr_hash ht; \
94 	uint8_t __raw[__qdf_ptr_hash_size(_bits)]; \
95 } __##name = { .ht = { .bits = _bits, .count = (1 << _bits) } }
96 
97 /**
98  * qdf_ptr_hash_ptr() - get a pointer to a declared qdf_ptr_hash
99  * @name: the C identifier of the declared qdf_ptr_hash
100  *
101  * Return: pointer to a qdf_ptr_hash
102  */
103 #define qdf_ptr_hash_ptr(name) &__##name.ht
104 
105 /**
106  * qdf_ptr_hash_declare_ptr() - declare a pointer to a new qdf_ptr_hash
107  * @name: the C identifier to use for the pointer to the new qdf_ptr_hash
108  * @bits: The number of bits to use for hashing
109  *
110  * Return: None
111  */
112 #define qdf_ptr_hash_declare_ptr(name, bits) \
113 qdf_ptr_hash_declare(name, bits); \
114 struct qdf_ptr_hash *name = qdf_ptr_hash_ptr(name)
115 
116 #define __qdf_ptr_hash_for_each_bucket(ht, bkt) \
117 	for ((bkt) = (ht)->buckets; \
118 	     (bkt) < (ht)->buckets + (ht)->count; \
119 	     (bkt)++)
120 
121 /**
122  * qdf_ptr_hash_init() - initialize a qdf_ptr_hash
123  * @ht: the hash table to initialize
124  *
125  * Return: None
126  */
qdf_ptr_hash_init(struct qdf_ptr_hash * ht)127 static inline void qdf_ptr_hash_init(struct qdf_ptr_hash *ht)
128 {
129 	struct qdf_ptr_hash_bucket *bucket;
130 
131 	__qdf_ptr_hash_for_each_bucket(ht, bucket)
132 		qdf_slist_init(&bucket->list);
133 }
134 
135 /**
136  * qdf_ptr_hash_deinit() - de-initialize a qdf_ptr_hash
137  * @ht: the hash table to de-initialize
138  *
139  * Return: None
140  */
qdf_ptr_hash_deinit(struct qdf_ptr_hash * ht)141 static inline void qdf_ptr_hash_deinit(struct qdf_ptr_hash *ht)
142 {
143 	struct qdf_ptr_hash_bucket *bucket;
144 
145 	__qdf_ptr_hash_for_each_bucket(ht, bucket)
146 		qdf_slist_deinit(&bucket->list);
147 }
148 
149 /**
150  * qdf_ptr_hash_create() - allocate and initialize a qdf_ptr_hash
151  * @bits: the number of bits to use for hashing
152  *
153  * Return: qdf_ptr_hash pointer on success, NULL on allocation failure
154  */
qdf_ptr_hash_create(uint8_t bits)155 static inline struct qdf_ptr_hash *qdf_ptr_hash_create(uint8_t bits)
156 {
157 	struct qdf_ptr_hash *ht = qdf_mem_malloc(__qdf_ptr_hash_size(bits));
158 
159 	if (!ht)
160 		return NULL;
161 
162 	ht->bits = bits;
163 	ht->count = 1 << bits;
164 	qdf_ptr_hash_init(ht);
165 
166 	return ht;
167 }
168 
169 /**
170  * qdf_ptr_hash_destroy() - de-initialize and de-allocate a qdf_ptr_hash
171  * @ht: the qdf_ptr_hash to destroy
172  *
173  * Return: None
174  */
qdf_ptr_hash_destroy(struct qdf_ptr_hash * ht)175 static inline void qdf_ptr_hash_destroy(struct qdf_ptr_hash *ht)
176 {
177 	qdf_ptr_hash_deinit(ht);
178 	qdf_mem_free(ht);
179 }
180 
181 /**
182  * qdf_ptr_hash_empty() - check if a qdf_ptr_hash has any entries
183  * @ht: the qdf_ptr_hash to check
184  *
185  * Return: true if @ht contains no entries
186  */
qdf_ptr_hash_empty(struct qdf_ptr_hash * ht)187 static inline bool qdf_ptr_hash_empty(struct qdf_ptr_hash *ht)
188 {
189 	struct qdf_ptr_hash_bucket *bucket;
190 
191 	__qdf_ptr_hash_for_each_bucket(ht, bucket)
192 		if (!qdf_slist_empty(&bucket->list))
193 			return false;
194 
195 	return true;
196 }
197 
198 #ifdef ENABLE_QDF_PTR_HASH_DEBUG
199 /**
200  * qdf_ptr_hash_dup_check_in_bucket() - check if a hash_entry is duplicated
201  *					in hash_bucket
202  * @bucket: qdf_ptr_hash_bucket pointer
203  * @cmp_entry: the hash_entry to be checked
204  *
205  * if the cmp_entry is found in bucket list, then trigger
206  * assert to report duplication.
207  *
208  * Return: None
209  */
qdf_ptr_hash_dup_check_in_bucket(struct qdf_ptr_hash_bucket * bucket,struct qdf_ptr_hash_entry * cmp_entry)210 static inline void qdf_ptr_hash_dup_check_in_bucket(
211 				struct qdf_ptr_hash_bucket *bucket,
212 				struct qdf_ptr_hash_entry *cmp_entry)
213 {
214 	struct qdf_ptr_hash_entry *tmp_entry;
215 
216 	qdf_slist_for_each(&bucket->list, tmp_entry, node)
217 		qdf_assert_always(tmp_entry != cmp_entry);
218 }
219 #else
220 #define qdf_ptr_hash_dup_check_in_bucket(_bucket, _cmp_entry) /* no op */
221 #endif
222 
223 static inline struct qdf_ptr_hash_bucket *
__qdf_ptr_hash_get_bucket(struct qdf_ptr_hash * ht,uintptr_t key)224 __qdf_ptr_hash_get_bucket(struct qdf_ptr_hash *ht, uintptr_t key)
225 {
226 	return ht->buckets + __qdf_ptr_hash_key(key, ht->bits);
227 }
228 
229 /**
230  * qdf_ptr_hash_add() - insert an entry into a qdf_ptr_hash
231  * @ht: the qdf_ptr_hash to insert into
232  * @key: the pointer to use as an insertion/lookup key
233  * @item: a pointer to a type that contains a qdf_ptr_hash_entry
234  * @entry_field: C identifier for the qdf_ptr_hash_entry field in @item
235  *
236  * Return: None
237  */
238 #define qdf_ptr_hash_add(ht, key, item, entry_field) \
239 	__qdf_ptr_hash_add(ht, (uintptr_t)key, &(item)->entry_field)
240 
__qdf_ptr_hash_add(struct qdf_ptr_hash * ht,uintptr_t key,struct qdf_ptr_hash_entry * entry)241 static inline void __qdf_ptr_hash_add(struct qdf_ptr_hash *ht, uintptr_t key,
242 				      struct qdf_ptr_hash_entry *entry)
243 {
244 	entry->key = key;
245 	/* check hash_enrty exist or not before push */
246 	qdf_ptr_hash_dup_check_in_bucket(__qdf_ptr_hash_get_bucket(ht, key),
247 					 entry);
248 	qdf_slist_push(&__qdf_ptr_hash_get_bucket(ht, key)->list, entry, node);
249 }
250 
251 /**
252  * qdf_ptr_hash_remove() - remove an entry from a qdf_ptr_hash
253  * @ht: the qdf_ptr_hash to remove from
254  * @key: the pointer to use as a lookup key
255  * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
256  * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
257  *
258  * Return: removed item of type @cursor on success, NULL otherwise
259  */
260 #define qdf_ptr_hash_remove(ht, key, cursor, entry_field) ({ \
261 	struct qdf_ptr_hash_entry *_e = \
262 		__qdf_ptr_hash_remove(ht, (uintptr_t)key); \
263 	cursor = _e ? qdf_container_of(_e, typeof(*(cursor)), \
264 				       entry_field) : NULL; \
265 	cursor; })
266 
267 static inline struct qdf_ptr_hash_entry *
__qdf_ptr_hash_remove(struct qdf_ptr_hash * ht,uintptr_t key)268 __qdf_ptr_hash_remove(struct qdf_ptr_hash *ht, uintptr_t key)
269 {
270 	struct qdf_ptr_hash_bucket *bucket = __qdf_ptr_hash_get_bucket(ht, key);
271 	struct qdf_ptr_hash_entry *prev;
272 	struct qdf_ptr_hash_entry *entry;
273 
274 	qdf_slist_for_each_del(&bucket->list, prev, entry, node) {
275 		if (entry->key == key) {
276 			qdf_slist_remove(&bucket->list, prev, node);
277 			/* check hash_enrty exist or not after remove */
278 			qdf_ptr_hash_dup_check_in_bucket(bucket, entry);
279 			entry->key = 0;
280 			return entry;
281 		}
282 	}
283 
284 	return NULL;
285 }
286 
287 #define __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) \
288 	qdf_slist_for_each(&(bucket)->list, cursor, entry_field.node)
289 
290 /**
291  * qdf_ptr_hash_for_each() - qdf_ptr_hash item iterator for all items
292  * @ht: the qdf_ptr_hash to iterate over
293  * @bucket: qdf_ptr_hash_bucket cursor pointer
294  * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
295  * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
296  */
297 #define qdf_ptr_hash_for_each(ht, bucket, cursor, entry_field) \
298 	__qdf_ptr_hash_for_each_bucket(ht, bucket) \
299 		__qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field)
300 
301 /**
302  * qdf_ptr_hash_for_each_by_hash() - qdf_ptr_hash item iterator for items which
303  *	hash to the same value as @key
304  * @ht: the qdf_ptr_hash to iterate over
305  * @key: the pointer to use as a lookup key
306  * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
307  * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
308  */
309 #define qdf_ptr_hash_for_each_by_hash(ht, key, cursor, entry_field) \
310 	__qdf_ptr_hash_for_each_in_bucket( \
311 		__qdf_ptr_hash_get_bucket(ht, (uintptr_t)key), \
312 		cursor, entry_field)
313 
314 /**
315  * qdf_ptr_hash_for_each_by_key() - qdf_ptr_hash item iterator for items whose
316  *	keys equal @_key
317  * @ht: the qdf_ptr_hash to iterate over
318  * @_key: the pointer to use as a lookup key
319  * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
320  * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
321  */
322 #define qdf_ptr_hash_for_each_by_key(ht, _key, cursor, entry_field) \
323 	qdf_ptr_hash_for_each_by_hash(ht, _key, cursor, entry_field) \
324 		if ((cursor)->entry_field.key == (uintptr_t)_key)
325 
326 /**
327  * qdf_ptr_hash_get() - get the first item whose key matches @key
328  * @ht: the qdf_ptr_hash to look in
329  * @key: the pointer to use as a lookup key
330  * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
331  * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
332  *
333  * Return: first item matching @key of type @cursor on success, NULL otherwise
334  */
335 #define qdf_ptr_hash_get(ht, key, cursor, entry_field) ({ \
336 	cursor = NULL; \
337 	qdf_ptr_hash_for_each_by_key(ht, key, cursor, entry_field) \
338 		break; \
339 	cursor; })
340 
341 #endif /* __QDF_PTR_HASH_H */
342 
343