1 | /* |
2 | * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> |
3 | * |
4 | * License: GNU GPL, version 2 or later. |
5 | * See the COPYING file in the top-level directory. |
6 | */ |
7 | #ifndef QEMU_QHT_H |
8 | #define QEMU_QHT_H |
9 | |
10 | #include "qemu/seqlock.h" |
11 | #include "qemu/thread.h" |
12 | #include "qemu/qdist.h" |
13 | |
14 | typedef bool (*qht_cmp_func_t)(const void *a, const void *b); |
15 | |
16 | struct qht { |
17 | struct qht_map *map; |
18 | qht_cmp_func_t cmp; |
19 | QemuMutex lock; /* serializes setters of ht->map */ |
20 | unsigned int mode; |
21 | }; |
22 | |
23 | /** |
24 | * struct qht_stats - Statistics of a QHT |
25 | * @head_buckets: number of head buckets |
26 | * @used_head_buckets: number of non-empty head buckets |
27 | * @entries: total number of entries |
28 | * @chain: frequency distribution representing the number of buckets in each |
29 | * chain, excluding empty chains. |
30 | * @occupancy: frequency distribution representing chain occupancy rate. |
31 | * Valid range: from 0.0 (empty) to 1.0 (full occupancy). |
32 | * |
33 | * An entry is a pointer-hash pair. |
34 | * Each bucket can host several entries. |
35 | * Chains are chains of buckets, whose first link is always a head bucket. |
36 | */ |
37 | struct qht_stats { |
38 | size_t head_buckets; |
39 | size_t used_head_buckets; |
40 | size_t entries; |
41 | struct qdist chain; |
42 | struct qdist occupancy; |
43 | }; |
44 | |
45 | typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); |
46 | typedef void (*qht_iter_func_t)(void *p, uint32_t h, void *up); |
47 | typedef bool (*qht_iter_bool_func_t)(void *p, uint32_t h, void *up); |
48 | |
49 | #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ |
50 | #define QHT_MODE_RAW_MUTEXES 0x2 /* bypass the profiler (QSP) */ |
51 | |
52 | /** |
53 | * qht_init - Initialize a QHT |
54 | * @ht: QHT to be initialized |
55 | * @cmp: default comparison function. Cannot be NULL. |
56 | * @n_elems: number of entries the hash table should be optimized for. |
57 | * @mode: bitmask with OR'ed QHT_MODE_* |
58 | */ |
59 | void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems, |
60 | unsigned int mode); |
61 | |
62 | /** |
63 | * qht_destroy - destroy a previously initialized QHT |
64 | * @ht: QHT to be destroyed |
65 | * |
66 | * Call only when there are no readers/writers left. |
67 | */ |
68 | void qht_destroy(struct qht *ht); |
69 | |
70 | /** |
71 | * qht_insert - Insert a pointer into the hash table |
72 | * @ht: QHT to insert to |
73 | * @p: pointer to be inserted |
74 | * @hash: hash corresponding to @p |
75 | * @existing: address where the pointer to an existing entry can be copied to |
76 | * |
77 | * Attempting to insert a NULL @p is a bug. |
78 | * Inserting the same pointer @p with different @hash values is a bug. |
79 | * |
80 | * In case of successful operation, smp_wmb() is implied before the pointer is |
81 | * inserted into the hash table. |
82 | * |
83 | * Returns true on success. |
84 | * Returns false if there is an existing entry in the table that is equivalent |
85 | * (i.e. ht->cmp matches and the hash is the same) to @p-@h. If @existing |
86 | * is !NULL, a pointer to this existing entry is copied to it. |
87 | */ |
88 | bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing); |
89 | |
90 | /** |
91 | * qht_lookup_custom - Look up a pointer using a custom comparison function. |
92 | * @ht: QHT to be looked up |
93 | * @userp: pointer to pass to @func |
94 | * @hash: hash of the pointer to be looked up |
95 | * @func: function to compare existing pointers against @userp |
96 | * |
97 | * Needs to be called under an RCU read-critical section. |
98 | * |
99 | * smp_read_barrier_depends() is implied before the call to @func. |
100 | * |
101 | * The user-provided @func compares pointers in QHT against @userp. |
102 | * If the function returns true, a match has been found. |
103 | * |
104 | * Returns the corresponding pointer when a match is found. |
105 | * Returns NULL otherwise. |
106 | */ |
107 | void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash, |
108 | qht_lookup_func_t func); |
109 | |
110 | /** |
111 | * qht_lookup - Look up a pointer in a QHT |
112 | * @ht: QHT to be looked up |
113 | * @userp: pointer to pass to the comparison function |
114 | * @hash: hash of the pointer to be looked up |
115 | * |
116 | * Calls qht_lookup_custom() using @ht's default comparison function. |
117 | */ |
118 | void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash); |
119 | |
120 | /** |
121 | * qht_remove - remove a pointer from the hash table |
122 | * @ht: QHT to remove from |
123 | * @p: pointer to be removed |
124 | * @hash: hash corresponding to @p |
125 | * |
126 | * Attempting to remove a NULL @p is a bug. |
127 | * |
128 | * Just-removed @p pointers cannot be immediately freed; they need to remain |
129 | * valid until the end of the RCU grace period in which qht_remove() is called. |
130 | * This guarantees that concurrent lookups will always compare against valid |
131 | * data. |
132 | * |
133 | * Returns true on success. |
134 | * Returns false if the @p-@hash pair was not found. |
135 | */ |
136 | bool qht_remove(struct qht *ht, const void *p, uint32_t hash); |
137 | |
138 | /** |
139 | * qht_reset - reset a QHT |
140 | * @ht: QHT to be reset |
141 | * |
142 | * All entries in the hash table are reset. No resizing is performed. |
143 | * |
144 | * If concurrent readers may exist, the objects pointed to by the hash table |
145 | * must remain valid for the existing RCU grace period -- see qht_remove(). |
146 | * See also: qht_reset_size() |
147 | */ |
148 | void qht_reset(struct qht *ht); |
149 | |
150 | /** |
151 | * qht_reset_size - reset and resize a QHT |
152 | * @ht: QHT to be reset and resized |
153 | * @n_elems: number of entries the resized hash table should be optimized for. |
154 | * |
155 | * Returns true if the resize was necessary and therefore performed. |
156 | * Returns false otherwise. |
157 | * |
158 | * If concurrent readers may exist, the objects pointed to by the hash table |
159 | * must remain valid for the existing RCU grace period -- see qht_remove(). |
160 | * See also: qht_reset(), qht_resize(). |
161 | */ |
162 | bool qht_reset_size(struct qht *ht, size_t n_elems); |
163 | |
164 | /** |
165 | * qht_resize - resize a QHT |
166 | * @ht: QHT to be resized |
167 | * @n_elems: number of entries the resized hash table should be optimized for |
168 | * |
169 | * Returns true on success. |
170 | * Returns false if the resize was not necessary and therefore not performed. |
171 | * See also: qht_reset_size(). |
172 | */ |
173 | bool qht_resize(struct qht *ht, size_t n_elems); |
174 | |
175 | /** |
176 | * qht_iter - Iterate over a QHT |
177 | * @ht: QHT to be iterated over |
178 | * @func: function to be called for each entry in QHT |
179 | * @userp: additional pointer to be passed to @func |
180 | * |
181 | * Each time it is called, user-provided @func is passed a pointer-hash pair, |
182 | * plus @userp. |
183 | * |
184 | * Note: @ht cannot be accessed from @func |
185 | * See also: qht_iter_remove() |
186 | */ |
187 | void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); |
188 | |
189 | /** |
190 | * qht_iter_remove - Iterate over a QHT, optionally removing entries |
191 | * @ht: QHT to be iterated over |
192 | * @func: function to be called for each entry in QHT |
193 | * @userp: additional pointer to be passed to @func |
194 | * |
195 | * Each time it is called, user-provided @func is passed a pointer-hash pair, |
196 | * plus @userp. If @func returns true, the pointer-hash pair is removed. |
197 | * |
198 | * Note: @ht cannot be accessed from @func |
199 | * See also: qht_iter() |
200 | */ |
201 | void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp); |
202 | |
203 | /** |
204 | * qht_statistics_init - Gather statistics from a QHT |
205 | * @ht: QHT to gather statistics from |
206 | * @stats: pointer to a &struct qht_stats to be filled in |
207 | * |
208 | * Does NOT need to be called under an RCU read-critical section, |
209 | * since it does not dereference any pointers stored in the hash table. |
210 | * |
211 | * When done with @stats, pass the struct to qht_statistics_destroy(). |
212 | * Failing to do this will leak memory. |
213 | */ |
214 | void qht_statistics_init(const struct qht *ht, struct qht_stats *stats); |
215 | |
216 | /** |
217 | * qht_statistics_destroy - Destroy a &struct qht_stats |
218 | * @stats: &struct qht_stats to be destroyed |
219 | * |
220 | * See also: qht_statistics_init(). |
221 | */ |
222 | void qht_statistics_destroy(struct qht_stats *stats); |
223 | |
224 | #endif /* QEMU_QHT_H */ |
225 | |