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