Execute tasklets in the same order they were queued
Subsystems (2)
PATCH 1/1 Execute tasklets in the same order they were queued
I noticed this when looking at an openswan issue. Openswan (ab?)uses the tasklet API to defer processing of packets in some situations, with one packet per tasklet_action(). I started noticing sequences of reverse-ordered sequence numbers coming over the wire, since new tasklets are always queued at the head of the list but processed sequentially.
Convert it to instead append new entries to the tail of the list. As an extra bonus, the splicing code in takeover_tasklets() no longer has to iterate over the list.
kernel/softirq.c +41 -20
@@ -355,7 +355,8 @@ void open_softirq(int nr, void (*action)(struct softirq_action*), void *data)/* Tasklets */ struct tasklet_head { -struct tasklet_struct *list; +struct tasklet_struct *head; +struct tasklet_struct **tail; };/* Some compilers disobey section attribute on statics when not
@@ -368,8 +369,9 @@ void __tasklet_schedule(struct tasklet_struct *t)unsigned long flags;local_irq_save (flags); - t->next =__get_cpu_var (tasklet_vec).list; -__get_cpu_var (tasklet_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_vec).tail = t; +__get_cpu_var (tasklet_vec).tail = &(t->next);raise_softirq_irqoff (TASKLET_SOFTIRQ );local_irq_restore (flags); }
@@ -381,8 +383,9 @@ void __tasklet_hi_schedule(struct tasklet_struct *t)unsigned long flags;local_irq_save (flags); - t->next =__get_cpu_var (tasklet_hi_vec).list; -__get_cpu_var (tasklet_hi_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_hi_vec).tail = t; +__get_cpu_var (tasklet_hi_vec).tail = &(t->next);raise_softirq_irqoff (HI_SOFTIRQ );local_irq_restore (flags); }
@@ -394,8 +397,9 @@ static void tasklet_action(struct softirq_action *a)struct tasklet_struct *list;local_irq_disable (); - list =__get_cpu_var (tasklet_vec).list; -__get_cpu_var (tasklet_vec).list =NULL ; + list =__get_cpu_var (tasklet_vec).head; +__get_cpu_var (tasklet_vec).head =NULL ; +__get_cpu_var (tasklet_vec).tail = &__get_cpu_var (tasklet_vec).head;local_irq_enable ();while (list) {
@@ -415,8 +419,9 @@ static void tasklet_action(struct softirq_action *a) }local_irq_disable (); - t->next =__get_cpu_var (tasklet_vec).list; -__get_cpu_var (tasklet_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_vec).tail = t; +__get_cpu_var (tasklet_vec).tail = &(t->next);__raise_softirq_irqoff (TASKLET_SOFTIRQ );local_irq_enable (); }
@@ -427,8 +432,9 @@ static void tasklet_hi_action(struct softirq_action *a)struct tasklet_struct *list;local_irq_disable (); - list =__get_cpu_var (tasklet_hi_vec).list; -__get_cpu_var (tasklet_hi_vec).list =NULL ; + list =__get_cpu_var (tasklet_hi_vec).head; +__get_cpu_var (tasklet_hi_vec).head =NULL ; +__get_cpu_var (tasklet_hi_vec).tail = &__get_cpu_var (tasklet_hi_vec).head;local_irq_enable ();while (list) {
@@ -448,8 +454,9 @@ static void tasklet_hi_action(struct softirq_action *a) }local_irq_disable (); - t->next =__get_cpu_var (tasklet_hi_vec).list; -__get_cpu_var (tasklet_hi_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_hi_vec).tail = t; +__get_cpu_var (tasklet_hi_vec).tail = &(t->next);__raise_softirq_irqoff (HI_SOFTIRQ );local_irq_enable (); }
@@ -486,6 +493,15 @@ EXPORT_SYMBOL(tasklet_kill);void __init softirq_init (void ) { +int cpu; + +for_each_possible_cpu (cpu) { +per_cpu (tasklet_vec, cpu).tail = + &per_cpu (tasklet_vec, cpu).head; +per_cpu (tasklet_hi_vec, cpu).tail = + &per_cpu (tasklet_hi_vec, cpu).head; + } +open_softirq (TASKLET_SOFTIRQ , tasklet_action,NULL );open_softirq (HI_SOFTIRQ , tasklet_hi_action,NULL ); }
@@ -554,9 +570,12 @@ void tasklet_kill_immediate(struct tasklet_struct *t, unsigned int cpu)return ;/* CPU is dead, so no lock needed. */ -for (i = &per_cpu (tasklet_vec, cpu).list; *i; i = &(*i)->next) { +for (i = &per_cpu (tasklet_vec, cpu).head; *i; i = &(*i)->next) {if (*i == t) { *i = t->next; +/* If this was the tail element, move the tail ptr */ +if (*i ==NULL ) +per_cpu (tasklet_vec, cpu).tail = i;return ; } }
@@ -571,14 +590,16 @@ static void takeover_tasklets(unsigned int cpu)local_irq_disable ();/* Find end, append list for that CPU. */ -for (i = &__get_cpu_var (tasklet_vec).list; *i; i = &(*i)->next); - *i =per_cpu (tasklet_vec, cpu).list; -per_cpu (tasklet_vec, cpu).list =NULL ; + *__get_cpu_var (tasklet_vec).tail =per_cpu (tasklet_vec, cpu).head; +__get_cpu_var (tasklet_vec).tail =per_cpu (tasklet_vec, cpu).tail; +per_cpu (tasklet_vec, cpu).head =NULL ; +per_cpu (tasklet_vec, cpu).next = &per_cpu (tasklet_vec, cpu).head;raise_softirq_irqoff (TASKLET_SOFTIRQ ); -for (i = &__get_cpu_var (tasklet_hi_vec).list; *i; i = &(*i)->next); - *i =per_cpu (tasklet_hi_vec, cpu).list; -per_cpu (tasklet_hi_vec, cpu).list =NULL ; + *__get_cpu_var (tasklet_hi_vec).tail =per_cpu (tasklet_hi_vec, cpu).head; +__get_cpu_var (tasklet_hi_vec).tail =per_cpu (tasklet_hi_vec, cpu).tail; +per_cpu (tasklet_hi_vec, cpu).head =NULL ; +per_cpu (tasklet_hi_vec, cpu).next = &per_cpu (tasklet_hi_vec, cpu).head;raise_softirq_irqoff (HI_SOFTIRQ );local_irq_enable ();
Quoted 10 lines · On Mon, 11 Feb 2008 16:28:13 -0600 Olof Johansson <[email protected]> wrote:
I noticed this when looking at an openswan issue. Openswan (ab?)uses the tasklet API to defer processing of packets in some situations, with one packet per
tasklet_action(). I started noticing sequences of reverse-ordered sequence numbers coming over the wire, since new tasklets are always queued at the head of the list but processed sequentially.Convert it to instead append new entries to the tail of the list. As an extra bonus, the splicing code in
takeover_tasklets()no longer has to iterate over the list.
hm, I'd have thought that this would already have caused problems in networking. And perhaps this change might have effects on networking too?
Probably it won't have _much_ effect on networking because networking probably isn't queueing one tasklet per packet(!) but perhaps with bonded channels or something like that?
Quoted 9 lines · On Mon, 11 Feb 2008 16:28:13 -0600 Olof Johansson <[email protected]> wrote:
I noticed this when looking at an openswan issue. Openswan (ab?)uses the tasklet API to defer processing of packets in some situations, with one packet per
tasklet_action(). I started noticing sequences of reverse-ordered sequence numbers coming over the wire, since new tasklets are always queued at the head of the list but processed sequentially.Convert it to instead append new entries to the tail of the list. As an extra bonus, the splicing code in
takeover_tasklets()no longer has to iterate over the list.
kernel/softirq.c: In function 'takeover_tasklets':kernel/softirq.c:597: error: 'struct tasklet_head' has no member named 'next' kernel/softirq.c:603: error: 'struct tasklet_head' has no member named 'next' kernel/softirq.c:588: warning: unused variable 'i'
PATCH v2 1/1 Execute tasklets in the same order they were queued
I noticed this when looking at an openswan issue. Openswan (ab?)uses the tasklet API to defer processing of packets in some situations, with one packet per tasklet_action(). I started noticing sequences of backwards-ordered sequence numbers coming over the wire, since new tasklets are always queued at the head of the list but processed sequentially.
Convert it to instead append new entries to the tail of the list. As an extra bonus, the splicing code in takeover_tasklets() no longer has to iterate over the list.
---
Quoted 4 lines · Andrew Morton
kernel/softirq.c: In function 'takeover_tasklets':kernel/softirq.c:597: error: 'structtasklet_head' has no member named 'next'kernel/softirq.c:603: error: 'structtasklet_head' has no member named 'next'kernel/softirq.c:588: warning: unused variable 'i'
How embarrassing. CONFIG_HOTPLUG_CPU was off when I built before I posted.
-Olof
kernel/softirq.c +41 -22
@@ -355,7 +355,8 @@ void open_softirq(int nr, void (*action)(struct softirq_action*), void *data)/* Tasklets */ struct tasklet_head { -struct tasklet_struct *list; +struct tasklet_struct *head; +struct tasklet_struct **tail; };/* Some compilers disobey section attribute on statics when not
@@ -368,8 +369,9 @@ void __tasklet_schedule(struct tasklet_struct *t)unsigned long flags;local_irq_save (flags); - t->next =__get_cpu_var (tasklet_vec).list; -__get_cpu_var (tasklet_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_vec).tail = t; +__get_cpu_var (tasklet_vec).tail = &(t->next);raise_softirq_irqoff (TASKLET_SOFTIRQ );local_irq_restore (flags); }
@@ -381,8 +383,9 @@ void __tasklet_hi_schedule(struct tasklet_struct *t)unsigned long flags;local_irq_save (flags); - t->next =__get_cpu_var (tasklet_hi_vec).list; -__get_cpu_var (tasklet_hi_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_hi_vec).tail = t; +__get_cpu_var (tasklet_hi_vec).tail = &(t->next);raise_softirq_irqoff (HI_SOFTIRQ );local_irq_restore (flags); }
@@ -394,8 +397,9 @@ static void tasklet_action(struct softirq_action *a)struct tasklet_struct *list;local_irq_disable (); - list =__get_cpu_var (tasklet_vec).list; -__get_cpu_var (tasklet_vec).list =NULL ; + list =__get_cpu_var (tasklet_vec).head; +__get_cpu_var (tasklet_vec).head =NULL ; +__get_cpu_var (tasklet_vec).tail = &__get_cpu_var (tasklet_vec).head;local_irq_enable ();while (list) {
@@ -415,8 +419,9 @@ static void tasklet_action(struct softirq_action *a) }local_irq_disable (); - t->next =__get_cpu_var (tasklet_vec).list; -__get_cpu_var (tasklet_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_vec).tail = t; +__get_cpu_var (tasklet_vec).tail = &(t->next);__raise_softirq_irqoff (TASKLET_SOFTIRQ );local_irq_enable (); }
@@ -427,8 +432,9 @@ static void tasklet_hi_action(struct softirq_action *a)struct tasklet_struct *list;local_irq_disable (); - list =__get_cpu_var (tasklet_hi_vec).list; -__get_cpu_var (tasklet_hi_vec).list =NULL ; + list =__get_cpu_var (tasklet_hi_vec).head; +__get_cpu_var (tasklet_hi_vec).head =NULL ; +__get_cpu_var (tasklet_hi_vec).tail = &__get_cpu_var (tasklet_hi_vec).head;local_irq_enable ();while (list) {
@@ -448,8 +454,9 @@ static void tasklet_hi_action(struct softirq_action *a) }local_irq_disable (); - t->next =__get_cpu_var (tasklet_hi_vec).list; -__get_cpu_var (tasklet_hi_vec).list = t; + t->next =NULL ; + *__get_cpu_var (tasklet_hi_vec).tail = t; +__get_cpu_var (tasklet_hi_vec).tail = &(t->next);__raise_softirq_irqoff (HI_SOFTIRQ );local_irq_enable (); }
@@ -486,6 +493,15 @@ EXPORT_SYMBOL(tasklet_kill);void __init softirq_init (void ) { +int cpu; + +for_each_possible_cpu (cpu) { +per_cpu (tasklet_vec, cpu).tail = + &per_cpu (tasklet_vec, cpu).head; +per_cpu (tasklet_hi_vec, cpu).tail = + &per_cpu (tasklet_hi_vec, cpu).head; + } +open_softirq (TASKLET_SOFTIRQ , tasklet_action,NULL );open_softirq (HI_SOFTIRQ , tasklet_hi_action,NULL ); }
@@ -554,9 +570,12 @@ void tasklet_kill_immediate(struct tasklet_struct *t, unsigned int cpu)return ;/* CPU is dead, so no lock needed. */ -for (i = &per_cpu (tasklet_vec, cpu).list; *i; i = &(*i)->next) { +for (i = &per_cpu (tasklet_vec, cpu).head; *i; i = &(*i)->next) {if (*i == t) { *i = t->next; +/* If this was the tail element, move the tail ptr */ +if (*i ==NULL ) +per_cpu (tasklet_vec, cpu).tail = i;return ; } }
@@ -565,20 +584,20 @@ void tasklet_kill_immediate(struct tasklet_struct *t, unsigned int cpu)static void takeover_tasklets (unsigned int cpu) { -struct tasklet_struct **i; -/* CPU is dead, so no lock needed. */ local_irq_disable ();/* Find end, append list for that CPU. */ -for (i = &__get_cpu_var (tasklet_vec).list; *i; i = &(*i)->next); - *i =per_cpu (tasklet_vec, cpu).list; -per_cpu (tasklet_vec, cpu).list =NULL ; + *__get_cpu_var (tasklet_vec).tail =per_cpu (tasklet_vec, cpu).head; +__get_cpu_var (tasklet_vec).tail =per_cpu (tasklet_vec, cpu).tail; +per_cpu (tasklet_vec, cpu).head =NULL ; +per_cpu (tasklet_vec, cpu).tail = &per_cpu (tasklet_vec, cpu).head;raise_softirq_irqoff (TASKLET_SOFTIRQ ); -for (i = &__get_cpu_var (tasklet_hi_vec).list; *i; i = &(*i)->next); - *i =per_cpu (tasklet_hi_vec, cpu).list; -per_cpu (tasklet_hi_vec, cpu).list =NULL ; + *__get_cpu_var (tasklet_hi_vec).tail =per_cpu (tasklet_hi_vec, cpu).head; +__get_cpu_var (tasklet_hi_vec).tail =per_cpu (tasklet_hi_vec, cpu).tail; +per_cpu (tasklet_hi_vec, cpu).head =NULL ; +per_cpu (tasklet_hi_vec, cpu).tail = &per_cpu (tasklet_hi_vec, cpu).head;raise_softirq_irqoff (HI_SOFTIRQ );local_irq_enable ();
Quoted 10 lines · On Tue, 12 Feb 2008 16:06:47 -0600 Olof Johansson <[email protected]> wrote:
I noticed this when looking at an openswan issue. Openswan (ab?)uses the tasklet API to defer processing of packets in some situations, with one packet per
tasklet_action(). I started noticing sequences of backwards-ordered sequence numbers coming over the wire, since new tasklets are always queued at the head of the list but processed sequentially.Convert it to instead append new entries to the tail of the list. As an extra bonus, the splicing code in
takeover_tasklets()no longer has to iterate over the list.
hm, well, let's see what if any effect this has on networking.
I'll cheerily tag this as to-be-merged-via-git-sched. Ingo wasn't doing much anyway.