Embox corporate blog
Abnormal programming
Open source
System Programming
C
25 January 2018

Реализация fork() без MMU

Здравствуй, читатель! Пару лет назад в статье про vfork() я обещал рассказать про реализацию fork() для систем без MMU, но руки до этого дошли только сейчас :)

В этой статье я расскажу, как мы реализовали такой странный fork(). Проверять работоспособность буду на сторонней программе — dash — интерпретаторе, который использует fork() для запуска приложений.

Кому интересно, прошу под кат.

Может возникнуть закономерный вопрос — зачем вообще делать какую-то урезанную версию fork(), если примерно для этого и существует vfork(), как раз позволяющий создавать процессы без использования MMU? На самом деле, есть ряд приложений, которые не используют копирование адресного пространства «на полную катушку», но и vfork()-а им недостаточно (напомню, что при использовании vfork() в потомке даже стек трогать нельзя, т. е. нельзя возвращаться из функции или менять локальные переменные).

dash — POSIX-совместимая легковесная оболочка — как раз служит примером такой программы. Если упростить, при вызове сторонних программ dash использует fork(), после чего в обоих процессах (родительском и дочернем) модифицирует некоторые статические данные, производит некоторые операции с кучей, затем дочерний процесс вызывает нужную программу с помощью execv(), а родитель вызывает waitpid() и ждёт завершения потомка.

Небольшой ликбез для тех, кто не понимает, что значат все эти слова, но почему-то продолжил читать статью: в UNIX-системах процессы создаются при помощи системного вызова fork(). По определению из POSIX, fork() должен создавать точную копию процесса за исключением некоторых переменных. При успешном выполнении функция возвращает значение ноль дочернему процессу и номер дочернего процесса — родителю (после этого процессы начинают «жить своей жизнью»). Получается, что в системе начинают работать два процесса с одними и теми же адресами переменных, с одним и тем же адресом стека и так далее. Тем не менее, данные «не путаются» между процессами благодаря использованию виртуальной памяти: создаётся копия данных родителя, и процесс-потомок обращается к другим физическим адресам. Подробнее про виртуальную память можно почитать здесь.

Современные MMU позволяют выставлять права доступа для страниц памяти, поэтому для создания процесса достаточно просто клонировать таблицу трансляции, помечая при этом страницы флагом copy-on-write, а при попытке записи в данную страницу клонировать данные по-настоящему. Отсутствие MMU не только лишает возможности использовать эту оптимизацию, но и ставит под вопрос возможность реализации вызова fork() в принципе. Без аппаратной поддержки виртуальной памяти программы используют физические адреса, а не виртуальные, а значит — процесс, полученный с помощью fork(), неизбежно будет обращаться к тем же самым данным, что и процесс-родитель.

В широком смысле, под адресным пространством процесса понимают всю память, замэпированную для того или иного процесса. Сюда входит сегмент с программным кодом, куча, стэки потоков, частично память ядра, может входить память периферии и так далее. В статье под адресным пространством будет пониматься куча (heap), статические данные (здесь и дальше под статическими данными подразумеваются данные из секций .bss и .data) и стек процесса, то есть данные которые могут быть изменены в обоих процессах. Именно с этими данными и придётся разбираться, чтобы избежать путаницы между работой «форкнутых».

Поскольку речь идёт о реализации fork() в многозадачной ОС, важную роль играет переключение контекста процесса. О переключении контекстов объектов, которые делят процессорное время, написано в нашей статье «Организация многозадачности в ядре ОС». В данном случае должно переключаться ещё и адресное пространство. Если в системах с MMU это, грубо говоря, изменение указателя на таблицу трансляции, то в случае отсутствия MMU обеспечить корректную работу процессов будет сложнее.

Один из способов — подменять значения на стеке, в куче и в статической памяти при переключении процессов. Это, конечно, очень медленно, но достаточно просто. Собственно, в этом и заключается идея для реализации нашего fork() без MMU. Мы запоминаем необходимые данные для «форкнутных» процессов и при переключении копируем значения в рабочее адресное пространство. Для стека, кучи и статических данных это делается по-разному.

Стек


В нашей ОС память для стеков потоков выделяется не динамически, а из статического пула, соответственно, некоторая часть .bss содержит в себе место под стеки. Нас интересуют только те стеки, соответствующие потоки которых являются «форкнутыми». Процессы-копии, согласно определению POSIX, должны иметь лишь один поток (копию того, в котором произошёл соответствующий системный вызов), но fork() может быть вызван из разных потоков в разное время, поэтому нужно для каждого адресного пространства поддерживать список потоков, стеки которых необходимо сохранять.

Куча


Данные кучи сохраняются в буфере, который выделяется из статического пула страниц.

.bss и .data


Embox (вместе со всеми приложениями) компилируется в один статический образ, поэтому информация о секциях .bss и .data берётся не из какого-нибудь ELF-файла, а сохраняется в общую секцию под уникальным именем (например, __module_embox__cmd__shell_data_vma). Информация о том, какие данные относятся к какому приложению, сохраняется в специальной структуре, которая задаётся во время компиляции.

struct mod_app {                 
    char  *data;             
    size_t data_sz;          
    char  *bss;              
    size_t bss_sz;           
};

Во время исполнения по текущему процессу можно узнать, где хранятся его данные.

При непосредственном запуске программы нужно скопировать соответствующие данные в некоторую область памяти (чтобы при последующих запусках программы начальные значения переменных были корректными).

Вот к эти куски памяти мы и будем копировать в выделенный участок системной памяти.

fork


Вышесказанного достаточно для того, чтобы понять, как именно работает вызов fork().
Сама функция fork является архитектурно-зависимой. На языке ассемблера реализована передача регистров в качестве аргумента вызову fork_body() — функции, реализующей логику системного вызова.

Хотя большинство читателей знакомо больше с набором команд x86, приведу реализацию для ARM, так как она гораздо короче и понятнее.

Регистры сохраняем в структуре pt_regs:

typedef struct pt_regs {
        int r[13];   /* Регистры общего назначения */
        int lr;      /* Адрес возврата */
        int sp;      /* Указатель стека */
        int psr;     /* Состояние программы, ARM-специфичный регистр */
} pt_regs_t;

Исходный код функции fork()
/* Регистры будем сохранять на стеке, для этого выделяем 68 байт */
sub    sp, sp, #68
/* Копируем 13 регистров общего назначения и регистр возврата */
stmia  sp, {r0 - r12, lr}
/* Сохраняем SP */
str    sp, [sp, #56]
/* Напрямую записывать CPSR в память не можем, поэтому считываем CPSR в r0*/
mrs    r0, cpsr;
/* Сохраняем CPSR на стеке */
str    r0, [sp, #60];
/* По соглашению о вызовах в r0 передаётся первый аргумент */           
mov    r0, sp
/* Переходим к архитектурно-независимой части вызова */                          
b      fork_body        


Как вы могли заметить, на самом деле, в ptregs сохраняется не корректное значение SP, а сдвинутое на 68 байт (в которые мы положили структуру pt_regs_t). Мы это учтём при восстановлении регистров.

Архитектурно-независимая часть вызова fork()
void _NORETURN fork_body(struct pt_regs *ptregs) {
    struct addr_space *adrspc;
    struct addr_space *child_adrspc;
    struct task *parent;
    pid_t child_pid;
    struct task *child;

    assert(ptregs);

    parent = task_self();
    assert(parent);

    child_pid = task_prepare(""); 
    if (0 > child_pid) {
        ptregs_retcode_err_jmp(ptregs, -1, child_pid);
        panic("%s returning", __func__);
    }

    adrspc = fork_addr_space_get(parent);
    if (!adrspc) {
        adrspc = fork_addr_space_create(NULL);
        fork_addr_space_set(parent, adrspc);
    }

    /* Save the stack of the current thread */
    fork_stack_store(adrspc, thread_self());

    child = task_table_get(child_pid);
    child_adrspc = fork_addr_space_create(adrspc);

    /* Can't use fork_addr_space_store() as we use
     * different task as data source */
    fork_stack_store(child_adrspc, child->tsk_main);
    fork_heap_store(&child_adrspc->heap_space, task_self());
    fork_static_store(&child_adrspc->static_space);

    memcpy(&child_adrspc->pt_entry, ptregs, sizeof(*ptregs));

    sched_lock();
    {
        child = task_table_get(child_pid);
        task_start(child, fork_child_trampoline, NULL);
        fork_addr_space_set(child, child_adrspc);
        thread_stack_set(child->tsk_main, thread_stack_get(thread_self()));
        thread_stack_set_size(child->tsk_main, thread_stack_get_size(thread_self()));
    }
    ptregs_retcode_jmp(ptregs, child_pid);
    sched_unlock();
    panic("%s returning", __func__);
}


Вызов функции ptregs_retcode_jmp() приведёт к возврату в родителький процесс. В свою очередь, дочерний процесс воспользуется тем же вызовом при старте процесса.

static void *fork_child_trampoline(void *arg) {
    struct addr_space *adrspc;

    adrspc = fork_addr_space_get(task_self());

    fork_stack_restore(adrspc, stack_ptr());

    ptregs_retcode_jmp(&adrspc->pt_entry, 0);
    panic("%s returning", __func__);
}

После того, как потомок вызывает execv(), необходимости поддерживать пересекающиеся адресные пространства уже нет, и, соответственно, копировать ничего при переключении контекста не нужно.

Проверка работоспособности


Собственно, для dash такой функциональности оказалось вполне достаточно :)

Для проверки в Embox можно запустить template x86/qemu

git clone https://github.com/embox/embox.git
cd embox
make confload-x86/qemu
make
./scripts/qemu/auto_qemu

После чего вызываем dash и внутри неё можно вызывать другие команды, например, ping.



Скорее всего, «потыкав» dash можно будет добиться какого-нибудь exception, не стесняйтесь создавать issue в нашем репозитории :)

+41
6.8k 60
Comments 1