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// Lock-free stack.
6
7package runtime
8
9import (
10	"runtime/internal/atomic"
11	"unsafe"
12)
13
14// lfstack is the head of a lock-free stack.
15//
16// The zero value of lfstack is an empty list.
17//
18// This stack is intrusive. Nodes must embed lfnode as the first field.
19//
20// The stack does not keep GC-visible pointers to nodes, so the caller
21// is responsible for ensuring the nodes are not garbage collected
22// (typically by allocating them from manually-managed memory).
23type lfstack uint64
24
25func (head *lfstack) push(node *lfnode) {
26	node.pushcnt++
27	new := lfstackPack(node, node.pushcnt)
28	if node1 := lfstackUnpack(new); node1 != node {
29		print("runtime: lfstack.push invalid packing: node=", node, " cnt=", hex(node.pushcnt), " packed=", hex(new), " -> node=", node1, "\n")
30		throw("lfstack.push")
31	}
32	for {
33		old := atomic.Load64((*uint64)(head))
34		node.next = old
35		if atomic.Cas64((*uint64)(head), old, new) {
36			break
37		}
38	}
39}
40
41func (head *lfstack) pop() unsafe.Pointer {
42	for {
43		old := atomic.Load64((*uint64)(head))
44		if old == 0 {
45			return nil
46		}
47		node := lfstackUnpack(old)
48		next := atomic.Load64(&node.next)
49		if atomic.Cas64((*uint64)(head), old, next) {
50			return unsafe.Pointer(node)
51		}
52	}
53}
54
55func (head *lfstack) empty() bool {
56	return atomic.Load64((*uint64)(head)) == 0
57}
58
59// lfnodeValidate panics if node is not a valid address for use with
60// lfstack.push. This only needs to be called when node is allocated.
61func lfnodeValidate(node *lfnode) {
62	if lfstackUnpack(lfstackPack(node, ^uintptr(0))) != node {
63		printlock()
64		println("runtime: bad lfnode address", hex(uintptr(unsafe.Pointer(node))))
65		throw("bad lfnode address")
66	}
67}
68