[PATCH/RFC] llist: add llist_[add|del_first]_exclusive

[PATCH/RFC] llist: add llist_[add|del_first]_exclusive

[Vitaly Wool]

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

Re: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive

[Huang, Ying]

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

Re: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive

[Huang, Ying]

Vitaly Wool <vitalywool@gmail.com> writes:

> 2017-12-19 2:35 GMT+01:00 Huang, Ying <ying.huang@intel.com>:
>
>> 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?
>>
>
>
> Could you please elaborate how this would be implemented "on top"?

struct llist_node *my_del_first_exclusive(struct llist_head *head)
{
        struct llist_node *node = llist_del_first(head);

        if (node)
                node->next = LLIST_NODE_UNLISTED;
}

bool my_add_exclusive(struct llist_node *node, struct llist_head *head)
{
        if (node->next != LLIST_NODE_UNLIST)
                return false;
        if (cmpxchg(&node->next, LLIST_NODE_UNLIST, NULL) !=
            LLIST_NODE_UNLIST)
                return false;
        llist_add(node, head);
        return true;
}

Best Regards,
Huang, Ying

Re: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive

[Huang, Ying]

Vitaly Wool <vitalywool@gmail.com> writes:

> 2017-12-20 1:57 GMT+01:00 Huang, Ying <ying.huang@intel.com>:
>
> <snip>
>
>>
>> > Could you please elaborate how this would be implemented "on top"?
>>
>> struct llist_node *my_del_first_exclusive(struct llist_head *head)
>> {
>>         struct llist_node *node = llist_del_first(head);
>>
>>         if (node)
>>                 node->next = LLIST_NODE_UNLISTED;
>> }
>>
>> bool my_add_exclusive(struct llist_node *node, struct llist_head *head)
>> {
>>         if (node->next != LLIST_NODE_UNLIST)
>>                 return false;
>>         if (cmpxchg(&node->next, LLIST_NODE_UNLIST, NULL) !=
>>             LLIST_NODE_UNLIST)
>>                 return false;
>>         llist_add(node, head);
>>         return true;
>> }
>>
>
> That would work, thanks. I'll update the patch.

Is there any other users except your code?  If no, I think it's better
to keep it with its only user instead part of llist library at least for
now.  Because I don't know whether the usage model is popular.

Best Regards,
Huang, Ying

> Thanks,
>    Vitaly

Re: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive

[Huang, Ying]

Vitaly Wool <vitalywool@gmail.com> writes:

> 2017-12-22 14:57 GMT+01:00 Huang, Ying <ying.huang@intel.com>:
>
>> Vitaly Wool <vitalywool@gmail.com> writes:
>>
>> > 2017-12-20 1:57 GMT+01:00 Huang, Ying <ying.huang@intel.com>:
>> >
>> > <snip>
>> >
>> >>
>> >> > Could you please elaborate how this would be implemented "on top"?
>> >>
>> >> struct llist_node *my_del_first_exclusive(struct llist_head *head)
>> >> {
>> >>         struct llist_node *node = llist_del_first(head);
>> >>
>> >>         if (node)
>> >>                 node->next = LLIST_NODE_UNLISTED;
>> >> }
>> >>
>> >> bool my_add_exclusive(struct llist_node *node, struct llist_head *head)
>> >> {
>> >>         if (node->next != LLIST_NODE_UNLIST)
>> >>                 return false;
>> >>         if (cmpxchg(&node->next, LLIST_NODE_UNLIST, NULL) !=
>> >>             LLIST_NODE_UNLIST)
>> >>                 return false;
>> >>         llist_add(node, head);
>> >>         return true;
>> >> }
>> >>
>> >
>> > That would work, thanks. I'll update the patch.
>>
>> Is there any other users except your code?  If no, I think it's better
>> to keep it with its only user instead part of llist library at least for
>> now.  Because I don't know whether the usage model is popular.
>>
>>
>>
> I'm going to come up with a patch to binder that uses these specific
> extensions, so I expect there'll be some users for this.

I think it is better to keep this in binder unless there are other
users.

Best Regards,
Huang, Ying

> Thanks,
>    Vitaly