lkml.org 
[lkml]   [2018]   [Mar]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 3/3] tracing: Rewrite filter logic to be simpler and faster
On Mon, 12 Mar 2018 13:42:46 +0100
Jiri Olsa <jolsa@redhat.com> wrote:

> On Fri, Mar 09, 2018 at 09:34:45PM -0500, Steven Rostedt wrote:
>
> SNIP
>
> >
> > -/* If not of not match is equal to not of not, then it is a match */
> > +/*
> > + * Without going into a formal proof, this explains the method that is used in
> > + * parsing the logical expressions.
> > + *
> > + * For example, if we have: "a && !(!b || (c && g)) || d || e && !f"
> > + * The first pass will convert it into the following program:
> > + *
> > + * n1: r=a; l1: if (!r) goto l4;
> > + * n2: r=b; l2: if (!r) goto l4;
>
> got stuck in here.. should that be 'goto l5' ?

Nope, this is correct. In fact, my user space implementation of the
code is what generated this output.

!(!b || (c && g)) is the same as (b && (!c || !g)), so we can rewrite
the above as:

a && b && (!c || !g) || d || e && !f

Which makes it more obvious why it is goto l4.

And since we have:

n1: r=a; l1: if (!r) goto l4;
n2: r=b; l2: if (!r) goto l4;
n3: r=c; r=!r; l3: if (r) goto l4;
n4: r=g; r=!r; l4: if (r) goto l5;
n5; r=d; l5: if (r) goto T;

If a is true, if (!r) is false so we continue to n2.
If b is false, then if (!r) is true, so we take the branch. Let's see
what that does:

l4: if (r) goto l5;

But since we jumped because r is false, then this if statement is
guaranteed to be false, and we continue to n5. Then we need to test d.

a && b && ... || d

You can see how that is correct. If a is true and then be is false,
then we ignore the rest of the && statement and jump to testing the
other side of || which is d.

-- Steve

>
> jirka
>
> > + * n3: r=c; r=!r; l3: if (r) goto l4;
> > + * n4: r=g; r=!r; l4: if (r) goto l5;
> > + * n5: r=d; l5: if (r) goto T
> > + * n6: r=e; l6: if (!r) goto l7;
> > + * n7: r=f; r=!r; l7: if (!r) goto F
> > + * T: return TRUE
> > + * F: return FALSE
>
> jirka

\
 
 \ /
  Last update: 2018-03-12 19:39    [W:0.251 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site