summaryrefslogtreecommitdiff
path: root/src/trace/store.zig
blob: 3eca8b7a70c57a3a175343921d2b8a908aa3cc92 (plain) (blame)
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
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
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(&regs));
    }
    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);
}