Google SoC, Optimized netfilter implementation

Google SoC, Optimized netfilter implementation

[Shreyas Bhatewara]

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

Hello folks,

I am a graduate student at Univ of Texas at Dallas. For the Google
Summer of code, I am very much interested in improving netfilter
implementation on Linux. I have worked with iptables (as user) and
Linux kernel (as developer) earlier. Hence, although I do not know how
exactly I can improve the netfilter performance as of now, I think I
am in good position to understand and propose a solution to the
problem during the project.

I am composing a proposal for this project to be submitted at Google
SoC. Could anyone brief me about what you mean by "dynamic code
generation" (https://www.linuxfoundation.org/en/Google_Summer_of_Code_2009#Optimized_netfilter_implementation).
It would be great if you could point me to some document/repository
path which talks about this.

Submitting a proposal requires me to introduce myself on this mailing
list. For details about me, please refer to my resume :
http://utdallas.edu/~shreyas.bhatewara/ResumeShreyasBhatewara.pdf ). I
have been working on Linux/Solaris kernels, C, C++  professionally and
academically for some time now.

Thanking you.
Shreyas N Bhatewara
--
MS Comp Sci, UTD, Aug 2009
BE Computer Engg, PICT, University of Pune.
------
Luck favors them who work hard smartly and I like being lucky :>

[-- Attachment #2: ResumeShreyasBhatewara.pdf --]
[-- Type: application/pdf, Size: 68702 bytes --]

Re: Google SoC, Optimized netfilter implementation

[Jan Engelhardt]

On Wednesday 2009-04-01 04:12, Shreyas Bhatewara wrote:
>
>I am composing a proposal for this project to be submitted at Google
>SoC. Could anyone brief me about what you mean by "dynamic code
>generation" (https://www.linuxfoundation.org/en/Google_Summer_of_Code_2009#Optimized_netfilter_implementation).
>It would be great if you could point me to some document/repository
>path which talks about this.

Umph. Quoting from that page:

"Currently netfilter packet classification is an interpreter that
applies chains of rules to every packet in the system. This can add
thousands of cpu cycles of per packet overhead for a reasonably
simple set of iptables rules.
Dynamic code generation could be used to significantly reduce this
overhead."

It is not as much overhead as one thinks. In fact, Xtables
modules are "hand-crafted" and highly specialized for their task.
They can do something like

	return iph->len >= 256;

in C, which will directly be translated to machine code. On the other
hand, expression based modules like u32 are _much more_ of an
interpreter, as they have to break down

  -m u32 --u32 "0 & 0xFFFF = 0x100:0xFFFF"
	[sic; there seems to be a bug in the u32 manpage
	for testing the layer-3 length.]

i.e. your typical interpreter that loops over tokens and operators
and so on. But see the source of xt_u32.

Sure, dynamic code compilation for expression modules is going to
solve _their_ slowness, but it is not going beyond the specialized
module model that Xtables currently is. You just can't beat the
3 or so ASM instructions emitted on x86 for "iph->len >= 256".

Re: Google SoC, Optimized netfilter implementation

[Stephen Hemminger]

On Tue, 31 Mar 2009 21:12:36 -0500
Shreyas Bhatewara <shreyas.bhatewara@gmail.com> wrote:

> Hello folks,
> 
> I am a graduate student at Univ of Texas at Dallas. For the Google
> Summer of code, I am very much interested in improving netfilter
> implementation on Linux. I have worked with iptables (as user) and
> Linux kernel (as developer) earlier. Hence, although I do not know how
> exactly I can improve the netfilter performance as of now, I think I
> am in good position to understand and propose a solution to the
> problem during the project.
> 
> I am composing a proposal for this project to be submitted at Google
> SoC. Could anyone brief me about what you mean by "dynamic code
> generation" (https://www.linuxfoundation.org/en/Google_Summer_of_Code_2009#Optimized_netfilter_implementation).
> It would be great if you could point me to some document/repository
> path which talks about this.
> 
> Submitting a proposal requires me to introduce myself on this mailing
> list. For details about me, please refer to my resume :
> http://utdallas.edu/~shreyas.bhatewara/ResumeShreyasBhatewara.pdf ). I
> have been working on Linux/Solaris kernels, C, C++  professionally and
> academically for some time now.
> 
> Thanking you.
> Shreyas N Bhatewara
> --
> MS Comp Sci, UTD, Aug 2009
> BE Computer Engg, PICT, University of Pune.
> ------
> Luck favors them who work hard smartly and I like being lucky :>

Have you looked at nftables which is what the architecture netfilter developers
are interested in pursing as the next step?  There are lots of possibilities for
smarter code generation for that.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Google SoC, Optimized netfilter implementation

[Shreyas Bhatewara]

>
> Have you looked at nftables which is what the architecture netfilter developers
> are interested in pursing as the next step?  There are lots of possibilities for
> smarter code generation for that.
>

Stephen,

I looked at nftables. It very much looks like the way to go ahead.

Thank you for your inputs.

->Shreyas
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Google SoC, Optimized netfilter implementation

[Andi Kleen]

Shreyas Bhatewara <shreyas.bhatewara@gmail.com> writes:
>
> I am composing a proposal for this project to be submitted at Google
> SoC. Could anyone brief me about what you mean by "dynamic code
> generation" (https://www.linuxfoundation.org/en/Google_Summer_of_Code_2009#Optimized_netfilter_implementation).


I believe it refers to generate machine code for firewall rules.
So instead of interpreting a data structure the dynamically generated
code would just check the rules directly.

This was done by some kernels before, e.g. OSF/Mach had code to compile
BPF rules into machine code.

Doing something like this would be likely interesting, but I expect
it would be far too much general work for a single SoC. So if you wanted
to do anything like that you would need to select a very narrow doable
subset.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: Google SoC, Optimized netfilter implementation

[Patrick McHardy]

Andi Kleen wrote:
> Shreyas Bhatewara <shreyas.bhatewara@gmail.com> writes:
>> I am composing a proposal for this project to be submitted at Google
>> SoC. Could anyone brief me about what you mean by "dynamic code
>> generation" (https://www.linuxfoundation.org/en/Google_Summer_of_Code_2009#Optimized_netfilter_implementation).
> 
> 
> I believe it refers to generate machine code for firewall rules.
> So instead of interpreting a data structure the dynamically generated
> code would just check the rules directly.
> 
> This was done by some kernels before, e.g. OSF/Mach had code to compile
> BPF rules into machine code.
> 
> Doing something like this would be likely interesting, but I expect
> it would be far too much general work for a single SoC. So if you wanted
> to do anything like that you would need to select a very narrow doable
> subset.

Thomas Graf presented something similar for TC at netconf 2005.
But I'm not sure whether it was ever released.

But I'm not so sure about the benefits. Sure, you can generate
optimized code for the simple cases (lets say, TCP port comparison).
But the impact how much you can gain from this is quite limited
I'd expect, for large rulesets algorithmic improvements have a
much larger potential. Something like hipac should not have to
look at the key for each dimension (port number, address etc.)
more than once, so it pretty much doesn't matter how well optimized
that code is.

Re: Google SoC, Optimized netfilter implementation

[Jesper Dangaard Brouer]

Hi Shreyas,

I would also recommend you to look at the nf-hipac 
project (http://www.hipac.org/), for inspiration.

I also have the masters thesis behind the nf-hipac project.  If you are 
interested I can find it for you...

Hilsen
   Jesper Brouer

--
-------------------------------------------------------------------
MSc. Master of Computer Science
Dept. of Computer Science, University of Copenhagen
Author of http://www.adsl-optimizer.dk
-------------------------------------------------------------------

Re: Google SoC, Optimized netfilter implementation

[Jesper Dangaard Brouer]

On Fri, 3 Apr 2009, Jesper Dangaard Brouer wrote:

> I would also recommend you to look at the nf-hipac project 
> (http://www.hipac.org/), for inspiration.
>
> I also have the masters thesis behind the nf-hipac project.  If you are 
> interested I can find it for you...

Here is the link to the masters thesis by Thomas Heinz,
titled: "HiPAC High Performance Packet Classification for Netfilter"

  http://www.net.t-labs.tu-berlin.de/papers/H-HiPAC-04.pdf

Cheers,
   Jesper Brouer

--
-------------------------------------------------------------------
MSc. Master of Computer Science
Dept. of Computer Science, University of Copenhagen
Author of http://www.adsl-optimizer.dk
-------------------------------------------------------------------

Re: Google SoC, Optimized netfilter implementation

[Shreyas Bhatewara]

On Sun, Apr 5, 2009 at 5:23 PM, Jesper Dangaard Brouer <hawk@diku.dk> wrote:

>
> Here is the link to the masters thesis by Thomas Heinz,
> titled: "HiPAC High Performance Packet Classification for Netfilter"
>
>  http://www.net.t-labs.tu-berlin.de/papers/H-HiPAC-04.pdf
>

Wow ! This would be handy. Thanks a lot Jesper.


->Shreyas
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html