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

[Jan Beulich <jbeulich@xxxxxxxx>]

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/

> --- 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?

> +                                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.)

> @@ -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"

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

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

> @@ -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?

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?

Jan