[PATCH] Re: _bfd_elf_parse_eh_frame() should not assume relocation order?

[Alexey Neyman <stilor at att dot net>]

On Tuesday, December 17, 2013 08:48:13 AM H.J. Lu wrote:
> On Tue, Dec 17, 2013 at 8:19 AM, Alexey Neyman <stilor@att.net> wrote:
> > On Tuesday, December 17, 2013 10:00:21 PM Alan Modra wrote:
> >> On Tue, Dec 17, 2013 at 01:02:03AM -0800, Alexey Neyman wrote:
> >> > The problem is that after 'ld -r' linking, the resulting .rela.eh_frame
> >> > is
> >> > not
> >> 
> >> > sorted by the r_offset:
> >> Why are you using ld -r?  Just to package up object files?  Not a good
> >> idea.
> > 
> > Yes, in order to post-process the resulting object file localize the
> > symbols for interfaces private to a module - limiting the exposure of
> > interfaces.> 
> > But that was not the question:
> >>  As you have discovered, ld -r reorders things.
> > 
> > The question was, is it allowed to do so? Why shouldn't it sort the
> > relocations when writing the resulting object if it expects such ordering
> > on input?
> 
> I think it should be allowed.
> 
> > The `info ld' states the following about the -r option:
> >      Generate relocatable output--i.e., generate an output file that can
> >      in turn serve as input to 'ld'.  This is often called "partial
> >      linking".
> > 
> > I don't see how this description can be interpreted to say "`ld -r' can
> > mess things up to the point ld itself will produce errors when trying to
> > link the object file previously produced by ld".
> > 
> > So, is it a bug in BFD?
> 
> Please open a binutils bug.

Done, proposed patch attached to the bug and to this email.

https://sourceware.org/bugzilla/show_bug.cgi?id=16345

Regards,
Alexey.

>From 63984be23dee3df45590f25e176ce4985691ebb3 Mon Sep 17 00:00:00 2001
From: Alexey Neyman <stilor@att.net>
Date: Wed, 18 Dec 2013 12:11:29 -0800
Subject: [PATCH] Allow .eh_frame reader to cope with unordered relocations

Unordered relocations can result from partial linking of file with different
text sections (e.g., .text and .init).
---
 bfd/elf-eh-frame.c | 149 +++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 127 insertions(+), 22 deletions(-)

diff --git a/bfd/elf-eh-frame.c b/bfd/elf-eh-frame.c
index 832a991..2457c4f 100644
--- a/bfd/elf-eh-frame.c
+++ b/bfd/elf-eh-frame.c
@@ -457,6 +457,107 @@ _bfd_elf_begin_eh_frame_parsing (struct bfd_link_info *info)
   hdr_info->merge_cies = !info->relocatable;
 }
 
+struct reloc_read_ops
+{
+  Elf_Internal_Rela * (*chk_relocs) (struct elf_reloc_cookie *,
+      bfd_vma, bfd_vma);
+  Elf_Internal_Rela * (*get_reloc) (struct elf_reloc_cookie *, bfd_vma);
+  void (*skip_relocs) (struct elf_reloc_cookie *, bfd_vma, bfd_vma *);
+};
+
+/* Implementation of the ENSURE_NO_RELOCS macro for ordered relocations. */
+static Elf_Internal_Rela *
+_bfd_chk_relocs_ordered (struct elf_reloc_cookie *cookie,
+			 bfd_vma rels_offset ATTRIBUTE_UNUSED,
+			 bfd_vma offset)
+{
+  /* FIXME: octets_per_byte.  */
+  if (cookie->rel < cookie->relend
+      && cookie->rel->r_offset < offset
+      && cookie->rel->r_info != 0)
+    return cookie->rel;
+  return NULL;
+}
+
+/* Implementation of the GET_RELOC macro for ordered relocations. */
+static Elf_Internal_Rela *
+_bfd_get_reloc_ordered (struct elf_reloc_cookie *cookie, bfd_vma offset)
+{
+  /* FIXME: octets_per_byte.  */
+  return cookie->rel < cookie->relend && cookie->rel->r_offset == offset
+    ? cookie->rel : NULL;
+}
+
+/* Implementation of the SKIP_RELOCS macro for ordered relocations. */
+static void
+_bfd_skip_relocs_ordered (struct elf_reloc_cookie *cookie, bfd_vma offset,
+			  bfd_vma *rels_offset ATTRIBUTE_UNUSED)
+{
+  /* FIXME: octets_per_byte.  */
+  while (cookie->rel < cookie->relend && cookie->rel->r_offset < offset)
+    cookie->rel++;
+}
+
+static struct reloc_read_ops _bfd_eh_ordered_relocs = {
+  .chk_relocs = _bfd_chk_relocs_ordered,
+  .get_reloc = _bfd_get_reloc_ordered,
+  .skip_relocs = _bfd_skip_relocs_ordered,
+};
+
+/* Implementation of the ENSURE_NO_RELOCS macro for unordered relocations. */
+static Elf_Internal_Rela *
+_bfd_chk_relocs_unordered (struct elf_reloc_cookie *cookie,
+			   bfd_vma rels_offset, bfd_vma offset)
+{
+  Elf_Internal_Rela *rel;
+
+  /* FIXME: octets_per_byte.  */
+  for (rel = cookie->rels; rel < cookie->relend; rel++)
+    if (rel->r_offset >= rels_offset
+	&& rel->r_offset < offset
+	&& rel->r_info != 0)
+      return rel;
+  return NULL;
+}
+
+/* Implementation of the GET_RELOC macro for unordered relocations. */
+static Elf_Internal_Rela *
+_bfd_get_reloc_unordered (struct elf_reloc_cookie *cookie, bfd_vma offset)
+{
+  Elf_Internal_Rela *rel;
+
+  /* FIXME: octets_per_byte.  */
+  for (rel = cookie->rels; rel < cookie->relend; rel++)
+    if (rel->r_offset == offset)
+      return rel;
+  return NULL;
+}
+
+/* Implementation of the SKIP_RELOCS macro for unordered relocations. */
+static void
+_bfd_skip_relocs_unordered (struct elf_reloc_cookie *cookie, bfd_vma offset,
+			    bfd_vma *rels_offset)
+{
+  Elf_Internal_Rela *rel, *best = NULL;
+  bfd_vma best_offs = -1;
+
+  /* FIXME: octets_per_byte.  */
+  *rels_offset = offset;
+  for (rel = cookie->rels; rel < cookie->relend; rel++)
+    if (rel->r_offset >= offset && rel->r_offset - offset < best_offs)
+      {
+	best = rel;
+	best_offs = rel->r_offset - offset;
+      }
+  cookie->rel = best ? best : cookie->relend;
+}
+
+static struct reloc_read_ops _bfd_eh_unordered_relocs = {
+  .chk_relocs = _bfd_chk_relocs_unordered,
+  .get_reloc = _bfd_get_reloc_unordered,
+  .skip_relocs = _bfd_skip_relocs_unordered,
+};
+
 /* Try to parse .eh_frame section SEC, which belongs to ABFD.  Store the
    information in the section's sec_info field on success.  COOKIE
    describes the relocations in SEC.  */
@@ -473,6 +574,8 @@ _bfd_elf_parse_eh_frame (bfd *abfd, struct bfd_link_info *info,
 
   bfd_byte *ehbuf = NULL, *buf, *end;
   bfd_byte *last_fde;
+  bfd_size_type sec_info_size = 0;
+  bfd_vma rels_offset = 0;
   struct eh_cie_fde *this_inf;
   unsigned int hdr_length, hdr_id;
   unsigned int cie_count;
@@ -484,6 +587,7 @@ _bfd_elf_parse_eh_frame (bfd *abfd, struct bfd_link_info *info,
   unsigned int num_cies;
   unsigned int num_entries;
   elf_gc_mark_hook_fn gc_mark_hook;
+  struct reloc_read_ops *rr_ops = NULL;
 
   htab = elf_hash_table (info);
   hdr_info = &htab->eh_info;
@@ -552,37 +656,32 @@ _bfd_elf_parse_eh_frame (bfd *abfd, struct bfd_link_info *info,
       REQUIRE (skip_bytes (&buf, end, hdr_length - 4));
     }
 
-  sec_info = (struct eh_frame_sec_info *)
-      bfd_zmalloc (sizeof (struct eh_frame_sec_info)
-                   + (num_entries - 1) * sizeof (struct eh_cie_fde));
+  sec_info_size = sizeof (struct eh_frame_sec_info)
+    + (num_entries - 1) * sizeof (struct eh_cie_fde);
+  sec_info = (struct eh_frame_sec_info *) bfd_zmalloc (sec_info_size);
   REQUIRE (sec_info);
 
   /* We need to have a "struct cie" for each CIE in this section.  */
   local_cies = (struct cie *) bfd_zmalloc (num_cies * sizeof (*local_cies));
   REQUIRE (local_cies);
 
-  /* FIXME: octets_per_byte.  */
+  /* Start with the assumption that relocations are ordered by offset */
+  rr_ops = &_bfd_eh_ordered_relocs;
+
 #define ENSURE_NO_RELOCS(buf)				\
-  REQUIRE (!(cookie->rel < cookie->relend		\
-	     && (cookie->rel->r_offset			\
-		 < (bfd_size_type) ((buf) - ehbuf))	\
-	     && cookie->rel->r_info != 0))
+  REQUIRE (!(rr_ops->chk_relocs (cookie, rels_offset,	\
+	  (buf) - ehbuf)))
 
-  /* FIXME: octets_per_byte.  */
 #define SKIP_RELOCS(buf)				\
-  while (cookie->rel < cookie->relend			\
-	 && (cookie->rel->r_offset			\
-	     < (bfd_size_type) ((buf) - ehbuf)))	\
-    cookie->rel++
+  (rr_ops->skip_relocs (cookie, (buf) - ehbuf,		\
+			&rels_offset))
 
-  /* FIXME: octets_per_byte.  */
 #define GET_RELOC(buf)					\
-  ((cookie->rel < cookie->relend			\
-    && (cookie->rel->r_offset				\
-	== (bfd_size_type) ((buf) - ehbuf)))		\
-   ? cookie->rel : NULL)
+  (rr_ops->get_reloc (cookie, (buf) - ehbuf))
 
+restart_reading:
   buf = ehbuf;
+  SKIP_RELOCS(buf);
   cie_count = 0;
   gc_mark_hook = get_elf_backend_data (abfd)->gc_mark_hook;
   while ((bfd_size_type) (buf - ehbuf) != sec->size)
@@ -718,11 +817,9 @@ _bfd_elf_parse_eh_frame (bfd *abfd, struct bfd_link_info *info,
 		      REQUIRE (GET_RELOC (buf));
 		      cie->personality.reloc_index
 			= cookie->rel - cookie->rels;
-		      /* Cope with MIPS-style composite relocations.  */
-		      do
-			cookie->rel++;
-		      while (GET_RELOC (buf) != NULL);
 		      REQUIRE (skip_bytes (&buf, end, per_width));
+		      /* Cope with MIPS-style composite relocations.  */
+		      SKIP_RELOCS(buf);
 		    }
 		    break;
 		  default:
@@ -913,6 +1010,14 @@ _bfd_elf_parse_eh_frame (bfd *abfd, struct bfd_link_info *info,
   goto success;
 
  free_no_table:
+  if (rr_ops == &_bfd_eh_ordered_relocs)
+    {
+      /* Perhaps, relocations are out of order. Retry with slower version
+         that does not require ordering. */
+      rr_ops = &_bfd_eh_unordered_relocs;
+      memset(sec_info, 0, sec_info_size);
+      goto restart_reading;
+    }
   (*info->callbacks->einfo)
     (_("%P: error in %B(%A); no .eh_frame_hdr table will be created.\n"),
      abfd, sec);
-- 
1.8.4.1