tcg: tb_lock removal redux v1

[Qemu-devel] [PATCH 06/16] translate-all: make l1_map lockless

Posted by Emilio G. Cota 7 years, 7 months ago

Groundwork for supporting parallel TCG generation.

We never remove entries from the radix tree, so we can use cmpxchg
to implement lockless insertions.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 accel/tcg/translate-all.c       | 24 ++++++++++++++----------
 docs/devel/multi-thread-tcg.txt |  4 ++--
 2 files changed, 16 insertions(+), 12 deletions(-)

diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c
index 06aa905..f2bfa71 100644
--- a/accel/tcg/translate-all.c
+++ b/accel/tcg/translate-all.c
@@ -472,20 +472,12 @@ static void page_init(void)
 #endif
 }
 
-/* If alloc=1:
- * Called with tb_lock held for system emulation.
- * Called with mmap_lock held for user-mode emulation.
- */
 static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc)
 {
     PageDesc *pd;
     void **lp;
     int i;
 
-    if (alloc) {
-        assert_memory_lock();
-    }
-
     /* Level 1.  Always allocated.  */
     lp = l1_map + ((index >> v_l1_shift) & (v_l1_size - 1));
 
@@ -494,11 +486,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc)
         void **p = atomic_rcu_read(lp);
 
         if (p == NULL) {
+            void *existing;
+
             if (!alloc) {
                 return NULL;
             }
             p = g_new0(void *, V_L2_SIZE);
-            atomic_rcu_set(lp, p);
+            existing = atomic_cmpxchg(lp, NULL, p);
+            if (unlikely(existing)) {
+                g_free(p);
+                p = existing;
+            }
         }
 
         lp = p + ((index >> (i * V_L2_BITS)) & (V_L2_SIZE - 1));
@@ -506,11 +504,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc)
 
     pd = atomic_rcu_read(lp);
     if (pd == NULL) {
+        void *existing;
+
         if (!alloc) {
             return NULL;
         }
         pd = g_new0(PageDesc, V_L2_SIZE);
-        atomic_rcu_set(lp, pd);
+        existing = atomic_cmpxchg(lp, NULL, pd);
+        if (unlikely(existing)) {
+            g_free(pd);
+            pd = existing;
+        }
     }
 
     return pd + (index & (V_L2_SIZE - 1));
diff --git a/docs/devel/multi-thread-tcg.txt b/docs/devel/multi-thread-tcg.txt
index a99b456..faf8918 100644
--- a/docs/devel/multi-thread-tcg.txt
+++ b/docs/devel/multi-thread-tcg.txt
@@ -134,8 +134,8 @@ tb_set_jmp_target() code. Modification to the linked lists that allow
 searching for linked pages are done under the protect of the
 tb_lock().
 
-The global page table is protected by the tb_lock() in system-mode and
-mmap_lock() in linux-user mode.
+The global page table is a lockless radix tree; cmpxchg is used
+to atomically insert new elements.
 
 The lookup caches are updated atomically and the lookup hash uses QHT
 which is designed for concurrent safe lookup.
-- 
2.7.4

Re: [Qemu-devel] [PATCH 06/16] translate-all: make l1_map lockless

Posted by Richard Henderson 7 years, 7 months ago

On 02/26/2018 09:39 PM, Emilio G. Cota wrote:
> Groundwork for supporting parallel TCG generation.
> 
> We never remove entries from the radix tree, so we can use cmpxchg
> to implement lockless insertions.
> 
> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  accel/tcg/translate-all.c       | 24 ++++++++++++++----------
>  docs/devel/multi-thread-tcg.txt |  4 ++--
>  2 files changed, 16 insertions(+), 12 deletions(-)

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>


r~

Re: [Qemu-devel] [PATCH 06/16] translate-all: make l1_map lockless

Posted by Alex Bennée 7 years, 6 months ago

Emilio G. Cota <cota@braap.org> writes:

> Groundwork for supporting parallel TCG generation.
>
> We never remove entries from the radix tree, so we can use cmpxchg
> to implement lockless insertions.
>
> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

> ---
>  accel/tcg/translate-all.c       | 24 ++++++++++++++----------
>  docs/devel/multi-thread-tcg.txt |  4 ++--
>  2 files changed, 16 insertions(+), 12 deletions(-)
>
> diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c
> index 06aa905..f2bfa71 100644
> --- a/accel/tcg/translate-all.c
> +++ b/accel/tcg/translate-all.c
> @@ -472,20 +472,12 @@ static void page_init(void)
>  #endif
>  }
>
> -/* If alloc=1:
> - * Called with tb_lock held for system emulation.
> - * Called with mmap_lock held for user-mode emulation.
> - */
>  static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc)
>  {
>      PageDesc *pd;
>      void **lp;
>      int i;
>
> -    if (alloc) {
> -        assert_memory_lock();
> -    }
> -
>      /* Level 1.  Always allocated.  */
>      lp = l1_map + ((index >> v_l1_shift) & (v_l1_size - 1));
>
> @@ -494,11 +486,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc)
>          void **p = atomic_rcu_read(lp);
>
>          if (p == NULL) {
> +            void *existing;
> +
>              if (!alloc) {
>                  return NULL;
>              }
>              p = g_new0(void *, V_L2_SIZE);
> -            atomic_rcu_set(lp, p);
> +            existing = atomic_cmpxchg(lp, NULL, p);
> +            if (unlikely(existing)) {
> +                g_free(p);
> +                p = existing;
> +            }
>          }
>
>          lp = p + ((index >> (i * V_L2_BITS)) & (V_L2_SIZE - 1));
> @@ -506,11 +504,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc)
>
>      pd = atomic_rcu_read(lp);
>      if (pd == NULL) {
> +        void *existing;
> +
>          if (!alloc) {
>              return NULL;
>          }
>          pd = g_new0(PageDesc, V_L2_SIZE);
> -        atomic_rcu_set(lp, pd);
> +        existing = atomic_cmpxchg(lp, NULL, pd);
> +        if (unlikely(existing)) {
> +            g_free(pd);
> +            pd = existing;
> +        }
>      }
>
>      return pd + (index & (V_L2_SIZE - 1));
> diff --git a/docs/devel/multi-thread-tcg.txt b/docs/devel/multi-thread-tcg.txt
> index a99b456..faf8918 100644
> --- a/docs/devel/multi-thread-tcg.txt
> +++ b/docs/devel/multi-thread-tcg.txt
> @@ -134,8 +134,8 @@ tb_set_jmp_target() code. Modification to the linked lists that allow
>  searching for linked pages are done under the protect of the
>  tb_lock().
>
> -The global page table is protected by the tb_lock() in system-mode and
> -mmap_lock() in linux-user mode.
> +The global page table is a lockless radix tree; cmpxchg is used
> +to atomically insert new elements.
>
>  The lookup caches are updated atomically and the lookup hash uses QHT
>  which is designed for concurrent safe lookup.


--
Alex Bennée