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                 list_del(&elt->list);
1056                 kfree(elt->operand);
1057                 kfree(elt);
1058         }
1059 }
1060
1061 static int filter_parse(struct filter_parse_state *ps)
1062 {
1063         int in_string = 0;
1064         int op, top_op;
1065         char ch;
1066
1067         while ((ch = infix_next(ps))) {
1068                 if (ch == '"') {
1069                         in_string ^= 1;
1070                         continue;
1071                 }
1072
1073                 if (in_string)
1074                         goto parse_operand;
1075
1076                 if (isspace(ch))
1077                         continue;
1078
1079                 if (is_op_char(ps, ch)) {
1080                         op = infix_get_op(ps, ch);
1081                         if (op == OP_NONE) {
1082                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1083                                 return -EINVAL;
1084                         }
1085
1086                         if (strlen(curr_operand(ps))) {
1087                                 postfix_append_operand(ps, curr_operand(ps));
1088                                 clear_operand_string(ps);
1089                         }
1090
1091                         while (!filter_opstack_empty(ps)) {
1092                                 top_op = filter_opstack_top(ps);
1093                                 if (!is_precedence_lower(ps, top_op, op)) {
1094                                         top_op = filter_opstack_pop(ps);
1095                                         postfix_append_op(ps, top_op);
1096                                         continue;
1097                                 }
1098                                 break;
1099                         }
1100
1101                         filter_opstack_push(ps, op);
1102                         continue;
1103                 }
1104
1105                 if (ch == '(') {
1106                         filter_opstack_push(ps, OP_OPEN_PAREN);
1107                         continue;
1108                 }
1109
1110                 if (ch == ')') {
1111                         if (strlen(curr_operand(ps))) {
1112                                 postfix_append_operand(ps, curr_operand(ps));
1113                                 clear_operand_string(ps);
1114                         }
1115
1116                         top_op = filter_opstack_pop(ps);
1117                         while (top_op != OP_NONE) {
1118                                 if (top_op == OP_OPEN_PAREN)
1119                                         break;
1120                                 postfix_append_op(ps, top_op);
1121                                 top_op = filter_opstack_pop(ps);
1122                         }
1123                         if (top_op == OP_NONE) {
1124                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1125                                 return -EINVAL;
1126                         }
1127                         continue;
1128                 }
1129 parse_operand:
1130                 if (append_operand_char(ps, ch)) {
1131                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1132                         return -EINVAL;
1133                 }
1134         }
1135
1136         if (strlen(curr_operand(ps)))
1137                 postfix_append_operand(ps, curr_operand(ps));
1138
1139         while (!filter_opstack_empty(ps)) {
1140                 top_op = filter_opstack_pop(ps);
1141                 if (top_op == OP_NONE)
1142                         break;
1143                 if (top_op == OP_OPEN_PAREN) {
1144                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1145                         return -EINVAL;
1146                 }
1147                 postfix_append_op(ps, top_op);
1148         }
1149
1150         return 0;
1151 }
1152
1153 static struct filter_pred *create_pred(int op, char *operand1, char *operand2)
1154 {
1155         struct filter_pred *pred;
1156
1157         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1158         if (!pred)
1159                 return NULL;
1160
1161         pred->field_name = kstrdup(operand1, GFP_KERNEL);
1162         if (!pred->field_name) {
1163                 kfree(pred);
1164                 return NULL;
1165         }
1166
1167         strcpy(pred->regex.pattern, operand2);
1168         pred->regex.len = strlen(pred->regex.pattern);
1169
1170         pred->op = op;
1171
1172         return pred;
1173 }
1174
1175 static struct filter_pred *create_logical_pred(int op)
1176 {
1177         struct filter_pred *pred;
1178
1179         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1180         if (!pred)
1181                 return NULL;
1182
1183         pred->op = op;
1184
1185         return pred;
1186 }
1187
1188 static int check_preds(struct filter_parse_state *ps)
1189 {
1190         int n_normal_preds = 0, n_logical_preds = 0;
1191         struct postfix_elt *elt;
1192
1193         list_for_each_entry(elt, &ps->postfix, list) {
1194                 if (elt->op == OP_NONE)
1195                         continue;
1196
1197                 if (elt->op == OP_AND || elt->op == OP_OR) {
1198                         n_logical_preds++;
1199                         continue;
1200                 }
1201                 n_normal_preds++;
1202         }
1203
1204         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1205                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1206                 return -EINVAL;
1207         }
1208
1209         return 0;
1210 }
1211
1212 static int replace_preds(struct event_subsystem *system,
1213                          struct ftrace_event_call *call,
1214                          struct filter_parse_state *ps,
1215                          char *filter_string,
1216                          bool dry_run)
1217 {
1218         char *operand1 = NULL, *operand2 = NULL;
1219         struct filter_pred *pred;
1220         struct postfix_elt *elt;
1221         int err;
1222         int n_preds = 0;
1223
1224         err = check_preds(ps);
1225         if (err)
1226                 return err;
1227
1228         list_for_each_entry(elt, &ps->postfix, list) {
1229                 if (elt->op == OP_NONE) {
1230                         if (!operand1)
1231                                 operand1 = elt->operand;
1232                         else if (!operand2)
1233                                 operand2 = elt->operand;
1234                         else {
1235                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1236                                 return -EINVAL;
1237                         }
1238                         continue;
1239                 }
1240
1241                 if (n_preds++ == MAX_FILTER_PRED) {
1242                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1243                         return -ENOSPC;
1244                 }
1245
1246                 if (elt->op == OP_AND || elt->op == OP_OR) {
1247                         pred = create_logical_pred(elt->op);
1248                         goto add_pred;
1249                 }
1250
1251                 if (!operand1 || !operand2) {
1252                         parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1253                         return -EINVAL;
1254                 }
1255
1256                 pred = create_pred(elt->op, operand1, operand2);
1257 add_pred:
1258                 if (!pred)
1259                         return -ENOMEM;
1260                 if (call)
1261                         err = filter_add_pred(ps, call, pred, false);
1262                 else
1263                         err = filter_add_subsystem_pred(ps, system, pred,
1264                                                 filter_string, dry_run);
1265                 filter_free_pred(pred);
1266                 if (err)
1267                         return err;
1268
1269                 operand1 = operand2 = NULL;
1270         }
1271
1272         return 0;
1273 }
1274
1275 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1276 {
1277         int err;
1278
1279         struct filter_parse_state *ps;
1280
1281         mutex_lock(&event_mutex);
1282
1283         err = init_preds(call);
1284         if (err)
1285                 goto out_unlock;
1286
1287         if (!strcmp(strstrip(filter_string), "0")) {
1288                 filter_disable_preds(call);
1289                 remove_filter_string(call->filter);
1290                 mutex_unlock(&event_mutex);
1291                 return 0;
1292         }
1293
1294         err = -ENOMEM;
1295         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1296         if (!ps)
1297                 goto out_unlock;
1298
1299         filter_disable_preds(call);
1300         replace_filter_string(call->filter, filter_string);
1301
1302         parse_init(ps, filter_ops, filter_string);
1303         err = filter_parse(ps);
1304         if (err) {
1305                 append_filter_err(ps, call->filter);
1306                 goto out;
1307         }
1308
1309         err = replace_preds(NULL, call, ps, filter_string, false);
1310         if (err)
1311                 append_filter_err(ps, call->filter);
1312
1313 out:
1314         filter_opstack_clear(ps);
1315         postfix_clear(ps);
1316         kfree(ps);
1317 out_unlock:
1318         mutex_unlock(&event_mutex);
1319
1320         return err;
1321 }
1322
1323 int apply_subsystem_event_filter(struct event_subsystem *system,
1324                                  char *filter_string)
1325 {
1326         int err;
1327
1328         struct filter_parse_state *ps;
1329
1330         mutex_lock(&event_mutex);
1331
1332         err = init_subsystem_preds(system);
1333         if (err)
1334                 goto out_unlock;
1335
1336         if (!strcmp(strstrip(filter_string), "0")) {
1337                 filter_free_subsystem_preds(system, FILTER_DISABLE_ALL);
1338                 remove_filter_string(system->filter);
1339                 mutex_unlock(&event_mutex);
1340                 return 0;
1341         }
1342
1343         err = -ENOMEM;
1344         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1345         if (!ps)
1346                 goto out_unlock;
1347
1348         replace_filter_string(system->filter, filter_string);
1349
1350         parse_init(ps, filter_ops, filter_string);
1351         err = filter_parse(ps);
1352         if (err) {
1353                 append_filter_err(ps, system->filter);
1354                 goto out;
1355         }
1356
1357         filter_free_subsystem_preds(system, FILTER_INIT_NO_RESET);
1358
1359         /* try to see the filter can be applied to which events */
1360         err = replace_preds(system, NULL, ps, filter_string, true);
1361         if (err) {
1362                 append_filter_err(ps, system->filter);
1363                 goto out;
1364         }
1365
1366         filter_free_subsystem_preds(system, FILTER_SKIP_NO_RESET);
1367
1368         /* really apply the filter to the events */
1369         err = replace_preds(system, NULL, ps, filter_string, false);
1370         if (err) {
1371                 append_filter_err(ps, system->filter);
1372                 filter_free_subsystem_preds(system, 2);
1373         }
1374
1375 out:
1376         filter_opstack_clear(ps);
1377         postfix_clear(ps);
1378         kfree(ps);
1379 out_unlock:
1380         mutex_unlock(&event_mutex);
1381
1382         return err;
1383 }
1384