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/module.h>
  22 #include <linux/ctype.h>
  23 #include <linux/mutex.h>
  24
  25 #include "trace.h"
  26 #include "trace_output.h"
  27
  28 enum filter_op_ids
  29 {
  30         OP_OR,
  31         OP_AND,
  32         OP_GLOB,
  33         OP_NE,
  34         OP_EQ,
  35         OP_LT,
  36         OP_LE,
  37         OP_GT,
  38         OP_GE,
  39         OP_NONE,
  40         OP_OPEN_PAREN,
  41 };
  42
  43 struct filter_op {
  44         int id;
  45         char *string;
  46         int precedence;
  47 };
  48
  49 static struct filter_op filter_ops[] = {
  50         { OP_OR,        "||",           1 },
  51         { OP_AND,       "&&",           2 },
  52         { OP_GLOB,      "~",            4 },
  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 = pred->regex.match(addr, &pred->regex, pred->regex.field_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 = pred->regex.match(*addr, &pred->regex, pred->regex.field_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 = pred->regex.match(addr, &pred->regex, 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 /* Basic regex callbacks */
 254 static int regex_match_full(char *str, struct regex *r, int len)
 255 {
 256         if (strncmp(str, r->pattern, len) == 0)
 257                 return 1;
 258         return 0;
 259 }
 260
 261 static int regex_match_front(char *str, struct regex *r, int len)
 262 {
 263         if (strncmp(str, r->pattern, len) == 0)
 264                 return 1;
 265         return 0;
 266 }
 267
 268 static int regex_match_middle(char *str, struct regex *r, int len)
 269 {
 270         if (strstr(str, r->pattern))
 271                 return 1;
 272         return 0;
 273 }
 274
 275 static int regex_match_end(char *str, struct regex *r, int len)
 276 {
 277         char *ptr = strstr(str, r->pattern);
 278
 279         if (ptr && (ptr[r->len] == 0))
 280                 return 1;
 281         return 0;
 282 }
 283
 284 /**
 285  * filter_parse_regex - parse a basic regex
 286  * @buff:   the raw regex
 287  * @len:    length of the regex
 288  * @search: will point to the beginning of the string to compare
 289  * @not:    tell whether the match will have to be inverted
 290  *
 291  * This passes in a buffer containing a regex and this function will
 292  * set search to point to the search part of the buffer and
 293  * return the type of search it is (see enum above).
 294  * This does modify buff.
 295  *
 296  * Returns enum type.
 297  *  search returns the pointer to use for comparison.
 298  *  not returns 1 if buff started with a '!'
 299  *     0 otherwise.
 300  */
 301 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
 302 {
 303         int type = MATCH_FULL;
 304         int i;
 305
 306         if (buff[0] == '!') {
 307                 *not = 1;
 308                 buff++;
 309                 len--;
 310         } else
 311                 *not = 0;
 312
 313         *search = buff;
 314
 315         for (i = 0; i < len; i++) {
 316                 if (buff[i] == '*') {
 317                         if (!i) {
 318                                 *search = buff + 1;
 319                                 type = MATCH_END_ONLY;
 320                         } else {
 321                                 if (type == MATCH_END_ONLY)
 322                                         type = MATCH_MIDDLE_ONLY;
 323                                 else
 324                                         type = MATCH_FRONT_ONLY;
 325                                 buff[i] = 0;
 326                                 break;
 327                         }
 328                 }
 329         }
 330
 331         return type;
 332 }
 333
 334 static void filter_build_regex(struct filter_pred *pred)
 335 {
 336         struct regex *r = &pred->regex;
 337         char *search;
 338         enum regex_type type = MATCH_FULL;
 339         int not = 0;
 340
 341         if (pred->op == OP_GLOB) {
 342                 type = filter_parse_regex(r->pattern, r->len, &search, &not);
 343                 r->len = strlen(search);
 344                 memmove(r->pattern, search, r->len+1);
 345         }
 346
 347         switch (type) {
 348         case MATCH_FULL:
 349                 r->match = regex_match_full;
 350                 break;
 351         case MATCH_FRONT_ONLY:
 352                 r->match = regex_match_front;
 353                 break;
 354         case MATCH_MIDDLE_ONLY:
 355                 r->match = regex_match_middle;
 356                 break;
 357         case MATCH_END_ONLY:
 358                 r->match = regex_match_end;
 359                 break;
 360         }
 361
 362         pred->not ^= not;
 363 }
 364
 365 /* return 1 if event matches, 0 otherwise (discard) */
 366 int filter_match_preds(struct ftrace_event_call *call, void *rec)
 367 {
 368         struct event_filter *filter = call->filter;
 369         int match, top = 0, val1 = 0, val2 = 0;
 370         int stack[MAX_FILTER_PRED];
 371         struct filter_pred *pred;
 372         int i;
 373
 374         for (i = 0; i < filter->n_preds; i++) {
 375                 pred = filter->preds[i];
 376                 if (!pred->pop_n) {
 377                         match = pred->fn(pred, rec, val1, val2);
 378                         stack[top++] = match;
 379                         continue;
 380                 }
 381                 if (pred->pop_n > top) {
 382                         WARN_ON_ONCE(1);
 383                         return 0;
 384                 }
 385                 val1 = stack[--top];
 386                 val2 = stack[--top];
 387                 match = pred->fn(pred, rec, val1, val2);
 388                 stack[top++] = match;
 389         }
 390
 391         return stack[--top];
 392 }
 393 EXPORT_SYMBOL_GPL(filter_match_preds);
 394
 395 static void parse_error(struct filter_parse_state *ps, int err, int pos)
 396 {
 397         ps->lasterr = err;
 398         ps->lasterr_pos = pos;
 399 }
 400
 401 static void remove_filter_string(struct event_filter *filter)
 402 {
 403         kfree(filter->filter_string);
 404         filter->filter_string = NULL;
 405 }
 406
 407 static int replace_filter_string(struct event_filter *filter,
 408                                  char *filter_string)
 409 {
 410         kfree(filter->filter_string);
 411         filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
 412         if (!filter->filter_string)
 413                 return -ENOMEM;
 414
 415         return 0;
 416 }
 417
 418 static int append_filter_string(struct event_filter *filter,
 419                                 char *string)
 420 {
 421         int newlen;
 422         char *new_filter_string;
 423
 424         BUG_ON(!filter->filter_string);
 425         newlen = strlen(filter->filter_string) + strlen(string) + 1;
 426         new_filter_string = kmalloc(newlen, GFP_KERNEL);
 427         if (!new_filter_string)
 428                 return -ENOMEM;
 429
 430         strcpy(new_filter_string, filter->filter_string);
 431         strcat(new_filter_string, string);
 432         kfree(filter->filter_string);
 433         filter->filter_string = new_filter_string;
 434
 435         return 0;
 436 }
 437
 438 static void append_filter_err(struct filter_parse_state *ps,
 439                               struct event_filter *filter)
 440 {
 441         int pos = ps->lasterr_pos;
 442         char *buf, *pbuf;
 443
 444         buf = (char *)__get_free_page(GFP_TEMPORARY);
 445         if (!buf)
 446                 return;
 447
 448         append_filter_string(filter, "\n");
 449         memset(buf, ' ', PAGE_SIZE);
 450         if (pos > PAGE_SIZE - 128)
 451                 pos = 0;
 452         buf[pos] = '^';
 453         pbuf = &buf[pos] + 1;
 454
 455         sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
 456         append_filter_string(filter, buf);
 457         free_page((unsigned long) buf);
 458 }
 459
 460 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
 461 {
 462         struct event_filter *filter = call->filter;
 463
 464         mutex_lock(&event_mutex);
 465         if (filter && filter->filter_string)
 466                 trace_seq_printf(s, "%s\n", filter->filter_string);
 467         else
 468                 trace_seq_printf(s, "none\n");
 469         mutex_unlock(&event_mutex);
 470 }
 471
 472 void print_subsystem_event_filter(struct event_subsystem *system,
 473                                   struct trace_seq *s)
 474 {
 475         struct event_filter *filter = system->filter;
 476
 477         mutex_lock(&event_mutex);
 478         if (filter && filter->filter_string)
 479                 trace_seq_printf(s, "%s\n", filter->filter_string);
 480         else
 481                 trace_seq_printf(s, "none\n");
 482         mutex_unlock(&event_mutex);
 483 }
 484
 485 static struct ftrace_event_field *
 486 find_event_field(struct ftrace_event_call *call, char *name)
 487 {
 488         struct ftrace_event_field *field;
 489
 490         list_for_each_entry(field, &call->fields, link) {
 491                 if (!strcmp(field->name, name))
 492                         return field;
 493         }
 494
 495         return NULL;
 496 }
 497
 498 static void filter_free_pred(struct filter_pred *pred)
 499 {
 500         if (!pred)
 501                 return;
 502
 503         kfree(pred->field_name);
 504         kfree(pred);
 505 }
 506
 507 static void filter_clear_pred(struct filter_pred *pred)
 508 {
 509         kfree(pred->field_name);
 510         pred->field_name = NULL;
 511         pred->regex.len = 0;
 512 }
 513
 514 static int filter_set_pred(struct filter_pred *dest,
 515                            struct filter_pred *src,
 516                            filter_pred_fn_t fn)
 517 {
 518         *dest = *src;
 519         if (src->field_name) {
 520                 dest->field_name = kstrdup(src->field_name, GFP_KERNEL);
 521                 if (!dest->field_name)
 522                         return -ENOMEM;
 523         }
 524         dest->fn = fn;
 525
 526         return 0;
 527 }
 528
 529 static void filter_disable_preds(struct ftrace_event_call *call)
 530 {
 531         struct event_filter *filter = call->filter;
 532         int i;
 533
 534         call->filter_active = 0;
 535         filter->n_preds = 0;
 536
 537         for (i = 0; i < MAX_FILTER_PRED; i++)
 538                 filter->preds[i]->fn = filter_pred_none;
 539 }
 540
 541 void destroy_preds(struct ftrace_event_call *call)
 542 {
 543         struct event_filter *filter = call->filter;
 544         int i;
 545
 546         if (!filter)
 547                 return;
 548
 549         for (i = 0; i < MAX_FILTER_PRED; i++) {
 550                 if (filter->preds[i])
 551                         filter_free_pred(filter->preds[i]);
 552         }
 553         kfree(filter->preds);
 554         kfree(filter->filter_string);
 555         kfree(filter);
 556         call->filter = NULL;
 557 }
 558
 559 static int init_preds(struct ftrace_event_call *call)
 560 {
 561         struct event_filter *filter;
 562         struct filter_pred *pred;
 563         int i;
 564
 565         if (call->filter)
 566                 return 0;
 567
 568         filter = call->filter = kzalloc(sizeof(*filter), GFP_KERNEL);
 569         if (!call->filter)
 570                 return -ENOMEM;
 571
 572         filter->n_preds = 0;
 573
 574         filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred), GFP_KERNEL);
 575         if (!filter->preds)
 576                 goto oom;
 577
 578         for (i = 0; i < MAX_FILTER_PRED; i++) {
 579                 pred = kzalloc(sizeof(*pred), GFP_KERNEL);
 580                 if (!pred)
 581                         goto oom;
 582                 pred->fn = filter_pred_none;
 583                 filter->preds[i] = pred;
 584         }
 585
 586         return 0;
 587
 588 oom:
 589         destroy_preds(call);
 590
 591         return -ENOMEM;
 592 }
 593
 594 static int init_subsystem_preds(struct event_subsystem *system)
 595 {
 596         struct ftrace_event_call *call;
 597         int err;
 598
 599         list_for_each_entry(call, &ftrace_events, list) {
 600                 if (!call->define_fields)
 601                         continue;
 602
 603                 if (strcmp(call->system, system->name) != 0)
 604                         continue;
 605
 606                 err = init_preds(call);
 607                 if (err)
 608                         return err;
 609         }
 610
 611         return 0;
 612 }
 613
 614 static void filter_free_subsystem_preds(struct event_subsystem *system)
 615 {
 616         struct ftrace_event_call *call;
 617
 618         list_for_each_entry(call, &ftrace_events, list) {
 619                 if (!call->define_fields)
 620                         continue;
 621
 622                 if (strcmp(call->system, system->name) != 0)
 623                         continue;
 624
 625                 filter_disable_preds(call);
 626                 remove_filter_string(call->filter);
 627         }
 628 }
 629
 630 static int filter_add_pred_fn(struct filter_parse_state *ps,
 631                               struct ftrace_event_call *call,
 632                               struct filter_pred *pred,
 633                               filter_pred_fn_t fn)
 634 {
 635         struct event_filter *filter = call->filter;
 636         int idx, err;
 637
 638         if (filter->n_preds == MAX_FILTER_PRED) {
 639                 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
 640                 return -ENOSPC;
 641         }
 642
 643         idx = filter->n_preds;
 644         filter_clear_pred(filter->preds[idx]);
 645         err = filter_set_pred(filter->preds[idx], pred, fn);
 646         if (err)
 647                 return err;
 648
 649         filter->n_preds++;
 650         call->filter_active = 1;
 651
 652         return 0;
 653 }
 654
 655 int filter_assign_type(const char *type)
 656 {
 657         if (strstr(type, "__data_loc") && strstr(type, "char"))
 658                 return FILTER_DYN_STRING;
 659
 660         if (strchr(type, '[') && strstr(type, "char"))
 661                 return FILTER_STATIC_STRING;
 662
 663         return FILTER_OTHER;
 664 }
 665
 666 static bool is_string_field(struct ftrace_event_field *field)
 667 {
 668         return field->filter_type == FILTER_DYN_STRING ||
 669                field->filter_type == FILTER_STATIC_STRING ||
 670                field->filter_type == FILTER_PTR_STRING;
 671 }
 672
 673 static int is_legal_op(struct ftrace_event_field *field, int op)
 674 {
 675         if (is_string_field(field) &&
 676             (op != OP_EQ && op != OP_NE && op != OP_GLOB))
 677                 return 0;
 678         if (!is_string_field(field) && op == OP_GLOB)
 679                 return 0;
 680
 681         return 1;
 682 }
 683
 684 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
 685                                              int field_is_signed)
 686 {
 687         filter_pred_fn_t fn = NULL;
 688
 689         switch (field_size) {
 690         case 8:
 691                 if (op == OP_EQ || op == OP_NE)
 692                         fn = filter_pred_64;
 693                 else if (field_is_signed)
 694                         fn = filter_pred_s64;
 695                 else
 696                         fn = filter_pred_u64;
 697                 break;
 698         case 4:
 699                 if (op == OP_EQ || op == OP_NE)
 700                         fn = filter_pred_32;
 701                 else if (field_is_signed)
 702                         fn = filter_pred_s32;
 703                 else
 704                         fn = filter_pred_u32;
 705                 break;
 706         case 2:
 707                 if (op == OP_EQ || op == OP_NE)
 708                         fn = filter_pred_16;
 709                 else if (field_is_signed)
 710                         fn = filter_pred_s16;
 711                 else
 712                         fn = filter_pred_u16;
 713                 break;
 714         case 1:
 715                 if (op == OP_EQ || op == OP_NE)
 716                         fn = filter_pred_8;
 717                 else if (field_is_signed)
 718                         fn = filter_pred_s8;
 719                 else
 720                         fn = filter_pred_u8;
 721                 break;
 722         }
 723
 724         return fn;
 725 }
 726
 727 static int filter_add_pred(struct filter_parse_state *ps,
 728                            struct ftrace_event_call *call,
 729                            struct filter_pred *pred,
 730                            bool dry_run)
 731 {
 732         struct ftrace_event_field *field;
 733         filter_pred_fn_t fn;
 734         unsigned long long val;
 735         int ret;
 736
 737         pred->fn = filter_pred_none;
 738
 739         if (pred->op == OP_AND) {
 740                 pred->pop_n = 2;
 741                 fn = filter_pred_and;
 742                 goto add_pred_fn;
 743         } else if (pred->op == OP_OR) {
 744                 pred->pop_n = 2;
 745                 fn = filter_pred_or;
 746                 goto add_pred_fn;
 747         }
 748
 749         field = find_event_field(call, pred->field_name);
 750         if (!field) {
 751                 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
 752                 return -EINVAL;
 753         }
 754
 755         pred->offset = field->offset;
 756
 757         if (!is_legal_op(field, pred->op)) {
 758                 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
 759                 return -EINVAL;
 760         }
 761
 762         if (is_string_field(field)) {
 763                 filter_build_regex(pred);
 764
 765                 if (field->filter_type == FILTER_STATIC_STRING) {
 766                         fn = filter_pred_string;
 767                         pred->regex.field_len = field->size;
 768                 } else if (field->filter_type == FILTER_DYN_STRING)
 769                         fn = filter_pred_strloc;
 770                 else {
 771                         fn = filter_pred_pchar;
 772                         pred->regex.field_len = strlen(pred->regex.pattern);
 773                 }
 774         } else {
 775                 if (field->is_signed)
 776                         ret = strict_strtoll(pred->regex.pattern, 0, &val);
 777                 else
 778                         ret = strict_strtoull(pred->regex.pattern, 0, &val);
 779                 if (ret) {
 780                         parse_error(ps, FILT_ERR_ILLEGAL_INTVAL, 0);
 781                         return -EINVAL;
 782                 }
 783                 pred->val = val;
 784
 785                 fn = select_comparison_fn(pred->op, field->size,
 786                                           field->is_signed);
 787                 if (!fn) {
 788                         parse_error(ps, FILT_ERR_INVALID_OP, 0);
 789                         return -EINVAL;
 790                 }
 791         }
 792
 793         if (pred->op == OP_NE)
 794                 pred->not = 1;
 795
 796 add_pred_fn:
 797         if (!dry_run)
 798                 return filter_add_pred_fn(ps, call, pred, fn);
 799         return 0;
 800 }
 801
 802 static void parse_init(struct filter_parse_state *ps,
 803                        struct filter_op *ops,
 804                        char *infix_string)
 805 {
 806         memset(ps, '\0', sizeof(*ps));
 807
 808         ps->infix.string = infix_string;
 809         ps->infix.cnt = strlen(infix_string);
 810         ps->ops = ops;
 811
 812         INIT_LIST_HEAD(&ps->opstack);
 813         INIT_LIST_HEAD(&ps->postfix);
 814 }
 815
 816 static char infix_next(struct filter_parse_state *ps)
 817 {
 818         ps->infix.cnt--;
 819
 820         return ps->infix.string[ps->infix.tail++];
 821 }
 822
 823 static char infix_peek(struct filter_parse_state *ps)
 824 {
 825         if (ps->infix.tail == strlen(ps->infix.string))
 826                 return 0;
 827
 828         return ps->infix.string[ps->infix.tail];
 829 }
 830
 831 static void infix_advance(struct filter_parse_state *ps)
 832 {
 833         ps->infix.cnt--;
 834         ps->infix.tail++;
 835 }
 836
 837 static inline int is_precedence_lower(struct filter_parse_state *ps,
 838                                       int a, int b)
 839 {
 840         return ps->ops[a].precedence < ps->ops[b].precedence;
 841 }
 842
 843 static inline int is_op_char(struct filter_parse_state *ps, char c)
 844 {
 845         int i;
 846
 847         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 848                 if (ps->ops[i].string[0] == c)
 849                         return 1;
 850         }
 851
 852         return 0;
 853 }
 854
 855 static int infix_get_op(struct filter_parse_state *ps, char firstc)
 856 {
 857         char nextc = infix_peek(ps);
 858         char opstr[3];
 859         int i;
 860
 861         opstr[0] = firstc;
 862         opstr[1] = nextc;
 863         opstr[2] = '\0';
 864
 865         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 866                 if (!strcmp(opstr, ps->ops[i].string)) {
 867                         infix_advance(ps);
 868                         return ps->ops[i].id;
 869                 }
 870         }
 871
 872         opstr[1] = '\0';
 873
 874         for (i = 0; strcmp(ps->ops[i].string, "OP_NONE"); i++) {
 875                 if (!strcmp(opstr, ps->ops[i].string))
 876                         return ps->ops[i].id;
 877         }
 878
 879         return OP_NONE;
 880 }
 881
 882 static inline void clear_operand_string(struct filter_parse_state *ps)
 883 {
 884         memset(ps->operand.string, '\0', MAX_FILTER_STR_VAL);
 885         ps->operand.tail = 0;
 886 }
 887
 888 static inline int append_operand_char(struct filter_parse_state *ps, char c)
 889 {
 890         if (ps->operand.tail == MAX_FILTER_STR_VAL - 1)
 891                 return -EINVAL;
 892
 893         ps->operand.string[ps->operand.tail++] = c;
 894
 895         return 0;
 896 }
 897
 898 static int filter_opstack_push(struct filter_parse_state *ps, int op)
 899 {
 900         struct opstack_op *opstack_op;
 901
 902         opstack_op = kmalloc(sizeof(*opstack_op), GFP_KERNEL);
 903         if (!opstack_op)
 904                 return -ENOMEM;
 905
 906         opstack_op->op = op;
 907         list_add(&opstack_op->list, &ps->opstack);
 908
 909         return 0;
 910 }
 911
 912 static int filter_opstack_empty(struct filter_parse_state *ps)
 913 {
 914         return list_empty(&ps->opstack);
 915 }
 916
 917 static int filter_opstack_top(struct filter_parse_state *ps)
 918 {
 919         struct opstack_op *opstack_op;
 920
 921         if (filter_opstack_empty(ps))
 922                 return OP_NONE;
 923
 924         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 925
 926         return opstack_op->op;
 927 }
 928
 929 static int filter_opstack_pop(struct filter_parse_state *ps)
 930 {
 931         struct opstack_op *opstack_op;
 932         int op;
 933
 934         if (filter_opstack_empty(ps))
 935                 return OP_NONE;
 936
 937         opstack_op = list_first_entry(&ps->opstack, struct opstack_op, list);
 938         op = opstack_op->op;
 939         list_del(&opstack_op->list);
 940
 941         kfree(opstack_op);
 942
 943         return op;
 944 }
 945
 946 static void filter_opstack_clear(struct filter_parse_state *ps)
 947 {
 948         while (!filter_opstack_empty(ps))
 949                 filter_opstack_pop(ps);
 950 }
 951
 952 static char *curr_operand(struct filter_parse_state *ps)
 953 {
 954         return ps->operand.string;
 955 }
 956
 957 static int postfix_append_operand(struct filter_parse_state *ps, char *operand)
 958 {
 959         struct postfix_elt *elt;
 960
 961         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 962         if (!elt)
 963                 return -ENOMEM;
 964
 965         elt->op = OP_NONE;
 966         elt->operand = kstrdup(operand, GFP_KERNEL);
 967         if (!elt->operand) {
 968                 kfree(elt);
 969                 return -ENOMEM;
 970         }
 971
 972         list_add_tail(&elt->list, &ps->postfix);
 973
 974         return 0;
 975 }
 976
 977 static int postfix_append_op(struct filter_parse_state *ps, int op)
 978 {
 979         struct postfix_elt *elt;
 980
 981         elt = kmalloc(sizeof(*elt), GFP_KERNEL);
 982         if (!elt)
 983                 return -ENOMEM;
 984
 985         elt->op = op;
 986         elt->operand = NULL;
 987
 988         list_add_tail(&elt->list, &ps->postfix);
 989
 990         return 0;
 991 }
 992
 993 static void postfix_clear(struct filter_parse_state *ps)
 994 {
 995         struct postfix_elt *elt;
 996
 997         while (!list_empty(&ps->postfix)) {
 998                 elt = list_first_entry(&ps->postfix, struct postfix_elt, list);
 999                 list_del(&elt->list);
1000                 kfree(elt->operand);
1001                 kfree(elt);
1002         }
1003 }
1004
1005 static int filter_parse(struct filter_parse_state *ps)
1006 {
1007         int in_string = 0;
1008         int op, top_op;
1009         char ch;
1010
1011         while ((ch = infix_next(ps))) {
1012                 if (ch == '"') {
1013                         in_string ^= 1;
1014                         continue;
1015                 }
1016
1017                 if (in_string)
1018                         goto parse_operand;
1019
1020                 if (isspace(ch))
1021                         continue;
1022
1023                 if (is_op_char(ps, ch)) {
1024                         op = infix_get_op(ps, ch);
1025                         if (op == OP_NONE) {
1026                                 parse_error(ps, FILT_ERR_INVALID_OP, 0);
1027                                 return -EINVAL;
1028                         }
1029
1030                         if (strlen(curr_operand(ps))) {
1031                                 postfix_append_operand(ps, curr_operand(ps));
1032                                 clear_operand_string(ps);
1033                         }
1034
1035                         while (!filter_opstack_empty(ps)) {
1036                                 top_op = filter_opstack_top(ps);
1037                                 if (!is_precedence_lower(ps, top_op, op)) {
1038                                         top_op = filter_opstack_pop(ps);
1039                                         postfix_append_op(ps, top_op);
1040                                         continue;
1041                                 }
1042                                 break;
1043                         }
1044
1045                         filter_opstack_push(ps, op);
1046                         continue;
1047                 }
1048
1049                 if (ch == '(') {
1050                         filter_opstack_push(ps, OP_OPEN_PAREN);
1051                         continue;
1052                 }
1053
1054                 if (ch == ')') {
1055                         if (strlen(curr_operand(ps))) {
1056                                 postfix_append_operand(ps, curr_operand(ps));
1057                                 clear_operand_string(ps);
1058                         }
1059
1060                         top_op = filter_opstack_pop(ps);
1061                         while (top_op != OP_NONE) {
1062                                 if (top_op == OP_OPEN_PAREN)
1063                                         break;
1064                                 postfix_append_op(ps, top_op);
1065                                 top_op = filter_opstack_pop(ps);
1066                         }
1067                         if (top_op == OP_NONE) {
1068                                 parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1069                                 return -EINVAL;
1070                         }
1071                         continue;
1072                 }
1073 parse_operand:
1074                 if (append_operand_char(ps, ch)) {
1075                         parse_error(ps, FILT_ERR_OPERAND_TOO_LONG, 0);
1076                         return -EINVAL;
1077                 }
1078         }
1079
1080         if (strlen(curr_operand(ps)))
1081                 postfix_append_operand(ps, curr_operand(ps));
1082
1083         while (!filter_opstack_empty(ps)) {
1084                 top_op = filter_opstack_pop(ps);
1085                 if (top_op == OP_NONE)
1086                         break;
1087                 if (top_op == OP_OPEN_PAREN) {
1088                         parse_error(ps, FILT_ERR_UNBALANCED_PAREN, 0);
1089                         return -EINVAL;
1090                 }
1091                 postfix_append_op(ps, top_op);
1092         }
1093
1094         return 0;
1095 }
1096
1097 static struct filter_pred *create_pred(int op, char *operand1, char *operand2)
1098 {
1099         struct filter_pred *pred;
1100
1101         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1102         if (!pred)
1103                 return NULL;
1104
1105         pred->field_name = kstrdup(operand1, GFP_KERNEL);
1106         if (!pred->field_name) {
1107                 kfree(pred);
1108                 return NULL;
1109         }
1110
1111         strcpy(pred->regex.pattern, operand2);
1112         pred->regex.len = strlen(pred->regex.pattern);
1113
1114         pred->op = op;
1115
1116         return pred;
1117 }
1118
1119 static struct filter_pred *create_logical_pred(int op)
1120 {
1121         struct filter_pred *pred;
1122
1123         pred = kzalloc(sizeof(*pred), GFP_KERNEL);
1124         if (!pred)
1125                 return NULL;
1126
1127         pred->op = op;
1128
1129         return pred;
1130 }
1131
1132 static int check_preds(struct filter_parse_state *ps)
1133 {
1134         int n_normal_preds = 0, n_logical_preds = 0;
1135         struct postfix_elt *elt;
1136
1137         list_for_each_entry(elt, &ps->postfix, list) {
1138                 if (elt->op == OP_NONE)
1139                         continue;
1140
1141                 if (elt->op == OP_AND || elt->op == OP_OR) {
1142                         n_logical_preds++;
1143                         continue;
1144                 }
1145                 n_normal_preds++;
1146         }
1147
1148         if (!n_normal_preds || n_logical_preds >= n_normal_preds) {
1149                 parse_error(ps, FILT_ERR_INVALID_FILTER, 0);
1150                 return -EINVAL;
1151         }
1152
1153         return 0;
1154 }
1155
1156 static int replace_preds(struct ftrace_event_call *call,
1157                          struct filter_parse_state *ps,
1158                          char *filter_string,
1159                          bool dry_run)
1160 {
1161         char *operand1 = NULL, *operand2 = NULL;
1162         struct filter_pred *pred;
1163         struct postfix_elt *elt;
1164         int err;
1165         int n_preds = 0;
1166
1167         err = check_preds(ps);
1168         if (err)
1169                 return err;
1170
1171         list_for_each_entry(elt, &ps->postfix, list) {
1172                 if (elt->op == OP_NONE) {
1173                         if (!operand1)
1174                                 operand1 = elt->operand;
1175                         else if (!operand2)
1176                                 operand2 = elt->operand;
1177                         else {
1178                                 parse_error(ps, FILT_ERR_TOO_MANY_OPERANDS, 0);
1179                                 return -EINVAL;
1180                         }
1181                         continue;
1182                 }
1183
1184                 if (n_preds++ == MAX_FILTER_PRED) {
1185                         parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
1186                         return -ENOSPC;
1187                 }
1188
1189                 if (elt->op == OP_AND || elt->op == OP_OR) {
1190                         pred = create_logical_pred(elt->op);
1191                         goto add_pred;
1192                 }
1193
1194                 if (!operand1 || !operand2) {
1195                         parse_error(ps, FILT_ERR_MISSING_FIELD, 0);
1196                         return -EINVAL;
1197                 }
1198
1199                 pred = create_pred(elt->op, operand1, operand2);
1200 add_pred:
1201                 if (!pred)
1202                         return -ENOMEM;
1203                 err = filter_add_pred(ps, call, pred, dry_run);
1204                 filter_free_pred(pred);
1205                 if (err)
1206                         return err;
1207
1208                 operand1 = operand2 = NULL;
1209         }
1210
1211         return 0;
1212 }
1213
1214 static int replace_system_preds(struct event_subsystem *system,
1215                                 struct filter_parse_state *ps,
1216                                 char *filter_string)
1217 {
1218         struct ftrace_event_call *call;
1219         int err;
1220         bool fail = true;
1221
1222         list_for_each_entry(call, &ftrace_events, list) {
1223
1224                 if (!call->define_fields)
1225                         continue;
1226
1227                 if (strcmp(call->system, system->name) != 0)
1228                         continue;
1229
1230                 /* try to see if the filter can be applied */
1231                 err = replace_preds(call, ps, filter_string, true);
1232                 if (err)
1233                         continue;
1234
1235                 /* really apply the filter */
1236                 filter_disable_preds(call);
1237                 err = replace_preds(call, ps, filter_string, false);
1238                 if (err)
1239                         filter_disable_preds(call);
1240                 else
1241                         replace_filter_string(call->filter, filter_string);
1242                 fail = false;
1243         }
1244
1245         if (fail) {
1246                 parse_error(ps, FILT_ERR_BAD_SUBSYS_FILTER, 0);
1247                 return err;
1248         }
1249         return 0;
1250 }
1251
1252 int apply_event_filter(struct ftrace_event_call *call, char *filter_string)
1253 {
1254         int err;
1255
1256         struct filter_parse_state *ps;
1257
1258         mutex_lock(&event_mutex);
1259
1260         err = init_preds(call);
1261         if (err)
1262                 goto out_unlock;
1263
1264         if (!strcmp(strstrip(filter_string), "0")) {
1265                 filter_disable_preds(call);
1266                 remove_filter_string(call->filter);
1267                 mutex_unlock(&event_mutex);
1268                 return 0;
1269         }
1270
1271         err = -ENOMEM;
1272         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1273         if (!ps)
1274                 goto out_unlock;
1275
1276         filter_disable_preds(call);
1277         replace_filter_string(call->filter, filter_string);
1278
1279         parse_init(ps, filter_ops, filter_string);
1280         err = filter_parse(ps);
1281         if (err) {
1282                 append_filter_err(ps, call->filter);
1283                 goto out;
1284         }
1285
1286         err = replace_preds(call, ps, filter_string, false);
1287         if (err)
1288                 append_filter_err(ps, call->filter);
1289
1290 out:
1291         filter_opstack_clear(ps);
1292         postfix_clear(ps);
1293         kfree(ps);
1294 out_unlock:
1295         mutex_unlock(&event_mutex);
1296
1297         return err;
1298 }
1299
1300 int apply_subsystem_event_filter(struct event_subsystem *system,
1301                                  char *filter_string)
1302 {
1303         int err;
1304
1305         struct filter_parse_state *ps;
1306
1307         mutex_lock(&event_mutex);
1308
1309         err = init_subsystem_preds(system);
1310         if (err)
1311                 goto out_unlock;
1312
1313         if (!strcmp(strstrip(filter_string), "0")) {
1314                 filter_free_subsystem_preds(system);
1315                 remove_filter_string(system->filter);
1316                 mutex_unlock(&event_mutex);
1317                 return 0;
1318         }
1319
1320         err = -ENOMEM;
1321         ps = kzalloc(sizeof(*ps), GFP_KERNEL);
1322         if (!ps)
1323                 goto out_unlock;
1324
1325         replace_filter_string(system->filter, filter_string);
1326
1327         parse_init(ps, filter_ops, filter_string);
1328         err = filter_parse(ps);
1329         if (err) {
1330                 append_filter_err(ps, system->filter);
1331                 goto out;
1332         }
1333
1334         err = replace_system_preds(system, ps, filter_string);
1335         if (err)
1336                 append_filter_err(ps, system->filter);
1337
1338 out:
1339         filter_opstack_clear(ps);
1340         postfix_clear(ps);
1341         kfree(ps);
1342 out_unlock:
1343         mutex_unlock(&event_mutex);
1344
1345         return err;
1346 }
1347