From 1c34496e5856886d565665fb64029ecdeb080ffb Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Wed, 8 Feb 2023 18:18:05 +0100 Subject: [PATCH] objtool: Remove instruction::list MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Replace the instruction::list by allocating instructions in arrays of 256 entries and stringing them together by (amortized) find_insn(). This shrinks instruction by 16 bytes and brings it down to 128. struct instruction { - struct list_head list; /* 0 16 */ - struct hlist_node hash; /* 16 16 */ - struct list_head call_node; /* 32 16 */ - struct section * sec; /* 48 8 */ - long unsigned int offset; /* 56 8 */ - /* --- cacheline 1 boundary (64 bytes) --- */ - long unsigned int immediate; /* 64 8 */ - unsigned int len; /* 72 4 */ - u8 type; /* 76 1 */ - - /* Bitfield combined with previous fields */ + struct hlist_node hash; /* 0 16 */ + struct list_head call_node; /* 16 16 */ + struct section * sec; /* 32 8 */ + long unsigned int offset; /* 40 8 */ + long unsigned int immediate; /* 48 8 */ + u8 len; /* 56 1 */ + u8 prev_len; /* 57 1 */ + u8 type; /* 58 1 */ + s8 instr; /* 59 1 */ + u32 idx:8; /* 60: 0 4 */ + u32 dead_end:1; /* 60: 8 4 */ + u32 ignore:1; /* 60: 9 4 */ + u32 ignore_alts:1; /* 60:10 4 */ + u32 hint:1; /* 60:11 4 */ + u32 save:1; /* 60:12 4 */ + u32 restore:1; /* 60:13 4 */ + u32 retpoline_safe:1; /* 60:14 4 */ + u32 noendbr:1; /* 60:15 4 */ + u32 entry:1; /* 60:16 4 */ + u32 visited:4; /* 60:17 4 */ + u32 no_reloc:1; /* 60:21 4 */ - u16 dead_end:1; /* 76: 8 2 */ - u16 ignore:1; /* 76: 9 2 */ - u16 ignore_alts:1; /* 76:10 2 */ - u16 hint:1; /* 76:11 2 */ - u16 save:1; /* 76:12 2 */ - u16 restore:1; /* 76:13 2 */ - u16 retpoline_safe:1; /* 76:14 2 */ - u16 noendbr:1; /* 76:15 2 */ - u16 entry:1; /* 78: 0 2 */ - u16 visited:4; /* 78: 1 2 */ - u16 no_reloc:1; /* 78: 5 2 */ + /* XXX 10 bits hole, try to pack */ - /* XXX 2 bits hole, try to pack */ - /* Bitfield combined with next fields */ - - s8 instr; /* 79 1 */ - struct alt_group * alt_group; /* 80 8 */ - struct instruction * jump_dest; /* 88 8 */ - struct instruction * first_jump_src; /* 96 8 */ + /* --- cacheline 1 boundary (64 bytes) --- */ + struct alt_group * alt_group; /* 64 8 */ + struct instruction * jump_dest; /* 72 8 */ + struct instruction * first_jump_src; /* 80 8 */ union { - struct symbol * _call_dest; /* 104 8 */ - struct reloc * _jump_table; /* 104 8 */ - }; /* 104 8 */ - struct alternative * alts; /* 112 8 */ - struct symbol * sym; /* 120 8 */ - /* --- cacheline 2 boundary (128 bytes) --- */ - struct stack_op * stack_ops; /* 128 8 */ - struct cfi_state * cfi; /* 136 8 */ + struct symbol * _call_dest; /* 88 8 */ + struct reloc * _jump_table; /* 88 8 */ + }; /* 88 8 */ + struct alternative * alts; /* 96 8 */ + struct symbol * sym; /* 104 8 */ + struct stack_op * stack_ops; /* 112 8 */ + struct cfi_state * cfi; /* 120 8 */ - /* size: 144, cachelines: 3, members: 28 */ - /* sum members: 142 */ - /* sum bitfield members: 14 bits, bit holes: 1, sum bit holes: 2 bits */ - /* last cacheline: 16 bytes */ + /* size: 128, cachelines: 2, members: 29 */ + /* sum members: 124 */ + /* sum bitfield members: 22 bits, bit holes: 1, sum bit holes: 10 bits */ }; pre: 5:38.18 real, 213.25 user, 124.90 sys, 23449040 mem post: 5:03.34 real, 210.75 user, 88.80 sys, 20241232 mem Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Ingo Molnar Acked-by: Josh Poimboeuf Tested-by: Nathan Chancellor # build only Tested-by: Thomas Weißschuh # compile and run Link: https://lore.kernel.org/r/20230208172245.851307606@infradead.org --- tools/objtool/check.c | 166 +++++++++++++++--------- tools/objtool/include/objtool/check.h | 51 ++++---- tools/objtool/include/objtool/objtool.h | 1 - tools/objtool/objtool.c | 1 - 4 files changed, 133 insertions(+), 86 deletions(-) diff --git a/tools/objtool/check.c b/tools/objtool/check.c index 7e9d3d3eed65..b0b467d9608a 100644 --- a/tools/objtool/check.c +++ b/tools/objtool/check.c @@ -47,27 +47,29 @@ struct instruction *find_insn(struct objtool_file *file, return NULL; } -static struct instruction *next_insn_same_sec(struct objtool_file *file, - struct instruction *insn) +struct instruction *next_insn_same_sec(struct objtool_file *file, + struct instruction *insn) { - struct instruction *next = list_next_entry(insn, list); + if (insn->idx == INSN_CHUNK_MAX) + return find_insn(file, insn->sec, insn->offset + insn->len); - if (!next || &next->list == &file->insn_list || next->sec != insn->sec) + insn++; + if (!insn->len) return NULL; - return next; + return insn; } static struct instruction *next_insn_same_func(struct objtool_file *file, struct instruction *insn) { - struct instruction *next = list_next_entry(insn, list); + struct instruction *next = next_insn_same_sec(file, insn); struct symbol *func = insn_func(insn); if (!func) return NULL; - if (&next->list != &file->insn_list && insn_func(next) == func) + if (next && insn_func(next) == func) return next; /* Check if we're already in the subfunction: */ @@ -78,17 +80,35 @@ static struct instruction *next_insn_same_func(struct objtool_file *file, return find_insn(file, func->cfunc->sec, func->cfunc->offset); } +static struct instruction *prev_insn_same_sec(struct objtool_file *file, + struct instruction *insn) +{ + if (insn->idx == 0) { + if (insn->prev_len) + return find_insn(file, insn->sec, insn->offset - insn->prev_len); + return NULL; + } + + return insn - 1; +} + static struct instruction *prev_insn_same_sym(struct objtool_file *file, - struct instruction *insn) + struct instruction *insn) { - struct instruction *prev = list_prev_entry(insn, list); + struct instruction *prev = prev_insn_same_sec(file, insn); - if (&prev->list != &file->insn_list && insn_func(prev) == insn_func(insn)) + if (prev && insn_func(prev) == insn_func(insn)) return prev; return NULL; } +#define for_each_insn(file, insn) \ + for (struct section *__sec, *__fake = (struct section *)1; \ + __fake; __fake = NULL) \ + for_each_sec(file, __sec) \ + sec_for_each_insn(file, __sec, insn) + #define func_for_each_insn(file, func, insn) \ for (insn = find_insn(file, func->sec, func->offset); \ insn; \ @@ -96,16 +116,13 @@ static struct instruction *prev_insn_same_sym(struct objtool_file *file, #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 == sym->sec && \ - insn->offset < sym->offset + sym->len; \ - insn = list_next_entry(insn, list)) + insn && insn->offset < sym->offset + sym->len; \ + insn = next_insn_same_sec(file, 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 == sym->sec && insn->offset >= sym->offset; \ - insn = list_prev_entry(insn, list)) + for (insn = prev_insn_same_sec(file, insn); \ + insn && insn->offset >= sym->offset; \ + insn = prev_insn_same_sec(file, insn)) #define sec_for_each_insn_from(file, insn) \ for (; insn; insn = next_insn_same_sec(file, insn)) @@ -384,6 +401,9 @@ static int decode_instructions(struct objtool_file *file) int ret; for_each_sec(file, sec) { + struct instruction *insns = NULL; + u8 prev_len = 0; + u8 idx = 0; if (!(sec->sh.sh_flags & SHF_EXECINSTR)) continue; @@ -409,22 +429,31 @@ static int decode_instructions(struct objtool_file *file) sec->init = true; for (offset = 0; offset < sec->sh.sh_size; offset += insn->len) { - insn = malloc(sizeof(*insn)); - if (!insn) { - WARN("malloc failed"); - return -1; + if (!insns || idx == INSN_CHUNK_MAX) { + insns = calloc(sizeof(*insn), INSN_CHUNK_SIZE); + if (!insns) { + WARN("malloc failed"); + return -1; + } + idx = 0; + } else { + idx++; } - memset(insn, 0, sizeof(*insn)); - INIT_LIST_HEAD(&insn->call_node); + insn = &insns[idx]; + insn->idx = idx; + INIT_LIST_HEAD(&insn->call_node); insn->sec = sec; insn->offset = offset; + insn->prev_len = prev_len; ret = arch_decode_instruction(file, sec, offset, sec->sh.sh_size - offset, insn); if (ret) - goto err; + return ret; + + prev_len = insn->len; /* * By default, "ud2" is a dead end unless otherwise @@ -435,10 +464,11 @@ static int decode_instructions(struct objtool_file *file) insn->dead_end = true; hash_add(file->insn_hash, &insn->hash, sec_offset_hash(sec, insn->offset)); - list_add_tail(&insn->list, &file->insn_list); nr_insns++; } +// printf("%s: last chunk used: %d\n", sec->name, (int)idx); + list_for_each_entry(func, &sec->symbol_list, list) { if (func->type != STT_NOTYPE && func->type != STT_FUNC) continue; @@ -481,10 +511,6 @@ static int decode_instructions(struct objtool_file *file) printf("nr_insns: %lu\n", nr_insns); return 0; - -err: - free(insn); - return ret; } /* @@ -599,7 +625,7 @@ static int add_dead_ends(struct objtool_file *file) } insn = find_insn(file, reloc->sym->sec, reloc->addend); if (insn) - insn = list_prev_entry(insn, list); + insn = prev_insn_same_sec(file, insn); else if (reloc->addend == reloc->sym->sec->sh.sh_size) { insn = find_last_insn(file, reloc->sym->sec); if (!insn) { @@ -634,7 +660,7 @@ reachable: } insn = find_insn(file, reloc->sym->sec, reloc->addend); if (insn) - insn = list_prev_entry(insn, list); + insn = prev_insn_same_sec(file, insn); else if (reloc->addend == reloc->sym->sec->sh.sh_size) { insn = find_last_insn(file, reloc->sym->sec); if (!insn) { @@ -1775,6 +1801,7 @@ static int handle_group_alt(struct objtool_file *file, orig_alt_group->orig_group = NULL; orig_alt_group->first_insn = orig_insn; orig_alt_group->last_insn = last_orig_insn; + orig_alt_group->nop = NULL; } else { if (orig_alt_group->last_insn->offset + orig_alt_group->last_insn->len - orig_alt_group->first_insn->offset != special_alt->orig_len) { @@ -1876,12 +1903,11 @@ static int handle_group_alt(struct objtool_file *file, return -1; } - if (nop) - list_add(&nop->list, &last_new_insn->list); end: new_alt_group->orig_group = orig_alt_group; new_alt_group->first_insn = *new_insn; - new_alt_group->last_insn = nop ? : last_new_insn; + new_alt_group->last_insn = last_new_insn; + new_alt_group->nop = nop; new_alt_group->cfi = orig_alt_group->cfi; return 0; } @@ -1931,7 +1957,7 @@ static int handle_jump_alt(struct objtool_file *file, else file->jl_long++; - *new_insn = list_next_entry(orig_insn, list); + *new_insn = next_insn_same_sec(file, orig_insn); return 0; } @@ -3522,11 +3548,28 @@ static struct instruction *next_insn_to_validate(struct objtool_file *file, * Simulate the fact that alternatives are patched in-place. When the * end of a replacement alt_group is reached, redirect objtool flow to * the end of the original alt_group. + * + * insn->alts->insn -> alt_group->first_insn + * ... + * alt_group->last_insn + * [alt_group->nop] -> next(orig_group->last_insn) */ - if (alt_group && insn == alt_group->last_insn && alt_group->orig_group) - return next_insn_same_sec(file, alt_group->orig_group->last_insn); + if (alt_group) { + if (alt_group->nop) { + /* ->nop implies ->orig_group */ + if (insn == alt_group->last_insn) + return alt_group->nop; + if (insn == alt_group->nop) + goto next_orig; + } + if (insn == alt_group->last_insn && alt_group->orig_group) + goto next_orig; + } return next_insn_same_sec(file, insn); + +next_orig: + return next_insn_same_sec(file, alt_group->orig_group->last_insn); } /* @@ -3777,11 +3820,25 @@ static int validate_branch(struct objtool_file *file, struct symbol *func, return 0; } +static int validate_unwind_hint(struct objtool_file *file, + struct instruction *insn, + struct insn_state *state) +{ + if (insn->hint && !insn->visited && !insn->ignore) { + int ret = validate_branch(file, insn_func(insn), insn, *state); + if (ret && opts.backtrace) + BT_FUNC("<=== (hint)", insn); + return ret; + } + + return 0; +} + static int validate_unwind_hints(struct objtool_file *file, struct section *sec) { struct instruction *insn; struct insn_state state; - int ret, warnings = 0; + int warnings = 0; if (!file->hints) return 0; @@ -3789,22 +3846,11 @@ static int validate_unwind_hints(struct objtool_file *file, struct section *sec) init_insn_state(file, &state, sec); if (sec) { - insn = find_insn(file, sec, 0); - if (!insn) - return 0; + sec_for_each_insn(file, sec, insn) + warnings += validate_unwind_hint(file, insn, &state); } else { - insn = list_first_entry(&file->insn_list, typeof(*insn), list); - } - - while (&insn->list != &file->insn_list && (!sec || insn->sec == sec)) { - if (insn->hint && !insn->visited && !insn->ignore) { - ret = validate_branch(file, insn_func(insn), insn, state); - if (ret && opts.backtrace) - BT_FUNC("<=== (hint)", insn); - warnings += ret; - } - - insn = list_next_entry(insn, list); + for_each_insn(file, insn) + warnings += validate_unwind_hint(file, insn, &state); } return warnings; @@ -4070,7 +4116,7 @@ static bool ignore_unreachable_insn(struct objtool_file *file, struct instructio * * It may also insert a UD2 after calling a __noreturn function. */ - prev_insn = list_prev_entry(insn, list); + prev_insn = prev_insn_same_sec(file, insn); if ((prev_insn->dead_end || dead_end_function(file, insn_call_dest(prev_insn))) && (insn->type == INSN_BUG || @@ -4102,7 +4148,7 @@ static bool ignore_unreachable_insn(struct objtool_file *file, struct instructio if (insn->offset + insn->len >= insn_func(insn)->offset + insn_func(insn)->len) break; - insn = list_next_entry(insn, list); + insn = next_insn_same_sec(file, insn); } return false; @@ -4115,10 +4161,10 @@ static int add_prefix_symbol(struct objtool_file *file, struct symbol *func, return 0; for (;;) { - struct instruction *prev = list_prev_entry(insn, list); + struct instruction *prev = prev_insn_same_sec(file, insn); u64 offset; - if (&prev->list == &file->insn_list) + if (!prev) break; if (prev->type != INSN_NOP) @@ -4517,7 +4563,7 @@ int check(struct objtool_file *file) warnings += ret; - if (list_empty(&file->insn_list)) + if (!nr_insns) goto out; if (opts.retpoline) { @@ -4626,7 +4672,7 @@ int check(struct objtool_file *file) warnings += ret; } - if (opts.orc && !list_empty(&file->insn_list)) { + if (opts.orc && nr_insns) { ret = orc_create(file); if (ret < 0) goto out; diff --git a/tools/objtool/include/objtool/check.h b/tools/objtool/include/objtool/check.h index ab6deaed9777..3e7c7004f7df 100644 --- a/tools/objtool/include/objtool/check.h +++ b/tools/objtool/include/objtool/check.h @@ -27,7 +27,7 @@ struct alt_group { struct alt_group *orig_group; /* First and last instructions in the group */ - struct instruction *first_insn, *last_insn; + struct instruction *first_insn, *last_insn, *nop; /* * Byte-offset-addressed len-sized array of pointers to CFI structs. @@ -36,31 +36,36 @@ struct alt_group { struct cfi_state **cfi; }; +#define INSN_CHUNK_BITS 8 +#define INSN_CHUNK_SIZE (1 << INSN_CHUNK_BITS) +#define INSN_CHUNK_MAX (INSN_CHUNK_SIZE - 1) + struct instruction { - struct list_head list; struct hlist_node hash; struct list_head call_node; struct section *sec; unsigned long offset; unsigned long immediate; - unsigned int len; - u8 type; - - u16 dead_end : 1, - ignore : 1, - ignore_alts : 1, - hint : 1, - save : 1, - restore : 1, - retpoline_safe : 1, - noendbr : 1, - entry : 1, - visited : 4, - no_reloc : 1; - /* 2 bit hole */ + u8 len; + u8 prev_len; + u8 type; s8 instr; + u32 idx : INSN_CHUNK_BITS, + dead_end : 1, + ignore : 1, + ignore_alts : 1, + hint : 1, + save : 1, + restore : 1, + retpoline_safe : 1, + noendbr : 1, + entry : 1, + visited : 4, + no_reloc : 1; + /* 10 bit hole */ + struct alt_group *alt_group; struct instruction *jump_dest; struct instruction *first_jump_src; @@ -109,13 +114,11 @@ static inline bool is_jump(struct instruction *insn) struct instruction *find_insn(struct objtool_file *file, struct section *sec, unsigned long offset); -#define for_each_insn(file, insn) \ - list_for_each_entry(insn, &file->insn_list, list) +struct instruction *next_insn_same_sec(struct objtool_file *file, struct instruction *insn); -#define sec_for_each_insn(file, sec, insn) \ - for (insn = find_insn(file, sec, 0); \ - insn && &insn->list != &file->insn_list && \ - insn->sec == sec; \ - insn = list_next_entry(insn, list)) +#define sec_for_each_insn(file, _sec, insn) \ + for (insn = find_insn(file, _sec, 0); \ + insn && insn->sec == _sec; \ + insn = next_insn_same_sec(file, insn)) #endif /* _CHECK_H */ diff --git a/tools/objtool/include/objtool/objtool.h b/tools/objtool/include/objtool/objtool.h index 6b40977bcdb1..94a33ee7b363 100644 --- a/tools/objtool/include/objtool/objtool.h +++ b/tools/objtool/include/objtool/objtool.h @@ -21,7 +21,6 @@ struct pv_state { struct objtool_file { struct elf *elf; - struct list_head insn_list; DECLARE_HASHTABLE(insn_hash, 20); struct list_head retpoline_call_list; struct list_head return_thunk_list; diff --git a/tools/objtool/objtool.c b/tools/objtool/objtool.c index 6affd8067f83..c54f7235c5d9 100644 --- a/tools/objtool/objtool.c +++ b/tools/objtool/objtool.c @@ -99,7 +99,6 @@ struct objtool_file *objtool_open_read(const char *_objname) return NULL; } - INIT_LIST_HEAD(&file.insn_list); hash_init(file.insn_hash); INIT_LIST_HEAD(&file.retpoline_call_list); INIT_LIST_HEAD(&file.return_thunk_list); -- 2.25.1