SAFE public projects git trees. - safe/jmp/linux-2.6/blob - kernel/trace/trace_events_filter.c

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