[PATCH] Avoid invoking undefined behavior when initializing CRC table

[PATCH] Avoid invoking undefined behavior when initializing CRC table

[Patrick Palka]

When I built GDB with (an older snapshot of) GCC 6 I get the following
error:

.../binutils-gdb/gdb/gdbserver/server.c: In function ‘crc32’:
.../binutils-gdb/gdb/gdbserver/server.c:1895:15: error: iteration 128 invokes undefined behavior [-Werror=aggressive-loop-optimizations]
    for (c = i << 24, j = 8; j > 0; --j)
               ^
.../binutils-gdb/gdb/gdbserver/server.c:1893:7: note: within this loop
       for (i = 0; i < 256; i++)
       ^
This error seems to be correct.  When the variable "int i" is >= 128,
the computation "i << 24" overflows for 32-bit signed int.

To avoid shifting into the sign bit, this patch makes the variables i
(and j, because why not) have type unsigned int instead.

(Alternatively, I can just define this local crc32 function in terms of
libiberty's xcrc32.  Any reason not to?  xcrc32 seems to be
based off of GDB's crc32 implementation.  Its documentation even
refers to it!)

gdb/gdbserver/ChangeLog:

	* server.c (crc32): Change type of induction variables i and j
	from int to unsigned int.
---
 gdb/gdbserver/server.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gdb/gdbserver/server.c b/gdb/gdbserver/server.c
index b385afb..70acafc 100644
--- a/gdb/gdbserver/server.c
+++ b/gdb/gdbserver/server.c
@@ -1927,7 +1927,7 @@ crc32 (CORE_ADDR base, int len, unsigned int crc)
   if (!crc32_table[1])
     {
       /* Initialize the CRC table and the decoding table.  */
-      int i, j;
+      unsigned int i, j;
       unsigned int c;
 
       for (i = 0; i < 256; i++)
-- 
2.7.0.rc1.98.gacf58d0.dirty

Re: [PATCH] Avoid invoking undefined behavior when initializing CRC table

[Patrick Palka]

[-- Attachment #1: Type: text/plain, Size: 2423 bytes --]

On Sun, 27 Dec 2015, Patrick Palka wrote:

> When I built GDB with (an older snapshot of) GCC 6 I get the following
> error:
>
> .../binutils-gdb/gdb/gdbserver/server.c: In function ‘crc32’:
> .../binutils-gdb/gdb/gdbserver/server.c:1895:15: error: iteration 128 invokes undefined behavior [-Werror=aggressive-loop-optimizations]
>    for (c = i << 24, j = 8; j > 0; --j)
>               ^
> .../binutils-gdb/gdb/gdbserver/server.c:1893:7: note: within this loop
>       for (i = 0; i < 256; i++)
>       ^
> This error seems to be correct.  When the variable "int i" is >= 128,
> the computation "i << 24" overflows for 32-bit signed int.
>
> To avoid shifting into the sign bit, this patch makes the variables i
> (and j, because why not) have type unsigned int instead.
>
> (Alternatively, I can just define this local crc32 function in terms of
> libiberty's xcrc32.  Any reason not to?  xcrc32 seems to be
> based off of GDB's crc32 implementation.  Its documentation even
> refers to it!)

And here's a rough diff that defines crc32 in terms of xcrc32:

diff --git a/gdb/gdbserver/server.c b/gdb/gdbserver/server.c
index 70acafc..0e3ac4e 100644
--- a/gdb/gdbserver/server.c
+++ b/gdb/gdbserver/server.c
@@ -1911,11 +1911,6 @@ handle_qxfer (char *own_buf, int packet_len, int *new_packet_len_p)
    return 0;
  }

-/* Table used by the crc32 function to calcuate the checksum.  */
-
-static unsigned int crc32_table[256] =
-{0, 0};
-
  /* Compute 32 bit CRC from inferior memory.

     On success, return 32 bit CRC.
@@ -1924,20 +1919,6 @@ static unsigned int crc32_table[256] =
  static unsigned long long
  crc32 (CORE_ADDR base, int len, unsigned int crc)
  {
-  if (!crc32_table[1])
-    {
-      /* Initialize the CRC table and the decoding table.  */
-      unsigned int i, j;
-      unsigned int c;
-
-      for (i = 0; i < 256; i++)
-       {
-         for (c = i << 24, j = 8; j > 0; --j)
-           c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);
-         crc32_table[i] = c;
-       }
-    }
-
    while (len--)
      {
        unsigned char byte = 0;
@@ -1946,7 +1927,7 @@ crc32 (CORE_ADDR base, int len, unsigned int crc)
        if (read_inferior_memory (base, &byte, 1) != 0)
         return (unsigned long long) -1;

-      crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ byte) & 255];
+      crc = xcrc32 (&byte, 1, crc);
        base++;
      }
    return (unsigned long long) crc;

Re: [PATCH] Avoid invoking undefined behavior when initializing CRC table

[Pedro Alves]

On 12/28/2015 04:15 AM, Patrick Palka wrote:
> On Sun, 27 Dec 2015, Patrick Palka wrote:
> 
>> When I built GDB with (an older snapshot of) GCC 6 I get the following
>> error:
>>
>> .../binutils-gdb/gdb/gdbserver/server.c: In function ‘crc32’:
>> .../binutils-gdb/gdb/gdbserver/server.c:1895:15: error: iteration 128 invokes undefined behavior [-Werror=aggressive-loop-optimizations]
>>    for (c = i << 24, j = 8; j > 0; --j)
>>               ^
>> .../binutils-gdb/gdb/gdbserver/server.c:1893:7: note: within this loop
>>       for (i = 0; i < 256; i++)
>>       ^
>> This error seems to be correct.  When the variable "int i" is >= 128,
>> the computation "i << 24" overflows for 32-bit signed int.
>>
>> To avoid shifting into the sign bit, this patch makes the variables i
>> (and j, because why not) have type unsigned int instead.
>>
>> (Alternatively, I can just define this local crc32 function in terms of
>> libiberty's xcrc32.  Any reason not to?

Just history.  gdbserver only started linking with libiberty in
2014 (0b04e52316) and the gdbserver crc32 code predates that.

> xcrc32 seems to be
>> based off of GDB's crc32 implementation.  Its documentation even
>> refers to it!)
> 
> And here's a rough diff that defines crc32 in terms of xcrc32:
> 

That looks good.  Tom did the same on the GDB side in 85ec6ce7d5 (2013).

Just in case, please make sure testing against gdbserver doesn't regress:

  $ make check -j8 RUNTESTFLAGS="--target_board=native-gdbserver" FORCE_PARALLEL=1

particularly, the compare-sections command.  We have a test which covers it:

  $ make check RUNTESTFLAGS="--target_board=native-gdbserver compare-sections.exp"

Thanks,
Pedro Alves

[PATCH] [COMMITTED] Use libiberty's crc32 implementation in gdbserver

[Patrick Palka]

Tested on x86_64-pc-linux-gnu native-gdbserver, no new regressions.

gdb/gdbserver/ChangeLog:

	* server.c (crc32_table): Delete.
	(crc32): Use libiberty's xcrc32 function.
---
 gdb/gdbserver/server.c | 21 +--------------------
 1 file changed, 1 insertion(+), 20 deletions(-)

diff --git a/gdb/gdbserver/server.c b/gdb/gdbserver/server.c
index b385afb..0e3ac4e 100644
--- a/gdb/gdbserver/server.c
+++ b/gdb/gdbserver/server.c
@@ -1911,11 +1911,6 @@ handle_qxfer (char *own_buf, int packet_len, int *new_packet_len_p)
   return 0;
 }
 
-/* Table used by the crc32 function to calcuate the checksum.  */
-
-static unsigned int crc32_table[256] =
-{0, 0};
-
 /* Compute 32 bit CRC from inferior memory.
 
    On success, return 32 bit CRC.
@@ -1924,20 +1919,6 @@ static unsigned int crc32_table[256] =
 static unsigned long long
 crc32 (CORE_ADDR base, int len, unsigned int crc)
 {
-  if (!crc32_table[1])
-    {
-      /* Initialize the CRC table and the decoding table.  */
-      int i, j;
-      unsigned int c;
-
-      for (i = 0; i < 256; i++)
-	{
-	  for (c = i << 24, j = 8; j > 0; --j)
-	    c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);
-	  crc32_table[i] = c;
-	}
-    }
-
   while (len--)
     {
       unsigned char byte = 0;
@@ -1946,7 +1927,7 @@ crc32 (CORE_ADDR base, int len, unsigned int crc)
       if (read_inferior_memory (base, &byte, 1) != 0)
 	return (unsigned long long) -1;
 
-      crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ byte) & 255];
+      crc = xcrc32 (&byte, 1, crc);
       base++;
     }
   return (unsigned long long) crc;
-- 
2.7.0.rc1.98.gacf58d0.dirty