test NULL at clone filter begin
[lttv.git] / ltt / branches / poly / lttv / lttv / filter.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2003-2005 Michel Dagenais
3 *
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;
7 *
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.
12 *
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,
16 * MA 02111-1307, USA.
17 */
18
19 /*
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.
24 */
25
26 /*
27 * YET TO BE ANSWERED
28 * - the exists an other lttv_filter which conflicts with this one
29 */
30
31 /*
32 * TODO
33 * - refine switch of expression in multiple uses functions
34 * - remove the idle expressions in the tree ****
35 * - add the current simple expression to the tree
36 */
37
38 #include <lttv/filter.h>
39
40 /*
41 read_token
42
43 read_expression
44 ( read expr )
45 simple expr [ op expr ]
46
47 read_simple_expression
48 read_field_path [ rel value ]
49
50 read_field_path
51 read_field_component [. field path]
52
53 read_field_component
54 name [ \[ value \] ]
55
56 data struct:
57 and/or(left/right)
58 not(child)
59 op(left/right)
60 path(component...) -> field
61 */
62
63 GQuark
64 LTTV_FILTER_TRACE,
65 LTTV_FILTER_TRACESET,
66 LTTV_FILTER_TRACEFILE,
67 LTTV_FILTER_STATE,
68 LTTV_FILTER_EVENT,
69 LTTV_FILTER_NAME,
70 LTTV_FILTER_CATEGORY,
71 LTTV_FILTER_TIME,
72 LTTV_FILTER_TSC,
73 LTTV_FILTER_PID,
74 LTTV_FILTER_PPID,
75 LTTV_FILTER_C_TIME,
76 LTTV_FILTER_I_TIME,
77 LTTV_FILTER_P_NAME,
78 LTTV_FILTER_EX_MODE,
79 LTTV_FILTER_EX_SUBMODE,
80 LTTV_FILTER_P_STATUS,
81 LTTV_FILTER_CPU;
82
83 LttvSimpleExpression*
84 lttv_simple_expression_new() {
85
86 }
87
88 /**
89 * Assign a new tree for the current expression
90 * or sub expression
91 * @return pointer of LttvFilter
92 */
93 LttvFilter* lttv_filter_tree_new() {
94 LttvFilter* tree;
95
96 tree = g_new(LttvFilter,1);
97 tree->node = 0; //g_new(lttv_expression,1);
98 // tree->node->type = LTTV_UNDEFINED_EXPRESSION;
99 tree->left = LTTV_TREE_IDLE;
100 tree->right = LTTV_TREE_IDLE;
101
102 return tree;
103 }
104
105 /**
106 * Destroys the tree and his sub-trees
107 * @param tree Tree which must be destroyed
108 */
109 void lttv_filter_tree_destroy(LttvFilter* tree) {
110
111 if(tree->left == LTTV_TREE_LEAF) g_free(tree->l_child.leaf);
112 else if(tree->left == LTTV_TREE_NODE) lttv_filter_tree_destroy(tree->l_child.t);
113
114 if(tree->right == LTTV_TREE_LEAF) g_free(tree->r_child.leaf);
115 else if(tree->right == LTTV_TREE_NODE) lttv_filter_tree_destroy(tree->r_child.t);
116
117 g_free(tree->node);
118 g_free(tree);
119 }
120
121 LttvFilter*
122 lttv_filter_clone(LttvFilter* tree) {
123
124 if(tree == NULL) return NULL;
125
126 LttvFilter* newtree = lttv_filter_tree_new();
127
128 /*
129 * TODO : Copy tree into new tree
130 */
131
132 return newtree;
133
134 }
135
136 void
137 lttv_filter_tree_add_node(GPtrArray* stack, LttvFilter* subtree, LttvLogicalOp op) {
138
139 LttvFilter* t1 = NULL;
140 LttvFilter* t2 = NULL;
141
142 t1 = (LttvFilter*)g_ptr_array_index(stack,stack->len-1);
143 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
144 t2 = lttv_filter_tree_new();
145 t2->node = op;
146 if(subtree != NULL) {
147 t2->left = LTTV_TREE_NODE;
148 t2->l_child.t = subtree;
149 subtree = NULL;
150 t1->right = LTTV_TREE_NODE;
151 t1->r_child.t = t2;
152 } else {
153 // a_simple_expression->value = a_field_component->str;
154 // a_field_component = g_string_new("");
155 t2->left = LTTV_TREE_LEAF;
156 // t2->l_child.leaf = a_simple_expression;
157 // a_simple_expression = g_new(lttv_simple_expression,1);
158 t1->right = LTTV_TREE_NODE;
159 t1->r_child.t = t2;
160 }
161
162 }
163
164 /**
165 * Parse through filtering field hierarchy as specified
166 * by user. This function compares each value to
167 * predetermined quarks
168 * @param fp The field path list
169 * @return success/failure of operation
170 */
171 gboolean
172 parse_field_path(GPtrArray* fp) {
173
174 GString* f = NULL;
175 if(fp->len < 2) return FALSE;
176 g_assert(f=g_ptr_array_index(fp,0)); //list_first(fp)->data;
177
178 if(g_quark_try_string(f->str) == LTTV_FILTER_EVENT) {
179 f=g_ptr_array_index(fp,1);
180 if(g_quark_try_string(f->str) == LTTV_FILTER_NAME) {}
181 else if(g_quark_try_string(f->str) == LTTV_FILTER_CATEGORY) {}
182 else if(g_quark_try_string(f->str) == LTTV_FILTER_TIME) {
183 // offset = &((LttEvent*)NULL)->event_time);
184 }
185 else if(g_quark_try_string(f->str) == LTTV_FILTER_TSC) {
186 // offset = &((LttEvent*)NULL)->event_cycle_count);
187 }
188 else { /* core.xml specified options */
189
190 }
191 } else if(g_quark_try_string(f->str) == LTTV_FILTER_TRACEFILE) {
192 f=g_ptr_array_index(fp,1);
193 if(g_quark_try_string(f->str) == LTTV_FILTER_NAME) {}
194 else return FALSE;
195 } else if(g_quark_try_string(f->str) == LTTV_FILTER_TRACE) {
196 f=g_ptr_array_index(fp,1);
197 if(g_quark_try_string(f->str) == LTTV_FILTER_NAME) {}
198 else return FALSE;
199
200 } else if(g_quark_try_string(f->str) == LTTV_FILTER_STATE) {
201 f=g_ptr_array_index(fp,1);
202 if(g_quark_try_string(f->str) == LTTV_FILTER_PID) {}
203 else if(g_quark_try_string(f->str) == LTTV_FILTER_PPID) {}
204 else if(g_quark_try_string(f->str) == LTTV_FILTER_C_TIME) {}
205 else if(g_quark_try_string(f->str) == LTTV_FILTER_I_TIME) {}
206 else if(g_quark_try_string(f->str) == LTTV_FILTER_P_NAME) {}
207 else if(g_quark_try_string(f->str) == LTTV_FILTER_EX_MODE) {}
208 else if(g_quark_try_string(f->str) == LTTV_FILTER_EX_SUBMODE) {}
209 else if(g_quark_try_string(f->str) == LTTV_FILTER_P_STATUS) {}
210 else if(g_quark_try_string(f->str) == LTTV_FILTER_CPU) {}
211 else return FALSE;
212
213 } else {
214 g_warning("Unrecognized field in filter string");
215 return FALSE;
216 }
217 return TRUE;
218 }
219
220 /**
221 * Add an filtering option to the current tree
222 * @param expression Current expression to parse
223 * @return success/failure of operation
224 */
225 gboolean
226 parse_simple_expression(GString* expression) {
227
228 unsigned i;
229
230
231
232
233 }
234
235 /**
236 * Creates a new lttv_filter
237 * @param expression filtering options string
238 * @param t pointer to the current LttvTrace
239 * @return the current lttv_filter or NULL if error
240 */
241 LttvFilter*
242 lttv_filter_new(char *expression, LttvTraceState *tcs) {
243
244 g_print("filter::lttv_filter_new()\n"); /* debug */
245
246 unsigned
247 i,
248 p_nesting=0, /* parenthesis nesting value */
249 b=0; /* current breakpoint in expression string */
250
251 /* trees */
252 LttvFilter
253 *tree = lttv_filter_tree_new(), /* main tree */
254 *subtree = NULL, /* buffer for subtrees */
255 *t1, /* buffer #1 */
256 *t2; /* buffer #2 */
257
258 /*
259 * Tree Stack
260 * each element of the list
261 * is a sub tree created
262 * by the use of parenthesis in the
263 * global expression. The final tree
264 * will be the one left at the root of
265 * the list
266 */
267 GPtrArray *tree_stack = g_ptr_array_new();
268 g_ptr_array_add( tree_stack,(gpointer) tree );
269
270 /* temporary values */
271 GString *a_field_component = g_string_new("");
272 GPtrArray *a_field_path = NULL;
273
274 LttvSimpleExpression* a_simple_expression = g_new(LttvSimpleExpression,1);
275
276 /*
277 * Parse entire expression and construct
278 * the binary tree. There are two steps
279 * in browsing that string
280 * 1. finding boolean ops " &,|,^,! " and parenthesis " {,(,[,],),} "
281 * 2. finding simple expressions
282 * - field path ( separated by dots )
283 * - op ( >, <, =, >=, <=, !=)
284 * - value ( integer, string ... )
285 * To spare computing time, the whole
286 * string is parsed in this loop for a
287 * O(n) complexity order.
288 *
289 * When encountering logical op &,|,^
290 * 1. parse the last value if any
291 * 2. create a new tree
292 * 3. add the expression (simple exp, or exp (subtree)) to the tree
293 * 4. concatenate this tree with the current tree on top of the stack
294 * When encountering math ops >,>=,<,<=,=,!=
295 * 1. add to op to the simple expression
296 * 2. concatenate last field component to field path
297 * When encountering concatening ops .
298 * 1. concatenate last field component to field path
299 * When encountering opening parenthesis (,{,[
300 * 1. create a new subtree on top of tree stack
301 * When encountering closing parenthesis ),},]
302 * 1. add the expression on right child of the current tree
303 * 2. the subtree is completed, allocate a new subtree
304 * 3. pop the tree value from the tree stack
305 */
306
307 a_field_path = g_ptr_array_new();
308 g_ptr_array_set_size(a_field_path,2); /* by default, recording 2 field expressions */
309
310
311 for(i=0;i<strlen(expression);i++) {
312 // g_print("%s\n",a_field_component->str);
313 g_print("%c ",expression[i]);
314 // g_print("switch:%c -->subtree:%p\n",expression[i],subtree);
315 switch(expression[i]) {
316 /*
317 * logical operators
318 */
319 case '&': /* and */
320 t1 = (LttvFilter*)g_ptr_array_index(tree_stack,tree_stack->len-1);
321 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
322 t2 = lttv_filter_tree_new();
323 t2->node = LTTV_LOGICAL_AND;
324 if(subtree != NULL) {
325 t2->left = LTTV_TREE_NODE;
326 t2->l_child.t = subtree;
327 subtree = NULL;
328 t1->right = LTTV_TREE_NODE;
329 t1->r_child.t = t2;
330 } else {
331 a_simple_expression->value = a_field_component->str;
332 a_field_component = g_string_new("");
333 t2->left = LTTV_TREE_LEAF;
334 t2->l_child.leaf = a_simple_expression;
335 a_simple_expression = g_new(LttvSimpleExpression,1);
336 t1->right = LTTV_TREE_NODE;
337 t1->r_child.t = t2;
338 }
339
340 break;
341 case '|': /* or */
342 t1 = (LttvFilter*)g_ptr_array_index(tree_stack,tree_stack->len-1);
343 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
344 t2 = lttv_filter_tree_new();
345 t2->node = LTTV_LOGICAL_OR;
346 if(subtree != NULL) {
347 t2->left = LTTV_TREE_NODE;
348 t2->l_child.t = subtree;
349 subtree = NULL;
350 t1->right = LTTV_TREE_NODE;
351 t1->r_child.t = t2;
352 } else {
353 a_simple_expression->value = a_field_component->str;
354 a_field_component = g_string_new("");
355 t2->left = LTTV_TREE_LEAF;
356 t2->l_child.leaf = a_simple_expression;
357 a_simple_expression = g_new(LttvSimpleExpression,1);
358 t1->right = LTTV_TREE_NODE;
359 t1->r_child.t = t2;
360 }
361 break;
362 case '^': /* xor */
363 t1 = (LttvFilter*)g_ptr_array_index(tree_stack,tree_stack->len-1);
364 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
365 t2 = lttv_filter_tree_new();
366 t2->node = LTTV_LOGICAL_XOR;
367 if(subtree != NULL) {
368 t2->left = LTTV_TREE_NODE;
369 t2->l_child.t = subtree;
370 subtree = NULL;
371 t1->right = LTTV_TREE_NODE;
372 t1->r_child.t = t2;
373 } else {
374 a_simple_expression->value = a_field_component->str;
375 a_field_component = g_string_new("");
376 t2->left = LTTV_TREE_LEAF;
377 t2->l_child.leaf = a_simple_expression;
378 a_simple_expression = g_new(LttvSimpleExpression,1);
379 t1->right = LTTV_TREE_NODE;
380 t1->r_child.t = t2;
381 }
382 break;
383 case '!': /* not, or not equal (math op) */
384 if(expression[i+1] == '=') { /* != */
385 a_simple_expression->op = LTTV_FIELD_NE;
386 i++;
387 g_ptr_array_add( a_field_path,(gpointer) a_field_component );
388 a_field_component = g_string_new("");
389 } else { /* ! */
390 // g_print("%s\n",a_field_component);
391 // a_field_component = g_string_new("");
392 t1 = (LttvFilter*)g_ptr_array_index(tree_stack,tree_stack->len-1);
393 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
394 t2 = lttv_filter_tree_new();
395 t2->node = LTTV_LOGICAL_NOT;
396 t1->right = LTTV_TREE_NODE;
397 t1->r_child.t = t2;
398 }
399 break;
400 case '(': /* start of parenthesis */
401 case '[':
402 case '{':
403 p_nesting++; /* incrementing parenthesis nesting value */
404 t1 = lttv_filter_tree_new();
405 g_ptr_array_add( tree_stack,(gpointer) t1 );
406 break;
407 case ')': /* end of parenthesis */
408 case ']':
409 case '}':
410 p_nesting--; /* decrementing parenthesis nesting value */
411 if(p_nesting<0 || tree_stack->len<2) {
412 g_warning("Wrong filtering options, the string\n\"%s\"\n\
413 is not valid due to parenthesis incorrect use",expression);
414 return NULL;
415 }
416
417 g_assert(tree_stack->len>0);
418 if(subtree != NULL) {
419 t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
420 while(t1->right != LTTV_TREE_IDLE && t1->right != LTTV_TREE_LEAF) {
421 g_assert(t1!=NULL && t1->r_child.t != NULL);
422 t1 = t1->r_child.t;
423 }
424 t1->right = LTTV_TREE_NODE;
425 t1->r_child.t = subtree;
426 subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
427 g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
428 } else {
429 a_simple_expression->value = a_field_component->str;
430 a_field_component = g_string_new("");
431 t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
432 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
433 t1->right = LTTV_TREE_LEAF;
434 t1->r_child.leaf = a_simple_expression;
435 a_simple_expression = g_new(LttvSimpleExpression,1);
436 subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
437 g_assert(subtree != NULL);
438 g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
439 }
440 break;
441
442 /*
443 * mathematic operators
444 */
445 case '<': /* lower, lower or equal */
446 if(expression[i+1] == '=') { /* <= */
447 i++;
448 a_simple_expression->op = LTTV_FIELD_LE;
449 } else a_simple_expression->op = LTTV_FIELD_LT;
450 g_ptr_array_add( a_field_path,(gpointer) a_field_component );
451 a_field_component = g_string_new("");
452 break;
453 case '>': /* higher, higher or equal */
454 if(expression[i+1] == '=') { /* >= */
455 i++;
456 a_simple_expression->op = LTTV_FIELD_GE;
457 } else a_simple_expression->op = LTTV_FIELD_GT;
458 g_ptr_array_add( a_field_path,(gpointer) a_field_component );
459 a_field_component = g_string_new("");
460 break;
461 case '=': /* equal */
462 a_simple_expression->op = LTTV_FIELD_EQ;
463 g_ptr_array_add( a_field_path,(gpointer) a_field_component );
464 a_field_component = g_string_new("");
465 break;
466 /*
467 * Field concatening caracter
468 */
469 case '.': /* dot */
470 g_ptr_array_add( a_field_path,(gpointer) a_field_component );
471 a_field_component = g_string_new("");
472 break;
473 default: /* concatening current string */
474 g_string_append_c(a_field_component,expression[i]);
475 }
476 }
477
478 g_print("subtree:%p, tree:%p, t1:%p, t2:%p\n",subtree,tree,t1,t2);
479 g_print("stack size: %i\n",tree_stack->len);
480
481 /*
482 * Preliminary check to see
483 * if tree was constructed correctly
484 */
485 if( p_nesting>0 ) {
486 g_warning("Wrong filtering options, the string\n\"%s\"\n\
487 is not valid due to parenthesis incorrect use",expression);
488 return NULL;
489 }
490
491 if(tree_stack->len != 1) /* only root tree should remain */
492 return NULL;
493
494 /* processing last element of expression */
495 t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
496 while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
497 if(subtree != NULL) { /* add the subtree */
498 t1->right = LTTV_TREE_NODE;
499 t1->r_child.t = subtree;
500 subtree = NULL;
501 } else { /* add a leaf */
502 a_simple_expression->value = a_field_component->str;
503 a_field_component = g_string_new("");
504 t1->right = LTTV_TREE_LEAF;
505 t1->r_child.leaf = a_simple_expression;
506 /*
507 * FIXME: is it really necessary to reallocate
508 * LttvSimpleExpression at this point ??
509 */
510 a_simple_expression = g_new(LttvSimpleExpression,1);
511 }
512
513 g_assert(tree != NULL);
514 g_assert(subtree == NULL);
515
516 lttv_filter_tracefile(tree,NULL);
517
518 return tree;
519
520 }
521
522 void
523 lttv_filter_destroy(LttvFilter* filter) {
524
525 }
526
527 /**
528 * Apply the filter to a specific trace
529 * @param filter the current filter applied
530 * @param tracefile the trace to apply the filter to
531 * @return success/failure of operation
532 */
533 gboolean
534 lttv_filter_tracefile(LttvFilter *filter, LttTracefile *tracefile) {
535
536 /*
537 * Each tree is parsed in inorder.
538 * This way, it's possible to apply the left filter of the
539 * tree, then decide whether or not the right branch should
540 * be parsed depending on the linking logical operator
541 *
542 * As for the filtering structure, since we are trying
543 * to remove elements from the trace, it might be better
544 * managing an array of all items to be removed ..
545 */
546
547 g_print("node:%p lchild:%p rchild:%p\n",filter,filter->l_child.t,filter->r_child.t);
548 g_print("node type%i\n",filter->node);
549 if(filter->left == LTTV_TREE_NODE) lttv_filter_tracefile(filter->l_child.t,NULL);
550 else if(filter->left == LTTV_TREE_LEAF) {
551 g_assert(filter->l_child.leaf->value != NULL);
552 g_print("%p: left is qqch %i %s\n",filter,filter->l_child.leaf->op,filter->l_child.leaf->value);
553 }
554 if(filter->right == LTTV_TREE_NODE) lttv_filter_tracefile(filter->r_child.t,NULL);
555 else if(filter->right == LTTV_TREE_LEAF) {
556 g_assert(filter->r_child.leaf->value != NULL);
557 g_print("%p: right is qqch %i %s\n",filter,filter->r_child.leaf->op,filter->r_child.leaf->value);
558 }
559
560 /* test */
561 /* int i, nb;
562 char *f_name, *e_name;
563
564 char* field = "cpu";
565
566 LttvTraceHook h;
567
568 LttEventType *et;
569
570 LttType *t;
571
572 GString *fe_name = g_string_new("");
573
574 nb = ltt_trace_eventtype_number(tcs->parent.t);
575 g_print("NB:%i\n",nb);
576 for(i = 0 ; i < nb ; i++) {
577 et = ltt_trace_eventtype_get(tcs->parent.t, i);
578 e_name = ltt_eventtype_name(et);
579 f_name = ltt_facility_name(ltt_eventtype_facility(et));
580 g_string_printf(fe_name, "%s.%s", f_name, e_name);
581 g_print("facility:%s and event:%s\n",f_name,e_name);
582 }
583 */
584 }
585
586 gboolean
587 lttv_filter_tracestate(LttvFilter *filter, LttvTraceState *tracestate) {
588
589 }
590
591 /**
592 * Apply the filter to a specific event
593 * @param filter the current filter applied
594 * @param event the event to apply the filter to
595 * @return success/failure of operation
596 */
597 gboolean
598 lttv_filter_event(LttvFilter *filter, LttEvent *event) {
599
600 }
601
602 /**
603 * Initializes the filter module and specific values
604 */
605 static void module_init()
606 {
607
608 /*
609 * Quarks initialization
610 * for hardcoded filtering options
611 *
612 * TODO: traceset has no yet been defined
613 */
614
615 /* top fields */
616 LTTV_FILTER_EVENT = g_quark_from_string("event");
617 LTTV_FILTER_TRACE = g_quark_from_string("trace");
618 LTTV_FILTER_TRACESET = g_quark_from_string("traceset");
619 LTTV_FILTER_STATE = g_quark_from_string("state");
620 LTTV_FILTER_TRACEFILE = g_quark_from_string("tracefile");
621
622 /* event.name, tracefile.name, trace.name */
623 LTTV_FILTER_NAME = g_quark_from_string("name");
624
625 /* event sub fields */
626 LTTV_FILTER_CATEGORY = g_quark_from_string("category");
627 LTTV_FILTER_TIME = g_quark_from_string("time");
628 LTTV_FILTER_TSC = g_quark_from_string("tsc");
629
630 /* state sub fields */
631 LTTV_FILTER_PID = g_quark_from_string("pid");
632 LTTV_FILTER_PPID = g_quark_from_string("ppid");
633 LTTV_FILTER_C_TIME = g_quark_from_string("creation_time");
634 LTTV_FILTER_I_TIME = g_quark_from_string("insertion_time");
635 LTTV_FILTER_P_NAME = g_quark_from_string("process_name");
636 LTTV_FILTER_EX_MODE = g_quark_from_string("execution_mode");
637 LTTV_FILTER_EX_SUBMODE = g_quark_from_string("execution_submode");
638 LTTV_FILTER_P_STATUS = g_quark_from_string("process_status");
639 LTTV_FILTER_CPU = g_quark_from_string("cpu");
640
641 }
642
643 /**
644 * Destroys the filter module and specific values
645 */
646 static void module_destroy()
647 {
648 }
649
650
651 LTTV_MODULE("filter", "Filters traceset and events", \
652 "Filters traceset and events specifically to user input", \
653 module_init, module_destroy)
654
655
656
This page took 0.04292 seconds and 5 git commands to generate.