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                 if (!WARN_ON_ONCE(!pred->fn))
 471                         match = pred->fn(pred, rec);
 472                 if (!!match == type)
 473                         return match;
 474         }
 475         return match;
 476 }
 477
 478 struct filter_match_preds_data {
 479         struct filter_pred *preds;
 480         int match;
 481         void *rec;
 482 };
 483
 484 static int filter_match_preds_cb(enum move_type move, struct filter_pred *pred,
 485                                  int *err, void *data)
 486 {
 487         struct filter_match_preds_data *d = data;
 488
 489         *err = 0;
 490         switch (move) {
 491         case MOVE_DOWN:
 492                 /* only AND and OR have children */
 493                 if (pred->left != FILTER_PRED_INVALID) {
 494                         /* If ops is set, then it was folded. */
 495                         if (!pred->ops)
 496                                 return WALK_PRED_DEFAULT;
 497                         /* We can treat folded ops as a leaf node */
 498                         d->match = process_ops(d->preds, pred, d->rec);
 499                 } else {
 500                         if (!WARN_ON_ONCE(!pred->fn))
 501                                 d->match = pred->fn(pred, d->rec);
 502                 }
 503
 504                 return WALK_PRED_PARENT;
 505         case MOVE_UP_FROM_LEFT:
 506                 /*
 507                  * Check for short circuits.
 508                  *
 509                  * Optimization: !!match == (pred->op == OP_OR)
 510                  *   is the same as:
 511                  * if ((match && pred->op == OP_OR) ||
 512                  *     (!match && pred->op == OP_AND))
 513                  */
 514                 if (!!d->match == (pred->op == OP_OR))
 515                         return WALK_PRED_PARENT;
 516                 break;
 517         case MOVE_UP_FROM_RIGHT:
 518                 break;
 519         }
 520
 521         return WALK_PRED_DEFAULT;
 522 }
 523
 524 /* return 1 if event matches, 0 otherwise (discard) */
 525 int filter_match_preds(struct event_filter *filter, void *rec)
 526 {
 527         struct filter_pred *preds;
 528         struct filter_pred *root;
 529         struct filter_match_preds_data data = {
 530                 /* match is currently meaningless */
 531                 .match = -1,
 532                 .rec   = rec,
 533         };
 534         int n_preds, ret;
 535
 536         /* no filter is considered a match */
 537         if (!filter)
 538                 return 1;
 539
 540         n_preds = filter->n_preds;
 541         if (!n_preds)
 542                 return 1;
 543
 544         /*
 545          * n_preds, root and filter->preds are protect with preemption disabled.
 546          */
 547         root = rcu_dereference_sched(filter->root);
 548         if (!root)
 549                 return 1;
 550
 551         data.preds = preds = rcu_dereference_sched(filter->preds);
 552         ret = walk_pred_tree(preds, root, filter_match_preds_cb, &data);
 553         WARN_ON(ret);
 554         return data.match;
 555 }
 556 EXPORT_SYMBOL_GPL(filter_match_preds);
 557
 558 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 559 {
 560         ps->lasterr = err;
 561         ps->lasterr_pos = pos;
 562 }
 563
 564 static void remove_filter_string(struct event_filter *filter)
 565 {
 566         if (!filter)
 567                 return;
 568
 569         kfree(filter->filter_string);
 570         filter->filter_string = NULL;
 571 }
 572
 573 static int replace_filter_string(struct event_filter *filter,
 574                                  char *filter_string)
 575 {
 576         kfree(filter->filter_string);
 577         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 578         if (!filter->filter_string)
 579                 return -ENOMEM;
 580
 581         return 0;
 582 }
 583
 584 static int append_filter_string(struct event_filter *filter,
 585                                 char *string)
 586 {
 587         int newlen;
 588         char *new_filter_string;
 589
 590         BUG_ON(!filter->filter_string);
 591         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 592         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 593         if (!new_filter_string)
 594                 return -ENOMEM;
 595
 596         strcpy(new_filter_string, filter->filter_string);
 597         strcat(new_filter_string, string);
 598         kfree(filter->filter_string);
 599         filter->filter_string = new_filter_string;
 600
 601         return 0;
 602 }
 603
 604 static void append_filter_err(struct filter_parse_state *ps,
 605                               struct event_filter *filter)
 606 {
 607         int pos = ps->lasterr_pos;
 608         char *buf, *pbuf;
 609
 610         buf = (char *)__get_free_page(GFP_TEMPORARY);
 611         if (!buf)
 612                 return;
 613
 614         append_filter_string(filter, "\n");
 615         memset(buf, ' ', PAGE_SIZE);
 616         if (pos > PAGE_SIZE - 128)
 617                 pos = 0;
 618         buf[pos] = '^';
 619         pbuf = &buf[pos] + 1;
 620
 621         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 622         append_filter_string(filter, buf);
 623         free_page((unsigned long) buf);
 624 }
 625
 626 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 627 {
 628         struct event_filter *filter;
 629
 630         mutex_lock(&event_mutex);
 631         filter = call->filter;
 632         if (filter && filter->filter_string)
 633                 trace_seq_printf(s, "%s\n", filter->filter_string);
 634         else
 635                 trace_seq_printf(s, "none\n");
 636         mutex_unlock(&event_mutex);
 637 }
 638
 639 void print_subsystem_event_filter(struct event_subsystem *system,
 640                                   struct trace_seq *s)
 641 {
 642         struct event_filter *filter;
 643
 644         mutex_lock(&event_mutex);
 645         filter = system->filter;
 646         if (filter && filter->filter_string)
 647                 trace_seq_printf(s, "%s\n", filter->filter_string);
 648         else
 649                 trace_seq_printf(s, "none\n");
 650         mutex_unlock(&event_mutex);
 651 }
 652
 653 static struct ftrace_event_field *
 654 __find_event_field(struct list_head *head, char *name)
 655 {
 656         struct ftrace_event_field *field;
 657
 658         list_for_each_entry(field, head, link) {
 659                 if (!strcmp(field->name, name))
 660                         return field;
 661         }
 662
 663         return NULL;
 664 }
 665
 666 static struct ftrace_event_field *
 667 find_event_field(struct ftrace_event_call *call, char *name)
 668 {
 669         struct ftrace_event_field *field;
 670         struct list_head *head;
 671
 672         field = __find_event_field(&ftrace_common_fields, name);
 673         if (field)
 674                 return field;
 675
 676         head = trace_get_fields(call);
 677         return __find_event_field(head, name);
 678 }
 679
 680 static int __alloc_pred_stack(struct pred_stack *stack, int n_preds)
 681 {
 682         stack->preds = kzalloc(sizeof(*stack->preds)*(n_preds + 1), GFP_KERNEL);
 683         if (!stack->preds)
 684                 return -ENOMEM;
 685         stack->index = n_preds;
 686         return 0;
 687 }
 688
 689 static void __free_pred_stack(struct pred_stack *stack)
 690 {
 691         kfree(stack->preds);
 692         stack->index = 0;
 693 }
 694
 695 static int __push_pred_stack(struct pred_stack *stack,
 696                              struct filter_pred *pred)
 697 {
 698         int index = stack->index;
 699
 700         if (WARN_ON(index == 0))
 701                 return -ENOSPC;
 702
 703         stack->preds[--index] = pred;
 704         stack->index = index;
 705         return 0;
 706 }
 707
 708 static struct filter_pred *
 709 __pop_pred_stack(struct pred_stack *stack)
 710 {
 711         struct filter_pred *pred;
 712         int index = stack->index;
 713
 714         pred = stack->preds[index++];
 715         if (!pred)
 716                 return NULL;
 717
 718         stack->index = index;
 719         return pred;
 720 }
 721
 722 static int filter_set_pred(struct event_filter *filter,
 723                            int idx,
 724                            struct pred_stack *stack,
 725                            struct filter_pred *src)
 726 {
 727         struct filter_pred *dest = &filter->preds[idx];
 728         struct filter_pred *left;
 729         struct filter_pred *right;
 730
 731         *dest = *src;
 732         dest->index = idx;
 733
 734         if (dest->op == OP_OR || dest->op == OP_AND) {
 735                 right = __pop_pred_stack(stack);
 736                 left = __pop_pred_stack(stack);
 737                 if (!left || !right)
 738                         return -EINVAL;
 739                 /*
 740                  * If both children can be folded
 741                  * and they are the same op as this op or a leaf,
 742                  * then this op can be folded.
 743                  */
 744                 if (left->index & FILTER_PRED_FOLD &&
 745                     (left->op == dest->op ||
 746                      left->left == FILTER_PRED_INVALID) &&
 747                     right->index & FILTER_PRED_FOLD &&
 748                     (right->op == dest->op ||
 749                      right->left == FILTER_PRED_INVALID))
 750                         dest->index |= FILTER_PRED_FOLD;
 751
 752                 dest->left = left->index & ~FILTER_PRED_FOLD;
 753                 dest->right = right->index & ~FILTER_PRED_FOLD;
 754                 left->parent = dest->index & ~FILTER_PRED_FOLD;
 755                 right->parent = dest->index | FILTER_PRED_IS_RIGHT;
 756         } else {
 757                 /*
 758                  * Make dest->left invalid to be used as a quick
 759                  * way to know this is a leaf node.
 760                  */
 761                 dest->left = FILTER_PRED_INVALID;
 762
 763                 /* All leafs allow folding the parent ops. */
 764                 dest->index |= FILTER_PRED_FOLD;
 765         }
 766
 767         return __push_pred_stack(stack, dest);
 768 }
 769
 770 static void __free_preds(struct event_filter *filter)
 771 {
 772         if (filter->preds) {
 773                 kfree(filter->preds);
 774                 filter->preds = NULL;
 775         }
 776         filter->a_preds = 0;
 777         filter->n_preds = 0;
 778 }
 779
 780 static void filter_disable(struct ftrace_event_call *call)
 781 {
 782         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 783 }
 784
 785 static void __free_filter(struct event_filter *filter)
 786 {
 787         if (!filter)
 788                 return;
 789
 790         __free_preds(filter);
 791         kfree(filter->filter_string);
 792         kfree(filter);
 793 }
 794
 795 /*
 796  * Called when destroying the ftrace_event_call.
 797  * The call is being freed, so we do not need to worry about
 798  * the call being currently used. This is for module code removing
 799  * the tracepoints from within it.
 800  */
 801 void destroy_preds(struct ftrace_event_call *call)
 802 {
 803         __free_filter(call->filter);
 804         call->filter = NULL;
 805 }
 806
 807 static struct event_filter *__alloc_filter(void)
 808 {
 809         struct event_filter *filter;
 810
 811         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 812         return filter;
 813 }
 814
 815 static int __alloc_preds(struct event_filter *filter, int n_preds)
 816 {
 817         struct filter_pred *pred;
 818         int i;
 819
 820         if (filter->preds)
 821                 __free_preds(filter);
 822
 823         filter->preds =
 824                 kzalloc(sizeof(*filter->preds) * n_preds, GFP_KERNEL);
 825
 826         if (!filter->preds)
 827                 return -ENOMEM;
 828
 829         filter->a_preds = n_preds;
 830         filter->n_preds = 0;
 831
 832         for (i = 0; i < n_preds; i++) {
 833                 pred = &filter->preds[i];
 834                 pred->fn = filter_pred_none;
 835         }
 836
 837         return 0;
 838 }
 839
 840 static void filter_free_subsystem_preds(struct event_subsystem *system)
 841 {
 842         struct ftrace_event_call *call;
 843
 844         list_for_each_entry(call, &ftrace_events, list) {
 845                 if (strcmp(call->class->system, system->name) != 0)
 846                         continue;
 847
 848                 filter_disable(call);
 849                 remove_filter_string(call->filter);
 850         }
 851 }
 852
 853 static void filter_free_subsystem_filters(struct event_subsystem *system)
 854 {
 855         struct ftrace_event_call *call;
 856
 857         list_for_each_entry(call, &ftrace_events, list) {
 858                 if (strcmp(call->class->system, system->name) != 0)
 859                         continue;
 860                 __free_filter(call->filter);
 861                 call->filter = NULL;
 862         }
 863 }
 864
 865 static int filter_add_pred(struct filter_parse_state *ps,
 866                            struct event_filter *filter,
 867                            struct filter_pred *pred,
 868                            struct pred_stack *stack)
 869 {
 870         int err;
 871
 872         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 873                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 874                 return -ENOSPC;
 875         }
 876
 877         err = filter_set_pred(filter, filter->n_preds, stack, pred);
 878         if (err)
 879                 return err;
 880
 881         filter->n_preds++;
 882
 883         return 0;
 884 }
 885
 886 int filter_assign_type(const char *type)
 887 {
 888         if (strstr(type, "__data_loc") && strstr(type, "char"))
 889                 return FILTER_DYN_STRING;
 890
 891         if (strchr(type, '[') && strstr(type, "char"))
 892                 return FILTER_STATIC_STRING;
 893
 894         return FILTER_OTHER;
 895 }
 896
 897 static bool is_string_field(struct ftrace_event_field *field)
 898 {
 899         return field->filter_type == FILTER_DYN_STRING ||
 900                field->filter_type == FILTER_STATIC_STRING ||
 901                field->filter_type == FILTER_PTR_STRING;
 902 }
 903
 904 static int is_legal_op(struct ftrace_event_field *field, int op)
 905 {
 906         if (is_string_field(field) &&
 907             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 908                 return 0;
 909         if (!is_string_field(field) && op == OP_GLOB)
 910                 return 0;
 911
 912         return 1;
 913 }
 914
 915 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 916                                              int field_is_signed)
 917 {
 918         filter_pred_fn_t fn = NULL;
 919
 920         switch (field_size) {
 921         case 8:
 922                 if (op == OP_EQ || op == OP_NE)
 923                         fn = filter_pred_64;
 924                 else if (field_is_signed)
 925                         fn = filter_pred_s64;
 926                 else
 927                         fn = filter_pred_u64;
 928                 break;
 929         case 4:
 930                 if (op == OP_EQ || op == OP_NE)
 931                         fn = filter_pred_32;
 932                 else if (field_is_signed)
 933                         fn = filter_pred_s32;
 934                 else
 935                         fn = filter_pred_u32;
 936                 break;
 937         case 2:
 938                 if (op == OP_EQ || op == OP_NE)
 939                         fn = filter_pred_16;
 940                 else if (field_is_signed)
 941                         fn = filter_pred_s16;
 942                 else
 943                         fn = filter_pred_u16;
 944                 break;
 945         case 1:
 946                 if (op == OP_EQ || op == OP_NE)
 947                         fn = filter_pred_8;
 948                 else if (field_is_signed)
 949                         fn = filter_pred_s8;
 950                 else
 951                         fn = filter_pred_u8;
 952                 break;
 953         }
 954
 955         return fn;
 956 }
 957
 958 static int init_pred(struct filter_parse_state *ps,
 959                      struct ftrace_event_field *field,
 960                      struct filter_pred *pred)
 961
 962 {
 963         filter_pred_fn_t fn = filter_pred_none;
 964         unsigned long long val;
 965         int ret;
 966
 967         pred->offset = field->offset;
 968
 969         if (!is_legal_op(field, pred->op)) {
 970                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 971                 return -EINVAL;
 972         }
 973
 974         if (is_string_field(field)) {
 975                 filter_build_regex(pred);
 976
 977                 if (field->filter_type == FILTER_STATIC_STRING) {
 978                         fn = filter_pred_string;
 979                         pred->regex.field_len = field->size;
 980                 } else if (field->filter_type == FILTER_DYN_STRING)
 981                         fn = filter_pred_strloc;
 982                 else
 983                         fn = filter_pred_pchar;
 984         } else {
 985                 if (field->is_signed)
 986                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 987                 else
 988                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 989                 if (ret) {
 990                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 991                         return -EINVAL;
 992                 }
 993                 pred->val = val;
 994
 995                 fn = select_comparison_fn(pred->op, field->size,
 996                                           field->is_signed);
 997                 if (!fn) {
 998                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 999                         return -EINVAL;
1000                 }
1001         }
1002
1003         if (pred->op == OP_NE)
1004                 pred->not = 1;
1005
1006         pred->fn = fn;
1007         return 0;
1008 }
1009
1010 static void parse_init(struct filter_parse_state *ps,
1011                        struct filter_op *ops,
1012                        char *infix_string)
1013 {
1014         memset(ps, '\0', sizeof(*ps));
1015
1016         ps->infix.string = infix_string;
1017         ps->infix.cnt = strlen(infix_string);
1018         ps->ops = ops;
1019
1020         INIT_LIST_HEAD(&ps->opstack);
1021         INIT_LIST_HEAD(&ps->postfix);
1022 }
1023
1024 static char infix_next(struct filter_parse_state *ps)
1025 {
1026         ps->infix.cnt--;
1027
1028         return ps->infix.string[ps->infix.tail++];
1029 }
1030
1031 static char infix_peek(struct filter_parse_state *ps)
1032 {
1033         if (ps->infix.tail == strlen(ps->infix.string))
1034                 return 0;
1035
1036         return ps->infix.string[ps->infix.tail];
1037 }
1038
1039 static void infix_advance(struct filter_parse_state *ps)
1040 {
1041         ps->infix.cnt--;
1042         ps->infix.tail++;
1043 }
1044
1045 static inline int is_precedence_lower(struct filter_parse_state *ps,
1046                                       int a, int b)
1047 {
1048         return ps->ops[a].precedence < ps->ops[b].precedence;
1049 }
1050
1051 static inline int is_op_char(struct filter_parse_state *ps, char c)
1052 {
1053         int i;
1054
1055         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1056                 if (ps->ops[i].string[0] == c)
1057                         return 1;
1058         }
1059
1060         return 0;
1061 }
1062
1063 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1064 {
1065         char nextc = infix_peek(ps);
1066         char opstr[3];
1067         int i;
1068
1069         opstr[0] = firstc;
1070         opstr[1] = nextc;
1071         opstr[2] = '\0';
1072
1073         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1074                 if (!strcmp(opstr, ps->ops[i].string)) {
1075                         infix_advance(ps);
1076                         return ps->ops[i].id;
1077                 }
1078         }
1079
1080         opstr[1] = '\0';
1081
1082         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1083                 if (!strcmp(opstr, ps->ops[i].string))
1084                         return ps->ops[i].id;
1085         }
1086
1087         return OP_NONE;
1088 }
1089
1090 static inline void clear_operand_string(struct filter_parse_state *ps)
1091 {
1092         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1093         ps->operand.tail = 0;
1094 }
1095
1096 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1097 {
1098         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1099                 return -EINVAL;
1100
1101         ps->operand.string[ps->operand.tail++] = c;
1102
1103         return 0;
1104 }
1105
1106 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1107 {
1108         struct opstack_op *opstack_op;
1109
1110         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1111         if (!opstack_op)
1112                 return -ENOMEM;
1113
1114         opstack_op->op = op;
1115         list_add(&opstack_op->list, &ps->opstack);
1116
1117         return 0;
1118 }
1119
1120 static int filter_opstack_empty(struct filter_parse_state *ps)
1121 {
1122         return list_empty(&ps->opstack);
1123 }
1124
1125 static int filter_opstack_top(struct filter_parse_state *ps)
1126 {
1127         struct opstack_op *opstack_op;
1128
1129         if (filter_opstack_empty(ps))
1130                 return OP_NONE;
1131
1132         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1133
1134         return opstack_op->op;
1135 }
1136
1137 static int filter_opstack_pop(struct filter_parse_state *ps)
1138 {
1139         struct opstack_op *opstack_op;
1140         int op;
1141
1142         if (filter_opstack_empty(ps))
1143                 return OP_NONE;
1144
1145         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1146         op = opstack_op->op;
1147         list_del(&opstack_op->list);
1148
1149         kfree(opstack_op);
1150
1151         return op;
1152 }
1153
1154 static void filter_opstack_clear(struct filter_parse_state *ps)
1155 {
1156         while (!filter_opstack_empty(ps))
1157                 filter_opstack_pop(ps);
1158 }
1159
1160 static char *curr_operand(struct filter_parse_state *ps)
1161 {
1162         return ps->operand.string;
1163 }
1164
1165 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1166 {
1167         struct postfix_elt *elt;
1168
1169         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1170         if (!elt)
1171                 return -ENOMEM;
1172
1173         elt->op = OP_NONE;
1174         elt->operand = kstrdup(operand, GFP_KERNEL);
1175         if (!elt->operand) {
1176                 kfree(elt);
1177                 return -ENOMEM;
1178         }
1179
1180         list_add_tail(&elt->list, &ps->postfix);
1181
1182         return 0;
1183 }
1184
1185 static int postfix_append_op(struct filter_parse_state *ps, int op)
1186 {
1187         struct postfix_elt *elt;
1188
1189         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1190         if (!elt)
1191                 return -ENOMEM;
1192
1193         elt->op = op;
1194         elt->operand = NULL;
1195
1196         list_add_tail(&elt->list, &ps->postfix);
1197
1198         return 0;
1199 }
1200
1201 static void postfix_clear(struct filter_parse_state *ps)
1202 {
1203         struct postfix_elt *elt;
1204
1205         while (!list_empty(&ps->postfix)) {
1206                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1207                 list_del(&elt->list);
1208                 kfree(elt->operand);
1209                 kfree(elt);
1210         }
1211 }
1212
1213 static int filter_parse(struct filter_parse_state *ps)
1214 {
1215         int in_string = 0;
1216         int op, top_op;
1217         char ch;
1218
1219         while ((ch = infix_next(ps))) {
1220                 if (ch == '"') {
1221                         in_string ^= 1;
1222                         continue;
1223                 }
1224
1225                 if (in_string)
1226                         goto parse_operand;
1227
1228                 if (isspace(ch))
1229                         continue;
1230
1231                 if (is_op_char(ps, ch)) {
1232                         op = infix_get_op(ps, ch);
1233                         if (op == OP_NONE) {
1234                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1235                                 return -EINVAL;
1236                         }
1237
1238                         if (strlen(curr_operand(ps))) {
1239                                 postfix_append_operand(ps, curr_operand(ps));
1240                                 clear_operand_string(ps);
1241                         }
1242
1243                         while (!filter_opstack_empty(ps)) {
1244                                 top_op = filter_opstack_top(ps);
1245                                 if (!is_precedence_lower(ps, top_op, op)) {
1246                                         top_op = filter_opstack_pop(ps);
1247                                         postfix_append_op(ps, top_op);
1248                                         continue;
1249                                 }
1250                                 break;
1251                         }
1252
1253                         filter_opstack_push(ps, op);
1254                         continue;
1255                 }
1256
1257                 if (ch == '(') {
1258                         filter_opstack_push(ps, OP_OPEN_PAREN);
1259                         continue;
1260                 }
1261
1262                 if (ch == ')') {
1263                         if (strlen(curr_operand(ps))) {
1264                                 postfix_append_operand(ps, curr_operand(ps));
1265                                 clear_operand_string(ps);
1266                         }
1267
1268                         top_op = filter_opstack_pop(ps);
1269                         while (top_op != OP_NONE) {
1270                                 if (top_op == OP_OPEN_PAREN)
1271                                         break;
1272                                 postfix_append_op(ps, top_op);
1273                                 top_op = filter_opstack_pop(ps);
1274                         }
1275                         if (top_op == OP_NONE) {
1276                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1277                                 return -EINVAL;
1278                         }
1279                         continue;
1280                 }
1281 parse_operand:
1282                 if (append_operand_char(ps, ch)) {
1283                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1284                         return -EINVAL;
1285                 }
1286         }
1287
1288         if (strlen(curr_operand(ps)))
1289                 postfix_append_operand(ps, curr_operand(ps));
1290
1291         while (!filter_opstack_empty(ps)) {
1292                 top_op = filter_opstack_pop(ps);
1293                 if (top_op == OP_NONE)
1294                         break;
1295                 if (top_op == OP_OPEN_PAREN) {
1296                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1297                         return -EINVAL;
1298                 }
1299                 postfix_append_op(ps, top_op);
1300         }
1301
1302         return 0;
1303 }
1304
1305 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1306                                        struct ftrace_event_call *call,
1307                                        int op, char *operand1, char *operand2)
1308 {
1309         struct ftrace_event_field *field;
1310         static struct filter_pred pred;
1311
1312         memset(&pred, 0, sizeof(pred));
1313         pred.op = op;
1314
1315         if (op == OP_AND || op == OP_OR)
1316                 return &pred;
1317
1318         if (!operand1 || !operand2) {
1319                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1320                 return NULL;
1321         }
1322
1323         field = find_event_field(call, operand1);
1324         if (!field) {
1325                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1326                 return NULL;
1327         }
1328
1329         strcpy(pred.regex.pattern, operand2);
1330         pred.regex.len = strlen(pred.regex.pattern);
1331
1332         return init_pred(ps, field, &pred) ? NULL : &pred;
1333 }
1334
1335 static int check_preds(struct filter_parse_state *ps)
1336 {
1337         int n_normal_preds = 0, n_logical_preds = 0;
1338         struct postfix_elt *elt;
1339
1340         list_for_each_entry(elt, &ps->postfix, list) {
1341                 if (elt->op == OP_NONE)
1342                         continue;
1343
1344                 if (elt->op == OP_AND || elt->op == OP_OR) {
1345                         n_logical_preds++;
1346                         continue;
1347                 }
1348                 n_normal_preds++;
1349         }
1350
1351         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1352                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1353                 return -EINVAL;
1354         }
1355
1356         return 0;
1357 }
1358
1359 static int count_preds(struct filter_parse_state *ps)
1360 {
1361         struct postfix_elt *elt;
1362         int n_preds = 0;
1363
1364         list_for_each_entry(elt, &ps->postfix, list) {
1365                 if (elt->op == OP_NONE)
1366                         continue;
1367                 n_preds++;
1368         }
1369
1370         return n_preds;
1371 }
1372
1373 struct check_pred_data {
1374         int count;
1375         int max;
1376 };
1377
1378 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1379                               int *err, void *data)
1380 {
1381         struct check_pred_data *d = data;
1382
1383         if (WARN_ON(d->count++ > d->max)) {
1384                 *err = -EINVAL;
1385                 return WALK_PRED_ABORT;
1386         }
1387         return WALK_PRED_DEFAULT;
1388 }
1389
1390 /*
1391  * The tree is walked at filtering of an event. If the tree is not correctly
1392  * built, it may cause an infinite loop. Check here that the tree does
1393  * indeed terminate.
1394  */
1395 static int check_pred_tree(struct event_filter *filter,
1396                            struct filter_pred *root)
1397 {
1398         struct check_pred_data data = {
1399                 /*
1400                  * The max that we can hit a node is three times.
1401                  * Once going down, once coming up from left, and
1402                  * once coming up from right. This is more than enough
1403                  * since leafs are only hit a single time.
1404                  */
1405                 .max   = 3 * filter->n_preds,
1406                 .count = 0,
1407         };
1408
1409         return walk_pred_tree(filter->preds, root,
1410                               check_pred_tree_cb, &data);
1411 }
1412
1413 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1414                           int *err, void *data)
1415 {
1416         int *count = data;
1417
1418         if ((move == MOVE_DOWN) &&
1419             (pred->left == FILTER_PRED_INVALID))
1420                 (*count)++;
1421
1422         return WALK_PRED_DEFAULT;
1423 }
1424
1425 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1426 {
1427         int count = 0, ret;
1428
1429         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1430         WARN_ON(ret);
1431         return count;
1432 }
1433
1434 struct fold_pred_data {
1435         struct filter_pred *root;
1436         int count;
1437         int children;
1438 };
1439
1440 static int fold_pred_cb(enum move_type move, struct filter_pred *pred,
1441                         int *err, void *data)
1442 {
1443         struct fold_pred_data *d = data;
1444         struct filter_pred *root = d->root;
1445
1446         if (move != MOVE_DOWN)
1447                 return WALK_PRED_DEFAULT;
1448         if (pred->left != FILTER_PRED_INVALID)
1449                 return WALK_PRED_DEFAULT;
1450
1451         if (WARN_ON(d->count == d->children)) {
1452                 *err = -EINVAL;
1453                 return WALK_PRED_ABORT;
1454         }
1455
1456         pred->index &= ~FILTER_PRED_FOLD;
1457         root->ops[d->count++] = pred->index;
1458         return WALK_PRED_DEFAULT;
1459 }
1460
1461 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1462 {
1463         struct fold_pred_data data = {
1464                 .root  = root,
1465                 .count = 0,
1466         };
1467         int children;
1468
1469         /* No need to keep the fold flag */
1470         root->index &= ~FILTER_PRED_FOLD;
1471
1472         /* If the root is a leaf then do nothing */
1473         if (root->left == FILTER_PRED_INVALID)
1474                 return 0;
1475
1476         /* count the children */
1477         children = count_leafs(preds, &preds[root->left]);
1478         children += count_leafs(preds, &preds[root->right]);
1479
1480         root->ops = kzalloc(sizeof(*root->ops) * children, GFP_KERNEL);
1481         if (!root->ops)
1482                 return -ENOMEM;
1483
1484         root->val = children;
1485         data.children = children;
1486         return walk_pred_tree(preds, root, fold_pred_cb, &data);
1487 }
1488
1489 static int fold_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1490                              int *err, void *data)
1491 {
1492         struct filter_pred *preds = data;
1493
1494         if (move != MOVE_DOWN)
1495                 return WALK_PRED_DEFAULT;
1496         if (!(pred->index & FILTER_PRED_FOLD))
1497                 return WALK_PRED_DEFAULT;
1498
1499         *err = fold_pred(preds, pred);
1500         if (*err)
1501                 return WALK_PRED_ABORT;
1502
1503         /* eveyrhing below is folded, continue with parent */
1504         return WALK_PRED_PARENT;
1505 }
1506
1507 /*
1508  * To optimize the processing of the ops, if we have several "ors" or
1509  * "ands" together, we can put them in an array and process them all
1510  * together speeding up the filter logic.
1511  */
1512 static int fold_pred_tree(struct event_filter *filter,
1513                            struct filter_pred *root)
1514 {
1515         return walk_pred_tree(filter->preds, root, fold_pred_tree_cb,
1516                               filter->preds);
1517 }
1518
1519 static int replace_preds(struct ftrace_event_call *call,
1520                          struct event_filter *filter,
1521                          struct filter_parse_state *ps,
1522                          char *filter_string,
1523                          bool dry_run)
1524 {
1525         char *operand1 = NULL, *operand2 = NULL;
1526         struct filter_pred *pred;
1527         struct filter_pred *root;
1528         struct postfix_elt *elt;
1529         struct pred_stack stack = { }; /* init to NULL */
1530         int err;
1531         int n_preds = 0;
1532
1533         n_preds = count_preds(ps);
1534         if (n_preds >= MAX_FILTER_PRED) {
1535                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1536                 return -ENOSPC;
1537         }
1538
1539         err = check_preds(ps);
1540         if (err)
1541                 return err;
1542
1543         if (!dry_run) {
1544                 err = __alloc_pred_stack(&stack, n_preds);
1545                 if (err)
1546                         return err;
1547                 err = __alloc_preds(filter, n_preds);
1548                 if (err)
1549                         goto fail;
1550         }
1551
1552         n_preds = 0;
1553         list_for_each_entry(elt, &ps->postfix, list) {
1554                 if (elt->op == OP_NONE) {
1555                         if (!operand1)
1556                                 operand1 = elt->operand;
1557                         else if (!operand2)
1558                                 operand2 = elt->operand;
1559                         else {
1560                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1561                                 err = -EINVAL;
1562                                 goto fail;
1563                         }
1564                         continue;
1565                 }
1566
1567                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1568                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1569                         err = -ENOSPC;
1570                         goto fail;
1571                 }
1572
1573                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1574                 if (!pred) {
1575                         err = -EINVAL;
1576                         goto fail;
1577                 }
1578
1579                 if (!dry_run) {
1580                         err = filter_add_pred(ps, filter, pred, &stack);
1581                         if (err)
1582                                 goto fail;
1583                 }
1584
1585                 operand1 = operand2 = NULL;
1586         }
1587
1588         if (!dry_run) {
1589                 /* We should have one item left on the stack */
1590                 pred = __pop_pred_stack(&stack);
1591                 if (!pred)
1592                         return -EINVAL;
1593                 /* This item is where we start from in matching */
1594                 root = pred;
1595                 /* Make sure the stack is empty */
1596                 pred = __pop_pred_stack(&stack);
1597                 if (WARN_ON(pred)) {
1598                         err = -EINVAL;
1599                         filter->root = NULL;
1600                         goto fail;
1601                 }
1602                 err = check_pred_tree(filter, root);
1603                 if (err)
1604                         goto fail;
1605
1606                 /* Optimize the tree */
1607                 err = fold_pred_tree(filter, root);
1608                 if (err)
1609                         goto fail;
1610
1611                 /* We don't set root until we know it works */
1612                 barrier();
1613                 filter->root = root;
1614         }
1615
1616         err = 0;
1617 fail:
1618         __free_pred_stack(&stack);
1619         return err;
1620 }
1621
1622 struct filter_list {
1623         struct list_head        list;
1624         struct event_filter     *filter;
1625 };
1626
1627 static int replace_system_preds(struct event_subsystem *system,
1628                                 struct filter_parse_state *ps,
1629                                 char *filter_string)
1630 {
1631         struct ftrace_event_call *call;
1632         struct filter_list *filter_item;
1633         struct filter_list *tmp;
1634         LIST_HEAD(filter_list);
1635         bool fail = true;
1636         int err;
1637
1638         list_for_each_entry(call, &ftrace_events, list) {
1639
1640                 if (strcmp(call->class->system, system->name) != 0)
1641                         continue;
1642
1643                 /*
1644                  * Try to see if the filter can be applied
1645                  *  (filter arg is ignored on dry_run)
1646                  */
1647                 err = replace_preds(call, NULL, ps, filter_string, true);
1648                 if (err)
1649                         goto fail;
1650         }
1651
1652         list_for_each_entry(call, &ftrace_events, list) {
1653                 struct event_filter *filter;
1654
1655                 if (strcmp(call->class->system, system->name) != 0)
1656                         continue;
1657
1658                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1659                 if (!filter_item)
1660                         goto fail_mem;
1661
1662                 list_add_tail(&filter_item->list, &filter_list);
1663
1664                 filter_item->filter = __alloc_filter();
1665                 if (!filter_item->filter)
1666                         goto fail_mem;
1667                 filter = filter_item->filter;
1668
1669                 /* Can only fail on no memory */
1670                 err = replace_filter_string(filter, filter_string);
1671                 if (err)
1672                         goto fail_mem;
1673
1674                 err = replace_preds(call, filter, ps, filter_string, false);
1675                 if (err) {
1676                         filter_disable(call);
1677                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1678                         append_filter_err(ps, filter);
1679                 } else
1680                         call->flags |= TRACE_EVENT_FL_FILTERED;
1681                 /*
1682                  * Regardless of if this returned an error, we still
1683                  * replace the filter for the call.
1684                  */
1685                 filter = call->filter;
1686                 call->filter = filter_item->filter;
1687                 filter_item->filter = filter;
1688
1689                 fail = false;
1690         }
1691
1692         if (fail)
1693                 goto fail;
1694
1695         /*
1696          * The calls can still be using the old filters.
1697          * Do a synchronize_sched() to ensure all calls are
1698          * done with them before we free them.
1699          */
1700         synchronize_sched();
1701         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1702                 __free_filter(filter_item->filter);
1703                 list_del(&filter_item->list);
1704                 kfree(filter_item);
1705         }
1706         return 0;
1707  fail:
1708         /* No call succeeded */
1709         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1710                 list_del(&filter_item->list);
1711                 kfree(filter_item);
1712         }
1713         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1714         return -EINVAL;
1715  fail_mem:
1716         /* If any call succeeded, we still need to sync */
1717         if (!fail)
1718                 synchronize_sched();
1719         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1720                 __free_filter(filter_item->filter);
1721                 list_del(&filter_item->list);
1722                 kfree(filter_item);
1723         }
1724         return -ENOMEM;
1725 }
1726
1727 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1728 {
1729         struct filter_parse_state *ps;
1730         struct event_filter *filter;
1731         struct event_filter *tmp;
1732         int err = 0;
1733
1734         mutex_lock(&event_mutex);
1735
1736         if (!strcmp(strstrip(filter_string), "0")) {
1737                 filter_disable(call);
1738                 filter = call->filter;
1739                 if (!filter)
1740                         goto out_unlock;
1741                 call->filter = NULL;
1742                 /* Make sure the filter is not being used */
1743                 synchronize_sched();
1744                 __free_filter(filter);
1745                 goto out_unlock;
1746         }
1747
1748         err = -ENOMEM;
1749         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1750         if (!ps)
1751                 goto out_unlock;
1752
1753         filter = __alloc_filter();
1754         if (!filter) {
1755                 kfree(ps);
1756                 goto out_unlock;
1757         }
1758
1759         replace_filter_string(filter, filter_string);
1760
1761         parse_init(ps, filter_ops, filter_string);
1762         err = filter_parse(ps);
1763         if (err) {
1764                 append_filter_err(ps, filter);
1765                 goto out;
1766         }
1767
1768         err = replace_preds(call, filter, ps, filter_string, false);
1769         if (err) {
1770                 filter_disable(call);
1771                 append_filter_err(ps, filter);
1772         } else
1773                 call->flags |= TRACE_EVENT_FL_FILTERED;
1774 out:
1775         /*
1776          * Always swap the call filter with the new filter
1777          * even if there was an error. If there was an error
1778          * in the filter, we disable the filter and show the error
1779          * string
1780          */
1781         tmp = call->filter;
1782         call->filter = filter;
1783         if (tmp) {
1784                 /* Make sure the call is done with the filter */
1785                 synchronize_sched();
1786                 __free_filter(tmp);
1787         }
1788         filter_opstack_clear(ps);
1789         postfix_clear(ps);
1790         kfree(ps);
1791 out_unlock:
1792         mutex_unlock(&event_mutex);
1793
1794         return err;
1795 }
1796
1797 int apply_subsystem_event_filter(struct event_subsystem *system,
1798                                  char *filter_string)
1799 {
1800         struct filter_parse_state *ps;
1801         struct event_filter *filter;
1802         int err = 0;
1803
1804         mutex_lock(&event_mutex);
1805
1806         /* Make sure the system still has events */
1807         if (!system->nr_events) {
1808                 err = -ENODEV;
1809                 goto out_unlock;
1810         }
1811
1812         if (!strcmp(strstrip(filter_string), "0")) {
1813                 filter_free_subsystem_preds(system);
1814                 remove_filter_string(system->filter);
1815                 filter = system->filter;
1816                 system->filter = NULL;
1817                 /* Ensure all filters are no longer used */
1818                 synchronize_sched();
1819                 filter_free_subsystem_filters(system);
1820                 __free_filter(filter);
1821                 goto out_unlock;
1822         }
1823
1824         err = -ENOMEM;
1825         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1826         if (!ps)
1827                 goto out_unlock;
1828
1829         filter = __alloc_filter();
1830         if (!filter)
1831                 goto out;
1832
1833         replace_filter_string(filter, filter_string);
1834         /*
1835          * No event actually uses the system filter
1836          * we can free it without synchronize_sched().
1837          */
1838         __free_filter(system->filter);
1839         system->filter = filter;
1840
1841         parse_init(ps, filter_ops, filter_string);
1842         err = filter_parse(ps);
1843         if (err) {
1844                 append_filter_err(ps, system->filter);
1845                 goto out;
1846         }
1847
1848         err = replace_system_preds(system, ps, filter_string);
1849         if (err)
1850                 append_filter_err(ps, system->filter);
1851
1852 out:
1853         filter_opstack_clear(ps);
1854         postfix_clear(ps);
1855         kfree(ps);
1856 out_unlock:
1857         mutex_unlock(&event_mutex);
1858
1859         return err;
1860 }
1861
1862 #ifdef CONFIG_PERF_EVENTS
1863
1864 void ftrace_profile_free_filter(struct perf_event *event)
1865 {
1866         struct event_filter *filter = event->filter;
1867
1868         event->filter = NULL;
1869         __free_filter(filter);
1870 }
1871
1872 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1873                               char *filter_str)
1874 {
1875         int err;
1876         struct event_filter *filter;
1877         struct filter_parse_state *ps;
1878         struct ftrace_event_call *call;
1879
1880         mutex_lock(&event_mutex);
1881
1882         call = event->tp_event;
1883
1884         err = -EINVAL;
1885         if (!call)
1886                 goto out_unlock;
1887
1888         err = -EEXIST;
1889         if (event->filter)
1890                 goto out_unlock;
1891
1892         filter = __alloc_filter();
1893         if (!filter) {
1894                 err = PTR_ERR(filter);
1895                 goto out_unlock;
1896         }
1897
1898         err = -ENOMEM;
1899         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1900         if (!ps)
1901                 goto free_filter;
1902
1903         parse_init(ps, filter_ops, filter_str);
1904         err = filter_parse(ps);
1905         if (err)
1906                 goto free_ps;
1907
1908         err = replace_preds(call, filter, ps, filter_str, false);
1909         if (!err)
1910                 event->filter = filter;
1911
1912 free_ps:
1913         filter_opstack_clear(ps);
1914         postfix_clear(ps);
1915         kfree(ps);
1916
1917 free_filter:
1918         if (err)
1919                 __free_filter(filter);
1920
1921 out_unlock:
1922         mutex_unlock(&event_mutex);
1923
1924         return err;
1925 }
1926
1927 #endif /* CONFIG_PERF_EVENTS */
1928