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

[Daniel Thompson]

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