[PATCH] list: Add safe entry iterators without an explicit n cursor

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@xxxxxxxxxx>

The list_for_each_entry_safe*() helpers are useful for loops which may
remove the current entry, but they require callers to provide a second
cursor named by convention as n. Some users do not need to inspect or
reset that cursor; they only need the iterator to keep the next entry
available while the current entry may be removed.

Add entry iterators which hide that temporary next cursor while otherwise
following the traversal pattern of the corresponding
list_for_each_entry_safe*() helpers.

Do not fold this behavior into list_for_each_entry(). That iterator
advances from pos after the loop body, and a few existing callers rely
on that semantics to observe list changes made during the body. For
example, stress_reorder_work() in kernel/locking/test-ww_mutex.c moves
the current entry to the list head with list_move(&ll->link, &locks) and
documents that this restarts iteration. If list_for_each_entry() cached
the next entry before running the body, the loop would continue from the
stale saved next entry instead of honoring the modified list order.

Signed-off-by: Kaitao Cheng <chengkaitao@xxxxxxxxxx>
---
 include/linux/list.h       | 60 ++++++++++++++++++++++++++++++++++++++
 scripts/include/list.h     | 13 +++++++++
 tools/include/linux/list.h | 60 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 133 insertions(+)

diff --git a/include/linux/list.h b/include/linux/list.h
index 09d979976b3b..d3597da3e952 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -908,6 +908,19 @@ static inline size_t list_count_nodes(struct list_head *head)
 	     !list_entry_is_head(pos, head, member); 			\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable - iterate over list of given type safe against
+ * removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_for_each_entry_mutable(pos, head, member)			\
+	for (typeof(pos) __temp__ = list_next_entry(pos =		\
+	     list_first_entry(head, typeof(*pos), member), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_safe_continue - continue list iteration safe against removal
  * @pos:	the type * to use as a loop cursor.
@@ -924,6 +937,22 @@ static inline size_t list_count_nodes(struct list_head *head)
 	     !list_entry_is_head(pos, head, member);				\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable_continue - continue list iteration safe against
+ * removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate over list of given type, continuing after current point,
+ * safe against removal of list entry.
+ */
+#define list_for_each_entry_mutable_continue(pos, head, member)		\
+	for (typeof(pos) __temp__ = list_next_entry(pos =		\
+	     list_next_entry(pos, member), member);			\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
  * @pos:	the type * to use as a loop cursor.
@@ -939,6 +968,21 @@ static inline size_t list_count_nodes(struct list_head *head)
 	     !list_entry_is_head(pos, head, member);				\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable_from - iterate over list from current point safe
+ * against removal
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate over list of given type from current point, safe against
+ * removal of list entry.
+ */
+#define list_for_each_entry_mutable_from(pos, head, member)		\
+	for (typeof(pos) __temp__ = list_next_entry(pos, member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
  * @pos:	the type * to use as a loop cursor.
@@ -955,6 +999,22 @@ static inline size_t list_count_nodes(struct list_head *head)
 	     !list_entry_is_head(pos, head, member); 			\
 	     pos = n, n = list_prev_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable_reverse - iterate backwards over list safe against
+ * removal
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate backwards over list of given type, safe against removal
+ * of list entry.
+ */
+#define list_for_each_entry_mutable_reverse(pos, head, member)		\
+	for (typeof(pos) __temp__ = list_prev_entry(pos =		\
+	     list_last_entry(head, typeof(*pos), member), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = __temp__, __temp__ = list_prev_entry(__temp__, member))
+
 /**
  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
  * @pos:	the loop cursor used in the list_for_each_entry_safe loop
diff --git a/scripts/include/list.h b/scripts/include/list.h
index 8bdcaadca709..ab84e3f70793 100644
--- a/scripts/include/list.h
+++ b/scripts/include/list.h
@@ -286,6 +286,19 @@ static inline int list_empty(const struct list_head *head)
 	     !list_entry_is_head(pos, head, member);			\
 	     pos = list_next_entry(pos, member))
 
+/**
+ * list_for_each_entry_mutable - iterate over list of given type safe against
+ * removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_for_each_entry_mutable(pos, head, member)			\
+	for (typeof(pos) __temp__ = list_next_entry(pos =		\
+	     list_first_entry(head, typeof(*pos), member), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_reverse - iterate backwards over list of given type.
  * @pos:	the type * to use as a loop cursor.
diff --git a/tools/include/linux/list.h b/tools/include/linux/list.h
index a692ff7aed5c..8aa394832aba 100644
--- a/tools/include/linux/list.h
+++ b/tools/include/linux/list.h
@@ -544,6 +544,19 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head); 					\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable - iterate over list of given type safe against
+ * removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_for_each_entry_mutable(pos, head, member)			\
+	for (typeof(pos) __temp__ = list_next_entry(pos =		\
+	     list_first_entry(head, typeof(*pos), member), member);	\
+	     &pos->member != (head);					\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_safe_continue - continue list iteration safe against removal
  * @pos:	the type * to use as a loop cursor.
@@ -560,6 +573,22 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head);						\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable_continue - continue list iteration safe against
+ * removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate over list of given type, continuing after current point,
+ * safe against removal of list entry.
+ */
+#define list_for_each_entry_mutable_continue(pos, head, member)		\
+	for (typeof(pos) __temp__ = list_next_entry(pos =		\
+	     list_next_entry(pos, member), member);			\
+	     &pos->member != (head);					\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
  * @pos:	the type * to use as a loop cursor.
@@ -575,6 +604,21 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head);						\
 	     pos = n, n = list_next_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable_from - iterate over list from current point safe
+ * against removal
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate over list of given type from current point, safe against
+ * removal of list entry.
+ */
+#define list_for_each_entry_mutable_from(pos, head, member)		\
+	for (typeof(pos) __temp__ = list_next_entry(pos, member);	\
+	     &pos->member != (head);					\
+	     pos = __temp__, __temp__ = list_next_entry(__temp__, member))
+
 /**
  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
  * @pos:	the type * to use as a loop cursor.
@@ -591,6 +635,22 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head); 					\
 	     pos = n, n = list_prev_entry(n, member))
 
+/**
+ * list_for_each_entry_mutable_reverse - iterate backwards over list safe
+ * against removal
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate backwards over list of given type, safe against removal
+ * of list entry.
+ */
+#define list_for_each_entry_mutable_reverse(pos, head, member)		\
+	for (typeof(pos) __temp__ = list_prev_entry(pos =		\
+	     list_last_entry(head, typeof(*pos), member), member);	\
+	     &pos->member != (head);					\
+	     pos = __temp__, __temp__ = list_prev_entry(__temp__, member))
+
 /**
  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
  * @pos:	the loop cursor used in the list_for_each_entry_safe loop
-- 
2.50.1 (Apple Git-155)