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: unsafe.Pointer arithmetic causes insertion of redundant nil checks #27180

Closed
FlorianUekermann opened this issue Aug 23, 2018 · 23 comments

Comments

@FlorianUekermann
Copy link
Contributor

@FlorianUekermann FlorianUekermann commented Aug 23, 2018

Most testing done using go version go1.10.1 linux/amd64
I have tried a bunch of releases, from 1.7, to 1.10.3

Caveat: I may just be confused about something, but I have spent quite some time trying to come up with reasons why the generated code makes sense and the mailing list didn't provide an answer either.

The pointer arithmetic pattern described in the unsafe documentation seems to cause the compiler to emit assembly to calculate and dereference the same pointer twice. The simplest way to reproduce this is:

func getElement1(a unsafe.Pointer) (r uint64) {
	return *(*uint64)(unsafe.Pointer(uintptr(a) + 8))
}

Looking at the (shortened) Go assembly we see this:

MOVQ    "".a(SP), AX
LEAQ    8(AX), CX
TESTB   AX, (CX)
MOVQ    8(AX), AX
MOVQ    AX, "".r+8(SP)

I would have expected something like this function (which I have tested and it seems to have the same behavior):

// func getElement1Asm(a unsafe.Pointer) (r uint64)
TEXT ·getElement1Asm(SB),NOSPLIT,$0
	MOVQ    a+8(SP), R8  // Why 8 instead of 0 like above?
	MOVQ	8(R8), R8
	MOVQ    R8, r+16(SP)
	RET

I have tried to come up with explanations for what the LEAQ, TESTB sequence is good for, but failed. It seems like the compiler is inserting the equivalent of _ = *(*uint64)(unsafe.Pointer(uintptr(a) + 8)) before the return statement.
I have tested countless variants of similar and not so similar functions containing pointer arithmetic and the result is always that both address calculation and dereference are duplicated, if an address is changed by a non-zero amount (*(*uint64)(unsafe.Pointer(uintptr(a) + 0)) doesn't have this issue).

I realize that this technically doesn't violate the spec or documented behavior, but the situation seems unfortunate (yes, I benchmarked the impact on less contrived examples).

ssa.html.log (renamed to make github happy)

@ianlancetaylor ianlancetaylor changed the title unsafe: Pointer arithmetic causes insertion of redundant nil checks cmd/compile: unsafe.Pointer arithmetic causes insertion of redundant nil checks Aug 23, 2018
@ianlancetaylor ianlancetaylor added this to the Go1.12 milestone Aug 23, 2018
@growler

This comment has been minimized.

Copy link
Contributor

@growler growler commented Aug 24, 2018

I have just stumbled upon this with a real life case:

// Go's syscall.Msghdr lacks SetIovlen
func setIovlen(msg *syscall.Msghdr, iovlen int) {
	const iovlenIs32bit = unsafe.Sizeof(msg.Iovlen) == 4
	if iovlenIs32bit {
		*(*uint32)(unsafe.Pointer(&msg.Iovlen)) = uint32(iovlen)
	} else {
		*(*uint64)(unsafe.Pointer(&msg.Iovlen)) = uint64(iovlen)
	}
}

func main() {
        var msg syscall.Msghdr
        setIovlen(&msg, 10) // line 20
        ...
}

Both 1.10.3 and 1.11rc2 generate

        0x001f 00031 (t.go:20)  LEAQ    "".msg+24(SP), AX
        0x0024 00036 (t.go:20)  PCDATA  $2, $0
        0x0024 00036 (t.go:20)  TESTB   AL, (AX)
        0x0026 00038 (t.go:20)  MOVL    $10, "".msg+24(SP)
@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 24, 2018

The question is, can we assume that all pointers generated by arithmetic are not nil?
I can concoct a counterexample:

getElement1(unsafe.Pointer(uintptr(1<<64-8)))

That being said, I think we should still get rid of the nil checks after any unsafe arithmetic. I don't think anyone is actually manufacturing nil pointers this way. We're solidly in unsafe territory here, which is exempt from the Go 1 compatibility guarantee.
The code change is easy. I think the challenge is how to describe this change in the unsafe docs.

For @growler's specific case, we could recognize a nil check of a LEAQ of a local variable can never be nil. That wouldn't require any change in behavior.

@FlorianUekermann

This comment has been minimized.

Copy link
Contributor Author

@FlorianUekermann FlorianUekermann commented Aug 24, 2018

Maybe this is where I'm misunderstanding the semantics the compiler tries to achieve, because I don't understand what you mean.

The question is, can we assume that all pointers generated by arithmetic are not nil?

My understanding is that this is irrelevant, because calculating or otherwise obtaining a nil pointer is not something that warrants any action, regardless of whether it is an unsafe pointer or not.

Dereferencing a pointer is different, that implies a nil check. Usually this happens implicitly, but if the dereference is optimized out because the result of the load isn't relevant to observed outcome, it needs to be replaced by a nil check to preserve the panic prescribed by the spec. But dereferencing is independent from pointer arithmetic. (I did test my own version with a nil pointer and it did panic iirc)

So I actually don't understand why the nil check is inserted there in the first place, not why it's not optimized out.

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 24, 2018

But there is a dereference. getElement1 does unsafe arithmetic and then dereferences the result.

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 24, 2018

Here's a concrete program that demonstrates the difference:

package main

import "unsafe"

const N = 0x77777777

type T struct {
	pad [N]byte
	v byte
}

func f(x,y uintptr) byte {
	p := (*T)(unsafe.Pointer(x - y))
	return p.v
}

func main() {
	println(f(0,0))
}

Should this panic, or return the contents of address 0x77777777?
Currently it panics:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x104df2f]

goroutine 1 [running]:
main.f(...)
	/Users/khr/gowork/tmp1.go:14
main.main()
	/Users/khr/gowork/tmp1.go:18 +0x1f
exit status 2

If we assume that pointer arithmetic always generates a non-nil result, then we'd instead do the other.

@cznic

This comment has been minimized.

Copy link
Contributor

@cznic cznic commented Aug 24, 2018

But there is a dereference. getElement1 does unsafe arithmetic and then dereferences the result.

Is it possible to left the nil dereference exception to be catched by the HW and getting rid of the SW detection?

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 24, 2018

We do use hardware detection. Usually, we can merge a nil check and a subsequent load if they are both using the same base pointer and if the constant offset in the load is small enough. It looks like that optimization gets defeated by unsafe arithmetic.

    v11 = ADDQconst <unsafe.Pointer> [8] v5 : CX
    v13 = LoweredNilCheck <void> v11 v1
    v14 = MOVQload <uint64> [8] v5 v1 : AX

The load and nil check have different base pointers, because the constant offset was merged with the load, but not merged with the nil check. We could probably allow merging constant offsets into nil checks. That would fix @FlorianUekermann's case, but probably isn't a general solution to this problem.

@FlorianUekermann

This comment has been minimized.

Copy link
Contributor Author

@FlorianUekermann FlorianUekermann commented Aug 24, 2018

Exactly, if there is a dereference already, why insert an extra one. I guess I don't understand why it makes a difference if the dereference happens in TESTB or MOVQ (in Go asm).
If you don't do arithmetic there's no check even though the pointer you're passing in may still be nil.

@FlorianUekermann

This comment has been minimized.

Copy link
Contributor Author

@FlorianUekermann FlorianUekermann commented Aug 24, 2018

Our comments overlapped. But I have an idea what I'm getting wrong now:
The nil check must happen on the base pointer of a structure in case base+offset happens to overlap with something that is valid? And the optimization that catches that base and load pointer are identical failed here?

Isn't there a guard range above 0, which is never used to catch these cases without explicit checks for nil?

@cznic

This comment has been minimized.

Copy link
Contributor

@cznic cznic commented Aug 24, 2018

Isn't there a guard range above 0, which is never used to catch these cases without explicit checks for nil?

AFAICT, at least on nixes there's one. But consider it's just a VM page-sized thing, so it'll be 4K on some if not most systems. Meaning accessing of field with offset >= 4096 using a nil struct pointer will not be HW detected. Same goes for an array with item offset large enough and this later case would be much more common in many programs. I didn't realized this when asking for the HW detection above.

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 24, 2018

Isn't there a guard range above 0, which is never used to catch these cases without explicit checks for nil?

I'm not sure what you're asking here, but we use this (from cmd/compile/internal/ssa/nilcheck.go):

// All platforms are guaranteed to fault if we load/store to anything smaller than this address.
//
// This should agree with minLegalPointer in the runtime.
const minZeroPage = 4096
@growler

This comment has been minimized.

Copy link
Contributor

@growler growler commented Aug 27, 2018

@randall77, does it make sense to open a specific issue for nil check on pointers to local variables then?

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 27, 2018

@growler: Sure, although we already do that normally:

			// a value resulting from taking the address of a
			// value, or a value constructed from an offset of a
			// non-nil ptr (OpAddPtr) implies it is non-nil
			if v.Op == OpAddr || v.Op == OpLocalAddr || v.Op == OpAddPtr {
				nonNilValues[v.ID] = true
			}

There's something a bit more subtle going on here. Looks like we're nil-checking offsets from local addresses, instead of those addresses themselves. That might be what needs fixing.

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 27, 2018

You might try adding OpOffPtr to that list if you want to try a CL.

@growler

This comment has been minimized.

Copy link
Contributor

@growler growler commented Aug 27, 2018

Works like a charm:

        0x001f 00031 (t.go:20)  MOVL    $10, "".msg+24(SP)

I was too quick about tests though, it has failed nilptr3.go

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 27, 2018

Ship it!

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 27, 2018

nilptr3.go is as much recording the status quo as it is a right vs. wrong test.
If the nil checks it's complaining about are really not needed, update the test.

@growler

This comment has been minimized.

Copy link
Contributor

@growler growler commented Aug 27, 2018

The nil check inside the function body has been removed as well, which I think is not desired result, since function might get called by a plenty of ways. Here is the function body compiled by 1.11:

        0x0000 00000 (t.go:12)  PCDATA  $2, $1
        0x0000 00000 (t.go:12)  PCDATA  $0, $1
        0x0000 00000 (t.go:12)  MOVQ    "".msg+8(SP), AX
        0x0005 00005 (t.go:12)  PCDATA  $2, $2
        0x0005 00005 (t.go:12)  LEAQ    24(AX), CX
        0x0009 00009 (t.go:12)  PCDATA  $2, $1
        0x0009 00009 (t.go:12)  TESTB   AL, (CX)
        0x000b 00011 (t.go:12)  MOVQ    "".iovlen+16(SP), CX
        0x0010 00016 (t.go:12)  PCDATA  $2, $0
        0x0010 00016 (t.go:12)  MOVL    CX, 24(AX)

and here is compiled with the suggested change:

        0x0000 00000 (t.go:12)  PCDATA  $2, $0
        0x0000 00000 (t.go:12)  PCDATA  $0, $0
        0x0000 00000 (t.go:12)  MOVQ    "".iovlen+16(SP), AX
        0x0005 00005 (t.go:12)  PCDATA  $2, $1
        0x0005 00005 (t.go:12)  PCDATA  $0, $1
        0x0005 00005 (t.go:12)  MOVQ    "".msg+8(SP), CX
        0x000a 00010 (t.go:12)  PCDATA  $2, $0
        0x000a 00010 (t.go:12)  MOVL    AX, 24(CX)
@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Aug 27, 2018

That should be ok. The nil check of msg has probably been merged with that last instruction.

@growler

This comment has been minimized.

Copy link
Contributor

@growler growler commented Aug 27, 2018

I see. That makes sense. Also, the function failing test is compiled to the same code by both versions, the only thing different is compiler's debug output:

../bin/go run run.go -- nilptr3.go
# go run run.go -- nilptr3.go

nilptr3.go:249: no match for `removed nil check` in:
	nilptr3.go:249: generated nil check
nilptr3.go:250: no match for `generated nil check` in:
	nilptr3.go:250: removed nil check
Unmatched Errors:
nilptr3.go:249: generated nil check
nilptr3.go:250: removed nil check

FAIL	nilptr3.go	0.056s
exit status 1

The failing function is

func f(t *TT) *byte {
        // See issue 17242.
        s := &t.SS  // ERROR "removed nil check"
        return &s.x // ERROR "generated nil check"
}

(Well, I don't understand what happened, but at least now it seems more logical, first compiler generates a nil check while dereferencing t, and then removes duplicated one, since s must be pointing to non-nil value). Ok, I'll test it again and will try to fill a CL, thank you!

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Aug 27, 2018

Change https://golang.org/cl/131735 mentions this issue: cmd/compile: remove unnecessary nil-check

gopherbot pushed a commit that referenced this issue Sep 4, 2018
Removes unnecessary nil-check when referencing offset from an
address. Suggested by Keith Randall in #27180.

Updates #27180

Change-Id: I326ed7fda7cfa98b7e4354c811900707fee26021
Reviewed-on: https://go-review.googlesource.com/131735
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@mundaym

This comment has been minimized.

Copy link
Member

@mundaym mundaym commented Oct 26, 2018

runtime.memhash runs into the same problem. I added a rule to replace Add(32|64) with AddPtr for ops with the unsafe.Pointer type and the code size reduced by about 10%. I don't think this is a great solution though due to the reasons listed above.

Merging constant offsets into LoweredNilCheck (as @randall77 suggested) would solve this problem for most uses of pointer arithmetic without changing any observable behavior. I wonder if we should just do that, at least for now? I'm happy to send a CL.

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Oct 30, 2018

Change https://golang.org/cl/146058 mentions this issue: cmd/compile: assume unsafe pointer arithmetic generates non-nil results

@gopherbot gopherbot closed this in 0c7762c Nov 14, 2018
@golang golang locked and limited conversation to collaborators Nov 14, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
8 participants
You can’t perform that action at this time.