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

["Alex Bennée" <alex.bennee@linaro.org>]

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