[PATCH v2 0/2] Fix a couple undefined behaviors flagged by UBSan

[PATCH v2 0/2] Fix a couple undefined behaviors flagged by UBSan

[Pedro Alves]

New in v2:
  - Fix a number of typos in patch #1.

Running the testsuite against GDBserver with a GDB built with
--enable-ubsan, I noticed a few problems.  This mini-series fixes a
couple.

Pedro Alves (2):
  gdb: Avoid undefined shifts
  Avoid undefined behavior in gdbscm_make_breakpoint

 gdb/guile/scm-breakpoint.c        |  10 +--
 gdb/testsuite/gdb.base/bitops.exp | 131 ++++++++++++++++++++++++++++++
 gdb/valarith.c                    |  61 +++++++++++++-
 3 files changed, 193 insertions(+), 9 deletions(-)


base-commit: edbc15e6c4f463173b25b1f8042346c2e1a78602
-- 
2.26.2

[PATCH v2 1/2] gdb: Avoid undefined shifts

[Pedro Alves]

I noticed that a build of GDB with GCC + --enable-ubsan, testing
against GDBserver showed this GDB crash:

  (gdb) PASS: gdb.trace/trace-condition.exp: trace: 0x00abababcdcdcdcd << 46 == 0x7373400000000000: advance to trace begin
  tstart
  ../../src/gdb/valarith.c:1365:15: runtime error: left shift of 48320975398096333 by 46 places cannot be represented in type 'long int'
  ERROR: GDB process no longer exists
  GDB process exited with wait status 269549 exp9 0 1
  UNRESOLVED: gdb.trace/trace-condition.exp: trace: 0x00abababcdcdcdcd << 46 == 0x7373400000000000: start trace experiment

The problem is that, "0x00abababcdcdcdcd << 46" is an undefined signed
left shift, because the result is not representable in the type of the
lhs, which is signed.  This actually became defined in C++20, and if
you compile with "g++ -std=c++20 -Wall", you'll see that GCC no longer
warns about it, while it warns if you specify prior language versions.

While at it, there are a couple other situations that are undefined
(and are still undefined in C++20) and result in GDB dying: shifting
by a negative ammount, or by >= than the bit size of the promoted lhs.
For the latter, GDB shifts using (U)LONGEST internally, so you have to
shift by >= 64 bits to see it:

 $ gdb --batch -q -ex "p 1 << -1"
 ../../src/gdb/valarith.c:1365:15: runtime error: shift exponent -1 is negative
 $ # gdb exited

 $ gdb --batch -q -ex "p 1 << 64"
 ../../src/gdb/valarith.c:1365:15: runtime error: shift exponent 64 is too large for 64-bit type 'long int'
 $ # gdb exited

Also, right shifting a negative value is implementation-defined
(before C++20, after which it is defined).  For this, I chose to
change nothing in GDB other than adding tests, as I don't really know
whether we need to do anything.  AFAIK, most implementations do an
arithmetic right shift, and it may be we don't support any host or
target that behaves differently.  Plus, this becomes defined in C++20
exactly as arithmetic right shift.

Compilers don't error out on such shifts, at best they warn, so I
think GDB should just continue doing the shifts anyhow too.

Thus:

- Adjust scalar_binop to avoid the undefined paths, either by adding
  explicit result paths, or by casting the lhs of the left shift to
  unsigned, as appropriate.  For the shifts by negative amount or a
  too-large amount, I made the result be 0 (and warn).  This is
  undefined, so we're free to pick any value, and 0 seems reasonable,
  as it's what you'd get if you split a too-large shift by a number of
  smaller valid shifts, and if you imagine a shift by a negative value
  as a shift by a very-large unsigned value, you get the same too.

- Make GDB warn for the cases that are still undefined in C++20.  The
  warnings' texts are the same as what GCC prints.

- Add comprehensive tests to gdb.base/bitops.exp, so that we exercise
  all these scenarios.

Change-Id: I8bcd5fa02de3114b7ababc03e65702d86ec8d45d
---
 gdb/testsuite/gdb.base/bitops.exp | 131 ++++++++++++++++++++++++++++++
 gdb/valarith.c                    |  61 +++++++++++++-
 2 files changed, 188 insertions(+), 4 deletions(-)

diff --git a/gdb/testsuite/gdb.base/bitops.exp b/gdb/testsuite/gdb.base/bitops.exp
index deea456710f..1dd991af72b 100644
--- a/gdb/testsuite/gdb.base/bitops.exp
+++ b/gdb/testsuite/gdb.base/bitops.exp
@@ -110,3 +110,134 @@ gdb_test "print 0 || 1 && 0 | 0 ^ 0 == 8" ".\[0-9\]* = 0" \
 gdb_test "print 0 == 8 > 128 >> 1 + 2 * 2" ".\[0-9\]* = 0" \
     "print value of 0 == 8 > 128 >> 1 + 2 * 2"
 
+# Test a print command that prints out RESULT_RE.  If WARNING is
+# non-empty, it is expected that GDB prints this warning before the
+# print result.  If WARNING is empty, it is expected that GDB prints
+# no text other than the print result.
+proc test_shift {cmd result_re {warning ""}} {
+    if {$warning != ""} {
+	set warning_re "[string_to_regexp $warning]\r\n"
+    } else {
+	set warning_re ""
+    }
+
+    set cmd_re [string_to_regexp $cmd]
+
+    gdb_test_multiple $cmd "" {
+	-re -wrap "^$cmd_re\r\n$warning_re\\$$::decimal$result_re" {
+	    pass $gdb_test_name
+	}
+    }
+}
+
+# Some warnings GDB outputs.
+set negative_shift "warning: right shift count is negative"
+set too_large_shift "warning: right shift count >= width of type"
+
+# Make sure a signed left shift that overflows, i.e., whose result
+# isn't representable in the signed type of the lhs, which is actually
+# undefined, doesn't crash GDB when is it built with UBSan.
+
+test_shift "print /x 0x0fffffffffffffff << 8" " = 0xffffffffffffff00"
+test_shift "print /x 0x0fffffff << 8" " = 0xffffff00"
+
+# Make sure the result is still signed when the lhs was signed.
+test_shift "print 0x0fffffffffffffff << 8" " = -256"
+test_shift "print 0x0fffffff << 8" " = -256"
+
+# 8-bit and 16-bit are promoted to int.
+foreach sign {"signed" "unsigned"} {
+    test_shift "print /x ($sign char) 0x0f << 8" " = 0xf00"
+    test_shift "print ($sign char) 0x0f << 8" " = 3840"
+    test_shift "print /x ($sign short) 0x0fff << 8" " = 0xfff00"
+    test_shift "print ($sign short) 0x0fff << 8" " = 1048320"
+}
+
+# Similarly, test shifting with both negative and too-large rhs.  Both
+# cases are undefined, but GDB lets them go through anyhow, similarly
+# to how compilers don't error out.  Try both signed and unsigned lhs.
+
+# 8-bit lhs, signed and unsigned.  These get promoted to 32-bit int.
+foreach lhs {"(signed char) 0x7f" "(unsigned char) 0xff"} {
+    test_shift "print $lhs << -1" " = 0" $negative_shift
+    test_shift "print $lhs >> -1" " = 0" $negative_shift
+
+    test_shift "print/x $lhs >> 8" " = 0x0"
+    test_shift "print/x $lhs << 8" " = 0x(7|f)f00"
+
+    test_shift "print $lhs >> 32" " = 0" $too_large_shift
+    test_shift "print $lhs << 32" " = 0" $too_large_shift
+    test_shift "print $lhs >> 33" " = 0" $too_large_shift
+    test_shift "print $lhs << 33" " = 0" $too_large_shift
+}
+
+# 16-bit lhs, signed and unsigned.  These get promoted to 32-bit int.
+foreach {lhs_cast lhs_val} {
+    "(short)" "0x7fff"
+    "(unsigned short)" "0xffff"
+} {
+    set lhs "$lhs_cast $lhs_val"
+
+    test_shift "print $lhs << -1" " = 0" $negative_shift
+    test_shift "print $lhs >> -1" " = 0" $negative_shift
+
+    # Confirm shifting by 0 doesn't warn.
+    test_shift "print/x $lhs << 0" " = $lhs_val"
+    test_shift "print/x $lhs >> 0" " = $lhs_val"
+
+    # These don't overflow due to promotion.
+    test_shift "print/x $lhs >> 16" " = 0x0"
+    test_shift "print/x $lhs << 16" " = 0x(7|f)fff0000"
+
+    test_shift "print $lhs >> 32" " = 0" $too_large_shift
+    test_shift "print $lhs << 32" " = 0" $too_large_shift
+    test_shift "print $lhs >> 33" " = 0" $too_large_shift
+    test_shift "print $lhs << 33" " = 0" $too_large_shift
+}
+
+# 32-bit lhs, signed and unsigned.
+foreach lhs {0x7fffffff 0xffffffff} {
+    test_shift "print $lhs << -1" " = 0" $negative_shift
+    test_shift "print $lhs >> -1" " = 0" $negative_shift
+
+    # Confirm shifting by 0 doesn't warn.
+    test_shift "print/x $lhs << 0" " = $lhs"
+    test_shift "print/x $lhs >> 0" " = $lhs"
+
+    test_shift "print $lhs >> 32" " = 0" $too_large_shift
+    test_shift "print $lhs << 32" " = 0" $too_large_shift
+
+    test_shift "print $lhs >> 33" " = 0" $too_large_shift
+    test_shift "print $lhs << 33" " = 0" $too_large_shift
+}
+
+# 64-bit lhs, signed and unsigned.
+foreach lhs {0x7fffffffffffffff 0xffffffffffffffff} {
+    test_shift "print $lhs >> -1" " = 0" $negative_shift
+    test_shift "print $lhs << -1" " = 0" $negative_shift
+
+    # Confirm shifting by 0 doesn't warn.
+    test_shift "print/x $lhs << 0" " = $lhs"
+    test_shift "print/x $lhs >> 0" " = $lhs"
+
+    test_shift "print $lhs >> 64" " = 0" $too_large_shift
+    test_shift "print $lhs << 64" " = 0" $too_large_shift
+
+    test_shift "print $lhs >> 65" " = 0" $too_large_shift
+    test_shift "print $lhs << 65" " = 0" $too_large_shift
+}
+
+# Right shift a negative number by a negative amount.
+test_shift "print -1 >> -1" " = 0" $negative_shift
+
+# Check right shifting a negative value.  This is
+# implementation-defined, up until C++20.  In most implementations,
+# this performs an arithmetic right shift, so that the result remains
+# negative.  Currently, GDB does whatever the host's compiler does.
+# If that turns out wrong for some host/target, then GDB should be
+# taught to ask the target gdbarch what to do.
+test_shift "print -1 >> 0" " = -1"
+test_shift "print -1 >> 1" " = -1"
+test_shift "print -8 >> 1" " = -4"
+test_shift "print -8l >> 1" " = -4"
+test_shift "print -8ll >> 1" " = -4"
diff --git a/gdb/valarith.c b/gdb/valarith.c
index 36d30f161f6..44f1dc2c826 100644
--- a/gdb/valarith.c
+++ b/gdb/valarith.c
@@ -1070,6 +1070,39 @@ complex_binop (struct value *arg1, struct value *arg2, enum exp_opcode op)
   return value_literal_complex (result_real, result_imag, result_type);
 }
 
+/* Return the type's length in bits.  */
+
+static int
+type_length_bits (type *type)
+{
+  int unit_size = gdbarch_addressable_memory_unit_size (type->arch ());
+  return unit_size * 8 * TYPE_LENGTH (type);
+}
+
+/* Check whether the RHS value of a shift is valid.  RHS_VAL is the
+   shift amount, and RESULT_TYPE is the result type.  This is used to
+   avoid both negative and too-large shift amounts, which are
+   undefined, and would crash a GDB built with UBSan.  Warns and
+   returns false if not valid, and returns true if not valid.  */
+
+static bool
+check_valid_shift_rhs (type *result_type, LONGEST rhs_val)
+{
+  if (rhs_val < 0)
+    {
+      warning (_("right shift count is negative"));
+      return false;
+    }
+
+  if (rhs_val >= type_length_bits (result_type))
+    {
+      warning (_("right shift count >= width of type"));
+      return false;
+    }
+
+  return true;
+}
+
 /* Perform a binary operation on two operands which have reasonable
    representations as integers or floats.  This includes booleans,
    characters, integers, or floats.
@@ -1233,11 +1266,17 @@ scalar_binop (struct value *arg1, struct value *arg2, enum exp_opcode op)
 	      break;
 
 	    case BINOP_LSH:
-	      v = v1 << v2;
+	      if (!check_valid_shift_rhs (result_type, v2))
+		v = 0;
+	      else
+		v = v1 << v2;
 	      break;
 
 	    case BINOP_RSH:
-	      v = v1 >> v2;
+	      if (!check_valid_shift_rhs (result_type, v2))
+		v = 0;
+	      else
+		v = v1 >> v2;
 	      break;
 
 	    case BINOP_BITWISE_AND:
@@ -1362,11 +1401,25 @@ scalar_binop (struct value *arg1, struct value *arg2, enum exp_opcode op)
 	      break;
 
 	    case BINOP_LSH:
-	      v = v1 << v2;
+	      if (!check_valid_shift_rhs (result_type, v2))
+		v = 0;
+	      else
+		{
+		  /* Cast to unsigned to avoid undefined behavior on
+		     signed shift overflow (unless C++20 or later),
+		     which would crash GDB when built with UBSan.
+		     Note we don't warn on left signed shift overflow,
+		     because starting with C++20, that is actually
+		     defined behavior.  */
+		  v = (ULONGEST) v1 << v2;
+		}
 	      break;
 
 	    case BINOP_RSH:
-	      v = v1 >> v2;
+	      if (!check_valid_shift_rhs (result_type, v2))
+		v = 0;
+	      else
+		v = v1 >> v2;
 	      break;
 
 	    case BINOP_BITWISE_AND:
-- 
2.26.2

Re: [PATCH v2 1/2] gdb: Avoid undefined shifts

[Tom Tromey]

>>>>> "Pedro" == Pedro Alves <pedro@palves.net> writes:

Pedro> Compilers don't error out on such shifts, at best they warn, so I
Pedro> think GDB should just continue doing the shifts anyhow too.

Pedro> - Adjust scalar_binop to avoid the undefined paths, either by adding
Pedro>   explicit result paths, or by casting the lhs of the left shift to
Pedro>   unsigned, as appropriate.  For the shifts by negative amount or a
Pedro>   too-large amount, I made the result be 0 (and warn).  This is
Pedro>   undefined, so we're free to pick any value, and 0 seems reasonable,
Pedro>   as it's what you'd get if you split a too-large shift by a number of
Pedro>   smaller valid shifts, and if you imagine a shift by a negative value
Pedro>   as a shift by a very-large unsigned value, you get the same too.

Pedro> - Make GDB warn for the cases that are still undefined in C++20.  The
Pedro>   warnings' texts are the same as what GCC prints.

I wonder whether any of the supported languages define shifts differently.
Rust is a bit vague about these cases, but I know Java had different
semantics (but OTOH Java would have had to implement its own expression
node for this anyway).

Anyway what I'm wondering is whether the warnings are always appropriate.

Pedro> +      warning (_("right shift count is negative"));

Pedro>  	    case BINOP_LSH:
Pedro> -	      v = v1 << v2;
Pedro> +	      if (!check_valid_shift_rhs (result_type, v2))

This is a left shift but the warning will mention a right shift.

Tom

Re: [PATCH v2 1/2] gdb: Avoid undefined shifts

[Pedro Alves]

On 2022-04-04 18:21, Tom Tromey wrote:
>>>>>> "Pedro" == Pedro Alves <pedro@palves.net> writes:
> 
> Pedro> Compilers don't error out on such shifts, at best they warn, so I
> Pedro> think GDB should just continue doing the shifts anyhow too.
> 
> Pedro> - Adjust scalar_binop to avoid the undefined paths, either by adding
> Pedro>   explicit result paths, or by casting the lhs of the left shift to
> Pedro>   unsigned, as appropriate.  For the shifts by negative amount or a
> Pedro>   too-large amount, I made the result be 0 (and warn).  This is
> Pedro>   undefined, so we're free to pick any value, and 0 seems reasonable,
> Pedro>   as it's what you'd get if you split a too-large shift by a number of
> Pedro>   smaller valid shifts, and if you imagine a shift by a negative value
> Pedro>   as a shift by a very-large unsigned value, you get the same too.
> 
> Pedro> - Make GDB warn for the cases that are still undefined in C++20.  The
> Pedro>   warnings' texts are the same as what GCC prints.
> 
> I wonder whether any of the supported languages define shifts differently.
> Rust is a bit vague about these cases, but I know Java had different
> semantics (but OTOH Java would have had to implement its own expression
> node for this anyway).
> 
> Anyway what I'm wondering is whether the warnings are always appropriate.

I was looking at that too a bit earlier today, and from here:

 https://www.alphacodingskills.com/rust/notes/rust-operator-left-shift.php

I ended up playing with this:

 https://www.cg.alphacodingskills.com/compile-rust-online.php

... 

 with expressions like:

  1_u64 << 64;
  1_u32 << 32;
  1_32 << 32;
  1 << -1;
  1_u32 << -1;

they all errored out with 

7 |   1_u64 << 64;
  |   ^^^^^^^^^^^ attempt to shift left by `64_i32`, which would overflow
  |
  = note: `#[deny(arithmetic_overflow)]` on by default


error: this arithmetic operation will overflow
 --> Main.rs:8:3
  |
8 |   1_u32 << 32;
  |   ^^^^^^^^^^^ attempt to shift left by `32_i32`, which would overflow

error: this arithmetic operation will overflow
 --> Main.rs:9:3
  |
9 |   1_32 << 32;
  |   ^^^^^^^^^^ attempt to shift left by `32_i32`, which would overflow

error: this arithmetic operation will overflow
  --> Main.rs:11:3
   |
11 |   1 << -1;
   |   ^^^^^^^ attempt to shift left by `-1_i32`, which would overflow

error: this arithmetic operation will overflow
  --> Main.rs:12:3
   |
12 |   1_u32 << -1;
   |   ^^^^^^^^^^^ attempt to shift left by `-1_i32`, which would overflow

error: aborting due to 5 previous errors


That "[deny(arithmetic_overflow)" made me google "rust arithmetic_overflow"
and I found references stating that you can disable overflow as a compiler
option, but I didn't try it.  I saw some references about overflow being
undefined, so I suppose warning is at least not incorrect for Rust.


I looked a bit at what D would do, all I could find is that it follows C's semantics.
">>" is arithmetic/signed shift, and there's a ">>>" operator for unsigned shift.


I looked a bit more now.  

For Golang, it seems like we shouldn't warn on too-large shifts.  Here:

 https://yourbasic.org/golang/bitwise-operator-cheat-sheet/

 ~~~
 00110101<<100	00000000	No upper limit on shift count
 ~~~

and negative numbers should be an error, it seems:

 "The bitwise operators take both signed and unsigned integers as input. The right-hand side of a shift operator, however, must be an unsigned integer."


I haven't yet looked up how >>100 should behave.  It may be that
-1 >> 100 should do an arithmetic shift and thus yield -1 instead of 0.


Looks like no other language uses BINOP_LSH, etc.


In any case, to be clear, if the semantics for a given language are different, then
it must be that we're already implementing them incorrectly, since the shifts are
currently translated to C++ shifts done on the host.

> 
> Pedro> +      warning (_("right shift count is negative"));
> 
> Pedro>  	    case BINOP_LSH:
> Pedro> -	      v = v1 << v2;
> Pedro> +	      if (!check_valid_shift_rhs (result_type, v2))
> 
> This is a left shift but the warning will mention a right shift.
> 

Thanks, don't know how I missed this.  I'll fix it.

Re: [PATCH v2 1/2] gdb: Avoid undefined shifts

[Tom Tromey]

Pedro> In any case, to be clear, if the semantics for a given language are different, then
Pedro> it must be that we're already implementing them incorrectly, since the shifts are
Pedro> currently translated to C++ shifts done on the host.

Makes sense, thanks.

Tom

[PATCH v2 2/2] Avoid undefined behavior in gdbscm_make_breakpoint

[Pedro Alves]

Running gdb.guile/scm-breakpoint.exp against an --enable-ubsan build,
we see:

 UNRESOLVED: gdb.guile/scm-breakpoint.exp: test_watchpoints: create a breakpoint with an invalid type number
 ...
 guile (define wp2 (make-breakpoint "result" #:wp-class WP_WRITE #:type 999))
 ../../src/gdb/guile/scm-breakpoint.c:377:11: runtime error: load of value 999, which is not a valid value for type 'bptype'
 ERROR: GDB process no longer exists

Fix this by parsing the user/guile input as plain int, and cast to
internal type only after we know we have a number that would be valid.

Change-Id: I03578d07db00be01b610a8f5ce72e5521aea6a4b
---
 gdb/guile/scm-breakpoint.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/gdb/guile/scm-breakpoint.c b/gdb/guile/scm-breakpoint.c
index 0069d3371ff..d6c89aa8c71 100644
--- a/gdb/guile/scm-breakpoint.c
+++ b/gdb/guile/scm-breakpoint.c
@@ -353,8 +353,8 @@ gdbscm_make_breakpoint (SCM location_scm, SCM rest)
   char *location;
   int type_arg_pos = -1, access_type_arg_pos = -1,
       internal_arg_pos = -1, temporary_arg_pos = -1;
-  enum bptype type = bp_breakpoint;
-  enum target_hw_bp_type access_type = hw_write;
+  int type = bp_breakpoint;
+  int access_type = hw_write;
   int internal = 0;
   int temporary = 0;
   SCM result;
@@ -403,7 +403,7 @@ gdbscm_make_breakpoint (SCM location_scm, SCM rest)
     case bp_access_watchpoint:
     case bp_catchpoint:
       {
-	const char *type_name = bpscm_type_to_string (type);
+	const char *type_name = bpscm_type_to_string ((enum bptype) type);
 	gdbscm_misc_error (FUNC_NAME, type_arg_pos,
 			   gdbscm_scm_from_c_string (type_name),
 			   _("unsupported breakpoint type"));
@@ -417,8 +417,8 @@ gdbscm_make_breakpoint (SCM location_scm, SCM rest)
 
   bp_smob->is_scheme_bkpt = 1;
   bp_smob->spec.location = location;
-  bp_smob->spec.type = type;
-  bp_smob->spec.access_type = access_type;
+  bp_smob->spec.type = (enum bptype) type;
+  bp_smob->spec.access_type = (enum target_hw_bp_type) access_type;
   bp_smob->spec.is_internal = internal;
   bp_smob->spec.is_temporary = temporary;
 
-- 
2.26.2

Re: [PATCH v2 2/2] Avoid undefined behavior in gdbscm_make_breakpoint

[Tom Tromey]

>>>>> "Pedro" == Pedro Alves <pedro@palves.net> writes:

Pedro> Fix this by parsing the user/guile input as plain int, and cast to
Pedro> internal type only after we know we have a number that would be valid.

This looks good.

Tom

Re: [PATCH v2 2/2] Avoid undefined behavior in gdbscm_make_breakpoint

[Pedro Alves]

On 2022-04-04 18:15, Tom Tromey wrote:
>>>>>> "Pedro" == Pedro Alves <pedro@palves.net> writes:
> 
> Pedro> Fix this by parsing the user/guile input as plain int, and cast to
> Pedro> internal type only after we know we have a number that would be valid.
> 
> This looks good.

Thanks, I've pushed this one.