[2/2] qemu-timer: make qemu_timer_mod_ns() and qemu_timer_del() thread-safe

Introduce QEMUTimerList->active_timers_lock to protect the linked list
of active timers.  This allows qemu_timer_mod_ns() to be called from any
thread.

Note that vm_clock is not thread-safe and its use of
qemu_clock_has_timers() works fine today but is also not thread-safe.

The purpose of this patch is to eventually let device models set or
cancel timers from a vcpu thread without holding the global mutex.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 include/qemu/timer.h | 17 ++++++++++++++
 qemu-timer.c         | 66 +++++++++++++++++++++++++++++++++++++++++-----------
 2 files changed, 69 insertions(+), 14 deletions(-)

--On 12 August 2013 14:49:29 +0200 Stefan Hajnoczi <stefanha@redhat.com> 
wrote:

> Introduce QEMUTimerList->active_timers_lock to protect the linked list
> of active timers.  This allows qemu_timer_mod_ns() to be called from any
> thread.
>
> Note that vm_clock is not thread-safe and its use of
> qemu_clock_has_timers() works fine today but is also not thread-safe.
>
> The purpose of this patch is to eventually let device models set or
> cancel timers from a vcpu thread without holding the global mutex.
>
> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>

Reviewed-by: Alex Bligh <alex@alex.org.uk>

> ---
>  include/qemu/timer.h | 17 ++++++++++++++
>  qemu-timer.c         | 66
> +++++++++++++++++++++++++++++++++++++++++-----------  2 files changed, 69
> insertions(+), 14 deletions(-)
>
> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> index 829c005..3543b0e 100644
> --- a/include/qemu/timer.h
> +++ b/include/qemu/timer.h
> @@ -114,6 +114,10 @@ static inline int64_t
> qemu_clock_get_us(QEMUClockType type)   * Determines whether a clock's
> default timer list
>   * has timers attached
>   *
> + * Note that this function should not be used when other threads also
> access + * the timer list.  The return value may be outdated by the time
> it is acted + * upon.
> + *
>   * Returns: true if the clock's default timer list
>   * has timers attached
>   */
> @@ -270,6 +274,10 @@ void timerlist_free(QEMUTimerList *timer_list);
>   *
>   * Determine whether a timer list has active timers
>   *
> + * Note that this function should not be used when other threads also
> access + * the timer list.  The return value may be outdated by the time
> it is acted + * upon.
> + *
>   * Returns: true if the timer list has timers.
>   */
>  bool timerlist_has_timers(QEMUTimerList *timer_list);
> @@ -511,6 +519,9 @@ void timer_free(QEMUTimer *ts);
>   * @ts: the timer
>   *
>   * Delete a timer from the active list.
> + *
> + * This function is thread-safe but the timer and its timer list must
> not be + * freed while this function is running.
>   */
>  void timer_del(QEMUTimer *ts);
>
> @@ -520,6 +531,9 @@ void timer_del(QEMUTimer *ts);
>   * @expire_time: the expiry time in nanoseconds
>   *
>   * Modify a timer to expire at @expire_time
> + *
> + * This function is thread-safe but the timer and its timer list must
> not be + * freed while this function is running.
>   */
>  void timer_mod_ns(QEMUTimer *ts, int64_t expire_time);
>
> @@ -530,6 +544,9 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time);
>   *
>   * Modify a timer to expiry at @expire_time, taking into
>   * account the scale associated with the timer.
> + *
> + * This function is thread-safe but the timer and its timer list must
> not be + * freed while this function is running.
>   */
>  void timer_mod(QEMUTimer *ts, int64_t expire_timer);
>
> diff --git a/qemu-timer.c b/qemu-timer.c
> index 818d235..3a5b46d 100644
> --- a/qemu-timer.c
> +++ b/qemu-timer.c
> @@ -66,6 +66,7 @@ QEMUClock qemu_clocks[QEMU_CLOCK_MAX];
>
>  struct QEMUTimerList {
>      QEMUClock *clock;
> +    QemuMutex active_timers_lock;
>      QEMUTimer *active_timers;
>      QLIST_ENTRY(QEMUTimerList) list;
>      QEMUTimerListNotifyCB *notify_cb;
> @@ -101,6 +102,7 @@ QEMUTimerList *timerlist_new(QEMUClockType type,
>      timer_list->clock = clock;
>      timer_list->notify_cb = cb;
>      timer_list->notify_opaque = opaque;
> +    qemu_mutex_init(&timer_list->active_timers_lock);
>      QLIST_INSERT_HEAD(&clock->timerlists, timer_list, list);
>      return timer_list;
>  }
> @@ -111,6 +113,7 @@ void timerlist_free(QEMUTimerList *timer_list)
>      if (timer_list->clock) {
>          QLIST_REMOVE(timer_list, list);
>      }
> +    qemu_mutex_destroy(&timer_list->active_timers_lock);
>      g_free(timer_list);
>  }
>
> @@ -163,9 +166,17 @@ bool qemu_clock_has_timers(QEMUClockType type)
>
>  bool timerlist_expired(QEMUTimerList *timer_list)
>  {
> -    return (timer_list->active_timers &&
> -            timer_list->active_timers->expire_time <
> -            qemu_clock_get_ns(timer_list->clock->type));
> +    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);
> +        return false;
> +    }
> +    expire_time = timer_list->active_timers->expire_time;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
> +
> +    return expire_time < qemu_clock_get_ns(timer_list->clock->type);
>  }
>
>  bool qemu_clock_expired(QEMUClockType type)
> @@ -182,13 +193,25 @@ bool qemu_clock_expired(QEMUClockType type)
>  int64_t timerlist_deadline_ns(QEMUTimerList *timer_list)
>  {
>      int64_t delta;
> +    int64_t expire_time;
>
> -    if (!timer_list->clock->enabled || !timer_list->active_timers) {
> +    if (!timer_list->clock->enabled) {
>          return -1;
>      }
>
> -    delta = timer_list->active_timers->expire_time -
> -        qemu_clock_get_ns(timer_list->clock->type);
> +    /* The active timers list may be modified before the caller uses our
> return +     * 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);
> +        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);
>
>      if (delta <= 0) {
>          return 0;
> @@ -299,9 +322,11 @@ void timer_free(QEMUTimer *ts)
>  /* stop a timer, but do not dealloc it */
>  void timer_del(QEMUTimer *ts)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer **pt, *t;
>
> -    pt = &ts->timer_list->active_timers;
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    pt = &timer_list->active_timers;
>      for(;;) {
>          t = *pt;
>          if (!t)
> @@ -312,18 +337,21 @@ void timer_del(QEMUTimer *ts)
>          }
>          pt = &t->next;
>      }
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
>  }
>
>  /* modify the current timer so that it will be fired when current_time
>     >= expire_time. The corresponding callback will be called. */
>  void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer **pt, *t;
>
>      timer_del(ts);
>
>      /* add the timer in the sorted list */
> -    pt = &ts->timer_list->active_timers;
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    pt = &timer_list->active_timers;
>      for(;;) {
>          t = *pt;
>          if (!timer_expired_ns(t, expire_time)) {
> @@ -334,12 +362,13 @@ void timer_mod_ns(QEMUTimer *ts, int64_t
> expire_time)      ts->expire_time = expire_time;
>      ts->next = *pt;
>      *pt = ts;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
>
>      /* Rearm if necessary  */
> -    if (pt == &ts->timer_list->active_timers) {
> +    if (pt == &timer_list->active_timers) {
>          /* Interrupt execution to force deadline recalculation.  */
> -        qemu_clock_warp(ts->timer_list->clock->type);
> -        timerlist_notify(ts->timer_list);
> +        qemu_clock_warp(timer_list->clock->type);
> +        timerlist_notify(timer_list);
>      }
>  }
>
> @@ -350,13 +379,19 @@ void timer_mod(QEMUTimer *ts, int64_t expire_time)
>
>  bool timer_pending(QEMUTimer *ts)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer *t;
> -    for (t = ts->timer_list->active_timers; t != NULL; t = t->next) {
> +    bool found = false;
> +
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    for (t = timer_list->active_timers; t != NULL; t = t->next) {
>          if (t == ts) {
> -            return true;
> +            found = true;
> +            break;
>          }
>      }
> -    return false;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
> +    return found;
>  }
>
>  bool timer_expired(QEMUTimer *timer_head, int64_t current_time)
> @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
>
>      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);
>              break;
>          }
>          /* remove timer from the list before calling the callback */
>          timer_list->active_timers = ts->next;
>          ts->next = NULL;
> +        qemu_mutex_unlock(&timer_list->active_timers_lock);
>
>          /* run the callback (the timer list can be modified) */
>          ts->cb(ts->opaque);
> --
> 1.8.3.1
>
>

On Mon, Aug 12, 2013 at 8:49 PM, Stefan Hajnoczi <stefanha@redhat.com> wrote:
> Introduce QEMUTimerList->active_timers_lock to protect the linked list
> of active timers.  This allows qemu_timer_mod_ns() to be called from any
> thread.
>
> Note that vm_clock is not thread-safe and its use of
> qemu_clock_has_timers() works fine today but is also not thread-safe.
>
> The purpose of this patch is to eventually let device models set or
> cancel timers from a vcpu thread without holding the global mutex.
>
> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
> ---
>  include/qemu/timer.h | 17 ++++++++++++++
>  qemu-timer.c         | 66 +++++++++++++++++++++++++++++++++++++++++-----------
>  2 files changed, 69 insertions(+), 14 deletions(-)
>
> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> index 829c005..3543b0e 100644
> --- a/include/qemu/timer.h
> +++ b/include/qemu/timer.h
> @@ -114,6 +114,10 @@ static inline int64_t qemu_clock_get_us(QEMUClockType type)
>   * Determines whether a clock's default timer list
>   * has timers attached
>   *
> + * Note that this function should not be used when other threads also access
> + * the timer list.  The return value may be outdated by the time it is acted
> + * upon.
> + *
>   * Returns: true if the clock's default timer list
>   * has timers attached
>   */
> @@ -270,6 +274,10 @@ void timerlist_free(QEMUTimerList *timer_list);
>   *
>   * Determine whether a timer list has active timers
>   *
> + * Note that this function should not be used when other threads also access
> + * the timer list.  The return value may be outdated by the time it is acted
> + * upon.
> + *
>   * Returns: true if the timer list has timers.
>   */
>  bool timerlist_has_timers(QEMUTimerList *timer_list);
> @@ -511,6 +519,9 @@ void timer_free(QEMUTimer *ts);
>   * @ts: the timer
>   *
>   * Delete a timer from the active list.
> + *
> + * This function is thread-safe but the timer and its timer list must not be
> + * freed while this function is running.
>   */
>  void timer_del(QEMUTimer *ts);
>
> @@ -520,6 +531,9 @@ void timer_del(QEMUTimer *ts);
>   * @expire_time: the expiry time in nanoseconds
>   *
>   * Modify a timer to expire at @expire_time
> + *
> + * This function is thread-safe but the timer and its timer list must not be
> + * freed while this function is running.
>   */
>  void timer_mod_ns(QEMUTimer *ts, int64_t expire_time);
>
> @@ -530,6 +544,9 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time);
>   *
>   * Modify a timer to expiry at @expire_time, taking into
>   * account the scale associated with the timer.
> + *
> + * This function is thread-safe but the timer and its timer list must not be
> + * freed while this function is running.
>   */
>  void timer_mod(QEMUTimer *ts, int64_t expire_timer);
>
> diff --git a/qemu-timer.c b/qemu-timer.c
> index 818d235..3a5b46d 100644
> --- a/qemu-timer.c
> +++ b/qemu-timer.c
> @@ -66,6 +66,7 @@ QEMUClock qemu_clocks[QEMU_CLOCK_MAX];
>
>  struct QEMUTimerList {
>      QEMUClock *clock;
> +    QemuMutex active_timers_lock;
>      QEMUTimer *active_timers;
>      QLIST_ENTRY(QEMUTimerList) list;
>      QEMUTimerListNotifyCB *notify_cb;
> @@ -101,6 +102,7 @@ QEMUTimerList *timerlist_new(QEMUClockType type,
>      timer_list->clock = clock;
>      timer_list->notify_cb = cb;
>      timer_list->notify_opaque = opaque;
> +    qemu_mutex_init(&timer_list->active_timers_lock);
>      QLIST_INSERT_HEAD(&clock->timerlists, timer_list, list);
>      return timer_list;
>  }
> @@ -111,6 +113,7 @@ void timerlist_free(QEMUTimerList *timer_list)
>      if (timer_list->clock) {
>          QLIST_REMOVE(timer_list, list);
>      }
> +    qemu_mutex_destroy(&timer_list->active_timers_lock);
>      g_free(timer_list);
>  }
>
> @@ -163,9 +166,17 @@ bool qemu_clock_has_timers(QEMUClockType type)
>
>  bool timerlist_expired(QEMUTimerList *timer_list)
>  {
> -    return (timer_list->active_timers &&
> -            timer_list->active_timers->expire_time <
> -            qemu_clock_get_ns(timer_list->clock->type));
> +    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);
> +        return false;
> +    }
> +    expire_time = timer_list->active_timers->expire_time;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
> +
> +    return expire_time < qemu_clock_get_ns(timer_list->clock->type);
>  }
>
>  bool qemu_clock_expired(QEMUClockType type)
> @@ -182,13 +193,25 @@ bool qemu_clock_expired(QEMUClockType type)
>  int64_t timerlist_deadline_ns(QEMUTimerList *timer_list)
>  {
>      int64_t delta;
> +    int64_t expire_time;
>
> -    if (!timer_list->clock->enabled || !timer_list->active_timers) {
> +    if (!timer_list->clock->enabled) {
>          return -1;
>      }
>
> -    delta = timer_list->active_timers->expire_time -
> -        qemu_clock_get_ns(timer_list->clock->type);
> +    /* The active timers list may be modified before the caller uses our return
> +     * 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);
> +        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);
>
>      if (delta <= 0) {
>          return 0;
> @@ -299,9 +322,11 @@ void timer_free(QEMUTimer *ts)
>  /* stop a timer, but do not dealloc it */
>  void timer_del(QEMUTimer *ts)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer **pt, *t;
>
> -    pt = &ts->timer_list->active_timers;
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    pt = &timer_list->active_timers;
>      for(;;) {
>          t = *pt;
>          if (!t)
> @@ -312,18 +337,21 @@ void timer_del(QEMUTimer *ts)
>          }
>          pt = &t->next;
>      }
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
>  }
>
>  /* modify the current timer so that it will be fired when current_time
>     >= expire_time. The corresponding callback will be called. */
>  void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer **pt, *t;
>
>      timer_del(ts);
>
>      /* add the timer in the sorted list */
> -    pt = &ts->timer_list->active_timers;
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    pt = &timer_list->active_timers;
>      for(;;) {
>          t = *pt;
>          if (!timer_expired_ns(t, expire_time)) {
> @@ -334,12 +362,13 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
>      ts->expire_time = expire_time;
>      ts->next = *pt;
>      *pt = ts;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
>
>      /* Rearm if necessary  */
> -    if (pt == &ts->timer_list->active_timers) {
> +    if (pt == &timer_list->active_timers) {
>          /* Interrupt execution to force deadline recalculation.  */
> -        qemu_clock_warp(ts->timer_list->clock->type);
> -        timerlist_notify(ts->timer_list);
> +        qemu_clock_warp(timer_list->clock->type);
> +        timerlist_notify(timer_list);
>      }
>  }
>
> @@ -350,13 +379,19 @@ void timer_mod(QEMUTimer *ts, int64_t expire_time)
>
>  bool timer_pending(QEMUTimer *ts)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer *t;
> -    for (t = ts->timer_list->active_timers; t != NULL; t = t->next) {
> +    bool found = false;
> +
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    for (t = timer_list->active_timers; t != NULL; t = t->next) {
>          if (t == ts) {
> -            return true;
> +            found = true;
> +            break;
>          }
>      }
> -    return false;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
> +    return found;
>  }
>
>  bool timer_expired(QEMUTimer *timer_head, int64_t current_time)
> @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
>
>      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);
>              break;
>          }
>          /* remove timer from the list before calling the callback */
>          timer_list->active_timers = ts->next;
>          ts->next = NULL;
> +        qemu_mutex_unlock(&timer_list->active_timers_lock);
>
Could we do better than this? lock/unlock around ts->cb always cause extra cost?
Beside this, others seems good.

Regards,
Pingfan
>          /* run the callback (the timer list can be modified) */
>          ts->cb(ts->opaque);
> --
> 1.8.3.1
>
>

On Thu, Aug 15, 2013 at 08:05:11AM +0800, liu ping fan wrote:
> On Mon, Aug 12, 2013 at 8:49 PM, Stefan Hajnoczi <stefanha@redhat.com> wrote:
> > @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
> >
> >      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);
> >              break;
> >          }
> >          /* remove timer from the list before calling the callback */
> >          timer_list->active_timers = ts->next;
> >          ts->next = NULL;
> > +        qemu_mutex_unlock(&timer_list->active_timers_lock);
> >
> Could we do better than this? lock/unlock around ts->cb always cause extra cost?
> Beside this, others seems good.

ts->cb() can do anything.  We need to drop the mutex to prevent
recursive locking.

There is no cheap way to clone the list before the loop (so that we
don't need to hold any lock while iterating), and the list may change
when ts->cb() is called.

Did you have a specific improvement in mind?

Stefan

On Thu, Aug 15, 2013 at 4:01 PM, Stefan Hajnoczi <stefanha@gmail.com> wrote:
> On Thu, Aug 15, 2013 at 08:05:11AM +0800, liu ping fan wrote:
>> On Mon, Aug 12, 2013 at 8:49 PM, Stefan Hajnoczi <stefanha@redhat.com> wrote:
>> > @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
>> >
>> >      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);
>> >              break;
>> >          }
>> >          /* remove timer from the list before calling the callback */
>> >          timer_list->active_timers = ts->next;
>> >          ts->next = NULL;
>> > +        qemu_mutex_unlock(&timer_list->active_timers_lock);
>> >
>> Could we do better than this? lock/unlock around ts->cb always cause extra cost?
>> Beside this, others seems good.
>
> ts->cb() can do anything.  We need to drop the mutex to prevent
> recursive locking.
>
> There is no cheap way to clone the list before the loop (so that we
> don't need to hold any lock while iterating), and the list may change
> when ts->cb() is called.
>
> Did you have a specific improvement in mind?
>
How about new_list for vcpu to add timer, an before walking, splice
the new_list to timer_list?
> Stefan

On Thu, Aug 15, 2013 at 4:22 PM, liu ping fan <qemulist@gmail.com> wrote:
> On Thu, Aug 15, 2013 at 4:01 PM, Stefan Hajnoczi <stefanha@gmail.com> wrote:
>> On Thu, Aug 15, 2013 at 08:05:11AM +0800, liu ping fan wrote:
>>> On Mon, Aug 12, 2013 at 8:49 PM, Stefan Hajnoczi <stefanha@redhat.com> wrote:
>>> > @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
>>> >
>>> >      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);
>>> >              break;
>>> >          }
>>> >          /* remove timer from the list before calling the callback */
>>> >          timer_list->active_timers = ts->next;
>>> >          ts->next = NULL;
>>> > +        qemu_mutex_unlock(&timer_list->active_timers_lock);
>>> >
>>> Could we do better than this? lock/unlock around ts->cb always cause extra cost?
>>> Beside this, others seems good.
>>
>> ts->cb() can do anything.  We need to drop the mutex to prevent
>> recursive locking.
>>
>> There is no cheap way to clone the list before the loop (so that we
>> don't need to hold any lock while iterating), and the list may change
>> when ts->cb() is called.
>>
>> Did you have a specific improvement in mind?
>>
> How about new_list for vcpu to add timer, an before walking, splice
> the new_list to timer_list?
Of course, qemu_mod_timer_ns() should tell the caller, maybe by TLS?
>> Stefan

On 15 Aug 2013, at 09:22, liu ping fan wrote:

> How about new_list for vcpu to add timer, an before walking, splice
> the new_list to timer_list?

If I understand you right, you would have to be careful
any timer routine modified itself or (less likely) any
other timer, as that timer would no longer be on the
timer list, but rather be on the 'walk list'.
There's no problem per se with them being on a new timer
list, but some of them may modify the existing timer
leaving it on the list you are walking, and some might
put it on the timerlist associated with the clock. I'm
not sure things expect timers to move between lists.
Whatever, that means you can't call the callback with
the mutex held in either the walk list or the timer list.

I believe it's reasonably common for timers to call
timer_mod on themselves to get them to fire again.

The best I can do is simply take the lock, examine the
timer at the head of the list (always), remove the
timer from the active list, unlock, and call the callback.
That's exactly what the patch does.


(side note: you can't just splice the lists because they
have to be ordered)

On Thu, Aug 15, 2013 at 04:24:57PM +0800, liu ping fan wrote:
> On Thu, Aug 15, 2013 at 4:22 PM, liu ping fan <qemulist@gmail.com> wrote:
> > On Thu, Aug 15, 2013 at 4:01 PM, Stefan Hajnoczi <stefanha@gmail.com> wrote:
> >> On Thu, Aug 15, 2013 at 08:05:11AM +0800, liu ping fan wrote:
> >>> On Mon, Aug 12, 2013 at 8:49 PM, Stefan Hajnoczi <stefanha@redhat.com> wrote:
> >>> > @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
> >>> >
> >>> >      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);
> >>> >              break;
> >>> >          }
> >>> >          /* remove timer from the list before calling the callback */
> >>> >          timer_list->active_timers = ts->next;
> >>> >          ts->next = NULL;
> >>> > +        qemu_mutex_unlock(&timer_list->active_timers_lock);
> >>> >
> >>> Could we do better than this? lock/unlock around ts->cb always cause extra cost?
> >>> Beside this, others seems good.
> >>
> >> ts->cb() can do anything.  We need to drop the mutex to prevent
> >> recursive locking.
> >>
> >> There is no cheap way to clone the list before the loop (so that we
> >> don't need to hold any lock while iterating), and the list may change
> >> when ts->cb() is called.
> >>
> >> Did you have a specific improvement in mind?
> >>
> > How about new_list for vcpu to add timer, an before walking, splice
> > the new_list to timer_list?
> Of course, qemu_mod_timer_ns() should tell the caller, maybe by TLS?

The common case is that we only check the first timer in
->active_timers.  Usually the first timer has not expired yet and we
return; the lock was taken once only.

I'm not sure it's worth complicating the case where we iterate multiple
times.

Stefan

Il 12/08/2013 14:49, Stefan Hajnoczi ha scritto:
> Introduce QEMUTimerList->active_timers_lock to protect the linked list
> of active timers.  This allows qemu_timer_mod_ns() to be called from any
> thread.
> 
> Note that vm_clock is not thread-safe and its use of
> qemu_clock_has_timers() works fine today but is also not thread-safe.
> 
> The purpose of this patch is to eventually let device models set or
> cancel timers from a vcpu thread without holding the global mutex.
> 
> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
> ---
>  include/qemu/timer.h | 17 ++++++++++++++
>  qemu-timer.c         | 66 +++++++++++++++++++++++++++++++++++++++++-----------
>  2 files changed, 69 insertions(+), 14 deletions(-)
> 
> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> index 829c005..3543b0e 100644
> --- a/include/qemu/timer.h
> +++ b/include/qemu/timer.h
> @@ -114,6 +114,10 @@ static inline int64_t qemu_clock_get_us(QEMUClockType type)
>   * Determines whether a clock's default timer list
>   * has timers attached
>   *
> + * Note that this function should not be used when other threads also access
> + * the timer list.  The return value may be outdated by the time it is acted
> + * upon.
> + *
>   * Returns: true if the clock's default timer list
>   * has timers attached
>   */
> @@ -270,6 +274,10 @@ void timerlist_free(QEMUTimerList *timer_list);
>   *
>   * Determine whether a timer list has active timers
>   *
> + * Note that this function should not be used when other threads also access
> + * the timer list.  The return value may be outdated by the time it is acted
> + * upon.
> + *
>   * Returns: true if the timer list has timers.
>   */
>  bool timerlist_has_timers(QEMUTimerList *timer_list);
> @@ -511,6 +519,9 @@ void timer_free(QEMUTimer *ts);
>   * @ts: the timer
>   *
>   * Delete a timer from the active list.
> + *
> + * This function is thread-safe but the timer and its timer list must not be
> + * freed while this function is running.
>   */
>  void timer_del(QEMUTimer *ts);
>  
> @@ -520,6 +531,9 @@ void timer_del(QEMUTimer *ts);
>   * @expire_time: the expiry time in nanoseconds
>   *
>   * Modify a timer to expire at @expire_time
> + *
> + * This function is thread-safe but the timer and its timer list must not be
> + * freed while this function is running.
>   */
>  void timer_mod_ns(QEMUTimer *ts, int64_t expire_time);
>  
> @@ -530,6 +544,9 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time);
>   *
>   * Modify a timer to expiry at @expire_time, taking into
>   * account the scale associated with the timer.
> + *
> + * This function is thread-safe but the timer and its timer list must not be
> + * freed while this function is running.
>   */
>  void timer_mod(QEMUTimer *ts, int64_t expire_timer);
>  
> diff --git a/qemu-timer.c b/qemu-timer.c
> index 818d235..3a5b46d 100644
> --- a/qemu-timer.c
> +++ b/qemu-timer.c
> @@ -66,6 +66,7 @@ QEMUClock qemu_clocks[QEMU_CLOCK_MAX];
>  
>  struct QEMUTimerList {
>      QEMUClock *clock;
> +    QemuMutex active_timers_lock;
>      QEMUTimer *active_timers;
>      QLIST_ENTRY(QEMUTimerList) list;
>      QEMUTimerListNotifyCB *notify_cb;
> @@ -101,6 +102,7 @@ QEMUTimerList *timerlist_new(QEMUClockType type,
>      timer_list->clock = clock;
>      timer_list->notify_cb = cb;
>      timer_list->notify_opaque = opaque;
> +    qemu_mutex_init(&timer_list->active_timers_lock);
>      QLIST_INSERT_HEAD(&clock->timerlists, timer_list, list);
>      return timer_list;
>  }
> @@ -111,6 +113,7 @@ void timerlist_free(QEMUTimerList *timer_list)
>      if (timer_list->clock) {
>          QLIST_REMOVE(timer_list, list);
>      }
> +    qemu_mutex_destroy(&timer_list->active_timers_lock);
>      g_free(timer_list);
>  }
>  
> @@ -163,9 +166,17 @@ bool qemu_clock_has_timers(QEMUClockType type)
>  
>  bool timerlist_expired(QEMUTimerList *timer_list)
>  {
> -    return (timer_list->active_timers &&
> -            timer_list->active_timers->expire_time <
> -            qemu_clock_get_ns(timer_list->clock->type));
> +    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);
> +        return false;
> +    }
> +    expire_time = timer_list->active_timers->expire_time;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);

Perhaps you can put here a comment similar to the one in
timerlist_deadline_ns?

> +    return expire_time < qemu_clock_get_ns(timer_list->clock->type);
>  }
>  
>  bool qemu_clock_expired(QEMUClockType type)
> @@ -182,13 +193,25 @@ bool qemu_clock_expired(QEMUClockType type)
>  int64_t timerlist_deadline_ns(QEMUTimerList *timer_list)
>  {
>      int64_t delta;
> +    int64_t expire_time;
>  
> -    if (!timer_list->clock->enabled || !timer_list->active_timers) {
> +    if (!timer_list->clock->enabled) {
>          return -1;
>      }
>  
> -    delta = timer_list->active_timers->expire_time -
> -        qemu_clock_get_ns(timer_list->clock->type);
> +    /* The active timers list may be modified before the caller uses our return
> +     * 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);
> +        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);
>  
>      if (delta <= 0) {
>          return 0;
> @@ -299,9 +322,11 @@ void timer_free(QEMUTimer *ts)
>  /* stop a timer, but do not dealloc it */
>  void timer_del(QEMUTimer *ts)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer **pt, *t;
>  
> -    pt = &ts->timer_list->active_timers;
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    pt = &timer_list->active_timers;
>      for(;;) {
>          t = *pt;
>          if (!t)
> @@ -312,18 +337,21 @@ void timer_del(QEMUTimer *ts)
>          }
>          pt = &t->next;
>      }
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
>  }
>  
>  /* modify the current timer so that it will be fired when current_time
>     >= expire_time. The corresponding callback will be called. */
>  void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer **pt, *t;
>  
>      timer_del(ts);
>  
>      /* add the timer in the sorted list */
> -    pt = &ts->timer_list->active_timers;
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    pt = &timer_list->active_timers;
>      for(;;) {
>          t = *pt;
>          if (!timer_expired_ns(t, expire_time)) {
> @@ -334,12 +362,13 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
>      ts->expire_time = expire_time;
>      ts->next = *pt;
>      *pt = ts;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
>  
>      /* Rearm if necessary  */
> -    if (pt == &ts->timer_list->active_timers) {
> +    if (pt == &timer_list->active_timers) {
>          /* Interrupt execution to force deadline recalculation.  */
> -        qemu_clock_warp(ts->timer_list->clock->type);
> -        timerlist_notify(ts->timer_list);
> +        qemu_clock_warp(timer_list->clock->type);
> +        timerlist_notify(timer_list);
>      }
>  }
>  
> @@ -350,13 +379,19 @@ void timer_mod(QEMUTimer *ts, int64_t expire_time)
>  
>  bool timer_pending(QEMUTimer *ts)
>  {
> +    QEMUTimerList *timer_list = ts->timer_list;
>      QEMUTimer *t;
> -    for (t = ts->timer_list->active_timers; t != NULL; t = t->next) {
> +    bool found = false;
> +
> +    qemu_mutex_lock(&timer_list->active_timers_lock);
> +    for (t = timer_list->active_timers; t != NULL; t = t->next) {
>          if (t == ts) {
> -            return true;
> +            found = true;
> +            break;
>          }
>      }
> -    return false;
> +    qemu_mutex_unlock(&timer_list->active_timers_lock);
> +    return found;
>  }
>  
>  bool timer_expired(QEMUTimer *timer_head, int64_t current_time)
> @@ -376,13 +411,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
>  
>      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);
>              break;
>          }
>          /* remove timer from the list before calling the callback */
>          timer_list->active_timers = ts->next;
>          ts->next = NULL;
> +        qemu_mutex_unlock(&timer_list->active_timers_lock);

Here I usually prefer an idiom like

    lock();
    for (;;) {
         ...
         unlock();
         ts->cb(ts->opaque);
         lock();
    }
    unlock();

It makes it a bit easier to avoid exits where the lock is not released.

Paolo

>  
>          /* run the callback (the timer list can be modified) */
>          ts->cb(ts->opaque);
>

Il 15/08/2013 14:00, Stefan Hajnoczi ha scritto:
> The common case is that we only check the first timer in
> ->active_timers.  Usually the first timer has not expired yet and we
> return; the lock was taken once only.
> 
> I'm not sure it's worth complicating the case where we iterate multiple
> times.

I agree.  Later we may try to get creative and optimize the lookup of
the first timer (take the lock zero times instead of once if the first
timer has not expired yet, take the lock once instead of twice if one
timer runs, etc.).  Anything beyond that would be premature.

Paolo