[PATCH v2] Convert tasklet to per-cpu tasklet.

[PATCH v2] Convert tasklet to per-cpu tasklet.

[Konrad Rzeszutek Wilk]

Hey,

Dusting of this patchset which had been languishing
in my queue.

The presentation at XPDS 2016 by Intel poked me to brush this off.

The Intel folks have run guests with large amount of CPUs and have
discovered that the spinlock on the tasklet ends up taking an
quite large time. This patchset should fix this problem - and it had
fixed it for me when I tried to run benchmarks that used the
tasklet infrastructure.

The patches are also at:
  git://xenbits.xen.org/people/konradwilk/xen.git percpu_tasklet.v4.8.v2


 xen/common/tasklet.c      | 305 +++++++++++++++++++++++++++++++++-------------
 xen/include/xen/tasklet.h |  52 +++++++-
 2 files changed, 271 insertions(+), 86 deletions(-)

Konrad Rzeszutek Wilk (5):
      tasklet: Introduce per-cpu tasklet for softirq.
      tasklet: Add cross CPU feeding of per-cpu tasklets.
      tasklet: Remove the old-softirq implementation.
      tasklet: Introduce per-cpu tasklet for schedule tasklet.
      tasklet: Remove the scaffolding.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 1/5] tasklet: Introduce per-cpu tasklet for softirq.

[Konrad Rzeszutek Wilk]

This implements a lockless per-cpu tasklet mechanism.

The existing tasklet mechanism has a single global
spinlock that is taken every-time the global list
is touched. And we use this lock quite a lot - when
we call do_tasklet_work which is called via an softirq
and from the idle loop. We take the lock on any
operation on the tasklet_list.

The problem we are facing is that there are quite a lot of
tasklets scheduled. The most common one that is invoked is
the one injecting the VIRQ_TIMER in the guest. Guests
are not insane and don't set the one-shot or periodic
clocks to be in sub 1ms intervals (causing said tasklet
to be scheduled for such small intervalls).

This is especially an problem with guests that have a
large amount of VCPUs.

With this patch the problem disappears.

As such this patch introduces the code to setup
softirq per-cpu tasklets and only modifies the PCI
passthrough cases instead of doing it wholesale. This
is done because:
 - We want to easily bisect it if things break.
 - We modify the code one section at a time to
   make it easier to review this core code.

Now on the code itself. The Linux code (softirq.c)
has an per-cpu implementation of tasklets on which
this was based on. However there are differences:
 - This patch executes one tasklet at a time - similar
   to how the existing implementation does it.
 - We use a double-linked list instead of a single linked
   list. We could use a single-linked list but folks are
   more familiar with 'list_*' type macros.
 - This patch does not have the cross-CPU feeders
   implemented. That code is in the patch
   titled: tasklet: Add cross CPU feeding of per-cpu
   tasklets. This is done to support:
   "tasklet_schedule_on_cpu"
 - We add an temporary 'TASKLET_SOFTIRQ_PERCPU' which
   is can co-exist with the TASKLET_SOFTIRQ. It will be
   replaced in 'tasklet: Remove the old-softirq
   implementation."

Signed-off-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
---
RFC: First version
v1: Posted, folks asked if ticketlocks fixed it.
v2: Intel confirmed at XPDS 2016 that the problem is still present
    with large guests.

Cc: Jan Beulich <jbeulich@suse.com>
Cc: Andrew Cooper <andrew.cooper3@citrix.com>
Cc: "Lan, Tianyu" <tianyu.lan@intel.com>
Cc:  Kevin Tian <kevin.tian@intel.com>
Cc: Jun Nakajima <jun.nakajima@intel.com>
---
 xen/arch/x86/hvm/hvm.c    |   2 +-
 xen/common/tasklet.c      | 129 ++++++++++++++++++++++++++++++++++++++++++++--
 xen/include/xen/softirq.h |   1 +
 xen/include/xen/tasklet.h |  61 ++++++++++++++++++++--
 4 files changed, 183 insertions(+), 10 deletions(-)

diff --git a/xen/arch/x86/hvm/hvm.c b/xen/arch/x86/hvm/hvm.c
index 0180f26..d933ddd 100644
--- a/xen/arch/x86/hvm/hvm.c
+++ b/xen/arch/x86/hvm/hvm.c
@@ -1511,7 +1511,7 @@ int hvm_vcpu_initialise(struct vcpu *v)
     if ( (rc = hvm_funcs.vcpu_initialise(v)) != 0 ) /* teardown: hvm_funcs.vcpu_destroy */
         goto fail3;
 
-    softirq_tasklet_init(
+    percpu_tasklet_init(
         &v->arch.hvm_vcpu.assert_evtchn_irq_tasklet,
         (void(*)(unsigned long))hvm_assert_evtchn_irq,
         (unsigned long)v);
diff --git a/xen/common/tasklet.c b/xen/common/tasklet.c
index 4e42fa7..319866f 100644
--- a/xen/common/tasklet.c
+++ b/xen/common/tasklet.c
@@ -31,10 +31,30 @@ static DEFINE_PER_CPU(struct list_head, softirq_tasklet_list);
 /* Protects all lists and tasklet structures. */
 static DEFINE_SPINLOCK(tasklet_lock);
 
+static DEFINE_PER_CPU(struct list_head, softirq_list);
+
 static void tasklet_enqueue(struct tasklet *t)
 {
     unsigned int cpu = t->scheduled_on;
 
+    if ( t->is_percpu )
+    {
+        unsigned long flags;
+        struct list_head *list;
+
+        INIT_LIST_HEAD(&t->list);
+        BUG_ON( !t->is_softirq );
+        BUG_ON( cpu != smp_processor_id() ); /* Not implemented yet. */
+
+        local_irq_save(flags);
+
+        list = &__get_cpu_var(softirq_list);
+        list_add_tail(&t->list, list);
+        raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+
+        local_irq_restore(flags);
+        return;
+    }
     if ( t->is_softirq )
     {
         struct list_head *list = &per_cpu(softirq_tasklet_list, cpu);
@@ -56,16 +76,25 @@ void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu)
 {
     unsigned long flags;
 
-    spin_lock_irqsave(&tasklet_lock, flags);
+    if ( !tasklets_initialised || t->is_dead )
+        return;
 
-    if ( tasklets_initialised && !t->is_dead )
+    if ( t->is_percpu )
     {
-        t->scheduled_on = cpu;
-        if ( !t->is_running )
+        if ( !test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
         {
-            list_del(&t->list);
+            t->scheduled_on = cpu;
             tasklet_enqueue(t);
         }
+        return;
+    }
+    spin_lock_irqsave(&tasklet_lock, flags);
+
+    t->scheduled_on = cpu;
+    if ( !t->is_running )
+    {
+        list_del(&t->list);
+        tasklet_enqueue(t);
     }
 
     spin_unlock_irqrestore(&tasklet_lock, flags);
@@ -104,6 +133,66 @@ static void do_tasklet_work(unsigned int cpu, struct list_head *list)
     }
 }
 
+void do_tasklet_work_percpu(void)
+{
+    struct tasklet *t = NULL;
+    struct list_head *head;
+    bool_t poke = 0;
+
+    local_irq_disable();
+    head = &__get_cpu_var(softirq_list);
+
+    if ( !list_empty(head) )
+    {
+        t = list_entry(head->next, struct tasklet, list);
+
+        if ( head->next == head->prev ) /* One singular item. Re-init head. */
+            INIT_LIST_HEAD(&__get_cpu_var(softirq_list));
+        else
+        {
+            /* Multiple items, update head to skip 't'. */
+            struct list_head *list;
+
+            /* One item past 't'. */
+            list = head->next->next;
+
+            BUG_ON(list == NULL);
+
+            /* And update head to skip 't'. Note that t->list.prev still
+             * points to head, but we don't care as we only process one tasklet
+             * and once done the tasklet list is re-init one way or another.
+             */
+            head->next = list;
+            poke = 1;
+        }
+    }
+    local_irq_enable();
+
+    if ( !t )
+        return; /* Never saw it happend, but we might have a spurious case? */
+
+    if ( tasklet_trylock(t) )
+    {
+        if ( !test_and_clear_bit(TASKLET_STATE_SCHED, &t->state) )
+                BUG();
+        sync_local_execstate();
+        t->func(t->data);
+        tasklet_unlock(t);
+        if ( poke )
+            raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+        /* We could reinit the t->list but tasklet_enqueue does it for us. */
+        return;
+    }
+
+    local_irq_disable();
+
+    INIT_LIST_HEAD(&t->list);
+    list_add_tail(&t->list, &__get_cpu_var(softirq_list));
+    smp_wmb();
+    raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+    local_irq_enable();
+}
+
 /* VCPU context work */
 void do_tasklet(void)
 {
@@ -147,10 +236,29 @@ static void tasklet_softirq_action(void)
     spin_unlock_irq(&tasklet_lock);
 }
 
+/* Per CPU softirq context work. */
+static void tasklet_softirq_percpu_action(void)
+{
+    do_tasklet_work_percpu();
+}
+
 void tasklet_kill(struct tasklet *t)
 {
     unsigned long flags;
 
+    if ( t->is_percpu )
+    {
+        while ( test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
+        {
+            do {
+                process_pending_softirqs();
+            } while ( test_bit(TASKLET_STATE_SCHED, &t->state) );
+        }
+        tasklet_unlock_wait(t);
+        clear_bit(TASKLET_STATE_SCHED, &t->state);
+        t->is_dead = 1;
+        return;
+    }
     spin_lock_irqsave(&tasklet_lock, flags);
 
     if ( !list_empty(&t->list) )
@@ -208,6 +316,14 @@ void softirq_tasklet_init(
     t->is_softirq = 1;
 }
 
+void percpu_tasklet_init(
+    struct tasklet *t, void (*func)(unsigned long), unsigned long data)
+{
+    tasklet_init(t, func, data);
+    t->is_softirq = 1;
+    t->is_percpu = 1;
+}
+
 static int cpu_callback(
     struct notifier_block *nfb, unsigned long action, void *hcpu)
 {
@@ -218,11 +334,13 @@ static int cpu_callback(
     case CPU_UP_PREPARE:
         INIT_LIST_HEAD(&per_cpu(tasklet_list, cpu));
         INIT_LIST_HEAD(&per_cpu(softirq_tasklet_list, cpu));
+        INIT_LIST_HEAD(&per_cpu(softirq_list, cpu));
         break;
     case CPU_UP_CANCELED:
     case CPU_DEAD:
         migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_tasklet_list, cpu));
+        migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_list, cpu));
         break;
     default:
         break;
@@ -242,6 +360,7 @@ void __init tasklet_subsys_init(void)
     cpu_callback(&cpu_nfb, CPU_UP_PREPARE, hcpu);
     register_cpu_notifier(&cpu_nfb);
     open_softirq(TASKLET_SOFTIRQ, tasklet_softirq_action);
+    open_softirq(TASKLET_SOFTIRQ_PERCPU, tasklet_softirq_percpu_action);
     tasklets_initialised = 1;
 }
 
diff --git a/xen/include/xen/softirq.h b/xen/include/xen/softirq.h
index 0895a16..6dda1ba 100644
--- a/xen/include/xen/softirq.h
+++ b/xen/include/xen/softirq.h
@@ -7,6 +7,7 @@ enum {
     SCHEDULE_SOFTIRQ,
     NEW_TLBFLUSH_CLOCK_PERIOD_SOFTIRQ,
     RCU_SOFTIRQ,
+    TASKLET_SOFTIRQ_PERCPU,
     TASKLET_SOFTIRQ,
     NR_COMMON_SOFTIRQS
 };
diff --git a/xen/include/xen/tasklet.h b/xen/include/xen/tasklet.h
index 8c3de7e..9497c47 100644
--- a/xen/include/xen/tasklet.h
+++ b/xen/include/xen/tasklet.h
@@ -17,21 +17,24 @@
 struct tasklet
 {
     struct list_head list;
+    unsigned long state;
     int scheduled_on;
     bool_t is_softirq;
     bool_t is_running;
     bool_t is_dead;
+    bool_t is_percpu;
     void (*func)(unsigned long);
     unsigned long data;
 };
 
-#define _DECLARE_TASKLET(name, func, data, softirq)                     \
+#define _DECLARE_TASKLET(name, func, data, softirq, percpu)             \
     struct tasklet name = {                                             \
-        LIST_HEAD_INIT(name.list), -1, softirq, 0, 0, func, data }
+        LIST_HEAD_INIT(name.list), 0, -1, softirq, 0, 0, percpu,        \
+        func, data }
 #define DECLARE_TASKLET(name, func, data)               \
-    _DECLARE_TASKLET(name, func, data, 0)
+    _DECLARE_TASKLET(name, func, data, 0, 0)
 #define DECLARE_SOFTIRQ_TASKLET(name, func, data)       \
-    _DECLARE_TASKLET(name, func, data, 1)
+    _DECLARE_TASKLET(name, func, data, 1, 0)
 
 /* Indicates status of tasklet work on each CPU. */
 DECLARE_PER_CPU(unsigned long, tasklet_work_to_do);
@@ -40,6 +43,54 @@ DECLARE_PER_CPU(unsigned long, tasklet_work_to_do);
 #define TASKLET_enqueued   (1ul << _TASKLET_enqueued)
 #define TASKLET_scheduled  (1ul << _TASKLET_scheduled)
 
+/* These fancy bit manipulations (bit 0 and bit 1) along with using a lock
+ * operation allow us to have four stages in tasklet life-time.
+ *  a) 0x0: Completely empty (not scheduled nor running).
+ *  b) 0x1: Scheduled but not running. Used to guard in 'tasklet_schedule'
+ *     such that we will only schedule one. If it is scheduled and had never
+ *     run (hence never clearing STATE_SCHED bit), tasklet_kill will spin
+ *     forever on said tasklet. However 'tasklet_schedule' raises the
+ *     softirq associated with the per-cpu - so it will run, albeit there might
+ *     be a race (tasklet_kill spinning until the softirq handler runs).
+ *  c) 0x2: it is running (only on one CPU) and can be scheduled on any
+ *     CPU. The bit 0 - scheduled is cleared at this stage allowing
+ *     'tasklet_schedule' to succesfully schedule.
+ *  d) 0x3: scheduled and running - only possible if the running tasklet calls
+ *     tasklet_schedule (on same CPU) or the tasklet is scheduled from another
+ *     CPU while the tasklet is running on another CPU.
+ *
+ * The two bits play a vital role in assuring that the tasklet is scheduled
+ * once and runs only once. The steps are:
+ *
+ *  1) tasklet_schedule: STATE_SCHED bit set (0x1), added on the per cpu list.
+ *  2) tasklet_softirq_percpu_action picks one tasklet from the list. Schedules
+ *  itself later if there are more tasklets on it. Tries to set STATE_RUN bit
+ *  (0x3) - if it fails adds tasklet back to the per-cpu list. If it succeeds
+ *  clears the STATE_SCHED bit (0x2). Once tasklet completed, unsets STATE_RUN
+ *  (0x0 or 0x1 if tasklet called tasklet_schedule).
+ */
+enum {
+    TASKLET_STATE_SCHED, /* Bit 0 */
+    TASKLET_STATE_RUN
+};
+
+static inline int tasklet_trylock(struct tasklet *t)
+{
+    return !test_and_set_bit(TASKLET_STATE_RUN, &(t)->state);
+}
+
+static inline void tasklet_unlock(struct tasklet *t)
+{
+    barrier();
+    clear_bit(TASKLET_STATE_RUN, &(t)->state);
+}
+static inline void tasklet_unlock_wait(struct tasklet *t)
+{
+    while (test_bit(TASKLET_STATE_RUN, &(t)->state))
+    {
+        barrier();
+    }
+}
 void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu);
 void tasklet_schedule(struct tasklet *t);
 void do_tasklet(void);
@@ -48,6 +99,8 @@ void tasklet_init(
     struct tasklet *t, void (*func)(unsigned long), unsigned long data);
 void softirq_tasklet_init(
     struct tasklet *t, void (*func)(unsigned long), unsigned long data);
+void percpu_tasklet_init(
+    struct tasklet *t, void (*func)(unsigned long), unsigned long data);
 void tasklet_subsys_init(void);
 
 #endif /* __XEN_TASKLET_H__ */
-- 
2.4.11


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 2/5] tasklet: Add cross CPU feeding of per-cpu tasklets.

[Konrad Rzeszutek Wilk]

Since the per-cpu tasklets are lockfree and run only
within their own CPU context - we need a mechanism
for 'tasklet_schedule_on_cpu' from other CPUs to
insert tasklets in the destination per-cpu lists.

We use an IPI mechanism which function implements an
per-cpu 'feeding' list and a global lock.

When the IPI happens on the target CPU it will drain
its per-cpu feeding list and add them in the per-cpu
tasklet vector. With that in place we can now swap
over all of the softirq_tasklet users to use it.
That means we can also eliminate the percpu_tasklet
scaffolding.

Note that we don't do this tasklet schedule on other
CPUs that often - during microcode update and when
doing hypercall_continuation.

This could be squashed in "tasklet: Introduce per-cpu
tasklet for softirq." but the author thought it would
be an easier aid in understanding the code with these
parts split out.

Signed-off-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
---
RFC: First version
v1: Posted, folks asked if ticketlocks fixed it.
v2: Intel confirmed at XPDS 2016 that the problem is still present
    with large guests.

Cc: Jan Beulich <jbeulich@suse.com>
Cc: Andrew Cooper <andrew.cooper3@citrix.com>
Cc: "Lan, Tianyu" <tianyu.lan@intel.com>
Cc:  Kevin Tian <kevin.tian@intel.com>
Cc: Jun Nakajima <jun.nakajima@intel.com>
---
 xen/arch/x86/hvm/hvm.c    |  2 +-
 xen/common/tasklet.c      | 50 +++++++++++++++++++++++++++++++++++++++--------
 xen/include/xen/tasklet.h |  2 --
 3 files changed, 43 insertions(+), 11 deletions(-)

diff --git a/xen/arch/x86/hvm/hvm.c b/xen/arch/x86/hvm/hvm.c
index d933ddd..0180f26 100644
--- a/xen/arch/x86/hvm/hvm.c
+++ b/xen/arch/x86/hvm/hvm.c
@@ -1511,7 +1511,7 @@ int hvm_vcpu_initialise(struct vcpu *v)
     if ( (rc = hvm_funcs.vcpu_initialise(v)) != 0 ) /* teardown: hvm_funcs.vcpu_destroy */
         goto fail3;
 
-    percpu_tasklet_init(
+    softirq_tasklet_init(
         &v->arch.hvm_vcpu.assert_evtchn_irq_tasklet,
         (void(*)(unsigned long))hvm_assert_evtchn_irq,
         (unsigned long)v);
diff --git a/xen/common/tasklet.c b/xen/common/tasklet.c
index 319866f..d8f3cb3 100644
--- a/xen/common/tasklet.c
+++ b/xen/common/tasklet.c
@@ -30,8 +30,36 @@ static DEFINE_PER_CPU(struct list_head, softirq_tasklet_list);
 
 /* Protects all lists and tasklet structures. */
 static DEFINE_SPINLOCK(tasklet_lock);
+static DEFINE_SPINLOCK(feeder_lock);
 
 static DEFINE_PER_CPU(struct list_head, softirq_list);
+static DEFINE_PER_CPU(struct list_head, tasklet_feeder);
+
+static void percpu_tasklet_feed(void *arg)
+{
+    unsigned long flags;
+    struct tasklet *t;
+    struct list_head *dst_list;
+    struct list_head *list = &__get_cpu_var(tasklet_feeder);
+
+    spin_lock_irqsave(&feeder_lock, flags);
+
+    if ( list_empty(list) )
+        goto out;
+
+    while ( !list_empty(list) )
+    {
+        t = list_entry(list->next, struct tasklet, list);
+        BUG_ON(!t->is_percpu);
+        list_del(&t->list);
+
+        dst_list = &__get_cpu_var(softirq_list);
+        list_add_tail(&t->list, dst_list);
+    }
+    raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+out:
+    spin_unlock_irqrestore(&feeder_lock, flags);
+}
 
 static void tasklet_enqueue(struct tasklet *t)
 {
@@ -44,7 +72,18 @@ static void tasklet_enqueue(struct tasklet *t)
 
         INIT_LIST_HEAD(&t->list);
         BUG_ON( !t->is_softirq );
-        BUG_ON( cpu != smp_processor_id() ); /* Not implemented yet. */
+
+        if ( cpu != smp_processor_id() )
+        {
+            spin_lock_irqsave(&feeder_lock, flags);
+
+            list = &per_cpu(tasklet_feeder, cpu);
+            list_add_tail(&t->list, list);
+
+            spin_unlock_irqrestore(&feeder_lock, flags);
+            on_selected_cpus(cpumask_of(cpu), percpu_tasklet_feed, NULL, 1);
+            return;
+        }
 
         local_irq_save(flags);
 
@@ -314,13 +353,6 @@ void softirq_tasklet_init(
 {
     tasklet_init(t, func, data);
     t->is_softirq = 1;
-}
-
-void percpu_tasklet_init(
-    struct tasklet *t, void (*func)(unsigned long), unsigned long data)
-{
-    tasklet_init(t, func, data);
-    t->is_softirq = 1;
     t->is_percpu = 1;
 }
 
@@ -335,12 +367,14 @@ static int cpu_callback(
         INIT_LIST_HEAD(&per_cpu(tasklet_list, cpu));
         INIT_LIST_HEAD(&per_cpu(softirq_tasklet_list, cpu));
         INIT_LIST_HEAD(&per_cpu(softirq_list, cpu));
+        INIT_LIST_HEAD(&per_cpu(tasklet_feeder, cpu));
         break;
     case CPU_UP_CANCELED:
     case CPU_DEAD:
         migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_tasklet_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_list, cpu));
+        migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_feeder, cpu));
         break;
     default:
         break;
diff --git a/xen/include/xen/tasklet.h b/xen/include/xen/tasklet.h
index 9497c47..530a5e7 100644
--- a/xen/include/xen/tasklet.h
+++ b/xen/include/xen/tasklet.h
@@ -99,8 +99,6 @@ void tasklet_init(
     struct tasklet *t, void (*func)(unsigned long), unsigned long data);
 void softirq_tasklet_init(
     struct tasklet *t, void (*func)(unsigned long), unsigned long data);
-void percpu_tasklet_init(
-    struct tasklet *t, void (*func)(unsigned long), unsigned long data);
 void tasklet_subsys_init(void);
 
 #endif /* __XEN_TASKLET_H__ */
-- 
2.4.11


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 3/5] tasklet: Remove the old-softirq implementation.

[Konrad Rzeszutek Wilk]

With the new percpu tasklet (see "tasklet: Introduce per-cpu tasklet."
and "tasklet: Add cross CPU feeding of per-cpu-tasklets") we have
now in a place a working version of per-cpu softirq tasklets.

We can now remove the old implementation of the
softirq tasklet. We also remove the temporary scaffolding
of TASKLET_SOFTIRQ_PERCPU. Further removal of code will
be done in "tasklet: Remove the old scaffolding" once the
schedule tasklet code is in.

This could be squashed in "tasklet: Introduce per-cpu
tasklet for softirq." but the author thought it would
be an easier aid in understanding the code with these
parts split out.

Signed-off-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
---
RFC: First version
v1: Posted, folks asked if ticketlocks fixed it.
v2: Intel confirmed at XPDS 2016 that the problem is still present
    with large guests.

Cc: Jan Beulich <jbeulich@suse.com>
Cc: Andrew Cooper <andrew.cooper3@citrix.com>
Cc: "Lan, Tianyu" <tianyu.lan@intel.com>
Cc:  Kevin Tian <kevin.tian@intel.com>
Cc: Jun Nakajima <jun.nakajima@intel.com>
Cc: George Dunlap <George.Dunlap@eu.citrix.com>
Cc: Ian Jackson <ian.jackson@eu.citrix.com>
Cc: Jan Beulich <jbeulich@suse.com>
Cc: Stefano Stabellini <sstabellini@kernel.org>
Cc: Tim Deegan <tim@xen.org>
Cc: Wei Liu <wei.liu2@citrix.com>
---
 xen/common/tasklet.c      | 35 ++++++-----------------------------
 xen/include/xen/softirq.h |  1 -
 xen/include/xen/tasklet.h |  2 +-
 3 files changed, 7 insertions(+), 31 deletions(-)

diff --git a/xen/common/tasklet.c b/xen/common/tasklet.c
index d8f3cb3..ab23338 100644
--- a/xen/common/tasklet.c
+++ b/xen/common/tasklet.c
@@ -26,7 +26,6 @@ static bool_t tasklets_initialised;
 DEFINE_PER_CPU(unsigned long, tasklet_work_to_do);
 
 static DEFINE_PER_CPU(struct list_head, tasklet_list);
-static DEFINE_PER_CPU(struct list_head, softirq_tasklet_list);
 
 /* Protects all lists and tasklet structures. */
 static DEFINE_SPINLOCK(tasklet_lock);
@@ -56,7 +55,7 @@ static void percpu_tasklet_feed(void *arg)
         dst_list = &__get_cpu_var(softirq_list);
         list_add_tail(&t->list, dst_list);
     }
-    raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+    raise_softirq(TASKLET_SOFTIRQ);
 out:
     spin_unlock_irqrestore(&feeder_lock, flags);
 }
@@ -89,18 +88,14 @@ static void tasklet_enqueue(struct tasklet *t)
 
         list = &__get_cpu_var(softirq_list);
         list_add_tail(&t->list, list);
-        raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+        raise_softirq(TASKLET_SOFTIRQ);
 
         local_irq_restore(flags);
         return;
     }
     if ( t->is_softirq )
     {
-        struct list_head *list = &per_cpu(softirq_tasklet_list, cpu);
-        bool_t was_empty = list_empty(list);
-        list_add_tail(&t->list, list);
-        if ( was_empty )
-            cpu_raise_softirq(cpu, TASKLET_SOFTIRQ);
+        BUG();
     }
     else
     {
@@ -218,7 +213,7 @@ void do_tasklet_work_percpu(void)
         t->func(t->data);
         tasklet_unlock(t);
         if ( poke )
-            raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+            raise_softirq(TASKLET_SOFTIRQ);
         /* We could reinit the t->list but tasklet_enqueue does it for us. */
         return;
     }
@@ -228,7 +223,7 @@ void do_tasklet_work_percpu(void)
     INIT_LIST_HEAD(&t->list);
     list_add_tail(&t->list, &__get_cpu_var(softirq_list));
     smp_wmb();
-    raise_softirq(TASKLET_SOFTIRQ_PERCPU);
+    raise_softirq(TASKLET_SOFTIRQ);
     local_irq_enable();
 }
 
@@ -259,24 +254,9 @@ void do_tasklet(void)
     spin_unlock_irq(&tasklet_lock);
 }
 
-/* Softirq context work */
-static void tasklet_softirq_action(void)
-{
-    unsigned int cpu = smp_processor_id();
-    struct list_head *list = &per_cpu(softirq_tasklet_list, cpu);
-
-    spin_lock_irq(&tasklet_lock);
-
-    do_tasklet_work(cpu, list);
-
-    if ( !list_empty(list) && !cpu_is_offline(cpu) )
-        raise_softirq(TASKLET_SOFTIRQ);
-
-    spin_unlock_irq(&tasklet_lock);
-}
 
 /* Per CPU softirq context work. */
-static void tasklet_softirq_percpu_action(void)
+static void tasklet_softirq_action(void)
 {
     do_tasklet_work_percpu();
 }
@@ -365,14 +345,12 @@ static int cpu_callback(
     {
     case CPU_UP_PREPARE:
         INIT_LIST_HEAD(&per_cpu(tasklet_list, cpu));
-        INIT_LIST_HEAD(&per_cpu(softirq_tasklet_list, cpu));
         INIT_LIST_HEAD(&per_cpu(softirq_list, cpu));
         INIT_LIST_HEAD(&per_cpu(tasklet_feeder, cpu));
         break;
     case CPU_UP_CANCELED:
     case CPU_DEAD:
         migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_list, cpu));
-        migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_tasklet_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_feeder, cpu));
         break;
@@ -394,7 +372,6 @@ void __init tasklet_subsys_init(void)
     cpu_callback(&cpu_nfb, CPU_UP_PREPARE, hcpu);
     register_cpu_notifier(&cpu_nfb);
     open_softirq(TASKLET_SOFTIRQ, tasklet_softirq_action);
-    open_softirq(TASKLET_SOFTIRQ_PERCPU, tasklet_softirq_percpu_action);
     tasklets_initialised = 1;
 }
 
diff --git a/xen/include/xen/softirq.h b/xen/include/xen/softirq.h
index 6dda1ba..0895a16 100644
--- a/xen/include/xen/softirq.h
+++ b/xen/include/xen/softirq.h
@@ -7,7 +7,6 @@ enum {
     SCHEDULE_SOFTIRQ,
     NEW_TLBFLUSH_CLOCK_PERIOD_SOFTIRQ,
     RCU_SOFTIRQ,
-    TASKLET_SOFTIRQ_PERCPU,
     TASKLET_SOFTIRQ,
     NR_COMMON_SOFTIRQS
 };
diff --git a/xen/include/xen/tasklet.h b/xen/include/xen/tasklet.h
index 530a5e7..21efe7b 100644
--- a/xen/include/xen/tasklet.h
+++ b/xen/include/xen/tasklet.h
@@ -34,7 +34,7 @@ struct tasklet
 #define DECLARE_TASKLET(name, func, data)               \
     _DECLARE_TASKLET(name, func, data, 0, 0)
 #define DECLARE_SOFTIRQ_TASKLET(name, func, data)       \
-    _DECLARE_TASKLET(name, func, data, 1, 0)
+    _DECLARE_TASKLET(name, func, data, 1, 1)
 
 /* Indicates status of tasklet work on each CPU. */
 DECLARE_PER_CPU(unsigned long, tasklet_work_to_do);
-- 
2.4.11


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 4/5] tasklet: Introduce per-cpu tasklet for schedule tasklet.

[Konrad Rzeszutek Wilk]

With the "tasklet: Introduce per-cpu tasklet for softirq."
and "tasklet: Add cross CPU feeding of per-cpu tasklets."
we have all the neccessary pieces to swap over the
schedule tasklet. As such this patch has the same logic
as the softirq one except that is uses a different
name for its per-cpu list ("tasklet_vec").

It also removes the old implementation in one swoop.

Signed-off-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
---

RFC: First version
v1: Posted, folks asked if ticketlocks fixed it.
v2: Intel confirmed at XPDS 2016 that the problem is still present
    with large guests.

Cc: Jan Beulich <jbeulich@suse.com>
Cc: Andrew Cooper <andrew.cooper3@citrix.com>
Cc: "Lan, Tianyu" <tianyu.lan@intel.com>
Cc:  Kevin Tian <kevin.tian@intel.com>
Cc: Jun Nakajima <jun.nakajima@intel.com>
Cc: George Dunlap <George.Dunlap@eu.citrix.com>
Cc: Ian Jackson <ian.jackson@eu.citrix.com>
Cc: Stefano Stabellini <sstabellini@kernel.org>
Cc: Tim Deegan <tim@xen.org>
Cc: Wei Liu <wei.liu2@citrix.com>
---
 xen/common/tasklet.c | 193 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 112 insertions(+), 81 deletions(-)

diff --git a/xen/common/tasklet.c b/xen/common/tasklet.c
index ab23338..618e73b 100644
--- a/xen/common/tasklet.c
+++ b/xen/common/tasklet.c
@@ -25,12 +25,10 @@ static bool_t tasklets_initialised;
 
 DEFINE_PER_CPU(unsigned long, tasklet_work_to_do);
 
-static DEFINE_PER_CPU(struct list_head, tasklet_list);
-
-/* Protects all lists and tasklet structures. */
-static DEFINE_SPINLOCK(tasklet_lock);
+/* Protects the tasklet_feeder list. */
 static DEFINE_SPINLOCK(feeder_lock);
 
+static DEFINE_PER_CPU(struct list_head, tasklet_list);
 static DEFINE_PER_CPU(struct list_head, softirq_list);
 static DEFINE_PER_CPU(struct list_head, tasklet_feeder);
 
@@ -40,6 +38,8 @@ static void percpu_tasklet_feed(void *arg)
     struct tasklet *t;
     struct list_head *dst_list;
     struct list_head *list = &__get_cpu_var(tasklet_feeder);
+    unsigned long *work_to_do = &__get_cpu_var(tasklet_work_to_do);
+    bool_t poke = 0;
 
     spin_lock_irqsave(&feeder_lock, flags);
 
@@ -52,10 +52,23 @@ static void percpu_tasklet_feed(void *arg)
         BUG_ON(!t->is_percpu);
         list_del(&t->list);
 
-        dst_list = &__get_cpu_var(softirq_list);
+        if ( t->is_softirq )
+        {
+            dst_list = &__get_cpu_var(softirq_list);
+            poke = 1;
+        }
+        else
+            dst_list = &__get_cpu_var(tasklet_list);
+
         list_add_tail(&t->list, dst_list);
     }
-    raise_softirq(TASKLET_SOFTIRQ);
+    if ( poke )
+        raise_softirq(TASKLET_SOFTIRQ);
+    else
+    {
+        if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
+            raise_softirq(SCHEDULE_SOFTIRQ);
+    }
 out:
     spin_unlock_irqrestore(&feeder_lock, flags);
 }
@@ -70,7 +83,6 @@ static void tasklet_enqueue(struct tasklet *t)
         struct list_head *list;
 
         INIT_LIST_HEAD(&t->list);
-        BUG_ON( !t->is_softirq );
 
         if ( cpu != smp_processor_id() )
         {
@@ -83,15 +95,32 @@ static void tasklet_enqueue(struct tasklet *t)
             on_selected_cpus(cpumask_of(cpu), percpu_tasklet_feed, NULL, 1);
             return;
         }
+        if ( t->is_softirq )
+        {
 
-        local_irq_save(flags);
+            local_irq_save(flags);
 
-        list = &__get_cpu_var(softirq_list);
-        list_add_tail(&t->list, list);
-        raise_softirq(TASKLET_SOFTIRQ);
+            list = &__get_cpu_var(softirq_list);
+            list_add_tail(&t->list, list);
+            raise_softirq(TASKLET_SOFTIRQ);
 
-        local_irq_restore(flags);
-        return;
+            local_irq_restore(flags);
+            return;
+        }
+        else
+        {
+            unsigned long *work_to_do = &__get_cpu_var(tasklet_work_to_do);
+
+            local_irq_save(flags);
+
+            list = &__get_cpu_var(tasklet_list);
+            list_add_tail(&t->list, list);
+            if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
+                raise_softirq(SCHEDULE_SOFTIRQ);
+
+            local_irq_restore(flags);
+            return;
+        }
     }
     if ( t->is_softirq )
     {
@@ -99,17 +128,12 @@ static void tasklet_enqueue(struct tasklet *t)
     }
     else
     {
-        unsigned long *work_to_do = &per_cpu(tasklet_work_to_do, cpu);
-        list_add_tail(&t->list, &per_cpu(tasklet_list, cpu));
-        if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
-            cpu_raise_softirq(cpu, SCHEDULE_SOFTIRQ);
+        BUG();
     }
 }
 
 void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu)
 {
-    unsigned long flags;
-
     if ( !tasklets_initialised || t->is_dead )
         return;
 
@@ -122,16 +146,7 @@ void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu)
         }
         return;
     }
-    spin_lock_irqsave(&tasklet_lock, flags);
-
-    t->scheduled_on = cpu;
-    if ( !t->is_running )
-    {
-        list_del(&t->list);
-        tasklet_enqueue(t);
-    }
-
-    spin_unlock_irqrestore(&tasklet_lock, flags);
+    BUG();
 }
 
 void tasklet_schedule(struct tasklet *t)
@@ -139,32 +154,67 @@ void tasklet_schedule(struct tasklet *t)
     tasklet_schedule_on_cpu(t, smp_processor_id());
 }
 
-static void do_tasklet_work(unsigned int cpu, struct list_head *list)
+/* Return 0 if there is more work to be done. */
+static int do_tasklet_work(void)
 {
-    struct tasklet *t;
+    struct tasklet *t = NULL;
+    struct list_head *head;
+    int rc = 1; /* All done. */
 
-    if ( unlikely(list_empty(list) || cpu_is_offline(cpu)) )
-        return;
+    local_irq_disable();
+    head = &__get_cpu_var(tasklet_list);
 
-    t = list_entry(list->next, struct tasklet, list);
-    list_del_init(&t->list);
+    if ( !list_empty(head) )
+    {
+        t = list_entry(head->next, struct tasklet, list);
 
-    BUG_ON(t->is_dead || t->is_running || (t->scheduled_on != cpu));
-    t->scheduled_on = -1;
-    t->is_running = 1;
+        if ( head->next == head->prev ) /* One singular item. Re-init head. */
+            INIT_LIST_HEAD(&__get_cpu_var(tasklet_list));
+        else
+        {
+            /* Multiple items, update head to skip 't'. */
+            struct list_head *list;
 
-    spin_unlock_irq(&tasklet_lock);
-    sync_local_execstate();
-    t->func(t->data);
-    spin_lock_irq(&tasklet_lock);
+            /* One item past 't'. */
+            list = head->next->next;
 
-    t->is_running = 0;
+            BUG_ON(list == NULL);
+
+            /* And update head to skip 't'. Note that t->list.prev still
+             * points to head, but we don't care as we only process one tasklet
+             * and once done the tasklet list is re-init one way or another.
+             */
+            head->next = list;
+            rc = 0; /* More work to be done. */
+        }
+    }
+    local_irq_enable();
 
-    if ( t->scheduled_on >= 0 )
+    if ( !t )
+        return 1; /* Never saw it happend, but we might have a spurious case? */
+
+    if ( tasklet_trylock(t) )
     {
-        BUG_ON(t->is_dead || !list_empty(&t->list));
-        tasklet_enqueue(t);
+        if ( !test_and_clear_bit(TASKLET_STATE_SCHED, &t->state) )
+                BUG();
+        sync_local_execstate();
+        t->func(t->data);
+        tasklet_unlock(t);
+        if ( rc == 0 )
+            raise_softirq(TASKLET_SOFTIRQ);
+        /* We could reinit the t->list but tasklet_enqueue does it for us. */
+        return rc;
     }
+
+    local_irq_disable();
+
+    INIT_LIST_HEAD(&t->list);
+    list_add_tail(&t->list, &__get_cpu_var(tasklet_list));
+    smp_wmb();
+    raise_softirq(TASKLET_SOFTIRQ);
+    local_irq_enable();
+
+    return 0; /* More to do. */
 }
 
 void do_tasklet_work_percpu(void)
@@ -232,7 +282,6 @@ void do_tasklet(void)
 {
     unsigned int cpu = smp_processor_id();
     unsigned long *work_to_do = &per_cpu(tasklet_work_to_do, cpu);
-    struct list_head *list = &per_cpu(tasklet_list, cpu);
 
     /*
      * Work must be enqueued *and* scheduled. Otherwise there is no work to
@@ -241,17 +290,11 @@ void do_tasklet(void)
     if ( likely(*work_to_do != (TASKLET_enqueued|TASKLET_scheduled)) )
         return;
 
-    spin_lock_irq(&tasklet_lock);
-
-    do_tasklet_work(cpu, list);
-
-    if ( list_empty(list) )
+    if ( do_tasklet_work() )
     {
-        clear_bit(_TASKLET_enqueued, work_to_do);        
+        clear_bit(_TASKLET_enqueued, work_to_do);
         raise_softirq(SCHEDULE_SOFTIRQ);
     }
-
-    spin_unlock_irq(&tasklet_lock);
 }
 
 
@@ -263,8 +306,6 @@ static void tasklet_softirq_action(void)
 
 void tasklet_kill(struct tasklet *t)
 {
-    unsigned long flags;
-
     if ( t->is_percpu )
     {
         while ( test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
@@ -278,25 +319,6 @@ void tasklet_kill(struct tasklet *t)
         t->is_dead = 1;
         return;
     }
-    spin_lock_irqsave(&tasklet_lock, flags);
-
-    if ( !list_empty(&t->list) )
-    {
-        BUG_ON(t->is_dead || t->is_running || (t->scheduled_on < 0));
-        list_del_init(&t->list);
-    }
-
-    t->scheduled_on = -1;
-    t->is_dead = 1;
-
-    while ( t->is_running )
-    {
-        spin_unlock_irqrestore(&tasklet_lock, flags);
-        cpu_relax();
-        spin_lock_irqsave(&tasklet_lock, flags);
-    }
-
-    spin_unlock_irqrestore(&tasklet_lock, flags);
 }
 
 static void migrate_tasklets_from_cpu(unsigned int cpu, struct list_head *list)
@@ -304,7 +326,7 @@ static void migrate_tasklets_from_cpu(unsigned int cpu, struct list_head *list)
     unsigned long flags;
     struct tasklet *t;
 
-    spin_lock_irqsave(&tasklet_lock, flags);
+    spin_lock_irqsave(&feeder_lock, flags);
 
     while ( !list_empty(list) )
     {
@@ -315,7 +337,7 @@ static void migrate_tasklets_from_cpu(unsigned int cpu, struct list_head *list)
         tasklet_enqueue(t);
     }
 
-    spin_unlock_irqrestore(&tasklet_lock, flags);
+    spin_unlock_irqrestore(&feeder_lock, flags);
 }
 
 void tasklet_init(
@@ -326,6 +348,7 @@ void tasklet_init(
     t->scheduled_on = -1;
     t->func = func;
     t->data = data;
+    t->is_percpu = 1;
 }
 
 void softirq_tasklet_init(
@@ -333,26 +356,34 @@ void softirq_tasklet_init(
 {
     tasklet_init(t, func, data);
     t->is_softirq = 1;
-    t->is_percpu = 1;
 }
 
 static int cpu_callback(
     struct notifier_block *nfb, unsigned long action, void *hcpu)
 {
     unsigned int cpu = (unsigned long)hcpu;
+    unsigned long *work_to_do;
 
     switch ( action )
     {
     case CPU_UP_PREPARE:
-        INIT_LIST_HEAD(&per_cpu(tasklet_list, cpu));
         INIT_LIST_HEAD(&per_cpu(softirq_list, cpu));
         INIT_LIST_HEAD(&per_cpu(tasklet_feeder, cpu));
+        INIT_LIST_HEAD(&per_cpu(tasklet_list, cpu));
         break;
     case CPU_UP_CANCELED:
     case CPU_DEAD:
-        migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_list, cpu));
         migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_feeder, cpu));
+        migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_list, cpu));
+
+        work_to_do = &per_cpu(tasklet_work_to_do, cpu);
+        if ( test_bit(_TASKLET_enqueued, work_to_do) )
+        {
+            work_to_do = &__get_cpu_var(tasklet_work_to_do);
+            if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
+                raise_softirq(SCHEDULE_SOFTIRQ);
+        }
         break;
     default:
         break;
-- 
2.4.11


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH v2 5/5] tasklet: Remove the scaffolding.

[Konrad Rzeszutek Wilk]

To catch any bisection issues, we had been replacing parts of
the tasklet code one functionality on top of each other. Now
that all of it is per-cpu and working we can remove the
old scaffolding and collapse functions.

We also remove the 'is_percpu' flag that is not needed
anymore. Most of this is code deletion and code
motion. No new functionality is added.

Signed-off-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
---
RFC: First version
v1: Posted, folks asked if ticketlocks fixed it.
v2: Intel confirmed at XPDS 2016 that the problem is still present
    with large guests.

Cc: Jan Beulich <jbeulich@suse.com>
Cc: Andrew Cooper <andrew.cooper3@citrix.com>
Cc: "Lan, Tianyu" <tianyu.lan@intel.com>
Cc:  Kevin Tian <kevin.tian@intel.com>
Cc: Jun Nakajima <jun.nakajima@intel.com>
Cc: George Dunlap <George.Dunlap@eu.citrix.com>
Cc: Ian Jackson <ian.jackson@eu.citrix.com>
Cc: Stefano Stabellini <sstabellini@kernel.org>
Cc: Tim Deegan <tim@xen.org>
Cc: Wei Liu <wei.liu2@citrix.com>
---
 xen/common/tasklet.c      | 110 ++++++++++++++++++----------------------------
 xen/include/xen/tasklet.h |   9 ++--
 2 files changed, 46 insertions(+), 73 deletions(-)

diff --git a/xen/common/tasklet.c b/xen/common/tasklet.c
index 618e73b..192fa79 100644
--- a/xen/common/tasklet.c
+++ b/xen/common/tasklet.c
@@ -49,7 +49,6 @@ static void percpu_tasklet_feed(void *arg)
     while ( !list_empty(list) )
     {
         t = list_entry(list->next, struct tasklet, list);
-        BUG_ON(!t->is_percpu);
         list_del(&t->list);
 
         if ( t->is_softirq )
@@ -76,59 +75,44 @@ out:
 static void tasklet_enqueue(struct tasklet *t)
 {
     unsigned int cpu = t->scheduled_on;
+    unsigned long flags;
+    struct list_head *list;
 
-    if ( t->is_percpu )
-    {
-        unsigned long flags;
-        struct list_head *list;
-
-        INIT_LIST_HEAD(&t->list);
-
-        if ( cpu != smp_processor_id() )
-        {
-            spin_lock_irqsave(&feeder_lock, flags);
-
-            list = &per_cpu(tasklet_feeder, cpu);
-            list_add_tail(&t->list, list);
-
-            spin_unlock_irqrestore(&feeder_lock, flags);
-            on_selected_cpus(cpumask_of(cpu), percpu_tasklet_feed, NULL, 1);
-            return;
-        }
-        if ( t->is_softirq )
-        {
-
-            local_irq_save(flags);
-
-            list = &__get_cpu_var(softirq_list);
-            list_add_tail(&t->list, list);
-            raise_softirq(TASKLET_SOFTIRQ);
+    INIT_LIST_HEAD(&t->list);
 
-            local_irq_restore(flags);
-            return;
-        }
-        else
-        {
-            unsigned long *work_to_do = &__get_cpu_var(tasklet_work_to_do);
+    if ( cpu != smp_processor_id() )
+    {
+        spin_lock_irqsave(&feeder_lock, flags);
 
-            local_irq_save(flags);
+        list = &per_cpu(tasklet_feeder, cpu);
+        list_add_tail(&t->list, list);
 
-            list = &__get_cpu_var(tasklet_list);
-            list_add_tail(&t->list, list);
-            if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
-                raise_softirq(SCHEDULE_SOFTIRQ);
+        spin_unlock_irqrestore(&feeder_lock, flags);
+        on_selected_cpus(cpumask_of(cpu), percpu_tasklet_feed, NULL, 1);
+        return;
+     }
+     if ( t->is_softirq )
+     {
+         local_irq_save(flags);
+
+         list = &__get_cpu_var(softirq_list);
+         list_add_tail(&t->list, list);
+         raise_softirq(TASKLET_SOFTIRQ);
+
+         local_irq_restore(flags);
+     }
+     else
+     {
+          unsigned long *work_to_do = &__get_cpu_var(tasklet_work_to_do);
+
+          local_irq_save(flags);
+
+          list = &__get_cpu_var(tasklet_list);
+          list_add_tail(&t->list, list);
+          if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
+            raise_softirq(SCHEDULE_SOFTIRQ);
 
-            local_irq_restore(flags);
-            return;
-        }
-    }
-    if ( t->is_softirq )
-    {
-        BUG();
-    }
-    else
-    {
-        BUG();
+          local_irq_restore(flags);
     }
 }
 
@@ -137,16 +121,11 @@ void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu)
     if ( !tasklets_initialised || t->is_dead )
         return;
 
-    if ( t->is_percpu )
+    if ( !test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
     {
-        if ( !test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
-        {
-            t->scheduled_on = cpu;
-            tasklet_enqueue(t);
-        }
-        return;
+        t->scheduled_on = cpu;
+        tasklet_enqueue(t);
     }
-    BUG();
 }
 
 void tasklet_schedule(struct tasklet *t)
@@ -306,19 +285,15 @@ static void tasklet_softirq_action(void)
 
 void tasklet_kill(struct tasklet *t)
 {
-    if ( t->is_percpu )
+    while ( test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
     {
-        while ( test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
-        {
-            do {
+        do {
                 process_pending_softirqs();
-            } while ( test_bit(TASKLET_STATE_SCHED, &t->state) );
-        }
-        tasklet_unlock_wait(t);
-        clear_bit(TASKLET_STATE_SCHED, &t->state);
-        t->is_dead = 1;
-        return;
+        } while ( test_bit(TASKLET_STATE_SCHED, &t->state) );
     }
+    tasklet_unlock_wait(t);
+    clear_bit(TASKLET_STATE_SCHED, &t->state);
+    t->is_dead = 1;
 }
 
 static void migrate_tasklets_from_cpu(unsigned int cpu, struct list_head *list)
@@ -348,7 +323,6 @@ void tasklet_init(
     t->scheduled_on = -1;
     t->func = func;
     t->data = data;
-    t->is_percpu = 1;
 }
 
 void softirq_tasklet_init(
diff --git a/xen/include/xen/tasklet.h b/xen/include/xen/tasklet.h
index 21efe7b..b7a6a81 100644
--- a/xen/include/xen/tasklet.h
+++ b/xen/include/xen/tasklet.h
@@ -22,19 +22,18 @@ struct tasklet
     bool_t is_softirq;
     bool_t is_running;
     bool_t is_dead;
-    bool_t is_percpu;
     void (*func)(unsigned long);
     unsigned long data;
 };
 
-#define _DECLARE_TASKLET(name, func, data, softirq, percpu)             \
+#define _DECLARE_TASKLET(name, func, data, softirq)                     \
     struct tasklet name = {                                             \
-        LIST_HEAD_INIT(name.list), 0, -1, softirq, 0, 0, percpu,        \
+        LIST_HEAD_INIT(name.list), 0, -1, softirq, 0, 0,                \
         func, data }
 #define DECLARE_TASKLET(name, func, data)               \
-    _DECLARE_TASKLET(name, func, data, 0, 0)
+    _DECLARE_TASKLET(name, func, data, 0)
 #define DECLARE_SOFTIRQ_TASKLET(name, func, data)       \
-    _DECLARE_TASKLET(name, func, data, 1, 1)
+    _DECLARE_TASKLET(name, func, data, 1)
 
 /* Indicates status of tasklet work on each CPU. */
 DECLARE_PER_CPU(unsigned long, tasklet_work_to_do);
-- 
2.4.11


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 1/5] tasklet: Introduce per-cpu tasklet for softirq.

[Wei Liu]

On Thu, Aug 25, 2016 at 03:23:57PM -0400, Konrad Rzeszutek Wilk wrote:
[...]
> +static inline void tasklet_unlock_wait(struct tasklet *t)
> +{
> +    while (test_bit(TASKLET_STATE_RUN, &(t)->state))
> +    {
> +        barrier();

Need cpu_relax() here?

> +    }

Wei.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 1/5] tasklet: Introduce per-cpu tasklet for softirq.

[Jan Beulich]

>>> On 25.08.16 at 21:23, <konrad.wilk@oracle.com> wrote:
> This implements a lockless per-cpu tasklet mechanism.

How does this correlate with the title? IOW, how is this new form of
tasklets "for" softirq? Perhaps part of the sentence above would be
a better fit for the title?

> The existing tasklet mechanism has a single global
> spinlock that is taken every-time the global list
> is touched. And we use this lock quite a lot - when
> we call do_tasklet_work which is called via an softirq
> and from the idle loop. We take the lock on any
> operation on the tasklet_list.
> 
> The problem we are facing is that there are quite a lot of
> tasklets scheduled. The most common one that is invoked is
> the one injecting the VIRQ_TIMER in the guest. Guests
> are not insane and don't set the one-shot or periodic
> clocks to be in sub 1ms intervals (causing said tasklet
> to be scheduled for such small intervalls).

I don't follow how this "guests are not insane" relates to the issue
described here. Plus - what if there was an insane guest?

> This is especially an problem with guests that have a
> large amount of VCPUs.
> 
> With this patch the problem disappears.
> 
> As such this patch introduces the code to setup
> softirq per-cpu tasklets and only modifies the PCI
> passthrough cases instead of doing it wholesale. This
> is done because:
>  - We want to easily bisect it if things break.
>  - We modify the code one section at a time to
>    make it easier to review this core code.

To me this looks to be contrary to the very first change I see:

> --- a/xen/arch/x86/hvm/hvm.c
> +++ b/xen/arch/x86/hvm/hvm.c
> @@ -1511,7 +1511,7 @@ int hvm_vcpu_initialise(struct vcpu *v)
>      if ( (rc = hvm_funcs.vcpu_initialise(v)) != 0 ) /* teardown: hvm_funcs.vcpu_destroy */
>          goto fail3;
>  
> -    softirq_tasklet_init(
> +    percpu_tasklet_init(
>          &v->arch.hvm_vcpu.assert_evtchn_irq_tasklet,
>          (void(*)(unsigned long))hvm_assert_evtchn_irq,
>          (unsigned long)v);

Isn't this unrelated to pass-through?

> --- a/xen/common/tasklet.c
> +++ b/xen/common/tasklet.c
> @@ -31,10 +31,30 @@ static DEFINE_PER_CPU(struct list_head, 
> softirq_tasklet_list);
>  /* Protects all lists and tasklet structures. */
>  static DEFINE_SPINLOCK(tasklet_lock);
>  
> +static DEFINE_PER_CPU(struct list_head, softirq_list);

Please put this next to the other two. Which then makes more
obvious that some naming changes might be helpful: We already
have softirq_tasklet_list. Maybe percpu_list or - since this already
is a per-CPU variable - local_list? Otherwise at least a comment
should be added to clarify the different purposes of the three lists.

>  static void tasklet_enqueue(struct tasklet *t)
>  {
>      unsigned int cpu = t->scheduled_on;
>  
> +    if ( t->is_percpu )
> +    {
> +        unsigned long flags;
> +        struct list_head *list;
> +
> +        INIT_LIST_HEAD(&t->list);

Why? You list_add_tail() below unconditionally.

> +        BUG_ON( !t->is_softirq );

If this is a requirement, wouldn't the two boolean flags better be
folded into a tristate enum, with the if() sequence here converted
to a switch()?

> +        BUG_ON( cpu != smp_processor_id() ); /* Not implemented yet. */
> +
> +        local_irq_save(flags);

Considering that the pre-existing two cases in this function don't do
any locking themselves, is the asymmetry to do the "locking" here a
good idea?

> +        list = &__get_cpu_var(softirq_list);
> +        list_add_tail(&t->list, list);
> +        raise_softirq(TASKLET_SOFTIRQ_PERCPU);
> +
> +        local_irq_restore(flags);
> +        return;
> +    }
>      if ( t->is_softirq )

Instead of return, please use "else if" here (unless converting to
switch() anyway).

> @@ -56,16 +76,25 @@ void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu)
>  {
>      unsigned long flags;
>  
> -    spin_lock_irqsave(&tasklet_lock, flags);
> +    if ( !tasklets_initialised || t->is_dead )
> +        return;
>  
> -    if ( tasklets_initialised && !t->is_dead )
> +    if ( t->is_percpu )
>      {
> -        t->scheduled_on = cpu;
> -        if ( !t->is_running )
> +        if ( !test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
>          {
> -            list_del(&t->list);
> +            t->scheduled_on = cpu;
>              tasklet_enqueue(t);
>          }
> +        return;
> +    }
> +    spin_lock_irqsave(&tasklet_lock, flags);

Blank line above this one please.

> @@ -104,6 +133,66 @@ static void do_tasklet_work(unsigned int cpu, struct list_head *list)
>      }
>  }
>  
> +void do_tasklet_work_percpu(void)

static

> +{
> +    struct tasklet *t = NULL;
> +    struct list_head *head;
> +    bool_t poke = 0;

bool / false

> +    local_irq_disable();
> +    head = &__get_cpu_var(softirq_list);
> +
> +    if ( !list_empty(head) )
> +    {
> +        t = list_entry(head->next, struct tasklet, list);
> +
> +        if ( head->next == head->prev ) /* One singular item. Re-init head. */

Do we have no list_*() function for this?

> +            INIT_LIST_HEAD(&__get_cpu_var(softirq_list));
> +        else
> +        {
> +            /* Multiple items, update head to skip 't'. */
> +            struct list_head *list;
> +
> +            /* One item past 't'. */
> +            list = head->next->next;
> +
> +            BUG_ON(list == NULL);
> +
> +            /* And update head to skip 't'. Note that t->list.prev still
> +             * points to head, but we don't care as we only process one tasklet
> +             * and once done the tasklet list is re-init one way or another.
> +             */
> +            head->next = list;

Why can't you use list_del() for all of the above, including the
INIT_LIST_HEAD() in the if branch?

> +            poke = 1;
> +        }
> +    }
> +    local_irq_enable();
> +
> +    if ( !t )
> +        return; /* Never saw it happend, but we might have a spurious case? */
> +
> +    if ( tasklet_trylock(t) )
> +    {
> +        if ( !test_and_clear_bit(TASKLET_STATE_SCHED, &t->state) )
> +                BUG();

Indentation.

> +        sync_local_execstate();
> +        t->func(t->data);
> +        tasklet_unlock(t);
> +        if ( poke )
> +            raise_softirq(TASKLET_SOFTIRQ_PERCPU);
> +        /* We could reinit the t->list but tasklet_enqueue does it for us. */

I can't see why re-initing would be needed here or there, nor why
do_tasklet_work() does so.

> +        return;
> +    }
> +
> +    local_irq_disable();
> +
> +    INIT_LIST_HEAD(&t->list);
> +    list_add_tail(&t->list, &__get_cpu_var(softirq_list));
> +    smp_wmb();
> +    raise_softirq(TASKLET_SOFTIRQ_PERCPU);
> +    local_irq_enable();

tasklet_enqueue()? The only difference appears to be the barrier
you have here but not there (and I don't think you need it).

> @@ -147,10 +236,29 @@ static void tasklet_softirq_action(void)
>      spin_unlock_irq(&tasklet_lock);
>  }
>  
> +/* Per CPU softirq context work. */
> +static void tasklet_softirq_percpu_action(void)
> +{
> +    do_tasklet_work_percpu();
> +}

Considering this is the only caller of the function - why do you need
two functions here?

>  void tasklet_kill(struct tasklet *t)
>  {
>      unsigned long flags;
>  
> +    if ( t->is_percpu )
> +    {
> +        while ( test_and_set_bit(TASKLET_STATE_SCHED, &t->state) )
> +        {
> +            do {
> +                process_pending_softirqs();
> +            } while ( test_bit(TASKLET_STATE_SCHED, &t->state) );
> +        }
> +        tasklet_unlock_wait(t);
> +        clear_bit(TASKLET_STATE_SCHED, &t->state);
> +        t->is_dead = 1;

true

> --- a/xen/include/xen/tasklet.h
> +++ b/xen/include/xen/tasklet.h
> @@ -17,21 +17,24 @@
>  struct tasklet
>  {
>      struct list_head list;
> +    unsigned long state;
>      int scheduled_on;
>      bool_t is_softirq;
>      bool_t is_running;
>      bool_t is_dead;
> +    bool_t is_percpu;
>      void (*func)(unsigned long);
>      unsigned long data;
>  };
>  
> -#define _DECLARE_TASKLET(name, func, data, softirq)                     \
> +#define _DECLARE_TASKLET(name, func, data, softirq, percpu)             \
>      struct tasklet name = {                                             \
> -        LIST_HEAD_INIT(name.list), -1, softirq, 0, 0, func, data }
> +        LIST_HEAD_INIT(name.list), 0, -1, softirq, 0, 0, percpu,        \
> +        func, data }

May I ask that you switch to designated member initializers if you
need to touch this already anyway?

> @@ -40,6 +43,54 @@ DECLARE_PER_CPU(unsigned long, tasklet_work_to_do);
>  #define TASKLET_enqueued   (1ul << _TASKLET_enqueued)
>  #define TASKLET_scheduled  (1ul << _TASKLET_scheduled)
>  
> +/* These fancy bit manipulations (bit 0 and bit 1) along with using a lock

Please avoid referring to "locked" operations outside of x86 code.
ITYM "atomic".

> + * operation allow us to have four stages in tasklet life-time.
> + *  a) 0x0: Completely empty (not scheduled nor running).
> + *  b) 0x1: Scheduled but not running. Used to guard in 'tasklet_schedule'
> + *     such that we will only schedule one. If it is scheduled and had never
> + *     run (hence never clearing STATE_SCHED bit), tasklet_kill will spin
> + *     forever on said tasklet. However 'tasklet_schedule' raises the
> + *     softirq associated with the per-cpu - so it will run, albeit there might
> + *     be a race (tasklet_kill spinning until the softirq handler runs).

And is there a guarantee the handler can actually run while
tasklet_kill() spins?

> + *  c) 0x2: it is running (only on one CPU) and can be scheduled on any
> + *     CPU. The bit 0 - scheduled is cleared at this stage allowing
> + *     'tasklet_schedule' to succesfully schedule.
> + *  d) 0x3: scheduled and running - only possible if the running tasklet calls
> + *     tasklet_schedule (on same CPU) or the tasklet is scheduled from another
> + *     CPU while the tasklet is running on another CPU.
> + *
> + * The two bits play a vital role in assuring that the tasklet is scheduled
> + * once and runs only once. The steps are:
> + *
> + *  1) tasklet_schedule: STATE_SCHED bit set (0x1), added on the per cpu list.
> + *  2) tasklet_softirq_percpu_action picks one tasklet from the list. Schedules
> + *  itself later if there are more tasklets on it. Tries to set STATE_RUN bit
> + *  (0x3) - if it fails adds tasklet back to the per-cpu list. If it succeeds
> + *  clears the STATE_SCHED bit (0x2).

Why are these two steps? Can't you transition 1 -> 2 in one go
(using cmpxchg())?

> Once tasklet completed, unsets STATE_RUN
> + *  (0x0 or 0x1 if tasklet called tasklet_schedule).
> + */
> +enum {
> +    TASKLET_STATE_SCHED, /* Bit 0 */
> +    TASKLET_STATE_RUN
> +};
> +
> +static inline int tasklet_trylock(struct tasklet *t)

bool and const

> +{
> +    return !test_and_set_bit(TASKLET_STATE_RUN, &(t)->state);
> +}
> +
> +static inline void tasklet_unlock(struct tasklet *t)
> +{
> +    barrier();
> +    clear_bit(TASKLET_STATE_RUN, &(t)->state);
> +}
> +static inline void tasklet_unlock_wait(struct tasklet *t)

const

> +{
> +    while (test_bit(TASKLET_STATE_RUN, &(t)->state))

Missing blanks.

> +    {
> +        barrier();
> +    }

Unnecessary braces.

Jan

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 2/5] tasklet: Add cross CPU feeding of per-cpu tasklets.

[Jan Beulich]

>>> On 25.08.16 at 21:23, <konrad.wilk@oracle.com> wrote:
> +static void percpu_tasklet_feed(void *arg)
> +{
> +    unsigned long flags;
> +    struct tasklet *t;
> +    struct list_head *dst_list;
> +    struct list_head *list = &__get_cpu_var(tasklet_feeder);
> +
> +    spin_lock_irqsave(&feeder_lock, flags);
> +
> +    if ( list_empty(list) )
> +        goto out;

Instead of this, how about e.g. initializing t to NULL above and ...

> +    while ( !list_empty(list) )
> +    {
> +        t = list_entry(list->next, struct tasklet, list);

[Intermediate note: list_first_entry(); I guess there also was at
least one such case in patch 1. Or perhaps even better
list_first_entry_or_null() and then this moved into the loop
condition.]

> +        BUG_ON(!t->is_percpu);
> +        list_del(&t->list);
> +
> +        dst_list = &__get_cpu_var(softirq_list);
> +        list_add_tail(&t->list, dst_list);
> +    }
> +    raise_softirq(TASKLET_SOFTIRQ_PERCPU);

... making this conditional upon t not being NULL? That would at
once ...

> +out:

... eliminate this label, which otherwise I would have to comment on.

Jan

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH v2 3/5] tasklet: Remove the old-softirq implementation.

[Jan Beulich]

>>> On 25.08.16 at 21:23, <konrad.wilk@oracle.com> wrote:
> With the new percpu tasklet (see "tasklet: Introduce per-cpu tasklet."
> and "tasklet: Add cross CPU feeding of per-cpu-tasklets") we have
> now in a place a working version of per-cpu softirq tasklets.
> 
> We can now remove the old implementation of the
> softirq tasklet. We also remove the temporary scaffolding
> of TASKLET_SOFTIRQ_PERCPU. Further removal of code will
> be done in "tasklet: Remove the old scaffolding" once the
> schedule tasklet code is in.
> 
> This could be squashed in "tasklet: Introduce per-cpu
> tasklet for softirq." but the author thought it would
> be an easier aid in understanding the code with these
> parts split out.

When you said something in the previous patch I tended to agree.
However, seeing this I'm not sure the split up isn't ending up worse
to look at than if you had switched over in one go, retaining e.g. ...

> --- a/xen/common/tasklet.c
> +++ b/xen/common/tasklet.c
> @@ -26,7 +26,6 @@ static bool_t tasklets_initialised;
>  DEFINE_PER_CPU(unsigned long, tasklet_work_to_do);
>  
>  static DEFINE_PER_CPU(struct list_head, tasklet_list);
> -static DEFINE_PER_CPU(struct list_head, softirq_tasklet_list);

... this original list name (I now can guess why in patch 1 you named
the new list the way you did, but for the end result I think this old
name is to be preferred, as what you add is not a list of softirqs).

> @@ -89,18 +88,14 @@ static void tasklet_enqueue(struct tasklet *t)
>  
>          list = &__get_cpu_var(softirq_list);
>          list_add_tail(&t->list, list);
> -        raise_softirq(TASKLET_SOFTIRQ_PERCPU);
> +        raise_softirq(TASKLET_SOFTIRQ);
>  
>          local_irq_restore(flags);
>          return;
>      }
>      if ( t->is_softirq )
>      {
> -        struct list_head *list = &per_cpu(softirq_tasklet_list, cpu);
> -        bool_t was_empty = list_empty(list);
> -        list_add_tail(&t->list, list);
> -        if ( was_empty )
> -            cpu_raise_softirq(cpu, TASKLET_SOFTIRQ);
> +        BUG();

I don't think you need the is_softirq flag anymore at this point,
which would eliminate this if() altogether.

Jan

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel