Documentation of locking needs when working with lists?

Documentation of locking needs when working with lists?

[Heiner Kallweit]

Even though lists are used everywhere, I was surprised not being able to find
documentation about which operations need locking, and which ones are safe
lock-less.

My case:
I have a list where the only operation is adding entries.
It's clear that adding entries has to be serialized.
Question is whether a list_for_each_entry is safe lock-less.

Looking at the code I *think* it's safe, under the precondition that
reading/writing pointers is atomic.

Any hint or documentation link would be appreciated. Thanks!

Re: Documentation of locking needs when working with lists?

[Greg Kroah-Hartman]

On Sat, May 10, 2025 at 10:46:32AM +0200, Heiner Kallweit wrote:
> Even though lists are used everywhere, I was surprised not being able to find
> documentation about which operations need locking, and which ones are safe
> lock-less.
> 
> My case:
> I have a list where the only operation is adding entries.
> It's clear that adding entries has to be serialized.
> Question is whether a list_for_each_entry is safe lock-less.
> 
> Looking at the code I *think* it's safe, under the precondition that
> reading/writing pointers is atomic.
> 
> Any hint or documentation link would be appreciated. Thanks!

You MUST have locking for your list if you have multiple processes
accessing it at the same time.

good luck!

greg k-h

Re: Documentation of locking needs when working with lists?

[Heiner Kallweit]

On 10.05.2025 15:20, Greg Kroah-Hartman wrote:
> On Sat, May 10, 2025 at 10:46:32AM +0200, Heiner Kallweit wrote:
>> Even though lists are used everywhere, I was surprised not being able to find
>> documentation about which operations need locking, and which ones are safe
>> lock-less.
>>
>> My case:
>> I have a list where the only operation is adding entries.
>> It's clear that adding entries has to be serialized.
>> Question is whether a list_for_each_entry is safe lock-less.
>>
>> Looking at the code I *think* it's safe, under the precondition that
>> reading/writing pointers is atomic.
>>
>> Any hint or documentation link would be appreciated. Thanks!
> 
> You MUST have locking for your list if you have multiple processes
> accessing it at the same time.
> 
Thanks. Sure, I need locking for the writers (list_add_tail).
Question is about the reader, list_for_each_entry.
Last step in list_add_tail() is WRITE_ONCE(prev->next, new);
list_next_entry() reads the "next" member of the iterator.

Therefore I think list_next_entry() always sees a consistent
state, either the old or the new value of the "next" pointer.
So I don't see a need for locking list_for_each_entry().

If there is such a need, I'd be interested in the potential
race scenario.

> good luck!
> 
> greg k-h

Re: Documentation of locking needs when working with lists?

[David Laight]

On Sat, 10 May 2025 10:46:32 +0200
Heiner Kallweit <hkallweit1@gmail.com> wrote:

> Even though lists are used everywhere, I was surprised not being able to find
> documentation about which operations need locking, and which ones are safe
> lock-less.
> 
> My case:
> I have a list where the only operation is adding entries.
> It's clear that adding entries has to be serialized.
> Question is whether a list_for_each_entry is safe lock-less.
> 
> Looking at the code I *think* it's safe, under the precondition that
> reading/writing pointers is atomic.
> 
> Any hint or documentation link would be appreciated. Thanks!
> 

Well, somewhere you must have code that destroys the list.
That must be locked against anything that traverses it ...

But if you have a singly linked list and keep a pointer to the last
entry in order to append entries then the list traversal code wont
explode.

However, on many architectures, you need memory sequencing instructions
to guarantee the list traversal code reads the expected contents of
newly added (or any other recently changed) items.
Read up on the semantics acquire and release operations.
Locks will give the required guarantee.

Most lockless lists in the kernel use 'rcu'.

	David