From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758384AbdLROq5 (ORCPT ); Mon, 18 Dec 2017 09:46:57 -0500 Received: from mail-lf0-f66.google.com ([209.85.215.66]:32835 "EHLO mail-lf0-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752688AbdLROqz (ORCPT ); Mon, 18 Dec 2017 09:46:55 -0500 X-Google-Smtp-Source: ACJfBovKPa7QC22FdEGRDBAFlT9hyb/6sJZixCFJfdpJXMRss43ieWu9OwUMUGn6k34paV9gpEtGgQ== Date: Mon, 18 Dec 2017 15:46:51 +0100 From: Vitaly Wool To: linux-kernel@vger.kernel.org, Huang Ying Cc: Oleksiy.Avramchenko@sony.com Subject: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive Message-Id: <20171218154651.777fb889c34259799bef3024@gmail.com> X-Mailer: Sylpheed 3.4.1 (GTK+ 2.24.23; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org It sometimes is necessary to be able to be able to use llist in the following manner: if (node_unlisted(node)) llst_add(node, list); i. e. only add a node to the list if it's not already on a list. This is not possible without taking locks because otherwise there's an obvious race between the check and the addition. This patch adds the routine to add a node only if it is not on any list that is lockless and race free as long as there's only one consumer. That is, llist_add_exclusive would only add a node if it's not already on a list, and llist_del_first_exclusive will delete the first node off the list and mark it as not being on any list. Signed-off-by: Vitaly Wool --- include/linux/llist.h | 25 +++++++++++++++++++++++++ lib/llist.c | 29 +++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+) diff --git a/include/linux/llist.h b/include/linux/llist.h index 85abc29..5c60e9e 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -74,6 +74,10 @@ struct llist_node { #define LLIST_HEAD_INIT(name) { NULL } #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) +#define LLIST_NODE_UNLISTED ((void *)(-1L)) +#define LLIST_NODE_INIT(name) { LLIST_NODE_UNLISTED } +#define LLIST_NODE(name) struct llist_node name = LLIST_NODE_INIT(name) + /** * init_llist_head - initialize lock-less list head * @head: the head for your lock-less list @@ -238,4 +242,25 @@ extern struct llist_node *llist_del_first(struct llist_head *head); struct llist_node *llist_reverse_order(struct llist_node *head); +/** + * llist_del_first_exclusive - delete the first entry of lock-less list + * and make sure its ->next is NULL + * @head: the head for your lock-less list + * + * If list is empty, return NULL, otherwise, return the first entry + * deleted, this is the newest added one. + * + */ +static inline struct llist_node *llist_del_first_exclusive( + struct llist_head *head) +{ + struct llist_node *node = llist_del_first(head); + + if (READ_ONCE(node)) + smp_store_release(&node->next, LLIST_NODE_UNLISTED); + return node; +} + +extern bool llist_add_exclusive(struct llist_node *, struct llist_head *); + #endif /* LLIST_H */ diff --git a/lib/llist.c b/lib/llist.c index 7062e93..c85fa6b 100644 --- a/lib/llist.c +++ b/lib/llist.c @@ -102,3 +102,32 @@ struct llist_node *llist_reverse_order(struct llist_node *head) return new_head; } EXPORT_SYMBOL_GPL(llist_reverse_order); + +/** + * llist_add_exclusive - add a node only if its ->next is NULL + * @node: the node to be added + * @head: the head for your lock-less list + * + * Return true if the node was added, or false otherwise. + */ +bool llist_add_exclusive(struct llist_node *node, struct llist_head *head) +{ + struct llist_node *next = LLIST_NODE_UNLISTED; + struct llist_node *entry, *new_next; + + /* + * if new_next is next (== LLIST_NODE_UNLISTED) on the first run, we + * get exclusive access to this node as long as others use + * llist_add_safe too. + * Then false can be returned no more and we'll loop until we get the + * stuff right. + */ + do { + entry = READ_ONCE(head->first); + if ((new_next = cmpxchg(&node->next, next, entry)) != next) + return false; + next = entry; + } while (cmpxchg(&head->first, entry, node) != entry); + return true; +} +EXPORT_SYMBOL_GPL(llist_add_exclusive); -- 2.7.4