[RFC PATCH v4 21/34] ftrace: sort ftrace entries earlier.

[Wang Nan <wangnan0@huawei.com>]

By extracting mcount sorting code and sort them earliler, futher patches
will be able to determine whether an address is on an ftrace entry or
not using bsearch().

ftrace_sort_mcount_area() will be called before, during and after
ftrace_init (when module insertion). Ensure it sort kernel mcount table
only once.

Signed-off-by: Wang Nan <wangnan0@huawei.com>
---
 include/linux/ftrace.h |  2 ++
 init/main.c            |  1 +
 kernel/trace/ftrace.c  | 38 ++++++++++++++++++++++++++++++++++++--
 3 files changed, 39 insertions(+), 2 deletions(-)

diff --git a/include/linux/ftrace.h b/include/linux/ftrace.h
index 1da6029..8db315a 100644
--- a/include/linux/ftrace.h
+++ b/include/linux/ftrace.h
@@ -701,8 +701,10 @@ static inline void __ftrace_enabled_restore(int enabled)
 
 #ifdef CONFIG_FTRACE_MCOUNT_RECORD
 extern void ftrace_init(void);
+extern void ftrace_init_early(void);
 #else
 static inline void ftrace_init(void) { }
+static inline void ftrace_init_early(void) { }
 #endif
 
 /*
diff --git a/init/main.c b/init/main.c
index 679d49e..6d269ac 100644
--- a/init/main.c
+++ b/init/main.c
@@ -518,6 +518,7 @@ asmlinkage __visible void __init start_kernel(void)
 	boot_cpu_init();
 	page_address_init();
 	pr_notice("%s", linux_banner);
+	ftrace_init_early();
 	setup_arch(&command_line);
 	init_kprobes_early();
 	mm_init_cpumask(&init_mm);
diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 6c6cbb1..fa3cdd3 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -112,6 +112,7 @@ ftrace_func_t ftrace_trace_function __read_mostly = ftrace_stub;
 ftrace_func_t ftrace_pid_function __read_mostly = ftrace_stub;
 static struct ftrace_ops global_ops;
 static struct ftrace_ops control_ops;
+static bool kernel_mcount_sorted = false;
 
 static void ftrace_ops_recurs_func(unsigned long ip, unsigned long parent_ip,
 				   struct ftrace_ops *op, struct pt_regs *regs);
@@ -4743,6 +4744,32 @@ static void ftrace_swap_ips(void *a, void *b, int size)
 	*ipb = t;
 }
 
+static void ftrace_sort_mcount_area(unsigned long *start, unsigned long *end)
+{
+	extern unsigned long __start_mcount_loc[];
+	extern unsigned long __stop_mcount_loc[];
+
+	unsigned long count;
+	bool is_kernel_mcount;
+
+	count = end - start;
+	if (!count)
+		return;
+
+	is_kernel_mcount =
+		(start == __start_mcount_loc) &&
+		(end == __stop_mcount_loc);
+
+	if (is_kernel_mcount && kernel_mcount_sorted)
+		return;
+
+	sort(start, count, sizeof(*start),
+		ftrace_cmp_ips, ftrace_swap_ips);
+
+	if (is_kernel_mcount)
+		kernel_mcount_sorted = true;
+}
+
 static int ftrace_process_locs(struct module *mod,
 			       unsigned long *start,
 			       unsigned long *end)
@@ -4761,8 +4788,7 @@ static int ftrace_process_locs(struct module *mod,
 	if (!count)
 		return 0;
 
-	sort(start, count, sizeof(*start),
-	     ftrace_cmp_ips, ftrace_swap_ips);
+	ftrace_sort_mcount_area(start, end);
 
 	start_pg = ftrace_allocate_pages(count);
 	if (!start_pg)
@@ -4965,6 +4991,14 @@ void __init ftrace_init(void)
 	ftrace_disabled = 1;
 }
 
+void __init ftrace_init_early(void)
+{
+	extern unsigned long __start_mcount_loc[];
+	extern unsigned long __stop_mcount_loc[];
+
+	ftrace_sort_mcount_area(__start_mcount_loc, __stop_mcount_loc);
+}
+
 /* Do nothing if arch does not support this */
 void __weak arch_ftrace_update_trampoline(struct ftrace_ops *ops)
 {
-- 
1.8.4