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
19// allocMyNode allocates nodes that are stored in an lfstack
20// outside the Go heap.
21// We require lfstack objects to live outside the heap so that
22// checkptr passes on the unsafe shenanigans used.
23func allocMyNode(data int) *MyNode {
24	n := (*MyNode)(PersistentAlloc(unsafe.Sizeof(MyNode{})))
25	LFNodeValidate(&n.LFNode)
26	n.data = data
27	return n
28}
29
30func fromMyNode(node *MyNode) *LFNode {
31	return (*LFNode)(unsafe.Pointer(node))
32}
33
34func toMyNode(node *LFNode) *MyNode {
35	return (*MyNode)(unsafe.Pointer(node))
36}
37
38var global any
39
40func TestLFStack(t *testing.T) {
41	stack := new(uint64)
42	global = stack // force heap allocation
43
44	// Check the stack is initially empty.
45	if LFStackPop(stack) != nil {
46		t.Fatalf("stack is not empty")
47	}
48
49	// Push one element.
50	node := allocMyNode(42)
51	LFStackPush(stack, fromMyNode(node))
52
53	// Push another.
54	node = allocMyNode(43)
55	LFStackPush(stack, fromMyNode(node))
56
57	// Pop one element.
58	node = toMyNode(LFStackPop(stack))
59	if node == nil {
60		t.Fatalf("stack is empty")
61	}
62	if node.data != 43 {
63		t.Fatalf("no lifo")
64	}
65
66	// Pop another.
67	node = toMyNode(LFStackPop(stack))
68	if node == nil {
69		t.Fatalf("stack is empty")
70	}
71	if node.data != 42 {
72		t.Fatalf("no lifo")
73	}
74
75	// Check the stack is empty again.
76	if LFStackPop(stack) != nil {
77		t.Fatalf("stack is not empty")
78	}
79	if *stack != 0 {
80		t.Fatalf("stack is not empty")
81	}
82}
83
84func TestLFStackStress(t *testing.T) {
85	const K = 100
86	P := 4 * GOMAXPROCS(-1)
87	N := 100000
88	if testing.Short() {
89		N /= 10
90	}
91	// Create 2 stacks.
92	stacks := [2]*uint64{new(uint64), new(uint64)}
93	// Push K elements randomly onto the stacks.
94	sum := 0
95	for i := 0; i < K; i++ {
96		sum += i
97		node := allocMyNode(i)
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