list_for_each_entry*: make iterator invisiable outside the loop
Subsystems (12)
cover 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(-)
Signature · 1 line
2.17.1
PATCH 1/6 Kbuild: compile kernel with gnu11 std
This patch is suggested by linus[1], there may be some corner cases which should be considered before merge, and is just for prove PATCH 2.
[1]: https://lore.kernel.org/all/CAHk-=wh97QY9fEQUK6zMVQwaQ_JWDvR=R+TxQ_0OYrMHQ+egvQ@mail.gmail.com/
--- Makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
Makefile +1 -1
@@ -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 -Wno-shift-negative-value KBUILD_CPPFLAGS := -D__KERNEL__ KBUILD_AFLAGS_KERNEL := KBUILD_CFLAGS_KERNEL :=
Signature · 1 line
2.17.1
kernel test robot
build botRe: [PATCH 1/6] Kbuild: compile kernel with gnu11 std
Thank you for the patch! Perhaps something to improve:
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 config: mips-rb532_defconfig (https://download.01.org/0day-ci/archive/20220302/[email protected]/config) compiler: mipsel-linux-gcc (GCC) 11.2.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/0day-ci/linux/commit/84ec4077430a7e8c23ea1ebc7b69e254fda25cb1
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Xiaomeng-Tong/list_for_each_entry-make-iterator-invisiable-outside-the-loop/20220301-160113 git checkout 84ec4077430a7e8c23ea1ebc7b69e254fda25cb1
# save the config file to linux build tree
mkdir build_dir
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.2.0 make.cross O=build_dir ARCH=mips SHELL=/bin/bash
If you fix the issue, kindly add following tag as appropriate
All warnings (new ones prefixed by >>):
>> cc1: warning: result of '-117440512 << 16' requires 44 bits to represent, but 'int' only has 32 bits [-Wshift-overflow=]
arch/mips/pci/pci-rc32434.c: In function 'rc32434_pcibridge_init':
arch/mips/pci/pci-rc32434.c:111:22: warning: variable 'dummyread' set but not used [-Wunused-but-set-variable]
111 | unsigned int dummyread, pcicntlval;
| ^~~~~~~~~---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/[email protected]
Re: [PATCH 1/6] Kbuild: compile kernel with gnu11 std
Quoted 4 lines · kernel test robot
All warnings (new ones prefixed by >>):
Quoted 1 line
Quoted 1 line
cc1: warning: result of '-117440512 << 16' requires 44 bits to represent, but 'int' only has 32 bits [-Wshift-overflow=]
So that's potentially an interesting warning, but this email doesn't actually tell *where* that warning happens.
I'm not entirely sure why this warning is new to this '-std=gnu11' change, but it's intriguing.
Instead it then gives the location for another warning:
Quoted 4 lines
arch/mips/pci/pci-rc32434.c: In function 'rc32434_pcibridge_init':
arch/mips/pci/pci-rc32434.c:111:22: warning: variable 'dummyread' set but not used [-Wunused-but-set-variable]
111 | unsigned int dummyread, pcicntlval;
| ^~~~~~~~~but that wasn't the new one (and that 'dummyread' is obviously _intentionally_ set but not used, as implied by the name).
Is there some place to actually see the full log (or some way to get a better pointer to just the new warning) to see that actual shift overflow thing?
Linus
Re: [PATCH 1/6] Kbuild: compile kernel with gnu11 std
Quoted 12 lines · Linus Torvalds
Quoted 4 lines · kernel test robot
All warnings (new ones prefixed by >>):
Quoted 1 line
Quoted 1 line
cc1: warning: result of '-117440512 << 16' requires 44 bits to represent, but 'int' only has 32 bits [-Wshift-overflow=]
So that's potentially an interesting warning, but this email doesn't actually tell *where* that warning happens.
I'm not entirely sure why this warning is new to this '-std=gnu11' change, but it's intriguing.
...
Quoted 4 lines
Is there some place to actually see the full log (or some way to get a better pointer to just the new warning) to see that actual shift overflow thing?
gcc-11 only shows the one line warning here. The source is
/* PCI CFG04 status fields */
#define PCI_CFG04_STAT_BIT 16
#define PCI_CFG04_STAT 0xffff0000
#define PCI_CFG04_STAT_66_MHZ (1 << 21)
#define PCI_CFG04_STAT_FBB (1 << 23)
#define PCI_CFG04_STAT_MDPE (1 << 24)
#define PCI_CFG04_STAT_DST (1 << 25)
#define PCI_CFG04_STAT_STA (1 << 27)
#define PCI_CFG04_STAT_RTA (1 << 28)
#define PCI_CFG04_STAT_RMA (1 << 29)
#define PCI_CFG04_STAT_SSE (1 << 30)
#define PCI_CFG04_STAT_PE (1 << 31)
#define KORINA_STAT (PCI_CFG04_STAT_MDPE | \
PCI_CFG04_STAT_STA | \
PCI_CFG04_STAT_RTA | \
PCI_CFG04_STAT_RMA | \
PCI_CFG04_STAT_SSE | \
PCI_CFG04_STAT_PE)#define KORINA_CNFG1 ((KORINA_STAT<<16)|KORINA_CMD)
unsigned int korina_cnfg_regs[25] = {
KORINA_CNFG1, /* ... */
};This looks like an actual bug to me, the bits are shifted 16 bits twice by accident, and it's been like this since rb532 was introduced in 2008.
Arnd
Re: [PATCH 1/6] Kbuild: compile kernel with gnu11 std
Quoted 2 lines · Arnd Bergmann
gcc-11 only shows the one line warning here.
What an odd warning. Not even a filename, much less a line number?
Quoted 20 lines
The source is
/* PCI CFG04 status fields */
#define PCI_CFG04_STAT_BIT 16 #define PCI_CFG04_STAT 0xffff0000 #define PCI_CFG04_STAT_66_MHZ (1 << 21) #define PCI_CFG04_STAT_FBB (1 << 23) #define PCI_CFG04_STAT_MDPE (1 << 24) #define PCI_CFG04_STAT_DST (1 << 25) #define PCI_CFG04_STAT_STA (1 << 27) #define PCI_CFG04_STAT_RTA (1 << 28) #define PCI_CFG04_STAT_RMA (1 << 29) #define PCI_CFG04_STAT_SSE (1 << 30) #define PCI_CFG04_STAT_PE (1 << 31) #define KORINA_STAT (PCI_CFG04_STAT_MDPE | \ PCI_CFG04_STAT_STA | \ PCI_CFG04_STAT_RTA | \ PCI_CFG04_STAT_RMA | \ PCI_CFG04_STAT_SSE | \ PCI_CFG04_STAT_PE)
Quoted 1 line
#define
KORINA_CNFG1((KORINA_STAT<<16)|KORINA_CMD)
Yeah, looks like that "<< 16" is likely just wrong.
I'm guessing that that KORINA_CNFG1 thing either ends up not mattering, or - probably more likely - nobody really used that platform@all. It has had pretty much zero updates sinced 2008.
Linus
Re: [PATCH 1/6] Kbuild: compile kernel with gnu11 std
Quoted 2 lines · Linus Torvalds
Yeah, looks like that "<< 16" is likely just wrong.
.. and perhaps more importantly, I guess that means that -Wshift-overflow is
@ somehow new to -std=gnu11
(b) possibly a lot more relevant and good than that
-Wshift-negative-value thing was
doing some grepping, it seems like we have never had that '-Wshift-overflow' even in any extra warnings.
And trying it myself (keeping -std=gnu89), enabling it doesn't report anything on a x86-64 allmodconfig build.
So I think this is likely a good new warning that -std=gnu11 brought in by accident. No false positives that I can see, and one report for a MIPS bug that looks real (but admittedly not a "sky-is-falling" one ;)
There's apparently a '-Wshift-overflow=2' mode too, but that warns about things that change the sign bit, ie expressions like
1<<31
warns.
And I would not be in the least surprised if we had a ton of those kinds of things all over (but I didn't check).
So the plain -Wshift-overflow seems to work just fine, and while it's surprising that it got enabled by gnu11, I think it's all good.
Famous last words.
Linus
Re: [PATCH 1/6] Kbuild: compile kernel with gnu11 std
Sincerely thank you for your reply. I also look forward to your comments on other patches, especially PATCH 2/6 which provides new *_inside macros to make iterator invisiable outside the list_for_each_entry* loop.
Best regards,
--
Xiaomeng Tong
PATCH 2/6 list: add new MACROs to make iterator invisiable outside the loop
In reply to Xiaomeng TongFor 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.
--- include/linux/list.h | 156 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 156 insertions(+)
include/linux/list.h +156 -0
@@ -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
Signature · 1 line
2.17.1
kernel test robot
build botRe: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Thank you for the patch! Perhaps something to improve:
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
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]
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
In reply to Xiaomeng TongQuoted 63 lines · Xiaomeng Tong
For each list_for_each_entry* macros(10 variants), implements a respective
new*_insideone. Such as the new macrolist_for_each_entry_insideforlist_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(+)include/linux/list.h +3
-0@@ -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 thelist_headwithin the struct.
+ */
+#definelist_for_each_entry_inside(pos, type, head, member)\include/linux/list.h +1
-0+ for (type * pos = list_first_entry(head, type, member);\
include/linux/list.h +1
-0+ !list_entry_is_head (pos, head, member);\
include/linux/list.h
Quoted 2 lines
include/linux/list.h +2
-0+ 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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 7 lines · James Bottomley
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)\
...
Quoted 7 lines
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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 15 lines · Xiaomeng Tong
Quoted 13 lines · James Bottomley
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)
Quoted 8 lines
Quoted 3 lines
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.hThe 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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
In reply to Xiaomeng TongQuoted 2 lines · Xiaomeng Tong
+#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
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.
Quoted 9 lines · Xiaomeng Tong
Quoted 2 lines
+#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.
Quoted 3 lines
- 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.
Quoted 14 lines
- 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:(quoted diff) +1
-1- 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.
Quoted 7 lines
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.
Quoted 2 lines
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]/
Quoted 3 lines
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) {Quoted 9 lines
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.
Quoted 2 lines
But even with that fixed, it's still a very cumbersome line.
With other mitigations mentioned above, the addition to line will be acceptable.
Quoted 6 lines
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.
Quoted 8 lines
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.
Quoted 2 lines
Linus
--
Xiaomeng Tong
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 8 lines · Xiaomeng Tong
Quoted 3 lines
- it means that the already *good* cases are the ones that are
penalized by having to changeYes, 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.
Quoted 2 lines
3. restore all name back to
list_for_each_entryafter 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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 11 lines · Linus Torvalds
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(-)
Makefile +1 -1
@@ -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 :=
include/linux/list.h +14 -0
@@ -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.
include/linux/sched.h +2 -2
@@ -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. */
kernel/exit.c +14 -14
@@ -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)
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 66 lines · Linus Torvalds
Quoted 11 lines · Linus Torvalds
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.cto 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){
- structtask_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 usinglist_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 inkernel/exit.c, but it does *not* convert the code inkernel/fork.c, which still does that old-style traversal:list_for_each_entry(child, &parent->children, sibling) {and the
kernel/fork.ccode 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 thatlist_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?
Quoted 6 lines
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.
Quoted 3 lines
Linus
<patch.diff>
Jakob
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 3 lines · Jakob Koschel
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").
Quoted 4 lines
I feel like this simply introduces a new set of macros
(we would also needlist_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.
Quoted 2 lines
Personally I guess I also prefer the name
list_for_each_entry()overlist_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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
In reply to Linus TorvaldsQuoted 31 lines · On Sat, 5 Mar 2022 16:35:36 -0800 Linus Torvalds…
Quoted 11 lines · Linus Torvalds
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.cto 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){
- structtask_struct*p;
-
-list_for_each_entry(p, &tsk->children, sibling){
+list_traverse(p, &tsk->children, sibling){
Quoted 7 lines
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.
Quoted 5 lines
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 usinglist_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.
Quoted 8 lines
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 inkernel/exit.c, but it does *not* convert the code inkernel/fork.c, which still does that old-style traversal:list_for_each_entry(child, &parent->children, sibling) {
Quoted 8 lines
and the
kernel/fork.ccode 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 thatlist_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.
Quoted 11 lines
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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable
In reply to Linus TorvaldsHi 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/]
Signature · 1 line
Michał Mirosław
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable
Quoted 4 lines · Michał Mirosław
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):
Oh, I thought of it.
It gets complicated.
For example, a type that refers to a list of itself (and 'struct task_struct' is one such example) cannot actually refer to that other member name while declaring the head entry.
That's true even if the target member was declared before the head that points to it - because the type just hasn't been fully instantiated yet, so you can't refer to it AT ALL.
And even if that wasn't the case - and we could refer to previous members during the initialization of subsequent ones - you'd still end up with circular issues when one type has a list of another type, which has a list of the first type.
Which I'm also fairly certain does happen.
With regular "circular pointers", the trick is to just pre-declare the type, ie
struct second;
struct first {
.. define here, can use 'struct second *'
};
struct second {
.. define here, can use 'struct first *'
};but that only works as long as you only use a pointer to that type. You can't actually use 'offsetof()' of the members that haven't been described yet.
Now, you can combine that "pre-declare the type" model with the "do the offsetof later", but it gets nasty.
So I actually think it *can* be made to work, but not using your "pointer to an array of the right size". I think you have to
- pre-declare another type (the name needs to be a mix of both the
base type and the target type) with one macro
- use a pointer to that as-yet undefined but declared type it in that
union defined by list_traversal_head() type
- then, later on, when that target type has been fully defined, have
a *different* macro that then creates the actual type, which can now have the right size, because the target has been declared
But that means that you can't really describe that thing inside just the list_traversal_head() thing, you need *another* place that firsat declares that type, and then a *third* place that defines that final the type once all the pieces are in hand.
So it gets a lot uglier. But yes, I do believe it it's doable with those extra steps.
The extra steps can at least be sanity-checked by that name, so there's some "cross-verification" that you get all the pieces right, but it ends up being pretty nasty.
It's extra nasty because that type-name ends up having to contain both the source and destination types, and the member name. We could avoid that before, because the 'name##_traversal_type' thing was entirely internal to the source structure that contains the head, so we didn't need to name that source structure - it was all very naturally encapsulated.
So you'd have to do something like
#define list_traversal_declare(src, head, dst, member) \
struct src##_##head##_##dst##_##member##_offset_type
#define list_traversal_defile(src, head, dst, member) \
list_traversal_declare(src,head,dst,member) { \
char[offsetof(struct dst, member); \
} #define list_traversal_head(src, name, dst, member) \
union {
struct list_head name; \
struct dst *name##_traversal_type; \
list_traversal_declare(src,head,dst,member) *name##_target_type_offset;
}and then you'd have to do
list_traversal_declare(task_struct, children, task_struct, sibling);
struct task_struct {
...
list_traversal_entry(task_struct, children, task_struct, sibling);
..
};
list_traversal_define(task_struct, children, task_struct, sibling);and now list_traversal() itself can use 'sizeof(*name##_target_type_offset)' to get that offset.
NOTE! All of the above was written in my MUA with absolutely no testing, just "I think something like this will work". And note how really ugly it gets.
So. Doable? Yes. But at a pretty horrid cost - not just inside the "list_traverse()" macro, but in that now the places declaring how the list works get much much nastier.
Linus
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Michał Mirosław
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):
Oh, I thought of it.
It gets complicated.
[...]
It seems that it's not that bad if we don't require checking whether a list_head of an entry is only ever used with a single list parent. The source type is not needed for the macros, and it turns out that pre-declaring the offset type is also not needed.
I compile-tested the code below on godbolt.org with -std=c11:
struct list_head {
struct list_head *prev, *next;
};#define offsetof __builtin_offsetof
#define typeof __typeof
#define list_traversal_head(name,type,target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
char (*name##_list_head_offset)[offsetof(type, target_member)]; \
}#define self_list_ref_offset_type(type,target_member) \ type##__##target_member##__offset__
#define define_self_list_ref_offset(type,target_member) \
self_list_ref_offset_type(type,target_member) \
{ char ignoreme__[offsetof(type, target_member)]; }#define self_list_traversal_head(name,type,target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
self_list_ref_offset_type(type,target_member) *name##_list_head_offset; \
}#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, head)
#define list_traverse(pos, head) \
for (typeof(*head##_traversal_type) pos = list_traversal_entry((head)->next, head); \
!list_traversal_entry_is_head(pos, head); \
pos = list_traversal_next_entry(pos,head))struct entry {
self_list_traversal_head(self_list, struct entry, child_head);
struct list_head child_head;
};define_self_list_ref_offset(struct entry, child_head);
void bar(struct entry *b);
void foo(struct entry *a)
{
list_traverse(pos, &a->self_list) {
bar(pos);
}
}Signature · 1 line
Michał Mirosław
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable
Quoted 2 lines · Michał Mirosław
The source type is not needed for the macros [..]
Ahh. Yeah, as long as we don't do typedefs, it looks like we don't need to pre-declare the member access types.
I expected that to be required, because function declarations taking arguments need it, but that's because they create their own scope. Just doing it in a regular struct (or in this case union) declaration is fine.
So we would only need that post-declaration.
That said, your naming is wrong. It's not just about "self". It's any case where the type we iterate over is declared after the type that has the head.
So I suspect it would be a lot better to just always do it, and not do that "self vs non-self" distinction.
Linus
RFC PATCH 1/1 list: test: Add a test for list_traverse
In reply to Linus TorvaldsUpdate 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.
---
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(+)
lib/list-test.c +24 -0
@@ -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), {},
Signature · 1 line
2.35.1.723.g4982287a31-goog
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
In reply to Linus TorvaldsQuoted 11 lines · Linus Torvalds
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.
include/linux/list.h line 26
Quoted 7 lines
include/linux/list.h +0
-0@@ -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.
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 3 lines · Daniel Thompson
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:
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.
Quoted 5 lines
For architectures without
HAVE_LD_DEAD_CODE_DATA_ELIMINATIONthen the "obvious" extension oflist_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
Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable outside the loop
Quoted 11 lines · Linus Torvalds
Quoted 3 lines · Daniel Thompson
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:
Quoted 7 lines
which means that you can't actually append the
target_membername 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.
Quoted 7 lines
Quoted 6 lines
Quoted 1 line
[this bit used to quote the definition of
LIST_HEAD();-) ]For architectures without
HAVE_LD_DEAD_CODE_DATA_ELIMINATIONthen the "obvious" extension oflist_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).
Quoted 6 lines
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 'structlist_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.
PATCH 3/6 kernel: remove iterator use outside the loop
In reply to Xiaomeng TongDemonstrations for:
- list_for_each_entry_inside
- list_for_each_entry_continue_inside
- list_for_each_entry_safe_continue_inside
--- kernel/power/snapshot.c | 28 ++++++++++++++++------------ kernel/signal.c | 6 +++--- 2 files changed, 19 insertions(+), 15 deletions(-)
kernel/power/snapshot.c +16 -12
@@ -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); }
kernel/signal.c +3 -3
@@ -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; }
Signature · 1 line
2.17.1
Re: [PATCH 3/6] kernel: remove iterator use outside the loop
Quoted 4 lines · Xiaomeng Tong
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
Re: [PATCH 3/6] kernel: remove iterator use outside the loop
Quoted 11 lines · greg k-h
Quoted 4 lines · Xiaomeng Tong
Demonstrations for:
-list_for_each_entry_inside
-list_for_each_entry_continue_inside
-list_for_each_entry_safe_continue_insideThis 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
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
PATCH 4/6 mm: remove iterator use outside the loop
In reply to Xiaomeng TongDemonstrations 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
--- mm/list_lru.c | 10 ++++++---- mm/slab_common.c | 7 ++----- mm/vmalloc.c | 6 +++--- 3 files changed, 11 insertions(+), 12 deletions(-)
mm/list_lru.c +6 -4
@@ -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; }
mm/slab_common.c +2 -5
@@ -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
mm/vmalloc.c +3 -3
@@ -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 ;
Signature · 1 line
2.17.1
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
PATCH 5/6 net/core: remove iterator use outside the loop
In reply to Xiaomeng TongDemonstrations for:
- list_for_each_entry_safe_reverse_inside
--- net/core/gro.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
net/core/gro.c +1 -2
@@ -286,9 +286,8 @@ static void __napi_gro_flush_chain(struct napi_struct *napi, u32 index, bool flush_old) {struct list_head *head = &napi->gro_hash[index].list; -struct sk_buff *skb, *p; -list_for_each_entry_safe_reverse (skb, p, head, list) { + list_for_each_entry_safe_reverse_inside(skb, p, struct sk_buff, head, list) {if (flush_old &&NAPI_GRO_CB (skb)->age == jiffies)return ;skb_list_del_init (skb);
Signature · 1 line
2.17.1
Re: [PATCH 5/6] net/core: 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 "skp", "p") 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
PATCH 6/6 drivers/dma: remove iterator use outside the loop
In reply to Xiaomeng TongDemonstrations for:
- list_for_each_entry_from_inside
- list_for_each_entry_safe_from_inside
--- drivers/dma/iop-adma.c | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-)
drivers/dma/iop-adma.c +3 -6
@@ -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);
Signature · 1 line
2.17.1
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