Real-Time Scheduling -- планировщик для RTOS

Цель статьи - восполнить нехватку терминологии в области управления процессами в системе реального времени, ОСРВ (анг. Real-Time OS). Надо определить, где наша RTOS располагатся относительно мировых достижений. В данной статье рассматривается терминология и обсуждается применимость методов планирования.

Хороший планировщик заданий - не обязательно сложный и ресурсоемкий алгоритм. Когда мы создаем операционную систему для контроллера мы работаем с голым железом. Ничто нас не ограничивает, мы можем использовать предоставляемые возможности контроллера на свое усмотрение. Эффективное управление можно описать без использования операционной системы. Необходимостью является довольно существенный объем системного кода, который выполняет переключение задач - планировщик заданий (анг. Task Scheduler).

Наша RTOS как идея зарождалась, когда мы еще использовали 8-битные контроллеры 51-й серии. Тогда не было никакой необходимости в планировании времени, наша ОС состояла из двух основных частей: жеского реал-тайма, который запускался по таймеру, и некоторой системной части - модульного ядра, которая выполнялась последовательно без переключения между заданиями. Позже, с переходом на 32 битные контроллеры ARM7TDMI, мы внедрили динамическое распределение памяти, и с переходом на Cortex-M стали активно использовать многозадачность. В качестве основного интерфейса был выбран CMSIS-RTOS API, с поддержкой тредов и полного набора возможностей синхронизации. В таком виде концепция ОС для конотроллеров просуществовала на протяжении 10 лет. Сегодня мы поддерживаем три системных интерфейса: CMSIS-RTOS API, CMSIS-RTOS v2, C11 <threads.h>. В этом году мы начали работу по масштабной поддержке системных интерфейсов POSIX. Реализация POSIX позволяет обеспечить переносимость прикладного кода между системами. Мы хотим сохранить эффективность управления заданиями и возможность гибкой настройки процессов планирования и в тоже время добавить переносимость для прикладного кода. Мы придерживаемся требования на сохранение эффективности кода: внедрение поддержки POSIX не должно вызывать существенного увеличения объема прошивок и снижения эффективности.

Терминология

Real-Time System

-- ОС в которой для успешной работы требуется точное соблюдение временных параметров запуска и исполнения задач.

Soft real-time, Hard real-time

RTOS cистемы условно можно разделить на две категории: с мягкими и жесткими требованиями. Различие можно определить так: нарушение временных параметров запуска заданий ведет к фатальным последствиям (hard real-time) или к временным сбоям, с возможностью дальнейшей работы (soft real-time). Пример жесткого реал-тайма: управение двигателем, управление рановесием (балансом), упраление летательным аппаратом. Обычно жесткие требования возникают применительно к задачам с периодической активностью. Soft real-time применятеся к апериодичским процессам.

Task -- задача (τ_i), процесс или тред, объект, для которого выполняется планирование времени запуска.
Job -- задание (J_i,j), процесс (Task_i) складывается из заданий.
Arrival Time (a_i,j) -- абсолютное время, когда процесс (τ_i) готов к исполнению очередного задания (J_i,j).
Burst Time, Execution time (c_i,j) -- время исполнения, интервал времени, когда процесс исполняется на CPU (Job), занимает процессорное время.
Absolute deadline, d_i,j, -- время от момента постановки в очередь до завершения выполнения задания (J_i,j). Время ожидания (arrival) и время работы (Execution time) в сумме образуют deadline (готовность)
worst case execution time (WCET) -- максимальное время исполнения.
minimum inter-arrival time (MIT) -- минимальная измеренная разница между задержками (arrival) на исполнение двух последовательных заданий одного процесса.

С одной стороны, для запуска периодических задач, когда мы заранее знаем период, мы можем использовать таймер. Для апериодических процессов планировщик анализирует времена и может распознавать периодическую активность измеряя WCET и MIT.

Priority Scheduling (PS)
-- планирование на основе приоритетов. Процессы орагнизуются в несколько очередей, каждая со своим приоритетом: сначала исполняются процессы с большим приоритетом, затем - с меньшим. Термин PS может применяться в сочетании с другими принципами планирования. Система, в которой PS - единственный механизм планирования, не жизнеспособная и не применима к RTOS, поскольку не гарантирует своевременное исполнение заданий.

Cooperative vs. Preemptive -- кооперативная и вытесняющая многозадачность. Кооперативная получается, когда процесс может передать управление только добровольно, например при ожидании ввода-вывода. Вытесняющая, когда определены правила переключения задач по времени работы. Правила переключения задач могут включать требования на приоритеты задач. Самая простая модель -- переключение задач на основе приоритетов: сначала выполняются все задачи с большим приоритетом, затем с меньшим. Процессы с большим приоритетом могут прерывать работу процессов с меньшим приоритетом. Процессы могут быть организованы в кольцевой буфер без нарушения порядка следования, первым вошел первым вышел(FIFO). В случае PS на основе приоритетов говорят об использовании нескольких очередей, каждая со своим приоритетом.

Rate-monotonic scheduling

Это система планирования, при которой частота запуска задачи (период работы) определяется ее приоритетом. Период работы до переключения обрано пропорционален приоритету задачи (1/T_i). Отношение максимальной продолжительности исполнения задания C_i = max{c_i,j} к величине периода (T_i), дает оценку загруженности процессора. Система планирования дает хороший результат, если общая загруженность не превышает 69% (в литературе пишут). RMS планирование предоставляет каждой задаче время работы задания порядка C/T.

Deadline-monotonic scheduling
Период работы до переключения обрано пропорционален дедлайну задачи, оценке времени завершения.

Earliest Deadline First (EDF)
-- алгоритм планирования на основе оценки времени завершения задания. Задания в очереди готовых к исполнению заданий сортируются по времени завершения. Система планирования EDF дает хороший результат в высоко нагруженных системах, если общая загруженность достигает 100% (в литературе так пишут).

Атрибутами задачи является периодичность запуска, предоставляемый временной интервал для работы (initial_budget) и deadline - время завершения. В нашей терминологии, временной интервал в пределах периода - бюджет, который начисляется с периодом, а deadline - расчетная величина, используется для сортировки очереди заданий.

Mixed-Criticality real-time systems

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

Hierarchical Scheduling

В системе, где есть иерархия процессов: процессороное время распределяется между виртуальными машинами, группами задач, процессами и тредами. Иерархия подразумеват минимум два уровня планировщика: один планирует время процесса, а другой занимается планированием времени треда в рамках выделенного времени процесса. Оба уровня настраиваются одинаковыми средствами и реализуются возможно одинаковыми алгоритмами. Увеличение иерархии - хорошо для загруженных систем, поскольку сокращается длина очереди на запуск отдельного треда. Еще один уровень планирования получается, если в систему добавлять признаки планирования, такие как идентификатор группы, например. Планирование может происходить на уровне виртуализации - еще один уровень иерархии.

Алгоритмы

FIFO - очередь процессов. Готовые к исполнению процессы перебираются по порядку из очереди, без нарушения порядка следования. Процесс может ожидать события или быть готовым к запуcку, так что представляем две очереди: процессы, которые ждут, и процессы готовые к исполнению. Процессы готовые к исполнению перебираются последовательно. В RTOS необходимо использовать вытесняющую многозадачность и обеспечить работу всех процессов. В сочетании с методом FIFO можно использовать кооперативную многозадачность. Расширением является планирование на основе приоритетов, нескольких очередей.

Round-Robin (RR) -- метод планирования с фиксированным интервалом переключения. На работу каждого процесса выделяется некоторое время, после чего происходит переключение на другой процесс. Метод позволяет избежать захвата процессора одной задачей. Совмещение метода RR с паланированием на основе приоритетов (PS) дает требование на динамическое или статическое изменение размера интервала в зависимости от приоритета задачи.

В POSIX используется похожая терминология для настройки политик планирования, режимов работы планировщика. Политика SCHED_FIFO - запрещает переключение задачи, SCHED_RR разрешает переключение задачи по времени, ограничивая интервал процессорного времени.

Можно получить хороший результат, если планирование выполняется методом RR. Когда я смотрю код контроллера - вижу, что метод RR - оптимальный выбор, сочетающий простоту и эффективность. Дело в том, что в RTOS не сильно загруженной, большая часть операций происходит асинхронно, каждая операция, которая требует отслеживания готовности или флага события не вызывает продолжительную загрузку CPU. Обработка событий выполняется в планировщике или по прерыванию, такми образом практически не реализуется необходимость принудительного переключения задач. Управление передается добровольно и возвращается по событию. Такое поведение характерно для систем с низкой нагруженностью. Однако можно представить некоторую ситуацию, когда отдельные процессы вызывают болшую загрузку CPU, например обработка графики или обработка сетевого трафика.

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

Мы могли бы определить для каждого процесса некоторый набор параметров, которые планировщик должен обеспечить. Среди этих праметров для периодических процессов можно указать: интервал запуска, длительность работы до переключения, джиттер - разброс времени ожидания запуска, дедлайн - ожидаемое время завершения.

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

Параметры запуска будут включать приод, требование на джиттер, фазу и опцию фазовой подстройки частоты запуска задачи. При этом все эти задачи должны быть с высоким приоритетом, не прерываться, обладать свойством кооперативная многозадачность, добровольно передавать управление. Остальные задачи в системе должны выполняться в фоне, когда процессор не занят обработкой задач с требованием hard real-time.

При этом каждая такая задача выполняется в своем тайм-слоте, и если выбивается из тайм-слота на время более допустимого отклонения, должна все-таки переключаться принудительно и выполняться с меньшим приоритетом. Важно, чтобы задержка одной задачи не приводила к сбою в других задачах. Ну вот так и описал основное свойство нашей операционки. У нас есть таймер, который используется планировщиком, и к нему можно прицепить некоторое количество таймерных задач или генерацию событий. Отклонение от времени запуска компенсируется, чтобы фазовая ошибка не накапливалась. Джиттер, ожидание запуска, время работы можно замерить и подвинуть фазы задач, чтобы они не мешали друг другу, тем самым минимизировать джиттер.

Для RTOS НУЖЕН Планировщик, который обеспечивает такое планирование на периодических процессах. И в тоже время хорошо работает на не пероидических задачах.

Попробую описать модель. Определяем очередь событий таймера, в которую добавляются треды с задержкой запуска, указанной с точностью до микросекунды. Эта очередь анализируется периодически по таймеру. Сортировка в очереди соответсвует понятию EDF. По таймеру, при наступлении расчетного времени запуска задача ставится на исполнение и прерывает текущую задачу (preempt). Запишем так:

// тред прерывает работу исполнения треда
    // в зависимости от приоритета расчитывается прибавка к бюджету
    thread->budget += BUDGET(thread->priority)
    // бюджет не должен превышать установленный лимит
    if (thread->budget > thread->init_budget)
        thread->budget = thread->init_budget;
    // если процесс не активен, добавляем его в начало очереди
    thread->priority= thread->sched.priority;
    sched_head(thread, thread->priority);

В планировщике проверяем условие, текущая задача переключается, если запрошено прерывание (preempt) или если бюджет исчерпан. Переключаем задачу и определяем ее приоритет, как низкий, ставим задачу в конец очереди с низким приоритетом.

if (running_thread->preempt) {
    running_thread->budget -= execution_time;
    sched_head(running_thread, running_thread->priority);
    __YIELD();
} else
if (running_thread->budget <= execution_time) {
  	running_thread->budget -= execution_time;
    running_thread->priority= running_thread->sched.low_priority;
  	running_thread->budget += BUDGET(running_thread->priority);
    sched_tail(running_thread, running_thread->priority);
    __YIELD();
}

В системе необходимо поддержать CPU_clock() - измерение штампа времени с точностью до такта процессора или такта системного таймера, из которого вычисляется execution_time до переключения.

Инициализация процесса происходит с атрибутами: sched_priority, sched_ss_low_priority, sched_ss_initial_budget. Можно немного доработать алгоритм и вычислять прибавку в бюджет BUDGET() на основе измеренного времени работы, thread->execution_time - время работы процесса до перехода в режим ожидания.

Aperiodic Task Scheduling

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

Апериодические сервисы называют Sporadic Server. Таким образом работу нашего планировщика можно описывать политикой SCHED_SPORADIC с набором атрибутов планирования. Такой сервис выполняется какое-то время (бюджетное, Q) с высоким приоритетом, затем приоритет занижается и разрешается прерывать задачу по времени, если она сама не отдала управление. Процесс ждет событие, затем выполняет некоторую работу в течение определенного времени (назовем бюджет) и уходит в ожидание. Если задача не ушла в ожидание, ей занижают приоритет. Измеренное время работы может использоваться для планирования и вычисления бюджета.

Для апериодических процессов можно определить еще ряд параметров, связанных с обработкой потока событий. Представим, что события возникают апериодически и может возникнуть ситуация, когда в момент возникновения события предыдущее событие еще не обработано. В этом случае мы ставим событие в очередь и начисляем дополнительное время на обработку события. Чтобы поток событий не захватил процессор нужно ограничивать число начислений в бюджет или запускать обработку событий с задержкой. Определяем дедлайн, когда это событие должно быть обработано и одновременно задаем начисление в бюджет - которое характеризует время выделенное на исоплнение.

Background Service

Это механизм запука апериодических задач в фоновом режиме, в режиме FIFO. В одной системе мы можем использовать несколько планировщиков. Мы можем выделить некоторый квант времени на работу фоновых процессов, к которым не предъявляются особые требования и не применяется PS планирование на основе приоритетов. В нашей системе к таким сервисам отностится сбор мусора и терминал вывода отладочной информации.

Этим же термином мы можем определить две очереди в планировщике: background, foreground. Очередь background обрабатывается с низким приоритетом, в своем временном интервале и может прерываться процессами из очереди foreground. Если задача выполняется слишком долго, можно ее автоматически перекинуть в из очереди foreground в очередь background.

Polling Server (PS)

Апериодические процессы, к которым не предъявляются требования к синхронности обработки могут запускаться по опросу готовности. Мы поддерживаем некоторый механизм запуска задач (Сервисов) по событиям с периодическим опросом состояния. По сути у нас в системе есть еще один планировщик. Если бы нам удалось определить такие задачи через определение политики планировщика, их можно было бы запускать с использованием pthread или определить, как событие, как struct sigevent, подобно тому как запускаются таймерные задачи, но с запуском процесса по событию. PS работает в фоновом режиме. Теоретически реализация PS может быть представлена, как периодический запуск планировщика со своей очередью. Отличие сервиса от обычного треда: при выходе из функции подобно таймеру, сервис снова ставится в очередь ожидания обработки.

Deferrable Server (DS)

Представляем себе вариант планирования на основе пропускной способности, задержка в начислении бюджета производится исходя из расчета заданной пропускной способности. Начисляения в бюджет должны происходить периодически с заданным интервалом. Чтобы обеспечить периодическую обработку, само начисление в бюджет должно быть отложено на заданный интервал времени, replenishment period.

Sporadic Server (SS)

Политика SCHED_SPORADIC d POSIX.1-2017 задает набор параметров:
sched_priority -- начальный приоритет исполнения
sched_ss_max_repl -- ограничение на число операций начислений в бюджет
sched_ss_low_priority, -- низкий приоритет
sched_ss_repl_period, -- задержка перед активацией начисления
sched_ss_initial_budget -- максимальное время работы без переключения

Количество необработанных запросов (replenishment operation) на пополнение бюджета ограничено величиной sched_ss_max_repl. Превышение этого ограничения ведет к снижению приоритета. Если задача в данный момент не активна или сигнал не может быть доставлен, сигнал ставится в очередь с высоким приоритетом и параметром activation_time + sched_ss_repl_period, чтобы обработка произошла в течение заданного интервала времени, затем увеличиваем счетчик запросов thread->pending.

Величина прибавки в бюджет replenish_amount может вычисляться исходя из того сколько времени было потрачено на выполнение операции в прошлый раз и не может првышать изначальный бюджет sched_ss_initial_budget.

Политика SCHED_FIFO позволяет устанавливать приоритет в интервале pthread_setschedprio(). В определении политики SCHED_RR бюджет фиксирован и обозначается параметром Round-Robin Interval. Стандарт POSIX определяет политку SCHED_SPORADIC, которую мы используем под свои нужды, или определяем некотороую нестандартную политику SCHED_DEADLINE, обеспечивающую обработку событий в заданный интервал времени. Политика SCHED_OTHER ничего не определяет точно, под ней можно скрыть нормальный режим работы планировщика с любым количеством параметров. POSIX дает характеристики политикам планировщика [POSIX: 2.8.4 Process Scheduling]:

SCHED_FIFO

Threads scheduled under this policy are chosen from a thread list that is ordered by the time its threads have been on the list without being executed; generally, the head of the list is the thread that has been on the list the longest time, and the tail is the thread that has been on the list the shortest time

SCHED_RR

This policy shall be identical to the SCHED_FIFO policy with the additional condition that when the implementation detects that a running thread has been executing as a running thread for a time period of the length returned by the sched_rr_get_interval( ) function or longer, the thread shall become the tail of its thread list and the head of that thread list shall be removed and made a running thread.

SCHED_SPORADIC

The sporadic server policy is based primarily on two time parameters: the replenishment period and the available execution capacity. The replenishment period is given by the sched_ss_repl_period member of the sched_param structure. The available execution capacity is initialized to the value given by the sched_ss_init_budget member of the same parameter. The sporadic server policy is identical to the SCHED_FIFO policy with some additional conditions that cause the thread’s assigned priority to be switched between the values specified by the sched_priority and sched_ss_low_priority members of the sched_param structure.

POSIX Определяет группы опций и функций, из которых формируется понятие Real-Time. C этого ракурса Real-Time определяется возможностью настройки параметров планировщика из кода программы, возможностями диагностикии измерения временных параметров задач, наборами функций для синхронизации задач. За каждым термином кроется некоторый функционал ядра и режимы планирования.

Real-time

asynchronous, synchronized and prioritized I/O, shared memory objects, process and range based memory locking, semaphores, timers, real-time signals, message passing, process scheduling;

Advanced Real-time

clock selection, process CPU-time clocks, monotonic clock, timeouts, typed memory objects;

Real-time Threads

thread priority inheritance and protection, thread scheduling;

Advanced Real-time Threads

thread CPU-time clocks, thread sporadic server, spin locks and barriers.

Использованные здесь термины применяются в виде опеределений в заголовке <unistd.h>, который и определяет функционал ядра RTOS.

Я представляю себе меню выбора, конфигурацию ядра, мы могли бы определить ряд параметров конфигурации, которые влияют на поддержку опций и выбор способов планирования в ядре RTOS.

1. Mixed-Criticality/Иерархическое планирование - возможность разделения процессов на группы. Можно предложить выделить группы: hard real-time, soft real-time, background service.
2. RMS, EDF или RR -- методы планирования, методы выделения бюджета задаче. При этом в одном планировщике методы планирования могут сочетаться и применяться индивидуально к каждому процессу. RR рассматриваем, как частный случай при котором бюджет задания фиксирован.
3. Динамическое управление производительностью системы исходя из оценки загруженности системы.
4. Поддержка Deferable Server/Sporadic Server, сетевые интерфейсы (дарйверы) с ограниченной пропускной способностью. Предполагает поддержку очереди событий. О дин из видов события - начисление бюджета и повышение приоритета.
5. Поддержка Polling Server.

В настоящее время в нашей RTOS системе реализуется Mixed-Criticality с двумя группами на основе приоритета. hard real-time периодические процессы не могут прерываться по времени, по истечении бюджета задание переключается и переходит в группу с меньшим приоритетом, soft real-time -- использует RR - метод планирования с фиксированным интервалом переключения заданий. Экспериментально реализован метод планирования с выделением интервала переключения задач динамически на основе приоритета. Экспериментально поддержан механизм занижения приоритета по истечении бюджета. Поддержан механизм Deferred/Sporadic Service Экспериментально поддерживается EDF метод планирования. Политика EDF Реализуется с подменой FIFO очереди заданий на очередь с приоритетами. Задания могут исполняться в фоновом режиме background service (FIFO, Cooperative Miltitask), и в режиме опроса готовности (Polling services, FIFO, Cooperative), при этом весь поток background service участвует в процессе планирования, как единый процесс со своим приоритетом. Такое сочетание выведено опытным путем и применяется в условиях низкой загруженности системы. Динамическое управление производительностью выражено циклом WFE -- ожидание события в фоновом процессе. Поддержка сервисов в ядре задается через определения #define osFeature_* в конфигурационном файле системы <board.h>, <cmsis_os.h>(поддержка системных интерфейсов CMSIS RTOS) и набором опций _POSIX_* в файле <unistd.h>, который классифицирует поддержку системных интерфейсов POSIX.

POSIX.1-202x: CPU-clocks, Monotonic clock, и таймауты

Мы затронули интересную тему, когда занимались реализацией CPU-clock и очередей событий в планировщике.
Планировщик живет одновременно в нескольких местах:
1. обработка прерываний от таймера и
2. процесс переключения задач.

В качестве системного таймера мы традиционно используем системный таймер SysTik, но можем использовать еще множество других таймеров. В частности, мы стали использовать счетчик циклов DWT для измерения CPU-clock, что позволяет выразить время работы треда в тактах процессора. В нашей системе SysTik работает на частоте 25кГц. Когда мы рассматриваем многоядерные архитектуры, может быть несколько системных таймеров, каждый со своим разрешением. Идентификатор системного таймера, на котором работает процесс, можно запросить функцией pthread_getcpuclockid() (TCT - POSIX Thread CPU-clock option). В новом стандарте POSIX.1-202x предлагают поддержать ожидание с явным указанием идентификатора системного таймера. Стандарт предлагают дополнить функциями синхронизации тредов с суффиксом *_clockwait, по аналогии с суффиксом *_timedwait.

sem_clockwait
pthread_mutex_clocklock
pthread_cond_clockwait
pthread_rwlock_clockrdlock
pthread_rwlock_clockwrlock
mq_clockreceive
mq_clocksend
. . .

Таким образом мы предполагаем несколько очередей ожидания в планировщике и предполагаем распределение работы планировщика между несколькими системными таймерами. Каждый системный таймер обрабатывает свою очередь событий.

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

POSIX предполагает использовать функции *_clockwait ради отказа от CLOCK_REALTIME в пользу CLOCK_MONOTONIC. Функции *_timedwait используют CLOCK_REALTIME, который должен соответствовать TIME_UTC в стандарте языка Си. CLOCK_REALTIME не является монотонным, может подстраиваться при необходимости. В обоих случаях виден некоторый изъян с неоднозначностью вычисления интервала времени, на который настраивается срабатывание таймера. Приходится дважды пересчитывать: сначала в прикладном коде к интервалу ожидания прибавлять текущее время, затем в системном коде вычитать абсолютное время и высчитывать задержку на срабатывание. Это черевато сбоями при подстройке времени. Если мы обеспечим монотонность CLOCK_REALTIME или станем выражать абсолютное время через монотонное время CLOCK_MONOTONIC, то таких проблем не возникает.

// пример настройки интерфейса POSIX
pthread_getcpuclockid(self, &clock_id);
clock_gettime(clock_id, &abstime);
timespec_add (&abstime, interval);
sem_clockwait(sem, clock_id, abstime);

Нужно стандартизировать функцию timespec_add(), чтобы убрать неоднозначность вычисления временных интервалов. Одновременно надо стандартизировать функцию сравнения timespec_cmp() для использования в со стороны RTOS.

С2х определяет таймеры TIME_THREAD_ACTIVE, которые в POSIX соответсвуют выбору CLOCK_THREAD_CPUTIME_ID. В нашей интерпретации эти времена могут высчитываться с большей точностью, чем CLOCK_MONOTONIC, которое обновляется в системном таймере и имеет сравнительно низкое разрешение.

В С1x всего три функции, которые завязаны на время ожидания: mtx_timedlock() cnd_timedwait() и thrd_sleep(). Ожидание задается дедлайном относительно TIME_UTC, что соответствует CLOCK_REALTIME в POSIX.

// пример настройки интерфейса C1x
struct timespec ts;
timespec_get(&ts, TIME_UTC);
timespec_add(&abstime, interval);
mtx_timedlock(mtx, &ts);

Внутри фукнции mtx_timedlock приходится еще раз запрашивать timespec_get и вычитать из абсолютного времени величину TIME_UTC, чтобы получить интервал ожидания - таймаут. Я думаю, как бы определить эти три функции, чтобы при компиляции не надо было два раза запрашивать системное время и не надо было бы прибавлять и вычитать переменную величину, чтобы с некоторой вероятностью опять получить значение интервала. Это не удобно. Это плохо, хочу использовать относительные времена ожидания.

// расшифровка, псевдокод
struct timespec ts;
ts = system_time; // копируем время
// добавляем смещение UTC
ts.tv_sec += UTC.tv_sec, ts.tv_nsec += UTC.tv_nsec;
if(ts.tv_nsec>=1000000000) {// коррекция при сложении
   ts.tv_nsec-=1000000000;
   ts.tv_sec++;
}
// добавляем Интервал времени ожидания
ts.tv_sec += interval.tv_sec, ts.tv_nsec += interval.tv_nsec;
if(ts.tv_nsec>=1000000000) {// коррекция
   ts.tv_nsec-=1000000000;
   ts.tv_sec++;
}
ts2 = system_time; // копируем время еще раз
ts2.tv_sec = ts.tv_sec - (ts2.tv_sec + UTC.tv_sec);
ts2.tv_nsec= ts.tv_nsec - (ts2.tv_sec + UTC.tv_nsec);
// вычисляем таймаут в микросекундах
timeout = (ts2.tv_sec*1000000 + ts2.tv_nsec/1000);
// передаем управление системе
syscall(mtx_timedlock, mtx, &timeout);

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

Давайте представим, что людьми предложившими использовать абсолютное время для ожидания мьютекса двигали возвышенные цели. Например, они предполагали, что обработка системного вызова происходит в другом часовом поясе и на другом компьютере, где TIME_MONOTONIC другой и их нельзя сравнивать. Тогда что мешает сравнивать интервалы?!

Следующая проблема, в ядре. Счетчик микросекунд - переменная, которая считает время с большим разрешением, переодически переполняется. Чтобы переполнение не сказывалось на проверке и разнца монотонно возрастала, мы приводим тип к беззнаковому:
(unsigned int)(clock() - activation_time) >= timeout

Как сделать тоже самое с абсолютным временем я не знаю. Все что приходит в голову - считать разницу в 64-битных числах. Т.е. в этом случае нам придется пересчитывать 64 битное монотонно возрастающее время в struct timespec и обратно бесчисленное количество раз. Хотим избавиться от бессмысленных операций. Вспоминаются числа с фиксированной точкой, можно хранить время в виде числа double.
Следующее приближение: как вычисление времени выглядит с использованием 64 битного времени:

// расшифровка
struct timespec ts;
ts = system_time; // копируем время
ts+= UTC;
ts+= interval;
ts2 = system_time; // копируем время еще раз
ts2 = ts - (ts2 + UTC);
timeout = ts2;
syscall(mtx_timedlock, mtx, &timeout);

Казалось бы такую последовательность возможно упростить до одного присваивания timeout = interval. Чтобы это стало возможным, нужно чтобы system_time не менялся. Т.е. при оптимизации компилятор должен взять значение system_time из регистра, иначе не упростит.

Следующее приближение. Время ожидания - аблолютное, выражено через монотонное системное время.

// расшифровка
struct timespec abstime;
abstime = system_time + UTC + interval;
abstime-= UTC;
syscall(mtx_timedlock, mtx, &abstime);

Со стороны системы обработка выглядит так:

// расшифровка
activation_time = system_time;
timeout  = abstime - activation_time;
. . .
if ((system_time - activation_time) >= timeout) . . .

Вот в таком виде я готов смириться, в ядре лишних действий не совершается.
Для реализации такого способа нужно, чтобы время складывалось и вычиталось, как 64 битное число:
t64 = ((uint64_t)ts.tv_sec<<32) | (uint32_t)ts.tv_nsec;
Коррекция 64 битного времени при сложении:
if ((uint32_t)t64 >= 1000000000) t64 += (1<<32)-1000000000;
Коррекция 64 битного времени при вычитании:
if ((int32_t)t64 < 0) t64 -= (1<<32)-1000000000;

Нужно дать свободу пользователю и хотелось бы придержиываться стандарта. При работе с 64 битным временем упакованным в ту же структуру struct timespec, вычисление интервала может выглядеть так:

// расшифровка
timespec_get(struct timespec *ts, int base){
    ts->u64 = system_monotonic_time + CLOCK_OFFSET(base);
}
timespec_add(struct timespec *ts, struct timespec *interval){
    ts->u64 += interval->u64;
}
mtx_timedlock(mtx_t *mtx, struct timespec *ts){
    ts->u64 -= CLOCK_OFFSET(TIME_UTC);
// выполнить коррекцию
	if(ts->tv_nsec<0) t64 -= (1<<32)-1000000000;
	else
	if(ts->tv_nsec>=1000000000) ts->u64 += (1<<32)-1000000000;
     . . .
}

CLOCK_OFFSET(TIME_MONOTONIC) равен нулю. Если все три функции доступны для оптимизации, то возможно компилятор упростит выражение до
ts->u64 = system_monotonic_time + interval->u64;

Заключение
Весь этот поток сознания вызыван стремелением рабочей группы по стандартизации POSIX привнести ряд функций в стандрт ради привязки времени ожидания к монотонному времени. Я в свою очередь стал анализировать, к чему это приводит в коде RTOS и что требуется реализовать в ядре для поддержки этого функционала. Меня очень беспокоит "кривизна" вычисления задержек и связанные с этим сбои. Хотелось бы избежать этих проблем. Проблему я вижу в том, что изначально принято использовать абсолютное время для ожидания, побочные явления от такого подхода могут привести к сбоям задач работающих в условиях жестких требований к времени исполнения (hard real-time).
Источник:
[1] The Open Group Standard, Additional APIs for the Base Specifications Issue 8, Part 1, 2021
[2] P1003.1™-202x, Draft 2.1+, September 2022 – Portable Operating System Interface (POSIX®)

POSIX на контроллере Cortex-M

POSIX - Portable Operating System Standard. Стандарт описывает переносимый (портируемый) программный интерфейс для юниксоподобной операционной системы. Юникс разработан вместе с языком Си, язык включает ряд библиотечных функций для работы с операционной системой. POSIX включет в себя стандартные библиотеки Си. Включает разделы посвященные файловой системе и работе с периферийными устройствами, PTHREAD - POSIX Thread и механизмы синхронизации тредов так же являются частью POSIX. Кроме того, стандарт наполнен комментариями почему так сделано и как должны работать те или иные функции операционной системы для переносимости прикладного кода.

Стандарт операционной системы POSIX.1-2017 в тоже время является стандартом IEEE Std 1003.1™-2017, и представлен на сайте The Open Group, как Technical Standard Base Specifications, Issue 7.

С некоторых пор мы реализуем поддержку POSIX в контроллере наравне с поддержкой библиотек стандарта C11, С2x и CMSIS-RTOS. Нужно это для переносимости прикладного программного обеспечения туда и обратно.

Первое впечатление - стандарт обширный - занимает около 4тыс. страниц в стиле man, сотни и сотни различных функций. Кажется, если такой объем, даже его конкретную часть, попробовать затолкать в контроллер, ничего не выйдет, памяти не хватит. Теперь, после нескольких месяцев изысканий, могу опровергнуть это утверждение. Создать POSIX совместимую ОС под контроллеры Cortex-M возможно.

1. C11 определяет интерфейс API для работы с тредами, мьюетексами и некондицией, и множество других библиотечных функций. C11 треды мы приняли за основу. Они выглядят проще чем posix pthread и в тоже время вполне по-взрослому, не хуже чем родные треды в OS Solaris. Отличие только в том, что у них нет атрибутов, а возвращаемое значение при ожидании завершения треда - int, целое число. Под Linux и Windows мы используем обертку для представления тредов в виде C11, под которой скрывается pthread и наоборот под RTOS мы можем поддерживать pthread без атрибутов, под которым скрываются треды C11. Атрибуты тредов не сильно важная деталь, по большей части она влияет на возможность настраивать алгоритм планировщика и на возможность предоставления доступа другим процессам через Shared Memory. При детальном рассмотрении атрибуты для предоставления доступа другим процессам PROCESS SHARED не требуются, поскольку этот механизм задействован автоматически при создании объекта поверх Shared Memory.

2. Для переносимости приложений связанных с обработкой данных или обработкой протоколов управления и сбора данных оказалось важным в точности соблюдать способы работы с системным временем, уметь точно настраивать интервалы. см C11 time.h. В частности мы широко используем измерение интервалов времени с использованием clock_gettime и nanosleep. (CS, _POSIX_CLOCK_SELECTION (Clock Selection option)) -- эти функции перекочевали в контроллер.

3. Близко по смыслу расположены таймеры, их можно использовать для генерации сигналов и для периодического запуска функций обработки. (TMR) _POSIX_TIMERS (Timers). В POSIX таймерные функции можно запускать в режиме треда. В итоге мы переписываем API RTOS в пользу POSIX таймеров.

4. _POSIX_SEMAPHORES простые семафоры для подсчета ресурсов, простые PLAIN мьютексы. Почему простые. Простые предполагают работу в общей памяти и их можно реализовать на базе атомарных операций. Концепция семафоров POSIX совместима c RTOS.

5. Есть примитивы синхронизации, которые мы не применяли до сих пор в контроллерах, потому что они предназначены прежде всего для синхронизации процессов в многоядерных архитектурах, но возможно они понадобятся когда-нибудь. Первое - это спинлоки, втрое - барьеры синхронизации. Я понимаю, что барьеры синхронизации возникают в задачах конвейерной обработки данных, это то, что пригодится на многоядерной системе. Про спинлоки такого сказать не могу, при прочих равных мы выбираем неблокирующие методы и стараемся не использовать такие методы. Все что можно сделать на спинлоках можно реализовать с использованием семафоров. В чем разница между спинлоками и мьютексами. Мьютекс подразумевает обладание, использовать мьютекс может только процесс владелец этого мьютекса. В нашей реализации нет разницы между мьютексом и спинлоком. RWLock - это еще один вид объектов, которые не задействованы в контроллерах. Мы все время ищем некоторый способ описать проблему Reader-Writer таким образом, чтобы читатели вообще никак не прерывали свою работу и не уходили в ожидание. В этой связи формулируем метод основанный на отложенных изменениях (отложенных транзакциях) и версиях структуры объекта (списка). В настоящее время у нас есть заготовка, модель интерфейса RWLock, без одной функции, она позволяет не блокировать читателей. Т.е. фактически мы говорим об отказе от интерфейса RWLock в пользу неблокирующих методов, и о маскировке под видом RWLock некоторого другого механизма типа STM(Транзакций памяти) или RCU. Транзакции памяти можно описать через манипуляцию страницами виртуальной памяти, атомарно подменяя страницы памяти.

6. Модель работы с флагами событий, сигналы _POSIX_REALTIME_SIGNALS. Сигналы вызывают некоторое замешательство... При внешнем сходстве, механизмы распространения сигналов в POSIX существенно более сложные, чем в RTOS. Поддержка традиционных сигналов и Realtime кажется громоздкой. Сигналы POSIX распространяются и доставляются тремя путями: Традиционно, через signal handler на уровне процесса, с привязкой к pid; сигналы ставятся в очередь, очередь привязана к pid и наследуется в какой-то мере тредами, реалтайм сигналы можно задействовать по маске и привязать к треду. Но в конечном счете весь набор этих возможностей ведет к медленной системе с обработкой структуры дерева процессов(тредов). Мы говорим о том, чтобы приспособить интерфейсы POSIX под наши задачи, под флаги процессов, а не о том, чтобы реализовать все возможности доставки сигналов описанные в POSIX.

// Обработка сигналов в CMSIS-RTOS
result = osSignalWait(маска флагов, таймаут)
if (result == osEventTimeout) {// обработка исключений
	. . .
} else {// обработка событий
	if (событие 1) ...
	if (coбытие 2) ...
}

Что-то похожее предлагает (POSIX REALTIME SIGNALS)

// POSIX REALTIME SIGNALS
signo = sigtimedwait(маска сигналов, таймаут)
if (signo<0) { // обработка ошибок
	if (errno==EAGAIN)...
	if (errno==EBUSY)... 
	if (errno==EINRT)...
} else { // обработка событий
	if (coбытие 1) ...
	if (coбытие 2) ...
}

Пояснения:
Выглядит близко к тексту. Сигналы в POSIX распространяются странными путями [см. POSIX]. Мне ясны три пути. Первый путь - традиционный, свойственный функции kill(), сигналы возникают в процессе, процесс может быть остановлен с ошибкой или обработать сигнал, используя, один из вариантов обработки. Существует множество предопределенных сигналов, которые генерируются по разным событиям. Вторым слоем идет метод поставить обработку сигналов в очередь. Каждому процессу приписываем входящую очередь сигналов. При этом сигнал уже может быть с параметром. Третий нарост, все ломается при использовании тредов, не ясно какой тред будет обрабатывать очередь сигналов. Предлагается использовать маски сигналов в тредах, и не ясно каким чудом сигнал будет доставлен в тред. Четвертый нарост - это возможность запускать обратные вызовы по случаю прихода сигналов. Эта возможность понятным образом реализуется применительно к Асинхронному вводу/выводу (AIO), Таймерам (TMR) и очередям сообщений (MSG).

Если не копаться в тонкостях внутренней реализации механизмов доставки сигналов, интерфейс sigtimedwait() позволяет описать механизм доставки через флаги процесса. У RTOS флаги процесса в каждом треде свои, а у POSIX не ясно. Таким образом, можно применить интерфейс к RTOS, но это может работать несколько иначе в POSIX системе. Для совместимости с POSIX следует использовать маски сигналов, и учитывать тот факт, что свободными для использования считаются сигналы в диапазоне [SIGRTMIN, SIGRTMAX]. Кстати, переносимость на этом заканчивается, Сигналы далеко не везде поддерживаются.

В POSIX широко используется передача кодов ошибки через errno. Критика: errno - это пережиток старины. Errno - это "костыль" для старой концепции юниксо-подобной ОС. Концепция была в том, что у процесса есть некоторый контекст, который включает ряд переменных: errno, environ, текущую рабочую директорию, идентификацию пользователя и т.д., включая, между прочим, контекст разбора множества функций, которые ныне не попадают в категорию Thread-Safe и Reentrant. Результат работы функции ожидания может включать код ошибки. Более экономичный способ передачи кода ошибки - передавать в отрицательных числах результата.

Сама по себе система заполнения и расшифровки errno вызывает лишние действия, как в библиотеке, так и в приложении. Хотя в нашей системе RTOS мы поддерживаем существование errno, я считаю - это пережиток прошлого и от него надо избавляться.

7. Вместо работы с файлами, у нас есть база данных, директория (иерархия системных объектов в форме дерева, в узлах - директории, на ветвях - файлы или устройства; POSIX под директорией понимает список файлов в узле дерева). В дереве размещаются объекты предопределенных типов. Мы можем запросить объект и получить его образ в памяти используя путь в дереве. Альтернативой является поиск в хеш-таблице или в дереве по уникальному идентификатору объекта. В POSIX определено сочетание {ino_t, dev_t} которое дает уникальный идентифкатор системного объекта в рамках системы или носителя. В нашем случае все данные, кроме разве что картинок и медиа-файлов, располагаются в памяти, отображаются в память. Использовать интерфейс open-read не целесообразно, он ведет к многократному копированию данных, в то время, как чтение возможно напрямую из флеш-памяти.

Для исключения копирования файлов мы поддерживаем ряд функций свойственных POSIX: отображение файлов в память _POSIX_MAPPED_FILES, защиту памяти _POSIX_MEMORY_PROTECTION. Мы готовы поддерживать обращение в стиле open() к директории (базе), но только с нечеловеческими путями. Нет смысла поддерживать текстовые пути. Возможно использовать коллекции объектов и обращаться к объектам с использованием типизованных идентификаторов {ino_t, dev_t}. Использование типизованных идентификаторов может быть вполне совместимо с представлением мультибайтовых строк c11. Только в нашем случае каждый символ мультибайтовой строки - это идентификатор объекта в структуре директории (в дереве устройств). Мы говорим о том, чтобы поддерживать систему имен в иерархии объектов, чтобы адресовать объекты по их уникальным идентификаторам. С точки зрения реализации, директорию (иерархию объектов в форме дерева) поддерживать оказывается проще, чем дерево с уникальными идентификаторами. Хеш таблица или бинарное дерево идентификаторов может располагаться как в каждой директории, так и в точке монтирования.

Мы говорим о расширении концепции поиска в дереве (см. [Раздел 4.13 POSIX.1-2017]) через представление идентификаторов в форме мультибайтововой строки, и представление уникального идентификатора объекта в форме {ino_t, dev_t}.

В POSIX удвоили количество системных функций относящихся к файловой системе, чтобы иметь возможность адресовать элементы поддерева, блокируя удаление фрагментов дерева. Это такая замечательная идея, суть которой в том, что в процессе поиска файлов том можно размонтировать, том или директорию можно удалить. Спасение от этого видится в увеличении числа ссылок на объект иерархии в процессе поиска.. Два параметра нужны, чтобы блокировать на изменение фрагмент дерева, пока ведется поиск в дереве. В тоже время такой способ позволяет адресовать объекты без разрешения путей, с использованием уникальных идентификаторов. В результате мы выделяем три идентификатора: корневую директорию (/) директорию системных устройств (/dev) и (CWD - рабочую директорию, где создаются обычные файлы). Нам нужна функция поиска в директории, с использованием хеш таблиц, которая с одной стороны следует стандарту POSIX, с другой стороны удовлетворяет нашим требованиям - использует идентификаторы вместо имен.

При создании файлов с использованием путей мы хотим иметь возможность автоматически именовать системные устрйства и файлы с использованием уникальных идентификаторов {ino_t, dev_t}, ino - уникальный номер объекта для данного типа устройства dev.

В итоге мы добавляем с систему RTOS следующий функционал, для регистрации объектов (системных устройсв и файлов) в дереве:
1. Разрешение имен в дереве относительно выбранных директорий.
dtree_path(at_dev, path, filename) -- разрешение имен файлов
dtree_link(at_dev, filename, dev) -- устанавливает ссылку линк в дереве.
dtree_nlink(dev) -- атомарно увеличивает число ссылок на системный объект.
dtree_unref(dev) -- уменьшает число ссылок, удаляет неиспользуемые объекты.
dtree_mknod(at_dev, filename, mode, OID) -- объект создается в режиме mode
Если OID при создании содержит только идентификатор типа, то нумерация объекта выполянется последовательно. filename - может быть NULL, в таком случае нумерация объектов выполняется последовательно с использованием уникального идентификатора и не использует имена файлов.

Начальная загрузка. Нужна начальная инициализация иерархии системных объектов, структуры директорий, файлов и регистрация системных устройств. Мы в связи с этим сформулировали сопособ загрузки из архива, архив - это файловая система ориентированная на чтение и прямое отображение в память. Можно использовать традиционный формат типа cpio, описанный в POSIX. А можно сделать, чтобы начальная загрузка использовала разметку данных от файловой системы. Для переносимости нужно поддержать один из форматов cpio.

Мы хотим регистрировать записи в файловой системе (RFS - Read-only FS) статически, определяя объекты в исходном коде как макросы, определяя константы в специальном сегменте данных, без какого либо дополнительного кода, без утилиты для создания архива.

Мы определяем записи файловой системы, как данные относящиеся к сегменту памяти "начальная загрузка". На этапе компиляции формируется сегмент данных, дописываемых в конец образа загрузки. Для этого мы определяем RFS - макросы для статической регистрации системных объектов в Read-only File System файловой системе, отображаемой в память. Таким образом, мы хотим создавать начальную структуру директорий и регистрировать системные устройства и системные объекты, включая Shared Memory Objects, Semaphores, MQueue, FIFO, ... Мне почему то хочется сразу заложить в функционал RFS возможность шифрования (криптографической защиты) данных на носителе, и возможность упаковки данных типа LZ4, LZO, LZJB2.

В POSIX принято все системные объекты называть устройствами. Файловая иерархия, - дерево системных объектов, направленный граф. В узлах дерева располагаются директории - списки объектов, директории наследуют информацию об устройстве в точке монтирования, файл привязан к классу драйвера устройства через директорию. Файл это системный объект, а вот приложения работают с дескриптором файла - идентификатором, дескриптору файла соответствует некоторый объект Open File Description, который собственно содержит информацию о позиции записи/чтения и ссылается на системный объект типа Файл. В то же время для работы с большинством объектов не нужно создавать отдельные сущности для поддержки сессии и по дескриптору можно напрямую получить сам системный объект. Всего насчитывается конечное число объектов около десятка: Файл, Директория, Разделяемый объект в памяти, сегмент памяти, семафор, очередь, FIFO, Symlink, Сокет. POSIX кроме этого определяет еще ряд непонятных устрйоств типа блочное устройство и символьное устройство. Концептуально POSIX разделяет понятие STREAM - поток данных в понимании POSIX и stream - объект типа FILE в понимании стандарта Си <stdio.h>. STREAM подразумевает очередь транзакций чтения/запись.

Общее впечатление от детального изучения стандарта - он не додуманный, обширный и не дододуманный. Я смотрел драфты на стандарт, в него продолжают добавлять заплатки, чтобы закрыть проблемы работы уже стандартизированных интерфейсов. Одна из таких проблем - синхронизация процессов в Realtime и монотонное время. Другая - сигналы. Третья - thread-safe, signal-safe, reentrancy, многие функции не обладают этим свойством. В результате количество фукнций удваивается и утраивается.

• [POSIX.1-2017] The Open Group Base Specifications Issue 7, 2018 edition IEEE Std 1003.1™-2017 (Revision of IEEE Std 1003.1-2008)

GF2p8 Кодирование Рида-Соломона в изоморфном представлении поля

Коды Рида-Соломона считаются через экспоненты и логарифмы по таблице. А у нас с внедренеием инструкций Intel GFNI появилось две другие возможности: использовать инструкцию умножения и аффинные преобразования.

Для примера я взял коды РС из проекта библиотеки генеации QR-кодов. Там используется полином поля G(2^8) P = 0x11D. Кодирование производится в цикле. При переходе к операциям умножения в поле 0x11D, цикл кодрования выглядит так.

	for(i = 0; i < data_length; i++) {
		uint8_t fb =  data[i] ^ Z[0];
		for(j = 0; j < ecc_length-1; j++) {
			Z[j] = Z[j+1] ^ gf2p8_mul(fb, g[j], 0x11D);
		}
		Z[j] = gf2p8_mul(fb, g[j], 0x11D);
	}
	for(i = 0; i < ecc_length; i++) {
		ecc[i] = Z[i];
	}

Преобразование алгоритма для расчета в изоморфном представлении поля с образующим полиномом 0x11B:

	const uint64_t M = 0xFFAACC88F0A0C080;
	const uint64_t Mr= 0xFFAACC88F0A0C080;

	for(i = 0; i < data_length; i++) {
		uint8_t fb =  affine(M,data[i]) ^ Z[0];
		for(j = 0; j < ecc_length-1; j++) {
			Z[j] = Z[j+1] ^ gf2p8_mul(fb, g[j], 0x11B);
		}
		Z[j] = gf2p8_mul(fb, g[j], 0x11B);
	}
	for(i = 0; i < ecc_length; i++) {
		ecc[i] = affine(Mr, Z[i]);
	}

Данное преобразование предполагает так же изоморфные преобразования компонент вектора генератора кодов (g). Векторизация алгоритма может быть выполнена по вложенному циклу.

[1]The comeback of Reed Solomon codes N.Drucker, Sh.Gueron, V.Krasnov

Приложение

Довеском идет код для расчета остатка от деления на 255. Когда в контроллере нет полиномиального умножения, приходится использовать способ расчета умножения и инверсии с использованием таблиц логарифмов и экспонент.

// Multiplication in Galua Fields
int gf_mul(int x, int y) {
    if (x == 0 || y == 0) return 0;
    return exp_[(log_[x] + log_[y])%255];
}
// Inversion in Galua Fields
int gf_inv(int x) {
    return exp_[255 - log_[x]];
}
// Division in Galua Fields
int gf_div(int x, int y) {
    if (x == 0) return 0;
    return exp_[(log_[x] + 255 - log_[y]) % 255];
}

Самая неудобная операция в этом случае - вычисление остатка от деления на 255. Избавился от деления.

// Остаток от деления на 255
uint8_t mod255(unsigned v) {
	uint32_t q = (v*0x1010102UL)>>(24);
	return q;
}

// Остаток от деления на 255
uint8_t mod255(unsigned v) {
	return v + (v>>8);
}

А этот вариант самый простой, применим для сложения логарифмов.

Такая вот оптимизация.

[2] Исходники на Github

Крипто-Рубль. Изоморфные преобразования при вычислении Хеш функции Stribog

Для расчета хеш функции ГОСТ Р 34.11-2012 "Stribog" выполняется табличная подстановка в цикле - это общепринятая практика.

Если вернуться к определению алгоритма, его описывают последовательностью матричных операций S, P, L, X:
S - подстановка Sbox для каждого элемента 8x8 байт.
P - транспонирование матрицы 8х8 байт
L - линейное преобразование.
X - исключающее ИЛИ.

Линейное преобразование может быть представлено операцией умножения матрицы коэффициентов 8x8 на матрицу состояния 8x8 в поле GF(2^8) с полиномом 0x171.

LM = {
0x71, 0x05, 0x09, 0xB9, 0x61, 0xA2, 0x27, 0x0E,
0x04, 0x88, 0x5B, 0xB2, 0xE4, 0x36, 0x5F, 0x65,
0x5F, 0xCB, 0xAD, 0x0F, 0xBA, 0x2C, 0x04, 0xA5,
0xE5, 0x01, 0x54, 0xBA, 0x0F, 0x11, 0x2A, 0x76,
0xD4, 0x81, 0x1C, 0xFA, 0x39, 0x5E, 0x15, 0x24,
0x05, 0x71, 0x5E, 0x66, 0x17, 0x1C, 0xD0, 0x02,
0x2D, 0xF1, 0xE7, 0x28, 0x55, 0xA0, 0x4C, 0x9A,
0x0E, 0x02, 0xF6, 0x8A, 0x15, 0x9D, 0x39, 0x71,

Пояснение, как оно соотносится с с матрицей A. Колонка 1 матрицы M - это элемент A[0] = 0x8e20faa72ba0b470,
для которого выполнен разворот порядка следования бит.
8E=>71 20=>04 FA=>5F
Колонка 2 матрицы M - это элемент A[8],
. . .
Колонка 8 матрицы M - это элемент A[56],

Я независимо вывел эту таблицу, из представленнй таблицы подстановки. О возможности подобного представления читал в статье автора [1]. Продемонструю, как выполнить декомпозицию таблиц. Берем два числа: первоя строка, вторая и третья колонка:
A[1] = 0x47107ddd9b505a38
A[2] = 0xad08b0e0c3282d1c
Выделяем по маске 7 бит в каждом байте (A[1] & ~0x0101010101010101) >> 1)^A[2] видим числа 0x8E008E8E8E000000. В каждом байте стоит полином, по которуму производится редуцирование 0x171, с отраженным порядком бит будет 0x8E. Перед нами просто таблица умножения в поле GF(2^8)/[0x171] с отраженным порядком следования бит в байте.

Линейное преобразование может быть представлено таблично.
Cвойство L(a+b) = L(a) + L(b), как и свойство L(a*b) = L(a)*L(b) - действует и для таблицы.

Мы рассматриваем возможность реализации без таблицы, с использованием афинных преобазований и операци умножения в поле GF(2^8). Операция умножения может быть выполнена с использованием векторных инструкций умножения без переносов (Intel), полиномиального умножения (Arm Neon). Афинные преобразования могут выполняться с использованием векторных инструкций без обращения к таблицам.

Оптимизация под векторные инсрукции Arm Neon. 16 байт составляют вектор, используя вектора можно в два действия эмулировать работу операции умножения на константу. Для эмуляции используется свойство линейности преобразования.

Оптимизация под GF-NI:

Парадокс в том, что отечественные алгоритмы Stribog и Kuznyechik можно считать с использованием американской криптографии. Американская криптография использует умножение в поле GF(2^8) по полиному 0x11B. Отечетсвенная криптография использует умножение с редуцированием по полиному 0x171 в алгоритме Stribog, 0x1C3 в алгоритме Kuznyechik. Можно использовать афинные изоморфные преобразования, чтобы отобразить все матрицы и коэффициенты для использования умножения в поле 0x11b.

Матрицы изоморфного преобразования мы научились находить[2]. Для преобразования 0x171=> 0x11B можно использовать матрицы

матрицы изоморфного преобразования 171 => 11B "Stribog"
171=>11B 02 0E M =49A24EE22C984CF0 M-1 =FB44BAF0CC5A0A1C
171=>11B 02 17 M =C30E560C5240D828 M-1 =6D0A141C3A9C2046
171=>11B 02 52 M =B1A27CD0765CD234 M-1 =F5481A5CBE24D86E
171=>11B 02 54 M =29903A0892D47ABC M-1 =E5126608F2EC44F0
171=>11B 02 A0 M =C154448014AEDCC6 M-1 =1B8C164A06F81208
171=>11B 02 B4 M =1590FECC3E8E8CE6 M-1 =9960C6DA5E32485C
171=>11B 02 F6 M =090EFAA096722E1A M-1 =6FD8B46E36428C4A
171=>11B 02 FD M =A7541EDA2602426A M-1 =CB20B646D48660DA

Изоморфное представление матрицы LM в поле 0x11B:

unsigned char LM_11b = {
	0xF6,0x55,0x74,0xE4,0x56,0x3E,0xC1,0x2F,
	0x54,0xDF,0x17,0x9E,0xA9,0x60,0x43,0x02,
	0x43,0x1D,0x10,0x2E,0xEB,0xBB,0x54,0x65,
	0xA8,0x01,0x39,0xEB,0x2E,0xA1,0xE1,0xAD,
	0x93,0xAB,0x81,0x26,0x4E,0x42,0xF5,0xCE,
	0x55,0xF6,0x42,0x0D,0xFB,0x81,0xC7,0x0E,
	0xBA,0x5C,0xA6,0xEF,0x38,0x30,0xEC,0x71,
	0x2F,0x0E,0x07,0xD1,0xF5,0x2A,0x4E,0xF6,

Необходимо таже преобразовать таблицу Sbox в изоморфное представление Sbox_iso = MR·S·RM^-1, где MR и RM^-1 - матрицы прямого и обратного изоморфного преобразования из поля образованного полиномом 0x171 в поле 0x11b. R - отражение порядка следования бит.

void SPLX_11b(const uint8_t* s, uint8_t* r)
{
	int i,j,k;
	for (i=0; i<8; i++)
	for (j=0; j<8; j++) {
		uint8_t v= 0;
		for (k=0; k<8; k++) 
			v ^= gf2p8_mul(LM_11b[j*8+k], Sbox_iso[s[k*8+i]]);
		r[i*8+j] ^= v;
	}
}

Полученный алгоритм выполняет операции S,P,L,X. В цике выполняется операция умножения в поле GF(2^8)/0x11B. Оптимизация под ARM Neon может использовать полиномиальное умножение с последующим редуцированием.

Я озаглавил сообщение "Крипто-рубль..". Все алгоритмы добычи крипто-валют основаны на вычислении хеш-функций, этот алгоритм удалось выполнить исключительно в 8-битных числах. Это открывает возможность векторизовать алгоритм для параллельного вычисления до 64 хешей. Другая оптимизация - изоморфное преобразование в композитное поле позволяет получить эффективную реализацию алгоритма аппаратно в ASIC или на FPGA.

[1] Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012, O. Kazymyrov, V. Kazymyrova

Представление системного времени

При вычислении интервалов времении, в POSIX и С11 используется структура timespec (секунды, наносекунды), получаем такую проверку.

ts.tv_nsec+=timeout;
if (ts.tv_nsec>=1000000000){
  ts.tv_nsec  = ts.tv_nsec % 1000000000;
  ts.tv_sec  += ts.tv_nsec / 1000000000;
}

В этом методе есть недостаток. Мы не можем применять такой подход для контроллеров. На архитектуре типа Cortex-M23 нет деления. Эмуляция деления будет вычисляться удивительно неэффективно. Надо исключить операцию деления и операцию взятия остатка от деления.
Идеально было бы исключить и проверку, чтобы код стал линейным.

Я перебирал варианты, как это вообще можно сделать. На ум приходят разные трюки с операциями: сложение с насыщением, с проверкой переполнения, сложение с переносом. Деление на константу можно заменить на умножение и сдвиг, но это опять не сильно эффективная операция.

Есть способ проведения вычислений с двоично-десятичными числами (Binary-coded decimal, BCD), когда при сложении выполняется коррекция операции сложения - добавление константы, чтобы заработать перенос между разрядами десятичного числа. В случае двоично-десятичных чисел к десятичному разряду добавляется дополнение (число 6), если разряд больше 9. Число 6 получается, как инверсия (0x9^0xF) или в нашей математике (16-10). Аналогично мы расчитываем дополнение для миллиарда в двоичном представлении ((1<<30) - 1000000000) или (0x3B9ACA00^0xFFFFFFFF).

Получился такой код, он предполагает использование 64 битного упакованного времени, при этом в малдших 32 битах числа расположены наносекунды, а в старших секунды.

// коррекция сложения интервалов времени
if ((uint32_t)t64 > 999999999UL) t64 += (uint32_t)~999999999UL; 

Полусумматор и входящий перенос

А был ли перенос между разрядами? Сумматор (операция сложения двоичных чисел) состоит из цепочки полусумматоров, в которой каждый последующий разряд использует перенос с предыдущего разряда. Нужно выделить входящий перенос каждого разряда. Рассмотрим как работает аппаратная функция переноса разрядов в полусумматоре.

ci = carry_in -- входящий перенос: 0 или 1
s  = a^b^ci    -- результат сумма разрядов
сo = ci? (a|b) : (a&b); -- исходящий перенос

Нас интересуют входящие переносы (сi) по маске двоично-десятичного числа 0x11111110 при сложении с дополнением (a+b+D). Сложение с дополнением формирует правильную цепочку переносов между десятичными разрядами. При этом коррекция результата сложения требуется, если между десятичными разрядами был перенос.

s1 = a+b; -- формирует правильные результаты в каждом разряде, если переноса не было,
s2 = a+b+D; -- формирует правильную цепочку переносов между разрядами.
s = co? s2: s1; -- коррекция результата сложения

Расчет BСD времени в упакованном формате

struct _BCD_Time {
  unsigned int susec:8;   //сотые
  unsigned int   sec:8;   //секунды
  unsigned int  mins:8;   //минуты
  unsigned int  hour:8;   //часы
}; 

#define BCD_TIME_CORRECT 0x66A6A666UL 
#define BCD_TIME_CARRYIN 0x11111110UL
time_add(a, b) {
  s1 = a + b;
  s2 = a + b + BCD_TIME_CORRECT;  // коррекция BCD для вычисления переносов
  m  =(a ^ b ^ s2) & BCD_TIME_CARRYIN; // из переносов делаем маску
  m  = m - (m>>4); // маска для выделения десятичных разрядов
  return s1 + (m & BCD_TIME_CORRECT); // коррекция сложения
}

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

[1] http://homepage.cs.uiowa.edu/~jones/bcd/bcd.html

Осваиваем GigaDevice GD32

Мы делаем свою операционную систему... которая поддерживает функционал C11 и собирается с использованием GCC.
GigaDevice не помог с этим. Загрузчик и примеры GD ориентированы на Keil и JAR. Постараюсь конспективно изложить, что нужно для разработки HAL с нуля и как действовать при виде нового контроллера с несовместимым API.

1.2 Индентификация системы

Порядок индентификации: определить ядро процессора (SCB_CPUID), определить к какому семейству контроллеров относится, размер памяти и уникальный идентификатор. При прочих равных в плату можно запаять совместимые по выводам контроллеры нескольких производителей. Устройство должно выдавать отладочную информацию: микроконтроллер и размер памяти. Это необходимо для внутрисхемной диагностики и обслуживания, внутрисхемной прошивки.

Идентификация ядра CPUID_CORE_ID BITS(4,15):
	CORTEX_M0   = 0xC20, ARMv6-M (0xC)
	CORTEX_M0P  = 0xC60, ARMv6-M
	CORTEX_M1   = 0xC21, ARMv6-M
	CORTEX_M3   = 0xC23, 
	CORTEX_M4   = 0xC24,
	CORTEX_M7   = 0xC27, ARMv7-M (0xF)
	CORTEX_M23  = 0xD20, ARMv8-M baseline (0xC)
	CORTEX_M33  = 0xD21, ARMv8‑M with Main Extension (0xF)
	CORTEX_M35P = 0xD31,
	CORTEX_M55  = 0xD22,
	CORTEX_M85  = 0xD23, ARMv8.1‑M with Main Extension (0xF)

Идентификация контроллера начинается с выбора адреса регистра отладки DBG/DBGMCU. Адрес регистра отладки зависит от ядра микроконтроллера.

ID code register (DBG_ID)
DBGMCU_IDCODE    0xE004 2000
DBG_ID_GD32E10X  0xE004 2000
DBGMCU_IDCODE_G4 0xE004 2000
DBGMCU_IDCODE_F7 0xE004 2000

DBGMCU_IDCODE_L0 0x4001 5800
DBG_ID_GD32E23X  0x4001 5800
DBGMCU_IDCODE_G0 0x4001 5800

DBGMCU_IDCODE_L5 0xE004 4000
DBGMCU_IDCODE_U5 0xE004 4000
DBG_ID_GD32E50X  0xE004 4000

DBGMCU_IDCODE_H7 0x5C00 1000

Глядя на таблицу, кажется адреса архитектурно зависимы. Если ядро Cortex-M0 или Cortex-M23 -- один адрес, если CM3/CM4 - другой, CM33.. . Размер флеш памяти определяется в зависимости от производителя и архитектуры, см. Memory density information. Для контроллеров GD32 находим два регистра...

Base address: 0x1FFF F7E0
SRAM_DENSITY 	BITS(16,31)
FLASH_DENSITY	BITS( 0,15)

Уникальный идентификатор Unique device ID (96 bits)

MCU         CPUID  DEV_ID  REV_ID 	UNIQUE_ID    MEM.DENSITY
GD32F1X0	0xC23  0x410   0x1303	0x1FFF F7AC  0x1FFF F7E0
GD32F10X	0xC23  0x410			0x1FFF F7E8  0x1FFF F7E0
GD32E10X	0xC24  0x410   0x1712	0x1FFF F7E8  0x1FFF F7E0
GD32F3X0	0xC24  0x410   0x1704	0x1FFF F7AC  0x1FFF F7E0
GD32F30X	0xC24					0x1FFF F7E8  0x1FFF F7E0
GD32F4XX	0xC24					0x1FFF 7A20  0x1FFF 7A10
STM32F75X		   0x449			0x1FF0 F420  0x1FF0 F442
STM32F72X          0x452            0x1FF0 7A10  0x1FF0 7A22
GD32E23X	0xD20  0x410   0x1909	0x1FFF F7AC  0x1FFF F7E0
GD32E50X 	0xD21  0x444			0x1FFF F7E8  0x1FFF F7E0
STM32U5xx   0x	   0x482   0x2001   0x0BFA 0700  0x0BFA 07A0
GD32VF10X                   		0x1FFF F7E8  0x1FFF F7E0

Часть 1.3. Программатор

Попробовал использовать ST-Link/V2 Programmer для прошивки GD32E10X -- работает, размер флеша определился корректно. Ревизия не известная, пишит, что найден "STM32F103 medium-density". Для GD32E23X и GD32E50X ST-Link не подходит. Прошивалку делаем из отладочной платы GD32E103R. Дополнительно изучаем тему изготовления CMSIS-DAP/DAPLink адаптера согласно рекомендациям и спецификациям ARM CMSIS-DAP.

Что-то работает не корректно. Основная проблема идентификации, что не распознаются признаки защиты памяти, OptionBytes -- выставление опций вызвает непоправимые изменения. Программатор должен знать, где располагаются, как и за что отвечают OptionBytes. Осознание проблемы приводит к некоторой модели идентификации контроллера программатором. У программатора должна быть база известных контроллеров, со своими адресами для идентификации. Идентификация начинается с CPUID, далее необходимо распознать опциональное оборудование ядра CoreSight, далее распознается DEV_ID и REV_ID. По трем параметрам (CPUID,DEV_ID,REV_ID) находим в базе микроконтроллер. Далее находим файл конфигурации периферии, например в формате CMSIS-SVD. ARM предлагает производителю контроллера cтандартный подход для встраивания поддержки в свою экосистему. Этот же подход нужен для создания инструмента программирования контроллеров.

• Создание файлов начальной загрузки startup_{device}.s -- Reset_Handler и таблица векторов прерываний.
• Создание файлов system_{device}.c/h -- начальная конфигурация контроллера
• Создание файла описания аппаратуры в формате SVD и генерация на его снове заголовков, используется утилита для генерации кода. Это позволяет в какой-то мере унифицировать HAL
• Описание и распознавание средсв отладки CoreSight встроенных в контроллер.
• Описание конфигурации флеш-памяти: размер памяти, размер сектора, разрядность и быстродействие операций.
• Создание и компиляция алгоритма прошивки флеш памяти, состоящего из ряда вызовов: EraseSector, ProgramPage, Verify..[CMSIS-Pack]. Скомпилированный код помещается в оперативную память и испольняется в режиме отладки. Функция программатора сводится к загрузке бутлодера и фрагментов прошиваемого кода в оперативную память и манипуляция точками запуска и останова.

Часть 1.4. Пакет описания аппаратуры DFP

Дополнительно можно изучить тему где взять подобные описания. Я нашел источник информации, помимо библиотек в пакетах DFP от производителя. Технология создания пакета описана на в стандарте CMSIS-Pack и поддерживается производителями контроллеров, см. Open-CMSIS-Pack.

К сожелению, поддержка пакетов CMSIS-Pack не является первичной. Пакеты Firmware Library обновляются раньше чем пакеты CMSIS-Pack и содержат более доставерную информацию об аппаратуре, они не полные, не сождержат описания сегментов памяти OptionBytes. Однако, это тот путь, который позволяет выполнять генерацию кода по описанию аппаратуры и может использоваться при отладке.

Структура директории

• Device/include/{CHIPX}.h -- описание аппаратуры
• Flash/{CHIPX}.flm -- бутлоадеры, elf формат
• svd/{CHIPX}.svd -- описание аппаратуры в формате CMSIS-SVD

Часть 1. Нужно создать совместимый Sturtup

C учетом правил сборки проекта и рекомендаций ARM у нас должно образоваться несколько файлов с определенным именованием.

• Device/source/gcc/gd32e10x.ld -- правила линковки. Скрипт включает размещение сегментов памяти и карту памяти. В тоже время генерация скрипта возможна по шаблону: перечислить встроенную память.
• Device/include/gd32e10x.h -- описание периферии. Стараемся придерживаться исходников производителя. В этом файле только базовые адреса устройств.
• Device/source/gcc/startup_gd32e10x.s -- вот этот файл линкуется первым. Он на асемблере, содержит таблицу векторов прерываний и инициализацию переменных. В нем выполняется инициализация сегментов памяти RAM data (заполнение начальными значениями) и bss (обнуление). Код производит два вызова: низкоуровневую настройку периферии (low_level_init), без которой операционка не может стартовать и после этого запускает основную функцию (main) или загружает модули ядра операционной системы. В нашем случае до функции main выполняется старт операционной системы, которая после запуска и инициализации мультизадачности, инициализации драйверов, запутит main.
• Device/source/system_gd32e10x.c (low_level_init) -- содержит настройку частоты ядра, ресет оборудования, вызвает начальную конфигурацию периферии, вызывает настройку работы внешней памяти, если есть.
• Кое-что еще нужно для нормальной работы программ на Си, не очевидное -- статические конструкторы и деструкторы, нужно запустить все конструкторы по списку. Мы пишем код на Си, но поддержка статический конструкторов нужна для функционала модулей ядра операционной системы. Инициализацию памяти и перемещение сегментов мы выполняем до запуска кода, в коде начальной загрузки.

Области памяти .bss, .data и таблица статических конструкторов определяеся в линкерном скрипте. В линкерном скрипте задается также размер памяти и указатель стека.

Совместимый startup это всегда один и тот же код, для Cortex-M. Отличием является таблица векторов, которая своя для каждого микроконтроллера. Метод создания - скопировать код, скопировать таблицу векторов от производителя и подправить синтакстис ассемблера, чтобы нравился GCC.

Часть 2.

Нужно создать код низкоуровневой инициализации (low_level_init). Пример нужно взять из файла startup_gd32e10x.c от производителя, но дописать и подправить придется. Тут всегда один стандартный вызов SystemInit(). SystemCoreClock -- глобальная переменная, на выходе инициализации должна содержать частоту ядра -- это требование совместимости с CMSIS-RTOS.

Часть 3.

Где-то между инициализацией периферии до запуска прикладных программ нужно настроить по списку все ноги, порты ввода-вывода. Это вероятно происходит до запуска main, до операционной системы. В нашей концепции все ноги по списку должны быть настроены до запуска приложения. Приложение может менять настройки периферии, но все выводы и порты должны быть в определенном состоянии на момент включения и на момент выключения. Нужно описать ноги согласно принятому API, в совместимом виде, чтобы один и тот же код можно было перенести между контроллерами разных произовдителей. Понятно что настройка происходит иначе, но описание ног должно быть унифицировано меду контроллерами разных производителей. Для этого надо составить файл hal/gpio.h и hal/gpio.c. Описание таблицы ног производится в заголовке board.h. Мы определяем ноги, группы ног по портам, с атрибутами: PIO_ANALOG, PIO_INPUT, PIO_OUTPUT, PIO_OPENDRAIN и т.д. Сложность в том, чтобы использовать одинаковый набор атрибутов на разных платформах, невзирая на то, что на одной нужно использовать Remap, а на другой - нет.

Часть 4.

Надо описать хотя бы один стандартный последовательный порт, который служит для отладки. На STM32 мы используем SWO для вывода отладочной информации. Тут этого нет. Но надежда умирает последней я расчитываю найти SWO даже если про него ничего не говорят. Признаком того, что SWO реализован аппаратно, является ITM (Instrumentation Trace Macrocell) и возможность настроить TRACE через DBGMCU.

Среди настроек регистра DBG_CTL находим TRACE_IOEN (включение трассировки) и TRACE_MODE=0 (Asyncronous).

Если в контроллере все же отсутсвует ITM и поддержка SWO, изучаем возможность использовать UART вместо SWO. Обращаю внимание, что аппаратура трассировки через SWO активируется со стороны программатора, программатор может не поддерживать канал отладки.

Первое что нужно при запуске нового контроллера - помыргать лампочкой, изменить логический урвоень на любой тестовой точке. Нам нужен хоть какой-то терминал, который покажет, что устройство загрузилось и работает. Это может быть последовательный порт типа UART, одноногий дебаггер -- осциллограф или логический анализатор. Теримнал и канал отладки (трассировки) - это функция операционной системы. Мы поддерживаем два режима трассировки. В одном режиме исполнение кода приостанавливается пока не выполнится вывод сообщения (debug) - блокирующий вызов, этот режим нужен для отладки драйверов и обработчиков прерываний. Второй режим -- ассинхронный (printf, puts), вывод отладочной информации не должен препятствовать работе прикладной программы, без блокировки, без задержки -- вывод сообщений выполняется в фоновом процессе.

Часть 5. Перенос ядра RTOS на иную архитектуру

Завязок на аппаратуру в операционной системе не так уж много, но они очень существенные. От этой зависимости можно абстрагироваться.

1. SVC -- системное прерывание, обращение к системной функции. Кусочек кода на ассемблере.
2. ContextSwitch -- выполняется при обращении к PendSW прерыванию. Так происходит на всех ядрах Cortex. В разных моделях различным образом используется стек при входе и выходе из прерывания. Есть модели с защитой памяти, с поддержкой FPU, с ленивыми переключениями, с поддержкой двух стеков MSP PSP, да и система команд зачастую различаются.

Таким образом, для нового контроллера надо написать две фукнции: SVC_Handler и PendSW_Handler. Еще есть функция, связанная с механизмом переключения задач, -- заполнение стека при запуске нового треда. Заполнение в частности включает EXEC_RETURN -- флаги способа возврата из обработчика прерывания. Эти флаги - псевдо-адрес возврата сообщают ядру, как восстановить стек. Количество флагов и значение меняется в разных ядрах Cortex, так что заполнение стека является аппаратно-зависимой фукнцией. В нашей реализации аппаратно зависимым от архитектуры оказался именно набор флагов EXEC_RETURN.

Ниже привожу примеры реализации обработчика системного вызова

SVC_Handler:
   mrs  r0, psp
   ldr  r1, [r0, #24]
   ldrb r1, [r1, #-2]
   ldr  pc, [r3, r1, LSL #2]

В нашей операционке SVC вызывается только из прикладных задач (Thread mode), в Handler mode вызовы SVC не используются. Код обработки SVC запросов не меняется для архитектур armv7m-e и armv8m.main, а вот ядро cortex-m23 (архитектура armv8m.base) такие инструкции со сдвигами и отрицательными смещениями не поддерживает, нужна альтернативная реализация.

Переключение c основного стека (Main Stack Pointer, MSP) на стек прикладных программ (Process Stack Pointer, PSP) происходит в процессе начальной загрузки. Мы выполняем это переключение в ассемблерном коде, чтобы исключить использование стека до момента переключения.

// переключение стека с MSP на PSP
	mov r0, sp
	msr psp, r0;
    ... настройка размера стека
	mrs r0, control;
	orr r0, #2
	msr control, r0
	sub sp, #256

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

В обработчике прерывания мы принимаем решение о переключении задач. Переключение задач происходит путем вызова программного прерывания PendSW следом за обработчиком аппаратного прерывания, выставляем флаг с использованием инструкции __YIELD().

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

PendSW_Handler: // переключение задач
   push {r4-r11,lr}
   . . .// сохраняем контекст (sp) и переходим к следующей задаче
   pop  {r4-r11,pc}

В этом примере переключение стеков (контектсорв задач) очень лаконично сформулировано. Однако, не все так гладко происходит на смом деле. На самом деле, находясь в прерывании PendSW мы используем Handler Stack Pointer (MSP), а возврат происходит в Thread mode с использованием Process Stack Pointer (PSP)

PendSW_Handler: // переключение задач
   mrs   r0, psp
   stmdb r0!, {r4-r11,lr}
   . . .// сохраняем контекст (r0) и переходим к следующей задаче
   ldmia r0!, {r4-r11,lr}
   msr	 psp, r0
   bx    lr

Далее мы усложняем процесс переключения, если используется FPU, и если используется исключение безопасности. Для каждого ядра и каждого варианта оборудования, с FPU, c MPU, c Security Extension возникает необходимость дописать или переписать код переключения контекстов задач.

Чтобы запустить новый контроллер с новым ядром надо все по списку выполнить без ошибок, иначе ни одна лампочка не мыргнет и контроллер не будет подавать признаков жизни, до исполнения main() мы не дойдем. Можно отлаживать отдельно запуск кода без операционной системы, на отладочной плате, но начальная загрузка должна заработать сразу.

Программатор DAP-Link для прошивки и тестирования Хеш-плат

Программатор

Новый контроллер -- это, возможно, и новый программатор. Все совместимые программаторы строятся на референсном коде ARM CMSIS-DAP/DAP-Link. Ядро ARM содержит CoreSight отладчик с поддежкой JTAG или SWD. GD32E103 определяется как STM32F103 и может прошиваться программатором STM ST-Link. А вот модели контроллеров GD32E23x и GD32E50x определяются с ошибкой и не шьются. Программатор GD-Link-OB содержится на отладочной плате. Программатор для GD32E23x и GD32E50x мы сделали из стартового набора GD32E103R-Start, отпаяв от платы отлаживаемый контроллер. Вероятно, вам удасться, где-то заказать GD-Link-S или GD-Link-Light. Говорят, можно использовать nanoDAP или еще какой-то CMSIS-DAP/DAP-Link эмулятор. Я прикинул, заказ программатора - минимум неделя. Заказал в производство собственный программатор совместимый с GD-Link-OB...

Расчет CRC-5 и CRC-24 в контроллерах GigaDevice

Аппаратно контроллер GigaDevice GD32E23X или GD32E50X может расчитывать 8, 16 и 32 битные полиномы. А какже расчитать аппаратно полиномы другой размерности? Для нас актуально расчитывать в контроллерах CRC-5 и CRC-24.

Привожу решение...

#define CRC5BTM_POLY 0x05
uint8_t crc5_btm(uint8_t crc, uint8_t *data, size_t data_len) 
{
	CRC_IDATA = (uint32_t)(crc<<3);
	CRC_CTL   = CRC_CTL_PS_8|CRC_CTL_RST;// REV_I REV_O
	CRC_POLY  = (uint32_t)(CRC5BTM_POLY<<3);
	int i;
	for (i=0; i< data_len; i++) 
		REG8(CRC) = data[i];
	return REG8(CRC)>>3;
}

Я выравниваю разрядность сдвигом, CRC5 считается в старших разрядах 8-битного регистра. Точно так же можно посчитать 24 битный CRC-24 с выравниванием на 32 бита.

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

Эмуляция инструкций CLZ и CTZ для Cortex-M23

Вылезла проблема эффективной реализации операции CLZ, потому что на ядре Cortex-M23 она не поддерживатся. В тоже время есть тонны кода для Cortex-M3/M4 с использованием инструкции CLZ.
Я изучил в доступных источниках и не нашел хорошей реалиазации. Мне нужна эффективная реализация этой операции, потому что на ней основана одна из основных функций -- выделение памяти и работа с флагами. Решил, что надо самому подобрать такую реализацию.

static	const uint8_t lut[16]= {4, 3, 2, 2, 1, 1, 1, 1};
int clz_u32(uint32_t a)
{
	int i = 28;
	if((a>>16)!=0) a>>=16,i-=16;
	if((a>> 8)!=0) a>>=8, i-=8;
	if((a>> 4)!=0) a>>=4, i-=4;
	return i + lut[a];
}

Еще одна реализация. Можно таблицу подстановки представить конструкцией switch.

int _clz_u32(uint32_t r0)
{
	int i=28;
	uint32_t b;
	if ((b = r0>>16) != 0) r0=b, i-=16;
	if ((b = r0>>8 ) != 0) r0=b, i-=8;
	if ((b = r0>>4 ) != 0) r0=b, i-=4;
	switch(r0 & 0xF) {
	case 0: b=4; break;
	case 1: b=3; break;
	case 2 ... 3: b=2; break;
	case 4 ... 7: b=1; break;
	default:b=0; break;
	}
	return i + b;//lut[r0];
}

Дальше занялся исследованием кода, который производися компилятором (#gcc -O3 -S).
Руками выполнил оптимизацию за компияторм, чтобы код стал компактнее. Оптимизация - обращене к таблице подстановки с использованием инструкции ADR.

__clzsi2:
        movs    r3, #28 // i=28

        lsrs    r2, r0, #16
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #16
1:
        lsrs    r2, r0, #8
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #8
1:
        lsrs    r2, r0, #4
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #4
1:
        adr     r2, 1f
        ldrb    r0, [r2, r0]
        adds    r0, r0, r3
        bx      lr
	.align 2
1:
	.byte 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0

Это пожалуй самая эффективная реализация. Затем подобрал аналогичным образом реализацию для CTZ.

static	const uint8_t lut_ctz[16]= {4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
int _ctz_u32(uint32_t a)
{
	int i = 28;
	if((a<<16)!=0) a<<=16,i-=16;
	if((a<< 8)!=0) a<<=8, i-=8;
	if((a<< 4)!=0) a<<=4, i-=4;
	return i + lut_ctz[a>>28];
}

__ctzsi2:
        movs    r3, #28

        lsls    r2, r0, #16
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #16
1:
        lsls    r2, r0, #8
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #8
1:
        lsls    r2, r0, #4
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #4
1:
        lsrs    r0, r0, #28
        adr     r2, 1f
        ldrb    r0, [r2, r0]
        adds    r0, r0, r3
        bx      lr
	.align 2
1:
	.byte 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0

[ARM DDI0550] ARM Cortex-M23 Processor Technical Reference Manual

CRC-15/CAN

Решил закрепить навык синтеза алгоритмов CRC с числом бит не кратным 8. Вот что получилось для CRC-15/CAN.

CRC-15/CAN

width=15 poly=0x4599 init=0x0000 refin=false refout=false xorout=0x0000 check=0x059e name="CRC-15"

Таблицы и коды при вычислении выравниваются по старшему биту.

// Табличный алгоритм CRC-15 для таблиц 16 значений
CRC16	CRC15_update(CRC16 crc, uint8_t val){
	crc<<=1;
	crc^= (val<<8);
	crc = (crc << 4) ^ CRC15_Lookup[(crc>>12) & 0xF];
	crc = (crc << 4) ^ CRC15_Lookup[(crc>>12) & 0xF];
	return (crc>>1);
}

// Табличный алгоритм CRC-15 для таблиц 256 значений
CRC16	CRC15_update(CRC16 crc, uint8_t val){
	crc<<=1;
	crc^= (val<<8);
	crc = (crc << 8) ^ CRC15_Lookup[crc>>8];
	return (crc>>1);
}

static const uint16_t CRC15_Lookup[] = {
0x0000, 0x8B32, 0x9D56, 0x1664, 
0xB19E, 0x3AAC, 0x2CC8, 0xA7FA,
0xE80E, 0x633C, 0x7558, 0xFE6A, 
0x5990, 0xD2A2, 0xC4C6, 0x4FF4,
. . .
};

CRC-5/BITMAIN Алгоритм для расчета и проверки контрольных сумм

CRC-5 обнаружил в проекте cgminer в ужасной реализации. Вычисления производятся по битам и далеко не самым оптимальным образом. Решил разобраться, почему и что это вообще за CRC такой. Из кода выяснил, что алгоритм похоже использует полином x^5+x^2+1(0x05). В таблицах нашел алгоритм CRC-5/USB с полиномом 0x05. Это тот же полином, только не ясно, как сделать алгоритм одинаково эффективно работающий с байтами и битами. В коде встречаются варианты применения алгоритма как к битовым строкам так и байтам. Решение такое: расчитать таблицу умножения для полинома и использовать табличные подстановки. Чтобы "подобрать" алгоритм для CRC5 сначала реализовал расчет CRC-5/USB, потому что для него есть точное определение в базе и прверочные числа.

CRC-5/USB

width=5 poly=0x05 init=0x1f refin=true refout=true xorout=0x1F check=0x19 name="CRC-5/USB"

CRC-5/BITMAIN

width=5 poly=0x05 init=0x1f refin=false refout=false xorout=0x0 check=0x0F name="CRC-5/BITMAIN"

Формат записи характеристик алгоритма: разрядность, полином, маска инициализации, отражение бит на входе и выходе алгоритма, маска инверсии на выходе и контрольная сумма от строки "123456789". Данных по CRC-5/BITMAIN не было, я даже не был уверен что это возможно. Сразу не получилось подобрать алгоритм, потому что неясно было, как выполнять выравнивание данных при пяти битах. Я начал с реализации табличного алгоритма для CRC-5/USB. Сделал алгоритм с табицей 16 элементов (умножение на 4 бита).

 Таблица подстановки для CRC-5/USB
0x00, 0x16, 0x05, 0x13,
0x0A, 0x1C, 0x0F, 0x19,
0x14, 0x02, 0x11, 0x07,
0x1E, 0x08, 0x1B, 0x0D,

Структура алгоритма точно такая же, как и для CRC-8.

uint8_t    CRC5USB_update(uint8_t crc, uint8_t data) 
{
  crc = crc ^ data;
  crc = (crc>>4) CRC5USB_Lookup4[crc&0xF];
  crc = (crc>>4) CRC5USB_Lookup4[crc&0xF];
  return crc&0x1F;
}

Если таблица имеет размер 256 элементов, алгоритм еще упроститься

uint8_t    CRC5USB_update(uint8_t crc, uint8_t data) 
{
  crc = crc ^ data;
  crc = CRC5USB_Lookup[crc];
  return crc;
}

Для CRC-5/BITMAIN сгенерировал таблицу умножения 256 элементов (умножение на 8 бит). В таблице и в алгоритме число 5 бит выравниывается по старшему разряду. Алгоритм работает над байтами,

uint8_t    CRC5_update(uint8_t crc, uint8_t data) 
{
  crc = (crc<<3) ^ data;
  crc = CRC5_Lookup[crc];
  return (crc>>3);
}

Для реализации в микроконтроллере мы обычно используем маленькие табицы по 16 элементов

uint8_t    CRC5_update(uint8_t crc, uint8_t data) 
{
  crc = (crc<<3) ^ data;
  crc = (crc<<4) ^ CRC5_Lookup[crc>>4];
  crc = (crc<<4) ^ CRC5_Lookup[crc>>4];
  return (crc>>3);
}

Алгоритм CRC можно дробить на любое число бит 1...8.

// шаг алгоритма для 1..8 бит
crc = crc ^ data;
crc = (crc << bits) ^ CRC5_Lookup[crc>>(8-bits)];

Таким образом можно посчитать CRC5, если число бит в битовой строке не кратно восьми. Данные при этом должны выравниваться по старшему биту.

 Таблица подстановки для CRC5
0x00, 0x28, 0x50, 0x78, 0xA0, 0x88, 0xF0, 0xD8,
0x68, 0x40, 0x38, 0x10, 0xC8, 0xE0, 0x98, 0xB0,
0xD0, 0xF8, 0x80, 0xA8, 0x70, 0x58, 0x20, 0x08,
0xB8, 0x90, 0xE8, 0xC0, 0x18, 0x30, 0x48, 0x60,
0x88, 0xA0, 0xD8, 0xF0, 0x28, 0x00, 0x78, 0x50,
0xE0, 0xC8, 0xB0, 0x98, 0x40, 0x68, 0x10, 0x38,
0x58, 0x70, 0x08, 0x20, 0xF8, 0xD0, 0xA8, 0x80,
0x30, 0x18, 0x60, 0x48, 0x90, 0xB8, 0xC0, 0xE8,
0x38, 0x10, 0x68, 0x40, 0x98, 0xB0, 0xC8, 0xE0,
0x50, 0x78, 0x00, 0x28, 0xF0, 0xD8, 0xA0, 0x88,
0xE8, 0xC0, 0xB8, 0x90, 0x48, 0x60, 0x18, 0x30,
0x80, 0xA8, 0xD0, 0xF8, 0x20, 0x08, 0x70, 0x58,
0xB0, 0x98, 0xE0, 0xC8, 0x10, 0x38, 0x40, 0x68,
0xD8, 0xF0, 0x88, 0xA0, 0x78, 0x50, 0x28, 0x00,
0x60, 0x48, 0x30, 0x18, 0xC0, 0xE8, 0x90, 0xB8,
0x08, 0x20, 0x58, 0x70, 0xA8, 0x80, 0xF8, 0xD0,
0x70, 0x58, 0x20, 0x08, 0xD0, 0xF8, 0x80, 0xA8,
0x18, 0x30, 0x48, 0x60, 0xB8, 0x90, 0xE8, 0xC0,
0xA0, 0x88, 0xF0, 0xD8, 0x00, 0x28, 0x50, 0x78,
0xC8, 0xE0, 0x98, 0xB0, 0x68, 0x40, 0x38, 0x10,
0xF8, 0xD0, 0xA8, 0x80, 0x58, 0x70, 0x08, 0x20,
0x90, 0xB8, 0xC0, 0xE8, 0x30, 0x18, 0x60, 0x48,
0x28, 0x00, 0x78, 0x50, 0x88, 0xA0, 0xD8, 0xF0,
0x40, 0x68, 0x10, 0x38, 0xE0, 0xC8, 0xB0, 0x98,
0x48, 0x60, 0x18, 0x30, 0xE8, 0xC0, 0xB8, 0x90,
0x20, 0x08, 0x70, 0x58, 0x80, 0xA8, 0xD0, 0xF8,
0x98, 0xB0, 0xC8, 0xE0, 0x38, 0x10, 0x68, 0x40,
0xF0, 0xD8, 0xA0, 0x88, 0x50, 0x78, 0x00, 0x28,
0xC0, 0xE8, 0x90, 0xB8, 0x60, 0x48, 0x30, 0x18,
0xA8, 0x80, 0xF8, 0xD0, 0x08, 0x20, 0x58, 0x70,
0x10, 0x38, 0x40, 0x68, 0xB0, 0x98, 0xE0, 0xC8,
0x78, 0x50, 0x28, 0x00, 0xD8, 0xF0, 0x88, 0xA0,

Хеш платы для Майнинга

С начала проекта мы наплодили множество версий хеш плат. Некоторые из них не нашли своего заказчика. Ищут.

Платы мы будем именовать по оригинальным названиям, имея ввиду, что наши платы являются аналогами и используют те же микросхемы ASIC. Во всех платах используется собственная оригинальная схема питания, совсем другие микросхемы и контроллеры, другая разводка платы, иная компоновка. Наши платы показывают большую надежность и устойчивость. Имеют гораздо меньшие габариты за счет эффективности водоблоков и компоновки плат.

Основные направления: 1) Совместимость. В совместимой версии платы мы оставляем то же количество чипов. 2) Производительность. Производительность оцениваем по числу гигахеш в секунду. 3) Эффективность.

S19 Hyd. Совместимые

Размер платы: 210мм х 96мм, 76 ASIC Bitmain BM1398, водяное охлаждение одностороннее. 1790 электронных компонент. 8100 контактных площадок, 4600 отверстий. Производительнсть 35-40 ТН/s

S19 Pro Hyd. Производительные

Размер платы: 210мм х 126, 114 ASIC Bitmain BM1398, водяное охлаждение двустороннее. 2290 электронных компонент. 10700 контактных площадок, 8400 отверстий. Производительнсть 50-60 ТН/s

S19 XP Hyd. Перспективные

Данные не раскрываются

L3+ Hyd. Экспериментальные

Размер платы: 150мм х 120мм, 96 ASIC Bitmain BM1485, водяное охлаждение. 1300 электронных компонент. 5660 контактных площадок, 8990 отверстий.