git.oblomov.eu Git - linux-2.6/blob - 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 (strchr(type, '[') && strstr(type, "char"))
 482                 return FILTER_STATIC_STRING;
 483
 484         if (!strcmp(type, "__str_loc"))
 485                 return FILTER_DYN_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
 550         pred->fn = filter_pred_none;
 551
 552         if (pred->op == OP_AND) {
 553                 pred->pop_n = 2;
 554                 return filter_add_pred_fn(ps, call, pred, filter_pred_and);
 555         } else if (pred->op == OP_OR) {
 556                 pred->pop_n = 2;
 557                 return filter_add_pred_fn(ps, call, pred, filter_pred_or);
 558         }
 559
 560         field = find_event_field(call, pred->field_name);
 561         if (!field) {
 562                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 563                 return -EINVAL;
 564         }
 565
 566         pred->offset = field->offset;
 567
 568         if (!is_legal_op(field, pred->op)) {
 569                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 570                 return -EINVAL;
 571         }
 572
 573         string_type = is_string_field(field->type);
 574         if (string_type) {
 575                 if (string_type == FILTER_STATIC_STRING)
 576                         fn = filter_pred_string;
 577                 else
 578                         fn = filter_pred_strloc;
 579                 pred->str_len = field->size;
 580                 if (pred->op == OP_NE)
 581                         pred->not = 1;
 582                 return filter_add_pred_fn(ps, call, pred, fn);
 583         } else {
 584                 if (strict_strtoull(pred->str_val, 0, &val)) {
 585                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 586                         return -EINVAL;
 587                 }
 588                 pred->val = val;
 589         }
 590
 591         fn = select_comparison_fn(pred->op, field->size, field->is_signed);
 592         if (!fn) {
 593                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
 594                 return -EINVAL;
 595         }
 596
 597         if (pred->op == OP_NE)
 598                 pred->not = 1;
 599
 600         return filter_add_pred_fn(ps, call, pred, fn);
 601 }
 602
 603 static int filter_add_subsystem_pred(struct filter_parse_state *ps,
 604                                      struct event_subsystem *system,
 605                                      struct filter_pred *pred,
 606                                      char *filter_string)
 607 {
 608         struct event_filter *filter = system->filter;
 609         struct ftrace_event_call *call;
 610         int err = 0;
 611
 612         if (!filter->preds) {
 613                 filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred),
 614                                         GFP_KERNEL);
 615
 616                 if (!filter->preds)
 617                         return -ENOMEM;
 618         }
 619
 620         if (filter->n_preds == MAX_FILTER_PRED) {
 621                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 622                 return -ENOSPC;
 623         }
 624
 625         filter->preds[filter->n_preds] = pred;
 626         filter->n_preds++;
 627
 628         mutex_lock(&event_mutex);
 629         list_for_each_entry(call, &ftrace_events, list) {
 630
 631                 if (!call->define_fields)
 632                         continue;
 633
 634                 if (strcmp(call->system, system->name))
 635                         continue;
 636
 637                 err = filter_add_pred(ps, call, pred);
 638                 if (err) {
 639                         filter_free_subsystem_preds(system);
 640                         parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
 641                         break;
 642                 }
 643                 replace_filter_string(call->filter, filter_string);
 644         }
 645         mutex_unlock(&event_mutex);
 646
 647         return err;
 648 }
 649
 650 static void parse_init(struct filter_parse_state *ps,
 651                        struct filter_op *ops,
 652                        char *infix_string)
 653 {
 654         memset(ps, '\0', sizeof(*ps));
 655
 656         ps->infix.string = infix_string;
 657         ps->infix.cnt = strlen(infix_string);
 658         ps->ops = ops;
 659
 660         INIT_LIST_HEAD(&ps->opstack);
 661         INIT_LIST_HEAD(&ps->postfix);
 662 }
 663
 664 static char infix_next(struct filter_parse_state *ps)
 665 {
 666         ps->infix.cnt--;
 667
 668         return ps->infix.string[ps->infix.tail++];
 669 }
 670
 671 static char infix_peek(struct filter_parse_state *ps)
 672 {
 673         if (ps->infix.tail == strlen(ps->infix.string))
 674                 return 0;
 675
 676         return ps->infix.string[ps->infix.tail];
 677 }
 678
 679 static void infix_advance(struct filter_parse_state *ps)
 680 {
 681         ps->infix.cnt--;
 682         ps->infix.tail++;
 683 }
 684
 685 static inline int is_precedence_lower(struct filter_parse_state *ps,
 686                                       int a, int b)
 687 {
 688         return ps->ops[a].precedence < ps->ops[b].precedence;
 689 }
 690
 691 static inline int is_op_char(struct filter_parse_state *ps, char c)
 692 {
 693         int i;
 694
 695         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 696                 if (ps->ops[i].string[0] == c)
 697                         return 1;
 698         }
 699
 700         return 0;
 701 }
 702
 703 static int infix_get_op(struct filter_parse_state *ps, char firstc)
 704 {
 705         char nextc = infix_peek(ps);
 706         char opstr[3];
 707         int i;
 708
 709         opstr[0] = firstc;
 710         opstr[1] = nextc;
 711         opstr[2] = '\0';
 712
 713         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 714                 if (!strcmp(opstr, ps->ops[i].string)) {
 715                         infix_advance(ps);
 716                         return ps->ops[i].id;
 717                 }
 718         }
 719
 720         opstr[1] = '\0';
 721
 722         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 723                 if (!strcmp(opstr, ps->ops[i].string))
 724                         return ps->ops[i].id;
 725         }
 726
 727         return OP_NONE;
 728 }
 729
 730 static inline void clear_operand_string(struct filter_parse_state *ps)
 731 {
 732         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
 733         ps->operand.tail = 0;
 734 }
 735
 736 static inline int append_operand_char(struct filter_parse_state *ps, char c)
 737 {
 738         if (ps->operand.tail == MAX_FILTER_STR_VAL)
 739                 return -EINVAL;
 740
 741         ps->operand.string[ps->operand.tail++] = c;
 742
 743         return 0;
 744 }
 745
 746 static int filter_opstack_push(struct filter_parse_state *ps, int op)
 747 {
 748         struct opstack_op *opstack_op;
 749
 750         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
 751         if (!opstack_op)
 752                 return -ENOMEM;
 753
 754         opstack_op->op = op;
 755         list_add(&opstack_op->list, &ps->opstack);
 756
 757         return 0;
 758 }
 759
 760 static int filter_opstack_empty(struct filter_parse_state *ps)
 761 {
 762         return list_empty(&ps->opstack);
 763 }
 764
 765 static int filter_opstack_top(struct filter_parse_state *ps)
 766 {
 767         struct opstack_op *opstack_op;
 768
 769         if (filter_opstack_empty(ps))
 770                 return OP_NONE;
 771
 772         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 773
 774         return opstack_op->op;
 775 }
 776
 777 static int filter_opstack_pop(struct filter_parse_state *ps)
 778 {
 779         struct opstack_op *opstack_op;
 780         int op;
 781
 782         if (filter_opstack_empty(ps))
 783                 return OP_NONE;
 784
 785         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 786         op = opstack_op->op;
 787         list_del(&opstack_op->list);
 788
 789         kfree(opstack_op);
 790
 791         return op;
 792 }
 793
 794 static void filter_opstack_clear(struct filter_parse_state *ps)
 795 {
 796         while (!filter_opstack_empty(ps))
 797                 filter_opstack_pop(ps);
 798 }
 799
 800 static char *curr_operand(struct filter_parse_state *ps)
 801 {
 802         return ps->operand.string;
 803 }
 804
 805 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
 806 {
 807         struct postfix_elt *elt;
 808
 809         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 810         if (!elt)
 811                 return -ENOMEM;
 812
 813         elt->op = OP_NONE;
 814         elt->operand = kstrdup(operand, GFP_KERNEL);
 815         if (!elt->operand) {
 816                 kfree(elt);
 817                 return -ENOMEM;
 818         }
 819
 820         list_add_tail(&elt->list, &ps->postfix);
 821
 822         return 0;
 823 }
 824
 825 static int postfix_append_op(struct filter_parse_state *ps, int op)
 826 {
 827         struct postfix_elt *elt;
 828
 829         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 830         if (!elt)
 831                 return -ENOMEM;
 832
 833         elt->op = op;
 834         elt->operand = NULL;
 835
 836         list_add_tail(&elt->list, &ps->postfix);
 837
 838         return 0;
 839 }
 840
 841 static void postfix_clear(struct filter_parse_state *ps)
 842 {
 843         struct postfix_elt *elt;
 844
 845         while (!list_empty(&ps->postfix)) {
 846                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
 847                 kfree(elt->operand);
 848                 list_del(&elt->list);
 849         }
 850 }
 851
 852 static int filter_parse(struct filter_parse_state *ps)
 853 {
 854         int in_string = 0;
 855         int op, top_op;
 856         char ch;
 857
 858         while ((ch = infix_next(ps))) {
 859                 if (ch == '"') {
 860                         in_string ^= 1;
 861                         continue;
 862                 }
 863
 864                 if (in_string)
 865                         goto parse_operand;
 866
 867                 if (isspace(ch))
 868                         continue;
 869
 870                 if (is_op_char(ps, ch)) {
 871                         op = infix_get_op(ps, ch);
 872                         if (op == OP_NONE) {
 873                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
 874                                 return -EINVAL;
 875                         }
 876
 877                         if (strlen(curr_operand(ps))) {
 878                                 postfix_append_operand(ps, curr_operand(ps));
 879                                 clear_operand_string(ps);
 880                         }
 881
 882                         while (!filter_opstack_empty(ps)) {
 883                                 top_op = filter_opstack_top(ps);
 884                                 if (!is_precedence_lower(ps, top_op, op)) {
 885                                         top_op = filter_opstack_pop(ps);
 886                                         postfix_append_op(ps, top_op);
 887                                         continue;
 888                                 }
 889                                 break;
 890                         }
 891
 892                         filter_opstack_push(ps, op);
 893                         continue;
 894                 }
 895
 896                 if (ch == '(') {
 897                         filter_opstack_push(ps, OP_OPEN_PAREN);
 898                         continue;
 899                 }
 900
 901                 if (ch == ')') {
 902                         if (strlen(curr_operand(ps))) {
 903                                 postfix_append_operand(ps, curr_operand(ps));
 904                                 clear_operand_string(ps);
 905                         }
 906
 907                         top_op = filter_opstack_pop(ps);
 908                         while (top_op != OP_NONE) {
 909                                 if (top_op == OP_OPEN_PAREN)
 910                                         break;
 911                                 postfix_append_op(ps, top_op);
 912                                 top_op = filter_opstack_pop(ps);
 913                         }
 914                         if (top_op == OP_NONE) {
 915                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
 916                                 return -EINVAL;
 917                         }
 918                         continue;
 919                 }
 920 parse_operand:
 921                 if (append_operand_char(ps, ch)) {
 922                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
 923                         return -EINVAL;
 924                 }
 925         }
 926
 927         if (strlen(curr_operand(ps)))
 928                 postfix_append_operand(ps, curr_operand(ps));
 929
 930         while (!filter_opstack_empty(ps)) {
 931                 top_op = filter_opstack_pop(ps);
 932                 if (top_op == OP_NONE)
 933                         break;
 934                 if (top_op == OP_OPEN_PAREN) {
 935                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
 936                         return -EINVAL;
 937                 }
 938                 postfix_append_op(ps, top_op);
 939         }
 940
 941         return 0;
 942 }
 943
 944 static struct filter_pred *create_pred(int op, char *operand1, char *operand2)
 945 {
 946         struct filter_pred *pred;
 947
 948         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 949         if (!pred)
 950                 return NULL;
 951
 952         pred->field_name = kstrdup(operand1, GFP_KERNEL);
 953         if (!pred->field_name) {
 954                 kfree(pred);
 955                 return NULL;
 956         }
 957
 958         strcpy(pred->str_val, operand2);
 959         pred->str_len = strlen(operand2);
 960
 961         pred->op = op;
 962
 963         return pred;
 964 }
 965
 966 static struct filter_pred *create_logical_pred(int op)
 967 {
 968         struct filter_pred *pred;
 969
 970         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 971         if (!pred)
 972                 return NULL;
 973
 974         pred->op = op;
 975
 976         return pred;
 977 }
 978
 979 static int check_preds(struct filter_parse_state *ps)
 980 {
 981         int n_normal_preds = 0, n_logical_preds = 0;
 982         struct postfix_elt *elt;
 983
 984         list_for_each_entry(elt, &ps->postfix, list) {
 985                 if (elt->op == OP_NONE)
 986                         continue;
 987
 988                 if (elt->op == OP_AND || elt->op == OP_OR) {
 989                         n_logical_preds++;
 990                         continue;
 991                 }
 992                 n_normal_preds++;
 993         }
 994
 995         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
 996                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
 997                 return -EINVAL;
 998         }
 999
1000         return 0;
1001 }
1002
1003 static int replace_preds(struct event_subsystem *system,
1004                          struct ftrace_event_call *call,
1005                          struct filter_parse_state *ps,
1006                          char *filter_string)
1007 {
1008         char *operand1 = NULL, *operand2 = NULL;
1009         struct filter_pred *pred;
1010         struct postfix_elt *elt;
1011         int err;
1012
1013         err = check_preds(ps);
1014         if (err)
1015                 return err;
1016
1017         list_for_each_entry(elt, &ps->postfix, list) {
1018                 if (elt->op == OP_NONE) {
1019                         if (!operand1)
1020                                 operand1 = elt->operand;
1021                         else if (!operand2)
1022                                 operand2 = elt->operand;
1023                         else {
1024                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1025                                 return -EINVAL;
1026                         }
1027                         continue;
1028                 }
1029
1030                 if (elt->op == OP_AND || elt->op == OP_OR) {
1031                         pred = create_logical_pred(elt->op);
1032                         if (call) {
1033                                 err = filter_add_pred(ps, call, pred);
1034                                 filter_free_pred(pred);
1035                         } else
1036                                 err = filter_add_subsystem_pred(ps, system,
1037                                                         pred, filter_string);
1038                         if (err)
1039                                 return err;
1040
1041                         operand1 = operand2 = NULL;
1042                         continue;
1043                 }
1044
1045                 if (!operand1 || !operand2) {
1046                         parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1047                         return -EINVAL;
1048                 }
1049
1050                 pred = create_pred(elt->op, operand1, operand2);
1051                 if (call) {
1052                         err = filter_add_pred(ps, call, pred);
1053                         filter_free_pred(pred);
1054                 } else
1055                         err = filter_add_subsystem_pred(ps, system, pred,
1056                                                         filter_string);
1057                 if (err)
1058                         return err;
1059
1060                 operand1 = operand2 = NULL;
1061         }
1062
1063         return 0;
1064 }
1065
1066 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1067 {
1068         int err;
1069
1070         struct filter_parse_state *ps;
1071
1072         mutex_lock(&filter_mutex);
1073
1074         if (!strcmp(strstrip(filter_string), "0")) {
1075                 filter_disable_preds(call);
1076                 remove_filter_string(call->filter);
1077                 mutex_unlock(&filter_mutex);
1078                 return 0;
1079         }
1080
1081         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1082         if (!ps)
1083                 return -ENOMEM;
1084
1085         filter_disable_preds(call);
1086         replace_filter_string(call->filter, filter_string);
1087
1088         parse_init(ps, filter_ops, filter_string);
1089         err = filter_parse(ps);
1090         if (err) {
1091                 append_filter_err(ps, call->filter);
1092                 goto out;
1093         }
1094
1095         err = replace_preds(NULL, call, ps, filter_string);
1096         if (err)
1097                 append_filter_err(ps, call->filter);
1098
1099 out:
1100         filter_opstack_clear(ps);
1101         postfix_clear(ps);
1102         kfree(ps);
1103
1104         mutex_unlock(&filter_mutex);
1105
1106         return err;
1107 }
1108
1109 int apply_subsystem_event_filter(struct event_subsystem *system,
1110                                  char *filter_string)
1111 {
1112         int err;
1113
1114         struct filter_parse_state *ps;
1115
1116         mutex_lock(&filter_mutex);
1117
1118         if (!strcmp(strstrip(filter_string), "0")) {
1119                 filter_free_subsystem_preds(system);
1120                 remove_filter_string(system->filter);
1121                 mutex_unlock(&filter_mutex);
1122                 return 0;
1123         }
1124
1125         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1126         if (!ps)
1127                 return -ENOMEM;
1128
1129         filter_free_subsystem_preds(system);
1130         replace_filter_string(system->filter, filter_string);
1131
1132         parse_init(ps, filter_ops, filter_string);
1133         err = filter_parse(ps);
1134         if (err) {
1135                 append_filter_err(ps, system->filter);
1136                 goto out;
1137         }
1138
1139         err = replace_preds(system, NULL, ps, filter_string);
1140         if (err)
1141                 append_filter_err(ps, system->filter);
1142
1143 out:
1144         filter_opstack_clear(ps);
1145         postfix_clear(ps);
1146         kfree(ps);
1147
1148         mutex_unlock(&filter_mutex);
1149
1150         return err;
1151 }
1152