12e11264aSEmilio G. Cota /*
22e11264aSEmilio G. Cota * qht.c - QEMU Hash Table, designed to scale for read-mostly workloads.
32e11264aSEmilio G. Cota *
42e11264aSEmilio G. Cota * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
52e11264aSEmilio G. Cota *
62e11264aSEmilio G. Cota * License: GNU GPL, version 2 or later.
72e11264aSEmilio G. Cota * See the COPYING file in the top-level directory.
82e11264aSEmilio G. Cota *
92e11264aSEmilio G. Cota * Assumptions:
102e11264aSEmilio G. Cota * - NULL cannot be inserted/removed as a pointer value.
112e11264aSEmilio G. Cota * - Trying to insert an already-existing hash-pointer pair is OK. However,
122e11264aSEmilio G. Cota * it is not OK to insert into the same hash table different hash-pointer
132e11264aSEmilio G. Cota * pairs that have the same pointer value, but not the hashes.
142e11264aSEmilio G. Cota * - Lookups are performed under an RCU read-critical section; removals
152e11264aSEmilio G. Cota * must wait for a grace period to elapse before freeing removed objects.
162e11264aSEmilio G. Cota *
172e11264aSEmilio G. Cota * Features:
182e11264aSEmilio G. Cota * - Reads (i.e. lookups and iterators) can be concurrent with other reads.
192e11264aSEmilio G. Cota * Lookups that are concurrent with writes to the same bucket will retry
202e11264aSEmilio G. Cota * via a seqlock; iterators acquire all bucket locks and therefore can be
212e11264aSEmilio G. Cota * concurrent with lookups and are serialized wrt writers.
222e11264aSEmilio G. Cota * - Writes (i.e. insertions/removals) can be concurrent with writes to
232e11264aSEmilio G. Cota * different buckets; writes to the same bucket are serialized through a lock.
242e11264aSEmilio G. Cota * - Optional auto-resizing: the hash table resizes up if the load surpasses
252e11264aSEmilio G. Cota * a certain threshold. Resizing is done concurrently with readers; writes
262e11264aSEmilio G. Cota * are serialized with the resize operation.
272e11264aSEmilio G. Cota *
282e11264aSEmilio G. Cota * The key structure is the bucket, which is cacheline-sized. Buckets
292e11264aSEmilio G. Cota * contain a few hash values and pointers; the u32 hash values are stored in
302e11264aSEmilio G. Cota * full so that resizing is fast. Having this structure instead of directly
312e11264aSEmilio G. Cota * chaining items has two advantages:
322e11264aSEmilio G. Cota * - Failed lookups fail fast, and touch a minimum number of cache lines.
332e11264aSEmilio G. Cota * - Resizing the hash table with concurrent lookups is easy.
342e11264aSEmilio G. Cota *
352e11264aSEmilio G. Cota * There are two types of buckets:
362e11264aSEmilio G. Cota * 1. "head" buckets are the ones allocated in the array of buckets in qht_map.
372e11264aSEmilio G. Cota * 2. all "non-head" buckets (i.e. all others) are members of a chain that
382e11264aSEmilio G. Cota * starts from a head bucket.
392e11264aSEmilio G. Cota * Note that the seqlock and spinlock of a head bucket applies to all buckets
402e11264aSEmilio G. Cota * chained to it; these two fields are unused in non-head buckets.
412e11264aSEmilio G. Cota *
422e11264aSEmilio G. Cota * On removals, we move the last valid item in the chain to the position of the
432e11264aSEmilio G. Cota * just-removed entry. This makes lookups slightly faster, since the moment an
442e11264aSEmilio G. Cota * invalid entry is found, the (failed) lookup is over.
452e11264aSEmilio G. Cota *
462e11264aSEmilio G. Cota * Resizing is done by taking all bucket spinlocks (so that no other writers can
472e11264aSEmilio G. Cota * race with us) and then copying all entries into a new hash map. Then, the
482e11264aSEmilio G. Cota * ht->map pointer is set, and the old map is freed once no RCU readers can see
492e11264aSEmilio G. Cota * it anymore.
502e11264aSEmilio G. Cota *
512e11264aSEmilio G. Cota * Writers check for concurrent resizes by comparing ht->map before and after
528cc360b9Szhaolichang * acquiring their bucket lock. If they don't match, a resize has occurred
532e11264aSEmilio G. Cota * while the bucket spinlock was being acquired.
542e11264aSEmilio G. Cota *
552e11264aSEmilio G. Cota * Related Work:
562e11264aSEmilio G. Cota * - Idea of cacheline-sized buckets with full hashes taken from:
572e11264aSEmilio G. Cota * David, Guerraoui & Trigonakis, "Asynchronized Concurrency:
582e11264aSEmilio G. Cota * The Secret to Scaling Concurrent Search Data Structures", ASPLOS'15.
592e11264aSEmilio G. Cota * - Why not RCU-based hash tables? They would allow us to get rid of the
602e11264aSEmilio G. Cota * seqlock, but resizing would take forever since RCU read critical
612e11264aSEmilio G. Cota * sections in QEMU take quite a long time.
622e11264aSEmilio G. Cota * More info on relativistic hash tables:
632e11264aSEmilio G. Cota * + Triplett, McKenney & Walpole, "Resizable, Scalable, Concurrent Hash
642e11264aSEmilio G. Cota * Tables via Relativistic Programming", USENIX ATC'11.
652e11264aSEmilio G. Cota * + Corbet, "Relativistic hash tables, part 1: Algorithms", @ lwn.net, 2014.
662e11264aSEmilio G. Cota * https://lwn.net/Articles/612021/
672e11264aSEmilio G. Cota */
68e9abfcb5SPaolo Bonzini #include "qemu/osdep.h"
692e11264aSEmilio G. Cota #include "qemu/qht.h"
702e11264aSEmilio G. Cota #include "qemu/atomic.h"
712e11264aSEmilio G. Cota #include "qemu/rcu.h"
725df022cfSPeter Maydell #include "qemu/memalign.h"
732e11264aSEmilio G. Cota
742e11264aSEmilio G. Cota //#define QHT_DEBUG
752e11264aSEmilio G. Cota
762e11264aSEmilio G. Cota /*
772e11264aSEmilio G. Cota * We want to avoid false sharing of cache lines. Most systems have 64-byte
782e11264aSEmilio G. Cota * cache lines so we go with it for simplicity.
792e11264aSEmilio G. Cota *
802e11264aSEmilio G. Cota * Note that systems with smaller cache lines will be fine (the struct is
812e11264aSEmilio G. Cota * almost 64-bytes); systems with larger cache lines might suffer from
822e11264aSEmilio G. Cota * some false sharing.
832e11264aSEmilio G. Cota */
842e11264aSEmilio G. Cota #define QHT_BUCKET_ALIGN 64
852e11264aSEmilio G. Cota
862e11264aSEmilio G. Cota /* define these to keep sizeof(qht_bucket) within QHT_BUCKET_ALIGN */
872e11264aSEmilio G. Cota #if HOST_LONG_BITS == 32
882e11264aSEmilio G. Cota #define QHT_BUCKET_ENTRIES 6
892e11264aSEmilio G. Cota #else /* 64-bit */
902e11264aSEmilio G. Cota #define QHT_BUCKET_ENTRIES 4
912e11264aSEmilio G. Cota #endif
922e11264aSEmilio G. Cota
9369d55e9cSEmilio G. Cota enum qht_iter_type {
9469d55e9cSEmilio G. Cota QHT_ITER_VOID, /* do nothing; use retvoid */
9569d55e9cSEmilio G. Cota QHT_ITER_RM, /* remove element if retbool returns true */
9669d55e9cSEmilio G. Cota };
9769d55e9cSEmilio G. Cota
9869d55e9cSEmilio G. Cota struct qht_iter {
9969d55e9cSEmilio G. Cota union {
10069d55e9cSEmilio G. Cota qht_iter_func_t retvoid;
10169d55e9cSEmilio G. Cota qht_iter_bool_func_t retbool;
10269d55e9cSEmilio G. Cota } f;
10369d55e9cSEmilio G. Cota enum qht_iter_type type;
10469d55e9cSEmilio G. Cota };
10569d55e9cSEmilio G. Cota
1062e11264aSEmilio G. Cota /*
107fe9959a2SEmilio G. Cota * Do _not_ use qemu_mutex_[try]lock directly! Use these macros, otherwise
108fe9959a2SEmilio G. Cota * the profiler (QSP) will deadlock.
109fe9959a2SEmilio G. Cota */
qht_lock(struct qht * ht)110fe9959a2SEmilio G. Cota static inline void qht_lock(struct qht *ht)
111fe9959a2SEmilio G. Cota {
112fe9959a2SEmilio G. Cota if (ht->mode & QHT_MODE_RAW_MUTEXES) {
113fe9959a2SEmilio G. Cota qemu_mutex_lock__raw(&ht->lock);
114fe9959a2SEmilio G. Cota } else {
115fe9959a2SEmilio G. Cota qemu_mutex_lock(&ht->lock);
116fe9959a2SEmilio G. Cota }
117fe9959a2SEmilio G. Cota }
118fe9959a2SEmilio G. Cota
qht_trylock(struct qht * ht)119fe9959a2SEmilio G. Cota static inline int qht_trylock(struct qht *ht)
120fe9959a2SEmilio G. Cota {
121fe9959a2SEmilio G. Cota if (ht->mode & QHT_MODE_RAW_MUTEXES) {
122fe9959a2SEmilio G. Cota return qemu_mutex_trylock__raw(&(ht)->lock);
123fe9959a2SEmilio G. Cota }
124fe9959a2SEmilio G. Cota return qemu_mutex_trylock(&(ht)->lock);
125fe9959a2SEmilio G. Cota }
126fe9959a2SEmilio G. Cota
127fe9959a2SEmilio G. Cota /* this inline is not really necessary, but it helps keep code consistent */
qht_unlock(struct qht * ht)128fe9959a2SEmilio G. Cota static inline void qht_unlock(struct qht *ht)
129fe9959a2SEmilio G. Cota {
130fe9959a2SEmilio G. Cota qemu_mutex_unlock(&ht->lock);
131fe9959a2SEmilio G. Cota }
132fe9959a2SEmilio G. Cota
133fe9959a2SEmilio G. Cota /*
1342e11264aSEmilio G. Cota * Note: reading partially-updated pointers in @pointers could lead to
135d73415a3SStefan Hajnoczi * segfaults. We thus access them with qatomic_read/set; this guarantees
1362e11264aSEmilio G. Cota * that the compiler makes all those accesses atomic. We also need the
137d73415a3SStefan Hajnoczi * volatile-like behavior in qatomic_read, since otherwise the compiler
1382e11264aSEmilio G. Cota * might refetch the pointer.
139d73415a3SStefan Hajnoczi * qatomic_read's are of course not necessary when the bucket lock is held.
1402e11264aSEmilio G. Cota *
1412e11264aSEmilio G. Cota * If both ht->lock and b->lock are grabbed, ht->lock should always
1422e11264aSEmilio G. Cota * be grabbed first.
1432e11264aSEmilio G. Cota */
1442e11264aSEmilio G. Cota struct qht_bucket {
1452e11264aSEmilio G. Cota QemuSpin lock;
1462e11264aSEmilio G. Cota QemuSeqLock sequence;
1472e11264aSEmilio G. Cota uint32_t hashes[QHT_BUCKET_ENTRIES];
1482e11264aSEmilio G. Cota void *pointers[QHT_BUCKET_ENTRIES];
1492e11264aSEmilio G. Cota struct qht_bucket *next;
1502e11264aSEmilio G. Cota } QEMU_ALIGNED(QHT_BUCKET_ALIGN);
1512e11264aSEmilio G. Cota
1522e11264aSEmilio G. Cota QEMU_BUILD_BUG_ON(sizeof(struct qht_bucket) > QHT_BUCKET_ALIGN);
1532e11264aSEmilio G. Cota
154*68f7b2beSEmilio Cota /*
155*68f7b2beSEmilio Cota * Under TSAN, we use striped locks instead of one lock per bucket chain.
156*68f7b2beSEmilio Cota * This avoids crashing under TSAN, since TSAN aborts the program if more than
157*68f7b2beSEmilio Cota * 64 locks are held (this is a hardcoded limit in TSAN).
158*68f7b2beSEmilio Cota * When resizing a QHT we grab all the buckets' locks, which can easily
159*68f7b2beSEmilio Cota * go over TSAN's limit. By using striped locks, we avoid this problem.
160*68f7b2beSEmilio Cota *
161*68f7b2beSEmilio Cota * Note: this number must be a power of two for easy index computation.
162*68f7b2beSEmilio Cota */
163*68f7b2beSEmilio Cota #define QHT_TSAN_BUCKET_LOCKS_BITS 4
164*68f7b2beSEmilio Cota #define QHT_TSAN_BUCKET_LOCKS (1 << QHT_TSAN_BUCKET_LOCKS_BITS)
165*68f7b2beSEmilio Cota
166*68f7b2beSEmilio Cota struct qht_tsan_lock {
167*68f7b2beSEmilio Cota QemuSpin lock;
168*68f7b2beSEmilio Cota } QEMU_ALIGNED(QHT_BUCKET_ALIGN);
169*68f7b2beSEmilio Cota
1702e11264aSEmilio G. Cota /**
1712e11264aSEmilio G. Cota * struct qht_map - structure to track an array of buckets
1722e11264aSEmilio G. Cota * @rcu: used by RCU. Keep it as the top field in the struct to help valgrind
1732e11264aSEmilio G. Cota * find the whole struct.
1742e11264aSEmilio G. Cota * @buckets: array of head buckets. It is constant once the map is created.
1752e11264aSEmilio G. Cota * @n_buckets: number of head buckets. It is constant once the map is created.
1762e11264aSEmilio G. Cota * @n_added_buckets: number of added (i.e. "non-head") buckets
1772e11264aSEmilio G. Cota * @n_added_buckets_threshold: threshold to trigger an upward resize once the
1782e11264aSEmilio G. Cota * number of added buckets surpasses it.
179*68f7b2beSEmilio Cota * @tsan_bucket_locks: Array of striped locks to be used only under TSAN.
1802e11264aSEmilio G. Cota *
1812e11264aSEmilio G. Cota * Buckets are tracked in what we call a "map", i.e. this structure.
1822e11264aSEmilio G. Cota */
1832e11264aSEmilio G. Cota struct qht_map {
1842e11264aSEmilio G. Cota struct rcu_head rcu;
1852e11264aSEmilio G. Cota struct qht_bucket *buckets;
1862e11264aSEmilio G. Cota size_t n_buckets;
1872e11264aSEmilio G. Cota size_t n_added_buckets;
1882e11264aSEmilio G. Cota size_t n_added_buckets_threshold;
189*68f7b2beSEmilio Cota #ifdef CONFIG_TSAN
190*68f7b2beSEmilio Cota struct qht_tsan_lock tsan_bucket_locks[QHT_TSAN_BUCKET_LOCKS];
191*68f7b2beSEmilio Cota #endif
1922e11264aSEmilio G. Cota };
1932e11264aSEmilio G. Cota
1942e11264aSEmilio G. Cota /* trigger a resize when n_added_buckets > n_buckets / div */
1952e11264aSEmilio G. Cota #define QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV 8
1962e11264aSEmilio G. Cota
19776b553b3SEmilio G. Cota static void qht_do_resize_reset(struct qht *ht, struct qht_map *new,
19876b553b3SEmilio G. Cota bool reset);
1992e11264aSEmilio G. Cota static void qht_grow_maybe(struct qht *ht);
2002e11264aSEmilio G. Cota
2012e11264aSEmilio G. Cota #ifdef QHT_DEBUG
2022e11264aSEmilio G. Cota
2032e11264aSEmilio G. Cota #define qht_debug_assert(X) do { assert(X); } while (0)
2042e11264aSEmilio G. Cota
qht_bucket_debug__locked(struct qht_bucket * b)2052e11264aSEmilio G. Cota static void qht_bucket_debug__locked(struct qht_bucket *b)
2062e11264aSEmilio G. Cota {
2072e11264aSEmilio G. Cota bool seen_empty = false;
2082e11264aSEmilio G. Cota bool corrupt = false;
2092e11264aSEmilio G. Cota int i;
2102e11264aSEmilio G. Cota
2112e11264aSEmilio G. Cota do {
2122e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
2132e11264aSEmilio G. Cota if (b->pointers[i] == NULL) {
2142e11264aSEmilio G. Cota seen_empty = true;
2152e11264aSEmilio G. Cota continue;
2162e11264aSEmilio G. Cota }
2172e11264aSEmilio G. Cota if (seen_empty) {
2182e11264aSEmilio G. Cota fprintf(stderr, "%s: b: %p, pos: %i, hash: 0x%x, p: %p\n",
2192e11264aSEmilio G. Cota __func__, b, i, b->hashes[i], b->pointers[i]);
2202e11264aSEmilio G. Cota corrupt = true;
2212e11264aSEmilio G. Cota }
2222e11264aSEmilio G. Cota }
2232e11264aSEmilio G. Cota b = b->next;
2242e11264aSEmilio G. Cota } while (b);
2252e11264aSEmilio G. Cota qht_debug_assert(!corrupt);
2262e11264aSEmilio G. Cota }
2272e11264aSEmilio G. Cota
qht_map_debug__all_locked(struct qht_map * map)2282e11264aSEmilio G. Cota static void qht_map_debug__all_locked(struct qht_map *map)
2292e11264aSEmilio G. Cota {
2302e11264aSEmilio G. Cota int i;
2312e11264aSEmilio G. Cota
2322e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
2332e11264aSEmilio G. Cota qht_bucket_debug__locked(&map->buckets[i]);
2342e11264aSEmilio G. Cota }
2352e11264aSEmilio G. Cota }
2362e11264aSEmilio G. Cota #else
2372e11264aSEmilio G. Cota
2382e11264aSEmilio G. Cota #define qht_debug_assert(X) do { (void)(X); } while (0)
2392e11264aSEmilio G. Cota
qht_bucket_debug__locked(struct qht_bucket * b)2402e11264aSEmilio G. Cota static inline void qht_bucket_debug__locked(struct qht_bucket *b)
2412e11264aSEmilio G. Cota { }
2422e11264aSEmilio G. Cota
qht_map_debug__all_locked(struct qht_map * map)2432e11264aSEmilio G. Cota static inline void qht_map_debug__all_locked(struct qht_map *map)
2442e11264aSEmilio G. Cota { }
2452e11264aSEmilio G. Cota #endif /* QHT_DEBUG */
2462e11264aSEmilio G. Cota
qht_elems_to_buckets(size_t n_elems)2472e11264aSEmilio G. Cota static inline size_t qht_elems_to_buckets(size_t n_elems)
2482e11264aSEmilio G. Cota {
2492e11264aSEmilio G. Cota return pow2ceil(n_elems / QHT_BUCKET_ENTRIES);
2502e11264aSEmilio G. Cota }
2512e11264aSEmilio G. Cota
252*68f7b2beSEmilio Cota /*
253*68f7b2beSEmilio Cota * When using striped locks (i.e. under TSAN), we have to be careful not
254*68f7b2beSEmilio Cota * to operate on the same lock twice (e.g. when iterating through all buckets).
255*68f7b2beSEmilio Cota * We achieve this by operating only on each stripe's first matching lock.
256*68f7b2beSEmilio Cota */
qht_do_if_first_in_stripe(struct qht_map * map,struct qht_bucket * b,void (* func)(QemuSpin * spin))257*68f7b2beSEmilio Cota static inline void qht_do_if_first_in_stripe(struct qht_map *map,
258*68f7b2beSEmilio Cota struct qht_bucket *b,
259*68f7b2beSEmilio Cota void (*func)(QemuSpin *spin))
260*68f7b2beSEmilio Cota {
261*68f7b2beSEmilio Cota #ifdef CONFIG_TSAN
262*68f7b2beSEmilio Cota unsigned long bucket_idx = b - map->buckets;
263*68f7b2beSEmilio Cota bool is_first_in_stripe = (bucket_idx >> QHT_TSAN_BUCKET_LOCKS_BITS) == 0;
264*68f7b2beSEmilio Cota if (is_first_in_stripe) {
265*68f7b2beSEmilio Cota unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS - 1);
266*68f7b2beSEmilio Cota func(&map->tsan_bucket_locks[lock_idx].lock);
267*68f7b2beSEmilio Cota }
268*68f7b2beSEmilio Cota #else
269*68f7b2beSEmilio Cota func(&b->lock);
270*68f7b2beSEmilio Cota #endif
271*68f7b2beSEmilio Cota }
272*68f7b2beSEmilio Cota
qht_bucket_lock_do(struct qht_map * map,struct qht_bucket * b,void (* func)(QemuSpin * lock))273*68f7b2beSEmilio Cota static inline void qht_bucket_lock_do(struct qht_map *map,
274*68f7b2beSEmilio Cota struct qht_bucket *b,
275*68f7b2beSEmilio Cota void (*func)(QemuSpin *lock))
276*68f7b2beSEmilio Cota {
277*68f7b2beSEmilio Cota #ifdef CONFIG_TSAN
278*68f7b2beSEmilio Cota unsigned long bucket_idx = b - map->buckets;
279*68f7b2beSEmilio Cota unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS - 1);
280*68f7b2beSEmilio Cota func(&map->tsan_bucket_locks[lock_idx].lock);
281*68f7b2beSEmilio Cota #else
282*68f7b2beSEmilio Cota func(&b->lock);
283*68f7b2beSEmilio Cota #endif
284*68f7b2beSEmilio Cota }
285*68f7b2beSEmilio Cota
qht_bucket_lock(struct qht_map * map,struct qht_bucket * b)286*68f7b2beSEmilio Cota static inline void qht_bucket_lock(struct qht_map *map,
287*68f7b2beSEmilio Cota struct qht_bucket *b)
288*68f7b2beSEmilio Cota {
289*68f7b2beSEmilio Cota qht_bucket_lock_do(map, b, qemu_spin_lock);
290*68f7b2beSEmilio Cota }
291*68f7b2beSEmilio Cota
qht_bucket_unlock(struct qht_map * map,struct qht_bucket * b)292*68f7b2beSEmilio Cota static inline void qht_bucket_unlock(struct qht_map *map,
293*68f7b2beSEmilio Cota struct qht_bucket *b)
294*68f7b2beSEmilio Cota {
295*68f7b2beSEmilio Cota qht_bucket_lock_do(map, b, qemu_spin_unlock);
296*68f7b2beSEmilio Cota }
297*68f7b2beSEmilio Cota
qht_head_init(struct qht_map * map,struct qht_bucket * b)298*68f7b2beSEmilio Cota static inline void qht_head_init(struct qht_map *map, struct qht_bucket *b)
2992e11264aSEmilio G. Cota {
3002e11264aSEmilio G. Cota memset(b, 0, sizeof(*b));
301*68f7b2beSEmilio Cota qht_do_if_first_in_stripe(map, b, qemu_spin_init);
3022e11264aSEmilio G. Cota seqlock_init(&b->sequence);
3032e11264aSEmilio G. Cota }
3042e11264aSEmilio G. Cota
3052e11264aSEmilio G. Cota static inline
qht_map_to_bucket(const struct qht_map * map,uint32_t hash)306e6c58299SEmilio G. Cota struct qht_bucket *qht_map_to_bucket(const struct qht_map *map, uint32_t hash)
3072e11264aSEmilio G. Cota {
3082e11264aSEmilio G. Cota return &map->buckets[hash & (map->n_buckets - 1)];
3092e11264aSEmilio G. Cota }
3102e11264aSEmilio G. Cota
3112e11264aSEmilio G. Cota /* acquire all bucket locks from a map */
qht_map_lock_buckets(struct qht_map * map)3122e11264aSEmilio G. Cota static void qht_map_lock_buckets(struct qht_map *map)
3132e11264aSEmilio G. Cota {
3142e11264aSEmilio G. Cota size_t i;
3152e11264aSEmilio G. Cota
3162e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
3172e11264aSEmilio G. Cota struct qht_bucket *b = &map->buckets[i];
3182e11264aSEmilio G. Cota
319*68f7b2beSEmilio Cota qht_do_if_first_in_stripe(map, b, qemu_spin_lock);
3202e11264aSEmilio G. Cota }
3212e11264aSEmilio G. Cota }
3222e11264aSEmilio G. Cota
qht_map_unlock_buckets(struct qht_map * map)3232e11264aSEmilio G. Cota static void qht_map_unlock_buckets(struct qht_map *map)
3242e11264aSEmilio G. Cota {
3252e11264aSEmilio G. Cota size_t i;
3262e11264aSEmilio G. Cota
3272e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
3282e11264aSEmilio G. Cota struct qht_bucket *b = &map->buckets[i];
3292e11264aSEmilio G. Cota
330*68f7b2beSEmilio Cota qht_do_if_first_in_stripe(map, b, qemu_spin_unlock);
3312e11264aSEmilio G. Cota }
3322e11264aSEmilio G. Cota }
3332e11264aSEmilio G. Cota
3342e11264aSEmilio G. Cota /*
3352e11264aSEmilio G. Cota * Call with at least a bucket lock held.
3362e11264aSEmilio G. Cota * @map should be the value read before acquiring the lock (or locks).
3372e11264aSEmilio G. Cota */
qht_map_is_stale__locked(const struct qht * ht,const struct qht_map * map)3381911c8a3SEmilio G. Cota static inline bool qht_map_is_stale__locked(const struct qht *ht,
3391911c8a3SEmilio G. Cota const struct qht_map *map)
3402e11264aSEmilio G. Cota {
3412e11264aSEmilio G. Cota return map != ht->map;
3422e11264aSEmilio G. Cota }
3432e11264aSEmilio G. Cota
3442e11264aSEmilio G. Cota /*
3452e11264aSEmilio G. Cota * Grab all bucket locks, and set @pmap after making sure the map isn't stale.
3462e11264aSEmilio G. Cota *
3472e11264aSEmilio G. Cota * Pairs with qht_map_unlock_buckets(), hence the pass-by-reference.
3482e11264aSEmilio G. Cota *
3492e11264aSEmilio G. Cota * Note: callers cannot have ht->lock held.
3502e11264aSEmilio G. Cota */
3512e11264aSEmilio G. Cota static inline
qht_map_lock_buckets__no_stale(struct qht * ht,struct qht_map ** pmap)3522e11264aSEmilio G. Cota void qht_map_lock_buckets__no_stale(struct qht *ht, struct qht_map **pmap)
3532e11264aSEmilio G. Cota {
3542e11264aSEmilio G. Cota struct qht_map *map;
3552e11264aSEmilio G. Cota
356d73415a3SStefan Hajnoczi map = qatomic_rcu_read(&ht->map);
3572e11264aSEmilio G. Cota qht_map_lock_buckets(map);
3582e11264aSEmilio G. Cota if (likely(!qht_map_is_stale__locked(ht, map))) {
3592e11264aSEmilio G. Cota *pmap = map;
3602e11264aSEmilio G. Cota return;
3612e11264aSEmilio G. Cota }
3622e11264aSEmilio G. Cota qht_map_unlock_buckets(map);
3632e11264aSEmilio G. Cota
3642e11264aSEmilio G. Cota /* we raced with a resize; acquire ht->lock to see the updated ht->map */
365fe9959a2SEmilio G. Cota qht_lock(ht);
3662e11264aSEmilio G. Cota map = ht->map;
3672e11264aSEmilio G. Cota qht_map_lock_buckets(map);
368fe9959a2SEmilio G. Cota qht_unlock(ht);
3692e11264aSEmilio G. Cota *pmap = map;
3702e11264aSEmilio G. Cota return;
3712e11264aSEmilio G. Cota }
3722e11264aSEmilio G. Cota
3732e11264aSEmilio G. Cota /*
3742e11264aSEmilio G. Cota * Get a head bucket and lock it, making sure its parent map is not stale.
3752e11264aSEmilio G. Cota * @pmap is filled with a pointer to the bucket's parent map.
3762e11264aSEmilio G. Cota *
377*68f7b2beSEmilio Cota * Unlock with qht_bucket_unlock.
3782e11264aSEmilio G. Cota *
3792e11264aSEmilio G. Cota * Note: callers cannot have ht->lock held.
3802e11264aSEmilio G. Cota */
3812e11264aSEmilio G. Cota static inline
qht_bucket_lock__no_stale(struct qht * ht,uint32_t hash,struct qht_map ** pmap)3822e11264aSEmilio G. Cota struct qht_bucket *qht_bucket_lock__no_stale(struct qht *ht, uint32_t hash,
3832e11264aSEmilio G. Cota struct qht_map **pmap)
3842e11264aSEmilio G. Cota {
3852e11264aSEmilio G. Cota struct qht_bucket *b;
3862e11264aSEmilio G. Cota struct qht_map *map;
3872e11264aSEmilio G. Cota
388d73415a3SStefan Hajnoczi map = qatomic_rcu_read(&ht->map);
3892e11264aSEmilio G. Cota b = qht_map_to_bucket(map, hash);
3902e11264aSEmilio G. Cota
391*68f7b2beSEmilio Cota qht_bucket_lock(map, b);
3922e11264aSEmilio G. Cota if (likely(!qht_map_is_stale__locked(ht, map))) {
3932e11264aSEmilio G. Cota *pmap = map;
3942e11264aSEmilio G. Cota return b;
3952e11264aSEmilio G. Cota }
396*68f7b2beSEmilio Cota qht_bucket_unlock(map, b);
3972e11264aSEmilio G. Cota
3982e11264aSEmilio G. Cota /* we raced with a resize; acquire ht->lock to see the updated ht->map */
399fe9959a2SEmilio G. Cota qht_lock(ht);
4002e11264aSEmilio G. Cota map = ht->map;
4012e11264aSEmilio G. Cota b = qht_map_to_bucket(map, hash);
402*68f7b2beSEmilio Cota qht_bucket_lock(map, b);
403fe9959a2SEmilio G. Cota qht_unlock(ht);
4042e11264aSEmilio G. Cota *pmap = map;
4052e11264aSEmilio G. Cota return b;
4062e11264aSEmilio G. Cota }
4072e11264aSEmilio G. Cota
qht_map_needs_resize(const struct qht_map * map)4081911c8a3SEmilio G. Cota static inline bool qht_map_needs_resize(const struct qht_map *map)
4092e11264aSEmilio G. Cota {
410d73415a3SStefan Hajnoczi return qatomic_read(&map->n_added_buckets) >
411d73415a3SStefan Hajnoczi map->n_added_buckets_threshold;
4122e11264aSEmilio G. Cota }
4132e11264aSEmilio G. Cota
qht_chain_destroy(struct qht_map * map,struct qht_bucket * head)414*68f7b2beSEmilio Cota static inline void qht_chain_destroy(struct qht_map *map,
415*68f7b2beSEmilio Cota struct qht_bucket *head)
4162e11264aSEmilio G. Cota {
4172e11264aSEmilio G. Cota struct qht_bucket *curr = head->next;
4182e11264aSEmilio G. Cota struct qht_bucket *prev;
4192e11264aSEmilio G. Cota
420*68f7b2beSEmilio Cota qht_do_if_first_in_stripe(map, head, qemu_spin_destroy);
4212e11264aSEmilio G. Cota while (curr) {
4222e11264aSEmilio G. Cota prev = curr;
4232e11264aSEmilio G. Cota curr = curr->next;
4242e11264aSEmilio G. Cota qemu_vfree(prev);
4252e11264aSEmilio G. Cota }
4262e11264aSEmilio G. Cota }
4272e11264aSEmilio G. Cota
4282e11264aSEmilio G. Cota /* pass only an orphan map */
qht_map_destroy(struct qht_map * map)4292e11264aSEmilio G. Cota static void qht_map_destroy(struct qht_map *map)
4302e11264aSEmilio G. Cota {
4312e11264aSEmilio G. Cota size_t i;
4322e11264aSEmilio G. Cota
4332e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
434*68f7b2beSEmilio Cota qht_chain_destroy(map, &map->buckets[i]);
4352e11264aSEmilio G. Cota }
4362e11264aSEmilio G. Cota qemu_vfree(map->buckets);
4372e11264aSEmilio G. Cota g_free(map);
4382e11264aSEmilio G. Cota }
4392e11264aSEmilio G. Cota
qht_map_create(size_t n_buckets)4402e11264aSEmilio G. Cota static struct qht_map *qht_map_create(size_t n_buckets)
4412e11264aSEmilio G. Cota {
4422e11264aSEmilio G. Cota struct qht_map *map;
4432e11264aSEmilio G. Cota size_t i;
4442e11264aSEmilio G. Cota
4452e11264aSEmilio G. Cota map = g_malloc(sizeof(*map));
4462e11264aSEmilio G. Cota map->n_buckets = n_buckets;
4472e11264aSEmilio G. Cota
4482e11264aSEmilio G. Cota map->n_added_buckets = 0;
4492e11264aSEmilio G. Cota map->n_added_buckets_threshold = n_buckets /
4502e11264aSEmilio G. Cota QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV;
4512e11264aSEmilio G. Cota
4522e11264aSEmilio G. Cota /* let tiny hash tables to at least add one non-head bucket */
4532e11264aSEmilio G. Cota if (unlikely(map->n_added_buckets_threshold == 0)) {
4542e11264aSEmilio G. Cota map->n_added_buckets_threshold = 1;
4552e11264aSEmilio G. Cota }
4562e11264aSEmilio G. Cota
4572e11264aSEmilio G. Cota map->buckets = qemu_memalign(QHT_BUCKET_ALIGN,
4582e11264aSEmilio G. Cota sizeof(*map->buckets) * n_buckets);
4592e11264aSEmilio G. Cota for (i = 0; i < n_buckets; i++) {
460*68f7b2beSEmilio Cota qht_head_init(map, &map->buckets[i]);
4612e11264aSEmilio G. Cota }
4622e11264aSEmilio G. Cota return map;
4632e11264aSEmilio G. Cota }
4642e11264aSEmilio G. Cota
qht_init(struct qht * ht,qht_cmp_func_t cmp,size_t n_elems,unsigned int mode)46561b8cef1SEmilio G. Cota void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems,
46661b8cef1SEmilio G. Cota unsigned int mode)
4672e11264aSEmilio G. Cota {
4682e11264aSEmilio G. Cota struct qht_map *map;
4692e11264aSEmilio G. Cota size_t n_buckets = qht_elems_to_buckets(n_elems);
4702e11264aSEmilio G. Cota
47161b8cef1SEmilio G. Cota g_assert(cmp);
47261b8cef1SEmilio G. Cota ht->cmp = cmp;
4732e11264aSEmilio G. Cota ht->mode = mode;
4742e11264aSEmilio G. Cota qemu_mutex_init(&ht->lock);
4752e11264aSEmilio G. Cota map = qht_map_create(n_buckets);
476d73415a3SStefan Hajnoczi qatomic_rcu_set(&ht->map, map);
4772e11264aSEmilio G. Cota }
4782e11264aSEmilio G. Cota
4792e11264aSEmilio G. Cota /* call only when there are no readers/writers left */
qht_destroy(struct qht * ht)4802e11264aSEmilio G. Cota void qht_destroy(struct qht *ht)
4812e11264aSEmilio G. Cota {
4822e11264aSEmilio G. Cota qht_map_destroy(ht->map);
4832e11264aSEmilio G. Cota memset(ht, 0, sizeof(*ht));
4842e11264aSEmilio G. Cota }
4852e11264aSEmilio G. Cota
qht_bucket_reset__locked(struct qht_bucket * head)4862e11264aSEmilio G. Cota static void qht_bucket_reset__locked(struct qht_bucket *head)
4872e11264aSEmilio G. Cota {
4882e11264aSEmilio G. Cota struct qht_bucket *b = head;
4892e11264aSEmilio G. Cota int i;
4902e11264aSEmilio G. Cota
4912e11264aSEmilio G. Cota seqlock_write_begin(&head->sequence);
4922e11264aSEmilio G. Cota do {
4932e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
4942e11264aSEmilio G. Cota if (b->pointers[i] == NULL) {
4952e11264aSEmilio G. Cota goto done;
4962e11264aSEmilio G. Cota }
497d73415a3SStefan Hajnoczi qatomic_set(&b->hashes[i], 0);
498d73415a3SStefan Hajnoczi qatomic_set(&b->pointers[i], NULL);
4992e11264aSEmilio G. Cota }
5002e11264aSEmilio G. Cota b = b->next;
5012e11264aSEmilio G. Cota } while (b);
5022e11264aSEmilio G. Cota done:
5032e11264aSEmilio G. Cota seqlock_write_end(&head->sequence);
5042e11264aSEmilio G. Cota }
5052e11264aSEmilio G. Cota
5062e11264aSEmilio G. Cota /* call with all bucket locks held */
qht_map_reset__all_locked(struct qht_map * map)5072e11264aSEmilio G. Cota static void qht_map_reset__all_locked(struct qht_map *map)
5082e11264aSEmilio G. Cota {
5092e11264aSEmilio G. Cota size_t i;
5102e11264aSEmilio G. Cota
5112e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
5122e11264aSEmilio G. Cota qht_bucket_reset__locked(&map->buckets[i]);
5132e11264aSEmilio G. Cota }
5142e11264aSEmilio G. Cota qht_map_debug__all_locked(map);
5152e11264aSEmilio G. Cota }
5162e11264aSEmilio G. Cota
qht_reset(struct qht * ht)5172e11264aSEmilio G. Cota void qht_reset(struct qht *ht)
5182e11264aSEmilio G. Cota {
5192e11264aSEmilio G. Cota struct qht_map *map;
5202e11264aSEmilio G. Cota
5212e11264aSEmilio G. Cota qht_map_lock_buckets__no_stale(ht, &map);
5222e11264aSEmilio G. Cota qht_map_reset__all_locked(map);
5232e11264aSEmilio G. Cota qht_map_unlock_buckets(map);
5242e11264aSEmilio G. Cota }
5252e11264aSEmilio G. Cota
qht_do_resize(struct qht * ht,struct qht_map * new)52676b553b3SEmilio G. Cota static inline void qht_do_resize(struct qht *ht, struct qht_map *new)
52776b553b3SEmilio G. Cota {
52876b553b3SEmilio G. Cota qht_do_resize_reset(ht, new, false);
52976b553b3SEmilio G. Cota }
53076b553b3SEmilio G. Cota
qht_do_resize_and_reset(struct qht * ht,struct qht_map * new)53176b553b3SEmilio G. Cota static inline void qht_do_resize_and_reset(struct qht *ht, struct qht_map *new)
53276b553b3SEmilio G. Cota {
53376b553b3SEmilio G. Cota qht_do_resize_reset(ht, new, true);
53476b553b3SEmilio G. Cota }
53576b553b3SEmilio G. Cota
qht_reset_size(struct qht * ht,size_t n_elems)5362e11264aSEmilio G. Cota bool qht_reset_size(struct qht *ht, size_t n_elems)
5372e11264aSEmilio G. Cota {
538f555a9d0SEmilio G. Cota struct qht_map *new = NULL;
5392e11264aSEmilio G. Cota struct qht_map *map;
5402e11264aSEmilio G. Cota size_t n_buckets;
5412e11264aSEmilio G. Cota
5422e11264aSEmilio G. Cota n_buckets = qht_elems_to_buckets(n_elems);
5432e11264aSEmilio G. Cota
544fe9959a2SEmilio G. Cota qht_lock(ht);
5452e11264aSEmilio G. Cota map = ht->map;
5462e11264aSEmilio G. Cota if (n_buckets != map->n_buckets) {
5472e11264aSEmilio G. Cota new = qht_map_create(n_buckets);
5482e11264aSEmilio G. Cota }
54976b553b3SEmilio G. Cota qht_do_resize_and_reset(ht, new);
550fe9959a2SEmilio G. Cota qht_unlock(ht);
5512e11264aSEmilio G. Cota
552f555a9d0SEmilio G. Cota return !!new;
5532e11264aSEmilio G. Cota }
5542e11264aSEmilio G. Cota
5552e11264aSEmilio G. Cota static inline
qht_do_lookup(const struct qht_bucket * head,qht_lookup_func_t func,const void * userp,uint32_t hash)556e6c58299SEmilio G. Cota void *qht_do_lookup(const struct qht_bucket *head, qht_lookup_func_t func,
5572e11264aSEmilio G. Cota const void *userp, uint32_t hash)
5582e11264aSEmilio G. Cota {
559e6c58299SEmilio G. Cota const struct qht_bucket *b = head;
5602e11264aSEmilio G. Cota int i;
5612e11264aSEmilio G. Cota
5622e11264aSEmilio G. Cota do {
5632e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
564d73415a3SStefan Hajnoczi if (qatomic_read(&b->hashes[i]) == hash) {
56534506b30SPaolo Bonzini /* The pointer is dereferenced before seqlock_read_retry,
56634506b30SPaolo Bonzini * so (unlike qht_insert__locked) we need to use
567d73415a3SStefan Hajnoczi * qatomic_rcu_read here.
56834506b30SPaolo Bonzini */
569d73415a3SStefan Hajnoczi void *p = qatomic_rcu_read(&b->pointers[i]);
5702e11264aSEmilio G. Cota
5712e11264aSEmilio G. Cota if (likely(p) && likely(func(p, userp))) {
5722e11264aSEmilio G. Cota return p;
5732e11264aSEmilio G. Cota }
5742e11264aSEmilio G. Cota }
5752e11264aSEmilio G. Cota }
576d73415a3SStefan Hajnoczi b = qatomic_rcu_read(&b->next);
5772e11264aSEmilio G. Cota } while (b);
5782e11264aSEmilio G. Cota
5792e11264aSEmilio G. Cota return NULL;
5802e11264aSEmilio G. Cota }
5812e11264aSEmilio G. Cota
5822e11264aSEmilio G. Cota static __attribute__((noinline))
qht_lookup__slowpath(const struct qht_bucket * b,qht_lookup_func_t func,const void * userp,uint32_t hash)583e6c58299SEmilio G. Cota void *qht_lookup__slowpath(const struct qht_bucket *b, qht_lookup_func_t func,
5842e11264aSEmilio G. Cota const void *userp, uint32_t hash)
5852e11264aSEmilio G. Cota {
5862e11264aSEmilio G. Cota unsigned int version;
5872e11264aSEmilio G. Cota void *ret;
5882e11264aSEmilio G. Cota
5892e11264aSEmilio G. Cota do {
5902e11264aSEmilio G. Cota version = seqlock_read_begin(&b->sequence);
5912e11264aSEmilio G. Cota ret = qht_do_lookup(b, func, userp, hash);
5922e11264aSEmilio G. Cota } while (seqlock_read_retry(&b->sequence, version));
5932e11264aSEmilio G. Cota return ret;
5942e11264aSEmilio G. Cota }
5952e11264aSEmilio G. Cota
qht_lookup_custom(const struct qht * ht,const void * userp,uint32_t hash,qht_lookup_func_t func)596e6c58299SEmilio G. Cota void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash,
59761b8cef1SEmilio G. Cota qht_lookup_func_t func)
5982e11264aSEmilio G. Cota {
599e6c58299SEmilio G. Cota const struct qht_bucket *b;
600e6c58299SEmilio G. Cota const struct qht_map *map;
6012e11264aSEmilio G. Cota unsigned int version;
6022e11264aSEmilio G. Cota void *ret;
6032e11264aSEmilio G. Cota
604d73415a3SStefan Hajnoczi map = qatomic_rcu_read(&ht->map);
6052e11264aSEmilio G. Cota b = qht_map_to_bucket(map, hash);
6062e11264aSEmilio G. Cota
6072e11264aSEmilio G. Cota version = seqlock_read_begin(&b->sequence);
6082e11264aSEmilio G. Cota ret = qht_do_lookup(b, func, userp, hash);
6092e11264aSEmilio G. Cota if (likely(!seqlock_read_retry(&b->sequence, version))) {
6102e11264aSEmilio G. Cota return ret;
6112e11264aSEmilio G. Cota }
6122e11264aSEmilio G. Cota /*
6132e11264aSEmilio G. Cota * Removing the do/while from the fastpath gives a 4% perf. increase when
6142e11264aSEmilio G. Cota * running a 100%-lookup microbenchmark.
6152e11264aSEmilio G. Cota */
6162e11264aSEmilio G. Cota return qht_lookup__slowpath(b, func, userp, hash);
6172e11264aSEmilio G. Cota }
6182e11264aSEmilio G. Cota
qht_lookup(const struct qht * ht,const void * userp,uint32_t hash)619e6c58299SEmilio G. Cota void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash)
62061b8cef1SEmilio G. Cota {
62161b8cef1SEmilio G. Cota return qht_lookup_custom(ht, userp, hash, ht->cmp);
62261b8cef1SEmilio G. Cota }
62361b8cef1SEmilio G. Cota
6241911c8a3SEmilio G. Cota /*
6251911c8a3SEmilio G. Cota * call with head->lock held
6261911c8a3SEmilio G. Cota * @ht is const since it is only used for ht->cmp()
6271911c8a3SEmilio G. Cota */
qht_insert__locked(const struct qht * ht,struct qht_map * map,struct qht_bucket * head,void * p,uint32_t hash,bool * needs_resize)6281911c8a3SEmilio G. Cota static void *qht_insert__locked(const struct qht *ht, struct qht_map *map,
6292e11264aSEmilio G. Cota struct qht_bucket *head, void *p, uint32_t hash,
6302e11264aSEmilio G. Cota bool *needs_resize)
6312e11264aSEmilio G. Cota {
6322e11264aSEmilio G. Cota struct qht_bucket *b = head;
6332e11264aSEmilio G. Cota struct qht_bucket *prev = NULL;
6342e11264aSEmilio G. Cota struct qht_bucket *new = NULL;
6352e11264aSEmilio G. Cota int i;
6362e11264aSEmilio G. Cota
6372e11264aSEmilio G. Cota do {
6382e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
6392e11264aSEmilio G. Cota if (b->pointers[i]) {
64032359d52SEmilio G. Cota if (unlikely(b->hashes[i] == hash &&
64132359d52SEmilio G. Cota ht->cmp(b->pointers[i], p))) {
64232359d52SEmilio G. Cota return b->pointers[i];
6432e11264aSEmilio G. Cota }
6442e11264aSEmilio G. Cota } else {
6452e11264aSEmilio G. Cota goto found;
6462e11264aSEmilio G. Cota }
6472e11264aSEmilio G. Cota }
6482e11264aSEmilio G. Cota prev = b;
6492e11264aSEmilio G. Cota b = b->next;
6502e11264aSEmilio G. Cota } while (b);
6512e11264aSEmilio G. Cota
6522e11264aSEmilio G. Cota b = qemu_memalign(QHT_BUCKET_ALIGN, sizeof(*b));
6532e11264aSEmilio G. Cota memset(b, 0, sizeof(*b));
6542e11264aSEmilio G. Cota new = b;
6552e11264aSEmilio G. Cota i = 0;
656d73415a3SStefan Hajnoczi qatomic_inc(&map->n_added_buckets);
6572e11264aSEmilio G. Cota if (unlikely(qht_map_needs_resize(map)) && needs_resize) {
6582e11264aSEmilio G. Cota *needs_resize = true;
6592e11264aSEmilio G. Cota }
6602e11264aSEmilio G. Cota
6612e11264aSEmilio G. Cota found:
6622e11264aSEmilio G. Cota /* found an empty key: acquire the seqlock and write */
6632e11264aSEmilio G. Cota seqlock_write_begin(&head->sequence);
6642e11264aSEmilio G. Cota if (new) {
665d73415a3SStefan Hajnoczi qatomic_rcu_set(&prev->next, b);
6662e11264aSEmilio G. Cota }
66734506b30SPaolo Bonzini /* smp_wmb() implicit in seqlock_write_begin. */
668d73415a3SStefan Hajnoczi qatomic_set(&b->hashes[i], hash);
669d73415a3SStefan Hajnoczi qatomic_set(&b->pointers[i], p);
6702e11264aSEmilio G. Cota seqlock_write_end(&head->sequence);
67132359d52SEmilio G. Cota return NULL;
6722e11264aSEmilio G. Cota }
6732e11264aSEmilio G. Cota
qht_grow_maybe(struct qht * ht)6742e11264aSEmilio G. Cota static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht)
6752e11264aSEmilio G. Cota {
6762e11264aSEmilio G. Cota struct qht_map *map;
6772e11264aSEmilio G. Cota
6782e11264aSEmilio G. Cota /*
6792e11264aSEmilio G. Cota * If the lock is taken it probably means there's an ongoing resize,
6802e11264aSEmilio G. Cota * so bail out.
6812e11264aSEmilio G. Cota */
682fe9959a2SEmilio G. Cota if (qht_trylock(ht)) {
6832e11264aSEmilio G. Cota return;
6842e11264aSEmilio G. Cota }
6852e11264aSEmilio G. Cota map = ht->map;
6862e11264aSEmilio G. Cota /* another thread might have just performed the resize we were after */
6872e11264aSEmilio G. Cota if (qht_map_needs_resize(map)) {
6882e11264aSEmilio G. Cota struct qht_map *new = qht_map_create(map->n_buckets * 2);
6892e11264aSEmilio G. Cota
6902e11264aSEmilio G. Cota qht_do_resize(ht, new);
6912e11264aSEmilio G. Cota }
692fe9959a2SEmilio G. Cota qht_unlock(ht);
6932e11264aSEmilio G. Cota }
6942e11264aSEmilio G. Cota
qht_insert(struct qht * ht,void * p,uint32_t hash,void ** existing)69532359d52SEmilio G. Cota bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing)
6962e11264aSEmilio G. Cota {
6972e11264aSEmilio G. Cota struct qht_bucket *b;
6982e11264aSEmilio G. Cota struct qht_map *map;
6992e11264aSEmilio G. Cota bool needs_resize = false;
70032359d52SEmilio G. Cota void *prev;
7012e11264aSEmilio G. Cota
7022e11264aSEmilio G. Cota /* NULL pointers are not supported */
7032e11264aSEmilio G. Cota qht_debug_assert(p);
7042e11264aSEmilio G. Cota
7052e11264aSEmilio G. Cota b = qht_bucket_lock__no_stale(ht, hash, &map);
70632359d52SEmilio G. Cota prev = qht_insert__locked(ht, map, b, p, hash, &needs_resize);
7072e11264aSEmilio G. Cota qht_bucket_debug__locked(b);
708*68f7b2beSEmilio Cota qht_bucket_unlock(map, b);
7092e11264aSEmilio G. Cota
7102e11264aSEmilio G. Cota if (unlikely(needs_resize) && ht->mode & QHT_MODE_AUTO_RESIZE) {
7112e11264aSEmilio G. Cota qht_grow_maybe(ht);
7122e11264aSEmilio G. Cota }
71332359d52SEmilio G. Cota if (likely(prev == NULL)) {
71432359d52SEmilio G. Cota return true;
71532359d52SEmilio G. Cota }
71632359d52SEmilio G. Cota if (existing) {
71732359d52SEmilio G. Cota *existing = prev;
71832359d52SEmilio G. Cota }
71932359d52SEmilio G. Cota return false;
7202e11264aSEmilio G. Cota }
7212e11264aSEmilio G. Cota
qht_entry_is_last(const struct qht_bucket * b,int pos)7221911c8a3SEmilio G. Cota static inline bool qht_entry_is_last(const struct qht_bucket *b, int pos)
7232e11264aSEmilio G. Cota {
7242e11264aSEmilio G. Cota if (pos == QHT_BUCKET_ENTRIES - 1) {
7252e11264aSEmilio G. Cota if (b->next == NULL) {
7262e11264aSEmilio G. Cota return true;
7272e11264aSEmilio G. Cota }
7282e11264aSEmilio G. Cota return b->next->pointers[0] == NULL;
7292e11264aSEmilio G. Cota }
7302e11264aSEmilio G. Cota return b->pointers[pos + 1] == NULL;
7312e11264aSEmilio G. Cota }
7322e11264aSEmilio G. Cota
7332e11264aSEmilio G. Cota static void
qht_entry_move(struct qht_bucket * to,int i,struct qht_bucket * from,int j)7342e11264aSEmilio G. Cota qht_entry_move(struct qht_bucket *to, int i, struct qht_bucket *from, int j)
7352e11264aSEmilio G. Cota {
7362e11264aSEmilio G. Cota qht_debug_assert(!(to == from && i == j));
7372e11264aSEmilio G. Cota qht_debug_assert(to->pointers[i]);
7382e11264aSEmilio G. Cota qht_debug_assert(from->pointers[j]);
7392e11264aSEmilio G. Cota
740d73415a3SStefan Hajnoczi qatomic_set(&to->hashes[i], from->hashes[j]);
741d73415a3SStefan Hajnoczi qatomic_set(&to->pointers[i], from->pointers[j]);
7422e11264aSEmilio G. Cota
743d73415a3SStefan Hajnoczi qatomic_set(&from->hashes[j], 0);
744d73415a3SStefan Hajnoczi qatomic_set(&from->pointers[j], NULL);
7452e11264aSEmilio G. Cota }
7462e11264aSEmilio G. Cota
7472e11264aSEmilio G. Cota /*
7489650ad3eSEmilio G. Cota * Find the last valid entry in @orig, and swap it with @orig[pos], which has
7492e11264aSEmilio G. Cota * just been invalidated.
7502e11264aSEmilio G. Cota */
qht_bucket_remove_entry(struct qht_bucket * orig,int pos)7512e11264aSEmilio G. Cota static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)
7522e11264aSEmilio G. Cota {
7532e11264aSEmilio G. Cota struct qht_bucket *b = orig;
7542e11264aSEmilio G. Cota struct qht_bucket *prev = NULL;
7552e11264aSEmilio G. Cota int i;
7562e11264aSEmilio G. Cota
7572e11264aSEmilio G. Cota if (qht_entry_is_last(orig, pos)) {
758def48dddSEmilio Cota qatomic_set(&orig->hashes[pos], 0);
759d73415a3SStefan Hajnoczi qatomic_set(&orig->pointers[pos], NULL);
7602e11264aSEmilio G. Cota return;
7612e11264aSEmilio G. Cota }
7622e11264aSEmilio G. Cota do {
7632e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
7642e11264aSEmilio G. Cota if (b->pointers[i]) {
7652e11264aSEmilio G. Cota continue;
7662e11264aSEmilio G. Cota }
7672e11264aSEmilio G. Cota if (i > 0) {
7682e11264aSEmilio G. Cota return qht_entry_move(orig, pos, b, i - 1);
7692e11264aSEmilio G. Cota }
7702e11264aSEmilio G. Cota qht_debug_assert(prev);
7712e11264aSEmilio G. Cota return qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
7722e11264aSEmilio G. Cota }
7732e11264aSEmilio G. Cota prev = b;
7742e11264aSEmilio G. Cota b = b->next;
7752e11264aSEmilio G. Cota } while (b);
7762e11264aSEmilio G. Cota /* no free entries other than orig[pos], so swap it with the last one */
7772e11264aSEmilio G. Cota qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
7782e11264aSEmilio G. Cota }
7792e11264aSEmilio G. Cota
7802e11264aSEmilio G. Cota /* call with b->lock held */
7812e11264aSEmilio G. Cota static inline
qht_remove__locked(struct qht_bucket * head,const void * p,uint32_t hash)782e2f07efaSEmilio G. Cota bool qht_remove__locked(struct qht_bucket *head, const void *p, uint32_t hash)
7832e11264aSEmilio G. Cota {
7842e11264aSEmilio G. Cota struct qht_bucket *b = head;
7852e11264aSEmilio G. Cota int i;
7862e11264aSEmilio G. Cota
7872e11264aSEmilio G. Cota do {
7882e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
7892e11264aSEmilio G. Cota void *q = b->pointers[i];
7902e11264aSEmilio G. Cota
7912e11264aSEmilio G. Cota if (unlikely(q == NULL)) {
7922e11264aSEmilio G. Cota return false;
7932e11264aSEmilio G. Cota }
7942e11264aSEmilio G. Cota if (q == p) {
7952e11264aSEmilio G. Cota qht_debug_assert(b->hashes[i] == hash);
7962e11264aSEmilio G. Cota seqlock_write_begin(&head->sequence);
7972e11264aSEmilio G. Cota qht_bucket_remove_entry(b, i);
7982e11264aSEmilio G. Cota seqlock_write_end(&head->sequence);
7992e11264aSEmilio G. Cota return true;
8002e11264aSEmilio G. Cota }
8012e11264aSEmilio G. Cota }
8022e11264aSEmilio G. Cota b = b->next;
8032e11264aSEmilio G. Cota } while (b);
8042e11264aSEmilio G. Cota return false;
8052e11264aSEmilio G. Cota }
8062e11264aSEmilio G. Cota
qht_remove(struct qht * ht,const void * p,uint32_t hash)8072e11264aSEmilio G. Cota bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
8082e11264aSEmilio G. Cota {
8092e11264aSEmilio G. Cota struct qht_bucket *b;
8102e11264aSEmilio G. Cota struct qht_map *map;
8112e11264aSEmilio G. Cota bool ret;
8122e11264aSEmilio G. Cota
8132e11264aSEmilio G. Cota /* NULL pointers are not supported */
8142e11264aSEmilio G. Cota qht_debug_assert(p);
8152e11264aSEmilio G. Cota
8162e11264aSEmilio G. Cota b = qht_bucket_lock__no_stale(ht, hash, &map);
817e2f07efaSEmilio G. Cota ret = qht_remove__locked(b, p, hash);
8182e11264aSEmilio G. Cota qht_bucket_debug__locked(b);
819*68f7b2beSEmilio Cota qht_bucket_unlock(map, b);
8202e11264aSEmilio G. Cota return ret;
8212e11264aSEmilio G. Cota }
8222e11264aSEmilio G. Cota
qht_bucket_iter(struct qht_bucket * head,const struct qht_iter * iter,void * userp)82378255ba2SEmilio G. Cota static inline void qht_bucket_iter(struct qht_bucket *head,
82469d55e9cSEmilio G. Cota const struct qht_iter *iter, void *userp)
8252e11264aSEmilio G. Cota {
82669d55e9cSEmilio G. Cota struct qht_bucket *b = head;
8272e11264aSEmilio G. Cota int i;
8282e11264aSEmilio G. Cota
8292e11264aSEmilio G. Cota do {
8302e11264aSEmilio G. Cota for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
8312e11264aSEmilio G. Cota if (b->pointers[i] == NULL) {
8322e11264aSEmilio G. Cota return;
8332e11264aSEmilio G. Cota }
83469d55e9cSEmilio G. Cota switch (iter->type) {
83569d55e9cSEmilio G. Cota case QHT_ITER_VOID:
83678255ba2SEmilio G. Cota iter->f.retvoid(b->pointers[i], b->hashes[i], userp);
83769d55e9cSEmilio G. Cota break;
83869d55e9cSEmilio G. Cota case QHT_ITER_RM:
83978255ba2SEmilio G. Cota if (iter->f.retbool(b->pointers[i], b->hashes[i], userp)) {
84069d55e9cSEmilio G. Cota /* replace i with the last valid element in the bucket */
84169d55e9cSEmilio G. Cota seqlock_write_begin(&head->sequence);
84269d55e9cSEmilio G. Cota qht_bucket_remove_entry(b, i);
84369d55e9cSEmilio G. Cota seqlock_write_end(&head->sequence);
84469d55e9cSEmilio G. Cota qht_bucket_debug__locked(b);
84569d55e9cSEmilio G. Cota /* reevaluate i, since it just got replaced */
84669d55e9cSEmilio G. Cota i--;
84769d55e9cSEmilio G. Cota continue;
84869d55e9cSEmilio G. Cota }
84969d55e9cSEmilio G. Cota break;
85069d55e9cSEmilio G. Cota default:
85169d55e9cSEmilio G. Cota g_assert_not_reached();
85269d55e9cSEmilio G. Cota }
8532e11264aSEmilio G. Cota }
8542e11264aSEmilio G. Cota b = b->next;
8552e11264aSEmilio G. Cota } while (b);
8562e11264aSEmilio G. Cota }
8572e11264aSEmilio G. Cota
8582e11264aSEmilio G. Cota /* call with all of the map's locks held */
qht_map_iter__all_locked(struct qht_map * map,const struct qht_iter * iter,void * userp)85978255ba2SEmilio G. Cota static inline void qht_map_iter__all_locked(struct qht_map *map,
86069d55e9cSEmilio G. Cota const struct qht_iter *iter,
86169d55e9cSEmilio G. Cota void *userp)
8622e11264aSEmilio G. Cota {
8632e11264aSEmilio G. Cota size_t i;
8642e11264aSEmilio G. Cota
8652e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
86678255ba2SEmilio G. Cota qht_bucket_iter(&map->buckets[i], iter, userp);
8672e11264aSEmilio G. Cota }
8682e11264aSEmilio G. Cota }
8692e11264aSEmilio G. Cota
87069d55e9cSEmilio G. Cota static inline void
do_qht_iter(struct qht * ht,const struct qht_iter * iter,void * userp)87169d55e9cSEmilio G. Cota do_qht_iter(struct qht *ht, const struct qht_iter *iter, void *userp)
8722e11264aSEmilio G. Cota {
8732e11264aSEmilio G. Cota struct qht_map *map;
8742e11264aSEmilio G. Cota
875d73415a3SStefan Hajnoczi map = qatomic_rcu_read(&ht->map);
8762e11264aSEmilio G. Cota qht_map_lock_buckets(map);
87778255ba2SEmilio G. Cota qht_map_iter__all_locked(map, iter, userp);
8782e11264aSEmilio G. Cota qht_map_unlock_buckets(map);
8792e11264aSEmilio G. Cota }
8802e11264aSEmilio G. Cota
qht_iter(struct qht * ht,qht_iter_func_t func,void * userp)88169d55e9cSEmilio G. Cota void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
88269d55e9cSEmilio G. Cota {
88369d55e9cSEmilio G. Cota const struct qht_iter iter = {
88469d55e9cSEmilio G. Cota .f.retvoid = func,
88569d55e9cSEmilio G. Cota .type = QHT_ITER_VOID,
88669d55e9cSEmilio G. Cota };
88769d55e9cSEmilio G. Cota
88869d55e9cSEmilio G. Cota do_qht_iter(ht, &iter, userp);
88969d55e9cSEmilio G. Cota }
89069d55e9cSEmilio G. Cota
qht_iter_remove(struct qht * ht,qht_iter_bool_func_t func,void * userp)89169d55e9cSEmilio G. Cota void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp)
89269d55e9cSEmilio G. Cota {
89369d55e9cSEmilio G. Cota const struct qht_iter iter = {
89469d55e9cSEmilio G. Cota .f.retbool = func,
89569d55e9cSEmilio G. Cota .type = QHT_ITER_RM,
89669d55e9cSEmilio G. Cota };
89769d55e9cSEmilio G. Cota
89869d55e9cSEmilio G. Cota do_qht_iter(ht, &iter, userp);
89969d55e9cSEmilio G. Cota }
90069d55e9cSEmilio G. Cota
90178255ba2SEmilio G. Cota struct qht_map_copy_data {
90278255ba2SEmilio G. Cota struct qht *ht;
90378255ba2SEmilio G. Cota struct qht_map *new;
90478255ba2SEmilio G. Cota };
90578255ba2SEmilio G. Cota
qht_map_copy(void * p,uint32_t hash,void * userp)90678255ba2SEmilio G. Cota static void qht_map_copy(void *p, uint32_t hash, void *userp)
9072e11264aSEmilio G. Cota {
90878255ba2SEmilio G. Cota struct qht_map_copy_data *data = userp;
90978255ba2SEmilio G. Cota struct qht *ht = data->ht;
91078255ba2SEmilio G. Cota struct qht_map *new = data->new;
9112e11264aSEmilio G. Cota struct qht_bucket *b = qht_map_to_bucket(new, hash);
9122e11264aSEmilio G. Cota
9132e11264aSEmilio G. Cota /* no need to acquire b->lock because no thread has seen this map yet */
9142e11264aSEmilio G. Cota qht_insert__locked(ht, new, b, p, hash, NULL);
9152e11264aSEmilio G. Cota }
9162e11264aSEmilio G. Cota
9172e11264aSEmilio G. Cota /*
91876b553b3SEmilio G. Cota * Atomically perform a resize and/or reset.
91976b553b3SEmilio G. Cota * Call with ht->lock held.
9202e11264aSEmilio G. Cota */
qht_do_resize_reset(struct qht * ht,struct qht_map * new,bool reset)92176b553b3SEmilio G. Cota static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
9222e11264aSEmilio G. Cota {
9232e11264aSEmilio G. Cota struct qht_map *old;
92469d55e9cSEmilio G. Cota const struct qht_iter iter = {
92569d55e9cSEmilio G. Cota .f.retvoid = qht_map_copy,
92669d55e9cSEmilio G. Cota .type = QHT_ITER_VOID,
92769d55e9cSEmilio G. Cota };
92878255ba2SEmilio G. Cota struct qht_map_copy_data data;
9292e11264aSEmilio G. Cota
9302e11264aSEmilio G. Cota old = ht->map;
93176b553b3SEmilio G. Cota qht_map_lock_buckets(old);
9322e11264aSEmilio G. Cota
93376b553b3SEmilio G. Cota if (reset) {
93476b553b3SEmilio G. Cota qht_map_reset__all_locked(old);
93576b553b3SEmilio G. Cota }
93676b553b3SEmilio G. Cota
93776b553b3SEmilio G. Cota if (new == NULL) {
93876b553b3SEmilio G. Cota qht_map_unlock_buckets(old);
93976b553b3SEmilio G. Cota return;
94076b553b3SEmilio G. Cota }
94176b553b3SEmilio G. Cota
942719a3077SMarkus Armbruster g_assert(new->n_buckets != old->n_buckets);
94378255ba2SEmilio G. Cota data.ht = ht;
94478255ba2SEmilio G. Cota data.new = new;
94578255ba2SEmilio G. Cota qht_map_iter__all_locked(old, &iter, &data);
9462e11264aSEmilio G. Cota qht_map_debug__all_locked(new);
9472e11264aSEmilio G. Cota
948d73415a3SStefan Hajnoczi qatomic_rcu_set(&ht->map, new);
94976b553b3SEmilio G. Cota qht_map_unlock_buckets(old);
9502e11264aSEmilio G. Cota call_rcu(old, qht_map_destroy, rcu);
9512e11264aSEmilio G. Cota }
9522e11264aSEmilio G. Cota
qht_resize(struct qht * ht,size_t n_elems)9532e11264aSEmilio G. Cota bool qht_resize(struct qht *ht, size_t n_elems)
9542e11264aSEmilio G. Cota {
9552e11264aSEmilio G. Cota size_t n_buckets = qht_elems_to_buckets(n_elems);
9562e11264aSEmilio G. Cota size_t ret = false;
9572e11264aSEmilio G. Cota
958fe9959a2SEmilio G. Cota qht_lock(ht);
9592e11264aSEmilio G. Cota if (n_buckets != ht->map->n_buckets) {
9602e11264aSEmilio G. Cota struct qht_map *new;
9612e11264aSEmilio G. Cota
9622e11264aSEmilio G. Cota new = qht_map_create(n_buckets);
9632e11264aSEmilio G. Cota qht_do_resize(ht, new);
9642e11264aSEmilio G. Cota ret = true;
9652e11264aSEmilio G. Cota }
966fe9959a2SEmilio G. Cota qht_unlock(ht);
9672e11264aSEmilio G. Cota
9682e11264aSEmilio G. Cota return ret;
9692e11264aSEmilio G. Cota }
9702e11264aSEmilio G. Cota
9712e11264aSEmilio G. Cota /* pass @stats to qht_statistics_destroy() when done */
qht_statistics_init(const struct qht * ht,struct qht_stats * stats)9726579f107SEmilio G. Cota void qht_statistics_init(const struct qht *ht, struct qht_stats *stats)
9732e11264aSEmilio G. Cota {
9746579f107SEmilio G. Cota const struct qht_map *map;
9752e11264aSEmilio G. Cota int i;
9762e11264aSEmilio G. Cota
977d73415a3SStefan Hajnoczi map = qatomic_rcu_read(&ht->map);
9782e11264aSEmilio G. Cota
9792e11264aSEmilio G. Cota stats->used_head_buckets = 0;
9802e11264aSEmilio G. Cota stats->entries = 0;
9812e11264aSEmilio G. Cota qdist_init(&stats->chain);
9822e11264aSEmilio G. Cota qdist_init(&stats->occupancy);
9837266ae91SEmilio G. Cota /* bail out if the qht has not yet been initialized */
9847266ae91SEmilio G. Cota if (unlikely(map == NULL)) {
9857266ae91SEmilio G. Cota stats->head_buckets = 0;
9867266ae91SEmilio G. Cota return;
9877266ae91SEmilio G. Cota }
9887266ae91SEmilio G. Cota stats->head_buckets = map->n_buckets;
9892e11264aSEmilio G. Cota
9902e11264aSEmilio G. Cota for (i = 0; i < map->n_buckets; i++) {
9916579f107SEmilio G. Cota const struct qht_bucket *head = &map->buckets[i];
9926579f107SEmilio G. Cota const struct qht_bucket *b;
9932e11264aSEmilio G. Cota unsigned int version;
9942e11264aSEmilio G. Cota size_t buckets;
9952e11264aSEmilio G. Cota size_t entries;
9962e11264aSEmilio G. Cota int j;
9972e11264aSEmilio G. Cota
9982e11264aSEmilio G. Cota do {
9992e11264aSEmilio G. Cota version = seqlock_read_begin(&head->sequence);
10002e11264aSEmilio G. Cota buckets = 0;
10012e11264aSEmilio G. Cota entries = 0;
10022e11264aSEmilio G. Cota b = head;
10032e11264aSEmilio G. Cota do {
10042e11264aSEmilio G. Cota for (j = 0; j < QHT_BUCKET_ENTRIES; j++) {
1005d73415a3SStefan Hajnoczi if (qatomic_read(&b->pointers[j]) == NULL) {
10062e11264aSEmilio G. Cota break;
10072e11264aSEmilio G. Cota }
10082e11264aSEmilio G. Cota entries++;
10092e11264aSEmilio G. Cota }
10102e11264aSEmilio G. Cota buckets++;
1011d73415a3SStefan Hajnoczi b = qatomic_rcu_read(&b->next);
10122e11264aSEmilio G. Cota } while (b);
10132e11264aSEmilio G. Cota } while (seqlock_read_retry(&head->sequence, version));
10142e11264aSEmilio G. Cota
10152e11264aSEmilio G. Cota if (entries) {
10162e11264aSEmilio G. Cota qdist_inc(&stats->chain, buckets);
10172e11264aSEmilio G. Cota qdist_inc(&stats->occupancy,
10182e11264aSEmilio G. Cota (double)entries / QHT_BUCKET_ENTRIES / buckets);
10192e11264aSEmilio G. Cota stats->used_head_buckets++;
10202e11264aSEmilio G. Cota stats->entries += entries;
10212e11264aSEmilio G. Cota } else {
10222e11264aSEmilio G. Cota qdist_inc(&stats->occupancy, 0);
10232e11264aSEmilio G. Cota }
10242e11264aSEmilio G. Cota }
10252e11264aSEmilio G. Cota }
10262e11264aSEmilio G. Cota
qht_statistics_destroy(struct qht_stats * stats)10272e11264aSEmilio G. Cota void qht_statistics_destroy(struct qht_stats *stats)
10282e11264aSEmilio G. Cota {
10292e11264aSEmilio G. Cota qdist_destroy(&stats->occupancy);
10302e11264aSEmilio G. Cota qdist_destroy(&stats->chain);
10312e11264aSEmilio G. Cota }
1032