x86: undwarf unwinder

In preparation for the new 'objtool undwarf generate' command, which will rely on 'objtool check', move the checking code from builtin-check.c to check.c where it can be used by other commands.

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

arch/x86/kernel/kprobes/opt.c +1 -0

@@ -28,6 +28,7 @@
 #include <linux/kdebug.h>
 #include <linux/kallsyms.h>
 #include <linux/ftrace.h>
+#include <linux/frame.h>
 
 #include <asm/text-patching.h>
 #include <asm/cacheflush.h>

arch/x86/kernel/kprobes/opt.c +0 -0

 			".global optprobe_template_entry\n"
 			"optprobe_template_entry:\n"
 #ifdef CONFIG_X86_64

@@ -131,7 +133,12 @@ asm (
 			"	popf\n"
 #endif
 			".global optprobe_template_end\n"

On 06/01/2017, 07:44 AM, Josh Poimboeuf wrote:
...

Quoted 13 lines

arch/x86/kernel/kprobes/opt.c +1 -0

@@ -28,6 +28,7 @@
 #include <linux/kdebug.h>
 #include <linux/kallsyms.h>
 #include <linux/ftrace.h>
+#include <linux/frame.h>
 
 #include <asm/text-patching.h>
 #include <asm/cacheflush.h>

@@ -94,6 +95,7 @@ static void synthesize_set_arg1(kprobe_opcode_t *addr, unsigned long val)
 }
 

arch/x86/kernel/kprobes/opt.c static void synthesize_set_arg1(kprobe_opcode_t *addr, unsigned long val) · line 98

Quoted 2 lines

arch/x86/kernel/kprobes/opt.c +1 -0

 asm (
+			"optprobe_template_func:\n"

Why do you add another symbol here? What's wrong with optprobe_template_entry?

index 3fb0747..1ca5d9a 100644

tools/objtool/elf.c +0 -0

tools/objtool/elf.c +7 -0

+	if (fd == -1) {
+		perror("creat");
+		return -1;
+	}
+
+	elfout = elf_begin(fd, ELF_C_WRITE, NULL);
+	if (!elfout) {

tools/objtool/elf.c +26 -0

+		perror("gelf_getehdr");
+		return -1;
+	}
+
+	if (!gelf_getehdr(elf->elf, &eh)) {
+		perror("gelf_getehdr");
+		return -1;
+	}
+
+	memset(&ehout, 0, sizeof(ehout));
+	ehout.e_ident[EI_DATA] = eh.e_ident[EI_DATA];
+	ehout.e_machine = eh.e_machine;
+	ehout.e_type = eh.e_type;
+	ehout.e_version = EV_CURRENT;
+	ehout.e_shstrndx = find_section_by_name(elf, ".shstrtab")->idx;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		if (sec->idx == 0)
+			continue;
+
+		scn = elf_newscn(elfout);
+		if (!scn) {
+			perror("elf_newscn");
+			return -1;
+		}
+

tools/objtool/elf.c +7 -0

+		sh = sec->sh;
+
+		if (!gelf_update_shdr(scn, &sh)) {
+			perror("gelf_update_shdr");
+			return -1;
+		}
+	}

tools/objtool/elf.c +4 -0

+
+	return 0;
+}
+
 void elf_close(struct elf *elf)
 {
 	struct section *sec, *tmpsec;

tools/objtool/undwarf.c new file +0 -0

@@ -0,0 +1,308 @@

tools/objtool/undwarf.c new file +22 -0

+int undwarf_dump(const char *_objname)
+{
+	struct elf *elf;
+	struct section *sec;
+	struct rela *rela;
+	struct undwarf *undwarf;
+	int nr, i;
+
+	objname = _objname;
+
+	elf = elf_open(objname);
+	if (!elf) {
+		WARN("error reading elf file %s\n", objname);
+		return 1;
+	}
+
+	sec = find_section_by_name(elf, ".undwarf");
+	if (!sec || !sec->rela)
+		return 0;
+
+	nr = sec->len / sizeof(*undwarf);
+	for (i = 0; i < nr; i++) {

On 06/01/2017, 07:44 AM, Josh Poimboeuf wrote:
...

Quoted 3 lines

index 3fb0747..1ca5d9a 100644

tools/objtool/elf.c +0 -0

...

tools/objtool/elf.c struct elf *elf_open(const char *name) · line 536

Quoted 11 lines

tools/objtool/elf.c +11 -0

+int elf_write_to_file(struct elf *elf, char *outfile)
+{
+	int fd;
+	struct section *sec;
+	Elf *elfout;
+	GElf_Ehdr eh, ehout;
+	Elf_Scn *scn;
+	Elf_Data *data;
+	GElf_Shdr sh;
+
+	fd = creat(outfile, 0777);

0755 even though it is umasked?

Quoted 7 lines

tools/objtool/elf.c +7 -0

+	if (fd == -1) {
+		perror("creat");
+		return -1;
+	}
+
+	elfout = elf_begin(fd, ELF_C_WRITE, NULL);
+	if (!elfout) {

tools/objtool/elf.c struct elf *elf_open(const char *name) · line 553

Quoted 10 lines

tools/objtool/elf.c +10 -0

+		perror("elf_begin");
+		return -1;
+	}
+
+	if (!gelf_newehdr(elfout, gelf_getclass(elf->elf))) {
+		perror("gelf_newehdr");
+		return -1;
+	}
+
+	if (!gelf_getehdr(elfout, &ehout)) {

This does not make much sense to do. You memset(0) it below.

Quoted 26 lines

tools/objtool/elf.c +26 -0

+		perror("gelf_getehdr");
+		return -1;
+	}
+
+	if (!gelf_getehdr(elf->elf, &eh)) {
+		perror("gelf_getehdr");
+		return -1;
+	}
+
+	memset(&ehout, 0, sizeof(ehout));
+	ehout.e_ident[EI_DATA] = eh.e_ident[EI_DATA];
+	ehout.e_machine = eh.e_machine;
+	ehout.e_type = eh.e_type;
+	ehout.e_version = EV_CURRENT;
+	ehout.e_shstrndx = find_section_by_name(elf, ".shstrtab")->idx;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		if (sec->idx == 0)
+			continue;
+
+		scn = elf_newscn(elfout);
+		if (!scn) {
+			perror("elf_newscn");
+			return -1;
+		}
+

tools/objtool/elf.c struct elf *elf_open(const char *name) · line 589

Quoted 10 lines

tools/objtool/elf.c +10 -0

+		data = elf_newdata(scn);
+		if (!data) {
+			perror("elf_newdata");
+			return -1;
+		}
+
+		if (!elf_flagdata(data, ELF_C_SET, ELF_F_DIRTY)) {
+			perror("elf_flagdata");
+			return -1;
+		}

There is not much point setting DIRTY flag here. elf_newdata does so.

tools/objtool/elf.c struct elf *elf_open(const char *name) · line 598

Quoted 8 lines

tools/objtool/elf.c +8 -0

+		data->d_type = sec->data->d_type;
+		data->d_buf = sec->data->d_buf;
+		data->d_size = sec->data->d_size;
+
+		if(!gelf_getshdr(scn, &sh)) {
+			perror("gelf_getshdr");
+			return -1;
+		}

This does not make much sense to do again. You overwrite the content right away:

Quoted 7 lines

tools/objtool/elf.c +7 -0

+		sh = sec->sh;
+
+		if (!gelf_update_shdr(scn, &sh)) {
+			perror("gelf_update_shdr");
+			return -1;
+		}
+	}

tools/objtool/elf.c struct elf *elf_open(const char *name) · line 616

Quoted 10 lines

tools/objtool/elf.c +10 -0

+
+	if (!gelf_update_ehdr(elfout, &ehout)) {
+		perror("gelf_update_ehdr");
+		return -1;
+	}
+
+	if (elf_update(elfout, ELF_C_WRITE) < 0) {
+		perror("elf_update");
+		return -1;
+	}

elf_end() + close() ?

Quoted 7 lines

tools/objtool/elf.c +4 -0

+
+	return 0;
+}
+
 void elf_close(struct elf *elf)
 {
 	struct section *sec, *tmpsec;

...

Quoted 3 lines

tools/objtool/undwarf.c new file +0 -0

@@ -0,0 +1,308 @@

...

Quoted 22 lines

tools/objtool/undwarf.c new file +22 -0

+int undwarf_dump(const char *_objname)
+{
+	struct elf *elf;
+	struct section *sec;
+	struct rela *rela;
+	struct undwarf *undwarf;
+	int nr, i;
+
+	objname = _objname;
+
+	elf = elf_open(objname);
+	if (!elf) {
+		WARN("error reading elf file %s\n", objname);
+		return 1;
+	}
+
+	sec = find_section_by_name(elf, ".undwarf");
+	if (!sec || !sec->rela)
+		return 0;
+
+	nr = sec->len / sizeof(*undwarf);
+	for (i = 0; i < nr; i++) {

...

tools/objtool/undwarf.c

Quoted 1 line

tools/objtool/undwarf.c new file +1 -0

+	}

elf_close() ?

tools/objtool/undwarf.c

Quoted 3 lines

tools/objtool/undwarf.c new file +3 -0

+
+	return 0;
+}

I agree with all your comments, will fix them all. Thanks for the review.

Quoted 2 lines · Josh Poimboeuf

I agree with all your comments, will fix them all. Thanks for the review.

This is not the correct way:
++ if (flags & O_WRONLY)
++ cmd = ELF_C_WRITE;
++ else if (flags & O_RDWR)
++ cmd = ELF_C_RDWR;
++ else
++ cmd = ELF_C_READ_MMAP;

For this particular codeflow, it works, but it should be:
(flags & O_ACCMODE) == O_WRONLY

                    == O_RDWR

Some asm (and inline asm) code does special things to the stack which objtool can't understand. (Nor can GCC or GNU assembler, for that matter.) In such cases we need a facility for the code to provide annotations, so the unwinder can unwind through it.

This provides such a facility, in the form of CFI hints. They're similar to the GNU assembler .cfi* directives, but they give more information, and are needed in far fewer places, because objtool can fill in the blanks by following branches and adjusting the stack pointer for pushes and pops.

Quoted 10 lines · Josh Poimboeuf

Some asm (and inline asm) code does special things to the stack which objtool can't understand. (Nor can GCC or GNU assembler, for that matter.) In such cases we need a facility for the code to provide annotations, so the unwinder can unwind through it.

This provides such a facility, in the form of CFI hints. They're similar to the GNU assembler .cfi* directives, but they give more information, and are needed in far fewer places, because objtool can fill in the blanks by following branches and adjusting the stack pointer for pushes and pops.

Two minor suggestions:

Could you prefix these with something other than "CFI_"? For those of use who have read the binutils manual, using "CFI_" sounds awfully like .cfi_, and people might expect the semantics to be the same.

arch/x86/include/asm/undwarf.h line 80

Quoted 2 lines

arch/x86/include/asm/undwarf.h new file +2 -0

+#define CFI_HINT(cfa_reg, cfa_offset, type)                    \
+       "999: \n\t"                                             \

Have you checked if 999 is used elsewhere? My personal preference is to use:

.Ldescriptive_text_\@:

instead of a hopefully-unique number. I never researched the history, but I suspect that the convention of using large numbers came from early binutils versions that didn't have \@, but we use \@ fairly extensively in the kernel these days, so it would seem that we no longer support binutils versions that old.

Quoted 14 lines · Andy Lutomirski

Quoted 10 lines · Josh Poimboeuf

Some asm (and inline asm) code does special things to the stack which objtool can't understand. (Nor can GCC or GNU assembler, for that matter.) In such cases we need a facility for the code to provide annotations, so the unwinder can unwind through it.

This provides such a facility, in the form of CFI hints. They're similar to the GNU assembler .cfi* directives, but they give more information, and are needed in far fewer places, because objtool can fill in the blanks by following branches and adjusting the stack pointer for pushes and pops.

Two minor suggestions:

Quoted 3 lines

Could you prefix these with something other than "CFI_"? For those of use who have read the binutils manual, using "CFI_" sounds awfully like .cfi_, and people might expect the semantics to be the same.

The intention was that even if this undwarf thing doesn't work out, the CFI_ macros could still be used by objtool to generate proper DWARF. Would prefixing them with CFI_HINT_ be better? Or UNWIND_HINT_?

Quoted 19 lines · Josh Poimboeuf

Quoted 17 lines · Andy Lutomirski

Quoted 10 lines · Josh Poimboeuf

Some asm (and inline asm) code does special things to the stack which objtool can't understand. (Nor can GCC or GNU assembler, for that matter.) In such cases we need a facility for the code to provide annotations, so the unwinder can unwind through it.

This provides such a facility, in the form of CFI hints. They're similar to the GNU assembler .cfi* directives, but they give more information, and are needed in far fewer places, because objtool can fill in the blanks by following branches and adjusting the stack pointer for pushes and pops.

Two minor suggestions:

Could you prefix these with something other than "CFI_"? For those of use who have read the binutils manual, using "CFI_" sounds awfully like .cfi_, and people might expect the semantics to be the same.

Quoted 3 lines

The intention was that even if this undwarf thing doesn't work out, the CFI_ macros could still be used by objtool to generate proper DWARF. Would prefixing them with CFI_HINT_ be better? Or UNWIND_HINT_?

This has nothing to do with the data format or implementation. I
just think that "CFI_" suggests that they're semantically equivalent to binutils' .cfi directives. If they're not, then maybe UNWIND_HINT is better.

Add CFI hint undwarf annotations to entry_64.S. This will enable the undwarf unwinder to unwind through any location in the entry code including syscalls, interrupts, and exceptions.

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

---
 arch/x86/entry/Makefile   |  1 -
 arch/x86/entry/calling.h  |  5 +++++
 arch/x86/entry/entry_64.S | 56 ++++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 55 insertions(+), 7 deletions(-)

arch/x86/entry/Makefile +0 -1

index 9976fce..af28a8a 100644
@@ -2,7 +2,6 @@
 # Makefile for the x86 low level entry code
 #
 
-OBJECT_FILES_NON_STANDARD_entry_$(BITS).o   := y
 OBJECT_FILES_NON_STANDARD_entry_64_compat.o := y
 
 CFLAGS_syscall_64.o            += $(call cc-option,-Wno-override-init,)

arch/x86/entry/calling.h +0 -0

index 05ed3d3..bbec02e 100644

Quoted 28 lines · Josh Poimboeuf

Add CFI hint undwarf annotations to entry_64.S. This will enable the undwarf unwinder to unwind through any location in the entry code including syscalls, interrupts, and exceptions.

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

---
 arch/x86/entry/Makefile   |  1 -
 arch/x86/entry/calling.h  |  5 +++++
 arch/x86/entry/entry_64.S | 56 ++++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 55 insertions(+), 7 deletions(-)

arch/x86/entry/Makefile +0 -1

index 9976fce..af28a8a 100644
@@ -2,7 +2,6 @@
 # Makefile for the x86 low level entry code
 #
 
-OBJECT_FILES_NON_STANDARD_entry_$(BITS).o   := y
 OBJECT_FILES_NON_STANDARD_entry_64_compat.o := y
 
 CFLAGS_syscall_64.o            += $(call cc-option,-Wno-override-init,)

arch/x86/entry/calling.h +0 -0

index 05ed3d3..bbec02e 100644

arch/x86/entry/calling.h line 6

Quoted 6 lines

arch/x86/entry/calling.h +2 -0

@@ -1,4 +1,6 @@
 #include <linux/jump_label.h>
+#include <asm/undwarf.h>
+
 
 /*
 

Just to make sure I understand this, if we unwind from...

arch/x86/entry/calling.h For 32-bit we have the following conventions - kernel is built with · line 115

Quoted 3 lines

arch/x86/entry/calling.h +0 -0

@@ -112,6 +114,7 @@ For 32-bit we have the following conventions - kernel is built with
        movq %rdx, 12*8+\offset(%rsp)
        movq %rsi, 13*8+\offset(%rsp)

...here..., will objtool think that rdx and rsi (etc) still live in their respective regs, or will it find them in the on-stack data given by CFI_REGS? If the former, how does undwarf deal with the corresponding pops?

arch/x86/entry/calling.h For 32-bit we have the following conventions - kernel is built with · line 117

Quoted 3 lines

arch/x86/entry/calling.h +1 -0

        movq %rdi, 14*8+\offset(%rsp)
+       CFI_REGS offset=\offset extra=0

arch/x86/entry/calling.h ENTRY(ret_from_fork) · line 427

Quoted 5 lines

arch/x86/entry/calling.h +1 -0

@@ -414,6 +424,7 @@ ENTRY(ret_from_fork)
 2:
        movq    %rsp, %rdi
        call    syscall_return_slowpath /* returns with IRQs disabled */
+       CFI_REGS

I'm confused. syscall_return_slowpath didn't change anything relevant to unwinding, right? What's CFI_REGS here for?

Quoted 11 lines · Andy Lutomirski

On Wed, May 31, 2017 at 10:44 PM, Josh Poimboeuf <[email protected]> wrote:
Just to make sure I understand this, if we unwind from...

arch/x86/entry/calling.h For 32-bit we have the following conventions - kernel is built with · line 115

Quoted 3 lines

arch/x86/entry/calling.h +0 -0

@@ -112,6 +114,7 @@ For 32-bit we have the following conventions - kernel is built with
        movq %rdx, 12*8+\offset(%rsp)
        movq %rsi, 13*8+\offset(%rsp)

...here..., will objtool think that rdx and rsi (etc) still live in their respective regs, or will it find them in the on-stack data given by CFI_REGS? If the former, how does undwarf deal with the corresponding pops?

It will find them in their respective registers, which is fine because they haven't been clobbered yet.

Quoted 13 lines · Josh Poimboeuf

Quoted 11 lines · Andy Lutomirski

On Wed, May 31, 2017 at 10:44 PM, Josh Poimboeuf <[email protected]> wrote:
Just to make sure I understand this, if we unwind from...

arch/x86/entry/calling.h For 32-bit we have the following conventions - kernel is built with · line 115

Quoted 3 lines

arch/x86/entry/calling.h +0 -0

@@ -112,6 +114,7 @@ For 32-bit we have the following conventions - kernel is built with
        movq %rdx, 12*8+\offset(%rsp)
        movq %rsi, 13*8+\offset(%rsp)

...here..., will objtool think that rdx and rsi (etc) still live in their respective regs, or will it find them in the on-stack data given by CFI_REGS? If the former, how does undwarf deal with the corresponding pops?

Quoted 2 lines

It will find them in their respective registers, which is fine because they haven't been clobbered yet.

Sorry, I hit send too soon. Which pops are you referring to?

Quoted 17 lines · Josh Poimboeuf

Quoted 15 lines · Josh Poimboeuf

Quoted 11 lines · Andy Lutomirski

On Wed, May 31, 2017 at 10:44 PM, Josh Poimboeuf <[email protected]> wrote:
Just to make sure I understand this, if we unwind from...

arch/x86/entry/calling.h For 32-bit we have the following conventions - kernel is built with · line 115

Quoted 3 lines

arch/x86/entry/calling.h +0 -0

@@ -112,6 +114,7 @@ For 32-bit we have the following conventions - kernel is built with
        movq %rdx, 12*8+\offset(%rsp)
        movq %rsi, 13*8+\offset(%rsp)

...here..., will objtool think that rdx and rsi (etc) still live in their respective regs, or will it find them in the on-stack data given by CFI_REGS? If the former, how does undwarf deal with the corresponding pops?

It will find them in their respective registers, which is fine because they haven't been clobbered yet.

Quoted 2 lines

Sorry, I hit send too soon. Which pops are you referring to?

If we do push, push, push, CFI_REGS, and then, later, we pop all those saved regs, how does undwarf figure out that those pops are moving a saved reg from the stack back to a register? Is objtool just that smart, or did I fail to notice an annotation somewhere, or does it not matter?

arch/x86/kernel/unwind_undwarf.c new file +12 -0

+static struct undwarf *__undwarf_lookup(struct undwarf *undwarf,
+					unsigned int num, unsigned long ip)
+{
+	struct undwarf *first = undwarf;
+	struct undwarf *last = undwarf + num - 1;
+	struct undwarf *mid;
+	unsigned long u_ip;
+
+	while (first <= last) {
+		mid = first + ((last - first) / 2);
+		u_ip = undwarf_ip(mid);
+

arch/x86/kernel/unwind_undwarf.c new file +11 -0

+static struct undwarf *undwarf_lookup(unsigned long ip)
+{
+	struct undwarf *undwarf;
+	struct module *mod;
+
+	/* Look in vmlinux undwarf section: */
+	undwarf = __undwarf_lookup(__undwarf_start, __undwarf_end - __undwarf_start, ip);
+	if (undwarf)
+		return undwarf;
+
+	/* Look in module undwarf sections: */

arch/x86/kernel/unwind_undwarf.c new file +6 -0

+static bool stack_access_ok(struct unwind_state *state, unsigned long addr,
+			    size_t len)
+{
+	struct stack_info *info = &state->stack_info;
+
+	/*

arch/x86/kernel/unwind_undwarf.c new file +3 -0

+
+	return true;
+}

Quoted 17 lines · Josh Poimboeuf

arch/x86/kernel/unwind_undwarf.c new file +17 -0

+static struct undwarf *__undwarf_lookup(struct undwarf *undwarf,
+					unsigned int num, unsigned long ip)
+{
+	struct undwarf *first = undwarf;
+	struct undwarf *last = undwarf + num - 1;
+	struct undwarf *mid;
+	unsigned long u_ip;
+
+	while (first <= last) {
+		mid = first + ((last - first) / 2);
+		u_ip = undwarf_ip(mid);
+
+		if (ip >= u_ip) {
+			if (ip < u_ip + mid->len)
+				return mid;
+			first = mid + 1;
+		} else

arch/x86/kernel/unwind_undwarf.c line 63

Quoted 5 lines

arch/x86/kernel/unwind_undwarf.c new file +5 -0

+			last = mid - 1;
+	}
+
+	return NULL;
+}

That's a bog standard binary search thing, don't we have a helper for that someplace?

Quoted 11 lines

arch/x86/kernel/unwind_undwarf.c new file +11 -0

+static struct undwarf *undwarf_lookup(unsigned long ip)
+{
+	struct undwarf *undwarf;
+	struct module *mod;
+
+	/* Look in vmlinux undwarf section: */
+	undwarf = __undwarf_lookup(__undwarf_start, __undwarf_end - __undwarf_start, ip);
+	if (undwarf)
+		return undwarf;
+
+	/* Look in module undwarf sections: */

arch/x86/kernel/unwind_undwarf.c line 85

Quoted 10 lines

arch/x86/kernel/unwind_undwarf.c new file +10 -0

+	preempt_disable();
+	mod = __module_address(ip);
+	if (!mod || !mod->arch.undwarf)
+		goto module_out;
+	undwarf = __undwarf_lookup(mod->arch.undwarf, mod->arch.num_undwarves, ip);
+
+module_out:
+	preempt_enable();
+	return undwarf;
+}

A few points here:

- that first lookup is entirely pointless if !core_kernel_text(ip)

- that preempt_{dis,en}able() muck is 'pointless', for while it shuts up the warnings from __modules_address(), nothing preserves the struct undwarf you get a pointer to after the preempt_enable().

- what about 'interesting' things like, ftrace_trampoline, kprobe insn slots and bpf text?

Quoted 19 lines · Peter Zijlstra

Quoted 17 lines · Josh Poimboeuf

arch/x86/kernel/unwind_undwarf.c new file +17 -0

+static struct undwarf *__undwarf_lookup(struct undwarf *undwarf,
+					unsigned int num, unsigned long ip)
+{
+	struct undwarf *first = undwarf;
+	struct undwarf *last = undwarf + num - 1;
+	struct undwarf *mid;
+	unsigned long u_ip;
+
+	while (first <= last) {
+		mid = first + ((last - first) / 2);
+		u_ip = undwarf_ip(mid);
+
+		if (ip >= u_ip) {
+			if (ip < u_ip + mid->len)
+				return mid;
+			first = mid + 1;
+		} else

Quoted 8 lines

arch/x86/kernel/unwind_undwarf.c line 63

Quoted 5 lines

arch/x86/kernel/unwind_undwarf.c new file +5 -0

+			last = mid - 1;
+	}
+
+	return NULL;
+}

That's a bog standard binary search thing, don't we have a helper for that someplace?

I wasn't able to find one...

Quoted 29 lines · Josh Poimboeuf

Quoted 19 lines · Peter Zijlstra

Quoted 17 lines · Josh Poimboeuf

arch/x86/kernel/unwind_undwarf.c new file +17 -0

+static struct undwarf *__undwarf_lookup(struct undwarf *undwarf,
+					unsigned int num, unsigned long ip)
+{
+	struct undwarf *first = undwarf;
+	struct undwarf *last = undwarf + num - 1;
+	struct undwarf *mid;
+	unsigned long u_ip;
+
+	while (first <= last) {
+		mid = first + ((last - first) / 2);
+		u_ip = undwarf_ip(mid);
+
+		if (ip >= u_ip) {
+			if (ip < u_ip + mid->len)
+				return mid;
+			first = mid + 1;
+		} else

Quoted 8 lines

arch/x86/kernel/unwind_undwarf.c line 63

Quoted 5 lines

arch/x86/kernel/unwind_undwarf.c new file +5 -0

+			last = mid - 1;
+	}
+
+	return NULL;
+}

That's a bog standard binary search thing, don't we have a helper for that someplace?

Quoted 1 line

I wasn't able to find one...

There is bsearch, but that doesn't support searching for a value in between of 2 keys. I.e. what we typically have is these keys:
some_function1 at 0x1000
some_function2 at 0x2000
and we look for IP which can be e.g. 0x1010. The bsearch's cmp function currently has no option to say, yes, the last one you asked me was the right one, this one is after it already.

There is bsearch,

Quoted 19 lines · Peter Zijlstra

Quoted 17 lines · Josh Poimboeuf

arch/x86/kernel/unwind_undwarf.c new file +17 -0

+static struct undwarf *__undwarf_lookup(struct undwarf *undwarf,
+					unsigned int num, unsigned long ip)
+{
+	struct undwarf *first = undwarf;
+	struct undwarf *last = undwarf + num - 1;
+	struct undwarf *mid;
+	unsigned long u_ip;
+
+	while (first <= last) {
+		mid = first + ((last - first) / 2);
+		u_ip = undwarf_ip(mid);
+
+		if (ip >= u_ip) {
+			if (ip < u_ip + mid->len)
+				return mid;
+			first = mid + 1;
+		} else

Quoted 8 lines

arch/x86/kernel/unwind_undwarf.c line 63

Quoted 5 lines

arch/x86/kernel/unwind_undwarf.c new file +5 -0

+			last = mid - 1;
+	}
+
+	return NULL;
+}

That's a bog standard binary search thing, don't we have a helper for that someplace?

I wasn't able to find one...

(quoted diff) +31 -0

+static struct undwarf *undwarf_lookup(unsigned long ip)
+{
+	struct undwarf *undwarf;
+	struct module *mod;
+
+	/* Look in vmlinux undwarf section: */
+	undwarf = __undwarf_lookup(__undwarf_start, __undwarf_end - __undwarf_start, ip);
+	if (undwarf)
+		return undwarf;
+
+	/* Look in module undwarf sections: */
+	preempt_disable();
+	mod = __module_address(ip);
+	if (!mod || !mod->arch.undwarf)
+		goto module_out;
+	undwarf = __undwarf_lookup(mod->arch.undwarf, mod->arch.num_undwarves, ip);
+
+module_out:
+	preempt_enable();
+	return undwarf;
+}
 
+bool unwind_next_frame(struct unwind_state *state)
+{
+	struct undwarf *undwarf;
+	unsigned long cfa;
+	bool indirect = false;
+	enum stack_type prev_type = state->stack_info.type;
+	unsigned long ip_p, prev_sp = state->sp;
+
+	if (unwind_done(state))
+		return false;

So we do that lookup for every single frame. That's going to hurt.

Would it make sense to cache the last 'module' in an attempt to at least avoid that lookup again? Something like so:

Quoted 4 lines · Peter Zijlstra

So we do that lookup for every single frame. That's going to hurt.

Would it make sense to cache the last 'module' in an attempt to at least avoid that lookup again? Something like so:

The only thing with caching the module is, what if the module goes away?

Based on your previous comment I was thinking I would disable preemption for the entire unwind_next_frame() step, but not *between* steps. I suppose we could require the unwind caller to disable preemption but I'd like to avoid that if possible.

Quoted 4 lines

Based on your previous comment I was thinking I would disable preemption for the entire unwind_next_frame() step, but not *between* steps. I suppose we could require the unwind caller to disable preemption but I'd like to avoid that if possible.

Right, keeping it disabled across a frame should be ok I suppose.

arch/x86/kernel/unwind_undwarf.c new file +0 -0

@@ -0,0 +1,402 @@

arch/x86/kernel/unwind_undwarf.c new file +15 -0

+void __unwind_start(struct unwind_state *state, struct task_struct *task,
+		    struct pt_regs *regs, unsigned long *first_frame)
+{
+	memset(state, 0, sizeof(*state));
+	state->task = task;
+
+	if (regs) {
+		if (user_mode(regs)) {
+			state->stack_info.type = STACK_TYPE_UNKNOWN;
+			return;
+		}
+
+		state->ip = regs->ip;
+		state->sp = kernel_stack_pointer(regs);
+		state->bp = regs->bp;

Quoted 3 lines · Josh Poimboeuf

arch/x86/kernel/unwind_undwarf.c new file +0 -0

@@ -0,0 +1,402 @@

...

Quoted 19 lines

arch/x86/kernel/unwind_undwarf.c new file +19 -0

+void __unwind_start(struct unwind_state *state, struct task_struct *task,
+		    struct pt_regs *regs, unsigned long *first_frame)
+{
+	memset(state, 0, sizeof(*state));
+	state->task = task;
+
+	if (regs) {
+		if (user_mode(regs)) {
+			state->stack_info.type = STACK_TYPE_UNKNOWN;
+			return;
+		}
+
+		state->ip = regs->ip;
+		state->sp = kernel_stack_pointer(regs);
+		state->bp = regs->bp;
+		state->regs = regs;
+
+	} else if (task == current) {
+		register void *__sp asm(_ASM_SP);

arch/x86/kernel/unwind_undwarf.c line 337

Quoted 6 lines

arch/x86/kernel/unwind_undwarf.c new file +6 -0

+
+		asm volatile("lea (%%rip), %0\n\t"
+			     "mov %%rsp, %1\n\t"
+			     "mov %%rbp, %2\n\t"
+			     : "=r" (state->ip), "=r" (state->sp),
+			       "=r" (state->bp), "+r" (__sp));

Maybe I don't understand this completely, but what is __sp used for here?

arch/x86/kernel/unwind_undwarf.c line 341

Quoted 3 lines

arch/x86/kernel/unwind_undwarf.c new file +3 -0

+		state->regs = NULL;
+
+	} else {

In DWARF unwinder, we also used to do here:

(quoted diff) +4 -0

+#ifdef CONFIG_SMP
+       } else if (task->on_cpu) {
+               return;
+#endif
        } else {

arch/x86/kernel/unwind_undwarf.c line 342

Quoted 1 line

arch/x86/kernel/unwind_undwarf.c new file +1 -0

+		struct inactive_task_frame *frame = (void *)task->thread.sp;

Since there is no inactive_task_frame for tasks currently running (on other CPUs). At least this always held in the past.

Though, the test is indeed racy.

Here's the contents of the undwarf.txt file which explains the 'why' in more detail:

Quoted 2 lines · Josh Poimboeuf

Here's the contents of the undwarf.txt file which explains the 'why' in more detail:

Ok, so the code quality looks pretty convincing to me - the new core 'undwarf' unwinder code is a _lot_ more readable than any of the Dwarf based attempts before.

That we control the debug info generation at build time is icing on the cake to me.

One thing I'd like to see on the list of benefits side of the equation is a size comparison of kernel .text, with frame pointers vs. undwarf, on 64-bit kernels.

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Quoted 4 lines

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

But I'll try to highlight that a little more.

Quoted 8 lines · Josh Poimboeuf

Quoted 4 lines

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

Quoted 4 lines

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

But I'll try to highlight that a little more.

That's relative to a DWARF unwinder. It doesn't appear to be possible to get anywhere near a frame-pointer unwinder due to having to do this log(n) lookup for every single frame.

Quoted 12 lines · Peter Zijlstra

Quoted 11 lines · Josh Poimboeuf

Quoted 4 lines

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

Quoted 5 lines

Quoted 1 line

But I'll try to highlight that a little more.

That's relative to a DWARF unwinder. It doesn't appear to be possible to get anywhere near a frame-pointer unwinder due to having to do this log(n) lookup for every single frame.

This is ~ 20 times faster than my DWARF unwinder by a quick measurement (20000 calls to save_stack_trace via single vfs_write).

Quoted 2 lines

This is ~ 20 times faster than my DWARF unwinder by a quick measurement (20000 calls to save_stack_trace via single vfs_write).

Wow!

Quoted 8 lines · Josh Poimboeuf

Quoted 4 lines

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

Quoted 4 lines

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

But I'll try to highlight that a little more.

That's relative to a DWARF unwinder.

It doesn't appear to be possible to get anywhere near a frame-pointer unwinder due to having to do this log(n) lookup for every single frame.

Quoted 3 lines

It doesn't appear to be possible to get anywhere near a frame-pointer unwinder due to having to do this log(n) lookup for every single frame.

Hm, is there something faster, yet not substantially bigger? Hash? Trie?

Quoted 5 lines

Quoted 4 lines

It doesn't appear to be possible to get anywhere near a frame-pointer unwinder due to having to do this log(n) lookup for every single frame.

Quoted 2 lines

Hm, is there something faster, yet not substantially bigger? Hash? Trie?

Not sure how to make a Hash work with nearest neighbour searches. And a trie will only give you a constant speedup over the binary search but not an improvement in complexity IIRC.

Quoted 9 lines · Peter Zijlstra

Quoted 8 lines · Josh Poimboeuf

Quoted 4 lines

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

Quoted 6 lines

Quoted 4 lines

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

But I'll try to highlight that a little more.

That's relative to a DWARF unwinder.

Yes.

Quoted 3 lines

It doesn't appear to be possible to get anywhere near a frame-pointer unwinder due to having to do this log(n) lookup for every single frame.

Hm, is there something faster, yet not substantially bigger? Hash? Trie?

Quoted 13 lines · Ingo Molnar

Quoted 2 lines · Josh Poimboeuf

Here's the contents of the undwarf.txt file which explains the 'why' in more detail:

Ok, so the code quality looks pretty convincing to me - the new core 'undwarf' unwinder code is a _lot_ more readable than any of the Dwarf based attempts before.

That we control the debug info generation at build time is icing on the cake to me.

Quoted 2 lines

One thing I'd like to see on the list of benefits side of the equation is a size comparison of kernel .text, with frame pointers vs. undwarf, on 64-bit kernels.

Ok, will do a text size comparison. The only difficulty I encountered there is that the 'size' tool considers the .undwarf section to be text for some reason. So the "text" size grew considerably :-)

Quoted 4 lines

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

But I'll try to highlight that a little more.

That's not what I meant! The speedup comes from (hopefully) being able to disable CONFIG_FRAME_POINTER, which:

Quoted 2 lines · Ingo Molnar

That's not what I meant! The speedup comes from (hopefully) being able to disable CONFIG_FRAME_POINTER, which:

BTW when you are mentioning this -- my measurements were with FP disabled.

Is there any reasonably simple-to-use benchmark I could run with FP=y and FP=n quickly?

Quoted 6 lines · Josh Poimboeuf

Quoted 4 lines · Ingo Molnar

Being able to generate more optimal code in the hottest code paths of the kernel is the _real_, primary upstream kernel benefit of a different debuginfo method - which has to be weighed against the pain of introducing a new unwinder. But this submission does not talk about that aspect at all, which should be fixed I think.

Quoted 7 lines

Actually I devoted an entire one-sentence paragraph to performance in the documentation:

The simpler debuginfo format also enables the unwinder to be relatively fast, which is important for perf and lockdep.

But I'll try to highlight that a little more.

That's not what I meant! The speedup comes from (hopefully) being able to disable CONFIG_FRAME_POINTER, which:

- creates simpler/faster function prologues and epilogues - no managing of RBP needed

- gives one more generic purpose register to work from. This matters less on 64-bit kernels but it's a small effect.

I've seen numbers of 1-2% of instruction count reduction in common kernel workloads, which would be pretty significant on well cached workloads.

That's not what I meant! The speedup comes from (hopefully) being able to disable CONFIG_FRAME_POINTER, which:

- creates simpler/faster function prologues and epilogues - no managing of RBP needed

- gives one more generic purpose register to work from. This matters less on 64-bit kernels but it's a small effect.

I've seen numbers of 1-2% of instruction count reduction in common kernel workloads, which would be pretty significant on well cached workloads.

Ccing Mel who did proper measurements and can hopefully comment on his results.

Quoted 11 lines · Ingo Molnar

That's not what I meant! The speedup comes from (hopefully) being able to disable CONFIG_FRAME_POINTER, which:

- creates simpler/faster function prologues and epilogues - no managing of RBP needed

- gives one more generic purpose register to work from. This matters less on 64-bit kernels but it's a small effect.

I've seen numbers of 1-2% of instruction count reduction in common kernel workloads, which would be pretty significant on well cached workloads.