| Message ID | 20250216102356.18801-2-jgross@suse.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | xen/list: some fixes in list.h | expand |
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
On 16/02/2025 10:23 am, 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. > > Avoid that by testing for the end of the list before advancing the > iterator. In case of having reached the end of the list, set the > iterator to NULL and use that for stopping the loop. This has the > additional advantage of not leaking the iterator pointing to something > which isn't a list element past the loop. > > Reported-by: Andrew Cooper <andrew.cooper3@citrix.com> > Signed-off-by: Juergen Gross <jgross@suse.com> I have to admit that my gut feeling is that this is vastly overcomplicated. It also further diverges from Linux. I couldn't find an obvious example of this kind of UBSAN failure in Linux which suggests to me that one of the differences might be relevant. I did start experimenting in this direction, but haven't finished. ~Andrew
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
On 17.02.2025 12:16, Juergen Gross wrote: > On 17.02.25 10:47, Jan Beulich wrote: >> On 16.02.2025 11:23, Juergen Gross wrote: >>> @@ -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? I'd prefer the former, but I probably wouldn't mind the latter. >>> @@ -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? Reading Linux'es rcu_dereference.rst, my understanding is that one of them would suffice if then we used its result rather than the original pointer. Then again RCU has been somewhat opaque to me for all the years ... > Otherwise today's implementation would suffer from the same problem IMHO. That's the impression I'm (now) having. Jan
On 17.02.25 12:39, Jan Beulich wrote: > On 17.02.2025 12:16, Juergen Gross wrote: >> On 17.02.25 10:47, Jan Beulich wrote: >>> On 16.02.2025 11:23, Juergen Gross wrote: >>>> @@ -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? > > I'd prefer the former, but I probably wouldn't mind the latter. > >>>> @@ -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? > > Reading Linux'es rcu_dereference.rst, my understanding is that one of them > would suffice if then we used its result rather than the original pointer. > Then again RCU has been somewhat opaque to me for all the years ... > >> Otherwise today's implementation would suffer from the same problem IMHO. > > That's the impression I'm (now) having. The rcu_dereference() is basically just for documentation purposes. If needed by an arch, it can add barriers, too, but according to the comments those would be needed on alpha only. The returned value is always the original pointer value. See the comment block in xen/include/xen/rcupdate.h Juergen
On 17.02.2025 12:58, Jürgen Groß wrote: > On 17.02.25 12:39, Jan Beulich wrote: >> On 17.02.2025 12:16, Juergen Gross wrote: >>> On 17.02.25 10:47, Jan Beulich wrote: >>>> On 16.02.2025 11:23, Juergen Gross wrote: >>>>> @@ -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? >> >> I'd prefer the former, but I probably wouldn't mind the latter. >> >>>>> @@ -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? >> >> Reading Linux'es rcu_dereference.rst, my understanding is that one of them >> would suffice if then we used its result rather than the original pointer. >> Then again RCU has been somewhat opaque to me for all the years ... >> >>> Otherwise today's implementation would suffer from the same problem IMHO. >> >> That's the impression I'm (now) having. > > The rcu_dereference() is basically just for documentation purposes. If needed > by an arch, it can add barriers, too, but according to the comments those would > be needed on alpha only. The returned value is always the original pointer > value. See the comment block in xen/include/xen/rcupdate.h Note the "This pointer may later be safely dereferenced" in there. As said, we'd be fine if we used the return value instead of the original "pos". Yet we don't. We effectively assume that the macro expands to just the passed in pointer, with no barriers or anything else. Anyway, since - as you validly say - this is a pre-existing issue, let's put it on the side right here. Jan
On 17.02.25 13:16, Jan Beulich wrote: > On 17.02.2025 12:58, Jürgen Groß wrote: >> On 17.02.25 12:39, Jan Beulich wrote: >>> On 17.02.2025 12:16, Juergen Gross wrote: >>>> On 17.02.25 10:47, Jan Beulich wrote: >>>>> On 16.02.2025 11:23, Juergen Gross wrote: >>>>>> @@ -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? >>> >>> I'd prefer the former, but I probably wouldn't mind the latter. >>> >>>>>> @@ -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? >>> >>> Reading Linux'es rcu_dereference.rst, my understanding is that one of them >>> would suffice if then we used its result rather than the original pointer. >>> Then again RCU has been somewhat opaque to me for all the years ... >>> >>>> Otherwise today's implementation would suffer from the same problem IMHO. >>> >>> That's the impression I'm (now) having. >> >> The rcu_dereference() is basically just for documentation purposes. If needed >> by an arch, it can add barriers, too, but according to the comments those would >> be needed on alpha only. The returned value is always the original pointer >> value. See the comment block in xen/include/xen/rcupdate.h > > Note the "This pointer may later be safely dereferenced" in there. As said, > we'd be fine if we used the return value instead of the original "pos". Yet > we don't. We effectively assume that the macro expands to just the passed > in pointer, with no barriers or anything else. > > Anyway, since - as you validly say - this is a pre-existing issue, let's put > it on the side right here. I'll setup a patch for 4.21 fixing all the rcu list iterators. Juergen
diff --git a/xen/include/xen/list.h b/xen/include/xen/list.h index 62169f4674..e6ece77225 100644 --- 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, + const struct list_head *head) +{ + return list->prev == head; +} + /** * list_is_last - tests whether @list is the last entry in list @head * @list: the entry to test @@ -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. + * + * Note that if the end of the list is reached, it returns NULL. + */ +#define list_next_entry_or_null(head, pos, member) \ + list_is_last(&(pos)->member, head) \ + ? NULL \ + : list_entry((pos)->member.next, typeof(*(pos)), member) + /** * list_prev_entry - get the prev element in list * @pos: the type * to cursor @@ -449,6 +472,18 @@ static inline void list_splice_init(struct list_head *list, #define list_prev_entry(pos, member) \ list_entry((pos)->member.prev, typeof(*(pos)), member) +/** + * list_prev_entry_or_null - get the prev element in list + * @pos: the type * to cursor + * @member: the name of the struct list_head within the struct. + * + * Note that if the start of the list is reached, it returns NULL. + */ +#define list_prev_entry_or_null(head, pos, member) \ + list_is_first(&(pos)->member, head) \ + ? NULL \ + : list_entry((pos)->member.prev, typeof(*(pos)), member) + /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. @@ -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; \ + (pos) = list_next_entry_or_null(head, pos, member) ) /** * list_for_each_entry_reverse - iterate backwards over list of given type. @@ -503,10 +538,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_reverse(pos, head, member) \ - for ((pos) = list_entry((head)->prev, typeof(*(pos)), member); \ - &(pos)->member != (head); \ - (pos) = list_entry((pos)->member.prev, typeof(*(pos)), member)) +#define list_for_each_entry_reverse(pos, head, member) \ + for ( (pos) = list_last_entry_or_null(head, typeof(*(pos)), member); \ + pos; \ + (pos) = list_prev_entry_or_null(head, pos, member) ) /** * list_prepare_entry - prepare a pos entry for use in @@ -530,10 +565,10 @@ static inline void list_splice_init(struct list_head *list, * Continue to iterate over list of given type, continuing after * the current position. */ -#define list_for_each_entry_continue(pos, head, member) \ - for ((pos) = list_entry((pos)->member.next, typeof(*(pos)), member); \ - &(pos)->member != (head); \ - (pos) = list_entry((pos)->member.next, typeof(*(pos)), member)) +#define list_for_each_entry_continue(pos, head, member) \ + for ( (pos) = list_next_entry_or_null(head, pos, member); \ + pos; \ + (pos) = list_next_entry_or_null(head, pos, member) ) /** * list_for_each_entry_from - iterate over list of given type from the @@ -544,9 +579,8 @@ static inline void list_splice_init(struct list_head *list, * * Iterate over list of given type, continuing from current position. */ -#define list_for_each_entry_from(pos, head, member) \ - for (; &(pos)->member != (head); \ - (pos) = list_entry((pos)->member.next, typeof(*(pos)), member)) +#define list_for_each_entry_from(pos, head, member) \ + for ( ; pos; (pos) = list_next_entry_or_null(head, pos, member) ) /** * list_for_each_entry_safe - iterate over list of given type safe @@ -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; \ + pos; \ + (pos) = (n), (n) = list_next_entry_or_null(head, n, member) ) /** * list_for_each_entry_safe_continue @@ -572,11 +606,11 @@ static inline void list_splice_init(struct list_head *list, * Iterate over list of given type, continuing after current point, * safe against removal of list entry. */ -#define list_for_each_entry_safe_continue(pos, n, head, member) \ - for ((pos) = list_entry((pos)->member.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_continue(pos, n, head, member) \ + for ( (pos) = list_next_entry_or_null(head, pos, member), \ + (n) = (pos) ? list_next_entry_or_null(head, pos, member) : NULL; \ + pos; \ + (pos) = (n), (n) = list_next_entry_or_null(head, n, member) ) /** * list_for_each_entry_safe_from @@ -589,9 +623,9 @@ static inline void list_splice_init(struct list_head *list, * removal of list entry. */ #define list_for_each_entry_safe_from(pos, n, head, member) \ - for ((n) = list_entry((pos)->member.next, typeof(*(pos)), member); \ - &(pos)->member != (head); \ - (pos) = (n), (n) = list_entry((n)->member.next, typeof(*(n)), member)) + for ( (n) = list_next_entry_or_null(head, pos, member); \ + pos; \ + (pos) = (n), (n) = list_next_entry_or_null(head, n, member) ) /** * list_for_each_entry_safe_reverse @@ -603,11 +637,11 @@ static inline void list_splice_init(struct list_head *list, * Iterate backwards over list of given type, safe against removal * of list entry. */ -#define list_for_each_entry_safe_reverse(pos, n, head, member) \ - for ((pos) = list_entry((head)->prev, typeof(*(pos)), member), \ - (n) = list_entry((pos)->member.prev, typeof(*(pos)), member); \ - &(pos)->member != (head); \ - (pos) = (n), (n) = list_entry((n)->member.prev, typeof(*(n)), member)) +#define list_for_each_entry_safe_reverse(pos, n, head, member) \ + for ( (pos) = list_last_entry_or_null(head, typeof(*(pos)), member), \ + (n) = (pos) ? list_prev_entry_or_null(head, pos, member) : NULL; \ + pos; \ + (pos) = (n), (n) = list_prev_entry_or_null(head, n, member) ) /** * list_for_each_rcu - iterate over an rcu-protected list @@ -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) ) /** * list_for_each_continue_rcu
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. Avoid that by testing for the end of the list before advancing the iterator. In case of having reached the end of the list, set the iterator to NULL and use that for stopping the loop. This has the additional advantage of not leaking the iterator pointing to something which isn't a list element past the loop. Reported-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Juergen Gross <jgross@suse.com> --- No proper Fixes: tag, as this bug predates Xen's git and mercurial history. --- xen/include/xen/list.h | 110 +++++++++++++++++++++++++++-------------- 1 file changed, 72 insertions(+), 38 deletions(-)