aboutsummaryrefslogtreecommitdiffstats
path: root/kernel/trace/trace.h
diff options
context:
space:
mode:
authorSteven Rostedt <srostedt@redhat.com>2011-01-27 22:54:33 -0500
committerSteven Rostedt <rostedt@goodmis.org>2011-02-07 20:56:19 -0500
commit61e9dea20e1ada886cc49a9ec6fe3c6ac0de7324 (patch)
tree8f12ee74970d57550806a6f3e905cfca8d67601a /kernel/trace/trace.h
parentf76690afd05e3e163149310bdcd30234f93b3a7a (diff)
tracing/filter: Use a tree instead of stack for filter_match_preds()
Currently the filter_match_preds() requires a stack to push and pop the preds to determine if the filter matches the record or not. This has two drawbacks: 1) It requires a stack to store state information. As this is done in fast paths we can't allocate the storage for this stack, and we can't use a global as it must be re-entrant. The stack is stored on the kernel stack and this greatly limits how many preds we may allow. 2) All conditions are calculated even when a short circuit exists. a || b will always calculate a and b even though a was determined to be true. Using a tree we can walk a constant structure that will save the state as we go. The algorithm is simply: pred = root; do { switch (move) { case MOVE_DOWN: if (OR or AND) { pred = left; continue; } if (pred == root) break; match = pred->fn(); pred = pred->parent; move = left child ? MOVE_UP_FROM_LEFT : MOVE_UP_FROM_RIGHT; continue; case MOVE_UP_FROM_LEFT: /* Only OR or AND can be a parent */ if (match && OR || !match && AND) { /* short circuit */ if (pred == root) break; pred = pred->parent; move = left child ? MOVE_UP_FROM_LEFT : MOVE_UP_FROM_RIGHT; continue; } pred = pred->right; move = MOVE_DOWN; continue; case MOVE_UP_FROM_RIGHT: if (pred == root) break; pred = pred->parent; move = left child ? MOVE_UP_FROM_LEFT : MOVE_UP_FROM_RIGHT; continue; } done = 1; } while (!done); This way there's no strict limit to how many preds we allow and it also will short circuit the logical operations when possible. Cc: Tom Zanussi <tzanussi@gmail.com> Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
Diffstat (limited to 'kernel/trace/trace.h')
-rw-r--r--kernel/trace/trace.h9
1 files changed, 8 insertions, 1 deletions
diff --git a/kernel/trace/trace.h b/kernel/trace/trace.h
index 254d04a84ec3..bba34a72c780 100644
--- a/kernel/trace/trace.h
+++ b/kernel/trace/trace.h
@@ -664,6 +664,7 @@ struct event_filter {
664 int n_preds; /* Number assigned */ 664 int n_preds; /* Number assigned */
665 int a_preds; /* allocated */ 665 int a_preds; /* allocated */
666 struct filter_pred *preds; 666 struct filter_pred *preds;
667 struct filter_pred *root;
667 char *filter_string; 668 char *filter_string;
668}; 669};
669 670
@@ -675,6 +676,9 @@ struct event_subsystem {
675 int nr_events; 676 int nr_events;
676}; 677};
677 678
679#define FILTER_PRED_INVALID ((unsigned short)-1)
680#define FILTER_PRED_IS_RIGHT (1 << 15)
681
678struct filter_pred; 682struct filter_pred;
679struct regex; 683struct regex;
680 684
@@ -704,7 +708,10 @@ struct filter_pred {
704 int offset; 708 int offset;
705 int not; 709 int not;
706 int op; 710 int op;
707 int pop_n; 711 unsigned short index;
712 unsigned short parent;
713 unsigned short left;
714 unsigned short right;
708}; 715};
709 716
710extern struct list_head ftrace_common_fields; 717extern struct list_head ftrace_common_fields;