kernel/trace/trace_events_filter.c

   1 /*
   2  * trace_events_filter - generic event filtering
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  *
  18  * Copyright (C) 2009 Tom Zanussi <tzanussi@gmail.com>
  19  */
  20
  21 #include <linux/module.h>
  22 #include <linux/ctype.h>
  23 #include <linux/mutex.h>
  24 #include <linux/perf_event.h>
  25 #include <linux/slab.h>
  26
  27 #include "trace.h"
  28 #include "trace_output.h"
  29
  30 #define DEFAULT_SYS_FILTER_MESSAGE                                      \
  31         "### global filter ###\n"                                       \
  32         "# Use this to set filters for multiple events.\n"              \
  33         "# Only events with the given fields will be affected.\n"       \
  34         "# If no events are modified, an error message will be displayed here"
  35
  36 enum filter_op_ids
  37 {
  38         OP_OR,
  39         OP_AND,
  40         OP_GLOB,
  41         OP_NE,
  42         OP_EQ,
  43         OP_LT,
  44         OP_LE,
  45         OP_GT,
  46         OP_GE,
  47         OP_BAND,
  48         OP_NONE,
  49         OP_OPEN_PAREN,
  50 };
  51
  52 struct filter_op {
  53         int id;
  54         char *string;
  55         int precedence;
  56 };
  57
  58 /* Order must be the same as enum filter_op_ids above */
  59 static struct filter_op filter_ops[] = {
  60         { OP_OR,        "||",           1 },
  61         { OP_AND,       "&&",           2 },
  62         { OP_GLOB,      "~",            4 },
  63         { OP_NE,        "!=",           4 },
  64         { OP_EQ,        "==",           4 },
  65         { OP_LT,        "<",            5 },
  66         { OP_LE,        "<=",           5 },
  67         { OP_GT,        ">",            5 },
  68         { OP_GE,        ">=",           5 },
  69         { OP_BAND,      "&",            6 },
  70         { OP_NONE,      "OP_NONE",      0 },
  71         { OP_OPEN_PAREN, "(",           0 },
  72 };
  73
  74 enum {
  75         FILT_ERR_NONE,
  76         FILT_ERR_INVALID_OP,
  77         FILT_ERR_UNBALANCED_PAREN,
  78         FILT_ERR_TOO_MANY_OPERANDS,
  79         FILT_ERR_OPERAND_TOO_LONG,
  80         FILT_ERR_FIELD_NOT_FOUND,
  81         FILT_ERR_ILLEGAL_FIELD_OP,
  82         FILT_ERR_ILLEGAL_INTVAL,
  83         FILT_ERR_BAD_SUBSYS_FILTER,
  84         FILT_ERR_TOO_MANY_PREDS,
  85         FILT_ERR_MISSING_FIELD,
  86         FILT_ERR_INVALID_FILTER,
  87         FILT_ERR_IP_FIELD_ONLY,
  88 };
  89
  90 static char *err_text[] = {
  91         "No error",
  92         "Invalid operator",
  93         "Unbalanced parens",
  94         "Too many operands",
  95         "Operand too long",
  96         "Field not found",
  97         "Illegal operation for field type",
  98         "Illegal integer value",
  99         "Couldn't find or set field in one of a subsystem's events",
 100         "Too many terms in predicate expression",
 101         "Missing field name and/or value",
 102         "Meaningless filter expression",
 103         "Only 'ip' field is supported for function trace",
 104 };
 105
 106 struct opstack_op {
 107         int op;
 108         struct list_head list;
 109 };
 110
 111 struct postfix_elt {
 112         int op;
 113         char *operand;
 114         struct list_head list;
 115 };
 116
 117 struct filter_parse_state {
 118         struct filter_op *ops;
 119         struct list_head opstack;
 120         struct list_head postfix;
 121         int lasterr;
 122         int lasterr_pos;
 123
 124         struct {
 125                 char *string;
 126                 unsigned int cnt;
 127                 unsigned int tail;
 128         } infix;
 129
 130         struct {
 131                 char string[MAX_FILTER_STR_VAL];
 132                 int pos;
 133                 unsigned int tail;
 134         } operand;
 135 };
 136
 137 struct pred_stack {
 138         struct filter_pred      **preds;
 139         int                     index;
 140 };
 141
 142 #define DEFINE_COMPARISON_PRED(type)                                    \
 143 static int filter_pred_##type(struct filter_pred *pred, void *event)    \
 144 {                                                                       \
 145         type *addr = (type *)(event + pred->offset);                    \
 146         type val = (type)pred->val;                                     \
 147         int match = 0;                                                  \
 148                                                                         \
 149         switch (pred->op) {                                             \
 150         case OP_LT:                                                     \
 151                 match = (*addr < val);                                  \
 152                 break;                                                  \
 153         case OP_LE:                                                     \
 154                 match = (*addr <= val);                                 \
 155                 break;                                                  \
 156         case OP_GT:                                                     \
 157                 match = (*addr > val);                                  \
 158                 break;                                                  \
 159         case OP_GE:                                                     \
 160                 match = (*addr >= val);                                 \
 161                 break;                                                  \
 162         case OP_BAND:                                                   \
 163                 match = (*addr & val);                                  \
 164                 break;                                                  \
 165         default:                                                        \
 166                 break;                                                  \
 167         }                                                               \
 168                                                                         \
 169         return match;                                                   \
 170 }
 171
 172 #define DEFINE_EQUALITY_PRED(size)                                      \
 173 static int filter_pred_##size(struct filter_pred *pred, void *event)    \
 174 {                                                                       \
 175         u##size *addr = (u##size *)(event + pred->offset);              \
 176         u##size val = (u##size)pred->val;                               \
 177         int match;                                                      \
 178                                                                         \
 179         match = (val == *addr) ^ pred->not;                             \
 180                                                                         \
 181         return match;                                                   \
 182 }
 183
 184 DEFINE_COMPARISON_PRED(s64);
 185 DEFINE_COMPARISON_PRED(u64);
 186 DEFINE_COMPARISON_PRED(s32);
 187 DEFINE_COMPARISON_PRED(u32);
 188 DEFINE_COMPARISON_PRED(s16);
 189 DEFINE_COMPARISON_PRED(u16);
 190 DEFINE_COMPARISON_PRED(s8);
 191 DEFINE_COMPARISON_PRED(u8);
 192
 193 DEFINE_EQUALITY_PRED(64);
 194 DEFINE_EQUALITY_PRED(32);
 195 DEFINE_EQUALITY_PRED(16);
 196 DEFINE_EQUALITY_PRED(8);
 197
 198 /* Filter predicate for fixed sized arrays of characters */
 199 static int filter_pred_string(struct filter_pred *pred, void *event)
 200 {
 201         char *addr = (char *)(event + pred->offset);
 202         int cmp, match;
 203
 204         cmp = pred->regex.match(addr, &pred->regex, pred->regex.field_len);
 205
 206         match = cmp ^ pred->not;
 207
 208         return match;
 209 }
 210
 211 /* Filter predicate for char * pointers */
 212 static int filter_pred_pchar(struct filter_pred *pred, void *event)
 213 {
 214         char **addr = (char **)(event + pred->offset);
 215         int cmp, match;
 216         int len = strlen(*addr) + 1;    /* including tailing '\0' */
 217
 218         cmp = pred->regex.match(*addr, &pred->regex, len);
 219
 220         match = cmp ^ pred->not;
 221
 222         return match;
 223 }
 224
 225 /*
 226  * Filter predicate for dynamic sized arrays of characters.
 227  * These are implemented through a list of strings at the end
 228  * of the entry.
 229  * Also each of these strings have a field in the entry which
 230  * contains its offset from the beginning of the entry.
 231  * We have then first to get this field, dereference it
 232  * and add it to the address of the entry, and at last we have
 233  * the address of the string.
 234  */
 235 static int filter_pred_strloc(struct filter_pred *pred, void *event)
 236 {
 237         u32 str_item = *(u32 *)(event + pred->offset);
 238         int str_loc = str_item & 0xffff;
 239         int str_len = str_item >> 16;
 240         char *addr = (char *)(event + str_loc);
 241         int cmp, match;
 242
 243         cmp = pred->regex.match(addr, &pred->regex, str_len);
 244
 245         match = cmp ^ pred->not;
 246
 247         return match;
 248 }
 249
 250 static int filter_pred_none(struct filter_pred *pred, void *event)
 251 {
 252         return 0;
 253 }
 254
 255 /*
 256  * regex_match_foo - Basic regex callbacks
 257  *
 258  * @str: the string to be searched
 259  * @r:   the regex structure containing the pattern string
 260  * @len: the length of the string to be searched (including '\0')
 261  *
 262  * Note:
 263  * - @str might not be NULL-terminated if it's of type DYN_STRING
 264  *   or STATIC_STRING
 265  */
 266
 267 static int regex_match_full(char *str, struct regex *r, int len)
 268 {
 269         if (strncmp(str, r->pattern, len) == 0)
 270                 return 1;
 271         return 0;
 272 }
 273
 274 static int regex_match_front(char *str, struct regex *r, int len)
 275 {
 276         if (strncmp(str, r->pattern, r->len) == 0)
 277                 return 1;
 278         return 0;
 279 }
 280
 281 static int regex_match_middle(char *str, struct regex *r, int len)
 282 {
 283         if (strnstr(str, r->pattern, len))
 284                 return 1;
 285         return 0;
 286 }
 287
 288 static int regex_match_end(char *str, struct regex *r, int len)
 289 {
 290         int strlen = len - 1;
 291
 292         if (strlen >= r->len &&
 293             memcmp(str + strlen - r->len, r->pattern, r->len) == 0)
 294                 return 1;
 295         return 0;
 296 }
 297
 298 /**
 299  * filter_parse_regex - parse a basic regex
 300  * @buff:   the raw regex
 301  * @len:    length of the regex
 302  * @search: will point to the beginning of the string to compare
 303  * @not:    tell whether the match will have to be inverted
 304  *
 305  * This passes in a buffer containing a regex and this function will
 306  * set search to point to the search part of the buffer and
 307  * return the type of search it is (see enum above).
 308  * This does modify buff.
 309  *
 310  * Returns enum type.
 311  *  search returns the pointer to use for comparison.
 312  *  not returns 1 if buff started with a '!'
 313  *     0 otherwise.
 314  */
 315 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
 316 {
 317         int type = MATCH_FULL;
 318         int i;
 319
 320         if (buff[0] == '!') {
 321                 *not = 1;
 322                 buff++;
 323                 len--;
 324         } else
 325                 *not = 0;
 326
 327         *search = buff;
 328
 329         for (i = 0; i < len; i++) {
 330                 if (buff[i] == '*') {
 331                         if (!i) {
 332                                 *search = buff + 1;
 333                                 type = MATCH_END_ONLY;
 334                         } else {
 335                                 if (type == MATCH_END_ONLY)
 336                                         type = MATCH_MIDDLE_ONLY;
 337                                 else
 338                                         type = MATCH_FRONT_ONLY;
 339                                 buff[i] = 0;
 340                                 break;
 341                         }
 342                 }
 343         }
 344
 345         return type;
 346 }
 347
 348 static void filter_build_regex(struct filter_pred *pred)
 349 {
 350         struct regex *r = &pred->regex;
 351         char *search;
 352         enum regex_type type = MATCH_FULL;
 353         int not = 0;
 354
 355         if (pred->op == OP_GLOB) {
 356                 type = filter_parse_regex(r->pattern, r->len, &search, &not);
 357                 r->len = strlen(search);
 358                 memmove(r->pattern, search, r->len+1);
 359         }
 360
 361         switch (type) {
 362         case MATCH_FULL:
 363                 r->match = regex_match_full;
 364                 break;
 365         case MATCH_FRONT_ONLY:
 366                 r->match = regex_match_front;
 367                 break;
 368         case MATCH_MIDDLE_ONLY:
 369                 r->match = regex_match_middle;
 370                 break;
 371         case MATCH_END_ONLY:
 372                 r->match = regex_match_end;
 373                 break;
 374         }
 375
 376         pred->not ^= not;
 377 }
 378
 379 enum move_type {
 380         MOVE_DOWN,
 381         MOVE_UP_FROM_LEFT,
 382         MOVE_UP_FROM_RIGHT
 383 };
 384
 385 static struct filter_pred *
 386 get_pred_parent(struct filter_pred *pred, struct filter_pred *preds,
 387                 int index, enum move_type *move)
 388 {
 389         if (pred->parent & FILTER_PRED_IS_RIGHT)
 390                 *move = MOVE_UP_FROM_RIGHT;
 391         else
 392                 *move = MOVE_UP_FROM_LEFT;
 393         pred = &preds[pred->parent & ~FILTER_PRED_IS_RIGHT];
 394
 395         return pred;
 396 }
 397
 398 enum walk_return {
 399         WALK_PRED_ABORT,
 400         WALK_PRED_PARENT,
 401         WALK_PRED_DEFAULT,
 402 };
 403
 404 typedef int (*filter_pred_walkcb_t) (enum move_type move,
 405                                      struct filter_pred *pred,
 406                                      int *err, void *data);
 407
 408 static int walk_pred_tree(struct filter_pred *preds,
 409                           struct filter_pred *root,
 410                           filter_pred_walkcb_t cb, void *data)
 411 {
 412         struct filter_pred *pred = root;
 413         enum move_type move = MOVE_DOWN;
 414         int done = 0;
 415
 416         if  (!preds)
 417                 return -EINVAL;
 418
 419         do {
 420                 int err = 0, ret;
 421
 422                 ret = cb(move, pred, &err, data);
 423                 if (ret == WALK_PRED_ABORT)
 424                         return err;
 425                 if (ret == WALK_PRED_PARENT)
 426                         goto get_parent;
 427
 428                 switch (move) {
 429                 case MOVE_DOWN:
 430                         if (pred->left != FILTER_PRED_INVALID) {
 431                                 pred = &preds[pred->left];
 432                                 continue;
 433                         }
 434                         goto get_parent;
 435                 case MOVE_UP_FROM_LEFT:
 436                         pred = &preds[pred->right];
 437                         move = MOVE_DOWN;
 438                         continue;
 439                 case MOVE_UP_FROM_RIGHT:
 440  get_parent:
 441                         if (pred == root)
 442                                 break;
 443                         pred = get_pred_parent(pred, preds,
 444                                                pred->parent,
 445                                                &move);
 446                         continue;
 447                 }
 448                 done = 1;
 449         } while (!done);
 450
 451         /* We are fine. */
 452         return 0;
 453 }
 454
 455 /*
 456  * A series of AND or ORs where found together. Instead of
 457  * climbing up and down the tree branches, an array of the
 458  * ops were made in order of checks. We can just move across
 459  * the array and short circuit if needed.
 460  */
 461 static int process_ops(struct filter_pred *preds,
 462                        struct filter_pred *op, void *rec)
 463 {
 464         struct filter_pred *pred;
 465         int match = 0;
 466         int type;
 467         int i;
 468
 469         /*
 470          * Micro-optimization: We set type to true if op
 471          * is an OR and false otherwise (AND). Then we
 472          * just need to test if the match is equal to
 473          * the type, and if it is, we can short circuit the
 474          * rest of the checks:
 475          *
 476          * if ((match && op->op == OP_OR) ||
 477          *     (!match && op->op == OP_AND))
 478          *        return match;
 479          */
 480         type = op->op == OP_OR;
 481
 482         for (i = 0; i < op->val; i++) {
 483                 pred = &preds[op->ops[i]];
 484                 if (!WARN_ON_ONCE(!pred->fn))
 485                         match = pred->fn(pred, rec);
 486                 if (!!match == type)
 487                         return match;
 488         }
 489         return match;
 490 }
 491
 492 struct filter_match_preds_data {
 493         struct filter_pred *preds;
 494         int match;
 495         void *rec;
 496 };
 497
 498 static int filter_match_preds_cb(enum move_type move, struct filter_pred *pred,
 499                                  int *err, void *data)
 500 {
 501         struct filter_match_preds_data *d = data;
 502
 503         *err = 0;
 504         switch (move) {
 505         case MOVE_DOWN:
 506                 /* only AND and OR have children */
 507                 if (pred->left != FILTER_PRED_INVALID) {
 508                         /* If ops is set, then it was folded. */
 509                         if (!pred->ops)
 510                                 return WALK_PRED_DEFAULT;
 511                         /* We can treat folded ops as a leaf node */
 512                         d->match = process_ops(d->preds, pred, d->rec);
 513                 } else {
 514                         if (!WARN_ON_ONCE(!pred->fn))
 515                                 d->match = pred->fn(pred, d->rec);
 516                 }
 517
 518                 return WALK_PRED_PARENT;
 519         case MOVE_UP_FROM_LEFT:
 520                 /*
 521                  * Check for short circuits.
 522                  *
 523                  * Optimization: !!match == (pred->op == OP_OR)
 524                  *   is the same as:
 525                  * if ((match && pred->op == OP_OR) ||
 526                  *     (!match && pred->op == OP_AND))
 527                  */
 528                 if (!!d->match == (pred->op == OP_OR))
 529                         return WALK_PRED_PARENT;
 530                 break;
 531         case MOVE_UP_FROM_RIGHT:
 532                 break;
 533         }
 534
 535         return WALK_PRED_DEFAULT;
 536 }
 537
 538 /* return 1 if event matches, 0 otherwise (discard) */
 539 int filter_match_preds(struct event_filter *filter, void *rec)
 540 {
 541         struct filter_pred *preds;
 542         struct filter_pred *root;
 543         struct filter_match_preds_data data = {
 544                 /* match is currently meaningless */
 545                 .match = -1,
 546                 .rec   = rec,
 547         };
 548         int n_preds, ret;
 549
 550         /* no filter is considered a match */
 551         if (!filter)
 552                 return 1;
 553
 554         n_preds = filter->n_preds;
 555         if (!n_preds)
 556                 return 1;
 557
 558         /*
 559          * n_preds, root and filter->preds are protect with preemption disabled.
 560          */
 561         root = rcu_dereference_sched(filter->root);
 562         if (!root)
 563                 return 1;
 564
 565         data.preds = preds = rcu_dereference_sched(filter->preds);
 566         ret = walk_pred_tree(preds, root, filter_match_preds_cb, &data);
 567         WARN_ON(ret);
 568         return data.match;
 569 }
 570 EXPORT_SYMBOL_GPL(filter_match_preds);
 571
 572 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 573 {
 574         ps->lasterr = err;
 575         ps->lasterr_pos = pos;
 576 }
 577
 578 static void remove_filter_string(struct event_filter *filter)
 579 {
 580         if (!filter)
 581                 return;
 582
 583         kfree(filter->filter_string);
 584         filter->filter_string = NULL;
 585 }
 586
 587 static int replace_filter_string(struct event_filter *filter,
 588                                  char *filter_string)
 589 {
 590         kfree(filter->filter_string);
 591         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 592         if (!filter->filter_string)
 593                 return -ENOMEM;
 594
 595         return 0;
 596 }
 597
 598 static int append_filter_string(struct event_filter *filter,
 599                                 char *string)
 600 {
 601         int newlen;
 602         char *new_filter_string;
 603
 604         BUG_ON(!filter->filter_string);
 605         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 606         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 607         if (!new_filter_string)
 608                 return -ENOMEM;
 609
 610         strcpy(new_filter_string, filter->filter_string);
 611         strcat(new_filter_string, string);
 612         kfree(filter->filter_string);
 613         filter->filter_string = new_filter_string;
 614
 615         return 0;
 616 }
 617
 618 static void append_filter_err(struct filter_parse_state *ps,
 619                               struct event_filter *filter)
 620 {
 621         int pos = ps->lasterr_pos;
 622         char *buf, *pbuf;
 623
 624         buf = (char *)__get_free_page(GFP_TEMPORARY);
 625         if (!buf)
 626                 return;
 627
 628         append_filter_string(filter, "\n");
 629         memset(buf, ' ', PAGE_SIZE);
 630         if (pos > PAGE_SIZE - 128)
 631                 pos = 0;
 632         buf[pos] = '^';
 633         pbuf = &buf[pos] + 1;
 634
 635         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 636         append_filter_string(filter, buf);
 637         free_page((unsigned long) buf);
 638 }
 639
 640 /* caller must hold event_mutex */
 641 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 642 {
 643         struct event_filter *filter = call->filter;
 644
 645         if (filter && filter->filter_string)
 646                 trace_seq_printf(s, "%s\n", filter->filter_string);
 647         else
 648                 trace_seq_puts(s, "none\n");
 649 }
 650
 651 void print_subsystem_event_filter(struct event_subsystem *system,
 652                                   struct trace_seq *s)
 653 {
 654         struct event_filter *filter;
 655
 656         mutex_lock(&event_mutex);
 657         filter = system->filter;
 658         if (filter && filter->filter_string)
 659                 trace_seq_printf(s, "%s\n", filter->filter_string);
 660         else
 661                 trace_seq_puts(s, DEFAULT_SYS_FILTER_MESSAGE "\n");
 662         mutex_unlock(&event_mutex);
 663 }
 664
 665 static int __alloc_pred_stack(struct pred_stack *stack, int n_preds)
 666 {
 667         stack->preds = kcalloc(n_preds + 1, sizeof(*stack->preds), GFP_KERNEL);
 668         if (!stack->preds)
 669                 return -ENOMEM;
 670         stack->index = n_preds;
 671         return 0;
 672 }
 673
 674 static void __free_pred_stack(struct pred_stack *stack)
 675 {
 676         kfree(stack->preds);
 677         stack->index = 0;
 678 }
 679
 680 static int __push_pred_stack(struct pred_stack *stack,
 681                              struct filter_pred *pred)
 682 {
 683         int index = stack->index;
 684
 685         if (WARN_ON(index == 0))
 686                 return -ENOSPC;
 687
 688         stack->preds[--index] = pred;
 689         stack->index = index;
 690         return 0;
 691 }
 692
 693 static struct filter_pred *
 694 __pop_pred_stack(struct pred_stack *stack)
 695 {
 696         struct filter_pred *pred;
 697         int index = stack->index;
 698
 699         pred = stack->preds[index++];
 700         if (!pred)
 701                 return NULL;
 702
 703         stack->index = index;
 704         return pred;
 705 }
 706
 707 static int filter_set_pred(struct event_filter *filter,
 708                            int idx,
 709                            struct pred_stack *stack,
 710                            struct filter_pred *src)
 711 {
 712         struct filter_pred *dest = &filter->preds[idx];
 713         struct filter_pred *left;
 714         struct filter_pred *right;
 715
 716         *dest = *src;
 717         dest->index = idx;
 718
 719         if (dest->op == OP_OR || dest->op == OP_AND) {
 720                 right = __pop_pred_stack(stack);
 721                 left = __pop_pred_stack(stack);
 722                 if (!left || !right)
 723                         return -EINVAL;
 724                 /*
 725                  * If both children can be folded
 726                  * and they are the same op as this op or a leaf,
 727                  * then this op can be folded.
 728                  */
 729                 if (left->index & FILTER_PRED_FOLD &&
 730                     (left->op == dest->op ||
 731                      left->left == FILTER_PRED_INVALID) &&
 732                     right->index & FILTER_PRED_FOLD &&
 733                     (right->op == dest->op ||
 734                      right->left == FILTER_PRED_INVALID))
 735                         dest->index |= FILTER_PRED_FOLD;
 736
 737                 dest->left = left->index & ~FILTER_PRED_FOLD;
 738                 dest->right = right->index & ~FILTER_PRED_FOLD;
 739                 left->parent = dest->index & ~FILTER_PRED_FOLD;
 740                 right->parent = dest->index | FILTER_PRED_IS_RIGHT;
 741         } else {
 742                 /*
 743                  * Make dest->left invalid to be used as a quick
 744                  * way to know this is a leaf node.
 745                  */
 746                 dest->left = FILTER_PRED_INVALID;
 747
 748                 /* All leafs allow folding the parent ops. */
 749                 dest->index |= FILTER_PRED_FOLD;
 750         }
 751
 752         return __push_pred_stack(stack, dest);
 753 }
 754
 755 static void __free_preds(struct event_filter *filter)
 756 {
 757         int i;
 758
 759         if (filter->preds) {
 760                 for (i = 0; i < filter->n_preds; i++)
 761                         kfree(filter->preds[i].ops);
 762                 kfree(filter->preds);
 763                 filter->preds = NULL;
 764         }
 765         filter->a_preds = 0;
 766         filter->n_preds = 0;
 767 }
 768
 769 static void filter_disable(struct ftrace_event_call *call)
 770 {
 771         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 772 }
 773
 774 static void __free_filter(struct event_filter *filter)
 775 {
 776         if (!filter)
 777                 return;
 778
 779         __free_preds(filter);
 780         kfree(filter->filter_string);
 781         kfree(filter);
 782 }
 783
 784 /*
 785  * Called when destroying the ftrace_event_call.
 786  * The call is being freed, so we do not need to worry about
 787  * the call being currently used. This is for module code removing
 788  * the tracepoints from within it.
 789  */
 790 void destroy_preds(struct ftrace_event_call *call)
 791 {
 792         __free_filter(call->filter);
 793         call->filter = NULL;
 794 }
 795
 796 static struct event_filter *__alloc_filter(void)
 797 {
 798         struct event_filter *filter;
 799
 800         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 801         return filter;
 802 }
 803
 804 static int __alloc_preds(struct event_filter *filter, int n_preds)
 805 {
 806         struct filter_pred *pred;
 807         int i;
 808
 809         if (filter->preds)
 810                 __free_preds(filter);
 811
 812         filter->preds = kcalloc(n_preds, sizeof(*filter->preds), GFP_KERNEL);
 813
 814         if (!filter->preds)
 815                 return -ENOMEM;
 816
 817         filter->a_preds = n_preds;
 818         filter->n_preds = 0;
 819
 820         for (i = 0; i < n_preds; i++) {
 821                 pred = &filter->preds[i];
 822                 pred->fn = filter_pred_none;
 823         }
 824
 825         return 0;
 826 }
 827
 828 static void filter_free_subsystem_preds(struct event_subsystem *system)
 829 {
 830         struct ftrace_event_call *call;
 831
 832         list_for_each_entry(call, &ftrace_events, list) {
 833                 if (strcmp(call->class->system, system->name) != 0)
 834                         continue;
 835
 836                 filter_disable(call);
 837                 remove_filter_string(call->filter);
 838         }
 839 }
 840
 841 static void filter_free_subsystem_filters(struct event_subsystem *system)
 842 {
 843         struct ftrace_event_call *call;
 844
 845         list_for_each_entry(call, &ftrace_events, list) {
 846                 if (strcmp(call->class->system, system->name) != 0)
 847                         continue;
 848                 __free_filter(call->filter);
 849                 call->filter = NULL;
 850         }
 851 }
 852
 853 static int filter_add_pred(struct filter_parse_state *ps,
 854                            struct event_filter *filter,
 855                            struct filter_pred *pred,
 856                            struct pred_stack *stack)
 857 {
 858         int err;
 859
 860         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 861                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 862                 return -ENOSPC;
 863         }
 864
 865         err = filter_set_pred(filter, filter->n_preds, stack, pred);
 866         if (err)
 867                 return err;
 868
 869         filter->n_preds++;
 870
 871         return 0;
 872 }
 873
 874 int filter_assign_type(const char *type)
 875 {
 876         if (strstr(type, "__data_loc") && strstr(type, "char"))
 877                 return FILTER_DYN_STRING;
 878
 879         if (strchr(type, '[') && strstr(type, "char"))
 880                 return FILTER_STATIC_STRING;
 881
 882         return FILTER_OTHER;
 883 }
 884
 885 static bool is_function_field(struct ftrace_event_field *field)
 886 {
 887         return field->filter_type == FILTER_TRACE_FN;
 888 }
 889
 890 static bool is_string_field(struct ftrace_event_field *field)
 891 {
 892         return field->filter_type == FILTER_DYN_STRING ||
 893                field->filter_type == FILTER_STATIC_STRING ||
 894                field->filter_type == FILTER_PTR_STRING;
 895 }
 896
 897 static int is_legal_op(struct ftrace_event_field *field, int op)
 898 {
 899         if (is_string_field(field) &&
 900             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 901                 return 0;
 902         if (!is_string_field(field) && op == OP_GLOB)
 903                 return 0;
 904
 905         return 1;
 906 }
 907
 908 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 909                                              int field_is_signed)
 910 {
 911         filter_pred_fn_t fn = NULL;
 912
 913         switch (field_size) {
 914         case 8:
 915                 if (op == OP_EQ || op == OP_NE)
 916                         fn = filter_pred_64;
 917                 else if (field_is_signed)
 918                         fn = filter_pred_s64;
 919                 else
 920                         fn = filter_pred_u64;
 921                 break;
 922         case 4:
 923                 if (op == OP_EQ || op == OP_NE)
 924                         fn = filter_pred_32;
 925                 else if (field_is_signed)
 926                         fn = filter_pred_s32;
 927                 else
 928                         fn = filter_pred_u32;
 929                 break;
 930         case 2:
 931                 if (op == OP_EQ || op == OP_NE)
 932                         fn = filter_pred_16;
 933                 else if (field_is_signed)
 934                         fn = filter_pred_s16;
 935                 else
 936                         fn = filter_pred_u16;
 937                 break;
 938         case 1:
 939                 if (op == OP_EQ || op == OP_NE)
 940                         fn = filter_pred_8;
 941                 else if (field_is_signed)
 942                         fn = filter_pred_s8;
 943                 else
 944                         fn = filter_pred_u8;
 945                 break;
 946         }
 947
 948         return fn;
 949 }
 950
 951 static int init_pred(struct filter_parse_state *ps,
 952                      struct ftrace_event_field *field,
 953                      struct filter_pred *pred)
 954
 955 {
 956         filter_pred_fn_t fn = filter_pred_none;
 957         unsigned long long val;
 958         int ret;
 959
 960         pred->offset = field->offset;
 961
 962         if (!is_legal_op(field, pred->op)) {
 963                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 964                 return -EINVAL;
 965         }
 966
 967         if (is_string_field(field)) {
 968                 filter_build_regex(pred);
 969
 970                 if (field->filter_type == FILTER_STATIC_STRING) {
 971                         fn = filter_pred_string;
 972                         pred->regex.field_len = field->size;
 973                 } else if (field->filter_type == FILTER_DYN_STRING)
 974                         fn = filter_pred_strloc;
 975                 else
 976                         fn = filter_pred_pchar;
 977         } else if (is_function_field(field)) {
 978                 if (strcmp(field->name, "ip")) {
 979                         parse_error(ps, FILT_ERR_IP_FIELD_ONLY, 0);
 980                         return -EINVAL;
 981                 }
 982         } else {
 983                 if (field->is_signed)
 984                         ret = kstrtoll(pred->regex.pattern, 0, &val);
 985                 else
 986                         ret = kstrtoull(pred->regex.pattern, 0, &val);
 987                 if (ret) {
 988                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 989                         return -EINVAL;
 990                 }
 991                 pred->val = val;
 992
 993                 fn = select_comparison_fn(pred->op, field->size,
 994                                           field->is_signed);
 995                 if (!fn) {
 996                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 997                         return -EINVAL;
 998                 }
 999         }
1000
1001         if (pred->op == OP_NE)
1002                 pred->not = 1;
1003
1004         pred->fn = fn;
1005         return 0;
1006 }
1007
1008 static void parse_init(struct filter_parse_state *ps,
1009                        struct filter_op *ops,
1010                        char *infix_string)
1011 {
1012         memset(ps, '\0', sizeof(*ps));
1013
1014         ps->infix.string = infix_string;
1015         ps->infix.cnt = strlen(infix_string);
1016         ps->ops = ops;
1017
1018         INIT_LIST_HEAD(&ps->opstack);
1019         INIT_LIST_HEAD(&ps->postfix);
1020 }
1021
1022 static char infix_next(struct filter_parse_state *ps)
1023 {
1024         ps->infix.cnt--;
1025
1026         return ps->infix.string[ps->infix.tail++];
1027 }
1028
1029 static char infix_peek(struct filter_parse_state *ps)
1030 {
1031         if (ps->infix.tail == strlen(ps->infix.string))
1032                 return 0;
1033
1034         return ps->infix.string[ps->infix.tail];
1035 }
1036
1037 static void infix_advance(struct filter_parse_state *ps)
1038 {
1039         ps->infix.cnt--;
1040         ps->infix.tail++;
1041 }
1042
1043 static inline int is_precedence_lower(struct filter_parse_state *ps,
1044                                       int a, int b)
1045 {
1046         return ps->ops[a].precedence < ps->ops[b].precedence;
1047 }
1048
1049 static inline int is_op_char(struct filter_parse_state *ps, char c)
1050 {
1051         int i;
1052
1053         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1054                 if (ps->ops[i].string[0] == c)
1055                         return 1;
1056         }
1057
1058         return 0;
1059 }
1060
1061 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1062 {
1063         char nextc = infix_peek(ps);
1064         char opstr[3];
1065         int i;
1066
1067         opstr[0] = firstc;
1068         opstr[1] = nextc;
1069         opstr[2] = '\0';
1070
1071         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1072                 if (!strcmp(opstr, ps->ops[i].string)) {
1073                         infix_advance(ps);
1074                         return ps->ops[i].id;
1075                 }
1076         }
1077
1078         opstr[1] = '\0';
1079
1080         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1081                 if (!strcmp(opstr, ps->ops[i].string))
1082                         return ps->ops[i].id;
1083         }
1084
1085         return OP_NONE;
1086 }
1087
1088 static inline void clear_operand_string(struct filter_parse_state *ps)
1089 {
1090         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1091         ps->operand.tail = 0;
1092 }
1093
1094 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1095 {
1096         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1097                 return -EINVAL;
1098
1099         ps->operand.string[ps->operand.tail++] = c;
1100
1101         return 0;
1102 }
1103
1104 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1105 {
1106         struct opstack_op *opstack_op;
1107
1108         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1109         if (!opstack_op)
1110                 return -ENOMEM;
1111
1112         opstack_op->op = op;
1113         list_add(&opstack_op->list, &ps->opstack);
1114
1115         return 0;
1116 }
1117
1118 static int filter_opstack_empty(struct filter_parse_state *ps)
1119 {
1120         return list_empty(&ps->opstack);
1121 }
1122
1123 static int filter_opstack_top(struct filter_parse_state *ps)
1124 {
1125         struct opstack_op *opstack_op;
1126
1127         if (filter_opstack_empty(ps))
1128                 return OP_NONE;
1129
1130         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1131
1132         return opstack_op->op;
1133 }
1134
1135 static int filter_opstack_pop(struct filter_parse_state *ps)
1136 {
1137         struct opstack_op *opstack_op;
1138         int op;
1139
1140         if (filter_opstack_empty(ps))
1141                 return OP_NONE;
1142
1143         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1144         op = opstack_op->op;
1145         list_del(&opstack_op->list);
1146
1147         kfree(opstack_op);
1148
1149         return op;
1150 }
1151
1152 static void filter_opstack_clear(struct filter_parse_state *ps)
1153 {
1154         while (!filter_opstack_empty(ps))
1155                 filter_opstack_pop(ps);
1156 }
1157
1158 static char *curr_operand(struct filter_parse_state *ps)
1159 {
1160         return ps->operand.string;
1161 }
1162
1163 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1164 {
1165         struct postfix_elt *elt;
1166
1167         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1168         if (!elt)
1169                 return -ENOMEM;
1170
1171         elt->op = OP_NONE;
1172         elt->operand = kstrdup(operand, GFP_KERNEL);
1173         if (!elt->operand) {
1174                 kfree(elt);
1175                 return -ENOMEM;
1176         }
1177
1178         list_add_tail(&elt->list, &ps->postfix);
1179
1180         return 0;
1181 }
1182
1183 static int postfix_append_op(struct filter_parse_state *ps, int op)
1184 {
1185         struct postfix_elt *elt;
1186
1187         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1188         if (!elt)
1189                 return -ENOMEM;
1190
1191         elt->op = op;
1192         elt->operand = NULL;
1193
1194         list_add_tail(&elt->list, &ps->postfix);
1195
1196         return 0;
1197 }
1198
1199 static void postfix_clear(struct filter_parse_state *ps)
1200 {
1201         struct postfix_elt *elt;
1202
1203         while (!list_empty(&ps->postfix)) {
1204                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1205                 list_del(&elt->list);
1206                 kfree(elt->operand);
1207                 kfree(elt);
1208         }
1209 }
1210
1211 static int filter_parse(struct filter_parse_state *ps)
1212 {
1213         int in_string = 0;
1214         int op, top_op;
1215         char ch;
1216
1217         while ((ch = infix_next(ps))) {
1218                 if (ch == '"') {
1219                         in_string ^= 1;
1220                         continue;
1221                 }
1222
1223                 if (in_string)
1224                         goto parse_operand;
1225
1226                 if (isspace(ch))
1227                         continue;
1228
1229                 if (is_op_char(ps, ch)) {
1230                         op = infix_get_op(ps, ch);
1231                         if (op == OP_NONE) {
1232                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1233                                 return -EINVAL;
1234                         }
1235
1236                         if (strlen(curr_operand(ps))) {
1237                                 postfix_append_operand(ps, curr_operand(ps));
1238                                 clear_operand_string(ps);
1239                         }
1240
1241                         while (!filter_opstack_empty(ps)) {
1242                                 top_op = filter_opstack_top(ps);
1243                                 if (!is_precedence_lower(ps, top_op, op)) {
1244                                         top_op = filter_opstack_pop(ps);
1245                                         postfix_append_op(ps, top_op);
1246                                         continue;
1247                                 }
1248                                 break;
1249                         }
1250
1251                         filter_opstack_push(ps, op);
1252                         continue;
1253                 }
1254
1255                 if (ch == '(') {
1256                         filter_opstack_push(ps, OP_OPEN_PAREN);
1257                         continue;
1258                 }
1259
1260                 if (ch == ')') {
1261                         if (strlen(curr_operand(ps))) {
1262                                 postfix_append_operand(ps, curr_operand(ps));
1263                                 clear_operand_string(ps);
1264                         }
1265
1266                         top_op = filter_opstack_pop(ps);
1267                         while (top_op != OP_NONE) {
1268                                 if (top_op == OP_OPEN_PAREN)
1269                                         break;
1270                                 postfix_append_op(ps, top_op);
1271                                 top_op = filter_opstack_pop(ps);
1272                         }
1273                         if (top_op == OP_NONE) {
1274                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1275                                 return -EINVAL;
1276                         }
1277                         continue;
1278                 }
1279 parse_operand:
1280                 if (append_operand_char(ps, ch)) {
1281                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1282                         return -EINVAL;
1283                 }
1284         }
1285
1286         if (strlen(curr_operand(ps)))
1287                 postfix_append_operand(ps, curr_operand(ps));
1288
1289         while (!filter_opstack_empty(ps)) {
1290                 top_op = filter_opstack_pop(ps);
1291                 if (top_op == OP_NONE)
1292                         break;
1293                 if (top_op == OP_OPEN_PAREN) {
1294                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1295                         return -EINVAL;
1296                 }
1297                 postfix_append_op(ps, top_op);
1298         }
1299
1300         return 0;
1301 }
1302
1303 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1304                                        struct ftrace_event_call *call,
1305                                        int op, char *operand1, char *operand2)
1306 {
1307         struct ftrace_event_field *field;
1308         static struct filter_pred pred;
1309
1310         memset(&pred, 0, sizeof(pred));
1311         pred.op = op;
1312
1313         if (op == OP_AND || op == OP_OR)
1314                 return &pred;
1315
1316         if (!operand1 || !operand2) {
1317                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1318                 return NULL;
1319         }
1320
1321         field = trace_find_event_field(call, operand1);
1322         if (!field) {
1323                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1324                 return NULL;
1325         }
1326
1327         strcpy(pred.regex.pattern, operand2);
1328         pred.regex.len = strlen(pred.regex.pattern);
1329         pred.field = field;
1330         return init_pred(ps, field, &pred) ? NULL : &pred;
1331 }
1332
1333 static int check_preds(struct filter_parse_state *ps)
1334 {
1335         int n_normal_preds = 0, n_logical_preds = 0;
1336         struct postfix_elt *elt;
1337
1338         list_for_each_entry(elt, &ps->postfix, list) {
1339                 if (elt->op == OP_NONE)
1340                         continue;
1341
1342                 if (elt->op == OP_AND || elt->op == OP_OR) {
1343                         n_logical_preds++;
1344                         continue;
1345                 }
1346                 n_normal_preds++;
1347         }
1348
1349         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1350                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1351                 return -EINVAL;
1352         }
1353
1354         return 0;
1355 }
1356
1357 static int count_preds(struct filter_parse_state *ps)
1358 {
1359         struct postfix_elt *elt;
1360         int n_preds = 0;
1361
1362         list_for_each_entry(elt, &ps->postfix, list) {
1363                 if (elt->op == OP_NONE)
1364                         continue;
1365                 n_preds++;
1366         }
1367
1368         return n_preds;
1369 }
1370
1371 struct check_pred_data {
1372         int count;
1373         int max;
1374 };
1375
1376 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1377                               int *err, void *data)
1378 {
1379         struct check_pred_data *d = data;
1380
1381         if (WARN_ON(d->count++ > d->max)) {
1382                 *err = -EINVAL;
1383                 return WALK_PRED_ABORT;
1384         }
1385         return WALK_PRED_DEFAULT;
1386 }
1387
1388 /*
1389  * The tree is walked at filtering of an event. If the tree is not correctly
1390  * built, it may cause an infinite loop. Check here that the tree does
1391  * indeed terminate.
1392  */
1393 static int check_pred_tree(struct event_filter *filter,
1394                            struct filter_pred *root)
1395 {
1396         struct check_pred_data data = {
1397                 /*
1398                  * The max that we can hit a node is three times.
1399                  * Once going down, once coming up from left, and
1400                  * once coming up from right. This is more than enough
1401                  * since leafs are only hit a single time.
1402                  */
1403                 .max   = 3 * filter->n_preds,
1404                 .count = 0,
1405         };
1406
1407         return walk_pred_tree(filter->preds, root,
1408                               check_pred_tree_cb, &data);
1409 }
1410
1411 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1412                           int *err, void *data)
1413 {
1414         int *count = data;
1415
1416         if ((move == MOVE_DOWN) &&
1417             (pred->left == FILTER_PRED_INVALID))
1418                 (*count)++;
1419
1420         return WALK_PRED_DEFAULT;
1421 }
1422
1423 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1424 {
1425         int count = 0, ret;
1426
1427         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1428         WARN_ON(ret);
1429         return count;
1430 }
1431
1432 struct fold_pred_data {
1433         struct filter_pred *root;
1434         int count;
1435         int children;
1436 };
1437
1438 static int fold_pred_cb(enum move_type move, struct filter_pred *pred,
1439                         int *err, void *data)
1440 {
1441         struct fold_pred_data *d = data;
1442         struct filter_pred *root = d->root;
1443
1444         if (move != MOVE_DOWN)
1445                 return WALK_PRED_DEFAULT;
1446         if (pred->left != FILTER_PRED_INVALID)
1447                 return WALK_PRED_DEFAULT;
1448
1449         if (WARN_ON(d->count == d->children)) {
1450                 *err = -EINVAL;
1451                 return WALK_PRED_ABORT;
1452         }
1453
1454         pred->index &= ~FILTER_PRED_FOLD;
1455         root->ops[d->count++] = pred->index;
1456         return WALK_PRED_DEFAULT;
1457 }
1458
1459 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1460 {
1461         struct fold_pred_data data = {
1462                 .root  = root,
1463                 .count = 0,
1464         };
1465         int children;
1466
1467         /* No need to keep the fold flag */
1468         root->index &= ~FILTER_PRED_FOLD;
1469
1470         /* If the root is a leaf then do nothing */
1471         if (root->left == FILTER_PRED_INVALID)
1472                 return 0;
1473
1474         /* count the children */
1475         children = count_leafs(preds, &preds[root->left]);
1476         children += count_leafs(preds, &preds[root->right]);
1477
1478         root->ops = kcalloc(children, sizeof(*root->ops), GFP_KERNEL);
1479         if (!root->ops)
1480                 return -ENOMEM;
1481
1482         root->val = children;
1483         data.children = children;
1484         return walk_pred_tree(preds, root, fold_pred_cb, &data);
1485 }
1486
1487 static int fold_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1488                              int *err, void *data)
1489 {
1490         struct filter_pred *preds = data;
1491
1492         if (move != MOVE_DOWN)
1493                 return WALK_PRED_DEFAULT;
1494         if (!(pred->index & FILTER_PRED_FOLD))
1495                 return WALK_PRED_DEFAULT;
1496
1497         *err = fold_pred(preds, pred);
1498         if (*err)
1499                 return WALK_PRED_ABORT;
1500
1501         /* eveyrhing below is folded, continue with parent */
1502         return WALK_PRED_PARENT;
1503 }
1504
1505 /*
1506  * To optimize the processing of the ops, if we have several "ors" or
1507  * "ands" together, we can put them in an array and process them all
1508  * together speeding up the filter logic.
1509  */
1510 static int fold_pred_tree(struct event_filter *filter,
1511                            struct filter_pred *root)
1512 {
1513         return walk_pred_tree(filter->preds, root, fold_pred_tree_cb,
1514                               filter->preds);
1515 }
1516
1517 static int replace_preds(struct ftrace_event_call *call,
1518                          struct event_filter *filter,
1519                          struct filter_parse_state *ps,
1520                          char *filter_string,
1521                          bool dry_run)
1522 {
1523         char *operand1 = NULL, *operand2 = NULL;
1524         struct filter_pred *pred;
1525         struct filter_pred *root;
1526         struct postfix_elt *elt;
1527         struct pred_stack stack = { }; /* init to NULL */
1528         int err;
1529         int n_preds = 0;
1530
1531         n_preds = count_preds(ps);
1532         if (n_preds >= MAX_FILTER_PRED) {
1533                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1534                 return -ENOSPC;
1535         }
1536
1537         err = check_preds(ps);
1538         if (err)
1539                 return err;
1540
1541         if (!dry_run) {
1542                 err = __alloc_pred_stack(&stack, n_preds);
1543                 if (err)
1544                         return err;
1545                 err = __alloc_preds(filter, n_preds);
1546                 if (err)
1547                         goto fail;
1548         }
1549
1550         n_preds = 0;
1551         list_for_each_entry(elt, &ps->postfix, list) {
1552                 if (elt->op == OP_NONE) {
1553                         if (!operand1)
1554                                 operand1 = elt->operand;
1555                         else if (!operand2)
1556                                 operand2 = elt->operand;
1557                         else {
1558                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1559                                 err = -EINVAL;
1560                                 goto fail;
1561                         }
1562                         continue;
1563                 }
1564
1565                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1566                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1567                         err = -ENOSPC;
1568                         goto fail;
1569                 }
1570
1571                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1572                 if (!pred) {
1573                         err = -EINVAL;
1574                         goto fail;
1575                 }
1576
1577                 if (!dry_run) {
1578                         err = filter_add_pred(ps, filter, pred, &stack);
1579                         if (err)
1580                                 goto fail;
1581                 }
1582
1583                 operand1 = operand2 = NULL;
1584         }
1585
1586         if (!dry_run) {
1587                 /* We should have one item left on the stack */
1588                 pred = __pop_pred_stack(&stack);
1589                 if (!pred)
1590                         return -EINVAL;
1591                 /* This item is where we start from in matching */
1592                 root = pred;
1593                 /* Make sure the stack is empty */
1594                 pred = __pop_pred_stack(&stack);
1595                 if (WARN_ON(pred)) {
1596                         err = -EINVAL;
1597                         filter->root = NULL;
1598                         goto fail;
1599                 }
1600                 err = check_pred_tree(filter, root);
1601                 if (err)
1602                         goto fail;
1603
1604                 /* Optimize the tree */
1605                 err = fold_pred_tree(filter, root);
1606                 if (err)
1607                         goto fail;
1608
1609                 /* We don't set root until we know it works */
1610                 barrier();
1611                 filter->root = root;
1612         }
1613
1614         err = 0;
1615 fail:
1616         __free_pred_stack(&stack);
1617         return err;
1618 }
1619
1620 struct filter_list {
1621         struct list_head        list;
1622         struct event_filter     *filter;
1623 };
1624
1625 static int replace_system_preds(struct event_subsystem *system,
1626                                 struct filter_parse_state *ps,
1627                                 char *filter_string)
1628 {
1629         struct ftrace_event_call *call;
1630         struct filter_list *filter_item;
1631         struct filter_list *tmp;
1632         LIST_HEAD(filter_list);
1633         bool fail = true;
1634         int err;
1635
1636         list_for_each_entry(call, &ftrace_events, list) {
1637
1638                 if (strcmp(call->class->system, system->name) != 0)
1639                         continue;
1640
1641                 /*
1642                  * Try to see if the filter can be applied
1643                  *  (filter arg is ignored on dry_run)
1644                  */
1645                 err = replace_preds(call, NULL, ps, filter_string, true);
1646                 if (err)
1647                         call->flags |= TRACE_EVENT_FL_NO_SET_FILTER;
1648                 else
1649                         call->flags &= ~TRACE_EVENT_FL_NO_SET_FILTER;
1650         }
1651
1652         list_for_each_entry(call, &ftrace_events, list) {
1653                 struct event_filter *filter;
1654
1655                 if (strcmp(call->class->system, system->name) != 0)
1656                         continue;
1657
1658                 if (call->flags & TRACE_EVENT_FL_NO_SET_FILTER)
1659                         continue;
1660
1661                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1662                 if (!filter_item)
1663                         goto fail_mem;
1664
1665                 list_add_tail(&filter_item->list, &filter_list);
1666
1667                 filter_item->filter = __alloc_filter();
1668                 if (!filter_item->filter)
1669                         goto fail_mem;
1670                 filter = filter_item->filter;
1671
1672                 /* Can only fail on no memory */
1673                 err = replace_filter_string(filter, filter_string);
1674                 if (err)
1675                         goto fail_mem;
1676
1677                 err = replace_preds(call, filter, ps, filter_string, false);
1678                 if (err) {
1679                         filter_disable(call);
1680                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1681                         append_filter_err(ps, filter);
1682                 } else
1683                         call->flags |= TRACE_EVENT_FL_FILTERED;
1684                 /*
1685                  * Regardless of if this returned an error, we still
1686                  * replace the filter for the call.
1687                  */
1688                 filter = call->filter;
1689                 rcu_assign_pointer(call->filter, filter_item->filter);
1690                 filter_item->filter = filter;
1691
1692                 fail = false;
1693         }
1694
1695         if (fail)
1696                 goto fail;
1697
1698         /*
1699          * The calls can still be using the old filters.
1700          * Do a synchronize_sched() to ensure all calls are
1701          * done with them before we free them.
1702          */
1703         synchronize_sched();
1704         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1705                 __free_filter(filter_item->filter);
1706                 list_del(&filter_item->list);
1707                 kfree(filter_item);
1708         }
1709         return 0;
1710  fail:
1711         /* No call succeeded */
1712         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1713                 list_del(&filter_item->list);
1714                 kfree(filter_item);
1715         }
1716         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1717         return -EINVAL;
1718  fail_mem:
1719         /* If any call succeeded, we still need to sync */
1720         if (!fail)
1721                 synchronize_sched();
1722         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1723                 __free_filter(filter_item->filter);
1724                 list_del(&filter_item->list);
1725                 kfree(filter_item);
1726         }
1727         return -ENOMEM;
1728 }
1729
1730 static int create_filter_start(char *filter_str, bool set_str,
1731                                struct filter_parse_state **psp,
1732                                struct event_filter **filterp)
1733 {
1734         struct event_filter *filter;
1735         struct filter_parse_state *ps = NULL;
1736         int err = 0;
1737
1738         WARN_ON_ONCE(*psp || *filterp);
1739
1740         /* allocate everything, and if any fails, free all and fail */
1741         filter = __alloc_filter();
1742         if (filter && set_str)
1743                 err = replace_filter_string(filter, filter_str);
1744
1745         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1746
1747         if (!filter || !ps || err) {
1748                 kfree(ps);
1749                 __free_filter(filter);
1750                 return -ENOMEM;
1751         }
1752
1753         /* we're committed to creating a new filter */
1754         *filterp = filter;
1755         *psp = ps;
1756
1757         parse_init(ps, filter_ops, filter_str);
1758         err = filter_parse(ps);
1759         if (err && set_str)
1760                 append_filter_err(ps, filter);
1761         return err;
1762 }
1763
1764 static void create_filter_finish(struct filter_parse_state *ps)
1765 {
1766         if (ps) {
1767                 filter_opstack_clear(ps);
1768                 postfix_clear(ps);
1769                 kfree(ps);
1770         }
1771 }
1772
1773 /**
1774  * create_filter - create a filter for a ftrace_event_call
1775  * @call: ftrace_event_call to create a filter for
1776  * @filter_str: filter string
1777  * @set_str: remember @filter_str and enable detailed error in filter
1778  * @filterp: out param for created filter (always updated on return)
1779  *
1780  * Creates a filter for @call with @filter_str.  If @set_str is %true,
1781  * @filter_str is copied and recorded in the new filter.
1782  *
1783  * On success, returns 0 and *@filterp points to the new filter.  On
1784  * failure, returns -errno and *@filterp may point to %NULL or to a new
1785  * filter.  In the latter case, the returned filter contains error
1786  * information if @set_str is %true and the caller is responsible for
1787  * freeing it.
1788  */
1789 static int create_filter(struct ftrace_event_call *call,
1790                          char *filter_str, bool set_str,
1791                          struct event_filter **filterp)
1792 {
1793         struct event_filter *filter = NULL;
1794         struct filter_parse_state *ps = NULL;
1795         int err;
1796
1797         err = create_filter_start(filter_str, set_str, &ps, &filter);
1798         if (!err) {
1799                 err = replace_preds(call, filter, ps, filter_str, false);
1800                 if (err && set_str)
1801                         append_filter_err(ps, filter);
1802         }
1803         create_filter_finish(ps);
1804
1805         *filterp = filter;
1806         return err;
1807 }
1808
1809 /**
1810  * create_system_filter - create a filter for an event_subsystem
1811  * @system: event_subsystem to create a filter for
1812  * @filter_str: filter string
1813  * @filterp: out param for created filter (always updated on return)
1814  *
1815  * Identical to create_filter() except that it creates a subsystem filter
1816  * and always remembers @filter_str.
1817  */
1818 static int create_system_filter(struct event_subsystem *system,
1819                                 char *filter_str, struct event_filter **filterp)
1820 {
1821         struct event_filter *filter = NULL;
1822         struct filter_parse_state *ps = NULL;
1823         int err;
1824
1825         err = create_filter_start(filter_str, true, &ps, &filter);
1826         if (!err) {
1827                 err = replace_system_preds(system, ps, filter_str);
1828                 if (!err) {
1829                         /* System filters just show a default message */
1830                         kfree(filter->filter_string);
1831                         filter->filter_string = NULL;
1832                 } else {
1833                         append_filter_err(ps, filter);
1834                 }
1835         }
1836         create_filter_finish(ps);
1837
1838         *filterp = filter;
1839         return err;
1840 }
1841
1842 /* caller must hold event_mutex */
1843 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1844 {
1845         struct event_filter *filter;
1846         int err;
1847
1848         if (!strcmp(strstrip(filter_string), "0")) {
1849                 filter_disable(call);
1850                 filter = call->filter;
1851                 if (!filter)
1852                         return 0;
1853                 RCU_INIT_POINTER(call->filter, NULL);
1854                 /* Make sure the filter is not being used */
1855                 synchronize_sched();
1856                 __free_filter(filter);
1857                 return 0;
1858         }
1859
1860         err = create_filter(call, filter_string, true, &filter);
1861
1862         /*
1863          * Always swap the call filter with the new filter
1864          * even if there was an error. If there was an error
1865          * in the filter, we disable the filter and show the error
1866          * string
1867          */
1868         if (filter) {
1869                 struct event_filter *tmp = call->filter;
1870
1871                 if (!err)
1872                         call->flags |= TRACE_EVENT_FL_FILTERED;
1873                 else
1874                         filter_disable(call);
1875
1876                 rcu_assign_pointer(call->filter, filter);
1877
1878                 if (tmp) {
1879                         /* Make sure the call is done with the filter */
1880                         synchronize_sched();
1881                         __free_filter(tmp);
1882                 }
1883         }
1884
1885         return err;
1886 }
1887
1888 int apply_subsystem_event_filter(struct ftrace_subsystem_dir *dir,
1889                                  char *filter_string)
1890 {
1891         struct event_subsystem *system = dir->subsystem;
1892         struct event_filter *filter;
1893         int err = 0;
1894
1895         mutex_lock(&event_mutex);
1896
1897         /* Make sure the system still has events */
1898         if (!dir->nr_events) {
1899                 err = -ENODEV;
1900                 goto out_unlock;
1901         }
1902
1903         if (!strcmp(strstrip(filter_string), "0")) {
1904                 filter_free_subsystem_preds(system);
1905                 remove_filter_string(system->filter);
1906                 filter = system->filter;
1907                 system->filter = NULL;
1908                 /* Ensure all filters are no longer used */
1909                 synchronize_sched();
1910                 filter_free_subsystem_filters(system);
1911                 __free_filter(filter);
1912                 goto out_unlock;
1913         }
1914
1915         err = create_system_filter(system, filter_string, &filter);
1916         if (filter) {
1917                 /*
1918                  * No event actually uses the system filter
1919                  * we can free it without synchronize_sched().
1920                  */
1921                 __free_filter(system->filter);
1922                 system->filter = filter;
1923         }
1924 out_unlock:
1925         mutex_unlock(&event_mutex);
1926
1927         return err;
1928 }
1929
1930 #ifdef CONFIG_PERF_EVENTS
1931
1932 void ftrace_profile_free_filter(struct perf_event *event)
1933 {
1934         struct event_filter *filter = event->filter;
1935
1936         event->filter = NULL;
1937         __free_filter(filter);
1938 }
1939
1940 struct function_filter_data {
1941         struct ftrace_ops *ops;
1942         int first_filter;
1943         int first_notrace;
1944 };
1945
1946 #ifdef CONFIG_FUNCTION_TRACER
1947 static char **
1948 ftrace_function_filter_re(char *buf, int len, int *count)
1949 {
1950         char *str, *sep, **re;
1951
1952         str = kstrndup(buf, len, GFP_KERNEL);
1953         if (!str)
1954                 return NULL;
1955
1956         /*
1957          * The argv_split function takes white space
1958          * as a separator, so convert ',' into spaces.
1959          */
1960         while ((sep = strchr(str, ',')))
1961                 *sep = ' ';
1962
1963         re = argv_split(GFP_KERNEL, str, count);
1964         kfree(str);
1965         return re;
1966 }
1967
1968 static int ftrace_function_set_regexp(struct ftrace_ops *ops, int filter,
1969                                       int reset, char *re, int len)
1970 {
1971         int ret;
1972
1973         if (filter)
1974                 ret = ftrace_set_filter(ops, re, len, reset);
1975         else
1976                 ret = ftrace_set_notrace(ops, re, len, reset);
1977
1978         return ret;
1979 }
1980
1981 static int __ftrace_function_set_filter(int filter, char *buf, int len,
1982                                         struct function_filter_data *data)
1983 {
1984         int i, re_cnt, ret = -EINVAL;
1985         int *reset;
1986         char **re;
1987
1988         reset = filter ? &data->first_filter : &data->first_notrace;
1989
1990         /*
1991          * The 'ip' field could have multiple filters set, separated
1992          * either by space or comma. We first cut the filter and apply
1993          * all pieces separatelly.
1994          */
1995         re = ftrace_function_filter_re(buf, len, &re_cnt);
1996         if (!re)
1997                 return -EINVAL;
1998
1999         for (i = 0; i < re_cnt; i++) {
2000                 ret = ftrace_function_set_regexp(data->ops, filter, *reset,
2001                                                  re[i], strlen(re[i]));
2002                 if (ret)
2003                         break;
2004
2005                 if (*reset)
2006                         *reset = 0;
2007         }
2008
2009         argv_free(re);
2010         return ret;
2011 }
2012
2013 static int ftrace_function_check_pred(struct filter_pred *pred, int leaf)
2014 {
2015         struct ftrace_event_field *field = pred->field;
2016
2017         if (leaf) {
2018                 /*
2019                  * Check the leaf predicate for function trace, verify:
2020                  *  - only '==' and '!=' is used
2021                  *  - the 'ip' field is used
2022                  */
2023                 if ((pred->op != OP_EQ) && (pred->op != OP_NE))
2024                         return -EINVAL;
2025
2026                 if (strcmp(field->name, "ip"))
2027                         return -EINVAL;
2028         } else {
2029                 /*
2030                  * Check the non leaf predicate for function trace, verify:
2031                  *  - only '||' is used
2032                 */
2033                 if (pred->op != OP_OR)
2034                         return -EINVAL;
2035         }
2036
2037         return 0;
2038 }
2039
2040 static int ftrace_function_set_filter_cb(enum move_type move,
2041                                          struct filter_pred *pred,
2042                                          int *err, void *data)
2043 {
2044         /* Checking the node is valid for function trace. */
2045         if ((move != MOVE_DOWN) ||
2046             (pred->left != FILTER_PRED_INVALID)) {
2047                 *err = ftrace_function_check_pred(pred, 0);
2048         } else {
2049                 *err = ftrace_function_check_pred(pred, 1);
2050                 if (*err)
2051                         return WALK_PRED_ABORT;
2052
2053                 *err = __ftrace_function_set_filter(pred->op == OP_EQ,
2054                                                     pred->regex.pattern,
2055                                                     pred->regex.len,
2056                                                     data);
2057         }
2058
2059         return (*err) ? WALK_PRED_ABORT : WALK_PRED_DEFAULT;
2060 }
2061
2062 static int ftrace_function_set_filter(struct perf_event *event,
2063                                       struct event_filter *filter)
2064 {
2065         struct function_filter_data data = {
2066                 .first_filter  = 1,
2067                 .first_notrace = 1,
2068                 .ops           = &event->ftrace_ops,
2069         };
2070
2071         return walk_pred_tree(filter->preds, filter->root,
2072                               ftrace_function_set_filter_cb, &data);
2073 }
2074 #else
2075 static int ftrace_function_set_filter(struct perf_event *event,
2076                                       struct event_filter *filter)
2077 {
2078         return -ENODEV;
2079 }
2080 #endif /* CONFIG_FUNCTION_TRACER */
2081
2082 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
2083                               char *filter_str)
2084 {
2085         int err;
2086         struct event_filter *filter;
2087         struct ftrace_event_call *call;
2088
2089         mutex_lock(&event_mutex);
2090
2091         call = event->tp_event;
2092
2093         err = -EINVAL;
2094         if (!call)
2095                 goto out_unlock;
2096
2097         err = -EEXIST;
2098         if (event->filter)
2099                 goto out_unlock;
2100
2101         err = create_filter(call, filter_str, false, &filter);
2102         if (err)
2103                 goto free_filter;
2104
2105         if (ftrace_event_is_function(call))
2106                 err = ftrace_function_set_filter(event, filter);
2107         else
2108                 event->filter = filter;
2109
2110 free_filter:
2111         if (err || ftrace_event_is_function(call))
2112                 __free_filter(filter);
2113
2114 out_unlock:
2115         mutex_unlock(&event_mutex);
2116
2117         return err;
2118 }
2119
2120 #endif /* CONFIG_PERF_EVENTS */
2121
2122 #ifdef CONFIG_FTRACE_STARTUP_TEST
2123
2124 #include <linux/types.h>
2125 #include <linux/tracepoint.h>
2126
2127 #define CREATE_TRACE_POINTS
2128 #include "trace_events_filter_test.h"
2129
2130 #define DATA_REC(m, va, vb, vc, vd, ve, vf, vg, vh, nvisit) \
2131 { \
2132         .filter = FILTER, \
2133         .rec    = { .a = va, .b = vb, .c = vc, .d = vd, \
2134                     .e = ve, .f = vf, .g = vg, .h = vh }, \
2135         .match  = m, \
2136         .not_visited = nvisit, \
2137 }
2138 #define YES 1
2139 #define NO  0
2140
2141 static struct test_filter_data_t {
2142         char *filter;
2143         struct ftrace_raw_ftrace_test_filter rec;
2144         int match;
2145         char *not_visited;
2146 } test_filter_data[] = {
2147 #define FILTER "a == 1 && b == 1 && c == 1 && d == 1 && " \
2148                "e == 1 && f == 1 && g == 1 && h == 1"
2149         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, ""),
2150         DATA_REC(NO,  0, 1, 1, 1, 1, 1, 1, 1, "bcdefgh"),
2151         DATA_REC(NO,  1, 1, 1, 1, 1, 1, 1, 0, ""),
2152 #undef FILTER
2153 #define FILTER "a == 1 || b == 1 || c == 1 || d == 1 || " \
2154                "e == 1 || f == 1 || g == 1 || h == 1"
2155         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2156         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 0, 1, ""),
2157         DATA_REC(YES, 1, 0, 0, 0, 0, 0, 0, 0, "bcdefgh"),
2158 #undef FILTER
2159 #define FILTER "(a == 1 || b == 1) && (c == 1 || d == 1) && " \
2160                "(e == 1 || f == 1) && (g == 1 || h == 1)"
2161         DATA_REC(NO,  0, 0, 1, 1, 1, 1, 1, 1, "dfh"),
2162         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2163         DATA_REC(YES, 1, 0, 1, 0, 0, 1, 0, 1, "bd"),
2164         DATA_REC(NO,  1, 0, 1, 0, 0, 1, 0, 0, "bd"),
2165 #undef FILTER
2166 #define FILTER "(a == 1 && b == 1) || (c == 1 && d == 1) || " \
2167                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2168         DATA_REC(YES, 1, 0, 1, 1, 1, 1, 1, 1, "efgh"),
2169         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 1, 1, ""),
2170         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2171 #undef FILTER
2172 #define FILTER "(a == 1 && b == 1) && (c == 1 && d == 1) && " \
2173                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2174         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 0, "gh"),
2175         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2176         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, ""),
2177 #undef FILTER
2178 #define FILTER "((a == 1 || b == 1) || (c == 1 || d == 1) || " \
2179                "(e == 1 || f == 1)) && (g == 1 || h == 1)"
2180         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 1, "bcdef"),
2181         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2182         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, "h"),
2183 #undef FILTER
2184 #define FILTER "((((((((a == 1) && (b == 1)) || (c == 1)) && (d == 1)) || " \
2185                "(e == 1)) && (f == 1)) || (g == 1)) && (h == 1))"
2186         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "ceg"),
2187         DATA_REC(NO,  0, 1, 0, 1, 0, 1, 0, 1, ""),
2188         DATA_REC(NO,  1, 0, 1, 0, 1, 0, 1, 0, ""),
2189 #undef FILTER
2190 #define FILTER "((((((((a == 1) || (b == 1)) && (c == 1)) || (d == 1)) && " \
2191                "(e == 1)) || (f == 1)) && (g == 1)) || (h == 1))"
2192         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "bdfh"),
2193         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2194         DATA_REC(YES, 1, 0, 1, 0, 1, 0, 1, 0, "bdfh"),
2195 };
2196
2197 #undef DATA_REC
2198 #undef FILTER
2199 #undef YES
2200 #undef NO
2201
2202 #define DATA_CNT (sizeof(test_filter_data)/sizeof(struct test_filter_data_t))
2203
2204 static int test_pred_visited;
2205
2206 static int test_pred_visited_fn(struct filter_pred *pred, void *event)
2207 {
2208         struct ftrace_event_field *field = pred->field;
2209
2210         test_pred_visited = 1;
2211         printk(KERN_INFO "\npred visited %s\n", field->name);
2212         return 1;
2213 }
2214
2215 static int test_walk_pred_cb(enum move_type move, struct filter_pred *pred,
2216                              int *err, void *data)
2217 {
2218         char *fields = data;
2219
2220         if ((move == MOVE_DOWN) &&
2221             (pred->left == FILTER_PRED_INVALID)) {
2222                 struct ftrace_event_field *field = pred->field;
2223
2224                 if (!field) {
2225                         WARN(1, "all leafs should have field defined");
2226                         return WALK_PRED_DEFAULT;
2227                 }
2228                 if (!strchr(fields, *field->name))
2229                         return WALK_PRED_DEFAULT;
2230
2231                 WARN_ON(!pred->fn);
2232                 pred->fn = test_pred_visited_fn;
2233         }
2234         return WALK_PRED_DEFAULT;
2235 }
2236
2237 static __init int ftrace_test_event_filter(void)
2238 {
2239         int i;
2240
2241         printk(KERN_INFO "Testing ftrace filter: ");
2242
2243         for (i = 0; i < DATA_CNT; i++) {
2244                 struct event_filter *filter = NULL;
2245                 struct test_filter_data_t *d = &test_filter_data[i];
2246                 int err;
2247
2248                 err = create_filter(&event_ftrace_test_filter, d->filter,
2249                                     false, &filter);
2250                 if (err) {
2251                         printk(KERN_INFO
2252                                "Failed to get filter for '%s', err %d\n",
2253                                d->filter, err);
2254                         __free_filter(filter);
2255                         break;
2256                 }
2257
2258                 /*
2259                  * The preemption disabling is not really needed for self
2260                  * tests, but the rcu dereference will complain without it.
2261                  */
2262                 preempt_disable();
2263                 if (*d->not_visited)
2264                         walk_pred_tree(filter->preds, filter->root,
2265                                        test_walk_pred_cb,
2266                                        d->not_visited);
2267
2268                 test_pred_visited = 0;
2269                 err = filter_match_preds(filter, &d->rec);
2270                 preempt_enable();
2271
2272                 __free_filter(filter);
2273
2274                 if (test_pred_visited) {
2275                         printk(KERN_INFO
2276                                "Failed, unwanted pred visited for filter %s\n",
2277                                d->filter);
2278                         break;
2279                 }
2280
2281                 if (err != d->match) {
2282                         printk(KERN_INFO
2283                                "Failed to match filter '%s', expected %d\n",
2284                                d->filter, d->match);
2285                         break;
2286                 }
2287         }
2288
2289         if (i == DATA_CNT)
2290                 printk(KERN_CONT "OK\n");
2291
2292         return 0;
2293 }
2294
2295 late_initcall(ftrace_test_event_filter);
2296
2297 #endif /* CONFIG_FTRACE_STARTUP_TEST */