[tip: objtool/core] objtool: Remove instruction::list

From: tip-bot2 for Peter Zijlstra
Date: Mon Feb 13 2023 - 06:10:41 EST

Next message: tip-bot2 for Peter Zijlstra: "[tip: objtool/core] objtool: Remove instruction::reloc"
Previous message: tip-bot2 for Peter Zijlstra: "[tip: objtool/core] objtool: Fix overlapping alternatives"
In reply to: Peter Zijlstra: "[PATCH 09/10] objtool: Remove instruction::list"
Next in thread: Nathan Chancellor: "Re: [PATCH 00/10] objtool: Honey, I shrunk the instruction"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

The following commit has been merged into the objtool/core branch of tip:

Commit-ID: 5a10ca6e6400d472553fda72e51e5ba598d24e1f
Gitweb: https://git.kernel.org/tip/5a10ca6e6400d472553fda72e51e5ba598d24e1f
Author: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
AuthorDate: Wed, 08 Feb 2023 18:18:05 +01:00
Committer: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
CommitterDate: Mon, 13 Feb 2023 11:26:09 +01:00

objtool: Remove instruction::list

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) <peterz@xxxxxxxxxxxxx>
Acked-by: Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
Tested-by: Nathan Chancellor <nathan@xxxxxxxxxx> # build only
Tested-by: Thomas Weißschuh <linux@xxxxxxxxxxxxxx> # compile and run
Link: https://lore.kernel.org/r/20230208172245.851307606@xxxxxxxxxxxxx
---
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 7e9d3d3..b0b467d 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 ab6deae..3e7c700 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 6b40977..94a33ee 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 6affd80..c54f723 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);

Next message: tip-bot2 for Peter Zijlstra: "[tip: objtool/core] objtool: Remove instruction::reloc"
Previous message: tip-bot2 for Peter Zijlstra: "[tip: objtool/core] objtool: Fix overlapping alternatives"
In reply to: Peter Zijlstra: "[PATCH 09/10] objtool: Remove instruction::list"
Next in thread: Nathan Chancellor: "Re: [PATCH 00/10] objtool: Honey, I shrunk the instruction"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]