A question about GRO neighbor packet matching

A question about GRO neighbor packet matching

[Ilya Matveychikov]

Hello all,


My question is about neighbor packet matching algorithm for TCP. Is it
correct to expect that IP packets should have continuous ID enumeration
(i.e. iph-next.id = iph-prev.id + 1)?

~~~
lib/librte_gro/gro_tcp4.c:check_seq_option()
	...
	/* check if the two packets are neighbors */
	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len - tcp_hl0;
	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
			(ip_id == (item->ip_id + 1)))
		/* append the new packet */
		return 1;
	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
			((ip_id + item->nb_merged) == item->ip_id))
		/* pre-pend the new packet */
		return -1;
	else
		return 0;
~~~

As per RFC791:

  Identification:  16 bits

    An identifying value assigned by the sender to aid in assembling the
    fragments of a datagram.

Re: A question about GRO neighbor packet matching

[Stephen Hemminger]

On Wed, 6 Dec 2017 18:02:21 +0400
Ilya Matveychikov <matvejchikov@gmail.com> wrote:

> Hello all,
> 
> 
> My question is about neighbor packet matching algorithm for TCP. Is it
> correct to expect that IP packets should have continuous ID enumeration
> (i.e. iph-next.id = iph-prev.id + 1)?


No.

> ~~~
> lib/librte_gro/gro_tcp4.c:check_seq_option()
> 	...
> 	/* check if the two packets are neighbors */
> 	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len - tcp_hl0;
> 	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
> 			(ip_id == (item->ip_id + 1)))
> 		/* append the new packet */
> 		return 1;
> 	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
> 			((ip_id + item->nb_merged) == item->ip_id))
> 		/* pre-pend the new packet */
> 		return -1;
> 	else
> 		return 0;
> ~~~
> 
> As per RFC791:
> 
>   Identification:  16 bits
> 
>     An identifying value assigned by the sender to aid in assembling the
>     fragments of a datagram.

The IP header id is meaningless in most TCP sessions.
Good TCP implementations use PMTU discovery which sets the Don't Fragment bit.
With DF, the IP id is unused (since no fragmentation).
Many implementations just send 0 since generating unique IP id requires an
atomic operation which is potential bottleneck.

Re: A question about GRO neighbor packet matching

[Ilya Matveychikov]

> On Dec 6, 2017, at 10:12 PM, Stephen Hemminger <stephen@networkplumber.org> wrote:
> 
> On Wed, 6 Dec 2017 18:02:21 +0400
> Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> 
>> Hello all,
>> 
>> 
>> My question is about neighbor packet matching algorithm for TCP. Is it
>> correct to expect that IP packets should have continuous ID enumeration
>> (i.e. iph-next.id = iph-prev.id + 1)?
> 
> 
> No.
> 
>> ~~~
>> lib/librte_gro/gro_tcp4.c:check_seq_option()
>> 	...
>> 	/* check if the two packets are neighbors */
>> 	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len - tcp_hl0;
>> 	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
>> 			(ip_id == (item->ip_id + 1)))
>> 		/* append the new packet */
>> 		return 1;
>> 	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
>> 			((ip_id + item->nb_merged) == item->ip_id))
>> 		/* pre-pend the new packet */
>> 		return -1;
>> 	else
>> 		return 0;
>> ~~~
>> 
>> As per RFC791:
>> 
>>  Identification:  16 bits
>> 
>>    An identifying value assigned by the sender to aid in assembling the
>>    fragments of a datagram.
> 
> The IP header id is meaningless in most TCP sessions.
> Good TCP implementations use PMTU discovery which sets the Don't Fragment bit.
> With DF, the IP id is unused (since no fragmentation).
> Many implementations just send 0 since generating unique IP id requires an
> atomic operation which is potential bottleneck.

So, is my question correct and the code is wrong?

Re: A question about GRO neighbor packet matching

[Stephen Hemminger]

On Wed, 6 Dec 2017 22:38:12 +0400
Ilya Matveychikov <matvejchikov@gmail.com> wrote:

> > On Dec 6, 2017, at 10:12 PM, Stephen Hemminger <stephen@networkplumber.org> wrote:
> > 
> > On Wed, 6 Dec 2017 18:02:21 +0400
> > Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> >   
> >> Hello all,
> >> 
> >> 
> >> My question is about neighbor packet matching algorithm for TCP. Is it
> >> correct to expect that IP packets should have continuous ID enumeration
> >> (i.e. iph-next.id = iph-prev.id + 1)?  
> > 
> > 
> > No.
> >   
> >> ~~~
> >> lib/librte_gro/gro_tcp4.c:check_seq_option()
> >> 	...
> >> 	/* check if the two packets are neighbors */
> >> 	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len - tcp_hl0;
> >> 	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
> >> 			(ip_id == (item->ip_id + 1)))
> >> 		/* append the new packet */
> >> 		return 1;
> >> 	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
> >> 			((ip_id + item->nb_merged) == item->ip_id))
> >> 		/* pre-pend the new packet */
> >> 		return -1;
> >> 	else
> >> 		return 0;
> >> ~~~
> >> 
> >> As per RFC791:
> >> 
> >>  Identification:  16 bits
> >> 
> >>    An identifying value assigned by the sender to aid in assembling the
> >>    fragments of a datagram.  
> > 
> > The IP header id is meaningless in most TCP sessions.
> > Good TCP implementations use PMTU discovery which sets the Don't Fragment bit.
> > With DF, the IP id is unused (since no fragmentation).
> > Many implementations just send 0 since generating unique IP id requires an
> > atomic operation which is potential bottleneck.  
> 
> So, is my question correct and the code is wrong?
> 

Yes. This code is wrong on several areas.
* The ip_id on TCP flows is irrelevant.
* packet should only be merged if TCP flags are the same.


The author should look at Linux net/ipv4/tcp_offload.c

Re: A question about GRO neighbor packet matching

[Ananyev, Konstantin]

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Stephen Hemminger
> Sent: Wednesday, December 6, 2017 11:16 PM
> To: Ilya Matveychikov <matvejchikov@gmail.com>
> Cc: dev@dpdk.org; Hu, Jiayu <jiayu.hu@intel.com>
> Subject: Re: [dpdk-dev] A question about GRO neighbor packet matching
> 
> On Wed, 6 Dec 2017 22:38:12 +0400
> Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> 
> > > On Dec 6, 2017, at 10:12 PM, Stephen Hemminger <stephen@networkplumber.org> wrote:
> > >
> > > On Wed, 6 Dec 2017 18:02:21 +0400
> > > Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> > >
> > >> Hello all,
> > >>
> > >>
> > >> My question is about neighbor packet matching algorithm for TCP. Is it
> > >> correct to expect that IP packets should have continuous ID enumeration
> > >> (i.e. iph-next.id = iph-prev.id + 1)?
> > >
> > >
> > > No.
> > >
> > >> ~~~
> > >> lib/librte_gro/gro_tcp4.c:check_seq_option()
> > >> 	...
> > >> 	/* check if the two packets are neighbors */
> > >> 	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len - tcp_hl0;
> > >> 	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
> > >> 			(ip_id == (item->ip_id + 1)))
> > >> 		/* append the new packet */
> > >> 		return 1;
> > >> 	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
> > >> 			((ip_id + item->nb_merged) == item->ip_id))
> > >> 		/* pre-pend the new packet */
> > >> 		return -1;
> > >> 	else
> > >> 		return 0;
> > >> ~~~
> > >>
> > >> As per RFC791:
> > >>
> > >>  Identification:  16 bits
> > >>
> > >>    An identifying value assigned by the sender to aid in assembling the
> > >>    fragments of a datagram.
> > >
> > > The IP header id is meaningless in most TCP sessions.
> > > Good TCP implementations use PMTU discovery which sets the Don't Fragment bit.
> > > With DF, the IP id is unused (since no fragmentation).
> > > Many implementations just send 0 since generating unique IP id requires an
> > > atomic operation which is potential bottleneck.
> >
> > So, is my question correct and the code is wrong?
> >
> 
> Yes. This code is wrong on several areas.
> * The ip_id on TCP flows is irrelevant.
> * packet should only be merged if TCP flags are the same.
> 
> 
> The author should look at Linux net/ipv4/tcp_offload.c

As I remember, linux GRO implementation *does* require that IP IDs
of the merging packets to be continuous.

net/ipv4/af_inet.c:
static struct sk_buff **inet_gro_receive(struct sk_buff **head,
					 struct sk_buff *skb)
{
  	...
 	id = ntohl(*(__be32 *)&iph->id);
	flush = (u16)((ntohl(*(__be32 *)iph) ^ skb_gro_len(skb)) | (id & ~IP_DF));
	id >>= 16;

	...

	NAPI_GRO_CB(p)->flush_id =
			    ((u16)(ntohs(iph2->id) + NAPI_GRO_CB(p)->count) ^ id);
	NAPI_GRO_CB(p)->flush |= flush;
               ....

And then at net/ipv4/tcp_offload.c:
struct sk_buff **tcp_gro_receive(struct sk_buff **head, struct sk_buff *skb)
{
	...
	/* Include the IP ID check below from the inner most IP hdr */
	flush = NAPI_GRO_CB(p)->flush | NAPI_GRO_CB(p)->flush_id;
	...
	if (flush || skb_gro_receive(head, skb)) {
 	...

The reason why we do need to check that IP ID is continuous - 
DPDK GRO library doesn't strip off IPv4 header, instead it has to merge them into one.
If IP ID would be non-contiguous it is unclear which one should be to used.
By same reason packets with different IP/TCP options are not allowed.
So in that case GRO lib makes a decision that it isn't safe to merge these packets.
As I understand linux does pretty much the same.
Konstantin 

 

Re: A question about GRO neighbor packet matching

[Stephen Hemminger]

On Thu, 7 Dec 2017 00:19:46 +0000
"Ananyev, Konstantin" <konstantin.ananyev@intel.com> wrote:

> > -----Original Message-----
> > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Stephen Hemminger
> > Sent: Wednesday, December 6, 2017 11:16 PM
> > To: Ilya Matveychikov <matvejchikov@gmail.com>
> > Cc: dev@dpdk.org; Hu, Jiayu <jiayu.hu@intel.com>
> > Subject: Re: [dpdk-dev] A question about GRO neighbor packet matching
> > 
> > On Wed, 6 Dec 2017 22:38:12 +0400
> > Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> >   
> > > > On Dec 6, 2017, at 10:12 PM, Stephen Hemminger <stephen@networkplumber.org> wrote:
> > > >
> > > > On Wed, 6 Dec 2017 18:02:21 +0400
> > > > Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> > > >  
> > > >> Hello all,
> > > >>
> > > >>
> > > >> My question is about neighbor packet matching algorithm for TCP. Is it
> > > >> correct to expect that IP packets should have continuous ID enumeration
> > > >> (i.e. iph-next.id = iph-prev.id + 1)?  
> > > >
> > > >
> > > > No.
> > > >  
> > > >> ~~~
> > > >> lib/librte_gro/gro_tcp4.c:check_seq_option()
> > > >> 	...
> > > >> 	/* check if the two packets are neighbors */
> > > >> 	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len - tcp_hl0;
> > > >> 	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
> > > >> 			(ip_id == (item->ip_id + 1)))
> > > >> 		/* append the new packet */
> > > >> 		return 1;
> > > >> 	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
> > > >> 			((ip_id + item->nb_merged) == item->ip_id))
> > > >> 		/* pre-pend the new packet */
> > > >> 		return -1;
> > > >> 	else
> > > >> 		return 0;
> > > >> ~~~
> > > >>
> > > >> As per RFC791:
> > > >>
> > > >>  Identification:  16 bits
> > > >>
> > > >>    An identifying value assigned by the sender to aid in assembling the
> > > >>    fragments of a datagram.  
> > > >
> > > > The IP header id is meaningless in most TCP sessions.
> > > > Good TCP implementations use PMTU discovery which sets the Don't Fragment bit.
> > > > With DF, the IP id is unused (since no fragmentation).
> > > > Many implementations just send 0 since generating unique IP id requires an
> > > > atomic operation which is potential bottleneck.  
> > >
> > > So, is my question correct and the code is wrong?
> > >  
> > 
> > Yes. This code is wrong on several areas.
> > * The ip_id on TCP flows is irrelevant.
> > * packet should only be merged if TCP flags are the same.
> > 
> > 
> > The author should look at Linux net/ipv4/tcp_offload.c  
> 
> As I remember, linux GRO implementation *does* require that IP IDs
> of the merging packets to be continuous.
> 
> net/ipv4/af_inet.c:
> static struct sk_buff **inet_gro_receive(struct sk_buff **head,
> 					 struct sk_buff *skb)
> {
>   	...
>  	id = ntohl(*(__be32 *)&iph->id);
> 	flush = (u16)((ntohl(*(__be32 *)iph) ^ skb_gro_len(skb)) | (id & ~IP_DF));
> 	id >>= 16;
> 
> 	...
> 
> 	NAPI_GRO_CB(p)->flush_id =
> 			    ((u16)(ntohs(iph2->id) + NAPI_GRO_CB(p)->count) ^ id);
> 	NAPI_GRO_CB(p)->flush |= flush;
>                ....
> 
> And then at net/ipv4/tcp_offload.c:
> struct sk_buff **tcp_gro_receive(struct sk_buff **head, struct sk_buff *skb)
> {
> 	...
> 	/* Include the IP ID check below from the inner most IP hdr */
> 	flush = NAPI_GRO_CB(p)->flush | NAPI_GRO_CB(p)->flush_id;
> 	...
> 	if (flush || skb_gro_receive(head, skb)) {
>  	...
> 
> The reason why we do need to check that IP ID is continuous - 
> DPDK GRO library doesn't strip off IPv4 header, instead it has to merge them into one.
> If IP ID would be non-contiguous it is unclear which one should be to used.
> By same reason packets with different IP/TCP options are not allowed.
> So in that case GRO lib makes a decision that it isn't safe to merge these packets.
> As I understand linux does pretty much the same.
> Konstantin 

You are right, but still not sure that Linux and DPDK are doing
the same thing with reordered packets.

Ok, went RFC hunting and the relevant one seems to be RFC 6864.
It mandates unique id's for each datagram so TCP does send them.

Re: A question about GRO neighbor packet matching

[Ilya Matveychikov]

> On Dec 7, 2017, at 5:01 AM, Stephen Hemminger <stephen@networkplumber.org> wrote:
> 
> Ok, went RFC hunting and the relevant one seems to be RFC 6864.
> It mandates unique id's for each datagram so TCP does send them.
> 
> 

Thanks for mention such the RFC, never heard about it.

Re: A question about GRO neighbor packet matching

[Hu, Jiayu]

Hi all,

> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Thursday, December 7, 2017 9:02 AM
> To: Ananyev, Konstantin <konstantin.ananyev@intel.com>
> Cc: Ilya Matveychikov <matvejchikov@gmail.com>; dev@dpdk.org; Hu, Jiayu
> <jiayu.hu@intel.com>
> Subject: Re: [dpdk-dev] A question about GRO neighbor packet matching
> 
> On Thu, 7 Dec 2017 00:19:46 +0000
> "Ananyev, Konstantin" <konstantin.ananyev@intel.com> wrote:
> 
> > > -----Original Message-----
> > > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Stephen
> Hemminger
> > > Sent: Wednesday, December 6, 2017 11:16 PM
> > > To: Ilya Matveychikov <matvejchikov@gmail.com>
> > > Cc: dev@dpdk.org; Hu, Jiayu <jiayu.hu@intel.com>
> > > Subject: Re: [dpdk-dev] A question about GRO neighbor packet matching
> > >
> > > On Wed, 6 Dec 2017 22:38:12 +0400
> > > Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> > >
> > > > > On Dec 6, 2017, at 10:12 PM, Stephen Hemminger
> <stephen@networkplumber.org> wrote:
> > > > >
> > > > > On Wed, 6 Dec 2017 18:02:21 +0400
> > > > > Ilya Matveychikov <matvejchikov@gmail.com> wrote:
> > > > >
> > > > >> Hello all,
> > > > >>
> > > > >>
> > > > >> My question is about neighbor packet matching algorithm for TCP. Is
> it
> > > > >> correct to expect that IP packets should have continuous ID
> enumeration
> > > > >> (i.e. iph-next.id = iph-prev.id + 1)?
> > > > >
> > > > >
> > > > > No.
> > > > >
> > > > >> ~~~
> > > > >> lib/librte_gro/gro_tcp4.c:check_seq_option()
> > > > >> 	...
> > > > >> 	/* check if the two packets are neighbors */
> > > > >> 	tcp_dl0 = pkt0->pkt_len - pkt0->l2_len - pkt0->l3_len -
> tcp_hl0;
> > > > >> 	if ((sent_seq == (item->sent_seq + tcp_dl0)) &&
> > > > >> 			(ip_id == (item->ip_id + 1)))
> > > > >> 		/* append the new packet */
> > > > >> 		return 1;
> > > > >> 	else if (((sent_seq + tcp_dl) == item->sent_seq) &&
> > > > >> 			((ip_id + item->nb_merged) == item->ip_id))
> > > > >> 		/* pre-pend the new packet */
> > > > >> 		return -1;
> > > > >> 	else
> > > > >> 		return 0;
> > > > >> ~~~
> > > > >>
> > > > >> As per RFC791:
> > > > >>
> > > > >>  Identification:  16 bits
> > > > >>
> > > > >>    An identifying value assigned by the sender to aid in assembling the
> > > > >>    fragments of a datagram.
> > > > >
> > > > > The IP header id is meaningless in most TCP sessions.
> > > > > Good TCP implementations use PMTU discovery which sets the Don't
> Fragment bit.
> > > > > With DF, the IP id is unused (since no fragmentation).
> > > > > Many implementations just send 0 since generating unique IP id
> requires an
> > > > > atomic operation which is potential bottleneck.
> > > >
> > > > So, is my question correct and the code is wrong?
> > > >
> > >
> > > Yes. This code is wrong on several areas.
> > > * The ip_id on TCP flows is irrelevant.

@Stephen and @Konstantin:
In the latest linux, its GRO supports two kinds of IP ID: fixed or incremental.
You can see the commit 1530545ed64b42e87acb43c0c16401bd1ebae6bf.
It uses "skb->is_atomic" to reflect if the IP ID is ignored. Linux GRO only checks
 IP ID for the packets which are non-atomic (is_atomic is 0), and these packets use
incremental IP ID. Others, which are atomic, use fixed IP ID and Linux doesn't check
their IP ID.

You can see the codes in tcp_offload.c:
	if (NAPI_GRO_CB(p)->flush_id != 1 || NAPI_GRO_CB(p)->count != 1 ||
		!NAPI_GRO_CB(p)->is_atomic)
			flush |= NAPI_GRO_CB(p)->flush_id;

In af_inet.c, is_atomic is set:
	NAPI_GRO_CB(skb)->is_atomic = !!(iph->frag_off & htons(IP_DF));

I haven't figured out which kind of packets are set to is_atomic in Linux.
Maybe Linux has followed RFC 6864. I need to investigate further.
Especially, we plan to support tunneled GRO. The outer IP ID will encounter
the same issue.

If you have any suggestions, that will be highly appreciated.

> > > * packet should only be merged if TCP flags are the same.

@Stephen, we do check TCP flags when decide if two packets can be merged.

Thanks,
Jiayu
> > >
> > >
> > > The author should look at Linux net/ipv4/tcp_offload.c
> >
> > As I remember, linux GRO implementation *does* require that IP IDs
> > of the merging packets to be continuous.
> >
> > net/ipv4/af_inet.c:
> > static struct sk_buff **inet_gro_receive(struct sk_buff **head,
> > 					 struct sk_buff *skb)
> > {
> >   	...
> >  	id = ntohl(*(__be32 *)&iph->id);
> > 	flush = (u16)((ntohl(*(__be32 *)iph) ^ skb_gro_len(skb)) | (id &
> ~IP_DF));
> > 	id >>= 16;
> >
> > 	...
> >
> > 	NAPI_GRO_CB(p)->flush_id =
> > 			    ((u16)(ntohs(iph2->id) + NAPI_GRO_CB(p)->count)
> ^ id);
> > 	NAPI_GRO_CB(p)->flush |= flush;
> >                ....
> >
> > And then at net/ipv4/tcp_offload.c:
> > struct sk_buff **tcp_gro_receive(struct sk_buff **head, struct sk_buff *skb)
> > {
> > 	...
> > 	/* Include the IP ID check below from the inner most IP hdr */
> > 	flush = NAPI_GRO_CB(p)->flush | NAPI_GRO_CB(p)->flush_id;
> > 	...
> > 	if (flush || skb_gro_receive(head, skb)) {
> >  	...
> >
> > The reason why we do need to check that IP ID is continuous -
> > DPDK GRO library doesn't strip off IPv4 header, instead it has to merge
> them into one.
> > If IP ID would be non-contiguous it is unclear which one should be to used.
> > By same reason packets with different IP/TCP options are not allowed.
> > So in that case GRO lib makes a decision that it isn't safe to merge these
> packets.
> > As I understand linux does pretty much the same.
> > Konstantin
> 
> You are right, but still not sure that Linux and DPDK are doing
> the same thing with reordered packets.
> 
> Ok, went RFC hunting and the relevant one seems to be RFC 6864.
> It mandates unique id's for each datagram so TCP does send them.
>