[PATCH v4 1/3] x86, stackvalidate: Compile-time stack frame pointer validation

[Josh Poimboeuf <jpoimboe@redhat.com>]

Frame pointer based stack traces aren't always reliable.  One big reason
is that most asm functions don't set up the frame pointer.

Fix that by enforcing that all asm functions honor CONFIG_FRAME_POINTER.
This is done with a new stackvalidate host tool which is automatically
run for every compiled .S file and which validates that every asm
function does the proper frame pointer setup.

Also, to make sure somebody didn't forget to annotate their callable asm code
as a function, flag an error for any return instructions which are hiding
outside of a function.  In almost all cases, return instructions are part of
callable functions and should be annotated as such so that we can validate
their frame pointer usage.  A whitelist mechanism exists for those few return
instructions which are not actually in callable code.

It currently only supports x86_64.  It *almost* supports x86_32, but the
stackvalidate code doesn't yet know how to deal with 32-bit REL
relocations for the return whitelists.  I tried to make the code generic
so that support for other architectures can be plugged in pretty easily.

As a first step, CONFIG_STACK_VALIDATION is disabled by default, and all
reported non-compliances result in warnings.  Right now I'm seeing 200+
warnings.  Once we get them all cleaned up, we can change the default to
CONFIG_STACK_VALIDATION=y and change the warnings to build errors so the
asm code can stay clean.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Acked-by: Michal Marek <mmarek@suse.cz>
---
 MAINTAINERS                           |   6 +
 arch/Kconfig                          |   3 +
 arch/x86/Kconfig                      |   1 +
 arch/x86/Makefile                     |   6 +-
 lib/Kconfig.debug                     |  11 ++
 scripts/Makefile                      |   1 +
 scripts/Makefile.build                |  22 ++-
 scripts/stackvalidate/Makefile        |  17 ++
 scripts/stackvalidate/arch-x86.c      | 134 +++++++++++++
 scripts/stackvalidate/arch.h          |  10 +
 scripts/stackvalidate/elf.c           | 352 ++++++++++++++++++++++++++++++++++
 scripts/stackvalidate/elf.h           |  56 ++++++
 scripts/stackvalidate/list.h          | 217 +++++++++++++++++++++
 scripts/stackvalidate/stackvalidate.c | 226 ++++++++++++++++++++++
 14 files changed, 1059 insertions(+), 3 deletions(-)
 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/stackvalidate.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 78ea7b6..6d700bf 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -9451,6 +9451,12 @@ L:	stable@vger.kernel.org
 S:	Supported
 F:	Documentation/stable_kernel_rules.txt
 
+STACK VALIDATION
+M:	Josh Poimboeuf <jpoimboe@redhat.com>
+S:	Supported
+F:	scripts/stackvalidate/
+F:	arch/x86/include/asm/func.h
+
 STAGING SUBSYSTEM
 M:	Greg Kroah-Hartman <gregkh@linuxfoundation.org>
 T:	git git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging.git
diff --git a/arch/Kconfig b/arch/Kconfig
index bec6666..a5c3f50 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -506,6 +506,9 @@ config HAVE_COPY_THREAD_TLS
 	  normal C parameter passing, rather than extracting the syscall
 	  argument from pt_regs.
 
+config HAVE_STACK_VALIDATION
+	bool
+
 #
 # ABI hall of shame
 #
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index c92fdcc..d60a2378a 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -146,6 +146,7 @@ config X86
 	select ACPI_LEGACY_TABLES_LOOKUP if ACPI
 	select X86_FEATURE_NAMES if PROC_FS
 	select SRCU
+	select HAVE_STACK_VALIDATION if FRAME_POINTER && X86_64
 
 config INSTRUCTION_DECODER
 	def_bool y
diff --git a/arch/x86/Makefile b/arch/x86/Makefile
index 57996ee..c5598a0 100644
--- a/arch/x86/Makefile
+++ b/arch/x86/Makefile
@@ -180,9 +180,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 eb3997b..7bfaf80 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 kernel stack validation"
+	depends on HAVE_STACK_VALIDATION
+	default n
+	help
+	  Add compile-time validations which help make kernel stack traces more
+	  reliable.  This includes checks to ensure that assembly functions
+	  save, update and restore the frame pointer or the back chain pointer.
+
+
 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..3b05833 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -253,6 +253,24 @@ define rule_cc_o_c
 	mv -f $(dot-target).tmp $(dot-target).cmd
 endef
 
+ifdef CONFIG_STACK_VALIDATION
+stackvalidate = $(objtree)/scripts/stackvalidate/stackvalidate
+cmd_stackvalidate =							  \
+	case $(@) in							  \
+		arch/x86/purgatory/*) ;;				  \
+		*) $(stackvalidate) "$(@)"; \
+	esac;
+endif
+
+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
 	$(call cmd,force_checksrc)
@@ -290,8 +308,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..6027ec4
--- /dev/null
+++ b/scripts/stackvalidate/Makefile
@@ -0,0 +1,17 @@
+hostprogs-y := stackvalidate
+always := $(hostprogs-y)
+
+stackvalidate-objs := stackvalidate.o elf.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..fbc0756
--- /dev/null
+++ b/scripts/stackvalidate/arch-x86.c
@@ -0,0 +1,134 @@
+#include <stdio.h>
+
+#define unlikely(cond) (cond)
+#include <asm/insn.h>
+#include <inat.c>
+#include <insn.c>
+
+#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;
+	}
+}
+
+/*
+ * arch_validate_function() - Ensures the given asm function saves, sets up,
+ * and restores the frame pointer.
+ *
+ * The frame pointer prologue/epilogue should look something like:
+ *
+ *   push %rbp
+ *   mov %rsp, %rbp
+ *   [ function body ]
+ *   pop %rbp
+ *   ret
+ *
+ * Return value:
+ *   -1: bad instruction
+ *    1: missing frame pointer logic
+ *    0: validation succeeded
+ */
+int arch_validate_function(struct elf *elf, struct symbol *func)
+{
+	struct insn insn;
+	unsigned long addr, length;
+	int push, mov, pop, ret, x86_64;
+
+	push = mov = pop = ret = 0;
+
+	x86_64 = is_x86_64(elf);
+	if (x86_64 == -1)
+		return -1;
+
+	for (addr = func->start; addr < func->end; addr += length) {
+		insn_init(&insn, (void *)addr, func->end - addr, x86_64);
+		insn_get_length(&insn);
+		length = insn.length;
+		insn_get_opcode(&insn);
+		if (!length || !insn.opcode.got) {
+			WARN("%s+0x%lx: bad instruction", func->name,
+			     addr - func->start);
+			return -1;
+		}
+
+		switch (insn.opcode.bytes[0]) {
+		case 0x55:
+			if (!insn.rex_prefix.nbytes)
+				/* push bp */
+				push++;
+			break;
+		case 0x5d:
+			if (!insn.rex_prefix.nbytes)
+				/* pop bp */
+				pop++;
+			break;
+		case 0xc9: /* leave */
+			pop++;
+			break;
+		case 0x89:
+			insn_get_modrm(&insn);
+			if (insn.modrm.bytes[0] == 0xe5)
+				/* mov sp, bp */
+				mov++;
+			break;
+		case 0xc3: /* ret */
+			ret++;
+			break;
+		}
+	}
+
+	if (push != 1 || mov != 1 || !pop || !ret || pop != ret) {
+		WARN("%s() is missing frame pointer logic.  Please use FUNC_ENTER.",
+		     func->name);
+		return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * arch_is_return_insn() - Determines whether the instruction at the given
+ * address is a return instruction.  Also returns the instruction length in
+ * *len.
+ *
+ * Return value:
+ *   -1: bad instruction
+ *    0: no, it's not a return instruction
+ *    1: yes, it's a return instruction
+ */
+int arch_is_return_insn(struct elf *elf, unsigned long addr,
+			unsigned int maxlen, unsigned int *len)
+{
+	struct insn insn;
+	int x86_64;
+
+	x86_64 = is_x86_64(elf);
+	if (x86_64 == -1)
+		return -1;
+
+	insn_init(&insn, (void *)addr, maxlen, x86_64);
+	insn_get_length(&insn);
+	insn_get_opcode(&insn);
+	if (!insn.opcode.got)
+		return -1;
+
+	*len = insn.length;
+
+	switch (insn.opcode.bytes[0]) {
+	case 0xc2: case 0xc3: /* ret near */
+	case 0xca: case 0xcb: /* ret far */
+		return 1;
+	}
+
+	return 0;
+}
diff --git a/scripts/stackvalidate/arch.h b/scripts/stackvalidate/arch.h
new file mode 100644
index 0000000..3b91b1c
--- /dev/null
+++ b/scripts/stackvalidate/arch.h
@@ -0,0 +1,10 @@
+#ifndef _ARCH_H_
+#define _ARCH_H_
+
+#include "elf.h"
+
+int arch_validate_function(struct elf *elf, struct symbol *func);
+int arch_is_return_insn(struct elf *elf, unsigned long addr,
+			unsigned int maxlen, unsigned int *len);
+
+#endif /* _ARCH_H_ */
diff --git a/scripts/stackvalidate/elf.c b/scripts/stackvalidate/elf.c
new file mode 100644
index 0000000..a1419a5
--- /dev/null
+++ b/scripts/stackvalidate/elf.c
@@ -0,0 +1,352 @@
+/*
+ * elf.c - ELF access library
+ *
+ * Adapted from kpatch (https://github.com/dynup/kpatch):
+ * Copyright (C) 2013-2015 Josh Poimboeuf <jpoimboe@redhat.com>
+ * Copyright (C) 2014 Seth Jennings <sjenning@redhat.com>
+ *
+ * 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"
+
+struct section *elf_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 *elf_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 *elf_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;
+}
+
+static int elf_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->data = elf_getdata(s, NULL);
+		if (!sec->data) {
+			perror("elf_getdata");
+			return -1;
+		}
+
+		if (sec->data->d_off != 0 ||
+		    sec->data->d_size != sec->sh.sh_size) {
+			WARN("unexpected data attributes for %s", sec->name);
+			return -1;
+		}
+
+		sec->start = (unsigned long)sec->data->d_buf;
+		sec->end = sec->start + sec->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 elf_read_symbols(struct elf *elf)
+{
+	struct section *symtab;
+	struct symbol *sym;
+	struct list_head *entry, *tmp;
+	int symbols_nr, i;
+
+	symtab = elf_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->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 = elf_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;
+		} else
+			sym->sec = elf_find_section_by_index(elf, 0);
+
+		sym->start = sym->sec->start + sym->sym.st_value;
+		sym->end = sym->start + 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->start > s->start) {
+				entry = tmp;
+				break;
+			}
+
+			if (sym->start == s->start && sym->end >= s->end) {
+				entry = tmp;
+				break;
+			}
+		}
+		list_add(&sym->list, entry);
+	}
+
+	return 0;
+
+err:
+	free(sym);
+	return -1;
+}
+
+static int elf_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 = elf_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->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 = elf_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 (elf_read_sections(elf))
+		goto err;
+
+	if (elf_read_symbols(elf))
+		goto err;
+
+	if (elf_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..db5d5fa
--- /dev/null
+++ b/scripts/stackvalidate/elf.h
@@ -0,0 +1,56 @@
+#ifndef _ELF_H_
+#define _ELF_H_
+
+#include <gelf.h>
+#include "list.h"
+
+#define WARN(format, ...) \
+	fprintf(stderr, \
+		"%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;
+	Elf_Data *data;
+	char *name;
+	int index;
+	unsigned long start, end;
+};
+
+struct symbol {
+	struct list_head list;
+	GElf_Sym sym;
+	struct section *sec;
+	char *name;
+	int index;
+	unsigned char bind, type;
+	unsigned long start, end;
+};
+
+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 *elf_find_section_by_name(struct elf *elf, const char *name);
+void elf_close(struct elf *elf);
+
+#endif /* _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/stackvalidate.c b/scripts/stackvalidate/stackvalidate.c
new file mode 100644
index 0000000..07f1110
--- /dev/null
+++ b/scripts/stackvalidate/stackvalidate.c
@@ -0,0 +1,226 @@
+/*
+ * stackvalidate.c
+ *
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@redhat.com>
+ *
+ * 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 tool automatically runs for every compiled .S file and validates that
+ * every asm function does the proper frame pointer setup.
+ *
+ * Also, to make sure somebody didn't forget to annotate their callable asm
+ * code as a function (e.g. via the FUNC_ENTER/FUNC_RETURN macros), it flags an
+ * error for any return instructions which are hiding outside of a function.
+ * In almost all cases, return instructions are part of callable functions and
+ * should be annotated as such so that we can validate their frame pointer
+ * usage.
+ *
+ * Whitelist mechanisms exist (RET_NOVALIDATE and FILE_NOVALIDATE) for those
+ * few return instructions which are not actually in callable code.
+ */
+
+#include <argp.h>
+#include <stdbool.h>
+
+#include "elf.h"
+#include "arch.h"
+
+int warnings;
+
+struct args {
+	char *args[1];
+};
+static const char args_doc[] = "file.o";
+static struct argp_option options[] = {
+	{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 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 RET_NOVALIDATE macro.
+ */
+static bool is_ret_whitelisted(struct elf *elf, struct section *sec,
+			       unsigned long offset)
+{
+	struct section *wlsec;
+	struct rela *rela;
+
+	wlsec = elf_find_section_by_name(elf,
+					 ".rela__stackvalidate_whitelist_ret");
+	if (!wlsec)
+		return false;
+
+	list_for_each_entry(rela, &wlsec->relas, list)
+		if (rela->sym->type == STT_SECTION &&
+		    rela->sym->index == sec->index && rela->addend == offset)
+			return true;
+
+	return false;
+}
+
+/*
+ * Check for the FILE_NOVALIDATE macro.
+ */
+static bool is_file_whitelisted(struct elf *elf)
+{
+	if (elf_find_section_by_name(elf, "__stackvalidate_whitelist_file"))
+		return true;
+
+	return false;
+}
+
+/*
+ * For the given collection of instructions which are outside an STT_FUNC
+ * function, ensure there are no (whitelisted) return instructions.
+ */
+static int validate_nonfunction(struct elf *elf, struct section *sec,
+				unsigned long start, unsigned long end)
+{
+	unsigned long addr;
+	unsigned int len;
+	int ret, warnings = 0;
+
+	for (addr = start; addr < end; addr += len) {
+		ret = arch_is_return_insn(elf, addr, end - addr, &len);
+		if (ret == -1)
+			return -1;
+
+		if (ret && !is_ret_whitelisted(elf, sec, addr - sec->start)) {
+			WARN("return instruction outside of a function at %s+0x%lx.  Please use FUNC_ENTER.",
+			     sec->name, addr - sec->start);
+			warnings++;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * For the given section, ensure that:
+ *
+ * 1) all STT_FUNC functions do the proper frame pointer setup; and
+ * 2) any other instructions outside of STT_FUNC aren't return instructions
+ *    (unless they're annotated with the RET_NOVALIDATE macro).
+ */
+static int validate_section(struct elf *elf, struct section *sec)
+{
+	struct symbol *func, *last_func;
+	struct symbol null_func = {};
+	int ret, warnings = 0;
+
+	if (!(sec->sh.sh_flags & SHF_EXECINSTR))
+		return 0;
+
+	if (list_empty(&sec->symbols)) {
+		WARN("%s: no symbols", sec->name);
+		return -1;
+	}
+
+	last_func = &null_func;
+	last_func->start = last_func->end = sec->start;
+	list_for_each_entry(func, &sec->symbols, list) {
+		if (func->type != STT_FUNC)
+			continue;
+
+		if (func->start != last_func->start &&
+		    func->end != last_func->end &&
+		    func->start < last_func->end) {
+			WARN("overlapping functions %s and %s",
+			     last_func->name, func->name);
+			warnings++;
+		}
+
+		if (func->start > last_func->end) {
+			ret = validate_nonfunction(elf, sec, last_func->end,
+						   func->start);
+			if (ret < 0)
+				return -1;
+
+			warnings += ret;
+		}
+
+		ret = arch_validate_function(elf, func);
+		if (ret < 0)
+			return -1;
+
+		warnings += ret;
+
+		last_func = func;
+	}
+
+	if (last_func->end < sec->end) {
+		ret = validate_nonfunction(elf, sec, last_func->end, sec->end);
+		if (ret < 0)
+			return -1;
+
+		warnings += ret;
+	}
+
+	return warnings;
+}
+
+int main(int argc, char *argv[])
+{
+	struct args args;
+	struct elf *elf;
+	struct section *sec;
+	int ret, 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;
+	}
+
+	if (is_file_whitelisted(elf))
+		return 0;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		ret = validate_section(elf, sec);
+		if (ret < 0)
+			return 1;
+
+		warnings += ret;
+	}
+
+	/* ignore warnings for now until we get all the asm code cleaned up */
+	return 0;
+}
-- 
2.1.0