tiny.profiling.ingest.capacity

1const std = @import("std");2const ingest = @import("root.zig");34const model = ingest.model;5const classify = ingest.classify;67pub const Capacity = struct {8    facts: model.Facts,9    line_bytes: usize,10    row_bits: usize,11    row_bit_bytes: usize,12    json_stack_bytes: usize,13    key_bytes: usize,14    key_entries: usize,15    object_frames: usize,16    key_entries_offset: usize,17    object_frames_offset: usize,18    scratch_bytes: usize,19    working_bytes: usize,2021    pub fn derive(limits: model.Limits) error{CapacityOverflow}!Capacity {22        std.debug.assert(limits.facts.sources.len == model.source_count);23        var line_bytes: usize = 0;24        var row_bits: usize = 0;25        var max_json_depth: usize = 0;26        var max_key_count: usize = 0;27        for (limits.facts.sources, 0..) |source, index| {28            std.debug.assert(index < model.source_count);29            if (source.present) {30                std.debug.assert(source.candidates <= source.lines);31                std.debug.assert(source.max_json_depth <= source.max_line_bytes);32                std.debug.assert(source.max_key_count <= source.max_line_bytes);33            }34            line_bytes = @max(line_bytes, source.max_line_bytes);35            max_json_depth = @max(max_json_depth, source.max_json_depth);36            max_key_count = @max(max_key_count, source.max_key_count);37            if (index < model.ordinary_source_count) {38                row_bits = add(row_bits, source.candidates) catch39                    return error.CapacityOverflow;40            }41        }42        const row_bit_bytes = try bytesForBits(row_bits);43        const json_stack_bytes = try bytesForBits(max_json_depth);44        const key_entries_offset = try alignForward(45            try add(json_stack_bytes, line_bytes),46            @alignOf(classify.KeyEntry),47        );48        const key_entry_bytes = try bytesFor(classify.KeyEntry, max_key_count);49        const object_frames_offset = try alignForward(50            try add(key_entries_offset, key_entry_bytes),51            @alignOf(classify.ObjectFrame),52        );53        const object_frame_bytes = try bytesFor(classify.ObjectFrame, max_json_depth);54        const scratch_bytes = try add(object_frames_offset, object_frame_bytes);55        const working_bytes = try add(try add(line_bytes, row_bit_bytes), scratch_bytes);56        if (row_bits > 0) std.debug.assert(row_bit_bytes <= row_bits);57        if (max_json_depth > 0) std.debug.assert(json_stack_bytes <= max_json_depth);58        if (line_bytes > 0) std.debug.assert(max_key_count <= line_bytes);59        std.debug.assert(key_entries_offset >= json_stack_bytes + line_bytes);60        std.debug.assert(object_frames_offset >= key_entries_offset);61        std.debug.assert(scratch_bytes >= object_frames_offset);62        std.debug.assert(working_bytes >= line_bytes);63        std.debug.assert(working_bytes >= row_bit_bytes);64        std.debug.assert(working_bytes >= scratch_bytes);65        return .{66            .facts = limits.facts,67            .line_bytes = line_bytes,68            .row_bits = row_bits,69            .row_bit_bytes = row_bit_bytes,70            .json_stack_bytes = json_stack_bytes,71            .key_bytes = line_bytes,72            .key_entries = max_key_count,73            .object_frames = max_json_depth,74            .key_entries_offset = key_entries_offset,75            .object_frames_offset = object_frames_offset,76            .scratch_bytes = scratch_bytes,77            .working_bytes = working_bytes,78        };79    }8081    pub fn scratch(82        self: Capacity,83        storage: []align(@alignOf(usize)) u8,84    ) classify.Scratch {85        std.debug.assert(storage.len == self.scratch_bytes);86        std.debug.assert(self.json_stack_bytes + self.key_bytes <= self.key_entries_offset);87        std.debug.assert(self.key_entries_offset <= self.object_frames_offset);88        std.debug.assert(self.object_frames_offset <= self.scratch_bytes);89        const keys_bytes = storage[self.key_entries_offset..self.object_frames_offset];90        const frames_bytes = storage[self.object_frames_offset..self.scratch_bytes];91        const result = classify.Scratch{92            .json_stack = storage[0..self.json_stack_bytes],93            .key_bytes = storage[self.json_stack_bytes..][0..self.key_bytes],94            .keys = std.mem.bytesAsSlice(95                classify.KeyEntry,96                @as([]align(@alignOf(classify.KeyEntry)) u8, @alignCast(keys_bytes)),97            )[0..self.key_entries],98            .objects = std.mem.bytesAsSlice(99                classify.ObjectFrame,100                @as([]align(@alignOf(classify.ObjectFrame)) u8, @alignCast(frames_bytes)),101            )[0..self.object_frames],102        };103        std.debug.assert(result.json_stack.len == self.json_stack_bytes);104        std.debug.assert(result.key_bytes.len == self.key_bytes);105        std.debug.assert(result.keys.len == self.key_entries);106        std.debug.assert(result.objects.len == self.object_frames);107        return result;108    }109};110111fn bytesForBits(bits: usize) error{CapacityOverflow}!usize {112    const whole = bits / 8;113    std.debug.assert(whole <= bits);114    if (bits % 8 == 0) return whole;115    return add(whole, 1);116}117118fn add(left: usize, right: usize) error{CapacityOverflow}!usize {119    return std.math.add(usize, left, right) catch error.CapacityOverflow;120}121122fn bytesFor(comptime T: type, count: usize) error{CapacityOverflow}!usize {123    std.debug.assert(@sizeOf(T) > 0);124    return std.math.mul(usize, @sizeOf(T), count) catch error.CapacityOverflow;125}126127fn alignForward(value: usize, alignment: usize) error{CapacityOverflow}!usize {128    std.debug.assert(std.math.isPowerOfTwo(alignment));129    const mask = alignment - 1;130    const rounded = try add(value, mask);131    return rounded & ~mask;132}133134fn modelIngestionWorkingBytes(facts: model.Facts) u128 {135    var line_bytes: u128 = 0;136    var row_bits: u128 = 0;137    var json_depth: u128 = 0;138    var key_count: u128 = 0;139    for (facts.sources, 0..) |source, index| {140        line_bytes = @max(line_bytes, source.max_line_bytes);141        json_depth = @max(json_depth, source.max_json_depth);142        key_count = @max(key_count, source.max_key_count);143        if (index < model.ordinary_source_count) row_bits += source.candidates;144    }145    const row_bytes = (row_bits + 7) / 8;146    const stack_bytes = (json_depth + 7) / 8;147    const key_offset = modelAlign(stack_bytes + line_bytes, @alignOf(classify.KeyEntry));148    const frame_offset = modelAlign(149        key_offset + key_count * @sizeOf(classify.KeyEntry),150        @alignOf(classify.ObjectFrame),151    );152    const scratch_bytes = frame_offset + json_depth * @sizeOf(classify.ObjectFrame);153    return line_bytes + row_bytes + scratch_bytes;154}155156fn modelAlign(value: u128, alignment: u128) u128 {157    std.debug.assert(std.math.isPowerOfTwo(alignment));158    return (value + alignment - 1) & ~(alignment - 1);159}160161test "ingestion capacity matches an independent bit and scratch model" {162    comptime {163        @stardustClaim(164            @import("alloc_phase").capacity.witness(@import("./root.zig").ArtifactIngestion, "profiling_ingestion_capacity_capacity_model"),165            null,166            null,167            null,168            null,169            null,170            null,171        );172    }173    comptime {174        @stardustClaim(175            @import("alloc_phase").capacity.witness(@import("./root.zig").ArtifactIngestion, "profiling_ingestion_capacity_overload"),176            null,177            null,178            null,179            null,180            null,181            null,182        );183    }184185    var facts = model.Facts{ .sources = @splat(.{}) };186    facts.sources[0].candidates = 9;187    facts.sources[0].max_line_bytes = 41;188    facts.sources[0].max_json_depth = 8;189    facts.sources[0].max_key_count = 3;190    facts.sources[1].candidates = 7;191    facts.sources[1].max_line_bytes = 17;192    facts.sources[1].max_json_depth = 9;193    const capacity = try Capacity.derive(.{ .paths = undefined, .facts = facts });194    try std.testing.expectEqual(@as(usize, 16), capacity.row_bits);195    try std.testing.expectEqual(@as(usize, 2), capacity.row_bit_bytes);196    try std.testing.expectEqual(@as(usize, 2), capacity.json_stack_bytes);197    try std.testing.expectEqual(@as(usize, 41), capacity.line_bytes);198    try std.testing.expectEqual(@as(usize, 3), capacity.key_entries);199    try std.testing.expectEqual(@as(usize, 9), capacity.object_frames);200    try std.testing.expect(capacity.scratch_bytes >= 43);201    try std.testing.expectEqual(202        capacity.line_bytes + capacity.row_bit_bytes + capacity.scratch_bytes,203        capacity.working_bytes,204    );205    try std.testing.expectEqual(206        modelIngestionWorkingBytes(facts),207        capacity.working_bytes,208    );209}210211test "ingestion capacity rejects unrepresentable candidate storage" {212    var facts = model.Facts{ .sources = @splat(.{}) };213    facts.sources[0].candidates = std.math.maxInt(usize);214    facts.sources[1].candidates = 1;215    try std.testing.expectError(216        error.CapacityOverflow,217        Capacity.derive(.{ .paths = undefined, .facts = facts }),218    );219}

1pub const capacity = @import("capacity.zig");