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
|
// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package runtime_test
import (
"math/rand"
. "runtime"
"testing"
"unsafe"
)
type MyNode struct {
LFNode
data int
}
func fromMyNode(node *MyNode) *LFNode {
return (*LFNode)(unsafe.Pointer(node))
}
func toMyNode(node *LFNode) *MyNode {
return (*MyNode)(unsafe.Pointer(node))
}
var global interface{}
func TestLFStack(t *testing.T) {
stack := new(uint64)
global = stack // force heap allocation
// Need to keep additional references to nodes, the stack is not all that type-safe.
var nodes []*MyNode
// Check the stack is initially empty.
if LFStackPop(stack) != nil {
t.Fatalf("stack is not empty")
}
// Push one element.
node := &MyNode{data: 42}
nodes = append(nodes, node)
LFStackPush(stack, fromMyNode(node))
// Push another.
node = &MyNode{data: 43}
nodes = append(nodes, node)
LFStackPush(stack, fromMyNode(node))
// Pop one element.
node = toMyNode(LFStackPop(stack))
if node == nil {
t.Fatalf("stack is empty")
}
if node.data != 43 {
t.Fatalf("no lifo")
}
// Pop another.
node = toMyNode(LFStackPop(stack))
if node == nil {
t.Fatalf("stack is empty")
}
if node.data != 42 {
t.Fatalf("no lifo")
}
// Check the stack is empty again.
if LFStackPop(stack) != nil {
t.Fatalf("stack is not empty")
}
if *stack != 0 {
t.Fatalf("stack is not empty")
}
}
var stress []*MyNode
func TestLFStackStress(t *testing.T) {
const K = 100
P := 4 * GOMAXPROCS(-1)
N := 100000
if testing.Short() {
N /= 10
}
// Create 2 stacks.
stacks := [2]*uint64{new(uint64), new(uint64)}
// Need to keep additional references to nodes,
// the lock-free stack is not type-safe.
stress = nil
// Push K elements randomly onto the stacks.
sum := 0
for i := 0; i < K; i++ {
sum += i
node := &MyNode{data: i}
stress = append(stress, node)
LFStackPush(stacks[i%2], fromMyNode(node))
}
c := make(chan bool, P)
for p := 0; p < P; p++ {
go func() {
r := rand.New(rand.NewSource(rand.Int63()))
// Pop a node from a random stack, then push it onto a random stack.
for i := 0; i < N; i++ {
node := toMyNode(LFStackPop(stacks[r.Intn(2)]))
if node != nil {
LFStackPush(stacks[r.Intn(2)], fromMyNode(node))
}
}
c <- true
}()
}
for i := 0; i < P; i++ {
<-c
}
// Pop all elements from both stacks, and verify that nothing lost.
sum2 := 0
cnt := 0
for i := 0; i < 2; i++ {
for {
node := toMyNode(LFStackPop(stacks[i]))
if node == nil {
break
}
cnt++
sum2 += node.data
node.Next = 0
}
}
if cnt != K {
t.Fatalf("Wrong number of nodes %d/%d", cnt, K)
}
if sum2 != sum {
t.Fatalf("Wrong sum %d/%d", sum2, sum)
}
// Let nodes be collected now.
stress = nil
}
|
