cmd/compile: checking len(data) and erroring out if too small does not help BCE #19126

navytux · 2017-02-16T18:42:15Z

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

The text was updated successfully, but these errors were encountered:

bradfitz · 2017-02-16T19:30:59Z

/cc @dr2chase

randall77 · 2017-02-16T20:11:12Z

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 · 2017-02-16T20:29:59Z

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

randall77 · 2017-02-16T20:36:50Z

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

navytux · 2017-02-17T09:01:38Z

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 · 2018-01-13T10:46:43Z

/cc @aclements

dgryski · 2018-01-18T18:48:01Z

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 · 2018-01-19T08:59:18Z

@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 · 2018-03-13T02:54:40Z

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.

gopherbot · 2019-09-06T17:12:34Z

Change https://golang.org/cl/193838 mentions this issue: cmd/compile: make prove trace OpAdd64 and OpMakeSlice:

bradfitz added the Performance label Feb 16, 2017

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

navytux mentioned this issue Mar 22, 2017

cmd/compile: teach BCE about copy return value #16833

Open

bradfitz added the NeedsFix The path to resolution is known, but the work has not been done. label Jun 29, 2017

bradfitz modified the milestones: Go1.10, Go1.9Maybe Jun 29, 2017

bradfitz modified the milestones: Go1.10, Go1.11 Nov 28, 2017

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

This was referenced Nov 11, 2019

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

Closed

cmd/compile: optimize XOR masking code #31586

Closed

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: checking len(data) and erroring out if too small does not help BCE #19126

cmd/compile: checking len(data) and erroring out if too small does not help BCE #19126

navytux commented Feb 16, 2017

bradfitz commented Feb 16, 2017

randall77 commented Feb 16, 2017

dr2chase commented Feb 16, 2017

randall77 commented Feb 16, 2017

navytux commented Feb 17, 2017

rasky commented Jan 13, 2018

dgryski commented Jan 18, 2018

navytux commented Jan 19, 2018

rasky commented Mar 13, 2018 •

edited

gopherbot commented Sep 6, 2019

cmd/compile: checking len(data) and erroring out if too small does not help BCE #19126

cmd/compile: checking len(data) and erroring out if too small does not help BCE #19126

Comments

navytux commented Feb 16, 2017

What did you do?

What did you expect to see?

What did you see instead?

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

Possibly related issues:

System details

bradfitz commented Feb 16, 2017

randall77 commented Feb 16, 2017

dr2chase commented Feb 16, 2017

randall77 commented Feb 16, 2017

navytux commented Feb 17, 2017

rasky commented Jan 13, 2018

dgryski commented Jan 18, 2018

navytux commented Jan 19, 2018

rasky commented Mar 13, 2018 • edited

gopherbot commented Sep 6, 2019

rasky commented Mar 13, 2018 •

edited