Skip to contentSkip to conversation

objtool: vmlinux.o and noinstr validation

PATCH Applied Peter Zijlstra 7 participants 89 messages Mar 24, 2020 – Apr 21, 2020

Subsystems (4)

v3 of 5 Applied Latest is v5 →

lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

v3 cover objtool: vmlinux.o and noinstr validation

Hi all,

Once more, more patches... up 7 from last time.

As should be familiar by now; these patches implement the noinstr (no-instrument) validation in objtool as requested by Thomas, to ensure critical code (entry for now, idle later) run no unexpected code.

Functions are marked with: noinstr, which implies notrace, noinline and sticks things in the .noinstr.text section. Such functions can then use instr_begin() and instr_end() to allow calls to code outside of this section in sanctioned areas.

Since a RELA does not include section information, we need to run objtool on a vmlinux.o which includes all relevant functions; so the first 'few' patches optimize objtool to allow running on vmlinux.o.

This all is starting to look good and barring any show-stoppers the plan is to get this merged soonish. There's one wobbly in patch 18, Josh any suggestions -- all I could come up with was ugleh.

author maintainer
#1 lore raw

PATCH v3 1/26 objtool: Introduce validate_return()

Trivial 'cleanup' to save one indentation level and match validate_call().

---
 tools/objtool/check.c |   64 ++++++++++++++++++++++++++++----------------------
 1 file changed, 36 insertions(+), 28 deletions(-)
tools/objtool/check.c +36 -28
@@ -1935,6 +1935,41 @@ static int validate_sibling_call(struct
 	return validate_call(insn, state);
 }
 
+static int validate_return(struct symbol *func, struct instruction *insn, struct insn_state *state)
+{
+	if (state->uaccess && !func_uaccess_safe(func)) {
+		WARN_FUNC("return with UACCESS enabled",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (!state->uaccess && func_uaccess_safe(func)) {
+		WARN_FUNC("return with UACCESS disabled from a UACCESS-safe function",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (state->df) {
+		WARN_FUNC("return with DF set",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (func && has_modified_stack_frame(state)) {
+		WARN_FUNC("return with modified stack frame",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (state->bp_scratch) {
+		WARN("%s uses BP as a scratch register",
+		     func->name);
+		return 1;
+	}
+
+	return 0;
+}
+
 /*
  * Follow the branch starting at the given instruction, and recursively follow
  * any other branches (jumps).  Meanwhile, track the frame pointer state at
@@ -2050,34 +2085,7 @@ static int validate_branch(struct objtoo
 		switch (insn->type) {
 
 		case INSN_RETURN:
-			if (state.uaccess && !func_uaccess_safe(func)) {
-				WARN_FUNC("return with UACCESS enabled", sec, insn->offset);
-				return 1;
-			}
-
-			if (!state.uaccess && func_uaccess_safe(func)) {
-				WARN_FUNC("return with UACCESS disabled from a UACCESS-safe function", sec, insn->offset);
-				return 1;
-			}
-
-			if (state.df) {
-				WARN_FUNC("return with DF set", sec, insn->offset);
-				return 1;
-			}
-
-			if (func && has_modified_stack_frame(&state)) {
-				WARN_FUNC("return with modified stack frame",
-					  sec, insn->offset);
-				return 1;
-			}
-
-			if (state.bp_scratch) {
-				WARN("%s uses BP as a scratch register",
-				     func->name);
-				return 1;
-			}
-
-			return 0;
+			return validate_return(func, insn, &state);
 
 		case INSN_CALL:
 		case INSN_CALL_DYNAMIC:
merge bot Applied
#3 lore raw

[tip: core/objtool] objtool: Introduce validate_return()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     a92e92d1a749e9bae9828f34f632d56ac2c6d2c3
Gitweb:        https://git.kernel.org/tip/a92e92d1a749e9bae9828f34f632d56ac2c6d2c3
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 10 Mar 2020 18:07:44 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:27 +01:00

objtool: Introduce validate_return()

Trivial 'cleanup' to save one indentation level and match validate_call().

---
 tools/objtool/check.c | 64 +++++++++++++++++++++++-------------------
 1 file changed, 36 insertions(+), 28 deletions(-)
tools/objtool/check.c +36 -28
index 6b6178e..da17b5a 100644
@@ -1975,6 +1975,41 @@ static int validate_sibling_call(struct instruction *insn, struct insn_state *st
 	return validate_call(insn, state);
 }
 
+static int validate_return(struct symbol *func, struct instruction *insn, struct insn_state *state)
+{
+	if (state->uaccess && !func_uaccess_safe(func)) {
+		WARN_FUNC("return with UACCESS enabled",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (!state->uaccess && func_uaccess_safe(func)) {
+		WARN_FUNC("return with UACCESS disabled from a UACCESS-safe function",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (state->df) {
+		WARN_FUNC("return with DF set",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (func && has_modified_stack_frame(state)) {
+		WARN_FUNC("return with modified stack frame",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
+	if (state->bp_scratch) {
+		WARN("%s uses BP as a scratch register",
+		     func->name);
+		return 1;
+	}
+
+	return 0;
+}
+
 /*
  * Follow the branch starting at the given instruction, and recursively follow
  * any other branches (jumps).  Meanwhile, track the frame pointer state at
@@ -2090,34 +2125,7 @@ static int validate_branch(struct objtool_file *file, struct symbol *func,
 		switch (insn->type) {
 
 		case INSN_RETURN:
-			if (state.uaccess && !func_uaccess_safe(func)) {
-				WARN_FUNC("return with UACCESS enabled", sec, insn->offset);
-				return 1;
-			}
-
-			if (!state.uaccess && func_uaccess_safe(func)) {
-				WARN_FUNC("return with UACCESS disabled from a UACCESS-safe function", sec, insn->offset);
-				return 1;
-			}
-
-			if (state.df) {
-				WARN_FUNC("return with DF set", sec, insn->offset);
-				return 1;
-			}
-
-			if (func && has_modified_stack_frame(&state)) {
-				WARN_FUNC("return with modified stack frame",
-					  sec, insn->offset);
-				return 1;
-			}
-
-			if (state.bp_scratch) {
-				WARN("%s uses BP as a scratch register",
-				     func->name);
-				return 1;
-			}
-
-			return 0;
+			return validate_return(func, insn, &state);
 
 		case INSN_CALL:
 		case INSN_CALL_DYNAMIC:
author maintainer
#4 lore raw

PATCH v3 2/26 objtool: Rename func_for_each_insn()

In reply to Peter Zijlstra

There is func_for_each_insn() and func_for_each_insn_all(), the both iterate the instructions, but the first uses symbol offset/length while the second uses insn->func.

Rename func_for_each_insn() to sym_for_eac_insn() because it iterates on symbol information.

---
 tools/objtool/check.c |   16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)
tools/objtool/check.c +8 -8
@@ -77,17 +77,17 @@ static struct instruction *next_insn_sam
 	     insn;							\
 	     insn = next_insn_same_func(file, insn))
 
-#define func_for_each_insn(file, func, insn)				\
-	for (insn = find_insn(file, func->sec, func->offset);		\
+#define sym_for_each_insn(file, sym, insn)				\
+	for (insn = find_insn(file, sym->sec, sym->offset);		\
 	     insn && &insn->list != &file->insn_list &&			\
-		insn->sec == func->sec &&				\
-		insn->offset < func->offset + func->len;		\
+		insn->sec == sym->sec &&				\
+		insn->offset < sym->offset + sym->len;			\
 	     insn = list_next_entry(insn, list))
 
-#define func_for_each_insn_continue_reverse(file, func, insn)		\
+#define sym_for_each_insn_continue_reverse(file, sym, insn)		\
 	for (insn = list_prev_entry(insn, list);			\
 	     &insn->list != &file->insn_list &&				\
-		insn->sec == func->sec && insn->offset >= func->offset;	\
+		insn->sec == sym->sec && insn->offset >= sym->offset;	\
 	     insn = list_prev_entry(insn, list))
 
 #define sec_for_each_insn_from(file, insn)				\
@@ -281,7 +281,7 @@ static int decode_instructions(struct ob
 				return -1;
 			}
 
-			func_for_each_insn(file, func, insn)
+			sym_for_each_insn(file, func, insn)
 				insn->func = func;
 		}
 	}
@@ -2024,7 +2024,7 @@ static int validate_branch(struct objtoo
 
 				i = insn;
 				save_insn = NULL;
-				func_for_each_insn_continue_reverse(file, func, i) {
+				sym_for_each_insn_continue_reverse(file, func, i) {
 					if (i->save) {
 						save_insn = i;
 						break;
Reviewed-by on v3 2/26
#5 lore raw

Re: [PATCH v3 02/26] objtool: Rename func_for_each_insn()

Quoted 5 lines · Peter Zijlstra

There is func_for_each_insn() and func_for_each_insn_all(), the both iterate the instructions, but the first uses symbol offset/length while the second uses insn->func.

Rename func_for_each_insn() to sym_for_eac_insn() because it iterates

I did not notice before, but there is a typo

s/sym_for_eac_insn/sym_for_each_insn/

Quoted 4 lines

on symbol information.

M

merge bot Applied
#6 lore raw

[tip: core/objtool] objtool: Rename func_for_each_insn()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     dbf4aeb0a494020644507459c2446e632cba1a05
Gitweb:        https://git.kernel.org/tip/dbf4aeb0a494020644507459c2446e632cba1a05
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 10 Mar 2020 18:24:59 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:27 +01:00

objtool: Rename func_for_each_insn()

There is func_for_each_insn() and func_for_each_insn_all(), the both iterate the instructions, but the first uses symbol offset/length while the second uses insn->func.

Rename func_for_each_insn() to sym_for_eac_insn() because it iterates on symbol information.

---
 tools/objtool/check.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)
tools/objtool/check.c +8 -8
index da17b5a..564ea1d 100644
@@ -77,17 +77,17 @@ static struct instruction *next_insn_same_func(struct objtool_file *file,
 	     insn;							\
 	     insn = next_insn_same_func(file, insn))
 
-#define func_for_each_insn(file, func, insn)				\
-	for (insn = find_insn(file, func->sec, func->offset);		\
+#define sym_for_each_insn(file, sym, insn)				\
+	for (insn = find_insn(file, sym->sec, sym->offset);		\
 	     insn && &insn->list != &file->insn_list &&			\
-		insn->sec == func->sec &&				\
-		insn->offset < func->offset + func->len;		\
+		insn->sec == sym->sec &&				\
+		insn->offset < sym->offset + sym->len;			\
 	     insn = list_next_entry(insn, list))
 
-#define func_for_each_insn_continue_reverse(file, func, insn)		\
+#define sym_for_each_insn_continue_reverse(file, sym, insn)		\
 	for (insn = list_prev_entry(insn, list);			\
 	     &insn->list != &file->insn_list &&				\
-		insn->sec == func->sec && insn->offset >= func->offset;	\
+		insn->sec == sym->sec && insn->offset >= sym->offset;	\
 	     insn = list_prev_entry(insn, list))
 
 #define sec_for_each_insn_from(file, insn)				\
@@ -286,7 +286,7 @@ static int decode_instructions(struct objtool_file *file)
 				return -1;
 			}
 
-			func_for_each_insn(file, func, insn)
+			sym_for_each_insn(file, func, insn)
 				insn->func = func;
 		}
 	}
@@ -2064,7 +2064,7 @@ static int validate_branch(struct objtool_file *file, struct symbol *func,
 
 				i = insn;
 				save_insn = NULL;
-				func_for_each_insn_continue_reverse(file, func, i) {
+				sym_for_each_insn_continue_reverse(file, func, i) {
 					if (i->save) {
 						save_insn = i;
 						break;
author maintainer
#7 lore raw

PATCH v3 3/26 objtool: Rename func_for_each_insn_all()

In reply to Peter Zijlstra

Now that func_for_each_insn() is available, rename func_for_each_insn_all(). This gets us:

sym_for_each_insn() - iterate on symbol offset/len func_for_each_insn() - iterate on insn->func

---
 tools/objtool/check.c |   12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
tools/objtool/check.c +6 -6
@@ -72,7 +72,7 @@ static struct instruction *next_insn_sam
 	return find_insn(file, func->cfunc->sec, func->cfunc->offset);
 }
 
-#define func_for_each_insn_all(file, func, insn)			\
+#define func_for_each_insn(file, func, insn)				\
 	for (insn = find_insn(file, func->sec, func->offset);		\
 	     insn;							\
 	     insn = next_insn_same_func(file, insn))
@@ -165,7 +165,7 @@ static bool __dead_end_function(struct o
 	if (!insn->func)
 		return false;
 
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		empty = false;
 
 		if (insn->type == INSN_RETURN)
@@ -180,7 +180,7 @@ static bool __dead_end_function(struct o
 	 * case, the function's dead-end status depends on whether the target
 	 * of the sibling call returns.
 	 */
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		if (is_sibling_call(insn)) {
 			struct instruction *dest = insn->jump_dest;
 
@@ -425,7 +425,7 @@ static void add_ignores(struct objtool_f
 			continue;
 		}
 
-		func_for_each_insn_all(file, func, insn)
+		func_for_each_insn(file, func, insn)
 			insn->ignore = true;
 	}
 }
@@ -1082,7 +1082,7 @@ static void mark_func_jump_tables(struct
 	struct instruction *insn, *last = NULL;
 	struct rela *rela;
 
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		if (!last)
 			last = insn;
 
@@ -1117,7 +1117,7 @@ static int add_func_jump_tables(struct o
 	struct instruction *insn;
 	int ret;
 
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		if (!insn->jump_table)
 			continue;
 
Reviewed-by on v3 3/26
#8 lore raw

Re: [PATCH v3 03/26] objtool: Rename func_for_each_insn_all()

Quoted 8 lines · Peter Zijlstra

Now that func_for_each_insn() is available, rename func_for_each_insn_all(). This gets us:

sym_for_each_insn() - iterate on symbol offset/len func_for_each_insn() - iterate on insn->func

M

merge bot Applied
#9 lore raw

[tip: core/objtool] objtool: Rename func_for_each_insn_all()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     f0f70adb78108a0cbc321a07133cd78ea4f84699
Gitweb:        https://git.kernel.org/tip/f0f70adb78108a0cbc321a07133cd78ea4f84699
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 10 Mar 2020 18:27:24 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:27 +01:00

objtool: Rename func_for_each_insn_all()

Now that func_for_each_insn() is available, rename func_for_each_insn_all(). This gets us:

sym_for_each_insn() - iterate on symbol offset/len func_for_each_insn() - iterate on insn->func

---
 tools/objtool/check.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
tools/objtool/check.c +6 -6
index 564ea1d..43f7d3c 100644
@@ -72,7 +72,7 @@ static struct instruction *next_insn_same_func(struct objtool_file *file,
 	return find_insn(file, func->cfunc->sec, func->cfunc->offset);
 }
 
-#define func_for_each_insn_all(file, func, insn)			\
+#define func_for_each_insn(file, func, insn)				\
 	for (insn = find_insn(file, func->sec, func->offset);		\
 	     insn;							\
 	     insn = next_insn_same_func(file, insn))
@@ -170,7 +170,7 @@ static bool __dead_end_function(struct objtool_file *file, struct symbol *func,
 	if (!insn->func)
 		return false;
 
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		empty = false;
 
 		if (insn->type == INSN_RETURN)
@@ -185,7 +185,7 @@ static bool __dead_end_function(struct objtool_file *file, struct symbol *func,
 	 * case, the function's dead-end status depends on whether the target
 	 * of the sibling call returns.
 	 */
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		if (is_sibling_call(insn)) {
 			struct instruction *dest = insn->jump_dest;
 
@@ -430,7 +430,7 @@ static void add_ignores(struct objtool_file *file)
 			continue;
 		}
 
-		func_for_each_insn_all(file, func, insn)
+		func_for_each_insn(file, func, insn)
 			insn->ignore = true;
 	}
 }
@@ -1122,7 +1122,7 @@ static void mark_func_jump_tables(struct objtool_file *file,
 	struct instruction *insn, *last = NULL;
 	struct rela *rela;
 
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		if (!last)
 			last = insn;
 
@@ -1157,7 +1157,7 @@ static int add_func_jump_tables(struct objtool_file *file,
 	struct instruction *insn;
 	int ret;
 
-	func_for_each_insn_all(file, func, insn) {
+	func_for_each_insn(file, func, insn) {
 		if (!insn->jump_table)
 			continue;
 
author maintainer
#10 lore raw

PATCH v3 4/26 x86/kexec: Use RIP relative addressing

In reply to Peter Zijlstra

Normally identity_mapped is not visible to objtool, due to:

  arch/x86/kernel/Makefile:OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o := y

However, when we want to run objtool on vmlinux.o there is no hiding it:

vmlinux.o: warning: objtool: .text+0x4c0f1: unsupported intra-function call

Replace the (i386 inspired) pattern:

call 1f
1: popq %r8

	subq $(1b - relocate_kernel), %r8

With a x86_64 RIP-relative LEA:

leaq relocate_kernel(%rip), %r8

---
 arch/x86/kernel/relocate_kernel_64.S |    5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
arch/x86/kernel/relocate_kernel_64.S +1 -4
@@ -196,10 +196,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_ma
 
 	/* get the re-entry point of the peer system */
 	movq	0(%rsp), %rbp
-	call	1f
-1:
-	popq	%r8
-	subq	$(1b - relocate_kernel), %r8
+	leaq	relocate_kernel(%rip), %r8
 	movq	CP_PA_SWAP_PAGE(%r8), %r10
 	movq	CP_PA_BACKUP_PAGES_MAP(%r8), %rdi
 	movq	CP_PA_TABLE_PAGE(%r8), %rax
Reviewed-by on v3 4/26
#11 lore raw

Re: [PATCH v3 04/26] x86/kexec: Use RIP relative addressing

Quoted 15 lines · Peter Zijlstra

Normally identity_mapped is not visible to objtool, due to:

  arch/x86/kernel/Makefile:OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o := y

However, when we want to run objtool on vmlinux.o there is no hiding it:

vmlinux.o: warning: objtool: .text+0x4c0f1: unsupported intra-function call

Replace the (i386 inspired) pattern:

call 1f
1: popq %r8

	subq $(1b - relocate_kernel), %r8
Quoted 7 lines

With a x86_64 RIP-relative LEA:

leaq relocate_kernel(%rip), %r8

M

merge bot Applied
#12 lore raw

[tip: core/objtool] x86/kexec: Use RIP relative addressing

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     fc8bd77d6476d7733ace9e03093b4acaee6e0605
Gitweb:        https://git.kernel.org/tip/fc8bd77d6476d7733ace9e03093b4acaee6e0605
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Mon, 16 Mar 2020 10:13:45 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:27 +01:00

x86/kexec: Use RIP relative addressing

Normally identity_mapped is not visible to objtool, due to:

  arch/x86/kernel/Makefile:OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o := y

However, when we want to run objtool on vmlinux.o there is no hiding it:

vmlinux.o: warning: objtool: .text+0x4c0f1: unsupported intra-function call

Replace the (i386 inspired) pattern:

call 1f
1: popq %r8

	subq $(1b - relocate_kernel), %r8

With a x86_64 RIP-relative LEA:

leaq relocate_kernel(%rip), %r8

---
 arch/x86/kernel/relocate_kernel_64.S | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
arch/x86/kernel/relocate_kernel_64.S +1 -4
index ef3ba99..cc5c8b9 100644
@@ -196,10 +196,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_mapped)
 
 	/* get the re-entry point of the peer system */
 	movq	0(%rsp), %rbp
-	call	1f
-1:
-	popq	%r8
-	subq	$(1b - relocate_kernel), %r8
+	leaq	relocate_kernel(%rip), %r8
 	movq	CP_PA_SWAP_PAGE(%r8), %r10
 	movq	CP_PA_BACKUP_PAGES_MAP(%r8), %rdi
 	movq	CP_PA_TABLE_PAGE(%r8), %rax
author maintainer
#13 lore raw

PATCH v3 5/26 x86/kexec: Make relocate_kernel_64.S objtool clean

In reply to Peter Zijlstra

Having fixed the biggest objtool issue in this file; fix up the rest and remove the exception.

---
 arch/x86/kernel/Makefile             |    1 -
 arch/x86/kernel/relocate_kernel_64.S |    7 +++++++
 2 files changed, 7 insertions(+), 1 deletion(-)
arch/x86/kernel/Makefile +0 -1
@@ -32,7 +32,6 @@ KASAN_SANITIZE_paravirt.o				:= n
 # by several compilation units. To be safe, disable all instrumentation.
 KCSAN_SANITIZE := n
 
-OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o	:= y
 OBJECT_FILES_NON_STANDARD_test_nx.o			:= y
 OBJECT_FILES_NON_STANDARD_paravirt_patch.o		:= y
 
arch/x86/kernel/relocate_kernel_64.S +7 -0
@@ -9,6 +9,8 @@
 #include <asm/kexec.h>
 #include <asm/processor-flags.h>
 #include <asm/pgtable_types.h>
+#include <asm/nospec-branch.h>
+#include <asm/unwind_hints.h>
 
 /*
  * Must be relocatable PIC code callable as a C function
@@ -39,6 +41,7 @@
 	.align PAGE_SIZE
 	.code64
 SYM_CODE_START_NOALIGN(relocate_kernel)
+	UNWIND_HINT_EMPTY
 	/*
 	 * %rdi indirection_page
 	 * %rsi page_list
@@ -105,6 +108,7 @@ SYM_CODE_START_NOALIGN(relocate_kernel)
 SYM_CODE_END(relocate_kernel)
 
 SYM_CODE_START_LOCAL_NOALIGN(identity_mapped)
+	UNWIND_HINT_EMPTY
 	/* set return address to 0 if not preserving context */
 	pushq	$0
 	/* store the start address on the stack */
@@ -192,6 +196,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_ma
 1:
 	popq	%rdx
 	leaq	PAGE_SIZE(%r10), %rsp
+	ANNOTATE_RETPOLINE_SAFE
 	call	*%rdx
 
 	/* get the re-entry point of the peer system */
@@ -209,6 +214,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_ma
 SYM_CODE_END(identity_mapped)
 
 SYM_CODE_START_LOCAL_NOALIGN(virtual_mapped)
+	UNWIND_HINT_EMPTY
 	movq	RSP(%r8), %rsp
 	movq	CR4(%r8), %rax
 	movq	%rax, %cr4
@@ -230,6 +236,7 @@ SYM_CODE_END(virtual_mapped)
 
 	/* Do the copies */
 SYM_CODE_START_LOCAL_NOALIGN(swap_pages)
+	UNWIND_HINT_EMPTY
 	movq	%rdi, %rcx 	/* Put the page_list in %rcx */
 	xorl	%edi, %edi
 	xorl	%esi, %esi
merge bot Applied
#16 lore raw

[tip: core/objtool] x86/kexec: Make relocate_kernel_64.S objtool clean

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     36cc552055a5f95bab479533b4ebbad6a6cea0e1
Gitweb:        https://git.kernel.org/tip/36cc552055a5f95bab479533b4ebbad6a6cea0e1
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 24 Mar 2020 15:35:42 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:28 +01:00

x86/kexec: Make relocate_kernel_64.S objtool clean

Having fixed the biggest objtool issue in this file; fix up the rest and remove the exception.

---
 arch/x86/kernel/Makefile             | 1 -
 arch/x86/kernel/relocate_kernel_64.S | 7 +++++++
 2 files changed, 7 insertions(+), 1 deletion(-)
arch/x86/kernel/Makefile +0 -1
index 9b294c1..8be5926 100644
@@ -28,7 +28,6 @@ KASAN_SANITIZE_dumpstack_$(BITS).o			:= n
 KASAN_SANITIZE_stacktrace.o				:= n
 KASAN_SANITIZE_paravirt.o				:= n
 
-OBJECT_FILES_NON_STANDARD_relocate_kernel_$(BITS).o	:= y
 OBJECT_FILES_NON_STANDARD_test_nx.o			:= y
 OBJECT_FILES_NON_STANDARD_paravirt_patch.o		:= y
 
arch/x86/kernel/relocate_kernel_64.S +7 -0
index cc5c8b9..a4d9a26 100644
@@ -9,6 +9,8 @@
 #include <asm/kexec.h>
 #include <asm/processor-flags.h>
 #include <asm/pgtable_types.h>
+#include <asm/nospec-branch.h>
+#include <asm/unwind_hints.h>
 
 /*
  * Must be relocatable PIC code callable as a C function
@@ -39,6 +41,7 @@
 	.align PAGE_SIZE
 	.code64
 SYM_CODE_START_NOALIGN(relocate_kernel)
+	UNWIND_HINT_EMPTY
 	/*
 	 * %rdi indirection_page
 	 * %rsi page_list
@@ -105,6 +108,7 @@ SYM_CODE_START_NOALIGN(relocate_kernel)
 SYM_CODE_END(relocate_kernel)
 
 SYM_CODE_START_LOCAL_NOALIGN(identity_mapped)
+	UNWIND_HINT_EMPTY
 	/* set return address to 0 if not preserving context */
 	pushq	$0
 	/* store the start address on the stack */
@@ -192,6 +196,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_mapped)
 1:
 	popq	%rdx
 	leaq	PAGE_SIZE(%r10), %rsp
+	ANNOTATE_RETPOLINE_SAFE
 	call	*%rdx
 
 	/* get the re-entry point of the peer system */
@@ -209,6 +214,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_mapped)
 SYM_CODE_END(identity_mapped)
 
 SYM_CODE_START_LOCAL_NOALIGN(virtual_mapped)
+	UNWIND_HINT_EMPTY
 	movq	RSP(%r8), %rsp
 	movq	CR4(%r8), %rax
 	movq	%rax, %cr4
@@ -230,6 +236,7 @@ SYM_CODE_END(virtual_mapped)
 
 	/* Do the copies */
 SYM_CODE_START_LOCAL_NOALIGN(swap_pages)
+	UNWIND_HINT_EMPTY
 	movq	%rdi, %rcx 	/* Put the page_list in %rcx */
 	xorl	%edi, %edi
 	xorl	%esi, %esi
author maintainer
#17 lore raw

PATCH v3 6/26 objtool: Optimize find_symbol_by_index()

In reply to Peter Zijlstra

The symbol index is object wide, not per section, so it makes no sense to have the symbol_hash be part of the section object. By moving it to the elf object we avoid the linear sections iteration.

This reduces the runtime of objtool on vmlinux.o from over 3 hours (I gave up) to a few minutes. The defconfig vmlinux.o has around 20k sections.

---
 tools/objtool/elf.c |   13 +++++--------
 tools/objtool/elf.h |    3 +--
 2 files changed, 6 insertions(+), 10 deletions(-)
tools/objtool/elf.c +5 -8
@@ -46,13 +46,11 @@ static struct section *find_section_by_i
 
 static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 {
-	struct section *sec;
 	struct symbol *sym;
 
-	list_for_each_entry(sec, &elf->sections, list)
-		hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
-			if (sym->idx == idx)
-				return sym;
+	hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+		if (sym->idx == idx)
+			return sym;
 
 	return NULL;
 }
@@ -166,7 +164,6 @@ static int read_sections(struct elf *elf
 		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);
 
@@ -299,7 +296,7 @@ static int read_symbols(struct elf *elf)
 		}
 		sym->alias = alias;
 		list_add(&sym->list, entry);
-		hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
+		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
 	}
 
 	/* Create parent/child links for any cold subfunctions */
@@ -425,6 +422,7 @@ struct elf *elf_read(const char *name, i
 	}
 	memset(elf, 0, sizeof(*elf));
 
+	hash_init(elf->symbol_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -486,7 +484,6 @@ struct section *elf_create_section(struc
 	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);
 
tools/objtool/elf.h +1 -2
@@ -27,7 +27,6 @@ struct section {
 	struct list_head list;
 	GElf_Shdr sh;
 	struct list_head symbol_list;
-	DECLARE_HASHTABLE(symbol_hash, 8);
 	struct list_head rela_list;
 	DECLARE_HASHTABLE(rela_hash, 16);
 	struct section *base, *rela;
@@ -71,7 +70,7 @@ struct elf {
 	int fd;
 	char *name;
 	struct list_head sections;
-	DECLARE_HASHTABLE(rela_hash, 16);
+	DECLARE_HASHTABLE(symbol_hash, 20);
 };
 
 
Reviewed-by on v3 6/26
#18 lore raw

Re: [PATCH v3 06/26] objtool: Optimize find_symbol_by_index()

Quoted 10 lines · Peter Zijlstra

The symbol index is object wide, not per section, so it makes no sense to have the symbol_hash be part of the section object. By moving it to the elf object we avoid the linear sections iteration.

This reduces the runtime of objtool on vmlinux.o from over 3 hours (I gave up) to a few minutes. The defconfig vmlinux.o has around 20k sections.

M

merge bot Applied
#19 lore raw

[tip: core/objtool] objtool: Optimize find_symbol_by_index()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     65fb11a7f6aeae678043738d06248a4e21f4e4e4
Gitweb:        https://git.kernel.org/tip/65fb11a7f6aeae678043738d06248a4e21f4e4e4
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 10 Mar 2020 18:39:45 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:28 +01:00

objtool: Optimize find_symbol_by_index()

The symbol index is object wide, not per section, so it makes no sense to have the symbol_hash be part of the section object. By moving it to the elf object we avoid the linear sections iteration.

This reduces the runtime of objtool on vmlinux.o from over 3 hours (I gave up) to a few minutes. The defconfig vmlinux.o has around 20k sections.

---
 tools/objtool/elf.c | 13 +++++--------
 tools/objtool/elf.h |  3 +--
 2 files changed, 6 insertions(+), 10 deletions(-)
tools/objtool/elf.c +5 -8
index cc4601c..b188b3e 100644
@@ -46,13 +46,11 @@ static struct section *find_section_by_index(struct elf *elf,
 
 static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 {
-	struct section *sec;
 	struct symbol *sym;
 
-	list_for_each_entry(sec, &elf->sections, list)
-		hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
-			if (sym->idx == idx)
-				return sym;
+	hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+		if (sym->idx == idx)
+			return sym;
 
 	return NULL;
 }
@@ -166,7 +164,6 @@ static int read_sections(struct elf *elf)
 		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);
 
@@ -299,7 +296,7 @@ static int read_symbols(struct elf *elf)
 		}
 		sym->alias = alias;
 		list_add(&sym->list, entry);
-		hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
+		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
 	}
 
 	/* Create parent/child links for any cold subfunctions */
@@ -425,6 +422,7 @@ struct elf *elf_read(const char *name, int flags)
 	}
 	memset(elf, 0, sizeof(*elf));
 
+	hash_init(elf->symbol_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -486,7 +484,6 @@ struct section *elf_create_section(struct elf *elf, const char *name,
 	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);
 
tools/objtool/elf.h +1 -2
index a196325..1222980 100644
@@ -27,7 +27,6 @@ struct section {
 	struct list_head list;
 	GElf_Shdr sh;
 	struct list_head symbol_list;
-	DECLARE_HASHTABLE(symbol_hash, 8);
 	struct list_head rela_list;
 	DECLARE_HASHTABLE(rela_hash, 16);
 	struct section *base, *rela;
@@ -71,7 +70,7 @@ struct elf {
 	int fd;
 	char *name;
 	struct list_head sections;
-	DECLARE_HASHTABLE(rela_hash, 16);
+	DECLARE_HASHTABLE(symbol_hash, 20);
 };
 
 
author maintainer
#20 lore raw

PATCH v3 7/26 objtool: Add a statistics mode

In reply to Peter Zijlstra

Have it print a few numbers which can be used to size the hashtables.

---
 tools/objtool/builtin-check.c |    3 ++-
 tools/objtool/builtin.h       |    2 +-
 tools/objtool/check.c         |    5 +++++
 tools/objtool/elf.c           |   18 +++++++++++++++++-
 4 files changed, 25 insertions(+), 3 deletions(-)
tools/objtool/builtin-check.c +2 -1
@@ -17,7 +17,7 @@
 #include "builtin.h"
 #include "check.h"
 
-bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess;
+bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
 
 static const char * const check_usage[] = {
 	"objtool check [<options>] file.o",
@@ -31,6 +31,7 @@ const struct option check_options[] = {
 	OPT_BOOLEAN('m', "module", &module, "Indicates the object will be part of a kernel module"),
 	OPT_BOOLEAN('b', "backtrace", &backtrace, "unwind on error"),
 	OPT_BOOLEAN('a', "uaccess", &uaccess, "enable uaccess checking"),
+	OPT_BOOLEAN('s', "stats", &stats, "print statistics"),
 	OPT_END(),
 };
 
tools/objtool/builtin.h +1 -1
@@ -8,7 +8,7 @@
 #include <subcmd/parse-options.h>
 
 extern const struct option check_options[];
-extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess;
+extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
 
 extern int cmd_check(int argc, const char **argv);
 extern int cmd_orc(int argc, const char **argv);
tools/objtool/check.c +5 -0
@@ -239,6 +239,7 @@ static int decode_instructions(struct ob
 	struct symbol *func;
 	unsigned long offset;
 	struct instruction *insn;
+	unsigned long nr_insns = 0;
 	int ret;
 
 	for_each_sec(file, sec) {
@@ -274,6 +275,7 @@ static int decode_instructions(struct ob
 
 			hash_add(file->insn_hash, &insn->hash, insn->offset);
 			list_add_tail(&insn->list, &file->insn_list);
+			nr_insns++;
 		}
 
 		list_for_each_entry(func, &sec->symbol_list, list) {
@@ -291,6 +293,9 @@ static int decode_instructions(struct ob
 		}
 	}
 
+	if (stats)
+		printf("nr_insns: %lu\n", nr_insns);
+
 	return 0;
 
 err:
tools/objtool/elf.c +17 -1
@@ -15,6 +15,7 @@
 #include <string.h>
 #include <unistd.h>
 #include <errno.h>
+#include "builtin.h"
 
 #include "elf.h"
 #include "warn.h"
@@ -202,6 +203,9 @@ static int read_sections(struct elf *elf
 		sec->len = sec->sh.sh_size;
 	}
 
+	if (stats)
+		printf("nr_sections: %lu\n", (unsigned long)sections_nr);
+
 	/* sanity check, one more call to elf_nextscn() should return NULL */
 	if (elf_nextscn(elf->elf, s)) {
 		WARN("section entry mismatch");
@@ -299,6 +303,9 @@ static int read_symbols(struct elf *elf)
 		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
 	}
 
+	if (stats)
+		printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
+
 	/* Create parent/child links for any cold subfunctions */
 	list_for_each_entry(sec, &elf->sections, list) {
 		list_for_each_entry(sym, &sec->symbol_list, list) {
@@ -360,6 +367,7 @@ static int read_relas(struct elf *elf)
 	struct rela *rela;
 	int i;
 	unsigned int symndx;
+	unsigned long nr_rela, max_rela = 0, tot_rela = 0;
 
 	list_for_each_entry(sec, &elf->sections, list) {
 		if (sec->sh.sh_type != SHT_RELA)
@@ -374,6 +382,7 @@ static int read_relas(struct elf *elf)
 
 		sec->base->rela = sec;
 
+		nr_rela = 0;
 		for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
 			rela = malloc(sizeof(*rela));
 			if (!rela) {
@@ -401,8 +410,15 @@ static int read_relas(struct elf *elf)
 
 			list_add_tail(&rela->list, &sec->rela_list);
 			hash_add(sec->rela_hash, &rela->hash, rela->offset);
-
+			nr_rela++;
 		}
+		max_rela = max(max_rela, nr_rela);
+		tot_rela += nr_rela;
+	}
+
+	if (stats) {
+		printf("max_rela: %lu\n", max_rela);
+		printf("tot_rela: %lu\n", tot_rela);
 	}
 
 	return 0;
merge bot Applied
#22 lore raw

[tip: core/objtool] objtool: Add a statistics mode

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     1e11f3fdc326d7466e43185ea943b6156143387c
Gitweb:        https://git.kernel.org/tip/1e11f3fdc326d7466e43185ea943b6156143387c
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 09:26:29 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:28 +01:00

objtool: Add a statistics mode

Have it print a few numbers which can be used to size the hashtables.

---
 tools/objtool/builtin-check.c |  3 ++-
 tools/objtool/builtin.h       |  2 +-
 tools/objtool/check.c         |  5 +++++
 tools/objtool/elf.c           | 18 +++++++++++++++++-
 4 files changed, 25 insertions(+), 3 deletions(-)
tools/objtool/builtin-check.c +2 -1
index c807984..10fbe75 100644
@@ -17,7 +17,7 @@
 #include "builtin.h"
 #include "check.h"
 
-bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess;
+bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
 
 static const char * const check_usage[] = {
 	"objtool check [<options>] file.o",
@@ -31,6 +31,7 @@ const struct option check_options[] = {
 	OPT_BOOLEAN('m', "module", &module, "Indicates the object will be part of a kernel module"),
 	OPT_BOOLEAN('b', "backtrace", &backtrace, "unwind on error"),
 	OPT_BOOLEAN('a', "uaccess", &uaccess, "enable uaccess checking"),
+	OPT_BOOLEAN('s', "stats", &stats, "print statistics"),
 	OPT_END(),
 };
 
tools/objtool/builtin.h +1 -1
index a32736f..0b90790 100644
@@ -8,7 +8,7 @@
 #include <subcmd/parse-options.h>
 
 extern const struct option check_options[];
-extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess;
+extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
 
 extern int cmd_check(int argc, const char **argv);
 extern int cmd_orc(int argc, const char **argv);
tools/objtool/check.c +5 -0
index 43f7d3c..6df1bae 100644
@@ -239,6 +239,7 @@ static int decode_instructions(struct objtool_file *file)
 	struct symbol *func;
 	unsigned long offset;
 	struct instruction *insn;
+	unsigned long nr_insns = 0;
 	int ret;
 
 	for_each_sec(file, sec) {
@@ -274,6 +275,7 @@ static int decode_instructions(struct objtool_file *file)
 
 			hash_add(file->insn_hash, &insn->hash, insn->offset);
 			list_add_tail(&insn->list, &file->insn_list);
+			nr_insns++;
 		}
 
 		list_for_each_entry(func, &sec->symbol_list, list) {
@@ -291,6 +293,9 @@ static int decode_instructions(struct objtool_file *file)
 		}
 	}
 
+	if (stats)
+		printf("nr_insns: %lu\n", nr_insns);
+
 	return 0;
 
 err:
tools/objtool/elf.c +17 -1
index b188b3e..ff29306 100644
@@ -15,6 +15,7 @@
 #include <string.h>
 #include <unistd.h>
 #include <errno.h>
+#include "builtin.h"
 
 #include "elf.h"
 #include "warn.h"
@@ -202,6 +203,9 @@ static int read_sections(struct elf *elf)
 		sec->len = sec->sh.sh_size;
 	}
 
+	if (stats)
+		printf("nr_sections: %lu\n", (unsigned long)sections_nr);
+
 	/* sanity check, one more call to elf_nextscn() should return NULL */
 	if (elf_nextscn(elf->elf, s)) {
 		WARN("section entry mismatch");
@@ -299,6 +303,9 @@ static int read_symbols(struct elf *elf)
 		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
 	}
 
+	if (stats)
+		printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
+
 	/* Create parent/child links for any cold subfunctions */
 	list_for_each_entry(sec, &elf->sections, list) {
 		list_for_each_entry(sym, &sec->symbol_list, list) {
@@ -360,6 +367,7 @@ static int read_relas(struct elf *elf)
 	struct rela *rela;
 	int i;
 	unsigned int symndx;
+	unsigned long nr_rela, max_rela = 0, tot_rela = 0;
 
 	list_for_each_entry(sec, &elf->sections, list) {
 		if (sec->sh.sh_type != SHT_RELA)
@@ -374,6 +382,7 @@ static int read_relas(struct elf *elf)
 
 		sec->base->rela = sec;
 
+		nr_rela = 0;
 		for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
 			rela = malloc(sizeof(*rela));
 			if (!rela) {
@@ -401,8 +410,15 @@ static int read_relas(struct elf *elf)
 
 			list_add_tail(&rela->list, &sec->rela_list);
 			hash_add(sec->rela_hash, &rela->hash, rela->offset);
-
+			nr_rela++;
 		}
+		max_rela = max(max_rela, nr_rela);
+		tot_rela += nr_rela;
+	}
+
+	if (stats) {
+		printf("max_rela: %lu\n", max_rela);
+		printf("tot_rela: %lu\n", tot_rela);
 	}
 
 	return 0;
author maintainer
#23 lore raw

PATCH v3 8/26 objtool: Optimize find_section_by_index()

In reply to Peter Zijlstra

In order to avoid a linear search (over 20k entries), add an section_hash to the elf object.

This reduces objtool on vmlinux.o from a few minutes to around 45 seconds.

---
 tools/objtool/elf.c |   13 ++++++++-----
 tools/objtool/elf.h |    2 ++
 2 files changed, 10 insertions(+), 5 deletions(-)
tools/objtool/elf.c +8 -5
@@ -38,7 +38,7 @@ static struct section *find_section_by_i
 {
 	struct section *sec;
 
-	list_for_each_entry(sec, &elf->sections, list)
+	hash_for_each_possible(elf->section_hash, sec, hash, idx)
 		if (sec->idx == idx)
 			return sec;
 
@@ -166,8 +166,6 @@ static int read_sections(struct elf *elf
 		INIT_LIST_HEAD(&sec->rela_list);
 		hash_init(sec->rela_hash);
 
-		list_add_tail(&sec->list, &elf->sections);
-
 		s = elf_getscn(elf->elf, i);
 		if (!s) {
 			WARN_ELF("elf_getscn");
@@ -201,6 +199,9 @@ static int read_sections(struct elf *elf
 			}
 		}
 		sec->len = sec->sh.sh_size;
+
+		list_add_tail(&sec->list, &elf->sections);
+		hash_add(elf->section_hash, &sec->hash, sec->idx);
 	}
 
 	if (stats)
@@ -439,6 +440,7 @@ struct elf *elf_read(const char *name, i
 	memset(elf, 0, sizeof(*elf));
 
 	hash_init(elf->symbol_hash);
+	hash_init(elf->section_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -501,8 +503,6 @@ struct section *elf_create_section(struc
 	INIT_LIST_HEAD(&sec->rela_list);
 	hash_init(sec->rela_hash);
 
-	list_add_tail(&sec->list, &elf->sections);
-
 	s = elf_newscn(elf->elf);
 	if (!s) {
 		WARN_ELF("elf_newscn");
@@ -579,6 +579,9 @@ struct section *elf_create_section(struc
 	shstrtab->len += strlen(name) + 1;
 	shstrtab->changed = true;
 
+	list_add_tail(&sec->list, &elf->sections);
+	hash_add(elf->section_hash, &sec->hash, sec->idx);
+
 	return sec;
 }
 
tools/objtool/elf.h +2 -0
@@ -25,6 +25,7 @@
 
 struct section {
 	struct list_head list;
+	struct hlist_node hash;
 	GElf_Shdr sh;
 	struct list_head symbol_list;
 	struct list_head rela_list;
@@ -71,6 +72,7 @@ struct elf {
 	char *name;
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
+	DECLARE_HASHTABLE(section_hash, 16);
 };
 
 
merge bot Applied
#25 lore raw

[tip: core/objtool] objtool: Optimize find_section_by_index()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     530389968739883a61192767e1c215653ba4ba2b
Gitweb:        https://git.kernel.org/tip/530389968739883a61192767e1c215653ba4ba2b
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 10 Mar 2020 18:43:35 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:28 +01:00

objtool: Optimize find_section_by_index()

In order to avoid a linear search (over 20k entries), add an section_hash to the elf object.

This reduces objtool on vmlinux.o from a few minutes to around 45 seconds.

---
 tools/objtool/elf.c | 13 ++++++++-----
 tools/objtool/elf.h |  2 ++
 2 files changed, 10 insertions(+), 5 deletions(-)
tools/objtool/elf.c +8 -5
index ff29306..9007713 100644
@@ -38,7 +38,7 @@ static struct section *find_section_by_index(struct elf *elf,
 {
 	struct section *sec;
 
-	list_for_each_entry(sec, &elf->sections, list)
+	hash_for_each_possible(elf->section_hash, sec, hash, idx)
 		if (sec->idx == idx)
 			return sec;
 
@@ -166,8 +166,6 @@ static int read_sections(struct elf *elf)
 		INIT_LIST_HEAD(&sec->rela_list);
 		hash_init(sec->rela_hash);
 
-		list_add_tail(&sec->list, &elf->sections);
-
 		s = elf_getscn(elf->elf, i);
 		if (!s) {
 			WARN_ELF("elf_getscn");
@@ -201,6 +199,9 @@ static int read_sections(struct elf *elf)
 			}
 		}
 		sec->len = sec->sh.sh_size;
+
+		list_add_tail(&sec->list, &elf->sections);
+		hash_add(elf->section_hash, &sec->hash, sec->idx);
 	}
 
 	if (stats)
@@ -439,6 +440,7 @@ struct elf *elf_read(const char *name, int flags)
 	memset(elf, 0, sizeof(*elf));
 
 	hash_init(elf->symbol_hash);
+	hash_init(elf->section_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -501,8 +503,6 @@ struct section *elf_create_section(struct elf *elf, const char *name,
 	INIT_LIST_HEAD(&sec->rela_list);
 	hash_init(sec->rela_hash);
 
-	list_add_tail(&sec->list, &elf->sections);
-
 	s = elf_newscn(elf->elf);
 	if (!s) {
 		WARN_ELF("elf_newscn");
@@ -579,6 +579,9 @@ struct section *elf_create_section(struct elf *elf, const char *name,
 	shstrtab->len += strlen(name) + 1;
 	shstrtab->changed = true;
 
+	list_add_tail(&sec->list, &elf->sections);
+	hash_add(elf->section_hash, &sec->hash, sec->idx);
+
 	return sec;
 }
 
tools/objtool/elf.h +2 -0
index 1222980..8c272eb 100644
@@ -25,6 +25,7 @@
 
 struct section {
 	struct list_head list;
+	struct hlist_node hash;
 	GElf_Shdr sh;
 	struct list_head symbol_list;
 	struct list_head rela_list;
@@ -71,6 +72,7 @@ struct elf {
 	char *name;
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
+	DECLARE_HASHTABLE(section_hash, 16);
 };
 
 
author maintainer
#26 lore raw

PATCH v3 9/26 objtool: Optimize find_section_by_name()

In reply to Peter Zijlstra

In order to avoid yet another linear search of (20k) sections, add a name based hash.

This reduces objtool runtime on vmlinux.o by some 10s to around 35s.

---
 tools/objtool/elf.c |   10 +++++++++-
 tools/objtool/elf.h |    3 +++
 2 files changed, 12 insertions(+), 1 deletion(-)
tools/objtool/elf.c +9 -1
@@ -22,11 +22,16 @@
 
 #define MAX_NAME_LEN 128
 
+static inline u32 str_hash(const char *str)
+{
+	return jhash(str, strlen(str), 0);
+}
+
 struct section *find_section_by_name(struct elf *elf, const char *name)
 {
 	struct section *sec;
 
-	list_for_each_entry(sec, &elf->sections, list)
+	hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
 		if (!strcmp(sec->name, name))
 			return sec;
 
@@ -202,6 +207,7 @@ static int read_sections(struct elf *elf
 
 		list_add_tail(&sec->list, &elf->sections);
 		hash_add(elf->section_hash, &sec->hash, sec->idx);
+		hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 	}
 
 	if (stats)
@@ -441,6 +447,7 @@ struct elf *elf_read(const char *name, i
 
 	hash_init(elf->symbol_hash);
 	hash_init(elf->section_hash);
+	hash_init(elf->section_name_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -581,6 +588,7 @@ struct section *elf_create_section(struc
 
 	list_add_tail(&sec->list, &elf->sections);
 	hash_add(elf->section_hash, &sec->hash, sec->idx);
+	hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 
 	return sec;
 }
tools/objtool/elf.h +3 -0
@@ -10,6 +10,7 @@
 #include <gelf.h>
 #include <linux/list.h>
 #include <linux/hashtable.h>
+#include <linux/jhash.h>
 
 #ifdef LIBELF_USE_DEPRECATED
 # define elf_getshdrnum    elf_getshnum
@@ -26,6 +27,7 @@
 struct section {
 	struct list_head list;
 	struct hlist_node hash;
+	struct hlist_node name_hash;
 	GElf_Shdr sh;
 	struct list_head symbol_list;
 	struct list_head rela_list;
@@ -73,6 +75,7 @@ struct elf {
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
+	DECLARE_HASHTABLE(section_name_hash, 16);
 };
 
 
merge bot Applied
#28 lore raw

[tip: core/objtool] objtool: Optimize find_section_by_name()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     ae358196fac3a0b4d2a7d47a4f401e3421027b03
Gitweb:        https://git.kernel.org/tip/ae358196fac3a0b4d2a7d47a4f401e3421027b03
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 09:32:10 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:29 +01:00

objtool: Optimize find_section_by_name()

In order to avoid yet another linear search of (20k) sections, add a name based hash.

This reduces objtool runtime on vmlinux.o by some 10s to around 35s.

---
 tools/objtool/elf.c | 10 +++++++++-
 tools/objtool/elf.h |  3 +++
 2 files changed, 12 insertions(+), 1 deletion(-)
tools/objtool/elf.c +9 -1
index 9007713..20fe40d 100644
@@ -22,11 +22,16 @@
 
 #define MAX_NAME_LEN 128
 
+static inline u32 str_hash(const char *str)
+{
+	return jhash(str, strlen(str), 0);
+}
+
 struct section *find_section_by_name(struct elf *elf, const char *name)
 {
 	struct section *sec;
 
-	list_for_each_entry(sec, &elf->sections, list)
+	hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
 		if (!strcmp(sec->name, name))
 			return sec;
 
@@ -202,6 +207,7 @@ static int read_sections(struct elf *elf)
 
 		list_add_tail(&sec->list, &elf->sections);
 		hash_add(elf->section_hash, &sec->hash, sec->idx);
+		hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 	}
 
 	if (stats)
@@ -441,6 +447,7 @@ struct elf *elf_read(const char *name, int flags)
 
 	hash_init(elf->symbol_hash);
 	hash_init(elf->section_hash);
+	hash_init(elf->section_name_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -581,6 +588,7 @@ struct section *elf_create_section(struct elf *elf, const char *name,
 
 	list_add_tail(&sec->list, &elf->sections);
 	hash_add(elf->section_hash, &sec->hash, sec->idx);
+	hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 
 	return sec;
 }
tools/objtool/elf.h +3 -0
index 8c272eb..ac7c46f 100644
@@ -10,6 +10,7 @@
 #include <gelf.h>
 #include <linux/list.h>
 #include <linux/hashtable.h>
+#include <linux/jhash.h>
 
 #ifdef LIBELF_USE_DEPRECATED
 # define elf_getshdrnum    elf_getshnum
@@ -26,6 +27,7 @@
 struct section {
 	struct list_head list;
 	struct hlist_node hash;
+	struct hlist_node name_hash;
 	GElf_Shdr sh;
 	struct list_head symbol_list;
 	struct list_head rela_list;
@@ -73,6 +75,7 @@ struct elf {
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
+	DECLARE_HASHTABLE(section_name_hash, 16);
 };
 
 
author maintainer
#29 lore raw

PATCH v3 10/26 objtool: Optimize find_symbol_*() and read_symbols()

In reply to Peter Zijlstra

All of:

read_symbols(), find_symbol_by_offset(), find_symbol_containing(), find_containing_func()

do a linear search of the symbols. Add an RB tree to make it go faster.

This about halves objtool runtime on vmlinux.o, from 34s to 18s.

---
 tools/objtool/Build |    5 +
 tools/objtool/elf.c |  194 ++++++++++++++++++++++++++++++++++++----------------
 tools/objtool/elf.h |    3 
 3 files changed, 144 insertions(+), 58 deletions(-)
tools/objtool/Build +5 -0
@@ -11,6 +11,7 @@ objtool-y += objtool.o
 objtool-y += libstring.o
 objtool-y += libctype.o
 objtool-y += str_error_r.o
+objtool-y += librbtree.o
 
 CFLAGS += -I$(srctree)/tools/lib
 
@@ -25,3 +26,7 @@ $(OUTPUT)libctype.o: ../lib/ctype.c FORC
 $(OUTPUT)str_error_r.o: ../lib/str_error_r.c FORCE
 	$(call rule_mkdir)
 	$(call if_changed_dep,cc_o_c)
+
+$(OUTPUT)librbtree.o: ../lib/rbtree.c FORCE
+	$(call rule_mkdir)
+	$(call if_changed_dep,cc_o_c)
tools/objtool/elf.c +136 -58

251 lines not on this page · raw message

tools/objtool/elf.h +3 -0
@@ -10,6 +10,7 @@
 #include <gelf.h>
 #include <linux/list.h>
 #include <linux/hashtable.h>
+#include <linux/rbtree.h>
 #include <linux/jhash.h>
 
 #ifdef LIBELF_USE_DEPRECATED
@@ -29,6 +30,7 @@ struct section {
 	struct hlist_node hash;
 	struct hlist_node name_hash;
 	GElf_Shdr sh;
+	struct rb_root symbol_tree;
 	struct list_head symbol_list;
 	struct list_head rela_list;
 	DECLARE_HASHTABLE(rela_hash, 16);
@@ -43,6 +45,7 @@ struct section {
 
 struct symbol {
 	struct list_head list;
+	struct rb_node node;
 	struct hlist_node hash;
 	GElf_Sym sym;
 	struct section *sec;
Reviewed-by on v3 10/26
#30 lore raw

Re: [PATCH v3 10/26] objtool: Optimize find_symbol_*() and read_symbols()

Quoted 5 lines · Peter Zijlstra

All of:

read_symbols(), find_symbol_by_offset(), find_symbol_containing(), find_containing_func()

Quoted 7 lines

do a linear search of the symbols. Add an RB tree to make it go faster.

This about halves objtool runtime on vmlinux.o, from 34s to 18s.

M

merge bot Applied
#31 lore raw

[tip: core/objtool] objtool: Optimize find_symbol_*() and read_symbols()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     2a362ecc3ec9632aeea4b9a9062db91b2bd9975a
Gitweb:        https://git.kernel.org/tip/2a362ecc3ec9632aeea4b9a9062db91b2bd9975a
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 09:34:42 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:29 +01:00

objtool: Optimize find_symbol_*() and read_symbols()

All of:

read_symbols(), find_symbol_by_offset(), find_symbol_containing(), find_containing_func()

do a linear search of the symbols. Add an RB tree to make it go faster.

This about halves objtool runtime on vmlinux.o, from 34s to 18s.

---
 tools/objtool/Build |   5 +-
 tools/objtool/elf.c | 194 ++++++++++++++++++++++++++++++-------------
 tools/objtool/elf.h |   3 +-
 3 files changed, 144 insertions(+), 58 deletions(-)
tools/objtool/Build +5 -0
index 8dc4f08..66f44f5 100644
@@ -11,6 +11,7 @@ objtool-y += objtool.o
 objtool-y += libstring.o
 objtool-y += libctype.o
 objtool-y += str_error_r.o
+objtool-y += librbtree.o
 
 CFLAGS += -I$(srctree)/tools/lib
 
@@ -25,3 +26,7 @@ $(OUTPUT)libctype.o: ../lib/ctype.c FORCE
 $(OUTPUT)str_error_r.o: ../lib/str_error_r.c FORCE
 	$(call rule_mkdir)
 	$(call if_changed_dep,cc_o_c)
+
+$(OUTPUT)librbtree.o: ../lib/rbtree.c FORCE
+	$(call rule_mkdir)
+	$(call if_changed_dep,cc_o_c)
tools/objtool/elf.c +136 -58

251 lines not on this page · raw message

tools/objtool/elf.h +3 -0
index ac7c46f..e4a8d68 100644
@@ -10,6 +10,7 @@
 #include <gelf.h>
 #include <linux/list.h>
 #include <linux/hashtable.h>
+#include <linux/rbtree.h>
 #include <linux/jhash.h>
 
 #ifdef LIBELF_USE_DEPRECATED
@@ -29,6 +30,7 @@ struct section {
 	struct hlist_node hash;
 	struct hlist_node name_hash;
 	GElf_Shdr sh;
+	struct rb_root symbol_tree;
 	struct list_head symbol_list;
 	struct list_head rela_list;
 	DECLARE_HASHTABLE(rela_hash, 16);
@@ -43,6 +45,7 @@ struct section {
 
 struct symbol {
 	struct list_head list;
+	struct rb_node node;
 	struct hlist_node hash;
 	GElf_Sym sym;
 	struct section *sec;
author maintainer
#32 lore raw

PATCH v3 11/26 objtool: Rename find_containing_func()

In reply to Peter Zijlstra

For consistency; we have:

find_symbol_by_offset() / find_symbol_containing()
find_func_by_offset() / find_containing_func()

fix that.

---
 tools/objtool/elf.c  |    2 +-
 tools/objtool/elf.h  |    2 +-
 tools/objtool/warn.h |    2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)
tools/objtool/elf.c +1 -1
@@ -187,7 +187,7 @@ struct symbol *find_symbol_containing(st
 	return NULL;
 }
 
-struct symbol *find_containing_func(struct section *sec, unsigned long offset)
+struct symbol *find_func_containing(struct section *sec, unsigned long offset)
 {
 	struct rb_node *node;
 
tools/objtool/elf.h +1 -1
@@ -91,7 +91,7 @@ struct symbol *find_symbol_containing(st
 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 symbol *find_func_containing(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);
tools/objtool/warn.h +1 -1
@@ -21,7 +21,7 @@ static inline char *offstr(struct sectio
 	char *name, *str;
 	unsigned long name_off;
 
-	func = find_containing_func(sec, offset);
+	func = find_func_containing(sec, offset);
 	if (func) {
 		name = func->name;
 		name_off = offset - func->offset;
merge bot Applied
#34 lore raw

[tip: core/objtool] objtool: Rename find_containing_func()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     53d20720bbc8718ef86fdfe53dec0accfb593ef8
Gitweb:        https://git.kernel.org/tip/53d20720bbc8718ef86fdfe53dec0accfb593ef8
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Mon, 16 Mar 2020 10:36:53 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:29 +01:00

objtool: Rename find_containing_func()

For consistency; we have:

find_symbol_by_offset() / find_symbol_containing()
find_func_by_offset() / find_containing_func()

fix that.

---
 tools/objtool/elf.c  | 2 +-
 tools/objtool/elf.h  | 2 +-
 tools/objtool/warn.h | 2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)
tools/objtool/elf.c +1 -1
index 3a8b426..07db4df 100644
@@ -187,7 +187,7 @@ struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
 	return NULL;
 }
 
-struct symbol *find_containing_func(struct section *sec, unsigned long offset)
+struct symbol *find_func_containing(struct section *sec, unsigned long offset)
 {
 	struct rb_node *node;
 
tools/objtool/elf.h +1 -1
index e4a8d68..d18f466 100644
@@ -91,7 +91,7 @@ struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
 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 symbol *find_func_containing(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);
tools/objtool/warn.h +1 -1
index cbb0a02..7799f60 100644
@@ -21,7 +21,7 @@ static inline char *offstr(struct section *sec, unsigned long offset)
 	char *name, *str;
 	unsigned long name_off;
 
-	func = find_containing_func(sec, offset);
+	func = find_func_containing(sec, offset);
 	if (func) {
 		name = func->name;
 		name_off = offset - func->offset;
author maintainer
#35 lore raw

PATCH v3 12/26 objtool: Resize insn_hash

In reply to Peter Zijlstra

Perf shows we're spending a lot of time in find_insn() and the statistics show we have around 3.2 million instruction. Increase the hash table size to reduce the bucket load from around 50 to 3.

This shaves about 2s off of objtool on vmlinux.o runtime, down to 16s.

---
 tools/objtool/check.h |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tools/objtool/check.h +1 -1
@@ -50,7 +50,7 @@ struct instruction {
 struct objtool_file {
 	struct elf *elf;
 	struct list_head insn_list;
-	DECLARE_HASHTABLE(insn_hash, 16);
+	DECLARE_HASHTABLE(insn_hash, 20);
 	bool ignore_unreachables, c_file, hints, rodata;
 };
 
Reviewed-by on v3 12/26
#36 lore raw

Re: [PATCH v3 12/26] objtool: Resize insn_hash

Quoted 8 lines · Peter Zijlstra

Perf shows we're spending a lot of time in find_insn() and the statistics show we have around 3.2 million instruction. Increase the hash table size to reduce the bucket load from around 50 to 3.

This shaves about 2s off of objtool on vmlinux.o runtime, down to 16s.

M

merge bot Applied
#37 lore raw

[tip: core/objtool] objtool: Resize insn_hash

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     513b5ca6b5fbeb766999fb1a4bc9a55c9fb7c9ca
Gitweb:        https://git.kernel.org/tip/513b5ca6b5fbeb766999fb1a4bc9a55c9fb7c9ca
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 10:20:46 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:30 +01:00

objtool: Resize insn_hash

Perf shows we're spending a lot of time in find_insn() and the statistics show we have around 3.2 million instruction. Increase the hash table size to reduce the bucket load from around 50 to 3.

This shaves about 2s off of objtool on vmlinux.o runtime, down to 16s.

---
 tools/objtool/check.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tools/objtool/check.h +1 -1
index 6d875ca..f0ce8ff 100644
@@ -50,7 +50,7 @@ struct instruction {
 struct objtool_file {
 	struct elf *elf;
 	struct list_head insn_list;
-	DECLARE_HASHTABLE(insn_hash, 16);
+	DECLARE_HASHTABLE(insn_hash, 20);
 	bool ignore_unreachables, c_file, hints, rodata;
 };
 
author maintainer
#38 lore raw

PATCH v3 13/26 objtool: Optimize find_symbol_by_name()

In reply to Peter Zijlstra

Perf showed that find_symbol_by_name() takes time; add a symbol name hash.

This shaves another second off of objtool on vmlinux.o runtime, down to 15 seconds.

---
 tools/objtool/elf.c |   10 +++++-----
 tools/objtool/elf.h |    2 ++
 2 files changed, 7 insertions(+), 5 deletions(-)
tools/objtool/elf.c +5 -5
@@ -203,13 +203,11 @@ struct symbol *find_func_containing(stru
 
 struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
 {
-	struct section *sec;
 	struct symbol *sym;
 
-	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbol_list, list)
-			if (!strcmp(sym->name, name))
-				return sym;
+	hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+		if (!strcmp(sym->name, name))
+			return sym;
 
 	return NULL;
 }
@@ -386,6 +384,7 @@ static int read_symbols(struct elf *elf)
 			entry = &sym->sec->symbol_list;
 		list_add(&sym->list, entry);
 		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+		hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
 	}
 
 	if (stats)
@@ -524,6 +523,7 @@ struct elf *elf_read(const char *name, i
 	memset(elf, 0, sizeof(*elf));
 
 	hash_init(elf->symbol_hash);
+	hash_init(elf->symbol_name_hash);
 	hash_init(elf->section_hash);
 	hash_init(elf->section_name_hash);
 	INIT_LIST_HEAD(&elf->sections);
tools/objtool/elf.h +2 -0
@@ -47,6 +47,7 @@ struct symbol {
 	struct list_head list;
 	struct rb_node node;
 	struct hlist_node hash;
+	struct hlist_node name_hash;
 	GElf_Sym sym;
 	struct section *sec;
 	char *name;
@@ -77,6 +78,7 @@ struct elf {
 	char *name;
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
+	DECLARE_HASHTABLE(symbol_name_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
 	DECLARE_HASHTABLE(section_name_hash, 16);
 };
merge bot Applied
#40 lore raw

[tip: core/objtool] objtool: Optimize find_symbol_by_name()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     cdb3d057a17d56363a831e486ea39e4c389a6cf9
Gitweb:        https://git.kernel.org/tip/cdb3d057a17d56363a831e486ea39e4c389a6cf9
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 10:17:38 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:30 +01:00

objtool: Optimize find_symbol_by_name()

Perf showed that find_symbol_by_name() takes time; add a symbol name hash.

This shaves another second off of objtool on vmlinux.o runtime, down to 15 seconds.

---
 tools/objtool/elf.c | 10 +++++-----
 tools/objtool/elf.h |  2 ++
 2 files changed, 7 insertions(+), 5 deletions(-)
tools/objtool/elf.c +5 -5
index 07db4df..43abae7 100644
@@ -203,13 +203,11 @@ struct symbol *find_func_containing(struct section *sec, unsigned long offset)
 
 struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
 {
-	struct section *sec;
 	struct symbol *sym;
 
-	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbol_list, list)
-			if (!strcmp(sym->name, name))
-				return sym;
+	hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+		if (!strcmp(sym->name, name))
+			return sym;
 
 	return NULL;
 }
@@ -386,6 +384,7 @@ static int read_symbols(struct elf *elf)
 			entry = &sym->sec->symbol_list;
 		list_add(&sym->list, entry);
 		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+		hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
 	}
 
 	if (stats)
@@ -524,6 +523,7 @@ struct elf *elf_read(const char *name, int flags)
 	memset(elf, 0, sizeof(*elf));
 
 	hash_init(elf->symbol_hash);
+	hash_init(elf->symbol_name_hash);
 	hash_init(elf->section_hash);
 	hash_init(elf->section_name_hash);
 	INIT_LIST_HEAD(&elf->sections);
tools/objtool/elf.h +2 -0
index d18f466..3088d92 100644
@@ -47,6 +47,7 @@ struct symbol {
 	struct list_head list;
 	struct rb_node node;
 	struct hlist_node hash;
+	struct hlist_node name_hash;
 	GElf_Sym sym;
 	struct section *sec;
 	char *name;
@@ -77,6 +78,7 @@ struct elf {
 	char *name;
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
+	DECLARE_HASHTABLE(symbol_name_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
 	DECLARE_HASHTABLE(section_name_hash, 16);
 };
author maintainer
#41 lore raw

PATCH v3 14/26 objtool: Optimize read_sections()

In reply to Peter Zijlstra

Perf showed that __hash_init() is a significant portion of read_sections(), so instead of doing a per section rela_hash, use an elf-wide rela_hash.

Statistics show us there are about 1.1 million relas, so size it accordingly.

This reduces the objtool on vmlinux.o runtime to a third, from 15 to 5 seconds.

---
 tools/objtool/check.c   |   18 +++++++++---------
 tools/objtool/elf.c     |   24 ++++++++++++++----------
 tools/objtool/elf.h     |   21 +++++++++++++++++----
 tools/objtool/orc_gen.c |    9 +++++----
 tools/objtool/special.c |    4 ++--
 5 files changed, 47 insertions(+), 29 deletions(-)
tools/objtool/check.c +9 -9
@@ -587,8 +587,8 @@ static int add_jump_destinations(struct
 		if (insn->ignore || insn->offset == FAKE_JUMP_OFFSET)
 			continue;
 
-		rela = find_rela_by_dest_range(insn->sec, insn->offset,
-					       insn->len);
+		rela = find_rela_by_dest_range(file->elf, insn->sec,
+					       insn->offset, insn->len);
 		if (!rela) {
 			dest_sec = insn->sec;
 			dest_off = insn->offset + insn->len + insn->immediate;
@@ -684,8 +684,8 @@ static int add_call_destinations(struct
 		if (insn->type != INSN_CALL)
 			continue;
 
-		rela = find_rela_by_dest_range(insn->sec, insn->offset,
-					       insn->len);
+		rela = find_rela_by_dest_range(file->elf, insn->sec,
+					       insn->offset, insn->len);
 		if (!rela) {
 			dest_off = insn->offset + insn->len + insn->immediate;
 			insn->call_dest = find_func_by_offset(insn->sec, dest_off);
@@ -814,7 +814,7 @@ static int handle_group_alt(struct objto
 		 */
 		if ((insn->offset != special_alt->new_off ||
 		    (insn->type != INSN_CALL && !is_static_jump(insn))) &&
-		    find_rela_by_dest_range(insn->sec, insn->offset, insn->len)) {
+		    find_rela_by_dest_range(file->elf, insn->sec, insn->offset, insn->len)) {
 
 			WARN_FUNC("unsupported relocation in alternatives section",
 				  insn->sec, insn->offset);
@@ -1084,8 +1084,8 @@ static struct rela *find_jump_table(stru
 		    break;
 
 		/* look for a relocation which references .rodata */
-		text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
-						    insn->len);
+		text_rela = find_rela_by_dest_range(file->elf, insn->sec,
+						    insn->offset, insn->len);
 		if (!text_rela || text_rela->sym->type != STT_SECTION ||
 		    !text_rela->sym->sec->rodata)
 			continue;
@@ -1114,7 +1114,7 @@ static struct rela *find_jump_table(stru
 		 * should reference text in the same function as the original
 		 * instruction.
 		 */
-		table_rela = find_rela_by_dest(table_sec, table_offset);
+		table_rela = find_rela_by_dest(file->elf, table_sec, table_offset);
 		if (!table_rela)
 			continue;
 		dest_insn = find_insn(file, table_rela->sym->sec, table_rela->addend);
@@ -1250,7 +1250,7 @@ static int read_unwind_hints(struct objt
 	for (i = 0; i < sec->len / sizeof(struct unwind_hint); i++) {
 		hint = (struct unwind_hint *)sec->data->d_buf + i;
 
-		rela = find_rela_by_dest(sec, i * sizeof(*hint));
+		rela = find_rela_by_dest(file->elf, sec, i * sizeof(*hint));
 		if (!rela) {
 			WARN("can't find rela for unwind_hints[%d]", i);
 			return -1;
tools/objtool/elf.c +14 -10
@@ -212,8 +212,8 @@ struct symbol *find_symbol_by_name(struc
 	return NULL;
 }
 
-struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
-				     unsigned int len)
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+				     unsigned long offset, unsigned int len)
 {
 	struct rela *rela;
 	unsigned long o;
@@ -221,17 +221,22 @@ struct rela *find_rela_by_dest_range(str
 	if (!sec->rela)
 		return NULL;
 
-	for (o = offset; o < offset + len; o++)
-		hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
-			if (rela->offset == o)
+	sec = sec->rela;
+
+	for (o = offset; o < offset + len; o++) {
+		hash_for_each_possible(elf->rela_hash, rela, hash,
+				       sec_offset_hash(sec, o)) {
+			if (rela->sec == sec && rela->offset == o)
 				return rela;
+		}
+	}
 
 	return NULL;
 }
 
-struct rela *find_rela_by_dest(struct section *sec, unsigned long offset)
+struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset)
 {
-	return find_rela_by_dest_range(sec, offset, 1);
+	return find_rela_by_dest_range(elf, sec, offset, 1);
 }
 
 static int read_sections(struct elf *elf)
@@ -261,7 +266,6 @@ static int read_sections(struct elf *elf
 
 		INIT_LIST_HEAD(&sec->symbol_list);
 		INIT_LIST_HEAD(&sec->rela_list);
-		hash_init(sec->rela_hash);
 
 		s = elf_getscn(elf->elf, i);
 		if (!s) {
@@ -493,7 +497,7 @@ static int read_relas(struct elf *elf)
 			}
 
 			list_add_tail(&rela->list, &sec->rela_list);
-			hash_add(sec->rela_hash, &rela->hash, rela->offset);
+			hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
 			nr_rela++;
 		}
 		max_rela = max(max_rela, nr_rela);
@@ -526,6 +530,7 @@ struct elf *elf_read(const char *name, i
 	hash_init(elf->symbol_name_hash);
 	hash_init(elf->section_hash);
 	hash_init(elf->section_name_hash);
+	hash_init(elf->rela_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -586,7 +591,6 @@ struct section *elf_create_section(struc
 
 	INIT_LIST_HEAD(&sec->symbol_list);
 	INIT_LIST_HEAD(&sec->rela_list);
-	hash_init(sec->rela_hash);
 
 	s = elf_newscn(elf->elf);
 	if (!s) {
tools/objtool/elf.h +17 -4
@@ -33,7 +33,6 @@ struct section {
 	struct rb_root symbol_tree;
 	struct list_head symbol_list;
 	struct list_head rela_list;
-	DECLARE_HASHTABLE(rela_hash, 16);
 	struct section *base, *rela;
 	struct symbol *sym;
 	Elf_Data *data;
@@ -81,8 +80,22 @@ struct elf {
 	DECLARE_HASHTABLE(symbol_name_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
 	DECLARE_HASHTABLE(section_name_hash, 16);
+	DECLARE_HASHTABLE(rela_hash, 20);
 };
 
+static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
+{
+	u32 ol = offset, oh = offset >> 32, idx = sec->idx;
+
+	__jhash_mix(ol, oh, idx);
+
+	return ol;
+}
+
+static inline u32 rela_hash(struct rela *rela)
+{
+	return sec_offset_hash(rela->sec, rela->offset);
+}
 
 struct elf *elf_read(const char *name, int flags);
 struct section *find_section_by_name(struct elf *elf, const char *name);
@@ -90,9 +103,9 @@ struct symbol *find_func_by_offset(struc
 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset);
 struct symbol *find_symbol_by_name(struct elf *elf, const char *name);
 struct symbol *find_symbol_containing(struct section *sec, unsigned long offset);
-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 rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset);
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+				     unsigned long offset, unsigned int len);
 struct symbol *find_func_containing(struct section *sec, unsigned long offset);
 struct section *elf_create_section(struct elf *elf, const char *name, size_t
 				   entsize, int nr);
tools/objtool/orc_gen.c +5 -4
@@ -81,7 +81,7 @@ int create_orc(struct objtool_file *file
 	return 0;
 }
 
-static int create_orc_entry(struct section *u_sec, struct section *ip_relasec,
+static int create_orc_entry(struct elf *elf, struct section *u_sec, struct section *ip_relasec,
 				unsigned int idx, struct section *insn_sec,
 				unsigned long insn_off, struct orc_entry *o)
 {
@@ -109,9 +109,10 @@ static int create_orc_entry(struct secti
 	rela->addend = insn_off;
 	rela->type = R_X86_64_PC32;
 	rela->offset = idx * sizeof(int);
+	rela->sec = ip_relasec;
 
 	list_add_tail(&rela->list, &ip_relasec->rela_list);
-	hash_add(ip_relasec->rela_hash, &rela->hash, rela->offset);
+	hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
 
 	return 0;
 }
@@ -182,7 +183,7 @@ int create_orc_sections(struct objtool_f
 			if (!prev_insn || memcmp(&insn->orc, &prev_insn->orc,
 						 sizeof(struct orc_entry))) {
 
-				if (create_orc_entry(u_sec, ip_relasec, idx,
+				if (create_orc_entry(file->elf, u_sec, ip_relasec, idx,
 						     insn->sec, insn->offset,
 						     &insn->orc))
 					return -1;
@@ -194,7 +195,7 @@ int create_orc_sections(struct objtool_f
 
 		/* section terminator */
 		if (prev_insn) {
-			if (create_orc_entry(u_sec, ip_relasec, idx,
+			if (create_orc_entry(file->elf, u_sec, ip_relasec, idx,
 					     prev_insn->sec,
 					     prev_insn->offset + prev_insn->len,
 					     &empty))
tools/objtool/special.c +2 -2
@@ -118,7 +118,7 @@ static int get_alt_entry(struct elf *elf
 		}
 	}
 
-	orig_rela = find_rela_by_dest(sec, offset + entry->orig);
+	orig_rela = find_rela_by_dest(elf, sec, offset + entry->orig);
 	if (!orig_rela) {
 		WARN_FUNC("can't find orig rela", sec, offset + entry->orig);
 		return -1;
@@ -133,7 +133,7 @@ static int get_alt_entry(struct elf *elf
 	alt->orig_off = orig_rela->addend;
 
 	if (!entry->group || alt->new_len) {
-		new_rela = find_rela_by_dest(sec, offset + entry->new);
+		new_rela = find_rela_by_dest(elf, sec, offset + entry->new);
 		if (!new_rela) {
 			WARN_FUNC("can't find new rela",
 				  sec, offset + entry->new);
Reviewed-by on v3 14/26
#42 lore raw

Re: [PATCH v3 14/26] objtool: Optimize read_sections()

Quoted 4 lines · Peter Zijlstra

Perf showed that __hash_init() is a significant portion of read_sections(), so instead of doing a per section rela_hash, use an elf-wide rela_hash.

Quoted 8 lines

Statistics show us there are about 1.1 million relas, so size it accordingly.

This reduces the objtool on vmlinux.o runtime to a third, from 15 to 5 seconds.

M

merge bot Applied
#43 lore raw

[tip: core/objtool] objtool: Optimize read_sections()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     8b5fa6bc326bf02f293b5a39a8f5b3de816265d3
Gitweb:        https://git.kernel.org/tip/8b5fa6bc326bf02f293b5a39a8f5b3de816265d3
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 11:23:36 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:30 +01:00

objtool: Optimize read_sections()

Perf showed that __hash_init() is a significant portion of read_sections(), so instead of doing a per section rela_hash, use an elf-wide rela_hash.

Statistics show us there are about 1.1 million relas, so size it accordingly.

This reduces the objtool on vmlinux.o runtime to a third, from 15 to 5 seconds.

---
 tools/objtool/check.c   | 18 +++++++++---------
 tools/objtool/elf.c     | 24 ++++++++++++++----------
 tools/objtool/elf.h     | 21 +++++++++++++++++----
 tools/objtool/orc_gen.c |  9 +++++----
 tools/objtool/special.c |  4 ++--
 5 files changed, 47 insertions(+), 29 deletions(-)
tools/objtool/check.c +9 -9
index 6df1bae..54a6043 100644
@@ -569,8 +569,8 @@ static int add_jump_destinations(struct objtool_file *file)
 		if (insn->ignore || insn->offset == FAKE_JUMP_OFFSET)
 			continue;
 
-		rela = find_rela_by_dest_range(insn->sec, insn->offset,
-					       insn->len);
+		rela = find_rela_by_dest_range(file->elf, insn->sec,
+					       insn->offset, insn->len);
 		if (!rela) {
 			dest_sec = insn->sec;
 			dest_off = insn->offset + insn->len + insn->immediate;
@@ -666,8 +666,8 @@ static int add_call_destinations(struct objtool_file *file)
 		if (insn->type != INSN_CALL)
 			continue;
 
-		rela = find_rela_by_dest_range(insn->sec, insn->offset,
-					       insn->len);
+		rela = find_rela_by_dest_range(file->elf, insn->sec,
+					       insn->offset, insn->len);
 		if (!rela) {
 			dest_off = insn->offset + insn->len + insn->immediate;
 			insn->call_dest = find_func_by_offset(insn->sec, dest_off);
@@ -796,7 +796,7 @@ static int handle_group_alt(struct objtool_file *file,
 		 */
 		if ((insn->offset != special_alt->new_off ||
 		    (insn->type != INSN_CALL && !is_static_jump(insn))) &&
-		    find_rela_by_dest_range(insn->sec, insn->offset, insn->len)) {
+		    find_rela_by_dest_range(file->elf, insn->sec, insn->offset, insn->len)) {
 
 			WARN_FUNC("unsupported relocation in alternatives section",
 				  insn->sec, insn->offset);
@@ -1066,8 +1066,8 @@ static struct rela *find_jump_table(struct objtool_file *file,
 		    break;
 
 		/* look for a relocation which references .rodata */
-		text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
-						    insn->len);
+		text_rela = find_rela_by_dest_range(file->elf, insn->sec,
+						    insn->offset, insn->len);
 		if (!text_rela || text_rela->sym->type != STT_SECTION ||
 		    !text_rela->sym->sec->rodata)
 			continue;
@@ -1096,7 +1096,7 @@ static struct rela *find_jump_table(struct objtool_file *file,
 		 * should reference text in the same function as the original
 		 * instruction.
 		 */
-		table_rela = find_rela_by_dest(table_sec, table_offset);
+		table_rela = find_rela_by_dest(file->elf, table_sec, table_offset);
 		if (!table_rela)
 			continue;
 		dest_insn = find_insn(file, table_rela->sym->sec, table_rela->addend);
@@ -1232,7 +1232,7 @@ static int read_unwind_hints(struct objtool_file *file)
 	for (i = 0; i < sec->len / sizeof(struct unwind_hint); i++) {
 		hint = (struct unwind_hint *)sec->data->d_buf + i;
 
-		rela = find_rela_by_dest(sec, i * sizeof(*hint));
+		rela = find_rela_by_dest(file->elf, sec, i * sizeof(*hint));
 		if (!rela) {
 			WARN("can't find rela for unwind_hints[%d]", i);
 			return -1;
tools/objtool/elf.c +14 -10
index 43abae7..8a0a1bc 100644
@@ -212,8 +212,8 @@ struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
 	return NULL;
 }
 
-struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
-				     unsigned int len)
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+				     unsigned long offset, unsigned int len)
 {
 	struct rela *rela;
 	unsigned long o;
@@ -221,17 +221,22 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 	if (!sec->rela)
 		return NULL;
 
-	for (o = offset; o < offset + len; o++)
-		hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
-			if (rela->offset == o)
+	sec = sec->rela;
+
+	for (o = offset; o < offset + len; o++) {
+		hash_for_each_possible(elf->rela_hash, rela, hash,
+				       sec_offset_hash(sec, o)) {
+			if (rela->sec == sec && rela->offset == o)
 				return rela;
+		}
+	}
 
 	return NULL;
 }
 
-struct rela *find_rela_by_dest(struct section *sec, unsigned long offset)
+struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset)
 {
-	return find_rela_by_dest_range(sec, offset, 1);
+	return find_rela_by_dest_range(elf, sec, offset, 1);
 }
 
 static int read_sections(struct elf *elf)
@@ -261,7 +266,6 @@ static int read_sections(struct elf *elf)
 
 		INIT_LIST_HEAD(&sec->symbol_list);
 		INIT_LIST_HEAD(&sec->rela_list);
-		hash_init(sec->rela_hash);
 
 		s = elf_getscn(elf->elf, i);
 		if (!s) {
@@ -493,7 +497,7 @@ static int read_relas(struct elf *elf)
 			}
 
 			list_add_tail(&rela->list, &sec->rela_list);
-			hash_add(sec->rela_hash, &rela->hash, rela->offset);
+			hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
 			nr_rela++;
 		}
 		max_rela = max(max_rela, nr_rela);
@@ -526,6 +530,7 @@ struct elf *elf_read(const char *name, int flags)
 	hash_init(elf->symbol_name_hash);
 	hash_init(elf->section_hash);
 	hash_init(elf->section_name_hash);
+	hash_init(elf->rela_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -586,7 +591,6 @@ struct section *elf_create_section(struct elf *elf, const char *name,
 
 	INIT_LIST_HEAD(&sec->symbol_list);
 	INIT_LIST_HEAD(&sec->rela_list);
-	hash_init(sec->rela_hash);
 
 	s = elf_newscn(elf->elf);
 	if (!s) {
tools/objtool/elf.h +17 -4
index 3088d92..dfd2431 100644
@@ -33,7 +33,6 @@ struct section {
 	struct rb_root symbol_tree;
 	struct list_head symbol_list;
 	struct list_head rela_list;
-	DECLARE_HASHTABLE(rela_hash, 16);
 	struct section *base, *rela;
 	struct symbol *sym;
 	Elf_Data *data;
@@ -81,8 +80,22 @@ struct elf {
 	DECLARE_HASHTABLE(symbol_name_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
 	DECLARE_HASHTABLE(section_name_hash, 16);
+	DECLARE_HASHTABLE(rela_hash, 20);
 };
 
+static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
+{
+	u32 ol = offset, oh = offset >> 32, idx = sec->idx;
+
+	__jhash_mix(ol, oh, idx);
+
+	return ol;
+}
+
+static inline u32 rela_hash(struct rela *rela)
+{
+	return sec_offset_hash(rela->sec, rela->offset);
+}
 
 struct elf *elf_read(const char *name, int flags);
 struct section *find_section_by_name(struct elf *elf, const char *name);
@@ -90,9 +103,9 @@ struct symbol *find_func_by_offset(struct section *sec, unsigned long offset);
 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset);
 struct symbol *find_symbol_by_name(struct elf *elf, const char *name);
 struct symbol *find_symbol_containing(struct section *sec, unsigned long offset);
-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 rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset);
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+				     unsigned long offset, unsigned int len);
 struct symbol *find_func_containing(struct section *sec, unsigned long offset);
 struct section *elf_create_section(struct elf *elf, const char *name, size_t
 				   entsize, int nr);
tools/objtool/orc_gen.c +5 -4
index 27a4112..41e4a27 100644
@@ -81,7 +81,7 @@ int create_orc(struct objtool_file *file)
 	return 0;
 }
 
-static int create_orc_entry(struct section *u_sec, struct section *ip_relasec,
+static int create_orc_entry(struct elf *elf, struct section *u_sec, struct section *ip_relasec,
 				unsigned int idx, struct section *insn_sec,
 				unsigned long insn_off, struct orc_entry *o)
 {
@@ -109,9 +109,10 @@ static int create_orc_entry(struct section *u_sec, struct section *ip_relasec,
 	rela->addend = insn_off;
 	rela->type = R_X86_64_PC32;
 	rela->offset = idx * sizeof(int);
+	rela->sec = ip_relasec;
 
 	list_add_tail(&rela->list, &ip_relasec->rela_list);
-	hash_add(ip_relasec->rela_hash, &rela->hash, rela->offset);
+	hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
 
 	return 0;
 }
@@ -182,7 +183,7 @@ int create_orc_sections(struct objtool_file *file)
 			if (!prev_insn || memcmp(&insn->orc, &prev_insn->orc,
 						 sizeof(struct orc_entry))) {
 
-				if (create_orc_entry(u_sec, ip_relasec, idx,
+				if (create_orc_entry(file->elf, u_sec, ip_relasec, idx,
 						     insn->sec, insn->offset,
 						     &insn->orc))
 					return -1;
@@ -194,7 +195,7 @@ int create_orc_sections(struct objtool_file *file)
 
 		/* section terminator */
 		if (prev_insn) {
-			if (create_orc_entry(u_sec, ip_relasec, idx,
+			if (create_orc_entry(file->elf, u_sec, ip_relasec, idx,
 					     prev_insn->sec,
 					     prev_insn->offset + prev_insn->len,
 					     &empty))
tools/objtool/special.c +2 -2
index fdbaa61..e74e018 100644
@@ -118,7 +118,7 @@ static int get_alt_entry(struct elf *elf, struct special_entry *entry,
 		}
 	}
 
-	orig_rela = find_rela_by_dest(sec, offset + entry->orig);
+	orig_rela = find_rela_by_dest(elf, sec, offset + entry->orig);
 	if (!orig_rela) {
 		WARN_FUNC("can't find orig rela", sec, offset + entry->orig);
 		return -1;
@@ -133,7 +133,7 @@ static int get_alt_entry(struct elf *elf, struct special_entry *entry,
 	alt->orig_off = orig_rela->addend;
 
 	if (!entry->group || alt->new_len) {
-		new_rela = find_rela_by_dest(sec, offset + entry->new);
+		new_rela = find_rela_by_dest(elf, sec, offset + entry->new);
 		if (!new_rela) {
 			WARN_FUNC("can't find new rela",
 				  sec, offset + entry->new);
author maintainer
#45 lore raw

Re: [PATCH v3 14/26] objtool: Optimize read_sections()

Quoted 1 line · On Tue, Apr 21, 2020 at 10:47:14PM +0800, youling257 wrote:

this patch cause 64bit kernel build failed on 32bit userspace, please fix.

You've now spend more time and effort complaining about this than it would've been to fix it yourself. The fix is absolutely trivial.

Anyway, I have a fix, it'll get there eventually. Excuse me for not considering 32bit a priority.

maintainer
#46 lore raw

Re: [PATCH v3 14/26] objtool: Optimize read_sections()

Quoted 1 line · Peter Zijlstra

Excuse me for not considering 32bit a priority.

rm -rf 32bit already!

Signature · 4 lines
Regards/Gruss,
    Boris.

https://people.kernel.org/tglx/notes-about-netiquette
#47 lore raw

Re: [PATCH v3 14/26] objtool: Optimize read_sections()

In reply to Peter Zijlstra

linux 5.7rc3 will fix? please submit the patch.

2020-04-21 23:49 GMT+08:00, Peter Zijlstra <[email protected]>:

Quoted 10 lines · On Tue, Apr 21, 2020 at 10:47:14PM +0800, youling257 wrote:
Quoted 2 lines

this patch cause 64bit kernel build failed on 32bit userspace, please fix.

You've now spend more time and effort complaining about this than it would've been to fix it yourself. The fix is absolutely trivial.

Anyway, I have a fix, it'll get there eventually. Excuse me for not considering 32bit a priority.

author maintainer
#48 lore raw

PATCH v3 15/26 objtool: Delete cleanup()

In reply to Peter Zijlstra

Perf shows we spend a measurable amount of time spend cleaning up right before we exit anyway. Avoid the needsless work and just terminate.

This reduces objtool on vmlinux.o runtime from 5.4s to 4.8s

---
 tools/objtool/check.c |   19 -------------------
 1 file changed, 19 deletions(-)
tools/objtool/check.c +0 -19
@@ -2476,23 +2476,6 @@ static int validate_reachable_instructio
 	return 0;
 }
 
-static void cleanup(struct objtool_file *file)
-{
-	struct instruction *insn, *tmpinsn;
-	struct alternative *alt, *tmpalt;
-
-	list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
-		list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
-			list_del(&alt->list);
-			free(alt);
-		}
-		list_del(&insn->list);
-		hash_del(&insn->hash);
-		free(insn);
-	}
-	elf_close(file->elf);
-}
-
 static struct objtool_file file;
 
 int check(const char *_objname, bool orc)
@@ -2560,8 +2543,6 @@ int check(const char *_objname, bool orc
 	}
 
 out:
-	cleanup(&file);
-
 	if (ret < 0) {
 		/*
 		 *  Fatal error.  The binary is corrupt or otherwise broken in
Reviewed-by on v3 15/26
#49 lore raw

Re: [PATCH v3 15/26] objtool: Delete cleanup()

Quoted 8 lines · Peter Zijlstra

Perf shows we spend a measurable amount of time spend cleaning up right before we exit anyway. Avoid the needsless work and just terminate.

This reduces objtool on vmlinux.o runtime from 5.4s to 4.8s

M

merge bot Applied
#50 lore raw

[tip: core/objtool] objtool: Delete cleanup()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     8887a86eddd93ca396ca35f7b41fb14ed412f85d
Gitweb:        https://git.kernel.org/tip/8887a86eddd93ca396ca35f7b41fb14ed412f85d
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Wed, 11 Mar 2020 23:07:42 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:30 +01:00

objtool: Delete cleanup()

Perf shows we spend a measurable amount of time spend cleaning up right before we exit anyway. Avoid the needsless work and just terminate.

This reduces objtool on vmlinux.o runtime from 5.4s to 4.8s

---
 tools/objtool/check.c | 19 -------------------
 1 file changed, 19 deletions(-)
tools/objtool/check.c +0 -19
index 54a6043..0c9c9ad 100644
@@ -2458,23 +2458,6 @@ static int validate_reachable_instructions(struct objtool_file *file)
 	return 0;
 }
 
-static void cleanup(struct objtool_file *file)
-{
-	struct instruction *insn, *tmpinsn;
-	struct alternative *alt, *tmpalt;
-
-	list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
-		list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
-			list_del(&alt->list);
-			free(alt);
-		}
-		list_del(&insn->list);
-		hash_del(&insn->hash);
-		free(insn);
-	}
-	elf_close(file->elf);
-}
-
 static struct objtool_file file;
 
 int check(const char *_objname, bool orc)
@@ -2542,8 +2525,6 @@ int check(const char *_objname, bool orc)
 	}
 
 out:
-	cleanup(&file);
-
 	if (ret < 0) {
 		/*
 		 *  Fatal error.  The binary is corrupt or otherwise broken in
author maintainer
#51 lore raw

PATCH v3 16/26 objtool: Optimize find_rela_by_dest_range()

In reply to Peter Zijlstra

Perf shows there is significant time in find_rela_by_dest(); this is because we have to iterate the address space per byte, looking for relocation entries.

Optimize this by reducing the address space granularity.

This reduces objtool on vmlinux.o runtime from 4.8 to 4.4 seconds.

---
 tools/objtool/elf.c |   15 +++++++++++----
 tools/objtool/elf.h |   16 +++++++++++++++-
 2 files changed, 26 insertions(+), 5 deletions(-)
tools/objtool/elf.c +11 -4
@@ -215,7 +215,7 @@ struct symbol *find_symbol_by_name(struc
 struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
 				     unsigned long offset, unsigned int len)
 {
-	struct rela *rela;
+	struct rela *rela, *r = NULL;
 	unsigned long o;
 
 	if (!sec->rela)
@@ -223,12 +223,19 @@ struct rela *find_rela_by_dest_range(str
 
 	sec = sec->rela;
 
-	for (o = offset; o < offset + len; o++) {
+	for_offset_range(o, offset, offset + len) {
 		hash_for_each_possible(elf->rela_hash, rela, hash,
 				       sec_offset_hash(sec, o)) {
-			if (rela->sec == sec && rela->offset == o)
-				return rela;
+			if (rela->sec != sec)
+				continue;
+
+			if (rela->offset >= offset && rela->offset < offset + len) {
+				if (!r || rela->offset < r->offset)
+					r = rela;
+			}
 		}
+		if (r)
+			return r;
 	}
 
 	return NULL;
tools/objtool/elf.h +15 -1
@@ -83,9 +83,23 @@ struct elf {
 	DECLARE_HASHTABLE(rela_hash, 20);
 };
 
+#define OFFSET_STRIDE_BITS	4
+#define OFFSET_STRIDE		(1UL << OFFSET_STRIDE_BITS)
+#define OFFSET_STRIDE_MASK	(~(OFFSET_STRIDE - 1))
+
+#define for_offset_range(_offset, _start, _end)		\
+	for (_offset = ((_start) & OFFSET_STRIDE_MASK);	\
+	     _offset <= ((_end) & OFFSET_STRIDE_MASK);	\
+	     _offset += OFFSET_STRIDE)
+
 static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
 {
-	u32 ol = offset, oh = offset >> 32, idx = sec->idx;
+	u32 ol, oh, idx = sec->idx;
+
+	offset &= OFFSET_STRIDE_MASK;
+
+	ol = offset;
+	oh = offset >> 32;
 
 	__jhash_mix(ol, oh, idx);
 
Reviewed-by on v3 16/26
#52 lore raw

Re: [PATCH v3 16/26] objtool: Optimize find_rela_by_dest_range()

Quoted 10 lines · Peter Zijlstra

Perf shows there is significant time in find_rela_by_dest(); this is because we have to iterate the address space per byte, looking for relocation entries.

Optimize this by reducing the address space granularity.

This reduces objtool on vmlinux.o runtime from 4.8 to 4.4 seconds.

M

merge bot Applied
#53 lore raw

[tip: core/objtool] objtool: Optimize find_rela_by_dest_range()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     74b873e49d92f90deb41d1a2a8fbb70328aebd67
Gitweb:        https://git.kernel.org/tip/74b873e49d92f90deb41d1a2a8fbb70328aebd67
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Thu, 12 Mar 2020 11:30:50 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:31 +01:00

objtool: Optimize find_rela_by_dest_range()

Perf shows there is significant time in find_rela_by_dest(); this is because we have to iterate the address space per byte, looking for relocation entries.

Optimize this by reducing the address space granularity.

This reduces objtool on vmlinux.o runtime from 4.8 to 4.4 seconds.

---
 tools/objtool/elf.c | 15 +++++++++++----
 tools/objtool/elf.h | 16 +++++++++++++++-
 2 files changed, 26 insertions(+), 5 deletions(-)
tools/objtool/elf.c +11 -4
index 8a0a1bc..09ddc8f 100644
@@ -215,7 +215,7 @@ struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
 struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
 				     unsigned long offset, unsigned int len)
 {
-	struct rela *rela;
+	struct rela *rela, *r = NULL;
 	unsigned long o;
 
 	if (!sec->rela)
@@ -223,12 +223,19 @@ struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
 
 	sec = sec->rela;
 
-	for (o = offset; o < offset + len; o++) {
+	for_offset_range(o, offset, offset + len) {
 		hash_for_each_possible(elf->rela_hash, rela, hash,
 				       sec_offset_hash(sec, o)) {
-			if (rela->sec == sec && rela->offset == o)
-				return rela;
+			if (rela->sec != sec)
+				continue;
+
+			if (rela->offset >= offset && rela->offset < offset + len) {
+				if (!r || rela->offset < r->offset)
+					r = rela;
+			}
 		}
+		if (r)
+			return r;
 	}
 
 	return NULL;
tools/objtool/elf.h +15 -1
index dfd2431..ebbb10c 100644
@@ -83,9 +83,23 @@ struct elf {
 	DECLARE_HASHTABLE(rela_hash, 20);
 };
 
+#define OFFSET_STRIDE_BITS	4
+#define OFFSET_STRIDE		(1UL << OFFSET_STRIDE_BITS)
+#define OFFSET_STRIDE_MASK	(~(OFFSET_STRIDE - 1))
+
+#define for_offset_range(_offset, _start, _end)		\
+	for (_offset = ((_start) & OFFSET_STRIDE_MASK);	\
+	     _offset <= ((_end) & OFFSET_STRIDE_MASK);	\
+	     _offset += OFFSET_STRIDE)
+
 static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
 {
-	u32 ol = offset, oh = offset >> 32, idx = sec->idx;
+	u32 ol, oh, idx = sec->idx;
+
+	offset &= OFFSET_STRIDE_MASK;
+
+	ol = offset;
+	oh = offset >> 32;
 
 	__jhash_mix(ol, oh, idx);
 
author maintainer
#54 lore raw

PATCH v3 17/26 objtool: Re-arrange validate_functions()

In reply to Peter Zijlstra

In preparation to adding a vmlinux.o specific pass, rearrange some code. No functional changes intended.

---
 tools/objtool/check.c |   60 ++++++++++++++++++++++++++++----------------------
 1 file changed, 34 insertions(+), 26 deletions(-)
tools/objtool/check.c +34 -26
@@ -2413,9 +2413,8 @@ static bool ignore_unreachable_insn(stru
 	return false;
 }
 
-static int validate_functions(struct objtool_file *file)
+static int validate_section(struct objtool_file *file, struct section *sec)
 {
-	struct section *sec;
 	struct symbol *func;
 	struct instruction *insn;
 	struct insn_state state;
@@ -2428,35 +2427,44 @@ static int validate_functions(struct obj
 	       CFI_NUM_REGS * sizeof(struct cfi_reg));
 	state.stack_size = initial_func_cfi.cfa.offset;
 
-	for_each_sec(file, sec) {
-		list_for_each_entry(func, &sec->symbol_list, list) {
-			if (func->type != STT_FUNC)
-				continue;
-
-			if (!func->len) {
-				WARN("%s() is missing an ELF size annotation",
-				     func->name);
-				warnings++;
-			}
-
-			if (func->pfunc != func || func->alias != func)
-				continue;
-
-			insn = find_insn(file, sec, func->offset);
-			if (!insn || insn->ignore || insn->visited)
-				continue;
-
-			state.uaccess = func->uaccess_safe;
-
-			ret = validate_branch(file, func, insn, state);
-			if (ret && backtrace)
-				BT_FUNC("<=== (func)", insn);
-			warnings += ret;
+	list_for_each_entry(func, &sec->symbol_list, list) {
+		if (func->type != STT_FUNC)
+			continue;
+
+		if (!func->len) {
+			WARN("%s() is missing an ELF size annotation",
+					func->name);
+			warnings++;
 		}
+
+		if (func->pfunc != func || func->alias != func)
+			continue;
+
+		insn = find_insn(file, sec, func->offset);
+		if (!insn || insn->ignore || insn->visited)
+			continue;
+
+		state.uaccess = func->uaccess_safe;
+
+		ret = validate_branch(file, func, insn, state);
+		if (ret && backtrace)
+			BT_FUNC("<=== (func)", insn);
+		warnings += ret;
 	}
 
 	return warnings;
 }
+
+static int validate_functions(struct objtool_file *file)
+{
+	struct section *sec;
+	int warnings = 0;
+
+	for_each_sec(file, sec)
+		warnings += validate_section(file, sec);
+
+	return warnings;
+}
 
 static int validate_reachable_instructions(struct objtool_file *file)
 {
Acked-by on v3 17/26
#55 lore raw

Re: [PATCH v3 17/26] objtool: Re-arrange validate_functions()

Quoted 46 lines · Peter Zijlstra

In preparation to adding a vmlinux.o specific pass, rearrange some code. No functional changes intended.

---
 tools/objtool/check.c |   60 ++++++++++++++++++++++++++++----------------------
 1 file changed, 34 insertions(+), 26 deletions(-)
tools/objtool/check.c +1 -23
@@ -2413,9 +2413,8 @@ static bool ignore_unreachable_insn(stru
 	return false;
 }
 
-static int validate_functions(struct objtool_file *file)
+static int validate_section(struct objtool_file *file, struct section *sec)
 {
-	struct section *sec;
 	struct symbol *func;
 	struct instruction *insn;
 	struct insn_state state;
@@ -2428,35 +2427,44 @@ static int validate_functions(struct obj
 	       CFI_NUM_REGS * sizeof(struct cfi_reg));
 	state.stack_size = initial_func_cfi.cfa.offset;
 
-	for_each_sec(file, sec) {
-		list_for_each_entry(func, &sec->symbol_list, list) {
-			if (func->type != STT_FUNC)
-				continue;
-
-			if (!func->len) {
-				WARN("%s() is missing an ELF size annotation",
-				     func->name);
-				warnings++;
-			}
-
-			if (func->pfunc != func || func->alias != func)
-				continue;
-
-			insn = find_insn(file, sec, func->offset);
-			if (!insn || insn->ignore || insn->visited)
-				continue;
-
-			state.uaccess = func->uaccess_safe;
-
-			ret = validate_branch(file, func, insn, state);

tools/objtool/check.c static int validate_functions(struct obj · line 2436

Quoted 10 lines
tools/objtool/check.c +7 -3
-			if (ret && backtrace)
-				BT_FUNC("<=== (func)", insn);
-			warnings += ret;
+	list_for_each_entry(func, &sec->symbol_list, list) {
+		if (func->type != STT_FUNC)
+			continue;
+
+		if (!func->len) {
+			WARN("%s() is missing an ELF size annotation",
+					func->name);

wonky indentation

Signature · 1 line
Josh
author maintainer
#56 lore raw

Re: [PATCH v3 17/26] objtool: Re-arrange validate_functions()

Quoted 6 lines · Josh Poimboeuf

tools/objtool/check.c static int validate_functions(struct obj · line 2436

Quoted 3 lines · Peter Zijlstra
tools/objtool/check.c +3 -0
+		if (!func->len) {
+			WARN("%s() is missing an ELF size annotation",
+					func->name);

wonky indentation

Argh, clearly I need to update my .vimrc on that machine. That's the default C indenting per Vim and I'm pretty sure I reflowed that function with =%.

merge bot Applied
#58 lore raw

[tip: core/objtool] objtool: Re-arrange validate_functions()

In reply to Peter Zijlstra
The following commit has been merged into the core/objtool branch of tip:

The following commit has been merged into the core/objtool branch of tip:

Commit-ID:     350994bf95414d6da67a72f27d7ac3832ce3725d
Gitweb:        https://git.kernel.org/tip/350994bf95414d6da67a72f27d7ac3832ce3725d
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Mon, 23 Mar 2020 20:57:13 +01:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 25 Mar 2020 18:28:31 +01:00

objtool: Re-arrange validate_functions()

In preparation to adding a vmlinux.o specific pass, rearrange some code. No functional changes intended.

---
 tools/objtool/check.c | 52 ++++++++++++++++++++++++------------------
 1 file changed, 30 insertions(+), 22 deletions(-)
tools/objtool/check.c +30 -22
index 0c9c9ad..0bfcb39 100644
@@ -2395,9 +2395,8 @@ static bool ignore_unreachable_insn(struct instruction *insn)
 	return false;
 }
 
-static int validate_functions(struct objtool_file *file)
+static int validate_section(struct objtool_file *file, struct section *sec)
 {
-	struct section *sec;
 	struct symbol *func;
 	struct instruction *insn;
 	struct insn_state state;
@@ -2410,36 +2409,45 @@ static int validate_functions(struct objtool_file *file)
 	       CFI_NUM_REGS * sizeof(struct cfi_reg));
 	state.stack_size = initial_func_cfi.cfa.offset;
 
-	for_each_sec(file, sec) {
-		list_for_each_entry(func, &sec->symbol_list, list) {
-			if (func->type != STT_FUNC)
-				continue;
+	list_for_each_entry(func, &sec->symbol_list, list) {
+		if (func->type != STT_FUNC)
+			continue;
 
-			if (!func->len) {
-				WARN("%s() is missing an ELF size annotation",
-				     func->name);
-				warnings++;
-			}
+		if (!func->len) {
+			WARN("%s() is missing an ELF size annotation",
+			     func->name);
+			warnings++;
+		}
 
-			if (func->pfunc != func || func->alias != func)
-				continue;
+		if (func->pfunc != func || func->alias != func)
+			continue;
 
-			insn = find_insn(file, sec, func->offset);
-			if (!insn || insn->ignore || insn->visited)
-				continue;
+		insn = find_insn(file, sec, func->offset);
+		if (!insn || insn->ignore || insn->visited)
+			continue;
 
-			state.uaccess = func->uaccess_safe;
+		state.uaccess = func->uaccess_safe;
 
-			ret = validate_branch(file, func, insn, state);
-			if (ret && backtrace)
-				BT_FUNC("<=== (func)", insn);
-			warnings += ret;
-		}
+		ret = validate_branch(file, func, insn, state);
+		if (ret && backtrace)
+			BT_FUNC("<=== (func)", insn);
+		warnings += ret;
 	}
 
 	return warnings;
 }
 
+static int validate_functions(struct objtool_file *file)
+{
+	struct section *sec;
+	int warnings = 0;
+
+	for_each_sec(file, sec)
+		warnings += validate_section(file, sec);
+
+	return warnings;
+}
+
 static int validate_reachable_instructions(struct objtool_file *file)
 {
 	struct instruction *insn;
author maintainer
#59 lore raw

PATCH v3 18/26 objtool: Fix !CFI insn_state propagation

In reply to Peter Zijlstra

Objtool keeps per instruction CFI state in struct insn_state and will save/restore this where required. However, insn_state has grown some !CFI state, and this must not be saved/restored (and thus lost).

Fix this by explicitly preserving the !CFI state and clarify by restucturing the code and adding a comment.

XXX, the insn==first condition is not handled right.

---
 tools/objtool/check.c |   95 +++++++++++++++++++++++++++++---------------------
 tools/objtool/check.h |    8 ++++
 2 files changed, 64 insertions(+), 39 deletions(-)
tools/objtool/check.c +56 -39
@@ -2033,6 +2033,59 @@ static int validate_return(struct symbol
 	return 0;
 }
 
+static int apply_insn_hint(struct objtool_file *file, struct section *sec,
+			   struct symbol *func, struct instruction *first,
+			   struct instruction *insn, struct insn_state *state)
+{
+	struct insn_state old = *state;
+
+	if (insn->restore) {
+		struct instruction *save_insn, *i;
+
+		i = insn;
+		save_insn = NULL;
+		sym_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; // XXX
+
+			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;
+
+	/* restore !CFI state */
+	state->df = old.df;
+	state->uaccess = old.uaccess;
+	state->uaccess_stack = old.uaccess_stack;
+
+	return 0;
+}
+
 /*
  * Follow the branch starting at the given instruction, and recursively follow
  * any other branches (jumps).  Meanwhile, track the frame pointer state at
@@ -2082,45 +2135,9 @@ static int validate_branch(struct objtoo
 		}
 
 		if (insn->hint) {
-			if (insn->restore) {
-				struct instruction *save_insn, *i;
-
-				i = insn;
-				save_insn = NULL;
-				sym_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;
-
+			ret = apply_insn_hint(file, sec, func, first, insn, &state);
+			if (ret)
+				return ret;
 		} else
 			insn->state = state;
 
tools/objtool/check.h +8 -0
@@ -13,6 +13,14 @@
 #include "orc.h"
 #include <linux/hashtable.h>
 
+/*
+ * This structure (mostly) contains the instruction level CFI (Call Frame
+ * Information) and is saved/restored where appropriate; see validate_branch().
+ *
+ * However it does also contain a limited amount of !CFI state; this state must
+ * not be saved/restored along with the CFI information and is manually
+ * preserved. See apply_insn_hint().
+ */
 struct insn_state {
 	struct cfi_reg cfa;
 	struct cfi_reg regs[CFI_NUM_REGS];
#60 lore raw

Re: [PATCH v3 18/26] objtool: Fix !CFI insn_state propagation

Quoted 45 lines · Peter Zijlstra

Objtool keeps per instruction CFI state in struct insn_state and will save/restore this where required. However, insn_state has grown some !CFI state, and this must not be saved/restored (and thus lost).

Fix this by explicitly preserving the !CFI state and clarify by restucturing the code and adding a comment.

XXX, the insn==first condition is not handled right.

---
 tools/objtool/check.c |   95 +++++++++++++++++++++++++++++---------------------
 tools/objtool/check.h |    8 ++++
 2 files changed, 64 insertions(+), 39 deletions(-)
tools/objtool/check.c +24 -0
@@ -2033,6 +2033,59 @@ static int validate_return(struct symbol
 	return 0;
 }
 
+static int apply_insn_hint(struct objtool_file *file, struct section *sec,
+			   struct symbol *func, struct instruction *first,
+			   struct instruction *insn, struct insn_state *state)
+{
+	struct insn_state old = *state;
+
+	if (insn->restore) {
+		struct instruction *save_insn, *i;
+
+		i = insn;
+		save_insn = NULL;
+		sym_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;
+		}
+

tools/objtool/check.c static int validate_return(struct symbol · line 2069

Quoted 10 lines
tools/objtool/check.c +10 -0
+		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; // XXX

Yeah, moving this code out to apply_insn_hint() seems like a nice idea, but it wouldn't be worth it if it breaks this case. TBH I don't remember if this check was for a real-world case. Might be worth looking at... If this case doesn't exist in reality then we could just remove this check altogether.

tools/objtool/check.c static int validate_return(struct symbol · line 2079

Quoted 10 lines
tools/objtool/check.c +10 -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;

This would have been easier to review if apply_insn_hint() were added in a separate patch.

tools/objtool/check.c static int validate_return(struct symbol · line 2084

Quoted 5 lines
tools/objtool/check.c +5 -0
+
+	/* restore !CFI state */
+	state->df = old.df;
+	state->uaccess = old.uaccess;
+	state->uaccess_stack = old.uaccess_stack;

Maybe we should just move the CFI stuff into a state->cfi substruct. That would remove the need for these bits and probably also the comment above the insn_state declaration.

Signature · 1 line
Josh
author maintainer
#61 lore raw

Re: [PATCH v3 18/26] objtool: Fix !CFI insn_state propagation

Quoted 18 lines · Josh Poimboeuf

tools/objtool/check.c static int validate_return(struct symbol · line 2069

Quoted 10 lines · Peter Zijlstra
tools/objtool/check.c +10 -0
+		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; // XXX

Yeah, moving this code out to apply_insn_hint() seems like a nice idea, but it wouldn't be worth it if it breaks this case. TBH I don't remember if this check was for a real-world case. Might be worth looking at... If this case doesn't exist in reality then we could just remove this check altogether.

I'll go run a bunch of builds with a print on it, that should tell us I suppose.

Quoted 5 lines
Quoted 5 lines
tools/objtool/check.c +5 -0
+
+			WARN_FUNC("objtool isn't smart enough to handle this CFI save/restore combo",
+					sec, insn->offset);
+			return 1;
+		}
Quoted 8 lines

tools/objtool/check.c static int validate_return(struct symbol · line 2079

Quoted 5 lines
tools/objtool/check.c +5 -0
+
+		insn->state = save_insn->state;
+	}
+
+	*state = insn->state;

This would have been easier to review if apply_insn_hint() were added in a separate patch.

27 it will be!

Quoted 9 lines

tools/objtool/check.c static int validate_return(struct symbol · line 2084

Quoted 5 lines
tools/objtool/check.c +5 -0
+
+	/* restore !CFI state */
+	state->df = old.df;
+	state->uaccess = old.uaccess;
+	state->uaccess_stack = old.uaccess_stack;

Maybe we should just move the CFI stuff into a state->cfi substruct. That would remove the need for these bits and probably also the comment above the insn_state declaration.

Indeed!

author maintainer
#62 lore raw

Re: [PATCH v3 18/26] objtool: Fix !CFI insn_state propagation

Quoted 20 lines · Peter Zijlstra
Quoted 18 lines · Josh Poimboeuf

Review

Quoted 10 lines · Peter Zijlstra
(quoted diff) +10 -0
+		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; // XXX

Yeah, moving this code out to apply_insn_hint() seems like a nice idea, but it wouldn't be worth it if it breaks this case. TBH I don't remember if this check was for a real-world case. Might be worth looking at... If this case doesn't exist in reality then we could just remove this check altogether.

Quoted 2 lines

I'll go run a bunch of builds with a print on it, that should tell us I suppose.

I can a bunch of builds, including an allmodconfig with the below on top and it 'works'.

So I suppose we can remove this special case.

---

tools/objtool/check.c +4 -2
@@ -2134,11 +2134,13 @@ static int apply_insn_hint(struct objtoo
 			 * after the save insn has been
 			 * visited.
 			 */
-			if (insn == first)
-				return 0; // XXX
 
 			WARN_FUNC("objtool isn't smart enough to handle this CFI save/restore combo",
 					sec, insn->offset);
+
+			if (insn == first)
+				return -1;
+
 			return 1;
 		}
 
#63 lore raw

Re: [PATCH v3 18/26] objtool: Fix !CFI insn_state propagation

Quoted 35 lines · Peter Zijlstra
Quoted 20 lines · Peter Zijlstra
Quoted 18 lines · Josh Poimboeuf

Review

Quoted 10 lines · Peter Zijlstra
(quoted diff) +10 -0
+		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; // XXX

Yeah, moving this code out to apply_insn_hint() seems like a nice idea, but it wouldn't be worth it if it breaks this case. TBH I don't remember if this check was for a real-world case. Might be worth looking at... If this case doesn't exist in reality then we could just remove this check altogether.

Quoted 2 lines

I'll go run a bunch of builds with a print on it, that should tell us I suppose.

I can a bunch of builds, including an allmodconfig with the below on top and it 'works'.

So I suppose we can remove this special case.

---

tools/objtool/check.c +0 -0
@@ -2134,11 +2134,13 @@ static int apply_insn_hint(struct objtoo
 			 * after the save insn has been
 			 * visited.

tools/objtool/check.c static int apply_insn_hint(struct objtoo · line 2143

Quoted 10 lines
tools/objtool/check.c +4 -2
 			 */
-			if (insn == first)
-				return 0; // XXX
 
 			WARN_FUNC("objtool isn't smart enough to handle this CFI save/restore combo",
 					sec, insn->offset);
+
+			if (insn == first)
+				return -1;
+

I think all the validate_branch() callers aren't prepared to handle a -1 return code.

We can just be lazy and remove this 'insn == first' check and consider it a non-fatal warning.

Signature · 1 line
Josh
author maintainer
#64 lore raw

PATCH 1/1 objtool: Remove CFI save/restore special case

In reply to Peter Zijlstra

Subject: objtool: Remove CFI save/restore special case
From: Peter Zijlstra <[email protected]>
Date: Wed Mar 25 12:58:16 CET 2020

There is a special case in the UNWIND_HINT_RESTORE code. When, upon looking for the UNWIND_HINT_SAVE instruction to restore from, it finds the instruction hasn't been visited yet, it normally issues a WARN, except when this HINT_SAVE instruction is the first instruction of this branch.

This special case is of dubious correctness and is certainly unused (verified with an allmodconfig build), the two sites that employ UNWIND_HINT_SAVE/RESTORE (sync_core() and ftrace_regs_caller()) have the SAVE on unconditional instructions at the start of the function. It is therefore impossible for the save_insn not to have been visited when we do hit the RESTORE.

Remove this.

---
 tools/objtool/check.c |   15 ++-------------
 1 file changed, 2 insertions(+), 13 deletions(-)
tools/objtool/check.c +2 -13
@@ -2040,15 +2040,14 @@ static int validate_return(struct symbol
  * tools/objtool/Documentation/stack-validation.txt.
  */
 static int validate_branch(struct objtool_file *file, struct symbol *func,
-			   struct instruction *first, struct insn_state state)
+			   struct instruction *insn, struct insn_state state)
 {
+	struct instruction *next_insn;
 	struct alternative *alt;
-	struct instruction *insn, *next_insn;
 	struct section *sec;
 	u8 visited;
 	int ret;
 
-	insn = first;
 	sec = insn->sec;
 
 	if (insn->alt_group && list_empty(&insn->alts)) {
@@ -2101,16 +2100,6 @@ static int validate_branch(struct objtoo
 				}
 
 				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;
author maintainer
#65 lore raw

PATCH 1/1 objtool: Factor out CFI hints

In reply to Peter Zijlstra

Subject: objtool: Factor out CFI hints
From: Peter Zijlstra <[email protected]>
Date: Wed Mar 25 13:08:17 CET 2020

Move the application of CFI hints into it's own function. No functional changes intended.

---
 tools/objtool/check.c |   66 ++++++++++++++++++++++++++++----------------------
 1 file changed, 37 insertions(+), 29 deletions(-)
tools/objtool/check.c +37 -29
@@ -2033,6 +2033,40 @@ static int validate_return(struct symbol
 	return 0;
 }
 
+static int apply_insn_hint(struct objtool_file *file, struct section *sec,
+			   struct symbol *func, struct instruction *insn,
+			   struct insn_state *state)
+{
+	if (insn->restore) {
+		struct instruction *save_insn, *i;
+
+		i = insn;
+		save_insn = NULL;
+		sym_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) {
+			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;
+}
+
 /*
  * Follow the branch starting at the given instruction, and recursively follow
  * any other branches (jumps).  Meanwhile, track the frame pointer state at
@@ -2081,35 +2115,9 @@ static int validate_branch(struct objtoo
 		}
 
 		if (insn->hint) {
-			if (insn->restore) {
-				struct instruction *save_insn, *i;
-
-				i = insn;
-				save_insn = NULL;
-				sym_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) {
-					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;
-
+			ret = apply_insn_hint(file, sec, func, insn, &state);
+			if (ret)
+				return ret;
 		} else
 			insn->state = state;
 
author maintainer
#66 lore raw

PATCH 1/1 objtool: Rename struct cfi_state

In reply to Peter Zijlstra

Subject: objtool: Rename struct cfi_state
From: Peter Zijlstra <[email protected]>
Date: Wed Mar 25 15:34:50 CET 2020

There's going to be a new struct cfi_state, rename this one to make place.

---
 tools/objtool/arch.h            |    2 +-
 tools/objtool/arch/x86/decode.c |    2 +-
 tools/objtool/cfi.h             |    2 +-
 tools/objtool/check.c           |    2 +-
 4 files changed, 4 insertions(+), 4 deletions(-)
tools/objtool/arch.h +1 -1
@@ -66,7 +66,7 @@ struct stack_op {
 	struct op_src src;
 };
 
-void arch_initial_func_cfi_state(struct cfi_state *state);
+void arch_initial_func_cfi_state(struct cfi_init_state *state);
 
 int arch_decode_instruction(struct elf *elf, struct section *sec,
 			    unsigned long offset, unsigned int maxlen,
tools/objtool/arch/x86/decode.c +1 -1
@@ -480,7 +480,7 @@ int arch_decode_instruction(struct elf *
 	return 0;
 }
 
-void arch_initial_func_cfi_state(struct cfi_state *state)
+void arch_initial_func_cfi_state(struct cfi_init_state *state)
 {
 	int i;
 
tools/objtool/cfi.h +1 -1
@@ -35,7 +35,7 @@ struct cfi_reg {
 	int offset;
 };
 
-struct cfi_state {
+struct cfi_init_state {
 	struct cfi_reg cfa;
 	struct cfi_reg regs[CFI_NUM_REGS];
 };
tools/objtool/check.c +1 -1
@@ -27,7 +27,7 @@ struct alternative {
 };
 
 const char *objname;
-struct cfi_state initial_func_cfi;
+struct cfi_init_state initial_func_cfi;
 
 struct instruction *find_insn(struct objtool_file *file,
 			      struct section *sec, unsigned long offset)
author maintainer
#67 lore raw

PATCH 1/1 objtool: Fix !CFI insn_state propagation

In reply to Peter Zijlstra

Subject: objtool: Fix !CFI insn_state propagation
From: Peter Zijlstra <[email protected]>
Date: Wed Mar 25 14:04:45 CET 2020

Objtool keeps per instruction CFI state in struct insn_state and will save/restore this where required. However, insn_state has grown some !CFI state, and this must not be saved/restored (that would loose/destroy state).

Fix this by moving the CFI specific parts of insn_state into struct cfi_state.

---
 tools/objtool/cfi.h     |   12 ++
 tools/objtool/check.c   |  270 ++++++++++++++++++++++++------------------------
 tools/objtool/check.h   |   13 --
 tools/objtool/orc_gen.c |    8 -
 4 files changed, 160 insertions(+), 143 deletions(-)
tools/objtool/cfi.h +12 -0
@@ -36,8 +36,20 @@ struct cfi_reg {
 };
 
 struct cfi_init_state {
+	struct cfi_reg regs[CFI_NUM_REGS];
 	struct cfi_reg cfa;
+};
+
+struct cfi_state {
 	struct cfi_reg regs[CFI_NUM_REGS];
+	struct cfi_reg vals[CFI_NUM_REGS];
+	struct cfi_reg cfa;
+	int stack_size;
+	int drap_reg, drap_offset;
+	unsigned char type;
+	bool bp_scratch;
+	bool drap;
+	bool end;
 };
 
 #endif /* _OBJTOOL_CFI_H */
tools/objtool/check.c +140 -130

631 lines not on this page · raw message

tools/objtool/check.h +4 -9
@@ -14,15 +14,10 @@
 #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, end, uaccess, df;
+	struct cfi_state cfi;
 	unsigned int uaccess_stack;
-	int drap_reg, drap_offset;
-	struct cfi_reg vals[CFI_NUM_REGS];
+	bool uaccess;
+	bool df;
 };
 
 struct instruction {
@@ -43,7 +38,7 @@ struct instruction {
 	struct list_head alts;
 	struct symbol *func;
 	struct stack_op stack_op;
-	struct insn_state state;
+	struct cfi_state cfi;
 	struct orc_entry orc;
 };
 
tools/objtool/orc_gen.c +4 -4
@@ -16,10 +16,10 @@ int create_orc(struct objtool_file *file
 
 	for_each_insn(file, insn) {
 		struct orc_entry *orc = &insn->orc;
-		struct cfi_reg *cfa = &insn->state.cfa;
-		struct cfi_reg *bp = &insn->state.regs[CFI_BP];
+		struct cfi_reg *cfa = &insn->cfi.cfa;
+		struct cfi_reg *bp = &insn->cfi.regs[CFI_BP];
 
-		orc->end = insn->state.end;
+		orc->end = insn->cfi.end;
 
 		if (cfa->base == CFI_UNDEFINED) {
 			orc->sp_reg = ORC_REG_UNDEFINED;
@@ -75,7 +75,7 @@ int create_orc(struct objtool_file *file
 
 		orc->sp_offset = cfa->offset;
 		orc->bp_offset = bp->offset;
-		orc->type = insn->state.type;
+		orc->type = insn->cfi.type;
 	}
 
 	return 0;
author maintainer
#68 lore raw

PATCH v3 19/26 objtool: Implement noinstr validation

In reply to Peter Zijlstra

Validate that any call out of .noinstr.text is in between instr_begin() and instr_end() annotations.

This annotation is useful to ensure correct behaviour wrt tracing sensitive code like entry/exit and idle code. When we run code in a sensitive context we want a guarantee no unknown code is ran.

Since this validation relies on knowing the section of call destination symbols, we must run it on vmlinux.o instead of on individual object files.

Add two options:

-d/--duplicate "duplicate validation for vmlinux" -l/--vmlinux "vmlinux.o validation"

Where the latter auto-detects when objname ends with "vmlinux.o" and the former will force all validations, also those already done on !vmlinux object files.

---
 tools/objtool/builtin-check.c |   11 +++-
 tools/objtool/builtin.h       |    2 
 tools/objtool/check.c         |   97 ++++++++++++++++++++++++++++++++++++++++++
 tools/objtool/check.h         |    3 +
 tools/objtool/elf.h           |    2 
 5 files changed, 111 insertions(+), 4 deletions(-)
tools/objtool/builtin-check.c +9 -2
@@ -14,10 +14,11 @@
  */
 
 #include <subcmd/parse-options.h>
+#include <string.h>
 #include "builtin.h"
 #include "check.h"
 
-bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
+bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats, validate_dup, vmlinux;
 
 static const char * const check_usage[] = {
 	"objtool check [<options>] file.o",
@@ -32,12 +33,14 @@ const struct option check_options[] = {
 	OPT_BOOLEAN('b', "backtrace", &backtrace, "unwind on error"),
 	OPT_BOOLEAN('a', "uaccess", &uaccess, "enable uaccess checking"),
 	OPT_BOOLEAN('s', "stats", &stats, "print statistics"),
+	OPT_BOOLEAN('d', "duplicate", &validate_dup, "duplicate validation for vmlinux.o"),
+	OPT_BOOLEAN('l', "vmlinux", &vmlinux, "vmlinux.o validation"),
 	OPT_END(),
 };
 
 int cmd_check(int argc, const char **argv)
 {
-	const char *objname;
+	const char *objname, *s;
 
 	argc = parse_options(argc, argv, check_options, check_usage, 0);
 
@@ -46,5 +49,9 @@ int cmd_check(int argc, const char **arg
 
 	objname = argv[0];
 
+	s = strstr(objname, "vmlinux.o");
+	if (s && !s[9])
+		vmlinux = true;
+
 	return check(objname, false);
 }
tools/objtool/builtin.h +1 -1
@@ -8,7 +8,7 @@
 #include <subcmd/parse-options.h>
 
 extern const struct option check_options[];
-extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
+extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats, validate_dup, vmlinux;
 
 extern int cmd_check(int argc, const char **argv);
 extern int cmd_orc(int argc, const char **argv);
tools/objtool/check.c +97 -0

151 lines not on this page · raw message

tools/objtool/check.h +3 -0
@@ -28,6 +28,8 @@ struct insn_state {
 	unsigned char type;
 	bool bp_scratch;
 	bool drap, end, uaccess, df;
+	bool noinstr;
+	s8 instr;
 	unsigned int uaccess_stack;
 	int drap_reg, drap_offset;
 	struct cfi_reg vals[CFI_NUM_REGS];
@@ -43,6 +45,7 @@ struct instruction {
 	unsigned long immediate;
 	bool alt_group, dead_end, ignore, hint, save, restore, ignore_alts;
 	bool retpoline_safe;
+	s8 instr;
 	u8 visited;
 	struct symbol *call_dest;
 	struct instruction *jump_dest;
tools/objtool/elf.h +1 -1
@@ -39,7 +39,7 @@ struct section {
 	char *name;
 	int idx;
 	unsigned int len;
-	bool changed, text, rodata;
+	bool changed, text, rodata, noinstr;
 };
 
 struct symbol {
Acked-by on v3 19/26
#69 lore raw

Re: [PATCH v3 19/26] objtool: Implement noinstr validation

Quoted 13 lines · Peter Zijlstra

Validate that any call out of .noinstr.text is in between instr_begin() and instr_end() annotations.

This annotation is useful to ensure correct behaviour wrt tracing sensitive code like entry/exit and idle code. When we run code in a sensitive context we want a guarantee no unknown code is ran.

Since this validation relies on knowing the section of call destination symbols, we must run it on vmlinux.o instead of on individual object files.

Add two options:

Quoted 8 lines

-d/--duplicate "duplicate validation for vmlinux" -l/--vmlinux "vmlinux.o validation"

Where the latter auto-detects when objname ends with "vmlinux.o" and the former will force all validations, also those already done on !vmlinux object files.

Signature · 1 line
Josh
author maintainer
#70 lore raw

PATCH v3 19/26 objtool: Implement noinstr validation

In reply to Peter Zijlstra

Subject: objtool: Implement noinstr validation
From: Peter Zijlstra <[email protected]>
Date: Tue Mar 10 18:57:41 CET 2020

Validate that any call out of .noinstr.text is in between instr_begin() and instr_end() annotations.

This annotation is useful to ensure correct behaviour wrt tracing sensitive code like entry/exit and idle code. When we run code in a sensitive context we want a guarantee no unknown code is ran.

Since this validation relies on knowing the section of call destination symbols, we must run it on vmlinux.o instead of on individual object files.

Add two options:

-d/--duplicate "duplicate validation for vmlinux" -l/--vmlinux "vmlinux.o validation"

Where the latter auto-detects when objname ends with "vmlinux.o" and the former will force all validations, also those already done on !vmlinux object files.

---
 tools/objtool/builtin-check.c |   11 +++-
 tools/objtool/builtin.h       |    2 
 tools/objtool/check.c         |   98 ++++++++++++++++++++++++++++++++++++++++++
 tools/objtool/check.h         |    3 +
 tools/objtool/elf.h           |    2 
 5 files changed, 112 insertions(+), 4 deletions(-)
tools/objtool/builtin-check.c +9 -2
@@ -14,10 +14,11 @@
  */
 
 #include <subcmd/parse-options.h>
+#include <string.h>
 #include "builtin.h"
 #include "check.h"
 
-bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
+bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats, validate_dup, vmlinux;
 
 static const char * const check_usage[] = {
 	"objtool check [<options>] file.o",
@@ -32,12 +33,14 @@ const struct option check_options[] = {
 	OPT_BOOLEAN('b', "backtrace", &backtrace, "unwind on error"),
 	OPT_BOOLEAN('a', "uaccess", &uaccess, "enable uaccess checking"),
 	OPT_BOOLEAN('s', "stats", &stats, "print statistics"),
+	OPT_BOOLEAN('d', "duplicate", &validate_dup, "duplicate validation for vmlinux.o"),
+	OPT_BOOLEAN('l', "vmlinux", &vmlinux, "vmlinux.o validation"),
 	OPT_END(),
 };
 
 int cmd_check(int argc, const char **argv)
 {
-	const char *objname;
+	const char *objname, *s;
 
 	argc = parse_options(argc, argv, check_options, check_usage, 0);
 
@@ -46,5 +49,9 @@ int cmd_check(int argc, const char **arg
 
 	objname = argv[0];
 
+	s = strstr(objname, "vmlinux.o");
+	if (s && !s[9])
+		vmlinux = true;
+
 	return check(objname, false);
 }
tools/objtool/builtin.h +1 -1
@@ -8,7 +8,7 @@
 #include <subcmd/parse-options.h>
 
 extern const struct option check_options[];
-extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats;
+extern bool no_fp, no_unreachable, retpoline, module, backtrace, uaccess, stats, validate_dup, vmlinux;
 
 extern int cmd_check(int argc, const char **argv);
 extern int cmd_orc(int argc, const char **argv);
tools/objtool/check.c +98 -0

152 lines not on this page · raw message

tools/objtool/check.h +3 -0
@@ -18,6 +18,8 @@ struct insn_state {
 	unsigned int uaccess_stack;
 	bool uaccess;
 	bool df;
+	bool noinstr;
+	s8 instr;
 };
 
 struct instruction {
@@ -30,6 +32,7 @@ struct instruction {
 	unsigned long immediate;
 	bool alt_group, dead_end, ignore, hint, save, restore, ignore_alts;
 	bool retpoline_safe;
+	s8 instr;
 	u8 visited;
 	struct symbol *call_dest;
 	struct instruction *jump_dest;
tools/objtool/elf.h +1 -1
@@ -39,7 +39,7 @@ struct section {
 	char *name;
 	int idx;
 	unsigned int len;
-	bool changed, text, rodata;
+	bool changed, text, rodata, noinstr;
 };
 
 struct symbol {
author maintainer
#71 lore raw

PATCH v3 20/26 objtool: Optimize !vmlinux.o again

In reply to Peter Zijlstra

When doing kbuild tests to see if the objtool changes affected those I found that there was a measurable regression:

pre post

  real    1m13.594        1m16.488s
  user    34m58.246s      35m23.947s
  sys     4m0.393s        4m27.312s

Perf showed that for small files the increased hash-table sizes were a measurable difference. Since we already have -l "vmlinux" to distinguish between the modes, make it also use a smaller portion of the hash-tables.

This flips it into a small win:

  real    1m14.143s
  user    34m49.292s
  sys     3m44.746s
---
 tools/objtool/elf.c     |   62 +++++++++++++++++++++++++++++++++---------------
 tools/objtool/elf.h     |   13 ++++++----
 tools/objtool/orc_gen.c |    3 --
 3 files changed, 52 insertions(+), 26 deletions(-)
tools/objtool/elf.c +43 -19
@@ -27,6 +27,22 @@ static inline u32 str_hash(const char *s
 	return jhash(str, strlen(str), 0);
 }
 
+static inline int elf_hash_bits(void)
+{
+	return vmlinux ? ELF_HASH_BITS : 16;
+}
+
+#define elf_hash_add(hashtable, node, key) \
+	hlist_add_head(node, &hashtable[hash_min(key, elf_hash_bits())])
+
+static void elf_hash_init(struct hlist_head *table)
+{
+	__hash_init(table, 1U << elf_hash_bits());
+}
+
+#define elf_hash_for_each_possible(name, obj, member, key)			\
+	hlist_for_each_entry(obj, &name[hash_min(key, elf_hash_bits())], member)
+
 static void rb_add(struct rb_root *tree, struct rb_node *node,
 		   int (*cmp)(struct rb_node *, const struct rb_node *))
 {
@@ -115,7 +131,7 @@ struct section *find_section_by_name(str
 {
 	struct section *sec;
 
-	hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
+	elf_hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
 		if (!strcmp(sec->name, name))
 			return sec;
 
@@ -127,7 +143,7 @@ static struct section *find_section_by_i
 {
 	struct section *sec;
 
-	hash_for_each_possible(elf->section_hash, sec, hash, idx)
+	elf_hash_for_each_possible(elf->section_hash, sec, hash, idx)
 		if (sec->idx == idx)
 			return sec;
 
@@ -138,7 +154,7 @@ static struct symbol *find_symbol_by_ind
 {
 	struct symbol *sym;
 
-	hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+	elf_hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
 		if (sym->idx == idx)
 			return sym;
 
@@ -205,7 +221,7 @@ struct symbol *find_symbol_by_name(struc
 {
 	struct symbol *sym;
 
-	hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+	elf_hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
 		if (!strcmp(sym->name, name))
 			return sym;
 
@@ -224,7 +240,7 @@ struct rela *find_rela_by_dest_range(str
 	sec = sec->rela;
 
 	for_offset_range(o, offset, offset + len) {
-		hash_for_each_possible(elf->rela_hash, rela, hash,
+		elf_hash_for_each_possible(elf->rela_hash, rela, hash,
 				       sec_offset_hash(sec, o)) {
 			if (rela->sec != sec)
 				continue;
@@ -309,8 +325,8 @@ static int read_sections(struct elf *elf
 		sec->len = sec->sh.sh_size;
 
 		list_add_tail(&sec->list, &elf->sections);
-		hash_add(elf->section_hash, &sec->hash, sec->idx);
-		hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
+		elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
+		elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 	}
 
 	if (stats)
@@ -394,8 +410,8 @@ static int read_symbols(struct elf *elf)
 		else
 			entry = &sym->sec->symbol_list;
 		list_add(&sym->list, entry);
-		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
-		hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
+		elf_hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+		elf_hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
 	}
 
 	if (stats)
@@ -456,6 +472,14 @@ static int read_symbols(struct elf *elf)
 	return -1;
 }
 
+void elf_add_rela(struct elf *elf, struct rela *rela)
+{
+	struct section *sec = rela->sec;
+
+	list_add_tail(&rela->list, &sec->rela_list);
+	elf_hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+}
+
 static int read_relas(struct elf *elf)
 {
 	struct section *sec;
@@ -503,8 +527,7 @@ static int read_relas(struct elf *elf)
 				return -1;
 			}
 
-			list_add_tail(&rela->list, &sec->rela_list);
-			hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+			elf_add_rela(elf, rela);
 			nr_rela++;
 		}
 		max_rela = max(max_rela, nr_rela);
@@ -531,15 +554,16 @@ struct elf *elf_read(const char *name, i
 		perror("malloc");
 		return NULL;
 	}
-	memset(elf, 0, sizeof(*elf));
+	memset(elf, 0, offsetof(struct elf, sections));
 
-	hash_init(elf->symbol_hash);
-	hash_init(elf->symbol_name_hash);
-	hash_init(elf->section_hash);
-	hash_init(elf->section_name_hash);
-	hash_init(elf->rela_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
+	elf_hash_init(elf->symbol_hash);
+	elf_hash_init(elf->symbol_name_hash);
+	elf_hash_init(elf->section_hash);
+	elf_hash_init(elf->section_name_hash);
+	elf_hash_init(elf->rela_hash);
+
 	elf->fd = open(name, flags);
 	if (elf->fd == -1) {
 		fprintf(stderr, "objtool: Can't open '%s': %s\n",
@@ -676,8 +700,8 @@ struct section *elf_create_section(struc
 	shstrtab->changed = true;
 
 	list_add_tail(&sec->list, &elf->sections);
-	hash_add(elf->section_hash, &sec->hash, sec->idx);
-	hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
+	elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
+	elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 
 	return sec;
 }
tools/objtool/elf.h +8 -5
@@ -70,17 +70,19 @@ struct rela {
 	bool jump_table_start;
 };
 
+#define ELF_HASH_BITS	20
+
 struct elf {
 	Elf *elf;
 	GElf_Ehdr ehdr;
 	int fd;
 	char *name;
 	struct list_head sections;
-	DECLARE_HASHTABLE(symbol_hash, 20);
-	DECLARE_HASHTABLE(symbol_name_hash, 20);
-	DECLARE_HASHTABLE(section_hash, 16);
-	DECLARE_HASHTABLE(section_name_hash, 16);
-	DECLARE_HASHTABLE(rela_hash, 20);
+	DECLARE_HASHTABLE(symbol_hash, ELF_HASH_BITS);
+	DECLARE_HASHTABLE(symbol_name_hash, ELF_HASH_BITS);
+	DECLARE_HASHTABLE(section_hash, ELF_HASH_BITS);
+	DECLARE_HASHTABLE(section_name_hash, ELF_HASH_BITS);
+	DECLARE_HASHTABLE(rela_hash, ELF_HASH_BITS);
 };
 
 #define OFFSET_STRIDE_BITS	4
@@ -127,6 +129,7 @@ struct section *elf_create_rela_section(
 int elf_rebuild_rela_section(struct section *sec);
 int elf_write(struct elf *elf);
 void elf_close(struct elf *elf);
+void elf_add_rela(struct elf *elf, struct rela *rela);
 
 #define for_each_sec(file, sec)						\
 	list_for_each_entry(sec, &file->elf->sections, list)
tools/objtool/orc_gen.c +1 -2
@@ -111,8 +111,7 @@ static int create_orc_entry(struct elf *
 	rela->offset = idx * sizeof(int);
 	rela->sec = ip_relasec;
 
-	list_add_tail(&rela->list, &ip_relasec->rela_list);
-	hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+	elf_add_rela(elf, rela);
 
 	return 0;
 }
author maintainer
#72 lore raw

PATCH v3 21/26 objtool: Use sec_offset_hash() for insn_hash

In reply to Peter Zijlstra

In preparation for find_insn_containing(), change insn_hash to use sec_offset_hash().

This actually reduces runtime; probably because mixing in the section index reduces the collisions due to text sections all starting their instructions at offset 0.

Runtime on vmlinux.o from 3.1 to 2.5 seconds.

---
 tools/objtool/check.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
tools/objtool/check.c +3 -2
@@ -34,9 +34,10 @@ struct instruction *find_insn(struct obj
 {
 	struct instruction *insn;
 
-	hash_for_each_possible(file->insn_hash, insn, hash, offset)
+	hash_for_each_possible(file->insn_hash, insn, hash, sec_offset_hash(sec, offset)) {
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
+	}
 
 	return NULL;
 }
@@ -276,7 +277,7 @@ static int decode_instructions(struct ob
 			if (ret)
 				goto err;
 
-			hash_add(file->insn_hash, &insn->hash, insn->offset);
+			hash_add(file->insn_hash, &insn->hash, sec_offset_hash(sec, insn->offset));
 			list_add_tail(&insn->list, &file->insn_list);
 			nr_insns++;
 		}
author maintainer
#73 lore raw

PATCH v3 22/26 objtool: Detect loading function pointers across noinstr

In reply to Peter Zijlstra

Detect if noinstr text loads functions pointers from regular text, doing so is a definite sign that indirect function calls are unsafe.

---
 tools/objtool/arch.h  |    2 +
 tools/objtool/check.c |   71 ++++++++++++++++++++++++++++++++++++++++++++++++++
 tools/objtool/check.h |    2 -
 3 files changed, 74 insertions(+), 1 deletion(-)
tools/objtool/arch.h +2 -0
@@ -75,4 +75,6 @@ int arch_decode_instruction(struct elf *
 
 bool arch_callee_saved_reg(unsigned char reg);
 
+#define MAX_INSN_SIZE 15
+
 #endif /* _ARCH_H */
tools/objtool/check.c +71 -0

101 lines not on this page · raw message

tools/objtool/check.h +1 -1
@@ -36,7 +36,7 @@ struct instruction {
 	enum insn_type type;
 	unsigned long immediate;
 	bool alt_group, dead_end, ignore, hint, save, restore, ignore_alts;
-	bool retpoline_safe;
+	bool retpoline_safe, has_text_rela;
 	s8 instr;
 	u8 visited;
 	struct symbol *call_dest;
author maintainer
#74 lore raw

PATCH v3 23/26 kbuild/objtool: Add objtool-vmlinux.o pass

In reply to Peter Zijlstra

Now that objtool is capable of processing vmlinux.o and actually has something useful to do there, (conditionally) add it to the final link pass.

This will increase build time by a few seconds.

---
 lib/Kconfig.debug       |    5 +++++
 scripts/link-vmlinux.sh |   24 ++++++++++++++++++++++++
 2 files changed, 29 insertions(+)
lib/Kconfig.debug +5 -0
@@ -379,6 +379,11 @@ config STACK_VALIDATION
 	  For more information, see
 	  tools/objtool/Documentation/stack-validation.txt.
 
+config VMLINUX_VALIDATION
+	bool
+	depends on STACK_VALIDATION && DEBUG_ENTRY && !PARAVIRT
+	default y
+
 config DEBUG_FORCE_WEAK_PER_CPU
 	bool "Force weak per-cpu definitions"
 	depends on DEBUG_KERNEL
scripts/link-vmlinux.sh +24 -0
@@ -55,6 +55,29 @@ modpost_link()
 	${LD} ${KBUILD_LDFLAGS} -r -o ${1} ${objects}
 }
 
+objtool_link()
+{
+	local objtoolopt;
+
+	if [ -n "${CONFIG_VMLINUX_VALIDATION}" ]; then
+		objtoolopt="check"
+		if [ -z "${CONFIG_FRAME_POINTER}" ]; then
+			objtoolopt="${objtoolopt} --no-fp"
+		fi
+		if [ -n "${CONFIG_GCOV_KERNEL}" ]; then
+			objtoolopt="${objtoolopt} --no-unreachable"
+		fi
+		if [ -n "${CONFIG_RETPOLINE}" ]; then
+			objtoolopt="${objtoolopt} --retpoline"
+		fi
+		if [ -n "${CONFIG_X86_SMAP}" ]; then
+			objtoolopt="${objtoolopt} --uaccess"
+		fi
+		info OBJTOOL ${1}
+		tools/objtool/objtool ${objtoolopt} ${1}
+	fi
+}
+
 # Link of vmlinux
 # ${1} - output file
 # ${2}, ${3}, ... - optional extra .o files
@@ -244,6 +267,7 @@ ${MAKE} -f "${srctree}/scripts/Makefile.
 #link vmlinux.o
 info LD vmlinux.o
 modpost_link vmlinux.o
+objtool_link vmlinux.o
 
 # modpost vmlinux.o to check for section mismatches
 ${MAKE} -f "${srctree}/scripts/Makefile.modpost" MODPOST_VMLINUX=1
#75 lore raw

Re: [PATCH v3 23/26] kbuild/objtool: Add objtool-vmlinux.o pass

Quoted 15 lines · Peter Zijlstra

Now that objtool is capable of processing vmlinux.o and actually has something useful to do there, (conditionally) add it to the final link pass.

This will increase build time by a few seconds.

---
 lib/Kconfig.debug       |    5 +++++
 scripts/link-vmlinux.sh |   24 ++++++++++++++++++++++++
 2 files changed, 29 insertions(+)

lib/Kconfig.debug config STACK_VALIDATION · line 386

Quoted 8 lines
lib/Kconfig.debug +5 -0
@@ -379,6 +379,11 @@ config STACK_VALIDATION
 	  For more information, see
 	  tools/objtool/Documentation/stack-validation.txt.
 
+config VMLINUX_VALIDATION
+	bool
+	depends on STACK_VALIDATION && DEBUG_ENTRY && !PARAVIRT
+	default y
+

So I'm assuming this is incompatible with PARAVIRT because of all the indirect pvops calls?

I'm thinking it should be easy to detect those and whitelist them because they always have a pv_ops relocation associated with the call instruction.

Signature · 1 line
Josh
author maintainer
#76 lore raw

Re: [PATCH v3 23/26] kbuild/objtool: Add objtool-vmlinux.o pass

Quoted 8 lines · Josh Poimboeuf

lib/Kconfig.debug config STACK_VALIDATION · line 386

Quoted 5 lines
lib/Kconfig.debug +5 -0
+config VMLINUX_VALIDATION
+	bool
+	depends on STACK_VALIDATION && DEBUG_ENTRY && !PARAVIRT
+	default y
+

So I'm assuming this is incompatible with PARAVIRT because of all the indirect pvops calls?

Yep.

Quoted 3 lines

I'm thinking it should be easy to detect those and whitelist them because they always have a pv_ops relocation associated with the call instruction.

I did consider that, but have been too lazy to actually make that work. Also, the series is large enough as it is.. :-)

author maintainer
#77 lore raw

PATCH v3 24/26 objtool: Avoid iterating !text section symbols

In reply to Peter Zijlstra

validate_functions() iterates all sections their symbols; this is pointless to do for !text sections as they won't have instructions anyway.

---
 tools/objtool/check.c |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
tools/objtool/check.c +5 -1
@@ -2621,8 +2621,12 @@ static int validate_functions(struct obj
 	struct section *sec;
 	int warnings = 0;
 
-	for_each_sec(file, sec)
+	for_each_sec(file, sec) {
+		if (!(sec->sh.sh_flags & SHF_EXECINSTR))
+			continue;
+
 		warnings += validate_section(file, sec);
+	}
 
 	return warnings;
 }
author maintainer
#79 lore raw

PATCH v3 25/26 objtool: Rearrange validate_section()

In reply to Peter Zijlstra

In preparation of further changes, once again break out the loop body. No functional changes intended.

---
 tools/objtool/check.c |   51 ++++++++++++++++++++++++++++----------------------
 1 file changed, 29 insertions(+), 22 deletions(-)
tools/objtool/check.c +29 -22
@@ -2552,12 +2552,37 @@ static void prepare_insn_rela(struct obj
 	}
 }
 
-static int validate_section(struct objtool_file *file, struct section *sec)
+static int validate_symbol(struct objtool_file *file, struct section *sec,
+			   struct symbol *sym, struct insn_state *state)
 {
-	struct symbol *func;
 	struct instruction *insn;
+	int ret;
+
+	if (!sym->len) {
+		WARN("%s() is missing an ELF size annotation", sym->name);
+		return 1;
+	}
+
+	if (sym->pfunc != sym || sym->alias != sym)
+		return 0;
+
+	insn = find_insn(file, sec, sym->offset);
+	if (!insn || insn->ignore || insn->visited)
+		return 0;
+
+	state->uaccess = sym->uaccess_safe;
+
+	ret = validate_branch(file, insn->func, insn, *state);
+	if (ret && backtrace)
+		BT_FUNC("<=== (sym)", insn);
+	return ret;
+}
+
+static int validate_section(struct objtool_file *file, struct section *sec)
+{
 	struct insn_state state;
-	int ret, warnings = 0;
+	struct symbol *func;
+	int warnings = 0;
 
 	clear_insn_state(&state);
 
@@ -2581,25 +2606,7 @@ static int validate_section(struct objto
 		if (func->type != STT_FUNC)
 			continue;
 
-		if (!func->len) {
-			WARN("%s() is missing an ELF size annotation",
-					func->name);
-			warnings++;
-		}
-
-		if (func->pfunc != func || func->alias != func)
-			continue;
-
-		insn = find_insn(file, sec, func->offset);
-		if (!insn || insn->ignore || insn->visited)
-			continue;
-
-		state.uaccess = func->uaccess_safe;
-
-		ret = validate_branch(file, func, insn, state);
-		if (ret && backtrace)
-			BT_FUNC("<=== (func)", insn);
-		warnings += ret;
+		warnings += validate_symbol(file, sec, func, &state);
 	}
 
 	return warnings;
author maintainer
#81 lore raw

PATCH v3 26/26 objtool: Add STT_NOTYPE noinstr validation

In reply to Peter Zijlstra

Make sure to also check STT_NOTYPE symbols for noinstr violations.

---
 tools/objtool/check.c |   19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)
tools/objtool/check.c +18 -1
@@ -2563,7 +2563,7 @@ static int validate_symbol(struct objtoo
 		return 1;
 	}
 
-	if (sym->pfunc != sym || sym->alias != sym)
+	if ((sym->type == STT_FUNC && sym->pfunc != sym) || sym->alias != sym)
 		return 0;
 
 	insn = find_insn(file, sec, sym->offset);
@@ -2610,6 +2610,23 @@ static int validate_section(struct objto
 		warnings += validate_symbol(file, sec, func, &state);
 	}
 
+	if (state.noinstr) {
+		/*
+		 * In vmlinux mode we will not run validate_unwind_hints() by
+		 * default which means we'll not otherwise visit STT_NOTYPE
+		 * symbols.
+		 *
+		 * In case of --duplicate mode, insn->visited will avoid actual
+		 * duplicate work being done.
+		 */
+		list_for_each_entry(func, &sec->symbol_list, list) {
+			if (func->type != STT_NOTYPE)
+				continue;
+
+			warnings += validate_symbol(file, sec, func, &state);
+		}
+	}
+
 	return warnings;
 }
 
#82 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 29 lines · Peter Zijlstra

Make sure to also check STT_NOTYPE symbols for noinstr violations.

---
 tools/objtool/check.c |   19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)
tools/objtool/check.c +8 -1
@@ -2563,7 +2563,7 @@ static int validate_symbol(struct objtoo
 		return 1;
 	}
 
-	if (sym->pfunc != sym || sym->alias != sym)
+	if ((sym->type == STT_FUNC && sym->pfunc != sym) || sym->alias != sym)
 		return 0;
 
 	insn = find_insn(file, sec, sym->offset);
@@ -2610,6 +2610,23 @@ static int validate_section(struct objto
 		warnings += validate_symbol(file, sec, func, &state);
 	}
 
+	if (state.noinstr) {
+		/*
+		 * In vmlinux mode we will not run validate_unwind_hints() by
+		 * default which means we'll not otherwise visit STT_NOTYPE
+		 * symbols.
+		 *
+		 * In case of --duplicate mode, insn->visited will avoid actual

tools/objtool/check.c static int validate_section(struct objto · line 2629

Quoted 10 lines
tools/objtool/check.c +10 -0
+		 * duplicate work being done.
+		 */
+		list_for_each_entry(func, &sec->symbol_list, list) {
+			if (func->type != STT_NOTYPE)
+				continue;
+
+			warnings += validate_symbol(file, sec, func, &state);
+		}
+	}
+

I guess this is ok, but is there a valid reason why we don't just call validate_unwind_hints()?

It's also slightly concerning that validate_reachable_instructions() isn't called, I'm not 100% convinced all the code will get checked.

Signature · 1 line
Josh
author maintainer
#83 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 23 lines · Josh Poimboeuf
Quoted 7 lines · Peter Zijlstra
tools/objtool/check.c +7 -0
+	if (state.noinstr) {
+		/*
+		 * In vmlinux mode we will not run validate_unwind_hints() by
+		 * default which means we'll not otherwise visit STT_NOTYPE
+		 * symbols.
+		 *
+		 * In case of --duplicate mode, insn->visited will avoid actual

tools/objtool/check.c static int validate_section(struct objto · line 2629

Quoted 10 lines
tools/objtool/check.c +10 -0
+		 * duplicate work being done.
+		 */
+		list_for_each_entry(func, &sec->symbol_list, list) {
+			if (func->type != STT_NOTYPE)
+				continue;
+
+			warnings += validate_symbol(file, sec, func, &state);
+		}
+	}
+

I guess this is ok, but is there a valid reason why we don't just call validate_unwind_hints()?

Quoted 2 lines

It's also slightly concerning that validate_reachable_instructions() isn't called, I'm not 100% convinced all the code will get checked.

This will only end up running on .noinstr.text, while validate_unwind_hints() will run on *everything*. That is, we're purposely not checking everything.

It very much relies on the !vmlinux mode to do the unreachable things.

#84 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 24 lines · Peter Zijlstra
Quoted 23 lines · Josh Poimboeuf
Quoted 7 lines · Peter Zijlstra
tools/objtool/check.c +7 -0
+	if (state.noinstr) {
+		/*
+		 * In vmlinux mode we will not run validate_unwind_hints() by
+		 * default which means we'll not otherwise visit STT_NOTYPE
+		 * symbols.
+		 *
+		 * In case of --duplicate mode, insn->visited will avoid actual

tools/objtool/check.c static int validate_section(struct objto · line 2629

Quoted 10 lines
tools/objtool/check.c +10 -0
+		 * duplicate work being done.
+		 */
+		list_for_each_entry(func, &sec->symbol_list, list) {
+			if (func->type != STT_NOTYPE)
+				continue;
+
+			warnings += validate_symbol(file, sec, func, &state);
+		}
+	}
+

I guess this is ok, but is there a valid reason why we don't just call validate_unwind_hints()?

Quoted 8 lines
Quoted 2 lines

It's also slightly concerning that validate_reachable_instructions() isn't called, I'm not 100% convinced all the code will get checked.

This will only end up running on .noinstr.text, while validate_unwind_hints() will run on *everything*. That is, we're purposely not checking everything.

It very much relies on the !vmlinux mode to do the unreachable things.

Sure, but couldn't validate_unwind_hints() and validate_reachable_instructions() be changed to *only* run on .noinstr.text, for the vmlinux case? That might help converge the vmlinux and !vmlinux paths.

Signature · 1 line
Josh
author maintainer
#85 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 4 lines · Josh Poimboeuf

Sure, but couldn't validate_unwind_hints() and validate_reachable_instructions() be changed to *only* run on .noinstr.text, for the vmlinux case? That might help converge the vmlinux and !vmlinux paths.

You're thinking something like so then?

tools/objtool/check.c +19 -5
@@ -2421,24 +2421,34 @@ static int validate_branch(struct objtoo
 	return 0;
 }
 
-static int validate_unwind_hints(struct objtool_file *file)
+static int validate_unwind_hints(struct objtool_file *file, struct section *sec)
 {
 	struct instruction *insn;
-	int ret, warnings = 0;
 	struct insn_state state;
+	int ret, warnings = 0;
 
 	if (!file->hints)
 		return 0;
 
 	clear_insn_state(&state);
 
-	for_each_insn(file, insn) {
+	if (sec) {
+		insn = find_insn(file, sec, 0);
+		if (!insn)
+			return 0;
+	} else {
+		insn = list_first_entry(&file->insn_list, typeof(*insn), list);
+	}
+
+	while (&insn->list != &file->insn_list && (!sec || insn->sec == sec)) {
 		if (insn->hint && !insn->visited) {
 			ret = validate_branch(file, insn->func, insn, state);
 			if (ret && backtrace)
 				BT_FUNC("<=== (hint)", insn);
 			warnings += ret;
 		}
+
+		insn = list_next_entry(insn, list);
 	}
 
 	return warnings;
@@ -2622,12 +2632,16 @@ static int validate_section(struct objto
 static int validate_vmlinux_functions(struct objtool_file *file)
 {
 	struct section *sec;
+	int warnings = 0;
 
 	sec = find_section_by_name(file->elf, ".noinstr.text");
 	if (!sec)
 		return 0;
 
-	return validate_section(file, sec);
+	warnings += validate_section(file, sec);
+	warnings += validate_unwind_hints(file, sec);
+
+	return warnings;
 }
 
 static int validate_functions(struct objtool_file *file)
@@ -2712,7 +2726,7 @@ int check(const char *_objname, bool orc
 		goto out;
 	warnings += ret;
 
-	ret = validate_unwind_hints(&file);
+	ret = validate_unwind_hints(&file, NULL);
 	if (ret < 0)
 		goto out;
 	warnings += ret;
#86 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Josh Poimboeuf

Sure, but couldn't validate_unwind_hints() and validate_reachable_instructions() be changed to *only* run on .noinstr.text, for the vmlinux case? That might help converge the vmlinux and !vmlinux paths.

You're thinking something like so then?

Not exactly. But I don't want to keep churning this patch set. I can add more patches later, so don't worry about it.

But I was thinking it would eventually be good to have the top-level check() be like

	sec = NULL;
	if (!validate_all)
		sec = find_section_by_name(file->elf, ".noinstr.text");

	ret = validate_functions(&file, sec);
	if (ret < 0)
		goto out;
	warnings += ret;

	ret = validate_unwind_hints(&file, sec);
	if (ret < 0)
		goto out;
	warnings += ret;

	if (!warnings) {
		ret = validate_reachable_instructions(&file, sec);
		if (ret < 0)
			goto out;
		warnings += ret;
	}

	if (!validate_all)
		goto out;

	ret = validate_retpoline(&file);
	....

that way the general flow is the same regardless...

Signature · 1 line
Josh
author maintainer
#87 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 42 lines · Josh Poimboeuf
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Josh Poimboeuf

Sure, but couldn't validate_unwind_hints() and validate_reachable_instructions() be changed to *only* run on .noinstr.text, for the vmlinux case? That might help converge the vmlinux and !vmlinux paths.

You're thinking something like so then?

Not exactly. But I don't want to keep churning this patch set. I can add more patches later, so don't worry about it.

But I was thinking it would eventually be good to have the top-level check() be like

	sec = NULL;
	if (!validate_all)
		sec = find_section_by_name(file->elf, ".noinstr.text");

	ret = validate_functions(&file, sec);
	if (ret < 0)
		goto out;
	warnings += ret;

	ret = validate_unwind_hints(&file, sec);
	if (ret < 0)
		goto out;
	warnings += ret;

	if (!warnings) {
		ret = validate_reachable_instructions(&file, sec);
		if (ret < 0)
			goto out;
		warnings += ret;
	}

	if (!validate_all)
		goto out;

	ret = validate_retpoline(&file);
	....
Quoted 1 line

that way the general flow is the same regardless...

Ah,... I see what you mean, there's two little wrinkles with that:

- validate_reachable_instructions() is strictly superluous, it does no additional validation between the !vmlinux and vmlinux mode, so I'd put that if (!validate_all) goto out, one up.

- tglx has a patch adding .entry.text to be considered as noinstr as a whole, which has:

@@ -2636,11 +2637,16 @@ static int validate_vmlinux_functions(st
int warnings = 0;

sec = find_section_by_name(file->elf, ".noinstr.text");
- if (!sec)
- return 0;
+ if (sec) {
+ warnings += validate_section(file, sec);
+ warnings += validate_unwind_hints(file, sec);
+ }

- warnings += validate_section(file, sec);
- warnings += validate_unwind_hints(file, sec);
+ sec = find_section_by_name(file->elf, ".entry.text");
+ if (sec) {
+ warnings += validate_section(file, sec);
+ warnings += validate_unwind_hints(file, sec);
+ }

return warnings;
}

Anyway, yes, we can do this on top.

I was going to commit the first 17 patches to tip/core/objtool and repost the remaining 13 once more. And then see how much pain I did to Julien's patches :-)

#88 lore raw

Re: [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation

Quoted 77 lines · Peter Zijlstra
Quoted 42 lines · Josh Poimboeuf
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Josh Poimboeuf

Sure, but couldn't validate_unwind_hints() and validate_reachable_instructions() be changed to *only* run on .noinstr.text, for the vmlinux case? That might help converge the vmlinux and !vmlinux paths.

You're thinking something like so then?

Not exactly. But I don't want to keep churning this patch set. I can add more patches later, so don't worry about it.

But I was thinking it would eventually be good to have the top-level check() be like

	sec = NULL;
	if (!validate_all)
		sec = find_section_by_name(file->elf, ".noinstr.text");

	ret = validate_functions(&file, sec);
	if (ret < 0)
		goto out;
	warnings += ret;

	ret = validate_unwind_hints(&file, sec);
	if (ret < 0)
		goto out;
	warnings += ret;

	if (!warnings) {
		ret = validate_reachable_instructions(&file, sec);
		if (ret < 0)
			goto out;
		warnings += ret;
	}

	if (!validate_all)
		goto out;

	ret = validate_retpoline(&file);
	....
Quoted 1 line

that way the general flow is the same regardless...

Ah,... I see what you mean, there's two little wrinkles with that:

- validate_reachable_instructions() is strictly superluous, it does no additional validation between the !vmlinux and vmlinux mode, so I'd put that if (!validate_all) goto out, one up.

- tglx has a patch adding .entry.text to be considered as noinstr as a whole, which has:

(quoted diff) +9 -4
@@ -2636,11 +2637,16 @@ static int validate_vmlinux_functions(st
  	int warnings = 0;
 
  	sec = find_section_by_name(file->elf, ".noinstr.text");
-	if (!sec)
-		return 0;
+	if (sec) {
+		warnings += validate_section(file, sec);
+		warnings += validate_unwind_hints(file, sec);
+	}
 
-	warnings += validate_section(file, sec);
-	warnings += validate_unwind_hints(file, sec);
+	sec = find_section_by_name(file->elf, ".entry.text");
+	if (sec) {
+		warnings += validate_section(file, sec);
+		warnings += validate_unwind_hints(file, sec);
+	}
 
  	return warnings;
  }
Quoted 6 lines

Anyway, yes, we can do this on top.

I was going to commit the first 17 patches to tip/core/objtool and repost the remaining 13 once more. And then see how much pain I did to Julien's patches :-)

I appreciate the concideration for my patches but, since your patches have been posted a few times already and were already reviewed, you might as well commit them. I'll rebase my patches on top and see the state of things (I'll need to do that with the whole arm64 series anyway).

I'll try to post the new version fast enough so I'm not behind some other major objtool changes :) .

In the mean time I'll have a look at this series and see what I might have to change for the rest of the arm64-objtool set!

Thanks,

Signature · 1 line
Julien Thierry