From mboxrd@z Thu Jan 1 00:00:00 1970 From: Christoph Paasch Subject: Re: [PATCH v3 26/30] net: sk_buff rbnode reorg Date: Thu, 18 Oct 2018 09:01:57 -0700 Message-ID: References: <20180913145902.17531-1-sthemmin@microsoft.com> <20180913145902.17531-27-sthemmin@microsoft.com> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Cc: David Miller , gregkh@linuxfoundation.org, netdev , stable@vger.kernel.org, Eric Dumazet , soheil@google.com, weiwan@google.com, willemb@google.com To: Stephen Hemminger Return-path: In-Reply-To: <20180913145902.17531-27-sthemmin@microsoft.com> Sender: stable-owner@vger.kernel.org List-Id: netdev.vger.kernel.org Hello, On Thu, Sep 13, 2018 at 8:00 AM Stephen Hemminger wrote: > > From: Eric Dumazet > > commit bffa72cf7f9df842f0016ba03586039296b4caaf upstream > > skb->rbnode shares space with skb->next, skb->prev and skb->tstamp > > Current uses (TCP receive ofo queue and netem) need to save/restore > tstamp, while skb->dev is either NULL (TCP) or a constant for a given > queue (netem). > > Since we plan using an RB tree for TCP retransmit queue to speedup SACK > processing with large BDP, this patch exchanges skb->dev and > skb->tstamp. > > This saves some overhead in both TCP and netem. > > v2: removes the swtstamp field from struct tcp_skb_cb > > Signed-off-by: Eric Dumazet > Cc: Soheil Hassas Yeganeh > Cc: Wei Wang > Cc: Willem de Bruijn > Acked-by: Soheil Hassas Yeganeh > Signed-off-by: David S. Miller > --- > include/linux/skbuff.h | 24 ++-- > include/net/inet_frag.h | 3 +- > net/ipv4/inet_fragment.c | 16 ++- > net/ipv4/ip_fragment.c | 182 +++++++++++++----------- > net/ipv6/netfilter/nf_conntrack_reasm.c | 1 + > net/ipv6/reassembly.c | 1 + > 6 files changed, 129 insertions(+), 98 deletions(-) this change is missing the pieces in sch_netem.c that Eric did as well. Thus, there is a panic that can be hit =C3=A0 la: https://github.com/multipath-tcp/mptcp/issues/285#issuecomment-431001559 The following diff fixes it (I can submit a proper patch later today). Storing of the tstamp can be changed as well (as Eric did in the original patch), but that's not causing any issues. I see a backport to v4.9 has been submitted as well... --- diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c index 2a2ab6bfe5d8..3d325b840802 100644 --- a/net/sched/sch_netem.c +++ b/net/sched/sch_netem.c @@ -624,6 +624,10 @@ static struct sk_buff *netem_dequeue(struct Qdisc *sch= ) skb->next =3D NULL; skb->prev =3D NULL; skb->tstamp =3D netem_skb_cb(skb)->tstamp_save; + /* skb->dev shares skb->rbnode area, + * we need to restore its value. + */ + skb->dev =3D qdisc_dev(sch); #ifdef CONFIG_NET_CLS_ACT /* > > diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h > index 2837e55df03e..f64e88444082 100644 > --- a/include/linux/skbuff.h > +++ b/include/linux/skbuff.h > @@ -663,23 +663,27 @@ struct sk_buff { > struct sk_buff *prev; > > union { > - ktime_t tstamp; > - u64 skb_mstamp; > + struct net_device *dev; > + /* Some protocols might use this space to= store information, > + * while device pointer would be NULL. > + * UDP receive path is one user. > + */ > + unsigned long dev_scratch; > }; > }; > - struct rb_node rbnode; /* used in netem & tcp stack */ > + struct rb_node rbnode; /* used in netem, ip4 def= rag, and tcp stack */ > + struct list_head list; > }; > - struct sock *sk; > > union { > - struct net_device *dev; > - /* Some protocols might use this space to store informati= on, > - * while device pointer would be NULL. > - * UDP receive path is one user. > - */ > - unsigned long dev_scratch; > + struct sock *sk; > int ip_defrag_offset; > }; > + > + union { > + ktime_t tstamp; > + u64 skb_mstamp; > + }; > /* > * This is the control buffer. It is free to use for every > * layer. Please put your private variables there. If you > diff --git a/include/net/inet_frag.h b/include/net/inet_frag.h > index ed07e3786d98..e4c71a7644be 100644 > --- a/include/net/inet_frag.h > +++ b/include/net/inet_frag.h > @@ -75,7 +75,8 @@ struct inet_frag_queue { > struct timer_list timer; > spinlock_t lock; > refcount_t refcnt; > - struct sk_buff *fragments; > + struct sk_buff *fragments; /* Used in IPv6. */ > + struct rb_root rb_fragments; /* Used in IPv4. */ > struct sk_buff *fragments_tail; > ktime_t stamp; > int len; > diff --git a/net/ipv4/inet_fragment.c b/net/ipv4/inet_fragment.c > index c9e35b81d093..6904cbb7de1a 100644 > --- a/net/ipv4/inet_fragment.c > +++ b/net/ipv4/inet_fragment.c > @@ -136,12 +136,16 @@ void inet_frag_destroy(struct inet_frag_queue *q) > fp =3D q->fragments; > nf =3D q->net; > f =3D nf->f; > - while (fp) { > - struct sk_buff *xp =3D fp->next; > - > - sum_truesize +=3D fp->truesize; > - kfree_skb(fp); > - fp =3D xp; > + if (fp) { > + do { > + struct sk_buff *xp =3D fp->next; > + > + sum_truesize +=3D fp->truesize; > + kfree_skb(fp); > + fp =3D xp; > + } while (fp); > + } else { > + sum_truesize =3D skb_rbtree_purge(&q->rb_fragments); > } > sum =3D sum_truesize + f->qsize; > > diff --git a/net/ipv4/ip_fragment.c b/net/ipv4/ip_fragment.c > index 960bf5eab59f..0e8f8de77e71 100644 > --- a/net/ipv4/ip_fragment.c > +++ b/net/ipv4/ip_fragment.c > @@ -136,7 +136,7 @@ static void ip_expire(struct timer_list *t) > { > struct inet_frag_queue *frag =3D from_timer(frag, t, timer); > const struct iphdr *iph; > - struct sk_buff *head; > + struct sk_buff *head =3D NULL; > struct net *net; > struct ipq *qp; > int err; > @@ -152,14 +152,31 @@ static void ip_expire(struct timer_list *t) > > ipq_kill(qp); > __IP_INC_STATS(net, IPSTATS_MIB_REASMFAILS); > - > - head =3D qp->q.fragments; > - > __IP_INC_STATS(net, IPSTATS_MIB_REASMTIMEOUT); > > - if (!(qp->q.flags & INET_FRAG_FIRST_IN) || !head) > + if (!qp->q.flags & INET_FRAG_FIRST_IN) > goto out; > > + /* sk_buff::dev and sk_buff::rbnode are unionized. So we > + * pull the head out of the tree in order to be able to > + * deal with head->dev. > + */ > + if (qp->q.fragments) { > + head =3D qp->q.fragments; > + qp->q.fragments =3D head->next; > + } else { > + head =3D skb_rb_first(&qp->q.rb_fragments); > + if (!head) > + goto out; > + rb_erase(&head->rbnode, &qp->q.rb_fragments); > + memset(&head->rbnode, 0, sizeof(head->rbnode)); > + barrier(); > + } > + if (head =3D=3D qp->q.fragments_tail) > + qp->q.fragments_tail =3D NULL; > + > + sub_frag_mem_limit(qp->q.net, head->truesize); > + > head->dev =3D dev_get_by_index_rcu(net, qp->iif); > if (!head->dev) > goto out; > @@ -179,16 +196,16 @@ static void ip_expire(struct timer_list *t) > (skb_rtable(head)->rt_type !=3D RTN_LOCAL)) > goto out; > > - skb_get(head); > spin_unlock(&qp->q.lock); > icmp_send(head, ICMP_TIME_EXCEEDED, ICMP_EXC_FRAGTIME, 0); > - kfree_skb(head); > goto out_rcu_unlock; > > out: > spin_unlock(&qp->q.lock); > out_rcu_unlock: > rcu_read_unlock(); > + if (head) > + kfree_skb(head); > ipq_put(qp); > } > > @@ -231,7 +248,7 @@ static int ip_frag_too_far(struct ipq *qp) > end =3D atomic_inc_return(&peer->rid); > qp->rid =3D end; > > - rc =3D qp->q.fragments && (end - start) > max; > + rc =3D qp->q.fragments_tail && (end - start) > max; > > if (rc) { > struct net *net; > @@ -245,7 +262,6 @@ static int ip_frag_too_far(struct ipq *qp) > > static int ip_frag_reinit(struct ipq *qp) > { > - struct sk_buff *fp; > unsigned int sum_truesize =3D 0; > > if (!mod_timer(&qp->q.timer, jiffies + qp->q.net->timeout)) { > @@ -253,20 +269,14 @@ static int ip_frag_reinit(struct ipq *qp) > return -ETIMEDOUT; > } > > - fp =3D qp->q.fragments; > - do { > - struct sk_buff *xp =3D fp->next; > - > - sum_truesize +=3D fp->truesize; > - kfree_skb(fp); > - fp =3D xp; > - } while (fp); > + sum_truesize =3D skb_rbtree_purge(&qp->q.rb_fragments); > sub_frag_mem_limit(qp->q.net, sum_truesize); > > qp->q.flags =3D 0; > qp->q.len =3D 0; > qp->q.meat =3D 0; > qp->q.fragments =3D NULL; > + qp->q.rb_fragments =3D RB_ROOT; > qp->q.fragments_tail =3D NULL; > qp->iif =3D 0; > qp->ecn =3D 0; > @@ -278,7 +288,8 @@ static int ip_frag_reinit(struct ipq *qp) > static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) > { > struct net *net =3D container_of(qp->q.net, struct net, ipv4.frag= s); > - struct sk_buff *prev, *next; > + struct rb_node **rbn, *parent; > + struct sk_buff *skb1; > struct net_device *dev; > unsigned int fragsize; > int flags, offset; > @@ -341,58 +352,58 @@ static int ip_frag_queue(struct ipq *qp, struct sk_= buff *skb) > if (err) > goto err; > > - /* Find out which fragments are in front and at the back of us > - * in the chain of fragments so far. We must know where to put > - * this fragment, right? > - */ > - prev =3D qp->q.fragments_tail; > - if (!prev || prev->ip_defrag_offset < offset) { > - next =3D NULL; > - goto found; > - } > - prev =3D NULL; > - for (next =3D qp->q.fragments; next !=3D NULL; next =3D next->nex= t) { > - if (next->ip_defrag_offset >=3D offset) > - break; /* bingo! */ > - prev =3D next; > - } > + /* Note : skb->rbnode and skb->dev share the same location. */ > + dev =3D skb->dev; > + /* Makes sure compiler wont do silly aliasing games */ > + barrier(); > > -found: > /* RFC5722, Section 4, amended by Errata ID : 3089 > * When reassembling an IPv6 datagram, i= f > * one or more its constituent fragments is determined to be an > * overlapping fragment, the entire datagram (and any constitue= nt > * fragments) MUST be silently discarded. > * > - * We do the same here for IPv4. > + * We do the same here for IPv4 (and increment an snmp counter). > */ > > - /* Is there an overlap with the previous fragment? */ > - if (prev && > - (prev->ip_defrag_offset + prev->len) > offset) > - goto discard_qp; > - > - /* Is there an overlap with the next fragment? */ > - if (next && next->ip_defrag_offset < end) > - goto discard_qp; > + /* Find out where to put this fragment. */ > + skb1 =3D 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_n= ode); > + qp->q.fragments_tail =3D skb; > + } else if ((skb1->ip_defrag_offset + skb1->len) < end) { > + /* This is the common/special case: skb goes to the end. = */ > + /* Detect and discard overlaps. */ > + if (offset < (skb1->ip_defrag_offset + skb1->len)) > + goto discard_qp; > + /* Insert after skb1. */ > + rb_link_node(&skb->rbnode, &skb1->rbnode, &skb1->rbnode.r= b_right); > + qp->q.fragments_tail =3D skb; > + } else { > + /* Binary search. Note that skb can become the first frag= ment, but > + * not the last (covered above). */ > + rbn =3D &qp->q.rb_fragments.rb_node; > + do { > + parent =3D *rbn; > + skb1 =3D rb_to_skb(parent); > + if (end <=3D skb1->ip_defrag_offset) > + rbn =3D &parent->rb_left; > + else if (offset >=3D skb1->ip_defrag_offset + skb= 1->len) > + rbn =3D &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. */ > + rb_link_node(&skb->rbnode, parent, rbn); > + } > + rb_insert_color(&skb->rbnode, &qp->q.rb_fragments); > > - /* Note : skb->ip_defrag_offset and skb->dev share the same locat= ion */ > - dev =3D skb->dev; > if (dev) > qp->iif =3D dev->ifindex; > - /* Makes sure compiler wont do silly aliasing games */ > - barrier(); > skb->ip_defrag_offset =3D offset; > > - /* Insert this fragment in the chain of fragments. */ > - skb->next =3D next; > - if (!next) > - qp->q.fragments_tail =3D skb; > - if (prev) > - prev->next =3D skb; > - else > - qp->q.fragments =3D skb; > - > qp->q.stamp =3D skb->tstamp; > qp->q.meat +=3D skb->len; > qp->ecn |=3D ecn; > @@ -414,7 +425,7 @@ static int ip_frag_queue(struct ipq *qp, struct sk_bu= ff *skb) > unsigned long orefdst =3D skb->_skb_refdst; > > skb->_skb_refdst =3D 0UL; > - err =3D ip_frag_reasm(qp, prev, dev); > + err =3D ip_frag_reasm(qp, skb, dev); > skb->_skb_refdst =3D orefdst; > return err; > } > @@ -431,15 +442,15 @@ static int ip_frag_queue(struct ipq *qp, struct sk_= buff *skb) > return err; > } > > - > /* Build a new IP datagram from all its fragments. */ > - > -static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, > +static int ip_frag_reasm(struct ipq *qp, struct sk_buff *skb, > struct net_device *dev) > { > struct net *net =3D container_of(qp->q.net, struct net, ipv4.frag= s); > struct iphdr *iph; > - struct sk_buff *fp, *head =3D qp->q.fragments; > + struct sk_buff *fp, *head =3D skb_rb_first(&qp->q.rb_fragments); > + struct sk_buff **nextp; /* To build frag_list. */ > + struct rb_node *rbn; > int len; > int ihlen; > int err; > @@ -453,25 +464,20 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_= buff *prev, > goto out_fail; > } > /* Make the one we just received the head. */ > - if (prev) { > - head =3D prev->next; > - fp =3D skb_clone(head, GFP_ATOMIC); > + if (head !=3D skb) { > + fp =3D skb_clone(skb, GFP_ATOMIC); > if (!fp) > goto out_nomem; > - > - fp->next =3D head->next; > - if (!fp->next) > + rb_replace_node(&skb->rbnode, &fp->rbnode, &qp->q.rb_frag= ments); > + if (qp->q.fragments_tail =3D=3D skb) > qp->q.fragments_tail =3D fp; > - prev->next =3D fp; > - > - skb_morph(head, qp->q.fragments); > - head->next =3D qp->q.fragments->next; > - > - consume_skb(qp->q.fragments); > - qp->q.fragments =3D head; > + skb_morph(skb, head); > + rb_replace_node(&head->rbnode, &skb->rbnode, > + &qp->q.rb_fragments); > + consume_skb(head); > + head =3D skb; > } > > - WARN_ON(!head); > WARN_ON(head->ip_defrag_offset !=3D 0); > > /* Allocate a new buffer for the datagram. */ > @@ -496,24 +502,35 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_= buff *prev, > clone =3D alloc_skb(0, GFP_ATOMIC); > if (!clone) > goto out_nomem; > - clone->next =3D head->next; > - head->next =3D clone; > skb_shinfo(clone)->frag_list =3D skb_shinfo(head)->frag_l= ist; > skb_frag_list_init(head); > for (i =3D 0; i < skb_shinfo(head)->nr_frags; i++) > plen +=3D skb_frag_size(&skb_shinfo(head)->frags[= i]); > clone->len =3D clone->data_len =3D head->data_len - plen; > - head->data_len -=3D clone->len; > - head->len -=3D clone->len; > + skb->truesize +=3D clone->truesize; > clone->csum =3D 0; > clone->ip_summed =3D head->ip_summed; > add_frag_mem_limit(qp->q.net, clone->truesize); > + skb_shinfo(head)->frag_list =3D clone; > + nextp =3D &clone->next; > + } else { > + nextp =3D &skb_shinfo(head)->frag_list; > } > > - skb_shinfo(head)->frag_list =3D head->next; > skb_push(head, head->data - skb_network_header(head)); > > - for (fp=3Dhead->next; fp; fp =3D fp->next) { > + /* Traverse the tree in order, to build frag_list. */ > + rbn =3D rb_next(&head->rbnode); > + rb_erase(&head->rbnode, &qp->q.rb_fragments); > + while (rbn) { > + struct rb_node *rbnext =3D rb_next(rbn); > + fp =3D rb_to_skb(rbn); > + rb_erase(rbn, &qp->q.rb_fragments); > + rbn =3D rbnext; > + *nextp =3D fp; > + nextp =3D &fp->next; > + fp->prev =3D NULL; > + memset(&fp->rbnode, 0, sizeof(fp->rbnode)); > head->data_len +=3D fp->len; > head->len +=3D fp->len; > if (head->ip_summed !=3D fp->ip_summed) > @@ -524,7 +541,9 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_bu= ff *prev, > } > sub_frag_mem_limit(qp->q.net, head->truesize); > > + *nextp =3D NULL; > head->next =3D NULL; > + head->prev =3D NULL; > head->dev =3D dev; > head->tstamp =3D qp->q.stamp; > IPCB(head)->frag_max_size =3D max(qp->max_df_size, qp->q.max_size= ); > @@ -552,6 +571,7 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_bu= ff *prev, > > __IP_INC_STATS(net, IPSTATS_MIB_REASMOKS); > qp->q.fragments =3D NULL; > + qp->q.rb_fragments =3D RB_ROOT; > qp->q.fragments_tail =3D NULL; > return 0; > > diff --git a/net/ipv6/netfilter/nf_conntrack_reasm.c b/net/ipv6/netfilter= /nf_conntrack_reasm.c > index 1d2f07cde01a..82ce0d0f54bf 100644 > --- a/net/ipv6/netfilter/nf_conntrack_reasm.c > +++ b/net/ipv6/netfilter/nf_conntrack_reasm.c > @@ -471,6 +471,7 @@ nf_ct_frag6_reasm(struct frag_queue *fq, struct sk_bu= ff *prev, struct net_devic > head->csum); > > fq->q.fragments =3D NULL; > + fq->q.rb_fragments =3D RB_ROOT; > fq->q.fragments_tail =3D NULL; > > return true; > diff --git a/net/ipv6/reassembly.c b/net/ipv6/reassembly.c > index afaad60dc2ac..ede0061b6f5d 100644 > --- a/net/ipv6/reassembly.c > +++ b/net/ipv6/reassembly.c > @@ -472,6 +472,7 @@ static int ip6_frag_reasm(struct frag_queue *fq, stru= ct sk_buff *prev, > __IP6_INC_STATS(net, __in6_dev_get(dev), IPSTATS_MIB_REASMOKS); > rcu_read_unlock(); > fq->q.fragments =3D NULL; > + fq->q.rb_fragments =3D RB_ROOT; > fq->q.fragments_tail =3D NULL; > return 1; > > -- > 2.18.0 >