Re: [Qemu-devel] [PATCH] [RFC] Convert Qemu Timer List and Active Timers to RCU

[Alex Bligh]

Mike,

Some comments:

1. You seem to be removing the use of the active_timers_lock and replacing it by
   rcu (fine). However, you seem to have left the qemu_mutex_destroy in
   timerlist_free, and left the mutex in QEMUTimerList. Any reason why we need
   both?

2. You have introduced rcu not only to protect active_timers, the list of
   active timers within one timerlist, but also to protect (I think)
   the list of timerlists, as evidenced by the fact you have
   reclaim_timer_list as well as reclaim_timer. We currently have no
   locking in the creation/deletion of timerlists as these only happen on init
   or on when an AioContext is created/destroyed (as these are the only things
   that create or delete TimerListGroups); both these operations are
   required to happen within the main thread and are protected by the
   BQL. Indeed currently nothing every destroys an AioContext. I suspect
   if there is really a need to destroy timerlists in threads other than
   the main thread we are going to have more issues than locking of the list of
   timerlists. I suggest you remove these changes and solely look at protecting
   the list of active timers (as opposed to the list of timerlists) by RCU.

   I wrote something describing the new structure here:
     http://blog.alex.org.uk/2013/08/24/changes-to-qemus-timer-system/

   I suspect simplifying this such that you are *only* protecting the active
   timer list would make the patch far less intrusive.

3. If you are going to protect the list of timerlists as well, do you
   not need to at least take the rcu read lock in timerlist_new?

4. In timerlist_notify(), you are holding the rcu_read_lock across
   the callback or qemu_notify_event. Why is this necessary? EG can't you
   do something like:

    void timerlist_notify(QEMUTimerList *timer_list)
    {
         rcu_read_lock();
         if (atomic_rcu_read(&timer_list->notify_cb)) {
            QEMUTimerListNotifyCB *notify_cb = timer_list->notify_cb;
            void *notify_opaque = timer_list->notify_opaque;
            rcu_read_unlock();
            notify_cb(notify_opaque);
        } else {
            rcu_read_unlock();
            qemu_notify_event();
        }
    }

   as if the callback modifies the timer it will take its own rcu read lock.
   My concern here is that the qemu_notify_event stuff could in theory be
   quite long running. Perhaps we don't care about how often reclaim occurs
   though.

5. Similarly to the above, in qemu_clock_notify, you take the
   rcu_read_lock, and then do a QLIST_FOREACH_RCU. That will mean
   the rcu_read_lock is taken anyway in 99% of calls to timerlist_notify.
   This is going through the list of timerlists, and that list is in
   practice static (protected by the BQL). Similarly in
   qemu_clock_deadline_ns_all, timerlist_get_clock, etc.

6. In timerlist_expired, rcu_read_unlock() appears to get called
   at the end after the return statement (last line of the function).

7. May be my reading of the diff, but in timer_mod_ns it seems to be
   introducing two rcu_read_unlock()s at the end of the function
   (after 'Rearm if necessary') - should the first not be a
   rcu_read_lock()?

8. Again, may be my reading of the diff, but you appear to have
   introduced a rcu_read_lock() outside the loop, but then
   unlock it within the loop. If the loop iterates more than once,
   won't it do more unlocks than locks?

Alex




On 12 Feb 2014, at 19:09, Mike Day wrote:

> 
> Allow readers to use RCU when reading Qemu timer lists. Applies to
> Paolo Bonzini's RCU branch, https://github.com/bonzini/qemu/tree/rcu.
> 
> This patch is for comment and review only.  The rcu branch needs to be
> rebased on upstream.
> 
> Signed-off-by: Mike Day <address@hidden>
> ---
> include/qemu/timer.h |  9 +++++-
> qemu-timer.c         | 88 +++++++++++++++++++++++++++++++++++-----------------
> 2 files changed, 67 insertions(+), 30 deletions(-)
> 
> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> index b58903b..5aaa213 100644
> --- a/include/qemu/timer.h
> +++ b/include/qemu/timer.h
> @@ -4,7 +4,13 @@
> #include "qemu/typedefs.h"
> #include "qemu-common.h"
> #include "qemu/notify.h"
> -
> +#ifdef __GNUC__
> +#ifndef __ATOMIC_RELEASE
> +#define __ATOMIC_RELEASE
> +#endif
> +#endif
> +#include "qemu/atomic.h"
> +#include "qemu/rcu.h"
> /* timers */
> 
> #define SCALE_MS 1000000
> @@ -61,6 +67,7 @@ struct QEMUTimer {
>     void *opaque;
>     QEMUTimer *next;
>     int scale;
> +    struct rcu_head rcu;
> };
> 
> extern QEMUTimerListGroup main_loop_tlg;
> diff --git a/qemu-timer.c b/qemu-timer.c
> index 6b62e88..27285ca 100644
> --- a/qemu-timer.c
> +++ b/qemu-timer.c
> @@ -29,6 +29,7 @@
> #include "hw/hw.h"
> 
> #include "qemu/timer.h"
> +#include "qemu/rcu_queue.h"
> #ifdef CONFIG_POSIX
> #include <pthread.h>
> #endif
> @@ -49,7 +50,6 @@ typedef struct QEMUClock {
> 
>     NotifierList reset_notifiers;
>     int64_t last;
> -
>     QEMUClockType type;
>     bool enabled;
> } QEMUClock;
> @@ -71,6 +71,7 @@ struct QEMUTimerList {
>     QLIST_ENTRY(QEMUTimerList) list;
>     QEMUTimerListNotifyCB *notify_cb;
>     void *notify_opaque;
> +    struct rcu_head rcu;
> };
> 
> /**
> @@ -107,6 +108,12 @@ QEMUTimerList *timerlist_new(QEMUClockType type,
>     return timer_list;
> }
> 
> +static void reclaim_timer_list(struct rcu_head *rcu)
> +{
> +    QEMUTimerList *timer_list = container_of(rcu, QEMUTimerList, rcu);
> +    g_free(timer_list);
> +}
> +
> void timerlist_free(QEMUTimerList *timer_list)
> {
>     assert(!timerlist_has_timers(timer_list));
> @@ -114,7 +121,7 @@ void timerlist_free(QEMUTimerList *timer_list)
>         QLIST_REMOVE(timer_list, list);
>     }
>     qemu_mutex_destroy(&timer_list->active_timers_lock);
> -    g_free(timer_list);
> +    call_rcu1(&timer_list->rcu, reclaim_timer_list);
> }
> 
> static void qemu_clock_init(QEMUClockType type)
> @@ -138,9 +145,11 @@ void qemu_clock_notify(QEMUClockType type)
> {
>     QEMUTimerList *timer_list;
>     QEMUClock *clock = qemu_clock_ptr(type);
> -    QLIST_FOREACH(timer_list, &clock->timerlists, list) {
> +    rcu_read_lock();
> +    QLIST_FOREACH_RCU(timer_list, &clock->timerlists, list) {
>         timerlist_notify(timer_list);
>     }
> +    rcu_read_unlock();
> }
> 
> void qemu_clock_enable(QEMUClockType type, bool enabled)
> @@ -155,7 +164,7 @@ void qemu_clock_enable(QEMUClockType type, bool enabled)
> 
> bool timerlist_has_timers(QEMUTimerList *timer_list)
> {
> -    return !!timer_list->active_timers;
> +    return !!atomic_rcu_read(&timer_list->active_timers);
> }
> 
> bool qemu_clock_has_timers(QEMUClockType type)
> @@ -168,15 +177,15 @@ bool timerlist_expired(QEMUTimerList *timer_list)
> {
>     int64_t expire_time;
> 
> -    qemu_mutex_lock(&timer_list->active_timers_lock);
> -    if (!timer_list->active_timers) {
> -        qemu_mutex_unlock(&timer_list->active_timers_lock);
> +    rcu_read_lock();
> +    if (atomic_rcu_read(&timer_list->active_timers)) {
> +        rcu_read_unlock();
>         return false;
>     }
> -    expire_time = timer_list->active_timers->expire_time;
> -    qemu_mutex_unlock(&timer_list->active_timers_lock);
> 
> +    expire_time = timer_list->active_timers->expire_time;
>     return expire_time < qemu_clock_get_ns(timer_list->clock->type);
> +    rcu_read_unlock();
> }
> 
> bool qemu_clock_expired(QEMUClockType type)
> @@ -194,8 +203,10 @@ int64_t timerlist_deadline_ns(QEMUTimerList *timer_list)
> {
>     int64_t delta;
>     int64_t expire_time;
> -
> -    if (!timer_list->clock->enabled) {
> +    bool enabled;
> +    rcu_read_lock();
> +    enabled = atomic_rcu_read(&timer_list->clock->enabled);
> +    if (!enabled) {
>         return -1;
>     }
> 
> @@ -203,16 +214,13 @@ int64_t timerlist_deadline_ns(QEMUTimerList *timer_list)
>      * value but ->notify_cb() is called when the deadline changes.  Therefore
>      * the caller should notice the change and there is no race condition.
>      */
> -    qemu_mutex_lock(&timer_list->active_timers_lock);
>     if (!timer_list->active_timers) {
> -        qemu_mutex_unlock(&timer_list->active_timers_lock);
> +        rcu_read_unlock();
>         return -1;
>     }
>     expire_time = timer_list->active_timers->expire_time;
> -    qemu_mutex_unlock(&timer_list->active_timers_lock);
> -
>     delta = expire_time - qemu_clock_get_ns(timer_list->clock->type);
> -
> +    rcu_read_unlock();
>     if (delta <= 0) {
>         return 0;
>     }
> @@ -230,16 +238,22 @@ int64_t qemu_clock_deadline_ns_all(QEMUClockType type)
>     int64_t deadline = -1;
>     QEMUTimerList *timer_list;
>     QEMUClock *clock = qemu_clock_ptr(type);
> -    QLIST_FOREACH(timer_list, &clock->timerlists, list) {
> +    rcu_read_lock();
> +    QLIST_FOREACH_RCU(timer_list, &clock->timerlists, list) {
>         deadline = qemu_soonest_timeout(deadline,
>                                         timerlist_deadline_ns(timer_list));
>     }
> +    rcu_read_unlock();
>     return deadline;
> }
> 
> QEMUClockType timerlist_get_clock(QEMUTimerList *timer_list)
> {
> -    return timer_list->clock->type;
> +    QEMUClockType type;
> +    rcu_read_lock();
> +    type = atomic_rcu_read(&timer_list->clock->type);
> +    rcu_read_unlock();
> +    return type;
> }
> 
> QEMUTimerList *qemu_clock_get_main_loop_timerlist(QEMUClockType type)
> @@ -249,11 +263,13 @@ QEMUTimerList 
> *qemu_clock_get_main_loop_timerlist(QEMUClockType type)
> 
> void timerlist_notify(QEMUTimerList *timer_list)
> {
> -    if (timer_list->notify_cb) {
> +    rcu_read_lock();
> +    if (atomic_rcu_read(&timer_list->notify_cb)) {
>         timer_list->notify_cb(timer_list->notify_opaque);
>     } else {
>         qemu_notify_event();
>     }
> +    rcu_read_unlock();
> }
> 
> /* Transition function to convert a nanosecond timeout to ms
> @@ -308,18 +324,24 @@ void timer_init(QEMUTimer *ts,
>                 QEMUTimerList *timer_list, int scale,
>                 QEMUTimerCB *cb, void *opaque)
> {
> -    ts->timer_list = timer_list;
>     ts->cb = cb;
>     ts->opaque = opaque;
>     ts->scale = scale;
>     ts->expire_time = -1;
> +    ts->timer_list = timer_list;
> }
> 
> -void timer_free(QEMUTimer *ts)
> +static void reclaim_timer(struct rcu_head *rcu)
> {
> +    QEMUTimer *ts = container_of(rcu, QEMUTimer, rcu);
>     g_free(ts);
> }
> 
> +void timer_free(QEMUTimer *ts)
> +{
> +    call_rcu1(&ts->rcu, reclaim_timer);
> +}
> +
> static void timer_del_locked(QEMUTimerList *timer_list, QEMUTimer *ts)
> {
>     QEMUTimer **pt, *t;
> @@ -331,7 +353,7 @@ static void timer_del_locked(QEMUTimerList *timer_list, 
> QEMUTimer *ts)
>         if (!t)
>             break;
>         if (t == ts) {
> -            *pt = t->next;
> +            atomic_rcu_set(pt, t->next);
>             break;
>         }
>         pt = &t->next;
> @@ -369,15 +391,17 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
>     }
>     ts->expire_time = MAX(expire_time, 0);
>     ts->next = *pt;
> -    *pt = ts;
> +    atomic_rcu_set(pt, ts);
>     qemu_mutex_unlock(&timer_list->active_timers_lock);
> -
>     /* Rearm if necessary  */
> +    rcu_read_unlock();
>     if (pt == &timer_list->active_timers) {
>         /* Interrupt execution to force deadline recalculation.  */
>         qemu_clock_warp(timer_list->clock->type);
>         timerlist_notify(timer_list);
>     }
> +    rcu_read_unlock();
> +
> }
> 
> void timer_mod(QEMUTimer *ts, int64_t expire_time)
> @@ -402,30 +426,35 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
>     bool progress = false;
>     QEMUTimerCB *cb;
>     void *opaque;
> +    bool enabled;
> 
> -    if (!timer_list->clock->enabled) {
> +    enabled = atomic_rcu_read(&timer_list->clock->enabled);
> +    if (!enabled) {
>         return progress;
>     }
> -
> +    rcu_read_lock();
>     current_time = qemu_clock_get_ns(timer_list->clock->type);
>     for(;;) {
> -        qemu_mutex_lock(&timer_list->active_timers_lock);
>         ts = timer_list->active_timers;
>         if (!timer_expired_ns(ts, current_time)) {
> -            qemu_mutex_unlock(&timer_list->active_timers_lock);
> +            rcu_read_unlock();
>             break;
>         }
> +        rcu_read_unlock();
> 
> +        qemu_mutex_lock(&timer_list->active_timers_lock);
>         /* remove timer from the list before calling the callback */
> -        timer_list->active_timers = ts->next;
>         ts->next = NULL;
>         ts->expire_time = -1;
>         cb = ts->cb;
>         opaque = ts->opaque;
> +        timer_list->active_timers = ts->next;
>         qemu_mutex_unlock(&timer_list->active_timers_lock);
> 
>         /* run the callback (the timer list can be modified) */
> +        rcu_read_lock();
>         cb(opaque);
> +        rcu_read_unlock();
>         progress = true;
>     }
>     return progress;
> @@ -477,6 +506,7 @@ int64_t timerlistgroup_deadline_ns(QEMUTimerListGroup 
> *tlg)
>     return deadline;
> }
> 
> +/* caller holds an rcu read lock */
> int64_t qemu_clock_get_ns(QEMUClockType type)
> {
>     int64_t now, last;
> 
> -- 
> Mike Day | "Endurance is a Virtue"
> 
> 

-- 
Alex Bligh