accel/tcg: Make PageFlagsNodes' start and last immutable
v2 cover accel/tcg: Make PageFlagsNodes' start and last immutable
v1: https://lore.kernel.org/qemu-devel/[email protected]/T/#t
v1 -> v2: Use a new approach: immutability.
Hi,
This series fixes the ancient vma-pthread test failures. It was sparked by a bug report by wasmtime project. The patch seems to fix all issues - I could run vma-pthread for an hour, while previously it would fail reliably in under a minute.
Best regards,
Ilya
Ilya Leoshkevich (3):
accel/tcg: Make PageFlagsNodes' start and last immutable tests/tcg/multiarch: Improve mutator randomness Revert "tests/tcg: skip the vma-pthread test on CI"
accel/tcg/user-exec.c | 37 ++++++++++++++++------------- tests/tcg/multiarch/Makefile.target | 9 ------- tests/tcg/multiarch/vma-pthread.c | 3 ++- 3 files changed, 23 insertions(+), 26 deletions(-)
Signature · 1 line
2.54.0
PATCH v2 1/3 accel/tcg: Make PageFlagsNodes' start and last immutable
page_check_range() may race with pageflags_set_clear() as follows:
T1 T2
------------------------------------- --------------------------------
p = pageflags_find(start, last);
interval_tree_remove(&p->itree, ...);
p->itree.start = last + 1;
if (start < p->itree.start) {
ret = false;
interval_tree_insert(&p->itree, ...);leading to errors like
fail indirect write 0x72f0a659aff0 (Bad address)
in vma-pthread test. I am able to reliably reproduce this on a machine with 32 SMT threads as follows in about 25 seconds:
jobs=32; \
seq "$jobs" | \
time -p parallel \
--jobs="$jobs" \
--halt=now,done=1 \
--ungroup \
'
_={};
while ./qemu-s390x tests/tcg/s390x-linux-user/vma-pthread; do
printf .;
done
'Also wasmtime project reported a similar failure pattern in their CI [1] with a similar reproducer [2].
There are other races like this. In general, region bounds mutating underneath the reader are very hard to reason about. So fix this by preventing mutations and creating copies instead. Use RCU guards in readers to avoid uses-after-frees.
Now, when the reader finds a node, it may fearlessly access its fields and be certain that at some point in time the respective region had the respective bounds and permissions. The downside is slightly more expensive mprotect(), but complexity reduction is worth it.
Lockless field accesses should probably be wrapped in qatomic_read(), but this is a pre-existing issue, so do not change it here.
[1] https://github.com/bytecodealliance/wasmtime/issues/10000
[2] https://gist.github.com/alexcrichton/f14f23a892ffb9df2522754572d51b1c
--- accel/tcg/user-exec.c | 37 +++++++++++++++++++++---------------- 1 file changed, 21 insertions(+), 16 deletions(-)
accel/tcg/user-exec.c +21 -16
@@ -239,13 +239,16 @@ void page_dump(FILE *f)int page_get_flags (vaddr address) { -PageFlagsNode *p =pageflags_find (address, address); +PageFlagsNode *p; + +RCU_READ_LOCK_GUARD ();/* * See util/interval-tree.c re lockless lookups: no false positives but * there are false negatives. If we find nothing, retry with the mmap * lock acquired. */ + p =pageflags_find (address, address);if (p) {return p->flags; }
@@ -301,15 +304,15 @@ static void pageflags_create_merge(vaddr start, vaddr last, int flags)if (prev) {if (next) { - prev->itree.last = next->itree.last; +pageflags_create (prev->itree.start, next->itree.last, flags);g_free_rcu (next, rcu); }else { - prev->itree.last = last; +pageflags_create (prev->itree.start, last, flags); } -interval_tree_insert (&prev->itree, &pageflags_root); +g_free_rcu (prev, rcu); }else if (next) { - next->itree.start = start; -interval_tree_insert (&next->itree, &pageflags_root); +pageflags_create (start, next->itree.last, flags); +g_free_rcu (next, rcu); }else {pageflags_create (start, last, flags); }
@@ -371,8 +374,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,if (set_flags != merge_flags) {if (p_start < start) {interval_tree_remove (&p->itree, &pageflags_root); - p->itree.last = start -1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (p_start, start -1 , p_flags); +g_free_rcu (p, rcu);if (last < p_last) {if (merge_flags &PAGE_VALID ) {
@@ -394,11 +397,11 @@ static bool pageflags_set_clear(vaddr start, vaddr last, }if (last < p_last) {interval_tree_remove (&p->itree, &pageflags_root); - p->itree.start = last +1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (last +1 , p_last, p_flags);if (merge_flags &PAGE_VALID ) {pageflags_create (start, last, merge_flags); } +g_free_rcu (p, rcu); }else {if (merge_flags &PAGE_VALID ) { p->flags = merge_flags;
@@ -419,8 +422,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,if (set_flags == p_flags) {if (start < p_start) {interval_tree_remove (&p->itree, &pageflags_root); - p->itree.start = start; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (start, p_last, p_flags); +g_free_rcu (p, rcu); }if (p_last < last) { start = p_last +1 ;
@@ -432,8 +435,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,/* Maybe split out head and/or tail ranges with the original flags. */ interval_tree_remove (&p->itree, &pageflags_root);if (p_start < start) { - p->itree.last = start -1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (p_start, start -1 , p_flags); +g_free_rcu (p, rcu);if (p_last < last) { goto restart;
@@ -442,8 +445,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,pageflags_create (last +1 , p_last, p_flags); } }else if (last < p_last) { - p->itree.start = last +1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (last +1 , p_last, p_flags); +g_free_rcu (p, rcu); }else {g_free_rcu (p, rcu); goto restart;
@@ -505,6 +508,8 @@ bool page_check_range(vaddr start, vaddr len, int flags)return false;/* wrap around */ } +RCU_READ_LOCK_GUARD (); + locked =have_mmap_lock ();while (true) {PageFlagsNode *p =pageflags_find (start, last);
Signature · 1 line
2.54.0
Quoted 157 lines · Ilya Leoshkevich
page_check_range()may race withpageflags_set_clear()as follows:T1 T2 ------------------------------------- -------------------------------- p = pageflags_find(start, last); interval_tree_remove(&p->itree, ...); p->itree.start = last + 1; if (start < p->itree.start) { ret = false; interval_tree_insert(&p->itree, ...);leading to errors like
fail indirect write 0x72f0a659aff0 (Bad address)in vma-pthread test. I am able to reliably reproduce this on a machine with 32 SMT threads as follows in about 25 seconds:
jobs=32; \ seq "$jobs" | \ time -p parallel \ --jobs="$jobs" \ --halt=now,done=1 \ --ungroup \ ' _={}; while ./qemu-s390x tests/tcg/s390x-linux-user/vma-pthread; do printf .; done 'Also wasmtime project reported a similar failure pattern in their CI [1] with a similar reproducer [2].
There are other races like this. In general, region bounds mutating underneath the reader are very hard to reason about. So fix this by preventing mutations and creating copies instead. Use RCU guards in readers to avoid uses-after-frees.
Now, when the reader finds a node, it may fearlessly access its fields and be certain that at some point in time the respective region had the respective bounds and permissions. The downside is slightly more expensive
mprotect(), but complexity reduction is worth it.Lockless field accesses should probably be wrapped in
qatomic_read(), but this is a pre-existing issue, so do not change it here.[1] https://github.com/bytecodealliance/wasmtime/issues/10000
[2] https://gist.github.com/alexcrichton/f14f23a892ffb9df2522754572d51b1cSigned-off-by Ilya Leoshkevich <[email protected]>--- accel/tcg/user-exec.c | 37 +++++++++++++++++++++---------------- 1 file changed, 21 insertions(+), 16 deletions(-)accel/tcg/user-exec.c +19
-16@@ -239,13 +239,16 @@ void page_dump(FILE *f)int page_get_flags (vaddr address) { -PageFlagsNode *p =pageflags_find (address, address); +PageFlagsNode *p; + +RCU_READ_LOCK_GUARD ();/* * See util/interval-tree.c re lockless lookups: no false positives but * there are false negatives. If we find nothing, retry with the mmap * lock acquired. */ + p =pageflags_find (address, address);if (p) {return p->flags; }@@ -301,15 +304,15 @@ static void pageflags_create_merge(vaddr start, vaddr last, int flags)if (prev) {if (next) { - prev->itree.last = next->itree.last; +pageflags_create (prev->itree.start, next->itree.last, flags);g_free_rcu (next, rcu); }else { - prev->itree.last = last; +pageflags_create (prev->itree.start, last, flags); } -interval_tree_insert (&prev->itree, &pageflags_root); +g_free_rcu (prev, rcu); }else if (next) { - next->itree.start = start; -interval_tree_insert (&next->itree, &pageflags_root); +pageflags_create (start, next->itree.last, flags); +g_free_rcu (next, rcu); }else {pageflags_create (start, last, flags); }@@ -371,8 +374,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,if (set_flags != merge_flags) {if (p_start < start) {interval_tree_remove (&p->itree, &pageflags_root); - p->itree.last = start -1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (p_start, start -1 , p_flags); +g_free_rcu (p, rcu);if (last < p_last) {if (merge_flags &PAGE_VALID ) {@@ -394,11 +397,11 @@ static bool pageflags_set_clear(vaddr start, vaddr last, }if (last < p_last) {interval_tree_remove (&p->itree, &pageflags_root); - p->itree.start = last +1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (last +1 , p_last, p_flags);if (merge_flags &PAGE_VALID ) {pageflags_create (start, last, merge_flags); } +g_free_rcu (p, rcu); }else {if (merge_flags &PAGE_VALID ) { p->flags = merge_flags;@@ -419,8 +422,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,if (set_flags == p_flags) {if (start < p_start) {interval_tree_remove (&p->itree, &pageflags_root); - p->itree.start = start; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (start, p_last, p_flags); +g_free_rcu (p, rcu); }if (p_last < last) { start = p_last +1 ;@@ -432,8 +435,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,/* Maybe split out head and/or tail ranges with the original flags. */ interval_tree_remove (&p->itree, &pageflags_root);if (p_start < start) { - p->itree.last = start -1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (p_start, start -1 , p_flags); +g_free_rcu (p, rcu);if (p_last < last) { goto restart;@@ -442,8 +445,8 @@ static bool pageflags_set_clear(vaddr start, vaddr last,pageflags_create (last +1 , p_last, p_flags); } }else if (last < p_last) { - p->itree.start = last +1 ; -interval_tree_insert (&p->itree, &pageflags_root); +pageflags_create (last +1 , p_last, p_flags); +g_free_rcu (p, rcu); }else {g_free_rcu (p, rcu); goto restart;
accel/tcg/user-exec.c bool page_check_range(vaddr start, vaddr len, int flags) · line 515
Quoted 8 lines
accel/tcg/user-exec.c +2
-0@@ -505,6 +508,8 @@ bool page_check_range(vaddr start, vaddr len, int flags)return false;/* wrap around */ } +RCU_READ_LOCK_GUARD (); + locked =have_mmap_lock ();while (true) {PageFlagsNode *p =pageflags_find (start, last);
Sorry, I forgot to include the tags:
Quoted 47 lines · Ilya Leoshkevich
page_check_range()may race withpageflags_set_clear()as follows:T1 T2 ------------------------------------- -------------------------------- p = pageflags_find(start, last); interval_tree_remove(&p->itree, ...); p->itree.start = last + 1; if (start < p->itree.start) { ret = false; interval_tree_insert(&p->itree, ...);leading to errors like
fail indirect write 0x72f0a659aff0 (Bad address)in vma-pthread test. I am able to reliably reproduce this on a machine with 32 SMT threads as follows in about 25 seconds:
jobs=32; \ seq "$jobs" | \ time -p parallel \ --jobs="$jobs" \ --halt=now,done=1 \ --ungroup \ ' _={}; while ./qemu-s390x tests/tcg/s390x-linux-user/vma-pthread; do printf .; done 'Also wasmtime project reported a similar failure pattern in their CI [1] with a similar reproducer [2].
There are other races like this. In general, region bounds mutating underneath the reader are very hard to reason about. So fix this by preventing mutations and creating copies instead. Use RCU guards in readers to avoid uses-after-frees.
Now, when the reader finds a node, it may fearlessly access its fields and be certain that at some point in time the respective region had the respective bounds and permissions. The downside is slightly more expensive
mprotect(), but complexity reduction is worth it.Lockless field accesses should probably be wrapped in
qatomic_read(), but this is a pre-existing issue, so do not change it here.
Quoted 8 lines
[1] https://github.com/bytecodealliance/wasmtime/issues/10000
[2] https://gist.github.com/alexcrichton/f14f23a892ffb9df2522754572d51b1cSigned-off-by Ilya Leoshkevich <[email protected]>--- accel/tcg/user-exec.c | 37 +++++++++++++++++++++---------------- 1 file changed, 21 insertions(+), 16 deletions(-)
PATCH v2 2/3 tests/tcg/multiarch: Improve mutator randomness
In reply to Ilya LeoshkevichCurrently mutators perform the same actions, because the RNG seed is derived from the current time in seconds. Mix in thread ID.
--- tests/tcg/multiarch/vma-pthread.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
tests/tcg/multiarch/vma-pthread.c +2 -1
@@ -11,6 +11,7 @@* pages, which are guaranteed to have the respective protection bit set. * Two mutator threads change the non-fixed protection bits randomly. */ +#define _GNU_SOURCE#include <assert.h> #include <fcntl.h> #include <pthread.h>
@@ -121,7 +122,7 @@ static void *thread_mutate(void *arg)unsigned int seed;int prot, ret; - seed = (unsigned int )time (NULL ); + seed = (unsigned int )time (NULL ) + (unsigned int )gettid ();for (i =0 ; i <10000 ; i++) { start_idx =rand_r (&seed) &PAGE_IDX_MASK ; end_idx =rand_r (&seed) &PAGE_IDX_MASK ;
Signature · 1 line
2.54.0
Re: [PATCH v2 2/3] tests/tcg/multiarch: Improve mutator randomness
Quoted 8 lines · Ilya Leoshkevich
Currently mutators perform the same actions, because the RNG seed is derived from the current time in seconds. Mix in thread ID.
Signed-off-by Ilya Leoshkevich <[email protected]>--- tests/tcg/multiarch/vma-pthread.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
PATCH v2 3/3 Revert "tests/tcg: skip the vma-pthread test on CI"
In reply to Ilya LeoshkevichNow that the page_check_range() race condition is fixed, let vma-pthread run on CI again.
This reverts commit 5842de51573fdbd7299ab4b33d64b7446cc07649.
--- tests/tcg/multiarch/Makefile.target | 9 --------- 1 file changed, 9 deletions(-)
tests/tcg/multiarch/Makefile.target +0 -9
@@ -60,15 +60,6 @@ tb-link: LDFLAGS+=-lpthread # code to work around the compiler. sha1: CFLAGS+=-Wno-stringop-overread -Wno-unknown-warning-option -# The vma-pthread seems very sensitive on gitlab and we currently -# don't know if its exposing a real bug or the test is flaky. -ifneq ($(GITLAB_CI),) -run-vma-pthread: vma-pthread - $(call skip-test, $<, "flaky on CI?") -run-plugin-vma-pthread-with-%: vma-pthread - $(call skip-test, $<, "flaky on CI?") -endif - run-test-mmap: test-mmap $(call run-test, test-mmap, $(QEMU) $<, $< (default))
Signature · 1 line
2.54.0
Re: [PATCH v2 3/3] Revert "tests/tcg: skip the vma-pthread test on CI"
Quoted 10 lines · Ilya Leoshkevich
Now that the
page_check_range()race condition is fixed, let vma-pthread run on CI again.This reverts commit
5842de51573fdbd7299ab4b33d64b7446cc07649.Signed-off-by Ilya Leoshkevich <[email protected]>--- tests/tcg/multiarch/Makefile.target | 9 --------- 1 file changed, 9 deletions(-)
Quoted 19 lines · Ilya Leoshkevich
v1: https://lore.kernel.org/qemu-devel/[email protected]/T/#t
v1 -> v2: Use a new approach: immutability.Hi,
This series fixes the ancient vma-pthread test failures. It was sparked by a bug report by wasmtime project. The patch seems to fix all issues - I could run vma-pthread for an hour, while previously it would fail reliably in under a minute.
Best regards,
IlyaIlya Leoshkevich (3):
accel/tcg: Make PageFlagsNodes' start and last immutable tests/tcg/multiarch: Improve mutator randomness Revert "tests/tcg: skip the vma-pthread test on CI"
Quoted 5 lines
accel/tcg/user-exec.c | 37 ++++++++++++++++------------- tests/tcg/multiarch/Makefile.target | 9 ------- tests/tcg/multiarch/vma-pthread.c | 3 ++- 3 files changed, 23 insertions(+), 26 deletions(-)
Thanks, this makes a lot of sense.
r~