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