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         int str_loc = *(int *)(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);
 385         call->filter = NULL;
 386 }
 387
 388 int init_preds(struct ftrace_event_call *call)
 389 {
 390         struct event_filter *filter;
 391         struct filter_pred *pred;
 392         int i;
 393
 394         filter = call->filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 395         if (!call->filter)
 396                 return -ENOMEM;
 397
 398         call->filter_active = 0;
 399         filter->n_preds = 0;
 400
 401         filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred), GFP_KERNEL);
 402         if (!filter->preds)
 403                 goto oom;
 404
 405         for (i = 0; i < MAX_FILTER_PRED; i++) {
 406                 pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 407                 if (!pred)
 408                         goto oom;
 409                 pred->fn = filter_pred_none;
 410                 filter->preds[i] = pred;
 411         }
 412
 413         return 0;
 414
 415 oom:
 416         destroy_preds(call);
 417
 418         return -ENOMEM;
 419 }
 420 EXPORT_SYMBOL_GPL(init_preds);
 421
 422 static void filter_free_subsystem_preds(struct event_subsystem *system)
 423 {
 424         struct event_filter *filter = system->filter;
 425         struct ftrace_event_call *call;
 426         int i;
 427
 428         if (filter->n_preds) {
 429                 for (i = 0; i < filter->n_preds; i++)
 430                         filter_free_pred(filter->preds[i]);
 431                 kfree(filter->preds);
 432                 filter->preds = NULL;
 433                 filter->n_preds = 0;
 434         }
 435
 436         mutex_lock(&event_mutex);
 437         list_for_each_entry(call, &ftrace_events, list) {
 438                 if (!call->define_fields)
 439                         continue;
 440
 441                 if (!strcmp(call->system, system->name)) {
 442                         filter_disable_preds(call);
 443                         remove_filter_string(call->filter);
 444                 }
 445         }
 446         mutex_unlock(&event_mutex);
 447 }
 448
 449 static int filter_add_pred_fn(struct filter_parse_state *ps,
 450                               struct ftrace_event_call *call,
 451                               struct filter_pred *pred,
 452                               filter_pred_fn_t fn)
 453 {
 454         struct event_filter *filter = call->filter;
 455         int idx, err;
 456
 457         if (filter->n_preds == MAX_FILTER_PRED) {
 458                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 459                 return -ENOSPC;
 460         }
 461
 462         idx = filter->n_preds;
 463         filter_clear_pred(filter->preds[idx]);
 464         err = filter_set_pred(filter->preds[idx], pred, fn);
 465         if (err)
 466                 return err;
 467
 468         filter->n_preds++;
 469         call->filter_active = 1;
 470
 471         return 0;
 472 }
 473
 474 enum {
 475         FILTER_STATIC_STRING = 1,
 476         FILTER_DYN_STRING
 477 };
 478
 479 static int is_string_field(const char *type)
 480 {
 481         if (strstr(type, "__data_loc") && strstr(type, "char"))
 482                 return FILTER_DYN_STRING;
 483
 484         if (strchr(type, '[') && strstr(type, "char"))
 485                 return FILTER_STATIC_STRING;
 486
 487         return 0;
 488 }
 489
 490 static int is_legal_op(struct ftrace_event_field *field, int op)
 491 {
 492         if (is_string_field(field->type) && (op != OP_EQ && op != OP_NE))
 493                 return 0;
 494
 495         return 1;
 496 }
 497
 498 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 499                                              int field_is_signed)
 500 {
 501         filter_pred_fn_t fn = NULL;
 502
 503         switch (field_size) {
 504         case 8:
 505                 if (op == OP_EQ || op == OP_NE)
 506                         fn = filter_pred_64;
 507                 else if (field_is_signed)
 508                         fn = filter_pred_s64;
 509                 else
 510                         fn = filter_pred_u64;
 511                 break;
 512         case 4:
 513                 if (op == OP_EQ || op == OP_NE)
 514                         fn = filter_pred_32;
 515                 else if (field_is_signed)
 516                         fn = filter_pred_s32;
 517                 else
 518                         fn = filter_pred_u32;
 519                 break;
 520         case 2:
 521                 if (op == OP_EQ || op == OP_NE)
 522                         fn = filter_pred_16;
 523                 else if (field_is_signed)
 524                         fn = filter_pred_s16;
 525                 else
 526                         fn = filter_pred_u16;
 527                 break;
 528         case 1:
 529                 if (op == OP_EQ || op == OP_NE)
 530                         fn = filter_pred_8;
 531                 else if (field_is_signed)
 532                         fn = filter_pred_s8;
 533                 else
 534                         fn = filter_pred_u8;
 535                 break;
 536         }
 537
 538         return fn;
 539 }
 540
 541 static int filter_add_pred(struct filter_parse_state *ps,
 542                            struct ftrace_event_call *call,
 543                            struct filter_pred *pred)
 544 {
 545         struct ftrace_event_field *field;
 546         filter_pred_fn_t fn;
 547         unsigned long long val;
 548         int string_type;
 549         int ret;
 550
 551         pred->fn = filter_pred_none;
 552
 553         if (pred->op == OP_AND) {
 554                 pred->pop_n = 2;
 555                 return filter_add_pred_fn(ps, call, pred, filter_pred_and);
 556         } else if (pred->op == OP_OR) {
 557                 pred->pop_n = 2;
 558                 return filter_add_pred_fn(ps, call, pred, filter_pred_or);
 559         }
 560
 561         field = find_event_field(call, pred->field_name);
 562         if (!field) {
 563                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 564                 return -EINVAL;
 565         }
 566
 567         pred->offset = field->offset;
 568
 569         if (!is_legal_op(field, pred->op)) {
 570                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 571                 return -EINVAL;
 572         }
 573
 574         string_type = is_string_field(field->type);
 575         if (string_type) {
 576                 if (string_type == FILTER_STATIC_STRING)
 577                         fn = filter_pred_string;
 578                 else
 579                         fn = filter_pred_strloc;
 580                 pred->str_len = field->size;
 581                 if (pred->op == OP_NE)
 582                         pred->not = 1;
 583                 return filter_add_pred_fn(ps, call, pred, fn);
 584         } else {
 585                 if (field->is_signed)
 586                         ret = strict_strtoll(pred->str_val, 0, &val);
 587                 else
 588                         ret = strict_strtoull(pred->str_val, 0, &val);
 589                 if (ret) {
 590                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 591                         return -EINVAL;
 592                 }
 593                 pred->val = val;
 594         }
 595
 596         fn = select_comparison_fn(pred->op, field->size, field->is_signed);
 597         if (!fn) {
 598                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
 599                 return -EINVAL;
 600         }
 601
 602         if (pred->op == OP_NE)
 603                 pred->not = 1;
 604
 605         return filter_add_pred_fn(ps, call, pred, fn);
 606 }
 607
 608 static int filter_add_subsystem_pred(struct filter_parse_state *ps,
 609                                      struct event_subsystem *system,
 610                                      struct filter_pred *pred,
 611                                      char *filter_string)
 612 {
 613         struct event_filter *filter = system->filter;
 614         struct ftrace_event_call *call;
 615         int err = 0;
 616
 617         if (!filter->preds) {
 618                 filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred),
 619                                         GFP_KERNEL);
 620
 621                 if (!filter->preds)
 622                         return -ENOMEM;
 623         }
 624
 625         if (filter->n_preds == MAX_FILTER_PRED) {
 626                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 627                 return -ENOSPC;
 628         }
 629
 630         filter->preds[filter->n_preds] = pred;
 631         filter->n_preds++;
 632
 633         mutex_lock(&event_mutex);
 634         list_for_each_entry(call, &ftrace_events, list) {
 635
 636                 if (!call->define_fields)
 637                         continue;
 638
 639                 if (strcmp(call->system, system->name))
 640                         continue;
 641
 642                 err = filter_add_pred(ps, call, pred);
 643                 if (err) {
 644                         mutex_unlock(&event_mutex);
 645                         filter_free_subsystem_preds(system);
 646                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
 647                         goto out;
 648                 }
 649                 replace_filter_string(call->filter, filter_string);
 650         }
 651         mutex_unlock(&event_mutex);
 652 out:
 653         return err;
 654 }
 655
 656 static void parse_init(struct filter_parse_state *ps,
 657                        struct filter_op *ops,
 658                        char *infix_string)
 659 {
 660         memset(ps, '\0', sizeof(*ps));
 661
 662         ps->infix.string = infix_string;
 663         ps->infix.cnt = strlen(infix_string);
 664         ps->ops = ops;
 665
 666         INIT_LIST_HEAD(&ps->opstack);
 667         INIT_LIST_HEAD(&ps->postfix);
 668 }
 669
 670 static char infix_next(struct filter_parse_state *ps)
 671 {
 672         ps->infix.cnt--;
 673
 674         return ps->infix.string[ps->infix.tail++];
 675 }
 676
 677 static char infix_peek(struct filter_parse_state *ps)
 678 {
 679         if (ps->infix.tail == strlen(ps->infix.string))
 680                 return 0;
 681
 682         return ps->infix.string[ps->infix.tail];
 683 }
 684
 685 static void infix_advance(struct filter_parse_state *ps)
 686 {
 687         ps->infix.cnt--;
 688         ps->infix.tail++;
 689 }
 690
 691 static inline int is_precedence_lower(struct filter_parse_state *ps,
 692                                       int a, int b)
 693 {
 694         return ps->ops[a].precedence < ps->ops[b].precedence;
 695 }
 696
 697 static inline int is_op_char(struct filter_parse_state *ps, char c)
 698 {
 699         int i;
 700
 701         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 702                 if (ps->ops[i].string[0] == c)
 703                         return 1;
 704         }
 705
 706         return 0;
 707 }
 708
 709 static int infix_get_op(struct filter_parse_state *ps, char firstc)
 710 {
 711         char nextc = infix_peek(ps);
 712         char opstr[3];
 713         int i;
 714
 715         opstr[0] = firstc;
 716         opstr[1] = nextc;
 717         opstr[2] = '\0';
 718
 719         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 720                 if (!strcmp(opstr, ps->ops[i].string)) {
 721                         infix_advance(ps);
 722                         return ps->ops[i].id;
 723                 }
 724         }
 725
 726         opstr[1] = '\0';
 727
 728         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 729                 if (!strcmp(opstr, ps->ops[i].string))
 730                         return ps->ops[i].id;
 731         }
 732
 733         return OP_NONE;
 734 }
 735
 736 static inline void clear_operand_string(struct filter_parse_state *ps)
 737 {
 738         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
 739         ps->operand.tail = 0;
 740 }
 741
 742 static inline int append_operand_char(struct filter_parse_state *ps, char c)
 743 {
 744         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
 745                 return -EINVAL;
 746
 747         ps->operand.string[ps->operand.tail++] = c;
 748
 749         return 0;
 750 }
 751
 752 static int filter_opstack_push(struct filter_parse_state *ps, int op)
 753 {
 754         struct opstack_op *opstack_op;
 755
 756         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
 757         if (!opstack_op)
 758                 return -ENOMEM;
 759
 760         opstack_op->op = op;
 761         list_add(&opstack_op->list, &ps->opstack);
 762
 763         return 0;
 764 }
 765
 766 static int filter_opstack_empty(struct filter_parse_state *ps)
 767 {
 768         return list_empty(&ps->opstack);
 769 }
 770
 771 static int filter_opstack_top(struct filter_parse_state *ps)
 772 {
 773         struct opstack_op *opstack_op;
 774
 775         if (filter_opstack_empty(ps))
 776                 return OP_NONE;
 777
 778         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 779
 780         return opstack_op->op;
 781 }
 782
 783 static int filter_opstack_pop(struct filter_parse_state *ps)
 784 {
 785         struct opstack_op *opstack_op;
 786         int op;
 787
 788         if (filter_opstack_empty(ps))
 789                 return OP_NONE;
 790
 791         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 792         op = opstack_op->op;
 793         list_del(&opstack_op->list);
 794
 795         kfree(opstack_op);
 796
 797         return op;
 798 }
 799
 800 static void filter_opstack_clear(struct filter_parse_state *ps)
 801 {
 802         while (!filter_opstack_empty(ps))
 803                 filter_opstack_pop(ps);
 804 }
 805
 806 static char *curr_operand(struct filter_parse_state *ps)
 807 {
 808         return ps->operand.string;
 809 }
 810
 811 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
 812 {
 813         struct postfix_elt *elt;
 814
 815         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 816         if (!elt)
 817                 return -ENOMEM;
 818
 819         elt->op = OP_NONE;
 820         elt->operand = kstrdup(operand, GFP_KERNEL);
 821         if (!elt->operand) {
 822                 kfree(elt);
 823                 return -ENOMEM;
 824         }
 825
 826         list_add_tail(&elt->list, &ps->postfix);
 827
 828         return 0;
 829 }
 830
 831 static int postfix_append_op(struct filter_parse_state *ps, int op)
 832 {
 833         struct postfix_elt *elt;
 834
 835         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 836         if (!elt)
 837                 return -ENOMEM;
 838
 839         elt->op = op;
 840         elt->operand = NULL;
 841
 842         list_add_tail(&elt->list, &ps->postfix);
 843
 844         return 0;
 845 }
 846
 847 static void postfix_clear(struct filter_parse_state *ps)
 848 {
 849         struct postfix_elt *elt;
 850
 851         while (!list_empty(&ps->postfix)) {
 852                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
 853                 kfree(elt->operand);
 854                 list_del(&elt->list);
 855         }
 856 }
 857
 858 static int filter_parse(struct filter_parse_state *ps)
 859 {
 860         int in_string = 0;
 861         int op, top_op;
 862         char ch;
 863
 864         while ((ch = infix_next(ps))) {
 865                 if (ch == '"') {
 866                         in_string ^= 1;
 867                         continue;
 868                 }
 869
 870                 if (in_string)
 871                         goto parse_operand;
 872
 873                 if (isspace(ch))
 874                         continue;
 875
 876                 if (is_op_char(ps, ch)) {
 877                         op = infix_get_op(ps, ch);
 878                         if (op == OP_NONE) {
 879                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
 880                                 return -EINVAL;
 881                         }
 882
 883                         if (strlen(curr_operand(ps))) {
 884                                 postfix_append_operand(ps, curr_operand(ps));
 885                                 clear_operand_string(ps);
 886                         }
 887
 888                         while (!filter_opstack_empty(ps)) {
 889                                 top_op = filter_opstack_top(ps);
 890                                 if (!is_precedence_lower(ps, top_op, op)) {
 891                                         top_op = filter_opstack_pop(ps);
 892                                         postfix_append_op(ps, top_op);
 893                                         continue;
 894                                 }
 895                                 break;
 896                         }
 897
 898                         filter_opstack_push(ps, op);
 899                         continue;
 900                 }
 901
 902                 if (ch == '(') {
 903                         filter_opstack_push(ps, OP_OPEN_PAREN);
 904                         continue;
 905                 }
 906
 907                 if (ch == ')') {
 908                         if (strlen(curr_operand(ps))) {
 909                                 postfix_append_operand(ps, curr_operand(ps));
 910                                 clear_operand_string(ps);
 911                         }
 912
 913                         top_op = filter_opstack_pop(ps);
 914                         while (top_op != OP_NONE) {
 915                                 if (top_op == OP_OPEN_PAREN)
 916                                         break;
 917                                 postfix_append_op(ps, top_op);
 918                                 top_op = filter_opstack_pop(ps);
 919                         }
 920                         if (top_op == OP_NONE) {
 921                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
 922                                 return -EINVAL;
 923                         }
 924                         continue;
 925                 }
 926 parse_operand:
 927                 if (append_operand_char(ps, ch)) {
 928                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
 929                         return -EINVAL;
 930                 }
 931         }
 932
 933         if (strlen(curr_operand(ps)))
 934                 postfix_append_operand(ps, curr_operand(ps));
 935
 936         while (!filter_opstack_empty(ps)) {
 937                 top_op = filter_opstack_pop(ps);
 938                 if (top_op == OP_NONE)
 939                         break;
 940                 if (top_op == OP_OPEN_PAREN) {
 941                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
 942                         return -EINVAL;
 943                 }
 944                 postfix_append_op(ps, top_op);
 945         }
 946
 947         return 0;
 948 }
 949
 950 static struct filter_pred *create_pred(int op, char *operand1, char *operand2)
 951 {
 952         struct filter_pred *pred;
 953
 954         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 955         if (!pred)
 956                 return NULL;
 957
 958         pred->field_name = kstrdup(operand1, GFP_KERNEL);
 959         if (!pred->field_name) {
 960                 kfree(pred);
 961                 return NULL;
 962         }
 963
 964         strcpy(pred->str_val, operand2);
 965         pred->str_len = strlen(operand2);
 966
 967         pred->op = op;
 968
 969         return pred;
 970 }
 971
 972 static struct filter_pred *create_logical_pred(int op)
 973 {
 974         struct filter_pred *pred;
 975
 976         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 977         if (!pred)
 978                 return NULL;
 979
 980         pred->op = op;
 981
 982         return pred;
 983 }
 984
 985 static int check_preds(struct filter_parse_state *ps)
 986 {
 987         int n_normal_preds = 0, n_logical_preds = 0;
 988         struct postfix_elt *elt;
 989
 990         list_for_each_entry(elt, &ps->postfix, list) {
 991                 if (elt->op == OP_NONE)
 992                         continue;
 993
 994                 if (elt->op == OP_AND || elt->op == OP_OR) {
 995                         n_logical_preds++;
 996                         continue;
 997                 }
 998                 n_normal_preds++;
 999         }
1000
1001         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1002                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1003                 return -EINVAL;
1004         }
1005
1006         return 0;
1007 }
1008
1009 static int replace_preds(struct event_subsystem *system,
1010                          struct ftrace_event_call *call,
1011                          struct filter_parse_state *ps,
1012                          char *filter_string)
1013 {
1014         char *operand1 = NULL, *operand2 = NULL;
1015         struct filter_pred *pred;
1016         struct postfix_elt *elt;
1017         int err;
1018
1019         err = check_preds(ps);
1020         if (err)
1021                 return err;
1022
1023         list_for_each_entry(elt, &ps->postfix, list) {
1024                 if (elt->op == OP_NONE) {
1025                         if (!operand1)
1026                                 operand1 = elt->operand;
1027                         else if (!operand2)
1028                                 operand2 = elt->operand;
1029                         else {
1030                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1031                                 return -EINVAL;
1032                         }
1033                         continue;
1034                 }
1035
1036                 if (elt->op == OP_AND || elt->op == OP_OR) {
1037                         pred = create_logical_pred(elt->op);
1038                         if (call) {
1039                                 err = filter_add_pred(ps, call, pred);
1040                                 filter_free_pred(pred);
1041                         } else
1042                                 err = filter_add_subsystem_pred(ps, system,
1043                                                         pred, filter_string);
1044                         if (err)
1045                                 return err;
1046
1047                         operand1 = operand2 = NULL;
1048                         continue;
1049                 }
1050
1051                 if (!operand1 || !operand2) {
1052                         parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1053                         return -EINVAL;
1054                 }
1055
1056                 pred = create_pred(elt->op, operand1, operand2);
1057                 if (call) {
1058                         err = filter_add_pred(ps, call, pred);
1059                         filter_free_pred(pred);
1060                 } else
1061                         err = filter_add_subsystem_pred(ps, system, pred,
1062                                                         filter_string);
1063                 if (err)
1064                         return err;
1065
1066                 operand1 = operand2 = NULL;
1067         }
1068
1069         return 0;
1070 }
1071
1072 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1073 {
1074         int err;
1075
1076         struct filter_parse_state *ps;
1077
1078         mutex_lock(&filter_mutex);
1079
1080         if (!strcmp(strstrip(filter_string), "0")) {
1081                 filter_disable_preds(call);
1082                 remove_filter_string(call->filter);
1083                 mutex_unlock(&filter_mutex);
1084                 return 0;
1085         }
1086
1087         err = -ENOMEM;
1088         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1089         if (!ps)
1090                 goto out_unlock;
1091
1092         filter_disable_preds(call);
1093         replace_filter_string(call->filter, filter_string);
1094
1095         parse_init(ps, filter_ops, filter_string);
1096         err = filter_parse(ps);
1097         if (err) {
1098                 append_filter_err(ps, call->filter);
1099                 goto out;
1100         }
1101
1102         err = replace_preds(NULL, call, ps, filter_string);
1103         if (err)
1104                 append_filter_err(ps, call->filter);
1105
1106 out:
1107         filter_opstack_clear(ps);
1108         postfix_clear(ps);
1109         kfree(ps);
1110 out_unlock:
1111         mutex_unlock(&filter_mutex);
1112
1113         return err;
1114 }
1115
1116 int apply_subsystem_event_filter(struct event_subsystem *system,
1117                                  char *filter_string)
1118 {
1119         int err;
1120
1121         struct filter_parse_state *ps;
1122
1123         mutex_lock(&filter_mutex);
1124
1125         if (!strcmp(strstrip(filter_string), "0")) {
1126                 filter_free_subsystem_preds(system);
1127                 remove_filter_string(system->filter);
1128                 mutex_unlock(&filter_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_free_subsystem_preds(system);
1138         replace_filter_string(system->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, system->filter);
1144                 goto out;
1145         }
1146
1147         err = replace_preds(system, NULL, ps, filter_string);
1148         if (err)
1149                 append_filter_err(ps, system->filter);
1150
1151 out:
1152         filter_opstack_clear(ps);
1153         postfix_clear(ps);
1154         kfree(ps);
1155 out_unlock:
1156         mutex_unlock(&filter_mutex);
1157
1158         return err;
1159 }
1160