Postcopy: Add stats on page requests
[qemu.git] / util / qht.c
1 /*
2 * qht.c - QEMU Hash Table, designed to scale for read-mostly workloads.
3 *
4 * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
5 *
6 * License: GNU GPL, version 2 or later.
7 * See the COPYING file in the top-level directory.
8 *
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.
16 *
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.
27 *
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.
34 *
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.
41 *
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.
45 *
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.
50 *
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 occured
53 * while the bucket spinlock was being acquired.
54 *
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/
67 */
68 #include "qemu/qht.h"
69 #include "qemu/atomic.h"
70 #include "qemu/rcu.h"
71
72 //#define QHT_DEBUG
73
74 /*
75 * We want to avoid false sharing of cache lines. Most systems have 64-byte
76 * cache lines so we go with it for simplicity.
77 *
78 * Note that systems with smaller cache lines will be fine (the struct is
79 * almost 64-bytes); systems with larger cache lines might suffer from
80 * some false sharing.
81 */
82 #define QHT_BUCKET_ALIGN 64
83
84 /* define these to keep sizeof(qht_bucket) within QHT_BUCKET_ALIGN */
85 #if HOST_LONG_BITS == 32
86 #define QHT_BUCKET_ENTRIES 6
87 #else /* 64-bit */
88 #define QHT_BUCKET_ENTRIES 4
89 #endif
90
91 /*
92 * Note: reading partially-updated pointers in @pointers could lead to
93 * segfaults. We thus access them with atomic_read/set; this guarantees
94 * that the compiler makes all those accesses atomic. We also need the
95 * volatile-like behavior in atomic_read, since otherwise the compiler
96 * might refetch the pointer.
97 * atomic_read's are of course not necessary when the bucket lock is held.
98 *
99 * If both ht->lock and b->lock are grabbed, ht->lock should always
100 * be grabbed first.
101 */
102 struct qht_bucket {
103 QemuSpin lock;
104 QemuSeqLock sequence;
105 uint32_t hashes[QHT_BUCKET_ENTRIES];
106 void *pointers[QHT_BUCKET_ENTRIES];
107 struct qht_bucket *next;
108 } QEMU_ALIGNED(QHT_BUCKET_ALIGN);
109
110 QEMU_BUILD_BUG_ON(sizeof(struct qht_bucket) > QHT_BUCKET_ALIGN);
111
112 /**
113 * struct qht_map - structure to track an array of buckets
114 * @rcu: used by RCU. Keep it as the top field in the struct to help valgrind
115 * find the whole struct.
116 * @buckets: array of head buckets. It is constant once the map is created.
117 * @n_buckets: number of head buckets. It is constant once the map is created.
118 * @n_added_buckets: number of added (i.e. "non-head") buckets
119 * @n_added_buckets_threshold: threshold to trigger an upward resize once the
120 * number of added buckets surpasses it.
121 *
122 * Buckets are tracked in what we call a "map", i.e. this structure.
123 */
124 struct qht_map {
125 struct rcu_head rcu;
126 struct qht_bucket *buckets;
127 size_t n_buckets;
128 size_t n_added_buckets;
129 size_t n_added_buckets_threshold;
130 };
131
132 /* trigger a resize when n_added_buckets > n_buckets / div */
133 #define QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV 8
134
135 static void qht_do_resize(struct qht *ht, struct qht_map *new);
136 static void qht_grow_maybe(struct qht *ht);
137
138 #ifdef QHT_DEBUG
139
140 #define qht_debug_assert(X) do { assert(X); } while (0)
141
142 static void qht_bucket_debug__locked(struct qht_bucket *b)
143 {
144 bool seen_empty = false;
145 bool corrupt = false;
146 int i;
147
148 do {
149 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
150 if (b->pointers[i] == NULL) {
151 seen_empty = true;
152 continue;
153 }
154 if (seen_empty) {
155 fprintf(stderr, "%s: b: %p, pos: %i, hash: 0x%x, p: %p\n",
156 __func__, b, i, b->hashes[i], b->pointers[i]);
157 corrupt = true;
158 }
159 }
160 b = b->next;
161 } while (b);
162 qht_debug_assert(!corrupt);
163 }
164
165 static void qht_map_debug__all_locked(struct qht_map *map)
166 {
167 int i;
168
169 for (i = 0; i < map->n_buckets; i++) {
170 qht_bucket_debug__locked(&map->buckets[i]);
171 }
172 }
173 #else
174
175 #define qht_debug_assert(X) do { (void)(X); } while (0)
176
177 static inline void qht_bucket_debug__locked(struct qht_bucket *b)
178 { }
179
180 static inline void qht_map_debug__all_locked(struct qht_map *map)
181 { }
182 #endif /* QHT_DEBUG */
183
184 static inline size_t qht_elems_to_buckets(size_t n_elems)
185 {
186 return pow2ceil(n_elems / QHT_BUCKET_ENTRIES);
187 }
188
189 static inline void qht_head_init(struct qht_bucket *b)
190 {
191 memset(b, 0, sizeof(*b));
192 qemu_spin_init(&b->lock);
193 seqlock_init(&b->sequence);
194 }
195
196 static inline
197 struct qht_bucket *qht_map_to_bucket(struct qht_map *map, uint32_t hash)
198 {
199 return &map->buckets[hash & (map->n_buckets - 1)];
200 }
201
202 /* acquire all bucket locks from a map */
203 static void qht_map_lock_buckets(struct qht_map *map)
204 {
205 size_t i;
206
207 for (i = 0; i < map->n_buckets; i++) {
208 struct qht_bucket *b = &map->buckets[i];
209
210 qemu_spin_lock(&b->lock);
211 }
212 }
213
214 static void qht_map_unlock_buckets(struct qht_map *map)
215 {
216 size_t i;
217
218 for (i = 0; i < map->n_buckets; i++) {
219 struct qht_bucket *b = &map->buckets[i];
220
221 qemu_spin_unlock(&b->lock);
222 }
223 }
224
225 /*
226 * Call with at least a bucket lock held.
227 * @map should be the value read before acquiring the lock (or locks).
228 */
229 static inline bool qht_map_is_stale__locked(struct qht *ht, struct qht_map *map)
230 {
231 return map != ht->map;
232 }
233
234 /*
235 * Grab all bucket locks, and set @pmap after making sure the map isn't stale.
236 *
237 * Pairs with qht_map_unlock_buckets(), hence the pass-by-reference.
238 *
239 * Note: callers cannot have ht->lock held.
240 */
241 static inline
242 void qht_map_lock_buckets__no_stale(struct qht *ht, struct qht_map **pmap)
243 {
244 struct qht_map *map;
245
246 map = atomic_rcu_read(&ht->map);
247 qht_map_lock_buckets(map);
248 if (likely(!qht_map_is_stale__locked(ht, map))) {
249 *pmap = map;
250 return;
251 }
252 qht_map_unlock_buckets(map);
253
254 /* we raced with a resize; acquire ht->lock to see the updated ht->map */
255 qemu_mutex_lock(&ht->lock);
256 map = ht->map;
257 qht_map_lock_buckets(map);
258 qemu_mutex_unlock(&ht->lock);
259 *pmap = map;
260 return;
261 }
262
263 /*
264 * Get a head bucket and lock it, making sure its parent map is not stale.
265 * @pmap is filled with a pointer to the bucket's parent map.
266 *
267 * Unlock with qemu_spin_unlock(&b->lock).
268 *
269 * Note: callers cannot have ht->lock held.
270 */
271 static inline
272 struct qht_bucket *qht_bucket_lock__no_stale(struct qht *ht, uint32_t hash,
273 struct qht_map **pmap)
274 {
275 struct qht_bucket *b;
276 struct qht_map *map;
277
278 map = atomic_rcu_read(&ht->map);
279 b = qht_map_to_bucket(map, hash);
280
281 qemu_spin_lock(&b->lock);
282 if (likely(!qht_map_is_stale__locked(ht, map))) {
283 *pmap = map;
284 return b;
285 }
286 qemu_spin_unlock(&b->lock);
287
288 /* we raced with a resize; acquire ht->lock to see the updated ht->map */
289 qemu_mutex_lock(&ht->lock);
290 map = ht->map;
291 b = qht_map_to_bucket(map, hash);
292 qemu_spin_lock(&b->lock);
293 qemu_mutex_unlock(&ht->lock);
294 *pmap = map;
295 return b;
296 }
297
298 static inline bool qht_map_needs_resize(struct qht_map *map)
299 {
300 return atomic_read(&map->n_added_buckets) > map->n_added_buckets_threshold;
301 }
302
303 static inline void qht_chain_destroy(struct qht_bucket *head)
304 {
305 struct qht_bucket *curr = head->next;
306 struct qht_bucket *prev;
307
308 while (curr) {
309 prev = curr;
310 curr = curr->next;
311 qemu_vfree(prev);
312 }
313 }
314
315 /* pass only an orphan map */
316 static void qht_map_destroy(struct qht_map *map)
317 {
318 size_t i;
319
320 for (i = 0; i < map->n_buckets; i++) {
321 qht_chain_destroy(&map->buckets[i]);
322 }
323 qemu_vfree(map->buckets);
324 g_free(map);
325 }
326
327 static struct qht_map *qht_map_create(size_t n_buckets)
328 {
329 struct qht_map *map;
330 size_t i;
331
332 map = g_malloc(sizeof(*map));
333 map->n_buckets = n_buckets;
334
335 map->n_added_buckets = 0;
336 map->n_added_buckets_threshold = n_buckets /
337 QHT_NR_ADDED_BUCKETS_THRESHOLD_DIV;
338
339 /* let tiny hash tables to at least add one non-head bucket */
340 if (unlikely(map->n_added_buckets_threshold == 0)) {
341 map->n_added_buckets_threshold = 1;
342 }
343
344 map->buckets = qemu_memalign(QHT_BUCKET_ALIGN,
345 sizeof(*map->buckets) * n_buckets);
346 for (i = 0; i < n_buckets; i++) {
347 qht_head_init(&map->buckets[i]);
348 }
349 return map;
350 }
351
352 void qht_init(struct qht *ht, size_t n_elems, unsigned int mode)
353 {
354 struct qht_map *map;
355 size_t n_buckets = qht_elems_to_buckets(n_elems);
356
357 ht->mode = mode;
358 qemu_mutex_init(&ht->lock);
359 map = qht_map_create(n_buckets);
360 atomic_rcu_set(&ht->map, map);
361 }
362
363 /* call only when there are no readers/writers left */
364 void qht_destroy(struct qht *ht)
365 {
366 qht_map_destroy(ht->map);
367 memset(ht, 0, sizeof(*ht));
368 }
369
370 static void qht_bucket_reset__locked(struct qht_bucket *head)
371 {
372 struct qht_bucket *b = head;
373 int i;
374
375 seqlock_write_begin(&head->sequence);
376 do {
377 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
378 if (b->pointers[i] == NULL) {
379 goto done;
380 }
381 b->hashes[i] = 0;
382 atomic_set(&b->pointers[i], NULL);
383 }
384 b = b->next;
385 } while (b);
386 done:
387 seqlock_write_end(&head->sequence);
388 }
389
390 /* call with all bucket locks held */
391 static void qht_map_reset__all_locked(struct qht_map *map)
392 {
393 size_t i;
394
395 for (i = 0; i < map->n_buckets; i++) {
396 qht_bucket_reset__locked(&map->buckets[i]);
397 }
398 qht_map_debug__all_locked(map);
399 }
400
401 void qht_reset(struct qht *ht)
402 {
403 struct qht_map *map;
404
405 qht_map_lock_buckets__no_stale(ht, &map);
406 qht_map_reset__all_locked(map);
407 qht_map_unlock_buckets(map);
408 }
409
410 bool qht_reset_size(struct qht *ht, size_t n_elems)
411 {
412 struct qht_map *new;
413 struct qht_map *map;
414 size_t n_buckets;
415 bool resize = false;
416
417 n_buckets = qht_elems_to_buckets(n_elems);
418
419 qemu_mutex_lock(&ht->lock);
420 map = ht->map;
421 if (n_buckets != map->n_buckets) {
422 new = qht_map_create(n_buckets);
423 resize = true;
424 }
425
426 qht_map_lock_buckets(map);
427 qht_map_reset__all_locked(map);
428 if (resize) {
429 qht_do_resize(ht, new);
430 }
431 qht_map_unlock_buckets(map);
432 qemu_mutex_unlock(&ht->lock);
433
434 return resize;
435 }
436
437 static inline
438 void *qht_do_lookup(struct qht_bucket *head, qht_lookup_func_t func,
439 const void *userp, uint32_t hash)
440 {
441 struct qht_bucket *b = head;
442 int i;
443
444 do {
445 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
446 if (b->hashes[i] == hash) {
447 void *p = atomic_read(&b->pointers[i]);
448
449 if (likely(p) && likely(func(p, userp))) {
450 return p;
451 }
452 }
453 }
454 b = atomic_rcu_read(&b->next);
455 } while (b);
456
457 return NULL;
458 }
459
460 static __attribute__((noinline))
461 void *qht_lookup__slowpath(struct qht_bucket *b, qht_lookup_func_t func,
462 const void *userp, uint32_t hash)
463 {
464 unsigned int version;
465 void *ret;
466
467 do {
468 version = seqlock_read_begin(&b->sequence);
469 ret = qht_do_lookup(b, func, userp, hash);
470 } while (seqlock_read_retry(&b->sequence, version));
471 return ret;
472 }
473
474 void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp,
475 uint32_t hash)
476 {
477 struct qht_bucket *b;
478 struct qht_map *map;
479 unsigned int version;
480 void *ret;
481
482 map = atomic_rcu_read(&ht->map);
483 b = qht_map_to_bucket(map, hash);
484
485 version = seqlock_read_begin(&b->sequence);
486 ret = qht_do_lookup(b, func, userp, hash);
487 if (likely(!seqlock_read_retry(&b->sequence, version))) {
488 return ret;
489 }
490 /*
491 * Removing the do/while from the fastpath gives a 4% perf. increase when
492 * running a 100%-lookup microbenchmark.
493 */
494 return qht_lookup__slowpath(b, func, userp, hash);
495 }
496
497 /* call with head->lock held */
498 static bool qht_insert__locked(struct qht *ht, struct qht_map *map,
499 struct qht_bucket *head, void *p, uint32_t hash,
500 bool *needs_resize)
501 {
502 struct qht_bucket *b = head;
503 struct qht_bucket *prev = NULL;
504 struct qht_bucket *new = NULL;
505 int i;
506
507 do {
508 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
509 if (b->pointers[i]) {
510 if (unlikely(b->pointers[i] == p)) {
511 return false;
512 }
513 } else {
514 goto found;
515 }
516 }
517 prev = b;
518 b = b->next;
519 } while (b);
520
521 b = qemu_memalign(QHT_BUCKET_ALIGN, sizeof(*b));
522 memset(b, 0, sizeof(*b));
523 new = b;
524 i = 0;
525 atomic_inc(&map->n_added_buckets);
526 if (unlikely(qht_map_needs_resize(map)) && needs_resize) {
527 *needs_resize = true;
528 }
529
530 found:
531 /* found an empty key: acquire the seqlock and write */
532 seqlock_write_begin(&head->sequence);
533 if (new) {
534 atomic_rcu_set(&prev->next, b);
535 }
536 b->hashes[i] = hash;
537 atomic_set(&b->pointers[i], p);
538 seqlock_write_end(&head->sequence);
539 return true;
540 }
541
542 static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht)
543 {
544 struct qht_map *map;
545
546 /*
547 * If the lock is taken it probably means there's an ongoing resize,
548 * so bail out.
549 */
550 if (qemu_mutex_trylock(&ht->lock)) {
551 return;
552 }
553 map = ht->map;
554 /* another thread might have just performed the resize we were after */
555 if (qht_map_needs_resize(map)) {
556 struct qht_map *new = qht_map_create(map->n_buckets * 2);
557
558 qht_map_lock_buckets(map);
559 qht_do_resize(ht, new);
560 qht_map_unlock_buckets(map);
561 }
562 qemu_mutex_unlock(&ht->lock);
563 }
564
565 bool qht_insert(struct qht *ht, void *p, uint32_t hash)
566 {
567 struct qht_bucket *b;
568 struct qht_map *map;
569 bool needs_resize = false;
570 bool ret;
571
572 /* NULL pointers are not supported */
573 qht_debug_assert(p);
574
575 b = qht_bucket_lock__no_stale(ht, hash, &map);
576 ret = qht_insert__locked(ht, map, b, p, hash, &needs_resize);
577 qht_bucket_debug__locked(b);
578 qemu_spin_unlock(&b->lock);
579
580 if (unlikely(needs_resize) && ht->mode & QHT_MODE_AUTO_RESIZE) {
581 qht_grow_maybe(ht);
582 }
583 return ret;
584 }
585
586 static inline bool qht_entry_is_last(struct qht_bucket *b, int pos)
587 {
588 if (pos == QHT_BUCKET_ENTRIES - 1) {
589 if (b->next == NULL) {
590 return true;
591 }
592 return b->next->pointers[0] == NULL;
593 }
594 return b->pointers[pos + 1] == NULL;
595 }
596
597 static void
598 qht_entry_move(struct qht_bucket *to, int i, struct qht_bucket *from, int j)
599 {
600 qht_debug_assert(!(to == from && i == j));
601 qht_debug_assert(to->pointers[i]);
602 qht_debug_assert(from->pointers[j]);
603
604 to->hashes[i] = from->hashes[j];
605 atomic_set(&to->pointers[i], from->pointers[j]);
606
607 from->hashes[j] = 0;
608 atomic_set(&from->pointers[j], NULL);
609 }
610
611 /*
612 * Find the last valid entry in @head, and swap it with @orig[pos], which has
613 * just been invalidated.
614 */
615 static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)
616 {
617 struct qht_bucket *b = orig;
618 struct qht_bucket *prev = NULL;
619 int i;
620
621 if (qht_entry_is_last(orig, pos)) {
622 orig->hashes[pos] = 0;
623 atomic_set(&orig->pointers[pos], NULL);
624 return;
625 }
626 do {
627 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
628 if (b->pointers[i]) {
629 continue;
630 }
631 if (i > 0) {
632 return qht_entry_move(orig, pos, b, i - 1);
633 }
634 qht_debug_assert(prev);
635 return qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
636 }
637 prev = b;
638 b = b->next;
639 } while (b);
640 /* no free entries other than orig[pos], so swap it with the last one */
641 qht_entry_move(orig, pos, prev, QHT_BUCKET_ENTRIES - 1);
642 }
643
644 /* call with b->lock held */
645 static inline
646 bool qht_remove__locked(struct qht_map *map, struct qht_bucket *head,
647 const void *p, uint32_t hash)
648 {
649 struct qht_bucket *b = head;
650 int i;
651
652 do {
653 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
654 void *q = b->pointers[i];
655
656 if (unlikely(q == NULL)) {
657 return false;
658 }
659 if (q == p) {
660 qht_debug_assert(b->hashes[i] == hash);
661 seqlock_write_begin(&head->sequence);
662 qht_bucket_remove_entry(b, i);
663 seqlock_write_end(&head->sequence);
664 return true;
665 }
666 }
667 b = b->next;
668 } while (b);
669 return false;
670 }
671
672 bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
673 {
674 struct qht_bucket *b;
675 struct qht_map *map;
676 bool ret;
677
678 /* NULL pointers are not supported */
679 qht_debug_assert(p);
680
681 b = qht_bucket_lock__no_stale(ht, hash, &map);
682 ret = qht_remove__locked(map, b, p, hash);
683 qht_bucket_debug__locked(b);
684 qemu_spin_unlock(&b->lock);
685 return ret;
686 }
687
688 static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
689 qht_iter_func_t func, void *userp)
690 {
691 int i;
692
693 do {
694 for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
695 if (b->pointers[i] == NULL) {
696 return;
697 }
698 func(ht, b->pointers[i], b->hashes[i], userp);
699 }
700 b = b->next;
701 } while (b);
702 }
703
704 /* call with all of the map's locks held */
705 static inline void qht_map_iter__all_locked(struct qht *ht, struct qht_map *map,
706 qht_iter_func_t func, void *userp)
707 {
708 size_t i;
709
710 for (i = 0; i < map->n_buckets; i++) {
711 qht_bucket_iter(ht, &map->buckets[i], func, userp);
712 }
713 }
714
715 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
716 {
717 struct qht_map *map;
718
719 map = atomic_rcu_read(&ht->map);
720 qht_map_lock_buckets(map);
721 /* Note: ht here is merely for carrying ht->mode; ht->map won't be read */
722 qht_map_iter__all_locked(ht, map, func, userp);
723 qht_map_unlock_buckets(map);
724 }
725
726 static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
727 {
728 struct qht_map *new = userp;
729 struct qht_bucket *b = qht_map_to_bucket(new, hash);
730
731 /* no need to acquire b->lock because no thread has seen this map yet */
732 qht_insert__locked(ht, new, b, p, hash, NULL);
733 }
734
735 /*
736 * Call with ht->lock and all bucket locks held.
737 *
738 * Creating the @new map here would add unnecessary delay while all the locks
739 * are held--holding up the bucket locks is particularly bad, since no writes
740 * can occur while these are held. Thus, we let callers create the new map,
741 * hopefully without the bucket locks held.
742 */
743 static void qht_do_resize(struct qht *ht, struct qht_map *new)
744 {
745 struct qht_map *old;
746
747 old = ht->map;
748 g_assert_cmpuint(new->n_buckets, !=, old->n_buckets);
749
750 qht_map_iter__all_locked(ht, old, qht_map_copy, new);
751 qht_map_debug__all_locked(new);
752
753 atomic_rcu_set(&ht->map, new);
754 call_rcu(old, qht_map_destroy, rcu);
755 }
756
757 bool qht_resize(struct qht *ht, size_t n_elems)
758 {
759 size_t n_buckets = qht_elems_to_buckets(n_elems);
760 size_t ret = false;
761
762 qemu_mutex_lock(&ht->lock);
763 if (n_buckets != ht->map->n_buckets) {
764 struct qht_map *new;
765 struct qht_map *old = ht->map;
766
767 new = qht_map_create(n_buckets);
768 qht_map_lock_buckets(old);
769 qht_do_resize(ht, new);
770 qht_map_unlock_buckets(old);
771 ret = true;
772 }
773 qemu_mutex_unlock(&ht->lock);
774
775 return ret;
776 }
777
778 /* pass @stats to qht_statistics_destroy() when done */
779 void qht_statistics_init(struct qht *ht, struct qht_stats *stats)
780 {
781 struct qht_map *map;
782 int i;
783
784 map = atomic_rcu_read(&ht->map);
785
786 stats->head_buckets = map->n_buckets;
787 stats->used_head_buckets = 0;
788 stats->entries = 0;
789 qdist_init(&stats->chain);
790 qdist_init(&stats->occupancy);
791
792 for (i = 0; i < map->n_buckets; i++) {
793 struct qht_bucket *head = &map->buckets[i];
794 struct qht_bucket *b;
795 unsigned int version;
796 size_t buckets;
797 size_t entries;
798 int j;
799
800 do {
801 version = seqlock_read_begin(&head->sequence);
802 buckets = 0;
803 entries = 0;
804 b = head;
805 do {
806 for (j = 0; j < QHT_BUCKET_ENTRIES; j++) {
807 if (atomic_read(&b->pointers[j]) == NULL) {
808 break;
809 }
810 entries++;
811 }
812 buckets++;
813 b = atomic_rcu_read(&b->next);
814 } while (b);
815 } while (seqlock_read_retry(&head->sequence, version));
816
817 if (entries) {
818 qdist_inc(&stats->chain, buckets);
819 qdist_inc(&stats->occupancy,
820 (double)entries / QHT_BUCKET_ENTRIES / buckets);
821 stats->used_head_buckets++;
822 stats->entries += entries;
823 } else {
824 qdist_inc(&stats->occupancy, 0);
825 }
826 }
827 }
828
829 void qht_statistics_destroy(struct qht_stats *stats)
830 {
831 qdist_destroy(&stats->occupancy);
832 qdist_destroy(&stats->chain);
833 }