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