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