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