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