Added "provision for rewound PPP frames" that allows receiving

reorder packets to pass to the upper layer without reorder.  It
will improve performance (throughput or loss rate) for PPTP or
L2TP(/IPesc) on networks that latency is unstable such as mobile
network.

As our test environment (bandwidth: 6Mbps, latency: 50ms for 97% of
traffic and 52ms for rest of traffic), throughput has changed from
0.76MB to 2.17MB on file upload by PPTP connected Windows Vista
ftp.exe.

Developed by UMEZAWA Takeshi at IIJ.

ok jmatthew@
tested jmatthew@ and myself.

4 files changed, 172 insertions, 66 deletions

diff --git a/sys/net/if_pppx.c b/sys/net/if_pppx.c
index 09e1133feae..f4f12ce9333 100644
--- a/sys/net/if_pppx.c
+++ b/sys/net/if_pppx.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_pppx.c,v 1.11 2011/08/21 09:00:15 jmatthew Exp $ */
+/*	$OpenBSD: if_pppx.c,v 1.12 2011/10/15 03:24:11 yasuoka Exp $ */
 
 /*
  * Copyright (c) 2010 Claudio Jeker <claudio@openbsd.org>
@@ -805,9 +805,13 @@ pppx_add_session(struct pppx_dev *pxd, struct pipex_session_req *req)
 #endif
 #ifdef PIPEX_MPPE
 	if ((req->pr_ppp_flags & PIPEX_PPP_MPPE_ACCEPTED) != 0)
-		pipex_mppe_req_init(&req->pr_mppe_recv, &session->mppe_recv);
+		pipex_session_init_mppe_recv(session,
+		    req->pr_mppe_recv.stateless, req->pr_mppe_recv.keylenbits,
+		    req->pr_mppe_recv.master_key);
 	if ((req->pr_ppp_flags & PIPEX_PPP_MPPE_ENABLED) != 0)
-		pipex_mppe_req_init(&req->pr_mppe_send, &session->mppe_send);
+		pipex_session_init_mppe_send(session,
+		    req->pr_mppe_send.stateless, req->pr_mppe_send.keylenbits,
+		    req->pr_mppe_send.master_key);
 
 	if (pipex_session_is_mppe_required(session)) {
 		if (!pipex_session_is_mppe_enabled(session) ||
diff --git a/sys/net/pipex.c b/sys/net/pipex.c
index 93955f394d7..87be24931e3 100644
--- a/sys/net/pipex.c
+++ b/sys/net/pipex.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pipex.c,v 1.21 2011/07/09 04:11:15 dhill Exp $	*/
+/*	$OpenBSD: pipex.c,v 1.22 2011/10/15 03:24:11 yasuoka Exp $	*/
 
 /*-
  * Copyright (c) 2009 Internet Initiative Japan Inc.
@@ -119,9 +119,6 @@ int pipex_debug = 0;		/* systcl net.inet.ip.pipex_debug */
 /* PPP compression == MPPE is assumed, so don't answer CCP Reset-Request. */
 #define PIPEX_NO_CCP_RESETACK	1
 
-/* see the comment on pipex_mppe_input() */
-#define	WORKAROUND_OUT_OF_SEQUENCE_PPP_FRAMING	1
-
 /************************************************************************
  * Core functions
  ************************************************************************/
@@ -394,9 +391,13 @@ pipex_add_session(struct pipex_session_req *req,
 #endif
 #ifdef PIPEX_MPPE
     	if ((req->pr_ppp_flags & PIPEX_PPP_MPPE_ACCEPTED) != 0)
-		pipex_mppe_req_init(&req->pr_mppe_recv, &session->mppe_recv);
+		pipex_session_init_mppe_recv(session,
+		    req->pr_mppe_recv.stateless, req->pr_mppe_recv.keylenbits,
+		    req->pr_mppe_recv.master_key);
     	if ((req->pr_ppp_flags & PIPEX_PPP_MPPE_ENABLED) != 0)
-		pipex_mppe_req_init(&req->pr_mppe_send, &session->mppe_send);
+		pipex_session_init_mppe_send(session,
+		    req->pr_mppe_send.stateless, req->pr_mppe_send.keylenbits,
+		    req->pr_mppe_send.master_key);
 
 	if (pipex_session_is_mppe_required(session)) {
 		if (!pipex_session_is_mppe_enabled(session) ||
@@ -609,6 +610,9 @@ pipex_destroy_session(struct pipex_session *session)
 		pipex_timer_stop();
 
 	splx(s);
+
+	if (session->mppe_recv.old_session_keys)
+		free(session->mppe_recv.old_session_keys, M_TEMP);
 	free(session, M_TEMP);
 
 	return (0);
@@ -1614,6 +1618,7 @@ pipex_pptp_input(struct mbuf *m0, struct pipex_session *session)
 	struct ip *ip;
 	struct pipex_gre_header *gre;
 	struct pipex_pptp_session *pptp_session;
+	int rewind = 0;
 
 	KASSERT(m0->m_pkthdr.len >= PIPEX_IPGRE_HDRLEN);
 	pptp_session = &session->proto.pptp;
@@ -1650,11 +1655,11 @@ pipex_pptp_input(struct mbuf *m0, struct pipex_session *session)
 		if (ack + 1 == pptp_session->snd_una) {
 			/* ack has not changed before */
 		} else if (SEQ32_LT(ack, pptp_session->snd_una)) {
-			reason = "ack out of sequence";
-			goto inseq;
+			/* OoO ack packets should not be dropped. */
+			rewind = 1;
 		} else if (SEQ32_GT(ack, pptp_session->snd_nxt)) {
 			reason = "ack for unknown sequence";
-			goto inseq;
+			goto out_seq;
 		} else {
 			ack++;
 			pptp_session->snd_una = ack;
@@ -1665,8 +1670,12 @@ pipex_pptp_input(struct mbuf *m0, struct pipex_session *session)
 		goto not_ours;
 	}
 	if (SEQ32_LT(seq, pptp_session->rcv_nxt)) {
-		reason = "out of sequence";
-		goto inseq;
+		rewind = 1;
+		if (SEQ32_LT(seq,
+		    pptp_session->rcv_nxt - PIPEX_REWIND_LIMIT)) {
+			reason = "out of sequence";
+			goto out_seq;
+		}
 	} else if (SEQ32_GE(seq, pptp_session->rcv_nxt + 
 	    pptp_session->maxwinsz)) {
 		pipex_session_log(session, LOG_DEBUG, 
@@ -1678,18 +1687,24 @@ pipex_pptp_input(struct mbuf *m0, struct pipex_session *session)
 
 	seq++;
 	nseq = SEQ32_SUB(seq, pptp_session->rcv_nxt);
-	pptp_session->rcv_nxt = seq;
-
-	if (SEQ32_SUB(seq, pptp_session->rcv_acked) >
-	    roundup(pptp_session->winsz, 2) / 2) /* Send ack only packet. */
-		pipex_pptp_output(NULL, session, 0, 1);
+	if (!rewind) {
+		pptp_session->rcv_nxt = seq;
+		if (SEQ32_SUB(seq, pptp_session->rcv_acked) >
+		    roundup(pptp_session->winsz, 2) / 2) /* Send ack only packet. */
+			pipex_pptp_output(NULL, session, 0, 1);
+	}
 
 	if ((m0 = pipex_common_input(session, m0, hlen, (int)ntohs(gre->len)))
 	    == NULL) {
 		/* ok,  The packet is for PIPEX */
-		session->proto.pptp.rcv_gap += nseq;
-		return (m0);
+		if (!rewind)
+			session->proto.pptp.rcv_gap += nseq;
+		return (NULL);
 	}
+
+	if (rewind)
+		goto out_seq;
+
 not_ours:
 	/* revert original seq/ack values */
 	seq--;
@@ -1720,7 +1735,7 @@ not_ours:
 	}
 
 	return (m0);
-inseq:
+out_seq:
 	pipex_session_log(session, LOG_DEBUG, 
 	    "Received bad data packet: %s: seq=%u(%u-%u) ack=%u(%u-%u)",
 	    reason, seq, pptp_session->rcv_nxt,
@@ -2054,6 +2069,7 @@ pipex_l2tp_input(struct mbuf *m0, int off0, struct pipex_session *session)
 	int length, offset, hlen, nseq;
 	u_char *cp, *nsp, *nrp;
 	uint16_t flags, ns = 0, nr = 0;
+	int rewind = 0;
 
 	length = offset = ns = nr = 0;
 	l2tp_session = &session->proto.l2tp;
@@ -2098,13 +2114,17 @@ pipex_l2tp_input(struct mbuf *m0, int off0, struct pipex_session *session)
 		    SEQ16_LE(nr, l2tp_session->ns_nxt))	
 			/* update 'ns_una' only if the ns is in valid range */
 			l2tp_session->ns_una = nr;
-
-		if (SEQ16_LT(ns, l2tp_session->nr_nxt))
-			goto out_seq;
+		if (SEQ16_LT(ns, l2tp_session->nr_nxt)) {
+			rewind = 1;
+			if (SEQ16_LT(ns,
+			    l2tp_session->nr_nxt - PIPEX_REWIND_LIMIT))
+				goto out_seq;
+		}
 
 		ns++;
 		nseq = SEQ16_SUB(ns, l2tp_session->nr_nxt);
-		l2tp_session->nr_nxt = ns;
+		if (!rewind)
+			l2tp_session->nr_nxt = ns;
 	}
 	if (flags & PIPEX_L2TP_FLAG_OFFSET)
 		GETSHORT(offset, cp);
@@ -2113,10 +2133,14 @@ pipex_l2tp_input(struct mbuf *m0, int off0, struct pipex_session *session)
 	hlen += off0 + offset;
 	if ((m0 = pipex_common_input(session, m0, hlen, length)) == NULL) {
 		/* ok,  The packet is for PIPEX */
-		session->proto.l2tp.nr_gap += nseq;
+		if (!rewind)
+			session->proto.l2tp.nr_gap += nseq;
 		return (NULL);
 	}
 
+	if (rewind)
+		goto out_seq;
+
 	/*
 	 * overwrite sequence numbers to adjust a gap between pipex and
 	 * userland.
@@ -2279,17 +2303,23 @@ pipex_l2tp_userland_output(struct mbuf *m0, struct pipex_session *session)
  * MPPE
  ***********************************************************************/
 #define	PIPEX_COHERENCY_CNT_MASK		0x0fff
-
 Static void
-pipex_mppe_req_init(struct pipex_mppe_req *mppe_req, struct pipex_mppe *mppe)
+pipex_mppe_init(struct pipex_mppe *mppe, int stateless, int keylenbits,
+    u_char *master_key, int has_oldkey)
 {
-	if (mppe_req->stateless)
+	memset(mppe, 0, sizeof(struct pipex_mppe));
+	if (stateless)
 		mppe->stateless = 1;
-	memcpy(mppe->master_key, mppe_req->master_key,
-	    sizeof(mppe->master_key));
+	if (has_oldkey)
+		mppe->old_session_keys =
+		    malloc(PIPEX_MPPE_KEYLEN * PIPEX_MPPE_NOLDKEY,
+		    M_TEMP, M_WAITOK);
+	else
+		mppe->old_session_keys = NULL;
+	memcpy(mppe->master_key, master_key, sizeof(mppe->master_key));
 
-	mppe->keylenbits = mppe_req->keylenbits;
-	switch (mppe_req->keylenbits) {
+	mppe->keylenbits = keylenbits;
+	switch (keylenbits) {
 	case 40:
 	case 56:
 		mppe->keylen = 8;
@@ -2302,7 +2332,25 @@ pipex_mppe_req_init(struct pipex_mppe_req *mppe_req, struct pipex_mppe *mppe)
 	GetNewKeyFromSHA(mppe->master_key, mppe->master_key, mppe->keylen,
 	    mppe->session_key);
 	pipex_mppe_reduce_key(mppe);
-	rc4_keysetup(&mppe->rc4ctx, mppe->session_key, mppe->keylen);
+	pipex_mppe_setkey(mppe);
+}
+
+void
+pipex_session_init_mppe_recv(struct pipex_session *session, int stateless,
+    int keylenbits, u_char *master_key)
+{
+	pipex_mppe_init(&session->mppe_recv, stateless, keylenbits,
+	    master_key, stateless);
+	session->ppp_flags |= PIPEX_PPP_MPPE_ACCEPTED;
+}
+
+void
+pipex_session_init_mppe_send(struct pipex_session *session, int stateless,
+    int keylenbits, u_char *master_key)
+{
+	pipex_mppe_init(&session->mppe_send, stateless, keylenbits,
+	    master_key, 0);
+	session->ppp_flags |= PIPEX_PPP_MPPE_ENABLED;
 }
 
 #include <crypto/sha1.h>
@@ -2354,17 +2402,23 @@ Static void
 mppe_key_change(struct pipex_mppe *mppe)
 {
 	u_char interim[16];
-	struct pipex_mppe keychg;	/* just for rc4ctx */
+	struct rc4_ctx keychg;
 
 	memset(&keychg, 0, sizeof(keychg));
 
 	GetNewKeyFromSHA(mppe->master_key, mppe->session_key, mppe->keylen,
 	    interim);
 
-	rc4_keysetup(&keychg.rc4ctx, interim, mppe->keylen);
-	rc4_crypt(&keychg.rc4ctx, interim, mppe->session_key, mppe->keylen);
+	rc4_keysetup(&keychg, interim, mppe->keylen);
+	rc4_crypt(&keychg, interim, mppe->session_key, mppe->keylen);
 
 	pipex_mppe_reduce_key(mppe);
+
+	if (mppe->old_session_keys) {
+		int idx = mppe->coher_cnt & PIPEX_MPPE_OLDKEYMASK;
+		memcpy(mppe->old_session_keys[idx],
+		    mppe->session_key, PIPEX_MPPE_KEYLEN);
+	}
 }
 
 Static void
@@ -2375,6 +2429,7 @@ pipex_mppe_input(struct mbuf *m0, struct pipex_session *session)
 	uint16_t coher_cnt;
 	struct mbuf *m1;
 	u_char *cp;
+	int rewind = 0;
 
 	/* pullup */
 	PIPEX_PULLUP(m0, sizeof(coher_cnt));
@@ -2403,7 +2458,6 @@ pipex_mppe_input(struct mbuf *m0, struct pipex_session *session)
 	/* adjust mbuf */
 	m_adj(m0, sizeof(coher_cnt));
 
-#ifdef	WORKAROUND_OUT_OF_SEQUENCE_PPP_FRAMING
 	/*
 	 * L2TP data session may be used without sequencing, PPP frames may
 	 * arrive in disorder.  The 'coherency counter' of MPPE detects such
@@ -2421,22 +2475,29 @@ pipex_mppe_input(struct mbuf *m0, struct pipex_session *session)
 	if (coher_cnt < mppe->coher_cnt)
 		coher_cnt0 += 0x1000;
 	if (coher_cnt0 - mppe->coher_cnt > 0x0f00) {
-		pipex_session_log(session, LOG_DEBUG,
-		    "Workaround the out-of-sequence PPP framing problem: "
-		    "%d => %d", mppe->coher_cnt, coher_cnt);
-		goto drop;
+		if (!mppe->stateless ||
+		    coher_cnt0 - mppe->coher_cnt
+		    <= 0x1000 - PIPEX_MPPE_NOLDKEY) {
+			pipex_session_log(session, LOG_DEBUG,
+			    "Workaround the out-of-sequence PPP framing problem: "
+			    "%d => %d", mppe->coher_cnt, coher_cnt);
+			goto drop;
+		}
+		rewind = 1;
 	}
     }
-#endif
+
 	if (mppe->stateless != 0) {
-		mppe_key_change(mppe);
-		while (mppe->coher_cnt != coher_cnt) {
+		if (!rewind) {
 			mppe_key_change(mppe);
-			mppe->coher_cnt++;
-			mppe->coher_cnt &= PIPEX_COHERENCY_CNT_MASK;
-			pktloss++;
+			while (mppe->coher_cnt != coher_cnt) {
+				mppe->coher_cnt++;
+				mppe->coher_cnt &= PIPEX_COHERENCY_CNT_MASK;
+				mppe_key_change(mppe);
+				pktloss++;
+			}
 		}
-		flushed = 1;
+		pipex_mppe_setoldkey(mppe, coher_cnt);
 	} else {
 		if (flushed) {
 			if (coher_cnt < mppe->coher_cnt) {
@@ -2461,26 +2522,27 @@ pipex_mppe_input(struct mbuf *m0, struct pipex_session *session)
 			mppe_key_change(mppe);
 			flushed = 1;
 		}
+		if (flushed)
+			pipex_mppe_setkey(mppe);
 	}
-#ifndef	WORKAROUND_OUT_OF_SEQUENCE_PPP_FRAMING
+
 	if (pktloss > 1000) {
 		pipex_session_log(session, LOG_DEBUG,
 		    "%d packets loss.", pktloss);
 	}
-#endif
-	if (flushed)
-		rc4_keysetup(&mppe->rc4ctx, mppe->session_key, mppe->keylen);
 
 	/* decrypt ppp payload */
 	for (m1 = m0; m1; m1 = m1->m_next) {
 		cp = mtod(m1, u_char *);
 		len = m1->m_len;
-		rc4_crypt(&mppe->rc4ctx, cp, cp, len);
+		pipex_mppe_crypt(mppe, len, cp, cp);
 	}
 
-	/* update coher_cnt */
-	mppe->coher_cnt++;
-	mppe->coher_cnt &= PIPEX_COHERENCY_CNT_MASK;
+	if (!rewind) {
+		/* update coher_cnt */
+		mppe->coher_cnt++;
+		mppe->coher_cnt &= PIPEX_COHERENCY_CNT_MASK;
+	}
 
 	pipex_ppp_input(m0, session, 1);
 
@@ -2547,7 +2609,7 @@ pipex_mppe_output(struct mbuf *m0, struct pipex_session *session,
 	}
 
 	if (flushed)
-		rc4_keysetup(&mppe->rc4ctx, mppe->session_key, mppe->keylen);
+		pipex_mppe_setkey(mppe);
 
 	PIPEX_MPPE_DBG((session, LOG_DEBUG, "out coher_cnt=%03x %s%s",
 	    mppe->coher_cnt, (flushed) ? "[flushed]" : "",
@@ -2572,7 +2634,7 @@ pipex_mppe_output(struct mbuf *m0, struct pipex_session *session,
 			len -= offsetof(struct mppe_header, protocol);
 			cp += offsetof(struct mppe_header, protocol);
 		}
-		rc4_crypt(&mppe->rc4ctx, cp, cp, len);
+		pipex_mppe_crypt(mppe, len, cp, cp);
 	}
 
 	pipex_ppp_output(m0, session, PPP_COMP);
@@ -2939,7 +3001,35 @@ pipex_sockaddr_compar_addr(struct sockaddr *a, struct sockaddr *b)
 		    sizeof(struct in6_addr));
 	}
 	panic("pipex_sockaddr_compar_addr: unknown address family");
-	return -1;
+
+	return (-1);
+}
+
+Static inline int
+pipex_mppe_setkey(struct pipex_mppe *mppe)
+{
+	rc4_keysetup(&mppe->rc4ctx, mppe->session_key, mppe->keylen);
+
+	return (0);
+}
+
+Static inline int
+pipex_mppe_setoldkey(struct pipex_mppe *mppe, uint16_t coher_cnt)
+{
+	KASSERT(mppe->old_session_keys != NULL);
+
+	rc4_keysetup(&mppe->rc4ctx,
+	    mppe->old_session_keys[coher_cnt & PIPEX_MPPE_OLDKEYMASK],
+	    mppe->keylen);
+
+	return (0);
+}
+
+Static inline void
+pipex_mppe_crypt(struct pipex_mppe *mppe, int len, u_char *indata,
+    u_char *outdata)
+{
+	rc4_crypt(&mppe->rc4ctx, indata, outdata, len);
 }
 
 int
diff --git a/sys/net/pipex.h b/sys/net/pipex.h
index 391e69ea54d..cddbbefc893 100644
--- a/sys/net/pipex.h
+++ b/sys/net/pipex.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pipex.h,v 1.9 2011/07/08 18:30:17 yasuoka Exp $	*/
+/*	$OpenBSD: pipex.h,v 1.10 2011/10/15 03:24:11 yasuoka Exp $	*/
 
 /*
  * Copyright (c) 2009 Internet Initiative Japan Inc.
@@ -216,6 +216,11 @@ struct pipex_session  *pipex_l2tp_userland_lookup_session_ipv4 (struct mbuf *, s
 struct pipex_session  *pipex_l2tp_userland_lookup_session_ipv6 (struct mbuf *, struct in6_addr);
 struct mbuf           *pipex_l2tp_userland_output (struct mbuf *, struct pipex_session *);
 int                   pipex_ioctl (struct pipex_iface_context *, int, caddr_t);
+void                  pipex_session_init_mppe_recv(struct pipex_session *, int,
+int, u_char *);
+void                  pipex_session_init_mppe_send(struct pipex_session *, int,
+int, u_char *);
+
 __END_DECLS
 
 #endif /* _KERNEL */
diff --git a/sys/net/pipex_local.h b/sys/net/pipex_local.h
index 11be4715ec8..dcbf9c1ef35 100644
--- a/sys/net/pipex_local.h
+++ b/sys/net/pipex_local.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pipex_local.h,v 1.12 2011/07/08 19:34:04 yasuoka Exp $	*/
+/*	$OpenBSD: pipex_local.h,v 1.13 2011/10/15 03:24:11 yasuoka Exp $	*/
 
 /*
  * Copyright (c) 2009 Internet Initiative Japan Inc.
@@ -37,6 +37,8 @@
 #define	PIPEX_PPPOE	1
 #define	PIPEX_MPPE	1
 
+#define PIPEX_REWIND_LIMIT		64
+
 #define PIPEX_ENABLED			0x0001
 
 #ifndef	LOG_PPPAC
@@ -59,6 +61,9 @@
 #define	NNBY	8	/* number of bits of a byte */
 #endif
 
+#define PIPEX_MPPE_NOLDKEY		64 /* should be power of two */
+#define PIPEX_MPPE_OLDKEYMASK		(PIPEX_MPPE_NOLDKEY - 1)
+
 #ifdef PIPEX_MPPE
 /* mppe rc4 key */
 struct pipex_mppe {
@@ -71,6 +76,7 @@ struct pipex_mppe {
 	struct  rc4_ctx rc4ctx;
 	u_char master_key[PIPEX_MPPE_KEYLEN];	/* master key of MPPE */
 	u_char session_key[PIPEX_MPPE_KEYLEN];	/* session key of MPPE */
+	u_char (*old_session_keys)[PIPEX_MPPE_KEYLEN];	/* old session keys */
 };
 #endif /* PIPEX_MPPE */
 
@@ -402,7 +408,7 @@ Static struct pipex_session  *pipex_l2tp_userland_lookup_session(struct mbuf *,
 #endif
 
 #ifdef PIPEX_MPPE
-Static void                  pipex_mppe_req_init (struct pipex_mppe_req *, struct pipex_mppe *);
+Static void                  pipex_mppe_init (struct pipex_mppe *, int, int, u_char *, int);
 Static void                  GetNewKeyFromSHA (u_char *, u_char *, int, u_char *);
 Static void                  pipex_mppe_reduce_key (struct pipex_mppe *);
 Static void                  mppe_key_change (struct pipex_mppe *);
@@ -410,8 +416,9 @@ Static void                  pipex_mppe_input (struct mbuf *, struct pipex_sessi
 Static void                  pipex_mppe_output (struct mbuf *, struct pipex_session *, uint16_t);
 Static void                  pipex_ccp_input (struct mbuf *, struct pipex_session *);
 Static int                   pipex_ccp_output (struct pipex_session *, int, int);
-Static inline int            rc4_key(struct pipex_mppe *, int, u_char *);
-Static inline void           rc4(struct pipex_mppe *, int, u_char *, u_char *);
+Static inline int            pipex_mppe_setkey(struct pipex_mppe *);
+Static inline int            pipex_mppe_setoldkey(struct pipex_mppe *, uint16_t);
+Static inline void           pipex_mppe_crypt(struct pipex_mppe *, int, u_char *, u_char *);
 #endif
 
 Static struct mbuf           *adjust_tcp_mss (struct mbuf *, int);