[PATCH v2 0/2] Compile-time stack frame pointer validation

[PATCH v2 0/2] Compile-time stack frame pointer validation

[Josh Poimboeuf]

In discussions around the live kernel patching consistency model RFC [1], Peter
and Ingo correctly pointed out that stack traces aren't reliable.  And as Ingo
said, there's no "strong force" which ensures we can rely on them.

So I've been thinking about how to fix that.  My goal is to eventually make
stack traces reliable.  Or at the very least, to be able to detect at runtime
when a given stack trace *might* be unreliable.  But improved stack traces
would broadly benefit the entire kernel, regardless of the outcome of the live
kernel patching consistency model discussions.

This patch set is just the first in a series of proposed stack trace
reliability improvements.  Future proposals will include runtime stack
reliability checking, as well as compile-time and runtime DWARF validations.

As far as I can tell, there are two main obstacles which prevent frame pointer
based stack traces from being reliable:

1) Missing frame pointer logic: currently, most assembly functions don't set up
   the frame pointer.

2) Interrupts: if a function is interrupted before it can save and set up
   the frame pointer, its caller won't show up in the stack trace.

This patch set aims to remove the first obstacle 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, 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 warnings to build errors so the asm code can stay clean.

The patches are based on linux-next.  Patch 1 adds the stackvalidate host tool.
Patch 2 adds some helper macros for asm functions so that they can comply with
stackvalidate.

[1] http://lkml.kernel.org/r/cover.1423499826.git.jpoimboe@redhat.com

v2:
- Fixed memory leaks reported by Petr Mladek

Josh Poimboeuf (2):
  x86, stackvalidate: Compile-time stack frame pointer validation
  x86, stackvalidate: Add asm frame pointer setup macros

 MAINTAINERS                           |   6 +
 arch/Kconfig                          |   4 +
 arch/x86/Kconfig                      |   1 +
 arch/x86/Makefile                     |   6 +-
 arch/x86/include/asm/func.h           |  82 ++++++++
 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 ++++++++++++++++++++++
 15 files changed, 1142 insertions(+), 3 deletions(-)
 create mode 100644 arch/x86/include/asm/func.h
 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

-- 
2.1.0

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

[Josh Poimboeuf]

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, 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 warnings to build errors so the asm code can stay clean.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 MAINTAINERS                           |   6 +
 arch/Kconfig                          |   4 +
 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, 1060 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 b99e5b8..86258e6 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -9365,6 +9365,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 a65eafb..9e7e388 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -499,6 +499,10 @@ config ARCH_HAS_ELF_RANDOMIZE
 	  - arch_mmap_rnd()
 	  - arch_randomize_brk()
 
+config HAVE_STACK_VALIDATION
+	bool
+
+
 #
 # ABI hall of shame
 #
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 9cee995..ed41a76 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -144,6 +144,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 2fda005..72f2f04 100644
--- a/arch/x86/Makefile
+++ b/arch/x86/Makefile
@@ -171,9 +171,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 8eaed3dd..b8a6884 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 y
+	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..b2a7c6f
--- /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

[PATCH v2 2/2] x86, stackvalidate: Add asm frame pointer setup macros

[Josh Poimboeuf]

Add some helper macros for asm functions so that they can comply with
stackvalidate.

The FUNC_ENTER and FUNC_RETURN macros help asm functions save, set up,
and restore frame pointers.

The RET_NOVALIDATE and FILE_NOVALIDATE macros can be used to whitelist
the few locations which need a return instruction outside of a callable
function.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 arch/x86/include/asm/func.h | 82 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)
 create mode 100644 arch/x86/include/asm/func.h

diff --git a/arch/x86/include/asm/func.h b/arch/x86/include/asm/func.h
new file mode 100644
index 0000000..ae84196
--- /dev/null
+++ b/arch/x86/include/asm/func.h
@@ -0,0 +1,82 @@
+#ifndef _ASM_X86_FUNC_H
+#define _ASM_X86_FUNC_H
+
+#include <linux/linkage.h>
+#include <asm/dwarf2.h>
+#include <asm/asm.h>
+
+.macro FUNC_ENTER_NO_FP name
+	ENTRY(\name)
+	CFI_STARTPROC
+	CFI_DEF_CFA _ASM_SP, __ASM_SEL(4, 8)
+.endm
+
+.macro FUNC_RETURN_NO_FP name
+	CFI_DEF_CFA _ASM_SP, __ASM_SEL(4, 8)
+	__ASM_SIZE(ret)
+	CFI_ENDPROC
+	ENDPROC(\name)
+.endm
+
+#ifdef CONFIG_FRAME_POINTER
+
+.macro FUNC_ENTER_FP name
+	FUNC_ENTER_NO_FP \name
+	__ASM_SIZE(push, _cfi) %_ASM_BP
+	CFI_REL_OFFSET _ASM_BP, 0
+	_ASM_MOV %_ASM_SP, %_ASM_BP
+	CFI_DEF_CFA_REGISTER _ASM_BP
+.endm
+
+.macro FUNC_RETURN_FP name
+	__ASM_SIZE(pop, _cfi) %_ASM_BP
+	CFI_RESTORE _ASM_BP
+	FUNC_RETURN_NO_FP \name
+.endm
+
+/*
+ * Every callable asm function should be bookended with FUNC_ENTER and
+ * FUNC_RETURN.  They do proper frame pointer and DWARF CFI setups in order to
+ * achieve more reliable stack traces.
+ *
+ * For the sake of simplicity and correct DWARF annotations, use of the macros
+ * requires that the return instruction comes at the end of the function.
+ */
+#define FUNC_ENTER(name) FUNC_ENTER_FP name
+#define FUNC_RETURN(name) FUNC_RETURN_FP name
+
+/*
+ * RET_NOVALIDATE tells the stack validation script to whitelist the return
+ * instruction immediately after the macro.  Only use it if you're completely
+ * sure you need a return instruction outside of a callable function.
+ * Otherwise, if the code can be called and you haven't annotated it with
+ * FUNC_ENTER/FUNC_RETURN, it will break stack trace reliability.
+ */
+.macro RET_NOVALIDATE
+	163:
+	.pushsection __stackvalidate_whitelist_ret, "ae"
+	_ASM_ALIGN
+	.long 163b - .
+	.popsection
+.endm
+
+/*
+ * FILE_NOVALIDATE is like RET_NOVALIDATE except it whitelists the entire file.
+ * Use with extreme caution or you will silently break stack traces.
+ */
+.macro FILE_NOVALIDATE
+	.pushsection __stackvalidate_whitelist_file, "ae"
+	.long 0
+	.popsection
+.endm
+
+#else /* !FRAME_POINTER */
+
+#define FUNC_ENTER(name) FUNC_ENTER_NO_FP name
+#define FUNC_RETURN(name) FUNC_RETURN_NO_FP name
+#define RET_NOVALIDATE
+#define FILE_NOVALIDATE
+
+#endif /* FRAME_POINTER */
+
+#endif /* _ASM_X86_FUNC_H */
-- 
2.1.0

Re: [PATCH v2 2/2] x86, stackvalidate: Add asm frame pointer setup macros

[H. Peter Anvin]

On 05/04/2015 01:23 PM, Josh Poimboeuf wrote:
> +	__ASM_SIZE(push, _cfi) %_ASM_BP
> +	__ASM_SIZE(pop, _cfi) %_ASM_BP

This seems ridiculous.  push/pop only come in one size per
architecture(*).  Can we make it so that just push_cfi and pop_cfi do
the right things?

	-hpa

(*) Intentionally ignoring 16 bit here...

Re: [PATCH v2 2/2] x86, stackvalidate: Add asm frame pointer setup macros

[Josh Poimboeuf]

On Mon, May 04, 2015 at 01:33:53PM -0700, H. Peter Anvin wrote:
> On 05/04/2015 01:23 PM, Josh Poimboeuf wrote:
> > +	__ASM_SIZE(push, _cfi) %_ASM_BP
> > +	__ASM_SIZE(pop, _cfi) %_ASM_BP
> 
> This seems ridiculous.  push/pop only come in one size per
> architecture(*).  Can we make it so that just push_cfi and pop_cfi do
> the right things?

Yeah, the separated pushq_cfi and pushl_cfi macros aren't really
necessary.  I'm guessing they were made separate in order to have a
consistent naming interface with movq_cfi and movl_cfi.

I'm not sure about which way is better.  But I can replace them with new
push_cfi and pop_cfi macros if you like.

-- 
Josh