tracing: Rewrite the function filter code
Steven Rostedt
maintainerv2 cover tracing: Rewrite the function filter code
Al Viro reviewed the ftrace event filter logic and was horrified. He wrote Tom and I a lengthy private email with a formal proof on how to do it simpler as well as more efficient.
Currently the filter logic creates a binary search tree (with some optimizations), and walks it to get a result.
Say we had the following filter: a && !(!b || c) || d && !e Where each letter is a predicate. A tree would be made to look something like:
||
/ \
&& &&
/ | | \
a !|| d !e
/ \
!b cIf a == 1, b == 1, c == 1, d == 1, e == 0, then all nodes would be walked.
|| -> && -> a -> && -> !|| -> !b -> !|| -> c -> !|| -> && -> || -> && -> d -> && -> !e -> && -> || -> return TRUE!
That's 16 steps across vertices.
Al's method would create a program using an array that denotes the predicate function, when to branch, and a target to branch to if the value is the same as when to branch. Storing the array as:
prog[0] = { a, 0, 2}; // predicate, when_to_branch, target prog[1] = { b, 0, 2};
prog[2] = { c, 0, 4};
prog[3] = { d, 0, 5};
prog[4] = { e, 1, 5};
prog[5] = { NULL, 0, 1}; // TRUE
prog[6] = { NULL, 0, 0}; // FALSE
Where the code to execute the above looks like:
for (i = 0; prog[i].pred; i++) {
struct filter_pred *pred = prog[i].pred;
int match = pred->fn(pred, rec);
if (match == prog[i].when_to_branch)
i = prog[i].target;
}
return prog[i].target;Which translates the above program array into:
n0: if (!a) goto n3;
n1: if (!b) goto n3;
n2: if (!c) goto T;
n3: if (!d) goto F;
n4: if (e) goto F;
T: return TRUE;
F: return FALSE;
And the above example only takes 6 steps to return TRUE.
Special thanks goes out to Al for his patience and his time that he spent in educating us in a proper logical parser.
Two patches were added to do some initial clean up. The last patch implements Al's suggestions. I wrote up a very lengthy comment describing what Al taught us in my own words (hopefully I got it right), and the implementation is similar to what Al showed with a few changes (again, hopefully I got that right too). I tested this with lots of different filters and it looks to be holding up.
git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git
ftrace/core
Head SHA1: 80765597bc587feae8dbc8ce97a0f32e12a6e625
Steven Rostedt (VMware) (3):
tracing: Combine enum and arrays into single macro in filter code
tracing: Clean up and document pred_funcs_##type creation and use
tracing: Rewrite filter logic to be simpler and faster
----
kernel/trace/trace.h | 15 +- kernel/trace/trace_events_filter.c | 2337 ++++++++++++++++-------------------- 2 files changed, 1068 insertions(+), 1284 deletions(-)
Changes from v1:
- Fixed echoing nothing into the filter (the tests echoed '0') (I fixed my tests)
- Added better RCU annotations.
(Thanks to zero day bot for pointing this out)
Diff from v1:
kernel/trace/trace.h +1 -1
@@ -1219,7 +1219,7 @@ struct ftrace_event_field {struct prog_entry ;struct event_filter { -struct prog_entry *prog; +struct prog_entry __rcu *prog;char *filter_string; };
kernel/trace/trace_events_filter.c +11 -6
@@ -982,14 +982,16 @@ void print_subsystem_event_filter(struct event_subsystem *system,static void free_prog (struct event_filter *filter) { -struct prog_entry *prog = filter->prog; +struct prog_entry *prog;int i; + prog =rcu_access_pointer (filter->prog);if (!prog)return ;for (i =0 ; prog[i].pred; i++)kfree (prog[i].pred); +kfree (prog); }static void filter_disable (struct trace_event_file *file)
@@ -1497,12 +1499,15 @@ static int process_preds(struct trace_event_call *call,return ret; } - prog =predicate_parse (filter_string, nr_parens, nr_preds, +if (!nr_preds) { + prog =NULL ; + }else { + prog =predicate_parse (filter_string, nr_parens, nr_preds, parse_pred, call, pe); -if (IS_ERR (prog)) -return PTR_ERR (prog); - - filter->prog = prog; +if (IS_ERR (prog)) +return PTR_ERR (prog); + } +rcu_assign_pointer (filter->prog, prog);return 0 ; }
Steven Rostedt
maintainerPATCH v2 1/3 tracing: Combine enum and arrays into single macro in filter code
From: "Steven Rostedt (VMware)" <[email protected]>
Instead of having a separate enum that is the index into another array, like a string array, make a single macro that combines them into a single list, and then the two can not get out of sync. This makes it easier to add and remove items.
The macro trick is:
#define DOGS \
C( JACK, "Jack Russell") \ C( ITALIAN, "Italian Greyhound") \ C( GERMAN, "German Shepherd")
#undef C
#define C(a, b) a
enum { DOGS };
#undef C
#define C(a, b) b
static char dogs[] = { DOGS };
--- kernel/trace/trace_events_filter.c | 112 ++++++++++++++++--------------------- 1 file changed, 48 insertions(+), 64 deletions(-)
kernel/trace/trace_events_filter.c +48 -64
@@ -33,22 +33,26 @@"# Only events with the given fields will be affected.\n" \ "# If no events are modified, an error message will be displayed here" -enum filter_op_ids -{ -OP_OR , -OP_AND , -OP_GLOB , -OP_NE , -OP_EQ , -OP_LT , -OP_LE , -OP_GT , -OP_GE , -OP_BAND , -OP_NOT , -OP_NONE , - OP_OPEN_PAREN, -}; +#define OPS \ + C( OP_OR, "||", 1 ), \ + C( OP_AND, "&&", 2 ), \ + C( OP_GLOB, "~", 4 ), \ + C( OP_NE, "!=", 4 ), \ + C( OP_EQ, "==", 4 ), \ + C( OP_LT, "<", 5 ), \ + C( OP_LE, "<=", 5 ), \ + C( OP_GT, ">", 5 ), \ + C( OP_GE, ">=", 5 ), \ + C( OP_BAND, "&", 6 ), \ + C( OP_NOT, "!", 6 ), \ + C( OP_NONE, "OP_NONE", 0 ), \ + C( OP_OPEN_PAREN, "(", 0 ), \ + C( OP_MAX, NULL, 0 ) + +#undef C +#define C (a, b, c) a + +enum filter_op_ids {OPS };struct filter_op {int id;
@@ -56,56 +60,36 @@ struct filter_op {int precedence; }; -/* Order must be the same as enum filter_op_ids above */ -static struct filter_op filter_ops[] = { - {OP_OR ,"||" ,1 }, - {OP_AND ,"&&" ,2 }, - {OP_GLOB ,"~" ,4 }, - {OP_NE ,"!=" ,4 }, - {OP_EQ ,"==" ,4 }, - {OP_LT ,"<" ,5 }, - {OP_LE ,"<=" ,5 }, - {OP_GT ,">" ,5 }, - {OP_GE ,">=" ,5 }, - {OP_BAND ,"&" ,6 }, - {OP_NOT ,"!" ,6 }, - {OP_NONE ,"OP_NONE" ,0 }, - {OP_OPEN_PAREN ,"(" ,0 }, -}; +#undef C +#define C (a, b, c) { a, b, c } -enum { -FILT_ERR_NONE , -FILT_ERR_INVALID_OP , -FILT_ERR_UNBALANCED_PAREN , -FILT_ERR_TOO_MANY_OPERANDS , -FILT_ERR_OPERAND_TOO_LONG , -FILT_ERR_FIELD_NOT_FOUND , -FILT_ERR_ILLEGAL_FIELD_OP , -FILT_ERR_ILLEGAL_INTVAL , -FILT_ERR_BAD_SUBSYS_FILTER , -FILT_ERR_TOO_MANY_PREDS , -FILT_ERR_MISSING_FIELD , -FILT_ERR_INVALID_FILTER , -FILT_ERR_IP_FIELD_ONLY , -FILT_ERR_ILLEGAL_NOT_OP , -}; +static struct filter_op filter_ops[] = {OPS }; -static char *err_text[] = { -"No error" , -"Invalid operator" , -"Unbalanced parens" , -"Too many operands" , -"Operand too long" , -"Field not found" , -"Illegal operation for field type" , -"Illegal integer value" , -"Couldn't find or set field in one of a subsystem's events" , -"Too many terms in predicate expression" , -"Missing field name and/or value" , -"Meaningless filter expression" , -"Only 'ip' field is supported for function trace" , -"Illegal use of '!'" , -}; +#define ERRORS \ + C( NONE, "No error"), \ + C( INVALID_OP, "Invalid operator"), \ + C( UNBALANCED_PAREN, "Unbalanced parens"), \ + C( TOO_MANY_OPERANDS, "Too many operands"), \ + C( OPERAND_TOO_LONG, "Operand too long"), \ + C( FIELD_NOT_FOUND, "Field not found"), \ + C( ILLEGAL_FIELD_OP, "Illegal operation for field type"), \ + C( ILLEGAL_INTVAL, "Illegal integer value"), \ + C( BAD_SUBSYS_FILTER, "Couldn't find or set field in one of a subsystem's events"), \ + C( TOO_MANY_PREDS, "Too many terms in predicate expression"), \ + C( MISSING_FIELD, "Missing field name and/or value"), \ + C( INVALID_FILTER, "Meaningless filter expression"), \ + C( IP_FIELD_ONLY, "Only 'ip' field is supported for function trace"), \ + C( ILLEGAL_NOT_OP, "Illegal use of '!'"), + +#undef C +#define C (a, b) FILT_ERR_##a + +enum {ERRORS }; + +#undef C +#define C (a, b) b + +static char *err_text[] = {ERRORS };struct opstack_op {enum filter_op_ids op;
Signature · 1 line
2.15.1
Steven Rostedt
maintainerPATCH v2 2/3 tracing: Clean up and document pred_funcs_##type creation and use
In reply to Steven RostedtFrom: "Steven Rostedt (VMware)" <[email protected]>
The pred_funcs_##type arrays consist of five functions that are assigned based on the ops. The array must be in the same order of the ops each function represents. The PRED_FUNC_START macro denotes the op enum that starts the op that maps to the pred_funcs_##type arrays. This is all very subtle and prone to bugs if the code is changed.
Add comments describing how PRED_FUNC_START and pred_funcs_##type array is used, and also a PRED_FUNC_MAX that is the maximum number of functions in the arrays.
Clean up select_comparison_fn() that assigns the predicates to the pred_funcs_##type array function as well as add protection in case an op is passed in that does not map correctly to the array.
--- kernel/trace/trace_events_filter.c | 46 ++++++++++++++++++++++++++------------ 1 file changed, 32 insertions(+), 14 deletions(-)
kernel/trace/trace_events_filter.c +32 -14
@@ -65,6 +65,13 @@ struct filter_op {static struct filter_op filter_ops[] = {OPS }; +/* +* pred functions are OP_LT, OP_LE, OP_GT, OP_GE, and OP_BAND +* pred_funcs_##type below must match the order of them above. +*/ +#define PRED_FUNC_START OP_LT +#define PRED_FUNC_MAX (OP_BAND - PRED_FUNC_START) +#define ERRORS \ C( NONE, "No error"), \ C( INVALID_OP, "Invalid operator"), \
@@ -172,8 +179,6 @@ static const filter_pred_fn_t pred_funcs_##type[] = { \ filter_pred_BAND_##type, \ }; -#define PRED_FUNC_START OP_LT -#define DEFINE_EQUALITY_PRED (size) \ static int filter_pred_##size(struct filter_pred *pred, void *event) \ { \
@@ -946,39 +951,52 @@ static filter_pred_fn_t select_comparison_fn(enum filter_op_ids op, int field_size, int field_is_signed) {filter_pred_fn_t fn =NULL ; +int pred_func_index =-1 ; + +switch (op) { +case OP_EQ : +case OP_NE : +break ; +default : +if (WARN_ON_ONCE (op <PRED_FUNC_START )) +return NULL ; + pred_func_index = op -PRED_FUNC_START ; +if (WARN_ON_ONCE (pred_func_index >PRED_FUNC_MAX )) +return NULL ; + }switch (field_size) {case 8 : -if (op ==OP_EQ || op ==OP_NE ) +if (pred_func_index <0 ) fn = filter_pred_64;else if (field_is_signed) - fn = pred_funcs_s64[op -PRED_FUNC_START ]; + fn = pred_funcs_s64[pred_func_index];else - fn = pred_funcs_u64[op -PRED_FUNC_START ]; + fn = pred_funcs_u64[pred_func_index];break ;case 4 : -if (op ==OP_EQ || op ==OP_NE ) +if (pred_func_index <0 ) fn = filter_pred_32;else if (field_is_signed) - fn = pred_funcs_s32[op -PRED_FUNC_START ]; + fn = pred_funcs_s32[pred_func_index];else - fn = pred_funcs_u32[op -PRED_FUNC_START ]; + fn = pred_funcs_u32[pred_func_index];break ;case 2 : -if (op ==OP_EQ || op ==OP_NE ) +if (pred_func_index <0 ) fn = filter_pred_16;else if (field_is_signed) - fn = pred_funcs_s16[op -PRED_FUNC_START ]; + fn = pred_funcs_s16[pred_func_index];else - fn = pred_funcs_u16[op -PRED_FUNC_START ]; + fn = pred_funcs_u16[pred_func_index];break ;case 1 : -if (op ==OP_EQ || op ==OP_NE ) +if (pred_func_index <0 ) fn = filter_pred_8;else if (field_is_signed) - fn = pred_funcs_s8[op -PRED_FUNC_START ]; + fn = pred_funcs_s8[pred_func_index];else - fn = pred_funcs_u8[op -PRED_FUNC_START ]; + fn = pred_funcs_u8[pred_func_index];break ; }
Signature · 1 line
2.15.1
Steven Rostedt
maintainerPATCH v2 3/3 tracing: Rewrite filter logic to be simpler and faster
In reply to Steven RostedtFrom: "Steven Rostedt (VMware)" <[email protected]>
Al Viro reviewed the filter logic of ftrace trace events and found it to be very troubling. It creates a binary tree based on the logic operators and walks it during tracing. He sent myself and Tom Zanussi a long explanation (and formal proof) of how to do the string parsing better and end up with a program array that can be simply iterated to come up with the correct results.
I took his ideas and his pseudo code and rewrote the filter logic based on them. In doing so, I was able to remove a lot of code, and have a much more condensed filter logic in the process. I wrote a very long comment describing the methadology that Al proposed in my own words. For more info on how this works, read the comment above predicate_parse().
--- kernel/trace/trace.h | 15 +- kernel/trace/trace_events_filter.c | 2311 ++++++++++++++++-------------------- 2 files changed, 1054 insertions(+), 1272 deletions(-)
kernel/trace/trace.h +5 -10
@@ -1216,12 +1216,11 @@ struct ftrace_event_field {int is_signed; }; +struct prog_entry ; +struct event_filter { -int n_preds;/* Number assigned */ -int a_preds;/* allocated */ -struct filter_pred __rcu *preds; -struct filter_pred __rcu *root; -char *filter_string; +struct prog_entry __rcu *prog; +char *filter_string; };struct event_subsystem {
@@ -1413,12 +1412,8 @@ struct filter_pred {unsigned short *ops;struct ftrace_event_field *field;int offset; -int not; +int not;int op; -unsigned short index; -unsigned short parent; -unsigned short left; -unsigned short right; };static inline bool is_string_field (struct ftrace_event_field *field)
kernel/trace/trace_events_filter.c +1049 -1262
2,692 lines not on this page · raw message
Signature · 1 line
2.15.1