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 7 package runtime 8 9 import ( 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). 23 type lfstack uint64 24 25 func (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 41 func (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 55 func (head *lfstack) empty() bool { 56 return atomic.Load64((*uint64)(head)) == 0 57 } 58
