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

sort: go 1.6 panic: runtime error: index out of range #14377

Closed
stevenh opened this issue Feb 18, 2016 · 22 comments
Closed

sort: go 1.6 panic: runtime error: index out of range #14377

stevenh opened this issue Feb 18, 2016 · 22 comments
Milestone

Comments

@stevenh
Copy link
Contributor

@stevenh stevenh commented Feb 18, 2016

It looks like the recent sort improvements, released in go 1.6 result in a runtime panic: index out of range

After updating to go 1.6 a simple sort that was working fine in 1.5.3 now causes a panic: runtime error: index out of range.

I added some debugging to try can catch it in the act and it seems like go 1.6's sort may be broken.

Output:

LEN: 189
LEN: 189 i: 95 j: 189
panic: runtime error: index out of range

I should never see that second LEN call as it means that sort called Less with i or j >= Len().

Code snippet

func (ba Sorter) Len() int {
        fmt.Println("LEN:", len(ba))
        return len(ba)
}

func (ba Sorter) Less(i, j int) bool {
        if len(ba) <= i || len(ba) <= j {
                fmt.Println("LEN:", len(ba), "i:", i, "j:", j)
        }
        a, b := ba[i], ba[j] // <-- Panic happens here
...
}

func (ba Sorter) Swap(i, j int) {
        ba[i], ba[j] = ba[j], ba[i]
} 

Reverting: e71d640 makes the problem go away.

panic: runtime error: index out of range

goroutine 23 [running]:
panic(0x8a4440, 0xc82000e100)
        /usr/local/go/src/runtime/panic.go:464 +0x3e6
Sorter.Less(0xc82018a000, 0xd6, 0x3e8, 0x1d, 0xffffffffffffffff, 0x1)
        sort.go:19 +0x41f
(*Sorter).Less(0xc820fc83c0, 0x1d, 0xffffffffffffffff, 0x1)
        <autogenerated>:471 +0xb5
sort.doPivot(0x800d81000, 0xc820fc83c0, 0x1d, 0x35, 0x1a, 0x3d)
        /usr/local/go/src/sort/sort.go:128 +0x27b
sort.quickSort(0x800d81000, 0xc820fc83c0, 0x1d, 0x35, 0xc)
        /usr/local/go/src/sort/sort.go:195 +0xa3
sort.quickSort(0x800d81000, 0xc820fc83c0, 0x0, 0x35, 0xd)
        /usr/local/go/src/sort/sort.go:202 +0x12a
sort.quickSort(0x800d81000, 0xc820fc83c0, 0x0, 0xd6, 0xf)
        /usr/local/go/src/sort/sort.go:199 +0xfe
sort.Sort(0x800d81000, 0xc820fc83c0)
        /usr/local/go/src/sort/sort.go:229 +0x74
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 18, 2016

Can you show us a complete program that reproduces the problem?

@ianlancetaylor ianlancetaylor added this to the Go1.6.1 milestone Feb 18, 2016
@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 18, 2016

Or at least the complete Less function.

(Does Go now require Less to be a strict weak ordering like the STL in C++?)

@cespare
Copy link
Contributor

@cespare cespare commented Feb 18, 2016

On golang-nuts @stevenh mentioned that the program has a data race.

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 18, 2016

@cespare, thanks. Indeed, from golang-nuts:

The fields being sorted by do indeed have a data race, however ...

No "howevers". Data race = no promises.

@bradfitz bradfitz closed this Feb 18, 2016
@stevenh
Copy link
Contributor Author

@stevenh stevenh commented Feb 18, 2016

Here's the full version of Less.

func (ba Sorter) Less(i, j int) bool {
if len(ba) <= i || len(ba) <= j {
fmt.Println("LEN:", len(ba), "i:", i, "j:", j)
}
a, b := ba[i], ba[j]

     if a.VirtualType() < b.VirtualType() {
             return true
     } else if b.VirtualType() < a.VirtualType() {
             return false
     }

     aAlloc := a.Allocated()
     bAlloc := b.Allocated()
     if aAlloc > bAlloc {
             return true
     } else if bAlloc > aAlloc {
             return false
     }

     if a.LastUsed().After(b.LastUsed()) {
             return true
     } else if b.LastUsed().After(a.LastUsed()) {
             return false
     }

     return a.ID() < b.ID()

}

-race identified that LastUsed is racey, but it didn't race on the sort
run which paniced.

On 18/02/2016 04:21, Brad Fitzpatrick wrote:

Or at least the complete Less function.

(Does Go now require Less to be a strict weak ordering like the STL in
C++?)


Reply to this email directly or view it on GitHub
#14377 (comment).

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 18, 2016

Feel free to re-open this bug if you have a complete stand-alone race-free repro.

But if there's a bug, somebody else will hit it. Everybody uses sort. The fact that we haven't seen it already suggests it is due to your race.

@hamaxx
Copy link
Contributor

@hamaxx hamaxx commented Feb 18, 2016

We had a similar issue with one of our sorts where comparison was not deterministic (we used random as a tiebreaker). It makes sense that it should be, but it might be a good idea to either document it or produce a more explicit error message.

Example that "works" in go 1.5 but crashes in 1.6:

package main

import (
    "math/rand"
    "sort"
)

type Test struct{}

type TestSort []*Test

func (v TestSort) Len() int {
    return len(v)
}
func (v TestSort) Swap(i, j int) {
    v[i], v[j] = v[j], v[i]
}
func (v TestSort) Less(i, j int) bool {
    return rand.Float32() < 0.5
}

func main() {
    results := []*Test{}
    for i := 0; i < 100; i++ {
        results = append(results, &Test{})
    }
    sort.Sort(TestSort(results))
}
@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 18, 2016

@hamaxx, thanks!

I can confirm:

bradfitz@laptop ~$ GOROOT=$HOME/go1.4 go run sort.go
bradfitz@laptop ~$ GOROOT=$HOME/go1.5 go run sort.go
bradfitz@laptop ~$ GOROOT=$HOME/go go run sort.go
panic: runtime error: index out of range

goroutine 1 [running]:
panic(0x66280, 0xc82000a080)
    /Users/bradfitz/go/src/runtime/panic.go:464 +0x3e6
main.(*TestSort).Swap(0xc82000e1c0, 0x62, 0xffffffffffffffff)
    <autogenerated>:2 +0x14b
sort.doPivot(0x13d088, 0xc82000e1c0, 0x0, 0x64, 0xc82000e1c0, 0x18)
    /Users/bradfitz/go/src/sort/sort.go:134 +0x5ea
sort.quickSort(0x13d088, 0xc82000e1c0, 0x0, 0x64, 0xd)
    /Users/bradfitz/go/src/sort/sort.go:195 +0xa3
sort.Sort(0x13d088, 0xc82000e1c0)
    /Users/bradfitz/go/src/sort/sort.go:229 +0x74
main.main()
    /Users/bradfitz/sort.go:27 +0x139
exit status 2
@bradfitz bradfitz reopened this Feb 18, 2016
@hamaxx
Copy link
Contributor

@hamaxx hamaxx commented Feb 18, 2016

I didn't look too deeply into it, but I think it might be pretty easy to just fix the issue for the next release:

--- orig/sort.go    2016-02-18 18:22:08.837326357 +0100
+++ sort.go 2016-02-19 17:18:50.180761240 +0100
@@ -119,15 +119,15 @@
    pivot := lo
    a, c := lo+1, hi-1

-   for ; a != c && data.Less(a, pivot); a++ {
+   for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
-       for ; b != c && !data.Less(pivot, b); b++ { // data[b] <= pivot
+       for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
-       for ; b != c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
+       for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
-       if b == c {
+       if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
@@ -167,11 +167,11 @@
        //  data[a <= i < b] unexamined
        //  data[b <= i < c] = pivot
        for {
-           for ; a != b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
+           for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
-           for ; a != b && data.Less(a, pivot); a++ { // data[a] < pivot
+           for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
-           if a == b {
+           if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
@funny-falcon
Copy link
Contributor

@funny-falcon funny-falcon commented Feb 21, 2016

I didn't thought about "random tie breaker" when i've changed comparison to inequality check.

While I think "random tie breaker" is not a good thing, it is sometimes useful. So patch should be applied.

Had someone sent already change for review?

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 21, 2016

@funny-falcon, no, there is no patch yet. It would be referenced here automatically if so. Want to send one?

@funny-falcon
Copy link
Contributor

@funny-falcon funny-falcon commented Feb 21, 2016

@hamaxx wrote it already in his comments (both test case and fix), so if he wants to make a patch, i will not cross his way.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Feb 21, 2016

Aside: I would recommend against the "random tie breaker" method. While I do think the index out of bound panic should be fixed, I don't think sort.Sort makes any guarantees about the output ordering when Less is not a deterministic total ordering function. (And the random tie breaker method violates both determinism and total ordering.)

@funny-falcon
Copy link
Contributor

@funny-falcon funny-falcon commented Feb 22, 2016

@mdempsky if you are team leader, you shall not allow "random tie breaker" to be merged into master. "rtb" is really a hack.

But if you makes personal project, then it is "quick and dirty" way to "sort by priority and get some random elements from min/max/mean priority".

Is Go only for good teams, or for "teenagers" also?

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 22, 2016

@funny-falcon, or @hamaxx, please send a CL. Code in comments isn't enough. Thanks.

@hamaxx
Copy link
Contributor

@hamaxx hamaxx commented Feb 22, 2016

Sure, I can send a CL.

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 22, 2016

@hamaxx, thanks!

@funny-falcon
Copy link
Contributor

@funny-falcon funny-falcon commented Feb 22, 2016

@bradfitz I didn't tell comments are enough ;-) I've said I don't want to steal @hamaxx authorship

@rsc
Copy link
Contributor

@rsc rsc commented Feb 23, 2016

It's not clear to me that defending against inconsistent Less functions is required of sort.Sort. Therefore it's not clear to me that this needs to go into a point release.

@funny-falcon
Copy link
Contributor

@funny-falcon funny-falcon commented Feb 23, 2016

Some one points to Go1x compatibility claim: program were working before Go1.6 and now it fails.

I believe it is my fault: when I changed condition I had an image of stable Less in my mind, and I forgot about "random tie breaker". "rtb" is really useful in some "quick&dirty" programs.

@gopherbot
Copy link

@gopherbot gopherbot commented Feb 23, 2016

CL https://golang.org/cl/19823 mentions this issue.

@gopherbot gopherbot closed this in 38d4511 Feb 24, 2016
@adg adg added the Release-Maybe label Apr 7, 2016
@adg adg modified the milestones: Go1.6.1, Go1.6.2 Apr 7, 2016
@rsc rsc added Release-OK and removed Release-Maybe labels Apr 7, 2016
@gopherbot
Copy link

@gopherbot gopherbot commented Apr 14, 2016

CL https://golang.org/cl/22039 mentions this issue.

gopherbot pushed a commit that referenced this issue Apr 14, 2016
Fixes #14377

Change-Id: I130a6e1b8bc827db44efd0a74e759b894ecc4977
Reviewed-on: https://go-review.googlesource.com/19823
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-on: https://go-review.googlesource.com/22039
@adg adg added Release-Applied and removed Release-OK labels Apr 14, 2016
@golang golang locked and limited conversation to collaborators Apr 19, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
10 participants
You can’t perform that action at this time.