lkml.org 
[lkml]   [2020]   [Mar]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[RFC][PATCH 14/16] objtool: Optimize find_rela_by_dest_range()
    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) <peterz@infradead.org>
    ---
    tools/objtool/elf.c | 15 +++++++++++----
    tools/objtool/elf.h | 11 ++++++++++-
    2 files changed, 21 insertions(+), 5 deletions(-)

    --- a/tools/objtool/elf.c
    +++ b/tools/objtool/elf.c
    @@ -204,7 +204,7 @@ struct symbol *find_symbol_by_name(struc
    struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
    unsigned int len)
    {
    - struct rela *rela;
    + struct rela *rela, *r = NULL;
    unsigned long o;

    if (!sec->rela)
    @@ -212,12 +212,19 @@ struct rela *find_rela_by_dest_range(str

    sec = sec->rela;

    - for (o = offset; o < offset + len; o++) {
    + for (o = offset & RELA_STRIDE_MASK; o < offset + len; o += RELA_STRIDE) {
    hash_for_each_possible(sec->elf->rela_hash, rela, hash,
    __rela_hash(o, sec->idx)) {
    - if (rela->sec == sec && rela->offset == o)
    - return rela;
    + if (rela->sec != sec)
    + continue;
    +
    + if (rela->offset >= offset && rela->offset < offset + len) {
    + if (!r || rela->offset < r->offset)
    + r = rela;
    + }
    }
    + if (r)
    + return r;
    }

    return NULL;
    --- a/tools/objtool/elf.h
    +++ b/tools/objtool/elf.h
    @@ -86,9 +86,18 @@ struct elf {
    DECLARE_HASHTABLE(rela_hash, 20);
    };

    +#define RELA_STRIDE_BITS 4
    +#define RELA_STRIDE (1UL << RELA_STRIDE_BITS)
    +#define RELA_STRIDE_MASK (~(RELA_STRIDE - 1))
    +
    static inline u32 __rela_hash(unsigned long offset, int idx)
    {
    - u32 ol = offset, oh = offset >> 32;
    + u32 ol, oh;
    +
    + offset &= RELA_STRIDE_MASK;
    +
    + ol = offset;
    + oh = offset >> 32;

    __jhash_mix(ol, oh, idx);


    \
     
     \ /
      Last update: 2020-03-12 14:53    [W:4.148 / U:21.116 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site