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