linux-toradex.git/tools/objtool/elf.h, branch v5.7-rc2

objtool: Optimize find_rela_by_dest_range()

2020-03-25T17:28:31+00:00

Perf shows there is significant time in find_rela_by_dest(); this is
because we have to iterate the address space per byte, looking for
relocation entries.

Optimize this by reducing the address space granularity.

This reduces objtool on vmlinux.o runtime from 4.8 to 4.4 seconds.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.861321325@infradead.org

objtool: Optimize read_sections()

2020-03-25T17:28:30+00:00

Perf showed that __hash_init() is a significant portion of
read_sections(), so instead of doing a per section rela_hash, use an
elf-wide rela_hash.

Statistics show us there are about 1.1 million relas, so size it
accordingly.

This reduces the objtool on vmlinux.o runtime to a third, from 15 to 5
seconds.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.739153726@infradead.org

objtool: Optimize find_symbol_by_name()

2020-03-25T17:28:30+00:00

Perf showed that find_symbol_by_name() takes time; add a symbol name
hash.

This shaves another second off of objtool on vmlinux.o runtime, down
to 15 seconds.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.676865656@infradead.org

objtool: Rename find_containing_func()

2020-03-25T17:28:29+00:00

For consistency; we have:

  find_symbol_by_offset() / find_symbol_containing()
  find_func_by_offset()   / find_containing_func()

fix that.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.558470724@infradead.org

objtool: Optimize find_symbol_*() and read_symbols()

2020-03-25T17:28:29+00:00

All of:

  read_symbols(), find_symbol_by_offset(), find_symbol_containing(),
  find_containing_func()

do a linear search of the symbols. Add an RB tree to make it go
faster.

This about halves objtool runtime on vmlinux.o, from 34s to 18s.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.499016559@infradead.org

objtool: Optimize find_section_by_name()

2020-03-25T17:28:29+00:00

In order to avoid yet another linear search of (20k) sections, add a
name based hash.

This reduces objtool runtime on vmlinux.o by some 10s to around 35s.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.440174280@infradead.org

objtool: Optimize find_section_by_index()

2020-03-25T17:28:28+00:00

In order to avoid a linear search (over 20k entries), add an
section_hash to the elf object.

This reduces objtool on vmlinux.o from a few minutes to around 45
seconds.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.381249993@infradead.org

objtool: Optimize find_symbol_by_index()

2020-03-25T17:28:28+00:00

The symbol index is object wide, not per section, so it makes no sense
to have the symbol_hash be part of the section object. By moving it to
the elf object we avoid the linear sections iteration.

This reduces the runtime of objtool on vmlinux.o from over 3 hours (I
gave up) to a few minutes. The defconfig vmlinux.o has around 20k
sections.

Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Miroslav Benes 
Acked-by: Josh Poimboeuf 
Link: https://lkml.kernel.org/r/20200324160924.261852348@infradead.org

objtool: Improve call destination function detection

2020-02-21T09:20:34+00:00

A recent clang change, combined with a binutils bug, can trigger a
situation where a ".Lprintk$local" STT_NOTYPE symbol gets created at the
same offset as the "printk" STT_FUNC symbol.  This confuses objtool:

  kernel/printk/printk.o: warning: objtool: ignore_loglevel_setup()+0x10: can't find call dest symbol at .text+0xc67

Improve the call destination detection by looking specifically for an
STT_FUNC symbol.

Reported-by: Nick Desaulniers 
Signed-off-by: Josh Poimboeuf 
Signed-off-by: Borislav Petkov 
Tested-by: Nick Desaulniers 
Tested-by: Nathan Chancellor 
Link: https://github.com/ClangBuiltLinux/linux/issues/872
Link: https://sourceware.org/bugzilla/show_bug.cgi?id=25551
Link: https://lkml.kernel.org/r/0a7ee320bc0ea4469bd3dc450a7b4725669e0ea9.1581997059.git.jpoimboe@redhat.com

objtool: Support repeated uses of the same C jump table

2019-07-18T19:01:09+00:00

This fixes objtool for both a GCC issue and a Clang issue:

1) GCC issue:

   kernel/bpf/core.o: warning: objtool: ___bpf_prog_run()+0x8d5: sibling call from callable instruction with modified stack frame

   With CONFIG_RETPOLINE=n, GCC is doing the following optimization in
   ___bpf_prog_run().

   Before:

           select_insn:
                   jmp *jumptable(,%rax,8)
                   ...
           ALU64_ADD_X:
                   ...
                   jmp select_insn
           ALU_ADD_X:
                   ...
                   jmp select_insn

   After:

           select_insn:
                   jmp *jumptable(, %rax, 8)
                   ...
           ALU64_ADD_X:
                   ...
                   jmp *jumptable(, %rax, 8)
           ALU_ADD_X:
                   ...
                   jmp *jumptable(, %rax, 8)

   This confuses objtool.  It has never seen multiple indirect jump
   sites which use the same jump table.

   For GCC switch tables, the only way of detecting the size of a table
   is by continuing to scan for more tables.  The size of the previous
   table can only be determined after another switch table is found, or
   when the scan reaches the end of the function.

   That logic was reused for C jump tables, and was based on the
   assumption that each jump table only has a single jump site.  The
   above optimization breaks that assumption.

2) Clang issue:

   drivers/usb/misc/sisusbvga/sisusb.o: warning: objtool: sisusb_write_mem_bulk()+0x588: can't find switch jump table

   With clang 9, code can be generated where a function contains two
   indirect jump instructions which use the same switch table.

The fix is the same for both issues: split the jump table parsing into
two passes.

In the first pass, locate the heads of all switch tables for the
function and mark their locations.

In the second pass, parse the switch tables and add them.

Fixes: e55a73251da3 ("bpf: Fix ORC unwinding in non-JIT BPF code")
Reported-by: Randy Dunlap 
Reported-by: Arnd Bergmann 
Signed-off-by: Jann Horn 
Signed-off-by: Josh Poimboeuf 
Signed-off-by: Thomas Gleixner 
Tested-by: Nick Desaulniers 
Acked-by: Peter Zijlstra (Intel) 
Link: https://lkml.kernel.org/r/e995befaada9d4d8b2cf788ff3f566ba900d2b4d.1563413318.git.jpoimboe@redhat.com

Co-developed-by: Josh Poimboeuf