Пишу игрушечную ОС (о реализации 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 потребовала некоторой модификации планировщика (пусть и минимальной). В интерфейсную часть (src/schedule.h) добавились функции:

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

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

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 (src/sync.c).

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 и есть тот обработчик, который вызывается планировщиком в контексте прерывания по таймеру. Её задача — разбудить нужный поток.

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

Автор: ababo

Источник