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