Skip to contentSkip to conversation

i386 dynamic fixup/self modifying code

PATCH In review Luca Barbieri 6 participants 17 messages Aug 28, 2002 – Sep 3, 2002

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 i386 dynamic fixup/self modifying code

This patch implements a system that modifies the kernel code at runtime depending on CPU features and SMPness.

In fact, I'm not really sure whether it's a good idea to do something like this. When I started implementing this it seemed to be possible to have a much simpler and cleaner implementation but unfortunately this isn't the case especially due to the need of SMP correctness.

This patch requires the is_smp() patch I posted earlier and also requires the new CPU selection code and the code that actually uses both.
This code already exists, but needs a few adjustments so it may not arrive immediately.

The code is invoked in the following ways:
* Undefined exception handler: this is used to replace unsupported instructions with supported ones. Used for invlpg -> flushall, prefetchnta -> prefetch -> nop, *fence -> lock addl 0, (%esp), movntq -> movq
* Int3 handler: this is used when a 1 byte opcode is desired. This is controlled by a config option so that debuggers and kprobe won't break. Used for lock/nop and APIC write
* Int 0xfa handler: this is a dynamic fixup specific vector used to implement everything else. Used for: spin unlock, io fence, sfence, APIC write (if int3 not available).

Note that the int3 and int 0xfa handler are actually invoked by the code to be modified, so the handlers replace calls to themselves. For example for APIC writes we have <int3> 0x40 mem32 -> <xchgl/movl> <%eax,> mem32.

No fixups are performed until SMP boot is completed. Instructions are instead emulated in the interrupt/exception handlers.

Unfortunately with this patch executing invalid code will cause the processor to enter an infinite exception loop rather than panic. Fixing this is not trivial for SMP+preempt so it's not done at the moment.

This code needs special care for SMP safety. Here is a copy of the comment explaining this:
/* If we are running on SMP any other processor might be executing the
code that we are modifying. We must make sure that the other processor will either fault or will execute the complete replacement instruction.

This is accomplished by using instructions that fault only depending on up to 4 bytes. When fixing up something we first write bytes after the first 4 and we then use a locked write to set the first 4.

We depend on the processor execute unit to never see our locked write before it sees the other modifications.

According to page 7-5 of the Intel Pentium 4 System Programming Manual, this is safe on 486 and Pentium <= 4.

For other processors this may be unsafe. If this is the case, on such processors IPIs must be sent to all other processors to block them before the fixup is performed. dynamic_fixup_smp_(un)lock are reserved for this purpose.
*/
Comments on whether this would work on Athlon MPs are appreciated. If it wouldn't an implementation of the send-IPIs-to-everyone code would also be appreciated.

BTW, credit for the original idea goes to Linus.

arch/i386/kernel/entry.S +47 -0
diff --exclude-from=/home/ldb/src/linux-exclude -urNdp linux-2.5.32/arch/i386/kernel/entry.S linux-2.5.32_fixup/arch/i386/kernel/entry.S
@@ -445,6 +445,13 @@ ENTRY(nmi)
 	RESTORE_ALL
 
 ENTRY(int3)
+#ifdef CONFIG_X86_DYNAMIC_FIXUP_INT3
+	testl $(VM_MASK), 8(%esp)
+	jnz 1f
+	testl $0x3, 4(%esp)
+	jz dynamic_fixup_entry_int3
+1:	
+#endif
 	pushl $0
 	pushl $do_int3
 	jmp error_code
@@ -507,6 +514,46 @@ ENTRY(spurious_interrupt_bug)
 	pushl $do_spurious_interrupt_bug
 	jmp error_code
 
+ENTRY(dynamic_fixup_entry_int)
+	pushl %eax
+	pushl %edx
+	pushl %ecx
+	call dynamic_fixup_x86_int
+	popl %ecx
+	popl %edx
+	popl %eax
+	iret	
+
+#ifdef CONFIG_X86_DYNAMIC_FIXUP_INT3
+ENTRY(dynamic_fixup_entry_int3)
+	pushl %eax
+	pushl %edx
+	pushl %ecx
+	call dynamic_fixup_x86_int3
+	popl %ecx
+	popl %edx
+	popl %eax
+	iret	
+#endif
+
+ENTRY(flush_tlb)
+	pushl %eax
+	movl %cr3, %eax
+	movl %eax, %cr3
+	popl %eax
+	ret
+
+ENTRY(emulate_rdtsc)
+	pushl %ecx
+	call do_gettimeofday64
+	movl %eax, %ecx
+	movl $1000000, %eax
+	mull %edx
+	addl %ecx, %eax
+	adcl $0, %edx
+	popl %ecx
+	ret
+	
 .data
 ENTRY(sys_call_table)
 	.long sys_ni_syscall	/* 0 - old "setup()" system call*/
arch/i386/kernel/fixup.c +510 -0

510 lines not on this page · raw message

arch/i386/kernel/head.S +20 -1
diff --exclude-from=/home/ldb/src/linux-exclude -urNdp linux-2.5.32/arch/i386/kernel/head.S linux-2.5.32_fixup/arch/i386/kernel/head.S
@@ -15,7 +15,9 @@
 #include <asm/page.h>
 #include <asm/pgtable.h>
 #include <asm/desc.h>
-
+#include <asm/irq_vectors.h>
+#include <asm/fixup.h>
+		
 #define OLD_CL_MAGIC_ADDR	0x90020
 #define OLD_CL_MAGIC		0xA33F
 #define OLD_CL_BASE_ADDR	0x90000
@@ -302,6 +304,23 @@ rp_sidt:
 	addl $8,%edi
 	dec %ecx
 	jne rp_sidt
+
+/* Setup dynamic fixup vectors */
+#ifdef CONFIG_X86_DYNAMIC_FIXUP_INT3
+	movl $(__KERNEL_CS << 16), %eax
+	movl $dynamic_fixup_entry_int3, %edx
+	movw %dx, %ax
+	movw $0x8f00, %dx
+	movl %eax, (idt_table + 3 * 8)
+	movl %edx, (idt_table + 3 * 8 + 4)
+#endif
+
+	movl $dynamic_fixup_entry_int, %edx
+	movw %dx, %ax
+	movw $0x8f00, %dx
+	movl %eax, (idt_table + DYNAMIC_FIXUP_VECTOR * 8)
+	movl %edx, (idt_table + DYNAMIC_FIXUP_VECTOR * 8 + 4)
+				
 	ret
 
 ENTRY(stack_start)
arch/i386/kernel/i8259.c +1 -1
diff --exclude-from=/home/ldb/src/linux-exclude -urNdp linux-2.5.32/arch/i386/kernel/i8259.c linux-2.5.32_fixup/arch/i386/kernel/i8259.c
@@ -385,7 +385,7 @@ void __init init_IRQ(void)
 	 */
 	for (i = 0; i < NR_IRQS; i++) {
 		int vector = FIRST_EXTERNAL_VECTOR + i;
-		if (vector != SYSCALL_VECTOR) 
+		if ((vector != SYSCALL_VECTOR) && (vector != DYNAMIC_FIXUP_VECTOR))
 			set_intr_gate(vector, interrupt[i]);
 	}
 
arch/i386/kernel/Makefile +1 -1
diff --exclude-from=/home/ldb/src/linux-exclude -urNdp linux-2.5.32/arch/i386/kernel/Makefile linux-2.5.32_fixup/arch/i386/kernel/Makefile
@@ -11,7 +11,7 @@ export-objs     := mca.o msr.o i386_ksym
 obj-y	:= process.o semaphore.o signal.o entry.o traps.o irq.o vm86.o \
 		ptrace.o i8259.o ioport.o ldt.o setup.o time.o sys_i386.o \
 		pci-dma.o i386_ksyms.o i387.o bluesmoke.o dmi_scan.o \
-		bootflag.o
+		bootflag.o fixup.o
 
 obj-y				+= cpu/
 obj-$(CONFIG_MCA)		+= mca.o
arch/i386/kernel/time.c +44 -22

109 lines not on this page · raw message

arch/i386/kernel/traps.c +36 -20

74 lines not on this page · raw message

include/asm-i386/fixup.h +41 -0

41 lines not on this page · raw message

include/asm-i386/irq_vectors.h +2 -0
diff --exclude-from=/home/ldb/src/linux-exclude -urNdp linux-2.5.32/include/asm-i386/irq_vectors.h linux-2.5.32_fixup/include/asm-i386/irq_vectors.h
@@ -28,6 +28,8 @@
 #define RESCHEDULE_VECTOR	0xfc
 #define CALL_FUNCTION_VECTOR	0xfb
 
+#define DYNAMIC_FIXUP_VECTOR	0xfa
+
 #define THERMAL_APIC_VECTOR	0xf0
 /*
  * Local APIC timer IRQ vector is on a different priority level,
init/main.c +7 -0
diff --exclude-from=/home/ldb/src/linux-exclude -urNdp linux-2.5.32/init/main.c linux-2.5.32_fixup/init/main.c
@@ -539,6 +539,13 @@ static void do_pre_smp_initcalls(void)
 	migration_init();
 #endif
 	spawn_ksoftirqd();
+
+#ifdef __i386__
+	{
+		extern void dynamic_fixup_start(void);
+		dynamic_fixup_start();
+	}
+#endif	
 }
 
 extern void prepare_namespace(void);
#1 lore raw
Quoted 13 lines · Luca Barbieri

This patch implements a system that modifies the kernel code at runtime depending on CPU features and SMPness.
...
/* If we are running on SMP any other processor might be executing the
code that we are modifying. We must make sure that the other processor will either fault or will execute the complete replacement instruction.

This is accomplished by using instructions that fault only depending on up to 4 bytes. When fixing up something we first write bytes after the first 4 and we then use a locked write to set the first 4.

Quoted 5 lines

We depend on the processor execute unit to never see our locked write before it sees the other modifications.

According to page 7-5 of the Intel Pentium 4 System Programming Manual, this is safe on 486 and Pentium <= 4.

I've tried this sort of thing before (unsynchronised cross-modifying code), but I had to abandon it due to Pentium III Erratum E49 and similar errata for all Intel P6 CPUs. Have you verified that you're not hitting this erratum?

/Mikael

#2 lore raw
Quoted 3 lines

I've tried this sort of thing before (unsynchronised cross-modifying code), but I had to abandon it due to Pentium III Erratum E49 and similar errata for all Intel P6 CPUs. Have you verified that you're not hitting this erratum?

It is indeed completely hitting it.
However, we can work around this by simply stopping all other CPUs in interrupt context with an IPI (while this may sound horrible, it shouldn't significantly impact performance unless the response time is excessively long).

I'll write some code to this. However I don't have the hardware to test it, so it might require multiple iterations to get it right.

As for the "all Intel P6 CPUs" are really _all_ Intel P6 CPU broken? Do you know of any other CPU that would need the workaround?

#3 lore raw
Quoted 8 lines · Luca Barbieri
Quoted 3 lines

I've tried this sort of thing before (unsynchronised cross-modifying code), but I had to abandon it due to Pentium III Erratum E49 and similar errata for all Intel P6 CPUs. Have you verified that you're not hitting this erratum?

It is indeed completely hitting it.
However, we can work around this by simply stopping all other CPUs in interrupt context with an IPI (while this may sound horrible, it shouldn't significantly impact performance unless the response time is excessively long).

That was my thought too. IPI to bring the others to a barrier, do the modification, release the barrier.

In my case (patching CALL instructions to call the correct targets after HW detection) I was fortunately able to fix up the code before it was seen by other CPUs, but this relied on the fact that I knew the locations of all CALL sites needing fix up.

Quoted 4 lines

I'll write some code to this. However I don't have the hardware to test it, so it might require multiple iterations to get it right.

As for the "all Intel P6 CPUs" are really _all_ Intel P6 CPU broken?

Yes, last time I checked the erratum existed for all members of Intel's P6 family.

Quoted 1 line

Do you know of any other CPU that would need the workaround?

No. The P5 is ok, and I believe the P4 is also. The K7s didn't have this listed as an erratum last time I checked.

/Mikael

#4 lore raw
In reply to Luca Barbieri

Hi!

Quoted 2 lines

This patch implements a system that modifies the kernel code at runtime depending on CPU features and SMPness.

Nice!

Quoted 6 lines

This patch requires the is_smp() patch I posted earlier and also requires the new CPU selection code and the code that actually uses both.
This code already exists, but needs a few adjustments so it may not arrive immediately.

Quoted 8 lines

The code is invoked in the following ways:
* Undefined exception handler: this is used to replace unsupported instructions with supported ones. Used for invlpg -> flushall, prefetchnta -> prefetch -> nop, *fence -> lock addl 0, (%esp), movntq -> movq
* Int3 handler: this is used when a 1 byte opcode is desired. This is controlled by a config option so that debuggers and kprobe won't break. Used for lock/nop and APIC write

Why not do *everything* using int3 handler? It should simplify your code.

Hooking on 'unknown instruction' should not be really neccessary if you replace all invlpgs (etc) with 0xcc...
Pavel

Quoted 3 lines

Unfortunately with this patch executing invalid code will cause the processor to enter an infinite exception loop rather than panic. Fixing this is not trivial for SMP+preempt so it's not done at the moment.

Using 0xcc for everything should fix that, right?

Signature · 2 lines
Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt,
details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.
#5 lore raw
Quoted 19 lines
Quoted 2 lines

This patch implements a system that modifies the kernel code at runtime depending on CPU features and SMPness.

Nice!

Quoted 6 lines

This patch requires the is_smp() patch I posted earlier and also requires the new CPU selection code and the code that actually uses both.
This code already exists, but needs a few adjustments so it may not arrive immediately.

Quoted 8 lines

The code is invoked in the following ways:
* Undefined exception handler: this is used to replace unsupported instructions with supported ones. Used for invlpg -> flushall, prefetchnta -> prefetch -> nop, *fence -> lock addl 0, (%esp), movntq -> movq
* Int3 handler: this is used when a 1 byte opcode is desired. This is controlled by a config option so that debuggers and kprobe won't break. Used for lock/nop and APIC write

Quoted 1 line

Why not do *everything* using int3 handler? It should simplify your code.

Because kdb, kgdb and kprobe want to use int3 so it must be used only if the config option is enabled.

Quoted 2 lines

Hooking on 'unknown instruction' should not be really neccessary if you replace all invlpgs (etc) with 0xcc...

It's better: first, if it is supported we have no faults. Second, in some cases (e.g. movntq) it's not possible without adding extra padding when using int xx (and int3 can't be used for the reason above).

Quoted 5 lines
Quoted 3 lines

Unfortunately with this patch executing invalid code will cause the processor to enter an infinite exception loop rather than panic. Fixing this is not trivial for SMP+preempt so it's not done at the moment.

Using 0xcc for everything should fix that, right?

Not possible. See above.

This could be fixed by checking whether the opcode is not one generated or recognized by the dynamic fixup code, assuming that nothing else can change the code.
However, this fails to detect "impossible" cases like cpus that should understand prefetches but that don't.

#6 lore raw
In reply to Pavel Machek
Quoted 5 lines · Pavel Machek
Quoted 3 lines

Unfortunately with this patch executing invalid code will cause the processor to enter an infinite exception loop rather than panic. Fixing this is not trivial for SMP+preempt so it's not done at the moment.

Using 0xcc for everything should fix that, right?

Except you can't do the fixup on SMP without risking hitting the CPU errata. You also break debugging tools that map kernel code pages r/o and people who ROM it.

The latter aren't a big problem (they can compile without runtime fixups). For the other fixups though you -have- to do them before you run the code. That isnt hard (eg sparc btfixup). You generate a list of the addresses in a segment, patch them all and let the init freeup blow the table away

#7 lore raw

Hi!

Quoted 10 lines
Quoted 5 lines
Quoted 3 lines

Unfortunately with this patch executing invalid code will cause the processor to enter an infinite exception loop rather than panic. Fixing this is not trivial for SMP+preempt so it's not done at the moment.

Using 0xcc for everything should fix that, right?

Except you can't do the fixup on SMP without risking hitting the CPU errata. You also break debugging tools that map kernel code pages r/o and people who ROM it.

Quoted 5 lines

The latter aren't a big problem (they can compile without runtime fixups). For the other fixups though you -have- to do them before you run the code. That isnt hard (eg sparc btfixup). You generate a list of the addresses in a segment, patch them all and let the init freeup blow the table away

Aha, making a list and just patching early at boot is even simpler than method I was thinking about.... Why not do it that way?
Pavel

Signature · 2 lines
Casualities in World Trade Center: ~3k dead inside the building,
cryptography in U.S.A. and free speech in Czech Republic.
#8 lore raw

From: Pavel Machek <[email protected]>
Date: Fri, 30 Aug 2002 01:22:33 +0200

Aha, making a list and just patching early at boot is even simpler than method I was thinking about.... Why not do it that way?

Even more cleverly you could use subsections, and thus:

1) __init free the patch code blocks at the end of boot
2) patch them more simply, the .subsection entries would be "kern_addr, insn" __u32 pairs on x86 for example.

#9 lore raw
Quoted 2 lines

2) patch them more simply, the .subsection entries would be "kern_addr, insn" __u32 pairs on x86 for example.

This can be made a single u32 by using the MSB for the insn and doing this with additions so that it works with relocations.
It might not be possible for modules, though.

#10 lore raw
In reply to Alan Cox
Quoted 9 lines · Alan Cox
Quoted 5 lines · Pavel Machek
Quoted 3 lines

Unfortunately with this patch executing invalid code will cause the processor to enter an infinite exception loop rather than panic. Fixing this is not trivial for SMP+preempt so it's not done at the moment.

Using 0xcc for everything should fix that, right?

Except you can't do the fixup on SMP without risking hitting the CPU errata.

Worked around by making sure all other processors are stopped (iret is serializing) sending IPIs if they are not already spinning on the fixup lock. See patch #2.

Quoted 5 lines

You also break debugging tools that map kernel code pages r/o and people who ROM it.

The latter aren't a big problem (they can compile without runtime fixups).

OK, I'll add a config option for this.

Quoted 4 lines

For the other fixups though you -have- to do them before you run the code. That isnt hard (eg sparc btfixup). You generate a list of the addresses in a segment, patch them all and let the init freeup blow the table away

Is doing them at runtime with the aforementioned workaround fine?

#11 lore raw
Quoted 3 lines · Luca Barbieri

Worked around by making sure all other processors are stopped (iret is serializing) sending IPIs if they are not already spinning on the fixup lock. See patch #2.

what happens we you do a fixup and the fixup occurs in an IPI handler (eg a cross CPU tlb flush).

Quoted 5 lines
Quoted 4 lines

For the other fixups though you -have- to do them before you run the code. That isnt hard (eg sparc btfixup). You generate a list of the addresses in a segment, patch them all and let the init freeup blow the table away

Is doing them at runtime with the aforementioned workaround fine?

Is doing them all in the beginning not somewhat saner and more debuggable. The only reason to do it at runtime is hotplugging a less capable CPU. I have a suggestion for that case which is that we don't bother about it 8)

#12 lore raw
Quoted 7 lines · Alan Cox
Quoted 3 lines · Luca Barbieri

Worked around by making sure all other processors are stopped (iret is serializing) sending IPIs if they are not already spinning on the fixup lock. See patch #2.

what happens we you do a fixup and the fixup occurs in an IPI handler (eg a cross CPU tlb flush).

Why should something bad happen in this case? (unless it happens in the IPI handler for the SMP lock vector, but I've duplicated the spinlock and apic-ack code to avoid using the fixups).

I've just noticed another problem instead: we might have a CPU waiting with interrupts disabled for the CPU executing the fixup. This could be fixed by waiting for a limited amount of iterations and then emulating the instruction, but it makes the code even uglier.

We might get deadlocks on NMIs but that would also happen if we e.g. get a memory parity NMI inside printk (deadlock on logbuf_lock). Should both bugs be fixed?

Quoted 8 lines
Quoted 5 lines
Quoted 4 lines

For the other fixups though you -have- to do them before you run the code. That isnt hard (eg sparc btfixup). You generate a list of the addresses in a segment, patch them all and let the init freeup blow the table away

Is doing them at runtime with the aforementioned workaround fine?

Is doing them all in the beginning not somewhat saner and more debuggable.

That wouldn't work for compiler-generated prefetches (unless you preprocess the compiler output) and would enlarge the kernel. However, it would be significantly cleaner.

Quoted 3 lines

The only reason to do it at runtime is hotplugging a less capable CPU. I have a suggestion for that case which is that we don't bother about it 8)

Even if we fixup at runtime this won't work since we the fixed up instructions won't fault.
To handle this, we would need to keep the table around, stop CPUs and fixup.
Anyway this scenario is quite unlikely.

#13 lore raw
Quoted 3 lines · Luca Barbieri

That wouldn't work for compiler-generated prefetches (unless you preprocess the compiler output) and would enlarge the kernel. However, it would be significantly cleaner.

My general experience with compiler generated prefetches right now is pretty poor for kernel type code. Its hard to do it right in the compiler for complex stuff rather than 'fortran in C' type jobs

We certainly could perl the asm to drop in the right directives if it became an issue, but there are children on the list so lets worry about it if it becomes a problem

#14 lore raw
Quoted 3 lines · Alan Cox

We certainly could perl the asm to drop in the right directives if it became an issue, but there are children on the list so lets worry about it if it becomes a problem

Other dirty tricks include __asm__ (".macro prefetcht0 addr; ....; .endm");

:-)

-- Jamie

#15 lore raw
In reply to Luca Barbieri
Quoted 5 lines · Luca Barbieri
Quoted 4 lines

For the other fixups though you -have- to do them before you run the code. That isnt hard (eg sparc btfixup). You generate a list of the addresses in a segment, patch them all and let the init freeup blow the table away

Is doing them at runtime with the aforementioned workaround fine?

I would suggest that the init time table is infinitely saner, but if there will be compiler generated instructions that are hard to catch, do
both: init time fixups for the __asm__ statements, and run time for compiler generated instructions.

You really want the init time fixups anyway, because a really _really_ obvious optimisation is to remove `lock' prefixes on UP.

-- Jamie