Commit-ID: 5855fead9cc358adebd6bdeec202d040c623ae38
Gitweb: http://git.kernel.org/tip/5855fead9cc358adebd6bdeec202d040c623ae38
Author: Steven Rostedt <srostedt@xxxxxxxxxx>
AuthorDate: Fri, 16 Dec 2011 19:27:42 -0500
Committer: Steven Rostedt <rostedt@xxxxxxxxxxx>
CommitDate: Wed, 21 Dec 2011 07:20:50 -0500
ftrace: Use bsearch to find record ip
Now that each set of pages in the function list are sorted by
ip, we can use bsearch to find a record within each set of pages.
This speeds up the ftrace_location() function by magnitudes.
For archs (like x86) that need to add a breakpoint at every function
that will be converted from a nop to a callback and vice versa,
the breakpoint callback needs to know if the breakpoint was for
ftrace or not. It requires finding the breakpoint ip within the
records. Doing a linear search is extremely inefficient. It is
a must to be able to do a fast binary search to find these locations.
Signed-off-by: Steven Rostedt <rostedt@xxxxxxxxxxx>
---
kernel/trace/ftrace.c | 38 +++++++++++++++++++++++---------------
1 files changed, 23 insertions(+), 15 deletions(-)
diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 2d6f8bc..dcd3a81 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -22,6 +22,7 @@
#include <linux/hardirq.h>
#include <linux/kthread.h>
#include <linux/uaccess.h>
+#include <linux/bsearch.h>
#include <linux/module.h>
#include <linux/ftrace.h>
#include <linux/sysctl.h>
@@ -1300,6 +1301,19 @@ ftrace_ops_test(struct ftrace_ops *ops, unsigned long ip)
} \
}
+
+static int ftrace_cmp_recs(const void *a, const void *b)
+{
+ const struct dyn_ftrace *reca = a;
+ const struct dyn_ftrace *recb = b;
+
+ if (reca->ip > recb->ip)
+ return 1;
+ if (reca->ip < recb->ip)
+ return -1;
+ return 0;
+}
+
/**
* ftrace_location - return true if the ip giving is a traced location
* @ip: the instruction pointer to check
@@ -1313,11 +1327,17 @@ int ftrace_location(unsigned long ip)
{
struct ftrace_page *pg;
struct dyn_ftrace *rec;
+ struct dyn_ftrace key;
- do_for_each_ftrace_rec(pg, rec) {
- if (rec->ip == ip)
+ key.ip = ip;
+
+ for (pg = ftrace_pages_start; pg; pg = pg->next) {
+ rec = bsearch(&key, pg->records, pg->index,
+ sizeof(struct dyn_ftrace),
+ ftrace_cmp_recs);
+ if (rec)
return 1;
- } while_for_each_ftrace_rec();
+ }
return 0;
}
@@ -3587,18 +3607,6 @@ static void ftrace_swap_recs(void *a, void *b, int size)
*recb = t;
}
-static int ftrace_cmp_recs(const void *a, const void *b)
-{
- const struct dyn_ftrace *reca = a;
- const struct dyn_ftrace *recb = b;
-
- if (reca->ip > recb->ip)
- return 1;
- if (reca->ip < recb->ip)
- return -1;
- return 0;
-}
-
static int ftrace_process_locs(struct module *mod,
unsigned long *start,
unsigned long *end)
--
To unsubscribe from this list: send the line "unsubscribe linux-tip-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
|