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