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