kernel/trace/trace_events_filter.c

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