From d458c25ce24ce00ea547e9976e293e7835416253 Mon Sep 17 00:00:00 2001 From: Andrea Bittau Date: Tue, 19 Sep 2006 13:07:20 -0700 Subject: [DCCP] CCID2: Initialize ssthresh to infinity Initialize the slow-start threshold to infinity. This way, upon connection initiation, slow-start will be exited only upon a packet loss. This patch will allow connections to quickly gain speed. Signed-off-by: Andrea Bittau Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/ccid2.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'net/dccp/ccids/ccid2.h') diff --git a/net/dccp/ccids/ccid2.h b/net/dccp/ccids/ccid2.h index 451a87464fa..b4cc6c0bf02 100644 --- a/net/dccp/ccids/ccid2.h +++ b/net/dccp/ccids/ccid2.h @@ -50,7 +50,7 @@ struct ccid2_hc_tx_sock { int ccid2hctx_cwnd; int ccid2hctx_ssacks; int ccid2hctx_acks; - int ccid2hctx_ssthresh; + unsigned int ccid2hctx_ssthresh; int ccid2hctx_pipe; int ccid2hctx_numdupack; struct ccid2_seq *ccid2hctx_seqbuf; -- cgit v1.2.3-70-g09d2 From 07978aabd52ce67f59971872c80f76d6e3ca18ae Mon Sep 17 00:00:00 2001 From: Andrea Bittau Date: Tue, 19 Sep 2006 13:13:37 -0700 Subject: [DCCP] CCID2: Allocate seq records on demand Allocate more sequence state on demand. Each time a packet is sent out by CCID2, a record of it needs to be kept. This list of records grows proportionally to cwnd. Previously, the length of this list was hardcored and therefore the cwnd could only grow to this value (of 128). Now, records are allocated on demand as necessary---cwnd may grow as it wishes. The exceptional case of when memory is not available is not handled gracefully. Perhaps, cwnd should be capped at that point. Signed-off-by: Andrea Bittau Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/ccid2.c | 96 ++++++++++++++++++++++++++++++++++---------------- net/dccp/ccids/ccid2.h | 6 +++- 2 files changed, 70 insertions(+), 32 deletions(-) (limited to 'net/dccp/ccids/ccid2.h') diff --git a/net/dccp/ccids/ccid2.c b/net/dccp/ccids/ccid2.c index dbcda7e868b..93a30ae8d07 100644 --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -44,8 +44,6 @@ static int ccid2_debug; #define ccid2_pr_debug(format, a...) #endif -static const int ccid2_seq_len = 128; - #ifdef CONFIG_IP_DCCP_CCID2_DEBUG static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx) { @@ -71,7 +69,6 @@ static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx) BUG_ON(seqp->ccid2s_seq <= prev->ccid2s_seq); BUG_ON(time_before(seqp->ccid2s_sent, prev->ccid2s_sent)); - BUG_ON(len > ccid2_seq_len); seqp = prev; } @@ -83,16 +80,57 @@ static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx) do { seqp = seqp->ccid2s_prev; len++; - BUG_ON(len > ccid2_seq_len); } while (seqp != hctx->ccid2hctx_seqh); - BUG_ON(len != ccid2_seq_len); ccid2_pr_debug("total len=%d\n", len); + BUG_ON(len != hctx->ccid2hctx_seqbufc * CCID2_SEQBUF_LEN); } #else #define ccid2_hc_tx_check_sanity(hctx) do {} while (0) #endif +static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock *hctx, int num, + gfp_t gfp) +{ + struct ccid2_seq *seqp; + int i; + + /* check if we have space to preserve the pointer to the buffer */ + if (hctx->ccid2hctx_seqbufc >= (sizeof(hctx->ccid2hctx_seqbuf) / + sizeof(struct ccid2_seq*))) + return -ENOMEM; + + /* allocate buffer and initialize linked list */ + seqp = kmalloc(sizeof(*seqp) * num, gfp); + if (seqp == NULL) + return -ENOMEM; + + for (i = 0; i < (num - 1); i++) { + seqp[i].ccid2s_next = &seqp[i + 1]; + seqp[i + 1].ccid2s_prev = &seqp[i]; + } + seqp[num - 1].ccid2s_next = seqp; + seqp->ccid2s_prev = &seqp[num - 1]; + + /* This is the first allocation. Initiate the head and tail. */ + if (hctx->ccid2hctx_seqbufc == 0) + hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqt = seqp; + else { + /* link the existing list with the one we just created */ + hctx->ccid2hctx_seqh->ccid2s_next = seqp; + seqp->ccid2s_prev = hctx->ccid2hctx_seqh; + + hctx->ccid2hctx_seqt->ccid2s_prev = &seqp[num - 1]; + seqp[num - 1].ccid2s_next = hctx->ccid2hctx_seqt; + } + + /* store the original pointer to the buffer so we can free it */ + hctx->ccid2hctx_seqbuf[hctx->ccid2hctx_seqbufc] = seqp; + hctx->ccid2hctx_seqbufc++; + + return 0; +} + static int ccid2_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb, int len) { @@ -231,6 +269,7 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, int len) { struct dccp_sock *dp = dccp_sk(sk); struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct ccid2_seq *next; u64 seq; ccid2_hc_tx_check_sanity(hctx); @@ -250,15 +289,23 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, int len) hctx->ccid2hctx_seqh->ccid2s_seq = seq; hctx->ccid2hctx_seqh->ccid2s_acked = 0; hctx->ccid2hctx_seqh->ccid2s_sent = jiffies; - hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqh->ccid2s_next; - ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx->ccid2hctx_cwnd, - hctx->ccid2hctx_pipe); + next = hctx->ccid2hctx_seqh->ccid2s_next; + /* check if we need to alloc more space */ + if (next == hctx->ccid2hctx_seqt) { + int rc; - if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt) { - /* XXX allocate more space */ - WARN_ON(1); + ccid2_pr_debug("allocating more space in history\n"); + rc = ccid2_hc_tx_alloc_seq(hctx, CCID2_SEQBUF_LEN, GFP_KERNEL); + BUG_ON(rc); /* XXX what do we do? */ + + next = hctx->ccid2hctx_seqh->ccid2s_next; + BUG_ON(next == hctx->ccid2hctx_seqt); } + hctx->ccid2hctx_seqh = next; + + ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx->ccid2hctx_cwnd, + hctx->ccid2hctx_pipe); hctx->ccid2hctx_sent++; @@ -674,8 +721,6 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) { struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid); - int seqcount = ccid2_seq_len; - int i; hctx->ccid2hctx_cwnd = 1; /* Initialize ssthresh to infinity. This means that we will exit the @@ -684,26 +729,12 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) */ hctx->ccid2hctx_ssthresh = ~0; hctx->ccid2hctx_numdupack = 3; + hctx->ccid2hctx_seqbufc = 0; /* XXX init ~ to window size... */ - hctx->ccid2hctx_seqbuf = kmalloc(sizeof(*hctx->ccid2hctx_seqbuf) * - seqcount, gfp_any()); - if (hctx->ccid2hctx_seqbuf == NULL) + if (ccid2_hc_tx_alloc_seq(hctx, CCID2_SEQBUF_LEN, GFP_ATOMIC) != 0) return -ENOMEM; - for (i = 0; i < (seqcount - 1); i++) { - hctx->ccid2hctx_seqbuf[i].ccid2s_next = - &hctx->ccid2hctx_seqbuf[i + 1]; - hctx->ccid2hctx_seqbuf[i + 1].ccid2s_prev = - &hctx->ccid2hctx_seqbuf[i]; - } - hctx->ccid2hctx_seqbuf[seqcount - 1].ccid2s_next = - hctx->ccid2hctx_seqbuf; - hctx->ccid2hctx_seqbuf->ccid2s_prev = - &hctx->ccid2hctx_seqbuf[seqcount - 1]; - - hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqbuf; - hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh; hctx->ccid2hctx_sent = 0; hctx->ccid2hctx_rto = 3 * HZ; hctx->ccid2hctx_srtt = -1; @@ -722,10 +753,13 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) static void ccid2_hc_tx_exit(struct sock *sk) { struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + int i; ccid2_hc_tx_kill_rto_timer(sk); - kfree(hctx->ccid2hctx_seqbuf); - hctx->ccid2hctx_seqbuf = NULL; + + for (i = 0; i < hctx->ccid2hctx_seqbufc; i++) + kfree(hctx->ccid2hctx_seqbuf[i]); + hctx->ccid2hctx_seqbufc = 0; } static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) diff --git a/net/dccp/ccids/ccid2.h b/net/dccp/ccids/ccid2.h index b4cc6c0bf02..2a02ce04ba8 100644 --- a/net/dccp/ccids/ccid2.h +++ b/net/dccp/ccids/ccid2.h @@ -35,6 +35,9 @@ struct ccid2_seq { struct ccid2_seq *ccid2s_next; }; +#define CCID2_SEQBUF_LEN 256 +#define CCID2_SEQBUF_MAX 128 + /** struct ccid2_hc_tx_sock - CCID2 TX half connection * * @ccid2hctx_ssacks - ACKs recv in slow start @@ -53,7 +56,8 @@ struct ccid2_hc_tx_sock { unsigned int ccid2hctx_ssthresh; int ccid2hctx_pipe; int ccid2hctx_numdupack; - struct ccid2_seq *ccid2hctx_seqbuf; + struct ccid2_seq *ccid2hctx_seqbuf[CCID2_SEQBUF_MAX]; + int ccid2hctx_seqbufc; struct ccid2_seq *ccid2hctx_seqh; struct ccid2_seq *ccid2hctx_seqt; long ccid2hctx_rto; -- cgit v1.2.3-70-g09d2 From 374bcf32c86e1b56eab832bbb6b21e636707eab6 Mon Sep 17 00:00:00 2001 From: Andrea Bittau Date: Tue, 19 Sep 2006 13:14:43 -0700 Subject: [DCCP] CCID2: Halve cwnd once upon multiple losses in a single RTT When multiple losses occur in one RTT, the window should be halved only once [a single "congestion event"]. This is now implemented, although not perfectly. Slightly changed the interface for changing the cwnd: pass hctx instead of dp. This is required in order to allow for change_cwnd to be called from _init(). Signed-off-by: Andrea Bittau Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: David S. Miller --- net/dccp/ccids/ccid2.c | 49 +++++++++++++++++++++++++++++++------------------ net/dccp/ccids/ccid2.h | 1 + 2 files changed, 32 insertions(+), 18 deletions(-) (limited to 'net/dccp/ccids/ccid2.h') diff --git a/net/dccp/ccids/ccid2.c b/net/dccp/ccids/ccid2.c index 93a30ae8d07..b88da035865 100644 --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -187,10 +187,8 @@ static void ccid2_change_l_ack_ratio(struct sock *sk, int val) dp->dccps_l_ack_ratio = val; } -static void ccid2_change_cwnd(struct sock *sk, int val) +static void ccid2_change_cwnd(struct ccid2_hc_tx_sock *hctx, int val) { - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); - if (val == 0) val = 1; @@ -234,7 +232,7 @@ static void ccid2_hc_tx_rto_expire(unsigned long data) hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd >> 1; if (hctx->ccid2hctx_ssthresh < 2) hctx->ccid2hctx_ssthresh = 2; - ccid2_change_cwnd(sk, 1); + ccid2_change_cwnd(hctx, 1); /* clear state about stuff we sent */ hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh; @@ -444,7 +442,7 @@ static inline void ccid2_new_ack(struct sock *sk, /* increase every 2 acks */ hctx->ccid2hctx_ssacks++; if (hctx->ccid2hctx_ssacks == 2) { - ccid2_change_cwnd(sk, hctx->ccid2hctx_cwnd + 1); + ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd+1); hctx->ccid2hctx_ssacks = 0; *maxincr = *maxincr - 1; } @@ -457,7 +455,7 @@ static inline void ccid2_new_ack(struct sock *sk, hctx->ccid2hctx_acks++; if (hctx->ccid2hctx_acks >= hctx->ccid2hctx_cwnd) { - ccid2_change_cwnd(sk, hctx->ccid2hctx_cwnd + 1); + ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd + 1); hctx->ccid2hctx_acks = 0; } } @@ -532,6 +530,22 @@ static void ccid2_hc_tx_dec_pipe(struct sock *sk) ccid2_hc_tx_kill_rto_timer(sk); } +static void ccid2_congestion_event(struct ccid2_hc_tx_sock *hctx, + struct ccid2_seq *seqp) +{ + if (time_before(seqp->ccid2s_sent, hctx->ccid2hctx_last_cong)) { + ccid2_pr_debug("Multiple losses in an RTT---treating as one\n"); + return; + } + + hctx->ccid2hctx_last_cong = jiffies; + + ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd >> 1); + hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd; + if (hctx->ccid2hctx_ssthresh < 2) + hctx->ccid2hctx_ssthresh = 2; +} + static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); @@ -542,7 +556,6 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) unsigned char veclen; int offset = 0; int done = 0; - int loss = 0; unsigned int maxincr = 0; ccid2_hc_tx_check_sanity(hctx); @@ -636,7 +649,8 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) !seqp->ccid2s_acked) { if (state == DCCP_ACKVEC_STATE_ECN_MARKED) { - loss = 1; + ccid2_congestion_event(hctx, + seqp); } else ccid2_new_ack(sk, seqp, &maxincr); @@ -688,7 +702,13 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) /* check for lost packets */ while (1) { if (!seqp->ccid2s_acked) { - loss = 1; + ccid2_pr_debug("Packet lost: %llu\n", + seqp->ccid2s_seq); + /* XXX need to traverse from tail -> head in + * order to detect multiple congestion events in + * one ack vector. + */ + ccid2_congestion_event(hctx, seqp); ccid2_hc_tx_dec_pipe(sk); } if (seqp == hctx->ccid2hctx_seqt) @@ -707,14 +727,6 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqt->ccid2s_next; } - if (loss) { - /* XXX do bit shifts guarantee a 0 as the new bit? */ - ccid2_change_cwnd(sk, hctx->ccid2hctx_cwnd >> 1); - hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd; - if (hctx->ccid2hctx_ssthresh < 2) - hctx->ccid2hctx_ssthresh = 2; - } - ccid2_hc_tx_check_sanity(hctx); } @@ -722,7 +734,7 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) { struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid); - hctx->ccid2hctx_cwnd = 1; + ccid2_change_cwnd(hctx, 1); /* Initialize ssthresh to infinity. This means that we will exit the * initial slow-start after the first packet loss. This is what we * want. @@ -741,6 +753,7 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) hctx->ccid2hctx_rttvar = -1; hctx->ccid2hctx_lastrtt = 0; hctx->ccid2hctx_rpdupack = -1; + hctx->ccid2hctx_last_cong = jiffies; hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire; hctx->ccid2hctx_rtotimer.data = (unsigned long)sk; diff --git a/net/dccp/ccids/ccid2.h b/net/dccp/ccids/ccid2.h index 2a02ce04ba8..5b2ef4acb30 100644 --- a/net/dccp/ccids/ccid2.h +++ b/net/dccp/ccids/ccid2.h @@ -71,6 +71,7 @@ struct ccid2_hc_tx_sock { u64 ccid2hctx_rpseq; int ccid2hctx_rpdupack; int ccid2hctx_sendwait; + unsigned long ccid2hctx_last_cong; }; struct ccid2_hc_rx_sock { -- cgit v1.2.3-70-g09d2