Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: map increment can give incorrect result #25936

Closed
rogpeppe opened this issue Jun 18, 2018 · 20 comments

Comments

Projects
None yet
@rogpeppe
Copy link
Contributor

commented Jun 18, 2018

What version of Go are you using (go version)?

go version devel +187c3a6 Sun Jun 17 21:35:39 2018 +0000 linux/amd64

Does this issue reproduce with the latest release?

No. It's on tip only.

What did you do?

Run this program:

package main

import (
	"fmt"
)

const (
	key1 = ""
	key2 = "x"
)

func main() {
	m := make(map[string]int)
	m[key1] = 99
	delete(m, key1)
	n1 := m[key2]
	m[key2]++
	n2 := m[key2]
	if n2 != n1+1 {
		fmt.Printf("BUG!!!!! %v; incremented %v to %v\n", key2, n1, n2)
	}
}

On tip, it prints BUG!!!!! x; incremented 0 to 100. It seems that the increment operator might be looking at the old value that has been deleted.

@mvdan

This comment has been minimized.

Copy link
Member

commented Jun 18, 2018

There have been some optimizations to maps in this cycle, I think. Would be useful to bisect all the changes since 1.10 with this reproducer.

@mvdan mvdan added this to the Go1.11 milestone Jun 18, 2018

@josharian josharian changed the title cmd/go: map increment can give incorrect result cmd/compile: map increment can give incorrect result Jun 18, 2018

@mvdan

This comment has been minimized.

Copy link
Member

commented Jun 18, 2018

Slightly simpler repro: https://play.golang.org/p/gU623UMz03_e

It happens with a map[int]int too, so it probably affects all maps.

@ALTree

This comment has been minimized.

Copy link
Member

commented Jun 18, 2018

Bisected to 7395083 (cmd/compile: avoid extra mapaccess in "m[k] op= r").

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor

commented Jun 18, 2018

Looking

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor

commented Jun 18, 2018

@mdempsky I looked at code and may confirm that if I force early re-write in order.go, like:

	if instrumenting || n.Left.Op == OINDEXMAP /*&& (n.SubOp() == ODIV || n.SubOp() == OMOD)*/ {
		// Rewrite m[k] op= r into m[k] = m[k] op r so
		// that we can ensure that if op panics
		// because r is zero, the panic happens before
		// the map assignment.

It works as expected!

So, the problem is that if we re-write "Rewrite m[k] op= r into m[k] = m[k] op r" in a walk.go we get invalid logic.

We could make this quick fix (with test) to unblock release but my concern is that we might have another bug in AST that gives us incorrect logic in this case.

I will continue looking but appreciate if any ideas.

@bradfitz

This comment has been minimized.

Copy link
Member

commented Jun 18, 2018

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor

commented Jun 18, 2018

I have an idea what happens.

delete(m, key1) doesn't aways "clear" value. L-Value map transforms into call runtime.mapassign that doesn't clear value after it "inserted/re-used". We never read from it before but only wrote to it.

This is why when we use L-value pointer returned by runtime.mapassign as R-Value, we use "old" value instead of "zero".

I will try to confirm it and figure out right solution:

  • either clear during "map delete"
  • clear during "insert/re-use" at mapassign
@mdempsky

This comment has been minimized.

Copy link
Member

commented Jun 19, 2018

Oof. I think ideally we'd introduce a new mapassignop function that ensures newly inserted values are zero-initialized.

We can add additional zero-initializing to mapassign or mapdelete, but that may add overhead to other map-using code.

On the upside, we only need explicit zero-initialization when the value type is a primitive arithmetic type, so maybe an extra store (or two, in the case of complex128) wouldn't be an unreasonable overhead. (We don't need to worry about string-valued maps, because they get explicitly cleared during mapdelete already.)

@martisch

This comment has been minimized.

Copy link
Member

commented Jun 19, 2018

I think what should be ideally avoided in a solution for speeding up m[k] += 1 for go1.11 and then making it correct is that we regress in performance for normal map assign m[k] = 1 from go1.10 to go1.11. Approximating over google profiling data seems to suggest normal map assign is consuming more time overall so the trade off of speeding up one and making the other slower should be carefully investigated. But as noted writing to a small memory location that will be overwritten again anyway might not be much of a problem.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Jun 19, 2018

We need only change mapdelete to ensure that empty slots are zeroed.
I think that might be acceptable. Or the wrapper @mdempsky suggested would work (mapassignop, which calls mapassign2, then zeroes the result slot if the 2nd return value was false).

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor

commented Jun 21, 2018

Working on fix, will publish soon

@gopherbot

This comment has been minimized.

Copy link

commented Jun 21, 2018

Change https://golang.org/cl/120255 mentions this issue: cmd/compile: map delete should clear value always

@nightlyone

This comment has been minimized.

Copy link
Contributor

commented Jun 21, 2018

side note for anyone else wondering about that: The newly introduced map bulk deletion (mapclear) still works as expected in this case.

package main

import (
        "fmt"
)

const (
        key1 = ""
        key2 = "x"
)

func main() {
        m := make(map[string]int)
        m[key1] = 99
        for k := range m {
                delete(m, k)
        }
        n1 := m[key2]
        m[key2]++
        n2 := m[key2]
        if n2 != n1+1 {
                fmt.Printf("BUG!!!!! %v; incremented %v to %v\n", key2, n1, n2)
        }
}
@josharian

This comment has been minimized.

Copy link
Contributor

commented Jun 21, 2018

Thanks for thinking of that, @nightlyone. We should probably add a test for that.

@odeke-em

This comment has been minimized.

Copy link
Member

commented Jun 22, 2018

@nightlyone or @josharian would any of you be interested in submitting the test that @josharian recommended we provide to lock in the bulk map clearing idiom :) ?

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor

commented Jun 22, 2018

@nightlyone Can you clarify please, I checked and confirm that this doesn't hit the problem but theoretically it does the same. Is it because there is optimization that replaces range-delete with some "mapclear"? I have seen the optimization in the code for arrays/slices (memclr). Does it do efficient clear for map as well?

Anyway, I am going to add appropriate test to fix. Thanks!

@josharian

This comment has been minimized.

Copy link
Contributor

commented Jun 22, 2018

@vkuzmin-uber see #20138 for bulk map clear

@nightlyone

This comment has been minimized.

Copy link
Contributor

commented Jun 23, 2018

@vkuzmin-uber yes there is such an optimization in place and @josharian pointed out the issue where it was discussed and implemented. I have been curious whether that code path was affected too and quickly shared my results.

The test case which you added and named TestIncrementAfterBulkClearKeyStringValueInt looks good to me and I verified that there is only one needed, since we have only one mapclear.

Great job!

@gopherbot gopherbot closed this in b080abf Jun 26, 2018

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor

commented Sep 18, 2018

We need only change mapdelete to ensure that empty slots are zeroed.
I think that might be acceptable. Or the wrapper @mdempsky suggested would work (mapassignop, which calls mapassign2, then zeroes the result slot if the 2nd return value was false).

Going to start working on wrapper/map API that explicitly support op= case. Will create a separate Issue.

@martisch

This comment has been minimized.

Copy link
Member

commented Sep 18, 2018

There is an issue for using a wrapper #26059

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.