[Qemu-devel] [RFC PATCH 0/3] Timer thread-safety improvements

[Qemu-devel] [RFC PATCH 0/3] Timer thread-safety improvements

[Paolo Bonzini]

These four patches go on top of Stefan's patch introducing a lock for
a timerlist's active timers.  Patches 1 and 2 fix bugs and probably
should simply be squashed into his patch.

Patch 3 is an optimization and code simplification.  It could even go
in _before_ introducing the lock, at Stefan's discretion.

Patch 4 (incomplete and not even compiled) is an optimization that avoids
taking the lock if timerlist_run_timers does not have any timer ready to
fire.  I'm posting it just to share the idea and will resend it with
more documentation later, once the RCU infrastructure is in.

Paolo Bonzini (4):
  qemu-timer: do del+mod atomically
  qemu-timer: fix race conditions on freeing the timer
  qemu-timer: do not take the lock in timer_pending
  qemu-timer: use RCU to preserve the timers during lockless lookup

 qemu-timer.c | 96 +++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 62 insertions(+), 34 deletions(-)

-- 
1.8.3.1

[Qemu-devel] [RFC PATCH 1/3] qemu-timer: do del+mod atomically

[Paolo Bonzini]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-timer.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/qemu-timer.c b/qemu-timer.c
index 04869f4..d650247 100644
--- a/qemu-timer.c
+++ b/qemu-timer.c
@@ -319,13 +319,10 @@ void timer_free(QEMUTimer *ts)
     g_free(ts);
 }
 
-/* stop a timer, but do not dealloc it */
-void timer_del(QEMUTimer *ts)
+static void timer_del_locked(QEMUTimerList *timer_list, QEMUTimer *ts)
 {
-    QEMUTimerList *timer_list = ts->timer_list;
     QEMUTimer **pt, *t;
 
-    qemu_mutex_lock(&timer_list->active_timers_lock);
     pt = &timer_list->active_timers;
     for(;;) {
         t = *pt;
@@ -337,6 +334,15 @@ void timer_del(QEMUTimer *ts)
         }
         pt = &t->next;
     }
+}
+
+/* stop a timer, but do not dealloc it */
+void timer_del(QEMUTimer *ts)
+{
+    QEMUTimerList *timer_list = ts->timer_list;
+
+    qemu_mutex_lock(&timer_list->active_timers_lock);
+    timer_del_locked(timer_list, ts);
     qemu_mutex_unlock(&timer_list->active_timers_lock);
 }
 
@@ -347,10 +353,10 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
     QEMUTimerList *timer_list = ts->timer_list;
     QEMUTimer **pt, *t;
 
-    timer_del(ts);
+    qemu_mutex_lock(&timer_list->active_timers_lock);
+    timer_del_locked(timer_list, ts);
 
     /* add the timer in the sorted list */
-    qemu_mutex_lock(&timer_list->active_timers_lock);
     pt = &timer_list->active_timers;
     for(;;) {
         t = *pt;
-- 
1.8.3.1

[Qemu-devel] [RFC PATCH 2/3] qemu-timer: fix race conditions on freeing the timer

[Paolo Bonzini]

Save the callback and opaque before releasing the mutex, because
the timer could be freed while we do not take the mutex.  Related
to this, ensure the timer is not active before freeing it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-timer.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/qemu-timer.c b/qemu-timer.c
index d650247..aa22801 100644
--- a/qemu-timer.c
+++ b/qemu-timer.c
@@ -316,6 +316,7 @@ void timer_init(QEMUTimer *ts,
 
 void timer_free(QEMUTimer *ts)
 {
+    timer_del(ts);
     g_free(ts);
 }
 
@@ -410,7 +411,9 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
     QEMUTimer *ts;
     int64_t current_time;
     bool progress = false;
-   
+    QEMUTimerCB *cb;
+    void *opaque;
+
     if (!timer_list->clock->enabled) {
         return progress;
     }
@@ -423,13 +426,16 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
             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;
+        cb = ts->cb;
+        opaque = ts->opaque;
         qemu_mutex_unlock(&timer_list->active_timers_lock);
 
         /* run the callback (the timer list can be modified) */
-        ts->cb(ts->opaque);
+        cb(opaque);
         progress = true;
     }
     return progress;
-- 
1.8.3.1

[Qemu-devel] [RFC PATCH 3/3] qemu-timer: do not take the lock in timer_pending

[Paolo Bonzini]

We can deduce the result from expire_time, by making it always -1 if
the timer is not in the active_timers list.  We need to check against
negative times passed to timer_mod_ns; clamping them to zero is not
a problem because the only clock that has a zero value at VM startup
is QEMU_CLOCK_VIRTUAL, and it is monotonic so it cannot be non-zero.
QEMU_CLOCK_HOST, instead, is not monotonic but it cannot go to negative
values unless the host time is seriously screwed up and points to
the 1960s.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-timer.c | 19 +++++--------------
 1 file changed, 5 insertions(+), 14 deletions(-)

diff --git a/qemu-timer.c b/qemu-timer.c
index aa22801..807319a 100644
--- a/qemu-timer.c
+++ b/qemu-timer.c
@@ -312,6 +312,7 @@ void timer_init(QEMUTimer *ts,
     ts->cb = cb;
     ts->opaque = opaque;
     ts->scale = scale;
+    ts->expire_time = -1;
 }
 
 void timer_free(QEMUTimer *ts)
@@ -324,6 +325,7 @@ static void timer_del_locked(QEMUTimerList *timer_list, QEMUTimer *ts)
 {
     QEMUTimer **pt, *t;
 
+    ts->expire_time = -1;
     pt = &timer_list->active_timers;
     for(;;) {
         t = *pt;
@@ -366,7 +368,7 @@ void timer_mod_ns(QEMUTimer *ts, int64_t expire_time)
         }
         pt = &t->next;
     }
-    ts->expire_time = expire_time;
+    ts->expire_time = MAX(expire_time, 0);
     ts->next = *pt;
     *pt = ts;
     qemu_mutex_unlock(&timer_list->active_timers_lock);
@@ -386,19 +388,7 @@ void timer_mod(QEMUTimer *ts, int64_t expire_time)
 
 bool timer_pending(QEMUTimer *ts)
 {
-    QEMUTimerList *timer_list = ts->timer_list;
-    QEMUTimer *t;
-    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) {
-            found = true;
-            break;
-        }
-    }
-    qemu_mutex_unlock(&timer_list->active_timers_lock);
-    return found;
+    return ts->expire_time >= 0;
 }
 
 bool timer_expired(QEMUTimer *timer_head, int64_t current_time)
@@ -430,6 +420,7 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
         /* 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;
         qemu_mutex_unlock(&timer_list->active_timers_lock);
-- 
1.8.3.1

[Qemu-devel] [RFC PATCH 4/3] qemu-timer: use RCU to preserve the timers during lockless lookup

[Paolo Bonzini]

This patch uses RCU to access the active timers list with no lock.  The
access can race with concurrent timer_mod calls, but most of our read-side
critical sections are racy anyway and rely on aio_notify being called
whenever the head of the list changes.  RCU is used simply to ensure that
the timer head does not go away while it is being examined lockless; thus
timer_mod is unchanged and only timer_free has to wait for a grace period.

The only case where we have to take care is in qemu_run_timers.  In this
case, "upgrading" the critical section by taking the mutex is not enough,
because the code relies on the timer being at the head of the list.  Thus,
we fetch the head again after taking the mutex.  The cost is two extra
memory reads for fired timer, and the savings is one mutex lock/unlock
per call to qemu_run_timers, so there is a net advantage.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-timer.c | 49 +++++++++++++++++++++++++++++++++++++------------
 1 file changed, 37 insertions(+), 12 deletions(-)

diff --git a/qemu-timer.c b/qemu-timer.c
index 807319a..9a9f52d 100644
--- a/qemu-timer.c
+++ b/qemu-timer.c
@@ -167,14 +167,16 @@ bool qemu_clock_has_timers(QEMUClockType type)
 bool timerlist_expired(QEMUTimerList *timer_list)
 {
     int64_t expire_time;
+    QEMUTimer *timer;
 
-    qemu_mutex_lock(&timer_list->active_timers_lock);
-    if (!timer_list->active_timers) {
-        qemu_mutex_unlock(&timer_list->active_timers_lock);
+    rcu_read_lock();
+    timer = atomic_rcu_read(&timer_list->active_timers);
+    if (!timer) {
+        rcu_read_unlock();
         return false;
     }
-    expire_time = timer_list->active_timers->expire_time;
-    qemu_mutex_unlock(&timer_list->active_timers_lock);
+    expire_time = timer->expire_time;
+    rcu_read_unlock();
 
     return expire_time < qemu_clock_get_ns(timer_list->clock->type);
 }
@@ -192,6 +195,7 @@ bool qemu_clock_expired(QEMUClockType type)
 
 int64_t timerlist_deadline_ns(QEMUTimerList *timer_list)
 {
+    QEMUTimer *timer;
     int64_t delta;
     int64_t expire_time;
 
@@ -203,13 +207,14 @@ 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_lock();
+    timer = atomic_rcu_read(&timer_list->active_timers);
+    if (!timer) {
+        rcu_read_unlock();
         return -1;
     }
-    expire_time = timer_list->active_timers->expire_time;
-    qemu_mutex_unlock(&timer_list->active_timers_lock);
+    expire_time = timer->expire_time;
+    rcu_read_unlock();
 
     delta = expire_time - qemu_clock_get_ns(timer_list->clock->type);
 
@@ -318,6 +323,8 @@ void timer_init(QEMUTimer *ts,
 void timer_free(QEMUTimer *ts)
 {
     timer_del(ts);
+
+    /* TODO: use call_rcu to free.  */
     g_free(ts);
 }
 
@@ -370,7 +377,7 @@ 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  */
@@ -410,6 +417,22 @@ bool timerlist_run_timers(QEMUTimerList *timer_list)
 
     current_time = qemu_clock_get_ns(timer_list->clock->type);
     for(;;) {
+        /* Check if the head of the list might be expired.  If a
+         * deletion or modification happens concurrently, we will
+         * detect it below with the lock taken.
+         */
+        rcu_read_lock();
+        ts = atomic_rcu_read(&timer_list->active_timers);
+        if (!timer_expired_ns(ts, current_time)) {
+            rcu_read_unlock();
+            break;
+        }
+        rcu_read_unlock();
+
+        /* A timer might be ready to fire.  Check it again with the lock
+         * taken to be safe against concurrent timer_mod; but in the common
+         * case no timer is ready and we can do everything lockless.
+         */
         qemu_mutex_lock(&timer_list->active_timers_lock);
         ts = timer_list->active_timers;
         if (!timer_expired_ns(ts, current_time)) {
-- 
1.8.3.1