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   /*
 176    * Main tree & Tree concatening list
 177    * each element of the list
 178    * is a sub tree created
 179    * by the use of parenthesis in the
 180    * global expression.  The final tree
 181    * will be the one created at the root of
 182    * the list
 183    */
 184   lttv_filter_tree* tree = lttv_filter_tree_new();
 185   lttv_filter_tree* subtree = NULL;
 186   GPtrArray *tree_stack = g_ptr_array_new();
 187   g_ptr_array_add( tree_stack,(gpointer) tree );
 188
 189   /* temporary values */
 190   GString *a_field_component = g_string_new("");
 191   GPtrArray *a_field_path = NULL;
 192
 193   lttv_simple_expression a_simple_expression;
 194
 195   /*
 196    *    Parse entire expression and construct
 197    *    the binary tree.  There are two steps
 198    *    in browsing that string
 199    *      1. finding boolean ops " &,|,^,! " and parenthesis " {,(,[,],),} "
 200    *      2. finding simple expressions
 201    *        - field path ( separated by dots )
 202    *        - op ( >, <, =, >=, <=, !=)
 203    *        - value ( integer, string ... )
 204    *    To spare computing time, the whole
 205    *    string is parsed in this loop for a
 206    *    O(n) complexity order.
 207    */
 208
 209   /*
 210    *  When encountering logical op &,|,^
 211    *    1. parse the last value if any
 212    *    2. create a new tree
 213    *    3. add the expression (simple exp, or exp (subtree)) to the tree
 214    *    4. concatenate this tree with the current tree on top of the stack
 215    *  When encountering math ops >,>=,<,<=,=,!=
 216    *    1. add to op to the simple expression
 217    *    2. concatenate last field component to field path
 218    *  When encountering concatening ops .
 219    *    1. concatenate last field component to field path
 220    *  When encountering opening parenthesis (,{,[
 221    *    1. create a new subtree on top of tree stack
 222    *  When encountering closing parenthesis ),},]
 223    *    1. add the expression on right child of the current tree
 224    *    2. the subtree is completed, allocate a new subtree
 225    *    3. pop the tree value from the tree stack
 226    */
 227
 228   a_field_path = g_ptr_array_new();
 229   g_ptr_array_set_size(a_field_path,2);   /* by default, recording 2 field expressions */
 230
 231   lttv_filter_tree *t1, *t2;
 232
 233   for(i=0;i<strlen(expression);i++) {
 234 //    g_print("%s\n",a_field_component->str);
 235     g_print("%c ",expression[i]);
 236     switch(expression[i]) {
 237       /*
 238        *   logical operators
 239        */
 240       case '&':   /* and */
 241         t1 = (lttv_filter_tree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
 242         while(t1->right != LTTV_TREE_UNDEFINED) t1 = t1->r_child.t;
 243         t2 = lttv_filter_tree_new();
 244         t2->node->type = LTTV_EXPRESSION_OP;
 245         t2->node->e.op = LTTV_LOGICAL_AND;
 246         if(subtree != NULL) {
 247           t2->left = LTTV_TREE_NODE;
 248           t2->l_child.t = subtree;
 249           subtree = NULL;
 250           t1->right = LTTV_TREE_NODE;
 251           t1->r_child.t = t2;
 252         } else {
 253           a_simple_expression.value = a_field_component->str;
 254           a_field_component = g_string_new("");
 255           t2->left = LTTV_TREE_LEAF;
 256           t2->l_child.leaf = g_new(lttv_simple_expression,1);
 257           t1->right = LTTV_TREE_NODE;
 258           t1->r_child.t = t2;
 259         }
 260
 261         break;
 262       case '|':   /* or */
 263         break;
 264       case '^':   /* xor */
 265         break;
 266       case '!':   /* not, or not equal (math op) */
 267         if(expression[i+1] == '=') {  /* != */
 268           a_simple_expression.op = LTTV_FIELD_NE;
 269           i++;
 270         } else {  /* ! */
 271           g_print("%s\n",a_field_component);
 272           a_field_component = g_string_new("");
 273         }
 274         break;
 275       case '(':   /* start of parenthesis */
 276       case '[':
 277       case '{':
 278         p_nesting++;      /* incrementing parenthesis nesting value */
 279         lttv_filter_tree* subtree = lttv_filter_tree_new();
 280         g_ptr_array_add( tree_stack,(gpointer) subtree );
 281         break;
 282       case ')':   /* end of parenthesis */
 283       case ']':
 284       case '}':
 285         p_nesting--;      /* decrementing parenthesis nesting value */
 286         if(p_nesting<0 || tree_stack->len<2) {
 287           g_warning("Wrong filtering options, the string\n\"%s\"\n\
 288                      is not valid due to parenthesis incorrect use",expression);
 289           return NULL;
 290         }
 291
 292         g_assert(tree_stack->len>0);
 293         if(subtree != NULL) {
 294           t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
 295           while(t1->right != LTTV_TREE_UNDEFINED && t1->right != LTTV_TREE_LEAF) {
 296               g_assert(t1!=NULL && t1->r_child.t != NULL);
 297               t1 = t1->r_child.t;
 298           }
 299           t1->right = LTTV_TREE_NODE;
 300           t1->r_child.t = subtree;
 301           subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
 302           g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
 303         } else {
 304           a_simple_expression.value = a_field_component->str;
 305           a_field_component = g_string_new("");
 306           t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
 307           while(t1->right != LTTV_TREE_UNDEFINED) t1 = t1->r_child.t;
 308           t1->right = LTTV_TREE_LEAF;
 309           t1->r_child.leaf = g_new(lttv_simple_expression,1);
 310           subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
 311           g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
 312         }
 313       /*  lttv_filter_tree *sub1 = g_ptr_array_index(tree_list,tree_list->len-1);
 314         lttv_filter_tree *sub2 = g_ptr_array_index(tree_list,tree_list->len);
 315         if(sub1->left == LTTV_TREE_UNDEFINED){
 316           sub1->l_child.t = sub2;
 317           sub1->left = LTTV_TREE_NODE;
 318         } else if(sub1->right == LTTV_TREE_UNDEFINED){
 319           sub1->r_child.t = sub2;
 320           sub1->right = LTTV_TREE_NODE;
 321         } else g_error("error during tree assignation");
 322         g_ptr_array_remove_index(tree_list,tree_list->len);
 323         break;
 324         */
 325       //  subtree = g_ptr_array_index(tree_stack,tree_stack->len);
 326       //  g_ptr_array_remove_index(tree_stack,tree_stack->len);
 327         break;
 328
 329       /*
 330        *        mathematic operators
 331        */
 332       case '<':   /* lower, lower or equal */
 333         if(expression[i+1] == '=') { /* <= */
 334           i++;
 335           a_simple_expression.op = LTTV_FIELD_LE;
 336         } else a_simple_expression.op = LTTV_FIELD_LT;
 337         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
 338         a_field_component = g_string_new("");
 339         break;
 340       case '>':   /* higher, higher or equal */
 341         if(expression[i+1] == '=') {  /* >= */
 342           i++;
 343           a_simple_expression.op = LTTV_FIELD_GE;
 344         } else a_simple_expression.op = LTTV_FIELD_GT;
 345         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
 346         a_field_component = g_string_new("");
 347         break;
 348       case '=':   /* equal */
 349         a_simple_expression.op = LTTV_FIELD_EQ;
 350         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
 351         a_field_component = g_string_new("");
 352         break;
 353       /*
 354        *  Field concatening caracter
 355        */
 356       case '.':   /* dot */
 357         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
 358         a_field_component = g_string_new("");
 359         break;
 360       default:    /* concatening current string */
 361         g_string_append_c(a_field_component,expression[i]);
 362     }
 363   }
 364
 365   /*  processing last element of expression   */
 366   g_assert(tree_stack->len==1); /* only root tree should remain */
 367   t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
 368   while(t1->right != LTTV_TREE_UNDEFINED) t1 = t1->r_child.t;
 369   if(subtree != NULL) {  /* add the subtree */
 370     t1->right = LTTV_TREE_NODE;
 371     t1->l_child.t = subtree;
 372     subtree = NULL;
 373   } else {  /* add a leaf */
 374     a_simple_expression.value = a_field_component->str;
 375     a_field_component = g_string_new("");
 376     t1->right = LTTV_TREE_LEAF;
 377     t1->r_child.leaf = g_new(lttv_simple_expression,1);
 378   }
 379
 380   g_assert(tree != NULL);
 381   g_assert(subtree == NULL);
 382
 383   if( p_nesting>0 ) {
 384     g_warning("Wrong filtering options, the string\n\"%s\"\n\
 385         is not valid due to parenthesis incorrect use",expression);
 386     return NULL;
 387   }
 388
 389   return tree;
 390
 391 }
 392
 393 /**
 394  *      Apply the filter to a specific trace
 395  *      @param filter the current filter applied
 396  *      @param tracefile the trace to apply the filter to
 397  *      @return success/failure of operation
 398  */
 399 gboolean
 400 lttv_filter_tracefile(lttv_filter_t *filter, LttTracefile *tracefile) {
 401
 402
 403
 404   /* test */
 405 /*  int i, nb;
 406   char *f_name, *e_name;
 407
 408   char* field = "cpu";
 409
 410   LttvTraceHook h;
 411
 412   LttEventType *et;
 413
 414   LttType *t;
 415
 416   GString *fe_name = g_string_new("");
 417
 418   nb = ltt_trace_eventtype_number(tcs->parent.t);
 419   g_print("NB:%i\n",nb);
 420   for(i = 0 ; i < nb ; i++) {
 421     et = ltt_trace_eventtype_get(tcs->parent.t, i);
 422     e_name = ltt_eventtype_name(et);
 423     f_name = ltt_facility_name(ltt_eventtype_facility(et));
 424     g_string_printf(fe_name, "%s.%s", f_name, e_name);
 425     g_print("facility:%s and event:%s\n",f_name,e_name);
 426   }
 427  */
 428 }
 429
 430 gboolean
 431 lttv_filter_tracestate(lttv_filter_t *filter, LttvTraceState *tracestate) {
 432
 433 }
 434
 435 /**
 436  *      Apply the filter to a specific event
 437  *      @param filter the current filter applied
 438  *      @param event the event to apply the filter to
 439  *      @return success/failure of operation
 440  */
 441 gboolean
 442 lttv_filter_event(lttv_filter_t *filter, LttEvent *event) {
 443
 444 }
 445
 446 /**
 447  *  Initializes the filter module and specific values
 448  */
 449 static void module_init()
 450 {
 451
 452   /*
 453    *  Quarks initialization
 454    *  for hardcoded filtering options
 455    *
 456    *  TODO: traceset has no yet been defined
 457    */
 458
 459   /* top fields */
 460   LTTV_FILTER_EVENT = g_quark_from_string("event");
 461   LTTV_FILTER_TRACE = g_quark_from_string("trace");
 462   LTTV_FILTER_TRACESET = g_quark_from_string("traceset");
 463   LTTV_FILTER_STATE = g_quark_from_string("state");
 464   LTTV_FILTER_TRACEFILE = g_quark_from_string("tracefile");
 465
 466   /* event.name, tracefile.name, trace.name */
 467   LTTV_FILTER_NAME = g_quark_from_string("name");
 468
 469   /* event sub fields */
 470   LTTV_FILTER_CATEGORY = g_quark_from_string("category");
 471   LTTV_FILTER_TIME = g_quark_from_string("time");
 472   LTTV_FILTER_TSC = g_quark_from_string("tsc");
 473
 474   /* state sub fields */
 475   LTTV_FILTER_PID = g_quark_from_string("pid");
 476   LTTV_FILTER_PPID = g_quark_from_string("ppid");
 477   LTTV_FILTER_C_TIME = g_quark_from_string("creation_time");
 478   LTTV_FILTER_I_TIME = g_quark_from_string("insertion_time");
 479   LTTV_FILTER_P_NAME = g_quark_from_string("process_name");
 480   LTTV_FILTER_EX_MODE = g_quark_from_string("execution_mode");
 481   LTTV_FILTER_EX_SUBMODE = g_quark_from_string("execution_submode");
 482   LTTV_FILTER_P_STATUS = g_quark_from_string("process_status");
 483   LTTV_FILTER_CPU = g_quark_from_string("cpu");
 484
 485 }
 486
 487 /**
 488  *  Destroys the filter module and specific values
 489  */
 490 static void module_destroy()
 491 {
 492 }
 493
 494
 495 LTTV_MODULE("filter", "Filters traceset and events", \
 496     "Filters traceset and events specifically to user input", \
 497     module_init, module_destroy)
 498
 499
 500