Skip to contentSkip to conversation

llist: add llist_[add|del_first]_exclusive

PATCH/RFC Vitaly Wool 2 participants 5 messages Dec 18, 2017 – Dec 28, 2017 3 messages not in the archive Library code

lore
Share & tools
lore
#0 lore raw

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
index 85abc29..5c60e9e 100644
@@ -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
index 7062e93..c85fa6b 100644
@@ -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
#1 lore raw
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_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
index 85abc29..5c60e9e 100644
@@ -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
index 7062e93..c85fa6b 100644
@@ -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

#3 lore raw
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_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 +0 -0
index 85abc29..5c60e9e 100644

include/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 -0
 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(

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
index 7062e93..c85fa6b 100644
@@ -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 -0
      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)

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

#5 lore raw
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(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)

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

#7 lore raw
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(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)

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