tracing/filter: Check the created pred tree

Since the filter walks a tree to determine if a match is made or not,
if the tree was incorrectly created, it could cause an infinite loop.

Add a check to walk the entire tree before assigning it as a filter
to make sure the tree is correct.

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

1 files changed, 71 insertions, 1 deletions

diff --git a/kernel/trace/trace_events_filter.c b/kernel/trace/trace_events_filter.c
index 0a3e0502b50..91c9cdcb040 100644
--- a/kernel/trace/trace_events_filter.c
+++ b/kernel/trace/trace_events_filter.c
@@ -1358,6 +1358,68 @@ static int count_preds(struct filter_parse_state *ps)
         return n_preds;
 }
 
+/*
+ * The tree is walked at filtering of an event. If the tree is not correctly
+ * built, it may cause an infinite loop. Check here that the tree does
+ * indeed terminate.
+ */
+static int check_pred_tree(struct event_filter *filter,
+                           struct filter_pred *root)
+{
+        struct filter_pred *preds;
+        struct filter_pred *pred;
+        enum move_type move = MOVE_DOWN;
+        int count = 0;
+        int done = 0;
+        int max;
+
+        /*
+         * The max that we can hit a node is three times.
+         * Once going down, once coming up from left, and
+         * once coming up from right. This is more than enough
+         * since leafs are only hit a single time.
+         */
+        max = 3 * filter->n_preds;
+
+        preds = filter->preds;
+        if  (!preds)
+                return -EINVAL;
+        pred = root;
+
+        do {
+                if (WARN_ON(count++ > max))
+                        return -EINVAL;
+
+                switch (move) {
+                case MOVE_DOWN:
+                        if (pred->left != FILTER_PRED_INVALID) {
+                                pred = &preds[pred->left];
+                                continue;
+                        }
+                        /* A leaf at the root is just a leaf in the tree */
+                        if (pred == root)
+                                break;
+                        pred = get_pred_parent(pred, preds,
+                                               pred->parent, &move);
+                        continue;
+                case MOVE_UP_FROM_LEFT:
+                        pred = &preds[pred->right];
+                        move = MOVE_DOWN;
+                        continue;
+                case MOVE_UP_FROM_RIGHT:
+                        if (pred == root)
+                                break;
+                        pred = get_pred_parent(pred, preds,
+                                               pred->parent, &move);
+                        continue;
+                }
+                done = 1;
+        } while (!done);
+
+        /* We are fine. */
+        return 0;
+}
+
 static int replace_preds(struct ftrace_event_call *call,
                          struct event_filter *filter,
                          struct filter_parse_state *ps,
@@ -1366,6 +1428,7 @@ static int replace_preds(struct ftrace_event_call *call,
 {
         char *operand1 = NULL, *operand2 = NULL;
         struct filter_pred *pred;
+        struct filter_pred *root;
         struct postfix_elt *elt;
         struct pred_stack stack = { }; /* init to NULL */
         int err;
@@ -1442,7 +1505,7 @@ add_pred:
                 if (!pred)
                         return -EINVAL;
                 /* This item is where we start from in matching */
-                filter->root = pred;
+                root = pred;
                 /* Make sure the stack is empty */
                 pred = __pop_pred_stack(&stack);
                 if (WARN_ON(pred)) {
@@ -1450,6 +1513,13 @@ add_pred:
                         filter->root = NULL;
                         goto fail;
                 }
+                err = check_pred_tree(filter, root);
+                if (err)
+                        goto fail;
+
+                /* We don't set root until we know it works */
+                barrier();
+                filter->root = root;
         }
 
         err = 0;