Merge remote-tracking branch 'remotes/jasowang/tags/net-pull-request' into staging
[qemu/ar7.git] / util / qht.c
blob079605121b1452dac9937b0e6137d88eaf029946
1 /*
2 * qht.c - QEMU Hash Table, designed to scale for read-mostly workloads.
4 * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
6 * License: GNU GPL, version 2 or later.
7 * See the COPYING file in the top-level directory.
9 * Assumptions:
10 * - NULL cannot be inserted/removed as a pointer value.
11 * - Trying to insert an already-existing hash-pointer pair is OK. However,
12 * it is not OK to insert into the same hash table different hash-pointer
13 * pairs that have the same pointer value, but not the hashes.
14 * - Lookups are performed under an RCU read-critical section; removals
15 * must wait for a grace period to elapse before freeing removed objects.
17 * Features:
18 * - Reads (i.e. lookups and iterators) can be concurrent with other reads.
19 * Lookups that are concurrent with writes to the same bucket will retry
20 * via a seqlock; iterators acquire all bucket locks and therefore can be
21 * concurrent with lookups and are serialized wrt writers.
22 * - Writes (i.e. insertions/removals) can be concurrent with writes to
23 * different buckets; writes to the same bucket are serialized through a lock.
24 * - Optional auto-resizing: the hash table resizes up if the load surpasses
25 * a certain threshold. Resizing is done concurrently with readers; writes
26 * are serialized with the resize operation.
28 * The key structure is the bucket, which is cacheline-sized. Buckets
29 * contain a few hash values and pointers; the u32 hash values are stored in
30 * full so that resizing is fast. Having this structure instead of directly
31 * chaining items has two advantages:
32 * - Failed lookups fail fast, and touch a minimum number of cache lines.
33 * - Resizing the hash table with concurrent lookups is easy.
35 * There are two types of buckets:
36 * 1. "head" buckets are the ones allocated in the array of buckets in qht_map.
37 * 2. all "non-head" buckets (i.e. all others) are members of a chain that
38 * starts from a head bucket.
39 * Note that the seqlock and spinlock of a head bucket applies to all buckets
40 * chained to it; these two fields are unused in non-head buckets.
42 * On removals, we move the last valid item in the chain to the position of the
43 * just-removed entry. This makes lookups slightly faster, since the moment an
44 * invalid entry is found, the (failed) lookup is over.
46 * Resizing is done by taking all bucket spinlocks (so that no other writers can
47 * race with us) and then copying all entries into a new hash map. Then, the
48 * ht->map pointer is set, and the old map is freed once no RCU readers can see
49 * it anymore.
51 * Writers check for concurrent resizes by comparing ht->map before and after
52 * acquiring their bucket lock. If they don't match, a resize has occurred
53 * while the bucket spinlock was being acquired.
55 * Related Work:
56 * - Idea of cacheline-sized buckets with full hashes taken from:
57 * David, Guerraoui & Trigonakis, "Asynchronized Concurrency:
58 * The Secret to Scaling Concurrent Search Data Structures", ASPLOS'15.
59 * - Why not RCU-based hash tables? They would allow us to get rid of the
60 * seqlock, but resizing would take forever since RCU read critical
61 * sections in QEMU take quite a long time.
62 * More info on relativistic hash tables:
63 * + Triplett, McKenney & Walpole, "Resizable, Scalable, Concurrent Hash
64 * Tables via Relativistic Programming", USENIX ATC'11.
65 * + Corbet, "Relativistic hash tables, part 1: Algorithms", @ lwn.net, 2014.
66 * https://lwn.net/Articles/612021/
68 #include "qemu/osdep.h"
69 #include "qemu/qht.h"
70 #include "qemu/atomic.h"
71 #include "qemu/rcu.h"
73 //#define QHT_DEBUG
76 * We want to avoid false sharing of cache lines. Most systems have 64-byte
77 * cache lines so we go with it for simplicity.
79 * Note that systems with smaller cache lines will be fine (the struct is
80 * almost 64-bytes); systems with larger cache lines might suffer from
81 * some false sharing.
83 #define QHT_BUCKET_ALIGN 64
85 /* define these to keep sizeof(qht_bucket) within QHT_BUCKET_ALIGN */
86 #if HOST_LONG_BITS == 32
87 #define QHT_BUCKET_ENTRIES 6
88 #else /* 64-bit */
89 #define QHT_BUCKET_ENTRIES 4
90 #endif
92 enum qht_iter_type {
93 QHT_ITER_VOID, /* do nothing; use retvoid */
94 QHT_ITER_RM, /* remove element if retbool returns true */
97 struct qht_iter {
98 union {
99 qht_iter_func_t retvoid;
100 qht_iter_bool_func_t retbool;
101 } f;
102 enum qht_iter_type type;
106 * Do _not_ use qemu_mutex_[try]lock directly! Use these macros, otherwise
107 * the profiler (QSP) will deadlock.
109 static inline void qht_lock(struct qht *ht)
111 if (ht->mode & QHT_MODE_RAW_MUTEXES) {
112 qemu_mutex_lock__raw(&ht->lock);
113 } else {
114 qemu_mutex_lock(&ht->lock);
118 static inline int qht_trylock(struct qht *ht)
120 if (ht->mode & QHT_MODE_RAW_MUTEXES) {
121 return qemu_mutex_trylock__raw(&(ht)->lock);
123 return qemu_mutex_trylock(&(ht)->lock);
126 /* this inline is not really necessary, but it helps keep code consistent */
127 static inline void qht_unlock(struct qht *ht)
129 qemu_mutex_unlock(&ht->lock);
133 * Note: reading partially-updated pointers in @pointers could lead to
134 * segfaults. We thus access them with qatomic_read/set; this guarantees
135 * that the compiler makes all those accesses atomic. We also need the
136 * volatile-like behavior in qatomic_read, since otherwise the compiler
137 * might refetch the pointer.
138 * qatomic_read's are of course not necessary when the bucket lock is held.
140 * If both ht->lock and b->lock are grabbed, ht->lock should always
141 * be grabbed first.
143 struct qht_bucket {
144 QemuSpin lock;
145 QemuSeqLock sequence;
146 uint32_t hashes[QHT_BUCKET_ENTRIES];
147 void *pointers[QHT_BUCKET_ENTRIES];
148 struct qht_bucket *next;
149 } QEMU_ALIGNED(QHT_BUCKET_ALIGN);
151 QEMU_BUILD_BUG_ON(sizeof(struct qht_bucket) > QHT_BUCKET_ALIGN);
154 * struct qht_map - structure to track an array of buckets
155 * @rcu: used by RCU. Keep it as the top field in the struct to help valgrind
156 * find the whole struct.
157 * @buckets: array of head buckets. It is constant once the map is created.
158 * @n_buckets: number of head buckets. It is constant once the map is created.
159 * @n_added_buckets: number of added (i.e. "non-head") buckets
160 * @n_added_buckets_threshold: threshold to trigger an upward resize once the
161 * number of added buckets surpasses it.
163 * Buckets are tracked in what we call a "map", i.e. this structure.
165 struct qht_map {
166 struct rcu_head rcu;
167 struct qht_bucket *buckets;
168 size_t n_buckets;
169 size_t n_added_buckets;
170 size_t n_added_buckets_threshold;
173 /* trigger a resize when n_added_buckets > n_buckets / div */
174 #define QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV 8
176 static void qht_do_resize_reset(struct qht *ht, struct qht_map *new,
177 bool reset);
178 static void qht_grow_maybe(struct qht *ht);
180 #ifdef QHT_DEBUG
182 #define qht_debug_assert(X) do { assert(X); } while (0)
184 static void qht_bucket_debug__locked(struct qht_bucket *b)
186 bool seen_empty = false;
187 bool corrupt = false;
188 int i;
190 do {
191 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
192 if (b->pointers[i] == NULL) {
193 seen_empty = true;
194 continue;
196 if (seen_empty) {
197 fprintf(stderr, "%s: b: %p, pos: %i, hash: 0x%x, p: %p\n",
198 __func__, b, i, b->hashes[i], b->pointers[i]);
199 corrupt = true;
202 b = b->next;
203 } while (b);
204 qht_debug_assert(!corrupt);
207 static void qht_map_debug__all_locked(struct qht_map *map)
209 int i;
211 for (i = 0; i < map->n_buckets; i++) {
212 qht_bucket_debug__locked(&map->buckets[i]);
215 #else
217 #define qht_debug_assert(X) do { (void)(X); } while (0)
219 static inline void qht_bucket_debug__locked(struct qht_bucket *b)
222 static inline void qht_map_debug__all_locked(struct qht_map *map)
224 #endif /* QHT_DEBUG */
226 static inline size_t qht_elems_to_buckets(size_t n_elems)
228 return pow2ceil(n_elems / QHT_BUCKET_ENTRIES);
231 static inline void qht_head_init(struct qht_bucket *b)
233 memset(b, 0, sizeof(*b));
234 qemu_spin_init(&b->lock);
235 seqlock_init(&b->sequence);
238 static inline
239 struct qht_bucket *qht_map_to_bucket(const struct qht_map *map, uint32_t hash)
241 return &map->buckets[hash & (map->n_buckets - 1)];
244 /* acquire all bucket locks from a map */
245 static void qht_map_lock_buckets(struct qht_map *map)
247 size_t i;
249 for (i = 0; i < map->n_buckets; i++) {
250 struct qht_bucket *b = &map->buckets[i];
252 qemu_spin_lock(&b->lock);
256 static void qht_map_unlock_buckets(struct qht_map *map)
258 size_t i;
260 for (i = 0; i < map->n_buckets; i++) {
261 struct qht_bucket *b = &map->buckets[i];
263 qemu_spin_unlock(&b->lock);
268 * Call with at least a bucket lock held.
269 * @map should be the value read before acquiring the lock (or locks).
271 static inline bool qht_map_is_stale__locked(const struct qht *ht,
272 const struct qht_map *map)
274 return map != ht->map;
278 * Grab all bucket locks, and set @pmap after making sure the map isn't stale.
280 * Pairs with qht_map_unlock_buckets(), hence the pass-by-reference.
282 * Note: callers cannot have ht->lock held.
284 static inline
285 void qht_map_lock_buckets__no_stale(struct qht *ht, struct qht_map **pmap)
287 struct qht_map *map;
289 map = qatomic_rcu_read(&ht->map);
290 qht_map_lock_buckets(map);
291 if (likely(!qht_map_is_stale__locked(ht, map))) {
292 *pmap = map;
293 return;
295 qht_map_unlock_buckets(map);
297 /* we raced with a resize; acquire ht->lock to see the updated ht->map */
298 qht_lock(ht);
299 map = ht->map;
300 qht_map_lock_buckets(map);
301 qht_unlock(ht);
302 *pmap = map;
303 return;
307 * Get a head bucket and lock it, making sure its parent map is not stale.
308 * @pmap is filled with a pointer to the bucket's parent map.
310 * Unlock with qemu_spin_unlock(&b->lock).
312 * Note: callers cannot have ht->lock held.
314 static inline
315 struct qht_bucket *qht_bucket_lock__no_stale(struct qht *ht, uint32_t hash,
316 struct qht_map **pmap)
318 struct qht_bucket *b;
319 struct qht_map *map;
321 map = qatomic_rcu_read(&ht->map);
322 b = qht_map_to_bucket(map, hash);
324 qemu_spin_lock(&b->lock);
325 if (likely(!qht_map_is_stale__locked(ht, map))) {
326 *pmap = map;
327 return b;
329 qemu_spin_unlock(&b->lock);
331 /* we raced with a resize; acquire ht->lock to see the updated ht->map */
332 qht_lock(ht);
333 map = ht->map;
334 b = qht_map_to_bucket(map, hash);
335 qemu_spin_lock(&b->lock);
336 qht_unlock(ht);
337 *pmap = map;
338 return b;
341 static inline bool qht_map_needs_resize(const struct qht_map *map)
343 return qatomic_read(&map->n_added_buckets) >
344 map->n_added_buckets_threshold;
347 static inline void qht_chain_destroy(const struct qht_bucket *head)
349 struct qht_bucket *curr = head->next;
350 struct qht_bucket *prev;
352 qemu_spin_destroy(&head->lock);
353 while (curr) {
354 prev = curr;
355 curr = curr->next;
356 qemu_vfree(prev);
360 /* pass only an orphan map */
361 static void qht_map_destroy(struct qht_map *map)
363 size_t i;
365 for (i = 0; i < map->n_buckets; i++) {
366 qht_chain_destroy(&map->buckets[i]);
368 qemu_vfree(map->buckets);
369 g_free(map);
372 static struct qht_map *qht_map_create(size_t n_buckets)
374 struct qht_map *map;
375 size_t i;
377 map = g_malloc(sizeof(*map));
378 map->n_buckets = n_buckets;
380 map->n_added_buckets = 0;
381 map->n_added_buckets_threshold = n_buckets /
382 QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV;
384 /* let tiny hash tables to at least add one non-head bucket */
385 if (unlikely(map->n_added_buckets_threshold == 0)) {
386 map->n_added_buckets_threshold = 1;
389 map->buckets = qemu_memalign(QHT_BUCKET_ALIGN,
390 sizeof(*map->buckets) * n_buckets);
391 for (i = 0; i < n_buckets; i++) {
392 qht_head_init(&map->buckets[i]);
394 return map;
397 void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems,
398 unsigned int mode)
400 struct qht_map *map;
401 size_t n_buckets = qht_elems_to_buckets(n_elems);
403 g_assert(cmp);
404 ht->cmp = cmp;
405 ht->mode = mode;
406 qemu_mutex_init(&ht->lock);
407 map = qht_map_create(n_buckets);
408 qatomic_rcu_set(&ht->map, map);
411 /* call only when there are no readers/writers left */
412 void qht_destroy(struct qht *ht)
414 qht_map_destroy(ht->map);
415 memset(ht, 0, sizeof(*ht));
418 static void qht_bucket_reset__locked(struct qht_bucket *head)
420 struct qht_bucket *b = head;
421 int i;
423 seqlock_write_begin(&head->sequence);
424 do {
425 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
426 if (b->pointers[i] == NULL) {
427 goto done;
429 qatomic_set(&b->hashes[i], 0);
430 qatomic_set(&b->pointers[i], NULL);
432 b = b->next;
433 } while (b);
434 done:
435 seqlock_write_end(&head->sequence);
438 /* call with all bucket locks held */
439 static void qht_map_reset__all_locked(struct qht_map *map)
441 size_t i;
443 for (i = 0; i < map->n_buckets; i++) {
444 qht_bucket_reset__locked(&map->buckets[i]);
446 qht_map_debug__all_locked(map);
449 void qht_reset(struct qht *ht)
451 struct qht_map *map;
453 qht_map_lock_buckets__no_stale(ht, &map);
454 qht_map_reset__all_locked(map);
455 qht_map_unlock_buckets(map);
458 static inline void qht_do_resize(struct qht *ht, struct qht_map *new)
460 qht_do_resize_reset(ht, new, false);
463 static inline void qht_do_resize_and_reset(struct qht *ht, struct qht_map *new)
465 qht_do_resize_reset(ht, new, true);
468 bool qht_reset_size(struct qht *ht, size_t n_elems)
470 struct qht_map *new = NULL;
471 struct qht_map *map;
472 size_t n_buckets;
474 n_buckets = qht_elems_to_buckets(n_elems);
476 qht_lock(ht);
477 map = ht->map;
478 if (n_buckets != map->n_buckets) {
479 new = qht_map_create(n_buckets);
481 qht_do_resize_and_reset(ht, new);
482 qht_unlock(ht);
484 return !!new;
487 static inline
488 void *qht_do_lookup(const struct qht_bucket *head, qht_lookup_func_t func,
489 const void *userp, uint32_t hash)
491 const struct qht_bucket *b = head;
492 int i;
494 do {
495 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
496 if (qatomic_read(&b->hashes[i]) == hash) {
497 /* The pointer is dereferenced before seqlock_read_retry,
498 * so (unlike qht_insert__locked) we need to use
499 * qatomic_rcu_read here.
501 void *p = qatomic_rcu_read(&b->pointers[i]);
503 if (likely(p) && likely(func(p, userp))) {
504 return p;
508 b = qatomic_rcu_read(&b->next);
509 } while (b);
511 return NULL;
514 static __attribute__((noinline))
515 void *qht_lookup__slowpath(const struct qht_bucket *b, qht_lookup_func_t func,
516 const void *userp, uint32_t hash)
518 unsigned int version;
519 void *ret;
521 do {
522 version = seqlock_read_begin(&b->sequence);
523 ret = qht_do_lookup(b, func, userp, hash);
524 } while (seqlock_read_retry(&b->sequence, version));
525 return ret;
528 void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash,
529 qht_lookup_func_t func)
531 const struct qht_bucket *b;
532 const struct qht_map *map;
533 unsigned int version;
534 void *ret;
536 map = qatomic_rcu_read(&ht->map);
537 b = qht_map_to_bucket(map, hash);
539 version = seqlock_read_begin(&b->sequence);
540 ret = qht_do_lookup(b, func, userp, hash);
541 if (likely(!seqlock_read_retry(&b->sequence, version))) {
542 return ret;
545 * Removing the do/while from the fastpath gives a 4% perf. increase when
546 * running a 100%-lookup microbenchmark.
548 return qht_lookup__slowpath(b, func, userp, hash);
551 void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash)
553 return qht_lookup_custom(ht, userp, hash, ht->cmp);
557 * call with head->lock held
558 * @ht is const since it is only used for ht->cmp()
560 static void *qht_insert__locked(const struct qht *ht, struct qht_map *map,
561 struct qht_bucket *head, void *p, uint32_t hash,
562 bool *needs_resize)
564 struct qht_bucket *b = head;
565 struct qht_bucket *prev = NULL;
566 struct qht_bucket *new = NULL;
567 int i;
569 do {
570 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
571 if (b->pointers[i]) {
572 if (unlikely(b->hashes[i] == hash &&
573 ht->cmp(b->pointers[i], p))) {
574 return b->pointers[i];
576 } else {
577 goto found;
580 prev = b;
581 b = b->next;
582 } while (b);
584 b = qemu_memalign(QHT_BUCKET_ALIGN, sizeof(*b));
585 memset(b, 0, sizeof(*b));
586 new = b;
587 i = 0;
588 qatomic_inc(&map->n_added_buckets);
589 if (unlikely(qht_map_needs_resize(map)) && needs_resize) {
590 *needs_resize = true;
593 found:
594 /* found an empty key: acquire the seqlock and write */
595 seqlock_write_begin(&head->sequence);
596 if (new) {
597 qatomic_rcu_set(&prev->next, b);
599 /* smp_wmb() implicit in seqlock_write_begin. */
600 qatomic_set(&b->hashes[i], hash);
601 qatomic_set(&b->pointers[i], p);
602 seqlock_write_end(&head->sequence);
603 return NULL;
606 static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht)
608 struct qht_map *map;
611 * If the lock is taken it probably means there's an ongoing resize,
612 * so bail out.
614 if (qht_trylock(ht)) {
615 return;
617 map = ht->map;
618 /* another thread might have just performed the resize we were after */
619 if (qht_map_needs_resize(map)) {
620 struct qht_map *new = qht_map_create(map->n_buckets * 2);
622 qht_do_resize(ht, new);
624 qht_unlock(ht);
627 bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing)
629 struct qht_bucket *b;
630 struct qht_map *map;
631 bool needs_resize = false;
632 void *prev;
634 /* NULL pointers are not supported */
635 qht_debug_assert(p);
637 b = qht_bucket_lock__no_stale(ht, hash, &map);
638 prev = qht_insert__locked(ht, map, b, p, hash, &needs_resize);
639 qht_bucket_debug__locked(b);
640 qemu_spin_unlock(&b->lock);
642 if (unlikely(needs_resize) && ht->mode & QHT_MODE_AUTO_RESIZE) {
643 qht_grow_maybe(ht);
645 if (likely(prev == NULL)) {
646 return true;
648 if (existing) {
649 *existing = prev;
651 return false;
654 static inline bool qht_entry_is_last(const struct qht_bucket *b, int pos)
656 if (pos == QHT_BUCKET_ENTRIES - 1) {
657 if (b->next == NULL) {
658 return true;
660 return b->next->pointers[0] == NULL;
662 return b->pointers[pos + 1] == NULL;
665 static void
666 qht_entry_move(struct qht_bucket *to, int i, struct qht_bucket *from, int j)
668 qht_debug_assert(!(to == from && i == j));
669 qht_debug_assert(to->pointers[i]);
670 qht_debug_assert(from->pointers[j]);
672 qatomic_set(&to->hashes[i], from->hashes[j]);
673 qatomic_set(&to->pointers[i], from->pointers[j]);
675 qatomic_set(&from->hashes[j], 0);
676 qatomic_set(&from->pointers[j], NULL);
680 * Find the last valid entry in @orig, and swap it with @orig[pos], which has
681 * just been invalidated.
683 static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)
685 struct qht_bucket *b = orig;
686 struct qht_bucket *prev = NULL;
687 int i;
689 if (qht_entry_is_last(orig, pos)) {
690 orig->hashes[pos] = 0;
691 qatomic_set(&orig->pointers[pos], NULL);
692 return;
694 do {
695 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
696 if (b->pointers[i]) {
697 continue;
699 if (i > 0) {
700 return qht_entry_move(orig, pos, b, i - 1);
702 qht_debug_assert(prev);
703 return qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
705 prev = b;
706 b = b->next;
707 } while (b);
708 /* no free entries other than orig[pos], so swap it with the last one */
709 qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
712 /* call with b->lock held */
713 static inline
714 bool qht_remove__locked(struct qht_bucket *head, const void *p, uint32_t hash)
716 struct qht_bucket *b = head;
717 int i;
719 do {
720 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
721 void *q = b->pointers[i];
723 if (unlikely(q == NULL)) {
724 return false;
726 if (q == p) {
727 qht_debug_assert(b->hashes[i] == hash);
728 seqlock_write_begin(&head->sequence);
729 qht_bucket_remove_entry(b, i);
730 seqlock_write_end(&head->sequence);
731 return true;
734 b = b->next;
735 } while (b);
736 return false;
739 bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
741 struct qht_bucket *b;
742 struct qht_map *map;
743 bool ret;
745 /* NULL pointers are not supported */
746 qht_debug_assert(p);
748 b = qht_bucket_lock__no_stale(ht, hash, &map);
749 ret = qht_remove__locked(b, p, hash);
750 qht_bucket_debug__locked(b);
751 qemu_spin_unlock(&b->lock);
752 return ret;
755 static inline void qht_bucket_iter(struct qht_bucket *head,
756 const struct qht_iter *iter, void *userp)
758 struct qht_bucket *b = head;
759 int i;
761 do {
762 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
763 if (b->pointers[i] == NULL) {
764 return;
766 switch (iter->type) {
767 case QHT_ITER_VOID:
768 iter->f.retvoid(b->pointers[i], b->hashes[i], userp);
769 break;
770 case QHT_ITER_RM:
771 if (iter->f.retbool(b->pointers[i], b->hashes[i], userp)) {
772 /* replace i with the last valid element in the bucket */
773 seqlock_write_begin(&head->sequence);
774 qht_bucket_remove_entry(b, i);
775 seqlock_write_end(&head->sequence);
776 qht_bucket_debug__locked(b);
777 /* reevaluate i, since it just got replaced */
778 i--;
779 continue;
781 break;
782 default:
783 g_assert_not_reached();
786 b = b->next;
787 } while (b);
790 /* call with all of the map's locks held */
791 static inline void qht_map_iter__all_locked(struct qht_map *map,
792 const struct qht_iter *iter,
793 void *userp)
795 size_t i;
797 for (i = 0; i < map->n_buckets; i++) {
798 qht_bucket_iter(&map->buckets[i], iter, userp);
802 static inline void
803 do_qht_iter(struct qht *ht, const struct qht_iter *iter, void *userp)
805 struct qht_map *map;
807 map = qatomic_rcu_read(&ht->map);
808 qht_map_lock_buckets(map);
809 qht_map_iter__all_locked(map, iter, userp);
810 qht_map_unlock_buckets(map);
813 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
815 const struct qht_iter iter = {
816 .f.retvoid = func,
817 .type = QHT_ITER_VOID,
820 do_qht_iter(ht, &iter, userp);
823 void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp)
825 const struct qht_iter iter = {
826 .f.retbool = func,
827 .type = QHT_ITER_RM,
830 do_qht_iter(ht, &iter, userp);
833 struct qht_map_copy_data {
834 struct qht *ht;
835 struct qht_map *new;
838 static void qht_map_copy(void *p, uint32_t hash, void *userp)
840 struct qht_map_copy_data *data = userp;
841 struct qht *ht = data->ht;
842 struct qht_map *new = data->new;
843 struct qht_bucket *b = qht_map_to_bucket(new, hash);
845 /* no need to acquire b->lock because no thread has seen this map yet */
846 qht_insert__locked(ht, new, b, p, hash, NULL);
850 * Atomically perform a resize and/or reset.
851 * Call with ht->lock held.
853 static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
855 struct qht_map *old;
856 const struct qht_iter iter = {
857 .f.retvoid = qht_map_copy,
858 .type = QHT_ITER_VOID,
860 struct qht_map_copy_data data;
862 old = ht->map;
863 qht_map_lock_buckets(old);
865 if (reset) {
866 qht_map_reset__all_locked(old);
869 if (new == NULL) {
870 qht_map_unlock_buckets(old);
871 return;
874 g_assert(new->n_buckets != old->n_buckets);
875 data.ht = ht;
876 data.new = new;
877 qht_map_iter__all_locked(old, &iter, &data);
878 qht_map_debug__all_locked(new);
880 qatomic_rcu_set(&ht->map, new);
881 qht_map_unlock_buckets(old);
882 call_rcu(old, qht_map_destroy, rcu);
885 bool qht_resize(struct qht *ht, size_t n_elems)
887 size_t n_buckets = qht_elems_to_buckets(n_elems);
888 size_t ret = false;
890 qht_lock(ht);
891 if (n_buckets != ht->map->n_buckets) {
892 struct qht_map *new;
894 new = qht_map_create(n_buckets);
895 qht_do_resize(ht, new);
896 ret = true;
898 qht_unlock(ht);
900 return ret;
903 /* pass @stats to qht_statistics_destroy() when done */
904 void qht_statistics_init(const struct qht *ht, struct qht_stats *stats)
906 const struct qht_map *map;
907 int i;
909 map = qatomic_rcu_read(&ht->map);
911 stats->used_head_buckets = 0;
912 stats->entries = 0;
913 qdist_init(&stats->chain);
914 qdist_init(&stats->occupancy);
915 /* bail out if the qht has not yet been initialized */
916 if (unlikely(map == NULL)) {
917 stats->head_buckets = 0;
918 return;
920 stats->head_buckets = map->n_buckets;
922 for (i = 0; i < map->n_buckets; i++) {
923 const struct qht_bucket *head = &map->buckets[i];
924 const struct qht_bucket *b;
925 unsigned int version;
926 size_t buckets;
927 size_t entries;
928 int j;
930 do {
931 version = seqlock_read_begin(&head->sequence);
932 buckets = 0;
933 entries = 0;
934 b = head;
935 do {
936 for (j = 0; j < QHT_BUCKET_ENTRIES; j++) {
937 if (qatomic_read(&b->pointers[j]) == NULL) {
938 break;
940 entries++;
942 buckets++;
943 b = qatomic_rcu_read(&b->next);
944 } while (b);
945 } while (seqlock_read_retry(&head->sequence, version));
947 if (entries) {
948 qdist_inc(&stats->chain, buckets);
949 qdist_inc(&stats->occupancy,
950 (double)entries / QHT_BUCKET_ENTRIES / buckets);
951 stats->used_head_buckets++;
952 stats->entries += entries;
953 } else {
954 qdist_inc(&stats->occupancy, 0);
959 void qht_statistics_destroy(struct qht_stats *stats)
961 qdist_destroy(&stats->occupancy);
962 qdist_destroy(&stats->chain);