lkml.org 
[lkml]   [2017]   [Dec]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive
Date
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

\
 
 \ /
  Last update: 2017-12-20 01:57    [W:0.066 / U:2.312 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site