Pileus Git - ~andy/linux/blob - 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 enum filter_op_ids
  31 {
  32         OP_OR,
  33         OP_AND,
  34         OP_GLOB,
  35         OP_NE,
  36         OP_EQ,
  37         OP_LT,
  38         OP_LE,
  39         OP_GT,
  40         OP_GE,
  41         OP_NONE,
  42         OP_OPEN_PAREN,
  43 };
  44
  45 struct filter_op {
  46         int id;
  47         char *string;
  48         int precedence;
  49 };
  50
  51 static struct filter_op filter_ops[] = {
  52         { OP_OR,        "||",           1 },
  53         { OP_AND,       "&&",           2 },
  54         { OP_GLOB,      "~",            4 },
  55         { OP_NE,        "!=",           4 },
  56         { OP_EQ,        "==",           4 },
  57         { OP_LT,        "<",            5 },
  58         { OP_LE,        "<=",           5 },
  59         { OP_GT,        ">",            5 },
  60         { OP_GE,        ">=",           5 },
  61         { OP_NONE,      "OP_NONE",      0 },
  62         { OP_OPEN_PAREN, "(",           0 },
  63 };
  64
  65 enum {
  66         FILT_ERR_NONE,
  67         FILT_ERR_INVALID_OP,
  68         FILT_ERR_UNBALANCED_PAREN,
  69         FILT_ERR_TOO_MANY_OPERANDS,
  70         FILT_ERR_OPERAND_TOO_LONG,
  71         FILT_ERR_FIELD_NOT_FOUND,
  72         FILT_ERR_ILLEGAL_FIELD_OP,
  73         FILT_ERR_ILLEGAL_INTVAL,
  74         FILT_ERR_BAD_SUBSYS_FILTER,
  75         FILT_ERR_TOO_MANY_PREDS,
  76         FILT_ERR_MISSING_FIELD,
  77         FILT_ERR_INVALID_FILTER,
  78 };
  79
  80 static char *err_text[] = {
  81         "No error",
  82         "Invalid operator",
  83         "Unbalanced parens",
  84         "Too many operands",
  85         "Operand too long",
  86         "Field not found",
  87         "Illegal operation for field type",
  88         "Illegal integer value",
  89         "Couldn't find or set field in one of a subsystem's events",
  90         "Too many terms in predicate expression",
  91         "Missing field name and/or value",
  92         "Meaningless filter expression",
  93 };
  94
  95 struct opstack_op {
  96         int op;
  97         struct list_head list;
  98 };
  99
 100 struct postfix_elt {
 101         int op;
 102         char *operand;
 103         struct list_head list;
 104 };
 105
 106 struct filter_parse_state {
 107         struct filter_op *ops;
 108         struct list_head opstack;
 109         struct list_head postfix;
 110         int lasterr;
 111         int lasterr_pos;
 112
 113         struct {
 114                 char *string;
 115                 unsigned int cnt;
 116                 unsigned int tail;
 117         } infix;
 118
 119         struct {
 120                 char string[MAX_FILTER_STR_VAL];
 121                 int pos;
 122                 unsigned int tail;
 123         } operand;
 124 };
 125
 126 struct pred_stack {
 127         struct filter_pred      **preds;
 128         int                     index;
 129 };
 130
 131 #define DEFINE_COMPARISON_PRED(type)                                    \
 132 static int filter_pred_##type(struct filter_pred *pred, void *event)    \
 133 {                                                                       \
 134         type *addr = (type *)(event + pred->offset);                    \
 135         type val = (type)pred->val;                                     \
 136         int match = 0;                                                  \
 137                                                                         \
 138         switch (pred->op) {                                             \
 139         case OP_LT:                                                     \
 140                 match = (*addr < val);                                  \
 141                 break;                                                  \
 142         case OP_LE:                                                     \
 143                 match = (*addr <= val);                                 \
 144                 break;                                                  \
 145         case OP_GT:                                                     \
 146                 match = (*addr > val);                                  \
 147                 break;                                                  \
 148         case OP_GE:                                                     \
 149                 match = (*addr >= val);                                 \
 150                 break;                                                  \
 151         default:                                                        \
 152                 break;                                                  \
 153         }                                                               \
 154                                                                         \
 155         return match;                                                   \
 156 }
 157
 158 #define DEFINE_EQUALITY_PRED(size)                                      \
 159 static int filter_pred_##size(struct filter_pred *pred, void *event)    \
 160 {                                                                       \
 161         u##size *addr = (u##size *)(event + pred->offset);              \
 162         u##size val = (u##size)pred->val;                               \
 163         int match;                                                      \
 164                                                                         \
 165         match = (val == *addr) ^ pred->not;                             \
 166                                                                         \
 167         return match;                                                   \
 168 }
 169
 170 DEFINE_COMPARISON_PRED(s64);
 171 DEFINE_COMPARISON_PRED(u64);
 172 DEFINE_COMPARISON_PRED(s32);
 173 DEFINE_COMPARISON_PRED(u32);
 174 DEFINE_COMPARISON_PRED(s16);
 175 DEFINE_COMPARISON_PRED(u16);
 176 DEFINE_COMPARISON_PRED(s8);
 177 DEFINE_COMPARISON_PRED(u8);
 178
 179 DEFINE_EQUALITY_PRED(64);
 180 DEFINE_EQUALITY_PRED(32);
 181 DEFINE_EQUALITY_PRED(16);
 182 DEFINE_EQUALITY_PRED(8);
 183
 184 /* Filter predicate for fixed sized arrays of characters */
 185 static int filter_pred_string(struct filter_pred *pred, void *event)
 186 {
 187         char *addr = (char *)(event + pred->offset);
 188         int cmp, match;
 189
 190         cmp = pred->regex.match(addr, &pred->regex, pred->regex.field_len);
 191
 192         match = cmp ^ pred->not;
 193
 194         return match;
 195 }
 196
 197 /* Filter predicate for char * pointers */
 198 static int filter_pred_pchar(struct filter_pred *pred, void *event)
 199 {
 200         char **addr = (char **)(event + pred->offset);
 201         int cmp, match;
 202         int len = strlen(*addr) + 1;    /* including tailing '\0' */
 203
 204         cmp = pred->regex.match(*addr, &pred->regex, len);
 205
 206         match = cmp ^ pred->not;
 207
 208         return match;
 209 }
 210
 211 /*
 212  * Filter predicate for dynamic sized arrays of characters.
 213  * These are implemented through a list of strings at the end
 214  * of the entry.
 215  * Also each of these strings have a field in the entry which
 216  * contains its offset from the beginning of the entry.
 217  * We have then first to get this field, dereference it
 218  * and add it to the address of the entry, and at last we have
 219  * the address of the string.
 220  */
 221 static int filter_pred_strloc(struct filter_pred *pred, void *event)
 222 {
 223         u32 str_item = *(u32 *)(event + pred->offset);
 224         int str_loc = str_item & 0xffff;
 225         int str_len = str_item >> 16;
 226         char *addr = (char *)(event + str_loc);
 227         int cmp, match;
 228
 229         cmp = pred->regex.match(addr, &pred->regex, str_len);
 230
 231         match = cmp ^ pred->not;
 232
 233         return match;
 234 }
 235
 236 static int filter_pred_none(struct filter_pred *pred, void *event)
 237 {
 238         return 0;
 239 }
 240
 241 /*
 242  * regex_match_foo - Basic regex callbacks
 243  *
 244  * @str: the string to be searched
 245  * @r:   the regex structure containing the pattern string
 246  * @len: the length of the string to be searched (including '\0')
 247  *
 248  * Note:
 249  * - @str might not be NULL-terminated if it's of type DYN_STRING
 250  *   or STATIC_STRING
 251  */
 252
 253 static int regex_match_full(char *str, struct regex *r, int len)
 254 {
 255         if (strncmp(str, r->pattern, len) == 0)
 256                 return 1;
 257         return 0;
 258 }
 259
 260 static int regex_match_front(char *str, struct regex *r, int len)
 261 {
 262         if (strncmp(str, r->pattern, r->len) == 0)
 263                 return 1;
 264         return 0;
 265 }
 266
 267 static int regex_match_middle(char *str, struct regex *r, int len)
 268 {
 269         if (strnstr(str, r->pattern, len))
 270                 return 1;
 271         return 0;
 272 }
 273
 274 static int regex_match_end(char *str, struct regex *r, int len)
 275 {
 276         int strlen = len - 1;
 277
 278         if (strlen >= r->len &&
 279             memcmp(str + strlen - r->len, r->pattern, r->len) == 0)
 280                 return 1;
 281         return 0;
 282 }
 283
 284 /**
 285  * filter_parse_regex - parse a basic regex
 286  * @buff:   the raw regex
 287  * @len:    length of the regex
 288  * @search: will point to the beginning of the string to compare
 289  * @not:    tell whether the match will have to be inverted
 290  *
 291  * This passes in a buffer containing a regex and this function will
 292  * set search to point to the search part of the buffer and
 293  * return the type of search it is (see enum above).
 294  * This does modify buff.
 295  *
 296  * Returns enum type.
 297  *  search returns the pointer to use for comparison.
 298  *  not returns 1 if buff started with a '!'
 299  *     0 otherwise.
 300  */
 301 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
 302 {
 303         int type = MATCH_FULL;
 304         int i;
 305
 306         if (buff[0] == '!') {
 307                 *not = 1;
 308                 buff++;
 309                 len--;
 310         } else
 311                 *not = 0;
 312
 313         *search = buff;
 314
 315         for (i = 0; i < len; i++) {
 316                 if (buff[i] == '*') {
 317                         if (!i) {
 318                                 *search = buff + 1;
 319                                 type = MATCH_END_ONLY;
 320                         } else {
 321                                 if (type == MATCH_END_ONLY)
 322                                         type = MATCH_MIDDLE_ONLY;
 323                                 else
 324                                         type = MATCH_FRONT_ONLY;
 325                                 buff[i] = 0;
 326                                 break;
 327                         }
 328                 }
 329         }
 330
 331         return type;
 332 }
 333
 334 static void filter_build_regex(struct filter_pred *pred)
 335 {
 336         struct regex *r = &pred->regex;
 337         char *search;
 338         enum regex_type type = MATCH_FULL;
 339         int not = 0;
 340
 341         if (pred->op == OP_GLOB) {
 342                 type = filter_parse_regex(r->pattern, r->len, &search, &not);
 343                 r->len = strlen(search);
 344                 memmove(r->pattern, search, r->len+1);
 345         }
 346
 347         switch (type) {
 348         case MATCH_FULL:
 349                 r->match = regex_match_full;
 350                 break;
 351         case MATCH_FRONT_ONLY:
 352                 r->match = regex_match_front;
 353                 break;
 354         case MATCH_MIDDLE_ONLY:
 355                 r->match = regex_match_middle;
 356                 break;
 357         case MATCH_END_ONLY:
 358                 r->match = regex_match_end;
 359                 break;
 360         }
 361
 362         pred->not ^= not;
 363 }
 364
 365 enum move_type {
 366         MOVE_DOWN,
 367         MOVE_UP_FROM_LEFT,
 368         MOVE_UP_FROM_RIGHT
 369 };
 370
 371 static struct filter_pred *
 372 get_pred_parent(struct filter_pred *pred, struct filter_pred *preds,
 373                 int index, enum move_type *move)
 374 {
 375         if (pred->parent & FILTER_PRED_IS_RIGHT)
 376                 *move = MOVE_UP_FROM_RIGHT;
 377         else
 378                 *move = MOVE_UP_FROM_LEFT;
 379         pred = &preds[pred->parent & ~FILTER_PRED_IS_RIGHT];
 380
 381         return pred;
 382 }
 383
 384 enum walk_return {
 385         WALK_PRED_ABORT,
 386         WALK_PRED_PARENT,
 387         WALK_PRED_DEFAULT,
 388 };
 389
 390 typedef int (*filter_pred_walkcb_t) (enum move_type move,
 391                                      struct filter_pred *pred,
 392                                      int *err, void *data);
 393
 394 static int walk_pred_tree(struct filter_pred *preds,
 395                           struct filter_pred *root,
 396                           filter_pred_walkcb_t cb, void *data)
 397 {
 398         struct filter_pred *pred = root;
 399         enum move_type move = MOVE_DOWN;
 400         int done = 0;
 401
 402         if  (!preds)
 403                 return -EINVAL;
 404
 405         do {
 406                 int err = 0, ret;
 407
 408                 ret = cb(move, pred, &err, data);
 409                 if (ret == WALK_PRED_ABORT)
 410                         return err;
 411                 if (ret == WALK_PRED_PARENT)
 412                         goto get_parent;
 413
 414                 switch (move) {
 415                 case MOVE_DOWN:
 416                         if (pred->left != FILTER_PRED_INVALID) {
 417                                 pred = &preds[pred->left];
 418                                 continue;
 419                         }
 420                         goto get_parent;
 421                 case MOVE_UP_FROM_LEFT:
 422                         pred = &preds[pred->right];
 423                         move = MOVE_DOWN;
 424                         continue;
 425                 case MOVE_UP_FROM_RIGHT:
 426  get_parent:
 427                         if (pred == root)
 428                                 break;
 429                         pred = get_pred_parent(pred, preds,
 430                                                pred->parent,
 431                                                &move);
 432                         continue;
 433                 }
 434                 done = 1;
 435         } while (!done);
 436
 437         /* We are fine. */
 438         return 0;
 439 }
 440
 441 /*
 442  * A series of AND or ORs where found together. Instead of
 443  * climbing up and down the tree branches, an array of the
 444  * ops were made in order of checks. We can just move across
 445  * the array and short circuit if needed.
 446  */
 447 static int process_ops(struct filter_pred *preds,
 448                        struct filter_pred *op, void *rec)
 449 {
 450         struct filter_pred *pred;
 451         int match = 0;
 452         int type;
 453         int i;
 454
 455         /*
 456          * Micro-optimization: We set type to true if op
 457          * is an OR and false otherwise (AND). Then we
 458          * just need to test if the match is equal to
 459          * the type, and if it is, we can short circuit the
 460          * rest of the checks:
 461          *
 462          * if ((match && op->op == OP_OR) ||
 463          *     (!match && op->op == OP_AND))
 464          *        return match;
 465          */
 466         type = op->op == OP_OR;
 467
 468         for (i = 0; i < op->val; i++) {
 469                 pred = &preds[op->ops[i]];
 470                 match = pred->fn(pred, rec);
 471                 if (!!match == type)
 472                         return match;
 473         }
 474         return match;
 475 }
 476
 477 /* return 1 if event matches, 0 otherwise (discard) */
 478 int filter_match_preds(struct event_filter *filter, void *rec)
 479 {
 480         int match = -1;
 481         enum move_type move = MOVE_DOWN;
 482         struct filter_pred *preds;
 483         struct filter_pred *pred;
 484         struct filter_pred *root;
 485         int n_preds;
 486         int done = 0;
 487
 488         /* no filter is considered a match */
 489         if (!filter)
 490                 return 1;
 491
 492         n_preds = filter->n_preds;
 493
 494         if (!n_preds)
 495                 return 1;
 496
 497         /*
 498          * n_preds, root and filter->preds are protect with preemption disabled.
 499          */
 500         preds = rcu_dereference_sched(filter->preds);
 501         root = rcu_dereference_sched(filter->root);
 502         if (!root)
 503                 return 1;
 504
 505         pred = root;
 506
 507         /* match is currently meaningless */
 508         match = -1;
 509
 510         do {
 511                 switch (move) {
 512                 case MOVE_DOWN:
 513                         /* only AND and OR have children */
 514                         if (pred->left != FILTER_PRED_INVALID) {
 515                                 /* If ops is set, then it was folded. */
 516                                 if (!pred->ops) {
 517                                         /* keep going to down the left side */
 518                                         pred = &preds[pred->left];
 519                                         continue;
 520                                 }
 521                                 /* We can treat folded ops as a leaf node */
 522                                 match = process_ops(preds, pred, rec);
 523                         } else
 524                                 match = pred->fn(pred, rec);
 525                         /* If this pred is the only pred */
 526                         if (pred == root)
 527                                 break;
 528                         pred = get_pred_parent(pred, preds,
 529                                                pred->parent, &move);
 530                         continue;
 531                 case MOVE_UP_FROM_LEFT:
 532                         /*
 533                          * Check for short circuits.
 534                          *
 535                          * Optimization: !!match == (pred->op == OP_OR)
 536                          *   is the same as:
 537                          * if ((match && pred->op == OP_OR) ||
 538                          *     (!match && pred->op == OP_AND))
 539                          */
 540                         if (!!match == (pred->op == OP_OR)) {
 541                                 if (pred == root)
 542                                         break;
 543                                 pred = get_pred_parent(pred, preds,
 544                                                        pred->parent, &move);
 545                                 continue;
 546                         }
 547                         /* now go down the right side of the tree. */
 548                         pred = &preds[pred->right];
 549                         move = MOVE_DOWN;
 550                         continue;
 551                 case MOVE_UP_FROM_RIGHT:
 552                         /* We finished this equation. */
 553                         if (pred == root)
 554                                 break;
 555                         pred = get_pred_parent(pred, preds,
 556                                                pred->parent, &move);
 557                         continue;
 558                 }
 559                 done = 1;
 560         } while (!done);
 561
 562         return match;
 563 }
 564 EXPORT_SYMBOL_GPL(filter_match_preds);
 565
 566 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 567 {
 568         ps->lasterr = err;
 569         ps->lasterr_pos = pos;
 570 }
 571
 572 static void remove_filter_string(struct event_filter *filter)
 573 {
 574         if (!filter)
 575                 return;
 576
 577         kfree(filter->filter_string);
 578         filter->filter_string = NULL;
 579 }
 580
 581 static int replace_filter_string(struct event_filter *filter,
 582                                  char *filter_string)
 583 {
 584         kfree(filter->filter_string);
 585         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 586         if (!filter->filter_string)
 587                 return -ENOMEM;
 588
 589         return 0;
 590 }
 591
 592 static int append_filter_string(struct event_filter *filter,
 593                                 char *string)
 594 {
 595         int newlen;
 596         char *new_filter_string;
 597
 598         BUG_ON(!filter->filter_string);
 599         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 600         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 601         if (!new_filter_string)
 602                 return -ENOMEM;
 603
 604         strcpy(new_filter_string, filter->filter_string);
 605         strcat(new_filter_string, string);
 606         kfree(filter->filter_string);
 607         filter->filter_string = new_filter_string;
 608
 609         return 0;
 610 }
 611
 612 static void append_filter_err(struct filter_parse_state *ps,
 613                               struct event_filter *filter)
 614 {
 615         int pos = ps->lasterr_pos;
 616         char *buf, *pbuf;
 617
 618         buf = (char *)__get_free_page(GFP_TEMPORARY);
 619         if (!buf)
 620                 return;
 621
 622         append_filter_string(filter, "\n");
 623         memset(buf, ' ', PAGE_SIZE);
 624         if (pos > PAGE_SIZE - 128)
 625                 pos = 0;
 626         buf[pos] = '^';
 627         pbuf = &buf[pos] + 1;
 628
 629         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 630         append_filter_string(filter, buf);
 631         free_page((unsigned long) buf);
 632 }
 633
 634 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 635 {
 636         struct event_filter *filter;
 637
 638         mutex_lock(&event_mutex);
 639         filter = call->filter;
 640         if (filter && filter->filter_string)
 641                 trace_seq_printf(s, "%s\n", filter->filter_string);
 642         else
 643                 trace_seq_printf(s, "none\n");
 644         mutex_unlock(&event_mutex);
 645 }
 646
 647 void print_subsystem_event_filter(struct event_subsystem *system,
 648                                   struct trace_seq *s)
 649 {
 650         struct event_filter *filter;
 651
 652         mutex_lock(&event_mutex);
 653         filter = system->filter;
 654         if (filter && filter->filter_string)
 655                 trace_seq_printf(s, "%s\n", filter->filter_string);
 656         else
 657                 trace_seq_printf(s, "none\n");
 658         mutex_unlock(&event_mutex);
 659 }
 660
 661 static struct ftrace_event_field *
 662 __find_event_field(struct list_head *head, char *name)
 663 {
 664         struct ftrace_event_field *field;
 665
 666         list_for_each_entry(field, head, link) {
 667                 if (!strcmp(field->name, name))
 668                         return field;
 669         }
 670
 671         return NULL;
 672 }
 673
 674 static struct ftrace_event_field *
 675 find_event_field(struct ftrace_event_call *call, char *name)
 676 {
 677         struct ftrace_event_field *field;
 678         struct list_head *head;
 679
 680         field = __find_event_field(&ftrace_common_fields, name);
 681         if (field)
 682                 return field;
 683
 684         head = trace_get_fields(call);
 685         return __find_event_field(head, name);
 686 }
 687
 688 static int __alloc_pred_stack(struct pred_stack *stack, int n_preds)
 689 {
 690         stack->preds = kzalloc(sizeof(*stack->preds)*(n_preds + 1), GFP_KERNEL);
 691         if (!stack->preds)
 692                 return -ENOMEM;
 693         stack->index = n_preds;
 694         return 0;
 695 }
 696
 697 static void __free_pred_stack(struct pred_stack *stack)
 698 {
 699         kfree(stack->preds);
 700         stack->index = 0;
 701 }
 702
 703 static int __push_pred_stack(struct pred_stack *stack,
 704                              struct filter_pred *pred)
 705 {
 706         int index = stack->index;
 707
 708         if (WARN_ON(index == 0))
 709                 return -ENOSPC;
 710
 711         stack->preds[--index] = pred;
 712         stack->index = index;
 713         return 0;
 714 }
 715
 716 static struct filter_pred *
 717 __pop_pred_stack(struct pred_stack *stack)
 718 {
 719         struct filter_pred *pred;
 720         int index = stack->index;
 721
 722         pred = stack->preds[index++];
 723         if (!pred)
 724                 return NULL;
 725
 726         stack->index = index;
 727         return pred;
 728 }
 729
 730 static int filter_set_pred(struct event_filter *filter,
 731                            int idx,
 732                            struct pred_stack *stack,
 733                            struct filter_pred *src)
 734 {
 735         struct filter_pred *dest = &filter->preds[idx];
 736         struct filter_pred *left;
 737         struct filter_pred *right;
 738
 739         *dest = *src;
 740         dest->index = idx;
 741
 742         if (dest->op == OP_OR || dest->op == OP_AND) {
 743                 right = __pop_pred_stack(stack);
 744                 left = __pop_pred_stack(stack);
 745                 if (!left || !right)
 746                         return -EINVAL;
 747                 /*
 748                  * If both children can be folded
 749                  * and they are the same op as this op or a leaf,
 750                  * then this op can be folded.
 751                  */
 752                 if (left->index & FILTER_PRED_FOLD &&
 753                     (left->op == dest->op ||
 754                      left->left == FILTER_PRED_INVALID) &&
 755                     right->index & FILTER_PRED_FOLD &&
 756                     (right->op == dest->op ||
 757                      right->left == FILTER_PRED_INVALID))
 758                         dest->index |= FILTER_PRED_FOLD;
 759
 760                 dest->left = left->index & ~FILTER_PRED_FOLD;
 761                 dest->right = right->index & ~FILTER_PRED_FOLD;
 762                 left->parent = dest->index & ~FILTER_PRED_FOLD;
 763                 right->parent = dest->index | FILTER_PRED_IS_RIGHT;
 764         } else {
 765                 /*
 766                  * Make dest->left invalid to be used as a quick
 767                  * way to know this is a leaf node.
 768                  */
 769                 dest->left = FILTER_PRED_INVALID;
 770
 771                 /* All leafs allow folding the parent ops. */
 772                 dest->index |= FILTER_PRED_FOLD;
 773         }
 774
 775         return __push_pred_stack(stack, dest);
 776 }
 777
 778 static void __free_preds(struct event_filter *filter)
 779 {
 780         if (filter->preds) {
 781                 kfree(filter->preds);
 782                 filter->preds = NULL;
 783         }
 784         filter->a_preds = 0;
 785         filter->n_preds = 0;
 786 }
 787
 788 static void filter_disable(struct ftrace_event_call *call)
 789 {
 790         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 791 }
 792
 793 static void __free_filter(struct event_filter *filter)
 794 {
 795         if (!filter)
 796                 return;
 797
 798         __free_preds(filter);
 799         kfree(filter->filter_string);
 800         kfree(filter);
 801 }
 802
 803 /*
 804  * Called when destroying the ftrace_event_call.
 805  * The call is being freed, so we do not need to worry about
 806  * the call being currently used. This is for module code removing
 807  * the tracepoints from within it.
 808  */
 809 void destroy_preds(struct ftrace_event_call *call)
 810 {
 811         __free_filter(call->filter);
 812         call->filter = NULL;
 813 }
 814
 815 static struct event_filter *__alloc_filter(void)
 816 {
 817         struct event_filter *filter;
 818
 819         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 820         return filter;
 821 }
 822
 823 static int __alloc_preds(struct event_filter *filter, int n_preds)
 824 {
 825         struct filter_pred *pred;
 826         int i;
 827
 828         if (filter->preds)
 829                 __free_preds(filter);
 830
 831         filter->preds =
 832                 kzalloc(sizeof(*filter->preds) * n_preds, GFP_KERNEL);
 833
 834         if (!filter->preds)
 835                 return -ENOMEM;
 836
 837         filter->a_preds = n_preds;
 838         filter->n_preds = 0;
 839
 840         for (i = 0; i < n_preds; i++) {
 841                 pred = &filter->preds[i];
 842                 pred->fn = filter_pred_none;
 843         }
 844
 845         return 0;
 846 }
 847
 848 static void filter_free_subsystem_preds(struct event_subsystem *system)
 849 {
 850         struct ftrace_event_call *call;
 851
 852         list_for_each_entry(call, &ftrace_events, list) {
 853                 if (strcmp(call->class->system, system->name) != 0)
 854                         continue;
 855
 856                 filter_disable(call);
 857                 remove_filter_string(call->filter);
 858         }
 859 }
 860
 861 static void filter_free_subsystem_filters(struct event_subsystem *system)
 862 {
 863         struct ftrace_event_call *call;
 864
 865         list_for_each_entry(call, &ftrace_events, list) {
 866                 if (strcmp(call->class->system, system->name) != 0)
 867                         continue;
 868                 __free_filter(call->filter);
 869                 call->filter = NULL;
 870         }
 871 }
 872
 873 static int filter_add_pred(struct filter_parse_state *ps,
 874                            struct event_filter *filter,
 875                            struct filter_pred *pred,
 876                            struct pred_stack *stack)
 877 {
 878         int err;
 879
 880         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 881                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 882                 return -ENOSPC;
 883         }
 884
 885         err = filter_set_pred(filter, filter->n_preds, stack, pred);
 886         if (err)
 887                 return err;
 888
 889         filter->n_preds++;
 890
 891         return 0;
 892 }
 893
 894 int filter_assign_type(const char *type)
 895 {
 896         if (strstr(type, "__data_loc") && strstr(type, "char"))
 897                 return FILTER_DYN_STRING;
 898
 899         if (strchr(type, '[') && strstr(type, "char"))
 900                 return FILTER_STATIC_STRING;
 901
 902         return FILTER_OTHER;
 903 }
 904
 905 static bool is_string_field(struct ftrace_event_field *field)
 906 {
 907         return field->filter_type == FILTER_DYN_STRING ||
 908                field->filter_type == FILTER_STATIC_STRING ||
 909                field->filter_type == FILTER_PTR_STRING;
 910 }
 911
 912 static int is_legal_op(struct ftrace_event_field *field, int op)
 913 {
 914         if (is_string_field(field) &&
 915             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 916                 return 0;
 917         if (!is_string_field(field) && op == OP_GLOB)
 918                 return 0;
 919
 920         return 1;
 921 }
 922
 923 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 924                                              int field_is_signed)
 925 {
 926         filter_pred_fn_t fn = NULL;
 927
 928         switch (field_size) {
 929         case 8:
 930                 if (op == OP_EQ || op == OP_NE)
 931                         fn = filter_pred_64;
 932                 else if (field_is_signed)
 933                         fn = filter_pred_s64;
 934                 else
 935                         fn = filter_pred_u64;
 936                 break;
 937         case 4:
 938                 if (op == OP_EQ || op == OP_NE)
 939                         fn = filter_pred_32;
 940                 else if (field_is_signed)
 941                         fn = filter_pred_s32;
 942                 else
 943                         fn = filter_pred_u32;
 944                 break;
 945         case 2:
 946                 if (op == OP_EQ || op == OP_NE)
 947                         fn = filter_pred_16;
 948                 else if (field_is_signed)
 949                         fn = filter_pred_s16;
 950                 else
 951                         fn = filter_pred_u16;
 952                 break;
 953         case 1:
 954                 if (op == OP_EQ || op == OP_NE)
 955                         fn = filter_pred_8;
 956                 else if (field_is_signed)
 957                         fn = filter_pred_s8;
 958                 else
 959                         fn = filter_pred_u8;
 960                 break;
 961         }
 962
 963         return fn;
 964 }
 965
 966 static int init_pred(struct filter_parse_state *ps,
 967                      struct ftrace_event_field *field,
 968                      struct filter_pred *pred)
 969
 970 {
 971         filter_pred_fn_t fn = filter_pred_none;
 972         unsigned long long val;
 973         int ret;
 974
 975         pred->offset = field->offset;
 976
 977         if (!is_legal_op(field, pred->op)) {
 978                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 979                 return -EINVAL;
 980         }
 981
 982         if (is_string_field(field)) {
 983                 filter_build_regex(pred);
 984
 985                 if (field->filter_type == FILTER_STATIC_STRING) {
 986                         fn = filter_pred_string;
 987                         pred->regex.field_len = field->size;
 988                 } else if (field->filter_type == FILTER_DYN_STRING)
 989                         fn = filter_pred_strloc;
 990                 else
 991                         fn = filter_pred_pchar;
 992         } else {
 993                 if (field->is_signed)
 994                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 995                 else
 996                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 997                 if (ret) {
 998                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 999                         return -EINVAL;
1000                 }
1001                 pred->val = val;
1002
1003                 fn = select_comparison_fn(pred->op, field->size,
1004                                           field->is_signed);
1005                 if (!fn) {
1006                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
1007                         return -EINVAL;
1008                 }
1009         }
1010
1011         if (pred->op == OP_NE)
1012                 pred->not = 1;
1013
1014         pred->fn = fn;
1015         return 0;
1016 }
1017
1018 static void parse_init(struct filter_parse_state *ps,
1019                        struct filter_op *ops,
1020                        char *infix_string)
1021 {
1022         memset(ps, '\0', sizeof(*ps));
1023
1024         ps->infix.string = infix_string;
1025         ps->infix.cnt = strlen(infix_string);
1026         ps->ops = ops;
1027
1028         INIT_LIST_HEAD(&ps->opstack);
1029         INIT_LIST_HEAD(&ps->postfix);
1030 }
1031
1032 static char infix_next(struct filter_parse_state *ps)
1033 {
1034         ps->infix.cnt--;
1035
1036         return ps->infix.string[ps->infix.tail++];
1037 }
1038
1039 static char infix_peek(struct filter_parse_state *ps)
1040 {
1041         if (ps->infix.tail == strlen(ps->infix.string))
1042                 return 0;
1043
1044         return ps->infix.string[ps->infix.tail];
1045 }
1046
1047 static void infix_advance(struct filter_parse_state *ps)
1048 {
1049         ps->infix.cnt--;
1050         ps->infix.tail++;
1051 }
1052
1053 static inline int is_precedence_lower(struct filter_parse_state *ps,
1054                                       int a, int b)
1055 {
1056         return ps->ops[a].precedence < ps->ops[b].precedence;
1057 }
1058
1059 static inline int is_op_char(struct filter_parse_state *ps, char c)
1060 {
1061         int i;
1062
1063         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1064                 if (ps->ops[i].string[0] == c)
1065                         return 1;
1066         }
1067
1068         return 0;
1069 }
1070
1071 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1072 {
1073         char nextc = infix_peek(ps);
1074         char opstr[3];
1075         int i;
1076
1077         opstr[0] = firstc;
1078         opstr[1] = nextc;
1079         opstr[2] = '\0';
1080
1081         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1082                 if (!strcmp(opstr, ps->ops[i].string)) {
1083                         infix_advance(ps);
1084                         return ps->ops[i].id;
1085                 }
1086         }
1087
1088         opstr[1] = '\0';
1089
1090         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1091                 if (!strcmp(opstr, ps->ops[i].string))
1092                         return ps->ops[i].id;
1093         }
1094
1095         return OP_NONE;
1096 }
1097
1098 static inline void clear_operand_string(struct filter_parse_state *ps)
1099 {
1100         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1101         ps->operand.tail = 0;
1102 }
1103
1104 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1105 {
1106         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1107                 return -EINVAL;
1108
1109         ps->operand.string[ps->operand.tail++] = c;
1110
1111         return 0;
1112 }
1113
1114 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1115 {
1116         struct opstack_op *opstack_op;
1117
1118         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1119         if (!opstack_op)
1120                 return -ENOMEM;
1121
1122         opstack_op->op = op;
1123         list_add(&opstack_op->list, &ps->opstack);
1124
1125         return 0;
1126 }
1127
1128 static int filter_opstack_empty(struct filter_parse_state *ps)
1129 {
1130         return list_empty(&ps->opstack);
1131 }
1132
1133 static int filter_opstack_top(struct filter_parse_state *ps)
1134 {
1135         struct opstack_op *opstack_op;
1136
1137         if (filter_opstack_empty(ps))
1138                 return OP_NONE;
1139
1140         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1141
1142         return opstack_op->op;
1143 }
1144
1145 static int filter_opstack_pop(struct filter_parse_state *ps)
1146 {
1147         struct opstack_op *opstack_op;
1148         int op;
1149
1150         if (filter_opstack_empty(ps))
1151                 return OP_NONE;
1152
1153         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1154         op = opstack_op->op;
1155         list_del(&opstack_op->list);
1156
1157         kfree(opstack_op);
1158
1159         return op;
1160 }
1161
1162 static void filter_opstack_clear(struct filter_parse_state *ps)
1163 {
1164         while (!filter_opstack_empty(ps))
1165                 filter_opstack_pop(ps);
1166 }
1167
1168 static char *curr_operand(struct filter_parse_state *ps)
1169 {
1170         return ps->operand.string;
1171 }
1172
1173 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1174 {
1175         struct postfix_elt *elt;
1176
1177         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1178         if (!elt)
1179                 return -ENOMEM;
1180
1181         elt->op = OP_NONE;
1182         elt->operand = kstrdup(operand, GFP_KERNEL);
1183         if (!elt->operand) {
1184                 kfree(elt);
1185                 return -ENOMEM;
1186         }
1187
1188         list_add_tail(&elt->list, &ps->postfix);
1189
1190         return 0;
1191 }
1192
1193 static int postfix_append_op(struct filter_parse_state *ps, int op)
1194 {
1195         struct postfix_elt *elt;
1196
1197         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1198         if (!elt)
1199                 return -ENOMEM;
1200
1201         elt->op = op;
1202         elt->operand = NULL;
1203
1204         list_add_tail(&elt->list, &ps->postfix);
1205
1206         return 0;
1207 }
1208
1209 static void postfix_clear(struct filter_parse_state *ps)
1210 {
1211         struct postfix_elt *elt;
1212
1213         while (!list_empty(&ps->postfix)) {
1214                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1215                 list_del(&elt->list);
1216                 kfree(elt->operand);
1217                 kfree(elt);
1218         }
1219 }
1220
1221 static int filter_parse(struct filter_parse_state *ps)
1222 {
1223         int in_string = 0;
1224         int op, top_op;
1225         char ch;
1226
1227         while ((ch = infix_next(ps))) {
1228                 if (ch == '"') {
1229                         in_string ^= 1;
1230                         continue;
1231                 }
1232
1233                 if (in_string)
1234                         goto parse_operand;
1235
1236                 if (isspace(ch))
1237                         continue;
1238
1239                 if (is_op_char(ps, ch)) {
1240                         op = infix_get_op(ps, ch);
1241                         if (op == OP_NONE) {
1242                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1243                                 return -EINVAL;
1244                         }
1245
1246                         if (strlen(curr_operand(ps))) {
1247                                 postfix_append_operand(ps, curr_operand(ps));
1248                                 clear_operand_string(ps);
1249                         }
1250
1251                         while (!filter_opstack_empty(ps)) {
1252                                 top_op = filter_opstack_top(ps);
1253                                 if (!is_precedence_lower(ps, top_op, op)) {
1254                                         top_op = filter_opstack_pop(ps);
1255                                         postfix_append_op(ps, top_op);
1256                                         continue;
1257                                 }
1258                                 break;
1259                         }
1260
1261                         filter_opstack_push(ps, op);
1262                         continue;
1263                 }
1264
1265                 if (ch == '(') {
1266                         filter_opstack_push(ps, OP_OPEN_PAREN);
1267                         continue;
1268                 }
1269
1270                 if (ch == ')') {
1271                         if (strlen(curr_operand(ps))) {
1272                                 postfix_append_operand(ps, curr_operand(ps));
1273                                 clear_operand_string(ps);
1274                         }
1275
1276                         top_op = filter_opstack_pop(ps);
1277                         while (top_op != OP_NONE) {
1278                                 if (top_op == OP_OPEN_PAREN)
1279                                         break;
1280                                 postfix_append_op(ps, top_op);
1281                                 top_op = filter_opstack_pop(ps);
1282                         }
1283                         if (top_op == OP_NONE) {
1284                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1285                                 return -EINVAL;
1286                         }
1287                         continue;
1288                 }
1289 parse_operand:
1290                 if (append_operand_char(ps, ch)) {
1291                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1292                         return -EINVAL;
1293                 }
1294         }
1295
1296         if (strlen(curr_operand(ps)))
1297                 postfix_append_operand(ps, curr_operand(ps));
1298
1299         while (!filter_opstack_empty(ps)) {
1300                 top_op = filter_opstack_pop(ps);
1301                 if (top_op == OP_NONE)
1302                         break;
1303                 if (top_op == OP_OPEN_PAREN) {
1304                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1305                         return -EINVAL;
1306                 }
1307                 postfix_append_op(ps, top_op);
1308         }
1309
1310         return 0;
1311 }
1312
1313 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1314                                        struct ftrace_event_call *call,
1315                                        int op, char *operand1, char *operand2)
1316 {
1317         struct ftrace_event_field *field;
1318         static struct filter_pred pred;
1319
1320         memset(&pred, 0, sizeof(pred));
1321         pred.op = op;
1322
1323         if (op == OP_AND || op == OP_OR)
1324                 return &pred;
1325
1326         if (!operand1 || !operand2) {
1327                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1328                 return NULL;
1329         }
1330
1331         field = find_event_field(call, operand1);
1332         if (!field) {
1333                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1334                 return NULL;
1335         }
1336
1337         strcpy(pred.regex.pattern, operand2);
1338         pred.regex.len = strlen(pred.regex.pattern);
1339
1340         return init_pred(ps, field, &pred) ? NULL : &pred;
1341 }
1342
1343 static int check_preds(struct filter_parse_state *ps)
1344 {
1345         int n_normal_preds = 0, n_logical_preds = 0;
1346         struct postfix_elt *elt;
1347
1348         list_for_each_entry(elt, &ps->postfix, list) {
1349                 if (elt->op == OP_NONE)
1350                         continue;
1351
1352                 if (elt->op == OP_AND || elt->op == OP_OR) {
1353                         n_logical_preds++;
1354                         continue;
1355                 }
1356                 n_normal_preds++;
1357         }
1358
1359         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1360                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1361                 return -EINVAL;
1362         }
1363
1364         return 0;
1365 }
1366
1367 static int count_preds(struct filter_parse_state *ps)
1368 {
1369         struct postfix_elt *elt;
1370         int n_preds = 0;
1371
1372         list_for_each_entry(elt, &ps->postfix, list) {
1373                 if (elt->op == OP_NONE)
1374                         continue;
1375                 n_preds++;
1376         }
1377
1378         return n_preds;
1379 }
1380
1381 struct check_pred_data {
1382         int count;
1383         int max;
1384 };
1385
1386 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1387                               int *err, void *data)
1388 {
1389         struct check_pred_data *d = data;
1390
1391         if (WARN_ON(d->count++ > d->max)) {
1392                 *err = -EINVAL;
1393                 return WALK_PRED_ABORT;
1394         }
1395         return WALK_PRED_DEFAULT;
1396 }
1397
1398 /*
1399  * The tree is walked at filtering of an event. If the tree is not correctly
1400  * built, it may cause an infinite loop. Check here that the tree does
1401  * indeed terminate.
1402  */
1403 static int check_pred_tree(struct event_filter *filter,
1404                            struct filter_pred *root)
1405 {
1406         struct check_pred_data data = {
1407                 /*
1408                  * The max that we can hit a node is three times.
1409                  * Once going down, once coming up from left, and
1410                  * once coming up from right. This is more than enough
1411                  * since leafs are only hit a single time.
1412                  */
1413                 .max   = 3 * filter->n_preds,
1414                 .count = 0,
1415         };
1416
1417         return walk_pred_tree(filter->preds, root,
1418                               check_pred_tree_cb, &data);
1419 }
1420
1421 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1422                           int *err, void *data)
1423 {
1424         int *count = data;
1425
1426         if ((move == MOVE_DOWN) &&
1427             (pred->left == FILTER_PRED_INVALID))
1428                 (*count)++;
1429
1430         return WALK_PRED_DEFAULT;
1431 }
1432
1433 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1434 {
1435         int count = 0, ret;
1436
1437         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1438         WARN_ON(ret);
1439         return count;
1440 }
1441
1442 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1443 {
1444         struct filter_pred *pred;
1445         enum move_type move = MOVE_DOWN;
1446         int count = 0;
1447         int children;
1448         int done = 0;
1449
1450         /* No need to keep the fold flag */
1451         root->index &= ~FILTER_PRED_FOLD;
1452
1453         /* If the root is a leaf then do nothing */
1454         if (root->left == FILTER_PRED_INVALID)
1455                 return 0;
1456
1457         /* count the children */
1458         children = count_leafs(preds, &preds[root->left]);
1459         children += count_leafs(preds, &preds[root->right]);
1460
1461         root->ops = kzalloc(sizeof(*root->ops) * children, GFP_KERNEL);
1462         if (!root->ops)
1463                 return -ENOMEM;
1464
1465         root->val = children;
1466
1467         pred = root;
1468         do {
1469                 switch (move) {
1470                 case MOVE_DOWN:
1471                         if (pred->left != FILTER_PRED_INVALID) {
1472                                 pred = &preds[pred->left];
1473                                 continue;
1474                         }
1475                         if (WARN_ON(count == children))
1476                                 return -EINVAL;
1477                         pred->index &= ~FILTER_PRED_FOLD;
1478                         root->ops[count++] = pred->index;
1479                         pred = get_pred_parent(pred, preds,
1480                                                pred->parent, &move);
1481                         continue;
1482                 case MOVE_UP_FROM_LEFT:
1483                         pred = &preds[pred->right];
1484                         move = MOVE_DOWN;
1485                         continue;
1486                 case MOVE_UP_FROM_RIGHT:
1487                         if (pred == root)
1488                                 break;
1489                         pred = get_pred_parent(pred, preds,
1490                                                pred->parent, &move);
1491                         continue;
1492                 }
1493                 done = 1;
1494         } while (!done);
1495
1496         return 0;
1497 }
1498
1499 /*
1500  * To optimize the processing of the ops, if we have several "ors" or
1501  * "ands" together, we can put them in an array and process them all
1502  * together speeding up the filter logic.
1503  */
1504 static int fold_pred_tree(struct event_filter *filter,
1505                            struct filter_pred *root)
1506 {
1507         struct filter_pred *preds;
1508         struct filter_pred *pred;
1509         enum move_type move = MOVE_DOWN;
1510         int done = 0;
1511         int err;
1512
1513         preds = filter->preds;
1514         if  (!preds)
1515                 return -EINVAL;
1516         pred = root;
1517
1518         do {
1519                 switch (move) {
1520                 case MOVE_DOWN:
1521                         if (pred->index & FILTER_PRED_FOLD) {
1522                                 err = fold_pred(preds, pred);
1523                                 if (err)
1524                                         return err;
1525                                 /* Folded nodes are like leafs */
1526                         } else if (pred->left != FILTER_PRED_INVALID) {
1527                                 pred = &preds[pred->left];
1528                                 continue;
1529                         }
1530
1531                         /* A leaf at the root is just a leaf in the tree */
1532                         if (pred == root)
1533                                 break;
1534                         pred = get_pred_parent(pred, preds,
1535                                                pred->parent, &move);
1536                         continue;
1537                 case MOVE_UP_FROM_LEFT:
1538                         pred = &preds[pred->right];
1539                         move = MOVE_DOWN;
1540                         continue;
1541                 case MOVE_UP_FROM_RIGHT:
1542                         if (pred == root)
1543                                 break;
1544                         pred = get_pred_parent(pred, preds,
1545                                                pred->parent, &move);
1546                         continue;
1547                 }
1548                 done = 1;
1549         } while (!done);
1550
1551         return 0;
1552 }
1553
1554 static int replace_preds(struct ftrace_event_call *call,
1555                          struct event_filter *filter,
1556                          struct filter_parse_state *ps,
1557                          char *filter_string,
1558                          bool dry_run)
1559 {
1560         char *operand1 = NULL, *operand2 = NULL;
1561         struct filter_pred *pred;
1562         struct filter_pred *root;
1563         struct postfix_elt *elt;
1564         struct pred_stack stack = { }; /* init to NULL */
1565         int err;
1566         int n_preds = 0;
1567
1568         n_preds = count_preds(ps);
1569         if (n_preds >= MAX_FILTER_PRED) {
1570                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1571                 return -ENOSPC;
1572         }
1573
1574         err = check_preds(ps);
1575         if (err)
1576                 return err;
1577
1578         if (!dry_run) {
1579                 err = __alloc_pred_stack(&stack, n_preds);
1580                 if (err)
1581                         return err;
1582                 err = __alloc_preds(filter, n_preds);
1583                 if (err)
1584                         goto fail;
1585         }
1586
1587         n_preds = 0;
1588         list_for_each_entry(elt, &ps->postfix, list) {
1589                 if (elt->op == OP_NONE) {
1590                         if (!operand1)
1591                                 operand1 = elt->operand;
1592                         else if (!operand2)
1593                                 operand2 = elt->operand;
1594                         else {
1595                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1596                                 err = -EINVAL;
1597                                 goto fail;
1598                         }
1599                         continue;
1600                 }
1601
1602                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1603                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1604                         err = -ENOSPC;
1605                         goto fail;
1606                 }
1607
1608                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1609                 if (!pred) {
1610                         err = -EINVAL;
1611                         goto fail;
1612                 }
1613
1614                 if (!dry_run) {
1615                         err = filter_add_pred(ps, filter, pred, &stack);
1616                         if (err)
1617                                 goto fail;
1618                 }
1619
1620                 operand1 = operand2 = NULL;
1621         }
1622
1623         if (!dry_run) {
1624                 /* We should have one item left on the stack */
1625                 pred = __pop_pred_stack(&stack);
1626                 if (!pred)
1627                         return -EINVAL;
1628                 /* This item is where we start from in matching */
1629                 root = pred;
1630                 /* Make sure the stack is empty */
1631                 pred = __pop_pred_stack(&stack);
1632                 if (WARN_ON(pred)) {
1633                         err = -EINVAL;
1634                         filter->root = NULL;
1635                         goto fail;
1636                 }
1637                 err = check_pred_tree(filter, root);
1638                 if (err)
1639                         goto fail;
1640
1641                 /* Optimize the tree */
1642                 err = fold_pred_tree(filter, root);
1643                 if (err)
1644                         goto fail;
1645
1646                 /* We don't set root until we know it works */
1647                 barrier();
1648                 filter->root = root;
1649         }
1650
1651         err = 0;
1652 fail:
1653         __free_pred_stack(&stack);
1654         return err;
1655 }
1656
1657 struct filter_list {
1658         struct list_head        list;
1659         struct event_filter     *filter;
1660 };
1661
1662 static int replace_system_preds(struct event_subsystem *system,
1663                                 struct filter_parse_state *ps,
1664                                 char *filter_string)
1665 {
1666         struct ftrace_event_call *call;
1667         struct filter_list *filter_item;
1668         struct filter_list *tmp;
1669         LIST_HEAD(filter_list);
1670         bool fail = true;
1671         int err;
1672
1673         list_for_each_entry(call, &ftrace_events, list) {
1674
1675                 if (strcmp(call->class->system, system->name) != 0)
1676                         continue;
1677
1678                 /*
1679                  * Try to see if the filter can be applied
1680                  *  (filter arg is ignored on dry_run)
1681                  */
1682                 err = replace_preds(call, NULL, ps, filter_string, true);
1683                 if (err)
1684                         goto fail;
1685         }
1686
1687         list_for_each_entry(call, &ftrace_events, list) {
1688                 struct event_filter *filter;
1689
1690                 if (strcmp(call->class->system, system->name) != 0)
1691                         continue;
1692
1693                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1694                 if (!filter_item)
1695                         goto fail_mem;
1696
1697                 list_add_tail(&filter_item->list, &filter_list);
1698
1699                 filter_item->filter = __alloc_filter();
1700                 if (!filter_item->filter)
1701                         goto fail_mem;
1702                 filter = filter_item->filter;
1703
1704                 /* Can only fail on no memory */
1705                 err = replace_filter_string(filter, filter_string);
1706                 if (err)
1707                         goto fail_mem;
1708
1709                 err = replace_preds(call, filter, ps, filter_string, false);
1710                 if (err) {
1711                         filter_disable(call);
1712                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1713                         append_filter_err(ps, filter);
1714                 } else
1715                         call->flags |= TRACE_EVENT_FL_FILTERED;
1716                 /*
1717                  * Regardless of if this returned an error, we still
1718                  * replace the filter for the call.
1719                  */
1720                 filter = call->filter;
1721                 call->filter = filter_item->filter;
1722                 filter_item->filter = filter;
1723
1724                 fail = false;
1725         }
1726
1727         if (fail)
1728                 goto fail;
1729
1730         /*
1731          * The calls can still be using the old filters.
1732          * Do a synchronize_sched() to ensure all calls are
1733          * done with them before we free them.
1734          */
1735         synchronize_sched();
1736         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1737                 __free_filter(filter_item->filter);
1738                 list_del(&filter_item->list);
1739                 kfree(filter_item);
1740         }
1741         return 0;
1742  fail:
1743         /* No call succeeded */
1744         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1745                 list_del(&filter_item->list);
1746                 kfree(filter_item);
1747         }
1748         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1749         return -EINVAL;
1750  fail_mem:
1751         /* If any call succeeded, we still need to sync */
1752         if (!fail)
1753                 synchronize_sched();
1754         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1755                 __free_filter(filter_item->filter);
1756                 list_del(&filter_item->list);
1757                 kfree(filter_item);
1758         }
1759         return -ENOMEM;
1760 }
1761
1762 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1763 {
1764         struct filter_parse_state *ps;
1765         struct event_filter *filter;
1766         struct event_filter *tmp;
1767         int err = 0;
1768
1769         mutex_lock(&event_mutex);
1770
1771         if (!strcmp(strstrip(filter_string), "0")) {
1772                 filter_disable(call);
1773                 filter = call->filter;
1774                 if (!filter)
1775                         goto out_unlock;
1776                 call->filter = NULL;
1777                 /* Make sure the filter is not being used */
1778                 synchronize_sched();
1779                 __free_filter(filter);
1780                 goto out_unlock;
1781         }
1782
1783         err = -ENOMEM;
1784         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1785         if (!ps)
1786                 goto out_unlock;
1787
1788         filter = __alloc_filter();
1789         if (!filter) {
1790                 kfree(ps);
1791                 goto out_unlock;
1792         }
1793
1794         replace_filter_string(filter, filter_string);
1795
1796         parse_init(ps, filter_ops, filter_string);
1797         err = filter_parse(ps);
1798         if (err) {
1799                 append_filter_err(ps, filter);
1800                 goto out;
1801         }
1802
1803         err = replace_preds(call, filter, ps, filter_string, false);
1804         if (err) {
1805                 filter_disable(call);
1806                 append_filter_err(ps, filter);
1807         } else
1808                 call->flags |= TRACE_EVENT_FL_FILTERED;
1809 out:
1810         /*
1811          * Always swap the call filter with the new filter
1812          * even if there was an error. If there was an error
1813          * in the filter, we disable the filter and show the error
1814          * string
1815          */
1816         tmp = call->filter;
1817         call->filter = filter;
1818         if (tmp) {
1819                 /* Make sure the call is done with the filter */
1820                 synchronize_sched();
1821                 __free_filter(tmp);
1822         }
1823         filter_opstack_clear(ps);
1824         postfix_clear(ps);
1825         kfree(ps);
1826 out_unlock:
1827         mutex_unlock(&event_mutex);
1828
1829         return err;
1830 }
1831
1832 int apply_subsystem_event_filter(struct event_subsystem *system,
1833                                  char *filter_string)
1834 {
1835         struct filter_parse_state *ps;
1836         struct event_filter *filter;
1837         int err = 0;
1838
1839         mutex_lock(&event_mutex);
1840
1841         /* Make sure the system still has events */
1842         if (!system->nr_events) {
1843                 err = -ENODEV;
1844                 goto out_unlock;
1845         }
1846
1847         if (!strcmp(strstrip(filter_string), "0")) {
1848                 filter_free_subsystem_preds(system);
1849                 remove_filter_string(system->filter);
1850                 filter = system->filter;
1851                 system->filter = NULL;
1852                 /* Ensure all filters are no longer used */
1853                 synchronize_sched();
1854                 filter_free_subsystem_filters(system);
1855                 __free_filter(filter);
1856                 goto out_unlock;
1857         }
1858
1859         err = -ENOMEM;
1860         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1861         if (!ps)
1862                 goto out_unlock;
1863
1864         filter = __alloc_filter();
1865         if (!filter)
1866                 goto out;
1867
1868         replace_filter_string(filter, filter_string);
1869         /*
1870          * No event actually uses the system filter
1871          * we can free it without synchronize_sched().
1872          */
1873         __free_filter(system->filter);
1874         system->filter = filter;
1875
1876         parse_init(ps, filter_ops, filter_string);
1877         err = filter_parse(ps);
1878         if (err) {
1879                 append_filter_err(ps, system->filter);
1880                 goto out;
1881         }
1882
1883         err = replace_system_preds(system, ps, filter_string);
1884         if (err)
1885                 append_filter_err(ps, system->filter);
1886
1887 out:
1888         filter_opstack_clear(ps);
1889         postfix_clear(ps);
1890         kfree(ps);
1891 out_unlock:
1892         mutex_unlock(&event_mutex);
1893
1894         return err;
1895 }
1896
1897 #ifdef CONFIG_PERF_EVENTS
1898
1899 void ftrace_profile_free_filter(struct perf_event *event)
1900 {
1901         struct event_filter *filter = event->filter;
1902
1903         event->filter = NULL;
1904         __free_filter(filter);
1905 }
1906
1907 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1908                               char *filter_str)
1909 {
1910         int err;
1911         struct event_filter *filter;
1912         struct filter_parse_state *ps;
1913         struct ftrace_event_call *call;
1914
1915         mutex_lock(&event_mutex);
1916
1917         call = event->tp_event;
1918
1919         err = -EINVAL;
1920         if (!call)
1921                 goto out_unlock;
1922
1923         err = -EEXIST;
1924         if (event->filter)
1925                 goto out_unlock;
1926
1927         filter = __alloc_filter();
1928         if (!filter) {
1929                 err = PTR_ERR(filter);
1930                 goto out_unlock;
1931         }
1932
1933         err = -ENOMEM;
1934         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1935         if (!ps)
1936                 goto free_filter;
1937
1938         parse_init(ps, filter_ops, filter_str);
1939         err = filter_parse(ps);
1940         if (err)
1941                 goto free_ps;
1942
1943         err = replace_preds(call, filter, ps, filter_str, false);
1944         if (!err)
1945                 event->filter = filter;
1946
1947 free_ps:
1948         filter_opstack_clear(ps);
1949         postfix_clear(ps);
1950         kfree(ps);
1951
1952 free_filter:
1953         if (err)
1954                 __free_filter(filter);
1955
1956 out_unlock:
1957         mutex_unlock(&event_mutex);
1958
1959         return err;
1960 }
1961
1962 #endif /* CONFIG_PERF_EVENTS */
1963