Prepare mutable list iterators to cache cursor state
v4 cover Prepare mutable list iterators to cache cursor state
From: Kaitao Cheng <[email protected]>
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/[email protected]/
Link to v2:
https://lore.kernel.org/all/[email protected]/
Link to v1:
https://lore.kernel.org/all/[email protected]/
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(-)
Signature · 1 line
2.43.0
PATCH v4 1/4 list: Add mutable iterator variants
From: Kaitao Cheng <[email protected]>
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.
--- include/linux/list.h | 180 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 175 insertions(+), 5 deletions(-)
include/linux/list.h +175 -5
@@ -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.
Signature · 1 line
2.43.0
PATCH v4 2/4 llist: Add mutable iterator variants
In reply to Kaitao ChengFrom: Kaitao Cheng <[email protected]>
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.
--- include/linux/llist.h | 67 ++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 63 insertions(+), 4 deletions(-)
include/linux/llist.h +63 -4
@@ -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
Signature · 1 line
2.43.0
PATCH v4 3/4 tools/list: Add mutable iterator variants
In reply to Kaitao ChengFrom: Kaitao Cheng <[email protected]>
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.
--- tools/include/linux/compiler.h | 2 + tools/include/linux/list.h | 184 +++++++++++++++++++++++++++++++-- 2 files changed, 180 insertions(+), 6 deletions(-)
tools/include/linux/compiler.h +2 -0
@@ -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) \
tools/include/linux/list.h +178 -6
292 lines not on this page · raw message
Signature · 1 line
2.43.0
PATCH v4 4/4 scripts/list: Add mutable iterator variants
In reply to Kaitao ChengFrom: Kaitao Cheng <[email protected]>
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.
--- scripts/include/list.h | 56 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 54 insertions(+), 2 deletions(-)
scripts/include/list.h +54 -2
@@ -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 */
Signature · 1 line
2.43.0
Quoted 16 lines · On Thu, 30 Jul 2026 17:50:32 +0800 Kaitao Cheng <[email protected]> wrote:
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.
Quoted 4 lines
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.
I can't say I'm very motivated about this proposal, sorry.
It adds nearly 500 lines of tricky new macros.
It churns ancient interfaces which have more than 6,000 callsites. Are maintainers to spend the next decade receiving "switch to *_mutable" cleanups?
Unless I'm missing something here, my vote is to let it be and go do more productive things.
Re: [PATCH v4 1/4] list: Add mutable iterator variants
In reply to Kaitao ChengHi,
Quoted 30 lines · Kaitao Cheng
From: Kaitao Cheng <[email protected]>
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 <[email protected]>---
include/linux/list.h | 180 +++++++++++++++++++++++++++++++++++++++++--1 file changed, 175 insertions(+), 5 deletions(-)include/linux/list.h +0
-0@@ -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 &structlist_headto use as a loop cursor.
Quoted 8 lines
* @n: another &struct
list_headto 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.
*/
#definelist_for_each_safe(pos, n, head)\
I as a reader would probably be confused by this. What temporary cursor? pos? n?
I tend to agree with Andrew's comment, that we would have to wonder how much of an improvement more functions to choose from are, when considering the cost-benefit-ratio.
Sure the temporary variables are often not needed, but sometimes APIs are (have to be) just like that. With spin_lock_irqsave() you're also forced to carry an integer around that you yourself never need.
Philipp
Re: [PATCH v4 1/4] list: Add mutable iterator variants
Quoted 1 line · Philipp Stanner
On Thu, 2026-07-30 at 17:50 +0800, Kaitao Cheng wrote:
...
Quoted 2 lines
With
spin_lock_irqsave()you're also
forced to carry an integer around that you yourself never need.
Maybe not the best example since we have cleanup.h :-)
Signature · 2 lines
With Best Regards, Andy Shevchenko