lkml.org 
[lkml]   [2011]   [Jan]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[RFC][PATCH 09/12] tracing/filter: Check the created pred tree
    From: Steven Rostedt <srostedt@redhat.com>

    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>
    ---
    kernel/trace/trace_events_filter.c | 72 +++++++++++++++++++++++++++++++++++-
    1 files changed, 71 insertions(+), 1 deletions(-)

    diff --git a/kernel/trace/trace_events_filter.c b/kernel/trace/trace_events_filter.c
    index afe59ab..47e9430 100644
    --- a/kernel/trace/trace_events_filter.c
    +++ b/kernel/trace/trace_events_filter.c
    @@ -1359,6 +1359,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,
    @@ -1367,6 +1429,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;
    @@ -1443,7 +1506,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)) {
    @@ -1451,6 +1514,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;
    --
    1.7.2.3



    \
     
     \ /
      Last update: 2011-01-28 05:39    [W:0.024 / U:62.484 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site