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