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