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         int i;
 773
 774         if (filter->preds) {
 775                 for (i = 0; i < filter->n_preds; i++)
 776                         kfree(filter->preds[i].ops);
 777                 kfree(filter->preds);
 778                 filter->preds = NULL;
 779         }
 780         filter->a_preds = 0;
 781         filter->n_preds = 0;
 782 }
 783
 784 static void filter_disable(struct ftrace_event_call *call)
 785 {
 786         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 787 }
 788
 789 static void __free_filter(struct event_filter *filter)
 790 {
 791         if (!filter)
 792                 return;
 793
 794         __free_preds(filter);
 795         kfree(filter->filter_string);
 796         kfree(filter);
 797 }
 798
 799 /*
 800  * Called when destroying the ftrace_event_call.
 801  * The call is being freed, so we do not need to worry about
 802  * the call being currently used. This is for module code removing
 803  * the tracepoints from within it.
 804  */
 805 void destroy_preds(struct ftrace_event_call *call)
 806 {
 807         __free_filter(call->filter);
 808         call->filter = NULL;
 809 }
 810
 811 static struct event_filter *__alloc_filter(void)
 812 {
 813         struct event_filter *filter;
 814
 815         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 816         return filter;
 817 }
 818
 819 static int __alloc_preds(struct event_filter *filter, int n_preds)
 820 {
 821         struct filter_pred *pred;
 822         int i;
 823
 824         if (filter->preds)
 825                 __free_preds(filter);
 826
 827         filter->preds =
 828                 kzalloc(sizeof(*filter->preds) * n_preds, GFP_KERNEL);
 829
 830         if (!filter->preds)
 831                 return -ENOMEM;
 832
 833         filter->a_preds = n_preds;
 834         filter->n_preds = 0;
 835
 836         for (i = 0; i < n_preds; i++) {
 837                 pred = &filter->preds[i];
 838                 pred->fn = filter_pred_none;
 839         }
 840
 841         return 0;
 842 }
 843
 844 static void filter_free_subsystem_preds(struct event_subsystem *system)
 845 {
 846         struct ftrace_event_call *call;
 847
 848         list_for_each_entry(call, &ftrace_events, list) {
 849                 if (strcmp(call->class->system, system->name) != 0)
 850                         continue;
 851
 852                 filter_disable(call);
 853                 remove_filter_string(call->filter);
 854         }
 855 }
 856
 857 static void filter_free_subsystem_filters(struct event_subsystem *system)
 858 {
 859         struct ftrace_event_call *call;
 860
 861         list_for_each_entry(call, &ftrace_events, list) {
 862                 if (strcmp(call->class->system, system->name) != 0)
 863                         continue;
 864                 __free_filter(call->filter);
 865                 call->filter = NULL;
 866         }
 867 }
 868
 869 static int filter_add_pred(struct filter_parse_state *ps,
 870                            struct event_filter *filter,
 871                            struct filter_pred *pred,
 872                            struct pred_stack *stack)
 873 {
 874         int err;
 875
 876         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 877                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 878                 return -ENOSPC;
 879         }
 880
 881         err = filter_set_pred(filter, filter->n_preds, stack, pred);
 882         if (err)
 883                 return err;
 884
 885         filter->n_preds++;
 886
 887         return 0;
 888 }
 889
 890 int filter_assign_type(const char *type)
 891 {
 892         if (strstr(type, "__data_loc") && strstr(type, "char"))
 893                 return FILTER_DYN_STRING;
 894
 895         if (strchr(type, '[') && strstr(type, "char"))
 896                 return FILTER_STATIC_STRING;
 897
 898         return FILTER_OTHER;
 899 }
 900
 901 static bool is_string_field(struct ftrace_event_field *field)
 902 {
 903         return field->filter_type == FILTER_DYN_STRING ||
 904                field->filter_type == FILTER_STATIC_STRING ||
 905                field->filter_type == FILTER_PTR_STRING;
 906 }
 907
 908 static int is_legal_op(struct ftrace_event_field *field, int op)
 909 {
 910         if (is_string_field(field) &&
 911             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 912                 return 0;
 913         if (!is_string_field(field) && op == OP_GLOB)
 914                 return 0;
 915
 916         return 1;
 917 }
 918
 919 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 920                                              int field_is_signed)
 921 {
 922         filter_pred_fn_t fn = NULL;
 923
 924         switch (field_size) {
 925         case 8:
 926                 if (op == OP_EQ || op == OP_NE)
 927                         fn = filter_pred_64;
 928                 else if (field_is_signed)
 929                         fn = filter_pred_s64;
 930                 else
 931                         fn = filter_pred_u64;
 932                 break;
 933         case 4:
 934                 if (op == OP_EQ || op == OP_NE)
 935                         fn = filter_pred_32;
 936                 else if (field_is_signed)
 937                         fn = filter_pred_s32;
 938                 else
 939                         fn = filter_pred_u32;
 940                 break;
 941         case 2:
 942                 if (op == OP_EQ || op == OP_NE)
 943                         fn = filter_pred_16;
 944                 else if (field_is_signed)
 945                         fn = filter_pred_s16;
 946                 else
 947                         fn = filter_pred_u16;
 948                 break;
 949         case 1:
 950                 if (op == OP_EQ || op == OP_NE)
 951                         fn = filter_pred_8;
 952                 else if (field_is_signed)
 953                         fn = filter_pred_s8;
 954                 else
 955                         fn = filter_pred_u8;
 956                 break;
 957         }
 958
 959         return fn;
 960 }
 961
 962 static int init_pred(struct filter_parse_state *ps,
 963                      struct ftrace_event_field *field,
 964                      struct filter_pred *pred)
 965
 966 {
 967         filter_pred_fn_t fn = filter_pred_none;
 968         unsigned long long val;
 969         int ret;
 970
 971         pred->offset = field->offset;
 972
 973         if (!is_legal_op(field, pred->op)) {
 974                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 975                 return -EINVAL;
 976         }
 977
 978         if (is_string_field(field)) {
 979                 filter_build_regex(pred);
 980
 981                 if (field->filter_type == FILTER_STATIC_STRING) {
 982                         fn = filter_pred_string;
 983                         pred->regex.field_len = field->size;
 984                 } else if (field->filter_type == FILTER_DYN_STRING)
 985                         fn = filter_pred_strloc;
 986                 else
 987                         fn = filter_pred_pchar;
 988         } else {
 989                 if (field->is_signed)
 990                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 991                 else
 992                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 993                 if (ret) {
 994                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 995                         return -EINVAL;
 996                 }
 997                 pred->val = val;
 998
 999                 fn = select_comparison_fn(pred->op, field->size,
1000                                           field->is_signed);
1001                 if (!fn) {
1002                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
1003                         return -EINVAL;
1004                 }
1005         }
1006
1007         if (pred->op == OP_NE)
1008                 pred->not = 1;
1009
1010         pred->fn = fn;
1011         return 0;
1012 }
1013
1014 static void parse_init(struct filter_parse_state *ps,
1015                        struct filter_op *ops,
1016                        char *infix_string)
1017 {
1018         memset(ps, '\0', sizeof(*ps));
1019
1020         ps->infix.string = infix_string;
1021         ps->infix.cnt = strlen(infix_string);
1022         ps->ops = ops;
1023
1024         INIT_LIST_HEAD(&ps->opstack);
1025         INIT_LIST_HEAD(&ps->postfix);
1026 }
1027
1028 static char infix_next(struct filter_parse_state *ps)
1029 {
1030         ps->infix.cnt--;
1031
1032         return ps->infix.string[ps->infix.tail++];
1033 }
1034
1035 static char infix_peek(struct filter_parse_state *ps)
1036 {
1037         if (ps->infix.tail == strlen(ps->infix.string))
1038                 return 0;
1039
1040         return ps->infix.string[ps->infix.tail];
1041 }
1042
1043 static void infix_advance(struct filter_parse_state *ps)
1044 {
1045         ps->infix.cnt--;
1046         ps->infix.tail++;
1047 }
1048
1049 static inline int is_precedence_lower(struct filter_parse_state *ps,
1050                                       int a, int b)
1051 {
1052         return ps->ops[a].precedence < ps->ops[b].precedence;
1053 }
1054
1055 static inline int is_op_char(struct filter_parse_state *ps, char c)
1056 {
1057         int i;
1058
1059         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1060                 if (ps->ops[i].string[0] == c)
1061                         return 1;
1062         }
1063
1064         return 0;
1065 }
1066
1067 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1068 {
1069         char nextc = infix_peek(ps);
1070         char opstr[3];
1071         int i;
1072
1073         opstr[0] = firstc;
1074         opstr[1] = nextc;
1075         opstr[2] = '\0';
1076
1077         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1078                 if (!strcmp(opstr, ps->ops[i].string)) {
1079                         infix_advance(ps);
1080                         return ps->ops[i].id;
1081                 }
1082         }
1083
1084         opstr[1] = '\0';
1085
1086         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1087                 if (!strcmp(opstr, ps->ops[i].string))
1088                         return ps->ops[i].id;
1089         }
1090
1091         return OP_NONE;
1092 }
1093
1094 static inline void clear_operand_string(struct filter_parse_state *ps)
1095 {
1096         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1097         ps->operand.tail = 0;
1098 }
1099
1100 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1101 {
1102         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1103                 return -EINVAL;
1104
1105         ps->operand.string[ps->operand.tail++] = c;
1106
1107         return 0;
1108 }
1109
1110 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1111 {
1112         struct opstack_op *opstack_op;
1113
1114         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1115         if (!opstack_op)
1116                 return -ENOMEM;
1117
1118         opstack_op->op = op;
1119         list_add(&opstack_op->list, &ps->opstack);
1120
1121         return 0;
1122 }
1123
1124 static int filter_opstack_empty(struct filter_parse_state *ps)
1125 {
1126         return list_empty(&ps->opstack);
1127 }
1128
1129 static int filter_opstack_top(struct filter_parse_state *ps)
1130 {
1131         struct opstack_op *opstack_op;
1132
1133         if (filter_opstack_empty(ps))
1134                 return OP_NONE;
1135
1136         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1137
1138         return opstack_op->op;
1139 }
1140
1141 static int filter_opstack_pop(struct filter_parse_state *ps)
1142 {
1143         struct opstack_op *opstack_op;
1144         int op;
1145
1146         if (filter_opstack_empty(ps))
1147                 return OP_NONE;
1148
1149         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1150         op = opstack_op->op;
1151         list_del(&opstack_op->list);
1152
1153         kfree(opstack_op);
1154
1155         return op;
1156 }
1157
1158 static void filter_opstack_clear(struct filter_parse_state *ps)
1159 {
1160         while (!filter_opstack_empty(ps))
1161                 filter_opstack_pop(ps);
1162 }
1163
1164 static char *curr_operand(struct filter_parse_state *ps)
1165 {
1166         return ps->operand.string;
1167 }
1168
1169 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1170 {
1171         struct postfix_elt *elt;
1172
1173         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1174         if (!elt)
1175                 return -ENOMEM;
1176
1177         elt->op = OP_NONE;
1178         elt->operand = kstrdup(operand, GFP_KERNEL);
1179         if (!elt->operand) {
1180                 kfree(elt);
1181                 return -ENOMEM;
1182         }
1183
1184         list_add_tail(&elt->list, &ps->postfix);
1185
1186         return 0;
1187 }
1188
1189 static int postfix_append_op(struct filter_parse_state *ps, int op)
1190 {
1191         struct postfix_elt *elt;
1192
1193         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1194         if (!elt)
1195                 return -ENOMEM;
1196
1197         elt->op = op;
1198         elt->operand = NULL;
1199
1200         list_add_tail(&elt->list, &ps->postfix);
1201
1202         return 0;
1203 }
1204
1205 static void postfix_clear(struct filter_parse_state *ps)
1206 {
1207         struct postfix_elt *elt;
1208
1209         while (!list_empty(&ps->postfix)) {
1210                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1211                 list_del(&elt->list);
1212                 kfree(elt->operand);
1213                 kfree(elt);
1214         }
1215 }
1216
1217 static int filter_parse(struct filter_parse_state *ps)
1218 {
1219         int in_string = 0;
1220         int op, top_op;
1221         char ch;
1222
1223         while ((ch = infix_next(ps))) {
1224                 if (ch == '"') {
1225                         in_string ^= 1;
1226                         continue;
1227                 }
1228
1229                 if (in_string)
1230                         goto parse_operand;
1231
1232                 if (isspace(ch))
1233                         continue;
1234
1235                 if (is_op_char(ps, ch)) {
1236                         op = infix_get_op(ps, ch);
1237                         if (op == OP_NONE) {
1238                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1239                                 return -EINVAL;
1240                         }
1241
1242                         if (strlen(curr_operand(ps))) {
1243                                 postfix_append_operand(ps, curr_operand(ps));
1244                                 clear_operand_string(ps);
1245                         }
1246
1247                         while (!filter_opstack_empty(ps)) {
1248                                 top_op = filter_opstack_top(ps);
1249                                 if (!is_precedence_lower(ps, top_op, op)) {
1250                                         top_op = filter_opstack_pop(ps);
1251                                         postfix_append_op(ps, top_op);
1252                                         continue;
1253                                 }
1254                                 break;
1255                         }
1256
1257                         filter_opstack_push(ps, op);
1258                         continue;
1259                 }
1260
1261                 if (ch == '(') {
1262                         filter_opstack_push(ps, OP_OPEN_PAREN);
1263                         continue;
1264                 }
1265
1266                 if (ch == ')') {
1267                         if (strlen(curr_operand(ps))) {
1268                                 postfix_append_operand(ps, curr_operand(ps));
1269                                 clear_operand_string(ps);
1270                         }
1271
1272                         top_op = filter_opstack_pop(ps);
1273                         while (top_op != OP_NONE) {
1274                                 if (top_op == OP_OPEN_PAREN)
1275                                         break;
1276                                 postfix_append_op(ps, top_op);
1277                                 top_op = filter_opstack_pop(ps);
1278                         }
1279                         if (top_op == OP_NONE) {
1280                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1281                                 return -EINVAL;
1282                         }
1283                         continue;
1284                 }
1285 parse_operand:
1286                 if (append_operand_char(ps, ch)) {
1287                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1288                         return -EINVAL;
1289                 }
1290         }
1291
1292         if (strlen(curr_operand(ps)))
1293                 postfix_append_operand(ps, curr_operand(ps));
1294
1295         while (!filter_opstack_empty(ps)) {
1296                 top_op = filter_opstack_pop(ps);
1297                 if (top_op == OP_NONE)
1298                         break;
1299                 if (top_op == OP_OPEN_PAREN) {
1300                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1301                         return -EINVAL;
1302                 }
1303                 postfix_append_op(ps, top_op);
1304         }
1305
1306         return 0;
1307 }
1308
1309 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1310                                        struct ftrace_event_call *call,
1311                                        int op, char *operand1, char *operand2)
1312 {
1313         struct ftrace_event_field *field;
1314         static struct filter_pred pred;
1315
1316         memset(&pred, 0, sizeof(pred));
1317         pred.op = op;
1318
1319         if (op == OP_AND || op == OP_OR)
1320                 return &pred;
1321
1322         if (!operand1 || !operand2) {
1323                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1324                 return NULL;
1325         }
1326
1327         field = find_event_field(call, operand1);
1328         if (!field) {
1329                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1330                 return NULL;
1331         }
1332
1333         strcpy(pred.regex.pattern, operand2);
1334         pred.regex.len = strlen(pred.regex.pattern);
1335
1336 #ifdef CONFIG_FTRACE_STARTUP_TEST
1337         pred.field = field;
1338 #endif
1339         return init_pred(ps, field, &pred) ? NULL : &pred;
1340 }
1341
1342 static int check_preds(struct filter_parse_state *ps)
1343 {
1344         int n_normal_preds = 0, n_logical_preds = 0;
1345         struct postfix_elt *elt;
1346
1347         list_for_each_entry(elt, &ps->postfix, list) {
1348                 if (elt->op == OP_NONE)
1349                         continue;
1350
1351                 if (elt->op == OP_AND || elt->op == OP_OR) {
1352                         n_logical_preds++;
1353                         continue;
1354                 }
1355                 n_normal_preds++;
1356         }
1357
1358         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1359                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1360                 return -EINVAL;
1361         }
1362
1363         return 0;
1364 }
1365
1366 static int count_preds(struct filter_parse_state *ps)
1367 {
1368         struct postfix_elt *elt;
1369         int n_preds = 0;
1370
1371         list_for_each_entry(elt, &ps->postfix, list) {
1372                 if (elt->op == OP_NONE)
1373                         continue;
1374                 n_preds++;
1375         }
1376
1377         return n_preds;
1378 }
1379
1380 struct check_pred_data {
1381         int count;
1382         int max;
1383 };
1384
1385 static int check_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1386                               int *err, void *data)
1387 {
1388         struct check_pred_data *d = data;
1389
1390         if (WARN_ON(d->count++ > d->max)) {
1391                 *err = -EINVAL;
1392                 return WALK_PRED_ABORT;
1393         }
1394         return WALK_PRED_DEFAULT;
1395 }
1396
1397 /*
1398  * The tree is walked at filtering of an event. If the tree is not correctly
1399  * built, it may cause an infinite loop. Check here that the tree does
1400  * indeed terminate.
1401  */
1402 static int check_pred_tree(struct event_filter *filter,
1403                            struct filter_pred *root)
1404 {
1405         struct check_pred_data data = {
1406                 /*
1407                  * The max that we can hit a node is three times.
1408                  * Once going down, once coming up from left, and
1409                  * once coming up from right. This is more than enough
1410                  * since leafs are only hit a single time.
1411                  */
1412                 .max   = 3 * filter->n_preds,
1413                 .count = 0,
1414         };
1415
1416         return walk_pred_tree(filter->preds, root,
1417                               check_pred_tree_cb, &data);
1418 }
1419
1420 static int count_leafs_cb(enum move_type move, struct filter_pred *pred,
1421                           int *err, void *data)
1422 {
1423         int *count = data;
1424
1425         if ((move == MOVE_DOWN) &&
1426             (pred->left == FILTER_PRED_INVALID))
1427                 (*count)++;
1428
1429         return WALK_PRED_DEFAULT;
1430 }
1431
1432 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1433 {
1434         int count = 0, ret;
1435
1436         ret = walk_pred_tree(preds, root, count_leafs_cb, &count);
1437         WARN_ON(ret);
1438         return count;
1439 }
1440
1441 struct fold_pred_data {
1442         struct filter_pred *root;
1443         int count;
1444         int children;
1445 };
1446
1447 static int fold_pred_cb(enum move_type move, struct filter_pred *pred,
1448                         int *err, void *data)
1449 {
1450         struct fold_pred_data *d = data;
1451         struct filter_pred *root = d->root;
1452
1453         if (move != MOVE_DOWN)
1454                 return WALK_PRED_DEFAULT;
1455         if (pred->left != FILTER_PRED_INVALID)
1456                 return WALK_PRED_DEFAULT;
1457
1458         if (WARN_ON(d->count == d->children)) {
1459                 *err = -EINVAL;
1460                 return WALK_PRED_ABORT;
1461         }
1462
1463         pred->index &= ~FILTER_PRED_FOLD;
1464         root->ops[d->count++] = pred->index;
1465         return WALK_PRED_DEFAULT;
1466 }
1467
1468 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1469 {
1470         struct fold_pred_data data = {
1471                 .root  = root,
1472                 .count = 0,
1473         };
1474         int children;
1475
1476         /* No need to keep the fold flag */
1477         root->index &= ~FILTER_PRED_FOLD;
1478
1479         /* If the root is a leaf then do nothing */
1480         if (root->left == FILTER_PRED_INVALID)
1481                 return 0;
1482
1483         /* count the children */
1484         children = count_leafs(preds, &preds[root->left]);
1485         children += count_leafs(preds, &preds[root->right]);
1486
1487         root->ops = kzalloc(sizeof(*root->ops) * children, GFP_KERNEL);
1488         if (!root->ops)
1489                 return -ENOMEM;
1490
1491         root->val = children;
1492         data.children = children;
1493         return walk_pred_tree(preds, root, fold_pred_cb, &data);
1494 }
1495
1496 static int fold_pred_tree_cb(enum move_type move, struct filter_pred *pred,
1497                              int *err, void *data)
1498 {
1499         struct filter_pred *preds = data;
1500
1501         if (move != MOVE_DOWN)
1502                 return WALK_PRED_DEFAULT;
1503         if (!(pred->index & FILTER_PRED_FOLD))
1504                 return WALK_PRED_DEFAULT;
1505
1506         *err = fold_pred(preds, pred);
1507         if (*err)
1508                 return WALK_PRED_ABORT;
1509
1510         /* eveyrhing below is folded, continue with parent */
1511         return WALK_PRED_PARENT;
1512 }
1513
1514 /*
1515  * To optimize the processing of the ops, if we have several "ors" or
1516  * "ands" together, we can put them in an array and process them all
1517  * together speeding up the filter logic.
1518  */
1519 static int fold_pred_tree(struct event_filter *filter,
1520                            struct filter_pred *root)
1521 {
1522         return walk_pred_tree(filter->preds, root, fold_pred_tree_cb,
1523                               filter->preds);
1524 }
1525
1526 static int replace_preds(struct ftrace_event_call *call,
1527                          struct event_filter *filter,
1528                          struct filter_parse_state *ps,
1529                          char *filter_string,
1530                          bool dry_run)
1531 {
1532         char *operand1 = NULL, *operand2 = NULL;
1533         struct filter_pred *pred;
1534         struct filter_pred *root;
1535         struct postfix_elt *elt;
1536         struct pred_stack stack = { }; /* init to NULL */
1537         int err;
1538         int n_preds = 0;
1539
1540         n_preds = count_preds(ps);
1541         if (n_preds >= MAX_FILTER_PRED) {
1542                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1543                 return -ENOSPC;
1544         }
1545
1546         err = check_preds(ps);
1547         if (err)
1548                 return err;
1549
1550         if (!dry_run) {
1551                 err = __alloc_pred_stack(&stack, n_preds);
1552                 if (err)
1553                         return err;
1554                 err = __alloc_preds(filter, n_preds);
1555                 if (err)
1556                         goto fail;
1557         }
1558
1559         n_preds = 0;
1560         list_for_each_entry(elt, &ps->postfix, list) {
1561                 if (elt->op == OP_NONE) {
1562                         if (!operand1)
1563                                 operand1 = elt->operand;
1564                         else if (!operand2)
1565                                 operand2 = elt->operand;
1566                         else {
1567                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1568                                 err = -EINVAL;
1569                                 goto fail;
1570                         }
1571                         continue;
1572                 }
1573
1574                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1575                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1576                         err = -ENOSPC;
1577                         goto fail;
1578                 }
1579
1580                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1581                 if (!pred) {
1582                         err = -EINVAL;
1583                         goto fail;
1584                 }
1585
1586                 if (!dry_run) {
1587                         err = filter_add_pred(ps, filter, pred, &stack);
1588                         if (err)
1589                                 goto fail;
1590                 }
1591
1592                 operand1 = operand2 = NULL;
1593         }
1594
1595         if (!dry_run) {
1596                 /* We should have one item left on the stack */
1597                 pred = __pop_pred_stack(&stack);
1598                 if (!pred)
1599                         return -EINVAL;
1600                 /* This item is where we start from in matching */
1601                 root = pred;
1602                 /* Make sure the stack is empty */
1603                 pred = __pop_pred_stack(&stack);
1604                 if (WARN_ON(pred)) {
1605                         err = -EINVAL;
1606                         filter->root = NULL;
1607                         goto fail;
1608                 }
1609                 err = check_pred_tree(filter, root);
1610                 if (err)
1611                         goto fail;
1612
1613                 /* Optimize the tree */
1614                 err = fold_pred_tree(filter, root);
1615                 if (err)
1616                         goto fail;
1617
1618                 /* We don't set root until we know it works */
1619                 barrier();
1620                 filter->root = root;
1621         }
1622
1623         err = 0;
1624 fail:
1625         __free_pred_stack(&stack);
1626         return err;
1627 }
1628
1629 struct filter_list {
1630         struct list_head        list;
1631         struct event_filter     *filter;
1632 };
1633
1634 static int replace_system_preds(struct event_subsystem *system,
1635                                 struct filter_parse_state *ps,
1636                                 char *filter_string)
1637 {
1638         struct ftrace_event_call *call;
1639         struct filter_list *filter_item;
1640         struct filter_list *tmp;
1641         LIST_HEAD(filter_list);
1642         bool fail = true;
1643         int err;
1644
1645         list_for_each_entry(call, &ftrace_events, list) {
1646
1647                 if (strcmp(call->class->system, system->name) != 0)
1648                         continue;
1649
1650                 /*
1651                  * Try to see if the filter can be applied
1652                  *  (filter arg is ignored on dry_run)
1653                  */
1654                 err = replace_preds(call, NULL, ps, filter_string, true);
1655                 if (err)
1656                         call->flags |= TRACE_EVENT_FL_NO_SET_FILTER;
1657                 else
1658                         call->flags &= ~TRACE_EVENT_FL_NO_SET_FILTER;
1659         }
1660
1661         list_for_each_entry(call, &ftrace_events, list) {
1662                 struct event_filter *filter;
1663
1664                 if (strcmp(call->class->system, system->name) != 0)
1665                         continue;
1666
1667                 if (call->flags & TRACE_EVENT_FL_NO_SET_FILTER)
1668                         continue;
1669
1670                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1671                 if (!filter_item)
1672                         goto fail_mem;
1673
1674                 list_add_tail(&filter_item->list, &filter_list);
1675
1676                 filter_item->filter = __alloc_filter();
1677                 if (!filter_item->filter)
1678                         goto fail_mem;
1679                 filter = filter_item->filter;
1680
1681                 /* Can only fail on no memory */
1682                 err = replace_filter_string(filter, filter_string);
1683                 if (err)
1684                         goto fail_mem;
1685
1686                 err = replace_preds(call, filter, ps, filter_string, false);
1687                 if (err) {
1688                         filter_disable(call);
1689                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1690                         append_filter_err(ps, filter);
1691                 } else
1692                         call->flags |= TRACE_EVENT_FL_FILTERED;
1693                 /*
1694                  * Regardless of if this returned an error, we still
1695                  * replace the filter for the call.
1696                  */
1697                 filter = call->filter;
1698                 rcu_assign_pointer(call->filter, filter_item->filter);
1699                 filter_item->filter = filter;
1700
1701                 fail = false;
1702         }
1703
1704         if (fail)
1705                 goto fail;
1706
1707         /*
1708          * The calls can still be using the old filters.
1709          * Do a synchronize_sched() to ensure all calls are
1710          * done with them before we free them.
1711          */
1712         synchronize_sched();
1713         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1714                 __free_filter(filter_item->filter);
1715                 list_del(&filter_item->list);
1716                 kfree(filter_item);
1717         }
1718         return 0;
1719  fail:
1720         /* No call succeeded */
1721         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1722                 list_del(&filter_item->list);
1723                 kfree(filter_item);
1724         }
1725         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1726         return -EINVAL;
1727  fail_mem:
1728         /* If any call succeeded, we still need to sync */
1729         if (!fail)
1730                 synchronize_sched();
1731         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1732                 __free_filter(filter_item->filter);
1733                 list_del(&filter_item->list);
1734                 kfree(filter_item);
1735         }
1736         return -ENOMEM;
1737 }
1738
1739 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1740 {
1741         struct filter_parse_state *ps;
1742         struct event_filter *filter;
1743         struct event_filter *tmp;
1744         int err = 0;
1745
1746         mutex_lock(&event_mutex);
1747
1748         if (!strcmp(strstrip(filter_string), "0")) {
1749                 filter_disable(call);
1750                 filter = call->filter;
1751                 if (!filter)
1752                         goto out_unlock;
1753                 RCU_INIT_POINTER(call->filter, NULL);
1754                 /* Make sure the filter is not being used */
1755                 synchronize_sched();
1756                 __free_filter(filter);
1757                 goto out_unlock;
1758         }
1759
1760         err = -ENOMEM;
1761         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1762         if (!ps)
1763                 goto out_unlock;
1764
1765         filter = __alloc_filter();
1766         if (!filter) {
1767                 kfree(ps);
1768                 goto out_unlock;
1769         }
1770
1771         replace_filter_string(filter, filter_string);
1772
1773         parse_init(ps, filter_ops, filter_string);
1774         err = filter_parse(ps);
1775         if (err) {
1776                 append_filter_err(ps, filter);
1777                 goto out;
1778         }
1779
1780         err = replace_preds(call, filter, ps, filter_string, false);
1781         if (err) {
1782                 filter_disable(call);
1783                 append_filter_err(ps, filter);
1784         } else
1785                 call->flags |= TRACE_EVENT_FL_FILTERED;
1786 out:
1787         /*
1788          * Always swap the call filter with the new filter
1789          * even if there was an error. If there was an error
1790          * in the filter, we disable the filter and show the error
1791          * string
1792          */
1793         tmp = call->filter;
1794         rcu_assign_pointer(call->filter, filter);
1795         if (tmp) {
1796                 /* Make sure the call is done with the filter */
1797                 synchronize_sched();
1798                 __free_filter(tmp);
1799         }
1800         filter_opstack_clear(ps);
1801         postfix_clear(ps);
1802         kfree(ps);
1803 out_unlock:
1804         mutex_unlock(&event_mutex);
1805
1806         return err;
1807 }
1808
1809 int apply_subsystem_event_filter(struct event_subsystem *system,
1810                                  char *filter_string)
1811 {
1812         struct filter_parse_state *ps;
1813         struct event_filter *filter;
1814         int err = 0;
1815
1816         mutex_lock(&event_mutex);
1817
1818         /* Make sure the system still has events */
1819         if (!system->nr_events) {
1820                 err = -ENODEV;
1821                 goto out_unlock;
1822         }
1823
1824         if (!strcmp(strstrip(filter_string), "0")) {
1825                 filter_free_subsystem_preds(system);
1826                 remove_filter_string(system->filter);
1827                 filter = system->filter;
1828                 system->filter = NULL;
1829                 /* Ensure all filters are no longer used */
1830                 synchronize_sched();
1831                 filter_free_subsystem_filters(system);
1832                 __free_filter(filter);
1833                 goto out_unlock;
1834         }
1835
1836         err = -ENOMEM;
1837         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1838         if (!ps)
1839                 goto out_unlock;
1840
1841         filter = __alloc_filter();
1842         if (!filter)
1843                 goto out;
1844
1845         replace_filter_string(filter, filter_string);
1846         /*
1847          * No event actually uses the system filter
1848          * we can free it without synchronize_sched().
1849          */
1850         __free_filter(system->filter);
1851         system->filter = filter;
1852
1853         parse_init(ps, filter_ops, filter_string);
1854         err = filter_parse(ps);
1855         if (err) {
1856                 append_filter_err(ps, system->filter);
1857                 goto out;
1858         }
1859
1860         err = replace_system_preds(system, ps, filter_string);
1861         if (err)
1862                 append_filter_err(ps, system->filter);
1863
1864 out:
1865         filter_opstack_clear(ps);
1866         postfix_clear(ps);
1867         kfree(ps);
1868 out_unlock:
1869         mutex_unlock(&event_mutex);
1870
1871         return err;
1872 }
1873
1874 #ifdef CONFIG_PERF_EVENTS
1875
1876 void ftrace_profile_free_filter(struct perf_event *event)
1877 {
1878         struct event_filter *filter = event->filter;
1879
1880         event->filter = NULL;
1881         __free_filter(filter);
1882 }
1883
1884 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1885                               char *filter_str)
1886 {
1887         int err;
1888         struct event_filter *filter;
1889         struct filter_parse_state *ps;
1890         struct ftrace_event_call *call;
1891
1892         mutex_lock(&event_mutex);
1893
1894         call = event->tp_event;
1895
1896         err = -EINVAL;
1897         if (!call)
1898                 goto out_unlock;
1899
1900         err = -EEXIST;
1901         if (event->filter)
1902                 goto out_unlock;
1903
1904         filter = __alloc_filter();
1905         if (!filter) {
1906                 err = PTR_ERR(filter);
1907                 goto out_unlock;
1908         }
1909
1910         err = -ENOMEM;
1911         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1912         if (!ps)
1913                 goto free_filter;
1914
1915         parse_init(ps, filter_ops, filter_str);
1916         err = filter_parse(ps);
1917         if (err)
1918                 goto free_ps;
1919
1920         err = replace_preds(call, filter, ps, filter_str, false);
1921         if (!err)
1922                 event->filter = filter;
1923
1924 free_ps:
1925         filter_opstack_clear(ps);
1926         postfix_clear(ps);
1927         kfree(ps);
1928
1929 free_filter:
1930         if (err)
1931                 __free_filter(filter);
1932
1933 out_unlock:
1934         mutex_unlock(&event_mutex);
1935
1936         return err;
1937 }
1938
1939 #endif /* CONFIG_PERF_EVENTS */
1940
1941 #ifdef CONFIG_FTRACE_STARTUP_TEST
1942
1943 #include <linux/types.h>
1944 #include <linux/tracepoint.h>
1945
1946 #define CREATE_TRACE_POINTS
1947 #include "trace_events_filter_test.h"
1948
1949 static int test_get_filter(char *filter_str, struct ftrace_event_call *call,
1950                            struct event_filter **pfilter)
1951 {
1952         struct event_filter *filter;
1953         struct filter_parse_state *ps;
1954         int err = -ENOMEM;
1955
1956         filter = __alloc_filter();
1957         if (!filter)
1958                 goto out;
1959
1960         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1961         if (!ps)
1962                 goto free_filter;
1963
1964         parse_init(ps, filter_ops, filter_str);
1965         err = filter_parse(ps);
1966         if (err)
1967                 goto free_ps;
1968
1969         err = replace_preds(call, filter, ps, filter_str, false);
1970         if (!err)
1971                 *pfilter = filter;
1972
1973  free_ps:
1974         filter_opstack_clear(ps);
1975         postfix_clear(ps);
1976         kfree(ps);
1977
1978  free_filter:
1979         if (err)
1980                 __free_filter(filter);
1981
1982  out:
1983         return err;
1984 }
1985
1986 #define DATA_REC(m, va, vb, vc, vd, ve, vf, vg, vh, nvisit) \
1987 { \
1988         .filter = FILTER, \
1989         .rec    = { .a = va, .b = vb, .c = vc, .d = vd, \
1990                     .e = ve, .f = vf, .g = vg, .h = vh }, \
1991         .match  = m, \
1992         .not_visited = nvisit, \
1993 }
1994 #define YES 1
1995 #define NO  0
1996
1997 static struct test_filter_data_t {
1998         char *filter;
1999         struct ftrace_raw_ftrace_test_filter rec;
2000         int match;
2001         char *not_visited;
2002 } test_filter_data[] = {
2003 #define FILTER "a == 1 && b == 1 && c == 1 && d == 1 && " \
2004                "e == 1 && f == 1 && g == 1 && h == 1"
2005         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, ""),
2006         DATA_REC(NO,  0, 1, 1, 1, 1, 1, 1, 1, "bcdefgh"),
2007         DATA_REC(NO,  1, 1, 1, 1, 1, 1, 1, 0, ""),
2008 #undef FILTER
2009 #define FILTER "a == 1 || b == 1 || c == 1 || d == 1 || " \
2010                "e == 1 || f == 1 || g == 1 || h == 1"
2011         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2012         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 0, 1, ""),
2013         DATA_REC(YES, 1, 0, 0, 0, 0, 0, 0, 0, "bcdefgh"),
2014 #undef FILTER
2015 #define FILTER "(a == 1 || b == 1) && (c == 1 || d == 1) && " \
2016                "(e == 1 || f == 1) && (g == 1 || h == 1)"
2017         DATA_REC(NO,  0, 0, 1, 1, 1, 1, 1, 1, "dfh"),
2018         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2019         DATA_REC(YES, 1, 0, 1, 0, 0, 1, 0, 1, "bd"),
2020         DATA_REC(NO,  1, 0, 1, 0, 0, 1, 0, 0, "bd"),
2021 #undef FILTER
2022 #define FILTER "(a == 1 && b == 1) || (c == 1 && d == 1) || " \
2023                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2024         DATA_REC(YES, 1, 0, 1, 1, 1, 1, 1, 1, "efgh"),
2025         DATA_REC(YES, 0, 0, 0, 0, 0, 0, 1, 1, ""),
2026         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2027 #undef FILTER
2028 #define FILTER "(a == 1 && b == 1) && (c == 1 && d == 1) && " \
2029                "(e == 1 && f == 1) || (g == 1 && h == 1)"
2030         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 0, "gh"),
2031         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 1, ""),
2032         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, ""),
2033 #undef FILTER
2034 #define FILTER "((a == 1 || b == 1) || (c == 1 || d == 1) || " \
2035                "(e == 1 || f == 1)) && (g == 1 || h == 1)"
2036         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 0, 1, "bcdef"),
2037         DATA_REC(NO,  0, 0, 0, 0, 0, 0, 0, 0, ""),
2038         DATA_REC(YES, 1, 1, 1, 1, 1, 0, 1, 1, "h"),
2039 #undef FILTER
2040 #define FILTER "((((((((a == 1) && (b == 1)) || (c == 1)) && (d == 1)) || " \
2041                "(e == 1)) && (f == 1)) || (g == 1)) && (h == 1))"
2042         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "ceg"),
2043         DATA_REC(NO,  0, 1, 0, 1, 0, 1, 0, 1, ""),
2044         DATA_REC(NO,  1, 0, 1, 0, 1, 0, 1, 0, ""),
2045 #undef FILTER
2046 #define FILTER "((((((((a == 1) || (b == 1)) && (c == 1)) || (d == 1)) && " \
2047                "(e == 1)) || (f == 1)) && (g == 1)) || (h == 1))"
2048         DATA_REC(YES, 1, 1, 1, 1, 1, 1, 1, 1, "bdfh"),
2049         DATA_REC(YES, 0, 1, 0, 1, 0, 1, 0, 1, ""),
2050         DATA_REC(YES, 1, 0, 1, 0, 1, 0, 1, 0, "bdfh"),
2051 };
2052
2053 #undef DATA_REC
2054 #undef FILTER
2055 #undef YES
2056 #undef NO
2057
2058 #define DATA_CNT (sizeof(test_filter_data)/sizeof(struct test_filter_data_t))
2059
2060 static int test_pred_visited;
2061
2062 static int test_pred_visited_fn(struct filter_pred *pred, void *event)
2063 {
2064         struct ftrace_event_field *field = pred->field;
2065
2066         test_pred_visited = 1;
2067         printk(KERN_INFO "\npred visited %s\n", field->name);
2068         return 1;
2069 }
2070
2071 static int test_walk_pred_cb(enum move_type move, struct filter_pred *pred,
2072                              int *err, void *data)
2073 {
2074         char *fields = data;
2075
2076         if ((move == MOVE_DOWN) &&
2077             (pred->left == FILTER_PRED_INVALID)) {
2078                 struct ftrace_event_field *field = pred->field;
2079
2080                 if (!field) {
2081                         WARN(1, "all leafs should have field defined");
2082                         return WALK_PRED_DEFAULT;
2083                 }
2084                 if (!strchr(fields, *field->name))
2085                         return WALK_PRED_DEFAULT;
2086
2087                 WARN_ON(!pred->fn);
2088                 pred->fn = test_pred_visited_fn;
2089         }
2090         return WALK_PRED_DEFAULT;
2091 }
2092
2093 static __init int ftrace_test_event_filter(void)
2094 {
2095         int i;
2096
2097         printk(KERN_INFO "Testing ftrace filter: ");
2098
2099         for (i = 0; i < DATA_CNT; i++) {
2100                 struct event_filter *filter = NULL;
2101                 struct test_filter_data_t *d = &test_filter_data[i];
2102                 int err;
2103
2104                 err = test_get_filter(d->filter, &event_ftrace_test_filter,
2105                                       &filter);
2106                 if (err) {
2107                         printk(KERN_INFO
2108                                "Failed to get filter for '%s', err %d\n",
2109                                d->filter, err);
2110                         break;
2111                 }
2112
2113                 /*
2114                  * The preemption disabling is not really needed for self
2115                  * tests, but the rcu dereference will complain without it.
2116                  */
2117                 preempt_disable();
2118                 if (*d->not_visited)
2119                         walk_pred_tree(filter->preds, filter->root,
2120                                        test_walk_pred_cb,
2121                                        d->not_visited);
2122
2123                 test_pred_visited = 0;
2124                 err = filter_match_preds(filter, &d->rec);
2125                 preempt_enable();
2126
2127                 __free_filter(filter);
2128
2129                 if (test_pred_visited) {
2130                         printk(KERN_INFO
2131                                "Failed, unwanted pred visited for filter %s\n",
2132                                d->filter);
2133                         break;
2134                 }
2135
2136                 if (err != d->match) {
2137                         printk(KERN_INFO
2138                                "Failed to match filter '%s', expected %d\n",
2139                                d->filter, d->match);
2140                         break;
2141                 }
2142         }
2143
2144         if (i == DATA_CNT)
2145                 printk(KERN_CONT "OK\n");
2146
2147         return 0;
2148 }
2149
2150 late_initcall(ftrace_test_event_filter);
2151
2152 #endif /* CONFIG_FTRACE_STARTUP_TEST */