aabzel 4 июн в 01:01

Как составить функцию инициализации микроконтроллера (Топологическая сортировка графов утилитой Make)

Простой

14 мин

5.4K

Системное программирование*C*Математика*Промышленное программирование*Программирование микроконтроллеров*

Туториал

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

При этом, чтобы код корректно работал надо начинать пользоваться программным компонентом только после того, как он будет проинициализирован. Инициализация это по сути настройка. У каждого программного компонента есть функция

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 <math.h>
#include <math.h>
#include <stddef.h>
#include <string.h>
#include <stdio.h>

#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;i<cnt;i++) {
        if(Node->DepArray[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; i<node_cnt; i++) {
            LG_PARN(TOPO_SORT, "%u:Text[%s]",i, csv_text);
            char node_name[100] = {0};
            res = csv_parse_text(csv_text, ',', i, node_name, sizeof(node_name));
            if(res) {
                int ret = 0 ;
                ret = strcmp("",node_name);
                if(0!=ret) {
                    uint32_t dup_cnt = csv_count_node(csv_text, ',' ,node_name);
                    if(1 < dup_cnt) {
                        LG_DEBUG(TOPO_SORT, "%u:Duplicant:[%s][%u]",i, node_name,dup_cnt);
                        uint32_t d=0;
                        for(d=0 ; d<(dup_cnt-1); d++){
                            char temp[200] = {0};
                            snprintf(temp,sizeof(temp),",%s,",node_name);
                            LG_DEBUG(TOPO_SORT, "TryDel[%s]",temp);
                            //str_del_substr_inplace_firts(csv_text, temp);
                            //res = replace_substring_first( csv_text, temp, ",") ;
                            replaceFirstOccurrence( csv_text, temp, ",") ;
                            i=0;
                        }
                    }
                }
            } else {
                LG_ERROR(TOPO_SORT, "%u:NoNode",i);
            }
            node_cnt = csv_cnt(csv_text, ',');
            LG_PARN(TOPO_SORT, "SwCnt:[%u]", node_cnt);
        }
    }
    return res;
}

bool topo_sort_proc_ll(TopoSortHandle_t* Node){
    bool res = false ;
    if(Node) {
        LG_DEBUG(TOPO_SORT, "Proc:");
        memset(Node->result2,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;i<node_cnt;i++) {
            char node_name[200] = {0};
            res = csv_parse_text(Node->result, ',', 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(0<i) {
                       sprintf(Node->result2,"%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;i<node_cnt;i++){
                    char node_name[100] = {0};
                    res = csv_parse_text(csv_line, ',',   i, node_name, sizeof(node_name));
                    if (res) {
                        LG_DEBUG(TOPO_SORT, "%u,SwCom:[%s]",i, node_name);
                        if(0<cnt){
                            snprintf(Node->result,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)

Второй вариант

На самом деле чтобы решить эту продуктовую задачу даже не нужно писать никакого нового своего кода! Можно просто воспользоваться старой доброй всеядной культовой утилитой Стюарта Фельдмана make 1976 года. У этой утилиты так много профессий, что и перечислять устанешь. В частности эта утилита умеет обходить ориентированный граф зависимостей.
Сейчас объясню как... Вот тут в файле MakeTopoSort мы просто декларативно перечисляем с какими программными компонентами хотим работать.


INIT_ORDER +=

SW_COMP += UnitTest
SW_COMP += StartPause
SW_COMP += AdcChannels
SW_COMP += Writer
SW_COMP += CAN
SW_COMP += Log
SW_COMP += Clk
SW_COMP += SysTick
SW_COMP += Flash
SW_COMP += Timer
SW_COMP += Button
SW_COMP += LedMono
SW_COMP += FlashFs
SW_COMP += GPIO
SW_COMP += RS485
SW_COMP += Nau8814
SW_COMP += NVS
SW_COMP += SPI
SW_COMP += WatchDog
SW_COMP += Cli
SW_COMP += Pwm
SW_COMP += DmaChannels
SW_COMP += SwDac
SW_COMP += RS232
SW_COMP += StringReader
SW_COMP += DMA
SW_COMP += IsoTp
SW_COMP += I2C
SW_COMP += UDS
SW_COMP += DID
SW_COMP += Relay
SW_COMP += I2S
SW_COMP += Heap
SW_COMP += Swd
SW_COMP += Param
SW_COMP += UART
SW_COMP += Time
SW_COMP += SuperCycle
SW_COMP += Task
SW_COMP += NVIC
SW_COMP += ADC

include sw_comp_dep.mk

init: $(SW_COMP)
	@echo $@
	@echo $(info ORDER:[$(INIT_ORDER)])
	@echo $(info SET:[$(SW_COMP)])

Указываем зависимости в другом файлике sw_comp_dep.mk


ADC: GPIO NVIC DMA AdcChannels
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

AdcChannels :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Array :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Audio :SwDac Math
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Button :GPIO Time
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

CAN :GPIO NVIC DMA
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

CRC :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Cli :Log StringReader
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Clk :StartPause
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

DID :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

DMA :NVIC DmaChannels
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

DmaChannels :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Fifo :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Flash :Array
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

FlashFs :NVS Flash
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

GPIO :Time
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Heap :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt


I2C :GPIO NVIC DMA
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

I2S :GPIO SPI NVIC DMA
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Intervals :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

IsoTp :CAN Time
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

LedMono : GPIO Time Math
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Limiter :Time Flash
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Log :Time Writer
	@echo $@
	@echo $@ >> init.txt
	$(eval INIT_ORDER += $@)

Math :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

NVIC :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

NVS :Flash CRC Intervals
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Nau8814 :I2S I2C GPIO Pwm Task Cli Audio
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Param :Flash FlashFs
	@echo $(info $@ )
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Pwm :GPIO Timer
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

RS232 :UART Fifo
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

RS485 :UART Fifo
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Relay :GPIO Time
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

SPI :GPIO Time DMA
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

StartPause :
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Stream :Fifo
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

String :Array
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

StringReader :Fifo UART String
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

SuperCycle :Task Time
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

SwDac :Array Math Time Heap
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Swd :GPIO
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

SysTick :Clk NVIC
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Task :Time Flash Limiter
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Time :Timer SysTick
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Timer :Clk NVIC Math DMA
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

UART :GPIO Fifo Time NVIC DMA
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

UDS :IsoTp DID CAN
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

UnitTest :Cli UDS Param
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

WatchDog :Clk
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

Writer :Stream
	@echo $@
	$(eval INIT_ORDER += $@)
	@echo $@ >> init.txt

и запускаем *.bat скрипт

cls
echo off

set batdir=%~dp0
echo batdir=%batdir%
cd %batdir%

echo  > init.txt
make.exe --always-make --file=MakeTopoSort -i -k init

Получаем результат

В этой же папке кристаллизируется файл init.txt, который и содержит правильную последовательность инициализации. Вот она на вашем экране:

StartPause,Clk,NVIC,Math,DmaChannels,DMA,Timer,SysTick,
Time,Fifo,Stream,Writer,Log,GPIO,UART,Array,String,StringReader,
Cli,CAN,IsoTp,DID,UDS,Flash,CRC,Intervals,NVS,FlashFs,Param,
UnitTest,AdcChannels,Button,LedMono,RS485,SPI,I2S,I2C,Pwm,Limiter,
Task,Heap,SwDac,Audio,Nau8814,WatchDog,RS232,Relay,Swd,SuperCycle,ADC,

Успех!

Развитие задачи

I) Топологическая сортировка текстовых токенов может быть также весьма полезна при монтаже электронных плат PCB.

На то есть две причины:

1--Дело в том, что существуют такие электронные компоненты, что припаяв один элемент, не влезет очередной элемент расположенный рядом.

2--Бывает так, что плату проверяют уже во время построения. Например, нет смысла припаивать микроконтроллер, если не собраны каскады питания и кварцевый генератор не выдает нужную частоту. Иначе вы просто соберёте бракованное изделие. История была такая уже не один раз.

По сути, эту же консольную утилиту make можно использовать для планирования работ по пайке электронных компонентов на PCB.

Так можно автоматически составлять инструкции для сборки абсолютно чего угодно, не только PCB, начиная от двигателя внутреннего сгорания заканчивая авиалайнером.

II) Также топологическая сортировка может пригодится менеджерам для составления плана работ по воплощению какого-либо проекта. Той же разработки ПО или аппаратуру. Можно сформировать учебный план для института. Да всё что угодно, где так или иначе есть то, что должно быть сделано в первую очередь.

Итоги

Удалось разработать методику выработки корректной последовательности инициализации программных компонентов в прошивке для микроконтроллеров.

Удалось составить консольную Cи утилиту, которая находит топологическую сортировку для графа на основе списка смежности. Также удалось научиться делать топологическую сортировку утилитой make.

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

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

Links

№	Название	URL
1	Генерация зависимостей внутри программы	https://habr.com/ru/articles/765424/
2	Топологическая сортировка графа	https://www.youtube.com/watch?v=o0P8oNXoA_w
4	Топологическая сортировка	https://habr.com/ru/companies/otus/articles/499138/
5	Магия makefile на простых примерах	https://microsin.net/programming/arm/learning-makefile-with-simple-examples.html
6	Change Makefile variable value inside the target body	https://stackoverflow.com/questions/2711963/change-makefile-variable-value-inside-the-target-body

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Вам приходилось использовать теорию графов в программировании микроконтроллеров?

16.67% да5

83.33% нет25

Проголосовали 30 пользователей. Воздержались 4 пользователя.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Вам приходилось строить граф зависимостей в пайке PCB?

8% да2

92% нет23

Проголосовали 25 пользователей. Воздержались 7 пользователей.

Теги:

Хабы:

Как составить функцию инициализации микроконтроллера (Топологическая сортировка графов утилитой Make)

Публикации

Истории

Работа

Ближайшие события