1 /* 2 * Copyright 2017 Advanced Micro Devices, Inc. 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included in 12 * all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR 18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20 * OTHER DEALINGS IN THE SOFTWARE. 21 * 22 */ 23 24 #ifndef _LINUX_CHASH_H 25 #define _LINUX_CHASH_H 26 27 #include <linux/types.h> 28 #include <linux/hash.h> 29 #include <linux/bug.h> 30 #include <asm/bitsperlong.h> 31 32 #if BITS_PER_LONG == 32 33 # define _CHASH_LONG_SHIFT 5 34 #elif BITS_PER_LONG == 64 35 # define _CHASH_LONG_SHIFT 6 36 #else 37 # error "Unexpected BITS_PER_LONG" 38 #endif 39 40 struct __chash_table { 41 u8 bits; 42 u8 key_size; 43 unsigned int value_size; 44 u32 size_mask; 45 unsigned long *occup_bitmap, *valid_bitmap; 46 union { 47 u32 *keys32; 48 u64 *keys64; 49 }; 50 u8 *values; 51 52 #ifdef CONFIG_CHASH_STATS 53 u64 hits, hits_steps, hits_time_ns; 54 u64 miss, miss_steps, miss_time_ns; 55 u64 relocs, reloc_dist; 56 #endif 57 }; 58 59 #define __CHASH_BITMAP_SIZE(bits) \ 60 (((1 << (bits)) + BITS_PER_LONG - 1) / BITS_PER_LONG) 61 #define __CHASH_ARRAY_SIZE(bits, size) \ 62 ((((size) << (bits)) + sizeof(long) - 1) / sizeof(long)) 63 64 #define __CHASH_DATA_SIZE(bits, key_size, value_size) \ 65 (__CHASH_BITMAP_SIZE(bits) * 2 + \ 66 __CHASH_ARRAY_SIZE(bits, key_size) + \ 67 __CHASH_ARRAY_SIZE(bits, value_size)) 68 69 #define STRUCT_CHASH_TABLE(bits, key_size, value_size) \ 70 struct { \ 71 struct __chash_table table; \ 72 unsigned long data \ 73 [__CHASH_DATA_SIZE(bits, key_size, value_size)];\ 74 } 75 76 /** 77 * struct chash_table - Dynamically allocated closed hash table 78 * 79 * Use this struct for dynamically allocated hash tables (using 80 * chash_table_alloc and chash_table_free), where the size is 81 * determined at runtime. 82 */ 83 struct chash_table { 84 struct __chash_table table; 85 unsigned long *data; 86 }; 87 88 /** 89 * DECLARE_CHASH_TABLE - macro to declare a closed hash table 90 * @table: name of the declared hash table 91 * @bts: Table size will be 2^bits entries 92 * @key_sz: Size of hash keys in bytes, 4 or 8 93 * @val_sz: Size of data values in bytes, can be 0 94 * 95 * This declares the hash table variable with a static size. 96 * 97 * The closed hash table stores key-value pairs with low memory and 98 * lookup overhead. In operation it performs no dynamic memory 99 * management. The data being stored does not require any 100 * list_heads. The hash table performs best with small @val_sz and as 101 * long as some space (about 50%) is left free in the table. But the 102 * table can still work reasonably efficiently even when filled up to 103 * about 90%. If bigger data items need to be stored and looked up, 104 * store the pointer to it as value in the hash table. 105 * 106 * @val_sz may be 0. This can be useful when all the stored 107 * information is contained in the key itself and the fact that it is 108 * in the hash table (or not). 109 */ 110 #define DECLARE_CHASH_TABLE(table, bts, key_sz, val_sz) \ 111 STRUCT_CHASH_TABLE(bts, key_sz, val_sz) table 112 113 #ifdef CONFIG_CHASH_STATS 114 #define __CHASH_STATS_INIT(prefix), \ 115 prefix.hits = 0, \ 116 prefix.hits_steps = 0, \ 117 prefix.hits_time_ns = 0, \ 118 prefix.miss = 0, \ 119 prefix.miss_steps = 0, \ 120 prefix.miss_time_ns = 0, \ 121 prefix.relocs = 0, \ 122 prefix.reloc_dist = 0 123 #else 124 #define __CHASH_STATS_INIT(prefix) 125 #endif 126 127 #define __CHASH_TABLE_INIT(prefix, data, bts, key_sz, val_sz) \ 128 prefix.bits = (bts), \ 129 prefix.key_size = (key_sz), \ 130 prefix.value_size = (val_sz), \ 131 prefix.size_mask = ((1 << bts) - 1), \ 132 prefix.occup_bitmap = &data[0], \ 133 prefix.valid_bitmap = &data \ 134 [__CHASH_BITMAP_SIZE(bts)], \ 135 prefix.keys64 = (u64 *)&data \ 136 [__CHASH_BITMAP_SIZE(bts) * 2], \ 137 prefix.values = (u8 *)&data \ 138 [__CHASH_BITMAP_SIZE(bts) * 2 + \ 139 __CHASH_ARRAY_SIZE(bts, key_sz)] \ 140 __CHASH_STATS_INIT(prefix) 141 142 /** 143 * DEFINE_CHASH_TABLE - macro to define and initialize a closed hash table 144 * @tbl: name of the declared hash table 145 * @bts: Table size will be 2^bits entries 146 * @key_sz: Size of hash keys in bytes, 4 or 8 147 * @val_sz: Size of data values in bytes, can be 0 148 * 149 * Note: the macro can be used for global and local hash table variables. 150 */ 151 #define DEFINE_CHASH_TABLE(tbl, bts, key_sz, val_sz) \ 152 DECLARE_CHASH_TABLE(tbl, bts, key_sz, val_sz) = { \ 153 .table = { \ 154 __CHASH_TABLE_INIT(, (tbl).data, bts, key_sz, val_sz) \ 155 }, \ 156 .data = {0} \ 157 } 158 159 /** 160 * INIT_CHASH_TABLE - Initialize a hash table declared by DECLARE_CHASH_TABLE 161 * @tbl: name of the declared hash table 162 * @bts: Table size will be 2^bits entries 163 * @key_sz: Size of hash keys in bytes, 4 or 8 164 * @val_sz: Size of data values in bytes, can be 0 165 */ 166 #define INIT_CHASH_TABLE(tbl, bts, key_sz, val_sz) \ 167 __CHASH_TABLE_INIT(((tbl).table), (tbl).data, bts, key_sz, val_sz) 168 169 int chash_table_alloc(struct chash_table *table, u8 bits, u8 key_size, 170 unsigned int value_size, gfp_t gfp_mask); 171 void chash_table_free(struct chash_table *table); 172 173 /** 174 * chash_table_dump_stats - Dump statistics of a closed hash table 175 * @tbl: Pointer to the table structure 176 * 177 * Dumps some performance statistics of the table gathered in operation 178 * in the kernel log using pr_debug. If CONFIG_DYNAMIC_DEBUG is enabled, 179 * user must turn on messages for chash.c (file chash.c +p). 180 */ 181 #ifdef CONFIG_CHASH_STATS 182 #define chash_table_dump_stats(tbl) __chash_table_dump_stats(&(*tbl).table) 183 184 void __chash_table_dump_stats(struct __chash_table *table); 185 #else 186 #define chash_table_dump_stats(tbl) 187 #endif 188 189 /** 190 * chash_table_reset_stats - Reset statistics of a closed hash table 191 * @tbl: Pointer to the table structure 192 */ 193 #ifdef CONFIG_CHASH_STATS 194 #define chash_table_reset_stats(tbl) __chash_table_reset_stats(&(*tbl).table) 195 196 static inline void __chash_table_reset_stats(struct __chash_table *table) 197 { 198 (void)table __CHASH_STATS_INIT((*table)); 199 } 200 #else 201 #define chash_table_reset_stats(tbl) 202 #endif 203 204 /** 205 * chash_table_copy_in - Copy a new value into the hash table 206 * @tbl: Pointer to the table structure 207 * @key: Key of the entry to add or update 208 * @value: Pointer to value to copy, may be NULL 209 * 210 * If @key already has an entry, its value is replaced. Otherwise a 211 * new entry is added. If @value is NULL, the value is left unchanged 212 * or uninitialized. Returns 1 if an entry already existed, 0 if a new 213 * entry was added or %-ENOMEM if there was no free space in the 214 * table. 215 */ 216 #define chash_table_copy_in(tbl, key, value) \ 217 __chash_table_copy_in(&(*tbl).table, key, value) 218 219 int __chash_table_copy_in(struct __chash_table *table, u64 key, 220 const void *value); 221 222 /** 223 * chash_table_copy_out - Copy a value out of the hash table 224 * @tbl: Pointer to the table structure 225 * @key: Key of the entry to find 226 * @value: Pointer to value to copy, may be NULL 227 * 228 * If @value is not NULL and the table has a non-0 value_size, the 229 * value at @key is copied to @value. Returns the slot index of the 230 * entry or %-EINVAL if @key was not found. 231 */ 232 #define chash_table_copy_out(tbl, key, value) \ 233 __chash_table_copy_out(&(*tbl).table, key, value, false) 234 235 int __chash_table_copy_out(struct __chash_table *table, u64 key, 236 void *value, bool remove); 237 238 /** 239 * chash_table_remove - Remove an entry from the hash table 240 * @tbl: Pointer to the table structure 241 * @key: Key of the entry to find 242 * @value: Pointer to value to copy, may be NULL 243 * 244 * If @value is not NULL and the table has a non-0 value_size, the 245 * value at @key is copied to @value. The entry is removed from the 246 * table. Returns the slot index of the removed entry or %-EINVAL if 247 * @key was not found. 248 */ 249 #define chash_table_remove(tbl, key, value) \ 250 __chash_table_copy_out(&(*tbl).table, key, value, true) 251 252 /* 253 * Low level iterator API used internally by the above functions. 254 */ 255 struct chash_iter { 256 struct __chash_table *table; 257 unsigned long mask; 258 int slot; 259 }; 260 261 /** 262 * CHASH_ITER_INIT - Initialize a hash table iterator 263 * @tbl: Pointer to hash table to iterate over 264 * @s: Initial slot number 265 */ 266 #define CHASH_ITER_INIT(table, s) { \ 267 table, \ 268 1UL << ((s) & (BITS_PER_LONG - 1)), \ 269 s \ 270 } 271 /** 272 * CHASH_ITER_SET - Set hash table iterator to new slot 273 * @iter: Iterator 274 * @s: Slot number 275 */ 276 #define CHASH_ITER_SET(iter, s) \ 277 (iter).mask = 1UL << ((s) & (BITS_PER_LONG - 1)), \ 278 (iter).slot = (s) 279 /** 280 * CHASH_ITER_INC - Increment hash table iterator 281 * @table: Hash table to iterate over 282 * 283 * Wraps around at the end. 284 */ 285 #define CHASH_ITER_INC(iter) do { \ 286 (iter).mask = (iter).mask << 1 | \ 287 (iter).mask >> (BITS_PER_LONG - 1); \ 288 (iter).slot = ((iter).slot + 1) & (iter).table->size_mask; \ 289 } while (0) 290 291 static inline bool chash_iter_is_valid(const struct chash_iter iter) 292 { 293 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 294 return !!(iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] & 295 iter.mask); 296 } 297 static inline bool chash_iter_is_empty(const struct chash_iter iter) 298 { 299 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 300 return !(iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] & 301 iter.mask); 302 } 303 304 static inline void chash_iter_set_valid(const struct chash_iter iter) 305 { 306 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 307 iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] |= iter.mask; 308 iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] |= iter.mask; 309 } 310 static inline void chash_iter_set_invalid(const struct chash_iter iter) 311 { 312 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 313 iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &= ~iter.mask; 314 } 315 static inline void chash_iter_set_empty(const struct chash_iter iter) 316 { 317 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 318 iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &= ~iter.mask; 319 } 320 321 static inline u32 chash_iter_key32(const struct chash_iter iter) 322 { 323 BUG_ON(iter.table->key_size != 4); 324 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 325 return iter.table->keys32[iter.slot]; 326 } 327 static inline u64 chash_iter_key64(const struct chash_iter iter) 328 { 329 BUG_ON(iter.table->key_size != 8); 330 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 331 return iter.table->keys64[iter.slot]; 332 } 333 static inline u64 chash_iter_key(const struct chash_iter iter) 334 { 335 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 336 return (iter.table->key_size == 4) ? 337 iter.table->keys32[iter.slot] : iter.table->keys64[iter.slot]; 338 } 339 340 static inline u32 chash_iter_hash32(const struct chash_iter iter) 341 { 342 BUG_ON(iter.table->key_size != 4); 343 return hash_32(chash_iter_key32(iter), iter.table->bits); 344 } 345 346 static inline u32 chash_iter_hash64(const struct chash_iter iter) 347 { 348 BUG_ON(iter.table->key_size != 8); 349 return hash_64(chash_iter_key64(iter), iter.table->bits); 350 } 351 352 static inline u32 chash_iter_hash(const struct chash_iter iter) 353 { 354 return (iter.table->key_size == 4) ? 355 hash_32(chash_iter_key32(iter), iter.table->bits) : 356 hash_64(chash_iter_key64(iter), iter.table->bits); 357 } 358 359 static inline void *chash_iter_value(const struct chash_iter iter) 360 { 361 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); 362 return iter.table->values + 363 ((unsigned long)iter.slot * iter.table->value_size); 364 } 365 366 #endif /* _LINUX_CHASH_H */ 367