objtool: Add tool to perform compile-time stack metadata validation

This adds a host tool named objtool which has a "check" subcommand which
analyzes .o files to ensure the validity of stack metadata.  It enforces
a set of rules on asm code and C inline assembly code so that stack
traces can be reliable.

For each function, it recursively follows all possible code paths and
validates the correct frame pointer state at each instruction.

It also follows code paths involving kernel special sections, like
.altinstructions, __jump_table, and __ex_table, which can add
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.

Here are some of the benefits of validating stack metadata:

a) More reliable stack traces for frame pointer enabled kernels

   Frame pointers are used for debugging purposes.  They allow runtime
   code and debug tools to be able to walk the stack to determine the
   chain of function call sites that led to the currently executing
   code.

   For some architectures, frame pointers are enabled by
   CONFIG_FRAME_POINTER.  For some other architectures they may be
   required by the ABI (sometimes referred to as "backchain pointers").

   For C code, gcc automatically generates instructions for setting up
   frame pointers when the -fno-omit-frame-pointer option is used.

   But for asm code, the frame setup instructions have to be written by
   hand, which most people don't do.  So the end result is that
   CONFIG_FRAME_POINTER is honored for C code but not for most asm code.

   For stack traces based on frame pointers to be reliable, all
   functions which call other functions must first create a stack frame
   and update the frame pointer.  If a first function doesn't properly
   create a stack frame before calling a second function, the *caller*
   of the first function will be skipped on the stack trace.

   For example, consider the following example backtrace with frame
   pointers enabled:

     [<ffffffff81812584>] dump_stack+0x4b/0x63
     [<ffffffff812d6dc2>] cmdline_proc_show+0x12/0x30
     [<ffffffff8127f568>] seq_read+0x108/0x3e0
     [<ffffffff812cce62>] proc_reg_read+0x42/0x70
     [<ffffffff81256197>] __vfs_read+0x37/0x100
     [<ffffffff81256b16>] vfs_read+0x86/0x130
     [<ffffffff81257898>] SyS_read+0x58/0xd0
     [<ffffffff8181c1f2>] entry_SYSCALL_64_fastpath+0x12/0x76

   It correctly shows that the caller of cmdline_proc_show() is
   seq_read().

   If we remove the frame pointer logic from cmdline_proc_show() by
   replacing the frame pointer related instructions with nops, here's
   what it looks like instead:

     [<ffffffff81812584>] dump_stack+0x4b/0x63
     [<ffffffff812d6dc2>] cmdline_proc_show+0x12/0x30
     [<ffffffff812cce62>] proc_reg_read+0x42/0x70
     [<ffffffff81256197>] __vfs_read+0x37/0x100
     [<ffffffff81256b16>] vfs_read+0x86/0x130
     [<ffffffff81257898>] SyS_read+0x58/0xd0
     [<ffffffff8181c1f2>] entry_SYSCALL_64_fastpath+0x12/0x76

   Notice that cmdline_proc_show()'s caller, seq_read(), has been
   skipped.  Instead the stack trace seems to show that
   cmdline_proc_show() was called by proc_reg_read().

   The benefit of "objtool check" here is that because it ensures that
   *all* functions honor CONFIG_FRAME_POINTER, no functions will ever[*]
   be skipped on a stack trace.

   [*] unless an interrupt or exception has occurred at the very
       beginning of a function before the stack frame has been created,
       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

   This is not yet implemented.  For more details about what is planned,
   see tools/objtool/Documentation/stack-validation.txt.

c) Higher live patching compatibility rate

   This is not yet implemented.  For more details about what is planned,
   see tools/objtool/Documentation/stack-validation.txt.

To achieve the validation, "objtool check" enforces the following rules:

1. Each callable function must be annotated as such with the ELF
   function type.  In asm code, this is typically done using the
   ENTRY/ENDPROC macros.  If objtool finds a return instruction
   outside of a function, it flags an error since that usually indicates
   callable code which should be annotated accordingly.

   This rule is needed so that objtool can properly identify each
   callable function in order to analyze its stack metadata.

2. Conversely, each section of code which is *not* callable should *not*
   be annotated as an ELF function.  The ENDPROC macro shouldn't be used
   in this case.

   This rule is needed so that objtool can ignore non-callable code.
   Such code doesn't have to follow any of the other rules.

3. Each callable function which calls another function must have the
   correct frame pointer logic, if required by CONFIG_FRAME_POINTER or
   the architecture's back chain rules.  This can by done in asm code
   with the FRAME_BEGIN/FRAME_END macros.

   This rule ensures that frame pointer based stack traces will work as
   designed.  If function A doesn't create a stack frame before calling
   function B, the _caller_ of function A will be skipped on the stack
   trace.

4. Dynamic jumps and jumps to undefined symbols are only allowed if:

   a) the jump is part of a switch statement; or

   b) the jump matches sibling call semantics and the frame pointer has
      the same value it had on function entry.

   This rule is needed so that objtool can reliably analyze all of a
   function's code paths.  If a function jumps to code in another file,
   and it's not a sibling call, objtool has no way to follow the jump
   because it only analyzes a single file at a time.

5. A callable function may not execute kernel entry/exit instructions.
   The only code which needs such instructions is kernel entry code,
   which shouldn't be be in callable functions anyway.

   This rule is just a sanity check to ensure that callable functions
   return normally.

It currently only supports x86_64.  I tried to make the code generic so
that support for other architectures can hopefully be plugged in
relatively easily.

On my Lenovo laptop with a i7-4810MQ 4-core/8-thread CPU, building the
kernel with objtool checking every .o file adds about three seconds of
total build time.  It hasn't been optimized for performance yet, so
there are probably some opportunities for better build performance.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/f3efb173de43bd067b060de73f856567c0fa1174.1456719558.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>

1 files changed, 1072 insertions, 0 deletions

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
new file mode 100644
index 000000000000..f7e0ebac3fbe
--- /dev/null
+++ b/tools/objtool/builtin-check.c
@@ -0,0 +1,1072 @@
+/*
+ * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@redhat.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * objtool check:
+ *
+ * This command analyzes every .o file and ensures the validity of its stack
+ * trace metadata.  It enforces a set of rules on asm code and C inline
+ * assembly code so that stack traces can be reliable.
+ *
+ * For more information, see tools/objtool/Documentation/stack-validation.txt.
+ */
+
+#include <string.h>
+#include <subcmd/parse-options.h>
+
+#include "builtin.h"
+#include "elf.h"
+#include "special.h"
+#include "arch.h"
+#include "warn.h"
+
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+
+#define STATE_FP_SAVED		0x1
+#define STATE_FP_SETUP		0x2
+#define STATE_FENTRY		0x4
+
+struct instruction {
+	struct list_head list;
+	struct section *sec;
+	unsigned long offset;
+	unsigned int len, state;
+	unsigned char type;
+	unsigned long immediate;
+	bool alt_group, visited;
+	struct symbol *call_dest;
+	struct instruction *jump_dest;
+	struct list_head alts;
+};
+
+struct alternative {
+	struct list_head list;
+	struct instruction *insn;
+};
+
+struct objtool_file {
+	struct elf *elf;
+	struct list_head insns;
+};
+
+const char *objname;
+static bool nofp;
+
+static struct instruction *find_instruction(struct objtool_file *file,
+					    struct section *sec,
+					    unsigned long offset)
+{
+	struct instruction *insn;
+
+	list_for_each_entry(insn, &file->insns, list)
+		if (insn->sec == sec && insn->offset == offset)
+			return insn;
+
+	return NULL;
+}
+
+/*
+ * Check if the function has been manually whitelisted with the
+ * STACK_FRAME_NON_STANDARD macro, or if it should be automatically whitelisted
+ * due to its use of a context switching instruction.
+ */
+static bool ignore_func(struct objtool_file *file, struct symbol *func)
+{
+	struct section *macro_sec;
+	struct rela *rela;
+	struct instruction *insn;
+
+	/* check for STACK_FRAME_NON_STANDARD */
+	macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
+	if (macro_sec && macro_sec->rela)
+		list_for_each_entry(rela, &macro_sec->rela->relas, list)
+			if (rela->sym->sec == func->sec &&
+			    rela->addend == func->offset)
+				return true;
+
+	/* check if it has a context switching instruction */
+	insn = find_instruction(file, func->sec, func->offset);
+	if (!insn)
+		return false;
+	list_for_each_entry_from(insn, &file->insns, list) {
+		if (insn->sec != func->sec ||
+		    insn->offset >= func->offset + func->len)
+			break;
+		if (insn->type == INSN_CONTEXT_SWITCH)
+			return true;
+	}
+
+	return false;
+}
+
+/*
+ * This checks to see if the given function is a "noreturn" function.
+ *
+ * For global functions which are outside the scope of this object file, we
+ * have to keep a manual list of them.
+ *
+ * For local functions, we have to detect them manually by simply looking for
+ * the lack of a return instruction.
+ */
+static bool dead_end_function(struct objtool_file *file, struct symbol *func)
+{
+	int i;
+	struct instruction *insn;
+	bool empty = true;
+
+	/*
+	 * Unfortunately these have to be hard coded because the noreturn
+	 * attribute isn't provided in ELF data.
+	 */
+	static const char * const global_noreturns[] = {
+		"__stack_chk_fail",
+		"panic",
+		"do_exit",
+		"__module_put_and_exit",
+		"complete_and_exit",
+		"kvm_spurious_fault",
+		"__reiserfs_panic",
+		"lbug_with_loc"
+	};
+
+	if (func->bind == STB_WEAK)
+		return false;
+
+	if (func->bind == STB_GLOBAL)
+		for (i = 0; i < ARRAY_SIZE(global_noreturns); i++)
+			if (!strcmp(func->name, global_noreturns[i]))
+				return true;
+
+	if (!func->sec)
+		return false;
+
+	insn = find_instruction(file, func->sec, func->offset);
+	if (!insn)
+		return false;
+
+	list_for_each_entry_from(insn, &file->insns, list) {
+		if (insn->sec != func->sec ||
+		    insn->offset >= func->offset + func->len)
+			break;
+
+		empty = false;
+
+		if (insn->type == INSN_RETURN)
+			return false;
+
+		if (insn->type == INSN_JUMP_UNCONDITIONAL) {
+			struct instruction *dest = insn->jump_dest;
+			struct symbol *dest_func;
+
+			if (!dest)
+				/* sibling call to another file */
+				return false;
+
+			if (dest->sec != func->sec ||
+			    dest->offset < func->offset ||
+			    dest->offset >= func->offset + func->len) {
+				/* local sibling call */
+				dest_func = find_symbol_by_offset(dest->sec,
+								  dest->offset);
+				if (!dest_func)
+					continue;
+
+				return dead_end_function(file, dest_func);
+			}
+		}
+
+		if (insn->type == INSN_JUMP_DYNAMIC)
+			/* sibling call */
+			return false;
+	}
+
+	return !empty;
+}
+
+/*
+ * Call the arch-specific instruction decoder for all the instructions and add
+ * them to the global insns list.
+ */
+static int decode_instructions(struct objtool_file *file)
+{
+	struct section *sec;
+	unsigned long offset;
+	struct instruction *insn;
+	int ret;
+
+	INIT_LIST_HEAD(&file->insns);
+
+	list_for_each_entry(sec, &file->elf->sections, list) {
+
+		if (!(sec->sh.sh_flags & SHF_EXECINSTR))
+			continue;
+
+		for (offset = 0; offset < sec->len; offset += insn->len) {
+			insn = malloc(sizeof(*insn));
+			memset(insn, 0, sizeof(*insn));
+
+			INIT_LIST_HEAD(&insn->alts);
+			insn->sec = sec;
+			insn->offset = offset;
+
+			ret = arch_decode_instruction(file->elf, sec, offset,
+						      sec->len - offset,
+						      &insn->len, &insn->type,
+						      &insn->immediate);
+			if (ret)
+				return ret;
+
+			if (!insn->type || insn->type > INSN_LAST) {
+				WARN_FUNC("invalid instruction type %d",
+					  insn->sec, insn->offset, insn->type);
+				return -1;
+			}
+
+			list_add_tail(&insn->list, &file->insns);
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * Warnings shouldn't be reported for ignored functions.
+ */
+static void get_ignores(struct objtool_file *file)
+{
+	struct instruction *insn;
+	struct section *sec;
+	struct symbol *func;
+
+	list_for_each_entry(sec, &file->elf->sections, list) {
+		list_for_each_entry(func, &sec->symbols, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			if (!ignore_func(file, func))
+				continue;
+
+			insn = find_instruction(file, sec, func->offset);
+			if (!insn)
+				continue;
+
+			list_for_each_entry_from(insn, &file->insns, list) {
+				if (insn->sec != func->sec ||
+				    insn->offset >= func->offset + func->len)
+					break;
+
+				insn->visited = true;
+			}
+		}
+	}
+}
+
+/*
+ * Find the destination instructions for all jumps.
+ */
+static int get_jump_destinations(struct objtool_file *file)
+{
+	struct instruction *insn;
+	struct rela *rela;
+	struct section *dest_sec;
+	unsigned long dest_off;
+
+	list_for_each_entry(insn, &file->insns, list) {
+		if (insn->type != INSN_JUMP_CONDITIONAL &&
+		    insn->type != INSN_JUMP_UNCONDITIONAL)
+			continue;
+
+		/* skip ignores */
+		if (insn->visited)
+			continue;
+
+		rela = find_rela_by_dest_range(insn->sec, insn->offset,
+					       insn->len);
+		if (!rela) {
+			dest_sec = insn->sec;
+			dest_off = insn->offset + insn->len + insn->immediate;
+		} else if (rela->sym->type == STT_SECTION) {
+			dest_sec = rela->sym->sec;
+			dest_off = rela->addend + 4;
+		} else if (rela->sym->sec->idx) {
+			dest_sec = rela->sym->sec;
+			dest_off = rela->sym->sym.st_value + rela->addend + 4;
+		} else {
+			/* sibling call */
+			insn->jump_dest = 0;
+			continue;
+		}
+
+		insn->jump_dest = find_instruction(file, dest_sec, dest_off);
+		if (!insn->jump_dest) {
+
+			/*
+			 * This is a special case where an alt instruction
+			 * jumps past the end of the section.  These are
+			 * handled later in handle_group_alt().
+			 */
+			if (!strcmp(insn->sec->name, ".altinstr_replacement"))
+				continue;
+
+			WARN_FUNC("can't find jump dest instruction at %s+0x%lx",
+				  insn->sec, insn->offset, dest_sec->name,
+				  dest_off);
+			return -1;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * Find the destination instructions for all calls.
+ */
+static int get_call_destinations(struct objtool_file *file)
+{
+	struct instruction *insn;
+	unsigned long dest_off;
+	struct rela *rela;
+
+	list_for_each_entry(insn, &file->insns, list) {
+		if (insn->type != INSN_CALL)
+			continue;
+
+		rela = find_rela_by_dest_range(insn->sec, insn->offset,
+					       insn->len);
+		if (!rela) {
+			dest_off = insn->offset + insn->len + insn->immediate;
+			insn->call_dest = find_symbol_by_offset(insn->sec,
+								dest_off);
+			if (!insn->call_dest) {
+				WARN_FUNC("can't find call dest symbol at offset 0x%lx",
+					  insn->sec, insn->offset, dest_off);
+				return -1;
+			}
+		} else if (rela->sym->type == STT_SECTION) {
+			insn->call_dest = find_symbol_by_offset(rela->sym->sec,
+								rela->addend+4);
+			if (!insn->call_dest ||
+			    insn->call_dest->type != STT_FUNC) {
+				WARN_FUNC("can't find call dest symbol at %s+0x%x",
+					  insn->sec, insn->offset,
+					  rela->sym->sec->name,
+					  rela->addend + 4);
+				return -1;
+			}
+		} else
+			insn->call_dest = rela->sym;
+	}
+
+	return 0;
+}
+
+/*
+ * The .alternatives section requires some extra special care, over and above
+ * what other special sections require:
+ *
+ * 1. Because alternatives are patched in-place, we need to insert a fake jump
+ *    instruction at the end so that validate_branch() skips all the original
+ *    replaced instructions when validating the new instruction path.
+ *
+ * 2. An added wrinkle is that the new instruction length might be zero.  In
+ *    that case the old instructions are replaced with noops.  We simulate that
+ *    by creating a fake jump as the only new instruction.
+ *
+ * 3. In some cases, the alternative section includes an instruction which
+ *    conditionally jumps to the _end_ of the entry.  We have to modify these
+ *    jumps' destinations to point back to .text rather than the end of the
+ *    entry in .altinstr_replacement.
+ *
+ * 4. It has been requested that we don't validate the !POPCNT feature path
+ *    which is a "very very small percentage of machines".
+ */
+static int handle_group_alt(struct objtool_file *file,
+			    struct special_alt *special_alt,
+			    struct instruction *orig_insn,
+			    struct instruction **new_insn)
+{
+	struct instruction *last_orig_insn, *last_new_insn, *insn, *fake_jump;
+	unsigned long dest_off;
+
+	last_orig_insn = NULL;
+	insn = orig_insn;
+	list_for_each_entry_from(insn, &file->insns, list) {
+		if (insn->sec != special_alt->orig_sec ||
+		    insn->offset >= special_alt->orig_off + special_alt->orig_len)
+			break;
+
+		if (special_alt->skip_orig)
+			insn->type = INSN_NOP;
+
+		insn->alt_group = true;
+		last_orig_insn = insn;
+	}
+
+	if (list_is_last(&last_orig_insn->list, &file->insns) ||
+	    list_next_entry(last_orig_insn, list)->sec != special_alt->orig_sec) {
+		WARN("%s: don't know how to handle alternatives at end of section",
+		     special_alt->orig_sec->name);
+		return -1;
+	}
+
+	fake_jump = malloc(sizeof(*fake_jump));
+	if (!fake_jump) {
+		WARN("malloc failed");
+		return -1;
+	}
+	memset(fake_jump, 0, sizeof(*fake_jump));
+	INIT_LIST_HEAD(&fake_jump->alts);
+	fake_jump->sec = special_alt->new_sec;
+	fake_jump->offset = -1;
+	fake_jump->type = INSN_JUMP_UNCONDITIONAL;
+	fake_jump->jump_dest = list_next_entry(last_orig_insn, list);
+
+	if (!special_alt->new_len) {
+		*new_insn = fake_jump;
+		return 0;
+	}
+
+	last_new_insn = NULL;
+	insn = *new_insn;
+	list_for_each_entry_from(insn, &file->insns, list) {
+		if (insn->sec != special_alt->new_sec ||
+		    insn->offset >= special_alt->new_off + special_alt->new_len)
+			break;
+
+		last_new_insn = insn;
+
+		if (insn->type != INSN_JUMP_CONDITIONAL &&
+		    insn->type != INSN_JUMP_UNCONDITIONAL)
+			continue;
+
+		if (!insn->immediate)
+			continue;
+
+		dest_off = insn->offset + insn->len + insn->immediate;
+		if (dest_off == special_alt->new_off + special_alt->new_len)
+			insn->jump_dest = fake_jump;
+
+		if (!insn->jump_dest) {
+			WARN_FUNC("can't find alternative jump destination",
+				  insn->sec, insn->offset);
+			return -1;
+		}
+	}
+
+	if (!last_new_insn) {
+		WARN_FUNC("can't find last new alternative instruction",
+			  special_alt->new_sec, special_alt->new_off);
+		return -1;
+	}
+
+	list_add(&fake_jump->list, &last_new_insn->list);
+
+	return 0;
+}
+
+/*
+ * A jump table entry can either convert a nop to a jump or a jump to a nop.
+ * If the original instruction is a jump, make the alt entry an effective nop
+ * by just skipping the original instruction.
+ */
+static int handle_jump_alt(struct objtool_file *file,
+			   struct special_alt *special_alt,
+			   struct instruction *orig_insn,
+			   struct instruction **new_insn)
+{
+	if (orig_insn->type == INSN_NOP)
+		return 0;
+
+	if (orig_insn->type != INSN_JUMP_UNCONDITIONAL) {
+		WARN_FUNC("unsupported instruction at jump label",
+			  orig_insn->sec, orig_insn->offset);
+		return -1;
+	}
+
+	*new_insn = list_next_entry(orig_insn, list);
+	return 0;
+}
+
+/*
+ * Read all the special sections which have alternate instructions which can be
+ * patched in or redirected to at runtime.  Each instruction having alternate
+ * instruction(s) has them added to its insn->alts list, which will be
+ * traversed in validate_branch().
+ */
+static int get_special_section_alts(struct objtool_file *file)
+{
+	struct list_head special_alts;
+	struct instruction *orig_insn, *new_insn;
+	struct special_alt *special_alt, *tmp;
+	struct alternative *alt;
+	int ret;
+
+	ret = special_get_alts(file->elf, &special_alts);
+	if (ret)
+		return ret;
+
+	list_for_each_entry_safe(special_alt, tmp, &special_alts, list) {
+		alt = malloc(sizeof(*alt));
+		if (!alt) {
+			WARN("malloc failed");
+			ret = -1;
+			goto out;
+		}
+
+		orig_insn = find_instruction(file, special_alt->orig_sec,
+					     special_alt->orig_off);
+		if (!orig_insn) {
+			WARN_FUNC("special: can't find orig instruction",
+				  special_alt->orig_sec, special_alt->orig_off);
+			ret = -1;
+			goto out;
+		}
+
+		new_insn = NULL;
+		if (!special_alt->group || special_alt->new_len) {
+			new_insn = find_instruction(file, special_alt->new_sec,
+						    special_alt->new_off);
+			if (!new_insn) {
+				WARN_FUNC("special: can't find new instruction",
+					  special_alt->new_sec,
+					  special_alt->new_off);
+				ret = -1;
+				goto out;
+			}
+		}
+
+		if (special_alt->group) {
+			ret = handle_group_alt(file, special_alt, orig_insn,
+					       &new_insn);
+			if (ret)
+				goto out;
+		} else if (special_alt->jump_or_nop) {
+			ret = handle_jump_alt(file, special_alt, orig_insn,
+					      &new_insn);
+			if (ret)
+				goto out;
+		}
+
+		alt->insn = new_insn;
+		list_add_tail(&alt->list, &orig_insn->alts);
+
+		list_del(&special_alt->list);
+		free(special_alt);
+	}
+
+out:
+	return ret;
+}
+
+/*
+ * For some switch statements, gcc generates a jump table in the .rodata
+ * section which contains a list of addresses within the function to jump to.
+ * This finds these jump tables and adds them to the insn->alts lists.
+ */
+static int get_switch_alts(struct objtool_file *file)
+{
+	struct instruction *insn, *alt_insn;
+	struct rela *rodata_rela, *rela;
+	struct section *rodata;
+	struct symbol *func;
+	struct alternative *alt;
+
+	list_for_each_entry(insn, &file->insns, list) {
+		if (insn->type != INSN_JUMP_DYNAMIC)
+			continue;
+
+		rodata_rela = find_rela_by_dest_range(insn->sec, insn->offset,
+						      insn->len);
+		if (!rodata_rela || strcmp(rodata_rela->sym->name, ".rodata"))
+			continue;
+
+		rodata = find_section_by_name(file->elf, ".rodata");
+		if (!rodata || !rodata->rela)
+			continue;
+
+		/* common case: jmpq *[addr](,%rax,8) */
+		rela = find_rela_by_dest(rodata, rodata_rela->addend);
+
+		/* rare case:   jmpq *[addr](%rip) */
+		if (!rela)
+			rela = find_rela_by_dest(rodata,
+						 rodata_rela->addend + 4);
+		if (!rela)
+			continue;
+
+		func = find_containing_func(insn->sec, insn->offset);
+		if (!func) {
+			WARN_FUNC("can't find containing func",
+				  insn->sec, insn->offset);
+			return -1;
+		}
+
+		list_for_each_entry_from(rela, &rodata->rela->relas, list) {
+			if (rela->sym->sec != insn->sec ||
+			    rela->addend <= func->offset ||
+			    rela->addend >= func->offset + func->len)
+				break;
+
+			alt_insn = find_instruction(file, insn->sec,
+						    rela->addend);
+			if (!alt_insn) {
+				WARN("%s: can't find instruction at %s+0x%x",
+				     rodata->rela->name, insn->sec->name,
+				     rela->addend);
+				return -1;
+			}
+
+			alt = malloc(sizeof(*alt));
+			if (!alt) {
+				WARN("malloc failed");
+				return -1;
+			}
+
+			alt->insn = alt_insn;
+			list_add_tail(&alt->list, &insn->alts);
+		}
+	}
+
+	return 0;
+}
+
+static int decode_sections(struct objtool_file *file)
+{
+	int ret;
+
+	ret = decode_instructions(file);
+	if (ret)
+		return ret;
+
+	get_ignores(file);
+
+	ret = get_jump_destinations(file);
+	if (ret)
+		return ret;
+
+	ret = get_call_destinations(file);
+	if (ret)
+		return ret;
+
+	ret = get_special_section_alts(file);
+	if (ret)
+		return ret;
+
+	ret = get_switch_alts(file);
+	if (ret)
+		return ret;
+
+	return 0;
+}
+
+static bool is_fentry_call(struct instruction *insn)
+{
+	if (insn->type == INSN_CALL &&
+	    insn->call_dest->type == STT_NOTYPE &&
+	    !strcmp(insn->call_dest->name, "__fentry__"))
+		return true;
+
+	return false;
+}
+
+static bool has_modified_stack_frame(struct instruction *insn)
+{
+	return (insn->state & STATE_FP_SAVED) ||
+	       (insn->state & STATE_FP_SETUP);
+}
+
+static bool has_valid_stack_frame(struct instruction *insn)
+{
+	return (insn->state & STATE_FP_SAVED) &&
+	       (insn->state & STATE_FP_SETUP);
+}
+
+/*
+ * Follow the branch starting at the given instruction, and recursively follow
+ * any other branches (jumps).  Meanwhile, track the frame pointer state at
+ * each instruction and validate all the rules described in
+ * tools/objtool/Documentation/stack-validation.txt.
+ */
+static int validate_branch(struct objtool_file *file,
+			   struct instruction *first, unsigned char first_state)
+{
+	struct alternative *alt;
+	struct instruction *insn;
+	struct section *sec;
+	unsigned char state;
+	int ret, warnings = 0;
+
+	insn = first;
+	sec = insn->sec;
+	state = first_state;
+
+	if (insn->alt_group && list_empty(&insn->alts)) {
+		WARN_FUNC("don't know how to handle branch to middle of alternative instruction group",
+			  sec, insn->offset);
+		warnings++;
+	}
+
+	while (1) {
+		if (insn->visited) {
+			if (insn->state != state) {
+				WARN_FUNC("frame pointer state mismatch",
+					  sec, insn->offset);
+				warnings++;
+			}
+
+			return warnings;
+		}
+
+		/*
+		 * Catch a rare case where a noreturn function falls through to
+		 * the next function.
+		 */
+		if (is_fentry_call(insn) && (state & STATE_FENTRY))
+			return warnings;
+
+		insn->visited = true;
+		insn->state = state;
+
+		list_for_each_entry(alt, &insn->alts, list) {
+			ret = validate_branch(file, alt->insn, state);
+			warnings += ret;
+		}
+
+		switch (insn->type) {
+
+		case INSN_FP_SAVE:
+			if (!nofp) {
+				if (state & STATE_FP_SAVED) {
+					WARN_FUNC("duplicate frame pointer save",
+						  sec, insn->offset);
+					warnings++;
+				}
+				state |= STATE_FP_SAVED;
+			}
+			break;
+
+		case INSN_FP_SETUP:
+			if (!nofp) {
+				if (state & STATE_FP_SETUP) {
+					WARN_FUNC("duplicate frame pointer setup",
+						  sec, insn->offset);
+					warnings++;
+				}
+				state |= STATE_FP_SETUP;
+			}
+			break;
+
+		case INSN_FP_RESTORE:
+			if (!nofp) {
+				if (has_valid_stack_frame(insn))
+					state &= ~STATE_FP_SETUP;
+
+				state &= ~STATE_FP_SAVED;
+			}
+			break;
+
+		case INSN_RETURN:
+			if (!nofp && has_modified_stack_frame(insn)) {
+				WARN_FUNC("return without frame pointer restore",
+					  sec, insn->offset);
+				warnings++;
+			}
+			return warnings;
+
+		case INSN_CALL:
+			if (is_fentry_call(insn)) {
+				state |= STATE_FENTRY;
+				break;
+			}
+
+			if (dead_end_function(file, insn->call_dest))
+				return warnings;
+
+			/* fallthrough */
+		case INSN_CALL_DYNAMIC:
+			if (!nofp && !has_valid_stack_frame(insn)) {
+				WARN_FUNC("call without frame pointer save/setup",
+					  sec, insn->offset);
+				warnings++;
+			}
+			break;
+
+		case INSN_JUMP_CONDITIONAL:
+		case INSN_JUMP_UNCONDITIONAL:
+			if (insn->jump_dest) {
+				ret = validate_branch(file, insn->jump_dest,
+						      state);
+				warnings += ret;
+			} else if (has_modified_stack_frame(insn)) {
+				WARN_FUNC("sibling call from callable instruction with changed frame pointer",
+					  sec, insn->offset);
+				warnings++;
+			} /* else it's a sibling call */
+
+			if (insn->type == INSN_JUMP_UNCONDITIONAL)
+				return warnings;
+
+			break;
+
+		case INSN_JUMP_DYNAMIC:
+			if (list_empty(&insn->alts) &&
+			    has_modified_stack_frame(insn)) {
+				WARN_FUNC("sibling call from callable instruction with changed frame pointer",
+					  sec, insn->offset);
+				warnings++;
+			}
+
+			return warnings;
+
+		case INSN_BUG:
+			return warnings;
+
+		default:
+			break;
+		}
+
+		insn = list_next_entry(insn, list);
+
+		if (&insn->list == &file->insns || insn->sec != sec) {
+			WARN("%s: unexpected end of section", sec->name);
+			warnings++;
+			return warnings;
+		}
+	}
+
+	return warnings;
+}
+
+static bool is_gcov_insn(struct instruction *insn)
+{
+	struct rela *rela;
+	struct section *sec;
+	struct symbol *sym;
+	unsigned long offset;
+
+	rela = find_rela_by_dest_range(insn->sec, insn->offset, insn->len);
+	if (!rela)
+		return false;
+
+	if (rela->sym->type != STT_SECTION)
+		return false;
+
+	sec = rela->sym->sec;
+	offset = rela->addend + insn->offset + insn->len - rela->offset;
+
+	list_for_each_entry(sym, &sec->symbols, list) {
+		if (sym->type != STT_OBJECT)
+			continue;
+
+		if (offset >= sym->offset && offset < sym->offset + sym->len)
+			return (!memcmp(sym->name, "__gcov0.", 8));
+	}
+
+	return false;
+}
+
+static bool is_kasan_insn(struct instruction *insn)
+{
+	return (insn->type == INSN_CALL &&
+		!strcmp(insn->call_dest->name, "__asan_handle_no_return"));
+}
+
+static bool is_ubsan_insn(struct instruction *insn)
+{
+	return (insn->type == INSN_CALL &&
+		!strcmp(insn->call_dest->name,
+			"__ubsan_handle_builtin_unreachable"));
+}
+
+static bool ignore_unreachable_insn(struct instruction *insn,
+				    unsigned long func_end)
+{
+	int i;
+
+	if (insn->type == INSN_NOP)
+		return true;
+
+	if (is_gcov_insn(insn))
+		return true;
+
+	/*
+	 * Check if this (or a subsequent) instruction is related to
+	 * CONFIG_UBSAN or CONFIG_KASAN.
+	 *
+	 * End the search at 5 instructions to avoid going into the weeds.
+	 */
+	for (i = 0; i < 5; i++) {
+
+		if (is_kasan_insn(insn) || is_ubsan_insn(insn))
+			return true;
+
+		if (insn->type == INSN_JUMP_UNCONDITIONAL && insn->jump_dest) {
+			insn = insn->jump_dest;
+			continue;
+		}
+
+		if (insn->offset + insn->len >= func_end)
+			break;
+		insn = list_next_entry(insn, list);
+	}
+
+	return false;
+}
+
+static int validate_functions(struct objtool_file *file)
+{
+	struct section *sec;
+	struct symbol *func;
+	struct instruction *insn;
+	unsigned long func_end;
+	int ret, warnings = 0;
+
+	list_for_each_entry(sec, &file->elf->sections, list) {
+		list_for_each_entry(func, &sec->symbols, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			insn = find_instruction(file, sec, func->offset);
+			if (!insn) {
+				WARN("%s(): can't find starting instruction",
+				     func->name);
+				warnings++;
+				continue;
+			}
+
+			ret = validate_branch(file, insn, 0);
+			warnings += ret;
+		}
+	}
+
+	list_for_each_entry(sec, &file->elf->sections, list) {
+		list_for_each_entry(func, &sec->symbols, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			insn = find_instruction(file, sec, func->offset);
+			if (!insn)
+				continue;
+
+			func_end = func->offset + func->len;
+
+			list_for_each_entry_from(insn, &file->insns, list) {
+				if (insn->sec != func->sec ||
+				    insn->offset >= func_end)
+					break;
+
+				if (insn->visited)
+					continue;
+
+				if (!ignore_unreachable_insn(insn, func_end)) {
+					WARN_FUNC("function has unreachable instruction", insn->sec, insn->offset);
+					warnings++;
+				}
+
+				insn->visited = true;
+			}
+		}
+	}
+
+	return warnings;
+}
+
+static int validate_uncallable_instructions(struct objtool_file *file)
+{
+	struct instruction *insn;
+	int warnings = 0;
+
+	list_for_each_entry(insn, &file->insns, list) {
+		if (!insn->visited && insn->type == INSN_RETURN) {
+			WARN_FUNC("return instruction outside of a callable function",
+				  insn->sec, insn->offset);
+			warnings++;
+		}
+	}
+
+	return warnings;
+}
+
+static void cleanup(struct objtool_file *file)
+{
+	struct instruction *insn, *tmpinsn;
+	struct alternative *alt, *tmpalt;
+
+	list_for_each_entry_safe(insn, tmpinsn, &file->insns, list) {
+		list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
+			list_del(&alt->list);
+			free(alt);
+		}
+		list_del(&insn->list);
+		free(insn);
+	}
+	elf_close(file->elf);
+}
+
+const char * const check_usage[] = {
+	"objtool check [<options>] file.o",
+	NULL,
+};
+
+int cmd_check(int argc, const char **argv)
+{
+	struct objtool_file file;
+	int ret, warnings = 0;
+
+	const struct option options[] = {
+		OPT_BOOLEAN('f', "no-fp", &nofp, "Skip frame pointer validation"),
+		OPT_END(),
+	};
+
+	argc = parse_options(argc, argv, options, check_usage, 0);
+
+	if (argc != 1)
+		usage_with_options(check_usage, options);
+
+	objname = argv[0];
+
+	file.elf = elf_open(objname);
+	if (!file.elf) {
+		fprintf(stderr, "error reading elf file %s\n", objname);
+		return 1;
+	}
+
+	INIT_LIST_HEAD(&file.insns);
+
+	ret = decode_sections(&file);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
+	ret = validate_functions(&file);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
+	ret = validate_uncallable_instructions(&file);
+	if (ret < 0)
+		goto out;
+	warnings += ret;
+
+out:
+	cleanup(&file);
+
+	/* ignore warnings for now until we get all the code cleaned up */
+	if (ret || warnings)
+		return 0;
+	return 0;
+}