lfstack_test.go

Documentation: 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
View as plain text