[PATCH net-next v2 0/3] Some optimization for lockless qdisc

[PATCH net-next v2 0/3] Some optimization for lockless qdisc

[Yunsheng Lin]

Patch 1: remove unnecessary seqcount operation.
Patch 2: implement TCQ_F_CAN_BYPASS.
Patch 3: remove qdisc->empty.

Performance data for pktgen in queue_xmit mode + dummy netdev
with pfifo_fast:

 threads    unpatched           patched             delta
    1       2.60Mpps            3.21Mpps             +23%
    2       3.84Mpps            5.56Mpps             +44%
    4       5.52Mpps            5.58Mpps             +1%
    8       2.77Mpps            2.76Mpps             -0.3%
   16       2.24Mpps            2.23Mpps             +0.4%

Performance for IP forward testing: 1.05Mpps increases to
1.16Mpps, about 10% improvement.

V2: Adjust the comment and commit log according to discussion
    in V1.
V1: Drop RFC tag, Add nolock_qdisc_is_empty() and do the qdisc
    empty checking without the protection of qdisc->seqlock to
    aviod doing unnecessary spin_trylock() for contention case.
RFC v4: Use STATE_MISSED and STATE_DRAINING to indicate non-empty
        qdisc, and add patch 1 and 3.

Yunsheng Lin (3):
  net: sched: avoid unnecessary seqcount operation for lockless qdisc
  net: sched: implement TCQ_F_CAN_BYPASS for lockless qdisc
  net: sched: remove qdisc->empty for lockless qdisc

 include/net/sch_generic.h | 31 ++++++++++++++++++-------------
 net/core/dev.c            | 27 +++++++++++++++++++++++++--
 net/sched/sch_generic.c   | 23 ++++++++++++++++-------
 3 files changed, 59 insertions(+), 22 deletions(-)

-- 
2.7.4

[PATCH net-next v2 1/3] net: sched: avoid unnecessary seqcount operation for lockless qdisc

[Yunsheng Lin]

qdisc->running seqcount operation is mainly used to do heuristic
locking on q->busylock for locked qdisc, see qdisc_is_running()
and __dev_xmit_skb().

So avoid doing seqcount operation for qdisc with TCQ_F_NOLOCK
flag.

Signed-off-by: Yunsheng Lin <linyunsheng@huawei.com>
---
 include/net/sch_generic.h | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 1e62551..3ed6bcc 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -188,6 +188,7 @@ static inline bool qdisc_run_begin(struct Qdisc *qdisc)
 
 nolock_empty:
 		WRITE_ONCE(qdisc->empty, false);
+		return true;
 	} else if (qdisc_is_running(qdisc)) {
 		return false;
 	}
@@ -201,7 +202,6 @@ static inline bool qdisc_run_begin(struct Qdisc *qdisc)
 
 static inline void qdisc_run_end(struct Qdisc *qdisc)
 {
-	write_seqcount_end(&qdisc->running);
 	if (qdisc->flags & TCQ_F_NOLOCK) {
 		spin_unlock(&qdisc->seqlock);
 
@@ -210,6 +210,8 @@ static inline void qdisc_run_end(struct Qdisc *qdisc)
 			clear_bit(__QDISC_STATE_MISSED, &qdisc->state);
 			__netif_schedule(qdisc);
 		}
+	} else {
+		write_seqcount_end(&qdisc->running);
 	}
 }
 
-- 
2.7.4

[PATCH net-next v2 2/3] net: sched: implement TCQ_F_CAN_BYPASS for lockless qdisc

[Yunsheng Lin]

Currently pfifo_fast has both TCQ_F_CAN_BYPASS and TCQ_F_NOLOCK
flag set, but queue discipline by-pass does not work for lockless
qdisc because skb is always enqueued to qdisc even when the qdisc
is empty, see __dev_xmit_skb().

This patch calls sch_direct_xmit() to transmit the skb directly
to the driver for empty lockless qdisc, which aviod enqueuing
and dequeuing operation.

As qdisc->empty is not reliable to indicate a empty qdisc because
there is a time window between enqueuing and setting qdisc->empty.
So we use the MISSED state added in commit a90c57f2cedd ("net:
sched: fix packet stuck problem for lockless qdisc"), which
indicate there is lock contention, suggesting that it is better
not to do the qdisc bypass in order to avoid packet out of order
problem.

In order to make MISSED state reliable to indicate a empty qdisc,
we need to ensure that testing and clearing of MISSED state is
within the protection of qdisc->seqlock, only setting MISSED state
can be done without the protection of qdisc->seqlock. A MISSED
state testing is added without the protection of qdisc->seqlock to
aviod doing unnecessary spin_trylock() for contention case.

As the enqueuing is not within the protection of qdisc->seqlock,
there is still a potential data race as pointed by Jakub [1]:

      thread1               thread2             thread3
qdisc_run_begin() # true
                        qdisc_run_begin(q)
                             set(MISSED)
pfifo_fast_dequeue
  clear(MISSED)
  # recheck the queue
qdisc_run_end()
                            enqueue skb1
                                             qdisc empty # true
                                          qdisc_run_begin() # true
                                          sch_direct_xmit() # skb2
                         qdisc_run_begin()
                            set(MISSED)

When above happens, skb1 enqueued by thread2 is transmited after
skb2 is transmited by thread3 because MISSED state setting and
enqueuing is not under the qdisc->seqlock. If qdisc bypass is
disabled, skb1 has better chance to be transmited quicker than
skb2

This patch does not take care of the above data race, because we
view this as similar as below:
Even at the same time CPU1 and CPU2 write the skb to two socket
which both heading to the same qdisc, there is no guarantee that
which skb will hit the qdisc first, because there is a lot of
factor like interrupt/softirq/cache miss/scheduling afffecting
that.

There are below cases that need special handling:
1. When MISSED state is cleared before another round of dequeuing
   in pfifo_fast_dequeue(), and __qdisc_run() might not be able to
   dequeue all skb in one round and call __netif_schedule(), which
   might result in a non-empty qdisc without MISSED set. In order
   to avoid this, the MISSED state is set for lockless qdisc and
   __netif_schedule() will be called at the end of qdisc_run_end.

2. The MISSED state also need to be set for lockless qdisc instead
   of calling __netif_schedule() directly when requeuing a skb for
   a similar reason.

3. For netdev queue stopped case, the MISSED case need clearing
   while the netdev queue is stopped, otherwise there may be
   unnecessary __netif_schedule() calling. So a new DRAINING state
   is added to indicate this case, which also indicate a non-empty
   qdisc.

4. As there is already netif_xmit_frozen_or_stopped() checking in
   dequeue_skb() and sch_direct_xmit(), which are both within the
   protection of qdisc->seqlock, but the same checking in
   __dev_xmit_skb() is without the protection, which might cause
   empty indication of a lockless qdisc to be not reliable. So
   remove the checking in __dev_xmit_skb(), and the checking in
   the protection of qdisc->seqlock seems enough to avoid the cpu
   consumption problem for netdev queue stopped case.

1. https://lkml.org/lkml/2021/5/29/215
Signed-off-by: Yunsheng Lin <linyunsheng@huawei.com>
---
V2: Adjust the comment and commit log according to discussion
    in V1.
V1: Add nolock_qdisc_is_empty() and do the qdisc empty checking
    without the protection of qdisc->seqlock to aviod doing
    unnecessary spin_trylock() for contention case.
RFC v4: Use STATE_MISSED and STATE_DRAINING to indicate non-empty
        qdisc.
---
 include/net/sch_generic.h | 16 +++++++++++++---
 net/core/dev.c            | 27 +++++++++++++++++++++++++--
 net/sched/sch_generic.c   | 20 ++++++++++++++++----
 3 files changed, 54 insertions(+), 9 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 3ed6bcc..177f240 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -37,8 +37,15 @@ enum qdisc_state_t {
 	__QDISC_STATE_SCHED,
 	__QDISC_STATE_DEACTIVATED,
 	__QDISC_STATE_MISSED,
+	__QDISC_STATE_DRAINING,
 };
 
+#define QDISC_STATE_MISSED	BIT(__QDISC_STATE_MISSED)
+#define QDISC_STATE_DRAINING	BIT(__QDISC_STATE_DRAINING)
+
+#define QDISC_STATE_NON_EMPTY	(QDISC_STATE_MISSED | \
+					QDISC_STATE_DRAINING)
+
 struct qdisc_size_table {
 	struct rcu_head		rcu;
 	struct list_head	list;
@@ -145,6 +152,11 @@ static inline bool qdisc_is_running(struct Qdisc *qdisc)
 	return (raw_read_seqcount(&qdisc->running) & 1) ? true : false;
 }
 
+static inline bool nolock_qdisc_is_empty(const struct Qdisc *qdisc)
+{
+	return !(READ_ONCE(qdisc->state) & QDISC_STATE_NON_EMPTY);
+}
+
 static inline bool qdisc_is_percpu_stats(const struct Qdisc *q)
 {
 	return q->flags & TCQ_F_CPUSTATS;
@@ -206,10 +218,8 @@ static inline void qdisc_run_end(struct Qdisc *qdisc)
 		spin_unlock(&qdisc->seqlock);
 
 		if (unlikely(test_bit(__QDISC_STATE_MISSED,
-				      &qdisc->state))) {
-			clear_bit(__QDISC_STATE_MISSED, &qdisc->state);
+				      &qdisc->state)))
 			__netif_schedule(qdisc);
-		}
 	} else {
 		write_seqcount_end(&qdisc->running);
 	}
diff --git a/net/core/dev.c b/net/core/dev.c
index 50531a2..991d09b 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -3852,10 +3852,33 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 	qdisc_calculate_pkt_len(skb, q);
 
 	if (q->flags & TCQ_F_NOLOCK) {
+		if (q->flags & TCQ_F_CAN_BYPASS && nolock_qdisc_is_empty(q) &&
+		    qdisc_run_begin(q)) {
+			/* Retest nolock_qdisc_is_empty() within the protection
+			 * of q->seqlock to protect from racing with requeuing.
+			 */
+			if (unlikely(!nolock_qdisc_is_empty(q))) {
+				rc = q->enqueue(skb, q, &to_free) &
+					NET_XMIT_MASK;
+				__qdisc_run(q);
+				qdisc_run_end(q);
+
+				goto no_lock_out;
+			}
+
+			qdisc_bstats_cpu_update(q, skb);
+			if (sch_direct_xmit(skb, q, dev, txq, NULL, true) &&
+			    !nolock_qdisc_is_empty(q))
+				__qdisc_run(q);
+
+			qdisc_run_end(q);
+			return NET_XMIT_SUCCESS;
+		}
+
 		rc = q->enqueue(skb, q, &to_free) & NET_XMIT_MASK;
-		if (likely(!netif_xmit_frozen_or_stopped(txq)))
-			qdisc_run(q);
+		qdisc_run(q);
 
+no_lock_out:
 		if (unlikely(to_free))
 			kfree_skb_list(to_free);
 		return rc;
diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c
index fc8b56b..83d7f5f 100644
--- a/net/sched/sch_generic.c
+++ b/net/sched/sch_generic.c
@@ -52,6 +52,8 @@ static void qdisc_maybe_clear_missed(struct Qdisc *q,
 	 */
 	if (!netif_xmit_frozen_or_stopped(txq))
 		set_bit(__QDISC_STATE_MISSED, &q->state);
+	else
+		set_bit(__QDISC_STATE_DRAINING, &q->state);
 }
 
 /* Main transmission queue. */
@@ -164,9 +166,13 @@ static inline void dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q)
 
 		skb = next;
 	}
-	if (lock)
+
+	if (lock) {
 		spin_unlock(lock);
-	__netif_schedule(q);
+		set_bit(__QDISC_STATE_MISSED, &q->state);
+	} else {
+		__netif_schedule(q);
+	}
 }
 
 static void try_bulk_dequeue_skb(struct Qdisc *q,
@@ -409,7 +415,11 @@ void __qdisc_run(struct Qdisc *q)
 	while (qdisc_restart(q, &packets)) {
 		quota -= packets;
 		if (quota <= 0) {
-			__netif_schedule(q);
+			if (q->flags & TCQ_F_NOLOCK)
+				set_bit(__QDISC_STATE_MISSED, &q->state);
+			else
+				__netif_schedule(q);
+
 			break;
 		}
 	}
@@ -680,13 +690,14 @@ static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
 	if (likely(skb)) {
 		qdisc_update_stats_at_dequeue(qdisc, skb);
 	} else if (need_retry &&
-		   test_bit(__QDISC_STATE_MISSED, &qdisc->state)) {
+		   READ_ONCE(qdisc->state) & QDISC_STATE_NON_EMPTY) {
 		/* Delay clearing the STATE_MISSED here to reduce
 		 * the overhead of the second spin_trylock() in
 		 * qdisc_run_begin() and __netif_schedule() calling
 		 * in qdisc_run_end().
 		 */
 		clear_bit(__QDISC_STATE_MISSED, &qdisc->state);
+		clear_bit(__QDISC_STATE_DRAINING, &qdisc->state);
 
 		/* Make sure dequeuing happens after clearing
 		 * STATE_MISSED.
@@ -1204,6 +1215,7 @@ static void dev_reset_queue(struct net_device *dev,
 	spin_unlock_bh(qdisc_lock(qdisc));
 	if (nolock) {
 		clear_bit(__QDISC_STATE_MISSED, &qdisc->state);
+		clear_bit(__QDISC_STATE_DRAINING, &qdisc->state);
 		spin_unlock_bh(&qdisc->seqlock);
 	}
 }
-- 
2.7.4

[PATCH net-next v2 3/3] net: sched: remove qdisc->empty for lockless qdisc

[Yunsheng Lin]

As MISSED and DRAINING state are used to indicate a non-empty
qdisc, qdisc->empty is not longer needed, so remove it.

Signed-off-by: Yunsheng Lin <linyunsheng@huawei.com>
---
 include/net/sch_generic.h | 13 +++----------
 net/sched/sch_generic.c   |  3 ---
 2 files changed, 3 insertions(+), 13 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 177f240..c99ffe9 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -117,8 +117,6 @@ struct Qdisc {
 	spinlock_t		busylock ____cacheline_aligned_in_smp;
 	spinlock_t		seqlock;
 
-	/* for NOLOCK qdisc, true if there are no enqueued skbs */
-	bool			empty;
 	struct rcu_head		rcu;
 
 	/* private data */
@@ -165,7 +163,7 @@ static inline bool qdisc_is_percpu_stats(const struct Qdisc *q)
 static inline bool qdisc_is_empty(const struct Qdisc *qdisc)
 {
 	if (qdisc_is_percpu_stats(qdisc))
-		return READ_ONCE(qdisc->empty);
+		return nolock_qdisc_is_empty(qdisc);
 	return !READ_ONCE(qdisc->q.qlen);
 }
 
@@ -173,7 +171,7 @@ static inline bool qdisc_run_begin(struct Qdisc *qdisc)
 {
 	if (qdisc->flags & TCQ_F_NOLOCK) {
 		if (spin_trylock(&qdisc->seqlock))
-			goto nolock_empty;
+			return true;
 
 		/* If the MISSED flag is set, it means other thread has
 		 * set the MISSED flag before second spin_trylock(), so
@@ -195,12 +193,7 @@ static inline bool qdisc_run_begin(struct Qdisc *qdisc)
 		/* Retry again in case other CPU may not see the new flag
 		 * after it releases the lock at the end of qdisc_run_end().
 		 */
-		if (!spin_trylock(&qdisc->seqlock))
-			return false;
-
-nolock_empty:
-		WRITE_ONCE(qdisc->empty, false);
-		return true;
+		return spin_trylock(&qdisc->seqlock);
 	} else if (qdisc_is_running(qdisc)) {
 		return false;
 	}
diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c
index 83d7f5f..1abd9c7 100644
--- a/net/sched/sch_generic.c
+++ b/net/sched/sch_generic.c
@@ -707,8 +707,6 @@ static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
 		need_retry = false;
 
 		goto retry;
-	} else {
-		WRITE_ONCE(qdisc->empty, true);
 	}
 
 	return skb;
@@ -909,7 +907,6 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 	sch->enqueue = ops->enqueue;
 	sch->dequeue = ops->dequeue;
 	sch->dev_queue = dev_queue;
-	sch->empty = true;
 	dev_hold(dev);
 	refcount_set(&sch->refcnt, 1);
 
-- 
2.7.4

Re: [PATCH net-next v2 0/3] Some optimization for lockless qdisc

[Jakub Kicinski]

On Thu, 3 Jun 2021 09:47:57 +0800 Yunsheng Lin wrote:
> Patch 1: remove unnecessary seqcount operation.
> Patch 2: implement TCQ_F_CAN_BYPASS.
> Patch 3: remove qdisc->empty.
> 
> Performance data for pktgen in queue_xmit mode + dummy netdev
> with pfifo_fast:
> 
>  threads    unpatched           patched             delta
>     1       2.60Mpps            3.21Mpps             +23%
>     2       3.84Mpps            5.56Mpps             +44%
>     4       5.52Mpps            5.58Mpps             +1%
>     8       2.77Mpps            2.76Mpps             -0.3%
>    16       2.24Mpps            2.23Mpps             +0.4%
> 
> Performance for IP forward testing: 1.05Mpps increases to
> 1.16Mpps, about 10% improvement.

Acked-by: Jakub Kicinski <kuba@kernel.org>

Re: [PATCH net-next v2 0/3] Some optimization for lockless qdisc

[Vladimir Oltean]

On Thu, Jun 03, 2021 at 11:35:48AM -0700, Jakub Kicinski wrote:
> On Thu, 3 Jun 2021 09:47:57 +0800 Yunsheng Lin wrote:
> > Patch 1: remove unnecessary seqcount operation.
> > Patch 2: implement TCQ_F_CAN_BYPASS.
> > Patch 3: remove qdisc->empty.
> > 
> > Performance data for pktgen in queue_xmit mode + dummy netdev
> > with pfifo_fast:
> > 
> >  threads    unpatched           patched             delta
> >     1       2.60Mpps            3.21Mpps             +23%
> >     2       3.84Mpps            5.56Mpps             +44%
> >     4       5.52Mpps            5.58Mpps             +1%
> >     8       2.77Mpps            2.76Mpps             -0.3%
> >    16       2.24Mpps            2.23Mpps             +0.4%
> > 
> > Performance for IP forward testing: 1.05Mpps increases to
> > 1.16Mpps, about 10% improvement.
> 
> Acked-by: Jakub Kicinski <kuba@kernel.org>

Any idea why these patches are deferred in patchwork?
https://patchwork.kernel.org/project/netdevbpf/cover/1622684880-39895-1-git-send-email-linyunsheng@huawei.com/

Re: Re: [PATCH net-next v2 0/3] Some optimization for lockless qdisc

[Yunsheng Lin]

On 2021/6/8 20:53, Vladimir Oltean wrote:
> On Thu, Jun 03, 2021 at 11:35:48AM -0700, Jakub Kicinski wrote:
>> On Thu, 3 Jun 2021 09:47:57 +0800 Yunsheng Lin wrote:
>>> Patch 1: remove unnecessary seqcount operation.
>>> Patch 2: implement TCQ_F_CAN_BYPASS.
>>> Patch 3: remove qdisc->empty.
>>>
>>> Performance data for pktgen in queue_xmit mode + dummy netdev
>>> with pfifo_fast:
>>>
>>>  threads    unpatched           patched             delta
>>>     1       2.60Mpps            3.21Mpps             +23%
>>>     2       3.84Mpps            5.56Mpps             +44%
>>>     4       5.52Mpps            5.58Mpps             +1%
>>>     8       2.77Mpps            2.76Mpps             -0.3%
>>>    16       2.24Mpps            2.23Mpps             +0.4%
>>>
>>> Performance for IP forward testing: 1.05Mpps increases to
>>> 1.16Mpps, about 10% improvement.
>>
>> Acked-by: Jakub Kicinski <kuba@kernel.org>
> 
> Any idea why these patches are deferred in patchwork?
> https://patchwork.kernel.org/project/netdevbpf/cover/1622684880-39895-1-git-send-email-linyunsheng@huawei.com/

I suppose it is a controversial change, which need more time
hanging to be reviewed and tested.

By the way, I did not pick up your "Tested-by" from previous
RFC version because there is some change between those version
that deserves a retesting. So it would be good to have a
"Tested-by" from you after confirming no out of order happening
for this version, thanks.

Re: [PATCH net-next v2 0/3] Some optimization for lockless qdisc

[Jakub Kicinski]

On Wed, 9 Jun 2021 09:31:39 +0800 Yunsheng Lin wrote:
> On 2021/6/8 20:53, Vladimir Oltean wrote:
> > On Thu, Jun 03, 2021 at 11:35:48AM -0700, Jakub Kicinski wrote:  
> >> On Thu, 3 Jun 2021 09:47:57 +0800 Yunsheng Lin wrote:  
> >>> Patch 1: remove unnecessary seqcount operation.
> >>> Patch 2: implement TCQ_F_CAN_BYPASS.
> >>> Patch 3: remove qdisc->empty.
> >>>
> >>> Performance data for pktgen in queue_xmit mode + dummy netdev
> >>> with pfifo_fast:
> >>>
> >>>  threads    unpatched           patched             delta
> >>>     1       2.60Mpps            3.21Mpps             +23%
> >>>     2       3.84Mpps            5.56Mpps             +44%
> >>>     4       5.52Mpps            5.58Mpps             +1%
> >>>     8       2.77Mpps            2.76Mpps             -0.3%
> >>>    16       2.24Mpps            2.23Mpps             +0.4%
> >>>
> >>> Performance for IP forward testing: 1.05Mpps increases to
> >>> 1.16Mpps, about 10% improvement.  
> >>
> >> Acked-by: Jakub Kicinski <kuba@kernel.org>  
> > 
> > Any idea why these patches are deferred in patchwork?
> > https://patchwork.kernel.org/project/netdevbpf/cover/1622684880-39895-1-git-send-email-linyunsheng@huawei.com/  
> 
> I suppose it is a controversial change, which need more time
> hanging to be reviewed and tested.

That'd be my guess also. A review from area experts would be great,
perhaps from Cong, John, Michal..  If the review doesn't come by
Friday - I'd repost.

Re: [PATCH net-next v2 0/3] Some optimization for lockless qdisc

[Vladimir Oltean]

On Wed, Jun 09, 2021 at 09:31:39AM +0800, Yunsheng Lin wrote:
> By the way, I did not pick up your "Tested-by" from previous
> RFC version because there is some change between those version
> that deserves a retesting. So it would be good to have a
> "Tested-by" from you after confirming no out of order happening
> for this version, thanks.

Tested-by: Vladimir Oltean <vladimir.oltean@nxp.com> # flexcan