Skip to contentSkip to conversation

net: add additional lock to qdisc to increase enqueue/dequeue fairness

RFC PATCH In review Alexander Duyck 6 participants 26 messages Mar 23, 2010 – Jun 2, 2010

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 net: add additional lock to qdisc to increase enqueue/dequeue fairness

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs. The issue is that the transmit rate drops significantly, and I believe it is due to the fact that the spinlock is shared between the 1 dequeue, and n-1 enqueue cpu threads. In order to improve this situation I am adding one additional lock which will need to be obtained during the enqueue portion of the path. This essentially allows sch_direct_xmit to jump to near the head of the line when attempting to obtain the lock after completing a transmit.

Running the script below I saw an increase from 200K packets per second to 1.07M packets per second as a result of this patch.

for j in seq 0 15; do

	for i in `seq 0 7`; do
		netperf -H <ip> -t UDP_STREAM -l 600 -N -T $i -- -m 6 &
	done

done

---

 include/net/sch_generic.h |    3 ++-
 net/core/dev.c            |    7 ++++++-
 net/sched/sch_generic.c   |    1 +
 3 files changed, 9 insertions(+), 2 deletions(-)
include/net/sch_generic.h +2 -1
index 67dc08e..f5088a9 100644
@@ -51,7 +51,6 @@ struct Qdisc {
 	struct list_head	list;
 	u32			handle;
 	u32			parent;
-	atomic_t		refcnt;
 	struct gnet_stats_rate_est	rate_est;
 	int			(*reshape_fail)(struct sk_buff *skb,
 					struct Qdisc *q);
@@ -65,6 +64,8 @@ struct Qdisc {
 	struct netdev_queue	*dev_queue;
 	struct Qdisc		*next_sched;
 
+	atomic_t		refcnt;
+	spinlock_t		enqueue_lock;
 	struct sk_buff		*gso_skb;
 	/*
 	 * For performance sake on SMP, we put highly modified fields at the end
net/core/dev.c +6 -1
index a03aab4..8a2d508 100644
@@ -2006,8 +2006,10 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 	spinlock_t *root_lock = qdisc_lock(q);
 	int rc;
 
+	spin_lock(&q->enqueue_lock);
 	spin_lock(root_lock);
 	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state))) {
+		spin_unlock(&q->enqueue_lock);
 		kfree_skb(skb);
 		rc = NET_XMIT_DROP;
 	} else if ((q->flags & TCQ_F_CAN_BYPASS) && !qdisc_qlen(q) &&
@@ -2018,7 +2020,9 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		 * xmit the skb directly.
 		 */
 		__qdisc_update_bstats(q, skb->len);
-		if (sch_direct_xmit(skb, q, dev, txq, root_lock))
+		spin_unlock(&q->enqueue_lock);
+		rc = sch_direct_xmit(skb, q, dev, txq, root_lock);
+		if (rc)
 			__qdisc_run(q);
 		else
 			clear_bit(__QDISC_STATE_RUNNING, &q->state);
@@ -2026,6 +2030,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		rc = NET_XMIT_SUCCESS;
 	} else {
 		rc = qdisc_enqueue_root(skb, q);
+		spin_unlock(&q->enqueue_lock);
 		qdisc_run(q);
 	}
 	spin_unlock(root_lock);
net/sched/sch_generic.c +1 -0
index 5173c1e..4b5e125 100644
@@ -538,6 +538,7 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 	sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 	sch->padded = (char *) sch - (char *) p;
 
+	spin_lock_init(&sch->enqueue_lock);
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
 	sch->ops = ops;
maintainer
#1 lore raw

From: Alexander Duyck <[email protected]>
Date: Tue, 23 Mar 2010 13:25:53 -0700

Quoted 2 lines

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs.

Why are you hitting any central qdisc lock on a multiqueue configuration?

#3 lore raw
In reply to Alexander Duyck
Quoted 9 lines · Alexander Duyck

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs. The issue is that the transmit rate drops significantly, and I believe it is due to the fact that the spinlock is shared between the 1 dequeue, and n-1 enqueue cpu threads. In order to improve this situation I am adding one additional lock which will need to be obtained during the enqueue portion of the path. This essentially allows sch_direct_xmit to jump to near the head of the line when attempting to obtain the lock after completing a transmit.

Quoted 8 lines

Running the script below I saw an increase from 200K packets per second to 1.07M packets per second as a result of this patch.

for j in seq 0 15; do

	for i in `seq 0 7`; do
		netperf -H <ip> -t UDP_STREAM -l 600 -N -T $i -- -m 6 &
	done

done

Wow - someone is using the no control connection mode in netperf :) Or were you actually trying to get the test-specific -N option to control whether or not netperf "connects" the UDP socket?

rick jones

#4 lore raw
In reply to Alexander Duyck
Quoted 12 lines · Alexander Duyck

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs. The issue is that the transmit rate drops significantly, and I believe it is due to the fact that the spinlock is shared between the 1 dequeue, and n-1 enqueue cpu threads. In order to improve this situation I am adding one additional lock which will need to be obtained during the enqueue portion of the path. This essentially allows sch_direct_xmit to jump to near the head of the line when attempting to obtain the lock after completing a transmit.

Running the script below I saw an increase from 200K packets per second to 1.07M packets per second as a result of this patch.

Quoted 9 lines

for j in seq 0 15; do

	for i in `seq 0 7`; do
		netperf -H <ip> -t UDP_STREAM -l 600 -N -T $i -- -m 6 &
	done

done

---

Hi Alexander

Thats a pretty good topic :)

So to speedup a pathological case (dozen of cpus all sending to same queue), you suggest adding a spin_lock to fast path, slowing down normal cases ?

Quite frankly, the real problem in this case is not the reduced throughput, but fact that one cpu can stay a long time doing the xmits to device, of skb queued by other cpus. This can hurt latencies a lot, for real time threads for example...

I wonder if ticket spinlocks are not the problem. Maybe we want a variant of spinlocks, so that cpu doing transmits can get the lock before other cpus...

#5 lore raw
Quoted 3 lines · Eric Dumazet

I wonder if ticket spinlocks are not the problem. Maybe we want a variant of spinlocks, so that cpu doing transmits can get the lock before other cpus...

Something like this portable implementation :

struct spinprio {
	spinlock_t	lock;
	int		highprio_cnt;
};

void spinprio_lock(struct spinprio *l)

{
	while (1) {
		spin_lock(&l->lock);
		if (!l->highprio_cnt)
			break;
		spin_unlock(&l->lock);
		cpu_relax();
	}
}

void spinprio_unlock(struct spinprio *l)

{
	spin_unlock(&l->lock);
}

void spinprio_relock(struct spinprio *l)

{
	l->highprio_cnt = 1;
	spin_lock(&l->lock);
	l->highprio_cnt = 0;
}

We would have to use spinprio_unlock()/spinprio_relock() in sch_direct_xmit()

maintainer
#6 lore raw
In reply to Eric Dumazet

From: Eric Dumazet <[email protected]>
Date: Tue, 23 Mar 2010 21:54:27 +0100

Quoted 8 lines

Quite frankly, the real problem in this case is not the reduced throughput, but fact that one cpu can stay a long time doing the xmits to device, of skb queued by other cpus. This can hurt latencies a lot, for real time threads for example...

I wonder if ticket spinlocks are not the problem. Maybe we want a variant of spinlocks, so that cpu doing transmits can get the lock before other cpus...

I want to note that things operate the way they do now intentionally.

Herbert Xu and Jamal Hadi Salim were active in this area about 4 years ago.

#7 lore raw
Quoted 12 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 23 Mar 2010 21:54:27 +0100

Quoted 8 lines

Quite frankly, the real problem in this case is not the reduced throughput, but fact that one cpu can stay a long time doing the xmits to device, of skb queued by other cpus. This can hurt latencies a lot, for real time threads for example...

I wonder if ticket spinlocks are not the problem. Maybe we want a variant of spinlocks, so that cpu doing transmits can get the lock before other cpus...

Quoted 5 lines

I want to note that things operate the way they do now intentionally.

Herbert Xu and Jamal Hadi Salim were active in this area about 4 years ago.

Yes, but ticket spinlocks were added after their work (in 2008 - 2.6.25 if I remember well) and change things.

We want cpu owning __QDISC_STATE_RUNNING being able to re-get the lock as fast as possible. Alexander results can show the possible speedup.

#17 lore raw
In reply to David Miller
Quoted 12 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 23 Mar 2010 21:54:27 +0100

Quoted 8 lines

Quite frankly, the real problem in this case is not the reduced throughput, but fact that one cpu can stay a long time doing the xmits to device, of skb queued by other cpus. This can hurt latencies a lot, for real time threads for example...

I wonder if ticket spinlocks are not the problem. Maybe we want a variant of spinlocks, so that cpu doing transmits can get the lock before other cpus...

Quoted 5 lines

I want to note that things operate the way they do now intentionally.

Herbert Xu and Jamal Hadi Salim were active in this area about 4 years ago.

I'll do some digging on this to see what I can find out. I'm not sure why we would want to do things this way since it seems like the CPU that has qdisc_running is sitting idle due to the fact that the ticket spinlocks have us waiting for all of the other CPU enqueues before we can get around to another dequeue. It seems like it would be in our best interest to keep qdisc_running going while we are still enqueuing on the other CPUs.

I'll also look into the idea of possibly coming up with a more portable solution such as a priority based spinlock solution.

Thanks,

Alex

#2 lore raw
In reply to David Miller
Quoted 8 lines · David Miller

From: Alexander Duyck <[email protected]>
Date: Tue, 23 Mar 2010 13:25:53 -0700

Quoted 2 lines

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs.

Why are you hitting any central qdisc lock on a multiqueue configuration?

One thing to remember is that systems can have a lot more CPUs than a NIC queues (e.g. 64 vs 8)

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#21 lore raw
In reply to Alexander Duyck
Quoted 9 lines · Alexander Duyck

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs. The issue is that the transmit rate drops significantly, and I believe it is due to the fact that the spinlock is shared between the 1 dequeue, and n-1 enqueue cpu threads. In order to improve this situation I am adding one additional lock which will need to be obtained during the enqueue portion of the path. This essentially allows sch_direct_xmit to jump to near the head of the line when attempting to obtain the lock after completing a transmit.

This two stages lock permits to dequeue cpu to have 50% of chance to get q.lock, since all other cpus (but one) are competing in enqueue_lock.

Quoted 30 lines

Running the script below I saw an increase from 200K packets per second to 1.07M packets per second as a result of this patch.

for j in seq 0 15; do

	for i in `seq 0 7`; do
		netperf -H <ip> -t UDP_STREAM -l 600 -N -T $i -- -m 6 &
	done

done

---

 include/net/sch_generic.h |    3 ++-
 net/core/dev.c            |    7 ++++++-
 net/sched/sch_generic.c   |    1 +
 3 files changed, 9 insertions(+), 2 deletions(-)
include/net/sch_generic.h +0 -1
index 67dc08e..f5088a9 100644
@@ -51,7 +51,6 @@ struct Qdisc {
 	struct list_head	list;
 	u32			handle;
 	u32			parent;
-	atomic_t		refcnt;
 	struct gnet_stats_rate_est	rate_est;
 	int			(*reshape_fail)(struct sk_buff *skb,
 					struct Qdisc *q);

include/net/sch_generic.h struct Qdisc { · line 70

Quoted 7 lines
include/net/sch_generic.h +2 -0
@@ -65,6 +64,8 @@ struct Qdisc {
 	struct netdev_queue	*dev_queue;
 	struct Qdisc		*next_sched;
 
+	atomic_t		refcnt;
+	spinlock_t		enqueue_lock;
 	struct sk_buff		*gso_skb;
 	/*

Could you at least try to not fill the hole, but place enqueue_lock right after "struct sk_buff_head q;" ?

include/net/sch_generic.h +1 -0
index 67dc08e..6079c70 100644
@@ -71,6 +71,7 @@ struct Qdisc {
         */
        unsigned long           state;
        struct sk_buff_head     q;
+       spinlock_t              enqueue_lock;
        struct gnet_stats_basic_packed bstats;
        struct gnet_stats_queue qstats;
 };

So that on x86_64, all these fields use one cache line instead of two.

offsetof(struct Qdisc, state)=0x80
offsetof(struct Qdisc, q)=0x88
offsetof(struct Qdisc, enqueue_lock)=0xa0

It would be nice to have a benchmark for non pathological cases (one cpu doing a flood xmit of small packets)

#22 lore raw

PATCH 1/1 net: add additional lock to qdisc to increase throughput

In reply to Alexander Duyck
Quoted 87 lines · Alexander Duyck

The qdisc layer shows a significant issue when you start transmitting from multiple CPUs. The issue is that the transmit rate drops significantly, and I believe it is due to the fact that the spinlock is shared between the 1 dequeue, and n-1 enqueue cpu threads. In order to improve this situation I am adding one additional lock which will need to be obtained during the enqueue portion of the path. This essentially allows sch_direct_xmit to jump to near the head of the line when attempting to obtain the lock after completing a transmit.

Running the script below I saw an increase from 200K packets per second to 1.07M packets per second as a result of this patch.

for j in seq 0 15; do

	for i in `seq 0 7`; do
		netperf -H <ip> -t UDP_STREAM -l 600 -N -T $i -- -m 6 &
	done

done

---

 include/net/sch_generic.h |    3 ++-
 net/core/dev.c            |    7 ++++++-
 net/sched/sch_generic.c   |    1 +
 3 files changed, 9 insertions(+), 2 deletions(-)
include/net/sch_generic.h +2 -1
index 67dc08e..f5088a9 100644
@@ -51,7 +51,6 @@ struct Qdisc {
 	struct list_head	list;
 	u32			handle;
 	u32			parent;
-	atomic_t		refcnt;
 	struct gnet_stats_rate_est	rate_est;
 	int			(*reshape_fail)(struct sk_buff *skb,
 					struct Qdisc *q);
@@ -65,6 +64,8 @@ struct Qdisc {
 	struct netdev_queue	*dev_queue;
 	struct Qdisc		*next_sched;
 
+	atomic_t		refcnt;
+	spinlock_t		enqueue_lock;
 	struct sk_buff		*gso_skb;
 	/*
 	 * For performance sake on SMP, we put highly modified fields at the end
net/core/dev.c +6 -1
index a03aab4..8a2d508 100644
@@ -2006,8 +2006,10 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 	spinlock_t *root_lock = qdisc_lock(q);
 	int rc;
 
+	spin_lock(&q->enqueue_lock);
 	spin_lock(root_lock);
 	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state))) {
+		spin_unlock(&q->enqueue_lock);
 		kfree_skb(skb);
 		rc = NET_XMIT_DROP;
 	} else if ((q->flags & TCQ_F_CAN_BYPASS) && !qdisc_qlen(q) &&
@@ -2018,7 +2020,9 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		 * xmit the skb directly.
 		 */
 		__qdisc_update_bstats(q, skb->len);
-		if (sch_direct_xmit(skb, q, dev, txq, root_lock))
+		spin_unlock(&q->enqueue_lock);
+		rc = sch_direct_xmit(skb, q, dev, txq, root_lock);
+		if (rc)
 			__qdisc_run(q);
 		else
 			clear_bit(__QDISC_STATE_RUNNING, &q->state);
@@ -2026,6 +2030,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		rc = NET_XMIT_SUCCESS;
 	} else {
 		rc = qdisc_enqueue_root(skb, q);
+		spin_unlock(&q->enqueue_lock);
 		qdisc_run(q);
 	}
 	spin_unlock(root_lock);
net/sched/sch_generic.c +0 -0
index 5173c1e..4b5e125 100644

net/sched/sch_generic.c struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue, · line 544

Quoted 7 lines
net/sched/sch_generic.c +1 -0
@@ -538,6 +538,7 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 	sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 	sch->padded = (char *) sch - (char *) p;
 
+	spin_lock_init(&sch->enqueue_lock);
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
 	sch->ops = ops;

Hi Alexander

What about following patch instead, adding an heuristic to avoid an extra atomic operation in fast path ?

I also try to release the 'busylock' after the main lock to favor the worker as much as possible. It must be released before main lock only before a call to __qdisc_run()

Another refinement would be to make the spinning done outside of BH disabled context, because we currently delay TX completion (if NAPI is used by driver) that can make room in device TX ring buffer. This would allow cpus to process incoming traffic too...

Thanks

[PATCH] net: add additional lock to qdisc to increase throughput

When many cpus compete for sending frames on a given qdisc, the qdisc spinlock suffers from very high contention.

The cpu owning __QDISC_STATE_RUNNING bit has same priority to acquire the lock, and cannot dequeue packets fast enough, since it must wait for this lock for each dequeued packet.

One solution to this problem is to force all cpus spinning on a second lock before trying to get the main lock, when/if they see __QDISC_STATE_RUNNING already set.

The owning cpu then compete with at most one other cpu for the main lock, allowing for higher dequeueing rate.

Based on a previous patch from Alexander Duyck. I added the heuristic to avoid the atomic in fast path, and put the new lock far away from the cache line used by the dequeue worker. Also try to release the busylock lock as late as possible.

Tests with following script gave a boost from ~50.000 pps to ~600.000 pps on a dual quad core machine (E5450 @3.00GHz), tg3 driver. (A single netperf flow can reach ~800.000 pps on this platform)

for j in seq 0 3; do
for i in seq 0 7; do

    netperf -H 192.168.0.1 -t UDP_STREAM -l 60 -N -T $i -- -m 6 &

done
done

---
 include/net/sch_generic.h |    3 ++-
 net/core/dev.c            |   29 +++++++++++++++++++++++++----
 net/sched/sch_generic.c   |    1 +
 3 files changed, 28 insertions(+), 5 deletions(-)
include/net/sch_generic.h +2 -1
index 03ca5d8..2d55649 100644
@@ -73,7 +73,8 @@ struct Qdisc {
 	struct sk_buff_head	q;
 	struct gnet_stats_basic_packed bstats;
 	struct gnet_stats_queue	qstats;
-	struct rcu_head     rcu_head;
+	struct rcu_head		rcu_head;
+	spinlock_t		busylock;
 };
 
 struct Qdisc_class_ops {
net/core/dev.c +25 -4
index 6c82065..1b313eb 100644
@@ -2040,6 +2040,16 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 {
 	spinlock_t *root_lock = qdisc_lock(q);
 	int rc;
+	bool contended = test_bit(__QDISC_STATE_RUNNING, &q->state);
+
+	/*
+	 * Heuristic to force contended enqueues to serialize on a
+	 * separate lock before trying to get qdisc main lock.
+	 * This permits __QDISC_STATE_RUNNING owner to get the lock more often
+	 * and dequeue packets faster.
+	 */
+	if (unlikely(contended))
+		spin_lock(&q->busylock);
 
 	spin_lock(root_lock);
 	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state))) {
@@ -2055,19 +2065,30 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		if (!(dev->priv_flags & IFF_XMIT_DST_RELEASE))
 			skb_dst_force(skb);
 		__qdisc_update_bstats(q, skb->len);
-		if (sch_direct_xmit(skb, q, dev, txq, root_lock))
+		if (sch_direct_xmit(skb, q, dev, txq, root_lock)) {
+			if (unlikely(contended)) {
+				spin_unlock(&q->busylock);
+				contended = false;
+			}
 			__qdisc_run(q);
-		else
+		} else
 			clear_bit(__QDISC_STATE_RUNNING, &q->state);
 
 		rc = NET_XMIT_SUCCESS;
 	} else {
 		skb_dst_force(skb);
 		rc = qdisc_enqueue_root(skb, q);
-		qdisc_run(q);
+		if (!test_and_set_bit(__QDISC_STATE_RUNNING, &q->state)) {
+			if (unlikely(contended)) {
+				spin_unlock(&q->busylock);
+				contended = false;
+			}
+			__qdisc_run(q);
+		}
 	}
 	spin_unlock(root_lock);
-
+	if (unlikely(contended))
+		spin_unlock(&q->busylock);
 	return rc;
 }
 
net/sched/sch_generic.c +1 -0
index a63029e..0a44290 100644
@@ -543,6 +543,7 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
+	spin_lock_init(&sch->busylock);
 	sch->ops = ops;
 	sch->enqueue = ops->enqueue;
 	sch->dequeue = ops->dequeue;
#8 lore raw
In reply to Eric Dumazet
Quoted 16 lines · On Tue, 23 Mar 2010 23:13:00 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 15 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 23 Mar 2010 21:54:27 +0100

Quoted 8 lines

Quite frankly, the real problem in this case is not the reduced throughput, but fact that one cpu can stay a long time doing the xmits to device, of skb queued by other cpus. This can hurt latencies a lot, for real time threads for example...

I wonder if ticket spinlocks are not the problem. Maybe we want a variant of spinlocks, so that cpu doing transmits can get the lock before other cpus...

I want to note that things operate the way they do now intentionally.

Quoted 8 lines
Quoted 2 lines

Herbert Xu and Jamal Hadi Salim were active in this area about 4 years ago.

Yes, but ticket spinlocks were added after their work (in 2008 - 2.6.25 if I remember well) and change things.

We want cpu owning __QDISC_STATE_RUNNING being able to re-get the lock as fast as possible. Alexander results can show the possible speedup.

What about having a special function (spin_lock_greedy?) that just ignores the ticket mechanism and always assumes it has right to next ticket.

#9 lore raw
Quoted 3 lines · Stephen Hemminger

What about having a special function (spin_lock_greedy?) that just ignores the ticket mechanism and always assumes it has right to next ticket.

I am not sure we want to do this, for a single use case... Adding a new lock primitive to linux should be really really motivated.

x86 ticket spinlocks are nice because we are sure no cpu is going to stay forever in this code. For other arches, I dont know how this is coped.

I thought about this before re-working on this patch, but found it was easier to slightly change Alexander code, ie adding a regular spinlock for the slowpath.

We could use cmpxchg() and manipulate several bits at once in fast path. ( __QDISC_STATE_RUNNING, __QDISC_STATE_LOCKED ... ) but making the crowd of cpus spin on the same bits/cacheline than dequeue worker would definitely slowdown the worker.

#10 lore raw
Quoted 13 lines · On Fri, 21 May 2010 18:44:35 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 3 lines · Stephen Hemminger

What about having a special function (spin_lock_greedy?) that just ignores the ticket mechanism and always assumes it has right to next ticket.

I am not sure we want to do this, for a single use case... Adding a new lock primitive to linux should be really really motivated.

x86 ticket spinlocks are nice because we are sure no cpu is going to stay forever in this code. For other arches, I dont know how this is coped.

Quoted 8 lines

I thought about this before re-working on this patch, but found it was easier to slightly change Alexander code, ie adding a regular spinlock for the slowpath.

We could use cmpxchg() and manipulate several bits at once in fast path. ( __QDISC_STATE_RUNNING, __QDISC_STATE_LOCKED ... ) but making the crowd of cpus spin on the same bits/cacheline than dequeue worker would definitely slowdown the worker.

Your solution is okay, but it is a special case performance hack and we seem to be getting more and more of these lately. This is a general problem of any producer/consumer case; other code will have same problem (like disk requests) and can't use the same solution.

Maybe the RT and scheduler folks have some input because it does seem like the same problem has occurred in other contexts before.

#11 lore raw
In reply to Eric Dumazet
Quoted 6 lines · Eric Dumazet

We could use cmpxchg() and manipulate several bits at once in fast path. ( __QDISC_STATE_RUNNING, __QDISC_STATE_LOCKED ... ) but making the crowd of cpus spin on the same bits/cacheline than dequeue worker would definitely slowdown the worker.

Maybe I am missing something, but __QDISC_STATE_RUNNING is always manipulated with the lock held...

We might avoid two atomic ops when changing this state (if moved to a separate container) in fast path (when a cpu sends only one packet and returns)

author Acked-by on v1 1/1
#23 lore raw

RE: [PATCH] net: add additional lock to qdisc to increase throughput

In reply to Eric Dumazet
Quoted 9 lines · Eric Dumazet

Tests with following script gave a boost from ~50.000 pps to ~600.000 pps on a dual quad core machine (E5450 @3.00GHz), tg3 driver. (A single netperf flow can reach ~800.000 pps on this platform)

for j in seq 0 3; do
for i in seq 0 7; do

    netperf -H 192.168.0.1 -t UDP_STREAM -l 60 -N -T $i -- -m 6 &

done
done

Running the same script with your patch my results went from 200Kpps to 1.2Mpps on a dual Xeon 5570.

#12 lore raw
In reply to Eric Dumazet
Quoted 9 lines · Eric Dumazet
Quoted 6 lines · Eric Dumazet

We could use cmpxchg() and manipulate several bits at once in fast path. ( __QDISC_STATE_RUNNING, __QDISC_STATE_LOCKED ... ) but making the crowd of cpus spin on the same bits/cacheline than dequeue worker would definitely slowdown the worker.

Quoted 8 lines

Maybe I am missing something, but __QDISC_STATE_RUNNING is always manipulated with the lock held...

We might avoid two atomic ops when changing this state (if moved to a separate container) in fast path (when a cpu sends only one packet and returns)

Here are two patches to implement this idea.

First patch to abstract QDISC_STATE_RUNNING access.

Second patch to add a __qstate container and remove the atomic ops.

#13 lore raw

PATCH 1/2 net: Define accessors to manipulate QDISC_STATE_RUNNING

In reply to Eric Dumazet

Define three helpers to manipulate QDISC_STATE_RUNNIG flag, that a second patch will move on another location.

---
 include/net/pkt_sched.h   |    2 +-
 include/net/sch_generic.h |   15 +++++++++++++++
 net/core/dev.c            |    4 ++--
 net/sched/sch_generic.c   |    4 ++--
 4 files changed, 20 insertions(+), 5 deletions(-)
include/net/pkt_sched.h +1 -1
index 9d4d87c..d9549af 100644
@@ -95,7 +95,7 @@ extern void __qdisc_run(struct Qdisc *q);
 
 static inline void qdisc_run(struct Qdisc *q)
 {
-	if (!test_and_set_bit(__QDISC_STATE_RUNNING, &q->state))
+	if (qdisc_run_begin(q))
 		__qdisc_run(q);
 }
 
include/net/sch_generic.h +15 -0
index 03ca5d8..9707dae 100644
@@ -76,6 +76,21 @@ struct Qdisc {
 	struct rcu_head     rcu_head;
 };
 
+static inline bool qdisc_is_running(struct Qdisc *qdisc)
+{
+	return test_bit(__QDISC_STATE_RUNNING, &qdisc->state);
+}
+
+static inline bool qdisc_run_begin(struct Qdisc *qdisc)
+{
+	return !test_and_set_bit(__QDISC_STATE_RUNNING, &qdisc->state);
+}
+
+static inline void qdisc_run_end(struct Qdisc *qdisc)
+{
+	clear_bit(__QDISC_STATE_RUNNING, &qdisc->state);
+}
+
 struct Qdisc_class_ops {
 	/* Child qdisc manipulation */
 	struct netdev_queue *	(*select_queue)(struct Qdisc *, struct tcmsg *);
net/core/dev.c +2 -2
index 983a3c1..2733226 100644
@@ -2047,7 +2047,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		kfree_skb(skb);
 		rc = NET_XMIT_DROP;
 	} else if ((q->flags & TCQ_F_CAN_BYPASS) && !qdisc_qlen(q) &&
-		   !test_and_set_bit(__QDISC_STATE_RUNNING, &q->state)) {
+		   qdisc_run_begin(q)) {
 		/*
 		 * This is a work-conserving queue; there are no old skbs
 		 * waiting to be sent out; and the qdisc is not running -
@@ -2059,7 +2059,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		if (sch_direct_xmit(skb, q, dev, txq, root_lock))
 			__qdisc_run(q);
 		else
-			clear_bit(__QDISC_STATE_RUNNING, &q->state);
+			qdisc_run_end(q);
 
 		rc = NET_XMIT_SUCCESS;
 	} else {
net/sched/sch_generic.c +2 -2
index bd1892f..37b86ea 100644
@@ -205,7 +205,7 @@ void __qdisc_run(struct Qdisc *q)
 		}
 	}
 
-	clear_bit(__QDISC_STATE_RUNNING, &q->state);
+	qdisc_run_end(q);
 }
 
 unsigned long dev_trans_start(struct net_device *dev)
@@ -797,7 +797,7 @@ static bool some_qdisc_is_busy(struct net_device *dev)
 
 		spin_lock_bh(root_lock);
 
-		val = (test_bit(__QDISC_STATE_RUNNING, &q->state) ||
+		val = (qdisc_is_running(q) ||
 		       test_bit(__QDISC_STATE_SCHED, &q->state));
 
 		spin_unlock_bh(root_lock);
#15 lore raw

PATCH 2/2 net: QDISC_STATE_RUNNING dont need atomic bit ops

In reply to Eric Dumazet

__QDISC_STATE_RUNNING is always changed while qdisc lock is held.

We can avoid two atomic operations in xmit path, if we move this bit in a new __state container.

Location of this __state container is carefully chosen so that fast path only dirties one qdisc cache line.

THROTTLED bit could later be moved into this __state location too, to avoid dirtying first qdisc cache line.

---
 include/net/sch_generic.h |   15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)
include/net/sch_generic.h +11 -4
index 9707dae..b3591e4 100644
@@ -23,11 +23,17 @@ struct qdisc_rate_table {
 };
 
 enum qdisc_state_t {
-	__QDISC_STATE_RUNNING,
 	__QDISC_STATE_SCHED,
 	__QDISC_STATE_DEACTIVATED,
 };
 
+/*
+ * following bits are only changed while qdisc lock is held
+ */
+enum qdisc___state_t {
+	__QDISC___STATE_RUNNING,
+};
+
 struct qdisc_size_table {
 	struct list_head	list;
 	struct tc_sizespec	szopts;
@@ -72,23 +78,24 @@ struct Qdisc {
 	unsigned long		state;
 	struct sk_buff_head	q;
 	struct gnet_stats_basic_packed bstats;
+	unsigned long		__state;
 	struct gnet_stats_queue	qstats;
 	struct rcu_head     rcu_head;
 };
 
 static inline bool qdisc_is_running(struct Qdisc *qdisc)
 {
-	return test_bit(__QDISC_STATE_RUNNING, &qdisc->state);
+	return test_bit(__QDISC___STATE_RUNNING, &qdisc->__state);
 }
 
 static inline bool qdisc_run_begin(struct Qdisc *qdisc)
 {
-	return !test_and_set_bit(__QDISC_STATE_RUNNING, &qdisc->state);
+	return !__test_and_set_bit(__QDISC___STATE_RUNNING, &qdisc->__state);
 }
 
 static inline void qdisc_run_end(struct Qdisc *qdisc)
 {
-	clear_bit(__QDISC_STATE_RUNNING, &qdisc->state);
+	__clear_bit(__QDISC___STATE_RUNNING, &qdisc->__state);
 }
 
 struct Qdisc_class_ops {
maintainer
#16 lore raw

Re: [PATCH 2/2 net-next-2.6] net: QDISC_STATE_RUNNING dont need atomic bit ops

In reply to Eric Dumazet

From: Eric Dumazet <[email protected]>
Date: Wed, 02 Jun 2010 11:50:33 +0200

Quoted 5 lines

__QDISC_STATE_RUNNING is always changed while qdisc lock is held.

We can avoid two atomic operations in xmit path, if we move this bit in a new __state container.

Quoted 7 lines

Location of this __state container is carefully chosen so that fast path only dirties one qdisc cache line.

THROTTLED bit could later be moved into this __state location too, to avoid dirtying first qdisc cache line.

Also looks good, applied.

One thing about naming. Here, even though we name the type and the state member with two leading underscores, the things that actually modify these state members are helper functions with names that lack double underscores.

So really, reading the code, you don't see that special considerations for these state changes might be necessary.

maintainer Applied
#24 lore raw

Re: [PATCH] net: add additional lock to qdisc to increase throughput

In reply to Duyck, Alexander H

From: "Duyck, Alexander H" <[email protected]>
Date: Fri, 21 May 2010 13:04:20 -0700

Quoted 11 lines
Quoted 9 lines · Eric Dumazet

Tests with following script gave a boost from ~50.000 pps to ~600.000 pps on a dual quad core machine (E5450 @3.00GHz), tg3 driver. (A single netperf flow can reach ~800.000 pps on this platform)

for j in seq 0 3; do
for i in seq 0 7; do

    netperf -H 192.168.0.1 -t UDP_STREAM -l 60 -N -T $i -- -m 6 &

done
done

Quoted 3 lines

Running the same script with your patch my results went from 200Kpps to 1.2Mpps on a dual Xeon 5570.

Applied, thanks guys.

#25 lore raw

Re: [PATCH] net: add additional lock to qdisc to increase throughput

Quoted 14 lines · David Miller

From: "Duyck, Alexander H" <[email protected]>
Date: Fri, 21 May 2010 13:04:20 -0700

Quoted 11 lines
Quoted 9 lines · Eric Dumazet

Tests with following script gave a boost from ~50.000 pps to ~600.000 pps on a dual quad core machine (E5450 @3.00GHz), tg3 driver. (A single netperf flow can reach ~800.000 pps on this platform)

for j in seq 0 3; do
for i in seq 0 7; do

    netperf -H 192.168.0.1 -t UDP_STREAM -l 60 -N -T $i -- -m 6 &

done
done

Quoted 5 lines
Quoted 3 lines

Running the same script with your patch my results went from 200Kpps to 1.2Mpps on a dual Xeon 5570.

Applied, thanks guys.

Thanks David, I realize you did all the necessary changes after qdisc_run_begin/qdisc_is_running/ integration ;)