net: Xmit Packet Steering (XPS)

net/core/dev.c +0 -2

@@ -2024,8 +2026,6 @@ gso:
           Either shot noqueue qdisc, it is even simpler 8)
         */
        if (dev->flags & IFF_UP) {
-               int cpu = smp_processor_id(); /* ok because BHs are off */
-
                if (txq->xmit_lock_owner != cpu) {
 
                        HARD_TX_LOCK(dev, txq, cpu);

@@ -2967,7 +2967,7 @@ static void net_rx_action(struct softirq_action *h)
        }

 out:
       local_irq_enable();
-
+       xps_flush();

Quoted 8 lines · Eric Dumazet

net/core/dev.c +0 -0

index 9977288..9e134f6 100644
@@ -2000,6 +2001,7 @@ gso:
        */
       rcu_read_lock_bh();
 

net/core/dev.c gso: · line 2006

Quoted 3 lines

net/core/dev.c +1 -0

+       skb->sending_cpu = cpu = smp_processor_id();
       txq = dev_pick_tx(dev, skb);
       q = rcu_dereference(txq->qdisc);

I think assigning cpu to skb->sending_cpu just before calling hard_start_xmit is better, because the CPU which dequeues the skb will be another one.

Quoted 9 lines

net/core/dev.c +0 -2

@@ -2024,8 +2026,6 @@ gso:
          Either shot noqueue qdisc, it is even simpler 8)
        */
       if (dev->flags & IFF_UP) {
-               int cpu = smp_processor_id(); /* ok because BHs are off */
-
               if (txq->xmit_lock_owner != cpu) {
 

net/core/dev.c static void net_rx_action(struct softirq_action *h) · line 2970

Quoted 7 lines

net/core/dev.c +1 -1

                       HARD_TX_LOCK(dev, txq, cpu);

@@ -2967,7 +2967,7 @@ static void net_rx_action(struct softirq_action *h)
       }
 out:
       local_irq_enable();
-
+       xps_flush();

If there isn't any new skbs, the memory will be hold forever. I know you want to eliminate unnecessary IPI, how about sending IPI only when the remote xps_pcpu_queues are changed from empty to nonempty?

Quoted 9 lines · Changli Gao

Quoted 8 lines · Eric Dumazet

net/core/dev.c +0 -0

index 9977288..9e134f6 100644
@@ -2000,6 +2001,7 @@ gso:
         */
        rcu_read_lock_bh();
 

Quoted 7 lines

net/core/dev.c gso: · line 2006

Quoted 3 lines

net/core/dev.c +1 -0

+       skb->sending_cpu = cpu = smp_processor_id();
        txq = dev_pick_tx(dev, skb);
        q = rcu_dereference(txq->qdisc);

I think assigning cpu to skb->sending_cpu just before calling hard_start_xmit is better, because the CPU which dequeues the skb will be another one.

I want to record the application CPU, because I want the application CPU to call sock_wfree(), not the CPU that happened to dequeue skb to transmit it in case of txq contention.

Quoted 9 lines

Quoted 9 lines

net/core/dev.c +0 -2

@@ -2024,8 +2026,6 @@ gso:
           Either shot noqueue qdisc, it is even simpler 8)
         */
        if (dev->flags & IFF_UP) {
-               int cpu = smp_processor_id(); /* ok because BHs are off */
-
                if (txq->xmit_lock_owner != cpu) {
 

Quoted 11 lines

Quoted 7 lines

net/core/dev.c +0 -0

                        HARD_TX_LOCK(dev, txq, cpu);

@@ -2967,7 +2967,7 @@ static void net_rx_action(struct softirq_action *h)
        }

 out:
       local_irq_enable();
-
+       xps_flush();

If there isn't any new skbs, the memory will be hold forever. I know you want to eliminate unnecessary IPI, how about sending IPI only when the remote xps_pcpu_queues are changed from empty to nonempty?

I dont understand your remark, and dont see the problem, yet.

I send IPI only on cpus I know I have at least one skb queueud for them. For each cpu taking TX completion interrupts I have :

One bitmask (xps_cpus) of cpus I will eventually send IPI at end of net_rx_action()

You call xps_flush() in net_rx_aciton(). It means that if no new packet arrives, xps_flush() won't be called forever, and the memory used by skbs will be hold forever. Did I misunderstand? Your algorithm only works with packet forwarding but sending packets from local sockets.

Changli Gao a écrit :

Please re-read my patch, you misunderstood it, or I dont get you.

If xps_consume_skb(skb) is ever called (from one to XXX times), then we xps_flush() them, from net_rx_action()

net_rx_action()
{
       while (has_work) {
               perform_napi_things(); // calls xps_consume_skb() }
       xps_flush(); // post things to remote cpus, and dont leak memory }

This net_rx_action() is same for forwarding and localy generated packets.

Quoted 3 lines · Eric Dumazet

Changli Gao a écrit :

Please re-read my patch, you misunderstood it, or I dont get you.

I think I didn't misunderstand it. If local socket only sends packets, which don't need replies from receiver, so new NIC RX IRQ, and NET_RX softirq won't be triggered. Who will call xps_flush() to free the memory used by locally generated packets?

Quoted 10 lines · Changli Gao

Quoted 3 lines · Eric Dumazet

Changli Gao a écrit :

Please re-read my patch, you misunderstood it, or I dont get you.

I think I didn't misunderstand it. If local socket only sends packets, which don't need replies from receiver, so new NIC RX IRQ, and NET_RX softirq won't be triggered. Who will call xps_flush() to free the memory used by locally generated packets?

Changli, when we transmit a skb on NIC, NIC is supposed to have a TX completion call back, to free this skb.

These completion calls are running from net_rx_action(), if driver is NAPI enabled.

Only NAPI enabled drivers are allowed to use XPS infrastructure.

I sent 100.000.000 packets in my pktgen+tg3 tests, without receiving a single packet in return, I can tell you all packets were correctly freed :)

On Thu, Nov 19, 2009 at 3:46 PM, Eric Dumazet <[email protected] <mailto:[email protected]>> wrote:

Here is first version of XPS.

Very cool! The infrastructure to move lists of skb's from cpu to another and the IPI to kick processing look like something that could be consolidated between rps and xps :-)

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

Because I chose to union skb->iif with skb->sending_cpu, I chose to introduce a new xps_consume_skb(skb), and not generalize consume_skb() itself.

This means that selected drivers must use new function to benefit from XPS

Is this better than modifying consume_skb so this can be used by any driver?

Preliminary tests are quite good, especially on NUMA machines.

Only NAPI drivers can use this new infrastructure (xps_consume_skb() cannot
be called from hardirq context, only from softirq)

Is this a strict requirement, especially considering devices with separate TX interrupts? For a hardirq we could we just put the skb on local percpu queue and schedule a softirq to do the ipi.

Here is first version of XPS.

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

Because I chose to union skb->iif with skb->sending_cpu, I chose
to introduce a new xps_consume_skb(skb), and not generalize consume_skb() itself.

This means that selected drivers must use new function to benefit from XPS

Preliminary tests are quite good, especially on NUMA machines.

Only NAPI drivers can use this new infrastructure (xps_consume_skb() cannot be called from hardirq context, only from softirq)

I converted tg3 and pktgen for my tests

Signed-off-by Eric Dumazet <[email protected]>

---

net/core/xps.c +5 -0

+/*
+ * called at end of net_rx_action()
+ * preemption (and cpu migration/offline/online) disabled
+ */
+void xps_flush(void)

net/core/xps.c +23 -0

+			prevlen = skb_queue_len(&q->list);
+			skb_queue_splice_init(&head[cpu], &q->list);
+			spin_unlock(&q->list.lock);
+			/*
+			 * We hope remote cpu will be fast enough to transfert
+			 * this list to its completion queue before our
+			 * next xps_flush() call
+			 */
+			if (!prevlen)
+				__smp_call_function_single(cpu, &q->csd, 0);
+			continue;
+		}
+		/*
+		 * ok, we must free these skbs, even if we tried to avoid it :)
+		 */
+		while ((skb = __skb_dequeue(&head[cpu])) != NULL)
+			__kfree_skb(skb);
+	}
+	cpus_clear(__get_cpu_var(xps_cpus));
+}
+
+/*
+ * called from hardirq (IPI) context

net/core/xps.c +9 -0

+	sd = &__get_cpu_var(softnet_data);
+	last->next = sd->completion_queue;
+	sd->completion_queue = q->list.next;
+	__skb_queue_head_init(&q->list);
+
+	spin_unlock(&q->list.lock);
+
+	raise_softirq_irqoff(NET_TX_SOFTIRQ);
+}

Quoted 3 lines · Eric Dumazet

Here is first version of XPS.

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

But why?... OK, you write in another message about sock_wfree(). Then how about users, who don't sock_wfree (routers)? Will there be any way to disable it?

net/core/xps.c line 6

Quoted 6 lines

net/core/xps.c +6 -0

+/*
+ * XPS : Xmit Packet Steering
+ *
+ * TX completion packet freeing is performed on cpu that sent packet.
+ */
+#if defined(CONFIG_SMP)

Shouldn't it be in the Makefile?

...

Quoted 11 lines

net/core/xps.c +11 -0

+/*
+ * called at end of net_rx_action()
+ * preemption (and cpu migration/offline/online) disabled
+ */
+void xps_flush(void)
+{
+	int cpu, prevlen;
+	struct sk_buff_head *head = per_cpu_ptr(xps_array, smp_processor_id());
+	struct xps_pcpu_queue *q;
+	struct sk_buff *skb;
+

net/core/xps.c line 81

Quoted 4 lines

net/core/xps.c +4 -0

+	for_each_cpu_mask_nr(cpu, __get_cpu_var(xps_cpus)) {
+		q = &per_cpu(xps_pcpu_queue, cpu);
+		if (cpu_online(cpu)) {
+			spin_lock(&q->list.lock);

This lock probably needs irq disabling: let's say 2 cpus run this at the same time and both are interrupted with these (previously scheduled) IPIs?

Quoted 4 lines

net/core/xps.c +4 -0

+static void remote_free_skb_list(void *arg)
+{
+	struct sk_buff *last;
+	struct softnet_data *sd;

net/core/xps.c line 114

Quoted 5 lines

net/core/xps.c +5 -0

+	struct xps_pcpu_queue *q = arg; /* &__get_cpu_var(xps_pcpu_queue); */
+
+	spin_lock(&q->list.lock);
+
+	last = q->list.prev;

Is q->list handled in case this cpu goes down before this IPI is triggered?

Quoted 3 lines · Jarek Poplawski

Quoted 2 lines · Eric Dumazet

Here is first version of XPS.

Quoted 5 lines

Quoted 1 line

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

But why?... OK, you write in another message about sock_wfree(). Then how about users, who don't sock_wfree (routers)? Will there be any way to disable it?

This is open for discussion, but I saw no problem with routing workloads.

sock_wfree() is not that expensive for tcp anyway.
You also have a cost of kfreeing() two blocks of memory per skb, if allocation was done by another cpu.

If this happens to be a problem, we can immediately free packet if it has no destructors :

At xmit time, initialize skb->sending_cpu like that

skb->sending_cpu = (skb->destructor) ? smp_processor_id() : 0xFFFF;

to make sure we dont touch too many cache lines at tx completion time.

Quoted 8 lines

net/core/xps.c line 6

Quoted 6 lines

net/core/xps.c +6 -0

+/*
+ * XPS : Xmit Packet Steering
+ *
+ * TX completion packet freeing is performed on cpu that sent packet.
+ */
+#if defined(CONFIG_SMP)

Shouldn't it be in the Makefile?

It is in Makefile too, I let it in prelim code to make it clear this was CONFIG_SMP only.

Quoted 14 lines

...

Quoted 11 lines

net/core/xps.c +11 -0

+/*
+ * called at end of net_rx_action()
+ * preemption (and cpu migration/offline/online) disabled
+ */
+void xps_flush(void)
+{
+	int cpu, prevlen;
+	struct sk_buff_head *head = per_cpu_ptr(xps_array, smp_processor_id());
+	struct xps_pcpu_queue *q;
+	struct sk_buff *skb;
+

Quoted 8 lines

net/core/xps.c line 81

Quoted 4 lines

net/core/xps.c +4 -0

+	for_each_cpu_mask_nr(cpu, __get_cpu_var(xps_cpus)) {
+		q = &per_cpu(xps_pcpu_queue, cpu);
+		if (cpu_online(cpu)) {
+			spin_lock(&q->list.lock);

This lock probably needs irq disabling: let's say 2 cpus run this at the same time and both are interrupted with these (previously scheduled) IPIs?

Repeat after me :

lockdep is my friend, lockdep is my friend, lockdep is my friend... :)

Seriously, I must think again on this locking schem.

Quoted 4 lines

Quoted 4 lines

net/core/xps.c +4 -0

+static void remote_free_skb_list(void *arg)
+{
+	struct sk_buff *last;
+	struct softnet_data *sd;

Quoted 8 lines

net/core/xps.c line 114

Quoted 5 lines

net/core/xps.c +5 -0

+	struct xps_pcpu_queue *q = arg; /* &__get_cpu_var(xps_pcpu_queue); */
+
+	spin_lock(&q->list.lock);
+
+	last = q->list.prev;

Is q->list handled in case this cpu goes down before this IPI is triggered?

[block migration] (how ? this is the question)

if (cpu_online(cpu)) { 
	give_work_to_cpu(cpu);
	trigger IPI
} else {

handle_work_ourself()
}

[unblock migration]

General problem is : what guards cpu going off line between the if (cpu_online(cpu)) and the IPI.
I dont know yet, but it seems that disabling preemption is enough to get this guarantee. This seems strange.

We can add a notifier (or better call a function from existing one : dev_cpu_callback()) to flush this queue when necessary.

Quoted 6 lines · Eric Dumazet

Quoted 2 lines · Jarek Poplawski

On 20-11-2009 00:46, Eric Dumazet wrote:
scheduled) IPIs?

Repeat after me :

lockdep is my friend, lockdep is my friend, lockdep is my friend... :)

Hmm... Actually, why did I have to do lockdep's job...

Quoted 4 lines · Jarek Poplawski

Quoted 3 lines · Eric Dumazet

Quoted 2 lines · Jarek Poplawski

On 20-11-2009 00:46, Eric Dumazet wrote:
scheduled) IPIs?

Quoted 5 lines

Quoted 3 lines

Repeat after me :

lockdep is my friend, lockdep is my friend, lockdep is my friend... :)

Hmm... Actually, why did I have to do lockdep's job...

In fact I could not find why irq masking is necessary, and lockdep is fine with my code and my testings. Care to explain what problem you spotted ?

Quoted 4 lines · Eric Dumazet

Quoted 1 line

Hmm... Actually, why did I have to do lockdep's job...

In fact I could not find why irq masking is necessary, and lockdep is fine with my code and my testings. Care to explain what problem you spotted ?

CPU1 CPU2
net_rx_action() net_rx_action()
xps_flush() xps_flush()
q = &per_cpu(xps_pcpu_queue, cpu2) q = &per_cpu(xps_pcpu_queue, cpu1)
spin_lock(&q->list.lock of cpu2) spin_lock(&q->list.lock of cpu1)

<IPI> <IPI>
remote_free_skb_list() remote_free_skb_list()
waiting on spin_lock(&q->list.lock of cpu1) waiting on spin_lock(&q->list.lock of cpu2)

IPIs triggerered e.g. by CPU3 (or/and CPU4...) doing net_rx_action as well.

Here is first version of XPS.

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

Because I chose to union skb->iif with skb->sending_cpu, I chose
to introduce a new xps_consume_skb(skb), and not generalize consume_skb() itself.

This means that selected drivers must use new function to benefit from XPS

Preliminary tests are quite good, especially on NUMA machines.

Only NAPI drivers can use this new infrastructure (xps_consume_skb() cannot be called from hardirq context, only from softirq)

I converted tg3 and pktgen for my tests

Do you have numbers on this? It seems like a lot of effort to avoid transfering a few cache lines.

-Andi (who is a bit sceptical and would rather see generic work for this in slab)

Quoted 3 lines · Andi Kleen

Do you have numbers on this? It seems like a lot of effort to avoid transfering a few cache lines.

Lot of efforts ? hmm...

Yes, I know, but slab/slub is already quite optimized :)

It probably is a special case, but addresses a real problem. Like rps, this addresses the case where a single queue NIC is the bottleneck on a system. Anything that takes work off the interrupting core and spreads it to other cores may alleviate the bottleneck.

Here is first version of XPS.

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

Because I chose to union skb->iif with skb->sending_cpu, I chose
to introduce a new xps_consume_skb(skb), and not generalize consume_skb() itself.

include/linux/skbuff.h +4 -1

index 63f4742..e8e4795 100644
@@ -366,7 +366,10 @@ struct sk_buff {
 	struct nf_bridge_info	*nf_bridge;
 #endif
 
-	int			iif;
+	union {
+		int		iif;
+		int		sending_cpu;
+	};

net/core/dev.c +1 -0

index 9977288..9e134f6 100644
@@ -1965,6 +1965,7 @@ int dev_queue_xmit(struct sk_buff *skb)
 	struct netdev_queue *txq;
 	struct Qdisc *q;
 	int rc = -ENOMEM;
+	int cpu;
 
 	/* GSO will handle the following emulations directly. */
 	if (netif_needs_gso(dev, skb))

There is one more problem: this will break things like act_mirred + ifb, and other cases using skb->iif e.g. for filtering on virtual devices at the xmit path.

Quoted 3 lines · Jarek Poplawski

There is one more problem: this will break things like act_mirred + ifb, and other cases using skb->iif e.g. for filtering on virtual devices at the xmit path.

Following patch might help us to locate real uses of this obscure field :) [PATCH net-next-2.6] net: rename skb->iif to skb->skb_iif

Quoted 6 lines

Quoted 3 lines · Jarek Poplawski

There is one more problem: this will break things like act_mirred + ifb, and other cases using skb->iif e.g. for filtering on virtual devices at the xmit path.

Following patch might help us to locate real uses of this obscure field :) [PATCH net-next-2.6] net: rename skb->iif to skb->skb_iif

Prefixing member names generally doesn't end well. Prefixing selected member names? ick.

Prefixing member names generally doesn't end well. Prefixing selected member names? ick.

Quoted 5 lines · Jarek Poplawski

There is one more problem: this will break things like act_mirred + ifb, and other cases using skb->iif e.g. for filtering on virtual devices at the xmit path.

Following patch might help us to locate real uses of this obscure field :)

[PATCH net-next-2.6] net: rename skb->iif to skb->skb_iif

To help grep games, rename iif to skb_iif

Signed-off-by Eric Dumazet <[email protected]>

Goal of XPS is to free TX completed skbs by the cpu that submitted the transmit.

Because I chose to union skb->iif with skb->sending_cpu, I chose
to introduce a new xps_consume_skb(skb), and not generalize consume_skb() itself.

This means that selected drivers must use new function to benefit from XPS

Preliminary tests are quite good, especially on NUMA machines.

Only NAPI drivers can use this new infrastructure (xps_consume_skb() cannot be called from hardirq context, only from softirq)

I converted tg3 and pktgen for my tests

Signed-off-by Eric Dumazet <[email protected]>

I like this work. But as you know it still needs a little bit more work :-)

Let's also pick a more decent name for the free function since tons of drivers are going to call this thing. How about dev_kfree_tx_skb()? :-)

I see Jarek and you have come to a mutual understanding about the locking. Since you need to change it anyways to fix the deadlock, what using a netchannel like scheme to do remote SKB queueing?

PAGE_SIZE queue arrays, lockless access to head and tail pointers, and if queue is full we local free.

I think that's a reasonable policy and the only detail to work out is to make sure we never race on the IPI send and thus miss processing the queue.

What do you think?