From patchwork Thu Aug 29 12:31:02 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 270805 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id AF0622C00A1 for ; Thu, 29 Aug 2013 22:33:39 +1000 (EST) Received: from localhost ([::1]:42878 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VF1Pt-0006mf-Qs for incoming@patchwork.ozlabs.org; Thu, 29 Aug 2013 08:33:37 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57750) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VF1Nw-00040M-Bv for qemu-devel@nongnu.org; Thu, 29 Aug 2013 08:31:44 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VF1Nm-0002HW-5f for qemu-devel@nongnu.org; Thu, 29 Aug 2013 08:31:36 -0400 Received: from mail-ea0-x22a.google.com ([2a00:1450:4013:c01::22a]:42002) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VF1Nl-0002Gp-DR for qemu-devel@nongnu.org; Thu, 29 Aug 2013 08:31:25 -0400 Received: by mail-ea0-f170.google.com with SMTP id h14so207302eak.29 for ; Thu, 29 Aug 2013 05:31:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=XuxU9QvDU3lYnCkHGNbcZRVD5lHne9vSpQGug3QlQUI=; b=R5rjCfyUkIHCBoQ2KOfcRTdlb70PiFGkgZATo1oUlCtqR4EiW7gACeQE3o62KTEgA0 moYszyX0ZZ4QuDrxLKEcNUOLo6RCSOXDYljWJaRAb3VZybeHZDnZPQ5kxGMCovwpxNH/ MSZZZucF2WfdvdHT1w4c8Z3IPCFzUpz2yUkhCvNUvuB53Xd8O41Wd0lKZUrLIF/jG/rv vhEY3Zmsm2Gw4IPqaWfm8KQv4u8I2bGtg5aRp7dVwJDjuaomhl3x3nIOS9Ih6iJ9vINk qBiwobdn3/hdFDx+J7x9fKYcsmYEaAMhE87uCvlL71CLZfGTYCU/HI7fm0koAsf7Bo5f hMwQ== X-Received: by 10.14.39.9 with SMTP id c9mr3124075eeb.68.1377779484484; Thu, 29 Aug 2013 05:31:24 -0700 (PDT) Received: from yakj.usersys.redhat.com (nat-pool-mxp-t.redhat.com. [209.132.186.18]) by mx.google.com with ESMTPSA id i1sm45727875eeg.0.1969.12.31.16.00.00 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Thu, 29 Aug 2013 05:31:23 -0700 (PDT) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Thu, 29 Aug 2013 14:31:02 +0200 Message-Id: <1377779462-24383-5-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1377779462-24383-1-git-send-email-pbonzini@redhat.com> References: <1377779462-24383-1-git-send-email-pbonzini@redhat.com> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4013:c01::22a Cc: qemulist@gmail.com, stefanha@redhat.com Subject: [Qemu-devel] [RFC PATCH 4/3] qemu-timer: use RCU to preserve the timers during lockless lookup X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org 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 --- 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)) {