net: Reorder incoming packets in PPPoLAC and PPPoPNS.
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>
diff --git a/drivers/net/ppp/pppolac.c b/drivers/net/ppp/pppolac.c
index af3202a..c94b850 100644
--- a/drivers/net/ppp/pppolac.c
+++ b/drivers/net/ppp/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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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/ppp/pppopns.c b/drivers/net/ppp/pppopns.c
index 2980971..fb81984 100644
--- a/drivers/net/ppp/pppopns.c
+++ b/drivers/net/ppp/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 @@
__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 @@
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 @@
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 @@
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 @@
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 8363b5c..1597b8b 100644
--- a/include/linux/if_pppox.h
+++ b/include/linux/if_pppox.h
@@ -174,19 +174,21 @@
};
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>
