[PATCH RESEND v2 0/2] migration/xbzrle: fix two avx512 runtime issues

[PATCH RESEND v2 0/2] migration/xbzrle: fix two avx512 runtime issues

[Matheus Tavares Bernardino]

This patchset strives to fix two bugs at xvzrle when --enable-avx512 is
used: an out-of-bounds write and an invalid argument to __builtin_ctz().

Those two errors can be seen in the test suite running:

$ ../configure --target-list=aarch64-softmmu --enable-sanitizers --enable-avx512bw
$ make tests/unit/test-xbzrle && ./tests/unit/test-xbzrle

  ==5518==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x62100000b100 at pc 0x561109a7714d bp 0x7ffed712a440 sp 0x7ffed712a430
  WRITE of size 1 at 0x62100000b100 thread T0
      #0 0x561109a7714c in uleb128_encode_small ../util/cutils.c:831
      #1 0x561109b67f6a in xbzrle_encode_buffer_avx512 ../migration/xbzrle.c:275
      #2 0x5611099a7428 in test_encode_decode_overflow ../tests/unit/test-xbzrle.c:153
      #3 0x7fb2fb65a58d  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a58d)
      #4 0x7fb2fb65a333  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a333)
      #5 0x7fb2fb65aa79 in g_test_run_suite (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa79)
      #6 0x7fb2fb65aa94 in g_test_run (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa94)
      #7 0x5611099a3a23 in main ../tests/unit/test-xbzrle.c:218
      #8 0x7fb2fa78c082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
      #9 0x5611099a608d in _start (/qemu/build/tests/unit/test-xbzrle+0x28408d)
  
  0x62100000b100 is located 0 bytes to the right of 4096-byte region [0x62100000a100,0x62100000b100)
  allocated by thread T0 here:
      #0 0x7fb2fb823a06 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:153
      #1 0x7fb2fb637ef0 in g_malloc0 (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x57ef0)
  
  ../migration/xbzrle.c:265: runtime error: passing zero to ctz(), which is not a valid argument

v1: https://lore.kernel.org/qemu-devel/cover.1678199971.git.quic_mathbern@quicinc.com/
(No changes since v1, only rebased on current master)

Matheus Tavares Bernardino (2):
  migration/xbzrle: use ctz64 to avoid undefined result
  migration/xbzrle: fix out-of-bounds write with axv512

 migration/xbzrle.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

-- 
2.39.1

[PATCH RESEND v2 1/2] migration/xbzrle: use ctz64 to avoid undefined result

[Matheus Tavares Bernardino]

__builtin_ctzll() produces undefined results when the argument is 0.
This can be seen through test-xbzrle, which produces the following
warning:

../migration/xbzrle.c:265: runtime error: passing zero to ctz(), which is not a valid argument

Replace __builtin_ctzll() with our ctz64() wrapper which properly
handles 0.

Signed-off-by: Matheus Tavares Bernardino <quic_mathbern@quicinc.com>
---
 migration/xbzrle.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/migration/xbzrle.c b/migration/xbzrle.c
index 05366e86c0..21b92d4eae 100644
--- a/migration/xbzrle.c
+++ b/migration/xbzrle.c
@@ -12,6 +12,7 @@
  */
 #include "qemu/osdep.h"
 #include "qemu/cutils.h"
+#include "qemu/host-utils.h"
 #include "xbzrle.h"
 
 /*
@@ -233,7 +234,7 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
                     break;
                 }
                 never_same = false;
-                num = __builtin_ctzll(~comp);
+                num = ctz64(~comp);
                 num = (num < bytes_to_check) ? num : bytes_to_check;
                 zrun_len += num;
                 bytes_to_check -= num;
@@ -262,7 +263,7 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
                 nzrun_len += 64;
                 break;
             }
-            num = __builtin_ctzll(comp);
+            num = ctz64(comp);
             num = (num < bytes_to_check) ? num : bytes_to_check;
             nzrun_len += num;
             bytes_to_check -= num;
-- 
2.39.1

Re: [PATCH RESEND v2 1/2] migration/xbzrle: use ctz64 to avoid undefined result

[Dr. David Alan Gilbert]

* Matheus Tavares Bernardino (quic_mathbern@quicinc.com) wrote:
> __builtin_ctzll() produces undefined results when the argument is 0.
> This can be seen through test-xbzrle, which produces the following
> warning:
> 
> ../migration/xbzrle.c:265: runtime error: passing zero to ctz(), which is not a valid argument
> 
> Replace __builtin_ctzll() with our ctz64() wrapper which properly
> handles 0.
> 
> Signed-off-by: Matheus Tavares Bernardino <quic_mathbern@quicinc.com>

Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>

> ---
>  migration/xbzrle.c | 5 +++--
>  1 file changed, 3 insertions(+), 2 deletions(-)
> 
> diff --git a/migration/xbzrle.c b/migration/xbzrle.c
> index 05366e86c0..21b92d4eae 100644
> --- a/migration/xbzrle.c
> +++ b/migration/xbzrle.c
> @@ -12,6 +12,7 @@
>   */
>  #include "qemu/osdep.h"
>  #include "qemu/cutils.h"
> +#include "qemu/host-utils.h"
>  #include "xbzrle.h"
>  
>  /*
> @@ -233,7 +234,7 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
>                      break;
>                  }
>                  never_same = false;
> -                num = __builtin_ctzll(~comp);
> +                num = ctz64(~comp);
>                  num = (num < bytes_to_check) ? num : bytes_to_check;
>                  zrun_len += num;
>                  bytes_to_check -= num;
> @@ -262,7 +263,7 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
>                  nzrun_len += 64;
>                  break;
>              }
> -            num = __builtin_ctzll(comp);
> +            num = ctz64(comp);
>              num = (num < bytes_to_check) ? num : bytes_to_check;
>              nzrun_len += num;
>              bytes_to_check -= num;
> -- 
> 2.39.1
> 
-- 
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

Re: [PATCH RESEND v2 1/2] migration/xbzrle: use ctz64 to avoid undefined result

[Juan Quintela]

Matheus Tavares Bernardino <quic_mathbern@quicinc.com> wrote:
> __builtin_ctzll() produces undefined results when the argument is 0.
> This can be seen through test-xbzrle, which produces the following
> warning:
>
> ../migration/xbzrle.c:265: runtime error: passing zero to ctz(), which is not a valid argument
>
> Replace __builtin_ctzll() with our ctz64() wrapper which properly
> handles 0.
>
> Signed-off-by: Matheus Tavares Bernardino <quic_mathbern@quicinc.com>

Reviewed-by: Juan Quintela <quintela@redhat.com>

queued.

[PATCH RESEND v2 2/2] migration/xbzrle: fix out-of-bounds write with axv512

[Matheus Tavares Bernardino]

xbzrle_encode_buffer_avx512() checks for overflows too scarcely in its
outer loop, causing out-of-bounds writes:

$ ../configure --target-list=aarch64-softmmu --enable-sanitizers --enable-avx512bw
$ make tests/unit/test-xbzrle && ./tests/unit/test-xbzrle

==5518==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x62100000b100 at pc 0x561109a7714d bp 0x7ffed712a440 sp 0x7ffed712a430
WRITE of size 1 at 0x62100000b100 thread T0
    #0 0x561109a7714c in uleb128_encode_small ../util/cutils.c:831
    #1 0x561109b67f6a in xbzrle_encode_buffer_avx512 ../migration/xbzrle.c:275
    #2 0x5611099a7428 in test_encode_decode_overflow ../tests/unit/test-xbzrle.c:153
    #3 0x7fb2fb65a58d  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a58d)
    #4 0x7fb2fb65a333  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a333)
    #5 0x7fb2fb65aa79 in g_test_run_suite (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa79)
    #6 0x7fb2fb65aa94 in g_test_run (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa94)
    #7 0x5611099a3a23 in main ../tests/unit/test-xbzrle.c:218
    #8 0x7fb2fa78c082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
    #9 0x5611099a608d in _start (/qemu/build/tests/unit/test-xbzrle+0x28408d)

0x62100000b100 is located 0 bytes to the right of 4096-byte region [0x62100000a100,0x62100000b100)
allocated by thread T0 here:
    #0 0x7fb2fb823a06 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:153
    #1 0x7fb2fb637ef0 in g_malloc0 (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x57ef0)

Fix that by performing the overflow check in the inner loop, instead.

Signed-off-by: Matheus Tavares Bernardino <quic_mathbern@quicinc.com>
---
 migration/xbzrle.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/migration/xbzrle.c b/migration/xbzrle.c
index 21b92d4eae..c6f8b20917 100644
--- a/migration/xbzrle.c
+++ b/migration/xbzrle.c
@@ -197,10 +197,6 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
     __m512i r = _mm512_set1_epi32(0);
 
     while (count512s) {
-        if (d + 2 > dlen) {
-            return -1;
-        }
-
         int bytes_to_check = 64;
         uint64_t mask = 0xffffffffffffffff;
         if (count512s == 1) {
@@ -216,6 +212,9 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
 
         bool is_same = (comp & 0x1);
         while (bytes_to_check) {
+            if (d + 2 > dlen) {
+                return -1;
+            }
             if (is_same) {
                 if (nzrun_len) {
                     d += uleb128_encode_small(dst + d, nzrun_len);
-- 
2.39.1

Re: [PATCH RESEND v2 2/2] migration/xbzrle: fix out-of-bounds write with axv512

[Dr. David Alan Gilbert]

* Matheus Tavares Bernardino (quic_mathbern@quicinc.com) wrote:
> xbzrle_encode_buffer_avx512() checks for overflows too scarcely in its
> outer loop, causing out-of-bounds writes:
> 
> $ ../configure --target-list=aarch64-softmmu --enable-sanitizers --enable-avx512bw
> $ make tests/unit/test-xbzrle && ./tests/unit/test-xbzrle
> 
> ==5518==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x62100000b100 at pc 0x561109a7714d bp 0x7ffed712a440 sp 0x7ffed712a430
> WRITE of size 1 at 0x62100000b100 thread T0
>     #0 0x561109a7714c in uleb128_encode_small ../util/cutils.c:831
>     #1 0x561109b67f6a in xbzrle_encode_buffer_avx512 ../migration/xbzrle.c:275
>     #2 0x5611099a7428 in test_encode_decode_overflow ../tests/unit/test-xbzrle.c:153
>     #3 0x7fb2fb65a58d  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a58d)
>     #4 0x7fb2fb65a333  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a333)
>     #5 0x7fb2fb65aa79 in g_test_run_suite (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa79)
>     #6 0x7fb2fb65aa94 in g_test_run (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa94)
>     #7 0x5611099a3a23 in main ../tests/unit/test-xbzrle.c:218
>     #8 0x7fb2fa78c082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
>     #9 0x5611099a608d in _start (/qemu/build/tests/unit/test-xbzrle+0x28408d)
> 
> 0x62100000b100 is located 0 bytes to the right of 4096-byte region [0x62100000a100,0x62100000b100)
> allocated by thread T0 here:
>     #0 0x7fb2fb823a06 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:153
>     #1 0x7fb2fb637ef0 in g_malloc0 (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x57ef0)
> 
> Fix that by performing the overflow check in the inner loop, instead.
> 
> Signed-off-by: Matheus Tavares Bernardino <quic_mathbern@quicinc.com>
> ---
>  migration/xbzrle.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/migration/xbzrle.c b/migration/xbzrle.c
> index 21b92d4eae..c6f8b20917 100644
> --- a/migration/xbzrle.c
> +++ b/migration/xbzrle.c
> @@ -197,10 +197,6 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
>      __m512i r = _mm512_set1_epi32(0);
>  
>      while (count512s) {
> -        if (d + 2 > dlen) {
> -            return -1;
> -        }
> -
>          int bytes_to_check = 64;
>          uint64_t mask = 0xffffffffffffffff;
>          if (count512s == 1) {
> @@ -216,6 +212,9 @@ int xbzrle_encode_buffer_avx512(uint8_t *old_buf, uint8_t *new_buf, int slen,
>  
>          bool is_same = (comp & 0x1);
>          while (bytes_to_check) {
> +            if (d + 2 > dlen) {
> +                return -1;
> +            }

I agree that's better, so:

Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>


but is it sufficient?
In that bytes_to_check loop there are 4 calls to uleb128_encode_small
with another one just off the end of the loop.
I've not figured out all the legal combos, but I'm pretty sure at least
a few can trigger in one iteration - so don't we need those checks
before ecah call?

Dave

>              if (is_same) {
>                  if (nzrun_len) {
>                      d += uleb128_encode_small(dst + d, nzrun_len);
> -- 
> 2.39.1
> 
-- 
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

Re: [PATCH RESEND v2 2/2] migration/xbzrle: fix out-of-bounds write with axv512

[Juan Quintela]

Matheus Tavares Bernardino <quic_mathbern@quicinc.com> wrote:
> xbzrle_encode_buffer_avx512() checks for overflows too scarcely in its
> outer loop, causing out-of-bounds writes:
>
> $ ../configure --target-list=aarch64-softmmu --enable-sanitizers --enable-avx512bw
> $ make tests/unit/test-xbzrle && ./tests/unit/test-xbzrle
>
> ==5518==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x62100000b100 at pc 0x561109a7714d bp 0x7ffed712a440 sp 0x7ffed712a430
> WRITE of size 1 at 0x62100000b100 thread T0
>     #0 0x561109a7714c in uleb128_encode_small ../util/cutils.c:831
>     #1 0x561109b67f6a in xbzrle_encode_buffer_avx512 ../migration/xbzrle.c:275
>     #2 0x5611099a7428 in test_encode_decode_overflow ../tests/unit/test-xbzrle.c:153
>     #3 0x7fb2fb65a58d  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a58d)
>     #4 0x7fb2fb65a333  (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7a333)
>     #5 0x7fb2fb65aa79 in g_test_run_suite (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa79)
>     #6 0x7fb2fb65aa94 in g_test_run (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x7aa94)
>     #7 0x5611099a3a23 in main ../tests/unit/test-xbzrle.c:218
>     #8 0x7fb2fa78c082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
>     #9 0x5611099a608d in _start (/qemu/build/tests/unit/test-xbzrle+0x28408d)
>
> 0x62100000b100 is located 0 bytes to the right of 4096-byte region [0x62100000a100,0x62100000b100)
> allocated by thread T0 here:
>     #0 0x7fb2fb823a06 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:153
>     #1 0x7fb2fb637ef0 in g_malloc0 (/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x57ef0)
>
> Fix that by performing the overflow check in the inner loop, instead.
>
> Signed-off-by: Matheus Tavares Bernardino <quic_mathbern@quicinc.com>

Reviewed-by: Juan Quintela <quintela@redhat.com>

queued.

As David said, we can still improve the code.

thanks, Juan.