From patchwork Mon Apr 23 16:42:24 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: 8053 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 61EEF23E22 for ; Mon, 23 Apr 2012 16:43:08 +0000 (UTC) Received: from mail-yw0-f52.google.com (mail-yw0-f52.google.com [209.85.213.52]) by fiordland.canonical.com (Postfix) with ESMTP id 148D1A181B8 for ; Mon, 23 Apr 2012 16:43:07 +0000 (UTC) Received: by yhpp61 with SMTP id p61so7768936yhp.11 for ; Mon, 23 Apr 2012 09:43:07 -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=ziXXWRvVQgsC1715I8iieFrD1obwgy4p7NdMI4oMefY=; b=iu+kqNdnvq2zjFitdMWy5Rsgrt9eqHmb7e4i6CERhRNVCaIHso3bTbpFNSG0uGuHvb h9ZiDx7JWpf+HQHZfNnjIwpx9fkEpIPA8zt8UStkcD+Fb9ri12Fquve1gymA4CVqColt bGSnwa9yAd7lkMvhKZTQwjYNkMMmMO3KvZ6tmCGtdn+PJ484jrk77phV349QtpIj1JE9 WiYsuh/7GslgrM2qwR/sQRBm1NX15QvoUqWy22gBxfmUtXvFscMGhHZNOWaEeqK4EDB4 2XRYbftKE9Fav+9XY63o3T3Xge8VI3wD5oWy4GSn/xjBaa2QJxjKx3BYgX6ZdVvVT7Uf 6G9g== Received: by 10.50.193.199 with SMTP id hq7mr7008279igc.49.1335199387179; Mon, 23 Apr 2012 09:43:07 -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.231.137.198 with SMTP id x6csp125371ibt; Mon, 23 Apr 2012 09:43:06 -0700 (PDT) Received: by 10.182.54.114 with SMTP id i18mr23971872obp.49.1335199385382; Mon, 23 Apr 2012 09:43:05 -0700 (PDT) Received: from e33.co.us.ibm.com (e33.co.us.ibm.com. [32.97.110.151]) by mx.google.com with ESMTPS id g3si2132878obz.18.2012.04.23.09.43.05 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 23 Apr 2012 09:43:05 -0700 (PDT) Received-SPF: pass (google.com: domain of paulmck@linux.vnet.ibm.com designates 32.97.110.151 as permitted sender) client-ip=32.97.110.151; Authentication-Results: mx.google.com; spf=pass (google.com: domain of paulmck@linux.vnet.ibm.com designates 32.97.110.151 as permitted sender) smtp.mail=paulmck@linux.vnet.ibm.com Received: from /spool/local by e33.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Mon, 23 Apr 2012 10:43:03 -0600 Received: from d03dlp03.boulder.ibm.com (9.17.202.179) by e33.co.us.ibm.com (192.168.1.133) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Mon, 23 Apr 2012 10:42:44 -0600 Received: from d03relay02.boulder.ibm.com (d03relay02.boulder.ibm.com [9.17.195.227]) by d03dlp03.boulder.ibm.com (Postfix) with ESMTP id E6B8519D8052 for ; Mon, 23 Apr 2012 10:42:30 -0600 (MDT) Received: from d03av01.boulder.ibm.com (d03av01.boulder.ibm.com [9.17.195.167]) by d03relay02.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q3NGgWXv054072 for ; Mon, 23 Apr 2012 10:42:34 -0600 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 q3NGgUgb018651 for ; Mon, 23 Apr 2012 10:42:31 -0600 Received: from paulmck-ThinkPad-W500 ([9.47.24.152]) by d03av01.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id q3NGgT7D018617; Mon, 23 Apr 2012 10:42:29 -0600 Received: by paulmck-ThinkPad-W500 (Postfix, from userid 1000) id 7B2E5E5260; Mon, 23 Apr 2012 09:42:29 -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, patches@linaro.org, Michel Machado , "Paul E. McKenney" Subject: [PATCH RFC tip/core/rcu 3/6] rcu: Replace list_first_entry_rcu() with list_first_or_null_rcu() Date: Mon, 23 Apr 2012 09:42:24 -0700 Message-Id: <1335199347-13926-3-git-send-email-paulmck@linux.vnet.ibm.com> X-Mailer: git-send-email 1.7.8 In-Reply-To: <1335199347-13926-1-git-send-email-paulmck@linux.vnet.ibm.com> References: <20120423164159.GA13819@linux.vnet.ibm.com> <1335199347-13926-1-git-send-email-paulmck@linux.vnet.ibm.com> X-Content-Scanned: Fidelis XPS MAILER x-cbid: 12042316-2398-0000-0000-000006097595 X-Gm-Message-State: ALoCoQkruO0GtshbU25d296rbX6MAb1LpYuE1PQzcAzA77c/oqiv9uQsgJdfctCOstjChK/+tJo+ From: Michel Machado The list_first_entry_rcu() macro is inherently unsafe because it cannot be applied to an empty list. But because RCU readers do not exclude updaters, a list might become empty between the time that list_empty() claimed it was non-empty and the time that list_first_entry_rcu() is invoked. Therefore, the list_empty() test cannot be separated from the list_first_entry_rcu() call. This commit therefore combines these to macros to create a new list_first_or_null_rcu() macro that replaces the old (and unsafe) list_first_entry_rcu() macro. This patch incorporates Paul's review comments on the previous version of this patch available here: https://lkml.org/lkml/2012/4/2/536 This patch cannot break any upstream code because list_first_entry_rcu() is not being used anywhere in the kernel (tested with grep(1)), and any external code using it is probably broken as a result of using it. Signed-off-by: Michel Machado CC: "Paul E. McKenney" CC: Dipankar Sarma Signed-off-by: Paul E. McKenney --- include/linux/rculist.h | 33 +++++++++++++++++++++++++++++---- 1 files changed, 29 insertions(+), 4 deletions(-) diff --git a/include/linux/rculist.h b/include/linux/rculist.h index a20c050..e0f0fab 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -233,18 +233,43 @@ static inline void list_splice_init_rcu(struct list_head *list, }) /** - * list_first_entry_rcu - get the first element from a list + * Where are list_empty_rcu() and list_first_entry_rcu()? + * + * Implementing those functions following their counterparts list_empty() and + * list_first_entry() is not advisable because they lead to subtle race + * conditions as the following snippet shows: + * + * if (!list_empty_rcu(mylist)) { + * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member); + * do_something(bar); + * } + * + * The list may not be empty when list_empty_rcu checks it, but it may be when + * list_first_entry_rcu rereads the ->next pointer. + * + * Rereading the ->next pointer is not a problem for list_empty() and + * list_first_entry() because they would be protected by a lock that blocks + * writers. + * + * See list_first_or_null_rcu for an alternative. + */ + +/** + * list_first_or_null_rcu - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. * - * Note, that list is expected to be not empty. + * Note that if the list is empty, it returns NULL. * * This primitive may safely run concurrently with the _rcu list-mutation * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). */ -#define list_first_entry_rcu(ptr, type, member) \ - list_entry_rcu((ptr)->next, type, member) +#define list_first_or_null_rcu(ptr, type, member) \ + ({struct list_head *__ptr = (ptr); \ + struct list_head __rcu *__next = list_next_rcu(__ptr); \ + likely(__ptr != __next) ? container_of(__next, type, member) : NULL; \ + }) /** * list_for_each_entry_rcu - iterate over rcu list of given type