Re: [PATCH v7 1/3] llist: Add a lock-less list variant terminated by a sentinel node

[Waiman Long]

On 10/3/22 12:40, Tejun Heo wrote:
> Hello, Waiman.
>
> On Mon, Oct 03, 2022 at 11:44:57AM -0400, Waiman Long wrote:
> > The lock-less list API is useful for dealing with list in a lock-less
> > manner. However, one of the drawback of the current API is that there
> > is not an easy way to determine if an entry has already been put into a
> > lock-less list. This has to be tracked externally and the tracking will
> > not be atomic unless some external synchronization logic is in place.
> >
> > This patch introduces a new variant of the lock-less list terminated
> > by a sentinel node instead of by NULL. The function names start with
> > "sllist" instead of "llist". The advantage of this scheme is that we
> > can atomically determine if an entry has been put into a lock-less
> > list by looking at the next pointer of the llist_node. Of course, the
> > callers must clear the next pointer when an entry is removed from the
> > lockless list. This is done automatically when the sllist_for_each_safe
> > or sllist_for_each_entry_safe iteraters are used. The non-safe versions
> > of sllist iterator are not provided.
> Any chance we can add sentinel to the existing llist instead of creating a
> new variant? There's no real downside to always using sentinel, right?

That was my original plan. However, after looking at some existing users 
of lockless list, they have coded in the dependency on the fact that a 
lockless list is empty if it is NULL. I guess I can make this true also 
for the new lockless list with sentinel at the expense of a bit more 
overhead in the entry insertion path and deletion path. I will take a 
further look at that.

Cheers,
Longman