| 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 */ |