Bug 17677 - _bfd_elf_get_synthetic_symtab runs in O(n^2) complexity
Summary: _bfd_elf_get_synthetic_symtab runs in O(n^2) complexity
Status: RESOLVED FIXED
Alias: None
Product: binutils
Classification: Unclassified
Component: binutils (show other bugs)
Version: 2.24
: P2 normal
Target Milestone: 2.25
Assignee: Not yet assigned to anyone
URL:
Keywords:
: 17764 (view as bug list)
Depends on:
Blocks:
 
Reported: 2014-12-03 19:16 UTC by Ori Bar
Modified: 2014-12-28 14:40 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ori Bar 2014-12-03 19:16:53 UTC
This bug was also reported here:
https://bugs.launchpad.net/ubuntu/+source/gdb/+bug/1388999

This bug causes a major slowdown for shared objects with many symbols (loading times gone from 1 minute to 15 minutes). One possible fix for this is to allocate an array of size n (n is the plt size) and fill it with the correct values via random access, doing only one pass on the binary.

I will illustrate this with pseudo code.

Here is the current algorithm, as implemented in _bfd_elf_get_synthetic_symtab's second for-loop.

    for i = 0 to count
      addr = bed->plt_sym_val(i, plt, p); // this function has average linear complexity
      // here addr is processed

I would replace the second for-loop with something like this (inspired by elf_x86_64_plt_sym_val):

    quick_plt_table = malloc(sizeof(bfd_vma) * count);
    for i = 0 to count
      if type_doesnt_match_backend()
          continue
      bfd_get_section_contents(abfd,..., reloc_index_raw);
      reloc_index = H_GET_32(abfd, reloc_index_raw);
      quick_plt_table[reloc_index] = plt->vma + plt_offset;
      plt_offset += bed->plt_entry_size;
      rel += int_rels_per_ext_rel;
    for i = 0 to count
      addr = quick_plt[i];
      // here addr is processed as done previously

Note that my version runs in linear complexity, and thus takes less time.
Comment 1 H.J. Lu 2014-12-03 21:48:16 UTC
For which target? i386, x86-64 or both?
Comment 2 Ori Bar 2014-12-04 11:17:43 UTC
For me it happened on x86-64 on a linux shared object with lots of exported symbols. I see no reason to assume this problem cannot happen on i386 though.
Comment 3 Sourceware Commits 2014-12-05 00:57:05 UTC
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "gdb and binutils".

The branch, master has been updated
       via  3972882e52d7199000bb5dfc753a86aa296a567a (commit)
      from  82cf9cb2653b39c426f330854c64028eab4cb65d (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=3972882e52d7199000bb5dfc753a86aa296a567a

commit 3972882e52d7199000bb5dfc753a86aa296a567a
Author: H.J. Lu <hjl.tools@gmail.com>
Date:   Thu Dec 4 14:19:41 2014 -0800

    Add _bfd_elf_ifunc_get_synthetic_symtab
    
    In i386 and x86-64 binaries with ifunc, relocations against .got.plt
    section may not be in the same order as entries in PLT section.  This
    patch adds _bfd_elf_ifunc_get_synthetic_symtab.  It takes a function
    pointer which returns an array of PLT entry symbol values.  It calls
    the function pointer to get the PLT entry symbol value array indexed
    by relocation index, instead of calling plt_sym_val on each relocation
    index.
    
    	PR binutils/17677
    	* elf-bfd.h (_bfd_elf_ifunc_get_synthetic_symtab): New prototype.
    	* elf-ifunc.c (_bfd_elf_ifunc_get_synthetic_symtab): New
    	function.
    	* elf32-i386.c (elf_i386_plt_sym_val): Removed.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_i386_get_plt_sym_val): New.
    	(elf_i386_get_synthetic_symtab): Likewise.
    	(bfd_elf32_get_synthetic_symtab): Likewise.
    	* elf64-x86-64.c (elf_x86_64_plt_sym_val): Removed.
    	(elf_x86_64_plt_sym_val_offset_plt_bnd): Likewise.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_x86_64_get_plt_sym_val): New.
    	(elf_x86_64_get_synthetic_symtab): Use
    	_bfd_elf_ifunc_get_synthetic_symtab.
    	(bfd_elf64_get_synthetic_symtab): Don't undefine for NaCl.

-----------------------------------------------------------------------

Summary of changes:
 bfd/ChangeLog      |   19 ++++
 bfd/elf-bfd.h      |    3 +
 bfd/elf-ifunc.c    |  125 ++++++++++++++++++++++++++++
 bfd/elf32-i386.c   |  101 ++++++++++++++++-------
 bfd/elf64-x86-64.c |  235 ++++++++++++++++-----------------------------------
 5 files changed, 292 insertions(+), 191 deletions(-)
Comment 4 Sourceware Commits 2014-12-05 01:00:47 UTC
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "gdb and binutils".

The branch, binutils-2_25-branch has been updated
       via  875896e3e6880ec4c27b4fdfc37ae44881e11ca8 (commit)
      from  f6989d5268fbd213d889e3d81f8972dd429b1bbf (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=875896e3e6880ec4c27b4fdfc37ae44881e11ca8

commit 875896e3e6880ec4c27b4fdfc37ae44881e11ca8
Author: H.J. Lu <hjl.tools@gmail.com>
Date:   Thu Dec 4 14:19:41 2014 -0800

    Add _bfd_elf_ifunc_get_synthetic_symtab
    
    In i386 and x86-64 binaries with ifunc, relocations against .got.plt
    section may not be in the same order as entries in PLT section.  This
    patch adds _bfd_elf_ifunc_get_synthetic_symtab.  It takes a function
    pointer which returns an array of PLT entry symbol values.  It calls
    the function pointer to get the PLT entry symbol value array indexed
    by relocation index, instead of calling plt_sym_val on each relocation
    index.
    
    	PR binutils/17677
    	* elf-bfd.h (_bfd_elf_ifunc_get_synthetic_symtab): New prototype.
    	* elf-ifunc.c (_bfd_elf_ifunc_get_synthetic_symtab): New
    	function.
    	* elf32-i386.c (elf_i386_plt_sym_val): Removed.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_i386_get_plt_sym_val): New.
    	(elf_i386_get_synthetic_symtab): Likewise.
    	(bfd_elf32_get_synthetic_symtab): Likewise.
    	* elf64-x86-64.c (elf_x86_64_plt_sym_val): Removed.
    	(elf_x86_64_plt_sym_val_offset_plt_bnd): Likewise.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_x86_64_get_plt_sym_val): New.
    	(elf_x86_64_get_synthetic_symtab): Use
    	_bfd_elf_ifunc_get_synthetic_symtab.
    	(bfd_elf64_get_synthetic_symtab): Don't undefine for NaCl.

-----------------------------------------------------------------------

Summary of changes:
 bfd/ChangeLog      |   19 ++++
 bfd/elf-bfd.h      |    3 +
 bfd/elf-ifunc.c    |  125 ++++++++++++++++++++++++++++
 bfd/elf32-i386.c   |  101 ++++++++++++++++-------
 bfd/elf64-x86-64.c |  235 ++++++++++++++++-----------------------------------
 5 files changed, 292 insertions(+), 191 deletions(-)
Comment 5 H.J. Lu 2014-12-05 01:01:57 UTC
Fixed on master and binutils 2.25 branch.
Comment 7 Sourceware Commits 2014-12-05 18:17:52 UTC
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "gdb and binutils".

The branch, hjl/gdb-7.8-branch has been created
        at  6a8939044781191d685e0aaeb78fe34a97ee3d55 (commit)

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=6a8939044781191d685e0aaeb78fe34a97ee3d55

commit 6a8939044781191d685e0aaeb78fe34a97ee3d55
Author: H.J. Lu <hjl.tools@gmail.com>
Date:   Thu Dec 4 14:19:41 2014 -0800

    Add _bfd_elf_ifunc_get_synthetic_symtab
    
    In i386 and x86-64 binaries with ifunc, relocations against .got.plt
    section may not be in the same order as entries in PLT section.  This
    patch adds _bfd_elf_ifunc_get_synthetic_symtab.  It takes a function
    pointer which returns an array of PLT entry symbol values.  It calls
    the function pointer to get the PLT entry symbol value array indexed
    by relocation index, instead of calling plt_sym_val on each relocation
    index.
    
    	PR binutils/17677
    	* elf-bfd.h (_bfd_elf_ifunc_get_synthetic_symtab): New prototype.
    	* elf-ifunc.c (_bfd_elf_ifunc_get_synthetic_symtab): New
    	function.
    	* elf32-i386.c (elf_i386_plt_sym_val): Removed.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_i386_get_plt_sym_val): New.
    	(elf_i386_get_synthetic_symtab): Likewise.
    	(bfd_elf32_get_synthetic_symtab): Likewise.
    	* elf64-x86-64.c (elf_x86_64_plt_sym_val): Removed.
    	(elf_x86_64_plt_sym_val_offset_plt_bnd): Likewise.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_x86_64_get_plt_sym_val): New.
    	(bfd_elf32_get_synthetic_symtab): Likewise.
    	(elf_x86_64_get_synthetic_symtab): Use
    	_bfd_elf_ifunc_get_synthetic_symtab.
    	(bfd_elf64_get_synthetic_symtab): Don't undefine for NaCl.

-----------------------------------------------------------------------
Comment 8 H.J. Lu 2014-12-05 18:19:39 UTC
I backported my fix to hjl/gdb-7.8-branch branch.  You can cherry-pick if
if needed.
Comment 9 Sourceware Commits 2014-12-15 22:09:20 UTC
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "gdb and binutils".

The branch, gdb-7.8-branch has been updated
       via  cd4294b2619e6b0e1ea0e553dbdfab40db814485 (commit)
      from  dbdc8a04a60670542cfda8749a2be78779ff7720 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=cd4294b2619e6b0e1ea0e553dbdfab40db814485

commit cd4294b2619e6b0e1ea0e553dbdfab40db814485
Author: H.J. Lu <hjl.tools@gmail.com>
Date:   Thu Dec 4 14:19:41 2014 -0800

    Add _bfd_elf_ifunc_get_synthetic_symtab
    
    In i386 and x86-64 binaries with ifunc, relocations against .got.plt
    section may not be in the same order as entries in PLT section.  This
    patch adds _bfd_elf_ifunc_get_synthetic_symtab.  It takes a function
    pointer which returns an array of PLT entry symbol values.  It calls
    the function pointer to get the PLT entry symbol value array indexed
    by relocation index, instead of calling plt_sym_val on each relocation
    index.
    
    	PR binutils/17677
    	* elf-bfd.h (_bfd_elf_ifunc_get_synthetic_symtab): New prototype.
    	* elf-ifunc.c (_bfd_elf_ifunc_get_synthetic_symtab): New
    	function.
    	* elf32-i386.c (elf_i386_plt_sym_val): Removed.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_i386_get_plt_sym_val): New.
    	(elf_i386_get_synthetic_symtab): Likewise.
    	(bfd_elf32_get_synthetic_symtab): Likewise.
    	* elf64-x86-64.c (elf_x86_64_plt_sym_val): Removed.
    	(elf_x86_64_plt_sym_val_offset_plt_bnd): Likewise.
    	(elf_backend_plt_sym_val): Likewise.
    	(elf_x86_64_get_plt_sym_val): New.
    	(bfd_elf32_get_synthetic_symtab): Likewise.
    	(elf_x86_64_get_synthetic_symtab): Use
    	_bfd_elf_ifunc_get_synthetic_symtab.
    	(bfd_elf64_get_synthetic_symtab): Don't undefine for NaCl.

-----------------------------------------------------------------------

Summary of changes:
 bfd/ChangeLog      |   23 +++++
 bfd/elf-bfd.h      |    3 +
 bfd/elf-ifunc.c    |  125 +++++++++++++++++++++++++++
 bfd/elf32-i386.c   |  101 ++++++++++++++++-------
 bfd/elf64-x86-64.c |  237 +++++++++++++++++-----------------------------------
 5 files changed, 298 insertions(+), 191 deletions(-)
Comment 10 Jan Kratochvil 2014-12-28 14:40:29 UTC
*** Bug 17764 has been marked as a duplicate of this bug. ***