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