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 func TestLFStack(t *testing.T) {
  28         stack := new(uint64)
  29         // Need to keep additional referenfces to nodes, the stack is not all that type-safe.
  30         var nodes []*MyNode
  31
  32         // Check the stack is initially empty.
  33         if LFStackPop(stack) != nil {
  34                 t.Fatalf("stack is not empty")
  35         }
  36
  37         // Push one element.
  38         node := &MyNode{data: 42}
  39         nodes = append(nodes, node)
  40         LFStackPush(stack, fromMyNode(node))
  41
  42         // Push another.
  43         node = &MyNode{data: 43}
  44         nodes = append(nodes, node)
  45         LFStackPush(stack, fromMyNode(node))
  46
  47         // Pop one element.
  48         node = toMyNode(LFStackPop(stack))
  49         if node == nil {
  50                 t.Fatalf("stack is empty")
  51         }
  52         if node.data != 43 {
  53                 t.Fatalf("no lifo")
  54         }
  55
  56         // Pop another.
  57         node = toMyNode(LFStackPop(stack))
  58         if node == nil {
  59                 t.Fatalf("stack is empty")
  60         }
  61         if node.data != 42 {
  62                 t.Fatalf("no lifo")
  63         }
  64
  65         // Check the stack is empty again.
  66         if LFStackPop(stack) != nil {
  67                 t.Fatalf("stack is not empty")
  68         }
  69         if *stack != 0 {
  70                 t.Fatalf("stack is not empty")
  71         }
  72 }
  73
  74 var stress []*MyNode
  75
  76 func TestLFStackStress(t *testing.T) {
  77         const K = 100
  78         P := 4 * GOMAXPROCS(-1)
  79         N := 100000
  80         if testing.Short() {
  81                 N /= 10
  82         }
  83         // Create 2 stacks.
  84         stacks := [2]*uint64{new(uint64), new(uint64)}
  85         // Need to keep additional references to nodes,
  86         // the lock-free stack is not type-safe.
  87         stress = nil
  88         // Push K elements randomly onto the stacks.
  89         sum := 0
  90         for i := 0; i < K; i++ {
  91                 sum += i
  92                 node := &MyNode{data: i}
  93                 stress = append(stress, node)
  94                 LFStackPush(stacks[i%2], fromMyNode(node))
  95         }
  96         c := make(chan bool, P)
  97         for p := 0; p < P; p++ {
  98                 go func() {
  99                         r := rand.New(rand.NewSource(rand.Int63()))
 100                         // Pop a node from a random stack, then push it onto a random stack.
 101                         for i := 0; i < N; i++ {
 102                                 node := toMyNode(LFStackPop(stacks[r.Intn(2)]))
 103                                 if node != nil {
 104                                         LFStackPush(stacks[r.Intn(2)], fromMyNode(node))
 105                                 }
 106                         }
 107                         c <- true
 108                 }()
 109         }
 110         for i := 0; i < P; i++ {
 111                 <-c
 112         }
 113         // Pop all elements from both stacks, and verify that nothing lost.
 114         sum2 := 0
 115         cnt := 0
 116         for i := 0; i < 2; i++ {
 117                 for {
 118                         node := toMyNode(LFStackPop(stacks[i]))
 119                         if node == nil {
 120                                 break
 121                         }
 122                         cnt++
 123                         sum2 += node.data
 124                         node.Next = nil
 125                 }
 126         }
 127         if cnt != K {
 128                 t.Fatalf("Wrong number of nodes %d/%d", cnt, K)
 129         }
 130         if sum2 != sum {
 131                 t.Fatalf("Wrong sum %d/%d", sum2, sum)
 132         }
 133
 134         // Let nodes be collected now.
 135         stress = nil
 136 }