x86: undwarf unwinder

This is a major rewrite of objtool. Instead of only tracking frame pointer changes, it now tracks all stack-related operations, including all register saves/restores.

In addition to making stack validation more robust, this also paves the way for undwarf generation.

Signed-off-by Josh Poimboeuf <[email protected]>

Quoted 8 lines · Josh Poimboeuf

This is a major rewrite of objtool. Instead of only tracking frame pointer changes, it now tracks all stack-related operations, including all register saves/restores.

In addition to making stack validation more robust, this also paves the way for undwarf generation.

Signed-off-by Josh Poimboeuf <[email protected]>

Note, I have applied the first 3 patches, and got a bunch of new warnings on x86 64-bit allmodconfig:

arch/x86/kernel/alternative.o: warning: objtool: do_sync_core()+0x1b: unsupported instruction in callable function arch/x86/kernel/alternative.o: warning: objtool: text_poke()+0x1a8: unsupported instruction in callable function arch/x86/kernel/ftrace.o: warning: objtool: do_sync_core()+0x16: unsupported instruction in callable function arch/x86/kernel/cpu/mcheck/mce.o: warning: objtool: machine_check_poll()+0x166: unsupported instruction in callable function arch/x86/kernel/cpu/mcheck/mce.o: warning: objtool: do_machine_check()+0x147: unsupported instruction in callable function

(That's the vmlinux build - plus 4 more warnings in the modules build.)

That's with GCC 5.3.1.

Let me know if you need any more info.

Quoted 23 lines · Ingo Molnar

Quoted 8 lines · Josh Poimboeuf

This is a major rewrite of objtool. Instead of only tracking frame pointer changes, it now tracks all stack-related operations, including all register saves/restores.

In addition to making stack validation more robust, this also paves the way for undwarf generation.

Signed-off-by Josh Poimboeuf <[email protected]>

Note, I have applied the first 3 patches, and got a bunch of new warnings on x86 64-bit allmodconfig:

arch/x86/kernel/alternative.o: warning: objtool: do_sync_core()+0x1b: unsupported instruction in callable function arch/x86/kernel/alternative.o: warning: objtool: text_poke()+0x1a8: unsupported instruction in callable function arch/x86/kernel/ftrace.o: warning: objtool: do_sync_core()+0x16: unsupported instruction in callable function arch/x86/kernel/cpu/mcheck/mce.o: warning: objtool: machine_check_poll()+0x166: unsupported instruction in callable function arch/x86/kernel/cpu/mcheck/mce.o: warning: objtool: do_machine_check()+0x147: unsupported instruction in callable function

(That's the vmlinux build - plus 4 more warnings in the modules build.)

Quoted 3 lines

That's with GCC 5.3.1.

Let me know if you need any more info.

Hm, this is odd. I tried with GCC 5.3.0 (which should presumably be almost identical to 5.3.1) and I don't see any warnings. Can you send me one of the object files it's complaining about?

Quoted 8 lines · Josh Poimboeuf

This is a major rewrite of objtool. Instead of only tracking frame pointer changes, it now tracks all stack-related operations, including all register saves/restores.

In addition to making stack validation more robust, this also paves the way for undwarf generation.

Signed-off-by Josh Poimboeuf <[email protected]>

Note, I have applied the first 3 patches, and got a bunch of new warnings on x86 64-bit allmodconfig:

arch/x86/kernel/alternative.o: warning: objtool: do_sync_core()+0x1b: unsupported instruction in callable function arch/x86/kernel/alternative.o: warning: objtool: text_poke()+0x1a8: unsupported instruction in callable function arch/x86/kernel/ftrace.o: warning: objtool: do_sync_core()+0x16: unsupported instruction in callable function arch/x86/kernel/cpu/mcheck/mce.o: warning: objtool: machine_check_poll()+0x166: unsupported instruction in callable function arch/x86/kernel/cpu/mcheck/mce.o: warning: objtool: do_machine_check()+0x147: unsupported instruction in callable function

(That's the vmlinux build - plus 4 more warnings in the modules build.)

That's with GCC 5.3.1.

Now that objtool knows the states of all registers on the stack for each instruction, it's straightforward to generate debuginfo for an unwinder to use.

Instead of generating DWARF, generate a new format called undwarf, which is more suitable for an in-kernel unwinder. See tools/objtool/Documentation/undwarf.txt for a more detailed description of this new debuginfo format and why it's preferable to DWARF.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 tools/objtool/Build                              |   3 +
 tools/objtool/Documentation/stack-validation.txt |  46 ++---
 tools/objtool/builtin-check.c                    |   2 +-
 tools/objtool/builtin-undwarf.c                  |  70 ++++++++
 tools/objtool/builtin.h                          |   1 +
 tools/objtool/check.c                            |  59 ++++++-
 tools/objtool/check.h                            |  15 +-
 tools/objtool/elf.c                              | 212 ++++++++++++++++++++--
 tools/objtool/elf.h                              |  15 +-
 tools/objtool/objtool.c                          |   3 +-
 tools/objtool/undwarf-types.h                    |  81 +++++++++

Quoted 10 lines · Josh Poimboeuf

Now that objtool knows the states of all registers on the stack for each instruction, it's straightforward to generate debuginfo for an unwinder to use.

Instead of generating DWARF, generate a new format called undwarf, which is more suitable for an in-kernel unwinder. See tools/objtool/Documentation/undwarf.txt for a more detailed description of this new debuginfo format and why it's preferable to DWARF.

Signed-off-by Josh Poimboeuf <[email protected]>

Quoted 12 lines

---
 tools/objtool/Build                              |   3 +
 tools/objtool/Documentation/stack-validation.txt |  46 ++---
 tools/objtool/builtin-check.c                    |   2 +-
 tools/objtool/builtin-undwarf.c                  |  70 ++++++++
 tools/objtool/builtin.h                          |   1 +
 tools/objtool/check.c                            |  59 ++++++-
 tools/objtool/check.h                            |  15 +-
 tools/objtool/elf.c                              | 212 ++++++++++++++++++++--
 tools/objtool/elf.h                              |  15 +-
 tools/objtool/objtool.c                          |   3 +-
 tools/objtool/undwarf-types.h                    |  81 +++++++++

Just a very quick stylistic suggestion: please name the header 'undwarf_types.h' (note the underscore versus hyphen), which is the common naming pattern used in the kernel.

tools/objtool/undwarf-types.h new file +52 -0

+#ifndef _UNDWARF_TYPES_H
+#define _UNDWARF_TYPES_H
+
+/*
+ * The UNDWARF_REG_* registers are base registers which are used to find other
+ * registers on the stack.
+ *
+ * The CFA (call frame address) is the value of the stack pointer on the
+ * previous frame, i.e. the caller's SP before it called the callee.
+ *
+ * The CFA is usually based on SP, unless a frame pointer has been saved, in
+ * which case it's based on BP.
+ *
+ * BP is usually either based on CFA or is undefined (meaning its value didn't
+ * change for the current frame).
+ *
+ * So the CFA base is usually either SP or BP, and the FP base is usually either
+ * CFA or undefined.  The rest of the base registers are needed for special
+ * cases like entry code and gcc aligned stacks.
+ */
+#define UNDWARF_REG_UNDEFINED		0
+#define UNDWARF_REG_CFA			1
+#define UNDWARF_REG_DX			2
+#define UNDWARF_REG_DI			3
+#define UNDWARF_REG_BP			4
+#define UNDWARF_REG_SP			5
+#define UNDWARF_REG_R10			6
+#define UNDWARF_REG_R13			7
+#define UNDWARF_REG_BP_INDIRECT		8
+#define UNDWARF_REG_SP_INDIRECT		9
+#define UNDWARF_REG_MAX			15
+
+/*
+ * UNDWARF_TYPE_CFA: Indicates that cfa_reg+cfa_offset points to the caller's
+ * stack pointer (aka the CFA in DWARF terms).  Used for all callable
+ * functions, i.e.  all C code and all callable asm functions.
+ *
+ * UNDWARF_TYPE_REGS: Used in entry code to indicate that cfa_reg+cfa_offset
+ * points to a fully populated pt_regs from a syscall, interrupt, or exception.
+ *
+ * UNDWARF_TYPE_REGS_IRET: Used in entry code to indicate that
+ * cfa_reg+cfa_offset points to the iret return frame.
+ */
+#define UNDWARF_TYPE_CFA		0
+#define UNDWARF_TYPE_REGS		1
+#define UNDWARF_TYPE_REGS_IRET		2
+
+/*
+ * This struct contains a simplified version of the DWARF Call Frame
+ * Information standard.  It contains only the necessary parts of the real
+ * DWARF, simplified for ease of access by the in-kernel unwinder.  It tells
+ * the unwinder how to find the previous SP and BP (and sometimes entry regs)

Quoted 5 lines

tools/objtool/undwarf-types.h new file +5 -0

+/*
+ * This struct contains a simplified version of the DWARF Call Frame
+ * Information standard.  It contains only the necessary parts of the real
+ * DWARF, simplified for ease of access by the in-kernel unwinder.  It tells
+ * the unwinder how to find the previous SP and BP (and sometimes entry regs)

tools/objtool/undwarf-types.h line 79

Quoted 10 lines

tools/objtool/undwarf-types.h new file +10 -0

+ * on the stack for a given code address (IP).  Each instance of the struct
+ * corresponds to one or more code locations.
+ */
+struct undwarf {
+	short cfa_offset;
+	short bp_offset;
+	unsigned cfa_reg:4;
+	unsigned bp_reg:4;
+	unsigned type:2;
+};

I never know straight away what 'CFA' stands for - could we please use natural names, i.e. something like:

struct undwarf {
	u16		sp_offset;
	u16		bp_offset;
	unsigned	sp_reg:4;
	unsigned	bp_reg:4;
	unsigned	type:2;
};

...

struct unwind_hint {
	u32		ip;
	u16		sp_offset;
	u8		sp_reg;
	u8		type;
};

?

Also note the slightly cleaner vertical alignment, plus the conversion to more stable data types: I believe various bits of tooling (perf and so) will eventually learn about undwarf, so having a well defined cross-arch data structure is probably of advantage.

Since we are not bound by DWARF anymore, we might as well use readable names and such?

Plus, shouldn't we use __packed for 'struct undwarf' to minimize the structure's size (to 6 bytes AFAICS?) - or is optimal packing of the main undwarf array already guaranteed on every platform with this layout?

Quoted 3 lines

Plus, shouldn't we use __packed for 'struct undwarf' to minimize the structure's size (to 6 bytes AFAICS?) - or is optimal packing of the main undwarf array already guaranteed on every platform with this layout?

Ah yes, it should definitely be packed (assuming that doesn't affect performance negatively).

Quoted 4 lines · Josh Poimboeuf

Quoted 3 lines

Plus, shouldn't we use __packed for 'struct undwarf' to minimize the structure's size (to 6 bytes AFAICS?) - or is optimal packing of the main undwarf array already guaranteed on every platform with this layout?

Quoted 2 lines

Ah yes, it should definitely be packed (assuming that doesn't affect performance negatively).

So if I count that correctly that should shave another ~1MB off a typical ~4MB table size?

Quoted 7 lines · Ingo Molnar

Quoted 4 lines · Josh Poimboeuf

Quoted 3 lines

Plus, shouldn't we use __packed for 'struct undwarf' to minimize the structure's size (to 6 bytes AFAICS?) - or is optimal packing of the main undwarf array already guaranteed on every platform with this layout?

Quoted 5 lines

Quoted 2 lines

Ah yes, it should definitely be packed (assuming that doesn't affect performance negatively).

So if I count that correctly that should shave another ~1MB off a typical ~4MB table size?

Here's what my Fedora kernel looks like *before* the packed change:

  $ eu-readelf -S vmlinux |grep undwarf
  [15] .undwarf_ip          PROGBITS     ffffffff81f776d0 011776d0 0012d9d0  0 A      0   0  1
  [16] .undwarf             PROGBITS     ffffffff820a50a0 012a50a0 0025b3a0  0 A      0   0  1

The total undwarf data size is ~3.5MB.

There are 308852 entries of two parallel arrays:

* .undwarf (8 bytes/entry) = 2470816 bytes
* .undwarf_ip (4 bytes/entry) = 1235408 bytes

If we pack undwarf, reducing the size of the .undwarf entries by two bytes, it will save 308852 * 2 = 617704.

So the savings will be ~600k, and the typical size will be reduced to ~3MB.

Quoted 27 lines · Josh Poimboeuf

Quoted 7 lines · Ingo Molnar

Quoted 4 lines · Josh Poimboeuf

Quoted 3 lines

Plus, shouldn't we use __packed for 'struct undwarf' to minimize the structure's size (to 6 bytes AFAICS?) - or is optimal packing of the main undwarf array already guaranteed on every platform with this layout?

Quoted 5 lines

Quoted 2 lines

Ah yes, it should definitely be packed (assuming that doesn't affect performance negatively).

So if I count that correctly that should shave another ~1MB off a typical ~4MB table size?

Here's what my Fedora kernel looks like *before* the packed change:

  $ eu-readelf -S vmlinux |grep undwarf
  [15] .undwarf_ip          PROGBITS     ffffffff81f776d0 011776d0 0012d9d0  0 A      0   0  1
  [16] .undwarf             PROGBITS     ffffffff820a50a0 012a50a0 0025b3a0  0 A      0   0  1

The total undwarf data size is ~3.5MB.

There are 308852 entries of two parallel arrays:

* .undwarf (8 bytes/entry) = 2470816 bytes
* .undwarf_ip (4 bytes/entry) = 1235408 bytes

Quoted 4 lines

If we pack undwarf, reducing the size of the .undwarf entries by two bytes, it will save 308852 * 2 = 617704.

So the savings will be ~600k, and the typical size will be reduced to ~3MB.

Just for the record, while packing the struct from 8 to 6 bytes did save 600k, it also made the unwinder ~7% slower. I think that's probably an ok tradeoff, so I'll leave it packed in v3.

Quoted 28 lines · Josh Poimboeuf

Quoted 27 lines · Josh Poimboeuf

Quoted 7 lines · Ingo Molnar

Quoted 4 lines · Josh Poimboeuf

Quoted 3 lines

Plus, shouldn't we use __packed for 'struct undwarf' to minimize the structure's size (to 6 bytes AFAICS?) - or is optimal packing of the main undwarf array already guaranteed on every platform with this layout?

Quoted 5 lines

Quoted 2 lines

Ah yes, it should definitely be packed (assuming that doesn't affect performance negatively).

So if I count that correctly that should shave another ~1MB off a typical ~4MB table size?

Here's what my Fedora kernel looks like *before* the packed change:

  $ eu-readelf -S vmlinux |grep undwarf
  [15] .undwarf_ip          PROGBITS     ffffffff81f776d0 011776d0 0012d9d0  0 A      0   0  1
  [16] .undwarf             PROGBITS     ffffffff820a50a0 012a50a0 0025b3a0  0 A      0   0  1

The total undwarf data size is ~3.5MB.

There are 308852 entries of two parallel arrays:

* .undwarf (8 bytes/entry) = 2470816 bytes
* .undwarf_ip (4 bytes/entry) = 1235408 bytes

Quoted 8 lines

Quoted 4 lines

If we pack undwarf, reducing the size of the .undwarf entries by two bytes, it will save 308852 * 2 = 617704.

So the savings will be ~600k, and the typical size will be reduced to ~3MB.

Just for the record, while packing the struct from 8 to 6 bytes did save 600k, it also made the unwinder ~7% slower. I think that's probably an ok tradeoff, so I'll leave it packed in v3.

So, out of curiosity, I'm wondering where that slowdown comes from: on modern x86 CPUs indexing by units of 6 bytes ought to be just as fast as indexing by 8 bytes, unless I'm missing something? Is it maybe the not naturally aligned 32-bit words?

Or maybe there's some bad case of a 32-bit word crossing a 64-byte cache line boundary that hits some pathological aspect of the CPU? We could probably get around any such problems by padding by 2 bytes on 64-byte boundaries - that's only a ~3% data size increase. The flip side would be a complication of the data structure and its accessors - which might cost more in terms of code generation efficiency than it buys us to begin with ...

Also, there's another aspect besides RAM footprint: a large data structure that is ~20% smaller means 20% less cache footprint: which for cache cold lookups might matter more than the direct computational cost.

Anyway, I used some linker magic to temporarily move the unwinder code to the end of .text, so that unwinder changes don't add unexpected side effects to the microbenchmark behavior. Now I'm getting more consistent results: the packed struct is measuring ~2% slower. The slight slowdown might just be explained by the fact that GCC generates some extra instructions for extracting the fields out of the packed struct.

In the meantime, I found a ~10% speedup by making the "fast lookup table" block size a power-of-two (256) to get rid of the need for a slow 'div' instruction.

I think I'm done performance tweaking for now. I'll keep the packed struct, and add the code for the 'div' removal, and hope to submit v3 soon.

There's a bug here that will need a small change to the entry code.

Mike Galbraith reported:

WARNING: can't dereference registers at ffffc900089d7e08 for ip ffffffff81740bbb

After some looking I found that it's caused by the following code snippet in the 'interrupt' macro in entry_64.S:

/*
* Save previous stack pointer, optionally switch to interrupt stack.
* irq_count is used to check if a CPU is already on an interrupt stack
* or not. While this is essentially redundant with preempt_count it is
* a little cheaper to use a separate counter in the PDA (short of
* moving irq_enter into assembly, which would be too much work) */
movq %rsp, %rdi
incl PER_CPU_VAR(irq_count)
cmovzq PER_CPU_VAR(irq_stack_ptr), %rsp
UNWIND_HINT_REGS base=rdi
pushq %rdi
UNWIND_HINT_REGS indirect=1

The problem is that it's changing the stack pointer *before* writing the previous stack pointer (push %rdi). So when unwinding from an NMI which hit between the rsp write and the rdi push, the unwinder tries to access the regs on the previous stack (by reading rdi), but the previous stack pointer isn't there yet, so the access is considered out of bounds.

Quoted 23 lines · Josh Poimboeuf

There's a bug here that will need a small change to the entry code.

Mike Galbraith reported:

WARNING: can't dereference registers at ffffc900089d7e08 for ip ffffffff81740bbb

After some looking I found that it's caused by the following code snippet in the 'interrupt' macro in entry_64.S:

/*
* Save previous stack pointer, optionally switch to interrupt stack.
* irq_count is used to check if a CPU is already on an interrupt stack
* or not. While this is essentially redundant with preempt_count it is
* a little cheaper to use a separate counter in the PDA (short of
* moving irq_enter into assembly, which would be too much work) */
movq %rsp, %rdi
incl PER_CPU_VAR(irq_count)
cmovzq PER_CPU_VAR(irq_stack_ptr), %rsp
UNWIND_HINT_REGS base=rdi
pushq %rdi
UNWIND_HINT_REGS indirect=1

Quoted 5 lines

The problem is that it's changing the stack pointer *before* writing the previous stack pointer (push %rdi). So when unwinding from an NMI which hit between the rsp write and the rdi push, the unwinder tries to access the regs on the previous stack (by reading rdi), but the previous stack pointer isn't there yet, so the access is considered out of bounds.

Ugh, that code. Does this problem go away with this patch applied:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_ist&id=2231ec7e0bcc1a2bc94a17081511ab54cc6badd1

If so, want to update the patch for new kernels (shouldn't conflict with anything except your unwind hints)?

Quoted 32 lines · Andy Lutomirski

Quoted 23 lines · Josh Poimboeuf

There's a bug here that will need a small change to the entry code.

Mike Galbraith reported:

WARNING: can't dereference registers at ffffc900089d7e08 for ip ffffffff81740bbb

After some looking I found that it's caused by the following code snippet in the 'interrupt' macro in entry_64.S:

/*
* Save previous stack pointer, optionally switch to interrupt stack.
* irq_count is used to check if a CPU is already on an interrupt stack
* or not. While this is essentially redundant with preempt_count it is
* a little cheaper to use a separate counter in the PDA (short of
* moving irq_enter into assembly, which would be too much work) */
movq %rsp, %rdi
incl PER_CPU_VAR(irq_count)
cmovzq PER_CPU_VAR(irq_stack_ptr), %rsp
UNWIND_HINT_REGS base=rdi
pushq %rdi
UNWIND_HINT_REGS indirect=1

Quoted 5 lines

The problem is that it's changing the stack pointer *before* writing the previous stack pointer (push %rdi). So when unwinding from an NMI which hit between the rsp write and the rdi push, the unwinder tries to access the regs on the previous stack (by reading rdi), but the previous stack pointer isn't there yet, so the access is considered out of bounds.

Ugh, that code. Does this problem go away with this patch applied:

Quoted 4 lines

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_ist&id=2231ec7e0bcc1a2bc94a17081511ab54cc6badd1

If so, want to update the patch for new kernels (shouldn't conflict with anything except your unwind hints)?

I don't think that patch will fix it, because it still updates rsp *before* writing the old rsp on the new stack. So there's still a window where the "previous stack" pointer is missing.

Quoted 35 lines · Josh Poimboeuf

Quoted 34 lines · Andy Lutomirski

Quoted 23 lines · Josh Poimboeuf

There's a bug here that will need a small change to the entry code.

Mike Galbraith reported:

WARNING: can't dereference registers at ffffc900089d7e08 for ip ffffffff81740bbb

After some looking I found that it's caused by the following code snippet in the 'interrupt' macro in entry_64.S:

/*
* Save previous stack pointer, optionally switch to interrupt stack.
* irq_count is used to check if a CPU is already on an interrupt stack
* or not. While this is essentially redundant with preempt_count it is
* a little cheaper to use a separate counter in the PDA (short of
* moving irq_enter into assembly, which would be too much work) */
movq %rsp, %rdi
incl PER_CPU_VAR(irq_count)
cmovzq PER_CPU_VAR(irq_stack_ptr), %rsp
UNWIND_HINT_REGS base=rdi
pushq %rdi
UNWIND_HINT_REGS indirect=1

Quoted 5 lines

The problem is that it's changing the stack pointer *before* writing the previous stack pointer (push %rdi). So when unwinding from an NMI which hit between the rsp write and the rdi push, the unwinder tries to access the regs on the previous stack (by reading rdi), but the previous stack pointer isn't there yet, so the access is considered out of bounds.

Ugh, that code. Does this problem go away with this patch applied:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_ist&id=2231ec7e0bcc1a2bc94a17081511ab54cc6badd1

Quoted 6 lines

Quoted 2 lines

If so, want to update the patch for new kernels (shouldn't conflict with anything except your unwind hints)?

I don't think that patch will fix it, because it still updates rsp *before* writing the old rsp on the new stack. So there's still a window where the "previous stack" pointer is missing.

But it's in a register. Is undwarf not able to grok that?

Quoted 38 lines · Andy Lutomirski

Quoted 36 lines · Josh Poimboeuf

Quoted 35 lines · Andy Lutomirski

Quoted 24 lines · Josh Poimboeuf

There's a bug here that will need a small change to the entry code.

Mike Galbraith reported:

WARNING: can't dereference registers at ffffc900089d7e08 for ip ffffffff81740bbb

After some looking I found that it's caused by the following code snippet in the 'interrupt' macro in entry_64.S:

/*
* Save previous stack pointer, optionally switch to interrupt stack.
* irq_count is used to check if a CPU is already on an interrupt stack
* or not. While this is essentially redundant with preempt_count it is
* a little cheaper to use a separate counter in the PDA (short of
* moving irq_enter into assembly, which would be too much work) */
movq %rsp, %rdi
incl PER_CPU_VAR(irq_count)
cmovzq PER_CPU_VAR(irq_stack_ptr), %rsp
UNWIND_HINT_REGS base=rdi
pushq %rdi
UNWIND_HINT_REGS indirect=1

Quoted 5 lines

The problem is that it's changing the stack pointer *before* writing the previous stack pointer (push %rdi). So when unwinding from an NMI which hit between the rsp write and the rdi push, the unwinder tries to access the regs on the previous stack (by reading rdi), but the previous stack pointer isn't there yet, so the access is considered out of bounds.

Ugh, that code. Does this problem go away with this patch applied:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_ist&id=2231ec7e0bcc1a2bc94a17081511ab54cc6badd1

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

If so, want to update the patch for new kernels (shouldn't conflict with anything except your unwind hints)?

I don't think that patch will fix it, because it still updates rsp *before* writing the old rsp on the new stack. So there's still a window where the "previous stack" pointer is missing.

But it's in a register. Is undwarf not able to grok that?

Sorry, I didn't explain it very well. Undwarf can find the regs pointer in rdi, it just doesn't trust its value.

See the stack_info.next_sp field, which is set in in_irq_stack():

   /*
    * The next stack pointer is the first thing pushed by the entry code
    * after switching to the irq stack.
    */
   info->next_sp = (unsigned long *)*(end - 1);

It's a safety mechanism. The unwinder needs the last word of the irq stack page to point to the previous stack. That way it can double check that the stack pointer it calculates is within the bounds of either the current stack or the previous stack.

In the above code, the previous stack pointer (or next stack pointer, depending on your perspective) hasn't been set up before it switches stacks. So the unwinder reads an uninitialized value into info->next_sp, and compares that with the regs pointer, and then stops the unwind because it thinks it went off into the weeds.

Signature · 1 line

Josh

Quoted 63 lines · Josh Poimboeuf

Quoted 37 lines · Andy Lutomirski

Quoted 36 lines · Josh Poimboeuf

Quoted 35 lines · Andy Lutomirski

Quoted 24 lines · Josh Poimboeuf

There's a bug here that will need a small change to the entry code.

Mike Galbraith reported:

WARNING: can't dereference registers at ffffc900089d7e08 for ip ffffffff81740bbb

After some looking I found that it's caused by the following code snippet in the 'interrupt' macro in entry_64.S:

/*
* Save previous stack pointer, optionally switch to interrupt stack.
* irq_count is used to check if a CPU is already on an interrupt stack
* or not. While this is essentially redundant with preempt_count it is
* a little cheaper to use a separate counter in the PDA (short of
* moving irq_enter into assembly, which would be too much work) */
movq %rsp, %rdi
incl PER_CPU_VAR(irq_count)
cmovzq PER_CPU_VAR(irq_stack_ptr), %rsp
UNWIND_HINT_REGS base=rdi
pushq %rdi
UNWIND_HINT_REGS indirect=1

Quoted 5 lines

The problem is that it's changing the stack pointer *before* writing the previous stack pointer (push %rdi). So when unwinding from an NMI which hit between the rsp write and the rdi push, the unwinder tries to access the regs on the previous stack (by reading rdi), but the previous stack pointer isn't there yet, so the access is considered out of bounds.

Ugh, that code. Does this problem go away with this patch applied:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_ist&id=2231ec7e0bcc1a2bc94a17081511ab54cc6badd1

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

If so, want to update the patch for new kernels (shouldn't conflict with anything except your unwind hints)?

I don't think that patch will fix it, because it still updates rsp *before* writing the old rsp on the new stack. So there's still a window where the "previous stack" pointer is missing.

But it's in a register. Is undwarf not able to grok that?

Sorry, I didn't explain it very well. Undwarf can find the regs pointer in rdi, it just doesn't trust its value.

See the stack_info.next_sp field, which is set in in_irq_stack():

   /*
    * The next stack pointer is the first thing pushed by the entry code
    * after switching to the irq stack.
    */
   info->next_sp = (unsigned long *)*(end - 1);

It's a safety mechanism. The unwinder needs the last word of the irq stack page to point to the previous stack. That way it can double check that the stack pointer it calculates is within the bounds of either the current stack or the previous stack.

Quoted 6 lines

In the above code, the previous stack pointer (or next stack pointer, depending on your perspective) hasn't been set up before it switches stacks. So the unwinder reads an uninitialized value into info->next_sp, and compares that with the regs pointer, and then stops the unwind because it thinks it went off into the weeds.

That should be manageable, though, I think. With my patch applied (and maybe even without it), the only exception to that rule is if regs->sp points just above the top of the IRQ stack and the next instruction is push reg. In that case, the reg is exactly as trustworthy as the normal rule.* Can you teach the unwinding code that this is okay?

* If an NMI hits right there, then it relies on unwinding out of the NMI correctly. But the usual checks that the target stack is a valid stack should prevent us from going off into the weeds regardless.

Quoted 31 lines · Andy Lutomirski

Quoted 17 lines

Sorry, I didn't explain it very well. Undwarf can find the regs pointer in rdi, it just doesn't trust its value.

See the stack_info.next_sp field, which is set in in_irq_stack():

   /*
    * The next stack pointer is the first thing pushed by the entry code
    * after switching to the irq stack.
    */
   info->next_sp = (unsigned long *)*(end - 1);

It's a safety mechanism. The unwinder needs the last word of the irq stack page to point to the previous stack. That way it can double check that the stack pointer it calculates is within the bounds of either the current stack or the previous stack.

Quoted 6 lines

In the above code, the previous stack pointer (or next stack pointer, depending on your perspective) hasn't been set up before it switches stacks. So the unwinder reads an uninitialized value into info->next_sp, and compares that with the regs pointer, and then stops the unwind because it thinks it went off into the weeds.

That should be manageable, though, I think. With my patch applied (and maybe even without it), the only exception to that rule is if regs->sp points just above the top of the IRQ stack and the next instruction is push reg. In that case, the reg is exactly as trustworthy as the normal rule.* Can you teach the unwinding code that this is okay?

Quoted 3 lines

* If an NMI hits right there, then it relies on unwinding out of the NMI correctly. But the usual checks that the target stack is a valid stack should prevent us from going off into the weeds regardless.

But that would remove a safeguard against the undwarf data being corrupt. Sure, it would only affect the rare case where the stack pointer is at the top of the IRQ stack, but still...

Also, the frame pointer and guess unwinders have the same issue, and this solution wouldn't work for them.

And, worst of all, the oops stack dumping code in show_trace_log_lvl() also has this issue . It relies on those previous stack pointers. And it's separated from the unwinder logic by design, so it can't ask the unwinder where the next stack is.

Hmm. There's another option that might be considerably nicer, though:
put the IRQ stack at a known (at link time) position *in percpu space*. (Presumably it already is -- I haven't checked.) Then we do:

.macro ENTER_IRQ_STACK old_rsp
DEBUG_ENTRY_ASSERT_IRQS_OFF
movq %rsp, \old_rsp
incl PER_CPU_VAR(irq_count)

/*
* Right now, if we just incremented irq_count to zero, we've
* claimed the IRQ stack but we haven't switched to it yet.
* Anything that can interrupt us here without using IST
* must be *extremely* careful to limit its stack usage. */
jnz .Lpush_old_rsp_\@
movq \old_rsp, PER_CPU_VAR(top_word_in_irq_stack)
movq PER_CPU_VAR(irq_stack_ptr), %rsp
.Lpush_old_rsp_\@:
pushq \old_rsp
.endm

Quoted 9 lines · Andy Lutomirski

Hmm. There's another option that might be considerably nicer, though:
put the IRQ stack at a known (at link time) position *in percpu space*. (Presumably it already is -- I haven't checked.) Then we do:

.macro ENTER_IRQ_STACK old_rsp
DEBUG_ENTRY_ASSERT_IRQS_OFF
movq %rsp, \old_rsp
incl PER_CPU_VAR(irq_count)

Quoted 13 lines

/*
* Right now, if we just incremented irq_count to zero, we've
* claimed the IRQ stack but we haven't switched to it yet.
* Anything that can interrupt us here without using IST
* must be *extremely* careful to limit its stack usage. */
jnz .Lpush_old_rsp_\@
movq \old_rsp, PER_CPU_VAR(top_word_in_irq_stack)
movq PER_CPU_VAR(irq_stack_ptr), %rsp
.Lpush_old_rsp_\@:
pushq \old_rsp
.endm

How about the two commits here (well, soon to be there once gitweb catches up):

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_irq_stack&id=0f56a55bb133cd53ccb78ca51378086296618322

If you like them, want to add them to your series?

Quoted 24 lines · Andy Lutomirski

Quoted 9 lines · Andy Lutomirski

Hmm. There's another option that might be considerably nicer, though:
put the IRQ stack at a known (at link time) position *in percpu space*. (Presumably it already is -- I haven't checked.) Then we do:

.macro ENTER_IRQ_STACK old_rsp
DEBUG_ENTRY_ASSERT_IRQS_OFF
movq %rsp, \old_rsp
incl PER_CPU_VAR(irq_count)

Quoted 13 lines

/*
* Right now, if we just incremented irq_count to zero, we've
* claimed the IRQ stack but we haven't switched to it yet.
* Anything that can interrupt us here without using IST
* must be *extremely* careful to limit its stack usage. */
jnz .Lpush_old_rsp_\@
movq \old_rsp, PER_CPU_VAR(top_word_in_irq_stack)
movq PER_CPU_VAR(irq_stack_ptr), %rsp
.Lpush_old_rsp_\@:
pushq \old_rsp
.endm

Quoted 5 lines

How about the two commits here (well, soon to be there once gitweb catches up):

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_irq_stack&id=0f56a55bb133cd53ccb78ca51378086296618322

If you like them, want to add them to your series?

The second patch looks good to me, thanks. I can pick up the patches.

A few comments about the first patch:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_irq_stack&id=3e2aa2102cc1c5e60d4a8637bff78d0478a55059

- It uses a '693:' label instead of '.Lirqs_off_\@:'

- There's a comment I don't follow:

"Anything that can interrupt us here without using IST must be *extremely* careful to limit its stack usage."

What specifically could interrupt there without using IST?

- Since do_softirq_own_stack() is a callable function, I think it still needs to save rbp.

- Why change the "jmp error_exit" to "ret" in
xen_do_hypervisor_callback()?

Quoted 5 lines

A few comments about the first patch:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_irq_stack&id=3e2aa2102cc1c5e60d4a8637bff78d0478a55059

- It uses a '693:' label instead of '.Lirqs_off_\@:'

Touché!

Quoted 7 lines

- There's a comment I don't follow:

"Anything that can interrupt us here without using IST must be *extremely* careful to limit its stack usage."

What specifically could interrupt there without using IST?

#DB, later on in the series. I'll update the comment.

Quoted 3 lines

- Since do_softirq_own_stack() is a callable function, I think it still needs to save rbp.

Whoops.

Quoted 3 lines

- Why change the "jmp error_exit" to "ret" in
xen_do_hypervisor_callback()?

To match the other change I made there. I removed both.

Quoted 28 lines · Andy Lutomirski

Quoted 5 lines

A few comments about the first patch:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_irq_stack&id=3e2aa2102cc1c5e60d4a8637bff78d0478a55059

- It uses a '693:' label instead of '.Lirqs_off_\@:'

Touché!

Quoted 7 lines

- There's a comment I don't follow:

"Anything that can interrupt us here without using IST must be *extremely* careful to limit its stack usage."

What specifically could interrupt there without using IST?

#DB, later on in the series. I'll update the comment.

Quoted 3 lines

- Since do_softirq_own_stack() is a callable function, I think it still needs to save rbp.

Whoops.

Quoted 3 lines

- Why change the "jmp error_exit" to "ret" in
xen_do_hypervisor_callback()?

Quoted 1 line

To match the other change I made there. I removed both.

One more thing I forgot to mention: if you could use r10 instead of r11, that would be helpful because it means one less register undwarf needs to know about. (It already deals with r10 because of GCC stack realignment).

--
Josh

Quoted 29 lines · Josh Poimboeuf

Quoted 28 lines · Andy Lutomirski

Quoted 5 lines

A few comments about the first patch:

https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/commit/?h=x86/entry_irq_stack&id=3e2aa2102cc1c5e60d4a8637bff78d0478a55059

- It uses a '693:' label instead of '.Lirqs_off_\@:'

Touché!

Quoted 7 lines

- There's a comment I don't follow:

"Anything that can interrupt us here without using IST must be *extremely* careful to limit its stack usage."

What specifically could interrupt there without using IST?

#DB, later on in the series. I'll update the comment.

Quoted 3 lines

- Since do_softirq_own_stack() is a callable function, I think it still needs to save rbp.

Whoops.

Quoted 3 lines

- Why change the "jmp error_exit" to "ret" in
xen_do_hypervisor_callback()?

Quoted 6 lines

Quoted 1 line

To match the other change I made there. I removed both.

One more thing I forgot to mention: if you could use r10 instead of r11, that would be helpful because it means one less register undwarf needs to know about. (It already deals with r10 because of GCC stack realignment).

I'll let you figure that one out :)

(Although I think I agree with hpa: why not let it support all regs? Or am I missing something still?)

Undwarf vs frame pointers
-------------------------

With frame pointers enabled, GCC adds instrumentation code to every function in the kernel. The kernel's .text size increases by about 3.2%, resulting in a broad kernel-wide slowdown. Measurements by Mel Gorman [1] have shown a slowdown of 5-10% for some workloads.

In contrast, the undwarf unwinder has no effect on text size or runtime performance, because the debuginfo is out of band. So if you disable frame pointers and enable undwarf, you get a nice performance improvement across the board, and still have reliable stack traces.

Another benefit of undwarf compared to frame pointers is that it can reliably unwind across interrupts and exceptions. Frame pointer based unwinds can skip the caller of the interrupted function if it was a leaf function or if the interrupt hit before the frame pointer was saved.

The main disadvantage of undwarf compared to frame pointers is that it needs more memory to store the undwarf table: roughly 3-5MB depending on the kernel config.

 56 files changed, 3466 insertions(+), 1765 deletions(-)

I'm not tied to the 'undwarf' name, other naming ideas are welcome.

Quoted 18 lines · Josh Poimboeuf

Undwarf vs frame pointers
-------------------------

With frame pointers enabled, GCC adds instrumentation code to every function in the kernel. The kernel's .text size increases by about 3.2%, resulting in a broad kernel-wide slowdown. Measurements by Mel Gorman [1] have shown a slowdown of 5-10% for some workloads.

In contrast, the undwarf unwinder has no effect on text size or runtime performance, because the debuginfo is out of band. So if you disable frame pointers and enable undwarf, you get a nice performance improvement across the board, and still have reliable stack traces.

Another benefit of undwarf compared to frame pointers is that it can reliably unwind across interrupts and exceptions. Frame pointer based unwinds can skip the caller of the interrupted function if it was a leaf function or if the interrupt hit before the frame pointer was saved.

Quoted 3 lines

The main disadvantage of undwarf compared to frame pointers is that it needs more memory to store the undwarf table: roughly 3-5MB depending on the kernel config.

Note that it's not just a performance improvement, but also an instruction cache locality improvement: 3.2% .text savings almost directly transform into a similarly sized reduction in cache footprint. That can transform to even higher speedups for workloads whose cache locality is borderline.

I _really_ like this feature, and the independence of the debuginfo data format.

Logistically it's too bad we are 3 days away from the merge window to be able to pick this up:

Quoted 1 line

 56 files changed, 3466 insertions(+), 1765 deletions(-)

OTOH most of the diffstat is in objtool.

Any objections to applying the first 3 objtool patches straight away and see whether anything breaks? That would significantly reduce the size of the rest of the patch set.

Quoted 1 line

I'm not tied to the 'undwarf' name, other naming ideas are welcome.

Ha, a new bike shed painting job! ;-)

I think 'undwarf' isn't a bad name, it's short, catchy and describes the purpose of the effort.

But I cannot resist some other suggestions, after 'elf' and 'dwarf' the obvious candidates from the peoples of Middle-earth would be:

- 'Hobbit'
- 'Eagle'
- 'Ent'
- 'Dragon'
- 'Troll'
- 'Ainur'

'struct troll_entry' has a certain charm to it.

'Eagle' is even nicer IMHO: larger than a dwarf but so much faster - and eagles are beautiful! Plus the name is 2 letters shorter than 'unwdwarf', win-win.

Quoted 17 lines

Quoted 1 line

I'm not tied to the 'undwarf' name, other naming ideas are welcome.

Ha, a new bike shed painting job! ;-)

I think 'undwarf' isn't a bad name, it's short, catchy and describes the purpose of the effort.

But I cannot resist some other suggestions, after 'elf' and 'dwarf' the obvious candidates from the peoples of Middle-earth would be:

- 'Hobbit'
- 'Eagle'
- 'Ent'
- 'Dragon'
- 'Troll'
- 'Ainur'

Quoted 4 lines

'struct troll_entry' has a certain charm to it.

'Eagle' is even nicer IMHO: larger than a dwarf but so much faster - and eagles are beautiful! Plus the name is 2 letters shorter than 'unwdwarf', win-win.

Finally, we get to the important part ;-)

Thus far I've been partial to undwarf, and I haven't been able to shake it.

But I like some of your suggestions. Especially troll and hobbit. Will need to do some more deep thinking about it :-)