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 struct qht { 15 struct qht_map *map; 16 QemuMutex lock; /* serializes setters of ht->map */ 17 unsigned int mode; 18 }; 19 20 /** 21 * struct qht_stats - Statistics of a QHT 22 * @head_buckets: number of head buckets 23 * @used_head_buckets: number of non-empty head buckets 24 * @entries: total number of entries 25 * @chain: frequency distribution representing the number of buckets in each 26 * chain, excluding empty chains. 27 * @occupancy: frequency distribution representing chain occupancy rate. 28 * Valid range: from 0.0 (empty) to 1.0 (full occupancy). 29 * 30 * An entry is a pointer-hash pair. 31 * Each bucket can host several entries. 32 * Chains are chains of buckets, whose first link is always a head bucket. 33 */ 34 struct qht_stats { 35 size_t head_buckets; 36 size_t used_head_buckets; 37 size_t entries; 38 struct qdist chain; 39 struct qdist occupancy; 40 }; 41 42 typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); 43 typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up); 44 45 #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ 46 47 /** 48 * qht_init - Initialize a QHT 49 * @ht: QHT to be initialized 50 * @n_elems: number of entries the hash table should be optimized for. 51 * @mode: bitmask with OR'ed QHT_MODE_* 52 */ 53 void qht_init(struct qht *ht, size_t n_elems, unsigned int mode); 54 55 /** 56 * qht_destroy - destroy a previously initialized QHT 57 * @ht: QHT to be destroyed 58 * 59 * Call only when there are no readers/writers left. 60 */ 61 void qht_destroy(struct qht *ht); 62 63 /** 64 * qht_insert - Insert a pointer into the hash table 65 * @ht: QHT to insert to 66 * @p: pointer to be inserted 67 * @hash: hash corresponding to @p 68 * 69 * Attempting to insert a NULL @p is a bug. 70 * Inserting the same pointer @p with different @hash values is a bug. 71 * 72 * In case of successful operation, smp_wmb() is implied before the pointer is 73 * inserted into the hash table. 74 * 75 * Returns true on sucess. 76 * Returns false if the @p-@hash pair already exists in the hash table. 77 */ 78 bool qht_insert(struct qht *ht, void *p, uint32_t hash); 79 80 /** 81 * qht_lookup - Look up a pointer in a QHT 82 * @ht: QHT to be looked up 83 * @func: function to compare existing pointers against @userp 84 * @userp: pointer to pass to @func 85 * @hash: hash of the pointer to be looked up 86 * 87 * Needs to be called under an RCU read-critical section. 88 * 89 * smp_read_barrier_depends() is implied before the call to @func. 90 * 91 * The user-provided @func compares pointers in QHT against @userp. 92 * If the function returns true, a match has been found. 93 * 94 * Returns the corresponding pointer when a match is found. 95 * Returns NULL otherwise. 96 */ 97 void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, 98 uint32_t hash); 99 100 /** 101 * qht_remove - remove a pointer from the hash table 102 * @ht: QHT to remove from 103 * @p: pointer to be removed 104 * @hash: hash corresponding to @p 105 * 106 * Attempting to remove a NULL @p is a bug. 107 * 108 * Just-removed @p pointers cannot be immediately freed; they need to remain 109 * valid until the end of the RCU grace period in which qht_remove() is called. 110 * This guarantees that concurrent lookups will always compare against valid 111 * data. 112 * 113 * Returns true on success. 114 * Returns false if the @p-@hash pair was not found. 115 */ 116 bool qht_remove(struct qht *ht, const void *p, uint32_t hash); 117 118 /** 119 * qht_reset - reset a QHT 120 * @ht: QHT to be reset 121 * 122 * All entries in the hash table are reset. No resizing is performed. 123 * 124 * If concurrent readers may exist, the objects pointed to by the hash table 125 * must remain valid for the existing RCU grace period -- see qht_remove(). 126 * See also: qht_reset_size() 127 */ 128 void qht_reset(struct qht *ht); 129 130 /** 131 * qht_reset_size - reset and resize a QHT 132 * @ht: QHT to be reset and resized 133 * @n_elems: number of entries the resized hash table should be optimized for. 134 * 135 * Returns true if the resize was necessary and therefore performed. 136 * Returns false otherwise. 137 * 138 * If concurrent readers may exist, the objects pointed to by the hash table 139 * must remain valid for the existing RCU grace period -- see qht_remove(). 140 * See also: qht_reset(), qht_resize(). 141 */ 142 bool qht_reset_size(struct qht *ht, size_t n_elems); 143 144 /** 145 * qht_resize - resize a QHT 146 * @ht: QHT to be resized 147 * @n_elems: number of entries the resized hash table should be optimized for 148 * 149 * Returns true on success. 150 * Returns false if the resize was not necessary and therefore not performed. 151 * See also: qht_reset_size(). 152 */ 153 bool qht_resize(struct qht *ht, size_t n_elems); 154 155 /** 156 * qht_iter - Iterate over a QHT 157 * @ht: QHT to be iterated over 158 * @func: function to be called for each entry in QHT 159 * @userp: additional pointer to be passed to @func 160 * 161 * Each time it is called, user-provided @func is passed a pointer-hash pair, 162 * plus @userp. 163 */ 164 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); 165 166 /** 167 * qht_statistics_init - Gather statistics from a QHT 168 * @ht: QHT to gather statistics from 169 * @stats: pointer to a struct qht_stats to be filled in 170 * 171 * Does NOT need to be called under an RCU read-critical section, 172 * since it does not dereference any pointers stored in the hash table. 173 * 174 * When done with @stats, pass the struct to qht_statistics_destroy(). 175 * Failing to do this will leak memory. 176 */ 177 void qht_statistics_init(struct qht *ht, struct qht_stats *stats); 178 179 /** 180 * qht_statistics_destroy - Destroy a struct qht_stats 181 * @stats: stuct qht_stats to be destroyed 182 * 183 * See also: qht_statistics_init(). 184 */ 185 void qht_statistics_destroy(struct qht_stats *stats); 186 187 #endif /* QEMU_QHT_H */ 188