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

cmd/compile: improve BCE to detect safe unbounded slicing #35483

Closed
nhooyr opened this issue Nov 9, 2019 · 4 comments
Closed

cmd/compile: improve BCE to detect safe unbounded slicing #35483

nhooyr opened this issue Nov 9, 2019 · 4 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@nhooyr
Copy link
Contributor

nhooyr commented Nov 9, 2019 •
edited

See #31586 (comment)

Core problem can be reduced to:

package scratch

import "encoding/binary"

func A1(b []byte) {
	key64 := uint64(1024)
	for len(b) >= 32 {
		v := binary.LittleEndian.Uint64(b)
		binary.LittleEndian.PutUint64(b, v^key64)
		v = binary.LittleEndian.Uint64(b[8:])
		binary.LittleEndian.PutUint64(b[8:], v^key64)
		v = binary.LittleEndian.Uint64(b[16:])
		binary.LittleEndian.PutUint64(b[16:], v^key64)
		v = binary.LittleEndian.Uint64(b[24:])
		binary.LittleEndian.PutUint64(b[24:], v^key64)
		b = b[32:]
	}
}

func A2(b []byte) {
	key64 := uint64(1024)
	for len(b) >= 32 {
		v := binary.LittleEndian.Uint64(b)
		binary.LittleEndian.PutUint64(b, v^key64)
		v = binary.LittleEndian.Uint64(b[8:16])
		binary.LittleEndian.PutUint64(b[8:16], v^key64)
		v = binary.LittleEndian.Uint64(b[16:24])
		binary.LittleEndian.PutUint64(b[16:24], v^key64)
		v = binary.LittleEndian.Uint64(b[24:32])
		binary.LittleEndian.PutUint64(b[24:32], v^key64)
		b = b[32:]
	}
}

BCE:

$ go build -gcflags="-d=ssa/check_bce/debug=1" scratch.go
# command-line-arguments
./scratch.go:10:34: Found IsInBounds
./scratch.go:12:34: Found IsInBounds
./scratch.go:14:34: Found IsInBounds

Bound checks remain in A1 even though they are not needed but are eliminated in A2 due to the explicit and not unbounded slices.

@renthraysk stated:

It was the _ = b[7] line in PutUint64() that was cause the bounds checks. The compiler failed to prove it's not needed with PutUint64(b[8:], x) however it does eliminate the first check in PutUint64(b, x).

I'm on 1.13.4 on macOS.
@nhooyr nhooyr mentioned this issue Nov 9, 2019
Closed
@josharian
Copy link
Contributor

cc @zdjones

@agnivade agnivade changed the title cmd/go: improve BCE to detect safe unbounded slicing cmd/compile: improve BCE to detect safe unbounded slicing Nov 10, 2019
@agnivade agnivade added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 10, 2019
@agnivade agnivade added this to the Unplanned milestone Nov 10, 2019
@zdjones
Copy link
Contributor

zdjones commented Nov 11, 2019

This is a duplicate of #24876. Also see #19126

The issue is that the prove pass does not currently do any arithimetic when assesing b[16:] and therefore has no information about the length of the resulting slice. see this comment: #19126 (comment).

I have a chain of CLs that fix this, but they are not complete this cycle.

@zdjones
Copy link
Contributor

zdjones commented Nov 11, 2019

Here is the CL chain that fixes this issue: https://go-review.googlesource.com/c/go/+/190657

@agnivade
Copy link
Contributor

Closing as a duplicate.

@golang golang locked and limited conversation to collaborators Nov 10, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
6 participants
@josharian @agnivade @ALTree @zdjones @gopherbot @nhooyr