netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* RFC: New BGF 'LOOP' instruction
@ 2010-08-02 11:03 Paul LeoNerd Evans
  2010-08-02 11:13 ` RFC: New BPF " Paul LeoNerd Evans
                   ` (2 more replies)
  0 siblings, 3 replies; 26+ messages in thread
From: Paul LeoNerd Evans @ 2010-08-02 11:03 UTC (permalink / raw)
  To: netdev

[-- Attachment #1: Type: text/plain, Size: 2670 bytes --]

---
 Proposal: Create a new BPF instruction, "LOOP", which can implement a
   specific time-bounded kind of while() loop over packet contents
---

IPv6 packets contain a linked-list of headers. Some other network
protocols may also contain linked-list structure.

BPF cannot implement loops.

Currently therefore, it is impossible to efficiently parse IPv6 packets
without resorting to such annoying tricks as statically unrolling a loop
into a long list of instructions. In IPv6's case this gets very large
very quickly, as different header types have different lengths, or
structure layouts.

I propose to add a new instruction, "LOOP", with the following
semantics:

 BPF_JMP|BPF_LOOP, jt

    If A == 0, fallthrough to the next instruction.
      (TODO: Or perhaps this should be considered a hard error which
       immediately aborts the filter, similar to divide by zero?)
    Otherwise:
       X += A.
       If X < len, jump backwards jt instructions.
       Otherwise, fallthrough to the next instruction

The following static checks would be enforced:

 None of the 'jt' preceeding instructions before the LOOP instruction
 (i.e. the body of the loop) may themselves be LOOP instructions, nor may
 they be STX.

The intention of this instruction is to be able to implement a loop in
which successive iterations advance the index register along the packet
buffer. By comparing X to the packet length, we can bound the running
time of the loop instruction, avoiding it locking up the kernel. By
banning STX instructions within the body of the loop, we can ensure that
X must be a strictly monotonically increasing sequence. At absolute
worst, X is increased by 1 each time, meaning at worst the body of the
loop must execute for every byte in the packet. By banning further
nested LOOP instructions, we can ensure at worst a linear running time.


I believe this addition should have minimal impact on existing users of
the filter layer, as it simply adds a new instruction and does not
otherwise change the semantics of any existing code. I also believe it
to be useful in writing filters that process IPv6 packets. I also
believe that the semantics and static checks are sufficient to preserve
the termination guarantee of BPF filter programs, ensuring each packet's
fate is decided in a timely fashion to avoid locking up the kernel.

Any comments on this, while I proceed? Barring any major complaints,
I'll have a hack at some code and present a patch in due course...

-- 
Paul "LeoNerd" Evans

leonerd@leonerd.org.uk
ICQ# 4135350       |  Registered Linux# 179460
http://www.leonerd.org.uk/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

^ permalink raw reply	[flat|nested] 26+ messages in thread

end of thread, other threads:[~2010-08-03 15:28 UTC | newest]

Thread overview: 26+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-08-02 11:03 RFC: New BGF 'LOOP' instruction Paul LeoNerd Evans
2010-08-02 11:13 ` RFC: New BPF " Paul LeoNerd Evans
2010-08-02 20:16 ` RFC: New BGF " Hagen Paul Pfeifer
2010-08-03  5:18   ` David Miller
2010-08-03  7:07     ` Paul LeoNerd Evans
2010-08-03  7:19       ` David Miller
2010-08-03  9:10         ` Hagen Paul Pfeifer
2010-08-03 13:40           ` Paul LeoNerd Evans
2010-08-03  9:03     ` Hagen Paul Pfeifer
2010-08-03  7:18   ` RFC: New BPF " Paul LeoNerd Evans
2010-08-03  5:13 ` RFC: New BGF " David Miller
2010-08-03  7:04   ` Paul LeoNerd Evans
2010-08-03  7:18     ` David Miller
2010-08-03 12:58       ` Andi Kleen
2010-08-03 13:07         ` David Miller
2010-08-03 13:34           ` RFC: New BPF " Paul LeoNerd Evans
2010-08-03 13:42             ` Paul LeoNerd Evans
2010-08-03 14:09             ` Rémi Denis-Courmont
2010-08-03 14:13               ` Paul LeoNerd Evans
2010-08-03 14:16                 ` Rémi Denis-Courmont
2010-08-03 14:19                   ` Paul LeoNerd Evans
2010-08-03 15:17                     ` Rémi Denis-Courmont
2010-08-03 15:27                       ` Paul LeoNerd Evans
2010-08-03 14:05           ` RFC: New BGF " Andi Kleen
2010-08-03 14:11             ` Paul LeoNerd Evans
2010-08-03 14:34               ` Paul LeoNerd Evans

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).