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