Skip to content

Commit 61e9dea

Browse files
Steven Rostedtrostedt
Steven Rostedt
authored and
rostedt
committed
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>
1 parent f76690a commit 61e9dea

File tree

2 files changed

+194
-46
lines changed

2 files changed

+194
-46
lines changed

‎kernel/trace/trace.h

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -664,6 +664,7 @@ struct event_filter {
664664
int n_preds; /* Number assigned */
665665
int a_preds; /* allocated */
666666
struct filter_pred *preds;
667+
struct filter_pred *root;
667668
char *filter_string;
668669
};
669670

@@ -675,6 +676,9 @@ struct event_subsystem {
675676
int nr_events;
676677
};
677678

679+
#define FILTER_PRED_INVALID ((unsigned short)-1)
680+
#define FILTER_PRED_IS_RIGHT (1 << 15)
681+
678682
struct filter_pred;
679683
struct regex;
680684

@@ -704,7 +708,10 @@ struct filter_pred {
704708
int offset;
705709
int not;
706710
int op;
707-
int pop_n;
711+
unsigned short index;
712+
unsigned short parent;
713+
unsigned short left;
714+
unsigned short right;
708715
};
709716

710717
extern struct list_head ftrace_common_fields;

0 commit comments

Comments
 (0)