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	"internal/runtime/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// must ensure the nodes are allocated outside the Go heap.
22type lfstack uint64
23
24func (head *lfstack) push(node *lfnode) {
25	node.pushcnt++
26	new := lfstackPack(node, node.pushcnt)
27	if node1 := lfstackUnpack(new); node1 != node {
28		print("runtime: lfstack.push invalid packing: node=", node, " cnt=", hex(node.pushcnt), " packed=", hex(new), " -> node=", node1, "\n")
29		throw("lfstack.push")
30	}
31	for {
32		old := atomic.Load64((*uint64)(head))
33		node.next = old
34		if atomic.Cas64((*uint64)(head), old, new) {
35			break
36		}
37	}
38}
39
40func (head *lfstack) pop() unsafe.Pointer {
41	for {
42		old := atomic.Load64((*uint64)(head))
43		if old == 0 {
44			return nil
45		}
46		node := lfstackUnpack(old)
47		next := atomic.Load64(&node.next)
48		if atomic.Cas64((*uint64)(head), old, next) {
49			return unsafe.Pointer(node)
50		}
51	}
52}
53
54func (head *lfstack) empty() bool {
55	return atomic.Load64((*uint64)(head)) == 0
56}
57
58// lfnodeValidate panics if node is not a valid address for use with
59// lfstack.push. This only needs to be called when node is allocated.
60func lfnodeValidate(node *lfnode) {
61	if base, _, _ := findObject(uintptr(unsafe.Pointer(node)), 0, 0); base != 0 {
62		throw("lfstack node allocated from the heap")
63	}
64	if lfstackUnpack(lfstackPack(node, ^uintptr(0))) != node {
65		printlock()
66		println("runtime: bad lfnode address", hex(uintptr(unsafe.Pointer(node))))
67		throw("bad lfnode address")
68	}
69}
70
71func lfstackPack(node *lfnode, cnt uintptr) uint64 {
72	return uint64(taggedPointerPack(unsafe.Pointer(node), cnt))
73}
74
75func lfstackUnpack(val uint64) *lfnode {
76	return (*lfnode)(taggedPointer(val).pointer())
77}
78