Fix never pruned tcp out-of-order queue

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 <[email protected]>

net/ipv4/tcp_input.c +46 -27

index 5119856..fb5f522 100644
@@ -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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Hello!

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

Quoted 3 lines · Vitaliy Gusev

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?

From: Andi Kleen <[email protected]>
Date: Tue, 15 Apr 2008 09:59:40 +0200

Quoted 9 lines

Quoted 3 lines · Vitaliy Gusev

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.

Quoted 1 line

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.

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.

From: Andi Kleen <[email protected]>
Date: Tue, 15 Apr 2008 10:14:56 +0200

Quoted 4 lines

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.

Quoted 9 lines · On 15 April 2008 12:18:10 David Miller wrote:

From: Andi Kleen <[email protected]>
Date: Tue, 15 Apr 2008 10:14:56 +0200

Quoted 4 lines

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.

Quoted 10 lines · Vitaliy Gusev

Quoted 9 lines · On 15 April 2008 12:18:10 David Miller wrote:

From: Andi Kleen <[email protected]>
Date: Tue, 15 Apr 2008 10:14:56 +0200

Quoted 4 lines

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:)

Quoted 2 lines

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

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

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.

Hello!

Quoted 1 line

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.

Quoted 1 line

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:

Quoted 2 lines

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.

Hello!

Quoted 1 line

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.

Quoted 1 line

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:

Quoted 2 lines

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.