Skip to contentSkip to conversation

list: Add safe entry iterators without an explicit n cursor

PATCH In review Kaitao Cheng 4 participants 4 messages May 29 – Jun 2 Kbuild

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 list: Add safe entry iterators without an explicit n cursor

From: Kaitao Cheng <[email protected]>

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.

---
 include/linux/list.h       | 60 ++++++++++++++++++++++++++++++++++++++
 scripts/include/list.h     | 13 +++++++++
 tools/include/linux/list.h | 60 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 133 insertions(+)
include/linux/list.h +60 -0
index 09d979976b3b..d3597da3e952 100644
@@ -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
scripts/include/list.h +13 -0
index 8bdcaadca709..ab84e3f70793 100644
@@ -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.
tools/include/linux/list.h +60 -0

84 lines not on this page · raw message

Signature · 1 line
2.50.1 (Apple Git-155)
#1 lore raw
Quoted 10 lines · On Fri, 29 May 2026 16:21:49 +0800 Kaitao Cheng <[email protected]> wrote:

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.

Quoted 8 lines

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.

Oh boy, this is a whole bunch of inscrutable macro magic and AI review
(https://sashiko.dev/#/patchset/[email protected])
is suggesting that it become even moreso.

I suggest that some patches which _use_ these macros would help to demonstrate the value. And perhaps use of a clever regexp which tells us how many sites might benefit.

#2 lore raw
In reply to Kaitao Cheng
Quoted 12 lines · Kaitao Cheng

From: Kaitao Cheng <[email protected]>

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.

Quoted 5 lines

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

On the contrary, it might be better to modify list_for_each_entry() itself. This prevents us from introducing multiple new interfaces, which could be overwhelming and confusing for new users.

If we do this, almost most callers of list_for_each_entry_safe() can be replaced by list_for_each_entry(), as the new modification enables it to properly handle the removal of the current loop cursor. As you'd expect, this would simplify usage to some extent by eliminating the need to pass a temporary variable.

Quoted 7 lines

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.

I used an AI to scan the entire repository, and the results are as follows (analyzed based on commit e98d21c170b0):

There are 9,925 list_for_each_entry() call sites in total. Among them, 9,919 do not require any adaptation, and only 6 need to be refactored:

• sound/soc/soc-dapm.c:258
• drivers/firewire/core-topology.c:275
• drivers/gpu/drm/i915/i915_scheduler.c:193
• drivers/gpu/drm/ttm/ttm_execbuf_util.c:89
• kernel/locking/locktorture.c:647
• kernel/locking/test-ww_mutex.c:522

As for list_for_each_entry_safe(), there are 4,572 callers. 4,550 of them can be directly replaced by the new list_for_each_entry(), while 22 cannot be replaced:

• drivers/gpio/gpiolib.c:527
• drivers/gpu/drm/i915/gem/i915_gem_context.c:1437
• drivers/gpu/drm/i915/gem/i915_gem_object.c:249
• drivers/gpu/drm/i915/gt/intel_gt_requests.c:143
• drivers/gpu/drm/i915/gt/intel_timeline.c:423
• drivers/gpu/drm/i915/i915_perf.c:2715
• drivers/gpu/drm/i915/pxp/intel_pxp.c:501
• drivers/gpu/drm/ttm/ttm_execbuf_util.c:90
• drivers/net/ethernet/mellanox/mlxsw/spectrum_router.c:7762
• drivers/net/wireless/marvell/mwifiex/init.c:559
• drivers/net/wireless/mediatek/mt76/mt7915/mac.c:2195
• drivers/net/wireless/mediatek/mt76/mt7996/mac.c:3066
• drivers/scsi/lpfc/lpfc_hbadisc.c:2574
• drivers/target/iscsi/iscsi_target.c:4693
• drivers/usb/c67x00/c67x00-sched.c:985
• drivers/usb/isp1760/isp1760-hcd.c:1060
• fs/btrfs/extent-tree.c:4666
• kernel/locking/locktorture.c:647
• kernel/locking/test-ww_mutex.c:522
• kernel/rcu/tasks.h:1059
• mm/page_reporting.c:183
• mm/shmem.c:1552"

During the AI's retrieval process, I noticed that it writes a script to perform a simple syntax analysis. This script filters out call sites within loops that don't involve any modifications to the list being iterated over (such as add, del, or move). In fact, this already eliminates the vast majority of call sites. As a result, there are very few instances that require manual or AI verification, which significantly improves the reliability of the AI's analysis.

"Of course, the results above are just for reference, and there's no guarantee that the AI won't miss something. My suggestion is to have the AI write the script first. Once we human-verify that the script is correct, we can run it to collect the remaining call sites that need manual review. After that, the AI can assist us in analyzing those remaining sites to minimize the risk of introducing new issues.

Muchun
Thanks

#3 lore raw
Quoted 12 lines · Muchun Song
Quoted 12 lines · Kaitao Cheng

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.

Quoted 5 lines
Quoted 1 line

Do not fold this behavior into list_for_each_entry(). That iterator

On the contrary, it might be better to modify list_for_each_entry() itself. This prevents us from introducing multiple new interfaces, which could be overwhelming and confusing for new users.

+1 here.

Quoted 62 lines

If we do this, almost most callers of list_for_each_entry_safe() can be replaced by list_for_each_entry(), as the new modification enables it to properly handle the removal of the current loop cursor. As you'd expect, this would simplify usage to some extent by eliminating the need to pass a temporary variable.

Quoted 7 lines

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.

I used an AI to scan the entire repository, and the results are as follows (analyzed based on commit e98d21c170b0):

There are 9,925 list_for_each_entry() call sites in total. Among them, 9,919 do not require any adaptation, and only 6 need to be refactored:

• sound/soc/soc-dapm.c:258
• drivers/firewire/core-topology.c:275
• drivers/gpu/drm/i915/i915_scheduler.c:193
• drivers/gpu/drm/ttm/ttm_execbuf_util.c:89
• kernel/locking/locktorture.c:647
• kernel/locking/test-ww_mutex.c:522

As for list_for_each_entry_safe(), there are 4,572 callers. 4,550 of them can be directly replaced by the new list_for_each_entry(), while 22 cannot be replaced:

• drivers/gpio/gpiolib.c:527
• drivers/gpu/drm/i915/gem/i915_gem_context.c:1437
• drivers/gpu/drm/i915/gem/i915_gem_object.c:249
• drivers/gpu/drm/i915/gt/intel_gt_requests.c:143
• drivers/gpu/drm/i915/gt/intel_timeline.c:423
• drivers/gpu/drm/i915/i915_perf.c:2715
• drivers/gpu/drm/i915/pxp/intel_pxp.c:501
• drivers/gpu/drm/ttm/ttm_execbuf_util.c:90
• drivers/net/ethernet/mellanox/mlxsw/spectrum_router.c:7762
• drivers/net/wireless/marvell/mwifiex/init.c:559
• drivers/net/wireless/mediatek/mt76/mt7915/mac.c:2195
• drivers/net/wireless/mediatek/mt76/mt7996/mac.c:3066
• drivers/scsi/lpfc/lpfc_hbadisc.c:2574
• drivers/target/iscsi/iscsi_target.c:4693
• drivers/usb/c67x00/c67x00-sched.c:985
• drivers/usb/isp1760/isp1760-hcd.c:1060
• fs/btrfs/extent-tree.c:4666
• kernel/locking/locktorture.c:647
• kernel/locking/test-ww_mutex.c:522
• kernel/rcu/tasks.h:1059
• mm/page_reporting.c:183
• mm/shmem.c:1552"

During the AI's retrieval process, I noticed that it writes a script to perform a simple syntax analysis. This script filters out call sites within loops that don't involve any modifications to the list being iterated over (such as add, del, or move). In fact, this already eliminates the vast majority of call sites. As a result, there are very few instances that require manual or AI verification, which significantly improves the reliability of the AI's analysis.

Quoted 6 lines

"Of course, the results above are just for reference, and there's no guarantee that the AI won't miss something. My suggestion is to have the AI write the script first. Once we human-verify that the script is correct, we can run it to collect the remaining call sites that need manual review. After that, the AI can assist us in analyzing those remaining sites to minimize the risk of introducing new issues.

Do not forget that we have coccinelle and semantic grep & patch.

Signature · 2 lines
With Best Regards,
Andy Shevchenko