kernel/trace/trace_events_filter.c

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