Pileus Git - ~andy/linux/blob - kernel/trace/trace_events_filter.c

   1 /*
   2  * trace_events_filter - generic event filtering
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  *
  18  * Copyright (C) 2009 Tom Zanussi <tzanussi@gmail.com>
  19  */
  20
  21 #include <linux/module.h>
  22 #include <linux/ctype.h>
  23 #include <linux/mutex.h>
  24 #include <linux/perf_event.h>
  25 #include <linux/slab.h>
  26
  27 #include "trace.h"
  28 #include "trace_output.h"
  29
  30 enum filter_op_ids
  31 {
  32         OP_OR,
  33         OP_AND,
  34         OP_GLOB,
  35         OP_NE,
  36         OP_EQ,
  37         OP_LT,
  38         OP_LE,
  39         OP_GT,
  40         OP_GE,
  41         OP_NONE,
  42         OP_OPEN_PAREN,
  43 };
  44
  45 struct filter_op {
  46         int id;
  47         char *string;
  48         int precedence;
  49 };
  50
  51 static struct filter_op filter_ops[] = {
  52         { OP_OR,        "||",           1 },
  53         { OP_AND,       "&&",           2 },
  54         { OP_GLOB,      "~",            4 },
  55         { OP_NE,        "!=",           4 },
  56         { OP_EQ,        "==",           4 },
  57         { OP_LT,        "<",            5 },
  58         { OP_LE,        "<=",           5 },
  59         { OP_GT,        ">",            5 },
  60         { OP_GE,        ">=",           5 },
  61         { OP_NONE,      "OP_NONE",      0 },
  62         { OP_OPEN_PAREN, "(",           0 },
  63 };
  64
  65 enum {
  66         FILT_ERR_NONE,
  67         FILT_ERR_INVALID_OP,
  68         FILT_ERR_UNBALANCED_PAREN,
  69         FILT_ERR_TOO_MANY_OPERANDS,
  70         FILT_ERR_OPERAND_TOO_LONG,
  71         FILT_ERR_FIELD_NOT_FOUND,
  72         FILT_ERR_ILLEGAL_FIELD_OP,
  73         FILT_ERR_ILLEGAL_INTVAL,
  74         FILT_ERR_BAD_SUBSYS_FILTER,
  75         FILT_ERR_TOO_MANY_PREDS,
  76         FILT_ERR_MISSING_FIELD,
  77         FILT_ERR_INVALID_FILTER,
  78 };
  79
  80 static char *err_text[] = {
  81         "No error",
  82         "Invalid operator",
  83         "Unbalanced parens",
  84         "Too many operands",
  85         "Operand too long",
  86         "Field not found",
  87         "Illegal operation for field type",
  88         "Illegal integer value",
  89         "Couldn't find or set field in one of a subsystem's events",
  90         "Too many terms in predicate expression",
  91         "Missing field name and/or value",
  92         "Meaningless filter expression",
  93 };
  94
  95 struct opstack_op {
  96         int op;
  97         struct list_head list;
  98 };
  99
 100 struct postfix_elt {
 101         int op;
 102         char *operand;
 103         struct list_head list;
 104 };
 105
 106 struct filter_parse_state {
 107         struct filter_op *ops;
 108         struct list_head opstack;
 109         struct list_head postfix;
 110         int lasterr;
 111         int lasterr_pos;
 112
 113         struct {
 114                 char *string;
 115                 unsigned int cnt;
 116                 unsigned int tail;
 117         } infix;
 118
 119         struct {
 120                 char string[MAX_FILTER_STR_VAL];
 121                 int pos;
 122                 unsigned int tail;
 123         } operand;
 124 };
 125
 126 struct pred_stack {
 127         struct filter_pred      **preds;
 128         int                     index;
 129 };
 130
 131 #define DEFINE_COMPARISON_PRED(type)                                    \
 132 static int filter_pred_##type(struct filter_pred *pred, void *event)    \
 133 {                                                                       \
 134         type *addr = (type *)(event + pred->offset);                    \
 135         type val = (type)pred->val;                                     \
 136         int match = 0;                                                  \
 137                                                                         \
 138         switch (pred->op) {                                             \
 139         case OP_LT:                                                     \
 140                 match = (*addr < val);                                  \
 141                 break;                                                  \
 142         case OP_LE:                                                     \
 143                 match = (*addr <= val);                                 \
 144                 break;                                                  \
 145         case OP_GT:                                                     \
 146                 match = (*addr > val);                                  \
 147                 break;                                                  \
 148         case OP_GE:                                                     \
 149                 match = (*addr >= val);                                 \
 150                 break;                                                  \
 151         default:                                                        \
 152                 break;                                                  \
 153         }                                                               \
 154                                                                         \
 155         return match;                                                   \
 156 }
 157
 158 #define DEFINE_EQUALITY_PRED(size)                                      \
 159 static int filter_pred_##size(struct filter_pred *pred, void *event)    \
 160 {                                                                       \
 161         u##size *addr = (u##size *)(event + pred->offset);              \
 162         u##size val = (u##size)pred->val;                               \
 163         int match;                                                      \
 164                                                                         \
 165         match = (val == *addr) ^ pred->not;                             \
 166                                                                         \
 167         return match;                                                   \
 168 }
 169
 170 DEFINE_COMPARISON_PRED(s64);
 171 DEFINE_COMPARISON_PRED(u64);
 172 DEFINE_COMPARISON_PRED(s32);
 173 DEFINE_COMPARISON_PRED(u32);
 174 DEFINE_COMPARISON_PRED(s16);
 175 DEFINE_COMPARISON_PRED(u16);
 176 DEFINE_COMPARISON_PRED(s8);
 177 DEFINE_COMPARISON_PRED(u8);
 178
 179 DEFINE_EQUALITY_PRED(64);
 180 DEFINE_EQUALITY_PRED(32);
 181 DEFINE_EQUALITY_PRED(16);
 182 DEFINE_EQUALITY_PRED(8);
 183
 184 /* Filter predicate for fixed sized arrays of characters */
 185 static int filter_pred_string(struct filter_pred *pred, void *event)
 186 {
 187         char *addr = (char *)(event + pred->offset);
 188         int cmp, match;
 189
 190         cmp = pred->regex.match(addr, &pred->regex, pred->regex.field_len);
 191
 192         match = cmp ^ pred->not;
 193
 194         return match;
 195 }
 196
 197 /* Filter predicate for char * pointers */
 198 static int filter_pred_pchar(struct filter_pred *pred, void *event)
 199 {
 200         char **addr = (char **)(event + pred->offset);
 201         int cmp, match;
 202         int len = strlen(*addr) + 1;    /* including tailing '\0' */
 203
 204         cmp = pred->regex.match(*addr, &pred->regex, len);
 205
 206         match = cmp ^ pred->not;
 207
 208         return match;
 209 }
 210
 211 /*
 212  * Filter predicate for dynamic sized arrays of characters.
 213  * These are implemented through a list of strings at the end
 214  * of the entry.
 215  * Also each of these strings have a field in the entry which
 216  * contains its offset from the beginning of the entry.
 217  * We have then first to get this field, dereference it
 218  * and add it to the address of the entry, and at last we have
 219  * the address of the string.
 220  */
 221 static int filter_pred_strloc(struct filter_pred *pred, void *event)
 222 {
 223         u32 str_item = *(u32 *)(event + pred->offset);
 224         int str_loc = str_item & 0xffff;
 225         int str_len = str_item >> 16;
 226         char *addr = (char *)(event + str_loc);
 227         int cmp, match;
 228
 229         cmp = pred->regex.match(addr, &pred->regex, str_len);
 230
 231         match = cmp ^ pred->not;
 232
 233         return match;
 234 }
 235
 236 static int filter_pred_none(struct filter_pred *pred, void *event)
 237 {
 238         return 0;
 239 }
 240
 241 /*
 242  * regex_match_foo - Basic regex callbacks
 243  *
 244  * @str: the string to be searched
 245  * @r:   the regex structure containing the pattern string
 246  * @len: the length of the string to be searched (including '\0')
 247  *
 248  * Note:
 249  * - @str might not be NULL-terminated if it's of type DYN_STRING
 250  *   or STATIC_STRING
 251  */
 252
 253 static int regex_match_full(char *str, struct regex *r, int len)
 254 {
 255         if (strncmp(str, r->pattern, len) == 0)
 256                 return 1;
 257         return 0;
 258 }
 259
 260 static int regex_match_front(char *str, struct regex *r, int len)
 261 {
 262         if (strncmp(str, r->pattern, r->len) == 0)
 263                 return 1;
 264         return 0;
 265 }
 266
 267 static int regex_match_middle(char *str, struct regex *r, int len)
 268 {
 269         if (strnstr(str, r->pattern, len))
 270                 return 1;
 271         return 0;
 272 }
 273
 274 static int regex_match_end(char *str, struct regex *r, int len)
 275 {
 276         int strlen = len - 1;
 277
 278         if (strlen >= r->len &&
 279             memcmp(str + strlen - r->len, r->pattern, r->len) == 0)
 280                 return 1;
 281         return 0;
 282 }
 283
 284 /**
 285  * filter_parse_regex - parse a basic regex
 286  * @buff:   the raw regex
 287  * @len:    length of the regex
 288  * @search: will point to the beginning of the string to compare
 289  * @not:    tell whether the match will have to be inverted
 290  *
 291  * This passes in a buffer containing a regex and this function will
 292  * set search to point to the search part of the buffer and
 293  * return the type of search it is (see enum above).
 294  * This does modify buff.
 295  *
 296  * Returns enum type.
 297  *  search returns the pointer to use for comparison.
 298  *  not returns 1 if buff started with a '!'
 299  *     0 otherwise.
 300  */
 301 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
 302 {
 303         int type = MATCH_FULL;
 304         int i;
 305
 306         if (buff[0] == '!') {
 307                 *not = 1;
 308                 buff++;
 309                 len--;
 310         } else
 311                 *not = 0;
 312
 313         *search = buff;
 314
 315         for (i = 0; i < len; i++) {
 316                 if (buff[i] == '*') {
 317                         if (!i) {
 318                                 *search = buff + 1;
 319                                 type = MATCH_END_ONLY;
 320                         } else {
 321                                 if (type == MATCH_END_ONLY)
 322                                         type = MATCH_MIDDLE_ONLY;
 323                                 else
 324                                         type = MATCH_FRONT_ONLY;
 325                                 buff[i] = 0;
 326                                 break;
 327                         }
 328                 }
 329         }
 330
 331         return type;
 332 }
 333
 334 static void filter_build_regex(struct filter_pred *pred)
 335 {
 336         struct regex *r = &pred->regex;
 337         char *search;
 338         enum regex_type type = MATCH_FULL;
 339         int not = 0;
 340
 341         if (pred->op == OP_GLOB) {
 342                 type = filter_parse_regex(r->pattern, r->len, &search, &not);
 343                 r->len = strlen(search);
 344                 memmove(r->pattern, search, r->len+1);
 345         }
 346
 347         switch (type) {
 348         case MATCH_FULL:
 349                 r->match = regex_match_full;
 350                 break;
 351         case MATCH_FRONT_ONLY:
 352                 r->match = regex_match_front;
 353                 break;
 354         case MATCH_MIDDLE_ONLY:
 355                 r->match = regex_match_middle;
 356                 break;
 357         case MATCH_END_ONLY:
 358                 r->match = regex_match_end;
 359                 break;
 360         }
 361
 362         pred->not ^= not;
 363 }
 364
 365 enum move_type {
 366         MOVE_DOWN,
 367         MOVE_UP_FROM_LEFT,
 368         MOVE_UP_FROM_RIGHT
 369 };
 370
 371 static struct filter_pred *
 372 get_pred_parent(struct filter_pred *pred, struct filter_pred *preds,
 373                 int index, enum move_type *move)
 374 {
 375         if (pred->parent & FILTER_PRED_IS_RIGHT)
 376                 *move = MOVE_UP_FROM_RIGHT;
 377         else
 378                 *move = MOVE_UP_FROM_LEFT;
 379         pred = &preds[pred->parent & ~FILTER_PRED_IS_RIGHT];
 380
 381         return pred;
 382 }
 383
 384 /*
 385  * A series of AND or ORs where found together. Instead of
 386  * climbing up and down the tree branches, an array of the
 387  * ops were made in order of checks. We can just move across
 388  * the array and short circuit if needed.
 389  */
 390 static int process_ops(struct filter_pred *preds,
 391                        struct filter_pred *op, void *rec)
 392 {
 393         struct filter_pred *pred;
 394         int match = 0;
 395         int type;
 396         int i;
 397
 398         /*
 399          * Micro-optimization: We set type to true if op
 400          * is an OR and false otherwise (AND). Then we
 401          * just need to test if the match is equal to
 402          * the type, and if it is, we can short circuit the
 403          * rest of the checks:
 404          *
 405          * if ((match && op->op == OP_OR) ||
 406          *     (!match && op->op == OP_AND))
 407          *        return match;
 408          */
 409         type = op->op == OP_OR;
 410
 411         for (i = 0; i < op->val; i++) {
 412                 pred = &preds[op->ops[i]];
 413                 match = pred->fn(pred, rec);
 414                 if (!!match == type)
 415                         return match;
 416         }
 417         return match;
 418 }
 419
 420 /* return 1 if event matches, 0 otherwise (discard) */
 421 int filter_match_preds(struct event_filter *filter, void *rec)
 422 {
 423         int match = -1;
 424         enum move_type move = MOVE_DOWN;
 425         struct filter_pred *preds;
 426         struct filter_pred *pred;
 427         struct filter_pred *root;
 428         int n_preds;
 429         int done = 0;
 430
 431         /* no filter is considered a match */
 432         if (!filter)
 433                 return 1;
 434
 435         n_preds = filter->n_preds;
 436
 437         if (!n_preds)
 438                 return 1;
 439
 440         /*
 441          * n_preds, root and filter->preds are protect with preemption disabled.
 442          */
 443         preds = rcu_dereference_sched(filter->preds);
 444         root = rcu_dereference_sched(filter->root);
 445         if (!root)
 446                 return 1;
 447
 448         pred = root;
 449
 450         /* match is currently meaningless */
 451         match = -1;
 452
 453         do {
 454                 switch (move) {
 455                 case MOVE_DOWN:
 456                         /* only AND and OR have children */
 457                         if (pred->left != FILTER_PRED_INVALID) {
 458                                 /* If ops is set, then it was folded. */
 459                                 if (!pred->ops) {
 460                                         /* keep going to down the left side */
 461                                         pred = &preds[pred->left];
 462                                         continue;
 463                                 }
 464                                 /* We can treat folded ops as a leaf node */
 465                                 match = process_ops(preds, pred, rec);
 466                         } else
 467                                 match = pred->fn(pred, rec);
 468                         /* If this pred is the only pred */
 469                         if (pred == root)
 470                                 break;
 471                         pred = get_pred_parent(pred, preds,
 472                                                pred->parent, &move);
 473                         continue;
 474                 case MOVE_UP_FROM_LEFT:
 475                         /*
 476                          * Check for short circuits.
 477                          *
 478                          * Optimization: !!match == (pred->op == OP_OR)
 479                          *   is the same as:
 480                          * if ((match && pred->op == OP_OR) ||
 481                          *     (!match && pred->op == OP_AND))
 482                          */
 483                         if (!!match == (pred->op == OP_OR)) {
 484                                 if (pred == root)
 485                                         break;
 486                                 pred = get_pred_parent(pred, preds,
 487                                                        pred->parent, &move);
 488                                 continue;
 489                         }
 490                         /* now go down the right side of the tree. */
 491                         pred = &preds[pred->right];
 492                         move = MOVE_DOWN;
 493                         continue;
 494                 case MOVE_UP_FROM_RIGHT:
 495                         /* We finished this equation. */
 496                         if (pred == root)
 497                                 break;
 498                         pred = get_pred_parent(pred, preds,
 499                                                pred->parent, &move);
 500                         continue;
 501                 }
 502                 done = 1;
 503         } while (!done);
 504
 505         return match;
 506 }
 507 EXPORT_SYMBOL_GPL(filter_match_preds);
 508
 509 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 510 {
 511         ps->lasterr = err;
 512         ps->lasterr_pos = pos;
 513 }
 514
 515 static void remove_filter_string(struct event_filter *filter)
 516 {
 517         if (!filter)
 518                 return;
 519
 520         kfree(filter->filter_string);
 521         filter->filter_string = NULL;
 522 }
 523
 524 static int replace_filter_string(struct event_filter *filter,
 525                                  char *filter_string)
 526 {
 527         kfree(filter->filter_string);
 528         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 529         if (!filter->filter_string)
 530                 return -ENOMEM;
 531
 532         return 0;
 533 }
 534
 535 static int append_filter_string(struct event_filter *filter,
 536                                 char *string)
 537 {
 538         int newlen;
 539         char *new_filter_string;
 540
 541         BUG_ON(!filter->filter_string);
 542         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 543         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 544         if (!new_filter_string)
 545                 return -ENOMEM;
 546
 547         strcpy(new_filter_string, filter->filter_string);
 548         strcat(new_filter_string, string);
 549         kfree(filter->filter_string);
 550         filter->filter_string = new_filter_string;
 551
 552         return 0;
 553 }
 554
 555 static void append_filter_err(struct filter_parse_state *ps,
 556                               struct event_filter *filter)
 557 {
 558         int pos = ps->lasterr_pos;
 559         char *buf, *pbuf;
 560
 561         buf = (char *)__get_free_page(GFP_TEMPORARY);
 562         if (!buf)
 563                 return;
 564
 565         append_filter_string(filter, "\n");
 566         memset(buf, ' ', PAGE_SIZE);
 567         if (pos > PAGE_SIZE - 128)
 568                 pos = 0;
 569         buf[pos] = '^';
 570         pbuf = &buf[pos] + 1;
 571
 572         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 573         append_filter_string(filter, buf);
 574         free_page((unsigned long) buf);
 575 }
 576
 577 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 578 {
 579         struct event_filter *filter;
 580
 581         mutex_lock(&event_mutex);
 582         filter = call->filter;
 583         if (filter && filter->filter_string)
 584                 trace_seq_printf(s, "%s\n", filter->filter_string);
 585         else
 586                 trace_seq_printf(s, "none\n");
 587         mutex_unlock(&event_mutex);
 588 }
 589
 590 void print_subsystem_event_filter(struct event_subsystem *system,
 591                                   struct trace_seq *s)
 592 {
 593         struct event_filter *filter;
 594
 595         mutex_lock(&event_mutex);
 596         filter = system->filter;
 597         if (filter && filter->filter_string)
 598                 trace_seq_printf(s, "%s\n", filter->filter_string);
 599         else
 600                 trace_seq_printf(s, "none\n");
 601         mutex_unlock(&event_mutex);
 602 }
 603
 604 static struct ftrace_event_field *
 605 __find_event_field(struct list_head *head, char *name)
 606 {
 607         struct ftrace_event_field *field;
 608
 609         list_for_each_entry(field, head, link) {
 610                 if (!strcmp(field->name, name))
 611                         return field;
 612         }
 613
 614         return NULL;
 615 }
 616
 617 static struct ftrace_event_field *
 618 find_event_field(struct ftrace_event_call *call, char *name)
 619 {
 620         struct ftrace_event_field *field;
 621         struct list_head *head;
 622
 623         field = __find_event_field(&ftrace_common_fields, name);
 624         if (field)
 625                 return field;
 626
 627         head = trace_get_fields(call);
 628         return __find_event_field(head, name);
 629 }
 630
 631 static int __alloc_pred_stack(struct pred_stack *stack, int n_preds)
 632 {
 633         stack->preds = kzalloc(sizeof(*stack->preds)*(n_preds + 1), GFP_KERNEL);
 634         if (!stack->preds)
 635                 return -ENOMEM;
 636         stack->index = n_preds;
 637         return 0;
 638 }
 639
 640 static void __free_pred_stack(struct pred_stack *stack)
 641 {
 642         kfree(stack->preds);
 643         stack->index = 0;
 644 }
 645
 646 static int __push_pred_stack(struct pred_stack *stack,
 647                              struct filter_pred *pred)
 648 {
 649         int index = stack->index;
 650
 651         if (WARN_ON(index == 0))
 652                 return -ENOSPC;
 653
 654         stack->preds[--index] = pred;
 655         stack->index = index;
 656         return 0;
 657 }
 658
 659 static struct filter_pred *
 660 __pop_pred_stack(struct pred_stack *stack)
 661 {
 662         struct filter_pred *pred;
 663         int index = stack->index;
 664
 665         pred = stack->preds[index++];
 666         if (!pred)
 667                 return NULL;
 668
 669         stack->index = index;
 670         return pred;
 671 }
 672
 673 static int filter_set_pred(struct event_filter *filter,
 674                            int idx,
 675                            struct pred_stack *stack,
 676                            struct filter_pred *src)
 677 {
 678         struct filter_pred *dest = &filter->preds[idx];
 679         struct filter_pred *left;
 680         struct filter_pred *right;
 681
 682         *dest = *src;
 683         dest->index = idx;
 684
 685         if (dest->op == OP_OR || dest->op == OP_AND) {
 686                 right = __pop_pred_stack(stack);
 687                 left = __pop_pred_stack(stack);
 688                 if (!left || !right)
 689                         return -EINVAL;
 690                 /*
 691                  * If both children can be folded
 692                  * and they are the same op as this op or a leaf,
 693                  * then this op can be folded.
 694                  */
 695                 if (left->index & FILTER_PRED_FOLD &&
 696                     (left->op == dest->op ||
 697                      left->left == FILTER_PRED_INVALID) &&
 698                     right->index & FILTER_PRED_FOLD &&
 699                     (right->op == dest->op ||
 700                      right->left == FILTER_PRED_INVALID))
 701                         dest->index |= FILTER_PRED_FOLD;
 702
 703                 dest->left = left->index & ~FILTER_PRED_FOLD;
 704                 dest->right = right->index & ~FILTER_PRED_FOLD;
 705                 left->parent = dest->index & ~FILTER_PRED_FOLD;
 706                 right->parent = dest->index | FILTER_PRED_IS_RIGHT;
 707         } else {
 708                 /*
 709                  * Make dest->left invalid to be used as a quick
 710                  * way to know this is a leaf node.
 711                  */
 712                 dest->left = FILTER_PRED_INVALID;
 713
 714                 /* All leafs allow folding the parent ops. */
 715                 dest->index |= FILTER_PRED_FOLD;
 716         }
 717
 718         return __push_pred_stack(stack, dest);
 719 }
 720
 721 static void __free_preds(struct event_filter *filter)
 722 {
 723         if (filter->preds) {
 724                 kfree(filter->preds);
 725                 filter->preds = NULL;
 726         }
 727         filter->a_preds = 0;
 728         filter->n_preds = 0;
 729 }
 730
 731 static void filter_disable(struct ftrace_event_call *call)
 732 {
 733         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 734 }
 735
 736 static void __free_filter(struct event_filter *filter)
 737 {
 738         if (!filter)
 739                 return;
 740
 741         __free_preds(filter);
 742         kfree(filter->filter_string);
 743         kfree(filter);
 744 }
 745
 746 /*
 747  * Called when destroying the ftrace_event_call.
 748  * The call is being freed, so we do not need to worry about
 749  * the call being currently used. This is for module code removing
 750  * the tracepoints from within it.
 751  */
 752 void destroy_preds(struct ftrace_event_call *call)
 753 {
 754         __free_filter(call->filter);
 755         call->filter = NULL;
 756 }
 757
 758 static struct event_filter *__alloc_filter(void)
 759 {
 760         struct event_filter *filter;
 761
 762         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 763         return filter;
 764 }
 765
 766 static int __alloc_preds(struct event_filter *filter, int n_preds)
 767 {
 768         struct filter_pred *pred;
 769         int i;
 770
 771         if (filter->preds)
 772                 __free_preds(filter);
 773
 774         filter->preds =
 775                 kzalloc(sizeof(*filter->preds) * n_preds, GFP_KERNEL);
 776
 777         if (!filter->preds)
 778                 return -ENOMEM;
 779
 780         filter->a_preds = n_preds;
 781         filter->n_preds = 0;
 782
 783         for (i = 0; i < n_preds; i++) {
 784                 pred = &filter->preds[i];
 785                 pred->fn = filter_pred_none;
 786         }
 787
 788         return 0;
 789 }
 790
 791 static void filter_free_subsystem_preds(struct event_subsystem *system)
 792 {
 793         struct ftrace_event_call *call;
 794
 795         list_for_each_entry(call, &ftrace_events, list) {
 796                 if (strcmp(call->class->system, system->name) != 0)
 797                         continue;
 798
 799                 filter_disable(call);
 800                 remove_filter_string(call->filter);
 801         }
 802 }
 803
 804 static void filter_free_subsystem_filters(struct event_subsystem *system)
 805 {
 806         struct ftrace_event_call *call;
 807
 808         list_for_each_entry(call, &ftrace_events, list) {
 809                 if (strcmp(call->class->system, system->name) != 0)
 810                         continue;
 811                 __free_filter(call->filter);
 812                 call->filter = NULL;
 813         }
 814 }
 815
 816 static int filter_add_pred(struct filter_parse_state *ps,
 817                            struct event_filter *filter,
 818                            struct filter_pred *pred,
 819                            struct pred_stack *stack)
 820 {
 821         int err;
 822
 823         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 824                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 825                 return -ENOSPC;
 826         }
 827
 828         err = filter_set_pred(filter, filter->n_preds, stack, pred);
 829         if (err)
 830                 return err;
 831
 832         filter->n_preds++;
 833
 834         return 0;
 835 }
 836
 837 int filter_assign_type(const char *type)
 838 {
 839         if (strstr(type, "__data_loc") && strstr(type, "char"))
 840                 return FILTER_DYN_STRING;
 841
 842         if (strchr(type, '[') && strstr(type, "char"))
 843                 return FILTER_STATIC_STRING;
 844
 845         return FILTER_OTHER;
 846 }
 847
 848 static bool is_string_field(struct ftrace_event_field *field)
 849 {
 850         return field->filter_type == FILTER_DYN_STRING ||
 851                field->filter_type == FILTER_STATIC_STRING ||
 852                field->filter_type == FILTER_PTR_STRING;
 853 }
 854
 855 static int is_legal_op(struct ftrace_event_field *field, int op)
 856 {
 857         if (is_string_field(field) &&
 858             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 859                 return 0;
 860         if (!is_string_field(field) && op == OP_GLOB)
 861                 return 0;
 862
 863         return 1;
 864 }
 865
 866 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 867                                              int field_is_signed)
 868 {
 869         filter_pred_fn_t fn = NULL;
 870
 871         switch (field_size) {
 872         case 8:
 873                 if (op == OP_EQ || op == OP_NE)
 874                         fn = filter_pred_64;
 875                 else if (field_is_signed)
 876                         fn = filter_pred_s64;
 877                 else
 878                         fn = filter_pred_u64;
 879                 break;
 880         case 4:
 881                 if (op == OP_EQ || op == OP_NE)
 882                         fn = filter_pred_32;
 883                 else if (field_is_signed)
 884                         fn = filter_pred_s32;
 885                 else
 886                         fn = filter_pred_u32;
 887                 break;
 888         case 2:
 889                 if (op == OP_EQ || op == OP_NE)
 890                         fn = filter_pred_16;
 891                 else if (field_is_signed)
 892                         fn = filter_pred_s16;
 893                 else
 894                         fn = filter_pred_u16;
 895                 break;
 896         case 1:
 897                 if (op == OP_EQ || op == OP_NE)
 898                         fn = filter_pred_8;
 899                 else if (field_is_signed)
 900                         fn = filter_pred_s8;
 901                 else
 902                         fn = filter_pred_u8;
 903                 break;
 904         }
 905
 906         return fn;
 907 }
 908
 909 static int init_pred(struct filter_parse_state *ps,
 910                      struct ftrace_event_field *field,
 911                      struct filter_pred *pred)
 912
 913 {
 914         filter_pred_fn_t fn = filter_pred_none;
 915         unsigned long long val;
 916         int ret;
 917
 918         pred->offset = field->offset;
 919
 920         if (!is_legal_op(field, pred->op)) {
 921                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 922                 return -EINVAL;
 923         }
 924
 925         if (is_string_field(field)) {
 926                 filter_build_regex(pred);
 927
 928                 if (field->filter_type == FILTER_STATIC_STRING) {
 929                         fn = filter_pred_string;
 930                         pred->regex.field_len = field->size;
 931                 } else if (field->filter_type == FILTER_DYN_STRING)
 932                         fn = filter_pred_strloc;
 933                 else
 934                         fn = filter_pred_pchar;
 935         } else {
 936                 if (field->is_signed)
 937                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 938                 else
 939                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 940                 if (ret) {
 941                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 942                         return -EINVAL;
 943                 }
 944                 pred->val = val;
 945
 946                 fn = select_comparison_fn(pred->op, field->size,
 947                                           field->is_signed);
 948                 if (!fn) {
 949                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 950                         return -EINVAL;
 951                 }
 952         }
 953
 954         if (pred->op == OP_NE)
 955                 pred->not = 1;
 956
 957         pred->fn = fn;
 958         return 0;
 959 }
 960
 961 static void parse_init(struct filter_parse_state *ps,
 962                        struct filter_op *ops,
 963                        char *infix_string)
 964 {
 965         memset(ps, '\0', sizeof(*ps));
 966
 967         ps->infix.string = infix_string;
 968         ps->infix.cnt = strlen(infix_string);
 969         ps->ops = ops;
 970
 971         INIT_LIST_HEAD(&ps->opstack);
 972         INIT_LIST_HEAD(&ps->postfix);
 973 }
 974
 975 static char infix_next(struct filter_parse_state *ps)
 976 {
 977         ps->infix.cnt--;
 978
 979         return ps->infix.string[ps->infix.tail++];
 980 }
 981
 982 static char infix_peek(struct filter_parse_state *ps)
 983 {
 984         if (ps->infix.tail == strlen(ps->infix.string))
 985                 return 0;
 986
 987         return ps->infix.string[ps->infix.tail];
 988 }
 989
 990 static void infix_advance(struct filter_parse_state *ps)
 991 {
 992         ps->infix.cnt--;
 993         ps->infix.tail++;
 994 }
 995
 996 static inline int is_precedence_lower(struct filter_parse_state *ps,
 997                                       int a, int b)
 998 {
 999         return ps->ops[a].precedence < ps->ops[b].precedence;
1000 }
1001
1002 static inline int is_op_char(struct filter_parse_state *ps, char c)
1003 {
1004         int i;
1005
1006         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1007                 if (ps->ops[i].string[0] == c)
1008                         return 1;
1009         }
1010
1011         return 0;
1012 }
1013
1014 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1015 {
1016         char nextc = infix_peek(ps);
1017         char opstr[3];
1018         int i;
1019
1020         opstr[0] = firstc;
1021         opstr[1] = nextc;
1022         opstr[2] = '\0';
1023
1024         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1025                 if (!strcmp(opstr, ps->ops[i].string)) {
1026                         infix_advance(ps);
1027                         return ps->ops[i].id;
1028                 }
1029         }
1030
1031         opstr[1] = '\0';
1032
1033         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1034                 if (!strcmp(opstr, ps->ops[i].string))
1035                         return ps->ops[i].id;
1036         }
1037
1038         return OP_NONE;
1039 }
1040
1041 static inline void clear_operand_string(struct filter_parse_state *ps)
1042 {
1043         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1044         ps->operand.tail = 0;
1045 }
1046
1047 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1048 {
1049         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1050                 return -EINVAL;
1051
1052         ps->operand.string[ps->operand.tail++] = c;
1053
1054         return 0;
1055 }
1056
1057 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1058 {
1059         struct opstack_op *opstack_op;
1060
1061         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1062         if (!opstack_op)
1063                 return -ENOMEM;
1064
1065         opstack_op->op = op;
1066         list_add(&opstack_op->list, &ps->opstack);
1067
1068         return 0;
1069 }
1070
1071 static int filter_opstack_empty(struct filter_parse_state *ps)
1072 {
1073         return list_empty(&ps->opstack);
1074 }
1075
1076 static int filter_opstack_top(struct filter_parse_state *ps)
1077 {
1078         struct opstack_op *opstack_op;
1079
1080         if (filter_opstack_empty(ps))
1081                 return OP_NONE;
1082
1083         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1084
1085         return opstack_op->op;
1086 }
1087
1088 static int filter_opstack_pop(struct filter_parse_state *ps)
1089 {
1090         struct opstack_op *opstack_op;
1091         int op;
1092
1093         if (filter_opstack_empty(ps))
1094                 return OP_NONE;
1095
1096         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1097         op = opstack_op->op;
1098         list_del(&opstack_op->list);
1099
1100         kfree(opstack_op);
1101
1102         return op;
1103 }
1104
1105 static void filter_opstack_clear(struct filter_parse_state *ps)
1106 {
1107         while (!filter_opstack_empty(ps))
1108                 filter_opstack_pop(ps);
1109 }
1110
1111 static char *curr_operand(struct filter_parse_state *ps)
1112 {
1113         return ps->operand.string;
1114 }
1115
1116 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1117 {
1118         struct postfix_elt *elt;
1119
1120         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1121         if (!elt)
1122                 return -ENOMEM;
1123
1124         elt->op = OP_NONE;
1125         elt->operand = kstrdup(operand, GFP_KERNEL);
1126         if (!elt->operand) {
1127                 kfree(elt);
1128                 return -ENOMEM;
1129         }
1130
1131         list_add_tail(&elt->list, &ps->postfix);
1132
1133         return 0;
1134 }
1135
1136 static int postfix_append_op(struct filter_parse_state *ps, int op)
1137 {
1138         struct postfix_elt *elt;
1139
1140         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1141         if (!elt)
1142                 return -ENOMEM;
1143
1144         elt->op = op;
1145         elt->operand = NULL;
1146
1147         list_add_tail(&elt->list, &ps->postfix);
1148
1149         return 0;
1150 }
1151
1152 static void postfix_clear(struct filter_parse_state *ps)
1153 {
1154         struct postfix_elt *elt;
1155
1156         while (!list_empty(&ps->postfix)) {
1157                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1158                 list_del(&elt->list);
1159                 kfree(elt->operand);
1160                 kfree(elt);
1161         }
1162 }
1163
1164 static int filter_parse(struct filter_parse_state *ps)
1165 {
1166         int in_string = 0;
1167         int op, top_op;
1168         char ch;
1169
1170         while ((ch = infix_next(ps))) {
1171                 if (ch == '"') {
1172                         in_string ^= 1;
1173                         continue;
1174                 }
1175
1176                 if (in_string)
1177                         goto parse_operand;
1178
1179                 if (isspace(ch))
1180                         continue;
1181
1182                 if (is_op_char(ps, ch)) {
1183                         op = infix_get_op(ps, ch);
1184                         if (op == OP_NONE) {
1185                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1186                                 return -EINVAL;
1187                         }
1188
1189                         if (strlen(curr_operand(ps))) {
1190                                 postfix_append_operand(ps, curr_operand(ps));
1191                                 clear_operand_string(ps);
1192                         }
1193
1194                         while (!filter_opstack_empty(ps)) {
1195                                 top_op = filter_opstack_top(ps);
1196                                 if (!is_precedence_lower(ps, top_op, op)) {
1197                                         top_op = filter_opstack_pop(ps);
1198                                         postfix_append_op(ps, top_op);
1199                                         continue;
1200                                 }
1201                                 break;
1202                         }
1203
1204                         filter_opstack_push(ps, op);
1205                         continue;
1206                 }
1207
1208                 if (ch == '(') {
1209                         filter_opstack_push(ps, OP_OPEN_PAREN);
1210                         continue;
1211                 }
1212
1213                 if (ch == ')') {
1214                         if (strlen(curr_operand(ps))) {
1215                                 postfix_append_operand(ps, curr_operand(ps));
1216                                 clear_operand_string(ps);
1217                         }
1218
1219                         top_op = filter_opstack_pop(ps);
1220                         while (top_op != OP_NONE) {
1221                                 if (top_op == OP_OPEN_PAREN)
1222                                         break;
1223                                 postfix_append_op(ps, top_op);
1224                                 top_op = filter_opstack_pop(ps);
1225                         }
1226                         if (top_op == OP_NONE) {
1227                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1228                                 return -EINVAL;
1229                         }
1230                         continue;
1231                 }
1232 parse_operand:
1233                 if (append_operand_char(ps, ch)) {
1234                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1235                         return -EINVAL;
1236                 }
1237         }
1238
1239         if (strlen(curr_operand(ps)))
1240                 postfix_append_operand(ps, curr_operand(ps));
1241
1242         while (!filter_opstack_empty(ps)) {
1243                 top_op = filter_opstack_pop(ps);
1244                 if (top_op == OP_NONE)
1245                         break;
1246                 if (top_op == OP_OPEN_PAREN) {
1247                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1248                         return -EINVAL;
1249                 }
1250                 postfix_append_op(ps, top_op);
1251         }
1252
1253         return 0;
1254 }
1255
1256 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1257                                        struct ftrace_event_call *call,
1258                                        int op, char *operand1, char *operand2)
1259 {
1260         struct ftrace_event_field *field;
1261         static struct filter_pred pred;
1262
1263         memset(&pred, 0, sizeof(pred));
1264         pred.op = op;
1265
1266         if (op == OP_AND || op == OP_OR)
1267                 return &pred;
1268
1269         if (!operand1 || !operand2) {
1270                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1271                 return NULL;
1272         }
1273
1274         field = find_event_field(call, operand1);
1275         if (!field) {
1276                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
1277                 return NULL;
1278         }
1279
1280         strcpy(pred.regex.pattern, operand2);
1281         pred.regex.len = strlen(pred.regex.pattern);
1282
1283         return init_pred(ps, field, &pred) ? NULL : &pred;
1284 }
1285
1286 static int check_preds(struct filter_parse_state *ps)
1287 {
1288         int n_normal_preds = 0, n_logical_preds = 0;
1289         struct postfix_elt *elt;
1290
1291         list_for_each_entry(elt, &ps->postfix, list) {
1292                 if (elt->op == OP_NONE)
1293                         continue;
1294
1295                 if (elt->op == OP_AND || elt->op == OP_OR) {
1296                         n_logical_preds++;
1297                         continue;
1298                 }
1299                 n_normal_preds++;
1300         }
1301
1302         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1303                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1304                 return -EINVAL;
1305         }
1306
1307         return 0;
1308 }
1309
1310 static int count_preds(struct filter_parse_state *ps)
1311 {
1312         struct postfix_elt *elt;
1313         int n_preds = 0;
1314
1315         list_for_each_entry(elt, &ps->postfix, list) {
1316                 if (elt->op == OP_NONE)
1317                         continue;
1318                 n_preds++;
1319         }
1320
1321         return n_preds;
1322 }
1323
1324 /*
1325  * The tree is walked at filtering of an event. If the tree is not correctly
1326  * built, it may cause an infinite loop. Check here that the tree does
1327  * indeed terminate.
1328  */
1329 static int check_pred_tree(struct event_filter *filter,
1330                            struct filter_pred *root)
1331 {
1332         struct filter_pred *preds;
1333         struct filter_pred *pred;
1334         enum move_type move = MOVE_DOWN;
1335         int count = 0;
1336         int done = 0;
1337         int max;
1338
1339         /*
1340          * The max that we can hit a node is three times.
1341          * Once going down, once coming up from left, and
1342          * once coming up from right. This is more than enough
1343          * since leafs are only hit a single time.
1344          */
1345         max = 3 * filter->n_preds;
1346
1347         preds = filter->preds;
1348         if  (!preds)
1349                 return -EINVAL;
1350         pred = root;
1351
1352         do {
1353                 if (WARN_ON(count++ > max))
1354                         return -EINVAL;
1355
1356                 switch (move) {
1357                 case MOVE_DOWN:
1358                         if (pred->left != FILTER_PRED_INVALID) {
1359                                 pred = &preds[pred->left];
1360                                 continue;
1361                         }
1362                         /* A leaf at the root is just a leaf in the tree */
1363                         if (pred == root)
1364                                 break;
1365                         pred = get_pred_parent(pred, preds,
1366                                                pred->parent, &move);
1367                         continue;
1368                 case MOVE_UP_FROM_LEFT:
1369                         pred = &preds[pred->right];
1370                         move = MOVE_DOWN;
1371                         continue;
1372                 case MOVE_UP_FROM_RIGHT:
1373                         if (pred == root)
1374                                 break;
1375                         pred = get_pred_parent(pred, preds,
1376                                                pred->parent, &move);
1377                         continue;
1378                 }
1379                 done = 1;
1380         } while (!done);
1381
1382         /* We are fine. */
1383         return 0;
1384 }
1385
1386 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1387 {
1388         struct filter_pred *pred;
1389         enum move_type move = MOVE_DOWN;
1390         int count = 0;
1391         int done = 0;
1392
1393         pred = root;
1394
1395         do {
1396                 switch (move) {
1397                 case MOVE_DOWN:
1398                         if (pred->left != FILTER_PRED_INVALID) {
1399                                 pred = &preds[pred->left];
1400                                 continue;
1401                         }
1402                         /* A leaf at the root is just a leaf in the tree */
1403                         if (pred == root)
1404                                 return 1;
1405                         count++;
1406                         pred = get_pred_parent(pred, preds,
1407                                                pred->parent, &move);
1408                         continue;
1409                 case MOVE_UP_FROM_LEFT:
1410                         pred = &preds[pred->right];
1411                         move = MOVE_DOWN;
1412                         continue;
1413                 case MOVE_UP_FROM_RIGHT:
1414                         if (pred == root)
1415                                 break;
1416                         pred = get_pred_parent(pred, preds,
1417                                                pred->parent, &move);
1418                         continue;
1419                 }
1420                 done = 1;
1421         } while (!done);
1422
1423         return count;
1424 }
1425
1426 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1427 {
1428         struct filter_pred *pred;
1429         enum move_type move = MOVE_DOWN;
1430         int count = 0;
1431         int children;
1432         int done = 0;
1433
1434         /* No need to keep the fold flag */
1435         root->index &= ~FILTER_PRED_FOLD;
1436
1437         /* If the root is a leaf then do nothing */
1438         if (root->left == FILTER_PRED_INVALID)
1439                 return 0;
1440
1441         /* count the children */
1442         children = count_leafs(preds, &preds[root->left]);
1443         children += count_leafs(preds, &preds[root->right]);
1444
1445         root->ops = kzalloc(sizeof(*root->ops) * children, GFP_KERNEL);
1446         if (!root->ops)
1447                 return -ENOMEM;
1448
1449         root->val = children;
1450
1451         pred = root;
1452         do {
1453                 switch (move) {
1454                 case MOVE_DOWN:
1455                         if (pred->left != FILTER_PRED_INVALID) {
1456                                 pred = &preds[pred->left];
1457                                 continue;
1458                         }
1459                         if (WARN_ON(count == children))
1460                                 return -EINVAL;
1461                         pred->index &= ~FILTER_PRED_FOLD;
1462                         root->ops[count++] = pred->index;
1463                         pred = get_pred_parent(pred, preds,
1464                                                pred->parent, &move);
1465                         continue;
1466                 case MOVE_UP_FROM_LEFT:
1467                         pred = &preds[pred->right];
1468                         move = MOVE_DOWN;
1469                         continue;
1470                 case MOVE_UP_FROM_RIGHT:
1471                         if (pred == root)
1472                                 break;
1473                         pred = get_pred_parent(pred, preds,
1474                                                pred->parent, &move);
1475                         continue;
1476                 }
1477                 done = 1;
1478         } while (!done);
1479
1480         return 0;
1481 }
1482
1483 /*
1484  * To optimize the processing of the ops, if we have several "ors" or
1485  * "ands" together, we can put them in an array and process them all
1486  * together speeding up the filter logic.
1487  */
1488 static int fold_pred_tree(struct event_filter *filter,
1489                            struct filter_pred *root)
1490 {
1491         struct filter_pred *preds;
1492         struct filter_pred *pred;
1493         enum move_type move = MOVE_DOWN;
1494         int done = 0;
1495         int err;
1496
1497         preds = filter->preds;
1498         if  (!preds)
1499                 return -EINVAL;
1500         pred = root;
1501
1502         do {
1503                 switch (move) {
1504                 case MOVE_DOWN:
1505                         if (pred->index & FILTER_PRED_FOLD) {
1506                                 err = fold_pred(preds, pred);
1507                                 if (err)
1508                                         return err;
1509                                 /* Folded nodes are like leafs */
1510                         } else if (pred->left != FILTER_PRED_INVALID) {
1511                                 pred = &preds[pred->left];
1512                                 continue;
1513                         }
1514
1515                         /* A leaf at the root is just a leaf in the tree */
1516                         if (pred == root)
1517                                 break;
1518                         pred = get_pred_parent(pred, preds,
1519                                                pred->parent, &move);
1520                         continue;
1521                 case MOVE_UP_FROM_LEFT:
1522                         pred = &preds[pred->right];
1523                         move = MOVE_DOWN;
1524                         continue;
1525                 case MOVE_UP_FROM_RIGHT:
1526                         if (pred == root)
1527                                 break;
1528                         pred = get_pred_parent(pred, preds,
1529                                                pred->parent, &move);
1530                         continue;
1531                 }
1532                 done = 1;
1533         } while (!done);
1534
1535         return 0;
1536 }
1537
1538 static int replace_preds(struct ftrace_event_call *call,
1539                          struct event_filter *filter,
1540                          struct filter_parse_state *ps,
1541                          char *filter_string,
1542                          bool dry_run)
1543 {
1544         char *operand1 = NULL, *operand2 = NULL;
1545         struct filter_pred *pred;
1546         struct filter_pred *root;
1547         struct postfix_elt *elt;
1548         struct pred_stack stack = { }; /* init to NULL */
1549         int err;
1550         int n_preds = 0;
1551
1552         n_preds = count_preds(ps);
1553         if (n_preds >= MAX_FILTER_PRED) {
1554                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1555                 return -ENOSPC;
1556         }
1557
1558         err = check_preds(ps);
1559         if (err)
1560                 return err;
1561
1562         if (!dry_run) {
1563                 err = __alloc_pred_stack(&stack, n_preds);
1564                 if (err)
1565                         return err;
1566                 err = __alloc_preds(filter, n_preds);
1567                 if (err)
1568                         goto fail;
1569         }
1570
1571         n_preds = 0;
1572         list_for_each_entry(elt, &ps->postfix, list) {
1573                 if (elt->op == OP_NONE) {
1574                         if (!operand1)
1575                                 operand1 = elt->operand;
1576                         else if (!operand2)
1577                                 operand2 = elt->operand;
1578                         else {
1579                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1580                                 err = -EINVAL;
1581                                 goto fail;
1582                         }
1583                         continue;
1584                 }
1585
1586                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1587                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1588                         err = -ENOSPC;
1589                         goto fail;
1590                 }
1591
1592                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1593                 if (!pred) {
1594                         err = -EINVAL;
1595                         goto fail;
1596                 }
1597
1598                 if (!dry_run) {
1599                         err = filter_add_pred(ps, filter, pred, &stack);
1600                         if (err)
1601                                 goto fail;
1602                 }
1603
1604                 operand1 = operand2 = NULL;
1605         }
1606
1607         if (!dry_run) {
1608                 /* We should have one item left on the stack */
1609                 pred = __pop_pred_stack(&stack);
1610                 if (!pred)
1611                         return -EINVAL;
1612                 /* This item is where we start from in matching */
1613                 root = pred;
1614                 /* Make sure the stack is empty */
1615                 pred = __pop_pred_stack(&stack);
1616                 if (WARN_ON(pred)) {
1617                         err = -EINVAL;
1618                         filter->root = NULL;
1619                         goto fail;
1620                 }
1621                 err = check_pred_tree(filter, root);
1622                 if (err)
1623                         goto fail;
1624
1625                 /* Optimize the tree */
1626                 err = fold_pred_tree(filter, root);
1627                 if (err)
1628                         goto fail;
1629
1630                 /* We don't set root until we know it works */
1631                 barrier();
1632                 filter->root = root;
1633         }
1634
1635         err = 0;
1636 fail:
1637         __free_pred_stack(&stack);
1638         return err;
1639 }
1640
1641 struct filter_list {
1642         struct list_head        list;
1643         struct event_filter     *filter;
1644 };
1645
1646 static int replace_system_preds(struct event_subsystem *system,
1647                                 struct filter_parse_state *ps,
1648                                 char *filter_string)
1649 {
1650         struct ftrace_event_call *call;
1651         struct filter_list *filter_item;
1652         struct filter_list *tmp;
1653         LIST_HEAD(filter_list);
1654         bool fail = true;
1655         int err;
1656
1657         list_for_each_entry(call, &ftrace_events, list) {
1658
1659                 if (strcmp(call->class->system, system->name) != 0)
1660                         continue;
1661
1662                 /*
1663                  * Try to see if the filter can be applied
1664                  *  (filter arg is ignored on dry_run)
1665                  */
1666                 err = replace_preds(call, NULL, ps, filter_string, true);
1667                 if (err)
1668                         goto fail;
1669         }
1670
1671         list_for_each_entry(call, &ftrace_events, list) {
1672                 struct event_filter *filter;
1673
1674                 if (strcmp(call->class->system, system->name) != 0)
1675                         continue;
1676
1677                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1678                 if (!filter_item)
1679                         goto fail_mem;
1680
1681                 list_add_tail(&filter_item->list, &filter_list);
1682
1683                 filter_item->filter = __alloc_filter();
1684                 if (!filter_item->filter)
1685                         goto fail_mem;
1686                 filter = filter_item->filter;
1687
1688                 /* Can only fail on no memory */
1689                 err = replace_filter_string(filter, filter_string);
1690                 if (err)
1691                         goto fail_mem;
1692
1693                 err = replace_preds(call, filter, ps, filter_string, false);
1694                 if (err) {
1695                         filter_disable(call);
1696                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1697                         append_filter_err(ps, filter);
1698                 } else
1699                         call->flags |= TRACE_EVENT_FL_FILTERED;
1700                 /*
1701                  * Regardless of if this returned an error, we still
1702                  * replace the filter for the call.
1703                  */
1704                 filter = call->filter;
1705                 call->filter = filter_item->filter;
1706                 filter_item->filter = filter;
1707
1708                 fail = false;
1709         }
1710
1711         if (fail)
1712                 goto fail;
1713
1714         /*
1715          * The calls can still be using the old filters.
1716          * Do a synchronize_sched() to ensure all calls are
1717          * done with them before we free them.
1718          */
1719         synchronize_sched();
1720         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1721                 __free_filter(filter_item->filter);
1722                 list_del(&filter_item->list);
1723                 kfree(filter_item);
1724         }
1725         return 0;
1726  fail:
1727         /* No call succeeded */
1728         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1729                 list_del(&filter_item->list);
1730                 kfree(filter_item);
1731         }
1732         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1733         return -EINVAL;
1734  fail_mem:
1735         /* If any call succeeded, we still need to sync */
1736         if (!fail)
1737                 synchronize_sched();
1738         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1739                 __free_filter(filter_item->filter);
1740                 list_del(&filter_item->list);
1741                 kfree(filter_item);
1742         }
1743         return -ENOMEM;
1744 }
1745
1746 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1747 {
1748         struct filter_parse_state *ps;
1749         struct event_filter *filter;
1750         struct event_filter *tmp;
1751         int err = 0;
1752
1753         mutex_lock(&event_mutex);
1754
1755         if (!strcmp(strstrip(filter_string), "0")) {
1756                 filter_disable(call);
1757                 filter = call->filter;
1758                 if (!filter)
1759                         goto out_unlock;
1760                 call->filter = NULL;
1761                 /* Make sure the filter is not being used */
1762                 synchronize_sched();
1763                 __free_filter(filter);
1764                 goto out_unlock;
1765         }
1766
1767         err = -ENOMEM;
1768         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1769         if (!ps)
1770                 goto out_unlock;
1771
1772         filter = __alloc_filter();
1773         if (!filter) {
1774                 kfree(ps);
1775                 goto out_unlock;
1776         }
1777
1778         replace_filter_string(filter, filter_string);
1779
1780         parse_init(ps, filter_ops, filter_string);
1781         err = filter_parse(ps);
1782         if (err) {
1783                 append_filter_err(ps, filter);
1784                 goto out;
1785         }
1786
1787         err = replace_preds(call, filter, ps, filter_string, false);
1788         if (err) {
1789                 filter_disable(call);
1790                 append_filter_err(ps, filter);
1791         } else
1792                 call->flags |= TRACE_EVENT_FL_FILTERED;
1793 out:
1794         /*
1795          * Always swap the call filter with the new filter
1796          * even if there was an error. If there was an error
1797          * in the filter, we disable the filter and show the error
1798          * string
1799          */
1800         tmp = call->filter;
1801         call->filter = filter;
1802         if (tmp) {
1803                 /* Make sure the call is done with the filter */
1804                 synchronize_sched();
1805                 __free_filter(tmp);
1806         }
1807         filter_opstack_clear(ps);
1808         postfix_clear(ps);
1809         kfree(ps);
1810 out_unlock:
1811         mutex_unlock(&event_mutex);
1812
1813         return err;
1814 }
1815
1816 int apply_subsystem_event_filter(struct event_subsystem *system,
1817                                  char *filter_string)
1818 {
1819         struct filter_parse_state *ps;
1820         struct event_filter *filter;
1821         int err = 0;
1822
1823         mutex_lock(&event_mutex);
1824
1825         /* Make sure the system still has events */
1826         if (!system->nr_events) {
1827                 err = -ENODEV;
1828                 goto out_unlock;
1829         }
1830
1831         if (!strcmp(strstrip(filter_string), "0")) {
1832                 filter_free_subsystem_preds(system);
1833                 remove_filter_string(system->filter);
1834                 filter = system->filter;
1835                 system->filter = NULL;
1836                 /* Ensure all filters are no longer used */
1837                 synchronize_sched();
1838                 filter_free_subsystem_filters(system);
1839                 __free_filter(filter);
1840                 goto out_unlock;
1841         }
1842
1843         err = -ENOMEM;
1844         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1845         if (!ps)
1846                 goto out_unlock;
1847
1848         filter = __alloc_filter();
1849         if (!filter)
1850                 goto out;
1851
1852         replace_filter_string(filter, filter_string);
1853         /*
1854          * No event actually uses the system filter
1855          * we can free it without synchronize_sched().
1856          */
1857         __free_filter(system->filter);
1858         system->filter = filter;
1859
1860         parse_init(ps, filter_ops, filter_string);
1861         err = filter_parse(ps);
1862         if (err) {
1863                 append_filter_err(ps, system->filter);
1864                 goto out;
1865         }
1866
1867         err = replace_system_preds(system, ps, filter_string);
1868         if (err)
1869                 append_filter_err(ps, system->filter);
1870
1871 out:
1872         filter_opstack_clear(ps);
1873         postfix_clear(ps);
1874         kfree(ps);
1875 out_unlock:
1876         mutex_unlock(&event_mutex);
1877
1878         return err;
1879 }
1880
1881 #ifdef CONFIG_PERF_EVENTS
1882
1883 void ftrace_profile_free_filter(struct perf_event *event)
1884 {
1885         struct event_filter *filter = event->filter;
1886
1887         event->filter = NULL;
1888         __free_filter(filter);
1889 }
1890
1891 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1892                               char *filter_str)
1893 {
1894         int err;
1895         struct event_filter *filter;
1896         struct filter_parse_state *ps;
1897         struct ftrace_event_call *call;
1898
1899         mutex_lock(&event_mutex);
1900
1901         call = event->tp_event;
1902
1903         err = -EINVAL;
1904         if (!call)
1905                 goto out_unlock;
1906
1907         err = -EEXIST;
1908         if (event->filter)
1909                 goto out_unlock;
1910
1911         filter = __alloc_filter();
1912         if (!filter) {
1913                 err = PTR_ERR(filter);
1914                 goto out_unlock;
1915         }
1916
1917         err = -ENOMEM;
1918         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1919         if (!ps)
1920                 goto free_filter;
1921
1922         parse_init(ps, filter_ops, filter_str);
1923         err = filter_parse(ps);
1924         if (err)
1925                 goto free_ps;
1926
1927         err = replace_preds(call, filter, ps, filter_str, false);
1928         if (!err)
1929                 event->filter = filter;
1930
1931 free_ps:
1932         filter_opstack_clear(ps);
1933         postfix_clear(ps);
1934         kfree(ps);
1935
1936 free_filter:
1937         if (err)
1938                 __free_filter(filter);
1939
1940 out_unlock:
1941         mutex_unlock(&event_mutex);
1942
1943         return err;
1944 }
1945
1946 #endif /* CONFIG_PERF_EVENTS */
1947