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 ftrace_event_call *call, char *name)
 501 {
 502         struct ftrace_event_field *field;
 503
 504         list_for_each_entry(field, &call->fields, link) {
 505                 if (!strcmp(field->name, name))
 506                         return field;
 507         }
 508
 509         return NULL;
 510 }
 511
 512 static void filter_free_pred(struct filter_pred *pred)
 513 {
 514         if (!pred)
 515                 return;
 516
 517         kfree(pred->field_name);
 518         kfree(pred);
 519 }
 520
 521 static void filter_clear_pred(struct filter_pred *pred)
 522 {
 523         kfree(pred->field_name);
 524         pred->field_name = NULL;
 525         pred->regex.len = 0;
 526 }
 527
 528 static int filter_set_pred(struct filter_pred *dest,
 529                            struct filter_pred *src,
 530                            filter_pred_fn_t fn)
 531 {
 532         *dest = *src;
 533         if (src->field_name) {
 534                 dest->field_name = kstrdup(src->field_name, GFP_KERNEL);
 535                 if (!dest->field_name)
 536                         return -ENOMEM;
 537         }
 538         dest->fn = fn;
 539
 540         return 0;
 541 }
 542
 543 static void filter_disable_preds(struct ftrace_event_call *call)
 544 {
 545         struct event_filter *filter = call->filter;
 546         int i;
 547
 548         call->filter_active = 0;
 549         filter->n_preds = 0;
 550
 551         for (i = 0; i < MAX_FILTER_PRED; i++)
 552                 filter->preds[i]->fn = filter_pred_none;
 553 }
 554
 555 static void __free_preds(struct event_filter *filter)
 556 {
 557         int i;
 558
 559         if (!filter)
 560                 return;
 561
 562         for (i = 0; i < MAX_FILTER_PRED; i++) {
 563                 if (filter->preds[i])
 564                         filter_free_pred(filter->preds[i]);
 565         }
 566         kfree(filter->preds);
 567         kfree(filter->filter_string);
 568         kfree(filter);
 569 }
 570
 571 void destroy_preds(struct ftrace_event_call *call)
 572 {
 573         __free_preds(call->filter);
 574         call->filter = NULL;
 575         call->filter_active = 0;
 576 }
 577
 578 static struct event_filter *__alloc_preds(void)
 579 {
 580         struct event_filter *filter;
 581         struct filter_pred *pred;
 582         int i;
 583
 584         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 585         if (!filter)
 586                 return ERR_PTR(-ENOMEM);
 587
 588         filter->n_preds = 0;
 589
 590         filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred), GFP_KERNEL);
 591         if (!filter->preds)
 592                 goto oom;
 593
 594         for (i = 0; i < MAX_FILTER_PRED; i++) {
 595                 pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 596                 if (!pred)
 597                         goto oom;
 598                 pred->fn = filter_pred_none;
 599                 filter->preds[i] = pred;
 600         }
 601
 602         return filter;
 603
 604 oom:
 605         __free_preds(filter);
 606         return ERR_PTR(-ENOMEM);
 607 }
 608
 609 static int init_preds(struct ftrace_event_call *call)
 610 {
 611         if (call->filter)
 612                 return 0;
 613
 614         call->filter_active = 0;
 615         call->filter = __alloc_preds();
 616         if (IS_ERR(call->filter))
 617                 return PTR_ERR(call->filter);
 618
 619         return 0;
 620 }
 621
 622 static int init_subsystem_preds(struct event_subsystem *system)
 623 {
 624         struct ftrace_event_call *call;
 625         int err;
 626
 627         list_for_each_entry(call, &ftrace_events, list) {
 628                 if (!call->define_fields)
 629                         continue;
 630
 631                 if (strcmp(call->system, system->name) != 0)
 632                         continue;
 633
 634                 err = init_preds(call);
 635                 if (err)
 636                         return err;
 637         }
 638
 639         return 0;
 640 }
 641
 642 static void filter_free_subsystem_preds(struct event_subsystem *system)
 643 {
 644         struct ftrace_event_call *call;
 645
 646         list_for_each_entry(call, &ftrace_events, list) {
 647                 if (!call->define_fields)
 648                         continue;
 649
 650                 if (strcmp(call->system, system->name) != 0)
 651                         continue;
 652
 653                 filter_disable_preds(call);
 654                 remove_filter_string(call->filter);
 655         }
 656 }
 657
 658 static int filter_add_pred_fn(struct filter_parse_state *ps,
 659                               struct ftrace_event_call *call,
 660                               struct event_filter *filter,
 661                               struct filter_pred *pred,
 662                               filter_pred_fn_t fn)
 663 {
 664         int idx, err;
 665
 666         if (filter->n_preds == MAX_FILTER_PRED) {
 667                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 668                 return -ENOSPC;
 669         }
 670
 671         idx = filter->n_preds;
 672         filter_clear_pred(filter->preds[idx]);
 673         err = filter_set_pred(filter->preds[idx], pred, fn);
 674         if (err)
 675                 return err;
 676
 677         filter->n_preds++;
 678
 679         return 0;
 680 }
 681
 682 int filter_assign_type(const char *type)
 683 {
 684         if (strstr(type, "__data_loc") && strstr(type, "char"))
 685                 return FILTER_DYN_STRING;
 686
 687         if (strchr(type, '[') && strstr(type, "char"))
 688                 return FILTER_STATIC_STRING;
 689
 690         return FILTER_OTHER;
 691 }
 692
 693 static bool is_string_field(struct ftrace_event_field *field)
 694 {
 695         return field->filter_type == FILTER_DYN_STRING ||
 696                field->filter_type == FILTER_STATIC_STRING ||
 697                field->filter_type == FILTER_PTR_STRING;
 698 }
 699
 700 static int is_legal_op(struct ftrace_event_field *field, int op)
 701 {
 702         if (is_string_field(field) &&
 703             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 704                 return 0;
 705         if (!is_string_field(field) && op == OP_GLOB)
 706                 return 0;
 707
 708         return 1;
 709 }
 710
 711 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 712                                              int field_is_signed)
 713 {
 714         filter_pred_fn_t fn = NULL;
 715
 716         switch (field_size) {
 717         case 8:
 718                 if (op == OP_EQ || op == OP_NE)
 719                         fn = filter_pred_64;
 720                 else if (field_is_signed)
 721                         fn = filter_pred_s64;
 722                 else
 723                         fn = filter_pred_u64;
 724                 break;
 725         case 4:
 726                 if (op == OP_EQ || op == OP_NE)
 727                         fn = filter_pred_32;
 728                 else if (field_is_signed)
 729                         fn = filter_pred_s32;
 730                 else
 731                         fn = filter_pred_u32;
 732                 break;
 733         case 2:
 734                 if (op == OP_EQ || op == OP_NE)
 735                         fn = filter_pred_16;
 736                 else if (field_is_signed)
 737                         fn = filter_pred_s16;
 738                 else
 739                         fn = filter_pred_u16;
 740                 break;
 741         case 1:
 742                 if (op == OP_EQ || op == OP_NE)
 743                         fn = filter_pred_8;
 744                 else if (field_is_signed)
 745                         fn = filter_pred_s8;
 746                 else
 747                         fn = filter_pred_u8;
 748                 break;
 749         }
 750
 751         return fn;
 752 }
 753
 754 static int filter_add_pred(struct filter_parse_state *ps,
 755                            struct ftrace_event_call *call,
 756                            struct event_filter *filter,
 757                            struct filter_pred *pred,
 758                            bool dry_run)
 759 {
 760         struct ftrace_event_field *field;
 761         filter_pred_fn_t fn;
 762         unsigned long long val;
 763         int ret;
 764
 765         pred->fn = filter_pred_none;
 766
 767         if (pred->op == OP_AND) {
 768                 pred->pop_n = 2;
 769                 fn = filter_pred_and;
 770                 goto add_pred_fn;
 771         } else if (pred->op == OP_OR) {
 772                 pred->pop_n = 2;
 773                 fn = filter_pred_or;
 774                 goto add_pred_fn;
 775         }
 776
 777         field = find_event_field(call, pred->field_name);
 778         if (!field) {
 779                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 780                 return -EINVAL;
 781         }
 782
 783         pred->offset = field->offset;
 784
 785         if (!is_legal_op(field, pred->op)) {
 786                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 787                 return -EINVAL;
 788         }
 789
 790         if (is_string_field(field)) {
 791                 filter_build_regex(pred);
 792
 793                 if (field->filter_type == FILTER_STATIC_STRING) {
 794                         fn = filter_pred_string;
 795                         pred->regex.field_len = field->size;
 796                 } else if (field->filter_type == FILTER_DYN_STRING)
 797                         fn = filter_pred_strloc;
 798                 else
 799                         fn = filter_pred_pchar;
 800         } else {
 801                 if (field->is_signed)
 802                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 803                 else
 804                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 805                 if (ret) {
 806                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 807                         return -EINVAL;
 808                 }
 809                 pred->val = val;
 810
 811                 fn = select_comparison_fn(pred->op, field->size,
 812                                           field->is_signed);
 813                 if (!fn) {
 814                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 815                         return -EINVAL;
 816                 }
 817         }
 818
 819         if (pred->op == OP_NE)
 820                 pred->not = 1;
 821
 822 add_pred_fn:
 823         if (!dry_run)
 824                 return filter_add_pred_fn(ps, call, filter, pred, fn);
 825         return 0;
 826 }
 827
 828 static void parse_init(struct filter_parse_state *ps,
 829                        struct filter_op *ops,
 830                        char *infix_string)
 831 {
 832         memset(ps, '\0', sizeof(*ps));
 833
 834         ps->infix.string = infix_string;
 835         ps->infix.cnt = strlen(infix_string);
 836         ps->ops = ops;
 837
 838         INIT_LIST_HEAD(&ps->opstack);
 839         INIT_LIST_HEAD(&ps->postfix);
 840 }
 841
 842 static char infix_next(struct filter_parse_state *ps)
 843 {
 844         ps->infix.cnt--;
 845
 846         return ps->infix.string[ps->infix.tail++];
 847 }
 848
 849 static char infix_peek(struct filter_parse_state *ps)
 850 {
 851         if (ps->infix.tail == strlen(ps->infix.string))
 852                 return 0;
 853
 854         return ps->infix.string[ps->infix.tail];
 855 }
 856
 857 static void infix_advance(struct filter_parse_state *ps)
 858 {
 859         ps->infix.cnt--;
 860         ps->infix.tail++;
 861 }
 862
 863 static inline int is_precedence_lower(struct filter_parse_state *ps,
 864                                       int a, int b)
 865 {
 866         return ps->ops[a].precedence < ps->ops[b].precedence;
 867 }
 868
 869 static inline int is_op_char(struct filter_parse_state *ps, char c)
 870 {
 871         int i;
 872
 873         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 874                 if (ps->ops[i].string[0] == c)
 875                         return 1;
 876         }
 877
 878         return 0;
 879 }
 880
 881 static int infix_get_op(struct filter_parse_state *ps, char firstc)
 882 {
 883         char nextc = infix_peek(ps);
 884         char opstr[3];
 885         int i;
 886
 887         opstr[0] = firstc;
 888         opstr[1] = nextc;
 889         opstr[2] = '\0';
 890
 891         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 892                 if (!strcmp(opstr, ps->ops[i].string)) {
 893                         infix_advance(ps);
 894                         return ps->ops[i].id;
 895                 }
 896         }
 897
 898         opstr[1] = '\0';
 899
 900         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 901                 if (!strcmp(opstr, ps->ops[i].string))
 902                         return ps->ops[i].id;
 903         }
 904
 905         return OP_NONE;
 906 }
 907
 908 static inline void clear_operand_string(struct filter_parse_state *ps)
 909 {
 910         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
 911         ps->operand.tail = 0;
 912 }
 913
 914 static inline int append_operand_char(struct filter_parse_state *ps, char c)
 915 {
 916         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
 917                 return -EINVAL;
 918
 919         ps->operand.string[ps->operand.tail++] = c;
 920
 921         return 0;
 922 }
 923
 924 static int filter_opstack_push(struct filter_parse_state *ps, int op)
 925 {
 926         struct opstack_op *opstack_op;
 927
 928         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
 929         if (!opstack_op)
 930                 return -ENOMEM;
 931
 932         opstack_op->op = op;
 933         list_add(&opstack_op->list, &ps->opstack);
 934
 935         return 0;
 936 }
 937
 938 static int filter_opstack_empty(struct filter_parse_state *ps)
 939 {
 940         return list_empty(&ps->opstack);
 941 }
 942
 943 static int filter_opstack_top(struct filter_parse_state *ps)
 944 {
 945         struct opstack_op *opstack_op;
 946
 947         if (filter_opstack_empty(ps))
 948                 return OP_NONE;
 949
 950         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 951
 952         return opstack_op->op;
 953 }
 954
 955 static int filter_opstack_pop(struct filter_parse_state *ps)
 956 {
 957         struct opstack_op *opstack_op;
 958         int op;
 959
 960         if (filter_opstack_empty(ps))
 961                 return OP_NONE;
 962
 963         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 964         op = opstack_op->op;
 965         list_del(&opstack_op->list);
 966
 967         kfree(opstack_op);
 968
 969         return op;
 970 }
 971
 972 static void filter_opstack_clear(struct filter_parse_state *ps)
 973 {
 974         while (!filter_opstack_empty(ps))
 975                 filter_opstack_pop(ps);
 976 }
 977
 978 static char *curr_operand(struct filter_parse_state *ps)
 979 {
 980         return ps->operand.string;
 981 }
 982
 983 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
 984 {
 985         struct postfix_elt *elt;
 986
 987         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 988         if (!elt)
 989                 return -ENOMEM;
 990
 991         elt->op = OP_NONE;
 992         elt->operand = kstrdup(operand, GFP_KERNEL);
 993         if (!elt->operand) {
 994                 kfree(elt);
 995                 return -ENOMEM;
 996         }
 997
 998         list_add_tail(&elt->list, &ps->postfix);
 999
1000         return 0;
1001 }
1002
1003 static int postfix_append_op(struct filter_parse_state *ps, int op)
1004 {
1005         struct postfix_elt *elt;
1006
1007         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
1008         if (!elt)
1009                 return -ENOMEM;
1010
1011         elt->op = op;
1012         elt->operand = NULL;
1013
1014         list_add_tail(&elt->list, &ps->postfix);
1015
1016         return 0;
1017 }
1018
1019 static void postfix_clear(struct filter_parse_state *ps)
1020 {
1021         struct postfix_elt *elt;
1022
1023         while (!list_empty(&ps->postfix)) {
1024                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
1025                 list_del(&elt->list);
1026                 kfree(elt->operand);
1027                 kfree(elt);
1028         }
1029 }
1030
1031 static int filter_parse(struct filter_parse_state *ps)
1032 {
1033         int in_string = 0;
1034         int op, top_op;
1035         char ch;
1036
1037         while ((ch = infix_next(ps))) {
1038                 if (ch == '"') {
1039                         in_string ^= 1;
1040                         continue;
1041                 }
1042
1043                 if (in_string)
1044                         goto parse_operand;
1045
1046                 if (isspace(ch))
1047                         continue;
1048
1049                 if (is_op_char(ps, ch)) {
1050                         op = infix_get_op(ps, ch);
1051                         if (op == OP_NONE) {
1052                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1053                                 return -EINVAL;
1054                         }
1055
1056                         if (strlen(curr_operand(ps))) {
1057                                 postfix_append_operand(ps, curr_operand(ps));
1058                                 clear_operand_string(ps);
1059                         }
1060
1061                         while (!filter_opstack_empty(ps)) {
1062                                 top_op = filter_opstack_top(ps);
1063                                 if (!is_precedence_lower(ps, top_op, op)) {
1064                                         top_op = filter_opstack_pop(ps);
1065                                         postfix_append_op(ps, top_op);
1066                                         continue;
1067                                 }
1068                                 break;
1069                         }
1070
1071                         filter_opstack_push(ps, op);
1072                         continue;
1073                 }
1074
1075                 if (ch == '(') {
1076                         filter_opstack_push(ps, OP_OPEN_PAREN);
1077                         continue;
1078                 }
1079
1080                 if (ch == ')') {
1081                         if (strlen(curr_operand(ps))) {
1082                                 postfix_append_operand(ps, curr_operand(ps));
1083                                 clear_operand_string(ps);
1084                         }
1085
1086                         top_op = filter_opstack_pop(ps);
1087                         while (top_op != OP_NONE) {
1088                                 if (top_op == OP_OPEN_PAREN)
1089                                         break;
1090                                 postfix_append_op(ps, top_op);
1091                                 top_op = filter_opstack_pop(ps);
1092                         }
1093                         if (top_op == OP_NONE) {
1094                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1095                                 return -EINVAL;
1096                         }
1097                         continue;
1098                 }
1099 parse_operand:
1100                 if (append_operand_char(ps, ch)) {
1101                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1102                         return -EINVAL;
1103                 }
1104         }
1105
1106         if (strlen(curr_operand(ps)))
1107                 postfix_append_operand(ps, curr_operand(ps));
1108
1109         while (!filter_opstack_empty(ps)) {
1110                 top_op = filter_opstack_pop(ps);
1111                 if (top_op == OP_NONE)
1112                         break;
1113                 if (top_op == OP_OPEN_PAREN) {
1114                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1115                         return -EINVAL;
1116                 }
1117                 postfix_append_op(ps, top_op);
1118         }
1119
1120         return 0;
1121 }
1122
1123 static struct filter_pred *create_pred(int op, char *operand1, char *operand2)
1124 {
1125         struct filter_pred *pred;
1126
1127         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1128         if (!pred)
1129                 return NULL;
1130
1131         pred->field_name = kstrdup(operand1, GFP_KERNEL);
1132         if (!pred->field_name) {
1133                 kfree(pred);
1134                 return NULL;
1135         }
1136
1137         strcpy(pred->regex.pattern, operand2);
1138         pred->regex.len = strlen(pred->regex.pattern);
1139
1140         pred->op = op;
1141
1142         return pred;
1143 }
1144
1145 static struct filter_pred *create_logical_pred(int op)
1146 {
1147         struct filter_pred *pred;
1148
1149         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1150         if (!pred)
1151                 return NULL;
1152
1153         pred->op = op;
1154
1155         return pred;
1156 }
1157
1158 static int check_preds(struct filter_parse_state *ps)
1159 {
1160         int n_normal_preds = 0, n_logical_preds = 0;
1161         struct postfix_elt *elt;
1162
1163         list_for_each_entry(elt, &ps->postfix, list) {
1164                 if (elt->op == OP_NONE)
1165                         continue;
1166
1167                 if (elt->op == OP_AND || elt->op == OP_OR) {
1168                         n_logical_preds++;
1169                         continue;
1170                 }
1171                 n_normal_preds++;
1172         }
1173
1174         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1175                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1176                 return -EINVAL;
1177         }
1178
1179         return 0;
1180 }
1181
1182 static int replace_preds(struct ftrace_event_call *call,
1183                          struct event_filter *filter,
1184                          struct filter_parse_state *ps,
1185                          char *filter_string,
1186                          bool dry_run)
1187 {
1188         char *operand1 = NULL, *operand2 = NULL;
1189         struct filter_pred *pred;
1190         struct postfix_elt *elt;
1191         int err;
1192         int n_preds = 0;
1193
1194         err = check_preds(ps);
1195         if (err)
1196                 return err;
1197
1198         list_for_each_entry(elt, &ps->postfix, list) {
1199                 if (elt->op == OP_NONE) {
1200                         if (!operand1)
1201                                 operand1 = elt->operand;
1202                         else if (!operand2)
1203                                 operand2 = elt->operand;
1204                         else {
1205                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1206                                 return -EINVAL;
1207                         }
1208                         continue;
1209                 }
1210
1211                 if (n_preds++ == MAX_FILTER_PRED) {
1212                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1213                         return -ENOSPC;
1214                 }
1215
1216                 if (elt->op == OP_AND || elt->op == OP_OR) {
1217                         pred = create_logical_pred(elt->op);
1218                         goto add_pred;
1219                 }
1220
1221                 if (!operand1 || !operand2) {
1222                         parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1223                         return -EINVAL;
1224                 }
1225
1226                 pred = create_pred(elt->op, operand1, operand2);
1227 add_pred:
1228                 if (!pred)
1229                         return -ENOMEM;
1230                 err = filter_add_pred(ps, call, filter, pred, dry_run);
1231                 filter_free_pred(pred);
1232                 if (err)
1233                         return err;
1234
1235                 operand1 = operand2 = NULL;
1236         }
1237
1238         return 0;
1239 }
1240
1241 static int replace_system_preds(struct event_subsystem *system,
1242                                 struct filter_parse_state *ps,
1243                                 char *filter_string)
1244 {
1245         struct ftrace_event_call *call;
1246         bool fail = true;
1247         int err;
1248
1249         list_for_each_entry(call, &ftrace_events, list) {
1250                 struct event_filter *filter = call->filter;
1251
1252                 if (!call->define_fields)
1253                         continue;
1254
1255                 if (strcmp(call->system, system->name) != 0)
1256                         continue;
1257
1258                 /* try to see if the filter can be applied */
1259                 err = replace_preds(call, filter, ps, filter_string, true);
1260                 if (err)
1261                         continue;
1262
1263                 /* really apply the filter */
1264                 filter_disable_preds(call);
1265                 err = replace_preds(call, filter, ps, filter_string, false);
1266                 if (err)
1267                         filter_disable_preds(call);
1268                 else {
1269                         call->filter_active = 1;
1270                         replace_filter_string(filter, filter_string);
1271                 }
1272                 fail = false;
1273         }
1274
1275         if (fail) {
1276                 parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1277                 return -EINVAL;
1278         }
1279         return 0;
1280 }
1281
1282 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1283 {
1284         int err;
1285         struct filter_parse_state *ps;
1286
1287         mutex_lock(&event_mutex);
1288
1289         err = init_preds(call);
1290         if (err)
1291                 goto out_unlock;
1292
1293         if (!strcmp(strstrip(filter_string), "0")) {
1294                 filter_disable_preds(call);
1295                 remove_filter_string(call->filter);
1296                 goto out_unlock;
1297         }
1298
1299         err = -ENOMEM;
1300         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1301         if (!ps)
1302                 goto out_unlock;
1303
1304         filter_disable_preds(call);
1305         replace_filter_string(call->filter, filter_string);
1306
1307         parse_init(ps, filter_ops, filter_string);
1308         err = filter_parse(ps);
1309         if (err) {
1310                 append_filter_err(ps, call->filter);
1311                 goto out;
1312         }
1313
1314         err = replace_preds(call, call->filter, ps, filter_string, false);
1315         if (err)
1316                 append_filter_err(ps, call->filter);
1317         else
1318                 call->filter_active = 1;
1319 out:
1320         filter_opstack_clear(ps);
1321         postfix_clear(ps);
1322         kfree(ps);
1323 out_unlock:
1324         mutex_unlock(&event_mutex);
1325
1326         return err;
1327 }
1328
1329 int apply_subsystem_event_filter(struct event_subsystem *system,
1330                                  char *filter_string)
1331 {
1332         int err;
1333         struct filter_parse_state *ps;
1334
1335         mutex_lock(&event_mutex);
1336
1337         err = init_subsystem_preds(system);
1338         if (err)
1339                 goto out_unlock;
1340
1341         if (!strcmp(strstrip(filter_string), "0")) {
1342                 filter_free_subsystem_preds(system);
1343                 remove_filter_string(system->filter);
1344                 goto out_unlock;
1345         }
1346
1347         err = -ENOMEM;
1348         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1349         if (!ps)
1350                 goto out_unlock;
1351
1352         replace_filter_string(system->filter, filter_string);
1353
1354         parse_init(ps, filter_ops, filter_string);
1355         err = filter_parse(ps);
1356         if (err) {
1357                 append_filter_err(ps, system->filter);
1358                 goto out;
1359         }
1360
1361         err = replace_system_preds(system, ps, filter_string);
1362         if (err)
1363                 append_filter_err(ps, system->filter);
1364
1365 out:
1366         filter_opstack_clear(ps);
1367         postfix_clear(ps);
1368         kfree(ps);
1369 out_unlock:
1370         mutex_unlock(&event_mutex);
1371
1372         return err;
1373 }
1374
1375 #ifdef CONFIG_PERF_EVENTS
1376
1377 void ftrace_profile_free_filter(struct perf_event *event)
1378 {
1379         struct event_filter *filter = event->filter;
1380
1381         event->filter = NULL;
1382         __free_preds(filter);
1383 }
1384
1385 int ftrace_profile_set_filter(struct perf_event *event, int event_id,
1386                               char *filter_str)
1387 {
1388         int err;
1389         struct event_filter *filter;
1390         struct filter_parse_state *ps;
1391         struct ftrace_event_call *call = NULL;
1392
1393         mutex_lock(&event_mutex);
1394
1395         list_for_each_entry(call, &ftrace_events, list) {
1396                 if (call->id == event_id)
1397                         break;
1398         }
1399
1400         err = -EINVAL;
1401         if (!call)
1402                 goto out_unlock;
1403
1404         err = -EEXIST;
1405         if (event->filter)
1406                 goto out_unlock;
1407
1408         filter = __alloc_preds();
1409         if (IS_ERR(filter)) {
1410                 err = PTR_ERR(filter);
1411                 goto out_unlock;
1412         }
1413
1414         err = -ENOMEM;
1415         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1416         if (!ps)
1417                 goto free_preds;
1418
1419         parse_init(ps, filter_ops, filter_str);
1420         err = filter_parse(ps);
1421         if (err)
1422                 goto free_ps;
1423
1424         err = replace_preds(call, filter, ps, filter_str, false);
1425         if (!err)
1426                 event->filter = filter;
1427
1428 free_ps:
1429         filter_opstack_clear(ps);
1430         postfix_clear(ps);
1431         kfree(ps);
1432
1433 free_preds:
1434         if (err)
1435                 __free_preds(filter);
1436
1437 out_unlock:
1438         mutex_unlock(&event_mutex);
1439
1440         return err;
1441 }
1442
1443 #endif /* CONFIG_PERF_EVENTS */
1444