1 /* 2 * Copyright (c) 2019 The Linux Foundation. All rights reserved. 3 * Copyright (c) 2022 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[0]; 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 * 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 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 * 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