Messages in this thread | | | From | "Huang\, Ying" <> | Subject | Re: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive | Date | Tue, 19 Dec 2017 09:35:26 +0800 |
| |
Vitaly Wool <vitalywool@gmail.com> writes:
> 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);
I think this could be implemented on top of llist, why add it into llist itself?
Best Regards, Huang, Ying
| |