On Fri, 4 Jul 2025 14:51:06 -0700
Guy Harris <ghar...@sonic.net> wrote:
> In the longer term, the compilation process should probably be split
> into:
>
> a phase that compiles a filter into a target-independent
> *and* link-layer-independent *and* snapshot-length-independent
> intermediate representation, optionally doing whatever optimization
> can be done with that;
>
> a phase that compiles that intermediate representation into
> optionally-optimized code for a particular link layer, snapshot
> length, and target.
A few years ago I noticed that bug reporters and myself sometimes
have to reconstruct the origin of particular BPF instruction manually,
for example,
(000) ldh [12]
(001) jeq #0x800 jt 2 jf 10
(002) ldb [23]
(003) jeq #0x6 jt 4 jf 10
(004) ldh [20]
(005) jset #0x1fff jt 10 jf 6
(006) ldxb 4*([14]&0xf)
(007) ldh [x + 16]
(008) jeq #0x50 jt 9 jf 10
(009) ret #262144
(010) ret #0
after some exercise becomes
(000) ldh [12] ; EtherType
(001) jeq #0x800 jt 2 jf 10 ; IPv4
(002) ldb [23] ; IP protocol
(003) jeq #0x6 jt 4 jf 10 ; TCP
(004) ldh [20] ; IPv4 fragment offset
(005) jset #0x1fff jt 10 jf 6 ; first fragment
(006) ldxb 4*([14]&0xf) ; IPv4 IHL
(007) ldh [x + 16] ; TCP dst port
(008) jeq #0x50 jt 9 jf 10 ; 80
(009) ret #262144
(010) ret #0
(and so on)
After doing this a few times I thought it would be nice to have these
comments generated automatically at the time of the conversion from a
parse tree to BPF instructions (which I presumed was the case). Then I
realised the grammar code generated BPF instructions (using gencode.c)
without an intermediate parse tree, but did not understand why. LBL
developers produced two major designs in this department and it seems
most likely they were aware of parse trees, so it would be useful to
reconstruct the line of thinking that lead to the current tree-less
design and to see how much of it still holds.
One potential reason to consider a parse tree could be implementing
these comments if it would be easier this way. That said, for this
purpose a parse tree may be not strictly necessary: if every function
that generates BPF instructions knew the syntax context (as is
currently done using a separate argument in gen_mac48host(), for
example, or as could be done by making the context a part of
compiler_state_t), it would be possible to use that for both the error
messages and the BPF instruction comments.
However, another reason why the comments would not be easy is that
there is no room for a comment in struct bpf_insn, and struct
bpf_program contains an array of those. A potential way to approach
that would be introducing a new structure that is a superset of
bpf_insn and producing two arrays of instructions in the output
bpf_program: one with the bare 64-bit elements and another
with the same plus debugging information, including the comments. Or
even the additional array could contain the debugging information only
and be of the same size. Then bpf_dump() could de-interleave the two
arrays and produce the annotated form above.
If this works, one of the reasonable things to do would be to avoid
generating the debugging information when it is not required (that is,
in most cases), which could be managed along the following lines:
// This would be PCAP_NO by default.
pcap_setopt(handle, PCAP_DUMP_WITH_COMMENTS, PCAP_YES);
But I digress. Speaking of the parse tree again, it potentially could
also make at least the following optimisations easier:
* eliminating always-true and always-false components from filter
programs, see libpcap issue 1022 for more detail (in fact, the
optimisation proposed there is based on what had been implemented in
RackCode parse tree about 15 years ago) -- this part may possibly be
implementable without a parse tree, I had a look earlier and
identified one obstacle on paper, but didn't prototype any code yet
* pre-computing arithmetic expressions that do not depend on the packet
data before generating any BPF instructions, for example, "2 * 2 = 4"
will always be true for every packet, which the optimiser already
catches, but it would be better not to generate the unnecessary BPF
instructions for that in the first place, and not to consume the BPF
registers; also the optimiser is not always available
One thing that can complicate this is that some always-true and
always-false components are in fact specific to the link-layer type,
for example, "ip" generates:
* always-true for DLT_IPV4
* always-false for DLT_IPV6
* a load and a comparison for DLT_RAW
Also it would be useful before reworking the code generator in major
ways to have it in as good shape as possible, such as:
* no known obvious bugs (documented design quirks allowed)
* as much test coverage as is practicable
* no C code duplication without a good reason
* no BPF instruction duplication without a good reason
* what the C code looks is what it actually does, and vice versa
* no known discrepancies in pcap-filter(7)
Overall the parse tree looks like quite a demanding change.
--
Denis Ovsienko
_______________________________________________
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
