Skip to contentSkip to conversation

x86/asm/entry/64: pack interrupt dispatch table tighter

PATCH In review Denys Vlasenko 4 participants 10 messages Apr 3, 2015 – Apr 4, 2015 x86

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 x86/asm/entry/64: pack interrupt dispatch table tighter

Interrupt entry points are handled with the following code:
Each 32-byte code block contains seven entry points

		...
		[push][jump 22] // 4 bytes
		[push][jump 18] // 4 bytes
		[push][jump 14] // 4 bytes
		[push][jump 10] // 4 bytes
		[push][jump  6] // 4 bytes
		[push][jump  2] // 4 bytes
		[push][jump common_interrupt][padding] // 8 bytes

		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump common_interrupt][padding]

		[padding_2]
	common_interrupt:

The first six jumps are short (2-byte insns) jumps to the last jump in the block. The last jump usually has to be a longer, 5-byte form.

There are about 30 such blocks.

This change uses the fact that last few of these blocks are close to "common_interrupt" label and the last jump there can also be a short one.

This allows several last 32-byte code blocks to contain eight, not seven entry points, and to have all these entry points jump directly to common_interrupt, eliminating one branch. They look like this:

[push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes

This change replaces ".p2align CONFIG_X86_L1_CACHE_SHIFT" before dispatch table and before common_interrupt with 32-byte alignment.

The first alignment was completely unnecessary:
the dispatch table will not benefit from any alignment bigger than 32 bytes (any entry point needs at most only 32 bytes of table to be read by the CPU).

The alignment before common_interrupt label affects the size of padding (the "[padding_2]" above) and excessive padding reduces the number of blocks which can be optimized. In the .config I tested with, this alignment was 64 bytes, this means two fewer blocks could be optimized. I believe 32-byte alignment should do just fine.

The condition which controls the choice of a direct jump versus short one,

    /* Can we reach common_interrupt with a short jump? */
    .if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)

was tested to be a passimistic one: the generated code will not erroneously generate a longer than necessary jump even with maximum possible padding and with -1 subtracted from the right hand side above.
This was verified by checking disassembly.

However, with current value of FIRST_SYSTEM_VECTOR it so happens that the padding before "common_interrupt" is zero bytes.

 Disassembly before                           After
 ==========================================   ==================================
...                                           ...
840 6a9b           push $0xffffffffffffff9b   82c 6a9d  push $0xffffffffffffff9d
842 eb16           jmp  85a                   82e eb30  jmp  860
844 6a9a           push $0xffffffffffffff9a   830 6a9c  push $0xffffffffffffff9c
846 eb12           jmp  85a                   832 eb2c  jmp  860
848 6a99           push $0xffffffffffffff99   834 6a9b  push $0xffffffffffffff9b
84a eb0e           jmp  85a                   836 eb28  jmp  860
84c 6a98           push $0xffffffffffffff98   838 6a9a  push $0xffffffffffffff9a
84e eb0a           jmp  85a                   83a eb24  jmp  860
850 6a97           push $0xffffffffffffff97   83c 6a99  push $0xffffffffffffff99
852 eb06           jmp  85a                   83e eb20  jmp  860
854 6a96           push $0xffffffffffffff96   840 6a98  push $0xffffffffffffff98
856 eb02           jmp  85a                   842 eb1c  jmp  860
858 6a95           push $0xffffffffffffff95   844 6a97  push $0xffffffffffffff97
85a eb24           jmp  880                   846 eb18  jmp  860
85c 0f1f4000       nopl 0x0(%rax)             848 6a96  push $0xffffffffffffff96
860 6a94           push $0xffffffffffffff94   84a eb14  jmp  860
862 eb0c           jmp  870                   84c 6a95  push $0xffffffffffffff95
864 6a93           push $0xffffffffffffff93   84e eb10  jmp  860
866 eb08           jmp  870                   850 6a94  push $0xffffffffffffff94
868 6a92           push $0xffffffffffffff92   852 eb0c  jmp  860
86a eb04           jmp  870                   854 6a93  push $0xffffffffffffff93
86c 6a91           push $0xffffffffffffff91   856 eb08  jmp  860
86e eb00           jmp  870                   858 6a92  push $0xffffffffffffff92
870 eb0e           jmp  880                   85a eb04  jmp  860

872 66666666662e0f data32 data32 data32 data3285c 6a91 push $0xffffffffffffff91 879 1f840000000000 nopw %cs:0x0(%rax,%rax,1) 85e eb00 jmp 860
880 <common_interrupt>: 860 <common_interrupt>:

Sizes:
text data bss dec hex filename

  12578	      0	      0	  12578	   3122	entry_64.o.before
  12546	      0	      0	  12546	   3102	entry_64.o
CC Linus Torvalds <[email protected]>
CC Steven Rostedt <[email protected]>
CC Ingo Molnar <[email protected]>
CC Borislav Petkov <[email protected]>
CC "H. Peter Anvin" <[email protected]>
CC Andy Lutomirski <[email protected]>
CC Oleg Nesterov <[email protected]>
CC Frederic Weisbecker <[email protected]>
CC Alexei Starovoitov <[email protected]>
CC Will Drewry <[email protected]>
CC Kees Cook <[email protected]>
---
 arch/x86/kernel/entry_64.S | 61 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 49 insertions(+), 12 deletions(-)
arch/x86/kernel/entry_64.S +49 -12
index da137f9..2003417 100644
@@ -537,33 +537,70 @@ END(ret_from_fork)
  * Build the entry stubs and pointer table with some assembler magic.
  * We pack 7 stubs into a single 32-byte chunk, which will fit in a
  * single cache line on all modern x86 implementations.
+ * The last few cachelines pack 8 stubs each.
  */
+ALIGN_common_interrupt=32
 	.section .init.rodata,"a"
 ENTRY(interrupt)
 	.section .entry.text
-	.p2align 5
-	.p2align CONFIG_X86_L1_CACHE_SHIFT
+	.align 32
 ENTRY(irq_entries_start)
 	INTR_FRAME
 vector=FIRST_EXTERNAL_VECTOR
-.rept (FIRST_SYSTEM_VECTOR-FIRST_EXTERNAL_VECTOR+6)/7
-	.balign 32
+.rept 256 /* this number does not need to be exact, just big enough */
+
+  /*
+   * Block of six "push + short_jump" pairs, 4 bytes each,
+   * and a 2-byte seventh "push", without its jump yet.
+   */
+need_near_jump=0
+push_count=0
   .rept	7
     .if vector < FIRST_SYSTEM_VECTOR
-      .if vector <> FIRST_EXTERNAL_VECTOR
+1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
+	.previous
+	.quad 1b
+	.section .entry.text
+vector=vector+1
+push_count=push_count+1
+      .if push_count < 7
+	/* Can we reach common_interrupt with a short jump? */
+	.if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)
+	  jmp common_interrupt  /* yes */
+	.else
+	  jmp 2f
+need_near_jump=1
+	.endif
 	CFI_ADJUST_CFA_OFFSET -8
       .endif
+    .endif
+  .endr
+
+  /* If we are close to the end, we can pack in yet another pair */
+  .if need_near_jump == 0
+    .if push_count == 7
+	/* The "short jump" for the seventh "push" */
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+    .endif
+    .if vector < FIRST_SYSTEM_VECTOR
+	/* "push + short_jump" pair #8 */
 1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
-      .if ((vector-FIRST_EXTERNAL_VECTOR)%7) <> 6
-	jmp 2f
-      .endif
-      .previous
+	.previous
 	.quad 1b
-      .section .entry.text
+	.section .entry.text
 vector=vector+1
+push_count=push_count+1
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
     .endif
-  .endr
+  .else
+	/* Use remaining space for "near jump" for the seventh "push" */
 2:	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+	.align 2
+  .endif
+
 .endr
 	CFI_ENDPROC
 END(irq_entries_start)
@@ -632,7 +669,7 @@ END(interrupt)
 	 * The interrupt stubs push (~vector+0x80) onto the stack and
 	 * then jump to common_interrupt.
 	 */
-	.p2align CONFIG_X86_L1_CACHE_SHIFT
+	.align ALIGN_common_interrupt
 common_interrupt:
 	XCPT_FRAME
 	ASM_CLAC
Signature · 1 line
1.8.1.4
#1 lore raw
Quoted 200 lines · Denys Vlasenko

Interrupt entry points are handled with the following code:
Each 32-byte code block contains seven entry points

		...
		[push][jump 22] // 4 bytes
		[push][jump 18] // 4 bytes
		[push][jump 14] // 4 bytes
		[push][jump 10] // 4 bytes
		[push][jump  6] // 4 bytes
		[push][jump  2] // 4 bytes
		[push][jump common_interrupt][padding] // 8 bytes

		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump common_interrupt][padding]

		[padding_2]
	common_interrupt:

The first six jumps are short (2-byte insns) jumps to the last jump in the block. The last jump usually has to be a longer, 5-byte form.

There are about 30 such blocks.

This change uses the fact that last few of these blocks are close to "common_interrupt" label and the last jump there can also be a short one.

This allows several last 32-byte code blocks to contain eight, not seven entry points, and to have all these entry points jump directly to common_interrupt, eliminating one branch. They look like this:

[push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes

This change replaces ".p2align CONFIG_X86_L1_CACHE_SHIFT" before dispatch table and before common_interrupt with 32-byte alignment.

The first alignment was completely unnecessary:
the dispatch table will not benefit from any alignment bigger than 32 bytes (any entry point needs at most only 32 bytes of table to be read by the CPU).

The alignment before common_interrupt label affects the size of padding (the "[padding_2]" above) and excessive padding reduces the number of blocks which can be optimized. In the .config I tested with, this alignment was 64 bytes, this means two fewer blocks could be optimized. I believe 32-byte alignment should do just fine.

The condition which controls the choice of a direct jump versus short one,

    /* Can we reach common_interrupt with a short jump? */
    .if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)

was tested to be a passimistic one: the generated code will not erroneously generate a longer than necessary jump even with maximum possible padding and with -1 subtracted from the right hand side above.
This was verified by checking disassembly.

However, with current value of FIRST_SYSTEM_VECTOR it so happens that the padding before "common_interrupt" is zero bytes.

 Disassembly before                           After
 ==========================================   ==================================
...                                           ...
840 6a9b           push $0xffffffffffffff9b   82c 6a9d  push $0xffffffffffffff9d
842 eb16           jmp  85a                   82e eb30  jmp  860
844 6a9a           push $0xffffffffffffff9a   830 6a9c  push $0xffffffffffffff9c
846 eb12           jmp  85a                   832 eb2c  jmp  860
848 6a99           push $0xffffffffffffff99   834 6a9b  push $0xffffffffffffff9b
84a eb0e           jmp  85a                   836 eb28  jmp  860
84c 6a98           push $0xffffffffffffff98   838 6a9a  push $0xffffffffffffff9a
84e eb0a           jmp  85a                   83a eb24  jmp  860
850 6a97           push $0xffffffffffffff97   83c 6a99  push $0xffffffffffffff99
852 eb06           jmp  85a                   83e eb20  jmp  860
854 6a96           push $0xffffffffffffff96   840 6a98  push $0xffffffffffffff98
856 eb02           jmp  85a                   842 eb1c  jmp  860
858 6a95           push $0xffffffffffffff95   844 6a97  push $0xffffffffffffff97
85a eb24           jmp  880                   846 eb18  jmp  860
85c 0f1f4000       nopl 0x0(%rax)             848 6a96  push $0xffffffffffffff96
860 6a94           push $0xffffffffffffff94   84a eb14  jmp  860
862 eb0c           jmp  870                   84c 6a95  push $0xffffffffffffff95
864 6a93           push $0xffffffffffffff93   84e eb10  jmp  860
866 eb08           jmp  870                   850 6a94  push $0xffffffffffffff94
868 6a92           push $0xffffffffffffff92   852 eb0c  jmp  860
86a eb04           jmp  870                   854 6a93  push $0xffffffffffffff93
86c 6a91           push $0xffffffffffffff91   856 eb08  jmp  860
86e eb00           jmp  870                   858 6a92  push $0xffffffffffffff92
870 eb0e           jmp  880                   85a eb04  jmp  860

872 66666666662e0f data32 data32 data32 data3285c 6a91 push $0xffffffffffffff91 879 1f840000000000 nopw %cs:0x0(%rax,%rax,1) 85e eb00 jmp 860
880 <common_interrupt>: 860 <common_interrupt>:

Sizes:
text data bss dec hex filename

  12578	      0	      0	  12578	   3122	entry_64.o.before
  12546	      0	      0	  12546	   3102	entry_64.o
CC Linus Torvalds <[email protected]>
CC Steven Rostedt <[email protected]>
CC Ingo Molnar <[email protected]>
CC Borislav Petkov <[email protected]>
CC "H. Peter Anvin" <[email protected]>
CC Andy Lutomirski <[email protected]>
CC Oleg Nesterov <[email protected]>
CC Frederic Weisbecker <[email protected]>
CC Alexei Starovoitov <[email protected]>
CC Will Drewry <[email protected]>
CC Kees Cook <[email protected]>
---
 arch/x86/kernel/entry_64.S | 61 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 49 insertions(+), 12 deletions(-)
arch/x86/kernel/entry_64.S +42 -11
index da137f9..2003417 100644
@@ -537,33 +537,70 @@ END(ret_from_fork)
  * Build the entry stubs and pointer table with some assembler magic.
  * We pack 7 stubs into a single 32-byte chunk, which will fit in a
  * single cache line on all modern x86 implementations.
+ * The last few cachelines pack 8 stubs each.
  */
+ALIGN_common_interrupt=32
 	.section .init.rodata,"a"
 ENTRY(interrupt)
 	.section .entry.text
-	.p2align 5
-	.p2align CONFIG_X86_L1_CACHE_SHIFT
+	.align 32
 ENTRY(irq_entries_start)
 	INTR_FRAME
 vector=FIRST_EXTERNAL_VECTOR
-.rept (FIRST_SYSTEM_VECTOR-FIRST_EXTERNAL_VECTOR+6)/7
-	.balign 32
+.rept 256 /* this number does not need to be exact, just big enough */
+
+  /*
+   * Block of six "push + short_jump" pairs, 4 bytes each,
+   * and a 2-byte seventh "push", without its jump yet.
+   */
+need_near_jump=0
+push_count=0
   .rept	7
     .if vector < FIRST_SYSTEM_VECTOR
-      .if vector <> FIRST_EXTERNAL_VECTOR
+1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
+	.previous
+	.quad 1b
+	.section .entry.text
+vector=vector+1
+push_count=push_count+1
+      .if push_count < 7
+	/* Can we reach common_interrupt with a short jump? */
+	.if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)
+	  jmp common_interrupt  /* yes */
+	.else
+	  jmp 2f
+need_near_jump=1
+	.endif
 	CFI_ADJUST_CFA_OFFSET -8
       .endif
+    .endif
+  .endr
+
+  /* If we are close to the end, we can pack in yet another pair */
+  .if need_near_jump == 0
+    .if push_count == 7
+	/* The "short jump" for the seventh "push" */
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+    .endif
+    .if vector < FIRST_SYSTEM_VECTOR
+	/* "push + short_jump" pair #8 */
 1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
-      .if ((vector-FIRST_EXTERNAL_VECTOR)%7) <> 6
-	jmp 2f
-      .endif
-      .previous
+	.previous
 	.quad 1b
-      .section .entry.text
+	.section .entry.text
 vector=vector+1
+push_count=push_count+1
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
     .endif
-  .endr

arch/x86/kernel/entry_64.S END(ret_from_fork) · line 606

Quoted 10 lines
arch/x86/kernel/entry_64.S +6 -0
+  .else
+	/* Use remaining space for "near jump" for the seventh "push" */
 2:	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+	.align 2
+  .endif
+
 .endr
 	CFI_ENDPROC
 END(irq_entries_start)

So I think this might be easier to read if we went low tech and used an open-coded 240+ lines assembly file for this, with a few obvious-purpose helper macros? It's not like it will change all that often so it only has to be generated once.

Thanks,

Ingo

#2 lore raw
Quoted 209 lines · Ingo Molnar
Quoted 206 lines · Denys Vlasenko

Interrupt entry points are handled with the following code:
Each 32-byte code block contains seven entry points

		...
		[push][jump 22] // 4 bytes
		[push][jump 18] // 4 bytes
		[push][jump 14] // 4 bytes
		[push][jump 10] // 4 bytes
		[push][jump  6] // 4 bytes
		[push][jump  2] // 4 bytes
		[push][jump common_interrupt][padding] // 8 bytes

		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump common_interrupt][padding]

		[padding_2]
	common_interrupt:

The first six jumps are short (2-byte insns) jumps to the last jump in the block. The last jump usually has to be a longer, 5-byte form.

There are about 30 such blocks.

This change uses the fact that last few of these blocks are close to "common_interrupt" label and the last jump there can also be a short one.

This allows several last 32-byte code blocks to contain eight, not seven entry points, and to have all these entry points jump directly to common_interrupt, eliminating one branch. They look like this:

[push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes

This change replaces ".p2align CONFIG_X86_L1_CACHE_SHIFT" before dispatch table and before common_interrupt with 32-byte alignment.

The first alignment was completely unnecessary:
the dispatch table will not benefit from any alignment bigger than 32 bytes (any entry point needs at most only 32 bytes of table to be read by the CPU).

The alignment before common_interrupt label affects the size of padding (the "[padding_2]" above) and excessive padding reduces the number of blocks which can be optimized. In the .config I tested with, this alignment was 64 bytes, this means two fewer blocks could be optimized. I believe 32-byte alignment should do just fine.

The condition which controls the choice of a direct jump versus short one,

    /* Can we reach common_interrupt with a short jump? */
    .if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)

was tested to be a passimistic one: the generated code will not erroneously generate a longer than necessary jump even with maximum possible padding and with -1 subtracted from the right hand side above.
This was verified by checking disassembly.

However, with current value of FIRST_SYSTEM_VECTOR it so happens that the padding before "common_interrupt" is zero bytes.

 Disassembly before                           After
 ==========================================   ==================================
...                                           ...
840 6a9b           push $0xffffffffffffff9b   82c 6a9d  push $0xffffffffffffff9d
842 eb16           jmp  85a                   82e eb30  jmp  860
844 6a9a           push $0xffffffffffffff9a   830 6a9c  push $0xffffffffffffff9c
846 eb12           jmp  85a                   832 eb2c  jmp  860
848 6a99           push $0xffffffffffffff99   834 6a9b  push $0xffffffffffffff9b
84a eb0e           jmp  85a                   836 eb28  jmp  860
84c 6a98           push $0xffffffffffffff98   838 6a9a  push $0xffffffffffffff9a
84e eb0a           jmp  85a                   83a eb24  jmp  860
850 6a97           push $0xffffffffffffff97   83c 6a99  push $0xffffffffffffff99
852 eb06           jmp  85a                   83e eb20  jmp  860
854 6a96           push $0xffffffffffffff96   840 6a98  push $0xffffffffffffff98
856 eb02           jmp  85a                   842 eb1c  jmp  860
858 6a95           push $0xffffffffffffff95   844 6a97  push $0xffffffffffffff97
85a eb24           jmp  880                   846 eb18  jmp  860
85c 0f1f4000       nopl 0x0(%rax)             848 6a96  push $0xffffffffffffff96
860 6a94           push $0xffffffffffffff94   84a eb14  jmp  860
862 eb0c           jmp  870                   84c 6a95  push $0xffffffffffffff95
864 6a93           push $0xffffffffffffff93   84e eb10  jmp  860
866 eb08           jmp  870                   850 6a94  push $0xffffffffffffff94
868 6a92           push $0xffffffffffffff92   852 eb0c  jmp  860
86a eb04           jmp  870                   854 6a93  push $0xffffffffffffff93
86c 6a91           push $0xffffffffffffff91   856 eb08  jmp  860
86e eb00           jmp  870                   858 6a92  push $0xffffffffffffff92
870 eb0e           jmp  880                   85a eb04  jmp  860

872 66666666662e0f data32 data32 data32 data3285c 6a91 push $0xffffffffffffff91 879 1f840000000000 nopw %cs:0x0(%rax,%rax,1) 85e eb00 jmp 860
880 <common_interrupt>: 860 <common_interrupt>:

Sizes:
text data bss dec hex filename

  12578	      0	      0	  12578	   3122	entry_64.o.before
  12546	      0	      0	  12546	   3102	entry_64.o
CC Linus Torvalds <[email protected]>
CC Steven Rostedt <[email protected]>
CC Ingo Molnar <[email protected]>
CC Borislav Petkov <[email protected]>
CC "H. Peter Anvin" <[email protected]>
CC Andy Lutomirski <[email protected]>
CC Oleg Nesterov <[email protected]>
CC Frederic Weisbecker <[email protected]>
CC Alexei Starovoitov <[email protected]>
CC Will Drewry <[email protected]>
CC Kees Cook <[email protected]>
---
 arch/x86/kernel/entry_64.S | 61 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 49 insertions(+), 12 deletions(-)
arch/x86/kernel/entry_64.S +47 -11
index da137f9..2003417 100644
@@ -537,33 +537,70 @@ END(ret_from_fork)
  * Build the entry stubs and pointer table with some assembler magic.
  * We pack 7 stubs into a single 32-byte chunk, which will fit in a
  * single cache line on all modern x86 implementations.
+ * The last few cachelines pack 8 stubs each.
  */
+ALIGN_common_interrupt=32
 	.section .init.rodata,"a"
 ENTRY(interrupt)
 	.section .entry.text
-	.p2align 5
-	.p2align CONFIG_X86_L1_CACHE_SHIFT
+	.align 32
 ENTRY(irq_entries_start)
 	INTR_FRAME
 vector=FIRST_EXTERNAL_VECTOR
-.rept (FIRST_SYSTEM_VECTOR-FIRST_EXTERNAL_VECTOR+6)/7
-	.balign 32
+.rept 256 /* this number does not need to be exact, just big enough */
+
+  /*
+   * Block of six "push + short_jump" pairs, 4 bytes each,
+   * and a 2-byte seventh "push", without its jump yet.
+   */
+need_near_jump=0
+push_count=0
   .rept	7
     .if vector < FIRST_SYSTEM_VECTOR
-      .if vector <> FIRST_EXTERNAL_VECTOR
+1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
+	.previous
+	.quad 1b
+	.section .entry.text
+vector=vector+1
+push_count=push_count+1
+      .if push_count < 7
+	/* Can we reach common_interrupt with a short jump? */
+	.if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)
+	  jmp common_interrupt  /* yes */
+	.else
+	  jmp 2f
+need_near_jump=1
+	.endif
 	CFI_ADJUST_CFA_OFFSET -8
       .endif
+    .endif
+  .endr
+
+  /* If we are close to the end, we can pack in yet another pair */
+  .if need_near_jump == 0
+    .if push_count == 7
+	/* The "short jump" for the seventh "push" */
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+    .endif
+    .if vector < FIRST_SYSTEM_VECTOR
+	/* "push + short_jump" pair #8 */
 1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
-      .if ((vector-FIRST_EXTERNAL_VECTOR)%7) <> 6
-	jmp 2f
-      .endif
-      .previous
+	.previous
 	.quad 1b
-      .section .entry.text
+	.section .entry.text
 vector=vector+1
+push_count=push_count+1
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
     .endif
-  .endr
+  .else
+	/* Use remaining space for "near jump" for the seventh "push" */
 2:	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+	.align 2
+  .endif
Quoted 8 lines

arch/x86/kernel/entry_64.S END(ret_from_fork) · line 606

Quoted 4 lines
arch/x86/kernel/entry_64.S +1 -0
+
 .endr
 	CFI_ENDPROC
 END(irq_entries_start)

So I think this might be easier to read if we went low tech and used an open-coded 240+ lines assembly file for this, with a few obvious-purpose helper macros?

I tried a few times but the results were monstrous.

#3 lore raw
In reply to Ingo Molnar
Quoted 210 lines · Ingo Molnar
Quoted 207 lines · Denys Vlasenko

Interrupt entry points are handled with the following code:
Each 32-byte code block contains seven entry points

		...
		[push][jump 22] // 4 bytes
		[push][jump 18] // 4 bytes
		[push][jump 14] // 4 bytes
		[push][jump 10] // 4 bytes
		[push][jump  6] // 4 bytes
		[push][jump  2] // 4 bytes
		[push][jump common_interrupt][padding] // 8 bytes

		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump]
		[push][jump common_interrupt][padding]

		[padding_2]
	common_interrupt:

The first six jumps are short (2-byte insns) jumps to the last jump in the block. The last jump usually has to be a longer, 5-byte form.

There are about 30 such blocks.

This change uses the fact that last few of these blocks are close to "common_interrupt" label and the last jump there can also be a short one.

This allows several last 32-byte code blocks to contain eight, not seven entry points, and to have all these entry points jump directly to common_interrupt, eliminating one branch. They look like this:

[push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes [push][jump common_interrupt] // 4 bytes

This change replaces ".p2align CONFIG_X86_L1_CACHE_SHIFT" before dispatch table and before common_interrupt with 32-byte alignment.

The first alignment was completely unnecessary:
the dispatch table will not benefit from any alignment bigger than 32 bytes (any entry point needs at most only 32 bytes of table to be read by the CPU).

The alignment before common_interrupt label affects the size of padding (the "[padding_2]" above) and excessive padding reduces the number of blocks which can be optimized. In the .config I tested with, this alignment was 64 bytes, this means two fewer blocks could be optimized. I believe 32-byte alignment should do just fine.

The condition which controls the choice of a direct jump versus short one,

    /* Can we reach common_interrupt with a short jump? */
    .if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)

was tested to be a passimistic one: the generated code will not erroneously generate a longer than necessary jump even with maximum possible padding and with -1 subtracted from the right hand side above.
This was verified by checking disassembly.

However, with current value of FIRST_SYSTEM_VECTOR it so happens that the padding before "common_interrupt" is zero bytes.

 Disassembly before                           After
 ==========================================   ==================================
...                                           ...
840 6a9b           push $0xffffffffffffff9b   82c 6a9d  push $0xffffffffffffff9d
842 eb16           jmp  85a                   82e eb30  jmp  860
844 6a9a           push $0xffffffffffffff9a   830 6a9c  push $0xffffffffffffff9c
846 eb12           jmp  85a                   832 eb2c  jmp  860
848 6a99           push $0xffffffffffffff99   834 6a9b  push $0xffffffffffffff9b
84a eb0e           jmp  85a                   836 eb28  jmp  860
84c 6a98           push $0xffffffffffffff98   838 6a9a  push $0xffffffffffffff9a
84e eb0a           jmp  85a                   83a eb24  jmp  860
850 6a97           push $0xffffffffffffff97   83c 6a99  push $0xffffffffffffff99
852 eb06           jmp  85a                   83e eb20  jmp  860
854 6a96           push $0xffffffffffffff96   840 6a98  push $0xffffffffffffff98
856 eb02           jmp  85a                   842 eb1c  jmp  860
858 6a95           push $0xffffffffffffff95   844 6a97  push $0xffffffffffffff97
85a eb24           jmp  880                   846 eb18  jmp  860
85c 0f1f4000       nopl 0x0(%rax)             848 6a96  push $0xffffffffffffff96
860 6a94           push $0xffffffffffffff94   84a eb14  jmp  860
862 eb0c           jmp  870                   84c 6a95  push $0xffffffffffffff95
864 6a93           push $0xffffffffffffff93   84e eb10  jmp  860
866 eb08           jmp  870                   850 6a94  push $0xffffffffffffff94
868 6a92           push $0xffffffffffffff92   852 eb0c  jmp  860
86a eb04           jmp  870                   854 6a93  push $0xffffffffffffff93
86c 6a91           push $0xffffffffffffff91   856 eb08  jmp  860
86e eb00           jmp  870                   858 6a92  push $0xffffffffffffff92
870 eb0e           jmp  880                   85a eb04  jmp  860

872 66666666662e0f data32 data32 data32 data3285c 6a91 push $0xffffffffffffff91 879 1f840000000000 nopw %cs:0x0(%rax,%rax,1) 85e eb00 jmp 860
880 <common_interrupt>: 860 <common_interrupt>:

Sizes:
text data bss dec hex filename

  12578	      0	      0	  12578	   3122	entry_64.o.before
  12546	      0	      0	  12546	   3102	entry_64.o
CC Linus Torvalds <[email protected]>
CC Steven Rostedt <[email protected]>
CC Ingo Molnar <[email protected]>
CC Borislav Petkov <[email protected]>
CC "H. Peter Anvin" <[email protected]>
CC Andy Lutomirski <[email protected]>
CC Oleg Nesterov <[email protected]>
CC Frederic Weisbecker <[email protected]>
CC Alexei Starovoitov <[email protected]>
CC Will Drewry <[email protected]>
CC Kees Cook <[email protected]>
---
 arch/x86/kernel/entry_64.S | 61 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 49 insertions(+), 12 deletions(-)
arch/x86/kernel/entry_64.S +48 -11
index da137f9..2003417 100644
@@ -537,33 +537,70 @@ END(ret_from_fork)
  * Build the entry stubs and pointer table with some assembler magic.
  * We pack 7 stubs into a single 32-byte chunk, which will fit in a
  * single cache line on all modern x86 implementations.
+ * The last few cachelines pack 8 stubs each.
  */
+ALIGN_common_interrupt=32
 	.section .init.rodata,"a"
 ENTRY(interrupt)
 	.section .entry.text
-	.p2align 5
-	.p2align CONFIG_X86_L1_CACHE_SHIFT
+	.align 32
 ENTRY(irq_entries_start)
 	INTR_FRAME
 vector=FIRST_EXTERNAL_VECTOR
-.rept (FIRST_SYSTEM_VECTOR-FIRST_EXTERNAL_VECTOR+6)/7
-	.balign 32
+.rept 256 /* this number does not need to be exact, just big enough */
+
+  /*
+   * Block of six "push + short_jump" pairs, 4 bytes each,
+   * and a 2-byte seventh "push", without its jump yet.
+   */
+need_near_jump=0
+push_count=0
   .rept	7
     .if vector < FIRST_SYSTEM_VECTOR
-      .if vector <> FIRST_EXTERNAL_VECTOR
+1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
+	.previous
+	.quad 1b
+	.section .entry.text
+vector=vector+1
+push_count=push_count+1
+      .if push_count < 7
+	/* Can we reach common_interrupt with a short jump? */
+	.if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)
+	  jmp common_interrupt  /* yes */
+	.else
+	  jmp 2f
+need_near_jump=1
+	.endif
 	CFI_ADJUST_CFA_OFFSET -8
       .endif
+    .endif
+  .endr
+
+  /* If we are close to the end, we can pack in yet another pair */
+  .if need_near_jump == 0
+    .if push_count == 7
+	/* The "short jump" for the seventh "push" */
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+    .endif
+    .if vector < FIRST_SYSTEM_VECTOR
+	/* "push + short_jump" pair #8 */
 1:	pushq_cfi $(~vector+0x80)	/* Note: always in signed byte range */
-      .if ((vector-FIRST_EXTERNAL_VECTOR)%7) <> 6
-	jmp 2f
-      .endif
-      .previous
+	.previous
 	.quad 1b
-      .section .entry.text
+	.section .entry.text
 vector=vector+1
+push_count=push_count+1
+	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
     .endif
-  .endr
+  .else
+	/* Use remaining space for "near jump" for the seventh "push" */
 2:	jmp common_interrupt
+	CFI_ADJUST_CFA_OFFSET -8
+	.align 2
+  .endif
+
Quoted 8 lines

arch/x86/kernel/entry_64.S END(ret_from_fork) · line 606

Quoted 3 lines
arch/x86/kernel/entry_64.S +0 -0
 .endr
 	CFI_ENDPROC
 END(irq_entries_start)

So I think this might be easier to read if we went low tech and used an open-coded 240+ lines assembly file for this, with a few obvious-purpose helper macros? It's not like it will change all that often so it only has to be generated once.

How about this version?
It's still isn't a star of readability,
but the structure of the 32-byte code block is more visible now...

/*
* Build the entry stubs and pointer table with some assembler magic.
* We pack 7 stubs into a single 32-byte chunk, which will fit in a
* single cache line on all modern x86 implementations.
* The last few cachelines pack 8 stubs each.
*/
ALIGN_common_interrupt=32
.section .init.rodata,"a"
ENTRY(interrupt)

	.section .entry.text
	.align 32

ENTRY(irq_entries_start)
INTR_FRAME

.macro push_vector
.if vector < FIRST_SYSTEM_VECTOR
1: pushq_cfi $(~vector+0x80) /* Note: always in signed byte range */
.previous
.quad 1b
.section .entry.text
need_jump=1
vector=vector+1

    .endif
	.endm

	.macro short_jump label
    .if need_jump == 1
	/* Can we reach common_interrupt with a short jump? */
    .if vector >= (FIRST_SYSTEM_VECTOR - (128-ALIGN_common_interrupt)/4)
	jmp	common_interrupt  /* yes */
    .else
	jmp	\label

need_near_jump=1
.endif
CFI_ADJUST_CFA_OFFSET -8
need_jump=0
.endif
.endm

.macro near_jump label
jmp \label
CFI_ADJUST_CFA_OFFSET -8
.endm

vector=FIRST_EXTERNAL_VECTOR
.rept 256 /* this number does not need to be exact, just big enough */ need_near_jump=0
push_vector; short_jump 2f
push_vector; short_jump 2f
push_vector; short_jump 2f
push_vector; short_jump 2f
push_vector; short_jump 2f
push_vector; short_jump 2f
.if need_near_jump == 1
push_vector; 2: near_jump common_interrupt; .align 2
.else
push_vector; short_jump common_interrupt push_vector; short_jump common_interrupt
.endif
.endr
CFI_ENDPROC
END(irq_entries_start)

.previous
END(interrupt)
.previous

#4 lore raw
Quoted 4 lines · Denys Vlasenko

How about this version?
It's still isn't a star of readability,
but the structure of the 32-byte code block is more visible now...

Do we really even want to be this clever in the first place?

The thing is, when we take an interrupt:

(a) the L1 I$ is always cold

(b) the instruction decoder has never had time to run ahead

(c) there are usually not that many different interrupts anyway, even
under load (ie you'd have maybe disk and networking)

(d) we intentionally spread out the different interrupt vector numbers

(e) the 32-byte block thing is questionable, most older
micro-architectures fetch in 16-byte blocks iirc.

So what this tells me is that:

- (a+b) the jump-to-jump is likely fairly expensive, because even
though they are in the same cacheline, the front end hasn't gotten ahead of anything, so there's no hiding any front end pipeline hickups.

- (c+d) there is likely very little advantage to trying to "pack"
things in cachelines

- (d+e) the 7-instructions-in-one-32-byte-block doesn't really sound
all that big of a win, and it does cause a 16-byte split for some interrupt.

In other words, I'd suggest that we just use simple unconditional 5-byte branch instead. Add the two-byte "push" instruction, you have 7 bytes per interrupt. Align that 7 bytes up to 8, and none of them ever cross a 16-byte boundary.

Simple, clean, and slightly bigger in memory footprint, but probably not noticeably more so in cache footprint, simply because there usually aren't that many active interrupts anyway.

The people who do millions of networking interrupts per second and have network cards that steer things to many different interrupts already try to make sure that the steering goes to different CPU's - otherwise there wouldn't be any *point* to steering things. So that particular case of "lots of active interrupts" doesn't have a bigger cache footprint *either*, since any particular CPU L1 I$ will still only handle a few interrupts.

So you get "only" 4 interrupt cases per 32 bytes rather than 7. But is that odd double jump and all this complexity really worth it?

So I really suggest just doing something stupid and straightforward (and completely untested) like this:

    .macro push_vector
        pushq_cfi $(~vector+0x80)
        jmp common_interrupt
        .align 8
    .endm

    vector=FIRST_EXTERNAL_VECTOR
    .align 64
    ENTRY(irq_entries_start)
    .rept 256 /* this number does not need to be exact, just big enough */
         make_vector
    .endr

and just be done with it.

(Of course, you have to change the code that knows about the "7 entries in 32 bytes" patterns too, but that's just going to be much simpler now).

Linus

#5 lore raw
Quoted 14 lines · Linus Torvalds
Quoted 4 lines · Denys Vlasenko

How about this version?
It's still isn't a star of readability,
but the structure of the 32-byte code block is more visible now...

Do we really even want to be this clever in the first place?

The thing is, when we take an interrupt:

(a) the L1 I$ is always cold

(b) the instruction decoder has never had time to run ahead

Quoted 8 lines

(c) there are usually not that many different interrupts anyway, even
under load (ie you'd have maybe disk and networking)

(d) we intentionally spread out the different interrupt vector numbers

(e) the 32-byte block thing is questionable, most older
micro-architectures fetch in 16-byte blocks iirc.

For the record, I actually measured the impact of the jump-to-jump when I wrote it. It has a small, *but measurable*, positive impact.

-hpa

#6 lore raw
Quoted 3 lines · H. Peter Anvin

For the record, I actually measured the impact of the jump-to-jump when I wrote it. It has a small, *but measurable*, positive impact.

What did you compare against, and how did you measure that? I don't see how it could *possibly* be faster than just a simple aligned "push
+ jmp".

Linus

#7 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 3 lines · H. Peter Anvin

For the record, I actually measured the impact of the jump-to-jump when I wrote it. It has a small, *but measurable*, positive impact.

What did you compare against, and how did you measure that? I don't see how it could *possibly* be faster than just a simple aligned "push
+ jmp".

I wish I remembered the exact details; it took a fair bit of gathering numbers as the spread was quite a bit wider than the delta, but in the end there were two distribution peaks clearly offset.

I seem to remember it involving a loop running RDTSC continuously and another RDTSC in the interrupt path.

-hpa

#8 lore raw
Quoted 11 lines · H. Peter Anvin
Quoted 9 lines · Linus Torvalds
Quoted 3 lines · H. Peter Anvin

For the record, I actually measured the impact of the jump-to-jump when I wrote it. It has a small, *but measurable*, positive impact.

What did you compare against, and how did you measure that? I don't see how it could *possibly* be faster than just a simple aligned "push
+ jmp".

Quoted 6 lines

I wish I remembered the exact details; it took a fair bit of gathering numbers as the spread was quite a bit wider than the delta, but in the end there were two distribution peaks clearly offset.

I seem to remember it involving a loop running RDTSC continuously and another RDTSC in the interrupt path.

So the thing is, while I don't know how you've loaded the machine, if user-space is doing nothing but looping in RDTSC, the kernel I$ might become cache hot easily not just in L2 but in L1 cache as well.

But 'when the machine is not doing anything' is not what we optimize for, we (try to) optimize for the case when there's a lot of work going on and the async context (irq, fault, etc.) I$ is likely cache-cold.

Thanks,

Ingo

#9 lore raw
In reply to Linus Torvalds
Quoted 24 lines · Linus Torvalds
Quoted 4 lines · Denys Vlasenko

How about this version?
It's still isn't a star of readability,
but the structure of the 32-byte code block is more visible now...

Do we really even want to be this clever in the first place?

The thing is, when we take an interrupt:

(a) the L1 I$ is always cold

(b) the instruction decoder has never had time to run ahead

(c) there are usually not that many different interrupts anyway, even
under load (ie you'd have maybe disk and networking)

(d) we intentionally spread out the different interrupt vector numbers

(e) the 32-byte block thing is questionable, most older
micro-architectures fetch in 16-byte blocks iirc.

So what this tells me is that:

Quoted 7 lines

- (a+b) the jump-to-jump is likely fairly expensive, because even
though they are in the same cacheline, the front end hasn't gotten ahead of anything, so there's no hiding any front end pipeline hickups.

- (c+d) there is likely very little advantage to trying to "pack"
things in cachelines

Good points.

Quoted 3 lines

- (d+e) the 7-instructions-in-one-32-byte-block doesn't really sound
all that big of a win, and it does cause a 16-byte split for some interrupt.

No, this doesn't happen. With current code, none of instructions cross 16-byte split. Even 8-byte boundary is never crossed.

Quoted 36 lines

In other words, I'd suggest that we just use simple unconditional 5-byte branch instead. Add the two-byte "push" instruction, you have 7 bytes per interrupt. Align that 7 bytes up to 8, and none of them ever cross a 16-byte boundary.

Simple, clean, and slightly bigger in memory footprint, but probably not noticeably more so in cache footprint, simply because there usually aren't that many active interrupts anyway.

The people who do millions of networking interrupts per second and have network cards that steer things to many different interrupts already try to make sure that the steering goes to different CPU's - otherwise there wouldn't be any *point* to steering things. So that particular case of "lots of active interrupts" doesn't have a bigger cache footprint *either*, since any particular CPU L1 I$ will still only handle a few interrupts.

So you get "only" 4 interrupt cases per 32 bytes rather than 7. But is that odd double jump and all this complexity really worth it?

So I really suggest just doing something stupid and straightforward (and completely untested) like this:

    .macro push_vector
        pushq_cfi $(~vector+0x80)
        jmp common_interrupt
        .align 8
    .endm

    vector=FIRST_EXTERNAL_VECTOR
    .align 64
    ENTRY(irq_entries_start)
    .rept 256 /* this number does not need to be exact, just big enough */
         make_vector
    .endr
Quoted 5 lines

and just be done with it.

(Of course, you have to change the code that knows about the "7 entries in 32 bytes" patterns too, but that's just going to be much simpler now).

I'll send a patch in ~30 minutes.