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: checking len(data) and erroring out if too small does not help BCE #19126

Open
navytux opened this Issue Feb 16, 2017 · 9 comments

Comments

Projects
None yet
6 participants
@navytux
Contributor

navytux commented Feb 16, 2017

Please answer these questions before submitting your issue. Thanks!

What did you do?

Hello up there. In my program there are many autogenerated packet decoder/encoders. A simple decoder looks like this:

package main

import (
        "encoding/binary"
        "errors"
)

type MyData struct {
        x uint32
        y uint32
        z uint64
        w uint64
}

var ErrDecodeOverflow = errors.New("decode: bufer overflow")

func (d *MyData) Decode(data []byte) (int, error) {
        if len(data) < 24 {
                goto overflow
        }

        d.x = binary.BigEndian.Uint32(data[0:])
        d.y = binary.BigEndian.Uint32(data[4:])
        d.z = binary.BigEndian.Uint64(data[8:])
        d.w = binary.BigEndian.Uint64(data[16:])
        return 24, nil

overflow:
        return 0, ErrDecodeOverflow
}

(https://play.golang.org/p/BganWzetvq)

The decoder explicitly cares to first check whether len(data) is too small and if so returns via goto overflow.

What did you expect to see?

Code generated for main Decode part does not have bound checks.

What did you see instead?

Compiled assembly has many bound checks:

"".(*MyData).Decode t=1 size=256 args=0x38 locals=0x8
        0x0000 00000 (x.go:17)  TEXT    "".(*MyData).Decode(SB), $8-56
        0x0000 00000 (x.go:17)  SUBQ    $8, SP
        0x0004 00004 (x.go:17)  MOVQ    BP, (SP)
        0x0008 00008 (x.go:17)  LEAQ    (SP), BP
        0x000c 00012 (x.go:17)  FUNCDATA        $0, gclocals·21e863e2261befa92f8534560680bbb6(SB)
        0x000c 00012 (x.go:17)  FUNCDATA        $1, gclocals·69c1753bd5f81501d95132d08af04464(SB)
        0x000c 00012 (x.go:18)  MOVQ    "".data+32(FP), AX
        0x0011 00017 (x.go:18)  CMPQ    AX, $24
        0x0015 00021 (x.go:18)  JLT     $0, 214
        0x001b 00027 (x.go:22)  MOVQ    "".data+24(FP), CX
        0x0020 00032 (x.go:22)  MOVL    (CX), DX
        0x0022 00034 (x.go:22)  BSWAPL  DX
        0x0024 00036 (x.go:22)  MOVQ    "".d+16(FP), BX
        0x0029 00041 (x.go:22)  MOVL    DX, (BX)
        0x002b 00043 (x.go:23)  LEAQ    -4(AX), DX
        0x002f 00047 (x.go:23)  MOVQ    "".data+40(FP), SI
        0x0034 00052 (x.go:23)  LEAQ    -4(SI), DI
        0x0038 00056 (x.go:23)  NEGQ    DI
        0x003b 00059 (x.go:23)  SARQ    $63, DI
        0x003f 00063 (x.go:23)  ANDQ    $4, DI
        0x0043 00067 (x.go:23)  CMPQ    DX, $3
        0x0047 00071 (x.go:23)  JLS     $0, 207                         <--
        0x004d 00077 (x.go:23)  MOVL    (CX)(DI*1), DX
        0x0050 00080 (x.go:23)  BSWAPL  DX
        0x0052 00082 (x.go:23)  MOVL    DX, 4(BX)
        0x0055 00085 (x.go:24)  LEAQ    -8(AX), DX
        0x0059 00089 (x.go:24)  LEAQ    -8(SI), DI
        0x005d 00093 (x.go:24)  NEGQ    DI
        0x0060 00096 (x.go:24)  SARQ    $63, DI
        0x0064 00100 (x.go:24)  ANDQ    $8, DI
        0x0068 00104 (x.go:24)  CMPQ    DX, $7
        0x006c 00108 (x.go:24)  JLS     $0, 200                         <--
        0x006e 00110 (x.go:24)  MOVQ    (CX)(DI*1), DX
        0x0072 00114 (x.go:24)  BSWAPQ  DX
        0x0075 00117 (x.go:24)  MOVQ    DX, 8(BX)
        0x0079 00121 (x.go:25)  LEAQ    -16(SI), DX
        0x007d 00125 (x.go:25)  NEGQ    DX
        0x0080 00128 (x.go:25)  ADDQ    $-16, AX
        0x0084 00132 (x.go:25)  SARQ    $63, DX
        0x0088 00136 (x.go:25)  ANDQ    $16, DX
        0x008c 00140 (x.go:25)  CMPQ    AX, $7
        0x0090 00144 (x.go:25)  JLS     $0, 193                         <--
        0x0092 00146 (x.go:25)  MOVQ    (CX)(DX*1), AX
        0x0096 00150 (x.go:25)  BSWAPQ  AX
        0x0099 00153 (x.go:25)  MOVQ    AX, 16(BX)
        0x009d 00157 (x.go:26)  MOVQ    $24, "".~r1+48(FP)
        0x00a6 00166 (x.go:26)  MOVQ    $0, "".~r2+56(FP)
        0x00af 00175 (x.go:26)  MOVQ    $0, "".~r2+64(FP)
        0x00b8 00184 (x.go:26)  MOVQ    (SP), BP
        0x00bc 00188 (x.go:26)  ADDQ    $8, SP
        0x00c0 00192 (x.go:26)  RET
        0x00c1 00193 (x.go:25)  PCDATA  $0, $1
        0x00c1 00193 (x.go:25)  CALL    runtime.panicindex(SB)          <--
        0x00c6 00198 (x.go:25)  UNDEF
        0x00c8 00200 (x.go:24)  PCDATA  $0, $1
        0x00c8 00200 (x.go:24)  CALL    runtime.panicindex(SB)          <--
        0x00cd 00205 (x.go:24)  UNDEF
        0x00cf 00207 (x.go:23)  PCDATA  $0, $1
        0x00cf 00207 (x.go:23)  CALL    runtime.panicindex(SB)          <--
        0x00d4 00212 (x.go:23)  UNDEF
        0x00d6 00214 (x.go:29)  MOVQ    "".ErrDecodeOverflow(SB), AX
        0x00dd 00221 (x.go:29)  MOVQ    "".ErrDecodeOverflow+8(SB), CX
        0x00e4 00228 (x.go:29)  MOVQ    $0, "".~r1+48(FP)
        0x00ed 00237 (x.go:29)  MOVQ    AX, "".~r2+56(FP)
        0x00f2 00242 (x.go:29)  MOVQ    CX, "".~r2+64(FP)
        0x00f7 00247 (x.go:29)  MOVQ    (SP), BP
        0x00fb 00251 (x.go:29)  ADDQ    $8, SP
        0x00ff 00255 (x.go:29)  RET

Does this issue reproduce with the latest release (go1.7.5)?

Yes, with both go1.7.4 and go1.8

Possibly related issues:

#17370
#16092
#15074

System details

go version devel +990124da2a Thu Feb 16 17:52:15 2017 +0000 linux/amd64
GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/kirr/go"
GORACE=""
GOROOT="/home/kirr/src/tools/go/go"
GOTOOLDIR="/home/kirr/src/tools/go/go/pkg/tool/linux_amd64"
GCCGO="/usr/bin/gccgo"
CC="gcc"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build151449272=/tmp/go-build -gno-record-gcc-switches"
CXX="g++"
CGO_ENABLED="1"
PKG_CONFIG="pkg-config"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
GOROOT/bin/go version: go version devel +990124da2a Thu Feb 16 17:52:15 2017 +0000 linux/amd64
GOROOT/bin/go tool compile -V: compile version devel +990124da2a Thu Feb 16 17:52:15 2017 +0000 X:framepointer
uname -sr: Linux 4.9.0-1-amd64
Distributor ID:	Debian
Description:	Debian GNU/Linux 9.0 (stretch)
Release:	9.0
Codename:	stretch
/lib/x86_64-linux-gnu/libc.so.6: GNU C Library (Debian GLIBC 2.24-9) stable release version 2.24, by Roland McGrath et al.
gdb --version: GNU gdb (Debian 7.12-6) 7.12.0.20161007-git

/cc @randall77

@bradfitz bradfitz added this to the Go1.9Maybe milestone Feb 16, 2017

@bradfitz

This comment has been minimized.

Member

bradfitz commented Feb 16, 2017

/cc @dr2chase

@randall77

This comment has been minimized.

Contributor

randall77 commented Feb 16, 2017

I thought that the fix for #16813 would help here. I thought wrong.

There's probably a x >= c implies x-d >= c-d implication that needs to be added to BCE.

@dr2chase

This comment has been minimized.

Contributor

dr2chase commented Feb 16, 2017

That implication requires inference of no over/underflow.
MAXINT >= c is true, but MAXINT-(-1) >= c-(-1) is usually false.

@randall77

This comment has been minimized.

Contributor

randall77 commented Feb 16, 2017

This would only be for constants c, d >= 0, which I think makes it always work.

@navytux

This comment has been minimized.

Contributor

navytux commented Feb 17, 2017

Thanks for feedback. Indeed it is a x >= c -> x + d >= c + d issue - for first data[:0] decoding there is already no bound check emitted (d = 0 there).

Looking forward for this to be eventually improved.

Thanks again,
Kirill

@rasky

This comment has been minimized.

Member

rasky commented Jan 13, 2018

@dgryski

This comment has been minimized.

Contributor

dgryski commented Jan 18, 2018

If the slices access are written as

      d.x = binary.BigEndian.Uint32(data[0:4])
      d.y = binary.BigEndian.Uint32(data[4:8])
      d.z = binary.BigEndian.Uint64(data[8:16])
      d.w = binary.BigEndian.Uint64(data[16:24])

Then the bounds checks are correctly removed.

I saw a similar issue with dgryski/go-metro@1308eab but I assumed it was because the bounds check "proof" (that len(ptr) >= 32) was invalidated when ptr was reassigned, even though it should have been possible to determine that the resulting accesses were safe.

@navytux

This comment has been minimized.

Contributor

navytux commented Jan 19, 2018

@dgryski thanks for information about workaround. I confirm that with

 17 func (d *MyData) Decode(data []byte) (int, error) {
 18         if len(data) < 24 {
 19                 goto overflow
 20         }
 21 
 22         d.x = binary.BigEndian.Uint32(data[0:0+4])
 23         d.y = binary.BigEndian.Uint32(data[4:4+4])
 24         d.z = binary.BigEndian.Uint64(data[8:8+8])
 25         d.w = binary.BigEndian.Uint64(data[16:16+8])
 26         return 24, nil
 27 
 28 overflow:
 29         return 0, ErrDecodeOverflow
 30 }

and both either go19 or today's tip Decode becomes something like (tip version below):

TEXT ·(*MyData).Decode(SB), NOSPLIT, $0-56 // bce.go:17
        NO_LOCAL_POINTERS
        // FUNCDATA $0, gclocals·846769608458630ae82546dab39e913e(SB) (args)
        // FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) (no locals)
        MOVQ       data+24(SP), AX
        CMPQ       AX, $24                        // bce.go:18
        JGE        pc45
        MOVQ       ·ErrDecodeOverflow+8(SB), AX  // bce.go:29
        MOVQ       ·ErrDecodeOverflow(SB), CX
        MOVQ       $0, _r1+40(SP)
        MOVQ       CX, _r2+48(SP)
        MOVQ       AX, _r2+56(SP)
        RET
pc45:
        MOVQ       data+16(SP), AX
        MOVL       (AX), CX                       // bce.go:22
        BSWAPL     CX
        MOVQ       d+8(SP), DX
        MOVL       CX, (DX)
        MOVL       4(AX), CX                      // bce.go:23
        BSWAPL     CX
        MOVL       CX, 4(DX)
        MOVQ       8(AX), CX                      // bce.go:24
        BSWAPQ     CX
        MOVQ       CX, 8(DX)
        MOVQ       16(AX), AX                     // bce.go:25
        BSWAPQ     AX
        MOVQ       AX, 16(DX)
        MOVQ       $24, _r1+40(SP)                // bce.go:26
        XORPS      X0, X0
        MOVUPS     X0, _r2+48(SP)
        RET

From this offhand I would say for original case it seems to be there is some BCE-related information lost somehow when inlining.

@rasky

This comment has been minimized.

Member

rasky commented Mar 13, 2018

The problem here is that in code like data[4:], the slice has length len(data)-4, and the last element accessed has index 4+3=7, and thus the compiler needs to prove that 7 < len(data)-4, knowing data len(data) >= 24.

@bradfitz bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment