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  // allocMyNode allocates nodes that are stored in an lfstack
    20  // outside the Go heap.
    21  // We require lfstack objects to live outside the heap so that
    22  // checkptr passes on the unsafe shenanigans used.
    23  func allocMyNode(data int) *MyNode {
    24  	n := (*MyNode)(PersistentAlloc(unsafe.Sizeof(MyNode{})))
    25  	LFNodeValidate(&n.LFNode)
    26  	n.data = data
    27  	return n
    28  }
    29  
    30  func fromMyNode(node *MyNode) *LFNode {
    31  	return (*LFNode)(unsafe.Pointer(node))
    32  }
    33  
    34  func toMyNode(node *LFNode) *MyNode {
    35  	return (*MyNode)(unsafe.Pointer(node))
    36  }
    37  
    38  var global any
    39  
    40  func TestLFStack(t *testing.T) {
    41  	stack := new(uint64)
    42  	global = stack // force heap allocation
    43  
    44  	// Check the stack is initially empty.
    45  	if LFStackPop(stack) != nil {
    46  		t.Fatalf("stack is not empty")
    47  	}
    48  
    49  	// Push one element.
    50  	node := allocMyNode(42)
    51  	LFStackPush(stack, fromMyNode(node))
    52  
    53  	// Push another.
    54  	node = allocMyNode(43)
    55  	LFStackPush(stack, fromMyNode(node))
    56  
    57  	// Pop one element.
    58  	node = toMyNode(LFStackPop(stack))
    59  	if node == nil {
    60  		t.Fatalf("stack is empty")
    61  	}
    62  	if node.data != 43 {
    63  		t.Fatalf("no lifo")
    64  	}
    65  
    66  	// Pop another.
    67  	node = toMyNode(LFStackPop(stack))
    68  	if node == nil {
    69  		t.Fatalf("stack is empty")
    70  	}
    71  	if node.data != 42 {
    72  		t.Fatalf("no lifo")
    73  	}
    74  
    75  	// Check the stack is empty again.
    76  	if LFStackPop(stack) != nil {
    77  		t.Fatalf("stack is not empty")
    78  	}
    79  	if *stack != 0 {
    80  		t.Fatalf("stack is not empty")
    81  	}
    82  }
    83  
    84  func TestLFStackStress(t *testing.T) {
    85  	const K = 100
    86  	P := 4 * GOMAXPROCS(-1)
    87  	N := 100000
    88  	if testing.Short() {
    89  		N /= 10
    90  	}
    91  	// Create 2 stacks.
    92  	stacks := [2]*uint64{new(uint64), new(uint64)}
    93  	// Push K elements randomly onto the stacks.
    94  	sum := 0
    95  	for i := 0; i < K; i++ {
    96  		sum += i
    97  		node := allocMyNode(i)
    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
View as plain text