net: Reorder incoming packets in PPPoLAC and PPPoPNS.android-samsung-2.6.35

PPP handles packet loss but does not work with out of order packets.
This change performs reordering of incoming data packets within a
sliding window of one second. Since sequence number is optional,
receiving a packet without it will drop all queued packets.

Currently the logic is triggered by incoming packets, so queued
packets have to wait till another packet is arrived. It is done for
simplicity since no additional locks or threads are required. For
reliable protocols, a retransmission will kick it. For unreliable
protocols, queued packets just seem like packet loss. Time-critical
protocols might be broken, but they never work with queueing anyway.

Signed-off-by: Chia-chi Yeh <chiachi@android.com>

3 files changed, 173 insertions, 31 deletions

diff --git a/drivers/net/pppolac.c b/drivers/net/pppolac.c
index af3202a920a..c94b8507d92 100644
--- a/drivers/net/pppolac.c
+++ b/drivers/net/pppolac.c
@@ -15,12 +15,15 @@
  */
 
 /* This driver handles L2TP data packets between a UDP socket and a PPP channel.
- * To keep things simple, only one session per socket is permitted. Packets are
- * sent via the socket, so it must keep connected to the same address. One must
- * not set sequencing in ICCN but let LNS controll it. Currently this driver
- * only works on IPv4 due to the lack of UDP encapsulation support in IPv6. */
+ * The socket must keep connected, and only one session per socket is permitted.
+ * Sequencing of outgoing packets is controlled by LNS. Incoming packets with
+ * sequences are reordered within a sliding window of one second. Currently
+ * reordering only happens when a packet is received. It is done for simplicity
+ * since no additional locks or threads are required. This driver only works on
+ * IPv4 due to the lack of UDP encapsulation support in IPv6. */
 
 #include <linux/module.h>
+#include <linux/jiffies.h>
 #include <linux/workqueue.h>
 #include <linux/skbuff.h>
 #include <linux/file.h>
@@ -53,14 +56,28 @@ static inline union unaligned *unaligned(void *ptr)
 	return (union unaligned *)ptr;
 }
 
+struct meta {
+	__u32 sequence;
+	__u32 timestamp;
+};
+
+static inline struct meta *skb_meta(struct sk_buff *skb)
+{
+	return (struct meta *)skb->cb;
+}
+
+/******************************************************************************/
+
 static int pppolac_recv_core(struct sock *sk_udp, struct sk_buff *skb)
 {
 	struct sock *sk = (struct sock *)sk_udp->sk_user_data;
 	struct pppolac_opt *opt = &pppox_sk(sk)->proto.lac;
+	struct meta *meta = skb_meta(skb);
+	__u32 now = jiffies;
 	__u8 bits;
 	__u8 *ptr;
 
-	/* Drop the packet if it is too short. */
+	/* Drop the packet if L2TP header is missing. */
 	if (skb->len < sizeof(struct udphdr) + 6)
 		goto drop;
 
@@ -99,9 +116,12 @@ static int pppolac_recv_core(struct sock *sk_udp, struct sk_buff *skb)
 	if (unaligned(ptr)->u32 != opt->local)
 		goto drop;
 
-	/* Check the sequence if it is present. According to RFC 2661 section
-	 * 5.4, the only thing to do is to update opt->sequencing. */
-	opt->sequencing = bits & L2TP_SEQUENCE_BIT;
+	/* Check the sequence if it is present. */
+	if (bits & L2TP_SEQUENCE_BIT) {
+		meta->sequence = ptr[4] << 8 | ptr[5];
+		if ((__s16)(meta->sequence - opt->recv_sequence) < 0)
+			goto drop;
+	}
 
 	/* Skip PPP address and control if they are present. */
 	if (skb->len >= 2 && skb->data[0] == PPP_ADDR &&
@@ -112,7 +132,54 @@ static int pppolac_recv_core(struct sock *sk_udp, struct sk_buff *skb)
 	if (skb->len >= 1 && skb->data[0] & 1)
 		skb_push(skb, 1)[0] = 0;
 
-	/* Finally, deliver the packet to PPP channel. */
+	/* Drop the packet if PPP protocol is missing. */
+	if (skb->len < 2)
+		goto drop;
+
+	/* Perform reordering if sequencing is enabled. */
+	atomic_set(&opt->sequencing, bits & L2TP_SEQUENCE_BIT);
+	if (bits & L2TP_SEQUENCE_BIT) {
+		struct sk_buff *skb1;
+
+		/* Insert the packet into receive queue in order. */
+		skb_set_owner_r(skb, sk);
+		skb_queue_walk(&sk->sk_receive_queue, skb1) {
+			struct meta *meta1 = skb_meta(skb1);
+			__s16 order = meta->sequence - meta1->sequence;
+			if (order == 0)
+				goto drop;
+			if (order < 0) {
+				meta->timestamp = meta1->timestamp;
+				skb_insert(skb1, skb, &sk->sk_receive_queue);
+				skb = NULL;
+				break;
+			}
+		}
+		if (skb) {
+			meta->timestamp = now;
+			skb_queue_tail(&sk->sk_receive_queue, skb);
+		}
+
+		/* Remove packets from receive queue as long as
+		 * 1. the receive buffer is full,
+		 * 2. they are queued longer than one second, or
+		 * 3. there are no missing packets before them. */
+		skb_queue_walk_safe(&sk->sk_receive_queue, skb, skb1) {
+			meta = skb_meta(skb);
+			if (atomic_read(&sk->sk_rmem_alloc) < sk->sk_rcvbuf &&
+					now - meta->timestamp < HZ &&
+					meta->sequence != opt->recv_sequence)
+				break;
+			skb_unlink(skb, &sk->sk_receive_queue);
+			opt->recv_sequence = (__u16)(meta->sequence + 1);
+			skb_orphan(skb);
+			ppp_input(&pppox_sk(sk)->chan, skb);
+		}
+		return NET_RX_SUCCESS;
+	}
+
+	/* Flush receive queue if sequencing is disabled. */
+	skb_queue_purge(&sk->sk_receive_queue);
 	skb_orphan(skb);
 	ppp_input(&pppox_sk(sk)->chan, skb);
 	return NET_RX_SUCCESS;
@@ -163,14 +230,14 @@ static int pppolac_xmit(struct ppp_channel *chan, struct sk_buff *skb)
 	skb->data[1] = PPP_CTRL;
 
 	/* Install L2TP header. */
-	if (opt->sequencing) {
+	if (atomic_read(&opt->sequencing)) {
 		skb_push(skb, 10);
 		skb->data[0] = L2TP_SEQUENCE_BIT;
-		skb->data[6] = opt->sequence >> 8;
-		skb->data[7] = opt->sequence;
+		skb->data[6] = opt->xmit_sequence >> 8;
+		skb->data[7] = opt->xmit_sequence;
 		skb->data[8] = 0;
 		skb->data[9] = 0;
-		opt->sequence++;
+		opt->xmit_sequence++;
 	} else {
 		skb_push(skb, 6);
 		skb->data[0] = 0;
@@ -246,6 +313,7 @@ static int pppolac_connect(struct socket *sock, struct sockaddr *useraddr,
 	po->chan.mtu = PPP_MTU - 80;
 	po->proto.lac.local = unaligned(&addr->local)->u32;
 	po->proto.lac.remote = unaligned(&addr->remote)->u32;
+	atomic_set(&po->proto.lac.sequencing, 1);
 	po->proto.lac.backlog_rcv = sk_udp->sk_backlog_rcv;
 
 	error = ppp_register_channel(&po->chan);
@@ -283,6 +351,7 @@ static int pppolac_release(struct socket *sock)
 	if (sk->sk_state != PPPOX_NONE) {
 		struct sock *sk_udp = (struct sock *)pppox_sk(sk)->chan.private;
 		lock_sock(sk_udp);
+		skb_queue_purge(&sk->sk_receive_queue);
 		pppox_unbind_sock(sk);
 		udp_sk(sk_udp)->encap_type = 0;
 		udp_sk(sk_udp)->encap_rcv = NULL;
diff --git a/drivers/net/pppopns.c b/drivers/net/pppopns.c
index 298097127c9..fb819844793 100644
--- a/drivers/net/pppopns.c
+++ b/drivers/net/pppopns.c
@@ -16,11 +16,14 @@
 
 /* This driver handles PPTP data packets between a RAW socket and a PPP channel.
  * The socket is created in the kernel space and connected to the same address
- * of the control socket. To keep things simple, packets are always sent with
- * sequence but without acknowledgement. This driver should work on both IPv4
- * and IPv6. */
+ * of the control socket. Outgoing packets are always sent with sequences but
+ * without acknowledgements. Incoming packets with sequences are reordered
+ * within a sliding window of one second. Currently reordering only happens when
+ * a packet is received. It is done for simplicity since no additional locks or
+ * threads are required. This driver should work on both IPv4 and IPv6. */
 
 #include <linux/module.h>
+#include <linux/jiffies.h>
 #include <linux/workqueue.h>
 #include <linux/skbuff.h>
 #include <linux/file.h>
@@ -52,21 +55,35 @@ struct header {
 	__u32	sequence;
 } __attribute__((packed));
 
+struct meta {
+	__u32 sequence;
+	__u32 timestamp;
+};
+
+static inline struct meta *skb_meta(struct sk_buff *skb)
+{
+	return (struct meta *)skb->cb;
+}
+
+/******************************************************************************/
+
 static int pppopns_recv_core(struct sock *sk_raw, struct sk_buff *skb)
 {
 	struct sock *sk = (struct sock *)sk_raw->sk_user_data;
 	struct pppopns_opt *opt = &pppox_sk(sk)->proto.pns;
+	struct meta *meta = skb_meta(skb);
+	__u32 now = jiffies;
 	struct header *hdr;
 
 	/* Skip transport header */
 	skb_pull(skb, skb_transport_header(skb) - skb->data);
 
-	/* Drop the packet if it is too short. */
+	/* Drop the packet if GRE header is missing. */
 	if (skb->len < GRE_HEADER_SIZE)
 		goto drop;
+	hdr = (struct header *)skb->data;
 
 	/* Check the header. */
-	hdr = (struct header *)skb->data;
 	if (hdr->type != PPTP_GRE_TYPE || hdr->call != opt->local ||
 			(hdr->bits & PPTP_GRE_BITS_MASK) != PPTP_GRE_BITS)
 		goto drop;
@@ -81,6 +98,13 @@ static int pppopns_recv_core(struct sock *sk_raw, struct sk_buff *skb)
 	if (skb->len != ntohs(hdr->length))
 		goto drop;
 
+	/* Check the sequence if it is present. */
+	if (hdr->bits & PPTP_GRE_SEQ_BIT) {
+		meta->sequence = ntohl(hdr->sequence);
+		if ((__s32)(meta->sequence - opt->recv_sequence) < 0)
+			goto drop;
+	}
+
 	/* Skip PPP address and control if they are present. */
 	if (skb->len >= 2 && skb->data[0] == PPP_ADDR &&
 			skb->data[1] == PPP_CTRL)
@@ -90,7 +114,53 @@ static int pppopns_recv_core(struct sock *sk_raw, struct sk_buff *skb)
 	if (skb->len >= 1 && skb->data[0] & 1)
 		skb_push(skb, 1)[0] = 0;
 
-	/* Finally, deliver the packet to PPP channel. */
+	/* Drop the packet if PPP protocol is missing. */
+	if (skb->len < 2)
+		goto drop;
+
+	/* Perform reordering if sequencing is enabled. */
+	if (hdr->bits & PPTP_GRE_SEQ_BIT) {
+		struct sk_buff *skb1;
+
+		/* Insert the packet into receive queue in order. */
+		skb_set_owner_r(skb, sk);
+		skb_queue_walk(&sk->sk_receive_queue, skb1) {
+			struct meta *meta1 = skb_meta(skb1);
+			__s32 order = meta->sequence - meta1->sequence;
+			if (order == 0)
+				goto drop;
+			if (order < 0) {
+				meta->timestamp = meta1->timestamp;
+				skb_insert(skb1, skb, &sk->sk_receive_queue);
+				skb = NULL;
+				break;
+			}
+		}
+		if (skb) {
+			meta->timestamp = now;
+			skb_queue_tail(&sk->sk_receive_queue, skb);
+		}
+
+		/* Remove packets from receive queue as long as
+		 * 1. the receive buffer is full,
+		 * 2. they are queued longer than one second, or
+		 * 3. there are no missing packets before them. */
+		skb_queue_walk_safe(&sk->sk_receive_queue, skb, skb1) {
+			meta = skb_meta(skb);
+			if (atomic_read(&sk->sk_rmem_alloc) < sk->sk_rcvbuf &&
+					now - meta->timestamp < HZ &&
+					meta->sequence != opt->recv_sequence)
+				break;
+			skb_unlink(skb, &sk->sk_receive_queue);
+			opt->recv_sequence = meta->sequence + 1;
+			skb_orphan(skb);
+			ppp_input(&pppox_sk(sk)->chan, skb);
+		}
+		return NET_RX_SUCCESS;
+	}
+
+	/* Flush receive queue if sequencing is disabled. */
+	skb_queue_purge(&sk->sk_receive_queue);
 	skb_orphan(skb);
 	ppp_input(&pppox_sk(sk)->chan, skb);
 	return NET_RX_SUCCESS;
@@ -151,8 +221,8 @@ static int pppopns_xmit(struct ppp_channel *chan, struct sk_buff *skb)
 	hdr->type = PPTP_GRE_TYPE;
 	hdr->length = htons(length);
 	hdr->call = opt->remote;
-	hdr->sequence = htonl(opt->sequence);
-	opt->sequence++;
+	hdr->sequence = htonl(opt->xmit_sequence);
+	opt->xmit_sequence++;
 
 	/* Now send the packet via the delivery queue. */
 	skb_set_owner_w(skb, sk_raw);
@@ -261,6 +331,7 @@ static int pppopns_release(struct socket *sock)
 	if (sk->sk_state != PPPOX_NONE) {
 		struct sock *sk_raw = (struct sock *)pppox_sk(sk)->chan.private;
 		lock_sock(sk_raw);
+		skb_queue_purge(&sk->sk_receive_queue);
 		pppox_unbind_sock(sk);
 		sk_raw->sk_data_ready = pppox_sk(sk)->proto.pns.data_ready;
 		sk_raw->sk_backlog_rcv = pppox_sk(sk)->proto.pns.backlog_rcv;
diff --git a/include/linux/if_pppox.h b/include/linux/if_pppox.h
index 8afd94f2824..a010ccbdb5e 100644
--- a/include/linux/if_pppox.h
+++ b/include/linux/if_pppox.h
@@ -155,19 +155,21 @@ struct pppoe_opt {
 };
 
 struct pppolac_opt {
-	__u32	local;
-	__u32	remote;
-	__u16	sequence;
-	__u8	sequencing;
-	int	(*backlog_rcv)(struct sock *sk_udp, struct sk_buff *skb);
+	__u32		local;
+	__u32		remote;
+	__u32		recv_sequence;
+	__u32		xmit_sequence;
+	atomic_t	sequencing;
+	int		(*backlog_rcv)(struct sock *sk_udp, struct sk_buff *skb);
 };
 
 struct pppopns_opt {
-	__u16	local;
-	__u16	remote;
-	__u32	sequence;
-	void	(*data_ready)(struct sock *sk_raw, int length);
-	int	(*backlog_rcv)(struct sock *sk_raw, struct sk_buff *skb);
+	__u16		local;
+	__u16		remote;
+	__u32		recv_sequence;
+	__u32		xmit_sequence;
+	void		(*data_ready)(struct sock *sk_raw, int length);
+	int		(*backlog_rcv)(struct sock *sk_raw, struct sk_buff *skb);
 };
 
 #include <net/sock.h>