Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Cc: Andrew Morton akpm@linux-foundation.org Cc: "Paul E. McKenney" paulmck@kernel.org Cc: Randy Dunlap rdunlap@infradead.org Cc: stable@vger.kernel.org --- include/linux/list.h | 50 +++++++++++++++++++++++++++++++------------- 1 file changed, 36 insertions(+), 14 deletions(-)
diff --git a/include/linux/list.h b/include/linux/list.h index 884216db3246..c4d215d02259 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -536,6 +536,17 @@ static inline void list_splice_tail_init(struct list_head *list, #define list_next_entry(pos, member) \ list_entry((pos)->member.next, typeof(*(pos)), member)
+/** + * list_next_entry_safe - get the next element in list [once] + * @pos: the type * to cursor + * @member: the name of the list_head within the struct. + * + * Like list_next_entry() but prevents the compiler from reloading the + * next element. + */ +#define list_next_entry_safe(pos, member) \ + list_entry(READ_ONCE((pos)->member.next), typeof(*(pos)), member) + /** * list_prev_entry - get the prev element in list * @pos: the type * to cursor @@ -544,6 +555,17 @@ static inline void list_splice_tail_init(struct list_head *list, #define list_prev_entry(pos, member) \ list_entry((pos)->member.prev, typeof(*(pos)), member)
+/** + * list_prev_entry_safe - get the prev element in list [once] + * @pos: the type * to cursor + * @member: the name of the list_head within the struct. + * + * Like list_prev_entry() but prevents the compiler from reloading the + * previous element. + */ +#define list_prev_entry_safe(pos, member) \ + list_entry(READ_ONCE((pos)->member.prev), typeof(*(pos)), member) + /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. @@ -686,9 +708,9 @@ static inline void list_splice_tail_init(struct list_head *list, */ #define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member), \ - n = list_next_entry(pos, member); \ + n = list_next_entry_safe(pos, member); \ &pos->member != (head); \ - pos = n, n = list_next_entry(n, member)) + pos = n, n = list_next_entry_safe(n, member))
/** * list_for_each_entry_safe_continue - continue list iteration safe against removal @@ -700,11 +722,11 @@ static inline void list_splice_tail_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_next_entry(pos, member), \ - n = list_next_entry(pos, member); \ - &pos->member != (head); \ - pos = n, n = list_next_entry(n, member)) +#define list_for_each_entry_safe_continue(pos, n, head, member) \ + for (pos = list_next_entry(pos, member), \ + n = list_next_entry_safe(pos, member); \ + &pos->member != (head); \ + pos = n, n = list_next_entry_safe(n, member))
/** * list_for_each_entry_safe_from - iterate over list from current point safe against removal @@ -716,10 +738,10 @@ static inline void list_splice_tail_init(struct list_head *list, * Iterate over list of given type from current point, safe against * removal of list entry. */ -#define list_for_each_entry_safe_from(pos, n, head, member) \ - for (n = list_next_entry(pos, member); \ - &pos->member != (head); \ - pos = n, n = list_next_entry(n, member)) +#define list_for_each_entry_safe_from(pos, n, head, member) \ + for (n = list_next_entry_safe(pos, member); \ + &pos->member != (head); \ + pos = n, n = list_next_entry_safe(n, member))
/** * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal @@ -733,9 +755,9 @@ static inline void list_splice_tail_init(struct list_head *list, */ #define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member), \ - n = list_prev_entry(pos, member); \ + n = list_prev_entry_safe(pos, member); \ &pos->member != (head); \ - pos = n, n = list_prev_entry(n, member)) + pos = n, n = list_prev_entry_safe(n, member))
/** * list_safe_reset_next - reset a stale list_for_each_entry_safe loop @@ -750,7 +772,7 @@ static inline void list_splice_tail_init(struct list_head *list, * completing the current iteration of the loop body. */ #define list_safe_reset_next(pos, n, member) \ - n = list_next_entry(pos, member) + n = list_next_entry_safe(pos, member)
/* * Double linked lists with a single pointer list head.
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
David
- Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Quoting David Laight (2020-03-10 11:36:41)
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
The warning kcsan gave made sense (a strange case where the emptying the list from inside the safe iterator would allow that list to be taken under a global mutex and have one extra request added to it. The list_for_each_entry_safe() should be ok in this scenario, so long as the next element is read before this element is dropped, and the compiler is instructed not to reload the element. kcsan is a little more insistent on having that annotation :)
In this instance I would say it was a false positive from kcsan, but I can see why it would complain and suspect that given a sufficiently aggressive compiler, we may be caught out by a late reload of the next element.
That's my conjecture, but I leave it to the lkmm experts to decide :) -Chris
From: Chris Wilson
Sent: 10 March 2020 11:50
Quoting David Laight (2020-03-10 11:36:41)
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
The warning kcsan gave made sense (a strange case where the emptying the list from inside the safe iterator would allow that list to be taken under a global mutex and have one extra request added to it. The list_for_each_entry_safe() should be ok in this scenario, so long as the next element is read before this element is dropped, and the compiler is instructed not to reload the element.
Normally the loop iteration code has to hold the mutex. I guess it can be released inside the loop provided no other code can ever delete entries.
kcsan is a little more insistent on having that annotation :)
In this instance I would say it was a false positive from kcsan, but I can see why it would complain and suspect that given a sufficiently aggressive compiler, we may be caught out by a late reload of the next element.
If you have: for (; p; p = next) { next = p->next; external_function_call(void); } the compiler must assume that the function call can change 'p->next' and read it before the call.
Is this a list with strange locking rules? The only deletes are from within the loop. Adds and deletes are locked. The list traversal isn't locked.
I suspect kcsan bleats because it doesn't assume the compiler will use a single instruction/memory operation to read p->next. That is just stupid.
David
- Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Quoting David Laight (2020-03-10 12:23:34)
From: Chris Wilson
Sent: 10 March 2020 11:50
Quoting David Laight (2020-03-10 11:36:41)
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
The warning kcsan gave made sense (a strange case where the emptying the list from inside the safe iterator would allow that list to be taken under a global mutex and have one extra request added to it. The list_for_each_entry_safe() should be ok in this scenario, so long as the next element is read before this element is dropped, and the compiler is instructed not to reload the element.
Normally the loop iteration code has to hold the mutex. I guess it can be released inside the loop provided no other code can ever delete entries.
kcsan is a little more insistent on having that annotation :)
In this instance I would say it was a false positive from kcsan, but I can see why it would complain and suspect that given a sufficiently aggressive compiler, we may be caught out by a late reload of the next element.
If you have: for (; p; p = next) { next = p->next; external_function_call(void); } the compiler must assume that the function call can change 'p->next' and read it before the call.
Is this a list with strange locking rules?
Yes.
The only deletes are from within the loop.
All deletes are within the mutex.
Adds and deletes are locked.
There's just one special case where after the very last element of all lists for an engine is removed, a global mutex is taken and one new element is added to one of the lists to track powering off the engine.
The list traversal isn't locked.
There's rcu traversal of the list as well.
I suspect kcsan bleats because it doesn't assume the compiler will use a single instruction/memory operation to read p->next. That is just stupid.
kcsan is looking for a write to a pointer after a read that is not in the same locking chain. While I have satisfied lockdep that I am not insane, I'm worrying in case kcsan has a valid objection to the potential data race in the safe list iterator. -Chris
On Tue, Mar 10, 2020 at 12:23:34PM +0000, David Laight wrote:
From: Chris Wilson
Sent: 10 March 2020 11:50
Quoting David Laight (2020-03-10 11:36:41)
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
Adding Marco on CC for his thoughts.
The warning kcsan gave made sense (a strange case where the emptying the list from inside the safe iterator would allow that list to be taken under a global mutex and have one extra request added to it. The list_for_each_entry_safe() should be ok in this scenario, so long as the next element is read before this element is dropped, and the compiler is instructed not to reload the element.
Normally the loop iteration code has to hold the mutex. I guess it can be released inside the loop provided no other code can ever delete entries.
kcsan is a little more insistent on having that annotation :)
In this instance I would say it was a false positive from kcsan, but I can see why it would complain and suspect that given a sufficiently aggressive compiler, we may be caught out by a late reload of the next element.
If you have: for (; p; p = next) { next = p->next; external_function_call(void); } the compiler must assume that the function call can change 'p->next' and read it before the call.
That "must assume" is a statement of current compiler technology. Given the progress over the past forty years, I would not expect this restriction to hold forever. Yes, we can and probably will get the compiler implementers to give us command-line flags to suppress global analysis. But given the progress in compilers that I have seen over the past 4+ decades, I would expect that the day will come when we won't want to be using those command-line flags.
But if you want to ignore KCSAN's warnings, you are free to do so.
Is this a list with strange locking rules? The only deletes are from within the loop. Adds and deletes are locked. The list traversal isn't locked.
I suspect kcsan bleats because it doesn't assume the compiler will use a single instruction/memory operation to read p->next. That is just stupid.
Heh! If I am still around, I will ask you for your evaluation of the above statement in 40 years. Actually, 10 years will likely suffice. ;-)
Thanx, Paul
On Tue, Mar 10, 2020 at 05:50:31AM -0700, Paul E. McKenney wrote:
On Tue, Mar 10, 2020 at 12:23:34PM +0000, David Laight wrote:
From: Chris Wilson
Sent: 10 March 2020 11:50
Quoting David Laight (2020-03-10 11:36:41)
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
Adding Marco on CC for his thoughts.
The warning kcsan gave made sense (a strange case where the emptying the list from inside the safe iterator would allow that list to be taken under a global mutex and have one extra request added to it. The list_for_each_entry_safe() should be ok in this scenario, so long as the next element is read before this element is dropped, and the compiler is instructed not to reload the element.
Normally the loop iteration code has to hold the mutex. I guess it can be released inside the loop provided no other code can ever delete entries.
kcsan is a little more insistent on having that annotation :)
In this instance I would say it was a false positive from kcsan, but I can see why it would complain and suspect that given a sufficiently aggressive compiler, we may be caught out by a late reload of the next element.
If you have: for (; p; p = next) { next = p->next; external_function_call(void); } the compiler must assume that the function call can change 'p->next' and read it before the call.
That "must assume" is a statement of current compiler technology. Given the progress over the past forty years, I would not expect this restriction to hold forever.
FWIW, this is exactly the sort of assumption that link time optimization is likely to render invalid going forward, and LTO is starting to be used today (e.g. to enable SW CFI stuff with clang).
Given that, I don't think that core kernel primitives can rely on this assumption.
Thanks, Mark.
On Tue, 10 Mar 2020 at 13:50, Paul E. McKenney paulmck@kernel.org wrote:
On Tue, Mar 10, 2020 at 12:23:34PM +0000, David Laight wrote:
From: Chris Wilson
Sent: 10 March 2020 11:50
Quoting David Laight (2020-03-10 11:36:41)
From: Chris Wilson
Sent: 10 March 2020 09:21 Instruct the compiler to read the next element in the list iteration once, and that it is not allowed to reload the value from the stale element later. This is important as during the course of the safe iteration, the stale element may be poisoned (unbeknownst to the compiler).
Eh? I thought any function call will stop the compiler being allowed to reload the value. The 'safe' loop iterators are only 'safe' against called code removing the current item from the list.
This helps prevent kcsan warnings over 'unsafe' conduct in releasing the list elements during list_for_each_entry_safe() and friends.
Sounds like kcsan is buggy ????
Adding Marco on CC for his thoughts.
I'd have to see a stack-trace with line-numbers.
But keep in mind what KCSAN does, which is report "data races". If the KCSAN report showed 2 accesses, where one of them was a *plain* read (and the other a write), then it's a valid data race (per LKMM's definition). It seems this was the case here.
As mentioned, the compiler is free to transform plain accesses in various concurrency-unfriendly ways.
FWIW, for writes we're already being quite generous, in that plain aligned writes up to word-size are assumed to be "atomic" with the default (conservative) config, i.e. marking such writes is optional. Although, that's a generous assumption that is not always guaranteed to hold (https://lore.kernel.org/lkml/20190821103200.kpufwtviqhpbuv2n@willie-the-truc...).
If there is code for which you prefer not to see KCSAN reports at all, you are free to disable them with KCSAN_SANITIZE_file.o := n
Thanks, -- Marco
The warning kcsan gave made sense (a strange case where the emptying the list from inside the safe iterator would allow that list to be taken under a global mutex and have one extra request added to it. The list_for_each_entry_safe() should be ok in this scenario, so long as the next element is read before this element is dropped, and the compiler is instructed not to reload the element.
Normally the loop iteration code has to hold the mutex. I guess it can be released inside the loop provided no other code can ever delete entries.
kcsan is a little more insistent on having that annotation :)
In this instance I would say it was a false positive from kcsan, but I can see why it would complain and suspect that given a sufficiently aggressive compiler, we may be caught out by a late reload of the next element.
If you have: for (; p; p = next) { next = p->next; external_function_call(void); } the compiler must assume that the function call can change 'p->next' and read it before the call.
That "must assume" is a statement of current compiler technology. Given the progress over the past forty years, I would not expect this restriction to hold forever. Yes, we can and probably will get the compiler implementers to give us command-line flags to suppress global analysis. But given the progress in compilers that I have seen over the past 4+ decades, I would expect that the day will come when we won't want to be using those command-line flags.
But if you want to ignore KCSAN's warnings, you are free to do so.
Is this a list with strange locking rules? The only deletes are from within the loop. Adds and deletes are locked. The list traversal isn't locked.
I suspect kcsan bleats because it doesn't assume the compiler will use a single instruction/memory operation to read p->next. That is just stupid.
Heh! If I am still around, I will ask you for your evaluation of the above statement in 40 years. Actually, 10 years will likely suffice. ;-)
Thanx, Paul
From: Marco Elver
Sent: 10 March 2020 14:10
...
FWIW, for writes we're already being quite generous, in that plain aligned writes up to word-size are assumed to be "atomic" with the default (conservative) config, i.e. marking such writes is optional. Although, that's a generous assumption that is not always guaranteed to hold (https://lore.kernel.org/lkml/20190821103200.kpufwtviqhpbuv2n@willie-the-truc...).
Remind me to start writing everything in assembler.
That and to mark all structure members 'volatile'.
David
- Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
On Tue, Mar 10, 2020 at 03:05:57PM +0000, David Laight wrote:
From: Marco Elver
Sent: 10 March 2020 14:10
...
FWIW, for writes we're already being quite generous, in that plain aligned writes up to word-size are assumed to be "atomic" with the default (conservative) config, i.e. marking such writes is optional. Although, that's a generous assumption that is not always guaranteed to hold (https://lore.kernel.org/lkml/20190821103200.kpufwtviqhpbuv2n@willie-the-truc...).
Remind me to start writing everything in assembler.
Been there, done that. :-/
That and to mark all structure members 'volatile'.
Indeed. READ_ONCE() and WRITE_ONCE() get this same effect, but without pessimizing non-concurrent accesses to those same members. Plus KCSAN knows about READ_ONCE(), WRITE_ONCE(), and also volatile members.
Thanx, Paul
On Tue, 10 Mar 2020 08:47:49 -0700 "Paul E. McKenney" paulmck@kernel.org wrote:
On Tue, Mar 10, 2020 at 03:05:57PM +0000, David Laight wrote:
From: Marco Elver
Sent: 10 March 2020 14:10
...
FWIW, for writes we're already being quite generous, in that plain aligned writes up to word-size are assumed to be "atomic" with the default (conservative) config, i.e. marking such writes is optional. Although, that's a generous assumption that is not always guaranteed to hold (https://lore.kernel.org/lkml/20190821103200.kpufwtviqhpbuv2n@willie-the-truc...).
Remind me to start writing everything in assembler.
Been there, done that. :-/
That and to mark all structure members 'volatile'.
Indeed. READ_ONCE() and WRITE_ONCE() get this same effect, but without pessimizing non-concurrent accesses to those same members. Plus KCSAN knows about READ_ONCE(), WRITE_ONCE(), and also volatile members.
So I take it from all the above that we should do this.
Did anyone actually review the code? :)
linux-stable-mirror@lists.linaro.org
-
Andrew Morton -
Chris Wilson -
David Laight -
Marco Elver -
Mark Rutland -
Paul E. McKenney