Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
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
19struct rhash_head {
20 struct rhash_head __rcu *next;
21};
22
23struct rhlist_head {
24 struct rhash_head rhead;
25 struct rhlist_head __rcu *next;
26};
27
28struct 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 */
35struct rhashtable_compare_arg {
36 struct rhashtable *ht;
37 const void *key;
38};
39
40typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
41typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
42typedef 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 */
59struct 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 */
86struct 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 */
106struct 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 */
115struct 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 */
129struct 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
139int rhashtable_init_noprof(struct rhashtable *ht,
140 const struct rhashtable_params *params);
141#define rhashtable_init(...) alloc_hooks(rhashtable_init_noprof(__VA_ARGS__))
142
143int 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 */