1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * Resizable, Scalable, Concurrent Hash Table 4 * 5 * Simple structures that might be needed in include 6 * files. 7 */ 8 9 #ifndef _LINUX_RHASHTABLE_TYPES_H 10 #define _LINUX_RHASHTABLE_TYPES_H 11 12 #include <linux/alloc_tag.h> 13 #include <linux/atomic.h> 14 #include <linux/compiler.h> 15 #include <linux/mutex.h> 16 #include <linux/workqueue_types.h> 17 18 struct rhash_head { 19 struct rhash_head __rcu *next; 20 }; 21 22 struct rhlist_head { 23 struct rhash_head rhead; 24 struct rhlist_head __rcu *next; 25 }; 26 27 struct bucket_table; 28 29 /** 30 * struct rhashtable_compare_arg - Key for the function rhashtable_compare 31 * @ht: Hash table 32 * @key: Key to compare against 33 */ 34 struct rhashtable_compare_arg { 35 struct rhashtable *ht; 36 const void *key; 37 }; 38 39 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed); 40 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed); 41 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg, 42 const void *obj); 43 44 /** 45 * struct rhashtable_params - Hash table construction parameters 46 * @nelem_hint: Hint on number of elements, should be 75% of desired size 47 * @key_len: Length of key 48 * @key_offset: Offset of key in struct to be hashed 49 * @head_offset: Offset of rhash_head in struct to be hashed 50 * @max_size: Maximum size while expanding 51 * @min_size: Minimum size while shrinking 52 * @automatic_shrinking: Enable automatic shrinking of tables 53 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash) 54 * @obj_hashfn: Function to hash object 55 * @obj_cmpfn: Function to compare key with object 56 */ 57 struct rhashtable_params { 58 u16 nelem_hint; 59 u16 key_len; 60 u16 key_offset; 61 u16 head_offset; 62 unsigned int max_size; 63 u16 min_size; 64 bool automatic_shrinking; 65 rht_hashfn_t hashfn; 66 rht_obj_hashfn_t obj_hashfn; 67 rht_obj_cmpfn_t obj_cmpfn; 68 }; 69 70 /** 71 * struct rhashtable - Hash table handle 72 * @tbl: Bucket table 73 * @key_len: Key length for hashfn 74 * @max_elems: Maximum number of elements in table 75 * @p: Configuration parameters 76 * @rhlist: True if this is an rhltable 77 * @run_work: Deferred worker to expand/shrink asynchronously 78 * @mutex: Mutex to protect current/future table swapping 79 * @lock: Spin lock to protect walker list 80 * @nelems: Number of elements in table 81 */ 82 struct rhashtable { 83 struct bucket_table __rcu *tbl; 84 unsigned int key_len; 85 unsigned int max_elems; 86 struct rhashtable_params p; 87 bool rhlist; 88 struct work_struct run_work; 89 struct mutex mutex; 90 spinlock_t lock; 91 atomic_t nelems; 92 #ifdef CONFIG_MEM_ALLOC_PROFILING 93 struct alloc_tag *alloc_tag; 94 #endif 95 }; 96 97 /** 98 * struct rhltable - Hash table with duplicate objects in a list 99 * @ht: Underlying rhtable 100 */ 101 struct rhltable { 102 struct rhashtable ht; 103 }; 104 105 /** 106 * struct rhashtable_walker - Hash table walker 107 * @list: List entry on list of walkers 108 * @tbl: The table that we were walking over 109 */ 110 struct rhashtable_walker { 111 struct list_head list; 112 struct bucket_table *tbl; 113 }; 114 115 /** 116 * struct rhashtable_iter - Hash table iterator 117 * @ht: Table to iterate through 118 * @p: Current pointer 119 * @list: Current hash list pointer 120 * @walker: Associated rhashtable walker 121 * @slot: Current slot 122 * @skip: Number of entries to skip in slot 123 */ 124 struct rhashtable_iter { 125 struct rhashtable *ht; 126 struct rhash_head *p; 127 struct rhlist_head *list; 128 struct rhashtable_walker walker; 129 unsigned int slot; 130 unsigned int skip; 131 bool end_of_table; 132 }; 133 134 int rhashtable_init_noprof(struct rhashtable *ht, 135 const struct rhashtable_params *params); 136 #define rhashtable_init(...) alloc_hooks(rhashtable_init_noprof(__VA_ARGS__)) 137 138 int rhltable_init_noprof(struct rhltable *hlt, 139 const struct rhashtable_params *params); 140 #define rhltable_init(...) alloc_hooks(rhltable_init_noprof(__VA_ARGS__)) 141 142 #endif /* _LINUX_RHASHTABLE_TYPES_H */ 143