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 * Returns true on sucess. 73 * Returns false if the @p-@hash pair already exists in the hash table. 74 */ 75 bool qht_insert(struct qht *ht, void *p, uint32_t hash); 76 77 /** 78 * qht_lookup - Look up a pointer in a QHT 79 * @ht: QHT to be looked up 80 * @func: function to compare existing pointers against @userp 81 * @userp: pointer to pass to @func 82 * @hash: hash of the pointer to be looked up 83 * 84 * Needs to be called under an RCU read-critical section. 85 * 86 * The user-provided @func compares pointers in QHT against @userp. 87 * If the function returns true, a match has been found. 88 * 89 * Returns the corresponding pointer when a match is found. 90 * Returns NULL otherwise. 91 */ 92 void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, 93 uint32_t hash); 94 95 /** 96 * qht_remove - remove a pointer from the hash table 97 * @ht: QHT to remove from 98 * @p: pointer to be removed 99 * @hash: hash corresponding to @p 100 * 101 * Attempting to remove a NULL @p is a bug. 102 * 103 * Just-removed @p pointers cannot be immediately freed; they need to remain 104 * valid until the end of the RCU grace period in which qht_remove() is called. 105 * This guarantees that concurrent lookups will always compare against valid 106 * data. 107 * 108 * Returns true on success. 109 * Returns false if the @p-@hash pair was not found. 110 */ 111 bool qht_remove(struct qht *ht, const void *p, uint32_t hash); 112 113 /** 114 * qht_reset - reset a QHT 115 * @ht: QHT to be reset 116 * 117 * All entries in the hash table are reset. No resizing is performed. 118 * 119 * If concurrent readers may exist, the objects pointed to by the hash table 120 * must remain valid for the existing RCU grace period -- see qht_remove(). 121 * See also: qht_reset_size() 122 */ 123 void qht_reset(struct qht *ht); 124 125 /** 126 * qht_reset_size - reset and resize a QHT 127 * @ht: QHT to be reset and resized 128 * @n_elems: number of entries the resized hash table should be optimized for. 129 * 130 * Returns true if the resize was necessary and therefore performed. 131 * Returns false otherwise. 132 * 133 * If concurrent readers may exist, the objects pointed to by the hash table 134 * must remain valid for the existing RCU grace period -- see qht_remove(). 135 * See also: qht_reset(), qht_resize(). 136 */ 137 bool qht_reset_size(struct qht *ht, size_t n_elems); 138 139 /** 140 * qht_resize - resize a QHT 141 * @ht: QHT to be resized 142 * @n_elems: number of entries the resized hash table should be optimized for 143 * 144 * Returns true on success. 145 * Returns false if the resize was not necessary and therefore not performed. 146 * See also: qht_reset_size(). 147 */ 148 bool qht_resize(struct qht *ht, size_t n_elems); 149 150 /** 151 * qht_iter - Iterate over a QHT 152 * @ht: QHT to be iterated over 153 * @func: function to be called for each entry in QHT 154 * @userp: additional pointer to be passed to @func 155 * 156 * Each time it is called, user-provided @func is passed a pointer-hash pair, 157 * plus @userp. 158 */ 159 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); 160 161 /** 162 * qht_statistics_init - Gather statistics from a QHT 163 * @ht: QHT to gather statistics from 164 * @stats: pointer to a struct qht_stats to be filled in 165 * 166 * Does NOT need to be called under an RCU read-critical section, 167 * since it does not dereference any pointers stored in the hash table. 168 * 169 * When done with @stats, pass the struct to qht_statistics_destroy(). 170 * Failing to do this will leak memory. 171 */ 172 void qht_statistics_init(struct qht *ht, struct qht_stats *stats); 173 174 /** 175 * qht_statistics_destroy - Destroy a struct qht_stats 176 * @stats: stuct qht_stats to be destroyed 177 * 178 * See also: qht_statistics_init(). 179 */ 180 void qht_statistics_destroy(struct qht_stats *stats); 181 182 #endif /* QEMU_QHT_H */ 183