Как Составить Функцию Инициализации Микроконтроллера (Топологическая Сортировка Графов)
В программировании микроконтроллеров первая задача, которую всегда приходится решать — это определить в каком порядке производить инициализацию прошивки. Дело в том, что прошивка состоит из набора программных компонентов. Каждый компонент как правило вызывает функции из других программных компонентов. Это нормальное явление. Так происходит пере использование кодовой базы.
При этом чтобы код корректно работал надо начинать пользоваться программным компонентом только после того, как он будет проинициализирован. Инициализация это по сути настройка. У каждого программного компонента есть функция
bool xxx_init(void);и надо понимать, когда эту функцию вызывать. То есть, до и после чего вызывать функцию xyz_init ()?
В переводе на кухонный язык каждое утром вы надеваем одежду, чтобы выйти на улицу. Понятное дело, что не имеет смысла надавать носки после того как надета обувь. Не имеет смысла надевать рубашку, когда надета куртка и т. п. Так же и в программировании микроконтроллеров. Нет смысла инициализировать подсистему UART, если не проинициализирован GPIO.
Проблема в том, что в каждой взрослой прошивке программных компонентов десятки. И зависимостей у каждого из них тоже много: по 5–7 штук. При этом программные компоненты пишут другие программисты указывая только текстовый файлик с зависимостями для своего программного компонента. Одновременно с этим вам для конкретной сборки надо, по мере возможности, так выставить последовательность инициализации, чтобы всё корректно прогрузилось и не заклинило.
Основная трудность в том, что перед написанием кода инициализации не очевидна оптимальная последовательность инициализации системы.
Радость лишь в том, что эту задачу можно решить чисто формальными методами. То есть к этой проблеме можно подойти с точки зрения дискретной математики!
Постановка задачи
Есть неупорядоченное множество компонентов. Просто набор строк (токенов), разделённых запятой.
Button,FlashFs,I2S,Log,StartPause,Writer,NVIC,Clk,SysTick,
Flash,Timer,GPIO,UART,Swd,ADC,I2C,SPI,CAN
,WatchDog,Pwm,DMA,Mcu,SwDac,
RS485,StringReader,CLI,IsoTp,
UDS,Relay,LedMono,NVS,Param,Heap,Time,
SuperCycle,task,UnitTest,Nau8814У каждого компонента есть зависимости. Как правило несколько. У каких-то тривиальных компонентов нет зависимостей.
start_pause,Clk
Writer,UART
Log UART
Clk,
Flash
SysTick,Clk
Timer, Clk
GPIO,
UART, GPIO
Swd,GPIO...
ADC,AdcChannels,..
I2C,GPIO UART
SPI,GPIO UART
CAN,GPIO
I2S,GPIO DMA
WatchDog,
RS232,GPIO UART
RS485,GPIO
StringReader,
CLI,RS232
Relay,GPIO Time
LedMonoInit,
NVS,Flash
Flash_FS, NVS Flash
Param, Flash_FS
SuperCycle,
task, SuperCycle
Получается ориентированный граф зависимостей программных компонентов. Вот, например, граф программных зависимостей для прошивки культового аппаратного менеджера паролей Pastilda
От нас требуется, не много не мало, упорядочить граф в массиве последовательность компонентов так, чтобы те компоненты у которых много зависимостей оказались справа (→). Те у которых мало зависимостей — слева (<-). Только и всего..
То есть надо обойти граф в порядке увеличения количества зависимостей. В дискретной математике эту процедуру называют Топологическая Сортировка графа.
Разумеется, надо написать компьютерную программу, которая и будет делать всю эту работу за нас.
Решение. Основная идея.
Ситуация осложняется еще и тем, что граф зависимостей программных компонентов это как бы два или три отдельных графа. Обычно это даже и не дерево, а лес.
Есть специальные алгоритмы для построения этого обхода. Однако они требуют динамического выделения памяти и рекурсию. Мне, как программисту микроконтроллеров, это делать не привычно, ибо во всех прошивках для МК всегда есть два золотых MISRA запрета:
1--Запрет на динамическую память.
2--Запрет на рекурсию.
Поэтому я изложу одно из наивных решений этой задачи, оперируя даже не графами, а строчками!
Итак, танцуем от печки… Пусть у нас есть вот такой простецкий граф зависимостей.
Идея очень проста. Объясню на примере. Допустим надо проинициализировать условные программные компоненты g, n, a, t.
Фаза 1 (Вставка)
На первом шаге мы просто на место каждого элемента в строке подставляем сам компонент и его зависимости. Вот так.
Фаза 2 (Удалить повторы)
В результирующей строке следует удалить повторы. То есть w. Причем, удалять надо слева (<). Ибо компонент уже проинициализировался справа (>). Повторная инициализация не имеет смысла, а порой и вовсе приводит к заклиниванию и осечкам в прошивке.
Фаза 3 (Повтор)
Продолжая эти процедуры замены (фаза1) и удаления повторов слева (фаза2) после нескольких итераций кристаллизируется решение задачи.
Фаза 4 (Зеркальное отражение)
Инвертировать элементы в финальной последовательности. В сухом остатке остается последовательность c y k t o b a p x l w q v n j q.
Проверка показывает, что обход всегда происходит вдоль рёбер ориентации графа. Это хорошая новость. Значит, что решение корректное.
Практическая часть.
Теперь следует реализовать этот алгоритм в коде. Причем желательно на Си, ибо сами прошивки мы пишем на Си. Поэтому репозиторий уже обогащён проверенными наработками по обработке формата CSV и алгоритмам на строчках.
Я написал на Си консольную Win утилиту, которая делает всю эту обработку текстовых CSV строчек. В качестве файла с зависимостями я подал на вход описание леса
ADC,GPIO,NVIC,DMA
AdcChannels
Array
Audio,SwDac,Math
Button,GPIO,Time
CAN,GPIO,NVIC,DMA
CRC
Cli,Log,StringReader
Clk,StartPause
DID
DMA,NVIC,DmaChannels
DmaChannels
Fifo
Flash,Array
FlashFs,NVS,Flash
GPIO,Time
Heap
I2C,GPIO,NVIC,DMA
I2S,GPIO,SPI,NVIC,DMA
Intervals
IsoTp,CAN,Time
LedMono,GPIO,Time,Math
Limiter,Time,Flash
Log,Time,Writer
Math
NVIC
NVS,Flash,CRC,Intervals
Nau8814,I2S,I2C,GPIO,Pwm,Task,Cli,Audio
Param,Flash,FlashFs
Pwm,GPIO,Timer
RS232,UART,Fifo
RS485,UART,Fifo
Relay,GPIO,Time
SPI,GPIO,Time,DMA
StartPause,
Stream,Fifo
String,Array
StringReader,Fifo,UART,String
SuperCycle,Task,Time
SwDac,Array,Math,Time,Heap
Swd,GPIO
SysTick,Clk,NVIC
Task,Time,Flash,Limiter
Time,Timer,SysTick
Timer,Clk,NVIC,Math,DMA
UART,GPIO,Fifo,Time,NVIC,DMA
UDS,IsoTp,DID,CAN
UnitTest,Cli
WatchDog,Clk
Writer,Stream
в качестве набора компонентов я подал CSV строку
StartPause,Writer,Log,NVIC,Clk,SysTick,Flash,
Timer,GPIO,UART,Swd,ADC,AdcChannels,I2C,SPI,
CAN,I2S,WatchDog,Pwm,DMA,DmaChannels,SwDac,RS232,
RS485,StringReader,Cli,IsoTp,UDS,DID,Relay,LedMono,
NVS,FlashFs,Param,Heap,Time,SuperCycle,Task,Button,UnitTest,Nau8814В результате утилита любезнейшим образом порекомендовала мне выполнить инициализацию системы вот в такой последовательности:
Math,Heap,NVIC,,StartPause,Clk,SysTick,
DmaChannels,DMA,Timer,Time,Array,SwDac,Audio,String,
Fifo,GPIO,UART,StringReader,Stream,Writer,Log,Cli,Flash,
Limiter,Task,Pwm,I2C,SPI,I2S,Nau8814,UnitTest,Button,
SuperCycle,Intervals,CRC,NVS,FlashFs,Param,LedMono,Relay,
DID,CAN,IsoTp,UDS,RS485,RS232,WatchDog,ADC,Swd,AdcChannelsИнтуитивно это выглядит тоже вполне корректно. Вот мы и получили план по загрузке прошивки. Никакой импровизации, всё формально математически обосновано.
Основной Си-код с решением
#include "topo_sort.h"
#include
#include
#include
#include
#include
#include "str_utils_ex.h"
#include "topo_sort_diag.h"
#include "log.h"
#include "code_generator.h"
#include "csv.h"
#define RES_SIZE 5000
#define ONE_DEP_SIZE 1000
#define MAX_DEP_LIST 200
typedef struct {
char name[ONE_DEP_SIZE];
bool valid;
uint32_t size;
uint32_t child_cnt;
}DepNode_t;
#define TOPO_SORT_COMMON_VARIABLES \
uint8_t num; \
char* name; \
bool valid;
typedef struct {
TOPO_SORT_COMMON_VARIABLES
DepNode_t DepArray[MAX_DEP_LIST];
char result[RES_SIZE];
char result2[RES_SIZE];
}TopoSortHandle_t;
typedef struct {
TOPO_SORT_COMMON_VARIABLES
}TopoSortConfig_t;
COMPONENT_GET_NODE(TopoSort, topo_sort)
COMPONENT_GET_CONFIG(TopoSort, topo_sort)
bool topo_sort_init_custom(void) {
bool res = true ;
LG_level_get_set(LINE, LG_LEVEL_INFO );
LG_level_get_set(TOPO_SORT, LG_LEVEL_INFO );
return res;
}
static DepNode_t* TopoSortNameToDep(TopoSortHandle_t* Node, char* name){
DepNode_t* Dep = NULL;
uint32_t i = 0 ;
bool res = false;
uint32_t cnt = MAX_DEP_LIST;
for(i=0;iDepArray[i].valid) {
char node_name[100]={0};
res = csv_parse_text(Node->DepArray[i].name, ',', 0, node_name, sizeof(node_name));
if(res) {
int ret = 0;
ret=strcmp(name,node_name);
if(0==ret){
Dep=&Node->DepArray[i];
}
}
}
}
return Dep;
}
bool csv_delete_duplicat_left(char * csv_text){
bool res = false ;
if(csv_text){
uint32_t node_cnt=0;
node_cnt = csv_cnt(csv_text, ',');
LG_PARN(TOPO_SORT, "SwCnt:[%u]", node_cnt);
uint32_t i = 0;
for(i=0; iresult2,0,sizeof(Node->result2));
uint32_t node_cnt = csv_cnt(Node->result, ',');
LG_DEBUG(TOPO_SORT, "SwCnt:[%u]", node_cnt);
uint32_t i = 0;
for(i=0;iresult, ',', i, node_name, sizeof(node_name));
if(res) {
DepNode_t* DepNode=TopoSortNameToDep(Node, node_name);
if(DepNode) {
LG_DEBUG(TOPO_SORT, "i:%u,+Deps[%s]", i,DepNode->name);
if(0result2,"%s,%s",Node->result2,DepNode->name);
} else {
sprintf(Node->result2,"%s",DepNode->name);
}
LG_PARN(TOPO_SORT, "%u,Raw[%s]",i, Node->result2);
}else{
LG_ERROR(TOPO_SORT, "NoDeps:i:%u,[%s]", i,node_name);
}
}else{
LG_ERROR(TOPO_SORT, "Err:i:%u", i);
}
}
LG_DEBUG(TOPO_SORT, "Raw[%s]", Node->result2);
/*Delete duplicat from left*/
res =csv_delete_duplicat_left(Node->result2);
LG_WARNING(TOPO_SORT, "-Dups[%s]", Node->result2);
memcpy(Node->result,Node->result2,sizeof(Node->result2));
}
return res;
}
bool topo_sort_load_dep(uint8_t num, char* const sw_dep){
bool res = false ;
LG_WARNING(TOPO_SORT, "LoadDep:[%s]", sw_dep);
TopoSortHandle_t* Node=TopoSortGetNode(num);
if(Node){
strcpy(Node->result, "");
strcpy(Node->result2, "");
FILE* FilePrt = NULL;
char str_line[1000] = {0};
FilePrt = fopen(sw_dep, "r");
uint32_t cnt=0;
if(FilePrt) {
strcpy(str_line, "");
LG_INFO(TOPO_SORT, "File [%s] OpenOk", sw_dep);
while(NULL != fgets(str_line, sizeof(str_line), FilePrt)) {
size_t len=strlen(str_line);
if(len){
uint32_t node_cnt = csv_cnt(str_line, ',');
LG_INFO(TOPO_SORT, "+L:%u,[%s]%u],DepCnt:[%u]",cnt,str_line,len, node_cnt);
str_del_char_inplace(str_line, '\n');
str_del_char_inplace(str_line, '\r');
memset(Node->DepArray[cnt].name,0,sizeof(Node->DepArray[cnt].name));
memcpy(Node->DepArray[cnt].name,str_line,len-1);
Node->DepArray[cnt].size = len-1;
Node->DepArray[cnt].valid = true;
Node->DepArray[cnt].child_cnt=node_cnt-1;
char node_name[100]={0};
res = csv_parse_text(str_line, ',', 0, node_name, sizeof(node_name));
if(res){
LG_INFO(TOPO_SORT, "%u,SwCom:[%s]Child:%u",cnt, node_name,node_cnt-1);
res = true;
}else{
res = false;
LG_ERROR(TOPO_SORT, "GetErr:%u",cnt);
}
}
strcpy(str_line, "");
cnt++;
}
fclose(FilePrt);
}else{
LG_ERROR(TOPO_SORT, "FileOpenErr");
}
}
return res;
}
bool topo_sort_run(uint8_t num, char* const sw_comps, char* const sw_dep){
bool res = false ;
TopoSortHandle_t* Node=TopoSortGetNode(num);
if(Node) {
strcpy(Node->result, "");
LG_WARNING(TOPO_SORT, "GenerateInit:[%s]Dep:[%s]", sw_comps,sw_dep);
res = topo_sort_load_dep(num, sw_dep);
FILE* FilePrt = NULL;
char csv_line[1000] = {0};
FilePrt = fopen(sw_comps, "r");
uint32_t cnt = 1;
if(FilePrt) {
LG_INFO(TOPO_SORT, "File [%s] OpenOk", sw_comps);
strcpy(csv_line, "");
while(NULL != fgets(csv_line, sizeof(csv_line), FilePrt)) {
uint32_t node_cnt = csv_cnt(csv_line, ',');
LG_INFO(TOPO_SORT, "Line:%u,SwComCnt:[%u]",cnt, node_cnt);
uint32_t i = 0 ;
for(i=0;iresult,RES_SIZE,"%s,%s",Node->result,node_name);
}else{
snprintf(Node->result,RES_SIZE,"%s",node_name);
}
uint32_t cnt = csv_cnt(Node->result, ',');
LG_DEBUG(TOPO_SORT, "+Set:%u:[%s]",cnt, Node->result);
} else {
LG_ERROR(TOPO_SORT, "GetErr:%u",i);
}
}
res = true;
strcpy(csv_line, "");
cnt++;
}
fclose(FilePrt);
}else{
LG_ERROR(TOPO_SORT, "FileOpenErr");
}
uint32_t i=0 ;
for(i=0;i<10;i++) {
LG_NOTICE(TOPO_SORT, "Set:[%s]",Node->result);
topo_sort_proc_ll(Node);
}
}
return res;
}
bool topo_sort_init_one(uint8_t num) {
LG_WARNING(TOPO_SORT, "INIT:%u", num);
bool res = false;
const TopoSortConfig_t* Config = TopoSortGetConfig(num);
if(Config) {
LG_WARNING(TOPO_SORT, "%s", TopoSortConfigToStr(Config));
TopoSortHandle_t* Node = TopoSortGetNode(num);
if(Node) {
Node->num = Config->num;
Node->valid = true;
memset(Node->result2,0,sizeof(Node->result2));
memset(Node->result,0,sizeof(Node->result));
strcpy(Node->result2,"");
strcpy(Node->result,"");
LG_level_get_set(TOPO_SORT, LG_LEVEL_INFO );
LG_level_get_set(LINE, LG_LEVEL_INFO );
res = true;
}
}
return res;
}
COMPONENT_INIT_PATTERT(TOPO_SORT, TOPO_SORT, topo_sort)
Развитие задачи
Топологическая сортировка текстовых токенов может быть также весьма полезна при монтаже электронных плат PCB. Дело в том, что существуют такие электронные компоненты, что припав один элемент не влезет очередной элемент расположенный рядом. По сути эту же консольную утилиту можно использовать для планирования работ по пайки электронных компонентов на PCB.
Вывод
Удалось разработать методику выработки корректной последовательности инициализации программных компонентов в прошивке для микроконтроллеров.
Удалось составить консольную Cи утилиту, которая находит топологическую сортировку для графа на основе списка смежности.
Это открывает дорогу для автоматической генерации массива инициализации на основе графа зависимостей между программными компонентами.
Если вам нужна готовая утилита топологической сортировки текстовых токенов, то пишите, я пришлю *.exe дистрибутив.
Links
