Re: [PATCH 1/2] xen/list: avoid UB in list iterators

[Juergen Gross <jgross@xxxxxxxx>]

On 17.02.25 10:47, Jan Beulich wrote:
> On 16.02.2025 11:23, Juergen Gross wrote:
> > The list_for_each_entry*() iterators are testing for having reached the
> > end of the list in a way which relies on undefined behavior: the
> > iterator (being a pointer to the struct of a list element) is advanced
> > and only then tested to have reached not the next element, but the list
> > head. This results in the list head being addressed via a list element
> > pointer, which is undefined, in case the list elements have a higher
> > alignment then the list head.
> Nit: s/then/than/
Oh, of course.

> > --- a/xen/include/xen/list.h
> > +++ b/xen/include/xen/list.h
> > @@ -291,6 +291,17 @@ static inline void list_move_tail(struct list_head *list,
> >       list_add_tail(list, head);
> >   }
> >   
> > +/**
> > + * list_is_first - tests whether @list is the first entry in list @head
> > + * @list: the entry to test
> > + * @head: the head of the list
> > + */
> > +static inline int list_is_first(const struct list_head *list,
> bool?
Fine with me, guessing that you'd accept the deviation from list_is_last().

> > +                                const struct list_head *head)
> > +{
> > +    return list->prev == head;
> > +}
> "list" is ambiguous, as it could also mean the start of the list. Maybe
> better "entry"? (I understand that'll be inconsistent with the subsequent
> list_is_last(), but what do you do.)
Okay.

> > @@ -440,7 +451,19 @@ static inline void list_splice_init(struct list_head *list,
> >     */
> >   #define list_next_entry(pos, member) \
> >           list_entry((pos)->member.next, typeof(*(pos)), member)
> > -
> > +
> > +/**
> > +  * list_next_entry_or_null - get the next element in list
> > +  * @pos:        the type * to cursor
> > +  * @member:     the name of the struct list_head  within the struct.
> Nit: Stray 2nd blank before "within"
Thanks for noticing.

> > @@ -492,10 +527,10 @@ static inline void list_splice_init(struct list_head 
> > *list,
> >    * @head:   the head for your list.
> >    * @member: the name of the list_struct within the struct.
> >    */
> > -#define list_for_each_entry(pos, head, member)                          \
> > -    for ((pos) = list_entry((head)->next, typeof(*(pos)), member);      \
> > -         &(pos)->member != (head);                                      \
> > -         (pos) = list_entry((pos)->member.next, typeof(*(pos)), member))
> > +#define list_for_each_entry(pos, head, member)                            \
> > +    for ( (pos) = list_first_entry_or_null(head, typeof(*(pos)), member); \
> > +          pos;                                                            \
> I suspect Misra would demand pos to be parenthesized here (and in similar
> places elsewhere), too.
I don't mind.

> > @@ -556,11 +590,11 @@ static inline void list_splice_init(struct list_head 
> > *list,
> >    * @head:   the head for your list.
> >    * @member: the name of the list_struct within the struct.
> >    */
> > -#define list_for_each_entry_safe(pos, n, head, member)                  \
> > -    for ((pos) = list_entry((head)->next, typeof(*(pos)), member),      \
> > -         (n) = list_entry((pos)->member.next, typeof(*(pos)), member);  \
> > -         &(pos)->member != (head);                                      \
> > -         (pos) = (n), (n) = list_entry((n)->member.next, typeof(*(n)), member))
> > +#define list_for_each_entry_safe(pos, n, head, member)                     \
> > +    for ( (pos) = list_first_entry_or_null(head, typeof(*(pos)), member),  \
> > +          (n) = (pos) ? list_next_entry_or_null(head, pos, member) : NULL; \
> n can end up being NULL here even if pos isn't. Then ...
>
> > +          pos;                                                             \
> > +          (pos) = (n), (n) = list_next_entry_or_null(head, n, member) )
> ... you can't use list_next_entry_or_null() on it.
Ah, indeed.

What would you prefer? Handling that in the *_safe() iterator macros, or
allowing the *_entry_or_null() macros to be called with a NULL parameter?

> > @@ -655,10 +689,10 @@ static inline void list_splice_init(struct list_head 
> > *list,
> >    * the _rcu list-mutation primitives such as list_add_rcu()
> >    * as long as the traversal is guarded by rcu_read_lock().
> >    */
> > -#define list_for_each_entry_rcu(pos, head, member)                      \
> > -    for ((pos) = list_entry((head)->next, typeof(*(pos)), member);      \
> > -         &rcu_dereference(pos)->member != (head);                       \
> > -         (pos) = list_entry((pos)->member.next, typeof(*(pos)), member))
> > +#define list_for_each_entry_rcu(pos, head, member)                        \
> > +    for ( (pos) = list_first_entry_or_null(head, typeof(*(pos)), member); \
> > +          rcu_dereference(pos);                                           \
> > +          (pos) = list_next_entry_or_null(head, pos, member) )
> Don't you need a list_next_entry_or_null_rcu() flavor here, using
> rcu_dereference() on the passed in pos for the (pos)->member.next deref?
Isn't the "rcu_dereference(pos);" all what is needed for the current iteration?
Otherwise today's implementation would suffer from the same problem IMHO.

> Question on the patch as a whole: Since I have a vague recollection that we
> may have a use or two of one of these iterator macros which actually make
> assumptions on the state of pos upon loop exit, did you audit all use sites?
No, I didn't. I'm doing it right now.

Found 1 case up to now.


Juergen

Attachment: OpenPGP_0xB0DE9DD628BF132F.asc
Description: OpenPGP public key

Attachment: OpenPGP_signature.asc
Description: OpenPGP digital signature