Skip to contentSkip to conversation

accel/tcg: Make PageFlagsNodes' start and last immutable

PATCH In review Ilya Leoshkevich 3 participants 9 messages Jul 6 – Jul 7

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 7704e4017dd..55761cacf65 100644
@@ -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
#2 lore raw
Quoted 157 lines · Ilya Leoshkevich

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 +19 -16
index 7704e4017dd..55761cacf65 100644
@@ -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:

Fixes 67ff2186b0a4 ("accel/tcg: Use interval tree for user-only page tracking")
Reviewed-by on v2 1/3
#3 lore raw
In reply to Ilya Leoshkevich
Quoted 47 lines · Ilya Leoshkevich

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.

Quoted 8 lines

[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(-)
#4 lore raw

PATCH v2 2/3 tests/tcg/multiarch: Improve mutator randomness

In reply to Ilya Leoshkevich

Currently 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
index 7045da08fc4..0b8ce9751be 100644
@@ -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
Reviewed-by on v2 2/3
#5 lore raw

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.

---
 tests/tcg/multiarch/vma-pthread.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
#6 lore raw

PATCH v2 3/3 Revert "tests/tcg: skip the vma-pthread test on CI"

In reply to Ilya Leoshkevich

Now 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
index 508149d57bd..ab4bf9c5d53 100644
@@ -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
Reviewed-by on v2 3/3
#7 lore raw

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.

---
 tests/tcg/multiarch/Makefile.target | 9 ---------
 1 file changed, 9 deletions(-)
Reviewed-by on the v2 series
#8 lore raw
In reply to Ilya Leoshkevich
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,
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"

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~