[Morello] Capability data relocations

Introduce three new relocations disguised as two relocations to
support capabilities.

R_MORELLO_CAPINIT is emitted as a static relocation by the assembler
and as a dynamic relocation by the linker; it's a one on one free!

The R_MORELLO_CAPINIT static relocation is emitted by the assembler to
provide capability information to the static linker.  The static
linker may do one of two things:

- For local symbols that can be resolved at link time, the static
  linker sets up frag and emits a R_MORELLO_RELATIVE dynamic
  relocation that the dynamic linker can resolve in a manner similar
  to R_AARCH64_RELATIVE.  The dynamic linker will have all of the
  information it needs (i.e. permissions, size and relative address)
  to set up the capability without needing to peek into the symbol
  table.

- For dynamic symbols, the static linker emits a R_MORELLO_CAPINIT
  with the reference of the dynamic symbol it refers to.  The dynamic
  linker is then responsible for resolving the symbol at runtime and
  setting up the capability based on the properties of the symbol it
  is able to deduce.

Linker and Linker script defined symbols
----------------------------------------

For symbols defined by the linker or in linker scripts, capability
size and permissions are based on the section the symbol belongs to.

For linker defined symbols (i.e. _DYNAMIC or _GLOBAL_OFFSET_TABLE_)
this is straightforward since the linker puts them in the correct
section and at the start.

For symbols defined in the linker script, if they are anywhere but the
end of the output script definition, their range becomes the point at
which they are defined, up to the end of the output section.  For
symbols defined at the end of the output section, the symbols are
defined with a zero size unless their name is of the form __start_.*
or __.*_start, indicating a start of the section that follows it.  In
this case, the symbols are given the range and permission of the
output section following it.

Ideally, the last case (i.e. the heuristic looking for the name)
should be strictly for compatibility and should eventually be fixed in
the linker script to put the symbol into the output section it intends
to track.  It may be a useful enhancement to add a warning to that
effect.

bfd/ChangeLog:

2020-10-20  Siddhesh Poyarekar  <siddesh.poyarekar@arm.com>

	* elfnn-aarch64.c (elfNN_aarch64_howto_table,
	elfNN_aarch64_final_link_relocate, elfNN_aarch64_check_relocs,
	elfNN_aarch64_relocate_section): Add R_MORELLO_CAPINIT and
	R_MORELLO_RELATIVE.
	(elf_aarch64_link_hash_table): New member srelcaps.
	(c64_valid_cap_range, exponent, cap_meta,
	section_start_symbol, c64_fixup_frag): New functions.
	* elfxx-aarch64.c (_bfd_aarch64_elf_put_addend,
	_bfd_aarch64_elf_resolve_relocation): Add
	BFD_RELOC_MORELLO_CAPINIT and BFD_RELOC_MORELLO_RELATIVE.
	* libbfd.h (bfd_reloc_code_real_names): Likewise.
	* reloc.c: Likewise.
	* bfd-in2.h: Regenerate.

gas/ChangeLog:

2020-10-20  Siddhesh Poyarekar  <siddesh.poyarekar@arm.com>

	* config/tc-aarch64.c (s_aarch64_capinit): New function.
	(md_pseudo_table): Use it.
	(md_apply_fix): Add BFD_RELOC_MORELLO_CAPINIT.
	(aarch64_fix_adjustable): Return FALSE for capabilities.
	* testsuite/gas/aarch64/morello-capinit.d: New test file.
	* testsuite/gas/aarch64/morello-capinit.s: Likewise.

include/ChangeLog:

2020-10-20  Siddhesh Poyarekar  <siddesh.poyarekar@arm.com>

	* elf/aarch64.h (R_MORELLO_CAPINIT, R_MORELLO_RELATIVE): New
	relocations.

ld/ChangeLog:

2020-10-20  Siddhesh Poyarekar  <siddesh.poyarekar@arm.com>

	* testsuite/ld-aarch64/aarch64-elf.exp: Add test.
	* testsuite/ld-aarch64/morello-capinit.d: New file.
	* testsuite/ld-aarch64/morello-capinit.ld: New file.
	* testsuite/ld-aarch64/morello-capinit.s: New file.

6 files changed, 330 insertions, 0 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index dcec7b2f264..7a1c8b737bf 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,5 +1,21 @@
 2020-10-20  Siddhesh Poyarekar  <siddesh.poyarekar@arm.com>
 
+	* elfnn-aarch64.c (elfNN_aarch64_howto_table,
+	elfNN_aarch64_final_link_relocate, elfNN_aarch64_check_relocs,
+	elfNN_aarch64_relocate_section): Add R_MORELLO_CAPINIT and
+	R_MORELLO_RELATIVE.
+	(elf_aarch64_link_hash_table): New member srelcaps.
+	(c64_valid_cap_range, exponent, cap_meta,
+	section_start_symbol, c64_fixup_frag): New functions.
+	* elfxx-aarch64.c (_bfd_aarch64_elf_put_addend,
+	_bfd_aarch64_elf_resolve_relocation): Add
+	BFD_RELOC_MORELLO_CAPINIT and BFD_RELOC_MORELLO_RELATIVE.
+	* libbfd.h (bfd_reloc_code_real_names): Likewise.
+	* reloc.c: Likewise.
+	* bfd-in2.h: Regenerate.
+
+2020-10-20  Siddhesh Poyarekar  <siddesh.poyarekar@arm.com>
+
 	* reloc.c: Add MORELLO_ADR_HI20_PCREL,
 	MORELLO_ADR_HI20_NC_PCREL and MORELLO_ADR_GOT_PAGE.
 	* elfnn-aarch64.c (elfNN_aarch64_howto_table): Likewise.
diff --git a/bfd/bfd-in2.h b/bfd/bfd-in2.h
index 01a2dccde4c..ed065af3c7b 100644
--- a/bfd/bfd-in2.h
+++ b/bfd/bfd-in2.h
@@ -5939,6 +5939,12 @@ instructions.  */
 /* AArch64 support for STT_GNU_IFUNC.  */
   BFD_RELOC_AARCH64_IRELATIVE,
 
+/* Morello Capability initialization.  */
+  BFD_RELOC_MORELLO_CAPINIT,
+
+/* Morello relative relocation for capabilities.  */
+  BFD_RELOC_MORELLO_RELATIVE,
+
 /* AArch64 pseudo relocation code to mark the end of the AArch64
 relocation enumerators that have direct mapping to ELF reloc codes.
 There are a few more enumerators after this one; those are mainly
diff --git a/bfd/elfnn-aarch64.c b/bfd/elfnn-aarch64.c
index 0cc63cc2889..c945572ed91 100644
--- a/bfd/elfnn-aarch64.c
+++ b/bfd/elfnn-aarch64.c
@@ -2213,6 +2213,34 @@ static reloc_howto_type elfNN_aarch64_howto_table[] =
 	 ALL_ONES,		/* dst_mask */
 	 FALSE),		/* pcrel_offset */
 
+  HOWTO64 (MORELLO_R (CAPINIT),	/* type */
+	 0,			/* rightshift */
+	 4,			/* size (0 = byte, 1 = short, 2 = long) */
+	 0,			/* bitsize */
+	 FALSE,			/* pc_relative */
+	 0,			/* bitpos */
+	 complain_overflow_dont,	/* complain_on_overflow */
+	 bfd_elf_generic_reloc,	/* special_function */
+	 MORELLO_R_STR (CAPINIT),	/* name */
+	 FALSE,			/* partial_inplace */
+	 ALL_ONES,		/* src_mask */
+	 ALL_ONES,		/* dst_mask */
+	 FALSE),		/* pcrel_offset */
+
+  HOWTO64 (MORELLO_R (RELATIVE),	/* type */
+	 0,			/* rightshift */
+	 2,			/* size (0 = byte, 1 = short, 2 = long) */
+	 64,			/* bitsize */
+	 FALSE,			/* pc_relative */
+	 0,			/* bitpos */
+	 complain_overflow_bitfield,	/* complain_on_overflow */
+	 bfd_elf_generic_reloc,	/* special_function */
+	 MORELLO_R_STR (RELATIVE),	/* name */
+	 TRUE,			/* partial_inplace */
+	 ALL_ONES,		/* src_mask */
+	 ALL_ONES,		/* dst_mask */
+	 FALSE),		/* pcrel_offset */
+
   EMPTY_HOWTO (0),
 };
 
@@ -2827,6 +2855,9 @@ struct elf_aarch64_link_hash_table
   /* Used by local STT_GNU_IFUNC symbols.  */
   htab_t loc_hash_table;
   void * loc_hash_memory;
+
+  /* Used for capability relocations.  */
+  asection *srelcaps;
 };
 
 /* Create an entry in an AArch64 ELF linker hash table.  */
@@ -5544,6 +5575,189 @@ aarch64_relocation_aginst_gp_p (bfd_reloc_code_real_type reloc)
 	  || reloc == BFD_RELOC_AARCH64_MOVW_GOTOFF_G1);
 }
 
+/* Capability format functions.  */
+
+static unsigned
+exponent (uint64_t len)
+{
+#define CAP_MAX_EXPONENT 50
+  /* Size is a 65 bit value, so there's an implicit 0 MSB.  */
+  unsigned zeroes = __builtin_clzl (len) + 1;
+
+  /* All bits up to and including CAP_MW - 2 are zero.  */
+  if (CAP_MAX_EXPONENT < zeroes)
+    return (unsigned) -1;
+  else
+    return CAP_MAX_EXPONENT - zeroes;
+#undef CAP_MAX_EXPONENT
+}
+
+#define ONES(x)         ((1ULL << ((x) + 1)) - 1)
+#define ALIGN_UP(x, a)  (((x) + ONES (a)) & (~ONES (a)))
+
+static bfd_boolean
+c64_valid_cap_range (bfd_vma *basep, bfd_vma *limitp)
+{
+  bfd_vma base = *basep, size = *limitp - *basep;
+
+  unsigned e, old_e;
+
+  if ((e = exponent (size)) == (unsigned) -1)
+    return TRUE;
+
+  size = ALIGN_UP (size, e + 3);
+  old_e = e;
+  e = exponent (size);
+  if (old_e != e)
+    size = ALIGN_UP (size, e + 3);
+
+  base = ALIGN_UP (base, e + 3);
+
+  if (base == *basep && *limitp == base + size)
+    return TRUE;
+
+  *basep = base;
+  *limitp = base + size;
+  return FALSE;
+}
+
+
+/* Build capability meta data, i.e. size and permissions for a capability.  */
+
+static bfd_vma
+cap_meta (size_t size, const asection *sec)
+{
+
+  if (size >= (1ULL << 56))
+    return (bfd_vma) -1;
+
+  size <<= 8;
+  if (sec->flags & SEC_READONLY
+      || sec->flags & SEC_ROM)
+    return size | 1;
+  if (sec->flags & SEC_CODE)
+    return size | 4;
+  if (sec->flags & SEC_ALLOC)
+    return size | 2;
+
+  /* We should always be able to derive a valid set of permissions
+     from the section flags.  */
+  abort ();
+}
+
+static bfd_boolean
+section_start_symbol (bfd *abfd ATTRIBUTE_UNUSED, asection *section,
+		      void *valp)
+{
+  return section->vma == *(bfd_vma *)valp;
+}
+
+static bfd_reloc_status_type
+c64_fixup_frag (bfd *input_bfd, struct bfd_link_info *info,
+		bfd_reloc_code_real_type bfd_r_type, Elf_Internal_Sym *sym,
+		struct elf_link_hash_entry *h, asection *sym_sec,
+		bfd_byte *frag_loc, bfd_vma value, bfd_signed_vma addend)
+{
+  bfd_vma size = 0;
+  asection *perm_sec = sym_sec;
+  bfd_boolean bounds_ok = FALSE;
+
+  if (sym != NULL)
+    {
+      size = sym->st_size;
+      if (size == 0)
+	goto need_size;
+    }
+  else if (h != NULL)
+    {
+      size = h->size;
+
+      if (size == 0 && sym_sec != NULL)
+	{
+	  /* Linker defined symbols are always at the start of the section they
+	     track.  */
+	  if (h->root.linker_def)
+	    {
+	      size = sym_sec->output_section->size;
+	      bounds_ok = TRUE;
+	    }
+	  else if (h->root.ldscript_def)
+	    {
+	      const char *name = h->root.root.string;
+	      size_t len = strlen (name);
+
+	      /* In the general case, the symbol should be able to access the
+	         entire output section following it.  */
+	      size = sym_sec->size - (value - sym_sec->vma);
+
+	      /* The special case: the symbol is at the end of the section.
+		 This could either mean that it is an end symbol or it is the
+		 start of the output section following the symbol.  We try to
+		 guess if it is a start of the next section by reading its
+		 name.  This is a compatibility hack, ideally linker scripts
+		 should be written such that start symbols are defined within
+		 the output section it intends to track.  */
+	      if (size == 0
+		  && (len > 8 && name[0] == '_' && name[1] == '_'
+		      && (!strncmp (name + 2, "start_", 6)
+			  || !strcmp (name + len - 6, "_start"))))
+		{
+		  asection *s = bfd_sections_find_if (info->output_bfd,
+						      section_start_symbol,
+						      &value);
+		  if (s != NULL)
+		    {
+		      perm_sec = s;
+		      size = s->size;
+		    }
+		}
+	      bounds_ok = TRUE;
+	    }
+	  else if (size == 0 && bfd_link_pic (info)
+		   && SYMBOL_REFERENCES_LOCAL (info, h))
+	    goto need_size;
+	}
+    }
+
+  /* Negative addends are not allowed for capability symbols.  */
+  if (addend < 0 || (bfd_vma) addend > size)
+    return bfd_reloc_outofrange;
+
+  bfd_vma base = value + addend, limit = value + addend + size;
+
+  if (!bounds_ok && !c64_valid_cap_range (&base, &limit))
+    {
+      /* xgettext:c-format */
+      _bfd_error_handler (_("%pB: capability range may exceed object bounds"),
+			  input_bfd);
+      bfd_set_error (bfd_error_bad_value);
+      return bfd_reloc_notsupported;
+    }
+
+  if (perm_sec != NULL)
+    {
+      bfd_vma frag = cap_meta (size, perm_sec);
+
+      if (frag == (bfd_vma) -1)
+	return bfd_reloc_outofrange;
+
+      bfd_put_64 (input_bfd, frag, frag_loc);
+    }
+
+  return bfd_reloc_continue;
+
+need_size:
+    {
+      int howto_index = bfd_r_type - BFD_RELOC_AARCH64_RELOC_START;
+      _bfd_error_handler
+	/* xgettext:c-format */
+	(_("%pB: relocation %s against local symbol without size info"),
+	 input_bfd, elfNN_aarch64_howto_table[howto_index].name);
+      bfd_set_error (bfd_error_bad_value);
+      return bfd_reloc_notsupported;
+    }
+}
+
 /* Perform a relocation as part of a final link.  The input relocation type
    should be TLS relaxed.  */
 
@@ -6343,6 +6557,59 @@ elfNN_aarch64_final_link_relocate (reloc_howto_type *howto,
       *unresolved_reloc_p = FALSE;
       break;
 
+    case BFD_RELOC_MORELLO_CAPINIT:
+	{
+	  Elf_Internal_Rela outrel;
+
+	  if (input_section->flags & SEC_READONLY)
+	    {
+	      _bfd_error_handler
+		/* xgettext:c-format */
+		(_("%pB: capability relocation section must be writable"),
+		 input_bfd);
+	      bfd_set_error (bfd_error_bad_value);
+	      return bfd_reloc_notsupported;
+	    }
+
+	  outrel.r_offset = _bfd_elf_section_offset (output_bfd, info,
+						     input_section,
+						     rel->r_offset);
+
+	  outrel.r_offset += (input_section->output_section->vma
+			      + input_section->output_offset);
+
+	  /* Capability-aligned.  */
+	  if (outrel.r_offset & 0xf)
+	    return bfd_reloc_overflow;
+
+	  bfd_reloc_status_type ret;
+
+	  ret = c64_fixup_frag (input_bfd, info, bfd_r_type, sym, h, sym_sec,
+				hit_data + 8, value, signed_addend);
+
+	  if (ret != bfd_reloc_continue)
+	    return ret;
+
+	  outrel.r_addend = signed_addend;
+
+	  /* Emit a dynamic relocation if we are building PIC.  */
+	  if (h != NULL
+	      && h->dynindx != -1
+	      && bfd_link_pic (info)
+	      && !SYMBOL_REFERENCES_LOCAL (info, h))
+	    outrel.r_info = ELFNN_R_INFO (h->dynindx, r_type);
+	  else
+	    outrel.r_info = ELFNN_R_INFO (0, MORELLO_R (RELATIVE));
+
+	  value |= (h != NULL ? h->target_internal : sym->st_target_internal);
+
+	  asection *s = globals->srelcaps;
+
+	  elf_append_rela (output_bfd, s, &outrel);
+	  *unresolved_reloc_p = FALSE;
+	}
+      break;
+
     default:
       return bfd_reloc_notsupported;
     }
@@ -7307,6 +7574,11 @@ symbol is being referenced in the indicated code as if it had a larger \
 alignment than was declared where it was defined"),
 		     name, input_bfd, input_section, rel->r_offset);
 		}
+
+	      if (real_r_type == BFD_RELOC_MORELLO_CAPINIT)
+		info->callbacks->warning
+		  (info, _("relocation offset must be capability aligned"),
+		   name, input_bfd, input_section, rel->r_offset);
 	      break;
 
 	    case bfd_reloc_undefined:
@@ -8168,6 +8440,25 @@ elfNN_aarch64_check_relocs (bfd *abfd, struct bfd_link_info *info,
 	    h->plt.refcount += 1;
 	  break;
 
+	case BFD_RELOC_MORELLO_CAPINIT:
+	  if (htab->srelcaps == NULL)
+	    {
+	      if (htab->root.dynobj == NULL)
+		htab->root.dynobj = abfd;
+
+	      sreloc = _bfd_elf_make_dynamic_reloc_section
+		(sec, htab->root.dynobj, LOG_FILE_ALIGN,
+		 abfd, /*rela? */ TRUE);
+
+	      if (sreloc == NULL)
+		return FALSE;
+
+	      htab->srelcaps = sreloc;
+	    }
+	  htab->srelcaps->size += RELOC_SIZE (htab);
+
+	  break;
+
 	default:
 	  break;
 	}
diff --git a/bfd/elfxx-aarch64.c b/bfd/elfxx-aarch64.c
index 82e725e8c1d..d16a0578608 100644
--- a/bfd/elfxx-aarch64.c
+++ b/bfd/elfxx-aarch64.c
@@ -381,6 +381,10 @@ _bfd_aarch64_elf_put_addend (bfd *abfd,
       contents = reencode_movw_imm (contents, addend);
       break;
 
+    case BFD_RELOC_MORELLO_CAPINIT:
+      contents = addend;
+      break;
+
     default:
       /* Repack simple data */
       if (howto->dst_mask & (howto->dst_mask + 1))
@@ -589,6 +593,9 @@ _bfd_aarch64_elf_resolve_relocation (bfd *input_bfd,
       value -= place & ~(bfd_vma) 0xffffffff;
       break;
 
+    case BFD_RELOC_MORELLO_CAPINIT:
+      value += addend;
+
     default:
       break;
     }
diff --git a/bfd/libbfd.h b/bfd/libbfd.h
index a5e30ce2bb0..877a6d677c2 100644
--- a/bfd/libbfd.h
+++ b/bfd/libbfd.h
@@ -3107,6 +3107,8 @@ static const char *const bfd_reloc_code_real_names[] = { "@@uninitialized@@",
   "BFD_RELOC_AARCH64_TLS_TPREL",
   "BFD_RELOC_AARCH64_TLSDESC",
   "BFD_RELOC_AARCH64_IRELATIVE",
+  "BFD_RELOC_MORELLO_CAPINIT",
+  "BFD_RELOC_MORELLO_RELATIVE",
   "BFD_RELOC_AARCH64_RELOC_END",
   "BFD_RELOC_AARCH64_GAS_INTERNAL_FIXUP",
   "BFD_RELOC_AARCH64_LDST_LO12",
diff --git a/bfd/reloc.c b/bfd/reloc.c
index 1d2eefd02b2..674d6c4e5f0 100644
--- a/bfd/reloc.c
+++ b/bfd/reloc.c
@@ -7530,6 +7530,14 @@ ENUM
 ENUMDOC
   AArch64 support for STT_GNU_IFUNC.
 ENUM
+  BFD_RELOC_MORELLO_CAPINIT
+ENUMDOC
+  Morello Capability initialization.
+ENUM
+  BFD_RELOC_MORELLO_RELATIVE
+ENUMDOC
+  Morello relative relocation for capabilities.
+ENUM
   BFD_RELOC_AARCH64_RELOC_END
 ENUMDOC
   AArch64 pseudo relocation code to mark the end of the AArch64