From 6849c6a2b8f4588a30eaf83a58a3d2c38c6cae60 Mon Sep 17 00:00:00 2001
From: Pedro Alves <pedro@palves.net>
Date: Fri, 1 Apr 2022 13:26:57 +0100
Subject: [PATCH] gdb: Avoid undefined shifts, fix Go shifts

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 a too-large count, I made the result be what you'd
  get if you split the large count in a series of smaller shifts.
  Thus:

     Left shift, positive or negative lhs:

       V << 64
	 =>  V << 16 << 16 << 16 << 16
	   => 0

     Right shift, positive lhs:

       Vpos >> 64
	 =>  Vpos >> 16 >> 16 >> 16 >> 16
	   => 0

     Right shift, negative lhs:

       Vneg >> 64
	 =>  Vneg >> 16 >> 16 >> 16 >> 16
	   => -1

  This is actually Go's semantics (the compiler really emits
  instructions to make it so that you get 0 or -1 if you have a
  too-large shift).  So for that language GDB does the shift and
  nothing else.  For other C-like languages where such a shift is
  undefined, GDB warns in addition to performing the shift.

  For shift by a negative count, for Go, this is a hard error.  For
  other languages, since their compilers only warn, I made GDB warn
  too.  The semantics I chose (we're free to pick them since this is
  undefined behavior) is as-if you had shifted by the count cast to
  unsigned, thus as if you had shifted by a too-large count, thus the
  same as the previous scenario illustrated above.

  Examples:

    (gdb) set language go
    (gdb) p 1 << 100
    $1 = 0
    (gdb) p -1 << 100
    $2 = 0
    (gdb) p 1 >> 100
    $3 = 0
    (gdb) p -1 >> 100
    $4 = -1
    (gdb) p -2 >> 100
    $5 = -1
    (gdb) p 1 << -1
    left shift count is negative

    (gdb) set language c
    (gdb) p -2 >> 100
    warning: right shift count >= width of type
    $6 = -1
    (gdb) p -2 << 100
    warning: left shift count >= width of type
    $7 = 0
    (gdb) p 1 << -1
    warning: left shift count is negative
    $8 = 0
    (gdb) p -1 >> -1
    warning: right shift count is negative
    $9 = -1

- The warnings' texts are the same as what GCC prints.

- Add comprehensive tests in a new gdb.base/bitshift.exp testcase, so
  that we exercise all these scenarios.

Change-Id: I8bcd5fa02de3114b7ababc03e65702d86ec8d45d
---
 gdb/testsuite/gdb.base/bitshift.exp | 368 ++++++++++++++++++++++++++++
 gdb/valarith.c                      | 103 +++++++-
 2 files changed, 467 insertions(+), 4 deletions(-)
 create mode 100644 gdb/testsuite/gdb.base/bitshift.exp

diff --git a/gdb/testsuite/gdb.base/bitshift.exp b/gdb/testsuite/gdb.base/bitshift.exp
new file mode 100644
index 00000000000..03f18b9ebe5
--- /dev/null
+++ b/gdb/testsuite/gdb.base/bitshift.exp
@@ -0,0 +1,368 @@
+# Copyright 2022 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program 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 General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test left and right bit shifting, in all languages that have such
+# operator.
+
+clean_restart
+
+# Test a print command that prints out RESULT_RE.  If WARNING_OR_ERROR
+# is non-empty, it is expected that for languages other than Go, GDB
+# prints this warning before the print result.  For Go, this is an
+# expected error.  If WARNING_OR_ERROR is empty, it is expected that
+# GDB prints no text other than the print result.
+proc test_shift {lang cmd result_re {warning_or_error ""}} {
+    set cmd_re [string_to_regexp $cmd]
+
+    if {$lang == "go"} {
+	if {$warning_or_error != ""} {
+	    set error_re "[string_to_regexp $warning_or_error]"
+	    gdb_test_multiple $cmd "" {
+		-re -wrap "^$cmd_re\r\n$error_re" {
+		    pass $gdb_test_name
+		}
+	    }
+	} else {
+	    gdb_test_multiple $cmd "" {
+		-re -wrap "^$cmd_re\r\n\\$$::decimal$result_re" {
+		    pass $gdb_test_name
+		}
+	    }
+	}
+    } else {
+	if {$warning_or_error != ""} {
+	    set warning_re "warning: [string_to_regexp $warning_or_error]\r\n"
+	} else {
+	    set warning_re ""
+	}
+
+	gdb_test_multiple $cmd "" {
+	    -re -wrap "^$cmd_re\r\n$warning_re\\$$::decimal$result_re" {
+		pass $gdb_test_name
+	    }
+	}
+    }
+}
+
+# Some warnings/errors GDB outputs.
+set rs_negative_shift_count "right shift count is negative"
+set rs_too_large_shift_count "right shift count >= width of type"
+set ls_negative_shift_count "left shift count is negative"
+set ls_too_large_shift_count "left shift count >= width of type"
+
+# Test a left shift that results in a too-large shift count warning in
+# all languages except Go.
+proc test_lshift_tl {lang cmd result_re} {
+    if {$lang != "go"} {
+	test_shift $lang $cmd $result_re $::ls_too_large_shift_count
+    } else {
+	test_shift $lang $cmd $result_re
+    }
+}
+
+# Test a right shift that results in a too-large shift count warning
+# in all languages except Go.
+proc test_rshift_tl {lang cmd result_re} {
+    if {$lang != "go"} {
+	test_shift $lang $cmd $result_re $::rs_too_large_shift_count
+    } else {
+	test_shift $lang $cmd $result_re
+    }
+}
+
+# Return VAL, an integer value converted/cast to the right type for
+# LANG.  SIGNED indicates whether the type should be signed or
+# unsigned.  BITS indicates the bit width of the type.  E.g., signed=0
+# and bits=32 results in:
+#   Go            =>  "uint($VAL)"
+#   D             =>  "cast(uint) $VAL"
+#   Rust          =>  "$VAL as i32"
+#   C/C++/others  =>  "(unsigned int) $VAL"
+proc make_val_cast {lang signed bits val} {
+    if {$lang == "go"} {
+	if {$signed} {
+	    set sign_prefix ""
+	} else {
+	    set sign_prefix "u"
+	}
+	return "${sign_prefix}int${bits}($val)"
+    } elseif {$lang == "d"} {
+	if {$signed} {
+	    set sign_prefix ""
+	} else {
+	    set sign_prefix "u"
+	}
+	if {$bits == 8} {
+	    set type "byte"
+	} elseif {$bits == 16} {
+	    set type "short"
+	} elseif {$bits == 32} {
+	    set type "int"
+	} elseif {$bits == 64} {
+	    set type "long"
+	} else {
+	    error "$lang: unsupported bits"
+	}
+	return "cast(${sign_prefix}$type) $val"
+    } elseif {$lang == "rust"} {
+	if {$signed} {
+	    set sign_prefix "i"
+	} else {
+	    set sign_prefix "u"
+	}
+	return "$val as ${sign_prefix}$bits"
+    } else {
+	# C-like cast.
+	if {$signed} {
+	    set sign_prefix ""
+	} else {
+	    set sign_prefix "un"
+	}
+	if {$bits == 8} {
+	    set type "char"
+	} elseif {$bits == 16} {
+	    set type "short"
+	} elseif {$bits == 32} {
+	    set type "int"
+	} elseif {$bits == 64} {
+	    if {$lang == "opencl"} {
+		set type "long"
+	    } else {
+		set type "long long"
+	    }
+	} else {
+	    error "$lang: unsupported bits"
+	}
+	return "(${sign_prefix}signed $type) $val"
+    }
+}
+
+# Generate make_int8 ... make_uint64 convenience procs, wrappers
+# around make_val_cast.
+foreach signed {0 1} {
+    if {$signed} {
+	set sign_prefix ""
+    } else {
+	set sign_prefix "u"
+    }
+    foreach bits {8 16 32 64} {
+	proc make_${sign_prefix}int${bits} {lang val} \
+	    "make_val_cast \$lang $signed $bits \$val"
+    }
+}
+
+# Test bitshifting, particularly with negative shift counts and
+# too-large-for-type shift counts.  Exercises all C-like-ish
+# languages.
+proc test_shifts {} {
+    global ls_negative_shift_count rs_negative_shift_count
+
+    # Extract the set of all supported languages.  We try all except
+    # languages we know wouldn't work.  We do this instead of
+    # hardcoding the set of languages that we know work, so that if
+    # GDB gains a new language, it is automatically exercised.
+    set supported_langs [get_set_option_choices "set language"]
+
+    foreach_with_prefix lang $supported_langs {
+	set skip_langs {
+	    "unknown" "ada" "modula-2" "pascal" "fortran"
+	}
+	if {[lsearch -exact $skip_langs $lang] >= 0} {
+	    continue
+	}
+
+	gdb_test_no_output "set language $lang"
+
+	# 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.
+
+	with_test_prefix "lsh overflow" {
+	    test_shift $lang "print /x 0x0fffffffffffffff << 8" \
+		" = 0xffffffffffffff00"
+	    test_shift $lang "print /x 0x0fffffff << 8" \
+		" = 0xffffff00"
+
+	    # Make sure the result is still signed when the lhs was
+	    # signed.
+	    test_shift $lang "print 0x0fffffffffffffff << 8" " = -256"
+	    test_shift $lang "print 0x0fffffff << 8" " = -256"
+	}
+
+	# 8-bit and 16-bit are promoted to int.
+	with_test_prefix "8-bit, promoted" {
+	    foreach lhs \
+		[list \
+		     [make_int8 $lang 0x0f] \
+		     [make_uint8 $lang 0x0f]] \
+	    {
+		test_shift $lang "print /x $lhs << 8" " = 0xf00"
+		test_shift $lang "print $lhs << 8" " = 3840"
+	    }
+	}
+	with_test_prefix "16-bit, promoted" {
+	    foreach lhs \
+		[list \
+		     [make_int16 $lang 0x0fff] \
+		     [make_uint16 $lang 0x0fff]] \
+	    {
+		test_shift $lang "print /x $lhs << 8" " = 0xfff00"
+		test_shift $lang "print $lhs << 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.
+	with_test_prefix "8-bit, invalid" {
+	    foreach lhs \
+		[list \
+		     [make_int8 $lang 0x7f] \
+		     [make_uint8 $lang 0xff]] \
+	    {
+		test_shift $lang "print $lhs << -1" " = 0" \
+		    $ls_negative_shift_count
+		test_shift $lang "print $lhs >> -1" " = 0" \
+		    $rs_negative_shift_count
+
+		test_shift $lang "print/x $lhs << 8" " = 0x(7|f)f00"
+		test_shift $lang "print/x $lhs >> 8" " = 0x0"
+
+		test_lshift_tl $lang "print $lhs << 32" " = 0"
+		test_rshift_tl $lang "print $lhs >> 32" " = 0"
+		test_lshift_tl $lang "print $lhs << 33" " = 0"
+		test_rshift_tl $lang "print $lhs >> 33" " = 0"
+	    }
+	}
+
+	# 16-bit lhs, signed and unsigned.  These get promoted to 32-bit int.
+	with_test_prefix "16-bit, invalid" {
+	    foreach {lhs res} \
+		[list \
+		     [make_int16 $lang 0x7fff] 0x7fff \
+		     [make_uint16 $lang 0xffff] 0xffff] \
+	    {
+		test_shift $lang "print $lhs << -1" " = 0" \
+		    $ls_negative_shift_count
+		test_shift $lang "print $lhs >> -1" " = 0" \
+		    $rs_negative_shift_count
+
+		# Confirm shifting by 0 doesn't warn.
+		test_shift $lang "print/x $lhs << 0" " = $res"
+		test_shift $lang "print/x $lhs >> 0" " = $res"
+
+		# These don't overflow due to promotion.
+		test_shift $lang "print/x $lhs << 16" " = 0x(7|f)fff0000"
+		test_shift $lang "print/x $lhs >> 16" " = 0x0"
+
+		test_lshift_tl $lang "print $lhs << 32" " = 0"
+		test_rshift_tl $lang "print $lhs >> 32" " = 0"
+		test_lshift_tl $lang "print $lhs << 33" " = 0"
+		test_rshift_tl $lang "print $lhs >> 33" " = 0"
+	    }
+	}
+
+	# 32-bit lhs, signed and unsigned.
+	with_test_prefix "32-bit, invalid" {
+	    foreach {lhs res} \
+		[list \
+		     [make_int32 $lang 0x7fffffff] 0x7fffffff \
+		     [make_uint32 $lang 0xffffffff] 0xffffffff] \
+	    {
+		test_shift $lang "print $lhs << -1" " = 0" \
+		    $ls_negative_shift_count
+		test_shift $lang "print $lhs >> -1" " = 0" \
+		    $rs_negative_shift_count
+
+		# Confirm shifting by 0 doesn't warn.
+		test_shift $lang "print/x $lhs << 0" " = $res"
+		test_shift $lang "print/x $lhs >> 0" " = $res"
+
+		test_lshift_tl $lang "print $lhs << 32" " = 0"
+		test_rshift_tl $lang "print $lhs >> 32" " = 0"
+
+		test_lshift_tl $lang "print $lhs << 33" " = 0"
+		test_rshift_tl $lang "print $lhs >> 33" " = 0"
+	    }
+	}
+
+	# 64-bit lhs, signed and unsigned.
+	with_test_prefix "64-bit, invalid" {
+	    foreach {lhs res} \
+		[list \
+		     [make_int64 $lang 0x7fffffffffffffff] \
+		     0x7fffffffffffffff \
+		     \
+		     [make_uint64 $lang 0xffffffffffffffff] \
+		     0xffffffffffffffff] \
+	    {
+		test_shift $lang "print $lhs << -1" " = 0" \
+		    $ls_negative_shift_count
+		test_shift $lang "print $lhs >> -1" " = 0" \
+		    $rs_negative_shift_count
+
+		# Confirm shifting by 0 doesn't warn.
+		test_shift $lang "print/x $lhs << 0" " = $res"
+		test_shift $lang "print/x $lhs >> 0" " = $res"
+
+		test_lshift_tl $lang "print $lhs << 64" " = 0"
+		test_rshift_tl $lang "print $lhs >> 64" " = 0"
+
+		test_lshift_tl $lang "print $lhs << 65" " = 0"
+		test_rshift_tl $lang "print $lhs >> 65" " = 0"
+	    }
+	}
+
+	# Right shift a negative number by a negative amount.
+	with_test_prefix "neg lhs/rhs" {
+	    test_shift $lang "print -1 >> -1" " = -1" $rs_negative_shift_count
+	    test_shift $lang "print -4 >> -2" " = -1" $rs_negative_shift_count
+	}
+
+	# Check right shifting a negative value.  For C++, 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.
+	with_test_prefix "rsh neg lhs" {
+	    test_shift $lang "print -1 >> 0" " = -1"
+	    test_shift $lang "print -1 >> 1" " = -1"
+	    test_shift $lang "print -8 >> 1" " = -4"
+	    test_shift $lang "print [make_int64 $lang -8] >> 1" " = -4"
+	}
+
+	# Make sure an unsigned 64-bit value with high bit set isn't
+	# confused for a negative shift count in the warning messages.
+	with_test_prefix "max-uint64" {
+	    test_lshift_tl $lang \
+		"print 1 << [make_uint64 $lang 0xffffffffffffffff]" " = 0"
+	    test_rshift_tl $lang \
+		"print 1 >> [make_uint64 $lang 0xffffffffffffffff]" " = 0"
+	    test_lshift_tl $lang \
+		"print -1 << [make_uint64 $lang 0xffffffffffffffff]" " = 0"
+	    test_rshift_tl $lang \
+		"print -1 >> [make_uint64 $lang 0xffffffffffffffff]" " = -1"
+	}
+    }
+}
+
+test_shifts
diff --git a/gdb/valarith.c b/gdb/valarith.c
index 36d30f161f6..6210267826e 100644
--- a/gdb/valarith.c
+++ b/gdb/valarith.c
@@ -1070,6 +1070,66 @@ 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 in C/C++ semantics.
+   SHIFT_COUNT is the shift amount, SHIFT_COUNT_TYPE is the type of
+   the shift count value, used to determine whether the type is
+   signed, 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.  Depending on the current
+   language, if the shift is not valid, this either warns and returns
+   false, or errors out.  Returns true if valid.  */
+
+static bool
+check_valid_shift_count (int op, type *result_type,
+			 type *shift_count_type, ULONGEST shift_count)
+{
+  if (!shift_count_type->is_unsigned () && (LONGEST) shift_count < 0)
+    {
+      auto error_or_warning = [] (const char *msg)
+      {
+	/* Shifts by a negative amount are always an error in Go.  Other
+	   languages are more permissive and their compilers just warn or
+	   have modes to disable the errors.  */
+	if (current_language->la_language == language_go)
+	  error (("%s"), msg);
+	else
+	  warning (("%s"), msg);
+      };
+
+      if (op == BINOP_RSH)
+	error_or_warning (_("right shift count is negative"));
+      else
+	error_or_warning (_("left shift count is negative"));
+      return false;
+    }
+
+  if (shift_count >= type_length_bits (result_type))
+    {
+      /* In Go, shifting by large amounts is defined.  Be silent and
+	 still return false, as the caller's error path does the right
+	 thing for Go.  */
+      if (current_language->la_language != language_go)
+	{
+	  if (op == BINOP_RSH)
+	    warning (_("right shift count >= width of type"));
+	  else
+	    warning (_("left 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 +1293,17 @@ scalar_binop (struct value *arg1, struct value *arg2, enum exp_opcode op)
 	      break;
 
 	    case BINOP_LSH:
-	      v = v1 << v2;
+	      if (!check_valid_shift_count (op, result_type, type2, v2))
+		v = 0;
+	      else
+		v = v1 << v2;
 	      break;
 
 	    case BINOP_RSH:
-	      v = v1 >> v2;
+	      if (!check_valid_shift_count (op, result_type, type2, v2))
+		v = 0;
+	      else
+		v = v1 >> v2;
 	      break;
 
 	    case BINOP_BITWISE_AND:
@@ -1362,11 +1428,40 @@ scalar_binop (struct value *arg1, struct value *arg2, enum exp_opcode op)
 	      break;
 
 	    case BINOP_LSH:
-	      v = v1 << v2;
+	      if (!check_valid_shift_count (op, result_type, type2, 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.  Also, note GDB assumes 2's
+		     complement throughout.  */
+		  v = (ULONGEST) v1 << v2;
+		}
 	      break;
 
 	    case BINOP_RSH:
-	      v = v1 >> v2;
+	      if (!check_valid_shift_count (op, result_type, type2, v2))
+		{
+		  /* Pretend the too-large shift was decomposed in a
+		     number of smaller shifts.  An arithmetic signed
+		     right shift of a negative number always yields -1
+		     with such semantics.  This is the right thing to
+		     do for Go, and we might as well do it for
+		     languages where it is undefined.  Also, pretend a
+		     shift by a negative number was a shift by the
+		     negative number cast to unsigned, which is the
+		     same as shifting by a too-large number.  */
+		  if (v1 < 0)
+		    v = -1;
+		  else
+		    v = 0;
+		}
+	      else
+		v = v1 >> v2;
 	      break;
 
 	    case BINOP_BITWISE_AND:
-- 
2.30.2