Написание сопрограммы на языке C

Я давно ничего не публиковал в своем блоге. Но это из-за смены работы. Я надеюсь, вы понимаете, что никогда не было легко заново освоиться в новой среде с новыми людьми, сохраняя при этом крутой технический уровень обучения. Требуется время, чтобы настроить себя соответствующим образом. В любом случае, я написал Coroutine на языке C в качестве подготовки к моему предстоящему сообщению о C ++ 20 Coroutine. Сегодня мы увидим Как Coroutine работает изнутри?.

/! \: эта статья изначально была опубликована в моем блоге. Если вы заинтересованы в получении моих последних статей, подпишитесь на мою рассылку.

Предпосылки

Если вы абсолютный новичок, вы можете выполнить следующие требования. А если вы не новичок, знайте, что пропустить!

Основы сопрограмм

Что такое сопрограмма?

Сопрограмма - это функция / подпрограмма (точнее, кооперативная подпрограмма), которая может быть приостановлена и возобновлена.
Другими словами, вы можете рассматривать сопрограмму как промежуточное решение для нормальной функции и потока. Потому что после вызова функции / подпрограммы она выполняется до конца. С другой стороны, поток может быть заблокирован примитивами синхронизации (такими как мьютекс, семафор и т. Д.) Или приостановлен планировщиком ОС. Но опять же вы не можете принять решение о приостановке и возобновлении по нему. Как это делает планировщик ОС.
В то время как сопрограмма, с другой стороны, может быть приостановлена в заранее определенной точке и возобновлена позже при необходимости программистом. Таким образом, здесь программист будет иметь полный контроль над потоком выполнения. Это тоже с минимальными накладными расходами по сравнению с потоком.
Сопрограмма также известна как собственные потоки, волокна (в окнах), легкие потоки, зеленые потоки (в java) и т. Д.

Зачем нам нужна сопрограмма?

Как я обычно делаю, прежде чем узнавать что-то новое, вы должны задать себе этот вопрос. Но позвольте мне ответить:
Сопрограммы могут обеспечивать очень высокий уровень параллелизма с очень небольшими накладными расходами. Поскольку при планировании не требуется вмешательство ОС. В многопоточной среде вам придется нести накладные расходы на планирование ОС.
Сопрограмма может приостанавливаться в заранее определенных точках, поэтому вы также можете избежать блокировки общих структур данных. Потому что вы никогда не скажете своему коду переключиться на другую сопрограмму в середине критического раздела.
С потоками каждому потоку нужен свой собственный стек с локальным хранилищем потока и другими вещами. Таким образом, использование памяти растет линейно с количеством потоков, которые у вас есть. В то время как с совместными подпрограммами количество подпрограмм не имеет прямого отношения к использованию вашей памяти.
Для большинства случаев использования сопрограмма является более оптимальным выбором, поскольку она быстрее по сравнению с потоком.
И если вы все еще не уверены, то дождитесь моей публикации C ++ Coroutine.

Теория API переключения между точками

Прежде чем мы углубимся в сопрограмму, нам необходимо понять следующие основные функции / API для переключения контекста. Конечно, как и мы, с меньшим количеством конкретной теории и большим количеством примеров кода.

setcontext
getcontext
makecontext
swapcontext

Если вы уже знакомы с _5 _ / _ 6_, возможно, вам будет легче понять эти функции. Вы можете рассматривать эти функции как расширенную версию _7 _ / _ 8_.
Единственная разница в том, что _9 _ / _ 10_ позволяет только один нелокальный переход вверх по стеку. Принимая во внимание, что эти API-интерфейсы позволяют создавать несколько совместных потоков управления, каждый со своим собственным стеком или точкой входа.

Структура данных для хранения контекста выполнения

Структура типа ucontext_t, определенная ниже, используется для хранения контекста выполнения.
Все четыре (setcontext, getcontext, makecontext & swapcontext) функции потока управления работают с этой структурой.

typedef struct {
    ucontext_t *uc_link;    
    stack_t     uc_stack;
    mcontext_t  uc_mcontext;
    sigset_t    uc_sigmask;
    ...
} ucontext_t;

uc_link указывает на контекст, который будет возобновлен при выходе из текущего контекста, если контекст был создан с makecontext (вторичный контекст).
uc_stack - стек, используемый контекстом.
uc_mcontext хранит состояние выполнения, включая все регистры и флаги ЦП, указатель фрейма / базы (т. Е. Указывает текущий фрейм выполнения), указатель команд (т. Е. Счетчик программ), регистр связи (т. Е. Сохраняет адрес возврата) и указатель стека (т. Е. Указывает текущий предел стека или конец текущего кадра). mcontext_t - это непрозрачный тип.
uc_sigmask используется для хранения набора сигналов, заблокированных в контексте. Это не в центре внимания на сегодня.

`int setcontext(const ucontext_t *ucp)`

Эта функция передает управление контексту в ucp. Выполнение продолжается с точки, в которой контекст был сохранен в ucp. setcontext не возвращается.

`int getcontext(ucontext_t *ucp)`

Сохраняет текущий контекст в ucp. Эта функция возвращает в двух возможных случаях:

после первого звонка,
или когда поток переключается на контекст в ucp через setcontext или swapcontext.

Функция getcontext не предоставляет возвращаемое значение для различения случаев (ее возвращаемое значение используется исключительно для сообщения об ошибке), поэтому программист должен использовать явную флаговую переменную, которая не должна быть регистровой переменной и должна быть объявлена volatile, чтобы избежать константы распространение или другие оптимизации компилятора.

`void makecontext(ucontext_t ucp, void (func)(), int argc, ...)`

Функция makecontext устанавливает альтернативный поток управления в ucp, который ранее был инициализирован с помощью getcontext.
Член ucp.uc_stack должен указывать на стек соответствующего размера; обычно используется константа SIGSTKSZ или MINSIGSTKSZ.
Когда ucp переходит к использованию setcontext или swapcontext, выполнение начнется с точки входа в функцию, на которую указывает func, с argc аргументами, как указано. Когда func завершается, управление возвращается контексту, указанному в ucp.uc_link.

`int swapcontext(ucontext_t oucp, ucontext_t ucp)`

Сохраняет текущее состояние выполнения в oucp, а затем передает управление выполнением ucp.

[Пример 1]: понимание переключения контекста с помощью `setcontext` & `getcontext` функций

Итак, мы прочитали много теории. Давайте создадим из этого что-то значимое.
Рассмотрим приведенную ниже программу, которая реализует простой бесконечный цикл, печатающий «Hello world» каждую секунду.

#include <stdio.h>
#include <ucontext.h>
#include <unistd.h>
#include <stdlib.h>
int main( ) {
    ucontext_t ctx = {0};
    getcontext(&ctx);   // Loop start
    puts("Hello world");
    sleep(1);
    setcontext(&ctx);   // Loop end 
    return EXIT_SUCCESS;
}

Здесь getcontext возвращается с обоими возможными случаями, как мы упоминали ранее, а именно:

после первого звонка,
когда поток переключается на контекст через setcontext.

Остальное, я думаю, не требует пояснений.

[Пример 2]: понимание потока управления с `makecontext` и `swapcontext` функциями

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <signal.h>
#include <ucontext.h>
void assign(uint32_t *var, uint32_t val) { 
    *var = val; 
}
int main( ) {
    uint32_t var = 0;
    ucontext_t ctx = {0}, back = {0};
    getcontext(&ctx);
    ctx.uc_stack.ss_sp = calloc(1, MINSIGSTKSZ);
    ctx.uc_stack.ss_size = MINSIGSTKSZ;
    ctx.uc_stack.ss_flags = 0;
    ctx.uc_link = &back; // Will get back to main as `swapcontext` call will populate `back` with current context
    // ctx.uc_link = 0;  // Will exit directly after `swapcontext` call
    makecontext(&ctx, (void (*)())assign, 2, &var, 100);
    swapcontext(&back, &ctx);    // Calling `assign` by switching context
    printf("var = %d\n", var);
    return EXIT_SUCCESS;
}

Здесь функция makecontext устанавливает альтернативный поток управления в ctx. И когда переход сделан с ctx с использованием swapcontext, выполнение начнется с assign с соответствующими аргументами, как указано.
Когда assign завершится, управление будет переключено на ctx.uc_link. Которая указывает на back и будет заполнена swapcontext перед переходом / переключением контекста.
Если ctx.uc_link установлен в 0, то текущий контекст выполнения считается основным, и поток завершится, когда assign контекст завершится.
Перед вызовом makecontext приложение / разработчик должны убедиться, что изменяемый контекст имеет предварительно выделенный стек. И argc соответствует количеству аргументов типа int, переданных в func. В противном случае поведение не определено.

Coroutine на языке C

Изначально я создал пример одного файла. Но потом я понял, что в один файл будет слишком много. Следовательно, я разделил пример реализации и использования на другой файл, что сделает его более понятным и легким для понимания. ## Реализация сопрограммы
Итак, вот простейшая сопрограмма на языке c:

`coroutine.h`

#pragma once
#include <stdint.h>
#include <stdlib.h>
#include <ucontext.h>
#include <stdbool.h>
typedef struct coro_t_ coro_t;
typedef int (*coro_function_t)(coro_t *coro);
/* 
    Coroutine handler
*/
struct coro_t_ {
    coro_function_t     function;           // Actual co-routine function
    ucontext_t          suspend_context;    // Stores context previous to coroutine jump
    ucontext_t          resume_context;     // Stores coroutine context
    int                 yield_value;        // Coroutine return/yield value
    bool                is_coro_finished;   // To indicate the current coroutine status
};
/* 
    Coroutine APIs for users
*/
coro_t *coro_new(coro_function_t function);
int coro_resume(coro_t *coro);    
void coro_yield(coro_t *coro, int value);
void coro_free(coro_t *coro);

Просто игнорируйте API сопрограмм на данный момент.
Главное, на что нужно обратить внимание, - это обработчик сопрограмм, у которого есть следующее поле
function: содержит адрес фактической функции сопрограммы, предоставленной пользователем.
suspend_context: Используется для приостановки функции сопрограммы.
resume_context: Содержит контекст фактической функции сопрограммы.
yield_value: для хранения возвращаемого значения между промежуточной точкой приостановки и окончательным возвращаемым значением.
is_coro_finished: Индикатор для проверки состояния времени жизни сопрограммы.

`coroutine.c`

#include <signal.h>
#include "coroutine.h"
static void _coro_entry_point(coro_t *coro) {
    int return_value = coro->function(coro);
    coro->is_coro_finished = true;
    coro_yield(coro, return_value);
}
coro_t *coro_new(coro_function_t function) {
    coro_t *coro = calloc(1, sizeof(*coro));
    coro->is_coro_finished = false;
    coro->function = function;
    coro->resume_context.uc_stack.ss_sp = calloc(1, MINSIGSTKSZ);
    coro->resume_context.uc_stack.ss_size = MINSIGSTKSZ;
    coro->resume_context.uc_link = 0;
    getcontext(&coro->resume_context);
    makecontext(&coro->resume_context, (void (*)())_coro_entry_point, 1, coro);
    return coro;
}
int coro_resume(coro_t *coro) {    
    if (coro->is_coro_finished) return -1;
    swapcontext(&coro->suspend_context, &coro->resume_context);
    return coro->yield_value;
}
void coro_yield(coro_t *coro, int value) {
    coro->yield_value = value;
    swapcontext(&coro->resume_context, &coro->suspend_context);
}
void coro_free(coro_t *coro) {
    free(coro->resume_context.uc_stack.ss_sp);
    free(coro);
}

Наиболее часто используемые API для сопрограмм - это coro_resume & coro_yield, которые затягивают фактическую работу приостановки и возобновления.
Если вы уже сознательно ознакомились с приведенными выше примерами API переключения контекста, то я не думаю, что есть что объяснять для coro_resume & coro_yield. Его просто coro_yield перескакивает на coro_resume и наоборот. За исключением первого вызова coro_resume, который переходит на _coro_entry_point.
coro_new выделяет память для обработчика, а также для стека, а затем заполняет элементы обработчика. И снова getcontext & makecontext к этому моменту должно быть ясно. В противном случае перечитайте приведенный выше раздел «Примеры API переключения контекста».
Если вы действительно понимаете приведенную выше реализацию API сопрограмм, тогда возникает очевидный вопрос: зачем нам вообще _coro_entry_point? Почему мы не можем напрямую перейти к реальной функции сопрограмм?
Но тогда мой аргумент будет: «Как обеспечить время жизни сопрограммы?».
Технически это означает, что номер звонка на coro_resume должен быть аналогичен / действителен номеру звонка на coro_yield плюс один (для фактического возврата).
В противном случае вы не сможете отслеживать урожайность. И поведение станет неопределенным.
Тем не менее, функция _coro_entry_point необходима, иначе невозможно вывести, что выполнение коротина полностью завершено. И следующий / последующий вызов coro_resume больше не действителен.

Время жизни сопрограммы

Благодаря указанной выше реализации, используя обработчик сопрограмм, вы должны иметь возможность полностью выполнить функцию сопрограммы только один раз на протяжении всей жизни программы / приложения.
Если вы хотите снова вызвать функцию сопрограммы, вам необходимо создать новый обработчик сопрограмм. А остальная часть процесса останется прежней.

Пример использования сопрограммы

`coroutine_example.c`

#include <stdio.h>
#include <assert.h>
#include "coroutine.h"
int hello_world(coro_t *coro) {    
    puts("Hello");
    coro_yield(coro, 1);    // Suspension point that returns the value `1`
    puts("World");
    return 2;
}
int main() {
    coro_t *coro = coro_new(hello_world);
    assert(coro_resume(coro) == 1);     // Verifying return value
    assert(coro_resume(coro) == 2);     // Verifying return value
    assert(coro_resume(coro) == -1);    // Invalid call
    coro_free(coro);
    return EXIT_SUCCESS;
}

Вариант использования довольно прост:
Сначала вы создаете обработчик сопрограмм.
Затем вы запускаете / возобновляете фактическую функцию сопрограммы с помощью того же обработчика сопрограмм.
И всякий раз, когда ваша фактическая функция сопрограммы встречает вызов coro_yield, она приостанавливает выполнение и возвращает значение, переданное во втором аргументе coro_yield.
И когда фактическое выполнение функции сопрограммы полностью завершится. Вызов coro_resume вернет -1, чтобы указать, что объект-обработчик сопрограммы больше не действителен и время жизни истекло.
Итак, вы видите, что coro_resume - это оболочка для нашей сопрограммы hello_world, которая выполняет hello_world по частям (очевидно, путем переключения контекста).

Компиляция

Я протестировал этот пример в WSL с помощью gcc 9.3.0 и glibc 2.31.

$ gcc -I./ coroutine_example.c coroutine.c  -o myapp && ./myapp 
Hello
World

Напутственные слова

Вы видите, что волшебства нет, если вы понимаете Как ЦП выполняет код ...! хорошо продуманный Glibc предоставляет богатый набор API переключения контекста. И, с точки зрения разработчиков низкого уровня, это просто хорошо организованные и сложные в организации / обслуживании (если используются необработанные) вызовы функций переключения контекста. Мое намерение здесь состояло в том, чтобы заложить основу для C ++ 20 Coroutine. Потому что я считаю, что если вы посмотрите на код с точки зрения процессора и компилятора, тогда все станет легко рассуждать на C ++. Увидимся в следующий раз с моим постом C ++ 20 Coroutine.

Написание сопрограммы на языке C

Предпосылки

Основы сопрограмм

Что такое сопрограмма?

Зачем нам нужна сопрограмма?

Теория API переключения между точками

Структура данных для хранения контекста выполнения

int setcontext(const ucontext_t *ucp)

int getcontext(ucontext_t *ucp)

void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...)

int swapcontext(ucontext_t *oucp, ucontext_t *ucp)

[Пример 1]: понимание переключения контекста с помощью setcontext & getcontext функций

[Пример 2]: понимание потока управления с makecontext и swapcontext функциями