From owner-freebsd-hackers@FreeBSD.ORG Tue Oct 22 15:41:03 2013 Return-Path: Delivered-To: freebsd-hackers@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTP id 05294CDB for ; Tue, 22 Oct 2013 15:41:03 +0000 (UTC) (envelope-from leonerd@leonerd.org.uk) Received: from cel.leonerd.org.uk (cel.leonerd.org.uk [IPv6:2001:8b0:3f7::2]) by mx1.freebsd.org (Postfix) with ESMTP id 8A79F235B for ; Tue, 22 Oct 2013 15:41:02 +0000 (UTC) Received: from shy.leonerd.org.uk (8.9.7.8.3.c.e.f.f.f.2.8.9.a.e.8.3.4.0.0.7.f.3.0.0.b.8.0.1.0.0.2.ip6.arpa [IPv6:2001:8b0:3f7:43:8ea9:82ff:fec3:8798]) by cel.leonerd.org.uk (Postfix) with ESMTPSA id B52A71BDA9 for ; Tue, 22 Oct 2013 16:41:00 +0100 (BST) Date: Tue, 22 Oct 2013 16:41:00 +0100 From: Paul "LeoNerd" Evans To: freebsd-hackers@FreeBSD.org Subject: BPF "loop" instruction to help IPv6 filtering Message-ID: <20131022164100.001122f6@shy.leonerd.org.uk> X-Mailer: Claws Mail 3.9.2 (GTK+ 2.24.21; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: multipart/signed; micalg=PGP-SHA256; boundary="Sig_/1v3qyOWaN0a0N=hGLHIl2Pt"; protocol="application/pgp-signature" X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 22 Oct 2013 15:41:03 -0000 --Sig_/1v3qyOWaN0a0N=hGLHIl2Pt Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable 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.=20 Does this sound sane? --=20 Paul "LeoNerd" Evans leonerd@leonerd.org.uk ICQ# 4135350 | Registered Linux# 179460 http://www.leonerd.org.uk/ --Sig_/1v3qyOWaN0a0N=hGLHIl2Pt Content-Type: application/pgp-signature; name=signature.asc Content-Disposition: attachment; filename=signature.asc -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.20 (GNU/Linux) iF4EAREIAAYFAlJmnIwACgkQ4y9efBOfZ0ihSgD/W2WqvPXP/nBpiyMxPtBFfk/e nUFRb1SXmJIZ9UtLqR0A/Rk4aDDM9riwxfdHDrQtFeyv5H5s3/0Ko+Q9RWwRL+H4 =9/SL -----END PGP SIGNATURE----- --Sig_/1v3qyOWaN0a0N=hGLHIl2Pt--