Re: reloc overflows

[Alan Modra <alan at SPRI dot Levels dot UniSA dot Edu dot Au>]

On 11 Mar 2000, Ian Lance Taylor wrote:

>    Date: Sat, 11 Mar 2000 13:02:04 +1030 (CST)
>    From: Alan Modra <alan@SPRI.Levels.UniSA.Edu.Au>
> 
>    Moving the hack up a little will cure the problem by
>    effectively saying that if bits_per_address == 32 then a 32-bit bitfield
>    reloc can't overflow (which is what you get when compiling with a 32-bit
>    bfd).  I don't particularly like this solution though as we might as well
>    remove all the bitfield overflow checking.
> 
> I think that might be right, though.  We won't actually be removing
> the overflow checking.  We will only be removing the overflow checking
> for a 32 bit relocation.  I think that might be right.  If
> bits_per_address == 32, then a 32 bit bitfield relocation can't really
> overflow.

This is splitting hairs, but I think if we do this, then with this
contrived example

$ cat jmp.s
.extern foo
 jmp foo
$ gas/ld/ld-new -Ttext 0 -e 0 -defsym foo=0x123456789 jmp.o
jmp.o(.text+0x1): relocation truncated to fit: R_386_PC32 foo

you wouldn't see a warning.

Linking the above example using a 32-bit bfd is even worse at the moment.
foo is silently limited to 0xffffffff.

>    My alternative solution, which also fixes the 16-bit reloc problem, is to
>    say that a bitfield reloc of n bits can represent numbers in the range
>    -(2**n) to 2**n-1.  The current range allowed is -(2**(n-1)) to 2**n-1,
>    ie. overlap of n bit signed and unsigned numbers.
> 
>    What do you all think of this?
> 
> I guess I can see some logic to that.

OK, here is some code.  Maybe that will stimulate some more discussion.

Index: reloc.c
===================================================================
RCS file: /cvs/src/src/bfd/reloc.c,v
retrieving revision 1.14
diff -u -p -r1.14 reloc.c
--- reloc.c	2000/03/11 01:16:52	1.14
+++ reloc.c	2000/03/12 07:44:52
@@ -540,17 +540,14 @@ bfd_check_overflow (how, bitsize, rights
 
     case complain_overflow_bitfield:
       /* Bitfields are sometimes signed, sometimes unsigned.  We
-         overflow if the value has some, but not all, bits set outside
-         the field, or if it has any bits set outside the field but
-         the sign bit is not set.  */
+	 explicitly allow an address wrap too, which means a bitfield
+	 of n bits is allowed to store -2**n to 2**n-1.  Thus overflow
+	 if the value has some, but not all, bits set outside the
+	 field.  */
       a >>= rightshift;
-      if ((a & ~ fieldmask) != 0)
-	{
-	  signmask = (fieldmask >> 1) + 1;
-	  ss = (signmask << rightshift) - 1;
-	  if ((ss | relocation) != ~ (bfd_vma) 0)
-	    flag = bfd_reloc_overflow;
-	}
+      ss = a & ~ fieldmask;
+      if (ss != 0 && ss != (((bfd_vma) -1 >> rightshift) & ~ fieldmask))
+	flag = bfd_reloc_overflow;
       break;
 
     default:
@@ -1428,7 +1425,7 @@ _bfd_relocate_contents (howto, input_bfd
 {
   int size;
   bfd_vma x = 0;
-  boolean overflow;
+  bfd_reloc_status_type flag;
   unsigned int rightshift = howto->rightshift;
   unsigned int bitpos = howto->bitpos;
 
@@ -1466,7 +1463,7 @@ _bfd_relocate_contents (howto, input_bfd
      which we don't check for.  We must either check at every single
      operation, which would be tedious, or we must do the computations
      in a type larger than bfd_vma, which would be inefficient.  */
-  overflow = false;
+  flag = bfd_reloc_ok;
   if (howto->complain_on_overflow != complain_overflow_dont)
     {
       bfd_vma addrmask, fieldmask, signmask, ss;
@@ -1492,7 +1489,7 @@ _bfd_relocate_contents (howto, input_bfd
 	  signmask = ~ (fieldmask >> 1);
 	  ss = a & signmask;
 	  if (ss != 0 && ss != ((addrmask >> rightshift) & signmask))
-	    overflow = true;
+	    flag = bfd_reloc_overflow;
 
 	  /* We only need this next bit of code if the sign bit of B
              is below the sign bit of A.  This would only happen if
@@ -1522,7 +1519,7 @@ _bfd_relocate_contents (howto, input_bfd
 	     */
 	  signmask = (fieldmask >> 1) + 1;
 	  if (((~ (a ^ b)) & (a ^ sum)) & signmask)
-	    overflow = true;
+	    flag = bfd_reloc_overflow;
 
 	  break;
 
@@ -1542,65 +1539,36 @@ _bfd_relocate_contents (howto, input_bfd
 	  b = (b & addrmask) >> bitpos;
 	  sum = (a + b) & addrmask;
 	  if ((a | b | sum) & ~ fieldmask)
-	    overflow = true;
+	    flag = bfd_reloc_overflow;
 
 	  break;
 
 	case complain_overflow_bitfield:
-	  /* Much like unsigned, except no trimming with addrmask.  In
-             addition, the sum overflows if there is a carry out of
-             the bfd_vma, i.e., the sum is less than either input
-             operand.  */
+	  /* Much like the signed check, but for a field one bit
+	     wider, and no trimming with addrmask.  We allow a
+	     bitfield to represent numbers in the range -2**n to
+	     2**n-1, where n is the number of bits in the field.
+	     Note that when bfd_vma is 32 bits, a 32-bit reloc can't
+	     overflow, which is exactly what we want.  */
 	  a >>= rightshift;
-	  b >>= bitpos;
-
-	  /* Bitfields are sometimes used for signed numbers; for
-             example, a 13-bit field sometimes represents values in
-             0..8191 and sometimes represents values in -4096..4095.
-             If the field is signed and a is -4095 (0x1001) and b is
-             -1 (0x1fff), the sum is -4096 (0x1000), but (0x1001 +
-             0x1fff is 0x3000).  It's not clear how to handle this
-             everywhere, since there is no way to know how many bits
-             are significant in the relocation, but the original code
-             assumed that it was fully sign extended, and we will keep
-             that assumption.  */
-	  signmask = (fieldmask >> 1) + 1;
 
-	  if ((a & ~ fieldmask) != 0)
-	    {
-	      /* Some bits out of the field are set.  This might not
-                 be a problem: if this is a signed bitfield, it is OK
-                 if all the high bits are set, including the sign
-                 bit.  We'll try setting all but the most significant
-                 bit in the original relocation value: if this is all
-                 ones, we are OK, assuming a signed bitfield.  */
-	      ss = (signmask << rightshift) - 1;
-	      if ((ss | relocation) != ~ (bfd_vma) 0)
-		overflow = true;
-	      a &= fieldmask;
-	    }
+	  signmask = ~ fieldmask;
+	  ss = a & signmask;
+	  if (ss != 0 && ss != (((bfd_vma) -1 >> rightshift) & signmask))
+	    flag = bfd_reloc_overflow;
 
-	  /* We just assume (b & ~ fieldmask) == 0.  */
+	  signmask = ((~ howto->src_mask) >> 1) & howto->src_mask;
+	  if ((b & signmask) != 0)
+	    b -= signmask << 1;
 
-	  /* We explicitly permit wrap around if this relocation
-	     covers the high bit of an address.  The Linux kernel
-	     relies on it, and it is the only way to write assembler
-	     code which can run when loaded at a location 0x80000000
-	     away from the location at which it is linked.  */
-	  if (howto->bitsize + rightshift
-	      == bfd_arch_bits_per_address (input_bfd))
-	    break;
+	  b >>= bitpos;
 
 	  sum = a + b;
-	  if (sum < a || (sum & ~ fieldmask) != 0)
-	    {
-	      /* There was a carry out, or the field overflowed.  Test
-                 for signed operands again.  Here the overflow test is
-                 as for complain_overflow_signed.  */
-	      if (((~ (a ^ b)) & (a ^ sum)) & signmask)
-		overflow = true;
-	    }
 
+	  signmask = fieldmask + 1;
+	  if (((~ (a ^ b)) & (a ^ sum)) & signmask)
+	    flag = bfd_reloc_overflow;
+
 	  break;
 
 	default:
@@ -1640,7 +1608,7 @@ _bfd_relocate_contents (howto, input_bfd
       break;
     }
 
-  return overflow ? bfd_reloc_overflow : bfd_reloc_ok;
+  return flag;
 }
 
 /*