[Bug binutils/17677] New: _bfd_elf_get_synthetic_symtab runs in O(n^2) complexity after commit 5840bf271c87c3fc14739173fdc91c6a14057130

[tohava at gmail dot com]

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

            Bug ID: 17677
           Summary: _bfd_elf_get_synthetic_symtab runs in O(n^2)
                    complexity after commit
                    5840bf271c87c3fc14739173fdc91c6a14057130
           Product: binutils
           Version: 2.24
            Status: NEW
          Severity: normal
          Priority: P2
         Component: binutils
          Assignee: unassigned at sourceware dot org
          Reporter: tohava at gmail dot com

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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.