Skip to content
  • Steven Rostedt's avatar
    tracing/filter: Use a tree instead of stack for filter_match_preds() · 61e9dea2
    Steven Rostedt authored
    
    
    Currently the filter_match_preds() requires a stack to push
    and pop the preds to determine if the filter matches the record or not.
    This has two drawbacks:
    
    1) It requires a stack to store state information. As this is done
       in fast paths we can't allocate the storage for this stack, and
       we can't use a global as it must be re-entrant. The stack is stored
       on the kernel stack and this greatly limits how many preds we
       may allow.
    
    2) All conditions are calculated even when a short circuit exists.
       a || b  will always calculate a and b even though a was determined
       to be true.
    
    Using a tree we can walk a constant structure that will save
    the state as we go. The algorithm is simply:
    
      pred = root;
      do {
    	switch (move) {
    	case MOVE_DOWN:
    		if (OR or AND) {
    			pred = left;
    			continue;
    		}
    		if (pred == root)
    			break;
    		match = pred->fn();
    		pred = pred->parent;
    		move = left child ? MOVE_UP_FROM_LEFT : MOVE_UP_FROM_RIGHT;
    		continue;
    
    	case MOVE_UP_FROM_LEFT:
    		/* Only OR or AND can be a parent */
    		if (match && OR || !match && AND) {
    			/* short circuit */
    			if (pred == root)
    				break;
    			pred = pred->parent;
    			move = left child ?
    				MOVE_UP_FROM_LEFT :
    				MOVE_UP_FROM_RIGHT;
    			continue;
    		}
    		pred = pred->right;
    		move = MOVE_DOWN;
    		continue;
    
    	case MOVE_UP_FROM_RIGHT:
    		if (pred == root)
    			break;
    		pred = pred->parent;
    		move = left child ? MOVE_UP_FROM_LEFT : MOVE_UP_FROM_RIGHT;
    		continue;
    	}
    	done = 1;
      } while (!done);
    
    This way there's no strict limit to how many preds we allow
    and it also will short circuit the logical operations when possible.
    
    Cc: Tom Zanussi <tzanussi@gmail.com>
    Signed-off-by: default avatarSteven Rostedt <rostedt@goodmis.org>
    61e9dea2