[PATCH] add section caches to coff_data_type

[PATCH] add section caches to coff_data_type

[Oleg Tolmatcev]

Hello all,

final patch to ld. All the patches together improve linking
performance from 9 minutes to 1 minute when linking rpcs3 in debug
mode with BUILD_LLVM=ON.

---
 bfd/coff-x86_64.c | 35 +++++++++++++++++++++++------------
 bfd/coffgen.c     | 27 +++++++++++++++++++++++++--
 bfd/libcoff-in.h  |  6 ++++++
 bfd/libcoff.h     |  6 ++++++
 bfd/peicode.h     | 35 +++++++++++++++++++++++++++++++++++
 5 files changed, 95 insertions(+), 14 deletions(-)

diff --git a/bfd/coff-x86_64.c b/bfd/coff-x86_64.c
index 822504a339..09291e2455 100644
--- a/bfd/coff-x86_64.c
+++ b/bfd/coff-x86_64.c
@@ -745,23 +745,34 @@ coff_amd64_rtype_to_howto (bfd *abfd ATTRIBUTE_UNUSED,

   if (rel->r_type == R_AMD64_SECREL)
     {
-      bfd_vma osect_vma;
+      bfd_vma osect_vma = 0;

       if (h && (h->root.type == bfd_link_hash_defined
         || h->root.type == bfd_link_hash_defweak))
     osect_vma = h->root.u.def.section->output_section->vma;
       else
-    {
-      asection *s;
-      int i;
-
-      /* Sigh, the only way to get the section to offset against
-         is to find it the hard way.  */
-      for (s = abfd->sections, i = 1; i < sym->n_scnum; i++)
-        s = s->next;
-
-      osect_vma = s->output_section->vma;
-    }
+        {
+          asection *s;
+
+          /* Sigh, the only way to get the section to offset against
+             is to find it the hard way.  */
+
+          if (htab_elements (coff_data (abfd)->section_by_index) == 0)
+            {
+              for (s = abfd->sections; s != NULL; s = s->next)
+                {
+                  void **slot
+                      = htab_find_slot (coff_data
(abfd)->section_by_index, s, INSERT);
+                  if (slot != NULL)
+                    *slot = s;
+                }
+            }
+          struct bfd_section needle;
+          needle.index = sym->n_scnum - 1;
+          s = htab_find (coff_data (abfd)->section_by_index, &needle);
+          if (s != NULL)
+            osect_vma = s->output_section->vma;
+        }

       *addendp -= osect_vma;
     }
diff --git a/bfd/coffgen.c b/bfd/coffgen.c
index 05f2640abe..326a7dbd88 100644
--- a/bfd/coffgen.c
+++ b/bfd/coffgen.c
@@ -42,6 +42,7 @@
 #include "libbfd.h"
 #include "coff/internal.h"
 #include "libcoff.h"
+#include "hashtab.h"

 /* Take a section header read from a coff file (in HOST byte order),
    and make a BFD "section" out of it.  This is used by ECOFF.  */
@@ -360,8 +361,6 @@ coff_object_p (bfd *abfd)
 asection *
 coff_section_from_bfd_index (bfd *abfd, int section_index)
 {
-  struct bfd_section *answer = abfd->sections;
-
   if (section_index == N_ABS)
     return bfd_abs_section_ptr;
   if (section_index == N_UNDEF)
@@ -369,6 +368,30 @@ coff_section_from_bfd_index (bfd *abfd, int section_index)
   if (section_index == N_DEBUG)
     return bfd_abs_section_ptr;

+  struct bfd_section *answer;
+
+  if (htab_elements (coff_data (abfd)->section_by_target_index) == 0)
+    {
+      answer = abfd->sections;
+      while (answer)
+        {
+          void **slot
+              = htab_find_slot (coff_data
(abfd)->section_by_target_index, answer, INSERT);
+          if (slot == NULL)
+            return bfd_und_section_ptr;
+          *slot = answer;
+          answer = answer->next;
+        }
+    }
+
+  struct bfd_section needle;
+  needle.target_index = section_index;
+
+  answer = htab_find (coff_data (abfd)->section_by_target_index, &needle);
+  if (answer != NULL)
+    return answer;
+
+  answer = abfd->sections;
   while (answer)
     {
       if (answer->target_index == section_index)
diff --git a/bfd/libcoff-in.h b/bfd/libcoff-in.h
index cdd504605b..6f4109931c 100644
--- a/bfd/libcoff-in.h
+++ b/bfd/libcoff-in.h
@@ -130,6 +130,12 @@ typedef struct coff_tdata
      COFF object into memory.  */
   char * stub;
   bfd_size_type stub_size;
+
+  /* hash table containing sections by target index */
+  htab_t section_by_target_index;
+
+  /* hash table containing sections by index */
+  htab_t section_by_index;
 } coff_data_type;

 /* Tdata for pe image files.  */
diff --git a/bfd/libcoff.h b/bfd/libcoff.h
index b58ee8aded..0cb335ee8d 100644
--- a/bfd/libcoff.h
+++ b/bfd/libcoff.h
@@ -133,6 +133,12 @@ typedef struct coff_tdata
      COFF object into memory.  */
   char * stub;
   bfd_size_type stub_size;
+
+  /* hash table containing sections by target index */
+  htab_t section_by_target_index;
+
+  /* hash table containing sections by index */
+  htab_t section_by_index;
 } coff_data_type;

 /* Tdata for pe image files.  */
diff --git a/bfd/peicode.h b/bfd/peicode.h
index df1e678b5a..c60961be9f 100644
--- a/bfd/peicode.h
+++ b/bfd/peicode.h
@@ -274,6 +274,36 @@ htab_eq_flags (const void *e1, const void *e2)
          && fe1->target_index == fe2->target_index;
 }

+static hashval_t
+htab_hash_section_index (const void *entry)
+{
+  const struct bfd_section *sec = entry;
+  return sec->index;
+}
+
+static int
+htab_eq_section_index (const void *e1, const void *e2)
+{
+  const struct bfd_section *sec1 = e1;
+  const struct bfd_section *sec2 = e2;
+  return sec1->index == sec2->index;
+}
+
+static hashval_t
+htab_hash_section_target_index (const void *entry)
+{
+  const struct bfd_section *sec = entry;
+  return sec->target_index;
+}
+
+static int
+htab_eq_section_target_index (const void *e1, const void *e2)
+{
+  const struct bfd_section *sec1 = e1;
+  const struct bfd_section *sec2 = e2;
+  return sec1->target_index == sec2->target_index;
+}
+
 static bool
 pe_mkobject (bfd * abfd)
 {
@@ -373,6 +403,11 @@ pe_mkobject_hook (bfd * abfd,
   memcpy (pe->dos_message, internal_f->pe.dos_message,
       sizeof (pe->dos_message));

+  pe->coff.section_by_index
+      = htab_create (10, htab_hash_section_index, htab_eq_section_index, NULL);
+  pe->coff.section_by_target_index = htab_create (
+      10, htab_hash_section_target_index, htab_eq_section_target_index, NULL);
+
   return (void *) pe;
 }

-- 
2.40.0.windows.1

Re: [PATCH] add section caches to coff_data_type

[Nick Clifton]

Hi Oleg,

> final patch to ld. All the patches together improve linking
> performance from 9 minutes to 1 minute when linking rpcs3 in debug
> mode with BUILD_LLVM=ON.

Unfortunately there are two problems with this patch:

   1.  It does not initialise the new fields in the coff_tdata
       structure for targets that just use the COFF file format
       rather than the PE file format.  (ie you need to duplicate
       the patch to peicode.h in the coffcode.h file).

   2.  (Actually more important): We either need a copyright
       assignment from you, or else you need to sign off on the
       patch before we can accept it.  To assign the copyright
       you should fill out one of the forms here and then send
       it off to the FSF:

https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=tree;f=doc/Copyright;h=22db9a802b4da96ad455cd933351c1359108f95d;hb=HEAD

       Alternatively you can attach a developer's certificate of
       origin to your patch, which is easier in the short term, but
       does need to be done with every patch submission.  More details
       here:

https://sourceware.org/binutils/wiki/HowToContribute

Cheers
   Nick

PS.  For your other two patches, I decided to treat them as "obvious"
   so no copyright assignment or DCO was needed.

Re: [PATCH] add section caches to coff_data_type

[Tom Tromey]

>>>>> Oleg Tolmatcev via Binutils <binutils@sourceware.org> writes:

> Hello all,
> final patch to ld. All the patches together improve linking
> performance from 9 minutes to 1 minute when linking rpcs3 in debug
> mode with BUILD_LLVM=ON.

> +  pe->coff.section_by_index
> +      = htab_create (10, htab_hash_section_index, htab_eq_section_index, NULL);
> +  pe->coff.section_by_target_index = htab_create (
> +      10, htab_hash_section_target_index, htab_eq_section_target_index, NULL);

I think something has to call htab_delete on these to avoid a memory leak.

Tom

Re: [PATCH] add section caches to coff_data_type

[Oleg Tolmatcev]

Am Do., 4. Mai 2023 um 13:29 Uhr schrieb Nick Clifton <nickc@redhat.com>:
>
> Hi Oleg,
>
> > final patch to ld. All the patches together improve linking
> > performance from 9 minutes to 1 minute when linking rpcs3 in debug
> > mode with BUILD_LLVM=ON.
>
> Unfortunately there are two problems with this patch:
>
>    1.  It does not initialise the new fields in the coff_tdata
>        structure for targets that just use the COFF file format
>        rather than the PE file format.  (ie you need to duplicate
>        the patch to peicode.h in the coffcode.h file).
>
>    2.  (Actually more important): We either need a copyright
>        assignment from you, or else you need to sign off on the
>        patch before we can accept it.  To assign the copyright
>        you should fill out one of the forms here and then send
>        it off to the FSF:
>
> https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=tree;f=doc/Copyright;h=22db9a802b4da96ad455cd933351c1359108f95d;hb=HEAD
>
>        Alternatively you can attach a developer's certificate of
>        origin to your patch, which is easier in the short term, but
>        does need to be done with every patch submission.  More details
>        here:
>
> https://sourceware.org/binutils/wiki/HowToContribute

Thanks for the review. I have attached the certificate and signed the
patch. I don't know where to free the hash tables, that's why I didn't
do it. The new patch is below.


Developer Certificate of Origin
Version 1.1

Copyright (C) 2004, 2006 The Linux Foundation and its contributors.

Everyone is permitted to copy and distribute verbatim copies of this
license document, but changing it is not allowed.

Developer's Certificate of Origin 1.1

By making a contribution to this project, I certify that:

(a) The contribution was created in whole or in part by me and I
    have the right to submit it under the open source license
    indicated in the file; or

(b) The contribution is based upon previous work that, to the best
    of my knowledge, is covered under an appropriate open source
    license and I have the right under that license to submit that
    work with modifications, whether created in whole or in part
    by me, under the same open source license (unless I am
    permitted to submit under a different license), as indicated
    in the file; or

(c) The contribution was provided directly to me by some other
    person who certified (a), (b) or (c) and I have not modified
    it.

(d) I understand and agree that this project and the contribution
    are public and that a record of the contribution (including all
    personal information I submit with it, including my sign-off) is
    maintained indefinitely and may be redistributed consistent with
    this project or the open source license(s) involved.

Signed-off-by: Oleg Tolmatcev <oleg.tolmatcev@gmail.com>
---
 bfd/coff-x86_64.c | 21 ++++++++++++++++-----
 bfd/coffcode.h    | 35 +++++++++++++++++++++++++++++++++++
 bfd/coffgen.c     | 27 +++++++++++++++++++++++++--
 bfd/libcoff-in.h  |  7 +++++++
 bfd/peicode.h     | 35 +++++++++++++++++++++++++++++++++++
 5 files changed, 118 insertions(+), 7 deletions(-)

diff --git a/bfd/coff-x86_64.c b/bfd/coff-x86_64.c
index 822504a339..c62802bdf4 100644
--- a/bfd/coff-x86_64.c
+++ b/bfd/coff-x86_64.c
@@ -745,7 +745,7 @@ coff_amd64_rtype_to_howto (bfd *abfd ATTRIBUTE_UNUSED,

   if (rel->r_type == R_AMD64_SECREL)
     {
-      bfd_vma osect_vma;
+      bfd_vma osect_vma = 0;

       if (h && (h->root.type == bfd_link_hash_defined
         || h->root.type == bfd_link_hash_defweak))
@@ -753,14 +753,25 @@ coff_amd64_rtype_to_howto (bfd *abfd ATTRIBUTE_UNUSED,
       else
     {
       asection *s;
-      int i;

       /* Sigh, the only way to get the section to offset against
          is to find it the hard way.  */
-      for (s = abfd->sections, i = 1; i < sym->n_scnum; i++)
-        s = s->next;

-      osect_vma = s->output_section->vma;
+      if (htab_elements (coff_data (abfd)->section_by_index) == 0)
+        {
+          for (s = abfd->sections; s != NULL; s = s->next)
+        {
+          void **slot = htab_find_slot (
+              coff_data (abfd)->section_by_index, s, INSERT);
+          if (slot != NULL)
+            *slot = s;
+        }
+        }
+      struct bfd_section needle;
+      needle.index = sym->n_scnum - 1;
+      s = htab_find (coff_data (abfd)->section_by_index, &needle);
+      if (s != NULL)
+        osect_vma = s->output_section->vma;
     }

       *addendp -= osect_vma;
diff --git a/bfd/coffcode.h b/bfd/coffcode.h
index 974c8ad985..3792c84ab1 100644
--- a/bfd/coffcode.h
+++ b/bfd/coffcode.h
@@ -731,6 +731,36 @@ sec_to_styp_flags (const char *sec_name, flagword
sec_flags)

 #ifndef COFF_WITH_PE

+static hashval_t
+htab_hash_section_index (const void *entry)
+{
+  const struct bfd_section *sec = entry;
+  return sec->index;
+}
+
+static int
+htab_eq_section_index (const void *e1, const void *e2)
+{
+  const struct bfd_section *sec1 = e1;
+  const struct bfd_section *sec2 = e2;
+  return sec1->index == sec2->index;
+}
+
+static hashval_t
+htab_hash_section_target_index (const void *entry)
+{
+  const struct bfd_section *sec = entry;
+  return sec->target_index;
+}
+
+static int
+htab_eq_section_target_index (const void *e1, const void *e2)
+{
+  const struct bfd_section *sec1 = e1;
+  const struct bfd_section *sec2 = e2;
+  return sec1->target_index == sec2->target_index;
+}
+
 static bool
 styp_to_sec_flags (bfd *abfd,
            void * hdr,
@@ -2154,6 +2184,11 @@ coff_mkobject_hook (bfd * abfd,
     abfd->flags |= HAS_DEBUG;
 #endif

+  coff->section_by_index
+      = htab_create (10, htab_hash_section_index, htab_eq_section_index, NULL);
+  coff->section_by_target_index = htab_create (
+      10, htab_hash_section_target_index, htab_eq_section_target_index, NULL);
+
   return coff;
 }
 #endif
diff --git a/bfd/coffgen.c b/bfd/coffgen.c
index ac936def56..d11bc03f56 100644
--- a/bfd/coffgen.c
+++ b/bfd/coffgen.c
@@ -42,6 +42,7 @@
 #include "libbfd.h"
 #include "coff/internal.h"
 #include "libcoff.h"
+#include "hashtab.h"

 /* Take a section header read from a coff file (in HOST byte order),
    and make a BFD "section" out of it.  This is used by ECOFF.  */
@@ -360,8 +361,6 @@ coff_object_p (bfd *abfd)
 asection *
 coff_section_from_bfd_index (bfd *abfd, int section_index)
 {
-  struct bfd_section *answer = abfd->sections;
-
   if (section_index == N_ABS)
     return bfd_abs_section_ptr;
   if (section_index == N_UNDEF)
@@ -369,6 +368,30 @@ coff_section_from_bfd_index (bfd *abfd, int section_index)
   if (section_index == N_DEBUG)
     return bfd_abs_section_ptr;

+  struct bfd_section *answer;
+
+  if (htab_elements (coff_data (abfd)->section_by_target_index) == 0)
+    {
+      answer = abfd->sections;
+      while (answer)
+    {
+      void **slot = htab_find_slot (
+          coff_data (abfd)->section_by_target_index, answer, INSERT);
+      if (slot == NULL)
+        return bfd_und_section_ptr;
+      *slot = answer;
+      answer = answer->next;
+    }
+    }
+
+  struct bfd_section needle;
+  needle.target_index = section_index;
+
+  answer = htab_find (coff_data (abfd)->section_by_target_index, &needle);
+  if (answer != NULL)
+    return answer;
+
+  answer = abfd->sections;
   while (answer)
     {
       if (answer->target_index == section_index)
diff --git a/bfd/libcoff-in.h b/bfd/libcoff-in.h
index d0839c76e9..ecd19397cb 100644
--- a/bfd/libcoff-in.h
+++ b/bfd/libcoff-in.h
@@ -24,6 +24,7 @@

 #include "bfdlink.h"
 #include "coff-bfd.h"
+#include "hashtab.h"

 #ifdef __cplusplus
 extern "C" {
@@ -129,6 +130,12 @@ typedef struct coff_tdata
      COFF object into memory.  */
   char * stub;
   bfd_size_type stub_size;
+
+  /* hash table containing sections by target index */
+  htab_t section_by_target_index;
+
+  /* hash table containing sections by index */
+  htab_t section_by_index;
 } coff_data_type;

 /* Tdata for pe image files.  */
diff --git a/bfd/peicode.h b/bfd/peicode.h
index e2e2be65b5..e0b89d33ff 100644
--- a/bfd/peicode.h
+++ b/bfd/peicode.h
@@ -255,6 +255,36 @@ coff_swap_scnhdr_in (bfd * abfd, void * ext, void * in)
 #endif
 }

+static hashval_t
+htab_hash_section_index (const void *entry)
+{
+  const struct bfd_section *sec = entry;
+  return sec->index;
+}
+
+static int
+htab_eq_section_index (const void *e1, const void *e2)
+{
+  const struct bfd_section *sec1 = e1;
+  const struct bfd_section *sec2 = e2;
+  return sec1->index == sec2->index;
+}
+
+static hashval_t
+htab_hash_section_target_index (const void *entry)
+{
+  const struct bfd_section *sec = entry;
+  return sec->target_index;
+}
+
+static int
+htab_eq_section_target_index (const void *e1, const void *e2)
+{
+  const struct bfd_section *sec1 = e1;
+  const struct bfd_section *sec2 = e2;
+  return sec1->target_index == sec2->target_index;
+}
+
 static bool
 pe_mkobject (bfd * abfd)
 {
@@ -352,6 +382,11 @@ pe_mkobject_hook (bfd * abfd,
   memcpy (pe->dos_message, internal_f->pe.dos_message,
       sizeof (pe->dos_message));

+  pe->coff.section_by_index
+      = htab_create (10, htab_hash_section_index, htab_eq_section_index, NULL);
+  pe->coff.section_by_target_index = htab_create (
+      10, htab_hash_section_target_index, htab_eq_section_target_index, NULL);
+
   return (void *) pe;
 }

-- 
2.40.1.windows.1

Re: [PATCH] add section caches to coff_data_type

[Nick Clifton]

Hi Oleg,

> Thanks for the review. I have attached the certificate and signed the
> patch. I don't know where to free the hash tables, that's why I didn't
> do it. The new patch is below.

I have gone ahead and applied your patch, with the addition of some extra
code to bfd/coffgen.c:_bfd_coff_close_and_cleanup() to free the hash tables.

Cheers
   Nick

Re: [PATCH] add section caches to coff_data_type

[Oleg Tolmatcev]

Am Di., 16. Mai 2023 um 15:28 Uhr schrieb Nick Clifton <nickc@redhat.com>:
>
> Hi Oleg,
>
> > Thanks for the review. I have attached the certificate and signed the
> > patch. I don't know where to free the hash tables, that's why I didn't
> > do it. The new patch is below.
>
> I have gone ahead and applied your patch, with the addition of some extra
> code to bfd/coffgen.c:_bfd_coff_close_and_cleanup() to free the hash tables.

Thanks a lot Nick.