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  *  - add the current simple expression to the tree
  35  */
  36
  37 #include <lttv/filter.h>
  38
  39 /*
  40   read_token
  41
  42   read_expression
  43     ( read expr )
  44     simple expr [ op expr ]
  45
  46   read_simple_expression
  47     read_field_path [ rel value ]
  48
  49   read_field_path
  50     read_field_component [. field path]
  51
  52   read_field_component
  53     name [ \[ value \] ]
  54
  55   data struct:
  56   and/or(left/right)
  57   not(child)
  58   op(left/right)
  59   path(component...) -> field
  60 */
  61
  62 GQuark
  63   LTTV_FILTER_TRACE,
  64   LTTV_FILTER_TRACESET,
  65   LTTV_FILTER_TRACEFILE,
  66   LTTV_FILTER_STATE,
  67   LTTV_FILTER_EVENT,
  68   LTTV_FILTER_NAME,
  69   LTTV_FILTER_CATEGORY,
  70   LTTV_FILTER_TIME,
  71   LTTV_FILTER_TSC,
  72   LTTV_FILTER_PID,
  73   LTTV_FILTER_PPID,
  74   LTTV_FILTER_C_TIME,
  75   LTTV_FILTER_I_TIME,
  76   LTTV_FILTER_P_NAME,
  77   LTTV_FILTER_EX_MODE,
  78   LTTV_FILTER_EX_SUBMODE,
  79   LTTV_FILTER_P_STATUS,
  80   LTTV_FILTER_CPU;
  81
  82 /**
  83  *  Assign a new tree for the current expression
  84  *  or sub expression
  85  *  @return pointer of lttv_filter_tree
  86  */
  87 lttv_filter_tree* lttv_filter_tree_new() {
  88   lttv_filter_tree* tree;
  89
  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;
  95
  96   return tree;
  97 }
  98
  99 /**
 100  *  Destroys the tree and his sub-trees
 101  *  @param tree Tree which must be destroyed
 102  */
 103 void lttv_filter_tree_destroy(lttv_filter_tree* tree) {
 104
 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);
 107
 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);
 110
 111   g_free(tree->node);
 112   g_free(tree);
 113 }
 114
 115 /**
 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
 121  */
 122 gboolean
 123 parse_field_path(GPtrArray* fp) {
 124
 125   GString* f = NULL;
 126   g_assert(f=g_ptr_array_index(fp,0)); //list_first(fp)->data;
 127
 128   if(g_quark_try_string(f->str) == LTTV_FILTER_EVENT) {
 129 //    parse_subfield(fp, LTTV_FILTER_EVENT);
 130
 131   } else if(g_quark_try_string(f->str) == LTTV_FILTER_TRACEFILE) {
 132
 133   } else if(g_quark_try_string(f->str) == LTTV_FILTER_TRACE) {
 134
 135   } else if(g_quark_try_string(f->str) == LTTV_FILTER_STATE) {
 136
 137   } else {
 138     g_warning("Unrecognized field in filter string");
 139     return FALSE;
 140   }
 141   return TRUE;
 142 }
 143
 144 /**
 145  *      Add an filtering option to the current tree
 146  *      @param expression Current expression to parse
 147  *      @return success/failure of operation
 148  */
 149 gboolean
 150 parse_simple_expression(GString* expression) {
 151
 152         unsigned i;
 153
 154
 155
 156
 157 }
 158
 159 /**
 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
 164  */
 165 lttv_filter_tree*
 166 lttv_filter_new(char *expression, LttvTraceState *tcs) {
 167
 168   g_print("filter::lttv_filter_new()\n");               /* debug */
 169
 170   unsigned
 171     i,
 172     p_nesting=0,        /* parenthesis nesting value */
 173     b=0;        /* current breakpoint in expression string */
 174
 175   /* trees */
 176   lttv_filter_tree
 177     *tree = lttv_filter_tree_new(),   /* main tree */
 178     *subtree = NULL,                  /* buffer for subtrees */
 179     *t1,                              /* buffer #1 */
 180     *t2;                              /* buffer #2 */
 181
 182   /*
 183    * Tree Stack
 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
 189    * the list
 190    */
 191   GPtrArray *tree_stack = g_ptr_array_new();
 192   g_ptr_array_add( tree_stack,(gpointer) tree );
 193
 194   /* temporary values */
 195   GString *a_field_component = g_string_new("");
 196   GPtrArray *a_field_path = NULL;
 197
 198   lttv_simple_expression a_simple_expression;
 199
 200   /*
 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.
 212    *
 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
 229    */
 230
 231   a_field_path = g_ptr_array_new();
 232   g_ptr_array_set_size(a_field_path,2);   /* by default, recording 2 field expressions */
 233
 234
 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]) {
 240       /*
 241        *   logical operators
 242        */
 243       case '&':   /* and */
 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;
 252           subtree = NULL;
 253           t1->right = LTTV_TREE_NODE;
 254           t1->r_child.t = t2;
 255         } else {
 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;
 261           t1->r_child.t = t2;
 262         }
 263
 264         break;
 265       case '|':   /* or */
 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;
 274           subtree = NULL;
 275           t1->right = LTTV_TREE_NODE;
 276           t1->r_child.t = t2;
 277         } else {
 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;
 283           t1->r_child.t = t2;
 284         }
 285         break;
 286       case '^':   /* xor */
 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;
 295           subtree = NULL;
 296           t1->right = LTTV_TREE_NODE;
 297           t1->r_child.t = t2;
 298         } else {
 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;
 304           t1->r_child.t = t2;
 305         }
 306         break;
 307       case '!':   /* not, or not equal (math op) */
 308         if(expression[i+1] == '=') {  /* != */
 309           a_simple_expression.op = LTTV_FIELD_NE;
 310           i++;
 311         } else {  /* ! */
 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;
 320           t1->r_child.t = t2;
 321         }
 322         break;
 323       case '(':   /* start of parenthesis */
 324       case '[':
 325       case '{':
 326         p_nesting++;      /* incrementing parenthesis nesting value */
 327         t1 = lttv_filter_tree_new();
 328         g_ptr_array_add( tree_stack,(gpointer) t1 );
 329         break;
 330       case ')':   /* end of parenthesis */
 331       case ']':
 332       case '}':
 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);
 337           return NULL;
 338         }
 339
 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);
 345               t1 = t1->r_child.t;
 346           }
 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);
 351         } else {
 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);
 361         }
 362         break;
 363
 364       /*
 365        *        mathematic operators
 366        */
 367       case '<':   /* lower, lower or equal */
 368         if(expression[i+1] == '=') { /* <= */
 369           i++;
 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("");
 374         break;
 375       case '>':   /* higher, higher or equal */
 376         if(expression[i+1] == '=') {  /* >= */
 377           i++;
 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("");
 382         break;
 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("");
 387         break;
 388       /*
 389        *  Field concatening caracter
 390        */
 391       case '.':   /* dot */
 392         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
 393         a_field_component = g_string_new("");
 394         break;
 395       default:    /* concatening current string */
 396         g_string_append_c(a_field_component,expression[i]);
 397     }
 398   }
 399
 400   g_print("subtree:%p, tree:%p, t1:%p, t2:%p\n",subtree,tree,t1,t2);
 401
 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;
 409     subtree = NULL;
 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);
 415   }
 416
 417   g_assert(tree != NULL);
 418   g_assert(subtree == NULL);
 419
 420   if( p_nesting>0 ) {
 421     g_warning("Wrong filtering options, the string\n\"%s\"\n\
 422         is not valid due to parenthesis incorrect use",expression);
 423     return NULL;
 424   }
 425
 426   lttv_filter_tracefile(tree,NULL);
 427
 428   return tree;
 429
 430 }
 431
 432 /**
 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
 437  */
 438 gboolean
 439 lttv_filter_tracefile(lttv_filter_tree *filter, LttTracefile *tracefile) {
 440
 441   /*
 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
 446    *
 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 ..
 450    */
 451
 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);
 455   }
 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);
 460
 461   /* test */
 462 /*  int i, nb;
 463   char *f_name, *e_name;
 464
 465   char* field = "cpu";
 466
 467   LttvTraceHook h;
 468
 469   LttEventType *et;
 470
 471   LttType *t;
 472
 473   GString *fe_name = g_string_new("");
 474
 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);
 483   }
 484  */
 485 }
 486
 487 gboolean
 488 lttv_filter_tracestate(lttv_filter_t *filter, LttvTraceState *tracestate) {
 489
 490 }
 491
 492 /**
 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
 497  */
 498 gboolean
 499 lttv_filter_event(lttv_filter_t *filter, LttEvent *event) {
 500
 501 }
 502
 503 /**
 504  *  Initializes the filter module and specific values
 505  */
 506 static void module_init()
 507 {
 508
 509   /*
 510    *  Quarks initialization
 511    *  for hardcoded filtering options
 512    *
 513    *  TODO: traceset has no yet been defined
 514    */
 515
 516   /* top fields */
 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");
 522
 523   /* event.name, tracefile.name, trace.name */
 524   LTTV_FILTER_NAME = g_quark_from_string("name");
 525
 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");
 530
 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");
 541
 542 }
 543
 544 /**
 545  *  Destroys the filter module and specific values
 546  */
 547 static void module_destroy()
 548 {
 549 }
 550
 551
 552 LTTV_MODULE("filter", "Filters traceset and events", \
 553     "Filters traceset and events specifically to user input", \
 554     module_init, module_destroy)
 555
 556
 557