diff options
Diffstat (limited to 'drivers/gpu/drm/amd/include/linux/chash.h')
| -rw-r--r-- | drivers/gpu/drm/amd/include/linux/chash.h | 366 |
1 files changed, 0 insertions, 366 deletions
diff --git a/drivers/gpu/drm/amd/include/linux/chash.h b/drivers/gpu/drm/amd/include/linux/chash.h deleted file mode 100644 index 6dc159924ed1..000000000000 --- a/drivers/gpu/drm/amd/include/linux/chash.h +++ /dev/null @@ -1,366 +0,0 @@ -/* - * Copyright 2017 Advanced Micro Devices, Inc. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR - * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, - * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR - * OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#ifndef _LINUX_CHASH_H -#define _LINUX_CHASH_H - -#include <linux/types.h> -#include <linux/hash.h> -#include <linux/bug.h> -#include <asm/bitsperlong.h> - -#if BITS_PER_LONG == 32 -# define _CHASH_LONG_SHIFT 5 -#elif BITS_PER_LONG == 64 -# define _CHASH_LONG_SHIFT 6 -#else -# error "Unexpected BITS_PER_LONG" -#endif - -struct __chash_table { - u8 bits; - u8 key_size; - unsigned int value_size; - u32 size_mask; - unsigned long *occup_bitmap, *valid_bitmap; - union { - u32 *keys32; - u64 *keys64; - }; - u8 *values; - -#ifdef CONFIG_CHASH_STATS - u64 hits, hits_steps, hits_time_ns; - u64 miss, miss_steps, miss_time_ns; - u64 relocs, reloc_dist; -#endif -}; - -#define __CHASH_BITMAP_SIZE(bits) \ - (((1 << (bits)) + BITS_PER_LONG - 1) / BITS_PER_LONG) -#define __CHASH_ARRAY_SIZE(bits, size) \ - ((((size) << (bits)) + sizeof(long) - 1) / sizeof(long)) - -#define __CHASH_DATA_SIZE(bits, key_size, value_size) \ - (__CHASH_BITMAP_SIZE(bits) * 2 + \ - __CHASH_ARRAY_SIZE(bits, key_size) + \ - __CHASH_ARRAY_SIZE(bits, value_size)) - -#define STRUCT_CHASH_TABLE(bits, key_size, value_size) \ - struct { \ - struct __chash_table table; \ - unsigned long data \ - [__CHASH_DATA_SIZE(bits, key_size, value_size)];\ - } - -/** - * struct chash_table - Dynamically allocated closed hash table - * - * Use this struct for dynamically allocated hash tables (using - * chash_table_alloc and chash_table_free), where the size is - * determined at runtime. - */ -struct chash_table { - struct __chash_table table; - unsigned long *data; -}; - -/** - * DECLARE_CHASH_TABLE - macro to declare a closed hash table - * @table: name of the declared hash table - * @bts: Table size will be 2^bits entries - * @key_sz: Size of hash keys in bytes, 4 or 8 - * @val_sz: Size of data values in bytes, can be 0 - * - * This declares the hash table variable with a static size. - * - * The closed hash table stores key-value pairs with low memory and - * lookup overhead. In operation it performs no dynamic memory - * management. The data being stored does not require any - * list_heads. The hash table performs best with small @val_sz and as - * long as some space (about 50%) is left free in the table. But the - * table can still work reasonably efficiently even when filled up to - * about 90%. If bigger data items need to be stored and looked up, - * store the pointer to it as value in the hash table. - * - * @val_sz may be 0. This can be useful when all the stored - * information is contained in the key itself and the fact that it is - * in the hash table (or not). - */ -#define DECLARE_CHASH_TABLE(table, bts, key_sz, val_sz) \ - STRUCT_CHASH_TABLE(bts, key_sz, val_sz) table - -#ifdef CONFIG_CHASH_STATS -#define __CHASH_STATS_INIT(prefix), \ - prefix.hits = 0, \ - prefix.hits_steps = 0, \ - prefix.hits_time_ns = 0, \ - prefix.miss = 0, \ - prefix.miss_steps = 0, \ - prefix.miss_time_ns = 0, \ - prefix.relocs = 0, \ - prefix.reloc_dist = 0 -#else -#define __CHASH_STATS_INIT(prefix) -#endif - -#define __CHASH_TABLE_INIT(prefix, data, bts, key_sz, val_sz) \ - prefix.bits = (bts), \ - prefix.key_size = (key_sz), \ - prefix.value_size = (val_sz), \ - prefix.size_mask = ((1 << bts) - 1), \ - prefix.occup_bitmap = &data[0], \ - prefix.valid_bitmap = &data \ - [__CHASH_BITMAP_SIZE(bts)], \ - prefix.keys64 = (u64 *)&data \ - [__CHASH_BITMAP_SIZE(bts) * 2], \ - prefix.values = (u8 *)&data \ - [__CHASH_BITMAP_SIZE(bts) * 2 + \ - __CHASH_ARRAY_SIZE(bts, key_sz)] \ - __CHASH_STATS_INIT(prefix) - -/** - * DEFINE_CHASH_TABLE - macro to define and initialize a closed hash table - * @tbl: name of the declared hash table - * @bts: Table size will be 2^bits entries - * @key_sz: Size of hash keys in bytes, 4 or 8 - * @val_sz: Size of data values in bytes, can be 0 - * - * Note: the macro can be used for global and local hash table variables. - */ -#define DEFINE_CHASH_TABLE(tbl, bts, key_sz, val_sz) \ - DECLARE_CHASH_TABLE(tbl, bts, key_sz, val_sz) = { \ - .table = { \ - __CHASH_TABLE_INIT(, (tbl).data, bts, key_sz, val_sz) \ - }, \ - .data = {0} \ - } - -/** - * INIT_CHASH_TABLE - Initialize a hash table declared by DECLARE_CHASH_TABLE - * @tbl: name of the declared hash table - * @bts: Table size will be 2^bits entries - * @key_sz: Size of hash keys in bytes, 4 or 8 - * @val_sz: Size of data values in bytes, can be 0 - */ -#define INIT_CHASH_TABLE(tbl, bts, key_sz, val_sz) \ - __CHASH_TABLE_INIT(((tbl).table), (tbl).data, bts, key_sz, val_sz) - -int chash_table_alloc(struct chash_table *table, u8 bits, u8 key_size, - unsigned int value_size, gfp_t gfp_mask); -void chash_table_free(struct chash_table *table); - -/** - * chash_table_dump_stats - Dump statistics of a closed hash table - * @tbl: Pointer to the table structure - * - * Dumps some performance statistics of the table gathered in operation - * in the kernel log using pr_debug. If CONFIG_DYNAMIC_DEBUG is enabled, - * user must turn on messages for chash.c (file chash.c +p). - */ -#ifdef CONFIG_CHASH_STATS -#define chash_table_dump_stats(tbl) __chash_table_dump_stats(&(*tbl).table) - -void __chash_table_dump_stats(struct __chash_table *table); -#else -#define chash_table_dump_stats(tbl) -#endif - -/** - * chash_table_reset_stats - Reset statistics of a closed hash table - * @tbl: Pointer to the table structure - */ -#ifdef CONFIG_CHASH_STATS -#define chash_table_reset_stats(tbl) __chash_table_reset_stats(&(*tbl).table) - -static inline void __chash_table_reset_stats(struct __chash_table *table) -{ - (void)table __CHASH_STATS_INIT((*table)); -} -#else -#define chash_table_reset_stats(tbl) -#endif - -/** - * chash_table_copy_in - Copy a new value into the hash table - * @tbl: Pointer to the table structure - * @key: Key of the entry to add or update - * @value: Pointer to value to copy, may be NULL - * - * If @key already has an entry, its value is replaced. Otherwise a - * new entry is added. If @value is NULL, the value is left unchanged - * or uninitialized. Returns 1 if an entry already existed, 0 if a new - * entry was added or %-ENOMEM if there was no free space in the - * table. - */ -#define chash_table_copy_in(tbl, key, value) \ - __chash_table_copy_in(&(*tbl).table, key, value) - -int __chash_table_copy_in(struct __chash_table *table, u64 key, - const void *value); - -/** - * chash_table_copy_out - Copy a value out of the hash table - * @tbl: Pointer to the table structure - * @key: Key of the entry to find - * @value: Pointer to value to copy, may be NULL - * - * If @value is not NULL and the table has a non-0 value_size, the - * value at @key is copied to @value. Returns the slot index of the - * entry or %-EINVAL if @key was not found. - */ -#define chash_table_copy_out(tbl, key, value) \ - __chash_table_copy_out(&(*tbl).table, key, value, false) - -int __chash_table_copy_out(struct __chash_table *table, u64 key, - void *value, bool remove); - -/** - * chash_table_remove - Remove an entry from the hash table - * @tbl: Pointer to the table structure - * @key: Key of the entry to find - * @value: Pointer to value to copy, may be NULL - * - * If @value is not NULL and the table has a non-0 value_size, the - * value at @key is copied to @value. The entry is removed from the - * table. Returns the slot index of the removed entry or %-EINVAL if - * @key was not found. - */ -#define chash_table_remove(tbl, key, value) \ - __chash_table_copy_out(&(*tbl).table, key, value, true) - -/* - * Low level iterator API used internally by the above functions. - */ -struct chash_iter { - struct __chash_table *table; - unsigned long mask; - int slot; -}; - -/** - * CHASH_ITER_INIT - Initialize a hash table iterator - * @tbl: Pointer to hash table to iterate over - * @s: Initial slot number - */ -#define CHASH_ITER_INIT(table, s) { \ - table, \ - 1UL << ((s) & (BITS_PER_LONG - 1)), \ - s \ - } -/** - * CHASH_ITER_SET - Set hash table iterator to new slot - * @iter: Iterator - * @s: Slot number - */ -#define CHASH_ITER_SET(iter, s) \ - (iter).mask = 1UL << ((s) & (BITS_PER_LONG - 1)), \ - (iter).slot = (s) -/** - * CHASH_ITER_INC - Increment hash table iterator - * @table: Hash table to iterate over - * - * Wraps around at the end. - */ -#define CHASH_ITER_INC(iter) do { \ - (iter).mask = (iter).mask << 1 | \ - (iter).mask >> (BITS_PER_LONG - 1); \ - (iter).slot = ((iter).slot + 1) & (iter).table->size_mask; \ - } while (0) - -static inline bool chash_iter_is_valid(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - return !!(iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] & - iter.mask); -} -static inline bool chash_iter_is_empty(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - return !(iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] & - iter.mask); -} - -static inline void chash_iter_set_valid(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] |= iter.mask; - iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] |= iter.mask; -} -static inline void chash_iter_set_invalid(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &= ~iter.mask; -} -static inline void chash_iter_set_empty(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &= ~iter.mask; -} - -static inline u32 chash_iter_key32(const struct chash_iter iter) -{ - BUG_ON(iter.table->key_size != 4); - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - return iter.table->keys32[iter.slot]; -} -static inline u64 chash_iter_key64(const struct chash_iter iter) -{ - BUG_ON(iter.table->key_size != 8); - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - return iter.table->keys64[iter.slot]; -} -static inline u64 chash_iter_key(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - return (iter.table->key_size == 4) ? - iter.table->keys32[iter.slot] : iter.table->keys64[iter.slot]; -} - -static inline u32 chash_iter_hash32(const struct chash_iter iter) -{ - BUG_ON(iter.table->key_size != 4); - return hash_32(chash_iter_key32(iter), iter.table->bits); -} - -static inline u32 chash_iter_hash64(const struct chash_iter iter) -{ - BUG_ON(iter.table->key_size != 8); - return hash_64(chash_iter_key64(iter), iter.table->bits); -} - -static inline u32 chash_iter_hash(const struct chash_iter iter) -{ - return (iter.table->key_size == 4) ? - hash_32(chash_iter_key32(iter), iter.table->bits) : - hash_64(chash_iter_key64(iter), iter.table->bits); -} - -static inline void *chash_iter_value(const struct chash_iter iter) -{ - BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits)); - return iter.table->values + - ((unsigned long)iter.slot * iter.table->value_size); -} - -#endif /* _LINUX_CHASH_H */ |