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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
const std = @import("std");
const Atomic = std.atomic.Atomic;
const Futex = @import("./futex.zig");
// Credit: this is copypasta from @kprotty. Thank you @kprotty!
pub const Mutex = struct {
state: Atomic(u32) = Atomic(u32).init(UNLOCKED),
const UNLOCKED = 0;
const LOCKED = 0b01;
const CONTENDED = 0b11;
const is_x86 = @import("builtin").target.cpu.arch.isX86();
pub fn tryAcquire(self: *Mutex) bool {
return self.acquireFast(true);
}
pub fn acquire(self: *Mutex) void {
if (!self.acquireFast(false)) {
self.acquireSlow();
}
}
inline fn acquireFast(self: *Mutex, comptime strong: bool) bool {
// On x86, "lock bts" uses less i-cache & can be faster than "lock cmpxchg" below.
if (comptime is_x86) {
return self.state.bitSet(@ctz(@as(u32, LOCKED)), .Acquire) == UNLOCKED;
}
const cas_fn = comptime switch (strong) {
true => "compareAndSwap",
else => "tryCompareAndSwap",
};
return @field(self.state, cas_fn)(
UNLOCKED,
LOCKED,
.Acquire,
.Monotonic,
) == null;
}
noinline fn acquireSlow(self: *Mutex) void {
// Spin a little bit on the Mutex state in the hopes that
// we can acquire it without having to call Futex.wait().
// Give up spinning if the Mutex is contended.
// This helps acquire() latency under micro-contention.
//
var spin: u8 = 100;
while (spin > 0) : (spin -= 1) {
std.atomic.spinLoopHint();
switch (self.state.load(.Monotonic)) {
UNLOCKED => _ = self.state.tryCompareAndSwap(
UNLOCKED,
LOCKED,
.Acquire,
.Monotonic,
) orelse return,
LOCKED => continue,
CONTENDED => break,
else => unreachable, // invalid Mutex state
}
}
// Make sure the state is CONTENDED before sleeping with Futex so release() can wake us up.
// Transitioning to CONTENDED may also acquire the mutex in the process.
//
// If we sleep, we must acquire the Mutex with CONTENDED to ensure that other threads
// sleeping on the Futex having seen CONTENDED before are eventually woken up by release().
// This unfortunately ends up in an extra Futex.wake() for the last thread but that's ok.
while (true) : (Futex.wait(&self.state, CONTENDED, null) catch unreachable) {
// On x86, "xchg" can be faster than "lock cmpxchg" below.
if (comptime is_x86) {
switch (self.state.swap(CONTENDED, .Acquire)) {
UNLOCKED => return,
LOCKED, CONTENDED => continue,
else => unreachable, // invalid Mutex state
}
}
var state = self.state.load(.Monotonic);
while (state != CONTENDED) {
state = switch (state) {
UNLOCKED => self.state.tryCompareAndSwap(state, CONTENDED, .Acquire, .Monotonic) orelse return,
LOCKED => self.state.tryCompareAndSwap(state, CONTENDED, .Monotonic, .Monotonic) orelse break,
CONTENDED => unreachable, // checked above
else => unreachable, // invalid Mutex state
};
}
}
}
pub fn release(self: *Mutex) void {
switch (self.state.swap(UNLOCKED, .Release)) {
UNLOCKED => unreachable, // released without being acquired
LOCKED => {},
CONTENDED => Futex.wake(&self.state, 1),
else => unreachable, // invalid Mutex state
}
}
};
pub const Lock = struct {
mutex: Mutex,
pub fn init() Lock {
return Lock{ .mutex = Mutex{} };
}
pub inline fn lock(this: *Lock) void {
this.mutex.acquire();
}
pub inline fn unlock(this: *Lock) void {
this.mutex.release();
}
};
pub fn spinCycle() void {}
|
