Home | History | Annotate | Download | only in runtime 
      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 
      5 package runtime_test
      6 
      7 import (
      8 	"math/rand"
      9 	. "runtime"
     10 	"testing"
     11 	"unsafe"
     12 )
     13 
     14 type MyNode struct {
     15 	LFNode
     16 	data int
     17 }
     18 
     19 func fromMyNode(node *MyNode) *LFNode {
     20 	return (*LFNode)(unsafe.Pointer(node))
     21 }
     22 
     23 func toMyNode(node *LFNode) *MyNode {
     24 	return (*MyNode)(unsafe.Pointer(node))
     25 }
     26 
     27 var global interface{}
     28 
     29 func 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 
     78 var stress []*MyNode
     79 
     80 func 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