Vitaly Wool <vitalyw...@gmail.com> writes: > 2017-12-19 2:35 GMT+01:00 Huang, Ying <ying.hu...@intel.com>: > >> 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? >> > > > 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