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

x/exp/slices: memory leak on Delete #54650

Open
Deleplace opened this issue Aug 24, 2022 · 6 comments
Open

x/exp/slices: memory leak on Delete #54650

Deleplace opened this issue Aug 24, 2022 · 6 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@Deleplace
Copy link

Deleplace commented Aug 24, 2022

What version of Go are you using (go version)?

$ go version
go version go1.19 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/deleplace/Library/Caches/go-build"
GOENV="/Users/deleplace/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/deleplace/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/deleplace/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.19"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/deleplace/git/go.googlesource.com/exp/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/p4/g7fnpss96g5708_mmv3cxzgh0000gn/T/go-build1427867040=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

The current implementation of slices.Delete is very straightforward but it has a number of drawbacks:

  1. When removing M elements (M==j-i), all elements beyond j are shifted M positions to the left. This means that M values on the right are now beyond the length of the result slice, but still within capacity, and still reachable through the original slice argument. If the elements are references or pointers or contain pointers, then these elements won't be GC'ed, which is a memory leak.
  2. There is no reason for these M values on the right to be reachable at all from any slice header. Zeroed values would make more sense.
  3. There is no check to make sure that i<=j, and the case i>j yields a result that violates the documentation of Delete.

I suggest fixing this by explicitly zeroing the tail of the original slice, and by explicitly checking that i<=j.

The problematic behaviors and suggested fix are shown at https://go.dev/play/p/ZhX_LRGm9N1

The memory leak (1) doesn't exist for non-pointer value types.

Zeroing the right tail fixes (1) for pointer types and changes the values visible from the original slice header. This is okay because Delete is a destructive function and makes no promise to keep the extra capacity unchanged.

The documentation says "Delete panics if s[i:j] is not a valid slice of s." which is currently not true because s[2:1] is not a valid slice (see https://go.dev/play/p/ftvpm65GGzL) but instead of panicking, Delete produces non-sensical results (see https://go.dev/play/p/sIJRru2sGPa). The new suggested implementation fixes this bug.

I will send a change containing the suggested implementation, and extra test cases.

@gopherbot
Copy link

gopherbot commented Aug 24, 2022

Change https://go.dev/cl/425209 mentions this issue: slices: fix memory leaks and invalid inputs

@gopherbot
Copy link

gopherbot commented Aug 24, 2022

Change https://go.dev/cl/425209 mentions this issue: slices: fix memory leaks and invalid inputs in Delete

@seankhliao seankhliao changed the title golang.org/x/exp/slices: memory leak on Delete x/exp/slices: memory leak on Delete Aug 24, 2022
@seankhliao seankhliao added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 24, 2022
@gopherbot gopherbot added this to the Unreleased milestone Aug 24, 2022
@gopherbot
Copy link

gopherbot commented Aug 26, 2022

Change https://go.dev/cl/425894 mentions this issue: slices.Delete: fix behavior on invalid slice indices arguments

@gopherbot
Copy link

gopherbot commented Aug 26, 2022

Change https://go.dev/cl/425895 mentions this issue: slices.Delete: explain memory leak in func comments.

gopherbot pushed a commit to golang/exp that referenced this issue Aug 26, 2022
Now doing an explicit bounds check, to panic on invalid indices

Fixes part (3) of golang/go#54650

Change-Id: I62a70c0f866e6c336d0c7feae5af33272fc568b6
Reviewed-on: https://go-review.googlesource.com/c/exp/+/425894
Auto-Submit: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
gopherbot pushed a commit to golang/exp that referenced this issue Aug 27, 2022
Mitigates golang/go#54650

Change-Id: I899094ec6af8d3b1985e737a5318e9776b4cb1a9
Reviewed-on: https://go-review.googlesource.com/c/exp/+/425895
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
@Deleplace
Copy link
Author

Deleplace commented Aug 30, 2022

Current status:

  • implemented and merged: bounds check
  • implemented and merged: doc warning about Delete not zeroing the "right tail" elements
  • not implemented: zeroing the "right tail" elements to prevent memory leaks

@beoran
Copy link

beoran commented Sep 8, 2022

@Deleplace I would think that in stead of documenting the memory leak, it should be fixed. Otherwise people will have to implement their own safer Delete.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

4 participants