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
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@FlorianUekermann
Copy link
Contributor

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 the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 23, 2018
@ianlancetaylor ianlancetaylor added this to the Go1.12 milestone Aug 23, 2018
@growler
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor Author

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
Copy link
Contributor

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

@randall77
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor Author

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
Copy link
Contributor Author

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

@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
Copy link
Contributor

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

@growler
Copy link
Contributor

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
Copy link
Contributor

Ship it!

@randall77
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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

@growler
Copy link
Contributor

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
Copy link

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
Copy link
Member

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
Copy link

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

@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.
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
Development

No branches or pull requests

8 participants