[PATCH v2 02/19] objtool: Rename func_for_each_insn()

[Peter Zijlstra]

There is func_for_each_insn() and func_for_each_insn_all(), the both
iterate the instructions, but the first uses symbol offset/length
while the second uses insn->func.

Rename func_for_each_insn() to sym_for_eac_insn() because it iterates
on symbol information.

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/check.c | 16 ++++++++--------
1 file changed, 8 insertions(+), 8 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -77,17 +77,17 @@ static struct instruction *next_insn_sam
insn; \
insn = next_insn_same_func(file, insn))

-#define func_for_each_insn(file, func, insn) \
- for (insn = find_insn(file, func->sec, func->offset); \
+#define sym_for_each_insn(file, sym, insn) \
+ for (insn = find_insn(file, sym->sec, sym->offset); \
insn && &insn->list != &file->insn_list && \
- insn->sec == func->sec && \
- insn->offset < func->offset + func->len; \
+ insn->sec == sym->sec && \
+ insn->offset < sym->offset + sym->len; \
insn = list_next_entry(insn, list))

-#define func_for_each_insn_continue_reverse(file, func, insn) \
+#define sym_for_each_insn_continue_reverse(file, sym, insn) \
for (insn = list_prev_entry(insn, list); \
&insn->list != &file->insn_list && \
- insn->sec == func->sec && insn->offset >= func->offset; \
+ insn->sec == sym->sec && insn->offset >= sym->offset; \
insn = list_prev_entry(insn, list))

#define sec_for_each_insn_from(file, insn) \
@@ -281,7 +281,7 @@ static int decode_instructions(struct ob
return -1;
}

- func_for_each_insn(file, func, insn)
+ sym_for_each_insn(file, func, insn)
insn->func = func;
}
}
@@ -2024,7 +2024,7 @@ static int validate_branch(struct objtoo

i = insn;
save_insn = NULL;
- func_for_each_insn_continue_reverse(file, func, i) {
+ sym_for_each_insn_continue_reverse(file, func, i) {
if (i->save) {
save_insn = i;
break;

[Peter Zijlstra]

Now that func_for_each_insn() is available, rename
func_for_each_insn_all(). This gets us:

sym_for_each_insn() - iterate on symbol offset/len
func_for_each_insn() - iterate on insn->func

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/check.c | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -72,7 +72,7 @@ static struct instruction *next_insn_sam
return find_insn(file, func->cfunc->sec, func->cfunc->offset);
}

-#define func_for_each_insn_all(file, func, insn) \
+#define func_for_each_insn(file, func, insn) \
for (insn = find_insn(file, func->sec, func->offset); \
insn; \
insn = next_insn_same_func(file, insn))
@@ -165,7 +165,7 @@ static bool __dead_end_function(struct o
if (!insn->func)
return false;

- func_for_each_insn_all(file, func, insn) {
+ func_for_each_insn(file, func, insn) {
empty = false;

if (insn->type == INSN_RETURN)
@@ -180,7 +180,7 @@ static bool __dead_end_function(struct o
* case, the function's dead-end status depends on whether the target
* of the sibling call returns.
*/
- func_for_each_insn_all(file, func, insn) {
+ func_for_each_insn(file, func, insn) {
if (is_sibling_call(insn)) {
struct instruction *dest = insn->jump_dest;

@@ -425,7 +425,7 @@ static void add_ignores(struct objtool_f
continue;
}

- func_for_each_insn_all(file, func, insn)
+ func_for_each_insn(file, func, insn)
insn->ignore = true;
}
}
@@ -1082,7 +1082,7 @@ static void mark_func_jump_tables(struct
struct instruction *insn, *last = NULL;
struct rela *rela;

- func_for_each_insn_all(file, func, insn) {
+ func_for_each_insn(file, func, insn) {
if (!last)
last = insn;

@@ -1117,7 +1117,7 @@ static int add_func_jump_tables(struct o
struct instruction *insn;
int ret;

- func_for_each_insn_all(file, func, insn) {
+ func_for_each_insn(file, func, insn) {
if (!insn->jump_table)
continue;

[Peter Zijlstra]

Normally identity_mapped is not visible to objtool, due to:

arch/x86/kernel/Makefile:OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o := y

However, when we want to run objtool on vmlinux.o there is no hiding
it:

vmlinux.o: warning: objtool: .text+0x4c0f1: unsupported intra-function call

Replace the (i386 inspired) pattern:

call 1f
1: popq %r8
subq $(1b - relocate_kernel), %r8

With a x86_64 RIP-relative LEA:

leaq relocate_kernel(%rip), %r8

Suggested-by: Brian Gerst <***@gmail.com>
Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
arch/x86/kernel/relocate_kernel_64.S | 5 +----
1 file changed, 1 insertion(+), 4 deletions(-)

--- a/arch/x86/kernel/relocate_kernel_64.S
+++ b/arch/x86/kernel/relocate_kernel_64.S
@@ -196,10 +196,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_ma

/* get the re-entry point of the peer system */
movq 0(%rsp), %rbp
- call 1f
-1:
- popq %r8
- subq $(1b - relocate_kernel), %r8
+ leaq relocate_kernel(%rip), %r8
movq CP_PA_SWAP_PAGE(%r8), %r10
movq CP_PA_BACKUP_PAGES_MAP(%r8), %rdi
movq CP_PA_TABLE_PAGE(%r8), %rax

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/elf.c | 13 ++++++++-----
tools/objtool/elf.h | 2 ++
2 files changed, 10 insertions(+), 5 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -38,7 +38,7 @@ static struct section *find_section_by_i
{
struct section *sec;

- list_for_each_entry(sec, &elf->sections, list)
+ hash_for_each_possible(elf->section_hash, sec, hash, idx)
if (sec->idx == idx)
return sec;

@@ -166,8 +166,6 @@ static int read_sections(struct elf *elf
INIT_LIST_HEAD(&sec->rela_list);
hash_init(sec->rela_hash);

- list_add_tail(&sec->list, &elf->sections);
-
s = elf_getscn(elf->elf, i);
if (!s) {
WARN_ELF("elf_getscn");
@@ -201,6 +199,9 @@ static int read_sections(struct elf *elf
}
}
sec->len = sec->sh.sh_size;
+
+ list_add_tail(&sec->list, &elf->sections);
+ hash_add(elf->section_hash, &sec->hash, sec->idx);
}

if (stats)
@@ -439,6 +440,7 @@ struct elf *elf_read(const char *name, i
memset(elf, 0, sizeof(*elf));

hash_init(elf->symbol_hash);
+ hash_init(elf->section_hash);
INIT_LIST_HEAD(&elf->sections);

elf->fd = open(name, flags);
@@ -501,8 +503,6 @@ struct section *elf_create_section(struc
INIT_LIST_HEAD(&sec->rela_list);
hash_init(sec->rela_hash);

- list_add_tail(&sec->list, &elf->sections);
-
s = elf_newscn(elf->elf);
if (!s) {
WARN_ELF("elf_newscn");
@@ -579,6 +579,9 @@ struct section *elf_create_section(struc
shstrtab->len += strlen(name) + 1;
shstrtab->changed = true;

+ list_add_tail(&sec->list, &elf->sections);
+ hash_add(elf->section_hash, &sec->hash, sec->idx);
+
return sec;
}

--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -25,6 +25,7 @@

struct section {
struct list_head list;
+ struct hlist_node hash;
GElf_Shdr sh;
struct list_head symbol_list;
struct list_head rela_list;
@@ -71,6 +72,7 @@ struct elf {
char *name;
struct list_head sections;
DECLARE_HASHTABLE(symbol_hash, 20);
+ DECLARE_HASHTABLE(section_hash, 16);
};

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/elf.c | 10 +++++++++-
tools/objtool/elf.h | 3 +++
2 files changed, 12 insertions(+), 1 deletion(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -22,11 +22,16 @@

#define MAX_NAME_LEN 128

+static inline u32 str_hash(const char *str)
+{
+ return jhash(str, strlen(str), 0);
+}
+
struct section *find_section_by_name(struct elf *elf, const char *name)
{
struct section *sec;

- list_for_each_entry(sec, &elf->sections, list)
+ hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
if (!strcmp(sec->name, name))
return sec;

@@ -202,6 +207,7 @@ static int read_sections(struct elf *elf

list_add_tail(&sec->list, &elf->sections);
hash_add(elf->section_hash, &sec->hash, sec->idx);
+ hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
}

if (stats)
@@ -441,6 +447,7 @@ struct elf *elf_read(const char *name, i

hash_init(elf->symbol_hash);
hash_init(elf->section_hash);
+ hash_init(elf->section_name_hash);
INIT_LIST_HEAD(&elf->sections);

elf->fd = open(name, flags);
@@ -581,6 +588,7 @@ struct section *elf_create_section(struc

list_add_tail(&sec->list, &elf->sections);
hash_add(elf->section_hash, &sec->hash, sec->idx);
+ hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));

return sec;
}
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -10,6 +10,7 @@
#include <gelf.h>
#include <linux/list.h>
#include <linux/hashtable.h>
+#include <linux/jhash.h>

#ifdef LIBELF_USE_DEPRECATED
# define elf_getshdrnum elf_getshnum
@@ -26,6 +27,7 @@
struct section {
struct list_head list;
struct hlist_node hash;
+ struct hlist_node name_hash;
GElf_Shdr sh;
struct list_head symbol_list;
struct list_head rela_list;
@@ -73,6 +75,7 @@ struct elf {
struct list_head sections;
DECLARE_HASHTABLE(symbol_hash, 20);
DECLARE_HASHTABLE(section_hash, 16);
+ DECLARE_HASHTABLE(section_name_hash, 16);
};

[Peter Zijlstra]

Perf shows we spend a measurable amount of time spend cleaning up
right before we exit anyway. Avoid the needsless work and just
terminate.

This reduces objtool on vmlinux.o runtime from 5.4s to 4.8s

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/check.c | 19 -------------------
1 file changed, 19 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -2476,23 +2476,6 @@ static int validate_reachable_instructio
return 0;
}

-static void cleanup(struct objtool_file *file)
-{
- struct instruction *insn, *tmpinsn;
- struct alternative *alt, *tmpalt;
-
- list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
- list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
- list_del(&alt->list);
- free(alt);
- }
- list_del(&insn->list);
- hash_del(&insn->hash);
- free(insn);
- }
- elf_close(file->elf);
-}
-
static struct objtool_file file;

int check(const char *_objname, bool orc)
@@ -2560,8 +2543,6 @@ int check(const char *_objname, bool orc
}

out:
- cleanup(&file);
-
if (ret < 0) {
/*
* Fatal error. The binary is corrupt or otherwise broken in

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/Build | 5 +
tools/objtool/elf.c | 194 ++++++++++++++++++++++++++++++++++++----------------
tools/objtool/elf.h | 3
3 files changed, 144 insertions(+), 58 deletions(-)

--- a/tools/objtool/Build
+++ b/tools/objtool/Build
@@ -11,6 +11,7 @@ objtool-y += objtool.o
objtool-y += libstring.o
objtool-y += libctype.o
objtool-y += str_error_r.o
+objtool-y += librbtree.o

CFLAGS += -I$(srctree)/tools/lib

@@ -25,3 +26,7 @@ $(OUTPUT)libctype.o: ../lib/ctype.c FORC
$(OUTPUT)str_error_r.o: ../lib/str_error_r.c FORCE
$(call rule_mkdir)
$(call if_changed_dep,cc_o_c)
+
+$(OUTPUT)librbtree.o: ../lib/rbtree.c FORCE
+ $(call rule_mkdir)
+ $(call if_changed_dep,cc_o_c)
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -27,6 +27,90 @@ static inline u32 str_hash(const char *s
return jhash(str, strlen(str), 0);
}

+static void rb_add(struct rb_root *tree, struct rb_node *node,
+ int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->rb_node;
+ struct rb_node *parent = NULL;
+
+ while (*link) {
+ parent = *link;
+ if (cmp(node, parent) < 0)
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color(node, tree);
+}
+
+static struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ struct rb_node *node = tree->rb_node;
+ struct rb_node *match = NULL;
+
+ while (node) {
+ int c = cmp(key, node);
+ if (c <= 0) {
+ if (!c)
+ match = node;
+ node = node->rb_left;
+ } else if (c > 0) {
+ node = node->rb_right;
+ }
+ }
+
+ return match;
+}
+
+static struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ node = rb_next(node);
+ if (node && cmp(key, node))
+ node = NULL;
+ return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+ for ((node) = rb_find_first((tree), (key), (cmp)); \
+ (node); (node) = rb_next_match((node), (key), (cmp)))
+
+static int symbol_to_offset(struct rb_node *a, const struct rb_node *b)
+{
+ struct symbol *sa = rb_entry(a, struct symbol, node);
+ struct symbol *sb = rb_entry(b, struct symbol, node);
+
+ if (sa->offset < sb->offset)
+ return -1;
+ if (sa->offset > sb->offset)
+ return 1;
+
+ if (sa->len < sb->len)
+ return -1;
+ if (sa->len > sb->len)
+ return 1;
+
+ sa->alias = sb;
+
+ return 0;
+}
+
+static int symbol_by_offset(const void *key, const struct rb_node *node)
+{
+ const struct symbol *s = rb_entry(node, struct symbol, node);
+ const unsigned long *o = key;
+
+ if (*o < s->offset)
+ return -1;
+ if (*o > s->offset + s->len)
+ return 1;
+
+ return 0;
+}
+
struct section *find_section_by_name(struct elf *elf, const char *name)
{
struct section *sec;
@@ -63,47 +147,69 @@ static struct symbol *find_symbol_by_ind

struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
{
- struct symbol *sym;
+ struct rb_node *node;

- list_for_each_entry(sym, &sec->symbol_list, list)
- if (sym->type != STT_SECTION && sym->offset == offset)
- return sym;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->offset == offset && s->type != STT_SECTION)
+ return s;
+ }

return NULL;
}

struct symbol *find_func_by_offset(struct section *sec, unsigned long offset)
{
- struct symbol *sym;
+ struct rb_node *node;

- list_for_each_entry(sym, &sec->symbol_list, list)
- if (sym->type == STT_FUNC && sym->offset == offset)
- return sym;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->offset == offset && s->type == STT_FUNC)
+ return s;
+ }

return NULL;
}

-struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
+struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
{
- struct section *sec;
- struct symbol *sym;
+ struct rb_node *node;

- list_for_each_entry(sec, &elf->sections, list)
- list_for_each_entry(sym, &sec->symbol_list, list)
- if (!strcmp(sym->name, name))
- return sym;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->type != STT_SECTION)
+ return s;
+ }

return NULL;
}

-struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
+struct symbol *find_containing_func(struct section *sec, unsigned long offset)
{
+ struct rb_node *node;
+
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->type == STT_FUNC)
+ return s;
+ }
+
+ return NULL;
+}
+
+struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
+{
+ struct section *sec;
struct symbol *sym;

- list_for_each_entry(sym, &sec->symbol_list, list)
- if (sym->type != STT_SECTION &&
- offset >= sym->offset && offset < sym->offset + sym->len)
- return sym;
+ list_for_each_entry(sec, &elf->sections, list)
+ list_for_each_entry(sym, &sec->symbol_list, list)
+ if (!strcmp(sym->name, name))
+ return sym;

return NULL;
}
@@ -130,18 +236,6 @@ struct rela *find_rela_by_dest(struct se
return find_rela_by_dest_range(sec, offset, 1);
}

-struct symbol *find_containing_func(struct section *sec, unsigned long offset)
-{
- struct symbol *func;
-
- list_for_each_entry(func, &sec->symbol_list, list)
- if (func->type == STT_FUNC && offset >= func->offset &&
- offset < func->offset + func->len)
- return func;
-
- return NULL;
-}
-
static int read_sections(struct elf *elf)
{
Elf_Scn *s = NULL;
@@ -225,8 +319,9 @@ static int read_sections(struct elf *elf
static int read_symbols(struct elf *elf)
{
struct section *symtab, *sec;
- struct symbol *sym, *pfunc, *alias;
- struct list_head *entry, *tmp;
+ struct symbol *sym, *pfunc;
+ struct list_head *entry;
+ struct rb_node *pnode;
int symbols_nr, i;
char *coldstr;

@@ -245,7 +340,7 @@ static int read_symbols(struct elf *elf)
return -1;
}
memset(sym, 0, sizeof(*sym));
- alias = sym;
+ sym->alias = sym;

sym->idx = i;

@@ -283,29 +378,12 @@ static int read_symbols(struct elf *elf)
sym->offset = sym->sym.st_value;
sym->len = sym->sym.st_size;

- /* sorted insert into a per-section list */
- entry = &sym->sec->symbol_list;
- list_for_each_prev(tmp, &sym->sec->symbol_list) {
- struct symbol *s;
-
- s = list_entry(tmp, struct symbol, list);
-
- if (sym->offset > s->offset) {
- entry = tmp;
- break;
- }
-
- if (sym->offset == s->offset) {
- if (sym->len && sym->len == s->len && alias == sym)
- alias = s;
-
- if (sym->len >= s->len) {
- entry = tmp;
- break;
- }
- }
- }
- sym->alias = alias;
+ rb_add(&sym->sec->symbol_tree, &sym->node, symbol_to_offset);
+ pnode = rb_prev(&sym->node);
+ if (pnode)
+ entry = &rb_entry(pnode, struct symbol, node)->list;
+ else
+ entry = &sym->sec->symbol_list;
list_add(&sym->list, entry);
hash_add(elf->symbol_hash, &sym->hash, sym->idx);
}
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -10,6 +10,7 @@
#include <gelf.h>
#include <linux/list.h>
#include <linux/hashtable.h>
+#include <linux/rbtree.h>
#include <linux/jhash.h>

#ifdef LIBELF_USE_DEPRECATED
@@ -29,6 +30,7 @@ struct section {
struct hlist_node hash;
struct hlist_node name_hash;
GElf_Shdr sh;
+ struct rb_root symbol_tree;
struct list_head symbol_list;
struct list_head rela_list;
DECLARE_HASHTABLE(rela_hash, 16);
@@ -43,6 +45,7 @@ struct section {

struct symbol {
struct list_head list;
+ struct rb_node node;
struct hlist_node hash;
GElf_Sym sym;
struct section *sec;

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/elf.c | 15 +++++++++++----
tools/objtool/elf.h | 16 +++++++++++++++-
2 files changed, 26 insertions(+), 5 deletions(-)

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

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

sec = sec->rela;

- for (o = offset; o < offset + len; o++) {
+ for_offset_range(o, offset, offset + len) {
hash_for_each_possible(elf->rela_hash, rela, hash,
sec_offset_hash(sec, o)) {
- 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
@@ -83,9 +83,23 @@ struct elf {
DECLARE_HASHTABLE(rela_hash, 20);
};

+#define OFFSET_STRIDE_BITS 4
+#define OFFSET_STRIDE (1UL << OFFSET_STRIDE_BITS)
+#define OFFSET_STRIDE_MASK (~(OFFSET_STRIDE - 1))
+
+#define for_offset_range(_offset, _start, _end) \
+ for (_offset = ((_start) & OFFSET_STRIDE_MASK); \
+ _offset <= ((_end) & OFFSET_STRIDE_MASK); \
+ _offset += OFFSET_STRIDE)
+
static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
{
- u32 ol = offset, oh = offset >> 32, idx = sec->idx;
+ u32 ol, oh, idx = sec->idx;
+
+ offset &= OFFSET_STRIDE_MASK;
+
+ ol = offset;
+ oh = offset >> 32;

__jhash_mix(ol, oh, idx);

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/check.c | 18 +++++++++---------
tools/objtool/elf.c | 24 ++++++++++++++----------
tools/objtool/elf.h | 21 +++++++++++++++++----
tools/objtool/orc_gen.c | 9 +++++----
tools/objtool/special.c | 4 ++--
5 files changed, 47 insertions(+), 29 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -587,8 +587,8 @@ static int add_jump_destinations(struct
if (insn->ignore || insn->offset == FAKE_JUMP_OFFSET)
continue;

- rela = find_rela_by_dest_range(insn->sec, insn->offset,
- insn->len);
+ rela = find_rela_by_dest_range(file->elf, insn->sec,
+ insn->offset, insn->len);
if (!rela) {
dest_sec = insn->sec;
dest_off = insn->offset + insn->len + insn->immediate;
@@ -684,8 +684,8 @@ static int add_call_destinations(struct
if (insn->type != INSN_CALL)
continue;

- rela = find_rela_by_dest_range(insn->sec, insn->offset,
- insn->len);
+ rela = find_rela_by_dest_range(file->elf, insn->sec,
+ insn->offset, insn->len);
if (!rela) {
dest_off = insn->offset + insn->len + insn->immediate;
insn->call_dest = find_func_by_offset(insn->sec, dest_off);
@@ -814,7 +814,7 @@ static int handle_group_alt(struct objto
*/
if ((insn->offset != special_alt->new_off ||
(insn->type != INSN_CALL && !is_static_jump(insn))) &&
- find_rela_by_dest_range(insn->sec, insn->offset, insn->len)) {
+ find_rela_by_dest_range(file->elf, insn->sec, insn->offset, insn->len)) {

WARN_FUNC("unsupported relocation in alternatives section",
insn->sec, insn->offset);
@@ -1084,8 +1084,8 @@ static struct rela *find_jump_table(stru
break;

/* look for a relocation which references .rodata */
- text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
- insn->len);
+ text_rela = find_rela_by_dest_range(file->elf, insn->sec,
+ insn->offset, insn->len);
if (!text_rela || text_rela->sym->type != STT_SECTION ||
!text_rela->sym->sec->rodata)
continue;
@@ -1114,7 +1114,7 @@ static struct rela *find_jump_table(stru
* should reference text in the same function as the original
* instruction.
*/
- table_rela = find_rela_by_dest(table_sec, table_offset);
+ table_rela = find_rela_by_dest(file->elf, table_sec, table_offset);
if (!table_rela)
continue;
dest_insn = find_insn(file, table_rela->sym->sec, table_rela->addend);
@@ -1250,7 +1250,7 @@ static int read_unwind_hints(struct objt
for (i = 0; i < sec->len / sizeof(struct unwind_hint); i++) {
hint = (struct unwind_hint *)sec->data->d_buf + i;

- rela = find_rela_by_dest(sec, i * sizeof(*hint));
+ rela = find_rela_by_dest(file->elf, sec, i * sizeof(*hint));
if (!rela) {
WARN("can't find rela for unwind_hints[%d]", i);
return -1;
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -212,8 +212,8 @@ struct symbol *find_symbol_by_name(struc
return NULL;
}

-struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
- unsigned int len)
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+ unsigned long offset, unsigned int len)
{
struct rela *rela;
unsigned long o;
@@ -221,17 +221,22 @@ struct rela *find_rela_by_dest_range(str
if (!sec->rela)
return NULL;

- for (o = offset; o < offset + len; o++)
- hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
- if (rela->offset == o)
+ sec = sec->rela;
+
+ for (o = offset; o < offset + len; o++) {
+ hash_for_each_possible(elf->rela_hash, rela, hash,
+ sec_offset_hash(sec, o)) {
+ if (rela->sec == sec && rela->offset == o)
return rela;
+ }
+ }

return NULL;
}

-struct rela *find_rela_by_dest(struct section *sec, unsigned long offset)
+struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset)
{
- return find_rela_by_dest_range(sec, offset, 1);
+ return find_rela_by_dest_range(elf, sec, offset, 1);
}

static int read_sections(struct elf *elf)
@@ -261,7 +266,6 @@ static int read_sections(struct elf *elf

INIT_LIST_HEAD(&sec->symbol_list);
INIT_LIST_HEAD(&sec->rela_list);
- hash_init(sec->rela_hash);

s = elf_getscn(elf->elf, i);
if (!s) {
@@ -493,7 +497,7 @@ static int read_relas(struct elf *elf)
}

list_add_tail(&rela->list, &sec->rela_list);
- hash_add(sec->rela_hash, &rela->hash, rela->offset);
+ hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
nr_rela++;
}
max_rela = max(max_rela, nr_rela);
@@ -526,6 +530,7 @@ struct elf *elf_read(const char *name, i
hash_init(elf->symbol_name_hash);
hash_init(elf->section_hash);
hash_init(elf->section_name_hash);
+ hash_init(elf->rela_hash);
INIT_LIST_HEAD(&elf->sections);

elf->fd = open(name, flags);
@@ -586,7 +591,6 @@ struct section *elf_create_section(struc

INIT_LIST_HEAD(&sec->symbol_list);
INIT_LIST_HEAD(&sec->rela_list);
- hash_init(sec->rela_hash);

s = elf_newscn(elf->elf);
if (!s) {
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -33,7 +33,6 @@ struct section {
struct rb_root symbol_tree;
struct list_head symbol_list;
struct list_head rela_list;
- DECLARE_HASHTABLE(rela_hash, 16);
struct section *base, *rela;
struct symbol *sym;
Elf_Data *data;
@@ -81,8 +80,22 @@ struct elf {
DECLARE_HASHTABLE(symbol_name_hash, 20);
DECLARE_HASHTABLE(section_hash, 16);
DECLARE_HASHTABLE(section_name_hash, 16);
+ DECLARE_HASHTABLE(rela_hash, 20);
};

+static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
+{
+ u32 ol = offset, oh = offset >> 32, idx = sec->idx;
+
+ __jhash_mix(ol, oh, idx);
+
+ return ol;
+}
+
+static inline u32 rela_hash(struct rela *rela)
+{
+ return sec_offset_hash(rela->sec, rela->offset);
+}

struct elf *elf_read(const char *name, int flags);
struct section *find_section_by_name(struct elf *elf, const char *name);
@@ -90,9 +103,9 @@ struct symbol *find_func_by_offset(struc
struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset);
struct symbol *find_symbol_by_name(struct elf *elf, const char *name);
struct symbol *find_symbol_containing(struct section *sec, unsigned long offset);
-struct rela *find_rela_by_dest(struct section *sec, unsigned long offset);
-struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
- unsigned int len);
+struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset);
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+ unsigned long offset, unsigned int len);
struct symbol *find_func_containing(struct section *sec, unsigned long offset);
struct section *elf_create_section(struct elf *elf, const char *name, size_t
entsize, int nr);
--- a/tools/objtool/orc_gen.c
+++ b/tools/objtool/orc_gen.c
@@ -81,7 +81,7 @@ int create_orc(struct objtool_file *file
return 0;
}

-static int create_orc_entry(struct section *u_sec, struct section *ip_relasec,
+static int create_orc_entry(struct elf *elf, struct section *u_sec, struct section *ip_relasec,
unsigned int idx, struct section *insn_sec,
unsigned long insn_off, struct orc_entry *o)
{
@@ -109,9 +109,10 @@ static int create_orc_entry(struct secti
rela->addend = insn_off;
rela->type = R_X86_64_PC32;
rela->offset = idx * sizeof(int);
+ rela->sec = ip_relasec;

list_add_tail(&rela->list, &ip_relasec->rela_list);
- hash_add(ip_relasec->rela_hash, &rela->hash, rela->offset);
+ hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));

return 0;
}
@@ -182,7 +183,7 @@ int create_orc_sections(struct objtool_f
if (!prev_insn || memcmp(&insn->orc, &prev_insn->orc,
sizeof(struct orc_entry))) {

- if (create_orc_entry(u_sec, ip_relasec, idx,
+ if (create_orc_entry(file->elf, u_sec, ip_relasec, idx,
insn->sec, insn->offset,
&insn->orc))
return -1;
@@ -194,7 +195,7 @@ int create_orc_sections(struct objtool_f

/* section terminator */
if (prev_insn) {
- if (create_orc_entry(u_sec, ip_relasec, idx,
+ if (create_orc_entry(file->elf, u_sec, ip_relasec, idx,
prev_insn->sec,
prev_insn->offset + prev_insn->len,
&empty))
--- a/tools/objtool/special.c
+++ b/tools/objtool/special.c
@@ -118,7 +118,7 @@ static int get_alt_entry(struct elf *elf
}
}

- orig_rela = find_rela_by_dest(sec, offset + entry->orig);
+ orig_rela = find_rela_by_dest(elf, sec, offset + entry->orig);
if (!orig_rela) {
WARN_FUNC("can't find orig rela", sec, offset + entry->orig);
return -1;
@@ -133,7 +133,7 @@ static int get_alt_entry(struct elf *elf
alt->orig_off = orig_rela->addend;

if (!entry->group || alt->new_len) {
- new_rela = find_rela_by_dest(sec, offset + entry->new);
+ new_rela = find_rela_by_dest(elf, sec, offset + entry->new);
if (!new_rela) {
WARN_FUNC("can't find new rela",
sec, offset + entry->new);

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/elf.c | 10 +++++-----
tools/objtool/elf.h | 2 ++
2 files changed, 7 insertions(+), 5 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -203,13 +203,11 @@ struct symbol *find_func_containing(stru

struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
{
- struct section *sec;
struct symbol *sym;

- list_for_each_entry(sec, &elf->sections, list)
- list_for_each_entry(sym, &sec->symbol_list, list)
- if (!strcmp(sym->name, name))
- return sym;
+ hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+ if (!strcmp(sym->name, name))
+ return sym;

return NULL;
}
@@ -386,6 +384,7 @@ static int read_symbols(struct elf *elf)
entry = &sym->sec->symbol_list;
list_add(&sym->list, entry);
hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+ hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
}

if (stats)
@@ -524,6 +523,7 @@ struct elf *elf_read(const char *name, i
memset(elf, 0, sizeof(*elf));

hash_init(elf->symbol_hash);
+ hash_init(elf->symbol_name_hash);
hash_init(elf->section_hash);
hash_init(elf->section_name_hash);
INIT_LIST_HEAD(&elf->sections);
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -47,6 +47,7 @@ struct symbol {
struct list_head list;
struct rb_node node;
struct hlist_node hash;
+ struct hlist_node name_hash;
GElf_Sym sym;
struct section *sec;
char *name;
@@ -77,6 +78,7 @@ struct elf {
char *name;
struct list_head sections;
DECLARE_HASHTABLE(symbol_hash, 20);
+ DECLARE_HASHTABLE(symbol_name_hash, 20);
DECLARE_HASHTABLE(section_hash, 16);
DECLARE_HASHTABLE(section_name_hash, 16);
};

[Peter Zijlstra]

Validate that any call out of .noinstr.text is in between
instr_begin() and instr_end() annotations.

This annotation is useful to ensure correct behaviour wrt tracing
sensitive code like entry/exit and idle code. When we run code in a
sensitive context we want a guarantee no unknown code is ran.

Since this validation relies on knowing the section of call
destination symbols, we must run it on vmlinux.o instead of on
individual object files.

Add two options:

-d/--duplicate "duplicate validation for vmlinux"
-l/--vmlinux "vmlinux.o validation"

Where the latter auto-detects when objname ends with "vmlinux.o" and
the former will force all validations, also those already done on
!vmlinux object files.

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/builtin-check.c | 11 ++-
tools/objtool/builtin.h | 2
tools/objtool/check.c | 153 +++++++++++++++++++++++++++++++++++-------
tools/objtool/check.h | 3
tools/objtool/elf.h | 2
5 files changed, 145 insertions(+), 26 deletions(-)

--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -14,10 +14,11 @@
*/

#include <subcmd/parse-options.h>
+#include <string.h>
#include "builtin.h"
#include "check.h"

-bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
+bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats, validate_dup, vmlinux;

static const char * const check_usage[] = {
"objtool check [<options>] file.o",
@@ -32,12 +33,14 @@ const struct option check_options[] = {
OPT_BOOLEAN('b', "backtrace", &backtrace, "unwind on error"),
OPT_BOOLEAN('a', "uaccess", &uaccess, "enable uaccess checking"),
OPT_BOOLEAN('s', "stats", &stats, "print statistics"),
+ OPT_BOOLEAN('d', "duplicate", &validate_dup, "duplicate validation for vmlinux.o"),
+ OPT_BOOLEAN('l', "vmlinux", &vmlinux, "vmlinux.o validation"),
OPT_END(),
};

int cmd_check(int argc, const char **argv)
{
- const char *objname;
+ const char *objname, *s;

argc = parse_options(argc, argv, check_options, check_usage, 0);

@@ -46,5 +49,9 @@ int cmd_check(int argc, const char **arg

objname = argv[0];

+ s = strstr(objname, "vmlinux.o");
+ if (s && !s[9])
+ vmlinux = true;
+
return check(objname, false);
}
--- a/tools/objtool/builtin.h
+++ b/tools/objtool/builtin.h
@@ -8,7 +8,7 @@
#include <subcmd/parse-options.h>

extern const struct option check_options[];
-extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
+extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats, validate_dup, vmlinux;

extern int cmd_check(int argc, const char **argv);
extern int cmd_orc(int argc, const char **argv);
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -252,6 +252,9 @@ static int decode_instructions(struct ob
strncmp(sec->name, ".discard.", 9))
sec->text = true;

+ if (!strcmp(sec->name, ".noinstr.text"))
+ sec->noinstr = true;
+
for (offset = 0; offset < sec->len; offset += insn->len) {
insn = malloc(sizeof(*insn));
if (!insn) {
@@ -1350,6 +1353,53 @@ static int read_retpoline_hints(struct o
return 0;
}

+static int read_instr_hints(struct objtool_file *file)
+{
+ struct section *sec;
+ struct instruction *insn;
+ struct rela *rela;
+
+ sec = find_section_by_name(file->elf, ".rela.discard.instr_end");
+ if (!sec)
+ return 0;
+
+ list_for_each_entry(rela, &sec->rela_list, list) {
+ if (rela->sym->type != STT_SECTION) {
+ WARN("unexpected relocation symbol type in %s", sec->name);
+ return -1;
+ }
+
+ insn = find_insn(file, rela->sym->sec, rela->addend);
+ if (!insn) {
+ WARN("bad .discard.instr_end entry");
+ return -1;
+ }
+
+ insn->instr--;
+ }
+
+ sec = find_section_by_name(file->elf, ".rela.discard.instr_begin");
+ if (!sec)
+ return 0;
+
+ list_for_each_entry(rela, &sec->rela_list, list) {
+ if (rela->sym->type != STT_SECTION) {
+ WARN("unexpected relocation symbol type in %s", sec->name);
+ return -1;
+ }
+
+ insn = find_insn(file, rela->sym->sec, rela->addend);
+ if (!insn) {
+ WARN("bad .discard.instr_begin entry");
+ return -1;
+ }
+
+ insn->instr++;
+ }
+
+ return 0;
+}
+
static void mark_rodata(struct objtool_file *file)
{
struct section *sec;
@@ -1421,6 +1471,10 @@ static int decode_sections(struct objtoo
if (ret)
return ret;

+ ret = read_instr_hints(file);
+ if (ret)
+ return ret;
+
return 0;
}

@@ -1972,6 +2026,14 @@ static inline const char *call_dest_name

static int validate_call(struct instruction *insn, struct insn_state *state)
{
+ if (state->noinstr && state->instr <= 0 &&
+ (!insn->call_dest || insn->call_dest->sec != insn->sec)) {
+ WARN_FUNC("call to %s() leaves .noinstr.text section",
+ insn->sec, insn->offset, call_dest_name(insn));
+ return 1;
+ }
+
+
if (state->uaccess && !func_uaccess_safe(insn->call_dest)) {
WARN_FUNC("call to %s() with UACCESS enabled",
insn->sec, insn->offset, call_dest_name(insn));
@@ -2000,6 +2062,12 @@ static int validate_sibling_call(struct

static int validate_return(struct symbol *func, struct instruction *insn, struct insn_state *state)
{
+ if (state->noinstr && state->instr > 0) {
+ WARN_FUNC("return with instrumentation enabled",
+ insn->sec, insn->offset);
+ return 1;
+ }
+
if (state->uaccess && !func_uaccess_safe(func)) {
WARN_FUNC("return with UACCESS enabled",
insn->sec, insn->offset);
@@ -2081,6 +2149,9 @@ static int validate_branch(struct objtoo
return 0;
}

+ if (state.noinstr)
+ state.instr += insn->instr;
+
if (insn->hint) {
if (insn->restore) {
struct instruction *save_insn, *i;
@@ -2413,9 +2484,8 @@ static bool ignore_unreachable_insn(stru
return false;
}

-static int validate_functions(struct objtool_file *file)
+static int validate_sec_functions(struct objtool_file *file, struct section *sec)
{
- struct section *sec;
struct symbol *func;
struct instruction *insn;
struct insn_state state;
@@ -2428,33 +2498,63 @@ static int validate_functions(struct obj
CFI_NUM_REGS * sizeof(struct cfi_reg));
state.stack_size = initial_func_cfi.cfa.offset;

- for_each_sec(file, sec) {
- list_for_each_entry(func, &sec->symbol_list, list) {
- if (func->type != STT_FUNC)
- continue;
+ /*
+ * We need the full vmlinux for noinstr validation, otherwise we can
+ * not correctly determine insn->call_dest->sec (external symbols do
+ * not have a section).
+ */
+ if (vmlinux)
+ state.noinstr = sec->noinstr;

- if (!func->len) {
- WARN("%s() is missing an ELF size annotation",
- func->name);
- warnings++;
- }
+ list_for_each_entry(func, &sec->symbol_list, list) {
+ if (func->type != STT_FUNC)
+ continue;

- if (func->pfunc != func || func->alias != func)
- continue;
+ if (!func->len) {
+ WARN("%s() is missing an ELF size annotation",
+ func->name);
+ warnings++;
+ }

- insn = find_insn(file, sec, func->offset);
- if (!insn || insn->ignore || insn->visited)
- continue;
+ if (func->pfunc != func || func->alias != func)
+ continue;

- state.uaccess = func->uaccess_safe;
+ insn = find_insn(file, sec, func->offset);
+ if (!insn || insn->ignore || insn->visited)
+ continue;

- ret = validate_branch(file, func, insn, state);
- if (ret && backtrace)
- BT_FUNC("<=== (func)", insn);
- warnings += ret;
- }
+ state.uaccess = func->uaccess_safe;
+
+ ret = validate_branch(file, func, insn, state);
+ if (ret && backtrace)
+ BT_FUNC("<=== (func)", insn);
+ warnings += ret;
+ }
+
+ return warnings;
+}
+
+static int validate_vmlinux_functions(struct objtool_file *file)
+{
+ struct section *sec;
+
+ sec = find_section_by_name(file->elf, ".noinstr.text");
+ if (!sec) {
+ WARN("No .noinstr.text section");
+ return -1;
}

+ return validate_sec_functions(file, sec);
+}
+
+static int validate_functions(struct objtool_file *file)
+{
+ struct section *sec;
+ int warnings = 0;
+
+ for_each_sec(file, sec)
+ warnings += validate_sec_functions(file, sec);
+
return warnings;
}

@@ -2504,6 +2604,15 @@ int check(const char *_objname, bool orc
if (list_empty(&file.insn_list))
goto out;

+ if (vmlinux && !validate_dup) {
+ ret = validate_vmlinux_functions(&file);
+ if (ret < 0)
+ goto out;
+
+ warnings += ret;
+ goto out;
+ }
+
if (retpoline) {
ret = validate_retpoline(&file);
if (ret < 0)
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -20,6 +20,8 @@ struct insn_state {
unsigned char type;
bool bp_scratch;
bool drap, end, uaccess, df;
+ bool noinstr;
+ s8 instr;
unsigned int uaccess_stack;
int drap_reg, drap_offset;
struct cfi_reg vals[CFI_NUM_REGS];
@@ -35,6 +37,7 @@ struct instruction {
unsigned long immediate;
bool alt_group, dead_end, ignore, hint, save, restore, ignore_alts;
bool retpoline_safe;
+ s8 instr;
u8 visited;
struct symbol *call_dest;
struct instruction *jump_dest;
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -39,7 +39,7 @@ struct section {
char *name;
int idx;
unsigned int len;
- bool changed, text, rodata;
+ bool changed, text, rodata, noinstr;
};

struct symbol {

[Josh Poimboeuf]

Post by Peter Zijlstra
Validate that any call out of .noinstr.text is in between
instr_begin() and instr_end() annotations.
This annotation is useful to ensure correct behaviour wrt tracing
sensitive code like entry/exit and idle code. When we run code in a
sensitive context we want a guarantee no unknown code is ran.
Since this validation relies on knowing the section of call
destination symbols, we must run it on vmlinux.o instead of on
individual object files.
-d/--duplicate "duplicate validation for vmlinux"
-l/--vmlinux "vmlinux.o validation"

I'm not sure I see the point of the --vmlinux option, when it will be
autodetected anyway?

Post by Peter Zijlstra
@@ -46,5 +49,9 @@ int cmd_check(int argc, const char **arg
objname = argv[0];
+ s = strstr(objname, "vmlinux.o");
+ if (s && !s[9])
+ vmlinux = true;
+

I think this would be slightly cleaner:

if (!strcmp(basename(objname), "vmlinux.o"))
vmlinux = true;

[Peter Zijlstra]

When doing kbuild tests to see if the objtool changes affected those I
found that there was a measurable regression:

pre post

real 1m13.594 1m16.488s
user 34m58.246s 35m23.947s
sys 4m0.393s 4m27.312s

Perf showed that for small files the increased hash-table sizes were a
measurable difference. Since we already have -l "vmlinux" to
distinguish between the modes, make it also use a smaller portion of
the hash-tables.

This flips it into a small win:

real 1m14.143s
user 34m49.292s
sys 3m44.746s

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/elf.c | 51 ++++++++++++++++++++++++++++++++++-----------------
tools/objtool/elf.h | 4 ++--
2 files changed, 36 insertions(+), 19 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -27,6 +27,22 @@ static inline u32 str_hash(const char *s
return jhash(str, strlen(str), 0);
}

+static inline int elf_hash_bits(void)
+{
+ return vmlinux ? 20 : 16;
+}
+
+#define elf_hash_add(hashtable, node, key) \
+ hlist_add_head(node, &hashtable[hash_min(key, elf_hash_bits())])
+
+static void elf_hash_init(struct hlist_head *table)
+{
+ __hash_init(table, 1U << elf_hash_bits());
+}
+
+#define elf_hash_for_each_possible(name, obj, member, key) \
+ hlist_for_each_entry(obj, &name[hash_min(key, elf_hash_bits())], member)
+
static void rb_add(struct rb_root *tree, struct rb_node *node,
int (*cmp)(struct rb_node *, const struct rb_node *))
{
@@ -115,7 +131,7 @@ struct section *find_section_by_name(str
{
struct section *sec;

- hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
+ elf_hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
if (!strcmp(sec->name, name))
return sec;

@@ -127,7 +143,7 @@ static struct section *find_section_by_i
{
struct section *sec;

- hash_for_each_possible(elf->section_hash, sec, hash, idx)
+ elf_hash_for_each_possible(elf->section_hash, sec, hash, idx)
if (sec->idx == idx)
return sec;

@@ -138,7 +154,7 @@ static struct symbol *find_symbol_by_ind
{
struct symbol *sym;

- hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+ elf_hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
if (sym->idx == idx)
return sym;

@@ -205,7 +221,7 @@ struct symbol *find_symbol_by_name(struc
{
struct symbol *sym;

- hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+ elf_hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
if (!strcmp(sym->name, name))
return sym;

@@ -309,8 +325,8 @@ static int read_sections(struct elf *elf
sec->len = sec->sh.sh_size;

list_add_tail(&sec->list, &elf->sections);
- hash_add(elf->section_hash, &sec->hash, sec->idx);
- hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
+ elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
+ elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
}

if (stats)
@@ -394,8 +410,8 @@ static int read_symbols(struct elf *elf)
else
entry = &sym->sec->symbol_list;
list_add(&sym->list, entry);
- hash_add(elf->symbol_hash, &sym->hash, sym->idx);
- hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
+ elf_hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+ elf_hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
}

if (stats)
@@ -504,7 +520,7 @@ static int read_relas(struct elf *elf)
}

list_add_tail(&rela->list, &sec->rela_list);
- hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+ elf_hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
nr_rela++;
}
max_rela = max(max_rela, nr_rela);
@@ -531,15 +547,16 @@ struct elf *elf_read(const char *name, i
perror("malloc");
return NULL;
}
- memset(elf, 0, sizeof(*elf));
+ memset(elf, 0, offsetof(struct elf, sections));

- hash_init(elf->symbol_hash);
- hash_init(elf->symbol_name_hash);
- hash_init(elf->section_hash);
- hash_init(elf->section_name_hash);
- hash_init(elf->rela_hash);
INIT_LIST_HEAD(&elf->sections);

+ elf_hash_init(elf->symbol_hash);
+ elf_hash_init(elf->symbol_name_hash);
+ elf_hash_init(elf->section_hash);
+ elf_hash_init(elf->section_name_hash);
+ elf_hash_init(elf->rela_hash);
+
elf->fd = open(name, flags);
if (elf->fd == -1) {
fprintf(stderr, "objtool: Can't open '%s': %s\n",
@@ -676,8 +693,8 @@ struct section *elf_create_section(struc
shstrtab->changed = true;

list_add_tail(&sec->list, &elf->sections);
- hash_add(elf->section_hash, &sec->hash, sec->idx);
- hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
+ elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
+ elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));

return sec;
}
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -80,8 +80,8 @@ struct elf {
struct list_head sections;
DECLARE_HASHTABLE(symbol_hash, 20);
DECLARE_HASHTABLE(symbol_name_hash, 20);
- DECLARE_HASHTABLE(section_hash, 16);
- DECLARE_HASHTABLE(section_name_hash, 16);
+ DECLARE_HASHTABLE(section_hash, 20);
+ DECLARE_HASHTABLE(section_name_hash, 20);
DECLARE_HASHTABLE(rela_hash, 20);
};

[Peter Zijlstra]

Detect if noinstr text loads functions pointers from regular text,
doing so is a definite sign that indirect function calls are unsafe.

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/arch.h | 2 +
tools/objtool/check.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++
tools/objtool/check.h | 2 -
3 files changed, 71 insertions(+), 1 deletion(-)

--- a/tools/objtool/arch.h
+++ b/tools/objtool/arch.h
@@ -75,4 +75,6 @@ int arch_decode_instruction(struct elf *

bool arch_callee_saved_reg(unsigned char reg);

+#define MAX_INSN_SIZE 15
+
#endif /* _ARCH_H */
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -42,6 +42,25 @@ struct instruction *find_insn(struct obj
return NULL;
}

+static struct instruction *find_insn_containing(struct objtool_file *file, struct section *sec,
+ unsigned long offset)
+{
+ struct instruction *insn;
+ unsigned long o;
+
+ for_offset_range(o, offset - MAX_INSN_SIZE - 1, offset) {
+ hash_for_each_possible(file->insn_hash, insn, hash, sec_offset_hash(sec, o)) {
+ if (insn->sec != sec)
+ continue;
+
+ if (insn->offset <= offset && insn->offset + insn->len > offset)
+ return insn;
+ }
+ }
+
+ return NULL;
+}
+
static struct instruction *next_insn_same_sec(struct objtool_file *file,
struct instruction *insn)
{
@@ -2102,6 +2121,29 @@ static int validate_return(struct symbol
return 0;
}

+static int validate_rela(struct instruction *insn, struct insn_state *state)
+{
+ /*
+ * Assume that any text rela that's not a CALL or JMP is a load of a
+ * function pointer.
+ */
+
+ switch (insn->type) {
+ case INSN_CALL:
+ case INSN_CALL_DYNAMIC:
+ case INSN_JUMP_CONDITIONAL:
+ case INSN_JUMP_UNCONDITIONAL:
+ return 0;
+ }
+
+ if (state->noinstr && state->instr <= 0 && insn->has_text_rela) {
+ WARN_FUNC("loading non-noinstr function pointer", insn->sec, insn->offset);
+ return 1;
+ }
+
+ return 0;
+}
+
/*
* Follow the branch starting at the given instruction, and recursively follow
* any other branches (jumps). Meanwhile, track the frame pointer state at
@@ -2217,6 +2259,10 @@ static int validate_branch(struct objtoo
return 0;
}

+ ret = validate_rela(insn, &state);
+ if (ret)
+ return ret;
+
switch (insn->type) {

case INSN_RETURN:
@@ -2485,6 +2531,25 @@ static bool ignore_unreachable_insn(stru
return false;
}

+static void prepare_insn_rela(struct objtool_file *file, struct section *sec)
+{
+ struct instruction *insn;
+ struct rela *rela;
+
+ if (!sec->rela)
+ return;
+
+ list_for_each_entry(rela, &sec->rela->rela_list, list) {
+ insn = find_insn_containing(file, sec, rela->offset);
+ if (!insn)
+ continue;
+
+ insn->has_text_rela = rela->sym && rela->sym->sec &&
+ rela->sym->sec->text &&
+ !rela->sym->sec->noinstr;
+ }
+}
+
static int validate_sec_functions(struct objtool_file *file, struct section *sec)
{
struct symbol *func;
@@ -2507,6 +2572,9 @@ static int validate_sec_functions(struct
if (vmlinux)
state.noinstr = sec->noinstr;

+ if (state.noinstr)
+ prepare_insn_rela(file, sec);
+
list_for_each_entry(func, &sec->symbol_list, list) {
if (func->type != STT_FUNC)
continue;
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -36,7 +36,7 @@ struct instruction {
enum insn_type type;
unsigned long immediate;
bool alt_group, dead_end, ignore, hint, save, restore, ignore_alts;
- bool retpoline_safe;
+ bool retpoline_safe, has_text_rela;
s8 instr;
u8 visited;
struct symbol *call_dest;

[kbuild test robot]

Hi Peter,

I love your patch! Yet something to improve:

[auto build test ERROR on tip/auto-latest]
[also build test ERROR on next-20200317]
[cannot apply to tip/x86/core linux/master linus/master v5.6-rc6]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]

url: https://github.com/0day-ci/linux/commits/Peter-Zijlstra/objtool-vmlinux-o-and-noinstr-validation/20200318-035709
base: https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 3168392536d32920349af53bdd108e3b92b10f4f
config: x86_64-allyesconfig (attached as .config)
compiler: clang version 11.0.0 (git://gitmirror/llvm_project 14a1b80e044aac1947c891525cf30521be0a79b7)
reproduce:
# FIXME the reproduce steps for clang is not ready yet

If you fix the issue, kindly add following tag

check.c:2131:10: error: 12 enumeration values not handled in switch: 'INSN_JUMP_DYNAMIC', 'INSN_JUMP_DYNAMIC_CONDITIONAL', 'INSN_RETURN'... [-Werror,-Wswitch]

switch (insn->type) {
^
1 error generated.
mv: cannot stat 'tools/objtool/.check.o.tmp': No such file or directory
make[4]: *** [tools/build/Makefile.build:96: tools/objtool/check.o] Error 1
/usr/bin/ld: scripts/dtc/dtc-parser.tab.o:(.bss+0x10): multiple definition of `yylloc'; scripts/dtc/dtc-lexer.lex.o:(.bss+0x58): first defined here
clang-11: error: linker command failed with exit code 1 (use -v to see invocation)
make[2]: *** [scripts/Makefile.host:116: scripts/dtc/dtc] Error 1
make[2]: Target '__build' not remade because of errors.
make[1]: *** [Makefile:1261: scripts_dtc] Error 2
make[4]: Target '__build' not remade because of errors.
make[3]: *** [Makefile:46: tools/objtool/objtool-in.o] Error 2
make[3]: Target 'all' not remade because of errors.
make[2]: *** [Makefile:68: objtool] Error 2
make[1]: *** [Makefile:1787: tools/objtool] Error 2
make[1]: Target 'prepare' not remade because of errors.
make: *** [Makefile:180: sub-make] Error 2
10 real 23 user 18 sys 399.16% cpu make prepare

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-***@lists.01.org

[Nick Desaulniers]

Just needs a `default:` case. From personal experience, this warning
helps you track down every switch on an enum when you add a new
enumeration value.

Ignore the dtc-lexer failure, that's a separate known issue.

Post by kbuild test robot
Hi Peter,
[auto build test ERROR on tip/auto-latest]
[also build test ERROR on next-20200317]
[cannot apply to tip/x86/core linux/master linus/master v5.6-rc6]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]
url: https://github.com/0day-ci/linux/commits/Peter-Zijlstra/objtool-vmlinux-o-and-noinstr-validation/20200318-035709
base: https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 3168392536d32920349af53bdd108e3b92b10f4f
config: x86_64-allyesconfig (attached as .config)
compiler: clang version 11.0.0 (git://gitmirror/llvm_project 14a1b80e044aac1947c891525cf30521be0a79b7)
# FIXME the reproduce steps for clang is not ready yet
If you fix the issue, kindly add following tag

check.c:2131:10: error: 12 enumeration values not handled in switch: 'INSN_JUMP_DYNAMIC', 'INSN_JUMP_DYNAMIC_CONDITIONAL', 'INSN_RETURN'... [-Werror,-Wswitch]

switch (insn->type) {
^
1 error generated.
mv: cannot stat 'tools/objtool/.check.o.tmp': No such file or directory
make[4]: *** [tools/build/Makefile.build:96: tools/objtool/check.o] Error 1
/usr/bin/ld: scripts/dtc/dtc-parser.tab.o:(.bss+0x10): multiple definition of `yylloc'; scripts/dtc/dtc-lexer.lex.o:(.bss+0x58): first defined here
clang-11: error: linker command failed with exit code 1 (use -v to see invocation)
make[2]: *** [scripts/Makefile.host:116: scripts/dtc/dtc] Error 1
make[2]: Target '__build' not remade because of errors.
make[1]: *** [Makefile:1261: scripts_dtc] Error 2
make[4]: Target '__build' not remade because of errors.
make[3]: *** [Makefile:46: tools/objtool/objtool-in.o] Error 2
make[3]: Target 'all' not remade because of errors.
make[2]: *** [Makefile:68: objtool] Error 2
make[1]: *** [Makefile:1787: tools/objtool] Error 2
make[1]: Target 'prepare' not remade because of errors.
make: *** [Makefile:180: sub-make] Error 2
10 real 23 user 18 sys 399.16% cpu make prepare
---
0-DAY CI Kernel Test Service, Intel Corporation
--
You received this message because you are subscribed to the Google Groups "Clang Built Linux" group.
To view this discussion on the web visit https://groups.google.com/d/msgid/clang-built-linux/202003180747.qU4yJl06%25lkp%40intel.com.

[Peter Zijlstra]

In preparation for find_insn_containing(), change insn_hash to use
sec_offset_hash().

This actually reduces runtime; probably because mixing in the section
index reduces the collisions due to text sections all starting their
instructions at offset 0.

Runtime on vmlinux.o from 3.1 to 2.5 seconds.

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/check.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -34,9 +34,10 @@ struct instruction *find_insn(struct obj
{
struct instruction *insn;

- hash_for_each_possible(file->insn_hash, insn, hash, offset)
+ hash_for_each_possible(file->insn_hash, insn, hash, sec_offset_hash(sec, offset)) {
if (insn->sec == sec && insn->offset == offset)
return insn;
+ }

return NULL;
}
@@ -276,7 +277,7 @@ static int decode_instructions(struct ob
if (ret)
goto err;

- hash_add(file->insn_hash, &insn->hash, insn->offset);
+ hash_add(file->insn_hash, &insn->hash, sec_offset_hash(sec, insn->offset));
list_add_tail(&insn->list, &file->insn_list);
nr_insns++;
}

[Peter Zijlstra]

Have it print a few numbers which can be used to size the hashtables.

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/builtin-check.c | 3 ++-
tools/objtool/builtin.h | 2 +-
tools/objtool/check.c | 5 +++++
tools/objtool/elf.c | 18 +++++++++++++++++-
4 files changed, 25 insertions(+), 3 deletions(-)

--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -17,7 +17,7 @@
#include "builtin.h"
#include "check.h"

-bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess;
+bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;

static const char * const check_usage[] = {
"objtool check [<options>] file.o",
@@ -31,6 +31,7 @@ const struct option check_options[] = {
OPT_BOOLEAN('m', "module", &module, "Indicates the object will be part of a kernel module"),
OPT_BOOLEAN('b', "backtrace", &backtrace, "unwind on error"),
OPT_BOOLEAN('a', "uaccess", &uaccess, "enable uaccess checking"),
+ OPT_BOOLEAN('s', "stats", &stats, "print statistics"),
OPT_END(),
};

--- a/tools/objtool/builtin.h
+++ b/tools/objtool/builtin.h
@@ -8,7 +8,7 @@
#include <subcmd/parse-options.h>

extern const struct option check_options[];
-extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess;
+extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;

extern int cmd_check(int argc, const char **argv);
extern int cmd_orc(int argc, const char **argv);
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -239,6 +239,7 @@ static int decode_instructions(struct ob
struct symbol *func;
unsigned long offset;
struct instruction *insn;
+ unsigned long nr_insns = 0;
int ret;

for_each_sec(file, sec) {
@@ -274,6 +275,7 @@ static int decode_instructions(struct ob

hash_add(file->insn_hash, &insn->hash, insn->offset);
list_add_tail(&insn->list, &file->insn_list);
+ nr_insns++;
}

list_for_each_entry(func, &sec->symbol_list, list) {
@@ -291,6 +293,9 @@ static int decode_instructions(struct ob
}
}

+ if (stats)
+ printf("nr_insns: %lu\n", nr_insns);
+
return 0;

err:
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -15,6 +15,7 @@
#include <string.h>
#include <unistd.h>
#include <errno.h>
+#include "builtin.h"

#include "elf.h"
#include "warn.h"
@@ -202,6 +203,9 @@ static int read_sections(struct elf *elf
sec->len = sec->sh.sh_size;
}

+ if (stats)
+ printf("nr_sections: %lu\n", (unsigned long)sections_nr);
+
/* sanity check, one more call to elf_nextscn() should return NULL */
if (elf_nextscn(elf->elf, s)) {
WARN("section entry mismatch");
@@ -299,6 +303,9 @@ static int read_symbols(struct elf *elf)
hash_add(elf->symbol_hash, &sym->hash, sym->idx);
}

+ if (stats)
+ printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
+
/* Create parent/child links for any cold subfunctions */
list_for_each_entry(sec, &elf->sections, list) {
list_for_each_entry(sym, &sec->symbol_list, list) {
@@ -360,6 +367,7 @@ static int read_relas(struct elf *elf)
struct rela *rela;
int i;
unsigned int symndx;
+ unsigned long nr_rela, max_rela = 0, tot_rela = 0;

list_for_each_entry(sec, &elf->sections, list) {
if (sec->sh.sh_type != SHT_RELA)
@@ -374,6 +382,7 @@ static int read_relas(struct elf *elf)

sec->base->rela = sec;

+ nr_rela = 0;
for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
rela = malloc(sizeof(*rela));
if (!rela) {
@@ -401,8 +410,15 @@ static int read_relas(struct elf *elf)

list_add_tail(&rela->list, &sec->rela_list);
hash_add(sec->rela_hash, &rela->hash, rela->offset);
-
+ nr_rela++;
}
+ max_rela = max(max_rela, nr_rela);
+ tot_rela += nr_rela;
+ }
+
+ if (stats) {
+ printf("max_rela: %lu\n", max_rela);
+ printf("tot_rela: %lu\n", tot_rela);
}

return 0;

[Peter Zijlstra]

Perf shows we're spending a lot of time in find_insn() and the
statistics show we have around 3.2 million instruction. Increase the
hash table size to reduce the bucket load from around 50 to 3.

This shaves about 2s off of objtool on vmlinux.o runtime, down to 16s.

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/check.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)

--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -50,7 +50,7 @@ struct instruction {
struct objtool_file {
struct elf *elf;
struct list_head insn_list;
- DECLARE_HASHTABLE(insn_hash, 16);
+ DECLARE_HASHTABLE(insn_hash, 20);
bool ignore_unreachables, c_file, hints, rodata;
};

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/elf.c | 2 +-
tools/objtool/elf.h | 2 +-
tools/objtool/warn.h | 2 +-
3 files changed, 3 insertions(+), 3 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -187,7 +187,7 @@ struct symbol *find_symbol_containing(st
return NULL;
}

-struct symbol *find_containing_func(struct section *sec, unsigned long offset)
+struct symbol *find_func_containing(struct section *sec, unsigned long offset)
{
struct rb_node *node;

--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -91,7 +91,7 @@ struct symbol *find_symbol_containing(st
struct rela *find_rela_by_dest(struct section *sec, unsigned long offset);
struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
unsigned int len);
-struct symbol *find_containing_func(struct section *sec, unsigned long offset);
+struct symbol *find_func_containing(struct section *sec, unsigned long offset);
struct section *elf_create_section(struct elf *elf, const char *name, size_t
entsize, int nr);
struct section *elf_create_rela_section(struct elf *elf, struct section *base);
--- a/tools/objtool/warn.h
+++ b/tools/objtool/warn.h
@@ -21,7 +21,7 @@ static inline char *offstr(struct sectio
char *name, *str;
unsigned long name_off;

- func = find_containing_func(sec, offset);
+ func = find_func_containing(sec, offset);
if (func) {
name = func->name;
name_off = offset - func->offset;

[Peter Zijlstra]

Trivial 'cleanup' to save one indentation level and match
validate_call().

Signed-off-by: Peter Zijlstra (Intel) <***@infradead.org>
---
tools/objtool/check.c | 64 ++++++++++++++++++++++++++++----------------------
1 file changed, 36 insertions(+), 28 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -1935,6 +1935,41 @@ static int validate_sibling_call(struct
return validate_call(insn, state);
}

+static int validate_return(struct symbol *func, struct instruction *insn, struct insn_state *state)
+{
+ if (state->uaccess && !func_uaccess_safe(func)) {
+ WARN_FUNC("return with UACCESS enabled",
+ insn->sec, insn->offset);
+ return 1;
+ }
+
+ if (!state->uaccess && func_uaccess_safe(func)) {
+ WARN_FUNC("return with UACCESS disabled from a UACCESS-safe function",
+ insn->sec, insn->offset);
+ return 1;
+ }
+
+ if (state->df) {
+ WARN_FUNC("return with DF set",
+ insn->sec, insn->offset);
+ return 1;
+ }
+
+ if (func && has_modified_stack_frame(state)) {
+ WARN_FUNC("return with modified stack frame",
+ insn->sec, insn->offset);
+ return 1;
+ }
+
+ if (state->bp_scratch) {
+ WARN("%s uses BP as a scratch register",
+ func->name);
+ return 1;
+ }
+
+ return 0;
+}
+
/*
* Follow the branch starting at the given instruction, and recursively follow
* any other branches (jumps). Meanwhile, track the frame pointer state at
@@ -2050,34 +2085,7 @@ static int validate_branch(struct objtoo
switch (insn->type) {

case INSN_RETURN:
- if (state.uaccess && !func_uaccess_safe(func)) {
- WARN_FUNC("return with UACCESS enabled", sec, insn->offset);
- return 1;
- }
-
- if (!state.uaccess && func_uaccess_safe(func)) {
- WARN_FUNC("return with UACCESS disabled from a UACCESS-safe function", sec, insn->offset);
- return 1;
- }
-
- if (state.df) {
- WARN_FUNC("return with DF set", sec, insn->offset);
- return 1;
- }
-
- if (func && has_modified_stack_frame(&state)) {
- WARN_FUNC("return with modified stack frame",
- sec, insn->offset);
- return 1;
- }
-
- if (state.bp_scratch) {
- WARN("%s uses BP as a scratch register",
- func->name);
- return 1;
- }
-
- return 0;
+ return validate_return(func, insn, &state);

case INSN_CALL:
case INSN_CALL_DYNAMIC:

[Peter Zijlstra]

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) <***@infradead.org>
---
tools/objtool/elf.c | 13 +++++--------
tools/objtool/elf.h | 3 +--
2 files changed, 6 insertions(+), 10 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -46,13 +46,11 @@ static struct section *find_section_by_i

static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
{
- struct section *sec;
struct symbol *sym;

- list_for_each_entry(sec, &elf->sections, list)
- hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
- if (sym->idx == idx)
- return sym;
+ hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+ if (sym->idx == idx)
+ return sym;

return NULL;
}
@@ -166,7 +164,6 @@ static int read_sections(struct elf *elf
INIT_LIST_HEAD(&sec->symbol_list);
INIT_LIST_HEAD(&sec->rela_list);
hash_init(sec->rela_hash);
- hash_init(sec->symbol_hash);

list_add_tail(&sec->list, &elf->sections);

@@ -299,7 +296,7 @@ static int read_symbols(struct elf *elf)
}
sym->alias = alias;
list_add(&sym->list, entry);
- hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
+ hash_add(elf->symbol_hash, &sym->hash, sym->idx);
}

/* Create parent/child links for any cold subfunctions */
@@ -425,6 +422,7 @@ struct elf *elf_read(const char *name, i
}
memset(elf, 0, sizeof(*elf));

+ hash_init(elf->symbol_hash);
INIT_LIST_HEAD(&elf->sections);

elf->fd = open(name, flags);
@@ -486,7 +484,6 @@ struct section *elf_create_section(struc
INIT_LIST_HEAD(&sec->symbol_list);
INIT_LIST_HEAD(&sec->rela_list);
hash_init(sec->rela_hash);
- hash_init(sec->symbol_hash);

list_add_tail(&sec->list, &elf->sections);

--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -27,7 +27,6 @@ struct section {
struct list_head list;
GElf_Shdr sh;
struct list_head symbol_list;
- DECLARE_HASHTABLE(symbol_hash, 8);
struct list_head rela_list;
DECLARE_HASHTABLE(rela_hash, 16);
struct section *base, *rela;
@@ -71,7 +70,7 @@ struct elf {
int fd;
char *name;
struct list_head sections;
- DECLARE_HASHTABLE(rela_hash, 16);
+ DECLARE_HASHTABLE(symbol_hash, 20);
};

[Josh Poimboeuf]

Hi all,
Moar patches. This implements the proposed objtool validation for the
noinstr -- function attribute
instr_{begin,end}() -- annotation
Who's purpose is to annotate such code that has constraints on instrumentation
-- such as early exception code. Specifically it makes it very hard to
accidentally add code to such regions.
I've left the whole noinstr naming in place, we'll bike-shed on that later.
This should address all feedback from RFC/v1.

Looks good to me, other than a few minor comments on patch 16.

Acked-by: Josh Poimboeuf <***@redhat.com>