GetOrSet race?

[aathan]

As I understand it golang's preemption model is that a goroutine may be interrupted either at "wait" boundaries (such as locks, sleeps) & when making system calls, or at function call boundaries where the stack may increase. In other words, the preemption model does allow for preemption between golang statements involving a function call.

Therefore, this code in GetOrSet() contains a race, no?

		if elem.key == key && !elem.isDeleted() {
			actual, loaded = *elem.value.Load(), true

Is your thinking that the race is of no consequence in a concurrent map because it would be no worse, in that case, than in the alternative, having scheduled the Set prior to the delete implicated in the race?

[alphadose]

@aathan those functions elem.isDeleted() and elem.value.Load are inlined by the golang compiler which can be verified with -gcflags="-m"
Furthermore, they are atomic instructions hence the compiler reduces them to atomic Load assembly instructions depending on the CPU architecture.
As they are now pure assembly, the golang runtime is not involved at all hence there is no scope of preemption in this case.

[aathan]

Ok. So they execute without interruption based on the language's current preemption model. My reading on that topic indicated that some function calls may involve cooperative preemption checks, so I thought I should ask given that the language also does not have a way to ensure at the call-site that no pre-emption will occur. I've not yet read the std lib code as a way of educating myself about this idiom, but would you say this sort of thing is a common idiom in go? What's the rule of thumb on the size of the called function, regarding whether a call may be preempted?

If there is a definitive guide for go's 1.18+ preemption model that'd be great. I'm not quite clear on how the underlying os threads are prevented from causing inter-goroutine preemptions despite this goroutine not returning to the golang scheduled between those function calls. After all, if two racing goroutines have already been scheduled, wouldn't the scheduling relationship you're relying upon be violated?

[alphadose]

@aathan a goroutine is generally preempted if it runs for more than 10ms or if a system call is involved. You can force a preemption too with runtime.Gosched(). Here is a great blog explaining the same https://medium.com/a-journey-with-go/go-goroutine-and-preemption-d6bc2aa2f4b7.

Also one goroutine cannot preempt another. All goroutines are managed by a special goroutine called g0 which is the main scheduler.

After all, if two racing goroutines have already been scheduled, wouldn't the scheduling relationship you're relying upon be violated?

Yes this is why race condition occurs and its the fault of the user not the runtime itself

[aathan]

Sure. I've written lightweight userland schedulers in a number of different contexts before; so, I'm just checking that I fully understand anything special go may be doing.

	for elem := existing; elem != nil && elem.keyHash <= h; elem = elem.nextPtr.Load() {
		if elem.key == key && !elem.isDeleted() {
		// HERE
			actual, loaded = *elem.value.Load(), true
			return
		}
	}

based on this, if two goroutines have been scheduled and they are running in separate os threads, nothing guarantees that one goroutine won't set elem.isDeleted()==true between where you check it, and where you load/return elem.value.

That is why I asked "Is your thinking that the race is of no consequence in a concurrent map because it would be no worse, in that case, than in the alternative, having scheduled the Set prior to the delete implicated in the race?"

There is in fact a race, and you may in fact be returning a deleted value, but that's no worse than the caller having called GetOrSet() a bit earlier such that it would have executed just prior to the racing delete...
... if, however, the guarantee you're trying to preserve is that all readers that run after a writer will see the same value, that won't be true in this code. The memory barrier that sets the element deleted may occur prior to returning the deleted value, but the caller will nevertheless see the deleted value.

Again, this may be of no consequence given the concurrent nature of the data structure, but it seems to be a nuanced difference from the guarantees provided by sync.Mutex?

[alphadose]

@aathan that reasoning is absolutely correct. Delete is done via an atomic Store and checked via a Load, so if in between the two instructions (elem.isDeleted and elem.value.Load), it might very well be possible that the element is marked deleted but the function still chooses to load the value and return true. Also golang follows memory_order_relaxed in atomic operations hence there are no write barriers to guarantee reads only happens after a write.

Again, this may be of no consequence given the concurrent nature of the data structure, but it seems to be a nuanced difference from the guarantees provided by sync.Mutex?

sync.Mutex uses system call to park the thread (futex in case of linux) hence there is a greater degree of synchronization in this case.

Here is a thread for more memory order types for atomic operations to provide a greater degree of synchronization https://groups.google.com/g/golang-dev/c/vVkH_9fl1D8/m/azJa10lkAwAJ which also talks about re-ordering of atomic operations so that the case like the one above doesn't occur.

[aathan]

FYI: https://groups.google.com/g/golang-nuts/c/q8jgCbeilbk