From 590ba7b9b579b97e34b51ab7e3460ebc85713343 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Wed, 28 Oct 2026 21:07:13 -0300 Subject: sketchbook: Zig 0.17, a Store on disk, requests, a scope (waveform, spectrum, spectrogram), audio codecs and fonts, web host --- src/host/memory.zig | 393 +++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 356 insertions(+), 37 deletions(-) (limited to 'src/host/memory.zig') diff --git a/src/host/memory.zig b/src/host/memory.zig index dd9f632..fc44e50 100644 --- a/src/host/memory.zig +++ b/src/host/memory.zig @@ -4,6 +4,12 @@ //! slots, plus a header describing the layout, so the state outlives restarts, //! a probe can read it from another process, and a reload with a changed //! layout can carry the old values over field by field. +//! +//! `StoreFile`: a heap in a file, mapped at the same address in every run, +//! so what it holds may point into it: the sketch's `Store` and everything +//! allocated for it outlive restarts. +//! +//! `Session`: this process's memory, kept across reloads. const std = @import("std"); const posix = std.posix; const linux = std.os.linux; @@ -197,7 +203,7 @@ pub const StateFile = struct { try self.resize(stride); const h = self.header(); h.* = .{ .size = new.size, .alignment = new.alignment, .hash = new.hash, .stride = stride, .used = old_used, .field_count = 0, .strings_len = 0 }; - try self.writeLayout(); + try writeLayout(self.map[0..header_len], self.layout); var total: Migration = .{}; for (old_slots, 0..) |maybe_old, i| { @@ -232,33 +238,34 @@ pub const StateFile = struct { } self.map = try mapFile(self.fd, len, .{ .READ = true, .WRITE = true }); } +}; - fn writeLayout(self: *StateFile) !void { - const h = self.header(); - const fields: [*]StoredField = @ptrCast(@alignCast(self.map.ptr + @sizeOf(Header))); - const strings_start = @sizeOf(Header) + self.layout.fields.len * @sizeOf(StoredField); - var strings: usize = 0; - for (self.layout.fields, 0..) |leaf, i| { - if (strings_start + strings + leaf.path.len + leaf.tags.len > header_len) return error.LayoutTooLarge; - const base = strings_start + strings; - @memcpy(self.map[base..][0..leaf.path.len], leaf.path); - @memcpy(self.map[base + leaf.path.len ..][0..leaf.tags.len], leaf.tags); - 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), - }; - strings += leaf.path.len + leaf.tags.len; - } - h.field_count = @intCast(self.layout.fields.len); - h.strings_len = @intCast(strings); +/// Writes `layout`'s leaves after the `Header` at the start of `region`. +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| { + if (strings_start + strings + leaf.path.len + leaf.tags.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); + 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), + }; + strings += leaf.path.len + leaf.tags.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. pub fn readLayout(arena: std.mem.Allocator, map: []const u8) !?Layout { @@ -306,15 +313,211 @@ pub fn mapReadOnly(path: []const u8) []align(page) const u8 { return posix.mmap(null, @intCast(len), .{ .READ = true }, .{ .TYPE = .SHARED }, fd, 0) catch &.{}; } +/// Where every store is mapped, in every process: far from where Linux puts +/// executables (0x55...) and mappings (0x7f...). +pub const store_base: usize = 0x2000_0000_0000; +/// The most a store can grow to. Only reserved: pages exist as they are used. +pub const store_reserve: usize = 64 << 30; +pub const store_magic = "SKSTORE1".*; +/// The layout region is a state file header; the allocator's own record +/// follows, then the heap. +const meta_offset = header_len; +const heap_offset = 2 * header_len; + +/// A heap in a file, with the sketch's `Store` at its root. Mapped at +/// `store_base` in every run, so pointers it holds into itself stay valid +/// across restarts. Not crash-safe: a crash in the middle of an allocation +/// can leave it inconsistent (`--fresh` starts over). +/// +/// Blocks come in power-of-two sizes, each class with a free list threaded +/// through the free blocks, so growing a list by doubling reuses what it +/// frees. The file grows by mapping more of it in place: nothing moves. +pub const StoreFile = struct { + fd: posix.fd_t, + /// Bytes of the file mapped at `store_base`. + len: usize, + /// The root's layout, owned by `arena`. + layout: Layout, + arena: std.heap.ArenaAllocator, + + const Meta = extern struct { + magic: [8]u8 = store_magic, + base: u64 = store_base, + /// Offset of the first byte never handed out. + top: u64 = heap_offset, + /// Offset of the sketch's Store, or 0 before the first adopt. + root: u64 = 0, + /// Offsets of the first free block of each size class (2^i bytes), 0 + /// when none; a free block's first 8 bytes hold the next one's. + free: [64]u64 = @splat(0), + }; + + pub fn open(gpa: std.mem.Allocator, path: []const u8, fresh: bool) !StoreFile { + const fd = try posix.openat(posix.AT.FDCWD, path, .{ .ACCMODE = .RDWR, .CREAT = true }, 0o600); + errdefer _ = posix.system.close(fd); + // The same file mapped by two processes would be two heaps writing + // over each other. + if (linux.errno(linux.flock(fd, posix.LOCK.EX | posix.LOCK.NB)) != .SUCCESS) return error.StoreInUse; + const reserved = posix.mmap(@ptrFromInt(store_base), store_reserve, .{}, .{ .TYPE = .PRIVATE, .ANONYMOUS = true, .NORESERVE = true, .FIXED_NOREPLACE = true }, -1, 0) catch return error.StoreAddressTaken; + // Old kernels treat FIXED_NOREPLACE as a hint. + if (@intFromPtr(reserved.ptr) != store_base) { + posix.munmap(reserved); + return error.StoreAddressTaken; + } + errdefer posix.munmap(reserved); + var self: StoreFile = .{ .fd = fd, .len = 0, .layout = .{}, .arena = .init(gpa) }; + errdefer self.arena.deinit(); + const size: usize = @intCast(try fileSize(fd)); + if (!fresh and size >= heap_offset) { + try self.grow(size); + const m = self.meta(); + if (std.mem.eql(u8, &m.magic, &store_magic) and m.base == store_base and m.top <= size) { + self.layout = try readLayout(self.arena.allocator(), self.region()) orelse .{}; + return self; + } + } + try self.wipe(); + return self; + } + + pub fn close(self: *StoreFile) void { + posix.munmap(@as([*]align(page) u8, @ptrFromInt(store_base))[0..store_reserve]); + _ = posix.system.close(self.fd); + self.arena.deinit(); + } + + /// Empties the store: no root, nothing allocated. + fn wipe(self: *StoreFile) !void { + // Mapped pages past the new end would fault: map the reserve back. + if (self.len > heap_offset) { + _ = try posix.mmap(@ptrFromInt(store_base + heap_offset), self.len - heap_offset, .{}, .{ .TYPE = .PRIVATE, .ANONYMOUS = true, .NORESERVE = true, .FIXED = true }, -1, 0); + self.len = heap_offset; + } + try truncate(self.fd, heap_offset); + try self.grow(heap_offset); + @memset(self.region(), 0); + self.header().* = .{ .magic = store_magic, .size = 0, .alignment = 1, .hash = 0, .stride = 0, .used = 0, .field_count = 0, .strings_len = 0 }; + self.meta().* = .{}; + self.layout = .{}; + } + + /// Maps the file up to `need` bytes, growing it when it is shorter. + fn grow(self: *StoreFile, need: usize) !void { + if (need <= self.len) return; + const len = std.mem.alignForward(usize, @max(need, self.len * 2, 1 << 20), page); + if (len > store_reserve) return error.StoreFull; + if (try fileSize(self.fd) < len) try truncate(self.fd, len); + _ = try posix.mmap(@ptrFromInt(store_base + self.len), len - self.len, .{ .READ = true, .WRITE = true }, .{ .TYPE = .SHARED, .FIXED = true }, self.fd, self.len); + self.len = len; + } + + fn region(_: *StoreFile) []u8 { + return @as([*]u8, @ptrFromInt(store_base))[0..header_len]; + } + fn header(_: *StoreFile) *Header { + return @ptrFromInt(store_base); + } + fn meta(_: *StoreFile) *Meta { + return @ptrFromInt(store_base + meta_offset); + } + + /// The sketch's Store. + pub fn root(self: *StoreFile) [*]u8 { + const offset = self.meta().root; + return @ptrFromInt(store_base + if (offset == 0) heap_offset else offset); + } + + pub const Adoption = StateFile.Adoption; + + /// Makes the root hold `new`'s layout: the new defaults, then every field + /// whose path and type are unchanged, copied over. Pointer fields keep + /// pointing where they did, since the store never moves. + pub fn adopt(self: *StoreFile, gpa: std.mem.Allocator, new: abi.Layout, defaults: *const fn (abi.Memory, [*]u8) callconv(.c) void) !Adoption { + const m = self.meta(); + if (m.root != 0 and self.layout.hash == new.hash and self.layout.size == new.size) return .unchanged; + const a = self.allocator(); + const alignment: std.mem.Alignment = .fromByteUnits(@max(new.alignment, 1)); + const fresh = a.rawAlloc(@max(new.size, 1), alignment, @returnAddress()) orelse return error.StoreFull; + @memset(fresh[0..@max(new.size, 1)], 0); + defaults(.store, fresh); + + var kept = self.arena; + defer kept.deinit(); + self.arena = .init(gpa); + const old_layout = self.layout; + self.layout = try Layout.copy(self.arena.allocator(), new); + var result: Adoption = .created; + if (m.root != 0) { + const old: [*]u8 = @ptrFromInt(store_base + m.root); + result = .{ .migrated = migrate(old_layout, old[0..old_layout.size], self.layout, fresh[0..new.size]) }; + a.rawFree(old[0..@max(old_layout.size, 1)], .fromByteUnits(@max(old_layout.alignment, 1)), @returnAddress()); + } + self.header().* = .{ .magic = store_magic, .size = new.size, .alignment = new.alignment, .hash = new.hash, .stride = 0, .used = 1, .field_count = 0, .strings_len = 0 }; + try writeLayout(self.region(), self.layout); + m.root = @intFromPtr(fresh) - store_base; + return result; + } + + pub fn allocator(self: *StoreFile) std.mem.Allocator { + return .{ .ptr = self, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } }; + } + + fn class(len: usize, alignment: std.mem.Alignment) u6 { + return @intCast(std.math.log2_int_ceil(usize, @max(len, alignment.toByteUnits(), 16))); + } + + fn alloc(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, _: usize) ?[*]u8 { + const self: *StoreFile = @ptrCast(@alignCast(ctx)); + const m = self.meta(); + const c = class(len, alignment); + const size = @as(usize, 1) << c; + if (m.free[c] != 0) { + const block: [*]u8 = @ptrFromInt(store_base + m.free[c]); + if (alignment.check(@intFromPtr(block))) { + m.free[c] = @as(*const u64, @ptrCast(@alignCast(block))).*; + return block; + } + } + const offset = std.mem.alignForward(usize, m.top, @max(@min(size, page), alignment.toByteUnits())); + self.grow(offset + size) catch return null; + m.top = offset + size; + return @ptrFromInt(store_base + offset); + } + + /// In place within the block's size class. + fn resize(_: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, _: usize) bool { + return class(memory.len, alignment) == class(new_len, alignment); + } + + fn remap(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret: usize) ?[*]u8 { + return if (resize(ctx, memory, alignment, new_len, ret)) memory.ptr else null; + } + + fn free(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, _: usize) void { + const self: *StoreFile = @ptrCast(@alignCast(ctx)); + const m = self.meta(); + const c = class(memory.len, alignment); + @as(*u64, @ptrCast(@alignCast(memory.ptr))).* = m.free[c]; + m.free[c] = @intFromPtr(memory.ptr) - store_base; + } +}; + +fn truncate(fd: posix.fd_t, len: usize) !void { + switch (posix.errno(posix.system.ftruncate(fd, @intCast(len)))) { + .SUCCESS => {}, + else => |err| return posix.unexpectedErrno(err), + } +} + /// Session memory: survives reloads while its layout hash is unchanged. -/// `heap` is released with it. +/// Everything allocated from `heap` is released with it. pub const Session = struct { bytes: []align(16) u8 = &.{}, hash: u64 = 0, - heap: std.heap.ArenaAllocator, + heap: Heap, pub fn init(gpa: std.mem.Allocator) Session { - return .{ .heap = .init(gpa) }; + return .{ .heap = .{ .gpa = gpa } }; } pub fn deinit(self: *Session, gpa: std.mem.Allocator) void { @@ -328,7 +531,7 @@ pub const Session = struct { if (layout.alignment > 16) return error.SessionOveraligned; gpa.free(self.bytes); self.bytes = &.{}; - _ = self.heap.reset(.free_all); + self.heap.reset(); self.bytes = try gpa.alignedAlloc(u8, .@"16", @max(layout.size, 1)); @memset(self.bytes, 0); defaults(.session, self.bytes.ptr); @@ -337,13 +540,88 @@ pub const Session = struct { } }; +/// 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, .forbidden)); - const l2 = try Layout.copy(arena.allocator(), abi.layout.of(V2, .forbidden)); + 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 = .{}; @@ -358,8 +636,8 @@ test "migration keeps unchanged fields and defaults the rest" { 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, .forbidden)); - const l2 = try Layout.copy(arena.allocator(), abi.layout.of(V2, .forbidden)); + 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)); @@ -382,12 +660,12 @@ test "state file migrates live state and snapshots, and a reopen reads the layou var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var buf: [std.fs.max_path_bytes]u8 = undefined; - const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/test.state", .{&tmp.sub_path}); + const path = try std.mem.print(&buf, ".zig-cache/tmp/{s}/test.state", .{&tmp.sub_path}); const gpa = std.testing.allocator; { var file = try StateFile.open(gpa, path); defer file.close(); - try std.testing.expectEqual(StateFile.Adoption.created, try file.adopt(gpa, abi.layout.of(V1, .forbidden), D.v1)); + try std.testing.expectEqual(StateFile.Adoption.created, try file.adopt(gpa, abi.layout.of(V1, .state), D.v1)); file.markUsed(0, true); @as(*V1, @ptrCast(file.slot(0).ptr)).score = 99; @memcpy(file.slot(3), file.slot(0)); @@ -396,7 +674,7 @@ test "state file migrates live state and snapshots, and a reopen reads the layou var file = try StateFile.open(gpa, path); defer file.close(); try std.testing.expectEqual(abi.layout.hash(V1), file.layout.hash); - const adoption = try file.adopt(gpa, abi.layout.of(V2, .forbidden), D.v2); + const adoption = try file.adopt(gpa, abi.layout.of(V2, .state), D.v2); try std.testing.expectEqual(@as(usize, 1), adoption.migrated.reset); for ([_]usize{ 0, 3 }) |i| { const s: *V2 = @ptrCast(file.slot(i).ptr); @@ -404,3 +682,44 @@ test "state file migrates live state and snapshots, and a reopen reads the layou } try std.testing.expect(!file.used(1)); } + +test "a store keeps its root and what it points to across a reopen, and migrates by field" { + const V1 = struct { list: std.ArrayList(u32) = .empty, count: u32 = 0 }; + const V2 = struct { added: u8 = 7, list: std.ArrayList(u32) = .empty }; + 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))).* = .{}; + } + }; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.mem.print(&buf, ".zig-cache/tmp/{s}/test.store", .{&tmp.sub_path}); + const gpa = std.testing.allocator; + { + var store = try StoreFile.open(gpa, path, false); + defer store.close(); + try std.testing.expectEqual(StoreFile.Adoption.created, try store.adopt(gpa, abi.layout.of(V1, .store), D.v1)); + const v: *V1 = @ptrCast(@alignCast(store.root())); + for (0..10_000) |i| try v.list.append(store.allocator(), @intCast(i)); + v.count = 3; + try std.testing.expectError(error.StoreInUse, StoreFile.open(gpa, path, false)); + } + { + var store = try StoreFile.open(gpa, path, false); + defer store.close(); + try std.testing.expectEqual(StoreFile.Adoption.unchanged, try store.adopt(gpa, abi.layout.of(V1, .store), D.v1)); + const adoption = try store.adopt(gpa, abi.layout.of(V2, .store), D.v2); + try std.testing.expectEqual(@as(usize, 1), adoption.migrated.reset); + const v: *V2 = @ptrCast(@alignCast(store.root())); + try std.testing.expectEqual(@as(u8, 7), v.added); + try std.testing.expectEqual(@as(u32, 9999), v.list.items[9999]); + v.list.deinit(store.allocator()); + } + var store = try StoreFile.open(gpa, path, true); + defer store.close(); + try std.testing.expectEqual(StoreFile.Adoption.created, try store.adopt(gpa, abi.layout.of(V2, .store), D.v2)); +} -- cgit v1.3