12e11264aSEmilio G. Cota /* 22e11264aSEmilio G. Cota * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> 32e11264aSEmilio G. Cota * 42e11264aSEmilio G. Cota * License: GNU GPL, version 2 or later. 52e11264aSEmilio G. Cota * See the COPYING file in the top-level directory. 62e11264aSEmilio G. Cota */ 72e11264aSEmilio G. Cota #ifndef QEMU_QHT_H 82e11264aSEmilio G. Cota #define QEMU_QHT_H 92e11264aSEmilio G. Cota 102e11264aSEmilio G. Cota #include "qemu/seqlock.h" 112e11264aSEmilio G. Cota #include "qemu/thread.h" 122e11264aSEmilio G. Cota #include "qemu/qdist.h" 132e11264aSEmilio G. Cota 1461b8cef1SEmilio G. Cota typedef bool (*qht_cmp_func_t)(const void *a, const void *b); 1561b8cef1SEmilio G. Cota 162e11264aSEmilio G. Cota struct qht { 172e11264aSEmilio G. Cota struct qht_map *map; 1861b8cef1SEmilio G. Cota qht_cmp_func_t cmp; 192e11264aSEmilio G. Cota QemuMutex lock; /* serializes setters of ht->map */ 202e11264aSEmilio G. Cota unsigned int mode; 212e11264aSEmilio G. Cota }; 222e11264aSEmilio G. Cota 232e11264aSEmilio G. Cota /** 242e11264aSEmilio G. Cota * struct qht_stats - Statistics of a QHT 252e11264aSEmilio G. Cota * @head_buckets: number of head buckets 262e11264aSEmilio G. Cota * @used_head_buckets: number of non-empty head buckets 272e11264aSEmilio G. Cota * @entries: total number of entries 282e11264aSEmilio G. Cota * @chain: frequency distribution representing the number of buckets in each 292e11264aSEmilio G. Cota * chain, excluding empty chains. 302e11264aSEmilio G. Cota * @occupancy: frequency distribution representing chain occupancy rate. 312e11264aSEmilio G. Cota * Valid range: from 0.0 (empty) to 1.0 (full occupancy). 322e11264aSEmilio G. Cota * 332e11264aSEmilio G. Cota * An entry is a pointer-hash pair. 342e11264aSEmilio G. Cota * Each bucket can host several entries. 352e11264aSEmilio G. Cota * Chains are chains of buckets, whose first link is always a head bucket. 362e11264aSEmilio G. Cota */ 372e11264aSEmilio G. Cota struct qht_stats { 382e11264aSEmilio G. Cota size_t head_buckets; 392e11264aSEmilio G. Cota size_t used_head_buckets; 402e11264aSEmilio G. Cota size_t entries; 412e11264aSEmilio G. Cota struct qdist chain; 422e11264aSEmilio G. Cota struct qdist occupancy; 432e11264aSEmilio G. Cota }; 442e11264aSEmilio G. Cota 452e11264aSEmilio G. Cota typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); 4678255ba2SEmilio G. Cota typedef void (*qht_iter_func_t)(void *p, uint32_t h, void *up); 4778255ba2SEmilio G. Cota typedef bool (*qht_iter_bool_func_t)(void *p, uint32_t h, void *up); 482e11264aSEmilio G. Cota 492e11264aSEmilio G. Cota #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ 50fe9959a2SEmilio G. Cota #define QHT_MODE_RAW_MUTEXES 0x2 /* bypass the profiler (QSP) */ 512e11264aSEmilio G. Cota 522e11264aSEmilio G. Cota /** 532e11264aSEmilio G. Cota * qht_init - Initialize a QHT 542e11264aSEmilio G. Cota * @ht: QHT to be initialized 5561b8cef1SEmilio G. Cota * @cmp: default comparison function. Cannot be NULL. 562e11264aSEmilio G. Cota * @n_elems: number of entries the hash table should be optimized for. 572e11264aSEmilio G. Cota * @mode: bitmask with OR'ed QHT_MODE_* 582e11264aSEmilio G. Cota */ 5961b8cef1SEmilio G. Cota void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems, 6061b8cef1SEmilio G. Cota unsigned int mode); 612e11264aSEmilio G. Cota 622e11264aSEmilio G. Cota /** 632e11264aSEmilio G. Cota * qht_destroy - destroy a previously initialized QHT 642e11264aSEmilio G. Cota * @ht: QHT to be destroyed 652e11264aSEmilio G. Cota * 662e11264aSEmilio G. Cota * Call only when there are no readers/writers left. 672e11264aSEmilio G. Cota */ 682e11264aSEmilio G. Cota void qht_destroy(struct qht *ht); 692e11264aSEmilio G. Cota 702e11264aSEmilio G. Cota /** 712e11264aSEmilio G. Cota * qht_insert - Insert a pointer into the hash table 722e11264aSEmilio G. Cota * @ht: QHT to insert to 732e11264aSEmilio G. Cota * @p: pointer to be inserted 742e11264aSEmilio G. Cota * @hash: hash corresponding to @p 7532359d52SEmilio G. Cota * @existing: address where the pointer to an existing entry can be copied to 762e11264aSEmilio G. Cota * 772e11264aSEmilio G. Cota * Attempting to insert a NULL @p is a bug. 782e11264aSEmilio G. Cota * Inserting the same pointer @p with different @hash values is a bug. 792e11264aSEmilio G. Cota * 8034506b30SPaolo Bonzini * In case of successful operation, smp_wmb() is implied before the pointer is 8134506b30SPaolo Bonzini * inserted into the hash table. 8234506b30SPaolo Bonzini * 835bb8590dSStefan Weil * Returns true on success. 8432359d52SEmilio G. Cota * Returns false if there is an existing entry in the table that is equivalent 8532359d52SEmilio G. Cota * (i.e. ht->cmp matches and the hash is the same) to @p-@h. If @existing 8632359d52SEmilio G. Cota * is !NULL, a pointer to this existing entry is copied to it. 872e11264aSEmilio G. Cota */ 8832359d52SEmilio G. Cota bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing); 892e11264aSEmilio G. Cota 902e11264aSEmilio G. Cota /** 9161b8cef1SEmilio G. Cota * qht_lookup_custom - Look up a pointer using a custom comparison function. 922e11264aSEmilio G. Cota * @ht: QHT to be looked up 932e11264aSEmilio G. Cota * @userp: pointer to pass to @func 942e11264aSEmilio G. Cota * @hash: hash of the pointer to be looked up 9561b8cef1SEmilio G. Cota * @func: function to compare existing pointers against @userp 962e11264aSEmilio G. Cota * 972e11264aSEmilio G. Cota * Needs to be called under an RCU read-critical section. 982e11264aSEmilio G. Cota * 9934506b30SPaolo Bonzini * smp_read_barrier_depends() is implied before the call to @func. 10034506b30SPaolo Bonzini * 1012e11264aSEmilio G. Cota * The user-provided @func compares pointers in QHT against @userp. 1022e11264aSEmilio G. Cota * If the function returns true, a match has been found. 1032e11264aSEmilio G. Cota * 1042e11264aSEmilio G. Cota * Returns the corresponding pointer when a match is found. 1052e11264aSEmilio G. Cota * Returns NULL otherwise. 1062e11264aSEmilio G. Cota */ 107e6c58299SEmilio G. Cota void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash, 10861b8cef1SEmilio G. Cota qht_lookup_func_t func); 10961b8cef1SEmilio G. Cota 11061b8cef1SEmilio G. Cota /** 11161b8cef1SEmilio G. Cota * qht_lookup - Look up a pointer in a QHT 11261b8cef1SEmilio G. Cota * @ht: QHT to be looked up 11361b8cef1SEmilio G. Cota * @userp: pointer to pass to the comparison function 11461b8cef1SEmilio G. Cota * @hash: hash of the pointer to be looked up 11561b8cef1SEmilio G. Cota * 11661b8cef1SEmilio G. Cota * Calls qht_lookup_custom() using @ht's default comparison function. 11761b8cef1SEmilio G. Cota */ 118e6c58299SEmilio G. Cota void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash); 1192e11264aSEmilio G. Cota 1202e11264aSEmilio G. Cota /** 1212e11264aSEmilio G. Cota * qht_remove - remove a pointer from the hash table 1222e11264aSEmilio G. Cota * @ht: QHT to remove from 1232e11264aSEmilio G. Cota * @p: pointer to be removed 1242e11264aSEmilio G. Cota * @hash: hash corresponding to @p 1252e11264aSEmilio G. Cota * 1262e11264aSEmilio G. Cota * Attempting to remove a NULL @p is a bug. 1272e11264aSEmilio G. Cota * 1282e11264aSEmilio G. Cota * Just-removed @p pointers cannot be immediately freed; they need to remain 1292e11264aSEmilio G. Cota * valid until the end of the RCU grace period in which qht_remove() is called. 1302e11264aSEmilio G. Cota * This guarantees that concurrent lookups will always compare against valid 1312e11264aSEmilio G. Cota * data. 1322e11264aSEmilio G. Cota * 1332e11264aSEmilio G. Cota * Returns true on success. 1342e11264aSEmilio G. Cota * Returns false if the @p-@hash pair was not found. 1352e11264aSEmilio G. Cota */ 1362e11264aSEmilio G. Cota bool qht_remove(struct qht *ht, const void *p, uint32_t hash); 1372e11264aSEmilio G. Cota 1382e11264aSEmilio G. Cota /** 1392e11264aSEmilio G. Cota * qht_reset - reset a QHT 1402e11264aSEmilio G. Cota * @ht: QHT to be reset 1412e11264aSEmilio G. Cota * 1422e11264aSEmilio G. Cota * All entries in the hash table are reset. No resizing is performed. 1432e11264aSEmilio G. Cota * 1442e11264aSEmilio G. Cota * If concurrent readers may exist, the objects pointed to by the hash table 1452e11264aSEmilio G. Cota * must remain valid for the existing RCU grace period -- see qht_remove(). 1462e11264aSEmilio G. Cota * See also: qht_reset_size() 1472e11264aSEmilio G. Cota */ 1482e11264aSEmilio G. Cota void qht_reset(struct qht *ht); 1492e11264aSEmilio G. Cota 1502e11264aSEmilio G. Cota /** 1512e11264aSEmilio G. Cota * qht_reset_size - reset and resize a QHT 1522e11264aSEmilio G. Cota * @ht: QHT to be reset and resized 1532e11264aSEmilio G. Cota * @n_elems: number of entries the resized hash table should be optimized for. 1542e11264aSEmilio G. Cota * 1552e11264aSEmilio G. Cota * Returns true if the resize was necessary and therefore performed. 1562e11264aSEmilio G. Cota * Returns false otherwise. 1572e11264aSEmilio G. Cota * 1582e11264aSEmilio G. Cota * If concurrent readers may exist, the objects pointed to by the hash table 1592e11264aSEmilio G. Cota * must remain valid for the existing RCU grace period -- see qht_remove(). 1602e11264aSEmilio G. Cota * See also: qht_reset(), qht_resize(). 1612e11264aSEmilio G. Cota */ 1622e11264aSEmilio G. Cota bool qht_reset_size(struct qht *ht, size_t n_elems); 1632e11264aSEmilio G. Cota 1642e11264aSEmilio G. Cota /** 1652e11264aSEmilio G. Cota * qht_resize - resize a QHT 1662e11264aSEmilio G. Cota * @ht: QHT to be resized 1672e11264aSEmilio G. Cota * @n_elems: number of entries the resized hash table should be optimized for 1682e11264aSEmilio G. Cota * 1692e11264aSEmilio G. Cota * Returns true on success. 1702e11264aSEmilio G. Cota * Returns false if the resize was not necessary and therefore not performed. 1712e11264aSEmilio G. Cota * See also: qht_reset_size(). 1722e11264aSEmilio G. Cota */ 1732e11264aSEmilio G. Cota bool qht_resize(struct qht *ht, size_t n_elems); 1742e11264aSEmilio G. Cota 1752e11264aSEmilio G. Cota /** 1762e11264aSEmilio G. Cota * qht_iter - Iterate over a QHT 1772e11264aSEmilio G. Cota * @ht: QHT to be iterated over 1782e11264aSEmilio G. Cota * @func: function to be called for each entry in QHT 1792e11264aSEmilio G. Cota * @userp: additional pointer to be passed to @func 1802e11264aSEmilio G. Cota * 1812e11264aSEmilio G. Cota * Each time it is called, user-provided @func is passed a pointer-hash pair, 1822e11264aSEmilio G. Cota * plus @userp. 18369d55e9cSEmilio G. Cota * 18469d55e9cSEmilio G. Cota * Note: @ht cannot be accessed from @func 18569d55e9cSEmilio G. Cota * See also: qht_iter_remove() 1862e11264aSEmilio G. Cota */ 1872e11264aSEmilio G. Cota void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); 1882e11264aSEmilio G. Cota 1892e11264aSEmilio G. Cota /** 19069d55e9cSEmilio G. Cota * qht_iter_remove - Iterate over a QHT, optionally removing entries 19169d55e9cSEmilio G. Cota * @ht: QHT to be iterated over 19269d55e9cSEmilio G. Cota * @func: function to be called for each entry in QHT 19369d55e9cSEmilio G. Cota * @userp: additional pointer to be passed to @func 19469d55e9cSEmilio G. Cota * 19569d55e9cSEmilio G. Cota * Each time it is called, user-provided @func is passed a pointer-hash pair, 19669d55e9cSEmilio G. Cota * plus @userp. If @func returns true, the pointer-hash pair is removed. 19769d55e9cSEmilio G. Cota * 19869d55e9cSEmilio G. Cota * Note: @ht cannot be accessed from @func 19969d55e9cSEmilio G. Cota * See also: qht_iter() 20069d55e9cSEmilio G. Cota */ 20169d55e9cSEmilio G. Cota void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp); 20269d55e9cSEmilio G. Cota 20369d55e9cSEmilio G. Cota /** 2042e11264aSEmilio G. Cota * qht_statistics_init - Gather statistics from a QHT 2052e11264aSEmilio G. Cota * @ht: QHT to gather statistics from 2066b1a7561SEmilio G. Cota * @stats: pointer to a &struct qht_stats to be filled in 2072e11264aSEmilio G. Cota * 2082e11264aSEmilio G. Cota * Does NOT need to be called under an RCU read-critical section, 2092e11264aSEmilio G. Cota * since it does not dereference any pointers stored in the hash table. 2102e11264aSEmilio G. Cota * 2112e11264aSEmilio G. Cota * When done with @stats, pass the struct to qht_statistics_destroy(). 2122e11264aSEmilio G. Cota * Failing to do this will leak memory. 2132e11264aSEmilio G. Cota */ 214*6579f107SEmilio G. Cota void qht_statistics_init(const struct qht *ht, struct qht_stats *stats); 2152e11264aSEmilio G. Cota 2162e11264aSEmilio G. Cota /** 2176b1a7561SEmilio G. Cota * qht_statistics_destroy - Destroy a &struct qht_stats 2186b1a7561SEmilio G. Cota * @stats: &struct qht_stats to be destroyed 2192e11264aSEmilio G. Cota * 2202e11264aSEmilio G. Cota * See also: qht_statistics_init(). 2212e11264aSEmilio G. Cota */ 2222e11264aSEmilio G. Cota void qht_statistics_destroy(struct qht_stats *stats); 2232e11264aSEmilio G. Cota 2242e11264aSEmilio G. Cota #endif /* QEMU_QHT_H */ 225