[PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Florian Weimer]

-----
Changes to the previous version:

* Use support_blob_repeat_allocate_shared to preserve sharing (no
  copy-on-write).
* Use MAP_FIXED for the head and tail, to change the existing mapping.

 string/Makefile               |   2 +-
 string/tst-memmove-overflow.c | 155 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 156 insertions(+), 1 deletion(-)

diff --git a/string/Makefile b/string/Makefile
index c46785f1a1..e1cca5516b 100644
--- a/string/Makefile
+++ b/string/Makefile
@@ -60,7 +60,7 @@ tests		:= tester inl-tester noinl-tester testcopy test-ffs	\
 		   bug-envz1 tst-strxfrm2 tst-endian tst-svc2		\
 		   tst-strtok_r bug-strcoll2 tst-cmp tst-xbzero-opt	\
 		   test-endian-types test-endian-file-scope		\
-		   test-endian-sign-conversion
+		   test-endian-sign-conversion tst-memmove-overflow
 
 # This test allocates a lot of memory and can run for a long time.
 xtests = tst-strcoll-overflow
diff --git a/string/tst-memmove-overflow.c b/string/tst-memmove-overflow.c
new file mode 100644
index 0000000000..b744679ef4
--- /dev/null
+++ b/string/tst-memmove-overflow.c
@@ -0,0 +1,155 @@
+/* Test for signed comparision bug in memmove (bug 25620).
+   Copyright (C) 2020 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+/* This test shifts a memory region which is a bit larger than 2 GiB
+   by one byte.  In order to make it more likely that the memory
+   allocation succeeds on 32-bit systems, most of the allocation
+   consists of shared pages.  Only a portion at the start and end of
+   the allocation are unshared, and contain a specific non-repeating
+   bit pattern.  */
+
+#include <array_length.h>
+#include <libc-diag.h>
+#include <stdint.h>
+#include <string.h>
+#include <support/blob_repeat.h>
+#include <support/check.h>
+#include <support/xunistd.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+#define TEST_MAIN
+#define TEST_NAME "memmove"
+#include "test-string.h"
+#include <support/test-driver.h>
+
+IMPL (memmove, 1)
+
+/* Size of the part of the allocation which is not shared, at the
+   start and the end of the overall allocation.  4 MiB.  */
+static const size_t unshared_size = 4U << 20;
+
+/* The allocation is 2 GiB plus 8 MiB.  This should work with all page
+   sizes that occur in practice.  */
+static const size_t allocation_size = (2U << 30) + 2 * unshared_size;
+
+/* Compute the expected byte at the given index.  This is used to
+   produce a non-repeating pattern.  */
+static inline unsigned char
+expected_value (size_t index)
+{
+  uint32_t randomized = 0x9e3779b9 * index; /* Based on golden ratio.  */
+  return randomized >> 25;	/* Result is in the range [0, 127].  */
+}
+
+static int
+test_main (void)
+{
+  test_init ();
+
+  FOR_EACH_IMPL (impl, 0)
+    {
+      printf ("info: testing %s\n", impl->name);
+
+      /* Check that the allocation sizes are multiples of the page
+	 size.  */
+      TEST_COMPARE (allocation_size % xsysconf (_SC_PAGESIZE), 0);
+      TEST_COMPARE (unshared_size % xsysconf (_SC_PAGESIZE), 0);
+
+      /* The repeating pattern has the MSB set in all bytes.  */
+      unsigned char repeating_pattern[128];
+      for (unsigned int i = 0; i < array_length (repeating_pattern); ++i)
+	repeating_pattern[i] = 0x80 | i;
+
+      struct support_blob_repeat repeat
+	= support_blob_repeat_allocate_shared (repeating_pattern,
+					       sizeof (repeating_pattern),
+					       (allocation_size
+						/ sizeof (repeating_pattern)));
+      if (repeat.start == NULL)
+	FAIL_UNSUPPORTED ("repeated blob allocation failed: %m");
+      TEST_COMPARE (repeat.size, allocation_size);
+
+      /* Unshared the start and the end of the allocation.  */
+      unsigned char *start = repeat.start;
+      xmmap (start, unshared_size,
+	     PROT_READ | PROT_WRITE,
+	     MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1);
+      xmmap (start + allocation_size - unshared_size, unshared_size,
+	     PROT_READ | PROT_WRITE,
+	     MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1);
+
+      /* Initialize the non-repeating pattern.  */
+      for (size_t i = 0; i < unshared_size; ++i)
+	start[i] = expected_value (i);
+      for (size_t i = allocation_size - unshared_size; i < allocation_size;
+	   ++i)
+	start[i] = expected_value (i);
+
+      /* Make sure that there was really no sharing.  */
+      asm volatile ("" ::: "memory");
+      for (size_t i = 0; i < unshared_size; ++i)
+	TEST_COMPARE (start[i], expected_value (i));
+      for (size_t i = allocation_size - unshared_size; i < allocation_size;
+	   ++i)
+	TEST_COMPARE (start[i], expected_value (i));
+
+      /* Used for a nicer error diagnostic using
+	 TEST_COMPARE_BLOB.  */
+      unsigned char expected_start[128];
+      memcpy (expected_start, start + 1, sizeof (expected_start));
+      unsigned char expected_end[128];
+      memcpy (expected_end,
+	      start + allocation_size - sizeof (expected_end),
+	      sizeof (expected_end));
+
+      /* Move the entire allocation forward by one byte.  */
+      DIAG_PUSH_NEEDS_COMMENT;
+#if __GNUC_PREREQ (8, 0)
+      /* GCC 8 warns about string function argument overflows.  */
+      DIAG_IGNORE_NEEDS_COMMENT (8, "-Warray-bounds");
+      DIAG_IGNORE_NEEDS_COMMENT (8, "-Wstringop-overflow");
+#endif
+      memmove (start, start + 1, allocation_size - 1);
+      DIAG_POP_NEEDS_COMMENT;
+
+      /* Check that the unshared of the memory region have been
+	 shifted as expected.  The TEST_COMPARE_BLOB checks are
+	 redundant, but produce nicer diagnostics.  */
+      asm volatile ("" ::: "memory");
+      TEST_COMPARE_BLOB (expected_start, sizeof (expected_start),
+			 start, sizeof (expected_start));
+      TEST_COMPARE_BLOB (expected_end, sizeof (expected_end),
+			 start + allocation_size - sizeof (expected_end) - 1,
+			 sizeof (expected_end));
+      for (size_t i = 0; i < unshared_size - 1; ++i)
+	TEST_COMPARE (start[i], expected_value (i + 1));
+      /* The gap between the checked start and end area of the mapping
+	 has shared mappings at unspecified boundaries, so do not
+	 check the expected values in the middle.  */
+      for (size_t i = allocation_size - unshared_size; i < allocation_size - 1;
+	   ++i)
+	TEST_COMPARE (start[i], expected_value (i + 1));
+
+      support_blob_repeat_free (&repeat);
+    }
+
+  return 0;
+}
+
+#include <support/test-driver.c>

Re: [PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Carlos O'Donell]

On 5/5/20 9:57 AM, Florian Weimer wrote:
> -----

Should be 3-dash.

> Changes to the previous version:

No regressions on x86_64 or i686.

OK for master.

Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Tested-by: Carlos O'Donell <carlos@redhat.com>

> 
> * Use support_blob_repeat_allocate_shared to preserve sharing (no
>   copy-on-write).
> * Use MAP_FIXED for the head and tail, to change the existing mapping.
> 
>  string/Makefile               |   2 +-
>  string/tst-memmove-overflow.c | 155 ++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 156 insertions(+), 1 deletion(-)
> 
> diff --git a/string/Makefile b/string/Makefile
> index c46785f1a1..e1cca5516b 100644
> --- a/string/Makefile
> +++ b/string/Makefile
> @@ -60,7 +60,7 @@ tests		:= tester inl-tester noinl-tester testcopy test-ffs	\
>  		   bug-envz1 tst-strxfrm2 tst-endian tst-svc2		\
>  		   tst-strtok_r bug-strcoll2 tst-cmp tst-xbzero-opt	\
>  		   test-endian-types test-endian-file-scope		\
> -		   test-endian-sign-conversion
> +		   test-endian-sign-conversion tst-memmove-overflow

OK.

>  
>  # This test allocates a lot of memory and can run for a long time.
>  xtests = tst-strcoll-overflow
> diff --git a/string/tst-memmove-overflow.c b/string/tst-memmove-overflow.c
> new file mode 100644
> index 0000000000..b744679ef4
> --- /dev/null
> +++ b/string/tst-memmove-overflow.c
> @@ -0,0 +1,155 @@
> +/* Test for signed comparision bug in memmove (bug 25620).

OK.

> +   Copyright (C) 2020 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library; if not, see
> +   <https://www.gnu.org/licenses/>.  */
> +
> +/* This test shifts a memory region which is a bit larger than 2 GiB
> +   by one byte.  In order to make it more likely that the memory
> +   allocation succeeds on 32-bit systems, most of the allocation
> +   consists of shared pages.  Only a portion at the start and end of
> +   the allocation are unshared, and contain a specific non-repeating
> +   bit pattern.  */

OK. Great initial comment.

> +
> +#include <array_length.h>
> +#include <libc-diag.h>
> +#include <stdint.h>
> +#include <string.h>
> +#include <support/blob_repeat.h>
> +#include <support/check.h>
> +#include <support/xunistd.h>
> +#include <sys/mman.h>
> +#include <unistd.h>
> +
> +#define TEST_MAIN
> +#define TEST_NAME "memmove"
> +#include "test-string.h"
> +#include <support/test-driver.h>
> +
> +IMPL (memmove, 1)
> +
> +/* Size of the part of the allocation which is not shared, at the
> +   start and the end of the overall allocation.  4 MiB.  */
> +static const size_t unshared_size = 4U << 20;

OK.

> +
> +/* The allocation is 2 GiB plus 8 MiB.  This should work with all page
> +   sizes that occur in practice.  */
> +static const size_t allocation_size = (2U << 30) + 2 * unshared_size;

OK.

> +
> +/* Compute the expected byte at the given index.  This is used to
> +   produce a non-repeating pattern.  */
> +static inline unsigned char
> +expected_value (size_t index)
> +{
> +  uint32_t randomized = 0x9e3779b9 * index; /* Based on golden ratio.  */
> +  return randomized >> 25;	/* Result is in the range [0, 127].  */
> +}

OK.

> +
> +static int
> +test_main (void)
> +{
> +  test_init ();
> +
> +  FOR_EACH_IMPL (impl, 0)
> +    {
> +      printf ("info: testing %s\n", impl->name);
> +
> +      /* Check that the allocation sizes are multiples of the page
> +	 size.  */
> +      TEST_COMPARE (allocation_size % xsysconf (_SC_PAGESIZE), 0);
> +      TEST_COMPARE (unshared_size % xsysconf (_SC_PAGESIZE), 0);
> +
> +      /* The repeating pattern has the MSB set in all bytes.  */
> +      unsigned char repeating_pattern[128];
> +      for (unsigned int i = 0; i < array_length (repeating_pattern); ++i)
> +	repeating_pattern[i] = 0x80 | i;

OK.

> +
> +      struct support_blob_repeat repeat
> +	= support_blob_repeat_allocate_shared (repeating_pattern,
> +					       sizeof (repeating_pattern),
> +					       (allocation_size
> +						/ sizeof (repeating_pattern)));

OK. Repeat the pattern shared.

> +      if (repeat.start == NULL)
> +	FAIL_UNSUPPORTED ("repeated blob allocation failed: %m");
> +      TEST_COMPARE (repeat.size, allocation_size);

OK.

> +
> +      /* Unshared the start and the end of the allocation.  */
> +      unsigned char *start = repeat.start;
> +      xmmap (start, unshared_size,
> +	     PROT_READ | PROT_WRITE,
> +	     MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1);
> +      xmmap (start + allocation_size - unshared_size, unshared_size,
> +	     PROT_READ | PROT_WRITE,
> +	     MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1);

OK. Unmap start 4MiB and ending 4MiB.

> +
> +      /* Initialize the non-repeating pattern.  */
> +      for (size_t i = 0; i < unshared_size; ++i)
> +	start[i] = expected_value (i);
> +      for (size_t i = allocation_size - unshared_size; i < allocation_size;
> +	   ++i)
> +	start[i] = expected_value (i);

OK.

> +
> +      /* Make sure that there was really no sharing.  */
> +      asm volatile ("" ::: "memory");
> +      for (size_t i = 0; i < unshared_size; ++i)
> +	TEST_COMPARE (start[i], expected_value (i));
> +      for (size_t i = allocation_size - unshared_size; i < allocation_size;
> +	   ++i)
> +	TEST_COMPARE (start[i], expected_value (i));

OK. Belt-and-suspenders :-)

> +
> +      /* Used for a nicer error diagnostic using
> +	 TEST_COMPARE_BLOB.  */
> +      unsigned char expected_start[128];
> +      memcpy (expected_start, start + 1, sizeof (expected_start));
> +      unsigned char expected_end[128];
> +      memcpy (expected_end,
> +	      start + allocation_size - sizeof (expected_end),
> +	      sizeof (expected_end));

OK.

> +
> +      /* Move the entire allocation forward by one byte.  */
> +      DIAG_PUSH_NEEDS_COMMENT;
> +#if __GNUC_PREREQ (8, 0)
> +      /* GCC 8 warns about string function argument overflows.  */
> +      DIAG_IGNORE_NEEDS_COMMENT (8, "-Warray-bounds");
> +      DIAG_IGNORE_NEEDS_COMMENT (8, "-Wstringop-overflow");
> +#endif
> +      memmove (start, start + 1, allocation_size - 1);
> +      DIAG_POP_NEEDS_COMMENT;

OK.

> +
> +      /* Check that the unshared of the memory region have been
> +	 shifted as expected.  The TEST_COMPARE_BLOB checks are
> +	 redundant, but produce nicer diagnostics.  */
> +      asm volatile ("" ::: "memory");
> +      TEST_COMPARE_BLOB (expected_start, sizeof (expected_start),
> +			 start, sizeof (expected_start));
> +      TEST_COMPARE_BLOB (expected_end, sizeof (expected_end),
> +			 start + allocation_size - sizeof (expected_end) - 1,
> +			 sizeof (expected_end));

OK. Compare blobs because you get the nice output.

> +      for (size_t i = 0; i < unshared_size - 1; ++i)
> +	TEST_COMPARE (start[i], expected_value (i + 1));

OK.

> +      /* The gap between the checked start and end area of the mapping
> +	 has shared mappings at unspecified boundaries, so do not
> +	 check the expected values in the middle.  */

OK. Yup, and checking all of these would take a long time.

> +      for (size_t i = allocation_size - unshared_size; i < allocation_size - 1;
> +	   ++i)
> +	TEST_COMPARE (start[i], expected_value (i + 1));

OK. Compare the actual bytes.

> +
> +      support_blob_repeat_free (&repeat);
> +    }

OK. Repeat for each implementation.

> +
> +  return 0;
> +}
> +
> +#include <support/test-driver.c>
> 


-- 
Cheers,
Carlos.

Re: [PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Andreas Schwab]

I'm getting an endless output of errors:

tst-memmove-overflow.c:141: numeric comparison failure
   left: 80 (0x50); from: start[i]
  right: 31 (0x1f); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 31 (0x1f); from: start[i]
  right: 110 (0x6e); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 110 (0x6e); from: start[i]
  right: 61 (0x3d); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 61 (0x3d); from: start[i]
  right: 13 (0xd); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 13 (0xd); from: start[i]
  right: 92 (0x5c); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 92 (0x5c); from: start[i]
  right: 43 (0x2b); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 43 (0x2b); from: start[i]
  right: 122 (0x7a); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 122 (0x7a); from: start[i]
  right: 73 (0x49); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 73 (0x49); from: start[i]
  right: 24 (0x18); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 24 (0x18); from: start[i]
  right: 103 (0x67); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 103 (0x67); from: start[i]
  right: 54 (0x36); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 54 (0x36); from: start[i]
  right: 5 (0x5); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 5 (0x5); from: start[i]
  right: 85 (0x55); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 85 (0x55); from: start[i]
  right: 36 (0x24); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 36 (0x24); from: start[i]
  right: 115 (0x73); from: expected_value (i + 1)
tst-memmove-overflow.c:141: numeric comparison failure
   left: 115 (0x73); from: start[i]
  right: 66 (0x42); from: expected_value (i + 1)

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Florian Weimer]

* Andreas Schwab:

> I'm getting an endless output of errors:
>
> tst-memmove-overflow.c:141: numeric comparison failure
>    left: 80 (0x50); from: start[i]
>   right: 31 (0x1f); from: expected_value (i + 1)

On which architecture?

Re: [PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Andreas Schwab]

https://build.opensuse.org/package/live_build_log/home:Andreas_Schwab:glibc/glibc:testsuite/a/armv7l

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Florian Weimer]

* Andreas Schwab:

> https://build.opensuse.org/package/live_build_log/home:Andreas_Schwab:glibc/glibc:testsuite/a/armv7l

Yes, that's part of bug 25620.  There's a new patch posted for it:

  <https://sourceware.org/pipermail/libc-alpha/2020-May/113863.html>

The patch submission did not come with a test case, and a test case was
requested, so we had a chicken-and-egg situation.

Thanks,
Florian

Re: [PATCH] string: Add string/tst-memmove-overflow, a test case for bug 25620

[Andreas Schwab]

On Mai 13 2020, Florian Weimer wrote:

> The patch submission did not come with a test case, and a test case was
> requested, so we had a chicken-and-egg situation.

Please revert then.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."