======== List RCU ======== .. toctree:: :maxdepth: 2 :caption: Contenido: Empleo de RCU, para proteger listas enlazadas ============================================= Una de las mejores aplicaciones de RCU, consiste en la protección de la mayoría de listas enlazadas - ``struct list_head`` en ``list.h``. La ventaja de esta aproximación, es que todas las barreras de memoria, son incluidas de forma automática, en la lista de macros. Este documento describe distintas aplicaciones RCU, empezando por la que mejor se adapta. Ejemplo 1: ciclo de lectura, tomado desde fuera del bloqueo, *actualizaciones fuera de lugar*. Las mejores aplicaciones en estos casos, donde si el bloqueo de *lectura-escritura* es utilizado, el bloqueo en el ciclo de lectura, será desestimado antes de tomar una acción basada en los resultados de la búsqueda. El ejemplo más representativo, es la *tabla de ruta*. Por que la tabla de ruta, sigue el estado del *equipo* fuera de la computadora; contendrá los datos que quedaron fuera. A pesar de esto, una vez la ruta ha sido computada, no hay necesidad de mantener la tabla de ruta estática, durante la transmisión del paquete. Después de todo, es posible mantener la tabla de ruta estática, todo lo necesario, pero no será posible guardar la *Internet* externa, del cambio. Es el estado de la *Internet* externa lo que importa. En adición, las entradas de ruta son habitualmente añadidas o retiradas, en lugar de ser modificadas *in situ*. Un ejemplo exclarecedor del empleo de RCU, podrá encontrarse mediante el soporte de auditoría a la *llamada de sistema*. Por ejemplo, la implementación de un bloqueo *lectura-escritura* de ``audit_filter_task()``, podría ser como sigue: .. code-block:: c static enum audit_state audit_filter_task(struct task_struct *tsk) { struct audit_entry *e; enum audit_state state; read_lock(&auditsc_lock); /* Note: audit_netlink_sem held by caller. */ list_for_each_entry(e, &audit_tsklist, list) { if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { read_unlock(&auditsc_lock); return state; } } read_unlock(&auditsc_lock); return AUDIT_BUILD_CONTEXT; } La lista aquí, es buscada através del bloqueo, pero el bloqueo es desestimado antes del correspondiente valor de retorno. En el tiempo en que el valor es aceptado, la lista podría haber sido modificada. Esto tiene sentido, al apagar la *auditoría*; es correcto auditar ciertas *llamadas de sistema*. Significa que RCU, puede ser aplicado en el ciclo de lectura, como sigue: .. code-block:: c static enum audit_state audit_filter_task(struct task_struct *tsk) { struct audit_entry *e; enum audit_state state; rcu_read_lock(); /* Note: audit_netlink_sem held by caller. */ list_for_each_entry_rcu(e, &audit_tsklist, list) { if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { rcu_read_unlock(); return state; } } rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; } Las llamadas ``read_lock()`` y ``read_unlock()`` han sido convertidas a ``rcu_read_lock()`` y ``rcu_read_unlock()``, respectivamente, la ``list_for_each_entry()`` ha sido convertida a ``list_for_each_entry_rcu()``. La macro ``_rcu()`` de primitivas transversales, inserta la barrera de memoria en el ciclo de lectura, que es requerida en *DEC Alpha CPUs*. Los cambios en el ciclo de actualización son esclarecedores. Un bloqueo *lectura-escritura*, podría utilizarse como sigue, para el borrado de una inserción: .. code-block:: c static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; write_lock(&auditsc_lock); list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { list_del(&e->list); write_unlock(&auditsc_lock); return 0; } } write_unlock(&auditsc_lock); return -EFAULT; /* No matching rule */ } static inline int audit_add_rule(struct audit_entry *entry, struct list_head *list) { write_lock(&auditsc_lock); if (entry->rule.flags & AUDIT_PREPEND) { entry->rule.flags &= ~AUDIT_PREPEND; list_add(&entry->list, list); } else { list_add_tail(&entry->list, list); } write_unlock(&auditsc_lock); return 0; } A continuación, las equivalencias RCU para estas dos funciones: .. code-block:: c static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; /* Do not use the _rcu iterator here, since this is the only * deletion routine. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { list_del_rcu(&e->list); call_rcu(&e->rcu, audit_free_rule); return 0; } } return -EFAULT; /* No matching rule */ } static inline int audit_add_rule(struct audit_entry *entry, struct list_head *list) { if (entry->rule.flags & AUDIT_PREPEND) { entry->rule.flags &= ~AUDIT_PREPEND; list_add_rcu(&entry->list, list); } else { list_add_tail_rcu(&entry->list, list); } return 0; } Normalmente, la ``write_lock()`` y ``write_unlock()`` serán reemplazadas por ``spin_lock()`` y ``spin_unlock()``, pero en tal caso, todas la *llamadas* mantedrán ``audit_netlink_sem``, por lo que no serán necesarios bloqueos adicionales. ``auditsc_lock`` podrá, por lo tanto, ser eliminado, ya que RCU *elimina* la necesidad de que los *escritores* excluyan a *lectores*. Llamadas ``write_lock()`` serán convertidas en llamadas ``spin_lock()``. Las primitivas ``list_del()``, ``list_add()``, y ``list_add_tail()``, han sido reemplazadas por ``list_del_rcu()``, ``list_add_rcu()``, y ``list_add_tail_rcu()``. La lista manipuladora de primitivas ``_rcu()``, añade barreras de memoria necesarias, en CPUs *débilmente* ordenadas -la mayoría de ellas. La primitiva ``list_del_rcu()`` omite el puntero que “envenena”, el código de depuración asistida, que de otra forma ocasionaría a *lectores* concurrentes, un fallo espectacular. Cuando *lectores*, pueden tolerar datos excedidos y las entradas, son tanto añadidas como borradas, sin una modificación en el lugar, resulta fácil el uso de RCU. Ejemplo 2: manipulado de actualizaciones *in situ*. El código de auditoría para las llamadas de sistema, no actualiza las reglas de auditoría en su loacalización. Aunque si lo hacen, el código de bloqueo de *lector-escritor* podría ser parecido a lo siguiente. Al campo ``field_count`` únicamente le está permitido decrecer, de cualquier otra forma, los campos añadidos deberá ser definidos: .. code-block:: c static inline int audit_upd_rule(struct audit_rule *rule, struct list_head *list, __u32 newaction, __u32 newfield_count) { struct audit_entry *e; struct audit_newentry *ne; write_lock(&auditsc_lock); /* Note: audit_netlink_sem held by caller. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { e->rule.action = newaction; e->rule.file_count = newfield_count; write_unlock(&auditsc_lock); return 0; } } write_unlock(&auditsc_lock); return -EFAULT; /* No matching rule */ } La versión RCU, crea una copia, actualiza la copia. Luego reemplaza la entrada *antigua* con la entrada actualizada. La secuencia de acciones, permite lecturas concurrentes, mientras se lleva a cabo una actualización efectiva. Es lo que da nombre a RCU; *read-copy update*. El código RCU, es como sigue: .. code-block:: c static inline int audit_upd_rule(struct audit_rule *rule, struct list_head *list, __u32 newaction, __u32 newfield_count) { struct audit_entry *e; struct audit_newentry *ne; list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { ne = kmalloc(sizeof(*entry), GFP_ATOMIC); if (ne == NULL) return -ENOMEM; audit_copy_rule(&ne->rule, &e->rule); ne->rule.action = newaction; ne->rule.file_count = newfield_count; list_replace_rcu(&e->list, &ne->list); call_rcu(&e->rcu, audit_free_rule); return 0; } } return -EFAULT; /* No matching rule */ } De nueve, es asumido que la llamada mantiene ``audit_netlink_sem``. Normalmente, el bloqueo *lector-escritor*, sería convertido en un *acelerador de bloqueo*, con esta suerte de códgo. Ejemplo 3: Eliminación de datos excedidos. Los ejemplos de auditoría -arriba, toleran la excedencia de datos, como la mayoría de algoritmos, que siguen el estado externo. Por que hay *una espera*, desde el momento en que *estado externo* cambia, antes que Linux, advierta el cambio; la excedencia adicional inducida en RCU, no es ningún problema. En cualquier caso, existen muchos ejemplos donde los datos excedidos, no son tolerados. Un ejemplo en el kernel de Linux, es el Sistema V IPC. Ver la función ``ipc_lock()`` en ``/ipc/util.c``. Este código comprueba una opción de *borrado*, bajo una entrada *individual?* del acelerador de bloqueo y, si la opción *borrado*, es configurada, significa que la entrada no existe. Para que esto sea de ayuda, la función de busqueda debe retornar, manteniento el acelerador de bloqueo selectivo, como ``ipc_lock()`` de hecho lo hace. *Pregunta rápida*: ¿Por qué la función de búsqueda, necesita retornar, manteniento el acelerador de bloqueo selectivo, con la técnica de la opción de *borrado*, par que sea de ayuda? Si el módulo de auditoría de la llamada de sistema, tuviese la necesidad de rechazar los datos excedidos, para conseguirlo, debería añadir la opción *borrado* y un acelerador de bloqueo, bloqueado, a la estructura ``audit_entry`` y, modificar ``audit_filter_task()``, como sigue: .. code-block:: c static enum audit_state audit_filter_task(struct task_struct *tsk) { struct audit_entry *e; enum audit_state state; rcu_read_lock(); list_for_each_entry_rcu(e, &audit_tsklist, list) { if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { spin_lock(&e->lock); if (e->deleted) { spin_unlock(&e->lock); rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; } rcu_read_unlock(); return state; } } rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; } .. admonition:: Nota este ejemplo asume que la entradas, son añadidas y borradas, únicamente. Es necesario un mecanismo adicional, capaz de trabajar correctamente con acciones de actualización, llevadas a cabo por ``audit_upd_rule()``. Por éste motivo?, ``audit_upd_rule()`` tendría la necesidad de barreras adicionales, para asegurar que ``list_add_rcu()``, fuese realmente ejecutado antes que ``list_del_rcu()``. La función ``audit_del_rule()`` tendría que establecer la opción *borrado*, bajo el *acelerador de bloqueo*, como sigue: .. code-block:: c static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; /* Do not need to use the _rcu iterator here, since this * is the only deletion routine. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { spin_lock(&e->lock); list_del_rcu(&e->list); e->deleted = 1; spin_unlock(&e->lock); call_rcu(&e->rcu, audit_free_rule); return 0; } } return -EFAULT; /* No matching rule */ } Sumario ======= La mayoría de lecturas basadas en listas de estructura de datos, que toleran el exceso de datos excedidos, transigen con el uso de RCU. El caso más simple, es donde las entradas son tanto añadidas como borradas de la estructura de datos -o modificadas de forma atómica, en el lugar. Pero modificaciones *no atómicas*, podrán ser gestionadas por medio de una copia, actualizando la copia y, reemplazando entonces, el original con la copia. Si los datos excedidos, no pudiesen ser tolerados, entonces la opción *borrado*, podría utilizarse en conjunción con el acelerador de bloqueo por entrada, con objeto de permitir a la función de búsqueda, rechazar datos recientemente borrados. Respuesta a la *pregunta rápida* ¿Por qué la función de búsqueda, necesita retornar, manteniento el acelerador de bloqueo selectivo, con la técnica de la opción de *borrado*, par que sea de ayuda? Si la función de búsqueda, deshecha el bloqueo por entrada antes de retornar, entonces la llamada procesará los datos escedidos en cualquier caso. Si realmente es correcto procesar los datos excedidos, entonces no hay necesidad de la opción *borrado*. Si representa un problema su procesado, será necesario mantener un bloqueo por entrada, en todo el código que utilize los valores de retorno. Referencias y agradecimientos ============================= .. admonition:: n. de t. el presente documento es objeto de estudio, cualquier daño o perjudicio derivado de la **mala interpretación** del mismo, eximirá al autor de consecuencias adversas. Peligro. Seguir leyendo bajo su própia responsabilidad. Atómicas, no divisibles, que no podrán ser pausadas hasta su finalización.