Estudio del uso de la sobrecarga de operadores para aritmética de punto fijo en C++ 
La aritmética de punto fijo es un mecanismo muy útil para la implementación de funciones matemáticas en procesadores sin unidad de coma flotante como microcontroladores y procesadores pequeños de 8 o 16 bits. A lo largo de este post se plantea el uso de la sobrecarga de operadores de C++ para facilitar las tareas de programación y mejorar la legibilidad del código cuando se usan tipos de punto fijo.

Introducción

La aritmética de punto fijo permite realizar operaciones con números fraccionarios mediante tipos enteros y operaciones enteras. En anteriores posts de este blog se ha hablado de forma extensa acerca de este tema, por lo que se remite a ellos a la persona interesada. A lo largo de este post usaré siempre valores de punto fijo Q16.16 (32 bits con 16 bits para la parte entera y 16 bits para la parte fraccionaria).

Implementación tradicional mediante macros

Tradicionalmente siempre he implementado la aritmética de punto fijo con un fichero de cabecera en el que defino "fixedpoint_t" como un "int32_t" y unas macros especiales para las operaciones de conversión de entero a punto fijo, de multiplicación y de división (las más "complejas"):

typedef int32_t fixedpoint_ct;

#define  FP_MUL(x, y)  ((int32_t) ((((int64_t) (x)) * ((int64_t) (y))) >> 16))
#define  FP_DIV(x, y)  ((int32_t) ((((int64_t) (x)) << 16) / ((int64_t) (y))))
#define  TO_FP(x)      (((int32_t ) (x)) << 16)

Como se puede apreciar, se trata de una implementación extremadamente sencilla y si lo que queremos es escribir una función que calcule:
$$\left({a \times b}\right) + \left({a \over b}\right)$$
Introduciríamos el siguiente código:

fixedpoint_ct fWithMacros(fixedpoint_ct a, fixedpoint_ct b) {
    return FP_MUL(a, b) + FP_DIV(a, b);
}

Y para los valores $a = 4$ y $b = 3$ la invocaríamos de la siguiente forma:

fixedpoint_ct v = fWithMacros(TO_FP(4), TO_FP(3));

Se trata de una implementación perfectamente válida aunque adolece de falta de claridad en el código: hay que leer con cuidado las operaciones aritméticas para no confundirse. Por otro lado es una implementación que tiene la ventaja de que en todo momento está claro que no estamos trabajando con un tipo "trivial".

Implementación basada en sobrecarga de operadores

Buscando un código más legible que el anterior, lo lógico es recurrir a la sobrecarga de operadores de C++. Definimos una clase "fixedpoint_t" en la que metemos un entero de 32 bits y definimos las cuatro operaciones básicas como "operator" dentro de la propia clase:

class fixedpoint_t {
    public:
        int32_t v;
        fixedpoint_t(int32_t x = 0) : v(x << 16) { };
        inline fixedpoint_t &operator = (const int32_t &x) { this->v = x << 16; return *this; };
        inline fixedpoint_t operator + (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = this->v + x.v; return ret; };
        inline fixedpoint_t operator - (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = this->v - x.v; return ret; };
        inline fixedpoint_t operator * (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = (((int64_t) this->v) * ((int64_t) x.v)) >> 16; return ret; };
        inline fixedpoint_t operator / (const fixedpoint_t &x) { fixedpoint_t ret; ret.v = (((int64_t) this->v) << 16) / ((int64_t) x.v); return ret; };
};

Esta implementación nos permite ahora escribir la misma función de antes de una forma más legible:

fixedpoint_t fWithOperators(fixedpoint_t a, fixedpoint_t b) {
    return (a * b) + (a / b);
}

Y, de la misma manera, también nos permite invocarla de forma más legible:

fixedpoint_t v = fWithOperators(4, 3);

Sin embargo se podría pensar que una implementación así generaría mucho más código que la implementación basada en macros. Hagamos unas pruebas.

Comparativa

Si compilamos con gcc el código de ambas funciones sin opciones de optimización:

g++ -std=c++11 -o fp fp.cc

la diferencia es abismal:

_Z11fWithMacrosii:
    push   %rbp
    mov    %rsp,%rbp
    push   %rbx
    mov    %edi,-0xc(%rbp)
    mov    %esi,-0x10(%rbp)
    mov    -0xc(%rbp),%eax
    movslq %eax,%rdx
    mov    -0x10(%rbp),%eax
    cltq   
    imul   %rdx,%rax
    sar    $0x10,%rax
    mov    %eax,%ecx
    mov    -0xc(%rbp),%eax
    cltq   
    shl    $0x10,%rax
    mov    -0x10(%rbp),%edx
    movslq %edx,%rbx
    cqto   
    idiv   %rbx
    add    %ecx,%eax
    pop    %rbx
    pop    %rbp
    retq   

_Z14fWithOperators12fixedpoint_tS_:
    push   %rbp
    mov    %rsp,%rbp
    sub    $0x40,%rsp
    mov    %edi,-0x30(%rbp)
    mov    %esi,-0x40(%rbp)
    lea    -0x40(%rbp),%rdx
    lea    -0x30(%rbp),%rax
    mov    %rdx,%rsi
    mov    %rax,%rdi
    callq  4009cc <_ZN12fixedpoint_tdvERKS_>
    mov    %eax,-0x20(%rbp)
    lea    -0x40(%rbp),%rdx
    lea    -0x30(%rbp),%rax
    mov    %rdx,%rsi
    mov    %rax,%rdi
    callq  40098a <_ZN12fixedpoint_tmlERKS_>
    mov    %eax,-0x10(%rbp)
    lea    -0x20(%rbp),%rdx
    lea    -0x10(%rbp),%rax
    mov    %rdx,%rsi
    mov    %rax,%rdi
    callq  400952 <_ZN12fixedpoint_tplERKS_>
    leaveq 
    retq   

El compilador ha hecho caso omiso del "inline" de las funciones miembro de la clase "fixedpoint_t" y las ha implementado como funciones aparte en ensamblador. En este caso la implementación usando macros es más eficiente. Activemos ahora el primer nivel de optimización "-O1":

g++ -std=c++11 -O1 -o fp fp.cc

Voilà, ahora apenas notamos la diferencia en el código generado:

_Z11fWithMacrosii:
    movslq %edi,%rax
    movslq %esi,%rsi
    mov    %rax,%rcx
    imul   %rsi,%rcx
    sar    $0x10,%rcx
    shl    $0x10,%rax
    cqto   
    idiv   %rsi
    add    %ecx,%eax
    retq   

_Z14fWithOperators12fixedpoint_tS_:
    movslq %edi,%rdi
    movslq %esi,%rsi
    mov    %rdi,%rax
    shl    $0x10,%rax
    cqto   
    idiv   %rsi
    imul   %rdi,%rsi
    sar    $0x10,%rsi
    add    %esi,%eax
    retq   

La implementación utilizando la clase "fixedpoint_t" con los operadores sobrecargados genera un código igual de eficiente que la implementación basada en macros.

Como conclusión podemos sacar que no es necesario sacrificar legibilidad en aras de la velocidad de ejecución, siempre y cuando usemos correctamente los elementos del lenguaje y compilemos usando las opciones de optimización adecuadas.

El código fuente puede descargarse de la sección soft.

[ añadir comentario ] ( 1306 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 3621 )
Implementación no bloqueante de un driver LCD 
A la hora de controlador un display LCD mediante el conocido adaptador I2C la gran mayoría de ejemplos disponibles por ahí implementan los estados de espera necesarios mediante retardos explícitos ("delays"). Dichas implementaciones están bien como prueba de concepto, pero no son deseables en entornos multitarea donde no podemos desperdiciar ciclos sólo esperando. En entornos reales se precisa de implementaciones no bloqueantes que hagan uso de timers e interrupciones.

El circuito

La interfaz de un display LCD estándar de caracteres es una interfaz paralelo de 8 bits, con 3 líneas de control adicionales (RS, EN y RW). Del bus paralelo de 8 bits pueden usarse sólo los 4 bits más significativos enviando de forma adecuada los comandos. Los circuitos de conversión a I2C que se venden habitualmente por AliExpress, Ebay y demás están basados en el conversor I2C/paralelo de 8 bits PCF8574 de Texas Instruments: del bus paralelo de dicho conversor se sacan los 4 bits más significativos para el bus paralelo del LCD y las tres señales de control para RS, EN y RW.



La configuración habitual en este tipo de módulos es esta:

PCF8574bit 7bit 6bit 5bit 4bit 3bit 2bit 1bit 0
LCDD7D6D5D4BLENRWRS

En la tabla se puede apreciar una cuarta señal de control etiquetada como BL (backlight) que controla el encendido del led de la luz trasera. Dicho led no forma parte de la circuitería estándar del display y ha sido introducido en versiones más recientes.

El problema

Los displays baratos de caracteres LCD que se encuentran en el mercado están basados en en un chip de Hitachi que no se caracteriza precisamente por su velocidad (probablemente debe ser uno de los chips más rentabilizados de toda la historia de Hitachi) y normalmente cada acceso debe estar seguido por una espera de uno a varios microsegundos, dependiendo del acceso realizado. A continuación puede verse la tabla de comandos de referencia del display, nótese la columna de la derecha ("Execution Time"):


(imagen extraida de https://learningmsp430.wordpress.com/2013/11/13/16x2-lcd-interfacing-in-8bit-mode/)

Cuando uno realiza una búsqueda en internet sobre códigos de ejemplo para control de displays LCD, la gran mayoría de los mismos (no digo todos porque considero que no los he visto todos, pero al menos todos los que yo he visto), implementan las esperas mediante retardos utilizando funciones "delay" o similares. Esta forma de implementación, aunque resulta simple, supone un desperdicio de ciclos e impide que el microcontrolador realice otras tareas de forma concurrente.

La solución no bloqueante

La solución ideal pasaría por una implementación basada en colas y en interrupciones. En este caso se ha implementado una máquina de estados que controla el flujo de datos I2C, el troceado de los bytes en dos nibbles y las esperas que hay que realizar entre un envío y el siguiente. Grosso modo, la solución sería la siguiente:

- Cada vez que se quiere escribir en el display, lo que se hace es escribir lo que se quiere mandar al display en una cola de datos, por lo que la función encargada de escribir regresa inmediatamente (no es bloqueante).

- El systick del microcontrolador cuando detecta que hay algún dato en la cola de datos inicia una máquina de estados que se encarga de trocear en byte en dos nibbles y enviarlos en tiempos diferentes, así hasta que la cola de datos quede vacía, en cuyo momento la máquina de estados pasa a modo "IDLE" y queda a la espera que de haya más datos en la cola.

- La capa I2C también está implementada como una cola de bytes de tal manera que si la capa LCD quiere escribir N bytes seguidos por I2C, los escribe de forma no bloqueante en la cola I2C (la función de escritura I2C también regresa inmediatamente) y se va vaciando a medida que la interrupción de callback de transmisión es llamada por el microcontrolador.

A continuación puede verse cómo ha quedado la máquina de estados del controlador LCD:



El código no queda tan sencillo a simple vista pero se trata, sin duda, de una implementación más eficiente.

#include "LCD.H"

using namespace avelino;
using namespace std;

void LCD::init(uint8_t address) {
    this->address = address;
    this->timerCounter = 5;
    this->status = LCD::Status::WAIT_AFTER_INIT;
    this->queue.push(LCD::QueueItem(0x33, LCD::IsCommand::YES));
    this->queue.push(LCD::QueueItem(0x32, LCD::IsCommand::YES));
    this->queue.push(LCD::QueueItem(0x28, LCD::IsCommand::YES));
    this->queue.push(LCD::QueueItem(0x08, LCD::IsCommand::YES));
    this->queue.push(LCD::QueueItem(0x01, LCD::IsCommand::YES));
    this->queue.push(LCD::QueueItem(0x06, LCD::IsCommand::YES));
    this->queue.push(LCD::QueueItem(0x0C, LCD::IsCommand::YES));
}

void LCD::tick() {
    Status localStatus = this->status;
    do {
        this->status = localStatus;
        if (localStatus == LCD::Status::WAIT_AFTER_INIT) {
            if (this->timerCounter > 0)
                this->timerCounter--;
            else
                localStatus = LCD::Status::IDLE;
        }
        else if (localStatus == LCD::Status::IDLE) {
            if (!this->queue.empty()) {
                I2CManager::deviceAddress = this->address << 1;
                localStatus = LCD::Status::SEND_FIRST_NIBBLE;
            }
        }
        else if (localStatus == LCD::Status::SEND_FIRST_NIBBLE) {
            uint8_t byte = this->queue.head().byte;
            LCD::IsCommand isCommand = this->queue.head().isCommand;
            I2CManager::txQueue.push((byte & 0xF0) | ((isCommand == LCD::IsCommand::YES) ? LCD::RS_0 : LCD::RS_1) | LCD::RW_0 | LCD::EN_1 | LCD::BL_1);
            I2CManager::txQueue.push((byte & 0xF0) | ((isCommand == LCD::IsCommand::YES) ? LCD::RS_0 : LCD::RS_1) | LCD::RW_0 | LCD::EN_0 | LCD::BL_1);
            I2CManager::send();
            localStatus = LCD::Status::WAIT_FIRST_NIBBLE_SENT;
        }
        else if (localStatus == LCD::Status::WAIT_FIRST_NIBBLE_SENT) {
            if (I2CManager::txDone) {
                this->timerCounter = 1;
                localStatus = LCD::Status::WAIT_TICK_AFTER_FIRST_NIBBLE_SENT;
            }
        }
        else if (localStatus == LCD::Status::WAIT_TICK_AFTER_FIRST_NIBBLE_SENT) {
            if (this->timerCounter > 0)
                this->timerCounter--;
            else
                localStatus = LCD::Status::SEND_SECOND_NIBBLE;
        }
        else if (localStatus == LCD::Status::SEND_SECOND_NIBBLE) {
            uint8_t byte = this->queue.head().byte << 4;
            LCD::IsCommand isCommand = this->queue.head().isCommand;
            this->queue.pop();
            I2CManager::txQueue.push((byte & 0xF0) | ((isCommand == LCD::IsCommand::YES) ? LCD::RS_0 : LCD::RS_1) | LCD::RW_0 | LCD::EN_1 | LCD::BL_1);
            I2CManager::txQueue.push((byte & 0xF0) | ((isCommand == LCD::IsCommand::YES) ? LCD::RS_0 : LCD::RS_1) | LCD::RW_0 | LCD::EN_0 | LCD::BL_1);
            I2CManager::send();
            localStatus = LCD::Status::WAIT_SECOND_NIBBLE_SENT;
        }
        else if (localStatus == LCD::Status::WAIT_SECOND_NIBBLE_SENT) {
            if (I2CManager::txDone) {
                this->timerCounter = 1;
                localStatus = LCD::Status::WAIT_TICK_AFTER_SECOND_NIBBLE_SENT;
            }
        }
        else if (localStatus == LCD::Status::WAIT_TICK_AFTER_SECOND_NIBBLE_SENT) {
            if (this->timerCounter > 0)
                this->timerCounter--;
            else
                localStatus = LCD::Status::IDLE;
        }
    } while (localStatus != this->status);
}


void LCD::write(const char *s, int16_t size, LCD::IsCommand isCommand) {
    while ((*s != 0) && ((size < 0) || (size > 0))) {
        this->queue.push(QueueItem(*s, isCommand));
        s++;
        if (size > 0)
            size--;
    }
}

La función miembro "tick" es invocada desde la interrupción systick del microcontrolador en "main.cc":

LCD lcd;

void systick() __attribute__ ((section(".systick")));

void systick() {
    lcd.tick();
}

Nótese que las colas (tanto la cola I2C como la cola LCD) están implementadas usando colas circulares estáticas a través de una plantilla ("StaticQueue.H").

#ifndef  __STATICQUEUE_H__
#define  __STATICQUEUE_H__

#include <stdint.h>

extern "C++" {
    namespace avelino {
        using namespace std;

        template <typename T, int32_t N>
        class StaticQueue {
            public:
                T data[N];
                int32_t headIndex;
                int32_t tailIndex;
                void push(const T &v);
                const T &head() { return this->data[this->headIndex]; };
                void pop();
                bool empty() { return (this->headIndex == this->tailIndex); };
                StaticQueue() : headIndex(0), tailIndex(0) { };
        };

        template <typename T, int32_t N>
        void StaticQueue<T, N>::push(const T &v) {
            this->data[this->tailIndex] = v;
            this->tailIndex++;
            if (this->tailIndex == N)
                this->tailIndex = 0;
        }

        template <typename T, int32_t N>
        void StaticQueue<T, N>::pop() {
            this->headIndex++;
            if (this->headIndex == N)
                this->headIndex = 0;
        }
    }
}

#endif  // __STATICQUEUE_H__

Se ha utilizado en varios sitios el "enum class", que permite trabajar con enumerados fuertemente tipados (introducido en el estándar C++11).

En la sección soft puede descargarse todo el código fuente.



[ añadir comentario ] ( 280 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 3730 )
Programación bare metal de un SoC: Prueba de concepto sobre la Orange Pi Zero Plus 
Los SoCs están diseñados para ejecutar sistemas operativos completos (Linux, Android, etc.). La programación bare metal de este tipo de chips es una tarea complicada y poco agradecida (normalmente no se justifica el uso de un SoC sin sistema operativo, para eso están los microcontroladores), sin embargo estos proyectos brindan una oportunidad única para conocer los entresijos del chip y de paso entender mejor cómo funcionan los SoCs en general.

Orange Pi Zero Plus

El corazón de la placa Orange Pi Zero Plus (la que se ha utilizado para esta prueba de concepto) es un SoC H5 de la marca AllWinner. Se trata de un ARM Cortex-A53 de cuadruple núcleo que implementa la arquitectura ARMv8-A (64 bits). En el arranque, todos los ARM de 64 bits arrancan en modo 32 bits, así que por simplicidad se ha decidido que la prueba de concepto se haga en el modo de arranque compatible ARMv7-A (32 bits, sin pasar a modo 64 bits) y utilizando sólo el primer núcleo (en el arranque sólo está operativo el núcleo 0, los núcleos 1, 2 y 3 están desactivados).

La secuencia de arranque del H5

El H5 implementa varias formas y modos de arranque, sin embargo, en la placa Orange Pi Zero Plus el modo de arranque que se usa es el que busca en la tarjeta de memoria (MicroSD) el bootloader. En el caso habitual, para cargar un sistema operativo, dicho bootloader sera el U-Boot u otro similar. Aunque en el manual de usuario del H5 se especifica de forma más detallada, se puede simplificar diciendo que al arrancar el H5 ejecuta una "boot ROM" (BROM) que no es modificable y que se encuentra cableada dentro del chip. Esta ROM se encarga de inicializar la tarjeta de memoria, de cargar el SPL (Second Program Loader) desde la tarjeta de memoria en la RAM y de ejecutar dicho código una vez está cargado en RAM. En terminología H5 este SPL hace las veces de boot loader.

En http://linux-sunxi.org/Bootable_SD_card#SD_Card_Layout se especifica la distribución de los datos en la tarjeta de memoria, dónde debe estar alojado el SPL (offset 8192) y lo que puede ocupar como máximo (32 KBytes). Según la documentación oficial (http://linux-sunxi.org/BROM#U-Boot_SPL_limitations), este SPL no puede ser código tal cual, sino que debe tener un formato y una especie de firma digital especial. Dicho formato se encuentra documentado y un programador desarrolló hace tiempo una pequeña utilidad llamada "mksunxiboot", open source, programada en C, que, a partir de un binario estándar, genera un binario firmado y reconocible por parte del SoC como un SPL válido (la firma no deja de ser una estructura de datos en la cabecera más un checksum). El código fuente de dicha utilidad (es un único fichero en C) se puede encontrar en https://github.com/amery/mksunxiboot/.

Haciendo nuestro propio SPL

Para hacer la prueba de concepto bare metal bastará con hacer un pequeño programa que haga de SPL. En este caso se ha optado por hacer el típico blinker que actúe sobre una de las salidas GPIO de la placa a la que conectaremos un led para comprobar que el invento funciona. Usaremos la salida GPIO12 (se podría usar cualquier otra) que se corresponde con el pin 3 del puerto de expansión de la Orange Pi Zero Plus (http://linux-sunxi.org/Orange_Pi_Zero_P ... nsion_Port).



A continuación necesitaremos cualquier toolchain "arm-none-eabi" que tengamos a mano, puede ser tanto descargada de algún repositorio como compilada por nosotros mismos (ver post en este mismo blog). Se trata de una toolchain diseñada para hacer programas bare metal para arquitecturas ARM de 32 bits. En principio hay dos formas de hacerlo: la elegante y lenta y la "sucia" y rápida. La forma elegante y lenta obliga a escribir un linker script que nos permita pasar casi cualquier programa que queramos a un SPL, sin embargo la forma sucia y rápida, aunque no da tanta libertad, sí que nos permite hacer la prueba de concepto de forma rápida.

#include <stdint.h>

void spl() __attribute__ ((section(".spl")));

void spl() {
    volatile uint64_t n;
    const uint64_t WAIT = 20000ULL;
    const uint32_t CCU_BASE = 0x01C20000;
    *((volatile uint32_t *) (CCU_BASE + 0x0068)) |= 0x00000020;   // PIO clock enable
    const uint32_t PIO_BASE = 0x01C20800;
    *((volatile uint32_t *) (PIO_BASE + 0x0004)) = 0x77717777;  // PA12 como pin de salida
    while (true) {
        *((volatile uint32_t *) (PIO_BASE + 0x0010)) = 0x00001000;   // PA12 := 1
        for (n = 0; n < WAIT; n++)
            ;
        *((volatile uint32_t *) (PIO_BASE + 0x0010)) = 0x00000000;   // PA12 := 0
        for (n = 0; n < WAIT; n++)
            ;
    }
}


Como se puede apreciar, escribimos el código en una función a la que podemos ponerle el nombre que queramos y, mediante atributos del compilador, le decimos que debe estar en la sección ".spl" (esta etiqueta es arbitraria, la sección podría llamarse ".pepejuan"). Nótese que no estamos usando variables globales y no estamos referenciando nada que esté fuera de la propia función en sí (todo el código está autocontenido). Esta limitación es importante, pues, como se verá más adelante, sólo usaremos como código SPL lo que esté dentro de la sección ".spl" que se ha definido en tiempo de compilación.

A la hora de escribir el código se recurrió al manual de usuario oficial del H5 (https://linux-sunxi.org/File:Allwinner_H5_Manual_v1.0.pdf): en la sección "CCU" (sub sección "Gating and reset") se explica cómo habilitar el reloj para el módulo PIO (el encargado de controlar los pines GPIO), mientras que en la sección "Port Controller (CPUx-PORT)" se explica como habilitar y usar los pines GPIO. Para compilar y generar el fichero binario que transferiremos a la tarjeta MicroSD haremos lo siguiente:

arm-none-eabi-g++ -mtune=cortex-a7 -fno-exceptions -fno-rtti -nostartfiles -c -o spl.o spl.cc
arm-none-eabi-objcopy -O binary -j .spl spl.o spl.bin
mksunxiboot spl.bin spl_with_signature.bin


Primero se genera el fichero "spl.o", a continuación usando la utilidad objcopy extraemos en forma binaria el código que se encuentra en la sección ".spl" desde dentro de "spl.o" hacia "spl.bin" y, como tercer paso, invocamos la utilidad "mksunxiboot" para generar, a partir de "spl.bin", un "spl_with_signature.bin" que sí puede ser transferido tal cual a la tarjeta MicroSD. Como se puede apreciar, se le dice al compilador que genere código compatible Cortex-A7 (para que genere código siguiendo la arquitectura ARMv7-A). Para los que tengan curiosidad por el código que ha generado el compilador, se puede desensamblar dicho código mediante el siguiente comando:

arm-none-eabi-objdump -D spl.o


A continuación cogemos el fichero "spl_with_signature.bin" que acabamos de generar, lo copiamos tal cual a partir del offset 8192 de la tarjeta de memoria y arrancamos la Orange Pi Zero Plus con dicha tarjeta de memoria insertada:

dd if=spl_with_signature.img of=/dev/sdb bs=1024 seek=8

Et voilà :



Todo el código fuente está disponible en la sección soft.

[ añadir comentario ] ( 359 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 1428 )
Multitarea apropiativa en microcontroladores: prueba de concepto sobre Arduino Leonardo 
Existen dos tipos básicos de multitarea: la multitarea colaborativa y la multitarea apropiativa. En un post anterior se abordó la implementación de la multitarea cooperativa de forma extensa por lo que ahora le toca el turno a la multitarea apropiativa: en este modelo el sistema "no se fia" de las tareas y de forma periódica arrebata ("se apropia") el control del procesador a la tarea actualmente en ejecución para ceder el control del mismo a otra tarea. Es el mecanismo utilizado por los RTOS en sistemas embebidos y por los sistemas operativos mas grandes (Linux, Windows, OSX, etc.).

Principios

Un sistema con multitarea apropiativa debe por tanto poseer mecanismos que permitan interrumpir la ejecución de la tarea actualmente en curso y que permitan también reanudar la ejecución de otra tarea que haya sido interrumpida previamente. Este mecanismo debería ser lo más transparente al usuario (a las tareas) posible por lo que normalmente se utilizan las interrupciones. Las interrupciones en la totalidad de los procesadores que las implementan (no conozco ningún procesador que no las tenga) permiten ejecutar código de forma no solicitada por la tarea actualmente en ejecución y a raiz de un evento externo al flujo actual de la tarea.

En el momento que se produce la interrupción (la causa puede ser externa al procesador: entradas de datos, pines de entrada que cambian de estado o interna: división entre cero, instrucción no reconocida, etc.) el procesador almacena en la pila del sistema la dirección de la siguiente instrucción que se va a ejecutar y hace que el contador de programa apunte a la primera instrucción del código de interrupción. Este código de interrupción que se ejecuta a raiz del evento suele denominarse ISR (Interrupt Service Routine).



Normalmente existirán diferentes orígenes de interrupción y diferentes vectores de interrupción. Por ejemplo un procesador podría tener dos orígenes de interrupción (el cambio de estado de un pin de entrada y el desbordamiento de un contador interno) y un solo vector de interrupción por lo que se ejecutará la misma ISR para cualquiera de los dos eventos que se produzca. En estos casos, obviamente, el procesador siempre provee mecanismos para que la ISR sea capaz de discernir cuál ha sido la causa de que ella se esté ejecutando (algún registro de estado, por ejemplo).

Lo normal es tener aproximadamente la misma cantidad de orígenes de interrupción que de vectores de interrupción, de tal forma que podemos definir una ISR para cada origen de interrupción. Nótese que una ISR no es más que un trozo de código. En algunos sistemas las ISR no se diferencian en nada de una función normal (por ejemplo, ARM Cortex-M) que debe terminar como todas las funciones con algún tipo de instrucción "ret", mientras que en otros sistemas se debe utilizar algun tipo de instrucción especial normalmente a la hora de regresar: por ejemplo los microcontroladores AVR deben terminar sus funciones ISR con la instrucción "reti" (RETurn from Interrupt). Sin embargo, salvo estas excepciones, dentro de una ISR se puede poner el código que se quiera: no deja de ser un trozo de código como cualquier otro.

Una ISR sencillita

Consideremos inicialmente una ISR sencillita que vamos a compilar para Arduino Leonardo (microcontrolador ATmega32U4):

#include <avr/interrupt.h>
#include <avr/io.h>
#include <stdint.h>

using namespace std;

ISR(TIMER0_OVF_vect) {
    PORTC ^= 0x80;
}

int main() {
    PRR1 |= 0x80;
    DDRC |= 0x80;
    TCCR0B |= 0x05;
    TIMSK0 |= 0x01;
    sei();
    while (true)
        ;
    return 0;
}

$ /ruta/avr/bin/avr-g++ -std=c++11 -DF_CPU=16000000UL -mmcu=atmega32u4 -Os -g -c -o test.o test.cc
$ /ruta/avr/bin/avr-g++ -std=c++11 -DF_CPU=16000000UL -mmcu=atmega32u4 -Os -c -o test.elf test.o

Como se puede ver, usando el compilador avr-g++ se puede hacer de forma muy sencilla un código con soporte para interrupciones en C++. En este caso tenemos un sencillo blinker de toda la vida: cada vez que el Timer 0 se desborda se cambia el estado del bit de salida y hace cambiar de estado a su vez un led conectado a él. Para comprobar de forma detallada cómo funciona el invento podemos desensamblar el fichero ELF generado por el compilador:

$ /ruta/avr/bin/avr-objdump -D test.elf

En la dirección 0 de la memoria tenemos los diferentes vectores de interrupción. Como se puede apreciar está definido el vector 0 (denominado vector de reset ya que en muchos procesadores, como el AVR, el reset se trata como una interrupción más por lo que el vector de reset indica qué código debe ejecutarse nada más encenderse el procesador) y el vector 23 (que se corresponde en el ATmega32U4 con la interrupción de desbordamiento del Timer 0):

Disassembly of section .text:

00000000 <__vectors>:
0: 0c 94 56 00 jmp 0xac ; 0xac <__ctors_end>
4: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
8: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
c: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
10: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
14: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
18: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
1c: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
20: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
24: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
28: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
2c: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
30: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
34: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
38: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
3c: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
40: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
44: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
48: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
4c: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
50: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
54: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
58: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
5c: 0c 94 62 00 jmp 0xc4 ; 0xc4 <__vector_23>
60: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
64: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
68: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
6c: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
70: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>
74: 0c 94 60 00 jmp 0xc0 ; 0xc0 <__bad_interrupt>

Si nos vamos al código que ha generado el compilador para la ISR correspondiente al vector 23:

000000c4 <__vector_23>:
c4: 1f 92 push r1
c6: 0f 92 push r0
c8: 0f b6 in r0, 0x3f ; 63
ca: 0f 92 push r0
cc: 11 24 eor r1, r1
ce: 8f 93 push r24
d0: 88 b1 in r24, 0x08 ; 8
d2: 80 58 subi r24, 0x80 ; 128
d4: 88 b9 out 0x08, r24 ; 8
d6: 8f 91 pop r24
d8: 0f 90 pop r0
da: 0f be out 0x3f, r0 ; 63
dc: 0f 90 pop r0
de: 1f 90 pop r1
e0: 18 95 reti

Vemos que lo primero que hace la ISR es guardar en la pila (PUSH) los registros R1, R0, SREG y R24 que son registros que utiliza ("ensucia") para hacer la operación:

PORTC ^= 0x80;

Y, tras realizar dicha operación, restaura de nuevo dichos registros en orden inverso desde la pila (POP) antes de regresar (RETI). Esta forma de operar hace que la tarea principal (el bucle infinito que hay en la función "main") no se da cuenta de que es interrumpido de forma periódica ya que la ISR se encarga de salvaguardar y restaurar los registros que utiliza de forma transparente. La función "main" como mucho puede notar que cada cierto tiempo, entre instrucción e instrucción, pasan más ciclos de lo normal :-).

Conmutación entre tareas

Como se comentó más arriba, cuando se produce una interrupción, los procesadores guardan siempre en la pila la dirección a donde el contador de programa (PC) debe regresar una vez que la interrupción ha terminado de servirse (cuando la ISR termine de ejecutarse). En el caso del ATmega32U4 el procesador empuja en la pila 3 bytes en dos de los cuales almacena la dirección de memoria de la siguiente instrucción que iba a ejecutar (aunque el ATmega32U4 tiene un espacio de direccionamiento de 16 bits, el núcleo AVR que utiliza es el mismo que tienen otros procesadores AVR que tienen un espacio de direcciones de más de 16 bits, de ahí los 3 bytes que se reservan en la pila para la dirección de retorno de la interrupción).

Si lo que queremos es conmutar entre tareas lo que hay que hacer nada más empezar la ejecución de la función ISR es guardar absolutamente todo el estado del procesador y esto se consigue en el caso de AVR apilando los 32 registros generales (desde R0 hasta R31) más el registro de estado SREG en la pila del sistema (PUSH).

ISR(TIMER0_OVF_vect) __attribute__ ((naked));

ISR(TIMER0_OVF_vect) {
    asm volatile (
        "push r0\n"
        "push r1\n"
        "push r2\n"
        "push r3\n"
        "push r4\n"
        "push r5\n"
        "push r6\n"
        "push r7\n"
        "push r8\n"
        "push r9\n"
        "push r10\n"
        "push r11\n"
        "push r12\n"
        "push r13\n"
        "push r14\n"
        "push r15\n"
        "push r16\n"
        "push r17\n"
        "push r18\n"
        "push r19\n"
        "push r20\n"
        "push r21\n"
        "push r22\n"
        "push r23\n"
        "push r24\n"
        "push r25\n"
        "push r26\n"
        "push r27\n"
        "push r28\n"
        "push r29\n"
        "push r30\n"
        "push r31\n"
        "in r0, 0x3f\n"
        "push r0\n"

A continuación, y como el top de la pila es algo cambiante a medida que se va ejecutando código, guardamos en una variable global la dirección de memoria del actual top de la pila: esto nos permitirá acceder cómodamente a los registros que acabamos de guardar independientemente de que empujemos más cosas en ella:

        // update stackPointerReference
        "push r0\n"
        "in r0, 0x3e\n"
        "sts stackPointerReference + 1, r0\n"    // sph
        "in r0, 0x3d\n"
        "sts stackPointerReference, r0\n"        // spl
        "pop r0\n"
    );
    stackPointerReference = (volatile uint8_t *) ((((uint32_t) stackPointerReference) + 1) | 0x800000);   // 23-th bit to 1 for SRAM address space

Poner a 1 el bit 23 del puntero stackPointerReference es un artificio necesario en avr-gcc ya que en ese entorno de compilación esa es la forma en la que se diferencian los punteros a memoria de datos de los punteros a memoria de programa (hay que recordar que los AVR tienen arquitectura Harvard).

Tras tener adecuadamente inicializado el puntero "stackPointerReference" podemos proceder a realizar la conmutación de tareas en sí. En nuestro caso se asume una política de tipo Round-robin en la que todas las tareas tienen exactamente el mismo tiempo de proceso. Lo que haremos será, partiendo de una lista de N tareas, cada vez que se ejecute la interrupción de desbordamiento del Timer 0, cambiaremos de la tarea i-ésima a la tarea ((i + 1) MOD N)-ésima, con lo que nos aseguramos que cuando llegamos a la última tarea de la lista volvemos a empezar por la primera y así sucesivamente.

Para cada tarea definimos un objeto de clase Task:

class StackFrame {
    public:
        uint8_t sreg;
        uint8_t r[32];
        uint8_t pc[3];
        void setPC(void *f) { this->pc[0] = 0; this->pc[1] = ((uint32_t) f) & 0x000000FF; this->pc[2] = ((((uint32_t) f) >> 8) & 0x000000FF); };
} __attribute__ ((packed));

class Task {
    public:
        StackFrame stackFrame;
        bool started;
        void (*run)();
        Task() : started(false) { };
};

Cada tarea tiene una copia del marco de pila ("stack frame") de la última vez que fue interrumpida, un booleano para indicar si la tarea ha sido iniciada o no y un puntero a una función que apunta a la primera instrucción de dicha tarea. En nuestro caso vamos a asumir, sin pérdida de generalidad, que nuestras tareas nunca terminan (no vamos a controlar lo que ocurre cuando la tarea termine).

Definimos además de forma global un array de punteros a objetos de tipo Task, una variable "currentTaskIndex" que indica la actual tarea que está en ejecución y el puntero "stackPointerReference" del que hablamos antes.

const uint16_t MAX_TASKS = 4;
volatile uint16_t numTasks;
volatile Task tasks[MAX_TASKS];
volatile uint16_t currentTaskIndex;
volatile uint8_t *stackPointerReference;

Los primero que hacemos tras calcular el valor de "stackPointerReference" es trabajar con la tarea actual:

    Task *currentTask = (Task *) &tasks[currentTaskIndex];
    if (currentTask->started) {
        // copy stack data to currentTask->stackFrame
        memcpy((void *) &currentTask->stackFrame, (const void *) (stackPointerReference + 1), sizeof(StackFrame));
    }
    else {
        // replace return address on currentTask->data with currentTask->run
        memset((void *) &currentTask->stackFrame, 0, sizeof(StackFrame));
        currentTask->stackFrame.setPC((void *) currentTask->run);
    }

Si ya está iniciada copiamos los registros que acabamos de apilar (en los PUSH masivos que hicimos al principio de la ISR) al campo "stackFrame" del objeto Task correspondiente a la tarea actual: esto es, ponemos a salvo los registros de la tarea actual pues nos disponemos a hacer una conmutación a la siguiente tarea.

En caso de que la tarea actual no esté iniciada lo que hacemos es borrar el campo "stackFrame" del objeto Task correspondiente a la tarea actual e inicializamos, dentro de esta estructura "stackFrame", los bytes correspondientes al contador de programa para que apunten a la primera instrucción de la tarea actual. Esto hará que cuando se restaure el marco de pila ("stack frame") de esta tarea se inicie dicha tarea (puesto que el contador de programa irá a la primera instrucción de dicha tarea).

A continuación trabajamos con el objeto de tipo Task correspondiente a la tarea siguiente:

    uint16_t nextTaskIndex = currentTaskIndex + 1;
    if (nextTaskIndex == numTasks)
        nextTaskIndex = 0;
    Task *nextTask = (Task *) &tasks[nextTaskIndex];
    if (nextTask->started) {
        // replace stack data with nextTask->stackFrame
        memcpy((void *) (stackPointerReference + 1), (const void *) &nextTask->stackFrame, sizeof(StackFrame));
    }
    else {
        // replace return address on stack with nextTask->run
        ((StackFrame *) (stackPointerReference + 1))->setPC((void *) nextTask->run);
        nextTask->started = true;
    }

En caso de que la siguiente tarea a iniciar ya esté iniciada ("started") simplemente sobreescribimos todo el marco de pila (los datos que metimos en la pila con los PUSH masivos del principio de la ISR) con los bytes de campo "stackFrame" de la siguiente tarea, lo que provocará una conmutación a la tarea siguiente en el momento que retornemos de la interrupción. En caso de que la siguiente tarea no esté iniciada aún hacemos lo mismo que en caso de la tarea actual: inicializamos, dentro de la estructura "stackFrame" los bytes correspondientes al contador de programa para que apunten a la primera instrucción de la tarea siguiente y, a continuación, marcamos la tarea como iniciada ("started = true").

Antes de terminar actualizamos la variable global "currentTaskIndex" para que apunte a la tarea a la que se le va a entregar el control de la CPU y hacemos una restauración normal de la pila (POP masivos) antes de terminar definitivamente con la instrucción "RETI".

    currentTaskIndex = nextTaskIndex;
    asm volatile (
        "pop r0\n"
        "out 0x3f, r0\n"
        "pop r31\n"
        "pop r30\n"
        "pop r29\n"
        "pop r28\n"
        "pop r27\n"
        "pop r26\n"
        "pop r25\n"
        "pop r24\n"
        "pop r23\n"
        "pop r22\n"
        "pop r21\n"
        "pop r20\n"
        "pop r19\n"
        "pop r18\n"
        "pop r17\n"
        "pop r16\n"
        "pop r15\n"
        "pop r14\n"
        "pop r13\n"
        "pop r12\n"
        "pop r11\n"
        "pop r10\n"
        "pop r9\n"
        "pop r8\n"
        "pop r7\n"
        "pop r6\n"
        "pop r5\n"
        "pop r4\n"
        "pop r3\n"
        "pop r2\n"
        "pop r1\n"
        "pop r0\n"
        "reti\n"
    );
}

Para la prueba de concepto se implementaros dos tareas muy sencillas: cada una hace parpadear un led a una velocidad diferente:

void task1() __attribute__ ((naked));

void task1() {
    DDRD |= 0x04;     // PD2 (D0 on Arduino Leonardo) as output
    while (true) {
        PORTD ^= 0x04;
        for (volatile uint32_t i = 0; i < 66000; i++)
            ;
    }
}

void task2() __attribute__ ((naked));

void task2() {
    DDRC |= 0x80;     // PC7 (D13 on Arduino Leonardo) as output
    while (true) {
        PORTC ^= 0x80;
        for (volatile uint32_t i = 0; i < 200000; i++)
            ;
    }
}


Consideraciones adicionales

Nótese que tanto la ISR como las funciones "tarea" ("task1" y "task2") son declaradas con el atributo "naked". Este atributo indica al compilador que no genere código preámbulo ni postámbulo (el código ensamblador relacionado normalmente con el manejo de parámetros y valores de retorno).

En el caso de las funciones "task1" y "task2" se ha usado este atributo por una cuestión de coherencia ya que no se trata de funciones que son invocadas de forma normal desde otra parte del programa y además se trata de funciones que no terminan nunca de ejecutarse.

El caso de la función ISR es más delicado porque en ese caso sí que es necesario usar el atributo "naked". Como se vió en la primera prueba con la interrupción del Timer 0, para el siguiente código:

ISR(TIMER0_OVF_vect) {
    PORTC ^= 0x80;
}

El compilador generaba instrucciones PUSH y POP de los registros que utilizaría, antes y después de la operación "PORTC ^= 0x80" respectivamente. En nuestro caso necesitamos que el apilado (PUSH) y desapilado (POP) de registros sea siempre igual y masivo y que esté perfectamente controlado por nosotros por lo que definimos la función con el atributo "naked" y nos encargamos nosotros de escribir de forma explícita el código ensamblador de preámbulo y postámbulo de la ISR.



Todo el código puede descargarse de la sección soft.

[ añadir comentario ] ( 5799 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 3199 )
Compilar la toolchain de GNU para ARM 
Hace tiempo publiqué las instrucciones para compilar la toolchain de GNU para ARM "bare metal" (sin sistema operativo, arm-none-eabi) basada en GCC 5.1 y newlib. Dichas instrucciones no son aplicables para las versiones actuales de GCC (7.2 a día de hoy) por lo que a continuación indico las instrucciones actualizadas a las nuevas versiones de binutils, gcc y newlib.

Se trata de una toolchain para sistemas "bare metal", sin sistema operativo, por lo que no tiene soporte para multihilos ni para librerías dinámicas.

binutils 2.29

mkdir -p /opt/baremetalarm/src
mkdir -p /opt/baremetalarm/build
cd /opt/baremetalarm/src
wget https://ftp.gnu.org/gnu/binutils/binutils-2.29.tar.bz2
tar xf binutils-2.29.tar.bz2
chown -R root:root binutils-2.29
cd ../build
mkdir binutils-2.29
cd binutils-2.29/
../../src/binutils-2.29/configure --prefix=/opt/baremetalarm --target=arm-none-eabi --disable-nls --disable-multilib
make
make install


gcc 7.2.0 (stage 1)

cd /opt/baremetalarm/src
wget https://ftp.gnu.org/gnu/gcc/gcc-7.2.0/gcc-7.2.0.tar.gz
wget https://ftp.gnu.org/gnu/gmp/gmp-6.1.2.tar.bz2
wget https://ftp.gnu.org/gnu/mpc/mpc-1.0.3.tar.gz
wget https://ftp.gnu.org/gnu/mpfr/mpfr-3.1.6.tar.gz
tar xf gcc-7.2.0.tar.gz
tar xf gmp-6.1.2.tar.bz2
tar xf mpc-1.0.3.tar.gz
tar xf mpfr-3.1.6.tar.gz
mv gmp-6.1.2 gcc-7.2.0/gmp
mv mpc-1.0.3 gcc-7.2.0/mpc
mv mpfr-3.1.6 gcc-7.2.0/mpfr
chown -R root:root gcc-7.2.0
cd ../build/
mkdir gcc-7.2.0-stage-1
cd gcc-7.2.0-stage-1/
export PATH=/opt/baremetalarm/bin:${PATH}
../../src/gcc-7.2.0/configure --prefix=/opt/baremetalarm --target=arm-none-eabi --enable-languages=c --without-headers --disable-nls --disable-multilib --disable-threads --disable-shared --disable-libssp --with-newlib
make all-gcc all-target-libgcc
make install-gcc install-target-libgcc


newlib

cd /opt/baremetalarm/src
git clone git://sourceware.org/git/newlib-cygwin.git
cd ../build
mkdir newlib
cd newlib
../../src/newlib-cygwin/configure --prefix=/opt/baremetalarm --target=arm-none-eabi --disable-multilib
make
make install


gcc 7.2.0 (stage 2)

cd /opt/baremetalarm/build
mkdir gcc-7.2.0-stage-2
cd gcc-7.2.0-stage-2/
../../src/gcc-7.2.0/configure --prefix=/opt/baremetalarm --target=arm-none-eabi --enable-languages="c,c++" --disable-nls --disable-multilib --disable-threads --disable-shared --disable-libssp --with-newlib
make
make install


El compilador de C++ de GCC 7.2 compila por defecto en modo C++14 y soporta prácticamente todo el estándar C++17.

[ añadir comentario ] ( 921 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 2686 )

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Siguiente> >>