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.p...@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.p...@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
> > >
>
