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