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
51  * Writers check for concurrent resizes by comparing ht->map before and after
174  * @buckets: array of head buckets. It is constant once the map is created.
175  * @n_buckets: number of head buckets. It is constant once the map is created.
181  * Buckets are tracked in what we call a "map", i.e. this structure.
228 static void qht_map_debug__all_locked(struct qht_map *map)  in qht_map_debug__all_locked()  argument
232     for (i = 0; i < map->n_buckets; i++) {  in qht_map_debug__all_locked()
233         qht_bucket_debug__locked(&map->buckets[i]);  in qht_map_debug__all_locked()
243 static inline void qht_map_debug__all_locked(struct qht_map *map)  in qht_map_debug__all_locked()  argument
257 static inline void qht_do_if_first_in_stripe(struct qht_map *map,  in qht_do_if_first_in_stripe()  argument
262     unsigned long bucket_idx = b - map->buckets;  in qht_do_if_first_in_stripe()
266         func(&map->tsan_bucket_locks[lock_idx].lock);  in qht_do_if_first_in_stripe()
273 static inline void qht_bucket_lock_do(struct qht_map *map,  in qht_bucket_lock_do()  argument
278     unsigned long bucket_idx = b - map->buckets;  in qht_bucket_lock_do()
280     func(&map->tsan_bucket_locks[lock_idx].lock);  in qht_bucket_lock_do()
286 static inline void qht_bucket_lock(struct qht_map *map,  in qht_bucket_lock()  argument
289     qht_bucket_lock_do(map, b, qemu_spin_lock);  in qht_bucket_lock()
292 static inline void qht_bucket_unlock(struct qht_map *map,  in qht_bucket_unlock()  argument
295     qht_bucket_lock_do(map, b, qemu_spin_unlock);  in qht_bucket_unlock()
298 static inline void qht_head_init(struct qht_map *map, struct qht_bucket *b)  in qht_head_init()  argument
301     qht_do_if_first_in_stripe(map, b, qemu_spin_init);  in qht_head_init()
306 struct qht_bucket *qht_map_to_bucket(const struct qht_map *map, uint32_t hash)  in qht_map_to_bucket()  argument
308     return &map->buckets[hash & (map->n_buckets - 1)];  in qht_map_to_bucket()
311 /* acquire all bucket locks from a map */
312 static void qht_map_lock_buckets(struct qht_map *map)  in qht_map_lock_buckets()  argument
316     for (i = 0; i < map->n_buckets; i++) {  in qht_map_lock_buckets()
317         struct qht_bucket *b = &map->buckets[i];  in qht_map_lock_buckets()
319         qht_do_if_first_in_stripe(map, b, qemu_spin_lock);  in qht_map_lock_buckets()
323 static void qht_map_unlock_buckets(struct qht_map *map)  in qht_map_unlock_buckets()  argument
327     for (i = 0; i < map->n_buckets; i++) {  in qht_map_unlock_buckets()
328         struct qht_bucket *b = &map->buckets[i];  in qht_map_unlock_buckets()
330         qht_do_if_first_in_stripe(map, b, qemu_spin_unlock);  in qht_map_unlock_buckets()
336  * @map should be the value read before acquiring the lock (or locks).
339                                             const struct qht_map *map)  in qht_map_is_stale__locked()  argument
341     return map != ht->map;  in qht_map_is_stale__locked()
345  * Grab all bucket locks, and set @pmap after making sure the map isn't stale.
354     struct qht_map *map;  in qht_map_lock_buckets__no_stale()  local
356     map = qatomic_rcu_read(&ht->map);  in qht_map_lock_buckets__no_stale()
357     qht_map_lock_buckets(map);  in qht_map_lock_buckets__no_stale()
358     if (likely(!qht_map_is_stale__locked(ht, map))) {  in qht_map_lock_buckets__no_stale()
359         *pmap = map;  in qht_map_lock_buckets__no_stale()
362     qht_map_unlock_buckets(map);  in qht_map_lock_buckets__no_stale()
364     /* we raced with a resize; acquire ht->lock to see the updated ht->map */  in qht_map_lock_buckets__no_stale()
366     map = ht->map;  in qht_map_lock_buckets__no_stale()
367     qht_map_lock_buckets(map);  in qht_map_lock_buckets__no_stale()
369     *pmap = map;  in qht_map_lock_buckets__no_stale()
373  * Get a head bucket and lock it, making sure its parent map is not stale.
374  * @pmap is filled with a pointer to the bucket's parent map.
385     struct qht_map *map;  in qht_bucket_lock__no_stale()  local
387     map = qatomic_rcu_read(&ht->map);  in qht_bucket_lock__no_stale()
388     b = qht_map_to_bucket(map, hash);  in qht_bucket_lock__no_stale()
390     qht_bucket_lock(map, b);  in qht_bucket_lock__no_stale()
391     if (likely(!qht_map_is_stale__locked(ht, map))) {  in qht_bucket_lock__no_stale()
392         *pmap = map;  in qht_bucket_lock__no_stale()
395     qht_bucket_unlock(map, b);  in qht_bucket_lock__no_stale()
397     /* we raced with a resize; acquire ht->lock to see the updated ht->map */  in qht_bucket_lock__no_stale()
399     map = ht->map;  in qht_bucket_lock__no_stale()
400     b = qht_map_to_bucket(map, hash);  in qht_bucket_lock__no_stale()
401     qht_bucket_lock(map, b);  in qht_bucket_lock__no_stale()
403     *pmap = map;  in qht_bucket_lock__no_stale()
407 static inline bool qht_map_needs_resize(const struct qht_map *map)  in qht_map_needs_resize()  argument
409     return qatomic_read(&map->n_added_buckets) >  in qht_map_needs_resize()
410            map->n_added_buckets_threshold;  in qht_map_needs_resize()
413 static inline void qht_chain_destroy(struct qht_map *map,  in qht_chain_destroy()  argument
419     qht_do_if_first_in_stripe(map, head, qemu_spin_destroy);  in qht_chain_destroy()
427 /* pass only an orphan map */
428 static void qht_map_destroy(struct qht_map *map)  in qht_map_destroy()  argument
432     for (i = 0; i < map->n_buckets; i++) {  in qht_map_destroy()
433         qht_chain_destroy(map, &map->buckets[i]);  in qht_map_destroy()
435     qemu_vfree(map->buckets);  in qht_map_destroy()
436     g_free(map);  in qht_map_destroy()
441     struct qht_map *map;  in qht_map_create()  local
444     map = g_malloc(sizeof(*map));  in qht_map_create()
445     map->n_buckets = n_buckets;  in qht_map_create()
447     map->n_added_buckets = 0;  in qht_map_create()
448     map->n_added_buckets_threshold = n_buckets /  in qht_map_create()
452     if (unlikely(map->n_added_buckets_threshold == 0)) {  in qht_map_create()
453         map->n_added_buckets_threshold = 1;  in qht_map_create()
456     map->buckets = qemu_memalign(QHT_BUCKET_ALIGN,  in qht_map_create()
457                                  sizeof(*map->buckets) * n_buckets);  in qht_map_create()
459         qht_head_init(map, &map->buckets[i]);  in qht_map_create()
461     return map;  in qht_map_create()
467     struct qht_map *map;  in qht_init()  local
474     map = qht_map_create(n_buckets);  in qht_init()
475     qatomic_rcu_set(&ht->map, map);  in qht_init()
481     qht_map_destroy(ht->map);  in qht_destroy()
506 static void qht_map_reset__all_locked(struct qht_map *map)  in qht_map_reset__all_locked()  argument
510     for (i = 0; i < map->n_buckets; i++) {  in qht_map_reset__all_locked()
511         qht_bucket_reset__locked(&map->buckets[i]);  in qht_map_reset__all_locked()
513     qht_map_debug__all_locked(map);  in qht_map_reset__all_locked()
518     struct qht_map *map;  in qht_reset()  local
520     qht_map_lock_buckets__no_stale(ht, &map);  in qht_reset()
521     qht_map_reset__all_locked(map);  in qht_reset()
522     qht_map_unlock_buckets(map);  in qht_reset()
538     struct qht_map *map;  in qht_reset_size()  local
544     map = ht->map;  in qht_reset_size()
545     if (n_buckets != map->n_buckets) {  in qht_reset_size()
599     const struct qht_map *map;  in qht_lookup_custom()  local
603     map = qatomic_rcu_read(&ht->map);  in qht_lookup_custom()
604     b = qht_map_to_bucket(map, hash);  in qht_lookup_custom()
627 static void *qht_insert__locked(const struct qht *ht, struct qht_map *map,  in qht_insert__locked()  argument
655     qatomic_inc(&map->n_added_buckets);  in qht_insert__locked()
656     if (unlikely(qht_map_needs_resize(map)) && needs_resize) {  in qht_insert__locked()
675     struct qht_map *map;  in qht_grow_maybe()  local
684     map = ht->map;  in qht_grow_maybe()
686     if (qht_map_needs_resize(map)) {  in qht_grow_maybe()
687         struct qht_map *new = qht_map_create(map->n_buckets * 2);  in qht_grow_maybe()
697     struct qht_map *map;  in qht_insert()  local
704     b = qht_bucket_lock__no_stale(ht, hash, &map);  in qht_insert()
705     prev = qht_insert__locked(ht, map, b, p, hash, &needs_resize);  in qht_insert()
707     qht_bucket_unlock(map, b);  in qht_insert()
809     struct qht_map *map;  in qht_remove()  local
815     b = qht_bucket_lock__no_stale(ht, hash, &map);  in qht_remove()
818     qht_bucket_unlock(map, b);  in qht_remove()
857 /* call with all of the map's locks held */
858 static inline void qht_map_iter__all_locked(struct qht_map *map,  in qht_map_iter__all_locked()  argument
864     for (i = 0; i < map->n_buckets; i++) {  in qht_map_iter__all_locked()
865         qht_bucket_iter(&map->buckets[i], iter, userp);  in qht_map_iter__all_locked()
872     struct qht_map *map;  in do_qht_iter()  local
874     map = qatomic_rcu_read(&ht->map);  in do_qht_iter()
875     qht_map_lock_buckets(map);  in do_qht_iter()
876     qht_map_iter__all_locked(map, iter, userp);  in do_qht_iter()
877     qht_map_unlock_buckets(map);  in do_qht_iter()
912     /* no need to acquire b->lock because no thread has seen this map yet */  in qht_map_copy()
929     old = ht->map;  in qht_do_resize_reset()
947     qatomic_rcu_set(&ht->map, new);  in qht_do_resize_reset()
958     if (n_buckets != ht->map->n_buckets) {  in qht_resize()
973     const struct qht_map *map;  in qht_statistics_init()  local
976     map = qatomic_rcu_read(&ht->map);  in qht_statistics_init()
983     if (unlikely(map == NULL)) {  in qht_statistics_init()
987     stats->head_buckets = map->n_buckets;  in qht_statistics_init()
989     for (i = 0; i < map->n_buckets; i++) {  in qht_statistics_init()
990         const struct qht_bucket *head = &map->buckets[i];  in qht_statistics_init()