diff options
| -rw-r--r-- | arch/x86/kernel/Makefile | 1 | ||||
| -rw-r--r-- | arch/x86/kernel/relocate_kernel_64.S | 12 | ||||
| -rw-r--r-- | tools/objtool/Build | 5 | ||||
| -rw-r--r-- | tools/objtool/builtin-check.c | 3 | ||||
| -rw-r--r-- | tools/objtool/builtin.h | 2 | ||||
| -rw-r--r-- | tools/objtool/check.c | 268 | ||||
| -rw-r--r-- | tools/objtool/check.h | 2 | ||||
| -rw-r--r-- | tools/objtool/elf.c | 281 | ||||
| -rw-r--r-- | tools/objtool/elf.h | 51 | ||||
| -rw-r--r-- | tools/objtool/orc_gen.c | 9 | ||||
| -rw-r--r-- | tools/objtool/special.c | 4 | ||||
| -rw-r--r-- | tools/objtool/warn.h | 2 |
12 files changed, 429 insertions, 211 deletions
diff --git a/arch/x86/kernel/Makefile b/arch/x86/kernel/Makefile index 9b294c13809a..8be5926cce51 100644 --- a/arch/x86/kernel/Makefile +++ b/arch/x86/kernel/Makefile @@ -28,7 +28,6 @@ KASAN_SANITIZE_dumpstack_$(BITS).o := n KASAN_SANITIZE_stacktrace.o := n KASAN_SANITIZE_paravirt.o := n -OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o := y OBJECT_FILES_NON_STANDARD_test_nx.o := y OBJECT_FILES_NON_STANDARD_paravirt_patch.o := y diff --git a/arch/x86/kernel/relocate_kernel_64.S b/arch/x86/kernel/relocate_kernel_64.S index ef3ba99068d3..a4d9a261425b 100644 --- a/arch/x86/kernel/relocate_kernel_64.S +++ b/arch/x86/kernel/relocate_kernel_64.S @@ -9,6 +9,8 @@ #include <asm/kexec.h> #include <asm/processor-flags.h> #include <asm/pgtable_types.h> +#include <asm/nospec-branch.h> +#include <asm/unwind_hints.h> /* * Must be relocatable PIC code callable as a C function @@ -39,6 +41,7 @@ .align PAGE_SIZE .code64 SYM_CODE_START_NOALIGN(relocate_kernel) + UNWIND_HINT_EMPTY /* * %rdi indirection_page * %rsi page_list @@ -105,6 +108,7 @@ SYM_CODE_START_NOALIGN(relocate_kernel) SYM_CODE_END(relocate_kernel) SYM_CODE_START_LOCAL_NOALIGN(identity_mapped) + UNWIND_HINT_EMPTY /* set return address to 0 if not preserving context */ pushq $0 /* store the start address on the stack */ @@ -192,14 +196,12 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_mapped) 1: popq %rdx leaq PAGE_SIZE(%r10), %rsp + ANNOTATE_RETPOLINE_SAFE call *%rdx /* 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 @@ -212,6 +214,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_mapped) SYM_CODE_END(identity_mapped) SYM_CODE_START_LOCAL_NOALIGN(virtual_mapped) + UNWIND_HINT_EMPTY movq RSP(%r8), %rsp movq CR4(%r8), %rax movq %rax, %cr4 @@ -233,6 +236,7 @@ SYM_CODE_END(virtual_mapped) /* Do the copies */ SYM_CODE_START_LOCAL_NOALIGN(swap_pages) + UNWIND_HINT_EMPTY movq %rdi, %rcx /* Put the page_list in %rcx */ xorl %edi, %edi xorl %esi, %esi diff --git a/tools/objtool/Build b/tools/objtool/Build index 8dc4f0848362..66f44f5cd2a6 100644 --- 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 FORCE $(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) diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c index c807984a03c1..10fbe75ab43d 100644 --- 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(), }; diff --git a/tools/objtool/builtin.h b/tools/objtool/builtin.h index a32736f8d2a4..0b907902ee79 100644 --- 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); diff --git a/tools/objtool/check.c b/tools/objtool/check.c index 4768d91c6d68..0bfcb390ca73 100644 --- a/tools/objtool/check.c +++ b/tools/objtool/check.c @@ -72,22 +72,22 @@ static struct instruction *next_insn_same_func(struct objtool_file *file, 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)) -#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) \ @@ -97,14 +97,19 @@ static struct instruction *next_insn_same_func(struct objtool_file *file, for (insn = next_insn_same_sec(file, insn); insn; \ insn = next_insn_same_sec(file, insn)) +static bool is_static_jump(struct instruction *insn) +{ + return insn->type == INSN_JUMP_CONDITIONAL || + insn->type == INSN_JUMP_UNCONDITIONAL; +} + static bool is_sibling_call(struct instruction *insn) { /* An indirect jump is either a sibling call or a jump to a table. */ if (insn->type == INSN_JUMP_DYNAMIC) return list_empty(&insn->alts); - if (insn->type != INSN_JUMP_CONDITIONAL && - insn->type != INSN_JUMP_UNCONDITIONAL) + if (!is_static_jump(insn)) return false; /* add_jump_destinations() sets insn->call_dest for sibling calls. */ @@ -165,7 +170,7 @@ static bool __dead_end_function(struct objtool_file *file, struct symbol *func, 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 +185,7 @@ static bool __dead_end_function(struct objtool_file *file, struct symbol *func, * 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; @@ -234,6 +239,7 @@ static int decode_instructions(struct objtool_file *file) struct symbol *func; unsigned long offset; struct instruction *insn; + unsigned long nr_insns = 0; int ret; for_each_sec(file, sec) { @@ -269,6 +275,7 @@ static int decode_instructions(struct objtool_file *file) 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) { @@ -281,11 +288,14 @@ static int decode_instructions(struct objtool_file *file) return -1; } - func_for_each_insn(file, func, insn) + sym_for_each_insn(file, func, insn) insn->func = func; } } + if (stats) + printf("nr_insns: %lu\n", nr_insns); + return 0; err: @@ -415,8 +425,8 @@ static void add_ignores(struct objtool_file *file) break; case STT_SECTION: - func = find_symbol_by_offset(rela->sym->sec, rela->addend); - if (!func || func->type != STT_FUNC) + func = find_func_by_offset(rela->sym->sec, rela->addend); + if (!func) continue; break; @@ -425,7 +435,7 @@ static void add_ignores(struct objtool_file *file) continue; } - func_for_each_insn_all(file, func, insn) + func_for_each_insn(file, func, insn) insn->ignore = true; } } @@ -553,15 +563,14 @@ static int add_jump_destinations(struct objtool_file *file) unsigned long dest_off; for_each_insn(file, insn) { - if (insn->type != INSN_JUMP_CONDITIONAL && - insn->type != INSN_JUMP_UNCONDITIONAL) + if (!is_static_jump(insn)) continue; 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; @@ -657,14 +666,18 @@ static int add_call_destinations(struct objtool_file *file) 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_symbol_by_offset(insn->sec, - dest_off); + insn->call_dest = find_func_by_offset(insn->sec, dest_off); + if (!insn->call_dest) + insn->call_dest = find_symbol_by_offset(insn->sec, dest_off); - if (!insn->call_dest && !insn->ignore) { + if (insn->ignore) + continue; + + if (!insn->call_dest) { WARN_FUNC("unsupported intra-function call", insn->sec, insn->offset); if (retpoline) @@ -672,11 +685,16 @@ static int add_call_destinations(struct objtool_file *file) return -1; } + if (insn->func && insn->call_dest->type != STT_FUNC) { + WARN_FUNC("unsupported call to non-function", + insn->sec, insn->offset); + return -1; + } + } else if (rela->sym->type == STT_SECTION) { - insn->call_dest = find_symbol_by_offset(rela->sym->sec, - rela->addend+4); - if (!insn->call_dest || - insn->call_dest->type != STT_FUNC) { + insn->call_dest = find_func_by_offset(rela->sym->sec, + rela->addend+4); + if (!insn->call_dest) { WARN_FUNC("can't find call dest symbol at %s+0x%x", insn->sec, insn->offset, rela->sym->sec->name, @@ -764,8 +782,28 @@ static int handle_group_alt(struct objtool_file *file, insn->ignore = orig_insn->ignore_alts; insn->func = orig_insn->func; - if (insn->type != INSN_JUMP_CONDITIONAL && - insn->type != INSN_JUMP_UNCONDITIONAL) + /* + * Since alternative replacement code is copy/pasted by the + * kernel after applying relocations, generally such code can't + * have relative-address relocation references to outside the + * .altinstr_replacement section, unless the arch's + * alternatives code can adjust the relative offsets + * accordingly. + * + * The x86 alternatives code adjusts the offsets only when it + * encounters a branch instruction at the very beginning of the + * replacement group. + */ + if ((insn->offset != special_alt->new_off || + (insn->type != INSN_CALL && !is_static_jump(insn))) && + find_rela_by_dest_range(file->elf, insn->sec, insn->offset, insn->len)) { + + WARN_FUNC("unsupported relocation in alternatives section", + insn->sec, insn->offset); + return -1; + } + + if (!is_static_jump(insn)) continue; if (!insn->immediate) @@ -1001,7 +1039,7 @@ static struct rela *find_jump_table(struct objtool_file *file, struct instruction *insn) { struct rela *text_rela, *table_rela; - struct instruction *orig_insn = insn; + struct instruction *dest_insn, *orig_insn = insn; struct section *table_sec; unsigned long table_offset; @@ -1028,8 +1066,8 @@ static struct rela *find_jump_table(struct objtool_file *file, 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; @@ -1053,10 +1091,17 @@ static struct rela *find_jump_table(struct objtool_file *file, strcmp(table_sec->name, C_JUMP_TABLE_SECTION)) continue; - /* Each table entry has a rela associated with it. */ - table_rela = find_rela_by_dest(table_sec, table_offset); + /* + * Each table entry has a rela associated with it. The rela + * should reference text in the same function as the original + * instruction. + */ + 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); + if (!dest_insn || !dest_insn->func || dest_insn->func->pfunc != func) + continue; /* * Use of RIP-relative switch jumps is quite rare, and @@ -1082,7 +1127,7 @@ static void mark_func_jump_tables(struct objtool_file *file, 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 +1162,7 @@ static int add_func_jump_tables(struct objtool_file *file, 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; @@ -1187,7 +1232,7 @@ static int read_unwind_hints(struct objtool_file *file) 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; @@ -1935,6 +1980,41 @@ static int validate_sibling_call(struct instruction *insn, struct insn_state *st 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 @@ -1989,7 +2069,7 @@ static int validate_branch(struct objtool_file *file, struct symbol *func, 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; @@ -2050,34 +2130,7 @@ static int validate_branch(struct objtool_file *file, struct symbol *func, 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: @@ -2342,9 +2395,8 @@ static bool ignore_unreachable_insn(struct instruction *insn) return false; } -static int validate_functions(struct objtool_file *file) +static int validate_section(struct objtool_file *file, struct section *sec) { - struct section *sec; struct symbol *func; struct instruction *insn; struct insn_state state; @@ -2357,36 +2409,45 @@ static int validate_functions(struct objtool_file *file) 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; + list_for_each_entry(func, &sec->symbol_list, list) { + if (func->type != STT_FUNC) + continue; - if (!func->len) { - WARN("%s() is missing an ELF size annotation", - func->name); - warnings++; - } + if (!func->len) { + WARN("%s() is missing an ELF size annotation", + func->name); + warnings++; + } - if (func->pfunc != func || func->alias != func) - continue; + if (func->pfunc != func || func->alias != func) + continue; - insn = find_insn(file, sec, func->offset); - if (!insn || insn->ignore || insn->visited) - continue; + insn = find_insn(file, sec, func->offset); + if (!insn || insn->ignore || insn->visited) + continue; - state.uaccess = func->uaccess_safe; + state.uaccess = func->uaccess_safe; - ret = validate_branch(file, func, insn, state); - if (ret && backtrace) - BT_FUNC("<=== (func)", insn); - warnings += ret; - } + ret = validate_branch(file, func, insn, state); + if (ret && backtrace) + BT_FUNC("<=== (func)", insn); + warnings += ret; } return warnings; } +static int validate_functions(struct objtool_file *file) +{ + struct section *sec; + int warnings = 0; + + for_each_sec(file, sec) + warnings += validate_section(file, sec); + + return warnings; +} + static int validate_reachable_instructions(struct objtool_file *file) { struct instruction *insn; @@ -2405,23 +2466,6 @@ static int validate_reachable_instructions(struct objtool_file *file) 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) @@ -2489,10 +2533,14 @@ int check(const char *_objname, bool orc) } out: - cleanup(&file); + if (ret < 0) { + /* + * Fatal error. The binary is corrupt or otherwise broken in + * some way, or objtool itself is broken. Fail the kernel + * build. + */ + return ret; + } - /* ignore warnings for now until we get all the code cleaned up */ - if (ret || warnings) - return 0; return 0; } diff --git a/tools/objtool/check.h b/tools/objtool/check.h index 6d875ca6fce0..f0ce8ffe7135 100644 --- 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; }; diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c index edba4745f25a..09ddc8f1def3 100644 --- a/tools/objtool/elf.c +++ b/tools/objtool/elf.c @@ -15,17 +15,107 @@ #include <string.h> #include <unistd.h> #include <errno.h> +#include "builtin.h" #include "elf.h" #include "warn.h" #define MAX_NAME_LEN 128 +static inline u32 str_hash(const char *str) +{ + 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; - 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; @@ -37,7 +127,7 @@ static struct section *find_section_by_index(struct elf *elf, { 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; @@ -46,88 +136,116 @@ static struct section *find_section_by_index(struct elf *elf, 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; } 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_symbol_by_name(struct elf *elf, const char *name) +struct symbol *find_func_by_offset(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->offset == offset && s->type == STT_FUNC) + return s; + } return NULL; } struct symbol *find_symbol_containing(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 && - offset >= sym->offset && offset < sym->offset + sym->len) - 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 rela *find_rela_by_dest_range(struct section *sec, unsigned long offset, - unsigned int len) +struct symbol *find_func_containing(struct section *sec, unsigned long offset) { - struct rela *rela; - unsigned long o; + struct rb_node *node; - if (!sec->rela) - return NULL; + rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { + struct symbol *s = rb_entry(node, struct symbol, node); - for (o = offset; o < offset + len; o++) - hash_for_each_possible(sec->rela->rela_hash, rela, hash, o) - if (rela->offset == o) - return rela; + if (s->type == STT_FUNC) + return s; + } return NULL; } -struct rela *find_rela_by_dest(struct section *sec, unsigned long offset) +struct symbol *find_symbol_by_name(struct elf *elf, const char *name) { - return find_rela_by_dest_range(sec, offset, 1); + struct symbol *sym; + + hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name)) + if (!strcmp(sym->name, name)) + return sym; + + return NULL; } -struct symbol *find_containing_func(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 *func; + struct rela *rela, *r = NULL; + unsigned long o; + + if (!sec->rela) + return NULL; - list_for_each_entry(func, &sec->symbol_list, list) - if (func->type == STT_FUNC && offset >= func->offset && - offset < func->offset + func->len) - return func; + sec = sec->rela; + + 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) + continue; + + if (rela->offset >= offset && rela->offset < offset + len) { + if (!r || rela->offset < r->offset) + r = rela; + } + } + if (r) + return r; + } return NULL; } +struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset) +{ + return find_rela_by_dest_range(elf, sec, offset, 1); +} + static int read_sections(struct elf *elf) { Elf_Scn *s = NULL; @@ -155,10 +273,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); s = elf_getscn(elf->elf, i); if (!s) { @@ -193,8 +307,15 @@ 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)); } + 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"); @@ -207,8 +328,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; @@ -227,7 +349,7 @@ static int read_symbols(struct elf *elf) return -1; } memset(sym, 0, sizeof(*sym)); - alias = sym; + sym->alias = sym; sym->idx = i; @@ -265,33 +387,20 @@ 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(sym->sec->symbol_hash, &sym->hash, sym->idx); + hash_add(elf->symbol_hash, &sym->hash, sym->idx); + hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name)); } + 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) { @@ -353,6 +462,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) @@ -367,6 +477,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) { @@ -393,9 +504,16 @@ 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); + tot_rela += nr_rela; + } + + if (stats) { + printf("max_rela: %lu\n", max_rela); + printf("tot_rela: %lu\n", tot_rela); } return 0; @@ -415,6 +533,11 @@ struct elf *elf_read(const char *name, int flags) } 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); + hash_init(elf->rela_hash); INIT_LIST_HEAD(&elf->sections); elf->fd = open(name, flags); @@ -475,10 +598,6 @@ struct section *elf_create_section(struct elf *elf, const char *name, 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); s = elf_newscn(elf->elf); if (!s) { @@ -556,6 +675,10 @@ struct section *elf_create_section(struct elf *elf, const char *name, shstrtab->len += strlen(name) + 1; 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)); + return sec; } diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h index 44150204db4d..ebbb10c61e24 100644 --- a/tools/objtool/elf.h +++ b/tools/objtool/elf.h @@ -10,6 +10,8 @@ #include <gelf.h> #include <linux/list.h> #include <linux/hashtable.h> +#include <linux/rbtree.h> +#include <linux/jhash.h> #ifdef LIBELF_USE_DEPRECATED # define elf_getshdrnum elf_getshnum @@ -25,11 +27,12 @@ struct section { struct list_head list; + struct hlist_node hash; + struct hlist_node name_hash; GElf_Shdr sh; + struct rb_root symbol_tree; struct list_head symbol_list; - DECLARE_HASHTABLE(symbol_hash, 8); struct list_head rela_list; - DECLARE_HASHTABLE(rela_hash, 16); struct section *base, *rela; struct symbol *sym; Elf_Data *data; @@ -41,7 +44,9 @@ struct section { 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; @@ -71,19 +76,51 @@ struct elf { int fd; char *name; struct list_head sections; - DECLARE_HASHTABLE(rela_hash, 16); + DECLARE_HASHTABLE(symbol_hash, 20); + DECLARE_HASHTABLE(symbol_name_hash, 20); + DECLARE_HASHTABLE(section_hash, 16); + DECLARE_HASHTABLE(section_name_hash, 16); + 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, oh, idx = sec->idx; + + offset &= OFFSET_STRIDE_MASK; + + ol = offset; + oh = offset >> 32; + + __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); +struct symbol *find_func_by_offset(struct section *sec, unsigned long offset); 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 symbol *find_containing_func(struct section *sec, unsigned long offset); +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); struct section *elf_create_rela_section(struct elf *elf, struct section *base); diff --git a/tools/objtool/orc_gen.c b/tools/objtool/orc_gen.c index 27a4112848c2..41e4a2754da4 100644 --- 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 section *u_sec, struct section *ip_relasec, 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_file *file) 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_file *file) /* 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)) diff --git a/tools/objtool/special.c b/tools/objtool/special.c index fdbaa611146d..e74e0189de22 100644 --- a/tools/objtool/special.c +++ b/tools/objtool/special.c @@ -118,7 +118,7 @@ static int get_alt_entry(struct elf *elf, struct special_entry *entry, } } - 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, struct special_entry *entry, 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); diff --git a/tools/objtool/warn.h b/tools/objtool/warn.h index cbb0a02b7480..7799f60de80a 100644 --- a/tools/objtool/warn.h +++ b/tools/objtool/warn.h @@ -21,7 +21,7 @@ static inline char *offstr(struct section *sec, unsigned long offset) 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; |