On Jul 8, 2025, at 7:58 AM, Denis Ovsienko <de...@ovsienko.info> wrote:
> On Mon, 7 Jul 2025 13:26:25 -0700
> Guy Harris <ghar...@sonic.net> wrote:
>
>> There could probably be a bunch of optimizations done to programs in
>> that IR.
>
> The parse tree, as a means of data handover between layers, would be an
> encoding.
If by "layers" you're referring to the "parse this filter expression without
taking the link-layer type into account" API and the "generate cBPF/eBPF code"
API, an abstract syntax tree is one possible encoding; others might be, for
example, a sequence of "operation, source 1, source 2, destination" quads,
including conditional branch operations (think of it as a higher-level
link-layer type and target-independent code, similar to the cBPF DAG we
currently use internally).
It may be that some manipulations are more easily done on a parse tree - at one
point, I thought of a way of handling "vlan"/"mils"/etc. in a fashion that
makes the modified packet offset apply *only* to code that's run if the vlan
test succeeds, so that, for example
(vlan and ip) or iso protocol clnp
doesn't, when "vlan" fails, end up looking at the wrong place in the packet
when testing for a *non*-VLAN CLNP packet, and thought that perhaps attaching
an "updated offset" tag to the right-hand branch, in the parse tree, of an
"and" with a "vlan" expression as the left-hand branch:
(or)
/ \
(and) (iso protocol clnp)
/ \
vlan (ip, but 4 bytes later)
would do the trick. A quad-style IR:
0: test-link-protocol-type VLAN
1: if-match 2, 5
2: advance-offset-for-link-protocol-type 4
3: test-link-protocol-type IP
4: if-match 9, 5
5: test-link-protocol-type ISO
6: if-match 7, 10
7: test-iso-protocol-type CLNP
8: if-match 9, 10
9: succeed
10: fail
might take more work to decorate with the advance-offset-for-link-protocol-type
operation.
> To make it possible to test the algorithms that
> produce/consume this encoding, it would be necessary to have means of
> serializing/deserializing the parse tree using some text form, then the
> following test types would become possible:
>
> 1. Does this filter expression translate to this parse tree?
> 2. Does this parse tree become that parse tree after this optimisation?
> 3. Does this parse tree become this BPF program after this translation?
That's independent of the representation; the same could be done for other
intermediate representations.
_______________________________________________
tcpdump-workers mailing list -- tcpdump-workers@lists.tcpdump.org
To unsubscribe send an email to tcpdump-workers-le...@lists.tcpdump.org
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
