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