Padrões de design para comunicação interprocessos em software embarcado (1/2)

A quem interessar: A depender do dispositivo em que escrevi parte dos textos, algumas palavras estão grafadas em português brasileiro (o meu nativo) ou português europeu (quando o auto corretor assim desejou).

1. Introdução

Nos dois últimos artigos demonstrei um pequeno kernel com escalonador de tarefas cíclico, porém preemptivo (round-robin) implementado em um ARM Cortex-M3. Além do escalonamento de tarefas também separavam-se os processos de usuário dos processos de supervisor, o que trouxe a necessidade da implementação de mecanismos de System Calls.

Durante os artigos, muitas vezes mencionei que o kernel ainda não estava preparado para a sincronização de tarefas e gerenciamento de recursos, ou de forma geral, não havia mecanismos para comunicação interprocessos.

Se quisermos generalizar o uso deste kernel – i.e., reutilizá-lo para uma solução em que as tasks não atuam isoladamente, um ou mais mecanismos de IPC é fundamental. Se por um lado os processos precisam cooperar para atingir determinados objetivos, por outro eles concorrem pelo uso limitado de recursos. [4]

2. IPCs: proteger e coordenar

O fenômeno que nos leva à necessidade de comunicação interprocessos é o da  Concorrência: os recursos finitos de um computador faz com que seja necessário coordenar as diversas actividades que concorrem simultaneamente ou paralelamente. Isto nos leva a ter que proteger uma atividade dos efeitos de outra e sincronizar atividades que são mutualmente dependentes. [4]

Figura 1. Multithreading e multiprocessing, conceitualmente [2]

Na publicação passada em que três tasks acessavam o mesmo hardware para imprimir na tela do PC, a coordenação para compartilhar o recurso foi feita com o sinal de TX_READY lido no registro do próprio dispositivo. Independente da quota de tempo que cada task tinha para ser executada, o kernel só liberava o processador após garantir que os dados da UART haviam sido transmitidos ao computador. Uma forma de IPC que não abstrai o hardware (UART) ou a aplicação (transmitir dados).

static void SysCallUART_PrintLn_(const char* args)
{
    __disable_irq(); // sessão crítica inicio
    uart_write_line(UART, args); // transmite dados        
    while (uart_get_status(UART) != UART_SR_TXRDY); //aguarda fim da transmissão
    __enable_irq(); // sessão crítica fim
    exitKernel_();
}

Lista 0. System Call lendo diretamente o sinal de TX_READY em uma critical region para coordenar as tarefas de acesso à UART

2.1. A Unidade Concorrente

O design do modelo de concorrência é uma parte crítica na arquitetura do sistema a ser desenvolvido. Vamos definir Process, Task e Thread.

Entendo um Process como algo estático (previamente definido) e encapsulado. Uma Task é um processo em execução. As Threads são tasks que acabam por ser dependentes entre si: uma consequência da topologia do sistema em que estes processos são executados [2, 3]. Se analisarmos a Figura 1, é intuitivo notar que a multithreading implica em complexidade de implementação em troca de economia/limitação de recursos.

Para efetivamente entender estes conceitos e modelar a arquitectura mais adequada ao gerenciamento da concorrência de tarefas em um dado sistema, a melhor definição que eu conheço é a de Unidade Concorrente [1]: 

«Unidade Concorrente é um conjunto de ações seqüenciais no mesmo segmento de execução. Também conhecido como task ou thread.» Em [2] uma Thread é definida como o «contexto de um processo em execução» – i.e., o contexto de uma Task – o que não se sobrepõe ou contradiz a definição dada por [1], e complementa a ideia de que uma thread é essencialmente dinâmica. Não à toa, a estrutura de dados em que salvamos o contexto de uma task é classicamente chamada de Thread Control Block.

Powell em [1] ainda observa: «muitos fazem uma distinção entre Task, Thread e Process. Entretanto, todos são o mesmo conceito em diferentes escopos.» Novamente analise a Figura 1. Se o “escopo”for a granularidade, diante do que consta na literatura apresentada, podemos dizer sem danos que: a thread é a menor unidade concorrente de um sistema quando em execução.

Figura 2. A, B, C e D são Unidades Concorrentes: a) A compartilhar um único core (pseudoconcorrentes)  b) Cada unidade tem seu próprio core c) Em execução, somente uma unidade concorrente estará activa em um dado instante de tempo (adaptado de [3])

2.2 A necessidade de sincronização

Antes de prosseguirmos, mais uma definição:

«Pontos de sincronização são aqueles em que as tasks compartilharão informações e/ou garantirão que determinadas pré-condições estejam satisfeitas antes  de prosseguirem.» [1]

A Figura 3 ilustra esta ideia. A barreira de sincronização só permite que o programa siga adiante quando todos os processos tiverem atingido aquele ponto – i.e., as condições para que todas as ações do sistema estejam corretamente sincronizados são verdadeiras.

Figura 3. a) Processos em execução b) Todos os processos exceto C estão prontos c) Assim que o processo C atinge o ponto de sincronização, o programa segue adiante. [3]

Eu prefiro o termo coordenação a sincronização, porque sincronia não é necessariamente um fenômeno desejável ou relacionado entre duas partes, portanto, gosto da ideia de pontos de coordenação. A literatura entretanto normalmente utiliza o termo sincronizado como sinônimo de coordenado.

A Figura 4 mostra unidades concorrentes, modeladas em três tasks. O que sabemos sobre elas? Se a analisarmos individualmente fica claro que na Task 1 a Acção A ocorre antes da B, que percorre um caminho condicional até chegar a E. O mesmo raciocínio  vale para as Tasks 2 e 3.

De que forma as acções individuais das Tasks 1, 2, e 3 relacionam-se entre si? Se a resposta (verdadeira) for “não se relacionam, ou não importa“, não há nenhum problema de concorrência a ser resolvido. E provavelmente o teu sistema é muito simples ou  muito bem desenhado.

Figura 4. Unidades concorrentes representadas como fluxogramas [1]

Entretanto, se em algum ponto é necessário garantir, por exemplo, que as Acções F, X e Zeta sejam executadas somente depois que as Ações E, Z e Gamma atingirem determinadas condições, precisamos de alguma forma reunir (join) cada um dos estados destas tasks em logicamente uma única thread, a partir de um ponto de sincronização. Após as condições necessárias terem sido atingidas no ponto de sincronização, as threads são novamente separadas (fork), e o programa segue.

Isto significa que sempre que houver condições entre dois ou mais processos para atingir determinado objectivo, precisamos criar mecanismos para que estes se comuniquem.

2.2.1. Mecanismos de Exclusão mútua

Recursos podem ser classificados como compartilháveis ou não compartilháveis. Isto depende da natureza física ou lógica de determinado recurso [4]. Por exemplo, a menor unidade de memória do sistema não pode ser lida e escrita ao mesmo tempo por dois processos distintos. Já uma estrutura de dados que guarda um resultado para ser consumido por um processo, precisa ser protegida para não ser sobrescrita antes de consumida (ou enquanto consumida, se pensarmos em pseudo-paralelismo), porque isto causará uma falha lógica no sistema. A exclusão mútua coordena o acesso de várias unidades concorrentes a um recurso.

2.2.2. Falha por deadlock

Quando processos concorrem por recursos, podemos chegar em uma situação em que nenhum deles consegue seguir adiante. Suponhamos dois processos A e B. O processo A está bloqueado, a espera de que um recurso seja liberado para seguir adiante. O processo B por sua vez só vai liberar este recurso quando determinada condição for satisfeita. Se esta condição depender do processo A, que já está bloqueado, temos um deadlock

3. Modelagem de Tasks em UML

Em UML há 3 maneiras de modelar concorrência [1]: objetos com o estereótipo «active» em diagramas estruturais, forks e joins em diagramas de seqüência, e regiões ortogonais em diagramas de máquinas de estado. Um objeto com o estereótipo «active» em geral é uma estrutura de outros objetos. O objeto ativo tem uma thread associada, que executa a ações sequenciais que correm em um contexto (contexto este que pode ou não estar representado ou inferido do diagrama). O símbolo de um objeto ativo pode tanto dar-se como um objeto comum com o estereótipo «active», ou com as bordas esquerda e direita destacadas. Na Figura 5, uma Task é modelada com cinco objetos ativos, um recurso (database) compartilhado e protegido por um semáforo e comentários com os metaparâmetros de cada thread associada (prioridade, período e deadline – parâmetros estes que dependem escalonador utilizado). Objetos «active» que não são um conjunto de outros objetos, como itsBuiltInTestThread  ou itsControlThread correm na sua própria thread. Por fim, em alguns casos utilizamos portas nas Tasks para conectarem-se diretamente com objetos – o que geralmente indica que passaremos estes valores por cópia, e em outros utilizamos links, o que normalmente indica que estes valores serão passados por referência.

4. Padrões para exclusão mútua

Quatro padrões de design serão aqui apresentados com os seus respectivos modelos UML: Critical Region, Guarded Call, Message Queue e Rendez-vous. Todos estes padrões estão descritos em [1].

4.1. Critical Region Pattern

Esta é a forma mais primitiva de coordenar tasks: desligar os mecanismos que poderiam interromper um trecho de execução, para evitar que a task ceda lugar a outra antes de as condições necessárias serem atendidas, ou para evitar a concorrência de acesso a um recurso.

Figura 6.Generalização do Padrão Critical Section em UML [1]

4.1.1. Rationale

Este padrão é utilizado em sistemas com escalonamento preemptivo, quando múltiplas unidades concorrentes podem acessar um mesmo recurso ou interromper uma tarefa em andamento. Ao desabilitarmos a troca de tarefas em determinado trecho de execução, garantimos a atomicidade da operação.

4.1.2 Elementos

CRSharedResource: O recurso a ser protegido é o  atributo value. Qualquer trecho de código que utilize os métodos setValue e getValue precisam ser colocados em regiões críticas.

TaskWithSharedResource: Este elemento simboliza o conjunto de tasks que acessam o recurso anteriormente mencionado (por isso a multiplicidade ‘*’ na associação de dependência). As tarefas não têm conhecimento de que recurso esta a ser utilizado; ele está encapsulado dentro do objeto CRSharedResource.

4.1.3. Implementação

Usualmente o kernel provê uma API com funções como osDisableTaskSwitch()/osEnableTaskSwitch(). Caso não, alguma diretiva em C/ASM pode ser utilizada para desabilitar as interrupções diretamente em hardware – no caso da API de abstração de hardware CMSIS para processadores ARM, esta diretiva seria __disable_irq()/__enable_irq(), e estamos na verdade a desabilitar toda e qualquer interrupção do sistema. Na publicação anterior, vários trechos do código do kernel estavam em critical regions porque necessitavam ser atômicos.

4.1.4. Exemplo

Na Figura 6, um hipotético sistema para mover o braço de um robô. Uma única Task move este braço (CRRobotArmManager). As entradas do usuário são as coordenadas (x, y, z) no espaço,  passadas por referência à Task.

É importante notar a estratégia para desacoplamento entre a Task e os objetos a ela associados: as regiões críticas são implementadas dentro dos métodos da Task, e não no método moveTo, por exemplo. A definição de regiões críticas dentro do método moveTo fatalmente acoplaria uma entidade que não é da natureza do kernel, o braço do robô - que deve poder ser movimentado por outros sistemas operacionais - à uma entidade totalmente acoplada ao kernel, a Task. Se não houver justificativa, o contrário é uma má escolha de design.
Figura 7. Exemplo de Task modelada que necessita do uso de sessão crítica [1]

Abaixo, o cabeçalho do programa, e a implementação de uma operação para facilitar a compreensão da linguagem UML [1]:

Lista 1. Cabeçalho da Task CRRobotArmManager [1]

#ifndef CRRobotArmManager_H
#define CRRobotArmManager_H
struct CRDisplay;
struct RobotArm;
struct UserInput;
typedef struct CRRobotArmManager CRRobotArmManager;
struct CRRobotArmManager 
{
  struct CRDisplay* itsCRDisplay;
  struct RobotArm* itsRobotArm;
  struct UserInput* itsUserInput;
};
/* Constructors and destructors:*/
void CRRobotArmManager_Init(CRRobotArmManager* const me);
void CRRobotArmManager_Cleanup(CRRobotArmManager* const me);
/* Operations */
void CRRobotArmManager_motorZero(CRRobotArmManager* const me);
void CRRobotArmManager_moveRobotArm(CRRobotArmManager* const me);
struct CRDisplay* CRRobotArmManager_getItsCRDisplay(const
CRRobotArmManager* const me);
void CRRobotArmManager_setItsCRDisplay(CRRobotArmManager* const
me, struct CRDisplay* p_CRDisplay);
struct RobotArm* CRRobotArmManager_getItsRobotArm(const
CRRobotArmManager* const me);
void CRRobotArmManager_setItsRobotArm(CRRobotArmManager* const me,
struct RobotArm* p_RobotArm);
struct UserInput* CRRobotArmManager_getItsUserInput(const
CRRobotArmManager* const me);
void CRRobotArmManager_setItsUserInput(CRRobotArmManager* const me,
struct UserInput* p_UserInput);
CRRobotArmManager * CRRobotArmManager_Create(void);
void CRRobotArmManager_Destroy(CRRobotArmManager* const me);
#endif

Lista 2. Método com o uso de critical regions [1]

void CRRobotArmManager_moveRobotArm(CRRobotArmManager* const me) 
{
 /* local stack variable declarations */
 int x, y, z, success = 1; 
 /*noncritical region code */
 /* note that the function below has its own critical region and so cannot be
 called inside of the critical region of this function
 */
 CRRobotArmManager_motorZero(me);
 x = UserInput_getX(me->itsUserInput);
 y = UserInput_getY(me->itsUserInput);
 z = UserInput_getX(me->itsUserInput);
 /* critical region begins */
 OS_disable_task_switching();
 /* critical region code */
 success = RobotArm_moveTo(me->itsRobotArm, x, y, z);
 /* critical region ends */
 OS_enable_task_switching();
 /* more noncritical region code */
 CRDisplay_printInt(me->itsCRDisplay, "Result is ", success);
}

4.2. Guarded Call Pattern

O padrão Guarded Call, serializa o acesso a um conjunto de serviços que potencialmente causam danos se chamados simultaneamente. Neste padrão, o acesso serializado é implementado através de um semáforo que previne que outras threads invoquem este serviço enquanto ele estiver em uso.

Figura 8. Generalização do Guarded Call Pattern modelado em UML [1]

4.2.1 Rationale

Múltiplas tarefas preemptivas acessam um recurso protegido invocando os métodos deste. O escalonador de tarefas por sua vez deve colocar a task que tentou acessar um recurso ocupado em uma fila de tasks bloqueadas, desbloqueando-a assim que o recurso for liberado.

4.2.2. Elementos

GuardedResource é um recurso compartilhado que emprega um Semaphore do tipo mutex para forçar a exclusão mútua entre múltiplas PreemptiveTasks (note que existe um único semáforo agregado a um único recurso, e portanto é um semáforo para um elemento, ou seja, um mutex1). Quando uma tarefa quer utilizar este recurso, as funções relevantes deste chamarão ao semáforo para colocá-lo em lock. Caso o recurso esteja livre, ele é locked e a tarefa pode utilizá-lo, e liberá-lo ao final. Caso o recurso já esteja em locked, este sinaliza ao escalonador para colocar a tarefa atual em estado blocked até que ele seja liberado. Outras tarefas que tentam acessar o recurso enquanto ele está bloqueado também tornar-se-ão blocked. Cabe ao escalonador do sistema fazer o manejo desta fila de tarefas bloqueadas a espera do recurso; ou seja, quais critérios serão utilizados para cada tarefa na fila – pode ser a prioridade, por exemplo.2

1 a implementação de semáforos/ mutexes é um assunto que será abordado na continuidade da construção do kernelzito já apresentado.

2 um problema comum nesta implementação é quando ocorre a chamada “inversão de prioridade”

4.2.3 Implementação

A parte mais complicada é a implementação dos semáforos. Normalmente o sistema operacional provê semáforos, acessados através de uma API do tipo:

  • Semaphore* osCreateSemaphore(): cria um semáforo e retorna um ponteiro para a instância.
  • void osDestroySemaphore(Semaphore*): destrói a instância semáforo para o qual aponta.
  • void osLockSemaphore(Semaphore*): trava o dispositivo associado ao semáforo se ele estiver livre. Caso não esteja, o contexto da tarefa que o requisitou é salvo, bem como a ID do semáforo do recurso requisitado, e a tarefa é colocada em blocked.
  • void osUnlockSemaphore(Semaphore*): destrava o dispositivo associado ao semáforo, e libera a tarefa que estava a sua espera.

4.2.4 Exemplo

A Figura 9 mostra a porção de um hipotético controlador de vôo. A classe KinematicData é compartilhada por diversos clientes. Para garantir a serialização de acesso um semáforo é instanciado neste recurso.

Figura 9. Padrão Guarded Pattern aplicado a um controlador de vôo

Isto evita que o método FlightDataDisplay::ShowFlightData()seja interrompido enquanto disponibiliza os dados de vôo, pelo método Navigator::updatePosition() por exemplo. Perceba que as Tasks não estão modeladas. A utilização do semáforo está acoplada ao escalonador – o seu estado quando a thread é disparada influencia no manejo da fila de threads no qual cada método em espera será executado. Abaixo snippets de parte da implementação para facilitar o entendimento.

Lista 3. Cabeçalho da classe KinematicData

#ifndef KinematicData_H
#define KinematicData_H
#include "GuardedCallExample.h"
#include "Attitude.h"
#include "OSSemaphore.h"
#include "Position.h"
typedef struct KinematicData KinematicData;
struct KinematicData 
{
 struct Attitude attitude;
 struct Position position;
 OSSemaphore* sema; /*## mutex semaphore */
};
/* Constructors and destructors:*/
void KinematicData_Init(KinematicData* const me);
void KinematicData_Cleanup(KinematicData* const me);
/* Operations */
Attitude KinematicData_getAttitude(KinematicData* const me);
struct Position KinematicData_getPosition(KinematicData* const me);
void KinematicData_setAttitude(KinematicData* const me, Attitude a);
void KinematicData_setPosition(KinematicData* const me, Position p);
KinematicData * KinematicData_Create(void);
void KinematicData_Destroy(KinematicData* const me);
#endif

Lista 4. Implementação da classe KinematicData

#include "KinematicData.h"
void KinematicData_Init(KinematicData* const me) 
{
  Attitude_Init(&(me->attitude));
  Position_Init(&(me->position));
  me->sema = OS_create_semaphore();
}
void KinematicData_Cleanup(KinematicData* const me) 
{
  OS_destroy_semaphore(me->sema);
}
struct Position KinematicData_getPosition(KinematicData* const me) 
{
  Position p;
  /* engage the lock */
  OS_lock_semaphore(me->sema);
  p = me->position;
  /* release the lock */
  OS_release_semaphore(me->sema);
  return p;
}
void KinematicData_setAttitude(KinematicData* const me, Attitude a) 
{
/* engage the lock */
  OS_lock_semaphore(me->sema);
  me->attitude = a;
  /* release the lock */
  OS_release_semaphore(me->sema);
}
void KinematicData_setPosition(KinematicData* const me, Position p) 
{
  /* engage the lock */
  OS_lock_semaphore(me->sema);
  me->position = p;
  /* release the lock */
  OS_release_semaphore(me->sema);
}
KinematicData * KinematicData_Create(void) 
{
  KinematicData* me = (KinematicData *)
  malloc(sizeof(KinematicData));
  if(me!=NULL) 
  {
   KinematicData_Init(me);
  }
  return me;
}
void KinematicData_Destroy(KinematicData* const me) 
{
  if(me!=NULL) 
  {
   KinematicData_Cleanup(me);
  }
  free(me);
}
Attitude KinematicData_getAttitude(KinematicData* const me) 
{
  Attitude a;
  /* engage the lock */
  OS_lock_semaphore(me->sema);
  a = me->attitude;
  /* release the lock */
  OS_release_semaphore(me->sema);
  return a;
}

Fim da primeira parte

Referências:
[1] Design Patterns for Embedded Systems in C (Douglass Powell, 2009)
[2] Embedded Systems: Real-Time Operating Systems for Arm Cortex-M MCUs (Jonathan Valvanno, 2012)
[3] Modern Operating Systems (Andrew Taneunbaum, Herbert Boss, 2014)
[4] Fundamentals of Operating Systems (A. M. Lister, 1984)

Separando espaços de supervisor e usuário no ARM Cortex-M3

1. Introdução

Os processadores ARM Cortex-M estão integrados a SoCs para domínios diversos, principalmente em muito daquilo que chamamos de dispositivos smart. Esta publicação é uma continuação da anterior, em que demonstrei a implementação de um mecanismo preemptivo mínimo para um ARM Cortex-M3, aproveitando-se dos recursos de hardware especiais para a troca de contexto.

Alguns recursos importantes desta arquitetura serão agora demonstrados como a separação de threads de usuário e kernel – com 2 stack pointers: MSP e PSP e a utilização de Supervisor Calls para implementar chamadas ao sistema.

Apesar de alguns conceitos sobre sistemas operacionais serem abordados porque são inerentes ao assunto, o objetivo é a exploração do ARM Cortex-M3, um processador relativamente barato e de larga aplicabilidade, e como aproveitá-lo para desenvolver sistemas mais robustos.

2. Registradores especiais

São 3 os registradores especiais no ARM Cortex-M3. Você pode consultar a documentação da ARM para entender o papel de cada um deles no processador. O mais importante nesta publicação é o CONTROL.

  • Program Status Registers (APSR, IPSR, e EPSR)
  • Interrupt Mask Registers (PRIMASK, FAULTMASK e BASEPRI)
  • Control (CONTROL).

Registradores especiais somente podem ser acessado através das instruções privilegiadas MRS (ARM Read Special Register) e MSR (ARM Set Special Register):

//Carrega em R0 o atual valor contido no registrador especial
MRS R0, SPECIAL 
//Carrega no registrador especial o valor contido em R0)
MSR SPECIAL, R0 

O registrador CONTROL tem somente 2 bits configuráveis. Quando um serviço de excepção (e.g., SysTick_Handler) estiver a ser executado, o processador estará em modo privilegiado e utilizando o main stack pointer (MSP), e CONTROL[1] = 0, CONTROL[0] = 0. Em outras rotinas que não sejam handlers, este registrador pode assumir diferentes valores a depender da implementação do software (Tabela 1).

No pequeno kernel mostrado anteriormente, as tasks da aplicação (Task1, Task2 e Task3) também eram executadas em modo privilegiado e utilizando o stack pointer principal (MSP). Assim, um programa da aplicação poderia alterar os registradores especiais do core se quisesse.

3. Sistema com 2 stack pointers e diferentes privilégios

Na última publicação ressaltei o fato de o registrador R13 não fazer parte do stackframe, pois é ele justamente que guarda o endereço do stack pointer. O R13 é um registrador do tipo “banked” (não conheço uma boa tradução para português), significando que ele é fisicamente replicado, e assume um valor ou outro a depender do estado do core.

CTRL[1] (0=MSP/1=PSP)CTRL[0] (0=Priv, 1=Non priv)Estado
00Privileged handler* / Base mode
01Unprivileged
10Privileged thread
11User thread
Tabela 1. Estados possíveis do registrador CONTROL
*em rotinas que atendem às exceções este modo estará sempre ativo mesmo que o CTRL[0] = 1.

Com dois stack pointers, um para aplicação e outro para o kernel, significa que uma thread de usuário não poderá facilmente corromper o stack pointer do kernel por um erro de programação na aplicação. Os privilégios por sua vez evitam que a aplicação sobrescreva registradores especiais. De acordo com os manuais da ARM, um sistema operacional robusto tipicamente tem as seguintes características:

  • serviços de interrupção utilizam o MSP (por default da arquitetura)
  • rotinas do kernel são ativadas através do SysTick em intervalos regulares para executar, em modo privilegiado, o escalonamento das tarefas e gerenciamento do sistema
  • aplicações de usuário são executadas como threads, usam o PSP em modo não-privilegiado
  • a memória para as stacks do kernel e handlers são apontadas pelo MSP, sendo que os dados stack só podem ser acessados em modo privilegiado*
  • a memória para a stack das aplicações é apontada pelo PSP

*por enquanto não vamos isolar os espaços de memória

4. Chamadas ao sistema (System Calls)

Em uma perspectiva simples, uma chamada de sistema é um método no qual um software requisita um serviço/mecanismo do kernel ou SO sobre o qual está rodando: gerenciamento de processos (escalonamento, mecanismos de IPC), acesso a algum recurso de hardware, sistema de arquivos, entre outros, a depender da arquitetura do sistema operacional.

Se pretendemos separar nosso sistema em níveis de privilégio é inevitável que o nível da aplicação precise fazer chamadas ao kernel para ter acesso a, por exemplo, serviços de hardware ou o que mais julgarmos crítico para a segurança e estabilidade do sistema.

Uma maneira comum de implementar system calls no ARM Cortex-M3 (e em outros cores baseados em ARMv7) é a utilização da interrupção por software chamada Supervisor Call (SVC). O SVC funciona como um ponto de entrada para um serviço que necessita de privilégios para ser executado. O único parâmetro de entrada de um SVC é o seu número (instrução ASM: SVC #N), ao qual associamos a uma chamada de função (callback). Ao contrário da outra excepção disparada via software disponível, que é o PendSV (Pendable Supervisor Call), o SVC pode ser disparado em modo usuário. Apesar de serem destinadas a diferentes usos – o PendSV é tipicamente usado como forma de “agendar” tarefas do kernel menos críticas e não perder ticks do sistema, é possível configurar o core para que usuários também possam disparar o PendSV.

Figura 2. Diagrama de blocos de uma possível arquitetura de sistema operacional no M3. Supervisor Calls funcionam como ponto de entrada para serviços privilegiados. [2]

5. Design

5.1 Utilização de dois stack pointers

Para a utilizar os dois stack pointers disponíveis (MSP e PSP) é fundamental entender 2 coisas:

  • A manipulação do registrador de controle: só é possível escrever ou ler o registrador de controle em modo handler (na rotina que atende à uma exceção) ou em threads privilegiadas.
  • O mecanismo de exceções: quando uma interrupção ocorre, o processador guarda na stack o conteúdo dos registradores R0-R3, LR, PC e xPSR, como explicado na publicação anterior. O valor do LR quando entramos em uma exceção indica o modo que o processador estava a rodar, quando a thread foi interrompida. Podemos manipular este valor de LR juntamente com a manipulação dos stack pointer para controlar o fluxo do programa.
LRBX LR
0xFFFFFFF9Volta para modo “base”, MSP privilegiado. (CONTROL=0b00)
0xFFFFFFFDVolta para user mode (PSP, com o nível de privilégio da entrada) (Control = 0b1x)
0xFFFFFFF1Volta para a interrupção anterior, no caso de uma interrupção de maior prioridade ocorrer durante uma de menor prioridade.
Tabela 2. Valores para retorno de exceção

5.1.1. Um kernel stack para cada user stack

Cada stack dedicada ao usuário terá uma stack de kernel correspondente (one kernel stack per thread). Assim, cada Task (thread principal) terá stacks de kernel e usuário associadas. Uma outra abordagem seria uma stack somente de kernel no sistema (one kernel stack per processor). A vantagem de utilizar a primeira abordagem é que além das threads do kernel poderem ser preemptivas, do ponto de vista de quem implementa o sistema, os programas que rodam no kernel seguem o mesmo padrão de desenvolvimento dos programas de aplicação. A vantagem da segunda abordagem é menor overhead de memória e menor latência nas trocas de contexto.

Figura 3. Cada user stack tem uma kernel stack associada

5.2 Mecanismos de entrada e saída do kernel

Na publicação anterior a interrupção feita pelo SysTick manejava a troca de contexto, i.e., interrompia a thread em execução, salvava seu stackframe, buscava a próxima thread apontada pelo campo next na estrutura TCB (thread control block) e a resumia.

Com a separação dos espaços de usuário e supervisor, teremos dois mecanismos para entrada e saída do kernel: as system calls, explicitamente chamadas em código, e a interrupção por SysTick que implementa a lógica de escalonamento (scheduling). Outro ponto a destacar, é que apesar de continuar utilizando um esquema round-robin simples, em que cada tarefa tem o mesmo tempo de execução, as threads do kernel também funcionarão de forma cooperativa com a a thread do usuário que a evocou, isto é: quando não houver mais nada a ser feito, o kernel pode explicitamente retornar. Se a thread do kernel demorar mais que o tempo entre um tick e outro, será interrompida e reagendada. As tarefas do usuário também poderiam utilizar-se de mecanismo similar, entretanto, por simplicidade para exposição, optei por deixar as tarefas de usuário somente em esquema round-robin fixo.

5.2.1. Escalonador (task scheduler)

O fluxograma do escalonador preemptivo a ser implementado está na Figura 4. O start-up do kernel e aplicação do usuário é também mostrado para maior clareza. O kernel é inicializado e voluntariamente inicia a primeira task de usuário. A cada interrupção por SysTick, a thread tem seu estado salvo e a próxima task agendada é resumida consoante ao estado em que foi interrompida: kernel ou user mode.

Figura 4. Fluxograma do escalonador

5.2.2 Chamadas ao sistema (System Calls)

As chamadas ao sistema ocorrem quando o usuário requisita acesso a um serviço privilegiado. Além disso, também utilizo o mesmo mecanismo para que tarefas privilegiadas do kernel retornem cooperativamente à tarefa do usuário.

Perceba que optei por não executar o as threads de kernel dentro do próprio handler, o que seria mais intuitivo, além de usual. As razões para isto são porque quis aproveitar o próprio mecanismo de interrupção do processador, que no seu retorno faz o POP dos registradores RO-R3, LR, PC e xPSR, e também para evitar o aninhamento de interrupções durante a preempção de tarefas do kernel. Caso eu tivesse optado por utilizar somente uma kernel stack para todas as threads, a implementação dentro do próprio handler julgo que seria melhor.

Figura 5. Fluxograma das system calls

6. Implementação

Abaixo explico os códigos criados para implementar as provas de conceito das funcionalidades anteriormente descritas. A maior parte do kernel propriamente dito é escrito em assembly, exceto para uma porção do handler de supervisor calls que é escrita em C com algum inline assembly. Na minha opinião, mais trabalhoso e suscetível a erros que escrever em assembly é embutir assembly no código C. A toolchain utilizada é a GNU ARM.

6.1. Stacks

Não há nada em especial aqui, exceto que agora além da stack de usuário, declaramos outro array de inteiros para a stack do kernel. Estes serão associados no Thread Control Block.

int32_t p_stacks[NTHREADS][STACK_SIZE]; // stack de usuário
int32_t k_stacks[NTHREADS][STACK_SIZE]; // stack do kernel

6.2. Task Scheduler

A principal diferença deste para o escalonador mostrado na última publicação é que agora manejaremos 2 stack pointers distintos: o MSP e o PSP. Assim, quando entramos em um handler de exceção, a porção do stackframe salvo automaticamente depende do stack pointer utilizado quando a exceção foi disparada. Entretanto na rotina de exceção o stack pointer ativo é sempre o MSP. Desta forma, para podermos manejar um stack pointer quando estamos a operar com outro, não poderemos utilizar as instruções PUSH e POP porque estas têm como endereço base o stack pointer ativo. Teremos de substituí-las pelas instruções LDMIA (load multiple and increment after, i.e, após o primeiro load incrementa-se o endereço base) para o POP, e STMDB (store multiple decrement before, antes do primeiro store decrementa-se o endereço base) para o PUSH, com o sinal de writeback “!” no endereço base [1].

// Exemplo de POP 
MRS R12, PSP // lê o valor do process stack pointer em R12
LDMIA R12!, {R4-R11} // R12 contém o endereço base (PSP)
/* o endereço contido em R12 agora armazena o valor de R4, [R12] + 0x4  
 contém o valor de R5, e assim por diante até que [R12] + 0x20 contém o 
 valor de R11.
 o valor inicial de R12 também é incrementado em 32 bytes 
*/
MSR PSP, R12 // PSP é atualizado para o novo valor de R12

// Exemplo de PUSH
MSR R12, MSP 
STMDB R12!, {R4-R11} 
/* [R12] - 0x20 contém R4, [R12] - 0x16 contém R5, ..., [R12] contém R4 
 o valor inicial de R12 é decrementado em 32 bytes */
MSR MSP, R12 // MSP é atualizado para o novo valor de R12 

Outra diferença é que agora a estrutura TCB precisa conter um ponteiro para cada um dos stack pointers da thread que controla, e também uma flag indicando se a tarefa a ser resumida estava utilizando o MSP ou o PSP quando foi interrompida.

// thread control block
struct tcb 
{
  int32_t*	psp; //psp salvo da ultima user thread interrompida
  int32_t*	ksp; //ksp salvo da ultima kernel thread interrompida	
  struct tcb	*next; //aponta para o proximo tcb
  int32_t	pid; //id da task (é o "i" do kSetInitStack(i))
  int32_t	kernel_flag; // 0=kernel, 1=user	
};
typedef struct tcb tcb_t;
tcb_t tcb[NTHREADS]; //array de tcbs
tcb_t* RunPtr; 

Abaixo a rotina que escrevi para implementação. O código foi escrito de forma a ficar claro em sua intenção, sem tentar economizar instruções. Perceba que na linha 5 o valor de LR assumido na entrada da excepção só é comparado com 0xFFFFFFFD, caso falso assume-se que ele é 0xFFFFFFFF9, isto porque garanto que não haverá interrupções aninhadas (o SysTick nunca interrompe um SVC, por exemplo), assim o LR nunca deve assumir 0xFFFFFFF1. Para propósitos que não uma prova de conceito, o teste deveria ser considerado.

.global SysTick_Handler
.type SysTick_Handler, %function
SysTick_Handler:			
CPSID	I //atomica inicio
CMP	LR, #0xFFFFFFFD //verifica se retornou de uma user thread
BEQ	SaveUserCtxt	//se sim, branch para save user context
B	SaveKernelCtxt  //se nao

SaveKernelCtxt:
MRS	R12, MSP 
STMDB	R12!, {R4-R11}  //push R4-R11
MSR	MSP, R12
LDR	R0,=RunPtr      //RunPtr aponta para a tcb atual
LDR	R1, [R0]
LDR	R2, [R1,#4]
STR	R12, [R2]  //salva stack pointer
B	Schedule

SaveUserCtxt:
MRS	R12, PSP
STMB	R12!, {R4-R11}
MSR	PSP, R12
LDR	R0,=RunPtr
LDR	R1, [R0]
STR	R12, [R1]		
B	Schedule

Schedule:
LDR	R1, =RunPtr //R1 <- RunPtr
LDR	R2, [R1]	
LDR	R2, [R2,#8] //R2 <- RunPtr.next
STR	R2, [R1]    //atualiza valor de RunPtr
LDR	R0, =RunPtr
LDR	R1, [R0]
LDR	R2, [R1,#16]
CMP	R2, #1	     //verifica se kernel_flag=1
BEQ	ResumeUser   //sim, resume user thread
B	ResumeKernel //nao, resume kernel thread

ResumeUser:
LDR	R1, =RunPtr  //R1 <- RunPtr
LDR	R2, [R1]
LDR	R2, [R2]
LDMIA	R2!, {R4-R11} //Resgata sw stackframe 
MSR	PSP, R2		
MOV	LR, #0xFFFFFFFD	//LR=return to user thread
CPSIE	I		//atomica fim
BX	LR 

ResumeKernel:
LDR	R1, =RunPtr   //R1 <- RunPtr atualizado
LDR	R2, [R1]
LDR	R2, [R2, #4]
MSR	MSP, R2
LDMIA	R2!, {R4-R11} //Resgata sw stackframe 
MSR	MSP, R2
MOV	LR, #0xFFFFFFF9	 //LR=return to kernel thread
CPSIE	I		 //atomic fim
BX	LR 

6.3 System Calls

A implementação dos system calls utiliza o SVC Handler. Como dito, o único parâmetro de entrada do SVC é o número que associamos a um callback. Mas então como passamos os argumentos para o callback? Eles precisam ser buscados na stack. O padrão AAPCS (ARM Application Procedure Call Standard), que é seguido pelos compiladores, diz que quando uma função (caller) chama outra função (callee), o callee espera que seus argumentos estejam em R0-R3. Da mesma forma, o caller espera que o retorno do callee esteja em R0. R4-R11 precisam ser preservados entre uma chamada e outra. R12 é o scratch register e pode ser usado livremente.

Não à toa, quando uma exceção ocorre o core salva (PUSH) na stack os registradores R0-R3, LR, PC e xPSR da função que foi interrompida, e no retorno os lança (POP) novamente nos registradores do core. Se trocarmos de contexto, isto é, após a interrupção não retornarmos ao mesmo ponto do programa que foi interrompido, precisamos explicitamente salvar o restante da stackframe para que a thread seja resumida de forma íntegra. É fundamental seguir o AAPCS se quisermos evocar funções escritas em assembly em código C e vice-versa.

Para executar chamadas ao sistema defini uma função macro em C que recebe o código do SVC e os argumentos para a callback (a sintaxe de assembly inline depende do compilador utilizado).

(Há uma razão de eu ter criado uma macro e não uma função comum: tem a ver com o ponto de retorno à user thread e o fato de os callbacks do kernel não serem executados dentro da exceção, o que exige a troca de contexto. Se criasse uma função comum para o system call, o stack pointer do usuário seria salvo dentro da chamada, e ao retornar do kernel, o SVC seria novamente executado.)

#define SysCall(svc_number, args) {					   				      
                                                                        \
	__ASM volatile ("MOV R0, %0 "     :: "r"            (args) );     \
	__ASM volatile ("svc %[immediate]"::[immediate] "I" (svc_number) : );   \
}

O valor de args é armazenado em R0. A chamada do SVC é feita com o imediato “svc_number”. Quando o SVC é disparado R0-R3 serão automaticamente salvos na stack. O código foi escrito da seguinte forma, sem economizar instruções, para clareza:

.global SVC_Handler
.type	SVC_Handler, %function
 SVC_Handler:
 MRS R12, PSP		 //salva psp
 CMP LR, #0xFFFFFFFD
 BEQ KernelEntry
 B   KernelExit

//salva contexto do usuário
KernelEntry: 
MRS	R3, PSP
STMDB	R3!, {R4-R11}
MSR	PSP, R3
LDR	R1,=RunPtr
LDR	R2, [R1]
STR	R3, [R2]	
LDR	R3, =#0  
STR	R3, [R1, #16] //kernel flag = 0
MOV	R0, R12   //psp da chamada no r0 do CORE pra recuperar svc number
B svchandler_main //branch para rotina em C 
KernelExit:
//recarrega frame do usuário
LDR	R0, =RunPtr
LDR	R1, [R0]
LDR	R2, [R1]
LDMIA	R2!, {R4-R11}
MOV	LR, #0xFFFFFFFD
MSR	PSP, R2
LDR	R12, =#1 //kernel flag = 1
STR	R12, [R1, #16]
BX	LR 

O restante da rotina para entrada no kernel é escrito em C [2, 3]. Perceba que na rotina escrita em assembly um branch simples ocorre (linha 20) e portanto ainda não retornamos do handler de exceção.

#define SysCall_GPIO_Toggle  1 //codigo svc para gpio toggle
#define SysCall_Uart_PrintLn 2 //codigo svc para uart print line

void svchandler_main(uint32_t * svc_args)
{		
    uint32_t svc_number;
    uint32_t svc_arg0;
    uint32_t svc_arg1;
    svc_number = ((char *) svc_args[6])[-2]; // recupera o imediato 
    svc_arg0 = svc_args[0];
    svc_arg1 = svc_args[1]; 
 
 switch(svc_number)
 {
 case SysCall_GPIO_Toggle: 
	k_stacks[RunPtr->pid][STACK_SIZE-2] = (int32_t)SysCallGPIO_Toggle_; //PC
	k_stacks[RunPtr->pid][STACK_SIZE-8] = (int32_t)svc_arg0; //R0
	k_stacks[RunPtr->pid][STACK_SIZE-1] = (1 << 24); // T=1 (xPSR)
	__ASM volatile ("MSR MSP, %0" : : "r" (RunPtr->ksp) : );
	__ASM volatile ("POP {R4-R11}");
	__ASM volatile ("MOV LR, #0xFFFFFFF9");
	__ASM volatile ("BX LR"); //retorna da excecao
	break;
 case SysCall_Uart_PrintLn: 
	k_stacks[RunPtr->pid][STACK_SIZE-2] = (int32_t)SysCallUART_PrintLn_; 
	k_stacks[RunPtr->pid][STACK_SIZE-8] = (int32_t)svc_arg0;
	k_stacks[RunPtr->pid][STACK_SIZE-1] = (1 << 24); // T=1
	__ASM volatile ("MSR MSP, %0" : : "r" (RunPtr->ksp) : );
	__ASM volatile ("POP {R4-R11}");
	__ASM volatile ("MOV LR, #0xFFFFFFF9");
	__ASM volatile ("BX LR"); //retorna da excecao
	break;
 default:
	__ASM volatile("B SysCall_Dummy");
	break;
 break;
 }
}

O svc_number, por sua vez, é recuperado ao andarmos dois bytes (por isso o cast para char) descrescentes a partir endereço do PC que está 6 posições acima de R0 na stack [1, 2, 3]. Note que foi preciso assinalar a R0 o valor contido em PSP logo após a entrada na interrupção, antes de salvarmos o restante da stack (linhas 4 e 19 do código assembly).

Após recuperar o número do SVC e os argumentos, inicializamos a stack do kernel, MSP é sobrescrito com o valor armazenado no TCB, mudamos o valor de LR para que a exceção ao retornar vá para o modo base, pois não iremos executar o callback dentro do handler. Quando a instrução BX LR é executada o restante do stackframe é automaticamente ativado nos registradores do core.

Um callback tem a seguinte cara:

static void SysCall_CallBack_(void* args)
{
	BSP_Function((int32_t) args); //funcao do BSB com unico argumento int32
	exitKernel_(); // //qualquer chamada ao svc aqui ira sair do kernel (Figura 5)
}

6.4. Start-up

O start-up é um ponto crítico. O sistema inicializa em modo base. As stacks são montadas. A primeira tarefa a ser executada pelo kernel após a inicialização do sistema é configurar o SysTick, mudar para o modo de usuário e disparar a primeira thread de usuário.

//inicializacao da primeira stack
tcb_t* RunPtrStart;
RunPtrStart = tcb[0];
void kFirstThreadInit(void)
{
	kSetInitStack(0); /* esta função segue o mesmo padrão da última postagem */
	k_stacks[0][STACK_SIZE-2] = (int32_t) UsrAppStart; // LR = UsrAppStart
}
// RunPtr e o restante dos tcbs é configurado da mesma forma da última publicacao 

As rotinas em assembly para o startup são as seguintes:

.equ SYSTICK_CTRL, 0xE000E010 
.equ TIME_SLICE,	999

.global kStart  // esta é a função principal de init 
.type kStart, %function
kStart:
LDR	R0, =RunPtrStart
LDR	R1, [R0]
LDR	R2, [R1,#4]
MSR	MSP, R2	  // MSP <- RunPtr.ksp
POP	{R4-R11}  //carrega stackframe 0 na callstack
POP	{R0-R3}
POP	{R12}
ADD	SP, SP, #4
POP	{LR}	 //LR <- PC = UsrAppStart
ADD	SP, SP, #4
BX	LR // vai para UsrAppStart

//esta função prepara a stack para disparar a primeira user thread
.global UsrAppStart 
.type	UsrAppStart, %function
UsrAppStart:				
LDR	R1, =RunPtr //R1 <- RunPtr
LDR	R2, [R1]		
LDR	R2, [R2]
MSR	PSP, R2
BL	SysTickConf //configura systick
MOV	R0, #0x3
MSR	CONTROL, R0 //habilita thread unprivileged mode
ISB		    /* inst sect barrier: garante que CONTROL 
                     estara atualizado nas proximas instrucoes*/
POP	{R4-R11}   //carrega stackframe 0 na callstack
POP	{R0-R3}
POP	{R12}
ADD	SP, SP, #4
POP	{LR}	   //LR <- PC
ADD	SP, SP, #4
BX LR
	
SysTickConf:
LDR	R0, =SYSTICK_CTRL 
MOV	R1, #0
STR	R1, [R0]  // zera contador
LDR	R1, =TIME_SLICE  
STR	R1, [R0,#4] // RELOAD <- TIME_SLICE
STR	R1, [R0,#8] // CURR_VALUE <- TIME_SLICE (mas tanto faz)
MOV	R1, #0x7   // 0b111:
		    // 1: Clock source = core clock 
		    // 1: Habilita irq
		    // 1: Habilita contador
STR	R1, [R0]		
BX	LR	    //volta pro caller

7. Teste

Para fazer um pequeno teste, vamos escrever na tela do PC através da UART. O callback para chamada de sistema foi escrito da seguinte forma:

static void SysCallUART_PrintLn_(const char* args)
{
	__disable_irq();
	uart_write_line(UART, args);		
	while (uart_get_status(UART) != UART_SR_TXRDY); //espera fim da transmissão
	__enable_irq();
	exitKernel_();
}

É preciso tomar cuidado na hora de utilizar multithreading concorrendo para utilizar serviços de hardware, já que ainda não inserimos nenhum mecanismo de semáforo. Entretanto, fiz a operação atômica e não será interrompida pelo SysTick. O programa principal é o seguinte:

#include <commondefs.h> //board support package, libs padrão, etc.
#include <kernel.h>  
#include <tasks.h>

int main(void)
{
  kHardwareInit(); //configura clock, interrupcoes, uart, entre outros
  kAddThreads(Task1, (void*)"Task1\n\r", Task2, (void*)"Task2\n\r", Task3, (void*)"Task3\n\r");
  RunPtrStart = &tcbs[0]; 
  RunPtr = &tcbs[1];
  uart_write_line(UART, "Inicializando kernel...\n\r");
  delay_ms(500); //delay para dar tempo de tirar o printscreen da tela 😛
  kStart();	
  while(1);
}

As tasks (threads principais) têm a seguinte cara:

void Task1(void* args)
{
	const char* string = (char*)args;
	while(1)
	{
		SysCall(SysCall_Uart_PrintLn, string);
	}
}

Na figura abaixo o sisteminha em execução:

8. Conclusões

A utilização de dois stack pointers, um para aplicação e outro para o kernel isola estes espaços não permitindo que a aplicação corrompa a stack do kernel. Os privilégios por sua vez evitam que a aplicação sobrescreva registradores especiais. Adicionar mais um stack pointer ao sistema exigiu mudanças na rotina do escalonamento porque agora manipulamos duas stacks no domínio de 2 stack pointers distintos, em que ambos estão sujeitos à preempção. Além disso, também foi adicionado um mecanismo cooperativo para que as tarefas do kernel liberem o processador para o usuário.

O mecanismo de system calls é utilizado como ponto de entrada a serviços de hardware, ou ao que mais julgarmos crítico para a segurança e estabilidade do sistema. Isto fará ainda mais sentido ao separarmos não só as stacks em níveis de privilégio mas também as regiões da memória com a MPU.

Para as próximas publicações ainda iremos: 1) incluir mecanismos de semáforos e IPCs, 2) configurar a MPU e 3) adicionar níveis de prioridades às tarefas que até então rodam em um esquema round-robin fixo.

9. Referências

[1] http://infocenter.arm.com/help/topic/com.arm.doc.ddi0337e/DDI0337E_cortex_m3_r1p1_trm.pdf

[2] The definitive Guide to ARM Cortex M3, Joseph Yiu

[3] https://developer.arm.com/docs/dui0471/j/handling-processor-exceptions/svc-handlers-in-c-and-assembly-language