Vitaly Wool <vitalyw...@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....@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
