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.

Sign up for GitHub

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

Jump to bottom

x/tools/go/ssa: mistakenly converts slice index to int on 32 bit systems #50949

Closed
dominikh opened this issue Feb 1, 2022 · 7 comments
Closed

x/tools/go/ssa: mistakenly converts slice index to int on 32 bit systems #50949

dominikh opened this issue Feb 1, 2022 · 7 comments
Labels
Analysis Issues related to static analysis (vet, x/tools/go/analysis) FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
Unreleased

Comments

@dominikh
Copy link
Member

dominikh commented Feb 1, 2022

Consider this program:

package main

import "math"

func main() {
	var idx int64 = math.MaxInt32*2 + 8
	x := make([]int, 16)
	println(x[idx])
	println(x[int(idx)])
}

go/ssa compiles it to

func main():
0:                                                                entry P:0 S:0
	t0 = new [16]int (makeslice)                                   *[16]int
	t1 = slice t0[:16:int]                                            []int
	t2 = convert int <- int64 (4294967302:int64)                        int
	t3 = &t1[t2]                                                       *int
	t4 = *t3                                                            int
	t5 = println(t4)                                                     ()
	t6 = convert int <- int64 (4294967302:int64)                        int
	t7 = &t1[t6]                                                       *int
	t8 = *t7                                                            int
	t9 = println(t8)                                                     ()
	return

both times converting the index to int before using it. But on systems where int is 32 bits wide, this is not correct. Compare with the runtime behavior on GOARCH=386: The first indexing operation panics with panic: runtime error: index out of range [4294967302] with length 16 while the second one succeeds, accessing x[6], thanks to wrap-around.

https://go.dev/ref/spec#Index_expressions is the relevant section of the specification.

/cc @timothy-king
@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Feb 1, 2022
@gopherbot gopherbot added this to the Unreleased milestone Feb 1, 2022
@timothy-king timothy-king added the Analysis Issues related to static analysis (vet, x/tools/go/analysis) label Feb 1, 2022
@timothy-king
Copy link
Contributor

Thank you for the report. SSA is not faithfully translating the original program.

Here are possible options for resolving this:

  1. Add a bounds check on the convert.
  2. Expand the set of types accepted as dereference indices can be expanded. Then eliminate the conversion.

My thoughts:

  • There are a lot of variants for bounds checking. The most obvious is to add a new basic block and branch on each conversion. This check can alternatively be built into the convert instruction (or a new instruction), i.e. panic if not in range. SSA can be made to be aware of the size of int when translating to eliminate noisy branches. (Probably are some variants I am missing.)
  • The second option is the cleanest but is likely the hardest on direct users of the ssa package as they are expected to change the interpretation/assumptions of the Index and IndexAddr instructions everywhere. Index and IndexAddr phrase themselves in the documentation as "Index is an integer expression." It does not say "int expression". So we justifiably have wiggle room to eliminate the conversion.
  • I do not believe we should make preserving the content of the panic a priority. As long as SSA says a panic happens, this is a sufficiently faithful translation.

Thoughts on the preferred resolution? In the meantime, I'll try to get some thoughts from the compiler folks for how to faithfully lower the check.

@timothy-king
Copy link
Contributor

Relevant part of cmd/compile:

go/src/cmd/compile/internal/ssagen/ssa.go

Line 7378 in a42bbf4

func (s *state) extendIndex(idx, len *ssa.Value, kind ssa.BoundsKind, bounded bool) *ssa.Value {

This solutions requires knowing the sizes of the target architecture. x/tools/go/ssa currently lacks this information.

@mdempsky
Copy link
Member

mdempsky commented Feb 1, 2022

Expand the set of types accepted as dereference indices can be expanded. Then eliminate the conversion.

FWIW, this is the solution cmd/compile uses in its IR representation, where bounds checks are still implicit as part of the index operation.

It's only once we lower to SSA where bounds checks are explicit that we constrain the size of the index value, because it needs to be register-sized for instruction selection / register allocation.

@dominikh
Copy link
Member Author

dominikh commented Feb 2, 2022 •
edited

I'm in favour of option 2.

Adding explicit bounds checks with branches seems out of place. go/ssa doesn't explicitly encode panics in the CFG. Interface assertions, slice indexing, map writes, pointer dereferences, all are assumed to panic dynamically, without these edges being part of the CFG.

Adding a new instruction that checks the bounds before the conversion seems unnecessarily detailed, and somewhat redundant with IndexAddr also doing bounds checking on the int index. It also doesn't match the language specification: there is no "if the index doesn't fit into an int, we panic". There is only "if the index is out of bounds, we panic"

The only faithful representation of the language semantics is IndexAddr accepting any integer type. There is no conversion to int, and doing additional bounds checking and conversions outside the IndexAddr instruction creates new behavior that doesn't exist¹.

the hardest on direct users of the ssa package as they are expected to change the interpretation/assumptions of the Index and IndexAddr instructions everywhere

They don't have to change much. The type of the index is no longer guaranteed to be int, but that's about it. The instructions could already panic for out of bounds indices; now these indices can be larger than before. This doesn't seem any harder on them than adding an entirely new instruction.

¹: this is all considering that go/ssa is a high-level IR that represents the language as specified. It doesn't encode the actual, lowered to real instructions, behavior.

@toothrot toothrot added the NeedsFix The path to resolution is known, but the work has not been done. label Feb 4, 2022
@zpavlinovic
Copy link
Contributor

I also lean towards option 2. Adding explicit checks with branches also might increase the size of SSA unnecessarily.

@zpavlinovic
Copy link
Contributor

The plan is to implement the fix based on option 2, which will happen after #48525 is done.

@dominikh dominikh mentioned this issue Feb 25, 2022
Closed
@gopherbot
Copy link

Change https://go.dev/cl/387996 mentions this issue: go/ssa: removes conversion of index value in Index and IndexAddr to int

@golang golang locked and limited conversation to collaborators Mar 30, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
Analysis Issues related to static analysis (vet, x/tools/go/analysis) FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
6 participants
@toothrot @mdempsky @dominikh @timothy-king @zpavlinovic @gopherbot