Re: hlist_for_each_entry && pos (Was: task_work_queue)

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Thu, Apr 12, 2012 at 06:00:59AM +0200, Oleg Nesterov wrote:
> On 04/12, Oleg Nesterov wrote:
> >
> > +	hlist_for_each_entry(twork, pos, &task->task_works, hlist) {
> 
> This reminds me.
> 
> hlist_for_each_entry_*() do not need "pos", it can be
> 
> 	#define hlist_for_each_entry(pos, head, member)					\
> 		for (pos = (void*)(head)->first;					\
> 		pos && ({ pos = hlist_entry((void*)pos, typeof(*pos), member); 1; });	\
> 		pos = (void*)(pos)->member.next)
> 
> The only problem, is there any possibility to change the callers
> somehow??? I even wrote the script which converts them all, but the
> patch is huge.
> 
> Please see the old (2008-04-21) message I sent to lkml below, today
> the diffstat is even "worse":
> 
> 	152 files changed, 611 insertions(+), 906 deletions(-)
> 
> and the patch size is 242k.
> 
> No? we can't?

Maybe this needs a phased approach:

1.	Add a new API name without the "pos" argument.

2.	Send individual patches to the uses, which allows time to
	clean up stragglers.

3.	Remove the old API name.  If any patches from #2 have been
	ignored, push them with the removal patch.

4.	Rename the new API name to the old one, if desired.

Yeah, cowardly of me, I know.

							Thanx, Paul

> -------------------------------------------------------------------------------
> [PATCH 0.01/1] hlist_for_each_entry_xxx: kill the "pos" argument
> 
> (The actual patch is huge, 116K, I'll send it offline. This email contains
>  the chunk for list.h only).
> 
> COMPILE TESTED ONLY (make allyesconfig).
> 
> All hlist_for_each_entry_xxx() macros require the "pos" argument, which is not
> actually needed and can be removed. See the changes in include/linux/list.h
> (note that hlist_for_each_entry_safe() now does prefetch() too).
> 
> Now we should convert the callers somehow. Unfortunately, this is not always
> easy. Consider this code for example:
> 
> 	{
> 		struct hlist_node *tmp1, *tmp2;
> 
> 		hlist_for_each_entry(pos, tmp1, head,mem)
> 			do_something(pos);
> 
> 		hlist_for_each_entry(pos, tmp2, head,mem)
> 			use(tmp2);
> 	}
> 
> The first hlist_for_each_entry is easy, but the second can't be converted
> automatically because "tmp2" is used.
> 
> So, this patch
> 
> 	- copies these macros to "obsolete" __hlist_for_each_entry_xxx()
> 
> 	- changes hlist_for_each_entry_xxxx() to avoid the "struct hlist_nod*"
> 
> 	- converts the rest of the kernel to use either new or old macros
> 
> For example, the patch for the code above is
> 
> 	 {
> 	-	struct hlist_node *tmp1, *tmp2;
> 	+	struct hlist_node *tmp2;
> 	 
> 	-	hlist_for_each_entry(pos, tmp1, head,mem)
> 	+	hlist_for_each_entry(pos, head,mem)
> 			do_something(pos);
> 	 
> 	-	hlist_for_each_entry(pos, tmp2, head,mem)
> 	+	__hlist_for_each_entry(pos, tmp2, head,mem)
> 			use(tmp2);
> 	 }
> 
> I believe it is very easy to convert the users of the obsolete macros, but
> this needs separate patches.
> 
> Except for changes in include/linux/list.h the patch was generated by this
> script:
> 
> 	#!/usr/bin/perl -w
> 	use strict;
> 
> 	my ($N_CNT, $O_CNT, @SRC, $CTXT, @CTXT);
> 
> 	sub say { printf STDERR "%4d: %s.\n", $., "@_" }
> 
> 	sub var { return $_->{$_[0]} || next for @CTXT }
> 
> 	sub parse_line
> 	{
> 		if (ord == ord '{') {
> 			unshift @CTXT, $CTXT = {
> 				-v_list => \@{$CTXT->{-v_list}},
> 				-v_rexp =>    $CTXT->{-v_rexp},
> 			};
> 		}
> 		elsif (ord == ord '}') {
> 			say "WARN! unmatched '}'" unless $CTXT;
> 
> 			while (my ($v, $c) = each %$CTXT) {
> 				my $trim = ord $v != ord '-' &&
> 					!$c->{used} && $c->{trim} || next;
> 
> 				for my $tr (@$trim) {
> 					substr($_, $tr->[1], 2, ''),
> 					substr($_, $tr->[2], $tr->[3], '')
> 						for $SRC[$tr->[0]];
> 					$N_CNT++;
> 				}
> 
> 				for ($SRC[$c->{decl}]) {
> 					s/\* \s* $v \b (?: \s* , \s*)?//x || die;
> 					s/,\s*(?=;)//; s/\bstruct\s+hlist_node\s*;//;
> 					$_ = '' if /^\s*\\?\s*$/;
> 				}
> 			}
> 			shift @CTXT; $CTXT = $CTXT[0];
> 		}
> 		elsif ($CTXT && /\b struct \s+ hlist_node \b ([^;]+)/x) {
> 			my $v_list = $CTXT->{-v_list};
> 			for (split /,/, $1) {
> 				/^\s* \* (\w+) \s* \z/x or next;
> 				$CTXT->{$1} = { decl => 0+@SRC };
> 				push @$v_list, $1;
> 			}
> 			$CTXT->{-v_rexp} = qr/\b(@{[join '|', @$v_list]})\b/
> 				if @$v_list;
> 		}
> 		elsif (/\b hlist_for_each_entry (?:_continue|_from|_safe|_rcu)? \b/xg) {
> 			my $u = length $`;
> 			if (/\G \s* \( .+? (, \s* (\w+) \s*)/x) {
> 				my $tr = [0+@SRC, $u, $-[1], length $1];
> 				if (my $v = var $2) { push @{$v->{trim}}, $tr; }
> 			} else {
> 				say "suspicious usage of hlist_for_each_entry_xxx()";
> 			}
> 			substr $_, $u, 0, '__';
> 			$O_CNT++;
> 		}
> 		elsif (my $re = $CTXT && $CTXT->{-v_rexp}) {
> 			var($1)->{used}++ while /$re/g;
> 		}
> 
> 		push @SRC, $_;
> 	}
> 
> 	sub diff_file
> 	{
> 		my $file = $_;
> 		warn "====> $file ...\n";
> 		($N_CNT, $O_CNT, @SRC, $CTXT, @CTXT) = 0;
> 
> 		open my $fd, '<', $file or die;
> 		while (<$fd>) {
> 			my $comm = s/(\/\*.*)//s && $1;
> 			parse_line for split /([{}])/, $_, -1;
> 			while ($comm) {
> 				push @SRC, $comm;
> 				$comm = $comm !~ /\*\// && <$fd>;
> 			}
> 		}
> 
> 		warn "WARN! unmatched '{'\n" if $CTXT;
> 		return warn "WARN! not changed\n" unless $O_CNT;
> 		warn "stat: $N_CNT from $O_CNT\n";
> 
> 		open my $diff, "|diff -up --label a/$file $file --label b/$file -";
> 		print $diff @SRC;
> 	}
> 
> 
> 	@ARGV || die "usage: $0 path_to_kernel || list_of_files\n";
> 
> 	if (-d $ARGV[0]) {
> 		chdir $ARGV[0] || die "ERR!! can't cd to $ARGV[0]\n";
> 		warn "grep ...\n";
> 		@ARGV = sort grep {
> 			chomp; s/^\.\///; $_ ne 'include/linux/list.h';
> 		} qx{grep --include='*.[ch]' -rle '\\bhlist_for_each_entry' .};
> 	}
> 
> 	diff_file for @ARGV;
> 
> (it open files readonly, so can be used safely)
> 
> Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> 
>  arch/arm/kernel/kprobes.c            |    6 +--
>  arch/ia64/kernel/kprobes.c           |    8 ++--
>  arch/powerpc/kernel/kprobes.c        |    6 +--
>  arch/s390/kernel/kprobes.c           |    6 +--
>  arch/sparc64/kernel/kprobes.c        |    6 +--
>  arch/sparc64/kernel/ldc.c            |    3 -
>  arch/x86/kernel/kprobes.c            |    6 +--
>  arch/x86/kvm/mmu.c                   |   20 ++++------
>  block/cfq-iosched.c                  |    3 -
>  block/elevator.c                     |    4 +-
>  crypto/algapi.c                      |    6 +--
>  drivers/infiniband/core/cma.c        |    3 -
>  drivers/infiniband/core/fmr_pool.c   |    3 -
>  drivers/md/raid5.c                   |    6 +--
>  drivers/net/macvlan.c                |    6 +--
>  drivers/net/pppol2tp.c               |    6 +--
>  drivers/net/sunvnet.c                |    3 -
>  drivers/net/wireless/zd1201.c        |    7 +--
>  fs/dcache.c                          |    3 -
>  fs/ecryptfs/messaging.c              |    5 +-
>  fs/fat/inode.c                       |    3 -
>  fs/gfs2/glock.c                      |    6 +--
>  fs/lockd/host.c                      |   17 +++------
>  fs/lockd/svcsubs.c                   |    7 +--
>  fs/nfsd/nfscache.c                   |    3 -
>  fs/ocfs2/dlm/dlmdebug.c              |    3 -
>  fs/ocfs2/dlm/dlmrecovery.c           |    6 +--
>  fs/xfs/xfs_inode.c                   |    3 -
>  include/linux/pci.h                  |    3 -
>  include/linux/pid.h                  |    3 -
>  include/net/ax25.h                   |    4 +-
>  include/net/inet_hashtables.h        |    2 -
>  include/net/inet_timewait_sock.h     |    6 +--
>  include/net/netrom.h                 |    8 ++--
>  include/net/sctp/sctp.h              |    2 -
>  include/net/sock.h                   |   10 ++---
>  kernel/kprobes.c                     |   36 ++++++++-----------
>  kernel/marker.c                      |   15 ++------
>  kernel/pid.c                         |    3 -
>  kernel/sched.c                       |    6 +--
>  kernel/user.c                        |    3 -
>  net/8021q/vlan.c                     |    3 -
>  net/9p/error.c                       |    2 -
>  net/atm/lec.c                        |   64 +++++++++++++++--------------------
>  net/ax25/ax25_iface.c                |    3 -
>  net/bridge/br_fdb.c                  |   17 +++------
>  net/can/af_can.c                     |   21 +++++------
>  net/can/proc.c                       |    6 +--
>  net/decnet/dn_table.c                |   13 ++-----
>  net/ipv4/fib_frontend.c              |   11 ++----
>  net/ipv4/fib_hash.c                  |   30 ++++++----------
>  net/ipv4/fib_semantics.c             |   23 ++++--------
>  net/ipv4/fib_trie.c                  |   25 ++++---------
>  net/ipv4/inet_fragment.c             |   10 ++---
>  net/ipv4/netfilter/nf_nat_core.c     |    3 -
>  net/ipv6/addrlabel.c                 |   14 +++----
>  net/ipv6/ip6_fib.c                   |    9 +---
>  net/ipv6/xfrm6_tunnel.c              |   12 ++----
>  net/netfilter/nf_conntrack_core.c    |   18 +++------
>  net/netfilter/nf_conntrack_expect.c  |   12 ++----
>  net/netfilter/nf_conntrack_helper.c  |   14 +++----
>  net/netfilter/nf_conntrack_netlink.c |   12 ++----
>  net/netfilter/nfnetlink_log.c        |    7 +--
>  net/netfilter/nfnetlink_queue.c      |   10 ++---
>  net/netfilter/xt_RATEEST.c           |    3 -
>  net/netfilter/xt_hashlimit.c         |   13 ++-----
>  net/sched/sch_htb.c                  |    9 +---
>  net/sunrpc/auth.c                    |    5 +-
>  net/sunrpc/svcauth.c                 |    3 -
>  net/tipc/name_table.c                |    8 +---
>  net/xfrm/xfrm_policy.c               |   53 ++++++++++++----------------
>  net/xfrm/xfrm_state.c                |   43 ++++++++---------------
>  72 files changed, 302 insertions(+), 439 deletions(-)
> 
> --- HL/include/linux/list.h~HLIST	2007-10-25 16:22:12.000000000 +0400
> +++ HL/include/linux/list.h	2008-04-21 17:17:44.000000000 +0400
> @@ -926,58 +926,54 @@ static inline void hlist_add_after_rcu(s
> 
>  /**
>   * hlist_for_each_entry	- iterate over list of given type
> - * @tpos:	the type * to use as a loop cursor.
> - * @pos:	the &struct hlist_node to use as a loop cursor.
> + * @pos:	the type * to use as a loop cursor.
>   * @head:	the head for your list.
>   * @member:	the name of the hlist_node within the struct.
>   */
> -#define hlist_for_each_entry(tpos, pos, head, member)			 \
> -	for (pos = (head)->first;					 \
> -	     pos && ({ prefetch(pos->next); 1;}) &&			 \
> -		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> -	     pos = pos->next)
> +#define hlist_for_each_entry(pos, head, member)				\
> +	for (pos = (void*)(head)->first; pos && ({			\
> +		prefetch(((struct hlist_node*)pos)->next);		\
> +		pos = hlist_entry((void*)pos, typeof(*pos), member); 1;	\
> +	     }); pos = (void*)(pos)->member.next)
> 
>  /**
>   * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
> - * @tpos:	the type * to use as a loop cursor.
> - * @pos:	the &struct hlist_node to use as a loop cursor.
> + * @pos:	the type * to use as a loop cursor.
>   * @member:	the name of the hlist_node within the struct.
>   */
> -#define hlist_for_each_entry_continue(tpos, pos, member)		 \
> -	for (pos = (pos)->next;						 \
> -	     pos && ({ prefetch(pos->next); 1;}) &&			 \
> -		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> -	     pos = pos->next)
> +#define hlist_for_each_entry_continue(pos, member)			\
> +	for (; (pos = (void*)(pos)->member.next) && ({			\
> +		prefetch(((struct hlist_node*)pos)->next);		\
> +		pos = hlist_entry((void*)pos, typeof(*pos), member); 1;	\
> +	     }); )
> 
>  /**
>   * hlist_for_each_entry_from - iterate over a hlist continuing from current point
> - * @tpos:	the type * to use as a loop cursor.
> - * @pos:	the &struct hlist_node to use as a loop cursor.
> + * @pos:	the type * to use as a loop cursor.
>   * @member:	the name of the hlist_node within the struct.
>   */
> -#define hlist_for_each_entry_from(tpos, pos, member)			 \
> -	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
> -		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> -	     pos = pos->next)
> +#define hlist_for_each_entry_from(pos, member)				\
> +	for (pos = pos ? (void*)&(pos)->member.next : pos; pos && ({	\
> +		prefetch(((struct hlist_node*)pos)->next);		\
> +		pos = hlist_entry((void*)pos, typeof(*pos), member); 1;	\
> +	     }); pos = (void*)(pos)->member.next)
> 
>  /**
>   * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
> - * @tpos:	the type * to use as a loop cursor.
> - * @pos:	the &struct hlist_node to use as a loop cursor.
> + * @pos:	the type * to use as a loop cursor.
>   * @n:		another &struct hlist_node to use as temporary storage
>   * @head:	the head for your list.
>   * @member:	the name of the hlist_node within the struct.
>   */
> -#define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
> -	for (pos = (head)->first;					 \
> -	     pos && ({ n = pos->next; 1; }) && 				 \
> -		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> -	     pos = n)
> +#define hlist_for_each_entry_safe(pos, n, head, member)			\
> +	for (pos = (void*)(head)->first; pos && ({			\
> +		n = ((struct hlist_node*)pos)->next; prefetch(n);	\
> +		pos = hlist_entry((void*)pos, typeof(*pos), member); 1;	\
> +	     }); pos = (void*)n)
> 
>  /**
>   * hlist_for_each_entry_rcu - iterate over rcu list of given type
> - * @tpos:	the type * to use as a loop cursor.
> - * @pos:	the &struct hlist_node to use as a loop cursor.
> + * @pos:	the type * to use as a loop cursor.
>   * @head:	the head for your list.
>   * @member:	the name of the hlist_node within the struct.
>   *
> @@ -985,7 +981,38 @@ static inline void hlist_add_after_rcu(s
>   * the _rcu list-mutation primitives such as hlist_add_head_rcu()
>   * as long as the traversal is guarded by rcu_read_lock().
>   */
> -#define hlist_for_each_entry_rcu(tpos, pos, head, member)		 \
> +#define hlist_for_each_entry_rcu(pos, head, member)			\
> +	for (pos = (void*)(head)->first; rcu_dereference(pos) && ({	\
> +		prefetch(((struct hlist_node*)pos)->next);		\
> +		pos = hlist_entry((void*)pos, typeof(*pos), member); 1;	\
> +	     }); pos = (void*)(pos)->member.next)
> +
> +/* -------- Obsolete, to be removed soon, do not use -------- */
> +
> +#define __hlist_for_each_entry(tpos, pos, head, member)			 \
> +	for (pos = (head)->first;					 \
> +	     pos && ({ prefetch(pos->next); 1;}) &&			 \
> +		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> +	     pos = pos->next)
> +
> +#define __hlist_for_each_entry_continue(tpos, pos, member)		 \
> +	for (pos = (pos)->next;						 \
> +	     pos && ({ prefetch(pos->next); 1;}) &&			 \
> +		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> +	     pos = pos->next)
> +
> +#define __hlist_for_each_entry_from(tpos, pos, member)			 \
> +	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
> +		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> +	     pos = pos->next)
> +
> +#define __hlist_for_each_entry_safe(tpos, pos, n, head, member) 	 \
> +	for (pos = (head)->first;					 \
> +	     pos && ({ n = pos->next; 1; }) && 				 \
> +		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> +	     pos = n)
> +
> +#define __hlist_for_each_entry_rcu(tpos, pos, head, member)		 \
>  	for (pos = (head)->first;					 \
>  	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	 \
>  		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>