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