Messages in this thread | | | Date | Mon, 12 Mar 2018 14:38:20 -0400 | From | Steven Rostedt <> | Subject | Re: [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
| |