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.
10 "runtime/internal/atomic"
14 // lfstack is the head of a lock-free stack.
16 // The zero value of lfstack is an empty list.
18 // This stack is intrusive. Nodes must embed lfnode as the first field.
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).
25 func (head
*lfstack
) push(node
*lfnode
) {
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")
33 old
:= atomic
.Load64((*uint64)(head
))
35 if atomic
.Cas64((*uint64)(head
), old
, new) {
41 func (head
*lfstack
) pop() unsafe
.Pointer
{
43 old
:= atomic
.Load64((*uint64)(head
))
47 node
:= lfstackUnpack(old
)
48 next
:= atomic
.Load64(&node
.next
)
49 if atomic
.Cas64((*uint64)(head
), old
, next
) {
50 return unsafe
.Pointer(node
)
55 func (head
*lfstack
) empty() bool {
56 return atomic
.Load64((*uint64)(head
)) == 0
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.
61 func lfnodeValidate(node
*lfnode
) {
62 if lfstackUnpack(lfstackPack(node
, ^uintptr(0))) != node
{
64 println("runtime: bad lfnode address", hex(uintptr(unsafe
.Pointer(node
))))
65 throw("bad lfnode address")