Alternatives vs ORC, a slightly easier way
Subsystems (3)
cover Alternatives vs ORC, a slightly easier way
These patches replace Peter's "Alternatives vs ORC, the hard way". The end result should be the same (support for paravirt patching's using of alternatives which modify the stack).
Josh Poimboeuf (3):
objtool: Refactor ORC section generation
objtool: Add 'alt_group' struct
objtool: Support stack layout changes in alternatives
.../Documentation/stack-validation.txt | 16 +- tools/objtool/Makefile | 4 - tools/objtool/arch.h | 4 - tools/objtool/builtin-orc.c | 6 +- tools/objtool/check.c | 190 ++++++----- tools/objtool/check.h | 22 +- tools/objtool/objtool.h | 3 +- tools/objtool/orc_gen.c | 308 ++++++++++-------- tools/objtool/weak.c | 7 +- 9 files changed, 315 insertions(+), 245 deletions(-)
Signature · 1 line
2.29.2
PATCH 2/3 objtool: Add 'alt_group' struct
Create a new struct associated with each group of alternatives instructions. This will help with the removal of fake jumps, and more importantly with adding support for stack layout changes in alternatives.
--- tools/objtool/check.c | 29 +++++++++++++++++++++++------ tools/objtool/check.h | 13 ++++++++++++- 2 files changed, 35 insertions(+), 7 deletions(-)
tools/objtool/check.c +23 -6
@@ -984,20 +984,28 @@ static int handle_group_alt(struct objtool_file *file,struct instruction *orig_insn, struct instruction **new_insn) { -static unsigned int alt_group_next_index =1 ; struct instruction *last_orig_insn, *last_new_insn, *insn, *fake_jump = NULL; -unsigned int alt_group = alt_group_next_index++; +struct alt_group *orig_alt_group, *new_alt_group;unsigned long dest_off; + + orig_alt_group =malloc (sizeof (*orig_alt_group)); +if (!orig_alt_group) { +WARN ("malloc failed" ); +return -1 ; + } last_orig_insn =NULL ; insn = orig_insn;sec_for_each_insn_from (file, insn) {if (insn->offset >= special_alt->orig_off + special_alt->orig_len)break ; - insn->alt_group = alt_group; + insn->alt_group = orig_alt_group; last_orig_insn = insn; } + orig_alt_group->orig_group =NULL ; + orig_alt_group->first_insn = orig_insn; + orig_alt_group->last_insn = last_orig_insn;if (next_insn_same_sec (file, last_orig_insn)) { fake_jump =malloc (sizeof (*fake_jump));
@@ -1028,8 +1036,13 @@ static int handle_group_alt(struct objtool_file *file,return 0 ; } + new_alt_group =malloc (sizeof (*new_alt_group)); +if (!new_alt_group) { +WARN ("malloc failed" ); +return -1 ; + } + last_new_insn =NULL ; - alt_group = alt_group_next_index++; insn = *new_insn;sec_for_each_insn_from (file, insn) {struct reloc *alt_reloc;
@@ -1041,7 +1054,7 @@ static int handle_group_alt(struct objtool_file *file, insn->ignore = orig_insn->ignore_alts; insn->func = orig_insn->func; - insn->alt_group = alt_group; + insn->alt_group = new_alt_group;/* * Since alternative replacement code is copy/pasted by the
@@ -1090,6 +1103,10 @@ static int handle_group_alt(struct objtool_file *file,return -1 ; } + new_alt_group->orig_group = orig_alt_group; + new_alt_group->first_insn = *new_insn; + new_alt_group->last_insn = last_new_insn; +if (fake_jump)list_add (&fake_jump->list, &last_new_insn->list);
@@ -2405,7 +2422,7 @@ static int validate_return(struct symbol *func, struct instruction *insn, structstatic void fill_alternative_cfi (struct objtool_file *file,struct instruction *insn) {struct instruction *first_insn = insn; -int alt_group = insn->alt_group; +struct alt_group *alt_group = insn->alt_group;sec_for_each_insn_continue (file, insn) {if (insn->alt_group != alt_group)
tools/objtool/check.h +12 -1
@@ -19,6 +19,17 @@ struct insn_state {s8 instr; }; +struct alt_group { +/* +* Pointer from a replacement group to the original group. NULL if it +* *is* the original group. +*/ +struct alt_group *orig_group; + +/* First and last instructions in the group */ +struct instruction *first_insn, *last_insn; +}; +struct instruction {struct list_head list;struct hlist_node hash;
@@ -34,7 +45,7 @@ struct instruction {s8 instr;u8 visited;u8 ret_offset; -int alt_group; +struct alt_group *alt_group;struct symbol *call_dest;struct instruction *jump_dest;struct instruction *first_jump_src;
Signature · 1 line
2.29.2
PATCH 1/3 objtool: Refactor ORC section generation
In reply to Josh PoimboeufDecouple ORC entries from instructions. This simplifies the control/data flow, and is going to make it easier to support alternative instructions which change the stack layout.
--- tools/objtool/Makefile | 4 - tools/objtool/arch.h | 4 - tools/objtool/builtin-orc.c | 6 +- tools/objtool/check.h | 3 - tools/objtool/objtool.h | 3 +- tools/objtool/orc_gen.c | 272 ++++++++++++++++++------------------ tools/objtool/weak.c | 7 +- 7 files changed, 140 insertions(+), 159 deletions(-)
tools/objtool/Makefile +0 -4
@@ -46,10 +46,6 @@ ifeq ($(SRCARCH),x86) SUBCMD_ORC := y endif -ifeq ($(SUBCMD_ORC),y) - CFLAGS += -DINSN_USE_ORC -endif - export SUBCMD_CHECK SUBCMD_ORC export srctree OUTPUT CFLAGS SRCARCH AWK include $(srctree)/tools/build/Makefile.include
tools/objtool/arch.h +0 -4
@@ -11,10 +11,6 @@#include "objtool.h" #include "cfi.h" -#ifdef INSN_USE_ORC -#include <asm/orc_types.h> -#endif -enum insn_type {INSN_JUMP_CONDITIONAL ,INSN_JUMP_UNCONDITIONAL ,
tools/objtool/builtin-orc.c +1 -5
@@ -51,11 +51,7 @@ int cmd_orc(int argc, const char **argv)if (list_empty (&file->insn_list))return 0 ; - ret =create_orc (file); -if (ret) -return ret; - - ret =create_orc_sections (file); + ret =orc_create (file);if (ret)return ret;
tools/objtool/check.h +0 -3
@@ -43,9 +43,6 @@ struct instruction {struct symbol *func;struct list_head stack_ops;struct cfi_state cfi; -#ifdef INSN_USE_ORC -struct orc_entry orc; -#endif };static inline bool is_static_jump (struct instruction *insn)
tools/objtool/objtool.h +1 -2
@@ -26,7 +26,6 @@ struct objtool_file *objtool_open_read(const char *_objname);int check (struct objtool_file *file);int orc_dump (const char *objname); -int create_orc (struct objtool_file *file); -int create_orc_sections (struct objtool_file *file); +int orc_create (struct objtool_file *file);#endif /* _OBJTOOL_H */
tools/objtool/orc_gen.c +137 -135
328 lines not on this page · raw message
tools/objtool/weak.c +1 -6
@@ -25,12 +25,7 @@ int __weak orc_dump(const char *_objname)UNSUPPORTED ("orc" ); } -int __weak create_orc (struct objtool_file *file) -{ -UNSUPPORTED ("orc" ); -} - -int __weak create_orc_sections (struct objtool_file *file) +int __weak orc_create (struct objtool_file *file) {UNSUPPORTED ("orc" ); }
Signature · 1 line
2.29.2
PATCH 3/3 objtool: Support stack layout changes in alternatives
In reply to Josh PoimboeufThe ORC unwinder showed a warning [1] which revealed the stack layout didn't match what was expected. The problem was that paravirt patching had replaced "CALL *pv_ops.irq.save_fl" with "PUSHF;POP". That changed the stack layout between the PUSHF and the POP, so unwinding from an interrupt which occurred between those two instructions would fail.
Part of the agreed upon solution was to rework the custom paravirt patching code to use alternatives instead, since objtool already knows how to read alternatives (and converging runtime patching infrastructure is always a good thing anyway). But the main problem still remains, which is that runtime patching can change the stack layout.
Making stack layout changes in alternatives was disallowed with commit 7117f16bf460 ("objtool: Fix ORC vs alternatives"), but now that paravirt is going to be doing it, it needs to be supported.
One way to do so would be to modify the ORC table when the code gets patched. But ORC is simple -- a good thing! -- and it's best to leave it alone.
Instead, support stack layout changes by "flattening" all possible stack states (CFI) from parallel alternative code streams into a single set of linear states. The only necessary limitation is that CFI conflicts are disallowed at all possible instruction boundaries.
For example, this scenario is allowed:
Alt1 Alt2 Alt3
0x00 CALL *pv_ops.save_fl CALL xen_save_fl PUSHF 0x01 POP %RAX 0x02 NOP
...
0x05 NOP
...
0x07 <insn>
The unwind information for offset-0x00 is identical for all 3 alternatives. Similarly offset-0x05 and higher also are identical (and the same as 0x00). However offset-0x01 has deviating CFI, but that is only relevant for Alt3, neither of the other alternative instruction streams will ever hit that offset.
This scenario is NOT allowed:
Alt1 Alt2
0x00 CALL *pv_ops.save_fl PUSHF
0x01 NOP6
...
0x07 NOP POP %RAX
The problem here is that offset-0x7, which is an instruction boundary in both possible instruction patch streams, has two conflicting stack layouts.
[ The above examples were stolen from Peter Zijlstra. ]
The new flattened CFI array is used both for the detection of conflicts (like the second example above) and the generation of linear ORC entries.
BTW, another benefit of these changes is that, thanks to some related cleanups (new fake nops and alt_group struct) objtool can finally be rid of fake jumps, which were a constant source of headaches.
[1] https://lkml.kernel.org/r/20201111170536.arx2zbn4ngvjoov7@treble
--- .../Documentation/stack-validation.txt | 16 +- tools/objtool/check.c | 175 ++++++++++-------- tools/objtool/check.h | 6 + tools/objtool/orc_gen.c | 56 +++++- 4 files changed, 157 insertions(+), 96 deletions(-)
tools/objtool/Documentation/stack-validation.txt +9 -7
@@ -315,13 +315,15 @@ they mean, and suggestions for how to fix them. function tracing inserts additional calls, which is not obvious from the sources). -10. file.o: warning: func()+0x5c: alternative modifies stack - - This means that an alternative includes instructions that modify the - stack. The problem is that there is only one ORC unwind table, this means - that the ORC unwind entries must be valid for each of the alternatives. - The easiest way to enforce this is to ensure alternatives do not contain - any ORC entries, which in turn implies the above constraint. +10. file.o: warning: func()+0x5c: stack layout conflict in alternatives + + This means that in the use of the alternative() or ALTERNATIVE() + macro, the code paths have conflicting modifications to the stack. + The problem is that there is only one ORC unwind table, which means + that the ORC unwind entries must be consistent for all possible + instruction boundaries regardless of which code has been patched. + This limitation can be overcome by massaging the alternatives with + NOPs to shift the stack changes around so they no longer conflict. 11. file.o: warning: unannotated intra-function call
tools/objtool/check.c +94 -81
274 lines not on this page · raw message
tools/objtool/check.h +6 -0
@@ -28,6 +28,12 @@ struct alt_group {/* First and last instructions in the group */ struct instruction *first_insn, *last_insn; + +/* +* Byte-offset-addressed len-sized array of pointers to CFI structs. +* This is shared with the other alt_groups in the same alternative. +*/ +struct cfi_state **cfi; };struct instruction {
tools/objtool/orc_gen.c +48 -8
69 lines not on this page · raw message
Signature · 1 line
2.29.2
Peter Zijlstra
maintainerRe: [PATCH 3/3] objtool: Support stack layout changes in alternatives
Quoted 23 lines · Josh Poimboeuf
For example, this scenario is allowed:
Alt1 Alt2 Alt3
0x00 CALL *pv_ops.save_fl CALL xen_save_fl PUSHF 0x01 POP %RAX 0x02 NOP...
0x05NOP
...
0x07<insn>This scenario is NOT allowed:
Alt1 Alt2
0x00 CALL *pv_ops.save_fl PUSHF 0x01 NOP6 ... 0x07 NOP POP %RAX
Quoted 3 lines
The problem here is that offset-0x7, which is an instruction boundary in both possible instruction patch streams, has two conflicting stack layouts.
There's another fun scenario:
0x00 CALL *pv_ops.save_fl PUSHF
0x01 NOP2
..
0x03 NOP5
..
0x07 NOP2
0x08 POP %RAX
0x09 <insn>
No conflicting boundary at 0x07, but still buggered.
Let me go read the actual patch to see if this is handled.
Re: [PATCH 3/3] objtool: Support stack layout changes in alternatives
Quoted 40 lines · Peter Zijlstra
Quoted 23 lines · Josh Poimboeuf
For example, this scenario is allowed:
Alt1 Alt2 Alt3
0x00 CALL *pv_ops.save_fl CALL xen_save_fl PUSHF 0x01 POP %RAX 0x02 NOP...
0x05NOP
...
0x07<insn>This scenario is NOT allowed:
Alt1 Alt2
0x00 CALL *pv_ops.save_fl PUSHF 0x01 NOP6 ... 0x07 NOP POP %RAXQuoted 3 lines
The problem here is that offset-0x7, which is an instruction boundary in both possible instruction patch streams, has two conflicting stack layouts.
There's another fun scenario:
0x00CALL *pv_ops.save_fl PUSHF
0x01NOP2
..
0x03NOP5
..
0x07NOP2
0x08POP %RAX
0x09<insn>
Quoted 3 lines
No conflicting boundary at
0x07, but still buggered.Let me go read the actual patch to see if this is handled.
That scenario looks good, see ORC below:
.diff --git a/arch/x86/entry/entry_64.S b/arch/x86/entry/entry_64.S index cad08703c4ad..4079a430ab3f 100644
arch/x86/entry/entry_64.S +5 -0
@@ -1483,3 +1483,8 @@ SYM_CODE_START(rewind_stack_do_exit) call do_exit SYM_CODE_END(rewind_stack_do_exit) .popsection + +SYM_FUNC_START(peter) + ALTERNATIVE "call *pv_ops+288(%rip); .byte 0x66,0x90", "pushf; .byte 0x66,0x90; .byte 0x66,0x66,0x66,0x90; popq %rax", X86_FEATURE_ALWAYS + ret +SYM_FUNC_END(peter)
00000000000014e0 <peter>:
14e0: ff 15 00 00 00 00 callq *0x0(%rip) # 14e6 <peter+0x6>
14e2: R_X86_64_PC32 pv_ops+0x11c
14e6: 66 90 xchg %ax,%ax
14e8: c3 retq
alt replacement:
cf: 9c pushfq d0: 66 90 xchg %ax,%ax d2: 66 66 66 90 data16 data16 xchg %ax,%ax d6: 58 pop %rax
ORC:
.entry.text+14e0: sp:sp+8 bp:(und) type:call end:0 .entry.text+14e1: sp:sp+16 bp:(und) type:call end:0 .entry.text+14e6: sp:sp+8 bp:(und) type:call end:0 .entry.text+14e7: sp:sp+16 bp:(und) type:call end:0 .entry.text+14e8: sp:sp+8 bp:(und) type:call end:0 .entry.text+14e9: sp:(und) bp:(und) type:call end:0
Signature · 1 line
Josh
Peter Zijlstra
maintainerRe: [PATCH 3/3] objtool: Support stack layout changes in alternatives
Quoted 46 lines · Josh Poimboeuf
Quoted 11 lines
There's another fun scenario:
0x00CALL *pv_ops.save_fl PUSHF
0x01NOP2
..
0x03NOP5
..
0x07NOP2
0x08POP %RAX
0x09<insn>Quoted 3 lines
No conflicting boundary at
0x07, but still buggered.Let me go read the actual patch to see if this is handled.
That scenario looks good, see ORC below:
.diff --git
a/arch/x86/entry/entry_64.Sb/arch/x86/entry/entry_64.Sindexcad08703c4ad..4079a430ab3f100644arch/x86/entry/entry_64.S +5
-0@@ -1483,3 +1483,8 @@ SYM_CODE_START(rewind_stack_do_exit) call do_exit SYM_CODE_END(rewind_stack_do_exit) .popsection + +SYM_FUNC_START(peter) + ALTERNATIVE "call *pv_ops+288(%rip); .byte 0x66,0x90", "pushf; .byte 0x66,0x90; .byte 0x66,0x66,0x66,0x90; popq %rax", X86_FEATURE_ALWAYS + ret +SYM_FUNC_END(peter)
00000000000014e0<peter>:
14e0: ff 15 00 00 00 00 callq *0x0(%rip) # 14e6 <peter+0x6>
14e2:R_X86_64_PC32pv_ops+0x11c
14e6: 66 90 xchg %ax,%ax
14e8: c3 retqalt replacement:
cf: 9c pushfq d0: 66 90 xchg %ax,%ax d2: 66 66 66 90 data16 data16 xchg %ax,%ax d6: 58 pop %rax
Quoted 8 lines
ORC:
.entry.text+14e0: sp:sp+8 bp:(und) type:call end:0 .entry.text+14e1: sp:sp+16 bp:(und) type:call end:0 .entry.text+14e6: sp:sp+8 bp:(und) type:call end:0 .entry.text+14e7: sp:sp+16 bp:(und) type:call end:0 .entry.text+14e8: sp:sp+8 bp:(und) type:call end:0 .entry.text+14e9: sp:(und) bp:(und) type:call end:0
Aaah, I was thinking the (LHS) NOP2 lookup would find the (RHS) PUSHF and fail, but yes, it will emit it's own +8 and find that ofcourse!
So then yes, we only need to concern outselves with same offset conflicts, and that does indeed simplify things considerably.
Re: [PATCH 3/3] objtool: Support stack layout changes in alternatives
In reply to Josh PoimboeufQuoted 3 lines · Josh Poimboeuf
BTW, another benefit of these changes is that, thanks to some related cleanups (new fake nops and
alt_groupstruct) objtool can finally be rid of fake jumps, which were a constant source of headaches.
\o/
You may also want to remove/edit the comment right before handle_group_alt() now that fake jumps are gone.
Anyway, I walked through the patch (set) and I think it should work fine (but I am not confident enough to give it Reviewed-by. My head spins :)). I even like the change.
Also, 1/3 is a benefit on its own, so if nothing else, it could go in.
Regards
Miroslav
Re: [PATCH 3/3] objtool: Support stack layout changes in alternatives
Quoted 8 lines · Miroslav Benes
Quoted 3 lines · Josh Poimboeuf
BTW, another benefit of these changes is that, thanks to some related cleanups (new fake nops and
alt_groupstruct) objtool can finally be rid of fake jumps, which were a constant source of headaches.\o/
Quoted 8 lines
You may also want to remove/edit the comment right before
handle_group_alt()now that fake jumps are gone.Anyway, I walked through the patch (set) and I think it should work fine (but I am not confident enough to give it Reviewed-by. My head spins :)). I even like the change.
Also, 1/3 is a benefit on its own, so if nothing else, it could go in.
Thanks for the review!
That comment is indeed now obsolete. I can squash something like so:
tools/objtool/check.c +2 -15
@@ -958,21 +958,8 @@ static int add_call_destinations(struct objtool_file *file) }/* -* The .alternatives section requires some extra special care, over and above -* what other special sections require: -* -* 1. Because alternatives are patched in-place, we need to insert a fake jump -* instruction at the end so that validate_branch() skips all the original -* replaced instructions when validating the new instruction path. -* -* 2. An added wrinkle is that the new instruction length might be zero. In -* that case the old instructions are replaced with noops. We simulate that -* by creating a fake jump as the only new instruction. -* -* 3. In some cases, the alternative section includes an instruction which -* conditionally jumps to the _end_ of the entry. We have to modify these -* jumps' destinations to point back to .text rather than the end of the -* entry in .altinstr_replacement. +* The .alternatives section requires some extra special care over and above +* other special sections because alternatives are patched in place. */ static int handle_group_alt(struct objtool_file *file, struct special_alt *special_alt,
Re: [PATCH 3/3] objtool: Support stack layout changes in alternatives
Quoted 20 lines
That comment is indeed now obsolete. I can squash something like so:
tools/objtool/check.c +0
-10@@ -958,21 +958,8 @@ static int add_call_destinations(struct objtool_file *file) }/* -* The .alternatives section requires some extra special care, over and above -* what other special sections require: -* -* 1. Because alternatives are patched in-place, we need to insert a fake jump -* instruction at the end so that validate_branch() skips all the original -* replaced instructions when validating the new instruction path. -* -* 2. An added wrinkle is that the new instruction length might be zero. In -* that case the old instructions are replaced with noops. We simulate that -* by creating a fake jump as the only new instruction.
tools/objtool/check.c static int add_call_destinations(struct objtool_file *file) · line 965
Quoted 10 lines
tools/objtool/check.c +2
-5-* -* 3. In some cases, the alternative section includes an instruction which -* conditionally jumps to the _end_ of the entry. We have to modify these -* jumps' destinations to point back to .text rather than the end of the -* entry in .altinstr_replacement. +* The .alternatives section requires some extra special care over and above +* other special sections because alternatives are patched in place. */ static int handle_group_alt(struct objtool_file *file, struct special_alt *special_alt,
Looks good to me.
Miroslav
Re: [PATCH 3/3] objtool: Support stack layout changes in alternatives
Quoted 24 lines · Miroslav Benes
Quoted 24 lines
That comment is indeed now obsolete. I can squash something like so:
tools/objtool/check.c +0
-14@@ -958,21 +958,8 @@ static int add_call_destinations(struct objtool_file *file) }/* -* The .alternatives section requires some extra special care, over and above -* what other special sections require: -* -* 1. Because alternatives are patched in-place, we need to insert a fake jump -* instruction at the end so that validate_branch() skips all the original -* replaced instructions when validating the new instruction path. -* -* 2. An added wrinkle is that the new instruction length might be zero. In -* that case the old instructions are replaced with noops. We simulate that -* by creating a fake jump as the only new instruction. -* -* 3. In some cases, the alternative section includes an instruction which -* conditionally jumps to the _end_ of the entry. We have to modify these -* jumps' destinations to point back to .text rather than the end of the
Quoted 8 lines
tools/objtool/check.c static int add_call_destinations(struct objtool_file *file) · line 965
Quoted 6 lines
tools/objtool/check.c +2
-1-* entry in .altinstr_replacement. +* The .alternatives section requires some extra special care over and above +* other special sections because alternatives are patched in place. */ static int handle_group_alt(struct objtool_file *file, struct special_alt *special_alt,Looks good to me.
Thanks, I squashed this in.
If there are no objections, I'll go ahead and merge this set in -tip. It doesn't have any direct dependencies on the Juergen's changes, and it would be nice to have some of these changes in-tree, especially the fake jump removal.
Signature · 1 line
Josh