llist: add llist_[add|del_first]_exclusive
PATCH v2 1/1 llist: add llist_[add|del_first]_exclusive
It sometimes is necessary to be able to be able to use llist in the following manner:
Quoted 2 lines
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 Vul <[email protected]>
--- include/linux/llist.h | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+)
include/linux/llist.h +47 -0
@@ -69,6 +69,15 @@ 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) + +static inline void INIT_LLIST_NODE (struct llist_node *node) +{ +WRITE_ONCE (node->next,LLIST_NODE_UNLISTED ); +} +/** * init_llist_head - initialize lock-less list head * @head: the head for your lock-less list
@@ -197,4 +206,42 @@ 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 it's marked as UNLISTED +* @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; +} + + +/** +* llist_add_exclusive - add a node only if it's not on any list +(i. e. marked as UNLISTED) +* @node: the node to be added +* @head: the head for your lock-less list +* +* Return true if the node was added, or false otherwise. +*/ +static inline bool llist_add_exclusive (struct llist_node *node, +struct llist_head *head) +{ +if (cmpxchg (&node->next,LLIST_NODE_UNLISTED ,NULL ) != +LLIST_NODE_UNLISTED ) +return false; + +llist_add (node, head); +return true; +}#endif /* LLIST_H */
Signature · 1 line
2.7.4