SFQ hash question

SFQ hash question

[Julien Vehent]

Hi there,

Since LARTC is down, I believe the best place to ask traffic control
questions is here.
I hope you guys won't mind...

I was reading the code of SFQ, and since I'm no C expert I don't
understand exactly on what the hash is computed:


-------
static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
{
	u32 h, h2;

	switch (skb->protocol) {
	case htons(ETH_P_IP):
	{
		const struct iphdr *iph = ip_hdr(skb);
		h = iph->daddr;
		h2 = iph->saddr ^ iph->protocol;
		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
		    (iph->protocol == IPPROTO_TCP ||
		     iph->protocol == IPPROTO_UDP ||
		     iph->protocol == IPPROTO_UDPLITE ||
		     iph->protocol == IPPROTO_SCTP ||
		     iph->protocol == IPPROTO_DCCP ||
		     iph->protocol == IPPROTO_ESP))
			h2 ^= *(((u32*)iph) + iph->ihl);
		break;
	}
------

OK for "h" and h2" before the "if", but what does this "if
(!(iph->frag_off&htons(IP_MF|IP_OFFSET))" really does?

And, also, I'm not sure about this: "h2 ^= *(((u32*)iph) + iph->ihl);"

Does it XOR h2 with the first 32 bits of the L4 protocol header ?


Thanks,
Julien

Re: SFQ hash question

[Julien Vehent]

On Fri, 11 Sep 2009 15:50:45 +0200, Julien Vehent <julien@linuxwall.info>
wrote:
> Hi there,
> 
> Since LARTC is down, I believe the best place to ask traffic control
> questions is here.
> I hope you guys won't mind...
> 
> I was reading the code of SFQ, and since I'm no C expert I don't
> understand exactly on what the hash is computed:
> 
> 
> -------
> static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
> {
> 	u32 h, h2;
> 
> 	switch (skb->protocol) {
> 	case htons(ETH_P_IP):
> 	{
> 		const struct iphdr *iph = ip_hdr(skb);
> 		h = iph->daddr;
> 		h2 = iph->saddr ^ iph->protocol;
> 		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
> 		    (iph->protocol == IPPROTO_TCP ||
> 		     iph->protocol == IPPROTO_UDP ||
> 		     iph->protocol == IPPROTO_UDPLITE ||
> 		     iph->protocol == IPPROTO_SCTP ||
> 		     iph->protocol == IPPROTO_DCCP ||
> 		     iph->protocol == IPPROTO_ESP))
> 			h2 ^= *(((u32*)iph) + iph->ihl);
> 		break;
> 	}
> ------
> 
> OK for "h" and h2" before the "if", but what does this "if
> (!(iph->frag_off&htons(IP_MF|IP_OFFSET))" really does?
> 
> And, also, I'm not sure about this: "h2 ^= *(((u32*)iph) + iph->ihl);"
> 
> Does it XOR h2 with the first 32 bits of the L4 protocol header ?
> 

Sorry for the noise... just read the man page and it's actually explained
there.

-----
On enqueueing, each packet is assigned to a hash bucket, based on
(i)   Source address
(ii)  Destination address
(iii) Source port
If these are available. SFQ knows about ipv4 and ipv6 and also UDP, TCP
and ESP. Packets with other protocols are hashed based on the 32bits
representation of their destination and the socket they belong to. A flow
corresponds mostly to a TCP/IP connection.
-----


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

Re: SFQ hash question

[Michal Soltys]

Julien Vehent wrote:
> 
> OK for "h" and h2" before the "if", but what does this "if
> (!(iph->frag_off&htons(IP_MF|IP_OFFSET))" really does?
> 

It checks whenever the packet is not a fragment. htons(IP_MF|IP_OFFSET) 
functions as a mask which is and'ed with frag_off (which covers both fragment 
offset and "more fragments" flag).

> And, also, I'm not sure about this: "h2 ^= *(((u32*)iph) + iph->ihl);"
> 
> Does it XOR h2 with the first 32 bits of the L4 protocol header ?
> 

Yes. Excluding ESP, it basically means source and destination port (if L3's payload 
is not a fragment, thus the previous test).

Btw - if you need better control of what contributes to hash used by sfq, check out 
flow filter:

http://marc.info/?l=linux-netdev&m=120180241422360&w=2

Re: SFQ hash question

[Julien Vehent]

On Fri, 11 Sep 2009 17:45:40 +0200, Michal Soltys <soltys@ziu.info> wrote:
> Julien Vehent wrote:
>> Hey Michal,
>> 
>> 
>> OK, so I believe the man page I read was not up to date.
>> 
>> http://linux.die.net/man/8/tc-sfq
>> 
>> As it been updated? Where can I find the last version?
>> 
> 
> A lot of man pages from iproute2 is not updated or documentation doesn't

> exist in the first place (u32, sfq, flow, hfsc, and many more) :)
> 
> Commandline help is usually more up to date.

You are giving me lots of homework for the week end :)

One theoritical question: imagine I would like to give a hand on the man
pages, who should I contact?

Re: SFQ hash question

[Michal Soltys]

Julien Vehent wrote:
> 
> One theoritical question: imagine I would like to give a hand on the man
> pages, who should I contact?
> 

Well, the maintainer of respective utility/ies + proper devel mailing list. 
Note, that tc, ip, ss - things related to iproute2 in general - belong to netdev, 
not netfilter-devel. Similary user questions about iproute2 -> net, not netfilter. 
AFAIK. Don't remove CC entries either.


As for docs in general, be sure to peek over:


http://www.linuxfoundation.org/en/Net
http://ace-host.stuart.id.au/russell/files/tc/doc/
http://b42.cz/notes/u32_classifier/
http://www.stearns.org/doc/iptables-u32.v0.1.7.html (note that negative offsets don't work though)
http://jengelh.medozas.de/images/nf-packet-flow.png
http://marc.info/?l=lartc&m=117569441229800&w=2 (basic matches)
http://marc.info/?l=linux-netdev&m=120180241422360&w=2 (external hashing, for sfq mainly)
doc subdirectory of iproute2
Documentation[/networking] subdirectory of kernel tree
book: "Understanding Linux Network Internals"
http://www.policyrouting.org/PolicyRoutingBook/ONLINE/TOC.html
http://www.cs.cmu.edu/~istoica/hfsc-tr.ps.gz
  ( depending on gs version, you might need: sed "s|\[FontBBox\]|/FontBBox load |" )
http://www.sonycsl.co.jp/~kjc/software/TIPS.txt (*BSD oriented, still interesting tidbits)


Some of the above will feel pretty heavy.