From patchwork Tue Oct 30 16:04:36 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Paul E. McKenney" X-Patchwork-Id: 12577 Return-Path: X-Original-To: patchwork@peony.canonical.com Delivered-To: patchwork@peony.canonical.com Received: from fiordland.canonical.com (fiordland.canonical.com [91.189.94.145]) by peony.canonical.com (Postfix) with ESMTP id 8395E23FB0 for ; Tue, 30 Oct 2012 16:05:43 +0000 (UTC) Received: from mail-ia0-f180.google.com (mail-ia0-f180.google.com [209.85.210.180]) by fiordland.canonical.com (Postfix) with ESMTP id 9FC79A18FD8 for ; Tue, 30 Oct 2012 16:05:42 +0000 (UTC) Received: by mail-ia0-f180.google.com with SMTP id f6so284179iag.11 for ; Tue, 30 Oct 2012 09:05:42 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-forwarded-to:x-forwarded-for:delivered-to:received-spf:from:to:cc :subject:date:message-id:x-mailer:in-reply-to:references :x-content-scanned:x-cbid:x-gm-message-state; bh=RpeeYxKyYNqLADp5U3cRyqCexf6k/YmTD1du1ScDwsw=; b=C+bTbQ1Mrcl0w8q9JEbtPHSlhzgWiOomum8lYnL5bY1gXpXY2YLKljLmihVTd1Yl8D uDh6xzcND8dNIUTLAAwq9+Aiqocl1ijoRRgppOE7ANNoNdHWhDsICUGU9EyiUiJ7SRAf 8YhvMXVlKoxfkOQ8bEA6eRNVVqGdSJXUPurwrr9EOPtwfYTA/usk4iBqUjgrXiUU4zqQ Svd++Ch02gZ136yz0uNidlka7VPiaUQwJyDkNH5xUOWvDHf/YYYFftfbGoozHH4/x8EV ikAGkY/bQc9ZL2HZtWwwcjTtRelLlQ5TKTGsUXPi+SyHNM9u/qNuY+/+w6B5VxHbDRMr cbwg== Received: by 10.50.161.169 with SMTP id xt9mr1888220igb.62.1351613141955; Tue, 30 Oct 2012 09:05:41 -0700 (PDT) X-Forwarded-To: linaro-patchwork@canonical.com X-Forwarded-For: patch@linaro.org linaro-patchwork@canonical.com Delivered-To: patches@linaro.org Received: by 10.50.67.148 with SMTP id n20csp439802igt; Tue, 30 Oct 2012 09:05:41 -0700 (PDT) Received: by 10.42.104.208 with SMTP id s16mr19110745ico.15.1351613141086; Tue, 30 Oct 2012 09:05:41 -0700 (PDT) Received: from e7.ny.us.ibm.com (e7.ny.us.ibm.com. [32.97.182.137]) by mx.google.com with ESMTPS id nu6si1106388icb.68.2012.10.30.09.05.40 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 30 Oct 2012 09:05:41 -0700 (PDT) Received-SPF: pass (google.com: domain of paulmck@linux.vnet.ibm.com designates 32.97.182.137 as permitted sender) client-ip=32.97.182.137; Authentication-Results: mx.google.com; spf=pass (google.com: domain of paulmck@linux.vnet.ibm.com designates 32.97.182.137 as permitted sender) smtp.mail=paulmck@linux.vnet.ibm.com Received: from /spool/local by e7.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 30 Oct 2012 12:05:39 -0400 Received: from d01dlp02.pok.ibm.com (9.56.250.167) by e7.ny.us.ibm.com (192.168.1.107) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Tue, 30 Oct 2012 12:05:21 -0400 Received: from d01relay03.pok.ibm.com (d01relay03.pok.ibm.com [9.56.227.235]) by d01dlp02.pok.ibm.com (Postfix) with ESMTP id 31BBA6E808D for ; Tue, 30 Oct 2012 12:05:18 -0400 (EDT) Received: from d03av01.boulder.ibm.com (d03av01.boulder.ibm.com [9.17.195.167]) by d01relay03.pok.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q9UG5HpH157628 for ; Tue, 30 Oct 2012 12:05:17 -0400 Received: from d03av01.boulder.ibm.com (loopback [127.0.0.1]) by d03av01.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id q9UG4qv6017850 for ; Tue, 30 Oct 2012 10:04:54 -0600 Received: from paulmck-ThinkPad-W500 (sig-9-77-143-103.mts.ibm.com [9.77.143.103]) by d03av01.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id q9UG4eMo016054; Tue, 30 Oct 2012 10:04:41 -0600 Received: by paulmck-ThinkPad-W500 (Postfix, from userid 1000) id DE7DDEBED7; Tue, 30 Oct 2012 09:04:38 -0700 (PDT) From: "Paul E. McKenney" To: linux-kernel@vger.kernel.org Cc: mingo@elte.hu, laijs@cn.fujitsu.com, dipankar@in.ibm.com, akpm@linux-foundation.org, mathieu.desnoyers@polymtl.ca, josh@joshtriplett.org, niv@us.ibm.com, tglx@linutronix.de, peterz@infradead.org, rostedt@goodmis.org, Valdis.Kletnieks@vt.edu, dhowells@redhat.com, eric.dumazet@gmail.com, darren@dvhart.com, fweisbec@gmail.com, sbw@mit.edu, patches@linaro.org, "Paul E. McKenney" Subject: [PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms Date: Tue, 30 Oct 2012 09:04:36 -0700 Message-Id: <1351613076-22022-4-git-send-email-paulmck@linux.vnet.ibm.com> X-Mailer: git-send-email 1.7.8 In-Reply-To: <1351613076-22022-1-git-send-email-paulmck@linux.vnet.ibm.com> References: <20121030160350.GA21837@linux.vnet.ibm.com> <1351613076-22022-1-git-send-email-paulmck@linux.vnet.ibm.com> X-Content-Scanned: Fidelis XPS MAILER x-cbid: 12103016-5806-0000-0000-00001B33E60D X-Gm-Message-State: ALoCoQlC4eJXLSwGAGAu7MR+k+OMhf2Z2E7HnQ5SHuV+Fxj68NVdyh0RS7MWg5VW02P3m2YyJ0Oe From: "Paul E. McKenney" The approach for mixing RCU and reference counting listed in the RCU documentation only describes one possible approach. This approach can result in failure on the read side, which is nice if you want fresh data, but not so good if you want simple code. This commit therefore adds two additional approaches that feature unconditional reference-count acquisition by RCU readers. These approaches are very similar to that used in the security code. Signed-off-by: Paul E. McKenney --- Documentation/RCU/rcuref.txt | 61 ++++++++++++++++++++++++++++++++++++++++- 1 files changed, 59 insertions(+), 2 deletions(-) diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt index 4202ad0..99ca662 100644 --- a/Documentation/RCU/rcuref.txt +++ b/Documentation/RCU/rcuref.txt @@ -20,7 +20,7 @@ release_referenced() delete() { { ... write_lock(&list_lock); atomic_dec(&el->rc, relfunc) ... - ... delete_element + ... remove_element } write_unlock(&list_lock); ... if (atomic_dec_and_test(&el->rc)) @@ -52,7 +52,7 @@ release_referenced() delete() { { ... spin_lock(&list_lock); if (atomic_dec_and_test(&el->rc)) ... - call_rcu(&el->head, el_free); delete_element + call_rcu(&el->head, el_free); remove_element ... spin_unlock(&list_lock); } ... if (atomic_dec_and_test(&el->rc)) @@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the update (write) stream. In such cases, atomic_inc_not_zero() might be overkill, since we hold the update-side spinlock. One might instead use atomic_inc() in such cases. + +It is not always convenient to deal with "FAIL" in the +search_and_reference() code path. In such cases, the +atomic_dec_and_test() may be moved from delete() to el_free() +as follows: + +1. 2. +add() search_and_reference() +{ { + alloc_object rcu_read_lock(); + ... search_for_element + atomic_set(&el->rc, 1); atomic_inc(&el->rc); + spin_lock(&list_lock); ... + + add_element rcu_read_unlock(); + ... } + spin_unlock(&list_lock); 4. +} delete() +3. { +release_referenced() spin_lock(&list_lock); +{ ... + ... remove_element + if (atomic_dec_and_test(&el->rc)) spin_unlock(&list_lock); + kfree(el); ... + ... call_rcu(&el->head, el_free); +} ... +5. } +void el_free(struct rcu_head *rhp) +{ + release_referenced(); +} + +The key point is that the initial reference added by add() is not removed +until after a grace period has elapsed following removal. This means that +search_and_reference() cannot find this element, which means that the value +of el->rc cannot increase. Thus, once it reaches zero, there are no +readers that can or ever will be able to reference the element. The +element can therefore safely be freed. This in turn guarantees that if +any reader finds the element, that reader may safely acquire a reference +without checking the value of the reference counter. + +In cases where delete() can sleep, synchronize_rcu() can be called from +delete(), so that el_free() can be subsumed into delete as follows: + +4. +delete() +{ + spin_lock(&list_lock); + ... + remove_element + spin_unlock(&list_lock); + ... + synchronize_rcu(); + if (atomic_dec_and_test(&el->rc)) + kfree(el); + ... +}