| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <11965492973133-git-send-email-ilpo.jarvinen@helsinki.fi>
Date: Sun, 2 Dec 2007 00:48:08 +0200
From: "Ilpo Järvinen" <ilpo.jarvinen@...sinki.fi>
To: David Miller <davem@...emloft.net>,
Herbert Xu <herbert@...dor.apana.org.au>
Cc: netdev@...r.kernel.org,
Stephen Hemminger <shemminger@...ux-foundation.org>,
"Ilpo Järvinen" <ilpo.jarvinen@...sinki.fi>
Subject: [PATCH 13/21] [TCP]: Store retransmit queue packets in RB tree.
From: =?ISO-8859-1?q?Ilpo_J=E4rvinen?= <ilpo.jarvinen@...sinki.fi>
This work was mostly done by David S. Miller.
Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@...sinki.fi>
---
include/linux/skbuff.h | 3 ++
include/linux/tcp.h | 2 +
include/net/tcp.h | 62 ++++++++++++++++++++++++++++++++++++++++++++-
net/ipv4/tcp_ipv4.c | 1 +
net/ipv4/tcp_minisocks.c | 1 +
net/ipv6/tcp_ipv6.c | 1 +
6 files changed, 68 insertions(+), 2 deletions(-)
diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
index d39f53e..b00e7e8 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
@@ -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>
@@ -253,6 +254,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;
diff --git a/include/linux/tcp.h b/include/linux/tcp.h
index 08027f1..c24fc06 100644
--- a/include/linux/tcp.h
+++ b/include/linux/tcp.h
@@ -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>
@@ -320,6 +321,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 */
diff --git a/include/net/tcp.h b/include/net/tcp.h
index 967f256..433c6a6 100644
--- a/include/net/tcp.h
+++ b/include/net/tcp.h
@@ -1190,6 +1190,11 @@ static inline void tcp_put_md5sig_pool(void)
put_cpu();
}
+static inline void tcp_write_queue_init(struct sock *sk)
+{
+ tcp_sk(sk)->write_queue_rb = RB_ROOT;
+}
+
/* write queue abstraction */
static inline void tcp_write_queue_purge(struct sock *sk)
{
@@ -1197,6 +1202,7 @@ static inline void tcp_write_queue_purge(struct sock *sk)
while ((skb = __skb_dequeue(&sk->sk_write_queue)) != NULL)
sk_stream_free_skb(sk, skb);
+ tcp_sk(sk)->write_queue_rb = RB_ROOT;
sk_stream_mem_reclaim(sk);
}
@@ -1252,7 +1258,7 @@ static inline void tcp_advance_send_head(struct sock *sk, struct sk_buff *skb)
TCP_SKB_CB(skb)->fack_count = TCP_SKB_CB(prev)->fack_count +
tcp_skb_pcount(prev);
- sk->sk_send_head = skb->next;
+ sk->sk_send_head = tcp_write_queue_next(sk, skb);
if (sk->sk_send_head == (struct sk_buff *)&sk->sk_write_queue)
sk->sk_send_head = NULL;
}
@@ -1268,10 +1274,58 @@ static inline void tcp_init_send_head(struct sock *sk)
sk->sk_send_head = NULL;
}
+static inline struct sk_buff *tcp_write_queue_find(struct sock *sk, __u32 seq)
+{
+ struct rb_node *rb_node = tcp_sk(sk)->write_queue_rb.rb_node;
+ struct sk_buff *skb = NULL;
+
+ while (rb_node) {
+ struct sk_buff *tmp = rb_entry(rb_node,struct sk_buff,rb);
+ if (after(TCP_SKB_CB(tmp)->end_seq, seq)) {
+ skb = tmp;
+ if (!after(TCP_SKB_CB(tmp)->seq, seq))
+ break;
+ rb_node = rb_node->rb_left;
+ } else
+ rb_node = rb_node->rb_right;
+
+ }
+ return skb;
+}
+
+static inline void tcp_rb_insert(struct sk_buff *skb, struct rb_root *root)
+{
+ struct rb_node **rb_link, *rb_parent;
+ __u32 seq = TCP_SKB_CB(skb)->seq;
+
+ rb_link = &root->rb_node;
+ rb_parent = NULL;
+ while (*rb_link) {
+ struct sk_buff *tmp;
+
+ rb_parent = *rb_link;
+ tmp = rb_entry(rb_parent,struct sk_buff,rb);
+ if (after(TCP_SKB_CB(tmp)->end_seq, seq)) {
+ BUG_ON(!after(TCP_SKB_CB(tmp)->seq, seq));
+ rb_link = &rb_parent->rb_left;
+ } else {
+ rb_link = &rb_parent->rb_right;
+ }
+ }
+ rb_link_node(&skb->rb, rb_parent, rb_link);
+ rb_insert_color(&skb->rb, root);
+}
+
+static inline void tcp_rb_unlink(struct sk_buff *skb, struct rb_root *root)
+{
+ rb_erase(&skb->rb, root);
+}
+
static inline void __tcp_add_write_queue_tail(struct sock *sk, struct sk_buff *skb)
{
TCP_SKB_CB(skb)->fack_count = 0;
__skb_queue_tail(&sk->sk_write_queue, skb);
+ tcp_rb_insert(skb, &tcp_sk(sk)->write_queue_rb);
}
static inline void tcp_add_write_queue_tail(struct sock *sk, struct sk_buff *skb)
@@ -1296,6 +1350,7 @@ static inline void __tcp_add_write_queue_head(struct sock *sk, struct sk_buff *s
BUG_ON(!skb_queue_empty(&sk->sk_write_queue));
__skb_queue_head(&sk->sk_write_queue, skb);
TCP_SKB_CB(skb)->fack_count = 0;
+ tcp_rb_insert(skb, &tcp_sk(sk)->write_queue_rb);
}
/* An insert into the middle of the write queue causes the fack
@@ -1326,15 +1381,17 @@ static inline void tcp_insert_write_queue_after(struct sk_buff *skb,
{
__skb_append(skb, buff, &sk->sk_write_queue);
tcp_reset_fack_counts(sk, buff);
+ tcp_rb_insert(buff, &tcp_sk(sk)->write_queue_rb);
}
-/* Insert skb between prev and next on the write queue of sk. */
+/* Insert new before skb on the write queue of sk. */
static inline void tcp_insert_write_queue_before(struct sk_buff *new,
struct sk_buff *skb,
struct sock *sk)
{
__skb_insert(new, skb->prev, skb, &sk->sk_write_queue);
tcp_reset_fack_counts(sk, new);
+ tcp_rb_insert(new, &tcp_sk(sk)->write_queue_rb);
if (sk->sk_send_head == skb)
sk->sk_send_head = new;
@@ -1343,6 +1400,7 @@ static inline void tcp_insert_write_queue_before(struct sk_buff *new,
static inline void tcp_unlink_write_queue(struct sk_buff *skb, struct sock *sk)
{
__skb_unlink(skb, &sk->sk_write_queue);
+ tcp_rb_unlink(skb, &tcp_sk(sk)->write_queue_rb);
}
static inline int tcp_skb_is_last(const struct sock *sk,
diff --git a/net/ipv4/tcp_ipv4.c b/net/ipv4/tcp_ipv4.c
index 652c323..5a27e42 100644
--- a/net/ipv4/tcp_ipv4.c
+++ b/net/ipv4/tcp_ipv4.c
@@ -1849,6 +1849,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);
+ tcp_write_queue_init(sk);
skb_queue_head_init(&tp->out_of_order_queue);
tcp_init_xmit_timers(sk);
tcp_prequeue_init(tp);
diff --git a/net/ipv4/tcp_minisocks.c b/net/ipv4/tcp_minisocks.c
index b61b768..e1a0e4a 100644
--- a/net/ipv4/tcp_minisocks.c
+++ b/net/ipv4/tcp_minisocks.c
@@ -426,6 +426,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);
+ tcp_write_queue_init(newsk);
skb_queue_head_init(&newtp->out_of_order_queue);
newtp->write_seq = treq->snt_isn + 1;
newtp->pushed_seq = newtp->write_seq;
diff --git a/net/ipv6/tcp_ipv6.c b/net/ipv6/tcp_ipv6.c
index 93980c3..f1294dc 100644
--- a/net/ipv6/tcp_ipv6.c
+++ b/net/ipv6/tcp_ipv6.c
@@ -1886,6 +1886,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);
+ tcp_write_queue_init(sk);
skb_queue_head_init(&tp->out_of_order_queue);
tcp_init_xmit_timers(sk);
tcp_prequeue_init(tp);
--
1.5.0.6
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists