search

golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
123.81k stars 17.65k forks source link

runtime: ignore map size hint if there's not enough memory? #24308

Open mfrw opened 6 years ago

mfrw commented 6 years ago

Please answer these questions before submitting your issue. Thanks!

What did you do?

go test in encoding/gob

What did you expect to see?

Passed tests

What did you see instead?

test_otpt.txt

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

No

System details

go version devel +0add9a4dcf Thu Mar 8 03:26:22 2018 +0000 linux/amd64
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/mfrw/.cache/go-build"
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/mfrw/go/go_get"
GORACE=""
GOROOT="/home/mfrw/go"
GOTMPDIR=""
GOTOOLDIR="/home/mfrw/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build389146753=/tmp/go-build -gno-record-gcc-switches"
GOROOT/bin/go version: go version devel +0add9a4dcf Thu Mar 8 03:26:22 2018 +0000 linux/amd64
GOROOT/bin/go tool compile -V: compile version devel +0add9a4dcf Thu Mar 8 03:26:22 2018 +0000
uname -sr: Linux 4.9.20-1-MANJARO
LSB Version:    n/a
Distributor ID: ManjaroLinux
Description:    Manjaro Linux
Release:    17.0.1
Codename:   Gellivara
/usr/lib/libc.so.6: GNU C Library (GNU libc) stable release version 2.25, by Roland McGrath et al.
gdb --version: GNU gdb (GDB) 7.12.1
=== RUN TestUintCodec --- PASS: TestUintCodec (0.00s) === RUN TestIntCodec --- PASS: TestIntCodec (0.00s) === RUN TestScalarEncInstructions --- PASS: TestScalarEncInstructions (0.00s) === RUN TestScalarDecInstructions --- PASS: TestScalarDecInstructions (0.00s) === RUN TestEndToEnd --- PASS: TestEndToEnd (0.00s) === RUN TestOverflow --- PASS: TestOverflow (0.00s) === RUN TestNesting --- PASS: TestNesting (0.00s) === RUN TestAutoIndirection --- PASS: TestAutoIndirection (0.00s) === RUN TestReorderedFields --- PASS: TestReorderedFields (0.00s) === RUN TestIgnoredFields --- PASS: TestIgnoredFields (0.00s) === RUN TestBadRecursiveType --- PASS: TestBadRecursiveType (0.00s) === RUN TestIndirectSliceMapArray --- PASS: TestIndirectSliceMapArray (0.00s) === RUN TestInterface --- PASS: TestInterface (0.00s) === RUN TestInterfaceBasic --- PASS: TestInterfaceBasic (0.00s) === RUN TestInterfacePointer --- PASS: TestInterfacePointer (0.00s) === RUN TestIgnoreInterface --- PASS: TestIgnoreInterface (0.00s) === RUN TestUnexportedFields --- PASS: TestUnexportedFields (0.00s) === RUN TestDebugSingleton --- PASS: TestDebugSingleton (0.00s) === RUN TestDebugStruct --- PASS: TestDebugStruct (0.00s) === RUN TestFuzz --- PASS: TestFuzz (0.00s) codec_test.go:1424: disabled; run with -gob.fuzz to enable === RUN TestFuzzRegressions --- PASS: TestFuzzRegressions (0.00s) codec_test.go:1444: disabled; run with -gob.fuzz to enable === RUN TestFuzzOneByte fatal error: runtime: out of memory runtime stack: runtime.throw(0x5b89e1, 0x16) /home/mfrw/go/src/runtime/panic.go:617 +0x80 runtime.sysMap(0xc004000000, 0xdd00000000, 0x6be7f8) /home/mfrw/go/src/runtime/mem_linux.go:156 +0xc7 runtime.(*mheap).sysAlloc(0x6a48e0, 0xdd00000000, 0x80, 0x0) /home/mfrw/go/src/runtime/malloc.go:601 +0x1d0 runtime.(*mheap).grow(0x6a48e0, 0x6e80000, 0x0) /home/mfrw/go/src/runtime/mheap.go:920 +0x42 runtime.(*mheap).allocSpanLocked(0x6a48e0, 0x6e80000, 0x6be808, 0x7f98353cbdd0) /home/mfrw/go/src/runtime/mheap.go:848 +0x337 runtime.(*mheap).alloc_m(0x6a48e0, 0x6e80000, 0xffffffffffff0100, 0x7f98353cbe08) /home/mfrw/go/src/runtime/mheap.go:692 +0x119 runtime.(*mheap).alloc.func1() /home/mfrw/go/src/runtime/mheap.go:759 +0x4d runtime.(*mheap).alloc(0x6a48e0, 0x6e80000, 0x7f9835010100, 0x4157f9) /home/mfrw/go/src/runtime/mheap.go:758 +0x8a runtime.largeAlloc(0xdd00000000, 0xc000280001, 0x7f9838545000) /home/mfrw/go/src/runtime/malloc.go:1001 +0x94 runtime.mallocgc.func1() /home/mfrw/go/src/runtime/malloc.go:896 +0x46 runtime.systemstack(0x0) /home/mfrw/go/src/runtime/asm_amd64.s:403 +0x66 runtime.mstart() /home/mfrw/go/src/runtime/proc.go:1170 goroutine 27 [running]: runtime.systemstack_switch() /home/mfrw/go/src/runtime/asm_amd64.s:363 fp=0xc000287748 sp=0xc000287740 pc=0x455360 runtime.mallocgc(0xdd00000000, 0x5970e0, 0xc0003f2b01, 0xc000287828) /home/mfrw/go/src/runtime/malloc.go:895 +0x895 fp=0xc0002877e8 sp=0xc000287748 pc=0x40bd45 runtime.newarray(0x5970e0, 0x110000000, 0x5a6da0) /home/mfrw/go/src/runtime/malloc.go:1030 +0x6a fp=0xc000287818 sp=0xc0002877e8 pc=0x40c12a runtime.makeBucketArray(0x57f520, 0xc0003edc20, 0xc000376318, 0x5) /home/mfrw/go/src/runtime/map.go:881 +0xe2 fp=0xc000287850 sp=0xc000287818 pc=0x40e672 runtime.makemap(0x57f520, 0x36f6e6502, 0xc0003edc20, 0x194) /home/mfrw/go/src/runtime/map.go:328 +0xe3 fp=0xc000287890 sp=0xc000287850 pc=0x40cd53 reflect.makemap(0x57f520, 0x36f6e6502, 0x15) /home/mfrw/go/src/runtime/map.go:1190 +0x167 fp=0xc0002878c8 sp=0xc000287890 pc=0x40f317 reflect.MakeMapWithSize(0x5dc640, 0x57f520, 0x36f6e6502, 0x1, 0x676e69646f636e65, 0x546e4f2e626f672f) /home/mfrw/go/src/reflect/value.go:2136 +0x69 fp=0xc0002878f0 sp=0xc0002878c8 pc=0x498899 encoding/gob.(*Decoder).decodeMap(0xc000376300, 0x5dc640, 0x57f520, 0xc000142820, 0x57f520, 0xc0003be3b0, 0x195, 0x5c16e8, 0x5c16a8, 0x5da720, ...) /home/mfrw/go/src/encoding/gob/decode.go:562 +0x6a9 fp=0xc0002879f8 sp=0xc0002878f0 pc=0x50a1e9 encoding/gob.(*Decoder).decOpFor.func2(0xc00021af50, 0xc000142820, 0x57f520, 0xc0003be3b0, 0x195) /home/mfrw/go/src/encoding/gob/decode.go:829 +0x97 fp=0xc000287a60 sp=0xc0002879f8 pc=0x544ad7 encoding/gob.(*Decoder).decodeStruct(0xc000376300, 0xc000142a00, 0x5a63a0, 0xc0003be360, 0x199) /home/mfrw/go/src/encoding/gob/decode.go:471 +0xc7 fp=0xc000287ae8 sp=0xc000287a60 pc=0x508fd7 encoding/gob.(*Decoder).decodeValue(0xc000376300, 0x62, 0x566a80, 0xc0003be360, 0x16) /home/mfrw/go/src/encoding/gob/decode.go:1205 +0x266 fp=0xc000287b90 sp=0xc000287ae8 pc=0x50f776 encoding/gob.(*Decoder).DecodeValue(0xc000376300, 0x566a80, 0xc0003be360, 0x16, 0x0, 0x0) /home/mfrw/go/src/encoding/gob/decoder.go:212 +0x134 fp=0xc000287bc8 sp=0xc000287b90 pc=0x510ac4 encoding/gob.(*Decoder).Decode(0xc000376300, 0x566a80, 0xc0003be360, 0xc000287cc8, 0xc000287cb0) /home/mfrw/go/src/encoding/gob/decoder.go:187 +0x18b fp=0xc000287c30 sp=0xc000287bc8 pc=0x5108eb encoding/gob.TestFuzzOneByte.func1(0xc0000c14a0, 0xc000287cc8, 0xc000287cb0, 0xc0003bc6c0, 0x112, 0x120, 0xc0003be360) /home/mfrw/go/src/encoding/gob/codec_test.go:1499 +0xe0 fp=0xc000287c68 sp=0xc000287c30 pc=0x545950 encoding/gob.TestFuzzOneByte(0xc0000c14a0) /home/mfrw/go/src/encoding/gob/codec_test.go:1501 +0x630 fp=0xc000287fa8 sp=0xc000287c68 pc=0x52ff50 testing.tRunner(0xc0000c14a0, 0x5c13a8) /home/mfrw/go/src/testing/testing.go:788 +0xc3 fp=0xc000287fd0 sp=0xc000287fa8 pc=0x4c2183 runtime.goexit() /home/mfrw/go/src/runtime/asm_amd64.s:1379 +0x1 fp=0xc000287fd8 sp=0xc000287fd0 pc=0x457431 created by testing.(*T).Run /home/mfrw/go/src/testing/testing.go:835 +0x2c5 goroutine 1 [chan receive]: testing.(*T).Run(0xc0000c14a0, 0x5b653c, 0xf, 0x5c13a8, 0x46d301) /home/mfrw/go/src/testing/testing.go:836 +0x2ec testing.runTests.func1(0xc0000c0000) /home/mfrw/go/src/testing/testing.go:1078 +0x64 testing.tRunner(0xc0000c0000, 0xc000057df8) /home/mfrw/go/src/testing/testing.go:788 +0xc3 testing.runTests(0xc00000c7e0, 0x69d6a0, 0x5c, 0x5c, 0x40b7a1) /home/mfrw/go/src/testing/testing.go:1076 +0x2a1 testing.(*M).Run(0xc0000be000, 0x0) /home/mfrw/go/src/testing/testing.go:993 +0x165 main.main() _testmain.go:260 +0x13d exit status 2 FAIL encoding/gob 0.698s
andybons commented 6 years ago

/cc @aclements

0xmohit commented 6 years ago

git bisect points to 2b415549b813ba36caafa34fc34d72e47ee8335c.

mvdan commented 6 years ago

@mfrw could you provide information about your hardware, such as the memory size and if you use any swap? None of the builders seem to have seen this panic, so maybe it's got something to do with the machine.

Also, is it just a flake, or does it happen every single time you run go test?

mfrw commented 6 years ago

@mvdan My ram is 8 Gb and yes I do use swap (8 Gb). No, I think its something weird, it passes all.bash but when I go inside the encode/gob package and test, it breaks. NOTE: It did not break on go1.10. Btw I tried to test it on my mac and it still broke.

=== RUN   TestFuzzRegressions
--- PASS: TestFuzzRegressions (0.00s)
        codec_test.go:1444: disabled; run with -gob.fuzz to enable
=== RUN   TestFuzzOneByte
signal: killed
FAIL    encoding/gob    65.392s
mvdan commented 6 years ago

Actually, I can reproduce it too on my linux laptop with 8GB of memory and no swap.

mvdan commented 6 years ago

The problem seems to be that the decoder ends up calling reflect.MakeMapWithSize with a size of 14754407682. Which can explain why the runtime then fails to allocate this much memory.

But what I don't understand is why @aclements' change to the runtime makes it suddenly fail. I also don't understand what happened earlier with such a large map creation.

josharian commented 6 years ago

Somewhat related: https://github.com/golang/go/issues/20221

mvdan commented 6 years ago

I'll send a CL now skipping this index, pending a proper fix in either runtime or gob.

gopherbot commented 6 years ago

Change https://golang.org/cl/99655 mentions this issue: encoding/gob: work around TestFuzzOneByte panic

mvdan commented 6 years ago

The test is passing on my machine now, with the test case being skipped. @aclements, would you like to keep this issue open to investigate if there's anything to fix in the runtime? If not, we can simply keep @josharian's previous issue to decide whether or not the gob package should handle malicious input gracefully.

bradfitz commented 6 years ago

To summarize, the open question is whether the runtime should ignore the map size hint if there's not enough memory to allocate it:

$ cat map.go 
package main

func main() {
        m := make(map[string]string, 14754407682)
        println(len(m))
}

$ go run map.go
fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x46db4e, 0x16)
        /home/bradfitz/go/src/runtime/panic.go:589 +0x6a
runtime.sysMap(0xc004000000, 0x12100000000, 0x4d6bb8)
        /home/bradfitz/go/src/runtime/mem_linux.go:156 +0xc7
runtime.(*mheap).sysAlloc(0x4be660, 0x12100000000, 0x0, 0x7fffca2fd298)
        /home/bradfitz/go/src/runtime/malloc.go:611 +0x1c7
runtime.(*mheap).grow(0x4be660, 0x9080000, 0x0)
        /home/bradfitz/go/src/runtime/mheap.go:920 +0x42
runtime.(*mheap).allocSpanLocked(0x4be660, 0x9080000, 0x4d6bc8, 0x20300000000000)
        /home/bradfitz/go/src/runtime/mheap.go:848 +0x337
runtime.(*mheap).alloc_m(0x4be660, 0x9080000, 0x410100, 0x7fa22a673a00)
        /home/bradfitz/go/src/runtime/mheap.go:692 +0x119
runtime.(*mheap).alloc.func1()
        /home/bradfitz/go/src/runtime/mheap.go:759 +0x4c
runtime.(*mheap).alloc(0x4be660, 0x9080000, 0x7fffca010100, 0x40fef5)
        /home/bradfitz/go/src/runtime/mheap.go:758 +0x8a
runtime.largeAlloc(0x12100000000, 0x440001, 0x7fa22c880000)
        /home/bradfitz/go/src/runtime/malloc.go:1011 +0x97
runtime.mallocgc.func1()
        /home/bradfitz/go/src/runtime/malloc.go:906 +0x46
runtime.systemstack(0x446549)
        /home/bradfitz/go/src/runtime/asm_amd64.s:351 +0x66
runtime.mstart()
        /home/bradfitz/go/src/runtime/proc.go:1223

goroutine 1 [running]:
runtime.systemstack_switch()
        /home/bradfitz/go/src/runtime/asm_amd64.s:311 fp=0xc0000345e0 sp=0xc0000345d8 pc=0x446640
runtime.mallocgc(0x12100000000, 0x463400, 0x444001, 0x7fa22c880000)
        /home/bradfitz/go/src/runtime/malloc.go:905 +0x896 fp=0xc000034680 sp=0xc0000345e0 pc=0x409f06
runtime.newarray(0x463400, 0x110000000, 0xf)
        /home/bradfitz/go/src/runtime/malloc.go:1040 +0x6a fp=0xc0000346b0 sp=0xc000034680 pc=0x40a27a
runtime.makeBucketArray(0x45c5e0, 0x20, 0x0, 0x0, 0x4ba3a0)
        /home/bradfitz/go/src/runtime/map.go:355 +0x184 fp=0xc0000346e8 sp=0xc0000346b0 pc=0x40b064
runtime.makemap(0x45c5e0, 0x36f6e6502, 0xc000034758, 0xc000074058)
        /home/bradfitz/go/src/runtime/map.go:321 +0xec fp=0xc000034730 sp=0xc0000346e8 pc=0x40adcc
main.main()
        /home/bradfitz/map.go:4 +0x5c fp=0xc000034798 sp=0xc000034730 pc=0x44e55c
runtime.main()
        /home/bradfitz/go/src/runtime/proc.go:201 +0x207 fp=0xc0000347e0 sp=0xc000034798 pc=0x4237e7
runtime.goexit()
        /home/bradfitz/go/src/runtime/asm_amd64.s:1333 +0x1 fp=0xc0000347e8 sp=0xc0000347e0 pc=0x448591
exit status 2

@aclements, @randall77, is this cool?

ianlancetaylor commented 6 years ago

We've agreed in the past that the hint passed to make for a map is only a hint. If we can't allocate enough memory to satisfy the hint, we should ignore it. See #19926. So this is a bug.

martisch commented 6 years ago

If its decided to make map buckets not allocate due to insufficient ram it would be nice to allow this check to be not enforced for small maps. e.g. up to 64 elements and for stack allocated buckets for performance (small local maps) and implementation complexity. Also if maps are small and allocation would fail its more likely another allocation might fail soon which cant be avoided.

randall77 commented 6 years ago

@ianlancetaylor I don't think that's what we decided. Reading over the comments on CL 40854, we only prevent panics for obviously bad hints (negative hints, or those which would require allocations larger than the max heap).

We discussed this today. We decided that we should never panic() because of a bad hint, but out of memory is ok. As a practical matter, that means 1) if hint < 0 { hint = 0 } 2) if computing the malloc size overflows an int64, or _MaxMem, set hint = 0. (take newarray's logic and copy it into hinit, replacing panic with hint=0) 3) proceed as before Those who are really passing adversarial data as a hint need to sanitize it first. It seems hard to sanitize the hint inside the map implementation in the general case.

ianlancetaylor commented 6 years ago

@randall77 Huh, I guess I misremember. So in that case, this is a bug in encoding/gob?

I understand that it is hard to handle a very large hint in the runtime, but it's even harder to handle in packages outside the runtime. I see that I tried to argue that in the CL also. If I was in the discussion you mention, I've forgotten about it.