Immediate Values for 2.6.23-rc6-mm1

Immediate values provide a way to use dynamic code patching to update variables sitting within the instruction stream. It saves caches lines normally used by static read mostly variables. Enable it by default, but let users disable it through the EMBEDDED menu with the "Disable immediate values" submenu entry.

Note: Since I think that I really should let embedded systems developers using RO memory the option to disable the immediate values, I choose to leave this menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes sense because we want to compile out all the immediate code when we decide not to use optimized immediate values at all (it removes otherwise unused code).

Signed-off-by Mathieu Desnoyers <[email protected]>

CC Adrian Bunk <[email protected]>

CC Andi Kleen <[email protected]>

CC Alexey Dobriyan <[email protected]>

CC Christoph Hellwig <[email protected]>

---
 init/Kconfig |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

Index: linux-2.6-lttng/init/Kconfig
===================================================================

init/Kconfig +12 -0

+	depends on X86_32 || PPC || PPC64
+	bool
+	help
+	  Immediate values are used as read-mostly variables that are rarely
+	  updated. They use code patching to modify the values inscribed in the
+	  instruction stream. It provides a way to save precious cache lines
+	  that would otherwise have to be used by these variables. They can be
+	  disabled through the EMBEDDED menu.
+
 menuconfig EMBEDDED
 	bool "Configure standard kernel features (for small systems)"
 	help

@@ -646,6 +657,16 @@ config PROC_KPAGEMAP
           information on page-level memory usage. Disabling this interface
           will reduce the size of the kernel by around 600 bytes.
 
+config DISABLE_IMMEDIATE
+	default y if EMBEDDED
+	bool "Disable immediate values" if EMBEDDED

It's a pity that gas seems to generate plain 0x90 nops rather than long-nop forms here. I thought it could do that.

include/asm-i386/immediate.h line 44

Quoted 10 lines · Mathieu Desnoyers

include/asm-i386/immediate.h new file +10 -0

+#define immediate_read(name)						\
+	({								\
+		__typeof__(name##__immediate) value;			\
+		switch (sizeof(value)) {				\
+		case 1:							\
+			asm (	".section __immediate, \"a\", @progbits;\n\t" \
+					".long %1, (0f)+1, 1;\n\t"	\
+					".previous;\n\t"		\
+					"0:\n\t"			\
+					"mov %2,%0;\n\t"		\

Given that you're relying on the exact instruction that this mov generates, it might be better to explicitly put the opcodes in with .byte. That way you're protected from the assembler deciding to generate some other form of the instruction (for whatever reason). I guess substituting in different registers would be a pain.

Allowing different registers should be doable, but if so, one would have to put 0: at the *end* of the instruction and use (0f)-4 instead, since the non-%eax forms are one byte longer.

This also seems "safer", since an imm32 is always the last thing in the instruction.

Quoted 3 lines · Jeremy Fitzhardinge

It's a pity that gas seems to generate plain 0x90 nops rather than long-nop forms here. I thought it could do that.

.p2align does it

Quoted 6 lines · Andi Kleen

Quoted 3 lines · Jeremy Fitzhardinge

It's a pity that gas seems to generate plain 0x90 nops rather than long-nop forms here. I thought it could do that.

.p2align does it

Just .p2align? Not align, balign, org or skip? Seems... strange.

Quoted 7 lines · Andi Kleen

Quoted 3 lines · Jeremy Fitzhardinge

It's a pity that gas seems to generate plain 0x90 nops rather than long-nop forms here. I thought it could do that.

.p2align does it

Just .p2align? Not align, balign, org or skip? Seems... strange.

include/asm-i386/immediate.h line 44

Quoted 10 lines · Mathieu Desnoyers

include/asm-i386/immediate.h new file +10 -0

+#define immediate_read(name)						\
+	({								\
+		__typeof__(name##__immediate) value;			\
+		switch (sizeof(value)) {				\
+		case 1:							\
+			asm (	".section __immediate, \"a\", @progbits;\n\t" \
+					".long %1, (0f)+1, 1;\n\t"	\
+					".previous;\n\t"		\
+					"0:\n\t"			\
+					"mov %2,%0;\n\t"		\

Given that you're relying on the exact instruction that this mov generates, it might be better to explicitly put the opcodes in with .byte. That way you're protected from the assembler deciding to generate some other form of the instruction (for whatever reason). I guess substituting in different registers would be a pain.

Aside from that, is there any reason not to just put $0 in there rather than use %2?

include/asm-i386/immediate.h line 66

Quoted 6 lines

include/asm-i386/immediate.h new file +4 -0

+					".long %1, (0f)+1, 4;\n\t"	\
+					".previous;\n\t"		\
+					"1:\n\t"			\
+					".org (1b)+(3-((1b)%%4)), 0x90;\n\t" \

Seems a little complex, but I couldn't come up with anything much better:

	.org . + 3 - (. & 3), 0x90

You can use . rather than needing to define 1:, it doesn't need quite so many parens, and using &3 avoids the %% wart.

It's a pity that gas seems to generate plain 0x90 nops rather than long-nop forms here. I thought it could do that.

J

Quoted 18 lines · Jeremy Fitzhardinge

include/asm-i386/immediate.h line 44

Quoted 10 lines · Mathieu Desnoyers

include/asm-i386/immediate.h new file +10 -0

+#define immediate_read(name)						\
+	({								\
+		__typeof__(name##__immediate) value;			\
+		switch (sizeof(value)) {				\
+		case 1:							\
+			asm (	".section __immediate, \"a\", @progbits;\n\t" \
+					".long %1, (0f)+1, 1;\n\t"	\
+					".previous;\n\t"		\
+					"0:\n\t"			\
+					"mov %2,%0;\n\t"		\

Given that you're relying on the exact instruction that this mov generates, it might be better to explicitly put the opcodes in with .byte. That way you're protected from the assembler deciding to generate some other form of the instruction (for whatever reason). I guess substituting in different registers would be a pain.

Allowing different registers should be doable, but if so, one would have to put 0: at the *end* of the instruction and use (0f)-4 instead, since the non-%eax forms are one byte longer.

This also seems "safer", since an imm32 is always the last thing in the instruction.

-hpa

Quoted 3 lines · Jeremy Fitzhardinge

It's a pity that gas seems to generate plain 0x90 nops rather than long-nop forms here. I thought it could do that.

.p2align does it.

-Andi

Quoted 28 lines · On Tue, 18 Sep 2007 17:07:49 -0400 Mathieu Desnoyers wrote:

Immediate values provide a way to use dynamic code patching to update variables sitting within the instruction stream. It saves caches lines normally used by static read mostly variables. Enable it by default, but let users disable it through the EMBEDDED menu with the "Disable immediate values" submenu entry.

Note: Since I think that I really should let embedded systems developers using RO memory the option to disable the immediate values, I choose to leave this menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes sense because we want to compile out all the immediate code when we decide not to use optimized immediate values at all (it removes otherwise unused code).

Signed-off-by Mathieu Desnoyers <[email protected]>

CC Adrian Bunk <[email protected]>

CC Andi Kleen <[email protected]>

CC Alexey Dobriyan <[email protected]>

CC Christoph Hellwig <[email protected]>

---
 init/Kconfig |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

Index: linux-2.6-lttng/init/Kconfig
===================================================================

init/Kconfig +0 -0

@@ -407,6 +407,17 @@ config CC_OPTIMIZE_FOR_SIZE
 config SYSCTL
 	bool
 

init/Kconfig config CC_OPTIMIZE_FOR_SIZE · line 411

Quoted 2 lines

init/Kconfig +2 -0

+config IMMEDIATE
+	default y if !DISABLE_IMMEDIATE

So DISABLE_IMMEDIATE is just an intermediate symbol to make this option be displayed in the EMBEDDED menu instead of in the General Setup menu ?

Quoted 20 lines

init/Kconfig +12 -0

+	depends on X86_32 || PPC || PPC64
+	bool
+	help
+	  Immediate values are used as read-mostly variables that are rarely
+	  updated. They use code patching to modify the values inscribed in the
+	  instruction stream. It provides a way to save precious cache lines
+	  that would otherwise have to be used by these variables. They can be
+	  disabled through the EMBEDDED menu.
+
 menuconfig EMBEDDED
 	bool "Configure standard kernel features (for small systems)"
 	help

@@ -646,6 +657,16 @@ config PROC_KPAGEMAP
           information on page-level memory usage. Disabling this interface
           will reduce the size of the kernel by around 600 bytes.
 
+config DISABLE_IMMEDIATE
+	default y if EMBEDDED
+	bool "Disable immediate values" if EMBEDDED

init/Kconfig config PROC_KPAGEMAP · line 672

Quoted 10 lines

init/Kconfig +7 -0

+	depends on X86_32 || PPC || PPC64
+	help
+	  Disable code patching based immediate values for embedded systems. It
+	  consumes slightly more memory and requires to modify the instruction
+	  stream each time a variable is updated. Should really be disabled for
+	  embedded systems with read-only text.
+
 endmenu		# General setup
 
 config RT_MUTEXES

---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

And yes, it's a pity there is no way to produce the long-nops there. :(

Quoted 4 lines · H. Peter Anvin

Allowing different registers should be doable, but if so, one would have to put 0: at the *end* of the instruction and use (0f)-4 instead, since the non-%eax forms are one byte longer.

OK, that's already a problem since its using "=r" as the constraint.

Quoted 2 lines

This also seems "safer", since an imm32 is always the last thing in the instruction.

Good idea. If gas/gcc generates entirely the wrong addressing mode, then we've got bigger problems.

Quoted 6 lines · * Jeremy Fitzhardinge ([email protected]) wrote:

Quoted 4 lines · H. Peter Anvin

Allowing different registers should be doable, but if so, one would have to put 0: at the *end* of the instruction and use (0f)-4 instead, since the non-%eax forms are one byte longer.

Quoted 8 lines

OK, that's already a problem since its using "=r" as the constraint.

Quoted 2 lines

This also seems "safer", since an imm32 is always the last thing in the instruction.

Good idea. If gas/gcc generates entirely the wrong addressing mode, then we've got bigger problems.

Ok, let's have a good look at what we want:

1 - get a pointer to the beginning of the immediate value within the
instruction.
2 - make sure that the immediate value, within the instruction, is
written to atomically wrt all CPUs, even on older architectures where non aligned writes are not atomic.

Effectively, placing a label at the end of the instruction, and then offsetting backward from there, will give us (1).

Then, for the alignment, we have to give a good look at the instruction set reference, mov instruction, to see what the variants of mov immediate value to register are on i386.

First, let's look at the possible prefixes:
- Lock and repeat prefixes : no
- Segment override prefixes: no memory reference there, so doesn't apply.
- Branch hints : no, it's a mov instruction
- Operand-size override prefix: *yes*, can be used for 2 bytes mov
- Address-size override prefix: no address in there, only immediate value and register.

(looking at the Compat/Leg Mode)

3 cases:

* 1 byte

B0 + rb         MOV r8, imm8     (1 byte opcode)
REX + B0 + rb   MOV r8, imm8     (only on 64 bits archs, never generated)
C6 /0           MOV r/m8, imm8   (2 bytes opcode)

(this one doesn't require alignment at all, since we do a 1 byte write)

* 2 bytes

B8 + rw         MOV r16, imm16   (1 byte opcode)
66 B8 + rd      MOV r16, imm16   (2 bytes opcode) (with 66H prefix)
C7 /0           MOV r/m16, imm16 (2 bytes opcode)

(Alignment on 4 bytes boundaries would be required because of the possible 1 byte opcode ? Or is the 66H prefix mandatory there ? If it is, then we can safely align on 2 bytes boundaries.)

* 4 bytes
B8 + rd MOV r32, imm32 (1 byte opcode)
C7 /0 MOV r/m32, imm32 (2 bytes opcode)
(the 2 bytes opcode can be a problem)

I have missed anything ?

Ok, let's have a good look at what we want:

1 - get a pointer to the beginning of the immediate value within the
instruction.
2 - make sure that the immediate value, within the instruction, is
written to atomically wrt all CPUs, even on older architectures where non aligned writes are not atomic.

* 4 bytes
B8 + rd MOV r32, imm32 (1 byte opcode)
C7 /0 MOV r/m32, imm32 (2 bytes opcode)
(the 2 bytes opcode can be a problem)

Quoted 9 lines · Mathieu Desnoyers

Ok, let's have a good look at what we want:

1 - get a pointer to the beginning of the immediate value within the
instruction.
2 - make sure that the immediate value, within the instruction, is
written to atomically wrt all CPUs, even on older architectures where non aligned writes are not atomic.

I think you'll find that even on modern architectures cross-cacheline writes aren't atomic.

Quoted 6 lines

* 4 bytes
B8 + rd MOV r32, imm32 (1 byte opcode)
C7 /0 MOV r/m32, imm32 (2 bytes opcode)
(the 2 bytes opcode can be a problem)

If gas generates the C7 opcodes by default, then that's a bug, nothing less.

Cross-cache-line, sure. But what about just not sizeof aligned? If its enough to avoid cross-cache-line, then that's simpler.

Which is something I was going to comment on: Mathieu, you try to align the constant itself, but you don't prevent the instruction overall from crossing a cache line. Given how delicate all this stuff is, it seems like a good idea to do that.

Quoted 12 lines · H. Peter Anvin

Quoted 9 lines · Mathieu Desnoyers

Ok, let's have a good look at what we want:

1 - get a pointer to the beginning of the immediate value within the
instruction.
2 - make sure that the immediate value, within the instruction, is
written to atomically wrt all CPUs, even on older architectures where non aligned writes are not atomic.

Quoted 3 lines

I think you'll find that even on modern architectures cross-cacheline writes aren't atomic.

Cross-cache-line, sure. But what about just not sizeof aligned? If its enough to avoid cross-cache-line, then that's simpler.

Which is something I was going to comment on: Mathieu, you try to align the constant itself, but you don't prevent the instruction overall from crossing a cache line. Given how delicate all this stuff is, it seems like a good idea to do that.

Quoted 8 lines

Quoted 7 lines

* 4 bytes
B8 + rd MOV r32, imm32 (1 byte opcode)
C7 /0 MOV r/m32, imm32 (2 bytes opcode)
(the 2 bytes opcode can be a problem)

Quoted 2 lines

If gas generates the C7 opcodes by default, then that's a bug, nothing less.

Well, in this case, it might be preferred if it brings the constant into alignment without explicit padding :)

Quoted 4 lines · Jeremy Fitzhardinge

Cross-cache-line, sure. But what about just not sizeof aligned? If its enough to avoid cross-cache-line, then that's simpler.

Not really. It pretty much comes down to the same problem.

Quoted 4 lines

Which is something I was going to comment on: Mathieu, you try to align the constant itself, but you don't prevent the instruction overall from crossing a cache line. Given how delicate all this stuff is, it seems like a good idea to do that.

Given how delicate all his stuff is, it would be interesting to know the magnitude of the expected payoff, which I personally don't remember seeing.

i386 optimization of the immediate values which uses a movl with code patching to set/unset the value used to populate the register used as variable source.

Changelog:
- Use text_poke_early with cr0 WP save/restore to patch the bypass. We are doing non atomic writes to a code region only touched by us (nobody can execute it since we are protected by the immediate_mutex).
- Put immediate_set and _immediate_set in the architecture independent header.

include/asm-i386/immediate.h new file +11 -0

+struct __immediate {
+	long var;		/* Pointer to the identifier variable of the
+				 * immediate value
+				 */
+	long immediate;		/*
+				 * Pointer to the memory location of the
+				 * immediate value within the instruction.
+				 */
+	long size;		/* Type size. */
+};
 
 
+		case 2:							\

Quoted 19 lines · Mathieu Desnoyers

i386 optimization of the immediate values which uses a movl with code patching to set/unset the value used to populate the register used as variable source.

Changelog:
- Use text_poke_early with cr0 WP save/restore to patch the bypass. We are doing non atomic writes to a code region only touched by us (nobody can execute it since we are protected by the immediate_mutex).
- Put immediate_set and _immediate_set in the architecture independent header.

include/asm-i386/immediate.h new file +10 -0

+struct __immediate {
+	long var;		/* Pointer to the identifier variable of the
+				 * immediate value
+				 */
+	long immediate;		/*
+				 * Pointer to the memory location of the
+				 * immediate value within the instruction.
+				 */
+	long size;		/* Type size. */
+};

include/asm-i386/immediate.h line 59

Quoted 11 lines

include/asm-i386/immediate.h new file +11 -0

+		case 2:							\
+			asm (	".section __immediate, \"a\", @progbits;\n\t" \
+					".long %1, (0f)+2, 2;\n\t"	\
+					".previous;\n\t"		\
+					"1:\n\t"			\
+					".align 2;\n\t"			\
+					"0:\n\t"			\
+					"mov %2,%0;\n\t"		\
+				: "=r" (value)				\
+				: "m" (name##__immediate),		\
+				  "i" (0));				\

Instead of letting gcc use whatever instruction it sees fit best for accessing the variable (like add/cmp/test...)
now we force it to use mov imm,reg first. Maybe with preceding nop due to "align 2".

And then we use 12 more bytes in __immediate section *for each* place where you read the variable.

Do you plan to use the same approach on x86_64?
I mean, longs there are twice as long.

Can this be made conditional, on CONFIG_CC_OPTIMIZE_FOR_SIZE perhaps?

--
vda

Quoted 4 lines · H. Peter Anvin

Allowing different registers should be doable, but if so, one would have to put 0: at the *end* of the instruction and use (0f)-4 instead, since the non-%eax forms are one byte longer.

OK, that's already a problem since its using "=r" as the constraint.

Quoted 2 lines

This also seems "safer", since an imm32 is always the last thing in the instruction.

Good idea. If gas/gcc generates entirely the wrong addressing mode, then we've got bigger problems.

I have tried generating asm-to-"register" c variables for char, short and int on i386 and I do not see this happening. The char opcode is always 1 byte, short 2 bytes and int 1 byte. Result:

gcc version 4.1.3 20070812 (prerelease) (Debian 4.1.2-15)

   8:   b3 02                   mov    $0x2,%bl
   a:   b1 03                   mov    $0x3,%cl
   c:   b2 04                   mov    $0x4,%dl
   e:   b0 05                   mov    $0x5,%al

  4f:   66 be 06 00             mov    $0x6,%si
  53:   66 bb 07 00             mov    $0x7,%bx
  57:   66 b9 08 00             mov    $0x8,%cx
  5b:   66 ba 09 00             mov    $0x9,%dx
  5f:   66 b8 0a 00             mov    $0xa,%ax

  9f:   bb 0b 00 00 00          mov    $0xb,%ebx
  a4:   be 0c 00 00 00          mov    $0xc,%esi
  a9:   b9 0d 00 00 00          mov    $0xd,%ecx
  ae:   ba 0e 00 00 00          mov    $0xe,%edx
  b3:   b8 0f 00 00 00          mov    $0xf,%eax

I notice that having a "=r" inline assembly that outputs to the first "register char" variable seems to be problematic. It fails with the following error:

/tmp/ccy35Hq1.s: Assembler messages:
/tmp/ccy35Hq1.s:15: Error: bad register name `%sil'

- Either I use a "r" constraint and let gcc produce the instructions, that I need to assume to have correct size so I can align their immediate values (therefore, taking the offset from the end of the instruction will not help). Here, if gas changes its behavior dramatically for a given immediate value size, it will break.

- Second choice is to stick to a particular register, choosing the one with the less side-effect, and encoding the instruction ourselves. I start to think that this second solution might be safer, even though we wouldn't let the compiler select the register which has the less impact by itself.

Quoted 5 lines · Mathieu Desnoyers

I have tried generating asm-to-"register" c variables for char, short and int on i386 and I do not see this happening. The char opcode is always 1 byte, short 2 bytes and int 1 byte. Result:

The comment was referring to x86-64, but I incorrectly remembered that applying to "movq $imm,%reg" as opposed to loading from an absolute address. gas actually has a special opcode (movabs) for the 64-bit version of the latter variant, which is only available with %rax and its subregisters.

Nevermind, in other words. It's still true, though, that the immediate will always be the last thing in the instruction -- that's a fixture of the instruction format.

Quoted 20 lines

gcc version 4.1.3 20070812 (prerelease) (Debian 4.1.2-15)

  8:   b3 02                   mov    $0x2,%bl
  a:   b1 03                   mov    $0x3,%cl
  c:   b2 04                   mov    $0x4,%dl
  e:   b0 05                   mov    $0x5,%al

 4f:   66 be 06 00             mov    $0x6,%si
 53:   66 bb 07 00             mov    $0x7,%bx
 57:   66 b9 08 00             mov    $0x8,%cx
 5b:   66 ba 09 00             mov    $0x9,%dx
 5f:   66 b8 0a 00             mov    $0xa,%ax

 9f:   bb 0b 00 00 00          mov    $0xb,%ebx
 a4:   be 0c 00 00 00          mov    $0xc,%esi
 a9:   b9 0d 00 00 00          mov    $0xd,%ecx
 ae:   ba 0e 00 00 00          mov    $0xe,%edx
 b3:   b8 0f 00 00 00          mov    $0xf,%eax

Quoted 6 lines

I notice that having a "=r" inline assembly that outputs to the first "register char" variable seems to be problematic. It fails with the following error:

/tmp/ccy35Hq1.s: Assembler messages:
/tmp/ccy35Hq1.s:15: Error: bad register name `%sil'

'r' is wrong for 8-bit variables on i386. It needs to be 'q'.

Will fix. I noticed that it was because I had too much "register" char variables declared and used at the same time. Putting a "g" constraint gave the same result.