Skip to contentSkip to conversation

Query on the rculist

DISCUSSION Mathieu Desnoyers 3 participants 4 messages Jan 21, 2013 – Jan 24, 2013 4 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 9 lines · * Liu Yuan ([email protected]) wrote:

Hi List,

I noticed that there are just few functions suffixed with rcu for
rculist. And from the source of Linux kernel rculist, I came up with some comments saying that list_empty_rcu() can be simply achieved by calling list_empty(). Is this true to urcu too? My questions is, are following equivalents true?

list_empty_rcu -> list_empty

Yes.

Quoted 1 line

list_del_init_rcu -> list_del_init

No.

Quoted 2 lines

If there are more equivalents, please show light on it.

I will prepare a patch to extend and document the list and rculist APIs. Your feedback is welcome.

Thanks!

Mathieu

Quoted 3 lines

Thanks,
Yuan

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20130121141645.GB31140@Krystal

#3 lore raw
Quoted 9 lines · Mathieu Desnoyers
Quoted 8 lines · * Liu Yuan ([email protected]) wrote:

Hi List,

I noticed that there are just few functions suffixed with rcu for
rculist. And from the source of Linux kernel rculist, I came up with some comments saying that list_empty_rcu() can be simply achieved by calling list_empty(). Is this true to urcu too? My questions is, are following equivalents true?

Quoted 7 lines
Quoted 1 line
   list_empty_rcu -> list_empty

Yes.

Quoted 1 line
   list_del_init_rcu -> list_del_init

No.

Add a trivial comment.

There is no list_del_init_rcu(), "init" hurts "rcu".
If you need a re-initialized object after deletion, you should use synchronzie_rcu():

list_del_rcu();
synchronize_rcu();
CDS_INIT_LIST_HEAD();

Quoted 15 lines
Quoted 3 lines

If there are more equivalents, please show light on it.

I will prepare a patch to extend and document the list and rculist APIs. Your feedback is welcome.

Thanks!

Mathieu

Quoted 3 lines

Thanks,
Yuan

_______________________________________________
lttng-dev mailing list
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

A message that is not in the archive (sent off-list or not yet received): [email protected]

#5 lore raw
Quoted 9 lines · Lai Jiangshan

Add a trivial comment.

There is no list_del_init_rcu(), "init" hurts "rcu".
If you need a re-initialized object after deletion, you should use synchronzie_rcu():

list_del_rcu();
synchronize_rcu();
CDS_INIT_LIST_HEAD();

Thanks, note taken. Mathieu, could you add this as comment for rculist.h? It will save people from finding list_dei_init_rcu().

Yuan

A message that is not in the archive (sent off-list or not yet received): [email protected]

#7 lore raw
Quoted 7 lines · * Liu Yuan ([email protected]) wrote:
Quoted 6 lines · Lai Jiangshan

Add a trivial comment.

There is no list_del_init_rcu(), "init" hurts "rcu".
If you need a re-initialized object after deletion, you should use synchronzie_rcu():

Quoted 6 lines
Quoted 3 lines

list_del_rcu();
synchronize_rcu();
CDS_INIT_LIST_HEAD();

Thanks, note taken. Mathieu, could you add this as comment for rculist.h? It will save people from finding list_dei_init_rcu().

Sure, done. Here is the updated proposed patch:

commit 82bffe25ba06e2ab8c872640efdf40d1f17f0e85

Author: Mathieu Desnoyers <[email protected]>
Date:   Mon Jan 21 15:53:41 2013 -0500

expand and cleanup list.h and rculist.h

Cleanup urcu/list.h and urcu/rculist.h: adopt Userspace RCU project coding style, comment each function thoroughly.

Add the following API members:

- cds_list_for_each_safe()
- cds_list_for_each_entry_reverse_safe()
- cds_list_add_tail_rcu()

Document that cds_list_empty() can be used on RCU lists without protection.

CC Liu Yuan <[email protected]>
CC Lai Jiangshan <[email protected]>
CC Paul E. McKenney <[email protected]>
urcu/list.h +261 -107
index 5d04394..61e3298 100644
@@ -5,7 +5,7 @@
  *
  * Copyright (C) 2009 Pierre-Marc Fournier
  * Conversion to RCU list.
- * Copyright (C) 2010 Mathieu Desnoyers <[email protected]>
+ * Copyright (C) 2010-2013 Mathieu Desnoyers <[email protected]>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -25,86 +25,124 @@
 #ifndef _CDS_LIST_H
 #define _CDS_LIST_H	1
 
-/* The definitions of this file are adopted from those which can be
-   found in the Linux kernel headers to enable people familiar with
-   the latter find their way in these sources as well.  */
-
+/*
+ * The definitions of this file are adopted from those which can be
+ * found in the Linux kernel headers to enable people familiar with the
+ * latter find their way in these sources as well.
+ */
 
-/* Basic type for the double-link list.  */
-struct cds_list_head
-{
-  struct cds_list_head *next;
-  struct cds_list_head *prev;
+/* Basic type for the double-link list. */
+struct cds_list_head {
+	struct cds_list_head *next;
+	struct cds_list_head *prev;
 };
 
+/* Define a variable with the head and tail of the list. */
+#define CDS_LIST_HEAD(name)	\
+	struct cds_list_head name = CDS_LIST_HEAD_INIT(name)
 
-/* Define a variable with the head and tail of the list.  */
-#define CDS_LIST_HEAD(name) \
-  struct cds_list_head name = { &(name), &(name) }
-
-/* Initialize a new list head.  */
-#define CDS_INIT_LIST_HEAD(ptr) \
-  (ptr)->next = (ptr)->prev = (ptr)
-
-#define CDS_LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) }
+#define CDS_LIST_HEAD_INIT(name)	{ .prev = &(name), .next = &(name) }
 
-/* Add new element at the head of the list.  */
-static inline void
-cds_list_add (struct cds_list_head *newp, struct cds_list_head *head)
+/*
+ * @CSD_INIT_LIST_HEAD: Initialize a new list head.
+ * @head: head of list to initialize.
+ */
+static inline
+void CDS_INIT_LIST_HEAD(struct cds_list_head *head)
 {
-  head->next->prev = newp;
-  newp->next = head->next;
-  newp->prev = head;
-  head->next = newp;
+	head->next = head;
+	head->prev = head;
 }
 
-
-/* Add new element at the tail of the list.  */
-static inline void
-cds_list_add_tail (struct cds_list_head *newp, struct cds_list_head *head)
+/*
+ * cds_list_add: Add new element at the head of the list.
+ * @newp: new element.
+ * @head: list head.
+ *
+ * Mutual exclusion against other updates and reads to list is required.
+ */
+static inline
+void cds_list_add(struct cds_list_head *newp, struct cds_list_head *head)
 {
-  head->prev->next = newp;
-  newp->next = head;
-  newp->prev = head->prev;
-  head->prev = newp;
+	head->next->prev = newp;
+	newp->next = head->next;
+	newp->prev = head;
+	head->next = newp;
 }
 
+/*
+ * cds_list_add_tail: Add new element at the tail of the list.
+ * @newp: new element.
+ * @head: list head.
+ *
+ * Mutual exclusion against other updates and reads to list is required.
+ */
+static inline
+void cds_list_add_tail(struct cds_list_head *newp, struct cds_list_head *head)
+{
+	head->prev->next = newp;
+	newp->next = head;
+	newp->prev = head->prev;
+	head->prev = newp;
+}
 
-/* Remove element from list.  */
-static inline void
-__cds_list_del (struct cds_list_head *prev, struct cds_list_head *next)
+static inline
+void __cds_list_del(struct cds_list_head *prev, struct cds_list_head *next)
 {
-  next->prev = prev;
-  prev->next = next;
+	next->prev = prev;
+	prev->next = next;
 }
 
-/* Remove element from list.  */
-static inline void
-cds_list_del (struct cds_list_head *elem)
+/*
+ * cds_list_del: Remove element from list.
+ * @elem: element to remove.
+ *
+ * Mutual exclusion against other updates and reads to list is required.
+ */
+static inline
+void cds_list_del(struct cds_list_head *elem)
 {
-  __cds_list_del (elem->prev, elem->next);
+	__cds_list_del(elem->prev, elem->next);
 }
 
-/* Remove element from list, initializing the element's list pointers. */
-static inline void
-cds_list_del_init (struct cds_list_head *elem)
+/*
+ * cds_list_del_init: Remove element from list, init element.
+ * @elem: element to remove.
+ *
+ * Remove element from list, initializing the element's list pointers.
+ * Mutual exclusion against other updates and reads to list is required.
+ */
+static inline
+void cds_list_del_init(struct cds_list_head *elem)
 {
 	cds_list_del(elem);
 	CDS_INIT_LIST_HEAD(elem);
 }
 
-/* delete from list, add to another list as head */
-static inline void
-cds_list_move (struct cds_list_head *elem, struct cds_list_head *head)
+/*
+ * cds_list_move: Delete from list, add to another list as head.
+ * @elem: element to move.
+ * @head: head of list to move into.
+ *
+ * Mutual exclusion against other updates and reads to both lists is
+ * required.
+ */
+static inline
+void cds_list_move(struct cds_list_head *elem, struct cds_list_head *head)
 {
-  __cds_list_del (elem->prev, elem->next);
-  cds_list_add (elem, head);
+	__cds_list_del(elem->prev, elem->next);
+	cds_list_add(elem, head);
 }
 
-/* replace an old entry.
+/*
+ * cds_list_replace: replace an old entry.
+ * @old: old entry.
+ * @_new: new entry.
+ *
+ * Mutual exclusion against other updates and reads to list is required.
  */
-static inline void
-cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new)
+static inline
+void cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new)
 {
 	_new->next = old->next;
 	_new->prev = old->prev;
@@ -112,75 +150,191 @@ cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new)
 	_new->next->prev = _new;
 }
 
-/* Join two lists.  */
-static inline void
-cds_list_splice (struct cds_list_head *add, struct cds_list_head *head)
+/*
+ * cds_list_empty: returns whether list is empty
+ *
+ * Return nonzero if list is empty, zero otherwise.
+ * cds_list_empty() can be used on RCU lists. RCU read-side lock is not
+ * required.
+ */
+static inline
+int cds_list_empty(struct cds_list_head *head)
 {
-  /* Do nothing if the list which gets added is empty.  */
-  if (add != add->next)
-    {
-      add->next->prev = head;
-      add->prev->next = head->next;
-      head->next->prev = add->prev;
-      head->next = add->next;
-    }
+	return head == head->next;
 }
 
-/* Get typed element from list at a given position.  */
-#define cds_list_entry(ptr, type, member) \
-  ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member)))
-
+/*
+ * cds_list_splice: Join two lists.
+ * @add: head of list to merge into @head.
+ * @head: head of list to be merged into.
+ *
+ * Merge @add into @head.
+ * Mutual exclusion against other updates and reads to both lists is
+ * required.
+ */
+static inline
+void cds_list_splice(struct cds_list_head *add, struct cds_list_head *head)
+{
+	if (cds_list_empty(add))
+		return;
+	add->next->prev = head;
+	add->prev->next = head->next;
+	head->next->prev = add->prev;
+	head->next = add->next;
+}
 
-/* Get first entry from a list. */
-#define cds_list_first_entry(ptr, type, member) \
-	cds_list_entry((ptr)->next, type, member)
+/*
+ * cds_list_replace_init: replace old entry by new one, init new entry.
+ * @old: old entry to replace.
+ * @_new: new entry to replace with.
+ *
+ * Mutual exclusion against other updates and reads to list is required.
+ */
+static inline
+void cds_list_replace_init(struct cds_list_head *old,
+		struct cds_list_head *_new)
+{
+	struct cds_list_head *head = old->next;
+	cds_list_del(old);
+	cds_list_add_tail(_new, head);
+	CDS_INIT_LIST_HEAD(old);
+}
 
+/*
+ * cds_list_entry: Get typed element from list at a given position.
+ * @ptr: node pointer (struct cds_list_head *).
+ * @type: type containing the list node field.
+ * @member: field name of list node within containing type.
+ */
+#define cds_list_entry(ptr, type, member)		\
+	((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member)))
 
-/* Iterate forward over the elements of the list.  */
-#define cds_list_for_each(pos, head) \
-  for (pos = (head)->next; pos != (head); pos = pos->next)
+/*
+ * cds_list_first_entry: Get first entry from a list.
+ * @head: list head (struct cds_list_head *).
+ * @type: type containing the list node field.
+ * @member: field name of list node within containing type.
+ *
+ * This should *not* be used on an empty list. Test for list emptiness
+ * before using @cds_list_first_entry.
+ */
+#define cds_list_first_entry(head, type, member)	\
+	cds_list_entry((head)->next, type, member)
 
+/*
+ * cds_list_for_each: Iterate forward over the elements of the list.
+ * @pos: pointer to use as iterator (struct cds_list_head *).
+ * @head: list head (struct cds_list_head *).
+ *
+ * Mutual exclusion against updates to list is required.
+ * It is not safe to remove elements within loop iteration.
+ */
+#define cds_list_for_each(pos, head)			\
+	for (pos = (head)->next; pos != (head); pos = pos->next)
 
-/* Iterate backward over the elements of the list.  */
-#define cds_list_for_each_prev(pos, head) \
-  for (pos = (head)->prev; pos != (head); pos = pos->prev)
+/*
+ * cds_list_for_each_safe: Iterate forward, safe against removal.
+ * @pos: pointer to use as iterator (struct cds_list_head *).
+ * @p: temporary pointer to store @pos copy (struct cds_list_head *).
+ * @head: list head (struct cds_list_head *).
+ *
+ * Mutual exclusion against updates to list is required.
+ * The list elements can be removed from the list within loop iteration.
+ */
+#define cds_list_for_each_safe(pos, p, head)		\
+	for (pos = (head)->next, p = pos->next;		\
+		pos != (head);				\
+		pos = p; p = pos->next)
 
+/*
+ * cds_list_for_each_prev: Iterate backward over the elements of the list.
+ * @pos: pointer to use as iterator (struct cds_list_head *).
+ * @head: list head (struct cds_list_head *).
+ *
+ * Mutual exclusion against updates to list is required.
+ * It is not safe to remove elements within loop iteration.
+ */
+#define cds_list_for_each_prev(pos, head)		\
+	for (pos = (head)->prev; pos != (head); pos = pos->prev)
 
-/* Iterate backwards over the elements list.  The list elements can be
-   removed from the list while doing this.  */
-#define cds_list_for_each_prev_safe(pos, p, head) \
-  for (pos = (head)->prev, p = pos->prev; \
-       pos != (head); \
-       pos = p, p = pos->prev)
+/*
+ * cds_list_for_each_prev_safe: Iterate backwards, safe against removal.
+ * @pos: pointer to use as iterator (struct cds_list_head *).
+ * @p: temporary pointer to store @pos copy (struct cds_list_head *).
+ * @head: list head (struct cds_list_head *).
+ *
+ * Mutual exclusion against updates to list is required.
+ * The list elements can be removed from the list within loop iteration.
+ */
+#define cds_list_for_each_prev_safe(pos, p, head)	\
+	for (pos = (head)->prev, p = pos->prev;		\
+		pos != (head);				\
+		pos = p, p = pos->prev)
 
-#define cds_list_for_each_entry(pos, head, member)				\
+/*
+ * cds_list_for_each_entry: Iterate forward over entries of the list.
+ * @pos: pointer to use as iterator (type of list node container).
+ * @head: list head (struct cds_list_head *).
+ * @member: field name of list node field within container type.
+ *
+ * Mutual exclusion against updates to list is required.
+ * It is not safe to remove elements within loop iteration.
+ */
+#define cds_list_for_each_entry(pos, head, member)			   \
 	for (pos = cds_list_entry((head)->next, __typeof__(*pos), member); \
-	     &pos->member != (head);					\
-	     pos = cds_list_entry(pos->member.next, __typeof__(*pos), member))
+		&pos->member != (head);					   \
+		pos = cds_list_entry(pos->member.next,			   \
+				__typeof__(*pos), member))
 
-#define cds_list_for_each_entry_reverse(pos, head, member)			\
+/*
+ * cds_list_for_each_entry_reverse: Iterate backwards over entries of the list.
+ * @pos: pointer to use as iterator (type of list node container).
+ * @head: list head (struct cds_list_head *).
+ * @member: field name of list node field within container type.
+ *
+ * Mutual exclusion against updates to list is required.
+ * It is not safe to remove elements within loop iteration.
+ */
+#define cds_list_for_each_entry_reverse(pos, head, member)		   \
 	for (pos = cds_list_entry((head)->prev, __typeof__(*pos), member); \
-	     &pos->member != (head);					\
-	     pos = cds_list_entry(pos->member.prev, __typeof__(*pos), member))
+		&pos->member != (head);					   \
+		pos = cds_list_entry(pos->member.prev,			   \
+				__typeof__(*pos), member))
 
-#define cds_list_for_each_entry_safe(pos, p, head, member)			\
+/*
+ * cds_list_for_each_entry_safe: Iterate forward, safe against removal.
+ * @pos: pointer to use as iterator (pointer to list node container).
+ * @p: temporary pointer to store @pos copy (pointer to list node container).
+ * @head: list head (struct cds_list_head *).
+ * @member: field name of list node field within container type.
+ *
+ * Mutual exclusion against updates to list is required.
+ * The list elements can be removed from the list within loop iteration.
+ */
+#define cds_list_for_each_entry_safe(pos, p, head, member)		   \
 	for (pos = cds_list_entry((head)->next, __typeof__(*pos), member), \
-		     p = cds_list_entry(pos->member.next, __typeof__(*pos), member); \
-	     &pos->member != (head);					\
-	     pos = p, p = cds_list_entry(pos->member.next, __typeof__(*pos), member))
+		p = cds_list_entry(pos->member.next,			   \
+				__typeof__(*pos), member);		   \
+		&pos->member != (head);					   \
+		pos = p, p = cds_list_entry(pos->member.next,		   \
+				__typeof__(*pos), member))
 
-static inline int cds_list_empty(struct cds_list_head *head)
-{
-	return head == head->next;
-}
-
-static inline void cds_list_replace_init(struct cds_list_head *old,
-				     struct cds_list_head *_new)
-{
-	struct cds_list_head *head = old->next;
-	cds_list_del(old);
-	cds_list_add_tail(_new, head);
-	CDS_INIT_LIST_HEAD(old);
-}
+/*
+ * cds_list_for_each_entry_reverse_safe: Iterate backwards, safe for removal.
+ * @pos: pointer to use as iterator (pointer to list node container).
+ * @p: temporary pointer to store @pos copy (pointer to list node container).
+ * @head: list head (struct cds_list_head *).
+ * @member: field name of list node field within container type.
+ *
+ * Mutual exclusion against updates to list is required.
+ * The list elements can be removed from the list within loop iteration.
+ */
+#define cds_list_for_each_entry_reverse_safe(pos, p, head, member)	   \
+	for (pos = cds_list_entry((head)->prev, __typeof__(*pos), member), \
+		p = cds_list_entry(pos->member.prev,			   \
+				__typeof__(*pos), member);		   \
+		&pos->member != (head);					   \
+		pos = p, p = cds_list_entry(pos->member.prev,		   \
+				__typeof__(*pos), member))
 
 #endif	/* _CDS_LIST_H */
urcu/rculist.h +87 -19

141 lines not on this page · raw message

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com