Date: Tue, 22 Oct 2013 16:41:00 +0100 From: Paul "LeoNerd" Evans <leonerd@leonerd.org.uk> To: freebsd-hackers@FreeBSD.org Subject: BPF "loop" instruction to help IPv6 filtering Message-ID: <20131022164100.001122f6@shy.leonerd.org.uk>
next in thread | raw e-mail | index | archive | help
[-- Attachment #1 --]
Hi all,
[I tried this suggestion at Linux a while ago, but was met with
complete silence. Trying my luck here instead hoping I can nudge
support from here first]
BPF deliberately avoids being fully Turing-powerful in order to
guarantee that its filter programs definitely terminate, to ensure
timely handling of packet filtering in the kernel. This is good.
However, I find that trying to filter IPv6 packets means that the
program has to take a number of non-ideal steps that make it less
useful to IPv6.
In contrast to IPv4 packets, IPv6 packets do not have a fixed header
with an area for protocol-level options, followed eventually by the
"upper level" protocol like TCP or UDP at an offset easily calculable
in fixed space. Instead, an IPv6 packet contains a "linked list"
structure, where the overall IPv6 header gives the protocol number of
the "next" protocol on the packet. That will either be TCP/UDP/similar,
or it will be some sort of wrapper header, with its own "next" field.
It is further complicated by each header having its own format, there
not being a standard "next" place to look without understanding the
specific protocol. All very messy.
Anyhow, the current way BPF-using programs have to filter for IPv6 is
to unroll the implied "while" loop this would create a fixed number of
times (e.g. tcpdump usually does 5), and expands the entire skip
program in each unrolling, leading to quite a large amount of code.
I would like to propose a new BPF instruction, "LOOP", which can apply
a limited kind of while() loop to the BPF program, making it easier to
filter on IPv6 packets. It would operate in conjunction with the 'X'
register, in the following way:
LOOP A, label -- add the accumulator to 'X', and jump backwards to
the given instruction if the new value of X is still
shorter than the overall packet length.
LOOP k, label -- add the immediate constant k to X, and jump backwards
as before.
Statically, the program can be checked to ensure that a constant 'k' is
non-zero, and that no instruction alters the value of 'X' between the
LOOP and its target label -- if these checks fail then the program is
rejected. Dynamically while running, if the LOOP A instruction is run
with the accumulator zero, then the program should "RET 0" (similar to
a divide by zero).
I believe these semantics ensure that the program is still guaranteed
to terminate eventually, as each LOOP instruction must make a non-zero
progress to the index, X; and furthermore it cannot proceed further
than the length of the packet.
How this would be used in practice would involve creating a switch-type
block, inspecting the "next protocol" field of the current IPv6 header,
being at the X index. If the type is the required one (e.g. TCP), then
the packet can be accepted (or further tested). If not, then the
switch-type block can increment X according to the size of the header
it is currently looking at, ensuring it now points at the next header
type. This allows an efficient IPv6-parsing program, because it doesn't
have to be loop-unrolled a static number of times, either consuming too
much program space, or lacking the ability to handle deeply-nested
constructs.
Does this sound sane?
--
Paul "LeoNerd" Evans
leonerd@leonerd.org.uk
ICQ# 4135350 | Registered Linux# 179460
http://www.leonerd.org.uk/
[-- Attachment #2 --]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.20 (GNU/Linux)
iF4EAREIAAYFAlJmnIwACgkQ4y9efBOfZ0ihSgD/W2WqvPXP/nBpiyMxPtBFfk/e
nUFRb1SXmJIZ9UtLqR0A/Rk4aDDM9riwxfdHDrQtFeyv5H5s3/0Ko+Q9RWwRL+H4
=9/SL
-----END PGP SIGNATURE-----
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20131022164100.001122f6>