[PATCH] rculist: Add macro list_prev_rcu

[PATCH] rculist: Add macro list_prev_rcu

[madhuparnabhowmik04]

From: Madhuparna Bhowmik <madhuparnabhowmik04@gmail.com>

There are instances in the linux kernel where the prev pointer
of a list is accessed.
Unlike list_next_rcu, a similar macro for accessing the prev
pointer was not present.
Therefore, directly accessing the prev pointer was causing
sparse errors.
One such example is the sparse error in fs/nfs/dir.c

error:
fs/nfs/dir.c:2353:14: error: incompatible types in comparison expression (different address spaces):
fs/nfs/dir.c:2353:14:    struct list_head [noderef] <asn:4> *
fs/nfs/dir.c:2353:14:    struct list_head *

The error is caused due to the following line:

lh = rcu_dereference(nfsi->access_cache_entry_lru.prev);

After adding the macro, this error can be fixed as follows:

lh = rcu_dereference(list_prev_rcu(&nfsi->access_cache_entry_lru));

Therefore, we think there is a need to add this macro to rculist.h.

Suggested-by: Joel Fernandes (Google) <joel@joelfernandes.org>
Signed-off-by: Madhuparna Bhowmik <madhuparnabhowmik04@gmail.com>
---
 include/linux/rculist.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index 4b7ae1bf50b3..49eef8437753 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -40,6 +40,12 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
  */
 #define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
 
+/*
+ * return the prev pointer of a list_head in an rcu safe
+ * way, we must not access it directly
+ */
+#define list_prev_rcu(list)	(*((struct list_head __rcu **)(&(list)->prev)))
+
 /*
  * Check during list traversal that we are within an RCU reader
  */
-- 
2.17.1

Re: [PATCH] rculist: Add macro list_prev_rcu

[Paul E. McKenney]

On Fri, Dec 06, 2019 at 08:35:54PM +0530, madhuparnabhowmik04@gmail.com wrote:
> From: Madhuparna Bhowmik <madhuparnabhowmik04@gmail.com>
> 
> There are instances in the linux kernel where the prev pointer
> of a list is accessed.
> Unlike list_next_rcu, a similar macro for accessing the prev
> pointer was not present.

Interesting patch, but...

You lost me on this one.  The list_head ->prev pointer is not marked
__rcu, so why is sparse complaining?  Or is someone trying to use
rcu_dereference() or similar on ->prev?  If so, it is important to note
that both list_del() and list_del_rcu() poision ->prev, so it is not
usually safe to access ->prev within an RCU read-side critical section.
At the very least, this restriction needs to be called out in the
list_prev_rcu() comment header.  And that use of rcu_dereference() and
friends on the ->prev pointer is almost always the result of confusion,
if not a bug.  (Or is this some new-to-me use case?)

Either way, the big question is how we are sure that the uses of ->prev
that sparse is complaining about are in fact safe.  More specifically,
what have those use cases done to ensure that there will be no invocation
of either list_del() or list_del_rcu() on the current element just before
the use of ->prev?  Here are a couple of possibilities:

1.	The list only grows, so list_del() and list_del_rcu() are never
	ever invoked on it.

	But even this is not safe because __list_add_rcu() does
	smp_store_release() only on ->next.  The initialization of
	->prev is completely unordered with any other initialization,
	which can result in bugs on lookup/insertion concurrency.

	So this instead becomes the list being constant.

2.	The ->prev pointer is never actually dereferenced, but only
	compared.  One example use case is determining whether the
	current element is first in the list by comparing its
	->prev pointer to the address of the list header.

	But this use case needs a READ_ONCE().

3.	These accesses are single-threaded, for example while the list
	is being initialized but before it is exposed to readers or
	after the list has been rendered inaccessible to readers
	(and following at least one grace period after that).  But in
	this case, there is no need for rcu_dereference(), so sparse
	should not be complaining.

4.	#3 above, but code is shared with the non-single-threaded case.
	But then the non-single-threaded code needs to be safe with
	respect to concurrent insertions and deletions, as called
	out above.

So what am I missing here?

							Thanx, Paul

> Therefore, directly accessing the prev pointer was causing
> sparse errors.
> One such example is the sparse error in fs/nfs/dir.c
> 
> error:
> fs/nfs/dir.c:2353:14: error: incompatible types in comparison expression (different address spaces):
> fs/nfs/dir.c:2353:14:    struct list_head [noderef] <asn:4> *
> fs/nfs/dir.c:2353:14:    struct list_head *
> 
> The error is caused due to the following line:
> 
> lh = rcu_dereference(nfsi->access_cache_entry_lru.prev);
> 
> After adding the macro, this error can be fixed as follows:
> 
> lh = rcu_dereference(list_prev_rcu(&nfsi->access_cache_entry_lru));
> 
> Therefore, we think there is a need to add this macro to rculist.h.
> 
> Suggested-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> Signed-off-by: Madhuparna Bhowmik <madhuparnabhowmik04@gmail.com>
> ---
>  include/linux/rculist.h | 6 ++++++
>  1 file changed, 6 insertions(+)
> 
> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> index 4b7ae1bf50b3..49eef8437753 100644
> --- a/include/linux/rculist.h
> +++ b/include/linux/rculist.h
> @@ -40,6 +40,12 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
>   */
>  #define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
>  
> +/*
> + * return the prev pointer of a list_head in an rcu safe
> + * way, we must not access it directly
> + */
> +#define list_prev_rcu(list)	(*((struct list_head __rcu **)(&(list)->prev)))
> +
>  /*
>   * Check during list traversal that we are within an RCU reader
>   */
> -- 
> 2.17.1
> 

Re: [PATCH] rculist: Add macro list_prev_rcu

[Joel Fernandes]

On Fri, Dec 06, 2019 at 07:32:58AM -0800, Paul E. McKenney wrote:
> On Fri, Dec 06, 2019 at 08:35:54PM +0530, madhuparnabhowmik04@gmail.com wrote:
> > From: Madhuparna Bhowmik <madhuparnabhowmik04@gmail.com>
> > 
> > There are instances in the linux kernel where the prev pointer
> > of a list is accessed.
> > Unlike list_next_rcu, a similar macro for accessing the prev
> > pointer was not present.
> 
> Interesting patch, but...
> 
> You lost me on this one.  The list_head ->prev pointer is not marked
> __rcu, so why is sparse complaining?  Or is someone trying to use
> rcu_dereference() or similar on ->prev?  If so, it is important to note
> that both list_del() and list_del_rcu() poision ->prev, so it is not
> usually safe to access ->prev within an RCU read-side critical section.
> At the very least, this restriction needs to be called out in the
> list_prev_rcu() comment header.  And that use of rcu_dereference() and
> friends on the ->prev pointer is almost always the result of confusion,
> if not a bug.  (Or is this some new-to-me use case?)

Madhuparna, could you please send the patch using this as well, to prevent
confusion? You can see how just sending one patch and not the user of it
creates avoidable confusion. Thanks.

Thanks Paul for taking a look. If I remember the dependent patch uses
rcu_dereference() but I don't remember all the details at the top of my head.

thanks,

 - Joel


> 
> Either way, the big question is how we are sure that the uses of ->prev
> that sparse is complaining about are in fact safe.  More specifically,
> what have those use cases done to ensure that there will be no invocation
> of either list_del() or list_del_rcu() on the current element just before
> the use of ->prev?  Here are a couple of possibilities:
> 
> 1.	The list only grows, so list_del() and list_del_rcu() are never
> 	ever invoked on it.
> 
> 	But even this is not safe because __list_add_rcu() does
> 	smp_store_release() only on ->next.  The initialization of
> 	->prev is completely unordered with any other initialization,
> 	which can result in bugs on lookup/insertion concurrency.
> 
> 	So this instead becomes the list being constant.
> 
> 2.	The ->prev pointer is never actually dereferenced, but only
> 	compared.  One example use case is determining whether the
> 	current element is first in the list by comparing its
> 	->prev pointer to the address of the list header.
> 
> 	But this use case needs a READ_ONCE().
> 
> 3.	These accesses are single-threaded, for example while the list
> 	is being initialized but before it is exposed to readers or
> 	after the list has been rendered inaccessible to readers
> 	(and following at least one grace period after that).  But in
> 	this case, there is no need for rcu_dereference(), so sparse
> 	should not be complaining.
> 
> 4.	#3 above, but code is shared with the non-single-threaded case.
> 	But then the non-single-threaded code needs to be safe with
> 	respect to concurrent insertions and deletions, as called
> 	out above.
> 
> So what am I missing here?
> 
> 							Thanx, Paul
> 
> > Therefore, directly accessing the prev pointer was causing
> > sparse errors.
> > One such example is the sparse error in fs/nfs/dir.c
> > 
> > error:
> > fs/nfs/dir.c:2353:14: error: incompatible types in comparison expression (different address spaces):
> > fs/nfs/dir.c:2353:14:    struct list_head [noderef] <asn:4> *
> > fs/nfs/dir.c:2353:14:    struct list_head *
> > 
> > The error is caused due to the following line:
> > 
> > lh = rcu_dereference(nfsi->access_cache_entry_lru.prev);
> > 
> > After adding the macro, this error can be fixed as follows:
> > 
> > lh = rcu_dereference(list_prev_rcu(&nfsi->access_cache_entry_lru));
> > 
> > Therefore, we think there is a need to add this macro to rculist.h.
> > 
> > Suggested-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > Signed-off-by: Madhuparna Bhowmik <madhuparnabhowmik04@gmail.com>
> > ---
> >  include/linux/rculist.h | 6 ++++++
> >  1 file changed, 6 insertions(+)
> > 
> > diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> > index 4b7ae1bf50b3..49eef8437753 100644
> > --- a/include/linux/rculist.h
> > +++ b/include/linux/rculist.h
> > @@ -40,6 +40,12 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> >   */
> >  #define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
> >  
> > +/*
> > + * return the prev pointer of a list_head in an rcu safe
> > + * way, we must not access it directly
> > + */
> > +#define list_prev_rcu(list)	(*((struct list_head __rcu **)(&(list)->prev)))
> > +
> >  /*
> >   * Check during list traversal that we are within an RCU reader
> >   */
> > -- 
> > 2.17.1
> >