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@xxxxxxx>
> > 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@xxxxxxx>
> > ---
> >  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
> >