[qemu,v5,04/18] memory: Move AddressSpaceDispatch from AddressSpace to FlatView

As we are going to share FlatView's between AddressSpace's,
and AddressSpaceDispatch is a structure to perform quick lookup
in FlatView, this moves ASD to FlatView.

After previosly open coded ASD rendering, we can also remove
as->next_dispatch as the new FlatView pointer is stored
on a stack and set to an AS atomically.

flatview_destroy() is executed under RCU instead of
address_space_dispatch_free() now.

This makes mem_begin/mem_commit to work with ASD and mem_add with FV
as later on mem_add will be taking FV as an argument anyway.

This should cause no behavioural change.

Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
---
Changes:
v4:
* since FlatView::rcu is used now to dispose FV, call_rcu() in
address_space_update_topology() is replaced with direct call to
flatview_unref()
---
 include/exec/memory-internal.h | 12 +++++++-----
 include/exec/memory.h          |  2 --
 exec.c                         | 41 +++++++++++------------------------------
 memory.c                       | 31 ++++++++++++++++++++++++-------
 4 files changed, 42 insertions(+), 44 deletions(-)

On 21/09/2017 10:50, Alexey Kardashevskiy wrote:
> * since FlatView::rcu is used now to dispose FV, call_rcu() in
> address_space_update_topology() is replaced with direct call to
> flatview_unref()

Hmm, this is not correct, as you could have


   thread 1             thread 2             RCU thread
  -------------------------------------------------------------
   rcu_read_lock
   read as->current_map
                        set as->current_map
                        flatview_unref
                           '--> call_rcu
   flatview_ref
   rcu_read_unlock
                                             flatview_destroy

I need to think a bit more about this (and possibly ask Paul...).

Paolo

On 21/09/17 21:51, Paolo Bonzini wrote:
> On 21/09/2017 10:50, Alexey Kardashevskiy wrote:
>> * since FlatView::rcu is used now to dispose FV, call_rcu() in
>> address_space_update_topology() is replaced with direct call to
>> flatview_unref()
> 
> Hmm, this is not correct, as you could have
> 
> 
>    thread 1             thread 2             RCU thread
>   -------------------------------------------------------------
>    rcu_read_lock
>    read as->current_map
>                         set as->current_map
>                         flatview_unref
>                            '--> call_rcu
>    flatview_ref
>    rcu_read_unlock
>                                              flatview_destroy
> 
> I need to think a bit more about this (and possibly ask Paul...).
> 
> Paolo
> 

Nah, you're right, it should be like this:


diff --git a/memory.c b/memory.c
index 35b2fc5f7f..689bf53866 100644
--- a/memory.c
+++ b/memory.c
@@ -317,7 +317,7 @@ static void flatview_ref(FlatView *view)
 static void flatview_unref(FlatView *view)
 {
     if (atomic_fetch_dec(&view->ref) == 1) {
-        call_rcu(view, flatview_destroy, rcu);
+        flatview_destroy(view);
     }
 }

@@ -768,7 +768,7 @@ static FlatView *generate_memory_topology(MemoryRegion *mr)
         flatview_simplify(view);

         if (!view->nr) {
-            flatview_destroy(view);
+            flatview_unref(view);
             use_empty = true;
         }
     }
@@ -1026,7 +1026,7 @@ static void address_space_set_flatview(AddressSpace *as)
     /* Writes are protected by the BQL.  */
     atomic_rcu_set(&as->current_map, new_view);
     if (old_view) {
-        flatview_unref(old_view);
+        call_rcu(view, flatview_unref, rcu);
     }

On 21/09/2017 15:44, Alexey Kardashevskiy wrote:
> On 21/09/17 21:51, Paolo Bonzini wrote:
>> On 21/09/2017 10:50, Alexey Kardashevskiy wrote:
>>> * since FlatView::rcu is used now to dispose FV, call_rcu() in
>>> address_space_update_topology() is replaced with direct call to
>>> flatview_unref()
>>
>> Hmm, this is not correct, as you could have
>>
>>
>>    thread 1             thread 2             RCU thread
>>   -------------------------------------------------------------
>>    rcu_read_lock
>>    read as->current_map
>>                         set as->current_map
>>                         flatview_unref
>>                            '--> call_rcu
>>    flatview_ref
>>    rcu_read_unlock
>>                                              flatview_destroy
>>
>> I need to think a bit more about this (and possibly ask Paul...).
>>
>> Paolo
>>
> 
> Nah, you're right, it should be like this:
> 
> 
> diff --git a/memory.c b/memory.c
> index 35b2fc5f7f..689bf53866 100644
> --- a/memory.c
> +++ b/memory.c
> @@ -317,7 +317,7 @@ static void flatview_ref(FlatView *view)
>  static void flatview_unref(FlatView *view)
>  {
>      if (atomic_fetch_dec(&view->ref) == 1) {
> -        call_rcu(view, flatview_destroy, rcu);
> +        flatview_destroy(view);
>      }
>  }
> 
> @@ -768,7 +768,7 @@ static FlatView *generate_memory_topology(MemoryRegion *mr)
>          flatview_simplify(view);
> 
>          if (!view->nr) {
> -            flatview_destroy(view);
> +            flatview_unref(view);
>              use_empty = true;
>          }
>      }
> @@ -1026,7 +1026,7 @@ static void address_space_set_flatview(AddressSpace *as)
>      /* Writes are protected by the BQL.  */
>      atomic_rcu_set(&as->current_map, new_view);
>      if (old_view) {
> -        flatview_unref(old_view);
> +        call_rcu(view, flatview_unref, rcu);
>      }

This still doesn't cover address_space_get_flatview, i.e. it is a 
pre-existing bug.

I found a similar case in Linux, here is how they solved it:

commit 358136532dd29e9ed96e0e523d2d510e71bda003
Author: Paolo Bonzini <pbonzini@redhat.com>
Date:   Thu Sep 21 14:32:47 2017 +0200

    memory: avoid "resurrection" of dead FlatViews
    
    It's possible for address_space_get_flatview() as it currently stands
    to cause a use-after-free for the returned FlatView, if the reference
    count is incremented after the FlatView has been replaced by a writer:
    
       thread 1             thread 2             RCU thread
      -------------------------------------------------------------
       rcu_read_lock
       read as->current_map
                            set as->current_map
                            flatview_unref
                               '--> call_rcu
       flatview_ref
         [ref=1]
       rcu_read_unlock
                                                 flatview_destroy
       <badness>
    
    Since FlatViews are not updated very often, we can just detect the
    situation using a new atomic op atomic_fetch_inc_nonzero, similar to
    Linux's atomic_inc_not_zero, which performs the refcount increment only if
    it hasn't already hit zero.  This is similar to Linux commit de09a9771a53
    ("CRED: Fix get_task_cred() and task_state() to not resurrect dead
    credentials", 2010-07-29).
    
    Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

diff --git a/docs/devel/atomics.txt b/docs/devel/atomics.txt
index 048e5f23cb..10c5fa37e8 100644
--- a/docs/devel/atomics.txt
+++ b/docs/devel/atomics.txt
@@ -64,6 +64,7 @@ operations:
     typeof(*ptr) atomic_fetch_and(ptr, val)
     typeof(*ptr) atomic_fetch_or(ptr, val)
     typeof(*ptr) atomic_fetch_xor(ptr, val)
+    typeof(*ptr) atomic_fetch_inc_nonzero(ptr)
     typeof(*ptr) atomic_xchg(ptr, val)
     typeof(*ptr) atomic_cmpxchg(ptr, old, new)
 
diff --git a/include/qemu/atomic.h b/include/qemu/atomic.h
index b6b62fb771..44ad1e6c32 100644
--- a/include/qemu/atomic.h
+++ b/include/qemu/atomic.h
@@ -197,6 +197,15 @@
     atomic_cmpxchg__nocheck(ptr, old, new);                             \
 })
 
+#define atomic_fetch_inc_nonzero(ptr) ({                                \
+    QEMU_BUILD_BUG_ON(sizeof(*ptr) > ATOMIC_REG_SIZE);                  \
+    typeof_strip_qual(*ptr) _oldn = atomic_read(ptr);                   \
+    while (_oldn && atomic_cmpxchg(ptr, _oldn, _oldn + 1) != _oldn) {   \
+        _oldn = atomic_read(ptr);                                       \
+    }                                                                   \
+    _oldn;                                                              \
+})
+
 /* Provide shorter names for GCC atomic builtins, return old value */
 #define atomic_fetch_inc(ptr)  __atomic_fetch_add(ptr, 1, __ATOMIC_SEQ_CST)
 #define atomic_fetch_dec(ptr)  __atomic_fetch_sub(ptr, 1, __ATOMIC_SEQ_CST)
diff --git a/memory.c b/memory.c
index 2b90117c60..51f54ab430 100644
--- a/memory.c
+++ b/memory.c
@@ -294,9 +294,9 @@ static void flatview_destroy(FlatView *view)
     g_free(view);
 }
 
-static void flatview_ref(FlatView *view)
+static bool flatview_ref(FlatView *view)
 {
-    atomic_inc(&view->ref);
+    return atomic_fetch_inc_nonzero(&view->ref) > 0;
 }
 
 static void flatview_unref(FlatView *view)
@@ -773,8 +773,12 @@ static FlatView *address_space_get_flatview(AddressSpace *as)
     FlatView *view;
 
     rcu_read_lock();
-    view = atomic_rcu_read(&as->current_map);
-    flatview_ref(view);
+    do {
+        view = atomic_rcu_read(&as->current_map);
+        /* If somebody has replaced as->current_map concurrently,
+         * flatview_ref returns false.
+         */
+    } while (!flatview_ref(view));
     rcu_read_unlock();
     return view;
 }