[RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Vitaliy Gusev]

Hello!

tcp_prune_queue() doesn't prune an out-of-order queue at all.
Therefore sk_rmem_schedule() can fail but the out-of-order queue
isn't pruned . This can lead to tcp deadlock state if the
next two conditions are held:

1. There are a sequence hole between last received in
   order segment and segments enqueued to the out-of-order queue.

2. Size of all segments in the out-of-order queue is more than tcp_mem[2].


Signed-off-by: Vitaliy Gusev <vgusev@openvz.org>

---
 tcp_input.c |   72 ++++++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 46 insertions(+), 26 deletions(-)


diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 5119856..fb5f522 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -3841,8 +3841,26 @@ static void tcp_ofo_queue(struct sock *sk)
 	}
 }
 
+static void tcp_prune_ofo_queue(struct sock *sk);
 static int tcp_prune_queue(struct sock *sk);
 
+static inline int tcp_try_rmem_schedule(struct sock *sk, unsigned int size)
+{
+	if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
+	    !sk_rmem_schedule(sk, size)) {
+
+		if (tcp_prune_queue(sk) < 0)
+			return -1;
+
+		if (!sk_rmem_schedule(sk, size)) {
+			tcp_prune_ofo_queue(sk);
+			if (!sk_rmem_schedule(sk, size))
+				return -1;
+		}
+	}
+	return 0;
+}
+
 static void tcp_data_queue(struct sock *sk, struct sk_buff *skb)
 {
 	struct tcphdr *th = tcp_hdr(skb);
@@ -3892,12 +3910,9 @@ static void tcp_data_queue(struct sock *sk, struct sk_buff *skb)
 		if (eaten <= 0) {
 queue_and_out:
 			if (eaten < 0 &&
-			    (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
-			     !sk_rmem_schedule(sk, skb->truesize))) {
-				if (tcp_prune_queue(sk) < 0 ||
-				    !sk_rmem_schedule(sk, skb->truesize))
-					goto drop;
-			}
+			    tcp_try_rmem_schedule(sk, skb->truesize))
+				goto drop;
+
 			skb_set_owner_r(skb, sk);
 			__skb_queue_tail(&sk->sk_receive_queue, skb);
 		}
@@ -3966,12 +3981,8 @@ drop:
 
 	TCP_ECN_check_ce(tp, skb);
 
-	if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
-	    !sk_rmem_schedule(sk, skb->truesize)) {
-		if (tcp_prune_queue(sk) < 0 ||
-		    !sk_rmem_schedule(sk, skb->truesize))
-			goto drop;
-	}
+	if (tcp_try_rmem_schedule(sk, skb->truesize))
+		goto drop;
 
 	/* Disable header prediction. */
 	tp->pred_flags = 0;
@@ -4198,6 +4209,28 @@ static void tcp_collapse_ofo_queue(struct sock *sk)
 	}
 }
 
+/*
+ * Purge the out-of-order queue.
+ */
+static void tcp_prune_ofo_queue(struct sock *sk)
+{
+	struct tcp_sock *tp = tcp_sk(sk);
+
+	if (!skb_queue_empty(&tp->out_of_order_queue)) {
+		NET_INC_STATS_BH(LINUX_MIB_OFOPRUNED);
+		__skb_queue_purge(&tp->out_of_order_queue);
+
+		/* Reset SACK state.  A conforming SACK implementation will
+		 * do the same at a timeout based retransmit.  When a connection
+		 * is in a sad state like this, we care only about integrity
+		 * of the connection not performance.
+		 */
+		if (tp->rx_opt.sack_ok)
+			tcp_sack_reset(&tp->rx_opt);
+		sk_mem_reclaim(sk);
+	}
+}
+
 /* Reduce allocated memory if we can, trying to get
  * the socket within its memory limits again.
  *
@@ -4231,20 +4264,7 @@ static int tcp_prune_queue(struct sock *sk)
 	/* Collapsing did not help, destructive actions follow.
 	 * This must not ever occur. */
 
-	/* First, purge the out_of_order queue. */
-	if (!skb_queue_empty(&tp->out_of_order_queue)) {
-		NET_INC_STATS_BH(LINUX_MIB_OFOPRUNED);
-		__skb_queue_purge(&tp->out_of_order_queue);
-
-		/* Reset SACK state.  A conforming SACK implementation will
-		 * do the same at a timeout based retransmit.  When a connection
-		 * is in a sad state like this, we care only about integrity
-		 * of the connection not performance.
-		 */
-		if (tcp_is_sack(tp))
-			tcp_sack_reset(&tp->rx_opt);
-		sk_mem_reclaim(sk);
-	}
+	tcp_prune_ofo_queue(sk);
 
 	if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf)
 		return 0;

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[David Miller]

From: Vitaliy Gusev <vgusev@openvz.org>
Date: Mon, 14 Apr 2008 21:21:53 +0400

[ Please CC: netdev@vger.kernel.org for networking patches in
  the future, thank you ]

> tcp_prune_queue() doesn't prune an out-of-order queue at all.
> Therefore sk_rmem_schedule() can fail but the out-of-order queue
> isn't pruned . This can lead to tcp deadlock state if the
> next two conditions are held:
> 
> 1. There are a sequence hole between last received in
>    order segment and segments enqueued to the out-of-order queue.
> 
> 2. Size of all segments in the out-of-order queue is more than tcp_mem[2].
> 
> 
> Signed-off-by: Vitaliy Gusev <vgusev@openvz.org>

Looks good, applied.

> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index 5119856..fb5f522 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -3841,8 +3841,26 @@ static void tcp_ofo_queue(struct sock *sk)
>  	}
>  }
>  
> +static void tcp_prune_ofo_queue(struct sock *sk);
>  static int tcp_prune_queue(struct sock *sk);
>  
> +static inline int tcp_try_rmem_schedule(struct sock *sk, unsigned int size)
> +{
> +	if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
> +	    !sk_rmem_schedule(sk, size)) {
> +
> +		if (tcp_prune_queue(sk) < 0)
> +			return -1;
> +
> +		if (!sk_rmem_schedule(sk, size)) {
> +			tcp_prune_ofo_queue(sk);
> +			if (!sk_rmem_schedule(sk, size))
> +				return -1;
> +		}
> +	}
> +	return 0;
> +}
> +
>  static void tcp_data_queue(struct sock *sk, struct sk_buff *skb)
>  {
>  	struct tcphdr *th = tcp_hdr(skb);
> @@ -3892,12 +3910,9 @@ static void tcp_data_queue(struct sock *sk, struct sk_buff *skb)
>  		if (eaten <= 0) {
>  queue_and_out:
>  			if (eaten < 0 &&
> -			    (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
> -			     !sk_rmem_schedule(sk, skb->truesize))) {
> -				if (tcp_prune_queue(sk) < 0 ||
> -				    !sk_rmem_schedule(sk, skb->truesize))
> -					goto drop;
> -			}
> +			    tcp_try_rmem_schedule(sk, skb->truesize))
> +				goto drop;
> +
>  			skb_set_owner_r(skb, sk);
>  			__skb_queue_tail(&sk->sk_receive_queue, skb);
>  		}
> @@ -3966,12 +3981,8 @@ drop:
>  
>  	TCP_ECN_check_ce(tp, skb);
>  
> -	if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
> -	    !sk_rmem_schedule(sk, skb->truesize)) {
> -		if (tcp_prune_queue(sk) < 0 ||
> -		    !sk_rmem_schedule(sk, skb->truesize))
> -			goto drop;
> -	}
> +	if (tcp_try_rmem_schedule(sk, skb->truesize))
> +		goto drop;
>  
>  	/* Disable header prediction. */
>  	tp->pred_flags = 0;
> @@ -4198,6 +4209,28 @@ static void tcp_collapse_ofo_queue(struct sock *sk)
>  	}
>  }
>  
> +/*
> + * Purge the out-of-order queue.
> + */
> +static void tcp_prune_ofo_queue(struct sock *sk)
> +{
> +	struct tcp_sock *tp = tcp_sk(sk);
> +
> +	if (!skb_queue_empty(&tp->out_of_order_queue)) {
> +		NET_INC_STATS_BH(LINUX_MIB_OFOPRUNED);
> +		__skb_queue_purge(&tp->out_of_order_queue);
> +
> +		/* Reset SACK state.  A conforming SACK implementation will
> +		 * do the same at a timeout based retransmit.  When a connection
> +		 * is in a sad state like this, we care only about integrity
> +		 * of the connection not performance.
> +		 */
> +		if (tp->rx_opt.sack_ok)
> +			tcp_sack_reset(&tp->rx_opt);
> +		sk_mem_reclaim(sk);
> +	}
> +}
> +
>  /* Reduce allocated memory if we can, trying to get
>   * the socket within its memory limits again.
>   *
> @@ -4231,20 +4264,7 @@ static int tcp_prune_queue(struct sock *sk)
>  	/* Collapsing did not help, destructive actions follow.
>  	 * This must not ever occur. */
>  
> -	/* First, purge the out_of_order queue. */
> -	if (!skb_queue_empty(&tp->out_of_order_queue)) {
> -		NET_INC_STATS_BH(LINUX_MIB_OFOPRUNED);
> -		__skb_queue_purge(&tp->out_of_order_queue);
> -
> -		/* Reset SACK state.  A conforming SACK implementation will
> -		 * do the same at a timeout based retransmit.  When a connection
> -		 * is in a sad state like this, we care only about integrity
> -		 * of the connection not performance.
> -		 */
> -		if (tcp_is_sack(tp))
> -			tcp_sack_reset(&tp->rx_opt);
> -		sk_mem_reclaim(sk);
> -	}
> +	tcp_prune_ofo_queue(sk);
>  
>  	if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf)
>  		return 0;
> 
> --
> 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/

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Andi Kleen]

Vitaliy Gusev <vgusev@openvz.org> writes:

> Hello!
>
> tcp_prune_queue() doesn't prune an out-of-order queue at all.

Why are you saying this? It has code to prune the ooo queue. You're even
moving it in your patch.

You're saying that the code doesn't work? If yes why? 

-Andi

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Tue, 15 Apr 2008 09:59:40 +0200

> Vitaliy Gusev <vgusev@openvz.org> writes:
> 
> > Hello!
> >
> > tcp_prune_queue() doesn't prune an out-of-order queue at all.
> 
> Why are you saying this? It has code to prune the ooo queue. You're even
> moving it in your patch.
> 
> You're saying that the code doesn't work? If yes why? 

There are inappropriate guards there, and it didn't get invoked
from another important code path.

That's what his change is fixing.

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Andi Kleen]

David Miller <davem@davemloft.net> writes:

> From: Andi Kleen <andi@firstfloor.org>
> Date: Tue, 15 Apr 2008 09:59:40 +0200
>
>> Vitaliy Gusev <vgusev@openvz.org> writes:
>> 
>> > Hello!
>> >
>> > tcp_prune_queue() doesn't prune an out-of-order queue at all.
>> 
>> Why are you saying this? It has code to prune the ooo queue. You're even
>> moving it in your patch.
>> 
>> You're saying that the code doesn't work? If yes why? 
>
> There are inappropriate guards there, and it didn't get invoked
> from another important code path.
>
> That's what his change is fixing.

Perhaps I'm dense, but I don't see the inappropiate guards. The 
guards are pretty much the same as before.

The main difference seems to be that
sk_rmem_schedule/__sk_mem_schedule is called more often, but it is 
unclear how this affects the ooo pruning which only checks
the queue length anyways.

-Andi

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Tue, 15 Apr 2008 10:14:56 +0200

> The main difference seems to be that
> sk_rmem_schedule/__sk_mem_schedule is called more often, but it is 
> unclear how this affects the ooo pruning which only checks
> the queue length anyways.

tcp_data_queue() would not do the tcp_prune_ofo_queue() in some
cases, it's the whole point of the patch.

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Vitaliy Gusev]

On 15 April 2008 12:18:10 David Miller wrote:
> From: Andi Kleen <andi@firstfloor.org>
> Date: Tue, 15 Apr 2008 10:14:56 +0200
> 
> > The main difference seems to be that
> > sk_rmem_schedule/__sk_mem_schedule is called more often, but it is 
> > unclear how this affects the ooo pruning which only checks
> > the queue length anyways.
> 
> tcp_data_queue() would not do the tcp_prune_ofo_queue() in some
> cases, it's the whole point of the patch.

Yes, if second sk_rmem_schedule() failed then tcp_prune_ofo_queue() is force called
and try sk_rmem_schedule() again.


-- 
Thank,
Vitaliy Gusev

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Andi Kleen]

Vitaliy Gusev wrote:
> On 15 April 2008 12:18:10 David Miller wrote:
>> From: Andi Kleen <andi@firstfloor.org>
>> Date: Tue, 15 Apr 2008 10:14:56 +0200
>>
>>> The main difference seems to be that
>>> sk_rmem_schedule/__sk_mem_schedule is called more often, but it is 
>>> unclear how this affects the ooo pruning which only checks
>>> the queue length anyways.
>> tcp_data_queue() would not do the tcp_prune_ofo_queue() in some
>> cases, it's the whole point of the patch.

I still think the guards are pretty much the same as before, sorry:)

> Yes, if second sk_rmem_schedule() failed then tcp_prune_ofo_queue() is force called
> and try sk_rmem_schedule() again.

Yes but that doesn't affect the ooo prune guards at all, they only check
rmem_alloc and neither sk_rmem_schedule() nor __sk_mem_schedule
change that. Also the two callers are the same too in their checks.

But why not repeat the whole prune for all cases in this case then?

e.g. you should probably at least repeat the third step (setting
pred_flags to 0) too.

-Andi

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Vitaliy Gusev]

On 15 April 2008 12:30:34 Andi Kleen wrote:
> Vitaliy Gusev wrote:
> > On 15 April 2008 12:18:10 David Miller wrote:
> >> From: Andi Kleen <andi@firstfloor.org>
> >> Date: Tue, 15 Apr 2008 10:14:56 +0200
> >>
> >>> The main difference seems to be that
> >>> sk_rmem_schedule/__sk_mem_schedule is called more often, but it is 
> >>> unclear how this affects the ooo pruning which only checks
> >>> the queue length anyways.
> >> tcp_data_queue() would not do the tcp_prune_ofo_queue() in some
> >> cases, it's the whole point of the patch.
> 
> I still think the guards are pretty much the same as before, sorry:)
> 
> > Yes, if second sk_rmem_schedule() failed then tcp_prune_ofo_queue() is force called
> > and try sk_rmem_schedule() again.
> 
> Yes but that doesn't affect the ooo prune guards at all, they only check
> rmem_alloc and neither sk_rmem_schedule() nor __sk_mem_schedule
> change that. Also the two callers are the same too in their checks.
>
> But why not repeat the whole prune for all cases in this case then?
> 
> e.g. you should probably at least repeat the third step (setting
> pred_flags to 0) too.

Did you mean merely add check on tcp_memory_allocated < prot->sysctl_mem[2]
to tcp_prune_queue() ?
It is not enough as __sk_mem_schedule() can fail also
because of memory_pressure is on and there are too many opened sockets.

i.e. I avoid duplicating checks from __sk_mem_schedule().


> 
> -Andi



-- 
Thank,
Vitaliy Gusev

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Alexey Kuznetsov]

Hello!

> I still think the guards are pretty much the same as before, sorry:)

Guards inside tcp_prune_queue() are the same exactly.

But the patch adds the second point where out-of-order queue is discarded.
It is when the socket is under rcvbuf, but nevertheless skb cannot
be queued due to system-wide limit. In that case out-of-order queue
is dropped and the limits are rechecked.


> But why not repeat the whole prune for all cases in this case then?

Collapsing and tuning rcv_ssthresh was done once, they are not guarded
by rcvbuf check. So, repeating those steps would be useless.

The only thing is:

> e.g. you should probably at least repeat the third step (setting
> pred_flags to 0) too.

Formally, this is correct. But this is not necessary, pred_flags reset
is redundant even in the first place. The fast path is not so fast,
memory limit is checked explicitly there.


The patch is not perfect. F.e. tcp_prune_ofo_queue() could see empty
out-of-order queue, in this case the second sk_stream_rmem_schedule()
is useless and could be skipped. But it is the second order effect.

I think this will work.

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Vitaliy Gusev]

On 15 April 2008 15:59:24 Alexey Kuznetsov wrote:
> Hello!
> 
> > I still think the guards are pretty much the same as before, sorry:)
> 
> Guards inside tcp_prune_queue() are the same exactly.
> 
> But the patch adds the second point where out-of-order queue is discarded.
> It is when the socket is under rcvbuf, but nevertheless skb cannot
> be queued due to system-wide limit. In that case out-of-order queue 
> is dropped and the limits are rechecked.
> 
> 
> > But why not repeat the whole prune for all cases in this case then?
> 
> Collapsing and tuning rcv_ssthresh was done once, they are not guarded
> by rcvbuf check. So, repeating those steps would be useless.
> 
> The only thing is:
> 
> > e.g. you should probably at least repeat the third step (setting
> > pred_flags to 0) too.
> 
> Formally, this is correct. But this is not necessary, pred_flags reset
> is redundant even in the first place. The fast path is not so fast,
> memory limit is checked explicitly there.
> 
> 
> The patch is not perfect. F.e. tcp_prune_ofo_queue() could see empty
> out-of-order queue, in this case the second sk_stream_rmem_schedule()
> is useless and could be skipped. But it is the second order effect.
> 
> I think this will work.

Thanks for comments. I will correct second call sk_stream_rmem_schedule()
and resend new patch.
 



-- 
Thank,
Vitaliy Gusev

Re: [RFC][PATCH][NET] Fix never pruned tcp out-of-order queue

[Vitaliy Gusev]

> On 15 April 2008 15:59:24 Alexey Kuznetsov wrote:
> Hello!
> 
> > I still think the guards are pretty much the same as before, sorry:)
> 
> Guards inside tcp_prune_queue() are the same exactly.
> 
> But the patch adds the second point where out-of-order queue is discarded.
> It is when the socket is under rcvbuf, but nevertheless skb cannot
> be queued due to system-wide limit. In that case out-of-order queue 
> is dropped and the limits are rechecked.
> 
> 
> > But why not repeat the whole prune for all cases in this case then?
> 
> Collapsing and tuning rcv_ssthresh was done once, they are not guarded
> by rcvbuf check. So, repeating those steps would be useless.
> 
> The only thing is:
> 
> > e.g. you should probably at least repeat the third step (setting
> > pred_flags to 0) too.
> 
> Formally, this is correct. But this is not necessary, pred_flags reset
> is redundant even in the first place. The fast path is not so fast,
> memory limit is checked explicitly there.
> 
> 
> The patch is not perfect. F.e. tcp_prune_ofo_queue() could see empty
> out-of-order queue, in this case the second sk_stream_rmem_schedule()
> is useless and could be skipped. But it is the second order effect.
> 
> I think this will work.

> Thanks for comments. I will correct second call sk_stream_rmem_schedule()
> and resend new patch.

Does tuning window need to consider free TCP memory (something like
tcp_mem[2] - memory_allocated) ?
 
-- 
Thank,
Vitaliy Gusev