[Qemu-devel] [PATCH 0/3] convert CPU list to RCU

[Qemu-devel] [PATCH 0/3] convert CPU list to RCU

[Emilio G. Cota]

We iterate over the CPU list quite frequently (e.g. with CPU_FOREACH),
but we rarely acquire the cpu_list_lock to do so. This is incorrect,
since the CPU list can be updated (new CPUs added to it) pretty
much anytime, particularly in user-mode.

Instead of grabbing cpu_list_lock everywhere, convert the list to RCU
to that iterations can be safe and wait-free.

Thanks,

		Emilio

[Qemu-devel] [PATCH 1/3] qom: use cpu->in_cpu_list instead of QTAILQ_IN_USE

[Emilio G. Cota]

This paves the way for implementing the CPU list with an RCU QLIST.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 cpus-common.c     | 3 ++-
 include/qom/cpu.h | 2 ++
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/cpus-common.c b/cpus-common.c
index 59f751ecf9..6eaedae60b 100644
--- a/cpus-common.c
+++ b/cpus-common.c
@@ -85,6 +85,7 @@ void cpu_list_add(CPUState *cpu)
         assert(!cpu_index_auto_assigned);
     }
     QTAILQ_INSERT_TAIL(&cpus, cpu, node);
+    cpu->in_cpu_list = true;
     qemu_mutex_unlock(&qemu_cpu_list_lock);
 
     finish_safe_work(cpu);
@@ -93,7 +94,7 @@ void cpu_list_add(CPUState *cpu)
 void cpu_list_remove(CPUState *cpu)
 {
     qemu_mutex_lock(&qemu_cpu_list_lock);
-    if (!QTAILQ_IN_USE(cpu, node)) {
+    if (!cpu->in_cpu_list) {
         /* there is nothing to undo since cpu_exec_init() hasn't been called */
         qemu_mutex_unlock(&qemu_cpu_list_lock);
         return;
diff --git a/include/qom/cpu.h b/include/qom/cpu.h
index bd796579ee..aa555e27a7 100644
--- a/include/qom/cpu.h
+++ b/include/qom/cpu.h
@@ -411,6 +411,8 @@ struct CPUState {
 
     bool ignore_memory_transaction_failures;
 
+    bool in_cpu_list; /* protected by qemu_cpu_list_lock */
+
     /* Note that this is accessed at the start of every TB via a negative
        offset from AREG0.  Leave this field at the end so as to make the
        (absolute value) offset as small as possible.  This reduces code
-- 
2.17.1

Re: [Qemu-devel] [PATCH 1/3] qom: use cpu->in_cpu_list instead of QTAILQ_IN_USE

[Paolo Bonzini]

On 13/08/2018 18:38, Emilio G. Cota wrote:
> This paves the way for implementing the CPU list with an RCU QLIST.
> 
> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  cpus-common.c     | 3 ++-
>  include/qom/cpu.h | 2 ++
>  2 files changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/cpus-common.c b/cpus-common.c
> index 59f751ecf9..6eaedae60b 100644
> --- a/cpus-common.c
> +++ b/cpus-common.c
> @@ -85,6 +85,7 @@ void cpu_list_add(CPUState *cpu)
>          assert(!cpu_index_auto_assigned);
>      }
>      QTAILQ_INSERT_TAIL(&cpus, cpu, node);
> +    cpu->in_cpu_list = true;
>      qemu_mutex_unlock(&qemu_cpu_list_lock);
>  
>      finish_safe_work(cpu);
> @@ -93,7 +94,7 @@ void cpu_list_add(CPUState *cpu)
>  void cpu_list_remove(CPUState *cpu)
>  {
>      qemu_mutex_lock(&qemu_cpu_list_lock);
> -    if (!QTAILQ_IN_USE(cpu, node)) {
> +    if (!cpu->in_cpu_list) {
>          /* there is nothing to undo since cpu_exec_init() hasn't been called */
>          qemu_mutex_unlock(&qemu_cpu_list_lock);
>          return;
> diff --git a/include/qom/cpu.h b/include/qom/cpu.h
> index bd796579ee..aa555e27a7 100644
> --- a/include/qom/cpu.h
> +++ b/include/qom/cpu.h
> @@ -411,6 +411,8 @@ struct CPUState {
>  
>      bool ignore_memory_transaction_failures;
>  
> +    bool in_cpu_list; /* protected by qemu_cpu_list_lock */
> +
>      /* Note that this is accessed at the start of every TB via a negative
>         offset from AREG0.  Leave this field at the end so as to make the
>         (absolute value) offset as small as possible.  This reduces code
> 

Reviewwed-by: Paolo Bonzini <pbonzini@redhat.com>

[Qemu-devel] [PATCH 2/3] spapr: do not use CPU_FOREACH_REVERSE

[Emilio G. Cota]

This paves the way for implementing the CPU list with an RCU QLIST,
which cannot be traversed in reverse order.

Note that this is the only caller of CPU_FOREACH_REVERSE.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 hw/ppc/spapr.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/hw/ppc/spapr.c b/hw/ppc/spapr.c
index 421b2dd09b..2ef5be2790 100644
--- a/hw/ppc/spapr.c
+++ b/hw/ppc/spapr.c
@@ -622,9 +622,12 @@ static void spapr_populate_cpu_dt(CPUState *cs, void *fdt, int offset,
 
 static void spapr_populate_cpus_dt_node(void *fdt, sPAPRMachineState *spapr)
 {
+    CPUState **rev;
     CPUState *cs;
+    int n_cpus;
     int cpus_offset;
     char *nodename;
+    int i;
 
     cpus_offset = fdt_add_subnode(fdt, 0, "cpus");
     _FDT(cpus_offset);
@@ -635,8 +638,19 @@ static void spapr_populate_cpus_dt_node(void *fdt, sPAPRMachineState *spapr)
      * We walk the CPUs in reverse order to ensure that CPU DT nodes
      * created by fdt_add_subnode() end up in the right order in FDT
      * for the guest kernel the enumerate the CPUs correctly.
+     *
+     * The CPU list cannot be traversed in reverse order, so we need
+     * to do extra work.
      */
-    CPU_FOREACH_REVERSE(cs) {
+    n_cpus = 0;
+    rev = NULL;
+    CPU_FOREACH(cs) {
+        rev = g_renew(CPUState *, rev, n_cpus + 1);
+        rev[n_cpus++] = cs;
+    }
+
+    for (i = n_cpus - 1; i >= 0; i--) {
+        CPUState *cs = rev[i];
         PowerPCCPU *cpu = POWERPC_CPU(cs);
         int index = spapr_get_vcpu_id(cpu);
         DeviceClass *dc = DEVICE_GET_CLASS(cs);
-- 
2.17.1

Re: [Qemu-devel] [PATCH 2/3] spapr: do not use CPU_FOREACH_REVERSE

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 2066 bytes --]

On Mon, Aug 13, 2018 at 12:38:58PM -0400, Emilio G. Cota wrote:
> This paves the way for implementing the CPU list with an RCU QLIST,
> which cannot be traversed in reverse order.
> 
> Note that this is the only caller of CPU_FOREACH_REVERSE.
> 
> Signed-off-by: Emilio G. Cota <cota@braap.org>

Acked-by: David Gibson <david@gibson.dropbear.id.au>

> ---
>  hw/ppc/spapr.c | 16 +++++++++++++++-
>  1 file changed, 15 insertions(+), 1 deletion(-)
> 
> diff --git a/hw/ppc/spapr.c b/hw/ppc/spapr.c
> index 421b2dd09b..2ef5be2790 100644
> --- a/hw/ppc/spapr.c
> +++ b/hw/ppc/spapr.c
> @@ -622,9 +622,12 @@ static void spapr_populate_cpu_dt(CPUState *cs, void *fdt, int offset,
>  
>  static void spapr_populate_cpus_dt_node(void *fdt, sPAPRMachineState *spapr)
>  {
> +    CPUState **rev;
>      CPUState *cs;
> +    int n_cpus;
>      int cpus_offset;
>      char *nodename;
> +    int i;
>  
>      cpus_offset = fdt_add_subnode(fdt, 0, "cpus");
>      _FDT(cpus_offset);
> @@ -635,8 +638,19 @@ static void spapr_populate_cpus_dt_node(void *fdt, sPAPRMachineState *spapr)
>       * We walk the CPUs in reverse order to ensure that CPU DT nodes
>       * created by fdt_add_subnode() end up in the right order in FDT
>       * for the guest kernel the enumerate the CPUs correctly.
> +     *
> +     * The CPU list cannot be traversed in reverse order, so we need
> +     * to do extra work.
>       */
> -    CPU_FOREACH_REVERSE(cs) {
> +    n_cpus = 0;
> +    rev = NULL;
> +    CPU_FOREACH(cs) {
> +        rev = g_renew(CPUState *, rev, n_cpus + 1);
> +        rev[n_cpus++] = cs;
> +    }
> +
> +    for (i = n_cpus - 1; i >= 0; i--) {
> +        CPUState *cs = rev[i];
>          PowerPCCPU *cpu = POWERPC_CPU(cs);
>          int index = spapr_get_vcpu_id(cpu);
>          DeviceClass *dc = DEVICE_GET_CLASS(cs);

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[Qemu-devel] [PATCH 3/3] qom: implement CPU list with an RCU QLIST

[Emilio G. Cota]

Iterating over the list without using atomics is undefined behaviour,
since the list can be modified concurrently by other threads (e.g.
every time a new thread is created in user-mode).

Fix it by implementing the CPU list as an RCU QLIST. This requires
a little bit of extra work to insert CPUs at the tail of
the list and to iterate over the list in reverse order (see previous patch).

One might be tempted to just insert new CPUs at the head of the list.
However, I think this might lead to hard-to-debug issues, since it is
possible that callers are assuming that CPUs are inserted at the tail
(just like spapr code did in the previous patch). So instead of auditing
all callers, this patch simply keeps the old behaviour.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 cpus-common.c        | 19 +++++++++++++++----
 cpus.c               |  2 +-
 exec.c               |  2 +-
 include/qom/cpu.h    | 15 +++++++--------
 linux-user/main.c    |  2 +-
 linux-user/syscall.c |  2 +-
 6 files changed, 26 insertions(+), 16 deletions(-)

diff --git a/cpus-common.c b/cpus-common.c
index 6eaedae60b..d8e8db48dd 100644
--- a/cpus-common.c
+++ b/cpus-common.c
@@ -77,6 +77,8 @@ static void finish_safe_work(CPUState *cpu)
 
 void cpu_list_add(CPUState *cpu)
 {
+    CPUState *cs, *cs_next;
+
     qemu_mutex_lock(&qemu_cpu_list_lock);
     if (cpu->cpu_index == UNASSIGNED_CPU_INDEX) {
         cpu->cpu_index = cpu_get_free_index();
@@ -84,7 +86,18 @@ void cpu_list_add(CPUState *cpu)
     } else {
         assert(!cpu_index_auto_assigned);
     }
-    QTAILQ_INSERT_TAIL(&cpus, cpu, node);
+    /* poor man's tail insert */
+    CPU_FOREACH_SAFE(cs, cs_next) {
+        if (cs_next == NULL) {
+            break;
+        }
+    }
+    if (cs == NULL) {
+        QLIST_INSERT_HEAD_RCU(&cpus, cpu, node);
+    } else {
+        g_assert(cs_next == NULL);
+        QLIST_INSERT_AFTER_RCU(cs, cpu, node);
+    }
     cpu->in_cpu_list = true;
     qemu_mutex_unlock(&qemu_cpu_list_lock);
 
@@ -100,9 +113,7 @@ void cpu_list_remove(CPUState *cpu)
         return;
     }
 
-    assert(!(cpu_index_auto_assigned && cpu != QTAILQ_LAST(&cpus, CPUTailQ)));
-
-    QTAILQ_REMOVE(&cpus, cpu, node);
+    QLIST_REMOVE_RCU(cpu, node);
     cpu->cpu_index = UNASSIGNED_CPU_INDEX;
     qemu_mutex_unlock(&qemu_cpu_list_lock);
 }
diff --git a/cpus.c b/cpus.c
index b5844b7103..82e298d825 100644
--- a/cpus.c
+++ b/cpus.c
@@ -1491,7 +1491,7 @@ static void *qemu_tcg_rr_cpu_thread_fn(void *arg)
             atomic_mb_set(&cpu->exit_request, 0);
         }
 
-        qemu_tcg_rr_wait_io_event(cpu ? cpu : QTAILQ_FIRST(&cpus));
+        qemu_tcg_rr_wait_io_event(cpu ? cpu : QLIST_FIRST_RCU(&cpus));
         deal_with_unplugged_cpus();
     }
 
diff --git a/exec.c b/exec.c
index 4f5df07b6a..cab0da6919 100644
--- a/exec.c
+++ b/exec.c
@@ -114,7 +114,7 @@ int target_page_bits;
 bool target_page_bits_decided;
 #endif
 
-struct CPUTailQ cpus = QTAILQ_HEAD_INITIALIZER(cpus);
+struct CPUTailQ cpus = QLIST_HEAD_INITIALIZER(cpus);
 /* current CPU in the current thread. It is only valid inside
    cpu_exec() */
 __thread CPUState *current_cpu;
diff --git a/include/qom/cpu.h b/include/qom/cpu.h
index aa555e27a7..407c57254d 100644
--- a/include/qom/cpu.h
+++ b/include/qom/cpu.h
@@ -26,6 +26,7 @@
 #include "exec/memattrs.h"
 #include "qapi/qapi-types-run-state.h"
 #include "qemu/bitmap.h"
+#include "qemu/rcu_queue.h"
 #include "qemu/queue.h"
 #include "qemu/thread.h"
 
@@ -371,7 +372,7 @@ struct CPUState {
     struct GDBRegisterState *gdb_regs;
     int gdb_num_regs;
     int gdb_num_g_regs;
-    QTAILQ_ENTRY(CPUState) node;
+    QLIST_ENTRY(CPUState) node;
 
     /* ice debug support */
     QTAILQ_HEAD(breakpoints_head, CPUBreakpoint) breakpoints;
@@ -436,15 +437,13 @@ struct CPUState {
     GArray *iommu_notifiers;
 };
 
-QTAILQ_HEAD(CPUTailQ, CPUState);
+QLIST_HEAD(CPUTailQ, CPUState);
 extern struct CPUTailQ cpus;
-#define CPU_NEXT(cpu) QTAILQ_NEXT(cpu, node)
-#define CPU_FOREACH(cpu) QTAILQ_FOREACH(cpu, &cpus, node)
+#define CPU_NEXT(cpu) QLIST_NEXT_RCU(cpu, node)
+#define CPU_FOREACH(cpu) QLIST_FOREACH_RCU(cpu, &cpus, node)
 #define CPU_FOREACH_SAFE(cpu, next_cpu) \
-    QTAILQ_FOREACH_SAFE(cpu, &cpus, node, next_cpu)
-#define CPU_FOREACH_REVERSE(cpu) \
-    QTAILQ_FOREACH_REVERSE(cpu, &cpus, CPUTailQ, node)
-#define first_cpu QTAILQ_FIRST(&cpus)
+    QLIST_FOREACH_SAFE_RCU(cpu, &cpus, node, next_cpu)
+#define first_cpu QLIST_FIRST_RCU(&cpus)
 
 extern __thread CPUState *current_cpu;
 
diff --git a/linux-user/main.c b/linux-user/main.c
index ea00dd9057..99afb14ae5 100644
--- a/linux-user/main.c
+++ b/linux-user/main.c
@@ -126,7 +126,7 @@ void fork_end(int child)
            Discard information about the parent threads.  */
         CPU_FOREACH_SAFE(cpu, next_cpu) {
             if (cpu != thread_cpu) {
-                QTAILQ_REMOVE(&cpus, cpu, node);
+                QLIST_REMOVE_RCU(cpu, node);
             }
         }
         qemu_init_cpu_list();
diff --git a/linux-user/syscall.c b/linux-user/syscall.c
index dfc851cc35..41b592dee3 100644
--- a/linux-user/syscall.c
+++ b/linux-user/syscall.c
@@ -8040,7 +8040,7 @@ abi_long do_syscall(void *cpu_env, int num, abi_long arg1,
             TaskState *ts;
 
             /* Remove the CPU from the list.  */
-            QTAILQ_REMOVE(&cpus, cpu, node);
+            QLIST_REMOVE_RCU(cpu, node);
 
             cpu_list_unlock();
 
-- 
2.17.1

Re: [Qemu-devel] [PATCH 3/3] qom: implement CPU list with an RCU QLIST

[Paolo Bonzini]

On 13/08/2018 18:38, Emilio G. Cota wrote:
> 
> Fix it by implementing the CPU list as an RCU QLIST. This requires
> a little bit of extra work to insert CPUs at the tail of
> the list and to iterate over the list in reverse order (see previous patch).
> 
> One might be tempted to just insert new CPUs at the head of the list.
> However, I think this might lead to hard-to-debug issues, since it is
> possible that callers are assuming that CPUs are inserted at the tail
> (just like spapr code did in the previous patch). So instead of auditing
> all callers, this patch simply keeps the old behaviour.

Why not add an RCU_QSIMPLEQ, or even use an array since the quadratic
behavior should not be an issue?  The advantage of the array is that
reverse iteration becomes trivial.

Thanks,

Paolo

Re: [Qemu-devel] [PATCH 3/3] qom: implement CPU list with an RCU QLIST

[Emilio G. Cota]

On Tue, Aug 14, 2018 at 08:26:54 +0200, Paolo Bonzini wrote:
> On 13/08/2018 18:38, Emilio G. Cota wrote:
> > Fix it by implementing the CPU list as an RCU QLIST. This requires
> > a little bit of extra work to insert CPUs at the tail of
> > the list and to iterate over the list in reverse order (see previous patch).
> > 
> > One might be tempted to just insert new CPUs at the head of the list.
> > However, I think this might lead to hard-to-debug issues, since it is
> > possible that callers are assuming that CPUs are inserted at the tail
> > (just like spapr code did in the previous patch). So instead of auditing
> > all callers, this patch simply keeps the old behaviour.
> 
> Why not add an RCU_QSIMPLEQ

Because we can't atomically update both head.last and item.next.

> , or even use an array since the quadratic
> behavior should not be an issue?  The advantage of the array is that
> reverse iteration becomes trivial.

I just gave this a shot. IMO implementing CPU_NEXT based on the
array is too ugly to live.

I think the poor man's tail insert + the CPU_FOREACH_REVERSE
are a better compromise.

Thanks,

		Emilio

Re: [Qemu-devel] [PATCH 3/3] qom: implement CPU list with an RCU QLIST

[Paolo Bonzini]

On 15/08/2018 02:34, Emilio G. Cota wrote:
> On Tue, Aug 14, 2018 at 08:26:54 +0200, Paolo Bonzini wrote:
>> On 13/08/2018 18:38, Emilio G. Cota wrote:
>>> Fix it by implementing the CPU list as an RCU QLIST. This requires
>>> a little bit of extra work to insert CPUs at the tail of
>>> the list and to iterate over the list in reverse order (see previous patch).
>>>
>>> One might be tempted to just insert new CPUs at the head of the list.
>>> However, I think this might lead to hard-to-debug issues, since it is
>>> possible that callers are assuming that CPUs are inserted at the tail
>>> (just like spapr code did in the previous patch). So instead of auditing
>>> all callers, this patch simply keeps the old behaviour.
>>
>> Why not add an RCU_QSIMPLEQ
> 
> Because we can't atomically update both head.last and item.next.

Why do you need that?  Updates are protected by a mutex in RCU-protected
lists, it is not necessary to make them atomic.  Also, feel free to
implement a subset of the write-side macros, for example only
INSERT_{HEAD,TAIL,AFTER} and REMOVE_HEAD.

Anyway, the only difference between non-RCU and RCU-protected update
macros should be the write barriers (atomic_rcu_set).

>> , or even use an array since the quadratic
>> behavior should not be an issue?  The advantage of the array is that
>> reverse iteration becomes trivial.
> 
> I just gave this a shot. IMO implementing CPU_NEXT based on the
> array is too ugly to live.

You're right, I forgot about CPU_NEXT.

Paolo

Re: [Qemu-devel] [PATCH 3/3] qom: implement CPU list with an RCU QLIST

[Emilio G. Cota]

On Fri, Aug 17, 2018 at 19:53:40 +0200, Paolo Bonzini wrote:
> On 15/08/2018 02:34, Emilio G. Cota wrote:
> > On Tue, Aug 14, 2018 at 08:26:54 +0200, Paolo Bonzini wrote:
> >> On 13/08/2018 18:38, Emilio G. Cota wrote:
> >>> Fix it by implementing the CPU list as an RCU QLIST. This requires
> >>> a little bit of extra work to insert CPUs at the tail of
> >>> the list and to iterate over the list in reverse order (see previous patch).
> >>>
> >>> One might be tempted to just insert new CPUs at the head of the list.
> >>> However, I think this might lead to hard-to-debug issues, since it is
> >>> possible that callers are assuming that CPUs are inserted at the tail
> >>> (just like spapr code did in the previous patch). So instead of auditing
> >>> all callers, this patch simply keeps the old behaviour.
> >>
> >> Why not add an RCU_QSIMPLEQ
> > 
> > Because we can't atomically update both head.last and item.next.
> 
> Why do you need that?  Updates are protected by a mutex in RCU-protected
> lists, it is not necessary to make them atomic.  Also, feel free to
> implement a subset of the write-side macros, for example only
> INSERT_{HEAD,TAIL,AFTER} and REMOVE_HEAD.

Yes I got confused, was thinking you wanted to support the
reverse traversal (simpleq doesn't even have the reverse pointers,
so I don't know how I reached that conclusion).

v2 incoming.

Thanks,

		E.