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