x/tools/go/ssa: wrong base pointer of loadconstraint when handling *ssa.Next in genInstr()@gen.go

[april1989]

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

$ go version 1.16.3

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GOHOSTARCH="amd64"
GOHOSTOS="darwin"

What did you do?

Run go pointer analysis under the directory /grpc-go/examples/features/xds/client (master with commit e38032e927812bb354297adcab933bedeff6c177) to analyze the main.go file. I do not think the commit is a necessary, probably the code from recent master is also able to reproduce the issue. I used the program below to run pointer analysis:

func main() {
	cfg := &packages.Config{
		Mode:  packages.LoadAllSyntax, // the level of information returned for each package
		Dir:   "",                     // directory in which to run the build system's query tool
		Tests: false,                  // setting Tests will include related test packages
	}
	initial, err := packages.Load(cfg)
	if err != nil {
		panic(fmt.Sprintln(err))
	}
	prog, pkgs := ssautil.AllPackages(initial, 0)
	prog.Build()
	mains, err := findMainPackages(pkgs)
	if err != nil {
		return
	}

	logfile, _ := os.Create("/Users/bozhen/Documents/GO2/default-x-tools/_logs/my_log_0") //replace with your log
	config := &pointer.Config{
		Mains:          mains,
		BuildCallGraph: true,
		Reflection:     false,
		Log:            logfile,
	}

	result, err := pointer.Analyze(config)
	if err != nil {
		panic(err) // internal error in pointer analysis
	}
	cg := result.CallGraph
	fmt.Println(cg)
}

func findMainPackages(pkgs []*ssa.Package) ([]*ssa.Package, error) {
	var mains []*ssa.Package
	for _, p := range pkgs {
		if p.Pkg.Name() == "main" && p.Func("main") != nil {
			mains = append(mains, p)
		}
	}
	if len(mains) == 0 { 
		return nil, fmt.Errorf("no main packages")
	}
	return mains, nil
}

What did you expect to see?

In the log, the constraints generated for IR statementt40 = next t34 in function (*google.golang.org/grpc/xds/internal/balancer/edsbalancer.balancerGroup).close should be:

; t40 = next t34
	localobj[t33] = n0
	load n319631 <- n319625[4]

where n319631 (the base pointer of the load) is from "Creating nodes for local values":

create n319629 bool for t40#0
create n319630 invalid type for t40#1
create n319631 *google.golang.org/grpc/xds/internal/balancer/edsbalancer.subBalancerWithConfig for t40#2
val[t40] = n319629  (*ssa.Next)

What did you see instead?

Instead, the generated constraints are:

; t40 = next t34
	localobj[t33] = n0
	load n319634 <- n319625[4]

where n319634 is from a irrelevant local variable at the begging of this function:

; *t4 = false:bool
	create n319634 bool for false:bool
	globalobj[false:bool] = n0
	val[false:bool] = n319634  (*ssa.Const)
	store n319598[0] <- n319634

I copied the grpc function here with which source code the above two IR statements mapped to:

func (bg *balancerGroup) close() {
	bg.incomingMu.Lock()
	if bg.incomingStarted { // !! this maps to IR: *t4 = false:bool
		bg.incomingStarted = false

		for _, pState := range bg.idToPickerState {
			// Reset everything to IDLE but keep the entry in map (to keep the
			// weight).
			pState.picker = nil
			pState.state = connectivity.Idle
		}

		// Also remove all SubConns.
		for sc := range bg.scToSubBalancer {
			bg.cc.RemoveSubConn(sc)
			delete(bg.scToSubBalancer, sc)
		}
	}
	bg.incomingMu.Unlock()

	bg.outgoingMu.Lock()
	if bg.outgoingStarted {
		bg.outgoingStarted = false
		for _, config := range bg.idToBalancerConfig { // !! this maps to IR: t40 = next t34
			config.stopBalancer()
		}
	}
	bg.outgoingMu.Unlock()
	// Clear(true) runs clear function to close sub-balancers in cache. It
	// must be called out of outgoing mutex.
	bg.balancerCache.Clear(true)
}

So, why is the node for t40 replaced by the node for t4 in the generated constraints, if my understanding is correct?

I checked the source code a little bit, found that the wrong mapping is because of the computation of odst += ksize when generating constraints for *ssa.Next and the key type is invalid (the code is at go/pointer/gen.go:1078 of the most recent commit when I submit this issue). Should not this be odst += 1? Because the algorithm only creates three pointers/nodes for this *ssa.Next instruction: ok, key and value. There is no flatten copy for key or value pointers. So, if the key type is invalid, shouldn't it skip this key node and use the value node (+= 1) as the load base, since the value will be extract later?

Thanks.

[cherrymui]

cc @findleyr

[timothy-king]

cc @alandonovan is the original author of the package and probably understands this code the best. Fixing this requires understanding an edge case in the pointer package, in particular the constraint generation for (*ssa.Next) on maps. Below is a summary of what is happening. I am not yet confident I understand what needs to be fixed.

I was able to reproduce the report following https://grpc.io/docs/languages/go/quickstart/.

Here is what is happening in way too much detail.

The instruction is:

        t40 = next t34      (ok bool, k invalid type, v *subBalancerWithConfig)

Note the invalid type k.

The local nodes are indeed as above (the constants differ from the original report):

        create n169136 bool for t40#0
        create n169137 invalid type for t40#1
        create n169138 *google.golang.org/grpc/xds/internal/balancer/edsbalancer.subBalancerWithConfig for t40#2
        val[t40] = n169136  (*ssa.Next)

At the end of the *ssa.Next case within genInstr() (line) the values of the following expressions are

ksize: 4
vsize: 1
osrc: 4
odst: 5
sz: 1
a.valueNode(instr): 169136
(a.valueNode(instr)+odst): 169141

From this we know the code took the else branch of if tTuple.At(1).Type() != tInvalid. This corresponds to k invalid type.

We then enter genLoad() here. The code looks for the objectNode() of the map t33. Nothing matches and we see the local object as n0. This matches this line in the output:

        localobj[t33] = n0

This means we fall into the load() case of genload(). This is called with the arguments:

load(dst: 169141, src: 169132, offset: 4, sizeof: 1)

This then creates the anomalous load constraint in the reported issue:

load n169141 <- n169132[4]

n169141 is just 169141 == a.valueNode(instr) + odst.

The region n169141 is created during the genIntr() while processing *t4 = false:bool as report. AFAICT what has happened is effectively a buffer overflow past the last region created during the "Creating nodes for local values". If so, the fact that they are connected is a coincidence.

All of that put together, it looks like (*ssa.Next) is trying to flatten the memory when the key is an invalid kind, but either:

• is not allocating the additional memory cells when this is the case,
• should not be flattening in the k is an invalid kind case,
• this needs to have some kind of support from objectNode() that should be happening, or
• the k invalid type needs to be fixed before pointer analysis.

Hopefully @alandonovan can give some direction on which of these (*ssa.Next) should be modeled as.

[scott-cotton]

follow up

Good news

The simple patch [1] below fixes the problem in the analysis of grpc and passes the unit tests in golang.org/x/tools/go/{pointer,ssa}.

Bad news

Performance

The fix may generate more nodes and hence slow things down a bit. It doesn't seem substantial from the runs I tried, but it is a possibility.

Coherence of *ssa.Next

The patch above keeps around some useless optimisations in constraint generation in pointer for *ssa.Next. There appear to be other problems with *ssa.Next types, such as the offsets in *ssa.Extract when a type is invalid, and perhaps flattening.

Also, it looks like we need a test and documentation for a range over a string in the generation of constraints.

SSA compatibility

The fix [1] no longer allows invalid types for *ssa.Next resulting from ranges over maps. Perhaps we should consider
changing the API of *ssa.Next so that it always gives all types and then provides an alternative API for whether the key or value (or both) are assigned to '_'.

What is the recommended process for changing package ssa in such a way? It's in x/tools, marked experimental in the docs, but it seems a number of tools depend on it as is.

Not easily solvable in go/pointer

All attempts to fix the problem in go/pointer failed.

1. Attempt 1: skip over invalid types when flattening *types.Tuple: no effect...
2. Attempt 2: disable optimisations in generate constraints for *ssa.Next: because of flattening this doesn't work.
3. Attempt 3: in case *ssa.Next in genFunc for allocating local nodes, use the type from the associated map instead of (*ssa.Next).Type(). This worked for the grpc analysis, but broke a unit test case in go/pointer/testdata/maps.go. The problem was that the created local nodes were not synchronised with the sizes associated with the constraints generated for *ssa.Extract.

Conclusions

@timothy-king it looks like almost all your alternatives for sources of incoherencies with the flattening are involved.

(Note it looks like @alandonovan moved from Google to Github: we may need to fix and continue this without him? @matloob ?)

It looks like this problem can be fixed in go/ssa/builder.go if the fix does not cause problems for the community. It also looks like the pointer analysis could have more extensive testing, and/or an internal consistency checks.

Thoughts?

References

[1] Diff of a fix.

scott@pavillion tools % git diff go/ssa/builder.go
diff --git a/go/ssa/builder.go b/go/ssa/builder.go
index 2d0fdaa4..178cbb36 100644
--- a/go/ssa/builder.go
+++ b/go/ssa/builder.go
@@ -1920,8 +1920,10 @@ func (b *builder) rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock) {

        case *types.Chan:
                k, loop, done = b.rangeChan(fn, x, tk, s.For)
+       case *types.Map:
+               k, v, loop, done = b.rangeIter(fn, x, rt.Key(), rt.Elem(), s.For)

-       case *types.Map, *types.Basic: // string
+       case *types.Basic: // string
                k, v, loop, done = b.rangeIter(fn, x, tk, tv, s.For)

        default:

[scott-cotton]

Please feel free to assign this issue to me if there are no other takers.

[timothy-king]

What is the recommended process for changing package ssa in such a way? It's in x/tools, marked experimental in the docs, but it seems a number of tools depend on it as is.

Like other x/tools package changes, the recommended process is to discuss this over a GH issue. This is not a big enough change to warrant a proposal IMO.

My quick summary of the proposed patch is to remove the following line from the documentation of *ssa.Next:

// The types of k and/or v may be types.Invalid.

Strictly speaking this is not backwards compatible with the previous contract. It is possible to use this as a side-effect for detecting "_, x := range" statements. Though I doubt this is happening in practice. This is in the realm of a change I think we can consider.

•           k, v, loop, done = b.rangeIter(fn, x, rt.Key(), rt.Elem(), s.For)
  

I am not sure whether this is exactly right. tk, tv may have different types than rt.Key(), rt.Elem() but which rt.Key(), rt.Elem() are assignable to. You probably want to use those when they are available. Example: https://play.golang.org/p/R5k9JB0ayoi . (I am not sure this is wrong either. Mostly pointing out this is subtle.)

Not easily solvable in go/pointer

I am not yet seeing an explanation for the root cause of the bug in this list. This still looks like a bug in go/pointer. go/ssa does not look like it has a bug. There are an order of magnitude more users of go/ssa than go/pointer. At the moment, I am inclined to suggest finding the root cause in go/pointer over making a mildly backwards incompatible change to go/ssa.

I am willing to update this opinion if we continue to be stumped.

(Note it looks like @alandonovan moved from Google to Github: we may need to fix and continue this without him? @matloob ?)

We can address this without @alandonovan's input. (Would be nice though.) @findleyr is listed as the "Secondary" owner for x/tools/go/ssa and would be a natural 2nd pair of eyes to take a look at this change.

(PS. It is kinda fun running into another VERIMAG alum.)

[findleyr]

We can address this without @alandonovan's input. (Would be nice though.) @findleyr is listed as the "Secondary" owner for x/tools/go/ssa and would be a natural 2nd pair of eyes to take a look at this change.

Hi, yes I can definitely take a look -- in particular I can try to offer an opinion on compatibility issues. Let me catch up a bit, and comment later this week.

[scott-cotton]

(PS Indeed!)

RE: summary of (previously) proposed change: yes, also for other range iters I would guess (at least string).

As for the root cause, @timothy-king 's observation that the types of k, v can be different than the map type made me try another fix in go/pointer/gen.go [1], which is based on the idea that the root cause is the false assumption that k, v types are the same as the corresponding Map.Key(), Map.Elem().

It passes the unit tests and the erroneous grpc case looks ok too.

I concur that the difference in usage of ssa vs pointer merits giving preference to a fix in pointer.

[1]

diff --git a/go/pointer/gen.go b/go/pointer/gen.go
index 4f8a75df..e06eae60 100644
--- a/go/pointer/gen.go
+++ b/go/pointer/gen.go
@@ -1060,12 +1060,14 @@ func (a *analysis) genInstr(cgn *cgnode, instr ssa.Instruction) {
                        theMap := instr.Iter.(*ssa.Range).X
                        tMap := theMap.Type().Underlying().(*types.Map)

-                       ksize := a.sizeof(tMap.Key())
-                       vsize := a.sizeof(tMap.Elem())
+                       sksize := a.sizeof(tMap.Key())
+                       svsize := a.sizeof(tMap.Elem())

                        // The k/v components of the Next tuple may each be invalid.
                        tTuple := instr.Type().(*types.Tuple)

+                       dksize := a.sizeof(tTuple.At(1).Type())
+
                        // Load from the map's (k,v) into the tuple's (ok, k, v).
                        osrc := uint32(0) // offset within map object
                        odst := uint32(1) // offset within tuple (initially just after 'ok bool')
@@ -1073,15 +1075,15 @@ func (a *analysis) genInstr(cgn *cgnode, instr ssa.Instruction) {

                        // Is key valid?
                        if tTuple.At(1).Type() != tInvalid {
-                               sz += ksize
+                               sz += sksize
                        } else {
-                               odst += ksize
-                               osrc += ksize
+                               odst += dksize // 0
+                               osrc += sksize
                        }

                        // Is value valid?
                        if tTuple.At(2).Type() != tInvalid {
-                               sz += vsize
+                               sz += svsize
                        }

                        a.genLoad(cgn, a.valueNode(instr)+nodeid(odst), theMap, osrc, sz)

[timothy-king]

I think the patch may be incomplete. dksize is not used. (Can you edit the previous comment?)

[scott-cotton]

I think the patch may be incomplete. dksize is not used. (Can you edit the previous comment?)

Yes, done.

[gopherbot]

Change https://golang.org/cl/335889 mentions this issue: go/pointer: fix constraint gen for *ssa.Next