1// run 2 3// Copyright 2017 The Go Authors. All rights reserved. 4// Use of this source code is governed by a BSD-style 5// license that can be found in the LICENSE file. 6 7// Test that locks don't go quadratic due to runtime hash table collisions. 8 9package main 10 11import ( 12 "bytes" 13 "fmt" 14 "log" 15 "os" 16 "runtime" 17 "runtime/pprof" 18 "sync" 19 "time" 20) 21 22const debug = false 23 24// checkLinear asserts that the running time of f(n) is at least linear but sub-quadratic. 25// tries is the initial number of iterations. 26func checkLinear(typ string, tries int, f func(n int)) { 27 // Depending on the machine and OS, this test might be too fast 28 // to measure with accurate enough granularity. On failure, 29 // make it run longer, hoping that the timing granularity 30 // is eventually sufficient. 31 32 timeF := func(n int) time.Duration { 33 t1 := time.Now() 34 f(n) 35 return time.Since(t1) 36 } 37 38 n := tries 39 fails := 0 40 var buf bytes.Buffer 41 inversions := 0 42 for { 43 t1 := timeF(n) 44 t2 := timeF(2 * n) 45 if debug { 46 println(n, t1.String(), 2*n, t2.String()) 47 } 48 fmt.Fprintf(&buf, "%d %v %d %v (%.1fX)\n", n, t1, 2*n, t2, float64(t2)/float64(t1)) 49 // should be 2x (linear); allow up to 3x 50 if t1*3/2 < t2 && t2 < t1*3 { 51 return 52 } 53 if t2 < t1 { 54 if inversions++; inversions >= 5 { 55 // The system must be overloaded (some builders). Give up. 56 return 57 } 58 continue // try again; don't increment fails 59 } 60 // Once the test runs long enough for n ops, 61 // try to get the right ratio at least once. 62 // If many in a row all fail, give up. 63 if fails++; fails >= 5 { 64 // If 2n ops run in under a second and the ratio 65 // doesn't work out, make n bigger, trying to reduce 66 // the effect that a constant amount of overhead has 67 // on the computed ratio. 68 if t2 < time.Second*4/10 { 69 fails = 0 70 n *= 2 71 continue 72 } 73 panic(fmt.Sprintf("%s: too slow: %d ops: %v; %d ops: %v\n\n%s", 74 typ, n, t1, 2*n, t2, buf.String())) 75 } 76 } 77} 78 79const offset = 251 // known size of runtime hash table 80 81const profile = false 82 83func main() { 84 if profile { 85 f, err := os.Create("lock.prof") 86 if err != nil { 87 log.Fatal(err) 88 } 89 pprof.StartCPUProfile(f) 90 defer pprof.StopCPUProfile() 91 } 92 93 checkLinear("lockone", 1000, func(n int) { 94 ch := make(chan int) 95 locks := make([]sync.RWMutex, offset+1) 96 for i := 0; i < n; i++ { 97 go func() { 98 locks[0].Lock() 99 ch <- 1 100 }() 101 } 102 time.Sleep(1 * time.Millisecond) 103 104 go func() { 105 for j := 0; j < n; j++ { 106 locks[1].Lock() 107 locks[offset].Lock() 108 locks[1].Unlock() 109 runtime.Gosched() 110 locks[offset].Unlock() 111 } 112 }() 113 114 for j := 0; j < n; j++ { 115 locks[1].Lock() 116 locks[offset].Lock() 117 locks[1].Unlock() 118 runtime.Gosched() 119 locks[offset].Unlock() 120 } 121 122 for i := 0; i < n; i++ { 123 <-ch 124 locks[0].Unlock() 125 } 126 }) 127 128 if runtime.GOARCH == "arm" && os.Getenv("GOARM") == "5" { 129 // lockmany reliably fails on the linux-arm-arm5spacemonkey 130 // builder. See https://golang.org/issue/24221. 131 return 132 } 133 134 checkLinear("lockmany", 1000, func(n int) { 135 locks := make([]sync.RWMutex, n*offset+1) 136 137 var wg sync.WaitGroup 138 for i := 0; i < n; i++ { 139 wg.Add(1) 140 go func(i int) { 141 locks[(i+1)*offset].Lock() 142 wg.Done() 143 locks[(i+1)*offset].Lock() 144 locks[(i+1)*offset].Unlock() 145 }(i) 146 } 147 wg.Wait() 148 149 go func() { 150 for j := 0; j < n; j++ { 151 locks[1].Lock() 152 locks[0].Lock() 153 locks[1].Unlock() 154 runtime.Gosched() 155 locks[0].Unlock() 156 } 157 }() 158 159 for j := 0; j < n; j++ { 160 locks[1].Lock() 161 locks[0].Lock() 162 locks[1].Unlock() 163 runtime.Gosched() 164 locks[0].Unlock() 165 } 166 167 for i := 0; i < n; i++ { 168 locks[(i+1)*offset].Unlock() 169 } 170 }) 171} 172