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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
|
//! Events from a traced process to its tracer through shared memory: many
//! producers (the target's threads), one consumer (the tracer). Lossless by
//! default: a producer waits when the ring is full.
//!
//! The file is a header page and `capacity` data bytes; the data is mapped
//! twice in a row, so a record never needs splitting at the end. A record is
//! a u64 word (payload length, and the commit bit set last), an `Event`, and
//! the payload padded to 8 bytes. Free space is always zero (the consumer
//! clears what it reads), so a reserved record not yet written reads as
//! uncommitted.
//!
//! Only raw syscalls and atomics: the agent calls `emit` from inside malloc
//! and signal handlers.
const Ring = @This();
const std = @import("std");
const linux = std.os.linux;
const event = @import("event.zig");
const Event = event.Event;
pub const magic: u64 = 0x31474e4952545a; // "ZTRING1"
const header_size = 4096;
const commit_bit: u64 = 1 << 63;
const record_overhead = 8 + @sizeOf(Event);
pub const Header = extern struct {
magic: u64,
/// Data bytes, a power of two.
capacity: u64,
/// Bytes ever reserved by producers.
head: std.atomic.Value(u64) align(64),
/// Bytes ever consumed.
tail: std.atomic.Value(u64) align(64),
/// Events dropped because the ring was full and `lossy` was set.
dropped: std.atomic.Value(u64) align(64),
/// A set of `Kind.bit`s: a producer that emits one of these waits, after
/// committing it, until the consumer calls `resumeAll`. This is how the
/// tracer stops the target at an event without ptrace.
stop_mask: std.atomic.Value(u64),
/// Stopped producers whose record lies below this may continue.
acked: std.atomic.Value(u64),
resume_seq: std.atomic.Value(u32),
/// Producers now waiting in a stop.
stopped: std.atomic.Value(u32),
/// Drop instead of waiting when full.
lossy: std.atomic.Value(u32),
space_seq: std.atomic.Value(u32),
space_waiters: std.atomic.Value(u32),
data_seq: std.atomic.Value(u32),
consumer_sleeping: std.atomic.Value(u32),
};
pub const Record = struct { ev: *const Event, payload: []const u8 };
fd: linux.fd_t,
hdr: *Header,
data: [*]u8,
/// The consumer's: the head it last read. It reads the producers' cache
/// line again only when that is used up.
seen_head: u64 = 0,
/// The producers': a tail the consumer has passed, read again only when the
/// ring looks full against it.
seen_tail: std.atomic.Value(u64) = .init(0),
/// A new ring in an anonymous memory file. The fd is inheritable: a child
/// maps it with `attach`.
pub fn create(capacity: usize) !Ring {
std.debug.assert(std.math.isPowerOfTwo(capacity) and capacity >= header_size);
const fd = try check(linux.memfd_create("ztrace-ring", 0));
errdefer _ = linux.close(@intCast(fd));
_ = try check(linux.ftruncate(@intCast(fd), @intCast(header_size + capacity)));
var ring = try map(@intCast(fd), capacity);
ring.hdr.magic = magic;
ring.hdr.capacity = capacity;
return ring;
}
/// Maps a ring another process created.
pub fn attach(fd: linux.fd_t) !Ring {
const page = try check(linux.mmap(null, header_size, .{ .READ = true }, .{ .TYPE = .SHARED }, fd, 0));
const hdr: *const Header = @ptrFromInt(page);
const capacity = hdr.capacity;
const ok = hdr.magic == magic;
_ = linux.munmap(@ptrFromInt(page), header_size);
if (!ok) return error.NotARing;
return map(fd, capacity);
}
fn map(fd: linux.fd_t, capacity: usize) !Ring {
const rw: linux.PROT = .{ .READ = true, .WRITE = true };
const base = try check(linux.mmap(null, header_size + 2 * capacity, .{}, .{ .TYPE = .PRIVATE, .ANONYMOUS = true }, -1, 0));
const ptr: [*]u8 = @ptrFromInt(base);
_ = try check(linux.mmap(ptr, header_size + capacity, rw, .{ .TYPE = .SHARED, .FIXED = true }, fd, 0));
_ = try check(linux.mmap(ptr + header_size + capacity, capacity, rw, .{ .TYPE = .SHARED, .FIXED = true }, fd, header_size));
return .{ .fd = fd, .hdr = @ptrCast(@alignCast(ptr)), .data = ptr + header_size };
}
pub fn close(r: *Ring) void {
_ = linux.munmap(@ptrCast(r.hdr), header_size + 2 * r.hdr.capacity);
_ = linux.close(r.fd);
}
fn check(rc: usize) !usize {
return if (linux.errno(rc) == .SUCCESS) rc else error.RingSyscall;
}
fn futexWait(word: *const std.atomic.Value(u32), expect: u32, timeout_ns: ?u64) void {
const ts: ?linux.timespec = if (timeout_ns) |ns| .{ .sec = @intCast(ns / std.time.ns_per_s), .nsec = @intCast(ns % std.time.ns_per_s) } else null;
_ = linux.futex_4arg(word, .{ .cmd = .WAIT, .private = false }, expect, if (ts) |*t| t else null);
}
fn futexWake(word: *const std.atomic.Value(u32)) void {
_ = linux.futex_3arg(word, .{ .cmd = .WAKE, .private = false }, std.math.maxInt(i32));
}
// Producer side.
pub fn emit(r: *Ring, ev: Event, payload: []const u8) void {
const h = r.hdr;
const need = record_overhead + std.mem.alignForward(usize, payload.len, 8);
// A record the ring could never hold is dropped, not waited for: the
// caller splits large payloads (a `mem_write` by address).
if (need > h.capacity) {
_ = h.dropped.fetchAdd(1, .monotonic);
return;
}
var at = h.head.load(.monotonic);
while (true) {
// A tail past `at` means `at` is stale (others reserved, and were
// consumed, since it was loaded): not full, and the exchange below
// fails and loads the head again. Hence the saturating subtractions.
if (at + need -| r.seen_tail.load(.monotonic) > h.capacity) r.seen_tail.store(h.tail.load(.acquire), .monotonic);
if (at + need -| r.seen_tail.load(.monotonic) > h.capacity) {
if (h.lossy.load(.monotonic) != 0) {
_ = h.dropped.fetchAdd(1, .monotonic);
return;
}
// Full: wait for the consumer. The timeout covers a wake lost
// between the check and the wait.
const seq = h.space_seq.load(.acquire);
_ = h.space_waiters.fetchAdd(1, .seq_cst);
if (at + need -| h.tail.load(.seq_cst) > h.capacity) futexWait(&h.space_seq, seq, std.time.ns_per_ms);
_ = h.space_waiters.fetchSub(1, .monotonic);
at = h.head.load(.monotonic);
continue;
}
at = h.head.cmpxchgWeak(at, at + need, .acquire, .monotonic) orelse break;
}
const rec = r.data + (at & (h.capacity - 1));
@memcpy(rec[8..][0..@sizeOf(Event)], std.mem.asBytes(&ev));
@memcpy(rec[record_overhead..][0..payload.len], payload);
@atomicStore(u64, @as(*u64, @ptrCast(@alignCast(rec))), payload.len | commit_bit, .release);
if (h.consumer_sleeping.load(.seq_cst) != 0) {
_ = h.data_seq.fetchAdd(1, .release);
futexWake(&h.data_seq);
}
if (h.stop_mask.load(.monotonic) & ev.kind.bit() != 0) {
_ = h.stopped.fetchAdd(1, .release);
while (true) {
const seq = h.resume_seq.load(.seq_cst);
if (h.acked.load(.seq_cst) > at) break;
futexWait(&h.resume_seq, seq, null);
}
_ = h.stopped.fetchSub(1, .release);
}
}
pub fn sink(r: *Ring) event.Sink {
return .{ .ctx = r, .emitFn = sinkEmit };
}
fn sinkEmit(ctx: *anyopaque, ev: *const Event, payload: []const u8) anyerror!void {
const r: *Ring = @ptrCast(@alignCast(ctx));
r.emit(ev.*, payload);
}
// Consumer side.
/// The oldest record, valid until `advance`. Null when there is none, or it
/// is still being written.
pub fn peek(r: *Ring) ?Record {
const h = r.hdr;
const t = h.tail.load(.monotonic);
if (t == r.seen_head) {
r.seen_head = h.head.load(.acquire);
if (t == r.seen_head) return null;
}
const rec = r.data + (t & (h.capacity - 1));
const word = @atomicLoad(u64, @as(*const u64, @ptrCast(@alignCast(rec))), .acquire);
if (word & commit_bit == 0) return null;
const len: usize = @intCast(word & ~commit_bit);
return .{ .ev = @ptrCast(@alignCast(rec + 8)), .payload = rec[record_overhead..][0..len] };
}
/// Consumes the record `peek` returned.
pub fn advance(r: *Ring, rec: Record) void {
const h = r.hdr;
const size = record_overhead + std.mem.alignForward(usize, rec.payload.len, 8);
const start: [*]u8 = @ptrFromInt(@intFromPtr(rec.ev) - 8);
@memset(start[0..size], 0);
const tail = h.tail.fetchAdd(size, .seq_cst) + size;
// A producer waiting for room is woken once half the ring is free, not
// at every record: the wake is a syscall, and it would be back waiting
// a record later.
if (h.space_waiters.load(.seq_cst) != 0 and h.head.load(.acquire) - tail <= h.capacity / 2) {
_ = h.space_seq.fetchAdd(1, .release);
futexWake(&h.space_seq);
}
}
/// Everything committed so far, into `to`. Returns the number of events.
pub fn drain(r: *Ring, to: event.Sink) !usize {
var n: usize = 0;
while (r.peek()) |rec| : (n += 1) {
try to.emit(rec.ev.*, rec.payload);
r.advance(rec);
}
return n;
}
/// Sleeps until a producer commits something, or the timeout.
pub fn wait(r: *Ring, timeout_ns: u64) void {
const h = r.hdr;
const seq = h.data_seq.load(.acquire);
h.consumer_sleeping.store(1, .seq_cst);
if (r.peek() == null) futexWait(&h.data_seq, seq, timeout_ns);
h.consumer_sleeping.store(0, .release);
}
/// Lets every producer stopped at a record already consumed continue.
pub fn resumeAll(r: *Ring) void {
r.hdr.acked.store(r.hdr.tail.load(.seq_cst), .seq_cst);
_ = r.hdr.resume_seq.fetchAdd(1, .seq_cst);
futexWake(&r.hdr.resume_seq);
}
test "records survive the wrap, payloads included" {
var ring = try Ring.create(4096);
defer ring.close();
var payload: [200]u8 = undefined;
// 264 bytes a record and a 4096-byte ring: the wrap falls inside one.
for (0..100) |i| {
@memset(&payload, @intCast(i));
ring.emit(.{ .kind = .mem_write, .a = .{ i, 0, 0, 0, 0, 0 } }, payload[0 .. i + 1]);
const rec = ring.peek().?;
try std.testing.expectEqual(i, rec.ev.a[0]);
try std.testing.expectEqual(i + 1, rec.payload.len);
try std.testing.expectEqual(@as(u8, @intCast(i)), rec.payload[i]);
ring.advance(rec);
}
try std.testing.expect(ring.peek() == null);
}
test "a second mapping sees the first's events; a full lossy ring drops" {
var a = try Ring.create(4096);
defer a.close();
var b = try Ring.attach(a.fd);
defer _ = linux.munmap(@ptrCast(b.hdr), header_size + 2 * b.hdr.capacity);
a.hdr.lossy.store(1, .monotonic);
for (0..100) |i| a.emit(.{ .kind = .step, .a = .{ i, 0, 0, 0, 0, 0 } }, "");
try std.testing.expectEqual(4096 / record_overhead, 100 - a.hdr.dropped.load(.monotonic));
try std.testing.expectEqual(@as(u64, 0), b.peek().?.ev.a[0]);
// One too large for the ring at all is dropped too, lossy or not.
a.hdr.lossy.store(0, .monotonic);
const dropped = a.hdr.dropped.load(.monotonic);
var big: [4096]u8 = undefined;
a.emit(.{ .kind = .mem_write }, &big);
try std.testing.expectEqual(dropped + 1, a.hdr.dropped.load(.monotonic));
}
test "producers on other threads, a stop and a resume" {
var ring = try Ring.create(1 << 16);
defer ring.close();
ring.hdr.stop_mask.store(event.Kind.mark.bit(), .monotonic);
const per = 20_000;
const producer = struct {
fn run(r: *Ring, id: u64) void {
for (0..per) |i| r.emit(.{ .kind = .step, .a = .{ id, i, 0, 0, 0, 0 } }, "");
r.emit(.{ .kind = .mark, .a = .{ id, 0, 0, 0, 0, 0 } }, "done");
}
};
var threads: [4]std.Thread = undefined;
for (&threads, 0..) |*t, id| t.* = try std.Thread.spawn(.{}, producer.run, .{ &ring, id });
var next: [4]u64 = @splat(0);
var marks: usize = 0;
while (marks < 4) {
const rec = ring.peek() orelse {
ring.wait(std.time.ns_per_ms);
continue;
};
const id = rec.ev.a[0];
if (rec.ev.kind == .mark) marks += 1 else {
try std.testing.expectEqual(next[id], rec.ev.a[1]);
next[id] += 1;
}
ring.advance(rec);
}
// Every producer is held at its mark until resumed.
while (ring.hdr.stopped.load(.acquire) != 4) _ = linux.sched_yield();
ring.resumeAll();
for (threads) |t| t.join();
try std.testing.expectEqual(@as(u64, 0), ring.hdr.dropped.load(.monotonic));
}
|