2022-03-01 09:20:11

by Xiaomeng Tong

[permalink] [raw]
Subject: [PATCH 0/6] list_for_each_entry*: make iterator invisiable outside the loop

In this discuss[1], linus proposed a idea to solve the use-after-iter
problem caused by the inappropriate iterator variable use of
list_for_each_entry* macros *outside* the loop.

The core of the idea is that make the rule be "you never use the iterator
outside the loop".
The perfect way should be "you are prohibited by the compiler from using
iterator variable outside the loop". Thus, we can declare the iterator
variable inside the loop and any use of iterator outside the loop will
be report as a error by compiler.

"declare the iterator variable inside the *for* loop" needs something
above gnu89 (like -std=gnu11), which is the task of PATCH 1.

The core patch of this series is PATCH 2, which respectively implements
a new iterator-inside macro for each list_for_each_entry* macro (10
variants). The name of the new macro is suffixed with *_inside*, such as
list_for_each_entry_inside for list_for_each_entry.

The reason for a new macro instead of directly modification on origin
macro is that, there are 15000+ callers of there macros scattered in
the whole kernel code. We cannot change all of these correctly in one
single patch considering that it must be correct for each commit. Thus,
we can define a new macro, and incrementally change these callers until
all these in the kernel are completely updated with *_inside* one. At
that time, we can just remove the implements of origin macros and rename
the *_inside* macro back to the origin name just in one single patch.

The PATCH 3~6 demonstrate how to change list_for_each_entry* callers into
*_inside one. Note all these 4 patch are just to prove the effectiveness
of the scheme for each list_for_each_entry* macro (10 variants). I think
the reasonable way is to kill all these 15000+ callers *on a file basis*,
considering that different macros may be called in the same context and
depend on each other, instead of *on a separate macro basis*.

[1]: https://lore.kernel.org/all/CAHk-=wgRr_D8CB-D9Kg-c=EHreAsk5SqXPwr9Y7k9sA6cWXJ6w@mail.gmail.com/

Xiaomeng Tong (6):
Kbuild: compile kernel with gnu11 std
list: add new MACROs to make iterator invisiable outside the loop
kernel: remove iterator use outside the loop
mm: remove iterator use outside the loop
net/core: remove iterator use outside the loop
drivers/dma: remove iterator use outside the loop

Makefile | 2 +-
drivers/dma/iop-adma.c | 9 +--
include/linux/list.h | 156 ++++++++++++++++++++++++++++++++++++++++
kernel/power/snapshot.c | 28 ++++----
kernel/signal.c | 6 +-
mm/list_lru.c | 10 +--
mm/slab_common.c | 7 +-
mm/vmalloc.c | 6 +-
net/core/gro.c | 3 +-
9 files changed, 191 insertions(+), 36 deletions(-)

--
2.17.1


2022-03-01 09:30:21

by Xiaomeng Tong

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

For each list_for_each_entry* macros(10 variants), implements a respective
new *_inside one. Such as the new macro list_for_each_entry_inside for
list_for_each_entry. The idea is to be as compatible with the original
interface as possible and to minimize code changes.

Here are 2 examples:

list_for_each_entry_inside:
- declare the iterator-variable pos inside the loop. Thus, the origin
declare of the inputed *pos* outside the loop should be removed. In
other words, the inputed *pos* now is just a string name.
- add a new "type" argument as the type of the container struct this is
embedded in, and should be inputed when calling the macro.

list_for_each_entry_safe_continue_inside:
- declare the iterator-variable pos and n inside the loop. Thus, the
origin declares of the inputed *pos* and *n* outside the loop should
be removed. In other words, the inputed *pos* and *n* now are just
string name.
- add a new "start" argument as the given iterator to start with and
can be used to get the container struct *type*. This should be inputed
when calling the macro.

Signed-off-by: Xiaomeng Tong <[email protected]>
---
include/linux/list.h | 156 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 156 insertions(+)

diff --git a/include/linux/list.h b/include/linux/list.h
index dd6c2041d..1595ce865 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -639,6 +639,19 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))

+/**
+ * list_for_each_entry_inside
+ * - iterate over list of given type and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @type: the type of the container struct this is embedded in.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_for_each_entry_inside(pos, type, head, member) \
+ for (type * pos = list_first_entry(head, type, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_next_entry(pos, member))
+
/**
* list_for_each_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop cursor.
@@ -650,6 +663,19 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = list_prev_entry(pos, member))

+/**
+ * list_for_each_entry_reverse_inside
+ * - iterate backwards over list of given type and keep iterator inside the loop.
+ * @pos: the type * to use as a loop cursor.
+ * @type: the type of the container struct this is embedded in.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_for_each_entry_reverse_inside(pos, type, head, member) \
+ for (type * pos = list_last_entry(head, type, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_prev_entry(pos, member))
+
/**
* list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
* @pos: the type * to use as a start point
@@ -675,6 +701,22 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))

+/**
+ * list_for_each_entry_continue_inside
+ * - continue iteration over list of given type and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @start: the given iterator to start with.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ *
+ * Continue to iterate over list of given type, continuing after
+ * the current position.
+ */
+#define list_for_each_entry_continue_inside(pos, start, head, member) \
+ for (typeof(*start) *pos = list_next_entry(start, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_next_entry(pos, member))
+
/**
* list_for_each_entry_continue_reverse - iterate backwards from the given point
* @pos: the type * to use as a loop cursor.
@@ -689,6 +731,22 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = list_prev_entry(pos, member))

+/**
+ * list_for_each_entry_continue_reverse_inside
+ * - iterate backwards from the given point and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @start: the given iterator to start with.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ *
+ * Start to iterate over list of given type backwards, continuing after
+ * the current position.
+ */
+#define list_for_each_entry_continue_reverse_inside(pos, start, head, member) \
+ for (typeof(*start) *pos = list_prev_entry(start, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_prev_entry(pos, member))
+
/**
* list_for_each_entry_from - iterate over list of given type from the current point
* @pos: the type * to use as a loop cursor.
@@ -701,6 +759,20 @@ static inline void list_splice_tail_init(struct list_head *list,
for (; !list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))

+/**
+ * list_for_each_entry_from_inside
+ * - iterate over list of given type from the current point and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @start: the given iterator to start with.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ *
+ * Iterate over list of given type, continuing from current position.
+ */
+#define list_for_each_entry_from_inside(pos, start, head, member) \
+ for (typeof(*start) *pos = start; !list_entry_is_head(pos, head, member); \
+ pos = list_next_entry(pos, member))
+
/**
* list_for_each_entry_from_reverse - iterate backwards over list of given type
* from the current point
@@ -714,6 +786,21 @@ static inline void list_splice_tail_init(struct list_head *list,
for (; !list_entry_is_head(pos, head, member); \
pos = list_prev_entry(pos, member))

+/**
+ * list_for_each_entry_from_reverse_inside
+ * - iterate backwards over list of given type from the current point
+ * and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @start: the given iterator to start with.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ *
+ * Iterate backwards over list of given type, continuing from current position.
+ */
+#define list_for_each_entry_from_reverse_inside(pos, start, head, member) \
+ for (typeof(*start) *pos = start; !list_entry_is_head(pos, head, member); \
+ pos = list_prev_entry(pos, member))
+
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop cursor.
@@ -727,6 +814,22 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))

+/**
+ * list_for_each_entry_safe_inside
+ * - iterate over list of given type safe against removal of list entry
+ * and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @type: the type of the container struct this is embedded in.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_for_each_entry_safe_inside(pos, n, type, head, member) \
+ for (type * pos = list_first_entry(head, type, member), \
+ *n = list_next_entry(pos, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = n, n = list_next_entry(n, member))
+
/**
* list_for_each_entry_safe_continue - continue list iteration safe against removal
* @pos: the type * to use as a loop cursor.
@@ -743,6 +846,24 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))

+/**
+ * list_for_each_entry_safe_continue_inside
+ * - continue list iteration safe against removal and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @start: the given iterator to start with.
+ * @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_safe_continue_inside(pos, n, start, head, member) \
+ for (typeof(*start) *pos = list_next_entry(start, member), \
+ *n = list_next_entry(pos, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = n, n = list_next_entry(n, 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.
@@ -758,6 +879,23 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))

+/**
+ * list_for_each_entry_safe_from_inside
+ * - iterate over list from current point safe against removal and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @start: the given iterator to start with.
+ * @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_safe_from_inside(pos, n, start, head, member) \
+ for (typeof(*start) *pos = start, *n = list_next_entry(pos, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = n, n = list_next_entry(n, member))
+
/**
* list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
* @pos: the type * to use as a loop cursor.
@@ -774,6 +912,24 @@ static inline void list_splice_tail_init(struct list_head *list,
!list_entry_is_head(pos, head, member); \
pos = n, n = list_prev_entry(n, member))

+/**
+ * list_for_each_entry_safe_reverse_insde
+ * - iterate backwards over list safe against removal and keep iterator inside the loop
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @type: the type of the struct this is enmbeded in.
+ * @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_safe_reverse_inside(pos, n, type, head, member) \
+ for (type * pos = list_last_entry(head, type, member), \
+ *n = list_prev_entry(pos, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = n, n = list_prev_entry(n, member))
+
/**
* list_safe_reset_next - reset a stale list_for_each_entry_safe loop
* @pos: the loop cursor used in the list_for_each_entry_safe loop
--
2.17.1

2022-03-01 09:30:22

by Xiaomeng Tong

[permalink] [raw]
Subject: [PATCH 6/6] drivers/dma: remove iterator use outside the loop

Demonstrations for:
- list_for_each_entry_from_inside
- list_for_each_entry_safe_from_inside

Signed-off-by: Xiaomeng Tong <[email protected]>
---
drivers/dma/iop-adma.c | 9 +++------
1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/drivers/dma/iop-adma.c b/drivers/dma/iop-adma.c
index 310b899d5..2f326fb37 100644
--- a/drivers/dma/iop-adma.c
+++ b/drivers/dma/iop-adma.c
@@ -159,7 +159,6 @@ static void __iop_adma_slot_cleanup(struct iop_adma_chan *iop_chan)

/* all the members of a group are complete */
if (slots_per_op != 0 && slot_cnt == 0) {
- struct iop_adma_desc_slot *grp_iter, *_grp_iter;
int end_of_chain = 0;
pr_debug("\tgroup end\n");

@@ -167,9 +166,8 @@ static void __iop_adma_slot_cleanup(struct iop_adma_chan *iop_chan)
if (grp_start->xor_check_result) {
u32 zero_sum_result = 0;
slot_cnt = grp_start->slot_cnt;
- grp_iter = grp_start;

- list_for_each_entry_from(grp_iter,
+ list_for_each_entry_from_inside(grp_iter, grp_start,
&iop_chan->chain, chain_node) {
zero_sum_result |=
iop_desc_get_zero_result(grp_iter);
@@ -186,9 +184,8 @@ static void __iop_adma_slot_cleanup(struct iop_adma_chan *iop_chan)

/* clean up the group */
slot_cnt = grp_start->slot_cnt;
- grp_iter = grp_start;
- list_for_each_entry_safe_from(grp_iter, _grp_iter,
- &iop_chan->chain, chain_node) {
+ list_for_each_entry_safe_from_inside(grp_iter, _grp_iter,
+ grp_start, &iop_chan->chain, chain_node) {
cookie = iop_adma_run_tx_complete_actions(
grp_iter, iop_chan, cookie);

--
2.17.1

2022-03-01 09:36:32

by Xiaomeng Tong

[permalink] [raw]
Subject: [PATCH 3/6] kernel: remove iterator use outside the loop

Demonstrations for:
- list_for_each_entry_inside
- list_for_each_entry_continue_inside
- list_for_each_entry_safe_continue_inside

Signed-off-by: Xiaomeng Tong <[email protected]>
---
kernel/power/snapshot.c | 28 ++++++++++++++++------------
kernel/signal.c | 6 +++---
2 files changed, 19 insertions(+), 15 deletions(-)

diff --git a/kernel/power/snapshot.c b/kernel/power/snapshot.c
index 330d49937..75958b5fa 100644
--- a/kernel/power/snapshot.c
+++ b/kernel/power/snapshot.c
@@ -625,16 +625,18 @@ static int create_mem_extents(struct list_head *list, gfp_t gfp_mask)

for_each_populated_zone(zone) {
unsigned long zone_start, zone_end;
- struct mem_extent *ext, *cur, *aux;
+ struct mem_extent *me = NULL;

zone_start = zone->zone_start_pfn;
zone_end = zone_end_pfn(zone);

- list_for_each_entry(ext, list, hook)
- if (zone_start <= ext->end)
+ list_for_each_entry_inside(ext, struct mem_extent, list, hook)
+ if (zone_start <= ext->end) {
+ me = ext;
break;
+ }

- if (&ext->hook == list || zone_end < ext->start) {
+ if (!me || zone_end < me->start) {
/* New extent is necessary */
struct mem_extent *new_ext;

@@ -645,23 +647,25 @@ static int create_mem_extents(struct list_head *list, gfp_t gfp_mask)
}
new_ext->start = zone_start;
new_ext->end = zone_end;
- list_add_tail(&new_ext->hook, &ext->hook);
+ if (!me)
+ list_add_tail(&new_ext->hook, list);
+ else
+ list_add_tail(&new_ext->hook, &me->hook);
continue;
}

/* Merge this zone's range of PFNs with the existing one */
- if (zone_start < ext->start)
- ext->start = zone_start;
- if (zone_end > ext->end)
- ext->end = zone_end;
+ if (zone_start < me->start)
+ me->start = zone_start;
+ if (zone_end > me->end)
+ me->end = zone_end;

/* More merging may be possible */
- cur = ext;
- list_for_each_entry_safe_continue(cur, aux, list, hook) {
+ list_for_each_entry_safe_continue_inside(cur, aux, me, list, hook) {
if (zone_end < cur->start)
break;
if (zone_end < cur->end)
- ext->end = cur->end;
+ me->end = cur->end;
list_del(&cur->hook);
kfree(cur);
}
diff --git a/kernel/signal.c b/kernel/signal.c
index 9b04631ac..da2c20de1 100644
--- a/kernel/signal.c
+++ b/kernel/signal.c
@@ -711,7 +711,7 @@ static int dequeue_synchronous_signal(kernel_siginfo_t *info)
{
struct task_struct *tsk = current;
struct sigpending *pending = &tsk->pending;
- struct sigqueue *q, *sync = NULL;
+ struct sigqueue *sync = NULL;

/*
* Might a synchronous signal be in the queue?
@@ -722,7 +722,7 @@ static int dequeue_synchronous_signal(kernel_siginfo_t *info)
/*
* Return the first synchronous signal in the queue.
*/
- list_for_each_entry(q, &pending->list, list) {
+ list_for_each_entry_inside(q, struct sigqueue, &pending->list, list) {
/* Synchronous signals have a positive si_code */
if ((q->info.si_code > SI_USER) &&
(sigmask(q->info.si_signo) & SYNCHRONOUS_MASK)) {
@@ -735,7 +735,7 @@ static int dequeue_synchronous_signal(kernel_siginfo_t *info)
/*
* Check if there is another siginfo for the same signal.
*/
- list_for_each_entry_continue(q, &pending->list, list) {
+ list_for_each_entry_continue_inside(q, sync, &pending->list, list) {
if (q->info.si_signo == sync->info.si_signo)
goto still_pending;
}
--
2.17.1

2022-03-01 09:49:12

by Xiaomeng Tong

[permalink] [raw]
Subject: [PATCH 4/6] mm: remove iterator use outside the loop

Demonstrations for:
- list_for_each_entry_inside
- list_for_each_entry_reverse_inside
- list_for_each_entry_safe_inside
- list_for_each_entry_from_inside
- list_for_each_entry_continue_reverse_inside

Signed-off-by: Xiaomeng Tong <[email protected]>
---
mm/list_lru.c | 10 ++++++----
mm/slab_common.c | 7 ++-----
mm/vmalloc.c | 6 +++---
3 files changed, 11 insertions(+), 12 deletions(-)

diff --git a/mm/list_lru.c b/mm/list_lru.c
index 0cd5e89ca..d8aab53a7 100644
--- a/mm/list_lru.c
+++ b/mm/list_lru.c
@@ -493,20 +493,22 @@ static void memcg_cancel_update_list_lru(struct list_lru *lru,
int memcg_update_all_list_lrus(int new_size)
{
int ret = 0;
- struct list_lru *lru;
+ struct list_lru *ll = NULL;
int old_size = memcg_nr_cache_ids;

mutex_lock(&list_lrus_mutex);
- list_for_each_entry(lru, &memcg_list_lrus, list) {
+ list_for_each_entry_inside(lru, struct list_lru, &memcg_list_lrus, list) {
ret = memcg_update_list_lru(lru, old_size, new_size);
- if (ret)
+ if (ret) {
+ ll = lru;
goto fail;
+ }
}
out:
mutex_unlock(&list_lrus_mutex);
return ret;
fail:
- list_for_each_entry_continue_reverse(lru, &memcg_list_lrus, list)
+ list_for_each_entry_continue_reverse_inside(lru, ll, &memcg_list_lrus, list)
memcg_cancel_update_list_lru(lru, old_size, new_size);
goto out;
}
diff --git a/mm/slab_common.c b/mm/slab_common.c
index 23f2ab071..68a25d385 100644
--- a/mm/slab_common.c
+++ b/mm/slab_common.c
@@ -186,8 +186,6 @@ int slab_unmergeable(struct kmem_cache *s)
struct kmem_cache *find_mergeable(unsigned int size, unsigned int align,
slab_flags_t flags, const char *name, void (*ctor)(void *))
{
- struct kmem_cache *s;
-
if (slab_nomerge)
return NULL;

@@ -202,7 +200,7 @@ struct kmem_cache *find_mergeable(unsigned int size, unsigned int align,
if (flags & SLAB_NEVER_MERGE)
return NULL;

- list_for_each_entry_reverse(s, &slab_caches, list) {
+ list_for_each_entry_reverse_inside(s, struct kmem_cache, &slab_caches, list) {
if (slab_unmergeable(s))
continue;

@@ -419,7 +417,6 @@ EXPORT_SYMBOL(kmem_cache_create);
static void slab_caches_to_rcu_destroy_workfn(struct work_struct *work)
{
LIST_HEAD(to_destroy);
- struct kmem_cache *s, *s2;

/*
* On destruction, SLAB_TYPESAFE_BY_RCU kmem_caches are put on the
@@ -439,7 +436,7 @@ static void slab_caches_to_rcu_destroy_workfn(struct work_struct *work)

rcu_barrier();

- list_for_each_entry_safe(s, s2, &to_destroy, list) {
+ list_for_each_entry_safe_inside(s, s2, struct kmem_cache, &to_destroy, list) {
debugfs_slab_release(s);
kfence_shutdown_cache(s);
#ifdef SLAB_SUPPORTS_SYSFS
diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 4165304d3..65a9f1db7 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -3417,14 +3417,14 @@ long vread(char *buf, char *addr, unsigned long count)
if ((unsigned long)addr + count <= va->va_start)
goto finished;

- list_for_each_entry_from(va, &vmap_area_list, list) {
+ list_for_each_entry_from_inside(iter, va, &vmap_area_list, list) {
if (!count)
break;

- if (!va->vm)
+ if (!iter->vm)
continue;

- vm = va->vm;
+ vm = iter->vm;
vaddr = (char *) vm->addr;
if (addr >= vaddr + get_vm_area_size(vm))
continue;
--
2.17.1

2022-03-01 13:43:42

by Xiaomeng Tong

[permalink] [raw]
Subject: Re: [PATCH 3/6] kernel: remove iterator use outside the loop

On Tue, 1 Mar 2022 11:41:34 +0100, greg k-h wrote:
> On Tue, Mar 01, 2022 at 03:58:36PM +0800, Xiaomeng Tong wrote:
> > Demonstrations for:
> > - list_for_each_entry_inside
> > - list_for_each_entry_continue_inside
> > - list_for_each_entry_safe_continue_inside
>
> This changelog does not make much sense at all. Why are you making
> these changes and how are we to review them? Same for the others in
> this series.
>
> confused,

I'm sorry for have created the confusion. I made this patch to remove
the use of iterator (in this patch is "ext", "cur", "aux", "q") outside
the list_for_each_entry* loop, using the new *_inside macros instead
which are introduced in PATCH v2, and to prove the effectiveness of
the new macros.

The detail for create_mem_extents patch:

1. remove the iterator use outside the loop:
- struct mem_extent *ext, *cur, *aux;

2. declare a ptr outside the loop and set NULL:
+ struct mem_extent *me = NULL;

3. repace list_for_each_entry with list_for_each_entry_inside, and pass
a new argument (struct mem_extent) as the struct type.
+ list_for_each_entry_inside(ext, struct mem_extent, list, hook)

4. when we hit the break in list_for_each_entry, record the found iterator
for lately use:
+ if (zone_start <= ext->end) {
+ me = ext;
break;
+ }

5. when we miss the break, the "me" is NULL and can be used to determine if
we already found the "ext". And replace every "ext" use after the loop
with "me".
- if (&ext->hook == list || zone_end < ext->start) {
+ if (!me || zone_end < me->start) {


6. repace list_for_each_entry_safe_continue with
list_for_each_entry_safe_continue_inside, and pass a new argument (me)
as the iterator to start/continue with.
- list_for_each_entry_safe_continue(cur, aux, list, hook) {
+ list_for_each_entry_safe_continue_inside(cur, aux, me, list, hook) {

Best regards,
--
Xiaomeng Tong

2022-03-01 15:27:32

by Greg Kroah-Hartman

[permalink] [raw]
Subject: Re: [PATCH 3/6] kernel: remove iterator use outside the loop

On Tue, Mar 01, 2022 at 03:58:36PM +0800, Xiaomeng Tong wrote:
> Demonstrations for:
> - list_for_each_entry_inside
> - list_for_each_entry_continue_inside
> - list_for_each_entry_safe_continue_inside

This changelog does not make much sense at all. Why are you making
these changes and how are we to review them? Same for the others in
this series.

confused,

greg k-h

2022-03-01 16:07:46

by Xiaomeng Tong

[permalink] [raw]
Subject: Re: [PATCH 6/6] drivers/dma: remove iterator use outside the loop

I'm sorry for have created the confusion. I made this patch to remove
the use of iterator (in this patch is "grp_iter", "_grp_iter") outside
the list_for_each_entry* loop, using the new *_inside macros instead
which are introduced in PATCH 2/6, and to prove the effectiveness of
the new macros.

Best regards,
--
Xiaomeng Tong

2022-03-01 16:17:00

by Xiaomeng Tong

[permalink] [raw]
Subject: Re: [PATCH 3/6] kernel: remove iterator use outside the loop

typo:
which are introduced in PATCH v2,
correct:
which are introduced in PATCH 2/6,

Best regards,
--
Xiaomeng Tong

2022-03-01 18:15:03

by Xiaomeng Tong

[permalink] [raw]
Subject: Re: [PATCH 4/6] mm: remove iterator use outside the loop

I'm sorry for have created the confusion. I made this patch to remove
the use of iterator (in this patch is "lru", "s", "s", "s2") outside
the list_for_each_entry* loop, using the new *_inside macros instead
which are introduced in PATCH 2/6, and to prove the effectiveness of
the new macros.

Best regards,
--
Xiaomeng Tong

2022-03-02 08:45:12

by kernel test robot

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

Hi Xiaomeng,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on linux/master]
[also build test WARNING on vkoul-dmaengine/next soc/for-next linus/master v5.17-rc6 next-20220301]
[cannot apply to hnaz-mm/master]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url: https://github.com/0day-ci/linux/commits/Xiaomeng-Tong/list_for_each_entry-make-iterator-invisiable-outside-the-loop/20220301-160113
base: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git 2c271fe77d52a0555161926c232cd5bc07178b39
reproduce: make htmldocs

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <[email protected]>

All warnings (new ones prefixed by >>):

>> include/linux/list.h:931: warning: expecting prototype for list_for_each_entry_safe_reverse_insde(). Prototype was for list_for_each_entry_safe_reverse_inside() instead

vim +931 include/linux/list.h

557
558 /**
559 * list_next_entry - get the next element in list
560 * @pos: the type * to cursor
561 * @member: the name of the list_head within the struct.
562 */
563 #define list_next_entry(pos, member) \
564 list_entry((pos)->member.next, typeof(*(pos)), member)
565
566 /**
567 * list_prev_entry - get the prev element in list
568 * @pos: the type * to cursor
569 * @member: the name of the list_head within the struct.
570 */
571 #define list_prev_entry(pos, member) \
572 list_entry((pos)->member.prev, typeof(*(pos)), member)
573
574 /**
575 * list_for_each - iterate over a list
576 * @pos: the &struct list_head to use as a loop cursor.
577 * @head: the head for your list.
578 */
579 #define list_for_each(pos, head) \
580 for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
581
582 /**
583 * list_for_each_continue - continue iteration over a list
584 * @pos: the &struct list_head to use as a loop cursor.
585 * @head: the head for your list.
586 *
587 * Continue to iterate over a list, continuing after the current position.
588 */
589 #define list_for_each_continue(pos, head) \
590 for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
591
592 /**
593 * list_for_each_prev - iterate over a list backwards
594 * @pos: the &struct list_head to use as a loop cursor.
595 * @head: the head for your list.
596 */
597 #define list_for_each_prev(pos, head) \
598 for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
599
600 /**
601 * list_for_each_safe - iterate over a list safe against removal of list entry
602 * @pos: the &struct list_head to use as a loop cursor.
603 * @n: another &struct list_head to use as temporary storage
604 * @head: the head for your list.
605 */
606 #define list_for_each_safe(pos, n, head) \
607 for (pos = (head)->next, n = pos->next; \
608 !list_is_head(pos, (head)); \
609 pos = n, n = pos->next)
610
611 /**
612 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
613 * @pos: the &struct list_head to use as a loop cursor.
614 * @n: another &struct list_head to use as temporary storage
615 * @head: the head for your list.
616 */
617 #define list_for_each_prev_safe(pos, n, head) \
618 for (pos = (head)->prev, n = pos->prev; \
619 !list_is_head(pos, (head)); \
620 pos = n, n = pos->prev)
621
622 /**
623 * list_entry_is_head - test if the entry points to the head of the list
624 * @pos: the type * to cursor
625 * @head: the head for your list.
626 * @member: the name of the list_head within the struct.
627 */
628 #define list_entry_is_head(pos, head, member) \
629 (&pos->member == (head))
630
631 /**
632 * list_for_each_entry - iterate over list of given type
633 * @pos: the type * to use as a loop cursor.
634 * @head: the head for your list.
635 * @member: the name of the list_head within the struct.
636 */
637 #define list_for_each_entry(pos, head, member) \
638 for (pos = list_first_entry(head, typeof(*pos), member); \
639 !list_entry_is_head(pos, head, member); \
640 pos = list_next_entry(pos, member))
641
642 /**
643 * list_for_each_entry_inside
644 * - iterate over list of given type and keep iterator inside the loop
645 * @pos: the type * to use as a loop cursor.
646 * @type: the type of the container struct this is embedded in.
647 * @head: the head for your list.
648 * @member: the name of the list_head within the struct.
649 */
650 #define list_for_each_entry_inside(pos, type, head, member) \
651 for (type * pos = list_first_entry(head, type, member); \
652 !list_entry_is_head(pos, head, member); \
653 pos = list_next_entry(pos, member))
654
655 /**
656 * list_for_each_entry_reverse - iterate backwards over list of given type.
657 * @pos: the type * to use as a loop cursor.
658 * @head: the head for your list.
659 * @member: the name of the list_head within the struct.
660 */
661 #define list_for_each_entry_reverse(pos, head, member) \
662 for (pos = list_last_entry(head, typeof(*pos), member); \
663 !list_entry_is_head(pos, head, member); \
664 pos = list_prev_entry(pos, member))
665
666 /**
667 * list_for_each_entry_reverse_inside
668 * - iterate backwards over list of given type and keep iterator inside the loop.
669 * @pos: the type * to use as a loop cursor.
670 * @type: the type of the container struct this is embedded in.
671 * @head: the head for your list.
672 * @member: the name of the list_head within the struct.
673 */
674 #define list_for_each_entry_reverse_inside(pos, type, head, member) \
675 for (type * pos = list_last_entry(head, type, member); \
676 !list_entry_is_head(pos, head, member); \
677 pos = list_prev_entry(pos, member))
678
679 /**
680 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
681 * @pos: the type * to use as a start point
682 * @head: the head of the list
683 * @member: the name of the list_head within the struct.
684 *
685 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
686 */
687 #define list_prepare_entry(pos, head, member) \
688 ((pos) ? : list_entry(head, typeof(*pos), member))
689
690 /**
691 * list_for_each_entry_continue - continue iteration over list of given type
692 * @pos: the type * to use as a loop cursor.
693 * @head: the head for your list.
694 * @member: the name of the list_head within the struct.
695 *
696 * Continue to iterate over list of given type, continuing after
697 * the current position.
698 */
699 #define list_for_each_entry_continue(pos, head, member) \
700 for (pos = list_next_entry(pos, member); \
701 !list_entry_is_head(pos, head, member); \
702 pos = list_next_entry(pos, member))
703
704 /**
705 * list_for_each_entry_continue_inside
706 * - continue iteration over list of given type and keep iterator inside the loop
707 * @pos: the type * to use as a loop cursor.
708 * @start: the given iterator to start with.
709 * @head: the head for your list.
710 * @member: the name of the list_head within the struct.
711 *
712 * Continue to iterate over list of given type, continuing after
713 * the current position.
714 */
715 #define list_for_each_entry_continue_inside(pos, start, head, member) \
716 for (typeof(*start) *pos = list_next_entry(start, member); \
717 !list_entry_is_head(pos, head, member); \
718 pos = list_next_entry(pos, member))
719
720 /**
721 * list_for_each_entry_continue_reverse - iterate backwards from the given point
722 * @pos: the type * to use as a loop cursor.
723 * @head: the head for your list.
724 * @member: the name of the list_head within the struct.
725 *
726 * Start to iterate over list of given type backwards, continuing after
727 * the current position.
728 */
729 #define list_for_each_entry_continue_reverse(pos, head, member) \
730 for (pos = list_prev_entry(pos, member); \
731 !list_entry_is_head(pos, head, member); \
732 pos = list_prev_entry(pos, member))
733
734 /**
735 * list_for_each_entry_continue_reverse_inside
736 * - iterate backwards from the given point and keep iterator inside the loop
737 * @pos: the type * to use as a loop cursor.
738 * @start: the given iterator to start with.
739 * @head: the head for your list.
740 * @member: the name of the list_head within the struct.
741 *
742 * Start to iterate over list of given type backwards, continuing after
743 * the current position.
744 */
745 #define list_for_each_entry_continue_reverse_inside(pos, start, head, member) \
746 for (typeof(*start) *pos = list_prev_entry(start, member); \
747 !list_entry_is_head(pos, head, member); \
748 pos = list_prev_entry(pos, member))
749
750 /**
751 * list_for_each_entry_from - iterate over list of given type from the current point
752 * @pos: the type * to use as a loop cursor.
753 * @head: the head for your list.
754 * @member: the name of the list_head within the struct.
755 *
756 * Iterate over list of given type, continuing from current position.
757 */
758 #define list_for_each_entry_from(pos, head, member) \
759 for (; !list_entry_is_head(pos, head, member); \
760 pos = list_next_entry(pos, member))
761
762 /**
763 * list_for_each_entry_from_inside
764 * - iterate over list of given type from the current point and keep iterator inside the loop
765 * @pos: the type * to use as a loop cursor.
766 * @start: the given iterator to start with.
767 * @head: the head for your list.
768 * @member: the name of the list_head within the struct.
769 *
770 * Iterate over list of given type, continuing from current position.
771 */
772 #define list_for_each_entry_from_inside(pos, start, head, member) \
773 for (typeof(*start) *pos = start; !list_entry_is_head(pos, head, member); \
774 pos = list_next_entry(pos, member))
775
776 /**
777 * list_for_each_entry_from_reverse - iterate backwards over list of given type
778 * from the current point
779 * @pos: the type * to use as a loop cursor.
780 * @head: the head for your list.
781 * @member: the name of the list_head within the struct.
782 *
783 * Iterate backwards over list of given type, continuing from current position.
784 */
785 #define list_for_each_entry_from_reverse(pos, head, member) \
786 for (; !list_entry_is_head(pos, head, member); \
787 pos = list_prev_entry(pos, member))
788
789 /**
790 * list_for_each_entry_from_reverse_inside
791 * - iterate backwards over list of given type from the current point
792 * and keep iterator inside the loop
793 * @pos: the type * to use as a loop cursor.
794 * @start: the given iterator to start with.
795 * @head: the head for your list.
796 * @member: the name of the list_head within the struct.
797 *
798 * Iterate backwards over list of given type, continuing from current position.
799 */
800 #define list_for_each_entry_from_reverse_inside(pos, start, head, member) \
801 for (typeof(*start) *pos = start; !list_entry_is_head(pos, head, member); \
802 pos = list_prev_entry(pos, member))
803
804 /**
805 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
806 * @pos: the type * to use as a loop cursor.
807 * @n: another type * to use as temporary storage
808 * @head: the head for your list.
809 * @member: the name of the list_head within the struct.
810 */
811 #define list_for_each_entry_safe(pos, n, head, member) \
812 for (pos = list_first_entry(head, typeof(*pos), member), \
813 n = list_next_entry(pos, member); \
814 !list_entry_is_head(pos, head, member); \
815 pos = n, n = list_next_entry(n, member))
816
817 /**
818 * list_for_each_entry_safe_inside
819 * - iterate over list of given type safe against removal of list entry
820 * and keep iterator inside the loop
821 * @pos: the type * to use as a loop cursor.
822 * @n: another type * to use as temporary storage
823 * @type: the type of the container struct this is embedded in.
824 * @head: the head for your list.
825 * @member: the name of the list_head within the struct.
826 */
827 #define list_for_each_entry_safe_inside(pos, n, type, head, member) \
828 for (type * pos = list_first_entry(head, type, member), \
829 *n = list_next_entry(pos, member); \
830 !list_entry_is_head(pos, head, member); \
831 pos = n, n = list_next_entry(n, member))
832
833 /**
834 * list_for_each_entry_safe_continue - continue list iteration safe against removal
835 * @pos: the type * to use as a loop cursor.
836 * @n: another type * to use as temporary storage
837 * @head: the head for your list.
838 * @member: the name of the list_head within the struct.
839 *
840 * Iterate over list of given type, continuing after current point,
841 * safe against removal of list entry.
842 */
843 #define list_for_each_entry_safe_continue(pos, n, head, member) \
844 for (pos = list_next_entry(pos, member), \
845 n = list_next_entry(pos, member); \
846 !list_entry_is_head(pos, head, member); \
847 pos = n, n = list_next_entry(n, member))
848
849 /**
850 * list_for_each_entry_safe_continue_inside
851 * - continue list iteration safe against removal and keep iterator inside the loop
852 * @pos: the type * to use as a loop cursor.
853 * @n: another type * to use as temporary storage
854 * @start: the given iterator to start with.
855 * @head: the head for your list.
856 * @member: the name of the list_head within the struct.
857 *
858 * Iterate over list of given type, continuing after current point,
859 * safe against removal of list entry.
860 */
861 #define list_for_each_entry_safe_continue_inside(pos, n, start, head, member) \
862 for (typeof(*start) *pos = list_next_entry(start, member), \
863 *n = list_next_entry(pos, member); \
864 !list_entry_is_head(pos, head, member); \
865 pos = n, n = list_next_entry(n, member))
866
867 /**
868 * list_for_each_entry_safe_from - iterate over list from current point safe against removal
869 * @pos: the type * to use as a loop cursor.
870 * @n: another type * to use as temporary storage
871 * @head: the head for your list.
872 * @member: the name of the list_head within the struct.
873 *
874 * Iterate over list of given type from current point, safe against
875 * removal of list entry.
876 */
877 #define list_for_each_entry_safe_from(pos, n, head, member) \
878 for (n = list_next_entry(pos, member); \
879 !list_entry_is_head(pos, head, member); \
880 pos = n, n = list_next_entry(n, member))
881
882 /**
883 * list_for_each_entry_safe_from_inside
884 * - iterate over list from current point safe against removal and keep iterator inside the loop
885 * @pos: the type * to use as a loop cursor.
886 * @n: another type * to use as temporary storage
887 * @start: the given iterator to start with.
888 * @head: the head for your list.
889 * @member: the name of the list_head within the struct.
890 *
891 * Iterate over list of given type from current point, safe against
892 * removal of list entry.
893 */
894 #define list_for_each_entry_safe_from_inside(pos, n, start, head, member) \
895 for (typeof(*start) *pos = start, *n = list_next_entry(pos, member); \
896 !list_entry_is_head(pos, head, member); \
897 pos = n, n = list_next_entry(n, member))
898
899 /**
900 * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
901 * @pos: the type * to use as a loop cursor.
902 * @n: another type * to use as temporary storage
903 * @head: the head for your list.
904 * @member: the name of the list_head within the struct.
905 *
906 * Iterate backwards over list of given type, safe against removal
907 * of list entry.
908 */
909 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
910 for (pos = list_last_entry(head, typeof(*pos), member), \
911 n = list_prev_entry(pos, member); \
912 !list_entry_is_head(pos, head, member); \
913 pos = n, n = list_prev_entry(n, member))
914
915 /**
916 * list_for_each_entry_safe_reverse_insde
917 * - iterate backwards over list safe against removal and keep iterator inside the loop
918 * @pos: the type * to use as a loop cursor.
919 * @n: another type * to use as temporary storage
920 * @type: the type of the struct this is enmbeded in.
921 * @head: the head for your list.
922 * @member: the name of the list_head within the struct.
923 *
924 * Iterate backwards over list of given type, safe against removal
925 * of list entry.
926 */
927 #define list_for_each_entry_safe_reverse_inside(pos, n, type, head, member) \
928 for (type * pos = list_last_entry(head, type, member), \
929 *n = list_prev_entry(pos, member); \
930 !list_entry_is_head(pos, head, member); \
> 931 pos = n, n = list_prev_entry(n, member))
932

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/[email protected]

2022-03-02 16:51:07

by James Bottomley

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

On Tue, 2022-03-01 at 15:58 +0800, Xiaomeng Tong wrote:
> For each list_for_each_entry* macros(10 variants), implements a
> respective
> new *_inside one. Such as the new macro list_for_each_entry_inside
> for
> list_for_each_entry. The idea is to be as compatible with the
> original
> interface as possible and to minimize code changes.
>
> Here are 2 examples:
>
> list_for_each_entry_inside:
> - declare the iterator-variable pos inside the loop. Thus, the
> origin
> declare of the inputed *pos* outside the loop should be removed.
> In
> other words, the inputed *pos* now is just a string name.
> - add a new "type" argument as the type of the container struct this
> is
> embedded in, and should be inputed when calling the macro.
>
> list_for_each_entry_safe_continue_inside:
> - declare the iterator-variable pos and n inside the loop. Thus, the
> origin declares of the inputed *pos* and *n* outside the loop
> should
> be removed. In other words, the inputed *pos* and *n* now are just
> string name.
> - add a new "start" argument as the given iterator to start with and
> can be used to get the container struct *type*. This should be
> inputed
> when calling the macro.
>
> Signed-off-by: Xiaomeng Tong <[email protected]>
> ---
> include/linux/list.h | 156
> +++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 156 insertions(+)
>
> diff --git a/include/linux/list.h b/include/linux/list.h
> index dd6c2041d..1595ce865 100644
> --- a/include/linux/list.h
> +++ b/include/linux/list.h
> @@ -639,6 +639,19 @@ static inline void list_splice_tail_init(struct
> list_head *list,
> !list_entry_is_head(pos, head, member);
> \
> pos = list_next_entry(pos, member))
>
> +/**
> + * list_for_each_entry_inside
> + * - iterate over list of given type and keep iterator inside the
> loop
> + * @pos: the type * to use as a loop cursor.
> + * @type: the type of the container struct this is embedded in.
> + * @head: the head for your list.
> + * @member: the name of the list_head within the struct.
> + */
> +#define list_for_each_entry_inside(pos, type, head, member)
> \
> + for (type * pos = list_first_entry(head, type, member);
> \
> + !list_entry_is_head(pos, head, member);
> \
> + pos = list_next_entry(pos, member))
> +
>

pos shouldn't be an input to the macro since it's being declared inside
it. All that will do will set up confusion about the shadowing of pos.
The macro should still work as

#define list_for_each_entry_inside(type, head, member) \
...

For safety, you could

#define POS __UNIQUE_ID(pos)

and use POS as the loop variable .. you'll have to go through an
intermediate macro to get it to be stable. There are examples in
linux/rcupdate.h

James


2022-03-03 03:31:49

by Xiaomeng Tong

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

On Wed, 02 Mar 2022 08:02:23 -0500, James Bottomley
<[email protected]> wrote:
> pos shouldn't be an input to the macro since it's being declared inside
> it. All that will do will set up confusion about the shadowing of pos.
> The macro should still work as
>
> #define list_for_each_entry_inside(type, head, member) \
> ...
>
> For safety, you could
>
> #define POS __UNIQUE_ID(pos)
>
> and use POS as the loop variable .. you'll have to go through an
> intermediate macro to get it to be stable. There are examples in
> linux/rcupdate.h

The outer "pos" variable is no longer needed and thus the declare
statement before the loop is removed, see the demostration in PATCH
3~6. Now, there is only one inner "pos" variable left. Thus, there
should be no such *shadow* problem.

Please remind me if i missed something, thanks.

--
Xiaomeng Tong

2022-03-04 02:20:19

by Linus Torvalds

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

On Mon, Feb 28, 2022 at 11:59 PM Xiaomeng Tong <[email protected]> wrote:
>
> +#define list_for_each_entry_inside(pos, type, head, member) \

So as mentioned in another thread, I actually tried exactly this.

And it was horrendous.

It's _technically_ probably a very nice solution, but

- it means that the already *good* cases are the ones that are
penalized by having to change

- the syntax of the thing becomes absolutely nasty

which means that _practially_ it's exactly the wrong thing to do.

Just as an example, this is a random current "good user" in kernel/exit.c:

- list_for_each_entry_safe(p, n, dead, ptrace_entry) {
+ list_for_each_entry_safe_inside(p, n, struct task_struct,
dead, ptrace_entry) {

and while some of the effects are nice (no need to declare p/n ahead
of time), just look at how nasty that line is.

Basically every single use will result in an over-long line. The above
example has minimal indentation, almost minimal variable names (to the
point of not being very descriptive at all), and one of the most basic
kernel structure types. And it still ended up 87 columns wide.

And no, the answer to that is not "do it on multiple lines then".
That is just even worse.

So I really think this is a major step in the wrong direction.

We should strive for the *bad* cases to have to do extra work, and
even there we should really strive for legibility.

Now, I think that "safe" version in particular can be simplified:
there's no reason to give the "n" variable a name. Now that we can
(with -stc=gnu11) just declare our own variables in the for-loop, the
need for that externally visible 'next' declaration just goes away.

So three of those 87 columns are pointless and should be removed. The
macro can just internally decare 'n' like it always wanted (but
couldn't do due to legacy C language syntax restrictions).

But even with that fixed, it's still a very cumbersome line.

Note how the old syntax was "only" 60 characters - long but still
quite legible (and would have space for two more levels of indentation
without even hitting 80 characters). And that was _despute_ having to
have that 'n' declaration.

And yes, the old syntax does require that

struct task_struct *p, *n;

line to declare the types, but that really is not a huge burden, and
is not complicated. It's just another "variables of the right type"
line (and as mentioned, the 'n' part has always been a C syntax
annoyance).

Linus

2022-03-04 12:04:04

by Xiaomeng Tong

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

First of all, thank you very much for your patient reply and valuable
comments. This is a great inspiration to me.

> On Mon, Feb 28, 2022 at 11:59 PM Xiaomeng Tong <[email protected]> wrote:
> >
> > +#define list_for_each_entry_inside(pos, type, head, member) \
>
> So as mentioned in another thread, I actually tried exactly this.
>
> And it was horrendous.
>
> It's _technically_ probably a very nice solution, but

Yes, I always think it is a perfect solution _technically_, since you
first proposed in the thread of Jakob's first subject.

>
> - it means that the already *good* cases are the ones that are
> penalized by having to change

Yes, but it also kills potential risks that one day somebody mistakely
uses iterator after the loop in this already *good* cases, as it removed
the original declare of pos and any use-after-loop will be catched by
compiler.

>
> - the syntax of the thing becomes absolutely nasty
>
> which means that _practially_ it's exactly the wrong thing to do.
>
> Just as an example, this is a random current "good user" in kernel/exit.c:
>
> - list_for_each_entry_safe(p, n, dead, ptrace_entry) {
> + list_for_each_entry_safe_inside(p, n, struct task_struct,
> dead, ptrace_entry) {
>
> and while some of the effects are nice (no need to declare p/n ahead
> of time), just look at how nasty that line is.
>
> Basically every single use will result in an over-long line. The above
> example has minimal indentation, almost minimal variable names (to the
> point of not being very descriptive at all), and one of the most basic
> kernel structure types. And it still ended up 87 columns wide.
>
> And no, the answer to that is not "do it on multiple lines then".
> That is just even worse.

Two avoid multiple lines, there are some mitigations:
1. use a shorter macro name: (add 2 chars)
list_for_each_entry_i instead of list_for_each_entry_inside

2. using a shorter type passing to the macro: (add 3 chars)
+ #define t struct sram_bank_info
- list_for_each_entry(pos, head, member) {
+ list_for_each_entry_i(pos, t, head, member) {

3. restore all name back to list_for_each_entry after everything is done:
(minus 2 chars)
Although we need replace all the use of list_for_each_entry* (15000+)
with list_for_each_entry*_i, the work can be done gradually rather
than all at once. We can incrementally replace these callers until
all these in the kernel are completely updated with *_i* one. At
that time, we can just remove the implements of origin macros and rename
the *_i* macro back to the origin name just in one single patch.

4. As you mentioned, the "safe" version of list_for_each_entry do not
need "n" argument anymore with the help of -std=gnu11. (minus 3 chars)

Thus, after all mitigations applied, the "safe" version adds *no* chars to
columns wide, and other version adds 3 chars totally, which is acceptable
to me.

>
> So I really think this is a major step in the wrong direction.

Maybe yes or maybe no.
Before the list_for_each_entry_inside way, I have tried something like
"typeof(pos) pos" way as and before you proposed in the thread of Jakob's
second subject, to avoid any changes to callers of the macros. But it also
has potential problems. see my previous reply to you here:
https://lore.kernel.org/lkml/[email protected]/

>
> We should strive for the *bad* cases to have to do extra work, and
> even there we should really strive for legibility.

Indeed, there are many "multiple lines" problems in the current kernel
code, for example (drivers/dma/iop-adma.c):
list_for_each_entry_from(grp_iter,
&iop_chan->chain, chain_node) {

>
> Now, I think that "safe" version in particular can be simplified:
> there's no reason to give the "n" variable a name. Now that we can
> (with -stc=gnu11) just declare our own variables in the for-loop, the
> need for that externally visible 'next' declaration just goes away.
>
> So three of those 87 columns are pointless and should be removed. The
> macro can just internally decare 'n' like it always wanted (but
> couldn't do due to legacy C language syntax restrictions).

Great, this does reduce three chars. and i will look into other versions.

>
> But even with that fixed, it's still a very cumbersome line.

With other mitigations mentioned above, the addition to line will be
acceptable.

>
> Note how the old syntax was "only" 60 characters - long but still
> quite legible (and would have space for two more levels of indentation
> without even hitting 80 characters). And that was _despute_ having to
> have that 'n' declaration.
>
> And yes, the old syntax does require that
>
> struct task_struct *p, *n;
>
> line to declare the types, but that really is not a huge burden, and
> is not complicated. It's just another "variables of the right type"
> line (and as mentioned, the 'n' part has always been a C syntax
> annoyance).

Yes, that really is not a huge burden, so is the mitigation 2 mentioned
above which defining a shorter type passing to the macro, to shorten the
new line.

>
> Linus

--
Xiaomeng Tong

2022-03-06 02:09:50

by Linus Torvalds

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

On Thu, Mar 3, 2022 at 6:51 PM Xiaomeng Tong <[email protected]> wrote:
>
> > - it means that the already *good* cases are the ones that are
> > penalized by having to change
>
> Yes, but it also kills potential risks that one day somebody mistakely
> uses iterator after the loop in this already *good* cases, as it removed
> the original declare of pos and any use-after-loop will be catched by
> compiler.

The thing is, I think we already have a solution to that case.

I think it's the bad "entry used outside" that we need to care about doing well.

> 3. restore all name back to list_for_each_entry after everything is done:
> (minus 2 chars)

You are ignoring the big elephant in the room - counting the small
things, but not counting the BIG thing.

That type name argument is long.

Right now we avoid it by pre-declaring it, and that's in many ways the
natural thing to do in C (you don't declare types in the place that
uses them, you declare the types in the variable declarations above
the code).

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 all the
'struct list_head' things *could* be made to be unnamed unions of the
list head, and the actual type it points to, ie something like

#define declare_list_head(type,type) union { struct list_head x;
type *x##_list_type; }

and then (to pick one particular example), we could make the "struct
task_struct" entry for children be

- struct list_head children;
+ declare_list_head(struct task_struct, children);

and now when you use

list_for_each_entry(p, &father->children, sibling) {

you could actually pick out the type with some really ugly
preprocessor crud, by doing 'typeof(*head##_list_type)' to get the
type of the thing we iterate over.

So we *could* embed the type that a list head points to with tricks
like that. The it would actually be type-safe, and not need a
declaration of the type anywhere. And it would be kind of nice to
document "this is a list head pointer to this kind of type".

And yes, it would be even better if we could also encode the member
name that contains the list entries somehow (ie in this case the
'sibling' list entry of the task struct) so that you'd really document
the full chain. But even my twisted mind cannot come up with any
tricks to do *that*.

But the above would be quite a *major* change.

And the above kind of preprocessor trickery and encoding a secondary
type as a union entry that isn't actually used for anythign else may
be too ugly to live anyway.

Linus

2022-03-06 17:51:49

by James Bottomley

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

On Thu, 2022-03-03 at 11:31 +0800, Xiaomeng Tong wrote:
> On Wed, 02 Mar 2022 08:02:23 -0500, James Bottomley
> <[email protected]> wrote:
> > pos shouldn't be an input to the macro since it's being declared
> > inside
> > it. All that will do will set up confusion about the shadowing of
> > pos.
> > The macro should still work as
> >
> > #define list_for_each_entry_inside(type, head, member) \
> > ...
> >
> > For safety, you could
> >
> > #define POS __UNIQUE_ID(pos)
> >
> > and use POS as the loop variable .. you'll have to go through an
> > intermediate macro to get it to be stable. There are examples in
> > linux/rcupdate.h
>
> The outer "pos" variable is no longer needed and thus the declare
> statement before the loop is removed, see the demostration in PATCH
> 3~6. Now, there is only one inner "pos" variable left. Thus, there
> should be no such *shadow* problem.

So why is pos in the signature of your #define then? Because that
means it expands to whatever goes in the first field of
list_for_each_entry_inside().

If someone needs to specify a unique name to avoid shadowing an
existing variable, then hide pos and use UNIQUE_ID instead was the
whole thrust of this comment.

James


2022-03-06 19:34:45

by Linus Torvalds

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

On Sun, Mar 6, 2022 at 4:19 AM Jakob Koschel <[email protected]> wrote:
>
> I guess we could apply this to list_for_each_entry() as well
> once all the uses after the loop are fixed?

I think that would be a good longer-term plan. "list_traverse()" ends
up being simpler syntactically, and has a certain level of inherent
type safety (not just the "don't expose the mis-typed head pointer
after the loop").

> I feel like this simply introduces a new set of macros
> (we would also need list_traverse_reverse(), list_traverse_continue_reverse()
> etc) and end up with a second set of macros that do pretty much
> the same as the first one.

I think that if we're happy with this, we can probably do a scripted
conversion. But I do like how it's incremental, in that we wouldn't
necessarily have to do it all in one go.

Because it's always really painful with flag-day interface changes,
which it would be to actually change the semantics of
"list_for_each_entry()" without a name change. It just makes for a lot
of pain for things that aren't in-tree yet (not just drivers that are
out-of-tree in general, but drivers in development etc).

And I really disliked the "pass the type to the list_for_each()"
macro, because of how it made the end result look more complex.

But list_traverse() looks like it would make the end result better
both from a user perspective (ie the code just looks simpler) but also
from the type safety point.

> Personally I guess I also prefer the name list_for_each_entry() over list_traverse()
> and not having two types of iterators for the same thing at the same time.

I absolutely agree with you in theory, and in many ways I like
list_for_each_entry() better as a name too (probably just because I'm
used to it).

But keeping the same name and changing how it works ends up being such
a "everything at once" thing that I don't think it's realistic.

Linus

2022-03-06 20:09:49

by Xiaomeng Tong

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

On Sat, 5 Mar 2022 16:35:36 -0800 Linus Torvalds
<[email protected]> wrote:
> On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds
> <[email protected]> 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()'.
>

Yes, brilliant! It is tricky and hacky. In your example: &tsk->children
will be expanded to &tsk->children_traversal_type.
And it also reduces column of the calling line with simplified version
of list_for_each_entry.

But, maybe there are some more cases the union-based way need to handle.
Such as, in your example, if the &HEAD passing to list_for_each_entry is
*not* "&tsk->children", but just a *naked head* with no any extra
information provoided:
void foo(...) {
bar(&tsk->children);
}
noinline void bar(struct list_head *naked_head) {
struct task_struct *p;
list_for_each_entry(p, naked_head, sibling) {
...
}
}
you should change all declares like "struct list_head" here with the union
one, but not only in the structure of task_struct itself.

I'm going to dig into this union-base way and re-send a patch if necessary.

> 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.
>

Yes, the "c" is as the found entry for outside use -- it is natural.
And the "pos" as a inside-defined variable -- it is our goal.
And the "continue" trick to reduce 1 line -- it is nice.

> 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.
>

Yes, i am very glad that you accepted and agreed my suggestion for the
*incremental changes* part, just like my "_inside" way used.
It means a lot for me to have your approval.

> 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

--
Xiaomeng Tong

2022-03-07 02:39:41

by Linus Torvalds

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

On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds
<[email protected]> 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


Attachments:
patch.diff (4.74 kB)

2022-03-07 06:53:28

by Jakob Koschel

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



> On 6. Mar 2022, at 01:35, Linus Torvalds <[email protected]> wrote:
>
> On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds
> <[email protected]> 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?

I guess we could apply this to list_for_each_entry() as well
once all the uses after the loop are fixed?

I feel like this simply introduces a new set of macros
(we would also need list_traverse_reverse(), list_traverse_continue_reverse()
etc) and end up with a second set of macros that do pretty much
the same as the first one.

I like the way of using list_traversal_head() to only remember the type.
The interface of list_traverse() is the same as list_for_each_entry() so
we could just do this with a simple coccinelle script once 'pos' is no
longer used after the loop:

-struct some_struct *pos;
+list_traversal_head(struct some_struct, pos, target_member);


although there are *some* cases where 'pos' is also used separately
in the function which would need to change, e.g.:

struct some_struct *pos = some_variable;

if (pos)
// do one thing
else
list_for_each_entry(pos, ..., ...)


(I've fixed ~440/450 cases now and I'm chunking it into patch sets right now.
The once left over are non-obvious code I would need some input on)

Personally I guess I also prefer the name list_for_each_entry() over list_traverse()
and not having two types of iterators for the same thing at the same time.


>
> Linus
> <patch.diff>

Jakob

2022-03-11 22:16:31

by Michał Mirosław

[permalink] [raw]
Subject: Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable

Hi Linus,

If the macro implementation doesn't have to be pretty, maybe it could go
a step further and remember the list_head's offset? That would look
something like following (expanding on your patch; not compile tested):

#define list_traversal_head(type,name,target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
char (*name##_list_head_offset)[offsetof(type, target_member)]; \
}

#define list_traversal_entry(ptr, head) \
(typeof(*head##_traversal_type))((void *)ptr - sizeof(**head##_list_head_offset))

#define list_traversal_entry_head(ptr, head) \
(struct list_head *)((void *)ptr + sizeof(**head##_list_head_offset))

#define list_traversal_entry_is_head(ptr, head) \
(list_traversal_entry_head(ptr, head) == (head))

#define list_traversal_next_entry(ptr, head) \
list_traversal_entry(list_traversal_entry_head(ptr, head)->next)

#define list_traverse(pos, head) \
for (typeof(*head##_traversal_type) pos = list_traversal_entry((head)->next); \
!list_traversal_entry_head(pos, head) == (head); \
pos = list_traversal_next_entry(pos, head))

[Sorry for lack of citations - I found the thread via https://lwn.net/Articles/887097/]

--
Micha? Miros?aw

2022-03-11 22:28:00

by Linus Torvalds

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

On Fri, Mar 11, 2022 at 6:27 AM Daniel Thompson
<[email protected]> wrote:
>
> It is possible simply to use spelling to help uncover errors in
> list_traverse()?

I'd love to, and thought that would be a lovely idea, but in another
thread ("") Barnabás Pőcze pointed out that we actually have a fair
number of cases where the list member entries are embedded in internal
structures and have a '.' in them:

https://lore.kernel.org/all/wKlkWvCGvBrBjshT6gHT23JY9kWImhFPmTKfZWtN5Bkv_OtIFHTy7thr5SAEL6sYDthMDth-rvFETX-gCZPPCb9t2bO1zilj0Q-OTTSbe00=@protonmail.com/

which means that you can't actually append the target_member name
except in the simplest cases, because it wouldn't result in one single
identifier.

Otherwise it would be a lovely idea.

> For architectures without HAVE_LD_DEAD_CODE_DATA_ELIMINATION then the
> "obvious" extension of list_traversal_head() ends up occupying bss
> space. Even replacing the pointer with a zero length array is still
> provoking gcc-11 (arm64) to allocate a byte from bss (often with a lot
> of padding added).

I think compilers give objects at least one byte of space, so that two
different objects get different addresses, and don't compare equal.

That said, I'm not seeing your issue. list_traversal_head() is a
union, and always has that 'struct list_head' in it, and that's the
biggest part of the union.

IOW, the other parts are (a) never used for anything but their type
and (b) will not take up any new space that isn't already used by the
list_head itself.

Linus

2022-03-11 22:56:04

by David Gow

[permalink] [raw]
Subject: [RFC PATCH] list: test: Add a test for list_traverse

Update the list KUnit test to include a test for the new list_traverse()
macro. This adds a new 'head' member to the list_test_struct to use as a
list head, using the list_traverse_head macro.

Signed-off-by: David Gow <[email protected]>
---

If, as seems likely, we're going to introduce new list traversal macros,
it'd be nice to update the linked list KUnit tests in lib/list-test.c to
test them. :-)

This patch works against the proposed list_traverse() macro posted here:
https://lore.kernel.org/all/CAHk-=wiacQM76xec=Hr7cLchVZ8Mo9VDHmXRJzJ_EX4sOsApEA@mail.gmail.com/

Feel free to use and/or adapt it if this or a similar macro is
introduced.

Cheers,
-- David

---
lib/list-test.c | 24 ++++++++++++++++++++++++
1 file changed, 24 insertions(+)

diff --git a/lib/list-test.c b/lib/list-test.c
index ee09505df16f..7fa2622ff9c7 100644
--- a/lib/list-test.c
+++ b/lib/list-test.c
@@ -12,6 +12,7 @@
struct list_test_struct {
int data;
struct list_head list;
+ list_traversal_head(struct list_test_struct, head, list);
};

static void list_test_list_init(struct kunit *test)
@@ -656,6 +657,28 @@ static void list_test_list_for_each_prev_safe(struct kunit *test)
KUNIT_EXPECT_TRUE(test, list_empty(&list));
}

+static void list_test_list_traverse(struct kunit *test)
+{
+ struct list_test_struct entries[5], head;
+ int i = 0;
+
+ INIT_LIST_HEAD(&head.head);
+
+ for (i = 0; i < 5; ++i) {
+ entries[i].data = i;
+ list_add_tail(&entries[i].list, &head.head);
+ }
+
+ i = 0;
+
+ list_traverse(cur, &head.head, list) {
+ KUNIT_EXPECT_EQ(test, cur->data, i);
+ i++;
+ }
+
+ KUNIT_EXPECT_EQ(test, i, 5);
+}
+
static void list_test_list_for_each_entry(struct kunit *test)
{
struct list_test_struct entries[5], *cur;
@@ -733,6 +756,7 @@ static struct kunit_case list_test_cases[] = {
KUNIT_CASE(list_test_list_for_each_prev),
KUNIT_CASE(list_test_list_for_each_safe),
KUNIT_CASE(list_test_list_for_each_prev_safe),
+ KUNIT_CASE(list_test_list_traverse),
KUNIT_CASE(list_test_list_for_each_entry),
KUNIT_CASE(list_test_list_for_each_entry_reverse),
{},
--
2.35.1.723.g4982287a31-goog

2022-03-11 23:26:42

by Daniel Thompson

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

On Sat, Mar 05, 2022 at 04:35:36PM -0800, Linus Torvalds wrote:
> On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds
> <[email protected]> wrote:
> 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?

It is possible simply to use spelling to help uncover errors in
list_traverse()?

Something like:

#define list_traversal_head(type, name, target_member) \
union { \
struct list_head name; \
type *name##_traversal_mismatch_##target_member; \
}

And:

#define list_traverse(pos, head, member) \
for (typeof(*head##_traversal_mismatch_##member) pos = list_first_entry(head, typeof(*pos), member); \
!list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))

If I deliberately insert an error into your modified exit.c then the
resulting errors even make helpful suggestions about what you did
wrong:

kernel/exit.c:412:32: error: ‘struct task_struct’ has no member named
‘children_traversal_mismatch_children’; did you mean
‘children_traversal_mismatch_sibling’?

The suggestions are not always as good as the above
(children_traversal_mismatch_ptrace_entry suggests
ptraced_traversal_mismatch_ptrace_entry) but, nevertheless, it does
appears to be robust in detecting incorrect traversal.


> 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)

Seeing this in the diff did set me thinking about static/global
list heads.

For architectures without HAVE_LD_DEAD_CODE_DATA_ELIMINATION then the
"obvious" extension of list_traversal_head() ends up occupying bss
space. Even replacing the pointer with a zero length array is still
provoking gcc-11 (arm64) to allocate a byte from bss (often with a lot
of padding added).

Perhaps in the grand scheme of things this doesn't matter. Across the
whole tree and all architecture I see only ~1200 instances so even in
the worst case and with padding everywhere the wasted RAM is only a few
kb.

Nevertheless I was curious if there is any cunning tricks to avoid
this? Naturally LIST_HEAD() could just declare a union but that would
require all sites of use to be updated simultaneously and I rather
like the way list_traverse_head() is entirely incremental.


Daniel.

2022-03-17 03:35:57

by Daniel Thompson

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

On Fri, Mar 11, 2022 at 10:41:06AM -0800, Linus Torvalds wrote:
> On Fri, Mar 11, 2022 at 6:27 AM Daniel Thompson
> <[email protected]> wrote:
> >
> > It is possible simply to use spelling to help uncover errors in
> > list_traverse()?
>
> I'd love to, and thought that would be a lovely idea, but in another
> thread ("") Barnabás Pőcze pointed out that we actually have a fair
> number of cases where the list member entries are embedded in internal
> structures and have a '.' in them:
>
> https://lore.kernel.org/all/wKlkWvCGvBrBjshT6gHT23JY9kWImhFPmTKfZWtN5Bkv_OtIFHTy7thr5SAEL6sYDthMDth-rvFETX-gCZPPCb9t2bO1zilj0Q-OTTSbe00=@protonmail.com/
>
> which means that you can't actually append the target_member name
> except in the simplest cases, because it wouldn't result in one single
> identifier.
>
> Otherwise it would be a lovely idea.

When I prototyped this I did actually include a backdoor to cover
situations like this but I ended up (incorrectly at appears) editing it
out for simplicity.

Basically the union is free so we can have more than one type * member:

#define list_traversal_head(type, name, target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
type *name##_traversal_mismatch_##target_member; \
}

This allows that the single structure cases to be checked whilst nested
structures (and array which I noticed also crop up) have a trap door such
as list_traverse_unchecked().

I did a quick grep to estimate how many nested/array cases there are and
came up with around 2.5% (roughly ~200 in ~8500, counting only the single
line users of list_for_each_entry() ).

As you say, lovely idea but having to use special API 2.5% of the time
seems a bit on the high side.

BTW, a complete aside, but whilst I was looking for trouble I also
spotted code where the list head is an array which means we are not able
to lookup the travesral type correctly:
list_for_each_entry(modes[i], &connector->modes, head)
However I found only one instance of this so it
much more acceptable rate of special cases than the 2.5% above.


> > > [this bit used to quote the definition of LIST_HEAD() ;-) ]
> > For architectures without HAVE_LD_DEAD_CODE_DATA_ELIMINATION then the
> > "obvious" extension of list_traversal_head() ends up occupying bss
> > space. Even replacing the pointer with a zero length array is still
> > provoking gcc-11 (arm64) to allocate a byte from bss (often with a lot
> > of padding added).
>
> I think compilers give objects at least one byte of space, so that two
> different objects get different addresses, and don't compare equal.
>
> That said, I'm not seeing your issue. list_traversal_head() is a
> union, and always has that 'struct list_head' in it, and that's the
> biggest part of the union.

Perhaps its a bit overblown for the safe of a few kilobytes (even if
there were two traversal types members) but I was wondering if there is
any cunning trick for LIST_HEAD() since we cannot have an anonymous
union outside a struct. In short, is this the best we can do for
LIST_TRAVERSE_HEAD():

#define LIST_TRAVERSE_HEAD(type, name, target_member) \
type * name##_traversal_type; \
struct list_head name = LIST_HEAD_INIT(name)


#define STATIC_LIST_TRAVERSE_HEAD(type, name, target_member) \
static type * name##_traversal_type; \
static list_head name = LIST_HEAD_INIT(name)


Daniel.