[ This is a repost of a previous RFC, rebased onto linux-next. ]
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] https://lkml.org/lkml/2015/2/9/475
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 | 341 ++++++++++++++++++++++++++++++++++
scripts/stackvalidate/elf.h | 56 ++++++
scripts/stackvalidate/list.h | 217 ++++++++++++++++++++++
scripts/stackvalidate/stackvalidate.c | 226 ++++++++++++++++++++++
15 files changed, 1131 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
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 <[email protected]>
---
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 | 341 ++++++++++++++++++++++++++++++++++
scripts/stackvalidate/elf.h | 56 ++++++
scripts/stackvalidate/list.h | 217 ++++++++++++++++++++++
scripts/stackvalidate/stackvalidate.c | 226 ++++++++++++++++++++++
14 files changed, 1049 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 68e96ee..1af2d64 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -9359,6 +9359,12 @@ L: [email protected]
S: Supported
F: Documentation/stable_kernel_rules.txt
+STACK VALIDATION
+M: Josh Poimboeuf <[email protected]>
+S: Supported
+F: scripts/stackvalidate/
+F: arch/x86/include/asm/func.h
+
STAGING SUBSYSTEM
M: Greg Kroah-Hartman <[email protected]>
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 40ada6e..a876c17 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -143,6 +143,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 f3d0e3e..dbc256a 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..7879a0f
--- /dev/null
+++ b/scripts/stackvalidate/elf.c
@@ -0,0 +1,341 @@
+/*
+ * elf.c - ELF access library
+ *
+ * Adapted from kpatch (https://github.com/dynup/kpatch):
+ * Copyright (C) 2013-2015 Josh Poimboeuf <[email protected]>
+ * Copyright (C) 2014 Seth Jennings <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, 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, §ions_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);
+
+ 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;
+
+ list_add_tail(&sec->list, &elf->sections);
+ }
+
+ /* 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");
+ return -1;
+ }
+
+ sym->name = elf_strptr(elf->elf, symtab->sh.sh_link,
+ sym->sym.st_name);
+ if (!sym->name) {
+ perror("elf_strptr");
+ return -1;
+ }
+
+ 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);
+ return -1;
+ }
+ 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;
+}
+
+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));
+
+ 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;
+ }
+
+ list_add_tail(&rela->list, &sec->relas);
+ }
+ }
+
+ 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));
+
+ elf->name = strdup(name);
+
+ elf->fd = open(name, O_RDONLY);
+ if (elf->fd == -1) {
+ perror("open");
+ return NULL;
+ }
+
+ elf->elf = elf_begin(elf->fd, ELF_C_READ_MMAP, NULL);
+ if (!elf->elf) {
+ perror("elf_begin");
+ return NULL;
+ }
+
+ if (!gelf_getehdr(elf->elf, &elf->ehdr)) {
+ perror("gelf_getehdr");
+ return NULL;
+ }
+
+ INIT_LIST_HEAD(&elf->sections);
+
+ 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);
+ }
+ free(elf->name);
+ close(elf->fd);
+ 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 <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, 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
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 <[email protected]>
---
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
On Mon, Apr 27, 2015 at 08:56:27AM -0500, Josh Poimboeuf wrote:
> 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.
Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to
also process the output of GCC with this tool? To both double check GCC
and to give the tool more input?
On Tue, Apr 28, 2015 at 02:16:06PM +0200, Peter Zijlstra wrote:
> On Mon, Apr 27, 2015 at 08:56:27AM -0500, Josh Poimboeuf wrote:
> > 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.
>
> Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to
> also process the output of GCC with this tool? To both double check GCC
> and to give the tool more input?
I tried that, but I discovered that gcc's usage of frame pointers would
be a lot harder to validate. It only sets up the frame pointer in code
paths which have call instructions. There are a lot of functions which
have conditional jumps at the beginning which can jump straight to a
return instruction without first doing the frame pointer setup.
So it would really need to have a much more sophisticated static code
analysis. But I think the possibility of gcc messing up frame pointers
is very slim. I doubt it would be worth the complexity (and added
compile time) needed to try to find any gcc bugs there.
--
Josh
On Tue, Apr 28, 2015 at 09:04:54AM -0500, Josh Poimboeuf wrote:
> On Tue, Apr 28, 2015 at 02:16:06PM +0200, Peter Zijlstra wrote:
> > On Mon, Apr 27, 2015 at 08:56:27AM -0500, Josh Poimboeuf wrote:
> > > 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.
> >
> > Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to
> > also process the output of GCC with this tool? To both double check GCC
> > and to give the tool more input?
>
> I tried that, but I discovered that gcc's usage of frame pointers would
> be a lot harder to validate. It only sets up the frame pointer in code
> paths which have call instructions. There are a lot of functions which
> have conditional jumps at the beginning which can jump straight to a
> return instruction without first doing the frame pointer setup.
Hmm, would not such code break your patching?
On Tue, Apr 28, 2015 at 04:08:42PM +0200, Peter Zijlstra wrote:
> On Tue, Apr 28, 2015 at 09:04:54AM -0500, Josh Poimboeuf wrote:
> > On Tue, Apr 28, 2015 at 02:16:06PM +0200, Peter Zijlstra wrote:
> > > On Mon, Apr 27, 2015 at 08:56:27AM -0500, Josh Poimboeuf wrote:
> > > > 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.
> > >
> > > Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to
> > > also process the output of GCC with this tool? To both double check GCC
> > > and to give the tool more input?
> >
> > I tried that, but I discovered that gcc's usage of frame pointers would
> > be a lot harder to validate. It only sets up the frame pointer in code
> > paths which have call instructions. There are a lot of functions which
> > have conditional jumps at the beginning which can jump straight to a
> > return instruction without first doing the frame pointer setup.
>
> Hmm, would not such code break your patching?
No, because we'll also do some runtime stack validation (which will be a
future patch set). If we detect preemption or an irq frame on the
stack, we'll assume the stack is unreliable and delay the patching of
the task (*). Otherwise the stack will only consist of calls down to
schedule() which will be guaranteed to have frame pointers.
(*) This can be even further improved by making _all_ stacks reliable if
we can ensure that dwarf call frame information is reliable (more
future patch sets).
--
Josh
On Tue, Apr 28, 2015 at 09:21:05AM -0500, Josh Poimboeuf wrote:
> > > I tried that, but I discovered that gcc's usage of frame pointers would
> > > be a lot harder to validate. It only sets up the frame pointer in code
> > > paths which have call instructions. There are a lot of functions which
> > > have conditional jumps at the beginning which can jump straight to a
> > > return instruction without first doing the frame pointer setup.
> >
> > Hmm, would not such code break your patching?
>
> No, because we'll also do some runtime stack validation (which will be a
> future patch set). If we detect preemption or an irq frame on the
> stack, we'll assume the stack is unreliable and delay the patching of
> the task (*).
Ah, which fixes your second issue too (the interrupt before frame
setup). OK.
On Mon 2015-04-27 08:56:27, Josh Poimboeuf wrote:
> 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 <[email protected]>
I made a quick look and have few questions.
[...]
> 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
> +/*
> + * 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;
I am a bit courious. You check 0x89 and 0x5e but I see the following
in the disasembly:
48 89 e5 mov %rsp,%rbp
I wonder if 48 is just a prefix that is filtered by insn_get_opcode or
what.
Sigh, I still need to learn a lot about assembly.
> + 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);
This looks quite weak condition to me. It accepts the instructions in
any order and at any place.
Also livepatching will rely on having fentry before the prologue. Do
you plan to add support for this ordering?
> + 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.
> + *
[...]
> 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..7879a0f
> --- /dev/null
> +++ b/scripts/stackvalidate/elf.c
[...]
> +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, §ions_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);
> +
> + s = elf_getscn(elf->elf, i);
> + if (!s) {
> + perror("elf_getscn");
> + return -1;
This is leaking "sec". It is not added to the list, so you could not
free it later. The same problem is on many other locations.
> + }
> +
> + 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;
> +
> + list_add_tail(&sec->list, &elf->sections);
> + }
> +
> + /* 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;
> +}
I basically ended here. I was rather curious how such a thing could
get implemented than doing a proper review.
Best Regards,
Petr
On Tue, Apr 28, 2015 at 06:44:15PM +0200, Petr Mladek wrote:
> On Mon 2015-04-27 08:56:27, Josh Poimboeuf wrote:
> > + case 0x89:
> > + insn_get_modrm(&insn);
> > + if (insn.modrm.bytes[0] == 0xe5)
> > + /* mov sp, bp */
> > + mov++;
> > + break;
>
> I am a bit courious. You check 0x89 and 0x5e but I see the following
> in the disasembly:
>
> 48 89 e5 mov %rsp,%rbp
>
> I wonder if 48 is just a prefix that is filtered by insn_get_opcode or
> what.
>
> Sigh, I still need to learn a lot about assembly.
Yeah, 0x48 is a prefix which means the operands are 64-bit. Here is a
useful, albeit very dense, x86 assembly reference:
http://ref.x86asm.net/coder64.html
> > + 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);
>
> This looks quite weak condition to me. It accepts the instructions in
> any order and at any place.
It's really designed to determine whether the frame pointer is being
updated, with some basic sanity checks. It doesn't guarantee that it's
being done _correctly_. Which is ok I think, since all assembly code is
hand-coded by people who (hopefully) are being careful and know exactly
what they're doing.
And as it turns out, today, >99% of callable asm functions don't have
any frame pointer logic and will fail this check.
> Also livepatching will rely on having fentry before the prologue. Do
> you plan to add support for this ordering?
No, because this is only intended to analyze hand-crafted asm code,
which generally doesn't have the fentry call (and so live patching can't
patch it).
However, if we wanted to enable the patching of asm functions in the
future, we could consider adding the fentry call to the FUNC_ENTER macro
later on.
> > + 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);
> > +
> > + s = elf_getscn(elf->elf, i);
> > + if (!s) {
> > + perror("elf_getscn");
> > + return -1;
>
> This is leaking "sec". It is not added to the list, so you could not
> free it later. The same problem is on many other locations.
Ah, right. It really doesn't matter much since this is a short running
userspace program, but I'll fix it up.
> > + /* 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;
> > +}
>
> I basically ended here. I was rather curious how such a thing could
> get implemented than doing a proper review.
Thanks a lot for looking!
--
Josh