drivers/gpu/drm/amd/include/linux/chash.h

   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 */