Skip to contentSkip to conversation

Documentation: x86: exception-tables: document CONFIG_BUILDTIME_TABLE_SORT

PATCH Superseded Nick Desaulniers 3 participants 4 messages Mar 23, 2020 – Mar 27, 2020 Documentation

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Documentation: x86: exception-tables: document CONFIG_BUILDTIME_TABLE_SORT

Provide more information about __ex_table sorting post link.

The exception tables and fixup tables use a commonly recurring pattern in the kernel of storing the address of labels as date in custom ELF sections, then finding these sections, iterating elements within them, and possibly revisiting them or modifying the data at these addresses.

Sorting readonly arrays to minimize runtime penalties is quite clever.

---
 Documentation/x86/exception-tables.rst | 9 +++++++++
 1 file changed, 9 insertions(+)
Documentation/x86/exception-tables.rst +9 -0
index ed6d4b0cf62c..15455b2f7ba8 100644
@@ -257,6 +257,9 @@ the fault, in our case the actual value is c0199ff5:
 the original assembly code: > 3:      movl $-14,%eax
 and linked in vmlinux     : > c0199ff5 <.fixup+10b5> movl   $0xfffffff2,%eax
 
+If the fixup was able to handle the exception, control flow may be returned
+to the instruction after the one that triggered the fault, ie. local label 2b.
+
 The assembly code::
 
  > .section __ex_table,"a"
@@ -344,3 +347,9 @@ pointer which points to one of:
      it as special.
 
 More functions can easily be added.
+
+CONFIG_BUILDTIME_TABLE_SORT allows the __ex_table section to be sorted post
+link of the kernel image, via a host utility scripts/sorttable. It will set the
+symbol main_extable_sort_needed to 0, avoiding sorting the __ex_table section
+at boot time. With the exception table sorted, at runtime when an exception
+occurs we can quickly lookup the __ex_table entry via binary search.
Signature · 1 line
2.25.1.696.g5e7596f4ac-goog
#1 lore raw
Quoted 30 lines · Nick Desaulniers

Provide more information about __ex_table sorting post link.

The exception tables and fixup tables use a commonly recurring pattern in the kernel of storing the address of labels as date in custom ELF sections, then finding these sections, iterating elements within them, and possibly revisiting them or modifying the data at these addresses.

Sorting readonly arrays to minimize runtime penalties is quite clever.

---
 Documentation/x86/exception-tables.rst | 9 +++++++++
 1 file changed, 9 insertions(+)
Documentation/x86/exception-tables.rst +3 -0
index ed6d4b0cf62c..15455b2f7ba8 100644
@@ -257,6 +257,9 @@ the fault, in our case the actual value is c0199ff5:
 the original assembly code: > 3:      movl $-14,%eax
 and linked in vmlinux     : > c0199ff5 <.fixup+10b5> movl   $0xfffffff2,%eax
 
+If the fixup was able to handle the exception, control flow may be returned
+to the instruction after the one that triggered the fault, ie. local label 2b.
+
 The assembly code::
 
  > .section __ex_table,"a"

Documentation/x86/exception-tables.rst pointer which points to one of: · line 355

Quoted 9 lines
Documentation/x86/exception-tables.rst +6 -0
@@ -344,3 +347,9 @@ pointer which points to one of:
      it as special.
 
 More functions can easily be added.
+
+CONFIG_BUILDTIME_TABLE_SORT allows the __ex_table section to be sorted post
+link of the kernel image, via a host utility scripts/sorttable. It will set the
+symbol main_extable_sort_needed to 0, avoiding sorting the __ex_table section
+at boot time. With the exception table sorted, at runtime when an exception
+occurs we can quickly lookup the __ex_table entry via binary search.

It is more than that. It not only saves the boot execution time needed to sort the table, but it is required for early exception handling to work -- and in the x86 code, we use the exception handling *extremely* early (on i386 before paging is even turned on!), long before the kernel would have had any opportunity to sort it.

So it is not just performance; it is also a correctness issue.

-hpa

#2 lore raw

PATCH v2 1/1 Documentation: x86: exception-tables: document CONFIG_BUILDTIME_TABLE_SORT

Provide more information about __ex_table sorting post link.

The exception tables and fixup tables use a commonly recurring pattern in the kernel of storing the address of labels as date in custom ELF sections, then finding these sections, iterating elements within them, and possibly revisiting them or modifying the data at these addresses.

Sorting readonly arrays to minimize runtime penalties is quite clever.

---
Changes V1 -> V2:
* Add Peter's note about early exception handling (final paragraph).

 Documentation/x86/exception-tables.rst | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
Documentation/x86/exception-tables.rst +14 -0
index ed6d4b0cf62c..81a393867f10 100644
@@ -257,6 +257,9 @@ the fault, in our case the actual value is c0199ff5:
 the original assembly code: > 3:      movl $-14,%eax
 and linked in vmlinux     : > c0199ff5 <.fixup+10b5> movl   $0xfffffff2,%eax
 
+If the fixup was able to handle the exception, control flow may be returned
+to the instruction after the one that triggered the fault, ie. local label 2b.
+
 The assembly code::
 
  > .section __ex_table,"a"
@@ -344,3 +347,14 @@ pointer which points to one of:
      it as special.
 
 More functions can easily be added.
+
+CONFIG_BUILDTIME_TABLE_SORT allows the __ex_table section to be sorted post
+link of the kernel image, via a host utility scripts/sorttable. It will set the
+symbol main_extable_sort_needed to 0, avoiding sorting the __ex_table section
+at boot time. With the exception table sorted, at runtime when an exception
+occurs we can quickly lookup the __ex_table entry via binary search.
+
+This is not just a boot time optimization, some architectures require this
+table to be sorted in order to handle exceptions relatively early in the boot
+process. For example, i386 makes use of this form of exception handling before
+paging support is even enabled!
Signature · 1 line
2.26.0.rc2.310.g2932bb562d-goog
maintainer Applied
#3 lore raw
Quoted 11 lines · On Thu, 26 Mar 2020 17:09:51 -0700 Nick Desaulniers <[email protected]>…

Provide more information about __ex_table sorting post link.

The exception tables and fixup tables use a commonly recurring pattern in the kernel of storing the address of labels as date in custom ELF sections, then finding these sections, iterating elements within them, and possibly revisiting them or modifying the data at these addresses.

Sorting readonly arrays to minimize runtime penalties is quite clever.

I've applied this, thanks.

jon