1// Copyright 2012 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package runtime_test
6
7import (
8	"math/rand"
9	. "runtime"
10	"testing"
11	"unsafe"
12)
13
14type MyNode struct {
15	LFNode
16	data int
17}
18
19func fromMyNode(node *MyNode) *LFNode {
20	return (*LFNode)(unsafe.Pointer(node))
21}
22
23func toMyNode(node *LFNode) *MyNode {
24	return (*MyNode)(unsafe.Pointer(node))
25}
26
27var global interface{}
28
29func TestLFStack(t *testing.T) {
30	stack := new(uint64)
31	global = stack // force heap allocation
32
33	// Need to keep additional references to nodes, the stack is not all that type-safe.
34	var nodes []*MyNode
35
36	// Check the stack is initially empty.
37	if LFStackPop(stack) != nil {
38		t.Fatalf("stack is not empty")
39	}
40
41	// Push one element.
42	node := &MyNode{data: 42}
43	nodes = append(nodes, node)
44	LFStackPush(stack, fromMyNode(node))
45
46	// Push another.
47	node = &MyNode{data: 43}
48	nodes = append(nodes, node)
49	LFStackPush(stack, fromMyNode(node))
50
51	// Pop one element.
52	node = toMyNode(LFStackPop(stack))
53	if node == nil {
54		t.Fatalf("stack is empty")
55	}
56	if node.data != 43 {
57		t.Fatalf("no lifo")
58	}
59
60	// Pop another.
61	node = toMyNode(LFStackPop(stack))
62	if node == nil {
63		t.Fatalf("stack is empty")
64	}
65	if node.data != 42 {
66		t.Fatalf("no lifo")
67	}
68
69	// Check the stack is empty again.
70	if LFStackPop(stack) != nil {
71		t.Fatalf("stack is not empty")
72	}
73	if *stack != 0 {
74		t.Fatalf("stack is not empty")
75	}
76}
77
78var stress []*MyNode
79
80func TestLFStackStress(t *testing.T) {
81	const K = 100
82	P := 4 * GOMAXPROCS(-1)
83	N := 100000
84	if testing.Short() {
85		N /= 10
86	}
87	// Create 2 stacks.
88	stacks := [2]*uint64{new(uint64), new(uint64)}
89	// Need to keep additional references to nodes,
90	// the lock-free stack is not type-safe.
91	stress = nil
92	// Push K elements randomly onto the stacks.
93	sum := 0
94	for i := 0; i < K; i++ {
95		sum += i
96		node := &MyNode{data: i}
97		stress = append(stress, node)
98		LFStackPush(stacks[i%2], fromMyNode(node))
99	}
100	c := make(chan bool, P)
101	for p := 0; p < P; p++ {
102		go func() {
103			r := rand.New(rand.NewSource(rand.Int63()))
104			// Pop a node from a random stack, then push it onto a random stack.
105			for i := 0; i < N; i++ {
106				node := toMyNode(LFStackPop(stacks[r.Intn(2)]))
107				if node != nil {
108					LFStackPush(stacks[r.Intn(2)], fromMyNode(node))
109				}
110			}
111			c <- true
112		}()
113	}
114	for i := 0; i < P; i++ {
115		<-c
116	}
117	// Pop all elements from both stacks, and verify that nothing lost.
118	sum2 := 0
119	cnt := 0
120	for i := 0; i < 2; i++ {
121		for {
122			node := toMyNode(LFStackPop(stacks[i]))
123			if node == nil {
124				break
125			}
126			cnt++
127			sum2 += node.data
128			node.Next = 0
129		}
130	}
131	if cnt != K {
132		t.Fatalf("Wrong number of nodes %d/%d", cnt, K)
133	}
134	if sum2 != sum {
135		t.Fatalf("Wrong sum %d/%d", sum2, sum)
136	}
137
138	// Let nodes be collected now.
139	stress = nil
140}
141