Um primeiro kernel preemptivo no ARM Cortex-M3

1 Introdução

Quando se fala em sistemas operativos para software embarcado, em geral pensa-se que eles são um overkill (implementação cujo custo não compensa) para a maioria das soluções. No entanto entre uma aplicação completamente “hosted” (que faz uso de um SO multithread e de propósito geral) e outra completamente “standalone” ou “bare-metal” há muitas variações.

Em publicações anteriores eu explorei a noção de tarefas cooperativas, desde um loop fazendo chamadas a partir de um vetor de ponteiros para funções, até algo um pouco mais complexo com os processos sendo manejados em um buffer circular, com critérios temporais explícitos. Desta vez vou mostrar uma implementação preemptiva mínima, para também abrir o caminho para algo um pouco mais complexo, como nas outras publicações.

2 Preemptivo versus Cooperativo

Em um sistema cooperativo o processador não realiza a troca de contexto entre uma tarefa e outra, sendo necessário que a tarefa por si só libere o processador para a próxima ocupá-lo. Não há nada de errado nisto, este esquema Run-To-Completion é suficiente e/ou necessário para muitas aplicações, e muitos sistemas embarcados são assim executados, inclusive alguns muito complexos. Mais antigamente até sistemas não-embarcados utilizavam-se de kernel cooperativo (Windows 3.x, NetWare 4.x, entre outros). Se uma tarefa travar, o sistema todo fica comprometido quando falamos de um modo estritamente cooperativo (portanto em um sistema operacional para servidores como era o NetWare, isto não parece bom).

No modo preemptivo, tarefas são interrompidas e posteriormente resumidas – i.e, um contexto (conjunto de estados dos registradores do processador) é salvo e depois recuperado. Isto leva a maior complexidade na implementação do sistema mas, se bem implementado, aumenta a robustez e a possibilidade de atender a requisitos de tempo mais estreitos.

3 Call stack

Um processador é, para todos os efeitos, uma máquina de estados. Com alguma simplificação, cada estado do nosso programa pode ser definido como o conjunto de valores dos registradoresdo core. Este conjunto dita qual rotina do programa está ativa. Portanto, ativar uma tarefa significa lançar valores na call stack de forma que esta tarefa será processada. Para trocar de contexto é necessário salvar os dados da call stack naquele ponto do programa. Estes dados “congelados” representam um estado do programa e portanto são chamados de stack frame.

Para resumir uma tarefa, um stack frame previamente salvo é carregado novamente na call stack – os registradores reais do core.

No ARM Cortex-M3, são 17 registadores de 32-bit que definem o estado ativo do processador: R0-R12 para uso geral e R13-R15 registos de uso especial, além do Program Status Register (PSR).

3.1. Arquiteturas load-store

Uma arquitetura do tipo load-store é aquela em que um dado da memória precisa de ser carregado (load) aos registradores do core antes de ser processado. Também, o resultado deste processamento antes de ser armazenado (store) na memória deve estar em um registo. (Na figura abaixo o PSR não está representado)

As duas operações básicas de acesso a memória no Cortex-M3:

// lê o dado contido no endereço apontado por Rn + offset e o coloca em Rn.
LDR Rd, [Rn, #offset]
//armazena dado contido em Rn no endereço apontado por Rd + offset
STR Rn, [Rd, #offset]

É importante ainda compreender no mínimo as instruções assembly do Cortex-M3 mostradas abaixo. Sugiro as fontes [1] e [2] como boas referências, além deste ou este link.

MOV Rd, Rn // Rd = Rn
MOV Rd, #M// Rd = M, sendo o imediato um valor de 32 bit (aqui representado por M)
ADD Rd, Rn, Rm  //Rd = Rn + Rm
ADD Rd, Rn, #M //Rd = Rn + M
SUB Rd, Rn, Rm //Rd = Rn - Rm
SUB Rd, Rn, #M //Rd = Rn - M
// pseudo-instrucao para salvar Rn em uma posicão da memória.
// Após um PUSH, o valor do stack pointer é decrementado em 4 bytes, e o
PUSH {Rn} 
//Ao contrário do PUSH, o POP incrementa o SP após carregar o dado em Rn.
POP  {Rn} 
B label //pula para a rotina label
BX Rm //pula para a rotina especificada indiretamente por Rm
BL label //pula para label e passa endereco da prox. instrucao ao LR
         //para retornar LR=Link Register 
CPSID I //habilita interrupções
CPSIE I //desabilita interrupções

Vamos operar o M3 no modo Thumb, onde as instruções têm na verdade 16 bits. Segundo a ARM, isto é feito para melhorar a densidade de código mantendo os benefícios de uma arquitetura 32-bit. O bit 24 do PSR é sempre 1.

3.2. Stacks e o stack pointer (SP)

Stack é um modelo de uso da memória. Seu funcionamento se dá no formato Last InFirst Out (último a entrar, primeiro a sair). É como se eu organizasse uma pilha de documentos para ler. É conveniente que o primeiro documento a ser lido esteja no topo da pilha, e o último ao final.

Normalmente dividimos a memória entre heap e stack. Como dito, na “call stack” estarão contidos aqueles dados temporários que determinam o próximo estado do processador. No heap estão armazenados dados cuja natureza não é temporária no curso do programa (isto não significa “não-volátil”). O stack pointer é uma espécie de pivô que mantém o controle do fluxo do programa, ao apontar para alguma posição da stack.

Figura 3. Modelo de uso de uma stack. Ao salvarmos dados antes de processá-los (transformá-los) guardamos a informação anterior. (Figura de [1])
Figura 4. Regiões da memória mapeada em um Cortex M3. A região disponível para a stack está confinada entre os endereços 0x20008000 e 0 0x20007C00. [1]

4 Multitarefas no ARM Cortex M3

O M3 oferece dois stack pointers (Main Stack Pointer e Process Stack Pointer) para isolar os processos do usuário dos processos do kernel. Todo serviço de interrupção é executado no modo kernel. Não é possível ir do modo usuário ao modo kernel (na verdade chamados de thread mode e privileged mode) sem passar por uma interrupção – mas é possível ir do modo privilegiado ao modo usuário alterando o registro de controle.

Figura 5. Troca de contexto em um SO que isola a aplicação do kernel [1]

O core também tem hardware dedicado para a troca de tarefas. O serviço de interrupção SysTick pode ser usado para implementar a troca de contextos síncrona. Ainda existem outras interrupções assíncronas por software (traps) como o PendSV e o SVC. Assim, o SysTick é utilizado para as tarefas síncronas no kernel, enquanto o SVC serve às interrupções assíncronas, quando a aplicação faz uma chamada ao sistema. O PendSV é uma trap (interrupção via software) que por padrão só pode ser disparada também no modo privilegiado. Normalmente sugere-se [1] ativá-la no SysTick, porque assim é possível manter o controle dos ticks para atender aos critérios de tempo. A interrupção por SysTick é logo servida, não correndo-se riscos de perder algum tick do relógio. Uma implementação de S.O. seguro, utilizaria os dois stack pointers para separar threads de usuário e kernel, além de também separar os domínios de memória se houver uma MPU (Memory Protection Unit) disponível.

Figura 6. Leiaute da memória de dados em um SO com dois stack pointers e memória protegida [1]

Em um primeiro momento iremos utilizar somente o MSP em modo privilegiado.

5. Construção do kernel

Kernel é um conceito um tanto amplo, mas creio que não exista um S.O. cujo kernel não seja o responsável pelo escalonamento das tarefas. Além disso, minimamente deve haver também mecanismos de IPC (comunicação inter-processos). É interessante notar a forte hardware-dependência do escalonador que será mostrado, devido à sua natureza low-level.

5.1. Stackframes e troca de contexto

Lembre-se: call stack = os registradores verdadeiros do core; stack ou stackframe = estado (valores) dos registradores salvos na memória.

Quando um SysTick é atendido, parte da call stack é salva pelo hardware (R0, R1, R2, R3, R12, R14 (LR) e R15 (PC) e PSR). Vamos chamar esta porção salva pelo hardware de hardware stackframe. O restante é o software stackframe [3], que devemos explicitamente salvar e recuperar com as instruções PUSH e POP.

Para pensar nosso sistema, podemos esquematizar uma troca de contexto completa, delineando as posições-chave que o stack pointer assume durante a operação (na figura abaixo os endereços de memória aumentam, de baixo pra cima. Quando SP aponta para R4 está alinhado com um endereço menor que o PC da sua stack)

Figura 7. Troca de contexto. A tarefa ativa é salva pelo hardware e pelo kernel. O stackpointer é reassinalado conforme critérios, apontado para o R4 do próximo stackframe a ser ativado. Os dados são resgatados. A tarefa é executada. (Figura baseada em [3])

Quando uma interrupção ocorre, SP estará apontando para o topo do stack (SP(O)) a ser salvo. É inevitável que seja assim porque é assim que o M3 funciona. Numa interrupção o hardware irá a salvar os primeiro 8 registradores mais altos da call stack nos 8 endereços abaixo do stack pointer, parando em (SP(1)). Quando salvarmos os registradores que restam, o SP agora estará apontando para o R4 da stack atual (SP(2)). Ao reassinalarmos o SP para o endereço que aponta ao R4 do próximo stack (SP(3)), o POP joga os valores de R4-R11 à call stack e o stack pointer agora está em (SP(4)). Finalmente, o retorno da interrupção resgata os valores do hardware stackframe à call stack, e o SP(5) está no topo da stack que acabou de ser ativada. (Se estiver se perguntando onde está o R13: ele armazena o valor do stack pointer )

A rotina para troca de contexto é escrita em assembly e implementa exatamente o que está descrito na Figura 7.

Figura 8. Troca de contexto

PS: Quando uma interrupção ocorre, o LR assume um código especial. 0xFFFFFFF9, se a thread interrompida estava a utilizar o MSP ou 0xFFFFFFFD se a thread interrompida utilizava o PSP.

5.1 Inicializando as stacks para cada tarefa

Para que a estratégia acima funcione, precisamos inicializar as stacks de cada tarefa, de acordo. O sp começa apontando para R4. Este é por definição o stack pointer inicial de uma task, pois é o endereço mais baixo de um frame.

Além disso, precisamos criar uma estrutura de dados que aponte corretamente para as stacks que serão ativadas a cada serviço de SysTick. Normalmente chamamos esta estrutura de TCB (thread control block). Por enquanto não utilizamos nenhum critério de escolha e portanto não há parâmetros de controle além do next: quando uma tarefa é interrompida, a próxima da fila será resumida e executada.

Figura 9. Estruturas para controle das threads

A função kSetInitStack inicializa a stack de cada thread i“. O stack pointer na TCB associada aponta para o dado relativo ao R4. Os dados da stack são inicializados com o número do registro a que devem ser carregados para facilitar o debug. O PSR só precisa ser inicializado com o bit 24 em 1, que é o bit que identifica o modo Thumb. As tarefas são do tipo void Task(void* args).

Figura 10. Inicializando a stack

Para adicionarmos uma tarefa à stack, precisamos inicialmente do endereço da função principal da task. Além disso, também passaremos um argumento. O primeiro argumento fica em R0. Se mais argumentos forem necessários outros registradores podem ser usados, conforme o AAPCS (ARM Application Procedure Call Standard).

Figura 11. Rotina para adicionar as tasks e seus argumentos no stackframe inicial

5.3. Inicializando o kernel

Não basta inicializar as stacks e esperar a interrupção do SysTick. O sp da estrutura TCB só guardará um valor válido de stack pointer quando a tarefa for interrompida.

Num sistema preemptivo, temos dois tipos de threads a rodar: background e foreground. O background comporta as rotinas do kernel, entre elas, a troca de contexto. A cada SysTick, é vez do kernel utilizar o processador. No foreground estarão as aplicações.

Se a tarefa já não tiver sido executada, o stack pointer guardado em sp não será válido. Assim precisamos fazer parecer que a tarefa foi executada, interrompida e guardada – para ser reativada depois. Eu usei a seguinte estratégia:

  1. Uma interrupção é forçada (PendSV). Hardware stackframe inicial é salvo.
  2. tcb[0].sp é carregado em SP. SP agora tem o endereço do dado R4 da stackframe
  3. O R4R11 do core são carregados com os valores da stackframe inicializada.
  4. ISR retorna, recupera o hardware stack frame e o SP estará no topo da stack. O PC agora está carregado com o endereço da primeira chamada a ser feita, e o programa segue o fluxo.
Figura 12. Serviço de interrupção do PendSV para inicializar kernel

Em [2] é sugerido uma outra forma de inicializar o kernel, bem mais didática:

Figura 13. Rotina para inicializar o kernel

Dispensa-se a interrupção e a call stack é carregada ativando o LR com o valor do PC da stack. Após finalmente levar o SP ao topo da stack, o BX LR executa a task e retorna.

Se utilizarmos o primeiro método apresentado, kStart fica simplesmente:

// com a lib CMSIS
void kStart(void) 
{ 
   SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk; 
} 

6. Juntando as peças

Para ilustrar vamos executar, em Round-Robin, 3 tarefas que chaveiam a saída de 3 diferentes pinos e incrementam um contador cada. O tempo entre uma troca de contexto e outro será de 1000 ciclos do relógio principal. Perceba que estas funções rodam dentro de um “while(1) { }”. É como se tivéssemos vários programas principais sendo executados no foreground. Cada stack tem 64 elementos de 4 bytes (256 bytes).

Figura 14. Tasks do sistema

Abaixo a função main do sistema. O hardware é inicializado. As tarefas são adicionadas e as stacks inicializadas com a função kAddThreads. O RunPtr recebe o endereço da thread 0. Após configurar o SysTick para disparar a cada 1000 ciclos de clock, inicializa-se o kernel. Depois de executar a primeira tarefa e ser interrompido, o sistema fica quicando entre uma tarefa e outra, com a troca de contexto a rodar no background.

Figura 15. Programa principal

6.1. Debug

Você vai precisar pelo menos de um simulador para implementar mais facilmente o sistema, pois precisará acessar os registradores do core (call stack) e ver os dados movimentando-se nas stacks. Se o sistema estiver a funcionar, a cada pausa do debugger os contadores devem ter praticamente o mesmo valor.

Na foto abaixo, utilizo uma placa Arduino Due com o processador Atmel SAM3X8E e um debugger Atmel ICE conectado na JTAG da placa. No osciloscópio pode-se ver as formas de onda das saídas chaveando de cada uma das 3 tasks.

Figura 16. Bancada para debug
Figura 17. Tasks 1, 2, 3 no osciloscópio.

7 Considerações finais

A implementação de um kernel preemptivo exige razoável conhecimento da arquitetura do processador a ser utilizado. Carregar os registradores da call stack e salvá-los de forma “artesanal” nos permite ter um maior controle do sistema às custas da complexidade de manejarmos as stacks.

O exemplo aqui apresentado é um exemplo mínimo onde cada tarefa recebe o mesmo tempo para ser executada. Após esse tempo, a tarefa é interrompida e suspensa – os dados da call stack são salvos. Este conjunto salvo chamamos de stackframe – uma “fotografia” da ponto do programa que estava a ser executado. A próxima tarefa a ser executada é carregada do ponto de onde parou e resumida. O código foi escrito de forma a explicitar os conceitos.

Na próxima publicação iremos adicionar prioridade às tarefas e separar as threads entre modo usuário e modo privilegiado – utilizando os dois stack pointers – requisito fundamental para um sistema mais seguro.

Referências

O texto desta postagem bem como as figuras não referenciadas são do autor.
[1] The definitive guide to ARM Cortex-M3 , Joseph Yiu
[2] Real-Time Operating Systems for the ARM Cortex-M, Jonathan Valvano
[3] https://www.embedded.com/taking-advantage-of-the-cortex-m3s-pre-emptive-context-switches/