1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2003-2005 Michel Dagenais
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License Version 2 as
6 * published by the Free Software Foundation;
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20 consist in AND, OR and NOT nested expressions, forming a tree with
21 simple relations as leaves. The simple relations test is a field
22 in an event is equal, not equal, smaller, smaller or equal, larger, or
23 larger or equal to a specified value.
28 * - the exists an other lttv_filter which conflicts with this one
33 * - refine switch of expression in multiple uses functions
34 * - add the current simple expression to the tree
37 #include <lttv/filter.h>
44 simple expr [ op expr ]
46 read_simple_expression
47 read_field_path [ rel value ]
50 read_field_component [. field path]
59 path(component...) -> field
65 LTTV_FILTER_TRACEFILE
,
78 LTTV_FILTER_EX_SUBMODE
,
83 * Assign a new tree for the current expression
85 * @return pointer of lttv_filter_tree
87 lttv_filter_tree
* lttv_filter_tree_new() {
88 lttv_filter_tree
* tree
;
90 tree
= g_new(lttv_filter_tree
,1);
91 tree
->node
= g_new(lttv_expression
,1);
92 tree
->node
->type
= LTTV_UNDEFINED_EXPRESSION
;
93 tree
->left
= LTTV_TREE_UNDEFINED
;
94 tree
->right
= LTTV_TREE_UNDEFINED
;
100 * Destroys the tree and his sub-trees
101 * @param tree Tree which must be destroyed
103 void lttv_filter_tree_destroy(lttv_filter_tree
* tree
) {
105 if(tree
->left
== LTTV_TREE_LEAF
) g_free(tree
->l_child
.leaf
);
106 else if(tree
->left
== LTTV_TREE_NODE
) lttv_filter_tree_destroy(tree
->l_child
.t
);
108 if(tree
->right
== LTTV_TREE_LEAF
) g_free(tree
->r_child
.leaf
);
109 else if(tree
->right
== LTTV_TREE_NODE
) lttv_filter_tree_destroy(tree
->r_child
.t
);
116 * Parse through filtering field hierarchy as specified
117 * by user. This function compares each value to
118 * predetermined quarks
119 * @param fp The field path list
120 * @return success/failure of operation
123 parse_field_path(GPtrArray
* fp
) {
126 g_assert(f
=g_ptr_array_index(fp
,0)); //list_first(fp)->data;
128 if(g_quark_try_string(f
->str
) == LTTV_FILTER_EVENT
) {
129 // parse_subfield(fp, LTTV_FILTER_EVENT);
131 } else if(g_quark_try_string(f
->str
) == LTTV_FILTER_TRACEFILE
) {
133 } else if(g_quark_try_string(f
->str
) == LTTV_FILTER_TRACE
) {
135 } else if(g_quark_try_string(f
->str
) == LTTV_FILTER_STATE
) {
138 g_warning("Unrecognized field in filter string");
145 * Add an filtering option to the current tree
146 * @param expression Current expression to parse
147 * @return success/failure of operation
150 parse_simple_expression(GString
* expression
) {
160 * Creates a new lttv_filter
161 * @param expression filtering options string
162 * @param t pointer to the current LttvTrace
163 * @return the current lttv_filter or NULL if error
166 lttv_filter_new(char *expression
, LttvTraceState
*tcs
) {
168 g_print("filter::lttv_filter_new()\n"); /* debug */
172 p_nesting
=0, /* parenthesis nesting value */
173 b
=0; /* current breakpoint in expression string */
177 *tree
= lttv_filter_tree_new(), /* main tree */
178 *subtree
= NULL
, /* buffer for subtrees */
184 * each element of the list
185 * is a sub tree created
186 * by the use of parenthesis in the
187 * global expression. The final tree
188 * will be the one left at the root of
191 GPtrArray
*tree_stack
= g_ptr_array_new();
192 g_ptr_array_add( tree_stack
,(gpointer
) tree
);
194 /* temporary values */
195 GString
*a_field_component
= g_string_new("");
196 GPtrArray
*a_field_path
= NULL
;
198 lttv_simple_expression a_simple_expression
;
201 * Parse entire expression and construct
202 * the binary tree. There are two steps
203 * in browsing that string
204 * 1. finding boolean ops " &,|,^,! " and parenthesis " {,(,[,],),} "
205 * 2. finding simple expressions
206 * - field path ( separated by dots )
207 * - op ( >, <, =, >=, <=, !=)
208 * - value ( integer, string ... )
209 * To spare computing time, the whole
210 * string is parsed in this loop for a
211 * O(n) complexity order.
213 * When encountering logical op &,|,^
214 * 1. parse the last value if any
215 * 2. create a new tree
216 * 3. add the expression (simple exp, or exp (subtree)) to the tree
217 * 4. concatenate this tree with the current tree on top of the stack
218 * When encountering math ops >,>=,<,<=,=,!=
219 * 1. add to op to the simple expression
220 * 2. concatenate last field component to field path
221 * When encountering concatening ops .
222 * 1. concatenate last field component to field path
223 * When encountering opening parenthesis (,{,[
224 * 1. create a new subtree on top of tree stack
225 * When encountering closing parenthesis ),},]
226 * 1. add the expression on right child of the current tree
227 * 2. the subtree is completed, allocate a new subtree
228 * 3. pop the tree value from the tree stack
231 a_field_path
= g_ptr_array_new();
232 g_ptr_array_set_size(a_field_path
,2); /* by default, recording 2 field expressions */
235 for(i
=0;i
<strlen(expression
);i
++) {
236 // g_print("%s\n",a_field_component->str);
237 g_print("%c ",expression
[i
]);
238 // g_print("switch:%c -->subtree:%p\n",expression[i],subtree);
239 switch(expression
[i
]) {
244 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
245 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
246 t2
= lttv_filter_tree_new();
247 t2
->node
->type
= LTTV_EXPRESSION_OP
;
248 t2
->node
->e
.op
= LTTV_LOGICAL_AND
;
249 if(subtree
!= NULL
) {
250 t2
->left
= LTTV_TREE_NODE
;
251 t2
->l_child
.t
= subtree
;
253 t1
->right
= LTTV_TREE_NODE
;
256 a_simple_expression
.value
= a_field_component
->str
;
257 a_field_component
= g_string_new("");
258 t2
->left
= LTTV_TREE_LEAF
;
259 t2
->l_child
.leaf
= g_new(lttv_simple_expression
,1);
260 t1
->right
= LTTV_TREE_NODE
;
266 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
267 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
268 t2
= lttv_filter_tree_new();
269 t2
->node
->type
= LTTV_EXPRESSION_OP
;
270 t2
->node
->e
.op
= LTTV_LOGICAL_OR
;
271 if(subtree
!= NULL
) {
272 t2
->left
= LTTV_TREE_NODE
;
273 t2
->l_child
.t
= subtree
;
275 t1
->right
= LTTV_TREE_NODE
;
278 a_simple_expression
.value
= a_field_component
->str
;
279 a_field_component
= g_string_new("");
280 t2
->left
= LTTV_TREE_LEAF
;
281 t2
->l_child
.leaf
= g_new(lttv_simple_expression
,1);
282 t1
->right
= LTTV_TREE_NODE
;
287 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
288 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
289 t2
= lttv_filter_tree_new();
290 t2
->node
->type
= LTTV_EXPRESSION_OP
;
291 t2
->node
->e
.op
= LTTV_LOGICAL_XOR
;
292 if(subtree
!= NULL
) {
293 t2
->left
= LTTV_TREE_NODE
;
294 t2
->l_child
.t
= subtree
;
296 t1
->right
= LTTV_TREE_NODE
;
299 a_simple_expression
.value
= a_field_component
->str
;
300 a_field_component
= g_string_new("");
301 t2
->left
= LTTV_TREE_LEAF
;
302 t2
->l_child
.leaf
= g_new(lttv_simple_expression
,1);
303 t1
->right
= LTTV_TREE_NODE
;
307 case '!': /* not, or not equal (math op) */
308 if(expression
[i
+1] == '=') { /* != */
309 a_simple_expression
.op
= LTTV_FIELD_NE
;
312 // g_print("%s\n",a_field_component);
313 // a_field_component = g_string_new("");
314 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
315 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
316 t2
= lttv_filter_tree_new();
317 t2
->node
->type
= LTTV_EXPRESSION_OP
;
318 t2
->node
->e
.op
= LTTV_LOGICAL_NOT
;
319 t1
->right
= LTTV_TREE_NODE
;
323 case '(': /* start of parenthesis */
326 p_nesting
++; /* incrementing parenthesis nesting value */
327 t1
= lttv_filter_tree_new();
328 g_ptr_array_add( tree_stack
,(gpointer
) t1
);
330 case ')': /* end of parenthesis */
333 p_nesting
--; /* decrementing parenthesis nesting value */
334 if(p_nesting
<0 || tree_stack
->len
<2) {
335 g_warning("Wrong filtering options, the string\n\"%s\"\n\
336 is not valid due to parenthesis incorrect use",expression
);
340 g_assert(tree_stack
->len
>0);
341 if(subtree
!= NULL
) {
342 t1
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
343 while(t1
->right
!= LTTV_TREE_UNDEFINED
&& t1
->right
!= LTTV_TREE_LEAF
) {
344 g_assert(t1
!=NULL
&& t1
->r_child
.t
!= NULL
);
347 t1
->right
= LTTV_TREE_NODE
;
348 t1
->r_child
.t
= subtree
;
349 subtree
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
350 g_ptr_array_remove_index(tree_stack
,tree_stack
->len
-1);
352 a_simple_expression
.value
= a_field_component
->str
;
353 a_field_component
= g_string_new("");
354 t1
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
355 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
356 t1
->right
= LTTV_TREE_LEAF
;
357 t1
->r_child
.leaf
= g_new(lttv_simple_expression
,1);
358 subtree
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
359 g_assert(subtree
!= NULL
);
360 g_ptr_array_remove_index(tree_stack
,tree_stack
->len
-1);
365 * mathematic operators
367 case '<': /* lower, lower or equal */
368 if(expression
[i
+1] == '=') { /* <= */
370 a_simple_expression
.op
= LTTV_FIELD_LE
;
371 } else a_simple_expression
.op
= LTTV_FIELD_LT
;
372 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
373 a_field_component
= g_string_new("");
375 case '>': /* higher, higher or equal */
376 if(expression
[i
+1] == '=') { /* >= */
378 a_simple_expression
.op
= LTTV_FIELD_GE
;
379 } else a_simple_expression
.op
= LTTV_FIELD_GT
;
380 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
381 a_field_component
= g_string_new("");
383 case '=': /* equal */
384 a_simple_expression
.op
= LTTV_FIELD_EQ
;
385 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
386 a_field_component
= g_string_new("");
389 * Field concatening caracter
392 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
393 a_field_component
= g_string_new("");
395 default: /* concatening current string */
396 g_string_append_c(a_field_component
,expression
[i
]);
400 g_print("subtree:%p, tree:%p, t1:%p, t2:%p\n",subtree
,tree
,t1
,t2
);
402 /* processing last element of expression */
403 g_assert(tree_stack
->len
==1); /* only root tree should remain */
404 t1
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
405 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
406 if(subtree
!= NULL
) { /* add the subtree */
407 t1
->right
= LTTV_TREE_NODE
;
408 t1
->l_child
.t
= subtree
;
410 } else { /* add a leaf */
411 a_simple_expression
.value
= a_field_component
->str
;
412 a_field_component
= g_string_new("");
413 t1
->right
= LTTV_TREE_LEAF
;
414 t1
->r_child
.leaf
= g_new(lttv_simple_expression
,1);
417 g_assert(tree
!= NULL
);
418 g_assert(subtree
== NULL
);
421 g_warning("Wrong filtering options, the string\n\"%s\"\n\
422 is not valid due to parenthesis incorrect use",expression
);
426 lttv_filter_tracefile(tree
,NULL
);
433 * Apply the filter to a specific trace
434 * @param filter the current filter applied
435 * @param tracefile the trace to apply the filter to
436 * @return success/failure of operation
439 lttv_filter_tracefile(lttv_filter_tree
*filter
, LttTracefile
*tracefile
) {
442 * Each tree is parsed in inorder.
443 * This way, it's possible to apply the left filter of the
444 * tree, then decide whether or not the right branch should
445 * be parsed depending on the linking logical operator
447 * As for the filtering structure, since we are trying
448 * to remove elements from the trace, it might be better
449 * managing an array of all items to be removed ..
452 g_print("node:%p lchild:%p rchild:%p\n",filter
,filter
->l_child
.t
,filter
->r_child
.t
);
453 if(filter
->node
->type
== LTTV_EXPRESSION_OP
) {
454 g_print("node type%i\n",filter
->node
->e
.op
);
456 if(filter
->left
== LTTV_TREE_NODE
) lttv_filter_tracefile(filter
->l_child
.t
,NULL
);
457 else g_print("%p: left is %i\n",filter
,filter
->left
);
458 if(filter
->right
== LTTV_TREE_NODE
) lttv_filter_tracefile(filter
->r_child
.t
,NULL
);
459 else g_print("%p: right is %i\n",filter
,filter
->right
);
463 char *f_name, *e_name;
473 GString *fe_name = g_string_new("");
475 nb = ltt_trace_eventtype_number(tcs->parent.t);
476 g_print("NB:%i\n",nb);
477 for(i = 0 ; i < nb ; i++) {
478 et = ltt_trace_eventtype_get(tcs->parent.t, i);
479 e_name = ltt_eventtype_name(et);
480 f_name = ltt_facility_name(ltt_eventtype_facility(et));
481 g_string_printf(fe_name, "%s.%s", f_name, e_name);
482 g_print("facility:%s and event:%s\n",f_name,e_name);
488 lttv_filter_tracestate(lttv_filter_t
*filter
, LttvTraceState
*tracestate
) {
493 * Apply the filter to a specific event
494 * @param filter the current filter applied
495 * @param event the event to apply the filter to
496 * @return success/failure of operation
499 lttv_filter_event(lttv_filter_t
*filter
, LttEvent
*event
) {
504 * Initializes the filter module and specific values
506 static void module_init()
510 * Quarks initialization
511 * for hardcoded filtering options
513 * TODO: traceset has no yet been defined
517 LTTV_FILTER_EVENT
= g_quark_from_string("event");
518 LTTV_FILTER_TRACE
= g_quark_from_string("trace");
519 LTTV_FILTER_TRACESET
= g_quark_from_string("traceset");
520 LTTV_FILTER_STATE
= g_quark_from_string("state");
521 LTTV_FILTER_TRACEFILE
= g_quark_from_string("tracefile");
523 /* event.name, tracefile.name, trace.name */
524 LTTV_FILTER_NAME
= g_quark_from_string("name");
526 /* event sub fields */
527 LTTV_FILTER_CATEGORY
= g_quark_from_string("category");
528 LTTV_FILTER_TIME
= g_quark_from_string("time");
529 LTTV_FILTER_TSC
= g_quark_from_string("tsc");
531 /* state sub fields */
532 LTTV_FILTER_PID
= g_quark_from_string("pid");
533 LTTV_FILTER_PPID
= g_quark_from_string("ppid");
534 LTTV_FILTER_C_TIME
= g_quark_from_string("creation_time");
535 LTTV_FILTER_I_TIME
= g_quark_from_string("insertion_time");
536 LTTV_FILTER_P_NAME
= g_quark_from_string("process_name");
537 LTTV_FILTER_EX_MODE
= g_quark_from_string("execution_mode");
538 LTTV_FILTER_EX_SUBMODE
= g_quark_from_string("execution_submode");
539 LTTV_FILTER_P_STATUS
= g_quark_from_string("process_status");
540 LTTV_FILTER_CPU
= g_quark_from_string("cpu");
545 * Destroys the filter module and specific values
547 static void module_destroy()
552 LTTV_MODULE("filter", "Filters traceset and events", \
553 "Filters traceset and events specifically to user input", \
554 module_init
, module_destroy
)