cmd/vet: warn about concurrent modification of a map (values added in a for loop)

[rokusei]

(using #43698 as a template)
Related issues: #9926, #35239

Per the Go specification of for loops, within the For statements with range clause section, it states:

If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next.

I expect that package authors might not be expecting the non-deterministic behavior that comes with concurrent modification. This can lead to unexpected bugs and behavior. I believe Java goes so far to even throw a runtime exception.

Playground example
Real-world example

I propose that cmd/vet should emit a warning when:

• a map is iterated over using a for statement
• the map has elements added during iteration

[mvdan]

How about doing it at run-time? Go will already panic if many concurrent reads and writes are done on a map. This wouldn't be a data race per se, but it could be possible to catch writes in the middle of a range at run-time.

[heschi]

Given that the behavior is specified, a runtime failure (even just in race mode) seems inappropriate to me.

As I understand it, vet checks are intended to have essentially no false positives. As such, someone would need to make a case that this is a bug, not just some of the time, but all the time.

cc @alandonovan

[mvdan]

Given that the behavior is specified, a runtime failure (even just in race mode) seems inappropriate to me.

Right, but then the same applies to vet :) I guess I'm saying that if this is definitely wrong, then it would be ideal to panic at run-time.

[ianlancetaylor]

It's not definitely wrong. It's entirely reasonable to add elements to a map during an iteration, if the new elements have some characteristic that allows the iteration to skip them.

I don't think vet should warn about this. Perhaps other static analyzers could warn about this case, but I don't see it as appropriate for vet.

That said, look at real code. Try writing the vet warning and running it over a bunch of packages written by different people (e.g., all Kubernetes packages including third party imported packages). If the new check never fires, it's probably not helpful and we shouldn't add it. If the new check only issues warnings on correct code, we shouldn't add it. If the new check only issues warnings on code that turns out to be incorrect, we should add it. Other cases (warnings on both correct and incorrect code) require a judgement call.

[bcmills]

This pattern isn't always wrong. Consider, say, a program that constructs a map containing the transitive closure of nodes in a graph by iterating until no new nodes are added. Such a program is guaranteed to converge on a map with deterministic contents, even though the set of nodes scanned (and added) in any given iteration may vary.

To detect real bugs, perhaps it would suffice to make the order of iteration more aggressive under some configuration. For example, in -race mode we could randomly choose between producing every new entry and no new entries (similar to what is proposed for #35128, or the existing scheduler randomization). Then the real bugs could be detected during testing, perhaps by fuzz tests (#44551).

[timothy-king]

One criteria for the check is that there needs to be a path back to the range statement, e.g. do not report inserting and then breaking/returning. I suspect there will be too many false positives otherwise.

That said, look at real code.

+1. The background rate of people misunderstanding "skippable" insertions vs. getting it right will determine how reasonable adding this check is.

Consider, say, a program that constructs a map containing the transitive closure of nodes in a graph by iterating until no new nodes are added.

@bcmills I don't understand the example you have in mind. Can you elaborate?

To detect real bugs, perhaps it would suffice to make the order of iteration more aggressive under some configuration.

Why not do this on regular go test? (Overhead?)

[bcmills]

I don't understand the example you have in mind. Can you elaborate?

Sure: https://play.golang.org/p/Aj5Oafuk8-I

[jamall-mahmoudi-dev]

I think must be cmd/vet tool issue a warning in such situations to prevent programmers from changing the map simultaneously during iteration. This warning can help increase the accuracy and predictability of the code and reduce bugs associated with this behavior.

[adonovan]

Within a single goroutine, adding to or deleting from a map while iterating over it is not always wrong, so we definitely would not want vet to report a diagnostic in that case. Therefore, I will close this issue.

With multiple goroutines, it is always a mistake to modify the map concurrent with iterating over it. It would be great if vet could reliably report a diagnostic for this (and other) data races. Unfortunately, statically detecting such races with only an ALGOL-like type system is one of the great unsolved (or unsolvable) problems of computer science.

[mhagger]

With multiple goroutines, it is always a mistake to modify the map concurrent with iterating over it.

@adonovan: I've been trying to figure out whether it is possible to modify a map during iteration, provided the start and end of the for loop always happen while a lock is held, and any other map accesses are protected by the same lock. For example, empirically, this example runs 100% correctly for me both with and without the race detector turned on. The core of it is this peculiar-looking locking pattern:

m := make(map[...]...)

lock.Lock()
for k, v := range m {
    // do something with map

    // Can we assume that map[k] == v here, before we release the lock?

    // release the lock to let other goroutines work with the map (reads
    // _and_ writes!):
    lock.Unlock()

    // do something not involving the map
    […]

    // re-obtain the lock before starting the next iteration:
    lock.Lock()
}
lock.Unlock()

Whether this is guaranteed to work is not obvious (at least to my eyes) from the language spec nor from the Go memory model spec.

Does the answer change if the iteration doesn't use a for-range loop, but uses an iterator like maps.All()?

[adonovan]

// Can we assume that map[k] == v here, before we release the lock?

Yes, assuming "do something" didn't remove it, and there are no map accesses that don't hold the lock.

Whether this is guaranteed to work is not obvious (at least to my eyes) from the language spec nor from the Go memory model spec.

Your code example though peculiar looks sound, but my claim was that concurrent modification and iteration is a mistake, and your example, by using a mutex, ensures that the map accesses are not concurrent but sequential.

Does the answer change if the iteration doesn't use a for-range loop, but uses an iterator like maps.All()?

No, maps.All uses range under the hood.

[mhagger]

Thanks so much for your response ✨

my claim was that concurrent modification and iteration is a mistake, and your example, by using a mutex, ensures that the map accesses are not concurrent but sequential.

There has been confusion, in the discussions that I've seen, about whether the whole loop should in some way be considered a single map "iteration", in which case the other accesses would be concurrent, or whether the loop should be considered to access the map many separate times, one at at the start of each loop repetition, in which case use of a lock can prevent concurrent accesses without the need to hold the lock for the whole duration of the loop. IMO the spec is not super clear about this detail.

This is good news as it opens up some interesting design possibilities.

[adonovan]

There has been confusion, in the discussions that I've seen, about whether the whole loop should in some way be considered a single map "iteration", in which case the other accesses would be concurrent, or whether the loop should be considered to access the map many separate times, one at at the start of each loop repetition, in which case use of a lock can prevent concurrent accesses without the need to hold the lock for the whole duration of the loop. IMO the spec is not super clear about
this detail.

The whole loop is indeed a single iteration of the map, but the iteration consists of a sequence of accesses to the map. In your example, all the accesses done by the iteration and all the accesses done by other goroutines are totally ordered, so there is no concurrent access to the map, even though there may be concurrency in the program as a whole.

I don't doubt the existence of confusion in discussions of concurrency.