Skip to contentSkip to conversation

: Ackvec patches by Bittau

PATCH In review Gerrit Renker 1 participant 1 message Oct 24, 2006 Networking

lore
Share & tools
lore
#0 lore raw

PATCH 4/17 : Ackvec patches by Bittau

These patches were written by Andrea Bittau and
were posted and signed-off by him as

	 01_ackvec_opt
	 02_ackvec_speed
	 03_ackvec_ccid_speed

Given that he achieved Gigabit speed with these patches, I think they should really be `in'.

Original commit messages:
============
[ACKVEC]: Split long ack vectors across multiple options
ack vectors grow proportional to the window size. If an ack vector does not fit into a single option, it must be spread across multiple options. This patch will allow for windows to grow larger.
http://www.mail-archive.com/[email protected]/msg00399.html

[ACKVEC - Optimization]: Do not traverse records if none will be found
Do not traverse the list of ack vector records [proportional to window size] when we know we will not find what we are looking for. This is especially useful because ack vectors are checked twice:
1) Upon parsing of options.
2) Upon notification of a new ack.

All of the work will occur during check #1. Therefore, when check #2 is performed, no new work will be done. This is now "detected" and there is no performance hit when doing #2.
http://www.mail-archive.com/[email protected]/msg00400.html

[ACKVEC & CCID2]: Code optimizations
These are code optimizations which are relevant when dealing with large windows. They are not coded the way I would like to, but they do the job for the short-term. This patch should be more neat.
http://www.mail-archive.com/[email protected]/msg00401.html

------------------------------------------------------------------------------

 net/dccp/ackvec.c      |  115 ++++++++++++++++++++++++++++++-------------------
 net/dccp/ackvec.h      |   22 ++++-----
 net/dccp/ccids/ccid2.c |   22 ++++++++-
 net/dccp/ccids/ccid2.h |    3 -
 net/dccp/options.c     |    7 +-
 5 files changed, 109 insertions(+), 60 deletions(-)

------------------------------------------------------------------------------

net/dccp/options.c +4 -3
index fb0db1f..81c53e1 100644
@@ -76,6 +76,7 @@ #endif
 	u32 elapsed_time;
 	int rc;
 	int mandatory = 0;
+	u64 ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
 
 	memset(opt_recv, 0, sizeof(*opt_recv));
 
@@ -152,9 +153,9 @@ #endif
 			if (pkt_type = DCCP_PKT_DATA)
 				break;
 
-			if (dccp_msk(sk)->dccpms_send_ack_vector &&
-			    dccp_ackvec_parse(sk, skb, opt, value, len))
-				goto out_invalid_option;
+			if (dccp_msk(sk)->dccpms_send_ack_vector)
+				ackno = dccp_ackvec_parse(sk, ackno, opt,
+							  value, len);
 			break;
 		case DCCPO_TIMESTAMP:
 			if (len != 4)
net/dccp/ccids/ccid2.h +2 -1
index 5b2ef4a..ebd7949 100644
@@ -35,7 +35,7 @@ struct ccid2_seq {
 	struct ccid2_seq	*ccid2s_next;
 };
 
-#define CCID2_SEQBUF_LEN 256
+#define CCID2_SEQBUF_LEN 1024
 #define CCID2_SEQBUF_MAX 128
 
 /** struct ccid2_hc_tx_sock - CCID2 TX half connection
@@ -72,6 +72,7 @@ struct ccid2_hc_tx_sock {
 	int			ccid2hctx_rpdupack;
 	int			ccid2hctx_sendwait;
 	unsigned long		ccid2hctx_last_cong;
+	u64			ccid2hctx_high_ack;
 };
 
 struct ccid2_hc_rx_sock {
net/dccp/ccids/ccid2.c +20 -2
index 2fbb84b..e0f85e9 100644
@@ -618,7 +618,17 @@ static void ccid2_hc_tx_packet_recv(stru
 	}
 
 	ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
-	seqp = hctx->ccid2hctx_seqh->ccid2s_prev;
+	if (ackno > hctx->ccid2hctx_high_ack)
+		hctx->ccid2hctx_high_ack = ackno;
+
+	seqp = hctx->ccid2hctx_seqt;
+	while (before48(seqp->ccid2s_seq, ackno)) {
+		seqp = seqp->ccid2s_next;
+		if (seqp = hctx->ccid2hctx_seqh) {
+			seqp = hctx->ccid2hctx_seqh->ccid2s_prev;
+			break;
+		}
+	}
 
 	/* If in slow-start, cwnd can increase at most Ack Ratio / 2 packets for
 	 * this single ack.  I round up.
@@ -695,7 +705,14 @@ static void ccid2_hc_tx_packet_recv(stru
 	/* The state about what is acked should be correct now
 	 * Check for NUMDUPACK
 	 */
-	seqp = hctx->ccid2hctx_seqh->ccid2s_prev;
+	seqp = hctx->ccid2hctx_seqt;
+	while (seqp->ccid2s_seq < hctx->ccid2hctx_high_ack) {
+		seqp = seqp->ccid2s_next;
+		if (seqp = hctx->ccid2hctx_seqh) {
+			seqp = hctx->ccid2hctx_seqh->ccid2s_prev;
+			break;
+		}
+	}
 	done = 0;
 	while (1) {
 		if (seqp->ccid2s_acked) {
@@ -769,6 +786,7 @@ static int ccid2_hc_tx_init(struct ccid 
 	hctx->ccid2hctx_lastrtt  = 0;
 	hctx->ccid2hctx_rpdupack = -1;
 	hctx->ccid2hctx_last_cong = jiffies;
+	hctx->ccid2hctx_high_ack = 0;
 
 	hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire;
 	hctx->ccid2hctx_rtotimer.data	  = (unsigned long)sk;
net/dccp/ackvec.h +11 -11
index cf8f20c..da1bec8 100644
@@ -17,7 +17,9 @@ #include <linux/time.h>
 #include <linux/types.h>
 
 /* Read about the ECN nonce to see why it is 253 */
-#define DCCP_MAX_ACKVEC_LEN 253
+#define DCCP_MAX_ACKVEC_OPT_LEN 253
+/* We can spread an ack vector across multiple options */
+#define DCCP_MAX_ACKVEC_LEN     (DCCP_MAX_ACKVEC_OPT_LEN * 2)
 
 #define DCCP_ACKVEC_STATE_RECEIVED	0
 #define DCCP_ACKVEC_STATE_ECN_MARKED	(1 << 6)
@@ -31,7 +33,7 @@ #define DCCP_ACKVEC_LEN_MASK		0x3F /* 00
  * This data structure is the one defined in RFC 4340, Appendix A.
  *
  * @dccpav_buf_head - circular buffer head
- * @dccpav_buf_tail - circular buffer tail
+ * @dccpav_vec_len -
  * @dccpav_buf_ackno - ack # of the most recent packet acknowledgeable in the
  * 		       buffer (i.e. %dccpav_buf_head)
  * @dccpav_buf_nonce - the one-bit sum of the ECN Nonces on all packets acked
@@ -41,20 +43,19 @@ #define DCCP_ACKVEC_LEN_MASK		0x3F /* 00
  * Ack Vectors it has recently sent. For each packet sent carrying an
  * Ack Vector, it remembers four variables:
  *
- * @dccpav_ack_ptr - the value of buf_head at the time of acknowledgement.
  * @dccpav_records - list of dccp_ackvec_record
+ * @dccpav_buf_nonce -
  * @dccpav_ack_nonce - the one-bit sum of the ECN Nonces for all State 0.
  *
- * @dccpav_time		- the time in usecs
+ * @dccpav_time	- the time in usecs
  * @dccpav_buf - circular buffer of acknowledgeable packets
  */
 struct dccp_ackvec {
 	u64		dccpav_buf_ackno;
 	struct list_head dccpav_records;
 	struct timeval	dccpav_time;
-	u8		dccpav_buf_head;
-	u8		dccpav_ack_ptr;
-	u8		dccpav_vec_len;
+	int		dccpav_buf_head;
+	int		dccpav_vec_len;
 	u8		dccpav_buf_nonce;
 	u8		dccpav_ack_nonce;
 	u8		dccpav_buf[DCCP_MAX_ACKVEC_LEN];
@@ -77,9 +78,9 @@ struct dccp_ackvec_record {
 	struct list_head dccpavr_node;
 	u64		 dccpavr_ack_seqno;
 	u64		 dccpavr_ack_ackno;
-	u8		 dccpavr_ack_ptr;
+	int		 dccpavr_ack_ptr;
 	u8		 dccpavr_ack_nonce;
-	u8		 dccpavr_sent_len;
+	int		 dccpavr_sent_len;
 };
 
 struct sock;
@@ -94,10 +95,9 @@ extern void dccp_ackvec_free(struct dccp
 
 extern int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
 			   const u64 ackno, const u8 state);
-
 extern void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av,
 					struct sock *sk, const u64 ackno);
-extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
+extern u64 dccp_ackvec_parse(struct sock *sk, u64 ackno,
 			     const u8 opt, const u8 *value, const u8 len);
 
 extern int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb);
net/dccp/ackvec.c +72 -43

201 lines not on this page · raw message