[1/3] list_bl: Add hlist_bl_add_before/behind helpers

Commit Message

Nikos Tsironis Dec. 20, 2018, 6:06 p.m. UTC

Add hlist_bl_add_before/behind helpers to add an element before/after an
existing element in a bl_list.

Signed-off-by: Nikos Tsironis <[e-mail]>
Signed-off-by: Ilias Tsitsimpis <[e-mail]>
---
 include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

Comments

Mike Snitzer Feb. 28, 2019, 9:32 p.m. UTC | #1

On Thu, Dec 20 2018 at  1:06pm -0500,
Nikos Tsironis <[e-mail]> wrote:

> Add hlist_bl_add_before/behind helpers to add an element before/after an
> existing element in a bl_list.
> 
> Signed-off-by: Nikos Tsironis <[e-mail]>
> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> ---
>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
>  1 file changed, 27 insertions(+)
> 
> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> index 3fc2cc57ba1b..2fd918e5fd48 100644
> --- a/include/linux/list_bl.h
> +++ b/include/linux/list_bl.h
> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
>  	hlist_bl_set_first(h, n);
>  }
>  
> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> +				       struct hlist_bl_node *next)
> +{
> +	struct hlist_bl_node **pprev = next->pprev;
> +
> +	n->pprev = pprev;
> +	n->next = next;
> +	next->pprev = &n->next;
> +
> +	/* pprev may be `first`, so be careful not to lose the lock bit */
> +	WRITE_ONCE(*pprev,
> +		   (struct hlist_bl_node *)
> +			((unsigned long)n |
> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
> +}
> +
> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> +				       struct hlist_bl_node *prev)
> +{
> +	n->next = prev->next;
> +	n->pprev = &prev->next;
> +	WRITE_ONCE(prev->next, n);
> +
> +	if (n->next)
> +		n->next->pprev = &n->next;
> +}
> +
>  static inline void __hlist_bl_del(struct hlist_bl_node *n)
>  {
>  	struct hlist_bl_node *next = n->next;
> -- 
> 2.11.0

Hi Paul and Christoph,

You've added your Signed-off-by to include/linux/list_bl.h commits in
the past.  I'm not sure how this proposed patch should be handled.

These new hlist_bl_add_{before,behind} changes are a prereq for
dm-snapshot changes that Nikos has proposed, please see:
https://patchwork.kernel.org/patch/10739265/

Any assistance/review you, or others on LKML, might be able to provide
would be appreciated.

Thanks,
Mike

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Mike Snitzer Feb. 28, 2019, 9:34 p.m. UTC | #2

On Thu, Feb 28 2019 at  4:32pm -0500,
Mike Snitzer <[e-mail]> wrote:

> On Thu, Dec 20 2018 at  1:06pm -0500,
> Nikos Tsironis <[e-mail]> wrote:
> 
> > Add hlist_bl_add_before/behind helpers to add an element before/after an
> > existing element in a bl_list.
> > 
> > Signed-off-by: Nikos Tsironis <[e-mail]>
> > Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> > ---
> >  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
> >  1 file changed, 27 insertions(+)
> > 
> > diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> > index 3fc2cc57ba1b..2fd918e5fd48 100644
> > --- a/include/linux/list_bl.h
> > +++ b/include/linux/list_bl.h
> > @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
> >  	hlist_bl_set_first(h, n);
> >  }
> >  
> > +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> > +				       struct hlist_bl_node *next)
> > +{
> > +	struct hlist_bl_node **pprev = next->pprev;
> > +
> > +	n->pprev = pprev;
> > +	n->next = next;
> > +	next->pprev = &n->next;
> > +
> > +	/* pprev may be `first`, so be careful not to lose the lock bit */
> > +	WRITE_ONCE(*pprev,
> > +		   (struct hlist_bl_node *)
> > +			((unsigned long)n |
> > +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
> > +}
> > +
> > +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> > +				       struct hlist_bl_node *prev)
> > +{
> > +	n->next = prev->next;
> > +	n->pprev = &prev->next;
> > +	WRITE_ONCE(prev->next, n);
> > +
> > +	if (n->next)
> > +		n->next->pprev = &n->next;
> > +}
> > +
> >  static inline void __hlist_bl_del(struct hlist_bl_node *n)
> >  {
> >  	struct hlist_bl_node *next = n->next;
> > -- 
> > 2.11.0
> 
> Hi Paul and Christoph,
> 
> You've added your Signed-off-by to include/linux/list_bl.h commits in
> the past.  I'm not sure how this proposed patch should be handled.
> 
> These new hlist_bl_add_{before,behind} changes are a prereq for
> dm-snapshot changes that Nikos has proposed, please see:
> https://patchwork.kernel.org/patch/10739265/
> 
> Any assistance/review you, or others on LKML, might be able to provide
> would be appreciated.

I should've clarified that: I'm asking for the purpose of getting these
changes staged for Linux 5.2.

Mike

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Christoph Hellwig March 11, 2019, 6:16 p.m. UTC | #3

On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> Hi Paul and Christoph,
> 
> You've added your Signed-off-by to include/linux/list_bl.h commits in
> the past.  I'm not sure how this proposed patch should be handled.
> 
> These new hlist_bl_add_{before,behind} changes are a prereq for
> dm-snapshot changes that Nikos has proposed, please see:
> https://patchwork.kernel.org/patch/10739265/
> 
> Any assistance/review you, or others on LKML, might be able to provide
> would be appreciated.

I just killed two helpers.  That being said assuming that we only
rely on the next pointer for the lockless traversals the changes look
fine to me, but the code might be beyond my paygrade..

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Paul E. McKenney March 11, 2019, 10:13 p.m. UTC | #4

On Mon, Mar 11, 2019 at 11:16:08AM -0700, Christoph Hellwig wrote:
> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> > Hi Paul and Christoph,
> > 
> > You've added your Signed-off-by to include/linux/list_bl.h commits in
> > the past.  I'm not sure how this proposed patch should be handled.
> > 
> > These new hlist_bl_add_{before,behind} changes are a prereq for
> > dm-snapshot changes that Nikos has proposed, please see:
> > https://patchwork.kernel.org/patch/10739265/
> > 
> > Any assistance/review you, or others on LKML, might be able to provide
> > would be appreciated.
> 
> I just killed two helpers.  That being said assuming that we only
> rely on the next pointer for the lockless traversals the changes look
> fine to me, but the code might be beyond my paygrade..

First, apologies for being slow on this one.

Second, were the two helpers hlist_bl_add_{before,behind}()?  If so, I
guess there is not much point in me looking them over.  Though perhaps
I should be looking something else over?

							Thanx, Paul

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Mike Snitzer March 11, 2019, 10:43 p.m. UTC | #5

On Mon, Mar 11 2019 at  6:13pm -0400,
Paul E. McKenney <[e-mail]> wrote:

> On Mon, Mar 11, 2019 at 11:16:08AM -0700, Christoph Hellwig wrote:
> > On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> > > Hi Paul and Christoph,
> > > 
> > > You've added your Signed-off-by to include/linux/list_bl.h commits in
> > > the past.  I'm not sure how this proposed patch should be handled.
> > > 
> > > These new hlist_bl_add_{before,behind} changes are a prereq for
> > > dm-snapshot changes that Nikos has proposed, please see:
> > > https://patchwork.kernel.org/patch/10739265/
> > > 
> > > Any assistance/review you, or others on LKML, might be able to provide
> > > would be appreciated.
> > 
> > I just killed two helpers.  That being said assuming that we only
> > rely on the next pointer for the lockless traversals the changes look
> > fine to me, but the code might be beyond my paygrade..
> 
> First, apologies for being slow on this one.

No problem.
 
> Second, were the two helpers hlist_bl_add_{before,behind}()?  If so, I
> guess there is not much point in me looking them over.  Though perhaps
> I should be looking something else over?

No, think Christoph was referring to his commit 1879fd6a26571fd4e8e1f
from 2011.

Anyway, I'd like you to look over this new proposed patch that
introduces hlist_bl_add_{before,behind}(), please see:
https://patchwork.kernel.org/patch/10835713/

If you're happy with the patch, and can provide your Reviewed-by or
Acked-by, I'll then pick it up as a prereq for the broader dm-snapshot
changes that Nikos has provided.

Thanks!
Mike

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Paul E. McKenney March 13, 2019, 11:48 p.m. UTC | #6

On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> On Thu, Dec 20 2018 at  1:06pm -0500,
> Nikos Tsironis <[e-mail]> wrote:
> 
> > Add hlist_bl_add_before/behind helpers to add an element before/after an
> > existing element in a bl_list.
> > 
> > Signed-off-by: Nikos Tsironis <[e-mail]>
> > Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> > ---
> >  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
> >  1 file changed, 27 insertions(+)
> > 
> > diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> > index 3fc2cc57ba1b..2fd918e5fd48 100644
> > --- a/include/linux/list_bl.h
> > +++ b/include/linux/list_bl.h
> > @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
> >  	hlist_bl_set_first(h, n);
> >  }
> >  
> > +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> > +				       struct hlist_bl_node *next)
> > +{
> > +	struct hlist_bl_node **pprev = next->pprev;
> > +
> > +	n->pprev = pprev;
> > +	n->next = next;
> > +	next->pprev = &n->next;
> > +
> > +	/* pprev may be `first`, so be careful not to lose the lock bit */
> > +	WRITE_ONCE(*pprev,
> > +		   (struct hlist_bl_node *)
> > +			((unsigned long)n |
> > +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));

A nit, but use of uintptr_t shrinks things a bit:

+		   (struct hlist_bl_node *)
+			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));

I am not too concerned about this, though.

The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
the corresponding READ_ONCE()) correct?

> > +}
> > +
> > +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> > +				       struct hlist_bl_node *prev)
> > +{
> > +	n->next = prev->next;
> > +	n->pprev = &prev->next;
> > +	WRITE_ONCE(prev->next, n);

I don't see what this WRITE_ONCE() is interacting with.  The traversals
use plain C-language reads, and hlist_bl_empty() can't get here.  All
uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
(Perhaps it should be removed?  Or is there some anticipated use?)

I don't believe that the WRITE_ONCE() is needed.  What am I missing?

Other than that, looks good.

							Thanx, Paul

> > +
> > +	if (n->next)
> > +		n->next->pprev = &n->next;
> > +}
> > +
> >  static inline void __hlist_bl_del(struct hlist_bl_node *n)
> >  {
> >  	struct hlist_bl_node *next = n->next;
> > -- 
> > 2.11.0
> 
> Hi Paul and Christoph,
> 
> You've added your Signed-off-by to include/linux/list_bl.h commits in
> the past.  I'm not sure how this proposed patch should be handled.
> 
> These new hlist_bl_add_{before,behind} changes are a prereq for
> dm-snapshot changes that Nikos has proposed, please see:
> https://patchwork.kernel.org/patch/10739265/
> 
> Any assistance/review you, or others on LKML, might be able to provide
> would be appreciated.
> 
> Thanks,
> Mike
> 

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Paul E. McKenney March 14, 2019, 12:25 a.m. UTC | #7

On Mon, Mar 11, 2019 at 06:43:33PM -0400, Mike Snitzer wrote:
> On Mon, Mar 11 2019 at  6:13pm -0400,
> Paul E. McKenney <[e-mail]> wrote:
> 
> > On Mon, Mar 11, 2019 at 11:16:08AM -0700, Christoph Hellwig wrote:
> > > On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> > > > Hi Paul and Christoph,
> > > > 
> > > > You've added your Signed-off-by to include/linux/list_bl.h commits in
> > > > the past.  I'm not sure how this proposed patch should be handled.
> > > > 
> > > > These new hlist_bl_add_{before,behind} changes are a prereq for
> > > > dm-snapshot changes that Nikos has proposed, please see:
> > > > https://patchwork.kernel.org/patch/10739265/
> > > > 
> > > > Any assistance/review you, or others on LKML, might be able to provide
> > > > would be appreciated.
> > > 
> > > I just killed two helpers.  That being said assuming that we only
> > > rely on the next pointer for the lockless traversals the changes look
> > > fine to me, but the code might be beyond my paygrade..
> > 
> > First, apologies for being slow on this one.
> 
> No problem.
>  
> > Second, were the two helpers hlist_bl_add_{before,behind}()?  If so, I
> > guess there is not much point in me looking them over.  Though perhaps
> > I should be looking something else over?
> 
> No, think Christoph was referring to his commit 1879fd6a26571fd4e8e1f
> from 2011.
> 
> Anyway, I'd like you to look over this new proposed patch that
> introduces hlist_bl_add_{before,behind}(), please see:
> https://patchwork.kernel.org/patch/10835713/
> 
> If you're happy with the patch, and can provide your Reviewed-by or
> Acked-by, I'll then pick it up as a prereq for the broader dm-snapshot
> changes that Nikos has provided.

I replied to the version earlier in this email thread.  Looks close,
but a couple of questions.

							Thanx, Paul

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Mike Snitzer March 14, 2019, 12:30 a.m. UTC | #8

On Wed, Mar 13 2019 at  7:48pm -0400,
Paul E. McKenney <[e-mail]> wrote:

> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> > On Thu, Dec 20 2018 at  1:06pm -0500,
> > Nikos Tsironis <[e-mail]> wrote:
> > 
> > > Add hlist_bl_add_before/behind helpers to add an element before/after an
> > > existing element in a bl_list.
> > > 
> > > Signed-off-by: Nikos Tsironis <[e-mail]>
> > > Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> > > ---
> > >  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
> > >  1 file changed, 27 insertions(+)
> > > 
> > > diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> > > index 3fc2cc57ba1b..2fd918e5fd48 100644
> > > --- a/include/linux/list_bl.h
> > > +++ b/include/linux/list_bl.h
> > > @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
> > >  	hlist_bl_set_first(h, n);
> > >  }
> > >  
> > > +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> > > +				       struct hlist_bl_node *next)
> > > +{
> > > +	struct hlist_bl_node **pprev = next->pprev;
> > > +
> > > +	n->pprev = pprev;
> > > +	n->next = next;
> > > +	next->pprev = &n->next;
> > > +
> > > +	/* pprev may be `first`, so be careful not to lose the lock bit */
> > > +	WRITE_ONCE(*pprev,
> > > +		   (struct hlist_bl_node *)
> > > +			((unsigned long)n |
> > > +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
> 
> A nit, but use of uintptr_t shrinks things a bit:
> 
> +		   (struct hlist_bl_node *)
> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
> 
> I am not too concerned about this, though.

I'm fine with folding in your suggestion.

> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
> the corresponding READ_ONCE()) correct?

Correct.

> > > +}
> > > +
> > > +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> > > +				       struct hlist_bl_node *prev)
> > > +{
> > > +	n->next = prev->next;
> > > +	n->pprev = &prev->next;
> > > +	WRITE_ONCE(prev->next, n);
> 
> I don't see what this WRITE_ONCE() is interacting with.  The traversals
> use plain C-language reads, and hlist_bl_empty() can't get here.  All
> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
> (Perhaps it should be removed?  Or is there some anticipated use?)
> 
> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
> 
> Other than that, looks good.
> 
> 							Thanx, Paul
> 

I'd imagine it was just born out of symmetry with hlist_bl_add_before()
and/or caution.  But let's see what Nikos has to say.

Thanks,
Mike

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Nikos Tsironis March 14, 2019, 1:28 p.m. UTC | #9

On 3/14/19 2:30 AM, Mike Snitzer wrote:
> On Wed, Mar 13 2019 at  7:48pm -0400,
> Paul E. McKenney <[e-mail]> wrote:
> 
Hi Paul,

Thanks a lot for your feedback!

>> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
>>> On Thu, Dec 20 2018 at  1:06pm -0500,
>>> Nikos Tsironis <[e-mail]> wrote:
>>>
>>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
>>>> existing element in a bl_list.
>>>>
>>>> Signed-off-by: Nikos Tsironis <[e-mail]>
>>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
>>>> ---
>>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
>>>>  1 file changed, 27 insertions(+)
>>>>
>>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
>>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
>>>> --- a/include/linux/list_bl.h
>>>> +++ b/include/linux/list_bl.h
>>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
>>>>  	hlist_bl_set_first(h, n);
>>>>  }
>>>>  
>>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
>>>> +				       struct hlist_bl_node *next)
>>>> +{
>>>> +	struct hlist_bl_node **pprev = next->pprev;
>>>> +
>>>> +	n->pprev = pprev;
>>>> +	n->next = next;
>>>> +	next->pprev = &n->next;
>>>> +
>>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
>>>> +	WRITE_ONCE(*pprev,
>>>> +		   (struct hlist_bl_node *)
>>>> +			((unsigned long)n |
>>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
>>
>> A nit, but use of uintptr_t shrinks things a bit:
>>
>> +		   (struct hlist_bl_node *)
>> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
>>
>> I am not too concerned about this, though.
> 
> I'm fine with folding in your suggestion.
> 

Indeed, this looks better.

>> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
>> the corresponding READ_ONCE()) correct?
> 
> Correct.

Yes that's correct.

> 
>>>> +}
>>>> +
>>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
>>>> +				       struct hlist_bl_node *prev)
>>>> +{
>>>> +	n->next = prev->next;
>>>> +	n->pprev = &prev->next;
>>>> +	WRITE_ONCE(prev->next, n);
>>
>> I don't see what this WRITE_ONCE() is interacting with.  The traversals
>> use plain C-language reads, and hlist_bl_empty() can't get here.  All
>> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
>> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
>> (Perhaps it should be removed?  Or is there some anticipated use?)

I am using hlist_bl_for_each_entry_safe() in this proposed patch for
dm-snapshot: https://patchwork.kernel.org/patch/10835709/

>>
>> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
>>
>> Other than that, looks good.
>>
>> 							Thanx, Paul
>>
> 
> I'd imagine it was just born out of symmetry with hlist_bl_add_before()
> and/or caution.  But let's see what Nikos has to say.

I also don't believe that this WRITE_SAME() is needed. But, looking at
hlist_add_behind() in include/linux/list.h, which, if I am not missing
something, is used in the same way as hlist_bl_add_behind(), it also
uses WRITE_ONCE() to update prev->next:

static inline void hlist_add_behind(struct hlist_node *n,
				    struct hlist_node *prev)
{
	n->next = prev->next;
	WRITE_ONCE(prev->next, n);
	n->pprev = &prev->next;

	if (n->next)
		n->next->pprev  = &n->next;
}

Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
("list: Use WRITE_ONCE() when adding to lists and hlists").

But, since I am not an expert in lockless programming, I opted to be on
the safe side and followed the example of hlist_add_behind().

That said, I will follow up with a new version of the patch removing the
WRITE_ONCE() and using uintptr_t instead of unsigned long.

Thanks,
Nikos

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Paul E. McKenney March 14, 2019, 2:07 p.m. UTC | #10

On Thu, Mar 14, 2019 at 03:28:23PM +0200, Nikos Tsironis wrote:
> On 3/14/19 2:30 AM, Mike Snitzer wrote:
> > On Wed, Mar 13 2019 at  7:48pm -0400,
> > Paul E. McKenney <[e-mail]> wrote:
> > 
> Hi Paul,
> 
> Thanks a lot for your feedback!

NP, and apologies for the delay.

> >> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> >>> On Thu, Dec 20 2018 at  1:06pm -0500,
> >>> Nikos Tsironis <[e-mail]> wrote:
> >>>
> >>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
> >>>> existing element in a bl_list.
> >>>>
> >>>> Signed-off-by: Nikos Tsironis <[e-mail]>
> >>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> >>>> ---
> >>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
> >>>>  1 file changed, 27 insertions(+)
> >>>>
> >>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> >>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
> >>>> --- a/include/linux/list_bl.h
> >>>> +++ b/include/linux/list_bl.h
> >>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
> >>>>  	hlist_bl_set_first(h, n);
> >>>>  }
> >>>>  
> >>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> >>>> +				       struct hlist_bl_node *next)
> >>>> +{
> >>>> +	struct hlist_bl_node **pprev = next->pprev;
> >>>> +
> >>>> +	n->pprev = pprev;
> >>>> +	n->next = next;
> >>>> +	next->pprev = &n->next;
> >>>> +
> >>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
> >>>> +	WRITE_ONCE(*pprev,
> >>>> +		   (struct hlist_bl_node *)
> >>>> +			((unsigned long)n |
> >>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
> >>
> >> A nit, but use of uintptr_t shrinks things a bit:
> >>
> >> +		   (struct hlist_bl_node *)
> >> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
> >>
> >> I am not too concerned about this, though.
> > 
> > I'm fine with folding in your suggestion.
> 
> Indeed, this looks better.
> 
> >> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
> >> the corresponding READ_ONCE()) correct?
> > 
> > Correct.
> 
> Yes that's correct.
> 
> >>>> +}
> >>>> +
> >>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> >>>> +				       struct hlist_bl_node *prev)
> >>>> +{
> >>>> +	n->next = prev->next;
> >>>> +	n->pprev = &prev->next;
> >>>> +	WRITE_ONCE(prev->next, n);
> >>
> >> I don't see what this WRITE_ONCE() is interacting with.  The traversals
> >> use plain C-language reads, and hlist_bl_empty() can't get here.  All
> >> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
> >> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
> >> (Perhaps it should be removed?  Or is there some anticipated use?)
> 
> I am using hlist_bl_for_each_entry_safe() in this proposed patch for
> dm-snapshot: https://patchwork.kernel.org/patch/10835709/

Probably should keep it, then.  ;-)

> >>
> >> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
> >>
> >> Other than that, looks good.
> >>
> >> 							Thanx, Paul
> >>
> > 
> > I'd imagine it was just born out of symmetry with hlist_bl_add_before()
> > and/or caution.  But let's see what Nikos has to say.
> 
> I also don't believe that this WRITE_SAME() is needed. But, looking at
> hlist_add_behind() in include/linux/list.h, which, if I am not missing
> something, is used in the same way as hlist_bl_add_behind(), it also
> uses WRITE_ONCE() to update prev->next:
> 
> static inline void hlist_add_behind(struct hlist_node *n,
> 				    struct hlist_node *prev)
> {
> 	n->next = prev->next;
> 	WRITE_ONCE(prev->next, n);
> 	n->pprev = &prev->next;
> 
> 	if (n->next)
> 		n->next->pprev  = &n->next;
> }
> 
> Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
> not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
> ("list: Use WRITE_ONCE() when adding to lists and hlists").

Looks like I have no one to blame but myself!

Would you like to remove that as part of your patch series?

> But, since I am not an expert in lockless programming, I opted to be on
> the safe side and followed the example of hlist_add_behind().
> 
> That said, I will follow up with a new version of the patch removing the
> WRITE_ONCE() and using uintptr_t instead of unsigned long.

Sounds good!

							Thanx, Paul

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Paul E. McKenney March 14, 2019, 3:03 p.m. UTC | #11

On Thu, Mar 14, 2019 at 07:07:50AM -0700, Paul E. McKenney wrote:
> On Thu, Mar 14, 2019 at 03:28:23PM +0200, Nikos Tsironis wrote:
> > On 3/14/19 2:30 AM, Mike Snitzer wrote:
> > > On Wed, Mar 13 2019 at  7:48pm -0400,
> > > Paul E. McKenney <[e-mail]> wrote:
> > > 
> > Hi Paul,
> > 
> > Thanks a lot for your feedback!
> 
> NP, and apologies for the delay.
> 
> > >> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> > >>> On Thu, Dec 20 2018 at  1:06pm -0500,
> > >>> Nikos Tsironis <[e-mail]> wrote:
> > >>>
> > >>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
> > >>>> existing element in a bl_list.
> > >>>>
> > >>>> Signed-off-by: Nikos Tsironis <[e-mail]>
> > >>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> > >>>> ---
> > >>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
> > >>>>  1 file changed, 27 insertions(+)
> > >>>>
> > >>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> > >>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
> > >>>> --- a/include/linux/list_bl.h
> > >>>> +++ b/include/linux/list_bl.h
> > >>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
> > >>>>  	hlist_bl_set_first(h, n);
> > >>>>  }
> > >>>>  
> > >>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> > >>>> +				       struct hlist_bl_node *next)
> > >>>> +{
> > >>>> +	struct hlist_bl_node **pprev = next->pprev;
> > >>>> +
> > >>>> +	n->pprev = pprev;
> > >>>> +	n->next = next;
> > >>>> +	next->pprev = &n->next;
> > >>>> +
> > >>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
> > >>>> +	WRITE_ONCE(*pprev,
> > >>>> +		   (struct hlist_bl_node *)
> > >>>> +			((unsigned long)n |
> > >>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
> > >>
> > >> A nit, but use of uintptr_t shrinks things a bit:
> > >>
> > >> +		   (struct hlist_bl_node *)
> > >> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
> > >>
> > >> I am not too concerned about this, though.
> > > 
> > > I'm fine with folding in your suggestion.
> > 
> > Indeed, this looks better.
> > 
> > >> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
> > >> the corresponding READ_ONCE()) correct?
> > > 
> > > Correct.
> > 
> > Yes that's correct.
> > 
> > >>>> +}
> > >>>> +
> > >>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> > >>>> +				       struct hlist_bl_node *prev)
> > >>>> +{
> > >>>> +	n->next = prev->next;
> > >>>> +	n->pprev = &prev->next;
> > >>>> +	WRITE_ONCE(prev->next, n);
> > >>
> > >> I don't see what this WRITE_ONCE() is interacting with.  The traversals
> > >> use plain C-language reads, and hlist_bl_empty() can't get here.  All
> > >> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
> > >> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
> > >> (Perhaps it should be removed?  Or is there some anticipated use?)
> > 
> > I am using hlist_bl_for_each_entry_safe() in this proposed patch for
> > dm-snapshot: https://patchwork.kernel.org/patch/10835709/
> 
> Probably should keep it, then.  ;-)
> 
> > >>
> > >> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
> > >>
> > >> Other than that, looks good.
> > >>
> > >> 							Thanx, Paul
> > >>
> > > 
> > > I'd imagine it was just born out of symmetry with hlist_bl_add_before()
> > > and/or caution.  But let's see what Nikos has to say.
> > 
> > I also don't believe that this WRITE_SAME() is needed. But, looking at
> > hlist_add_behind() in include/linux/list.h, which, if I am not missing
> > something, is used in the same way as hlist_bl_add_behind(), it also
> > uses WRITE_ONCE() to update prev->next:
> > 
> > static inline void hlist_add_behind(struct hlist_node *n,
> > 				    struct hlist_node *prev)
> > {
> > 	n->next = prev->next;
> > 	WRITE_ONCE(prev->next, n);
> > 	n->pprev = &prev->next;
> > 
> > 	if (n->next)
> > 		n->next->pprev  = &n->next;
> > }
> > 
> > Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
> > not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
> > ("list: Use WRITE_ONCE() when adding to lists and hlists").
> 
> Looks like I have no one to blame but myself!
> 
> Would you like to remove that as part of your patch series?
> 
> > But, since I am not an expert in lockless programming, I opted to be on
> > the safe side and followed the example of hlist_add_behind().
> > 
> > That said, I will follow up with a new version of the patch removing the
> > WRITE_ONCE() and using uintptr_t instead of unsigned long.
> 
> Sounds good!

Oh, and of course intptr_t is one character shorter than uintptr_t, and
looks to work just as well in this context.  ;-)

							Thanx, Paul

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Nikos Tsironis March 14, 2019, 5:01 p.m. UTC | #12

On 3/14/19 4:07 PM, Paul E. McKenney wrote:
> On Thu, Mar 14, 2019 at 03:28:23PM +0200, Nikos Tsironis wrote:
>> On 3/14/19 2:30 AM, Mike Snitzer wrote:
>>> On Wed, Mar 13 2019 at  7:48pm -0400,
>>> Paul E. McKenney <[e-mail]> wrote:
>>>
>> Hi Paul,
>>
>> Thanks a lot for your feedback!
> 
> NP, and apologies for the delay.
> 
>>>> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
>>>>> On Thu, Dec 20 2018 at  1:06pm -0500,
>>>>> Nikos Tsironis <[e-mail]> wrote:
>>>>>
>>>>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
>>>>>> existing element in a bl_list.
>>>>>>
>>>>>> Signed-off-by: Nikos Tsironis <[e-mail]>
>>>>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
>>>>>> ---
>>>>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
>>>>>>  1 file changed, 27 insertions(+)
>>>>>>
>>>>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
>>>>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
>>>>>> --- a/include/linux/list_bl.h
>>>>>> +++ b/include/linux/list_bl.h
>>>>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
>>>>>>  	hlist_bl_set_first(h, n);
>>>>>>  }
>>>>>>  
>>>>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
>>>>>> +				       struct hlist_bl_node *next)
>>>>>> +{
>>>>>> +	struct hlist_bl_node **pprev = next->pprev;
>>>>>> +
>>>>>> +	n->pprev = pprev;
>>>>>> +	n->next = next;
>>>>>> +	next->pprev = &n->next;
>>>>>> +
>>>>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
>>>>>> +	WRITE_ONCE(*pprev,
>>>>>> +		   (struct hlist_bl_node *)
>>>>>> +			((unsigned long)n |
>>>>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
>>>>
>>>> A nit, but use of uintptr_t shrinks things a bit:
>>>>
>>>> +		   (struct hlist_bl_node *)
>>>> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
>>>>
>>>> I am not too concerned about this, though.
>>>
>>> I'm fine with folding in your suggestion.
>>
>> Indeed, this looks better.
>>
>>>> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
>>>> the corresponding READ_ONCE()) correct?
>>>
>>> Correct.
>>
>> Yes that's correct.
>>
>>>>>> +}
>>>>>> +
>>>>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
>>>>>> +				       struct hlist_bl_node *prev)
>>>>>> +{
>>>>>> +	n->next = prev->next;
>>>>>> +	n->pprev = &prev->next;
>>>>>> +	WRITE_ONCE(prev->next, n);
>>>>
>>>> I don't see what this WRITE_ONCE() is interacting with.  The traversals
>>>> use plain C-language reads, and hlist_bl_empty() can't get here.  All
>>>> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
>>>> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
>>>> (Perhaps it should be removed?  Or is there some anticipated use?)
>>
>> I am using hlist_bl_for_each_entry_safe() in this proposed patch for
>> dm-snapshot: https://patchwork.kernel.org/patch/10835709/
> 
> Probably should keep it, then.  ;-)
> 
>>>>
>>>> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
>>>>
>>>> Other than that, looks good.
>>>>
>>>> 							Thanx, Paul
>>>>
>>>
>>> I'd imagine it was just born out of symmetry with hlist_bl_add_before()
>>> and/or caution.  But let's see what Nikos has to say.
>>
>> I also don't believe that this WRITE_SAME() is needed. But, looking at
>> hlist_add_behind() in include/linux/list.h, which, if I am not missing
>> something, is used in the same way as hlist_bl_add_behind(), it also
>> uses WRITE_ONCE() to update prev->next:
>>
>> static inline void hlist_add_behind(struct hlist_node *n,
>> 				    struct hlist_node *prev)
>> {
>> 	n->next = prev->next;
>> 	WRITE_ONCE(prev->next, n);
>> 	n->pprev = &prev->next;
>>
>> 	if (n->next)
>> 		n->next->pprev  = &n->next;
>> }
>>
>> Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
>> not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
>> ("list: Use WRITE_ONCE() when adding to lists and hlists").
> 
> Looks like I have no one to blame but myself!
> 
> Would you like to remove that as part of your patch series?

Yes, Of course. I will add an extra patch removing the WRITE_ONCE() from
hlist_add_behind().

Thanks,
Nikos

> 
>> But, since I am not an expert in lockless programming, I opted to be on
>> the safe side and followed the example of hlist_add_behind().
>>
>> That said, I will follow up with a new version of the patch removing the
>> WRITE_ONCE() and using uintptr_t instead of unsigned long.
> 
> Sounds good!
> 
> 							Thanx, Paul
> 
> --
> dm-devel mailing list
> [e-mail]
> https://www.redhat.com/mailman/listinfo/dm-devel
> 

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Nikos Tsironis March 17, 2019, 11:52 a.m. UTC | #13

On 3/14/19 5:03 PM, Paul E. McKenney wrote:
> On Thu, Mar 14, 2019 at 07:07:50AM -0700, Paul E. McKenney wrote:
>> On Thu, Mar 14, 2019 at 03:28:23PM +0200, Nikos Tsironis wrote:
>>> On 3/14/19 2:30 AM, Mike Snitzer wrote:
>>>> On Wed, Mar 13 2019 at  7:48pm -0400,
>>>> Paul E. McKenney <[e-mail]> wrote:
>>>>
>>> Hi Paul,
>>>
>>> Thanks a lot for your feedback!
>>
>> NP, and apologies for the delay.
>>
>>>>> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
>>>>>> On Thu, Dec 20 2018 at  1:06pm -0500,
>>>>>> Nikos Tsironis <[e-mail]> wrote:
>>>>>>
>>>>>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
>>>>>>> existing element in a bl_list.
>>>>>>>
>>>>>>> Signed-off-by: Nikos Tsironis <[e-mail]>
>>>>>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
>>>>>>> ---
>>>>>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
>>>>>>>  1 file changed, 27 insertions(+)
>>>>>>>
>>>>>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
>>>>>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
>>>>>>> --- a/include/linux/list_bl.h
>>>>>>> +++ b/include/linux/list_bl.h
>>>>>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
>>>>>>>  	hlist_bl_set_first(h, n);
>>>>>>>  }
>>>>>>>  
>>>>>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
>>>>>>> +				       struct hlist_bl_node *next)
>>>>>>> +{
>>>>>>> +	struct hlist_bl_node **pprev = next->pprev;
>>>>>>> +
>>>>>>> +	n->pprev = pprev;
>>>>>>> +	n->next = next;
>>>>>>> +	next->pprev = &n->next;
>>>>>>> +
>>>>>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
>>>>>>> +	WRITE_ONCE(*pprev,
>>>>>>> +		   (struct hlist_bl_node *)
>>>>>>> +			((unsigned long)n |
>>>>>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
>>>>>
>>>>> A nit, but use of uintptr_t shrinks things a bit:
>>>>>
>>>>> +		   (struct hlist_bl_node *)
>>>>> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
>>>>>
>>>>> I am not too concerned about this, though.
>>>>
>>>> I'm fine with folding in your suggestion.
>>>
>>> Indeed, this looks better.
>>>
>>>>> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
>>>>> the corresponding READ_ONCE()) correct?
>>>>
>>>> Correct.
>>>
>>> Yes that's correct.
>>>
>>>>>>> +}
>>>>>>> +
>>>>>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
>>>>>>> +				       struct hlist_bl_node *prev)
>>>>>>> +{
>>>>>>> +	n->next = prev->next;
>>>>>>> +	n->pprev = &prev->next;
>>>>>>> +	WRITE_ONCE(prev->next, n);
>>>>>
>>>>> I don't see what this WRITE_ONCE() is interacting with.  The traversals
>>>>> use plain C-language reads, and hlist_bl_empty() can't get here.  All
>>>>> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
>>>>> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
>>>>> (Perhaps it should be removed?  Or is there some anticipated use?)
>>>
>>> I am using hlist_bl_for_each_entry_safe() in this proposed patch for
>>> dm-snapshot: https://patchwork.kernel.org/patch/10835709/
>>
>> Probably should keep it, then.  ;-)
>>
>>>>>
>>>>> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
>>>>>
>>>>> Other than that, looks good.
>>>>>
>>>>> 							Thanx, Paul
>>>>>
>>>>
>>>> I'd imagine it was just born out of symmetry with hlist_bl_add_before()
>>>> and/or caution.  But let's see what Nikos has to say.
>>>
>>> I also don't believe that this WRITE_SAME() is needed. But, looking at
>>> hlist_add_behind() in include/linux/list.h, which, if I am not missing
>>> something, is used in the same way as hlist_bl_add_behind(), it also
>>> uses WRITE_ONCE() to update prev->next:
>>>
>>> static inline void hlist_add_behind(struct hlist_node *n,
>>> 				    struct hlist_node *prev)
>>> {
>>> 	n->next = prev->next;
>>> 	WRITE_ONCE(prev->next, n);
>>> 	n->pprev = &prev->next;
>>>
>>> 	if (n->next)
>>> 		n->next->pprev  = &n->next;
>>> }
>>>
>>> Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
>>> not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
>>> ("list: Use WRITE_ONCE() when adding to lists and hlists").
>>
>> Looks like I have no one to blame but myself!
>>
>> Would you like to remove that as part of your patch series?
>>
>>> But, since I am not an expert in lockless programming, I opted to be on
>>> the safe side and followed the example of hlist_add_behind().
>>>
>>> That said, I will follow up with a new version of the patch removing the
>>> WRITE_ONCE() and using uintptr_t instead of unsigned long.
>>
>> Sounds good!
> 
> Oh, and of course intptr_t is one character shorter than uintptr_t, and
> looks to work just as well in this context.  ;-)
> 
> 							Thanx, Paul
> 


Hi Paul,

Sorry for the late reply.

intptr_t seems to be defined only in a header file under arch/mips, so I
will stick to uintptr_t.

Thanks,
Nikos

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Paul E. McKenney March 18, 2019, 5:16 p.m. UTC | #14

On Sun, Mar 17, 2019 at 01:52:50PM +0200, Nikos Tsironis wrote:
> On 3/14/19 5:03 PM, Paul E. McKenney wrote:
> > On Thu, Mar 14, 2019 at 07:07:50AM -0700, Paul E. McKenney wrote:
> >> On Thu, Mar 14, 2019 at 03:28:23PM +0200, Nikos Tsironis wrote:
> >>> On 3/14/19 2:30 AM, Mike Snitzer wrote:
> >>>> On Wed, Mar 13 2019 at  7:48pm -0400,
> >>>> Paul E. McKenney <[e-mail]> wrote:
> >>>>
> >>> Hi Paul,
> >>>
> >>> Thanks a lot for your feedback!
> >>
> >> NP, and apologies for the delay.
> >>
> >>>>> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
> >>>>>> On Thu, Dec 20 2018 at  1:06pm -0500,
> >>>>>> Nikos Tsironis <[e-mail]> wrote:
> >>>>>>
> >>>>>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
> >>>>>>> existing element in a bl_list.
> >>>>>>>
> >>>>>>> Signed-off-by: Nikos Tsironis <[e-mail]>
> >>>>>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
> >>>>>>> ---
> >>>>>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
> >>>>>>>  1 file changed, 27 insertions(+)
> >>>>>>>
> >>>>>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
> >>>>>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
> >>>>>>> --- a/include/linux/list_bl.h
> >>>>>>> +++ b/include/linux/list_bl.h
> >>>>>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
> >>>>>>>  	hlist_bl_set_first(h, n);
> >>>>>>>  }
> >>>>>>>  
> >>>>>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
> >>>>>>> +				       struct hlist_bl_node *next)
> >>>>>>> +{
> >>>>>>> +	struct hlist_bl_node **pprev = next->pprev;
> >>>>>>> +
> >>>>>>> +	n->pprev = pprev;
> >>>>>>> +	n->next = next;
> >>>>>>> +	next->pprev = &n->next;
> >>>>>>> +
> >>>>>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
> >>>>>>> +	WRITE_ONCE(*pprev,
> >>>>>>> +		   (struct hlist_bl_node *)
> >>>>>>> +			((unsigned long)n |
> >>>>>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
> >>>>>
> >>>>> A nit, but use of uintptr_t shrinks things a bit:
> >>>>>
> >>>>> +		   (struct hlist_bl_node *)
> >>>>> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
> >>>>>
> >>>>> I am not too concerned about this, though.
> >>>>
> >>>> I'm fine with folding in your suggestion.
> >>>
> >>> Indeed, this looks better.
> >>>
> >>>>> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
> >>>>> the corresponding READ_ONCE()) correct?
> >>>>
> >>>> Correct.
> >>>
> >>> Yes that's correct.
> >>>
> >>>>>>> +}
> >>>>>>> +
> >>>>>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
> >>>>>>> +				       struct hlist_bl_node *prev)
> >>>>>>> +{
> >>>>>>> +	n->next = prev->next;
> >>>>>>> +	n->pprev = &prev->next;
> >>>>>>> +	WRITE_ONCE(prev->next, n);
> >>>>>
> >>>>> I don't see what this WRITE_ONCE() is interacting with.  The traversals
> >>>>> use plain C-language reads, and hlist_bl_empty() can't get here.  All
> >>>>> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
> >>>>> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
> >>>>> (Perhaps it should be removed?  Or is there some anticipated use?)
> >>>
> >>> I am using hlist_bl_for_each_entry_safe() in this proposed patch for
> >>> dm-snapshot: https://patchwork.kernel.org/patch/10835709/
> >>
> >> Probably should keep it, then.  ;-)
> >>
> >>>>>
> >>>>> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
> >>>>>
> >>>>> Other than that, looks good.
> >>>>>
> >>>>> 							Thanx, Paul
> >>>>>
> >>>>
> >>>> I'd imagine it was just born out of symmetry with hlist_bl_add_before()
> >>>> and/or caution.  But let's see what Nikos has to say.
> >>>
> >>> I also don't believe that this WRITE_SAME() is needed. But, looking at
> >>> hlist_add_behind() in include/linux/list.h, which, if I am not missing
> >>> something, is used in the same way as hlist_bl_add_behind(), it also
> >>> uses WRITE_ONCE() to update prev->next:
> >>>
> >>> static inline void hlist_add_behind(struct hlist_node *n,
> >>> 				    struct hlist_node *prev)
> >>> {
> >>> 	n->next = prev->next;
> >>> 	WRITE_ONCE(prev->next, n);
> >>> 	n->pprev = &prev->next;
> >>>
> >>> 	if (n->next)
> >>> 		n->next->pprev  = &n->next;
> >>> }
> >>>
> >>> Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
> >>> not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
> >>> ("list: Use WRITE_ONCE() when adding to lists and hlists").
> >>
> >> Looks like I have no one to blame but myself!
> >>
> >> Would you like to remove that as part of your patch series?
> >>
> >>> But, since I am not an expert in lockless programming, I opted to be on
> >>> the safe side and followed the example of hlist_add_behind().
> >>>
> >>> That said, I will follow up with a new version of the patch removing the
> >>> WRITE_ONCE() and using uintptr_t instead of unsigned long.
> >>
> >> Sounds good!
> > 
> > Oh, and of course intptr_t is one character shorter than uintptr_t, and
> > looks to work just as well in this context.  ;-)
> > 
> > 							Thanx, Paul
> > 
> 
> 
> Hi Paul,
> 
> Sorry for the late reply.
> 
> intptr_t seems to be defined only in a header file under arch/mips, so I
> will stick to uintptr_t.

Ah, apologies for the misdirection!  Hmmm...  Maybe intptr_t should be
added alongside uintptr_t?  Saving a character is saving a character.  ;-)

							Thanx, Paul

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Nikos Tsironis March 20, 2019, 8:25 p.m. UTC | #15

On 3/18/19 7:16 PM, Paul E. McKenney wrote:
> On Sun, Mar 17, 2019 at 01:52:50PM +0200, Nikos Tsironis wrote:
>> On 3/14/19 5:03 PM, Paul E. McKenney wrote:
>>> On Thu, Mar 14, 2019 at 07:07:50AM -0700, Paul E. McKenney wrote:
>>>> On Thu, Mar 14, 2019 at 03:28:23PM +0200, Nikos Tsironis wrote:
>>>>> On 3/14/19 2:30 AM, Mike Snitzer wrote:
>>>>>> On Wed, Mar 13 2019 at  7:48pm -0400,
>>>>>> Paul E. McKenney <[e-mail]> wrote:
>>>>>>
>>>>> Hi Paul,
>>>>>
>>>>> Thanks a lot for your feedback!
>>>>
>>>> NP, and apologies for the delay.
>>>>
>>>>>>> On Thu, Feb 28, 2019 at 04:32:02PM -0500, Mike Snitzer wrote:
>>>>>>>> On Thu, Dec 20 2018 at  1:06pm -0500,
>>>>>>>> Nikos Tsironis <[e-mail]> wrote:
>>>>>>>>
>>>>>>>>> Add hlist_bl_add_before/behind helpers to add an element before/after an
>>>>>>>>> existing element in a bl_list.
>>>>>>>>>
>>>>>>>>> Signed-off-by: Nikos Tsironis <[e-mail]>
>>>>>>>>> Signed-off-by: Ilias Tsitsimpis <[e-mail]>
>>>>>>>>> ---
>>>>>>>>>  include/linux/list_bl.h | 27 +++++++++++++++++++++++++++
>>>>>>>>>  1 file changed, 27 insertions(+)
>>>>>>>>>
>>>>>>>>> diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
>>>>>>>>> index 3fc2cc57ba1b..2fd918e5fd48 100644
>>>>>>>>> --- a/include/linux/list_bl.h
>>>>>>>>> +++ b/include/linux/list_bl.h
>>>>>>>>> @@ -86,6 +86,33 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
>>>>>>>>>  	hlist_bl_set_first(h, n);
>>>>>>>>>  }
>>>>>>>>>  
>>>>>>>>> +static inline void hlist_bl_add_before(struct hlist_bl_node *n,
>>>>>>>>> +				       struct hlist_bl_node *next)
>>>>>>>>> +{
>>>>>>>>> +	struct hlist_bl_node **pprev = next->pprev;
>>>>>>>>> +
>>>>>>>>> +	n->pprev = pprev;
>>>>>>>>> +	n->next = next;
>>>>>>>>> +	next->pprev = &n->next;
>>>>>>>>> +
>>>>>>>>> +	/* pprev may be `first`, so be careful not to lose the lock bit */
>>>>>>>>> +	WRITE_ONCE(*pprev,
>>>>>>>>> +		   (struct hlist_bl_node *)
>>>>>>>>> +			((unsigned long)n |
>>>>>>>>> +			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
>>>>>>>
>>>>>>> A nit, but use of uintptr_t shrinks things a bit:
>>>>>>>
>>>>>>> +		   (struct hlist_bl_node *)
>>>>>>> +			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
>>>>>>>
>>>>>>> I am not too concerned about this, though.
>>>>>>
>>>>>> I'm fine with folding in your suggestion.
>>>>>
>>>>> Indeed, this looks better.
>>>>>
>>>>>>> The WRITE_ONCE() is to handle races with hlist_bl_empty() (which does contain
>>>>>>> the corresponding READ_ONCE()) correct?
>>>>>>
>>>>>> Correct.
>>>>>
>>>>> Yes that's correct.
>>>>>
>>>>>>>>> +}
>>>>>>>>> +
>>>>>>>>> +static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
>>>>>>>>> +				       struct hlist_bl_node *prev)
>>>>>>>>> +{
>>>>>>>>> +	n->next = prev->next;
>>>>>>>>> +	n->pprev = &prev->next;
>>>>>>>>> +	WRITE_ONCE(prev->next, n);
>>>>>>>
>>>>>>> I don't see what this WRITE_ONCE() is interacting with.  The traversals
>>>>>>> use plain C-language reads, and hlist_bl_empty() can't get here.  All
>>>>>>> uses of hlist_bl_for_each_entry() invoke hlist_bl_lock() before starting
>>>>>>> the traversal, and hlist_bl_for_each_entry_safe() looks to be unused.
>>>>>>> (Perhaps it should be removed?  Or is there some anticipated use?)
>>>>>
>>>>> I am using hlist_bl_for_each_entry_safe() in this proposed patch for
>>>>> dm-snapshot: https://patchwork.kernel.org/patch/10835709/
>>>>
>>>> Probably should keep it, then.  ;-)
>>>>
>>>>>>>
>>>>>>> I don't believe that the WRITE_ONCE() is needed.  What am I missing?
>>>>>>>
>>>>>>> Other than that, looks good.
>>>>>>>
>>>>>>> 							Thanx, Paul
>>>>>>>
>>>>>>
>>>>>> I'd imagine it was just born out of symmetry with hlist_bl_add_before()
>>>>>> and/or caution.  But let's see what Nikos has to say.
>>>>>
>>>>> I also don't believe that this WRITE_SAME() is needed. But, looking at
>>>>> hlist_add_behind() in include/linux/list.h, which, if I am not missing
>>>>> something, is used in the same way as hlist_bl_add_behind(), it also
>>>>> uses WRITE_ONCE() to update prev->next:
>>>>>
>>>>> static inline void hlist_add_behind(struct hlist_node *n,
>>>>> 				    struct hlist_node *prev)
>>>>> {
>>>>> 	n->next = prev->next;
>>>>> 	WRITE_ONCE(prev->next, n);
>>>>> 	n->pprev = &prev->next;
>>>>>
>>>>> 	if (n->next)
>>>>> 		n->next->pprev  = &n->next;
>>>>> }
>>>>>
>>>>> Could it be the case that the WRITE_ONCE() in hlist_add_behind() is also
>>>>> not needed? This WRITE_ONCE() was introduced by commit 1c97be677f72b3
>>>>> ("list: Use WRITE_ONCE() when adding to lists and hlists").
>>>>
>>>> Looks like I have no one to blame but myself!
>>>>
>>>> Would you like to remove that as part of your patch series?
>>>>
>>>>> But, since I am not an expert in lockless programming, I opted to be on
>>>>> the safe side and followed the example of hlist_add_behind().
>>>>>
>>>>> That said, I will follow up with a new version of the patch removing the
>>>>> WRITE_ONCE() and using uintptr_t instead of unsigned long.
>>>>
>>>> Sounds good!
>>>
>>> Oh, and of course intptr_t is one character shorter than uintptr_t, and
>>> looks to work just as well in this context.  ;-)
>>>
>>> 							Thanx, Paul
>>>
>>
>>
>> Hi Paul,
>>
>> Sorry for the late reply.
>>
>> intptr_t seems to be defined only in a header file under arch/mips, so I
>> will stick to uintptr_t.
> 
> Ah, apologies for the misdirection!  Hmmm...  Maybe intptr_t should be
> added alongside uintptr_t?  Saving a character is saving a character.  ;-)
> 
> 							Thanx, Paul
> 

I will follow up with an unrelated patch to add intptr_t to
include/linux/types.h, so that it is available in subsequent patches
throughout the kernel.

Nikos

--
dm-devel mailing list
[e-mail]
https://www.redhat.com/mailman/listinfo/dm-devel

Patch

diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h
index 3fc2cc57ba1b..2fd918e5fd48 100644
--- a/include/linux/list_bl.h
+++ b/include/linux/list_bl.h
@@ -86,6 +86,33 @@  static inline void hlist_bl_add_head(struct hlist_bl_node *n,
 	hlist_bl_set_first(h, n);
 }
 
+static inline void hlist_bl_add_before(struct hlist_bl_node *n,
+				       struct hlist_bl_node *next)
+{
+	struct hlist_bl_node **pprev = next->pprev;
+
+	n->pprev = pprev;
+	n->next = next;
+	next->pprev = &n->next;
+
+	/* pprev may be `first`, so be careful not to lose the lock bit */
+	WRITE_ONCE(*pprev,
+		   (struct hlist_bl_node *)
+			((unsigned long)n |
+			 ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
+}
+
+static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
+				       struct hlist_bl_node *prev)
+{
+	n->next = prev->next;
+	n->pprev = &prev->next;
+	WRITE_ONCE(prev->next, n);
+
+	if (n->next)
+		n->next->pprev = &n->next;
+}
+
 static inline void __hlist_bl_del(struct hlist_bl_node *n)
 {
 	struct hlist_bl_node *next = n->next;