You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@nuttx.apache.org by xi...@apache.org on 2023/01/18 08:24:17 UTC
[nuttx] 02/04: net/tcp: add out-of-order segment support
This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit d175f50f017d3e239177347a9856d42b1fc02ae3
Author: chao an <an...@xiaomi.com>
AuthorDate: Fri Jan 6 15:30:58 2023 +0800
net/tcp: add out-of-order segment support
Signed-off-by: chao an <an...@xiaomi.com>
---
net/tcp/Kconfig | 16 +++
net/tcp/tcp.h | 43 +++++++
net/tcp/tcp_callback.c | 156 +++++++++++++++++++++++-
net/tcp/tcp_conn.c | 16 +++
net/tcp/tcp_input.c | 312 ++++++++++++++++++++++++++++++++++++++++++++++-
net/tcp/tcp_recvwindow.c | 30 +++++
6 files changed, 571 insertions(+), 2 deletions(-)
diff --git a/net/tcp/Kconfig b/net/tcp/Kconfig
index a9958d935c..64208e76b2 100644
--- a/net/tcp/Kconfig
+++ b/net/tcp/Kconfig
@@ -135,6 +135,22 @@ config NET_TCP_WINDOW_SCALE_FACTOR
endif # NET_TCP_WINDOW_SCALE
+config NET_TCP_OUT_OF_ORDER
+ bool "Enable TCP/IP Out Of Order segments"
+ default n
+ ---help---
+ TCP will queue segments that arrive out of order.
+
+if NET_TCP_OUT_OF_ORDER
+
+config NET_TCP_OUT_OF_ORDER_BUFSIZE
+ int "TCP/IP Out Of Order buffer size"
+ default 16384
+ ---help---
+ This is the default value for out-of-order buffer size.
+
+endif # NET_TCP_OUT_OF_ORDER
+
config NET_TCP_NOTIFIER
bool "Support TCP notifications"
default n
diff --git a/net/tcp/tcp.h b/net/tcp/tcp.h
index 5637106499..bac6bc94de 100644
--- a/net/tcp/tcp.h
+++ b/net/tcp/tcp.h
@@ -106,6 +106,10 @@
#define TCP_WSCALE 0x01U /* Window Scale option enabled */
+/* The Max Range count of TCP Selective ACKs */
+
+#define TCP_SACK_RANGES_MAX 4
+
/* After receiving 3 duplicate ACKs, TCP performs a retransmission
* (RFC 5681 (3.2))
*/
@@ -144,6 +148,15 @@ struct tcp_poll_s
FAR struct devif_callback_s *cb; /* Needed to teardown the poll */
};
+/* Out-of-order segments */
+
+struct tcp_ofoseg_s
+{
+ uint32_t left; /* Left edge of segment */
+ uint32_t right; /* Right edge of segment */
+ FAR struct iob_s *data; /* Out-of-order buffering */
+};
+
struct tcp_conn_s
{
/* Common prologue of all connection structures. */
@@ -251,6 +264,17 @@ struct tcp_conn_s
struct iob_s *readahead; /* Read-ahead buffering */
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+
+ /* Number of out-of-order segments */
+
+ uint8_t nofosegs;
+
+ /* This defines a out of order segment block. */
+
+ struct tcp_ofoseg_s ofosegs[TCP_SACK_RANGES_MAX];
+#endif
+
#ifdef CONFIG_NET_TCP_WRITE_BUFFERS
/* Write buffering
*
@@ -2100,6 +2124,25 @@ void tcp_sendbuffer_notify(FAR struct tcp_conn_s *conn);
uint16_t tcpip_hdrsize(FAR struct tcp_conn_s *conn);
+/****************************************************************************
+ * Name: tcp_ofoseg_bufsize
+ *
+ * Description:
+ * Calculate the pending size of out-of-order buffer
+ *
+ * Input Parameters:
+ * conn - The TCP connection of interest
+ *
+ * Returned Value:
+ * Total size of out-of-order buffer
+ *
+ * Assumptions:
+ * This function must be called with the network locked.
+ *
+ ****************************************************************************/
+
+int tcp_ofoseg_bufsize(FAR struct tcp_conn_s *conn);
+
#ifdef __cplusplus
}
#endif
diff --git a/net/tcp/tcp_callback.c b/net/tcp/tcp_callback.c
index 3d00cdcc1f..d825ba07eb 100644
--- a/net/tcp/tcp_callback.c
+++ b/net/tcp/tcp_callback.c
@@ -94,10 +94,155 @@ tcp_data_event(FAR struct net_driver_s *dev, FAR struct tcp_conn_s *conn,
return flags;
}
+/****************************************************************************
+ * Name: tcp_ofoseg_data_event
+ *
+ * Description:
+ * Handle out-of-order segment to readahead poll.
+ *
+ * Assumptions:
+ * - This function must be called with the network locked.
+ *
+ ****************************************************************************/
+
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+static uint16_t tcp_ofoseg_data_event(FAR struct net_driver_s *dev,
+ FAR struct tcp_conn_s *conn,
+ uint16_t flags)
+{
+ FAR struct tcp_ofoseg_s *seg;
+ uint32_t rcvseq;
+ int i = 0;
+
+ /* Assume that we will ACK the data. The data will be ACKed if it is
+ * placed in the read-ahead buffer -OR- if it zero length
+ */
+
+ flags |= TCP_SNDACK;
+
+ /* Get the receive sequence number */
+
+ rcvseq = tcp_getsequence(conn->rcvseq);
+
+ ninfo("TCP OFOSEG rcvseq [%" PRIu32 "]\n", rcvseq);
+
+ /* Foreach out-of-order segments */
+
+ while (i < conn->nofosegs)
+ {
+ seg = &conn->ofosegs[i];
+
+ /* rcvseq -->|
+ * ofoseg |------|
+ */
+
+ if (rcvseq == seg->left)
+ {
+ ninfo("TCP OFOSEG input [%" PRIu32 " : %" PRIu32 " : %u]\n",
+ seg->left, seg->right, seg->data->io_pktlen);
+ rcvseq = TCP_SEQ_ADD(rcvseq,
+ seg->data->io_pktlen);
+ net_incr32(conn->rcvseq, seg->data->io_pktlen);
+ tcp_dataconcat(&conn->readahead, &seg->data);
+ }
+ else if (TCP_SEQ_GT(rcvseq, seg->left))
+ {
+ /* rcvseq -->|
+ * ofoseg |------|
+ */
+
+ if (TCP_SEQ_GTE(rcvseq, seg->right))
+ {
+ /* Remove stale segments */
+
+ iob_free_chain(seg->data);
+ seg->data = NULL;
+ }
+
+ /* rcvseq -->|
+ * ofoseg |------|
+ */
+
+ else
+ {
+ seg->data =
+ iob_trimhead(seg->data,
+ TCP_SEQ_SUB(rcvseq, seg->left));
+ seg->left = rcvseq;
+ if (seg->data != NULL)
+ {
+ ninfo("TCP OFOSEG input "
+ "[%" PRIu32 " : %" PRIu32 " : %u]\n",
+ seg->left, seg->right, seg->data->io_pktlen);
+ rcvseq = TCP_SEQ_ADD(rcvseq,
+ seg->data->io_pktlen);
+ net_incr32(conn->rcvseq, seg->data->io_pktlen);
+ tcp_dataconcat(&conn->readahead, &seg->data);
+ }
+ }
+ }
+
+ /* Rebuild out-of-order pool if segment is consumed */
+
+ if (seg->data == NULL)
+ {
+ for (; i < conn->nofosegs - 1; i++)
+ {
+ conn->ofosegs[i] = conn->ofosegs[i + 1];
+ }
+
+ conn->nofosegs--;
+
+ /* Try segments again */
+
+ i = 0;
+ }
+ else
+ {
+ i++;
+ }
+ }
+
+ return flags;
+}
+#endif /* CONFIG_NET_TCP_OUT_OF_ORDER */
+
/****************************************************************************
* Public Functions
****************************************************************************/
+/****************************************************************************
+ * Name: tcp_ofoseg_bufsize
+ *
+ * Description:
+ * Calculate the pending size of out-of-order buffer
+ *
+ * Input Parameters:
+ * conn - The TCP connection of interest
+ *
+ * Returned Value:
+ * Total size of out-of-order buffer
+ *
+ * Assumptions:
+ * This function must be called with the network locked.
+ *
+ ****************************************************************************/
+
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+int tcp_ofoseg_bufsize(FAR struct tcp_conn_s *conn)
+{
+ int total = 0;
+ int i;
+
+ for (i = 0; i < conn->nofosegs; i++)
+ {
+ total += conn->ofosegs[i].data->io_pktlen;
+ }
+
+ return total;
+}
+#endif /* CONFIG_NET_TCP_OUT_OF_ORDER */
+
/****************************************************************************
* Name: tcp_callback
*
@@ -112,7 +257,7 @@ tcp_data_event(FAR struct net_driver_s *dev, FAR struct tcp_conn_s *conn,
uint16_t tcp_callback(FAR struct net_driver_s *dev,
FAR struct tcp_conn_s *conn, uint16_t flags)
{
-#ifdef CONFIG_NET_TCP_NOTIFIER
+#if defined(CONFIG_NET_TCP_NOTIFIER) || defined(CONFIG_NET_TCP_OUT_OF_ORDER)
uint16_t orig = flags;
#endif
@@ -166,6 +311,15 @@ uint16_t tcp_callback(FAR struct net_driver_s *dev,
flags = tcp_data_event(dev, conn, flags);
}
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+ if ((orig & TCP_NEWDATA) != 0 && conn->nofosegs > 0)
+ {
+ /* Try out-of-order pool if new data is coming */
+
+ flags = tcp_ofoseg_data_event(dev, conn, flags);
+ }
+#endif
+
/* Check if there is a connection-related event and a connection
* callback.
*/
diff --git a/net/tcp/tcp_conn.c b/net/tcp/tcp_conn.c
index de09d72c13..1c2b359478 100644
--- a/net/tcp/tcp_conn.c
+++ b/net/tcp/tcp_conn.c
@@ -806,6 +806,22 @@ void tcp_free(FAR struct tcp_conn_s *conn)
iob_free_chain(conn->readahead);
conn->readahead = NULL;
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+ /* Release any out-of-order buffers */
+
+ if (conn->nofosegs > 0)
+ {
+ int i;
+
+ for (i = 0; i < conn->nofosegs; i++)
+ {
+ iob_free_chain(conn->ofosegs[i].data);
+ }
+
+ conn->nofosegs = 0;
+ }
+#endif /* CONFIG_NET_TCP_OUT_OF_ORDER */
+
#ifdef CONFIG_NET_TCP_WRITE_BUFFERS
/* Release any write buffers attached to the connection */
diff --git a/net/tcp/tcp_input.c b/net/tcp/tcp_input.c
index 4ed4edc025..552f6b1d37 100644
--- a/net/tcp/tcp_input.c
+++ b/net/tcp/tcp_input.c
@@ -257,6 +257,313 @@ static void tcp_snd_wnd_update(FAR struct tcp_conn_s *conn,
}
}
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+
+/****************************************************************************
+ * Name: tcp_rebuild_ofosegs
+ *
+ * Description:
+ * Re-build out-of-order pool from incoming segment
+ *
+ * Input Parameters:
+ * conn - The TCP connection of interest
+ * ofoseg - Pointer to incoming out-of-order segment
+ * start - Index of start postion of segment pool
+ *
+ * Returned Value:
+ * True if incoming data has been consumed
+ *
+ * Assumptions:
+ * The network is locked.
+ *
+ ****************************************************************************/
+
+static bool tcp_rebuild_ofosegs(FAR struct tcp_conn_s *conn,
+ FAR struct tcp_ofoseg_s *ofoseg,
+ int start)
+{
+ struct tcp_ofoseg_s *seg;
+ int i;
+
+ for (i = start; i < conn->nofosegs && ofoseg->data != NULL; i++)
+ {
+ seg = &conn->ofosegs[i];
+
+ /* ofoseg |~~~
+ * segpool |---|
+ */
+
+ if (TCP_SEQ_GTE(ofoseg->left, seg->left))
+ {
+ /* ofoseg |---|
+ * segpool |---|
+ */
+
+ if (TCP_SEQ_GT(ofoseg->left, seg->right))
+ {
+ continue;
+ }
+
+ /* ofoseg |---|
+ * segpool |---|
+ */
+
+ else if (ofoseg->left == seg->right)
+ {
+ tcp_dataconcat(&seg->data, &ofoseg->data);
+ seg->right = ofoseg->right;
+ }
+
+ /* ofoseg |--|
+ * segpool |---|
+ */
+
+ else if (TCP_SEQ_LTE(ofoseg->right, seg->right))
+ {
+ iob_free_chain(ofoseg->data);
+ ofoseg->data = NULL;
+ }
+
+ /* ofoseg |---|
+ * segpool |---|
+ */
+
+ else if (TCP_SEQ_GT(ofoseg->right, seg->right))
+ {
+ ofoseg->data =
+ iob_trimhead(ofoseg->data,
+ TCP_SEQ_SUB(seg->right, ofoseg->left));
+ tcp_dataconcat(&seg->data, &ofoseg->data);
+ seg->right = ofoseg->right;
+ }
+ }
+
+ /* ofoseg |~~~
+ * segpool |---|
+ */
+
+ else
+ {
+ /* ofoseg |---|
+ * segpool |---|
+ */
+
+ if (ofoseg->right == seg->left)
+ {
+ tcp_dataconcat(&ofoseg->data, &seg->data);
+ seg->data = ofoseg->data;
+ seg->left = ofoseg->left;
+ ofoseg->data = NULL;
+ }
+
+ /* ofoseg |---|
+ * segpool |---|
+ */
+
+ else if (TCP_SEQ_LT(ofoseg->right, seg->left))
+ {
+ continue;
+ }
+
+ /* ofoseg |---|~|
+ * segpool |--|
+ */
+
+ else if (TCP_SEQ_GTE(ofoseg->right, seg->right))
+ {
+ iob_free_chain(seg->data);
+ *seg = *ofoseg;
+ ofoseg->data = NULL;
+ }
+
+ /* ofoseg |---|
+ * segpool |---|
+ */
+
+ else if (TCP_SEQ_GT(ofoseg->right, seg->left))
+ {
+ ofoseg->data =
+ iob_trimtail(ofoseg->data,
+ ofoseg->right - seg->left);
+ tcp_dataconcat(&ofoseg->data, &seg->data);
+ seg->data = ofoseg->data;
+ seg->left = ofoseg->left;
+ ofoseg->data = NULL;
+ }
+ }
+ }
+
+ return (ofoseg->data == NULL);
+}
+
+/****************************************************************************
+ * Name: tcp_reorder_ofosegs
+ *
+ * Description:
+ * Sort out-of-order segments by left edge
+ *
+ * Input Parameters:
+ * nofosegs - Number of out-of-order semgnets
+ * ofosegs - Pointer to out-of-order segments
+ *
+ * Returned Value:
+ * True if re-order occurs
+ *
+ * Assumptions:
+ * The network is locked.
+ *
+ ****************************************************************************/
+
+static bool tcp_reorder_ofosegs(int nofosegs,
+ FAR struct tcp_ofoseg_s *ofosegs)
+{
+ struct tcp_ofoseg_s segs;
+ bool reordered = false;
+ int i;
+ int j;
+
+ /* Sort out-of-order segments by left edge */
+
+ for (i = 0; i < nofosegs - 1; i++)
+ {
+ for (j = 0; j < nofosegs - 1 - i; j++)
+ {
+ if (TCP_SEQ_GT(ofosegs[j].left,
+ ofosegs[j + 1].left))
+ {
+ segs = ofosegs[j];
+ ofosegs[j] = ofosegs[j + 1];
+ ofosegs[j + 1] = segs;
+ reordered = true;
+ }
+ }
+ }
+
+ return reordered;
+}
+
+/****************************************************************************
+ * Name: tcp_input_ofosegs
+ *
+ * Description:
+ * Handle incoming TCP data to out-of-order pool
+ *
+ * Input Parameters:
+ * dev - The device driver structure containing the received TCP packet.
+ * conn - The TCP connection of interest
+ * iplen - Length of the IP header (IPv4_HDRLEN or IPv6_HDRLEN).
+ *
+ * Returned Value:
+ * None
+ *
+ * Assumptions:
+ * The network is locked.
+ *
+ ****************************************************************************/
+
+static void tcp_input_ofosegs(FAR struct net_driver_s *dev,
+ FAR struct tcp_conn_s *conn,
+ unsigned int iplen)
+{
+ struct tcp_ofoseg_s ofoseg;
+ bool rebuild;
+ int i = 0;
+ int len;
+
+ ofoseg.left =
+ tcp_getsequence(((FAR struct tcp_hdr_s *)IPBUF(iplen))->seqno);
+
+ /* Calculate the pending size of out-of-order cache, if the input edge can
+ * not fill the adjacent segments, drop it
+ */
+
+ if (tcp_ofoseg_bufsize(conn) > CONFIG_NET_TCP_OUT_OF_ORDER_BUFSIZE &&
+ ofoseg.left >= conn->ofosegs[0].left)
+ {
+ return;
+ }
+
+ /* Get left/right edge from incoming data */
+
+ len = (dev->d_appdata - dev->d_iob->io_data) - dev->d_iob->io_offset;
+ ofoseg.right = TCP_SEQ_ADD(ofoseg.left, dev->d_iob->io_pktlen - len);
+
+ ninfo("TCP OFOSEG out-of-order "
+ "[%" PRIu32 " : %" PRIu32 " : %" PRIu32 "]\n",
+ ofoseg.left, ofoseg.right, TCP_SEQ_SUB(ofoseg.right, ofoseg.left));
+
+ /* Trim l3/l4 header to reserve appdata */
+
+ dev->d_iob = iob_trimhead(dev->d_iob, len);
+ if (dev->d_iob == NULL)
+ {
+ /* No available data, clear device buffer */
+
+ goto clear;
+ }
+
+ ofoseg.data = dev->d_iob;
+
+ /* Build out-of-order pool */
+
+ rebuild = tcp_rebuild_ofosegs(conn, &ofoseg, 0);
+
+ /* Incoming segment out of order from existing pool, add to new segment */
+
+ if (!rebuild && conn->nofosegs != TCP_SACK_RANGES_MAX)
+ {
+ conn->ofosegs[conn->nofosegs] = ofoseg;
+ conn->nofosegs++;
+ rebuild = true;
+ }
+
+ /* Try Re-order ofosegs */
+
+ if (rebuild &&
+ tcp_reorder_ofosegs(conn->nofosegs, (FAR void *)conn->ofosegs))
+ {
+ /* Re-build out-of-order pool after re-order */
+
+ while (i < conn->nofosegs - 1)
+ {
+ if (tcp_rebuild_ofosegs(conn, &conn->ofosegs[i], i + 1))
+ {
+ for (; i < conn->nofosegs - 1; i++)
+ {
+ conn->ofosegs[i] = conn->ofosegs[i + 1];
+ }
+
+ conn->nofosegs--;
+
+ i = 0;
+ }
+ else
+ {
+ i++;
+ }
+ }
+ }
+
+ for (i = 0; i < conn->nofosegs; i++)
+ {
+ ninfo("TCP OFOSEG [%d][%" PRIu32 " : %" PRIu32 " : %" PRIu32 "]\n", i,
+ conn->ofosegs[i].left, conn->ofosegs[i].right,
+ TCP_SEQ_SUB(conn->ofosegs[i].right, conn->ofosegs[i].left));
+ }
+
+ /* Incoming data has been consumed, re-prepare device buffer to send
+ * response.
+ */
+
+ if (rebuild)
+ {
+clear:
+ netdev_iob_clear(dev);
+ netdev_iob_prepare(dev, false, 0);
+ }
+}
+#endif /* CONFIG_NET_TCP_OUT_OF_ORDER */
+
/****************************************************************************
* Name: tcp_input
*
@@ -697,8 +1004,11 @@ found:
}
else
{
- /* We never queue out-of-order segments. */
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+ /* Queue out-of-order segments. */
+ tcp_input_ofosegs(dev, conn, iplen);
+#endif
tcp_send(dev, conn, TCP_ACK, tcpiplen);
return;
}
diff --git a/net/tcp/tcp_recvwindow.c b/net/tcp/tcp_recvwindow.c
index 7be6fd1682..2777c86230 100644
--- a/net/tcp/tcp_recvwindow.c
+++ b/net/tcp/tcp_recvwindow.c
@@ -219,6 +219,36 @@ uint32_t tcp_get_recvwindow(FAR struct net_driver_s *dev,
recvwndo = tcp_calc_rcvsize(conn, recvwndo);
+#ifdef CONFIG_NET_TCP_OUT_OF_ORDER
+ /* Calculate the minimum desired size */
+
+ if (conn->nofosegs > 0)
+ {
+ uint32_t desire = conn->ofosegs[0].left -
+ tcp_getsequence(conn->rcvseq);
+ int bufsize = tcp_ofoseg_bufsize(conn);
+
+ if (desire < tcp_rx_mss(dev))
+ {
+ desire = tcp_rx_mss(dev);
+ }
+
+ if (TCP_SEQ_LT(recvwndo, bufsize))
+ {
+ recvwndo = 0;
+ }
+ else
+ {
+ recvwndo -= bufsize;
+ }
+
+ if (recvwndo < desire)
+ {
+ recvwndo = desire;
+ }
+ }
+#endif /* CONFIG_NET_TCP_OUT_OF_ORDER */
+
#ifdef CONFIG_NET_TCP_WINDOW_SCALE
recvwndo >>= conn->rcv_scale;
#endif