llist: add llist_[add|del_first]_exclusive
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.
--- include/linux/llist.h | 25 +++++++++++++++++++++++++ lib/llist.c | 29 +++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+)
include/linux/llist.h +25 -0
@@ -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 */
lib/llist.c +29 -0
@@ -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);
Signature · 1 line
2.7.4
Quoted 89 lines · 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_exclusivewould only add a node if it's not already on a list, andllist_del_first_exclusivewill delete the first node off the list and mark it as not being on any list.Signed-off-by Vitaly Wool <[email protected]>--- include/linux/llist.h | 25 +++++++++++++++++++++++++ lib/llist.c | 29 +++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+)include/linux/llist.h +25
-0@@ -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 */ lib/llist.c +19
-0@@ -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.
lib/llist.c struct llist_node *llist_reverse_order(struct llist_node *head) · line 133
Quoted 10 lines
lib/llist.c +10
-0+*/ +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
A message that is not in the archive (sent off-list or not yet received): CAMJBoFOMpL4WarWU7txYiT7cVqRyrNLVqu-GOhEmjoNhPBQ=3w@mail.gmail.com
Quoted 117 lines · Vitaly Wool
2017-12-19 2:35 GMT+01:00 Huang, Ying <[email protected]>:
Quoted 98 lines
Quoted 26 lines · 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_exclusivewould only add a node if it's not already on a list, andllist_del_first_exclusivewill delete the first node off the list and mark it as not being on any list.Signed-off-by Vitaly Wool <[email protected]>--- include/linux/llist.h | 25 +++++++++++++++++++++++++ lib/llist.c | 29 +++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+)include/linux/llist.h +0
-0include/linux/llist.h struct llist_node { · line 75
Quoted 2 lines
include/linux/llist.h +0
-0@@ -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)include/linux/llist.h struct llist_node {
Quoted 4 lines
include/linux/llist.h +3
-0+#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)include/linux/llist.h extern struct llist_node *llist_del_first(struct
Quoted 5 lines
include/linux/llist.h +1
-0+/** * 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);Quoted 13 lines
include/linux/llist.h +10
-0struct 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(include/linux/llist.h extern struct llist_node *llist_del_first(struct llist_head *head);
Quoted 10 lines
include/linux/llist.h +10
-0+ 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*);
lib/llist.c struct llist_node *llist_reverse_order(struct
Quoted 7 lines
include/linux/llist.h +1
-0+#endif /* LLIST_H */ lib/llist.c +0
-0@@ -102,3 +102,32 @@ struct llist_node *llist_reverse_order(struct
llist_node*head)lib/llist.c struct llist_node *llist_reverse_order(struct llist_node *head)
Quoted 12 lines
lib/llist.c +9
-0return 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)
lib/llist.c struct llist_node *llist_reverse_order(struct llist_node *head)
Quoted 6 lines
lib/llist.c +6
-0+{ +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
lib/llist.c struct llist_node *llist_reverse_order(struct llist_node *head)
Quoted 3 lines
lib/llist.c +3
-0+* 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
Quoted 15 lines
lib/llist.c struct llist_node *llist_reverse_order(struct llist_node *head) · line 133
Quoted 11 lines
lib/llist.c +11
-0+* 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?
Quoted 1 line
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
A message that is not in the archive (sent off-list or not yet received): CAMJBoFPt1xXxe5O9uvsLDufs4UHELk3DKPp=MjN5QUQJXUeQHg@mail.gmail.com
Quoted 27 lines · Vitaly Wool
2017-12-20 1:57 GMT+01:00 Huang, Ying <[email protected]>:
<snip>
Quoted 12 lines
Quoted 2 lines
Could you please elaborate how this would be implemented "on top"?
struct
llist_node*my_del_first_exclusive(structllist_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)Quoted 10 lines
{ 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; }
Quoted 1 line
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
Quoted 2 lines
Thanks,
Vitaly
A message that is not in the archive (sent off-list or not yet received): CAMJBoFPYqHgPmu-_RoYN9HLwhDZrgX1XCEtmW6YbCsyb+ZboTA@mail.gmail.com
Quoted 33 lines · Vitaly Wool
2017-12-22 14:57 GMT+01:00 Huang, Ying <[email protected]>:
Quoted 31 lines
Quoted 28 lines · Vitaly Wool
2017-12-20 1:57 GMT+01:00 Huang, Ying <[email protected]>:
<snip>
Quoted 12 lines
Quoted 2 lines
Could you please elaborate how this would be implemented "on top"?
struct
llist_node*my_del_first_exclusive(structllist_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)Quoted 10 lines
{ 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.
Quoted 8 lines
Quoted 6 lines
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
Quoted 2 lines
Thanks,
Vitaly