Пишу игрушечную ОС (о реализации sleep)

Очередной пост для блога, посвященного работе над игрушечной ОС. В прошлый раз я писал про необходимость в простеньком драйвере AHCI (SATA). Прежде чем начать двигаться в этом направлении, я решил набросать инфраструктуру драйверов: общий интерфейс драйвера + уточнённый интерфейс драйвера устройства хранения. Формулирование этих интерфейсов выявила проблему, на которую я ранее не обращал внимания — проблему портируемости.

Не зависящий от платформы код (например, большая часть планировщика, вспомогательный код типа kprintf, …) у меня перемешивается с кодом, заточенным только под x86_64 (системные таблицы дескрипторов, APIC, прерывания, …). Хотя ничего не мешало мне сформулировать интерфейс драйвера, жёстко привязанного к x86_64 (в частности, свободно оперировать PCI-адресами), мне стало ясно, что без чёткого отделения кода, специфичного для конкретной платформы, от общего портируемого кода я буду лишь усугублять ситуацию. Итак, я принял решение перебрать всё написанное, отделив общий код (в корне src/) от кода, специфичного для платформы (в src/x86_64/). Этим я и занимался последние две недели.

Опишу вкратце механизм разделения кода на примере планировщика. Интерфейс планировщика src/schedule.h подключает (#include) специальный файл src/x86_64/schedule.inc, содержащий зависящие от платформы static inline функции (как интерфейсные, так и внутренние). Все внутренние символы (не относящиеся к интерфейсным, но не могущие быть static) предваряются префиксом "__". Основная реализация планировщика находится в src/schedule.c, отдельные внутренние функции и код ассемблера в src/x86_64/schedule.c. Таким образом, кода планировщика «распыляется» на две директории. Разумеется, эта сложность лишь для общего случая, тогда как многие модули строятся по упрощённой схеме. Например, для cpu_info (информация о логических процессорах) заголовок раполагается в src/, а реализация — в src/x86_64/. Или полностью платформозависимый APIC целиком помещён в src/x86_64/.

Теперь об обещанной функции sleep. В отличие от мьютекса реализация sleep потребовала некоторой модификации планировщика (пусть и минимальной). В интерфейсную часть добавились функции:

typedef void (*timer_proc)(uint64_t ticks);  uint64_t get_ticks(void); timer_proc get_timer_proc(void); uint64_t get_timer_ticks(void); // is zeroed after triggering void set_timer_proc(timer_proc proc); // called within a timer interrupt void set_timer_ticks(uint64_t ticks); // not thread-safe 

Т.е. теперь планировщик выступает ещё и в роли таймера: хранит счётчик тиков (внутренних прерываний по таймеру), а также вызывает функцию-обработчик, как только число тиков достигнет заданного числа. Рассмотрим реализацию этого механизма.

static inline void handle_timer(int cpu) {   if (cpu == get_bsp_cpu())     ticks++;    if (timer_ticks[cpu] && timer_ticks[cpu] <= ticks) {     uint64_t prev_ticks = timer_ticks[cpu];     timer_ticks[cpu] = 0;     set_outer_spinlock(true);     timer_proc_(prev_ticks);     set_outer_spinlock(false);   } } 

Функция handle_timer вызывается в каждом прерывании по таймеру. Несмотря на то, что счётчик ticks инкрементируется только для bootstrap-процессора, таймер независимо программируется для каждого из логических процессоров. Оборачивание вызова обработчика в set_outer_spinlock нужно для того, чтобы вызов release_spinlock внутри обработчика случайно не выполнил инструкцию STI (не забываем, что мы находимся в контексте прерывания).

Вот теперь, пользуясь этим расширенным функционалом планировщика, мы можем реализовать sleep.

struct sleep_node {   struct sleep_node *next;   thread_id thread;   uint64_t ticks; };  static struct sleep_data {   struct sleep_node *tail;   struct mem_pool pool;   struct spinlock lock; } sleeping[CONFIG_CPUS_MAX];  static void sleep_timer_proc(UNUSED uint64_t ticks) {   struct sleep_data *slp = &sleeping[get_cpu()];   if (slp->tail) {     struct sleep_node *node = slp->tail;     slp->tail = slp->tail->next;     if (slp->tail)       set_timer_ticks(slp->tail->ticks);     resume_thread(node->thread);     free_block(&slp->pool, node);   } }  err_code sleep(uint64_t period) {   struct sleep_data *slp = &sleeping[get_cpu()];   err_code err = ERR_NONE;    acquire_spinlock(&slp->lock, 0);   struct sleep_node *node = alloc_block(&slp->pool);   if (node) {     node->thread = get_thread();     node->ticks = get_ticks() + period / CONFIG_SCHEDULER_TICK_INTERVAL;      if (!slp->tail || slp->tail->ticks > node->ticks) { // is first to wake up       node->next = slp->tail, slp->tail = node;       set_timer_ticks(node->ticks);     }     else {       struct sleep_node *prev = slp->tail;       while (prev->next && prev->next->ticks <= node->ticks)         prev = prev->next;       node->next = prev->next, prev->next = node;     }      pause_this_thread(&slp->lock);   }   else     err = ERR_OUT_OF_MEMORY;   if (err)     release_spinlock(&slp->lock);    return err; } 

Вышеприведённый код нуждается в некоторых пояснениях:

1. Экземпляр структуры sleep_data соответствует логическому процессору. Пул для sleep_node у каждого процессора независимый, поскольку mem_pool не потокобезопасен.

Именно поэтому в коде мьютекса у меня прячется серьёзная ошибка: для всех мьютексов предусмотрен единый пул для mutex_node, а нужно, чтобы каждый мьютекс имел свой собственный пул. Планирую исправить это в ближайшее время.

2. Как видно из кода, при добавлении в список потоки ранжируются по времени пробуждения (в тиках).

3. Функция sleep_timer_proc и есть тот обработчик, который вызывается планировщиком в контексте прерывания по таймеру. Её задача — разбудить нужный поток.

Остальное кажется достаточно прозрачным.