Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop

[Linus Torvalds]

On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds
<torvalds@xxxxxxxxxxxxxxxxxxxx> wrote:
>
> Now, I'd love for the list head entry itself to "declare the type",
> and solve it that way. That would in many ways be the optimal
> situation, in that when a structure has that
>
>         struct list_head xyz;
>
> entry, it would be lovely to declare *there* what the list entry type
> is - and have 'list_for_each_entry()' just pick it up that way.
>
> It would be doable in theory - with some preprocessor trickery [...]

Ok, I decided to look at how that theory looks in real life.

The attached patch does actually work for me. I'm not saying this is
*beautiful*, but I made the changes to kernel/exit.c to show how this
can be used, and while the preprocessor tricks and the odd "unnamed
union with a special member to give the target type" is all kinds of
hacky, the actual use case code looks quite nice.

In particular, look at the "good case" list_for_each_entry() transformation:

   static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk)
   {
  -     struct task_struct *p;
  -
  -     list_for_each_entry(p, &tsk->children, sibling) {
  +     list_traverse(p, &tsk->children, sibling) {

IOW, it avoided the need to declare 'p' entirely, and it avoids the
need for a type, because the macro now *knows* the type of that
'tsk->children' list and picks it out automatically.

So 'list_traverse()' is basically a simplified version of
'list_for_each_entry()'.

That patch also has - as another example - the "use outside the loop"
case in mm_update_next_owner(). That is more of a "rewrite the loop
cleanly using list_traverse() thing, but it's also quite simple and
natural.

One nice part of this approach is that it allows for incremental changes.

In fact, the patch very much is meant to demonstrate exactly that:
yes, it converts the uses in kernel/exit.c, but it does *not* convert
the code in kernel/fork.c, which still does that old-style traversal:

                list_for_each_entry(child, &parent->children, sibling) {

and the kernel/fork.c code continues to work as well as it ever did.

So that new 'list_traverse()' function allows for people to say "ok, I
will now declare that list head with that list_traversal_head() macro,
and then I can convert 'list_for_each_entry()' users one by one to
this simpler syntax that also doesn't allow the list iterator to be
used outside the list.

What do people think? Is this clever and useful, or just too subtle
and odd to exist?

NOTE! I decided to add that "name of the target head in the target
type" to the list_traversal_head() macro, but it's not actually used
as is. It's more of a wishful "maybe we could add some sanity checking
of the target list entries later".

Comments?

                   Linus
 Makefile              |  2 +-
 include/linux/list.h  | 14 ++++++++++++++
 include/linux/sched.h |  4 ++--
 kernel/exit.c         | 28 ++++++++++++++--------------
 4 files changed, 31 insertions(+), 17 deletions(-)

diff --git a/Makefile b/Makefile
index daeb5c88b50b..cc4b0a266af0 100644
--- a/Makefile
+++ b/Makefile
@@ -515,7 +515,7 @@ KBUILD_CFLAGS   := -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs \
 		   -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE \
 		   -Werror=implicit-function-declaration -Werror=implicit-int \
 		   -Werror=return-type -Wno-format-security \
-		   -std=gnu89
+		   -std=gnu11
 KBUILD_CPPFLAGS := -D__KERNEL__
 KBUILD_AFLAGS_KERNEL :=
 KBUILD_CFLAGS_KERNEL :=
diff --git a/include/linux/list.h b/include/linux/list.h
index dd6c2041d09c..1e8b3e495b51 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -25,6 +25,9 @@
 #define LIST_HEAD(name) \
 	struct list_head name = LIST_HEAD_INIT(name)
 
+#define list_traversal_head(type,name,target_member) \
+	union { struct list_head name; type *name##_traversal_type; }
+
 /**
  * INIT_LIST_HEAD - Initialize a list_head structure
  * @list: list_head structure to be initialized.
@@ -628,6 +631,17 @@ static inline void list_splice_tail_init(struct list_head *list,
 #define list_entry_is_head(pos, head, member)				\
 	(&pos->member == (head))
 
+/**
+ * list_traverse - iterate over a typed list
+ * @pos:	the name to use for the loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the type.
+ */
+#define list_traverse(pos, head, member) \
+	for (typeof(*head##_traversal_type) pos = list_first_entry(head, typeof(*pos), member); \
+		!list_entry_is_head(pos, head, member);	\
+		pos = list_next_entry(pos, member))
+
 /**
  * list_for_each_entry	-	iterate over list of given type
  * @pos:	the type * to use as a loop cursor.
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 75ba8aa60248..55e60405da1c 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -965,7 +965,7 @@ struct task_struct {
 	/*
 	 * Children/sibling form the list of natural children:
 	 */
-	struct list_head		children;
+	list_traversal_head(struct task_struct, children, sibling);
 	struct list_head		sibling;
 	struct task_struct		*group_leader;
 
@@ -975,7 +975,7 @@ struct task_struct {
 	 * This includes both natural children and PTRACE_ATTACH targets.
 	 * 'ptrace_entry' is this task's link on the p->parent->ptraced list.
 	 */
-	struct list_head		ptraced;
+	list_traversal_head(struct task_struct, ptraced, ptrace_entry);
 	struct list_head		ptrace_entry;
 
 	/* PID/PID hash table linkage. */
diff --git a/kernel/exit.c b/kernel/exit.c
index b00a25bb4ab9..c85cb1a6bec2 100644
--- a/kernel/exit.c
+++ b/kernel/exit.c
@@ -409,17 +409,21 @@ void mm_update_next_owner(struct mm_struct *mm)
 	/*
 	 * Search in the children
 	 */
-	list_for_each_entry(c, &p->children, sibling) {
-		if (c->mm == mm)
-			goto assign_new_owner;
+	list_traverse(pos, &p->children, sibling) {
+		if (pos->mm != mm)
+			continue;
+		c = pos;
+		goto assign_new_owner;
 	}
 
 	/*
 	 * Search in the siblings
 	 */
-	list_for_each_entry(c, &p->real_parent->children, sibling) {
-		if (c->mm == mm)
-			goto assign_new_owner;
+	list_traverse(pos, &p->real_parent->children, sibling) {
+		if (pos->mm != mm)
+			continue;
+		c = pos;
+		goto assign_new_owner;
 	}
 
 	/*
@@ -628,7 +632,7 @@ static void reparent_leader(struct task_struct *father, struct task_struct *p,
 static void forget_original_parent(struct task_struct *father,
 					struct list_head *dead)
 {
-	struct task_struct *p, *t, *reaper;
+	struct task_struct *t, *reaper;
 
 	if (unlikely(!list_empty(&father->ptraced)))
 		exit_ptrace(father, dead);
@@ -639,7 +643,7 @@ static void forget_original_parent(struct task_struct *father,
 		return;
 
 	reaper = find_new_reaper(father, reaper);
-	list_for_each_entry(p, &father->children, sibling) {
+	list_traverse(p, &father->children, sibling) {
 		for_each_thread(p, t) {
 			RCU_INIT_POINTER(t->real_parent, reaper);
 			BUG_ON((!t->ptrace) != (rcu_access_pointer(t->parent) == father));
@@ -1405,9 +1409,7 @@ static int wait_consider_task(struct wait_opts *wo, int ptrace,
  */
 static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk)
 {
-	struct task_struct *p;
-
-	list_for_each_entry(p, &tsk->children, sibling) {
+	list_traverse(p, &tsk->children, sibling) {
 		int ret = wait_consider_task(wo, 0, p);
 
 		if (ret)
@@ -1419,9 +1421,7 @@ static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk)
 
 static int ptrace_do_wait(struct wait_opts *wo, struct task_struct *tsk)
 {
-	struct task_struct *p;
-
-	list_for_each_entry(p, &tsk->ptraced, ptrace_entry) {
+	list_traverse(p, &tsk->ptraced, ptrace_entry) {
 		int ret = wait_consider_task(wo, 1, p);
 
 		if (ret)