From 0b29354e1ddf6cf75ac4c426a00dd3435ace5069 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 10 Nov 2026 11:08:49 -0300 Subject: ztrace: the event, the ring, the recording, a ptrace loop One 64-byte Event for every backend; a shared-memory ring from target to tracer with stop/resume; a Recorder that folds events into xitdb moments (registers, memory in 64-byte chunks with known-byte masks, strings) and a Trace that reads any moment back; a minimal ptrace Process; ztrace record, run and dump. Per-area build files so the areas grow apart. --- .gitignore | 5 + README.md | 61 ++++++++++ build.zig | 84 +++++++++++++ build.zig.zon | 13 +++ build/agent.zig | 5 + build/anim.zig | 5 + build/debugger.zig | 5 + build/kernel.zig | 5 + build/llvm.zig | 5 + src/cli/dump.zig | 39 +++++++ src/cli/main.zig | 37 ++++++ src/cli/record.zig | 112 ++++++++++++++++++ src/cli/run.zig | 63 ++++++++++ src/cli/util.zig | 27 +++++ src/trace/Ring.zig | 277 +++++++++++++++++++++++++++++++++++++++++++ src/trace/client.zig | 56 +++++++++ src/trace/event.zig | 163 ++++++++++++++++++++++++++ src/trace/host.zig | 71 +++++++++++ src/trace/ptrace.zig | 158 +++++++++++++++++++++++++ src/trace/root.zig | 24 ++++ src/trace/store.zig | 325 +++++++++++++++++++++++++++++++++++++++++++++++++++ targets/emit.zig | 14 +++ targets/fib.c | 12 ++ 23 files changed, 1566 insertions(+) create mode 100644 .gitignore create mode 100644 README.md create mode 100644 build.zig create mode 100644 build.zig.zon create mode 100644 build/agent.zig create mode 100644 build/anim.zig create mode 100644 build/debugger.zig create mode 100644 build/kernel.zig create mode 100644 build/llvm.zig create mode 100644 src/cli/dump.zig create mode 100644 src/cli/main.zig create mode 100644 src/cli/record.zig create mode 100644 src/cli/run.zig create mode 100644 src/cli/util.zig create mode 100644 src/trace/Ring.zig create mode 100644 src/trace/client.zig create mode 100644 src/trace/event.zig create mode 100644 src/trace/host.zig create mode 100644 src/trace/ptrace.zig create mode 100644 src/trace/root.zig create mode 100644 src/trace/store.zig create mode 100644 targets/emit.zig create mode 100644 targets/fib.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..1b2ab82 --- /dev/null +++ b/.gitignore @@ -0,0 +1,5 @@ +.zig-cache/ +zig-out/ +zig-pkg/ +*.ztrace +.ws/ diff --git a/README.md b/README.md new file mode 100644 index 0000000..07b0571 --- /dev/null +++ b/README.md @@ -0,0 +1,61 @@ +# computeranim + +Two things that meet at a file: + +- **ztrace**, a small tracer/debugger: many ways to watch a program run, one + event format, one recording. +- **canim**, animations of what was recorded (registers, memory, syscalls, + data structures, source), written as code, exported as frames for ffmpeg. + +```sh +zig build # zig-out/bin/ztrace +zig build test # everything; test- for one +ztrace record -o fib.ztrace -- ./fib 10 # under ptrace, an instruction a moment +ztrace record --syscalls -- ls / # ... or a syscall a moment +ztrace run --preload libztrace-agent.so -- ./prog # in-process, no ptrace +ztrace dump fib.ztrace +``` + +## The pieces + +| Where | What | +| --- | --- | +| `src/trace/event.zig` | `Event` (64 bytes: time, thread, kind, six words) plus a payload; `Kind`; `Regs`; `Sink` | +| `src/trace/Ring.zig` | events from the target to the tracer through shared memory; a producer can be held at a kind (`stop_mask`) until `resumeAll` | +| `src/trace/client.zig`, `host.zig` | the ring's two ends: inside the target, inside the tracer | +| `src/trace/store.zig` | `Recorder` (a `Sink`) and `Trace`: the recording, in xitdb | +| `src/trace/ptrace.zig` | the out-of-process backend | +| `src/agent/` | the in-process backend: a library preloaded or linked into the target | +| `llvm/` | compiler instrumentation and its runtime | +| `src/trace/kernel*` | perf events and BPF | +| `src/anim/`, `scenes/` | the animation library and its scenes | +| `src/cli/` | the `ztrace` command, a file a subcommand | +| `targets/` | programs to trace | +| `build/` | each area's part of the build | + +Every backend produces `Event`s into a `Sink`. The recorder is one; the ring +is another, with the recorder at its far end. + +## A recording + +An xitdb file: a history of immutable **moments**. A moment is the state +then (registers per thread, every byte of memory seen so far, the strings +defined), sharing what did not change with the moment before, and the +events that led to it. `Trace.moment(i)` is any of them, in any order: time +travel is an index. + +The recorder ends a moment at the kinds in `Recorder.cut` (by default a +step, a breakpoint, a syscall's exit, a signal, a source line, a mark), so +the cost of time travel is chosen per recording. Measured (release, this +machine): a moment costs about 10 µs and 1 KB before its own data; an +instruction-level recording of `fib(12)`, 145 000 moments, is 245 MB at +56 000 moments a second; events inside a moment cost their own bytes only. + +## Depends on + +- [sketchbook](../sketchbook): window, drawing, shaders, hot reload, the + manim-style `anim` module, frame export. +- [pardes](../02-pardes-code): tree-sitter parsing, highlighting, themes. +- [xitdb](https://github.com/xit-vcs/xitdb): the recording. + +x86-64 Linux, Zig 0.17. diff --git a/build.zig b/build.zig new file mode 100644 index 0000000..cbcd493 --- /dev/null +++ b/build.zig @@ -0,0 +1,84 @@ +const std = @import("std"); + +/// What each area's build file (`build/*.zig`) is handed. +pub const Ctx = struct { + b: *std.Build, + target: std.Build.ResolvedTarget, + optimize: std.builtin.OptimizeMode, + /// The tracing library: events, ring, recorder, backends. + ztrace: *std.Build.Module, + /// The `ztrace` command. + exe: *std.Build.Step.Compile, + /// `zig build test`: everything. + test_step: *std.Build.Step, + + /// A C program to trace, from `targets/`: -O1 with debug info, frame + /// pointers kept, so its code is short and still maps to its source. + pub fn cTarget(ctx: Ctx, name: []const u8, files: []const []const u8) *std.Build.Step.Compile { + const mod = ctx.b.createModule(.{ .target = ctx.target, .optimize = .Debug, .link_libc = true, .omit_frame_pointer = false }); + mod.addCSourceFiles(.{ .root = ctx.b.path("targets"), .files = files, .flags = &.{ "-O1", "-g", "-fno-omit-frame-pointer" } }); + return ctx.b.addExecutable(.{ .name = name, .root_module = mod }); + } + + /// A Zig program to trace, from `targets/`, with the library importable + /// as `ztrace`. + pub fn zigTarget(ctx: Ctx, name: []const u8, file: []const u8) *std.Build.Step.Compile { + return ctx.b.addExecutable(.{ .name = name, .root_module = ctx.b.createModule(.{ + .root_source_file = ctx.b.path(file), + .target = ctx.target, + .optimize = ctx.optimize, + .imports = &.{.{ .name = "ztrace", .module = ctx.ztrace }}, + }) }); + } + + /// A step of its own for one area's tests, also part of `test`. + pub fn areaTest(ctx: Ctx, name: []const u8, description: []const u8) *std.Build.Step { + const step = ctx.b.step(name, description); + ctx.test_step.dependOn(step); + return step; + } +}; + +pub fn build(b: *std.Build) void { + const target = b.standardTargetOptions(.{}); + const optimize = b.standardOptimizeOption(.{}); + + const xitdb = b.dependency("xitdb", .{}).module("xitdb"); + const ztrace = b.addModule("ztrace", .{ + .root_source_file = b.path("src/trace/root.zig"), + .target = target, + .optimize = optimize, + .imports = &.{.{ .name = "xitdb", .module = xitdb }}, + }); + + const exe = b.addExecutable(.{ .name = "ztrace", .root_module = b.createModule(.{ + .root_source_file = b.path("src/cli/main.zig"), + .target = target, + .optimize = optimize, + .imports = &.{.{ .name = "ztrace", .module = ztrace }}, + }) }); + b.installArtifact(exe); + + const ctx: Ctx = .{ .b = b, .target = target, .optimize = optimize, .ztrace = ztrace, .exe = exe, .test_step = b.step("test", "Run every test") }; + + // The library's own tests, and a target with its own producer recorded + // through the ring. + const core = ctx.areaTest("test-core", "Events, ring, recorder, ptrace basics"); + core.dependOn(&b.addRunArtifact(b.addTest(.{ .root_module = ztrace })).step); + const emit = b.addRunArtifact(exe); + emit.addArgs(&.{ "run", "-o" }); + _ = emit.addOutputFileArg("emit.ztrace"); + emit.addArg("--"); + emit.addArtifactArg(ctx.zigTarget("emit", "targets/emit.zig")); + emit.addArg("5000"); + emit.expectStdErrMatch("5001 events (0 dropped)"); + emit.expectStdErrMatch("exit 7"); + core.dependOn(&emit.step); + + // Each area adds its own artifacts, targets and test step. + @import("build/debugger.zig").add(ctx); + @import("build/agent.zig").add(ctx); + @import("build/llvm.zig").add(ctx); + @import("build/kernel.zig").add(ctx); + @import("build/anim.zig").add(ctx); +} diff --git a/build.zig.zon b/build.zig.zon new file mode 100644 index 0000000..e144c08 --- /dev/null +++ b/build.zig.zon @@ -0,0 +1,13 @@ +.{ + .name = .computeranim, + .version = "0.0.1", + .dependencies = .{ + .xitdb = .{ + .url = "https://github.com/xit-vcs/xitdb/archive/6b93af1af3a260399fa0a0b1b268ded2cbf5eec5.tar.gz", + .hash = "xitdb-0.0.0-EEFkxhwmBwDz1N8H9oHhVhd1Al5YZp8iDhaMLm2_79pS", + }, + }, + .minimum_zig_version = "0.17.0", + .paths = .{""}, + .fingerprint = 0x52dcabb102ca943e, +} diff --git a/build/agent.zig b/build/agent.zig new file mode 100644 index 0000000..d3c7eb3 --- /dev/null +++ b/build/agent.zig @@ -0,0 +1,5 @@ +const Ctx = @import("../build.zig").Ctx; + +pub fn add(ctx: Ctx) void { + _ = ctx; +} diff --git a/build/anim.zig b/build/anim.zig new file mode 100644 index 0000000..d3c7eb3 --- /dev/null +++ b/build/anim.zig @@ -0,0 +1,5 @@ +const Ctx = @import("../build.zig").Ctx; + +pub fn add(ctx: Ctx) void { + _ = ctx; +} diff --git a/build/debugger.zig b/build/debugger.zig new file mode 100644 index 0000000..d3c7eb3 --- /dev/null +++ b/build/debugger.zig @@ -0,0 +1,5 @@ +const Ctx = @import("../build.zig").Ctx; + +pub fn add(ctx: Ctx) void { + _ = ctx; +} diff --git a/build/kernel.zig b/build/kernel.zig new file mode 100644 index 0000000..d3c7eb3 --- /dev/null +++ b/build/kernel.zig @@ -0,0 +1,5 @@ +const Ctx = @import("../build.zig").Ctx; + +pub fn add(ctx: Ctx) void { + _ = ctx; +} diff --git a/build/llvm.zig b/build/llvm.zig new file mode 100644 index 0000000..d3c7eb3 --- /dev/null +++ b/build/llvm.zig @@ -0,0 +1,5 @@ +const Ctx = @import("../build.zig").Ctx; + +pub fn add(ctx: Ctx) void { + _ = ctx; +} diff --git a/src/cli/dump.zig b/src/cli/dump.zig new file mode 100644 index 0000000..a37ba59 --- /dev/null +++ b/src/cli/dump.zig @@ -0,0 +1,39 @@ +//! ztrace dump: a recording's events, a line each. +const std = @import("std"); +const zt = @import("ztrace"); +const util = @import("util.zig"); + +pub const usage = + \\usage: ztrace dump FILE + \\ + \\Prints every event of a recording: moment, kind, thread, arguments, + \\payload size. + \\ +; + +pub fn run(init: std.process.Init, args: []const [:0]const u8) !void { + if (args.len != 1) util.fail(usage, .{}); + var trace = try zt.Trace.open(init.gpa, init.io, args[0]); + defer trace.close(); + var buf: [4096]u8 = undefined; + var file_writer = std.Io.File.stdout().writer(init.io, &buf); + const w = &file_writer.interface; + print(init.gpa, &trace, w) catch |err| switch (err) { + // The reader went away (`| head`): not an error. + error.WriteFailed => return, + else => |e| return e, + }; +} + +fn print(gpa: std.mem.Allocator, trace: *zt.Trace, w: *std.Io.Writer) !void { + for (0..trace.len) |index| { + const moment = try trace.moment(index); + var events = try moment.events(gpa); + defer events.deinit(gpa); + while (events.next()) |item| { + const ev = item.ev; + try w.print("{d:>6} {t:<13} tid={d} aux={d} a={x} {x} {x} +{d}\n", .{ index, ev.kind, ev.tid, ev.aux, ev.a[0], ev.a[1], ev.a[2], item.payload.len }); + } + } + try w.flush(); +} diff --git a/src/cli/main.zig b/src/cli/main.zig new file mode 100644 index 0000000..498f8d4 --- /dev/null +++ b/src/cli/main.zig @@ -0,0 +1,37 @@ +//! ztrace: many ways to watch a program, one recording. +const std = @import("std"); +const util = @import("util.zig"); + +/// A command is a file with `usage` and `run(init, args)`. +const commands = .{ + .record = @import("record.zig"), + .run = @import("run.zig"), + .dump = @import("dump.zig"), +}; + +const usage = + \\usage: ztrace COMMAND ... + \\ + \\ record run a program under ptrace into a recording + \\ run record a program that carries a ring producer (agent, instrumentation) + \\ dump print a recording's events + \\ + \\`ztrace COMMAND --help` for each. + \\ +; + +pub fn main(init: std.process.Init) !void { + const args = try init.minimal.args.toSlice(init.arena.allocator()); + if (args.len < 2) util.fail(usage, .{}); + inline for (@typeInfo(@TypeOf(commands)).@"struct".field_names) |name| { + if (std.mem.eql(u8, args[1], name)) { + const command = @field(commands, name); + if (args.len > 2 and std.mem.eql(u8, args[2], "--help")) { + std.debug.print("{s}", .{command.usage}); + return; + } + return command.run(init, args[2..]); + } + } + util.fail(usage, .{}); +} diff --git a/src/cli/record.zig b/src/cli/record.zig new file mode 100644 index 0000000..ab617d4 --- /dev/null +++ b/src/cli/record.zig @@ -0,0 +1,112 @@ +//! ztrace record: a program under ptrace, every stop a moment. +const std = @import("std"); +const zt = @import("ztrace"); +const util = @import("util.zig"); +const fail = util.fail; + +pub const usage = + \\usage: ztrace record [-o FILE] [--steps N] [--syscalls] [--stack BYTES] -- PROGRAM [ARGS] + \\ + \\Runs PROGRAM under ptrace into a recording (default out.ztrace): every + \\instruction, or with --syscalls every syscall. --steps stops after N + \\moments. --stack records that many bytes above the stack pointer at each + \\stop (default 128). + \\ +; + +pub fn run(init: std.process.Init, args: []const [:0]const u8) !void { + const arena = init.arena.allocator(); + var out: []const u8 = "out.ztrace"; + var max_moments: u64 = std.math.maxInt(u64); + var by_syscall = false; + var stack_bytes: usize = 128; + var i: usize = 0; + while (i < args.len) : (i += 1) { + const arg = args[i]; + if (std.mem.eql(u8, arg, "--")) { + i += 1; + break; + } else if (std.mem.eql(u8, arg, "-o") and i + 1 < args.len) { + i += 1; + out = args[i]; + } else if (std.mem.eql(u8, arg, "--steps") and i + 1 < args.len) { + i += 1; + max_moments = std.fmt.parseInt(u64, args[i], 0) catch fail("--steps needs a number\n", .{}); + } else if (std.mem.eql(u8, arg, "--stack") and i + 1 < args.len) { + i += 1; + stack_bytes = std.fmt.parseInt(usize, args[i], 0) catch fail("--stack needs a number\n", .{}); + } else if (std.mem.eql(u8, arg, "--syscalls")) { + by_syscall = true; + } else fail(usage, .{}); + } + if (i >= args.len) fail(usage, .{}); + + const path = try util.resolve(init, args[i]); + const argv = try util.targetArgv(arena, args[i..]); + var proc = try zt.ptrace.Process.spawn(path, argv, init.minimal.environ.block.slice.ptr); + errdefer proc.kill(); + + var rec = try zt.Recorder.create(init.gpa, init.io, out); + const tid: u32 = @intCast(proc.pid); + const stack = try arena.alloc(u8, stack_bytes); + const stack_seen = try arena.alloc(u8, stack_bytes); + var stack_at: u64 = 0; + + var timer = zt.event.now(); + var exit_code: u64 = 0; + while (rec.moments < max_moments) { + const stop = if (by_syscall) try proc.syscall() else try proc.stepi(); + switch (stop) { + .exited => |code| { + exit_code = code; + try rec.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = .exit, .a = .{ code, 0, 0, 0, 0, 0 } }, ""); + break; + }, + .killed => |sig| { + exit_code = 128 + @as(u64, @intFromEnum(sig)); + try rec.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = .exit, .a = .{ exit_code, 0, 0, 0, 0, 0 } }, ""); + break; + }, + .signal => |sig| try rec.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = .signal, .aux = @intCast(@intFromEnum(sig)) }, ""), + .trap, .syscall => { + const regs = try proc.regs(); + // The stack above rsp: only the bytes that changed since the last stop. + const n = proc.read(regs.rsp, stack); + if (regs.rsp != stack_at) @memset(stack_seen, 0); + var from: usize = 0; + while (from < n) { + if (regs.rsp == stack_at and stack[from] == stack_seen[from]) { + from += 1; + continue; + } + var to = from + 1; + while (to < n and (regs.rsp != stack_at or stack[to] != stack_seen[to])) to += 1; + try rec.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = .mem_write, .a = .{ regs.rsp + from, to - from, regs.rip, 0, 0, 0 } }, stack[from..to]); + from = to; + } + @memcpy(stack_seen[0..n], stack[0..n]); + stack_at = regs.rsp; + + const ev: zt.Event = if (stop == .trap) + .{ .ts = zt.event.now(), .tid = tid, .kind = .step, .a = .{ regs.rip, 0, 0, 0, 0, 0 } } + else if (proc.in_syscall) + .{ .ts = zt.event.now(), .tid = tid, .kind = .syscall_enter, .aux = @truncate(regs.orig_rax), .a = .{ regs.rdi, regs.rsi, regs.rdx, regs.r10, regs.r8, regs.r9 } } + else + .{ .ts = zt.event.now(), .tid = tid, .kind = .syscall_exit, .aux = @truncate(regs.orig_rax), .a = .{ regs.rax, 0, 0, 0, 0, 0 } }; + try rec.emit(ev, std.mem.asBytes(®s)); + }, + } + } else proc.kill(); + timer = zt.event.now() - timer; + + const moments = rec.moments + @intFromBool(rec.delta.items.len > 0); + const events = rec.count; + try rec.close(); + const size = (try std.Io.Dir.cwd().statFile(init.io, out, .{})).size; + std.debug.print("{s}: {d} moments, {d} events, {d} bytes ({d} bytes/moment), {d:.1} ms, {d:.0} moments/s, exit {d}\n", .{ + out, moments, + events, size, + size / @max(moments, 1), @as(f64, @floatFromInt(timer)) / 1e6, + @as(f64, @floatFromInt(moments)) / (@as(f64, @floatFromInt(timer)) / 1e9), exit_code, + }); +} diff --git a/src/cli/run.zig b/src/cli/run.zig new file mode 100644 index 0000000..c4f1b25 --- /dev/null +++ b/src/cli/run.zig @@ -0,0 +1,63 @@ +//! ztrace run: a program that carries a ring producer (the preloaded agent, +//! or instrumentation linked in), recorded at full speed, no ptrace. +const std = @import("std"); +const zt = @import("ztrace"); +const util = @import("util.zig"); +const fail = util.fail; + +pub const usage = + \\usage: ztrace run [-o FILE] [--preload LIB] [--ring BYTES] -- PROGRAM [ARGS] + \\ + \\Runs PROGRAM with a shared-memory ring in its environment and records + \\what it emits (default out.ztrace). --preload puts a library (the agent) + \\into it with LD_PRELOAD. --ring sizes the ring (a power of two, default + \\16 MiB). + \\ +; + +pub fn run(init: std.process.Init, args: []const [:0]const u8) !void { + const arena = init.arena.allocator(); + var out: []const u8 = "out.ztrace"; + var options: zt.host.Options = .{}; + var i: usize = 0; + while (i < args.len) : (i += 1) { + const arg = args[i]; + if (std.mem.eql(u8, arg, "--")) { + i += 1; + break; + } else if (std.mem.eql(u8, arg, "-o") and i + 1 < args.len) { + i += 1; + out = args[i]; + } else if (std.mem.eql(u8, arg, "--preload") and i + 1 < args.len) { + i += 1; + options.preload = args[i]; + } else if (std.mem.eql(u8, arg, "--ring") and i + 1 < args.len) { + i += 1; + options.ring_bytes = std.fmt.parseInt(usize, args[i], 0) catch 0; + if (!std.math.isPowerOfTwo(options.ring_bytes) or options.ring_bytes < 4096) fail("--ring needs a power of two, 4096 or more\n", .{}); + } else fail(usage, .{}); + } + if (i >= args.len) fail(usage, .{}); + + const path = try util.resolve(init, args[i]); + const argv = try util.targetArgv(arena, args[i..]); + var session = try zt.host.Session.spawn(arena, path, argv, init.minimal.environ.block.slice, options); + defer session.close(); + var rec = try zt.Recorder.create(init.gpa, init.io, out); + + const start = zt.event.now(); + while (try session.pump(rec.sink(), 10 * std.time.ns_per_ms)) {} + const ns = zt.event.now() - start; + + const events = rec.count; + const moments = rec.moments + @intFromBool(rec.delta.items.len > 0); + const dropped = session.ring.hdr.dropped.load(.monotonic); + try rec.close(); + const size = (try std.Io.Dir.cwd().statFile(init.io, out, .{})).size; + std.debug.print("{s}: {d} moments, {d} events ({d} dropped), {d} bytes, {d:.1} ms, {d:.0} events/s, exit {d}\n", .{ + out, moments, + events, dropped, + size, @as(f64, @floatFromInt(ns)) / 1e6, + @as(f64, @floatFromInt(events)) / (@as(f64, @floatFromInt(ns)) / 1e9), session.exit_code.?, + }); +} diff --git a/src/cli/util.zig b/src/cli/util.zig new file mode 100644 index 0000000..abdedd1 --- /dev/null +++ b/src/cli/util.zig @@ -0,0 +1,27 @@ +//! What every command needs. +const std = @import("std"); + +pub fn fail(comptime fmt: []const u8, args: anytype) noreturn { + std.debug.print(fmt, args); + std.process.exit(2); +} + +/// `name` as a path: itself with a slash in it, else the first match in PATH. +pub fn resolve(init: std.process.Init, name: [:0]const u8) ![*:0]const u8 { + if (std.mem.indexOfScalar(u8, name, '/') != null) return name.ptr; + const arena = init.arena.allocator(); + var dirs = std.mem.tokenizeScalar(u8, init.environ_map.get("PATH") orelse "/usr/bin:/bin", ':'); + while (dirs.next()) |dir| { + const candidate = try std.fs.path.joinZ(arena, &.{ dir, name }); + std.Io.Dir.cwd().access(init.io, candidate, .{ .execute = true }) catch continue; + return candidate.ptr; + } + fail("{s}: not found in PATH\n", .{name}); +} + +/// The arguments after a command's own, as the target's argv. +pub fn targetArgv(arena: std.mem.Allocator, args: []const [:0]const u8) ![:null]?[*:0]const u8 { + const argv = try arena.allocSentinel(?[*:0]const u8, args.len, null); + for (argv, args) |*dst, s| dst.* = s.ptr; + return argv; +} diff --git a/src/trace/Ring.zig b/src/trace/Ring.zig new file mode 100644 index 0000000..47b490b --- /dev/null +++ b/src/trace/Ring.zig @@ -0,0 +1,277 @@ +//! 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, + +/// 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); + std.debug.assert(need <= h.capacity); + var at = h.head.load(.monotonic); + while (true) { + if (at + need - h.tail.load(.acquire) > 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 == h.head.load(.acquire)) 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); + _ = h.tail.fetchAdd(size, .seq_cst); + if (h.space_waiters.load(.seq_cst) != 0) { + _ = 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]); +} + +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)); +} diff --git a/src/trace/client.zig b/src/trace/client.zig new file mode 100644 index 0000000..c8f2eea --- /dev/null +++ b/src/trace/client.zig @@ -0,0 +1,56 @@ +//! The producer side, inside the traced process: finds the ring its tracer +//! handed it and emits into it. Raw syscalls only, no libc, no allocation: +//! callable from a library constructor, from malloc, from a signal handler. +const std = @import("std"); +const linux = std.os.linux; +const event = @import("event.zig"); +const Ring = @import("Ring.zig"); + +/// The tracer sets this to the ring's inherited file descriptor. +pub const env_fd = "ZTRACE_RING_FD"; + +var ring: Ring = undefined; +/// 0 untried, 1 attaching, 2 attached, 3 no ring. +var state: std.atomic.Value(u8) = .init(0); + +/// The process's ring, attached on first use. Null when it is not traced. +pub fn get() ?*Ring { + while (true) switch (state.load(.acquire)) { + 2 => return &ring, + 3 => return null, + 1 => _ = linux.sched_yield(), + else => if (state.cmpxchgStrong(0, 1, .acquire, .monotonic) == null) { + const attached = if (envFd()) |fd| Ring.attach(fd) catch null else null; + if (attached) |r| ring = r; + state.store(if (attached != null) 2 else 3, .release); + }, + }; +} + +pub fn emit(kind: event.Kind, aux: u16, a: [6]u64, payload: []const u8) void { + const r = get() orelse return; + // shortcut: a gettid syscall per event; cache it per thread once the agent has TLS. + r.emit(.{ .ts = event.now(), .tid = @intCast(linux.gettid()), .kind = kind, .aux = aux, .a = a }, payload); +} + +/// `ZTRACE_RING_FD` from /proc/self/environ: a preloaded library cannot +/// count on libc's environ being set up yet. +fn envFd() ?linux.fd_t { + const rc = linux.open("/proc/self/environ", .{}, 0); + if (linux.errno(rc) != .SUCCESS) return null; + const fd: linux.fd_t = @intCast(rc); + defer _ = linux.close(fd); + var buf: [1 << 16]u8 = undefined; + var len: usize = 0; + while (len < buf.len) { + const n = linux.read(fd, buf[len..].ptr, buf.len - len); + if (linux.errno(n) != .SUCCESS or n == 0) break; + len += n; + } + var vars = std.mem.splitScalar(u8, buf[0..len], 0); + while (vars.next()) |v| { + if (!std.mem.startsWith(u8, v, env_fd ++ "=")) continue; + return std.fmt.parseInt(linux.fd_t, v[env_fd.len + 1 ..], 10) catch null; + } + return null; +} diff --git a/src/trace/event.zig b/src/trace/event.zig new file mode 100644 index 0000000..91e8c62 --- /dev/null +++ b/src/trace/event.zig @@ -0,0 +1,163 @@ +//! The one record every backend produces (ptrace, the in-process agent, +//! LLVM instrumentation, kernel tracing) and every consumer reads (the +//! recorder, the animations). 64 bytes, plus an optional payload carried +//! beside it. `extern` because it crosses processes (the ring) and is +//! written to disk (the recorder). +const std = @import("std"); + +pub const Kind = enum(u16) { + // Execution stops. Payload: `Regs`, when the backend has them. + /// a0=pc + step = 1, + /// a0=pc a1=breakpoint id + breakpoint = 2, + /// aux=nr a0..a5=args. Payload: optional decoded bytes (a path). + syscall_enter = 3, + /// aux=nr a0=return value + syscall_exit = 4, + /// aux=signo a0=fault address a1=pc + signal = 5, + /// a0=exit code, or 128+signo when killed + exit = 6, + /// a0=new tid + thread_start = 7, + thread_exit = 8, + + // Memory. + /// a0=addr a1=len. Payload: the bytes now at addr (len of them). + mem_write = 16, + /// a0=addr a1=len a2=pc + mem_read = 17, + /// a0=ptr a1=size a2=caller pc. aux: `Alloc`. + alloc = 18, + /// a0=ptr a1=caller pc + free = 19, + /// a0=addr a1=len a2=prot a3=file offset. Payload: path, if file-backed. + map = 20, + /// a0=addr a1=len + unmap = 21, + + // Instrumentation (compiler passes, hooks). + /// a0=callee a1=call site a2=sp + call = 32, + /// a0=callee a1=return value + ret = 33, + /// a0=file string id a1=line a2=column a3=pc + line = 34, + /// a0=pc (a coverage edge) + edge = 35, + /// aux=operand bytes a0=pc a1=lhs a2=rhs + cmp = 36, + /// A named variable comes alive: a0=addr a1=size a2=name string id a3=type string id + variable = 37, + + // Kernel. + /// a0=prev tid a1=next tid a2=cpu + sched = 48, + /// a0=fault address a1=pc. aux: fault flags. + fault = 49, + /// a0=pc a1=counter id a2=value + sample = 50, + /// A kprobe, uprobe, tracepoint or USDT probe: a0=probe string id a1..a5=arguments + probe = 51, + + // Annotations. + /// a0=user value. Payload: text. + mark = 60, + /// Defines a string id for later events: a0=id. Payload: the text. + string = 61, + _, + + /// The bit of a kind in a 64-bit set (kinds are all below 64). + pub fn bit(k: Kind) u64 { + return @as(u64, 1) << @intCast(@intFromEnum(k)); + } +}; + +pub const Alloc = enum(u16) { malloc, calloc, realloc, memalign, mmap }; + +pub const Event = extern struct { + /// CLOCK_MONOTONIC nanoseconds. + ts: u64 = 0, + tid: u32 = 0, + kind: Kind, + /// Small kind-specific value (syscall number, signal, operand size). + aux: u16 = 0, + a: [6]u64 = @splat(0), + + comptime { + std.debug.assert(@sizeOf(Event) == 64); + } +}; + +/// Where events go. A recorder, a ring, a printer. +pub const Sink = struct { + ctx: *anyopaque, + emitFn: *const fn (ctx: *anyopaque, ev: *const Event, payload: []const u8) anyerror!void, + + pub fn emit(s: Sink, ev: Event, payload: []const u8) !void { + return s.emitFn(s.ctx, &ev, payload); + } +}; + +/// x86-64 general registers, in the kernel's `user_regs_struct` order, so +/// PTRACE_GETREGS fills it directly. +pub const Regs = extern struct { + r15: u64 = 0, + r14: u64 = 0, + r13: u64 = 0, + r12: u64 = 0, + rbp: u64 = 0, + rbx: u64 = 0, + r11: u64 = 0, + r10: u64 = 0, + r9: u64 = 0, + r8: u64 = 0, + rax: u64 = 0, + rcx: u64 = 0, + rdx: u64 = 0, + rsi: u64 = 0, + rdi: u64 = 0, + orig_rax: u64 = 0, + rip: u64 = 0, + cs: u64 = 0, + eflags: u64 = 0, + rsp: u64 = 0, + ss: u64 = 0, + fs_base: u64 = 0, + gs_base: u64 = 0, + ds: u64 = 0, + es: u64 = 0, + fs: u64 = 0, + gs: u64 = 0, + + comptime { + std.debug.assert(@sizeOf(Regs) == 27 * 8); + } + + /// The registers a viewer shows, in display order. + pub const names = [_][]const u8{ "rax", "rbx", "rcx", "rdx", "rsi", "rdi", "rbp", "rsp", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", "rip", "eflags" }; + + pub fn get(r: *const Regs, comptime name: []const u8) u64 { + return @field(r, name); + } + + /// By name at runtime: null for a name that is no register. + pub fn named(r: *const Regs, name: []const u8) ?u64 { + inline for (@typeInfo(Regs).@"struct".field_names) |f| { + if (std.mem.eql(u8, f, name)) return @field(r, f); + } + return null; + } +}; + +pub fn now() u64 { + var ts: std.os.linux.timespec = undefined; + _ = std.os.linux.clock_gettime(.MONOTONIC, &ts); + return @as(u64, @intCast(ts.sec)) * std.time.ns_per_s + @as(u64, @intCast(ts.nsec)); +} + +test "kind bits fit a u64 set" { + inline for (@typeInfo(Kind).@"enum".field_values) |v| try std.testing.expect(v < 64); + try std.testing.expectEqual(@as(?u64, 7), (Regs{ .rip = 7 }).named("rip")); +} diff --git a/src/trace/host.zig b/src/trace/host.zig new file mode 100644 index 0000000..f111d55 --- /dev/null +++ b/src/trace/host.zig @@ -0,0 +1,71 @@ +//! The tracer's side of a ring: run a program that carries a ring producer +//! (the preloaded agent, or instrumentation linked into it) and pump what it +//! emits into a sink. No ptrace: the target runs at full speed. +const std = @import("std"); +const linux = std.os.linux; +const event = @import("event.zig"); +const Ring = @import("Ring.zig"); +const client = @import("client.zig"); + +pub const Options = struct { + ring_bytes: usize = 1 << 24, + /// A shared library to LD_PRELOAD into the target (the agent). + preload: ?[]const u8 = null, +}; + +pub const Session = struct { + ring: Ring, + pid: linux.pid_t, + exit_code: ?u8 = null, + + /// Starts `path` with the ring in its environment. `arena` holds the + /// child's environment block. + pub fn spawn(arena: std.mem.Allocator, path: [*:0]const u8, argv: [*:null]const ?[*:0]const u8, env: [:null]const ?[*:0]const u8, options: Options) !Session { + var ring = try Ring.create(options.ring_bytes); + errdefer ring.close(); + var envp: std.ArrayList(?[*:0]const u8) = .empty; + for (env) |v| { + const s = std.mem.span(v.?); + if (std.mem.startsWith(u8, s, client.env_fd ++ "=")) continue; + if (options.preload != null and std.mem.startsWith(u8, s, "LD_PRELOAD=")) continue; + try envp.append(arena, v); + } + try envp.append(arena, try std.fmt.allocPrintSentinel(arena, client.env_fd ++ "={d}", .{ring.fd}, 0)); + if (options.preload) |lib| try envp.append(arena, try std.fmt.allocPrintSentinel(arena, "LD_PRELOAD={s}", .{lib}, 0)); + const block = try envp.toOwnedSliceSentinel(arena, null); + + const rc = linux.fork(); + if (linux.errno(rc) != .SUCCESS) return error.Fork; + if (rc == 0) { + _ = linux.execve(path, argv, block.ptr); + linux.exit_group(127); + } + return .{ .ring = ring, .pid = @intCast(rc) }; + } + + /// Moves what the target emitted into `to`, waiting up to `timeout_ns` + /// when there is nothing. False once the target has exited and the ring + /// is empty: `exit_code` is then set. + pub fn pump(s: *Session, to: event.Sink, timeout_ns: u64) !bool { + if (try s.ring.drain(to) > 0) return true; + if (s.exit_code != null) return false; + var status: u32 = 0; + const rc = linux.waitpid(s.pid, @ptrCast(&status), linux.W.NOHANG); + if (linux.errno(rc) == .SUCCESS and rc != 0) { + s.exit_code = if (linux.W.IFEXITED(status)) linux.W.EXITSTATUS(status) else 128 +| @as(u8, @truncate(@intFromEnum(linux.W.TERMSIG(status)))); + // What it emitted before dying is still in the ring. + return true; + } + s.ring.wait(timeout_ns); + return true; + } + + pub fn close(s: *Session) void { + if (s.exit_code == null) { + _ = linux.kill(s.pid, .KILL); + var status: u32 = 0; + _ = linux.waitpid(s.pid, @ptrCast(&status), 0); + } + s.ring.close(); + } +}; diff --git a/src/trace/ptrace.zig b/src/trace/ptrace.zig new file mode 100644 index 0000000..40a9a7a --- /dev/null +++ b/src/trace/ptrace.zig @@ -0,0 +1,158 @@ +//! The out-of-process backend: a target run under ptrace. Start it, stop it +//! at instructions, syscalls and breakpoints, read its registers and memory. +//! x86-64 Linux. +const std = @import("std"); +const linux = std.os.linux; +const event = @import("event.zig"); +const Regs = event.Regs; +const P = linux.PTRACE; + +pub const Stop = union(enum) { + /// A single step finished, or a breakpoint was hit. + trap, + /// At a syscall's entry or exit (they alternate). + syscall, + /// A signal is about to be delivered; `resume_signal` holds it. + signal: linux.SIG, + exited: u8, + killed: linux.SIG, +}; + +pub const Process = struct { + pid: linux.pid_t, + /// The signal the next resume delivers. + resume_signal: u32 = 0, + in_syscall: bool = false, + + /// Runs `argv` stopped at its first instruction. `path` is the + /// executable; `argv` and `envp` are what it gets. + pub fn spawn(path: [*:0]const u8, argv: [*:null]const ?[*:0]const u8, envp: [*:null]const ?[*:0]const u8) !Process { + const pid = try check(linux.fork()); + if (pid == 0) { + // The child: raw syscalls only until exec. + _ = linux.ptrace(P.TRACEME, 0, 0, 0, 0); + _ = linux.execve(path, argv, envp); + linux.exit_group(127); + } + var p: Process = .{ .pid = @intCast(pid) }; + switch (try p.wait()) { + // The stop exec makes under PTRACE_TRACEME. + .signal, .trap => {}, + else => return error.ExecFailed, + } + p.resume_signal = 0; + _ = try check(linux.ptrace(P.SETOPTIONS, p.pid, 0, P.O.TRACESYSGOOD | P.O.EXITKILL, 0)); + return p; + } + + /// One instruction. + pub fn stepi(p: *Process) !Stop { + return p.run(P.SINGLESTEP); + } + + /// Until the next breakpoint, signal or exit. + pub fn cont(p: *Process) !Stop { + return p.run(P.CONT); + } + + /// Until the next syscall entry or exit. + pub fn syscall(p: *Process) !Stop { + return p.run(P.SYSCALL); + } + + fn run(p: *Process, request: u32) !Stop { + _ = try check(linux.ptrace(request, p.pid, 0, p.resume_signal, 0)); + p.resume_signal = 0; + return p.wait(); + } + + fn wait(p: *Process) !Stop { + var status: u32 = 0; + _ = try check(linux.waitpid(p.pid, @ptrCast(&status), linux.W.UNTRACED)); + if (linux.W.IFEXITED(status)) return .{ .exited = linux.W.EXITSTATUS(status) }; + if (linux.W.IFSIGNALED(status)) return .{ .killed = linux.W.TERMSIG(status) }; + const sig: u32 = (status >> 8) & 0xff; + if (sig == @intFromEnum(linux.SIG.TRAP) | 0x80) { + p.in_syscall = !p.in_syscall; + return .syscall; + } + if (sig == @intFromEnum(linux.SIG.TRAP)) return .trap; + p.resume_signal = sig; + return .{ .signal = @enumFromInt(sig) }; + } + + pub fn regs(p: *const Process) !Regs { + var out: Regs = undefined; + _ = try check(linux.ptrace(P.GETREGS, p.pid, 0, @intFromPtr(&out), 0)); + return out; + } + + pub fn setRegs(p: *const Process, r: *const Regs) !void { + _ = try check(linux.ptrace(P.SETREGS, p.pid, 0, @intFromPtr(r), 0)); + } + + /// The target's memory in one syscall, however long. Returns the bytes + /// read: short where the range leaves mapped memory. + pub fn read(p: *const Process, addr: u64, buf: []u8) usize { + const local = [1]std.posix.iovec{.{ .base = buf.ptr, .len = buf.len }}; + const remote = [1]std.posix.iovec_const{.{ .base = @ptrFromInt(addr), .len = buf.len }}; + const rc = linux.process_vm_readv(p.pid, &local, &remote, 0); + return if (linux.errno(rc) == .SUCCESS) rc else 0; + } + + /// Writes through ptrace, so read-only pages (code) can be patched. + pub fn write(p: *const Process, addr: u64, bytes: []const u8) !void { + var at: usize = 0; + while (at < bytes.len) { + var word: [8]u8 = undefined; + const n = @min(8, bytes.len - at); + if (n < 8 and p.read(addr + at, &word) != 8) return error.BadAddress; + @memcpy(word[0..n], bytes[at..][0..n]); + _ = try check(linux.ptrace(P.POKEDATA, p.pid, addr + at, @bitCast(word), 0)); + at += n; + } + } + + pub fn kill(p: *Process) void { + _ = linux.kill(p.pid, .KILL); + var status: u32 = 0; + _ = linux.waitpid(p.pid, @ptrCast(&status), 0); + } +}; + +fn check(rc: usize) !usize { + return switch (linux.errno(rc)) { + .SUCCESS => rc, + .SRCH => error.NoSuchProcess, + .PERM => error.PermissionDenied, + .FAULT, .IO => error.BadAddress, + else => error.Ptrace, + }; +} + +test "a child is stepped, read, patched and run to its exit" { + const argv = [_:null]?[*:0]const u8{ "/bin/true", null }; + const envp = [_:null]?[*:0]const u8{null}; + var p = try Process.spawn("/bin/true", &argv, &envp); + errdefer p.kill(); + const before = try p.regs(); + try std.testing.expect(before.rip != 0); + try std.testing.expectEqual(Stop.trap, try p.stepi()); + try std.testing.expect((try p.regs()).rip != before.rip); + + // The stack is writable and reads back. + var buf: [16]u8 = undefined; + try p.write(before.rsp - 64, "0123456789abcdef"[0..11]); + try std.testing.expectEqual(@as(usize, 16), p.read(before.rsp - 64, &buf)); + try std.testing.expectEqualStrings("0123456789a", buf[0..11]); + try std.testing.expectEqual(@as(usize, 0), p.read(8, &buf)); + + try std.testing.expectEqual(Stop.syscall, try p.syscall()); + while (true) switch (try p.cont()) { + .exited => |code| { + try std.testing.expectEqual(@as(u8, 0), code); + break; + }, + else => {}, + }; +} diff --git a/src/trace/root.zig b/src/trace/root.zig new file mode 100644 index 0000000..62a9fa7 --- /dev/null +++ b/src/trace/root.zig @@ -0,0 +1,24 @@ +//! ztrace: one event format, many ways to produce it, one recording. +pub const event = @import("event.zig"); +pub const Event = event.Event; +pub const Kind = event.Kind; +pub const Regs = event.Regs; +pub const Sink = event.Sink; +pub const Ring = @import("Ring.zig"); +pub const store = @import("store.zig"); +pub const Recorder = store.Recorder; +pub const Trace = store.Trace; +pub const ptrace = @import("ptrace.zig"); +/// Inside the target: the ring it was handed. +pub const client = @import("client.zig"); +/// Inside the tracer: a target running with a ring. +pub const host = @import("host.zig"); + +test { + _ = event; + _ = Ring; + _ = store; + _ = ptrace; + _ = client; + _ = host; +} diff --git a/src/trace/store.zig b/src/trace/store.zig new file mode 100644 index 0000000..3eca8b7 --- /dev/null +++ b/src/trace/store.zig @@ -0,0 +1,325 @@ +//! A recording on disk, in xitdb: a history of immutable moments. Each +//! moment is the whole state then (registers per thread, the memory seen so +//! far, the strings defined) sharing everything unchanged with the moment +//! before, plus the events that led to it. Time travel is an index. +//! +//! history[i] = map { +//! delta the events of this moment: (u32 payload length, Event, payload)* +//! count events up to and including this moment +//! regs map tid -> Regs bytes +//! mem sorted map, big-endian (addr / 64) -> u64 mask of known bytes, 64 bytes +//! strings map id -> text +//! } +//! +//! The `Recorder` is a `Sink`: it takes events from any backend, folds them +//! into the state, and ends a moment at the kinds in `cut`. +const std = @import("std"); +const xitdb = @import("xitdb"); +const event = @import("event.zig"); +const Event = event.Event; +const Regs = event.Regs; +const Kind = event.Kind; + +const WriteDB = xitdb.Database(.buffered_file, u64); +const ReadDB = xitdb.Database(.file, u64); + +const Key = enum(u64) { delta = 1, count, regs, mem, strings }; +fn key(k: Key) u64 { + return @intFromEnum(k); +} + +pub const chunk_bytes = 64; +const Chunk = extern struct { + /// Bit i set: byte i was recorded. + known: u64 = 0, + bytes: [chunk_bytes]u8 = @splat(0), +}; + +fn chunkKey(index: u64) [8]u8 { + var out: [8]u8 = undefined; + std.mem.writeInt(u64, &out, index, .big); + return out; +} + +pub const Recorder = struct { + gpa: std.mem.Allocator, + io: std.Io, + file: std.Io.File, + /// Its own allocation: the database points at it. + buffer: *std.Io.Writer.Allocating, + db: WriteDB, + /// A moment ends after an event of one of these kinds. + cut: u64 = Kind.step.bit() | Kind.breakpoint.bit() | Kind.syscall_exit.bit() | Kind.signal.bit() | Kind.exit.bit() | Kind.line.bit() | Kind.mark.bit(), + /// ... or when its events pass this many bytes. + max_delta: usize = 1 << 20, + delta: std.ArrayList(u8) = .empty, + count: u64 = 0, + moments: u64 = 0, + regs_dirty: std.AutoArrayHashMapUnmanaged(u32, Regs) = .empty, + /// Every chunk recorded so far, so a partial write needs no read back. + mem: std.AutoHashMapUnmanaged(u64, Chunk) = .empty, + mem_dirty: std.AutoArrayHashMapUnmanaged(u64, void) = .empty, + /// (id, offset and length into `delta`) of this moment's strings. + strings_dirty: std.ArrayList(struct { id: u64, at: usize, len: usize }) = .empty, + + /// A new recording at `path`, replacing any file there. + pub fn create(gpa: std.mem.Allocator, io: std.Io, path: []const u8) !Recorder { + const file = try std.Io.Dir.cwd().createFile(io, path, .{ .read = true, .truncate = true }); + errdefer file.close(io); + const buffer = try gpa.create(std.Io.Writer.Allocating); + errdefer gpa.destroy(buffer); + buffer.* = .init(gpa); + errdefer buffer.deinit(); + // No fsync: a recording is rewritten by running the program again. + const db = try WriteDB.init(io, .{ .file = file, .buffer = buffer, .fsync = false }); + return .{ .gpa = gpa, .io = io, .file = file, .buffer = buffer, .db = db }; + } + + /// Ends the last moment and closes the file. + pub fn close(r: *Recorder) !void { + defer { + r.delta.deinit(r.gpa); + r.regs_dirty.deinit(r.gpa); + r.mem.deinit(r.gpa); + r.mem_dirty.deinit(r.gpa); + r.strings_dirty.deinit(r.gpa); + r.file.close(r.io); + r.buffer.deinit(); + r.gpa.destroy(r.buffer); + } + if (r.delta.items.len > 0) try r.commit(); + try r.db.core.flush(); + } + + pub fn sink(r: *Recorder) event.Sink { + return .{ .ctx = r, .emitFn = sinkEmit }; + } + + fn sinkEmit(ctx: *anyopaque, ev: *const Event, payload: []const u8) anyerror!void { + const r: *Recorder = @ptrCast(@alignCast(ctx)); + return r.emit(ev.*, payload); + } + + pub fn emit(r: *Recorder, ev: Event, payload: []const u8) !void { + var len: [4]u8 = undefined; + std.mem.writeInt(u32, &len, @intCast(payload.len), .little); + try r.delta.appendSlice(r.gpa, &len); + try r.delta.appendSlice(r.gpa, std.mem.asBytes(&ev)); + const payload_at = r.delta.items.len; + try r.delta.appendSlice(r.gpa, payload); + r.count += 1; + + switch (ev.kind) { + .mem_write => try r.write(ev.a[0], payload), + .string => try r.strings_dirty.append(r.gpa, .{ .id = ev.a[0], .at = payload_at, .len = payload.len }), + // Any event may carry the thread's registers. + else => if (payload.len == @sizeOf(Regs)) try r.regs_dirty.put(r.gpa, ev.tid, std.mem.bytesToValue(Regs, payload)), + } + if (r.cut & ev.kind.bit() != 0 or r.delta.items.len >= r.max_delta) try r.commit(); + } + + fn write(r: *Recorder, addr: u64, bytes: []const u8) !void { + var at = addr; + var rest = bytes; + while (rest.len > 0) { + const index = at / chunk_bytes; + const off: usize = @intCast(at % chunk_bytes); + const n = @min(rest.len, chunk_bytes - off); + const gop = try r.mem.getOrPut(r.gpa, index); + if (!gop.found_existing) gop.value_ptr.* = .{}; + @memcpy(gop.value_ptr.bytes[off..][0..n], rest[0..n]); + gop.value_ptr.known |= (if (n == 64) ~@as(u64, 0) else (@as(u64, 1) << @intCast(n)) - 1) << @intCast(off); + try r.mem_dirty.put(r.gpa, index, {}); + at += n; + rest = rest[n..]; + } + } + + /// Ends the moment: one transaction. + pub fn commit(r: *Recorder) !void { + const Ctx = struct { + r: *Recorder, + pub fn run(ctx: @This(), cursor: *WriteDB.Cursor(.read_write)) !void { + const rec = ctx.r; + const moment = try WriteDB.HashMap(.read_write).init(cursor.*); + try moment.put(key(.delta), .{ .bytes = rec.delta.items }); + try moment.put(key(.count), .{ .uint = rec.count }); + if (rec.regs_dirty.count() > 0) { + const regs = try WriteDB.HashMap(.read_write).init(try moment.putCursor(key(.regs))); + for (rec.regs_dirty.keys(), rec.regs_dirty.values()) |tid, *value| try regs.put(tid, .{ .bytes = std.mem.asBytes(value) }); + } + if (rec.mem_dirty.count() > 0) { + const mem = try WriteDB.SortedMap(.read_write).init(try moment.putCursor(key(.mem))); + for (rec.mem_dirty.keys()) |index| try mem.put(&chunkKey(index), .{ .bytes = std.mem.asBytes(rec.mem.getPtr(index).?) }); + } + if (rec.strings_dirty.items.len > 0) { + const strings = try WriteDB.HashMap(.read_write).init(try moment.putCursor(key(.strings))); + for (rec.strings_dirty.items) |s| try strings.put(s.id, .{ .bytes = rec.delta.items[s.at..][0..s.len] }); + } + } + }; + const history = try WriteDB.ArrayList(.read_write).init(r.db.rootCursor()); + try history.appendContext(.{ .slot = try history.getSlot(-1) }, Ctx{ .r = r }); + r.moments += 1; + r.delta.clearRetainingCapacity(); + r.regs_dirty.clearRetainingCapacity(); + r.mem_dirty.clearRetainingCapacity(); + r.strings_dirty.clearRetainingCapacity(); + } +}; + +/// A recording, read. Any moment, in any order. +pub const Trace = struct { + gpa: std.mem.Allocator, + io: std.Io, + file: std.Io.File, + db: *ReadDB, + len: u64, + + pub fn open(gpa: std.mem.Allocator, io: std.Io, path: []const u8) !Trace { + const file = try std.Io.Dir.cwd().openFile(io, path, .{}); + errdefer file.close(io); + const db = try gpa.create(ReadDB); + errdefer gpa.destroy(db); + db.* = try ReadDB.init(io, .{ .file = file, .fsync = false }); + const history = try ReadDB.ArrayList(.read_only).init(db.rootCursor().readOnly()); + return .{ .gpa = gpa, .io = io, .file = file, .db = db, .len = try history.count() }; + } + + pub fn close(t: *Trace) void { + t.file.close(t.io); + t.gpa.destroy(t.db); + } + + pub fn moment(t: *const Trace, index: u64) !Moment { + const history = try ReadDB.ArrayList(.read_only).init(t.db.rootCursor().readOnly()); + const cursor = (try history.getCursor(@intCast(index))) orelse return error.NoSuchMoment; + return .{ .index = index, .map = try ReadDB.HashMap(.read_only).init(cursor) }; + } +}; + +pub const Moment = struct { + index: u64, + map: ReadDB.HashMap(.read_only), + + /// Events up to and including this moment. + pub fn count(m: Moment) !u64 { + return (try m.map.getCursor(key(.count))).?.readUint(); + } + + pub fn regs(m: Moment, tid: u32) !?Regs { + const all = try ReadDB.HashMap(.read_only).init((try m.map.getCursor(key(.regs))) orelse return null); + const cursor = (try all.getCursor(tid)) orelse return null; + var out: Regs = undefined; + _ = try cursor.readBytes(std.mem.asBytes(&out)); + return out; + } + + /// The memory at `addr` as of this moment. Bytes never recorded read as + /// zero, and false in `known` when it is given. + pub fn read(m: Moment, addr: u64, buf: []u8, known: ?[]bool) !void { + @memset(buf, 0); + if (known) |k| @memset(k, false); + const mem = try ReadDB.SortedMap(.read_only).init((try m.map.getCursor(key(.mem))) orelse return); + var done: usize = 0; + while (done < buf.len) { + const at = addr + done; + const off: usize = @intCast(at % chunk_bytes); + const n = @min(buf.len - done, chunk_bytes - off); + if (try mem.getCursor(&chunkKey(at / chunk_bytes))) |cursor| { + var chunk: Chunk = undefined; + _ = try cursor.readBytes(std.mem.asBytes(&chunk)); + @memcpy(buf[done..][0..n], chunk.bytes[off..][0..n]); + if (known) |k| for (k[done..][0..n], off..) |*bit, i| { + bit.* = chunk.known >> @intCast(i) & 1 != 0; + }; + } + done += n; + } + } + + pub fn string(m: Moment, id: u64, buf: []u8) !?[]const u8 { + const all = try ReadDB.HashMap(.read_only).init((try m.map.getCursor(key(.strings))) orelse return null); + const cursor = (try all.getCursor(id)) orelse return null; + return try cursor.readBytes(buf); + } + + /// The events that led from the moment before to this one. Free with + /// `Events.deinit`. + pub fn events(m: Moment, gpa: std.mem.Allocator) !Events { + const cursor = (try m.map.getCursor(key(.delta))).?; + return .{ .bytes = try cursor.readBytesAlloc(gpa, null) }; + } +}; + +pub const Events = struct { + bytes: []const u8, + at: usize = 0, + + pub const Item = struct { ev: Event, payload: []const u8 }; + + pub fn deinit(e: *Events, gpa: std.mem.Allocator) void { + gpa.free(e.bytes); + } + + pub fn next(e: *Events) ?Item { + if (e.at >= e.bytes.len) return null; + const len = std.mem.readInt(u32, e.bytes[e.at..][0..4], .little); + const ev = std.mem.bytesToValue(Event, e.bytes[e.at + 4 ..][0..@sizeOf(Event)]); + const start = e.at + 4 + @sizeOf(Event); + e.at = start + len; + return .{ .ev = ev, .payload = e.bytes[start..][0..len] }; + } +}; + +test "a recording is read back moment by moment" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var path_buf: [std.Io.Dir.max_path_bytes]u8 = undefined; + const dir = path_buf[0..try tmp.dir.realPath(io, &path_buf)]; + const path = try std.fs.path.join(gpa, &.{ dir, "t.ztrace" }); + defer gpa.free(path); + + var rec = try Recorder.create(gpa, io, path); + try rec.emit(.{ .kind = .string, .a = .{ 9, 0, 0, 0, 0, 0 } }, "fib.c"); + for (0..3) |i| { + // A write that straddles two chunks, then the step that ends the moment. + const bytes: [4]u8 = @splat(@intCast(i + 1)); + try rec.emit(.{ .kind = .mem_write, .a = .{ 62 + i, 4, 0, 0, 0, 0 } }, &bytes); + const regs: Regs = .{ .rip = 0x1000 + i, .rax = i }; + try rec.emit(.{ .kind = .step, .tid = 7, .a = .{ regs.rip, 0, 0, 0, 0, 0 } }, std.mem.asBytes(®s)); + } + try rec.close(); + + var trace = try Trace.open(gpa, io, path); + defer trace.close(); + try std.testing.expectEqual(@as(u64, 3), trace.len); + + // The first moment still shows the first write only: nothing later leaked back. + const first = try trace.moment(0); + var buf: [8]u8 = undefined; + var known: [8]bool = undefined; + try first.read(60, &buf, &known); + try std.testing.expectEqualSlices(u8, &.{ 0, 0, 1, 1, 1, 1, 0, 0 }, &buf); + try std.testing.expectEqualSlices(bool, &.{ false, false, true, true, true, true, false, false }, &known); + try std.testing.expectEqual(@as(u64, 0x1000), (try first.regs(7)).?.rip); + try std.testing.expectEqual(@as(u64, 3), try first.count()); + + const last = try trace.moment(2); + try last.read(60, &buf, null); + try std.testing.expectEqualSlices(u8, &.{ 0, 0, 1, 2, 3, 3, 3, 3 }, &buf); + try std.testing.expectEqual(@as(u64, 2), (try last.regs(7)).?.rax); + try std.testing.expect((try last.regs(8)) == null); + var name: [16]u8 = undefined; + try std.testing.expectEqualStrings("fib.c", (try last.string(9, &name)).?); + + var events = try last.events(gpa); + defer events.deinit(gpa); + try std.testing.expectEqual(Kind.mem_write, events.next().?.ev.kind); + const step = events.next().?; + try std.testing.expectEqual(@as(u64, 0x1002), step.ev.a[0]); + try std.testing.expectEqual(@sizeOf(Regs), step.payload.len); + try std.testing.expect(events.next() == null); +} diff --git a/targets/emit.zig b/targets/emit.zig new file mode 100644 index 0000000..e1b0b72 --- /dev/null +++ b/targets/emit.zig @@ -0,0 +1,14 @@ +//! A target that carries its own producer: emits N marks through the ring +//! (argv[1], default 1000) and one write, then exits 7. The host test and +//! the ring's throughput number run on it. +const std = @import("std"); +const zt = @import("ztrace"); + +pub fn main(init: std.process.Init.Minimal) u8 { + var args = init.args.iterate(); + _ = args.skip(); + const n = if (args.next()) |arg| std.fmt.parseInt(u64, arg, 10) catch 1000 else 1000; + zt.client.emit(.mem_write, 0, .{ 0x1000, 5, 0, 0, 0, 0 }, "hello"); + for (0..n) |i| zt.client.emit(.mark, 0, .{ i, 0, 0, 0, 0, 0 }, ""); + return 7; +} diff --git a/targets/fib.c b/targets/fib.c new file mode 100644 index 0000000..5be9998 --- /dev/null +++ b/targets/fib.c @@ -0,0 +1,12 @@ +#include +#include + +static unsigned long fib(unsigned n) { + return n < 2 ? n : fib(n - 1) + fib(n - 2); +} + +int main(int argc, char **argv) { + unsigned n = argc > 1 ? (unsigned)atoi(argv[1]) : 10; + printf("fib(%u) = %lu\n", n, fib(n)); + return 0; +} -- cgit v1.3