Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1353841 > unrolled thread

[PATCH 00/11] Various objtool fixes

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH 00/11] Various objtool fixes Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
    [PATCH 01/11] objtool: Prevent infinite recursion in noreturn detection Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
      [tip:core/objtool] objtool: Prevent infinite recursion in noreturn  detection tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 05/11] objtool: Add helper macros for traversing instructions Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
      [tip:core/objtool] objtool: Add helper macros for traversing  instructions tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 10/11] objtool: Add several performance improvements Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
      [tip:core/objtool] objtool: Add several performance improvements tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 03/11] objtool: Compile with debugging symbols Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
      [tip:core/objtool] objtool: Compile with debugging symbols tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 04/11] objtool: Fix false positive warnings related to sibling calls Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
      [tip:core/objtool] objtool: Fix false positive warnings related to  sibling calls tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 02/11] objtool: Detect infinite recursion Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
      [tip:core/objtool] objtool: Detect infinite recursion tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 06/11] objtool: Remove superflous INIT_LIST_HEAD Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
      [tip:core/objtool] objtool: Remove superflous INIT_LIST_HEAD tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 07/11] objtool: Rename some variables and functions Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
      [tip:core/objtool] objtool: Rename some variables and functions tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 08/11] objtool: Fix false positive warnings for functions with multiple switch statements Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
      [tip:core/objtool] objtool: Fix false positive warnings for  functions with multiple switch statements tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
    [PATCH 09/11] tools/objtool: Copy hashtable.h into tools directory Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
      Re: [PATCH 09/11] tools/objtool: Copy hashtable.h into tools  directory Ingo Molnar <mingo@kernel.org> - 2016-03-09 10:50 +0100
        Re: [PATCH 09/11] tools/objtool: Copy hashtable.h into tools  directory Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 17:10 +0100
          Re: [PATCH 09/11] tools/objtool: Copy hashtable.h into tools  directory Ingo Molnar <mingo@kernel.org> - 2016-03-09 19:50 +0100
      [tip:core/objtool] tools: Copy hashtable.h into tools directory tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100

Page 1 of 2  [1] 2  Next page →

#1353841 — [PATCH 00/11] Various objtool fixes

Based on tip/master.

These patches fix all known objtool issues:

- infinite loop
- sibling call false positives
- switch statement jump table fix
- performance improvements
- print one warning per function

Josh Poimboeuf (11):
  objtool: Prevent infinite recursion in noreturn detection
  objtool: Detect infinite recursion
  objtool: Compile with debugging symbols
  objtool: Fix false positive warnings related to sibling calls
  objtool: Add helper macros for traversing instructions
  objtool: Remove superflous INIT_LIST_HEAD
  objtool: Rename some variables and functions
  objtool: Fix false positive warnings for functions with multiple
    switch statements
  tools/objtool: Copy hashtable.h into tools directory
  objtool: Add several performance improvements
  objtool: Only print one warning per function

 tools/include/asm-generic/bitops/__fls.h |   2 +-
 tools/include/asm-generic/bitops/fls.h   |   2 +-
 tools/include/asm-generic/bitops/fls64.h |   2 +-
 tools/include/linux/hashtable.h          | 152 +++++++++++
 tools/objtool/Makefile                   |   2 +-
 tools/objtool/builtin-check.c            | 429 +++++++++++++++++++------------
 tools/objtool/elf.c                      |  37 ++-
 tools/objtool/elf.h                      |  14 +-
 8 files changed, 447 insertions(+), 193 deletions(-)
 create mode 100644 tools/include/linux/hashtable.h

-- 
2.4.3

[toc] | [next] | [standalone]

#1353842 — [PATCH 01/11] objtool: Prevent infinite recursion in noreturn detection

Ingo reported an infinite loop in objtool with a certain randconfig [1].
With the given config, two functions in crypto/ablkcipher.o contained
sibling calls to each other, which threw the recursive call in
dead_end_function() for a loop (literally!).

Split the noreturn detection into two passes.  In the first pass, check
for return instructions.  In the second pass, do the potentially
recursive sibling call check.  In most cases, the first pass will be
good enough.  In the rare case where a second pass is needed, recursion
should hopefully no longer be possible.

[1] https://lkml.kernel.org/r/20160308154909.GA20956@gmail.com

Reported-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index f7e0eba..80d9ed9 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -125,7 +125,7 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
 static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 {
 	int i;
-	struct instruction *insn;
+	struct instruction *insn, *func_insn;
 	bool empty = true;
 
 	/*
@@ -154,10 +154,11 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 	if (!func->sec)
 		return false;
 
-	insn = find_instruction(file, func->sec, func->offset);
-	if (!insn)
+	func_insn = find_instruction(file, func->sec, func->offset);
+	if (!func_insn)
 		return false;
 
+	insn = func_insn;
 	list_for_each_entry_from(insn, &file->insns, list) {
 		if (insn->sec != func->sec ||
 		    insn->offset >= func->offset + func->len)
@@ -167,6 +168,21 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 
 		if (insn->type == INSN_RETURN)
 			return false;
+	}
+
+	if (empty)
+		return false;
+
+	/*
+	 * A function can have a sibling call instead of a return.  In that
+	 * case, the function's dead-end status depends on whether the target
+	 * of the sibling call returns.
+	 */
+	insn = func_insn;
+	list_for_each_entry_from(insn, &file->insns, list) {
+		if (insn->sec != func->sec ||
+		    insn->offset >= func->offset + func->len)
+			break;
 
 		if (insn->type == INSN_JUMP_UNCONDITIONAL) {
 			struct instruction *dest = insn->jump_dest;
@@ -194,7 +210,7 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 			return false;
 	}
 
-	return !empty;
+	return true;
 }
 
 /*
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354045 — [tip:core/objtool] objtool: Prevent infinite recursion in noreturn detection

Commit-ID:  81bfafca1332869160e9da789252276e2f34a14e
Gitweb:     http://git.kernel.org/tip/81bfafca1332869160e9da789252276e2f34a14e
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:51 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:07 +0100

objtool: Prevent infinite recursion in noreturn detection

Ingo reported an infinite loop in objtool with a certain randconfig [1].
With the given config, two functions in crypto/ablkcipher.o contained
sibling calls to each other, which threw the recursive call in
dead_end_function() for a loop (literally!).

Split the noreturn detection into two passes.  In the first pass, check
for return instructions.  In the second pass, do the potentially
recursive sibling call check.  In most cases, the first pass will be
good enough.  In the rare case where a second pass is needed, recursion
should hopefully no longer be possible.

[1] https://lkml.kernel.org/r/20160308154909.GA20956@gmail.com

Reported-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/16afb602640ef43b7782087d6cca17bf6fc13603.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index f7e0eba..80d9ed9 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -125,7 +125,7 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
 static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 {
 	int i;
-	struct instruction *insn;
+	struct instruction *insn, *func_insn;
 	bool empty = true;
 
 	/*
@@ -154,10 +154,11 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 	if (!func->sec)
 		return false;
 
-	insn = find_instruction(file, func->sec, func->offset);
-	if (!insn)
+	func_insn = find_instruction(file, func->sec, func->offset);
+	if (!func_insn)
 		return false;
 
+	insn = func_insn;
 	list_for_each_entry_from(insn, &file->insns, list) {
 		if (insn->sec != func->sec ||
 		    insn->offset >= func->offset + func->len)
@@ -167,6 +168,21 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 
 		if (insn->type == INSN_RETURN)
 			return false;
+	}
+
+	if (empty)
+		return false;
+
+	/*
+	 * A function can have a sibling call instead of a return.  In that
+	 * case, the function's dead-end status depends on whether the target
+	 * of the sibling call returns.
+	 */
+	insn = func_insn;
+	list_for_each_entry_from(insn, &file->insns, list) {
+		if (insn->sec != func->sec ||
+		    insn->offset >= func->offset + func->len)
+			break;
 
 		if (insn->type == INSN_JUMP_UNCONDITIONAL) {
 			struct instruction *dest = insn->jump_dest;
@@ -194,7 +210,7 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 			return false;
 	}
 
-	return !empty;
+	return true;
 }
 
 /*

[toc] | [prev] | [next] | [standalone]

#1353843 — [PATCH 05/11] objtool: Add helper macros for traversing instructions

Add some helper macros to make it easier to traverse instructions, and
to abstract the details of the instruction list implementation in
preparation for creating a hash structure.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 128 ++++++++++++++++++------------------------
 1 file changed, 55 insertions(+), 73 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index fe24804..46a8985 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -66,9 +66,8 @@ struct objtool_file {
 const char *objname;
 static bool nofp;
 
-static struct instruction *find_instruction(struct objtool_file *file,
-					    struct section *sec,
-					    unsigned long offset)
+static struct instruction *find_insn(struct objtool_file *file,
+				     struct section *sec, unsigned long offset)
 {
 	struct instruction *insn;
 
@@ -79,6 +78,31 @@ static struct instruction *find_instruction(struct objtool_file *file,
 	return NULL;
 }
 
+static struct instruction *next_insn_same_sec(struct objtool_file *file,
+					      struct instruction *insn)
+{
+	struct instruction *next = list_next_entry(insn, list);
+
+	if (&next->list == &file->insns || next->sec != insn->sec)
+		return NULL;
+
+	return next;
+}
+
+#define for_each_insn(file, insn)					\
+	list_for_each_entry(insn, &file->insns, list)
+
+#define func_for_each_insn(file, func, insn)				\
+	for (insn = find_insn(file, func->sec, func->offset);		\
+	     insn && &insn->list != &file->insns &&			\
+		insn->sec == func->sec &&				\
+		insn->offset < func->offset + func->len;		\
+	     insn = list_next_entry(insn, list))
+
+#define sec_for_each_insn_from(file, insn)				\
+	for (; insn; insn = next_insn_same_sec(file, insn))
+
+
 /*
  * Check if the function has been manually whitelisted with the
  * STACK_FRAME_NON_STANDARD macro, or if it should be automatically whitelisted
@@ -99,16 +123,9 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
 				return true;
 
 	/* check if it has a context switching instruction */
-	insn = find_instruction(file, func->sec, func->offset);
-	if (!insn)
-		return false;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != func->sec ||
-		    insn->offset >= func->offset + func->len)
-			break;
+	func_for_each_insn(file, func, insn)
 		if (insn->type == INSN_CONTEXT_SWITCH)
 			return true;
-	}
 
 	return false;
 }
@@ -131,7 +148,7 @@ static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 			       int recursion)
 {
 	int i;
-	struct instruction *insn, *func_insn;
+	struct instruction *insn;
 	bool empty = true;
 
 	/*
@@ -160,16 +177,7 @@ static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 	if (!func->sec)
 		return 0;
 
-	func_insn = find_instruction(file, func->sec, func->offset);
-	if (!func_insn)
-		return 0;
-
-	insn = func_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != func->sec ||
-		    insn->offset >= func->offset + func->len)
-			break;
-
+	func_for_each_insn(file, func, insn) {
 		empty = false;
 
 		if (insn->type == INSN_RETURN)
@@ -184,8 +192,7 @@ static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 	 * case, the function's dead-end status depends on whether the target
 	 * of the sibling call returns.
 	 */
-	insn = func_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
+	func_for_each_insn(file, func, insn) {
 		if (insn->sec != func->sec ||
 		    insn->offset >= func->offset + func->len)
 			break;
@@ -294,17 +301,8 @@ static void get_ignores(struct objtool_file *file)
 			if (!ignore_func(file, func))
 				continue;
 
-			insn = find_instruction(file, sec, func->offset);
-			if (!insn)
-				continue;
-
-			list_for_each_entry_from(insn, &file->insns, list) {
-				if (insn->sec != func->sec ||
-				    insn->offset >= func->offset + func->len)
-					break;
-
+			func_for_each_insn(file, func, insn)
 				insn->visited = true;
-			}
 		}
 	}
 }
@@ -319,7 +317,7 @@ static int get_jump_destinations(struct objtool_file *file)
 	struct section *dest_sec;
 	unsigned long dest_off;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (insn->type != INSN_JUMP_CONDITIONAL &&
 		    insn->type != INSN_JUMP_UNCONDITIONAL)
 			continue;
@@ -345,7 +343,7 @@ static int get_jump_destinations(struct objtool_file *file)
 			continue;
 		}
 
-		insn->jump_dest = find_instruction(file, dest_sec, dest_off);
+		insn->jump_dest = find_insn(file, dest_sec, dest_off);
 		if (!insn->jump_dest) {
 
 			/*
@@ -375,7 +373,7 @@ static int get_call_destinations(struct objtool_file *file)
 	unsigned long dest_off;
 	struct rela *rela;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (insn->type != INSN_CALL)
 			continue;
 
@@ -438,9 +436,8 @@ static int handle_group_alt(struct objtool_file *file,
 
 	last_orig_insn = NULL;
 	insn = orig_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != special_alt->orig_sec ||
-		    insn->offset >= special_alt->orig_off + special_alt->orig_len)
+	sec_for_each_insn_from(file, insn) {
+		if (insn->offset >= special_alt->orig_off + special_alt->orig_len)
 			break;
 
 		if (special_alt->skip_orig)
@@ -450,8 +447,7 @@ static int handle_group_alt(struct objtool_file *file,
 		last_orig_insn = insn;
 	}
 
-	if (list_is_last(&last_orig_insn->list, &file->insns) ||
-	    list_next_entry(last_orig_insn, list)->sec != special_alt->orig_sec) {
+	if (!next_insn_same_sec(file, last_orig_insn)) {
 		WARN("%s: don't know how to handle alternatives at end of section",
 		     special_alt->orig_sec->name);
 		return -1;
@@ -476,9 +472,8 @@ static int handle_group_alt(struct objtool_file *file,
 
 	last_new_insn = NULL;
 	insn = *new_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != special_alt->new_sec ||
-		    insn->offset >= special_alt->new_off + special_alt->new_len)
+	sec_for_each_insn_from(file, insn) {
+		if (insn->offset >= special_alt->new_off + special_alt->new_len)
 			break;
 
 		last_new_insn = insn;
@@ -561,8 +556,8 @@ static int get_special_section_alts(struct objtool_file *file)
 			goto out;
 		}
 
-		orig_insn = find_instruction(file, special_alt->orig_sec,
-					     special_alt->orig_off);
+		orig_insn = find_insn(file, special_alt->orig_sec,
+				      special_alt->orig_off);
 		if (!orig_insn) {
 			WARN_FUNC("special: can't find orig instruction",
 				  special_alt->orig_sec, special_alt->orig_off);
@@ -572,8 +567,8 @@ static int get_special_section_alts(struct objtool_file *file)
 
 		new_insn = NULL;
 		if (!special_alt->group || special_alt->new_len) {
-			new_insn = find_instruction(file, special_alt->new_sec,
-						    special_alt->new_off);
+			new_insn = find_insn(file, special_alt->new_sec,
+					     special_alt->new_off);
 			if (!new_insn) {
 				WARN_FUNC("special: can't find new instruction",
 					  special_alt->new_sec,
@@ -619,7 +614,7 @@ static int get_switch_alts(struct objtool_file *file)
 	struct symbol *func;
 	struct alternative *alt;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
@@ -655,8 +650,7 @@ static int get_switch_alts(struct objtool_file *file)
 			    rela->addend >= func->offset + func->len)
 				break;
 
-			alt_insn = find_instruction(file, insn->sec,
-						    rela->addend);
+			alt_insn = find_insn(file, insn->sec, rela->addend);
 			if (!alt_insn) {
 				WARN("%s: can't find instruction at %s+0x%x",
 				     rodata->rela->name, insn->sec->name,
@@ -881,9 +875,8 @@ static int validate_branch(struct objtool_file *file,
 			break;
 		}
 
-		insn = list_next_entry(insn, list);
-
-		if (&insn->list == &file->insns || insn->sec != sec) {
+		insn = next_insn_same_sec(file, insn);
+		if (!insn) {
 			WARN("%s: unexpected end of section", sec->name);
 			warnings++;
 			return warnings;
@@ -934,8 +927,8 @@ static bool is_ubsan_insn(struct instruction *insn)
 			"__ubsan_handle_builtin_unreachable"));
 }
 
-static bool ignore_unreachable_insn(struct instruction *insn,
-				    unsigned long func_end)
+static bool ignore_unreachable_insn(struct symbol *func,
+				    struct instruction *insn)
 {
 	int i;
 
@@ -961,7 +954,7 @@ static bool ignore_unreachable_insn(struct instruction *insn,
 			continue;
 		}
 
-		if (insn->offset + insn->len >= func_end)
+		if (insn->offset + insn->len >= func->offset + func->len)
 			break;
 		insn = list_next_entry(insn, list);
 	}
@@ -974,7 +967,6 @@ static int validate_functions(struct objtool_file *file)
 	struct section *sec;
 	struct symbol *func;
 	struct instruction *insn;
-	unsigned long func_end;
 	int ret, warnings = 0;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
@@ -982,7 +974,7 @@ static int validate_functions(struct objtool_file *file)
 			if (func->type != STT_FUNC)
 				continue;
 
-			insn = find_instruction(file, sec, func->offset);
+			insn = find_insn(file, sec, func->offset);
 			if (!insn) {
 				WARN("%s(): can't find starting instruction",
 				     func->name);
@@ -1000,21 +992,11 @@ static int validate_functions(struct objtool_file *file)
 			if (func->type != STT_FUNC)
 				continue;
 
-			insn = find_instruction(file, sec, func->offset);
-			if (!insn)
-				continue;
-
-			func_end = func->offset + func->len;
-
-			list_for_each_entry_from(insn, &file->insns, list) {
-				if (insn->sec != func->sec ||
-				    insn->offset >= func_end)
-					break;
-
+			func_for_each_insn(file, func, insn) {
 				if (insn->visited)
 					continue;
 
-				if (!ignore_unreachable_insn(insn, func_end)) {
+				if (!ignore_unreachable_insn(func, insn)) {
 					WARN_FUNC("function has unreachable instruction", insn->sec, insn->offset);
 					warnings++;
 				}
@@ -1032,7 +1014,7 @@ static int validate_uncallable_instructions(struct objtool_file *file)
 	struct instruction *insn;
 	int warnings = 0;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (!insn->visited && insn->type == INSN_RETURN) {
 			WARN_FUNC("return instruction outside of a callable function",
 				  insn->sec, insn->offset);
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354048 — [tip:core/objtool] objtool: Add helper macros for traversing instructions

Commit-ID:  74aec058beb0bdaf64454291ef4ba176932bfad3
Gitweb:     http://git.kernel.org/tip/74aec058beb0bdaf64454291ef4ba176932bfad3
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:55 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:08 +0100

objtool: Add helper macros for traversing instructions

Add some helper macros to make it easier to traverse instructions, and
to abstract the details of the instruction list implementation in
preparation for creating a hash structure.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/8e1715d5035bc02b4db28d0fccef6bb1170d1f12.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 128 ++++++++++++++++++------------------------
 1 file changed, 55 insertions(+), 73 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index fe24804..46a8985 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -66,9 +66,8 @@ struct objtool_file {
 const char *objname;
 static bool nofp;
 
-static struct instruction *find_instruction(struct objtool_file *file,
-					    struct section *sec,
-					    unsigned long offset)
+static struct instruction *find_insn(struct objtool_file *file,
+				     struct section *sec, unsigned long offset)
 {
 	struct instruction *insn;
 
@@ -79,6 +78,31 @@ static struct instruction *find_instruction(struct objtool_file *file,
 	return NULL;
 }
 
+static struct instruction *next_insn_same_sec(struct objtool_file *file,
+					      struct instruction *insn)
+{
+	struct instruction *next = list_next_entry(insn, list);
+
+	if (&next->list == &file->insns || next->sec != insn->sec)
+		return NULL;
+
+	return next;
+}
+
+#define for_each_insn(file, insn)					\
+	list_for_each_entry(insn, &file->insns, list)
+
+#define func_for_each_insn(file, func, insn)				\
+	for (insn = find_insn(file, func->sec, func->offset);		\
+	     insn && &insn->list != &file->insns &&			\
+		insn->sec == func->sec &&				\
+		insn->offset < func->offset + func->len;		\
+	     insn = list_next_entry(insn, list))
+
+#define sec_for_each_insn_from(file, insn)				\
+	for (; insn; insn = next_insn_same_sec(file, insn))
+
+
 /*
  * Check if the function has been manually whitelisted with the
  * STACK_FRAME_NON_STANDARD macro, or if it should be automatically whitelisted
@@ -99,16 +123,9 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
 				return true;
 
 	/* check if it has a context switching instruction */
-	insn = find_instruction(file, func->sec, func->offset);
-	if (!insn)
-		return false;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != func->sec ||
-		    insn->offset >= func->offset + func->len)
-			break;
+	func_for_each_insn(file, func, insn)
 		if (insn->type == INSN_CONTEXT_SWITCH)
 			return true;
-	}
 
 	return false;
 }
@@ -131,7 +148,7 @@ static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 			       int recursion)
 {
 	int i;
-	struct instruction *insn, *func_insn;
+	struct instruction *insn;
 	bool empty = true;
 
 	/*
@@ -160,16 +177,7 @@ static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 	if (!func->sec)
 		return 0;
 
-	func_insn = find_instruction(file, func->sec, func->offset);
-	if (!func_insn)
-		return 0;
-
-	insn = func_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != func->sec ||
-		    insn->offset >= func->offset + func->len)
-			break;
-
+	func_for_each_insn(file, func, insn) {
 		empty = false;
 
 		if (insn->type == INSN_RETURN)
@@ -184,8 +192,7 @@ static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 	 * case, the function's dead-end status depends on whether the target
 	 * of the sibling call returns.
 	 */
-	insn = func_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
+	func_for_each_insn(file, func, insn) {
 		if (insn->sec != func->sec ||
 		    insn->offset >= func->offset + func->len)
 			break;
@@ -294,17 +301,8 @@ static void get_ignores(struct objtool_file *file)
 			if (!ignore_func(file, func))
 				continue;
 
-			insn = find_instruction(file, sec, func->offset);
-			if (!insn)
-				continue;
-
-			list_for_each_entry_from(insn, &file->insns, list) {
-				if (insn->sec != func->sec ||
-				    insn->offset >= func->offset + func->len)
-					break;
-
+			func_for_each_insn(file, func, insn)
 				insn->visited = true;
-			}
 		}
 	}
 }
@@ -319,7 +317,7 @@ static int get_jump_destinations(struct objtool_file *file)
 	struct section *dest_sec;
 	unsigned long dest_off;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (insn->type != INSN_JUMP_CONDITIONAL &&
 		    insn->type != INSN_JUMP_UNCONDITIONAL)
 			continue;
@@ -345,7 +343,7 @@ static int get_jump_destinations(struct objtool_file *file)
 			continue;
 		}
 
-		insn->jump_dest = find_instruction(file, dest_sec, dest_off);
+		insn->jump_dest = find_insn(file, dest_sec, dest_off);
 		if (!insn->jump_dest) {
 
 			/*
@@ -375,7 +373,7 @@ static int get_call_destinations(struct objtool_file *file)
 	unsigned long dest_off;
 	struct rela *rela;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (insn->type != INSN_CALL)
 			continue;
 
@@ -438,9 +436,8 @@ static int handle_group_alt(struct objtool_file *file,
 
 	last_orig_insn = NULL;
 	insn = orig_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != special_alt->orig_sec ||
-		    insn->offset >= special_alt->orig_off + special_alt->orig_len)
+	sec_for_each_insn_from(file, insn) {
+		if (insn->offset >= special_alt->orig_off + special_alt->orig_len)
 			break;
 
 		if (special_alt->skip_orig)
@@ -450,8 +447,7 @@ static int handle_group_alt(struct objtool_file *file,
 		last_orig_insn = insn;
 	}
 
-	if (list_is_last(&last_orig_insn->list, &file->insns) ||
-	    list_next_entry(last_orig_insn, list)->sec != special_alt->orig_sec) {
+	if (!next_insn_same_sec(file, last_orig_insn)) {
 		WARN("%s: don't know how to handle alternatives at end of section",
 		     special_alt->orig_sec->name);
 		return -1;
@@ -476,9 +472,8 @@ static int handle_group_alt(struct objtool_file *file,
 
 	last_new_insn = NULL;
 	insn = *new_insn;
-	list_for_each_entry_from(insn, &file->insns, list) {
-		if (insn->sec != special_alt->new_sec ||
-		    insn->offset >= special_alt->new_off + special_alt->new_len)
+	sec_for_each_insn_from(file, insn) {
+		if (insn->offset >= special_alt->new_off + special_alt->new_len)
 			break;
 
 		last_new_insn = insn;
@@ -561,8 +556,8 @@ static int get_special_section_alts(struct objtool_file *file)
 			goto out;
 		}
 
-		orig_insn = find_instruction(file, special_alt->orig_sec,
-					     special_alt->orig_off);
+		orig_insn = find_insn(file, special_alt->orig_sec,
+				      special_alt->orig_off);
 		if (!orig_insn) {
 			WARN_FUNC("special: can't find orig instruction",
 				  special_alt->orig_sec, special_alt->orig_off);
@@ -572,8 +567,8 @@ static int get_special_section_alts(struct objtool_file *file)
 
 		new_insn = NULL;
 		if (!special_alt->group || special_alt->new_len) {
-			new_insn = find_instruction(file, special_alt->new_sec,
-						    special_alt->new_off);
+			new_insn = find_insn(file, special_alt->new_sec,
+					     special_alt->new_off);
 			if (!new_insn) {
 				WARN_FUNC("special: can't find new instruction",
 					  special_alt->new_sec,
@@ -619,7 +614,7 @@ static int get_switch_alts(struct objtool_file *file)
 	struct symbol *func;
 	struct alternative *alt;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
@@ -655,8 +650,7 @@ static int get_switch_alts(struct objtool_file *file)
 			    rela->addend >= func->offset + func->len)
 				break;
 
-			alt_insn = find_instruction(file, insn->sec,
-						    rela->addend);
+			alt_insn = find_insn(file, insn->sec, rela->addend);
 			if (!alt_insn) {
 				WARN("%s: can't find instruction at %s+0x%x",
 				     rodata->rela->name, insn->sec->name,
@@ -881,9 +875,8 @@ static int validate_branch(struct objtool_file *file,
 			break;
 		}
 
-		insn = list_next_entry(insn, list);
-
-		if (&insn->list == &file->insns || insn->sec != sec) {
+		insn = next_insn_same_sec(file, insn);
+		if (!insn) {
 			WARN("%s: unexpected end of section", sec->name);
 			warnings++;
 			return warnings;
@@ -934,8 +927,8 @@ static bool is_ubsan_insn(struct instruction *insn)
 			"__ubsan_handle_builtin_unreachable"));
 }
 
-static bool ignore_unreachable_insn(struct instruction *insn,
-				    unsigned long func_end)
+static bool ignore_unreachable_insn(struct symbol *func,
+				    struct instruction *insn)
 {
 	int i;
 
@@ -961,7 +954,7 @@ static bool ignore_unreachable_insn(struct instruction *insn,
 			continue;
 		}
 
-		if (insn->offset + insn->len >= func_end)
+		if (insn->offset + insn->len >= func->offset + func->len)
 			break;
 		insn = list_next_entry(insn, list);
 	}
@@ -974,7 +967,6 @@ static int validate_functions(struct objtool_file *file)
 	struct section *sec;
 	struct symbol *func;
 	struct instruction *insn;
-	unsigned long func_end;
 	int ret, warnings = 0;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
@@ -982,7 +974,7 @@ static int validate_functions(struct objtool_file *file)
 			if (func->type != STT_FUNC)
 				continue;
 
-			insn = find_instruction(file, sec, func->offset);
+			insn = find_insn(file, sec, func->offset);
 			if (!insn) {
 				WARN("%s(): can't find starting instruction",
 				     func->name);
@@ -1000,21 +992,11 @@ static int validate_functions(struct objtool_file *file)
 			if (func->type != STT_FUNC)
 				continue;
 
-			insn = find_instruction(file, sec, func->offset);
-			if (!insn)
-				continue;
-
-			func_end = func->offset + func->len;
-
-			list_for_each_entry_from(insn, &file->insns, list) {
-				if (insn->sec != func->sec ||
-				    insn->offset >= func_end)
-					break;
-
+			func_for_each_insn(file, func, insn) {
 				if (insn->visited)
 					continue;
 
-				if (!ignore_unreachable_insn(insn, func_end)) {
+				if (!ignore_unreachable_insn(func, insn)) {
 					WARN_FUNC("function has unreachable instruction", insn->sec, insn->offset);
 					warnings++;
 				}
@@ -1032,7 +1014,7 @@ static int validate_uncallable_instructions(struct objtool_file *file)
 	struct instruction *insn;
 	int warnings = 0;
 
-	list_for_each_entry(insn, &file->insns, list) {
+	for_each_insn(file, insn) {
 		if (!insn->visited && insn->type == INSN_RETURN) {
 			WARN_FUNC("return instruction outside of a callable function",
 				  insn->sec, insn->offset);

[toc] | [prev] | [next] | [standalone]

#1353844 — [PATCH 10/11] objtool: Add several performance improvements

Use hash tables for instruction and rela lookups (and keep the linked
lists around for sequential access).

Also cache the section struct for the "__func_stack_frame_non_standard"
section.

With this change, "objtool check net/wireless/nl80211.o" goes from:

  real	0m1.168s
  user	0m1.163s
  sys	0m0.005s

to:

  real	0m0.059s
  user	0m0.042s
  sys	0m0.017s

for a 20x speedup.

With the same object, it should be noted that the memory heap usage grew
from 8MB to 62MB.  Reducing the memory usage is on the TODO list.

Reported-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 18 ++++++++++++------
 tools/objtool/elf.c           | 21 +++++++++++++++------
 tools/objtool/elf.h           | 10 ++++++++--
 3 files changed, 35 insertions(+), 14 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index cf1e48d..bfeee22 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -34,6 +34,8 @@
 #include "arch.h"
 #include "warn.h"
 
+#include <linux/hashtable.h>
+
 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 
 #define STATE_FP_SAVED		0x1
@@ -42,6 +44,7 @@
 
 struct instruction {
 	struct list_head list;
+	struct hlist_node hash;
 	struct section *sec;
 	unsigned long offset;
 	unsigned int len, state;
@@ -61,7 +64,8 @@ struct alternative {
 struct objtool_file {
 	struct elf *elf;
 	struct list_head insn_list;
-	struct section *rodata;
+	DECLARE_HASHTABLE(insn_hash, 16);
+	struct section *rodata, *whitelist;
 };
 
 const char *objname;
@@ -72,7 +76,7 @@ static struct instruction *find_insn(struct objtool_file *file,
 {
 	struct instruction *insn;
 
-	list_for_each_entry(insn, &file->insn_list, list)
+	hash_for_each_possible(file->insn_hash, insn, hash, offset)
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
 
@@ -111,14 +115,12 @@ static struct instruction *next_insn_same_sec(struct objtool_file *file,
  */
 static bool ignore_func(struct objtool_file *file, struct symbol *func)
 {
-	struct section *macro_sec;
 	struct rela *rela;
 	struct instruction *insn;
 
 	/* check for STACK_FRAME_NON_STANDARD */
-	macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
-	if (macro_sec && macro_sec->rela)
-		list_for_each_entry(rela, &macro_sec->rela->rela_list, list)
+	if (file->whitelist && file->whitelist->rela)
+		list_for_each_entry(rela, &file->whitelist->rela->rela_list, list)
 			if (rela->sym->sec == func->sec &&
 			    rela->addend == func->offset)
 				return true;
@@ -276,6 +278,7 @@ static int decode_instructions(struct objtool_file *file)
 				return -1;
 			}
 
+			hash_add(file->insn_hash, &insn->hash, insn->offset);
 			list_add_tail(&insn->list, &file->insn_list);
 		}
 	}
@@ -729,6 +732,7 @@ static int decode_sections(struct objtool_file *file)
 {
 	int ret;
 
+	file->whitelist = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
 	file->rodata = find_section_by_name(file->elf, ".rodata");
 
 	ret = decode_instructions(file);
@@ -1091,6 +1095,7 @@ static void cleanup(struct objtool_file *file)
 			free(alt);
 		}
 		list_del(&insn->list);
+		hash_del(&insn->hash);
 		free(insn);
 	}
 	elf_close(file->elf);
@@ -1125,6 +1130,7 @@ int cmd_check(int argc, const char **argv)
 	}
 
 	INIT_LIST_HEAD(&file.insn_list);
+	hash_init(file.insn_hash);
 
 	ret = decode_sections(&file);
 	if (ret < 0)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 7de243f..e11f6b6 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -59,7 +59,7 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 	struct symbol *sym;
 
 	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbol_list, list)
+		hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
 			if (sym->idx == idx)
 				return sym;
 
@@ -82,13 +82,15 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 				     unsigned int len)
 {
 	struct rela *rela;
+	unsigned long o;
 
 	if (!sec->rela)
 		return NULL;
 
-	list_for_each_entry(rela, &sec->rela->rela_list, list)
-		if (rela->offset >= offset && rela->offset < offset + len)
-			return rela;
+	for (o = offset; o < offset + len; o++)
+		hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
+			if (rela->offset == o)
+				return rela;
 
 	return NULL;
 }
@@ -137,6 +139,8 @@ 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);
 
@@ -261,6 +265,7 @@ static int read_symbols(struct elf *elf)
 			}
 		}
 		list_add(&sym->list, entry);
+		hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
 	}
 
 	return 0;
@@ -298,8 +303,6 @@ static int read_relas(struct elf *elf)
 			}
 			memset(rela, 0, sizeof(*rela));
 
-			list_add_tail(&rela->list, &sec->rela_list);
-
 			if (!gelf_getrela(sec->elf_data, i, &rela->rela)) {
 				perror("gelf_getrela");
 				return -1;
@@ -315,6 +318,10 @@ static int read_relas(struct elf *elf)
 				     symndx, sec->name);
 				return -1;
 			}
+
+			list_add_tail(&rela->list, &sec->rela_list);
+			hash_add(sec->rela_hash, &rela->hash, rela->offset);
+
 		}
 	}
 
@@ -384,10 +391,12 @@ void elf_close(struct elf *elf)
 	list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
 		list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
 			list_del(&sym->list);
+			hash_del(&sym->hash);
 			free(sym);
 		}
 		list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) {
 			list_del(&rela->list);
+			hash_del(&rela->hash);
 			free(rela);
 		}
 		list_del(&sec->list);
diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index 57e4653..7f3e00a 100644
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -21,12 +21,15 @@
 #include <stdio.h>
 #include <gelf.h>
 #include <linux/list.h>
+#include <linux/hashtable.h>
 
 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;
 	struct symbol *sym;
 	Elf_Data *elf_data;
@@ -38,10 +41,11 @@ struct section {
 
 struct symbol {
 	struct list_head list;
+	struct hlist_node hash;
 	GElf_Sym sym;
 	struct section *sec;
 	char *name;
-	int idx;
+	unsigned int idx;
 	unsigned char bind, type;
 	unsigned long offset;
 	unsigned int len;
@@ -49,10 +53,11 @@ struct symbol {
 
 struct rela {
 	struct list_head list;
+	struct hlist_node hash;
 	GElf_Rela rela;
 	struct symbol *sym;
 	unsigned int type;
-	int offset;
+	unsigned long offset;
 	int addend;
 };
 
@@ -62,6 +67,7 @@ struct elf {
 	int fd;
 	char *name;
 	struct list_head sections;
+	DECLARE_HASHTABLE(rela_hash, 16);
 };
 
 
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354056 — [tip:core/objtool] objtool: Add several performance improvements

Commit-ID:  042ba73fe7eb63872ee2d6ac86410052210c1f16
Gitweb:     http://git.kernel.org/tip/042ba73fe7eb63872ee2d6ac86410052210c1f16
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:07:00 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:10 +0100

objtool: Add several performance improvements

Use hash tables for instruction and rela lookups (and keep the linked
lists around for sequential access).

Also cache the section struct for the "__func_stack_frame_non_standard"
section.

With this change, "objtool check net/wireless/nl80211.o" goes from:

  real	0m1.168s
  user	0m1.163s
  sys	0m0.005s

to:

  real	0m0.059s
  user	0m0.042s
  sys	0m0.017s

for a 20x speedup.

With the same object, it should be noted that the memory heap usage grew
from 8MB to 62MB.  Reducing the memory usage is on the TODO list.

Reported-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/dd0d8e1449506cfa7701b4e7ba73577077c44253.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 18 ++++++++++++------
 tools/objtool/elf.c           | 21 +++++++++++++++------
 tools/objtool/elf.h           | 10 ++++++++--
 3 files changed, 35 insertions(+), 14 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index cf1e48d..bfeee22 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -34,6 +34,8 @@
 #include "arch.h"
 #include "warn.h"
 
+#include <linux/hashtable.h>
+
 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 
 #define STATE_FP_SAVED		0x1
@@ -42,6 +44,7 @@
 
 struct instruction {
 	struct list_head list;
+	struct hlist_node hash;
 	struct section *sec;
 	unsigned long offset;
 	unsigned int len, state;
@@ -61,7 +64,8 @@ struct alternative {
 struct objtool_file {
 	struct elf *elf;
 	struct list_head insn_list;
-	struct section *rodata;
+	DECLARE_HASHTABLE(insn_hash, 16);
+	struct section *rodata, *whitelist;
 };
 
 const char *objname;
@@ -72,7 +76,7 @@ static struct instruction *find_insn(struct objtool_file *file,
 {
 	struct instruction *insn;
 
-	list_for_each_entry(insn, &file->insn_list, list)
+	hash_for_each_possible(file->insn_hash, insn, hash, offset)
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
 
@@ -111,14 +115,12 @@ static struct instruction *next_insn_same_sec(struct objtool_file *file,
  */
 static bool ignore_func(struct objtool_file *file, struct symbol *func)
 {
-	struct section *macro_sec;
 	struct rela *rela;
 	struct instruction *insn;
 
 	/* check for STACK_FRAME_NON_STANDARD */
-	macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
-	if (macro_sec && macro_sec->rela)
-		list_for_each_entry(rela, &macro_sec->rela->rela_list, list)
+	if (file->whitelist && file->whitelist->rela)
+		list_for_each_entry(rela, &file->whitelist->rela->rela_list, list)
 			if (rela->sym->sec == func->sec &&
 			    rela->addend == func->offset)
 				return true;
@@ -276,6 +278,7 @@ static int decode_instructions(struct objtool_file *file)
 				return -1;
 			}
 
+			hash_add(file->insn_hash, &insn->hash, insn->offset);
 			list_add_tail(&insn->list, &file->insn_list);
 		}
 	}
@@ -729,6 +732,7 @@ static int decode_sections(struct objtool_file *file)
 {
 	int ret;
 
+	file->whitelist = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
 	file->rodata = find_section_by_name(file->elf, ".rodata");
 
 	ret = decode_instructions(file);
@@ -1091,6 +1095,7 @@ static void cleanup(struct objtool_file *file)
 			free(alt);
 		}
 		list_del(&insn->list);
+		hash_del(&insn->hash);
 		free(insn);
 	}
 	elf_close(file->elf);
@@ -1125,6 +1130,7 @@ int cmd_check(int argc, const char **argv)
 	}
 
 	INIT_LIST_HEAD(&file.insn_list);
+	hash_init(file.insn_hash);
 
 	ret = decode_sections(&file);
 	if (ret < 0)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 7de243f..e11f6b6 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -59,7 +59,7 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 	struct symbol *sym;
 
 	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbol_list, list)
+		hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
 			if (sym->idx == idx)
 				return sym;
 
@@ -82,13 +82,15 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 				     unsigned int len)
 {
 	struct rela *rela;
+	unsigned long o;
 
 	if (!sec->rela)
 		return NULL;
 
-	list_for_each_entry(rela, &sec->rela->rela_list, list)
-		if (rela->offset >= offset && rela->offset < offset + len)
-			return rela;
+	for (o = offset; o < offset + len; o++)
+		hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
+			if (rela->offset == o)
+				return rela;
 
 	return NULL;
 }
@@ -137,6 +139,8 @@ 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);
 
@@ -261,6 +265,7 @@ static int read_symbols(struct elf *elf)
 			}
 		}
 		list_add(&sym->list, entry);
+		hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
 	}
 
 	return 0;
@@ -298,8 +303,6 @@ static int read_relas(struct elf *elf)
 			}
 			memset(rela, 0, sizeof(*rela));
 
-			list_add_tail(&rela->list, &sec->rela_list);
-
 			if (!gelf_getrela(sec->elf_data, i, &rela->rela)) {
 				perror("gelf_getrela");
 				return -1;
@@ -315,6 +318,10 @@ static int read_relas(struct elf *elf)
 				     symndx, sec->name);
 				return -1;
 			}
+
+			list_add_tail(&rela->list, &sec->rela_list);
+			hash_add(sec->rela_hash, &rela->hash, rela->offset);
+
 		}
 	}
 
@@ -384,10 +391,12 @@ void elf_close(struct elf *elf)
 	list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
 		list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
 			list_del(&sym->list);
+			hash_del(&sym->hash);
 			free(sym);
 		}
 		list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) {
 			list_del(&rela->list);
+			hash_del(&rela->hash);
 			free(rela);
 		}
 		list_del(&sec->list);
diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index 57e4653..7f3e00a 100644
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -21,12 +21,15 @@
 #include <stdio.h>
 #include <gelf.h>
 #include <linux/list.h>
+#include <linux/hashtable.h>
 
 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;
 	struct symbol *sym;
 	Elf_Data *elf_data;
@@ -38,10 +41,11 @@ struct section {
 
 struct symbol {
 	struct list_head list;
+	struct hlist_node hash;
 	GElf_Sym sym;
 	struct section *sec;
 	char *name;
-	int idx;
+	unsigned int idx;
 	unsigned char bind, type;
 	unsigned long offset;
 	unsigned int len;
@@ -49,10 +53,11 @@ struct symbol {
 
 struct rela {
 	struct list_head list;
+	struct hlist_node hash;
 	GElf_Rela rela;
 	struct symbol *sym;
 	unsigned int type;
-	int offset;
+	unsigned long offset;
 	int addend;
 };
 
@@ -62,6 +67,7 @@ struct elf {
 	int fd;
 	char *name;
 	struct list_head sections;
+	DECLARE_HASHTABLE(rela_hash, 16);
 };
 
 

[toc] | [prev] | [next] | [standalone]

#1353846 — [PATCH 03/11] objtool: Compile with debugging symbols

Compile objtool with debugging symbols ('-g') to help tools like perf
and gdb understand what it's doing.  Combined with '-O2', it's not
always helpful, but it's better than nothing.

Reported-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tools/objtool/Makefile b/tools/objtool/Makefile
index e4a6bd5..6765c7e 100644
--- a/tools/objtool/Makefile
+++ b/tools/objtool/Makefile
@@ -27,7 +27,7 @@ OBJTOOL_IN := $(OBJTOOL)-in.o
 all: $(OBJTOOL)
 
 INCLUDES := -I$(srctree)/tools/include
-CFLAGS   += -Wall -Werror $(EXTRA_WARNINGS) -fomit-frame-pointer -O2 $(INCLUDES)
+CFLAGS   += -Wall -Werror $(EXTRA_WARNINGS) -fomit-frame-pointer -O2 -g $(INCLUDES)
 LDFLAGS  += -lelf $(LIBSUBCMD)
 
 AWK = awk
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354052 — [tip:core/objtool] objtool: Compile with debugging symbols

Commit-ID:  d435fb5ef74c31909ca58f93aa87ad09b17bbe9a
Gitweb:     http://git.kernel.org/tip/d435fb5ef74c31909ca58f93aa87ad09b17bbe9a
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:53 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:08 +0100

objtool: Compile with debugging symbols

Compile objtool with debugging symbols ('-g') to help tools like perf
and gdb understand what it's doing.  Combined with '-O2', it's not
always helpful, but it's better than nothing.

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

diff --git a/tools/objtool/Makefile b/tools/objtool/Makefile
index e4a6bd5..6765c7e 100644
--- a/tools/objtool/Makefile
+++ b/tools/objtool/Makefile
@@ -27,7 +27,7 @@ OBJTOOL_IN := $(OBJTOOL)-in.o
 all: $(OBJTOOL)
 
 INCLUDES := -I$(srctree)/tools/include
-CFLAGS   += -Wall -Werror $(EXTRA_WARNINGS) -fomit-frame-pointer -O2 $(INCLUDES)
+CFLAGS   += -Wall -Werror $(EXTRA_WARNINGS) -fomit-frame-pointer -O2 -g $(INCLUDES)
 LDFLAGS  += -lelf $(LIBSUBCMD)
 
 AWK = awk

[toc] | [prev] | [next] | [standalone]

#1353849 — [PATCH 04/11] objtool: Fix false positive warnings related to sibling calls

With some configs [1], objtool prints a bunch of false positive warnings
like:

  arch/x86/events/core.o: warning: objtool: x86_del_exclusive()+0x0: frame pointer state mismatch

For some reason this config has a bunch of sibling calls.  When objtool
follows a sibling call jump, it attempts to compare the frame pointer
state.  But it also accidentally compares the FENTRY state, resulting in
a false positive warning.

[1] https://lkml.kernel.org/r/20160308154909.GA20956@gmail.com

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 51da270..fe24804 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -729,6 +729,11 @@ static bool has_valid_stack_frame(struct instruction *insn)
 	       (insn->state & STATE_FP_SETUP);
 }
 
+static unsigned int frame_state(unsigned long state)
+{
+	return (state & (STATE_FP_SAVED | STATE_FP_SETUP));
+}
+
 /*
  * Follow the branch starting at the given instruction, and recursively follow
  * any other branches (jumps).  Meanwhile, track the frame pointer state at
@@ -756,7 +761,7 @@ static int validate_branch(struct objtool_file *file,
 
 	while (1) {
 		if (insn->visited) {
-			if (insn->state != state) {
+			if (frame_state(insn->state) != frame_state(state)) {
 				WARN_FUNC("frame pointer state mismatch",
 					  sec, insn->offset);
 				warnings++;
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354047 — [tip:core/objtool] objtool: Fix false positive warnings related to sibling calls

Commit-ID:  d8d1b2cb58540b0cf572be4715167c473193888e
Gitweb:     http://git.kernel.org/tip/d8d1b2cb58540b0cf572be4715167c473193888e
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:54 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:08 +0100

objtool: Fix false positive warnings related to sibling calls

With some configs [1], objtool prints a bunch of false positive warnings
like:

  arch/x86/events/core.o: warning: objtool: x86_del_exclusive()+0x0: frame pointer state mismatch

For some reason this config has a bunch of sibling calls.  When objtool
follows a sibling call jump, it attempts to compare the frame pointer
state.  But it also accidentally compares the FENTRY state, resulting in
a false positive warning.

[1] https://lkml.kernel.org/r/20160308154909.GA20956@gmail.com

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/382de77ccaaa8cd79b27a155c3d109ebd4ce0219.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 51da270..fe24804 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -729,6 +729,11 @@ static bool has_valid_stack_frame(struct instruction *insn)
 	       (insn->state & STATE_FP_SETUP);
 }
 
+static unsigned int frame_state(unsigned long state)
+{
+	return (state & (STATE_FP_SAVED | STATE_FP_SETUP));
+}
+
 /*
  * Follow the branch starting at the given instruction, and recursively follow
  * any other branches (jumps).  Meanwhile, track the frame pointer state at
@@ -756,7 +761,7 @@ static int validate_branch(struct objtool_file *file,
 
 	while (1) {
 		if (insn->visited) {
-			if (insn->state != state) {
+			if (frame_state(insn->state) != frame_state(state)) {
 				WARN_FUNC("frame pointer state mismatch",
 					  sec, insn->offset);
 				warnings++;

[toc] | [prev] | [next] | [standalone]

#1353850 — [PATCH 02/11] objtool: Detect infinite recursion

I don't _think_ dead_end_function() can get into a recursive loop, but
just in case, stop the loop and print a warning.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 45 +++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 80d9ed9..51da270 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -121,8 +121,14 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
  *
  * For local functions, we have to detect them manually by simply looking for
  * the lack of a return instruction.
+ *
+ * Returns:
+ *  -1: error
+ *   0: no dead end
+ *   1: dead end
  */
-static bool dead_end_function(struct objtool_file *file, struct symbol *func)
+static int __dead_end_function(struct objtool_file *file, struct symbol *func,
+			       int recursion)
 {
 	int i;
 	struct instruction *insn, *func_insn;
@@ -144,19 +150,19 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 	};
 
 	if (func->bind == STB_WEAK)
-		return false;
+		return 0;
 
 	if (func->bind == STB_GLOBAL)
 		for (i = 0; i < ARRAY_SIZE(global_noreturns); i++)
 			if (!strcmp(func->name, global_noreturns[i]))
-				return true;
+				return 1;
 
 	if (!func->sec)
-		return false;
+		return 0;
 
 	func_insn = find_instruction(file, func->sec, func->offset);
 	if (!func_insn)
-		return false;
+		return 0;
 
 	insn = func_insn;
 	list_for_each_entry_from(insn, &file->insns, list) {
@@ -167,11 +173,11 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 		empty = false;
 
 		if (insn->type == INSN_RETURN)
-			return false;
+			return 0;
 	}
 
 	if (empty)
-		return false;
+		return 0;
 
 	/*
 	 * A function can have a sibling call instead of a return.  In that
@@ -190,7 +196,7 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 
 			if (!dest)
 				/* sibling call to another file */
-				return false;
+				return 0;
 
 			if (dest->sec != func->sec ||
 			    dest->offset < func->offset ||
@@ -201,16 +207,28 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 				if (!dest_func)
 					continue;
 
-				return dead_end_function(file, dest_func);
+				if (recursion == 5) {
+					WARN_FUNC("infinite recursion (objtool bug!)",
+						  dest->sec, dest->offset);
+					return -1;
+				}
+
+				return __dead_end_function(file, dest_func,
+							   recursion + 1);
 			}
 		}
 
 		if (insn->type == INSN_JUMP_DYNAMIC)
 			/* sibling call */
-			return false;
+			return 0;
 	}
 
-	return true;
+	return 1;
+}
+
+static int dead_end_function(struct objtool_file *file, struct symbol *func)
+{
+	return __dead_end_function(file, func, 0);
 }
 
 /*
@@ -809,8 +827,11 @@ static int validate_branch(struct objtool_file *file,
 				break;
 			}
 
-			if (dead_end_function(file, insn->call_dest))
+			ret = dead_end_function(file, insn->call_dest);
+			if (ret == 1)
 				return warnings;
+			if (ret == -1)
+				warnings++;
 
 			/* fallthrough */
 		case INSN_CALL_DYNAMIC:
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354042 — [tip:core/objtool] objtool: Detect infinite recursion

Commit-ID:  b1e03249510b32645826bbf61a1452dd766c2e5c
Gitweb:     http://git.kernel.org/tip/b1e03249510b32645826bbf61a1452dd766c2e5c
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:52 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:07 +0100

objtool: Detect infinite recursion

I don't _think_ dead_end_function() can get into a recursive loop, but
just in case, stop the loop and print a warning.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/ff489a63e6feb88abb192cfb361d81626dcf3e89.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 45 +++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 80d9ed9..51da270 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -121,8 +121,14 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
  *
  * For local functions, we have to detect them manually by simply looking for
  * the lack of a return instruction.
+ *
+ * Returns:
+ *  -1: error
+ *   0: no dead end
+ *   1: dead end
  */
-static bool dead_end_function(struct objtool_file *file, struct symbol *func)
+static int __dead_end_function(struct objtool_file *file, struct symbol *func,
+			       int recursion)
 {
 	int i;
 	struct instruction *insn, *func_insn;
@@ -144,19 +150,19 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 	};
 
 	if (func->bind == STB_WEAK)
-		return false;
+		return 0;
 
 	if (func->bind == STB_GLOBAL)
 		for (i = 0; i < ARRAY_SIZE(global_noreturns); i++)
 			if (!strcmp(func->name, global_noreturns[i]))
-				return true;
+				return 1;
 
 	if (!func->sec)
-		return false;
+		return 0;
 
 	func_insn = find_instruction(file, func->sec, func->offset);
 	if (!func_insn)
-		return false;
+		return 0;
 
 	insn = func_insn;
 	list_for_each_entry_from(insn, &file->insns, list) {
@@ -167,11 +173,11 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 		empty = false;
 
 		if (insn->type == INSN_RETURN)
-			return false;
+			return 0;
 	}
 
 	if (empty)
-		return false;
+		return 0;
 
 	/*
 	 * A function can have a sibling call instead of a return.  In that
@@ -190,7 +196,7 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 
 			if (!dest)
 				/* sibling call to another file */
-				return false;
+				return 0;
 
 			if (dest->sec != func->sec ||
 			    dest->offset < func->offset ||
@@ -201,16 +207,28 @@ static bool dead_end_function(struct objtool_file *file, struct symbol *func)
 				if (!dest_func)
 					continue;
 
-				return dead_end_function(file, dest_func);
+				if (recursion == 5) {
+					WARN_FUNC("infinite recursion (objtool bug!)",
+						  dest->sec, dest->offset);
+					return -1;
+				}
+
+				return __dead_end_function(file, dest_func,
+							   recursion + 1);
 			}
 		}
 
 		if (insn->type == INSN_JUMP_DYNAMIC)
 			/* sibling call */
-			return false;
+			return 0;
 	}
 
-	return true;
+	return 1;
+}
+
+static int dead_end_function(struct objtool_file *file, struct symbol *func)
+{
+	return __dead_end_function(file, func, 0);
 }
 
 /*
@@ -809,8 +827,11 @@ static int validate_branch(struct objtool_file *file,
 				break;
 			}
 
-			if (dead_end_function(file, insn->call_dest))
+			ret = dead_end_function(file, insn->call_dest);
+			if (ret == 1)
 				return warnings;
+			if (ret == -1)
+				warnings++;
 
 			/* fallthrough */
 		case INSN_CALL_DYNAMIC:

[toc] | [prev] | [next] | [standalone]

#1353851 — [PATCH 06/11] objtool: Remove superflous INIT_LIST_HEAD

The insns list is initialized twice, in cmd_check() and in
decode_instructions().  Remove the latter.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 46a8985..a974f295 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -249,8 +249,6 @@ static int decode_instructions(struct objtool_file *file)
 	struct instruction *insn;
 	int ret;
 
-	INIT_LIST_HEAD(&file->insns);
-
 	list_for_each_entry(sec, &file->elf->sections, list) {
 
 		if (!(sec->sh.sh_flags & SHF_EXECINSTR))
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354049 — [tip:core/objtool] objtool: Remove superflous INIT_LIST_HEAD

Commit-ID:  e2a5f18a1ba11e8b1e9ee53b6fca4be12bb5749e
Gitweb:     http://git.kernel.org/tip/e2a5f18a1ba11e8b1e9ee53b6fca4be12bb5749e
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:56 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:08 +0100

objtool: Remove superflous INIT_LIST_HEAD

The insns list is initialized twice, in cmd_check() and in
decode_instructions().  Remove the latter.

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

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index 46a8985..a974f295 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -249,8 +249,6 @@ static int decode_instructions(struct objtool_file *file)
 	struct instruction *insn;
 	int ret;
 
-	INIT_LIST_HEAD(&file->insns);
-
 	list_for_each_entry(sec, &file->elf->sections, list) {
 
 		if (!(sec->sh.sh_flags & SHF_EXECINSTR))

[toc] | [prev] | [next] | [standalone]

#1353853 — [PATCH 07/11] objtool: Rename some variables and functions

Rename some list heads to distinguish them from hash node heads, which
are added later in the patch series.

Also rename the get_*() functions to add_*(), which is more descriptive:
they "add" data to the objtool_file struct.

Also rename rodata_rela and text_rela to be clearer:
- text_rela refers to a rela entry in .rela.text.
- rodata_rela refers to a rela entry in .rela.rodata.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 80 ++++++++++++++++++++++---------------------
 tools/objtool/elf.c           | 22 ++++++------
 tools/objtool/elf.h           |  4 +--
 3 files changed, 54 insertions(+), 52 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index a974f295..cdbdd7d 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -60,7 +60,7 @@ struct alternative {
 
 struct objtool_file {
 	struct elf *elf;
-	struct list_head insns;
+	struct list_head insn_list;
 };
 
 const char *objname;
@@ -71,7 +71,7 @@ static struct instruction *find_insn(struct objtool_file *file,
 {
 	struct instruction *insn;
 
-	list_for_each_entry(insn, &file->insns, list)
+	list_for_each_entry(insn, &file->insn_list, list)
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
 
@@ -83,18 +83,18 @@ static struct instruction *next_insn_same_sec(struct objtool_file *file,
 {
 	struct instruction *next = list_next_entry(insn, list);
 
-	if (&next->list == &file->insns || next->sec != insn->sec)
+	if (&next->list == &file->insn_list || next->sec != insn->sec)
 		return NULL;
 
 	return next;
 }
 
 #define for_each_insn(file, insn)					\
-	list_for_each_entry(insn, &file->insns, list)
+	list_for_each_entry(insn, &file->insn_list, list)
 
 #define func_for_each_insn(file, func, insn)				\
 	for (insn = find_insn(file, func->sec, func->offset);		\
-	     insn && &insn->list != &file->insns &&			\
+	     insn && &insn->list != &file->insn_list &&			\
 		insn->sec == func->sec &&				\
 		insn->offset < func->offset + func->len;		\
 	     insn = list_next_entry(insn, list))
@@ -117,7 +117,7 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
 	/* check for STACK_FRAME_NON_STANDARD */
 	macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
 	if (macro_sec && macro_sec->rela)
-		list_for_each_entry(rela, &macro_sec->rela->relas, list)
+		list_for_each_entry(rela, &macro_sec->rela->rela_list, list)
 			if (rela->sym->sec == func->sec &&
 			    rela->addend == func->offset)
 				return true;
@@ -240,7 +240,7 @@ static int dead_end_function(struct objtool_file *file, struct symbol *func)
 
 /*
  * Call the arch-specific instruction decoder for all the instructions and add
- * them to the global insns list.
+ * them to the global instruction list.
  */
 static int decode_instructions(struct objtool_file *file)
 {
@@ -275,7 +275,7 @@ static int decode_instructions(struct objtool_file *file)
 				return -1;
 			}
 
-			list_add_tail(&insn->list, &file->insns);
+			list_add_tail(&insn->list, &file->insn_list);
 		}
 	}
 
@@ -285,14 +285,14 @@ static int decode_instructions(struct objtool_file *file)
 /*
  * Warnings shouldn't be reported for ignored functions.
  */
-static void get_ignores(struct objtool_file *file)
+static void add_ignores(struct objtool_file *file)
 {
 	struct instruction *insn;
 	struct section *sec;
 	struct symbol *func;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
-		list_for_each_entry(func, &sec->symbols, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
 			if (func->type != STT_FUNC)
 				continue;
 
@@ -308,7 +308,7 @@ static void get_ignores(struct objtool_file *file)
 /*
  * Find the destination instructions for all jumps.
  */
-static int get_jump_destinations(struct objtool_file *file)
+static int add_jump_destinations(struct objtool_file *file)
 {
 	struct instruction *insn;
 	struct rela *rela;
@@ -365,7 +365,7 @@ static int get_jump_destinations(struct objtool_file *file)
 /*
  * Find the destination instructions for all calls.
  */
-static int get_call_destinations(struct objtool_file *file)
+static int add_call_destinations(struct objtool_file *file)
 {
 	struct instruction *insn;
 	unsigned long dest_off;
@@ -534,7 +534,7 @@ static int handle_jump_alt(struct objtool_file *file,
  * instruction(s) has them added to its insn->alts list, which will be
  * traversed in validate_branch().
  */
-static int get_special_section_alts(struct objtool_file *file)
+static int add_special_section_alts(struct objtool_file *file)
 {
 	struct list_head special_alts;
 	struct instruction *orig_insn, *new_insn;
@@ -604,10 +604,10 @@ out:
  * section which contains a list of addresses within the function to jump to.
  * This finds these jump tables and adds them to the insn->alts lists.
  */
-static int get_switch_alts(struct objtool_file *file)
+static int add_switch_table_alts(struct objtool_file *file)
 {
 	struct instruction *insn, *alt_insn;
-	struct rela *rodata_rela, *rela;
+	struct rela *rodata_rela, *text_rela;
 	struct section *rodata;
 	struct symbol *func;
 	struct alternative *alt;
@@ -616,9 +616,9 @@ static int get_switch_alts(struct objtool_file *file)
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
-		rodata_rela = find_rela_by_dest_range(insn->sec, insn->offset,
-						      insn->len);
-		if (!rodata_rela || strcmp(rodata_rela->sym->name, ".rodata"))
+		text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
+						    insn->len);
+		if (!text_rela || strcmp(text_rela->sym->name, ".rodata"))
 			continue;
 
 		rodata = find_section_by_name(file->elf, ".rodata");
@@ -626,13 +626,13 @@ static int get_switch_alts(struct objtool_file *file)
 			continue;
 
 		/* common case: jmpq *[addr](,%rax,8) */
-		rela = find_rela_by_dest(rodata, rodata_rela->addend);
+		rodata_rela = find_rela_by_dest(rodata, text_rela->addend);
 
 		/* rare case:   jmpq *[addr](%rip) */
-		if (!rela)
-			rela = find_rela_by_dest(rodata,
-						 rodata_rela->addend + 4);
-		if (!rela)
+		if (!rodata_rela)
+			rodata_rela = find_rela_by_dest(rodata,
+							text_rela->addend + 4);
+		if (!rodata_rela)
 			continue;
 
 		func = find_containing_func(insn->sec, insn->offset);
@@ -642,17 +642,19 @@ static int get_switch_alts(struct objtool_file *file)
 			return -1;
 		}
 
-		list_for_each_entry_from(rela, &rodata->rela->relas, list) {
-			if (rela->sym->sec != insn->sec ||
-			    rela->addend <= func->offset ||
-			    rela->addend >= func->offset + func->len)
+		list_for_each_entry_from(rodata_rela, &rodata->rela->rela_list,
+					 list) {
+			if (rodata_rela->sym->sec != insn->sec ||
+			    rodata_rela->addend <= func->offset ||
+			    rodata_rela->addend >= func->offset + func->len)
 				break;
 
-			alt_insn = find_insn(file, insn->sec, rela->addend);
+			alt_insn = find_insn(file, insn->sec,
+					     rodata_rela->addend);
 			if (!alt_insn) {
 				WARN("%s: can't find instruction at %s+0x%x",
 				     rodata->rela->name, insn->sec->name,
-				     rela->addend);
+				     rodata_rela->addend);
 				return -1;
 			}
 
@@ -678,21 +680,21 @@ static int decode_sections(struct objtool_file *file)
 	if (ret)
 		return ret;
 
-	get_ignores(file);
+	add_ignores(file);
 
-	ret = get_jump_destinations(file);
+	ret = add_jump_destinations(file);
 	if (ret)
 		return ret;
 
-	ret = get_call_destinations(file);
+	ret = add_call_destinations(file);
 	if (ret)
 		return ret;
 
-	ret = get_special_section_alts(file);
+	ret = add_special_section_alts(file);
 	if (ret)
 		return ret;
 
-	ret = get_switch_alts(file);
+	ret = add_switch_table_alts(file);
 	if (ret)
 		return ret;
 
@@ -901,7 +903,7 @@ static bool is_gcov_insn(struct instruction *insn)
 	sec = rela->sym->sec;
 	offset = rela->addend + insn->offset + insn->len - rela->offset;
 
-	list_for_each_entry(sym, &sec->symbols, list) {
+	list_for_each_entry(sym, &sec->symbol_list, list) {
 		if (sym->type != STT_OBJECT)
 			continue;
 
@@ -968,7 +970,7 @@ static int validate_functions(struct objtool_file *file)
 	int ret, warnings = 0;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
-		list_for_each_entry(func, &sec->symbols, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
 			if (func->type != STT_FUNC)
 				continue;
 
@@ -986,7 +988,7 @@ static int validate_functions(struct objtool_file *file)
 	}
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
-		list_for_each_entry(func, &sec->symbols, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
 			if (func->type != STT_FUNC)
 				continue;
 
@@ -1028,7 +1030,7 @@ static void cleanup(struct objtool_file *file)
 	struct instruction *insn, *tmpinsn;
 	struct alternative *alt, *tmpalt;
 
-	list_for_each_entry_safe(insn, tmpinsn, &file->insns, list) {
+	list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
 		list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
 			list_del(&alt->list);
 			free(alt);
@@ -1067,7 +1069,7 @@ int cmd_check(int argc, const char **argv)
 		return 1;
 	}
 
-	INIT_LIST_HEAD(&file.insns);
+	INIT_LIST_HEAD(&file.insn_list);
 
 	ret = decode_sections(&file);
 	if (ret < 0)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index d547e3f..7de243f 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -59,7 +59,7 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 	struct symbol *sym;
 
 	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbols, list)
+		list_for_each_entry(sym, &sec->symbol_list, list)
 			if (sym->idx == idx)
 				return sym;
 
@@ -70,7 +70,7 @@ struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
 {
 	struct symbol *sym;
 
-	list_for_each_entry(sym, &sec->symbols, list)
+	list_for_each_entry(sym, &sec->symbol_list, list)
 		if (sym->type != STT_SECTION &&
 		    sym->offset == offset)
 			return sym;
@@ -86,7 +86,7 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 	if (!sec->rela)
 		return NULL;
 
-	list_for_each_entry(rela, &sec->rela->relas, list)
+	list_for_each_entry(rela, &sec->rela->rela_list, list)
 		if (rela->offset >= offset && rela->offset < offset + len)
 			return rela;
 
@@ -102,7 +102,7 @@ struct symbol *find_containing_func(struct section *sec, unsigned long offset)
 {
 	struct symbol *func;
 
-	list_for_each_entry(func, &sec->symbols, list)
+	list_for_each_entry(func, &sec->symbol_list, list)
 		if (func->type == STT_FUNC && offset >= func->offset &&
 		    offset < func->offset + func->len)
 			return func;
@@ -135,8 +135,8 @@ static int read_sections(struct elf *elf)
 		}
 		memset(sec, 0, sizeof(*sec));
 
-		INIT_LIST_HEAD(&sec->symbols);
-		INIT_LIST_HEAD(&sec->relas);
+		INIT_LIST_HEAD(&sec->symbol_list);
+		INIT_LIST_HEAD(&sec->rela_list);
 
 		list_add_tail(&sec->list, &elf->sections);
 
@@ -244,8 +244,8 @@ static int read_symbols(struct elf *elf)
 		sym->len = sym->sym.st_size;
 
 		/* sorted insert into a per-section list */
-		entry = &sym->sec->symbols;
-		list_for_each_prev(tmp, &sym->sec->symbols) {
+		entry = &sym->sec->symbol_list;
+		list_for_each_prev(tmp, &sym->sec->symbol_list) {
 			struct symbol *s;
 
 			s = list_entry(tmp, struct symbol, list);
@@ -298,7 +298,7 @@ static int read_relas(struct elf *elf)
 			}
 			memset(rela, 0, sizeof(*rela));
 
-			list_add_tail(&rela->list, &sec->relas);
+			list_add_tail(&rela->list, &sec->rela_list);
 
 			if (!gelf_getrela(sec->elf_data, i, &rela->rela)) {
 				perror("gelf_getrela");
@@ -382,11 +382,11 @@ void elf_close(struct elf *elf)
 	struct rela *rela, *tmprela;
 
 	list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
-		list_for_each_entry_safe(sym, tmpsym, &sec->symbols, list) {
+		list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
 			list_del(&sym->list);
 			free(sym);
 		}
-		list_for_each_entry_safe(rela, tmprela, &sec->relas, list) {
+		list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) {
 			list_del(&rela->list);
 			free(rela);
 		}
diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index 66919de..57e4653 100644
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -25,8 +25,8 @@
 struct section {
 	struct list_head list;
 	GElf_Shdr sh;
-	struct list_head symbols;
-	struct list_head relas;
+	struct list_head symbol_list;
+	struct list_head rela_list;
 	struct section *base, *rela;
 	struct symbol *sym;
 	Elf_Data *elf_data;
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354053 — [tip:core/objtool] objtool: Rename some variables and functions

Commit-ID:  a196e17198224cacd2d992f12cb6d81d354de82f
Gitweb:     http://git.kernel.org/tip/a196e17198224cacd2d992f12cb6d81d354de82f
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:57 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:09 +0100

objtool: Rename some variables and functions

Rename some list heads to distinguish them from hash node heads, which
are added later in the patch series.

Also rename the get_*() functions to add_*(), which is more descriptive:
they "add" data to the objtool_file struct.

Also rename rodata_rela and text_rela to be clearer:
- text_rela refers to a rela entry in .rela.text.
- rodata_rela refers to a rela entry in .rela.rodata.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/ee0eca2bba8482aa45758958c5586c00a7b71e62.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 80 ++++++++++++++++++++++---------------------
 tools/objtool/elf.c           | 22 ++++++------
 tools/objtool/elf.h           |  4 +--
 3 files changed, 54 insertions(+), 52 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index a974f295..cdbdd7d 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -60,7 +60,7 @@ struct alternative {
 
 struct objtool_file {
 	struct elf *elf;
-	struct list_head insns;
+	struct list_head insn_list;
 };
 
 const char *objname;
@@ -71,7 +71,7 @@ static struct instruction *find_insn(struct objtool_file *file,
 {
 	struct instruction *insn;
 
-	list_for_each_entry(insn, &file->insns, list)
+	list_for_each_entry(insn, &file->insn_list, list)
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
 
@@ -83,18 +83,18 @@ static struct instruction *next_insn_same_sec(struct objtool_file *file,
 {
 	struct instruction *next = list_next_entry(insn, list);
 
-	if (&next->list == &file->insns || next->sec != insn->sec)
+	if (&next->list == &file->insn_list || next->sec != insn->sec)
 		return NULL;
 
 	return next;
 }
 
 #define for_each_insn(file, insn)					\
-	list_for_each_entry(insn, &file->insns, list)
+	list_for_each_entry(insn, &file->insn_list, list)
 
 #define func_for_each_insn(file, func, insn)				\
 	for (insn = find_insn(file, func->sec, func->offset);		\
-	     insn && &insn->list != &file->insns &&			\
+	     insn && &insn->list != &file->insn_list &&			\
 		insn->sec == func->sec &&				\
 		insn->offset < func->offset + func->len;		\
 	     insn = list_next_entry(insn, list))
@@ -117,7 +117,7 @@ static bool ignore_func(struct objtool_file *file, struct symbol *func)
 	/* check for STACK_FRAME_NON_STANDARD */
 	macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
 	if (macro_sec && macro_sec->rela)
-		list_for_each_entry(rela, &macro_sec->rela->relas, list)
+		list_for_each_entry(rela, &macro_sec->rela->rela_list, list)
 			if (rela->sym->sec == func->sec &&
 			    rela->addend == func->offset)
 				return true;
@@ -240,7 +240,7 @@ static int dead_end_function(struct objtool_file *file, struct symbol *func)
 
 /*
  * Call the arch-specific instruction decoder for all the instructions and add
- * them to the global insns list.
+ * them to the global instruction list.
  */
 static int decode_instructions(struct objtool_file *file)
 {
@@ -275,7 +275,7 @@ static int decode_instructions(struct objtool_file *file)
 				return -1;
 			}
 
-			list_add_tail(&insn->list, &file->insns);
+			list_add_tail(&insn->list, &file->insn_list);
 		}
 	}
 
@@ -285,14 +285,14 @@ static int decode_instructions(struct objtool_file *file)
 /*
  * Warnings shouldn't be reported for ignored functions.
  */
-static void get_ignores(struct objtool_file *file)
+static void add_ignores(struct objtool_file *file)
 {
 	struct instruction *insn;
 	struct section *sec;
 	struct symbol *func;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
-		list_for_each_entry(func, &sec->symbols, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
 			if (func->type != STT_FUNC)
 				continue;
 
@@ -308,7 +308,7 @@ static void get_ignores(struct objtool_file *file)
 /*
  * Find the destination instructions for all jumps.
  */
-static int get_jump_destinations(struct objtool_file *file)
+static int add_jump_destinations(struct objtool_file *file)
 {
 	struct instruction *insn;
 	struct rela *rela;
@@ -365,7 +365,7 @@ static int get_jump_destinations(struct objtool_file *file)
 /*
  * Find the destination instructions for all calls.
  */
-static int get_call_destinations(struct objtool_file *file)
+static int add_call_destinations(struct objtool_file *file)
 {
 	struct instruction *insn;
 	unsigned long dest_off;
@@ -534,7 +534,7 @@ static int handle_jump_alt(struct objtool_file *file,
  * instruction(s) has them added to its insn->alts list, which will be
  * traversed in validate_branch().
  */
-static int get_special_section_alts(struct objtool_file *file)
+static int add_special_section_alts(struct objtool_file *file)
 {
 	struct list_head special_alts;
 	struct instruction *orig_insn, *new_insn;
@@ -604,10 +604,10 @@ out:
  * section which contains a list of addresses within the function to jump to.
  * This finds these jump tables and adds them to the insn->alts lists.
  */
-static int get_switch_alts(struct objtool_file *file)
+static int add_switch_table_alts(struct objtool_file *file)
 {
 	struct instruction *insn, *alt_insn;
-	struct rela *rodata_rela, *rela;
+	struct rela *rodata_rela, *text_rela;
 	struct section *rodata;
 	struct symbol *func;
 	struct alternative *alt;
@@ -616,9 +616,9 @@ static int get_switch_alts(struct objtool_file *file)
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
-		rodata_rela = find_rela_by_dest_range(insn->sec, insn->offset,
-						      insn->len);
-		if (!rodata_rela || strcmp(rodata_rela->sym->name, ".rodata"))
+		text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
+						    insn->len);
+		if (!text_rela || strcmp(text_rela->sym->name, ".rodata"))
 			continue;
 
 		rodata = find_section_by_name(file->elf, ".rodata");
@@ -626,13 +626,13 @@ static int get_switch_alts(struct objtool_file *file)
 			continue;
 
 		/* common case: jmpq *[addr](,%rax,8) */
-		rela = find_rela_by_dest(rodata, rodata_rela->addend);
+		rodata_rela = find_rela_by_dest(rodata, text_rela->addend);
 
 		/* rare case:   jmpq *[addr](%rip) */
-		if (!rela)
-			rela = find_rela_by_dest(rodata,
-						 rodata_rela->addend + 4);
-		if (!rela)
+		if (!rodata_rela)
+			rodata_rela = find_rela_by_dest(rodata,
+							text_rela->addend + 4);
+		if (!rodata_rela)
 			continue;
 
 		func = find_containing_func(insn->sec, insn->offset);
@@ -642,17 +642,19 @@ static int get_switch_alts(struct objtool_file *file)
 			return -1;
 		}
 
-		list_for_each_entry_from(rela, &rodata->rela->relas, list) {
-			if (rela->sym->sec != insn->sec ||
-			    rela->addend <= func->offset ||
-			    rela->addend >= func->offset + func->len)
+		list_for_each_entry_from(rodata_rela, &rodata->rela->rela_list,
+					 list) {
+			if (rodata_rela->sym->sec != insn->sec ||
+			    rodata_rela->addend <= func->offset ||
+			    rodata_rela->addend >= func->offset + func->len)
 				break;
 
-			alt_insn = find_insn(file, insn->sec, rela->addend);
+			alt_insn = find_insn(file, insn->sec,
+					     rodata_rela->addend);
 			if (!alt_insn) {
 				WARN("%s: can't find instruction at %s+0x%x",
 				     rodata->rela->name, insn->sec->name,
-				     rela->addend);
+				     rodata_rela->addend);
 				return -1;
 			}
 
@@ -678,21 +680,21 @@ static int decode_sections(struct objtool_file *file)
 	if (ret)
 		return ret;
 
-	get_ignores(file);
+	add_ignores(file);
 
-	ret = get_jump_destinations(file);
+	ret = add_jump_destinations(file);
 	if (ret)
 		return ret;
 
-	ret = get_call_destinations(file);
+	ret = add_call_destinations(file);
 	if (ret)
 		return ret;
 
-	ret = get_special_section_alts(file);
+	ret = add_special_section_alts(file);
 	if (ret)
 		return ret;
 
-	ret = get_switch_alts(file);
+	ret = add_switch_table_alts(file);
 	if (ret)
 		return ret;
 
@@ -901,7 +903,7 @@ static bool is_gcov_insn(struct instruction *insn)
 	sec = rela->sym->sec;
 	offset = rela->addend + insn->offset + insn->len - rela->offset;
 
-	list_for_each_entry(sym, &sec->symbols, list) {
+	list_for_each_entry(sym, &sec->symbol_list, list) {
 		if (sym->type != STT_OBJECT)
 			continue;
 
@@ -968,7 +970,7 @@ static int validate_functions(struct objtool_file *file)
 	int ret, warnings = 0;
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
-		list_for_each_entry(func, &sec->symbols, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
 			if (func->type != STT_FUNC)
 				continue;
 
@@ -986,7 +988,7 @@ static int validate_functions(struct objtool_file *file)
 	}
 
 	list_for_each_entry(sec, &file->elf->sections, list) {
-		list_for_each_entry(func, &sec->symbols, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
 			if (func->type != STT_FUNC)
 				continue;
 
@@ -1028,7 +1030,7 @@ static void cleanup(struct objtool_file *file)
 	struct instruction *insn, *tmpinsn;
 	struct alternative *alt, *tmpalt;
 
-	list_for_each_entry_safe(insn, tmpinsn, &file->insns, list) {
+	list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
 		list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
 			list_del(&alt->list);
 			free(alt);
@@ -1067,7 +1069,7 @@ int cmd_check(int argc, const char **argv)
 		return 1;
 	}
 
-	INIT_LIST_HEAD(&file.insns);
+	INIT_LIST_HEAD(&file.insn_list);
 
 	ret = decode_sections(&file);
 	if (ret < 0)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index d547e3f..7de243f 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -59,7 +59,7 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 	struct symbol *sym;
 
 	list_for_each_entry(sec, &elf->sections, list)
-		list_for_each_entry(sym, &sec->symbols, list)
+		list_for_each_entry(sym, &sec->symbol_list, list)
 			if (sym->idx == idx)
 				return sym;
 
@@ -70,7 +70,7 @@ struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
 {
 	struct symbol *sym;
 
-	list_for_each_entry(sym, &sec->symbols, list)
+	list_for_each_entry(sym, &sec->symbol_list, list)
 		if (sym->type != STT_SECTION &&
 		    sym->offset == offset)
 			return sym;
@@ -86,7 +86,7 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 	if (!sec->rela)
 		return NULL;
 
-	list_for_each_entry(rela, &sec->rela->relas, list)
+	list_for_each_entry(rela, &sec->rela->rela_list, list)
 		if (rela->offset >= offset && rela->offset < offset + len)
 			return rela;
 
@@ -102,7 +102,7 @@ struct symbol *find_containing_func(struct section *sec, unsigned long offset)
 {
 	struct symbol *func;
 
-	list_for_each_entry(func, &sec->symbols, list)
+	list_for_each_entry(func, &sec->symbol_list, list)
 		if (func->type == STT_FUNC && offset >= func->offset &&
 		    offset < func->offset + func->len)
 			return func;
@@ -135,8 +135,8 @@ static int read_sections(struct elf *elf)
 		}
 		memset(sec, 0, sizeof(*sec));
 
-		INIT_LIST_HEAD(&sec->symbols);
-		INIT_LIST_HEAD(&sec->relas);
+		INIT_LIST_HEAD(&sec->symbol_list);
+		INIT_LIST_HEAD(&sec->rela_list);
 
 		list_add_tail(&sec->list, &elf->sections);
 
@@ -244,8 +244,8 @@ static int read_symbols(struct elf *elf)
 		sym->len = sym->sym.st_size;
 
 		/* sorted insert into a per-section list */
-		entry = &sym->sec->symbols;
-		list_for_each_prev(tmp, &sym->sec->symbols) {
+		entry = &sym->sec->symbol_list;
+		list_for_each_prev(tmp, &sym->sec->symbol_list) {
 			struct symbol *s;
 
 			s = list_entry(tmp, struct symbol, list);
@@ -298,7 +298,7 @@ static int read_relas(struct elf *elf)
 			}
 			memset(rela, 0, sizeof(*rela));
 
-			list_add_tail(&rela->list, &sec->relas);
+			list_add_tail(&rela->list, &sec->rela_list);
 
 			if (!gelf_getrela(sec->elf_data, i, &rela->rela)) {
 				perror("gelf_getrela");
@@ -382,11 +382,11 @@ void elf_close(struct elf *elf)
 	struct rela *rela, *tmprela;
 
 	list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
-		list_for_each_entry_safe(sym, tmpsym, &sec->symbols, list) {
+		list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
 			list_del(&sym->list);
 			free(sym);
 		}
-		list_for_each_entry_safe(rela, tmprela, &sec->relas, list) {
+		list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) {
 			list_del(&rela->list);
 			free(rela);
 		}
diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index 66919de..57e4653 100644
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -25,8 +25,8 @@
 struct section {
 	struct list_head list;
 	GElf_Shdr sh;
-	struct list_head symbols;
-	struct list_head relas;
+	struct list_head symbol_list;
+	struct list_head rela_list;
 	struct section *base, *rela;
 	struct symbol *sym;
 	Elf_Data *elf_data;

[toc] | [prev] | [next] | [standalone]

#1353854 — [PATCH 08/11] objtool: Fix false positive warnings for functions with multiple switch statements

Ingo reported [1] some false positive objtool warnings:

  drivers/net/wireless/realtek/rtlwifi/base.o: warning: objtool: rtlwifi_rate_mapping()+0x2e7: frame pointer state mismatch
  drivers/net/wireless/realtek/rtlwifi/base.o: warning: objtool: rtlwifi_rate_mapping()+0x2f3: frame pointer state mismatch
  ...

And so did the 0-day bot [2]:

  drivers/gpu/drm/radeon/cik.o: warning: objtool: cik_tiling_mode_table_init()+0x6ce: call without frame pointer save/setup
  drivers/gpu/drm/radeon/cik.o: warning: objtool: cik_tiling_mode_table_init()+0x72b: call without frame pointer save/setup
  ...

Both sets of warnings involve functions which have multiple switch
statements.  When there's more than one switch statement in a function,
objtool interprets all the switch jump tables as a single table.  If the
targets of one jump table assume a stack frame and the targets of
another one don't, it prints false positive warnings.

Fix the bug by detecting the size of each switch jump table.  For
multiple tables, each one ends where the next one begins.

[1] https://lkml.kernel.org/r/20160308103716.GA9618@gmail.com
[2] https://lists.01.org/pipermail/kbuild-all/2016-March/018124.html

Reported-by: Ingo Molnar <mingo@kernel.org>
Reported-by: kbuild test robot <fengguang.wu@intel.com>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/builtin-check.c | 145 +++++++++++++++++++++++++++++-------------
 1 file changed, 100 insertions(+), 45 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index cdbdd7d..cf1e48d 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -61,6 +61,7 @@ struct alternative {
 struct objtool_file {
 	struct elf *elf;
 	struct list_head insn_list;
+	struct section *rodata;
 };
 
 const char *objname;
@@ -599,73 +600,125 @@ out:
 	return ret;
 }
 
-/*
- * For some switch statements, gcc generates a jump table in the .rodata
- * section which contains a list of addresses within the function to jump to.
- * This finds these jump tables and adds them to the insn->alts lists.
- */
-static int add_switch_table_alts(struct objtool_file *file)
+static int add_switch_table(struct objtool_file *file, struct symbol *func,
+			    struct instruction *insn, struct rela *table,
+			    struct rela *next_table)
 {
-	struct instruction *insn, *alt_insn;
-	struct rela *rodata_rela, *text_rela;
-	struct section *rodata;
-	struct symbol *func;
+	struct rela *rela = table;
+	struct instruction *alt_insn;
 	struct alternative *alt;
 
-	for_each_insn(file, insn) {
+	list_for_each_entry_from(rela, &file->rodata->rela->rela_list, list) {
+		if (rela == next_table)
+			break;
+
+		if (rela->sym->sec != insn->sec ||
+		    rela->addend <= func->offset ||
+		    rela->addend >= func->offset + func->len)
+			break;
+
+		alt_insn = find_insn(file, insn->sec, rela->addend);
+		if (!alt_insn) {
+			WARN("%s: can't find instruction at %s+0x%x",
+			     file->rodata->rela->name, insn->sec->name,
+			     rela->addend);
+			return -1;
+		}
+
+		alt = malloc(sizeof(*alt));
+		if (!alt) {
+			WARN("malloc failed");
+			return -1;
+		}
+
+		alt->insn = alt_insn;
+		list_add_tail(&alt->list, &insn->alts);
+	}
+
+	return 0;
+}
+
+static int add_func_switch_tables(struct objtool_file *file,
+				  struct symbol *func)
+{
+	struct instruction *insn, *prev_jump;
+	struct rela *text_rela, *rodata_rela, *prev_rela;
+	int ret;
+
+	prev_jump = NULL;
+
+	func_for_each_insn(file, func, insn) {
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
 		text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
 						    insn->len);
-		if (!text_rela || strcmp(text_rela->sym->name, ".rodata"))
-			continue;
-
-		rodata = find_section_by_name(file->elf, ".rodata");
-		if (!rodata || !rodata->rela)
+		if (!text_rela || text_rela->sym != file->rodata->sym)
 			continue;
 
 		/* common case: jmpq *[addr](,%rax,8) */
-		rodata_rela = find_rela_by_dest(rodata, text_rela->addend);
+		rodata_rela = find_rela_by_dest(file->rodata,
+						text_rela->addend);
 
-		/* rare case:   jmpq *[addr](%rip) */
+		/*
+		 * TODO: Document where this is needed, or get rid of it.
+		 *
+		 * rare case:   jmpq *[addr](%rip)
+		 */
 		if (!rodata_rela)
-			rodata_rela = find_rela_by_dest(rodata,
+			rodata_rela = find_rela_by_dest(file->rodata,
 							text_rela->addend + 4);
+
 		if (!rodata_rela)
 			continue;
 
-		func = find_containing_func(insn->sec, insn->offset);
-		if (!func) {
-			WARN_FUNC("can't find containing func",
-				  insn->sec, insn->offset);
-			return -1;
+		/*
+		 * We found a switch table, but we don't know yet how big it
+		 * is.  Don't add it until we reach the end of the function or
+		 * the beginning of another switch table in the same function.
+		 */
+		if (prev_jump) {
+			ret = add_switch_table(file, func, prev_jump, prev_rela,
+					       rodata_rela);
+			if (ret)
+				return ret;
 		}
 
-		list_for_each_entry_from(rodata_rela, &rodata->rela->rela_list,
-					 list) {
-			if (rodata_rela->sym->sec != insn->sec ||
-			    rodata_rela->addend <= func->offset ||
-			    rodata_rela->addend >= func->offset + func->len)
-				break;
+		prev_jump = insn;
+		prev_rela = rodata_rela;
+	}
 
-			alt_insn = find_insn(file, insn->sec,
-					     rodata_rela->addend);
-			if (!alt_insn) {
-				WARN("%s: can't find instruction at %s+0x%x",
-				     rodata->rela->name, insn->sec->name,
-				     rodata_rela->addend);
-				return -1;
-			}
+	if (prev_jump) {
+		ret = add_switch_table(file, func, prev_jump, prev_rela, NULL);
+		if (ret)
+			return ret;
+	}
 
-			alt = malloc(sizeof(*alt));
-			if (!alt) {
-				WARN("malloc failed");
-				return -1;
-			}
+	return 0;
+}
 
-			alt->insn = alt_insn;
-			list_add_tail(&alt->list, &insn->alts);
+/*
+ * For some switch statements, gcc generates a jump table in the .rodata
+ * section which contains a list of addresses within the function to jump to.
+ * This finds these jump tables and adds them to the insn->alts lists.
+ */
+static int add_switch_table_alts(struct objtool_file *file)
+{
+	struct section *sec;
+	struct symbol *func;
+	int ret;
+
+	if (!file->rodata || !file->rodata->rela)
+		return 0;
+
+	list_for_each_entry(sec, &file->elf->sections, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			ret = add_func_switch_tables(file, func);
+			if (ret)
+				return ret;
 		}
 	}
 
@@ -676,6 +729,8 @@ static int decode_sections(struct objtool_file *file)
 {
 	int ret;
 
+	file->rodata = find_section_by_name(file->elf, ".rodata");
+
 	ret = decode_instructions(file);
 	if (ret)
 		return ret;
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

#1354051 — [tip:core/objtool] objtool: Fix false positive warnings for functions with multiple switch statements

Commit-ID:  8133fbb4240ae2918d993defa0f6824864412f56
Gitweb:     http://git.kernel.org/tip/8133fbb4240ae2918d993defa0f6824864412f56
Author:     Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:06:58 -0600
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 9 Mar 2016 10:48:09 +0100

objtool: Fix false positive warnings for functions with multiple switch statements

Ingo reported [1] some false positive objtool warnings:

  drivers/net/wireless/realtek/rtlwifi/base.o: warning: objtool: rtlwifi_rate_mapping()+0x2e7: frame pointer state mismatch
  drivers/net/wireless/realtek/rtlwifi/base.o: warning: objtool: rtlwifi_rate_mapping()+0x2f3: frame pointer state mismatch
  ...

And so did the 0-day bot [2]:

  drivers/gpu/drm/radeon/cik.o: warning: objtool: cik_tiling_mode_table_init()+0x6ce: call without frame pointer save/setup
  drivers/gpu/drm/radeon/cik.o: warning: objtool: cik_tiling_mode_table_init()+0x72b: call without frame pointer save/setup
  ...

Both sets of warnings involve functions which have multiple switch
statements.  When there's more than one switch statement in a function,
objtool interprets all the switch jump tables as a single table.  If the
targets of one jump table assume a stack frame and the targets of
another one don't, it prints false positive warnings.

Fix the bug by detecting the size of each switch jump table.  For
multiple tables, each one ends where the next one begins.

[1] https://lkml.kernel.org/r/20160308103716.GA9618@gmail.com
[2] https://lists.01.org/pipermail/kbuild-all/2016-March/018124.html

Reported-by: Ingo Molnar <mingo@kernel.org>
Reported-by: kbuild test robot <fengguang.wu@intel.com>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/2d7eecc6bc52d301f494b80f5fd62c2b6c895658.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/objtool/builtin-check.c | 145 +++++++++++++++++++++++++++++-------------
 1 file changed, 100 insertions(+), 45 deletions(-)

diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c
index cdbdd7d..cf1e48d 100644
--- a/tools/objtool/builtin-check.c
+++ b/tools/objtool/builtin-check.c
@@ -61,6 +61,7 @@ struct alternative {
 struct objtool_file {
 	struct elf *elf;
 	struct list_head insn_list;
+	struct section *rodata;
 };
 
 const char *objname;
@@ -599,73 +600,125 @@ out:
 	return ret;
 }
 
-/*
- * For some switch statements, gcc generates a jump table in the .rodata
- * section which contains a list of addresses within the function to jump to.
- * This finds these jump tables and adds them to the insn->alts lists.
- */
-static int add_switch_table_alts(struct objtool_file *file)
+static int add_switch_table(struct objtool_file *file, struct symbol *func,
+			    struct instruction *insn, struct rela *table,
+			    struct rela *next_table)
 {
-	struct instruction *insn, *alt_insn;
-	struct rela *rodata_rela, *text_rela;
-	struct section *rodata;
-	struct symbol *func;
+	struct rela *rela = table;
+	struct instruction *alt_insn;
 	struct alternative *alt;
 
-	for_each_insn(file, insn) {
+	list_for_each_entry_from(rela, &file->rodata->rela->rela_list, list) {
+		if (rela == next_table)
+			break;
+
+		if (rela->sym->sec != insn->sec ||
+		    rela->addend <= func->offset ||
+		    rela->addend >= func->offset + func->len)
+			break;
+
+		alt_insn = find_insn(file, insn->sec, rela->addend);
+		if (!alt_insn) {
+			WARN("%s: can't find instruction at %s+0x%x",
+			     file->rodata->rela->name, insn->sec->name,
+			     rela->addend);
+			return -1;
+		}
+
+		alt = malloc(sizeof(*alt));
+		if (!alt) {
+			WARN("malloc failed");
+			return -1;
+		}
+
+		alt->insn = alt_insn;
+		list_add_tail(&alt->list, &insn->alts);
+	}
+
+	return 0;
+}
+
+static int add_func_switch_tables(struct objtool_file *file,
+				  struct symbol *func)
+{
+	struct instruction *insn, *prev_jump;
+	struct rela *text_rela, *rodata_rela, *prev_rela;
+	int ret;
+
+	prev_jump = NULL;
+
+	func_for_each_insn(file, func, insn) {
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
 		text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
 						    insn->len);
-		if (!text_rela || strcmp(text_rela->sym->name, ".rodata"))
-			continue;
-
-		rodata = find_section_by_name(file->elf, ".rodata");
-		if (!rodata || !rodata->rela)
+		if (!text_rela || text_rela->sym != file->rodata->sym)
 			continue;
 
 		/* common case: jmpq *[addr](,%rax,8) */
-		rodata_rela = find_rela_by_dest(rodata, text_rela->addend);
+		rodata_rela = find_rela_by_dest(file->rodata,
+						text_rela->addend);
 
-		/* rare case:   jmpq *[addr](%rip) */
+		/*
+		 * TODO: Document where this is needed, or get rid of it.
+		 *
+		 * rare case:   jmpq *[addr](%rip)
+		 */
 		if (!rodata_rela)
-			rodata_rela = find_rela_by_dest(rodata,
+			rodata_rela = find_rela_by_dest(file->rodata,
 							text_rela->addend + 4);
+
 		if (!rodata_rela)
 			continue;
 
-		func = find_containing_func(insn->sec, insn->offset);
-		if (!func) {
-			WARN_FUNC("can't find containing func",
-				  insn->sec, insn->offset);
-			return -1;
+		/*
+		 * We found a switch table, but we don't know yet how big it
+		 * is.  Don't add it until we reach the end of the function or
+		 * the beginning of another switch table in the same function.
+		 */
+		if (prev_jump) {
+			ret = add_switch_table(file, func, prev_jump, prev_rela,
+					       rodata_rela);
+			if (ret)
+				return ret;
 		}
 
-		list_for_each_entry_from(rodata_rela, &rodata->rela->rela_list,
-					 list) {
-			if (rodata_rela->sym->sec != insn->sec ||
-			    rodata_rela->addend <= func->offset ||
-			    rodata_rela->addend >= func->offset + func->len)
-				break;
+		prev_jump = insn;
+		prev_rela = rodata_rela;
+	}
 
-			alt_insn = find_insn(file, insn->sec,
-					     rodata_rela->addend);
-			if (!alt_insn) {
-				WARN("%s: can't find instruction at %s+0x%x",
-				     rodata->rela->name, insn->sec->name,
-				     rodata_rela->addend);
-				return -1;
-			}
+	if (prev_jump) {
+		ret = add_switch_table(file, func, prev_jump, prev_rela, NULL);
+		if (ret)
+			return ret;
+	}
 
-			alt = malloc(sizeof(*alt));
-			if (!alt) {
-				WARN("malloc failed");
-				return -1;
-			}
+	return 0;
+}
 
-			alt->insn = alt_insn;
-			list_add_tail(&alt->list, &insn->alts);
+/*
+ * For some switch statements, gcc generates a jump table in the .rodata
+ * section which contains a list of addresses within the function to jump to.
+ * This finds these jump tables and adds them to the insn->alts lists.
+ */
+static int add_switch_table_alts(struct objtool_file *file)
+{
+	struct section *sec;
+	struct symbol *func;
+	int ret;
+
+	if (!file->rodata || !file->rodata->rela)
+		return 0;
+
+	list_for_each_entry(sec, &file->elf->sections, list) {
+		list_for_each_entry(func, &sec->symbol_list, list) {
+			if (func->type != STT_FUNC)
+				continue;
+
+			ret = add_func_switch_tables(file, func);
+			if (ret)
+				return ret;
 		}
 	}
 
@@ -676,6 +729,8 @@ static int decode_sections(struct objtool_file *file)
 {
 	int ret;
 
+	file->rodata = find_section_by_name(file->elf, ".rodata");
+
 	ret = decode_instructions(file);
 	if (ret)
 		return ret;

[toc] | [prev] | [next] | [standalone]

#1353856 — [PATCH 09/11] tools/objtool: Copy hashtable.h into tools directory

Copy hashtable.h from include/linux/tools.h.  It's needed by objtool in
the next patch in the series.

Add some includes that it needs, and remove references to
kernel-specific features like RCU and __read_mostly.

Also change some if its dependency headers' includes to use quotes
instead of brackets so gcc can find them.

Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/include/asm-generic/bitops/__fls.h |   2 +-
 tools/include/asm-generic/bitops/fls.h   |   2 +-
 tools/include/asm-generic/bitops/fls64.h |   2 +-
 tools/include/linux/hashtable.h          | 152 +++++++++++++++++++++++++++++++
 4 files changed, 155 insertions(+), 3 deletions(-)
 create mode 100644 tools/include/linux/hashtable.h

diff --git a/tools/include/asm-generic/bitops/__fls.h b/tools/include/asm-generic/bitops/__fls.h
index 2218b9a..494c9c6 100644
--- a/tools/include/asm-generic/bitops/__fls.h
+++ b/tools/include/asm-generic/bitops/__fls.h
@@ -1 +1 @@
-#include <../../../../include/asm-generic/bitops/__fls.h>
+#include "../../../../include/asm-generic/bitops/__fls.h"
diff --git a/tools/include/asm-generic/bitops/fls.h b/tools/include/asm-generic/bitops/fls.h
index dbf711a..0e4995f 100644
--- a/tools/include/asm-generic/bitops/fls.h
+++ b/tools/include/asm-generic/bitops/fls.h
@@ -1 +1 @@
-#include <../../../../include/asm-generic/bitops/fls.h>
+#include "../../../../include/asm-generic/bitops/fls.h"
diff --git a/tools/include/asm-generic/bitops/fls64.h b/tools/include/asm-generic/bitops/fls64.h
index 980b1f6..35bee00 100644
--- a/tools/include/asm-generic/bitops/fls64.h
+++ b/tools/include/asm-generic/bitops/fls64.h
@@ -1 +1 @@
-#include <../../../../include/asm-generic/bitops/fls64.h>
+#include "../../../../include/asm-generic/bitops/fls64.h"
diff --git a/tools/include/linux/hashtable.h b/tools/include/linux/hashtable.h
new file mode 100644
index 0000000..c65cc0a
--- /dev/null
+++ b/tools/include/linux/hashtable.h
@@ -0,0 +1,152 @@
+/*
+ * Statically sized hash table implementation
+ * (C) 2012  Sasha Levin <levinsasha928@gmail.com>
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include <linux/list.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/bitops.h>
+#include <linux/hash.h>
+#include <linux/log2.h>
+
+#ifndef ARRAY_SIZE
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+#endif
+
+#define DEFINE_HASHTABLE(name, bits)						\
+	struct hlist_head name[1 << (bits)] =					\
+			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
+
+#define DECLARE_HASHTABLE(name, bits)                                   	\
+	struct hlist_head name[1 << (bits)]
+
+#define HASH_SIZE(name) (ARRAY_SIZE(name))
+#define HASH_BITS(name) ilog2(HASH_SIZE(name))
+
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
+#define hash_min(val, bits)							\
+	(sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
+
+static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
+{
+	unsigned int i;
+
+	for (i = 0; i < sz; i++)
+		INIT_HLIST_HEAD(&ht[i]);
+}
+
+/**
+ * hash_init - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ *
+ * Calculates the size of the hashtable from the given parameter, otherwise
+ * same as hash_init_size.
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.
+ */
+#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, node, key)						\
+	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
+
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the &struct hlist_node of the object to be checked
+ */
+static inline bool hash_hashed(struct hlist_node *node)
+{
+	return !hlist_unhashed(node);
+}
+
+static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
+{
+	unsigned int i;
+
+	for (i = 0; i < sz; i++)
+		if (!hlist_empty(&ht[i]))
+			return false;
+
+	return true;
+}
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.
+ */
+#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
+
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: &struct hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+	hlist_del_init(node);
+}
+
+/**
+ * hash_for_each - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bkt: integer to use as bucket loop cursor
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each(name, bkt, obj, member)				\
+	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
+			(bkt)++)\
+		hlist_for_each_entry(obj, &name[bkt], member)
+
+/**
+ * hash_for_each_safe - iterate over a hashtable safe against removal of
+ * hash entry
+ * @name: hashtable to iterate
+ * @bkt: integer to use as bucket loop cursor
+ * @tmp: a &struct used for temporary storage
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each_safe(name, bkt, tmp, obj, member)			\
+	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
+			(bkt)++)\
+		hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible(name, obj, member, key)			\
+	hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
+
+/**
+ * hash_for_each_possible_safe - iterate over all possible objects hashing to the
+ * same bucket safe against removals
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @tmp: a &struct used for temporary storage
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_safe(name, obj, tmp, member, key)	\
+	hlist_for_each_entry_safe(obj, tmp,\
+		&name[hash_min(key, HASH_BITS(name))], member)
+
+
+#endif
-- 
2.4.3

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web