Operaciones atómicas en ARM

Question

He estado trabajando en un sistema operativo integrado para ARM, sin embargo, hay algunas cosas que no entendí sobre la arquitectura, incluso después de referirme a ARMARM y fuente de Linux.

Operaciones atómicas.

ARM ARM dice que las instrucciones de carga y almacenamiento son atómicas y se garantiza que su ejecución estará completa antes de que se ejecute el controlador de interrupciones. Verificado examinado

arch/arm/include/asm/atomic.h : 
    #define atomic_read(v) (*(volatile int *)&(v)->counter) 
    #define atomic_set(v,i) (((v)->counter) = (i)) 

Sin embargo, el problema viene cuando quiero manipular este valor de forma atómica utilizando las instrucciones de la CPU (atomic_inc, atomic_dec, atomic_cmpxchg etc ..) que utilizan LDREX y STREX para ARMv7 (mi objetivo) .

ARMARM no dice nada acerca de las interrupciones que se bloquean en esta sección, por lo que supongo que puede producirse una interrupción entre LDREX y STREX. Lo que sí menciona es acerca de bloquear el bus de memoria, que supongo que solo es útil para sistemas MP donde puede haber más CPU intentando acceder a la misma ubicación al mismo tiempo. Pero para UP (y posiblemente MP), si se activa una interrupción de temporizador (o IPI para SMP) en esta pequeña ventana de LDREX y STREX, el controlador de excepción ejecuta posiblemente cambios en el contexto de la CPU y vuelve a la nueva tarea, sin embargo la parte impactante aparece ahora , ejecuta 'CLREX' y, por lo tanto, elimina cualquier bloqueo exclusivo mantenido por el hilo anterior. Entonces, ¿qué mejor que usar LDREX y STREX que LDR y STR para la atomicidad en un sistema UP?

He leído algo sobre un monitor de bloqueo exclusivo, así que tengo una teoría posible de que cuando el hilo se reanude y ejecute el STREX, el monitor del sistema operativo hará que falle esta llamada y se pueda detectar el ciclo. ejecutado usando el nuevo valor en el proceso (rama de regreso a LDREX), ¿estoy aquí?

Answer 1

Bien, obtuve la respuesta de su website.

Si un cambio de contexto programa un proceso después de que el proceso haya realizado una carga-exclusiva pero antes de que ejecute el exclusivo de tienda, el exclusivo de tienda devuelve un resultado falso negativo cuando se reanuda el proceso y la memoria no se actualiza. Esto no afecta la funcionalidad del programa, porque el proceso puede volver a intentar la operación de inmediato.

Answer 2

La idea detrás del paradigma/tienda exclusiva de carga ligada es que si si la tienda sigue muy pronto después de la carga, sin operaciones de memoria que intervienen, y si no otra cosa ha tocado la ubicación, la tienda es probable para tener éxito, pero si algo más ha tocado la ubicación de la tienda es cierto para fallar. No hay garantía de que las tiendas a veces no fallarán sin razón aparente; si el tiempo entre carga y almacenamiento se mantiene al mínimo, sin embargo, y hay accesos sin memoria entre ellos, como un bucle:

do 
{ 
    new_value = __LDREXW(dest) + 1; 
} while (__STREXW(new_value, dest)); 

general se puede confiar para tener éxito dentro de unos pocos intentos.Si el cálculo del nuevo valor basado en el valor anterior requiere algún cálculo significativo, se debe reescribir el bucle como:

do 
{ 
    old_value = *dest; 

    new_value = complicated_function(old_value); 
} while (CompareAndStore(dest, new_value, old_value) != 0); 

... Assuming CompareAndStore is something like: 

uint32_t CompareAndStore(uint32_t *dest, uint32_t new_value, uint_32 old_value) 
{ 
    do 
    { 
    if (__LDREXW(dest) != old_value) return 1; // Failure 
    } while(__STREXW(new_value, dest); 
    return 0; 
} 

Este código tendrá que volver a ejecutar el bucle principal si algo cambia * dest mientras que el nuevo valor se calcula , pero sólo se necesita el pequeño bucle que se vuelva a ejecutar si el __STREXW falla por alguna otra razón [que se espera no es demasiado probable, teniendo en cuenta que sólo habrá unos dos instrucciones entre la __LDREXW y __STREXW]

Adición Un ejemplo de una situación en la que "calcular un nuevo valor basado en el anterior" podría ser complicado sería una en la que los "valores" ar e efectivamente una referencia a una estructura de datos compleja. El código puede buscar la referencia anterior, derivar una nueva estructura de datos de la anterior y luego actualizar la referencia. Este patrón aparece mucho más a menudo en los marcos recolectados de basura que en la programación de "metal desnudo", pero hay una variedad de formas en que puede surgir incluso cuando se programa metal desnudo. Los asignadores malloc/calloc normales generalmente no son seguros para la rosca/interruptores, pero a menudo lo son los asignadores para estructuras de tamaño fijo. Si uno tiene un "pool" de algún número de potencias de dos de las estructuras de datos (digamos 255), se podría utilizar algo como:

#define FOO_POOL_SIZE_SHIFT 8 
#define FOO_POOL_SIZE (1 << FOO_POOL_SIZE_SHIFT) 
#define FOO_POOL_SIZE_MASK (FOO_POOL_SIZE-1) 

void do_update(void) 
{ 
    // The foo_pool_alloc() method should return a slot number in the lower bits and 
    // some sort of counter value in the upper bits so that once some particular 
    // uint32_t value is returned, that same value will not be returned again unless 
    // there are at least (UINT_MAX)/(FOO_POOL_SIZE) intervening allocations (to avoid 
    // the possibility that while one task is performing its update, a second task 
    // changes the thing to a new one and releases the old one, and a third task gets 
    // given the newly-freed item and changes the thing to that, such that from the 
    // point of view of the first task, the thing never changed.) 

    uint32_t new_thing = foo_pool_alloc(); 
    uint32_t old_thing; 
    do 
    { 
    // Capture old reference 
    old_thing = foo_current_thing; 

    // Compute new thing based on old one 
    update_thing(&foo_pool[new_thing & FOO_POOL_SIZE_MASK], 
     &foo_pool[old_thing & FOO_POOL_SIZE_MASK); 
    } while(CompareAndSwap(&foo_current_thing, new_thing, old_thing) != 0); 
    foo_pool_free(old_thing); 
} 

Si no será a menudo múltiples hilos/interrupciones/lo que sea que intentan actualice la misma cosa al mismo tiempo, este enfoque debería permitir que las actualizaciones se realicen de forma segura. Si existe una relación de prioridad entre las cosas que pueden intentar actualizar el mismo elemento, se garantiza que la más alta prioridad tendrá éxito en su primer intento, la próxima prioridad más alta tendrá éxito en cualquier intento que no sea reemplazado por el de mayor prioridad, etc. Si uno usaba el bloqueo, la tarea de mayor prioridad que quería realizar la actualización tendría que esperar a que termine la actualización de menor prioridad; utilizando el paradigma CompareAndSwap, la tarea de mayor prioridad no se verá afectada por la inferior (pero hará que la inferior tenga que hacer un trabajo desaprovechado).