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