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 /* Basic regex callbacks */
 256 static int regex_match_full(char *str, struct regex *r, int len)
 257 {
 258         if (strncmp(str, r->pattern, len) == 0)
 259                 return 1;
 260         return 0;
 261 }
 262
 263 static int regex_match_front(char *str, struct regex *r, int len)
 264 {
 265         if (strncmp(str, r->pattern, r->len) == 0)
 266                 return 1;
 267         return 0;
 268 }
 269
 270 static int regex_match_middle(char *str, struct regex *r, int len)
 271 {
 272         if (strnstr(str, r->pattern, len))
 273                 return 1;
 274         return 0;
 275 }
 276
 277 static int regex_match_end(char *str, struct regex *r, int len)
 278 {
 279         int strlen = len - 1;
 280
 281         if (strlen >= r->len &&
 282             memcmp(str + strlen - r->len, r->pattern, r->len) == 0)
 283                 return 1;
 284         return 0;
 285 }
 286
 287 /**
 288  * filter_parse_regex - parse a basic regex
 289  * @buff:   the raw regex
 290  * @len:    length of the regex
 291  * @search: will point to the beginning of the string to compare
 292  * @not:    tell whether the match will have to be inverted
 293  *
 294  * This passes in a buffer containing a regex and this function will
 295  * set search to point to the search part of the buffer and
 296  * return the type of search it is (see enum above).
 297  * This does modify buff.
 298  *
 299  * Returns enum type.
 300  *  search returns the pointer to use for comparison.
 301  *  not returns 1 if buff started with a '!'
 302  *     0 otherwise.
 303  */
 304 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
 305 {
 306         int type = MATCH_FULL;
 307         int i;
 308
 309         if (buff[0] == '!') {
 310                 *not = 1;
 311                 buff++;
 312                 len--;
 313         } else
 314                 *not = 0;
 315
 316         *search = buff;
 317
 318         for (i = 0; i < len; i++) {
 319                 if (buff[i] == '*') {
 320                         if (!i) {
 321                                 *search = buff + 1;
 322                                 type = MATCH_END_ONLY;
 323                         } else {
 324                                 if (type == MATCH_END_ONLY)
 325                                         type = MATCH_MIDDLE_ONLY;
 326                                 else
 327                                         type = MATCH_FRONT_ONLY;
 328                                 buff[i] = 0;
 329                                 break;
 330                         }
 331                 }
 332         }
 333
 334         return type;
 335 }
 336
 337 static void filter_build_regex(struct filter_pred *pred)
 338 {
 339         struct regex *r = &pred->regex;
 340         char *search;
 341         enum regex_type type = MATCH_FULL;
 342         int not = 0;
 343
 344         if (pred->op == OP_GLOB) {
 345                 type = filter_parse_regex(r->pattern, r->len, &search, &not);
 346                 r->len = strlen(search);
 347                 memmove(r->pattern, search, r->len+1);
 348         }
 349
 350         switch (type) {
 351         case MATCH_FULL:
 352                 r->match = regex_match_full;
 353                 break;
 354         case MATCH_FRONT_ONLY:
 355                 r->match = regex_match_front;
 356                 break;
 357         case MATCH_MIDDLE_ONLY:
 358                 r->match = regex_match_middle;
 359                 break;
 360         case MATCH_END_ONLY:
 361                 r->match = regex_match_end;
 362                 break;
 363         }
 364
 365         pred->not ^= not;
 366 }
 367
 368 /* return 1 if event matches, 0 otherwise (discard) */
 369 int filter_match_preds(struct event_filter *filter, void *rec)
 370 {
 371         int match, top = 0, val1 = 0, val2 = 0;
 372         int stack[MAX_FILTER_PRED];
 373         struct filter_pred *pred;
 374         int i;
 375
 376         for (i = 0; i < filter->n_preds; i++) {
 377                 pred = filter->preds[i];
 378                 if (!pred->pop_n) {
 379                         match = pred->fn(pred, rec, val1, val2);
 380                         stack[top++] = match;
 381                         continue;
 382                 }
 383                 if (pred->pop_n > top) {
 384                         WARN_ON_ONCE(1);
 385                         return 0;
 386                 }
 387                 val1 = stack[--top];
 388                 val2 = stack[--top];
 389                 match = pred->fn(pred, rec, val1, val2);
 390                 stack[top++] = match;
 391         }
 392
 393         return stack[--top];
 394 }
 395 EXPORT_SYMBOL_GPL(filter_match_preds);
 396
 397 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 398 {
 399         ps->lasterr = err;
 400         ps->lasterr_pos = pos;
 401 }
 402
 403 static void remove_filter_string(struct event_filter *filter)
 404 {
 405         kfree(filter->filter_string);
 406         filter->filter_string = NULL;
 407 }
 408
 409 static int replace_filter_string(struct event_filter *filter,
 410                                  char *filter_string)
 411 {
 412         kfree(filter->filter_string);
 413         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 414         if (!filter->filter_string)
 415                 return -ENOMEM;
 416
 417         return 0;
 418 }
 419
 420 static int append_filter_string(struct event_filter *filter,
 421                                 char *string)
 422 {
 423         int newlen;
 424         char *new_filter_string;
 425
 426         BUG_ON(!filter->filter_string);
 427         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 428         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 429         if (!new_filter_string)
 430                 return -ENOMEM;
 431
 432         strcpy(new_filter_string, filter->filter_string);
 433         strcat(new_filter_string, string);
 434         kfree(filter->filter_string);
 435         filter->filter_string = new_filter_string;
 436
 437         return 0;
 438 }
 439
 440 static void append_filter_err(struct filter_parse_state *ps,
 441                               struct event_filter *filter)
 442 {
 443         int pos = ps->lasterr_pos;
 444         char *buf, *pbuf;
 445
 446         buf = (char *)__get_free_page(GFP_TEMPORARY);
 447         if (!buf)
 448                 return;
 449
 450         append_filter_string(filter, "\n");
 451         memset(buf, ' ', PAGE_SIZE);
 452         if (pos > PAGE_SIZE - 128)
 453                 pos = 0;
 454         buf[pos] = '^';
 455         pbuf = &buf[pos] + 1;
 456
 457         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 458         append_filter_string(filter, buf);
 459         free_page((unsigned long) buf);
 460 }
 461
 462 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 463 {
 464         struct event_filter *filter = call->filter;
 465
 466         mutex_lock(&event_mutex);
 467         if (filter && filter->filter_string)
 468                 trace_seq_printf(s, "%s\n", filter->filter_string);
 469         else
 470                 trace_seq_printf(s, "none\n");
 471         mutex_unlock(&event_mutex);
 472 }
 473
 474 void print_subsystem_event_filter(struct event_subsystem *system,
 475                                   struct trace_seq *s)
 476 {
 477         struct event_filter *filter = system->filter;
 478
 479         mutex_lock(&event_mutex);
 480         if (filter && filter->filter_string)
 481                 trace_seq_printf(s, "%s\n", filter->filter_string);
 482         else
 483                 trace_seq_printf(s, "none\n");
 484         mutex_unlock(&event_mutex);
 485 }
 486
 487 static struct ftrace_event_field *
 488 find_event_field(struct ftrace_event_call *call, char *name)
 489 {
 490         struct ftrace_event_field *field;
 491
 492         list_for_each_entry(field, &call->fields, link) {
 493                 if (!strcmp(field->name, name))
 494                         return field;
 495         }
 496
 497         return NULL;
 498 }
 499
 500 static void filter_free_pred(struct filter_pred *pred)
 501 {
 502         if (!pred)
 503                 return;
 504
 505         kfree(pred->field_name);
 506         kfree(pred);
 507 }
 508
 509 static void filter_clear_pred(struct filter_pred *pred)
 510 {
 511         kfree(pred->field_name);
 512         pred->field_name = NULL;
 513         pred->regex.len = 0;
 514 }
 515
 516 static int filter_set_pred(struct filter_pred *dest,
 517                            struct filter_pred *src,
 518                            filter_pred_fn_t fn)
 519 {
 520         *dest = *src;
 521         if (src->field_name) {
 522                 dest->field_name = kstrdup(src->field_name, GFP_KERNEL);
 523                 if (!dest->field_name)
 524                         return -ENOMEM;
 525         }
 526         dest->fn = fn;
 527
 528         return 0;
 529 }
 530
 531 static void filter_disable_preds(struct ftrace_event_call *call)
 532 {
 533         struct event_filter *filter = call->filter;
 534         int i;
 535
 536         call->filter_active = 0;
 537         filter->n_preds = 0;
 538
 539         for (i = 0; i < MAX_FILTER_PRED; i++)
 540                 filter->preds[i]->fn = filter_pred_none;
 541 }
 542
 543 static void __free_preds(struct event_filter *filter)
 544 {
 545         int i;
 546
 547         if (!filter)
 548                 return;
 549
 550         for (i = 0; i < MAX_FILTER_PRED; i++) {
 551                 if (filter->preds[i])
 552                         filter_free_pred(filter->preds[i]);
 553         }
 554         kfree(filter->preds);
 555         kfree(filter->filter_string);
 556         kfree(filter);
 557 }
 558
 559 void destroy_preds(struct ftrace_event_call *call)
 560 {
 561         __free_preds(call->filter);
 562         call->filter = NULL;
 563         call->filter_active = 0;
 564 }
 565
 566 static struct event_filter *__alloc_preds(void)
 567 {
 568         struct event_filter *filter;
 569         struct filter_pred *pred;
 570         int i;
 571
 572         filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 573         if (!filter)
 574                 return ERR_PTR(-ENOMEM);
 575
 576         filter->n_preds = 0;
 577
 578         filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred), GFP_KERNEL);
 579         if (!filter->preds)
 580                 goto oom;
 581
 582         for (i = 0; i < MAX_FILTER_PRED; i++) {
 583                 pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 584                 if (!pred)
 585                         goto oom;
 586                 pred->fn = filter_pred_none;
 587                 filter->preds[i] = pred;
 588         }
 589
 590         return filter;
 591
 592 oom:
 593         __free_preds(filter);
 594         return ERR_PTR(-ENOMEM);
 595 }
 596
 597 static int init_preds(struct ftrace_event_call *call)
 598 {
 599         if (call->filter)
 600                 return 0;
 601
 602         call->filter_active = 0;
 603         call->filter = __alloc_preds();
 604         if (IS_ERR(call->filter))
 605                 return PTR_ERR(call->filter);
 606
 607         return 0;
 608 }
 609
 610 static int init_subsystem_preds(struct event_subsystem *system)
 611 {
 612         struct ftrace_event_call *call;
 613         int err;
 614
 615         list_for_each_entry(call, &ftrace_events, list) {
 616                 if (!call->define_fields)
 617                         continue;
 618
 619                 if (strcmp(call->system, system->name) != 0)
 620                         continue;
 621
 622                 err = init_preds(call);
 623                 if (err)
 624                         return err;
 625         }
 626
 627         return 0;
 628 }
 629
 630 static void filter_free_subsystem_preds(struct event_subsystem *system)
 631 {
 632         struct ftrace_event_call *call;
 633
 634         list_for_each_entry(call, &ftrace_events, list) {
 635                 if (!call->define_fields)
 636                         continue;
 637
 638                 if (strcmp(call->system, system->name) != 0)
 639                         continue;
 640
 641                 filter_disable_preds(call);
 642                 remove_filter_string(call->filter);
 643         }
 644 }
 645
 646 static int filter_add_pred_fn(struct filter_parse_state *ps,
 647                               struct ftrace_event_call *call,
 648                               struct event_filter *filter,
 649                               struct filter_pred *pred,
 650                               filter_pred_fn_t fn)
 651 {
 652         int idx, err;
 653
 654         if (filter->n_preds == MAX_FILTER_PRED) {
 655                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 656                 return -ENOSPC;
 657         }
 658
 659         idx = filter->n_preds;
 660         filter_clear_pred(filter->preds[idx]);
 661         err = filter_set_pred(filter->preds[idx], pred, fn);
 662         if (err)
 663                 return err;
 664
 665         filter->n_preds++;
 666
 667         return 0;
 668 }
 669
 670 int filter_assign_type(const char *type)
 671 {
 672         if (strstr(type, "__data_loc") && strstr(type, "char"))
 673                 return FILTER_DYN_STRING;
 674
 675         if (strchr(type, '[') && strstr(type, "char"))
 676                 return FILTER_STATIC_STRING;
 677
 678         return FILTER_OTHER;
 679 }
 680
 681 static bool is_string_field(struct ftrace_event_field *field)
 682 {
 683         return field->filter_type == FILTER_DYN_STRING ||
 684                field->filter_type == FILTER_STATIC_STRING ||
 685                field->filter_type == FILTER_PTR_STRING;
 686 }
 687
 688 static int is_legal_op(struct ftrace_event_field *field, int op)
 689 {
 690         if (is_string_field(field) &&
 691             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 692                 return 0;
 693         if (!is_string_field(field) && op == OP_GLOB)
 694                 return 0;
 695
 696         return 1;
 697 }
 698
 699 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 700                                              int field_is_signed)
 701 {
 702         filter_pred_fn_t fn = NULL;
 703
 704         switch (field_size) {
 705         case 8:
 706                 if (op == OP_EQ || op == OP_NE)
 707                         fn = filter_pred_64;
 708                 else if (field_is_signed)
 709                         fn = filter_pred_s64;
 710                 else
 711                         fn = filter_pred_u64;
 712                 break;
 713         case 4:
 714                 if (op == OP_EQ || op == OP_NE)
 715                         fn = filter_pred_32;
 716                 else if (field_is_signed)
 717                         fn = filter_pred_s32;
 718                 else
 719                         fn = filter_pred_u32;
 720                 break;
 721         case 2:
 722                 if (op == OP_EQ || op == OP_NE)
 723                         fn = filter_pred_16;
 724                 else if (field_is_signed)
 725                         fn = filter_pred_s16;
 726                 else
 727                         fn = filter_pred_u16;
 728                 break;
 729         case 1:
 730                 if (op == OP_EQ || op == OP_NE)
 731                         fn = filter_pred_8;
 732                 else if (field_is_signed)
 733                         fn = filter_pred_s8;
 734                 else
 735                         fn = filter_pred_u8;
 736                 break;
 737         }
 738
 739         return fn;
 740 }
 741
 742 static int filter_add_pred(struct filter_parse_state *ps,
 743                            struct ftrace_event_call *call,
 744                            struct event_filter *filter,
 745                            struct filter_pred *pred,
 746                            bool dry_run)
 747 {
 748         struct ftrace_event_field *field;
 749         filter_pred_fn_t fn;
 750         unsigned long long val;
 751         int ret;
 752
 753         pred->fn = filter_pred_none;
 754
 755         if (pred->op == OP_AND) {
 756                 pred->pop_n = 2;
 757                 fn = filter_pred_and;
 758                 goto add_pred_fn;
 759         } else if (pred->op == OP_OR) {
 760                 pred->pop_n = 2;
 761                 fn = filter_pred_or;
 762                 goto add_pred_fn;
 763         }
 764
 765         field = find_event_field(call, pred->field_name);
 766         if (!field) {
 767                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 768                 return -EINVAL;
 769         }
 770
 771         pred->offset = field->offset;
 772
 773         if (!is_legal_op(field, pred->op)) {
 774                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 775                 return -EINVAL;
 776         }
 777
 778         if (is_string_field(field)) {
 779                 filter_build_regex(pred);
 780
 781                 if (field->filter_type == FILTER_STATIC_STRING) {
 782                         fn = filter_pred_string;
 783                         pred->regex.field_len = field->size;
 784                 } else if (field->filter_type == FILTER_DYN_STRING)
 785                         fn = filter_pred_strloc;
 786                 else
 787                         fn = filter_pred_pchar;
 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