tracing/filter: Optimize filter by folding the tree

There are many cases that a filter will contain multiple ORs or
ANDs together near the leafs. Walking up and down the tree to get
to the next compare can be a waste.

If there are several ORs or ANDs together, fold them into a single
pred and allocate an array of the conditions that they check.
This will speed up the filter by linearly walking an array
and can still break out if a short circuit condition is met.

Cc: Tom Zanussi <tzanussi@gmail.com>
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

1 files changed, 11 insertions, 1 deletions

diff --git a/kernel/trace/trace.h b/kernel/trace/trace.h
index bba34a72c780..d754330934bb 100644
--- a/kernel/trace/trace.h
+++ b/kernel/trace/trace.h
@@ -678,6 +678,7 @@ struct event_subsystem {
 
 #define FILTER_PRED_INVALID     ((unsigned short)-1)
 #define FILTER_PRED_IS_RIGHT    (1 << 15)
+#define FILTER_PRED_FOLD        (1 << 15)
 
 struct filter_pred;
 struct regex;
@@ -704,7 +705,16 @@ struct filter_pred {
         filter_pred_fn_t        fn;
         u64                     val;
         struct regex            regex;
-        char                    *field_name;
+        /*
+         * Leaf nodes use field_name, ops is used by AND and OR
+         * nodes. The field_name is always freed when freeing a pred.
+         * We can overload field_name for ops and have it freed
+         * as well.
+         */
+        union {
+                char            *field_name;
+                unsigned short  *ops;
+        };
         int                     offset;
         int                     not;
         int                     op;