x86: dynamic indirect call promotion

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

It is expected that this opcode is not in common use.

Signed-off-by Nadav Amit <[email protected]>

---
arch/x86/entry/entry_64.S | 10 ++++++++++
arch/x86/include/asm/nospec-branch.h | 12 ++++++++++++

2 files changed, 22 insertions(+)

arch/x86/entry/entry_64.S +10 -0

index cb8a5893fd33..31d59aad496e 100644
@@ -643,6 +643,16 @@ retint_kernel:
   jnc    1f
 0:    cmpl    $0, PER_CPU_VAR(__preempt_count)
   jnz    1f
+
+    /*
+     * Allow to use hint to prevent preemption on a certain instruction.
+     * Consider an instruction with the first byte having REX prefix
+     * without any bits set as an indication for preemption disabled.
+     */
+    movq    RIP(%rsp), %rax
+    cmpb    $PREEMPT_DISABLE_PREFIX, (%rax)
+    jz    1f
+
   call    preempt_schedule_irq
   jmp    0b

1:

arch/x86/include/asm/nospec-branch.h +6 -0

index 80dc14422495..0267611eb247 100644
@@ -52,6 +52,12 @@
   jnz    771b;                \
   add    $(BITS_PER_LONG/8) * nr, sp;
 
+/*
+ * An empty REX-prefix is an indication that preemption should not take place on
+ * this instruction.
+ */
+#define PREEMPT_DISABLE_PREFIX                 (0x40)
+
 #ifdef __ASSEMBLY__
 
 /*

@@ -148,6 +154,12 @@
 #endif

.endm

+.macro preempt_disable_prefix

arch/x86/include/asm/nospec-branch.h +5 -0

+#ifdef CONFIG_PREEMPT
+    .byte    PREEMPT_DISABLE_PREFIX
+#endif
+.endm
+

#else /* __ASSEMBLY__ */

#define ANNOTATE_NOSPEC_ALTERNATIVE \

Signature · 1 line

2.17.1

Quoted 10 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Quoted 12 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

Quoted 7 lines

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

I agree that for super-general case this might be inappropriate.

Quoted 13 lines · Andy Lutomirski

Quoted 10 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

Quoted 7 lines

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Quoted 22 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

Quoted 6 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Look for cond_local_irq_enable().

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 3 lines

Quoted 3 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Quoted 5 lines

Quoted 3 lines

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

To be frank, I paid relatively little attention to this subject. Any feedback about the other parts and especially on the high-level approach? Is modifying the retpolines in the proposed manner (assembly macros) acceptable?

Thanks,
Nadav

Quoted 40 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 3 lines

Quoted 3 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Quoted 8 lines

Quoted 5 lines

Quoted 3 lines

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

I’m not totally certain there’s a case that matters. But it’s worth checking

Quoted 4 lines

To be frank, I paid relatively little attention to this subject. Any feedback about the other parts and especially on the high-level approach? Is modifying the retpolines in the proposed manner (assembly macros) acceptable?

It’s certainly a neat idea, and it could be a real speedup.

Quoted 49 lines · Andy Lutomirski

Quoted 40 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 3 lines

Quoted 3 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Quoted 8 lines

Quoted 5 lines

Quoted 3 lines

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

Quoted 8 lines

I’m not totally certain there’s a case that matters. But it’s worth checking

Quoted 4 lines

To be frank, I paid relatively little attention to this subject. Any feedback about the other parts and especially on the high-level approach? Is modifying the retpolines in the proposed manner (assembly macros) acceptable?

It’s certainly a neat idea, and it could be a real speedup.

Great. So I’ll try to shape things up, and I still wait for other comments (from others).

I’ll just mention two more patches I need to cleanup (I know I still owe you some work, so obviously it will be done later):

1. Seccomp trampolines. On my Ubuntu, when I run Redis, systemd installs 17 BPF filters on the Redis server process that are invoked on each system-call. Invoking each one requires an indirect branch. The patch keeps a per-process kernel code-page that holds trampolines for these functions.

2. Binary-search for system-calls. Use the per-process kernel code-page also to hold multiple trampolines for the 16 common system calls of a certain process. The patch uses an indirection table and a binary-search to find the proper trampoline.

Thanks again,
Nadav

Quoted 64 lines · Nadav Amit

Quoted 47 lines · Andy Lutomirski

Quoted 38 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 3 lines

Quoted 3 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Quoted 8 lines

Quoted 5 lines

Quoted 3 lines

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

Quoted 8 lines

I’m not totally certain there’s a case that matters. But it’s worth checking

Quoted 4 lines

To be frank, I paid relatively little attention to this subject. Any feedback about the other parts and especially on the high-level approach? Is modifying the retpolines in the proposed manner (assembly macros) acceptable?

It’s certainly a neat idea, and it could be a real speedup.

Great. So I’ll try to shape things up, and I still wait for other comments (from others).

I’ll just mention two more patches I need to cleanup (I know I still owe you some work, so obviously it will be done later):

Quoted 4 lines

1. Seccomp trampolines. On my Ubuntu, when I run Redis, systemd installs 17 BPF filters on the Redis server process that are invoked on each system-call. Invoking each one requires an indirect branch. The patch keeps a per-process kernel code-page that holds trampolines for these functions.

I wonder how many levels of branches are needed before the branches involved exceed the retpoline cost.

Quoted 4 lines

2. Binary-search for system-calls. Use the per-process kernel code-page also to hold multiple trampolines for the 16 common system calls of a certain process. The patch uses an indirection table and a binary-search to find the proper trampoline.

Same comment applies here.

Quoted 44 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Quoted 4 lines

Quoted 1 line

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

I’m not totally certain there’s a case that matters. But it’s worth checking

Quoted 44 lines · Andy Lutomirski

Quoted 44 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

I’m not totally certain there’s a case that matters. But it’s worth checking

I am still checking. But, I wanted to ask you whether the existing code is correct, since it seems to me that others do the same mistake I did, unless I don’t understand the code.

Consider for example do_int3(), and see my inlined comments:

dotraplinkage void notrace do_int3(struct pt_regs *regs, long error_code) {
...
ist_enter(regs); // => preempt_disable()
cond_local_irq_enable(regs); // => assume it enables IRQs

   ...
   // resched irq can be delivered here. It will not caused rescheduling
   // since preemption is disabled

   cond_local_irq_disable(regs);    // => assume it disables IRQs
   ist_exit(regs);            // => preempt_enable_no_resched()
}

At this point resched will not happen for unbounded length of time (unless there is another point when exiting the trap handler that checks if preemption should take place).

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Am I missing something?

Thanks,
Nadav

Quoted 69 lines · Nadav Amit

Quoted 42 lines · Andy Lutomirski

Quoted 42 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

I’m not totally certain there’s a case that matters. But it’s worth checking

I am still checking. But, I wanted to ask you whether the existing code is correct, since it seems to me that others do the same mistake I did, unless I don’t understand the code.

Consider for example do_int3(), and see my inlined comments:

dotraplinkage void notrace do_int3(struct pt_regs *regs, long error_code) {
...
ist_enter(regs); // => preempt_disable()
cond_local_irq_enable(regs); // => assume it enables IRQs

...
// resched irq can be delivered here. It will not caused rescheduling // since preemption is disabled

Quoted 7 lines

cond_local_irq_disable(regs); // => assume it disables IRQs
ist_exit(regs); // => preempt_enable_no_resched()
}

At this point resched will not happen for unbounded length of time (unless there is another point when exiting the trap handler that checks if preemption should take place).

I think it's only a bug in the cases where someone uses extable to fix up an int3 (which would be nuts) or that we oops. But I should still fix it. In the normal case where int3 was in user code, we'll miss the reschedule in do_trap(), but we'll reschedule in prepare_exit_to_usermode() -> exit_to_usermode_loop().

Quoted 77 lines · Andy Lutomirski

Quoted 69 lines · Nadav Amit

Quoted 42 lines · Andy Lutomirski

Quoted 42 lines · Nadav Amit

Quoted 23 lines · Andy Lutomirski

Quoted 23 lines · Nadav Amit

Quoted 19 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs. First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens ― you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable(). To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying…

Quoted 4 lines

Quoted 4 lines

Yes, I didn’t pay enough attention here. For my use-case, I think that the easiest solution would be to make synchronize_sched() ignore preemptions that happen while the prefix is detected. It would slightly change the meaning of the prefix.

So thinking about it further, rewinding the instruction seems the easiest and most robust solution. I’ll do it.

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

You also aren’t accounting for the case where you get an exception that is, in turn, preempted.

Hmm.. Can you give me an example for such an exception in my use-case? I cannot think of an exception that might be preempted (assuming #BP, #MC cannot be preempted).

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Look for cond_local_irq_enable().

I looked at it. Yet, I still don’t see how exceptions might happen in my use-case, but having said that - this can be fixed too.

I’m not totally certain there’s a case that matters. But it’s worth checking

I am still checking. But, I wanted to ask you whether the existing code is correct, since it seems to me that others do the same mistake I did, unless I don’t understand the code.

Consider for example do_int3(), and see my inlined comments:

dotraplinkage void notrace do_int3(struct pt_regs *regs, long error_code) {
...
ist_enter(regs); // => preempt_disable()
cond_local_irq_enable(regs); // => assume it enables IRQs

...
// resched irq can be delivered here. It will not caused rescheduling // since preemption is disabled

Quoted 7 lines

cond_local_irq_disable(regs); // => assume it disables IRQs
ist_exit(regs); // => preempt_enable_no_resched()
}

At this point resched will not happen for unbounded length of time (unless there is another point when exiting the trap handler that checks if preemption should take place).

Quoted 5 lines

I think it's only a bug in the cases where someone uses extable to fix up an int3 (which would be nuts) or that we oops. But I should still fix it. In the normal case where int3 was in user code, we'll miss the reschedule in do_trap(), but we'll reschedule in prepare_exit_to_usermode() -> exit_to_usermode_loop().

Thanks for your quick response, and sorry for bothering instead of dealing with it. Note that do_debug() does something similar to do_int3().

And then there is optimized_callback() that also uses preempt_enable_no_resched(). I think the original use was correct, but then a19b2e3d7839 ("kprobes/x86: Remove IRQ disabling from ftrace-based/optimized kprobes”) removed the IRQ disabling, while leaving preempt_enable_no_resched() . No?

Quoted 4 lines

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Alexei, I think this code is just wrong.

Do you know why it uses
preempt_enable_no_resched()?

Quoted 6 lines

Quoted 4 lines

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Alexei, I think this code is just wrong.

why 'just wrong' ?

Quoted 3 lines

Do you know why it uses
preempt_enable_no_resched()?

dont recall precisely.
we could be preemptable at the point where macro is called. I think the goal of no_resched was to avoid adding scheduling points where they didn't exist before just because a prog ran for few nsec. May be Daniel or Roman remember.

Quoted 8 lines · Alexei Starovoitov

Quoted 6 lines

Quoted 4 lines

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Alexei, I think this code is just wrong.

why 'just wrong' ?

Because you lost a preemption point, this is a no-no.

Quoted 9 lines

Quoted 3 lines

Do you know why it uses
preempt_enable_no_resched()?

dont recall precisely.
we could be preemptable at the point where macro is called. I think the goal of no_resched was to avoid adding scheduling points where they didn't exist before just because a prog ran for few nsec. May be Daniel or Roman remember.

No, you did the exact opposite, where there previously was a preemption, you just ate it. The band saw didn't get stopped in time, you loose your hand etc..

Quoted 2 lines

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Alexei, I think this code is just wrong. Do you know why it uses preempt_enable_no_resched()?

Oleg, the code in kernel/signal.c:

                preempt_disable();
                read_unlock(&tasklist_lock);
                preempt_enable_no_resched();
                freezable_schedule();

Oleg, the code in kernel/signal.c:

                preempt_disable();
                read_unlock(&tasklist_lock);
                preempt_enable_no_resched();
                freezable_schedule();

looks bogus. I don't get what it's trying to achieve with preempt_disable(), and I also don't see why no_resched does anything. Sure, it prevents a reschedule triggered during read_unlock() from causing a reschedule,

but it doesn't prevent an interrupt immediately after the preempt_enable_no_resched() call from scheduling.

Consider for example do_int3(), and see my inlined comments:

dotraplinkage void notrace do_int3(struct pt_regs *regs, long error_code)

{
	...
	ist_enter(regs); 		// => preempt_disable()
	cond_local_irq_enable(regs);	// => assume it enables IRQs

	...
	// resched irq can be delivered here. It will not caused rescheduling
	// since preemption is disabled

	cond_local_irq_disable(regs);	// => assume it disables IRQs
	ist_exit(regs);			// => preempt_enable_no_resched()
}

At this point resched will not happen for unbounded length of time (unless there is another point when exiting the trap handler that checks if preemption should take place).

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Am I missing something?

Quoted 22 lines · Nadav Amit

Consider for example do_int3(), and see my inlined comments:

dotraplinkage void notrace do_int3(struct pt_regs *regs, long error_code) {
...
ist_enter(regs); // => preempt_disable()
cond_local_irq_enable(regs); // => assume it enables IRQs

   ...
   // resched irq can be delivered here. It will not caused rescheduling
   // since preemption is disabled

   cond_local_irq_disable(regs);    // => assume it disables IRQs
   ist_exit(regs);            // => preempt_enable_no_resched()
}

At this point resched will not happen for unbounded length of time (unless there is another point when exiting the trap handler that checks if preemption should take place).

Quoted 4 lines

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Am I missing something?

Would not the interrupt return then check for TIF_NEED_RESCHED and call schedule() ?

I think (and this certainly wants a comment) is that the ist_exit() thing hard relies on the interrupt-return path doing the reschedule.

Quoted 23 lines · Peter Zijlstra

Quoted 22 lines · Nadav Amit

Consider for example do_int3(), and see my inlined comments:

dotraplinkage void notrace do_int3(struct pt_regs *regs, long error_code) {
...
ist_enter(regs); // => preempt_disable()
cond_local_irq_enable(regs); // => assume it enables IRQs

   ...
   // resched irq can be delivered here. It will not caused rescheduling
   // since preemption is disabled

   cond_local_irq_disable(regs);    // => assume it disables IRQs
   ist_exit(regs);            // => preempt_enable_no_resched()
}

At this point resched will not happen for unbounded length of time (unless there is another point when exiting the trap handler that checks if preemption should take place).

Quoted 7 lines

Quoted 4 lines

Another example is __BPF_PROG_RUN_ARRAY(), which also uses preempt_enable_no_resched().

Am I missing something?

Would not the interrupt return then check for TIF_NEED_RESCHED and call schedule() ?

The paranoid exit path doesn’t check TIF_NEED_RESCHED because it’s fundamentally atomic — it’s running on a percpu stack and it can’t schedule. In theory we could do some evil stack switching, but we don’t.

How does NMI handle this? If an NMI that hit interruptible kernel code overflows a perf counter, how does the wake up work?

Quoted 10 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs.

First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable().

To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying...

Quoted 18 lines · Andy Lutomirski

Quoted 9 lines · Nadav Amit

It is sometimes beneficial to prevent preemption for very few instructions, or prevent preemption for some instructions that precede a branch (this latter case will be introduced in the next patches).

To provide such functionality on x86-64, we use an empty REX-prefix (opcode 0x40) as an indication that preemption is disabled for the following instruction.

Nifty!

That being said, I think you have a few bugs.

First, you can’t just ignore a rescheduling interrupt, as you introduce unbounded latency when this happens — you’re effectively emulating preempt_enable_no_resched(), which is not a drop-in replacement for preempt_enable().

Quoted 3 lines

To fix this, you may need to jump to a slow-path trampoline that calls schedule() at the end or consider rewinding one instruction instead. Or use TF, which is only a little bit terrifying...

At which point we're very close to in-kernel rseq.

		base		relpoline
		----		---------

nginx 22898 25178 (+10%)
redis-ycsb 24523 25486 (+4%)
dbench 2144 2103 (+2%)

Quoted 5 lines · Nadav Amit

base relpoline

		----		---------

nginx 22898 25178 (+10%)
redis-ycsb 24523 25486 (+4%)
dbench 2144 2103 (+2%)

Just out of curiosity, which indirect branches are the culprits here for causing the slowdowns?

Quoted 8 lines · Nadav Amit

Quoted 5 lines

base relpoline

		----		---------

nginx 22898 25178 (+10%)
redis-ycsb 24523 25486 (+4%)
dbench 2144 2103 (+2%)

Just out of curiosity, which indirect branches are the culprits here for causing the slowdowns?

So I didn’t try to measure exactly which one. There are roughly 500 that actually “run” in my tests.

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

		base		relpoline
		----		---------

nginx 22898 25178 (+10%)
redis-ycsb 24523 25486 (+4%)
dbench 2144 2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 39 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

		base		relpoline
		----		---------

nginx 22898 25178 (+10%)
redis-ycsb 24523 25486 (+4%)
dbench 2144 2103 (+2%)

Quoted 2 lines

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Some high-level comments:

- "Relpoline" looks confusingly a lot like "retpoline". How about "optpoline"? To avoid confusing myself I will hereafter refer to it as such :-)

- Instead of patching one byte at a time, is there a reason why text_poke_bp() can't be used? That would greatly simplify the patching process, as everything could be patched in a single step.

- In many cases, a single direct call may not be sufficient, as there could be for example multiple tasks using different network protocols which need different callbacks for the same call site.

- I'm not sure about the periodic retraining logic, it seems a bit nondeterministic and bursty.

So I'd propose the following changes:

- In the optpoline, reserve space for multiple (5 or so) comparisons and direct calls. Maybe the number of reserved cmp/jne/call slots can be tweaked by the caller somehow. Or maybe it could grow as needed. Starting out, they would just be NOPs.

- Instead of the temporary learning mode, add permanent tracking to detect a direct call "miss" -- i.e., when none of the existing direct calls are applicable and the retpoline will be used.

- In the case of a miss (or N misses), it could trigger a direct call patching operation to be run later (workqueue or syscall exit). If all the direct call slots are full, it could patch the least recently modified one. If this causes thrashing (>x changes over y time), it could increase the number of direct call slots using a trampoline. Even if there were several slots, CPU branch prediction would presumably help make it much faster than a basic retpoline.

Thoughts?

Quoted 45 lines · Josh Poimboeuf

Quoted 41 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

		base		relpoline
		----		---------

nginx 22898 25178 (+10%)
redis-ycsb 24523 25486 (+4%)
dbench 2144 2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Quoted 5 lines

Some high-level comments:

- "Relpoline" looks confusingly a lot like "retpoline". How about "optpoline"? To avoid confusing myself I will hereafter refer to it as such :-)

Sure. For the academic paper we submitted, we used a much worse name that my colleague came up with. I’m ok with anything other than that name (not mentioned to prevent double-blinding violations). I’ll go with your name.

Quoted 3 lines

- Instead of patching one byte at a time, is there a reason why text_poke_bp() can't be used? That would greatly simplify the patching process, as everything could be patched in a single step.

I thought of it and maybe it is somehow possible, but there are several problems, for which I didn’t find a simple solution:

1. An indirect branch inside the BP handler might be the one we patch

2. An indirect branch inside an interrupt or NMI handler might be the one we patch

3. Overall, we need to patch more than a single instruction, and text_poke_bp() is not suitable

Quoted 3 lines

- In many cases, a single direct call may not be sufficient, as there could be for example multiple tasks using different network protocols which need different callbacks for the same call site.

We want to know during compilation how many targets to use. It is not super-simple to support multiple inlined targets, but it is feasible if you are willing to annotate when multiple targets are needed.

We have a version which uses outlined indirect branch promotion when there are multiple targets, but it’s not ready for prime time, and the code-cache misses can induce some overheads.

Quoted 2 lines

- I'm not sure about the periodic retraining logic, it seems a bit nondeterministic and bursty.

I agree. It can be limited to cases in which modules are loaded/removed, or when the user explicitly asks for it to take place.

Quoted 20 lines

So I'd propose the following changes:

- In the optpoline, reserve space for multiple (5 or so) comparisons and direct calls. Maybe the number of reserved cmp/jne/call slots can be tweaked by the caller somehow. Or maybe it could grow as needed. Starting out, they would just be NOPs.

- Instead of the temporary learning mode, add permanent tracking to detect a direct call "miss" -- i.e., when none of the existing direct calls are applicable and the retpoline will be used.

- In the case of a miss (or N misses), it could trigger a direct call patching operation to be run later (workqueue or syscall exit). If all the direct call slots are full, it could patch the least recently modified one. If this causes thrashing (>x changes over y time), it could increase the number of direct call slots using a trampoline. Even if there were several slots, CPU branch prediction would presumably help make it much faster than a basic retpoline.

Quoted 1 line

Thoughts?

I’m ok with these changes in general, although having multiple inline targets is not super-simple. However, there are a few issues:

- There is potentially a negative impact due to code-size increase which I was worried about.

- I see no reason not to use all the available slots immediately when we encounter a miss.

- The order of the branches might be “wrong” (unoptimized) if we do not do any relearning.

- The main question is what to do if we run out of slots and still get (many?) misses. I presume the right thing is to disable the optpoline and jump over it to the retpoline.

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 41 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

           base            relpoline
           ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 3 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

Quoted 4 lines

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Callees can clobber flags, so it seems fine to me.

Quoted 2 lines

1. An indirect branch inside the BP handler might be the one we patch

I _think_ nested INT3s should be doable, because they don't use IST. Maybe Andy can clarify.

Quoted 2 lines

2. An indirect branch inside an interrupt or NMI handler might be the one we patch

But INT3s just use the existing stack, and NMIs support nesting, so I'm thinking that should also be doable. Andy?

Quoted 64 lines · Josh Poimboeuf

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 41 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

          base            relpoline
          ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 7 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Quoted 1 line

Callees can clobber flags, so it seems fine to me.

Just to check I understand your approach right: you made a macro called "call", and you're therefore causing all instances of "call" to become magic? This is... terrifying. It's even plausibly worse than "#define if" :) The scariest bit is that it will impact inline asm as well. Maybe a gcc plugin would be less alarming?

Quoted 4 lines

Quoted 1 line

1. An indirect branch inside the BP handler might be the one we patch

I _think_ nested INT3s should be doable, because they don't use IST. Maybe Andy can clarify.

int3 should survive recursion these days. Although I admit I'm currently wondering what happens if one thread puts a kprobe on an address that another thread tries to text_poke.

Also, this relpoline magic is likely to start patching text at runtime on a semi-regular basis. This type of patching is *slow*. Is it a problem?

Quoted 6 lines

Quoted 3 lines

2. An indirect branch inside an interrupt or NMI handler might be the one we patch

But INT3s just use the existing stack, and NMIs support nesting, so I'm thinking that should also be doable. Andy?

In principle, as long as the code isn't NOKPROBE_SYMBOL-ified, we should be fine, right? I'd be a little nervous if we get an int3 in the C code that handles the early part of an NMI from user mode. It's *probably* okay, but one of the alarming issues is that the int3 return path will implicitly unmask NMI, which isn't fantastic. Maybe we finally need to dust off my old "return using RET" code to get rid of that problem.

Quoted 67 lines · Andy Lutomirski

Quoted 66 lines · Josh Poimboeuf

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 43 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

         base            relpoline
         ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 7 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Quoted 7 lines

Quoted 1 line

Callees can clobber flags, so it seems fine to me.

Just to check I understand your approach right: you made a macro called "call", and you're therefore causing all instances of "call" to become magic? This is... terrifying. It's even plausibly worse than "#define if" :) The scariest bit is that it will impact inline asm as well. Maybe a gcc plugin would be less alarming?

It is likely to look less alarming. When I looked at the inline retpoline implementation of gcc, it didn’t look much better than what I did - it basically just emits assembly instructions.

Anyhow, I look (again) into using gcc-plugins.

Quoted 5 lines

Quoted 4 lines

Quoted 1 line

1. An indirect branch inside the BP handler might be the one we patch

I _think_ nested INT3s should be doable, because they don't use IST. Maybe Andy can clarify.

Quoted 3 lines

int3 should survive recursion these days. Although I admit I'm currently wondering what happens if one thread puts a kprobe on an address that another thread tries to text_poke.

The issue I regarded is having an indirect call *inside* the the handler. For example, you try to patch the call to bp_int3_handler and then get an int3. They can be annotated to prevent them from being patched. Then again, I need to see how gcc plugins can get these annotations.

Quoted 5 lines

Also, this relpoline magic is likely to start patching text at runtime on a semi-regular basis. This type of patching is *slow*. Is it a problem?

It didn’t appear so. Although there are >10000 indirect branches in the kernel, you don’t patch too many of them even you are doing relearning.

Quoted 7 lines

Quoted 6 lines

Quoted 3 lines

2. An indirect branch inside an interrupt or NMI handler might be the one we patch

But INT3s just use the existing stack, and NMIs support nesting, so I'm thinking that should also be doable. Andy?

Quoted 7 lines

In principle, as long as the code isn't NOKPROBE_SYMBOL-ified, we should be fine, right? I'd be a little nervous if we get an int3 in the C code that handles the early part of an NMI from user mode. It's *probably* okay, but one of the alarming issues is that the int3 return path will implicitly unmask NMI, which isn't fantastic. Maybe we finally need to dust off my old "return using RET" code to get rid of that problem.

So it may be possible. It would require having a new text_poke_bp() variant for multiple instructions. text_poke_bp() might be slower though.

To be clear, that wasn’t a NAK. It was merely a “this is alarming.”

Hey Josh - you could potentially do the same hack to generate the static call tables. Take that, objtool.

Quoted 75 lines · Nadav Amit

Quoted 74 lines · Andy Lutomirski

Quoted 61 lines · Josh Poimboeuf

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 43 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

         base            relpoline
         ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 3 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

Quoted 6 lines

Quoted 4 lines

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Callees can clobber flags, so it seems fine to me.

Just to check I understand your approach right: you made a macro called "call", and you're therefore causing all instances of "call" to become magic? This is... terrifying. It's even plausibly worse than "#define if" :) The scariest bit is that it will impact inline asm as well. Maybe a gcc plugin would be less alarming?

Quoted 3 lines

It is likely to look less alarming. When I looked at the inline retpoline implementation of gcc, it didn’t look much better than what I did - it basically just emits assembly instructions.

To be clear, that wasn’t a NAK. It was merely a “this is alarming.”

Quoted 79 lines · Andy Lutomirski

Quoted 75 lines · Nadav Amit

Quoted 74 lines · Andy Lutomirski

Quoted 61 lines · Josh Poimboeuf

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 43 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

         base            relpoline
         ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 3 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

Quoted 6 lines

Quoted 4 lines

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Callees can clobber flags, so it seems fine to me.

Just to check I understand your approach right: you made a macro called "call", and you're therefore causing all instances of "call" to become magic? This is... terrifying. It's even plausibly worse than "#define if" :) The scariest bit is that it will impact inline asm as well. Maybe a gcc plugin would be less alarming?

Quoted 5 lines

Quoted 3 lines

It is likely to look less alarming. When I looked at the inline retpoline implementation of gcc, it didn’t look much better than what I did - it basically just emits assembly instructions.

To be clear, that wasn’t a NAK. It was merely a “this is alarming.”

Although... how do you avoid matching on things that really don't want this treatment? paravirt ops come to mind.

Quoted 82 lines · Andy Lutomirski

Quoted 81 lines · Andy Lutomirski

Quoted 78 lines · Nadav Amit

Quoted 67 lines · Andy Lutomirski

Quoted 66 lines · Josh Poimboeuf

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 43 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

        base            relpoline
        ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 7 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Quoted 7 lines

Quoted 1 line

Callees can clobber flags, so it seems fine to me.

Just to check I understand your approach right: you made a macro called "call", and you're therefore causing all instances of "call" to become magic? This is... terrifying. It's even plausibly worse than "#define if" :) The scariest bit is that it will impact inline asm as well. Maybe a gcc plugin would be less alarming?

It is likely to look less alarming. When I looked at the inline retpoline implementation of gcc, it didn’t look much better than what I did - it basically just emits assembly instructions.

Quoted 4 lines

Quoted 1 line

To be clear, that wasn’t a NAK. It was merely a “this is alarming.”

Although... how do you avoid matching on things that really don't want this treatment? paravirt ops come to mind.

Paravirt ops don't use retpolines because they're patched into direct calls during boot. So Nadav's patches won't touch them.

Quoted 85 lines · Josh Poimboeuf

Quoted 82 lines · Andy Lutomirski

Quoted 81 lines · Andy Lutomirski

Quoted 78 lines · Nadav Amit

Quoted 67 lines · Andy Lutomirski

Quoted 66 lines · Josh Poimboeuf

Quoted 45 lines · Nadav Amit

Quoted 45 lines · Josh Poimboeuf

Quoted 43 lines · Nadav Amit

This RFC introduces indirect call promotion in runtime, which for the matter of simplification (and branding) will be called here "relpolines" (relative call + trampoline). Relpolines are mainly intended as a way of reducing retpoline overheads due to Spectre v2.

Unlike indirect call promotion through profile guided optimization, the proposed approach does not require a profiling stage, works well with modules whose address is unknown and can adapt to changing workloads.

The main idea is simple: for every indirect call, we inject a piece of code with fast- and slow-path calls. The fast path is used if the target matches the expected (hot) target. The slow-path uses a retpoline. During training, the slow-path is set to call a function that saves the call source and target in a hash-table and keep count for call frequency. The most common target is then patched into the hot path.

The patching is done on-the-fly by patching the conditional branch (opcode and offset) that is used to compare the target to the hot target. This allows to direct all cores to the fast-path, while patching the slow-path and vice-versa. Patching follows 2 more rules: (1) Only patch a single byte when the code might be executed by any core. (2) When patching more than one byte, ensure that all cores do not run the to-be-patched-code by preventing this code from being preempted, and using synchronize_sched() after patching the branch that jumps over this code.

Changing all the indirect calls to use relpolines is done using assembly macro magic. There are alternative solutions, but this one is relatively simple and transparent. There is also logic to retrain the software predictor, but the policy it uses may need to be refined.

Eventually the results are not bad (2 VCPU VM, throughput reported):

        base            relpoline
        ----            ---------
nginx      22898           25178 (+10%)
redis-ycsb 24523           25486 (+4%)
dbench     2144            2103 (+2%)

When retpolines are disabled, and if retraining is off, performance benefits are up to 2% (nginx), but are much less impressive.

Quoted 7 lines

Quoted 5 lines

Hi Nadav,

Peter pointed me to these patches during a discussion about retpoline profiling. Personally, I think this is brilliant. This could help networking and filesystem intensive workloads a lot.

Thanks! I was a bit held-back by the relatively limited number of responses.

It is a rather, erm, ambitious idea, maybe they were speechless :-)

Quoted 7 lines

I finished another version two weeks ago, and every day I think: "should it be RFCv2 or v1”, ending up not sending it…

There is one issue that I realized while working on the new version: I’m not sure it is well-defined what an outline retpoline is allowed to do. The indirect branch promotion code can change rflags, which might cause correction issues. In practice, using gcc, it is not a problem.

Quoted 7 lines

Quoted 1 line

Callees can clobber flags, so it seems fine to me.

Just to check I understand your approach right: you made a macro called "call", and you're therefore causing all instances of "call" to become magic? This is... terrifying. It's even plausibly worse than "#define if" :) The scariest bit is that it will impact inline asm as well. Maybe a gcc plugin would be less alarming?

It is likely to look less alarming. When I looked at the inline retpoline implementation of gcc, it didn’t look much better than what I did - it basically just emits assembly instructions.

Quoted 7 lines

Quoted 4 lines

Quoted 1 line

To be clear, that wasn’t a NAK. It was merely a “this is alarming.”

Although... how do you avoid matching on things that really don't want this treatment? paravirt ops come to mind.

Paravirt ops don't use retpolines because they're patched into direct calls during boot. So Nadav's patches won't touch them.

Actually, the way it’s handled is slightly more complicated - yes, the CALL macro should not be applied, as Josh said, but the question is how it is achieved.

The basic idea is that the CALL macro should only be applied to C source-files and not to assembly files and for macros.s, which holds the PV call macros. I will recheck it is done this way.