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 #define DEFINE_COMPARISON_PRED(type)                                    \
 127 static int filter_pred_##type(struct filter_pred *pred, void *event,    \
 128                               int val1, int val2)                       \
 129 {                                                                       \
 130         type *addr = (type *)(event + pred->offset);                    \
 131         type val = (type)pred->val;                                     \
 132         int match = 0;                                                  \
 133                                                                         \
 134         switch (pred->op) {                                             \
 135         case OP_LT:                                                     \
 136                 match = (*addr < val);                                  \
 137                 break;                                                  \
 138         case OP_LE:                                                     \
 139                 match = (*addr <= val);                                 \
 140                 break;                                                  \
 141         case OP_GT:                                                     \
 142                 match = (*addr > val);                                  \
 143                 break;                                                  \
 144         case OP_GE:                                                     \
 145                 match = (*addr >= val);                                 \
 146                 break;                                                  \
 147         default:                                                        \
 148                 break;                                                  \
 149         }                                                               \
 150                                                                         \
 151         return match;                                                   \
 152 }
 153
 154 #define DEFINE_EQUALITY_PRED(size)                                      \
 155 static int filter_pred_##size(struct filter_pred *pred, void *event,    \
 156                               int val1, int val2)                       \
 157 {                                                                       \
 158         u##size *addr = (u##size *)(event + pred->offset);              \
 159         u##size val = (u##size)pred->val;                               \
 160         int match;                                                      \
 161                                                                         \
 162         match = (val == *addr) ^ pred->not;                             \
 163                                                                         \
 164         return match;                                                   \
 165 }
 166
 167 DEFINE_COMPARISON_PRED(s64);
 168 DEFINE_COMPARISON_PRED(u64);
 169 DEFINE_COMPARISON_PRED(s32);
 170 DEFINE_COMPARISON_PRED(u32);
 171 DEFINE_COMPARISON_PRED(s16);
 172 DEFINE_COMPARISON_PRED(u16);
 173 DEFINE_COMPARISON_PRED(s8);
 174 DEFINE_COMPARISON_PRED(u8);
 175
 176 DEFINE_EQUALITY_PRED(64);
 177 DEFINE_EQUALITY_PRED(32);
 178 DEFINE_EQUALITY_PRED(16);
 179 DEFINE_EQUALITY_PRED(8);
 180
 181 static int filter_pred_and(struct filter_pred *pred __attribute((unused)),
 182                            void *event __attribute((unused)),
 183                            int val1, int val2)
 184 {
 185         return val1 && val2;
 186 }
 187
 188 static int filter_pred_or(struct filter_pred *pred __attribute((unused)),
 189                           void *event __attribute((unused)),
 190                           int val1, int val2)
 191 {
 192         return val1 || val2;
 193 }
 194
 195 /* Filter predicate for fixed sized arrays of characters */
 196 static int filter_pred_string(struct filter_pred *pred, void *event,
 197                               int val1, int val2)
 198 {
 199         char *addr = (char *)(event + pred->offset);
 200         int cmp, match;
 201
 202         cmp = pred->regex.match(addr, &pred->regex, pred->regex.field_len);
 203
 204         match = cmp ^ pred->not;
 205
 206         return match;
 207 }
 208
 209 /* Filter predicate for char * pointers */
 210 static int filter_pred_pchar(struct filter_pred *pred, void *event,
 211                              int val1, int val2)
 212 {
 213         char **addr = (char **)(event + pred->offset);
 214         int cmp, match;
 215         int len = strlen(*addr) + 1;    /* including tailing '\0' */
 216
 217         cmp = pred->regex.match(*addr, &pred->regex, len);
 218
 219         match = cmp ^ pred->not;
 220
 221         return match;
 222 }
 223
 224 /*
 225  * Filter predicate for dynamic sized arrays of characters.
 226  * These are implemented through a list of strings at the end
 227  * of the entry.
 228  * Also each of these strings have a field in the entry which
 229  * contains its offset from the beginning of the entry.
 230  * We have then first to get this field, dereference it
 231  * and add it to the address of the entry, and at last we have
 232  * the address of the string.
 233  */
 234 static int filter_pred_strloc(struct filter_pred *pred, void *event,
 235                               int val1, int val2)
 236 {
 237         u32 str_item = *(u32 *)(event + pred->offset);
 238         int str_loc = str_item & 0xffff;
 239         int str_len = str_item >> 16;
 240         char *addr = (char *)(event + str_loc);
 241         int cmp, match;
 242
 243         cmp = pred->regex.match(addr, &pred->regex, str_len);
 244
 245         match = cmp ^ pred->not;
 246
 247         return match;
 248 }
 249
 250 static int filter_pred_none(struct filter_pred *pred, void *event,
 251                             int val1, int val2)
 252 {
 253         return 0;
 254 }
 255
 256 /*
 257  * regex_match_foo - Basic regex callbacks
 258  *
 259  * @str: the string to be searched
 260  * @r:   the regex structure containing the pattern string
 261  * @len: the length of the string to be searched (including '\0')
 262  *
 263  * Note:
 264  * - @str might not be NULL-terminated if it's of type DYN_STRING
 265  *   or STATIC_STRING
 266  */
 267
 268 static int regex_match_full(char *str, struct regex *r, int len)
 269 {
 270         if (strncmp(str, r->pattern, len) == 0)
 271                 return 1;
 272         return 0;
 273 }
 274
 275 static int regex_match_front(char *str, struct regex *r, int len)
 276 {
 277         if (strncmp(str, r->pattern, r->len) == 0)
 278                 return 1;
 279         return 0;
 280 }
 281
 282 static int regex_match_middle(char *str, struct regex *r, int len)
 283 {
 284         if (strnstr(str, r->pattern, len))
 285                 return 1;
 286         return 0;
 287 }
 288
 289 static int regex_match_end(char *str, struct regex *r, int len)
 290 {
 291         int strlen = len - 1;
 292
 293         if (strlen >= r->len &&
 294             memcmp(str + strlen - r->len, r->pattern, r->len) == 0)
 295                 return 1;
 296         return 0;
 297 }
 298
 299 /**
 300  * filter_parse_regex - parse a basic regex
 301  * @buff:   the raw regex
 302  * @len:    length of the regex
 303  * @search: will point to the beginning of the string to compare
 304  * @not:    tell whether the match will have to be inverted
 305  *
 306  * This passes in a buffer containing a regex and this function will
 307  * set search to point to the search part of the buffer and
 308  * return the type of search it is (see enum above).
 309  * This does modify buff.
 310  *
 311  * Returns enum type.
 312  *  search returns the pointer to use for comparison.
 313  *  not returns 1 if buff started with a '!'
 314  *     0 otherwise.
 315  */
 316 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
 317 {
 318         int type = MATCH_FULL;
 319         int i;
 320
 321         if (buff[0] == '!') {
 322                 *not = 1;
 323                 buff++;
 324                 len--;
 325         } else
 326                 *not = 0;
 327
 328         *search = buff;
 329
 330         for (i = 0; i < len; i++) {
 331                 if (buff[i] == '*') {
 332                         if (!i) {
 333                                 *search = buff + 1;
 334                                 type = MATCH_END_ONLY;
 335                         } else {
 336                                 if (type == MATCH_END_ONLY)
 337                                         type = MATCH_MIDDLE_ONLY;
 338                                 else
 339                                         type = MATCH_FRONT_ONLY;
 340                                 buff[i] = 0;
 341                                 break;
 342                         }
 343                 }
 344         }
 345
 346         return type;
 347 }
 348
 349 static void filter_build_regex(struct filter_pred *pred)
 350 {
 351         struct regex *r = &pred->regex;
 352         char *search;
 353         enum regex_type type = MATCH_FULL;
 354         int not = 0;
 355
 356         if (pred->op == OP_GLOB) {
 357                 type = filter_parse_regex(r->pattern, r->len, &search, &not);
 358                 r->len = strlen(search);
 359                 memmove(r->pattern, search, r->len+1);
 360         }
 361
 362         switch (type) {
 363         case MATCH_FULL:
 364                 r->match = regex_match_full;
 365                 break;
 366         case MATCH_FRONT_ONLY:
 367                 r->match = regex_match_front;
 368                 break;
 369         case MATCH_MIDDLE_ONLY:
 370                 r->match = regex_match_middle;
 371                 break;
 372         case MATCH_END_ONLY:
 373                 r->match = regex_match_end;
 374                 break;
 375         }
 376
 377         pred->not ^= not;
 378 }
 379
 380 /* return 1 if event matches, 0 otherwise (discard) */
 381 int filter_match_preds(struct event_filter *filter, void *rec)
 382 {
 383         int match, top = 0, val1 = 0, val2 = 0;
 384         int stack[MAX_FILTER_PRED];
 385         struct filter_pred *pred;
 386         int i;
 387
 388         for (i = 0; i < filter->n_preds; i++) {
 389                 pred = filter->preds[i];
 390                 if (!pred->pop_n) {
 391                         match = pred->fn(pred, rec, val1, val2);
 392                         stack[top++] = match;
 393                         continue;
 394                 }
 395                 if (pred->pop_n > top) {
 396                         WARN_ON_ONCE(1);
 397                         return 0;
 398                 }
 399                 val1 = stack[--top];
 400                 val2 = stack[--top];
 401                 match = pred->fn(pred, rec, val1, val2);
 402                 stack[top++] = match;
 403         }
 404
 405         return stack[--top];
 406 }
 407 EXPORT_SYMBOL_GPL(filter_match_preds);
 408
 409 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 410 {
 411         ps->lasterr = err;
 412         ps->lasterr_pos = pos;
 413 }
 414
 415 static void remove_filter_string(struct event_filter *filter)
 416 {
 417         kfree(filter->filter_string);
 418         filter->filter_string = NULL;
 419 }
 420
 421 static int replace_filter_string(struct event_filter *filter,
 422                                  char *filter_string)
 423 {
 424         kfree(filter->filter_string);
 425         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 426         if (!filter->filter_string)
 427                 return -ENOMEM;
 428
 429         return 0;
 430 }
 431
 432 static int append_filter_string(struct event_filter *filter,
 433                                 char *string)
 434 {
 435         int newlen;
 436         char *new_filter_string;
 437
 438         BUG_ON(!filter->filter_string);
 439         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 440         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 441         if (!new_filter_string)
 442                 return -ENOMEM;
 443
 444         strcpy(new_filter_string, filter->filter_string);
 445         strcat(new_filter_string, string);
 446         kfree(filter->filter_string);
 447         filter->filter_string = new_filter_string;
 448
 449         return 0;
 450 }
 451
 452 static void append_filter_err(struct filter_parse_state *ps,
 453                               struct event_filter *filter)
 454 {
 455         int pos = ps->lasterr_pos;
 456         char *buf, *pbuf;
 457
 458         buf = (char *)__get_free_page(GFP_TEMPORARY);
 459         if (!buf)
 460                 return;
 461
 462         append_filter_string(filter, "\n");
 463         memset(buf, ' ', PAGE_SIZE);
 464         if (pos > PAGE_SIZE - 128)
 465                 pos = 0;
 466         buf[pos] = '^';
 467         pbuf = &buf[pos] + 1;
 468
 469         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 470         append_filter_string(filter, buf);
 471         free_page((unsigned long) buf);
 472 }
 473
 474 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 475 {
 476         struct event_filter *filter = call->filter;
 477
 478         mutex_lock(&event_mutex);
 479         if (filter && filter->filter_string)
 480                 trace_seq_printf(s, "%s\n", filter->filter_string);
 481         else
 482                 trace_seq_printf(s, "none\n");
 483         mutex_unlock(&event_mutex);
 484 }
 485
 486 void print_subsystem_event_filter(struct event_subsystem *system,
 487                                   struct trace_seq *s)
 488 {
 489         struct event_filter *filter = system->filter;
 490
 491         mutex_lock(&event_mutex);
 492         if (filter && filter->filter_string)
 493                 trace_seq_printf(s, "%s\n", filter->filter_string);
 494         else
 495                 trace_seq_printf(s, "none\n");
 496         mutex_unlock(&event_mutex);
 497 }
 498
 499 static struct ftrace_event_field *
 500 __find_event_field(struct list_head *head, char *name)
 501 {
 502         struct ftrace_event_field *field;
 503
 504         list_for_each_entry(field, head, link) {
 505                 if (!strcmp(field->name, name))
 506                         return field;
 507         }
 508
 509         return NULL;
 510 }
 511
 512 static struct ftrace_event_field *
 513 find_event_field(struct ftrace_event_call *call, char *name)
 514 {
 515         struct ftrace_event_field *field;
 516         struct list_head *head;
 517
 518         field = __find_event_field(&ftrace_common_fields, name);
 519         if (field)
 520                 return field;
 521
 522         head = trace_get_fields(call);
 523         return __find_event_field(head, name);
 524 }
 525
 526 static void filter_free_pred(struct filter_pred *pred)
 527 {
 528         if (!pred)
 529                 return;
 530
 531         kfree(pred->field_name);
 532         kfree(pred);
 533 }
 534
 535 static void filter_clear_pred(struct filter_pred *pred)
 536 {
 537         kfree(pred->field_name);
 538         pred->field_name = NULL;
 539         pred->regex.len = 0;
 540 }
 541
 542 static int filter_set_pred(struct filter_pred *dest,
 543                            struct filter_pred *src,
 544                            filter_pred_fn_t fn)
 545 {
 546         *dest = *src;
 547         if (src->field_name) {
 548                 dest->field_name = kstrdup(src->field_name, GFP_KERNEL);
 549                 if (!dest->field_name)
 550                         return -ENOMEM;
 551         }
 552         dest->fn = fn;
 553
 554         return 0;
 555 }
 556
 557 static void filter_disable_preds(struct ftrace_event_call *call)
 558 {
 559         struct event_filter *filter = call->filter;
 560         int i;
 561
 562         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 563         filter->n_preds = 0;
 564
 565         for (i = 0; i < MAX_FILTER_PRED; i++)
 566                 filter->preds[i]->fn = filter_pred_none;
 567 }
 568
 569 static void __free_preds(struct event_filter *filter)
 570 {
 571         int i;
 572
 573         if (!filter)
 574                 return;
 575
 576         for (i = 0; i < MAX_FILTER_PRED; i++) {
 577                 if (filter->preds[i])
 578                         filter_free_pred(filter->preds[i]);
 579         }
 580         kfree(filter->preds);
 581         kfree(filter->filter_string);
 582         kfree(filter);
 583 }
 584
 585 void destroy_preds(struct ftrace_event_call *call)
 586 {
 587         __free_preds(call->filter);
 588         call->filter = NULL;
 589         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 590 }
 591
 592 static struct event_filter *__alloc_preds(void)
 593 {
 594         struct event_filter *filter;
 595         struct filter_pred *pred;
 596         int i;
 597
 598         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 599         if (!filter)
 600                 return ERR_PTR(-ENOMEM);
 601
 602         filter->n_preds = 0;
 603
 604         filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred), GFP_KERNEL);
 605         if (!filter->preds)
 606                 goto oom;
 607
 608         for (i = 0; i < MAX_FILTER_PRED; i++) {
 609                 pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 610                 if (!pred)
 611                         goto oom;
 612                 pred->fn = filter_pred_none;
 613                 filter->preds[i] = pred;
 614         }
 615
 616         return filter;
 617
 618 oom:
 619         __free_preds(filter);
 620         return ERR_PTR(-ENOMEM);
 621 }
 622
 623 static int init_preds(struct ftrace_event_call *call)
 624 {
 625         if (call->filter)
 626                 return 0;
 627
 628         call->flags &= ~TRACE_EVENT_FL_FILTERED;
 629         call->filter = __alloc_preds();
 630         if (IS_ERR(call->filter))
 631                 return PTR_ERR(call->filter);
 632
 633         return 0;
 634 }
 635
 636 static int init_subsystem_preds(struct event_subsystem *system)
 637 {
 638         struct ftrace_event_call *call;
 639         int err;
 640
 641         list_for_each_entry(call, &ftrace_events, list) {
 642                 if (strcmp(call->class->system, system->name) != 0)
 643                         continue;
 644
 645                 err = init_preds(call);
 646                 if (err)
 647                         return err;
 648         }
 649
 650         return 0;
 651 }
 652
 653 static void filter_free_subsystem_preds(struct event_subsystem *system)
 654 {
 655         struct ftrace_event_call *call;
 656
 657         list_for_each_entry(call, &ftrace_events, list) {
 658                 if (strcmp(call->class->system, system->name) != 0)
 659                         continue;
 660
 661                 filter_disable_preds(call);
 662                 remove_filter_string(call->filter);
 663         }
 664 }
 665
 666 static int filter_add_pred_fn(struct filter_parse_state *ps,
 667                               struct ftrace_event_call *call,
 668                               struct event_filter *filter,
 669                               struct filter_pred *pred,
 670                               filter_pred_fn_t fn)
 671 {
 672         int idx, err;
 673
 674         if (filter->n_preds == MAX_FILTER_PRED) {
 675                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 676                 return -ENOSPC;
 677         }
 678
 679         idx = filter->n_preds;
 680         filter_clear_pred(filter->preds[idx]);
 681         err = filter_set_pred(filter->preds[idx], pred, fn);
 682         if (err)
 683                 return err;
 684
 685         filter->n_preds++;
 686
 687         return 0;
 688 }
 689
 690 int filter_assign_type(const char *type)
 691 {
 692         if (strstr(type, "__data_loc") && strstr(type, "char"))
 693                 return FILTER_DYN_STRING;
 694
 695         if (strchr(type, '[') && strstr(type, "char"))
 696                 return FILTER_STATIC_STRING;
 697
 698         return FILTER_OTHER;
 699 }
 700
 701 static bool is_string_field(struct ftrace_event_field *field)
 702 {
 703         return field->filter_type == FILTER_DYN_STRING ||
 704                field->filter_type == FILTER_STATIC_STRING ||
 705                field->filter_type == FILTER_PTR_STRING;
 706 }
 707
 708 static int is_legal_op(struct ftrace_event_field *field, int op)
 709 {
 710         if (is_string_field(field) &&
 711             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 712                 return 0;
 713         if (!is_string_field(field) && op == OP_GLOB)
 714                 return 0;
 715
 716         return 1;
 717 }
 718
 719 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 720                                              int field_is_signed)
 721 {
 722         filter_pred_fn_t fn = NULL;
 723
 724         switch (field_size) {
 725         case 8:
 726                 if (op == OP_EQ || op == OP_NE)
 727                         fn = filter_pred_64;
 728                 else if (field_is_signed)
 729                         fn = filter_pred_s64;
 730                 else
 731                         fn = filter_pred_u64;
 732                 break;
 733         case 4:
 734                 if (op == OP_EQ || op == OP_NE)
 735                         fn = filter_pred_32;
 736                 else if (field_is_signed)
 737                         fn = filter_pred_s32;
 738                 else
 739                         fn = filter_pred_u32;
 740                 break;
 741         case 2:
 742                 if (op == OP_EQ || op == OP_NE)
 743                         fn = filter_pred_16;
 744                 else if (field_is_signed)
 745                         fn = filter_pred_s16;
 746                 else
 747                         fn = filter_pred_u16;
 748                 break;
 749         case 1:
 750                 if (op == OP_EQ || op == OP_NE)
 751                         fn = filter_pred_8;
 752                 else if (field_is_signed)
 753                         fn = filter_pred_s8;
 754                 else
 755                         fn = filter_pred_u8;
 756                 break;
 757         }
 758
 759         return fn;
 760 }
 761
 762 static int filter_add_pred(struct filter_parse_state *ps,
 763                            struct ftrace_event_call *call,
 764                            struct event_filter *filter,
 765                            struct filter_pred *pred,
 766                            bool dry_run)
 767 {
 768         struct ftrace_event_field *field;
 769         filter_pred_fn_t fn;
 770         unsigned long long val;
 771         int ret;
 772
 773         pred->fn = filter_pred_none;
 774
 775         if (pred->op == OP_AND) {
 776                 pred->pop_n = 2;
 777                 fn = filter_pred_and;
 778                 goto add_pred_fn;
 779         } else if (pred->op == OP_OR) {
 780                 pred->pop_n = 2;
 781                 fn = filter_pred_or;
 782                 goto add_pred_fn;
 783         }
 784
 785         field = find_event_field(call, pred->field_name);
 786         if (!field) {
 787                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 788                 return -EINVAL;
 789         }
 790
 791         pred->offset = field->offset;
 792
 793         if (!is_legal_op(field, pred->op)) {
 794                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 795                 return -EINVAL;
 796         }
 797
 798         if (is_string_field(field)) {
 799                 filter_build_regex(pred);
 800
 801                 if (field->filter_type == FILTER_STATIC_STRING) {
 802                         fn = filter_pred_string;
 803                         pred->regex.field_len = field->size;
 804                 } else if (field->filter_type == FILTER_DYN_STRING)
 805                         fn = filter_pred_strloc;
 806                 else
 807                         fn = filter_pred_pchar;
 808         } else {
 809                 if (field->is_signed)
 810                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 811                 else
 812                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 813                 if (ret) {
 814                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 815                         return -EINVAL;
 816                 }
 817                 pred->val = val;
 818
 819                 fn = select_comparison_fn(pred->op, field->size,
 820                                           field->is_signed);
 821                 if (!fn) {
 822                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 823                         return -EINVAL;
 824                 }
 825         }
 826
 827         if (pred->op == OP_NE)
 828                 pred->not = 1;
 829
 830 add_pred_fn:
 831         if (!dry_run)
 832                 return filter_add_pred_fn(ps, call, filter, pred, fn);
 833         return 0;
 834 }
 835
 836 static void parse_init(struct filter_parse_state *ps,
 837                        struct filter_op *ops,
 838                        char *infix_string)
 839 {
 840         memset(ps, '\0', sizeof(*ps));
 841
 842         ps->infix.string = infix_string;
 843         ps->infix.cnt = strlen(infix_string);
 844         ps->ops = ops;
 845
 846         INIT_LIST_HEAD(&ps->opstack);
 847         INIT_LIST_HEAD(&ps->postfix);
 848 }
 849
 850 static char infix_next(struct filter_parse_state *ps)
 851 {
 852         ps->infix.cnt--;
 853
 854         return ps->infix.string[ps->infix.tail++];
 855 }
 856
 857 static char infix_peek(struct filter_parse_state *ps)
 858 {
 859         if (ps->infix.tail == strlen(ps->infix.string))
 860                 return 0;
 861
 862         return ps->infix.string[ps->infix.tail];
 863 }
 864
 865 static void infix_advance(struct filter_parse_state *ps)
 866 {
 867         ps->infix.cnt--;
 868         ps->infix.tail++;
 869 }
 870
 871 static inline int is_precedence_lower(struct filter_parse_state *ps,
 872                                       int a, int b)
 873 {
 874         return ps->ops[a].precedence < ps->ops[b].precedence;
 875 }
 876
 877 static inline int is_op_char(struct filter_parse_state *ps, char c)
 878 {
 879         int i;
 880
 881         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 882                 if (ps->ops[i].string[0] == c)
 883                         return 1;
 884         }
 885
 886         return 0;
 887 }
 888
 889 static int infix_get_op(struct filter_parse_state *ps, char firstc)
 890 {
 891         char nextc = infix_peek(ps);
 892         char opstr[3];
 893         int i;
 894
 895         opstr[0] = firstc;
 896         opstr[1] = nextc;
 897         opstr[2] = '\0';
 898
 899         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 900                 if (!strcmp(opstr, ps->ops[i].string)) {
 901                         infix_advance(ps);
 902                         return ps->ops[i].id;
 903                 }
 904         }
 905
 906         opstr[1] = '\0';
 907
 908         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 909                 if (!strcmp(opstr, ps->ops[i].string))
 910                         return ps->ops[i].id;
 911         }
 912
 913         return OP_NONE;
 914 }
 915
 916 static inline void clear_operand_string(struct filter_parse_state *ps)
 917 {
 918         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
 919         ps->operand.tail = 0;
 920 }
 921
 922 static inline int append_operand_char(struct filter_parse_state *ps, char c)
 923 {
 924         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
 925                 return -EINVAL;
 926
 927         ps->operand.string[ps->operand.tail++] = c;
 928
 929         return 0;
 930 }
 931
 932 static int filter_opstack_push(struct filter_parse_state *ps, int op)
 933 {
 934         struct opstack_op *opstack_op;
 935
 936         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
 937         if (!opstack_op)
 938                 return -ENOMEM;
 939
 940         opstack_op->op = op;
 941         list_add(&opstack_op->list, &ps->opstack);
 942
 943         return 0;
 944 }
 945
 946 static int filter_opstack_empty(struct filter_parse_state *ps)
 947 {
 948         return list_empty(&ps->opstack);
 949 }
 950
 951 static int filter_opstack_top(struct filter_parse_state *ps)
 952 {
 953         struct opstack_op *opstack_op;
 954
 955         if (filter_opstack_empty(ps))
 956                 return OP_NONE;
 957
 958         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 959
 960         return opstack_op->op;
 961 }
 962
 963 static int filter_opstack_pop(struct filter_parse_state *ps)
 964 {
 965         struct opstack_op *opstack_op;
 966         int op;
 967
 968         if (filter_opstack_empty(ps))
 969                 return OP_NONE;
 970
 971         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 972         op = opstack_op->op;
 973         list_del(&opstack_op->list);
 974
 975         kfree(opstack_op);
 976
 977         return op;
 978 }
 979
 980 static void filter_opstack_clear(struct filter_parse_state *ps)
 981 {
 982         while (!filter_opstack_empty(ps))
 983                 filter_opstack_pop(ps);
 984 }
 985
 986 static char *curr_operand(struct filter_parse_state *ps)
 987 {
 988         return ps->operand.string;
 989 }
 990
 991 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
 992 {
 993         struct postfix_elt *elt;
 994
 995         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 996         if (!elt)
 997                 return -ENOMEM;
 998
 999         elt->op = OP_NONE;
1000         elt->operand = kstrdup(operand, GFP_KERNEL);
1001         if (!elt->operand) {
1002                 kfree(elt);
1003                 return -ENOMEM;
1004         }
1005
1006         list_add_tail(&elt->list, &ps->postfix);
1007
1008         return 0;
1009 }
1010
1011 static int postfix_append_op(struct filter_parse_state *ps, int op)
1012 {
1013         struct postfix_elt *elt;
1014
1015         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1016         if (!elt)
1017                 return -ENOMEM;
1018
1019         elt->op = op;
1020         elt->operand = NULL;
1021
1022         list_add_tail(&elt->list, &ps->postfix);
1023
1024         return 0;
1025 }
1026
1027 static void postfix_clear(struct filter_parse_state *ps)
1028 {
1029         struct postfix_elt *elt;
1030
1031         while (!list_empty(&ps->postfix)) {
1032                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1033                 list_del(&elt->list);
1034                 kfree(elt->operand);
1035                 kfree(elt);
1036         }
1037 }
1038
1039 static int filter_parse(struct filter_parse_state *ps)
1040 {
1041         int in_string = 0;
1042         int op, top_op;
1043         char ch;
1044
1045         while ((ch = infix_next(ps))) {
1046                 if (ch == '"') {
1047                         in_string ^= 1;
1048                         continue;
1049                 }
1050
1051                 if (in_string)
1052                         goto parse_operand;
1053
1054                 if (isspace(ch))
1055                         continue;
1056
1057                 if (is_op_char(ps, ch)) {
1058                         op = infix_get_op(ps, ch);
1059                         if (op == OP_NONE) {
1060                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1061                                 return -EINVAL;
1062                         }
1063
1064                         if (strlen(curr_operand(ps))) {
1065                                 postfix_append_operand(ps, curr_operand(ps));
1066                                 clear_operand_string(ps);
1067                         }
1068
1069                         while (!filter_opstack_empty(ps)) {
1070                                 top_op = filter_opstack_top(ps);
1071                                 if (!is_precedence_lower(ps, top_op, op)) {
1072                                         top_op = filter_opstack_pop(ps);
1073                                         postfix_append_op(ps, top_op);
1074                                         continue;
1075                                 }
1076                                 break;
1077                         }
1078
1079                         filter_opstack_push(ps, op);
1080                         continue;
1081                 }
1082
1083                 if (ch == '(') {
1084                         filter_opstack_push(ps, OP_OPEN_PAREN);
1085                         continue;
1086                 }
1087
1088                 if (ch == ')') {
1089                         if (strlen(curr_operand(ps))) {
1090                                 postfix_append_operand(ps, curr_operand(ps));
1091                                 clear_operand_string(ps);
1092                         }
1093
1094                         top_op = filter_opstack_pop(ps);
1095                         while (top_op != OP_NONE) {
1096                                 if (top_op == OP_OPEN_PAREN)
1097                                         break;
1098                                 postfix_append_op(ps, top_op);
1099                                 top_op = filter_opstack_pop(ps);
1100                         }
1101                         if (top_op == OP_NONE) {
1102                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1103                                 return -EINVAL;
1104                         }
1105                         continue;
1106                 }
1107 parse_operand:
1108                 if (append_operand_char(ps, ch)) {
1109                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1110                         return -EINVAL;
1111                 }
1112         }
1113
1114         if (strlen(curr_operand(ps)))
1115                 postfix_append_operand(ps, curr_operand(ps));
1116
1117         while (!filter_opstack_empty(ps)) {
1118                 top_op = filter_opstack_pop(ps);
1119                 if (top_op == OP_NONE)
1120                         break;
1121                 if (top_op == OP_OPEN_PAREN) {
1122                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1123                         return -EINVAL;
1124                 }
1125                 postfix_append_op(ps, top_op);
1126         }
1127
1128         return 0;
1129 }
1130
1131 static struct filter_pred *create_pred(int op, char *operand1, char *operand2)
1132 {
1133         struct filter_pred *pred;
1134
1135         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1136         if (!pred)
1137                 return NULL;
1138
1139         pred->field_name = kstrdup(operand1, GFP_KERNEL);
1140         if (!pred->field_name) {
1141                 kfree(pred);
1142                 return NULL;
1143         }
1144
1145         strcpy(pred->regex.pattern, operand2);
1146         pred->regex.len = strlen(pred->regex.pattern);
1147
1148         pred->op = op;
1149
1150         return pred;
1151 }
1152
1153 static struct filter_pred *create_logical_pred(int op)
1154 {
1155         struct filter_pred *pred;
1156
1157         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1158         if (!pred)
1159                 return NULL;
1160
1161         pred->op = op;
1162
1163         return pred;
1164 }
1165
1166 static int check_preds(struct filter_parse_state *ps)
1167 {
1168         int n_normal_preds = 0, n_logical_preds = 0;
1169         struct postfix_elt *elt;
1170
1171         list_for_each_entry(elt, &ps->postfix, list) {
1172                 if (elt->op == OP_NONE)
1173                         continue;
1174
1175                 if (elt->op == OP_AND || elt->op == OP_OR) {
1176                         n_logical_preds++;
1177                         continue;
1178                 }
1179                 n_normal_preds++;
1180         }
1181
1182         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1183                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1184                 return -EINVAL;
1185         }
1186
1187         return 0;
1188 }
1189
1190 static int replace_preds(struct ftrace_event_call *call,
1191                          struct event_filter *filter,
1192                          struct filter_parse_state *ps,
1193                          char *filter_string,
1194                          bool dry_run)
1195 {
1196         char *operand1 = NULL, *operand2 = NULL;
1197         struct filter_pred *pred;
1198         struct postfix_elt *elt;
1199         int err;
1200         int n_preds = 0;
1201
1202         err = check_preds(ps);
1203         if (err)
1204                 return err;
1205
1206         list_for_each_entry(elt, &ps->postfix, list) {
1207                 if (elt->op == OP_NONE) {
1208                         if (!operand1)
1209                                 operand1 = elt->operand;
1210                         else if (!operand2)
1211                                 operand2 = elt->operand;
1212                         else {
1213                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1214                                 return -EINVAL;
1215                         }
1216                         continue;
1217                 }
1218
1219                 if (n_preds++ == MAX_FILTER_PRED) {
1220                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1221                         return -ENOSPC;
1222                 }
1223
1224                 if (elt->op == OP_AND || elt->op == OP_OR) {
1225                         pred = create_logical_pred(elt->op);
1226                         goto add_pred;
1227                 }
1228
1229                 if (!operand1 || !operand2) {
1230                         parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1231                         return -EINVAL;
1232                 }
1233
1234                 pred = create_pred(elt->op, operand1, operand2);
1235 add_pred:
1236                 if (!pred)
1237                         return -ENOMEM;
1238                 err = filter_add_pred(ps, call, filter, pred, dry_run);
1239                 filter_free_pred(pred);
1240                 if (err)
1241                         return err;
1242
1243                 operand1 = operand2 = NULL;
1244         }
1245
1246         return 0;
1247 }
1248
1249 static int replace_system_preds(struct event_subsystem *system,
1250                                 struct filter_parse_state *ps,
1251                                 char *filter_string)
1252 {
1253         struct ftrace_event_call *call;
1254         bool fail = true;
1255         int err;
1256
1257         list_for_each_entry(call, &ftrace_events, list) {
1258                 struct event_filter *filter = call->filter;
1259
1260                 if (strcmp(call->class->system, system->name) != 0)
1261                         continue;
1262
1263                 /* try to see if the filter can be applied */
1264                 err = replace_preds(call, filter, ps, filter_string, true);
1265                 if (err)
1266                         continue;
1267
1268                 /* really apply the filter */
1269                 filter_disable_preds(call);
1270                 err = replace_preds(call, filter, ps, filter_string, false);
1271                 if (err)
1272                         filter_disable_preds(call);
1273                 else {
1274                         call->flags |= TRACE_EVENT_FL_FILTERED;
1275                         replace_filter_string(filter, filter_string);
1276                 }
1277                 fail = false;
1278         }
1279
1280         if (fail) {
1281                 parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1282                 return -EINVAL;
1283         }
1284         return 0;
1285 }
1286
1287 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1288 {
1289         int err;
1290         struct filter_parse_state *ps;
1291
1292         mutex_lock(&event_mutex);
1293
1294         err = init_preds(call);
1295         if (err)
1296                 goto out_unlock;
1297
1298         if (!strcmp(strstrip(filter_string), "0")) {
1299                 filter_disable_preds(call);
1300                 remove_filter_string(call->filter);
1301                 goto out_unlock;
1302         }
1303
1304         err = -ENOMEM;
1305         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1306         if (!ps)
1307                 goto out_unlock;
1308
1309         filter_disable_preds(call);
1310         replace_filter_string(call->filter, filter_string);
1311
1312         parse_init(ps, filter_ops, filter_string);
1313         err = filter_parse(ps);
1314         if (err) {
1315                 append_filter_err(ps, call->filter);
1316                 goto out;
1317         }
1318
1319         err = replace_preds(call, call->filter, ps, filter_string, false);
1320         if (err)
1321                 append_filter_err(ps, call->filter);
1322         else
1323                 call->flags |= TRACE_EVENT_FL_FILTERED;
1324 out:
1325         filter_opstack_clear(ps);
1326         postfix_clear(ps);
1327         kfree(ps);
1328 out_unlock:
1329         mutex_unlock(&event_mutex);
1330
1331         return err;
1332 }
1333
1334 int apply_subsystem_event_filter(struct event_subsystem *system,
1335                                  char *filter_string)
1336 {
1337         int err;
1338         struct filter_parse_state *ps;
1339
1340         mutex_lock(&event_mutex);
1341
1342         err = init_subsystem_preds(system);
1343         if (err)
1344                 goto out_unlock;
1345
1346         if (!strcmp(strstrip(filter_string), "0")) {
1347                 filter_free_subsystem_preds(system);
1348                 remove_filter_string(system->filter);
1349                 goto out_unlock;
1350         }
1351
1352         err = -ENOMEM;
1353         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1354         if (!ps)
1355                 goto out_unlock;
1356
1357         replace_filter_string(system->filter, filter_string);
1358
1359         parse_init(ps, filter_ops, filter_string);
1360         err = filter_parse(ps);
1361         if (err) {
1362                 append_filter_err(ps, system->filter);
1363                 goto out;
1364         }
1365
1366         err = replace_system_preds(system, ps, filter_string);
1367         if (err)
1368                 append_filter_err(ps, system->filter);
1369
1370 out:
1371         filter_opstack_clear(ps);
1372         postfix_clear(ps);
1373         kfree(ps);
1374 out_unlock:
1375         mutex_unlock(&event_mutex);
1376
1377         return err;
1378 }
1379
1380 #ifdef CONFIG_PERF_EVENTS
1381
1382 void ftrace_profile_free_filter(struct perf_event *event)
1383 {
1384         struct event_filter *filter = event->filter;
1385
1386         event->filter = NULL;
1387         __free_preds(filter);
1388 }
1389
1390 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1391                               char *filter_str)
1392 {
1393         int err;
1394         struct event_filter *filter;
1395         struct filter_parse_state *ps;
1396         struct ftrace_event_call *call = NULL;
1397
1398         mutex_lock(&event_mutex);
1399
1400         list_for_each_entry(call, &ftrace_events, list) {
1401                 if (call->event.type == event_id)
1402                         break;
1403         }
1404
1405         err = -EINVAL;
1406         if (&call->list == &ftrace_events)
1407                 goto out_unlock;
1408
1409         err = -EEXIST;
1410         if (event->filter)
1411                 goto out_unlock;
1412
1413         filter = __alloc_preds();
1414         if (IS_ERR(filter)) {
1415                 err = PTR_ERR(filter);
1416                 goto out_unlock;
1417         }
1418
1419         err = -ENOMEM;
1420         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1421         if (!ps)
1422                 goto free_preds;
1423
1424         parse_init(ps, filter_ops, filter_str);
1425         err = filter_parse(ps);
1426         if (err)
1427                 goto free_ps;
1428
1429         err = replace_preds(call, filter, ps, filter_str, false);
1430         if (!err)
1431                 event->filter = filter;
1432
1433 free_ps:
1434         filter_opstack_clear(ps);
1435         postfix_clear(ps);
1436         kfree(ps);
1437
1438 free_preds:
1439         if (err)
1440                 __free_preds(filter);
1441
1442 out_unlock:
1443         mutex_unlock(&event_mutex);
1444
1445         return err;
1446 }
1447
1448 #endif /* CONFIG_PERF_EVENTS */
1449