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>

diff --git a/kernel/trace/trace_events_filter.c b/kernel/trace/trace_events_filter.c
index 0a3e0502b50790e5e955c5f8b7a399aff74ba07e..91c9cdcb040b92447f10294c92523a1c4c17be51 100644 (file)
--- 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;