libgo/go/runtime/lfstack_test.go

   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 }