tsan fixes
v2 cover tsan fixes
Changes since v1:
- call g_free_rcu on tb_jmp_cache directly, and call tcg_exec_unrealizefn after calling cpu_list_remove(cpu)
- add patch to de-const qemu_spin_destroy
- remove wrappers for qht_do_if_first_in_stripe
Thanks,
Emilio
PATCH v2 1/5 cpu: free cpu->tb_jmp_cache with RCU
Fixes the appended use-after-free. The root cause is that during tb invalidation we use CPU_FOREACH, and therefore to safely free a vCPU we must wait for an RCU grace period to elapse.
$ x86_64-linux-user/qemu-x86_64 tests/tcg/x86_64-linux-user/munmap-pthread
=================================================================
==1800604==ERROR: AddressSanitizer: heap-use-after-free on address 0x62d0005f7418 at pc 0x5593da6704eb bp 0x7f4961a7ac70 sp 0x7f4961a7ac60
READ of size 8 at 0x62d0005f7418 thread T2
#0 0x5593da6704ea in tb_jmp_cache_inval_tb ../accel/tcg/tb-maint.c:244
#1 0x5593da6704ea in do_tb_phys_invalidate ../accel/tcg/tb-maint.c:290
#2 0x5593da670631 in tb_phys_invalidate__locked ../accel/tcg/tb-maint.c:306
#3 0x5593da670631 in tb_invalidate_phys_page_range__locked ../accel/tcg/tb-maint.c:542
#4 0x5593da67106d in tb_invalidate_phys_range ../accel/tcg/tb-maint.c:614
#5 0x5593da6a64d4 in target_munmap ../linux-user/mmap.c:766
#6 0x5593da6dba05 in do_syscall1 ../linux-user/syscall.c:10105
#7 0x5593da6f564c in do_syscall ../linux-user/syscall.c:13329
#8 0x5593da49e80c in cpu_loop ../linux-user/x86_64/../i386/cpu_loop.c:233
#9 0x5593da6be28c in clone_func ../linux-user/syscall.c:6633
#10 0x7f496231cb42 in start_thread nptl/pthread_create.c:442
#11 0x7f49623ae9ff (/lib/x86_64-linux-gnu/libc.so.6+0x1269ff)0x62d0005f7418 is located 28696 bytes inside of 32768-byte region [0x62d0005f0400,0x62d0005f8400) freed by thread T148 here:
#0 0x7f49627b6460 in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
#1 0x5593da5ac057 in cpu_exec_unrealizefn ../cpu.c:180
#2 0x5593da81f851 (/home/cota/src/qemu/build/qemu-x86_64+0x484851)--- accel/tcg/cpu-exec.c | 3 +-- accel/tcg/tb-jmp-cache.h | 1 + cpu.c | 11 ++++++++++- 3 files changed, 12 insertions(+), 3 deletions(-)
accel/tcg/cpu-exec.c +1 -2
@@ -1064,13 +1064,12 @@ void tcg_exec_realizefn(CPUState *cpu, Error **errp)/* undo the initializations in reverse order */ void tcg_exec_unrealizefn (CPUState *cpu) { -qemu_plugin_vcpu_exit_hook (cpu);#ifndef CONFIG_USER_ONLY tcg_iommu_free_notifier_list (cpu);#endif /* !CONFIG_USER_ONLY */ tlb_destroy (cpu); -g_free (cpu->tb_jmp_cache); +g_free_rcu (cpu->tb_jmp_cache, rcu); }#ifndef CONFIG_USER_ONLY
accel/tcg/tb-jmp-cache.h +1 -0
@@ -18,6 +18,7 @@* a load_acquire/store_release to 'tb'. */ struct CPUJumpCache { +struct rcu_head rcu;struct {TranslationBlock *tb;#if TARGET_TB_PCREL
cpu.c +10 -1
@@ -176,11 +176,20 @@ void cpu_exec_unrealizefn(CPUState *cpu) vmstate_unregister(NULL, &vmstate_cpu_common, cpu); }#endif + +/* Call the plugin hook before clearing cpu->cpu_index in cpu_list_remove */ if (tcg_enabled ()) { -tcg_exec_unrealizefn (cpu); +qemu_plugin_vcpu_exit_hook (cpu); }cpu_list_remove (cpu); +/* +* Now that the vCPU has been removed from the RCU list, we can call +* tcg_exec_unrealizefn, which may free fields using call_rcu. +*/ +if (tcg_enabled ()) { +tcg_exec_unrealizefn (cpu); + } }/*
Signature · 1 line
2.34.1
PATCH v2 2/5 util/qht: add missing atomic_set(hashes[i])
In reply to Emilio CotaWe forgot to add this one in "a890643958 util/qht: atomically set b->hashes".
Detected with tsan.
--- util/qht.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
util/qht.c +1 -1
@@ -688,7 +688,7 @@ static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)int i;if (qht_entry_is_last (orig, pos)) { - orig->hashes[pos] =0 ; +qatomic_set (&orig->hashes[pos],0 );qatomic_set (&orig->pointers[pos],NULL );return ; }
Signature · 1 line
2.34.1
Re: [PATCH v2 2/5] util/qht: add missing atomic_set(hashes[i])
Quoted 7 lines · Emilio Cota
We forgot to add this one in "
a890643958util/qht: atomically setb->hashes".Detected with tsan.
Reviewed-by Richard Henderson <[email protected]>Reviewed-by Philippe Mathieu-Daudé <[email protected]>Signed-off-by Emilio Cota <[email protected]>
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
PATCH v2 3/5 thread: de-const qemu_spin_destroy
In reply to Emilio Cota--- include/qemu/thread.h | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)
include/qemu/thread.h +2 -3
@@ -237,11 +237,10 @@ static inline void qemu_spin_init(QemuSpin *spin)#endif } -/* const parameter because the only purpose here is the TSAN annotation */ -static inline void qemu_spin_destroy (const QemuSpin *spin) +static inline void qemu_spin_destroy (QemuSpin *spin) {#ifdef CONFIG_TSAN -__tsan_mutex_destroy ((void *)spin, __tsan_mutex_not_static); +__tsan_mutex_destroy (spin, __tsan_mutex_not_static);#endif }
Signature · 1 line
2.34.1
Re: [PATCH v2 3/5] thread: de-const qemu_spin_destroy
Quoted 12 lines · Emilio Cota
Signed-off-by Emilio Cota <[email protected]>--- include/qemu/thread.h | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)include/qemu/thread.h +0
-0@@ -237,11 +237,10 @@ static inline void qemu_spin_init(QemuSpin *spin)#endif }
include/qemu/thread.h static inline void qemu_spin_init(QemuSpin *spin) · line 245
Quoted 10 lines
include/qemu/thread.h +2
-3-/* const parameter because the only purpose here is the TSAN annotation */ -static inline void qemu_spin_destroy (const QemuSpin *spin) +static inline void qemu_spin_destroy (QemuSpin *spin) {#ifdef CONFIG_TSAN -__tsan_mutex_destroy ((void *)spin, __tsan_mutex_not_static); +__tsan_mutex_destroy (spin, __tsan_mutex_not_static);#endif }
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
PATCH v2 4/5 util/qht: use striped locks under TSAN
In reply to Emilio CotaFixes this tsan crash, easy to reproduce with any large enough program:
$ tests/unit/test-qht
1..2
ThreadSanitizer: CHECK failed: sanitizer_deadlock_detector.h:67 "((n_all_locks_)) < (((sizeof(all_locks_with_contexts_)/sizeof((all_locks_with_contexts_)[0]))))" (0x40, 0x40) (tid=1821568)
#0 __tsan::CheckUnwind() ../../../../src/libsanitizer/tsan/tsan_rtl.cpp:353 (libtsan.so.2+0x90034)
#1 __sanitizer::CheckFailed(char const*, int, char const*, unsigned long long, unsigned long long) ../../../../src/libsanitizer/sanitizer_common/sanitizer_termination.cpp:86 (libtsan.so.2+0xca555)
#2 __sanitizer::DeadlockDetectorTLS<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >::addLock(unsigned long, unsigned long, unsigned int) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector.h:67 (libtsan.so.2+0xb3616)
#3 __sanitizer::DeadlockDetectorTLS<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >::addLock(unsigned long, unsigned long, unsigned int) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector.h:59 (libtsan.so.2+0xb3616)
#4 __sanitizer::DeadlockDetector<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >::onLockAfter(__sanitizer::DeadlockDetectorTLS<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >*, unsigned long, unsigned int) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector.h:216 (libtsan.so.2+0xb3616)
#5 __sanitizer::DD::MutexAfterLock(__sanitizer::DDCallback*, __sanitizer::DDMutex*, bool, bool) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector1.cpp:169 (libtsan.so.2+0xb3616)
#6 __tsan::MutexPostLock(__tsan::ThreadState*, unsigned long, unsigned long, unsigned int, int) ../../../../src/libsanitizer/tsan/tsan_rtl_mutex.cpp:200 (libtsan.so.2+0xa3382)
#7 __tsan_mutex_post_lock ../../../../src/libsanitizer/tsan/tsan_interface_ann.cpp:384 (libtsan.so.2+0x76bc3)
#8 qemu_spin_lock /home/cota/src/qemu/include/qemu/thread.h:259 (test-qht+0x44a97)
#9 qht_map_lock_buckets ../util/qht.c:253 (test-qht+0x44a97)
#10 do_qht_iter ../util/qht.c:809 (test-qht+0x45f33)
#11 qht_iter ../util/qht.c:821 (test-qht+0x45f33)
#12 iter_check ../tests/unit/test-qht.c:121 (test-qht+0xe473)
#13 qht_do_test ../tests/unit/test-qht.c:202 (test-qht+0xe473)
#14 qht_test ../tests/unit/test-qht.c:240 (test-qht+0xe7c1)
#15 test_default ../tests/unit/test-qht.c:246 (test-qht+0xe828)
#16 <null> <null> (libglib-2.0.so.0+0x7daed)
#17 <null> <null> (libglib-2.0.so.0+0x7d80a)
#18 <null> <null> (libglib-2.0.so.0+0x7d80a)
#19 g_test_run_suite <null> (libglib-2.0.so.0+0x7dfe9)
#20 g_test_run <null> (libglib-2.0.so.0+0x7e055)
#21 main ../tests/unit/test-qht.c:259 (test-qht+0xd2c6)
#22 __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58 (libc.so.6+0x29d8f)
#23 __libc_start_main_impl ../csu/libc-start.c:392 (libc.so.6+0x29e3f)
#24 _start <null> (test-qht+0xdb44)--- util/qht.c | 101 +++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 87 insertions(+), 14 deletions(-)
util/qht.c +87 -14
@@ -151,6 +151,22 @@ struct qht_bucket {QEMU_BUILD_BUG_ON (sizeof (struct qht_bucket ) >QHT_BUCKET_ALIGN ); +/* +* Under TSAN, we use striped locks instead of one lock per bucket chain. +* This avoids crashing under TSAN, since TSAN aborts the program if more than +* 64 locks are held (this is a hardcoded limit in TSAN). +* When resizing a QHT we grab all the buckets' locks, which can easily +* go over TSAN's limit. By using striped locks, we avoid this problem. +* +* Note: this number must be a power of two for easy index computation. +*/ +#define QHT_TSAN_BUCKET_LOCKS_BITS 4 +#define QHT_TSAN_BUCKET_LOCKS (1 << QHT_TSAN_BUCKET_LOCKS_BITS) + +struct qht_tsan_lock { +QemuSpin lock; +}QEMU_ALIGNED (QHT_BUCKET_ALIGN ); +/** * struct qht_map - structure to track an array of buckets * @rcu: used by RCU. Keep it as the top field in the struct to help valgrind
@@ -160,6 +176,7 @@ QEMU_BUILD_BUG_ON(sizeof(struct qht_bucket) > QHT_BUCKET_ALIGN);* @n_added_buckets: number of added (i.e. "non-head") buckets * @n_added_buckets_threshold: threshold to trigger an upward resize once the * number of added buckets surpasses it. +* @tsan_bucket_locks: Array of striped locks to be used only under TSAN. * * Buckets are tracked in what we call a "map", i.e. this structure. */
@@ -169,6 +186,9 @@ struct qht_map {size_t n_buckets;size_t n_added_buckets;size_t n_added_buckets_threshold; +#ifdef CONFIG_TSAN +struct qht_tsan_lock tsan_bucket_locks[QHT_TSAN_BUCKET_LOCKS ]; +#endif };/* trigger a resize when n_added_buckets > n_buckets / div */
@@ -229,10 +249,62 @@ static inline size_t qht_elems_to_buckets(size_t n_elems)return pow2ceil (n_elems /QHT_BUCKET_ENTRIES ); } -static inline void qht_head_init (struct qht_bucket *b) +/* +* When using striped locks (i.e. under TSAN), we have to be careful not +* to operate on the same lock twice (e.g. when iterating through all buckets). +* We achieve this by operating only on each stripe's first matching lock. +*/ +static inline void qht_do_if_first_in_stripe (const struct qht_map *map, +struct qht_bucket *b, +void (*func)(QemuSpin *spin)) +{ +#ifdef CONFIG_TSAN +unsigned long bucket_idx = b - map->buckets; +bool is_first_in_stripe = (bucket_idx >>QHT_TSAN_BUCKET_LOCKS_BITS ) ==0 ; +if (is_first_in_stripe) { +unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS -1 ); +func (&map->tsan_bucket_locks[lock_idx]); + } +#else +func (&b->lock); +#endif +} + +static inline void qht_bucket_lock_destroy (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_do_if_first_in_stripe (map, b, qemu_spin_destroy); +} + +static inline void qht_bucket_lock_do (const struct qht_map *map, +struct qht_bucket *b, +void (*func)(QemuSpin *lock)) +{ +#ifdef CONFIG_TSAN +unsigned long bucket_idx = b - map->buckets; +unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS -1 ); +func (&map->tsan_bucket_locks[lock_idx]); +#else +func (&b->lock); +#endif +} + +static inline void qht_bucket_lock (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_bucket_lock_do (map, b, qemu_spin_lock); +} + +static inline void qht_bucket_unlock (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_bucket_lock_do (map, b, qemu_spin_unlock); +} + +static inline void qht_head_init (struct qht_map *map,struct qht_bucket *b) {memset (b,0 ,sizeof (*b)); -qemu_spin_init (&b->lock); +qht_do_if_first_in_stripe (map, b, qemu_spin_init);seqlock_init (&b->sequence); }
@@ -250,7 +322,7 @@ static void qht_map_lock_buckets(struct qht_map *map)for (i =0 ; i < map->n_buckets; i++) {struct qht_bucket *b = &map->buckets[i]; -qemu_spin_lock (&b->lock); +qht_do_if_first_in_stripe (map, b, qemu_spin_lock); } }
@@ -261,7 +333,7 @@ static void qht_map_unlock_buckets(struct qht_map *map)for (i =0 ; i < map->n_buckets; i++) {struct qht_bucket *b = &map->buckets[i]; -qemu_spin_unlock (&b->lock); +qht_do_if_first_in_stripe (map, b, qemu_spin_unlock); } }
@@ -308,7 +380,7 @@ void qht_map_lock_buckets__no_stale(struct qht *ht, struct qht_map **pmap)* Get a head bucket and lock it, making sure its parent map is not stale. * @pmap is filled with a pointer to the bucket's parent map. * -* Unlock with qemu_spin_unlock(&b->lock). +* Unlock with qht_bucket_unlock. * * Note: callers cannot have ht->lock held. */
@@ -322,18 +394,18 @@ struct qht_bucket *qht_bucket_lock__no_stale(struct qht *ht, uint32_t hash, map =qatomic_rcu_read (&ht->map); b =qht_map_to_bucket (map, hash); -qemu_spin_lock (&b->lock); +qht_bucket_lock (map, b);if (likely (!qht_map_is_stale__locked (ht, map))) { *pmap = map;return b; } -qemu_spin_unlock (&b->lock); +qht_bucket_unlock (map, b);/* we raced with a resize; acquire ht->lock to see the updated ht->map */ qht_lock (ht); map = ht->map; b =qht_map_to_bucket (map, hash); -qemu_spin_lock (&b->lock); +qht_bucket_lock (map, b);qht_unlock (ht); *pmap = map;return b;
@@ -345,12 +417,13 @@ static inline bool qht_map_needs_resize(const struct qht_map *map) map->n_added_buckets_threshold; } -static inline void qht_chain_destroy (const struct qht_bucket *head) +static inline void qht_chain_destroy (const struct qht_map *map, +struct qht_bucket *head) {struct qht_bucket *curr = head->next;struct qht_bucket *prev; -qemu_spin_destroy (&head->lock); +qht_do_if_first_in_stripe (map, head, qemu_spin_destroy);while (curr) { prev = curr; curr = curr->next;
@@ -364,7 +437,7 @@ static void qht_map_destroy(struct qht_map *map)size_t i;for (i =0 ; i < map->n_buckets; i++) { -qht_chain_destroy (&map->buckets[i]); +qht_chain_destroy (map, &map->buckets[i]); }qemu_vfree (map->buckets);g_free (map);
@@ -390,7 +463,7 @@ static struct qht_map *qht_map_create(size_t n_buckets) map->buckets =qemu_memalign (QHT_BUCKET_ALIGN ,sizeof (*map->buckets) * n_buckets);for (i =0 ; i < n_buckets; i++) { -qht_head_init (&map->buckets[i]); +qht_head_init (map, &map->buckets[i]); }return map; }
@@ -638,7 +711,7 @@ bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing) b =qht_bucket_lock__no_stale (ht, hash, &map); prev =qht_insert__locked (ht, map, b, p, hash, &needs_resize);qht_bucket_debug__locked (b); -qemu_spin_unlock (&b->lock); +qht_bucket_unlock (map, b);if (unlikely (needs_resize) && ht->mode &QHT_MODE_AUTO_RESIZE ) {qht_grow_maybe (ht);
@@ -749,7 +822,7 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash) b =qht_bucket_lock__no_stale (ht, hash, &map); ret =qht_remove__locked (b, p, hash);qht_bucket_debug__locked (b); -qemu_spin_unlock (&b->lock); +qht_bucket_unlock (map, b);return ret; }
Signature · 1 line
2.34.1
Re: [PATCH v2 4/5] util/qht: use striped locks under TSAN
Quoted 91 lines · Emilio Cota
Fixes this tsan crash, easy to reproduce with any large enough program:
$ tests/unit/test-qht 1..2 ThreadSanitizer: CHECK failed: sanitizer_deadlock_detector.h:67 "((n_all_locks_)) < (((sizeof(all_locks_with_contexts_)/sizeof((all_locks_with_contexts_)[0]))))" (0x40, 0x40) (tid=1821568) #0 __tsan::CheckUnwind() ../../../../src/libsanitizer/tsan/tsan_rtl.cpp:353 (libtsan.so.2+0x90034) #1 __sanitizer::CheckFailed(char const*, int, char const*, unsigned long long, unsigned long long) ../../../../src/libsanitizer/sanitizer_common/sanitizer_termination.cpp:86 (libtsan.so.2+0xca555) #2 __sanitizer::DeadlockDetectorTLS<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >::addLock(unsigned long, unsigned long, unsigned int) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector.h:67 (libtsan.so.2+0xb3616) #3 __sanitizer::DeadlockDetectorTLS<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >::addLock(unsigned long, unsigned long, unsigned int) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector.h:59 (libtsan.so.2+0xb3616) #4 __sanitizer::DeadlockDetector<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >::onLockAfter(__sanitizer::DeadlockDetectorTLS<__sanitizer::TwoLevelBitVector<1ul, __sanitizer::BasicBitVector<unsigned long> > >*, unsigned long, unsigned int) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector.h:216 (libtsan.so.2+0xb3616) #5 __sanitizer::DD::MutexAfterLock(__sanitizer::DDCallback*, __sanitizer::DDMutex*, bool, bool) ../../../../src/libsanitizer/sanitizer_common/sanitizer_deadlock_detector1.cpp:169 (libtsan.so.2+0xb3616) #6 __tsan::MutexPostLock(__tsan::ThreadState*, unsigned long, unsigned long, unsigned int, int) ../../../../src/libsanitizer/tsan/tsan_rtl_mutex.cpp:200 (libtsan.so.2+0xa3382) #7 __tsan_mutex_post_lock ../../../../src/libsanitizer/tsan/tsan_interface_ann.cpp:384 (libtsan.so.2+0x76bc3) #8 qemu_spin_lock /home/cota/src/qemu/include/qemu/thread.h:259 (test-qht+0x44a97) #9 qht_map_lock_buckets ../util/qht.c:253 (test-qht+0x44a97) #10 do_qht_iter ../util/qht.c:809 (test-qht+0x45f33) #11 qht_iter ../util/qht.c:821 (test-qht+0x45f33) #12 iter_check ../tests/unit/test-qht.c:121 (test-qht+0xe473) #13 qht_do_test ../tests/unit/test-qht.c:202 (test-qht+0xe473) #14 qht_test ../tests/unit/test-qht.c:240 (test-qht+0xe7c1) #15 test_default ../tests/unit/test-qht.c:246 (test-qht+0xe828) #16 <null> <null> (libglib-2.0.so.0+0x7daed) #17 <null> <null> (libglib-2.0.so.0+0x7d80a) #18 <null> <null> (libglib-2.0.so.0+0x7d80a) #19 g_test_run_suite <null> (libglib-2.0.so.0+0x7dfe9) #20 g_test_run <null> (libglib-2.0.so.0+0x7e055) #21 main ../tests/unit/test-qht.c:259 (test-qht+0xd2c6) #22 __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58 (libc.so.6+0x29d8f) #23 __libc_start_main_impl ../csu/libc-start.c:392 (libc.so.6+0x29e3f) #24 _start <null> (test-qht+0xdb44)Signed-off-by Emilio Cota <[email protected]>--- util/qht.c | 101 +++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 87 insertions(+), 14 deletions(-)util/qht.c +25
-1@@ -151,6 +151,22 @@ struct qht_bucket {QEMU_BUILD_BUG_ON (sizeof (struct qht_bucket ) >QHT_BUCKET_ALIGN ); +/* +* Under TSAN, we use striped locks instead of one lock per bucket chain. +* This avoids crashing under TSAN, since TSAN aborts the program if more than +* 64 locks are held (this is a hardcoded limit in TSAN). +* When resizing a QHT we grab all the buckets' locks, which can easily +* go over TSAN's limit. By using striped locks, we avoid this problem. +* +* Note: this number must be a power of two for easy index computation. +*/ +#define QHT_TSAN_BUCKET_LOCKS_BITS 4 +#define QHT_TSAN_BUCKET_LOCKS (1 << QHT_TSAN_BUCKET_LOCKS_BITS) + +struct qht_tsan_lock { +QemuSpin lock; +}QEMU_ALIGNED (QHT_BUCKET_ALIGN ); +/** * struct qht_map - structure to track an array of buckets * @rcu: used by RCU. Keep it as the top field in the struct to help valgrind @@ -160,6 +176,7 @@ QEMU_BUILD_BUG_ON(sizeof(struct qht_bucket) > QHT_BUCKET_ALIGN);* @n_added_buckets: number of added (i.e. "non-head") buckets * @n_added_buckets_threshold: threshold to trigger an upward resize once the * number of added buckets surpasses it. +* @tsan_bucket_locks: Array of striped locks to be used only under TSAN. * * Buckets are tracked in what we call a "map", i.e. this structure. */ @@ -169,6 +186,9 @@ struct qht_map {size_t n_buckets;size_t n_added_buckets;size_t n_added_buckets_threshold; +#ifdef CONFIG_TSAN +struct qht_tsan_lock tsan_bucket_locks[QHT_TSAN_BUCKET_LOCKS ]; +#endif };/* trigger a resize when n_added_buckets > n_buckets / div */ @@ -229,10 +249,62 @@ static inline size_t qht_elems_to_buckets(size_t n_elems)return pow2ceil (n_elems /QHT_BUCKET_ENTRIES ); } -static inline void qht_head_init (struct qht_bucket *b) +/* +* When using striped locks (i.e. under TSAN), we have to be careful not +* to operate on the same lock twice (e.g. when iterating through all buckets). +* We achieve this by operating only on each stripe's first matching lock. +*/
util/qht.c static inline size_t qht_elems_to_buckets(size_t n_elems) · line 266
Quoted 10 lines
util/qht.c +10
-0+static inline void qht_do_if_first_in_stripe (const struct qht_map *map, +struct qht_bucket *b, +void (*func)(QemuSpin *spin)) +{ +#ifdef CONFIG_TSAN +unsigned long bucket_idx = b - map->buckets; +bool is_first_in_stripe = (bucket_idx >>QHT_TSAN_BUCKET_LOCKS_BITS ) ==0 ; +if (is_first_in_stripe) { +unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS -1 ); +func (&map->tsan_bucket_locks[lock_idx]);
Hmm I ran into an issue with:
../util/qht.c:286:10: error: incompatible pointer types passing 'const struct qht_tsan_lock *' to parameter of type 'QemuSpin *' (aka 'struct QemuSpin *') [-Werror,-Wincompatible-pointer-types]
func(&map->tsan_bucket_locks[lock_idx]);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~But changing the line to:
func(&map->tsan_bucket_locks[lock_idx].lock);
still fails because:
../../util/qht.c:266:14: error: passing 'const QemuSpin *' (aka 'const struct QemuSpin *') to parameter of type 'QemuSpin *' (aka 'struct QemuSpin *') discards qualifiers [\
-Werror,-Wincompatible-pointer-types-discards-qualifiers]
func(&map->tsan_bucket_locks[lock_idx].lock);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ util/qht.c static inline size_t qht_elems_to_buckets(size_t n_elems) · line 277
Quoted 11 lines
util/qht.c +11
-0+ } +#else +func (&b->lock); +#endif +} + +static inline void qht_bucket_lock_destroy (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_do_if_first_in_stripe (map, b, qemu_spin_destroy); +}
Who is meant to be calling this?
Quoted 134 lines
util/qht.c +41
-13+ +static inline void qht_bucket_lock_do (const struct qht_map *map, +struct qht_bucket *b, +void (*func)(QemuSpin *lock)) +{ +#ifdef CONFIG_TSAN +unsigned long bucket_idx = b - map->buckets; +unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS -1 ); +func (&map->tsan_bucket_locks[lock_idx]); +#else +func (&b->lock); +#endif +} + +static inline void qht_bucket_lock (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_bucket_lock_do (map, b, qemu_spin_lock); +} + +static inline void qht_bucket_unlock (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_bucket_lock_do (map, b, qemu_spin_unlock); +} + +static inline void qht_head_init (struct qht_map *map,struct qht_bucket *b) {memset (b,0 ,sizeof (*b)); -qemu_spin_init (&b->lock); +qht_do_if_first_in_stripe (map, b, qemu_spin_init);seqlock_init (&b->sequence); }@@ -250,7 +322,7 @@ static void qht_map_lock_buckets(struct qht_map *map)for (i =0 ; i < map->n_buckets; i++) {struct qht_bucket *b = &map->buckets[i]; -qemu_spin_lock (&b->lock); +qht_do_if_first_in_stripe (map, b, qemu_spin_lock); } }@@ -261,7 +333,7 @@ static void qht_map_unlock_buckets(struct qht_map *map)for (i =0 ; i < map->n_buckets; i++) {struct qht_bucket *b = &map->buckets[i]; -qemu_spin_unlock (&b->lock); +qht_do_if_first_in_stripe (map, b, qemu_spin_unlock); } }@@ -308,7 +380,7 @@ void qht_map_lock_buckets__no_stale(struct qht *ht, struct qht_map **pmap)* Get a head bucket and lock it, making sure its parent map is not stale. * @pmap is filled with a pointer to the bucket's parent map. * -* Unlock with qemu_spin_unlock(&b->lock). +* Unlock with qht_bucket_unlock. * * Note: callers cannot have ht->lock held. */ @@ -322,18 +394,18 @@ struct qht_bucket *qht_bucket_lock__no_stale(struct qht *ht, uint32_t hash, map =qatomic_rcu_read (&ht->map); b =qht_map_to_bucket (map, hash); -qemu_spin_lock (&b->lock); +qht_bucket_lock (map, b);if (likely (!qht_map_is_stale__locked (ht, map))) { *pmap = map;return b; } -qemu_spin_unlock (&b->lock); +qht_bucket_unlock (map, b);/* we raced with a resize; acquire ht->lock to see the updated ht->map */ qht_lock (ht); map = ht->map; b =qht_map_to_bucket (map, hash); -qemu_spin_lock (&b->lock); +qht_bucket_lock (map, b);qht_unlock (ht); *pmap = map;return b;@@ -345,12 +417,13 @@ static inline bool qht_map_needs_resize(const struct qht_map *map) map->n_added_buckets_threshold; } -static inline void qht_chain_destroy (const struct qht_bucket *head) +static inline void qht_chain_destroy (const struct qht_map *map, +struct qht_bucket *head) {struct qht_bucket *curr = head->next;struct qht_bucket *prev; -qemu_spin_destroy (&head->lock); +qht_do_if_first_in_stripe (map, head, qemu_spin_destroy);while (curr) { prev = curr; curr = curr->next;@@ -364,7 +437,7 @@ static void qht_map_destroy(struct qht_map *map)size_t i;for (i =0 ; i < map->n_buckets; i++) { -qht_chain_destroy (&map->buckets[i]); +qht_chain_destroy (map, &map->buckets[i]); }qemu_vfree (map->buckets);g_free (map);@@ -390,7 +463,7 @@ static struct qht_map *qht_map_create(size_t n_buckets) map->buckets =qemu_memalign (QHT_BUCKET_ALIGN ,sizeof (*map->buckets) * n_buckets);for (i =0 ; i < n_buckets; i++) { -qht_head_init (&map->buckets[i]); +qht_head_init (map, &map->buckets[i]); }return map; }@@ -638,7 +711,7 @@ bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing) b =qht_bucket_lock__no_stale (ht, hash, &map); prev =qht_insert__locked (ht, map, b, p, hash, &needs_resize);qht_bucket_debug__locked (b); -qemu_spin_unlock (&b->lock); +qht_bucket_unlock (map, b);if (unlikely (needs_resize) && ht->mode &QHT_MODE_AUTO_RESIZE ) {qht_grow_maybe (ht);@@ -749,7 +822,7 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash) b =qht_bucket_lock__no_stale (ht, hash, &map); ret =qht_remove__locked (b, p, hash);qht_bucket_debug__locked (b); -qemu_spin_unlock (&b->lock); +qht_bucket_unlock (map, b);return ret; }
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
Re: [PATCH v2 4/5] util/qht: use striped locks under TSAN
Quoted 1 line · Alex Bennée
Emilio Cota <[email protected]> writes:
(snip)
Quoted 13 lines
util/qht.c static inline size_t qht_elems_to_buckets(size_t n_elems) · line 266
Quoted 10 lines
util/qht.c +10
-0+static inline void qht_do_if_first_in_stripe (const struct qht_map *map, +struct qht_bucket *b, +void (*func)(QemuSpin *spin)) +{ +#ifdef CONFIG_TSAN +unsigned long bucket_idx = b - map->buckets; +bool is_first_in_stripe = (bucket_idx >>QHT_TSAN_BUCKET_LOCKS_BITS ) ==0 ; +if (is_first_in_stripe) { +unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS -1 ); +func (&map->tsan_bucket_locks[lock_idx]);Hmm I ran into an issue with:
Quoted 1 line
../util/qht.c:286:10: error: incompatible pointer types passing 'const structqht_tsan_lock*' to parameter of type 'QemuSpin *' (aka 'struct QemuSpin *') [-Werror,-Wincompatible-pointer-types]
Gaah, sorry. I didn't notice this because of unrelated noise due to having to configure with --disable-werror. Fixed now by removing a bunch of const's and also using .lock.
Quoted 7 lines
util/qht.c static inline size_t qht_elems_to_buckets(size_t n_elems) · line 277
Quoted 5 lines
util/qht.c +5
-0+static inline void qht_bucket_lock_destroy (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_do_if_first_in_stripe (map, b, qemu_spin_destroy); +}Who is meant to be calling this?
Should have been removed in v2; fixed now.
I've uploaded the v3 series to https://github.com/cota/qemu/tree/tsan-v3
Please let me know if you want me to also mail it to the list. Thanks,
Emilio
Re: [PATCH v2 4/5] util/qht: use striped locks under TSAN
Quoted 32 lines · Emilio Cota
Quoted 1 line · Alex Bennée
Emilio Cota <[email protected]> writes:
(snip)
Quoted 13 lines
util/qht.c static inline size_t qht_elems_to_buckets(size_t n_elems) · line 266
Quoted 10 lines
util/qht.c +10
-0+static inline void qht_do_if_first_in_stripe (const struct qht_map *map, +struct qht_bucket *b, +void (*func)(QemuSpin *spin)) +{ +#ifdef CONFIG_TSAN +unsigned long bucket_idx = b - map->buckets; +bool is_first_in_stripe = (bucket_idx >>QHT_TSAN_BUCKET_LOCKS_BITS ) ==0 ; +if (is_first_in_stripe) { +unsigned long lock_idx = bucket_idx & (QHT_TSAN_BUCKET_LOCKS -1 ); +func (&map->tsan_bucket_locks[lock_idx]);Hmm I ran into an issue with:
Quoted 3 lines
../util/qht.c:286:10: error: incompatible pointer types passing
'const structqht_tsan_lock*' to parameter of type 'QemuSpin *' (aka 'struct QemuSpin *') [-Werror,-Wincompatible-pointer-types]Gaah, sorry. I didn't notice this because of unrelated noise due to having to configure with --disable-werror. Fixed now by removing a bunch of const's and also using .lock.
Quoted 7 lines
util/qht.c static inline size_t qht_elems_to_buckets(size_t n_elems) · line 277
Quoted 5 lines
util/qht.c +5
-0+static inline void qht_bucket_lock_destroy (const struct qht_map *map, +struct qht_bucket *b) +{ +qht_do_if_first_in_stripe (map, b, qemu_spin_destroy); +}Who is meant to be calling this?
Quoted 5 lines
Should have been removed in v2; fixed now.
I've uploaded the v3 series to https://github.com/cota/qemu/tree/tsan-v3
Please let me know if you want me to also mail it to the list.
Please do and then I can be sure I'm upto date when I rebuild the PR.
Quoted 3 lines
Thanks,
Emilio
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
PATCH v2 5/5 plugins: make qemu_plugin_user_exit's locking order consistent with fork_start's
In reply to Emilio CotaTo fix potential deadlocks as reported by tsan.
--- plugins/core.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-)
plugins/core.c +11 -5
@@ -500,10 +500,17 @@ void qemu_plugin_user_exit(void)enum qemu_plugin_event ev;CPUState *cpu; -QEMU_LOCK_GUARD (&plugin.lock); - +/* +* Locking order: we must acquire locks in an order that is consistent +* with the one in fork_start(). That is: +* - start_exclusive(), which acquires qemu_cpu_list_lock, +* must be called before acquiring plugin.lock. +* - tb_flush(), which acquires mmap_lock(), must be called +* while plugin.lock is not held. +*/ start_exclusive (); +qemu_rec_mutex_lock (&plugin.lock);/* un-register all callbacks except the final AT_EXIT one */ for (ev =0 ; ev <QEMU_PLUGIN_EV_MAX ; ev++) {if (ev !=QEMU_PLUGIN_EV_ATEXIT ) {
@@ -513,13 +520,12 @@ void qemu_plugin_user_exit(void) } } } - -tb_flush (current_cpu); -CPU_FOREACH (cpu) {qemu_plugin_disable_mem_helpers (cpu); } +qemu_rec_mutex_unlock (&plugin.lock); +tb_flush (current_cpu);end_exclusive ();/* now it's safe to handle the exit case */
Signature · 1 line
2.34.1
Re: [PATCH v2 5/5] plugins: make qemu_plugin_user_exit's locking order consistent with fork_start's
Quoted 7 lines · Emilio Cota
To fix potential deadlocks as reported by tsan.
Reviewed-by Richard Henderson <[email protected]>Signed-off-by Emilio Cota <[email protected]>--- plugins/core.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-)
Alex Bennée
AppliedQuoted 11 lines · Emilio Cota
Changes since v1:
- call
g_free_rcuontb_jmp_cachedirectly, and calltcg_exec_unrealizefnafter callingcpu_list_remove(cpu)- add patch to de-const
qemu_spin_destroy- remove wrappers for
qht_do_if_first_in_stripeThanks,
Emilio
Queued to plugins/next, as there is some intersection with plugins.
Richard,
Please shout if you want to pull this stuff in directly.
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
Quoted 12 lines · Alex Bennée
Quoted 9 lines · Emilio Cota
Changes since v1:
- call
g_free_rcuontb_jmp_cachedirectly, and calltcg_exec_unrealizefnafter callingcpu_list_remove(cpu)- add patch to de-const
qemu_spin_destroy- remove wrappers for
qht_do_if_first_in_stripe
Quoted 9 lines
Quoted 2 lines
Thanks,
EmilioQueued to plugins/next, as there is some intersection with plugins.
Richard,
Please shout if you want to pull this stuff in directly.
Please go ahead.
r~