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