?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
USB: ehci-omap.c: introduce missing kfree
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / kernel / trace / trace_events_filter.c
blob50504cb228deded61a141aca151c3d802719b2c2
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
215 cmp = pred->regex.match(*addr, &pred->regex, pred->regex.field_len);
216
217 match = cmp ^ pred->not;
218
219 return match;
220 }
221
222 /*
223 * Filter predicate for dynamic sized arrays of characters.
224 * These are implemented through a list of strings at the end
225 * of the entry.
226 * Also each of these strings have a field in the entry which
227 * contains its offset from the beginning of the entry.
228 * We have then first to get this field, dereference it
229 * and add it to the address of the entry, and at last we have
230 * the address of the string.
231 */
232 static int filter_pred_strloc(struct filter_pred *pred, void *event,
233 int val1, int val2)
234 {
235 u32 str_item = *(u32 *)(event + pred->offset);
236 int str_loc = str_item & 0xffff;
237 int str_len = str_item >> 16;
238 char *addr = (char *)(event + str_loc);
239 int cmp, match;
240
241 cmp = pred->regex.match(addr, &pred->regex, str_len);
242
243 match = cmp ^ pred->not;
244
245 return match;
246 }
247
248 static int filter_pred_none(struct filter_pred *pred, void *event,
249 int val1, int val2)
250 {
251 return 0;
252 }
253
254 /* Basic regex callbacks */
255 static int regex_match_full(char *str, struct regex *r, int len)
256 {
257 if (strncmp(str, r->pattern, len) == 0)
258 return 1;
259 return 0;
260 }
261
262 static int regex_match_front(char *str, struct regex *r, int len)
263 {
264 if (strncmp(str, r->pattern, len) == 0)
265 return 1;
266 return 0;
267 }
268
269 static int regex_match_middle(char *str, struct regex *r, int len)
270 {
271 if (strstr(str, r->pattern))
272 return 1;
273 return 0;
274 }
275
276 static int regex_match_end(char *str, struct regex *r, int len)
277 {
278 char *ptr = strstr(str, r->pattern);
279
280 if (ptr && (ptr[r->len] == 0))
281 return 1;
282 return 0;
283 }
284
285 /**
286 * filter_parse_regex - parse a basic regex
287 * @buff: the raw regex
288 * @len: length of the regex
289 * @search: will point to the beginning of the string to compare
290 * @not: tell whether the match will have to be inverted
291 *
292 * This passes in a buffer containing a regex and this function will
293 * set search to point to the search part of the buffer and
294 * return the type of search it is (see enum above).
295 * This does modify buff.
296 *
297 * Returns enum type.
298 * search returns the pointer to use for comparison.
299 * not returns 1 if buff started with a '!'
300 * 0 otherwise.
301 */
302 enum regex_type filter_parse_regex(char *buff, int len, char **search, int *not)
303 {
304 int type = MATCH_FULL;
305 int i;
306
307 if (buff[0] == '!') {
308 *not = 1;
309 buff++;
310 len--;
311 } else
312 *not = 0;
313
314 *search = buff;
315
316 for (i = 0; i < len; i++) {
317 if (buff[i] == '*') {
318 if (!i) {
319 *search = buff + 1;
320 type = MATCH_END_ONLY;
321 } else {
322 if (type == MATCH_END_ONLY)
323 type = MATCH_MIDDLE_ONLY;
324 else
325 type = MATCH_FRONT_ONLY;
326 buff[i] = 0;
327 break;
328 }
329 }
330 }
331
332 return type;
333 }
334
335 static void filter_build_regex(struct filter_pred *pred)
336 {
337 struct regex *r = &pred->regex;
338 char *search;
339 enum regex_type type = MATCH_FULL;
340 int not = 0;
341
342 if (pred->op == OP_GLOB) {
343 type = filter_parse_regex(r->pattern, r->len, &search, &not);
344 r->len = strlen(search);
345 memmove(r->pattern, search, r->len+1);
346 }
347
348 switch (type) {
349 case MATCH_FULL:
350 r->match = regex_match_full;
351 break;
352 case MATCH_FRONT_ONLY:
353 r->match = regex_match_front;
354 break;
355 case MATCH_MIDDLE_ONLY:
356 r->match = regex_match_middle;
357 break;
358 case MATCH_END_ONLY:
359 r->match = regex_match_end;
360 break;
361 }
362
363 pred->not ^= not;
364 }
365
366 /* return 1 if event matches, 0 otherwise (discard) */
367 int filter_match_preds(struct event_filter *filter, void *rec)
368 {
369 int match, top = 0, val1 = 0, val2 = 0;
370 int stack[MAX_FILTER_PRED];
371 struct filter_pred *pred;
372 int i;
373
374 for (i = 0; i < filter->n_preds; i++) {
375 pred = filter->preds[i];
376 if (!pred->pop_n) {
377 match = pred->fn(pred, rec, val1, val2);
378 stack[top++] = match;
379 continue;
380 }
381 if (pred->pop_n > top) {
382 WARN_ON_ONCE(1);
383 return 0;
384 }
385 val1 = stack[--top];
386 val2 = stack[--top];
387 match = pred->fn(pred, rec, val1, val2);
388 stack[top++] = match;
389 }
390
391 return stack[--top];
392 }
393 EXPORT_SYMBOL_GPL(filter_match_preds);
394
395 static void parse_error(struct filter_parse_state *ps, int err, int pos)
396 {
397 ps->lasterr = err;
398 ps->lasterr_pos = pos;
399 }
400
401 static void remove_filter_string(struct event_filter *filter)
402 {
403 kfree(filter->filter_string);
404 filter->filter_string = NULL;
405 }
406
407 static int replace_filter_string(struct event_filter *filter,
408 char *filter_string)
409 {
410 kfree(filter->filter_string);
411 filter->filter_string = kstrdup(filter_string, GFP_KERNEL);
412 if (!filter->filter_string)
413 return -ENOMEM;
414
415 return 0;
416 }
417
418 static int append_filter_string(struct event_filter *filter,
419 char *string)
420 {
421 int newlen;
422 char *new_filter_string;
423
424 BUG_ON(!filter->filter_string);
425 newlen = strlen(filter->filter_string) + strlen(string) + 1;
426 new_filter_string = kmalloc(newlen, GFP_KERNEL);
427 if (!new_filter_string)
428 return -ENOMEM;
429
430 strcpy(new_filter_string, filter->filter_string);
431 strcat(new_filter_string, string);
432 kfree(filter->filter_string);
433 filter->filter_string = new_filter_string;
434
435 return 0;
436 }
437
438 static void append_filter_err(struct filter_parse_state *ps,
439 struct event_filter *filter)
440 {
441 int pos = ps->lasterr_pos;
442 char *buf, *pbuf;
443
444 buf = (char *)__get_free_page(GFP_TEMPORARY);
445 if (!buf)
446 return;
447
448 append_filter_string(filter, "\n");
449 memset(buf, ' ', PAGE_SIZE);
450 if (pos > PAGE_SIZE - 128)
451 pos = 0;
452 buf[pos] = '^';
453 pbuf = &buf[pos] + 1;
454
455 sprintf(pbuf, "\nparse_error: %s\n", err_text[ps->lasterr]);
456 append_filter_string(filter, buf);
457 free_page((unsigned long) buf);
458 }
459
460 void print_event_filter(struct ftrace_event_call *call, struct trace_seq *s)
461 {
462 struct event_filter *filter = call->filter;
463
464 mutex_lock(&event_mutex);
465 if (filter && filter->filter_string)
466 trace_seq_printf(s, "%s\n", filter->filter_string);
467 else
468 trace_seq_printf(s, "none\n");
469 mutex_unlock(&event_mutex);
470 }
471
472 void print_subsystem_event_filter(struct event_subsystem *system,
473 struct trace_seq *s)
474 {
475 struct event_filter *filter = system->filter;
476
477 mutex_lock(&event_mutex);
478 if (filter && filter->filter_string)
479 trace_seq_printf(s, "%s\n", filter->filter_string);
480 else
481 trace_seq_printf(s, "none\n");
482 mutex_unlock(&event_mutex);
483 }
484
485 static struct ftrace_event_field *
486 find_event_field(struct ftrace_event_call *call, char *name)
487 {
488 struct ftrace_event_field *field;
489
490 list_for_each_entry(field, &call->fields, link) {
491 if (!strcmp(field->name, name))
492 return field;
493 }
494
495 return NULL;
496 }
497
498 static void filter_free_pred(struct filter_pred *pred)
499 {
500 if (!pred)
501 return;
502
503 kfree(pred->field_name);
504 kfree(pred);
505 }
506
507 static void filter_clear_pred(struct filter_pred *pred)
508 {
509 kfree(pred->field_name);
510 pred->field_name = NULL;
511 pred->regex.len = 0;
512 }
513
514 static int filter_set_pred(struct filter_pred *dest,
515 struct filter_pred *src,
516 filter_pred_fn_t fn)
517 {
518 *dest = *src;
519 if (src->field_name) {
520 dest->field_name = kstrdup(src->field_name, GFP_KERNEL);
521 if (!dest->field_name)
522 return -ENOMEM;
523 }
524 dest->fn = fn;
525
526 return 0;
527 }
528
529 static void filter_disable_preds(struct ftrace_event_call *call)
530 {
531 struct event_filter *filter = call->filter;
532 int i;
533
534 call->filter_active = 0;
535 filter->n_preds = 0;
536
537 for (i = 0; i < MAX_FILTER_PRED; i++)
538 filter->preds[i]->fn = filter_pred_none;
539 }
540
541 static void __free_preds(struct event_filter *filter)
542 {
543 int i;
544
545 if (!filter)
546 return;
547
548 for (i = 0; i < MAX_FILTER_PRED; i++) {
549 if (filter->preds[i])
550 filter_free_pred(filter->preds[i]);
551 }
552 kfree(filter->preds);
553 kfree(filter->filter_string);
554 kfree(filter);
555 }
556
557 void destroy_preds(struct ftrace_event_call *call)
558 {
559 __free_preds(call->filter);
560 call->filter = NULL;
561 call->filter_active = 0;
562 }
563
564 static struct event_filter *__alloc_preds(void)
565 {
566 struct event_filter *filter;
567 struct filter_pred *pred;
568 int i;
569
570 filter = kzalloc(sizeof(*filter), GFP_KERNEL);
571 if (!filter)
572 return ERR_PTR(-ENOMEM);
573
574 filter->n_preds = 0;
575
576 filter->preds = kzalloc(MAX_FILTER_PRED * sizeof(pred), GFP_KERNEL);
577 if (!filter->preds)
578 goto oom;
579
580 for (i = 0; i < MAX_FILTER_PRED; i++) {
581 pred = kzalloc(sizeof(*pred), GFP_KERNEL);
582 if (!pred)
583 goto oom;
584 pred->fn = filter_pred_none;
585 filter->preds[i] = pred;
586 }
587
588 return filter;
589
590 oom:
591 __free_preds(filter);
592 return ERR_PTR(-ENOMEM);
593 }
594
595 static int init_preds(struct ftrace_event_call *call)
596 {
597 if (call->filter)
598 return 0;
599
600 call->filter_active = 0;
601 call->filter = __alloc_preds();
602 if (IS_ERR(call->filter))
603 return PTR_ERR(call->filter);
604
605 return 0;
606 }
607
608 static int init_subsystem_preds(struct event_subsystem *system)
609 {
610 struct ftrace_event_call *call;
611 int err;
612
613 list_for_each_entry(call, &ftrace_events, list) {
614 if (!call->define_fields)
615 continue;
616
617 if (strcmp(call->system, system->name) != 0)
618 continue;
619
620 err = init_preds(call);
621 if (err)
622 return err;
623 }
624
625 return 0;
626 }
627
628 static void filter_free_subsystem_preds(struct event_subsystem *system)
629 {
630 struct ftrace_event_call *call;
631
632 list_for_each_entry(call, &ftrace_events, list) {
633 if (!call->define_fields)
634 continue;
635
636 if (strcmp(call->system, system->name) != 0)
637 continue;
638
639 filter_disable_preds(call);
640 remove_filter_string(call->filter);
641 }
642 }
643
644 static int filter_add_pred_fn(struct filter_parse_state *ps,
645 struct ftrace_event_call *call,
646 struct event_filter *filter,
647 struct filter_pred *pred,
648 filter_pred_fn_t fn)
649 {
650 int idx, err;
651
652 if (filter->n_preds == MAX_FILTER_PRED) {
653 parse_error(ps, FILT_ERR_TOO_MANY_PREDS, 0);
654 return -ENOSPC;
655 }
656
657 idx = filter->n_preds;
658 filter_clear_pred(filter->preds[idx]);
659 err = filter_set_pred(filter->preds[idx], pred, fn);
660 if (err)
661 return err;
662
663 filter->n_preds++;
664
665 return 0;
666 }
667
668 int filter_assign_type(const char *type)
669 {
670 if (strstr(type, "__data_loc") && strstr(type, "char"))
671 return FILTER_DYN_STRING;
672
673 if (strchr(type, '[') && strstr(type, "char"))
674 return FILTER_STATIC_STRING;
675
676 return FILTER_OTHER;
677 }
678
679 static bool is_string_field(struct ftrace_event_field *field)
680 {
681 return field->filter_type == FILTER_DYN_STRING ||
682 field->filter_type == FILTER_STATIC_STRING ||
683 field->filter_type == FILTER_PTR_STRING;
684 }
685
686 static int is_legal_op(struct ftrace_event_field *field, int op)
687 {
688 if (is_string_field(field) &&
689 (op != OP_EQ && op != OP_NE && op != OP_GLOB))
690 return 0;
691 if (!is_string_field(field) && op == OP_GLOB)
692 return 0;
693
694 return 1;
695 }
696
697 static filter_pred_fn_t select_comparison_fn(int op, int field_size,
698 int field_is_signed)
699 {
700 filter_pred_fn_t fn = NULL;
701
702 switch (field_size) {
703 case 8:
704 if (op == OP_EQ || op == OP_NE)
705 fn = filter_pred_64;
706 else if (field_is_signed)
707 fn = filter_pred_s64;
708 else
709 fn = filter_pred_u64;
710 break;
711 case 4:
712 if (op == OP_EQ || op == OP_NE)
713 fn = filter_pred_32;
714 else if (field_is_signed)
715 fn = filter_pred_s32;
716 else
717 fn = filter_pred_u32;
718 break;
719 case 2:
720 if (op == OP_EQ || op == OP_NE)
721 fn = filter_pred_16;
722 else if (field_is_signed)
723 fn = filter_pred_s16;
724 else
725 fn = filter_pred_u16;
726 break;
727 case 1:
728 if (op == OP_EQ || op == OP_NE)
729 fn = filter_pred_8;
730 else if (field_is_signed)
731 fn = filter_pred_s8;
732 else
733 fn = filter_pred_u8;
734 break;
735 }
736
737 return fn;
738 }
739
740 static int filter_add_pred(struct filter_parse_state *ps,
741 struct ftrace_event_call *call,
742 struct event_filter *filter,
743 struct filter_pred *pred,
744 bool dry_run)
745 {
746 struct ftrace_event_field *field;
747 filter_pred_fn_t fn;
748 unsigned long long val;
749 int ret;
750
751 pred->fn = filter_pred_none;
752
753 if (pred->op == OP_AND) {
754 pred->pop_n = 2;
755 fn = filter_pred_and;
756 goto add_pred_fn;
757 } else if (pred->op == OP_OR) {
758 pred->pop_n = 2;
759 fn = filter_pred_or;
760 goto add_pred_fn;
761 }
762
763 field = find_event_field(call, pred->field_name);
764 if (!field) {
765 parse_error(ps, FILT_ERR_FIELD_NOT_FOUND, 0);
766 return -EINVAL;
767 }
768
769 pred->offset = field->offset;
770
771 if (!is_legal_op(field, pred->op)) {
772 parse_error(ps, FILT_ERR_ILLEGAL_FIELD_OP, 0);
773 return -EINVAL;
774 }
775
776 if (is_string_field(field)) {
777 filter_build_regex(pred);
778
779 if (field->filter_type == FILTER_STATIC_STRING) {
780 fn = filter_pred_string;
781 pred->regex.field_len = field->size;
782 } else if (field->filter_type == FILTER_DYN_STRING)
783 fn = filter_pred_strloc;
784 else {
785 fn = filter_pred_pchar;
786 pred->regex.field_len = strlen(pred->regex.pattern);
787 }
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
Linux 2.6 ibm-acpi/thinkpad-acpi driver git tree