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