Skip to contentSkip to conversation

: TCP RB tree core v2.

PATCH In review David Miller 2 participants 3 messages Mar 7, 2007 – Mar 8, 2007

Subsystems (3)
Networking Network drivers TCP
lore
Share & tools
lore

David Miller

author maintainer
#0 lore raw

PATCH 1/1 : TCP RB tree core v2.

I checked the TCP write queue abstraction patch into the net-2.6.22 GIT tree at:

	kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6.22.git

And below is the current version of the second patch which actually does the RB tree stuff.

This infrastructure is necessary for the SKB hinting elimination work various folks are doing. I'm hesitent to check this into the net-2.6.22 tree until it's been running on my workstation for a little while without any crashes.

My plane is to check it in after it survives some testing of mine, and if the RB tree business turns out to be too costly for the gains we get I'll rip it out before I merge this tree to Linus.

[TCP]: Store retransmit queue packets in RB tree.

Signed-off-by David S. Miller <[email protected]>
include/linux/skbuff.h +3 -0
index 0d5351a..c76e194 100644
@@ -18,6 +18,7 @@
 #include <linux/compiler.h>
 #include <linux/time.h>
 #include <linux/cache.h>
+#include <linux/rbtree.h>
 
 #include <asm/atomic.h>
 #include <asm/types.h>

@@ -230,6 +231,8 @@ struct sk_buff {
 	struct sk_buff		*next;
 	struct sk_buff		*prev;
 
+	struct rb_node		rb;
+
 	struct sock		*sk;
 	ktime_t			tstamp;
 	struct net_device	*dev;
include/linux/tcp.h +2 -0
index 18a468d..b73687a 100644
@@ -174,6 +174,7 @@ struct tcp_md5sig {
 
 #include <linux/skbuff.h>
 #include <linux/dmaengine.h>
+#include <linux/rbtree.h>
 #include <net/sock.h>
 #include <net/inet_connection_sock.h>
 #include <net/inet_timewait_sock.h>

@@ -306,6 +307,7 @@ struct tcp_sock {
 	u32	snd_cwnd_used;
 	u32	snd_cwnd_stamp;
 
+	struct rb_root		write_queue_rb;
 	struct sk_buff_head	out_of_order_queue; /* Out of order segments go here */
 
  	u32	rcv_wnd;	/* Current receiver window		*/
include/net/tcp.h +52 -2

99 lines not on this page · raw message

net/ipv4/tcp_ipv4.c +1 -0
index 3326681..bf5f139 100644
@@ -1838,6 +1838,7 @@ static int tcp_v4_init_sock(struct sock *sk)
 	struct inet_connection_sock *icsk = inet_csk(sk);
 	struct tcp_sock *tp = tcp_sk(sk);
 
+	tp->write_queue_rb = RB_ROOT;
 	skb_queue_head_init(&tp->out_of_order_queue);
 	tcp_init_xmit_timers(sk);
 	tcp_prequeue_init(tp);
net/ipv4/tcp_minisocks.c +1 -0
index ac4ce48..0a57c36 100644
@@ -421,6 +421,7 @@ struct sock *tcp_create_openreq_child(struct sock *sk, struct request_sock *req,
 
 		tcp_set_ca_state(newsk, TCP_CA_Open);
 		tcp_init_xmit_timers(newsk);
+		newtp->write_queue_rb = RB_ROOT;
 		skb_queue_head_init(&newtp->out_of_order_queue);
 		newtp->write_seq = treq->snt_isn + 1;
 		newtp->pushed_seq = newtp->write_seq;
net/ipv4/tcp_output.c +2 -2
index 26c16d1..bc2d477 100644
@@ -1267,11 +1267,11 @@ static int tcp_mtu_probe(struct sock *sk)
 	sk_charge_skb(sk, nskb);
 
 	skb = tcp_send_head(sk);
+	TCP_SKB_CB(nskb)->seq = TCP_SKB_CB(skb)->seq;
+	TCP_SKB_CB(nskb)->end_seq = TCP_SKB_CB(skb)->seq + probe_size;
 	tcp_insert_write_queue_before(nskb, skb, sk);
 	tcp_advance_send_head(sk, skb);
 
-	TCP_SKB_CB(nskb)->seq = TCP_SKB_CB(skb)->seq;
-	TCP_SKB_CB(nskb)->end_seq = TCP_SKB_CB(skb)->seq + probe_size;
 	TCP_SKB_CB(nskb)->flags = TCPCB_FLAG_ACK;
 	TCP_SKB_CB(nskb)->sacked = 0;
 	nskb->csum = 0;
net/ipv6/tcp_ipv6.c +1 -0
index f57a9ba..21706a1 100644
@@ -1890,6 +1890,7 @@ static int tcp_v6_init_sock(struct sock *sk)
 	struct inet_connection_sock *icsk = inet_csk(sk);
 	struct tcp_sock *tp = tcp_sk(sk);
 
+	tp->write_queue_rb = RB_ROOT;
 	skb_queue_head_init(&tp->out_of_order_queue);
 	tcp_init_xmit_timers(sk);
 	tcp_prequeue_init(tp);
#1 lore raw
Quoted 4 lines · David Miller

I checked the TCP write queue abstraction patch into the net-2.6.22 GIT tree at:

	kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6.22.git

While tried to apply your patch below, I noticed it's already there. It turns out that ebbe72e602c1e825c8ec97349095bdd286c0ff24 seems to be a mess, it includes also rbtree stuff you are giving below.

Quoted 2 lines

And below is the current version of the second patch which actually does the RB tree stuff.

...snip...

Signature · 1 line
 i.
author maintainer
#2 lore raw

From: "Ilpo_Järvinen" <[email protected]>
Date: Thu, 8 Mar 2007 06:21:03 +0200 (EET)

Quoted 10 lines · David Miller
Quoted 5 lines

I checked the TCP write queue abstraction patch into the net-2.6.22 GIT tree at:

	kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6.22.git

While tried to apply your patch below, I noticed it's already there. It turns out that ebbe72e602c1e825c8ec97349095bdd286c0ff24 seems to be a mess, it includes also rbtree stuff you are giving below.

I noticed this just an hour ago too.

I'm rebasing the tree and checking it in properly this time with a bug fix or two :)

Stephen Hemminger noticed that it crashes with TSO, which still isn't fixed, and I'm trying to figure out that bug right now.