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 #ifdef CONFIG_FTRACE_STARTUP_TEST
1333         pred.field = field;
1334 #endif
1335         return init_pred(ps, field, &pred) ? NULL : &pred;
1336 }
1337
1338 static int check_preds(struct filter_parse_state *ps)
1339 {
1340         int n_normal_preds = 0, n_logical_preds = 0;
1341         struct postfix_elt *elt;
1342
1343         list_for_each_entry(elt, &ps->postfix, list) {
1344                 if (elt->op == OP_NONE)
1345                         continue;
1346
1347                 if (elt->op == OP_AND || elt->op == OP_OR) {
1348                         n_logical_preds++;
1349                         continue;
1350                 }
1351                 n_normal_preds++;
1352         }
1353
1354         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1355                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1356                 return -EINVAL;
1357         }
1358
1359         return 0;
1360 }
1361
1362 static int count_preds(struct filter_parse_state *ps)
1363 {
1364         struct postfix_elt *elt;
1365         int n_preds = 0;
1366
1367         list_for_each_entry(elt, &ps->postfix, list) {
1368                 if (elt->op == OP_NONE)
1369                         continue;
1370                 n_preds++;
1371         }
1372
1373         return n_preds;
1374 }
1375
1376 struct check_pred_data {
1377         int count;
1378         int max;
1379 };
1380
1381 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1382                               int *err, void *data)
1383 {
1384         struct check_pred_data *d = data;
1385
1386         if (WARN_ON(d->count++ > d->max)) {
1387                 *err = -EINVAL;
1388                 return WALK_PRED_ABORT;
1389         }
1390         return WALK_PRED_DEFAULT;
1391 }
1392
1393 /*
1394  * The tree is walked at filtering of an event. If the tree is not correctly
1395  * built, it may cause an infinite loop. Check here that the tree does
1396  * indeed terminate.
1397  */
1398 static int check_pred_tree(struct event_filter *filter,
1399                            struct filter_pred *root)
1400 {
1401         struct check_pred_data data = {
1402                 /*
1403                  * The max that we can hit a node is three times.
1404                  * Once going down, once coming up from left, and
1405                  * once coming up from right. This is more than enough
1406                  * since leafs are only hit a single time.
1407                  */
1408                 .max   = 3 * filter->n_preds,
1409                 .count = 0,
1410         };
1411
1412         return walk_pred_tree(filter->preds, root,
1413                               check_pred_tree_cb, &data);
1414 }
1415
1416 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1417                           int *err, void *data)
1418 {
1419         int *count = data;
1420
1421         if ((move == MOVE_DOWN) &&
1422             (pred->left == FILTER_PRED_INVALID))
1423                 (*count)++;
1424
1425         return WALK_PRED_DEFAULT;
1426 }
1427
1428 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1429 {
1430         int count = 0, ret;
1431
1432         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1433         WARN_ON(ret);
1434         return count;
1435 }
1436
1437 struct fold_pred_data {
1438         struct filter_pred *root;
1439         int count;
1440         int children;
1441 };
1442
1443 static int fold_pred_cb(enum move_type move, struct filter_pred *pred,
1444                         int *err, void *data)
1445 {
1446         struct fold_pred_data *d = data;
1447         struct filter_pred *root = d->root;
1448
1449         if (move != MOVE_DOWN)
1450                 return WALK_PRED_DEFAULT;
1451         if (pred->left != FILTER_PRED_INVALID)
1452                 return WALK_PRED_DEFAULT;
1453
1454         if (WARN_ON(d->count == d->children)) {
1455                 *err = -EINVAL;
1456                 return WALK_PRED_ABORT;
1457         }
1458
1459         pred->index &= ~FILTER_PRED_FOLD;
1460         root->ops[d->count++] = pred->index;
1461         return WALK_PRED_DEFAULT;
1462 }
1463
1464 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1465 {
1466         struct fold_pred_data data = {
1467                 .root  = root,
1468                 .count = 0,
1469         };
1470         int children;
1471
1472         /* No need to keep the fold flag */
1473         root->index &= ~FILTER_PRED_FOLD;
1474
1475         /* If the root is a leaf then do nothing */
1476         if (root->left == FILTER_PRED_INVALID)
1477                 return 0;
1478
1479         /* count the children */
1480         children = count_leafs(preds, &preds[root->left]);
1481         children += count_leafs(preds, &preds[root->right]);
1482
1483         root->ops = kzalloc(sizeof(*root->ops) * children, GFP_KERNEL);
1484         if (!root->ops)
1485                 return -ENOMEM;
1486
1487         root->val = children;
1488         data.children = children;
1489         return walk_pred_tree(preds, root, fold_pred_cb, &data);
1490 }
1491
1492 static int fold_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1493                              int *err, void *data)
1494 {
1495         struct filter_pred *preds = data;
1496
1497         if (move != MOVE_DOWN)
1498                 return WALK_PRED_DEFAULT;
1499         if (!(pred->index & FILTER_PRED_FOLD))
1500                 return WALK_PRED_DEFAULT;
1501
1502         *err = fold_pred(preds, pred);
1503         if (*err)
1504                 return WALK_PRED_ABORT;
1505
1506         /* eveyrhing below is folded, continue with parent */
1507         return WALK_PRED_PARENT;
1508 }
1509
1510 /*
1511  * To optimize the processing of the ops, if we have several "ors" or
1512  * "ands" together, we can put them in an array and process them all
1513  * together speeding up the filter logic.
1514  */
1515 static int fold_pred_tree(struct event_filter *filter,
1516                            struct filter_pred *root)
1517 {
1518         return walk_pred_tree(filter->preds, root, fold_pred_tree_cb,
1519                               filter->preds);
1520 }
1521
1522 static int replace_preds(struct ftrace_event_call *call,
1523                          struct event_filter *filter,
1524                          struct filter_parse_state *ps,
1525                          char *filter_string,
1526                          bool dry_run)
1527 {
1528         char *operand1 = NULL, *operand2 = NULL;
1529         struct filter_pred *pred;
1530         struct filter_pred *root;
1531         struct postfix_elt *elt;
1532         struct pred_stack stack = { }; /* init to NULL */
1533         int err;
1534         int n_preds = 0;
1535
1536         n_preds = count_preds(ps);
1537         if (n_preds >= MAX_FILTER_PRED) {
1538                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1539                 return -ENOSPC;
1540         }
1541
1542         err = check_preds(ps);
1543         if (err)
1544                 return err;
1545
1546         if (!dry_run) {
1547                 err = __alloc_pred_stack(&stack, n_preds);
1548                 if (err)
1549                         return err;
1550                 err = __alloc_preds(filter, n_preds);
1551                 if (err)
1552                         goto fail;
1553         }
1554
1555         n_preds = 0;
1556         list_for_each_entry(elt, &ps->postfix, list) {
1557                 if (elt->op == OP_NONE) {
1558                         if (!operand1)
1559                                 operand1 = elt->operand;
1560                         else if (!operand2)
1561                                 operand2 = elt->operand;
1562                         else {
1563                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1564                                 err = -EINVAL;
1565                                 goto fail;
1566                         }
1567                         continue;
1568                 }
1569
1570                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1571                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1572                         err = -ENOSPC;
1573                         goto fail;
1574                 }
1575
1576                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1577                 if (!pred) {
1578                         err = -EINVAL;
1579                         goto fail;
1580                 }
1581
1582                 if (!dry_run) {
1583                         err = filter_add_pred(ps, filter, pred, &stack);
1584                         if (err)
1585                                 goto fail;
1586                 }
1587
1588                 operand1 = operand2 = NULL;
1589         }
1590
1591         if (!dry_run) {
1592                 /* We should have one item left on the stack */
1593                 pred = __pop_pred_stack(&stack);
1594                 if (!pred)
1595                         return -EINVAL;
1596                 /* This item is where we start from in matching */
1597                 root = pred;
1598                 /* Make sure the stack is empty */
1599                 pred = __pop_pred_stack(&stack);
1600                 if (WARN_ON(pred)) {
1601                         err = -EINVAL;
1602                         filter->root = NULL;
1603                         goto fail;
1604                 }
1605                 err = check_pred_tree(filter, root);
1606                 if (err)
1607                         goto fail;
1608
1609                 /* Optimize the tree */
1610                 err = fold_pred_tree(filter, root);
1611                 if (err)
1612                         goto fail;
1613
1614                 /* We don't set root until we know it works */
1615                 barrier();
1616                 filter->root = root;
1617         }
1618
1619         err = 0;
1620 fail:
1621         __free_pred_stack(&stack);
1622         return err;
1623 }
1624
1625 struct filter_list {
1626         struct list_head        list;
1627         struct event_filter     *filter;
1628 };
1629
1630 static int replace_system_preds(struct event_subsystem *system,
1631                                 struct filter_parse_state *ps,
1632                                 char *filter_string)
1633 {
1634         struct ftrace_event_call *call;
1635         struct filter_list *filter_item;
1636         struct filter_list *tmp;
1637         LIST_HEAD(filter_list);
1638         bool fail = true;
1639         int err;
1640
1641         list_for_each_entry(call, &ftrace_events, list) {
1642
1643                 if (strcmp(call->class->system, system->name) != 0)
1644                         continue;
1645
1646                 /*
1647                  * Try to see if the filter can be applied
1648                  *  (filter arg is ignored on dry_run)
1649                  */
1650                 err = replace_preds(call, NULL, ps, filter_string, true);
1651                 if (err)
1652                         call->flags |= TRACE_EVENT_FL_NO_SET_FILTER;
1653                 else
1654                         call->flags &= ~TRACE_EVENT_FL_NO_SET_FILTER;
1655         }
1656
1657         list_for_each_entry(call, &ftrace_events, list) {
1658                 struct event_filter *filter;
1659
1660                 if (strcmp(call->class->system, system->name) != 0)
1661                         continue;
1662
1663                 if (call->flags & TRACE_EVENT_FL_NO_SET_FILTER)
1664                         continue;
1665
1666                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1667                 if (!filter_item)
1668                         goto fail_mem;
1669
1670                 list_add_tail(&filter_item->list, &filter_list);
1671
1672                 filter_item->filter = __alloc_filter();
1673                 if (!filter_item->filter)
1674                         goto fail_mem;
1675                 filter = filter_item->filter;
1676
1677                 /* Can only fail on no memory */
1678                 err = replace_filter_string(filter, filter_string);
1679                 if (err)
1680                         goto fail_mem;
1681
1682                 err = replace_preds(call, filter, ps, filter_string, false);
1683                 if (err) {
1684                         filter_disable(call);
1685                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1686                         append_filter_err(ps, filter);
1687                 } else
1688                         call->flags |= TRACE_EVENT_FL_FILTERED;
1689                 /*
1690                  * Regardless of if this returned an error, we still
1691                  * replace the filter for the call.
1692                  */
1693                 filter = call->filter;
1694                 rcu_assign_pointer(call->filter, filter_item->filter);
1695                 filter_item->filter = filter;
1696
1697                 fail = false;
1698         }
1699
1700         if (fail)
1701                 goto fail;
1702
1703         /*
1704          * The calls can still be using the old filters.
1705          * Do a synchronize_sched() to ensure all calls are
1706          * done with them before we free them.
1707          */
1708         synchronize_sched();
1709         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1710                 __free_filter(filter_item->filter);
1711                 list_del(&filter_item->list);
1712                 kfree(filter_item);
1713         }
1714         return 0;
1715  fail:
1716         /* No call succeeded */
1717         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1718                 list_del(&filter_item->list);
1719                 kfree(filter_item);
1720         }
1721         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1722         return -EINVAL;
1723  fail_mem:
1724         /* If any call succeeded, we still need to sync */
1725         if (!fail)
1726                 synchronize_sched();
1727         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1728                 __free_filter(filter_item->filter);
1729                 list_del(&filter_item->list);
1730                 kfree(filter_item);
1731         }
1732         return -ENOMEM;
1733 }
1734
1735 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1736 {
1737         struct filter_parse_state *ps;
1738         struct event_filter *filter;
1739         struct event_filter *tmp;
1740         int err = 0;
1741
1742         mutex_lock(&event_mutex);
1743
1744         if (!strcmp(strstrip(filter_string), "0")) {
1745                 filter_disable(call);
1746                 filter = call->filter;
1747                 if (!filter)
1748                         goto out_unlock;
1749                 RCU_INIT_POINTER(call->filter, NULL);
1750                 /* Make sure the filter is not being used */
1751                 synchronize_sched();
1752                 __free_filter(filter);
1753                 goto out_unlock;
1754         }
1755
1756         err = -ENOMEM;
1757         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1758         if (!ps)
1759                 goto out_unlock;
1760
1761         filter = __alloc_filter();
1762         if (!filter) {
1763                 kfree(ps);
1764                 goto out_unlock;
1765         }
1766
1767         replace_filter_string(filter, filter_string);
1768
1769         parse_init(ps, filter_ops, filter_string);
1770         err = filter_parse(ps);
1771         if (err) {
1772                 append_filter_err(ps, filter);
1773                 goto out;
1774         }
1775
1776         err = replace_preds(call, filter, ps, filter_string, false);
1777         if (err) {
1778                 filter_disable(call);
1779                 append_filter_err(ps, filter);
1780         } else
1781                 call->flags |= TRACE_EVENT_FL_FILTERED;
1782 out:
1783         /*
1784          * Always swap the call filter with the new filter
1785          * even if there was an error. If there was an error
1786          * in the filter, we disable the filter and show the error
1787          * string
1788          */
1789         tmp = call->filter;
1790         rcu_assign_pointer(call->filter, filter);
1791         if (tmp) {
1792                 /* Make sure the call is done with the filter */
1793                 synchronize_sched();
1794                 __free_filter(tmp);
1795         }
1796         filter_opstack_clear(ps);
1797         postfix_clear(ps);
1798         kfree(ps);
1799 out_unlock:
1800         mutex_unlock(&event_mutex);
1801
1802         return err;
1803 }
1804
1805 int apply_subsystem_event_filter(struct event_subsystem *system,
1806                                  char *filter_string)
1807 {
1808         struct filter_parse_state *ps;
1809         struct event_filter *filter;
1810         int err = 0;
1811
1812         mutex_lock(&event_mutex);
1813
1814         /* Make sure the system still has events */
1815         if (!system->nr_events) {
1816                 err = -ENODEV;
1817                 goto out_unlock;
1818         }
1819
1820         if (!strcmp(strstrip(filter_string), "0")) {
1821                 filter_free_subsystem_preds(system);
1822                 remove_filter_string(system->filter);
1823                 filter = system->filter;
1824                 system->filter = NULL;
1825                 /* Ensure all filters are no longer used */
1826                 synchronize_sched();
1827                 filter_free_subsystem_filters(system);
1828                 __free_filter(filter);
1829                 goto out_unlock;
1830         }
1831
1832         err = -ENOMEM;
1833         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1834         if (!ps)
1835                 goto out_unlock;
1836
1837         filter = __alloc_filter();
1838         if (!filter)
1839                 goto out;
1840
1841         replace_filter_string(filter, filter_string);
1842         /*
1843          * No event actually uses the system filter
1844          * we can free it without synchronize_sched().
1845          */
1846         __free_filter(system->filter);
1847         system->filter = filter;
1848
1849         parse_init(ps, filter_ops, filter_string);
1850         err = filter_parse(ps);
1851         if (err) {
1852                 append_filter_err(ps, system->filter);
1853                 goto out;
1854         }
1855
1856         err = replace_system_preds(system, ps, filter_string);
1857         if (err)
1858                 append_filter_err(ps, system->filter);
1859
1860 out:
1861         filter_opstack_clear(ps);
1862         postfix_clear(ps);
1863         kfree(ps);
1864 out_unlock:
1865         mutex_unlock(&event_mutex);
1866
1867         return err;
1868 }
1869
1870 #ifdef CONFIG_PERF_EVENTS
1871
1872 void ftrace_profile_free_filter(struct perf_event *event)
1873 {
1874         struct event_filter *filter = event->filter;
1875
1876         event->filter = NULL;
1877         __free_filter(filter);
1878 }
1879
1880 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1881                               char *filter_str)
1882 {
1883         int err;
1884         struct event_filter *filter;
1885         struct filter_parse_state *ps;
1886         struct ftrace_event_call *call;
1887
1888         mutex_lock(&event_mutex);
1889
1890         call = event->tp_event;
1891
1892         err = -EINVAL;
1893         if (!call)
1894                 goto out_unlock;
1895
1896         err = -EEXIST;
1897         if (event->filter)
1898                 goto out_unlock;
1899
1900         filter = __alloc_filter();
1901         if (!filter) {
1902                 err = PTR_ERR(filter);
1903                 goto out_unlock;
1904         }
1905
1906         err = -ENOMEM;
1907         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1908         if (!ps)
1909                 goto free_filter;
1910
1911         parse_init(ps, filter_ops, filter_str);
1912         err = filter_parse(ps);
1913         if (err)
1914                 goto free_ps;
1915
1916         err = replace_preds(call, filter, ps, filter_str, false);
1917         if (!err)
1918                 event->filter = filter;
1919
1920 free_ps:
1921         filter_opstack_clear(ps);
1922         postfix_clear(ps);
1923         kfree(ps);
1924
1925 free_filter:
1926         if (err)
1927                 __free_filter(filter);
1928
1929 out_unlock:
1930         mutex_unlock(&event_mutex);
1931
1932         return err;
1933 }
1934
1935 #endif /* CONFIG_PERF_EVENTS */
1936
1937 #ifdef CONFIG_FTRACE_STARTUP_TEST
1938
1939 #include <linux/types.h>
1940 #include <linux/tracepoint.h>
1941
1942 #define CREATE_TRACE_POINTS
1943 #include "trace_events_filter_test.h"
1944
1945 static int test_get_filter(char *filter_str, struct ftrace_event_call *call,
1946                            struct event_filter **pfilter)
1947 {
1948         struct event_filter *filter;
1949         struct filter_parse_state *ps;
1950         int err = -ENOMEM;
1951
1952         filter = __alloc_filter();
1953         if (!filter)
1954                 goto out;
1955
1956         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1957         if (!ps)
1958                 goto free_filter;
1959
1960         parse_init(ps, filter_ops, filter_str);
1961         err = filter_parse(ps);
1962         if (err)
1963                 goto free_ps;
1964
1965         err = replace_preds(call, filter, ps, filter_str, false);
1966         if (!err)
1967                 *pfilter = filter;
1968
1969  free_ps:
1970         filter_opstack_clear(ps);
1971         postfix_clear(ps);
1972         kfree(ps);
1973
1974  free_filter:
1975         if (err)
1976                 __free_filter(filter);
1977
1978  out:
1979         return err;
1980 }
1981
1982 #define DATA_REC(m, va, vb, vc, vd, ve, vf, vg, vh, nvisit) \
1983 { \
1984         .filter = FILTER, \
1985         .rec    = { .a = va, .b = vb, .c = vc, .d = vd, \
1986                     .e = ve, .f = vf, .g = vg, .h = vh }, \
1987         .match  = m, \
1988         .not_visited = nvisit, \
1989 }
1990 #define YES 1
1991 #define NO  0
1992
1993 static struct test_filter_data_t {
1994         char *filter;
1995         struct ftrace_raw_ftrace_test_filter rec;
1996         int match;
1997         char *not_visited;
1998 } test_filter_data[] = {
1999 #define FILTER "a == 1 && b == 1 && c == 1 && d == 1 && " \
2000                "e == 1 && f == 1 && g == 1 && h == 1"
2001         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, ""),
2002         DATA_REC(NO,  0, 1, 1, 1, 1, 1, 1, 1, "bcdefgh"),
2003         DATA_REC(NO,  1, 1, 1, 1, 1, 1, 1, 0, ""),
2004 #undef FILTER
2005 #define FILTER "a == 1 || b == 1 || c == 1 || d == 1 || " \
2006                "e == 1 || f == 1 || g == 1 || h == 1"
2007         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2008         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 0, 1, ""),
2009         DATA_REC(YES, 1, 0, 0, 0, 0, 0, 0, 0, "bcdefgh"),
2010 #undef FILTER
2011 #define FILTER "(a == 1 || b == 1) && (c == 1 || d == 1) && " \
2012                "(e == 1 || f == 1) && (g == 1 || h == 1)"
2013         DATA_REC(NO,  0, 0, 1, 1, 1, 1, 1, 1, "dfh"),
2014         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2015         DATA_REC(YES, 1, 0, 1, 0, 0, 1, 0, 1, "bd"),
2016         DATA_REC(NO,  1, 0, 1, 0, 0, 1, 0, 0, "bd"),
2017 #undef FILTER
2018 #define FILTER "(a == 1 && b == 1) || (c == 1 && d == 1) || " \
2019                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2020         DATA_REC(YES, 1, 0, 1, 1, 1, 1, 1, 1, "efgh"),
2021         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 1, 1, ""),
2022         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2023 #undef FILTER
2024 #define FILTER "(a == 1 && b == 1) && (c == 1 && d == 1) && " \
2025                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2026         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 0, "gh"),
2027         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2028         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, ""),
2029 #undef FILTER
2030 #define FILTER "((a == 1 || b == 1) || (c == 1 || d == 1) || " \
2031                "(e == 1 || f == 1)) && (g == 1 || h == 1)"
2032         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 1, "bcdef"),
2033         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2034         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, "h"),
2035 #undef FILTER
2036 #define FILTER "((((((((a == 1) && (b == 1)) || (c == 1)) && (d == 1)) || " \
2037                "(e == 1)) && (f == 1)) || (g == 1)) && (h == 1))"
2038         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "ceg"),
2039         DATA_REC(NO,  0, 1, 0, 1, 0, 1, 0, 1, ""),
2040         DATA_REC(NO,  1, 0, 1, 0, 1, 0, 1, 0, ""),
2041 #undef FILTER
2042 #define FILTER "((((((((a == 1) || (b == 1)) && (c == 1)) || (d == 1)) && " \
2043                "(e == 1)) || (f == 1)) && (g == 1)) || (h == 1))"
2044         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "bdfh"),
2045         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2046         DATA_REC(YES, 1, 0, 1, 0, 1, 0, 1, 0, "bdfh"),
2047 };
2048
2049 #undef DATA_REC
2050 #undef FILTER
2051 #undef YES
2052 #undef NO
2053
2054 #define DATA_CNT (sizeof(test_filter_data)/sizeof(struct test_filter_data_t))
2055
2056 static int test_pred_visited;
2057
2058 static int test_pred_visited_fn(struct filter_pred *pred, void *event)
2059 {
2060         struct ftrace_event_field *field = pred->field;
2061
2062         test_pred_visited = 1;
2063         printk(KERN_INFO "\npred visited %s\n", field->name);
2064         return 1;
2065 }
2066
2067 static int test_walk_pred_cb(enum move_type move, struct filter_pred *pred,
2068                              int *err, void *data)
2069 {
2070         char *fields = data;
2071
2072         if ((move == MOVE_DOWN) &&
2073             (pred->left == FILTER_PRED_INVALID)) {
2074                 struct ftrace_event_field *field = pred->field;
2075
2076                 if (!field) {
2077                         WARN(1, "all leafs should have field defined");
2078                         return WALK_PRED_DEFAULT;
2079                 }
2080                 if (!strchr(fields, *field->name))
2081                         return WALK_PRED_DEFAULT;
2082
2083                 WARN_ON(!pred->fn);
2084                 pred->fn = test_pred_visited_fn;
2085         }
2086         return WALK_PRED_DEFAULT;
2087 }
2088
2089 static __init int ftrace_test_event_filter(void)
2090 {
2091         int i;
2092
2093         printk(KERN_INFO "Testing ftrace filter: ");
2094
2095         for (i = 0; i < DATA_CNT; i++) {
2096                 struct event_filter *filter = NULL;
2097                 struct test_filter_data_t *d = &test_filter_data[i];
2098                 int err;
2099
2100                 err = test_get_filter(d->filter, &event_ftrace_test_filter,
2101                                       &filter);
2102                 if (err) {
2103                         printk(KERN_INFO
2104                                "Failed to get filter for '%s', err %d\n",
2105                                d->filter, err);
2106                         break;
2107                 }
2108
2109                 /*
2110                  * The preemption disabling is not really needed for self
2111                  * tests, but the rcu dereference will complain without it.
2112                  */
2113                 preempt_disable();
2114                 if (*d->not_visited)
2115                         walk_pred_tree(filter->preds, filter->root,
2116                                        test_walk_pred_cb,
2117                                        d->not_visited);
2118
2119                 test_pred_visited = 0;
2120                 err = filter_match_preds(filter, &d->rec);
2121                 preempt_enable();
2122
2123                 __free_filter(filter);
2124
2125                 if (test_pred_visited) {
2126                         printk(KERN_INFO
2127                                "Failed, unwanted pred visited for filter %s\n",
2128                                d->filter);
2129                         break;
2130                 }
2131
2132                 if (err != d->match) {
2133                         printk(KERN_INFO
2134                                "Failed to match filter '%s', expected %d\n",
2135                                d->filter, d->match);
2136                         break;
2137                 }
2138         }
2139
2140         if (i == DATA_CNT)
2141                 printk(KERN_CONT "OK\n");
2142
2143         return 0;
2144 }
2145
2146 late_initcall(ftrace_test_event_filter);
2147
2148 #endif /* CONFIG_FTRACE_STARTUP_TEST */