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