[PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[Changli Gao]

reimplement completion_queue as a FIFO queue.

As slab allocator always does its best to return the latest unused objects, we'd
better release skb in order, this patch reimplement completion_queue as a FIFO
queue instead of the old LIFO queue.

At the same time, a opencoding skb queue is replaced with a sk_buff_head queue.

Signed-off-by: Changli Gao <xiaosuo@gmail.com>
----
 include/linux/netdevice.h |    2 +-
 net/core/dev.c            |   28 ++++++++++------------------
 net/core/netpoll.c        |   12 +++++-------
 3 files changed, 16 insertions(+), 26 deletions(-)
diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index 3c5ed5f..785e514 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -1386,7 +1386,7 @@ static inline int unregister_gifconf(unsigned int family)
 struct softnet_data {
 	struct Qdisc		*output_queue;
 	struct list_head	poll_list;
-	struct sk_buff		*completion_queue;
+	struct sk_buff_head	completion_queue;
 
 #ifdef CONFIG_RPS
 	struct softnet_data	*rps_ipi_list;
diff --git a/net/core/dev.c b/net/core/dev.c
index 4d43f1a..5bbfa0f 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -1578,8 +1578,7 @@ void dev_kfree_skb_irq(struct sk_buff *skb)
 
 		local_irq_save(flags);
 		sd = &__get_cpu_var(softnet_data);
-		skb->next = sd->completion_queue;
-		sd->completion_queue = skb;
+		__skb_queue_tail(&sd->completion_queue, skb);
 		raise_softirq_irqoff(NET_TX_SOFTIRQ);
 		local_irq_restore(flags);
 	}
@@ -2506,18 +2505,16 @@ static void net_tx_action(struct softirq_action *h)
 {
 	struct softnet_data *sd = &__get_cpu_var(softnet_data);
 
-	if (sd->completion_queue) {
-		struct sk_buff *clist;
+	if (!skb_queue_empty(&sd->completion_queue)) {
+		struct sk_buff_head queue;
+		struct sk_buff *skb;
 
+		__skb_queue_head_init(&queue);
 		local_irq_disable();
-		clist = sd->completion_queue;
-		sd->completion_queue = NULL;
+		skb_queue_splice_tail_init(&sd->completion_queue, &queue);
 		local_irq_enable();
 
-		while (clist) {
-			struct sk_buff *skb = clist;
-			clist = clist->next;
-
+		while ((skb = __skb_dequeue(&queue))) {
 			WARN_ON(atomic_read(&skb->users));
 			__kfree_skb(skb);
 		}
@@ -5593,7 +5590,6 @@ static int dev_cpu_callback(struct notifier_block *nfb,
 			    unsigned long action,
 			    void *ocpu)
 {
-	struct sk_buff **list_skb;
 	struct Qdisc **list_net;
 	struct sk_buff *skb;
 	unsigned int cpu, oldcpu = (unsigned long)ocpu;
@@ -5607,13 +5603,9 @@ static int dev_cpu_callback(struct notifier_block *nfb,
 	sd = &per_cpu(softnet_data, cpu);
 	oldsd = &per_cpu(softnet_data, oldcpu);
 
-	/* Find end of our completion_queue. */
-	list_skb = &sd->completion_queue;
-	while (*list_skb)
-		list_skb = &(*list_skb)->next;
 	/* Append completion queue from offline CPU. */
-	*list_skb = oldsd->completion_queue;
-	oldsd->completion_queue = NULL;
+	skb_queue_splice_tail_init(&oldsd->completion_queue,
+				   &sd->completion_queue);
 
 	/* Find end of our output_queue. */
 	list_net = &sd->output_queue;
@@ -5849,7 +5841,7 @@ static int __init net_dev_init(void)
 		struct softnet_data *sd = &per_cpu(softnet_data, i);
 
 		skb_queue_head_init(&sd->input_pkt_queue);
-		sd->completion_queue = NULL;
+		__skb_queue_head_init(&sd->completion_queue);
 		INIT_LIST_HEAD(&sd->poll_list);
 
 #ifdef CONFIG_RPS
diff --git a/net/core/netpoll.c b/net/core/netpoll.c
index a58f59b..3905a14 100644
--- a/net/core/netpoll.c
+++ b/net/core/netpoll.c
@@ -222,17 +222,15 @@ static void zap_completion_queue(void)
 	unsigned long flags;
 	struct softnet_data *sd = &get_cpu_var(softnet_data);
 
-	if (sd->completion_queue) {
-		struct sk_buff *clist;
+	if (!skb_queue_empty(&sd->completion_queue)) {
+		struct sk_buff_head queue;
+		struct sk_buff *skb;
 
 		local_irq_save(flags);
-		clist = sd->completion_queue;
-		sd->completion_queue = NULL;
+		skb_queue_splice_tail_init(&sd->completion_queue, &queue);
 		local_irq_restore(flags);
 
-		while (clist != NULL) {
-			struct sk_buff *skb = clist;
-			clist = clist->next;
+		while ((skb = __skb_dequeue(&queue))) {
 			if (skb->destructor) {
 				atomic_inc(&skb->users);
 				dev_kfree_skb_any(skb); /* put this one back */

Re: [PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[Eric Dumazet]

Le lundi 26 avril 2010 à 11:20 +0800, Changli Gao a écrit :
> reimplement completion_queue as a FIFO queue.
> 
> As slab allocator always does its best to return the latest unused objects, we'd
> better release skb in order, this patch reimplement completion_queue as a FIFO
> queue instead of the old LIFO queue.
> 

1) New devices dont use completion queue.

2) Hot objects are the last enqueued.
   If many objects were queued, the old one are not hot anymore.

   Using FIFO will give more cache misses, when walking the chain
(skb->next)

3) Claim about slab allocators properties are irrelevant. SLUB doesnt
touch objects, unless some debugging is on.

> At the same time, a opencoding skb queue is replaced with a sk_buff_head queue.
> 

Yes, this is a pro, yet it cost a bit more, because of extra things
(qlen management, and two pointers per object)

For example, compare text size before and after the patch.

If you feel open coding a LIFO is error prone, you could add generic
primitives to kernel ?

> Signed-off-by: Changli Gao <xiaosuo@gmail.com>
> ----
>  include/linux/netdevice.h |    2 +-
>  net/core/dev.c            |   28 ++++++++++------------------
>  net/core/netpoll.c        |   12 +++++-------
>  3 files changed, 16 insertions(+), 26 deletions(-)
> diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
> index 3c5ed5f..785e514 100644
> --- a/include/linux/netdevice.h
> +++ b/include/linux/netdevice.h
> @@ -1386,7 +1386,7 @@ static inline int unregister_gifconf(unsigned int family)
>  struct softnet_data {
>  	struct Qdisc		*output_queue;
>  	struct list_head	poll_list;
> -	struct sk_buff		*completion_queue;
> +	struct sk_buff_head	completion_queue;
>  
>  #ifdef CONFIG_RPS
>  	struct softnet_data	*rps_ipi_list;
> diff --git a/net/core/dev.c b/net/core/dev.c
> index 4d43f1a..5bbfa0f 100644
> --- a/net/core/dev.c
> +++ b/net/core/dev.c
> @@ -1578,8 +1578,7 @@ void dev_kfree_skb_irq(struct sk_buff *skb)
>  
>  		local_irq_save(flags);
>  		sd = &__get_cpu_var(softnet_data);
> -		skb->next = sd->completion_queue;
> -		sd->completion_queue = skb;
> +		__skb_queue_tail(&sd->completion_queue, skb);
>  		raise_softirq_irqoff(NET_TX_SOFTIRQ);
>  		local_irq_restore(flags);
>  	}
> @@ -2506,18 +2505,16 @@ static void net_tx_action(struct softirq_action *h)
>  {
>  	struct softnet_data *sd = &__get_cpu_var(softnet_data);
>  
> -	if (sd->completion_queue) {
> -		struct sk_buff *clist;
> +	if (!skb_queue_empty(&sd->completion_queue)) {
> +		struct sk_buff_head queue;
> +		struct sk_buff *skb;
>  
> +		__skb_queue_head_init(&queue);
>  		local_irq_disable();
> -		clist = sd->completion_queue;
> -		sd->completion_queue = NULL;
> +		skb_queue_splice_tail_init(&sd->completion_queue, &queue);
>  		local_irq_enable();
>  
> -		while (clist) {
> -			struct sk_buff *skb = clist;
> -			clist = clist->next;
> -
> +		while ((skb = __skb_dequeue(&queue))) {
>  			WARN_ON(atomic_read(&skb->users));
>  			__kfree_skb(skb);
>  		}
> @@ -5593,7 +5590,6 @@ static int dev_cpu_callback(struct notifier_block *nfb,
>  			    unsigned long action,
>  			    void *ocpu)
>  {
> -	struct sk_buff **list_skb;
>  	struct Qdisc **list_net;
>  	struct sk_buff *skb;
>  	unsigned int cpu, oldcpu = (unsigned long)ocpu;
> @@ -5607,13 +5603,9 @@ static int dev_cpu_callback(struct notifier_block *nfb,
>  	sd = &per_cpu(softnet_data, cpu);
>  	oldsd = &per_cpu(softnet_data, oldcpu);
>  
> -	/* Find end of our completion_queue. */
> -	list_skb = &sd->completion_queue;
> -	while (*list_skb)
> -		list_skb = &(*list_skb)->next;
>  	/* Append completion queue from offline CPU. */
> -	*list_skb = oldsd->completion_queue;
> -	oldsd->completion_queue = NULL;
> +	skb_queue_splice_tail_init(&oldsd->completion_queue,
> +				   &sd->completion_queue);
>  
>  	/* Find end of our output_queue. */
>  	list_net = &sd->output_queue;
> @@ -5849,7 +5841,7 @@ static int __init net_dev_init(void)
>  		struct softnet_data *sd = &per_cpu(softnet_data, i);
>  
>  		skb_queue_head_init(&sd->input_pkt_queue);
> -		sd->completion_queue = NULL;
> +		__skb_queue_head_init(&sd->completion_queue);
>  		INIT_LIST_HEAD(&sd->poll_list);
>  
>  #ifdef CONFIG_RPS
> diff --git a/net/core/netpoll.c b/net/core/netpoll.c
> index a58f59b..3905a14 100644
> --- a/net/core/netpoll.c
> +++ b/net/core/netpoll.c
> @@ -222,17 +222,15 @@ static void zap_completion_queue(void)
>  	unsigned long flags;
>  	struct softnet_data *sd = &get_cpu_var(softnet_data);
>  
> -	if (sd->completion_queue) {
> -		struct sk_buff *clist;
> +	if (!skb_queue_empty(&sd->completion_queue)) {
> +		struct sk_buff_head queue;
> +		struct sk_buff *skb;
>  
>  		local_irq_save(flags);
> -		clist = sd->completion_queue;
> -		sd->completion_queue = NULL;
> +		skb_queue_splice_tail_init(&sd->completion_queue, &queue);
>  		local_irq_restore(flags);
>  
> -		while (clist != NULL) {
> -			struct sk_buff *skb = clist;
> -			clist = clist->next;
> +		while ((skb = __skb_dequeue(&queue))) {
>  			if (skb->destructor) {
>  				atomic_inc(&skb->users);
>  				dev_kfree_skb_any(skb); /* put this one back */
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[Changli Gao]

On Mon, Apr 26, 2010 at 1:14 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le lundi 26 avril 2010 à 11:20 +0800, Changli Gao a écrit :
>> reimplement completion_queue as a FIFO queue.
>>
>> As slab allocator always does its best to return the latest unused objects, we'd
>> better release skb in order, this patch reimplement completion_queue as a FIFO
>> queue instead of the old LIFO queue.
>>
>
> 1) New devices dont use completion queue.

It is good enough reason for rejection.

>
> 2) Hot objects are the last enqueued.
>   If many objects were queued, the old one are not hot anymore.
>
>   Using FIFO will give more cache misses, when walking the chain
> (skb->next)
>

I meaned that slab allocator maintains objects in the LIFO manner, and
if we call kmem_cache_alloc(cache) after a kmem_cache_free(cache)
call, the last object freed by kmem_cache_free(cache) will be
returned, as this object are more likely in cache and hot. If we don't
realse skbs in FIFO manner, the last and hot one will not been
returned at first.

-- 
Regards，
Changli Gao(xiaosuo@gmail.com)

Re: [PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[Eric Dumazet]

Le lundi 26 avril 2010 à 13:44 +0800, Changli Gao a écrit :
> On Mon, Apr 26, 2010 at 1:14 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > Le lundi 26 avril 2010 à 11:20 +0800, Changli Gao a écrit :
> >> reimplement completion_queue as a FIFO queue.
> >>
> >> As slab allocator always does its best to return the latest unused objects, we'd
> >> better release skb in order, this patch reimplement completion_queue as a FIFO
> >> queue instead of the old LIFO queue.
> >
> >
> > 1) New devices dont use completion queue.
> 
> It is good enough reason for rejection.
> 

I said, this part of the kernel is not used today.

> >
> > 2) Hot objects are the last enqueued.
> >   If many objects were queued, the old one are not hot anymore.
> >
> >   Using FIFO will give more cache misses, when walking the chain
> > (skb->next)
> >
> 
> I meaned that slab allocator maintains objects in the LIFO manner, and
> if we call kmem_cache_alloc(cache) after a kmem_cache_free(cache)
> call, the last object freed by kmem_cache_free(cache) will be
> returned, as this object are more likely in cache and hot. If we don't
> realse skbs in FIFO manner, the last and hot one will not been
> returned at first.
> 

But your patch doesnt change this behavior. This is irrelevant.

LIFO is the slub behavior, for the exact reason its better for cache
reuse. Same for completion queue.

I repeat : 
- slub dont touch objects in normal situations.
- LIFO is better for caches.
- LIFO is faster (one pointer for the queue head)

Re: [PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Mon, 26 Apr 2010 08:09:14 +0200

> LIFO is the slub behavior, for the exact reason its better for cache
> reuse. Same for completion queue.
> 
> I repeat : 
> - slub dont touch objects in normal situations.
> - LIFO is better for caches.
> - LIFO is faster (one pointer for the queue head)

No matter what is faster, we have to process packets in
FIFO order, otherwise we get reordering within a flow
which is to be absolutely avoided.

Re: [PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[Eric Dumazet]

Le dimanche 25 avril 2010 à 23:27 -0700, David Miller a écrit :

> No matter what is faster, we have to process packets in
> FIFO order, otherwise we get reordering within a flow
> which is to be absolutely avoided.

Hmm, completion queue is about freeing skb, and its name is misleading.

This queue is feed by dev_kfree_skb_irq() only

Re: [PATCH 1/2] net: reimplement completion_queue as a FIFO queue

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Mon, 26 Apr 2010 09:21:49 +0200

> Le dimanche 25 avril 2010 à 23:27 -0700, David Miller a écrit :
> 
>> No matter what is faster, we have to process packets in
>> FIFO order, otherwise we get reordering within a flow
>> which is to be absolutely avoided.
> 
> Hmm, completion queue is about freeing skb, and its name is misleading.
> 
> This queue is feed by dev_kfree_skb_irq() only

Ok I see, thanks for explaining.