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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
const std = @import("index.zig");
const builtin = @import("builtin");
const AtomicOrder = builtin.AtomicOrder;
const AtomicRmwOp = builtin.AtomicRmwOp;
const assert = std.debug.assert;
const SpinLock = std.SpinLock;
const linux = std.os.linux;
const windows = std.os.windows;
/// Lock may be held only once. If the same thread
/// tries to acquire the same mutex twice, it deadlocks.
/// The Linux implementation is based on mutex3 from
/// https://www.akkadia.org/drepper/futex.pdf
pub const Mutex = switch(builtin.os) {
builtin.Os.linux => struct {
/// 0: unlocked
/// 1: locked, no waiters
/// 2: locked, one or more waiters
lock: i32,
pub const Held = struct {
mutex: *Mutex,
pub fn release(self: Held) void {
const c = @atomicRmw(i32, &self.mutex.lock, AtomicRmwOp.Sub, 1, AtomicOrder.Release);
if (c != 1) {
_ = @atomicRmw(i32, &self.mutex.lock, AtomicRmwOp.Xchg, 0, AtomicOrder.Release);
const rc = linux.futex_wake(&self.mutex.lock, linux.FUTEX_WAKE | linux.FUTEX_PRIVATE_FLAG, 1);
switch (linux.getErrno(rc)) {
0 => {},
linux.EINVAL => unreachable,
else => unreachable,
}
}
}
};
pub fn init() Mutex {
return Mutex {
.lock = 0,
};
}
pub fn deinit(self: *Mutex) void {}
pub fn acquire(self: *Mutex) Held {
var c = @cmpxchgWeak(i32, &self.lock, 0, 1, AtomicOrder.Acquire, AtomicOrder.Monotonic) orelse
return Held{ .mutex = self };
if (c != 2)
c = @atomicRmw(i32, &self.lock, AtomicRmwOp.Xchg, 2, AtomicOrder.Acquire);
while (c != 0) {
const rc = linux.futex_wait(&self.lock, linux.FUTEX_WAIT | linux.FUTEX_PRIVATE_FLAG, 2, null);
switch (linux.getErrno(rc)) {
0, linux.EINTR, linux.EAGAIN => {},
linux.EINVAL => unreachable,
else => unreachable,
}
c = @atomicRmw(i32, &self.lock, AtomicRmwOp.Xchg, 2, AtomicOrder.Acquire);
}
return Held { .mutex = self };
}
},
builtin.Os.windows => struct {
lock: ?*windows.RTL_CRITICAL_SECTION,
pub const Held = struct {
mutex: *Mutex,
pub fn release(self: Held) void {
windows.LeaveCriticalSection(self.mutex.lock);
}
};
pub fn init() Mutex {
var lock: ?*windows.RTL_CRITICAL_SECTION = null;
windows.InitializeCriticalSection(lock);
return Mutex { .lock = lock };
}
pub fn deinit(self: *Mutex) void {
if (self.lock != null) {
windows.DeleteCriticalSection(self.lock);
self.lock = null;
}
}
pub fn acquire(self: *Mutex) Held {
windows.EnterCriticalSection(self.lock);
return Held { .mutex = self };
}
},
else => struct {
/// TODO better implementation than spin lock
lock: SpinLock,
pub const Held = struct {
mutex: *Mutex,
pub fn release(self: Held) void {
SpinLock.Held.release(SpinLock.Held { .spinlock = &self.mutex.lock });
}
};
pub fn init() Mutex {
return Mutex {
.lock = SpinLock.init(),
};
}
pub fn deinit(self: *Mutex) void {}
pub fn acquire(self: *Mutex) Held {
_ = self.lock.acquire();
return Held { .mutex = self };
}
},
};
const Context = struct {
mutex: *Mutex,
data: i128,
const incr_count = 10000;
};
test "std.Mutex" {
var direct_allocator = std.heap.DirectAllocator.init();
defer direct_allocator.deinit();
var plenty_of_memory = try direct_allocator.allocator.alloc(u8, 300 * 1024);
defer direct_allocator.allocator.free(plenty_of_memory);
var fixed_buffer_allocator = std.heap.ThreadSafeFixedBufferAllocator.init(plenty_of_memory);
var a = &fixed_buffer_allocator.allocator;
var mutex = Mutex.init();
defer mutex.deinit();
var context = Context{
.mutex = &mutex,
.data = 0,
};
const thread_count = 10;
var threads: [thread_count]*std.os.Thread = undefined;
for (threads) |*t| {
t.* = try std.os.spawnThread(&context, worker);
}
for (threads) |t|
t.wait();
std.debug.assertOrPanic(context.data == thread_count * Context.incr_count);
}
fn worker(ctx: *Context) void {
var i: usize = 0;
while (i != Context.incr_count) : (i += 1) {
const held = ctx.mutex.acquire();
defer held.release();
ctx.data += 1;
}
}
|
