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.