Dentro del núcleo Linux 2.4 - Mecanismos IPC (I)

Este capítulo describe los mecanismos IPC semáforo, memoria compartida y cola de mensajes tal como han sido implementados en el núcleo Linux 2.4. Está organizado en 4 secciones. Las tres primeras secciones cubren las interfaces y las funciones de soporte para semaphores∞, message queues∞, y shared memory∞ respectivamente. La sección last∞ describe un conjunto de funciones comunes y estructuras de datos que son compartidas por los tres mecanismos.

Semáforos∞

Las funciones descritas en esta sección implementan el nivel de usuario de los mecanismos de los semáforos. Nótese que esta implementación ayuda en el uso de los spinlocks y semáforos del núcleo. Para eliminar esta confusión el término "semáforo del núcleo" será usado en referencia a los semáforos del núcleo. Todos los otros usos de la palabra "semáforo" será una referencia a los semáforos del nivel de usuario.

Interfaces de la Llamada al sistema de los Semáforos

sys_semget()

La llamada entera a sys_semget() es protegida por el semáforo global del núcleo sem_ids.sem∞

En el caso donde un nuevo conjunto de semáforos deben de ser creados, la función newary()∞ es llamada para crear e inicializar un nuevo conjunto de semáforos. La ID del nuevo conjunto es retornada al llamante.

En el caso donde un valor de llave es suministrado por un conjunto de semáforos existentes, ipc_findkey()∞ es llamado para buscar el correspondiente descriptor del semáforo en el índice de la matriz. Los parámetros y los permisos del llamante son verificados antes de devolver la ID del conjunto de semáforos.

sys_semctl()

Para los comandos IPC_INFO∞, SEM_INFO∞, y SEM_STAT∞, semctl_nolock()∞ es llamado para realizar las funciones necesarias.

Para los comandos GETALL∞, GETVAL∞, GETPID∞, GETNCNT∞, GETZCNT∞, IPC_STAT∞, SETVAL∞, y SETALL∞, semctl_main()∞ es llamado para realizar las funciones necesarias.

Para los comandos IPC_RMID∞ y IPC_SET∞, semctl_down()∞ es llamada para realizar las funciones necesarias. Durante todas estas operaciones, es mantenido el semáforo global del núcleo sem_ids.sem∞.

sys_semop()

Después de validar los parámetros de la llamada, los datos de las operaciones de los semáforos son copiados desde el espacio de usuario a una antememoria temporal. Si una pequeña antememoria temporal es suficiente, entonces es usada una antememoria de pila. En otro caso, es asignad una antememoria más grande. Después de copiar los datos de las operaciones de los semáforos, el spinlock global de los semáforos es cerrado, y la ID del conjunto de semáforos especificado por el usuario es validado. Los permisos de acceso para el conjunto de semáforos también son validados.

Todas las operaciones de los semáforos especificadas por el usuario son analizadas. Durante este proceso, es mantenida una cuenta para todas las operaciones que tienen la bandera SEM_UNDO establecida. Una bandera decrease es establecida si alguna de las operaciones quitan de un valor del semáforo, y una bandera alter es establecida si alguno de los valores de los semáforos es modificado (esto es, incrementados o decrementados). El número de cada semáforos a ser modificado es validado.

Si SEM_UNDO estaba asertado para alguna de las operaciones del semáforo, entonces la lista para deshacer la actual tarea es buscada por una estructura deshacer asociada con este conjunto de semáforos. Durante esta búsqueda, si la ID del conjunto de semáforos de alguna de las estructuras deshacer es encontrada será -1, entonces freeundos()∞ es llamada para liberar la estructura deshacer y quitarla de la lista. Si no se encuentra ninguna estructura deshacer para este conjunto de semáforos entonces alloc_undo()∞ es llamada para asignar e inicializar una.

La función try_atomic_semop()∞ es llamada con el parámetro do_undo igual a 0 en orden de ejecutar la secuencia de operaciones. El valor de retorno indica si ambas operaciones han tenido éxito, han sido fallidas, o que no han sido ejecutadas porque necesitaban bloquear. Cada uno de estos casos son más ampliamente descritos a continuación:

Operaciones de semáforos no bloqueantes

La función try_atomic_semop()∞ devuelve cero para indicar que todas las operaciones en la secuencia han sido realizadas con éxito. Es este caso, update_queue()∞ es llamada para recorrer la cola de las operaciones pendientes del semáforo para el conjunto del semáforo y despertar cualquier tarea dormida que no necesite bloquear más. Esto completa la ejecución de la llamada al sistema sys_semop() para este caso.

Operaciones de Semáforo con fallos

Si try_atomic_semop()∞ devuelve un valor negativo, entonces ha sido encontrada una condición de fallo. En este caso, ninguna de las operaciones han sido ejecutadas. Esto ocurre cuando una operación de un semáforo causaría un valor inválido del semáforo, o un operación marcada como IPC_NOWAIT es incapaz de completarse. La condición de error es retornada al llamante de sys_semop().

Antes de que sys_semop() retorne, es hecha una llamada a update_queue()∞ para recorrer la cola de operaciones pendientes del semáforo para el conjunto del semáforo y despierta cualquier tarea dormida que no necesite más bloqueos.

Operaciones de Semáforo bloqueantes

La función try_atomic_semop()∞ devuelve un 1 para indicar que la secuencia de operaciones del semáforo no fue ejecutada porque uno de los semáforos bloquearía. Para este caso, un nuevo elemento sem_queue∞ es inicializado conteniendo estas operaciones del semáforo. Si alguna de estas operaciones afectaran al estado del semáforo, entonces un nuevo elemento de cola es añadido al final de la cola. En otro caso, el nuevo elemento es añadido al principio de la cola.

El elemento semsleeping de la tarea actual está establecido para indicar que la tarea está durmiendo en este elemento sem_queue∞. La tarea actual es marcada como TASK_INTERRUPTIBLE, y el elemento sleeper del sem_queue∞ es establecido para identificar esta tarea por el durmiente. El spinlock global del semáforo es entonces desbloqueado, y schedule() es llamado para poner la tarea actual a dormir.

Cuando es despertada, la tarea vuelve a cerrar el spinlock global del semáforo, determina por qué fue despertada, y cómo debería de responder. Los siguientes casos son manejados:

• Si el conjunto de semáforos ha sido borrado, entonces la llamada al sistema falla con EIDRM.
• Si el elemento status de la estructura sem_queue∞ está establecido a 1, entonces la tarea es despertada en orden a reintentar las operaciones del semáforo, Otra llamada a try_atomic_semop()∞ es realizada para ejecutar la secuencia de las operaciones del semáforo. Si try_atomic_sweep() devuelve 1, entonces la tarea debe de bloquearse otra vez como se describió anteriormente. En otro caso, se devuelve 0 en caso de éxito, o un código de error apropiado en caso de fallo. Antes de que sys_semop() regrese, current->semsleeping es limpiado, y sem_queue∞ es borrado de la cola. Si alguna de las operaciones del semáforo especificada eran operaciones alteradoras (incremento o decremento), entonces update_queue()∞ es llamado para recorrer la cola de operaciones pendientes del semáforo para el conjunto del semáforo y despertar cualquier tarea dormida que no necesite bloquear más.
• Si el elemento status de la estructura sem_queue∞ NO está establecida a 1, y el elemento sem_queue∞ no ha sido quitado de la cola, entonces la tarea ha sido despertada por una interrupción. Es este caso, la llamada al sistema falla con EINTR. Antes de regresar, current->semsleeping es limpiado, y sem_queue∞ es borrado de la cola. También update_queue()∞ es llamado si alguna de las operaciones eran operaciones alterantes.
• Si el elemento status de la estructura sem_queue∞ NO está establecido a 1, y el elemento sem_queue∞ ha sido quitado de la cola, entonces las operaciones del semáforo ya han sido ejecutadas por update_queue()∞. La cola status, la cual será 0 si se tiene éxito o un código negativo de error en caso de fallo, se convertirá en el valor de retorno de la llamada al sistema.

Estructuras Específicas de Soporte de Semáforos

Las siguientes estructuras son usadas específicamente para el soporte de semáforos:

struct sem_array

---

/* Una estructura de datos sem_array para cada conjunto de semáforos en el sistema. */
struct sem_array {
struct kern_ipc_perm sem_perm; /* permisos .. ver ipc.h */
time_t sem_otime; /* último tiempo de la operación con el semáforo */
time_t sem_ctime; /* último tiempo de cambio */
struct sem *sem_base; /* puntero al primer semáforo en el array */
struct sem_queue *sem_pending; /* operaciones pendientes para ser procesadas */
struct sem_queue sem_pending_last; /* última operación pendiente */
struct sem_undo *undo; /* peticiones deshechas en este array * /
unsigned long sem_nsems; /* número de semáforos en el array */
};

---

struct sem

---

/* Una estructura de semáforo para cada semáforo en el sistema. */
struct sem {
int semval; /* valor actual */
int sempid; /* pid de la última operación */
};

---

struct seminfo

---

struct seminfo {
int semmap;
int semmni;
int semmns;
int semmnu;
int semmsl;
int semopm;
int semume;
int semusz;
int semvmx;
int semaem;
};

---

struct semid64_ds

---

struct semid64_ds {
struct ipc64_perm sem_perm; /* permisos.. ver ipc.h */
kernel_time_t sem_otime; /* último tiempo de operación con el semáforo */
unsigned long unused1;
kernel_time_t sem_ctime; /* último tiempo de cambio */
unsigned long unused2;
unsigned long sem_nsems; /* número de semáforos en la matriz */
unsigned long unused3;
unsigned long unused4;
};

---

struct sem_queue

---

/* Una cola para cada proceso durmiendo en el sistema. */
struct sem_queue {
struct sem_queue * next; /* siguiente entrada en la cola */
struct sem_queue prev; /* entrada anterior en la cola, *(q->prev)

q */ struct task_struct* sleeper; /* este proceso */
struct sem_undo * undo; /* estructura deshacer */
int pid; /* id del proceso del proceso pedido */
int status; /* status de terminación de la operación */
struct sem_array * sma; /* matriz de semáforos para las operaciones */
int id; /* id interna del semáforo */
struct sembuf * sops; /* matriz de operaciones pendientes*/
int nsops; /* número de operaciones */
int alter; /* operaciones que alterarán el semáforo */
};

---

struct sembuf

---

/* las llamadas al sistema cogen una matriz de estas. */
struct sembuf {
unsigned short sem_num; /* indice del semáforo en la matriz */
short sem_op; /* operación del semáforo */
short sem_flg; /* banderas de la operación */
};

---

struct sem_undo

---

/* Cada tarea tiene una lista de peticiones de deshacer. Ellas son
* ejecutadas cuando el proceso sale.
*/
struct sem_undo {
struct sem_undo * proc_next; /* siguiente entrada en este proceso */
struct sem_undo * id_next; /* siguiente entrada en
este conjunto de semáforos */
int semid; /* identificador del
conjunto de semáforos */
short * semadj; /* matriz de ajustes, una
por semáforo */

};

---

Funciones de Soporte de Semáforos

Las siguientes funciones son usadas específicamente para soportar los semáforos:

newary()

newary() confía en la función ipc_alloc()∞ para asignar la memoria requerida para el nuevo conjunto de semáforos. El asigna suficiente memoria para el conjunto de descriptores del semáforo y para cada uno de los semáforos en el conjunto. La memoria asignada es limpiada, y la dirección del primer elemento del conjunto de descriptores del semáforo es pasada a ipc_addid()∞. ipc_addid()∞ reserva una entrada de la matriz para el conjunto de descriptores del semáforo e inicializa los datos ( struct kern_ipc_perm∞) para el conjunto. La variavle global used_sems es actualizada por el número de semáforos en el nuevo conjunto y la inicialización de los datos ( struct kern_ipc_perm∞) para el nuevo conjunto es completada. Otras inicializaciones realizadas para este conjunto son listadas a continuación:

• El elemento sem_base para el conjunto es inicializado a la dirección inmediatamente siguiente siguiendo la porción ( struct sem_array∞) de los nuevos segmentos asignados. Esto corresponde a la localización del primer semáforon en el conjunto.
• La cola sem_pending es inicializada como vacía.

Todas las operaciones siguiendo la llamada a ipc_addid()∞ son realizadas mientras se mantiene el spinlock global de los semáforos. Después de desbloquear el spinlock global de los semáforos, newary() llama a ipc_buildid()∞ (a través de sem_buildid()). Esta función usa el índice del conjunto de descriptores del semáforo para crear una única ID, que es entonces devuelta al llamador de newary().

freeary()

freeary() es llamada por semctl_down()∞ para realizar las funciones listadas a continuación. Es llamada con el spinlock global de los semáforos bloqueado y regresa con el spinlock desbloqueado.

• La función ipc_rmid()∞ es llamada (a través del envoltorio sem_rmid()) para borrar la ID del conjunto de semáforos y para recuperar un puntero al conjunto de semáforos.
• La lista de deshacer para el conjunto de semáforos es invalidada.
• Todos los procesos pendientes son despertados y son obligados a fallar con EIDRM.
• EL número de semáforos usados es reducido con el número de semáforos en el conjunto borrado.
• La memoria asociada con el conjunto de semáforos es liberada.

semctl_down()

semctcl_down() suministra las operaciones IPC_RMID∞ y IPC_SET∞ de la llamada al sistema semctl(). La ID del conjunto de semáforos y los permisos de acceso son verificadas en ambas operaciones, y en ambos casos, el spinlock global del semáforo es mantenido a lo largo de la operación.

IPC_RMID

La operación IPC_RMID llama a freeary()∞ para borrar el conjunto del semáforo.

IPC_SET

La operación IPC_SET actualiza los elementos uid, gid, mode, y ctime del conjunto de semáforos.

semctl_nolock()

semctl_nolock() es llamada por sys_semctl()∞ para realizar las operaciones IPC_INFO, SEM_INFO y SEM_STAT.

IPC_INFO y SEM_INFO

IPC_INFO y SEM_INFO causan una antememoria temporal seminfo∞ para que sea inicializada y cargada con los datos estadísticos sin cambiar del semáforo, los elementos semusz y semaem de la estructura seminfo∞ son actualizados de acuerdo con el comando dado (IPC_INFO o SEM_INFO). El valor de retorno de las llamadas al sistema es establecido al conjunto máximo de IDs del conjunto de semáforos.

SEM_STAT

SEM_STAT causa la inicialización de la antememoria temporal semid64_ds∞. El spinlock global del semáforo es entonces mantenido mientras se copian los valores sem_otime, sem_ctime, y sem_nsems en la antememoria. Estos datos son entonces copiados al espacio de usuario.

semctl_main()

semctl_main() es llamado por sys_semctl()∞ para realizar muchas de las funciones soportadas, tal como se describe en la sección posterior. Anteriormente a realizar alguna de las siguientes operaciones, semctl_main() cierra el spinlock global del semáforo y valida la ID del conjunto de semáforos y los permisos. El spinlock es liberado antes de retornar.

GETALL

La operación GETALL carga los actuales valores del semáforo en una antememoria temporal del núcleo y entonces los copia fuera del espacio de usuario. La pequeña pila de antememoria es usada si el conjunto del semáforo es pequeño. En otro caso, el spinlock es temporalmente deshechado en orden de asignar una antememoria más grande. El spinlock es mantenido mientras se copian los valores del semáforo en la antememoria temporal.

SETALL

La operación SETALL copia los valores del semáforo desde el espacio de usuario en una antememoria temporal, y entonces en el conjunto del semáforo. El spinlock es quitado mientras se copian los valores desde el espacio de usuario a la antememoria temporal, y mientras se verifican valores razonables. Si el conjunto del semáforo es pequeño, entonces una pila de antememoria es usada, en otro caso una antememoria más grande es asignado. El spinlock es recuperado y mantenido mientras las siguientes operaciones son realizadas en el conjunto del semáforo:

• Los valores del semáforo son copiados en el conjunto del semáforo.
• Los ajustes del semáforon de la cola de deshacer para el conjunto del semáforo son limpiados.
• El valor sem_ctime para el conjunto de semáforos es establecido.
• La función update_queue()∞ es llamada para recorrer la cola de semops (operaciones del semáforo) pendientes y mirar por alguna tarea que pueda ser completada como un resultado de la operación SETALL. Cualquier tarea pendiente que no sea más bloqueada es despertada.

IPC_STAT

En la operación IPC_STAT, los valores sem_otime, sem_ctime, y sem_nsems son copiados en una pila de antememoria. Los datos son entonces copiados al espacio de usuario después de tirar con el spinlock.

GETVAL

Para GETVALL en el caso de no error, el valor de retorno para la llamada al sistema es establecido al valor del semáforo especificado.

GETPID

Para GETPID en el caso de no error, el valor de retorno para la llamada al sistema es establecido al pid asociado con las última operación del semáforo.

GETNCNT

Para GETNCNT en el caso de no error, el valor de retorno para la llamada al sistema de establecido al número de procesos esperando en el semáforo siendo menor que cero. Este número es calculado por la función count_semncnt()∞.

GETZCNT

Para GETZCNT en la caso de no error, el valor de retorno para la llamada al sistema es establecido al número de procesos esperando en el semáforo estando establecido a cero. Este número es calculado por la función count_semzcnt()∞.

SETVAL

Después de validar el nuevo valor del semáforo, las siguientes funciones son realizadas:

• La cola de deshacer es buscada para cualquier ajuste en este semáforo. Cualquier ajuste que sea encontrado es reinicializado a cero.
• El valor del semáforo es establecido al valor suministrado.
• El valor del semáforo sem_ctime para el conjunto del semáforo es actualizado.
• La función update_queue()∞ es llamada para recorrer la cola de semops (operaciones del semáforo) pendientes y buscar a cualquier tarea que pueda ser completada como resultado de la operación SETALL∞. Cualquier tarea que no vaya a ser más bloqueada es despertada.

count_semncnt()

count_semncnt() cuenta el número de tareas esperando por el valor del semáforo para que sea menor que cero.

count_semzcnt()

count_semzcnt() cuenta el número de tareas esperando por el valor del semáforo para que sea cero.

update_queue()

update_queue() recorre la cola de semops pendientes para un conjunto de un semáforo y llama a try_atomic_semop()∞ para determinar qué secuencias de las operaciones de los semáforos serán realizadas. Si el estado de la cola de elementos indica que las tareas bloqueadas ya han sido despertadas, entonces la cola de elementos es pasada por alto. Para los otros elementos de la cola, la bandera q-alter es pasada como el parámetro deshacer a try_atomic_semop()∞, indicando que cualquier operación alterante debería de ser deshecha antes de retornar.

Si la secuencia de operaciones bloquearan, entonces update_queue() retornará sin hacer ningún cambio.

Una secuencia de operaciones puede fallar si una de las operaciones de los semáforos puede causar un valor inválido del semáforo, o una operación marcada como IPC_NOWAIT es incapaz de completarse. En este caso, la tarea que es bloqueada en la secuencia de las operaciones del semáforo es despertada, y la cola de status es establecida con un código de error apropiado. El elemento de la cola es también quitado de la cola.

Si la secuencia de las operaciones no es alterante, entonces ellas deberían de pasar un valor cero como parámetro deshacer a try_atomic_semop()∞. Si estas operaciones tienen éxito, entonces son consideradas completas y son borradas de la cola. La tarea bloqueada es despertada, y el elemento de la cola status es establecido para indicar el éxito.

Si la secuencia de las operaciones pueden alterar los valores del semáforo, pero puede tener éxito, entonces las tareas durmiendo que no necesiten ser más bloqueadas tienen que ser despertadas. La cola status es establecida a 1 para indicar que la tarea bloqueada ha sido despertada. Las operaciones no han sido realizadas, por lo tanto el elemento de la cola no es quitado de la cola. Las operaciones del semáforo serán ejecutadas por la tarea despertada.

try_atomic_semop()

try_atomic_semop() es llamada por sys_semop()∞ y update_queue()∞ para determinar si una secuencia de operaciones del semáforo tendrán éxito. El determina esto intentando realizar cada una de las operaciones.

Si una operación bloqueante es encontrada, entonces el proceso es abortado y todas los operaciones son deshechas. -EAGAIN es devuelto si IPC_NOWAIT es establecido. En otro caso, es devuelto 1 para indicar que la secuencia de las operaciones del semáforo está bloqueada.

Si un valor del semáforo es ajustado más alla de los límites del sistema, entonces todas las operaciones son deshechas, y -ERANGE es retornado.

Si todas las operaciones de la secuencia tienen éxito, y el parámetro do_undo no es cero, entonces todas las operaciones son deshechas, y 0 es devuelto. Si el parámetro do_undo es cero, entonces todas las operaciones tienen éxito y continúan obligadas, y el sem_otime, campo del conjunto de semáforos es actualizado.

sem_revalidate()

sem_revalidate() es llamado cuando el spinlock global del semáforo ha sido temporalmente tirado y necesita ser bloqueado otra vez. Es llamado por semctl_main()∞ y alloc_undo()∞. Valida la ID del semáforo y los permisos, y si tiene éxito retorna con el spinlock global de los semáforos bloqueado.

freeundos()

freeundos() recorre las lista de procesos por deshacer en busca de la estructura deshacer deseada. Si es encontrada, la estructura deshacer es quitada de la lista y liberada. Un puntero a la siguiente estructura deshacer en la lista de procesos es devuelta.

alloc_undo()

alloc_undo() espera ser llamada con el spinlock global de los semáforos cerrado. En el caso de un error, regresa con él desbloqueado.

El spinlock global de los semáforos es desbloqueado, y kmallock() es llamado para asignar suficiente memoria para la estructura sem_undo∞, y también para un array de uno de los valores de ajuste para cada semáforo en el conjunto. Si tiene éxito, el spinlock es recuperado con una llamada a sem_revalidate()∞.

La nueva estructura semundo es entonces inicializada, y la dirección de esta estructura es colocada en la dirección suministrada por el llamante. La nueva estructura deshacer es entonces colocada en la cabeza de la lista deshacer para la actual tarea.

sem_exit()

sem_exit() es llamada por do_exit(), y es la responsable de ejecutar todos los ajustes deshacer para la tarea saliente.

Si el actual proceso fue bloqueado en un semáforo, entonces es borrado desde la lista sem_queue∞ mientras se mantiene el spinlock global de los semáforos.

La lista deshacer para la actual tarea es entonces recorrida, y las siguientes operaciones son realizadas mientras se mantienen y liberan los spinlocks globales de los semáforos a lo largo del procesamiento de cada elemento de la lista. Las siguientes operaciones son realizadas para cada uno de los elementos deshacer:

• La estructura deshacer y la ID del conjunto del semáforo son validadas.
• La lista deshacer del correspondiente conjunto de semáforos es buscada para encontrar una referencia a la misma estructura deshacer y para quitarla de esa lista.
• Los ajustes indicadores en la estructura deshacer son aplicados al conjunto de semáforos.
• El parámetro sem_otime del conjunto de semáforos es actualizado.
• update_queue()∞ es llamado para recorrer la cola de las semops pendientes y despertar cualquier tarea durmiento que no necesite ser bloqueada como resultado de la operación deshacer.
• La estructura deshacer es liberada.

Cuando el procesamiento de la lista está completo, el valor current->semundo es limpiado.