MIPS: Move signal return trampolines off the stack.

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

index 955c5f0..491e5be 100644

arch/mips/kernel/syscall.c +1 -1

@@ -77,7 +77,7 @@ unsigned long arch_get_unmapped_area(struct file *filp,
 unsigned long addr,
       int do_color_align;
       unsigned long task_size;
 
-       task_size = STACK_TOP;
+       task_size = test_thread_flag(TIF_32BIT_ADDR) ? TASK_SIZE32 :
 TASK_SIZE;
 

if (len > task_size)
return -ENOMEM;

Hello David:

On Tue, Apr 21, 2009 at 3:33 PM, David Daney <[email protected] <mailto:[email protected]>> wrote:

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

This patch fails to compile for me with an RM7035C-based system (out of tree, sadly). The error I see is:

CC arch/mips/kernel/syscall.o
arch/mips/kernel/syscall.c: In function 'arch_get_unmapped_area':
arch/mips/kernel/syscall.c:80: error: 'TASK_SIZE32' undeclared (first use in this function) arch/mips/kernel/syscall.c:80: error: (Each undeclared identifier is reported only once arch/mips/kernel/syscall.c:80: error: for each function it appears in.) make[1]: *** [arch/mips/kernel/syscall.o] Error 1

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

Signed-off-by David Daney <[email protected]>

Quoted 9 lines · David Daney

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

Signed-off-by David Daney <[email protected]>

Note that for FPU-less CPUs, the kernel FP emulator also uses a user stack trampoline to execute instructions in the delay slots of emulated FP branches. I didn't see any of the math-emu modules being tweaked in either part of your patch. Presumably, one would want to move that operation into the vdso as well. With the proposed patch, I'm not sure whether things would continue working normally as before, still using the user stack, or whether the dsemulret code depends on something that is changed by the patch, and will now implode. Probably the former, but paranoia is not a character defect in OS kernel work. I don't have a test case handy (nor a test system any more), but compiling something like whetstone or linpack in C with a high degree of optimization will *probably* generate FP branches with live delay slots.

Quoted 9 lines · Kevin D. Kissell

Quoted 8 lines · David Daney

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

Quoted 7 lines

Quoted 1 line

Signed-off-by David Daney <[email protected]>

Note that for FPU-less CPUs, the kernel FP emulator also uses a user stack trampoline to execute instructions in the delay slots of emulated FP branches. I didn't see any of the math-emu modules being tweaked in either part of your patch. Presumably, one would want to move that operation into the vdso as well.

[ ... ]
It is an ugly problem. I am trying to hack something up to fix it.

David Daney

Quoted 12 lines · On Wednesday 22 April 2009 20:01:44 David Daney wrote:

Quoted 10 lines · Kevin D. Kissell

Quoted 8 lines · David Daney

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

Quoted 8 lines

Quoted 8 lines

Quoted 2 lines

Signed-off-by David Daney <[email protected]>

Note that for FPU-less CPUs, the kernel FP emulator also uses a user stack trampoline to execute instructions in the delay slots of emulated FP branches. I didn't see any of the math-emu modules being tweaked in either part of your patch. Presumably, one would want to move that operation into the vdso as well.

Kevin,

As David says, this is a Very Ugly Problem. Each FP trampoline
is effectively per-(runtime-)instance per-thread, i.e., there is a unique FP trampoline for every dynamic instance of (non-trivial non-FP) instruction in an FP delay slot. This is essentially the complete opposite of the signal-return trampoline, which is fixed (constant text) for all instances in all threads.

As such, David's vdso (assuming it's similar to those on other
architectures (I've not looked at it closely yet)) may not have any obvious role to play in moving the FP trampoline('s code?) off the user's stack.

Quoted 32 lines · Brian Foster

Quoted 12 lines · On Wednesday 22 April 2009 20:01:44 David Daney wrote:

Quoted 10 lines · Kevin D. Kissell

Quoted 8 lines · David Daney

This is a preliminary patch to add a vdso to all user processes. Still missing are ELF headers and .eh_frame information. But it is enough to allow us to move signal trampolines off of the stack.

We allocate a single page (the vdso) and write all possible signal trampolines into it. The stack is moved down by one page and the vdso is mapped into this space.

Quoted 8 lines

Quoted 8 lines

Quoted 2 lines

Signed-off-by David Daney <[email protected]>

Note that for FPU-less CPUs, the kernel FP emulator also uses a user stack trampoline to execute instructions in the delay slots of emulated FP branches. I didn't see any of the math-emu modules being tweaked in either part of your patch. Presumably, one would want to move that operation into the vdso as well.

Kevin,

As David says, this is a Very Ugly Problem. Each FP trampoline
is effectively per-(runtime-)instance per-thread, i.e., there is a unique FP trampoline for every dynamic instance of (non-trivial non-FP) instruction in an FP delay slot. This is essentially the complete opposite of the signal-return trampoline, which is fixed (constant text) for all instances in all threads.

Quoted 5 lines

As such, David's vdso (assuming it's similar to those on other
architectures (I've not looked at it closely yet)) may not have any obvious role to play in moving the FP trampoline('s code?) off the user's stack.

I haven't reviewed David's code in detail, but from his description, I thought that there was a vdso page per task/thread. If there's only one per processor, then, yes, that poses a challenge to porting the FPU emulation code to use it, since, as you observe, the instruction sequence to be executed may differ for each delay slot emulation. It should still be possible, though. FP emulation is in itself expensive, and FP branches with live delay slots are a smallish subset of the overall FP instructions to be emulated, so a dynamic scheme to allocate/free slots in a vdso page wouldn't have that dramatic a performance impact, overall. As the instructions aren't constant, the I-caches would need to be flushed after each dsemul setup, even using a vdso page, but that shouldn't break the fact that one could avoid it for signals, so long as a different cache line within the vdso page is used for signal versus dsemul trampolines.

Quoted 13 lines · Kevin D. Kissell

Quoted 11 lines · Brian Foster

Quoted 7 lines · On Wednesday 22 April 2009 20:01:44 David Daney wrote:

Quoted 6 lines · Kevin D. Kissell

Quoted 2 lines · David Daney

This is a preliminary patch to add a vdso to all user processes. [ ... ]

Note that for FPU-less CPUs, the kernel FP emulator also uses a user stack trampoline to execute instructions in the delay slots of emulated FP branches. [ ... ]

As David says, this is a Very Ugly Problem. Each FP trampoline
is effectively per-(runtime-)instance per-thread [ ... ]

Quoted 6 lines

I haven't reviewed David's code in detail, but from his description, I thought that there was a vdso page per task/thread. If there's only one per processor, then, yes, that poses a challenge to porting the FPU emulation code to use it, since, as you observe, the instruction sequence to be executed may differ for each delay slot emulation. It should still be possible, though. [ ... ]

Kevin is right, this is ugly.

My current plan is to map an anonymous page with execute permission for each vma (process) and place all FP trampolines there. Each thread that needs a trampoline will allocate a piece of this page and write the trampoline. We can arrange it so that the only way a thread can exit the trampoline is by taking some sort of fault (currently this is true for the normal case), or exiting.

Then we free the trampoline for other
threads to use. If all the slots in the trampoline page are in use, a thread would block until there is a free one, rarely, if ever would this happen.
[ ... ]

Quoted 27 lines · On Friday 24 April 2009 17:30:35 David Daney wrote:

Quoted 18 lines · Kevin D. Kissell

Quoted 9 lines · Brian Foster

Quoted 7 lines · On Wednesday 22 April 2009 20:01:44 David Daney wrote:

Quoted 5 lines · Kevin D. Kissell

Quoted 3 lines · David Daney

This is a preliminary patch to add a vdso to all user processes. [ ... ]

Quoted 7 lines

Quoted 4 lines

Quoted 4 lines

Note that for FPU-less CPUs, the kernel FP emulator also uses a user stack trampoline to execute instructions in the delay slots of emulated FP branches. [ ... ]

As David says, this is a Very Ugly Problem. Each FP trampoline
is effectively per-(runtime-)instance per-thread [ ... ]

Quoted 7 lines

I haven't reviewed David's code in detail, but from his description, I thought that there was a vdso page per task/thread. If there's only one per processor, then, yes, that poses a challenge to porting the FPU emulation code to use it, since, as you observe, the instruction sequence to be executed may differ for each delay slot emulation. It should still be possible, though. [ ... ]

Quoted 9 lines

Kevin is right, this is ugly.

My current plan is to map an anonymous page with execute permission for each vma (process) and place all FP trampolines there. Each thread that needs a trampoline will allocate a piece of this page and write the trampoline. We can arrange it so that the only way a thread can exit the trampoline is by taking some sort of fault (currently this is true for the normal case), or exiting.

David,

The above is the bit which has always stumped me.
Having a per-process(or similar) page for the FP trampoline(s) is the “obvious” approach, but what has had me going around in circles is how to know when an allocated slot/trampoline can be freed. As you imply, in the normal case, it seems trivial. It's the not-normal cases which aren't clear (or at least aren't clear to me!).

You say (EMPHASIS added) “We can arrange it so
that the ONLY way a thread can exit the trampoline is by taking some sort of fault ... or exiting”, which if true, could solve the issue. Could you elucidate on this point, please?

Well, he's *almost* right about that. The delay slot emulation function executes a single instruction off the user stack/vdso slot, which is followed in memory by an instruction that provokes an address exception. The address exception handler detects the special case (and it should be noted that detecting the special case could be made simpler and more reliable if a vdso-type region were used),

cleans up, and restores normal stack behavior. That "clean up" could, of course, include any necessary vdso slot management. But what about cases that won't get to the magic alignment trap?

As the instruction being executed is extracted from a branch delay slot, we know it's not legal for it to be any sort of branch or jump instruction.

But it *could* be a trap or system call instruction, or a
load/store that would provoke a TLB exception. In the usual cases, however, as I believe David was alluding, either the exception will ultimately unwind to return to execute the magic alignment trap, or the thread will exit, and could free the emulation slot as part of general cleanup.

But there's a case that isn't handled in this model, and that's the case of an exception (or interrupt that falls in the 2-instruction window) resulting in a signal that is caught and dispatched, and where either the signal handler does a longjmp and restarts FP computation, or where the signal handler itself contains a FP branch with yet another delay slot to be emulated. One *could* get alarm signal before the original delay slot instruction is executed, so recycling the same vdso cache line would be premature. It's hard to get away from something distinctly stack-like if one wants to cover these cases.

My short-term suggestion would be to leave FP emulator delay slot handling on the (executable) user stack, even if signal trampolines use the vdso.

Longer term, we might consider what sorts of crockery would be necessary to deal with delay slot abandonment and recursion. That might mean adding cruft to the signal dispatch logic to detect that we're in mid-delay-slot-emulation and defer the signal until after the alignment trap cleanup is done (adds annoying run-time overhead, but is probably the smallest increase in footprint and complexity), or it might mean changing the delay slot emulation paradigm completely and bolting a full instruction set emulator into the FP emulator, so that the delay slot instruction is simulated in kernel mode, rather than requiring execution in user mode. I rejected that idea out-of-hand when I first did the FP emulator integration with the kernel, years ago, but maybe the constraints have changed...

Quoted 6 lines · Kevin D. Kissell

But it *could* be a trap or system call instruction, or a load/store
that would provoke a TLB exception. In the usual cases, however, as I believe David was alluding, either the exception will ultimately unwind to return to execute the magic alignment trap, or the thread will exit, and could free the emulation slot as part of general cleanup.

Quoted 11 lines

But there's a case that isn't handled in this model, and that's the case of an exception (or interrupt that falls in the 2-instruction window) resulting in a signal that is caught and dispatched, and where either the signal handler does a longjmp and restarts FP computation, or where the signal handler itself contains a FP branch with yet another delay slot to be emulated. One *could* get alarm signal before the original delay slot instruction is executed, so recycling the same vdso cache line would be premature. It's hard to get away from something distinctly stack-like if one wants to cover these cases.

System calls we don't have to handle, they will eventually return to the break instruction following the delay slot instruction and be handled by the normal processing.

I am thinking that all other exceptions will result in one of three cases:

1) They will work like system calls and return to the 'break'.

2) The thread will exit.

3) They result in a signal being sent to the thread. We can handle it in force_signal(). In this case we would adjust the eip to point at the original location of the instruction and clean things up. If the signal handler tries to restart the instruction, the FP emulator will re-run the emulation.

Quoted 29 lines · David Daney

Quoted 6 lines · Kevin D. Kissell

But it *could* be a trap or system call instruction, or a load/store
that would provoke a TLB exception. In the usual cases, however, as I believe David was alluding, either the exception will ultimately unwind to return to execute the magic alignment trap, or the thread will exit, and could free the emulation slot as part of general cleanup.

Quoted 11 lines

But there's a case that isn't handled in this model, and that's the case of an exception (or interrupt that falls in the 2-instruction window) resulting in a signal that is caught and dispatched, and where either the signal handler does a longjmp and restarts FP computation, or where the signal handler itself contains a FP branch with yet another delay slot to be emulated. One *could* get alarm signal before the original delay slot instruction is executed, so recycling the same vdso cache line would be premature. It's hard to get away from something distinctly stack-like if one wants to cover these cases.

System calls we don't have to handle, they will eventually return to the break instruction following the delay slot instruction and be handled by the normal processing.

I am thinking that all other exceptions will result in one of three cases:

1) They will work like system calls and return to the 'break'.

Quoted 7 lines

2) The thread will exit.

3) They result in a signal being sent to the thread. We can handle it in force_signal(). In this case we would adjust the eip to point at the original location of the instruction and clean things up. If the signal handler tries to restart the instruction, the FP emulator will re-run the emulation.

That's presumably OK if we *know* that the delay slot instruction has *not* executed prior to the signal being taken. But if it has, it may have had side-effects, i.e. imagine if it's an "ADD.S f4, f4, f6". We can't re-run the emulation without generating erroneous processor state. What do we do if, between the ADD.S and the

BREAK-that-replaces-my-old-alignment-trap, a timer interrupt comes in,
causing a SIGALRM which is caught and which executes another FP branch? When I first wrote the delay slot handling code, I dreamed of disabling interrupts during the delay slot instruction emulation - I think I even
coded it that way at one point - but it's fundamentally uncool to go off
into user mode with interrupts off.

I really think that once the delay slot emulation machinery has been put
into motion, that fact needs to become a part of the thread state. Currently, it's encoded, in a sense, in the stack pointer and the stack contents. If we no longer stack it, and use a more static instruction
buffer as a trampoline, then I think it needs to be tagged as part of
the kernel's thread state.

That knowledge might be used in various ways. I still think it would work to check that state and cause any signals to that thread need to be deferred until it has processed the BREAK instruction to restore the pre-emulation instruction flow. Once the state has been restored from the dsemul record, the signal can be dispatched rather than returning directly to the branch target. I don't like putting another check into the context restore code, though.

A cruftier, but less inefficient-in-the-expected-case approach would be a variant on what you suggest above. Signal dispatch could check the EPC, and *if* EPC shows that the delay slot exception hasn't yet executed, it could roll back the EPC to re-execute the FP branch after the signal. If the delay slot instruction *has* executed, but not the following BREAK, the signal dispatch code could preemptively do the dsemulret cleanup and restore the pre-emulation stack and post-emulation EPC before doing the signal dispatch.

Regards,

Kevin K.

This is a preliminary patch to add a vdso to all user processes.

arch/mips/kernel/vdso.c new file +0 -0

new file mode 100644
index 0000000..a1f38a6

arch/mips/kernel/vdso.c new file +18 -0

+int arch_setup_additional_pages(struct linux_binprm *bprm, int uses_interp)
+{
+	int ret;
+	unsigned long addr;
+	struct mm_struct *mm = current->mm;
+
+	down_write(&mm->mmap_sem);
+
+	addr = vdso_addr(mm->start_stack);
+
+	addr = get_unmapped_area(NULL, addr, PAGE_SIZE, 0, 0);
+	if (IS_ERR_VALUE(addr)) {
+		ret = addr;
+		goto up_fail;
+	}
+
+	ret = install_special_mapping(mm, addr, PAGE_SIZE,
+				      VM_READ|VM_EXEC|

arch/mips/kernel/vdso.c new file +3 -0

+	up_write(&mm->mmap_sem);
+	return ret;
+}

Quoted 1 line · David Daney

This is a preliminary patch to add a vdso to all user processes.

...

Quoted 3 lines

arch/mips/kernel/vdso.c new file +0 -0

new file mode 100644
index 0000000..a1f38a6

...

arch/mips/kernel/vdso.c line 35

Quoted 5 lines

arch/mips/kernel/vdso.c new file +5 -0

+static void __init install_trampoline(u32 *tramp, unsigned int sigreturn)
+{
+	tramp[0] = 0x24020000 + sigreturn;	/* li v0, sigreturn */
+	tramp[1] = 0x0000000c;			/* syscall */
+}

We can do away with magic constants by building on asm/inst.h:

static void __init install_trampoline(union mips_instruction *tramp,
short sigreturn)

{
	static struct i_format li_sigreturn = {	/* li, v0, sigreturn */
		.opcode = addiu_op,
		.rs = 0,			/* zero */
		.rt = 2,			/* v0 */
	};
	static struct r_format syscall = {		/* syscall */
		.opcode = spec_op,
		.func = syscall_op
	};
	tramp[0].i_format = li_sigreturn;
	tramp[0].i_format.simmediate = sigreturn;
	tramp[1].r_format = syscall;
}

Admittedly, this isn't really a proper use of the r_format structure. The right way is to add another structure to asm/inst.h and use that:

Quoted 19 lines

arch/mips/kernel/vdso.c new file +18 -0

+int arch_setup_additional_pages(struct linux_binprm *bprm, int uses_interp)
+{
+	int ret;
+	unsigned long addr;
+	struct mm_struct *mm = current->mm;
+
+	down_write(&mm->mmap_sem);
+
+	addr = vdso_addr(mm->start_stack);
+
+	addr = get_unmapped_area(NULL, addr, PAGE_SIZE, 0, 0);
+	if (IS_ERR_VALUE(addr)) {
+		ret = addr;
+		goto up_fail;
+	}
+
+	ret = install_special_mapping(mm, addr, PAGE_SIZE,
+				      VM_READ|VM_EXEC|

arch/mips/kernel/vdso.c line 101

Quoted 10 lines

arch/mips/kernel/vdso.c new file +10 -0

+				      VM_MAYREAD|VM_MAYWRITE|VM_MAYEXEC|
+				      VM_ALWAYSDUMP,
+				      &vdso_page);
+
+	if (ret)
+		goto up_fail;
+
+	mm->context.vdso = (void *)addr;
+
+up_fail:

It seems that this is an unexpected condition that probably indicates a failure of the expected state of the process at this point. Perhaps a pr_err() or pr_warning() would be appropriate?

arch/mips/kernel/vdso.c line 104

Quoted 3 lines

arch/mips/kernel/vdso.c new file +3 -0

+	up_write(&mm->mmap_sem);
+	return ret;
+}

Quoted 33 lines

Quoted 18 lines

arch/mips/kernel/vdso.c new file +18 -0

+int arch_setup_additional_pages(struct linux_binprm *bprm, int uses_interp)
+{
+	int ret;
+	unsigned long addr;
+	struct mm_struct *mm = current->mm;
+
+	down_write(&mm->mmap_sem);
+
+	addr = vdso_addr(mm->start_stack);
+
+	addr = get_unmapped_area(NULL, addr, PAGE_SIZE, 0, 0);
+	if (IS_ERR_VALUE(addr)) {
+		ret = addr;
+		goto up_fail;
+	}
+
+	ret = install_special_mapping(mm, addr, PAGE_SIZE,
+				      VM_READ|VM_EXEC|

arch/mips/kernel/vdso.c line 101

Quoted 10 lines

arch/mips/kernel/vdso.c new file +10 -0

+				      VM_MAYREAD|VM_MAYWRITE|VM_MAYEXEC|
+				      VM_ALWAYSDUMP,
+				      &vdso_page);
+
+	if (ret)
+		goto up_fail;
+
+	mm->context.vdso = (void *)addr;
+
+up_fail:

It seems that this is an unexpected condition that probably indicates a failure of the expected state of the process at this point. Perhaps a pr_err() or pr_warning() would be appropriate?

Quoted 3 lines

arch/mips/kernel/vdso.c line 104

Quoted 3 lines

arch/mips/kernel/vdso.c new file +3 -0

+	up_write(&mm->mmap_sem);
+	return ret;
+}

Really it should always succeed. Something is seriously wrong if you cannot map that page and we should probably panic().

David Daney

This is a follow on to the vdso patch.

Since all processes now have signal trampolines permanently mapped, we can use those instead of putting the trampoline on the stack and invalidating the corresponding icache across all CPUs. We also get rid of a bunch of ICACHE_REFILLS_WORKAROUND_WAR code.

Signed-off-by David Daney <[email protected]>

This patch set (against 2.6.29.1) creates a vdso and moves the signal trampolines to it from their previous home on the stack.

Tested with a 64-bit kernel on a Cavium Octeon cn3860 where I have the following results from lmbench2:

Before:
n64 - Signal handler overhead: 14.517 microseconds n32 - Signal handler overhead: 14.497 microseconds o32 - Signal handler overhead: 16.637 microseconds

After:

n64 - Signal handler overhead: 7.935 microseconds
n32 - Signal handler overhead: 7.334 microseconds
o32 - Signal handler overhead: 8.628 microseconds

Comments encourged.

Quoted 11 lines · David Daney

This patch set (against 2.6.29.1) creates a vdso and moves the signal trampolines to it from their previous home on the stack.

Tested with a 64-bit kernel on a Cavium Octeon cn3860 where I have the following results from lmbench2:

Before:
n64 - Signal handler overhead: 14.517 microseconds n32 - Signal handler overhead: 14.497 microseconds o32 - Signal handler overhead: 16.637 microseconds

Quoted 5 lines

After:

n64 - Signal handler overhead: 7.935 microseconds
n32 - Signal handler overhead: 7.334 microseconds
o32 - Signal handler overhead: 8.628 microseconds

Nice numbers, and something that will be even more critical as real-time features are added and used!

Quoted 1 line

Comments encourged.

Only one comment, which I would not want to hold up acceptance:
based on some numbers sent out recently, it looks like the kernel is experiencing some performance issues with exec() and I think this change will make it slightly slower. You could avoid this by deferring installation of the trampoline to the first use of a system call that registers a signal handler.

David VomLehn wrote:

Quoted 6 lines

Only one comment, which I would not want to hold up acceptance:
based on some numbers sent out recently, it looks like the kernel is experiencing some performance issues with exec() and I think this change will make it slightly slower. You could avoid this by deferring installation of the trampoline to the first use of a system call that registers a signal handler.

I should try to measure this too. Although this is what x86 et al. do. It is by far much simpler and less prone to bugs that trying to hook into the system calls. After an executable has had the chance to start additional threads and establish arbitrary mappings things get complicated.

David Daney