[RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder

madvenka@linux.microsoft.com posted 20 patches 2 months, 4 weeks ago
[RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder
Posted by madvenka@linux.microsoft.com 2 months, 4 weeks ago
From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>

Implement a built-in command called cmd_fpv() that can be invoked as
follows:

	objtool fpv generate file.o

The built-in command invokes decode_instructions() to walk each function
and decode the instructions of the function.

Signed-off-by: Madhavan T. Venkataraman <madvenka@linux.microsoft.com>
---
 tools/objtool/Build                     |  5 ++
 tools/objtool/Makefile                  |  6 ++-
 tools/objtool/builtin-fpv.c             | 71 +++++++++++++++++++++++++
 tools/objtool/fpv.c                     | 19 +++++++
 tools/objtool/include/objtool/builtin.h |  1 +
 tools/objtool/include/objtool/objtool.h |  1 +
 tools/objtool/objtool.c                 | 12 ++++-
 tools/objtool/weak.c                    |  5 ++
 8 files changed, 117 insertions(+), 3 deletions(-)
 create mode 100644 tools/objtool/builtin-fpv.c
 create mode 100644 tools/objtool/fpv.c

diff --git a/tools/objtool/Build b/tools/objtool/Build
index 9c2a332f61f3..a491f51c40b4 100644
--- a/tools/objtool/Build
+++ b/tools/objtool/Build
@@ -15,9 +15,14 @@ objtool-$(SUBCMD_ORC) += decode.o
 objtool-$(SUBCMD_ORC) += unwind_hints.o
 objtool-$(SUBCMD_ORC) += orc_gen.o
 objtool-$(SUBCMD_ORC) += orc_dump.o
+objtool-$(SUBCMD_FPV) += fpv.o
+objtool-$(SUBCMD_FPV) += cfi.o
+objtool-$(SUBCMD_FPV) += insn.o
+objtool-$(SUBCMD_FPV) += decode.o
 
 objtool-y += builtin-check.o
 objtool-y += builtin-orc.o
+objtool-y += builtin-fpv.o
 objtool-y += elf.o
 objtool-y += objtool.o
 
diff --git a/tools/objtool/Makefile b/tools/objtool/Makefile
index 0dbd397f319d..2511053245bc 100644
--- a/tools/objtool/Makefile
+++ b/tools/objtool/Makefile
@@ -47,7 +47,11 @@ ifeq ($(SRCARCH),x86)
 	SUBCMD_ORC := y
 endif
 
-export SUBCMD_CHECK SUBCMD_ORC
+ifeq ($(SRCARCH),arm64)
+	SUBCMD_FPV := y
+endif
+
+export SUBCMD_CHECK SUBCMD_ORC SUBCMD_FPV
 export srctree OUTPUT CFLAGS SRCARCH AWK
 include $(srctree)/tools/build/Makefile.include
 
diff --git a/tools/objtool/builtin-fpv.c b/tools/objtool/builtin-fpv.c
new file mode 100644
index 000000000000..ff57dde39587
--- /dev/null
+++ b/tools/objtool/builtin-fpv.c
@@ -0,0 +1,71 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Author: Madhavan T. Venkataraman (madvenka@linux.microsoft.com)
+ *
+ * Copyright (C) 2022 Microsoft Corporation
+ */
+
+/*
+ * objtool fp validation:
+ *
+ * This command analyzes a .o file and adds .orc_unwind and .orc_unwind_ip
+ * sections to it. The sections are used by the frame pointer-based in-kernel
+ * unwinder to validate the frame pointer.
+ */
+
+#include <string.h>
+#include <objtool/builtin.h>
+#include <objtool/objtool.h>
+
+static const char * const fpv_usage[] = {
+	"objtool fpv generate file.o",
+	NULL,
+};
+
+const struct option fpv_options[] = {
+	OPT_END(),
+};
+
+int cmd_fpv(int argc, const char **argv)
+{
+	const char *objname;
+	struct objtool_file *file;
+	int ret;
+
+	argc--; argv++;
+	if (argc <= 0)
+		usage_with_options(fpv_usage, fpv_options);
+
+	objname = argv[1];
+
+	file = objtool_open_read(objname);
+	if (!file)
+		return 1;
+
+	/* Supported architectures. */
+	switch (file->elf->ehdr.e_machine) {
+	case EM_AARCH64:
+		break;
+
+	default:
+		return 1;
+	}
+
+	if (!strncmp(argv[0], "gen", 3)) {
+		ret = fpv_decode(file);
+		if (ret)
+			return ret;
+
+		if (list_empty(&file->insn_list))
+			return 0;
+
+		if (!file->elf->changed)
+			return 0;
+
+		return elf_write(file->elf);
+	}
+
+	usage_with_options(fpv_usage, fpv_options);
+
+	return 0;
+}
diff --git a/tools/objtool/fpv.c b/tools/objtool/fpv.c
new file mode 100644
index 000000000000..76f0f2e611a8
--- /dev/null
+++ b/tools/objtool/fpv.c
@@ -0,0 +1,19 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Author: Madhavan T. Venkataraman (madvenka@linux.microsoft.com)
+ *
+ * Copyright (C) 2022 Microsoft Corporation
+ */
+
+#include <string.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+
+#include <objtool/builtin.h>
+#include <objtool/insn.h>
+#include <objtool/warn.h>
+
+int fpv_decode(struct objtool_file *file)
+{
+	return decode_instructions(file);
+}
diff --git a/tools/objtool/include/objtool/builtin.h b/tools/objtool/include/objtool/builtin.h
index c39dbfaef6dc..bfd99e08c33b 100644
--- a/tools/objtool/include/objtool/builtin.h
+++ b/tools/objtool/include/objtool/builtin.h
@@ -16,5 +16,6 @@ extern int cmd_parse_options(int argc, const char **argv, const char * const usa
 
 extern int cmd_check(int argc, const char **argv);
 extern int cmd_orc(int argc, const char **argv);
+extern int cmd_fpv(int argc, const char **argv);
 
 #endif /* _BUILTIN_H */
diff --git a/tools/objtool/include/objtool/objtool.h b/tools/objtool/include/objtool/objtool.h
index 7a5c13a78f87..e00c8dcc6885 100644
--- a/tools/objtool/include/objtool/objtool.h
+++ b/tools/objtool/include/objtool/objtool.h
@@ -45,5 +45,6 @@ void objtool_pv_add(struct objtool_file *file, int idx, struct symbol *func);
 int check(struct objtool_file *file);
 int orc_dump(const char *objname);
 int orc_create(struct objtool_file *file);
+int fpv_decode(struct objtool_file *file);
 
 #endif /* _OBJTOOL_H */
diff --git a/tools/objtool/objtool.c b/tools/objtool/objtool.c
index b09946f4e1d6..974a9bc384e8 100644
--- a/tools/objtool/objtool.c
+++ b/tools/objtool/objtool.c
@@ -35,9 +35,17 @@ struct cmd_struct {
 static const char objtool_usage_string[] =
 	"objtool COMMAND [ARGS]";
 
+static const char check_help[] =
+	"Perform stack metadata validation on an object file";
+static const char orc_help[] =
+	"Generate in-place ORC unwind tables for an object file";
+static const char fpv_help[] =
+	"Generate in-place FP validation tables for an object file";
+
 static struct cmd_struct objtool_cmds[] = {
-	{"check",	cmd_check,	"Perform stack metadata validation on an object file" },
-	{"orc",		cmd_orc,	"Generate in-place ORC unwind tables for an object file" },
+	{"check",	cmd_check,	check_help },
+	{"orc",		cmd_orc,	orc_help },
+	{"fpv",		cmd_fpv,	fpv_help },
 };
 
 bool help;
diff --git a/tools/objtool/weak.c b/tools/objtool/weak.c
index 8314e824db4a..5e56ad5fe0fe 100644
--- a/tools/objtool/weak.c
+++ b/tools/objtool/weak.c
@@ -29,3 +29,8 @@ int __weak orc_create(struct objtool_file *file)
 {
 	UNSUPPORTED("orc");
 }
+
+int __weak fpv_decode(struct objtool_file *file)
+{
+	UNSUPPORTED("fpv");
+}
-- 
2.25.1
Re: [RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder
Posted by Mark Brown 2 months, 3 weeks ago
On Mon, May 23, 2022 at 07:16:26PM -0500, madvenka@linux.microsoft.com wrote:
> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
> 
> Implement a built-in command called cmd_fpv() that can be invoked as
> follows:
> 
> 	objtool fpv generate file.o
> 
> The built-in command invokes decode_instructions() to walk each function
> and decode the instructions of the function.

In commit b51277eb9775ce91 ("objtool: Ditch subcommands") Josh removed
subcommands so this interface is going to need a rethink.
Re: [RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder
Posted by Madhavan T. Venkataraman 2 months, 3 weeks ago

On 5/24/22 09:09, Mark Brown wrote:
> On Mon, May 23, 2022 at 07:16:26PM -0500, madvenka@linux.microsoft.com wrote:
>> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
>>
>> Implement a built-in command called cmd_fpv() that can be invoked as
>> follows:
>>
>> 	objtool fpv generate file.o
>>
>> The built-in command invokes decode_instructions() to walk each function
>> and decode the instructions of the function.
> 
> In commit b51277eb9775ce91 ("objtool: Ditch subcommands") Josh removed
> subcommands so this interface is going to need a rethink.

Thanks for mentioning this. I will sync my patchset to the latest and send out version 3.

Thanks!

Madhavan
Re: [RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder
Posted by Peter Zijlstra 2 months, 3 weeks ago
On Sun, May 29, 2022 at 09:49:44AM -0500, Madhavan T. Venkataraman wrote:
> 
> 
> On 5/24/22 09:09, Mark Brown wrote:
> > On Mon, May 23, 2022 at 07:16:26PM -0500, madvenka@linux.microsoft.com wrote:
> >> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
> >>
> >> Implement a built-in command called cmd_fpv() that can be invoked as
> >> follows:
> >>
> >> 	objtool fpv generate file.o
> >>
> >> The built-in command invokes decode_instructions() to walk each function
> >> and decode the instructions of the function.
> > 
> > In commit b51277eb9775ce91 ("objtool: Ditch subcommands") Josh removed
> > subcommands so this interface is going to need a rethink.
> 
> Thanks for mentioning this. I will sync my patchset to the latest and send out version 3.

Before you do; why are you duplicating lots of validate_branch() ? Why
can't you use the regular code to generate ORC data?

I'm really not happy about all this.
Re: [RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder
Posted by Madhavan T. Venkataraman 2 months, 2 weeks ago

On 5/30/22 02:51, Peter Zijlstra wrote:
> On Sun, May 29, 2022 at 09:49:44AM -0500, Madhavan T. Venkataraman wrote:
>>
>>
>> On 5/24/22 09:09, Mark Brown wrote:
>>> On Mon, May 23, 2022 at 07:16:26PM -0500, madvenka@linux.microsoft.com wrote:
>>>> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
>>>>
>>>> Implement a built-in command called cmd_fpv() that can be invoked as
>>>> follows:
>>>>
>>>> 	objtool fpv generate file.o
>>>>
>>>> The built-in command invokes decode_instructions() to walk each function
>>>> and decode the instructions of the function.
>>>
>>> In commit b51277eb9775ce91 ("objtool: Ditch subcommands") Josh removed
>>> subcommands so this interface is going to need a rethink.
>>
>> Thanks for mentioning this. I will sync my patchset to the latest and send out version 3.
> 
> Before you do; why are you duplicating lots of validate_branch() ? Why
> can't you use the regular code to generate ORC data?
> 
> I'm really not happy about all this.

Hi Peter,

I am preparing a detailed response to this explaining why I have not used validate_branch().
The short answer is that no validation is required for my approach. But I will send my detailed
response shortly.

Thanks.

Madhavan
Re: [RFC PATCH v2 09/20] objtool: arm64: Implement command to invoke the decoder
Posted by Madhavan T. Venkataraman 2 months, 1 week ago

On 6/1/22 17:45, Madhavan T. Venkataraman wrote:
> 
> 
> On 5/30/22 02:51, Peter Zijlstra wrote:
>> On Sun, May 29, 2022 at 09:49:44AM -0500, Madhavan T. Venkataraman wrote:
>>>
>>>
>>> On 5/24/22 09:09, Mark Brown wrote:
>>>> On Mon, May 23, 2022 at 07:16:26PM -0500, madvenka@linux.microsoft.com wrote:
>>>>> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
>>>>>
>>>>> Implement a built-in command called cmd_fpv() that can be invoked as
>>>>> follows:
>>>>>
>>>>> 	objtool fpv generate file.o
>>>>>
>>>>> The built-in command invokes decode_instructions() to walk each function
>>>>> and decode the instructions of the function.
>>>>
>>>> In commit b51277eb9775ce91 ("objtool: Ditch subcommands") Josh removed
>>>> subcommands so this interface is going to need a rethink.
>>>
>>> Thanks for mentioning this. I will sync my patchset to the latest and send out version 3.
>>
>> Before you do; why are you duplicating lots of validate_branch() ? Why
>> can't you use the regular code to generate ORC data?
>>
>> I'm really not happy about all this.
> 
> Hi Peter,
> 
> I am preparing a detailed response to this explaining why I have not used validate_branch().
> The short answer is that no validation is required for my approach. But I will send my detailed
> response shortly.
> 
> Thanks.
> 
> Madhavan

Sorry for the delay in responding to your comment. I had to make changes
to address it and complete testing.

I will address your comment in version 3. There are two parts to your comment:

- Why is validate_branch() not being used in Dynamic FP Validation?

	I will use it in version 3. See below.

- Why is the current code not being used to compute ORC?

	There are some differences in the CFI code between X86 and ARM64.
	So, I have defined handle_insn_ops() separately for the two in v3.

What I am doing in v3
=====================

I have discarded my own function (walk_code()) to walk instructions. Instead,
I have used validate_branch() per your comment.

However, my approach requires no validation. More on this below.

So, what I have done is to move all of the validation checks and actions into
their own functions. I define the functions separately for Static Stack
Validation (in check.c) and Dynamic Frame Pointer Validation (in fpv.c). The
two files are mutually exclusive.

The functions in fpv.c contain their own checks and actions.

	validate_insn_initial()		Initial checks.
	validate_insn_cfi()		CFI-related checks.
	validate_insn_alt()		Alternate instructions checks.
	validate_insn_return()		Return instruction checks.
	validate_insn_call()		Call/Call dynamic instruction checks.
	validate_insn_jump()		Jump instruction checks.
	validate_insn_jump_dynamic()	Jump Dynamic instruction checks.
	validate_insn_rest()		Checks for miscellaneous instructions.
	validate_ibt_insn()		IBT instruction checks.
	handle_insn_ops()		Update CFI from stack ops generated by
					the decoder.

validate_branch() looks like this now:

int validate_branch(struct objtool_file *file, struct symbol *func,
		    struct instruction *insn, struct insn_state state)
{
	struct instruction *next_insn, *prev_insn = NULL;
	struct section *sec;
	u8 visited;
	int ret;

	sec = insn->sec;

	while (1) {
		next_insn = next_insn_to_validate(file, insn);

		if (validate_insn_initial(file, func, insn, &ret))
			return ret;

		if (validate_insn_cfi(prev_insn, insn, &state, &visited, &ret))
			return ret;

		if (state.noinstr)
			state.instr += insn->instr;

		if (validate_insn_alt(file, func, insn, &state, &ret))
			return ret;

		if (handle_insn_ops(insn, next_insn, &state))
			return 1;

		switch (insn->type) {

		case INSN_RETURN:
			validate_insn_return(func, insn,
					     next_insn, &state, &ret);
			return ret;

		case INSN_CALL:
		case INSN_CALL_DYNAMIC:
			if (validate_insn_call(file, func, insn, &state, &ret))
				return ret;
			break;

		case INSN_JUMP_CONDITIONAL:
		case INSN_JUMP_UNCONDITIONAL:
			if (validate_insn_jump(file, func, insn, &state, &ret))
				return ret;
			break;

		case INSN_JUMP_DYNAMIC:
		case INSN_JUMP_DYNAMIC_CONDITIONAL:
			if (validate_insn_jump_dynamic(file, insn, next_insn,
						       &state, &ret)) {
				return ret;
			}
			break;

		default:
			if (validate_insn_rest(func, insn, next_insn,
					       &state, &ret)) {
				return ret;
			}
			break;
		}

		if (ibt)
			validate_ibt_insn(file, insn);

		if (insn->dead_end)
			return 0;

		if (!next_insn) {
			if (state.cfi.cfa.base == CFI_UNDEFINED)
				return 0;
			WARN("%s: unexpected end of section", sec->name);
			return 1;
		}

		prev_insn = insn;
		insn = next_insn;
	}

	return 0;
}

Why no validation?
==================

There are two approaches for reliable stacktrace.

1. Static Stack Validation (the current approach).

   Analyze the code statically and perform checks for ABI compliance and valid
   stack operations. If any warnings or errors are encountered, "fix" the
   kernel and/or the toolchain so the generated code conforms to Objtool's
   expectations.

2. Dynamic Frame Pointer Validation.

   Don't perform any validation of kernel code. Simply compute the SP and FP
   offsets at each instruction address based on the actual code. During unwind,
   compute a frame pointer from the offsets at each frame and validate the
   actual frame pointer with it. If an FP cannot be computed or the computed
   FP does not match the actual FP, consider the frame unreliable for unwind.

   Since the unwinder can clearly tell whether a frame is reliable or not,
   reliable stacktrace can be provided.

I am doing (2) in my patch series.

Different cases
===============

C Functions
-----------

I find that the compiler generates proper FP prolog and epilog for C functions.
The only exceptions I found are functions that have multiple code paths sharing
some instructions with differing CFIs. See CFI mismatch below. This mismatch
happens only for a very small percentage of the functions.

	Buggy code generated by compiler
	--------------------------------

	Even assuming that the compiler can sometimes generate code that does
	not follow ABI rules, it is still not a problem as the unwinder can
	do an FP match and tell whether some code is reliable for unwind or not.

Assembly Functions
------------------

There are two cases:

	SYM_CODE functions
	------------------

	Functions defined using the SYM_CODE_*() macros. 

	AFAICT, Objtool does not process these. These are low-level functions
	that don't follow any ABI rules. The ORC entries for these would be
	undefined. So, the unwinder will rightly consider them unreliable
	for unwind.

	SYM_FUNC functions
	------------------

	Functions defined using the SYM_FUNC_*() macros.

	These are supposed to have proper FP prologs and epilogs.

	At the moment, they don't for ARM64. The unwinder will consider these
	unreliable for unwind at the moment.

	That said, I am working on a separate patch series to add the prologs
	and epilogs to these functions (except in cases where functionality
	or performance would be affected). This is not required to support
	reliable stack trace. This is only to reduce potential retries during
	the livepatch process.

Functions without a proper FP prolog/epilog
-------------------------------------------

For leaf functions, the compiler may not generate FP prologs/epilogs for
performance reasons. In Dynamic FP Validation, the unwinder will recognize
these to be unreliable for unwind.

Assembly functions that don't have a proper FP prolog/epilog are treated like
leaf functions.

CFI mismatch
------------

This is based on actual code on ARM64.

Let us say there are two code paths in a function. The two code paths share
some instructions. If the SP and FP offsets are different in the two code paths,
the shared instructions will have a CFI mismatch. But this is not invalid or
buggy code. It is just a case that Objtool cannot handle because only one CFI
is associated with an instruction in Objtool.

In my approach, one CFI will be recorded. The other will be ignored. The
computed FP will match the actual FP in one code path. It will not match
in the other one. The unwinder will consider the former reliable and the
latter unreliable.

This happens only for a very small number of functions in the entire kernel.

That said, I am investigating the possibility of storing both in ORC entries
in a manner similar to alternate instructions. If this is feasible, then the
unwinder can do an FP match using any of these entries.

Thanks!

Madhavan