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         if (!ps->infix.cnt)
1054                 return 0;
1055
1056         ps->infix.cnt--;
1057
1058         return ps->infix.string[ps->infix.tail++];
1059 }
1060
1061 static char infix_peek(struct filter_parse_state *ps)
1062 {
1063         if (ps->infix.tail == strlen(ps->infix.string))
1064                 return 0;
1065
1066         return ps->infix.string[ps->infix.tail];
1067 }
1068
1069 static void infix_advance(struct filter_parse_state *ps)
1070 {
1071         if (!ps->infix.cnt)
1072                 return;
1073
1074         ps->infix.cnt--;
1075         ps->infix.tail++;
1076 }
1077
1078 static inline int is_precedence_lower(struct filter_parse_state *ps,
1079                                       int a, int b)
1080 {
1081         return ps->ops[a].precedence < ps->ops[b].precedence;
1082 }
1083
1084 static inline int is_op_char(struct filter_parse_state *ps, char c)
1085 {
1086         int i;
1087
1088         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1089                 if (ps->ops[i].string[0] == c)
1090                         return 1;
1091         }
1092
1093         return 0;
1094 }
1095
1096 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1097 {
1098         char nextc = infix_peek(ps);
1099         char opstr[3];
1100         int i;
1101
1102         opstr[0] = firstc;
1103         opstr[1] = nextc;
1104         opstr[2] = '\0';
1105
1106         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1107                 if (!strcmp(opstr, ps->ops[i].string)) {
1108                         infix_advance(ps);
1109                         return ps->ops[i].id;
1110                 }
1111         }
1112
1113         opstr[1] = '\0';
1114
1115         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1116                 if (!strcmp(opstr, ps->ops[i].string))
1117                         return ps->ops[i].id;
1118         }
1119
1120         return OP_NONE;
1121 }
1122
1123 static inline void clear_operand_string(struct filter_parse_state *ps)
1124 {
1125         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1126         ps->operand.tail = 0;
1127 }
1128
1129 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1130 {
1131         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1132                 return -EINVAL;
1133
1134         ps->operand.string[ps->operand.tail++] = c;
1135
1136         return 0;
1137 }
1138
1139 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1140 {
1141         struct opstack_op *opstack_op;
1142
1143         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1144         if (!opstack_op)
1145                 return -ENOMEM;
1146
1147         opstack_op->op = op;
1148         list_add(&opstack_op->list, &ps->opstack);
1149
1150         return 0;
1151 }
1152
1153 static int filter_opstack_empty(struct filter_parse_state *ps)
1154 {
1155         return list_empty(&ps->opstack);
1156 }
1157
1158 static int filter_opstack_top(struct filter_parse_state *ps)
1159 {
1160         struct opstack_op *opstack_op;
1161
1162         if (filter_opstack_empty(ps))
1163                 return OP_NONE;
1164
1165         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1166
1167         return opstack_op->op;
1168 }
1169
1170 static int filter_opstack_pop(struct filter_parse_state *ps)
1171 {
1172         struct opstack_op *opstack_op;
1173         int op;
1174
1175         if (filter_opstack_empty(ps))
1176                 return OP_NONE;
1177
1178         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1179         op = opstack_op->op;
1180         list_del(&opstack_op->list);
1181
1182         kfree(opstack_op);
1183
1184         return op;
1185 }
1186
1187 static void filter_opstack_clear(struct filter_parse_state *ps)
1188 {
1189         while (!filter_opstack_empty(ps))
1190                 filter_opstack_pop(ps);
1191 }
1192
1193 static char *curr_operand(struct filter_parse_state *ps)
1194 {
1195         return ps->operand.string;
1196 }
1197
1198 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1199 {
1200         struct postfix_elt *elt;
1201
1202         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1203         if (!elt)
1204                 return -ENOMEM;
1205
1206         elt->op = OP_NONE;
1207         elt->operand = kstrdup(operand, GFP_KERNEL);
1208         if (!elt->operand) {
1209                 kfree(elt);
1210                 return -ENOMEM;
1211         }
1212
1213         list_add_tail(&elt->list, &ps->postfix);
1214
1215         return 0;
1216 }
1217
1218 static int postfix_append_op(struct filter_parse_state *ps, int op)
1219 {
1220         struct postfix_elt *elt;
1221
1222         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1223         if (!elt)
1224                 return -ENOMEM;
1225
1226         elt->op = op;
1227         elt->operand = NULL;
1228
1229         list_add_tail(&elt->list, &ps->postfix);
1230
1231         return 0;
1232 }
1233
1234 static void postfix_clear(struct filter_parse_state *ps)
1235 {
1236         struct postfix_elt *elt;
1237
1238         while (!list_empty(&ps->postfix)) {
1239                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1240                 list_del(&elt->list);
1241                 kfree(elt->operand);
1242                 kfree(elt);
1243         }
1244 }
1245
1246 static int filter_parse(struct filter_parse_state *ps)
1247 {
1248         int in_string = 0;
1249         int op, top_op;
1250         char ch;
1251
1252         while ((ch = infix_next(ps))) {
1253                 if (ch == '"') {
1254                         in_string ^= 1;
1255                         continue;
1256                 }
1257
1258                 if (in_string)
1259                         goto parse_operand;
1260
1261                 if (isspace(ch))
1262                         continue;
1263
1264                 if (is_op_char(ps, ch)) {
1265                         op = infix_get_op(ps, ch);
1266                         if (op == OP_NONE) {
1267                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1268                                 return -EINVAL;
1269                         }
1270
1271                         if (strlen(curr_operand(ps))) {
1272                                 postfix_append_operand(ps, curr_operand(ps));
1273                                 clear_operand_string(ps);
1274                         }
1275
1276                         while (!filter_opstack_empty(ps)) {
1277                                 top_op = filter_opstack_top(ps);
1278                                 if (!is_precedence_lower(ps, top_op, op)) {
1279                                         top_op = filter_opstack_pop(ps);
1280                                         postfix_append_op(ps, top_op);
1281                                         continue;
1282                                 }
1283                                 break;
1284                         }
1285
1286                         filter_opstack_push(ps, op);
1287                         continue;
1288                 }
1289
1290                 if (ch == '(') {
1291                         filter_opstack_push(ps, OP_OPEN_PAREN);
1292                         continue;
1293                 }
1294
1295                 if (ch == ')') {
1296                         if (strlen(curr_operand(ps))) {
1297                                 postfix_append_operand(ps, curr_operand(ps));
1298                                 clear_operand_string(ps);
1299                         }
1300
1301                         top_op = filter_opstack_pop(ps);
1302                         while (top_op != OP_NONE) {
1303                                 if (top_op == OP_OPEN_PAREN)
1304                                         break;
1305                                 postfix_append_op(ps, top_op);
1306                                 top_op = filter_opstack_pop(ps);
1307                         }
1308                         if (top_op == OP_NONE) {
1309                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1310                                 return -EINVAL;
1311                         }
1312                         continue;
1313                 }
1314 parse_operand:
1315                 if (append_operand_char(ps, ch)) {
1316                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1317                         return -EINVAL;
1318                 }
1319         }
1320
1321         if (strlen(curr_operand(ps)))
1322                 postfix_append_operand(ps, curr_operand(ps));
1323
1324         while (!filter_opstack_empty(ps)) {
1325                 top_op = filter_opstack_pop(ps);
1326                 if (top_op == OP_NONE)
1327                         break;
1328                 if (top_op == OP_OPEN_PAREN) {
1329                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1330                         return -EINVAL;
1331                 }
1332                 postfix_append_op(ps, top_op);
1333         }
1334
1335         return 0;
1336 }
1337
1338 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1339                                        struct ftrace_event_call *call,
1340                                        int op, char *operand1, char *operand2)
1341 {
1342         struct ftrace_event_field *field;
1343         static struct filter_pred pred;
1344
1345         memset(&pred, 0, sizeof(pred));
1346         pred.op = op;
1347
1348         if (op == OP_AND || op == OP_OR)
1349                 return &pred;
1350
1351         if (!operand1 || !operand2) {
1352                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1353                 return NULL;
1354         }
1355
1356         field = trace_find_event_field(call, operand1);
1357         if (!field) {
1358                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1359                 return NULL;
1360         }
1361
1362         strcpy(pred.regex.pattern, operand2);
1363         pred.regex.len = strlen(pred.regex.pattern);
1364         pred.field = field;
1365         return init_pred(ps, field, &pred) ? NULL : &pred;
1366 }
1367
1368 static int check_preds(struct filter_parse_state *ps)
1369 {
1370         int n_normal_preds = 0, n_logical_preds = 0;
1371         struct postfix_elt *elt;
1372         int cnt = 0;
1373
1374         list_for_each_entry(elt, &ps->postfix, list) {
1375                 if (elt->op == OP_NONE) {
1376                         cnt++;
1377                         continue;
1378                 }
1379
1380                 cnt--;
1381                 if (elt->op == OP_AND || elt->op == OP_OR) {
1382                         n_logical_preds++;
1383                         continue;
1384                 }
1385                 n_normal_preds++;
1386                 /* all ops should have operands */
1387                 if (cnt < 0)
1388                         break;
1389         }
1390
1391         if (cnt != 1 || !n_normal_preds || n_logical_preds >= n_normal_preds) {
1392                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1393                 return -EINVAL;
1394         }
1395
1396         return 0;
1397 }
1398
1399 static int count_preds(struct filter_parse_state *ps)
1400 {
1401         struct postfix_elt *elt;
1402         int n_preds = 0;
1403
1404         list_for_each_entry(elt, &ps->postfix, list) {
1405                 if (elt->op == OP_NONE)
1406                         continue;
1407                 n_preds++;
1408         }
1409
1410         return n_preds;
1411 }
1412
1413 struct check_pred_data {
1414         int count;
1415         int max;
1416 };
1417
1418 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1419                               int *err, void *data)
1420 {
1421         struct check_pred_data *d = data;
1422
1423         if (WARN_ON(d->count++ > d->max)) {
1424                 *err = -EINVAL;
1425                 return WALK_PRED_ABORT;
1426         }
1427         return WALK_PRED_DEFAULT;
1428 }
1429
1430 /*
1431  * The tree is walked at filtering of an event. If the tree is not correctly
1432  * built, it may cause an infinite loop. Check here that the tree does
1433  * indeed terminate.
1434  */
1435 static int check_pred_tree(struct event_filter *filter,
1436                            struct filter_pred *root)
1437 {
1438         struct check_pred_data data = {
1439                 /*
1440                  * The max that we can hit a node is three times.
1441                  * Once going down, once coming up from left, and
1442                  * once coming up from right. This is more than enough
1443                  * since leafs are only hit a single time.
1444                  */
1445                 .max   = 3 * filter->n_preds,
1446                 .count = 0,
1447         };
1448
1449         return walk_pred_tree(filter->preds, root,
1450                               check_pred_tree_cb, &data);
1451 }
1452
1453 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1454                           int *err, void *data)
1455 {
1456         int *count = data;
1457
1458         if ((move == MOVE_DOWN) &&
1459             (pred->left == FILTER_PRED_INVALID))
1460                 (*count)++;
1461
1462         return WALK_PRED_DEFAULT;
1463 }
1464
1465 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1466 {
1467         int count = 0, ret;
1468
1469         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1470         WARN_ON(ret);
1471         return count;
1472 }
1473
1474 struct fold_pred_data {
1475         struct filter_pred *root;
1476         int count;
1477         int children;
1478 };
1479
1480 static int fold_pred_cb(enum move_type move, struct filter_pred *pred,
1481                         int *err, void *data)
1482 {
1483         struct fold_pred_data *d = data;
1484         struct filter_pred *root = d->root;
1485
1486         if (move != MOVE_DOWN)
1487                 return WALK_PRED_DEFAULT;
1488         if (pred->left != FILTER_PRED_INVALID)
1489                 return WALK_PRED_DEFAULT;
1490
1491         if (WARN_ON(d->count == d->children)) {
1492                 *err = -EINVAL;
1493                 return WALK_PRED_ABORT;
1494         }
1495
1496         pred->index &= ~FILTER_PRED_FOLD;
1497         root->ops[d->count++] = pred->index;
1498         return WALK_PRED_DEFAULT;
1499 }
1500
1501 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1502 {
1503         struct fold_pred_data data = {
1504                 .root  = root,
1505                 .count = 0,
1506         };
1507         int children;
1508
1509         /* No need to keep the fold flag */
1510         root->index &= ~FILTER_PRED_FOLD;
1511
1512         /* If the root is a leaf then do nothing */
1513         if (root->left == FILTER_PRED_INVALID)
1514                 return 0;
1515
1516         /* count the children */
1517         children = count_leafs(preds, &preds[root->left]);
1518         children += count_leafs(preds, &preds[root->right]);
1519
1520         root->ops = kcalloc(children, sizeof(*root->ops), GFP_KERNEL);
1521         if (!root->ops)
1522                 return -ENOMEM;
1523
1524         root->val = children;
1525         data.children = children;
1526         return walk_pred_tree(preds, root, fold_pred_cb, &data);
1527 }
1528
1529 static int fold_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1530                              int *err, void *data)
1531 {
1532         struct filter_pred *preds = data;
1533
1534         if (move != MOVE_DOWN)
1535                 return WALK_PRED_DEFAULT;
1536         if (!(pred->index & FILTER_PRED_FOLD))
1537                 return WALK_PRED_DEFAULT;
1538
1539         *err = fold_pred(preds, pred);
1540         if (*err)
1541                 return WALK_PRED_ABORT;
1542
1543         /* eveyrhing below is folded, continue with parent */
1544         return WALK_PRED_PARENT;
1545 }
1546
1547 /*
1548  * To optimize the processing of the ops, if we have several "ors" or
1549  * "ands" together, we can put them in an array and process them all
1550  * together speeding up the filter logic.
1551  */
1552 static int fold_pred_tree(struct event_filter *filter,
1553                            struct filter_pred *root)
1554 {
1555         return walk_pred_tree(filter->preds, root, fold_pred_tree_cb,
1556                               filter->preds);
1557 }
1558
1559 static int replace_preds(struct ftrace_event_call *call,
1560                          struct event_filter *filter,
1561                          struct filter_parse_state *ps,
1562                          bool dry_run)
1563 {
1564         char *operand1 = NULL, *operand2 = NULL;
1565         struct filter_pred *pred;
1566         struct filter_pred *root;
1567         struct postfix_elt *elt;
1568         struct pred_stack stack = { }; /* init to NULL */
1569         int err;
1570         int n_preds = 0;
1571
1572         n_preds = count_preds(ps);
1573         if (n_preds >= MAX_FILTER_PRED) {
1574                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1575                 return -ENOSPC;
1576         }
1577
1578         err = check_preds(ps);
1579         if (err)
1580                 return err;
1581
1582         if (!dry_run) {
1583                 err = __alloc_pred_stack(&stack, n_preds);
1584                 if (err)
1585                         return err;
1586                 err = __alloc_preds(filter, n_preds);
1587                 if (err)
1588                         goto fail;
1589         }
1590
1591         n_preds = 0;
1592         list_for_each_entry(elt, &ps->postfix, list) {
1593                 if (elt->op == OP_NONE) {
1594                         if (!operand1)
1595                                 operand1 = elt->operand;
1596                         else if (!operand2)
1597                                 operand2 = elt->operand;
1598                         else {
1599                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1600                                 err = -EINVAL;
1601                                 goto fail;
1602                         }
1603                         continue;
1604                 }
1605
1606                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1607                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1608                         err = -ENOSPC;
1609                         goto fail;
1610                 }
1611
1612                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1613                 if (!pred) {
1614                         err = -EINVAL;
1615                         goto fail;
1616                 }
1617
1618                 if (!dry_run) {
1619                         err = filter_add_pred(ps, filter, pred, &stack);
1620                         if (err)
1621                                 goto fail;
1622                 }
1623
1624                 operand1 = operand2 = NULL;
1625         }
1626
1627         if (!dry_run) {
1628                 /* We should have one item left on the stack */
1629                 pred = __pop_pred_stack(&stack);
1630                 if (!pred)
1631                         return -EINVAL;
1632                 /* This item is where we start from in matching */
1633                 root = pred;
1634                 /* Make sure the stack is empty */
1635                 pred = __pop_pred_stack(&stack);
1636                 if (WARN_ON(pred)) {
1637                         err = -EINVAL;
1638                         filter->root = NULL;
1639                         goto fail;
1640                 }
1641                 err = check_pred_tree(filter, root);
1642                 if (err)
1643                         goto fail;
1644
1645                 /* Optimize the tree */
1646                 err = fold_pred_tree(filter, root);
1647                 if (err)
1648                         goto fail;
1649
1650                 /* We don't set root until we know it works */
1651                 barrier();
1652                 filter->root = root;
1653         }
1654
1655         err = 0;
1656 fail:
1657         __free_pred_stack(&stack);
1658         return err;
1659 }
1660
1661 static inline void event_set_filtered_flag(struct ftrace_event_file *file)
1662 {
1663         struct ftrace_event_call *call = file->event_call;
1664
1665         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1666                 call->flags |= TRACE_EVENT_FL_FILTERED;
1667         else
1668                 file->flags |= FTRACE_EVENT_FL_FILTERED;
1669 }
1670
1671 static inline void event_set_filter(struct ftrace_event_file *file,
1672                                     struct event_filter *filter)
1673 {
1674         struct ftrace_event_call *call = file->event_call;
1675
1676         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1677                 rcu_assign_pointer(call->filter, filter);
1678         else
1679                 rcu_assign_pointer(file->filter, filter);
1680 }
1681
1682 static inline void event_clear_filter(struct ftrace_event_file *file)
1683 {
1684         struct ftrace_event_call *call = file->event_call;
1685
1686         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1687                 RCU_INIT_POINTER(call->filter, NULL);
1688         else
1689                 RCU_INIT_POINTER(file->filter, NULL);
1690 }
1691
1692 static inline void
1693 event_set_no_set_filter_flag(struct ftrace_event_file *file)
1694 {
1695         struct ftrace_event_call *call = file->event_call;
1696
1697         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1698                 call->flags |= TRACE_EVENT_FL_NO_SET_FILTER;
1699         else
1700                 file->flags |= FTRACE_EVENT_FL_NO_SET_FILTER;
1701 }
1702
1703 static inline void
1704 event_clear_no_set_filter_flag(struct ftrace_event_file *file)
1705 {
1706         struct ftrace_event_call *call = file->event_call;
1707
1708         if (call->flags & TRACE_EVENT_FL_USE_CALL_FILTER)
1709                 call->flags &= ~TRACE_EVENT_FL_NO_SET_FILTER;
1710         else
1711                 file->flags &= ~FTRACE_EVENT_FL_NO_SET_FILTER;
1712 }
1713
1714 static inline bool
1715 event_no_set_filter_flag(struct ftrace_event_file *file)
1716 {
1717         struct ftrace_event_call *call = file->event_call;
1718
1719         if (file->flags & FTRACE_EVENT_FL_NO_SET_FILTER)
1720                 return true;
1721
1722         if ((call->flags & TRACE_EVENT_FL_USE_CALL_FILTER) &&
1723             (call->flags & TRACE_EVENT_FL_NO_SET_FILTER))
1724                 return true;
1725
1726         return false;
1727 }
1728
1729 struct filter_list {
1730         struct list_head        list;
1731         struct event_filter     *filter;
1732 };
1733
1734 static int replace_system_preds(struct ftrace_subsystem_dir *dir,
1735                                 struct trace_array *tr,
1736                                 struct filter_parse_state *ps,
1737                                 char *filter_string)
1738 {
1739         struct ftrace_event_file *file;
1740         struct filter_list *filter_item;
1741         struct filter_list *tmp;
1742         LIST_HEAD(filter_list);
1743         bool fail = true;
1744         int err;
1745
1746         list_for_each_entry(file, &tr->events, list) {
1747                 if (file->system != dir)
1748                         continue;
1749
1750                 /*
1751                  * Try to see if the filter can be applied
1752                  *  (filter arg is ignored on dry_run)
1753                  */
1754                 err = replace_preds(file->event_call, NULL, ps, true);
1755                 if (err)
1756                         event_set_no_set_filter_flag(file);
1757                 else
1758                         event_clear_no_set_filter_flag(file);
1759         }
1760
1761         list_for_each_entry(file, &tr->events, list) {
1762                 struct event_filter *filter;
1763
1764                 if (file->system != dir)
1765                         continue;
1766
1767                 if (event_no_set_filter_flag(file))
1768                         continue;
1769
1770                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1771                 if (!filter_item)
1772                         goto fail_mem;
1773
1774                 list_add_tail(&filter_item->list, &filter_list);
1775
1776                 filter_item->filter = __alloc_filter();
1777                 if (!filter_item->filter)
1778                         goto fail_mem;
1779                 filter = filter_item->filter;
1780
1781                 /* Can only fail on no memory */
1782                 err = replace_filter_string(filter, filter_string);
1783                 if (err)
1784                         goto fail_mem;
1785
1786                 err = replace_preds(file->event_call, filter, ps, false);
1787                 if (err) {
1788                         filter_disable(file);
1789                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1790                         append_filter_err(ps, filter);
1791                 } else
1792                         event_set_filtered_flag(file);
1793                 /*
1794                  * Regardless of if this returned an error, we still
1795                  * replace the filter for the call.
1796                  */
1797                 filter = event_filter(file);
1798                 event_set_filter(file, filter_item->filter);
1799                 filter_item->filter = filter;
1800
1801                 fail = false;
1802         }
1803
1804         if (fail)
1805                 goto fail;
1806
1807         /*
1808          * The calls can still be using the old filters.
1809          * Do a synchronize_sched() to ensure all calls are
1810          * done with them before we free them.
1811          */
1812         synchronize_sched();
1813         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1814                 __free_filter(filter_item->filter);
1815                 list_del(&filter_item->list);
1816                 kfree(filter_item);
1817         }
1818         return 0;
1819  fail:
1820         /* No call succeeded */
1821         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1822                 list_del(&filter_item->list);
1823                 kfree(filter_item);
1824         }
1825         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1826         return -EINVAL;
1827  fail_mem:
1828         /* If any call succeeded, we still need to sync */
1829         if (!fail)
1830                 synchronize_sched();
1831         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1832                 __free_filter(filter_item->filter);
1833                 list_del(&filter_item->list);
1834                 kfree(filter_item);
1835         }
1836         return -ENOMEM;
1837 }
1838
1839 static int create_filter_start(char *filter_str, bool set_str,
1840                                struct filter_parse_state **psp,
1841                                struct event_filter **filterp)
1842 {
1843         struct event_filter *filter;
1844         struct filter_parse_state *ps = NULL;
1845         int err = 0;
1846
1847         WARN_ON_ONCE(*psp || *filterp);
1848
1849         /* allocate everything, and if any fails, free all and fail */
1850         filter = __alloc_filter();
1851         if (filter && set_str)
1852                 err = replace_filter_string(filter, filter_str);
1853
1854         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1855
1856         if (!filter || !ps || err) {
1857                 kfree(ps);
1858                 __free_filter(filter);
1859                 return -ENOMEM;
1860         }
1861
1862         /* we're committed to creating a new filter */
1863         *filterp = filter;
1864         *psp = ps;
1865
1866         parse_init(ps, filter_ops, filter_str);
1867         err = filter_parse(ps);
1868         if (err && set_str)
1869                 append_filter_err(ps, filter);
1870         return err;
1871 }
1872
1873 static void create_filter_finish(struct filter_parse_state *ps)
1874 {
1875         if (ps) {
1876                 filter_opstack_clear(ps);
1877                 postfix_clear(ps);
1878                 kfree(ps);
1879         }
1880 }
1881
1882 /**
1883  * create_filter - create a filter for a ftrace_event_call
1884  * @call: ftrace_event_call to create a filter for
1885  * @filter_str: filter string
1886  * @set_str: remember @filter_str and enable detailed error in filter
1887  * @filterp: out param for created filter (always updated on return)
1888  *
1889  * Creates a filter for @call with @filter_str.  If @set_str is %true,
1890  * @filter_str is copied and recorded in the new filter.
1891  *
1892  * On success, returns 0 and *@filterp points to the new filter.  On
1893  * failure, returns -errno and *@filterp may point to %NULL or to a new
1894  * filter.  In the latter case, the returned filter contains error
1895  * information if @set_str is %true and the caller is responsible for
1896  * freeing it.
1897  */
1898 static int create_filter(struct ftrace_event_call *call,
1899                          char *filter_str, bool set_str,
1900                          struct event_filter **filterp)
1901 {
1902         struct event_filter *filter = NULL;
1903         struct filter_parse_state *ps = NULL;
1904         int err;
1905
1906         err = create_filter_start(filter_str, set_str, &ps, &filter);
1907         if (!err) {
1908                 err = replace_preds(call, filter, ps, false);
1909                 if (err && set_str)
1910                         append_filter_err(ps, filter);
1911         }
1912         create_filter_finish(ps);
1913
1914         *filterp = filter;
1915         return err;
1916 }
1917
1918 int create_event_filter(struct ftrace_event_call *call,
1919                         char *filter_str, bool set_str,
1920                         struct event_filter **filterp)
1921 {
1922         return create_filter(call, filter_str, set_str, filterp);
1923 }
1924
1925 /**
1926  * create_system_filter - create a filter for an event_subsystem
1927  * @system: event_subsystem to create a filter for
1928  * @filter_str: filter string
1929  * @filterp: out param for created filter (always updated on return)
1930  *
1931  * Identical to create_filter() except that it creates a subsystem filter
1932  * and always remembers @filter_str.
1933  */
1934 static int create_system_filter(struct ftrace_subsystem_dir *dir,
1935                                 struct trace_array *tr,
1936                                 char *filter_str, struct event_filter **filterp)
1937 {
1938         struct event_filter *filter = NULL;
1939         struct filter_parse_state *ps = NULL;
1940         int err;
1941
1942         err = create_filter_start(filter_str, true, &ps, &filter);
1943         if (!err) {
1944                 err = replace_system_preds(dir, tr, ps, filter_str);
1945                 if (!err) {
1946                         /* System filters just show a default message */
1947                         kfree(filter->filter_string);
1948                         filter->filter_string = NULL;
1949                 } else {
1950                         append_filter_err(ps, filter);
1951                 }
1952         }
1953         create_filter_finish(ps);
1954
1955         *filterp = filter;
1956         return err;
1957 }
1958
1959 /* caller must hold event_mutex */
1960 int apply_event_filter(struct ftrace_event_file *file, char *filter_string)
1961 {
1962         struct ftrace_event_call *call = file->event_call;
1963         struct event_filter *filter;
1964         int err;
1965
1966         if (!strcmp(strstrip(filter_string), "0")) {
1967                 filter_disable(file);
1968                 filter = event_filter(file);
1969
1970                 if (!filter)
1971                         return 0;
1972
1973                 event_clear_filter(file);
1974
1975                 /* Make sure the filter is not being used */
1976                 synchronize_sched();
1977                 __free_filter(filter);
1978
1979                 return 0;
1980         }
1981
1982         err = create_filter(call, filter_string, true, &filter);
1983
1984         /*
1985          * Always swap the call filter with the new filter
1986          * even if there was an error. If there was an error
1987          * in the filter, we disable the filter and show the error
1988          * string
1989          */
1990         if (filter) {
1991                 struct event_filter *tmp;
1992
1993                 tmp = event_filter(file);
1994                 if (!err)
1995                         event_set_filtered_flag(file);
1996                 else
1997                         filter_disable(file);
1998
1999                 event_set_filter(file, filter);
2000
2001                 if (tmp) {
2002                         /* Make sure the call is done with the filter */
2003                         synchronize_sched();
2004                         __free_filter(tmp);
2005                 }
2006         }
2007
2008         return err;
2009 }
2010
2011 int apply_subsystem_event_filter(struct ftrace_subsystem_dir *dir,
2012                                  char *filter_string)
2013 {
2014         struct event_subsystem *system = dir->subsystem;
2015         struct trace_array *tr = dir->tr;
2016         struct event_filter *filter;
2017         int err = 0;
2018
2019         mutex_lock(&event_mutex);
2020
2021         /* Make sure the system still has events */
2022         if (!dir->nr_events) {
2023                 err = -ENODEV;
2024                 goto out_unlock;
2025         }
2026
2027         if (!strcmp(strstrip(filter_string), "0")) {
2028                 filter_free_subsystem_preds(dir, tr);
2029                 remove_filter_string(system->filter);
2030                 filter = system->filter;
2031                 system->filter = NULL;
2032                 /* Ensure all filters are no longer used */
2033                 synchronize_sched();
2034                 filter_free_subsystem_filters(dir, tr);
2035                 __free_filter(filter);
2036                 goto out_unlock;
2037         }
2038
2039         err = create_system_filter(dir, tr, filter_string, &filter);
2040         if (filter) {
2041                 /*
2042                  * No event actually uses the system filter
2043                  * we can free it without synchronize_sched().
2044                  */
2045                 __free_filter(system->filter);
2046                 system->filter = filter;
2047         }
2048 out_unlock:
2049         mutex_unlock(&event_mutex);
2050
2051         return err;
2052 }
2053
2054 #ifdef CONFIG_PERF_EVENTS
2055
2056 void ftrace_profile_free_filter(struct perf_event *event)
2057 {
2058         struct event_filter *filter = event->filter;
2059
2060         event->filter = NULL;
2061         __free_filter(filter);
2062 }
2063
2064 struct function_filter_data {
2065         struct ftrace_ops *ops;
2066         int first_filter;
2067         int first_notrace;
2068 };
2069
2070 #ifdef CONFIG_FUNCTION_TRACER
2071 static char **
2072 ftrace_function_filter_re(char *buf, int len, int *count)
2073 {
2074         char *str, *sep, **re;
2075
2076         str = kstrndup(buf, len, GFP_KERNEL);
2077         if (!str)
2078                 return NULL;
2079
2080         /*
2081          * The argv_split function takes white space
2082          * as a separator, so convert ',' into spaces.
2083          */
2084         while ((sep = strchr(str, ',')))
2085                 *sep = ' ';
2086
2087         re = argv_split(GFP_KERNEL, str, count);
2088         kfree(str);
2089         return re;
2090 }
2091
2092 static int ftrace_function_set_regexp(struct ftrace_ops *ops, int filter,
2093                                       int reset, char *re, int len)
2094 {
2095         int ret;
2096
2097         if (filter)
2098                 ret = ftrace_set_filter(ops, re, len, reset);
2099         else
2100                 ret = ftrace_set_notrace(ops, re, len, reset);
2101
2102         return ret;
2103 }
2104
2105 static int __ftrace_function_set_filter(int filter, char *buf, int len,
2106                                         struct function_filter_data *data)
2107 {
2108         int i, re_cnt, ret = -EINVAL;
2109         int *reset;
2110         char **re;
2111
2112         reset = filter ? &data->first_filter : &data->first_notrace;
2113
2114         /*
2115          * The 'ip' field could have multiple filters set, separated
2116          * either by space or comma. We first cut the filter and apply
2117          * all pieces separatelly.
2118          */
2119         re = ftrace_function_filter_re(buf, len, &re_cnt);
2120         if (!re)
2121                 return -EINVAL;
2122
2123         for (i = 0; i < re_cnt; i++) {
2124                 ret = ftrace_function_set_regexp(data->ops, filter, *reset,
2125                                                  re[i], strlen(re[i]));
2126                 if (ret)
2127                         break;
2128
2129                 if (*reset)
2130                         *reset = 0;
2131         }
2132
2133         argv_free(re);
2134         return ret;
2135 }
2136
2137 static int ftrace_function_check_pred(struct filter_pred *pred, int leaf)
2138 {
2139         struct ftrace_event_field *field = pred->field;
2140
2141         if (leaf) {
2142                 /*
2143                  * Check the leaf predicate for function trace, verify:
2144                  *  - only '==' and '!=' is used
2145                  *  - the 'ip' field is used
2146                  */
2147                 if ((pred->op != OP_EQ) && (pred->op != OP_NE))
2148                         return -EINVAL;
2149
2150                 if (strcmp(field->name, "ip"))
2151                         return -EINVAL;
2152         } else {
2153                 /*
2154                  * Check the non leaf predicate for function trace, verify:
2155                  *  - only '||' is used
2156                 */
2157                 if (pred->op != OP_OR)
2158                         return -EINVAL;
2159         }
2160
2161         return 0;
2162 }
2163
2164 static int ftrace_function_set_filter_cb(enum move_type move,
2165                                          struct filter_pred *pred,
2166                                          int *err, void *data)
2167 {
2168         /* Checking the node is valid for function trace. */
2169         if ((move != MOVE_DOWN) ||
2170             (pred->left != FILTER_PRED_INVALID)) {
2171                 *err = ftrace_function_check_pred(pred, 0);
2172         } else {
2173                 *err = ftrace_function_check_pred(pred, 1);
2174                 if (*err)
2175                         return WALK_PRED_ABORT;
2176
2177                 *err = __ftrace_function_set_filter(pred->op == OP_EQ,
2178                                                     pred->regex.pattern,
2179                                                     pred->regex.len,
2180                                                     data);
2181         }
2182
2183         return (*err) ? WALK_PRED_ABORT : WALK_PRED_DEFAULT;
2184 }
2185
2186 static int ftrace_function_set_filter(struct perf_event *event,
2187                                       struct event_filter *filter)
2188 {
2189         struct function_filter_data data = {
2190                 .first_filter  = 1,
2191                 .first_notrace = 1,
2192                 .ops           = &event->ftrace_ops,
2193         };
2194
2195         return walk_pred_tree(filter->preds, filter->root,
2196                               ftrace_function_set_filter_cb, &data);
2197 }
2198 #else
2199 static int ftrace_function_set_filter(struct perf_event *event,
2200                                       struct event_filter *filter)
2201 {
2202         return -ENODEV;
2203 }
2204 #endif /* CONFIG_FUNCTION_TRACER */
2205
2206 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
2207                               char *filter_str)
2208 {
2209         int err;
2210         struct event_filter *filter;
2211         struct ftrace_event_call *call;
2212
2213         mutex_lock(&event_mutex);
2214
2215         call = event->tp_event;
2216
2217         err = -EINVAL;
2218         if (!call)
2219                 goto out_unlock;
2220
2221         err = -EEXIST;
2222         if (event->filter)
2223                 goto out_unlock;
2224
2225         err = create_filter(call, filter_str, false, &filter);
2226         if (err)
2227                 goto free_filter;
2228
2229         if (ftrace_event_is_function(call))
2230                 err = ftrace_function_set_filter(event, filter);
2231         else
2232                 event->filter = filter;
2233
2234 free_filter:
2235         if (err || ftrace_event_is_function(call))
2236                 __free_filter(filter);
2237
2238 out_unlock:
2239         mutex_unlock(&event_mutex);
2240
2241         return err;
2242 }
2243
2244 #endif /* CONFIG_PERF_EVENTS */
2245
2246 #ifdef CONFIG_FTRACE_STARTUP_TEST
2247
2248 #include <linux/types.h>
2249 #include <linux/tracepoint.h>
2250
2251 #define CREATE_TRACE_POINTS
2252 #include "trace_events_filter_test.h"
2253
2254 #define DATA_REC(m, va, vb, vc, vd, ve, vf, vg, vh, nvisit) \
2255 { \
2256         .filter = FILTER, \
2257         .rec    = { .a = va, .b = vb, .c = vc, .d = vd, \
2258                     .e = ve, .f = vf, .g = vg, .h = vh }, \
2259         .match  = m, \
2260         .not_visited = nvisit, \
2261 }
2262 #define YES 1
2263 #define NO  0
2264
2265 static struct test_filter_data_t {
2266         char *filter;
2267         struct ftrace_raw_ftrace_test_filter rec;
2268         int match;
2269         char *not_visited;
2270 } test_filter_data[] = {
2271 #define FILTER "a == 1 && b == 1 && c == 1 && d == 1 && " \
2272                "e == 1 && f == 1 && g == 1 && h == 1"
2273         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, ""),
2274         DATA_REC(NO,  0, 1, 1, 1, 1, 1, 1, 1, "bcdefgh"),
2275         DATA_REC(NO,  1, 1, 1, 1, 1, 1, 1, 0, ""),
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(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2280         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 0, 1, ""),
2281         DATA_REC(YES, 1, 0, 0, 0, 0, 0, 0, 0, "bcdefgh"),
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(NO,  0, 0, 1, 1, 1, 1, 1, 1, "dfh"),
2286         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2287         DATA_REC(YES, 1, 0, 1, 0, 0, 1, 0, 1, "bd"),
2288         DATA_REC(NO,  1, 0, 1, 0, 0, 1, 0, 0, "bd"),
2289 #undef FILTER
2290 #define FILTER "(a == 1 && b == 1) || (c == 1 && d == 1) || " \
2291                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2292         DATA_REC(YES, 1, 0, 1, 1, 1, 1, 1, 1, "efgh"),
2293         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 1, 1, ""),
2294         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2295 #undef FILTER
2296 #define FILTER "(a == 1 && b == 1) && (c == 1 && d == 1) && " \
2297                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2298         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 0, "gh"),
2299         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2300         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, ""),
2301 #undef FILTER
2302 #define FILTER "((a == 1 || b == 1) || (c == 1 || d == 1) || " \
2303                "(e == 1 || f == 1)) && (g == 1 || h == 1)"
2304         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 1, "bcdef"),
2305         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2306         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, "h"),
2307 #undef FILTER
2308 #define FILTER "((((((((a == 1) && (b == 1)) || (c == 1)) && (d == 1)) || " \
2309                "(e == 1)) && (f == 1)) || (g == 1)) && (h == 1))"
2310         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "ceg"),
2311         DATA_REC(NO,  0, 1, 0, 1, 0, 1, 0, 1, ""),
2312         DATA_REC(NO,  1, 0, 1, 0, 1, 0, 1, 0, ""),
2313 #undef FILTER
2314 #define FILTER "((((((((a == 1) || (b == 1)) && (c == 1)) || (d == 1)) && " \
2315                "(e == 1)) || (f == 1)) && (g == 1)) || (h == 1))"
2316         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "bdfh"),
2317         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2318         DATA_REC(YES, 1, 0, 1, 0, 1, 0, 1, 0, "bdfh"),
2319 };
2320
2321 #undef DATA_REC
2322 #undef FILTER
2323 #undef YES
2324 #undef NO
2325
2326 #define DATA_CNT (sizeof(test_filter_data)/sizeof(struct test_filter_data_t))
2327
2328 static int test_pred_visited;
2329
2330 static int test_pred_visited_fn(struct filter_pred *pred, void *event)
2331 {
2332         struct ftrace_event_field *field = pred->field;
2333
2334         test_pred_visited = 1;
2335         printk(KERN_INFO "\npred visited %s\n", field->name);
2336         return 1;
2337 }
2338
2339 static int test_walk_pred_cb(enum move_type move, struct filter_pred *pred,
2340                              int *err, void *data)
2341 {
2342         char *fields = data;
2343
2344         if ((move == MOVE_DOWN) &&
2345             (pred->left == FILTER_PRED_INVALID)) {
2346                 struct ftrace_event_field *field = pred->field;
2347
2348                 if (!field) {
2349                         WARN(1, "all leafs should have field defined");
2350                         return WALK_PRED_DEFAULT;
2351                 }
2352                 if (!strchr(fields, *field->name))
2353                         return WALK_PRED_DEFAULT;
2354
2355                 WARN_ON(!pred->fn);
2356                 pred->fn = test_pred_visited_fn;
2357         }
2358         return WALK_PRED_DEFAULT;
2359 }
2360
2361 static __init int ftrace_test_event_filter(void)
2362 {
2363         int i;
2364
2365         printk(KERN_INFO "Testing ftrace filter: ");
2366
2367         for (i = 0; i < DATA_CNT; i++) {
2368                 struct event_filter *filter = NULL;
2369                 struct test_filter_data_t *d = &test_filter_data[i];
2370                 int err;
2371
2372                 err = create_filter(&event_ftrace_test_filter, d->filter,
2373                                     false, &filter);
2374                 if (err) {
2375                         printk(KERN_INFO
2376                                "Failed to get filter for '%s', err %d\n",
2377                                d->filter, err);
2378                         __free_filter(filter);
2379                         break;
2380                 }
2381
2382                 /*
2383                  * The preemption disabling is not really needed for self
2384                  * tests, but the rcu dereference will complain without it.
2385                  */
2386                 preempt_disable();
2387                 if (*d->not_visited)
2388                         walk_pred_tree(filter->preds, filter->root,
2389                                        test_walk_pred_cb,
2390                                        d->not_visited);
2391
2392                 test_pred_visited = 0;
2393                 err = filter_match_preds(filter, &d->rec);
2394                 preempt_enable();
2395
2396                 __free_filter(filter);
2397
2398                 if (test_pred_visited) {
2399                         printk(KERN_INFO
2400                                "Failed, unwanted pred visited for filter %s\n",
2401                                d->filter);
2402                         break;
2403                 }
2404
2405                 if (err != d->match) {
2406                         printk(KERN_INFO
2407                                "Failed to match filter '%s', expected %d\n",
2408                                d->filter, d->match);
2409                         break;
2410                 }
2411         }
2412
2413         if (i == DATA_CNT)
2414                 printk(KERN_CONT "OK\n");
2415
2416         return 0;
2417 }
2418
2419 late_initcall(ftrace_test_event_filter);
2420
2421 #endif /* CONFIG_FTRACE_STARTUP_TEST */