[PATCH v6 2/4] x86/stackvalidate: Compile-time stack validation

[Josh Poimboeuf]

This adds a CONFIG_STACK_VALIDATION option which enables a host tool
named stackvalidate which runs at compile time.  It analyzes every .o
file and ensures the validity of its stack metadata.  It enforces a set
of rules on asm code and C inline assembly code so that stack traces can
be reliable.

Currently it checks frame pointer usage.  I plan to add DWARF CFI
validation as well.

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 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 external jump tables.

To achieve the validation, stackvalidate 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 stackvalidate finds a return instruction
   outside of a function, it flags an error since that usually indicates
   callable code which should be annotated accordingly.

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.

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/ENDFRAME macros.

4. A callable function may not jump to a symbol in another file.  Such
   cross-file jumps can't be validated because stackvalidate only
   analyzes a single .o file at a time.

5. A callable function may not jump to a dynamically determined address.
   Such jumps can't be validated since the jump destination is unknown
   at compile time.

6. A callable function may not execute a context switching instruction.
   The only code which needs to do context switches is kernel entry
   code, which shouldn't be annotated to be in callable functions
   anyway.

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.

Currently with my Fedora config it's reporting over 1400 warnings, but
most of them are duplicates.  The warnings affect 37 .c files and 18 .S
files.  The C file warnings are generally due to inline assembly, which
doesn't seem to play nice with frame pointers.

As a first step, CONFIG_STACK_VALIDATION is disabled by default, and all
reported non-compliances result in warnings.  Once we get them all
cleaned up, we can change the default to CONFIG_STACK_VALIDATION=y and
change the warnings to errors to keep the stack metadata clean.

On my Lenovo T430s 4-core laptop, building the kernel with it enabled
adds about 3.6 seconds (14.4 seconds of total CPU).  It hasn't been
optimized for performance yet, so there are probably some opportunities
for better build performance.

Signed-off-by: Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
---
 Documentation/stack-validation.txt    | 189 ++++++++
 MAINTAINERS                           |   8 +
 arch/Kconfig                          |   6 +
 arch/x86/Kconfig                      |   1 +
 arch/x86/Makefile                     |   6 +-
 lib/Kconfig.debug                     |  11 +
 scripts/Makefile                      |   1 +
 scripts/Makefile.build                |  34 +-
 scripts/stackvalidate/Makefile        |  24 +
 scripts/stackvalidate/arch-x86.c      | 147 ++++++
 scripts/stackvalidate/arch.h          |  44 ++
 scripts/stackvalidate/elf.c           | 421 +++++++++++++++++
 scripts/stackvalidate/elf.h           |  85 ++++
 scripts/stackvalidate/list.h          | 217 +++++++++
 scripts/stackvalidate/special.c       | 176 +++++++
 scripts/stackvalidate/special.h       |  40 ++
 scripts/stackvalidate/stackvalidate.c | 858 ++++++++++++++++++++++++++++++++++
 17 files changed, 2263 insertions(+), 5 deletions(-)
 create mode 100644 Documentation/stack-validation.txt
 create mode 100644 scripts/stackvalidate/Makefile
 create mode 100644 scripts/stackvalidate/arch-x86.c
 create mode 100644 scripts/stackvalidate/arch.h
 create mode 100644 scripts/stackvalidate/elf.c
 create mode 100644 scripts/stackvalidate/elf.h
 create mode 100644 scripts/stackvalidate/list.h
 create mode 100644 scripts/stackvalidate/special.c
 create mode 100644 scripts/stackvalidate/special.h
 create mode 100644 scripts/stackvalidate/stackvalidate.c

diff --git a/Documentation/stack-validation.txt b/Documentation/stack-validation.txt
new file mode 100644
index 0000000..4b66336
--- /dev/null
+++ b/Documentation/stack-validation.txt
@@ -0,0 +1,189 @@
+Compile-time stack validation
+=============================
+
+
+Overview
+--------
+
+The CONFIG_STACK_VALIDATION option enables a host tool named
+stackvalidate which runs at compile time.  It analyzes every .o file and
+ensures the validity of its stack metadata.  It enforces a set of rules
+on asm code and C inline assembly code so that stack traces can be
+reliable.
+
+Currently it only checks frame pointer usage, but there are plans to add
+DWARF CFI validation as well.
+
+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 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 external jump tables.
+
+
+Rules
+-----
+
+To achieve the validation, stackvalidate 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 stackvalidate finds a return instruction
+   outside of a function, it flags an error since that usually indicates
+   callable code which should be annotated accordingly.
+
+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.
+
+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/ENDFRAME macros.
+
+4. A callable function may not jump to a symbol in another file.  Such
+   cross-file jumps can't be validated because stackvalidate only
+   analyzes a single .o file at a time.
+
+5. A callable function may not jump to a dynamically determined address.
+   Such jumps can't be validated since the jump destination is unknown
+   at compile time.
+
+6. A callable function may not execute a context switching instruction.
+   The only code which needs to do context switches is kernel entry
+   code, which shouldn't be annotated to be in callable functions
+   anyway.
+
+
+Errors in .S files
+------------------
+
+If you're getting an error in a compiled .S file which you don't
+understand, first make sure that the affected code follows the above
+rules.
+
+Here are some examples of common problems and suggestions for how to fix
+them.
+
+
+1. stackvalidate: asm_file.o: func()+0x128: call without frame pointer save/setup
+
+   The func() function made a function call without first saving and/or
+   updating the frame pointer.
+
+   If func() is indeed a callable function, add proper frame pointer
+   logic using the FP_SAVE and FP_RESTORE macros.  Otherwise, remove its
+   ELF function annotation by changing ENDPROC to END.
+
+
+2. stackvalidate: asm_file.o: .text+0x53: return instruction outside of a callable function
+
+   A return instruction was detected, but stackvalidate couldn't find a
+   way for a callable function to reach the instruction.
+
+   If the return instruction is inside (or reachable from) a callable
+   function, the function needs to be annotated with the PROC/ENDPROC
+   macros.
+
+   If you _really_ need a return instruction outside of a function, and
+   are 100% sure that it won't affect stack traces, you can tell
+   stackvalidate to ignore it.  See the "Adding exceptions" section
+   below.
+
+
+3. stackvalidate: asm_file.o: func()+0x9: function has unreachable instruction
+
+   The instruction lives inside of a callable function, but there's no
+   possible control flow path from the beginning of the function to the
+   instruction.
+
+   If the instruction is actually needed, and it's actually in a
+   callable function, ensure that its function is properly annotated
+   with PROC/ENDPROC.
+
+   If it's not actually in a callable function (e.g. kernel entry code),
+   change ENDPROC to END.
+
+
+4. stackvalidate: asm_file.o: func(): can't find starting instruction
+   or
+   stackvalidate: asm_file.o: func()+0x11dd: can't decode instruction
+
+   Did you put data in a text section?  If so, that can confuse
+   stackvalidate's instruction decoder.  Move the data to a more
+   appropriate section like .data or .rodata.
+
+
+5. stackvalidate: asm_file.o: func()+0x6: context switch from callable function
+
+   This is a context switch instruction like sysenter or sysret.  Such
+   instructions aren't allowed in a callable function, and are most
+   likely part of kernel entry code.
+
+   If the instruction isn't actually in a callable function, change
+   ENDPROC to END.
+
+
+6. stackvalidate: asm_file.o: func()+0x26: jump to outside file from callable function
+   or
+   stackvalidate: asm_file.o: func()+0xd9: jump to dynamic address from callable function
+
+   These are constraints imposed by stackvalidate so that it can
+   properly analyze all jump targets.  Dynamic jump targets and jumps to
+   code in other object files aren't allowed.
+
+   If the instruction is not actually in a callable function (e.g.
+   kernel entry code), change ENDPROC to END.
+
+   Otherwise you may need to move the destination code to the local
+   file.
+
+
+7. stackvalidate: asm_file: func()+0x5c: frame pointer state mismatch
+
+   The instruction's frame pointer state is inconsistent, depending on
+   which execution path was taken to reach the instruction.
+
+   Make sure the function pushes and sets up the frame pointer (for
+   x86_64, this means rbp) at the beginning of the function and pops it
+   at the end of the function.  Also make sure that no other code in the
+   function touches the frame pointer.
+
+
+Errors in .c files
+------------------
+
+If you're getting a stackvalidate error in a compiled .c file, chances
+are the file uses inline assembly (or uses a macro or an inline function
+which uses inline assembly).  See the above section for .S file errors
+for an understanding what the individual error messages mean.
+
+Many of these errors seem to be caused by the fact that gcc doesn't seem
+to provide a way to deal properly with frame pointers when using inline
+assembly.  This needs more investigation and discussion...
+
+Another possible cause for errors in C code is if the Makefile removes
+-fno-omit-frame-pointer or adds -fomit-frame-pointer to the gcc options.
+
+
+Adding exceptions
+-----------------
+
+If you _really_ need stackvalidate to ignore something, and are 100%
+sure that it won't affect kernel stack traces, you can tell
+stackvalidate to ignore it:
+
+- To skip validation of an instruction, use the
+  STACKVALIDATE_IGNORE_INSN macro immediately before the instruction.
+
+- To skip validation of a function, use the STACKVALIDATE_IGNORE_FUNC
+  macro.
+
+- To skip validation of a file, add "STACKVALIDATE_filename.o := n" to
+  the Makefile.
+
+- To skip validation of a directory, add "STACKVALIDATE := n" to the
+  Makefile.
diff --git a/MAINTAINERS b/MAINTAINERS
index e63e337..ded7729 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -9652,6 +9652,14 @@ L:	stable@xxxxxxxxxxxxxxx
 S:	Supported
 F:	Documentation/stable_kernel_rules.txt
 
+STACK VALIDATION
+M:	Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+S:	Supported
+F:	scripts/stackvalidate/
+F:	arch/x86/include/asm/frame.h
+F:	include/linux/stackvalidate.h
+F:	Documentation/stack-validation.txt
+
 STAGING SUBSYSTEM
 M:	Greg Kroah-Hartman <gregkh@xxxxxxxxxxxxxxxxxxx>
 T:	git git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging.git
diff --git a/arch/Kconfig b/arch/Kconfig
index 150a01b..8a921d5 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -515,6 +515,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 stackvalidate host tool, which adds
+	  compile-time stack metadata validation.
+
 #
 # ABI hall of shame
 #
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 31fc0cd..e7370d1 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -150,6 +150,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
diff --git a/arch/x86/Makefile b/arch/x86/Makefile
index 118e6de..438c153 100644
--- a/arch/x86/Makefile
+++ b/arch/x86/Makefile
@@ -174,9 +174,13 @@ KBUILD_CFLAGS += $(call cc-option,-mno-avx,)
 KBUILD_CFLAGS += $(mflags-y)
 KBUILD_AFLAGS += $(mflags-y)
 
-archscripts: scripts_basic
+archscripts: scripts_basic $(objtree)/arch/x86/lib/inat-tables.c
 	$(Q)$(MAKE) $(build)=arch/x86/tools relocs
 
+# this file is needed early by scripts/stackvalidate
+$(objtree)/arch/x86/lib/inat-tables.c:
+	$(Q)$(MAKE) $(build)=arch/x86/lib $@
+
 ###
 # Syscall table generation
 
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e2894b2..6c96f36 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -332,6 +332,17 @@ 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 "Enable compile-time stack metadata validation"
+	depends on HAVE_STACK_VALIDATION
+	default n
+	help
+	  Add compile-time checks to validate stack metadata, including frame
+	  pointers and back chain pointers.  This helps ensure that runtime
+	  stack traces are more reliable.
+
+	  For more information, see Documentation/stack-validation.txt.
+
 config DEBUG_FORCE_WEAK_PER_CPU
 	bool "Force weak per-cpu definitions"
 	depends on DEBUG_KERNEL
diff --git a/scripts/Makefile b/scripts/Makefile
index 2016a64..c882a91 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -37,6 +37,7 @@ subdir-y                     += mod
 subdir-$(CONFIG_SECURITY_SELINUX) += selinux
 subdir-$(CONFIG_DTC)         += dtc
 subdir-$(CONFIG_GDB_SCRIPTS) += gdb
+subdir-$(CONFIG_STACK_VALIDATION) += stackvalidate
 
 # Let clean descend into subdirs
 subdir-	+= basic kconfig package
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index 01df30a..a1270d3 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -241,9 +241,26 @@ cmd_record_mcount =						\
 	fi;
 endif
 
+ifdef CONFIG_STACK_VALIDATION
+
+stackvalidate = $(objtree)/scripts/stackvalidate/stackvalidate
+
+ifndef CONFIG_FRAME_POINTER
+nofp = --no-frame-pointer
+endif
+
+# Set STACKVALIDATE_foo.o=n to skip stack validation for a file.
+# Set STACKVALIDATE=n to skip stack validation for a directory.
+cmd_stackvalidate = $(if $(patsubst n%,, \
+	$(STACKVALIDATE_$(basetarget).o)$(STACKVALIDATE)y), \
+	$(stackvalidate) $(nofp) "$(@)";)
+
+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_stackvalidate)						  \
 	$(cmd_modversions)						  \
 	$(call echo-cmd,record_mcount)					  \
 	$(cmd_record_mcount)						  \
@@ -253,14 +270,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_stackvalidate)						  \
+	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) $(stackvalidate) 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) $(stackvalidate) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 	@{ echo $(@:.o=.ko); echo $@; } > $(MODVERDIR)/$(@F:.o=.mod)
@@ -290,8 +316,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 $(stackvalidate) FORCE
+	$(call if_changed_rule,as_o_S)
 
 targets += $(real-objs-y) $(real-objs-m) $(lib-y)
 targets += $(extra-y) $(MAKECMDGOALS) $(always)
diff --git a/scripts/stackvalidate/Makefile b/scripts/stackvalidate/Makefile
new file mode 100644
index 0000000..468c075
--- /dev/null
+++ b/scripts/stackvalidate/Makefile
@@ -0,0 +1,24 @@
+hostprogs-y := stackvalidate
+always := $(hostprogs-y)
+
+stackvalidate-objs := stackvalidate.o elf.o special.o
+
+HOSTCFLAGS += -Werror
+HOSTLOADLIBES_stackvalidate := -lelf
+
+ifdef CONFIG_X86
+
+stackvalidate-objs += arch-x86.o
+
+HOSTCFLAGS_arch-x86.o := -I$(objtree)/arch/x86/lib/ \
+			 -I$(srctree)/arch/x86/include/ \
+			 -I$(srctree)/arch/x86/lib/
+
+$(obj)/arch-x86.o: $(srctree)/arch/x86/lib/insn.c \
+		   $(srctree)/arch/x86/lib/inat.c \
+		   $(srctree)/arch/x86/include/asm/inat_types.h \
+		   $(srctree)/arch/x86/include/asm/inat.h \
+		   $(srctree)/arch/x86/include/asm/insn.h \
+		   $(objtree)/arch/x86/lib/inat-tables.c
+
+endif
diff --git a/scripts/stackvalidate/arch-x86.c b/scripts/stackvalidate/arch-x86.c
new file mode 100644
index 0000000..4e31e04
--- /dev/null
+++ b/scripts/stackvalidate/arch-x86.c
@@ -0,0 +1,147 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdio.h>
+
+#define unlikely(cond) (cond)
+#include <asm/insn.h>
+#include <inat.c>
+#include <insn.c>
+#include <stdlib.h>
+
+#include "elf.h"
+#include "arch.h"
+
+static int is_x86_64(struct elf *elf)
+{
+	switch (elf->ehdr.e_machine) {
+	case EM_X86_64:
+		return 1;
+	case EM_386:
+		return 0;
+	default:
+		WARN("unexpected ELF machine type %d", elf->ehdr.e_machine);
+		return -1;
+	}
+}
+
+int arch_decode_instruction(struct elf *elf, struct section *sec,
+			    unsigned long offset, unsigned int maxlen,
+			    unsigned int *len, unsigned char *type,
+			    unsigned long *immediate)
+{
+	struct insn insn;
+	int x86_64;
+	unsigned char op1, op2, ext;
+
+	x86_64 = is_x86_64(elf);
+	if (x86_64 == -1)
+		return -1;
+
+	insn_init(&insn, (void *)(sec->data + offset), maxlen, x86_64);
+	insn_get_length(&insn);
+	insn_get_opcode(&insn);
+	insn_get_modrm(&insn);
+	insn_get_immediate(&insn);
+
+	if (!insn.opcode.got || !insn.modrm.got || !insn.immediate.got) {
+		WARN("%s: can't decode instruction",
+		     offstr(sec, offset));
+		return -1;
+	}
+
+	*len = insn.length;
+	*type = INSN_OTHER;
+
+	if (insn.vex_prefix.nbytes)
+		return 0;
+
+	op1 = insn.opcode.bytes[0];
+	op2 = insn.opcode.bytes[1];
+
+	switch (op1) {
+	case 0x55:
+		if (!insn.rex_prefix.nbytes)
+			/* push rbp */
+			*type = INSN_FP_SAVE;
+		break;
+	case 0x5d:
+		if (!insn.rex_prefix.nbytes)
+			/* pop rbp */
+			*type = INSN_FP_RESTORE;
+		break;
+	case 0x70 ... 0x7f:
+		*type = INSN_JUMP_CONDITIONAL;
+		break;
+	case 0x89:
+		if (insn.rex_prefix.nbytes == 1 && insn.rex_prefix.bytes[0] == 0x48 &&
+		    insn.modrm.nbytes && insn.modrm.bytes[0] == 0xe5)
+			/* mov rsp, rbp */
+			*type = INSN_FP_SETUP;
+		break;
+	case 0x90:
+		*type = INSN_NOP;
+	case 0x0f:
+		if (op2 >= 0x80 && op2 <= 0x8f)
+			*type = INSN_JUMP_CONDITIONAL;
+		else if (op2 == 0x05 || op2 == 0x07 || op2 == 0x34 ||
+			 op2 == 0x35)
+			/* sysenter, sysret */
+			*type = INSN_CONTEXT_SWITCH;
+		else if (op2 == 0x0b || op2 == 0xb9)
+			/* ud2 */
+			*type = INSN_BUG;
+		else if (op2 == 0x0d || op2 == 0x1f)
+			/* nopl/nopw */
+			*type = INSN_NOP;
+		break;
+	case 0xc9: /* leave */
+		*type = INSN_FP_RESTORE;
+		break;
+	case 0xe3: /* jecxz/jrcxz */
+		*type = INSN_JUMP_CONDITIONAL;
+		break;
+	case 0xe9:
+	case 0xeb:
+		*type = INSN_JUMP_UNCONDITIONAL;
+		break;
+
+	case 0xc2:
+	case 0xc3:
+		*type = INSN_RETURN;
+		break;
+	case 0xc5: /* iret */
+	case 0xca: /* retf */
+	case 0xcb: /* retf */
+		*type = INSN_CONTEXT_SWITCH;
+		break;
+	case 0xe8:
+		*type = INSN_CALL;
+		break;
+	case 0xff:
+		ext = X86_MODRM_REG(insn.modrm.bytes[0]);
+		if (ext == 2 || ext == 3)
+			*type = INSN_CALL_DYNAMIC;
+		else if (ext == 4 || ext == 5)
+			*type = INSN_JUMP_DYNAMIC;
+		break;
+	}
+
+	*immediate = insn.immediate.nbytes ? insn.immediate.value : 0;
+
+	return 0;
+}
diff --git a/scripts/stackvalidate/arch.h b/scripts/stackvalidate/arch.h
new file mode 100644
index 0000000..f7350fc
--- /dev/null
+++ b/scripts/stackvalidate/arch.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _ARCH_H
+#define _ARCH_H
+
+#include <stdbool.h>
+#include "elf.h"
+
+#define INSN_FP_SAVE		1
+#define INSN_FP_SETUP		2
+#define INSN_FP_RESTORE		3
+#define INSN_JUMP_CONDITIONAL	4
+#define INSN_JUMP_UNCONDITIONAL	5
+#define INSN_JUMP_DYNAMIC	6
+#define INSN_CALL		7
+#define INSN_CALL_DYNAMIC	8
+#define INSN_RETURN		9
+#define INSN_CONTEXT_SWITCH	10
+#define INSN_BUG		11
+#define INSN_NOP		12
+#define INSN_OTHER		13
+#define INSN_LAST		INSN_OTHER
+
+int arch_decode_instruction(struct elf *elf, struct section *sec,
+			    unsigned long offset, unsigned int maxlen,
+			    unsigned int *len, unsigned char *type,
+			    unsigned long *displacement);
+
+#endif /* _ARCH_H */
diff --git a/scripts/stackvalidate/elf.c b/scripts/stackvalidate/elf.c
new file mode 100644
index 0000000..c38bdb1
--- /dev/null
+++ b/scripts/stackvalidate/elf.c
@@ -0,0 +1,421 @@
+/*
+ * elf.c - ELF access library
+ *
+ * Adapted from kpatch (https://github.com/dynup/kpatch):
+ * Copyright (C) 2013-2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ * Copyright (C) 2014 Seth Jennings <sjenning@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "elf.h"
+
+char *offstr(struct section *sec, unsigned long offset)
+{
+	struct symbol *func;
+	char *name, *str;
+	unsigned long name_off;
+
+	func = find_containing_func(sec, offset);
+	if (func) {
+		name = func->name;
+		name_off = offset - func->offset;
+	} else {
+		name = sec->name;
+		name_off = offset;
+	}
+
+	str = malloc(strlen(name) + 20);
+
+	if (func)
+		sprintf(str, "%s()+0x%lx", name, name_off);
+	else
+		sprintf(str, "%s+0x%lx", name, name_off);
+
+	return str;
+}
+
+struct section *find_section_by_name(struct elf *elf, const char *name)
+{
+	struct section *sec;
+
+	list_for_each_entry(sec, &elf->sections, list)
+		if (!strcmp(sec->name, name))
+			return sec;
+
+	return NULL;
+}
+
+static struct section *find_section_by_index(struct elf *elf,
+					     unsigned int index)
+{
+	struct section *sec;
+
+	list_for_each_entry(sec, &elf->sections, list)
+		if (sec->index == index)
+			return sec;
+
+	return NULL;
+}
+
+static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int index)
+{
+	struct section *sec;
+	struct symbol *sym;
+
+	list_for_each_entry(sec, &elf->sections, list)
+		list_for_each_entry(sym, &sec->symbols, list)
+			if (sym->index == index)
+				return sym;
+
+	return NULL;
+}
+
+struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
+{
+	struct symbol *sym;
+
+	list_for_each_entry(sym, &sec->symbols, list)
+		if (sym->type != STT_SECTION &&
+		    sym->offset == offset)
+			return sym;
+
+	return NULL;
+}
+
+struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
+				     unsigned int len)
+{
+	struct rela *rela;
+
+	if (!sec->rela)
+		return NULL;
+
+	list_for_each_entry(rela, &sec->rela->relas, list)
+		if (rela->offset >= offset && rela->offset < offset + len)
+			return rela;
+
+	return NULL;
+}
+
+struct rela *find_rela_by_dest(struct section *sec, unsigned long offset)
+{
+	return find_rela_by_dest_range(sec, offset, 1);
+}
+
+struct symbol *find_containing_func(struct section *sec, unsigned long offset)
+{
+	struct symbol *func;
+
+	list_for_each_entry(func, &sec->symbols, list)
+		if (func->type == STT_FUNC && offset >= func->offset &&
+		    offset < func->offset + func->len)
+			return func;
+
+	return NULL;
+}
+
+static int read_sections(struct elf *elf)
+{
+	Elf_Scn *s = NULL;
+	struct section *sec;
+	size_t shstrndx, sections_nr;
+	int i;
+
+	if (elf_getshdrnum(elf->elf, &sections_nr)) {
+		perror("elf_getshdrnum");
+		return -1;
+	}
+
+	if (elf_getshdrstrndx(elf->elf, &shstrndx)) {
+		perror("elf_getshdrstrndx");
+		return -1;
+	}
+
+	for (i = 0; i < sections_nr; i++) {
+		sec = malloc(sizeof(*sec));
+		if (!sec) {
+			perror("malloc");
+			return -1;
+		}
+		memset(sec, 0, sizeof(*sec));
+
+		INIT_LIST_HEAD(&sec->symbols);
+		INIT_LIST_HEAD(&sec->relas);
+
+		list_add_tail(&sec->list, &elf->sections);
+
+		s = elf_getscn(elf->elf, i);
+		if (!s) {
+			perror("elf_getscn");
+			return -1;
+		}
+
+		sec->index = elf_ndxscn(s);
+
+		if (!gelf_getshdr(s, &sec->sh)) {
+			perror("gelf_getshdr");
+			return -1;
+		}
+
+		sec->name = elf_strptr(elf->elf, shstrndx, sec->sh.sh_name);
+		if (!sec->name) {
+			perror("elf_strptr");
+			return -1;
+		}
+
+		sec->elf_data = elf_getdata(s, NULL);
+		if (!sec->elf_data) {
+			perror("elf_getdata");
+			return -1;
+		}
+
+		if (sec->elf_data->d_off != 0 ||
+		    sec->elf_data->d_size != sec->sh.sh_size) {
+			WARN("unexpected data attributes for %s", sec->name);
+			return -1;
+		}
+
+		sec->data = (unsigned long)sec->elf_data->d_buf;
+		sec->len = sec->elf_data->d_size;
+	}
+
+	/* sanity check, one more call to elf_nextscn() should return NULL */
+	if (elf_nextscn(elf->elf, s)) {
+		WARN("section entry mismatch");
+		return -1;
+	}
+
+	return 0;
+}
+
+static int read_symbols(struct elf *elf)
+{
+	struct section *symtab;
+	struct symbol *sym;
+	struct list_head *entry, *tmp;
+	int symbols_nr, i;
+
+	symtab = find_section_by_name(elf, ".symtab");
+	if (!symtab) {
+		WARN("missing symbol table");
+		return -1;
+	}
+
+	symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
+
+	for (i = 0; i < symbols_nr; i++) {
+		sym = malloc(sizeof(*sym));
+		if (!sym) {
+			perror("malloc");
+			return -1;
+		}
+		memset(sym, 0, sizeof(*sym));
+
+		sym->index = i;
+
+		if (!gelf_getsym(symtab->elf_data, i, &sym->sym)) {
+			perror("gelf_getsym");
+			goto err;
+		}
+
+		sym->name = elf_strptr(elf->elf, symtab->sh.sh_link,
+				       sym->sym.st_name);
+		if (!sym->name) {
+			perror("elf_strptr");
+			goto err;
+		}
+
+		sym->type = GELF_ST_TYPE(sym->sym.st_info);
+		sym->bind = GELF_ST_BIND(sym->sym.st_info);
+
+		if (sym->sym.st_shndx > SHN_UNDEF &&
+		    sym->sym.st_shndx < SHN_LORESERVE) {
+			sym->sec = find_section_by_index(elf, sym->sym.st_shndx);
+			if (!sym->sec) {
+				WARN("couldn't find section for symbol %s",
+				     sym->name);
+				goto err;
+			}
+			if (sym->type == STT_SECTION) {
+				sym->name = sym->sec->name;
+				sym->sec->sym = sym;
+			}
+		} else
+			sym->sec = find_section_by_index(elf, 0);
+
+		sym->offset = sym->sym.st_value;
+		sym->len = sym->sym.st_size;
+
+		/* sorted insert into a per-section list */
+		entry = &sym->sec->symbols;
+		list_for_each_prev(tmp, &sym->sec->symbols) {
+			struct symbol *s;
+
+			s = list_entry(tmp, struct symbol, list);
+
+			if (sym->offset > s->offset) {
+				entry = tmp;
+				break;
+			}
+
+			if (sym->offset == s->offset && sym->len >= s->len) {
+				entry = tmp;
+				break;
+			}
+		}
+		list_add(&sym->list, entry);
+	}
+
+	return 0;
+
+err:
+	free(sym);
+	return -1;
+}
+
+static int read_relas(struct elf *elf)
+{
+	struct section *sec;
+	struct rela *rela;
+	int i;
+	unsigned int symndx;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		if (sec->sh.sh_type != SHT_RELA)
+			continue;
+
+		sec->base = find_section_by_name(elf, sec->name + 5);
+		if (!sec->base) {
+			WARN("can't find base section for rela section %s",
+			     sec->name);
+			return -1;
+		}
+
+		sec->base->rela = sec;
+
+		for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
+			rela = malloc(sizeof(*rela));
+			if (!rela) {
+				perror("malloc");
+				return -1;
+			}
+			memset(rela, 0, sizeof(*rela));
+
+			list_add_tail(&rela->list, &sec->relas);
+
+			if (!gelf_getrela(sec->elf_data, i, &rela->rela)) {
+				perror("gelf_getrela");
+				return -1;
+			}
+
+			rela->type = GELF_R_TYPE(rela->rela.r_info);
+			rela->addend = rela->rela.r_addend;
+			rela->offset = rela->rela.r_offset;
+			symndx = GELF_R_SYM(rela->rela.r_info);
+			rela->sym = find_symbol_by_index(elf, symndx);
+			if (!rela->sym) {
+				WARN("can't find rela entry symbol %d for %s",
+				     symndx, sec->name);
+				return -1;
+			}
+		}
+	}
+
+	return 0;
+}
+
+struct elf *elf_open(const char *name)
+{
+	struct elf *elf;
+
+	elf_version(EV_CURRENT);
+
+	elf = malloc(sizeof(*elf));
+	if (!elf) {
+		perror("malloc");
+		return NULL;
+	}
+	memset(elf, 0, sizeof(*elf));
+
+	INIT_LIST_HEAD(&elf->sections);
+
+	elf->name = strdup(name);
+	if (!elf->name) {
+		perror("strdup");
+		goto err;
+	}
+
+	elf->fd = open(name, O_RDONLY);
+	if (elf->fd == -1) {
+		perror("open");
+		goto err;
+	}
+
+	elf->elf = elf_begin(elf->fd, ELF_C_READ_MMAP, NULL);
+	if (!elf->elf) {
+		perror("elf_begin");
+		goto err;
+	}
+
+	if (!gelf_getehdr(elf->elf, &elf->ehdr)) {
+		perror("gelf_getehdr");
+		goto err;
+	}
+
+	if (read_sections(elf))
+		goto err;
+
+	if (read_symbols(elf))
+		goto err;
+
+	if (read_relas(elf))
+		goto err;
+
+	return elf;
+
+err:
+	elf_close(elf);
+	return NULL;
+}
+
+void elf_close(struct elf *elf)
+{
+	struct section *sec, *tmpsec;
+	struct symbol *sym, *tmpsym;
+
+	list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
+		list_for_each_entry_safe(sym, tmpsym, &sec->symbols, list) {
+			list_del(&sym->list);
+			free(sym);
+		}
+		list_del(&sec->list);
+		free(sec);
+	}
+	if (elf->name)
+		free(elf->name);
+	if (elf->fd > 0)
+		close(elf->fd);
+	if (elf->elf)
+		elf_end(elf->elf);
+	free(elf);
+}
diff --git a/scripts/stackvalidate/elf.h b/scripts/stackvalidate/elf.h
new file mode 100644
index 0000000..65a27cb
--- /dev/null
+++ b/scripts/stackvalidate/elf.h
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _STACKVALIDATE_ELF_H
+#define _STACKVALIDATE_ELF_H
+
+#include <stdio.h>
+#include <gelf.h>
+#include "list.h"
+
+#define WARN(format, ...) \
+	fprintf(stderr, \
+		"stackvalidate: %s: " format "\n", \
+		elf->name, ##__VA_ARGS__)
+
+struct section {
+	struct list_head list;
+	GElf_Shdr sh;
+	struct list_head symbols;
+	struct list_head relas;
+	struct section *base, *rela;
+	struct symbol *sym;
+	Elf_Data *elf_data;
+	char *name;
+	int index;
+	unsigned long data;
+	unsigned int len;
+};
+
+struct symbol {
+	struct list_head list;
+	GElf_Sym sym;
+	struct section *sec;
+	char *name;
+	int index;
+	unsigned char bind, type;
+	unsigned long offset;
+	unsigned int len;
+};
+
+struct rela {
+	struct list_head list;
+	GElf_Rela rela;
+	struct symbol *sym;
+	unsigned int type;
+	int offset;
+	int addend;
+};
+
+struct elf {
+	Elf *elf;
+	GElf_Ehdr ehdr;
+	int fd;
+	char *name;
+	struct list_head sections;
+};
+
+
+struct elf *elf_open(const char *name);
+struct section *find_section_by_name(struct elf *elf, const char *name);
+struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset);
+struct rela *find_rela_by_dest(struct section *sec, unsigned long offset);
+struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
+				     unsigned int len);
+struct symbol *find_containing_func(struct section *sec, unsigned long offset);
+char *offstr(struct section *sec, unsigned long offset);
+void elf_close(struct elf *elf);
+
+
+
+#endif /* _STACKVALIDATE_ELF_H */
diff --git a/scripts/stackvalidate/list.h b/scripts/stackvalidate/list.h
new file mode 100644
index 0000000..25716b5
--- /dev/null
+++ b/scripts/stackvalidate/list.h
@@ -0,0 +1,217 @@
+#ifndef _LIST_H
+#define _LIST_H
+
+#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+
+#define container_of(ptr, type, member) ({ \
+	const typeof(((type *)0)->member) *__mptr = (ptr); \
+	(type *)((char *)__mptr - offsetof(type, member)); })
+
+#define LIST_POISON1 ((void *) 0x00100100)
+#define LIST_POISON2 ((void *) 0x00200200)
+
+struct list_head {
+	struct list_head *next, *prev;
+};
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define LIST_HEAD(name) \
+	struct list_head name = LIST_HEAD_INIT(name)
+
+static inline void INIT_LIST_HEAD(struct list_head *list)
+{
+	list->next = list;
+	list->prev = list;
+}
+
+static inline void __list_add(struct list_head *new,
+			      struct list_head *prev,
+			      struct list_head *next)
+{
+	next->prev = new;
+	new->next = next;
+	new->prev = prev;
+	prev->next = new;
+}
+
+static inline void list_add(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head, head->next);
+}
+
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head->prev, head);
+}
+
+static inline void __list_del(struct list_head *prev, struct list_head *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+static inline void __list_del_entry(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+}
+
+static inline void list_del(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+	entry->next = LIST_POISON1;
+	entry->prev = LIST_POISON2;
+}
+
+static inline void list_replace(struct list_head *old,
+				struct list_head *new)
+{
+	new->next = old->next;
+	new->next->prev = new;
+	new->prev = old->prev;
+	new->prev->next = new;
+}
+
+static inline void list_replace_init(struct list_head *old,
+					struct list_head *new)
+{
+	list_replace(old, new);
+	INIT_LIST_HEAD(old);
+}
+
+static inline void list_del_init(struct list_head *entry)
+{
+	__list_del_entry(entry);
+	INIT_LIST_HEAD(entry);
+}
+
+static inline void list_move(struct list_head *list, struct list_head *head)
+{
+	__list_del_entry(list);
+	list_add(list, head);
+}
+
+static inline void list_move_tail(struct list_head *list,
+				  struct list_head *head)
+{
+	__list_del_entry(list);
+	list_add_tail(list, head);
+}
+
+static inline int list_is_last(const struct list_head *list,
+				const struct list_head *head)
+{
+	return list->next == head;
+}
+
+static inline int list_empty(const struct list_head *head)
+{
+	return head->next == head;
+}
+
+static inline int list_empty_careful(const struct list_head *head)
+{
+	struct list_head *next = head->next;
+
+	return (next == head) && (next == head->prev);
+}
+
+static inline void list_rotate_left(struct list_head *head)
+{
+	struct list_head *first;
+
+	if (!list_empty(head)) {
+		first = head->next;
+		list_move_tail(first, head);
+	}
+}
+
+static inline int list_is_singular(const struct list_head *head)
+{
+	return !list_empty(head) && (head->next == head->prev);
+}
+
+#define list_entry(ptr, type, member) \
+	container_of(ptr, type, member)
+
+#define list_first_entry(ptr, type, member) \
+	list_entry((ptr)->next, type, member)
+
+#define list_last_entry(ptr, type, member) \
+	list_entry((ptr)->prev, type, member)
+
+#define list_first_entry_or_null(ptr, type, member) \
+	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
+
+#define list_next_entry(pos, member) \
+	list_entry((pos)->member.next, typeof(*(pos)), member)
+
+#define list_prev_entry(pos, member) \
+	list_entry((pos)->member.prev, typeof(*(pos)), member)
+
+#define list_for_each(pos, head) \
+	for (pos = (head)->next; pos != (head); pos = pos->next)
+
+#define list_for_each_prev(pos, head) \
+	for (pos = (head)->prev; pos != (head); pos = pos->prev)
+
+#define list_for_each_safe(pos, n, head) \
+	for (pos = (head)->next, n = pos->next; pos != (head); \
+		pos = n, n = pos->next)
+
+#define list_for_each_prev_safe(pos, n, head) \
+	for (pos = (head)->prev, n = pos->prev; \
+	     pos != (head); \
+	     pos = n, n = pos->prev)
+
+#define list_for_each_entry(pos, head, member)				\
+	for (pos = list_first_entry(head, typeof(*pos), member);	\
+	     &pos->member != (head);					\
+	     pos = list_next_entry(pos, member))
+
+#define list_for_each_entry_reverse(pos, head, member)			\
+	for (pos = list_last_entry(head, typeof(*pos), member);		\
+	     &pos->member != (head);					\
+	     pos = list_prev_entry(pos, member))
+
+#define list_prepare_entry(pos, head, member) \
+	((pos) ? : list_entry(head, typeof(*pos), member))
+
+#define list_for_each_entry_continue(pos, head, member)			\
+	for (pos = list_next_entry(pos, member);			\
+	     &pos->member != (head);					\
+	     pos = list_next_entry(pos, member))
+
+#define list_for_each_entry_continue_reverse(pos, head, member)		\
+	for (pos = list_prev_entry(pos, member);			\
+	     &pos->member != (head);					\
+	     pos = list_prev_entry(pos, member))
+
+#define list_for_each_entry_from(pos, head, member)			\
+	for (; &pos->member != (head);					\
+	     pos = list_next_entry(pos, member))
+
+#define list_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = list_first_entry(head, typeof(*pos), member),	\
+		n = list_next_entry(pos, member);			\
+	     &pos->member != (head);					\
+	     pos = n, n = list_next_entry(n, member))
+
+#define list_for_each_entry_safe_continue(pos, n, head, member)		\
+	for (pos = list_next_entry(pos, member),			\
+		n = list_next_entry(pos, member);			\
+	     &pos->member != (head);					\
+	     pos = n, n = list_next_entry(n, member))
+
+#define list_for_each_entry_safe_from(pos, n, head, member)		\
+	for (n = list_next_entry(pos, member);				\
+	     &pos->member != (head);					\
+	     pos = n, n = list_next_entry(n, member))
+
+#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
+	for (pos = list_last_entry(head, typeof(*pos), member),		\
+		n = list_prev_entry(pos, member);			\
+	     &pos->member != (head);					\
+	     pos = n, n = list_prev_entry(n, member))
+
+#endif /* _LIST_H */
diff --git a/scripts/stackvalidate/special.c b/scripts/stackvalidate/special.c
new file mode 100644
index 0000000..e676520
--- /dev/null
+++ b/scripts/stackvalidate/special.c
@@ -0,0 +1,176 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * This file reads all the special sections which have alternate instructions
+ * which can be patched in or redirected to at runtime.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include "special.h"
+
+#define EX_ENTRY_SIZE		8
+#define EX_ORIG_OFFSET		0
+#define EX_NEW_OFFSET		4
+
+#define ALT_ENTRY_SIZE		13
+#define ALT_ORIG_OFFSET		0
+#define ALT_NEW_OFFSET		4
+#define ALT_ORIG_LEN_OFFSET	10
+#define ALT_NEW_LEN_OFFSET	11
+
+#define JUMP_ENTRY_SIZE		24
+#define JUMP_ORIG_OFFSET	0
+#define JUMP_NEW_OFFSET	8
+
+struct special_entry {
+	char *sec;
+	bool group;
+	unsigned char size, orig, new;
+	unsigned char orig_len, new_len; /* group only */
+};
+
+struct special_entry entries[] = {
+	{
+		.sec = ".altinstructions",
+		.group = true,
+		.size = ALT_ENTRY_SIZE,
+		.orig = ALT_ORIG_OFFSET,
+		.orig_len = ALT_ORIG_LEN_OFFSET,
+		.new = ALT_NEW_OFFSET,
+		.new_len = ALT_NEW_LEN_OFFSET,
+	},
+	{
+		.sec = "__jump_table",
+		.size = JUMP_ENTRY_SIZE,
+		.orig = JUMP_ORIG_OFFSET,
+		.new = JUMP_NEW_OFFSET,
+	},
+	{
+		.sec = "__ex_table",
+		.size = EX_ENTRY_SIZE,
+		.orig = EX_ORIG_OFFSET,
+		.new = EX_NEW_OFFSET,
+	},
+	{},
+};
+
+static int get_alt_entry(struct elf *elf, struct special_entry *entry,
+			 struct section *sec, int index,
+			 struct special_alt *alt)
+{
+	struct rela *orig_rela, *new_rela;
+	unsigned long offset;
+
+	offset = index * entry->size;
+
+	alt->group = entry->group;
+
+	if (alt->group) {
+		alt->orig_len = *(unsigned char *)(sec->data + offset + \
+						   entry->orig_len);
+		alt->new_len = *(unsigned char *)(sec->data + offset + \
+						  entry->new_len);
+	}
+
+	orig_rela = find_rela_by_dest(sec, offset + entry->orig);
+	if (!orig_rela) {
+		WARN("%s: can't find orig rela",
+		     offstr(sec, offset + entry->orig));
+		return -1;
+	}
+	if (orig_rela->sym->type != STT_SECTION) {
+		WARN("%s: don't know how to handle non-section rela symbol %s",
+		     offstr(sec, offset + entry->orig),
+		     orig_rela->sym->name);
+		return -1;
+	}
+
+	alt->orig_sec = orig_rela->sym->sec;
+	alt->orig_off = orig_rela->addend;
+
+	if (!entry->group || alt->new_len) {
+		new_rela = find_rela_by_dest(sec, offset + entry->new);
+		if (!new_rela) {
+			WARN("%s: can't find new rela",
+			     offstr(sec, offset + entry->new));
+			return -1;
+		}
+		if (new_rela->sym->type != STT_SECTION) {
+			WARN("%s: don't know how to handle non-section rela symbol %s",
+			     offstr(sec, offset + entry->new), new_rela->sym->name);
+			return -1;
+		}
+
+		alt->new_sec = new_rela->sym->sec;
+		alt->new_off = (unsigned int)new_rela->addend;
+
+		/* _ASM_EXTABLE_EX hack */
+		if (alt->new_off >= 0x7ffffff0)
+			alt->new_off -= 0x7ffffff0;
+	}
+
+	return 0;
+}
+
+/*
+ * Read all the special sections and create a list of special_alt structs which
+ * describe all the alternate instructions which can be patched in or
+ * redirected to at runtime.
+ */
+int special_get_alts(struct elf *elf, struct list_head *alts)
+{
+	struct special_entry *entry;
+	struct section *sec;
+	unsigned int nr_entries;
+	struct special_alt *alt;
+	int index, ret;
+
+	INIT_LIST_HEAD(alts);
+
+	for (entry = entries; entry->sec; entry++) {
+		sec = find_section_by_name(elf, entry->sec);
+		if (!sec)
+			continue;
+
+		if (sec->len % entry->size != 0) {
+			WARN("%s size not a multiple of %d",
+			     sec->name, JUMP_ENTRY_SIZE);
+			return -1;
+		}
+
+		nr_entries = sec->len / entry->size;
+
+		for (index = 0; index < nr_entries; index++) {
+			alt = malloc(sizeof(*alt));
+			if (!alt) {
+				WARN("malloc failed");
+				return -1;
+			}
+			memset(alt, 0, sizeof(*alt));
+
+			ret = get_alt_entry(elf, entry, sec, index, alt);
+			if (ret)
+				return ret;
+
+			list_add_tail(&alt->list, alts);
+		}
+	}
+
+	return 0;
+}
diff --git a/scripts/stackvalidate/special.h b/scripts/stackvalidate/special.h
new file mode 100644
index 0000000..fc7ea8e
--- /dev/null
+++ b/scripts/stackvalidate/special.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _SPECIAL_H
+#define _SPECIAL_H
+
+#include <stdbool.h>
+#include "elf.h"
+
+struct special_alt {
+	struct list_head list;
+
+	bool group;
+
+	struct section *orig_sec;
+	unsigned long orig_off;
+
+	struct section *new_sec;
+	unsigned long new_off;
+
+	unsigned int orig_len, new_len; /* group only */
+};
+
+int special_get_alts(struct elf *elf, struct list_head *alts);
+
+#endif /* _SPECIAL_H */
diff --git a/scripts/stackvalidate/stackvalidate.c b/scripts/stackvalidate/stackvalidate.c
new file mode 100644
index 0000000..9a64434
--- /dev/null
+++ b/scripts/stackvalidate/stackvalidate.c
@@ -0,0 +1,858 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * stackvalidate:
+ *
+ * This tool analyzes every .o file and ensures the validity of its stack trace
+ * metadata.  It enforces a set of rules on asm code and C inline assembly code
+ * so that stack traces can be reliable.
+ *
+ * NOTE: This program has a lot of memory leaks.  That's ok.  It's faster and
+ *       easier that way.
+ *
+ * For more information, see Documentation/stack-validation.txt.
+ */
+
+#include <argp.h>
+#include <stdbool.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "elf.h"
+#include "arch.h"
+#include "special.h"
+
+#define STATE_FP_SAVED		0x1
+#define STATE_FP_SETUP		0x2
+
+int warnings;
+
+struct instruction {
+	struct list_head list;
+	struct section *sec;
+	unsigned long offset;
+	unsigned int len, state;
+	unsigned char type;
+	unsigned long immediate;
+	bool alt_group, visited;
+	struct symbol *call_dest;
+	struct instruction *jump_dest;
+	struct list_head alts;
+};
+
+struct list_head insns;
+
+struct alternative {
+	struct list_head list;
+	struct instruction *insn;
+};
+
+struct args {
+	char *args[1];
+	bool nofp;
+};
+struct args args;
+static const char args_doc[] = "file.o";
+static struct argp_option options[] = {
+	{"no-frame-pointer", 1, 0, 0, "Don't check frame pointers" },
+	{0},
+};
+static error_t parse_opt(int key, char *arg, struct argp_state *state)
+{
+	/* Get the input argument from argp_parse, which we
+	   know is a pointer to our args structure. */
+	struct args *args = state->input;
+
+	switch (key) {
+	case 1: /* --no-frame-pointer */
+		args->nofp = true;
+		break;
+
+	case ARGP_KEY_ARG:
+		if (state->arg_num >= 1)
+			/* Too many arguments. */
+			argp_usage(state);
+		args->args[state->arg_num] = arg;
+		break;
+
+	case ARGP_KEY_END:
+		if (state->arg_num < 1)
+			/* Not enough arguments. */
+			argp_usage(state);
+		break;
+
+	default:
+		return ARGP_ERR_UNKNOWN;
+	}
+	return 0;
+}
+static struct argp argp = { options, parse_opt, args_doc, 0 };
+
+/*
+ * Check for the STACKVALIDATE_IGNORE_INSN macro.
+ */
+static bool ignore_insn(struct elf *elf, struct section *sec,
+			unsigned long offset)
+{
+	struct section *macro_sec;
+	struct rela *rela;
+
+	macro_sec = find_section_by_name(elf, "__stackvalidate_ignore_insn");
+	if (!macro_sec || !macro_sec->rela)
+		return false;
+
+	list_for_each_entry(rela, &macro_sec->rela->relas, list)
+		if (rela->sym->type == STT_SECTION &&
+		    rela->sym == sec->sym &&
+		    rela->addend == offset)
+			return true;
+
+	return false;
+}
+
+/*
+ * Check for the STACKVALIDATE_IGNORE_FUNC macro.
+ */
+static bool ignore_func(struct elf *elf, struct symbol *func)
+{
+	struct section *macro_sec;
+	struct rela *rela;
+
+	macro_sec = find_section_by_name(elf, "__stackvalidate_ignore_func");
+	if (!macro_sec || !macro_sec->rela)
+		return false;
+
+	list_for_each_entry(rela, &macro_sec->rela->relas, list)
+		if (rela->sym == func)
+			return true;
+
+	return false;
+}
+
+static struct instruction *find_instruction(struct section *sec,
+					    unsigned long offset)
+{
+	struct instruction *insn;
+
+	list_for_each_entry(insn, &insns, list)
+		if (insn->sec == sec && insn->offset == offset)
+			return insn;
+
+	return NULL;
+}
+
+/*
+ * This checks to see if the given function is a "noreturn" function.
+ *
+ * For global functions which are outside the scope of this object file, we
+ * have to keep a manual list of them.
+ *
+ * For local functions, we have to detect them manually by simply looking for
+ * the lack of a return instruction.
+ */
+static bool dead_end_function(struct symbol *func)
+{
+	struct instruction *insn;
+
+	if (func->bind == STB_GLOBAL &&
+	    (!strcmp(func->name, "__stack_chk_fail") ||
+	     !strcmp(func->name, "panic") ||
+	     !strcmp(func->name, "do_exit")))
+		return true;
+
+	if (!func->sec)
+		return false;
+
+	insn = find_instruction(func->sec, func->offset);
+	if (!insn)
+		return false;
+
+	list_for_each_entry_from(insn, &insns, list) {
+		if (insn->sec != func->sec ||
+		    insn->offset >= func->offset + func->len)
+					break;
+
+		if (insn->type == INSN_RETURN)
+			return false;
+	}
+
+	return true;
+}
+
+/*
+ * Call the arch-specific instruction decoder for all the instructions and add
+ * them to the global insns list.
+ */
+static int decode_instructions(struct elf *elf)
+{
+	struct section *sec;
+	unsigned long offset;
+	struct instruction *insn;
+	int ret;
+
+	INIT_LIST_HEAD(&insns);
+
+	list_for_each_entry(sec, &elf->sections, list) {
+
+		if (!(sec->sh.sh_flags & SHF_EXECINSTR))
+			continue;
+
+		for (offset = 0; offset < sec->len; offset += insn->len) {
+			insn = malloc(sizeof(*insn));
+			memset(insn, 0, sizeof(*insn));
+
+			INIT_LIST_HEAD(&insn->alts);
+			insn->sec = sec;
+			insn->offset = offset;
+
+			ret = arch_decode_instruction(elf, sec, offset,
+						      sec->len - offset,
+						      &insn->len, &insn->type,
+						      &insn->immediate);
+			if (ret)
+				return ret;
+
+			if (!insn->type || insn->type > INSN_LAST) {
+				WARN("%s: invalid instruction type %d",
+				     offstr(sec, insn->offset), insn->type);
+				return -1;
+			}
+
+			list_add_tail(&insn->list, &insns);
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * Find the destination instructions for all jumps.
+ */
+static int get_jump_destinations(struct elf *elf)
+{
+	struct instruction *insn;
+	struct rela *rela;
+	struct section *dest_sec;
+	unsigned long dest_off;
+
+	list_for_each_entry(insn, &insns, list) {
+		if (insn->type != INSN_JUMP_CONDITIONAL &&
+		    insn->type != INSN_JUMP_UNCONDITIONAL)
+			continue;
+
+		rela = find_rela_by_dest_range(insn->sec, insn->offset,
+					       insn->len);
+		if (!rela) {
+			dest_sec = insn->sec;
+			dest_off = insn->offset + insn->len + insn->immediate;
+		} else if (rela->sym->type == STT_SECTION) {
+			dest_sec = rela->sym->sec;
+			dest_off = rela->addend + 4;
+		} else if (rela->sym->sec->index) {
+			dest_sec = rela->sym->sec;
+			dest_off = rela->sym->sym.st_value + rela->addend + 4;
+		} else {
+			/*
+			 * This error (jump to another file) will be handled
+			 * later in validate_functions().
+			 */
+			continue;
+		}
+
+		insn->jump_dest = find_instruction(dest_sec, dest_off);
+		if (!insn->jump_dest) {
+
+			/*
+			 * This is a special case where an alt instruction
+			 * jumps past the end of the section.  These are
+			 * handled later.
+			 */
+			if (!strcmp(insn->sec->name, ".altinstr_replacement"))
+				continue;
+
+			WARN("%s: can't find jump dest instruction at %s+0x%lx",
+			     offstr(insn->sec, insn->offset), dest_sec->name,
+			     dest_off);
+			return -1;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * Find the destination instructions for all calls.
+ */
+static int get_call_destinations(struct elf *elf)
+{
+	struct instruction *insn;
+	unsigned long dest_off;
+	struct rela *rela;
+
+	list_for_each_entry(insn, &insns, list) {
+		if (insn->type != INSN_CALL)
+			continue;
+
+		rela = find_rela_by_dest_range(insn->sec, insn->offset,
+					       insn->len);
+		if (!rela) {
+			dest_off = insn->offset + insn->len + insn->immediate;
+			insn->call_dest = find_symbol_by_offset(insn->sec,
+								dest_off);
+			if (!insn->call_dest) {
+				WARN("%s: can't find call dest symbol at offset 0x%lx",
+				     offstr(insn->sec, insn->offset), dest_off);
+				return -1;
+			}
+		} else if (rela->sym->type == STT_SECTION) {
+			insn->call_dest = find_symbol_by_offset(rela->sym->sec,
+								rela->addend+4);
+			if (!insn->call_dest ||
+			    insn->call_dest->type != STT_FUNC) {
+				WARN("%s: can't find call dest symbol at %s+0x%x",
+				     offstr(insn->sec, insn->offset),
+				     rela->sym->sec->name, rela->addend + 4);
+				return -1;
+			}
+		} else
+			insn->call_dest = rela->sym;
+	}
+
+	return 0;
+}
+
+/*
+ * The .alternatives section requires some extra special care, over and above
+ * what other special sections require:
+ *
+ * 1. Because alternatives are patched in-place, we need to insert a fake jump
+ *    instruction at the end so that validate_branch() skips all the original
+ *    replaced instructions when validating the new instruction path.
+ *
+ * 2. An added wrinkle is that the new instruction length might be zero.  In
+ *    that case the old instructions are replaced with noops.  We simulate that
+ *    by creating a fake jump as the only new instruction.
+ *
+ * 3. In some cases, the alternative section includes an instruction which
+ *    conditionally jumps to the _end_ of the entry.  We have to modify these
+ *    jumps' destinations to point back to .text rather than the end of the
+ *    entry in .altinstr_replacement.
+ */
+static int handle_group_alt(struct elf *elf, struct special_alt *special_alt,
+			    struct instruction *orig_insn,
+			    struct instruction **new_insn)
+{
+	struct instruction *last_orig_insn, *last_new_insn, *insn, *fake_jump;
+	unsigned long dest_off;
+
+	last_orig_insn = NULL;
+	insn = orig_insn;
+	list_for_each_entry_from(insn, &insns, list) {
+		if (insn->sec != special_alt->orig_sec ||
+		    insn->offset >= special_alt->orig_off + special_alt->orig_len)
+			break;
+
+		insn->alt_group = true;
+		last_orig_insn = insn;
+	}
+
+	if (list_is_last(&last_orig_insn->list, &insns) ||
+			 list_next_entry(last_orig_insn, list)->sec != special_alt->orig_sec) {
+		WARN("%s: don't know how to handle alternatives at end of section",
+		     special_alt->orig_sec->name);
+		return -1;
+	}
+
+	fake_jump = malloc(sizeof(*fake_jump));
+	if (!fake_jump) {
+		WARN("malloc failed");
+		return -1;
+	}
+	memset(fake_jump, 0, sizeof(*fake_jump));
+	INIT_LIST_HEAD(&fake_jump->alts);
+	fake_jump->sec = special_alt->new_sec;
+	fake_jump->offset = -1;
+	fake_jump->type = INSN_JUMP_UNCONDITIONAL;
+	fake_jump->jump_dest = list_next_entry(last_orig_insn, list);
+
+	if (!special_alt->new_len) {
+		*new_insn = fake_jump;
+		return 0;
+	}
+
+	last_new_insn = NULL;
+	insn = *new_insn;
+	list_for_each_entry_from(insn, &insns, list) {
+		if (insn->sec != special_alt->new_sec ||
+		    insn->offset >= special_alt->new_off + special_alt->new_len)
+			break;
+
+		last_new_insn = insn;
+
+		if (insn->type != INSN_JUMP_CONDITIONAL &&
+		    insn->type != INSN_JUMP_UNCONDITIONAL)
+			continue;
+
+		if (!insn->immediate)
+			continue;
+
+		dest_off = insn->offset + insn->len + insn->immediate;
+		if (dest_off == special_alt->new_off + special_alt->new_len)
+			insn->jump_dest = fake_jump;
+
+		if (!insn->jump_dest) {
+			WARN("%s: can't find alternative jump destination",
+			     offstr(insn->sec, insn->offset));
+			return -1;
+		}
+	}
+
+	if (!last_new_insn) {
+		WARN("%s: can't find last new alternative instruction",
+		     offstr(special_alt->new_sec, special_alt->new_off));
+		return -1;
+	}
+
+	list_add(&fake_jump->list, &last_new_insn->list);
+
+	return 0;
+}
+
+/*
+ * Read all the special sections which have alternate instructions which can be
+ * patched in or redirected to at runtime.  Each instruction having alternate
+ * instruction(s) has them added to its insn->alts list, which will be
+ * traversed in validate_branch().
+ */
+static int get_special_section_alts(struct elf *elf)
+{
+	struct list_head special_alts;
+	struct instruction *orig_insn, *new_insn;
+	struct special_alt *special_alt, *tmp;
+	struct alternative *alt;
+	int ret;
+
+	ret = special_get_alts(elf, &special_alts);
+	if (ret)
+		return ret;
+
+	list_for_each_entry_safe(special_alt, tmp, &special_alts, list) {
+		alt = malloc(sizeof(*alt));
+		if (!alt) {
+			WARN("malloc failed");
+			return -1;
+		}
+
+		orig_insn = find_instruction(special_alt->orig_sec,
+					     special_alt->orig_off);
+		if (!orig_insn) {
+			WARN("%s: special: can't find orig instruction",
+			     offstr(special_alt->orig_sec,
+				    special_alt->orig_off));
+			return -1;
+		}
+
+		new_insn = NULL;
+		if (!special_alt->group || special_alt->new_len) {
+			new_insn = find_instruction(special_alt->new_sec,
+						    special_alt->new_off);
+			if (!new_insn) {
+				WARN("%s: special: can't find new instruction",
+				     offstr(special_alt->new_sec,
+					    special_alt->new_off));
+				return -1;
+			}
+		}
+
+		if (special_alt->group) {
+			ret = handle_group_alt(elf, special_alt, orig_insn,
+					       &new_insn);
+			if (ret)
+				return ret;
+		}
+
+		alt->insn = new_insn;
+		list_add_tail(&alt->list, &orig_insn->alts);
+	}
+
+	return 0;
+}
+
+/*
+ * For some switch statements, gcc generates a jump table in the .rodata
+ * section which contains a list of addresses within the function to jump to.
+ * This finds these jump tables and adds them to the insn->alts lists.
+ */
+static int get_switch_alts(struct elf *elf)
+{
+	struct instruction *insn, *alt_insn;
+	struct rela *rodata_rela, *rela;
+	struct section *rodata;
+	struct symbol *func;
+	struct alternative *alt;
+
+	list_for_each_entry(insn, &insns, list) {
+		if (insn->type != INSN_JUMP_DYNAMIC)
+			continue;
+
+		rodata_rela = find_rela_by_dest_range(insn->sec, insn->offset,
+						      insn->len);
+		if (!rodata_rela || strcmp(rodata_rela->sym->name, ".rodata"))
+			continue;
+
+		rodata = find_section_by_name(elf, ".rodata");
+		if (!rodata || !rodata->rela)
+			continue;
+
+		rela = find_rela_by_dest(rodata, rodata_rela->addend);
+		if (!rela)
+			continue;
+
+		func = find_containing_func(insn->sec, insn->offset);
+		if (!func) {
+			WARN("%s: can't find containing func",
+			     offstr(insn->sec, insn->offset));
+			return -1;
+		}
+
+		list_for_each_entry_from(rela, &rodata->rela->relas, list) {
+			if (rela->sym->sec != insn->sec ||
+			    rela->addend <= func->offset ||
+			    rela->addend >= func->offset + func->len)
+				break;
+
+			alt_insn = find_instruction(insn->sec, rela->addend);
+			if (!alt_insn) {
+				WARN("%s: can't find instruction at %s+0x%x",
+				     rodata->rela->name, insn->sec->name,
+				     rela->addend);
+				return -1;
+			}
+
+			alt = malloc(sizeof(*alt));
+			if (!alt) {
+				WARN("malloc failed");
+				return -1;
+			}
+
+			alt->insn = alt_insn;
+			list_add_tail(&alt->list, &insn->alts);
+		}
+	}
+
+	return 0;
+}
+
+static int decode_sections(struct elf *elf)
+{
+	int ret;
+
+	ret = decode_instructions(elf);
+	if (ret)
+		return ret;
+
+	ret = get_jump_destinations(elf);
+	if (ret)
+		return ret;
+
+	ret = get_call_destinations(elf);
+	if (ret)
+		return ret;
+
+	ret = get_special_section_alts(elf);
+	if (ret)
+		return ret;
+
+	ret = get_switch_alts(elf);
+	if (ret)
+		return ret;
+
+	return 0;
+}
+
+/*
+ * Follow the branch starting at the given instruction, and recursively follow
+ * any other branches (jumps).  Meanwhile, track the frame pointer state at
+ * each instruction and validate all the rules described in
+ * Documentation/stack-validation.txt.
+ */
+static int validate_branch(struct elf *elf, struct instruction *first,
+			   unsigned char first_state)
+{
+	struct alternative *alt;
+	struct instruction *insn;
+	struct section *sec;
+	unsigned char state;
+	int ret, warnings = 0;
+
+	insn = first;
+	sec = insn->sec;
+	state = first_state;
+
+	if (insn->alt_group && list_empty(&insn->alts)) {
+		WARN("%s: don't know how to handle branch to middle of alternative instruction group",
+		     offstr(sec, insn->offset));
+		warnings++;
+	}
+
+	while (1) {
+		if (insn->visited) {
+			if (insn->state != state) {
+				WARN("%s: frame pointer state mismatch",
+				     offstr(sec, insn->offset));
+				warnings++;
+			}
+
+			return warnings;
+		}
+
+		insn->visited = true;
+		insn->state = state;
+
+		list_for_each_entry(alt, &insn->alts, list) {
+			ret = validate_branch(elf, alt->insn, state);
+			warnings += ret;
+		}
+
+		switch (insn->type) {
+
+		case INSN_FP_SAVE:
+			if (!args.nofp) {
+				if (insn->state & STATE_FP_SAVED) {
+					WARN("%s: duplicate frame pointer save",
+					     offstr(sec, insn->offset));
+					warnings++;
+				}
+				state |= STATE_FP_SAVED;
+			}
+			break;
+
+		case INSN_FP_SETUP:
+			if (!args.nofp) {
+				if (insn->state & STATE_FP_SETUP) {
+					WARN("%s: duplicate frame pointer setup",
+					     offstr(sec, insn->offset));
+					warnings++;
+				}
+				state |= STATE_FP_SETUP;
+			}
+			break;
+
+		case INSN_FP_RESTORE:
+			if (!args.nofp) {
+				if (!(insn->state & STATE_FP_SAVED) ||
+				    !(insn->state & STATE_FP_SETUP)) {
+					WARN("%s: frame pointer restore without save/setup",
+					     offstr(sec, insn->offset));
+					warnings++;
+				}
+				state &= ~STATE_FP_SAVED;
+				state &= ~STATE_FP_SETUP;
+			}
+			break;
+
+		case INSN_RETURN:
+			if (!args.nofp && ((insn->state & STATE_FP_SAVED) ||
+					   (insn->state & STATE_FP_SETUP))) {
+				WARN("%s: return without frame pointer restore",
+				     offstr(sec, insn->offset));
+				warnings++;
+			}
+			return warnings;
+
+		case INSN_CALL:
+			if (insn->call_dest->type == STT_NOTYPE &&
+			    !strcmp(insn->call_dest->name, "__fentry__"))
+				break;
+
+			if (dead_end_function(insn->call_dest))
+				return warnings;
+
+			/* fallthrough */
+
+		case INSN_CALL_DYNAMIC:
+			if (!args.nofp && (!(insn->state & STATE_FP_SAVED) ||
+					   !(insn->state & STATE_FP_SETUP))) {
+				WARN("%s: call without frame pointer save/setup",
+				     offstr(sec, insn->offset));
+				warnings++;
+			}
+			break;
+
+		case INSN_JUMP_CONDITIONAL:
+		case INSN_JUMP_UNCONDITIONAL:
+			if (!insn->jump_dest) {
+				WARN("%s: jump to outside file from callable instruction",
+				     offstr(sec, insn->offset));
+				warnings++;
+			} else {
+				ret = validate_branch(elf, insn->jump_dest,
+						      state);
+				warnings += ret;
+			}
+
+			if (insn->type == INSN_JUMP_UNCONDITIONAL)
+				return warnings;
+
+			break;
+
+		case INSN_JUMP_DYNAMIC:
+			if (list_empty(&insn->alts)) {
+				WARN("%s: jump to dynamic address from callable instruction",
+				     offstr(sec, insn->offset));
+				warnings++;
+			}
+
+			return warnings;
+
+		case INSN_CONTEXT_SWITCH:
+			WARN("%s: context switch from callable instruction",
+			     offstr(sec, insn->offset));
+			warnings++;
+
+			return warnings;
+
+		case INSN_BUG:
+			return warnings;
+
+		}
+
+		insn = list_next_entry(insn, list);
+
+		if (&insn->list == &insns || insn->sec != sec) {
+			WARN("%s: unexpected end of section", sec->name);
+			warnings++;
+			return warnings;
+		}
+	}
+
+	return warnings;
+}
+
+static int validate_functions(struct elf *elf)
+{
+	struct section *sec;
+	struct symbol *func;
+	struct instruction *insn;
+	int ret, warnings = 0;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		list_for_each_entry(func, &sec->symbols, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			insn = find_instruction(sec, func->offset);
+			if (!insn) {
+				WARN("%s(): can't find starting instruction", func->name);
+				warnings++;
+				continue;
+			}
+
+			if (ignore_func(elf, func)) {
+				list_for_each_entry_from(insn, &insns, list) {
+					if (insn->sec != func->sec ||
+					    insn->offset >= func->offset + func->len)
+						break;
+					insn->visited = true;
+				}
+			}
+
+			ret = validate_branch(elf, insn, 0);
+			warnings += ret;
+		}
+	}
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		list_for_each_entry(func, &sec->symbols, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			insn = find_instruction(sec, func->offset);
+			if (!insn)
+				continue;
+
+			list_for_each_entry_from(insn, &insns, list) {
+				if (insn->sec != func->sec ||
+				    insn->offset >= func->offset + func->len)
+					break;
+
+				if (!insn->visited && insn->type != INSN_NOP) {
+					WARN("%s: function has unreachable instruction",
+					     offstr(insn->sec, insn->offset));
+					warnings++;
+				}
+
+				insn->visited = true;
+			}
+		}
+	}
+
+	return warnings;
+}
+
+static int validate_uncallable_instructions(struct elf *elf)
+{
+	struct instruction *insn;
+	int warnings = 0;
+
+	list_for_each_entry(insn, &insns, list) {
+		if (!insn->visited && insn->type == INSN_RETURN &&
+		    !ignore_insn(elf, insn->sec, insn->offset)) {
+			WARN("%s: return instruction outside of a callable function",
+			     offstr(insn->sec, insn->offset));
+			warnings++;
+		}
+	}
+
+	return warnings;
+}
+
+int main(int argc, char *argv[])
+{
+	struct elf *elf;
+	int ret = 0, warnings = 0;
+
+	argp_parse(&argp, argc, argv, 0, 0, &args);
+
+	elf = elf_open(args.args[0]);
+	if (!elf) {
+		fprintf(stderr, "error reading elf file %s\n", args.args[0]);
+		return 1;
+	}
+
+	ret = decode_sections(elf);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
+	ret = validate_functions(elf);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
+	ret = validate_uncallable_instructions(elf);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
+out:
+	/* ignore warnings for now until we get all the code cleaned up */
+	if (ret || warnings)
+		return 0;
+	return 0;
+}
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/