1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Lock-free stack.
package runtime
import (
"internal/runtime/atomic"
"unsafe"
)
// lfstack is the head of a lock-free stack.
//
// The zero value of lfstack is an empty list.
//
// This stack is intrusive. Nodes must embed lfnode as the first field.
//
// The stack does not keep GC-visible pointers to nodes, so the caller
// must ensure the nodes are allocated outside the Go heap.
type lfstack uint64
func (head *lfstack) push(node *lfnode) {
node.pushcnt++
new := lfstackPack(node, node.pushcnt)
for {
old := atomic.Load64((*uint64)(head))
node.next = old
if atomic.Cas64((*uint64)(head), old, new) {
break
}
}
}
func (head *lfstack) pop() unsafe.Pointer {
var backoff uint32
// TODO: tweak backoff parameters on other architectures.
if GOARCH == "arm64" {
backoff = 128
}
for {
old := atomic.Load64((*uint64)(head))
if old == 0 {
return nil
}
node := lfstackUnpack(old)
next := atomic.Load64(&node.next)
if atomic.Cas64((*uint64)(head), old, next) {
return unsafe.Pointer(node)
}
// Use a backoff approach to reduce demand to the shared memory location
// decreases memory contention and allows for other threads to make quicker
// progress.
// Read more in this Arm blog post:
// https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/multi-threaded-applications-arm
procyield(backoff)
// Increase backoff time.
backoff += backoff / 2
}
}
func (head *lfstack) empty() bool {
return atomic.Load64((*uint64)(head)) == 0
}
// lfnodeValidate panics if node is not a valid address for use with
// lfstack.push. This only needs to be called when node is allocated.
func lfnodeValidate(node *lfnode) {
if base, _, _ := findObject(uintptr(unsafe.Pointer(node)), 0, 0); base != 0 {
throw("lfstack node allocated from the heap")
}
lfstackPack(node, ^uintptr(0))
}
func lfstackPack(node *lfnode, cnt uintptr) uint64 {
return uint64(taggedPointerPack(unsafe.Pointer(node), cnt&(1<<tagBits-1)))
}
func lfstackUnpack(val uint64) *lfnode {
return (*lfnode)(taggedPointer(val).pointer())
}
|
