summaryrefslogtreecommitdiff
path: root/src/host/memory.zig
blob: 2749ea128c2bca7285ce8e9b4574537346bb0d90 (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
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
//! Sketch memory by lifetime.
//!
//! `State`: process memory in the layout the sketch declares; a reload
//! with a changed layout carries the old values over field by field. It
//! outlives the process in the sessions database (Sessions.zig), whose
//! stretches keep its layout in the header format below.
//!
//! `OldState`: a state file from before the database held the present,
//! read once to import it.
//!
//! `Session`: this process's memory, kept across reloads.
const std = @import("std");
const posix = std.posix;
const linux = std.os.linux;
const abi = @import("abi");
const field_value = @import("fields.zig");

pub const page = std.heap.page_size_min;
pub const header_len = 64 * 1024;
/// A layout header, and an old file's one slot, the live state.
pub const file_magic = "SKETCH03".*;
/// Before sessions: slot 0 live and 1..7 snapshots (`old_slot_count`), which
/// the host imports as marks and then drops (`dropSnapshots`).
pub const file_magic_v2 = "SKETCH02".*;
pub const old_slot_count = 8;
/// What hosts before element leaves wrote: arrays are whole leaves
/// (`StoredFieldV1`), and eight slots. Read, and rewritten as
/// `file_magic_v2` on adopt.
pub const file_magic_v1 = "SKETCH01".*;

pub const Header = extern struct {
    magic: [8]u8 = file_magic,
    size: u64,
    alignment: u64,
    hash: u64,
    /// The slot's size, page aligned (and the distance between an old
    /// file's slots).
    stride: u64,
    /// Bit `i`: slot `i` holds state.
    used: u32,
    field_count: u32,
    strings_len: u32,
    reserved: u32 = 0,
};

/// A leaf as stored in the file: strings are offsets into the string table,
/// and so is `dims`, `rank` little-endian (count, stride) u32 pairs.
pub const StoredField = extern struct {
    offset: u32,
    size: u32,
    hash: u64,
    path: u32,
    path_len: u16,
    tags_len: u16,
    tags: u32,
    kind: abi.Field.Kind,
    rank: u8 = 0,
    reserved: [2]u8 = @splat(0),
    dims: u32 = 0,
    reserved2: u32 = 0,
};

/// A leaf as `file_magic_v1` files store it: no element leaves.
pub const StoredFieldV1 = extern struct {
    offset: u32,
    size: u32,
    hash: u64,
    path: u32,
    path_len: u16,
    tags_len: u16,
    tags: u32,
    kind: abi.Field.Kind,
    reserved: [3]u8 = @splat(0),
};

const Dim = abi.Field.Dim;

/// A layout the host owns: copied out of a sketch, or read from a file.
pub const Layout = struct {
    size: usize = 0,
    alignment: usize = 1,
    hash: u64 = 0,
    fields: []const Leaf = &.{},

    /// A leaf with `dims` stands for all its elements (`list[].x`), at
    /// `offset` plus index times stride per dimension. `find` resolves one.
    pub const Leaf = struct {
        path: []const u8,
        offset: u32,
        size: u32,
        kind: abi.Field.Kind,
        hash: u64,
        tags: []const u8,
        dims: []const Dim = &.{},

        pub fn bytes(leaf: Leaf, memory: []const u8) []const u8 {
            return memory[leaf.offset..][0..leaf.size];
        }
        /// The leaf at `offset` (from `elements`), as a leaf of its own.
        pub fn at(leaf: Leaf, offset: usize) Leaf {
            var one = leaf;
            one.offset = @intCast(offset);
            one.dims = &.{};
            return one;
        }
        /// A whole array, kept for copying in one piece; its elements are
        /// leaves of their own.
        pub fn whole(leaf: Leaf) bool {
            return leaf.kind == .array;
        }
        /// Offsets of every element, first index slowest.
        pub fn elements(leaf: Leaf) Elements {
            return .init(leaf.offset, leaf.dims, leaf.dims, null);
        }
        /// Writes the path naming the element at `offset`, indices filled in.
        pub fn name(leaf: Leaf, offset: usize, w: *std.Io.Writer) std.Io.Writer.Error!void {
            var rest = offset - leaf.offset;
            var parts = std.mem.splitSequence(u8, leaf.path, "[]");
            try w.writeAll(parts.first());
            for (leaf.dims) |d| {
                try w.print("[{d}]", .{rest / d.stride});
                rest %= d.stride;
                try w.writeAll(parts.next() orelse "");
            }
        }
    };

    pub fn copy(arena: std.mem.Allocator, l: abi.Layout) !Layout {
        const fields = try arena.alloc(Leaf, l.fields.len);
        for (fields, l.fields) |*to, from| to.* = .{
            .path = try arena.dupe(u8, std.mem.span(from.path)),
            .offset = from.offset,
            .size = from.size,
            .kind = from.kind,
            .hash = from.hash,
            .tags = try arena.dupe(u8, std.mem.span(from.tags)),
            .dims = try arena.dupe(Dim, from.dims[0..from.rank]),
        };
        return .{ .size = l.size, .alignment = l.alignment, .hash = l.hash, .fields = fields };
    }

    /// The leaf `path` names, with indices for every array it is in
    /// (`list[3].pos[0]`), as a leaf of its own; null when there is none
    /// or an index is out of range.
    pub fn find(self: Layout, path: []const u8) ?Leaf {
        for (self.fields) |leaf| {
            const delta = abi.layout.match(leaf.path, leaf.dims, path) orelse continue;
            return leaf.at(leaf.offset + delta);
        }
        return null;
    }

    /// The leaf whose pattern is exactly `pattern` (`list[].x`).
    pub fn pattern(self: Layout, path: []const u8) ?Leaf {
        for (self.fields) |leaf| if (std.mem.eql(u8, leaf.path, path)) return leaf;
        return null;
    }
};

/// Walks element offsets of one leaf, or of the elements two layouts of a
/// leaf share (`limit`, the smaller count per dimension), with offsets in
/// both.
pub const Elements = struct {
    index: [abi.layout.max_rank]u32 = @splat(0),
    limit: [abi.layout.max_rank]u32 = @splat(0),
    rank: usize,
    a: Side,
    b: Side,
    done: bool,

    const Side = struct { base: usize, dims: []const Dim };

    pub fn init(base: usize, dims: []const Dim, other_dims: []const Dim, other_base: ?usize) Elements {
        var e: Elements = .{ .rank = dims.len, .a = .{ .base = base, .dims = dims }, .b = .{ .base = other_base orelse base, .dims = other_dims }, .done = false };
        for (dims, other_dims, 0..) |x, y, i| {
            e.limit[i] = @min(x.count, y.count);
            if (e.limit[i] == 0) e.done = true;
        }
        return e;
    }

    fn offset(e: *const Elements, side: Side) usize {
        var at = side.base;
        for (side.dims, 0..) |d, i| at += @as(usize, e.index[i]) * d.stride;
        return at;
    }

    pub fn next(e: *Elements) ?usize {
        const pair = e.nextPair() orelse return null;
        return pair[0];
    }

    pub fn nextPair(e: *Elements) ?[2]usize {
        if (e.done) return null;
        const pair: [2]usize = .{ e.offset(e.a), e.offset(e.b) };
        var i = e.rank;
        while (true) {
            if (i == 0) {
                e.done = true;
                break;
            }
            i -= 1;
            e.index[i] += 1;
            if (e.index[i] < e.limit[i]) break;
            e.index[i] = 0;
        }
        return pair;
    }
};

pub const Migration = struct { kept: usize = 0, reset: usize = 0 };

/// Copies every leaf of `from` whose path and type are unchanged into `to`,
/// which already holds the new defaults. Arrays copy element by element:
/// the elements both layouts have (the common prefix of each dimension; a
/// shrink drops the rest, a growth keeps the new defaults), field by field
/// inside each, enums by tag name. An array whose type is unchanged copies
/// in one piece. Counts are of leaves, not elements.
pub fn migrate(from: Layout, old: []const u8, to: Layout, new: []u8) Migration {
    var result: Migration = .{};
    // The array copied whole most recently: its elements' leaves follow it.
    var copied: ?[]const u8 = null;
    for (to.fields) |leaf| {
        if (copied) |prefix| {
            if (leaf.path.len > prefix.len and std.mem.startsWith(u8, leaf.path, prefix) and leaf.path[prefix.len] == '[') continue;
            copied = null;
        }
        const before = from.pattern(leaf.path) orelse {
            if (!leaf.whole()) result.reset += 1;
            continue;
        };
        if (before.dims.len != leaf.dims.len) {
            if (!leaf.whole()) result.reset += 1;
            continue;
        }
        if (before.hash == leaf.hash and before.size == leaf.size) {
            var it: Elements = .init(leaf.offset, leaf.dims, before.dims, before.offset);
            while (it.nextPair()) |pair| @memcpy(new[pair[0]..][0..leaf.size], old[pair[1]..][0..leaf.size]);
            if (leaf.whole()) copied = leaf.path;
            result.kept += 1;
        } else if (before.kind == .@"enum" and leaf.kind == .@"enum") {
            var it: Elements = .init(leaf.offset, leaf.dims, before.dims, before.offset);
            var any = false;
            var seen: usize = 0;
            while (it.nextPair()) |pair| : (seen += 1) {
                if (remapEnum(before.at(pair[1]), old, leaf.at(pair[0]), new)) any = true;
            }
            if (any or seen == 0) result.kept += 1 else result.reset += 1;
        } else if (!leaf.whole()) result.reset += 1;
    }
    return result;
}

pub const Diff = struct {
    /// Leaf values (elements counted one by one) that differ.
    count: usize = 0,
    first: ?Place = null,
    last: ?Place = null,

    pub const Place = struct { leaf: Layout.Leaf, offset: usize };
};

/// Compares two copies of state leaf by leaf, so padding (a Debug
/// `@Vector`'s spare lane, the gaps between fields) never differs.
pub fn compare(layout: Layout, a: []const u8, b: []const u8) Diff {
    return compareKept(layout, layout, a, b);
}

/// `compare` over the leaves `migrate` from `from` keeps (`keeps`).
pub fn compareKept(from: Layout, layout: Layout, a: []const u8, b: []const u8) Diff {
    var diff: Diff = .{};
    for (layout.fields) |leaf| {
        if (leaf.whole() or (from.hash != layout.hash and !keeps(from, leaf))) continue;
        var it = leaf.elements();
        while (it.next()) |offset| {
            if (std.mem.eql(u8, a[offset..][0..leaf.size], b[offset..][0..leaf.size])) continue;
            diff.count += 1;
            if (diff.first == null) diff.first = .{ .leaf = leaf, .offset = offset };
            diff.last = .{ .leaf = leaf, .offset = offset };
        }
    }
    return diff;
}

/// Carries an enum over by tag name; false when its name no longer exists.
fn remapEnum(from: Layout.Leaf, old: []const u8, to: Layout.Leaf, new: []u8) bool {
    const name = field_value.tagName(from.tags, field_value.readInt(i64, from.bytes(old))) orelse return false;
    const value = field_value.tagValue(to.tags, name) orelse return false;
    field_value.writeInt(new[to.offset..][0..to.size], value);
    return true;
}

/// Live State: page aligned, in the running sketch's layout; `header` is
/// that layout as `layoutOf` reads it back, for the sessions' stretches.
pub const State = struct {
    bytes: []align(page) u8 = &.{},
    layout: Layout = .{},
    header: []const u8 = "",
    /// Owns `layout` and `header`.
    arena: std.heap.ArenaAllocator,

    pub fn init(gpa: std.mem.Allocator) State {
        return .{ .arena = .init(gpa) };
    }

    pub fn deinit(self: *State, gpa: std.mem.Allocator) void {
        gpa.free(self.bytes);
        self.arena.deinit();
    }

    pub fn live(self: *State) []align(page) u8 {
        return self.bytes[0..self.layout.size];
    }

    /// Makes State hold `new`'s layout: a new allocation of its defaults
    /// (`defaults`), then every leaf `migrate` keeps of the old State. Null
    /// when the layout is unchanged, or there was none.
    pub fn adopt(self: *State, gpa: std.mem.Allocator, new: abi.Layout, defaults: *const fn (abi.Memory, [*]u8) callconv(.c) void) !?Migration {
        const first = self.bytes.len == 0;
        if (!first and self.layout.hash == new.hash and self.layout.size == new.size) return null;
        var arena: std.heap.ArenaAllocator = .init(gpa);
        errdefer arena.deinit();
        const layout = try Layout.copy(arena.allocator(), new);
        const region = try arena.allocator().alignedAlloc(u8, .of(Header), header_len);
        @memset(region, 0);
        const h: *Header = @ptrCast(region.ptr);
        h.* = .{ .size = new.size, .alignment = new.alignment, .hash = new.hash, .stride = std.mem.alignForward(usize, @max(new.size, 1), page), .used = 1, .field_count = 0, .strings_len = 0 };
        try writeLayout(region, layout);
        const bytes = try gpa.alignedAlloc(u8, .fromByteUnits(page), @max(new.size, 1));
        @memset(bytes, 0);
        defaults(.state, bytes.ptr);
        const m = if (first) null else migrate(self.layout, self.live(), layout, bytes);
        self.deinit(gpa);
        self.* = .{ .bytes = bytes, .layout = layout, .header = region[0 .. @sizeOf(Header) + @as(usize, h.field_count) * @sizeOf(StoredField) + h.strings_len], .arena = arena };
        return m;
    }
};

/// A state file from before the sessions database held the present: a
/// layout header, then one slot (`file_magic`), or eight (`file_magic_v2`,
/// `file_magic_v1`), the first live State and the others snapshots. Mapped
/// read-only: imported once, never changed.
pub const OldState = struct {
    map: []align(page) const u8,
    slots: usize,

    /// error.FileNotFound when `path` is missing or empty; a file that is
    /// no state file this host reads is refused.
    pub fn open(path: []const u8) !OldState {
        const map = mapReadOnly(path);
        if (map.len == 0) return error.FileNotFound;
        errdefer posix.munmap(map);
        if (map.len < header_len) return error.NotAStateFile;
        const h: *const Header = @ptrCast(map.ptr);
        const slots: usize = if (std.mem.eql(u8, &h.magic, &file_magic)) 1 else if (std.mem.eql(u8, &h.magic, &file_magic_v2) or std.mem.eql(u8, &h.magic, &file_magic_v1)) old_slot_count else return error.NotAStateFile;
        if (map.len < header_len + slots * h.stride or h.size > h.stride) return error.CorruptStateFile;
        return .{ .map = map, .slots = slots };
    }

    pub fn close(self: OldState) void {
        posix.munmap(self.map);
    }

    /// The header and layout, as `restore` and `layoutOf` take them.
    pub fn layoutBytes(self: OldState) []const u8 {
        return self.map[0..header_len];
    }

    /// Slot `i`'s State, null when the slot is unused.
    pub fn slot(self: OldState, i: usize) ?[]const u8 {
        const h: *const Header = @ptrCast(self.map.ptr);
        if (h.used & (@as(u32, 1) << @intCast(i)) == 0) return null;
        return self.map[header_len + i * h.stride ..][0..h.size];
    }
};

/// Fills `live` (laid out as `to`) from `image`, state kept in another
/// layout, described by `layout_bytes` (a header as `State.header` holds
/// it): `defaults`, then every leaf `migrate` keeps. Returns the
/// image's layout, `arena`'s.
pub fn restore(arena: std.mem.Allocator, layout_bytes: []const u8, image: []const u8, to: Layout, live: []u8, defaults: *const fn (abi.Memory, [*]u8) callconv(.c) void) !Layout {
    const from = try layoutOf(arena, layout_bytes);
    if (image.len != from.size) return error.CorruptKeyframe;
    @memset(live, 0);
    defaults(.state, live.ptr);
    _ = migrate(from, image, to, live);
    return from;
}

/// The layout in a header as `State.header` holds it, `arena`'s.
pub fn layoutOf(arena: std.mem.Allocator, layout_bytes: []const u8) !Layout {
    if (layout_bytes.len < @sizeOf(Header) or layout_bytes.len > header_len) return error.CorruptKeyframe;
    const region = try arena.alignedAlloc(u8, .of(Header), header_len);
    @memset(region, 0);
    @memcpy(region[0..layout_bytes.len], layout_bytes);
    return try readLayout(arena, region) orelse .{};
}

/// Whether `migrate` from `from` keeps `leaf`'s value: compared on these
/// only, state restored across a layout change differs nowhere it was reset.
pub fn keeps(from: Layout, leaf: Layout.Leaf) bool {
    const before = from.pattern(leaf.path) orelse return false;
    if (before.dims.len != leaf.dims.len) return false;
    return (before.hash == leaf.hash and before.size == leaf.size) or (before.kind == .@"enum" and leaf.kind == .@"enum");
}

/// Writes `layout`'s leaves after the `Header` at the start of `region`,
/// in the current format (`StoredField`); the caller sets the magic.
fn writeLayout(region: []u8, layout: Layout) !void {
    const h: *Header = @ptrCast(@alignCast(region.ptr));
    const fields: [*]StoredField = @ptrCast(@alignCast(region.ptr + @sizeOf(Header)));
    const strings_start = @sizeOf(Header) + layout.fields.len * @sizeOf(StoredField);
    var strings: usize = 0;
    for (layout.fields, 0..) |leaf, i| {
        const dims_len = leaf.dims.len * @sizeOf(Dim);
        if (strings_start + strings + leaf.path.len + leaf.tags.len + dims_len > region.len) return error.LayoutTooLarge;
        const base = strings_start + strings;
        @memcpy(region[base..][0..leaf.path.len], leaf.path);
        @memcpy(region[base + leaf.path.len ..][0..leaf.tags.len], leaf.tags);
        for (leaf.dims, 0..) |d, j| {
            const at = base + leaf.path.len + leaf.tags.len + j * @sizeOf(Dim);
            std.mem.writeInt(u32, region[at..][0..4], d.count, .little);
            std.mem.writeInt(u32, region[at + 4 ..][0..4], d.stride, .little);
        }
        fields[i] = .{
            .offset = leaf.offset,
            .size = leaf.size,
            .hash = leaf.hash,
            .kind = leaf.kind,
            .path = @intCast(strings),
            .path_len = @intCast(leaf.path.len),
            .tags = @intCast(strings + leaf.path.len),
            .tags_len = @intCast(leaf.tags.len),
            .rank = @intCast(leaf.dims.len),
            .dims = @intCast(strings + leaf.path.len + leaf.tags.len),
        };
        strings += leaf.path.len + leaf.tags.len + dims_len;
    }
    h.field_count = @intCast(layout.fields.len);
    h.strings_len = @intCast(strings);
}

/// The layout stored in a state file's header, or null if it has none.
/// Reads both formats, by magic: a v1 header (`file_magic_v1`) has no
/// element leaves, so its arrays are whole leaves only, which migrate while
/// their type is unchanged.
pub fn readLayout(arena: std.mem.Allocator, map: []const u8) !?Layout {
    const h: *const Header = @ptrCast(@alignCast(map.ptr));
    if (h.hash == 0 and h.field_count == 0) return null;
    const v1 = std.mem.eql(u8, &h.magic, &file_magic_v1);
    const stride: usize = if (v1) @sizeOf(StoredFieldV1) else @sizeOf(StoredField);
    const strings_start = @sizeOf(Header) + @as(usize, h.field_count) * stride;
    if (strings_start + h.strings_len > header_len or map.len < header_len) return error.CorruptHeader;
    const strings = map[strings_start..][0..h.strings_len];
    const leaves = try arena.alloc(Layout.Leaf, h.field_count);
    for (leaves, 0..) |*leaf, i| {
        const at = @sizeOf(Header) + i * stride;
        const f: StoredField = if (v1) blk: {
            const old: *const StoredFieldV1 = @ptrCast(@alignCast(map[at..].ptr));
            break :blk .{ .offset = old.offset, .size = old.size, .hash = old.hash, .path = old.path, .path_len = old.path_len, .tags = old.tags, .tags_len = old.tags_len, .kind = old.kind };
        } else @as(*const StoredField, @ptrCast(@alignCast(map[at..].ptr))).*;
        const dims_len = @as(usize, f.rank) * @sizeOf(Dim);
        if (f.path + f.path_len > strings.len or f.tags + f.tags_len > strings.len or f.dims + dims_len > strings.len) return error.CorruptHeader;
        if (f.rank > abi.layout.max_rank) return error.CorruptHeader;
        const dims = try arena.alloc(Dim, f.rank);
        for (dims, 0..) |*d, j| {
            const raw = strings[f.dims + j * @sizeOf(Dim) ..];
            d.* = .{ .count = std.mem.readInt(u32, raw[0..4], .little), .stride = std.mem.readInt(u32, raw[4..8], .little) };
        }
        // Copied: the mapping moves when the file is resized.
        leaf.* = .{
            .path = try arena.dupe(u8, strings[f.path..][0..f.path_len]),
            .offset = f.offset,
            .size = f.size,
            .kind = f.kind,
            .hash = f.hash,
            .tags = try arena.dupe(u8, strings[f.tags..][0..f.tags_len]),
            .dims = dims,
        };
        // Every element must lie inside the state.
        var end: usize = @as(usize, leaf.offset) + leaf.size;
        for (dims) |d| end += @as(usize, d.stride) * (d.count -| 1);
        if (end > h.size) return error.CorruptHeader;
    }
    return .{ .size = h.size, .alignment = h.alignment, .hash = h.hash, .fields = leaves };
}

pub fn fileSize(fd: posix.fd_t) !u64 {
    var stat: linux.Statx = undefined;
    switch (linux.errno(linux.statx(fd, "", linux.AT.EMPTY_PATH, .{ .SIZE = true }, &stat))) {
        .SUCCESS => {},
        else => |err| return posix.unexpectedErrno(err),
    }
    return stat.size;
}

/// Maps a whole file read-only; empty when missing or empty.
pub fn mapReadOnly(path: []const u8) []align(page) const u8 {
    const fd = posix.openat(posix.AT.FDCWD, path, .{ .ACCMODE = .RDONLY }, 0) catch return &.{};
    defer _ = posix.system.close(fd);
    const len = fileSize(fd) catch return &.{};
    if (len == 0) return &.{};
    return posix.mmap(null, @intCast(len), .{ .READ = true }, .{ .TYPE = .SHARED }, fd, 0) catch &.{};
}

/// Session memory: survives reloads while its layout hash is unchanged.
/// Everything allocated from `heap` is released with it.
pub const Session = struct {
    bytes: []align(16) u8 = &.{},
    hash: u64 = 0,
    heap: Heap,

    pub fn init(gpa: std.mem.Allocator) Session {
        return .{ .heap = .{ .gpa = gpa } };
    }

    pub fn deinit(self: *Session, gpa: std.mem.Allocator) void {
        gpa.free(self.bytes);
        self.heap.deinit();
    }

    /// True when the session was reset to `layout`'s defaults.
    pub fn adopt(self: *Session, gpa: std.mem.Allocator, layout: abi.Layout, defaults: *const fn (abi.Memory, [*]u8) callconv(.c) void) !bool {
        if (self.hash == layout.hash and self.bytes.len == @max(layout.size, 1)) return false;
        if (layout.alignment > 16) return error.SessionOveraligned;
        gpa.free(self.bytes);
        self.bytes = &.{};
        self.heap.reset();
        self.bytes = try gpa.alignedAlloc(u8, .@"16", @max(layout.size, 1));
        @memset(self.bytes, 0);
        defaults(.session, self.bytes.ptr);
        self.hash = layout.hash;
        return true;
    }
};

/// The session's allocator: general purpose, so memory frees one allocation
/// at a time (a growing list does not leave its old copies behind), and it
/// remembers what is still live, so a session reset releases all of it.
pub const Heap = struct {
    gpa: std.mem.Allocator,
    live: std.AutoHashMapUnmanaged(usize, Block) = .empty,

    const Block = struct { len: usize, alignment: std.mem.Alignment };

    pub fn allocator(self: *Heap) std.mem.Allocator {
        return .{ .ptr = self, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } };
    }

    /// Releases every live allocation.
    pub fn reset(self: *Heap) void {
        var it = self.live.iterator();
        while (it.next()) |entry| {
            const memory: [*]u8 = @ptrFromInt(entry.key_ptr.*);
            self.gpa.rawFree(memory[0..entry.value_ptr.len], entry.value_ptr.alignment, @returnAddress());
        }
        self.live.clearRetainingCapacity();
    }

    pub fn deinit(self: *Heap) void {
        self.reset();
        self.live.deinit(self.gpa);
    }

    fn alloc(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret: usize) ?[*]u8 {
        const self: *Heap = @ptrCast(@alignCast(ctx));
        self.live.ensureUnusedCapacity(self.gpa, 1) catch return null;
        const memory = self.gpa.rawAlloc(len, alignment, ret) orelse return null;
        self.live.putAssumeCapacity(@intFromPtr(memory), .{ .len = len, .alignment = alignment });
        return memory;
    }

    fn resize(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret: usize) bool {
        const self: *Heap = @ptrCast(@alignCast(ctx));
        if (!self.gpa.rawResize(memory, alignment, new_len, ret)) return false;
        self.live.getPtr(@intFromPtr(memory.ptr)).?.len = new_len;
        return true;
    }

    fn remap(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret: usize) ?[*]u8 {
        const self: *Heap = @ptrCast(@alignCast(ctx));
        self.live.ensureUnusedCapacity(self.gpa, 1) catch return null;
        const moved = self.gpa.rawRemap(memory, alignment, new_len, ret) orelse return null;
        _ = self.live.remove(@intFromPtr(memory.ptr));
        self.live.putAssumeCapacity(@intFromPtr(moved), .{ .len = new_len, .alignment = alignment });
        return moved;
    }

    fn free(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret: usize) void {
        const self: *Heap = @ptrCast(@alignCast(ctx));
        _ = self.live.remove(@intFromPtr(memory.ptr));
        self.gpa.rawFree(memory, alignment, ret);
    }
};

test "the session heap frees one allocation at a time, and the rest on reset" {
    var heap: Heap = .{ .gpa = std.testing.allocator };
    defer heap.deinit();
    const a = heap.allocator();
    var list: std.ArrayList(u32) = .empty;
    for (0..1000) |i| try list.append(a, @intCast(i));
    try std.testing.expectEqual(@as(usize, 1), heap.live.count());
    const loose = try a.alloc(u8, 100);
    a.free(loose);
    try std.testing.expectEqual(@as(usize, 1), heap.live.count());
    _ = try a.create(u64);
    heap.reset();
    try std.testing.expectEqual(@as(usize, 0), heap.live.count());
    // std.testing.allocator fails the test if anything leaked.
}

test "enums migrate by tag name" {
    const V1 = struct { mood: enum(u8) { calm, lost, angry } = .calm, gone: enum(u8) { a, b } = .b };
    const V2 = struct { mood: enum(u16) { angry = 7, calm, sleepy } = .sleepy, gone: enum(u8) { c } = .c };
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();
    const l1 = try Layout.copy(arena.allocator(), abi.layout.of(V1, .state));
    const l2 = try Layout.copy(arena.allocator(), abi.layout.of(V2, .state));
    for ([_]struct { @FieldType(V1, "mood"), @FieldType(V2, "mood") }{ .{ .calm, .calm }, .{ .angry, .angry }, .{ .lost, .sleepy } }) |case| {
        const old: V1 = .{ .mood = case[0] };
        var new: V2 = .{};
        _ = migrate(l1, std.mem.asBytes(&old), l2, std.mem.asBytes(&new));
        try std.testing.expectEqual(case[1], new.mood);
        try std.testing.expectEqual(.c, new.gone);
    }
}

test "migration keeps unchanged fields and defaults the rest" {
    const V1 = extern struct { a: u32 = 1, b: f32 = 2, gone: u8 = 3 };
    const V2 = extern struct { b: f32 = 20, a: u32 = 10, b2: [2]u8 = .{ 7, 7 } };
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();
    const l1 = try Layout.copy(arena.allocator(), abi.layout.of(V1, .state));
    const l2 = try Layout.copy(arena.allocator(), abi.layout.of(V2, .state));
    const old: V1 = .{ .a = 42, .b = 0.5 };
    var new: V2 = .{};
    const m = migrate(l1, std.mem.asBytes(&old), l2, std.mem.asBytes(&new));
    try std.testing.expectEqual(V2{ .a = 42, .b = 0.5 }, new);
    try std.testing.expectEqual(@as(usize, 2), m.kept);
    try std.testing.expectEqual(@as(usize, 1), m.reset);
}

test "State migrates to a changed layout, and keeps itself when it is unchanged" {
    const V1 = extern struct { score: u32 = 0, name: [4]u8 = "none".* };
    const V2 = extern struct { level: u16 = 1, score: u32 = 0 };
    const D = struct {
        fn v1(_: abi.Memory, p: [*]u8) callconv(.c) void {
            @as(*V1, @ptrCast(@alignCast(p))).* = .{};
        }
        fn v2(_: abi.Memory, p: [*]u8) callconv(.c) void {
            @as(*V2, @ptrCast(@alignCast(p))).* = .{};
        }
    };
    const gpa = std.testing.allocator;
    var state: State = .init(gpa);
    defer state.deinit(gpa);
    try std.testing.expectEqual(@as(?Migration, null), try state.adopt(gpa, abi.layout.of(V1, .state), D.v1));
    @as(*V1, @ptrCast(state.live().ptr)).score = 99;
    try std.testing.expectEqual(@as(?Migration, null), try state.adopt(gpa, abi.layout.of(V1, .state), D.v1));
    try std.testing.expectEqual(@as(u32, 99), @as(*V1, @ptrCast(state.live().ptr)).score);
    const m = (try state.adopt(gpa, abi.layout.of(V2, .state), D.v2)).?;
    try std.testing.expectEqual(@as(usize, 1), m.reset);
    try std.testing.expectEqual(V2{ .level = 1, .score = 99 }, @as(*V2, @ptrCast(@alignCast(state.live().ptr))).*);
    // The header reads back as the layout.
    var arena: std.heap.ArenaAllocator = .init(gpa);
    defer arena.deinit();
    try std.testing.expectEqual(abi.layout.hash(V2), (try layoutOf(arena.allocator(), state.header)).hash);
}

test "arrays migrate element by element: fields, enums by name, shrink and growth" {
    const E1 = struct { x: f32 = 0, mood: enum(u8) { calm = 1, wild = 2 } = .calm };
    const E2 = struct { added: u8 = 9, mood: enum(u8) { wild = 5, calm = 6, sleepy = 7 } = .sleepy, x: f32 = 0 };
    const V1 = struct { list: struct { buffer: [4]E1 = @splat(.{}), len: u32 = 0 } = .{}, samples: [4]u16 = @splat(0), pos: [2]f32 = @splat(0), grid: [2][3]u8 = @splat(@splat(0)) };
    const V2 = struct { list: struct { buffer: [2]E2 = @splat(.{}), len: u32 = 0 } = .{}, samples: [6]u16 = @splat(5), pos: @Vector(2, f32) = @splat(0), grid: [3][2]u8 = @splat(@splat(0)) };
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();
    const l1 = try Layout.copy(arena.allocator(), abi.layout.of(V1, .state));
    const l2 = try Layout.copy(arena.allocator(), abi.layout.of(V2, .state));
    var old: V1 = .{ .samples = .{ 1, 2, 3, 4 }, .pos = .{ 3, 4 }, .grid = .{ .{ 1, 2, 3 }, .{ 4, 5, 6 } } };
    for (&old.list.buffer, 0..) |*e, i| e.* = .{ .x = @floatFromInt(i + 1), .mood = if (i % 2 == 0) .calm else .wild };
    old.list.len = 4;
    var new: V2 = .{};
    _ = migrate(l1, std.mem.asBytes(&old), l2, std.mem.asBytes(&new));
    try std.testing.expectEqual(E2{ .added = 9, .mood = .calm, .x = 1 }, new.list.buffer[0]);
    try std.testing.expectEqual(E2{ .added = 9, .mood = .wild, .x = 2 }, new.list.buffer[1]);
    // `len` is kept as it was: a List clamps it where it is read.
    try std.testing.expectEqual(@as(u32, 4), new.list.len);
    try std.testing.expectEqual([6]u16{ 1, 2, 3, 4, 5, 5 }, new.samples);
    try std.testing.expectEqual(@as(f32, 4), new.pos[1]);
    try std.testing.expectEqual([3][2]u8{ .{ 1, 2 }, .{ 4, 5 }, .{ 0, 0 } }, new.grid);

    // Growing back: the kept elements return, new ones take defaults.
    var back: V1 = .{};
    _ = migrate(l2, std.mem.asBytes(&new), l1, std.mem.asBytes(&back));
    try std.testing.expectEqual(@as(f32, 2), back.list.buffer[1].x);
    try std.testing.expectEqual(@as(f32, 0), back.list.buffer[2].x);
    try std.testing.expectEqual(.wild, back.list.buffer[1].mood);
}

test "an array of songs keeps its songs when a song gains a field" {
    const Note = struct { pitch: u8 = 0, length: u8 = 1 };
    const Song1 = struct { name: [8]u8 = @splat(0), notes: [16]Note = @splat(.{}), tempo: u16 = 120 };
    const Song2 = struct { tempo: u16 = 120, swing: f32 = 0.5, notes: [16]Note = @splat(.{}), name: [8]u8 = @splat(0) };
    const V1 = struct { songs: [8]Song1 = @splat(.{}), other: u32 = 0 };
    const V2 = struct { added: u8 = 1, songs: [8]Song2 = @splat(.{}) };
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();
    const l1 = try Layout.copy(arena.allocator(), abi.layout.of(V1, .state));
    const l2 = try Layout.copy(arena.allocator(), abi.layout.of(V2, .state));
    var old: V1 = .{};
    for (&old.songs, 0..) |*song, i| {
        song.name = "song   0".*;
        song.name[7] = '0' + @as(u8, @intCast(i));
        song.tempo = @intCast(100 + i);
        for (&song.notes, 0..) |*n, j| n.* = .{ .pitch = @intCast(i * 16 + j), .length = 2 };
    }
    var new: V2 = .{};
    const m = migrate(l1, std.mem.asBytes(&old), l2, std.mem.asBytes(&new));
    for (old.songs, new.songs) |a, b| {
        try std.testing.expectEqualSlices(u8, &a.name, &b.name);
        try std.testing.expectEqual(a.tempo, b.tempo);
        try std.testing.expectEqual(@as(f32, 0.5), b.swing);
        for (a.notes, b.notes) |x, y| try std.testing.expectEqual(x, y);
    }
    // songs[].notes is unchanged, so it copies whole; swing and added are new.
    try std.testing.expectEqual(@as(usize, 2), m.reset);
    // The same type on both sides copies in one piece.
    var same: V1 = .{};
    try std.testing.expectEqual(@as(usize, 2), migrate(l1, std.mem.asBytes(&old), l1, std.mem.asBytes(&same)).kept);
    try std.testing.expectEqualDeep(old, same);
}

test "compare goes leaf by leaf: padding never differs" {
    const S = struct { a: u8 = 1, b: u32 = 2, v: @Vector(3, f32) = .{ 1, 2, 3 }, list: [2]struct { c: u8 = 0, d: u16 = 0 } = @splat(.{}) };
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();
    const layout = try Layout.copy(arena.allocator(), abi.layout.of(S, .state));
    var x: S = .{};
    var y: S = .{};
    const a = std.mem.asBytes(&x);
    const b = std.mem.asBytes(&y);
    @memcpy(b, a);
    // Every byte no leaf covers.
    var covered: [@sizeOf(S)]bool = @splat(false);
    for (layout.fields) |leaf| {
        if (leaf.whole()) continue;
        var it = leaf.elements();
        while (it.next()) |offset| @memset(covered[offset..][0..leaf.size], true);
    }
    var padding: usize = 0;
    for (covered, 0..) |c, i| if (!c) {
        b[i] ^= 0xff;
        padding += 1;
    };
    try std.testing.expect(padding >= 4);
    try std.testing.expectEqual(@as(usize, 0), compare(layout, a, b).count);
    y.list[1].d = 7;
    y.v[2] = 0;
    const diff = compare(layout, a, b);
    try std.testing.expectEqual(@as(usize, 2), diff.count);
    var buf: [64]u8 = undefined;
    var w: std.Io.Writer = .fixed(&buf);
    try diff.last.?.leaf.name(diff.last.?.offset, &w);
    try std.testing.expectEqualStrings("list[1].d", w.buffered());
}

fn testPath(buf: []u8, tmp: anytype, name: []const u8) ![]const u8 {
    return std.mem.print(buf, ".zig-cache/tmp/{s}/{s}", .{ &tmp.sub_path, name });
}

test "a file that is not a state file is refused, untouched" {
    var tmp = std.testing.tmpDir(.{});
    defer tmp.cleanup();
    const io = std.testing.io;
    var buf: [std.fs.max_path_bytes]u8 = undefined;
    for ([_]usize{ 100, 3 * header_len }) |len| {
        const path = try testPath(&buf, tmp, "notes.state");
        const text = try std.testing.allocator.alloc(u8, len);
        defer std.testing.allocator.free(text);
        @memset(text, 'x');
        try std.Io.Dir.cwd().writeFile(io, .{ .sub_path = path, .data = text });
        try std.testing.expectError(error.NotAStateFile, OldState.open(path));
        const after = try std.Io.Dir.cwd().readFileAlloc(io, path, std.testing.allocator, .unlimited);
        defer std.testing.allocator.free(after);
        try std.testing.expectEqualSlices(u8, text, after);
    }
    try std.testing.expectError(error.FileNotFound, OldState.open(try testPath(&buf, tmp, "none.state")));
}

test "a state file from before element leaves (drat-meout's) imports with every value" {
    const gpa = std.testing.allocator;
    const io = std.testing.io;
    var tmp = std.testing.tmpDir(.{});
    defer tmp.cleanup();
    var buf: [std.fs.max_path_bytes]u8 = undefined;
    const path = try testPath(&buf, tmp, "game.state");
    const original = try std.Io.Dir.cwd().readFileAlloc(io, "test/fixtures/drat-meout-v1.state-fixture", gpa, .unlimited);
    defer gpa.free(original);
    try std.Io.Dir.cwd().writeFile(io, .{ .sub_path = path, .data = original });
    try std.testing.expectEqualStrings(&file_magic_v1, original[0..8]);

    var arena: std.heap.ArenaAllocator = .init(gpa);
    defer arena.deinit();
    const a = arena.allocator();
    const old = (try readLayout(a, original)).?;
    try std.testing.expect(old.find("tracker.songs") != null);
    const h: *const Header = @ptrCast(@alignCast(original.ptr));
    const live = original[header_len..][0..h.size];

    const file = try OldState.open(path);
    defer file.close();
    try std.testing.expectEqual(@as(usize, old_slot_count), file.slots);
    // Into the layout the game had when it wrote the file, as a sketch would
    // describe it: every byte; then into a changed one (one field gone, one
    // new): every other leaf keeps its value, the songs included (an
    // unchanged array type, so whole).
    for ([_][]const u8{ "", "scene" }) |drop| {
        var state: State = .init(gpa);
        defer state.deinit(gpa);
        _ = try state.adopt(gpa, try asSketchLayout(a, old, drop), NoDefaults.f);
        @memset(state.live(), 0);
        _ = try restore(a, file.layoutBytes(), file.slot(0).?, state.layout, state.live(), NoDefaults.f);
        if (drop.len == 0) try std.testing.expectEqualSlices(u8, live, state.live());
        for (old.fields) |leaf| {
            if (drop.len > 0 and std.mem.eql(u8, leaf.path, drop)) continue;
            try std.testing.expectEqualSlices(u8, leaf.bytes(live), leaf.bytes(state.live()));
        }
    }
    // The file is as it was.
    const after = try tmp.dir.readFileAlloc(io, "game.state", gpa, .unlimited);
    defer gpa.free(after);
    try std.testing.expectEqualSlices(u8, original, after);
}

const NoDefaults = struct {
    fn f(_: abi.Memory, _: [*]u8) callconv(.c) void {}
};

/// `l` as `abi.Layout`, without the leaf at `drop` and with a new byte
/// leaf `added` past the end, the type hash changed accordingly.
fn asSketchLayout(a: std.mem.Allocator, l: Layout, drop: []const u8) !abi.Layout {
    var fields: std.ArrayList(abi.Field) = .empty;
    for (l.fields) |leaf| {
        if (std.mem.eql(u8, leaf.path, drop)) continue;
        try fields.append(a, .{
            .path = try a.dupeSentinel(u8, leaf.path, 0),
            .offset = leaf.offset,
            .size = leaf.size,
            .kind = leaf.kind,
            .hash = leaf.hash,
            .tags = try a.dupeSentinel(u8, leaf.tags, 0),
        });
    }
    if (drop.len == 0) return .{ .size = l.size, .alignment = l.alignment, .hash = l.hash, .fields = fields.items };
    try fields.append(a, .{ .path = "added", .offset = @intCast(l.size), .size = 1, .kind = .uint, .hash = abi.layout.hash(u8) });
    return .{ .size = l.size + 1, .alignment = l.alignment, .hash = l.hash ^ 1, .fields = fields.items };
}