From: Vitaly Wool <vitalywool@gmail.com>
To: linux-kernel@vger.kernel.org, Huang Ying <ying.huang@intel.com>
Cc: Oleksiy.Avramchenko@sony.com
Subject: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive
Date: Mon, 18 Dec 2017 15:46:51 +0100 [thread overview]
Message-ID: <20171218154651.777fb889c34259799bef3024@gmail.com> (raw)
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 <vitaly.vul@sony.com>
---
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
next reply other threads:[~2017-12-18 14:46 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-12-18 14:46 Vitaly Wool [this message]
2017-12-19 1:35 ` [PATCH/RFC] llist: add llist_[add|del_first]_exclusive Huang, Ying
[not found] ` <CAMJBoFOMpL4WarWU7txYiT7cVqRyrNLVqu-GOhEmjoNhPBQ=3w@mail.gmail.com>
2017-12-20 0:57 ` Huang, Ying
[not found] ` <CAMJBoFPt1xXxe5O9uvsLDufs4UHELk3DKPp=MjN5QUQJXUeQHg@mail.gmail.com>
2017-12-22 13:57 ` Huang, Ying
[not found] ` <CAMJBoFPYqHgPmu-_RoYN9HLwhDZrgX1XCEtmW6YbCsyb+ZboTA@mail.gmail.com>
2017-12-28 0:47 ` Huang, Ying
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171218154651.777fb889c34259799bef3024@gmail.com \
--to=vitalywool@gmail.com \
--cc=Oleksiy.Avramchenko@sony.com \
--cc=linux-kernel@vger.kernel.org \
--cc=ying.huang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).