1.1. El Problema con la Concurrencia

(Sáltate esto si sabes lo que es una Condición de Carrera (Race Condition).

En un programa normal, puedes incrementar un contador de la forma:

      contador_muy_importante++;
    

Esto es lo que esperarías que pasase:

Esto es lo que quizás pase:

Este solapamiento, donde lo que sucede depende del tiempo relativo de múltiples tareas, es llamado condición de carrera. La parte de código que contenie al punto de concurrencia se llamado región crítica. Y especialmente desde que Linux se empezó a ejecutar en máquinas SMP, se ha convertido en uno de los puntos más grandes del diseño e implementación del núcleo.

La solución es reconocer cuando ocurren estos accesos simultáneos, y usar bloqueos para asegurar que sólo una instancia puede entrar en la región crítica en cada instante. Hay muchas primitivas amigables en el núcleo Linux que te ayudan a hacer esto. Y entonces hay primitivas no amigables, pero yo intento que no existan.

2.1. Bloqueos y Núcleos Monoprocesador

Para núcleos compilados sin CONFIG_SMP, los spinlocks no existen. Esta es una excelente decisión de diseño; cuando nadie se puede ejecutar al mismo tiempo, no hay motivo para tener un bloqueo.

Deberías siempre de probar tu código de bloqueo con CONFIG_SMP habilitado, incluso si no tienes un equipo de prueba SMP, porque aún así pillará algunos tipos (simples) de deadlock.

Los semáforos todavía existen, porque son requeridos para la sincronización entre contextos de usuario, tal como veremos a continuación.

2.2. Variantes de Bloqueo Lectura/Escritura

Los spinlocks y los semáforos tienen variantes de lectura/escritura: rwlock_t y struct rw_semaphore. Estos dividen a los usuarios en dos clases: los lectores y los escritores. Si sólo estás leyendo datos, puedes coger un bloqueo de lectura, pero para escribir los datos necesitas un bloqueo de escritura. Mucha gente puede tener un bloqueo de lectura, pero uno de escritura debe de ser único.

Esto significa que es mucho más fácil bloquear si tu código se divide ordenadamente entre líneas lectoras y escritoras. Toda las discusiones posteriores también se aplican a las variantes de lectura/escritura.

2.3. Bloqueando Sólo en el Contexto de Usuario

Si tienes una estructura de datos que siempre es accedida desde el contexto de usuario, entonces puedes usar un semáforo simple (linux/asm/semaphore.h) para protegerla. Este es el caso más trivial; inicializas el semáforo al número de recursos disponibles (usualmente 1), y llamas a down_interruptible() para coger el semáforo, y up() para liberarlo. Hay también una función down(), que debería de ser evitada, porque no regresará si se recibe una señal.

Ejemplo: linux/net/core/netfilter.c permite el registro de unas nuevas llamadas setsockopt() y getsockopt(). El registro y desregistro sólo son realizadas en la carga y descarga de un módulo (y tiempo de arranque, donde no hay concurrencia), y la lista de registros sólo es consultada por una llamada al sistema desconocida setsockopt() o getsockopt(). La nf_sockopt_mutex es perfecta para proteger esto, especialmente desde que las llamadas setsockopt y getsockopt quizás se vayan a dormir. sleep.

2.4. Bloqueando entre Contexto de Usuario y BHs (Bottom Halves)

Si un bottom half comparte datos con el contexto de usuario, tienes dos problemas. El primero, el actual contexto de usuario puede ser interrumpido por un bottom half, y el segundo, la región crítica puede ser ejecutada desde otra CPU. Aquí es donde es usado spin_lock_bh() (include/linux/spinlock.h). El deshabilita los bottom halves es esta CPU, entonces coge el bloqueo. spin_unlock_bh() realiza lo inverso.

Esto además funciona perfectamente para UP ; el spinlock desaparece, y esta macro simplemente se transforma en local_bh_disable() (include/asm/softirq.h), la cual te protege de que el bottom half se ejecute.

2.5. Bloqueando Entre Contexto de Usuario y Tasklets/Soft IRQs

Esto es exactamente lo mismo que lo anterior, porque local_bh_disable() actualmente también deshabilita todas las softirqs y tasklets en esta CPU. Debería de ser llamada `local_softirq_disable()', pero el nombre ha sido preservado por motivos históricos. De forma similar, en un mundo perfecto spin_lock_bh() debería de ser llamada spin_lock_softirq().

2.6. Bloqueando Entre Bottom Halves

Algunas veces un bottom half quizás quiera compartir datos con otro bottom half (recuerda especialmente que los cronómetros se ejecutan en un bottom half).

2.7. Bloqueando Entre Tasklets

Algunas veces una tasklet quizás quiera compartir datos con otra tasklet, o con un bottom half.

2.8. Bloqueando entre Softirqs

Frecuentemente una softirq quizás quiera compartir datos con ella misma, con una tasklet, o con un bottom half.

3.1. Bloqueando entre IRQs Hardware y Softirqs/Tasklets/BHs

Si un manejador irq hardware comparte datos con una softirq, tienes dos problemas. Primeramente, la softirq procesando puede ser interrumpida por una interrupción hardware, y segundo, la región crítica podría ser entrada por una interrupción hardware en otra CPU. Aquí es donde se usa spin_lock_irq(). Está definida para deshabilitar las interrupciones en esa cpu, entonces coge el bloqueo. spin_unlock_irq() hace lo inverso.

Esto también trabaja perfectamente para UP: el spinlock se desvanece, y esta macro simplemente se convierte en local_irq_disable() (include/asm/smp.h), qye te protege de que las softirq/tasklet/BH se ejecuten.

spin_lock_irqsave() (include/linux/spinlock.h) es una variante que salva cuando las interrupciones estaban habilidatas o deshabilitadas en una palabra de flags, que es pasada a spin_lock_irqrestore(). Esto significa que el mismo código puede ser usado dentro de un manejador irq hardware (donde las interrupciones ya estan deshabilitadas) y en softirqs (donde se requiere el deshabilitar las irqs).

4.1. En un Contexto de Interrupciones No Escritores

Hay un caso bastante común donde un manejador de interrupciones necesita acceder a la región crítica, pero no necesita acceso de escritura. En este caso, no necesitas usar read_lock_irq(), únicamente read_lock() en todos los sitios (desde que ocurre una interrupción, el manejador irq sólo intentará coger el bloqueo, que no hará deadlock). Todavía necesitas usar write_lock_irq().

Una lógica similar se aplica al bloqueo entre softirqs/tasklets/BHs que nunca necesitan un bloqueo de escritura, y al contexto de usuario: read_lock() y write_lock_bh().

4.2. Deadlock: Simple y Avanzado

Hay un fallo de codificación donde un pedazo de código intenta obtener un spinlock dos veces: él esperará siempre, esperando a que el bloqueo sea liberado (spinlocks, rwlocks y semáforos no son recursivos en Linux). Esto es trivial de diagnosticar: no es un tipo de problema de estar-cinco-noches-despierto-hablando-con-los-suaves-conejitos-del-código.

Para un caso ligeramente más complejo, imagínate que tienes una región compartida por un bottom half y un contexto de usuario. Si usas una llamada spin_lock() para protegerla, es posible que el contexto de usuario sea interrumpido por el bottom half mientras mantiene el bloqueo, y el bottom half entonces esperará para siempre para obtener el mismo bloqueo.

Ambas son llamadas deadlock (bloqueo muerto), y como se mostró antes, puede ocurrir con una CPU simple (aunque no en compilaciones para UP, ya que los spinlocks se desvanecen en la compilación del núcleo con CONFIG_SMP=n. Aún tendrás corrupción de datos en el segundo ejemplo).

Este bloqueo completo es fácil de diagnosticar: en equipos SMP el cronómetro guardián o compilado con DEBUG_SPINLOCKS establecido (include/linux/spinlock.h) nos mostrará esto inmediatamente cuando suceda.

Un problema más complejo es el también llamado `abrazo mortal', involucrando a dos o más bloqueos. Digamos que tienes una tabla hash: cada entrada en la tabla es un spinlock, y una cadena de objetos ordenados. Dentro de un manejador softirq, algunas veces quieres alterar un objeto de un lugar de la tabla hash a otro: coges el spinlock de la vieja cadena hash y el spinlock de la nueva cadena hash, y borras el objeto de la vieja y lo insertas en la nueva.

Aquí hay dos problemas. El primero es que si tu código siempre intenta mover el objeto a la misma cadena, él se hará un deadlock cuando se intente bloquear dos veces. El segundo es que si la misma softirq u otra CPU está intentando mover otro objeto en la dirección inversa podría pasar lo siguiente:

Las dos CPUs esperarán para siempre, esperando a que el otro libere su bloqueo. Él parecerá, olerá, y se sentirá como si cayera el sistema.

4.3. Datos por cada CPU

Una gran técnica usada ampliamente para eliminar el bloqueo es duplicar la información para cada CPU. Por ejemplo, si quieres mantener una cuenta de una condición común, puedes usar un spinlock y un contador simple. Bonito y simple.

Si esto era muy lento [probablemente no], puedes en vez de esto usar un contador para cada CPU [no lo hagas], entonces ninguno de ellos necesitarán un bloqueo exclusivo [estás gastando tu tiempo aquí]. Para asegurarte de que las CPUs no tienen que sincronizar las cachés todo el tiempo, alinea los contadores al límite de las cachés añadiendo `__cacheline_aligned' a la declaración (include/linux/cache.h). [¿No puedes pensar en alguna cosa mejor que hacer?]

De cualquier forma necesitarán un bloqueo de lectura para acceder a sus propios contadores. De esta forma puedes usar un bloqueo de escritura para garantizar acceso exclusivo a todos ellos a la vez, para llevar cuenta de ellos.

4.4. Bloqueos Gran Lector

Un ejemplo clásico de información para cada CPU son los bloqueos `gran lector' de Ingo (linux/include/brlock.h). Estos usan técnicas de datos de cada CPU descritas más adelante para crear un bloqueo que es muy rápido en obtener un bloqueo de lectura, pero agonizantemente lento para un bloqueo de escritura.

Afortunadamente, hay un número limitado disponible de estos bloqueos: tienes que ir a través de un proceso de entrevista estricta para obtener uno.

4.5. Eliminando los bloqueos: Ordenamiento de Lecturas y Escrituras

Algunas veces es posible eliminar el bloqueo. Considera el siguiente caso del código del cortafuegos 2.2, que inserta un elemento en una lista simplemente enlazada en el contexto de usuario:

        new->next = i->next;
        i->next = new;
    

Aquí el autor (Alan Cox, que sabía lo que estaba haciendo) asume que el asignamiento de punteros es atómico. Esto es importante, porque los paquetes de red atravesarían esta lista en bottom halves sin un bloqueo. Dependiendo del tiempo exacto, ellos verían el nuevo elemento en las lista con un puntero next válido, o no verían la lista todavía. Aún se requiere un bloqueo contra otras CPUs insertando o borrando de la lista, por supuesto.

Por supuesto, las escrituras deben estar en este orden, en otro caso el nuevo elemento aparece en la lista con un puntero next inválido, y alguna otra CPU iterando en el tiempo equivocado saltará a través de él a la basura. Porque las modernas CPUs reordenan, el código de Alan actualmente se lee como sigue:

        new->next = i->next;
        wmb();
        i->next = new;

La función wmb() es una barrera de escritura de memoria (include/asm/system.h): ni el compilador ni la CPU permitirán alguna escritura a memoria después de que wmb() sea visible a otro hardware antes de que alguna otra escritura se encuentre antes de wmb().

Como i386 no realiza reordenamiento de escritura, este bug nunca fue mostrada en esta plataforma. Es otras plataformas SMP, de cualquier forma, si que fue mostrado.

También hay rmb() para ordenamiento de lectura: para asegurar que cualquier lectura previa de una variable ocurre antes de la siguiente lectura. La macro simple mb() combina rmb() y wmb().

Algunas operaciones atómicas están definidas para actuar como una barrera de memoria (esto es, como la macro mb(), pero si dudas, se explícito. También, las operaciones de spinlock actuan como barreras parciales: las operaciones después de obtener un spinlock nunca serán movidas para preceder a la llamada spin_lock(), y las operaciones antes de liberar un spinlock nunca serán movidas después de la llamada spin_unlock().

4.6. Eliminando los Bloqueos: Operaciones Atómicas

Hay un número de operaciones atómicas definidas en include/asm/atomic.h: estas están garantizadas que serán atómicas para todas las CPUs en el sistema, entonces eliminando las carreras. Si tus datos compartidos consisten, digamos, en un simple contador, estas operaciones quizás sean más simples que usar spinlocks (aunque para algo no trivial el uso de spinlocks es más claro).

Destacar que las operaciones atómicas están definidas para actuar como barreras de escritura y lectura en todas las plataformas.

4.7. Protegiendo Una Colección de Objetos: Cuentas de Referencia

Bloqueando una colección de objetos es bastante fácil: coges un spinlock simple, y te aseguras de obtenerlo antes de buscar, añadir o borrar un objeto.

El propósito de este bloqueo no es proteger los objetos individuales: quizás tengas un bloqueo separado dentro de cada uno de ellos. Es para proteger la estructura de datos conteniendo el objeto de las condiciones de carrera. Frecuentemente el mismo bloqueo es usado también para proteger los contenidos de todos los objetos, por simplicidad, pero ellos son inherentemente ortogonales (y muchas otras grandes palabras diseñadas para confundir).

Cambiando esto a un bloqueo de lectura-escritura frecuentemente ayudará notablemente si las lecturas son más frecuentes que las escrituras. Si no, hay otra aproximación que puedes usar para reducir el tiempo que es mantenido el bloqueo: las cuentas de referencia.

En esta aproximación, un objeto tiene un dueño, quien establece la cuenta de referencia a uno. Cuando obtienes un puntero al objeto, incrementas la cuenta de referencia (una operación 'obtener'). Cuando abandonas un puntero, decrementas la cuenta de referencia (una operación 'poner'). Cuando el dueño quiere destruirlo, lo marca como muerto y hace una operación poner.

Cualquiera que ponga la cuenta de referencia a cero (usualmente implementado con atomic_dec_and_test()) limpia y libera el objeto.

Esto significa que se garantiza que el objeto no se desvanecerá debajo de ti, incluso aunque no tengas más un bloqueo para la colección.

Aquí hay algún código esqueleto:

        void create_foo(struct foo *x)
        {
                atomic_set(&x->use, 1);
                spin_lock_bh(&list_lock);
                ... inserta en la lista ...
                spin_unlock_bh(&list_lock);
        }

        struct foo *get_foo(int desc)
        {
                struct foo *ret;

                spin_lock_bh(&list_lock);
                ... encuentra en la lista ...
                if (ret) atomic_inc(&ret->use);
                spin_unlock_bh(&list_lock);

                return ret;
        }

        void put_foo(struct foo *x)
        {
                if (atomic_dec_and_test(&x->use))
                        kfree(foo);
        }

        void destroy_foo(struct foo *x)
        {
                spin_lock_bh(&list_lock);
                ... borra de la lista ...
                spin_unlock_bh(&list_lock);

                put_foo(x);
        }
    

4.8. Cosas Que Duermen

Nunca puedes llamar a las siguientes rutinas mientras estás manteniendo un spinlock, porque ellas quizás se vayan a dormir. Esto también significa que necesitas estar en el contexto de usuario.

• Accesos a userspace:

  • copy_from_user()

  • copy_to_user()

  • get_user()

  • put_user()

• kmalloc(GFP_KERNEL)

• down_interruptible() y down()

  Hay una función down_trylock() que puede ser usada dentro del contexto de interrupción, ya que no dormirá. up() tampoco dormirá.

printk() puede ser llamada en cualquier contexto, suficientemente interesante.

4.9. La Follonera Sparc

Alan Cox dice "la deshabilitación/habilitación de una sparc es en la ventana registrada". Andi Kleen dice "cuando restore_flags (restauras las banderas) en una función diferente ensucias todas las ventanas de registros".

Por lo tanto nunca pases el conjunto de palabras de flags por spin_lock_irqsave() y hermanos a otra función (a menos que sea declarada inline). Usualmente nadie hace esto, pero ahora ya estás advertido. Dave Miller nunca puede hacer nada de una forma directa (Puedo decir esto porque tengo fotos de él y de cierto defensor de PowerPC en una posición comprometida).

4.10. Cronómetros de Carreras: Un Pasatiempo del Núcleo

Los cronómetros pueden producir sus propios problemas con las carreras. Considera una colección de objeros (listas, hash, etc) donde cada objeto tiene un cronómetro que lo va a destruir.

Si quieres destruir la colección entera (digamos en el borrado de un módulo), quizás realices lo siguiente:

        /* ESTE CÓDIGO ES MALO MALO MALO MALO: SI HUBIERA ALGO PEOR
           USUARÍA NOTACIÓN HÚNGARA */
        spin_lock_bh(&list_lock);

        while (list) {
                struct foo *next = list->next;
                del_timer(&list->timer);
                kfree(list);
                list = next;
        }

        spin_unlock_bh(&list_lock);
    

Tarde o temprano, esto rompería en SMP, porque un cronómetro puede acabar antes que spin_lock_bh(), y sólo obtendría el bloqueo después de spin_unlock_bh(), y entonces intentaría liberar el elemento (¡el cual ya ha sido liberado!).

Esto puede ser eliminado comprobando el resultado de del_timer(): si retorna 1, el cronómetro ha sido borrado. Si 0, significa (en este caso) que está actualmente ejecutándose, por lo tanto lo que podemos hacer es:

        retry:  
                spin_lock_bh(&list_lock);

                while (list) {
                        struct foo *next = list->next;
                        if (!del_timer(&list->timer)) {
                                /* Le da al cronómetro una oportunidad para borrarlo */
                                spin_unlock_bh(&list_lock);
                                goto retry;
                        }
                        kfree(list);
                        list = next;
                }

                spin_unlock_bh(&list_lock);
    

Otro problema común es el borrando de cronómetros que se reinician a ellos mismos (llamando a add_timer() al final de su función cronómetro). Porque este es un caso bastante común que es propenso a carreras, puedes poner una llamada a timer_exit() muy al funal de tu función cronómetro, y usar del_timer_sync() para manejar este caso. Él retorna el número de veces que el cronómetro tuvo que ser borrado antes de que finalmente lo paráramos añadiéndolo otra vez.