libgo/go/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 }