Compile-time stack metadata validation

This is v18 of the compile-time stack metadata validation patch set.

It's based on tip:core/objtool.

v17 can be found here:

https://lkml.kernel.org/r/[email protected]

For more information about the motivation behind this patch set, and more details about what it does, see the patch 7 changelog and tools/objtool/Documentation/stack-validation.txt.

Patches 1-6 mark various directories, files, and functions as "non-standard".

Patches 7-9 add objtool and integrate it into the kernel build.

v18:
- include/linux/objtool.h -> include/linux/frame.h
- __objtool_ignore_func -> __func_stack_frame_non_standard
- reword commit messages and comments a bit
- reorder patches

v17:
- __ex_table fix
- rename stacktool -> objtool
- STACKTOOL_IGNORE_FUNCTION -> STACK_FRAME_NON_STANDARD
- 'STACKTOOL := n' -> 'OBJECT_FILES_NON_STANDARD := y'
- updated global_noreturns list

v16:
- fix all allyesconfig warnings, except for staging
- get rid of STACKTOOL_IGNORE_INSN which is no longer needed
- remove several whitelists in favor of automatically whitelisting any function with a special instruction like ljmp, lret, or vmrun
- split up stacktool patch into 3 parts as suggested by Ingo
- update the global noreturn function list
- detect noreturn function fallthroughs
- skip weak functions in noreturn call detection logic
- add empty function check to noreturn logic
- allow non-section rela symbols for __ex_table sections
- support rare switch table case with jmpq *[addr](%rip)
- don't warn on frame pointer restore without save
- rearrange patch order a bit

v15:
- restructure code for a new cmdline interface "stacktool check" using the new subcommand framework in tools/lib/subcmd
- fix 32 bit build fail (put __sp at end) in paravirt_types.h patch 10 which was reported by 0day

v14:
- make tools/include/linux/list.h self-sufficient
- create FRAME_OFFSET to allow 32-bit code to be able to access function arguments on the stack
- add FRAME_OFFSET usage in crypto patch 14/24: "Create stack frames in aesni-intel_asm.S"
- rename "index" -> "idx" to fix build with some compilers

v13:
- LDFLAGS order fix from Chris J Arges
- new warning fix patches from Chris J Arges
- "--frame-pointer" -> "--check-frame-pointer"

v12:
- rename "stackvalidate" -> "stacktool"
- move from scripts/ to tools/:
- makefile rework
- make a copy of the x86 insn code (and warn if the code diverges)
- use tools/include/linux/list.h
- move warning macros to a new warn.h file
- change wording: "stack validation" -> "stack metadata validation"

v11:
- attempt to answer the "why" question better in the documentation and commit message
- s/FP_SAVE/FRAME_BEGIN/ in documentation

v10:
- add scripts/mod to directory ignores
- remove circular dependencies for ignored objects which are built before stackvalidate
- fix CONFIG_MODVERSIONS incompatibility

v9:
- rename FRAME/ENDFRAME -> FRAME_BEGIN/FRAME_END
- fix jump table issue for when the original instruction is a jump
- drop paravirt thunk alignment patch
- add maintainers to CC for proposed warning fixes

v8:
- add proposed fixes for warnings
- fix all memory leaks
- process ignores earlier and add more ignore checks
- always assume POPCNT alternative is enabled
- drop hweight inline asm fix
- drop __schedule() ignore patch
- change .Ltemp_\@ to .Lstackvalidate_ignore_\@ in asm macro
- fix CONFIG_* checks in asm macros
- add C versions of ignore macros and frame macros
- change ";" to "\n" in C macros
- add ifdef CONFIG_STACK_VALIDATION checks in C ignore macros
- use numbered label in C ignore macro
- add missing break in switch case statement in arch-x86.c

v7:
- sibling call support
- document proposed solution for inline asm() frame pointer issues
- say "kernel entry/exit" instead of "context switch"
- clarify the checking of switch statement jump tables
- discard __stackvalidate_ignore_* sections in linker script
- use .Ltemp_\@ to get a unique label instead of static 3-digit number
- change STACKVALIDATE_IGNORE_FUNC variable to a static
- move STACKVALIDATE_IGNORE_INSN to arch-specific .h file

v6:
- rename asmvalidate -> stackvalidate (again)
- gcc-generated object file support
- recursive branch state analysis
- external jump support
- fixup/exception table support
- jump label support
- switch statement jump table support
- added documentation
- detection of "noreturn" dead end functions
- added a Kbuild mechanism for skipping files and dirs
- moved frame pointer macros to arch/x86/include/asm/frame.h
- moved ignore macros to include/linux/stackvalidate.h

v5:
- stackvalidate -> asmvalidate
- frame pointers only required for non-leaf functions
- check for the use of the FP_SAVE/RESTORE macros instead of manually analyzing code to detect frame pointer usage
- additional checks to ensure each function doesn't leave its boundaries
- make the macros simpler and more flexible
- support for analyzing ALTERNATIVE macros
- simplified the arch interfaces in scripts/asmvalidate/arch.h
- fixed some asmvalidate warnings
- rebased onto latest tip asm cleanups
- many more small changes

v4:
- Changed the default to CONFIG_STACK_VALIDATION=n, until all the asm code can get cleaned up.
- Fixed a stackvalidate error path exit code issue found by Michal Marek.

v3:
- Added a patch to make the push/pop CFI macros arch-independent, as suggested by H. Peter Anvin

v2:
- Fixed memory leaks reported by Petr Mladek

Josh Poimboeuf (9):
objtool: Mark non-standard files and directories
objtool: Add STACK_FRAME_NON_STANDARD macro
x86/xen: Mark xen_cpuid() stack frame as non-standard
bpf: Mark __bpf_prog_run() stack frame as non-standard
sched: Mark __schedule() stack frame as non-standard x86/kprobes: Mark kretprobe_trampoline() stack frame as non-standard
objtool: Compile-time stack metadata validation
objtool: Add CONFIG_STACK_VALIDATION option
objtool: Enable stack metadata validation on x86_64

 MAINTAINERS                                       |   5 +
 Makefile                                          |   5 +-
 arch/Kconfig                                      |   6 +
 arch/x86/Kconfig                                  |   1 +
 arch/x86/boot/Makefile                            |   3 +-
 arch/x86/boot/compressed/Makefile                 |   3 +-
 arch/x86/entry/Makefile                           |   4 +
 arch/x86/entry/vdso/Makefile                      |   6 +-
 arch/x86/kernel/Makefile                          |  11 +-
 arch/x86/kernel/kprobes/core.c                    |   2 +
 arch/x86/kernel/vmlinux.lds.S                     |   5 +-
 arch/x86/platform/efi/Makefile                    |   2 +
 arch/x86/purgatory/Makefile                       |   2 +
 arch/x86/realmode/Makefile                        |   4 +-
 arch/x86/realmode/rm/Makefile                     |   3 +-
 arch/x86/xen/enlighten.c                          |   3 +-
 drivers/firmware/efi/libstub/Makefile             |   1 +
 include/linux/frame.h                             |  23 +
 kernel/bpf/core.c                                 |   2 +
 kernel/sched/core.c                               |   2 +
 lib/Kconfig.debug                                 |  12 +
 scripts/Makefile.build                            |  39 +-
 scripts/mod/Makefile                              |   2 +
 tools/Makefile                                    |  14 +-
 tools/objtool/.gitignore                          |   2 +
 tools/objtool/Build                               |  13 +
 tools/objtool/Documentation/stack-validation.txt  | 340 ++++++++
 tools/objtool/Makefile                            |  60 ++
 tools/objtool/arch.h                              |  44 +
 tools/objtool/arch/x86/Build                      |  12 +
 tools/objtool/arch/x86/decode.c                   | 172 ++++
 tools/objtool/arch/x86/insn/gen-insn-attr-x86.awk | 387 +++++++++
 tools/objtool/arch/x86/insn/inat.c                |  97 +++
 tools/objtool/arch/x86/insn/inat.h                | 221 +++++
 tools/objtool/arch/x86/insn/inat_types.h          |  29 +
 tools/objtool/arch/x86/insn/insn.c                | 594 +++++++++++++
 tools/objtool/arch/x86/insn/insn.h                | 201 +++++
 tools/objtool/arch/x86/insn/x86-opcode-map.txt    | 984 +++++++++++++++++++++
 tools/objtool/builtin-check.c                     | 993 ++++++++++++++++++++++
 tools/objtool/builtin.h                           |  22 +
 tools/objtool/elf.c                               | 403 +++++++++
 tools/objtool/elf.h                               |  79 ++
 tools/objtool/objtool.c                           | 134 +++
 tools/objtool/special.c                           | 193 +++++
 tools/objtool/special.h                           |  42 +
 tools/objtool/warn.h                              |  60 ++
 46 files changed, 5220 insertions(+), 22 deletions(-)
 create mode 100644 include/linux/frame.h
 create mode 100644 tools/objtool/.gitignore
 create mode 100644 tools/objtool/Build
 create mode 100644 tools/objtool/Documentation/stack-validation.txt
 create mode 100644 tools/objtool/Makefile
 create mode 100644 tools/objtool/arch.h
 create mode 100644 tools/objtool/arch/x86/Build
 create mode 100644 tools/objtool/arch/x86/decode.c
 create mode 100644 tools/objtool/arch/x86/insn/gen-insn-attr-x86.awk
 create mode 100644 tools/objtool/arch/x86/insn/inat.c
 create mode 100644 tools/objtool/arch/x86/insn/inat.h
 create mode 100644 tools/objtool/arch/x86/insn/inat_types.h
 create mode 100644 tools/objtool/arch/x86/insn/insn.c
 create mode 100644 tools/objtool/arch/x86/insn/insn.h
 create mode 100644 tools/objtool/arch/x86/insn/x86-opcode-map.txt
 create mode 100644 tools/objtool/builtin-check.c
 create mode 100644 tools/objtool/builtin.h
 create mode 100644 tools/objtool/elf.c
 create mode 100644 tools/objtool/elf.h
 create mode 100644 tools/objtool/objtool.c
 create mode 100644 tools/objtool/special.c
 create mode 100644 tools/objtool/special.h
 create mode 100644 tools/objtool/warn.h

2.4.3

Code which runs outside the kernel's normal mode of operation often does unusual things which can cause a static analysis tool like objtool to emit false positive warnings:

- boot image
- vdso image
- relocation
- realmode
- efi
- head
- purgatory
- modpost

Set OBJECT_FILES_NON_STANDARD for their related files and directories, which will tell objtool to skip checking them. It's ok to skip them because they don't affect runtime stack traces.

Also skip the following code which does the right thing with respect to frame pointers, but is too "special" to be validated by a tool:

- entry
- mcount

Also skip the test_nx module because it modifies its exception handling table at runtime, which objtool can't understand. Fortunately it's just a test module so it doesn't matter much.

Currently objtool is the only user of OBJECT_FILES_NON_STANDARD, but it might eventually be useful for other tools.

---
 arch/x86/boot/Makefile                |  3 ++-
 arch/x86/boot/compressed/Makefile     |  3 ++-
 arch/x86/entry/Makefile               |  4 ++++
 arch/x86/entry/vdso/Makefile          |  6 ++++--
 arch/x86/kernel/Makefile              | 11 ++++++++---
 arch/x86/platform/efi/Makefile        |  2 ++
 arch/x86/purgatory/Makefile           |  2 ++
 arch/x86/realmode/Makefile            |  4 +++-
 arch/x86/realmode/rm/Makefile         |  3 ++-
 drivers/firmware/efi/libstub/Makefile |  1 +
 scripts/mod/Makefile                  |  2 ++
 11 files changed, 32 insertions(+), 9 deletions(-)

index bbe1a62..0bf6749 100644
@@ -9,7 +9,8 @@
 # Changed by many, many contributors over the years.
 #
 
-KASAN_SANITIZE := n
+KASAN_SANITIZE			:= n
+OBJECT_FILES_NON_STANDARD	:= y
 
 # If you want to preset the SVGA mode, uncomment the next line and
 # set SVGA_MODE to whatever number you want.

index f9ce75d..5e1d26e 100644
@@ -16,7 +16,8 @@
 #	(see scripts/Makefile.lib size_append)
 #	compressed vmlinux.bin.all + u32 size of vmlinux.bin.all
 
-KASAN_SANITIZE := n
+KASAN_SANITIZE			:= n
+OBJECT_FILES_NON_STANDARD	:= y
 
 targets := vmlinux vmlinux.bin vmlinux.bin.gz vmlinux.bin.bz2 vmlinux.bin.lzma \
 	vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4

index bd55ded..fe91c25 100644
@@ -1,6 +1,10 @@
 #
 # 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
+
 obj-y				:= entry_$(BITS).o thunk_$(BITS).o syscall_$(BITS).o
 obj-y				+= common.o
 

index c854541..f9fb859 100644
@@ -3,8 +3,9 @@
 #
 
 KBUILD_CFLAGS += $(DISABLE_LTO)
-KASAN_SANITIZE := n
-UBSAN_SANITIZE := n
+KASAN_SANITIZE			:= n
+UBSAN_SANITIZE			:= n
+OBJECT_FILES_NON_STANDARD	:= y
 
 VDSO64-$(CONFIG_X86_64)		:= y
 VDSOX32-$(CONFIG_X86_X32_ABI)	:= y

@@ -16,6 +17,7 @@ vobjs-y := vdso-note.o vclock_gettime.o vgetcpu.o
 
 # files to link into kernel
 obj-y				+= vma.o
+OBJECT_FILES_NON_STANDARD_vma.o	:= n
 
 # vDSO images to build
 vdso_img-$(VDSO64-y)		+= 64

index b1b78ff..d5fb087 100644
@@ -16,9 +16,14 @@ CFLAGS_REMOVE_ftrace.o = -pg
 CFLAGS_REMOVE_early_printk.o = -pg
 endif
 
-KASAN_SANITIZE_head$(BITS).o := n
-KASAN_SANITIZE_dumpstack.o := n
-KASAN_SANITIZE_dumpstack_$(BITS).o := n
+KASAN_SANITIZE_head$(BITS).o				:= n
+KASAN_SANITIZE_dumpstack.o				:= n
+KASAN_SANITIZE_dumpstack_$(BITS).o			:= n
+
+OBJECT_FILES_NON_STANDARD_head_$(BITS).o		:= y
+OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o	:= y
+OBJECT_FILES_NON_STANDARD_mcount_$(BITS).o		:= y
+OBJECT_FILES_NON_STANDARD_test_nx.o			:= y
 
 CFLAGS_irq.o := -I$(src)/../include/asm/trace
 

index 2846aaa..066619b 100644
@@ -1,3 +1,5 @@
+OBJECT_FILES_NON_STANDARD_efi_thunk_$(BITS).o := y
+
 obj-$(CONFIG_EFI) 		+= quirks.o efi.o efi_$(BITS).o efi_stub_$(BITS).o
 obj-$(CONFIG_ACPI_BGRT) += efi-bgrt.o
 obj-$(CONFIG_EARLY_PRINTK_EFI)	+= early_printk.o

index 2c835e3..92e3e1d 100644
@@ -1,3 +1,5 @@
+OBJECT_FILES_NON_STANDARD := y
+
 purgatory-y := purgatory.o stack.o setup-x86_$(BITS).o sha256.o entry64.o string.o
 
 targets += $(purgatory-y)

index e02c2c6..682c895 100644
@@ -6,7 +6,9 @@
 # for more details.
 #
 #
-KASAN_SANITIZE := n
+KASAN_SANITIZE			:= n
+OBJECT_FILES_NON_STANDARD	:= y
+
 subdir- := rm
 
 obj-y += init.o

index 3e75fcf..053abe7b0 100644
@@ -6,7 +6,8 @@
 # for more details.
 #
 #
-KASAN_SANITIZE := n
+KASAN_SANITIZE			:= n
+OBJECT_FILES_NON_STANDARD	:= y
 
 always := realmode.bin realmode.relocs
 

index aaf9c0b..68fa977 100644
@@ -23,6 +23,7 @@ KBUILD_CFLAGS			:= $(cflags-y) -DDISABLE_BRANCH_PROFILING \
 GCOV_PROFILE			:= n
 KASAN_SANITIZE			:= n
 UBSAN_SANITIZE			:= n
+OBJECT_FILES_NON_STANDARD	:= y
 
 lib-y				:= efi-stub-helper.o
 

index c11212f..19d9bca 100644
@@ -1,3 +1,5 @@
+OBJECT_FILES_NON_STANDARD := y
+
 hostprogs-y	:= modpost mk_elfconfig
 always		:= $(hostprogs-y) empty.o
 

2.4.3

Add a new macro, STACK_FRAME_NON_STANDARD, which is used to denote a function which does something unusual related to its stack frame. Use of the macro prevents objtool from emitting a false positive warning.

---
 arch/x86/kernel/vmlinux.lds.S |  5 ++++-
 include/linux/frame.h         | 23 +++++++++++++++++++++++
 2 files changed, 27 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/frame.h

index 92dc211..13fa0ad 100644
@@ -343,7 +343,10 @@ SECTIONS
 
 	/* Sections to be discarded */
 	DISCARDS
-	/DISCARD/ : { *(.eh_frame) }
+	/DISCARD/ : {
+		*(.eh_frame)
+		*(__func_stack_frame_non_standard)
+	}
 }
 
 

new file mode 100644
index 0000000..e6baaba
@@ -0,0 +1,23 @@
+#ifndef _LINUX_FRAME_H
+#define _LINUX_FRAME_H
+
+#ifdef CONFIG_STACK_VALIDATION
+/*
+ * This macro marks the given function's stack frame as "non-standard", which
+ * tells objtool to ignore the function when doing stack metadata validation.
+ * It should only be used in special cases where you're 100% sure it won't
+ * affect the reliability of frame pointers and kernel stack traces.
+ *
+ * For more information, see tools/objtool/Documentation/stack-validation.txt.
+ */
+#define STACK_FRAME_NON_STANDARD(func) \
+	static void __used __section(__func_stack_frame_non_standard) \
+		*__func_stack_frame_non_standard_##func = func
+
+#else /* !CONFIG_STACK_VALIDATION */
+
+#define STACK_FRAME_NON_STANDARD(func)
+
+#endif /* CONFIG_STACK_VALIDATION */
+
+#endif /* _LINUX_FRAME_H */

2.4.3

'objtool check' reports the following false positive warning:

objtool: arch/x86/xen/enlighten.o: xen_cpuid()+0x41: can't find jump dest instruction at .text+0x108

The warning is due to xen_cpuid()'s use of XEN_EMULATE_PREFIX to insert some fake instructions which objtool doesn't know how to decode.

---
 arch/x86/xen/enlighten.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index d09e4c9..5c45a69 100644
@@ -32,6 +32,7 @@
 #include <linux/gfp.h>
 #include <linux/memblock.h>
 #include <linux/edd.h>
+#include <linux/frame.h>
 
 #ifdef CONFIG_KEXEC_CORE
 #include <linux/kexec.h>

@@ -351,8 +352,8 @@ static void xen_cpuid(unsigned int *ax, unsigned int *bx,
 	*cx &= maskecx;
 	*cx |= setecx;
 	*dx &= maskedx;
-
 }
+STACK_FRAME_NON_STANDARD(xen_cpuid); /* XEN_EMULATE_PREFIX */
 
 static bool __init xen_check_mwait(void)
 {

2.4.3

objtool reports the following false positive warnings:

objtool: kernel/bpf/core.o: __bpf_prog_run()+0x5c: sibling call from callable instruction with changed frame pointer
objtool: kernel/bpf/core.o: __bpf_prog_run()+0x60: function has unreachable instruction
objtool: kernel/bpf/core.o: __bpf_prog_run()+0x64: function has unreachable instruction
[...]

It's confused by the following dynamic jump instruction in __bpf_prog_run()::

jmp *(%r12,%rax,8)

which corresponds to the following line in the C code:

  goto *jumptable[insn->code];

There's no way for objtool to deterministically find all possible branch targets for a dynamic jump, so it can't verify this code.

In this case the jumps all stay within the function, and there's nothing unusual going on related to the stack, so we can whitelist the function.

---
 kernel/bpf/core.c | 2 ++
 1 file changed, 2 insertions(+)

index 972d9a8..be0abf6 100644
@@ -27,6 +27,7 @@
 #include <linux/random.h>
 #include <linux/moduleloader.h>
 #include <linux/bpf.h>
+#include <linux/frame.h>
 
 #include <asm/unaligned.h>
 

@@ -649,6 +650,7 @@ load_byte:
 		WARN_RATELIMIT(1, "unknown opcode %02x\n", insn->code);
 		return 0;
 }
+STACK_FRAME_NON_STANDARD(__bpf_prog_run); /* jump table */
 
 bool bpf_prog_array_compatible(struct bpf_array *array,
 			       const struct bpf_prog *fp)

2.4.3

objtool reports the following warnings for __schedule():

objtool: kernel/sched/core.o: __schedule()+0x3c0: duplicate frame pointer save
objtool: kernel/sched/core.o: __schedule()+0x3fd: sibling call from callable instruction with changed frame pointer
objtool: kernel/sched/core.o: __schedule()+0x40a: call without frame pointer save/setup
objtool: kernel/sched/core.o: __schedule()+0x7fd: frame pointer state mismatch
objtool: kernel/sched/core.o: __schedule()+0x421: frame pointer state mismatch

Basically it's confused by two unusual attributes of the switch_to() macro:

1. It saves prev's frame pointer to the old stack and restores next's frame pointer from the new stack.

2. For new tasks it jumps directly to ret_from_fork.

Eventually it would probably be a good idea to clean up the ret_from_fork hack so that new tasks are created with a valid initial stack, as suggested by Andy:

https://lkml.kernel.org/r/CALCETrWsqCw4L1qKO9j9L5F+4ED4viuLQTFc=n1pKBZfFPQUFg@mail.gmail.com

Then __schedule() could return normally into the new code and objtool hopefully wouldn't have a problem anymore.

In the meantime, mark its stack frame as non-standard so we can have a baseline with no objtool warnings. The marker also serves as a reminder that this code could be improved a bit.

---
 kernel/sched/core.c | 2 ++
 1 file changed, 2 insertions(+)

index 9503d59..641043d 100644
@@ -74,6 +74,7 @@
 #include <linux/binfmts.h>
 #include <linux/context_tracking.h>
 #include <linux/compiler.h>
+#include <linux/frame.h>
 
 #include <asm/switch_to.h>
 #include <asm/tlb.h>

@@ -3288,6 +3289,7 @@ static void __sched notrace __schedule(bool preempt)
 
 	balance_callback(rq);
 }
+STACK_FRAME_NON_STANDARD(__schedule); /* switch_to() */
 
 static inline void sched_submit_work(struct task_struct *tsk)
 {

2.4.3

objtool reports the following warning for kretprobe_trampoline():

objtool: arch/x86/kernel/kprobes/core.o: kretprobe_trampoline()+0x20: call without frame pointer save/setup

kretprobes are a special case where the stack is intentionally wrong. The return address isn't known at the beginning of the trampoline, so the stack frame can't be set up properly before it calls trampoline_handler().

Because kretprobe handlers don't sleep, the frame pointer doesn't *have* to be accurate in the trampoline. So it's ok to tell objtool to ignore it. This results in no actual changes to the generated code.

---
 arch/x86/kernel/kprobes/core.c | 2 ++
 1 file changed, 2 insertions(+)

index 48acaac..ae703ac 100644
@@ -49,6 +49,7 @@
 #include <linux/kdebug.h>
 #include <linux/kallsyms.h>
 #include <linux/ftrace.h>
+#include <linux/frame.h>
 
 #include <asm/cacheflush.h>
 #include <asm/desc.h>

@@ -703,6 +704,7 @@ asm(
 	".size kretprobe_trampoline, .-kretprobe_trampoline\n"
 );
 NOKPROBE_SYMBOL(kretprobe_trampoline);
+STACK_FRAME_NON_STANDARD(kretprobe_trampoline);
 
 /*
  * Called from kretprobe_trampoline

2.4.3

This adds a host tool named objtool which has a 'check' subcommand which analyzes .o files to ensure the validity of stack metadata. It enforces a set of rules on asm code and C inline assembly code so that stack traces can be reliable.

For each function, it recursively follows all possible code paths and validates the correct frame pointer state at each instruction.

It also follows code paths involving kernel special sections, like .altinstructions, __jump_table, and __ex_table, which can add alternative execution paths to a given instruction (or set of instructions). Similarly, it knows how to follow switch statements, for which gcc sometimes uses jump tables.

Here are some of the benefits of validating stack metadata:

a) More reliable stack traces for frame pointer enabled kernels

Frame pointers are used for debugging purposes. They allow runtime code and debug tools to be able to walk the stack to determine the chain of function call sites that led to the currently executing code.

For some architectures, frame pointers are enabled by CONFIG_FRAME_POINTER. For some other architectures they may be required by the ABI (sometimes referred to as "backchain pointers").

For C code, gcc automatically generates instructions for setting up frame pointers when the -fno-omit-frame-pointer option is used.

But for asm code, the frame setup instructions have to be written by hand, which most people don't do. So the end result is that CONFIG_FRAME_POINTER is honored for C code but not for most asm code.

For stack traces based on frame pointers to be reliable, all functions which call other functions must first create a stack frame and update the frame pointer. If a first function doesn't properly create a stack frame before calling a second function, the *caller* of the first function will be skipped on the stack trace.

For example, consider the following example backtrace with frame pointers enabled:

     [<ffffffff81812584>] dump_stack+0x4b/0x63
     [<ffffffff812d6dc2>] cmdline_proc_show+0x12/0x30
     [<ffffffff8127f568>] seq_read+0x108/0x3e0
     [<ffffffff812cce62>] proc_reg_read+0x42/0x70
     [<ffffffff81256197>] __vfs_read+0x37/0x100
     [<ffffffff81256b16>] vfs_read+0x86/0x130
     [<ffffffff81257898>] SyS_read+0x58/0xd0
     [<ffffffff8181c1f2>] entry_SYSCALL_64_fastpath+0x12/0x76

It correctly shows that the caller of cmdline_proc_show() is seq_read().

If we remove the frame pointer logic from cmdline_proc_show() by replacing the frame pointer related instructions with nops, here's what it looks like instead:

     [<ffffffff81812584>] dump_stack+0x4b/0x63
     [<ffffffff812d6dc2>] cmdline_proc_show+0x12/0x30
     [<ffffffff812cce62>] proc_reg_read+0x42/0x70
     [<ffffffff81256197>] __vfs_read+0x37/0x100
     [<ffffffff81256b16>] vfs_read+0x86/0x130
     [<ffffffff81257898>] SyS_read+0x58/0xd0
     [<ffffffff8181c1f2>] entry_SYSCALL_64_fastpath+0x12/0x76

Notice that cmdline_proc_show()'s caller, seq_read(), has been skipped. Instead the stack trace seems to show that cmdline_proc_show() was called by proc_reg_read().

The benefit of 'objtool check' here is that because it ensures that *all* functions honor CONFIG_FRAME_POINTER, no functions will ever[*] be skipped on a stack trace.

[*] unless an interrupt or exception has occurred at the very
beginning of a function before the stack frame has been created, or at the very end of the function after the stack frame has been destroyed. This is an inherent limitation of frame pointers.

b) 100% reliable stack traces for DWARF enabled kernels

This is not yet implemented. For more details about what is planned, see tools/objtool/Documentation/stack-validation.txt.

c) Higher live patching compatibility rate

This is not yet implemented. For more details about what is planned, see tools/objtool/Documentation/stack-validation.txt.

To achieve the validation, 'objtool check' enforces the following rules:

1. Each callable function must be annotated as such with the ELF function type. In asm code, this is typically done using the ENTRY/ENDPROC macros. If objtool finds a return instruction outside of a function, it flags an error since that usually indicates callable code which should be annotated accordingly.

This rule is needed so that objtool can properly identify each callable function in order to analyze its stack metadata.

2. Conversely, each section of code which is *not* callable should *not* be annotated as an ELF function. The ENDPROC macro shouldn't be used in this case.

This rule is needed so that objtool can ignore non-callable code. Such code doesn't have to follow any of the other rules.

3. Each callable function which calls another function must have the correct frame pointer logic, if required by CONFIG_FRAME_POINTER or the architecture's back chain rules. This can by done in asm code with the FRAME_BEGIN/FRAME_END macros.

This rule ensures that frame pointer based stack traces will work as designed. If function A doesn't create a stack frame before calling function B, the _caller_ of function A will be skipped on the stack trace.

4. Dynamic jumps and jumps to undefined symbols are only allowed if:

a) the jump is part of a switch statement; or

b) the jump matches sibling call semantics and the frame pointer has the same value it had on function entry.

This rule is needed so that objtool can reliably analyze all of a function's code paths. If a function jumps to code in another file, and it's not a sibling call, objtool has no way to follow the jump because it only analyzes a single file at a time.

5. A callable function may not execute kernel entry/exit instructions. The only code which needs such instructions is kernel entry code, which shouldn't be be in callable functions anyway.

This rule is just a sanity check to ensure that callable functions return normally.

It currently only supports x86_64. I tried to make the code generic so that support for other architectures can hopefully be plugged in relatively easily.

On my Lenovo laptop with a i7-4810MQ 4-core/8-thread CPU, building the kernel with objtool checking every .o file adds about three seconds of total build time. It hasn't been optimized for performance yet, so there are probably some opportunities for better build performance.

---
 MAINTAINERS                                       |   5 +
 tools/Makefile                                    |  14 +-
 tools/objtool/.gitignore                          |   2 +
 tools/objtool/Build                               |  13 +
 tools/objtool/Documentation/stack-validation.txt  | 340 ++++++++
 tools/objtool/Makefile                            |  60 ++
 tools/objtool/arch.h                              |  44 +
 tools/objtool/arch/x86/Build                      |  12 +
 tools/objtool/arch/x86/decode.c                   | 172 ++++
 tools/objtool/arch/x86/insn/gen-insn-attr-x86.awk | 387 +++++++++
 tools/objtool/arch/x86/insn/inat.c                |  97 +++
 tools/objtool/arch/x86/insn/inat.h                | 221 +++++
 tools/objtool/arch/x86/insn/inat_types.h          |  29 +
 tools/objtool/arch/x86/insn/insn.c                | 594 +++++++++++++
 tools/objtool/arch/x86/insn/insn.h                | 201 +++++
 tools/objtool/arch/x86/insn/x86-opcode-map.txt    | 984 +++++++++++++++++++++
 tools/objtool/builtin-check.c                     | 993 ++++++++++++++++++++++
 tools/objtool/builtin.h                           |  22 +
 tools/objtool/elf.c                               | 403 +++++++++
 tools/objtool/elf.h                               |  79 ++
 tools/objtool/objtool.c                           | 134 +++
 tools/objtool/special.c                           | 193 +++++
 tools/objtool/special.h                           |  42 +
 tools/objtool/warn.h                              |  60 ++
 24 files changed, 5095 insertions(+), 6 deletions(-)
 create mode 100644 tools/objtool/.gitignore
 create mode 100644 tools/objtool/Build
 create mode 100644 tools/objtool/Documentation/stack-validation.txt
 create mode 100644 tools/objtool/Makefile
 create mode 100644 tools/objtool/arch.h
 create mode 100644 tools/objtool/arch/x86/Build
 create mode 100644 tools/objtool/arch/x86/decode.c
 create mode 100644 tools/objtool/arch/x86/insn/gen-insn-attr-x86.awk
 create mode 100644 tools/objtool/arch/x86/insn/inat.c
 create mode 100644 tools/objtool/arch/x86/insn/inat.h
 create mode 100644 tools/objtool/arch/x86/insn/inat_types.h
 create mode 100644 tools/objtool/arch/x86/insn/insn.c
 create mode 100644 tools/objtool/arch/x86/insn/insn.h
 create mode 100644 tools/objtool/arch/x86/insn/x86-opcode-map.txt
 create mode 100644 tools/objtool/builtin-check.c
 create mode 100644 tools/objtool/builtin.h
 create mode 100644 tools/objtool/elf.c
 create mode 100644 tools/objtool/elf.h
 create mode 100644 tools/objtool/objtool.c
 create mode 100644 tools/objtool/special.c
 create mode 100644 tools/objtool/special.h
 create mode 100644 tools/objtool/warn.h

index 2fa3303..545daaf 100644
@@ -7778,6 +7778,11 @@ L:	[email protected] (moderated for non-subscribers)
 S:	Maintained
 F:	sound/soc/codecs/tfa9879*
 
+OBJTOOL
+M:	Josh Poimboeuf <[email protected]>
+S:	Supported
+F:	tools/objtool/
+
 OMAP SUPPORT
 M:	Tony Lindgren <[email protected]>
 L:	[email protected]

index 6339f6a..cc2a37d 100644
@@ -20,6 +20,7 @@ help:
 	@echo '  perf                   - Linux performance measurement and analysis tool'
 	@echo '  selftests              - various kernel selftests'
 	@echo '  spi                    - spi tools'
+	@echo '  objtool                - an ELF object analysis tool'
 	@echo '  tmon                   - thermal monitoring and tuning tool'
 	@echo '  turbostat              - Intel CPU idle stats and freq reporting tool'
 	@echo '  usb                    - USB testing tools'

@@ -53,7 +54,7 @@ acpi: FORCE
 cpupower: FORCE
 	$(call descend,power/$@)
 
-cgroup firewire hv guest spi usb virtio vm net iio: FORCE
+cgroup firewire hv guest spi usb virtio vm net iio objtool: FORCE
 	$(call descend,$@)
 
 liblockdep: FORCE

@@ -85,7 +86,7 @@ freefall: FORCE
 all: acpi cgroup cpupower hv firewire lguest \
 		perf selftests turbostat usb \
 		virtio vm net x86_energy_perf_policy \
-		tmon freefall
+		tmon freefall objtool
 
 acpi_install:
 	$(call descend,power/$(@:_install=),install)

@@ -93,7 +94,7 @@ acpi_install:
 cpupower_install:
 	$(call descend,power/$(@:_install=),install)
 
-cgroup_install firewire_install hv_install lguest_install perf_install usb_install virtio_install vm_install net_install:
+cgroup_install firewire_install hv_install lguest_install perf_install usb_install virtio_install vm_install net_install objtool_install:
 	$(call descend,$(@:_install=),install)
 
 selftests_install:

@@ -111,7 +112,7 @@ freefall_install:
 install: acpi_install cgroup_install cpupower_install hv_install firewire_install lguest_install \
 		perf_install selftests_install turbostat_install usb_install \
 		virtio_install vm_install net_install x86_energy_perf_policy_install \
-		tmon_install freefall_install
+		tmon_install freefall_install objtool_install
 
 acpi_clean:
 	$(call descend,power/acpi,clean)

@@ -119,7 +120,7 @@ acpi_clean:
 cpupower_clean:
 	$(call descend,power/cpupower,clean)
 
-cgroup_clean hv_clean firewire_clean lguest_clean spi_clean usb_clean virtio_clean vm_clean net_clean iio_clean:
+cgroup_clean hv_clean firewire_clean lguest_clean spi_clean usb_clean virtio_clean vm_clean net_clean iio_clean objtool_clean:
 	$(call descend,$(@:_clean=),clean)
 
 liblockdep_clean:

@@ -155,6 +156,7 @@ build_clean:
 clean: acpi_clean cgroup_clean cpupower_clean hv_clean firewire_clean lguest_clean \
 		perf_clean selftests_clean turbostat_clean spi_clean usb_clean virtio_clean \
 		vm_clean net_clean iio_clean x86_energy_perf_policy_clean tmon_clean \
-		freefall_clean build_clean libbpf_clean libsubcmd_clean liblockdep_clean
+		freefall_clean build_clean libbpf_clean libsubcmd_clean liblockdep_clean \
+		objtool_clean
 
 .PHONY: FORCE

new file mode 100644
index 0000000..a0b3128
@@ -0,0 +1,2 @@
+arch/x86/insn/inat-tables.c
+objtool

new file mode 100644
index 0000000..0e89258
@@ -0,0 +1,13 @@
+objtool-y += arch/$(ARCH)/
+objtool-y += builtin-check.o
+objtool-y += elf.o
+objtool-y += special.o
+objtool-y += objtool.o
+
+objtool-y += libstring.o
+
+CFLAGS += -I$(srctree)/tools/lib
+
+$(OUTPUT)libstring.o: ../lib/string.c FORCE
+	$(call rule_mkdir)
+	$(call if_changed_dep,cc_o_c)

new file mode 100644
index 0000000..debbdb0
@@ -0,0 +1,12 @@
+objtool-y += decode.o
+
+inat_tables_script = arch/x86/insn/gen-insn-attr-x86.awk
+inat_tables_maps = arch/x86/insn/x86-opcode-map.txt
+
+$(OUTPUT)arch/x86/insn/inat-tables.c: $(inat_tables_script) $(inat_tables_maps)
+	$(call rule_mkdir)
+	$(Q)$(call echo-cmd,gen)$(AWK) -f $(inat_tables_script) $(inat_tables_maps) > $@
+
+$(OUTPUT)arch/x86/decode.o: $(OUTPUT)arch/x86/insn/inat-tables.c
+
+CFLAGS_decode.o += -I$(OUTPUT)arch/x86/insn

new file mode 100644
index 0000000..cb3c20c
@@ -0,0 +1,29 @@
+#ifndef _ASM_X86_INAT_TYPES_H
+#define _ASM_X86_INAT_TYPES_H
+/*
+ * x86 instruction attributes
+ *
+ * Written by Masami Hiramatsu <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ */
+
+/* Instruction attributes */
+typedef unsigned int insn_attr_t;
+typedef unsigned char insn_byte_t;
+typedef signed int insn_value_t;
+
+#endif

new file mode 100644
index 0000000..34d2ba7

2.4.3

Part of the diff is not shown here. View the raw message.

Add a CONFIG_STACK_VALIDATION option which will run "objtool check" for each .o file to ensure the validity of its stack metadata.

---
 Makefile               |  5 ++++-
 arch/Kconfig           |  6 ++++++
 lib/Kconfig.debug      | 12 ++++++++++++
 scripts/Makefile.build | 39 +++++++++++++++++++++++++++++++++++----
 4 files changed, 57 insertions(+), 5 deletions(-)

index fbe1b92..62be03b 100644
@@ -993,7 +993,10 @@ prepare0: archprepare FORCE
 	$(Q)$(MAKE) $(build)=.
 
 # All the preparing..
-prepare: prepare0
+prepare: prepare0 prepare-objtool
+
+PHONY += prepare-objtool
+prepare-objtool: $(if $(CONFIG_STACK_VALIDATION), tools/objtool FORCE)
 
 # Generate some files
 # ---------------------------------------------------------------------------

index f6b649d..81869a5 100644
@@ -583,6 +583,12 @@ config HAVE_COPY_THREAD_TLS
 	  normal C parameter passing, rather than extracting the syscall
 	  argument from pt_regs.
 
+config HAVE_STACK_VALIDATION
+	bool
+	help
+	  Architecture supports the 'objtool check' host tool command, which
+	  performs compile-time stack metadata validation.
+
 #
 # ABI hall of shame
 #

index 8bfd1ac..8552656 100644
@@ -342,6 +342,18 @@ config FRAME_POINTER
 	  larger and slower, but it gives very useful debugging information
 	  in case of kernel bugs. (precise oopses/stacktraces/warnings)
 
+config STACK_VALIDATION
+	bool "Compile-time stack metadata validation"
+	depends on HAVE_STACK_VALIDATION
+	default n
+	help
+	  Add compile-time checks to validate stack metadata, including frame
+	  pointers (if CONFIG_FRAME_POINTER is enabled).  This helps ensure
+	  that runtime stack traces are more reliable.
+
+	  For more information, see
+	  tools/objtool/Documentation/stack-validation.txt.
+
 config DEBUG_FORCE_WEAK_PER_CPU
 	bool "Force weak per-cpu definitions"
 	depends on DEBUG_KERNEL

index 2c47f9c..130a452 100644
@@ -241,10 +241,32 @@ cmd_record_mcount =						\
 	fi;
 endif
 
+ifdef CONFIG_STACK_VALIDATION
+
+__objtool_obj := $(objtree)/tools/objtool/objtool
+
+objtool_args = check
+ifndef CONFIG_FRAME_POINTER
+objtool_args += --no-fp
+endif
+
+# 'OBJECT_FILES_NON_STANDARD := y': skip objtool checking for a directory
+# 'OBJECT_FILES_NON_STANDARD_foo.o := 'y': skip objtool checking for a file
+# 'OBJECT_FILES_NON_STANDARD_foo.o := 'n': override directory skip for a file
+cmd_objtool = $(if $(patsubst y%,, \
+	$(OBJECT_FILES_NON_STANDARD_$(basetarget).o)$(OBJECT_FILES_NON_STANDARD)n), \
+	$(__objtool_obj) $(objtool_args) "$(@)";)
+objtool_obj = $(if $(patsubst y%,, \
+	$(OBJECT_FILES_NON_STANDARD_$(basetarget).o)$(OBJECT_FILES_NON_STANDARD)n), \
+	$(__objtool_obj))
+
+endif # CONFIG_STACK_VALIDATION
+
 define rule_cc_o_c
 	$(call echo-cmd,checksrc) $(cmd_checksrc)			  \
 	$(call echo-cmd,cc_o_c) $(cmd_cc_o_c);				  \
 	$(cmd_modversions)						  \
+	$(cmd_objtool)						  \
 	$(call echo-cmd,record_mcount)					  \
 	$(cmd_record_mcount)						  \
 	scripts/basic/fixdep $(depfile) $@ '$(call make-cmd,cc_o_c)' >    \

@@ -253,14 +275,23 @@ define rule_cc_o_c
 	mv -f $(dot-target).tmp $(dot-target).cmd
 endef
 
+define rule_as_o_S
+	$(call echo-cmd,as_o_S) $(cmd_as_o_S);				  \
+	$(cmd_objtool)						  \
+	scripts/basic/fixdep $(depfile) $@ '$(call make-cmd,as_o_S)' >    \
+	                                              $(dot-target).tmp;  \
+	rm -f $(depfile);						  \
+	mv -f $(dot-target).tmp $(dot-target).cmd
+endef
+
 # Built-in and composite module parts
-$(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
+$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_obj) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 
 # Single-part modules are special since we need to mark them in $(MODVERDIR)
 
-$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
+$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_obj) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 	@{ echo $(@:.o=.ko); echo $@; } > $(MODVERDIR)/$(@F:.o=.mod)

@@ -290,8 +321,8 @@ $(obj)/%.s: $(src)/%.S FORCE
 quiet_cmd_as_o_S = AS $(quiet_modtag)  $@
 cmd_as_o_S       = $(CC) $(a_flags) -c -o $@ $<
 
-$(obj)/%.o: $(src)/%.S FORCE
-	$(call if_changed_dep,as_o_S)
+$(obj)/%.o: $(src)/%.S $(objtool_obj) FORCE
+	$(call if_changed_rule,as_o_S)
 
 targets += $(real-objs-y) $(real-objs-m) $(lib-y)
 targets += $(extra-y) $(MAKECMDGOALS) $(always)

2.4.3

Set HAVE_STACK_VALIDATION to enable stack metadata validation for x86_64.

---
 arch/x86/Kconfig | 1 +
 1 file changed, 1 insertion(+)

index c46662f..adc5a6d 100644
@@ -155,6 +155,7 @@ config X86
 	select VIRT_TO_BUS
 	select X86_DEV_DMA_OPS			if X86_64
 	select X86_FEATURE_NAMES		if PROC_FS
+	select HAVE_STACK_VALIDATION		if X86_64
 
 config INSTRUCTION_DECODER
 	def_bool y

2.4.3

FYI, I got this build failure on allmodconfig-x86-64:

objtool.c:134:1: error: control reaches end of non-void function [-Werror=return-type]

that was with:

gcc version 4.8.3 20140911 (Red Hat 4.8.3-7) (GCC)

GCC 5.2.1 does not trigger this warning, which is I suspect why you have not seen this in your own testing.

I applied the fix below: all paths that generate a nonzero error do an explicit exit(), so return 0 is fine here.

Thanks,

Ingo

=====================>

 tools/objtool/objtool.c | 2 ++
 1 file changed, 2 insertions(+)

index 4e53d272c0c3..46c326db4f46 100644
@@ -131,4 +131,6 @@ int main(int argc, const char **argv)
 		cmd_usage();
 
 	handle_internal_command(argc, argv);
+
+	return 0;
 }

Another thing I've noticed are _thousands_ of these warnings:

objtool: kernel/sched/core.o: preempt_schedule_irq()+0x20: function has unreachable instruction
objtool: kernel/sched/core.o: preempt_schedule_irq()+0x27: function has unreachable instruction
objtool: kernel/sched/core.o: preempt_schedule_irq()+0x2c: function has unreachable instruction
objtool: kernel/sched/core.o: preempt_schedule_irq()+0x33: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_put_page_vector()+0x171: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_put_page_vector()+0x178: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_put_page_vector()+0x17d: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_put_page_vector()+0x184: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_get_direct_page_vector()+0xe2: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_get_direct_page_vector()+0xe9: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_get_direct_page_vector()+0xee: function has unreachable instruction
objtool: net/ceph/pagevec.o: ceph_get_direct_page_vector()+0xf5: function has unreachable instruction
objtool: net/ceph/pagevec.o: zero_user_segment()+0x120: function has unreachable instruction
objtool: net/ceph/pagevec.o: zero_user_segment()+0x127: function has unreachable instruction
objtool: net/ceph/pagevec.o: zero_user_segment()+0x12c: function has unreachable instruction
objtool: net/ceph/pagevec.o: zero_user_segment()+0x133: function has unreachable instruction

that's on an x86-64 allyesconfig kernel, with objtool merged to tip:master, using GCC 4.9.2:

gcc version 4.9.2 20150212 (Red Hat 4.9.2-6) (GCC)

Also, please prefix such warnings with the standard compiler prefix, something like this:

	kernel/sched/core.c: warning: objtool: preempt_schedule_irq()+0x20: function has unreachable instruction

so that scripts/tools monitoring new build warnings can pick them up automatically?

Thanks,

Ingo

Those are caused by CONFIG_KASAN, CONFIG_UBSAN, and CONFIG_GCOV_KERNEL, which can all add unreachable instructions. Technically, an unreachable instruction isn't really a problem, but objtool warns about it because it often means there's something going on in the control flow which it doesn't understand.

I guess we could make CONFIG_STACK_VALIDATION conflict with those options, but I think that would disable it on allyesconfig.

I'll see if I can make objtool smarter so that it detects these special cases of unreachable instructions and ignores them.

Yeah, good idea.

--
Josh