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
14typedef bool (*qht_cmp_func_t)(const void *a, const void *b);
15
16struct 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 */
37struct 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
45typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp);
46typedef void (*qht_iter_func_t)(void *p, uint32_t h, void *up);
47typedef 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 */
59void 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 */
68void 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 */
88bool 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 */
107void *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 */
118void *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 */
136bool 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 */
148void 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 */
162bool 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 */
173bool 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 */
187void 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 */
201void 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 */
214void 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 */
222void qht_statistics_destroy(struct qht_stats *stats);
223
224#endif /* QEMU_QHT_H */
225