[PATCH v4 0/4] Prepare mutable list iterators to cache cursor state

[PATCH v4 0/4] Prepare mutable list iterators to cache cursor state

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

The list_for_each*_safe() helpers are used when the loop body may remove
the current entry.  Their current interface, however, forces every caller
to define a temporary cursor outside the macro and pass it in, even when
the caller never uses that cursor directly.  For most call sites this
extra cursor is just boilerplate required by the macro implementation.

This is awkward because the saved next pointer is an internal detail of
the iteration.  Callers that only remove or move the current entry do not
need to spell it out.

The _safe() suffix has also caused confusion.  Christian Koenig pointed
out that the name is easy to read as a thread-safe variant, especially
for beginners, even though it only means that the iterator keeps enough
state to tolerate removal of the current entry.  He suggested _mutable()
as a clearer description of what the loop permits.

Add *_mutable() iterator variants for list, hlist and llist. The caller
omits the temporary cursor and the macro creates a unique internal cursor
with typeof(pos) and __UNIQUE_ID(). The existing *_safe() helpers remain
available for compatibility.

For ease of discussion, I need to summarize the currently possible
approaches and briefly describe their respective pros and cons,
using the list_for_each_entry* interfaces as examples.

1. Add list_for_each_entry_mutable, while keeping list_for_each_entry
and list_for_each_entry_safe unchanged. list_for_each_entry_mutable
would be used specifically for safe deletion scenarios that do not
need to expose the temporary cursor externally. The code can refer to
the v4 and v1 versions.

Pros: Does not depend on immediate per-subsystem adaptation and can be
      merged directly.
Cons: Requires adding a whole set of mutable interfaces, which makes the
      code somewhat redundant.

2. Directly optimize away the temporary cursor in list_for_each_entry_safe
and define it inside the loop instead, changing the interface from four
arguments to three.

Pros: Does not add redundant interfaces.
Cons: (1) Users need to manually update special cases that use the
      traversal variable of list_for_each_entry_safe, the new
      list_for_each_entry_safe would no longer apply there and would
      need to be open-coded.
      (2) Because the macro arguments changes, all list_for_each_entry_safe
      callers would need to be modified and merged together, making it
      difficult to merge such a large amount of code at once.

3. Use a variadic macro approach to optimize list_for_each_entry_safe,
so that it supports both three and four arguments. The code can refer to
the v3 version.

Pros: (1) Does not add redundant interfaces.
      (2) Does not depend on immediate per-subsystem adaptation and can
      be merged directly.
Cons: (1) Increases compile time.
      (2) Makes the interface harder for users to use.

4. Optimize list_for_each_entry by defining the temporary cursor
internally, making it compatible with the functionality of
list_for_each_entry_safe. The code can refer to the v2 version.

Pros: (1) Does not add redundant interfaces.
      (2) The number of externally visible arguments of list_for_each_entry
      remains unchanged, still three.
Cons: (1) list_for_each_entry and list_for_each_entry_safe would be merged
      into one, and list_for_each_entry_safe would gradually be deprecated.
      (2) Users need to manually update special cases that use the traversal
      variable of list_for_each_entry, the new list_for_each_entry would no
      longer apply there and would need to be open-coded. There are 15 such
      cases in total.

5. Use a variadic macro approach to optimize list_for_each_entry, so that
it supports both three and four arguments.

Pros: (1) Does not add redundant interfaces.
      (2) Does not depend on immediate per-subsystem adaptation and can be
      merged directly.
Cons: (1) Increases compile time.
      (2) list_for_each_entry and list_for_each_entry_safe would be merged
      into one, and list_for_each_entry_safe would gradually be deprecated.

6. Make no changes, keep the current logic unchanged, and close the current
email discussion.

After broad discussion, more developers agreed to use option 1 for the
change. The implementation details follow the current patch series.

Changes in v4 (Jani Nikula):
- Abandon variadic macro approach

Changes in v3 (Christian König, Andy Shevchenko):
- Convert safe list walks to mutable iterators

Changes in v2 (Muchun Song, Andy Shevchenko):
- Drop the list_for_each_entry_mutable*() helpers from v1 and make the
  cursor change directly in the existing list_for_each_entry*() helpers.
- Open-code special list walks that rely on updating the loop cursor in
  the body, preserving their existing traversal semantics.

Link to v3:
https://lore.kernel.org/all/20260622040533.29824-1-kaitao.cheng@linux.dev/

Link to v2:
https://lore.kernel.org/all/20260609061347.93688-1-kaitao.cheng@linux.dev/

Link to v1:
https://lore.kernel.org/all/20260529082149.76764-1-kaitao.cheng@linux.dev/

Kaitao Cheng (4):
  list: Add mutable iterator variants
  llist: Add mutable iterator variants
  tools/list: Add mutable iterator variants
  scripts/list: Add mutable iterator variants

 include/linux/list.h           | 180 +++++++++++++++++++++++++++++++-
 include/linux/llist.h          |  67 +++++++++++-
 scripts/include/list.h         |  56 +++++++++-
 tools/include/linux/compiler.h |   2 +
 tools/include/linux/list.h     | 184 +++++++++++++++++++++++++++++++--
 5 files changed, 472 insertions(+), 17 deletions(-)

-- 
2.43.0

[PATCH v4 1/4] list: Add mutable iterator variants

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

The list_for_each*_safe() helpers allow the current entry to be removed
while iterating, but require callers to declare and pass a temporary
cursor. Most callers never use that cursor directly, so exposing it adds
boilerplate and leaks an implementation detail into each call site.

Add *_mutable() variants for list and hlist iterators. These variants
keep the temporary cursor in a uniquely named local variable inside the
macro while preserving the removal-safe iteration semantics.

Keep the existing *_safe() variants for callers that need to access or
reset the temporary cursor, and update their documentation to clarify
which interface to use.

Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>
---
 include/linux/list.h | 180 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 175 insertions(+), 5 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 09d979976b3b..373b08b929d3 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -765,26 +765,62 @@ static inline void list_splice_tail_init(struct list_head *list,
 
 /**
  * list_for_each_safe - iterate over a list safe against removal of list entry
+ *	with a caller-provided temporary cursor
  * @pos:	the &struct list_head to use as a loop cursor.
  * @n:		another &struct list_head to use as temporary storage
  * @head:	the head for your list.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_mutable() instead.
  */
 #define list_for_each_safe(pos, n, head) \
 	for (pos = (head)->next, n = pos->next; \
 	     !list_is_head(pos, (head)); \
 	     pos = n, n = pos->next)
 
+#define __list_for_each_mutable(pos, tmp, head)				\
+	for (typeof(pos) tmp = (pos = (head)->next)->next;		\
+	     !list_is_head(pos, (head));				\
+	     pos = tmp, tmp = pos->next)
+
+/**
+ * list_for_each_mutable - iterate over a list safe against entry removal
+ *	with an internal temporary cursor
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @head:	the head for your list.
+ */
+#define list_for_each_mutable(pos, head)				\
+	__list_for_each_mutable(pos, __UNIQUE_ID(next), head)
+
 /**
- * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
+ * list_for_each_prev_safe - iterate over a list backwards safe against removal
+ *	of list entry with a caller-provided temporary cursor
  * @pos:	the &struct list_head to use as a loop cursor.
  * @n:		another &struct list_head to use as temporary storage
  * @head:	the head for your list.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_prev_mutable() instead.
  */
 #define list_for_each_prev_safe(pos, n, head) \
 	for (pos = (head)->prev, n = pos->prev; \
 	     !list_is_head(pos, (head)); \
 	     pos = n, n = pos->prev)
 
+#define __list_for_each_prev_mutable(pos, tmp, head)			\
+	for (typeof(pos) tmp = (pos = (head)->prev)->prev;		\
+	     !list_is_head(pos, (head));				\
+	     pos = tmp, tmp = pos->prev)
+
+/**
+ * list_for_each_prev_mutable - iterate over a list backwards safe against entry
+ *	removal with an internal temporary cursor
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @head:	the head for your list.
+ */
+#define list_for_each_prev_mutable(pos, head)				\
+	__list_for_each_prev_mutable(pos, __UNIQUE_ID(prev), head)
+
 /**
  * list_count_nodes - count nodes in the list
  * @head:	the head for your list.
@@ -896,11 +932,15 @@ static inline size_t list_count_nodes(struct list_head *head)
 	     pos = list_prev_entry(pos, member))
 
 /**
- * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * list_for_each_entry_safe - iterate over list of given type safe against
+ *	removal of list entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @head:	the head for your list.
  * @member:	the name of the list_head within the struct.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable() instead.
  */
 #define list_for_each_entry_safe(pos, n, head, member)			\
 	for (pos = list_first_entry(head, typeof(*pos), member),	\
@@ -908,8 +948,25 @@ 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))
 
+#define __list_for_each_entry_mutable(pos, tmp, head, member)		\
+	for (typeof(pos) tmp = list_next_entry(pos =			\
+		list_first_entry(head, typeof(*pos), member), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable - iterate over a list safe against entry removal
+ *	with an internal temporary cursor
+ * @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)			\
+	__list_for_each_entry_mutable(pos, __UNIQUE_ID(next), head, member)
+
 /**
  * list_for_each_entry_safe_continue - continue list iteration safe against removal
+ *	with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @head:	the head for your list.
@@ -917,6 +974,9 @@ static inline size_t list_count_nodes(struct list_head *head)
  *
  * Iterate over list of given type, continuing after current point,
  * safe against removal of list entry.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable_continue() instead.
  */
 #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
 	for (pos = list_next_entry(pos, member), 				\
@@ -924,8 +984,28 @@ 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))
 
+#define __list_for_each_entry_mutable_continue(pos, tmp, head, member)	\
+	for (typeof(pos) tmp = list_next_entry(pos =			\
+		list_next_entry(pos, member), member);			\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
 /**
- * list_for_each_entry_safe_from - iterate over list from current point safe against removal
+ * list_for_each_entry_mutable_continue - continue list iteration safe against
+ *	removal with an internal temporary cursor
+ * @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)		\
+	__list_for_each_entry_mutable_continue(pos, __UNIQUE_ID(next), head, member)
+
+/**
+ * list_for_each_entry_safe_from - iterate over list from current point safe
+ *	against removal with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @head:	the head for your list.
@@ -933,14 +1013,36 @@ static inline size_t list_count_nodes(struct list_head *head)
  *
  * Iterate over list of given type from current point, safe against
  * removal of list entry.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable_from() instead.
  */
 #define list_for_each_entry_safe_from(pos, n, head, member) 			\
 	for (n = list_next_entry(pos, member);					\
 	     !list_entry_is_head(pos, head, member);				\
 	     pos = n, n = list_next_entry(n, member))
 
+#define __list_for_each_entry_mutable_from(pos, tmp, head, member)	\
+	for (typeof(pos) tmp = list_next_entry(pos, member);		\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable_from - iterate over list from current point safe
+ *	against removal with an internal temporary cursor
+ * @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)		\
+	__list_for_each_entry_mutable_from(pos,	__UNIQUE_ID(next), head, member)
+
 /**
- * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
+ * list_for_each_entry_safe_reverse - iterate backwards over list safe against
+ *	removal with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @head:	the head for your list.
@@ -948,6 +1050,9 @@ static inline size_t list_count_nodes(struct list_head *head)
  *
  * Iterate backwards over list of given type, safe against removal
  * of list entry.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable_reverse() instead.
  */
 #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
 	for (pos = list_last_entry(head, typeof(*pos), member),		\
@@ -955,6 +1060,25 @@ 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))
 
+#define __list_for_each_entry_mutable_reverse(pos, tmp, head, member)	\
+	for (typeof(pos) tmp = list_prev_entry(pos =			\
+		list_last_entry(head, typeof(*pos), member), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = tmp, tmp = list_prev_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable_reverse - iterate backwards over list safe
+ *	against removal with an internal temporary cursor
+ * @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)		\
+	__list_for_each_entry_mutable_reverse(pos, __UNIQUE_ID(prev), head, 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
@@ -1185,10 +1309,34 @@ static inline void hlist_splice_init(struct hlist_head *from,
 #define hlist_for_each(pos, head) \
 	for (pos = (head)->first; pos ; pos = pos->next)
 
+/**
+ * hlist_for_each_safe - iterate over a hlist safe against entry removal
+ *	with a caller-provided temporary cursor
+ * @pos:	the &struct hlist_node to use as a loop cursor.
+ * @n:		another &struct hlist_node to use as temporary storage.
+ * @head:	the head for your hlist.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * hlist_for_each_mutable() instead.
+ */
 #define hlist_for_each_safe(pos, n, head) \
 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 	     pos = n)
 
+#define __hlist_for_each_mutable(pos, tmp, head)			\
+	for (typeof(pos) tmp = (pos = (head)->first) ? pos->next : NULL; \
+	     pos;							\
+	     pos = tmp, tmp = pos ? pos->next : NULL)
+
+/**
+ * hlist_for_each_mutable - iterate over a hlist safe against entry removal
+ *	with an internal temporary cursor
+ * @pos:	the &struct hlist_node to use as a loop cursor.
+ * @head:	the head for your hlist.
+ */
+#define hlist_for_each_mutable(pos, head)				\
+	__hlist_for_each_mutable(pos, __UNIQUE_ID(next), head)
+
 #define hlist_entry_safe(ptr, type, member) \
 	({ typeof(ptr) ____ptr = (ptr); \
 	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
@@ -1225,17 +1373,39 @@ static inline void hlist_splice_init(struct hlist_head *from,
 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 
 /**
- * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * hlist_for_each_entry_safe - iterate over list of given type safe against
+ *	removal of list entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		a &struct hlist_node to use as temporary storage
  * @head:	the head for your list.
  * @member:	the name of the hlist_node within the struct.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * hlist_for_each_entry_mutable() instead.
  */
 #define hlist_for_each_entry_safe(pos, n, head, member) 		\
 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
 	     pos && ({ n = pos->member.next; 1; });			\
 	     pos = hlist_entry_safe(n, typeof(*pos), member))
 
+#define __hlist_for_each_entry_mutable(pos, tmp, head, member)		\
+	for (struct hlist_node *tmp = (pos =				\
+		hlist_entry_safe((head)->first, typeof(*pos), member)) ? \
+		pos->member.next : NULL;				\
+	     pos;							\
+	     pos = hlist_entry_safe((tmp), typeof(*pos), member),	\
+		tmp = pos ? pos->member.next : NULL)
+
+/**
+ * hlist_for_each_entry_mutable - iterate over hlist safe against entry removal
+ *	with an internal temporary cursor
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your hlist.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_mutable(pos, head, member)			\
+	__hlist_for_each_entry_mutable(pos, __UNIQUE_ID(next), head, member)
+
 /**
  * hlist_count_nodes - count nodes in the hlist
  * @head:	the head for your hlist.
-- 
2.43.0

[PATCH v4 2/4] llist: Add mutable iterator variants

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

The llist_for_each_safe() and llist_for_each_entry_safe() helpers allow
the current entry to be removed while iterating, but require callers to
declare and pass a temporary cursor. Most callers do not access that
cursor directly, so exposing it adds unnecessary boilerplate.

Add mutable variants that keep the temporary cursor in a uniquely named
local variable inside the macro while preserving removal-safe iteration
semantics.

Keep the existing *_safe() variants for callers that need to access or
reset the temporary cursor, and update their documentation to clarify
which interface to use.

Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>
---
 include/linux/llist.h | 67 ++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 63 insertions(+), 4 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index 413249764f7b..559058a8d4a0 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -145,7 +145,7 @@ static inline bool llist_on_list(const struct llist_node *node)
 
 /**
  * llist_for_each_safe - iterate over some deleted entries of a lock-less list
- *			 safe against removal of list entry
+ *	safe against entry removal with a caller-provided temporary cursor
  * @pos:	the &struct llist_node to use as a loop cursor
  * @n:		another &struct llist_node to use as temporary storage
  * @node:	the first entry of deleted list entries
@@ -158,10 +158,36 @@ static inline bool llist_on_list(const struct llist_node *node)
  * traverse order is from the newest to the oldest added entry.  If
  * you want to traverse from the oldest to the newest, you must
  * reverse the order by yourself before traversing.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * llist_for_each_mutable() instead.
  */
 #define llist_for_each_safe(pos, n, node)			\
 	for ((pos) = (node); (pos) && ((n) = (pos)->next, true); (pos) = (n))
 
+#define __llist_for_each_mutable(pos, tmp, node)			\
+	for (typeof(pos) tmp = ((pos) = (node)) ? (pos)->next : NULL;	\
+	     (pos);							\
+	     (pos) = tmp, tmp = (pos) ? (pos)->next : NULL)
+
+/**
+ * llist_for_each_mutable - iterate over some deleted entries of a lock-less
+ *	list safe against entry removal with an internal temporary cursor
+ * @pos:	the &struct llist_node to use as a loop cursor
+ * @node:	the first entry of deleted list entries
+ *
+ * In general, some entries of the lock-less list can be traversed
+ * safely only after being deleted from list, so start with an entry
+ * instead of list head.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ */
+#define llist_for_each_mutable(pos, node)				\
+	__llist_for_each_mutable(pos, __UNIQUE_ID(next), node)
+
 /**
  * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
  * @pos:	the type * to use as a loop cursor.
@@ -183,8 +209,9 @@ static inline bool llist_on_list(const struct llist_node *node)
 	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
 
 /**
- * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
- *			       safe against removal of list entry
+ * llist_for_each_entry_safe - iterate over some deleted entries of a lock-less
+ *	list of given type safe against entry removal with a caller-provided
+ *	temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @node:	the first entry of deleted list entries.
@@ -198,13 +225,45 @@ static inline bool llist_on_list(const struct llist_node *node)
  * traverse order is from the newest to the oldest added entry.  If
  * you want to traverse from the oldest to the newest, you must
  * reverse the order by yourself before traversing.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * llist_for_each_entry_mutable() instead.
  */
 #define llist_for_each_entry_safe(pos, n, node, member)			       \
 	for (pos = llist_entry((node), typeof(*pos), member);		       \
 	     member_address_is_nonnull(pos, member) &&			       \
-	        (n = llist_entry(pos->member.next, typeof(*n), member), true); \
+	     (n = llist_entry(pos->member.next, typeof(*n), member), true);    \
 	     pos = n)
 
+#define __llist_for_each_entry_mutable(pos, tmp, node, member)			\
+	for (typeof(pos) tmp =							\
+		((pos) = llist_entry((node), typeof(*(pos)), member),		\
+		member_address_is_nonnull(pos, member) ?			\
+		llist_entry((pos)->member.next, typeof(*(pos)), member) : NULL);\
+	     member_address_is_nonnull(pos, member);				\
+	     (pos) = tmp, tmp = member_address_is_nonnull(pos, member) ?	\
+		llist_entry((pos)->member.next, typeof(*(pos)), member) : NULL)
+
+/**
+ * llist_for_each_entry_mutable - iterate over some deleted entries of a
+ *	lock-less list of given type safe against entry removal with an internal
+ *	temporary cursor
+ * @pos:	the type * to use as a loop cursor.
+ * @node:	the first entry of deleted list entries.
+ * @member:	the name of the llist_node with the struct.
+ *
+ * In general, some entries of the lock-less list can be traversed
+ * safely only after being removed from list, so start with an entry
+ * instead of list head.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ */
+#define llist_for_each_entry_mutable(pos, node, member)			\
+	__llist_for_each_entry_mutable(pos, __UNIQUE_ID(next), node, member)
+
 /**
  * llist_empty - tests whether a lock-less list is empty
  * @head:	the list to test
-- 
2.43.0

[PATCH v4 3/4] tools/list: Add mutable iterator variants

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

The tools tree carries its own copy of the list helpers, but it does not
provide the mutable iterator variants available to in-kernel users. Tools
therefore still need to declare and pass a temporary cursor when removing
the current entry during iteration, even when the loop body never uses it.

This commit complements the work to add support for mutable iterator
variants. Add the list and hlist *_mutable() iterator variants to the
tools copy. Keep the temporary cursor in a uniquely named local variable
while preserving the removal-safe iteration semantics.

Keep the existing *_safe() variants for callers that need to access or
reset the temporary cursor, and clarify the distinction in their
documentation. Provide a __UNIQUE_ID fallback because the tools compiler
headers do not define it.

Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>
---
 tools/include/linux/compiler.h |   2 +
 tools/include/linux/list.h     | 184 +++++++++++++++++++++++++++++++--
 2 files changed, 180 insertions(+), 6 deletions(-)

diff --git a/tools/include/linux/compiler.h b/tools/include/linux/compiler.h
index f2f54b038168..9edbb09d67f3 100644
--- a/tools/include/linux/compiler.h
+++ b/tools/include/linux/compiler.h
@@ -242,6 +242,8 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 #define ___PASTE(a, b) a##b
 #define __PASTE(a, b) ___PASTE(a, b)
 
+#define __UNIQUE_ID(name) __PASTE(__UNIQUE_ID_, __PASTE(name, __PASTE(_, __COUNTER__)))
+
 #ifndef OPTIMIZER_HIDE_VAR
 /* Make the optimizer believe the variable can be manipulated arbitrarily. */
 #define OPTIMIZER_HIDE_VAR(var)						\
diff --git a/tools/include/linux/list.h b/tools/include/linux/list.h
index a692ff7aed5c..28e42aaee062 100644
--- a/tools/include/linux/list.h
+++ b/tools/include/linux/list.h
@@ -439,25 +439,59 @@ static inline void list_splice_tail_init(struct list_head *list,
 
 /**
  * list_for_each_safe - iterate over a list safe against removal of list entry
+ *	with a caller-provided temporary cursor
  * @pos:	the &struct list_head to use as a loop cursor.
  * @n:		another &struct list_head to use as temporary storage
  * @head:	the head for your list.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_mutable() instead.
  */
 #define list_for_each_safe(pos, n, head) \
 	for (pos = (head)->next, n = pos->next; pos != (head); \
 		pos = n, n = pos->next)
 
+#define __list_for_each_mutable(pos, tmp, head)				\
+	for (typeof(pos) tmp = (pos = (head)->next)->next;		\
+	     pos != (head); pos = tmp, tmp = pos->next)
+
 /**
- * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
+ * list_for_each_mutable - iterate over a list safe against removal of the
+ *	current entry with an internal temporary cursor
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @head:	the head for your list.
+ */
+#define list_for_each_mutable(pos, head)				\
+	__list_for_each_mutable(pos, __UNIQUE_ID(next), head)
+
+/**
+ * list_for_each_prev_safe - iterate over a list backwards safe against removal
+ *	of the current entry with a caller-provided temporary cursor
  * @pos:	the &struct list_head to use as a loop cursor.
  * @n:		another &struct list_head to use as temporary storage
  * @head:	the head for your list.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_prev_mutable() instead.
  */
 #define list_for_each_prev_safe(pos, n, head) \
 	for (pos = (head)->prev, n = pos->prev; \
 	     pos != (head); \
 	     pos = n, n = pos->prev)
 
+#define __list_for_each_prev_mutable(pos, tmp, head)			\
+	for (typeof(pos) tmp = (pos = (head)->prev)->prev;		\
+	     pos != (head); pos = tmp, tmp = pos->prev)
+
+/**
+ * list_for_each_prev_mutable - iterate over a list backwards safe against
+ *	removal of the current entry with an internal temporary cursor
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @head:	the head for your list.
+ */
+#define list_for_each_prev_mutable(pos, head)				\
+	__list_for_each_prev_mutable(pos, __UNIQUE_ID(prev), head)
+
 /**
  * list_for_each_entry	-	iterate over list of given type
  * @pos:	the type * to use as a loop cursor.
@@ -532,11 +566,15 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     pos = list_next_entry(pos, member))
 
 /**
- * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * list_for_each_entry_safe - iterate over list of given type safe against
+ *	removal of the current entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @head:	the head for your list.
  * @member:	the name of the list_head within the struct.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable() instead.
  */
 #define list_for_each_entry_safe(pos, n, head, member)			\
 	for (pos = list_first_entry(head, typeof(*pos), member),	\
@@ -544,15 +582,35 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head); 					\
 	     pos = n, n = list_next_entry(n, member))
 
+#define __list_for_each_entry_mutable(pos, tmp, head, member)		\
+	for (typeof(pos) tmp = list_next_entry(pos =			\
+		list_first_entry(head, typeof(*pos), member), member);	\
+	     &pos->member != (head);					\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable - iterate over a list safe against removal of
+ *	the current entry with an internal temporary cursor
+ * @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)			\
+	__list_for_each_entry_mutable(pos, __UNIQUE_ID(next), head, member)
+
 /**
  * list_for_each_entry_safe_continue - continue list iteration safe against removal
+ *	of the current entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @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.
+ * safe against removal of the current entry.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable_continue() instead.
  */
 #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
 	for (pos = list_next_entry(pos, member), 				\
@@ -560,30 +618,78 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head);						\
 	     pos = n, n = list_next_entry(n, member))
 
+#define __list_for_each_entry_mutable_continue(pos, tmp, head, member)	\
+	for (typeof(pos) tmp = list_next_entry(pos =			\
+		list_next_entry(pos, member), member);			\
+	     &pos->member != (head);					\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable_continue - continue list iteration safe against
+ *	removal of the current entry with an internal temporary cursor
+ * @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 the current entry.
+ */
+#define list_for_each_entry_mutable_continue(pos, head, member)		\
+	__list_for_each_entry_mutable_continue(pos,			\
+					       __UNIQUE_ID(next),	\
+					       head, member)
+
 /**
  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
+ *	of the current entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @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.
+ * removal of the current entry.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable_from() instead.
  */
 #define list_for_each_entry_safe_from(pos, n, head, member) 			\
 	for (n = list_next_entry(pos, member);					\
 	     &pos->member != (head);						\
 	     pos = n, n = list_next_entry(n, member))
 
+#define __list_for_each_entry_mutable_from(pos, tmp, head, member)	\
+	for (typeof(pos) tmp = list_next_entry(pos, member);		\
+	     &pos->member != (head);					\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable_from - iterate over list from current point safe
+ *	against removal of the current entry with an internal temporary cursor
+ * @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 the current entry.
+ */
+#define list_for_each_entry_mutable_from(pos, head, member)		\
+	__list_for_each_entry_mutable_from(pos, __UNIQUE_ID(next),	\
+					   head, member)
+
 /**
  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
+ *	of the current entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @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.
+ * of the current entry.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable_reverse() instead.
  */
 #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
 	for (pos = list_last_entry(head, typeof(*pos), member),		\
@@ -591,6 +697,27 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head); 					\
 	     pos = n, n = list_prev_entry(n, member))
 
+#define __list_for_each_entry_mutable_reverse(pos, tmp, head, member)	\
+	for (typeof(pos) tmp = list_prev_entry(pos =			\
+		list_last_entry(head, typeof(*pos), member), member);	\
+	     &pos->member != (head);					\
+	     pos = tmp, tmp = list_prev_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable_reverse - iterate backwards over list safe
+ *	against removal of the current entry with an internal temporary cursor
+ * @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 the current entry.
+ */
+#define list_for_each_entry_mutable_reverse(pos, head, member)		\
+	__list_for_each_entry_mutable_reverse(pos,			\
+					      __UNIQUE_ID(prev),		\
+					      head, 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
@@ -717,10 +844,33 @@ static inline void hlist_move_list(struct hlist_head *old,
 #define hlist_for_each(pos, head) \
 	for (pos = (head)->first; pos ; pos = pos->next)
 
+/**
+ * hlist_for_each_safe - iterate over a hlist safe against removal of the
+ *	current entry with a caller-provided temporary cursor
+ * @pos:	the &struct hlist_node to use as a loop cursor.
+ * @n:		another &struct hlist_node to use as temporary storage.
+ * @head:	the head for your hlist.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * hlist_for_each_mutable() instead.
+ */
 #define hlist_for_each_safe(pos, n, head) \
 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 	     pos = n)
 
+#define __hlist_for_each_mutable(pos, tmp, head)			\
+	for (typeof(pos) tmp = (pos = (head)->first) ? pos->next : NULL;\
+	     pos; pos = tmp, tmp = pos ? pos->next : NULL)
+
+/**
+ * hlist_for_each_mutable - iterate over a hlist safe against removal of the
+ *	current entry with an internal temporary cursor
+ * @pos:	the &struct hlist_node to use as a loop cursor.
+ * @head:	the head for your hlist.
+ */
+#define hlist_for_each_mutable(pos, head)				\
+	__hlist_for_each_mutable(pos, __UNIQUE_ID(next), head)
+
 #define hlist_entry_safe(ptr, type, member) \
 	({ typeof(ptr) ____ptr = (ptr); \
 	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
@@ -757,17 +907,39 @@ static inline void hlist_move_list(struct hlist_head *old,
 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 
 /**
- * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * hlist_for_each_entry_safe - iterate over list of given type safe against
+ *	removal of the current entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another &struct hlist_node to use as temporary storage
  * @head:	the head for your list.
  * @member:	the name of the hlist_node within the struct.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * hlist_for_each_entry_mutable() instead.
  */
 #define hlist_for_each_entry_safe(pos, n, head, member) 		\
 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
 	     pos && ({ n = pos->member.next; 1; });			\
 	     pos = hlist_entry_safe(n, typeof(*pos), member))
 
+#define __hlist_for_each_entry_mutable(pos, tmp, head, member)		\
+	for (struct hlist_node *tmp = (pos =				\
+		hlist_entry_safe((head)->first, typeof(*pos), member)) ? \
+		pos->member.next : NULL;					\
+	     pos;							\
+	     pos = hlist_entry_safe(tmp, typeof(*pos), member),		\
+		tmp = pos ? pos->member.next : NULL)
+
+/**
+ * hlist_for_each_entry_mutable - iterate over hlist safe against removal of
+ *	the current entry with an internal temporary cursor
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your hlist.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_mutable(pos, head, member)			\
+	__hlist_for_each_entry_mutable(pos, __UNIQUE_ID(next), head, member)
+
 /**
  * list_del_range - deletes range of entries from list.
  * @begin: first element in the range to delete from the list.
-- 
2.43.0

[PATCH v4 4/4] scripts/list: Add mutable iterator variants

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

The kernel has added mutable iterator variants, so sync the scripts/list
implementation accordingly. The safe iterators require callers to declare
and pass a temporary cursor even when the loop body only needs to remove
the current entry.

Add list_for_each_entry_mutable() and hlist_for_each_entry_mutable() so
callers can use removal-safe iteration without exposing the temporary
cursor. Keep the existing safe variants for users that need direct access
to the cursor, and document the distinction.

Add local __PASTE() and __UNIQUE_ID() helpers to generate the internal
cursor name, matching the format used by include/linux/compiler.h.

Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>
---
 scripts/include/list.h | 56 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 54 insertions(+), 2 deletions(-)

diff --git a/scripts/include/list.h b/scripts/include/list.h
index 8bdcaadca709..ff1c84339344 100644
--- a/scripts/include/list.h
+++ b/scripts/include/list.h
@@ -9,6 +9,16 @@
 /* Are two types/vars the same type (ignoring qualifiers)? */
 #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
 
+#ifndef __PASTE
+/* Indirect macros required for expanded argument pasting, eg. __LINE__. */
+#define ___PASTE(a, b) a##b
+#define __PASTE(a, b) ___PASTE(a, b)
+#endif
+
+#ifndef __UNIQUE_ID
+#define __UNIQUE_ID(name) __PASTE(__UNIQUE_ID_, __PASTE(name, __PASTE(_, __COUNTER__)))
+#endif
+
 /**
  * container_of - cast a member of a structure out to the containing structure
  * @ptr:	the pointer to the member.
@@ -298,11 +308,15 @@ static inline int list_empty(const struct list_head *head)
 	     pos = list_prev_entry(pos, member))
 
 /**
- * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry
+ * list_for_each_entry_safe - iterate over list of given type safe against
+ *	removal of list entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		another type * to use as temporary storage
  * @head:	the head for your list.
  * @member:	the name of the list_head within the struct.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * list_for_each_entry_mutable() instead.
  */
 #define list_for_each_entry_safe(pos, n, head, member)			\
 	for (pos = list_first_entry(head, typeof(*pos), member),	\
@@ -310,6 +324,22 @@ static inline int list_empty(const struct list_head *head)
 	     !list_entry_is_head(pos, head, member);			\
 	     pos = n, n = list_next_entry(n, member))
 
+#define __list_for_each_entry_mutable(pos, tmp, head, member)		\
+	for (typeof(pos) tmp = list_next_entry(pos =			\
+		list_first_entry(head, typeof(*pos), member), member);	\
+	     !list_entry_is_head(pos, head, member);			\
+	     pos = tmp, tmp = list_next_entry(tmp, member))
+
+/**
+ * list_for_each_entry_mutable - iterate over a list safe against removal of
+ *	list entry with an internal temporary cursor
+ * @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)			\
+	__list_for_each_entry_mutable(pos, __UNIQUE_ID(next), head, member)
+
 /*
  * Double linked lists with a single pointer list head.
  * Mostly useful for hash tables where the two pointer list head is
@@ -414,15 +444,37 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 
 /**
- * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * hlist_for_each_entry_safe - iterate over list of given type safe against
+ *	removal of list entry with a caller-provided temporary cursor
  * @pos:	the type * to use as a loop cursor.
  * @n:		a &struct hlist_node to use as temporary storage
  * @head:	the head for your list.
  * @member:	the name of the hlist_node within the struct.
+ *
+ * If the caller does not need to access the temporary cursor, use
+ * hlist_for_each_entry_mutable() instead.
  */
 #define hlist_for_each_entry_safe(pos, n, head, member) 		\
 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
 	     pos && ({ n = pos->member.next; 1; });			\
 	     pos = hlist_entry_safe(n, typeof(*pos), member))
 
+#define __hlist_for_each_entry_mutable(pos, tmp, head, member)		\
+	for (struct hlist_node *tmp = (pos =				\
+		hlist_entry_safe((head)->first, typeof(*pos), member)) ? \
+		pos->member.next : NULL;				\
+	     pos;							\
+	     pos = hlist_entry_safe(tmp, typeof(*pos), member),		\
+		tmp = pos ? pos->member.next : NULL)
+
+/**
+ * hlist_for_each_entry_mutable - iterate over hlist safe against removal of
+ *	list entry with an internal temporary cursor
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your hlist.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_mutable(pos, head, member)			\
+	__hlist_for_each_entry_mutable(pos, __UNIQUE_ID(next), head, member)
+
 #endif /* LIST_H */
-- 
2.43.0