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