Netfiltering - NF_IP_LOCAL_OUT - how it works???

Netfiltering - NF_IP_LOCAL_OUT - how it works???

[Vishwas Raman]

Hi,

I am working with the 2.4.20 kernel.

The module I am writing is supposed to intercept all outgoing packets 
passing between the TCP and IP layer. I was trying to use the 
netfiltering mechanism for that purpose.

While initializing the module, I register a NF_IP_LOCAL_OUT hook for the 
outgoing packet and change skb->dst->output to my_ip_output() instead of 
ip_output() in that hook function. After loading the module, I see 
control being transferred to my_ip_output() for all outgoing packets 
which in turn calls ip_output() and everything seems to work well.

The exit function of the module also unregisters the hook that I am using.

The problem is that after I unload the module, which in turn unregisters 
the hook, I have a kernel panic happening each time I use TCP.

The panic occurs at the following point, ip_build_and_send_pkt() in 
ip_output.c where it is trying to call

     NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, skb, NULL, rt->u.dst.dev,
                     output_maybe_reroute);

I thought once the unregistering of the hook is done, it no longer looks 
for that hook function. I have no idea why it is failing. May be I am 
doing something grossly wrong with netfiltering. Anyone who is familiar 
with netfiltering and has registered and unregistered hooks before might 
be able to guide me regarding this.

Any help will be appreciated.

Thanks,

-Vishwas.

Re: Netfiltering - NF_IP_LOCAL_OUT - how it works???

[Harald Welte]

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

Hi Vishwas, sorry for the late reply.  Most netfilter developers have
been to the netfilter developer workshop, I guess.

you should ask this question on the netfilter-devel mailinglist, where
it is more on-topic than on lkml.

On Thu, Aug 14, 2003 at 03:06:26PM -0700, Vishwas Raman wrote:

> While initializing the module, I register a NF_IP_LOCAL_OUT hook for the 
> outgoing packet and change skb->dst->output to my_ip_output() instead of 
> ip_output() in that hook function. After loading the module, I see 
> control being transferred to my_ip_output() for all outgoing packets 
> which in turn calls ip_output() and everything seems to work well.
> 
> The exit function of the module also unregisters the hook that I am using.
> 
> The problem is that after I unload the module, which in turn unregisters 
> the hook, I have a kernel panic happening each time I use TCP.
> 
> The panic occurs at the following point, ip_build_and_send_pkt() in 
> ip_output.c where it is trying to call
> 
>     NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, skb, NULL, rt->u.dst.dev,
>                     output_maybe_reroute);
> 
> I thought once the unregistering of the hook is done, it no longer looks 
> for that hook function. I have no idea why it is failing. May be I am 
> doing something grossly wrong with netfiltering. Anyone who is familiar 
> with netfiltering and has registered and unregistered hooks before might 
> be able to guide me regarding this.

I think either you are doing something wrong while unregistering from
the netfilter hook - or you are running into a race condition.  It might
happen, that you assign the skb->dst->output function of a packet to
your function, and then you remove the module before that packet is
actually sent.

> -Vishwas.

-- 
- Harald Welte <laforge@gnumonks.org>               http://www.gnumonks.org/
============================================================================
Programming is like sex: One mistake and you have to support it your lifetime

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

Re: Netfiltering - NF_IP_LOCAL_OUT - how it works???

[Vishwas Raman]

Harald Welte wrote:
> Hi Vishwas, sorry for the late reply.  Most netfilter developers have
> been to the netfilter developer workshop, I guess.
> 
> you should ask this question on the netfilter-devel mailinglist, where
> it is more on-topic than on lkml.
> 
> On Thu, Aug 14, 2003 at 03:06:26PM -0700, Vishwas Raman wrote:
> 
> 
>>While initializing the module, I register a NF_IP_LOCAL_OUT hook for the 
>>outgoing packet and change skb->dst->output to my_ip_output() instead of 
>>ip_output() in that hook function. After loading the module, I see 
>>control being transferred to my_ip_output() for all outgoing packets 
>>which in turn calls ip_output() and everything seems to work well.
>>
>>The exit function of the module also unregisters the hook that I am using.
>>
>>The problem is that after I unload the module, which in turn unregisters 
>>the hook, I have a kernel panic happening each time I use TCP.
>>
>>The panic occurs at the following point, ip_build_and_send_pkt() in 
>>ip_output.c where it is trying to call
>>
>>    NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, skb, NULL, rt->u.dst.dev,
>>                    output_maybe_reroute);
>>
>>I thought once the unregistering of the hook is done, it no longer looks 
>>for that hook function. I have no idea why it is failing. May be I am 
>>doing something grossly wrong with netfiltering. Anyone who is familiar 
>>with netfiltering and has registered and unregistered hooks before might 
>>be able to guide me regarding this.
> 
> 
> I think either you are doing something wrong while unregistering from
> the netfilter hook - or you are running into a race condition.  It might
> happen, that you assign the skb->dst->output function of a packet to
> your function, and then you remove the module before that packet is
> actually sent.

Actually I did solve the problem. All I had to do was reset 
skb->dst->output() to ip_output() in my_ip_output() which is defined in 
my module. The problem was that even after my module was unloaded the 
destination cache was still pointing to my_ip_output() which was 
non-existent...

Thanks,

-Vishwas.




> 
> 
>>-Vishwas.
> 
> 



-- 
--
Vishwas Raman
Software Engineer, Eternal Systems, Inc,
5290 Overpass Rd, Bldg D, Santa Barbara. CA 93111
Email: vishwas@eternal-systems.com
Tel:   (805) 696-9051 x246
Fax:   (805) 696-9083
URL:   http://www.eternal-systems.com/

Incremental update of TCP Checksum

[Vishwas Raman]

Hi all,

I have a very simple question, which a lot of you would have solved. I 
am intercepting a TCP packet, which I would like to change slightly.

Let's say, I change the doff field of the tcp-header (for eg: increase 
it by 1). I know it is wrong just to change the doff field without 
increasing the packet length, but lets say I do it just as a test. Since 
I changed a portion of the tcp header, I have to update the tcp checksum 
too right!!! If so, what is the best way to do so, without having to 
recalculate the entire tcp checksum (I know how to recalculate the 
checksum from scratch).

Can anyone out there tell me the algorithm to update the checksum 
without having to recalculate it.

I tried the following algorithm but it didnt work. The packet got 
rejected as a packet with bad cksum.

void changePacket(struct sk_buff* skb)
{
     struct tcphdr *tcpHdr = skb->h.th;
     // Verifying the tcp checksum works here...
     tcpHeader->doff += 1;
     long cksum = (~(tcpHdr->check))&0xffff;
     cksum += 1;
     while (cksum >> 16)
     {
         cksum = (cksum & 0xffff) + (cksum >> 16);
     }
     tcpHeader->check = ~cksum;
     // Verifying tcp checksum here fails with bad cksum
}

Any pointers/help in this regard will be highly appreciated...

Thanks,

-Vishwas.

Re: Incremental update of TCP Checksum

[Valdis.Kletnieks]

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

On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-systems.com>  said:

> Can anyone out there tell me the algorithm to update the checksum 
> without having to recalculate it.

The canonical source is the RFCs:

1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
     Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
     RFC1141) (Status: UNKNOWN)

1141 Incremental updating of the Internet checksum. T. Mallory, A.
     Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
     (Updated by RFC1624) (Status: INFORMATIONAL)

1624 Computation of the Internet Checksum via Incremental Update. A.
     Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
     RFC1141) (Status: INFORMATIONAL)

http://www.ietf.org/rfc/rfc1071.txt
http://www.ietf.org/rfc/rfc1141.txt
http://www.ietf.org/rfc/rfc1624.txt

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

Re: Incremental update of TCP Checksum

[Richard B. Johnson]

On Tue, 16 Sep 2003, Vishwas Raman wrote:

> Hi all,
>
> I have a very simple question, which a lot of you would have solved. I
> am intercepting a TCP packet, which I would like to change slightly.
>
> Let's say, I change the doff field of the tcp-header (for eg: increase
> it by 1). I know it is wrong just to change the doff field without
> increasing the packet length, but lets say I do it just as a test. Since
> I changed a portion of the tcp header, I have to update the tcp checksum
> too right!!! If so, what is the best way to do so, without having to
> recalculate the entire tcp checksum (I know how to recalculate the
> checksum from scratch).
>
> Can anyone out there tell me the algorithm to update the checksum
> without having to recalculate it.
>
> I tried the following algorithm but it didnt work. The packet got
> rejected as a packet with bad cksum.
>
> void changePacket(struct sk_buff* skb)
> {
>      struct tcphdr *tcpHdr = skb->h.th;
>      // Verifying the tcp checksum works here...
>      tcpHeader->doff += 1;
>      long cksum = (~(tcpHdr->check))&0xffff;
>      cksum += 1;
>      while (cksum >> 16)
>      {
>          cksum = (cksum & 0xffff) + (cksum >> 16);
>      }
>      tcpHeader->check = ~cksum;
>      // Verifying tcp checksum here fails with bad cksum
> }
>
> Any pointers/help in this regard will be highly appreciated...

The TCP/IP checksum is a WORD sum (unsigned short) in which
any overflow out of the word causes the word to be incremented.
The final sum is then inverted to become the checksum. Note that
many algorithms sum into a long then fold-back the bits. It's
the same thing, different method.

Therefore:
	Given an existing checksum of 0xffff, if the
	next word to be summed is 0x0001, the result
	will be 0x0001 because adding 1 to 0xffff makes
	it 0, causing an overflow which propagates to
	become 0x0001.
So:
	Clearly, information is lost because one doesn't
	know how the 0x0001 was obtained.

If I were to modify a low byte somewhere by subtracting 1,
would I know that the new checksum, excluding the inversion,
was 0x0000? No. It could be 0xffff.

This presents a problem when trying to modify existing checksums.
It's certainly easier to set the existing checksum to 0, then
re-checksum the whole packet. It's probably faster than some
looping algorithm that attempts to unwind a previous checksum.


Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: Incremental update of TCP Checksum

[Vishwas Raman]

Richard B. Johnson wrote:
> On Tue, 16 Sep 2003, Vishwas Raman wrote:
> 
> 
>>Hi all,
>>
>>I have a very simple question, which a lot of you would have solved. I
>>am intercepting a TCP packet, which I would like to change slightly.
>>
>>Let's say, I change the doff field of the tcp-header (for eg: increase
>>it by 1). I know it is wrong just to change the doff field without
>>increasing the packet length, but lets say I do it just as a test. Since
>>I changed a portion of the tcp header, I have to update the tcp checksum
>>too right!!! If so, what is the best way to do so, without having to
>>recalculate the entire tcp checksum (I know how to recalculate the
>>checksum from scratch).
>>
>>Can anyone out there tell me the algorithm to update the checksum
>>without having to recalculate it.
>>
>>I tried the following algorithm but it didnt work. The packet got
>>rejected as a packet with bad cksum.
>>
>>void changePacket(struct sk_buff* skb)
>>{
>>     struct tcphdr *tcpHdr = skb->h.th;
>>     // Verifying the tcp checksum works here...
>>     tcpHeader->doff += 1;
>>     long cksum = (~(tcpHdr->check))&0xffff;
>>     cksum += 1;
>>     while (cksum >> 16)
>>     {
>>         cksum = (cksum & 0xffff) + (cksum >> 16);
>>     }
>>     tcpHeader->check = ~cksum;
>>     // Verifying tcp checksum here fails with bad cksum
>>}
>>
>>Any pointers/help in this regard will be highly appreciated...
> 
> 
> The TCP/IP checksum is a WORD sum (unsigned short) in which
> any overflow out of the word causes the word to be incremented.
> The final sum is then inverted to become the checksum. Note that
> many algorithms sum into a long then fold-back the bits. It's
> the same thing, different method.
> 
> Therefore:
> 	Given an existing checksum of 0xffff, if the
> 	next word to be summed is 0x0001, the result
> 	will be 0x0001 because adding 1 to 0xffff makes
> 	it 0, causing an overflow which propagates to
> 	become 0x0001.
> So:
> 	Clearly, information is lost because one doesn't
> 	know how the 0x0001 was obtained.
> 
> If I were to modify a low byte somewhere by subtracting 1,
> would I know that the new checksum, excluding the inversion,
> was 0x0000? No. It could be 0xffff.
> 
> This presents a problem when trying to modify existing checksums.
> It's certainly easier to set the existing checksum to 0, then
> re-checksum the whole packet. It's probably faster than some
> looping algorithm that attempts to unwind a previous checksum.

Are you then suggesting that instead of trying to do an incremental 
update of the tcp checksum, I set it to 0 and recalculate it from 
scratch? But I thought that doing that was a big performance hit. Isn't it?

> 
> 
> Cheers,
> Dick Johnson
> Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
>             Note 96.31% of all statistics are fiction.
> 
> 
> 



-- 
--
Vishwas Raman
Software Engineer, Eternal Systems, Inc,
5290 Overpass Rd, Bldg D, Santa Barbara. CA 93111
Email: vishwas@eternal-systems.com
Tel:   (805) 696-9051 x246
Fax:   (805) 696-9083
URL:   http://www.eternal-systems.com/

Re: Incremental update of TCP Checksum

[Vishwas Raman]

Valdis.Kletnieks@vt.edu wrote:
> On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-systems.com>  said:
> 
> 
>>Can anyone out there tell me the algorithm to update the checksum 
>>without having to recalculate it.
> 
> 
> The canonical source is the RFCs:
> 
> 1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
>      Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
>      RFC1141) (Status: UNKNOWN)
> 
> 1141 Incremental updating of the Internet checksum. T. Mallory, A.
>      Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
>      (Updated by RFC1624) (Status: INFORMATIONAL)
> 
> 1624 Computation of the Internet Checksum via Incremental Update. A.
>      Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
>      RFC1141) (Status: INFORMATIONAL)
> 
> http://www.ietf.org/rfc/rfc1071.txt
> http://www.ietf.org/rfc/rfc1141.txt
> http://www.ietf.org/rfc/rfc1624.txt

As mentioned in RFC1624, I did the following.
void changePacket(struct sk_buff* skb)
{
     struct tcphdr *tcpHdr = skb->h.th;

     // Verifying the tcp checksum works here...

     __u16 oldDoff = tcpHeader->doff;
     tcpHeader->doff += 1;	

     // Formula from RFC1624 is HC' = ~(C + (-m) + m')
     // where HC  - old checksum in header
     // C   - one's complement sum of old header
     // HC' - new checksum in header
     // C'  - one's complement sum of new header
     // m   - old value of a 16-bit field
     // m'  - new value of a 16-bit field

     long cksum = (~(tcpHdr->check))&0xffff;
     cksum += (__u16)~oldDoff;
     cksum += tcpHeader->doff;
     while (cksum >> 16)
     {
         cksum = (cksum & 0xffff) + (cksum >> 16);
     }
     tcpHeader->check = ~cksum;

     // Verifying tcp checksum here fails with bad cksum
}

Is there any glaring mistake in the above code. If so, can someone
please let me know what it is. It will be of great help.

Thanks,

-Vishwas.

Re: Incremental update of TCP Checksum

[Patrick McHardy]

Vishwas Raman wrote:

> Can anyone out there tell me the algorithm to update the checksum 
> without having to recalculate it. 


Have a look at net/ipv4/netfilter/ipt_TCPMSS.c (cheat_check).

Regards,
Patrick

Re: Incremental update of TCP Checksum

[Richard B. Johnson]

On Tue, 16 Sep 2003, Vishwas Raman wrote:

>
> Richard B. Johnson wrote:
> > On Tue, 16 Sep 2003, Vishwas Raman wrote:
> >
> >
> >>Hi all,
> >>
> >>I have a very simple question, which a lot of you would have solved. I
> >>am intercepting a TCP packet, which I would like to change slightly.
> >>
> >>Let's say, I change the doff field of the tcp-header (for eg: increase
> >>it by 1). I know it is wrong just to change the doff field without
> >>increasing the packet length, but lets say I do it just as a test. Since
> >>I changed a portion of the tcp header, I have to update the tcp checksum
> >>too right!!! If so, what is the best way to do so, without having to
> >>recalculate the entire tcp checksum (I know how to recalculate the
> >>checksum from scratch).
> >>
> >>Can anyone out there tell me the algorithm to update the checksum
> >>without having to recalculate it.
> >>
> >>I tried the following algorithm but it didnt work. The packet got
> >>rejected as a packet with bad cksum.
> >>
> >>void changePacket(struct sk_buff* skb)
> >>{
> >>     struct tcphdr *tcpHdr = skb->h.th;
> >>     // Verifying the tcp checksum works here...
> >>     tcpHeader->doff += 1;
> >>     long cksum = (~(tcpHdr->check))&0xffff;
> >>     cksum += 1;
> >>     while (cksum >> 16)
> >>     {
> >>         cksum = (cksum & 0xffff) + (cksum >> 16);
> >>     }
> >>     tcpHeader->check = ~cksum;
> >>     // Verifying tcp checksum here fails with bad cksum
> >>}
> >>
> >>Any pointers/help in this regard will be highly appreciated...
> >
> >
> > The TCP/IP checksum is a WORD sum (unsigned short) in which
> > any overflow out of the word causes the word to be incremented.
> > The final sum is then inverted to become the checksum. Note that
> > many algorithms sum into a long then fold-back the bits. It's
> > the same thing, different method.
> >
> > Therefore:
> > 	Given an existing checksum of 0xffff, if the
> > 	next word to be summed is 0x0001, the result
> > 	will be 0x0001 because adding 1 to 0xffff makes
> > 	it 0, causing an overflow which propagates to
> > 	become 0x0001.
> > So:
> > 	Clearly, information is lost because one doesn't
> > 	know how the 0x0001 was obtained.
> >
> > If I were to modify a low byte somewhere by subtracting 1,
> > would I know that the new checksum, excluding the inversion,
> > was 0x0000? No. It could be 0xffff.
> >
> > This presents a problem when trying to modify existing checksums.
> > It's certainly easier to set the existing checksum to 0, then
> > re-checksum the whole packet. It's probably faster than some
> > looping algorithm that attempts to unwind a previous checksum.
>
> Are you then suggesting that instead of trying to do an incremental
> update of the tcp checksum, I set it to 0 and recalculate it from
> scratch? But I thought that doing that was a big performance hit.
> Isn't it?
>

I would just do it. No TCP/IP checksum is a "big performance hit".
An ordinary 'C' procedure does it in about 1.3 CPU clocks/byte.
The ASM checksum routine does it in about 0.54 CPU clocks/byte.
This is basically the time necessary to access memory.

Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: Incremental update of TCP Checksum

[Jesper Juhl]

On Tue, 16 Sep 2003, Vishwas Raman wrote:

>
> Richard B. Johnson wrote:
> > On Tue, 16 Sep 2003, Vishwas Raman wrote:
> >
> >
> >>Hi all,
> >>
> >>I have a very simple question, which a lot of you would have solved. I
> >>am intercepting a TCP packet, which I would like to change slightly.
> >>
> >>Let's say, I change the doff field of the tcp-header (for eg: increase
> >>it by 1). I know it is wrong just to change the doff field without
> >>increasing the packet length, but lets say I do it just as a test. Since
> >>I changed a portion of the tcp header, I have to update the tcp checksum
> >>too right!!! If so, what is the best way to do so, without having to
> >>recalculate the entire tcp checksum (I know how to recalculate the
> >>checksum from scratch).
> >>
> >
> > The TCP/IP checksum is a WORD sum (unsigned short) in which
> > any overflow out of the word causes the word to be incremented.
> > The final sum is then inverted to become the checksum. Note that
> > many algorithms sum into a long then fold-back the bits. It's
> > the same thing, different method.
> >
> > Therefore:
> > 	Given an existing checksum of 0xffff, if the
> > 	next word to be summed is 0x0001, the result
> > 	will be 0x0001 because adding 1 to 0xffff makes
> > 	it 0, causing an overflow which propagates to
> > 	become 0x0001.
> > So:
> > 	Clearly, information is lost because one doesn't
> > 	know how the 0x0001 was obtained.
> >
> > If I were to modify a low byte somewhere by subtracting 1,
> > would I know that the new checksum, excluding the inversion,
> > was 0x0000? No. It could be 0xffff.
> >
> > This presents a problem when trying to modify existing checksums.
> > It's certainly easier to set the existing checksum to 0, then
> > re-checksum the whole packet. It's probably faster than some
> > looping algorithm that attempts to unwind a previous checksum.
>
> Are you then suggesting that instead of trying to do an incremental
> update of the tcp checksum, I set it to 0 and recalculate it from
> scratch? But I thought that doing that was a big performance hit. Isn't it?
>
Personally I can't see that you have any other option. The way the
checksum is calculated information is lost, so it's impossible to
determine exactely what input generated the current output (the checksum).
Just as it is impossible to tell if the number 6 was generated from 2+2+2,
from 3*2 or from 3+3 or some other...  So I don't see what else you can do
except just recalculate the checksum from scratch. To try and determine
how your modification would affect the checksum would probably take far
longer than just re-calculating it.


- Jesper Juhl <jju@dif.dk>

Re: Incremental update of TCP Checksum

[Leo Mauro]

On Tuesday 16 September 2003 04:32 pm, Vishwas Raman wrote:

> As mentioned in RFC1624, I did the following.
> void changePacket(struct sk_buff* skb)
> {
>      struct tcphdr *tcpHdr = skb->h.th;
>
>      // Verifying the tcp checksum works here...
>
>      __u16 oldDoff = tcpHeader->doff;
>      tcpHeader->doff += 1;
>
>      // Formula from RFC1624 is HC' = ~(C + (-m) + m')
>      // where HC  - old checksum in header
>      // C   - one's complement sum of old header
>      // HC' - new checksum in header
>      // C'  - one's complement sum of new header
>      // m   - old value of a 16-bit field
>      // m'  - new value of a 16-bit field
>
>      long cksum = (~(tcpHdr->check))&0xffff;
>      cksum += (__u16)~oldDoff;
                       ^  should be a -

>      cksum += tcpHeader->doff;
>      while (cksum >> 16)
>      {
>          cksum = (cksum & 0xffff) + (cksum >> 16);
>      }
>      tcpHeader->check = ~cksum;
>
>      // Verifying tcp checksum here fails with bad cksum
> }

-- 
Leo Mauro
Network Security
Simon Bolivar University
Caracas, Venezuela

Re: Incremental update of TCP Checksum

[Jamie Lokier]

Richard B. Johnson wrote:
>If I were to modify a low byte somewhere by subtracting 1,
>would I know that the new checksum, excluding the inversion,
>was 0x0000? No. It could be 0xffff.

You're right about information being thrown away, but wrong because IP
checksums are more rigidly defined than that.

RFC1624 was written because the earlier RFC actually got this wrong.

As long as at least one of the checksummed words is known to be
non-zero, 0x0000 is not a possible value.  This is true of all IP checksums.

There is only one possible value of the non-complemented sum: 0xffff.

So when you subtract 1 from 0x0001, you get 0xffff.

To do this right, instead of subtracting a word, you add the
complement of the word.  After carry-folding, this works out right.

Vishwas Raman wrote:
> Are you then suggesting that instead of trying to do an incremental 
> update of the tcp checksum, I set it to 0 and recalculate it from 
> scratch? But I thought that doing that was a big performance hit. Isn't it?

You don't need to recalculate the sum.  All routers modify the IP
header checksum when they decrement the TTL of a packet - it's a
widely used algorithm.  Equation 3 from RFC1624 is correct :)

Your code looks fine to me.  Are you sure you're verifying the
checksum correctly?

>     while (cksum >> 16)
>     {
>         cksum = (cksum & 0xffff) + (cksum >> 16);
>     }

In general you need to add back the carry bits at most twice, btw.

	cksum = (cksum & 0xffff) + (cksum >> 16);
	cksum += (cksum >> 16);

-- Jamie

Re: Incremental update of TCP Checksum

[Vishwas Raman]

Jamie Lokier wrote:
> Richard B. Johnson wrote:
> 
>>If I were to modify a low byte somewhere by subtracting 1,
>>would I know that the new checksum, excluding the inversion,
>>was 0x0000? No. It could be 0xffff.
> 
> 
> You're right about information being thrown away, but wrong because IP
> checksums are more rigidly defined than that.
> 
> RFC1624 was written because the earlier RFC actually got this wrong.
> 
> As long as at least one of the checksummed words is known to be
> non-zero, 0x0000 is not a possible value.  This is true of all IP checksums.
> 
> There is only one possible value of the non-complemented sum: 0xffff.
> 
> So when you subtract 1 from 0x0001, you get 0xffff.
> 
> To do this right, instead of subtracting a word, you add the
> complement of the word.  After carry-folding, this works out right.
> 
> Vishwas Raman wrote:
> 
>>Are you then suggesting that instead of trying to do an incremental 
>>update of the tcp checksum, I set it to 0 and recalculate it from 
>>scratch? But I thought that doing that was a big performance hit. Isn't it?
> 
> 
> You don't need to recalculate the sum.  All routers modify the IP
> header checksum when they decrement the TTL of a packet - it's a
> widely used algorithm.  Equation 3 from RFC1624 is correct :)

I was also under the belief that RFC1624 was handling this correctly.

> 
> Your code looks fine to me.  Are you sure you're verifying the
> checksum correctly?


This is how I am verifying the checksum. It seems to work in other 
cases. (by the way, I am working with the 2.4.20 kernel src code)

/* I do this check for only packets that are less than or equal to 76 
bytes in length. And I make sure the packets that I am dealing with are 
less than this length */

int tcpFailoverVerifyChecksum(struct sk_buff* skb)
{
     int len = skb->len - sizeof(struct iphdr);
     retValue = tcp_v4_check(skb->h.th, len,
                             skb->nh.iph->saddr, skb->nh.iph->daddr,
                             csum_partial((char *)skb->h.th, len, 0));
     return retValue;
}

Is the above function right? If not, what is the right way to verify the 
checksum of a tcp packet?


> 
> 
>>    while (cksum >> 16)
>>    {
>>        cksum = (cksum & 0xffff) + (cksum >> 16);
>>    }
> 
> 
> In general you need to add back the carry bits at most twice, btw.
> 
> 	cksum = (cksum & 0xffff) + (cksum >> 16);
> 	cksum += (cksum >> 16);

Ok...I will make the change... Thks...

Re: Incremental update of TCP Checksum

[Lincoln Dale]

At 06:35 AM 17/09/2003, Jesper Juhl wrote:
>Personally I can't see that you have any other option. The way the
>checksum is calculated information is lost, so it's impossible to
>determine exactely what input generated the current output (the checksum).
>Just as it is impossible to tell if the number 6 was generated from 2+2+2,
>from 3*2 or from 3+3 or some other...  So I don't see what else you can do
>except just recalculate the checksum from scratch. To try and determine
>how your modification would affect the checksum would probably take far
>longer than just re-calculating it.

of course you can do an incremental checksum update.
you know that if you're changing a field from (say) 0x22 to 0x11 then you 
can 'back out' the 0x22 and recalculate the checksum with 0x11.

this is the whole rationale behind why its a _checksum_ and not a _CRC_.

router(s) have taken advantage of incremental since day one.



cheers,

lincoln.

Re: Incremental update of TCP Checksum

[Jesper Juhl]

On Wed, 17 Sep 2003, Lincoln Dale wrote:

> At 06:35 AM 17/09/2003, Jesper Juhl wrote:
> >Personally I can't see that you have any other option. The way the
> >checksum is calculated information is lost, so it's impossible to
> >determine exactely what input generated the current output (the checksum).
> >Just as it is impossible to tell if the number 6 was generated from 2+2+2,
> >from 3*2 or from 3+3 or some other...  So I don't see what else you can do
> >except just recalculate the checksum from scratch. To try and determine
> >how your modification would affect the checksum would probably take far
> >longer than just re-calculating it.
>
> of course you can do an incremental checksum update.
> you know that if you're changing a field from (say) 0x22 to 0x11 then you
> can 'back out' the 0x22 and recalculate the checksum with 0x11.
>
> this is the whole rationale behind why its a _checksum_ and not a _CRC_.
>
> router(s) have taken advantage of incremental since day one.
>

I stand corrected.  Thank you for pointing that out.

Jesper Juhl <jju@dif.dk>

Re: Incremental update of TCP Checksum

[Raf D'Halleweyn]

This is what I wrote some time ago. But I haven't used it recently.

/* Incrementaly update a checksum, given old and new 32bit words */
static inline __u16 incr_check_l(__u16 old_check, __u32 old, __u32 new)
{ /* see RFC's 1624, 1141 and 1071 for incremental checksum updates */
    __u32 l;
    old_check = ~ntohs(old_check);
    old = ~old;
    l = (__u32)old_check + (old>>16) + (old&0xffff)
        + (new>>16) + (new&0xffff);
    return htons(~( (__u16)(l>>16) + (l&0xffff) ));
}


I have a similar function that can be used when you only change a 16bit
word:


/* Incrementaly update a checksum, given old and new 16bit words */
static inline __u16 incr_check_s(__u16 old_check, __u16 old, __u16 new)
{    /* see RFC's 1624, 1141 and 1071 for incremental checksum updates
*/
    __u32 l;
    old_check = ~ntohs(old_check);
    old = ~old;
    l = (__u32)old_check + old + new;
    return htons(~( (__u16)(l>>16) + (l&0xffff) ));
}


On Tue, 2003-09-16 at 16:32, Vishwas Raman wrote:
> Valdis.Kletnieks@vt.edu wrote:
> > On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-systems.com>  said:
> > 
> > 
> >>Can anyone out there tell me the algorithm to update the checksum 
> >>without having to recalculate it.
> > 
> > 
> > The canonical source is the RFCs:
> > 
> > 1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
> >      Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
> >      RFC1141) (Status: UNKNOWN)
> > 
> > 1141 Incremental updating of the Internet checksum. T. Mallory, A.
> >      Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
> >      (Updated by RFC1624) (Status: INFORMATIONAL)
> > 
> > 1624 Computation of the Internet Checksum via Incremental Update. A.
> >      Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
> >      RFC1141) (Status: INFORMATIONAL)
> > 
> > http://www.ietf.org/rfc/rfc1071.txt
> > http://www.ietf.org/rfc/rfc1141.txt
> > http://www.ietf.org/rfc/rfc1624.txt
> 
> As mentioned in RFC1624, I did the following.
> void changePacket(struct sk_buff* skb)
> {
>      struct tcphdr *tcpHdr = skb->h.th;
> 
>      // Verifying the tcp checksum works here...
> 
>      __u16 oldDoff = tcpHeader->doff;
>      tcpHeader->doff += 1;	
> 
>      // Formula from RFC1624 is HC' = ~(C + (-m) + m')
>      // where HC  - old checksum in header
>      // C   - one's complement sum of old header
>      // HC' - new checksum in header
>      // C'  - one's complement sum of new header
>      // m   - old value of a 16-bit field
>      // m'  - new value of a 16-bit field
> 
>      long cksum = (~(tcpHdr->check))&0xffff;
>      cksum += (__u16)~oldDoff;
>      cksum += tcpHeader->doff;
>      while (cksum >> 16)
>      {
>          cksum = (cksum & 0xffff) + (cksum >> 16);
>      }
>      tcpHeader->check = ~cksum;
> 
>      // Verifying tcp checksum here fails with bad cksum
> }
> 
> Is there any glaring mistake in the above code. If so, can someone
> please let me know what it is. It will be of great help.
> 
> Thanks,
> 
> -Vishwas.
> 
> 
> 
> 
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
-- 
Raf D'Halleweyn <raf@noduck.net>

Re: Incremental update of TCP Checksum

[David S. Miller]

On Tue, 16 Sep 2003 23:28:26 -0400
"Raf D'Halleweyn" <raf@noduck.net> wrote:

> This is what I wrote some time ago. But I haven't used it recently.

See include/net/ip.h:ip_increase_ttl().  Most people get this
code wrong, in particular the final carry.

Re: Incremental update of TCP Checksum

[Richard B. Johnson]

On Tue, 16 Sep 2003, Raf D'Halleweyn wrote:

>
> This is what I wrote some time ago. But I haven't used it recently.
>
> /* Incrementaly update a checksum, given old and new 32bit words */
> static inline __u16 incr_check_l(__u16 old_check, __u32 old, __u32 new)
> { /* see RFC's 1624, 1141 and 1071 for incremental checksum updates */
>     __u32 l;
>     old_check = ~ntohs(old_check);
>     old = ~old;
>     l = (__u32)old_check + (old>>16) + (old&0xffff)
>         + (new>>16) + (new&0xffff);
>     return htons(~( (__u16)(l>>16) + (l&0xffff) ));
> }
>
>
> I have a similar function that can be used when you only change a 16bit
> word:
>
>
> /* Incrementaly update a checksum, given old and new 16bit words */
> static inline __u16 incr_check_s(__u16 old_check, __u16 old, __u16 new)
> {    /* see RFC's 1624, 1141 and 1071 for incremental checksum updates
> */
>     __u32 l;
>     old_check = ~ntohs(old_check);
>     old = ~old;
>     l = (__u32)old_check + old + new;
>     return htons(~( (__u16)(l>>16) + (l&0xffff) ));
> }
>
>
> On Tue, 2003-09-16 at 16:32, Vishwas Raman wrote:
> > Valdis.Kletnieks@vt.edu wrote:
> > > On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-
> > > systems.com>  said:
> > >
> > >
> > >>Can anyone out there tell me the algorithm to update the checksum
> > >>without having to recalculate it.
> > >
> > >
> > > The canonical source is the RFCs:
> > >
> > > 1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
> > >      Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
> > >      RFC1141) (Status: UNKNOWN)
> > >
> > > 1141 Incremental updating of the Internet checksum. T. Mallory, A.
> > >      Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
> > >      (Updated by RFC1624) (Status: INFORMATIONAL)
> > >
> > > 1624 Computation of the Internet Checksum via Incremental Update. A.
> > >      Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
> > >      RFC1141) (Status: INFORMATIONAL)
> > >
> > > http://www.ietf.org/rfc/rfc1071.txt
> > > http://www.ietf.org/rfc/rfc1141.txt
> > > http://www.ietf.org/rfc/rfc1624.txt
> >
> > As mentioned in RFC1624, I did the following.
> > void changePacket(struct sk_buff* skb)
> > {
> >      struct tcphdr *tcpHdr = skb->h.th;
> >
> >      // Verifying the tcp checksum works here...
> >
> >      __u16 oldDoff = tcpHeader->doff;
> >      tcpHeader->doff += 1;
> >
> >      // Formula from RFC1624 is HC' = ~(C + (-m) + m')
> >      // where HC  - old checksum in header
> >      // C   - one's complement sum of old header
> >      // HC' - new checksum in header
> >      // C'  - one's complement sum of new header
> >      // m   - old value of a 16-bit field
> >      // m'  - new value of a 16-bit field
> >
> >      long cksum = (~(tcpHdr->check))&0xffff;
> >      cksum += (__u16)~oldDoff;
> >      cksum += tcpHeader->doff;
> >      while (cksum >> 16)
> >      {
> >          cksum = (cksum & 0xffff) + (cksum >> 16);
> >      }
> >      tcpHeader->check = ~cksum;
> >
> >      // Verifying tcp checksum here fails with bad cksum
> > }
> >
> > Is there any glaring mistake in the above code. If so, can someone
> > please let me know what it is. It will be of great help.
> >
> > Thanks,
> >
> > -Vishwas.


This is all wonderful. This assumes that the stuff being modified
in the packet is on well-defined boundaries, seldom the case when
you are re-writing packet data, but certainly the case if you
are re-writing an IP address.

Also, modern switches do not rewrite checksums using software.
Therefore, they do not use a re-write algorithm as stated by
others. The checksum gets calculated "for free" during the
hardware transfer to an output holding FIFO. It is done using
an ASIC with the appropriate adder and "stumble-carry".

Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: Incremental update of TCP Checksum

[Jamie Lokier]

Richard B. Johnson wrote:
> This is all wonderful. This assumes that the stuff being modified
> in the packet is on well-defined boundaries, seldom the case when
> you are re-writing packet data, but certainly the case if you
> are re-writing an IP address.

The only important boundary consideration is whether you're modifying
at an odd or even byte offset into the packet.

-- Jamie