[PATCH v2 0/5] tsan fixes

[PATCH v2 0/5] tsan fixes

[Emilio Cota]

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

[Emilio Cota]

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)

Signed-off-by: Emilio Cota <cota@braap.org>
---
 accel/tcg/cpu-exec.c     |  3 +--
 accel/tcg/tb-jmp-cache.h |  1 +
 cpu.c                    | 11 ++++++++++-
 3 files changed, 12 insertions(+), 3 deletions(-)

diff --git a/accel/tcg/cpu-exec.c b/accel/tcg/cpu-exec.c
index 356fe348de..6bd29227f3 100644
--- a/accel/tcg/cpu-exec.c
+++ b/accel/tcg/cpu-exec.c
@@ -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
diff --git a/accel/tcg/tb-jmp-cache.h b/accel/tcg/tb-jmp-cache.h
index ff5ffc8fc2..b3f6e78835 100644
--- a/accel/tcg/tb-jmp-cache.h
+++ b/accel/tcg/tb-jmp-cache.h
@@ -18,6 +18,7 @@
  * a load_acquire/store_release to 'tb'.
  */
 struct CPUJumpCache {
+    struct rcu_head rcu;
     struct {
         TranslationBlock *tb;
 #if TARGET_TB_PCREL
diff --git a/cpu.c b/cpu.c
index 4a7d865427..21cf809614 100644
--- a/cpu.c
+++ b/cpu.c
@@ -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);
+    }
 }
 
 /*
-- 
2.34.1

[PATCH v2 2/5] util/qht: add missing atomic_set(hashes[i])

[Emilio Cota]

We forgot to add this one in "a890643958 util/qht: atomically set b->hashes".

Detected with tsan.

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Signed-off-by: Emilio Cota <cota@braap.org>
---
 util/qht.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/util/qht.c b/util/qht.c
index 065fc501f4..15866299e6 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -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;
     }
-- 
2.34.1

Re: [PATCH v2 2/5] util/qht: add missing atomic_set(hashes[i])

[Alex Bennée]

Emilio Cota <cota@braap.org> writes:

> We forgot to add this one in "a890643958 util/qht: atomically set b->hashes".
>
> Detected with tsan.
>
> Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
> Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
> Signed-off-by: Emilio Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

-- 
Alex Bennée
Virtualisation Tech Lead @ Linaro

[PATCH v2 3/5] thread: de-const qemu_spin_destroy

[Emilio Cota]

Signed-off-by: Emilio Cota <cota@braap.org>
---
 include/qemu/thread.h | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/include/qemu/thread.h b/include/qemu/thread.h
index 7c6703bce3..7841084199 100644
--- a/include/qemu/thread.h
+++ b/include/qemu/thread.h
@@ -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
 }
 
-- 
2.34.1

Re: [PATCH v2 3/5] thread: de-const qemu_spin_destroy

[Alex Bennée]

Emilio Cota <cota@braap.org> writes:

> Signed-off-by: Emilio Cota <cota@braap.org>
> ---
>  include/qemu/thread.h | 5 ++---
>  1 file changed, 2 insertions(+), 3 deletions(-)
>
> diff --git a/include/qemu/thread.h b/include/qemu/thread.h
> index 7c6703bce3..7841084199 100644
> --- a/include/qemu/thread.h
> +++ b/include/qemu/thread.h
> @@ -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
>  }

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

-- 
Alex Bennée
Virtualisation Tech Lead @ Linaro

[PATCH v2 4/5] util/qht: use striped locks under TSAN

[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 <cota@braap.org>
---
 util/qht.c | 101 +++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 87 insertions(+), 14 deletions(-)

diff --git a/util/qht.c b/util/qht.c
index 15866299e6..70cc733d5d 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -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;
 }
 
-- 
2.34.1

Re: [PATCH v2 4/5] util/qht: use striped locks under TSAN

[Alex Bennée]

Emilio Cota <cota@braap.org> writes:

> 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 <cota@braap.org>
> ---
>  util/qht.c | 101 +++++++++++++++++++++++++++++++++++++++++++++--------
>  1 file changed, 87 insertions(+), 14 deletions(-)
>
> diff --git a/util/qht.c b/util/qht.c
> index 15866299e6..70cc733d5d 100644
> --- a/util/qht.c
> +++ b/util/qht.c
> @@ -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]);

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);                                                                                                                        
             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~            

> +    }
> +#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?

> +
> +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;
>  }


-- 
Alex Bennée
Virtualisation Tech Lead @ Linaro

Re: [PATCH v2 4/5] util/qht: use striped locks under TSAN

[Emilio Cota]

On Tue, Jan 10, 2023 at 20:58:01 +0000, Alex Bennée wrote:
> Emilio Cota <cota@braap.org> writes:
(snip)
> > +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]

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.

> > +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

[Alex Bennée]

Emilio Cota <cota@braap.org> writes:

> On Tue, Jan 10, 2023 at 20:58:01 +0000, Alex Bennée wrote:
>> Emilio Cota <cota@braap.org> writes:
> (snip)
>> > +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]
>
> 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.
>
>> > +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.

Please do and then I can be sure I'm upto date when I rebuild the PR.

> Thanks,
>
> 		Emilio


-- 
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

[Emilio Cota]

To fix potential deadlocks as reported by tsan.

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
Signed-off-by: Emilio Cota <cota@braap.org>
---
 plugins/core.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/plugins/core.c b/plugins/core.c
index ccb770a485..728bacef95 100644
--- a/plugins/core.c
+++ b/plugins/core.c
@@ -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 */
-- 
2.34.1

Re: [PATCH v2 5/5] plugins: make qemu_plugin_user_exit's locking order consistent with fork_start's

[Philippe Mathieu-Daudé]

On 9/1/23 23:49, Emilio Cota wrote:
> To fix potential deadlocks as reported by tsan.
> 
> Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
> Signed-off-by: Emilio Cota <cota@braap.org>
> ---
>   plugins/core.c | 16 +++++++++++-----
>   1 file changed, 11 insertions(+), 5 deletions(-)

Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>

Re: [PATCH v2 0/5] tsan fixes

[Alex Bennée]

Emilio Cota <cota@braap.org> writes:

> 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

Queued to plugins/next, as there is some intersection with plugins.

Richard,

Please shout if you want to pull this stuff in directly.

-- 
Alex Bennée
Virtualisation Tech Lead @ Linaro

Re: [PATCH v2 0/5] tsan fixes

[Richard Henderson]

On 1/10/23 04:55, Alex Bennée wrote:
> 
> Emilio Cota <cota@braap.org> writes:
> 
>> 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
> 
> Queued 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~