[QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

Hello folks,

I'm careful in saying.. and curious about..

In restrictive cases like only addtions happen but never deletion, can't
we safely traverse a llist? I believe llist can be more useful if we can
release the restriction. Can't we?

If yes, we may add another function traversing starting from a head. Or
just use existing funtion with head->first.

Thank a lot for your answers in advance :)

----->8-----
From 1e73882799b269cd86e7a7c955021e3a18d1e6cf Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park@lge.com>
Date: Tue, 31 Jul 2018 09:31:57 +0900
Subject: [QUESTION] llist: Comment releasing 'must delete' restriction before
 traversing

llist traversing can run without deletion in restrictive cases all
items are added but never deleted like a rculist traversing such as
list_for_each_entry_lockless. So add the comment.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/llist.h | 24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index 85abc29..d012d3e 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -32,8 +32,12 @@
  * operation, with "-" being no lock needed, while "L" being lock is needed.
  *
  * The list entries deleted via llist_del_all can be traversed with
- * traversing function such as llist_for_each etc.  But the list
- * entries can not be traversed safely before deleted from the list.
+ * traversing function such as llist_for_each etc.  Normally the list
+ * entries cannot be traversed safely before deleted from the list
+ * except the cases items are added to the list but never deleted.  In
+ * that restrictive cases the list may be safely traversed concurrently
+ * with llist_add.
+ *
  * The order of deleted entries is from the newest to the oldest added
  * one.  If you want to traverse from the oldest to the newest, you
  * must reverse the order by yourself before traversing.
@@ -116,7 +120,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being deleted from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
@@ -135,7 +141,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being deleted from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
@@ -153,7 +161,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being removed from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
@@ -175,7 +185,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being removed from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
-- 
1.9.1

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Huang, Ying]

Byungchul Park <byungchul.park@lge.com> writes:

> Hello folks,
>
> I'm careful in saying.. and curious about..
>
> In restrictive cases like only addtions happen but never deletion, can't
> we safely traverse a llist? I believe llist can be more useful if we can
> release the restriction. Can't we?
>
> If yes, we may add another function traversing starting from a head. Or
> just use existing funtion with head->first.
>
> Thank a lot for your answers in advance :)

What's the use case?  I don't know how it is useful that items are never
deleted from the llist.

Some other locks could be used to provide mutual exclusive between

- llist add, llist traverse

and

- llist delete

Is this your use case?

Best Regards,
Huang, Ying

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

On Tue, Jul 31, 2018 at 09:37:50AM +0800, Huang, Ying wrote:
> Byungchul Park <byungchul.park@lge.com> writes:
> 
> > Hello folks,
> >
> > I'm careful in saying.. and curious about..
> >
> > In restrictive cases like only addtions happen but never deletion, can't
> > we safely traverse a llist? I believe llist can be more useful if we can
> > release the restriction. Can't we?
> >
> > If yes, we may add another function traversing starting from a head. Or
> > just use existing funtion with head->first.
> >
> > Thank a lot for your answers in advance :)
> 
> What's the use case?  I don't know how it is useful that items are never
> deleted from the llist.
> 
> Some other locks could be used to provide mutual exclusive between
> 
> - llist add, llist traverse

Hello Huang,

In my use case, I only do adding and traversing on a llist.

> 
> and
> 
> - llist delete

Of course, I will use a lock when deletion is needed.

So.. in the case only adding into and traversing a llist is needed,
can't we safely traverse a llist in the way I thought? Or am I missing
something?

Thank you.

> Is this your use case?
> 
> Best Regards,
> Huang, Ying

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Huang, Ying]

Byungchul Park <byungchul.park@lge.com> writes:

> On Tue, Jul 31, 2018 at 09:37:50AM +0800, Huang, Ying wrote:
>> Byungchul Park <byungchul.park@lge.com> writes:
>> 
>> > Hello folks,
>> >
>> > I'm careful in saying.. and curious about..
>> >
>> > In restrictive cases like only addtions happen but never deletion, can't
>> > we safely traverse a llist? I believe llist can be more useful if we can
>> > release the restriction. Can't we?
>> >
>> > If yes, we may add another function traversing starting from a head. Or
>> > just use existing funtion with head->first.
>> >
>> > Thank a lot for your answers in advance :)
>> 
>> What's the use case?  I don't know how it is useful that items are never
>> deleted from the llist.
>> 
>> Some other locks could be used to provide mutual exclusive between
>> 
>> - llist add, llist traverse
>
> Hello Huang,

Hello Byungchul,

> In my use case, I only do adding and traversing on a llist.

Can you provide more details about your use case?

Best Regards,
Huang, Ying

>> 
>> and
>> 
>> - llist delete
>
> Of course, I will use a lock when deletion is needed.
>
> So.. in the case only adding into and traversing a llist is needed,
> can't we safely traverse a llist in the way I thought? Or am I missing
> something?
>
> Thank you.
>
>> Is this your use case?
>> 
>> Best Regards,
>> Huang, Ying

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Paul E. McKenney]

On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:
> Hello folks,
> 
> I'm careful in saying.. and curious about..
> 
> In restrictive cases like only addtions happen but never deletion, can't
> we safely traverse a llist? I believe llist can be more useful if we can
> release the restriction. Can't we?

Yes, but please give a thought to the people looking at your code some
time down the line.  If you are doing this, lots of comments, please.

Here are the approaches that I am aware of:

1.	Normal RCU.  Use list_add_rcu(), list_del_rcu(), and friends.

2.	Things are added but never deleted.  Use list_add_rcu() and
	friends, but since you don't ever delete anything, you never
	use list_del_rcu(), synchronize_rcu(), call_rcu(), and friends.

3.	Things are added, but deletion deletes the entire list.
	You need to use something like list_del_rcu() to handle
	this, and you need synchronize_rcu(), call_rcu(), and friends.
	So really not all that much different than #1.

4.	Things are added, but deletions happen during some sort of
	maintenance phase during which there are no readers.  This is
	really easy to get wrong -- all you have to do is let one little
	reader slip in and all is broken.  Also the maintenance phases
	often take longer than planned.  (We used a trick somewhat
	like this back when I worked on the dormitory system back at
	university the first time around, but we had the advantage of
	everyone using the system being in the same timezone and
	the system being taken down every night anyway.)

5.	Just mark the deleted elements, but leave them in the list.
	Actually remove them using one of the above techniques.

There are probably others, but those come to mind immediately.

I suggest that such special cases stay in the subsystem in question.
If a given technique gains wider use, then it might be time to
update header comments.

> If yes, we may add another function traversing starting from a head. Or
> just use existing funtion with head->first.

If you start with head->first, then you need to make sure that a concurrent
add of an element at the head of the list works.  You need at least a
READ_ONCE() and preferably an rcu_dereference() or similar.

> Thank a lot for your answers in advance :)

You did ask!

							Thanx, Paul

> ----->8-----
> >From 1e73882799b269cd86e7a7c955021e3a18d1e6cf Mon Sep 17 00:00:00 2001
> From: Byungchul Park <byungchul.park@lge.com>
> Date: Tue, 31 Jul 2018 09:31:57 +0900
> Subject: [QUESTION] llist: Comment releasing 'must delete' restriction before
>  traversing
> 
> llist traversing can run without deletion in restrictive cases all
> items are added but never deleted like a rculist traversing such as
> list_for_each_entry_lockless. So add the comment.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  include/linux/llist.h | 24 ++++++++++++++++++------
>  1 file changed, 18 insertions(+), 6 deletions(-)
> 
> diff --git a/include/linux/llist.h b/include/linux/llist.h
> index 85abc29..d012d3e 100644
> --- a/include/linux/llist.h
> +++ b/include/linux/llist.h
> @@ -32,8 +32,12 @@
>   * operation, with "-" being no lock needed, while "L" being lock is needed.
>   *
>   * The list entries deleted via llist_del_all can be traversed with
> - * traversing function such as llist_for_each etc.  But the list
> - * entries can not be traversed safely before deleted from the list.
> + * traversing function such as llist_for_each etc.  Normally the list
> + * entries cannot be traversed safely before deleted from the list
> + * except the cases items are added to the list but never deleted.  In
> + * that restrictive cases the list may be safely traversed concurrently
> + * with llist_add.
> + *
>   * The order of deleted entries is from the newest to the oldest added
>   * one.  If you want to traverse from the oldest to the newest, you
>   * must reverse the order by yourself before traversing.
> @@ -116,7 +120,9 @@ static inline void init_llist_head(struct llist_head *list)
>   *
>   * In general, some entries of the lock-less list can be traversed
>   * safely only after being deleted from list, so start with an entry
> - * instead of list head.
> + * instead of list head.  But in restrictive cases items are added to
> + * the list but never deleted, the list may be safely traversed
> + * concurrently with llist_add.
>   *
>   * If being used on entries deleted from lock-less list directly, the
>   * traverse order is from the newest to the oldest added entry.  If
> @@ -135,7 +141,9 @@ static inline void init_llist_head(struct llist_head *list)
>   *
>   * In general, some entries of the lock-less list can be traversed
>   * safely only after being deleted from list, so start with an entry
> - * instead of list head.
> + * instead of list head.  But in restrictive cases items are added to
> + * the list but never deleted, the list may be safely traversed
> + * concurrently with llist_add.
>   *
>   * If being used on entries deleted from lock-less list directly, the
>   * traverse order is from the newest to the oldest added entry.  If
> @@ -153,7 +161,9 @@ static inline void init_llist_head(struct llist_head *list)
>   *
>   * In general, some entries of the lock-less list can be traversed
>   * safely only after being removed from list, so start with an entry
> - * instead of list head.
> + * instead of list head.  But in restrictive cases items are added to
> + * the list but never deleted, the list may be safely traversed
> + * concurrently with llist_add.
>   *
>   * If being used on entries deleted from lock-less list directly, the
>   * traverse order is from the newest to the oldest added entry.  If
> @@ -175,7 +185,9 @@ static inline void init_llist_head(struct llist_head *list)
>   *
>   * In general, some entries of the lock-less list can be traversed
>   * safely only after being removed from list, so start with an entry
> - * instead of list head.
> + * instead of list head.  But in restrictive cases items are added to
> + * the list but never deleted, the list may be safely traversed
> + * concurrently with llist_add.
>   *
>   * If being used on entries deleted from lock-less list directly, the
>   * traverse order is from the newest to the oldest added entry.  If
> -- 
> 1.9.1
> 

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

On Mon, Jul 30, 2018 at 09:30:42PM -0700, Paul E. McKenney wrote:
> On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:
> > Hello folks,
> > 
> > I'm careful in saying.. and curious about..
> > 
> > In restrictive cases like only addtions happen but never deletion, can't
> > we safely traverse a llist? I believe llist can be more useful if we can
> > release the restriction. Can't we?
> 
> Yes, but please give a thought to the people looking at your code some
> time down the line.  If you are doing this, lots of comments, please.

Yes, I will. Thank you for the comment.

> Here are the approaches that I am aware of:
> 
> 1.	Normal RCU.  Use list_add_rcu(), list_del_rcu(), and friends.
> 
> 2.	Things are added but never deleted.  Use list_add_rcu() and
> 	friends, but since you don't ever delete anything, you never
> 	use list_del_rcu(), synchronize_rcu(), call_rcu(), and friends.

I think rcu list also works well. But I decided to use llist because
llist is simpler and has one less pointer.

Just to be sure, let me explain my use case more:

   1. Introduced a global list where single linked list is sufficient.
   2. All operations I need is to add items and traverse the list.
   3. Ensure the operations always happen within irq-disabled section.
   4. I'm considering CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG properly.
   5. The list can be accessed by every CPU concurrently.

Of course, I can use normal double list with a lock or rcu list. But I
think it doesn't have to be protected by even rcu in that case. I wanted
to use the simplest one all requiremnets are satisfied with and I
thought it's llist. Thoughts?

> 5.	Just mark the deleted elements, but leave them in the list.
> 	Actually remove them using one of the above techniques.

Honestly, I have a plan to do this thing as a future work. But now, I
can assume deletion never happen with the list :)

> I suggest that such special cases stay in the subsystem in question.
> If a given technique gains wider use, then it might be time to
> update header comments.

Ok.

> > If yes, we may add another function traversing starting from a head. Or
> > just use existing funtion with head->first.
> 
> If you start with head->first, then you need to make sure that a concurrent
> add of an element at the head of the list works.  You need at least a
> READ_ONCE() and preferably an rcu_dereference() or similar.

Yes, sir. I'll be careful in doing it.

Thanks a lot.

> > Thank a lot for your answers in advance :)
> 
> You did ask!
> 
> 							Thanx, Paul
> 
> > ----->8-----
> > >From 1e73882799b269cd86e7a7c955021e3a18d1e6cf Mon Sep 17 00:00:00 2001
> > From: Byungchul Park <byungchul.park@lge.com>
> > Date: Tue, 31 Jul 2018 09:31:57 +0900
> > Subject: [QUESTION] llist: Comment releasing 'must delete' restriction before
> >  traversing
> > 
> > llist traversing can run without deletion in restrictive cases all
> > items are added but never deleted like a rculist traversing such as
> > list_for_each_entry_lockless. So add the comment.
> > 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  include/linux/llist.h | 24 ++++++++++++++++++------
> >  1 file changed, 18 insertions(+), 6 deletions(-)
> > 
> > diff --git a/include/linux/llist.h b/include/linux/llist.h
> > index 85abc29..d012d3e 100644
> > --- a/include/linux/llist.h
> > +++ b/include/linux/llist.h
> > @@ -32,8 +32,12 @@
> >   * operation, with "-" being no lock needed, while "L" being lock is needed.
> >   *
> >   * The list entries deleted via llist_del_all can be traversed with
> > - * traversing function such as llist_for_each etc.  But the list
> > - * entries can not be traversed safely before deleted from the list.
> > + * traversing function such as llist_for_each etc.  Normally the list
> > + * entries cannot be traversed safely before deleted from the list
> > + * except the cases items are added to the list but never deleted.  In
> > + * that restrictive cases the list may be safely traversed concurrently
> > + * with llist_add.
> > + *
> >   * The order of deleted entries is from the newest to the oldest added
> >   * one.  If you want to traverse from the oldest to the newest, you
> >   * must reverse the order by yourself before traversing.
> > @@ -116,7 +120,9 @@ static inline void init_llist_head(struct llist_head *list)
> >   *
> >   * In general, some entries of the lock-less list can be traversed
> >   * safely only after being deleted from list, so start with an entry
> > - * instead of list head.
> > + * instead of list head.  But in restrictive cases items are added to
> > + * the list but never deleted, the list may be safely traversed
> > + * concurrently with llist_add.
> >   *
> >   * If being used on entries deleted from lock-less list directly, the
> >   * traverse order is from the newest to the oldest added entry.  If
> > @@ -135,7 +141,9 @@ static inline void init_llist_head(struct llist_head *list)
> >   *
> >   * In general, some entries of the lock-less list can be traversed
> >   * safely only after being deleted from list, so start with an entry
> > - * instead of list head.
> > + * instead of list head.  But in restrictive cases items are added to
> > + * the list but never deleted, the list may be safely traversed
> > + * concurrently with llist_add.
> >   *
> >   * If being used on entries deleted from lock-less list directly, the
> >   * traverse order is from the newest to the oldest added entry.  If
> > @@ -153,7 +161,9 @@ static inline void init_llist_head(struct llist_head *list)
> >   *
> >   * In general, some entries of the lock-less list can be traversed
> >   * safely only after being removed from list, so start with an entry
> > - * instead of list head.
> > + * instead of list head.  But in restrictive cases items are added to
> > + * the list but never deleted, the list may be safely traversed
> > + * concurrently with llist_add.
> >   *
> >   * If being used on entries deleted from lock-less list directly, the
> >   * traverse order is from the newest to the oldest added entry.  If
> > @@ -175,7 +185,9 @@ static inline void init_llist_head(struct llist_head *list)
> >   *
> >   * In general, some entries of the lock-less list can be traversed
> >   * safely only after being removed from list, so start with an entry
> > - * instead of list head.
> > + * instead of list head.  But in restrictive cases items are added to
> > + * the list but never deleted, the list may be safely traversed
> > + * concurrently with llist_add.
> >   *
> >   * If being used on entries deleted from lock-less list directly, the
> >   * traverse order is from the newest to the oldest added entry.  If
> > -- 
> > 1.9.1
> > 

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Paul E. McKenney]

On Tue, Jul 31, 2018 at 06:29:50PM +0900, Byungchul Park wrote:
> On Mon, Jul 30, 2018 at 09:30:42PM -0700, Paul E. McKenney wrote:
> > On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:
> > > Hello folks,
> > > 
> > > I'm careful in saying.. and curious about..
> > > 
> > > In restrictive cases like only addtions happen but never deletion, can't
> > > we safely traverse a llist? I believe llist can be more useful if we can
> > > release the restriction. Can't we?
> > 
> > Yes, but please give a thought to the people looking at your code some
> > time down the line.  If you are doing this, lots of comments, please.
> 
> Yes, I will. Thank you for the comment.
> 
> > Here are the approaches that I am aware of:
> > 
> > 1.	Normal RCU.  Use list_add_rcu(), list_del_rcu(), and friends.
> > 
> > 2.	Things are added but never deleted.  Use list_add_rcu() and
> > 	friends, but since you don't ever delete anything, you never
> > 	use list_del_rcu(), synchronize_rcu(), call_rcu(), and friends.
> 
> I think rcu list also works well. But I decided to use llist because
> llist is simpler and has one less pointer.

No.

To see this, look at llist_for_each() below, which is absolutely -not-
able to reliably traverse lists while nodes are being inserted.

#define llist_for_each(pos, node)			\
	for ((pos) = (node); pos; (pos) = (pos)->next)

Now, you could introduce an llist_for_each_rcu() that used rcu_dereference
or similar (thus handling insertion, but that is not what your patches
currently do.

> Just to be sure, let me explain my use case more:
> 
>    1. Introduced a global list where single linked list is sufficient.
>    2. All operations I need is to add items and traverse the list.
>    3. Ensure the operations always happen within irq-disabled section.
>    4. I'm considering CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG properly.
>    5. The list can be accessed by every CPU concurrently.
> 
> Of course, I can use normal double list with a lock or rcu list. But I
> think it doesn't have to be protected by even rcu in that case. I wanted
> to use the simplest one all requiremnets are satisfied with and I
> thought it's llist. Thoughts?

If you want lockless reader traversal, you need rcu_dereference().

> > 5.	Just mark the deleted elements, but leave them in the list.
> > 	Actually remove them using one of the above techniques.
> 
> Honestly, I have a plan to do this thing as a future work. But now, I
> can assume deletion never happen with the list :)
> 
> > I suggest that such special cases stay in the subsystem in question.
> > If a given technique gains wider use, then it might be time to
> > update header comments.
> 
> Ok.
> 
> > > If yes, we may add another function traversing starting from a head. Or
> > > just use existing funtion with head->first.
> > 
> > If you start with head->first, then you need to make sure that a concurrent
> > add of an element at the head of the list works.  You need at least a
> > READ_ONCE() and preferably an rcu_dereference() or similar.
> 
> Yes, sir. I'll be careful in doing it.

Which means adding something to the current llist.h.

							Thanx, Paul

> Thanks a lot.
> 
> > > Thank a lot for your answers in advance :)
> > 
> > You did ask!
> > 
> > 							Thanx, Paul
> > 
> > > ----->8-----
> > > >From 1e73882799b269cd86e7a7c955021e3a18d1e6cf Mon Sep 17 00:00:00 2001
> > > From: Byungchul Park <byungchul.park@lge.com>
> > > Date: Tue, 31 Jul 2018 09:31:57 +0900
> > > Subject: [QUESTION] llist: Comment releasing 'must delete' restriction before
> > >  traversing
> > > 
> > > llist traversing can run without deletion in restrictive cases all
> > > items are added but never deleted like a rculist traversing such as
> > > list_for_each_entry_lockless. So add the comment.
> > > 
> > > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > > ---
> > >  include/linux/llist.h | 24 ++++++++++++++++++------
> > >  1 file changed, 18 insertions(+), 6 deletions(-)
> > > 
> > > diff --git a/include/linux/llist.h b/include/linux/llist.h
> > > index 85abc29..d012d3e 100644
> > > --- a/include/linux/llist.h
> > > +++ b/include/linux/llist.h
> > > @@ -32,8 +32,12 @@
> > >   * operation, with "-" being no lock needed, while "L" being lock is needed.
> > >   *
> > >   * The list entries deleted via llist_del_all can be traversed with
> > > - * traversing function such as llist_for_each etc.  But the list
> > > - * entries can not be traversed safely before deleted from the list.
> > > + * traversing function such as llist_for_each etc.  Normally the list
> > > + * entries cannot be traversed safely before deleted from the list
> > > + * except the cases items are added to the list but never deleted.  In
> > > + * that restrictive cases the list may be safely traversed concurrently
> > > + * with llist_add.
> > > + *
> > >   * The order of deleted entries is from the newest to the oldest added
> > >   * one.  If you want to traverse from the oldest to the newest, you
> > >   * must reverse the order by yourself before traversing.
> > > @@ -116,7 +120,9 @@ static inline void init_llist_head(struct llist_head *list)
> > >   *
> > >   * In general, some entries of the lock-less list can be traversed
> > >   * safely only after being deleted from list, so start with an entry
> > > - * instead of list head.
> > > + * instead of list head.  But in restrictive cases items are added to
> > > + * the list but never deleted, the list may be safely traversed
> > > + * concurrently with llist_add.
> > >   *
> > >   * If being used on entries deleted from lock-less list directly, the
> > >   * traverse order is from the newest to the oldest added entry.  If
> > > @@ -135,7 +141,9 @@ static inline void init_llist_head(struct llist_head *list)
> > >   *
> > >   * In general, some entries of the lock-less list can be traversed
> > >   * safely only after being deleted from list, so start with an entry
> > > - * instead of list head.
> > > + * instead of list head.  But in restrictive cases items are added to
> > > + * the list but never deleted, the list may be safely traversed
> > > + * concurrently with llist_add.
> > >   *
> > >   * If being used on entries deleted from lock-less list directly, the
> > >   * traverse order is from the newest to the oldest added entry.  If
> > > @@ -153,7 +161,9 @@ static inline void init_llist_head(struct llist_head *list)
> > >   *
> > >   * In general, some entries of the lock-less list can be traversed
> > >   * safely only after being removed from list, so start with an entry
> > > - * instead of list head.
> > > + * instead of list head.  But in restrictive cases items are added to
> > > + * the list but never deleted, the list may be safely traversed
> > > + * concurrently with llist_add.
> > >   *
> > >   * If being used on entries deleted from lock-less list directly, the
> > >   * traverse order is from the newest to the oldest added entry.  If
> > > @@ -175,7 +185,9 @@ static inline void init_llist_head(struct llist_head *list)
> > >   *
> > >   * In general, some entries of the lock-less list can be traversed
> > >   * safely only after being removed from list, so start with an entry
> > > - * instead of list head.
> > > + * instead of list head.  But in restrictive cases items are added to
> > > + * the list but never deleted, the list may be safely traversed
> > > + * concurrently with llist_add.
> > >   *
> > >   * If being used on entries deleted from lock-less list directly, the
> > >   * traverse order is from the newest to the oldest added entry.  If
> > > -- 
> > > 1.9.1
> > > 
> 

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

On Tue, Jul 31, 2018 at 07:30:52AM -0700, Paul E. McKenney wrote:
> On Tue, Jul 31, 2018 at 06:29:50PM +0900, Byungchul Park wrote:
> > On Mon, Jul 30, 2018 at 09:30:42PM -0700, Paul E. McKenney wrote:
> > > On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:
> > > > Hello folks,
> > > > 
> > > > I'm careful in saying.. and curious about..
> > > > 
> > > > In restrictive cases like only addtions happen but never deletion, can't
> > > > we safely traverse a llist? I believe llist can be more useful if we can
> > > > release the restriction. Can't we?
> > > 
> > > Yes, but please give a thought to the people looking at your code some
> > > time down the line.  If you are doing this, lots of comments, please.
> > 
> > Yes, I will. Thank you for the comment.
> > 
> > > Here are the approaches that I am aware of:
> > > 
> > > 1.	Normal RCU.  Use list_add_rcu(), list_del_rcu(), and friends.
> > > 
> > > 2.	Things are added but never deleted.  Use list_add_rcu() and
> > > 	friends, but since you don't ever delete anything, you never
> > > 	use list_del_rcu(), synchronize_rcu(), call_rcu(), and friends.
> > 
> > I think rcu list also works well. But I decided to use llist because
> > llist is simpler and has one less pointer.
> 
> No.
> 
> To see this, look at llist_for_each() below, which is absolutely -not-
> able to reliably traverse lists while nodes are being inserted.

Ah.. Not only 'node' but also 'pos->next' can cause a problem w/o
rcu_dereference or similar.. I need consider another way.

Or I might need memory barrier between READ_ONCE(head->first) and
llist_for_each() to make sure safely to read 'pos->next' when I see
a value of 'head->first'.

> #define llist_for_each(pos, node)			\
> 	for ((pos) = (node); pos; (pos) = (pos)->next)
> 
> Now, you could introduce an llist_for_each_rcu() that used rcu_dereference
> or similar (thus handling insertion, but that is not what your patches
> currently do.

Right.

> > Just to be sure, let me explain my use case more:
> > 
> >    1. Introduced a global list where single linked list is sufficient.
> >    2. All operations I need is to add items and traverse the list.
> >    3. Ensure the operations always happen within irq-disabled section.
> >    4. I'm considering CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG properly.
> >    5. The list can be accessed by every CPU concurrently.
> > 
> > Of course, I can use normal double list with a lock or rcu list. But I
> > think it doesn't have to be protected by even rcu in that case. I wanted
> > to use the simplest one all requiremnets are satisfied with and I
> > thought it's llist. Thoughts?
> 
> If you want lockless reader traversal, you need rcu_dereference().

Yes, I need that or similar anyway.

Thanks a lot, Paul!

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Huang, Ying]

Byungchul Park <byungchul.park@lge.com> writes:

> I think rcu list also works well. But I decided to use llist because
> llist is simpler and has one less pointer.
>
> Just to be sure, let me explain my use case more:
>
>    1. Introduced a global list where single linked list is sufficient.
>    2. All operations I need is to add items and traverse the list.
>    3. Ensure the operations always happen within irq-disabled section.
>    4. I'm considering CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG properly.
>    5. The list can be accessed by every CPU concurrently.
>

Can you provide more information about where is your use case?  Is it a
kernel driver?  Then it is better to submit the patch together with its
user.

And I have the similar concern as Steven Rostedt.  That is, if you are
the only user forever, it's not necessary to change the common code.

Best Regards,
Huang, Ying

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

On Wed, Aug 01, 2018 at 01:43:10PM +0800, Huang, Ying wrote:
> Byungchul Park <byungchul.park@lge.com> writes:
> 
> > I think rcu list also works well. But I decided to use llist because
> > llist is simpler and has one less pointer.
> >
> > Just to be sure, let me explain my use case more:
> >
> >    1. Introduced a global list where single linked list is sufficient.
> >    2. All operations I need is to add items and traverse the list.
> >    3. Ensure the operations always happen within irq-disabled section.
> >    4. I'm considering CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG properly.
> >    5. The list can be accessed by every CPU concurrently.
> >
> 
> Can you provide more information about where is your use case?  Is it a
> kernel driver?  Then it is better to submit the patch together with its
> user.
> 
> And I have the similar concern as Steven Rostedt.  That is, if you are
> the only user forever, it's not necessary to change the common code.

I'm sorry the patch is too complicated and premature to share at the
moment so I don't know how to extract only what you're asking me for.

Thanks anyway. The common code doesn't have to be changed then.

> Best Regards,
> Huang, Ying

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Peter Zijlstra]

On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:
> In restrictive cases like only addtions happen but never deletion, can't
> we safely traverse a llist? I believe llist can be more useful if we can
> release the restriction. Can't we?

Yes you can, but I'm not sure it makes much sense to confuse the
comments with this.

This really ends up in the 'you had better know what you're doing'
category.

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

On Tue, Jul 31, 2018 at 10:52:57AM +0200, Peter Zijlstra wrote:
> On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:
> > In restrictive cases like only addtions happen but never deletion, can't
> > we safely traverse a llist? I believe llist can be more useful if we can
> > release the restriction. Can't we?
> 
> Yes you can, but I'm not sure it makes much sense to confuse the
> comments with this.
> 
> This really ends up in the 'you had better know what you're doing'
> category.

Partially agree with you. But why not add more explanation?

If you think the comment confuse us, then it's ok to keep it itself.

Thanks.

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Steven Rostedt]

On Tue, 31 Jul 2018 18:38:09 +0900
Byungchul Park <byungchul.park@lge.com> wrote:

> On Tue, Jul 31, 2018 at 10:52:57AM +0200, Peter Zijlstra wrote:
> > On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:  
> > > In restrictive cases like only addtions happen but never deletion, can't
> > > we safely traverse a llist? I believe llist can be more useful if we can
> > > release the restriction. Can't we?  
> > 
> > Yes you can, but I'm not sure it makes much sense to confuse the
> > comments with this.
> > 
> > This really ends up in the 'you had better know what you're doing'
> > category.  
> 
> Partially agree with you. But why not add more explanation?
> 
> If you think the comment confuse us, then it's ok to keep it itself.
> 

It appears that you will only have your own users that will be doing
this, correct? How many use cases have no deletion? I wouldn't change
the generic comments on llist for something that's a one off and hardly
used.

-- Steve

Re: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

[Byungchul Park]

On Tue, Jul 31, 2018 at 09:46:16AM -0400, Steven Rostedt wrote:
> On Tue, 31 Jul 2018 18:38:09 +0900
> Byungchul Park <byungchul.park@lge.com> wrote:
> 
> > On Tue, Jul 31, 2018 at 10:52:57AM +0200, Peter Zijlstra wrote:
> > > On Tue, Jul 31, 2018 at 09:58:36AM +0900, Byungchul Park wrote:  
> > > > In restrictive cases like only addtions happen but never deletion, can't
> > > > we safely traverse a llist? I believe llist can be more useful if we can
> > > > release the restriction. Can't we?  
> > > 
> > > Yes you can, but I'm not sure it makes much sense to confuse the
> > > comments with this.
> > > 
> > > This really ends up in the 'you had better know what you're doing'
> > > category.  
> > 
> > Partially agree with you. But why not add more explanation?
> > 
> > If you think the comment confuse us, then it's ok to keep it itself.
> > 
> 
> It appears that you will only have your own users that will be doing
> this, correct? How many use cases have no deletion? I wouldn't change
> the generic comments on llist for something that's a one off and hardly
> used.

Thanks for the comment. OK.

> -- Steve