From: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
To: linux-kernel@vger.kernel.org, netdev@vger.kernel.org
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
stable@vger.kernel.org, Willem de Bruijn <willemb@google.com>,
Peter Oskolkov <posk@google.com>,
Eric Dumazet <edumazet@google.com>,
Florian Westphal <fw@strlen.de>,
"David S. Miller" <davem@davemloft.net>
Subject: [PATCH 4.9 69/71] ip: process in-order fragments efficiently
Date: Tue, 16 Oct 2018 19:10:06 +0200 [thread overview]
Message-ID: <20181016170542.857918296@linuxfoundation.org> (raw)
In-Reply-To: <20181016170539.315587743@linuxfoundation.org>
4.9-stable review patch. If anyone has any objections, please let me know.
------------------
From: Peter Oskolkov <posk@google.com>
This patch changes the runtime behavior of IP defrag queue:
incoming in-order fragments are added to the end of the current
list/"run" of in-order fragments at the tail.
On some workloads, UDP stream performance is substantially improved:
RX: ./udp_stream -F 10 -T 2 -l 60
TX: ./udp_stream -c -H <host> -F 10 -T 5 -l 60
with this patchset applied on a 10Gbps receiver:
throughput=9524.18
throughput_units=Mbit/s
upstream (net-next):
throughput=4608.93
throughput_units=Mbit/s
Reported-by: Willem de Bruijn <willemb@google.com>
Signed-off-by: Peter Oskolkov <posk@google.com>
Cc: Eric Dumazet <edumazet@google.com>
Cc: Florian Westphal <fw@strlen.de>
Signed-off-by: David S. Miller <davem@davemloft.net>
(cherry picked from commit a4fd284a1f8fd4b6c59aa59db2185b1e17c5c11c)
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---
net/ipv4/inet_fragment.c | 2
net/ipv4/ip_fragment.c | 110 +++++++++++++++++++++++++++++------------------
2 files changed, 70 insertions(+), 42 deletions(-)
--- a/net/ipv4/inet_fragment.c
+++ b/net/ipv4/inet_fragment.c
@@ -145,7 +145,7 @@ void inet_frag_destroy(struct inet_frag_
fp = xp;
} while (fp);
} else {
- sum_truesize = skb_rbtree_purge(&q->rb_fragments);
+ sum_truesize = inet_frag_rbtree_purge(&q->rb_fragments);
}
sum = sum_truesize + f->qsize;
--- a/net/ipv4/ip_fragment.c
+++ b/net/ipv4/ip_fragment.c
@@ -125,8 +125,8 @@ static u8 ip4_frag_ecn(u8 tos)
static struct inet_frags ip4_frags;
-static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev,
- struct net_device *dev);
+static int ip_frag_reasm(struct ipq *qp, struct sk_buff *skb,
+ struct sk_buff *prev_tail, struct net_device *dev);
static void ip4_frag_init(struct inet_frag_queue *q, const void *a)
@@ -217,7 +217,12 @@ static void ip_expire(unsigned long arg)
head = skb_rb_first(&qp->q.rb_fragments);
if (!head)
goto out;
- rb_erase(&head->rbnode, &qp->q.rb_fragments);
+ if (FRAG_CB(head)->next_frag)
+ rb_replace_node(&head->rbnode,
+ &FRAG_CB(head)->next_frag->rbnode,
+ &qp->q.rb_fragments);
+ else
+ rb_erase(&head->rbnode, &qp->q.rb_fragments);
memset(&head->rbnode, 0, sizeof(head->rbnode));
barrier();
}
@@ -318,7 +323,7 @@ static int ip_frag_reinit(struct ipq *qp
return -ETIMEDOUT;
}
- sum_truesize = skb_rbtree_purge(&qp->q.rb_fragments);
+ sum_truesize = inet_frag_rbtree_purge(&qp->q.rb_fragments);
sub_frag_mem_limit(qp->q.net, sum_truesize);
qp->q.flags = 0;
@@ -327,6 +332,7 @@ static int ip_frag_reinit(struct ipq *qp
qp->q.fragments = NULL;
qp->q.rb_fragments = RB_ROOT;
qp->q.fragments_tail = NULL;
+ qp->q.last_run_head = NULL;
qp->iif = 0;
qp->ecn = 0;
@@ -338,7 +344,7 @@ static int ip_frag_queue(struct ipq *qp,
{
struct net *net = container_of(qp->q.net, struct net, ipv4.frags);
struct rb_node **rbn, *parent;
- struct sk_buff *skb1;
+ struct sk_buff *skb1, *prev_tail;
struct net_device *dev;
unsigned int fragsize;
int flags, offset;
@@ -416,38 +422,41 @@ static int ip_frag_queue(struct ipq *qp,
*/
/* Find out where to put this fragment. */
- skb1 = qp->q.fragments_tail;
- if (!skb1) {
- /* This is the first fragment we've received. */
- rb_link_node(&skb->rbnode, NULL, &qp->q.rb_fragments.rb_node);
- qp->q.fragments_tail = skb;
- } else if ((skb1->ip_defrag_offset + skb1->len) < end) {
- /* This is the common/special case: skb goes to the end. */
+ prev_tail = qp->q.fragments_tail;
+ if (!prev_tail)
+ ip4_frag_create_run(&qp->q, skb); /* First fragment. */
+ else if (prev_tail->ip_defrag_offset + prev_tail->len < end) {
+ /* This is the common case: skb goes to the end. */
/* Detect and discard overlaps. */
- if (offset < (skb1->ip_defrag_offset + skb1->len))
+ if (offset < prev_tail->ip_defrag_offset + prev_tail->len)
goto discard_qp;
- /* Insert after skb1. */
- rb_link_node(&skb->rbnode, &skb1->rbnode, &skb1->rbnode.rb_right);
- qp->q.fragments_tail = skb;
+ if (offset == prev_tail->ip_defrag_offset + prev_tail->len)
+ ip4_frag_append_to_last_run(&qp->q, skb);
+ else
+ ip4_frag_create_run(&qp->q, skb);
} else {
- /* Binary search. Note that skb can become the first fragment, but
- * not the last (covered above). */
+ /* Binary search. Note that skb can become the first fragment,
+ * but not the last (covered above).
+ */
rbn = &qp->q.rb_fragments.rb_node;
do {
parent = *rbn;
skb1 = rb_to_skb(parent);
if (end <= skb1->ip_defrag_offset)
rbn = &parent->rb_left;
- else if (offset >= skb1->ip_defrag_offset + skb1->len)
+ else if (offset >= skb1->ip_defrag_offset +
+ FRAG_CB(skb1)->frag_run_len)
rbn = &parent->rb_right;
else /* Found an overlap with skb1. */
goto discard_qp;
} while (*rbn);
/* Here we have parent properly set, and rbn pointing to
- * one of its NULL left/right children. Insert skb. */
+ * one of its NULL left/right children. Insert skb.
+ */
+ ip4_frag_init_run(skb);
rb_link_node(&skb->rbnode, parent, rbn);
+ rb_insert_color(&skb->rbnode, &qp->q.rb_fragments);
}
- rb_insert_color(&skb->rbnode, &qp->q.rb_fragments);
if (dev)
qp->iif = dev->ifindex;
@@ -474,7 +483,7 @@ static int ip_frag_queue(struct ipq *qp,
unsigned long orefdst = skb->_skb_refdst;
skb->_skb_refdst = 0UL;
- err = ip_frag_reasm(qp, skb, dev);
+ err = ip_frag_reasm(qp, skb, prev_tail, dev);
skb->_skb_refdst = orefdst;
return err;
}
@@ -493,7 +502,7 @@ err:
/* Build a new IP datagram from all its fragments. */
static int ip_frag_reasm(struct ipq *qp, struct sk_buff *skb,
- struct net_device *dev)
+ struct sk_buff *prev_tail, struct net_device *dev)
{
struct net *net = container_of(qp->q.net, struct net, ipv4.frags);
struct iphdr *iph;
@@ -517,10 +526,16 @@ static int ip_frag_reasm(struct ipq *qp,
fp = skb_clone(skb, GFP_ATOMIC);
if (!fp)
goto out_nomem;
- rb_replace_node(&skb->rbnode, &fp->rbnode, &qp->q.rb_fragments);
+ FRAG_CB(fp)->next_frag = FRAG_CB(skb)->next_frag;
+ if (RB_EMPTY_NODE(&skb->rbnode))
+ FRAG_CB(prev_tail)->next_frag = fp;
+ else
+ rb_replace_node(&skb->rbnode, &fp->rbnode,
+ &qp->q.rb_fragments);
if (qp->q.fragments_tail == skb)
qp->q.fragments_tail = fp;
skb_morph(skb, head);
+ FRAG_CB(skb)->next_frag = FRAG_CB(head)->next_frag;
rb_replace_node(&head->rbnode, &skb->rbnode,
&qp->q.rb_fragments);
consume_skb(head);
@@ -556,7 +571,7 @@ static int ip_frag_reasm(struct ipq *qp,
for (i = 0; i < skb_shinfo(head)->nr_frags; i++)
plen += skb_frag_size(&skb_shinfo(head)->frags[i]);
clone->len = clone->data_len = head->data_len - plen;
- skb->truesize += clone->truesize;
+ head->truesize += clone->truesize;
clone->csum = 0;
clone->ip_summed = head->ip_summed;
add_frag_mem_limit(qp->q.net, clone->truesize);
@@ -569,24 +584,36 @@ static int ip_frag_reasm(struct ipq *qp,
skb_push(head, head->data - skb_network_header(head));
/* Traverse the tree in order, to build frag_list. */
+ fp = FRAG_CB(head)->next_frag;
rbn = rb_next(&head->rbnode);
rb_erase(&head->rbnode, &qp->q.rb_fragments);
- while (rbn) {
- struct rb_node *rbnext = rb_next(rbn);
- fp = rb_to_skb(rbn);
- rb_erase(rbn, &qp->q.rb_fragments);
- rbn = rbnext;
- *nextp = fp;
- nextp = &fp->next;
- fp->prev = NULL;
- memset(&fp->rbnode, 0, sizeof(fp->rbnode));
- head->data_len += fp->len;
- head->len += fp->len;
- if (head->ip_summed != fp->ip_summed)
- head->ip_summed = CHECKSUM_NONE;
- else if (head->ip_summed == CHECKSUM_COMPLETE)
- head->csum = csum_add(head->csum, fp->csum);
- head->truesize += fp->truesize;
+ while (rbn || fp) {
+ /* fp points to the next sk_buff in the current run;
+ * rbn points to the next run.
+ */
+ /* Go through the current run. */
+ while (fp) {
+ *nextp = fp;
+ nextp = &fp->next;
+ fp->prev = NULL;
+ memset(&fp->rbnode, 0, sizeof(fp->rbnode));
+ head->data_len += fp->len;
+ head->len += fp->len;
+ if (head->ip_summed != fp->ip_summed)
+ head->ip_summed = CHECKSUM_NONE;
+ else if (head->ip_summed == CHECKSUM_COMPLETE)
+ head->csum = csum_add(head->csum, fp->csum);
+ head->truesize += fp->truesize;
+ fp = FRAG_CB(fp)->next_frag;
+ }
+ /* Move to the next run. */
+ if (rbn) {
+ struct rb_node *rbnext = rb_next(rbn);
+
+ fp = rb_to_skb(rbn);
+ rb_erase(rbn, &qp->q.rb_fragments);
+ rbn = rbnext;
+ }
}
sub_frag_mem_limit(qp->q.net, head->truesize);
@@ -622,6 +649,7 @@ static int ip_frag_reasm(struct ipq *qp,
qp->q.fragments = NULL;
qp->q.rb_fragments = RB_ROOT;
qp->q.fragments_tail = NULL;
+ qp->q.last_run_head = NULL;
return 0;
out_nomem:
next prev parent reply other threads:[~2018-10-16 17:25 UTC|newest]
Thread overview: 82+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-16 17:08 [PATCH 4.9 00/71] 4.9.134-stable review Greg Kroah-Hartman
2018-10-16 17:08 ` [PATCH 4.9 01/71] ASoC: wm8804: Add ACPI support Greg Kroah-Hartman
2018-10-16 17:08 ` [PATCH 4.9 02/71] ASoC: sigmadsp: safeload should not have lower byte limit Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 03/71] selftests/efivarfs: add required kernel configs Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 04/71] selftests: memory-hotplug: add required configs Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 05/71] mfd: omap-usb-host: Fix dts probe of children Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 06/71] scsi: iscsi: target: Dont use stack buffer for scatterlist Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 07/71] scsi: qla2xxx: Fix an endian bug in fcpcmd_is_corrupted() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 08/71] sound: enable interrupt after dma buffer initialization Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 09/71] stmmac: fix valid numbers of unicast filter entries Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 10/71] net: macb: disable scatter-gather for macb on sama5d3 Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 11/71] ARM: dts: at91: add new compatibility string " Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 12/71] x86/kvm/lapic: always disable MMIO interface in x2APIC mode Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 13/71] drm/amdgpu: Fix SDMA HQD destroy error on gfx_v7 Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 14/71] ext4: Fix error code in ext4_xattr_set_entry() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 15/71] mm/vmstat.c: fix outdated vmstat_text Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 16/71] MIPS: VDSO: Always map near top of user memory Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 17/71] mach64: detect the dot clock divider correctly on sparc Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 18/71] perf script python: Fix export-to-postgresql.py occasional failure Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 19/71] mm: Preserve _PAGE_DEVMAP across mprotect() calls Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 20/71] i2c: i2c-scmi: fix for i2c_smbus_write_block_data Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 21/71] xhci: Dont print a warning when setting link state for disabled ports Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 22/71] bnxt_en: Fix TX timeout during netpoll Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 23/71] bonding: avoid possible dead-lock Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 24/71] ip6_tunnel: be careful when accessing the inner header Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 25/71] ip_tunnel: " Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 26/71] ipv4: fix use-after-free in ip_cmsg_recv_dstaddr() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 27/71] ipv6: take rcu lock in rawv6_send_hdrinc() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 28/71] net: dsa: bcm_sf2: Call setup during switch resume Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 29/71] net: hns: fix for unmapping problem when SMMU is on Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 30/71] net: ipv4: update fnhe_pmtu when first hops MTU changes Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 31/71] net/ipv6: Display all addresses in output of /proc/net/if_inet6 Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 32/71] netlabel: check for IPV4MASK in addrinfo_get Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 33/71] net/usb: cancel pending work when unbinding smsc75xx Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 34/71] qlcnic: fix Tx descriptor corruption on 82xx devices Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 35/71] qmi_wwan: Added support for Gemaltos Cinterion ALASxx WWAN interface Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 36/71] team: Forbid enslaving team device to itself Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 37/71] net: dsa: bcm_sf2: Fix unbind ordering Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 38/71] net: mvpp2: Extract the correct ethtype from the skb for tx csum offload Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 39/71] net: systemport: Fix wake-up interrupt race during resume Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 40/71] rtnl: limit IFLA_NUM_TX_QUEUES and IFLA_NUM_RX_QUEUES to 4096 Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 41/71] tcp/dccp: fix lockdep issue when SYN is backlogged Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 42/71] inet: make sure to grab rcu_read_lock before using ireq->ireq_opt Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 43/71] inet: frags: change inet_frags_init_net() return value Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 44/71] inet: frags: add a pointer to struct netns_frags Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 45/71] inet: frags: refactor ipfrag_init() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 46/71] inet: frags: refactor ipv6_frag_init() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 47/71] inet: frags: refactor lowpan_net_frag_init() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 48/71] ipv6: export ip6 fragments sysctl to unprivileged users Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 49/71] rhashtable: add schedule points Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 50/71] inet: frags: use rhashtables for reassembly units Greg Kroah-Hartman
2018-10-26 13:39 ` Stefan Schmidt
2018-11-29 12:54 ` Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 51/71] inet: frags: remove some helpers Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 52/71] inet: frags: get rif of inet_frag_evicting() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 53/71] inet: frags: remove inet_frag_maybe_warn_overflow() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 54/71] inet: frags: break the 2GB limit for frags storage Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 55/71] inet: frags: do not clone skb in ip_expire() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 56/71] ipv6: frags: rewrite ip6_expire_frag_queue() Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 57/71] rhashtable: reorganize struct rhashtable layout Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 58/71] inet: frags: reorganize struct netns_frags Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 59/71] inet: frags: get rid of ipfrag_skb_cb/FRAG_CB Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 60/71] inet: frags: fix ip6frag_low_thresh boundary Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 61/71] ip: discard IPv4 datagrams with overlapping segments Greg Kroah-Hartman
2018-10-16 17:09 ` [PATCH 4.9 62/71] net: speed up skb_rbtree_purge() Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 63/71] net: modify skb_rbtree_purge to return the truesize of all purged skbs Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 64/71] ipv6: defrag: drop non-last frags smaller than min mtu Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 65/71] net: pskb_trim_rcsum() and CHECKSUM_COMPLETE are friends Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 66/71] net: add rb_to_skb() and other rb tree helpers Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 67/71] ip: use rb trees for IP frag queue Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 68/71] ip: add helpers to process in-order fragments faster Greg Kroah-Hartman
2018-10-16 17:10 ` Greg Kroah-Hartman [this message]
2018-10-16 17:10 ` [PATCH 4.9 70/71] ip: frags: fix crash in ip_do_fragment() Greg Kroah-Hartman
2018-10-16 17:10 ` [PATCH 4.9 71/71] ipv4: frags: precedence bug in ip_expire() Greg Kroah-Hartman
2018-10-17 7:20 ` [PATCH 4.9 00/71] 4.9.134-stable review Amit Pundir
2018-10-17 7:51 ` Greg Kroah-Hartman
2018-10-17 13:19 ` Guenter Roeck
2018-10-17 13:32 ` Greg Kroah-Hartman
2018-10-17 15:11 ` Rafael Tinoco
2018-10-17 18:43 ` Shuah Khan
2018-10-17 19:19 ` Guenter Roeck
2018-10-18 7:12 ` Greg Kroah-Hartman
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20181016170542.857918296@linuxfoundation.org \
--to=gregkh@linuxfoundation.org \
--cc=davem@davemloft.net \
--cc=edumazet@google.com \
--cc=fw@strlen.de \
--cc=linux-kernel@vger.kernel.org \
--cc=netdev@vger.kernel.org \
--cc=posk@google.com \
--cc=stable@vger.kernel.org \
--cc=willemb@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).