tiny.memtrace.stack.roots

1pub const roots = roots_mod;

1const std = @import("std");2const sys = @import("sys");3const observe = @import("alloc_observe");4const pretty_json = @import("pretty").json;5const memtrace = @import("../root.zig");6const analyze_mod = @import("analyze.zig");7const capture_mod = @import("capture.zig");8const identity_mod = @import("identity.zig");9const symbolize_mod = @import("symbolize.zig");1011const coverage_mod = memtrace.coverage;12const event_mod = memtrace.event;1314const Allocator = std.mem.Allocator;1516pub const Format = enum {17    text,18    jsonl,19};2021pub const Sort = enum {22    roots,23    requested_bytes,24    backing_bytes,25    high_water,26};2728pub const Detail = enum {29    summary,30    sources,31    full,32};3334pub const Options = struct {35    top: usize = std.math.maxInt(usize),36    frame_limit: usize = capture_mod.max_frames_limit,37    format: Format = .text,38    binary_path: ?[]const u8 = null,39    selection: analyze_mod.Selection = .allocations,40    sort: Sort = .high_water,41    detail: Detail = .full,42    window: analyze_mod.Window = .{},43};4445const Metrics = struct {46    operations: u64 = 0,47    logical_operations: u64 = 0,48    backing_operations: u64 = 0,49    physical_operations: u64 = 0,50    backing_requested_bytes: u128 = 0,51    physical_requested_bytes: u128 = 0,52    max_depth: u32 = 0,5354    fn record(self: *Metrics, event: event_mod.ReplayEvent) !void {55        self.operations = try std.math.add(u64, self.operations, 1);56        const bytes = requestBytes(event);57        switch (event.layer) {58            .logical_allocator => {59                self.logical_operations = try std.math.add(60                    u64,61                    self.logical_operations,62                    1,63                );64            },65            .backing_boundary => {66                self.backing_operations = try std.math.add(67                    u64,68                    self.backing_operations,69                    1,70                );71                self.backing_requested_bytes = try std.math.add(72                    u128,73                    self.backing_requested_bytes,74                    bytes,75                );76            },77            .physical_page => {78                self.physical_operations = try std.math.add(79                    u64,80                    self.physical_operations,81                    1,82                );83                self.physical_requested_bytes = try std.math.add(84                    u128,85                    self.physical_requested_bytes,86                    bytes,87                );88            },89        }90    }9192    fn merge(self: *Metrics, other: Metrics) !void {93        self.operations = try std.math.add(94            u64,95            self.operations,96            other.operations,97        );98        self.logical_operations = try std.math.add(99            u64,100            self.logical_operations,101            other.logical_operations,102        );103        self.backing_operations = try std.math.add(104            u64,105            self.backing_operations,106            other.backing_operations,107        );108        self.physical_operations = try std.math.add(109            u64,110            self.physical_operations,111            other.physical_operations,112        );113        self.backing_requested_bytes = try std.math.add(114            u128,115            self.backing_requested_bytes,116            other.backing_requested_bytes,117        );118        self.physical_requested_bytes = try std.math.add(119            u128,120            self.physical_requested_bytes,121            other.physical_requested_bytes,122        );123        self.max_depth = @max(self.max_depth, other.max_depth);124    }125126    fn mergeChild(self: *Metrics, child: Metrics) !void {127        try self.merge(child);128        self.max_depth = @max(129            self.max_depth,130            try std.math.add(u32, child.max_depth, 1),131        );132    }133};134135const RootKey = struct {136    stack_id: u32,137    kind: event_mod.Kind,138    succeeded: bool,139    layer: event_mod.Layer,140    producer: observe.Producer,141};142143const Lifetime = struct {144    live_allocations: u64 = 0,145    live_bytes: u128 = 0,146    high_water_live_bytes: u128 = 0,147148    fn allocate(self: *Lifetime, len: usize) !void {149        self.live_allocations = try std.math.add(150            u64,151            self.live_allocations,152            1,153        );154        self.live_bytes = try std.math.add(u128, self.live_bytes, len);155        self.high_water_live_bytes = @max(156            self.high_water_live_bytes,157            self.live_bytes,158        );159    }160161    fn free(self: *Lifetime, len: usize) !void {162        if (self.live_allocations == 0 or self.live_bytes < len) {163            return error.InvalidCausalRootLifetime;164        }165        self.live_allocations -= 1;166        self.live_bytes -= len;167    }168169    fn resize(self: *Lifetime, old_len: usize, new_len: usize) !void {170        if (self.live_bytes < old_len) {171            return error.InvalidCausalRootLifetime;172        }173        self.live_bytes -= old_len;174        self.live_bytes = try std.math.add(u128, self.live_bytes, new_len);175        self.high_water_live_bytes = @max(176            self.high_water_live_bytes,177            self.live_bytes,178        );179    }180};181182const Counters = struct {183    roots: u64 = 0,184    root_requested_bytes: u128 = 0,185    metrics: Metrics = .{},186    lifetime: Lifetime = .{},187188    fn record(189        self: *Counters,190        event: event_mod.ReplayEvent,191        metrics: Metrics,192    ) !void {193        self.roots = try std.math.add(u64, self.roots, 1);194        self.root_requested_bytes = try std.math.add(195            u128,196            self.root_requested_bytes,197            requestBytes(event),198        );199        try self.metrics.merge(metrics);200    }201202    fn merge(self: *Counters, other: Counters) !void {203        self.roots = try std.math.add(u64, self.roots, other.roots);204        self.root_requested_bytes = try std.math.add(205            u128,206            self.root_requested_bytes,207            other.root_requested_bytes,208        );209        try self.metrics.merge(other.metrics);210    }211};212213const Summary = struct {214    key: RootKey,215    counters: Counters,216    definition: analyze_mod.Definition,217};218219const Totals = struct {220    roots: u64 = 0,221    successful: u64 = 0,222    failed: u64 = 0,223    root_requested_bytes: u128 = 0,224    metrics: Metrics = .{},225    lifetime: Lifetime = .{},226};227228const SourceKey = struct {229    kind: event_mod.Kind,230    succeeded: bool,231    layer: event_mod.Layer,232    producer: observe.Producer,233    site: u64,234    caller: u64,235};236237const Source = struct {238    key: SourceKey,239    counters: Counters,240    unique_stacks: u32,241};242243const LiveAllocation = struct {244    root: RootKey,245    source: SourceKey,246    len: usize,247};248249const Display = struct {250    source_groups: usize,251    displayed_sources: usize,252    root_stacks: usize,253    displayed_stacks: usize,254};255256const ChildEvidence = struct {257    operation_id: u64,258    sequence: u64,259    stack_id: u32,260    scope_id: u32,261    kind: event_mod.Kind,262    layer: event_mod.Layer,263    producer: observe.Producer,264    succeeded: bool,265    requested_bytes: usize,266    return_address: u64,267268    fn fromEvent(event: event_mod.ReplayEvent) ChildEvidence {269        return .{270            .operation_id = event.operation_id,271            .sequence = event.seq orelse 0,272            .stack_id = event.stack_id,273            .scope_id = event.scope_id,274            .kind = event.kind,275            .layer = event.layer,276            .producer = event.producer,277            .succeeded = event.succeeded,278            .requested_bytes = if (event.kind.isMemoryOperation())279                requestBytes(event)280            else281                0,282            .return_address = event.return_address,283        };284    }285};286287const Pending = struct {288    metrics: Metrics = .{},289    child: ChildEvidence,290};291292const DanglingParent = struct {293    operation_id: u64,294    child: ChildEvidence,295    site_address: u64,296};297298const OperationLedger = struct {299    seen: std.DynamicBitSetUnmanaged = .{},300    unique: u64 = 0,301    minimum: u64 = std.math.maxInt(u64),302    maximum: u64 = 0,303    last_id: u64 = 0,304    last_parent: u64 = 0,305306    fn deinit(self: *OperationLedger, allocator: Allocator) void {307        self.seen.deinit(allocator);308        self.* = undefined;309    }310311    fn record(312        self: *OperationLedger,313        allocator: Allocator,314        operation_id: u64,315        parent_operation_id: u64,316    ) !void {317        const index = std.math.cast(usize, operation_id) orelse318            return error.CausalOperationIdOverflow;319        try self.ensureCapacity(allocator, index);320        if (self.seen.isSet(index)) {321            if (operation_id != self.last_id) {322                return error.NonContiguousCausalOperationGroup;323            }324            if (parent_operation_id != self.last_parent) {325                return error.CausalOperationParentConflict;326            }327            return;328        }329        self.seen.set(index);330        self.unique = try std.math.add(u64, self.unique, 1);331        self.minimum = @min(self.minimum, operation_id);332        self.maximum = @max(self.maximum, operation_id);333        self.last_id = operation_id;334        self.last_parent = parent_operation_id;335    }336337    fn ensureCapacity(338        self: *OperationLedger,339        allocator: Allocator,340        index: usize,341    ) !void {342        if (index < self.seen.bit_length) return;343        const required = try std.math.add(usize, index, 1);344        const doubled = std.math.mul(345            usize,346            @max(self.seen.bit_length, 1024),347            2,348        ) catch std.math.maxInt(usize);349        try self.seen.resize(allocator, @max(required, doubled), false);350    }351352    fn validate(self: OperationLedger) !void {353        if (self.unique == 0) return;354        const span = try std.math.add(355            u64,356            self.maximum - self.minimum,357            1,358        );359        if (span != self.unique) return error.NonContiguousCausalOperations;360    }361};362363const Analyzer = struct {364    allocator: Allocator,365    stack: analyze_mod.Analyzer,366    pending: std.AutoHashMapUnmanaged(u64, Pending) = .{},367    groups: std.AutoHashMapUnmanaged(RootKey, Counters) = .{},368    source_lifetimes: std.AutoHashMapUnmanaged(SourceKey, Lifetime) = .{},369    live_allocations: std.AutoHashMapUnmanaged(u64, LiveAllocation) = .{},370    operation_ledger: OperationLedger = .{},371    lifetime: Lifetime = .{},372    finished: bool = false,373374    fn init(allocator: Allocator, window: analyze_mod.Window) Analyzer {375        return .{376            .allocator = allocator,377            .stack = analyze_mod.Analyzer.init(allocator, window),378        };379    }380381    fn deinit(self: *Analyzer) void {382        self.stack.deinit();383        self.pending.deinit(self.allocator);384        self.groups.deinit(self.allocator);385        self.source_lifetimes.deinit(self.allocator);386        self.live_allocations.deinit(self.allocator);387        self.operation_ledger.deinit(self.allocator);388        self.* = undefined;389    }390391    fn ingestJsonLine(self: *Analyzer, line: []const u8) !void {392        if (self.finished) return error.CausalRootAnalyzerFinished;393        const text = std.mem.trim(u8, line, " \t\r\n");394        if (text.len == 0) return;395        try self.stack.ingestJsonLine(text);396        if (identity_mod.isMetadataLine(text) or397            coverage_mod.isMetadataLine(text) or398            capture_mod.isMetadataLine(text))399        {400            return;401        }402        const event = try event_mod.parseReplayFast(text);403        const memory_operation = event.kind.isMemoryOperation();404        if (!memory_operation and event.kind != .lifecycle) return;405        if (event.operation_id == 0) return error.MissingCausalOperation;406        if (event.parent_operation_id >= event.operation_id and407            event.parent_operation_id != 0)408        {409            return error.CausalOperationCycle;410        }411        if (memory_operation) try self.recordExistingLifetime(event);412        try self.operation_ledger.record(413            self.allocator,414            event.operation_id,415            event.parent_operation_id,416        );417418        var metrics = if (self.pending.fetchRemove(event.operation_id)) |entry|419            entry.value.metrics420        else421            Metrics{};422        if (memory_operation) try metrics.record(event);423        if (event.parent_operation_id == 0) {424            if (!memory_operation) return;425            if (!try self.stack.includes(event)) return;426            return self.recordRoot(event, metrics);427        }428        const parent = try self.pending.getOrPut(429            self.allocator,430            event.parent_operation_id,431        );432        if (!parent.found_existing) {433            parent.value_ptr.* = .{434                .child = ChildEvidence.fromEvent(event),435            };436        }437        if (memory_operation) {438            try parent.value_ptr.metrics.mergeChild(metrics);439        } else {440            try parent.value_ptr.metrics.merge(metrics);441        }442    }443444    fn finish(self: *Analyzer) !void {445        if (self.finished) return error.CausalRootAnalyzerFinished;446        try self.stack.validate();447        try self.finishCausal();448    }449450    fn finishCausal(self: *Analyzer) !void {451        if (self.finished) return error.CausalRootAnalyzerFinished;452        if (self.pending.count() != 0) return error.DanglingParentOperation;453        try self.operation_ledger.validate();454        try self.validateLifetimes();455        self.finished = true;456    }457458    fn validateLifetimes(self: *const Analyzer) !void {459        var group_allocations: u64 = 0;460        var group_bytes: u128 = 0;461        var groups = self.groups.valueIterator();462        while (groups.next()) |counters| {463            group_allocations = try std.math.add(464                u64,465                group_allocations,466                counters.lifetime.live_allocations,467            );468            group_bytes = try std.math.add(469                u128,470                group_bytes,471                counters.lifetime.live_bytes,472            );473        }474        var source_allocations: u64 = 0;475        var source_bytes: u128 = 0;476        var sources = self.source_lifetimes.valueIterator();477        while (sources.next()) |lifetime| {478            source_allocations = try std.math.add(479                u64,480                source_allocations,481                lifetime.live_allocations,482            );483            source_bytes = try std.math.add(484                u128,485                source_bytes,486                lifetime.live_bytes,487            );488        }489        if (group_allocations != self.lifetime.live_allocations or490            source_allocations != self.lifetime.live_allocations or491            self.live_allocations.count() != self.lifetime.live_allocations or492            group_bytes != self.lifetime.live_bytes or493            source_bytes != self.lifetime.live_bytes)494        {495            return error.InvalidCausalRootLifetime;496        }497    }498499    fn collectDangling(500        self: *const Analyzer,501    ) !std.ArrayListUnmanaged(DanglingParent) {502        var result = std.ArrayListUnmanaged(DanglingParent).empty;503        errdefer result.deinit(self.allocator);504        try result.ensureTotalCapacity(self.allocator, self.pending.count());505        var pending = self.pending.iterator();506        while (pending.next()) |entry| {507            const child = entry.value_ptr.child;508            const site_address = if (child.stack_id != 0)509                (self.stack.stackDefinition(child.stack_id) orelse510                    return error.MissingStackDefinition).call_addresses[0]511            else source: {512                const return_address = std.math.cast(513                    usize,514                    child.return_address,515                ) orelse return error.InvalidDanglingParentSite;516                if (return_address == 0) return error.MissingDanglingParentSite;517                break :source capture_mod.callAddress(return_address);518            };519            result.appendAssumeCapacity(.{520                .operation_id = entry.key_ptr.*,521                .child = child,522                .site_address = site_address,523            });524        }525        std.mem.sort(526            DanglingParent,527            result.items,528            {},529            danglingParentLessThan,530        );531        return result;532    }533534    fn recordRoot(535        self: *Analyzer,536        event: event_mod.ReplayEvent,537        metrics: Metrics,538    ) !void {539        const key = RootKey{540            .stack_id = event.stack_id,541            .kind = event.kind,542            .succeeded = event.succeeded,543            .layer = event.layer,544            .producer = event.producer,545        };546        const entry = try self.groups.getOrPut(self.allocator, key);547        if (!entry.found_existing) entry.value_ptr.* = .{};548        try entry.value_ptr.record(event, metrics);549        try self.recordLifetime(event, key);550    }551552    fn recordLifetime(553        self: *Analyzer,554        event: event_mod.ReplayEvent,555        root: RootKey,556    ) !void {557        switch (event.kind) {558            .alloc => if (event.succeeded and event.tracked and event.len != 0) {559                try self.recordAllocation(event, root);560            },561            else => {},562        }563    }564565    fn recordExistingLifetime(566        self: *Analyzer,567        event: event_mod.ReplayEvent,568    ) !void {569        switch (event.kind) {570            .free, .release => if (event.tracked and event.len != 0) {571                try self.recordFree(event);572            },573            .resize => if (event.succeeded and event.tracked) {574                try self.recordResize(event);575            },576            .remap => if (event.succeeded and event.tracked) {577                try self.recordRemap(event);578            },579            else => {},580        }581    }582583    fn recordAllocation(584        self: *Analyzer,585        event: event_mod.ReplayEvent,586        root: RootKey,587    ) !void {588        const source = self.sourceKey(root);589        const allocation_key = allocationKey(590            event.allocation_id,591            event.address,592        );593        if (allocation_key == 0) return error.MissingCausalAllocationIdentity;594        const live = try self.live_allocations.getOrPut(595            self.allocator,596            allocation_key,597        );598        if (live.found_existing) return error.DuplicateCausalAllocation;599        live.value_ptr.* = .{600            .root = root,601            .source = source,602            .len = event.len,603        };604        try self.lifetime.allocate(event.len);605        try self.groups.getPtr(root).?.lifetime.allocate(event.len);606        const source_entry = try self.source_lifetimes.getOrPut(607            self.allocator,608            source,609        );610        if (!source_entry.found_existing) source_entry.value_ptr.* = .{};611        try source_entry.value_ptr.allocate(event.len);612    }613614    fn recordFree(615        self: *Analyzer,616        event: event_mod.ReplayEvent,617    ) !void {618        const allocation_key = allocationKey(619            event.allocation_id,620            event.address,621        );622        const removed = self.live_allocations.fetchRemove(allocation_key) orelse {623            return;624        };625        try self.release(removed.value, removed.value.len);626    }627628    fn recordResize(629        self: *Analyzer,630        event: event_mod.ReplayEvent,631    ) !void {632        const allocation_key = allocationKey(633            event.allocation_id,634            event.address,635        );636        const live = self.live_allocations.getPtr(allocation_key) orelse {637            return;638        };639        try self.resize(live.*, event.len);640        live.len = event.len;641    }642643    fn recordRemap(644        self: *Analyzer,645        event: event_mod.ReplayEvent,646    ) !void {647        const old_key = allocationKey(648            event.allocation_id,649            event.old_address,650        );651        const new_key = allocationKey(652            event.allocation_id,653            event.address,654        );655        if (old_key == new_key) return self.recordResize(event);656        const removed = self.live_allocations.fetchRemove(old_key) orelse {657            return;658        };659        const entry = try self.live_allocations.getOrPut(660            self.allocator,661            new_key,662        );663        if (entry.found_existing) return error.DuplicateCausalAllocation;664        entry.value_ptr.* = removed.value;665        try self.resize(entry.value_ptr.*, event.len);666        entry.value_ptr.len = event.len;667    }668669    fn release(670        self: *Analyzer,671        live: LiveAllocation,672        len: usize,673    ) !void {674        try self.lifetime.free(len);675        try self.groups.getPtr(live.root).?.lifetime.free(len);676        try self.source_lifetimes.getPtr(live.source).?.free(len);677    }678679    fn resize(680        self: *Analyzer,681        live: LiveAllocation,682        new_len: usize,683    ) !void {684        try self.lifetime.resize(live.len, new_len);685        try self.groups.getPtr(live.root).?.lifetime.resize(686            live.len,687            new_len,688        );689        try self.source_lifetimes.getPtr(live.source).?.resize(690            live.len,691            new_len,692        );693    }694695    fn sourceKey(self: *const Analyzer, root: RootKey) SourceKey {696        const definition = self.stack.stackDefinition(root.stack_id).?;697        return .{698            .kind = root.kind,699            .succeeded = root.succeeded,700            .layer = root.layer,701            .producer = root.producer,702            .site = definition.call_addresses[0],703            .caller = callerAddress(definition),704        };705    }706707    fn collect(708        self: *const Analyzer,709        selection: analyze_mod.Selection,710    ) !std.ArrayListUnmanaged(Summary) {711        if (!self.finished) return error.CausalRootAnalyzerNotFinished;712        var result = std.ArrayListUnmanaged(Summary).empty;713        errdefer result.deinit(self.allocator);714        try result.ensureTotalCapacity(self.allocator, self.groups.count());715        var groups = self.groups.iterator();716        while (groups.next()) |entry| {717            if (!selection.includes(entry.key_ptr.kind)) continue;718            result.appendAssumeCapacity(.{719                .key = entry.key_ptr.*,720                .counters = entry.value_ptr.*,721                .definition = self.stack.stackDefinition(722                    entry.key_ptr.stack_id,723                ).?,724            });725        }726        return result;727    }728729    fn totals(730        self: *const Analyzer,731        selection: analyze_mod.Selection,732    ) !Totals {733        if (!self.finished) return error.CausalRootAnalyzerNotFinished;734        var result: Totals = .{};735        var groups = self.groups.iterator();736        while (groups.next()) |entry| {737            if (!selection.includes(entry.key_ptr.kind)) continue;738            result.roots = try std.math.add(739                u64,740                result.roots,741                entry.value_ptr.roots,742            );743            result.root_requested_bytes = try std.math.add(744                u128,745                result.root_requested_bytes,746                entry.value_ptr.root_requested_bytes,747            );748            if (entry.key_ptr.succeeded) {749                result.successful = try std.math.add(750                    u64,751                    result.successful,752                    entry.value_ptr.roots,753                );754            } else {755                result.failed = try std.math.add(756                    u64,757                    result.failed,758                    entry.value_ptr.roots,759                );760            }761            try result.metrics.merge(entry.value_ptr.metrics);762        }763        result.lifetime = self.lifetime;764        return result;765    }766};767768pub fn writeFromPath(769    allocator: Allocator,770    events_path: []const u8,771    writer: *std.Io.Writer,772    options: Options,773) !void {774    if (options.top == 0 or775        options.frame_limit == 0 or776        options.frame_limit > capture_mod.max_frames_limit)777    {778        return error.InvalidCausalRootReportLimit;779    }780    try options.window.validate();781    var analyzer = Analyzer.init(allocator, options.window);782    defer analyzer.deinit();783    try ingestPath(&analyzer, events_path);784    try analyzer.stack.validate();785786    var inferred_binary: ?[]u8 = null;787    defer if (inferred_binary) |path| allocator.free(path);788    const binary_path = options.binary_path orelse inferred: {789        inferred_binary = try identity_mod.artifactPathAlloc(790            allocator,791            events_path,792        );793        break :inferred inferred_binary.?;794    };795    const actual_digest = identity_mod.fileDigest(796        allocator,797        binary_path,798    ) catch |err| switch (err) {799        error.FileNotFound => return error.MissingExecutableArtifact,800        else => return err,801    };802    const expected_digest = analyzer.stack.executable_digest.?;803    if (!std.mem.eql(u8, &actual_digest, &expected_digest)) {804        return error.ExecutableIdentityMismatch;805    }806    analyzer.finishCausal() catch |err| switch (err) {807        error.DanglingParentOperation => {808            try writeDanglingReport(809                allocator,810                writer,811                &analyzer,812                options,813                binary_path,814                expected_digest,815            );816            return err;817        },818        else => return err,819    };820821    var summaries = try analyzer.collect(options.selection);822    defer summaries.deinit(allocator);823    const totals = try analyzer.totals(options.selection);824    std.mem.sort(Summary, summaries.items, options.sort, summaryGreaterThan);825    const stack_limit = if (options.detail == .full)826        @min(options.top, summaries.items.len)827    else828        0;829    var sources = try collectSources(allocator, &analyzer, summaries.items);830    defer sources.deinit(allocator);831    std.mem.sort(Source, sources.items, options.sort, sourceGreaterThan);832    const source_limit = if (options.detail == .summary)833        0834    else835        @min(options.top, sources.items.len);836    const display = Display{837        .source_groups = sources.items.len,838        .displayed_sources = source_limit,839        .root_stacks = summaries.items.len,840        .displayed_stacks = stack_limit,841    };842    var addresses = try collectAddresses(843        allocator,844        summaries.items[0..stack_limit],845        sources.items[0..source_limit],846        options.frame_limit,847    );848    defer addresses.deinit(allocator);849    var symbols = if (addresses.items.len == 0)850        null851    else852        try symbolize_mod.resolveAlloc(853            allocator,854            binary_path,855            addresses.items,856        );857    defer if (symbols) |*resolved| resolved.deinit(allocator);858    switch (options.format) {859        .text => try writeText(860            writer,861            &analyzer,862            totals,863            options.selection,864            options.sort,865            options.window,866            display,867            sources.items[0..source_limit],868            summaries.items[0..stack_limit],869            symbols,870            options.frame_limit,871            expected_digest,872        ),873        .jsonl => try writeJsonl(874            writer,875            &analyzer,876            totals,877            options.selection,878            options.sort,879            options.window,880            display,881            sources.items[0..source_limit],882            summaries.items[0..stack_limit],883            symbols,884            options.frame_limit,885            expected_digest,886        ),887    }888}889890fn ingestPath(analyzer: *Analyzer, path: []const u8) !void {891    var file = try sys.fs.cwd().openFile(sys.fs.debugIo(), path, .{});892    defer file.close(sys.fs.debugIo());893    var buffer: [64 * 1024]u8 = undefined;894    var reader = file.reader(sys.fs.debugIo(), &buffer);895    while (true) {896        const line = reader.interface.takeDelimiter('\n') catch |err| switch (err) {897            error.ReadFailed => return reader.err.?,898            else => return err,899        };900        const actual = line orelse break;901        try analyzer.ingestJsonLine(actual);902    }903}904905fn writeDanglingReport(906    allocator: Allocator,907    writer: *std.Io.Writer,908    analyzer: *const Analyzer,909    options: Options,910    binary_path: []const u8,911    digest: identity_mod.Digest,912) !void {913    var dangling = try analyzer.collectDangling();914    defer dangling.deinit(allocator);915    const limit = @min(options.top, dangling.items.len);916    var addresses = try collectDanglingAddresses(917        allocator,918        dangling.items[0..limit],919    );920    defer addresses.deinit(allocator);921    var symbols = if (addresses.items.len == 0)922        null923    else924        try symbolize_mod.resolveAlloc(925            allocator,926            binary_path,927            addresses.items,928        );929    defer if (symbols) |*resolved| resolved.deinit(allocator);930    switch (options.format) {931        .text => try writeDanglingText(932            writer,933            analyzer,934            dangling.items[0..limit],935            dangling.items.len,936            symbols,937            digest,938        ),939        .jsonl => try writeDanglingJsonl(940            writer,941            analyzer,942            dangling.items[0..limit],943            dangling.items.len,944            symbols,945            digest,946        ),947    }948}949950fn collectDanglingAddresses(951    allocator: Allocator,952    dangling: []const DanglingParent,953) !std.ArrayListUnmanaged(u64) {954    var seen = std.AutoHashMapUnmanaged(u64, void){};955    defer seen.deinit(allocator);956    var addresses = std.ArrayListUnmanaged(u64).empty;957    errdefer addresses.deinit(allocator);958    try addresses.ensureTotalCapacity(allocator, dangling.len);959    for (dangling) |entry| {960        const address = entry.site_address;961        const result = try seen.getOrPut(allocator, address);962        if (result.found_existing) continue;963        addresses.appendAssumeCapacity(address);964    }965    std.mem.sort(u64, addresses.items, {}, lessThan);966    return addresses;967}968969fn writeDanglingText(970    writer: *std.Io.Writer,971    analyzer: *const Analyzer,972    dangling: []const DanglingParent,973    total: usize,974    symbols: ?symbolize_mod.Symbols,975    digest: identity_mod.Digest,976) !void {977    const digest_hex = std.fmt.bytesToHex(digest, .lower);978    try writer.print(979        "causal_roots_error code=dangling_parent_operation " ++980            "diagnostic_universe=all_memory_operations missing_parents={d} " ++981            "displayed_missing_parents={d} binary_sha256={s}\n",982        .{ total, dangling.len, digest_hex },983    );984    for (dangling) |entry| {985        const child = entry.child;986        try writer.print(987            "dangling_parent missing_parent_operation_id={d} " ++988                "observed_child_operation_id={d} observed_child_sequence={d} " ++989                "observed_child_scope_id={d} observed_child_operation={s} " ++990                "observed_child_layer={s} observed_child_producer={s} " ++991                "observed_child_outcome={s} observed_child_requested_bytes={d} " ++992                "observed_child_stack_id={d} observed_child_scope=",993            .{994                entry.operation_id,995                child.operation_id,996                child.sequence,997                child.scope_id,998                child.kind.tag(),999                child.layer.tag(),1000                @tagName(child.producer),1001                outcomeTag(child.succeeded),1002                child.requested_bytes,1003                child.stack_id,1004            },1005        );1006        const scope = analyzer.stack.scopePath(child.scope_id) orelse "unknown";1007        try pretty_json.writeString(writer, scope);1008        try writeTextAddress(1009            writer,1010            " observed_child_site",1011            entry.site_address,1012            symbols,1013        );1014        try writer.writeByte('\n');1015    }1016}10171018fn writeDanglingJsonl(1019    writer: *std.Io.Writer,1020    analyzer: *const Analyzer,1021    dangling: []const DanglingParent,1022    total: usize,1023    symbols: ?symbolize_mod.Symbols,1024    digest: identity_mod.Digest,1025) !void {1026    var header_stream = pretty_json.Writer.init(writer, .minified);1027    const header = try header_stream.object();1028    try header.field("kind", "causal_root_error");1029    try header.field("code", "dangling_parent_operation");1030    try header.field("diagnostic_universe", "all_memory_operations");1031    try header.field("missing_parents", total);1032    try header.field("displayed_missing_parents", dangling.len);1033    try header.hexString("binary_sha256", &digest);1034    try header.endLine();1035    for (dangling) |entry| {1036        try writeDanglingJsonEntry(writer, analyzer, entry, symbols);1037    }1038}10391040fn writeDanglingJsonEntry(1041    writer: *std.Io.Writer,1042    analyzer: *const Analyzer,1043    entry: DanglingParent,1044    symbols: ?symbolize_mod.Symbols,1045) !void {1046    const child = entry.child;1047    var stream = pretty_json.Writer.init(writer, .minified);1048    const object = try stream.object();1049    try object.field("kind", "causal_root_dangling_parent");1050    try object.field("missing_parent_operation_id", entry.operation_id);1051    try object.field("observed_child_operation_id", child.operation_id);1052    try object.field("observed_child_sequence", child.sequence);1053    try object.field("observed_child_scope_id", child.scope_id);1054    try object.field("observed_child_scope", analyzer.stack.scopePath(1055        child.scope_id,1056    ));1057    try object.field("observed_child_operation", child.kind.tag());1058    try object.field("observed_child_layer", child.layer.tag());1059    try object.field("observed_child_producer", @tagName(child.producer));1060    try object.field("observed_child_succeeded", child.succeeded);1061    try object.field("observed_child_requested_bytes", child.requested_bytes);1062    try object.field("observed_child_stack_id", child.stack_id);1063    const address = entry.site_address;1064    try object.field("observed_child_site_address", address);1065    try writeJsonSymbol(object, "observed_child_site", address, symbols);1066    try object.endLine();1067}10681069fn collectSources(1070    allocator: Allocator,1071    analyzer: *const Analyzer,1072    summaries: []const Summary,1073) !std.ArrayListUnmanaged(Source) {1074    var counts = std.AutoHashMapUnmanaged(SourceKey, Source){};1075    defer counts.deinit(allocator);1076    for (summaries) |summary| {1077        const key = SourceKey{1078            .kind = summary.key.kind,1079            .succeeded = summary.key.succeeded,1080            .layer = summary.key.layer,1081            .producer = summary.key.producer,1082            .site = summary.definition.call_addresses[0],1083            .caller = callerAddress(summary.definition),1084        };1085        const entry = try counts.getOrPut(allocator, key);1086        if (!entry.found_existing) {1087            entry.value_ptr.* = .{1088                .key = key,1089                .counters = .{},1090                .unique_stacks = 0,1091            };1092        }1093        try entry.value_ptr.counters.merge(summary.counters);1094        entry.value_ptr.unique_stacks = try std.math.add(1095            u32,1096            entry.value_ptr.unique_stacks,1097            1,1098        );1099    }1100    var sources = std.ArrayListUnmanaged(Source).empty;1101    errdefer sources.deinit(allocator);1102    try sources.ensureTotalCapacity(allocator, counts.count());1103    var values = counts.valueIterator();1104    while (values.next()) |source| sources.appendAssumeCapacity(source.*);1105    for (sources.items) |*source| {1106        source.counters.lifetime = analyzer.source_lifetimes.get(1107            source.key,1108        ) orelse .{};1109    }1110    return sources;1111}11121113fn collectAddresses(1114    allocator: Allocator,1115    summaries: []const Summary,1116    sources: []const Source,1117    frame_limit: usize,1118) !std.ArrayListUnmanaged(u64) {1119    var seen = std.AutoHashMapUnmanaged(u64, void){};1120    defer seen.deinit(allocator);1121    var addresses = std.ArrayListUnmanaged(u64).empty;1122    errdefer addresses.deinit(allocator);1123    for (sources) |source| {1124        try appendAddress(allocator, &seen, &addresses, source.key.site);1125        if (source.key.caller != 0) {1126            try appendAddress(1127                allocator,1128                &seen,1129                &addresses,1130                source.key.caller,1131            );1132        }1133    }1134    for (summaries) |summary| {1135        const limit = @min(1136            frame_limit,1137            summary.definition.call_addresses.len,1138        );1139        for (summary.definition.call_addresses[0..limit]) |address| {1140            try appendAddress(allocator, &seen, &addresses, address);1141        }1142    }1143    std.mem.sort(u64, addresses.items, {}, lessThan);1144    return addresses;1145}11461147fn appendAddress(1148    allocator: Allocator,1149    seen: *std.AutoHashMapUnmanaged(u64, void),1150    addresses: *std.ArrayListUnmanaged(u64),1151    address: u64,1152) !void {1153    const entry = try seen.getOrPut(allocator, address);1154    if (entry.found_existing) return;1155    try addresses.append(allocator, address);1156}11571158fn callerAddress(definition: analyze_mod.Definition) u64 {1159    const site = definition.call_addresses[0];1160    for (definition.call_addresses[1..], 1..) |address, index| {1161        if (address != site) continue;1162        const caller_index = index + 1;1163        if (caller_index < definition.call_addresses.len) {1164            return definition.call_addresses[caller_index];1165        }1166        return 0;1167    }1168    return 0;1169}11701171fn summaryGreaterThan(sort: Sort, left: Summary, right: Summary) bool {1172    if (counterOrder(sort, left.counters, right.counters)) |order| {1173        return order;1174    }1175    if (left.counters.roots != right.counters.roots) {1176        return left.counters.roots > right.counters.roots;1177    }1178    if (left.counters.root_requested_bytes !=1179        right.counters.root_requested_bytes)1180    {1181        return left.counters.root_requested_bytes >1182            right.counters.root_requested_bytes;1183    }1184    if (left.counters.metrics.operations != right.counters.metrics.operations) {1185        return left.counters.metrics.operations >1186            right.counters.metrics.operations;1187    }1188    return keyLessThan(left.key, right.key);1189}11901191fn sourceGreaterThan(sort: Sort, left: Source, right: Source) bool {1192    if (counterOrder(sort, left.counters, right.counters)) |order| {1193        return order;1194    }1195    if (left.counters.roots != right.counters.roots) {1196        return left.counters.roots > right.counters.roots;1197    }1198    if (left.counters.root_requested_bytes !=1199        right.counters.root_requested_bytes)1200    {1201        return left.counters.root_requested_bytes >1202            right.counters.root_requested_bytes;1203    }1204    if (left.key.site != right.key.site) return left.key.site < right.key.site;1205    if (left.key.caller != right.key.caller) {1206        return left.key.caller < right.key.caller;1207    }1208    return sourceKeyLessThan(left.key, right.key);1209}12101211fn counterOrder(1212    sort: Sort,1213    left: Counters,1214    right: Counters,1215) ?bool {1216    const left_value: u128 = switch (sort) {1217        .roots => left.roots,1218        .requested_bytes => left.root_requested_bytes,1219        .backing_bytes => left.metrics.backing_requested_bytes,1220        .high_water => left.lifetime.high_water_live_bytes,1221    };1222    const right_value: u128 = switch (sort) {1223        .roots => right.roots,1224        .requested_bytes => right.root_requested_bytes,1225        .backing_bytes => right.metrics.backing_requested_bytes,1226        .high_water => right.lifetime.high_water_live_bytes,1227    };1228    if (left_value == right_value) return null;1229    return left_value > right_value;1230}12311232fn keyLessThan(left: RootKey, right: RootKey) bool {1233    if (left.kind != right.kind) {1234        return @backingInt(left.kind) < @backingInt(right.kind);1235    }1236    if (left.layer != right.layer) {1237        return @backingInt(left.layer) < @backingInt(right.layer);1238    }1239    if (left.producer != right.producer) {1240        return @backingInt(left.producer) < @backingInt(right.producer);1241    }1242    if (left.succeeded != right.succeeded) return left.succeeded;1243    return left.stack_id < right.stack_id;1244}12451246fn sourceKeyLessThan(left: SourceKey, right: SourceKey) bool {1247    if (left.kind != right.kind) {1248        return @backingInt(left.kind) < @backingInt(right.kind);1249    }1250    if (left.layer != right.layer) {1251        return @backingInt(left.layer) < @backingInt(right.layer);1252    }1253    if (left.producer != right.producer) {1254        return @backingInt(left.producer) < @backingInt(right.producer);1255    }1256    return left.succeeded and !right.succeeded;1257}12581259fn selectionTag(selection: analyze_mod.Selection) []const u8 {1260    return switch (selection) {1261        .allocations => "allocations",1262        .all => "all",1263    };1264}12651266fn sortTag(sort: Sort) []const u8 {1267    return switch (sort) {1268        .roots => "roots",1269        .requested_bytes => "requested_bytes",1270        .backing_bytes => "backing_bytes",1271        .high_water => "high_water",1272    };1273}12741275fn allocationKey(allocation_id: u64, address: u64) u64 {1276    return if (allocation_id != 0) allocation_id else address;1277}12781279fn outcomeTag(succeeded: bool) []const u8 {1280    return if (succeeded) "success" else "failure";1281}12821283fn requestBytes(event: event_mod.ReplayEvent) usize {1284    return switch (event.kind) {1285        .free, .release, .unmap => event.old_len,1286        .alloc, .resize, .remap, .map, .protect, .discard, .decommit, .advise => event.len,1287        else => unreachable,1288    };1289}12901291fn lessThan(_: void, left: u64, right: u64) bool {1292    return left < right;1293}12941295fn danglingParentLessThan(1296    _: void,1297    left: DanglingParent,1298    right: DanglingParent,1299) bool {1300    if (left.operation_id != right.operation_id) {1301        return left.operation_id < right.operation_id;1302    }1303    if (left.child.sequence != right.child.sequence) {1304        return left.child.sequence < right.child.sequence;1305    }1306    return left.child.operation_id < right.child.operation_id;1307}13081309fn writeText(1310    writer: *std.Io.Writer,1311    analyzer: *const Analyzer,1312    totals: Totals,1313    selection: analyze_mod.Selection,1314    sort: Sort,1315    window: analyze_mod.Window,1316    display: Display,1317    sources: []const Source,1318    summaries: []const Summary,1319    maybe_symbols: ?symbolize_mod.Symbols,1320    frame_limit: usize,1321    digest: identity_mod.Digest,1322) !void {1323    const digest_hex = std.fmt.bytesToHex(digest, .lower);1324    const coverage = analyzer.stack.coverage.?;1325    try writer.print(1326        "causal_roots status={s} universe={s} selection={s} sort={s} " ++1327            "roots={d} " ++1328            "successful={d} failed={d} root_requested_bytes={d} " ++1329            "live_allocations={d} live_bytes={d} " ++1330            "high_water_live_bytes={d} " ++1331            "causal_operations={d} logical_operations={d} " ++1332            "backing_operations={d} physical_operations={d} " ++1333            "backing_requested_bytes={d} physical_requested_bytes={d} " ++1334            "max_depth={d} source_groups={d} displayed_sources={d} " ++1335            "root_stacks={d} displayed_stacks={d} binary_sha256={s}",1336        .{1337            coverage.statusTag(),1338            coverage.universe.tag(),1339            selectionTag(selection),1340            sortTag(sort),1341            totals.roots,1342            totals.successful,1343            totals.failed,1344            totals.root_requested_bytes,1345            totals.lifetime.live_allocations,1346            totals.lifetime.live_bytes,1347            totals.lifetime.high_water_live_bytes,1348            totals.metrics.operations,1349            totals.metrics.logical_operations,1350            totals.metrics.backing_operations,1351            totals.metrics.physical_operations,1352            totals.metrics.backing_requested_bytes,1353            totals.metrics.physical_requested_bytes,1354            totals.metrics.max_depth,1355            display.source_groups,1356            display.displayed_sources,1357            display.root_stacks,1358            display.displayed_stacks,1359            digest_hex,1360        },1361    );1362    try writeTextWindow(writer, window, "root_operation");1363    try writer.writeByte('\n');1364    try writeCoverage(writer, coverage);1365    for (sources) |source| {1366        try writer.print(1367            "root_source layer={s} producer={s} operation={s} outcome={s} " ++1368                "roots={d} root_requested_bytes={d} live_allocations={d} " ++1369                "live_bytes={d} high_water_live_bytes={d} " ++1370                "causal_operations={d} " ++1371                "logical_operations={d} backing_operations={d} " ++1372                "physical_operations={d} backing_requested_bytes={d} " ++1373                "physical_requested_bytes={d} max_depth={d} unique_stacks={d}",1374            .{1375                source.key.layer.tag(),1376                @tagName(source.key.producer),1377                source.key.kind.tag(),1378                outcomeTag(source.key.succeeded),1379                source.counters.roots,1380                source.counters.root_requested_bytes,1381                source.counters.lifetime.live_allocations,1382                source.counters.lifetime.live_bytes,1383                source.counters.lifetime.high_water_live_bytes,1384                source.counters.metrics.operations,1385                source.counters.metrics.logical_operations,1386                source.counters.metrics.backing_operations,1387                source.counters.metrics.physical_operations,1388                source.counters.metrics.backing_requested_bytes,1389                source.counters.metrics.physical_requested_bytes,1390                source.counters.metrics.max_depth,1391                source.unique_stacks,1392            },1393        );1394        try writeTextAddress(1395            writer,1396            " site",1397            source.key.site,1398            maybe_symbols,1399        );1400        if (source.key.caller != 0) {1401            try writeTextAddress(1402                writer,1403                " caller",1404                source.key.caller,1405                maybe_symbols,1406            );1407        } else {1408            try writer.writeAll(" caller=unavailable");1409        }1410        try writer.writeByte('\n');1411    }1412    for (summaries) |summary| {1413        const displayed = @min(1414            frame_limit,1415            summary.definition.call_addresses.len,1416        );1417        try writer.print(1418            "root_stack id={d} layer={s} producer={s} operation={s} " ++1419                "outcome={s} roots={d} root_requested_bytes={d} " ++1420                "live_allocations={d} live_bytes={d} " ++1421                "high_water_live_bytes={d} " ++1422                "causal_operations={d} logical_operations={d} " ++1423                "backing_operations={d} physical_operations={d} " ++1424                "backing_requested_bytes={d} physical_requested_bytes={d} " ++1425                "max_depth={d} captured_frames={d} displayed_frames={d}\n",1426            .{1427                summary.key.stack_id,1428                summary.key.layer.tag(),1429                @tagName(summary.key.producer),1430                summary.key.kind.tag(),1431                outcomeTag(summary.key.succeeded),1432                summary.counters.roots,1433                summary.counters.root_requested_bytes,1434                summary.counters.lifetime.live_allocations,1435                summary.counters.lifetime.live_bytes,1436                summary.counters.lifetime.high_water_live_bytes,1437                summary.counters.metrics.operations,1438                summary.counters.metrics.logical_operations,1439                summary.counters.metrics.backing_operations,1440                summary.counters.metrics.physical_operations,1441                summary.counters.metrics.backing_requested_bytes,1442                summary.counters.metrics.physical_requested_bytes,1443                summary.counters.metrics.max_depth,1444                summary.definition.call_addresses.len,1445                displayed,1446            },1447        );1448        try writeTextFrames(1449            writer,1450            summary.definition,1451            displayed,1452            maybe_symbols,1453        );1454    }1455}14561457fn writeCoverage(1458    writer: *std.Io.Writer,1459    coverage: coverage_mod.Manifest,1460) !void {1461    try writer.print(1462        "coverage child_allocator_fast_paths={s} sys_memory_operations={s} " ++1463            "direct_os_memory_operations={s} unowned_allocator_producers={s} " ++1464            "foreign_allocations={s} observer_control={s} " ++1465            "observer_control_operations={d} zero_length_operations={s} " ++1466            "predispatch_failures={s}\n",1467        .{1468            coverage.child_allocator_fast_paths.tag(),1469            coverage.sys_memory_operations.tag(),1470            coverage.direct_os_memory_operations.tag(),1471            coverage.unowned_allocator_producers.tag(),1472            coverage.foreign_allocations.tag(),1473            coverage.observer_control.tag(),1474            coverage.observer_control_operations,1475            coverage.zero_length_operations.tag(),1476            coverage.predispatch_failures.tag(),1477        },1478    );1479}14801481fn writeTextFrames(1482    writer: *std.Io.Writer,1483    definition: analyze_mod.Definition,1484    displayed: usize,1485    maybe_symbols: ?symbolize_mod.Symbols,1486) !void {1487    for (definition.call_addresses[0..displayed], 0..) |address, frame_index| {1488        const resolved = if (maybe_symbols) |symbols|1489            symbols.find(address)1490        else1491            &.{};1492        try writer.print(1493            "  frame={d} kind={s} call_address=0x{x}",1494            .{1495                frame_index,1496                if (frame_index == 0) "root_site" else "physical",1497                address,1498            },1499        );1500        if (resolved.len != 0) {1501            try writer.writeAll(" function=");1502            try pretty_json.writeString(writer, resolved[0].function);1503            try writer.writeAll(" location=");1504            try pretty_json.writeString(writer, resolved[0].location);1505        }1506        try writer.writeByte('\n');1507        for (resolved[1..], 1..) |inline_frame, inline_index| {1508            try writer.print("    inline={d} function=", .{inline_index});1509            try pretty_json.writeString(writer, inline_frame.function);1510            try writer.writeAll(" location=");1511            try pretty_json.writeString(writer, inline_frame.location);1512            try writer.writeByte('\n');1513        }1514    }1515}15161517fn writeTextAddress(1518    writer: *std.Io.Writer,1519    prefix: []const u8,1520    address: u64,1521    maybe_symbols: ?symbolize_mod.Symbols,1522) !void {1523    try writer.print("{s}_address=0x{x}", .{ prefix, address });1524    const resolved = if (maybe_symbols) |symbols|1525        symbols.find(address)1526    else1527        &.{};1528    if (resolved.len == 0) return;1529    try writer.print("{s}_function=", .{prefix});1530    try pretty_json.writeString(writer, resolved[0].function);1531    try writer.print("{s}_location=", .{prefix});1532    try pretty_json.writeString(writer, resolved[0].location);1533    if (resolved.len == 1) return;1534    const owner = resolved[resolved.len - 1];1535    try writer.print("{s}_owner_function=", .{prefix});1536    try pretty_json.writeString(writer, owner.function);1537    try writer.print("{s}_owner_location=", .{prefix});1538    try pretty_json.writeString(writer, owner.location);1539}15401541fn writeTextWindow(1542    writer: *std.Io.Writer,1543    window: analyze_mod.Window,1544    anchor: []const u8,1545) !void {1546    try writer.writeAll(" window_scope=");1547    if (window.scope) |scope| {1548        try pretty_json.writeString(writer, scope);1549    } else {1550        try writer.writeAll("all");1551    }1552    try writer.writeAll(" window_scope_match=subtree window_first_sequence=");1553    try writeOptionalSequence(writer, window.first_sequence);1554    try writer.writeAll(" window_last_sequence=");1555    try writeOptionalSequence(writer, window.last_sequence);1556    try writer.print(" window_sequence_bounds=inclusive window_anchor={s}", .{1557        anchor,1558    });1559}15601561fn writeOptionalSequence(writer: *std.Io.Writer, sequence: ?u64) !void {1562    if (sequence) |value| {1563        try writer.print("{d}", .{value});1564    } else {1565        try writer.writeAll("all");1566    }1567}15681569fn writeJsonWindow(1570    object: pretty_json.Object,1571    window: analyze_mod.Window,1572    anchor: []const u8,1573) !void {1574    try object.field("window_scope", window.scope);1575    try object.field("window_scope_match", "subtree");1576    try object.field("window_first_sequence", window.first_sequence);1577    try object.field("window_last_sequence", window.last_sequence);1578    try object.field("window_sequence_bounds", "inclusive");1579    try object.field("window_anchor", anchor);1580}15811582fn writeCounterFields(object: pretty_json.Object, counters: anytype) !void {1583    try object.field("roots", counters.roots);1584    try object.field("root_requested_bytes", counters.root_requested_bytes);1585    try object.field("live_allocations", counters.lifetime.live_allocations);1586    try object.field("live_bytes", counters.lifetime.live_bytes);1587    try object.field("high_water_live_bytes", counters.lifetime.high_water_live_bytes);1588    try object.field("causal_operations", counters.metrics.operations);1589    try object.field("logical_operations", counters.metrics.logical_operations);1590    try object.field("backing_operations", counters.metrics.backing_operations);1591    try object.field("physical_operations", counters.metrics.physical_operations);1592    try object.field("backing_requested_bytes", counters.metrics.backing_requested_bytes);1593    try object.field("physical_requested_bytes", counters.metrics.physical_requested_bytes);1594    try object.field("max_depth", counters.metrics.max_depth);1595}15961597fn writeJsonl(1598    writer: *std.Io.Writer,1599    analyzer: *const Analyzer,1600    totals: Totals,1601    selection: analyze_mod.Selection,1602    sort: Sort,1603    window: analyze_mod.Window,1604    display: Display,1605    sources: []const Source,1606    summaries: []const Summary,1607    maybe_symbols: ?symbolize_mod.Symbols,1608    frame_limit: usize,1609    digest: identity_mod.Digest,1610) !void {1611    const coverage = analyzer.stack.coverage.?;1612    var summary_stream = pretty_json.Writer.init(writer, .minified);1613    const header = try summary_stream.object();1614    try header.field("kind", "causal_root_summary");1615    try header.field("status", coverage.statusTag());1616    try header.field("universe", coverage.universe.tag());1617    try header.field("selection", selectionTag(selection));1618    try header.field("sort", sortTag(sort));1619    try header.field("roots", totals.roots);1620    try header.field("successful", totals.successful);1621    try header.field("failed", totals.failed);1622    try header.field("root_requested_bytes", totals.root_requested_bytes);1623    try header.field("live_allocations", totals.lifetime.live_allocations);1624    try header.field("live_bytes", totals.lifetime.live_bytes);1625    try header.field("high_water_live_bytes", totals.lifetime.high_water_live_bytes);1626    try header.field("causal_operations", totals.metrics.operations);1627    try header.field("logical_operations", totals.metrics.logical_operations);1628    try header.field("backing_operations", totals.metrics.backing_operations);1629    try header.field("physical_operations", totals.metrics.physical_operations);1630    try header.field("backing_requested_bytes", totals.metrics.backing_requested_bytes);1631    try header.field("physical_requested_bytes", totals.metrics.physical_requested_bytes);1632    try header.field("max_depth", totals.metrics.max_depth);1633    try header.field("source_groups", display.source_groups);1634    try header.field("displayed_sources", display.displayed_sources);1635    try header.field("root_stacks", display.root_stacks);1636    try header.field("displayed_stacks", display.displayed_stacks);1637    try header.hexString("binary_sha256", &digest);1638    try writeJsonWindow(header, window, "root_operation");1639    try header.field("child_allocator_fast_paths", coverage.child_allocator_fast_paths.tag());1640    try header.field("sys_memory_operations", coverage.sys_memory_operations.tag());1641    try header.field("direct_os_memory_operations", coverage.direct_os_memory_operations.tag());1642    try header.field("unowned_allocator_producers", coverage.unowned_allocator_producers.tag());1643    try header.field("foreign_allocations", coverage.foreign_allocations.tag());1644    try header.field("observer_control", coverage.observer_control.tag());1645    try header.field("observer_control_operations", coverage.observer_control_operations);1646    try header.field("zero_length_operations", coverage.zero_length_operations.tag());1647    try header.field("predispatch_failures", coverage.predispatch_failures.tag());1648    try header.endLine();1649    for (sources) |source| {1650        var stream = pretty_json.Writer.init(writer, .minified);1651        const object = try stream.object();1652        try object.field("kind", "causal_root_source");1653        try object.field("layer", source.key.layer.tag());1654        try object.field("producer", @tagName(source.key.producer));1655        try object.field("operation", source.key.kind.tag());1656        try object.field("succeeded", source.key.succeeded);1657        try writeCounterFields(object, source.counters);1658        try object.field("unique_stacks", source.unique_stacks);1659        try object.field("site_address", source.key.site);1660        const caller_address: ?u64 = if (source.key.caller == 0) null else source.key.caller;1661        try object.field("caller_address", caller_address);1662        try writeJsonSymbol(1663            object,1664            "site",1665            source.key.site,1666            maybe_symbols,1667        );1668        if (source.key.caller != 0) {1669            try writeJsonSymbol(1670                object,1671                "caller",1672                source.key.caller,1673                maybe_symbols,1674            );1675        }1676        try object.endLine();1677    }1678    for (summaries) |summary| {1679        const displayed = @min(1680            frame_limit,1681            summary.definition.call_addresses.len,1682        );1683        var stream = pretty_json.Writer.init(writer, .minified);1684        const object = try stream.object();1685        try object.field("kind", "causal_root_stack");1686        try object.field("stack_id", summary.key.stack_id);1687        try object.field("layer", summary.key.layer.tag());1688        try object.field("producer", @tagName(summary.key.producer));1689        try object.field("operation", summary.key.kind.tag());1690        try object.field("succeeded", summary.key.succeeded);1691        try writeCounterFields(object, summary.counters);1692        try object.field("captured_frames", summary.definition.call_addresses.len);1693        try object.field("displayed_frames", displayed);1694        try object.endLine();1695        for (1696            summary.definition.call_addresses[0..displayed],1697            0..,1698        ) |address, frame_index| {1699            const resolved = if (maybe_symbols) |symbols|1700                symbols.find(address)1701            else1702                &.{};1703            if (resolved.len == 0) {1704                try writeJsonFrame(1705                    writer,1706                    summary.key.stack_id,1707                    frame_index,1708                    address,1709                    0,1710                    "",1711                    "",1712                );1713                continue;1714            }1715            for (resolved, 0..) |inline_frame, inline_index| {1716                try writeJsonFrame(1717                    writer,1718                    summary.key.stack_id,1719                    frame_index,1720                    address,1721                    inline_index,1722                    inline_frame.function,1723                    inline_frame.location,1724                );1725            }1726        }1727    }1728}17291730fn writeJsonSymbol(1731    object: pretty_json.Object,1732    prefix: []const u8,1733    address: u64,1734    maybe_symbols: ?symbolize_mod.Symbols,1735) !void {1736    const resolved = if (maybe_symbols) |symbols|1737        symbols.find(address)1738    else1739        &.{};1740    if (resolved.len == 0) return;1741    try object.fieldParts(&.{ prefix, "_function" }, resolved[0].function);1742    try object.fieldParts(&.{ prefix, "_location" }, resolved[0].location);1743    if (resolved.len == 1) return;1744    const owner = resolved[resolved.len - 1];1745    try object.fieldParts(&.{ prefix, "_owner_function" }, owner.function);1746    try object.fieldParts(&.{ prefix, "_owner_location" }, owner.location);1747}17481749fn writeJsonFrame(1750    writer: *std.Io.Writer,1751    stack_id: u32,1752    frame_index: usize,1753    address: u64,1754    inline_index: usize,1755    function: []const u8,1756    location: []const u8,1757) !void {1758    var stream = pretty_json.Writer.init(writer, .minified);1759    const object = try stream.object();1760    try object.field("kind", "causal_root_stack_frame");1761    try object.field("stack_id", stack_id);1762    try object.field("frame", frame_index);1763    try object.field("frame_kind", if (frame_index == 0) "root_site" else "physical");1764    try object.field("call_address", address);1765    try object.field("inline", inline_index);1766    try object.field("function", function);1767    try object.field("location", location);1768    try object.endLine();1769}17701771fn fixture(analyzer: *Analyzer, dangling: bool) !void {1772    const digest: identity_mod.Digest = @splat(0xaa);1773    var input = std.Io.Writer.Allocating.init(std.testing.allocator);1774    defer input.deinit();1775    try identity_mod.writeMetadata(&input.writer, digest);1776    try coverage_mod.writeMetadata(1777        &input.writer,1778        coverage_mod.ownedProducerManifest(),1779    );1780    var addresses = [_]usize{ 1, 2 };1781    try capture_mod.writeDefinition(&input.writer, 1, .{1782        .addresses = &addresses,1783        .truncated = false,1784        .unwind_failed = false,1785        .missing_return_address = false,1786        .collision_next = 0,1787    });1788    try (event_mod.Event{1789        .seq = 1,1790        .kind = .trace_start,1791    }).writeJsonLine(&input.writer, null, null);1792    try (event_mod.Event{1793        .seq = 2,1794        .kind = .map,1795        .len = 128,1796        .stack_id = 1,1797        .layer = .physical_page,1798        .operation_id = 3,1799        .parent_operation_id = 2,1800        .producer = .sys_memory,1801    }).writeJsonLine(&input.writer, null, null);1802    try (event_mod.Event{1803        .seq = 3,1804        .kind = .alloc,1805        .len = 64,1806        .stack_id = 1,1807        .operation_id = 2,1808        .parent_operation_id = 1,1809    }).writeJsonLine(&input.writer, null, null);1810    if (!dangling) {1811        try (event_mod.Event{1812            .seq = 4,1813            .kind = .alloc,1814            .allocation_id = 1,1815            .address = 4096,1816            .len = 16,1817            .stack_id = 1,1818            .layer = .logical_allocator,1819            .operation_id = 1,1820            .producer = .arena,1821        }).writeJsonLine(&input.writer, null, null);1822        try (event_mod.Event{1823            .seq = 5,1824            .kind = .alloc,1825            .allocation_id = 2,1826            .address = 8192,1827            .len = 32,1828            .stack_id = 1,1829            .layer = .logical_allocator,1830            .operation_id = 4,1831            .producer = .arena,1832        }).writeJsonLine(&input.writer, null, null);1833    }1834    try (event_mod.Event{1835        .seq = if (dangling) 4 else 6,1836        .kind = .trace_stop,1837    }).writeJsonLine(&input.writer, null, null);1838    var lines = std.mem.splitScalar(u8, input.written(), '\n');1839    while (lines.next()) |line| try analyzer.ingestJsonLine(line);1840}18411842test "causal roots collapse nested allocator layers" {1843    var analyzer = Analyzer.init(std.testing.allocator, .{});1844    defer analyzer.deinit();1845    try fixture(&analyzer, false);1846    try analyzer.finish();1847    const totals = try analyzer.totals(.allocations);1848    try std.testing.expectEqual(@as(u64, 2), totals.roots);1849    try std.testing.expectEqual(@as(u128, 48), totals.root_requested_bytes);1850    try std.testing.expectEqual(@as(u64, 4), totals.metrics.operations);1851    try std.testing.expectEqual(@as(u64, 2), totals.metrics.logical_operations);1852    try std.testing.expectEqual(@as(u64, 1), totals.metrics.backing_operations);1853    try std.testing.expectEqual(@as(u64, 1), totals.metrics.physical_operations);1854    try std.testing.expectEqual(@as(u32, 2), totals.metrics.max_depth);1855    try std.testing.expectEqual(@as(u64, 2), totals.lifetime.live_allocations);1856    try std.testing.expectEqual(@as(u128, 48), totals.lifetime.live_bytes);1857    try std.testing.expectEqual(1858        @as(u128, 48),1859        totals.lifetime.high_water_live_bytes,1860    );1861}18621863test "causal roots reject a missing parent operation" {1864    var analyzer = Analyzer.init(std.testing.allocator, .{});1865    defer analyzer.deinit();1866    try fixture(&analyzer, true);1867    try std.testing.expectError(1868        error.DanglingParentOperation,1869        analyzer.finish(),1870    );1871}18721873test "causal roots identify each missing parent through its observed child site" {1874    var analyzer = Analyzer.init(std.testing.allocator, .{});1875    defer analyzer.deinit();1876    try fixture(&analyzer, true);1877    try analyzer.stack.validate();1878    var dangling = try analyzer.collectDangling();1879    defer dangling.deinit(std.testing.allocator);18801881    try std.testing.expectEqual(@as(usize, 1), dangling.items.len);1882    try std.testing.expectEqual(@as(u64, 1), dangling.items[0].operation_id);1883    try std.testing.expectEqual(@as(u64, 2), dangling.items[0].child.operation_id);1884    try std.testing.expectEqual(@as(u64, 1), dangling.items[0].site_address);18851886    var output = std.Io.Writer.Allocating.init(std.testing.allocator);1887    defer output.deinit();1888    const digest: identity_mod.Digest = @splat(0xaa);1889    try writeDanglingText(1890        &output.writer,1891        &analyzer,1892        dangling.items,1893        dangling.items.len,1894        null,1895        digest,1896    );1897    try std.testing.expect(std.mem.indexOf(1898        u8,1899        output.written(),1900        "missing_parent_operation_id=1 observed_child_operation_id=2",1901    ) != null);1902    try std.testing.expect(std.mem.indexOf(1903        u8,1904        output.written(),1905        "observed_child_site_address=0x1",1906    ) != null);1907}19081909test "causal root window anchors a complete tree at its root operation" {1910    var analyzer = Analyzer.init(std.testing.allocator, .{1911        .scope = "root/phase",1912        .first_sequence = 4,1913        .last_sequence = 4,1914    });1915    defer analyzer.deinit();1916    try filteredRootFixture(&analyzer);1917    try analyzer.finish();19181919    const totals = try analyzer.totals(.allocations);1920    try std.testing.expectEqual(@as(u64, 1), totals.roots);1921    try std.testing.expectEqual(@as(u128, 16), totals.root_requested_bytes);1922    try std.testing.expectEqual(@as(u64, 2), totals.metrics.operations);1923    try std.testing.expectEqual(@as(u64, 1), totals.metrics.logical_operations);1924    try std.testing.expectEqual(@as(u64, 1), totals.metrics.backing_operations);1925    try std.testing.expectEqual(@as(u128, 64), totals.metrics.backing_requested_bytes);1926}19271928fn filteredRootFixture(analyzer: *Analyzer) !void {1929    const digest: identity_mod.Digest = @splat(0xaa);1930    var input = std.Io.Writer.Allocating.init(std.testing.allocator);1931    defer input.deinit();1932    try identity_mod.writeMetadata(&input.writer, digest);1933    try coverage_mod.writeMetadata(1934        &input.writer,1935        coverage_mod.ownedProducerManifest(),1936    );1937    var addresses = [_]usize{ 1, 2 };1938    try capture_mod.writeDefinition(&input.writer, 1, .{1939        .addresses = &addresses,1940        .truncated = false,1941        .unwind_failed = false,1942        .missing_return_address = false,1943        .collision_next = 0,1944    });1945    const lines = [_][]const u8{1946        "{\"v\":3,\"seq\":1,\"kind\":\"trace.start\"}",1947        "{\"v\":3,\"seq\":2,\"kind\":\"scope.enter\",\"scope_id\":1," ++1948            "\"scope\":\"root/phase\"}",1949        "{\"v\":3,\"seq\":3,\"kind\":\"alloc\",\"scope_id\":1,\"len\":64," ++1950            "\"stack_id\":1,\"operation_id\":2,\"parent_operation_id\":1}",1951        "{\"v\":3,\"seq\":4,\"kind\":\"alloc\",\"scope_id\":1," ++1952            "\"allocation_id\":1,\"address\":4096,\"len\":16,\"stack_id\":1," ++1953            "\"layer\":\"logical_allocator\",\"operation_id\":1," ++1954            "\"producer\":\"arena\"}",1955        "{\"v\":3,\"seq\":5,\"kind\":\"scope.exit\",\"scope_id\":1}",1956        "{\"v\":3,\"seq\":6,\"kind\":\"scope.enter\",\"scope_id\":2," ++1957            "\"scope\":\"root/other\"}",1958        "{\"v\":3,\"seq\":7,\"kind\":\"alloc\",\"scope_id\":2,\"len\":128," ++1959            "\"stack_id\":1,\"operation_id\":4,\"parent_operation_id\":3}",1960        "{\"v\":3,\"seq\":8,\"kind\":\"alloc\",\"scope_id\":2," ++1961            "\"allocation_id\":2,\"address\":8192,\"len\":32,\"stack_id\":1," ++1962            "\"layer\":\"logical_allocator\",\"operation_id\":3," ++1963            "\"producer\":\"arena\"}",1964        "{\"v\":3,\"seq\":9,\"kind\":\"free\",\"scope_id\":2,\"address\":99," ++1965            "\"len\":8,\"old_len\":8,\"stack_id\":1,\"operation_id\":6," ++1966            "\"parent_operation_id\":5}",1967        "{\"v\":3,\"seq\":10,\"kind\":\"release\",\"scope_id\":2," ++1968            "\"address\":99,\"len\":8,\"old_len\":8,\"stack_id\":1," ++1969            "\"operation_id\":5}",1970        "{\"v\":3,\"seq\":11,\"kind\":\"lifecycle\",\"scope_id\":2," ++1971            "\"return_address\":2,\"operation_id\":5}",1972        "{\"v\":3,\"seq\":12,\"kind\":\"scope.exit\",\"scope_id\":2}",1973        "{\"v\":3,\"seq\":13,\"kind\":\"trace.stop\"}",1974    };1975    var metadata = std.mem.splitScalar(u8, input.written(), '\n');1976    while (metadata.next()) |line| try analyzer.ingestJsonLine(line);1977    for (lines) |line| try analyzer.ingestJsonLine(line);1978}19791980test "causal root source ordering is irreflexive" {1981    const source = Source{1982        .key = .{1983            .kind = .alloc,1984            .succeeded = true,1985            .layer = .logical_allocator,1986            .producer = .arena,1987            .site = 1,1988            .caller = 2,1989        },1990        .counters = .{},1991        .unique_stacks = 1,1992    };1993    try std.testing.expect(!sourceGreaterThan(.high_water, source, source));1994}19951996test "causal root lifetime tracks resize and release" {1997    var lifetime = Lifetime{};1998    try lifetime.allocate(16);1999    try lifetime.resize(16, 40);2000    try lifetime.resize(40, 24);2001    try lifetime.free(24);2002    try std.testing.expectEqual(@as(u64, 0), lifetime.live_allocations);2003    try std.testing.expectEqual(@as(u128, 0), lifetime.live_bytes);2004    try std.testing.expectEqual(2005        @as(u128, 40),2006        lifetime.high_water_live_bytes,2007    );2008}20092010test "causal operation ledger validates contiguous multi-event groups" {2011    var ledger = OperationLedger{};2012    defer ledger.deinit(std.testing.allocator);2013    try ledger.record(std.testing.allocator, 2, 1);2014    try ledger.record(std.testing.allocator, 2, 1);2015    try ledger.record(std.testing.allocator, 1, 0);2016    try ledger.validate();2017    try std.testing.expectEqual(@as(u64, 2), ledger.unique);2018    try std.testing.expectError(2019        error.NonContiguousCausalOperationGroup,2020        ledger.record(std.testing.allocator, 2, 1),2021    );2022}20232024test "causal operation ledger rejects a parent conflict within one group" {2025    var ledger = OperationLedger{};2026    defer ledger.deinit(std.testing.allocator);2027    try ledger.record(std.testing.allocator, 2, 1);2028    try std.testing.expectError(2029        error.CausalOperationParentConflict,2030        ledger.record(std.testing.allocator, 2, 0),2031    );2032}