kernel/trace/trace_events_filter.c

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