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