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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 




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




[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Security]     [Bugtraq]     [Linux OMAP]     [Linux MIPS]     [eCos]     [Asterisk Internet PBX]     [Linux API]     [Monitors]

  Powered by Linux