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