Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

Ядро на своей машине: таймер, вытеснение и маска прерываний

lead~150 мин

открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

Ядро на своей машине: таймер, вытеснение и маска прерываний

За три прошлых урока машина Y86 обросла почти всем, что нужно операционной системе. В уроке про исключения у неё появились бит привилегий, таблица исключений, инструкции trap и iret и первый системный вызов write. В уроке про процессы ядро научилось держать два процесса: контекст каждого лежит в PCB, а переключаются они по вызову yield, то есть по доброй воле. В уроке про сигналы ты увидел, как асинхронное событие врывается в программу между двумя любыми инструкциями, почему обработчику нужна маска и как второй сигнал того же типа пропадает, пока первый ждёт. Сегодня эти три линии сходятся в одной точке. Мы подключим к машине таймер, и процесс, который не собирается никому уступать, будет снят с процессора силой. Ядро на ассемблере Y86 соберём своим ассемблером из урока 21, прогоним на своём симуляторе из урока 22 и снимем трассу, которая повторяется такт в такт. А потом выключим маску прерываний и посмотрим, как ядро восстанавливает процесс из собственного кода и падает.

Цели урока

Понимать, чем вытесняющая многозадачность отличается от кооперативной и почему без таймера ядро не хозяин на машине.
Написать таймер как устройство: счётчик тактов, линия запроса в один бит, счёт потерянных тиков.
Знать, в какой момент такта процессор принимает прерывание, какой адрес возврата кладёт в кадр и почему прерванный процесс ничего не замечает.
Прочитать ядро на ассемблере Y86 целиком: три входа из таблицы исключений, сохранение контекста прямо в PCB, разбор причины, планировщик по кругу, восстановление и iret.
Снимать детерминированную трассу двух процессов при заданном периоде таймера и объяснять в ней каждое переключение.
Считать цену переключения в тактах и видеть, как короткий период превращает машину в обработчик прерываний, который ничего не успевает.
Воспроизвести гонку без маски прерываний: оборванный write, испорченный PCB, падение ядра. Связать её с гонками в обработчиках сигналов.

Кто хозяин на машине

Вспомни, чем кончился урок про процессы. Ядро yield.ys держит два PCB, процессы ping и pong печатают по слову и зовут yield, ядро переключает их по кругу. Схема работает, пока оба процесса вежливы. Это кооперативная многозадачность: процессор переходит из рук в руки только тогда, когда текущий владелец сам его отдаёт.

Теперь представь процесс, который yield не зовёт. Не обязательно злонамеренный: достаточно цикла с ошибкой в условии. Вот такой процесс, только без ошибки, он просто занят своим делом:

# Процесс tick: три раза печатает своё слово, между ними считает впустую.
# Процессор он не уступает: его вытесняет таймер.

        .pos 0x400
        irmovq $3, %rbx
loop:   irmovq $1, %rax         # write(word, 5)
        irmovq word, %rdi
        irmovq $5, %rsi
        trap
        irmovq $20, %rcx        # пустой цикл: сорок инструкций работы
spin:   iaddq $-1, %rcx
        jne spin
        iaddq $-1, %rbx
        jne loop
        irmovq $60, %rax        # exit
        trap

        .align 8
word:   .quad 0x0a6b636974        # "tick\n", младший байт первым

Три раза напечатать слово, между печатью покрутить пустой цикл на двадцать оборотов, в конце exit. Системные вызовы с теми же номерами, что в Linux на x86-64: write это 1, exit это 60, номер в %rax, аргументы в %rdi и %rsi. Строка tick\n лежит одним словом .quad: байты идут от младшего к старшему, 0x74 это t, 0x0a в пятом байте это перевод строки.

Второй процесс, tock.ys, отличается двумя строками: он собран с адреса 0x800 и печатает другое слово.

# Процесс tock: три раза печатает своё слово, между ними считает впустую.
# Процессор он не уступает: его вытесняет таймер.

        .pos 0x800
        irmovq $3, %rbx
loop:   irmovq $1, %rax         # write(word, 5)
        irmovq word, %rdi
        irmovq $5, %rsi
        trap
        irmovq $20, %rcx        # пустой цикл: сорок инструкций работы
spin:   iaddq $-1, %rcx
        jne spin
        iaddq $-1, %rbx
        jne loop
        irmovq $60, %rax        # exit
        trap

        .align 8
word:   .quad 0x0a6b636f74        # "tock\n", младший байт первым

Запусти эту пару под ядром из прошлого урока, и получишь ровно то, чего следовало ждать:

tick
tick
tick
tock
tock
tock

tock не получил ни одного такта, пока tick не закончился сам. В ядро tick заходил трижды, на каждом write, но ядро после write честно возвращало его обратно: причин переключаться у него не было. Если бы tick крутился вечно, tock не запустился бы никогда, и ядро ничего не смогло бы с этим сделать. Оно вообще не исполняется, пока процесс не позовёт его сам. Ядро, которое получает управление только по приглашению, на машине не хозяин.

Нужен способ вернуть управление ядру без согласия процесса. В железе такой способ один: прерывание от устройства. Из четырёх классов исключений в таблице урока 47 три у нас уже работают: системный вызов (trap), сбой (adr, ins) и аварийный останов. Не хватает четвёртого, единственного асинхронного. Строка для него в таблице исключений заведена с самого начала, причина номер три, timer. Осталось сделать устройство, которое будет в неё стрелять.

Схема, в которой ядро отбирает процессор по таймеру, называется вытесняющей многозадачностью. На ней стоят Linux, macOS, Windows NT и все, кого ты встретишь в работе. Кооперативная схема при этом никуда не делась: она живёт этажом выше, в event loop браузера и Node.js, в сопрограммах, в планировщике горутин до Go 1.14 (там вытеснение по сигналу SIGURG добавили как раз потому, что плотный цикл без вызовов функций вешал сборщик мусора). Проблема у всех одна и та же, та самая, что у tick и tock.

Таймер как устройство

Настоящий таймер это счётчик, который тактируется кварцем и по достижении нуля дёргает линию прерывания. В первом IBM PC стояла микросхема Intel 8253 (потом 8254): генератор на 1,193182 МГц, шестнадцатибитный делитель, и с делителем по умолчанию 65536 получались знаменитые 18,2 прерывания в секунду, по которым DOS вёл часы. Сегодня таймер сидит внутри процессора. У x86-64 это таймер локального APIC, свой на каждое ядро, в режиме TSC-deadline: ядро ОС записывает в регистр MSR момент, когда хочет прерывание, и процессор сравнивает его со счётчиком тактов. У ARM, включая Apple Silicon, это generic timer с регистрами CNTP_TVAL_EL0 и CNTP_CTL_EL0. Суть за сорок пять лет не поменялась: счётчик, сравнение, линия.

Как часто тикать, решает ядро. В Linux это константа сборки CONFIG_HZ: варианты 100, 250, 300 и 1000 прерываний в секунду, у большинства настольных дистрибутивов 250 или 1000. Посмотреть у себя: grep 'CONFIG_HZ=' /boot/config-$(uname -r). Не путай её с тем, что отвечает getconf CLK_TCK: там всегда 100, это единица измерения для times(), зафиксированная ради совместимости, а не частота таймера. С 2007 года ядро умеет не тикать на простаивающем процессоре (NO_HZ_IDLE), а с версии 3.10 и на процессоре, где крутится ровно одна задача (NO_HZ_FULL): прерывание, которое ничего не решает, только будит процессор и греет батарею.

Наш таймер проще некуда: он считает такты машины и раз в period тактов поднимает линию. Весь файл вместе с тестом:

//! Таймер: устройство, которое раз в `period` тактов поднимает линию прерывания.
//!
//! Линия это один бит в состоянии процессора, очереди за ней нет. Если прошлый
//! запрос ещё не принят (ядро сидит под маской дольше периода), новый тик
//! ничего не добавляет и пропадает. Таймер такие тики считает.

const std = @import("std");

pub const Tick = enum {
    /// Период ещё не истёк или таймер выключен.
    idle,
    /// Линия поднята.
    raised,
    /// Период истёк, а прошлый запрос так и висит: тик потерян.
    lost,
};

pub const Timer = struct {
    /// Тактов между прерываниями. Ноль выключает таймер.
    period: usize = 0,
    count: usize = 0,
    raised: usize = 0,
    lost: usize = 0,

    /// Один такт машины. `irq` это линия запроса в состоянии процессора.
    pub fn tick(self: *Timer, irq: *bool) Tick {
        if (self.period == 0) return .idle;
        self.count += 1;
        if (self.count < self.period) return .idle;
        self.count = 0;
        if (irq.*) {
            self.lost += 1;
            return .lost;
        }
        irq.* = true;
        self.raised += 1;
        return .raised;
    }
};

test "таймер поднимает линию раз в период, второй запрос поверх первого теряется" {
    var timer: Timer = .{ .period = 3 };
    var irq = false;
    try std.testing.expectEqual(Tick.idle, timer.tick(&irq));
    try std.testing.expectEqual(Tick.idle, timer.tick(&irq));
    try std.testing.expectEqual(Tick.raised, timer.tick(&irq));
    try std.testing.expect(irq);

    // Процессор линию не опустил: следующий период уходит в потери.
    for (0..2) |_| _ = timer.tick(&irq);
    try std.testing.expectEqual(Tick.lost, timer.tick(&irq));
    try std.testing.expectEqual(@as(usize, 1), timer.raised);
    try std.testing.expectEqual(@as(usize, 1), timer.lost);
}

В этом файле два решения, и оба взяты из настоящего железа.

Первое: таймер не вызывает обработчик и вообще ничего не знает про процессор. Он поднимает линию irq, то есть ставит один бит, и на этом его работа кончена. Когда и как на этот бит отреагировать, решает процессор. Устройство и процессор развязаны одной булевой переменной, как на плате они развязаны одним проводом.

Второе: линия это один бит, а не счётчик. Если прошлый запрос ещё висит, потому что процессор сидит с запрещёнными прерываниями дольше периода, новый тик ничего не добавляет. Поднять уже поднятую линию нельзя. Таймер такие тики считает в lost, но только для нас с тобой: у настоящего железа такого счётчика нет, и ядро о потере не узнает.

Это та же самая арифметика, что у сигналов. В уроке про сигналы ожидающие сигналы процесса хранились битовой маской, по биту на тип, и второй SIGCHLD поверх ещё не доставленного первого пропадал. Отсюда правило: обработчик SIGCHLD собирает waitpid в цикле, потому что один сигнал значит “как минимум один ребёнок”, а не “ровно один”. С прерыванием таймера то же: одно прерывание значит “прошло как минимум period тактов”. Старые ядра Linux вели часы подсчётом тиков и при потерях отставали, в журнале появлялось Losing some ticks... checking if CPU frequency changed, а в виртуальных машинах нулевых годов часы гостя убегали на минуты в сутки. Лечится это так же, как с waitpid: не считать события, а спрашивать источник истины. Современное ядро в обработчике тика читает аппаратный счётчик (TSC, HPET) и узнаёт, сколько времени прошло на самом деле.

Прерывание со стороны процессора

Таймер поднял линию. Что делает процессор? В уроке 47 весь вход в ядро уже написан: handleTrap в src/sim/trap.zig кладёт кадр из трёх слов (адрес возврата, слово состояния, прежний %rsp), переключает машину в режим ядра и прыгает по адресу из таблицы. Прерыванию нужен тот же механизм, меняется только то, кто и когда его запускает. Правок в процессоре четыре, все маленькие.

В состоянии машины появляются два поля: сама линия и переключатель, который пригодится нам в конце урока.

    /// Прерывания разрешены. После сброса запрещены: ядру сперва надо встать.
    ie: bool = false,
    /// Линия запроса прерывания. Её поднимает таймер, опускает процессор,
    /// когда прерывание принято. Бит один: второй запрос поверх первого пропадает.
    irq: bool = false,
    /// Сбрасывает ли железо `ie` при входе в обработчик. Выключают это только
    /// затем, чтобы посмотреть на прерывание внутри обработчика.
    mask_on_entry: bool = true,

Поле ie у тебя уже есть: это бит разрешения прерываний из слова состояния, четвёртый по счёту. До сегодняшнего дня он ложился в кадр и возвращался из кадра без всякой пользы, потому что разрешать было нечего. После сброса прерывания запрещены. Это важно: ядро стартует с адреса 0, и до первого iret его никто не потревожит, даже если таймер уже тикает.

В handleTrap одна строка получает условие. Раньше железо гасило ie безусловно, теперь смотрит на переключатель:

    st.set(.rsp, frame);
    st.user = false;
    if (st.mask_on_entry) st.ie = false;
    st.pc = vector;
    return .{ .cause = cause, .epc = return_pc, .vector = vector };

И главное, в cpu.zig появляется функция, которая решает, принять ли прерывание, и step зовёт её первой:

/// Прерывание принимается между инструкциями: линия поднята и прерывания
/// разрешены. Адрес возврата это инструкция, которая не успела начаться.
fn acceptInterrupt(st: *State) ?trap.Entry {
    if (!st.irq or !st.ie) return null;
    st.irq = false;
    return trap.handleTrap(st, .timer, st.pc);
}

/// Один такт: шесть этапов подряд над одним набором проводов. До них машина
/// смотрит на линию прерывания, после них разбирается с исключением.
pub fn step(st: *State) Retired {
    const irq = acceptInterrupt(st);
    const pc = st.pc;
    const user = st.user;
    var s: Signals = .{};

    fetch(st, &s);
    decode(st, &s);
    execute(st, &s);
    memory(st, &s);
    writeback(st, &s);
    pcUpdate(st, &s);

    const stat = s.stat;
    const exc = raise(st, &s);
    st.stat = s.stat;
    return .{
        .pc = pc,
        .icode = s.icode,
        .ifun = s.ifun,
        .stat = if (exc != null) stat else s.stat,
        .user = user,
        .irq = irq,
        .exc = exc,
        .out = s.out,
    };
}

Посмотри на порядок внутри step. Проверка линии стоит до выборки, а не после записи и не посередине. Прерывание принимается на границе между инструкциями: предыдущая отработала целиком, следующая ещё не начиналась. Адрес возврата это st.pc на момент проверки, то есть адрес той инструкции, которая не успела начаться. Сравни с двумя другими случаями, они рядом в функции raise из урока 47: у trap адрес возврата это следующая инструкция (вызов состоялся, повторять его не надо), у сбоя это сама сбойная (ядро может починить причину и дать ей вторую попытку, этим мы воспользуемся в уроке про отображение памяти). Три класса исключений из таблицы книги в железе отличаются одним числом, которое ложится в кадр.

Почему на границе, а не когда придётся? Потому что тогда состояние машины в момент входа в обработчик всегда объяснимо: все инструкции до адреса возврата выполнены полностью, ни одна после него не начата. Это называется точными исключениями, и для нашей последовательной машины оно бесплатное. Для конвейера из урока 30 оно стоит дорого: в момент прерывания в пяти стадиях сидят пять недоделанных инструкций, и процессор обязан довести до конца те, что старше точки прерывания, и выбросить те, что младше, теми же пузырьками, которыми он выбрасывает инструкции после неверно предсказанного перехода. В процессоре с внеочередным исполнением этим занимается отдельный блок, буфер переупорядочивания.

Заметь ещё две вещи. Принятое прерывание опускает линию (st.irq = false): запрос обслужен, следующий тик сможет поднять её снова. И прерывание не занимает такт: после acceptInterrupt тот же вызов step исполняет уже первую инструкцию обработчика. В трассе строка irq стоит перед строкой инструкции, а pc в Retired это уже адрес обработчика.

Прерванному процессу всё это незаметно. Его PC, флаги и %rsp лежат в кадре, остальные четырнадцать регистров сохранит ядро, и после iret он продолжит с той же инструкции с теми же значениями. Единственное, что он мог бы заметить, это время: между двумя его соседними инструкциями прошло несколько сотен тактов. Процессы, которым это важно, так и ловят вытеснение: читают счётчик времени в цикле и смотрят на скачки.

Вспомни стек на ощупь

Сохранение контекста у нас это четырнадцать pushq подряд, восстановление это четырнадцать popq. Если подзабыл, как эта пара двигает %rsp, вернись на минуту к машине из урока 22 и пройди по шагам программу push_pop_rsp. В ядре ровно эти инструкции будут писать не в стек, а в PCB: для железа разницы нет, %rsp это просто адрес, куда ляжет следующее слово. Ту же машину, но уже с ядром, таймером и двумя процессами, ты покрутишь ниже, когда разберём трассы.

Таймер на плате

Процессор и таймер соединяет Computer из урока 47. Там он подключал к процессору консоль и писал трассу второй версии, теперь к ним добавляется таймер. Файл небольшой, и таймер в нём задевает почти каждую функцию, так что вот он целиком:

//! Компьютер: процессор, таймер и консоль на одной плате.
//!
//! `cpu.step` умеет исключения, но не знает, откуда берутся прерывания и куда
//! деваются байты из порта вывода. Здесь к процессору подключены устройства,
//! и здесь же пишется трасса версии 2. Порядок событий в такте:
//!
//!   1. процессор принимает прерывание, если линия поднята и они разрешены;
//!   2. исполняется одна инструкция, возможно с исключением в конце;
//!   3. тикает таймер.
//!
//! Строки трассы:
//!
//!   irq timer 0x412 -> 0x040    прерывание принято, адрес возврата и обработчик
//!   U 0x400 30 AOK              режим, адрес, icode и ifun, код состояния инструкции
//!   out 68                      байт ушёл на консоль
//!   exc trap 0x415 -> 0x010     инструкция закончилась исключением
//!   lost timer                  тик пропал: прошлый запрос ещё не принят
//!   halt cycles=120             дальше пятнадцать регистров, как в версии 1
//!   timer raised=3 lost=0       счётчики таймера, если он был включён

const std = @import("std");

const cpu = @import("cpu.zig");
const isa = @import("../isa.zig");
const state = @import("state.zig");
const trace = @import("trace.zig");
const trap = @import("trap.zig");

const State = state.State;
const Timer = @import("timer.zig").Timer;
const Writer = std.Io.Writer;

pub const Config = struct {
    /// Период таймера в тактах. Ноль: таймера нет.
    timer_period: usize = 0,
    /// Маскирует ли железо прерывания при входе в обработчик.
    mask: bool = true,
    /// Печатать только события, без строк инструкций.
    events_only: bool = false,
    max_steps: usize = 100_000,
};

pub const Summary = struct {
    cycles: usize,
    stat: isa.Stat,
    hit_limit: bool,
    raised: usize,
    lost: usize,
};

pub const Computer = struct {
    st: State = .init(),
    timer: Timer,
    config: Config,
    /// Куда писать трассу и куда консоль. null: не писать.
    trace_out: ?*Writer = null,
    console: ?*Writer = null,
    cycles: usize = 0,

    pub fn init(config: Config) Computer {
        var self: Computer = .{ .timer = .{ .period = config.timer_period }, .config = config };
        self.st.mask_on_entry = config.mask;
        return self;
    }

    /// Накладывает образ на память: ненулевые байты образа ложатся поверх.
    /// Так в одну память попадают ядро и программы, собранные по отдельности.
    pub fn load(self: *Computer, image: []const u8) void {
        for (image, 0..) |byte, at| {
            if (byte != 0 and at < isa.mem_size) self.st.mem[at] = byte;
        }
    }

    pub fn step(self: *Computer) Writer.Error!void {
        const r = cpu.step(&self.st);
        self.cycles += 1;
        try self.record(r);
        if (self.timer.tick(&self.st.irq) == .lost) {
            if (self.trace_out) |w| try w.writeAll("lost timer\n");
        }
    }

    pub fn run(self: *Computer) Writer.Error!Summary {
        while (self.st.stat == .aok and self.cycles < self.config.max_steps) try self.step();
        if (self.trace_out) |w| {
            try w.print("halt cycles={d}\n", .{self.cycles});
            try trace.writeRegisters(w, &self.st);
            if (self.timer.period != 0) {
                try w.print("timer raised={d} lost={d}\n", .{ self.timer.raised, self.timer.lost });
            }
        }
        return .{
            .cycles = self.cycles,
            .stat = self.st.stat,
            .hit_limit = self.st.stat == .aok,
            .raised = self.timer.raised,
            .lost = self.timer.lost,
        };
    }

    fn record(self: *Computer, r: cpu.Retired) Writer.Error!void {
        if (r.out) |byte| {
            if (self.console) |c| try c.writeByte(byte);
        }
        const w = self.trace_out orelse return;
        if (r.irq) |e| try writeEntry(w, "irq", e);
        if (!self.config.events_only) {
            try w.print("{c} 0x{x:0>3} {x}{x} {s}\n", .{
                @as(u8, if (r.user) 'U' else 'K'),
                r.pc,
                @intFromEnum(r.icode),
                r.ifun,
                r.stat.name(),
            });
        }
        if (r.out) |byte| try w.print("out {x:0>2}\n", .{byte});
        if (r.exc) |e| try writeEntry(w, "exc", e);
    }
};

fn writeEntry(w: *Writer, kind: []const u8, e: trap.Entry) Writer.Error!void {
    try w.print("{s} {s} 0x{x:0>3} -> 0x{x:0>3}\n", .{ kind, e.cause.name(), e.epc, e.vector });
}

/// Результат прогона текстом: трасса и то, что появилось на консоли.
pub const Output = struct {
    trace: []u8,
    console: []u8,
    summary: Summary,

    pub fn deinit(self: *Output, gpa: std.mem.Allocator) void {
        gpa.free(self.trace);
        gpa.free(self.console);
        self.* = undefined;
    }
};

/// Накладывает образы, прогоняет машину и возвращает трассу с консолью.
pub fn runImages(gpa: std.mem.Allocator, images: []const []const u8, config: Config) std.mem.Allocator.Error!Output {
    var trace_buf: Writer.Allocating = .init(gpa);
    defer trace_buf.deinit();
    var console_buf: Writer.Allocating = .init(gpa);
    defer console_buf.deinit();

    var computer: Computer = .init(config);
    computer.trace_out = &trace_buf.writer;
    computer.console = &console_buf.writer;
    for (images) |image| computer.load(image);
    const summary = computer.run() catch return error.OutOfMemory;

    const trace_text = try trace_buf.toOwnedSlice();
    errdefer gpa.free(trace_text);
    return .{ .trace = trace_text, .console = try console_buf.toOwnedSlice(), .summary = summary };
}

Порядок в step выбран не случайно: сначала процессор (внутри него проверка линии, потом инструкция), потом тик таймера. Значит, линия, поднятая на такте N, будет замечена в начале такта N + 1. При периоде 150 первое прерывание примется перед сто пятьдесят первой инструкцией. Поменяй порядок местами, и все адреса в трассах сдвинутся на инструкцию. Ни один из вариантов не правильнее другого, но выбрать надо один и навсегда: на детерминизме этой трассы стоят тесты.

Computer остаётся единственным местом, которое что-то печатает. Процессор возвращает Retired с полями irq, exc, out, таймер возвращает Tick, а в строки их превращает record. Поэтому cpu.zig и timer.zig тестируются без всякого вывода, а формат трассы меняется в одном файле.

В main.zig команда kernel получает два ключа, они кладут значения в Config:

        if (std.mem.eql(u8, arg, "--no-mask")) {
            config.mask = false;
        } else if (std.mem.eql(u8, arg, "--events")) {
            config.events_only = true;
        } else if (std.mem.eql(u8, arg, "--console")) {
            console_only = true;
        } else if (std.mem.eql(u8, arg, "--timer")) {
            i += 1;
            if (i == args.len) {
                try cli.err.writeAll("у ключа --timer нет значения\n");
                return error.BadUsage;
            }
            config.timer_period = std.fmt.parseInt(usize, args[i], 10) catch {
                try cli.err.print("период таймера это число тактов, а не {s}\n", .{args[i]});
                return error.BadUsage;
            };

И регистрация нового: в src/root.zig строка pub const timer = @import("sim/timer.zig");, в src/programs.zig три новых имени, в build.zig номер шага, три программы и образцы трасс.

    /// Ядро целиком: то же плюс таймер.
    pub const full = @embedFile("kernel.ys");
    pub const ping = @embedFile("ping.ys");
    pub const pong = @embedFile("pong.ys");
    pub const tick = @embedFile("tick.ys");
    pub const tock = @embedFile("tock.ys");
    pub const crash = @embedFile("crash.ys");

const steps = [_][]const u8{ "20", "21", "22", "23", "24", "25", "26", "27", "29", "30", "39", "47", "48", "50" };

const kernel_programs = [_][]const u8{ "hello", "yield", "kernel", "ping", "pong", "tick", "tock", "crash" };

/// Образцы трасс машины с ядром, лежат в `tests/expected/`.
const kernel_traces = [_][]const u8{
    "kernel_150.events",
    "kernel_150.trace",
    "kernel_150_nomask.events",
};

Образцы из tests/expected/ попадают в тесты так же, как программы попадают в модуль: анонимным импортом, чтобы @embedFile("kernel_150.trace") нашёл файл за границей каталога с тестом. В цикле по шагам, рядом с остальными импортами теста:

            for (kernel_traces) |name| {
                tests.root_module.addAnonymousImport(name, .{
                    .root_source_file = b.path(b.fmt("tests/expected/{s}", .{name})),
                });
            }

Железо готово. Обрати внимание, как мало его понадобилось: одно устройство на пятьдесят строк, два поля в состоянии, одна функция на пять строк в процессоре. Вся остальная сложность вытесняющей многозадачности живёт в ядре.

Шаг проекта: ядро целиком

Новое ядро kernel.ys вырастает из yield.ys прошлого урока. Отличий по существу три: третий вход в таблице исключений, ветка “причина равна трём” в разборе и комментарий про маску. Но это главный файл всего блока, так что прочитаем его целиком, сверху вниз, а не разницей.

# Ядро целиком: два процесса, вытесняющая многозадачность по таймеру,
# системные вызовы write, yield и exit.
#
# Контекст процесса лежит в PCB: четырнадцать регистров, потом кадр
# исключения (PC, слово состояния, %rsp), потом два поля ядра.
#
#   0x00 %r14 ... 0x60 %rcx, 0x68 %rax     регистры, в порядке обратном pushq
#   0x70 PC    0x78 состояние    0x80 %rsp  кадр, его кладёт железо
#   0x88 жив ли процесс          0x90 следующий PCB по кругу
#
# Слово ksp в таблице исключений всегда смотрит на смещение 0x88 текущего
# PCB. Поэтому кадр железо кладёт прямо в PCB, а ядро дописывает под него
# регистры обычными pushq. Копировать ничего не надо.
#
# Пока ядро работает, прерывания замаскированы: железо сбрасывает разрешение
# на входе в обработчик, а iret возвращает его из слова состояния процесса.
# Без этой маски таймер вошёл бы в ядро, которое ещё не дописало PCB.

        .pos 0
boot:   jmp resume              # PCB заполнены статически, остаётся запустить первый

# Входы из таблицы. Причину кладём в %rax, прежний %rax уже в PCB.
on_trap:
        pushq %rax
        irmovq $0, %rax
        jmp save
on_fault:
        pushq %rax
        irmovq $1, %rax
        jmp save
on_timer:
        pushq %rax
        irmovq $3, %rax

save:   pushq %rcx
        pushq %rdx
        pushq %rbx
        pushq %rbp
        pushq %rsi
        pushq %rdi
        pushq %r8
        pushq %r9
        pushq %r10
        pushq %r11
        pushq %r12
        pushq %r13
        pushq %r14
        irmovq kstack, %rsp     # контекст сохранён, дальше свой стек
        irmovq current, %rbx
        mrmovq (%rbx), %rbx     # %rbx это PCB текущего процесса
        andq %rax, %rax
        je syscall
        iaddq $-3, %rax
        je schedule             # таймер: квант кончился, очередь следующего
        jmp kill                # сбой: процесс снимаем

# Системный вызов: номер и аргументы читаем из сохранённого контекста.
syscall:
        mrmovq 0x68(%rbx), %rax
        iaddq $-1, %rax
        je sys_write            # 1
        iaddq $-23, %rax
        je schedule             # 24, yield
        iaddq $-36, %rax
        je kill                 # 60, exit
        irmovq $-1, %rax
        rmmovq %rax, 0x68(%rbx) # такого вызова нет
        jmp resume

# write(%rdi = адрес, %rsi = длина)
sys_write:
        mrmovq 0x38(%rbx), %rdi
        mrmovq 0x40(%rbx), %rsi
wloop:  andq %rsi, %rsi
        je wdone
        mrmovq (%rdi), %rcx
        out %rcx
        iaddq $1, %rdi
        iaddq $-1, %rsi
        jmp wloop
wdone:  mrmovq 0x40(%rbx), %rax
        rmmovq %rax, 0x68(%rbx) # процесс увидит длину в %rax
        jmp resume

# Процесс закончился или упал. Если живых не осталось, машина встаёт.
kill:   irmovq $0, %rax
        rmmovq %rax, 0x88(%rbx)
        irmovq alive, %rcx
        mrmovq (%rcx), %rax
        iaddq $-1, %rax
        rmmovq %rax, (%rcx)
        jne schedule
        halt

# Следующий живой процесс по кругу становится текущим.
schedule:
        mrmovq 0x90(%rbx), %rbx
        mrmovq 0x88(%rbx), %rax
        andq %rax, %rax
        je schedule
        irmovq current, %rcx
        rmmovq %rbx, (%rcx)

# Вернуть текущий процесс на процессор.
resume: irmovq current, %rbx
        mrmovq (%rbx), %rsp     # %rsp на начало PCB
        rrmovq %rsp, %rax
        iaddq $0x88, %rax
        irmovq ksp, %rcx
        rmmovq %rax, (%rcx)     # следующий кадр ляжет в этот же PCB
        popq %r14
        popq %r13
        popq %r12
        popq %r11
        popq %r10
        popq %r9
        popq %r8
        popq %rdi
        popq %rsi
        popq %rbp
        popq %rbx
        popq %rdx
        popq %rcx
        popq %rax
        iret

# Данные ядра. Код обязан кончиться раньше: ассемблер наложение не ловит.
        .pos 0x280
current:
        .quad pcb_a
alive:  .quad 2

# Процесс A: образ с 0x400, стек под 0x800.
        .pos 0x2a0
pcb_a:
        .pos 0x310
        .quad 0x400             # PC
        .quad 0x19              # пользовательский режим, прерывания разрешены, ZF = 1
        .quad 0x800             # %rsp
        .quad 1                 # жив
        .quad pcb_b

# Процесс B: образ с 0x800, стек под 0xc00.
        .pos 0x340
pcb_b:
        .pos 0x3b0
        .quad 0x800
        .quad 0x19
        .quad 0xc00
        .quad 1
        .quad pcb_a

# Стек ядра растёт вниз от таблицы исключений, в свободную память.
        .pos 0xfc0
kstack:
        .quad on_trap
        .quad on_fault
        .quad on_fault
        .quad on_timer
ksp:    .quad 0

Карта памяти

Четыре килобайта поделены так:

адреса	что лежит
`0x000` до `0x22c`	код ядра, последняя инструкция это `iret`
`0x280`, `0x288`	`current` (адрес PCB текущего процесса) и `alive` (сколько процессов живо)
`0x2a0` до `0x337`	PCB процесса A, 152 байта
`0x340` до `0x3d7`	PCB процесса B
`0x400` до `0x7ff`	процесс A: код с `0x400`, стек растёт вниз от `0x800`
`0x800` до `0xbff`	процесс B: код с `0x800`, стек от `0xc00`
до `0xfc0`	стек ядра, растёт вниз в свободную память
`0xfc0` до `0xfdf`	таблица исключений: `trap`, `adr`, `ins`, `timer`
`0xfe0`	слово `ksp`

Три файла собираются по отдельности, каждый своим вызовом ассемблера, и Computer.load накладывает образы друг на друга: ненулевые байты ложатся поверх. Это замена загрузчику, которого у нас нет. Защиты памяти тоже нет: процесс A может записать что угодно в PCB соседа или в код ядра. Бит привилегий запрещает ему halt, out и iret, но не запрещает rmmovq по любому адресу. Это честное состояние машины до страничной памяти, и оно продержится до урока про отображение памяти, где в машине появится MMU.

Ещё одна ловушка в самом низу файла: код ядра обязан кончиться до 0x280. Ассемблер из урока 21 наложение кусков не ловит, директива .pos просто переставляет счётчик адреса. Дорастёт код до данных, и current молча ляжет поверх инструкций. Сейчас запас 83 байта. Если будешь дописывать системные вызовы в домашней работе, проверяй листинг.

PCB и трюк с ksp

PCB устроен так, чтобы сохранение контекста не требовало ни одного копирования:

смещение  что лежит                        кто пишет
0x00      %r14                              ядро, последний pushq
0x08      %r13
...
0x60      %rcx
0x68      %rax                              ядро, первый pushq
0x70      PC                                железо, кадр исключения
0x78      слово состояния                   железо
0x80      %rsp процесса                     железо
0x88      жив ли процесс                    ядро
0x90      следующий PCB по кругу            задан статически

Вспомни из урока 47, куда железо кладёт кадр, когда исключение пришло из пользовательского режима: не на стек процесса (ему верить нельзя, там может быть любой мусор), а под адрес из слова ksp. Ядро держит ksp равным PCB + 0x88. Кадр занимает 24 байта под этим адресом, то есть ровно поля 0x70, 0x78 и 0x80. После входа %rsp смотрит на PCB + 0x70, и первый же pushq %rax кладёт регистр в PCB + 0x68. Ещё тринадцать pushq, и весь контекст лежит в PCB в правильном порядке. Железо и ядро пишут одну структуру с двух сторон, не договариваясь ни о чём, кроме одного адреса.

Настоящий x86-64 устроен так же, только слово называется иначе. Вершину стека для входа из третьего кольца в нулевое процессор берёт из поля RSP0 сегмента состояния задачи, TSS. Linux много лет при каждом переключении потоков записывал туда вершину стека ядра нового потока, в точности как наше ядро переписывает ksp. С 2018 года, после Meltdown, там стоит постоянный маленький стек на каждый процессор, а на стек потока пересаживается уже код входа, первыми же инструкциями. Кадр у x86-64 из пяти слов, а не трёх (добавляются селекторы CS и SS), регистры общего назначения ядро так же дописывает под него командами push, и получившаяся структура называется struct pt_regs. Если читал в исходниках Linux entry_64.S и не понимал, что там происходит: происходит save.

Три входа и разбор причины

Железо различает причины номером строки в таблице, а обработчик у нас по сути один. Поэтому каждый вход делает минимум и сливается с остальными: сохраняет %rax процесса (первым, потому что он сейчас понадобится), кладёт в %rax номер причины и прыгает в save. Входов три на четыре строки таблицы: сбои adr и ins ядро не различает, оба кончаются снятием процесса.

После save контекст в безопасности, и ядро пересаживается на собственный стек: irmovq kstack, %rsp. Стек ядра каждый раз начинается с чистого листа. Это законно, потому что ядро не прерывается и не засыпает посреди работы: между входом и iret оно проходит путь целиком, и на стеке после него не остаётся ничего нужного. У Linux не так: там у каждого потока свой стек ядра, потому что поток может уснуть внутри системного вызова, и его стек ядра обязан пережить сон.

Разбор причины это три инструкции, и в них есть приём, без которого на Y86 не обойтись. Инструкции сравнения нет. Флаги ставят только арифметика и логика, поэтому “равно ли нулю” пишется как andq %rax, %rax (значение не меняется, ZF ставится), а “равно ли трём” как iaddq $-3, %rax и проверка нуля. Значение при этом портится, так что цепочка сравнений идёт лесенкой: вычли единицу, проверили, вычли ещё двадцать три, проверили. Тот же приём в разборе номера системного вызова: 1, 24, 60 это 1, 1 + 23, 1 + 23 + 36.

Ветка таймера самая короткая во всём ядре: je schedule. Квант кончился, очередь следующего. Контекст уже сохранён, сохранён полностью, и сохранён тем же кодом, что при системном вызове. Процессу, которого сняли таймером, не нужно ничего возвращать в %rax, его PCB не трогают вообще.

Планировщик и возврат

schedule идёт по кольцу PCB от текущего к следующему, пока не найдёт живой, и записывает его в current. Это планирование по кругу, round robin, самое простое из честных. Если живой процесс один, кольцо возвращает его же, и ядро переключает процесс сам на себя: дорого, но правильно. Случай, когда живых нет, сюда не доходит: его ловит kill и останавливает машину.

resume это save наоборот. %rsp ставится на начало PCB, ksp переписывается на PCB + 0x88 (следующий кадр должен лечь в PCB того процесса, который сейчас поедет, а не того, который только что ехал), четырнадцать popq достают регистры, и после последнего %rsp смотрит ровно на кадр. iret снимает кадр: PC, слово состояния, %rsp. Вместе со словом состояния возвращаются режим процесса и бит ie. Прерывания включаются той же инструкцией, которая покидает ядро: ни такта с разрешёнными прерываниями внутри ядра нет.

Первый запуск процесса ничем не отличается от возврата в него. PCB заполнены статически, директивами .quad: PC равен началу образа, %rsp концу его области, слово состояния 0x19. Разложи его по битам из isa.zig: 0x10 пользовательский режим, 0x08 прерывания разрешены, 0x01 флаг ZF, как после сброса. Регистры нулевые. Ядро стартует с jmp resume и “возвращается” в процесс, который ещё ни разу не исполнялся. Так же стартует первый процесс в xv6 и так же fork в любом Unix делает нового ребёнка: готовит на стеке ядра кадр, как будто ребёнок уже входил в ядро, и выходит из него обычным путём.

Прогон: период 150

$ zig build run -- kernel programs/kernel/kernel.ys programs/kernel/tick.ys programs/kernel/tock.ys --timer 150 --console
tick
tock
tick
tock
tick
tock

Ни один из процессов не звал yield, а вывод идёт вперемежку. С ключом --events в трассе остаются только события, без строк инструкций. Вот она целиком, этот же файл лежит в tests/expected/kernel_150.events:

exc trap 0x429 -> 0x009
out 74
out 69
out 63
out 6b
out 0a
irq timer 0x43d -> 0x033
exc trap 0x829 -> 0x009
out 74
out 6f
out 63
out 6b
out 0a
irq timer 0x833 -> 0x033
exc trap 0x429 -> 0x009
out 74
out 69
out 63
out 6b
out 0a
irq timer 0x433 -> 0x033
exc trap 0x829 -> 0x009
out 74
out 6f
out 63
out 6b
out 0a
irq timer 0x829 -> 0x033
exc trap 0x429 -> 0x009
out 74
out 69
out 63
out 6b
out 0a
irq timer 0x429 -> 0x033
exc trap 0x829 -> 0x009
out 74
out 6f
out 63
out 6b
out 0a
irq timer 0x829 -> 0x033
irq timer 0x43d -> 0x033
exc trap 0x864 -> 0x009
irq timer 0x43d -> 0x033
exc trap 0x464 -> 0x009
halt cycles=1326
%rax 0x0000000000000000
%rcx 0x0000000000000288
%rdx 0x0000000000000000
%rbx 0x00000000000002a0
%rsp 0x0000000000000fc0
%rbp 0x0000000000000000
%rsi 0x0000000000000005
%rdi 0x0000000000000468
%r8 0x0000000000000000
%r9 0x0000000000000000
%r10 0x0000000000000000
%r11 0x0000000000000000
%r12 0x0000000000000000
%r13 0x0000000000000000
%r14 0x0000000000000000
timer raised=8 lost=0

Читается так. exc trap 0x429 -> 0x009: инструкция trap процесса A, адрес возврата 0x429 (следующая за ней), обработчик on_trap по адресу 0x009. Пять строк out это байты tick\n, они выходят из wloop в режиме ядра. irq timer 0x43d -> 0x033: принято прерывание, процесс A не успел начать инструкцию по адресу 0x43d (это jne spin, он был посреди пустого цикла), обработчик on_timer по адресу 0x033. Следующая строка уже от процесса B: exc trap 0x829. Переключение состоялось.

В конце два exit (0x864 и 0x464 это адреса после последнего trap в каждом образе), halt на такте 1326 и счётчики: восемь прерываний, потерь нет. Регистры в хвосте принадлежат ядру, а не процессам: %rbx это 0x2a0, PCB последнего умершего, %rsp это kstack.

Теперь то же место в полной трассе, вокруг первого прерывания:

U 0x433 c0 AOK
U 0x43d 74 AOK
U 0x433 c0 AOK
irq timer 0x43d -> 0x033
K 0x033 a0 AOK
K 0x035 30 AOK
K 0x03f a0 AOK
...
K 0x22a b0 AOK
K 0x22c d1 AOK
U 0x800 30 AOK
U 0x80a 30 AOK

Процесс крутил iaddq (c0) и jne (74). Перед очередным jne пришло прерывание, и следующая строка уже в режиме K: pushq %rax по адресу 0x033. Дальше 49 строк ядра, последняя это iret (d1) по адресу 0x22c, и первая инструкция процесса B по адресу 0x800. Между U 0x433 и U 0x800 нет ни одной инструкции, которую исполнил бы процесс A, зная о переключении.

Сколько стоит переключение

Посчитаем по трассе. Путь от on_timer до iret всегда один и тот же: 2 инструкции входа, 13 pushq, 7 на пересадку на стек ядра и разбор причины, 6 на schedule, 6 на начало resume, 14 popq, iret. Итого 49 тактов, и это число видно в трассе буквально: каждый отрезок строк K после irq имеет длину 49. Системный вызов write на пять байт стоит 87 тактов.

Всего полезной работы в двух процессах 288 тактов, это число не зависит от таймера. Остальное забирает ядро:

прогон	тактов всего	в режиме ядра	в процессах	доля ядра
без таймера	930	642	288	69%
`--timer 150`	1326	1038	288	78%
`--timer 60`	3571	3283	288	92%

Доли выглядят дико, и дело в масштабе. Наш квант это 150 инструкций, переключение это 49, треть кванта. У настоящей машины пропорция другая на четыре порядка: переключение контекста в Linux на современном x86-64 стоит единицы микросекунд вместе с косвенными потерями на остывший кэш и TLB, а квант это миллисекунды. Планировщик EEVDF, который с версии 6.6 сменил CFS, нарезает базовый отрезок около трёх миллисекунд на типичной многоядерной машине. Отношение порядка одного к тысяче. Наша машина показывает ту же механику под увеличительным стеклом: на ней видно, куда именно уходят такты, и что переключение никогда не бесплатно.

Отсюда же вечный компромисс при выборе кванта. Короткий квант даёт отзывчивость: никто не ждёт долго. Длинный даёт пропускную способность: меньше тактов сгорает на переключениях. CONFIG_HZ=1000 выбирают для рабочего стола, CONFIG_HZ=100 или 250 для сервера, и это тот же выбор между строками нашей таблицы.

Период короче ядра: потерянные тики

Уменьшим период до 60. Вывод цел, все шесть слов на месте. Но в трассе появилась новая строка:

exc trap 0x429 -> 0x009
irq timer 0x429 -> 0x033
irq timer 0x800 -> 0x033
irq timer 0x429 -> 0x033
irq timer 0x800 -> 0x033
irq timer 0x429 -> 0x033
irq timer 0x80a -> 0x033
irq timer 0x433 -> 0x033
exc trap 0x829 -> 0x009
lost timer
irq timer 0x829 -> 0x033
irq timer 0x433 -> 0x033
irq timer 0x83d -> 0x033
irq timer 0x43d -> 0x033
irq timer 0x833 -> 0x033
irq timer 0x433 -> 0x033
irq timer 0x83d -> 0x033
irq timer 0x414 -> 0x033
irq timer 0x833 -> 0x033
exc trap 0x429 -> 0x009
lost timer
irq timer 0x429 -> 0x033
irq timer 0x833 -> 0x033
irq timer 0x433 -> 0x033
...
halt cycles=3571
timer raised=54 lost=5

lost timer стоит сразу после каждого write. Причина в арифметике: write занимает в ядре 87 тактов, а период 60. Процесс вошёл в ядро, железо погасило ie, и пока ядро под маской гонит байты в порт, таймер успевает сработать дважды. Первый тик поднимает линию, и она висит: принять прерывание некому. Второй тик находит линию поднятой и пропадает. Когда ядро наконец делает iret, слово состояния процесса возвращает ie, и висящее прерывание принимается немедленно, до первой же инструкции процесса. Посмотри на адреса возврата: irq timer 0x429 сразу за exc trap 0x429. Процесс вернулся из write и не исполнил ни одной инструкции: его тут же сняли.

Сами процессы при этом получают по 11 тактов на квант: 60 минус 49 на переключение. Вся программа растянулась с 1326 тактов до 3571, и 92 процента из них ушли ядру.

А теперь период 30:

$ zig build run -- kernel programs/kernel/kernel.ys programs/kernel/tick.ys programs/kernel/tock.ys --timer 30 --console
tick
машина не дошла до останова: такты кончились
error: StepLimit

Одно слово, и больше ничего за сто тысяч тактов. В событиях картина такая:

exc trap 0x429 -> 0x009
lost timer
lost timer
irq timer 0x429 -> 0x033
lost timer
irq timer 0x800 -> 0x033
lost timer
irq timer 0x429 -> 0x033
irq timer 0x800 -> 0x033
lost timer
irq timer 0x429 -> 0x033
...
timer raised=2040 lost=1293

Адреса возврата не двигаются: 0x429, 0x800, 0x429, 0x800. Переключение стоит 49 тактов, период 30. К моменту iret следующее прерывание уже висит на линии и принимается до первой инструкции процесса. Процесс B так и стоит на своей самой первой инструкции по адресу 0x800. Машина занята на сто процентов, полезной работы ноль.

У этого состояния есть имя: livelock. В отличие от взаимной блокировки здесь никто никого не ждёт, все заняты, просто без толку. Классическая работа Могула и Рамакришнана 1996 года описала его на сетевых картах: под потоком пакетов ядро BSD тратило всё время на приём прерываний от карты и не успевало передать пакеты приложению, пропускная способность под нагрузкой падала до нуля. Лекарство, которое они предложили, стоит сегодня в каждом сетевом драйвере Linux под именем NAPI: под нагрузкой драйвер прерывания выключает и опрашивает карту сам, в удобное ему время. То есть возвращается от вытесняющей схемы к кооперативной, когда вытеснение перестаёт окупаться.

Маска прерываний и что бывает без неё

До сих пор ядро ни разу не прерывалось. Проверить легко: во всех прогонах адреса возврата в строках irq не ниже 0x400, прерывания приходили только в процессы. Это работа одной строки в handleTrap: на входе в обработчик железо гасит ie, и до iret ядро глухо. Настоящий x86-64 делает то же: вход через шлюз прерывания (interrupt gate) сбрасывает флаг IF в RFLAGS, а iretq возвращает его вместе с остальными флагами. Есть и другой тип шлюза, trap gate, который IF не трогает, и выбор между ними делает ядро для каждой строки своей таблицы. Linux на x86-64 для всего использует шлюзы прерываний и включает прерывания сам, командой sti, когда дошёл до безопасного места.

Зачем это нужно, лучше один раз увидеть. У нашего железа маску можно выключить ключом --no-mask: mask_on_entry становится ложью, handleTrap оставляет ie как было, и таймер получает право войти в ядро в любом месте. Период прежний, 150.

$ zig build run -- kernel programs/kernel/kernel.ys programs/kernel/tick.ys programs/kernel/tock.ys --timer 150 --no-mask --console
tick
tock
tick
tock
ticktock

Два перевода строки пропали, и машина при этом даже не остановилась по-человечески. События, они же файл tests/expected/kernel_150_nomask.events:

exc trap 0x429 -> 0x009
out 74
out 69
out 63
out 6b
out 0a
irq timer 0x43d -> 0x033
exc trap 0x829 -> 0x009
out 74
out 6f
out 63
out 6b
out 0a
irq timer 0x833 -> 0x033
exc trap 0x429 -> 0x009
out 74
out 69
out 63
out 6b
out 0a
irq timer 0x433 -> 0x033
exc trap 0x829 -> 0x009
out 74
out 6f
out 63
out 6b
out 0a
irq timer 0x146 -> 0x033
exc trap 0x429 -> 0x009
out 74
out 69
out 63
out 6b
irq timer 0x127 -> 0x033
exc trap 0x829 -> 0x009
out 74
out 6f
out 63
out 6b
irq timer 0x112 -> 0x033
exc trap 0x464 -> 0x009
irq timer 0x222 -> 0x033
halt cycles=1104
%rax 0x0033500000000000
%rcx 0x000280f330000000
%rdx 0x0000000fc0f430ef
%rbx 0xa0dfa0cfa0bfa0af
%rsp 0xfffffffdf0c00000
%rbp 0xa09fa08fa07fa06f
%rsi 0xa05fa03fa02fa01f
%rdi 0xa000000000000000
%r8 0x03f0300fa0000000
%r9 0x000000003f700000
%r10 0x000000000001f030
%r11 0x0fa0000000000000
%r12 0x003f700000000000
%r13 0x000000f0300fa000
%r14 0x000000000001dc70
timer raised=7 lost=0

Первые три прерывания попали в процессы (0x43d, 0x833, 0x433), и всё шло как раньше. Следующие четыре попали в ядро. Разберём каждое, сверяясь с листингом: адреса ниже 0x400 это код kernel.ys.

Такт 600, адрес 0x146. Это метка wdone: процесс B позвал write, цикл wloop уже выдал все пять байт, осталось записать длину в %rax процесса. Приходит прерывание. Машина в режиме ядра, поэтому кадр ложится не в PCB, а на текущий стек, то есть на стек ядра: ksp железо читает только при входе из пользовательского режима. on_timer и save честно сохраняют четырнадцать регистров, но сохраняют регистры ядра и тоже на стек ядра. Следующая инструкция irmovq kstack, %rsp выбрасывает всё сохранённое. Разбор причины видит тройку, schedule переключает на процесс A. Что осталось в PCB процесса B? Контекст на момент его trap: PC равен 0x829, %rax равен единице. Когда до B снова дойдёт очередь, он продолжит после trap, как будто вызов завершился. Байты вышли, а возвращаемое значение потерялось: в %rax у него номер вызова вместо длины. Наш tock результат не проверяет, и ему повезло.

Такт 750, адрес 0x127. Это инструкция out %rcx, и на этот раз цикл не закончен: четыре байта процесса A вышли, пятый, перевод строки, ещё нет. Тот же сценарий: состояние ядра выброшено, процесс A позже продолжит после trap в полной уверенности, что write отработал. Недописанный вызов никто не продолжит, потому что о нём никто не помнит. Отсюда tick без перевода строки.

Такт 900, адрес 0x112. Метка wloop, остался один байт. То же самое с процессом B, отсюда tock без перевода строки.

Такт 1050, адрес 0x222. А вот это уже не потерянный байт. Процесс A только что сделал exit, ядро пометило его мёртвым, выбрало B и восстанавливает его контекст. 0x222 это десятый popq из четырнадцати. В этот момент %rsp смотрит внутрь PCB процесса B, на 0x388. Приходит прерывание, машина в режиме ядра, кадр ложится на текущий стек, то есть в PCB. Потом save кладёт под него четырнадцать регистров, 112 байт. PCB процесса B начинается с 0x340, вплотную под ним по адресам лежит PCB процесса A, и pushq растут вниз как раз в него: слова с 0x300 по 0x338 это %rcx, %rax, кадр, признак жизни и, по адресу 0x330, ссылка на следующий PCB процесса A. Туда ложится нулевой регистр.

Дальше планировщик делает ровно то, что написано. От B идёт к A, видит, что A мёртв, идёт к следующему за A. Следующий за A теперь по адресу ноль. Признак жизни у “PCB по адресу ноль” это слово по адресу 0x88, а там код ядра, байты инструкций, не ноль. Значит, жив. resume ставит %rsp в ноль и четырнадцатью popq раскладывает по регистрам первые 112 байт собственного кода. Посмотри на хвост трассы:

K 0x22c d1 AOK
K 0x6200000000000000 f0 ADR
halt cycles=1104
%rax 0x0033500000000000
%rcx 0x000280f330000000
...
%r14 0x000000000001dc70

В %r14 лежит 70 dc 01, если читать от младшего байта. Это jmp resume, самая первая инструкция ядра. iret взял “адрес возврата” из слов по адресу 0x70, прыгнул на 0x6200000000000000, выборка дала ADR, а сбой в режиме ядра ловить некому. Машина встала. В Linux это называлось бы kernel panic.

Что здесь произошло на самом деле

Ядро написано в предположении, что между входом и iret его никто не прерывает. На этом предположении стоят три вещи: стек ядра можно каждый раз начинать заново; PCB можно использовать как стек; глобальные current и ksp можно менять в несколько инструкций. Сними маску, и все три ломаются, причём не сразу и не всегда, а только когда тик попадёт в неудачное место. При периоде 150 он попал на шестисотом такте. Поменяй период на единицу, и тики лягут в другие места, а картина будет другой.

Это та же гонка, что в уроке про сигналы, только этажом ниже. Там основная программа добавляла задание в список, обработчик SIGCHLD удалял задание из списка, и если сигнал приходил посреди добавления, список оставался в состоянии, которого не предусматривал ни один из двух участников. Лекарство там было sigprocmask: заблокировать сигнал на время работы с общей структурой. Здесь общая структура это PCB и стек ядра, два участника это ядро и оно же, вошедшее второй раз, а sigprocmask зовётся битом ie. Даже потеря та же самая: пока сигнал заблокирован, второй такой же пропадает, и пока ie сброшен, пропадает второй тик. Маска меняет порчу данных на потерю события, и этот обмен почти всегда выгоден: с потерей события можно жить (спроси источник истины), с испорченным PCB нельзя.

Главное отличие нашей ошибки от обычной в том, что она воспроизводится. Настоящая гонка с прерыванием проявляется раз в неделю на машине заказчика, потому что зависит от температуры кварца. Наша зависит только от периода таймера, и два прогона с одним периодом дают одну трассу байт в байт. Это свойство симулятора мы сейчас превратим в тест. Помни о нём, когда будешь отлаживать настоящие гонки: первое, что делают с неуловимой ошибкой, это ищут способ сделать её детерминированной.

В настоящих ядрах выключить прерывания целиком на всё время работы нельзя: системный вызов может длиться миллисекунды, и всё это время машина была бы глуха к сети и диску. Поэтому ядро Linux прерываемо почти везде, а короткие участки, где трогают общие с обработчиками структуры, закрывает само: local_irq_save и local_irq_restore, spin_lock_irqsave. Цена этого в том, что каждую такую структуру надо знать в лицо. Наше ядро выбрало простой путь, и для ядра на двести строк это правильный выбор. xv6 делает так же: в его usertrap прерывания включаются только после того, как контекст сохранён, а внутри sched выключены всегда.

Машина с ядром в браузере

Всё, что мы только что читали в трассах, можно прощёлкать руками. Это та же машина из урока 22, но в режиме ядра: в память уже загружены kernel.ys, tick.ys и tock.ys, рядом с регистрами появились бейджи режима (K или U), битов ie и irq, текущего процесса (A это tick, B это tock) и счётчики таймера: сколько натикало из периода, сколько прерываний поднято, сколько потеряно. Ручек две: “период таймера” (выключен, 60, 100, 150 или 300 тактов) и флажок “маска прерываний на входе в обработчик”. Байты из порта собирает панель “вывод машины”, а в трассе, кроме знакомых строк irq timer, exc, out и lost timer, стоят пометки вида # контекст: процесс A -> B в тех местах, где resume отдал процессор соседу. Кнопка “до события” гонит машину до ближайшей строки irq, exc, out или lost timer, чтобы не щёлкать сорок девять pushq и popq по одному. Трассы виджета совпадают с трассами Zig-симулятора строка в строку.

Четыре опыта, по порядку:

Таймер выключен. Дойди до конца и посмотри на панель “вывод машины”: три tick, потом три tock. Бейдж irq ни разу не загорелся, процесс меняется только на exit.
Период 150, маска включена. Жми “до события” и следи за первым irq timer 0x43d -> 0x033: режим сменился на K, ie погас, %rsp смотрит в PCB процесса A (0x308 после первого pushq). Пройди по шагам до iret и убедись, что ie вернулся той же инструкцией, которая сменила режим на U, а процесс в бейдже стал B. В конце raised=8, lost=0, вывод вперемежку.
Период 60, маска включена. Здесь появляется буквальная строка lost timer: дойди до первого write и смотри, как счётчик таймера дважды доходит до периода, пока ie погашен. Первый раз загорается irq, второй раз растёт lost. Сразу после iret прерывание принимается с адресом возврата 0x429: процесс не успел ничего. Итог raised=54, lost=5, вывод цел.
Период 150, маска снята. Потерь не будет, lost=0: без маски прерывание принимается сразу, линия не висит. Зато ломается всё остальное. Дойди до irq timer 0x146: режим уже K, и %rsp после входа уходит не в PCB, а под 0xfc0, на стек ядра. Дальше смотри на панель вывода, где tick и tock склеятся без переводов строк, и на последнее событие irq timer 0x222: %rsp в этот момент равен 0x388, внутри PCB процесса B. Дошагай до останова с кодом ADR и загляни в регистры: в них лежат байты кода ядра.

Тесты шага

Трасса при заданном периоде одна и та же от запуска к запуску: в машине нет ни одного источника случайности, таймер считает такты, а не время. Значит, её можно хранить образцом и сравнивать байт в байт. Образцы снимаются той же программой:

$ K="programs/kernel/kernel.ys programs/kernel/tick.ys programs/kernel/tock.ys"
$ zig build run -- kernel $K --timer 150 > tests/expected/kernel_150.trace
$ zig build run -- kernel $K --timer 150 --events > tests/expected/kernel_150.events
$ zig build run -- kernel $K --timer 150 --no-mask --events > tests/expected/kernel_150_nomask.events

Перенаправление здесь через >, не через >>: писатель стандартного вывода в Zig 0.16 пишет позиционно и при дозаписи затёр бы начало файла. И одно правило гигиены. Образец, снятый с программы, фиксирует её поведение, а не правильность. Прежде чем положить файл в tests/expected/, прочитай его глазами: события мы разобрали выше, в полной трассе проверь хотя бы первое переключение и хвост. Иначе тест будет охранять ошибку.

//! Шаг 50: ядро целиком. Таймер, вытеснение, маска прерываний.
//!
//! Главное свойство: при заданном периоде таймера трасса двух процессов
//! одна и та же от запуска к запуску, поэтому её можно хранить образцом.
//! Второе: без маски прерывание входит в ядро посреди системного вызова,
//! и это тоже воспроизводится такт в такт.

const std = @import("std");
const y86 = @import("y86");

const testing = std.testing;
const computer = y86.computer;
const kernel = y86.programs.kernel;

fn run(sources: []const []const u8, config: computer.Config) !computer.Output {
    var images: [4][]u8 = undefined;
    var count: usize = 0;
    defer for (images[0..count]) |image| testing.allocator.free(image);
    for (sources) |source| {
        var result = try y86.assembler.assemble(testing.allocator, source, null);
        defer result.deinit(testing.allocator);
        images[count] = try testing.allocator.dupe(u8, result.image);
        count += 1;
    }
    return computer.runImages(testing.allocator, images[0..count], config);
}

const two = [_][]const u8{ kernel.full, kernel.tick, kernel.tock };

test "трасса двух процессов при периоде 150 совпадает с образцом" {
    var full = try run(&two, .{ .timer_period = 150 });
    defer full.deinit(testing.allocator);
    try testing.expectEqualStrings(@embedFile("kernel_150.trace"), full.trace);

    var events = try run(&two, .{ .timer_period = 150, .events_only = true });
    defer events.deinit(testing.allocator);
    try testing.expectEqualStrings(@embedFile("kernel_150.events"), events.trace);
    try testing.expectEqualStrings("tick\ntock\ntick\ntock\ntick\ntock\n", events.console);
}

test "без таймера процессы идут друг за другом, с таймером вперемежку" {
    var alone = try run(&two, .{});
    defer alone.deinit(testing.allocator);
    try testing.expectEqualStrings("tick\ntick\ntick\ntock\ntock\ntock\n", alone.console);

    var shared = try run(&two, .{ .timer_period = 150 });
    defer shared.deinit(testing.allocator);
    try testing.expect(!std.mem.eql(u8, alone.console, shared.console));
    // Работа та же, тактов больше: переключения не бесплатны.
    try testing.expect(shared.summary.cycles > alone.summary.cycles);
    try testing.expectEqual(@as(usize, 0), shared.summary.lost);
}

test "под маской ядро не прерывается" {
    var out = try run(&two, .{ .timer_period = 150, .events_only = true });
    defer out.deinit(testing.allocator);
    try testing.expectEqual(@as(usize, 0), kernelInterrupts(out.trace));
}

test "период короче работы ядра: тики теряются, вывод цел" {
    // Линия запроса это один бит. Пока ядро под маской, второй тик поверх
    // непринятого первого пропадает, как второй сигнал того же типа.
    var out = try run(&two, .{ .timer_period = 60, .events_only = true });
    defer out.deinit(testing.allocator);
    try testing.expectEqual(@as(usize, 5), out.summary.lost);
    try testing.expectEqual(@as(usize, 5), std.mem.count(u8, out.trace, "lost timer\n"));
    try testing.expectEqual(@as(usize, 3), std.mem.count(u8, out.console, "tick\n"));
    try testing.expectEqual(@as(usize, 3), std.mem.count(u8, out.console, "tock\n"));
}

test "без маски прерывание рвёт системный вызов, и это воспроизводится" {
    const config: computer.Config = .{ .timer_period = 150, .mask = false, .events_only = true };
    var out = try run(&two, config);
    defer out.deinit(testing.allocator);

    try testing.expectEqualStrings(@embedFile("kernel_150_nomask.events"), out.trace);
    // Таймер вошёл в ядро четыре раза, первый раз посреди цикла write.
    try testing.expectEqual(@as(usize, 4), kernelInterrupts(out.trace));
    try testing.expect(std.mem.indexOf(u8, out.trace, "irq timer 0x146 -> ") != null);
    // Недописанный write никто не продолжил: два перевода строки пропали.
    try testing.expectEqualStrings("tick\ntock\ntick\ntock\nticktock", out.console);

    // Второй прогон даёт ту же трассу байт в байт.
    var again = try run(&two, config);
    defer again.deinit(testing.allocator);
    try testing.expectEqualStrings(out.trace, again.trace);
}

test "упавший процесс снимается и при вытеснении" {
    var out = try run(&.{ kernel.full, kernel.tick, kernel.crash }, .{ .timer_period = 150 });
    defer out.deinit(testing.allocator);
    try testing.expectEqualStrings("tick\ntick\ntick\n", out.console);
    try testing.expectEqual(y86.Stat.hlt, out.summary.stat);
}

/// Сколько прерываний принято с адресом возврата внутри ядра (ниже 0x400).
fn kernelInterrupts(trace_text: []const u8) usize {
    var count: usize = 0;
    var lines = std.mem.tokenizeScalar(u8, trace_text, '\n');
    while (lines.next()) |line| {
        if (!std.mem.startsWith(u8, line, "irq timer 0x")) continue;
        const epc = std.fmt.parseInt(u64, line[12..15], 16) catch continue;
        if (epc < 0x400) count += 1;
    }
    return count;
}

Шесть тестов, и у каждого своя роль. Первый держит трассу целиком: любая правка ядра, железа или ассемблера, которая сдвинет хоть один адрес, его уронит. Это намеренно хрупкий тест, он так и задуман: упал, посмотри на разницу, и если она ожидаемая, пересними образец. Второй проверяет смысл, а не байты: с таймером вывод другой, тактов больше, потерь нет. Третий проверяет маску через помощник kernelInterrupts, который считает прерывания с адресом возврата ниже 0x400. Четвёртый закрепляет числа при периоде 60: ровно пять потерь и целый вывод. Пятый воспроизводит аварию без маски и проверяет главное её свойство, повторяемость. Шестой берёт процесс crash.ys из урока 48 и убеждается, что сбой ADR в процессе под таймером по-прежнему снимает только виновного.

$ zig build test -Dstep=50 --summary all
...
+- run test 6 pass (6 total)
$ zig build test -Dstep=47 && zig build test -Dstep=48

Старые шаги обязаны остаться зелёными, и останутся: без ключа --timer период равен нулю, таймер молчит, и машина ведёт себя в точности как в уроке 48.

На macOS. Весь сегодняшний код это наша собственная машина, и ей безразлично, где работать: zig build test и все прогоны идут на macOS напрямую, песочница не нужна, трассы совпадают с Linux байт в байт. Различается только то, что под капотом у самой macOS, и туда полезно заглянуть. sysctl kern.clockrate на Apple Silicon отвечает hz = 100, tick = 10000: сто тиков в секунду, десять миллисекунд. Это унаследованная от BSD единица учёта, а не частота прерываний: ядро XNU давно бестиковое, таймер ARM (generic timer, регистр CNTP_TVAL_EL0) каждый раз заводится на ближайший срок, когда ядру что-то понадобится. Квант планировщика Mach по умолчанию десять миллисекунд. Слово, в котором ARM64 держит вершину стека ядра, называется SP_EL1: у процессора два указателя стека, по одному на уровень привилегий, и при исключении он переключается на второй сам, без чтения памяти. Кадра в памяти железо ARM не кладёт вовсе: адрес возврата и слово состояния попадают в регистры ELR_EL1 и SPSR_EL1, а в память их вместе с остальными регистрами сохраняет ядро. Инструкция возврата называется eret. Те же три слова, что в нашем кадре, только лежат в регистрах.

Практика

В задаче ты пишешь ту половину входа в ядро, которую делает железо: statusWord, setStatus, handleTrap и iret. Это чистые функции над маленькой структурой Machine, без ассемблера и без симулятора, но сценарий последнего теста взят из сегодняшнего проекта: два процесса, у каждого ksp смотрит в свой PCB, и возврат в первый идёт ровно туда, где его прервали. Следи за порядком: сначала все проверки, потом первая запись. Тесты сравнивают машину после отказа целиком, вместе с памятью.

Упражнения

E50.1★

Процесс исполняет цикл из двух инструкций, iaddq и jne, и таймер снимает его перед jne. Какие значения лежат в кадре исключения? Что было бы с процессом, если бы железо положило в кадр адрес следующей инструкции, как при trap? А если бы ядро сохранило все регистры, но забыло про флаги?

E50.2★

Посчитай по листингу kernel.ys, сколько тактов занимает yield от trap до первой инструкции соседа и сколько занимает exit последнего живого процесса. Проверь оба числа по трассе без таймера.

E50.3★★

При каком наименьшем периоде таймера пара tick и tock ещё завершается? Сначала выведи оценку из двух чисел, 49 и 87, потом найди точное значение перебором ключа --timer и объясни, почему оно отличается от оценки.

E50.4★★

В книге есть задача про программу, которая вызывает fork в цикле и печатает: нужно перечислить возможные выводы. Сделай её аналог для нашей машины. Два процесса печатают по два разных байта каждый, без пустых циклов. Сколько разных выводов можно получить, перебирая период таймера от 50 до 300? Какие перестановки байтов недостижимы ни при каком периоде и почему?

E50.5★★

Добавь системный вызов getpid (номер 39, как в Linux): он возвращает в %rax адрес PCB вызывающего процесса. Какие строки ядра пришлось тронуть? Уложился ли код в запас до 0x280?

E50.6★★★

Замени планирование по кругу на приоритетное: в PCB появляется поле приоритета, таймер переключает на соседа только если его приоритет не ниже. Покажи на трассе голодание процесса с низким приоритетом. Потом добавь старение: каждый пропущенный квант поднимает приоритет ждущего на единицу. Сколько квантов ждёт теперь самый невезучий?

E50.7★★★

Сделай ядро устойчивым к прерыванию в режиме ядра, не полагаясь на маску. Подсказка в трёх частях: вход из режима ядра надо отличать от входа из процесса (куда смотрит слово состояния в кадре?); регистры прерванного ядра надо сохранять на стек ядра и возвращать оттуда же, не трогая ни PCB, ни kstack; переключать процесс из вложенного входа нельзя, можно только выставить флаг “пора”, который проверит внешний вход перед resume. Прогони с --no-mask и добейся целого вывода. Это та самая конструкция, которой Linux откладывает перепланирование до выхода из прерывания, флаг там зовут TIF_NEED_RESCHED.

Итоги

Кооперативная многозадачность держится на вежливости процессов. Вытесняющая держится на прерывании таймера: это единственный способ вернуть управление ядру без согласия процесса.
Таймер это счётчик и линия в один бит. Устройство поднимает линию, процессор проверяет её между инструкциями, принятое прерывание опускает её. Второй тик поверх непринятого первого пропадает, как второй сигнал того же типа.
Прерывание принимается на границе инструкций и кладёт в кадр адрес той, что не успела начаться. У trap в кадре следующая инструкция, у сбоя сама сбойная. Весь остальной вход в ядро у трёх классов общий.
Контекст это всё, что нужно для продолжения: четырнадцать регистров от ядра плюс PC, слово состояния и %rsp от железа. Слово ksp смотрит внутрь PCB, поэтому кадр ложится прямо туда, а ядро дописывает регистры обычными pushq. У x86-64 ту же роль играет RSP0 в TSS.
Планировщик по кругу это шесть инструкций. Переключение целиком стоит 49 тактов, write на пять байт 87. При периоде 150 ядро забирает 78 процентов тактов, при 60 уже 92, при 30 машина занята одними прерываниями и не исполняет ни одной инструкции процесса.
Маска прерываний внутри обработчика меняет порчу данных на потерю события. Без неё таймер рвёт write посередине, кладёт кадр внутрь PCB, и ядро восстанавливает “процесс” из собственного кода. Это та же гонка, что между программой и обработчиком сигнала, и лечится она тем же: закрыть общую структуру от второго входа.
Симулятор делает гонку детерминированной: один период, одна трасса. Поэтому аварию можно положить в тест образцом.

Дальше

У машины Y86 теперь есть всё, что в книге называется потоком управления с исключениями: системные вызовы, сбои, прерывания, процессы и ядро, которое ими распоряжается. Чего у неё нет, так это защиты памяти: процесс по-прежнему может испортить ядро одной инструкцией rmmovq, и маска прерываний тут не поможет. К этому мы вернёмся, когда дойдём до виртуальной памяти, и MMU на нашей машине появится в уроке про отображение памяти. А пока закончим с потоком управления на стороне обычных программ. В следующем уроке речь пойдёт про нелокальные переходы: setjmp и longjmp делают в пользовательском коде почти то же, что save и resume в нашем ядре, сохраняют регистры в буфер и позже возвращают их, только без всякого ядра. Там же выяснится, почему Zig обходится без них и что у него вместо исключений.

домашка

Домашка

Добавь в ядро счётчик тиков и системный вызов sleep(n): процесс не получает процессор, пока не пройдёт n прерываний таймера. Перепиши tick.ys так, чтобы вместо пустого цикла он спал, и сравни число тактов и долю тактов в режиме ядра с исходным прогоном.L
Заведи в PCB поле с числом квантов, которые процесс получил, и печатай оба счётчика перед остановом машины. Прогони tick и tock с периодами 150, 100 и 60 и объясни, почему кванты делятся не поровну.L
Сделай write переживающим прерывание без маски: ядро после каждого байта сохраняет в PCB продвинутые адрес и длину, а прерванный вызов перезапускается с того же места. Прогони с ключом --no-mask и найди, какие места ядра всё равно остались уязвимыми.L