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 * - divide expression structure
35 * - a simple expression -> leaf
36 * - a logical operator -> node
37 * - add the current simple expression to the tree
40 #include <lttv/filter.h>
47 simple expr [ op expr ]
49 read_simple_expression
50 read_field_path [ rel value ]
53 read_field_component [. field path]
62 path(component...) -> field
68 LTTV_FILTER_TRACEFILE
,
81 LTTV_FILTER_EX_SUBMODE
,
86 * Assign a new tree for the current expression
88 * @return pointer of lttv_filter_tree
90 lttv_filter_tree
* lttv_filter_tree_new() {
91 lttv_filter_tree
* tree
;
93 tree
= g_new(lttv_filter_tree
,1);
94 tree
->node
= g_new(lttv_expression
,1);
95 tree
->node
->type
= LTTV_UNDEFINED_EXPRESSION
;
96 tree
->left
= LTTV_TREE_UNDEFINED
;
97 tree
->right
= LTTV_TREE_UNDEFINED
;
103 * Destroys the tree and his sub-trees
104 * @param tree Tree which must be destroyed
106 void lttv_filter_tree_destroy(lttv_filter_tree
* tree
) {
108 if(tree
->left
== LTTV_TREE_LEAF
) g_free(tree
->l_child
.leaf
);
109 else if(tree
->left
== LTTV_TREE_NODE
) lttv_filter_tree_destroy(tree
->l_child
.t
);
111 if(tree
->right
== LTTV_TREE_LEAF
) g_free(tree
->r_child
.leaf
);
112 else if(tree
->right
== LTTV_TREE_NODE
) lttv_filter_tree_destroy(tree
->r_child
.t
);
119 * Parse through filtering field hierarchy as specified
120 * by user. This function compares each value to
121 * predetermined quarks
122 * @param fp The field path list
123 * @return success/failure of operation
126 parse_field_path(GPtrArray
* fp
) {
129 if(fp
->len
< 2) return FALSE
;
130 g_assert(f
=g_ptr_array_index(fp
,0)); //list_first(fp)->data;
132 if(g_quark_try_string(f
->str
) == LTTV_FILTER_EVENT
) {
133 f
=g_ptr_array_index(fp
,1);
134 if(g_quark_try_string(f
->str
) == LTTV_FILTER_NAME
) {}
135 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_CATEGORY
) {}
136 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_TIME
) {
137 // offset = &((LttEvent*)NULL)->event_time);
139 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_TSC
) {
140 // offset = &((LttEvent*)NULL)->event_cycle_count);
142 else { /* core.xml specified options */
145 } else if(g_quark_try_string(f
->str
) == LTTV_FILTER_TRACEFILE
) {
146 f
=g_ptr_array_index(fp
,1);
147 if(g_quark_try_string(f
->str
) == LTTV_FILTER_NAME
) {}
149 } else if(g_quark_try_string(f
->str
) == LTTV_FILTER_TRACE
) {
150 f
=g_ptr_array_index(fp
,1);
151 if(g_quark_try_string(f
->str
) == LTTV_FILTER_NAME
) {}
154 } else if(g_quark_try_string(f
->str
) == LTTV_FILTER_STATE
) {
155 f
=g_ptr_array_index(fp
,1);
156 if(g_quark_try_string(f
->str
) == LTTV_FILTER_PID
) {}
157 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_PPID
) {}
158 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_C_TIME
) {}
159 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_I_TIME
) {}
160 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_P_NAME
) {}
161 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_EX_MODE
) {}
162 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_EX_SUBMODE
) {}
163 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_P_STATUS
) {}
164 else if(g_quark_try_string(f
->str
) == LTTV_FILTER_CPU
) {}
168 g_warning("Unrecognized field in filter string");
175 * Add an filtering option to the current tree
176 * @param expression Current expression to parse
177 * @return success/failure of operation
180 parse_simple_expression(GString
* expression
) {
190 * Creates a new lttv_filter
191 * @param expression filtering options string
192 * @param t pointer to the current LttvTrace
193 * @return the current lttv_filter or NULL if error
196 lttv_filter_new(char *expression
, LttvTraceState
*tcs
) {
198 g_print("filter::lttv_filter_new()\n"); /* debug */
202 p_nesting
=0, /* parenthesis nesting value */
203 b
=0; /* current breakpoint in expression string */
207 *tree
= lttv_filter_tree_new(), /* main tree */
208 *subtree
= NULL
, /* buffer for subtrees */
214 * each element of the list
215 * is a sub tree created
216 * by the use of parenthesis in the
217 * global expression. The final tree
218 * will be the one left at the root of
221 GPtrArray
*tree_stack
= g_ptr_array_new();
222 g_ptr_array_add( tree_stack
,(gpointer
) tree
);
224 /* temporary values */
225 GString
*a_field_component
= g_string_new("");
226 GPtrArray
*a_field_path
= NULL
;
228 lttv_simple_expression a_simple_expression
;
231 * Parse entire expression and construct
232 * the binary tree. There are two steps
233 * in browsing that string
234 * 1. finding boolean ops " &,|,^,! " and parenthesis " {,(,[,],),} "
235 * 2. finding simple expressions
236 * - field path ( separated by dots )
237 * - op ( >, <, =, >=, <=, !=)
238 * - value ( integer, string ... )
239 * To spare computing time, the whole
240 * string is parsed in this loop for a
241 * O(n) complexity order.
243 * When encountering logical op &,|,^
244 * 1. parse the last value if any
245 * 2. create a new tree
246 * 3. add the expression (simple exp, or exp (subtree)) to the tree
247 * 4. concatenate this tree with the current tree on top of the stack
248 * When encountering math ops >,>=,<,<=,=,!=
249 * 1. add to op to the simple expression
250 * 2. concatenate last field component to field path
251 * When encountering concatening ops .
252 * 1. concatenate last field component to field path
253 * When encountering opening parenthesis (,{,[
254 * 1. create a new subtree on top of tree stack
255 * When encountering closing parenthesis ),},]
256 * 1. add the expression on right child of the current tree
257 * 2. the subtree is completed, allocate a new subtree
258 * 3. pop the tree value from the tree stack
261 a_field_path
= g_ptr_array_new();
262 g_ptr_array_set_size(a_field_path
,2); /* by default, recording 2 field expressions */
265 for(i
=0;i
<strlen(expression
);i
++) {
266 // g_print("%s\n",a_field_component->str);
267 g_print("%c ",expression
[i
]);
268 // g_print("switch:%c -->subtree:%p\n",expression[i],subtree);
269 switch(expression
[i
]) {
274 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
275 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
276 t2
= lttv_filter_tree_new();
277 t2
->node
->type
= LTTV_EXPRESSION_OP
;
278 t2
->node
->e
.op
= LTTV_LOGICAL_AND
;
279 if(subtree
!= NULL
) {
280 t2
->left
= LTTV_TREE_NODE
;
281 t2
->l_child
.t
= subtree
;
283 t1
->right
= LTTV_TREE_NODE
;
286 a_simple_expression
.value
= a_field_component
->str
;
287 a_field_component
= g_string_new("");
288 t2
->left
= LTTV_TREE_LEAF
;
289 t2
->l_child
.leaf
= g_new(lttv_simple_expression
,1);
290 t1
->right
= LTTV_TREE_NODE
;
296 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
297 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
298 t2
= lttv_filter_tree_new();
299 t2
->node
->type
= LTTV_EXPRESSION_OP
;
300 t2
->node
->e
.op
= LTTV_LOGICAL_OR
;
301 if(subtree
!= NULL
) {
302 t2
->left
= LTTV_TREE_NODE
;
303 t2
->l_child
.t
= subtree
;
305 t1
->right
= LTTV_TREE_NODE
;
308 a_simple_expression
.value
= a_field_component
->str
;
309 a_field_component
= g_string_new("");
310 t2
->left
= LTTV_TREE_LEAF
;
311 t2
->l_child
.leaf
= g_new(lttv_simple_expression
,1);
312 t1
->right
= LTTV_TREE_NODE
;
317 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
318 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
319 t2
= lttv_filter_tree_new();
320 t2
->node
->type
= LTTV_EXPRESSION_OP
;
321 t2
->node
->e
.op
= LTTV_LOGICAL_XOR
;
322 if(subtree
!= NULL
) {
323 t2
->left
= LTTV_TREE_NODE
;
324 t2
->l_child
.t
= subtree
;
326 t1
->right
= LTTV_TREE_NODE
;
329 a_simple_expression
.value
= a_field_component
->str
;
330 a_field_component
= g_string_new("");
331 t2
->left
= LTTV_TREE_LEAF
;
332 t2
->l_child
.leaf
= g_new(lttv_simple_expression
,1);
333 t1
->right
= LTTV_TREE_NODE
;
337 case '!': /* not, or not equal (math op) */
338 if(expression
[i
+1] == '=') { /* != */
339 a_simple_expression
.op
= LTTV_FIELD_NE
;
342 // g_print("%s\n",a_field_component);
343 // a_field_component = g_string_new("");
344 t1
= (lttv_filter_tree
*)g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
345 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
346 t2
= lttv_filter_tree_new();
347 t2
->node
->type
= LTTV_EXPRESSION_OP
;
348 t2
->node
->e
.op
= LTTV_LOGICAL_NOT
;
349 t1
->right
= LTTV_TREE_NODE
;
353 case '(': /* start of parenthesis */
356 p_nesting
++; /* incrementing parenthesis nesting value */
357 t1
= lttv_filter_tree_new();
358 g_ptr_array_add( tree_stack
,(gpointer
) t1
);
360 case ')': /* end of parenthesis */
363 p_nesting
--; /* decrementing parenthesis nesting value */
364 if(p_nesting
<0 || tree_stack
->len
<2) {
365 g_warning("Wrong filtering options, the string\n\"%s\"\n\
366 is not valid due to parenthesis incorrect use",expression
);
370 g_assert(tree_stack
->len
>0);
371 if(subtree
!= NULL
) {
372 t1
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
373 while(t1
->right
!= LTTV_TREE_UNDEFINED
&& t1
->right
!= LTTV_TREE_LEAF
) {
374 g_assert(t1
!=NULL
&& t1
->r_child
.t
!= NULL
);
377 t1
->right
= LTTV_TREE_NODE
;
378 t1
->r_child
.t
= subtree
;
379 subtree
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
380 g_ptr_array_remove_index(tree_stack
,tree_stack
->len
-1);
382 a_simple_expression
.value
= a_field_component
->str
;
383 a_field_component
= g_string_new("");
384 t1
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
385 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
386 t1
->right
= LTTV_TREE_LEAF
;
387 t1
->r_child
.leaf
= g_new(lttv_simple_expression
,1);
388 subtree
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
389 g_assert(subtree
!= NULL
);
390 g_ptr_array_remove_index(tree_stack
,tree_stack
->len
-1);
395 * mathematic operators
397 case '<': /* lower, lower or equal */
398 if(expression
[i
+1] == '=') { /* <= */
400 a_simple_expression
.op
= LTTV_FIELD_LE
;
401 } else a_simple_expression
.op
= LTTV_FIELD_LT
;
402 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
403 a_field_component
= g_string_new("");
405 case '>': /* higher, higher or equal */
406 if(expression
[i
+1] == '=') { /* >= */
408 a_simple_expression
.op
= LTTV_FIELD_GE
;
409 } else a_simple_expression
.op
= LTTV_FIELD_GT
;
410 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
411 a_field_component
= g_string_new("");
413 case '=': /* equal */
414 a_simple_expression
.op
= LTTV_FIELD_EQ
;
415 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
416 a_field_component
= g_string_new("");
419 * Field concatening caracter
422 g_ptr_array_add( a_field_path
,(gpointer
) a_field_component
);
423 a_field_component
= g_string_new("");
425 default: /* concatening current string */
426 g_string_append_c(a_field_component
,expression
[i
]);
430 g_print("subtree:%p, tree:%p, t1:%p, t2:%p\n",subtree
,tree
,t1
,t2
);
432 /* processing last element of expression */
433 g_assert(tree_stack
->len
==1); /* only root tree should remain */
434 t1
= g_ptr_array_index(tree_stack
,tree_stack
->len
-1);
435 while(t1
->right
!= LTTV_TREE_UNDEFINED
) t1
= t1
->r_child
.t
;
436 if(subtree
!= NULL
) { /* add the subtree */
437 t1
->right
= LTTV_TREE_NODE
;
438 t1
->l_child
.t
= subtree
;
440 } else { /* add a leaf */
441 a_simple_expression
.value
= a_field_component
->str
;
442 a_field_component
= g_string_new("");
443 t1
->right
= LTTV_TREE_LEAF
;
444 t1
->r_child
.leaf
= g_new(lttv_simple_expression
,1);
447 g_assert(tree
!= NULL
);
448 g_assert(subtree
== NULL
);
451 g_warning("Wrong filtering options, the string\n\"%s\"\n\
452 is not valid due to parenthesis incorrect use",expression
);
456 lttv_filter_tracefile(tree
,NULL
);
463 * Apply the filter to a specific trace
464 * @param filter the current filter applied
465 * @param tracefile the trace to apply the filter to
466 * @return success/failure of operation
469 lttv_filter_tracefile(lttv_filter_tree
*filter
, LttTracefile
*tracefile
) {
472 * Each tree is parsed in inorder.
473 * This way, it's possible to apply the left filter of the
474 * tree, then decide whether or not the right branch should
475 * be parsed depending on the linking logical operator
477 * As for the filtering structure, since we are trying
478 * to remove elements from the trace, it might be better
479 * managing an array of all items to be removed ..
482 g_print("node:%p lchild:%p rchild:%p\n",filter
,filter
->l_child
.t
,filter
->r_child
.t
);
483 if(filter
->node
->type
== LTTV_EXPRESSION_OP
) {
484 g_print("node type%i\n",filter
->node
->e
.op
);
486 if(filter
->left
== LTTV_TREE_NODE
) lttv_filter_tracefile(filter
->l_child
.t
,NULL
);
487 else g_print("%p: left is %i\n",filter
,filter
->left
);
488 if(filter
->right
== LTTV_TREE_NODE
) lttv_filter_tracefile(filter
->r_child
.t
,NULL
);
489 else g_print("%p: right is %i\n",filter
,filter
->right
);
493 char *f_name, *e_name;
503 GString *fe_name = g_string_new("");
505 nb = ltt_trace_eventtype_number(tcs->parent.t);
506 g_print("NB:%i\n",nb);
507 for(i = 0 ; i < nb ; i++) {
508 et = ltt_trace_eventtype_get(tcs->parent.t, i);
509 e_name = ltt_eventtype_name(et);
510 f_name = ltt_facility_name(ltt_eventtype_facility(et));
511 g_string_printf(fe_name, "%s.%s", f_name, e_name);
512 g_print("facility:%s and event:%s\n",f_name,e_name);
518 lttv_filter_tracestate(lttv_filter_t
*filter
, LttvTraceState
*tracestate
) {
523 * Apply the filter to a specific event
524 * @param filter the current filter applied
525 * @param event the event to apply the filter to
526 * @return success/failure of operation
529 lttv_filter_event(lttv_filter_t
*filter
, LttEvent
*event
) {
534 * Initializes the filter module and specific values
536 static void module_init()
540 * Quarks initialization
541 * for hardcoded filtering options
543 * TODO: traceset has no yet been defined
547 LTTV_FILTER_EVENT
= g_quark_from_string("event");
548 LTTV_FILTER_TRACE
= g_quark_from_string("trace");
549 LTTV_FILTER_TRACESET
= g_quark_from_string("traceset");
550 LTTV_FILTER_STATE
= g_quark_from_string("state");
551 LTTV_FILTER_TRACEFILE
= g_quark_from_string("tracefile");
553 /* event.name, tracefile.name, trace.name */
554 LTTV_FILTER_NAME
= g_quark_from_string("name");
556 /* event sub fields */
557 LTTV_FILTER_CATEGORY
= g_quark_from_string("category");
558 LTTV_FILTER_TIME
= g_quark_from_string("time");
559 LTTV_FILTER_TSC
= g_quark_from_string("tsc");
561 /* state sub fields */
562 LTTV_FILTER_PID
= g_quark_from_string("pid");
563 LTTV_FILTER_PPID
= g_quark_from_string("ppid");
564 LTTV_FILTER_C_TIME
= g_quark_from_string("creation_time");
565 LTTV_FILTER_I_TIME
= g_quark_from_string("insertion_time");
566 LTTV_FILTER_P_NAME
= g_quark_from_string("process_name");
567 LTTV_FILTER_EX_MODE
= g_quark_from_string("execution_mode");
568 LTTV_FILTER_EX_SUBMODE
= g_quark_from_string("execution_submode");
569 LTTV_FILTER_P_STATUS
= g_quark_from_string("process_status");
570 LTTV_FILTER_CPU
= g_quark_from_string("cpu");
575 * Destroys the filter module and specific values
577 static void module_destroy()
582 LTTV_MODULE("filter", "Filters traceset and events", \
583 "Filters traceset and events specifically to user input", \
584 module_init
, module_destroy
)