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