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