Hello, On Thu, Sep 13, 2018 at 8:00 AM Stephen Hemminger <stephen@xxxxxxxxxxxxxxxxxx> wrote: > > From: Eric Dumazet <edumazet@xxxxxxxxxx> > > 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 <edumazet@xxxxxxxxxx> > Cc: Soheil Hassas Yeganeh <soheil@xxxxxxxxxx> > Cc: Wei Wang <weiwan@xxxxxxxxxx> > Cc: Willem de Bruijn <willemb@xxxxxxxxxx> > Acked-by: Soheil Hassas Yeganeh <soheil@xxxxxxxxxx> > Signed-off-by: David S. Miller <davem@xxxxxxxxxxxxx> > --- > 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 à 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 = NULL; skb->prev = NULL; skb->tstamp = netem_skb_cb(skb)->tstamp_save; + /* skb->dev shares skb->rbnode area, + * we need to restore its value. + */ + skb->dev = 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 defrag, and tcp stack */ > + struct list_head list; > }; > - struct sock *sk; > > union { > - 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 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 = q->fragments; > nf = q->net; > f = nf->f; > - while (fp) { > - struct sk_buff *xp = fp->next; > - > - sum_truesize += fp->truesize; > - kfree_skb(fp); > - fp = xp; > + if (fp) { > + do { > + struct sk_buff *xp = fp->next; > + > + sum_truesize += fp->truesize; > + kfree_skb(fp); > + fp = xp; > + } while (fp); > + } else { > + sum_truesize = skb_rbtree_purge(&q->rb_fragments); > } > sum = 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 = from_timer(frag, t, timer); > const struct iphdr *iph; > - struct sk_buff *head; > + struct sk_buff *head = 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 = 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 = qp->q.fragments; > + qp->q.fragments = head->next; > + } else { > + head = 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 == qp->q.fragments_tail) > + qp->q.fragments_tail = NULL; > + > + sub_frag_mem_limit(qp->q.net, head->truesize); > + > head->dev = 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 != 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 = atomic_inc_return(&peer->rid); > qp->rid = end; > > - rc = qp->q.fragments && (end - start) > max; > + rc = 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 = 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 = qp->q.fragments; > - do { > - struct sk_buff *xp = fp->next; > - > - sum_truesize += fp->truesize; > - kfree_skb(fp); > - fp = xp; > - } while (fp); > + sum_truesize = skb_rbtree_purge(&qp->q.rb_fragments); > sub_frag_mem_limit(qp->q.net, sum_truesize); > > qp->q.flags = 0; > qp->q.len = 0; > qp->q.meat = 0; > qp->q.fragments = NULL; > + qp->q.rb_fragments = RB_ROOT; > qp->q.fragments_tail = NULL; > qp->iif = 0; > qp->ecn = 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 = container_of(qp->q.net, struct net, ipv4.frags); > - 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 = qp->q.fragments_tail; > - if (!prev || prev->ip_defrag_offset < offset) { > - next = NULL; > - goto found; > - } > - prev = NULL; > - for (next = qp->q.fragments; next != NULL; next = next->next) { > - if (next->ip_defrag_offset >= offset) > - break; /* bingo! */ > - prev = next; > - } > + /* Note : skb->rbnode and skb->dev share the same location. */ > + dev = 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, if > * one or more its constituent fragments is determined to be an > * overlapping fragment, the entire datagram (and any constituent > * 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 = 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. */ > + /* 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.rb_right); > + qp->q.fragments_tail = skb; > + } else { > + /* 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) > + 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. */ > + 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 location */ > - dev = skb->dev; > if (dev) > qp->iif = dev->ifindex; > - /* Makes sure compiler wont do silly aliasing games */ > - barrier(); > skb->ip_defrag_offset = offset; > > - /* Insert this fragment in the chain of fragments. */ > - skb->next = next; > - if (!next) > - qp->q.fragments_tail = skb; > - if (prev) > - prev->next = skb; > - else > - qp->q.fragments = skb; > - > qp->q.stamp = skb->tstamp; > qp->q.meat += skb->len; > qp->ecn |= ecn; > @@ -414,7 +425,7 @@ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) > unsigned long orefdst = skb->_skb_refdst; > > skb->_skb_refdst = 0UL; > - err = ip_frag_reasm(qp, prev, dev); > + err = ip_frag_reasm(qp, skb, dev); > skb->_skb_refdst = 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 = container_of(qp->q.net, struct net, ipv4.frags); > struct iphdr *iph; > - struct sk_buff *fp, *head = qp->q.fragments; > + struct sk_buff *fp, *head = 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 = prev->next; > - fp = skb_clone(head, GFP_ATOMIC); > + if (head != skb) { > + fp = skb_clone(skb, GFP_ATOMIC); > if (!fp) > goto out_nomem; > - > - fp->next = head->next; > - if (!fp->next) > + rb_replace_node(&skb->rbnode, &fp->rbnode, &qp->q.rb_fragments); > + if (qp->q.fragments_tail == skb) > qp->q.fragments_tail = fp; > - prev->next = fp; > - > - skb_morph(head, qp->q.fragments); > - head->next = qp->q.fragments->next; > - > - consume_skb(qp->q.fragments); > - qp->q.fragments = head; > + skb_morph(skb, head); > + rb_replace_node(&head->rbnode, &skb->rbnode, > + &qp->q.rb_fragments); > + consume_skb(head); > + head = skb; > } > > - WARN_ON(!head); > WARN_ON(head->ip_defrag_offset != 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 = alloc_skb(0, GFP_ATOMIC); > if (!clone) > goto out_nomem; > - clone->next = head->next; > - head->next = clone; > skb_shinfo(clone)->frag_list = skb_shinfo(head)->frag_list; > skb_frag_list_init(head); > 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; > - head->data_len -= clone->len; > - head->len -= clone->len; > + skb->truesize += clone->truesize; > clone->csum = 0; > clone->ip_summed = head->ip_summed; > add_frag_mem_limit(qp->q.net, clone->truesize); > + skb_shinfo(head)->frag_list = clone; > + nextp = &clone->next; > + } else { > + nextp = &skb_shinfo(head)->frag_list; > } > > - skb_shinfo(head)->frag_list = head->next; > skb_push(head, head->data - skb_network_header(head)); > > - for (fp=head->next; fp; fp = fp->next) { > + /* Traverse the tree in order, to build frag_list. */ > + 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) > @@ -524,7 +541,9 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, > } > sub_frag_mem_limit(qp->q.net, head->truesize); > > + *nextp = NULL; > head->next = NULL; > + head->prev = NULL; > head->dev = dev; > head->tstamp = qp->q.stamp; > IPCB(head)->frag_max_size = max(qp->max_df_size, qp->q.max_size); > @@ -552,6 +571,7 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, > > __IP_INC_STATS(net, IPSTATS_MIB_REASMOKS); > qp->q.fragments = NULL; > + qp->q.rb_fragments = RB_ROOT; > qp->q.fragments_tail = 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_buff *prev, struct net_devic > head->csum); > > fq->q.fragments = NULL; > + fq->q.rb_fragments = RB_ROOT; > fq->q.fragments_tail = 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, struct sk_buff *prev, > __IP6_INC_STATS(net, __in6_dev_get(dev), IPSTATS_MIB_REASMOKS); > rcu_read_unlock(); > fq->q.fragments = NULL; > + fq->q.rb_fragments = RB_ROOT; > fq->q.fragments_tail = NULL; > return 1; > > -- > 2.18.0 >
