[RFC PATCH 05/10] objtool, x86: add facility for asm code to provide CFI hints

[Josh Poimboeuf <jpoimboe@redhat.com>]

Some asm (and inline asm) code does special things to the stack which
objtool can't understand.  (Nor can GCC or GNU assembler, for that
matter.)  In such cases we need a facility for the code to provide
annotations, so the unwinder can unwind through it.

This provides such a facility, in the form of CFI hints.  They're
similar to the GNU assembler .cfi* directives, but they give more
information, and are needed in far fewer places, because objtool can
fill in the blanks by following branches and adjusting the stack pointer
for pushes and pops.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 arch/x86/include/asm/undwarf-types.h | 100 ++++++++++++++++++++
 arch/x86/include/asm/undwarf.h       |  97 +++++++++++++++++++
 tools/objtool/Makefile               |   3 +
 tools/objtool/check.c                | 176 ++++++++++++++++++++++++++++++++++-
 tools/objtool/check.h                |   4 +-
 5 files changed, 373 insertions(+), 7 deletions(-)
 create mode 100644 arch/x86/include/asm/undwarf-types.h
 create mode 100644 arch/x86/include/asm/undwarf.h

diff --git a/arch/x86/include/asm/undwarf-types.h b/arch/x86/include/asm/undwarf-types.h
new file mode 100644
index 0000000..b624188
--- /dev/null
+++ b/arch/x86/include/asm/undwarf-types.h
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2017 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/>.
+ */
+
+#ifndef _UNDWARF_TYPES_H
+#define _UNDWARF_TYPES_H
+
+/*
+ * The UNDWARF_REG_* registers are base registers which are used to find other
+ * registers on the stack.
+ *
+ * The CFA (call frame address) is the value of the stack pointer on the
+ * previous frame, i.e. the caller's SP before it called the callee.
+ *
+ * The CFA is usually based on SP, unless a frame pointer has been saved, in
+ * which case it's based on BP.
+ *
+ * BP is usually either based on CFA or is undefined (meaning its value didn't
+ * change for the current frame).
+ *
+ * So the CFA base is usually either SP or BP, and the FP base is usually either
+ * CFA or undefined.  The rest of the base registers are needed for special
+ * cases like entry code and gcc aligned stacks.
+ */
+#define UNDWARF_REG_UNDEFINED		0
+#define UNDWARF_REG_CFA			1
+#define UNDWARF_REG_DX			2
+#define UNDWARF_REG_DI			3
+#define UNDWARF_REG_BP			4
+#define UNDWARF_REG_SP			5
+#define UNDWARF_REG_R10			6
+#define UNDWARF_REG_R13			7
+#define UNDWARF_REG_BP_INDIRECT		8
+#define UNDWARF_REG_SP_INDIRECT		9
+#define UNDWARF_REG_MAX			15
+
+/*
+ * UNDWARF_TYPE_CFA: Indicates that cfa_reg+cfa_offset points to the caller's
+ * stack pointer (aka the CFA in DWARF terms).  Used for all callable
+ * functions, i.e.  all C code and all callable asm functions.
+ *
+ * UNDWARF_TYPE_REGS: Used in entry code to indicate that cfa_reg+cfa_offset
+ * points to a fully populated pt_regs from a syscall, interrupt, or exception.
+ *
+ * UNDWARF_TYPE_REGS_IRET: Used in entry code to indicate that
+ * cfa_reg+cfa_offset points to the iret return frame.
+ *
+ * The CFI_HINT macros are only used for the undwarf_cfi_hints struct.  They
+ * are not used for the undwarf struct due to size and complexity constraints.
+ */
+#define UNDWARF_TYPE_CFA		0
+#define UNDWARF_TYPE_REGS		1
+#define UNDWARF_TYPE_REGS_IRET		2
+#define CFI_HINT_TYPE_SAVE		3
+#define CFI_HINT_TYPE_RESTORE		4
+
+#ifndef __ASSEMBLY__
+/*
+ * This struct contains a simplified version of the DWARF Call Frame
+ * Information standard.  It contains only the necessary parts of the real
+ * DWARF, simplified for ease of access by the in-kernel unwinder.  It tells
+ * the unwinder how to find the previous SP and BP (and sometimes entry regs)
+ * on the stack, given a code address (IP).
+ */
+struct undwarf {
+	int ip;
+	unsigned int len;
+	short cfa_offset;
+	short bp_offset;
+	unsigned cfa_reg:4;
+	unsigned bp_reg:4;
+	unsigned type:2;
+};
+
+/*
+ * This struct is used by asm and inline asm code to manually annotate the
+ * location of registers on the stack for the undwarf unwinder.
+ */
+struct undwarf_cfi_hint {
+	unsigned int ip;
+	short cfa_offset;
+	unsigned char cfa_reg;
+	unsigned char type;
+};
+#endif /* __ASSEMBLY__ */
+
+#endif /* _UNDWARF_TYPES_H */
diff --git a/arch/x86/include/asm/undwarf.h b/arch/x86/include/asm/undwarf.h
new file mode 100644
index 0000000..e763cf9
--- /dev/null
+++ b/arch/x86/include/asm/undwarf.h
@@ -0,0 +1,97 @@
+#ifndef _ASM_X86_UNDWARF_H
+#define _ASM_X86_UNDWARF_H
+
+#include "undwarf-types.h"
+
+#ifdef __ASSEMBLY__
+
+/*
+ * In asm, there are two kinds of code: normal C-type callable functions and
+ * the rest.  The normal callable functions can be called by other code, and
+ * don't do anything unusual with the stack.  Such normal callable functions
+ * are annotated with the ENTRY/ENDPROC macros.  Most asm code falls in this
+ * category.  In this case, no special debugging annotations are needed because
+ * objtool can automatically generate the .undwarf section which the undwarf
+ * unwinder reads at runtime.
+ *
+ * Anything which doesn't fall into the above category, such as syscall and
+ * interrupt handlers, tends to not be called directly by other functions, and
+ * often does unusual non-C-function-type things with the stack pointer.  Such
+ * code needs to be annotated such that objtool can understand it.  The
+ * following CFI hint macros are for this type of code.
+ *
+ * These macros provide hints to objtool about the state of the stack at each
+ * instruction.  Objtool starts from the hints and follows the code flow,
+ * making automatic CFI adjustments when it sees pushes and pops, adjusting the
+ * debuginfo as necessary.  It will also warn if it sees any inconsistencies.
+ */
+.macro CFI_HINT cfa_reg=UNDWARF_REG_SP cfa_offset=0 type=UNDWARF_TYPE_CFA
+#ifdef CONFIG_STACK_VALIDATION
+999:
+	.pushsection .discard.undwarf_cfi_hints
+		/* struct undwarf_cfi_hint */
+		.long 999b - .		/* ip		*/
+		.short \cfa_offset	/* cfa_offset	*/
+		.byte \cfa_reg		/* cfa_reg */
+		.byte \type		/* type */
+	.popsection
+#endif
+.endm
+
+.macro CFI_EMPTY
+	CFI_HINT cfa_reg=UNDWARF_REG_UNDEFINED
+.endm
+
+.macro CFI_REGS base=rsp offset=0 indirect=0 extra=1 iret=0
+	.if \base == rsp && \indirect
+		.set cfa_reg, UNDWARF_REG_SP_INDIRECT
+	.elseif \base == rsp
+		.set cfa_reg, UNDWARF_REG_SP
+	.elseif \base == rbp
+		.set cfa_reg, UNDWARF_REG_BP
+	.elseif \base == rdi
+		.set cfa_reg, UNDWARF_REG_DI
+	.elseif \base == rdx
+		.set cfa_reg, UNDWARF_REG_DX
+	.else
+		.error "CFI_REGS: bad base register"
+	.endif
+
+	.if \iret
+		.set type, UNDWARF_TYPE_REGS_IRET
+	.else
+		.set type, UNDWARF_TYPE_REGS
+	.endif
+
+	CFI_HINT cfa_reg=cfa_reg cfa_offset=\offset type=type
+.endm
+
+.macro CFI_IRET_REGS base=rsp offset=0
+	CFI_REGS base=\base offset=\offset iret=1
+.endm
+
+.macro CFI_FUNC cfa_offset=8
+	CFI_HINT cfa_offset=\cfa_offset
+.endm
+
+#else /* !__ASSEMBLY__ */
+
+#define CFI_HINT(cfa_reg, cfa_offset, type)			\
+	"999: \n\t"						\
+	".pushsection .discard.undwarf_cfi_hints\n\t"		\
+	/* struct undwarf_cfi_hint */				\
+	".long 999b - .\n\t"					\
+	".short " __stringify(cfa_offset) "\n\t"		\
+	".byte " __stringify(cfa_reg) "\n\t"			\
+	".byte " __stringify(type) "\n\t"			\
+	".popsection\n\t"
+
+#define CFI_SAVE CFI_HINT(0, 0, CFI_HINT_TYPE_SAVE)
+
+#define CFI_RESTORE CFI_HINT(0, 0, CFI_HINT_TYPE_RESTORE)
+
+
+#endif /* __ASSEMBLY__ */
+
+
+#endif /* _ASM_X86_UNDWARF_H */
diff --git a/tools/objtool/Makefile b/tools/objtool/Makefile
index 0e2765e..7997d5c 100644
--- a/tools/objtool/Makefile
+++ b/tools/objtool/Makefile
@@ -52,6 +52,9 @@ $(OBJTOOL): $(LIBSUBCMD) $(OBJTOOL_IN)
 	diff -I'^#include' arch/x86/insn/inat.h ../../arch/x86/include/asm/inat.h >/dev/null && \
 	diff -I'^#include' arch/x86/insn/inat_types.h ../../arch/x86/include/asm/inat_types.h >/dev/null) \
 	|| echo "warning: objtool: x86 instruction decoder differs from kernel" >&2 )) || true
+	@(test -d ../../kernel -a -d ../../tools -a -d ../objtool && (( \
+	diff ../../arch/x86/include/asm/undwarf-types.h undwarf-types.h >/dev/null) \
+	|| echo "warning: objtool: undwarf-types.h differs from kernel" >&2 )) || true
 	$(QUIET_LINK)$(CC) $(OBJTOOL_IN) $(LDFLAGS) -o $@
 
 
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index ca8f4fc..a409a4d 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -876,6 +876,99 @@ static int add_switch_table_alts(struct objtool_file *file)
 	return 0;
 }
 
+static int read_cfi_hints(struct objtool_file *file)
+{
+	struct section *sec, *relasec;
+	struct rela *rela;
+	struct undwarf_cfi_hint *hint;
+	struct instruction *insn;
+	struct cfi_reg *cfa;
+	int i;
+
+	sec = find_section_by_name(file->elf, ".discard.undwarf_cfi_hints");
+	if (!sec)
+		return 0;
+
+	relasec = sec->rela;
+	if (!relasec) {
+		WARN("missing .rela.discard.undwarf_cfi_hints section");
+		return -1;
+	}
+
+	if (sec->len % sizeof(struct undwarf_cfi_hint)) {
+		WARN("struct undwarf_cfi_hint size mismatch");
+		return -1;
+	}
+
+	file->hints = true;
+
+	for (i = 0; i < sec->len / sizeof(struct undwarf_cfi_hint); i++) {
+		hint = (struct undwarf_cfi_hint *)sec->data->d_buf + i;
+
+		rela = find_rela_by_dest(sec, i * sizeof(*hint));
+		if (!rela) {
+			WARN("can't find rela for undwarf_cfi_hints[%d]", i);
+			return -1;
+		}
+
+		insn = find_insn(file, rela->sym->sec, rela->addend);
+		if (!insn) {
+			WARN("can't find insn for undwarf_cfi_hints[%d]", i);
+			return -1;
+		}
+
+		cfa = &insn->state.cfa;
+
+		if (hint->type == CFI_HINT_TYPE_SAVE) {
+			insn->save = true;
+			continue;
+
+		} else if (hint->type == CFI_HINT_TYPE_RESTORE) {
+			insn->restore = true;
+			insn->hint = true;
+			continue;
+		}
+
+		insn->hint = true;
+
+		switch (hint->cfa_reg) {
+		case UNDWARF_REG_UNDEFINED:
+			cfa->base = CFI_UNDEFINED;
+			break;
+		case UNDWARF_REG_SP:
+			cfa->base = CFI_SP;
+			break;
+		case UNDWARF_REG_BP:
+			cfa->base = CFI_BP;
+			break;
+		case UNDWARF_REG_SP_INDIRECT:
+			cfa->base = CFI_SP_INDIRECT;
+			break;
+		case UNDWARF_REG_R10:
+			cfa->base = CFI_R10;
+			break;
+		case UNDWARF_REG_R13:
+			cfa->base = CFI_R13;
+			break;
+		case UNDWARF_REG_DI:
+			cfa->base = CFI_DI;
+			break;
+		case UNDWARF_REG_DX:
+			cfa->base = CFI_DX;
+			break;
+		default:
+			WARN_FUNC("unsupported undwarf_cfi_hint cfa base reg %d",
+				  insn->sec, insn->offset, hint->cfa_reg);
+			return -1;
+		}
+
+		cfa->offset = hint->cfa_offset;
+		insn->state.type = hint->type;
+	}
+
+	return 0;
+}
+
 static int decode_sections(struct objtool_file *file)
 {
 	int ret;
@@ -906,6 +999,10 @@ static int decode_sections(struct objtool_file *file)
 	if (ret)
 		return ret;
 
+	ret = read_cfi_hints(file);
+	if (ret)
+		return ret;
+
 	return 0;
 }
 
@@ -1313,7 +1410,7 @@ static int validate_branch(struct objtool_file *file, struct instruction *first,
 			   struct insn_state state)
 {
 	struct alternative *alt;
-	struct instruction *insn;
+	struct instruction *insn, *next_insn;
 	struct section *sec;
 	struct symbol *func = NULL;
 	int ret;
@@ -1328,6 +1425,8 @@ static int validate_branch(struct objtool_file *file, struct instruction *first,
 	}
 
 	while (1) {
+		next_insn = next_insn_same_sec(file, insn);
+
 		if (file->c_file && insn->func) {
 			if (func && func != insn->func) {
 				WARN("%s() falls through to next function %s()",
@@ -1339,13 +1438,54 @@ static int validate_branch(struct objtool_file *file, struct instruction *first,
 		func = insn->func;
 
 		if (insn->visited) {
-			if (!!insn_state_match(insn, &state))
+			if (!insn->hint && !insn_state_match(insn, &state))
 				return 1;
 
 			return 0;
 		}
 
-		insn->state = state;
+		if (insn->hint) {
+			if (insn->restore) {
+				struct instruction *save_insn, *i;
+
+				i = insn;
+				save_insn = NULL;
+				func_for_each_insn_continue_reverse(file, func, i) {
+					if (i->save) {
+						save_insn = i;
+						break;
+					}
+				}
+
+				if (!save_insn) {
+					WARN_FUNC("no corresponding CFI save for CFI restore",
+						  sec, insn->offset);
+					return 1;
+				}
+
+				if (!save_insn->visited) {
+					/*
+					 * Oops, no state to copy yet.
+					 * Hopefully we can reach this
+					 * instruction from another branch
+					 * after the save insn has been
+					 * visited.
+					 */
+					if (insn == first)
+						return 0;
+
+					WARN_FUNC("objtool isn't smart enough to handle this CFI save/restore combo",
+						  sec, insn->offset);
+					return 1;
+				}
+
+				insn->state = save_insn->state;
+			}
+
+			state = insn->state;
+
+		} else
+			insn->state = state;
 
 		insn->visited = true;
 
@@ -1420,7 +1560,7 @@ static int validate_branch(struct objtool_file *file, struct instruction *first,
 			return 0;
 
 		case INSN_CONTEXT_SWITCH:
-			if (func) {
+			if (func && (!next_insn || !next_insn->hint)) {
 				WARN_FUNC("unsupported instruction in callable function",
 					  sec, insn->offset);
 				return 1;
@@ -1440,7 +1580,7 @@ static int validate_branch(struct objtool_file *file, struct instruction *first,
 		if (insn->dead_end)
 			return 0;
 
-		insn = next_insn_same_sec(file, insn);
+		insn = next_insn;
 		if (!insn) {
 			WARN("%s: unexpected end of section", sec->name);
 			return 1;
@@ -1450,6 +1590,27 @@ static int validate_branch(struct objtool_file *file, struct instruction *first,
 	return 0;
 }
 
+static int validate_cfi_hints(struct objtool_file *file)
+{
+	struct instruction *insn;
+	int ret, warnings = 0;
+	struct insn_state state;
+
+	if (!file->hints)
+		return 0;
+
+	clear_insn_state(&state);
+
+	for_each_insn(file, insn) {
+		if (insn->hint && !insn->visited) {
+			ret = validate_branch(file, insn, state);
+			warnings += ret;
+		}
+	}
+
+	return warnings;
+}
+
 static bool is_kasan_insn(struct instruction *insn)
 {
 	return (insn->type == INSN_CALL &&
@@ -1615,6 +1776,11 @@ int check(const char *_objname, bool _nofp, bool undwarf)
 		goto out;
 	warnings += ret;
 
+	ret = validate_cfi_hints(&file);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
 	if (!warnings) {
 		ret = validate_reachable_instructions(&file);
 		if (ret < 0)
diff --git a/tools/objtool/check.h b/tools/objtool/check.h
index e56bb1c..d711336 100644
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -43,7 +43,7 @@ struct instruction {
 	unsigned int len;
 	unsigned char type;
 	unsigned long immediate;
-	bool alt_group, visited, dead_end, ignore, needs_cfi;
+	bool alt_group, visited, dead_end, ignore, needs_cfi, hint, save, restore;
 	struct symbol *call_dest;
 	struct instruction *jump_dest;
 	struct list_head alts;
@@ -58,7 +58,7 @@ struct objtool_file {
 	struct list_head insn_list;
 	DECLARE_HASHTABLE(insn_hash, 16);
 	struct section *rodata, *whitelist;
-	bool ignore_unreachables, c_file;
+	bool ignore_unreachables, c_file, hints;
 };
 
 int check(const char *objname, bool nofp, bool undwarf);
-- 
2.7.4