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