Source file src/runtime/lfstack.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	// 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	
    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 {
    63			printlock()
    64			println("runtime: bad lfnode address", hex(uintptr(unsafe.Pointer(node))))
    65			throw("bad lfnode address")
    66		}
    67	}
    68	

View as plain text