| Message ID | 20220301075839.4156-3-xiam0nd.tong@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | list_for_each_entry*: make iterator invisiable outside the loop | expand |
Hi Xiaomeng, Thank you for the patch! Perhaps something to improve: [auto build test WARNING on linux/master] [also build test WARNING on vkoul-dmaengine/next soc/for-next linus/master v5.17-rc6 next-20220301] [cannot apply to hnaz-mm/master] [If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in https://git-scm.com/docs/git-format-patch] url: https://github.com/0day-ci/linux/commits/Xiaomeng-Tong/list_for_each_entry-make-iterator-invisiable-outside-the-loop/20220301-160113 base: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git 2c271fe77d52a0555161926c232cd5bc07178b39 reproduce: make htmldocs If you fix the issue, kindly add following tag as appropriate Reported-by: kernel test robot <lkp@intel.com> 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/kbuild-all@lists.01.org
On Tue, 2022-03-01 at 15:58 +0800, Xiaomeng Tong wrote: > For each list_for_each_entry* macros(10 variants), implements a > respective > new *_inside one. Such as the new macro list_for_each_entry_inside > for > list_for_each_entry. The idea is to be as compatible with the > original > interface as possible and to minimize code changes. > > Here are 2 examples: > > list_for_each_entry_inside: > - declare the iterator-variable pos inside the loop. Thus, the > origin > declare of the inputed *pos* outside the loop should be removed. > In > other words, the inputed *pos* now is just a string name. > - add a new "type" argument as the type of the container struct this > is > embedded in, and should be inputed when calling the macro. > > list_for_each_entry_safe_continue_inside: > - declare the iterator-variable pos and n inside the loop. Thus, the > origin declares of the inputed *pos* and *n* outside the loop > should > be removed. In other words, the inputed *pos* and *n* now are just > string name. > - add a new "start" argument as the given iterator to start with and > can be used to get the container struct *type*. This should be > inputed > when calling the macro. > > Signed-off-by: Xiaomeng Tong <xiam0nd.tong@gmail.com> > --- > include/linux/list.h | 156 > +++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 156 insertions(+) > > diff --git a/include/linux/list.h b/include/linux/list.h > index dd6c2041d..1595ce865 100644 > --- a/include/linux/list.h > +++ b/include/linux/list.h > @@ -639,6 +639,19 @@ static inline void list_splice_tail_init(struct > list_head *list, > !list_entry_is_head(pos, head, member); > \ > pos = list_next_entry(pos, member)) > > +/** > + * list_for_each_entry_inside > + * - iterate over list of given type and keep iterator inside the > loop > + * @pos: the type * to use as a loop cursor. > + * @type: the type of the container struct this is embedded in. > + * @head: the head for your list. > + * @member: the name of the list_head within the struct. > + */ > +#define list_for_each_entry_inside(pos, type, head, member) > \ > + for (type * pos = list_first_entry(head, type, member); > \ > + !list_entry_is_head(pos, head, member); > \ > + pos = list_next_entry(pos, member)) > + > pos shouldn't be an input to the macro since it's being declared inside it. All that will do will set up confusion about the shadowing of pos. The macro should still work as #define list_for_each_entry_inside(type, head, member) \ ... For safety, you could #define POS __UNIQUE_ID(pos) and use POS as the loop variable .. you'll have to go through an intermediate macro to get it to be stable. There are examples in linux/rcupdate.h James
On Wed, 02 Mar 2022 08:02:23 -0500, James Bottomley <James.Bottomley@HansenPartnership.com> wrote: > pos shouldn't be an input to the macro since it's being declared inside > it. All that will do will set up confusion about the shadowing of pos. > The macro should still work as > > #define list_for_each_entry_inside(type, head, member) \ > ... > > For safety, you could > > #define POS __UNIQUE_ID(pos) > > and use POS as the loop variable .. you'll have to go through an > intermediate macro to get it to be stable. There are examples in > linux/rcupdate.h The outer "pos" variable is no longer needed and thus the declare statement before the loop is removed, see the demostration in PATCH 3~6. Now, there is only one inner "pos" variable left. Thus, there should be no such *shadow* problem. Please remind me if i missed something, thanks. -- Xiaomeng Tong
On Mon, Feb 28, 2022 at 11:59 PM Xiaomeng Tong <xiam0nd.tong@gmail.com> wrote: > > +#define list_for_each_entry_inside(pos, type, head, member) \ So as mentioned in another thread, I actually tried exactly this. And it was horrendous. It's _technically_ probably a very nice solution, but - it means that the already *good* cases are the ones that are penalized by having to change - the syntax of the thing becomes absolutely nasty which means that _practially_ it's exactly the wrong thing to do. Just as an example, this is a random current "good user" in kernel/exit.c: - list_for_each_entry_safe(p, n, dead, ptrace_entry) { + list_for_each_entry_safe_inside(p, n, struct task_struct, dead, ptrace_entry) { and while some of the effects are nice (no need to declare p/n ahead of time), just look at how nasty that line is. Basically every single use will result in an over-long line. The above example has minimal indentation, almost minimal variable names (to the point of not being very descriptive at all), and one of the most basic kernel structure types. And it still ended up 87 columns wide. And no, the answer to that is not "do it on multiple lines then". That is just even worse. So I really think this is a major step in the wrong direction. We should strive for the *bad* cases to have to do extra work, and even there we should really strive for legibility. Now, I think that "safe" version in particular can be simplified: there's no reason to give the "n" variable a name. Now that we can (with -stc=gnu11) just declare our own variables in the for-loop, the need for that externally visible 'next' declaration just goes away. So three of those 87 columns are pointless and should be removed. The macro can just internally decare 'n' like it always wanted (but couldn't do due to legacy C language syntax restrictions). But even with that fixed, it's still a very cumbersome line. Note how the old syntax was "only" 60 characters - long but still quite legible (and would have space for two more levels of indentation without even hitting 80 characters). And that was _despute_ having to have that 'n' declaration. And yes, the old syntax does require that struct task_struct *p, *n; line to declare the types, but that really is not a huge burden, and is not complicated. It's just another "variables of the right type" line (and as mentioned, the 'n' part has always been a C syntax annoyance). Linus
First of all, thank you very much for your patient reply and valuable comments. This is a great inspiration to me. > On Mon, Feb 28, 2022 at 11:59 PM Xiaomeng Tong <xiam0nd.tong@gmail.com> wrote: > > > > +#define list_for_each_entry_inside(pos, type, head, member) \ > > So as mentioned in another thread, I actually tried exactly this. > > And it was horrendous. > > It's _technically_ probably a very nice solution, but Yes, I always think it is a perfect solution _technically_, since you first proposed in the thread of Jakob's first subject. > > - it means that the already *good* cases are the ones that are > penalized by having to change Yes, but it also kills potential risks that one day somebody mistakely uses iterator after the loop in this already *good* cases, as it removed the original declare of pos and any use-after-loop will be catched by compiler. > > - the syntax of the thing becomes absolutely nasty > > which means that _practially_ it's exactly the wrong thing to do. > > Just as an example, this is a random current "good user" in kernel/exit.c: > > - list_for_each_entry_safe(p, n, dead, ptrace_entry) { > + list_for_each_entry_safe_inside(p, n, struct task_struct, > dead, ptrace_entry) { > > and while some of the effects are nice (no need to declare p/n ahead > of time), just look at how nasty that line is. > > Basically every single use will result in an over-long line. The above > example has minimal indentation, almost minimal variable names (to the > point of not being very descriptive at all), and one of the most basic > kernel structure types. And it still ended up 87 columns wide. > > And no, the answer to that is not "do it on multiple lines then". > That is just even worse. Two avoid multiple lines, there are some mitigations: 1. use a shorter macro name: (add 2 chars) list_for_each_entry_i instead of list_for_each_entry_inside 2. using a shorter type passing to the macro: (add 3 chars) + #define t struct sram_bank_info - list_for_each_entry(pos, head, member) { + list_for_each_entry_i(pos, t, head, member) { 3. restore all name back to list_for_each_entry after everything is done: (minus 2 chars) Although we need replace all the use of list_for_each_entry* (15000+) with list_for_each_entry*_i, the work can be done gradually rather than all at once. We can incrementally replace these callers until all these in the kernel are completely updated with *_i* one. At that time, we can just remove the implements of origin macros and rename the *_i* macro back to the origin name just in one single patch. 4. As you mentioned, the "safe" version of list_for_each_entry do not need "n" argument anymore with the help of -std=gnu11. (minus 3 chars) Thus, after all mitigations applied, the "safe" version adds *no* chars to columns wide, and other version adds 3 chars totally, which is acceptable to me. > > So I really think this is a major step in the wrong direction. Maybe yes or maybe no. Before the list_for_each_entry_inside way, I have tried something like "typeof(pos) pos" way as and before you proposed in the thread of Jakob's second subject, to avoid any changes to callers of the macros. But it also has potential problems. see my previous reply to you here: https://lore.kernel.org/lkml/20220302093106.8402-1-xiam0nd.tong@gmail.com/ > > We should strive for the *bad* cases to have to do extra work, and > even there we should really strive for legibility. Indeed, there are many "multiple lines" problems in the current kernel code, for example (drivers/dma/iop-adma.c): list_for_each_entry_from(grp_iter, &iop_chan->chain, chain_node) { > > Now, I think that "safe" version in particular can be simplified: > there's no reason to give the "n" variable a name. Now that we can > (with -stc=gnu11) just declare our own variables in the for-loop, the > need for that externally visible 'next' declaration just goes away. > > So three of those 87 columns are pointless and should be removed. The > macro can just internally decare 'n' like it always wanted (but > couldn't do due to legacy C language syntax restrictions). Great, this does reduce three chars. and i will look into other versions. > > But even with that fixed, it's still a very cumbersome line. With other mitigations mentioned above, the addition to line will be acceptable. > > Note how the old syntax was "only" 60 characters - long but still > quite legible (and would have space for two more levels of indentation > without even hitting 80 characters). And that was _despute_ having to > have that 'n' declaration. > > And yes, the old syntax does require that > > struct task_struct *p, *n; > > line to declare the types, but that really is not a huge burden, and > is not complicated. It's just another "variables of the right type" > line (and as mentioned, the 'n' part has always been a C syntax > annoyance). Yes, that really is not a huge burden, so is the mitigation 2 mentioned above which defining a shorter type passing to the macro, to shorten the new line. > > Linus -- Xiaomeng Tong
On Thu, Mar 3, 2022 at 6:51 PM Xiaomeng Tong <xiam0nd.tong@gmail.com> wrote: > > > - it means that the already *good* cases are the ones that are > > penalized by having to change > > Yes, but it also kills potential risks that one day somebody mistakely > uses iterator after the loop in this already *good* cases, as it removed > the original declare of pos and any use-after-loop will be catched by > compiler. The thing is, I think we already have a solution to that case. I think it's the bad "entry used outside" that we need to care about doing well. > 3. restore all name back to list_for_each_entry after everything is done: > (minus 2 chars) You are ignoring the big elephant in the room - counting the small things, but not counting the BIG thing. That type name argument is long. Right now we avoid it by pre-declaring it, and that's in many ways the natural thing to do in C (you don't declare types in the place that uses them, you declare the types in the variable declarations above the code). Now, I'd love for the list head entry itself to "declare the type", and solve it that way. That would in many ways be the optimal situation, in that when a structure has that struct list_head xyz; entry, it would be lovely to declare *there* what the list entry type is - and have 'list_for_each_entry()' just pick it up that way. It would be doable in theory - with some preprocessor trickery all the 'struct list_head' things *could* be made to be unnamed unions of the list head, and the actual type it points to, ie something like #define declare_list_head(type,type) union { struct list_head x; type *x##_list_type; } and then (to pick one particular example), we could make the "struct task_struct" entry for children be - struct list_head children; + declare_list_head(struct task_struct, children); and now when you use list_for_each_entry(p, &father->children, sibling) { you could actually pick out the type with some really ugly preprocessor crud, by doing 'typeof(*head##_list_type)' to get the type of the thing we iterate over. So we *could* embed the type that a list head points to with tricks like that. The it would actually be type-safe, and not need a declaration of the type anywhere. And it would be kind of nice to document "this is a list head pointer to this kind of type". And yes, it would be even better if we could also encode the member name that contains the list entries somehow (ie in this case the 'sibling' list entry of the task struct) so that you'd really document the full chain. But even my twisted mind cannot come up with any tricks to do *that*. But the above would be quite a *major* change. And the above kind of preprocessor trickery and encoding a secondary type as a union entry that isn't actually used for anythign else may be too ugly to live anyway. Linus
On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds <torvalds@linux-foundation.org> wrote: > > Now, I'd love for the list head entry itself to "declare the type", > and solve it that way. That would in many ways be the optimal > situation, in that when a structure has that > > struct list_head xyz; > > entry, it would be lovely to declare *there* what the list entry type > is - and have 'list_for_each_entry()' just pick it up that way. > > It would be doable in theory - with some preprocessor trickery [...] Ok, I decided to look at how that theory looks in real life. The attached patch does actually work for me. I'm not saying this is *beautiful*, but I made the changes to kernel/exit.c to show how this can be used, and while the preprocessor tricks and the odd "unnamed union with a special member to give the target type" is all kinds of hacky, the actual use case code looks quite nice. In particular, look at the "good case" list_for_each_entry() transformation: static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk) { - struct task_struct *p; - - list_for_each_entry(p, &tsk->children, sibling) { + list_traverse(p, &tsk->children, sibling) { IOW, it avoided the need to declare 'p' entirely, and it avoids the need for a type, because the macro now *knows* the type of that 'tsk->children' list and picks it out automatically. So 'list_traverse()' is basically a simplified version of 'list_for_each_entry()'. That patch also has - as another example - the "use outside the loop" case in mm_update_next_owner(). That is more of a "rewrite the loop cleanly using list_traverse() thing, but it's also quite simple and natural. One nice part of this approach is that it allows for incremental changes. In fact, the patch very much is meant to demonstrate exactly that: yes, it converts the uses in kernel/exit.c, but it does *not* convert the code in kernel/fork.c, which still does that old-style traversal: list_for_each_entry(child, &parent->children, sibling) { and the kernel/fork.c code continues to work as well as it ever did. So that new 'list_traverse()' function allows for people to say "ok, I will now declare that list head with that list_traversal_head() macro, and then I can convert 'list_for_each_entry()' users one by one to this simpler syntax that also doesn't allow the list iterator to be used outside the list. What do people think? Is this clever and useful, or just too subtle and odd to exist? NOTE! I decided to add that "name of the target head in the target type" to the list_traversal_head() macro, but it's not actually used as is. It's more of a wishful "maybe we could add some sanity checking of the target list entries later". Comments? Linus
> On 6. Mar 2022, at 01:35, Linus Torvalds <torvalds@linux-foundation.org> wrote: > > On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds > <torvalds@linux-foundation.org> wrote: >> >> Now, I'd love for the list head entry itself to "declare the type", >> and solve it that way. That would in many ways be the optimal >> situation, in that when a structure has that >> >> struct list_head xyz; >> >> entry, it would be lovely to declare *there* what the list entry type >> is - and have 'list_for_each_entry()' just pick it up that way. >> >> It would be doable in theory - with some preprocessor trickery [...] > > Ok, I decided to look at how that theory looks in real life. > > The attached patch does actually work for me. I'm not saying this is > *beautiful*, but I made the changes to kernel/exit.c to show how this > can be used, and while the preprocessor tricks and the odd "unnamed > union with a special member to give the target type" is all kinds of > hacky, the actual use case code looks quite nice. > > In particular, look at the "good case" list_for_each_entry() transformation: > > static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk) > { > - struct task_struct *p; > - > - list_for_each_entry(p, &tsk->children, sibling) { > + list_traverse(p, &tsk->children, sibling) { > > IOW, it avoided the need to declare 'p' entirely, and it avoids the > need for a type, because the macro now *knows* the type of that > 'tsk->children' list and picks it out automatically. > > So 'list_traverse()' is basically a simplified version of > 'list_for_each_entry()'. > > That patch also has - as another example - the "use outside the loop" > case in mm_update_next_owner(). That is more of a "rewrite the loop > cleanly using list_traverse() thing, but it's also quite simple and > natural. > > One nice part of this approach is that it allows for incremental changes. > > In fact, the patch very much is meant to demonstrate exactly that: > yes, it converts the uses in kernel/exit.c, but it does *not* convert > the code in kernel/fork.c, which still does that old-style traversal: > > list_for_each_entry(child, &parent->children, sibling) { > > and the kernel/fork.c code continues to work as well as it ever did. > > So that new 'list_traverse()' function allows for people to say "ok, I > will now declare that list head with that list_traversal_head() macro, > and then I can convert 'list_for_each_entry()' users one by one to > this simpler syntax that also doesn't allow the list iterator to be > used outside the list. > > What do people think? Is this clever and useful, or just too subtle > and odd to exist? > > NOTE! I decided to add that "name of the target head in the target > type" to the list_traversal_head() macro, but it's not actually used > as is. It's more of a wishful "maybe we could add some sanity checking > of the target list entries later". > > Comments? I guess we could apply this to list_for_each_entry() as well once all the uses after the loop are fixed? I feel like this simply introduces a new set of macros (we would also need list_traverse_reverse(), list_traverse_continue_reverse() etc) and end up with a second set of macros that do pretty much the same as the first one. I like the way of using list_traversal_head() to only remember the type. The interface of list_traverse() is the same as list_for_each_entry() so we could just do this with a simple coccinelle script once 'pos' is no longer used after the loop: -struct some_struct *pos; +list_traversal_head(struct some_struct, pos, target_member); although there are *some* cases where 'pos' is also used separately in the function which would need to change, e.g.: struct some_struct *pos = some_variable; if (pos) // do one thing else list_for_each_entry(pos, ..., ...) (I've fixed ~440/450 cases now and I'm chunking it into patch sets right now. The once left over are non-obvious code I would need some input on) Personally I guess I also prefer the name list_for_each_entry() over list_traverse() and not having two types of iterators for the same thing at the same time. > > Linus > <patch.diff> Jakob
On Sat, 5 Mar 2022 16:35:36 -0800 Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds > <torvalds@linux-foundation.org> wrote: > > > > Now, I'd love for the list head entry itself to "declare the type", > > and solve it that way. That would in many ways be the optimal > > situation, in that when a structure has that > > > > struct list_head xyz; > > > > entry, it would be lovely to declare *there* what the list entry type > > is - and have 'list_for_each_entry()' just pick it up that way. > > > > It would be doable in theory - with some preprocessor trickery [...] > > Ok, I decided to look at how that theory looks in real life. > > The attached patch does actually work for me. I'm not saying this is > *beautiful*, but I made the changes to kernel/exit.c to show how this > can be used, and while the preprocessor tricks and the odd "unnamed > union with a special member to give the target type" is all kinds of > hacky, the actual use case code looks quite nice. > > In particular, look at the "good case" list_for_each_entry() transformation: > > static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk) > { > - struct task_struct *p; > - > - list_for_each_entry(p, &tsk->children, sibling) { > + list_traverse(p, &tsk->children, sibling) { > > IOW, it avoided the need to declare 'p' entirely, and it avoids the > need for a type, because the macro now *knows* the type of that > 'tsk->children' list and picks it out automatically. > > So 'list_traverse()' is basically a simplified version of > 'list_for_each_entry()'. > Yes, brilliant! It is tricky and hacky. In your example: &tsk->children will be expanded to &tsk->children_traversal_type. And it also reduces column of the calling line with simplified version of list_for_each_entry. But, maybe there are some more cases the union-based way need to handle. Such as, in your example, if the &HEAD passing to list_for_each_entry is *not* "&tsk->children", but just a *naked head* with no any extra information provoided: void foo(...) { bar(&tsk->children); } noinline void bar(struct list_head *naked_head) { struct task_struct *p; list_for_each_entry(p, naked_head, sibling) { ... } } you should change all declares like "struct list_head" here with the union one, but not only in the structure of task_struct itself. I'm going to dig into this union-base way and re-send a patch if necessary. > That patch also has - as another example - the "use outside the loop" > case in mm_update_next_owner(). That is more of a "rewrite the loop > cleanly using list_traverse() thing, but it's also quite simple and > natural. > Yes, the "c" is as the found entry for outside use -- it is natural. And the "pos" as a inside-defined variable -- it is our goal. And the "continue" trick to reduce 1 line -- it is nice. > One nice part of this approach is that it allows for incremental changes. > > In fact, the patch very much is meant to demonstrate exactly that: > yes, it converts the uses in kernel/exit.c, but it does *not* convert > the code in kernel/fork.c, which still does that old-style traversal: > > list_for_each_entry(child, &parent->children, sibling) { > > and the kernel/fork.c code continues to work as well as it ever did. > > So that new 'list_traverse()' function allows for people to say "ok, I > will now declare that list head with that list_traversal_head() macro, > and then I can convert 'list_for_each_entry()' users one by one to > this simpler syntax that also doesn't allow the list iterator to be > used outside the list. > Yes, i am very glad that you accepted and agreed my suggestion for the *incremental changes* part, just like my "_inside" way used. It means a lot for me to have your approval. > What do people think? Is this clever and useful, or just too subtle > and odd to exist? > > NOTE! I decided to add that "name of the target head in the target > type" to the list_traversal_head() macro, but it's not actually used > as is. It's more of a wishful "maybe we could add some sanity checking > of the target list entries later". > > Comments? > > Linus -- Xiaomeng Tong
On Thu, 2022-03-03 at 11:31 +0800, Xiaomeng Tong wrote: > On Wed, 02 Mar 2022 08:02:23 -0500, James Bottomley > <James.Bottomley@HansenPartnership.com> wrote: > > pos shouldn't be an input to the macro since it's being declared > > inside > > it. All that will do will set up confusion about the shadowing of > > pos. > > The macro should still work as > > > > #define list_for_each_entry_inside(type, head, member) \ > > ... > > > > For safety, you could > > > > #define POS __UNIQUE_ID(pos) > > > > and use POS as the loop variable .. you'll have to go through an > > intermediate macro to get it to be stable. There are examples in > > linux/rcupdate.h > > The outer "pos" variable is no longer needed and thus the declare > statement before the loop is removed, see the demostration in PATCH > 3~6. Now, there is only one inner "pos" variable left. Thus, there > should be no such *shadow* problem. So why is pos in the signature of your #define then? Because that means it expands to whatever goes in the first field of list_for_each_entry_inside(). If someone needs to specify a unique name to avoid shadowing an existing variable, then hide pos and use UNIQUE_ID instead was the whole thrust of this comment. James
On Sun, Mar 6, 2022 at 4:19 AM Jakob Koschel <jakobkoschel@gmail.com> wrote: > > I guess we could apply this to list_for_each_entry() as well > once all the uses after the loop are fixed? I think that would be a good longer-term plan. "list_traverse()" ends up being simpler syntactically, and has a certain level of inherent type safety (not just the "don't expose the mis-typed head pointer after the loop"). > I feel like this simply introduces a new set of macros > (we would also need list_traverse_reverse(), list_traverse_continue_reverse() > etc) and end up with a second set of macros that do pretty much > the same as the first one. I think that if we're happy with this, we can probably do a scripted conversion. But I do like how it's incremental, in that we wouldn't necessarily have to do it all in one go. Because it's always really painful with flag-day interface changes, which it would be to actually change the semantics of "list_for_each_entry()" without a name change. It just makes for a lot of pain for things that aren't in-tree yet (not just drivers that are out-of-tree in general, but drivers in development etc). And I really disliked the "pass the type to the list_for_each()" macro, because of how it made the end result look more complex. But list_traverse() looks like it would make the end result better both from a user perspective (ie the code just looks simpler) but also from the type safety point. > Personally I guess I also prefer the name list_for_each_entry() over list_traverse() > and not having two types of iterators for the same thing at the same time. I absolutely agree with you in theory, and in many ways I like list_for_each_entry() better as a name too (probably just because I'm used to it). But keeping the same name and changing how it works ends up being such a "everything at once" thing that I don't think it's realistic. Linus
Hi Linus,
If the macro implementation doesn't have to be pretty, maybe it could go
a step further and remember the list_head's offset? That would look
something like following (expanding on your patch; not compile tested):
#define list_traversal_head(type,name,target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
char (*name##_list_head_offset)[offsetof(type, target_member)]; \
}
#define list_traversal_entry(ptr, head) \
(typeof(*head##_traversal_type))((void *)ptr - sizeof(**head##_list_head_offset))
#define list_traversal_entry_head(ptr, head) \
(struct list_head *)((void *)ptr + sizeof(**head##_list_head_offset))
#define list_traversal_entry_is_head(ptr, head) \
(list_traversal_entry_head(ptr, head) == (head))
#define list_traversal_next_entry(ptr, head) \
list_traversal_entry(list_traversal_entry_head(ptr, head)->next)
#define list_traverse(pos, head) \
for (typeof(*head##_traversal_type) pos = list_traversal_entry((head)->next); \
!list_traversal_entry_head(pos, head) == (head); \
pos = list_traversal_next_entry(pos, head))
[Sorry for lack of citations - I found the thread via https://lwn.net/Articles/887097/]
On Thu, Mar 10, 2022 at 3:54 PM Michał Mirosław <mirq-linux@rere.qmqm.pl> wrote: > > 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
On Sat, Mar 05, 2022 at 04:35:36PM -0800, Linus Torvalds wrote: > On Sat, Mar 5, 2022 at 1:09 PM Linus Torvalds > <torvalds@linux-foundation.org> wrote: > What do people think? Is this clever and useful, or just too > subtle and odd to exist? > NOTE! I decided to add that "name of the target head in the target > type" to the list_traversal_head() macro, but it's not actually used > as is. It's more of a wishful "maybe we could add some sanity checking > of the target list entries later". > > Comments? It is possible simply to use spelling to help uncover errors in list_traverse()? Something like: #define list_traversal_head(type, name, target_member) \ union { \ struct list_head name; \ type *name##_traversal_mismatch_##target_member; \ } And: #define list_traverse(pos, head, member) \ for (typeof(*head##_traversal_mismatch_##member) pos = list_first_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member)) If I deliberately insert an error into your modified exit.c then the resulting errors even make helpful suggestions about what you did wrong: kernel/exit.c:412:32: error: ‘struct task_struct’ has no member named ‘children_traversal_mismatch_children’; did you mean ‘children_traversal_mismatch_sibling’? The suggestions are not always as good as the above (children_traversal_mismatch_ptrace_entry suggests ptraced_traversal_mismatch_ptrace_entry) but, nevertheless, it does appears to be robust in detecting incorrect traversal. > diff --git a/include/linux/list.h b/include/linux/list.h > index dd6c2041d09c..1e8b3e495b51 100644 > --- a/include/linux/list.h > +++ b/include/linux/list.h > @@ -25,6 +25,9 @@ > #define LIST_HEAD(name) \ > struct list_head name = LIST_HEAD_INIT(name) Seeing this in the diff did set me thinking about static/global list heads. For architectures without HAVE_LD_DEAD_CODE_DATA_ELIMINATION then the "obvious" extension of list_traversal_head() ends up occupying bss space. Even replacing the pointer with a zero length array is still provoking gcc-11 (arm64) to allocate a byte from bss (often with a lot of padding added). Perhaps in the grand scheme of things this doesn't matter. Across the whole tree and all architecture I see only ~1200 instances so even in the worst case and with padding everywhere the wasted RAM is only a few kb. Nevertheless I was curious if there is any cunning tricks to avoid this? Naturally LIST_HEAD() could just declare a union but that would require all sites of use to be updated simultaneously and I rather like the way list_traverse_head() is entirely incremental. Daniel.
On Fri, Mar 11, 2022 at 6:27 AM Daniel Thompson <daniel.thompson@linaro.org> wrote: > > It is possible simply to use spelling to help uncover errors in > list_traverse()? I'd love to, and thought that would be a lovely idea, but in another thread ("") Barnabás Pőcze pointed out that we actually have a fair number of cases where the list member entries are embedded in internal structures and have a '.' in them: https://lore.kernel.org/all/wKlkWvCGvBrBjshT6gHT23JY9kWImhFPmTKfZWtN5Bkv_OtIFHTy7thr5SAEL6sYDthMDth-rvFETX-gCZPPCb9t2bO1zilj0Q-OTTSbe00=@protonmail.com/ which means that you can't actually append the target_member name except in the simplest cases, because it wouldn't result in one single identifier. Otherwise it would be a lovely idea. > For architectures without HAVE_LD_DEAD_CODE_DATA_ELIMINATION then the > "obvious" extension of list_traversal_head() ends up occupying bss > space. Even replacing the pointer with a zero length array is still > provoking gcc-11 (arm64) to allocate a byte from bss (often with a lot > of padding added). I think compilers give objects at least one byte of space, so that two different objects get different addresses, and don't compare equal. That said, I'm not seeing your issue. list_traversal_head() is a union, and always has that 'struct list_head' in it, and that's the biggest part of the union. IOW, the other parts are (a) never used for anything but their type and (b) will not take up any new space that isn't already used by the list_head itself. Linus
On Thu, Mar 10, 2022 at 04:46:33PM -0800, Linus Torvalds wrote: > On Thu, Mar 10, 2022 at 3:54 PM Michał Mirosław <mirq-linux@rere.qmqm.pl> wrote: > > > > 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); } }
On Sat, Mar 12, 2022 at 2:24 AM Michał Mirosław <mirq-linux@rere.qmqm.pl> wrote: > > 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
On Fri, Mar 11, 2022 at 10:41:06AM -0800, Linus Torvalds wrote: > On Fri, Mar 11, 2022 at 6:27 AM Daniel Thompson > <daniel.thompson@linaro.org> wrote: > > > > It is possible simply to use spelling to help uncover errors in > > list_traverse()? > > I'd love to, and thought that would be a lovely idea, but in another > thread ("") Barnabás Pőcze pointed out that we actually have a fair > number of cases where the list member entries are embedded in internal > structures and have a '.' in them: > > https://lore.kernel.org/all/wKlkWvCGvBrBjshT6gHT23JY9kWImhFPmTKfZWtN5Bkv_OtIFHTy7thr5SAEL6sYDthMDth-rvFETX-gCZPPCb9t2bO1zilj0Q-OTTSbe00=@protonmail.com/ > > which means that you can't actually append the target_member name > except in the simplest cases, because it wouldn't result in one single > identifier. > > Otherwise it would be a lovely idea. When I prototyped this I did actually include a backdoor to cover situations like this but I ended up (incorrectly at appears) editing it out for simplicity. Basically the union is free so we can have more than one type * member: #define list_traversal_head(type, name, target_member) \ union { \ struct list_head name; \ type *name##_traversal_type; \ type *name##_traversal_mismatch_##target_member; \ } This allows that the single structure cases to be checked whilst nested structures (and array which I noticed also crop up) have a trap door such as list_traverse_unchecked(). I did a quick grep to estimate how many nested/array cases there are and came up with around 2.5% (roughly ~200 in ~8500, counting only the single line users of list_for_each_entry() ). As you say, lovely idea but having to use special API 2.5% of the time seems a bit on the high side. BTW, a complete aside, but whilst I was looking for trouble I also spotted code where the list head is an array which means we are not able to lookup the travesral type correctly: list_for_each_entry(modes[i], &connector->modes, head) However I found only one instance of this so it much more acceptable rate of special cases than the 2.5% above. > > > [this bit used to quote the definition of LIST_HEAD() ;-) ] > > For architectures without HAVE_LD_DEAD_CODE_DATA_ELIMINATION then the > > "obvious" extension of list_traversal_head() ends up occupying bss > > space. Even replacing the pointer with a zero length array is still > > provoking gcc-11 (arm64) to allocate a byte from bss (often with a lot > > of padding added). > > I think compilers give objects at least one byte of space, so that two > different objects get different addresses, and don't compare equal. > > That said, I'm not seeing your issue. list_traversal_head() is a > union, and always has that 'struct list_head' in it, and that's the > biggest part of the union. Perhaps its a bit overblown for the safe of a few kilobytes (even if there were two traversal types members) but I was wondering if there is any cunning trick for LIST_HEAD() since we cannot have an anonymous union outside a struct. In short, is this the best we can do for LIST_TRAVERSE_HEAD(): #define LIST_TRAVERSE_HEAD(type, name, target_member) \ type * name##_traversal_type; \ struct list_head name = LIST_HEAD_INIT(name) #define STATIC_LIST_TRAVERSE_HEAD(type, name, target_member) \ static type * name##_traversal_type; \ static list_head name = LIST_HEAD_INIT(name) Daniel.
diff --git a/include/linux/list.h b/include/linux/list.h index dd6c2041d..1595ce865 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -639,6 +639,19 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member)) +/** + * list_for_each_entry_inside + * - iterate over list of given type and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @type: the type of the container struct this is embedded in. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + */ +#define list_for_each_entry_inside(pos, type, head, member) \ + for (type * pos = list_first_entry(head, type, member); \ + !list_entry_is_head(pos, head, member); \ + pos = list_next_entry(pos, member)) + /** * list_for_each_entry_reverse - iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. @@ -650,6 +663,19 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member)) +/** + * list_for_each_entry_reverse_inside + * - iterate backwards over list of given type and keep iterator inside the loop. + * @pos: the type * to use as a loop cursor. + * @type: the type of the container struct this is embedded in. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + */ +#define list_for_each_entry_reverse_inside(pos, type, head, member) \ + for (type * pos = list_last_entry(head, type, member); \ + !list_entry_is_head(pos, head, member); \ + pos = list_prev_entry(pos, member)) + /** * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() * @pos: the type * to use as a start point @@ -675,6 +701,22 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member)) +/** + * list_for_each_entry_continue_inside + * - continue iteration over list of given type and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @start: the given iterator to start with. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Continue to iterate over list of given type, continuing after + * the current position. + */ +#define list_for_each_entry_continue_inside(pos, start, head, member) \ + for (typeof(*start) *pos = list_next_entry(start, member); \ + !list_entry_is_head(pos, head, member); \ + pos = list_next_entry(pos, member)) + /** * list_for_each_entry_continue_reverse - iterate backwards from the given point * @pos: the type * to use as a loop cursor. @@ -689,6 +731,22 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member)) +/** + * list_for_each_entry_continue_reverse_inside + * - iterate backwards from the given point and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @start: the given iterator to start with. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Start to iterate over list of given type backwards, continuing after + * the current position. + */ +#define list_for_each_entry_continue_reverse_inside(pos, start, head, member) \ + for (typeof(*start) *pos = list_prev_entry(start, member); \ + !list_entry_is_head(pos, head, member); \ + pos = list_prev_entry(pos, member)) + /** * list_for_each_entry_from - iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. @@ -701,6 +759,20 @@ static inline void list_splice_tail_init(struct list_head *list, for (; !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member)) +/** + * list_for_each_entry_from_inside + * - iterate over list of given type from the current point and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @start: the given iterator to start with. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Iterate over list of given type, continuing from current position. + */ +#define list_for_each_entry_from_inside(pos, start, head, member) \ + for (typeof(*start) *pos = start; !list_entry_is_head(pos, head, member); \ + pos = list_next_entry(pos, member)) + /** * list_for_each_entry_from_reverse - iterate backwards over list of given type * from the current point @@ -714,6 +786,21 @@ static inline void list_splice_tail_init(struct list_head *list, for (; !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member)) +/** + * list_for_each_entry_from_reverse_inside + * - iterate backwards over list of given type from the current point + * and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @start: the given iterator to start with. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Iterate backwards over list of given type, continuing from current position. + */ +#define list_for_each_entry_from_reverse_inside(pos, start, head, member) \ + for (typeof(*start) *pos = start; !list_entry_is_head(pos, head, member); \ + pos = list_prev_entry(pos, member)) + /** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. @@ -727,6 +814,22 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = n, n = list_next_entry(n, member)) +/** + * list_for_each_entry_safe_inside + * - iterate over list of given type safe against removal of list entry + * and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @type: the type of the container struct this is embedded in. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + */ +#define list_for_each_entry_safe_inside(pos, n, type, head, member) \ + for (type * pos = list_first_entry(head, type, member), \ + *n = list_next_entry(pos, member); \ + !list_entry_is_head(pos, head, member); \ + pos = n, n = list_next_entry(n, member)) + /** * list_for_each_entry_safe_continue - continue list iteration safe against removal * @pos: the type * to use as a loop cursor. @@ -743,6 +846,24 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = n, n = list_next_entry(n, member)) +/** + * list_for_each_entry_safe_continue_inside + * - continue list iteration safe against removal and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @start: the given iterator to start with. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Iterate over list of given type, continuing after current point, + * safe against removal of list entry. + */ +#define list_for_each_entry_safe_continue_inside(pos, n, start, head, member) \ + for (typeof(*start) *pos = list_next_entry(start, member), \ + *n = list_next_entry(pos, member); \ + !list_entry_is_head(pos, head, member); \ + pos = n, n = list_next_entry(n, member)) + /** * list_for_each_entry_safe_from - iterate over list from current point safe against removal * @pos: the type * to use as a loop cursor. @@ -758,6 +879,23 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = n, n = list_next_entry(n, member)) +/** + * list_for_each_entry_safe_from_inside + * - iterate over list from current point safe against removal and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @start: the given iterator to start with. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Iterate over list of given type from current point, safe against + * removal of list entry. + */ +#define list_for_each_entry_safe_from_inside(pos, n, start, head, member) \ + for (typeof(*start) *pos = start, *n = list_next_entry(pos, member); \ + !list_entry_is_head(pos, head, member); \ + pos = n, n = list_next_entry(n, member)) + /** * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal * @pos: the type * to use as a loop cursor. @@ -774,6 +912,24 @@ static inline void list_splice_tail_init(struct list_head *list, !list_entry_is_head(pos, head, member); \ pos = n, n = list_prev_entry(n, member)) +/** + * list_for_each_entry_safe_reverse_insde + * - iterate backwards over list safe against removal and keep iterator inside the loop + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @type: the type of the struct this is enmbeded in. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + * + * Iterate backwards over list of given type, safe against removal + * of list entry. + */ +#define list_for_each_entry_safe_reverse_inside(pos, n, type, head, member) \ + for (type * pos = list_last_entry(head, type, member), \ + *n = list_prev_entry(pos, member); \ + !list_entry_is_head(pos, head, member); \ + pos = n, n = list_prev_entry(n, member)) + /** * list_safe_reset_next - reset a stale list_for_each_entry_safe loop * @pos: the loop cursor used in the list_for_each_entry_safe loop
For each list_for_each_entry* macros(10 variants), implements a respective new *_inside one. Such as the new macro list_for_each_entry_inside for list_for_each_entry. The idea is to be as compatible with the original interface as possible and to minimize code changes. Here are 2 examples: list_for_each_entry_inside: - declare the iterator-variable pos inside the loop. Thus, the origin declare of the inputed *pos* outside the loop should be removed. In other words, the inputed *pos* now is just a string name. - add a new "type" argument as the type of the container struct this is embedded in, and should be inputed when calling the macro. list_for_each_entry_safe_continue_inside: - declare the iterator-variable pos and n inside the loop. Thus, the origin declares of the inputed *pos* and *n* outside the loop should be removed. In other words, the inputed *pos* and *n* now are just string name. - add a new "start" argument as the given iterator to start with and can be used to get the container struct *type*. This should be inputed when calling the macro. Signed-off-by: Xiaomeng Tong <xiam0nd.tong@gmail.com> --- include/linux/list.h | 156 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 156 insertions(+)