1

Topic: Автоматическая генерация исходного кода

Automatic Device Driver Synthesis with Termite

Intel Labs опубликовала статью по автоматической генерации исходного кода драйверов и последующей кросс-адаптации.

Источник информации: http://www.xakep.ru/magazine/xa/151/xa_151.pdf

Алгоритм работы Termite основан на методах
«теории игр». Драйвер выступает в роли первого игрока, а остальное
окружение, к которому можно причислить ОС и устройство, — второго.
Рагхунат поясняет: «Когда драйвер делает ход, окружение тоже меняет
свое состояние. Выигрышная стратегия состоит в том, чтобы делать
ходы по игровому полю таким образом, чтобы не ввести окружение в
противоречивое или тупиковое состояние».

2

Re: Автоматическая генерация исходного кода

Сокращённый перевод статьи. Если заинтересовали детали, пишите дополню.


Резюме.

Синтезируют текст драйвера из спецификаций.  Проиводительность
созданного драйвера эквивалентна обычному.

Введение.

Программа термиты требует 2 входные спецификации. Список регистров.
Описание интерфейса с ОС.
Драйвер синтезируется на языке С. Алгоритм создание драйвера
описывается на языке теории игр.

2 раздел - методология синтеза.
3 раздел - специфика языка термит.
4 раздел - спецификация между драйвером и ОС.
5 раздел -  алгоритм синтеза.
6 раздел - оценки драйвера.
7 раздел - ограничения данной реализации.
8 раздел - связанные работы.
9 раздел - выводы.

2. Спецификация включает состояние и поведение драйвера, которые важны
на программном уровне. Спецификации регистров берутся из даташитов.
Инициализация Езернет и Скази дисков делается подобным образом, что
позволяет объединить драйвера для них в один класс.  На рисунке 1.
показана самая общая схема зависимости риаботы синтезатора от 3 типов
спецификации.

2.1 Спецификация Класса-устройства.
Устройство класса Ethernet-контроллера, например, включает в себя
такие события, как передачи пакетов, завершение автоматическое согласование,
и изменения статуса соединения. Требуется только инкрементальная
реализация протоколов обмена.
Например если у нас есть ioctl() интерфейс с особенностью, то надо
реализовать только эту особенность.

2.2. Спецификация Устройства.
Если посмотреть 2 описания операции передачи для Езернет контроллера
на рис.1 и 2, можно заметить, что есть разночтения по поводу установки
13 бита.
Это потому, что документация не формальная. Первый способ это
сравнение описания.
Второй способ это сравнения драйвера. Третий способ это построить
спецификацию на основе регистрового описания HDL. Хардваре дизайн
лангвиджес - это набор регистров и шин обмена данными. Автоматический
синтез этой спецификации пока не реализован, но вполне возможен
производителем оборудования.

2.3 Спецификация ОС.
В этом разделе описаны функции вызова драйвера со стороны ОС. Это
может быть несколько отдельных интерфейсов. Если устройство
подключается к стандартной шине, то в этой спецификации можно
использовать общие таймеры и менеджеры памяти.

2.4 Процесс синтеза.
Цель синтеза - создать исходник на языке Си для драйвера устройства.
Два основных требования. 1. Безопасность. Соответствовать ОС, 2.
Надёжность. Гарантированное достижение действия за несколько шагов.
Этот процесс можно представить как игру драйвера с ОС. ОС даёт задание
а драйвер его выполняет за конечное число шагов и в рамках условий ОС.
Детали в разделе 5.  В результате мы генерируем машину состояний. В
каждом состоянии драйвер что то делает: пишет в устройство,
регистрируется, делает вызов ОС, ждёт ввода с перефериёного
устройства, которым управляет драйвер, ждёт вызова от ОС. Машина
состояний конвертируется в исходный код.

3. Описание языка Термиты.
Пример спецификации драйвера на этом языке можно увидеть в секции 4.

3.1 Требования
Это должен быть язык высокого уровня, который позволяет описывать
ансамбли конечных автоматов.
Примеры данных в спецификации Термит включает устройство регистров,
DMA буферов, и операционная система ввода / вывода,
запрос дескрипторов. HDL язык для этого хорош, но нами не реализован.
Мы сделали свой язык на основе  LOTOS process calculus.

3.2 Сообщения, интерфейсы и компоненты.
На языке Термит все взаимодействия, между драйвером и операционной
системой описываются как сообщения. Далее идёт описание HDL подобного
языка с мультиплексируемыми шинами сообщений. (Всё это лично мне
напомнило Алгоритмическую схему или графический язык Дракон, который
был описан в Книге Параджанова и релиз которого вышел на днях с
открытыми исходными кодами. Этот язык хорош для Актив Оберон, как и
концепция из этой статьи.)
Поддерживаются следующий типы данных логические, arbitrarily sized
integers, перечисляемый тип и структуры.  Сообщения входящие,
исходящие и от ОС. Есть переменные интерфейса и наборы состояний.
Сущности верхнего уровня в языке Термит является компонентом, которая
описывает драйвер устройства.

3.3 Интерфейс конечного автомата.
Каждое состояние описывается процессом. Сложные процессы составляются
из простых посредством операторов из Таблицы 1. Описание форматов
сообщений, правил перехода и триггеров Таймаута. (В точности описывает
4 и 6 уровни моей классификации функций из моей недописанной книги по
языку физической реальности).

4. Пример.
Описывает драйвер устройства хост контроллера Secure Digital (SD).

4.1 Обзор.
Это контроллер SD карты. Находиться между Центральным процессором и
считывателем карты. Спецификация интерфейса была взята из Verilol HDL
описания проекта ОпенКоре (Архитектура ядра открытая и опубликованная
компанией Сан Систем).  Три спецификации показаны на рис. 6. Авторами
статьи были сделаны ряд упрощений по управлению питанием и
игнорирования шины. Результат работы синтезатора представлен в разделе
6.

4.2 Спецификация класса устройства.
Форматы команд. Блоки данных. Смена частоты. И другие возможности устройства.

4.3 Интерфейс операционной системы.
Приведён на рис. 8. Далее комментарии к описанию.

4.4 Спецификация интерфейса устройства.
Приведена на рис. 9. Сделана на основе Verilog описания. Каждому
архитектурному делу ставиться в соответствии процесс и описываются его
интерфейсы.
Далее по тексту комментарии.

4.5 Конечный автомат драйвера.
Алгоритм построения конечного автомата будет представлен в разделе 5.
На рис. 11 приведён фрагмент конечного автомата, который получился без
стадии управления считыванием или записью данных. Далее описание
машины состояния с одним ветвлением, как на рис. 11.

5. Алгоритм синтезатора.
Имеет 3 стадии. 1. Объединение индивидуальных интерфейсов драйвера в
одно описание. 2. Установка ограничений среды. 3. Синтезация драйвера.

5.1 Соединение интерфейсов. Производиться за счёт декартового
умножения подпространств каждого интерфейса на основе 3 правил.

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

5.3 Генерация кода. Машина выстраивает не параллельную
последовательность действий по достижению цели и реализует её в Си
код.

5.4 Оптимизация. Делается за счёт упрощения условий и вычисляемых
значений (4 уровень в моём описании).

6. Оценка.
Тут сообщаются результаты синтеза не тривиальных драйверов для
различных операционных систем.

6.1 Реальный синтезируемый драйвер в 4 разв больше по объёму.
6.2 Производительность. Синтезируемый драйвер тратит на 1 процент
больше ресурсов процессора.
6.3 Автоматическая генерация драйвера для ФриБСД.

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

8. Связанные работы.
Генерация кода для ОС реального времени. Devil [17], NDL [5], and HAIL
[23].  Анализ исходного кода для экстракции спецификацй. Синтез
подхода анализа исходного кода драйвера на Си и описания на Verilog
HDL

3

Re: Автоматическая генерация исходного кода

Статья про автогенерацию исходного кода драйверов, за счёт порождения конечного автомата. Конечный автомат как найденный маршрут в лабиринте среды. Каждое состояние это один или несколько процессов (Активных объектов), которые комбинируются параллельно или последовательно (3.3 Interface state machines). Причём, совокупность возможных шагов устройства (интерфейсов) есть декартово произведение (5.1 Computing an aggregate specification)

4

Re: Автоматическая генерация исходного кода

Автор: *

интересно что с приходом технического прогресса машины заменили ручной труд людей.
все думали ну вот мы будем теперь сидеть и просто программировать эти машины.
Создание программы которая пишет программы(практически всегда эффективнее и безошибочнее чем человек) наверное лишит работы миллионы программистов((

Согласен с Вами и приведу ссылки на наиболее продвинутого специалиста в этой области и его прошлые проекты:

http://ryzhyk.net/

http://ssrg.nicta.com.au/projects/TS/drivers/synthesis/

http://ssrg.nicta.com.au/projects/TS/filesystems.pml

По моим сведениям, он первый человек который используя алгоритм игры сделал программу которая написала оптимальный драйвер для SD карты и других устройств. То есть заменил программиста программой :-) Не без гордости добавлю, что он работает в нашей корпорации (Samsung electronics RND), где работал и я во время моих лучших проектов.

https://github.com/termite2/specs

Это открытые спецификации для устройств, которые может прочитать эта программа пишущая драйвера для этих устройств.

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

http://ryzhyk.net/publications/Ryzhyk_CKSH_09.pdf

А вот это более свежая статья того же автора:
http://arxiv.org/pdf/1407.3681.pdf


(Понятно что это базируется на HDL подобных спецификациях железа и операционной системы, то есть люди без желания изучать железо и мат. часть пролетают как фанерный самолёт над Парижем)

5

Re: Автоматическая генерация исходного кода

http://riscv.org/

Вот открытая HDL архитектура. Карты в руки - генерируйте любые программы - все спецификации железа есть и их можно поменять и прошиться с новой архитектурой на FPGA.

6

Re: Автоматическая генерация исходного кода

Автор: *


А что плохого в этом? Что по Вашему в счет?

5. Алгоритм синтезатора.
Имеет 3 стадии. 1. Объединение индивидуальных интерфейсов драйвера в
одно описание. 2. Установка ограничений среды. 3. Синтезация драйвера.

5.1 Соединение интерфейсов (снизу уровень железа и сверху уровень вызовов OS). Производиться за счёт декартового умножения подпространств каждого интерфейса на основе 3 правил. По сути это операция [tex]\wedge[/tex] я двух симплексных многообразий.

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

5.3 Генерация кода. Машина выстраивает не параллельную
последовательность действий по достижению цели и реализует её в Си
код.

5.4 Оптимизация. Делается за счёт упрощения условий и вычисляемых
значений (4 уровень в моём описании)