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 static inline struct event_filter *event_filter(struct ftrace_event_file *file)
 641 {
 642         if (file->event_call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
 643                 return file->event_call->filter;
 644         else
 645                 return file->filter;
 646 }
 647
 648 /* caller must hold event_mutex */
 649 void print_event_filter(struct ftrace_event_file *file, struct trace_seq *s)
 650 {
 651         struct event_filter *filter = event_filter(file);
 652
 653         if (filter && filter->filter_string)
 654                 trace_seq_printf(s, "%s\n", filter->filter_string);
 655         else
 656                 trace_seq_puts(s, "none\n");
 657 }
 658
 659 void print_subsystem_event_filter(struct event_subsystem *system,
 660                                   struct trace_seq *s)
 661 {
 662         struct event_filter *filter;
 663
 664         mutex_lock(&event_mutex);
 665         filter = system->filter;
 666         if (filter && filter->filter_string)
 667                 trace_seq_printf(s, "%s\n", filter->filter_string);
 668         else
 669                 trace_seq_puts(s, DEFAULT_SYS_FILTER_MESSAGE "\n");
 670         mutex_unlock(&event_mutex);
 671 }
 672
 673 static int __alloc_pred_stack(struct pred_stack *stack, int n_preds)
 674 {
 675         stack->preds = kcalloc(n_preds + 1, sizeof(*stack->preds), GFP_KERNEL);
 676         if (!stack->preds)
 677                 return -ENOMEM;
 678         stack->index = n_preds;
 679         return 0;
 680 }
 681
 682 static void __free_pred_stack(struct pred_stack *stack)
 683 {
 684         kfree(stack->preds);
 685         stack->index = 0;
 686 }
 687
 688 static int __push_pred_stack(struct pred_stack *stack,
 689                              struct filter_pred *pred)
 690 {
 691         int index = stack->index;
 692
 693         if (WARN_ON(index == 0))
 694                 return -ENOSPC;
 695
 696         stack->preds[--index] = pred;
 697         stack->index = index;
 698         return 0;
 699 }
 700
 701 static struct filter_pred *
 702 __pop_pred_stack(struct pred_stack *stack)
 703 {
 704         struct filter_pred *pred;
 705         int index = stack->index;
 706
 707         pred = stack->preds[index++];
 708         if (!pred)
 709                 return NULL;
 710
 711         stack->index = index;
 712         return pred;
 713 }
 714
 715 static int filter_set_pred(struct event_filter *filter,
 716                            int idx,
 717                            struct pred_stack *stack,
 718                            struct filter_pred *src)
 719 {
 720         struct filter_pred *dest = &filter->preds[idx];
 721         struct filter_pred *left;
 722         struct filter_pred *right;
 723
 724         *dest = *src;
 725         dest->index = idx;
 726
 727         if (dest->op == OP_OR || dest->op == OP_AND) {
 728                 right = __pop_pred_stack(stack);
 729                 left = __pop_pred_stack(stack);
 730                 if (!left || !right)
 731                         return -EINVAL;
 732                 /*
 733                  * If both children can be folded
 734                  * and they are the same op as this op or a leaf,
 735                  * then this op can be folded.
 736                  */
 737                 if (left->index & FILTER_PRED_FOLD &&
 738                     (left->op == dest->op ||
 739                      left->left == FILTER_PRED_INVALID) &&
 740                     right->index & FILTER_PRED_FOLD &&
 741                     (right->op == dest->op ||
 742                      right->left == FILTER_PRED_INVALID))
 743                         dest->index |= FILTER_PRED_FOLD;
 744
 745                 dest->left = left->index & ~FILTER_PRED_FOLD;
 746                 dest->right = right->index & ~FILTER_PRED_FOLD;
 747                 left->parent = dest->index & ~FILTER_PRED_FOLD;
 748                 right->parent = dest->index | FILTER_PRED_IS_RIGHT;
 749         } else {
 750                 /*
 751                  * Make dest->left invalid to be used as a quick
 752                  * way to know this is a leaf node.
 753                  */
 754                 dest->left = FILTER_PRED_INVALID;
 755
 756                 /* All leafs allow folding the parent ops. */
 757                 dest->index |= FILTER_PRED_FOLD;
 758         }
 759
 760         return __push_pred_stack(stack, dest);
 761 }
 762
 763 static void __free_preds(struct event_filter *filter)
 764 {
 765         int i;
 766
 767         if (filter->preds) {
 768                 for (i = 0; i < filter->n_preds; i++)
 769                         kfree(filter->preds[i].ops);
 770                 kfree(filter->preds);
 771                 filter->preds = NULL;
 772         }
 773         filter->a_preds = 0;
 774         filter->n_preds = 0;
 775 }
 776
 777 static void filter_disable(struct ftrace_event_file *file)
 778 {
 779         struct ftrace_event_call *call = file->event_call;
 780
 781         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
 782                 call->flags &= ~TRACE_EVENT_FL_FILTERED;
 783         else
 784                 file->flags &= ~FTRACE_EVENT_FL_FILTERED;
 785 }
 786
 787 static void __free_filter(struct event_filter *filter)
 788 {
 789         if (!filter)
 790                 return;
 791
 792         __free_preds(filter);
 793         kfree(filter->filter_string);
 794         kfree(filter);
 795 }
 796
 797 void free_event_filter(struct event_filter *filter)
 798 {
 799         __free_filter(filter);
 800 }
 801
 802 static struct event_filter *__alloc_filter(void)
 803 {
 804         struct event_filter *filter;
 805
 806         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 807         return filter;
 808 }
 809
 810 static int __alloc_preds(struct event_filter *filter, int n_preds)
 811 {
 812         struct filter_pred *pred;
 813         int i;
 814
 815         if (filter->preds)
 816                 __free_preds(filter);
 817
 818         filter->preds = kcalloc(n_preds, sizeof(*filter->preds), GFP_KERNEL);
 819
 820         if (!filter->preds)
 821                 return -ENOMEM;
 822
 823         filter->a_preds = n_preds;
 824         filter->n_preds = 0;
 825
 826         for (i = 0; i < n_preds; i++) {
 827                 pred = &filter->preds[i];
 828                 pred->fn = filter_pred_none;
 829         }
 830
 831         return 0;
 832 }
 833
 834 static inline void __remove_filter(struct ftrace_event_file *file)
 835 {
 836         struct ftrace_event_call *call = file->event_call;
 837
 838         filter_disable(file);
 839         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
 840                 remove_filter_string(call->filter);
 841         else
 842                 remove_filter_string(file->filter);
 843 }
 844
 845 static void filter_free_subsystem_preds(struct ftrace_subsystem_dir *dir,
 846                                         struct trace_array *tr)
 847 {
 848         struct ftrace_event_file *file;
 849
 850         list_for_each_entry(file, &tr->events, list) {
 851                 if (file->system != dir)
 852                         continue;
 853                 __remove_filter(file);
 854         }
 855 }
 856
 857 static inline void __free_subsystem_filter(struct ftrace_event_file *file)
 858 {
 859         struct ftrace_event_call *call = file->event_call;
 860
 861         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER) {
 862                 __free_filter(call->filter);
 863                 call->filter = NULL;
 864         } else {
 865                 __free_filter(file->filter);
 866                 file->filter = NULL;
 867         }
 868 }
 869
 870 static void filter_free_subsystem_filters(struct ftrace_subsystem_dir *dir,
 871                                           struct trace_array *tr)
 872 {
 873         struct ftrace_event_file *file;
 874
 875         list_for_each_entry(file, &tr->events, list) {
 876                 if (file->system != dir)
 877                         continue;
 878                 __free_subsystem_filter(file);
 879         }
 880 }
 881
 882 static int filter_add_pred(struct filter_parse_state *ps,
 883                            struct event_filter *filter,
 884                            struct filter_pred *pred,
 885                            struct pred_stack *stack)
 886 {
 887         int err;
 888
 889         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 890                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 891                 return -ENOSPC;
 892         }
 893
 894         err = filter_set_pred(filter, filter->n_preds, stack, pred);
 895         if (err)
 896                 return err;
 897
 898         filter->n_preds++;
 899
 900         return 0;
 901 }
 902
 903 int filter_assign_type(const char *type)
 904 {
 905         if (strstr(type, "__data_loc") && strstr(type, "char"))
 906                 return FILTER_DYN_STRING;
 907
 908         if (strchr(type, '[') && strstr(type, "char"))
 909                 return FILTER_STATIC_STRING;
 910
 911         return FILTER_OTHER;
 912 }
 913
 914 static bool is_function_field(struct ftrace_event_field *field)
 915 {
 916         return field->filter_type == FILTER_TRACE_FN;
 917 }
 918
 919 static bool is_string_field(struct ftrace_event_field *field)
 920 {
 921         return field->filter_type == FILTER_DYN_STRING ||
 922                field->filter_type == FILTER_STATIC_STRING ||
 923                field->filter_type == FILTER_PTR_STRING;
 924 }
 925
 926 static int is_legal_op(struct ftrace_event_field *field, int op)
 927 {
 928         if (is_string_field(field) &&
 929             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 930                 return 0;
 931         if (!is_string_field(field) && op == OP_GLOB)
 932                 return 0;
 933
 934         return 1;
 935 }
 936
 937 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 938                                              int field_is_signed)
 939 {
 940         filter_pred_fn_t fn = NULL;
 941
 942         switch (field_size) {
 943         case 8:
 944                 if (op == OP_EQ || op == OP_NE)
 945                         fn = filter_pred_64;
 946                 else if (field_is_signed)
 947                         fn = filter_pred_s64;
 948                 else
 949                         fn = filter_pred_u64;
 950                 break;
 951         case 4:
 952                 if (op == OP_EQ || op == OP_NE)
 953                         fn = filter_pred_32;
 954                 else if (field_is_signed)
 955                         fn = filter_pred_s32;
 956                 else
 957                         fn = filter_pred_u32;
 958                 break;
 959         case 2:
 960                 if (op == OP_EQ || op == OP_NE)
 961                         fn = filter_pred_16;
 962                 else if (field_is_signed)
 963                         fn = filter_pred_s16;
 964                 else
 965                         fn = filter_pred_u16;
 966                 break;
 967         case 1:
 968                 if (op == OP_EQ || op == OP_NE)
 969                         fn = filter_pred_8;
 970                 else if (field_is_signed)
 971                         fn = filter_pred_s8;
 972                 else
 973                         fn = filter_pred_u8;
 974                 break;
 975         }
 976
 977         return fn;
 978 }
 979
 980 static int init_pred(struct filter_parse_state *ps,
 981                      struct ftrace_event_field *field,
 982                      struct filter_pred *pred)
 983
 984 {
 985         filter_pred_fn_t fn = filter_pred_none;
 986         unsigned long long val;
 987         int ret;
 988
 989         pred->offset = field->offset;
 990
 991         if (!is_legal_op(field, pred->op)) {
 992                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 993                 return -EINVAL;
 994         }
 995
 996         if (is_string_field(field)) {
 997                 filter_build_regex(pred);
 998
 999                 if (field->filter_type == FILTER_STATIC_STRING) {
1000                         fn = filter_pred_string;
1001                         pred->regex.field_len = field->size;
1002                 } else if (field->filter_type == FILTER_DYN_STRING)
1003                         fn = filter_pred_strloc;
1004                 else
1005                         fn = filter_pred_pchar;
1006         } else if (is_function_field(field)) {
1007                 if (strcmp(field->name, "ip")) {
1008                         parse_error(ps, FILT_ERR_IP_FIELD_ONLY, 0);
1009                         return -EINVAL;
1010                 }
1011         } else {
1012                 if (field->is_signed)
1013                         ret = kstrtoll(pred->regex.pattern, 0, &val);
1014                 else
1015                         ret = kstrtoull(pred->regex.pattern, 0, &val);
1016                 if (ret) {
1017                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
1018                         return -EINVAL;
1019                 }
1020                 pred->val = val;
1021
1022                 fn = select_comparison_fn(pred->op, field->size,
1023                                           field->is_signed);
1024                 if (!fn) {
1025                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
1026                         return -EINVAL;
1027                 }
1028         }
1029
1030         if (pred->op == OP_NE)
1031                 pred->not = 1;
1032
1033         pred->fn = fn;
1034         return 0;
1035 }
1036
1037 static void parse_init(struct filter_parse_state *ps,
1038                        struct filter_op *ops,
1039                        char *infix_string)
1040 {
1041         memset(ps, '\0', sizeof(*ps));
1042
1043         ps->infix.string = infix_string;
1044         ps->infix.cnt = strlen(infix_string);
1045         ps->ops = ops;
1046
1047         INIT_LIST_HEAD(&ps->opstack);
1048         INIT_LIST_HEAD(&ps->postfix);
1049 }
1050
1051 static char infix_next(struct filter_parse_state *ps)
1052 {
1053         ps->infix.cnt--;
1054
1055         return ps->infix.string[ps->infix.tail++];
1056 }
1057
1058 static char infix_peek(struct filter_parse_state *ps)
1059 {
1060         if (ps->infix.tail == strlen(ps->infix.string))
1061                 return 0;
1062
1063         return ps->infix.string[ps->infix.tail];
1064 }
1065
1066 static void infix_advance(struct filter_parse_state *ps)
1067 {
1068         ps->infix.cnt--;
1069         ps->infix.tail++;
1070 }
1071
1072 static inline int is_precedence_lower(struct filter_parse_state *ps,
1073                                       int a, int b)
1074 {
1075         return ps->ops[a].precedence < ps->ops[b].precedence;
1076 }
1077
1078 static inline int is_op_char(struct filter_parse_state *ps, char c)
1079 {
1080         int i;
1081
1082         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1083                 if (ps->ops[i].string[0] == c)
1084                         return 1;
1085         }
1086
1087         return 0;
1088 }
1089
1090 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1091 {
1092         char nextc = infix_peek(ps);
1093         char opstr[3];
1094         int i;
1095
1096         opstr[0] = firstc;
1097         opstr[1] = nextc;
1098         opstr[2] = '\0';
1099
1100         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1101                 if (!strcmp(opstr, ps->ops[i].string)) {
1102                         infix_advance(ps);
1103                         return ps->ops[i].id;
1104                 }
1105         }
1106
1107         opstr[1] = '\0';
1108
1109         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1110                 if (!strcmp(opstr, ps->ops[i].string))
1111                         return ps->ops[i].id;
1112         }
1113
1114         return OP_NONE;
1115 }
1116
1117 static inline void clear_operand_string(struct filter_parse_state *ps)
1118 {
1119         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1120         ps->operand.tail = 0;
1121 }
1122
1123 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1124 {
1125         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1126                 return -EINVAL;
1127
1128         ps->operand.string[ps->operand.tail++] = c;
1129
1130         return 0;
1131 }
1132
1133 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1134 {
1135         struct opstack_op *opstack_op;
1136
1137         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1138         if (!opstack_op)
1139                 return -ENOMEM;
1140
1141         opstack_op->op = op;
1142         list_add(&opstack_op->list, &ps->opstack);
1143
1144         return 0;
1145 }
1146
1147 static int filter_opstack_empty(struct filter_parse_state *ps)
1148 {
1149         return list_empty(&ps->opstack);
1150 }
1151
1152 static int filter_opstack_top(struct filter_parse_state *ps)
1153 {
1154         struct opstack_op *opstack_op;
1155
1156         if (filter_opstack_empty(ps))
1157                 return OP_NONE;
1158
1159         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1160
1161         return opstack_op->op;
1162 }
1163
1164 static int filter_opstack_pop(struct filter_parse_state *ps)
1165 {
1166         struct opstack_op *opstack_op;
1167         int op;
1168
1169         if (filter_opstack_empty(ps))
1170                 return OP_NONE;
1171
1172         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1173         op = opstack_op->op;
1174         list_del(&opstack_op->list);
1175
1176         kfree(opstack_op);
1177
1178         return op;
1179 }
1180
1181 static void filter_opstack_clear(struct filter_parse_state *ps)
1182 {
1183         while (!filter_opstack_empty(ps))
1184                 filter_opstack_pop(ps);
1185 }
1186
1187 static char *curr_operand(struct filter_parse_state *ps)
1188 {
1189         return ps->operand.string;
1190 }
1191
1192 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1193 {
1194         struct postfix_elt *elt;
1195
1196         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1197         if (!elt)
1198                 return -ENOMEM;
1199
1200         elt->op = OP_NONE;
1201         elt->operand = kstrdup(operand, GFP_KERNEL);
1202         if (!elt->operand) {
1203                 kfree(elt);
1204                 return -ENOMEM;
1205         }
1206
1207         list_add_tail(&elt->list, &ps->postfix);
1208
1209         return 0;
1210 }
1211
1212 static int postfix_append_op(struct filter_parse_state *ps, int op)
1213 {
1214         struct postfix_elt *elt;
1215
1216         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1217         if (!elt)
1218                 return -ENOMEM;
1219
1220         elt->op = op;
1221         elt->operand = NULL;
1222
1223         list_add_tail(&elt->list, &ps->postfix);
1224
1225         return 0;
1226 }
1227
1228 static void postfix_clear(struct filter_parse_state *ps)
1229 {
1230         struct postfix_elt *elt;
1231
1232         while (!list_empty(&ps->postfix)) {
1233                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1234                 list_del(&elt->list);
1235                 kfree(elt->operand);
1236                 kfree(elt);
1237         }
1238 }
1239
1240 static int filter_parse(struct filter_parse_state *ps)
1241 {
1242         int in_string = 0;
1243         int op, top_op;
1244         char ch;
1245
1246         while ((ch = infix_next(ps))) {
1247                 if (ch == '"') {
1248                         in_string ^= 1;
1249                         continue;
1250                 }
1251
1252                 if (in_string)
1253                         goto parse_operand;
1254
1255                 if (isspace(ch))
1256                         continue;
1257
1258                 if (is_op_char(ps, ch)) {
1259                         op = infix_get_op(ps, ch);
1260                         if (op == OP_NONE) {
1261                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1262                                 return -EINVAL;
1263                         }
1264
1265                         if (strlen(curr_operand(ps))) {
1266                                 postfix_append_operand(ps, curr_operand(ps));
1267                                 clear_operand_string(ps);
1268                         }
1269
1270                         while (!filter_opstack_empty(ps)) {
1271                                 top_op = filter_opstack_top(ps);
1272                                 if (!is_precedence_lower(ps, top_op, op)) {
1273                                         top_op = filter_opstack_pop(ps);
1274                                         postfix_append_op(ps, top_op);
1275                                         continue;
1276                                 }
1277                                 break;
1278                         }
1279
1280                         filter_opstack_push(ps, op);
1281                         continue;
1282                 }
1283
1284                 if (ch == '(') {
1285                         filter_opstack_push(ps, OP_OPEN_PAREN);
1286                         continue;
1287                 }
1288
1289                 if (ch == ')') {
1290                         if (strlen(curr_operand(ps))) {
1291                                 postfix_append_operand(ps, curr_operand(ps));
1292                                 clear_operand_string(ps);
1293                         }
1294
1295                         top_op = filter_opstack_pop(ps);
1296                         while (top_op != OP_NONE) {
1297                                 if (top_op == OP_OPEN_PAREN)
1298                                         break;
1299                                 postfix_append_op(ps, top_op);
1300                                 top_op = filter_opstack_pop(ps);
1301                         }
1302                         if (top_op == OP_NONE) {
1303                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1304                                 return -EINVAL;
1305                         }
1306                         continue;
1307                 }
1308 parse_operand:
1309                 if (append_operand_char(ps, ch)) {
1310                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1311                         return -EINVAL;
1312                 }
1313         }
1314
1315         if (strlen(curr_operand(ps)))
1316                 postfix_append_operand(ps, curr_operand(ps));
1317
1318         while (!filter_opstack_empty(ps)) {
1319                 top_op = filter_opstack_pop(ps);
1320                 if (top_op == OP_NONE)
1321                         break;
1322                 if (top_op == OP_OPEN_PAREN) {
1323                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1324                         return -EINVAL;
1325                 }
1326                 postfix_append_op(ps, top_op);
1327         }
1328
1329         return 0;
1330 }
1331
1332 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1333                                        struct ftrace_event_call *call,
1334                                        int op, char *operand1, char *operand2)
1335 {
1336         struct ftrace_event_field *field;
1337         static struct filter_pred pred;
1338
1339         memset(&pred, 0, sizeof(pred));
1340         pred.op = op;
1341
1342         if (op == OP_AND || op == OP_OR)
1343                 return &pred;
1344
1345         if (!operand1 || !operand2) {
1346                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1347                 return NULL;
1348         }
1349
1350         field = trace_find_event_field(call, operand1);
1351         if (!field) {
1352                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1353                 return NULL;
1354         }
1355
1356         strcpy(pred.regex.pattern, operand2);
1357         pred.regex.len = strlen(pred.regex.pattern);
1358         pred.field = field;
1359         return init_pred(ps, field, &pred) ? NULL : &pred;
1360 }
1361
1362 static int check_preds(struct filter_parse_state *ps)
1363 {
1364         int n_normal_preds = 0, n_logical_preds = 0;
1365         struct postfix_elt *elt;
1366
1367         list_for_each_entry(elt, &ps->postfix, list) {
1368                 if (elt->op == OP_NONE)
1369                         continue;
1370
1371                 if (elt->op == OP_AND || elt->op == OP_OR) {
1372                         n_logical_preds++;
1373                         continue;
1374                 }
1375                 n_normal_preds++;
1376         }
1377
1378         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1379                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1380                 return -EINVAL;
1381         }
1382
1383         return 0;
1384 }
1385
1386 static int count_preds(struct filter_parse_state *ps)
1387 {
1388         struct postfix_elt *elt;
1389         int n_preds = 0;
1390
1391         list_for_each_entry(elt, &ps->postfix, list) {
1392                 if (elt->op == OP_NONE)
1393                         continue;
1394                 n_preds++;
1395         }
1396
1397         return n_preds;
1398 }
1399
1400 struct check_pred_data {
1401         int count;
1402         int max;
1403 };
1404
1405 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1406                               int *err, void *data)
1407 {
1408         struct check_pred_data *d = data;
1409
1410         if (WARN_ON(d->count++ > d->max)) {
1411                 *err = -EINVAL;
1412                 return WALK_PRED_ABORT;
1413         }
1414         return WALK_PRED_DEFAULT;
1415 }
1416
1417 /*
1418  * The tree is walked at filtering of an event. If the tree is not correctly
1419  * built, it may cause an infinite loop. Check here that the tree does
1420  * indeed terminate.
1421  */
1422 static int check_pred_tree(struct event_filter *filter,
1423                            struct filter_pred *root)
1424 {
1425         struct check_pred_data data = {
1426                 /*
1427                  * The max that we can hit a node is three times.
1428                  * Once going down, once coming up from left, and
1429                  * once coming up from right. This is more than enough
1430                  * since leafs are only hit a single time.
1431                  */
1432                 .max   = 3 * filter->n_preds,
1433                 .count = 0,
1434         };
1435
1436         return walk_pred_tree(filter->preds, root,
1437                               check_pred_tree_cb, &data);
1438 }
1439
1440 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1441                           int *err, void *data)
1442 {
1443         int *count = data;
1444
1445         if ((move == MOVE_DOWN) &&
1446             (pred->left == FILTER_PRED_INVALID))
1447                 (*count)++;
1448
1449         return WALK_PRED_DEFAULT;
1450 }
1451
1452 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1453 {
1454         int count = 0, ret;
1455
1456         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1457         WARN_ON(ret);
1458         return count;
1459 }
1460
1461 struct fold_pred_data {
1462         struct filter_pred *root;
1463         int count;
1464         int children;
1465 };
1466
1467 static int fold_pred_cb(enum move_type move, struct filter_pred *pred,
1468                         int *err, void *data)
1469 {
1470         struct fold_pred_data *d = data;
1471         struct filter_pred *root = d->root;
1472
1473         if (move != MOVE_DOWN)
1474                 return WALK_PRED_DEFAULT;
1475         if (pred->left != FILTER_PRED_INVALID)
1476                 return WALK_PRED_DEFAULT;
1477
1478         if (WARN_ON(d->count == d->children)) {
1479                 *err = -EINVAL;
1480                 return WALK_PRED_ABORT;
1481         }
1482
1483         pred->index &= ~FILTER_PRED_FOLD;
1484         root->ops[d->count++] = pred->index;
1485         return WALK_PRED_DEFAULT;
1486 }
1487
1488 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1489 {
1490         struct fold_pred_data data = {
1491                 .root  = root,
1492                 .count = 0,
1493         };
1494         int children;
1495
1496         /* No need to keep the fold flag */
1497         root->index &= ~FILTER_PRED_FOLD;
1498
1499         /* If the root is a leaf then do nothing */
1500         if (root->left == FILTER_PRED_INVALID)
1501                 return 0;
1502
1503         /* count the children */
1504         children = count_leafs(preds, &preds[root->left]);
1505         children += count_leafs(preds, &preds[root->right]);
1506
1507         root->ops = kcalloc(children, sizeof(*root->ops), GFP_KERNEL);
1508         if (!root->ops)
1509                 return -ENOMEM;
1510
1511         root->val = children;
1512         data.children = children;
1513         return walk_pred_tree(preds, root, fold_pred_cb, &data);
1514 }
1515
1516 static int fold_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1517                              int *err, void *data)
1518 {
1519         struct filter_pred *preds = data;
1520
1521         if (move != MOVE_DOWN)
1522                 return WALK_PRED_DEFAULT;
1523         if (!(pred->index & FILTER_PRED_FOLD))
1524                 return WALK_PRED_DEFAULT;
1525
1526         *err = fold_pred(preds, pred);
1527         if (*err)
1528                 return WALK_PRED_ABORT;
1529
1530         /* eveyrhing below is folded, continue with parent */
1531         return WALK_PRED_PARENT;
1532 }
1533
1534 /*
1535  * To optimize the processing of the ops, if we have several "ors" or
1536  * "ands" together, we can put them in an array and process them all
1537  * together speeding up the filter logic.
1538  */
1539 static int fold_pred_tree(struct event_filter *filter,
1540                            struct filter_pred *root)
1541 {
1542         return walk_pred_tree(filter->preds, root, fold_pred_tree_cb,
1543                               filter->preds);
1544 }
1545
1546 static int replace_preds(struct ftrace_event_call *call,
1547                          struct event_filter *filter,
1548                          struct filter_parse_state *ps,
1549                          bool dry_run)
1550 {
1551         char *operand1 = NULL, *operand2 = NULL;
1552         struct filter_pred *pred;
1553         struct filter_pred *root;
1554         struct postfix_elt *elt;
1555         struct pred_stack stack = { }; /* init to NULL */
1556         int err;
1557         int n_preds = 0;
1558
1559         n_preds = count_preds(ps);
1560         if (n_preds >= MAX_FILTER_PRED) {
1561                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1562                 return -ENOSPC;
1563         }
1564
1565         err = check_preds(ps);
1566         if (err)
1567                 return err;
1568
1569         if (!dry_run) {
1570                 err = __alloc_pred_stack(&stack, n_preds);
1571                 if (err)
1572                         return err;
1573                 err = __alloc_preds(filter, n_preds);
1574                 if (err)
1575                         goto fail;
1576         }
1577
1578         n_preds = 0;
1579         list_for_each_entry(elt, &ps->postfix, list) {
1580                 if (elt->op == OP_NONE) {
1581                         if (!operand1)
1582                                 operand1 = elt->operand;
1583                         else if (!operand2)
1584                                 operand2 = elt->operand;
1585                         else {
1586                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1587                                 err = -EINVAL;
1588                                 goto fail;
1589                         }
1590                         continue;
1591                 }
1592
1593                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1594                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1595                         err = -ENOSPC;
1596                         goto fail;
1597                 }
1598
1599                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1600                 if (!pred) {
1601                         err = -EINVAL;
1602                         goto fail;
1603                 }
1604
1605                 if (!dry_run) {
1606                         err = filter_add_pred(ps, filter, pred, &stack);
1607                         if (err)
1608                                 goto fail;
1609                 }
1610
1611                 operand1 = operand2 = NULL;
1612         }
1613
1614         if (!dry_run) {
1615                 /* We should have one item left on the stack */
1616                 pred = __pop_pred_stack(&stack);
1617                 if (!pred)
1618                         return -EINVAL;
1619                 /* This item is where we start from in matching */
1620                 root = pred;
1621                 /* Make sure the stack is empty */
1622                 pred = __pop_pred_stack(&stack);
1623                 if (WARN_ON(pred)) {
1624                         err = -EINVAL;
1625                         filter->root = NULL;
1626                         goto fail;
1627                 }
1628                 err = check_pred_tree(filter, root);
1629                 if (err)
1630                         goto fail;
1631
1632                 /* Optimize the tree */
1633                 err = fold_pred_tree(filter, root);
1634                 if (err)
1635                         goto fail;
1636
1637                 /* We don't set root until we know it works */
1638                 barrier();
1639                 filter->root = root;
1640         }
1641
1642         err = 0;
1643 fail:
1644         __free_pred_stack(&stack);
1645         return err;
1646 }
1647
1648 static inline void event_set_filtered_flag(struct ftrace_event_file *file)
1649 {
1650         struct ftrace_event_call *call = file->event_call;
1651
1652         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1653                 call->flags |= TRACE_EVENT_FL_FILTERED;
1654         else
1655                 file->flags |= FTRACE_EVENT_FL_FILTERED;
1656 }
1657
1658 static inline void event_set_filter(struct ftrace_event_file *file,
1659                                     struct event_filter *filter)
1660 {
1661         struct ftrace_event_call *call = file->event_call;
1662
1663         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1664                 rcu_assign_pointer(call->filter, filter);
1665         else
1666                 rcu_assign_pointer(file->filter, filter);
1667 }
1668
1669 static inline void event_clear_filter(struct ftrace_event_file *file)
1670 {
1671         struct ftrace_event_call *call = file->event_call;
1672
1673         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1674                 RCU_INIT_POINTER(call->filter, NULL);
1675         else
1676                 RCU_INIT_POINTER(file->filter, NULL);
1677 }
1678
1679 static inline void
1680 event_set_no_set_filter_flag(struct ftrace_event_file *file)
1681 {
1682         struct ftrace_event_call *call = file->event_call;
1683
1684         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1685                 call->flags |= TRACE_EVENT_FL_NO_SET_FILTER;
1686         else
1687                 file->flags |= FTRACE_EVENT_FL_NO_SET_FILTER;
1688 }
1689
1690 static inline void
1691 event_clear_no_set_filter_flag(struct ftrace_event_file *file)
1692 {
1693         struct ftrace_event_call *call = file->event_call;
1694
1695         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1696                 call->flags &= ~TRACE_EVENT_FL_NO_SET_FILTER;
1697         else
1698                 file->flags &= ~FTRACE_EVENT_FL_NO_SET_FILTER;
1699 }
1700
1701 static inline bool
1702 event_no_set_filter_flag(struct ftrace_event_file *file)
1703 {
1704         struct ftrace_event_call *call = file->event_call;
1705
1706         if (file->flags & FTRACE_EVENT_FL_NO_SET_FILTER)
1707                 return true;
1708
1709         if ((call->flags & TRACE_EVENT_FL_USE_CALL_FILTER) &&
1710             (call->flags & TRACE_EVENT_FL_NO_SET_FILTER))
1711                 return true;
1712
1713         return false;
1714 }
1715
1716 struct filter_list {
1717         struct list_head        list;
1718         struct event_filter     *filter;
1719 };
1720
1721 static int replace_system_preds(struct ftrace_subsystem_dir *dir,
1722                                 struct trace_array *tr,
1723                                 struct filter_parse_state *ps,
1724                                 char *filter_string)
1725 {
1726         struct ftrace_event_file *file;
1727         struct filter_list *filter_item;
1728         struct filter_list *tmp;
1729         LIST_HEAD(filter_list);
1730         bool fail = true;
1731         int err;
1732
1733         list_for_each_entry(file, &tr->events, list) {
1734                 if (file->system != dir)
1735                         continue;
1736
1737                 /*
1738                  * Try to see if the filter can be applied
1739                  *  (filter arg is ignored on dry_run)
1740                  */
1741                 err = replace_preds(file->event_call, NULL, ps, true);
1742                 if (err)
1743                         event_set_no_set_filter_flag(file);
1744                 else
1745                         event_clear_no_set_filter_flag(file);
1746         }
1747
1748         list_for_each_entry(file, &tr->events, list) {
1749                 struct event_filter *filter;
1750
1751                 if (file->system != dir)
1752                         continue;
1753
1754                 if (event_no_set_filter_flag(file))
1755                         continue;
1756
1757                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1758                 if (!filter_item)
1759                         goto fail_mem;
1760
1761                 list_add_tail(&filter_item->list, &filter_list);
1762
1763                 filter_item->filter = __alloc_filter();
1764                 if (!filter_item->filter)
1765                         goto fail_mem;
1766                 filter = filter_item->filter;
1767
1768                 /* Can only fail on no memory */
1769                 err = replace_filter_string(filter, filter_string);
1770                 if (err)
1771                         goto fail_mem;
1772
1773                 err = replace_preds(file->event_call, filter, ps, false);
1774                 if (err) {
1775                         filter_disable(file);
1776                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1777                         append_filter_err(ps, filter);
1778                 } else
1779                         event_set_filtered_flag(file);
1780                 /*
1781                  * Regardless of if this returned an error, we still
1782                  * replace the filter for the call.
1783                  */
1784                 filter = event_filter(file);
1785                 event_set_filter(file, filter_item->filter);
1786                 filter_item->filter = filter;
1787
1788                 fail = false;
1789         }
1790
1791         if (fail)
1792                 goto fail;
1793
1794         /*
1795          * The calls can still be using the old filters.
1796          * Do a synchronize_sched() to ensure all calls are
1797          * done with them before we free them.
1798          */
1799         synchronize_sched();
1800         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1801                 __free_filter(filter_item->filter);
1802                 list_del(&filter_item->list);
1803                 kfree(filter_item);
1804         }
1805         return 0;
1806  fail:
1807         /* No call succeeded */
1808         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1809                 list_del(&filter_item->list);
1810                 kfree(filter_item);
1811         }
1812         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1813         return -EINVAL;
1814  fail_mem:
1815         /* If any call succeeded, we still need to sync */
1816         if (!fail)
1817                 synchronize_sched();
1818         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1819                 __free_filter(filter_item->filter);
1820                 list_del(&filter_item->list);
1821                 kfree(filter_item);
1822         }
1823         return -ENOMEM;
1824 }
1825
1826 static int create_filter_start(char *filter_str, bool set_str,
1827                                struct filter_parse_state **psp,
1828                                struct event_filter **filterp)
1829 {
1830         struct event_filter *filter;
1831         struct filter_parse_state *ps = NULL;
1832         int err = 0;
1833
1834         WARN_ON_ONCE(*psp || *filterp);
1835
1836         /* allocate everything, and if any fails, free all and fail */
1837         filter = __alloc_filter();
1838         if (filter && set_str)
1839                 err = replace_filter_string(filter, filter_str);
1840
1841         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1842
1843         if (!filter || !ps || err) {
1844                 kfree(ps);
1845                 __free_filter(filter);
1846                 return -ENOMEM;
1847         }
1848
1849         /* we're committed to creating a new filter */
1850         *filterp = filter;
1851         *psp = ps;
1852
1853         parse_init(ps, filter_ops, filter_str);
1854         err = filter_parse(ps);
1855         if (err && set_str)
1856                 append_filter_err(ps, filter);
1857         return err;
1858 }
1859
1860 static void create_filter_finish(struct filter_parse_state *ps)
1861 {
1862         if (ps) {
1863                 filter_opstack_clear(ps);
1864                 postfix_clear(ps);
1865                 kfree(ps);
1866         }
1867 }
1868
1869 /**
1870  * create_filter - create a filter for a ftrace_event_call
1871  * @call: ftrace_event_call to create a filter for
1872  * @filter_str: filter string
1873  * @set_str: remember @filter_str and enable detailed error in filter
1874  * @filterp: out param for created filter (always updated on return)
1875  *
1876  * Creates a filter for @call with @filter_str.  If @set_str is %true,
1877  * @filter_str is copied and recorded in the new filter.
1878  *
1879  * On success, returns 0 and *@filterp points to the new filter.  On
1880  * failure, returns -errno and *@filterp may point to %NULL or to a new
1881  * filter.  In the latter case, the returned filter contains error
1882  * information if @set_str is %true and the caller is responsible for
1883  * freeing it.
1884  */
1885 static int create_filter(struct ftrace_event_call *call,
1886                          char *filter_str, bool set_str,
1887                          struct event_filter **filterp)
1888 {
1889         struct event_filter *filter = NULL;
1890         struct filter_parse_state *ps = NULL;
1891         int err;
1892
1893         err = create_filter_start(filter_str, set_str, &ps, &filter);
1894         if (!err) {
1895                 err = replace_preds(call, filter, ps, false);
1896                 if (err && set_str)
1897                         append_filter_err(ps, filter);
1898         }
1899         create_filter_finish(ps);
1900
1901         *filterp = filter;
1902         return err;
1903 }
1904
1905 int create_event_filter(struct ftrace_event_call *call,
1906                         char *filter_str, bool set_str,
1907                         struct event_filter **filterp)
1908 {
1909         return create_filter(call, filter_str, set_str, filterp);
1910 }
1911
1912 /**
1913  * create_system_filter - create a filter for an event_subsystem
1914  * @system: event_subsystem to create a filter for
1915  * @filter_str: filter string
1916  * @filterp: out param for created filter (always updated on return)
1917  *
1918  * Identical to create_filter() except that it creates a subsystem filter
1919  * and always remembers @filter_str.
1920  */
1921 static int create_system_filter(struct ftrace_subsystem_dir *dir,
1922                                 struct trace_array *tr,
1923                                 char *filter_str, struct event_filter **filterp)
1924 {
1925         struct event_filter *filter = NULL;
1926         struct filter_parse_state *ps = NULL;
1927         int err;
1928
1929         err = create_filter_start(filter_str, true, &ps, &filter);
1930         if (!err) {
1931                 err = replace_system_preds(dir, tr, ps, filter_str);
1932                 if (!err) {
1933                         /* System filters just show a default message */
1934                         kfree(filter->filter_string);
1935                         filter->filter_string = NULL;
1936                 } else {
1937                         append_filter_err(ps, filter);
1938                 }
1939         }
1940         create_filter_finish(ps);
1941
1942         *filterp = filter;
1943         return err;
1944 }
1945
1946 /* caller must hold event_mutex */
1947 int apply_event_filter(struct ftrace_event_file *file, char *filter_string)
1948 {
1949         struct ftrace_event_call *call = file->event_call;
1950         struct event_filter *filter;
1951         int err;
1952
1953         if (!strcmp(strstrip(filter_string), "0")) {
1954                 filter_disable(file);
1955                 filter = event_filter(file);
1956
1957                 if (!filter)
1958                         return 0;
1959
1960                 event_clear_filter(file);
1961
1962                 /* Make sure the filter is not being used */
1963                 synchronize_sched();
1964                 __free_filter(filter);
1965
1966                 return 0;
1967         }
1968
1969         err = create_filter(call, filter_string, true, &filter);
1970
1971         /*
1972          * Always swap the call filter with the new filter
1973          * even if there was an error. If there was an error
1974          * in the filter, we disable the filter and show the error
1975          * string
1976          */
1977         if (filter) {
1978                 struct event_filter *tmp;
1979
1980                 tmp = event_filter(file);
1981                 if (!err)
1982                         event_set_filtered_flag(file);
1983                 else
1984                         filter_disable(file);
1985
1986                 event_set_filter(file, filter);
1987
1988                 if (tmp) {
1989                         /* Make sure the call is done with the filter */
1990                         synchronize_sched();
1991                         __free_filter(tmp);
1992                 }
1993         }
1994
1995         return err;
1996 }
1997
1998 int apply_subsystem_event_filter(struct ftrace_subsystem_dir *dir,
1999                                  char *filter_string)
2000 {
2001         struct event_subsystem *system = dir->subsystem;
2002         struct trace_array *tr = dir->tr;
2003         struct event_filter *filter;
2004         int err = 0;
2005
2006         mutex_lock(&event_mutex);
2007
2008         /* Make sure the system still has events */
2009         if (!dir->nr_events) {
2010                 err = -ENODEV;
2011                 goto out_unlock;
2012         }
2013
2014         if (!strcmp(strstrip(filter_string), "0")) {
2015                 filter_free_subsystem_preds(dir, tr);
2016                 remove_filter_string(system->filter);
2017                 filter = system->filter;
2018                 system->filter = NULL;
2019                 /* Ensure all filters are no longer used */
2020                 synchronize_sched();
2021                 filter_free_subsystem_filters(dir, tr);
2022                 __free_filter(filter);
2023                 goto out_unlock;
2024         }
2025
2026         err = create_system_filter(dir, tr, filter_string, &filter);
2027         if (filter) {
2028                 /*
2029                  * No event actually uses the system filter
2030                  * we can free it without synchronize_sched().
2031                  */
2032                 __free_filter(system->filter);
2033                 system->filter = filter;
2034         }
2035 out_unlock:
2036         mutex_unlock(&event_mutex);
2037
2038         return err;
2039 }
2040
2041 #ifdef CONFIG_PERF_EVENTS
2042
2043 void ftrace_profile_free_filter(struct perf_event *event)
2044 {
2045         struct event_filter *filter = event->filter;
2046
2047         event->filter = NULL;
2048         __free_filter(filter);
2049 }
2050
2051 struct function_filter_data {
2052         struct ftrace_ops *ops;
2053         int first_filter;
2054         int first_notrace;
2055 };
2056
2057 #ifdef CONFIG_FUNCTION_TRACER
2058 static char **
2059 ftrace_function_filter_re(char *buf, int len, int *count)
2060 {
2061         char *str, *sep, **re;
2062
2063         str = kstrndup(buf, len, GFP_KERNEL);
2064         if (!str)
2065                 return NULL;
2066
2067         /*
2068          * The argv_split function takes white space
2069          * as a separator, so convert ',' into spaces.
2070          */
2071         while ((sep = strchr(str, ',')))
2072                 *sep = ' ';
2073
2074         re = argv_split(GFP_KERNEL, str, count);
2075         kfree(str);
2076         return re;
2077 }
2078
2079 static int ftrace_function_set_regexp(struct ftrace_ops *ops, int filter,
2080                                       int reset, char *re, int len)
2081 {
2082         int ret;
2083
2084         if (filter)
2085                 ret = ftrace_set_filter(ops, re, len, reset);
2086         else
2087                 ret = ftrace_set_notrace(ops, re, len, reset);
2088
2089         return ret;
2090 }
2091
2092 static int __ftrace_function_set_filter(int filter, char *buf, int len,
2093                                         struct function_filter_data *data)
2094 {
2095         int i, re_cnt, ret = -EINVAL;
2096         int *reset;
2097         char **re;
2098
2099         reset = filter ? &data->first_filter : &data->first_notrace;
2100
2101         /*
2102          * The 'ip' field could have multiple filters set, separated
2103          * either by space or comma. We first cut the filter and apply
2104          * all pieces separatelly.
2105          */
2106         re = ftrace_function_filter_re(buf, len, &re_cnt);
2107         if (!re)
2108                 return -EINVAL;
2109
2110         for (i = 0; i < re_cnt; i++) {
2111                 ret = ftrace_function_set_regexp(data->ops, filter, *reset,
2112                                                  re[i], strlen(re[i]));
2113                 if (ret)
2114                         break;
2115
2116                 if (*reset)
2117                         *reset = 0;
2118         }
2119
2120         argv_free(re);
2121         return ret;
2122 }
2123
2124 static int ftrace_function_check_pred(struct filter_pred *pred, int leaf)
2125 {
2126         struct ftrace_event_field *field = pred->field;
2127
2128         if (leaf) {
2129                 /*
2130                  * Check the leaf predicate for function trace, verify:
2131                  *  - only '==' and '!=' is used
2132                  *  - the 'ip' field is used
2133                  */
2134                 if ((pred->op != OP_EQ) && (pred->op != OP_NE))
2135                         return -EINVAL;
2136
2137                 if (strcmp(field->name, "ip"))
2138                         return -EINVAL;
2139         } else {
2140                 /*
2141                  * Check the non leaf predicate for function trace, verify:
2142                  *  - only '||' is used
2143                 */
2144                 if (pred->op != OP_OR)
2145                         return -EINVAL;
2146         }
2147
2148         return 0;
2149 }
2150
2151 static int ftrace_function_set_filter_cb(enum move_type move,
2152                                          struct filter_pred *pred,
2153                                          int *err, void *data)
2154 {
2155         /* Checking the node is valid for function trace. */
2156         if ((move != MOVE_DOWN) ||
2157             (pred->left != FILTER_PRED_INVALID)) {
2158                 *err = ftrace_function_check_pred(pred, 0);
2159         } else {
2160                 *err = ftrace_function_check_pred(pred, 1);
2161                 if (*err)
2162                         return WALK_PRED_ABORT;
2163
2164                 *err = __ftrace_function_set_filter(pred->op == OP_EQ,
2165                                                     pred->regex.pattern,
2166                                                     pred->regex.len,
2167                                                     data);
2168         }
2169
2170         return (*err) ? WALK_PRED_ABORT : WALK_PRED_DEFAULT;
2171 }
2172
2173 static int ftrace_function_set_filter(struct perf_event *event,
2174                                       struct event_filter *filter)
2175 {
2176         struct function_filter_data data = {
2177                 .first_filter  = 1,
2178                 .first_notrace = 1,
2179                 .ops           = &event->ftrace_ops,
2180         };
2181
2182         return walk_pred_tree(filter->preds, filter->root,
2183                               ftrace_function_set_filter_cb, &data);
2184 }
2185 #else
2186 static int ftrace_function_set_filter(struct perf_event *event,
2187                                       struct event_filter *filter)
2188 {
2189         return -ENODEV;
2190 }
2191 #endif /* CONFIG_FUNCTION_TRACER */
2192
2193 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
2194                               char *filter_str)
2195 {
2196         int err;
2197         struct event_filter *filter;
2198         struct ftrace_event_call *call;
2199
2200         mutex_lock(&event_mutex);
2201
2202         call = event->tp_event;
2203
2204         err = -EINVAL;
2205         if (!call)
2206                 goto out_unlock;
2207
2208         err = -EEXIST;
2209         if (event->filter)
2210                 goto out_unlock;
2211
2212         err = create_filter(call, filter_str, false, &filter);
2213         if (err)
2214                 goto free_filter;
2215
2216         if (ftrace_event_is_function(call))
2217                 err = ftrace_function_set_filter(event, filter);
2218         else
2219                 event->filter = filter;
2220
2221 free_filter:
2222         if (err || ftrace_event_is_function(call))
2223                 __free_filter(filter);
2224
2225 out_unlock:
2226         mutex_unlock(&event_mutex);
2227
2228         return err;
2229 }
2230
2231 #endif /* CONFIG_PERF_EVENTS */
2232
2233 #ifdef CONFIG_FTRACE_STARTUP_TEST
2234
2235 #include <linux/types.h>
2236 #include <linux/tracepoint.h>
2237
2238 #define CREATE_TRACE_POINTS
2239 #include "trace_events_filter_test.h"
2240
2241 #define DATA_REC(m, va, vb, vc, vd, ve, vf, vg, vh, nvisit) \
2242 { \
2243         .filter = FILTER, \
2244         .rec    = { .a = va, .b = vb, .c = vc, .d = vd, \
2245                     .e = ve, .f = vf, .g = vg, .h = vh }, \
2246         .match  = m, \
2247         .not_visited = nvisit, \
2248 }
2249 #define YES 1
2250 #define NO  0
2251
2252 static struct test_filter_data_t {
2253         char *filter;
2254         struct ftrace_raw_ftrace_test_filter rec;
2255         int match;
2256         char *not_visited;
2257 } test_filter_data[] = {
2258 #define FILTER "a == 1 && b == 1 && c == 1 && d == 1 && " \
2259                "e == 1 && f == 1 && g == 1 && h == 1"
2260         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, ""),
2261         DATA_REC(NO,  0, 1, 1, 1, 1, 1, 1, 1, "bcdefgh"),
2262         DATA_REC(NO,  1, 1, 1, 1, 1, 1, 1, 0, ""),
2263 #undef FILTER
2264 #define FILTER "a == 1 || b == 1 || c == 1 || d == 1 || " \
2265                "e == 1 || f == 1 || g == 1 || h == 1"
2266         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2267         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 0, 1, ""),
2268         DATA_REC(YES, 1, 0, 0, 0, 0, 0, 0, 0, "bcdefgh"),
2269 #undef FILTER
2270 #define FILTER "(a == 1 || b == 1) && (c == 1 || d == 1) && " \
2271                "(e == 1 || f == 1) && (g == 1 || h == 1)"
2272         DATA_REC(NO,  0, 0, 1, 1, 1, 1, 1, 1, "dfh"),
2273         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2274         DATA_REC(YES, 1, 0, 1, 0, 0, 1, 0, 1, "bd"),
2275         DATA_REC(NO,  1, 0, 1, 0, 0, 1, 0, 0, "bd"),
2276 #undef FILTER
2277 #define FILTER "(a == 1 && b == 1) || (c == 1 && d == 1) || " \
2278                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2279         DATA_REC(YES, 1, 0, 1, 1, 1, 1, 1, 1, "efgh"),
2280         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 1, 1, ""),
2281         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2282 #undef FILTER
2283 #define FILTER "(a == 1 && b == 1) && (c == 1 && d == 1) && " \
2284                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2285         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 0, "gh"),
2286         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2287         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, ""),
2288 #undef FILTER
2289 #define FILTER "((a == 1 || b == 1) || (c == 1 || d == 1) || " \
2290                "(e == 1 || f == 1)) && (g == 1 || h == 1)"
2291         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 1, "bcdef"),
2292         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2293         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, "h"),
2294 #undef FILTER
2295 #define FILTER "((((((((a == 1) && (b == 1)) || (c == 1)) && (d == 1)) || " \
2296                "(e == 1)) && (f == 1)) || (g == 1)) && (h == 1))"
2297         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "ceg"),
2298         DATA_REC(NO,  0, 1, 0, 1, 0, 1, 0, 1, ""),
2299         DATA_REC(NO,  1, 0, 1, 0, 1, 0, 1, 0, ""),
2300 #undef FILTER
2301 #define FILTER "((((((((a == 1) || (b == 1)) && (c == 1)) || (d == 1)) && " \
2302                "(e == 1)) || (f == 1)) && (g == 1)) || (h == 1))"
2303         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "bdfh"),
2304         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2305         DATA_REC(YES, 1, 0, 1, 0, 1, 0, 1, 0, "bdfh"),
2306 };
2307
2308 #undef DATA_REC
2309 #undef FILTER
2310 #undef YES
2311 #undef NO
2312
2313 #define DATA_CNT (sizeof(test_filter_data)/sizeof(struct test_filter_data_t))
2314
2315 static int test_pred_visited;
2316
2317 static int test_pred_visited_fn(struct filter_pred *pred, void *event)
2318 {
2319         struct ftrace_event_field *field = pred->field;
2320
2321         test_pred_visited = 1;
2322         printk(KERN_INFO "\npred visited %s\n", field->name);
2323         return 1;
2324 }
2325
2326 static int test_walk_pred_cb(enum move_type move, struct filter_pred *pred,
2327                              int *err, void *data)
2328 {
2329         char *fields = data;
2330
2331         if ((move == MOVE_DOWN) &&
2332             (pred->left == FILTER_PRED_INVALID)) {
2333                 struct ftrace_event_field *field = pred->field;
2334
2335                 if (!field) {
2336                         WARN(1, "all leafs should have field defined");
2337                         return WALK_PRED_DEFAULT;
2338                 }
2339                 if (!strchr(fields, *field->name))
2340                         return WALK_PRED_DEFAULT;
2341
2342                 WARN_ON(!pred->fn);
2343                 pred->fn = test_pred_visited_fn;
2344         }
2345         return WALK_PRED_DEFAULT;
2346 }
2347
2348 static __init int ftrace_test_event_filter(void)
2349 {
2350         int i;
2351
2352         printk(KERN_INFO "Testing ftrace filter: ");
2353
2354         for (i = 0; i < DATA_CNT; i++) {
2355                 struct event_filter *filter = NULL;
2356                 struct test_filter_data_t *d = &test_filter_data[i];
2357                 int err;
2358
2359                 err = create_filter(&event_ftrace_test_filter, d->filter,
2360                                     false, &filter);
2361                 if (err) {
2362                         printk(KERN_INFO
2363                                "Failed to get filter for '%s', err %d\n",
2364                                d->filter, err);
2365                         __free_filter(filter);
2366                         break;
2367                 }
2368
2369                 /*
2370                  * The preemption disabling is not really needed for self
2371                  * tests, but the rcu dereference will complain without it.
2372                  */
2373                 preempt_disable();
2374                 if (*d->not_visited)
2375                         walk_pred_tree(filter->preds, filter->root,
2376                                        test_walk_pred_cb,
2377                                        d->not_visited);
2378
2379                 test_pred_visited = 0;
2380                 err = filter_match_preds(filter, &d->rec);
2381                 preempt_enable();
2382
2383                 __free_filter(filter);
2384
2385                 if (test_pred_visited) {
2386                         printk(KERN_INFO
2387                                "Failed, unwanted pred visited for filter %s\n",
2388                                d->filter);
2389                         break;
2390                 }
2391
2392                 if (err != d->match) {
2393                         printk(KERN_INFO
2394                                "Failed to match filter '%s', expected %d\n",
2395                                d->filter, d->match);
2396                         break;
2397                 }
2398         }
2399
2400         if (i == DATA_CNT)
2401                 printk(KERN_CONT "OK\n");
2402
2403         return 0;
2404 }
2405
2406 late_initcall(ftrace_test_event_filter);
2407
2408 #endif /* CONFIG_FTRACE_STARTUP_TEST */