summaryrefslogtreecommitdiff
path: root/drivers/gpu/drm/amd/include/linux/chash.h
blob: 6dc159924ed108927d24aa24e1619a8a1f8dfbbc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
/*
 * 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 */