[RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Peter Zijlstra]

Hi all,

These patches extend objtool to be able to run on vmlinux.o and validate
Thomas's proposed noinstr annotation:

  https://lkml.kernel.org/r/20200310170951.87c29e9c1cfbddd93ccd92b3@kernel.org

 "That's why we want the sections and the annotation. If something calls
  out of a noinstr section into a regular text section and the call is not
  annotated at the call site, then objtool can complain and tell you. What
  Peter and I came up with looks like this:

  noinstr foo()
	do_protected(); <- Safe because in the noinstr section
	instr_begin();  <- Marks the begin of a safe region, ignored
			   by objtool
	do_stuff();     <- All good
	instr_end();    <- End of the safe region. objtool starts
			   looking again
	do_other_stuff();  <- Unsafe because do_other_stuff() is
			      not protected

  and:

  noinstr do_protected()
	bar();          <- objtool will complain here
  "

It should be accompanied by something like the below; which you'll find in a
series by Thomas.

---  

--- a/include/asm-generic/sections.h
+++ b/include/asm-generic/sections.h
@@ -53,6 +53,9 @@ extern char __ctors_start[], __ctors_end
 /* Start and end of .opd section - used for function descriptors. */
 extern char __start_opd[], __end_opd[];
 
+/* Start and end of instrumentation protected text section */
+extern char __noinstr_text_start[], __noinstr_text_end[];
+
 extern __visible const void __nosave_begin, __nosave_end;
 
 /* Function descriptor handling (if any).  Override in asm/sections.h */
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -550,6 +550,10 @@
 #define TEXT_TEXT							\
 		ALIGN_FUNCTION();					\
 		*(.text.hot TEXT_MAIN .text.fixup .text.unlikely)	\
+		ALIGN_FUNCTION();					\
+		__noinstr_text_start = .;				\
+		*(.noinstr.text)					\
+		__noinstr_text_end = .;					\
 		*(.text..refcount)					\
 		*(.ref.text)						\
 	MEM_KEEP(init.text*)						\
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -120,12 +120,37 @@ void ftrace_likely_update(struct ftrace_
 /* Annotate a C jump table to allow objtool to follow the code flow */
 #define __annotate_jump_table __section(.rodata..c_jump_table)
 
+/* Begin/end of an instrumentation safe region */
+#define instr_begin() ({						\
+	asm volatile("%c0:\n\t"						\
+		     ".pushsection .discard.instr_begin\n\t"		\
+		     ".long %c0b - .\n\t"				\
+		     ".popsection\n\t" : : "i" (__COUNTER__));		\
+})
+
+#define instr_end() ({							\
+	asm volatile("%c0:\n\t"						\
+		     ".pushsection .discard.instr_end\n\t"		\
+		     ".long %c0b - .\n\t"				\
+		     ".popsection\n\t" : : "i" (__COUNTER__));		\
+})
+
 #else
 #define annotate_reachable()
 #define annotate_unreachable()
 #define __annotate_jump_table
+#define instr_begin()		do { } while(0)
+#define instr_end()		do { } while(0)
 #endif
 
+#define INSTR(expr) ({			\
+	typeof(({ expr; })) __ret;	\
+	instr_begin();			\
+	__ret = ({ expr; });		\
+	instr_end();			\
+	__ret;				\
+})
+
 #ifndef ASM_UNREACHABLE
 # define ASM_UNREACHABLE
 #endif
--- a/include/linux/compiler_types.h
+++ b/include/linux/compiler_types.h
@@ -118,6 +118,11 @@ struct ftrace_likely_data {
 #define notrace			__attribute__((__no_instrument_function__))
 #endif
 
+/* Section for code which can't be instrumented at all */
+#define noinstr								\
+	notrace __attribute((__section__(".noinstr.text")))
+
+
 /*
  * it doesn't make sense on ARM (currently the only user of __naked)
  * to trace naked functions because then mcount is called without
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -953,7 +953,7 @@ static void check_section(const char *mo
 
 #define DATA_SECTIONS ".data", ".data.rel"
 #define TEXT_SECTIONS ".text", ".text.unlikely", ".sched.text", \
-		".kprobes.text", ".cpuidle.text"
+		".kprobes.text", ".cpuidle.text", ".noinstr.text"
 #define OTHER_TEXT_SECTIONS ".ref.text", ".head.text", ".spinlock.text", \
 		".fixup", ".entry.text", ".exception.text", ".text.*", \
 		".coldtext"

[RFC][PATCH 01/16] objtool: Introduce validate_return()

[Peter Zijlstra]

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

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/check.c |   64 ++++++++++++++++++++++++++++----------------------
 1 file changed, 36 insertions(+), 28 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -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:

[RFC][PATCH 02/16] objtool: Rename func_for_each_insn()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/check.c |   16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -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;

[RFC][PATCH 03/16] objtool: Rename func_for_each_insn_all()

[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

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/check.c |   12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -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;
 

[RFC][PATCH 04/16] objtool: Annotate identity_mapped()

[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. Without the annotation we'll get complaints about the:

	call 1f
1:	popq %rB

construct from the add_call_destinations() pass. Because
identity_mapped() is a SYM_CODE_START_LOCAL_NOALIGN() it is STT_NOTYPE
and we need sym_for_each_insn() to iterate the actual instructions.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 arch/x86/kernel/relocate_kernel_64.S |    2 ++
 include/linux/frame.h                |   16 ++++++++++++++++
 tools/objtool/check.c                |    4 ++--
 3 files changed, 20 insertions(+), 2 deletions(-)

--- a/arch/x86/kernel/relocate_kernel_64.S
+++ b/arch/x86/kernel/relocate_kernel_64.S
@@ -5,6 +5,7 @@
  */
 
 #include <linux/linkage.h>
+#include <linux/frame.h>
 #include <asm/page_types.h>
 #include <asm/kexec.h>
 #include <asm/processor-flags.h>
@@ -210,6 +211,7 @@ SYM_CODE_START_LOCAL_NOALIGN(identity_ma
 	pushq	%rax
 	ret
 SYM_CODE_END(identity_mapped)
+STACK_FRAME_NON_STANDARD(identity_mapped)
 
 SYM_CODE_START_LOCAL_NOALIGN(virtual_mapped)
 	movq	RSP(%r8), %rsp
--- a/include/linux/frame.h
+++ b/include/linux/frame.h
@@ -3,6 +3,9 @@
 #define _LINUX_FRAME_H
 
 #ifdef CONFIG_STACK_VALIDATION
+
+#ifndef __ASSEMBLY__
+
 /*
  * This macro marks the given function's stack frame as "non-standard", which
  * tells objtool to ignore the function when doing stack metadata validation.
@@ -15,6 +18,19 @@
 	static void __used __section(.discard.func_stack_frame_non_standard) \
 		*__func_stack_frame_non_standard_##func = func
 
+#else /* __ASSEMBLY__ */
+
+#define STACK_FRAME_NON_STANDARD(func) \
+	.pushsection .discard.func_stack_frame_non_standard, "aw"; \
+	.align 8; \
+	.type __func_stack_frame_non_standard_##func, @object; \
+	.size __func_stack_frame_non_standard_##func, 8; \
+__func_stack_frame_non_standard_##func: \
+	.quad func; \
+	.popsection
+
+#endif /* __ASSEMBLY */
+
 #else /* !CONFIG_STACK_VALIDATION */
 
 #define STACK_FRAME_NON_STANDARD(func)
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -416,7 +416,7 @@ static void add_ignores(struct objtool_f
 
 		case STT_SECTION:
 			func = find_symbol_by_offset(rela->sym->sec, rela->addend);
-			if (!func || func->type != STT_FUNC)
+			if (!func || (func->type != STT_FUNC && func->type != STT_NOTYPE))
 				continue;
 			break;
 
@@ -425,7 +425,7 @@ static void add_ignores(struct objtool_f
 			continue;
 		}
 
-		func_for_each_insn(file, func, insn)
+		sym_for_each_insn(file, func, insn)
 			insn->ignore = true;
 	}
 }

Re: [RFC][PATCH 04/16] objtool: Annotate identity_mapped()

[Peter Zijlstra]

On Thu, Mar 12, 2020 at 02:41:11PM +0100, Peter Zijlstra wrote:

> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -416,7 +416,7 @@ static void add_ignores(struct objtool_f
>  
>  		case STT_SECTION:
>  			func = find_symbol_by_offset(rela->sym->sec, rela->addend);
> -			if (!func || func->type != STT_FUNC)
> +			if (!func || (func->type != STT_FUNC && func->type != STT_NOTYPE))
>  				continue;
>  			break;
>  
> @@ -425,7 +425,7 @@ static void add_ignores(struct objtool_f
>  			continue;
>  		}
>  
> -		func_for_each_insn(file, func, insn)
> +		sym_for_each_insn(file, func, insn)
>  			insn->ignore = true;
>  	}
>  }


This conflicts with:

  7acfe5315312 ("objtool: Improve call destination function detection")

which wasn't in the tree we were working against :/

I've resolved it something like so.

---
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -406,7 +406,7 @@ static void add_ignores(struct objtool_f
 {
 	struct instruction *insn;
 	struct section *sec;
-	struct symbol *func;
+	struct symbol *sym;
 	struct rela *rela;
 
 	sec = find_section_by_name(file->elf, ".rela.discard.func_stack_frame_non_standard");
@@ -416,12 +416,12 @@ static void add_ignores(struct objtool_f
 	list_for_each_entry(rela, &sec->rela_list, list) {
 		switch (rela->sym->type) {
 		case STT_FUNC:
-			func = rela->sym;
+			sym = rela->sym;
 			break;
 
 		case STT_SECTION:
-			func = find_func_by_offset(rela->sym->sec, rela->addend);
-			if (!func)
+			sym = find_symbol_by_offset(rela->sym->sec, rela->addend);
+			if (!sym || (sym->type != STT_FUNC || sym->type != STT_NOTYPE))
 				continue;
 			break;
 
@@ -430,7 +430,7 @@ static void add_ignores(struct objtool_f
 			continue;
 		}
 
-		sym_for_each_insn(file, func, insn)
+		sym_for_each_insn(file, sym, insn)
 			insn->ignore = true;
 	}
 }

Re: [RFC][PATCH 04/16] objtool: Annotate identity_mapped()

[Josh Poimboeuf]

On Fri, Mar 13, 2020 at 03:34:29PM +0100, Peter Zijlstra wrote:
> This conflicts with:
> 
>   7acfe5315312 ("objtool: Improve call destination function detection")
> 
> which wasn't in the tree we were working against :/
> 
> I've resolved it something like so.
> 
> ---
> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -406,7 +406,7 @@ static void add_ignores(struct objtool_f
>  {
>  	struct instruction *insn;
>  	struct section *sec;
> -	struct symbol *func;
> +	struct symbol *sym;
>  	struct rela *rela;
>  
>  	sec = find_section_by_name(file->elf, ".rela.discard.func_stack_frame_non_standard");
> @@ -416,12 +416,12 @@ static void add_ignores(struct objtool_f
>  	list_for_each_entry(rela, &sec->rela_list, list) {
>  		switch (rela->sym->type) {
>  		case STT_FUNC:
> -			func = rela->sym;
> +			sym = rela->sym;
>  			break;
>  
>  		case STT_SECTION:
> -			func = find_func_by_offset(rela->sym->sec, rela->addend);
> -			if (!func)
> +			sym = find_symbol_by_offset(rela->sym->sec, rela->addend);
> +			if (!sym || (sym->type != STT_FUNC || sym->type != STT_NOTYPE))
                                                           ^^
							   &&

-- 
Josh

Re: [RFC][PATCH 04/16] objtool: Annotate identity_mapped()

[Brian Gerst]

On Thu, Mar 12, 2020 at 9:53 AM Peter Zijlstra <peterz@infradead.org> wrote:
>
> 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. Without the annotation we'll get complaints about the:
>
         call 1f
1:      popq %r8
        subq $(1b - relocate_kernel), %r8

It looks to me that this code is simply trying to get the virtual
address of relocate_kernel using the old 32-bit method of PIC address
calculation.  On 64-bit can be done with leaq relocate_kernel(%rip),
%r8.

--
Brian Gerst

Re: [RFC][PATCH 04/16] objtool: Annotate identity_mapped()

[Peter Zijlstra]

On Fri, Mar 13, 2020 at 12:46:05PM -0400, Brian Gerst wrote:
> On Thu, Mar 12, 2020 at 9:53 AM Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > 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. Without the annotation we'll get complaints about the:
> >
>          call 1f
> 1:      popq %r8
>         subq $(1b - relocate_kernel), %r8
> 
> It looks to me that this code is simply trying to get the virtual
> address of relocate_kernel using the old 32-bit method of PIC address
> calculation.  On 64-bit can be done with leaq relocate_kernel(%rip),
> %r8.

Indeed. Objtool would be happy with that. And it seems I can still kexec
a kernel too.

Thanks!

[RFC][PATCH 05/16] objtool: Optimize find_symbol_by_index()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |   14 ++++++--------
 tools/objtool/elf.h |    3 +--
 2 files changed, 7 insertions(+), 10 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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;
 }
@@ -156,7 +154,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);
 
@@ -289,7 +286,8 @@ 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 */
@@ -415,6 +413,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);
@@ -476,7 +475,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);
 
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -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);
 };
 
 

Re: [RFC][PATCH 05/16] objtool: Optimize find_symbol_by_index()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:12PM +0100, Peter Zijlstra wrote:
> 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.

I remember there was a specific reason for this oddity, but it eludes me
now.

This does make sense, assuming it doesn't break anything.

-- 
Josh

Re: [RFC][PATCH 05/16] objtool: Optimize find_symbol_by_index()

[Josh Poimboeuf]

On Sun, Mar 15, 2020 at 11:09:19AM -0500, Josh Poimboeuf wrote:
> On Thu, Mar 12, 2020 at 02:41:12PM +0100, Peter Zijlstra wrote:
> > 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.
> 
> I remember there was a specific reason for this oddity, but it eludes me
> now.
> 
> This does make sense, assuming it doesn't break anything.

On second thought I guess it was the symbol_list which had this
intentional per-section structure (for a still unremembered reason).

Then the symbol_hash came later, and it just parroted the symbol_list
structure.  So yeah, this change should be fine.

-- 
Josh

Re: [RFC][PATCH 05/16] objtool: Optimize find_symbol_by_index()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:12PM +0100, Peter Zijlstra wrote:
> @@ -289,7 +286,8 @@ 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);

Unnecessary added whitespace.

-- 
Josh

Re: [RFC][PATCH 05/16] objtool: Optimize find_symbol_by_index()

[Miroslav Benes]

> --- a/tools/objtool/elf.h
> +++ b/tools/objtool/elf.h
> @@ -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);
>  };

Not that it really matters, but what was rela_hash in struct elf for 
before this?

Miroslav

Re: [RFC][PATCH 05/16] objtool: Optimize find_symbol_by_index()

[Peter Zijlstra]

On Tue, Mar 17, 2020 at 12:55:01PM +0100, Miroslav Benes wrote:
> > --- a/tools/objtool/elf.h
> > +++ b/tools/objtool/elf.h
> > @@ -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);
> >  };
> 
> Not that it really matters, but what was rela_hash in struct elf for 
> before this?

Unused afaict.

[RFC][PATCH 06/16] objtool: Add a statistics mode

[Peter Zijlstra]

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

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 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(-)

--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -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(),
 };
 
--- a/tools/objtool/builtin.h
+++ b/tools/objtool/builtin.h
@@ -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);
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -234,6 +234,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) {
@@ -268,6 +269,7 @@ static int decode_instructions(struct ob
 				goto err;
 
 			hash_add(file->insn_hash, &insn->hash, insn->offset);
+			nr_insns++;
 			list_add_tail(&insn->list, &file->insn_list);
 		}
 
@@ -286,6 +288,9 @@ static int decode_instructions(struct ob
 		}
 	}
 
+	if (stats)
+		printf("nr_insns: %lu\n", nr_insns);
+
 	return 0;
 
 err:
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -15,6 +15,7 @@
 #include <string.h>
 #include <unistd.h>
 #include <errno.h>
+#include "builtin.h"
 
 #include "elf.h"
 #include "warn.h"
@@ -192,6 +193,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");
@@ -290,6 +294,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) {
@@ -351,6 +358,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)
@@ -365,6 +373,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) {
@@ -392,8 +401,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;

Re: [RFC][PATCH 06/16] objtool: Add a statistics mode

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:13PM +0100, Peter Zijlstra wrote:
> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -234,6 +234,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) {
> @@ -268,6 +269,7 @@ static int decode_instructions(struct ob
>  				goto err;
>  
>  			hash_add(file->insn_hash, &insn->hash, insn->offset);
> +			nr_insns++;
>  			list_add_tail(&insn->list, &file->insn_list);

It's slightly more readable to do the 'nr_insns++' after the
list_add_tail().

-- 
Josh

[RFC][PATCH 07/16] objtool: Optimize find_section_by_index()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |    7 ++++++-
 tools/objtool/elf.h |    2 ++
 2 files changed, 8 insertions(+), 1 deletion(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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;
 
@@ -191,6 +191,8 @@ static int read_sections(struct elf *elf
 			}
 		}
 		sec->len = sec->sh.sh_size;
+
+		hash_add(elf->section_hash, &sec->hash, sec->idx);
 	}
 
 	if (stats)
@@ -430,6 +432,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);
@@ -570,6 +573,8 @@ struct section *elf_create_section(struc
 	shstrtab->len += strlen(name) + 1;
 	shstrtab->changed = true;
 
+	hash_add(elf->section_hash, &sec->hash, sec->idx);
+
 	return sec;
 }
 
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -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);
 };
 
 

Re: [RFC][PATCH 07/16] objtool: Optimize find_section_by_index()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:14PM +0100, Peter Zijlstra wrote:
> 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.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  tools/objtool/elf.c |    7 ++++++-
>  tools/objtool/elf.h |    2 ++
>  2 files changed, 8 insertions(+), 1 deletion(-)
> 
> --- a/tools/objtool/elf.c
> +++ b/tools/objtool/elf.c
> @@ -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;
>  
> @@ -191,6 +191,8 @@ static int read_sections(struct elf *elf
>  			}
>  		}
>  		sec->len = sec->sh.sh_size;
> +
> +		hash_add(elf->section_hash, &sec->hash, sec->idx);

Can you move the

  list_add_tail(&sec->list, &elf->sections);

down here so they're done at the same place?

>  	}
>  
>  	if (stats)
> @@ -430,6 +432,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);
> @@ -570,6 +573,8 @@ struct section *elf_create_section(struc
>  	shstrtab->len += strlen(name) + 1;
>  	shstrtab->changed = true;
>  
> +	hash_add(elf->section_hash, &sec->hash, sec->idx);
> +
>  	return sec;
>  }

Ditto

-- 
Josh

[RFC][PATCH 08/16] Optimize find_section_by_name()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |    9 ++++++++-
 tools/objtool/elf.h |    3 +++
 2 files changed, 11 insertions(+), 1 deletion(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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;
 
@@ -193,6 +198,7 @@ static int read_sections(struct elf *elf
 		sec->len = sec->sh.sh_size;
 
 		hash_add(elf->section_hash, &sec->hash, sec->idx);
+		hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
 	}
 
 	if (stats)
@@ -433,6 +439,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);
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -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);
 };
 
 

Re: [RFC][PATCH 08/16] Optimize find_section_by_name()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:15PM +0100, Peter Zijlstra wrote:
> 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.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>

$SUBJECT needs "objtool: " prefix.

-- 
Josh

Re: [RFC][PATCH 08/16] Optimize find_section_by_name()

[Miroslav Benes]

> @@ -193,6 +198,7 @@ static int read_sections(struct elf *elf
>  		sec->len = sec->sh.sh_size;
>  
>  		hash_add(elf->section_hash, &sec->hash, sec->idx);
> +		hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
>  	}

Don't you need to the same in elf_create_section()?

Miroslav

Re: [RFC][PATCH 08/16] Optimize find_section_by_name()

[Peter Zijlstra]

On Tue, Mar 17, 2020 at 01:22:23PM +0100, Miroslav Benes wrote:
> > @@ -193,6 +198,7 @@ static int read_sections(struct elf *elf
> >  		sec->len = sec->sh.sh_size;
> >  
> >  		hash_add(elf->section_hash, &sec->hash, sec->idx);
> > +		hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
> >  	}
> 
> Don't you need to the same in elf_create_section()?

Yes, already fixed. Noticed it yesterday when I was addressing Josh's
comments.

[RFC][PATCH 09/16] objtool: Optimize find_symbol_*() and read_symbols()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/Build |    5 +
 tools/objtool/elf.c |  186 ++++++++++++++++++++++++++++++++++++----------------
 tools/objtool/elf.h |    3 
 3 files changed, 140 insertions(+), 54 deletions(-)

--- a/tools/objtool/Build
+++ b/tools/objtool/Build
@@ -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)
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -27,6 +27,90 @@ static inline u32 str_hash(const char *s
 	return jhash(str, strlen(str), 0);
 }
 
+static void rb_add(struct rb_root *tree, struct rb_node *node,
+		   int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_node;
+	struct rb_node *parent = NULL;
+
+	while (*link) {
+		parent = *link;
+		if (cmp(node, parent) < 0)
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+}
+
+static struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+			       int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+	struct rb_node *match = NULL;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c <= 0) {
+			if (!c)
+				match = node;
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		}
+	}
+
+	return match;
+}
+
+static struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+				    int (*cmp)(const void *key, const struct rb_node *))
+{
+	node = rb_next(node);
+	if (node && cmp(key, node))
+		node = NULL;
+	return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+	for ((node) = rb_find_first((tree), (key), (cmp)); \
+	     (node); (node) = rb_next_match((node), (key), (cmp)))
+
+static int symbol_to_offset(struct rb_node *a, const struct rb_node *b)
+{
+	struct symbol *sa = rb_entry(a, struct symbol, node);
+	struct symbol *sb = rb_entry(b, struct symbol, node);
+
+	if (sa->offset < sb->offset)
+		return -1;
+	if (sa->offset > sb->offset)
+		return 1;
+
+	if (sa->len < sb->len)
+		return -1;
+	if (sa->len > sb->len)
+		return 1;
+
+	sa->alias = sb;
+
+	return 0;
+}
+
+static int symbol_by_offset(const void *key, const struct rb_node *node)
+{
+	const struct symbol *s = rb_entry(node, struct symbol, node);
+	const unsigned long *o = key;
+
+	if (*o < s->offset)
+		return -1;
+	if (*o > s->offset + s->len)
+		return 1;
+
+	return 0;
+}
+
 struct section *find_section_by_name(struct elf *elf, const char *name)
 {
 	struct section *sec;
@@ -63,37 +147,58 @@ static struct symbol *find_symbol_by_ind
 
 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
 {
-	struct symbol *sym;
+	struct rb_node *node;
 
-	list_for_each_entry(sym, &sec->symbol_list, list)
-		if (sym->type != STT_SECTION &&
-		    sym->offset == offset)
-			return sym;
+	rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+		struct symbol *s = rb_entry(node, struct symbol, node);
+
+		if (s->offset != offset)
+			continue;
+
+		if (s->type != STT_SECTION)
+			return s;
+	}
 
 	return NULL;
 }
 
-struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
+struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
 {
-	struct section *sec;
-	struct symbol *sym;
+	struct rb_node *node;
 
-	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbol_list, list)
-			if (!strcmp(sym->name, name))
-				return sym;
+	rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+		struct symbol *s = rb_entry(node, struct symbol, node);
+
+		if (s->type != STT_SECTION)
+			return s;
+	}
 
 	return NULL;
 }
 
-struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
+struct symbol *find_containing_func(struct section *sec, unsigned long offset)
 {
+	struct rb_node *node;
+
+	rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+		struct symbol *s = rb_entry(node, struct symbol, node);
+
+		if (s->type == STT_FUNC)
+			return s;
+	}
+
+	return NULL;
+}
+
+struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
+{
+	struct section *sec;
 	struct symbol *sym;
 
-	list_for_each_entry(sym, &sec->symbol_list, list)
-		if (sym->type != STT_SECTION &&
-		    offset >= sym->offset && offset < sym->offset + sym->len)
-			return 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;
 
 	return NULL;
 }
@@ -120,18 +225,6 @@ struct rela *find_rela_by_dest(struct se
 	return find_rela_by_dest_range(sec, offset, 1);
 }
 
-struct symbol *find_containing_func(struct section *sec, unsigned long offset)
-{
-	struct symbol *func;
-
-	list_for_each_entry(func, &sec->symbol_list, list)
-		if (func->type == STT_FUNC && offset >= func->offset &&
-		    offset < func->offset + func->len)
-			return func;
-
-	return NULL;
-}
-
 static int read_sections(struct elf *elf)
 {
 	Elf_Scn *s = NULL;
@@ -216,8 +309,9 @@ static int read_sections(struct elf *elf
 static int read_symbols(struct elf *elf)
 {
 	struct section *symtab, *sec;
-	struct symbol *sym, *pfunc, *alias;
-	struct list_head *entry, *tmp;
+	struct symbol *sym, *pfunc;
+	struct list_head *entry;
+	struct rb_node *pnode;
 	int symbols_nr, i;
 	char *coldstr;
 
@@ -236,7 +330,7 @@ static int read_symbols(struct elf *elf)
 			return -1;
 		}
 		memset(sym, 0, sizeof(*sym));
-		alias = sym;
+		sym->alias = sym;
 
 		sym->idx = i;
 
@@ -274,29 +368,13 @@ static int read_symbols(struct elf *elf)
 		sym->offset = sym->sym.st_value;
 		sym->len = sym->sym.st_size;
 
-		/* sorted insert into a per-section list */
-		entry = &sym->sec->symbol_list;
-		list_for_each_prev(tmp, &sym->sec->symbol_list) {
-			struct symbol *s;
-
-			s = list_entry(tmp, struct symbol, list);
-
-			if (sym->offset > s->offset) {
-				entry = tmp;
-				break;
-			}
+		rb_add(&sym->sec->symbol_tree, &sym->node, symbol_to_offset);
 
-			if (sym->offset == s->offset) {
-				if (sym->len && sym->len == s->len && alias == sym)
-					alias = s;
-
-				if (sym->len >= s->len) {
-					entry = tmp;
-					break;
-				}
-			}
-		}
-		sym->alias = alias;
+		pnode = rb_prev(&sym->node);
+		if (pnode)
+			entry = &rb_entry(pnode, struct symbol, node)->list;
+		else
+			entry = &sym->sec->symbol_list;
 		list_add(&sym->list, entry);
 
 		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -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;

Re: [RFC][PATCH 09/16] objtool: Optimize find_symbol_*() and read_symbols()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:16PM +0100, Peter Zijlstra wrote:
> 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.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>

This one also doesn't apply on latest tip.

I assume we also need to optimize the new find_func_by_offset().

-- 
Josh

Re: [RFC][PATCH 09/16] objtool: Optimize find_symbol_*() and read_symbols()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:16PM +0100, Peter Zijlstra wrote:
>  struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
>  {
> -	struct symbol *sym;
> +	struct rb_node *node;
>  
> -	list_for_each_entry(sym, &sec->symbol_list, list)
> -		if (sym->type != STT_SECTION &&
> -		    sym->offset == offset)
> -			return sym;
> +	rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
> +		struct symbol *s = rb_entry(node, struct symbol, node);
> +
> +		if (s->offset != offset)
> +			continue;
> +
> +		if (s->type != STT_SECTION)
> +			return s;
> +	}

Can be simplified to:

		if (s->offset == offset && s->type != STT_SECTION)
			return s;

-- 
Josh

[RFC][PATCH 10/16] objtool: Resize insn_hash

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/check.h |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -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;
 };
 

[RFC][PATCH 11/16] objtool: Optimize find_symbol_by_name()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |   10 +++++-----
 tools/objtool/elf.h |    2 ++
 2 files changed, 7 insertions(+), 5 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -134,13 +134,11 @@ struct symbol *find_symbol_by_offset(str
 
 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;
 }
@@ -365,6 +363,7 @@ static int read_symbols(struct elf *elf)
 		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)
@@ -503,6 +502,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);
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -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);
 };

[RFC][PATCH 12/16] objtool: Optimize read_sections()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c     |   18 ++++++++++++------
 tools/objtool/elf.h     |   18 +++++++++++++++++-
 tools/objtool/orc_gen.c |    3 ++-
 3 files changed, 31 insertions(+), 8 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -210,10 +210,15 @@ 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(sec->elf->rela_hash, rela, hash,
+				       __rela_hash(o, sec->idx)) {
+			if (rela->sec == sec && rela->offset == o)
 				return rela;
+		}
+	}
 
 	return NULL;
 }
@@ -248,9 +253,9 @@ static int read_sections(struct elf *elf
 		}
 		memset(sec, 0, sizeof(*sec));
 
+		sec->elf = elf;
 		INIT_LIST_HEAD(&sec->symbol_list);
 		INIT_LIST_HEAD(&sec->rela_list);
-		hash_init(sec->rela_hash);
 
 		list_add_tail(&sec->list, &elf->sections);
 
@@ -485,7 +490,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);
@@ -518,6 +523,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);
@@ -576,9 +582,9 @@ struct section *elf_create_section(struc
 	}
 	memset(sec, 0, sizeof(*sec));
 
+	sec->elf = elf;
 	INIT_LIST_HEAD(&sec->symbol_list);
 	INIT_LIST_HEAD(&sec->rela_list);
-	hash_init(sec->rela_hash);
 
 	list_add_tail(&sec->list, &elf->sections);
 
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -25,6 +25,8 @@
 #define ELF_C_READ_MMAP ELF_C_READ
 #endif
 
+struct elf;
+
 struct section {
 	struct list_head list;
 	struct hlist_node hash;
@@ -33,7 +35,7 @@ struct section {
 	struct rb_root symbol_tree;
 	struct list_head symbol_list;
 	struct list_head rela_list;
-	DECLARE_HASHTABLE(rela_hash, 16);
+	struct elf *elf;
 	struct section *base, *rela;
 	struct symbol *sym;
 	Elf_Data *data;
@@ -81,8 +83,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 __rela_hash(unsigned long offset, int idx)
+{
+	u32 ol = offset, oh = offset >> 32;
+
+	__jhash_mix(ol, oh, idx);
+
+	return ol;
+}
+
+static inline u32 rela_hash(struct rela *rela)
+{
+	return __rela_hash(rela->offset, rela->sec->idx);
+}
 
 struct elf *elf_read(const char *name, int flags);
 struct section *find_section_by_name(struct elf *elf, const char *name);
--- a/tools/objtool/orc_gen.c
+++ b/tools/objtool/orc_gen.c
@@ -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(ip_relasec->elf->rela_hash, &rela->hash, rela_hash(rela));
 
 	return 0;
 }

Re: [RFC][PATCH 12/16] objtool: Optimize read_sections()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:19PM +0100, Peter Zijlstra wrote:
> +++ b/tools/objtool/elf.h
> @@ -25,6 +25,8 @@
>  #define ELF_C_READ_MMAP ELF_C_READ
>  #endif
>  
> +struct elf;
> +
>  struct section {
>  	struct list_head list;
>  	struct hlist_node hash;
> @@ -33,7 +35,7 @@ struct section {
>  	struct rb_root symbol_tree;
>  	struct list_head symbol_list;
>  	struct list_head rela_list;
> -	DECLARE_HASHTABLE(rela_hash, 16);
> +	struct elf *elf;

Instead of adding 'elf' here I'd rather just add it as an argument to
the find_rela_by_dest*() functions.

-- 
Josh

[RFC][PATCH 13/16] objtool: Delete cleanup()

[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

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/check.c |   19 -------------------
 1 file changed, 19 deletions(-)

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -2520,23 +2520,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)
@@ -2613,8 +2596,6 @@ int check(const char *_objname, bool orc
 	}
 
 out:
-	cleanup(&file);
-
 	/* ignore warnings for now until we get all the code cleaned up */
 	if (ret || warnings)
 		return 0;

[RFC][PATCH 14/16] objtool: Optimize find_rela_by_dest_range()

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |   15 +++++++++++----
 tools/objtool/elf.h |   11 ++++++++++-
 2 files changed, 21 insertions(+), 5 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -204,7 +204,7 @@ struct symbol *find_symbol_by_name(struc
 struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 				     unsigned int len)
 {
-	struct rela *rela;
+	struct rela *rela, *r = NULL;
 	unsigned long o;
 
 	if (!sec->rela)
@@ -212,12 +212,19 @@ struct rela *find_rela_by_dest_range(str
 
 	sec = sec->rela;
 
-	for (o = offset; o < offset + len; o++) {
+	for (o = offset & RELA_STRIDE_MASK; o < offset + len; o += RELA_STRIDE) {
 		hash_for_each_possible(sec->elf->rela_hash, rela, hash,
 				       __rela_hash(o, sec->idx)) {
-			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;
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -86,9 +86,18 @@ struct elf {
 	DECLARE_HASHTABLE(rela_hash, 20);
 };
 
+#define RELA_STRIDE_BITS	4
+#define RELA_STRIDE		(1UL << RELA_STRIDE_BITS)
+#define RELA_STRIDE_MASK	(~(RELA_STRIDE - 1))
+
 static inline u32 __rela_hash(unsigned long offset, int idx)
 {
-	u32 ol = offset, oh = offset >> 32;
+	u32 ol, oh;
+
+	offset &= RELA_STRIDE_MASK;
+
+	ol = offset;
+	oh = offset >> 32;
 
 	__jhash_mix(ol, oh, idx);
 

[RFC][PATCH 15/16] objtool: Implement noinstr validation

[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 the -i "noinstr validation only" option because:

 - vmlinux.o isn't 'clean' vs the existing validations
 - skipping the other validations (which have already been done
   earlier in the build) saves around a second of runtime.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/builtin-check.c |    4 -
 tools/objtool/builtin.h       |    2 
 tools/objtool/check.c         |  155 ++++++++++++++++++++++++++++++++++++------
 tools/objtool/check.h         |    3 
 4 files changed, 140 insertions(+), 24 deletions(-)

--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -17,7 +17,7 @@
 #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, noinstr, vmlinux;
 
 static const char * const check_usage[] = {
 	"objtool check [<options>] file.o",
@@ -32,6 +32,8 @@ 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('i', "noinstr", &noinstr, "noinstr validation only"),
+	OPT_BOOLEAN('l', "vmlinux", &vmlinux, "vmlinux.o validation"),
 	OPT_END(),
 };
 
--- a/tools/objtool/builtin.h
+++ b/tools/objtool/builtin.h
@@ -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, noinstr, vmlinux;
 
 extern int cmd_check(int argc, const char **argv);
 extern int cmd_orc(int argc, const char **argv);
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -1292,6 +1292,53 @@ static int read_retpoline_hints(struct o
 	return 0;
 }
 
+static int read_instr_hints(struct objtool_file *file)
+{
+	struct section *sec;
+	struct instruction *insn;
+	struct rela *rela;
+
+	sec = find_section_by_name(file->elf, ".rela.discard.instr_end");
+	if (!sec)
+		return 0;
+
+	list_for_each_entry(rela, &sec->rela_list, list) {
+		if (rela->sym->type != STT_SECTION) {
+			WARN("unexpected relocation symbol type in %s", sec->name);
+			return -1;
+		}
+
+		insn = find_insn(file, rela->sym->sec, rela->addend);
+		if (!insn) {
+			WARN("bad .discard.instr_end entry");
+			return -1;
+		}
+
+		insn->instr--;
+	}
+
+	sec = find_section_by_name(file->elf, ".rela.discard.instr_begin");
+	if (!sec)
+		return 0;
+
+	list_for_each_entry(rela, &sec->rela_list, list) {
+		if (rela->sym->type != STT_SECTION) {
+			WARN("unexpected relocation symbol type in %s", sec->name);
+			return -1;
+		}
+
+		insn = find_insn(file, rela->sym->sec, rela->addend);
+		if (!insn) {
+			WARN("bad .discard.instr_begin entry");
+			return -1;
+		}
+
+		insn->instr++;
+	}
+
+	return 0;
+}
+
 static void mark_rodata(struct objtool_file *file)
 {
 	struct section *sec;
@@ -1363,6 +1410,10 @@ static int decode_sections(struct objtoo
 	if (ret)
 		return ret;
 
+	ret = read_instr_hints(file);
+	if (ret)
+		return ret;
+
 	return 0;
 }
 
@@ -1914,6 +1965,14 @@ static inline const char *call_dest_name
 
 static int validate_call(struct instruction *insn, struct insn_state *state)
 {
+	if (state->noinstr && state->instr <= 0 &&
+	    (!insn->call_dest || insn->call_dest->sec != insn->sec)) {
+		WARN_FUNC("call to %s() leaves .noinstr.text section",
+				insn->sec, insn->offset, call_dest_name(insn));
+		return 1;
+	}
+
+
 	if (state->uaccess && !func_uaccess_safe(insn->call_dest)) {
 		WARN_FUNC("call to %s() with UACCESS enabled",
 				insn->sec, insn->offset, call_dest_name(insn));
@@ -1942,6 +2001,12 @@ static int validate_sibling_call(struct
 
 static int validate_return(struct symbol *func, struct instruction *insn, struct insn_state *state)
 {
+	if (state->noinstr && state->instr > 0) {
+		WARN_FUNC("return with instrumentation enabled",
+			  insn->sec, insn->offset);
+		return 1;
+	}
+
 	if (state->uaccess && !func_uaccess_safe(func)) {
 		WARN_FUNC("return with UACCESS enabled",
 			  insn->sec, insn->offset);
@@ -2023,6 +2088,9 @@ static int validate_branch(struct objtoo
 				return 0;
 		}
 
+		if (state.noinstr)
+			state.instr += insn->instr;
+
 		if (insn->hint) {
 			if (insn->restore) {
 				struct instruction *save_insn, *i;
@@ -2355,9 +2423,8 @@ static bool ignore_unreachable_insn(stru
 	return false;
 }
 
-static int validate_functions(struct objtool_file *file)
+static int validate_sec_functions(struct objtool_file *file, struct section *sec)
 {
-	struct section *sec;
 	struct symbol *func;
 	struct instruction *insn;
 	struct insn_state state;
@@ -2370,33 +2437,68 @@ 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;
+	/*
+	 * We need the full vmlinux for noinstr validation, otherwise we can
+	 * not correctly determine insn->call_dest->sec (external symbols do
+	 * not have a section).
+	 */
+	if (vmlinux && !strcmp(sec->name, ".noinstr.text"))
+		state.noinstr = true;
 
-			if (!func->len) {
-				WARN("%s() is missing an ELF size annotation",
-				     func->name);
-				warnings++;
-			}
+	list_for_each_entry(func, &sec->symbol_list, list) {
+		if (func->type != STT_FUNC)
+			continue;
 
-			if (func->pfunc != func || func->alias != func)
-				continue;
+		if (!func->len) {
+			WARN("%s() is missing an ELF size annotation",
+					func->name);
+			warnings++;
+		}
 
-			insn = find_insn(file, sec, func->offset);
-			if (!insn || insn->ignore || insn->visited)
-				continue;
+		if (func->pfunc != func || func->alias != func)
+			continue;
 
-			state.uaccess = func->uaccess_safe;
+		insn = find_insn(file, sec, func->offset);
+		if (!insn || insn->ignore || insn->visited)
+			continue;
 
-			ret = validate_branch(file, func, insn, state);
-			if (ret && backtrace)
-				BT_FUNC("<=== (func)", insn);
-			warnings += ret;
-		}
+		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_noinstr_functions(struct objtool_file *file)
+{
+	struct section *sec;
+
+	if (!vmlinux) {
+		WARN("noinstr validation needs vmlinux\n");
+		return -1;
 	}
 
+	sec = find_section_by_name(file->elf, ".noinstr.text");
+	if (!sec) {
+		WARN("No .noinstr.text section");
+		return -1;
+	}
+
+	return validate_sec_functions(file, sec);
+}
+
+static int validate_functions(struct objtool_file *file)
+{
+	struct section *sec;
+	int warnings = 0;
+
+	for_each_sec(file, sec)
+		warnings += validate_sec_functions(file, sec);
+
 	return warnings;
 }
 
@@ -2446,6 +2548,15 @@ int check(const char *_objname, bool orc
 	if (list_empty(&file.insn_list))
 		goto out;
 
+	if (noinstr) {
+		ret = validate_noinstr_functions(&file);
+		if (ret < 0)
+			goto out;
+
+		warnings += ret;
+		goto out;
+	}
+
 	if (retpoline) {
 		ret = validate_retpoline(&file);
 		if (ret < 0)
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -20,6 +20,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];
@@ -35,6 +37,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;

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:22PM +0100, Peter Zijlstra wrote:
> 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 the -i "noinstr validation only" option because:
> 
>  - vmlinux.o isn't 'clean' vs the existing validations
>  - skipping the other validations (which have already been done
>    earlier in the build) saves around a second of runtime.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>

I find the phrase "noinstr" to be WAY too ambiguous.  To my brain it
clearly stands for "no instructions" and I have to do a double take
every time I read it.

And "read_instr_hints" reads as "read_instruction_hints()".

Can we come up with a more readable name?  Why not just "notrace"?

The trace begin/end annotations could be

  trace_allow_begin()
  trace_allow_end()

Also -- what happens when a function belongs in both .notrace.text and
in one of the other special-purpose sections like .sched.text,
.meminit.text or .entry.text?

Maybe storing pointers to the functions, like NOKPROBE_SYMBOL does,
would be better than putting the functions in a separate section.

> ---
>  tools/objtool/builtin-check.c |    4 -
>  tools/objtool/builtin.h       |    2 
>  tools/objtool/check.c         |  155 ++++++++++++++++++++++++++++++++++++------
>  tools/objtool/check.h         |    3 
>  4 files changed, 140 insertions(+), 24 deletions(-)
> 
> --- a/tools/objtool/builtin-check.c
> +++ b/tools/objtool/builtin-check.c
> @@ -17,7 +17,7 @@
>  #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, noinstr, vmlinux;
>  
>  static const char * const check_usage[] = {
>  	"objtool check [<options>] file.o",
> @@ -32,6 +32,8 @@ 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('i', "noinstr", &noinstr, "noinstr validation only"),
> +	OPT_BOOLEAN('l', "vmlinux", &vmlinux, "vmlinux.o validation"),
>  	OPT_END(),
>  };

It seems like there should be an easy way to auto-detect vmlinux.o,
without needing a cmdline option.

For example, if the file name is "vmlinux.o" :-)

Also, maybe we can just hard-code the fact that vmlinux.o is always
noinstr-only.  Over time we'll probably need to move more per-.o
functionalities to vmlinux.o and I think we should avoid creating a
bunch of cmdline options.

-- 
Josh

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Peter Zijlstra]

On Sun, Mar 15, 2020 at 01:03:20PM -0500, Josh Poimboeuf wrote:
> On Thu, Mar 12, 2020 at 02:41:22PM +0100, Peter Zijlstra wrote:
> > 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 the -i "noinstr validation only" option because:
> > 
> >  - vmlinux.o isn't 'clean' vs the existing validations
> >  - skipping the other validations (which have already been done
> >    earlier in the build) saves around a second of runtime.
> > 
> > Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> I find the phrase "noinstr" to be WAY too ambiguous.  To my brain it
> clearly stands for "no instructions" and I have to do a double take
> every time I read it.

Thing is, we use insn for instruction all over both arch/x86/ and
objtool.

My personal naming preference didn't make it due to CoC reasons :-/

> And "read_instr_hints" reads as "read_instruction_hints()".
> 
> Can we come up with a more readable name?  Why not just "notrace"?
> 
> The trace begin/end annotations could be
> 
>   trace_allow_begin()
>   trace_allow_end()

notrace already exists and we didn't want to confuse things further.

> Also -- what happens when a function belongs in both .notrace.text and
> in one of the other special-purpose sections like .sched.text,
> .meminit.text or .entry.text?

Hasn't happened yet, initially we were thinking of using .entry.text for
this as a whole, but decided against that due to how .entry.text is
special for PTI (although exposing most of this code really wouldn't
matter).

The thing with .sched.text is that we really should never call into
scheduling from these contexts anyway. We've not ran into meminit yet.
(all this finicky entry code is ran with IRQs disabled).

The one that could potentially interfere is .cpuidle.text.

> Maybe storing pointers to the functions, like NOKPROBE_SYMBOL does,
> would be better than putting the functions in a separate section.

Thing is, I really _hate_ that annotation style.

> > ---
> >  tools/objtool/builtin-check.c |    4 -
> >  tools/objtool/builtin.h       |    2 
> >  tools/objtool/check.c         |  155 ++++++++++++++++++++++++++++++++++++------
> >  tools/objtool/check.h         |    3 
> >  4 files changed, 140 insertions(+), 24 deletions(-)
> > 
> > --- a/tools/objtool/builtin-check.c
> > +++ b/tools/objtool/builtin-check.c
> > @@ -17,7 +17,7 @@
> >  #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, noinstr, vmlinux;
> >  
> >  static const char * const check_usage[] = {
> >  	"objtool check [<options>] file.o",
> > @@ -32,6 +32,8 @@ 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('i', "noinstr", &noinstr, "noinstr validation only"),
> > +	OPT_BOOLEAN('l', "vmlinux", &vmlinux, "vmlinux.o validation"),
> >  	OPT_END(),
> >  };
> 
> It seems like there should be an easy way to auto-detect vmlinux.o,
> without needing a cmdline option.
> 
> For example, if the file name is "vmlinux.o" :-)

Fair enough I suppose...

> Also, maybe we can just hard-code the fact that vmlinux.o is always
> noinstr-only.  Over time we'll probably need to move more per-.o
> functionalities to vmlinux.o and I think we should avoid creating a
> bunch of cmdline options.

but you're ruining things here, see, for a regular x86_64 config, we'd
run this with:

	objtool check -fail vmlinux.o

And I was hoping to get vmlinux.o objtool clean, surprisingly there
really aren't that many complaints. But the -i thing makes it run
significantly faster without duplicating all the bits we've already
checked.

Anyway, let me address and refresh the series while we bicket about
naming later. I'm thikning Thomas would much prefer to get his first
round of patches out first.

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Josh Poimboeuf]

On Mon, Mar 16, 2020 at 02:24:19PM +0100, Peter Zijlstra wrote:
> > And "read_instr_hints" reads as "read_instruction_hints()".
> > 
> > Can we come up with a more readable name?  Why not just "notrace"?
> > 
> > The trace begin/end annotations could be
> > 
> >   trace_allow_begin()
> >   trace_allow_end()
> 
> notrace already exists and we didn't want to confuse things further.

Um, why would it confuse things to call a section of notrace code
".notrace.text"???

> > Also -- what happens when a function belongs in both .notrace.text and
> > in one of the other special-purpose sections like .sched.text,
> > .meminit.text or .entry.text?
> 
> Hasn't happened yet, initially we were thinking of using .entry.text for
> this as a whole, but decided against that due to how .entry.text is
> special for PTI (although exposing most of this code really wouldn't
> matter).
> 
> The thing with .sched.text is that we really should never call into
> scheduling from these contexts anyway. We've not ran into meminit yet.
> (all this finicky entry code is ran with IRQs disabled).
> 
> The one that could potentially interfere is .cpuidle.text.
> 
> > Maybe storing pointers to the functions, like NOKPROBE_SYMBOL does,
> > would be better than putting the functions in a separate section.
> 
> Thing is, I really _hate_ that annotation style.

I do too, but I get the feeling this "put everything in its own section"
thing is going to bite us.

> > Also, maybe we can just hard-code the fact that vmlinux.o is always
> > noinstr-only.  Over time we'll probably need to move more per-.o
> > functionalities to vmlinux.o and I think we should avoid creating a
> > bunch of cmdline options.
> 
> but you're ruining things here, see, for a regular x86_64 config, we'd
> run this with:
> 
> 	objtool check -fail vmlinux.o
>
> And I was hoping to get vmlinux.o objtool clean, surprisingly there
> really aren't that many complaints. But the -i thing makes it run
> significantly faster without duplicating all the bits we've already
> checked.

My suggestion is that the "-i" option would be hard-coded (for now).  So
nothing extra would get checked.

-- 
Josh

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Josh Poimboeuf]

On Mon, Mar 16, 2020 at 11:19:07AM -0500, Josh Poimboeuf wrote:
> > And I was hoping to get vmlinux.o objtool clean, surprisingly there
> > really aren't that many complaints. But the -i thing makes it run
> > significantly faster without duplicating all the bits we've already
> > checked.
> 
> My suggestion is that the "-i" option would be hard-coded (for now).  So
> nothing extra would get checked.

If that wasn't clear, I mean that for vmlinux.o we'd only do the
instr-checking.  For individual .o's we'd do everything else.

-- 
Josh

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Peter Zijlstra]

On Mon, Mar 16, 2020 at 11:21:47AM -0500, Josh Poimboeuf wrote:
> On Mon, Mar 16, 2020 at 11:19:07AM -0500, Josh Poimboeuf wrote:
> > > And I was hoping to get vmlinux.o objtool clean, surprisingly there
> > > really aren't that many complaints. But the -i thing makes it run
> > > significantly faster without duplicating all the bits we've already
> > > checked.
> > 
> > My suggestion is that the "-i" option would be hard-coded (for now).  So
> > nothing extra would get checked.
> 
> If that wasn't clear, I mean that for vmlinux.o we'd only do the
> instr-checking.  For individual .o's we'd do everything else.

That'd get in the way of making vmlinux.o objtool clean though :/

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Peter Zijlstra]

On Mon, Mar 16, 2020 at 11:19:04AM -0500, Josh Poimboeuf wrote:
> On Mon, Mar 16, 2020 at 02:24:19PM +0100, Peter Zijlstra wrote:
> > > And "read_instr_hints" reads as "read_instruction_hints()".
> > > 
> > > Can we come up with a more readable name?  Why not just "notrace"?
> > > 
> > > The trace begin/end annotations could be
> > > 
> > >   trace_allow_begin()
> > >   trace_allow_end()
> > 
> > notrace already exists and we didn't want to confuse things further.
> 
> Um, why would it confuse things to call a section of notrace code
> ".notrace.text"???

Because it is strictly stronger than the notrace attribute is. And we
certainly don't want all that is now marked notrace to end up there.

Our section also very much excludes kprobes and hardware breakpoints for
starters.

Re: [RFC][PATCH 15/16] objtool: Implement noinstr validation

[Josh Poimboeuf]

On Mon, Mar 16, 2020 at 05:48:27PM +0100, Peter Zijlstra wrote:
> On Mon, Mar 16, 2020 at 11:19:04AM -0500, Josh Poimboeuf wrote:
> > On Mon, Mar 16, 2020 at 02:24:19PM +0100, Peter Zijlstra wrote:
> > > > And "read_instr_hints" reads as "read_instruction_hints()".
> > > > 
> > > > Can we come up with a more readable name?  Why not just "notrace"?
> > > > 
> > > > The trace begin/end annotations could be
> > > > 
> > > >   trace_allow_begin()
> > > >   trace_allow_end()
> > > 
> > > notrace already exists and we didn't want to confuse things further.
> > 
> > Um, why would it confuse things to call a section of notrace code
> > ".notrace.text"???
> 
> Because it is strictly stronger than the notrace attribute is. And we
> certainly don't want all that is now marked notrace to end up there.

Ok, I must have misunderstood, I thought it was *all* notrace code going
in there.

I still hope we can come up with a better name.

-- 
Josh

[RFC][PATCH 16/16] objtool: Optimize !vmlinux.o again

[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

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |   40 ++++++++++++++++++++++++++++------------
 tools/objtool/elf.h |    4 ++--
 2 files changed, 30 insertions(+), 14 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -27,6 +27,21 @@ static inline u32 str_hash(const char *s
 	return jhash(str, strlen(str), 0);
 }
 
+static inline int elf_hash_bits(void)
+{
+	return vmlinux ? 20 : 16;
+}
+
+static inline void elf_hash_add(struct hlist_head *table, struct hlist_node *node, u32 key)
+{
+	hlist_add_head(node, &table[hash_32(key, elf_hash_bits())]);
+}
+
+static void elf_hash_init(struct hlist_head *table)
+{
+	__hash_init(table, 1U << elf_hash_bits());
+}
+
 static void rb_add(struct rb_root *tree, struct rb_node *node,
 		   int (*cmp)(struct rb_node *, const struct rb_node *))
 {
@@ -300,8 +315,8 @@ static int read_sections(struct elf *elf
 		}
 		sec->len = sec->sh.sh_size;
 
-		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)
@@ -387,8 +402,8 @@ 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));
+		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)
@@ -497,7 +512,7 @@ static int read_relas(struct elf *elf)
 			}
 
 			list_add_tail(&rela->list, &sec->rela_list);
-			hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+			elf_hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
 			nr_rela++;
 		}
 		max_rela = max(max_rela, nr_rela);
@@ -524,15 +539,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",
@@ -671,7 +687,7 @@ struct section *elf_create_section(struc
 	shstrtab->len += strlen(name) + 1;
 	shstrtab->changed = true;
 
-	hash_add(elf->section_hash, &sec->hash, sec->idx);
+	elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
 
 	return sec;
 }
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -81,8 +81,8 @@ struct elf {
 	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(section_hash, 20);
+	DECLARE_HASHTABLE(section_name_hash, 20);
 	DECLARE_HASHTABLE(rela_hash, 20);
 };
 

[RFC][PATCH v2 16/16] objtool: Optimize !vmlinux.o again

[Peter Zijlstra]

Turns out I lost a refresh on this one.

---
Subject: objtool: Optimize !vmlinux.o again
From: Peter Zijlstra <peterz@infradead.org>
Date: Thu Mar 12 14:29:38 CET 2020

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

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 tools/objtool/elf.c |   51 ++++++++++++++++++++++++++++++++++-----------------
 tools/objtool/elf.h |    4 ++--
 2 files changed, 36 insertions(+), 19 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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 ? 20 : 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;
 
@@ -194,7 +210,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;
 
@@ -213,7 +229,7 @@ struct rela *find_rela_by_dest_range(str
 	sec = sec->rela;
 
 	for (o = offset & RELA_STRIDE_MASK; o < offset + len; o += RELA_STRIDE) {
-		hash_for_each_possible(sec->elf->rela_hash, rela, hash,
+		elf_hash_for_each_possible(sec->elf->rela_hash, rela, hash,
 				       __rela_hash(o, sec->idx)) {
 			if (rela->sec != sec)
 				continue;
@@ -300,8 +316,8 @@ static int read_sections(struct elf *elf
 		}
 		sec->len = sec->sh.sh_size;
 
-		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)
@@ -387,8 +403,8 @@ 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));
+		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)
@@ -497,7 +513,7 @@ static int read_relas(struct elf *elf)
 			}
 
 			list_add_tail(&rela->list, &sec->rela_list);
-			hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+			elf_hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
 			nr_rela++;
 		}
 		max_rela = max(max_rela, nr_rela);
@@ -524,15 +540,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",
@@ -671,7 +688,7 @@ struct section *elf_create_section(struc
 	shstrtab->len += strlen(name) + 1;
 	shstrtab->changed = true;
 
-	hash_add(elf->section_hash, &sec->hash, sec->idx);
+	elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
 
 	return sec;
 }
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -81,8 +81,8 @@ struct elf {
 	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(section_hash, 20);
+	DECLARE_HASHTABLE(section_name_hash, 20);
 	DECLARE_HASHTABLE(rela_hash, 20);
 };
 

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Peter Zijlstra]

On Thu, Mar 12, 2020 at 02:41:07PM +0100, Peter Zijlstra wrote:
> Hi all,
> 
> These patches extend objtool to be able to run on vmlinux.o and validate
> Thomas's proposed noinstr annotation:
> 
>   https://lkml.kernel.org/r/20200310170951.87c29e9c1cfbddd93ccd92b3@kernel.org
> 
>  "That's why we want the sections and the annotation. If something calls
>   out of a noinstr section into a regular text section and the call is not
>   annotated at the call site, then objtool can complain and tell you. What
>   Peter and I came up with looks like this:
> 
>   noinstr foo()
> 	do_protected(); <- Safe because in the noinstr section
> 	instr_begin();  <- Marks the begin of a safe region, ignored
> 			   by objtool
> 	do_stuff();     <- All good
> 	instr_end();    <- End of the safe region. objtool starts
> 			   looking again
> 	do_other_stuff();  <- Unsafe because do_other_stuff() is
> 			      not protected
> 
>   and:
> 
>   noinstr do_protected()
> 	bar();          <- objtool will complain here
>   "
> 
> It should be accompanied by something like the below; which you'll find in a
> series by Thomas.
> 

So one of the problem i've ran into while playing with this and Thomas'
patches is that it is 'difficult' to deal with indirect function calls.

objtool basically gives up instantly.

I know smatch has passes were it looks for function pointer assignments
and carries that forward into it's callchain generation. Doing something
like that for objtool is going to be 'fun'...

For now I've got limited success dodging a few instances with
__always_inline (which then results in the compiler resolving the
indirection).

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 05:23:37PM +0100, Peter Zijlstra wrote:
> So one of the problem i've ran into while playing with this and Thomas'
> patches is that it is 'difficult' to deal with indirect function calls.
> 
> objtool basically gives up instantly.
> 
> I know smatch has passes were it looks for function pointer assignments
> and carries that forward into it's callchain generation. Doing something
> like that for objtool is going to be 'fun'...

Yeah, it would have to keep track of register and memory values, even
across function calls.  Which is basically crossing over into emulation
territory.  Which objtool wasn't really built for.

-- 
Josh

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Peter Zijlstra]

On Thu, Mar 12, 2020 at 05:23:37PM +0100, Peter Zijlstra wrote:

> So one of the problem i've ran into while playing with this and Thomas'
> patches is that it is 'difficult' to deal with indirect function calls.
> 
> objtool basically gives up instantly.
> 
> I know smatch has passes were it looks for function pointer assignments
> and carries that forward into it's callchain generation. Doing something
> like that for objtool is going to be 'fun'...
> 
> For now I've got limited success dodging a few instances with
> __always_inline (which then results in the compiler resolving the
> indirection).

Here's a little something that at least detects 'immediate' function
pointers crossing the boundary.

It's slow though; it almost tripples the runtime. But I'm too tired to
make it fast, maybe tomorrow.

---

--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -247,6 +247,9 @@ static int decode_instructions(struct ob
 		    strncmp(sec->name, ".discard.", 9))
 			sec->text = true;

+		if (!strcmp(sec->name, ".noinstr.text"))
+			sec->noinstr = true;
+
 		for (offset = 0; offset < sec->len; offset += insn->len) {
 			insn = malloc(sizeof(*insn));
 			if (!insn) {
@@ -2040,6 +2043,28 @@ static int validate_return(struct symbol
 	return 0;
 }

+static int validate_rela(struct instruction *insn, struct insn_state *state)
+{
+	struct section *sec;
+	struct rela *rela;
+
+	if (!(state->noinstr && state->instr <= 0))
+		return 0;
+
+	rela = find_rela_by_dest_range(insn->sec, insn->offset, insn->len);
+	if (!rela || !rela->sym || !rela->sym->sec)
+		return 0;
+
+	sec = rela->sym->sec;
+	if (sec->text && !sec->noinstr) {
+		WARN_FUNC("loading non-noinstr function pointer\n",
+			  insn->sec, insn->offset);
+		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
@@ -2222,6 +2247,10 @@ static int validate_branch(struct objtoo
 			return 0;

 		case INSN_STACK:
+			ret = validate_rela(insn, &state);
+			if (ret)
+				return ret;
+
 			if (update_insn_state(insn, &state))
 				return 1;

@@ -2285,6 +2314,10 @@ static int validate_branch(struct objtoo
 			break;

 		default:
+			ret = validate_rela(insn, &state);
+			if (ret)
+				return ret;
+
 			break;
 		}

@@ -2442,8 +2475,8 @@ static int validate_sec_functions(struct
 	 * not correctly determine insn->call_dest->sec (external symbols do
 	 * not have a section).
 	 */
-	if (vmlinux && !strcmp(sec->name, ".noinstr.text"))
-		state.noinstr = true;
+	if (vmlinux)
+		state.noinstr = sec->noinstr;

 	list_for_each_entry(func, &sec->symbol_list, list) {
 		if (func->type != STT_FUNC)
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -43,7 +43,7 @@ struct section {
 	char *name;
 	int idx;
 	unsigned int len;
-	bool changed, text, rodata;
+	bool changed, text, rodata, noinstr;
 };

 struct symbol {

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Masami Hiramatsu]

On Thu, 12 Mar 2020 17:23:37 +0100
Peter Zijlstra <peterz@infradead.org> wrote:

> On Thu, Mar 12, 2020 at 02:41:07PM +0100, Peter Zijlstra wrote:
> > Hi all,
> > 
> > These patches extend objtool to be able to run on vmlinux.o and validate
> > Thomas's proposed noinstr annotation:
> > 
> >   https://lkml.kernel.org/r/20200310170951.87c29e9c1cfbddd93ccd92b3@kernel.org
> > 
> >  "That's why we want the sections and the annotation. If something calls
> >   out of a noinstr section into a regular text section and the call is not
> >   annotated at the call site, then objtool can complain and tell you. What
> >   Peter and I came up with looks like this:
> > 
> >   noinstr foo()
> > 	do_protected(); <- Safe because in the noinstr section
> > 	instr_begin();  <- Marks the begin of a safe region, ignored
> > 			   by objtool
> > 	do_stuff();     <- All good
> > 	instr_end();    <- End of the safe region. objtool starts
> > 			   looking again
> > 	do_other_stuff();  <- Unsafe because do_other_stuff() is
> > 			      not protected
> > 
> >   and:
> > 
> >   noinstr do_protected()
> > 	bar();          <- objtool will complain here
> >   "
> > 
> > It should be accompanied by something like the below; which you'll find in a
> > series by Thomas.
> > 
> 
> So one of the problem i've ran into while playing with this and Thomas'
> patches is that it is 'difficult' to deal with indirect function calls.
> 
> objtool basically gives up instantly.

Can we introduce a "safe-call" wrapper function instead of indirect
call, and if objtool found an indirect call without safe-call function,
it can make it an error?

static int __noinstr safe_indirect_callback(int (*fn)(...), real-args)
{
	if (!is_instr_text(fn))
		return -ERANGE;
	return fn(real-args)
}

BTW, out of curiously, if BUG*() or WARN*() cases happens in the noinstr
section, do we also need to move them (register dump, stack unwinding,
printk, console output, etc.) all into noinstr section?

Thank you,

-- 
Masami Hiramatsu <mhiramat@kernel.org>

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Thomas Gleixner]

Masami Hiramatsu <mhiramat@kernel.org> writes:
> BTW, out of curiously, if BUG*() or WARN*() cases happens in the noinstr
> section, do we also need to move them (register dump, stack unwinding,
> printk, console output, etc.) all into noinstr section?

The current plan is to declare BUG()/WARN() "safe". On x86 it is kinda
safe as it uses UD2. That raises an exception which handles the bug/warn
after establishing the correct state.

Of course it's debatable, but moving all of this into the noinstr
section might be just a too wide scope.

Thanks,

        tglx

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Masami Hiramatsu]

On Tue, 17 Mar 2020 10:26:49 +0100
Thomas Gleixner <tglx@linutronix.de> wrote:

> Masami Hiramatsu <mhiramat@kernel.org> writes:
> > BTW, out of curiously, if BUG*() or WARN*() cases happens in the noinstr
> > section, do we also need to move them (register dump, stack unwinding,
> > printk, console output, etc.) all into noinstr section?
> 
> The current plan is to declare BUG()/WARN() "safe". On x86 it is kinda
> safe as it uses UD2. That raises an exception which handles the bug/warn
> after establishing the correct state.

OK, so at least the entry of BUG()/WARN() is in noinstr, but the
register/stack dump routines are out of noinstr.

> 
> Of course it's debatable, but moving all of this into the noinstr
> section might be just a too wide scope.

Agreed.

Thank you,

-- 
Masami Hiramatsu <mhiramat@kernel.org>

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Peter Zijlstra]

On Tue, Mar 17, 2020 at 09:56:28AM +0900, Masami Hiramatsu wrote:
> On Thu, 12 Mar 2020 17:23:37 +0100
> Peter Zijlstra <peterz@infradead.org> wrote:

> > So one of the problem i've ran into while playing with this and Thomas'
> > patches is that it is 'difficult' to deal with indirect function calls.
> > 
> > objtool basically gives up instantly.
> 
> Can we introduce a "safe-call" wrapper function instead of indirect
> call, and if objtool found an indirect call without safe-call function,
> it can make it an error?
> 
> static int __noinstr safe_indirect_callback(int (*fn)(...), real-args)
> {
> 	if (!is_instr_text(fn))
> 		return -ERANGE;
> 	return fn(real-args)
> }

That is a runtime test and as such susceptible to code coverage issues.

I could probably frob a few cases manually in objtool; so far I've
managed to just make them go away.

> BTW, out of curiously, if BUG*() or WARN*() cases happens in the noinstr
> section, do we also need to move them (register dump, stack unwinding,
> printk, console output, etc.) all into noinstr section?

Since BUG/WARN should not happen, we've added instr_begin()/instr_end()
to their slow path. If those trigger, we've got bigger issues.

Re: [RFC][PATCH 00/16] objtool: vmlinux.o and noinstr validation

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:07PM +0100, Peter Zijlstra wrote:
> Hi all,
> 
> These patches extend objtool to be able to run on vmlinux.o and validate
> Thomas's proposed noinstr annotation:
> 
>   https://lkml.kernel.org/r/20200310170951.87c29e9c1cfbddd93ccd92b3@kernel.org
> 
>  "That's why we want the sections and the annotation. If something calls
>   out of a noinstr section into a regular text section and the call is not
>   annotated at the call site, then objtool can complain and tell you. What
>   Peter and I came up with looks like this:
> 
>   noinstr foo()
> 	do_protected(); <- Safe because in the noinstr section
> 	instr_begin();  <- Marks the begin of a safe region, ignored
> 			   by objtool
> 	do_stuff();     <- All good
> 	instr_end();    <- End of the safe region. objtool starts
> 			   looking again
> 	do_other_stuff();  <- Unsafe because do_other_stuff() is
> 			      not protected
> 
>   and:
> 
>   noinstr do_protected()
> 	bar();          <- objtool will complain here
>   "
> 
> It should be accompanied by something like the below; which you'll find in a
> series by Thomas.

Awesome work!

This is also a big step towards other eventual objtool features, like
LTO compatibility.

I did have a few concerns about the overall "noinstr" implementation,
mentioned in my reply to patch 15.

Other than that, and the minor comments I sent, the code looks great.

-- 
Josh