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 void filter_free_pred(struct filter_pred *pred)
 632 {
 633         kfree(pred->field_name);
 634 }
 635
 636 static void filter_clear_pred(struct filter_pred *pred)
 637 {
 638         kfree(pred->field_name);
 639         pred->field_name = NULL;
 640         pred->regex.len = 0;
 641 }
 642
 643 static int __alloc_pred_stack(struct pred_stack *stack, int n_preds)
 644 {
 645         stack->preds = kzalloc(sizeof(*stack->preds)*(n_preds + 1), GFP_KERNEL);
 646         if (!stack->preds)
 647                 return -ENOMEM;
 648         stack->index = n_preds;
 649         return 0;
 650 }
 651
 652 static void __free_pred_stack(struct pred_stack *stack)
 653 {
 654         kfree(stack->preds);
 655         stack->index = 0;
 656 }
 657
 658 static int __push_pred_stack(struct pred_stack *stack,
 659                              struct filter_pred *pred)
 660 {
 661         int index = stack->index;
 662
 663         if (WARN_ON(index == 0))
 664                 return -ENOSPC;
 665
 666         stack->preds[--index] = pred;
 667         stack->index = index;
 668         return 0;
 669 }
 670
 671 static struct filter_pred *
 672 __pop_pred_stack(struct pred_stack *stack)
 673 {
 674         struct filter_pred *pred;
 675         int index = stack->index;
 676
 677         pred = stack->preds[index++];
 678         if (!pred)
 679                 return NULL;
 680
 681         stack->index = index;
 682         return pred;
 683 }
 684
 685 static int filter_set_pred(struct event_filter *filter,
 686                            int idx,
 687                            struct pred_stack *stack,
 688                            struct filter_pred *src)
 689 {
 690         struct filter_pred *dest = &filter->preds[idx];
 691         struct filter_pred *left;
 692         struct filter_pred *right;
 693
 694         *dest = *src;
 695         if (src->field_name) {
 696                 dest->field_name = kstrdup(src->field_name, GFP_KERNEL);
 697                 if (!dest->field_name)
 698                         return -ENOMEM;
 699         }
 700         dest->index = idx;
 701
 702         if (dest->op == OP_OR || dest->op == OP_AND) {
 703                 right = __pop_pred_stack(stack);
 704                 left = __pop_pred_stack(stack);
 705                 if (!left || !right)
 706                         return -EINVAL;
 707                 /*
 708                  * If both children can be folded
 709                  * and they are the same op as this op or a leaf,
 710                  * then this op can be folded.
 711                  */
 712                 if (left->index & FILTER_PRED_FOLD &&
 713                     (left->op == dest->op ||
 714                      left->left == FILTER_PRED_INVALID) &&
 715                     right->index & FILTER_PRED_FOLD &&
 716                     (right->op == dest->op ||
 717                      right->left == FILTER_PRED_INVALID))
 718                         dest->index |= FILTER_PRED_FOLD;
 719
 720                 dest->left = left->index & ~FILTER_PRED_FOLD;
 721                 dest->right = right->index & ~FILTER_PRED_FOLD;
 722                 left->parent = dest->index & ~FILTER_PRED_FOLD;
 723                 right->parent = dest->index | FILTER_PRED_IS_RIGHT;
 724         } else {
 725                 /*
 726                  * Make dest->left invalid to be used as a quick
 727                  * way to know this is a leaf node.
 728                  */
 729                 dest->left = FILTER_PRED_INVALID;
 730
 731                 /* All leafs allow folding the parent ops. */
 732                 dest->index |= FILTER_PRED_FOLD;
 733         }
 734
 735         return __push_pred_stack(stack, dest);
 736 }
 737
 738 static void __free_preds(struct event_filter *filter)
 739 {
 740         int i;
 741
 742         if (filter->preds) {
 743                 for (i = 0; i < filter->a_preds; i++)
 744                         kfree(filter->preds[i].field_name);
 745                 kfree(filter->preds);
 746                 filter->preds = NULL;
 747         }
 748         filter->a_preds = 0;
 749         filter->n_preds = 0;
 750 }
 751
 752 static void filter_disable(struct ftrace_event_call *call)
 753 {
 754         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 755 }
 756
 757 static void __free_filter(struct event_filter *filter)
 758 {
 759         if (!filter)
 760                 return;
 761
 762         __free_preds(filter);
 763         kfree(filter->filter_string);
 764         kfree(filter);
 765 }
 766
 767 /*
 768  * Called when destroying the ftrace_event_call.
 769  * The call is being freed, so we do not need to worry about
 770  * the call being currently used. This is for module code removing
 771  * the tracepoints from within it.
 772  */
 773 void destroy_preds(struct ftrace_event_call *call)
 774 {
 775         __free_filter(call->filter);
 776         call->filter = NULL;
 777 }
 778
 779 static struct event_filter *__alloc_filter(void)
 780 {
 781         struct event_filter *filter;
 782
 783         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 784         return filter;
 785 }
 786
 787 static int __alloc_preds(struct event_filter *filter, int n_preds)
 788 {
 789         struct filter_pred *pred;
 790         int i;
 791
 792         if (filter->preds)
 793                 __free_preds(filter);
 794
 795         filter->preds =
 796                 kzalloc(sizeof(*filter->preds) * n_preds, GFP_KERNEL);
 797
 798         if (!filter->preds)
 799                 return -ENOMEM;
 800
 801         filter->a_preds = n_preds;
 802         filter->n_preds = 0;
 803
 804         for (i = 0; i < n_preds; i++) {
 805                 pred = &filter->preds[i];
 806                 pred->fn = filter_pred_none;
 807         }
 808
 809         return 0;
 810 }
 811
 812 static void filter_free_subsystem_preds(struct event_subsystem *system)
 813 {
 814         struct ftrace_event_call *call;
 815
 816         list_for_each_entry(call, &ftrace_events, list) {
 817                 if (strcmp(call->class->system, system->name) != 0)
 818                         continue;
 819
 820                 filter_disable(call);
 821                 remove_filter_string(call->filter);
 822         }
 823 }
 824
 825 static void filter_free_subsystem_filters(struct event_subsystem *system)
 826 {
 827         struct ftrace_event_call *call;
 828
 829         list_for_each_entry(call, &ftrace_events, list) {
 830                 if (strcmp(call->class->system, system->name) != 0)
 831                         continue;
 832                 __free_filter(call->filter);
 833                 call->filter = NULL;
 834         }
 835 }
 836
 837 static int filter_add_pred(struct filter_parse_state *ps,
 838                            struct event_filter *filter,
 839                            struct filter_pred *pred,
 840                            struct pred_stack *stack)
 841 {
 842         int idx, err;
 843
 844         if (WARN_ON(filter->n_preds == filter->a_preds)) {
 845                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 846                 return -ENOSPC;
 847         }
 848
 849         idx = filter->n_preds;
 850         filter_clear_pred(&filter->preds[idx]);
 851         err = filter_set_pred(filter, idx, stack, pred);
 852         if (err)
 853                 return err;
 854
 855         filter->n_preds++;
 856
 857         return 0;
 858 }
 859
 860 int filter_assign_type(const char *type)
 861 {
 862         if (strstr(type, "__data_loc") && strstr(type, "char"))
 863                 return FILTER_DYN_STRING;
 864
 865         if (strchr(type, '[') && strstr(type, "char"))
 866                 return FILTER_STATIC_STRING;
 867
 868         return FILTER_OTHER;
 869 }
 870
 871 static bool is_string_field(struct ftrace_event_field *field)
 872 {
 873         return field->filter_type == FILTER_DYN_STRING ||
 874                field->filter_type == FILTER_STATIC_STRING ||
 875                field->filter_type == FILTER_PTR_STRING;
 876 }
 877
 878 static int is_legal_op(struct ftrace_event_field *field, int op)
 879 {
 880         if (is_string_field(field) &&
 881             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 882                 return 0;
 883         if (!is_string_field(field) && op == OP_GLOB)
 884                 return 0;
 885
 886         return 1;
 887 }
 888
 889 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 890                                              int field_is_signed)
 891 {
 892         filter_pred_fn_t fn = NULL;
 893
 894         switch (field_size) {
 895         case 8:
 896                 if (op == OP_EQ || op == OP_NE)
 897                         fn = filter_pred_64;
 898                 else if (field_is_signed)
 899                         fn = filter_pred_s64;
 900                 else
 901                         fn = filter_pred_u64;
 902                 break;
 903         case 4:
 904                 if (op == OP_EQ || op == OP_NE)
 905                         fn = filter_pred_32;
 906                 else if (field_is_signed)
 907                         fn = filter_pred_s32;
 908                 else
 909                         fn = filter_pred_u32;
 910                 break;
 911         case 2:
 912                 if (op == OP_EQ || op == OP_NE)
 913                         fn = filter_pred_16;
 914                 else if (field_is_signed)
 915                         fn = filter_pred_s16;
 916                 else
 917                         fn = filter_pred_u16;
 918                 break;
 919         case 1:
 920                 if (op == OP_EQ || op == OP_NE)
 921                         fn = filter_pred_8;
 922                 else if (field_is_signed)
 923                         fn = filter_pred_s8;
 924                 else
 925                         fn = filter_pred_u8;
 926                 break;
 927         }
 928
 929         return fn;
 930 }
 931
 932 static int init_pred(struct filter_parse_state *ps,
 933                      struct ftrace_event_call *call,
 934                      struct filter_pred *pred)
 935
 936 {
 937         struct ftrace_event_field *field;
 938         filter_pred_fn_t fn = filter_pred_none;
 939         unsigned long long val;
 940         int ret;
 941
 942         field = find_event_field(call, pred->field_name);
 943         if (!field) {
 944                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 945                 return -EINVAL;
 946         }
 947
 948         pred->offset = field->offset;
 949
 950         if (!is_legal_op(field, pred->op)) {
 951                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 952                 return -EINVAL;
 953         }
 954
 955         if (is_string_field(field)) {
 956                 filter_build_regex(pred);
 957
 958                 if (field->filter_type == FILTER_STATIC_STRING) {
 959                         fn = filter_pred_string;
 960                         pred->regex.field_len = field->size;
 961                 } else if (field->filter_type == FILTER_DYN_STRING)
 962                         fn = filter_pred_strloc;
 963                 else
 964                         fn = filter_pred_pchar;
 965         } else {
 966                 if (field->is_signed)
 967                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 968                 else
 969                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 970                 if (ret) {
 971                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 972                         return -EINVAL;
 973                 }
 974                 pred->val = val;
 975
 976                 fn = select_comparison_fn(pred->op, field->size,
 977                                           field->is_signed);
 978                 if (!fn) {
 979                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 980                         return -EINVAL;
 981                 }
 982         }
 983
 984         if (pred->op == OP_NE)
 985                 pred->not = 1;
 986
 987         pred->fn = fn;
 988         return 0;
 989 }
 990
 991 static void parse_init(struct filter_parse_state *ps,
 992                        struct filter_op *ops,
 993                        char *infix_string)
 994 {
 995         memset(ps, '\0', sizeof(*ps));
 996
 997         ps->infix.string = infix_string;
 998         ps->infix.cnt = strlen(infix_string);
 999         ps->ops = ops;
1000
1001         INIT_LIST_HEAD(&ps->opstack);
1002         INIT_LIST_HEAD(&ps->postfix);
1003 }
1004
1005 static char infix_next(struct filter_parse_state *ps)
1006 {
1007         ps->infix.cnt--;
1008
1009         return ps->infix.string[ps->infix.tail++];
1010 }
1011
1012 static char infix_peek(struct filter_parse_state *ps)
1013 {
1014         if (ps->infix.tail == strlen(ps->infix.string))
1015                 return 0;
1016
1017         return ps->infix.string[ps->infix.tail];
1018 }
1019
1020 static void infix_advance(struct filter_parse_state *ps)
1021 {
1022         ps->infix.cnt--;
1023         ps->infix.tail++;
1024 }
1025
1026 static inline int is_precedence_lower(struct filter_parse_state *ps,
1027                                       int a, int b)
1028 {
1029         return ps->ops[a].precedence < ps->ops[b].precedence;
1030 }
1031
1032 static inline int is_op_char(struct filter_parse_state *ps, char c)
1033 {
1034         int i;
1035
1036         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1037                 if (ps->ops[i].string[0] == c)
1038                         return 1;
1039         }
1040
1041         return 0;
1042 }
1043
1044 static int infix_get_op(struct filter_parse_state *ps, char firstc)
1045 {
1046         char nextc = infix_peek(ps);
1047         char opstr[3];
1048         int i;
1049
1050         opstr[0] = firstc;
1051         opstr[1] = nextc;
1052         opstr[2] = '\0';
1053
1054         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1055                 if (!strcmp(opstr, ps->ops[i].string)) {
1056                         infix_advance(ps);
1057                         return ps->ops[i].id;
1058                 }
1059         }
1060
1061         opstr[1] = '\0';
1062
1063         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
1064                 if (!strcmp(opstr, ps->ops[i].string))
1065                         return ps->ops[i].id;
1066         }
1067
1068         return OP_NONE;
1069 }
1070
1071 static inline void clear_operand_string(struct filter_parse_state *ps)
1072 {
1073         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
1074         ps->operand.tail = 0;
1075 }
1076
1077 static inline int append_operand_char(struct filter_parse_state *ps, char c)
1078 {
1079         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
1080                 return -EINVAL;
1081
1082         ps->operand.string[ps->operand.tail++] = c;
1083
1084         return 0;
1085 }
1086
1087 static int filter_opstack_push(struct filter_parse_state *ps, int op)
1088 {
1089         struct opstack_op *opstack_op;
1090
1091         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
1092         if (!opstack_op)
1093                 return -ENOMEM;
1094
1095         opstack_op->op = op;
1096         list_add(&opstack_op->list, &ps->opstack);
1097
1098         return 0;
1099 }
1100
1101 static int filter_opstack_empty(struct filter_parse_state *ps)
1102 {
1103         return list_empty(&ps->opstack);
1104 }
1105
1106 static int filter_opstack_top(struct filter_parse_state *ps)
1107 {
1108         struct opstack_op *opstack_op;
1109
1110         if (filter_opstack_empty(ps))
1111                 return OP_NONE;
1112
1113         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1114
1115         return opstack_op->op;
1116 }
1117
1118 static int filter_opstack_pop(struct filter_parse_state *ps)
1119 {
1120         struct opstack_op *opstack_op;
1121         int op;
1122
1123         if (filter_opstack_empty(ps))
1124                 return OP_NONE;
1125
1126         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
1127         op = opstack_op->op;
1128         list_del(&opstack_op->list);
1129
1130         kfree(opstack_op);
1131
1132         return op;
1133 }
1134
1135 static void filter_opstack_clear(struct filter_parse_state *ps)
1136 {
1137         while (!filter_opstack_empty(ps))
1138                 filter_opstack_pop(ps);
1139 }
1140
1141 static char *curr_operand(struct filter_parse_state *ps)
1142 {
1143         return ps->operand.string;
1144 }
1145
1146 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
1147 {
1148         struct postfix_elt *elt;
1149
1150         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1151         if (!elt)
1152                 return -ENOMEM;
1153
1154         elt->op = OP_NONE;
1155         elt->operand = kstrdup(operand, GFP_KERNEL);
1156         if (!elt->operand) {
1157                 kfree(elt);
1158                 return -ENOMEM;
1159         }
1160
1161         list_add_tail(&elt->list, &ps->postfix);
1162
1163         return 0;
1164 }
1165
1166 static int postfix_append_op(struct filter_parse_state *ps, int op)
1167 {
1168         struct postfix_elt *elt;
1169
1170         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1171         if (!elt)
1172                 return -ENOMEM;
1173
1174         elt->op = op;
1175         elt->operand = NULL;
1176
1177         list_add_tail(&elt->list, &ps->postfix);
1178
1179         return 0;
1180 }
1181
1182 static void postfix_clear(struct filter_parse_state *ps)
1183 {
1184         struct postfix_elt *elt;
1185
1186         while (!list_empty(&ps->postfix)) {
1187                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1188                 list_del(&elt->list);
1189                 kfree(elt->operand);
1190                 kfree(elt);
1191         }
1192 }
1193
1194 static int filter_parse(struct filter_parse_state *ps)
1195 {
1196         int in_string = 0;
1197         int op, top_op;
1198         char ch;
1199
1200         while ((ch = infix_next(ps))) {
1201                 if (ch == '"') {
1202                         in_string ^= 1;
1203                         continue;
1204                 }
1205
1206                 if (in_string)
1207                         goto parse_operand;
1208
1209                 if (isspace(ch))
1210                         continue;
1211
1212                 if (is_op_char(ps, ch)) {
1213                         op = infix_get_op(ps, ch);
1214                         if (op == OP_NONE) {
1215                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1216                                 return -EINVAL;
1217                         }
1218
1219                         if (strlen(curr_operand(ps))) {
1220                                 postfix_append_operand(ps, curr_operand(ps));
1221                                 clear_operand_string(ps);
1222                         }
1223
1224                         while (!filter_opstack_empty(ps)) {
1225                                 top_op = filter_opstack_top(ps);
1226                                 if (!is_precedence_lower(ps, top_op, op)) {
1227                                         top_op = filter_opstack_pop(ps);
1228                                         postfix_append_op(ps, top_op);
1229                                         continue;
1230                                 }
1231                                 break;
1232                         }
1233
1234                         filter_opstack_push(ps, op);
1235                         continue;
1236                 }
1237
1238                 if (ch == '(') {
1239                         filter_opstack_push(ps, OP_OPEN_PAREN);
1240                         continue;
1241                 }
1242
1243                 if (ch == ')') {
1244                         if (strlen(curr_operand(ps))) {
1245                                 postfix_append_operand(ps, curr_operand(ps));
1246                                 clear_operand_string(ps);
1247                         }
1248
1249                         top_op = filter_opstack_pop(ps);
1250                         while (top_op != OP_NONE) {
1251                                 if (top_op == OP_OPEN_PAREN)
1252                                         break;
1253                                 postfix_append_op(ps, top_op);
1254                                 top_op = filter_opstack_pop(ps);
1255                         }
1256                         if (top_op == OP_NONE) {
1257                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1258                                 return -EINVAL;
1259                         }
1260                         continue;
1261                 }
1262 parse_operand:
1263                 if (append_operand_char(ps, ch)) {
1264                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1265                         return -EINVAL;
1266                 }
1267         }
1268
1269         if (strlen(curr_operand(ps)))
1270                 postfix_append_operand(ps, curr_operand(ps));
1271
1272         while (!filter_opstack_empty(ps)) {
1273                 top_op = filter_opstack_pop(ps);
1274                 if (top_op == OP_NONE)
1275                         break;
1276                 if (top_op == OP_OPEN_PAREN) {
1277                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1278                         return -EINVAL;
1279                 }
1280                 postfix_append_op(ps, top_op);
1281         }
1282
1283         return 0;
1284 }
1285
1286 static struct filter_pred *create_pred(struct filter_parse_state *ps,
1287                                        struct ftrace_event_call *call,
1288                                        int op, char *operand1, char *operand2)
1289 {
1290         static struct filter_pred pred;
1291
1292         memset(&pred, 0, sizeof(pred));
1293         pred.op = op;
1294
1295         if (op == OP_AND || op == OP_OR)
1296                 return &pred;
1297
1298         if (!operand1 || !operand2) {
1299                 parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1300                 return NULL;
1301         }
1302
1303         pred.field_name = kstrdup(operand1, GFP_KERNEL);
1304         if (!pred.field_name)
1305                 return NULL;
1306
1307         strcpy(pred.regex.pattern, operand2);
1308         pred.regex.len = strlen(pred.regex.pattern);
1309
1310         return init_pred(ps, call, &pred) ? NULL : &pred;
1311 }
1312
1313 static int check_preds(struct filter_parse_state *ps)
1314 {
1315         int n_normal_preds = 0, n_logical_preds = 0;
1316         struct postfix_elt *elt;
1317
1318         list_for_each_entry(elt, &ps->postfix, list) {
1319                 if (elt->op == OP_NONE)
1320                         continue;
1321
1322                 if (elt->op == OP_AND || elt->op == OP_OR) {
1323                         n_logical_preds++;
1324                         continue;
1325                 }
1326                 n_normal_preds++;
1327         }
1328
1329         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1330                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1331                 return -EINVAL;
1332         }
1333
1334         return 0;
1335 }
1336
1337 static int count_preds(struct filter_parse_state *ps)
1338 {
1339         struct postfix_elt *elt;
1340         int n_preds = 0;
1341
1342         list_for_each_entry(elt, &ps->postfix, list) {
1343                 if (elt->op == OP_NONE)
1344                         continue;
1345                 n_preds++;
1346         }
1347
1348         return n_preds;
1349 }
1350
1351 /*
1352  * The tree is walked at filtering of an event. If the tree is not correctly
1353  * built, it may cause an infinite loop. Check here that the tree does
1354  * indeed terminate.
1355  */
1356 static int check_pred_tree(struct event_filter *filter,
1357                            struct filter_pred *root)
1358 {
1359         struct filter_pred *preds;
1360         struct filter_pred *pred;
1361         enum move_type move = MOVE_DOWN;
1362         int count = 0;
1363         int done = 0;
1364         int max;
1365
1366         /*
1367          * The max that we can hit a node is three times.
1368          * Once going down, once coming up from left, and
1369          * once coming up from right. This is more than enough
1370          * since leafs are only hit a single time.
1371          */
1372         max = 3 * filter->n_preds;
1373
1374         preds = filter->preds;
1375         if  (!preds)
1376                 return -EINVAL;
1377         pred = root;
1378
1379         do {
1380                 if (WARN_ON(count++ > max))
1381                         return -EINVAL;
1382
1383                 switch (move) {
1384                 case MOVE_DOWN:
1385                         if (pred->left != FILTER_PRED_INVALID) {
1386                                 pred = &preds[pred->left];
1387                                 continue;
1388                         }
1389                         /* A leaf at the root is just a leaf in the tree */
1390                         if (pred == root)
1391                                 break;
1392                         pred = get_pred_parent(pred, preds,
1393                                                pred->parent, &move);
1394                         continue;
1395                 case MOVE_UP_FROM_LEFT:
1396                         pred = &preds[pred->right];
1397                         move = MOVE_DOWN;
1398                         continue;
1399                 case MOVE_UP_FROM_RIGHT:
1400                         if (pred == root)
1401                                 break;
1402                         pred = get_pred_parent(pred, preds,
1403                                                pred->parent, &move);
1404                         continue;
1405                 }
1406                 done = 1;
1407         } while (!done);
1408
1409         /* We are fine. */
1410         return 0;
1411 }
1412
1413 static int count_leafs(struct filter_pred *preds, struct filter_pred *root)
1414 {
1415         struct filter_pred *pred;
1416         enum move_type move = MOVE_DOWN;
1417         int count = 0;
1418         int done = 0;
1419
1420         pred = root;
1421
1422         do {
1423                 switch (move) {
1424                 case MOVE_DOWN:
1425                         if (pred->left != FILTER_PRED_INVALID) {
1426                                 pred = &preds[pred->left];
1427                                 continue;
1428                         }
1429                         /* A leaf at the root is just a leaf in the tree */
1430                         if (pred == root)
1431                                 return 1;
1432                         count++;
1433                         pred = get_pred_parent(pred, preds,
1434                                                pred->parent, &move);
1435                         continue;
1436                 case MOVE_UP_FROM_LEFT:
1437                         pred = &preds[pred->right];
1438                         move = MOVE_DOWN;
1439                         continue;
1440                 case MOVE_UP_FROM_RIGHT:
1441                         if (pred == root)
1442                                 break;
1443                         pred = get_pred_parent(pred, preds,
1444                                                pred->parent, &move);
1445                         continue;
1446                 }
1447                 done = 1;
1448         } while (!done);
1449
1450         return count;
1451 }
1452
1453 static int fold_pred(struct filter_pred *preds, struct filter_pred *root)
1454 {
1455         struct filter_pred *pred;
1456         enum move_type move = MOVE_DOWN;
1457         int count = 0;
1458         int children;
1459         int done = 0;
1460
1461         /* No need to keep the fold flag */
1462         root->index &= ~FILTER_PRED_FOLD;
1463
1464         /* If the root is a leaf then do nothing */
1465         if (root->left == FILTER_PRED_INVALID)
1466                 return 0;
1467
1468         /* count the children */
1469         children = count_leafs(preds, &preds[root->left]);
1470         children += count_leafs(preds, &preds[root->right]);
1471
1472         root->ops = kzalloc(sizeof(*root->ops) * children, GFP_KERNEL);
1473         if (!root->ops)
1474                 return -ENOMEM;
1475
1476         root->val = children;
1477
1478         pred = root;
1479         do {
1480                 switch (move) {
1481                 case MOVE_DOWN:
1482                         if (pred->left != FILTER_PRED_INVALID) {
1483                                 pred = &preds[pred->left];
1484                                 continue;
1485                         }
1486                         if (WARN_ON(count == children))
1487                                 return -EINVAL;
1488                         pred->index &= ~FILTER_PRED_FOLD;
1489                         root->ops[count++] = pred->index;
1490                         pred = get_pred_parent(pred, preds,
1491                                                pred->parent, &move);
1492                         continue;
1493                 case MOVE_UP_FROM_LEFT:
1494                         pred = &preds[pred->right];
1495                         move = MOVE_DOWN;
1496                         continue;
1497                 case MOVE_UP_FROM_RIGHT:
1498                         if (pred == root)
1499                                 break;
1500                         pred = get_pred_parent(pred, preds,
1501                                                pred->parent, &move);
1502                         continue;
1503                 }
1504                 done = 1;
1505         } while (!done);
1506
1507         return 0;
1508 }
1509
1510 /*
1511  * To optimize the processing of the ops, if we have several "ors" or
1512  * "ands" together, we can put them in an array and process them all
1513  * together speeding up the filter logic.
1514  */
1515 static int fold_pred_tree(struct event_filter *filter,
1516                            struct filter_pred *root)
1517 {
1518         struct filter_pred *preds;
1519         struct filter_pred *pred;
1520         enum move_type move = MOVE_DOWN;
1521         int done = 0;
1522         int err;
1523
1524         preds = filter->preds;
1525         if  (!preds)
1526                 return -EINVAL;
1527         pred = root;
1528
1529         do {
1530                 switch (move) {
1531                 case MOVE_DOWN:
1532                         if (pred->index & FILTER_PRED_FOLD) {
1533                                 err = fold_pred(preds, pred);
1534                                 if (err)
1535                                         return err;
1536                                 /* Folded nodes are like leafs */
1537                         } else if (pred->left != FILTER_PRED_INVALID) {
1538                                 pred = &preds[pred->left];
1539                                 continue;
1540                         }
1541
1542                         /* A leaf at the root is just a leaf in the tree */
1543                         if (pred == root)
1544                                 break;
1545                         pred = get_pred_parent(pred, preds,
1546                                                pred->parent, &move);
1547                         continue;
1548                 case MOVE_UP_FROM_LEFT:
1549                         pred = &preds[pred->right];
1550                         move = MOVE_DOWN;
1551                         continue;
1552                 case MOVE_UP_FROM_RIGHT:
1553                         if (pred == root)
1554                                 break;
1555                         pred = get_pred_parent(pred, preds,
1556                                                pred->parent, &move);
1557                         continue;
1558                 }
1559                 done = 1;
1560         } while (!done);
1561
1562         return 0;
1563 }
1564
1565 static int replace_preds(struct ftrace_event_call *call,
1566                          struct event_filter *filter,
1567                          struct filter_parse_state *ps,
1568                          char *filter_string,
1569                          bool dry_run)
1570 {
1571         char *operand1 = NULL, *operand2 = NULL;
1572         struct filter_pred *pred;
1573         struct filter_pred *root;
1574         struct postfix_elt *elt;
1575         struct pred_stack stack = { }; /* init to NULL */
1576         int err;
1577         int n_preds = 0;
1578
1579         n_preds = count_preds(ps);
1580         if (n_preds >= MAX_FILTER_PRED) {
1581                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1582                 return -ENOSPC;
1583         }
1584
1585         err = check_preds(ps);
1586         if (err)
1587                 return err;
1588
1589         if (!dry_run) {
1590                 err = __alloc_pred_stack(&stack, n_preds);
1591                 if (err)
1592                         return err;
1593                 err = __alloc_preds(filter, n_preds);
1594                 if (err)
1595                         goto fail;
1596         }
1597
1598         n_preds = 0;
1599         list_for_each_entry(elt, &ps->postfix, list) {
1600                 if (elt->op == OP_NONE) {
1601                         if (!operand1)
1602                                 operand1 = elt->operand;
1603                         else if (!operand2)
1604                                 operand2 = elt->operand;
1605                         else {
1606                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1607                                 err = -EINVAL;
1608                                 goto fail;
1609                         }
1610                         continue;
1611                 }
1612
1613                 if (WARN_ON(n_preds++ == MAX_FILTER_PRED)) {
1614                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1615                         err = -ENOSPC;
1616                         goto fail;
1617                 }
1618
1619                 pred = create_pred(ps, call, elt->op, operand1, operand2);
1620                 if (!pred) {
1621                         err = -ENOMEM;
1622                         goto fail;
1623                 }
1624                 if (!dry_run) {
1625                         err = filter_add_pred(ps, filter, pred, &stack);
1626                         if (err) {
1627                                 filter_free_pred(pred);
1628                                 goto fail;
1629                         }
1630                 }
1631
1632                 filter_free_pred(pred);
1633                 operand1 = operand2 = NULL;
1634         }
1635
1636         if (!dry_run) {
1637                 /* We should have one item left on the stack */
1638                 pred = __pop_pred_stack(&stack);
1639                 if (!pred)
1640                         return -EINVAL;
1641                 /* This item is where we start from in matching */
1642                 root = pred;
1643                 /* Make sure the stack is empty */
1644                 pred = __pop_pred_stack(&stack);
1645                 if (WARN_ON(pred)) {
1646                         err = -EINVAL;
1647                         filter->root = NULL;
1648                         goto fail;
1649                 }
1650                 err = check_pred_tree(filter, root);
1651                 if (err)
1652                         goto fail;
1653
1654                 /* Optimize the tree */
1655                 err = fold_pred_tree(filter, root);
1656                 if (err)
1657                         goto fail;
1658
1659                 /* We don't set root until we know it works */
1660                 barrier();
1661                 filter->root = root;
1662         }
1663
1664         err = 0;
1665 fail:
1666         __free_pred_stack(&stack);
1667         return err;
1668 }
1669
1670 struct filter_list {
1671         struct list_head        list;
1672         struct event_filter     *filter;
1673 };
1674
1675 static int replace_system_preds(struct event_subsystem *system,
1676                                 struct filter_parse_state *ps,
1677                                 char *filter_string)
1678 {
1679         struct ftrace_event_call *call;
1680         struct filter_list *filter_item;
1681         struct filter_list *tmp;
1682         LIST_HEAD(filter_list);
1683         bool fail = true;
1684         int err;
1685
1686         list_for_each_entry(call, &ftrace_events, list) {
1687
1688                 if (strcmp(call->class->system, system->name) != 0)
1689                         continue;
1690
1691                 /*
1692                  * Try to see if the filter can be applied
1693                  *  (filter arg is ignored on dry_run)
1694                  */
1695                 err = replace_preds(call, NULL, ps, filter_string, true);
1696                 if (err)
1697                         goto fail;
1698         }
1699
1700         list_for_each_entry(call, &ftrace_events, list) {
1701                 struct event_filter *filter;
1702
1703                 if (strcmp(call->class->system, system->name) != 0)
1704                         continue;
1705
1706                 filter_item = kzalloc(sizeof(*filter_item), GFP_KERNEL);
1707                 if (!filter_item)
1708                         goto fail_mem;
1709
1710                 list_add_tail(&filter_item->list, &filter_list);
1711
1712                 filter_item->filter = __alloc_filter();
1713                 if (!filter_item->filter)
1714                         goto fail_mem;
1715                 filter = filter_item->filter;
1716
1717                 /* Can only fail on no memory */
1718                 err = replace_filter_string(filter, filter_string);
1719                 if (err)
1720                         goto fail_mem;
1721
1722                 err = replace_preds(call, filter, ps, filter_string, false);
1723                 if (err) {
1724                         filter_disable(call);
1725                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1726                         append_filter_err(ps, filter);
1727                 } else
1728                         call->flags |= TRACE_EVENT_FL_FILTERED;
1729                 /*
1730                  * Regardless of if this returned an error, we still
1731                  * replace the filter for the call.
1732                  */
1733                 filter = call->filter;
1734                 call->filter = filter_item->filter;
1735                 filter_item->filter = filter;
1736
1737                 fail = false;
1738         }
1739
1740         if (fail)
1741                 goto fail;
1742
1743         /*
1744          * The calls can still be using the old filters.
1745          * Do a synchronize_sched() to ensure all calls are
1746          * done with them before we free them.
1747          */
1748         synchronize_sched();
1749         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1750                 __free_filter(filter_item->filter);
1751                 list_del(&filter_item->list);
1752                 kfree(filter_item);
1753         }
1754         return 0;
1755  fail:
1756         /* No call succeeded */
1757         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1758                 list_del(&filter_item->list);
1759                 kfree(filter_item);
1760         }
1761         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1762         return -EINVAL;
1763  fail_mem:
1764         /* If any call succeeded, we still need to sync */
1765         if (!fail)
1766                 synchronize_sched();
1767         list_for_each_entry_safe(filter_item, tmp, &filter_list, list) {
1768                 __free_filter(filter_item->filter);
1769                 list_del(&filter_item->list);
1770                 kfree(filter_item);
1771         }
1772         return -ENOMEM;
1773 }
1774
1775 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1776 {
1777         struct filter_parse_state *ps;
1778         struct event_filter *filter;
1779         struct event_filter *tmp;
1780         int err = 0;
1781
1782         mutex_lock(&event_mutex);
1783
1784         if (!strcmp(strstrip(filter_string), "0")) {
1785                 filter_disable(call);
1786                 filter = call->filter;
1787                 if (!filter)
1788                         goto out_unlock;
1789                 call->filter = NULL;
1790                 /* Make sure the filter is not being used */
1791                 synchronize_sched();
1792                 __free_filter(filter);
1793                 goto out_unlock;
1794         }
1795
1796         err = -ENOMEM;
1797         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1798         if (!ps)
1799                 goto out_unlock;
1800
1801         filter = __alloc_filter();
1802         if (!filter) {
1803                 kfree(ps);
1804                 goto out_unlock;
1805         }
1806
1807         replace_filter_string(filter, filter_string);
1808
1809         parse_init(ps, filter_ops, filter_string);
1810         err = filter_parse(ps);
1811         if (err) {
1812                 append_filter_err(ps, filter);
1813                 goto out;
1814         }
1815
1816         err = replace_preds(call, filter, ps, filter_string, false);
1817         if (err) {
1818                 filter_disable(call);
1819                 append_filter_err(ps, filter);
1820         } else
1821                 call->flags |= TRACE_EVENT_FL_FILTERED;
1822 out:
1823         /*
1824          * Always swap the call filter with the new filter
1825          * even if there was an error. If there was an error
1826          * in the filter, we disable the filter and show the error
1827          * string
1828          */
1829         tmp = call->filter;
1830         call->filter = filter;
1831         if (tmp) {
1832                 /* Make sure the call is done with the filter */
1833                 synchronize_sched();
1834                 __free_filter(tmp);
1835         }
1836         filter_opstack_clear(ps);
1837         postfix_clear(ps);
1838         kfree(ps);
1839 out_unlock:
1840         mutex_unlock(&event_mutex);
1841
1842         return err;
1843 }
1844
1845 int apply_subsystem_event_filter(struct event_subsystem *system,
1846                                  char *filter_string)
1847 {
1848         struct filter_parse_state *ps;
1849         struct event_filter *filter;
1850         int err = 0;
1851
1852         mutex_lock(&event_mutex);
1853
1854         /* Make sure the system still has events */
1855         if (!system->nr_events) {
1856                 err = -ENODEV;
1857                 goto out_unlock;
1858         }
1859
1860         if (!strcmp(strstrip(filter_string), "0")) {
1861                 filter_free_subsystem_preds(system);
1862                 remove_filter_string(system->filter);
1863                 filter = system->filter;
1864                 system->filter = NULL;
1865                 /* Ensure all filters are no longer used */
1866                 synchronize_sched();
1867                 filter_free_subsystem_filters(system);
1868                 __free_filter(filter);
1869                 goto out_unlock;
1870         }
1871
1872         err = -ENOMEM;
1873         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1874         if (!ps)
1875                 goto out_unlock;
1876
1877         filter = __alloc_filter();
1878         if (!filter)
1879                 goto out;
1880
1881         replace_filter_string(filter, filter_string);
1882         /*
1883          * No event actually uses the system filter
1884          * we can free it without synchronize_sched().
1885          */
1886         __free_filter(system->filter);
1887         system->filter = filter;
1888
1889         parse_init(ps, filter_ops, filter_string);
1890         err = filter_parse(ps);
1891         if (err) {
1892                 append_filter_err(ps, system->filter);
1893                 goto out;
1894         }
1895
1896         err = replace_system_preds(system, ps, filter_string);
1897         if (err)
1898                 append_filter_err(ps, system->filter);
1899
1900 out:
1901         filter_opstack_clear(ps);
1902         postfix_clear(ps);
1903         kfree(ps);
1904 out_unlock:
1905         mutex_unlock(&event_mutex);
1906
1907         return err;
1908 }
1909
1910 #ifdef CONFIG_PERF_EVENTS
1911
1912 void ftrace_profile_free_filter(struct perf_event *event)
1913 {
1914         struct event_filter *filter = event->filter;
1915
1916         event->filter = NULL;
1917         __free_filter(filter);
1918 }
1919
1920 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1921                               char *filter_str)
1922 {
1923         int err;
1924         struct event_filter *filter;
1925         struct filter_parse_state *ps;
1926         struct ftrace_event_call *call = NULL;
1927
1928         mutex_lock(&event_mutex);
1929
1930         list_for_each_entry(call, &ftrace_events, list) {
1931                 if (call->event.type == event_id)
1932                         break;
1933         }
1934
1935         err = -EINVAL;
1936         if (&call->list == &ftrace_events)
1937                 goto out_unlock;
1938
1939         err = -EEXIST;
1940         if (event->filter)
1941                 goto out_unlock;
1942
1943         filter = __alloc_filter();
1944         if (!filter) {
1945                 err = PTR_ERR(filter);
1946                 goto out_unlock;
1947         }
1948
1949         err = -ENOMEM;
1950         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1951         if (!ps)
1952                 goto free_filter;
1953
1954         parse_init(ps, filter_ops, filter_str);
1955         err = filter_parse(ps);
1956         if (err)
1957                 goto free_ps;
1958
1959         err = replace_preds(call, filter, ps, filter_str, false);
1960         if (!err)
1961                 event->filter = filter;
1962
1963 free_ps:
1964         filter_opstack_clear(ps);
1965         postfix_clear(ps);
1966         kfree(ps);
1967
1968 free_filter:
1969         if (err)
1970                 __free_filter(filter);
1971
1972 out_unlock:
1973         mutex_unlock(&event_mutex);
1974
1975         return err;
1976 }
1977
1978 #endif /* CONFIG_PERF_EVENTS */
1979