reflect: sort.SliceStable sorts incorrectly on arm64 with `less` function created with `reflect.MakeFunc` and slice of sufficient length #57184

jfhamlin · 2022-12-09T04:14:04Z

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

$ go version
go version devel go1.20-e738a2f Thu Dec 8 23:06:18 2022 +0000 darwin/arm64

Does this issue reproduce with the latest release?

Yes (with gotip)

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

go env Output

$ go env
GO111MODULE=""
GOARCH="arm64"
GOBIN=""
GOCACHE="/Users/jfhamlin/Library/Caches/go-build"
GOENV="/Users/jfhamlin/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/jfhamlin/Projects/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/jfhamlin/Projects/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/Users/jfhamlin/sdk/gotip"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/Users/jfhamlin/sdk/gotip/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="devel go1.20-e738a2f Thu Dec 8 23:06:18 2022 +0000"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="0"
GOMOD="/dev/null"
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch arm64 -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/mm/bhf4r1f11zq3fc1gckc5wt6h0000gn/T/go-build3493514532=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

The sort.SliceStable function fails to sort a slice correctly when using a comparison function created using reflect.MakeFunc. I've only reproduced the issue on Apple silicon and only when the length of the slice being sorted is greater than or equal to 261. The same program produced the correct result on amd64.

Go Playground Link: https://go.dev/play/p/HSez0_sewXy?v=gotip
Note that the bug does not reproduce in the playground, presumably because it runs on amd64, not arm64.

package main

import (
	"log"
	"reflect"
	"sort"
)

func main() {
	// 261 is the shortest slice length for which this fails
	const length = 261
	x := make([]int, length)
	for i := 0; i < length; i++ {
		x[i] = i
	}

	isLessStatic := func(i, j int) bool {
		return x[i] < x[j]
	}

	isLessReflect := reflect.MakeFunc(reflect.TypeOf(isLessStatic), func(args []reflect.Value) []reflect.Value {
		//return []reflect.Value{reflect.ValueOf(false)} // also fails
		return []reflect.Value{reflect.ValueOf(x[args[0].Int()] < x[args[1].Int()])}
	}).Interface().(func(i, j int) bool)

	_ = isLessReflect
	sort.SliceStable(x, isLessReflect)
	// sort.SliceStable(x, isLessStatic) // passes

	for i := 0; i < length-1; i++ {
		if x[i] >= x[i+1] {
			log.Fatalf("not sorted! (length=%v)\n%v\n", length, x)
		}
	}
}

What did you expect to see?

(i.e. no output)

What did you see instead?

2022/12/08 19:59:15 not sorted! (length=261)
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 260 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259]
exit status 1

(the greatest value, 260, is moved to the wrong index)

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

jclapis · 2022-12-09T05:33:27Z

I can repro this using go v1.19.4 on an rk3588 (Rock 5B); the above works on x64 but fails on arm64 with the following:

2022/12/09 05:29:00 not sorted! (length=261)
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 260 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259]
exit status 1

Running it multiple times doesn't change the output; 260 is always after 239.

randall77 · 2022-12-09T07:08:26Z

return []reflect.Value{reflect.ValueOf(args[0].Int() < args[1].Int())}

This isn't right. You're comparing i and j, not x[i] and x[j].

jfhamlin · 2022-12-09T16:43:30Z

@randall77 you're absolutely right. that bug slipped in with my minimal example, but it reproduces with a comparison between x[i] and x[j] as well. i've edited the opening comment with the fix to the comparator.

randall77 · 2022-12-09T17:21:57Z

Ok, I can reproduce now.

randall77 · 2022-12-09T18:32:16Z

I think I see the issue.

arm64 has some confusion about how booleans are passed in registers.
cmd/compile/internal/ssa/_gen/ARM64Ops.go claims in the top comment that booleans are stored in the low byte of a register, and the upper bytes are junk.
Some of our code generation rules, however, assume that booleans are full register width. E.g., this one:

(If cond yes no) => (TBNZ [0] cond yes no)

I think what is happening is that reflect in particular is only setting the low byte of the return register to the returned boolean. The other bytes in that register are junk. Later uses of that boolean by the sort package branch the wrong way as a result.

I can fix this by changing reflect to zero the target register before writing a "thinner" value to it.

 func intToReg(r *abi.RegArgs, reg int, argSize uintptr, from unsafe.Pointer) {
+       var z [8]byte
+       memmove(r.IntRegArgAddr(reg, 8), unsafe.Pointer(&z), 8)
        memmove(r.IntRegArgAddr(reg, argSize), from, argSize)
 }

Not really a full fix, but demonstrates that the upper bytes of registers are the problem. Really we need to decide whether booleans are full-reg or low-byte-only and enforce that rule throughout.

@golang/arm

randall77 · 2022-12-09T18:37:31Z

I take back the claim that the rewrite rule I showed above is broken. It isn't, it only depends on the low bit.
But something is using the high bits incorrectly. Looking...

cherrymui · 2022-12-09T18:37:53Z

I thought I fixed some rules in the past to do the proper extension before comparison, maybe there are still places I missed.

I think the compiler generally assume values only have low bits meaningful, so is the register ABI. So I think we want to fix the compiler.

The TBNZ shouldn't be a problem, though. TBNZ only checks the zeroth bit, not the hight bits.

I'll take a look.

randall77 · 2022-12-09T18:41:27Z

Something in the lower pass is to blame, on the return value of functions. sort.symMerge_func has a closure call. Before lowering:

v130 (441) = ClosureCall <bool,mem> {AuxCall{nil}} [16] v129 v114 v127 v122 v187
v131 (441) = SelectN <mem> [1] v130
v132 (441) = SelectN <bool> [0] v130
v233 (439) = CondSelect <int> v122 v116 v132 (r[int])
v235 (439) = CondSelect <int> v115 v134 v132 (start[int])

after lowering:

v130 (441) = CALLclosure <bool,mem> {AuxCall{nil}} [16] v129 v114 v127 v161 v187
v131 (441) = SelectN <mem> [1] v130
v132 (441) = SelectN <bool> [0] v130
v201 (439) = CMPWconst <flags> [0] v132
v191 (439) = CMPWconst <flags> [0] v132
v233 (439) = CSEL <int> {NotEqual} v161 v116 v201 (r[int])
v235 (439) = CSINC <int> {NotEqual} v115 v161 v191 (start[int])

Those CMPWconsts look wrong.

randall77 · 2022-12-09T18:44:24Z

This is probably the bad one:

(CondSelect x y boolval) && flagArg(boolval) == nil => (CSEL [OpARM64NotEqual] x y (CMPWconst [0] boolval))

I think we just need to use some sort of TEST of the low bit instead of CMPW.

ianlancetaylor · 2022-12-09T18:59:10Z

Do we know whether this problem occurs on earlier releases? If so, we should backport. Thanks.

randall77 · 2022-12-09T19:00:30Z

I believe so, this rule is old. I will double-check.

gopherbot · 2022-12-09T19:01:13Z

Change https://go.dev/cl/456556 mentions this issue: cmd/compile: fix conditional select rule

randall77 · 2022-12-09T19:05:07Z

Yes, this bug was introduced in 1.18.

@gopherbot please open backport issues.

This bug causes miscompilation of conditional move instructions. In rare cases (involving reflection, but maybe others) the boolean expression triggering the conditional move is wrong.

gopherbot · 2022-12-09T19:05:32Z

Backport issue(s) opened: #57211 (for 1.18), #57212 (for 1.19).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

gopherbot · 2022-12-10T03:52:26Z

Change https://go.dev/cl/456437 mentions this issue: cmd/compile: fix conditional move rule on PPC64

Similar to CL 456556 but for ppc64 instead of arm64. Change docs about how booleans are stored in registers for ppc64. We now don't promise to keep the upper bits zeroed; they might be junk. To test, I changed the boolean generation instructions (MOVBZload* and ISEL* with boolean type) to OR in 0x100 to the result. all.bash still passed, so I think nothing else is depending on the upper bits of booleans. Update #57184 Change-Id: Ie66f8934a0dafa34d0a8c2a37324868d959a852c Reviewed-on: https://go-review.googlesource.com/c/go/+/456437 Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Keith Randall <khr@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: KAMPANAT THUMWONG (KONG PC) <1992kongpc.kth@gmail.com> Run-TryBot: Archana Ravindar <aravind5@in.ibm.com>

gopherbot added the compiler/runtime label Dec 9, 2022

randall77 closed this as completed Dec 9, 2022

randall77 reopened this Dec 9, 2022

randall77 added the release-blocker label Dec 9, 2022

randall77 added this to the Go1.20 milestone Dec 9, 2022

gopherbot mentioned this issue Dec 9, 2022

reflect: sort.SliceStable sorts incorrectly on arm64 with less function created with reflect.MakeFunc and slice of sufficient length [1.18 backport] #57211

Closed

randall77 mentioned this issue Dec 9, 2022

reflect: sort.SliceStable sorts incorrectly on arm64 with less function created with reflect.MakeFunc and slice of sufficient length [1.19 backport] #57212

Closed

gopherbot closed this as completed in e8f78cb Dec 9, 2022

ferrmin mentioned this issue Dec 12, 2022

cmd/compile: fix conditional move rule on PPC64 ferrmin/go#538

Merged

golang locked and limited conversation to collaborators Dec 10, 2023

gopherbot added the FrozenDueToAge label Dec 10, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

reflect: sort.SliceStable sorts incorrectly on arm64 with `less` function created with `reflect.MakeFunc` and slice of sufficient length #57184

reflect: sort.SliceStable sorts incorrectly on arm64 with `less` function created with `reflect.MakeFunc` and slice of sufficient length #57184

jfhamlin commented Dec 9, 2022 •

edited

Loading

jclapis commented Dec 9, 2022

randall77 commented Dec 9, 2022

jfhamlin commented Dec 9, 2022 •

edited

Loading

randall77 commented Dec 9, 2022

randall77 commented Dec 9, 2022

randall77 commented Dec 9, 2022

cherrymui commented Dec 9, 2022

randall77 commented Dec 9, 2022

randall77 commented Dec 9, 2022

ianlancetaylor commented Dec 9, 2022

randall77 commented Dec 9, 2022

gopherbot commented Dec 9, 2022

randall77 commented Dec 9, 2022

gopherbot commented Dec 9, 2022 •

edited by dmitshur

Loading

gopherbot commented Dec 10, 2022

reflect: sort.SliceStable sorts incorrectly on arm64 with less function created with reflect.MakeFunc and slice of sufficient length #57184

reflect: sort.SliceStable sorts incorrectly on arm64 with less function created with reflect.MakeFunc and slice of sufficient length #57184

Comments

jfhamlin commented Dec 9, 2022 • edited Loading

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

jclapis commented Dec 9, 2022

randall77 commented Dec 9, 2022

jfhamlin commented Dec 9, 2022 • edited Loading

randall77 commented Dec 9, 2022

randall77 commented Dec 9, 2022

randall77 commented Dec 9, 2022

cherrymui commented Dec 9, 2022

randall77 commented Dec 9, 2022

randall77 commented Dec 9, 2022

ianlancetaylor commented Dec 9, 2022

randall77 commented Dec 9, 2022

gopherbot commented Dec 9, 2022

randall77 commented Dec 9, 2022

gopherbot commented Dec 9, 2022 • edited by dmitshur Loading

gopherbot commented Dec 10, 2022

reflect: sort.SliceStable sorts incorrectly on arm64 with `less` function created with `reflect.MakeFunc` and slice of sufficient length #57184

reflect: sort.SliceStable sorts incorrectly on arm64 with `less` function created with `reflect.MakeFunc` and slice of sufficient length #57184

jfhamlin commented Dec 9, 2022 •

edited

Loading

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

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

jfhamlin commented Dec 9, 2022 •

edited

Loading

gopherbot commented Dec 9, 2022 •

edited by dmitshur

Loading