[RFC PATCH 04/10] objtool: add undwarf debuginfo generation

[Josh Poimboeuf]

Now that objtool knows the states of all registers on the stack for each
instruction, it's straightforward to generate debuginfo for an unwinder
to use.

Instead of generating DWARF, generate a new format called undwarf, which
is more suitable for an in-kernel unwinder.  See
tools/objtool/Documentation/undwarf.txt for a more detailed description
of this new debuginfo format and why it's preferable to DWARF.

Signed-off-by: Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
---
 tools/objtool/Build                              |   2 +
 tools/objtool/Documentation/stack-validation.txt |  45 +---
 tools/objtool/Documentation/undwarf.txt          |  99 ++++++++
 tools/objtool/builtin-check.c                    |   2 +-
 tools/objtool/builtin-undwarf.c                  |  70 ++++++
 tools/objtool/builtin.h                          |   1 +
 tools/objtool/check.c                            |  57 ++++-
 tools/objtool/check.h                            |   7 +-
 tools/objtool/elf.c                              | 224 +++++++++++++++++
 tools/objtool/elf.h                              |   5 +
 tools/objtool/objtool.c                          |   3 +-
 tools/objtool/undwarf-types.h                    | 100 ++++++++
 tools/objtool/undwarf.c                          | 308 +++++++++++++++++++++++
 tools/objtool/{builtin.h => undwarf.h}           |  19 +-
 14 files changed, 898 insertions(+), 44 deletions(-)
 create mode 100644 tools/objtool/Documentation/undwarf.txt
 create mode 100644 tools/objtool/builtin-undwarf.c
 create mode 100644 tools/objtool/undwarf-types.h
 create mode 100644 tools/objtool/undwarf.c
 copy tools/objtool/{builtin.h => undwarf.h} (64%)

diff --git a/tools/objtool/Build b/tools/objtool/Build
index 6f2e198..845c879 100644
--- a/tools/objtool/Build
+++ b/tools/objtool/Build
@@ -1,6 +1,8 @@
 objtool-y += arch/$(SRCARCH)/
 objtool-y += builtin-check.o
+objtool-y += builtin-undwarf.o
 objtool-y += check.o
+objtool-y += undwarf.o
 objtool-y += elf.o
 objtool-y += special.o
 objtool-y += objtool.o
diff --git a/tools/objtool/Documentation/stack-validation.txt b/tools/objtool/Documentation/stack-validation.txt
index 17c1195..e961971 100644
--- a/tools/objtool/Documentation/stack-validation.txt
+++ b/tools/objtool/Documentation/stack-validation.txt
@@ -11,9 +11,6 @@ analyzes every .o file and ensures the validity of its stack metadata.
 It enforces a set of rules on asm code and C inline assembly code so
 that stack traces can be reliable.
 
-Currently it only checks frame pointer usage, but there are plans to add
-CFI validation for C files and CFI generation for asm files.
-
 For each function, it recursively follows all possible code paths and
 validates the correct frame pointer state at each instruction.
 
@@ -23,6 +20,9 @@ alternative execution paths to a given instruction (or set of
 instructions).  Similarly, it knows how to follow switch statements, for
 which gcc sometimes uses jump tables.
 
+(Objtool also has an 'undwarf generate' subcommand which generates
+debuginfo for the undwarf unwinder.  See undwarf.txt for more details.)
+
 
 Why do we need stack metadata validation?
 -----------------------------------------
@@ -93,37 +93,14 @@ a) More reliable stack traces for frame pointer enabled kernels
        or at the very end of the function after the stack frame has been
        destroyed.  This is an inherent limitation of frame pointers.
 
-b) 100% reliable stack traces for DWARF enabled kernels
-
-   (NOTE: This is not yet implemented)
-
-   As an alternative to frame pointers, DWARF Call Frame Information
-   (CFI) metadata can be used to walk the stack.  Unlike frame pointers,
-   CFI metadata is out of band.  So it doesn't affect runtime
-   performance and it can be reliable even when interrupts or exceptions
-   are involved.
-
-   For C code, gcc automatically generates DWARF CFI metadata.  But for
-   asm code, generating CFI is a tedious manual approach which requires
-   manually placed .cfi assembler macros to be scattered throughout the
-   code.  It's clumsy and very easy to get wrong, and it makes the real
-   code harder to read.
-
-   Stacktool will improve this situation in several ways.  For code
-   which already has CFI annotations, it will validate them.  For code
-   which doesn't have CFI annotations, it will generate them.  So an
-   architecture can opt to strip out all the manual .cfi annotations
-   from their asm code and have objtool generate them instead.
-
-   We might also add a runtime stack validation debug option where we
-   periodically walk the stack from schedule() and/or an NMI to ensure
-   that the stack metadata is sane and that we reach the bottom of the
-   stack.
-
-   So the benefit of objtool here will be that external tooling should
-   always show perfect stack traces.  And the same will be true for
-   kernel warning/oops traces if the architecture has a runtime DWARF
-   unwinder.
+b) Out-of-band debuginfo generation (undwarf)
+
+   As an alternative to frame pointers, undwarf metadata can be used to
+   walk the stack.  Unlike frame pointers, undwarf is out of band.  So
+   it doesn't affect runtime performance and it can be reliable even
+   when interrupts or exceptions are involved.
+
+   For more details, see undwarf.txt.
 
 c) Higher live patching compatibility rate
 
diff --git a/tools/objtool/Documentation/undwarf.txt b/tools/objtool/Documentation/undwarf.txt
new file mode 100644
index 0000000..3c7a6d6
--- /dev/null
+++ b/tools/objtool/Documentation/undwarf.txt
@@ -0,0 +1,99 @@
+Undwarf debuginfo generation
+============================
+
+Overview
+--------
+
+The kernel CONFIG_UNDWARF_UNWINDER option enables objtool generation of
+undwarf debuginfo, which is out-of-band data which is used by the
+in-kernel undwarf unwinder.  It's similar in concept to DWARF CFI
+debuginfo which would be used by a DWARF unwinder.  The difference is
+that the format of the undwarf data is simpler than DWARF, which in turn
+allows the unwinder to be simpler.
+
+Objtool generates the undwarf data by piggybacking on the compile-time
+stack metadata validation work described in stack-validation.txt.  After
+analyzing all the code paths of a .o file, it creates an array of
+'struct undwarf's and writes them to the .undwarf section.
+
+Then at vmlinux link time, the .undwarf section is sorted by the
+sorttable script.  The resulting sorted array of undwarf structs is used
+by the unwinder at runtime to correlate a given text address with its
+stack state.
+
+
+Why not just use DWARF?
+-----------------------
+
+Undwarf has some of the same benefits as DWARF.  Unlike frame pointers,
+the debuginfo is out-of-band. so it has no effect on runtime
+performance.  Another benefit is that it's possible to reliably unwind
+across interrupts and exceptions.
+
+Undwarf debuginfo's advantage over DWARF itself is that it's much
+simpler.  It gets rid of the DWARF CFI state machine and also gets rid
+of the tracking of unnecessary registers.  This allows the unwinder to
+be much simpler, meaning fewer bugs, which is especially important for
+mission critical oops code.
+
+The simpler debuginfo format also enables the unwinder to be relatively
+fast, which is important for perf and lockdep.
+
+The undwarf format does have a few downsides.  The undwarf table takes
+up extra memory -- something in the ballpark of 3-5MB, depending on the
+kernel config.  In the future we may try to rearrange the data to
+compress that a bit.
+
+Another downside is that, as GCC evolves, it's conceivable that the
+undwarf data may end up being *too* simple to describe the state of the
+stack for certain optimizations.  Will we end up having to track the
+state of more registers and eventually end up reinventing DWARF?
+
+I think this is unlikely because GCC seems to save the frame pointer for
+any unusual stack adjustments it does, so I suspect we'll really only
+ever need to keep track of the stack pointer and the frame pointer
+between call frames.  But even if we do end up having to track all the
+registers DWARF tracks, at least we will still control the format, e.g.
+no complex state machines.
+
+
+Why generate undwarf with objtool?
+----------------------------------
+
+It should be possible to generate the undwarf data with a simple tool
+which converts DWARF to undwarf.  However, such a solution would be
+incomplete due to the kernel's extensive use of asm, inline asm, and
+special sections like exception tables.
+
+That could be rectified by manually annotating those special code paths
+using GNU assembler .cfi annotations in .S files, and homegrown
+annotations for inline asm in .c files.  But asm annotations were tried
+in the past and were found to be unmaintainable.  They were often
+incorrect/incomplete and made the code harder to read and keep updated.
+And based on looking at glibc code, annotating inline asm in .c files
+might be even worse.
+
+With compile-time stack metadata validation, objtool already follows all
+the code paths and already has all the information it needs to be able
+to generate undwarf data from scratch.  So it's an easy step to go from
+stack validation to undwarf generation.
+
+Objtool still needs a few annotations, but only in code which does
+unusual things to the stack like entry code.  And even then, far fewer
+annotations are needed than what DWARF would need, so it's much more
+maintainable than DWARF CFI annotations.
+
+So the advantages of using objtool to generate undwarf are that it gives
+more accurate debuginfo, with close to zero annotations.  It also
+insulates the kernel from toolchain bugs which can be very painful to
+deal with in the kernel since it often has to workaround issues in older
+versions of the toolchain for years.
+
+The downside is that the unwinder now becomes dependent on objtool's
+ability to reverse engineer GCC code flows.  If GCC optimizations become
+too complicated for objtool to follow, the undwarf generation might stop
+working or become incomplete.  In such a case we may need to revisit the
+current implementation.  Some possible solutions would be asking GCC to
+make the optimizations more palatable, or having objtool use DWARF as an
+additional input.  (It's worth noting that live patching already has
+such a dependency on objtool.)
diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 365c34e..eedf089 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -52,5 +52,5 @@ int cmd_check(int argc, const char **argv)
 
 	objname = argv[0];
 
-	return check(objname, nofp);
+	return check(objname, nofp, false);
 }
diff --git a/tools/objtool/builtin-undwarf.c b/tools/objtool/builtin-undwarf.c
new file mode 100644
index 0000000..900b1e5
--- /dev/null
+++ b/tools/objtool/builtin-undwarf.c
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * objtool undwarf:
+ *
+ * This command analyzes a .o file and adds an .undwarf section to it, which is
+ * used by the in-kernel "undwarf" unwinder.
+ *
+ * This command is a superset of "objtool check".
+ */
+
+#include <string.h>
+#include <subcmd/parse-options.h>
+#include "builtin.h"
+#include "check.h"
+
+
+static const char *undwarf_usage[] = {
+	"objtool undwarf generate [<options>] file.o",
+	"objtool undwarf dump file.o",
+	NULL,
+};
+
+extern const struct option check_options[];
+extern bool nofp;
+
+int cmd_undwarf(int argc, const char **argv)
+{
+	const char *objname;
+
+	argc--; argv++;
+	if (!strncmp(argv[0], "gen", 3)) {
+		argc = parse_options(argc, argv, check_options, undwarf_usage, 0);
+		if (argc != 1)
+			usage_with_options(undwarf_usage, check_options);
+
+		objname = argv[0];
+
+		return check(objname, nofp, true);
+
+	}
+
+	if (!strcmp(argv[0], "dump")) {
+		if (argc != 2)
+			usage_with_options(undwarf_usage, check_options);
+
+		objname = argv[1];
+
+		return undwarf_dump(objname);
+	}
+
+	usage_with_options(undwarf_usage, check_options);
+
+	return 0;
+}
diff --git a/tools/objtool/builtin.h b/tools/objtool/builtin.h
index 34d2ba7..0b9722f 100644
--- a/tools/objtool/builtin.h
+++ b/tools/objtool/builtin.h
@@ -18,5 +18,6 @@
 #define _BUILTIN_H
 
 extern int cmd_check(int argc, const char **argv);
+extern int cmd_undwarf(int argc, const char **argv);
 
 #endif /* _BUILTIN_H */
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index e924fd5..ca8f4fc 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -246,12 +246,20 @@ static int decode_instructions(struct objtool_file *file)
 	unsigned long offset;
 	struct instruction *insn;
 	int ret;
+	bool needs_cfi;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
 
 		if (!(sec->sh.sh_flags & SHF_EXECINSTR))
 			continue;
 
+		if (!strcmp(sec->name, ".altinstr_replacement") ||
+		    !strcmp(sec->name, ".altinstr_aux") ||
+		    !strncmp(sec->name, ".discard.", 9))
+			needs_cfi = false;
+		else
+			needs_cfi = true;
+
 		for (offset = 0; offset < sec->len; offset += insn->len) {
 			insn = malloc(sizeof(*insn));
 			if (!insn) {
@@ -264,6 +272,7 @@ static int decode_instructions(struct objtool_file *file)
 
 			insn->sec = sec;
 			insn->offset = offset;
+			insn->needs_cfi = needs_cfi;
 
 			ret = arch_decode_instruction(file->elf, sec, offset,
 						      sec->len - offset,
@@ -940,6 +949,30 @@ static bool has_valid_stack_frame(struct insn_state *state)
 	return false;
 }
 
+static int update_insn_state_regs(struct instruction *insn, struct insn_state *state)
+{
+	struct cfi_reg *cfa = &state->cfa;
+	struct stack_op *op = &insn->stack_op;
+
+	if (cfa->base != CFI_SP)
+		return 0;
+
+	/* push */
+	if (op->dest.type == OP_DEST_PUSH)
+		cfa->offset += 8;
+
+	/* pop */
+	if (op->src.type == OP_SRC_POP)
+		cfa->offset -= 8;
+
+	/* add immediate to sp */
+	if (op->dest.type == OP_DEST_REG && op->src.type == OP_SRC_ADD &&
+	    op->dest.reg == CFI_SP && op->src.reg == CFI_SP)
+		cfa->offset -= op->src.offset;
+
+	return 0;
+}
+
 static void save_reg(struct insn_state *state, unsigned char reg, int base,
 		     int offset)
 {
@@ -1001,6 +1034,10 @@ static int update_insn_state(struct instruction *insn, struct insn_state *state)
 		return 0;
 	}
 
+	if (state->type == UNDWARF_TYPE_REGS ||
+	    state->type == UNDWARF_TYPE_REGS_IRET)
+		return update_insn_state_regs(insn, state);
+
 	switch (op->dest.type) {
 
 	case OP_DEST_REG:
@@ -1249,6 +1286,10 @@ static bool insn_state_match(struct instruction *insn, struct insn_state *state)
 			break;
 		}
 
+	} else if (state1->type != state2->type) {
+		WARN_FUNC("stack state mismatch: type1=%d type2=%d",
+			  insn->sec, insn->offset, state1->type, state2->type);
+
 	} else if (state1->drap != state2->drap ||
 		 (state1->drap && state1->drap_reg != state2->drap_reg)) {
 		WARN_FUNC("stack state mismatch: drap1=%d(%d) drap2=%d(%d)",
@@ -1538,7 +1579,7 @@ static void cleanup(struct objtool_file *file)
 	elf_close(file->elf);
 }
 
-int check(const char *_objname, bool _nofp)
+int check(const char *_objname, bool _nofp, bool undwarf)
 {
 	struct objtool_file file;
 	int ret, warnings = 0;
@@ -1581,6 +1622,20 @@ int check(const char *_objname, bool _nofp)
 		warnings += ret;
 	}
 
+	if (undwarf) {
+		ret = create_undwarf(&file);
+		if (ret < 0)
+			goto out;
+
+		ret = create_undwarf_section(&file);
+		if (ret < 0)
+			goto out;
+
+		ret = update_file(&file);
+		if (ret < 0)
+			goto out;
+	}
+
 out:
 	cleanup(&file);
 
diff --git a/tools/objtool/check.h b/tools/objtool/check.h
index da85f5b..e56bb1c 100644
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -22,12 +22,14 @@
 #include "elf.h"
 #include "cfi.h"
 #include "arch.h"
+#include "undwarf.h"
 #include <linux/hashtable.h>
 
 struct insn_state {
 	struct cfi_reg cfa;
 	struct cfi_reg regs[CFI_NUM_REGS];
 	int stack_size;
+	unsigned char type;
 	bool bp_scratch;
 	bool drap;
 	int drap_reg;
@@ -41,13 +43,14 @@ struct instruction {
 	unsigned int len;
 	unsigned char type;
 	unsigned long immediate;
-	bool alt_group, visited, dead_end, ignore;
+	bool alt_group, visited, dead_end, ignore, needs_cfi;
 	struct symbol *call_dest;
 	struct instruction *jump_dest;
 	struct list_head alts;
 	struct symbol *func;
 	struct stack_op stack_op;
 	struct insn_state state;
+	struct undwarf undwarf;
 };
 
 struct objtool_file {
@@ -58,7 +61,7 @@ struct objtool_file {
 	bool ignore_unreachables, c_file;
 };
 
-int check(const char *objname, bool nofp);
+int check(const char *objname, bool nofp, bool undwarf);
 
 #define for_each_insn(file, insn)					\
 	list_for_each_entry(insn, &file->insn_list, list)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 3fb0747..1ca5d9a 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -394,6 +394,230 @@ struct elf *elf_open(const char *name)
 	return NULL;
 }
 
+struct section *elf_create_section(struct elf *elf, const char *name,
+				   size_t entsize, int nr)
+{
+	struct section *sec, *shstrtab;
+	size_t size = entsize * nr;
+	char *buf;
+
+	sec = malloc(sizeof(*sec));
+	if (!sec) {
+		perror("malloc");
+		return NULL;
+	}
+	memset(sec, 0, sizeof(*sec));
+
+	INIT_LIST_HEAD(&sec->symbol_list);
+	INIT_LIST_HEAD(&sec->rela_list);
+	hash_init(sec->rela_hash);
+	hash_init(sec->symbol_hash);
+
+	list_add_tail(&sec->list, &elf->sections);
+
+	sec->name = strdup(name);
+	if (!sec->name) {
+		perror("strdup");
+		return NULL;
+	}
+
+	sec->idx = list_prev_entry(sec, list)->idx + 1;
+	sec->len = size;
+
+	sec->sh.sh_entsize = entsize;
+	sec->sh.sh_size = size;
+
+	sec->data = malloc(sizeof(*sec->data));
+	if (!sec->data) {
+		perror("malloc");
+		return NULL;
+	}
+
+	sec->data->d_buf = NULL;
+	if (size) {
+		sec->data->d_buf = malloc(size);
+		if (!sec->data->d_buf) {
+			perror("malloc");
+			return NULL;
+		}
+	}
+
+	sec->data->d_size = size;
+	sec->data->d_type = ELF_T_BYTE;
+
+	shstrtab = find_section_by_name(elf, ".shstrtab");
+	if (!shstrtab) {
+		WARN("can't find .shstrtab section");
+		return NULL;
+	}
+	size = shstrtab->len + strlen(name) + 1;
+	buf = malloc(size);
+	memcpy(buf, shstrtab->data->d_buf, shstrtab->len);
+	strcpy(buf + shstrtab->len, name);
+	sec->sh.sh_name = shstrtab->len;
+	shstrtab->data->d_buf = buf;
+	shstrtab->data->d_size = shstrtab->len = size;
+
+	return sec;
+}
+
+struct section *elf_create_rela_section(struct elf *elf, struct section *base)
+{
+	char *relaname;
+	struct section *sec;
+
+	relaname = malloc(strlen(base->name) + strlen(".rela") + 1);
+	if (!relaname) {
+		perror("malloc");
+		return NULL;
+	}
+	strcpy(relaname, ".rela");
+	strcat(relaname, base->name);
+
+	sec = elf_create_section(elf, relaname, sizeof(GElf_Rela), 0);
+	if (!sec)
+		return NULL;
+
+	base->rela = sec;
+	sec->base = base;
+
+	sec->sh.sh_type = SHT_RELA;
+	sec->sh.sh_addralign = 8;
+	sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
+	sec->sh.sh_info = base->idx;
+	sec->sh.sh_flags = SHF_INFO_LINK;
+
+	return sec;
+}
+
+int elf_rebuild_rela_section(struct section *sec)
+{
+	struct rela *rela;
+	int nr, index = 0, size;
+	GElf_Rela *relas;
+
+	nr = 0;
+	list_for_each_entry(rela, &sec->rela_list, list)
+		nr++;
+
+	size = nr * sizeof(*relas);
+	relas = malloc(size);
+	if (!relas) {
+		perror("malloc");
+		return -1;
+	}
+
+	sec->data->d_buf = relas;
+	sec->data->d_size = size;
+
+	sec->sh.sh_size = size;
+
+	index = 0;
+	list_for_each_entry(rela, &sec->rela_list, list) {
+		relas[index].r_offset = rela->offset;
+		relas[index].r_addend = rela->addend;
+		relas[index].r_info = GELF_R_INFO(rela->sym->idx, rela->type);
+		index++;
+	}
+
+	return 0;
+}
+
+int elf_write_to_file(struct elf *elf, char *outfile)
+{
+	int fd;
+	struct section *sec;
+	Elf *elfout;
+	GElf_Ehdr eh, ehout;
+	Elf_Scn *scn;
+	Elf_Data *data;
+	GElf_Shdr sh;
+
+	fd = creat(outfile, 0777);
+	if (fd == -1) {
+		perror("creat");
+		return -1;
+	}
+
+	elfout = elf_begin(fd, ELF_C_WRITE, NULL);
+	if (!elfout) {
+		perror("elf_begin");
+		return -1;
+	}
+
+	if (!gelf_newehdr(elfout, gelf_getclass(elf->elf))) {
+		perror("gelf_newehdr");
+		return -1;
+	}
+
+	if (!gelf_getehdr(elfout, &ehout)) {
+		perror("gelf_getehdr");
+		return -1;
+	}
+
+	if (!gelf_getehdr(elf->elf, &eh)) {
+		perror("gelf_getehdr");
+		return -1;
+	}
+
+	memset(&ehout, 0, sizeof(ehout));
+	ehout.e_ident[EI_DATA] = eh.e_ident[EI_DATA];
+	ehout.e_machine = eh.e_machine;
+	ehout.e_type = eh.e_type;
+	ehout.e_version = EV_CURRENT;
+	ehout.e_shstrndx = find_section_by_name(elf, ".shstrtab")->idx;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		if (sec->idx == 0)
+			continue;
+
+		scn = elf_newscn(elfout);
+		if (!scn) {
+			perror("elf_newscn");
+			return -1;
+		}
+
+		data = elf_newdata(scn);
+		if (!data) {
+			perror("elf_newdata");
+			return -1;
+		}
+
+		if (!elf_flagdata(data, ELF_C_SET, ELF_F_DIRTY)) {
+			perror("elf_flagdata");
+			return -1;
+		}
+
+		data->d_type = sec->data->d_type;
+		data->d_buf = sec->data->d_buf;
+		data->d_size = sec->data->d_size;
+
+		if(!gelf_getshdr(scn, &sh)) {
+			perror("gelf_getshdr");
+			return -1;
+		}
+
+		sh = sec->sh;
+
+		if (!gelf_update_shdr(scn, &sh)) {
+			perror("gelf_update_shdr");
+			return -1;
+		}
+	}
+
+	if (!gelf_update_ehdr(elfout, &ehout)) {
+		perror("gelf_update_ehdr");
+		return -1;
+	}
+
+	if (elf_update(elfout, ELF_C_WRITE) < 0) {
+		perror("elf_update");
+		return -1;
+	}
+
+	return 0;
+}
+
 void elf_close(struct elf *elf)
 {
 	struct section *sec, *tmpsec;
diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index 75e44c7..f9d68ea 100644
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -83,6 +83,11 @@ struct rela *find_rela_by_dest(struct section *sec, unsigned long offset);
 struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 				     unsigned int len);
 struct symbol *find_containing_func(struct section *sec, unsigned long offset);
+struct section *elf_create_section(struct elf *elf, const char *name, size_t
+				   entsize, int nr);
+struct section *elf_create_rela_section(struct elf *elf, struct section *base);
+int elf_rebuild_rela_section(struct section *sec);
+int elf_write_to_file(struct elf *elf, char *outfile);
 void elf_close(struct elf *elf);
 
 
diff --git a/tools/objtool/objtool.c b/tools/objtool/objtool.c
index ecc5b1b..b2051d1 100644
--- a/tools/objtool/objtool.c
+++ b/tools/objtool/objtool.c
@@ -42,10 +42,11 @@ struct cmd_struct {
 };
 
 static const char objtool_usage_string[] =
-	"objtool [OPTIONS] COMMAND [ARGS]";
+	"objtool COMMAND [ARGS]";
 
 static struct cmd_struct objtool_cmds[] = {
 	{"check",	cmd_check,	"Perform stack metadata validation on an object file" },
+	{"undwarf",	cmd_undwarf,	"Generate in-place undwarf metadata for an object file" },
 };
 
 bool help;
diff --git a/tools/objtool/undwarf-types.h b/tools/objtool/undwarf-types.h
new file mode 100644
index 0000000..b624188
--- /dev/null
+++ b/tools/objtool/undwarf-types.h
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _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/tools/objtool/undwarf.c b/tools/objtool/undwarf.c
new file mode 100644
index 0000000..68c026f
--- /dev/null
+++ b/tools/objtool/undwarf.c
@@ -0,0 +1,308 @@
+/*
+ * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "undwarf.h"
+#include "check.h"
+#include "warn.h"
+
+int create_undwarf(struct objtool_file *file)
+{
+	struct instruction *insn;
+
+	for_each_insn(file, insn) {
+		struct undwarf *undwarf = &insn->undwarf;
+		struct cfi_reg *cfa = &insn->state.cfa;
+		struct cfi_reg *bp = &insn->state.regs[CFI_BP];
+
+		if (cfa->base == CFI_UNDEFINED) {
+			undwarf->cfa_reg = UNDWARF_REG_UNDEFINED;
+			continue;
+		}
+
+		switch (cfa->base) {
+		case CFI_SP:
+			undwarf->cfa_reg = UNDWARF_REG_SP;
+			break;
+		case CFI_SP_INDIRECT:
+			undwarf->cfa_reg = UNDWARF_REG_SP_INDIRECT;
+			break;
+		case CFI_BP:
+			undwarf->cfa_reg = UNDWARF_REG_BP;
+			break;
+		case CFI_BP_INDIRECT:
+			undwarf->cfa_reg = UNDWARF_REG_BP_INDIRECT;
+			break;
+		case CFI_R10:
+			undwarf->cfa_reg = UNDWARF_REG_R10;
+			break;
+		case CFI_R13:
+			undwarf->cfa_reg = UNDWARF_REG_R10;
+			break;
+		case CFI_DI:
+			undwarf->cfa_reg = UNDWARF_REG_DI;
+			break;
+		case CFI_DX:
+			undwarf->cfa_reg = UNDWARF_REG_DX;
+			break;
+		default:
+			WARN_FUNC("unknown CFA base reg %d",
+				  insn->sec, insn->offset, cfa->base);
+			return -1;
+		}
+
+		switch(bp->base) {
+		case CFI_UNDEFINED:
+			undwarf->bp_reg = UNDWARF_REG_UNDEFINED;
+			break;
+		case CFI_CFA:
+			undwarf->bp_reg = UNDWARF_REG_CFA;
+			break;
+		case CFI_BP:
+			undwarf->bp_reg = UNDWARF_REG_BP;
+			break;
+		default:
+			WARN_FUNC("unknown BP base reg %d",
+				  insn->sec, insn->offset, bp->base);
+			return -1;
+		}
+
+		undwarf->cfa_offset = cfa->offset;
+		undwarf->bp_offset = bp->offset;
+		undwarf->type = insn->state.type;
+	}
+
+	return 0;
+}
+
+int create_undwarf_section(struct objtool_file *file)
+{
+	struct instruction *insn, *prev_insn = NULL;
+	struct section *sec, *relasec;
+	struct rela *rela;
+	unsigned int index, nr = 0;
+	struct undwarf *undwarf = NULL;
+
+	sec = find_section_by_name(file->elf, ".undwarf");
+	if (sec) {
+		WARN("file already has .undwarf section, skipping");
+		return -1;
+	}
+
+	/* count number of needed undwarves */
+	for_each_insn(file, insn) {
+		if (insn->needs_cfi &&
+		    (!prev_insn || prev_insn->sec != insn->sec ||
+		     memcmp(&insn->undwarf, &prev_insn->undwarf,
+			    sizeof(struct undwarf)))) {
+			nr++;
+		}
+		prev_insn = insn;
+	}
+
+	if (!nr)
+		return 0;
+
+	/* create .undwarf and .rela.undwarf sections */
+	sec = elf_create_section(file->elf, ".undwarf",
+				 sizeof(struct undwarf), nr);
+
+	sec->sh.sh_type = SHT_PROGBITS;
+	sec->sh.sh_addralign = 1;
+	sec->sh.sh_flags = SHF_ALLOC;
+
+	relasec = elf_create_rela_section(file->elf, sec);
+	if (!relasec)
+		return -1;
+
+	/* populate sections */
+	index = 0;
+	prev_insn = NULL;
+	for_each_insn(file, insn) {
+		if (insn->needs_cfi &&
+		    (!prev_insn || prev_insn->sec != insn->sec ||
+		     memcmp(&insn->undwarf, &prev_insn->undwarf,
+			    sizeof(struct undwarf)))) {
+
+#if 0
+			printf("%s:%lx: cfa:%d+%d bp:%d+%d type:%d\n",
+			       insn->sec->name, insn->offset, insn->undwarf.cfa_reg,
+			       insn->undwarf.cfa_offset, insn->undwarf.fp_reg,
+			       insn->undwarf.fp_offset, insn->undwarf.type);
+#endif
+
+			undwarf = (struct undwarf *)sec->data->d_buf + index;
+
+			memcpy(undwarf, &insn->undwarf, sizeof(*undwarf));
+			undwarf->len = insn->len;
+
+			/* add rela for undwarf->ip */
+			rela = malloc(sizeof(*rela));
+			if (!rela) {
+				perror("malloc");
+				return -1;
+			}
+			memset(rela, 0, sizeof(*rela));
+
+			rela->sym = insn->sec->sym;
+			rela->addend = insn->offset;
+			rela->type = R_X86_64_PC32;
+			rela->offset = index * sizeof(struct undwarf);
+
+			list_add_tail(&rela->list, &relasec->rela_list);
+			hash_add(relasec->rela_hash, &rela->hash, rela->offset);
+
+			index++;
+
+		} else if (insn->needs_cfi) {
+			undwarf->len += insn->len;
+		}
+		prev_insn = insn;
+	}
+
+	if (elf_rebuild_rela_section(relasec))
+		return -1;
+
+	return 0;
+}
+
+int update_file(struct objtool_file *file)
+{
+	char *outfile;
+	int ret;
+
+	outfile = malloc(strlen(objname) + strlen(".undwarf") + 1);
+	if (!outfile) {
+		perror("malloc");
+		return -1;
+	}
+
+	strcpy(outfile, objname);
+	strcat(outfile, ".undwarf");
+	ret = elf_write_to_file(file->elf, outfile);
+	if (ret < 0)
+		return -1;
+
+	if (rename(outfile, objname) < 0) {
+		WARN("can't rename file");
+		perror("rename");
+		return -1;
+	}
+
+	free(outfile);
+
+	return 0;
+}
+
+static const char *reg_name(unsigned int reg)
+{
+	switch (reg) {
+	case UNDWARF_REG_CFA:
+		return "cfa";
+	case UNDWARF_REG_DX:
+		return "dx";
+	case UNDWARF_REG_DI:
+		return "di";
+	case UNDWARF_REG_BP:
+		return "bp";
+	case UNDWARF_REG_SP:
+		return "sp";
+	case UNDWARF_REG_R10:
+		return "r10";
+	case UNDWARF_REG_R13:
+		return "r13";
+	case UNDWARF_REG_BP_INDIRECT:
+		return "bp(ind)";
+	case UNDWARF_REG_SP_INDIRECT:
+		return "sp(ind)";
+	default:
+		return "?";
+	}
+}
+
+static const char *undwarf_type_name(unsigned int type)
+{
+	switch (type) {
+	case UNDWARF_TYPE_CFA:
+		return "cfa";
+	case UNDWARF_TYPE_REGS:
+		return "regs";
+	case UNDWARF_TYPE_REGS_IRET:
+		return "iret";
+	default:
+		return "?";
+	}
+}
+
+static void print_reg(unsigned int reg, int offset)
+{
+	if (reg == UNDWARF_REG_BP_INDIRECT)
+		printf("(bp%+d)", offset);
+	else if (reg == UNDWARF_REG_SP_INDIRECT)
+		printf("(sp%+d)", offset);
+	else if (reg == UNDWARF_REG_UNDEFINED)
+		printf("(und)");
+	else
+		printf("%s%+d", reg_name(reg), offset);
+}
+
+int undwarf_dump(const char *_objname)
+{
+	struct elf *elf;
+	struct section *sec;
+	struct rela *rela;
+	struct undwarf *undwarf;
+	int nr, i;
+
+	objname = _objname;
+
+	elf = elf_open(objname);
+	if (!elf) {
+		WARN("error reading elf file %s\n", objname);
+		return 1;
+	}
+
+	sec = find_section_by_name(elf, ".undwarf");
+	if (!sec || !sec->rela)
+		return 0;
+
+	nr = sec->len / sizeof(*undwarf);
+	for (i = 0; i < nr; i++) {
+		undwarf = (struct undwarf *)sec->data->d_buf + i;
+
+		rela = find_rela_by_dest(sec, i * sizeof(*undwarf));
+		if (!rela) {
+			WARN("can't find rela for undwarf[%d]\n", i);
+			return 1;
+		}
+
+		printf("%s+%x: len:%u cfa:",
+		       rela->sym->name, rela->addend, undwarf->len);
+
+		print_reg(undwarf->cfa_reg, undwarf->cfa_offset);
+
+		printf(" bp:");
+
+		print_reg(undwarf->bp_reg, undwarf->bp_offset);
+
+		printf(" type:%s\n", undwarf_type_name(undwarf->type));
+	}
+
+	return 0;
+}
diff --git a/tools/objtool/builtin.h b/tools/objtool/undwarf.h
similarity index 64%
copy from tools/objtool/builtin.h
copy to tools/objtool/undwarf.h
index 34d2ba7..76346e7 100644
--- a/tools/objtool/builtin.h
+++ b/tools/objtool/undwarf.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License
@@ -14,9 +14,18 @@
  * 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 _BUILTIN_H
-#define _BUILTIN_H
 
-extern int cmd_check(int argc, const char **argv);
+#ifndef _UNDWARF_H
+#define _UNDWARF_H
 
-#endif /* _BUILTIN_H */
+#include "undwarf-types.h"
+
+struct objtool_file;
+
+int create_undwarf(struct objtool_file *file);
+int create_undwarf_section(struct objtool_file *file);
+int update_file(struct objtool_file *file);
+
+int undwarf_dump(const char *objname);
+
+#endif /* _UNDWARF_H */
-- 
2.7.4