Add a documentation for JobSupport.addLastAtomic

[qwwdfsad]

• Document internal invariants
• Add memory footprint test
• This explanation can be used to reasonably review follow-up PR that gets rid of addLastIf

[qwwdfsad]

@dkhalanskyjb while you are here, here is the rough outline of the migration plan that minimizes the impact on the codebase (e.g. we don't have to rewrite everything in JobSupport), and helps us to get rid of DCSS, pave a road towards concurrent linked list without doing a lot of redundant work:

• Provide a concept of "closing" the list. Luckily, we already have that (addLastIfPrev in previous versions, currently removed), it's local (i.e. operation affects only the list itself and not the memory locations around) and battle-tested, this is basically how old channels were implemented
• Finalization of the job state (figuring the precise definition is the trick here. TL;DR currently it's when DCSS fails) is now a multi-step operation:
  • Close the list with the new state (e.g. node Closed(newProposedState))
  • Update the state
  • Any observer of the list's tail (e.g. the caller of invokeOfCompletion) first helps with the state (list: [xs] :: Closed(newProposedState) -> newProposedState) and only then launches their operation
• Now we can safely remove DCSS from the codebase and have a more "local" reasoning about job states.
• Provide the same concept of closing to ConcurrentLinkedList and seamlessly migrate

The second step is the trickiest one and other is a chance it won't work out, so any critique is welcomed

[qwwdfsad]

@dkhalanskyjb I see, thanks for the trace. It seems like the root of the problem is that we can update the state without actually touching the tail of the list (or without touching the list whatsoever), creating a race. Seems like concurrent helping has to be performed unconditionally

[dkhalanskyjb]

I don't understand how this can be achieved in a data-race-free manner and without blocking synchronization. If you mean double-checking whether the list is closed after updating the state, almost the same interleaving is possible, only cancellation should happen in a third thread instead. The same non-linearizable outputs are still possible if the third thread gets preempted before it starts the helping.

On Fri, Oct 20, 2023 at 6:04 PM Vsevolod Tolstopyatov < @.***> wrote:

@dkhalanskyjb https://github.com/dkhalanskyjb I see, thanks for the trace. It seems like the root of the problem is that we can update the state without actually touching the tail of the list (or without touching the list whatsoever), creating a race. Seems like concurrent helping has to be performed unconditionally

— Reply to this email directly, view it on GitHub https://github.com/Kotlin/kotlinx.coroutines/pull/3892#issuecomment-1773007393, or unsubscribe https://github.com/notifications/unsubscribe-auth/AMT73TJH7Z47I7FDYQ5UR7DYAKOHTAVCNFSM6AAAAAA46N66LWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTONZTGAYDOMZZGM . You are receiving this because you were mentioned.Message ID: @.***>

[dkhalanskyjb]

There's a scheme for finalization I have far more faith in. It's similar to how DCSS behaves now but without the overly general consensus mechanism:

• First, update the state to ListClosingInProgress(new state) (which is not Incomplete). The state is the sole source of truth; the other memory locations are (potentially outdated) reflections of it.
• Anyone who sees this state (including the one who initially set it) must attempt to close the list (without any special markers).
• Anyone who knows that the list is closed (including the one who initially closed it) must attempt to update the state to new state. The operation that succeeds is responsible for the finalization: notifying everyone on the list, etc.

In essence, ListClosingInProgress(new state) behaves exactly like new state, except it imposes some cleanup work on other operations.

If an operation successfully appends to the list, this must have happened before the finalization, as we have an event ordering updating the list -> closing the list -> sending out notifications. In particular, this approach would fix #3893: there's no way for notifications not to be sent to some newly added element.