@sarnold	bienvenidos al cuarto día de presentaciones de umeet :)
@sarnold	el primer conferenciante de hoy es william lee irwin, III
@wli	Para dar un trasfondo general, el "hashing" (o desmenuzado) generalizado de pid se supone que mejora el rendimiento de los algoritmos internos al núcleo de manera que escalen mejor con el número de tareas.
@sarnold	(por favor, dirijan sus preguntas y comentarios a #qc; gracias)
@wli	En general, los sistemas grandes tienden a ejecutar cosas como servidores que hacen fork o muchos servidores diferentes (posiblemente de diferentes usuarios) simultáneamente.
@wli	Casi todas las alteraciones al 2.5.x se hechas para esto tratan directamente con los problemas de complejidad computacional tradicional del análisis básico de algoritmos.
@wli	De manera que para empezar a mirar más a fondo, examinemos algo de código del 2.4.x que se ha visto que tiene problemas.
@wli	(no sólo los que tienen que ver directamente con el pidhashing, sino aquellos que implican búsquedas sobre todas las tareas)
@wli	(1) count_active_tasks()
@wli	Esto está intentando calcular la carga media.
@wli	En 2.4.x, el cuerpo de la función es:
@wli	for_each_task(p) {
@wli	if ((p->state == TASK_RUNNING ||
@wli	(p->state & TASK_UNINTERRUPTIBLE)))
@wli	nr += FIXED_1;
@wli	}
@wli	La noción es simple: contar el número de tareas que están en TASK_RUNNING o TASK_UNINTERRUPTIBLE
@wli	el código de 2.5.x hace lo mismo, pero se implementa usando un principio diferente:
@wli	"Ve contando, y cuando se te diga, devuelve el número."
@wli	<grimoire:#qc> puede parecer tonto, ¿pero cómo se define FIXED_1?
@wli	FIXED_1 es una constante que se usa para cálculos en aritmética de coma fija.
@wli	Representa al 1.
@wli	Hay un problema con esta estrategia: cambiar el estado provoca una sobrecarga en la contabilidad, pero examinar el estado es mucho menos costoso.
@wli	La nueva sobrecarga en el conteo toma la forma de incrementar y decrementar contadores y mover cosas entre listas, etc.
@wli	count_active_tasks() es bastante instrumental de otra manera: se ha comprobado que existe un problema de fiabilidad con el crecimiento de la velocidad de reloj en los servidores SMP (o al menos, he provocado el problema durante algunas pruebas).
@wli	Esto se debe a que los tic del reloj ocurren con frecuencia, pero el tiempo que se pierde en él depende del número de tareas
@wli	De manera que cuando se tarda demasiado en examinar todas las tareas, se puede experimentar lo que se llama "timeslice overrun".
@wli	Este tipo de problema no es se restringe a esta función.
@wli	(2) sys_setpgid()
@wli	Esta función no se ejercita a menudo, o al menos no se considera normalmente como de rendimiento crítico, pero su implementación en 2.4.x presenta algunas desventajas.
@wli	Si puedo detenerme un momento:
@wli	<jmgv:#qc> ¿pero cuándo actualizas el contador de tareas? supuse que cada tarea añade 1 cuando nace y resta 1 antes de morir... ¿no es así?
@wli	En general, las alteraciones sobre task-state se realizan para pasar un tipo de argumento implícito al planificador.
@wli	De manera que básicamente, el planificador incrementa y decrementa el contador de TASK_RUNNING cuando las cosas duermen o despiertan, e incrementa y decrementa un segundo contador para TASK_UNINTERRUPTIBLE cuando las cosas duermen y despiertan. En principio, se podría usar un único contador, pero se necesita contar aisladamente TASK_RUNNING.
@wli	Esto es nr_uninterruptible() y rq->nr_uninterruptible de 2.5.x
@wli	De manera que volvamos a (2)
@wli	La parte crítica a examinar en esto es:
@wli	if (pgid != pid) {
@wli	struct task_struct * tmp;
@wli	for_each_task (tmp) {
@wli	if (tmp->pgrp == pgid &&
@wli	tmp->session == current->session)
@wli	goto ok_pgid;
@wli	}
@wli	goto out;
@wli	En este punto vemos que suceden 2 comprobaciones:
@wli	(A) comprobamos si algo alguien tiene ya un ID de grupo de procesos dado.
@wli	(B) comprobamos si alguien está en la misma sesión.
@wli	Le hace pensar a uno "¿No sería bueno si hubiera otra manera de averiguarlo?"
@wli	En 2.5.x las cosas son un poco diferentes
@wli	La vieja infraestructura de 2.4.x tiene una tabla hash sólo para task-pid
@wli	En 2.5.x tenemos tablas hash para task->pid, task->tgid, task->pgrp, y task->session
@wli	El mismo código se ve ahora así:
@wli	for_each_task_pid(pgid, PIDTYPE_PGID, p, l, pid)
@wli	if (p->session == current->session)
@wli	goto ok_pgid;
@wli	<seletz:#qc> puede que sea una pregunta tonta: ¿qué contienen estas tablas hash? valor y clave, quiero decir.
@wli	bien, esta pregunta me ayudará a explicar qué es lo que sucede en ese código.
@wli	Hay una "struct pid" que representa un "id de proceso" dado
@wli	La noción de "id de proceso" es una generalización, de manera que no significa sólo PID, sino que incluye PID, PGID, TGID y SID.
@wli	La struct pid tiene en su interior una lista de todas las tareas que comparten el mismo valor para ese ID.
@wli	Por ejemplo, supongamos que hay 20 tareas en un grupo de procesos dado.
@wli	La struct pid de ese pgrp aparecerá en las listas de 'buckets' de la tabla hash, y miraremos esa estructura, avanzando por la lista que hay en su interior.
@wli	Esto debería darnos una idea de qué hay en for_each_task_pid().
@wli	#define for_each_task_pid(who, type, task, elem, pid)           \
@wli	if ((pid = find_pid(type, who)))                        \
@wli	for (elem = pid->task_list.next,                        \
@wli	prefetch(elem->next),                           \
@wli	task = pid_task(elem, type);                    \
@wli	elem != &pid->task_list;                        \
@wli	elem = elem->next, prefetch(elem->next),        \
@wli	task = pid_task(elem, type))
@wli	pid = find_pid(type, who) /* find_pid() hace búsquedas en tablas hash, y encuentra una struct pid que coincida */
@wli	específicamente, find_pid() toma como primer argumento el tipo de pid (PGID/SID/etc.), y como segundo argumento el valor.
@wli	Se usa para inicializar el bucle.
@wli	La parte del bucle examina la pid->task_list
@wli	y esencialmente es un list_for_each_entry()
@wli	Observarán que en una struct pid hay dos conjuntos de enlaces de lista:
@wli	Uno para la tabla hash y otro para la lista de tareas: esto es para ayudar la compartición.
@wli	Ahora es cuando entra en juego el principio que mencioné al respecto de la sobrecarga de cambios en contraposición a la sobrecarga de examen:
@wli	Esta tablas tienen que actualizarse al hacer fork(), exec() y exit().
@wli	Hay otra clase de efectos secundarios:
@wli	El bloqueo cambia en algunos casos (menos importantes).
@wli	sys_setpgid() es uno de estos casos.
@wli	En 2.4.x no había estructura asociada a pgrp que tuviera que ser alterada cuando cambiase, pero 2.4.x obtenía tasklist_lock al leer.
@wli	En 2.5.x la hay, de manera que se debe obtener tasklist_lock al escribir.
@wli	Este es un problema diferente: algunas operaciones son menos paralelizables ahora, pero son mucho más eficientes al hacerse en serie.
@wli	La tendencia general con estas operaciones que han sido serializadas en 2.5.x es que son operaciones "poco comunes", aquellas que no se piden con frecuencia o no se consideran de rendimiento crítico, mientras que las operaciones aque han sido aceleradas no se veían afectadas seriamente por la sobrecarga del conteo, o fueron aceleradas drásticamente, y ya se realizaban en serie.
@wli	Hay otro efecto secundario, y de hecho, se usó para promocionar esta estructura para el núcleo:
@wli	Esta contabilidad evita la notificación explícita cuando se deja de usar un pid.
@wli	A primera vista, esto no parece terriblemente importante, pero hay una operación en particular que me gustaría que conociesen.
@wli	Durante fork(), se necesita asingar a un proceso un ID unívoco. A esto se le llama "asignación de pid".
@wli	El asignador de pid de 2.4.x tiene una estrategia básica de «examina la lista de tareas y comprueba si el ID que he supuesto al principio sirve realmente».
@wli	En realidad es un algoritmo un tanto refinado, pero no muy determinista.
@wli	El asignador de 2.4.x mantiene una "ventana" de pids seguros, y mueve, y hace crecer o decrecer esta ventana según asigna pids y examina la lista de tareas.
@wli	En el "mejor" caso, esto resulta en un rendimiento de O(tareas), pero en el peor, es de O(tareas**2) (cuadrático). Y en realidad es probable que tras una secuencia de operaciones, las cosa pasa a un comportamiento medio, de tal manera que aunque a veces lleve un tiempo O(tareas**2), en general es de O(tareas).
@wli	Normalmente esto está bien, pero es más cuestionable en SMP:
@wli	el problema es que su peor caso puede ser lo suficientemente severo cuando hay suficientes tareas como para que se puedan desatar los mecanismos de detección de interbloqueo, como el 'watchdog' de NMI, al competir las cosas por intentar hacer write_lock_irq(&tasklist_lock).
@wli	El asignador de pid de 2.5.x usa las actualizaciones de la tabla de hash para ayudarse.
@wli	void detach_pid(task_t *task, enum pid_type type)
@wli	{
@wli	int nr = __detach_pid(task, type);
@wli	if (!nr)
@wli	return;
@wli	for (type = 0; type < PIDTYPE_MAX; ++type)
@wli	if (find_pid(type, nr))
@wli	return;
@wli	free_pidmap(nr);
@wli	}
@wli	El bucle for () es la parte importante aquí.
@wli	Está haciendo «para todos los tipos de ID de procesos, si podemos encontrar este número de ID en uso, vuelve sin hacer nada"
@wli	Si hay un número de ID completamente sin usar, lo marca en el mapa de bits.
@wli	Este mapa de bits tiene un lugar para cada número pid posible, y si el bit está marcado, entonces el número de ID está siendo usado, y si no, no lo está.
@wli	<sarnold:#qc> un mapa de bits de 32k para los pid?
@wli	En realidad no
@wli	El espacio de PID se ha hecho algo más grande para poder ejecutar más procesos.
@wli	El espacio máximo permisible de PID es de 4M, y su tamaño se controla mediante sysctl
@wli	En realidad hay dos niveles en el mapa:
@wli	El primero es un nivel que apunta a páginas con una cuenta de pid libres en su interior.
@wli	El segundo es una página cuyos bits se usan para llevar el rastro de los pid individuales.
@wli	<chbm:#qc> uint32
@wli	<chbm:#qc> por qué no usarlo :)
@wli	La única razón es que en general la sobrecarga de espacio de suficientes tareas para utilizar un espacio de PID tan grande lo hace impracticable, al menos en 32 bits.
@wli	En máquinas de 64 bits con mucha memoria podría ser posible un número de tareas suficiente como para utilizarlo del todo, pero no es útil debido a la sobrecarga generada.
@wli	Es lo suficientemente grande como para acomodar los números de tareas que piden las cargas de trabajo reales, lo cual normalmente no es mucho más de 100K en los casos más grandes, y como el tiempo de búsqueda es O(1) (volveré a esto en un momento), el tamaño del espacio ocupado es casi arbitrario.
@wli	Lo notarán en alloc_pidmap():
@wli	scan_more:
@wli	offset = find_next_zero_bit(map->page, BITS_PER_PAGE, offset);
@wli	if (offset >= BITS_PER_PAGE)
@wli	goto next_map;
@wli	if (test_and_set_bit(offset, map->page))
@wli	goto scan_more;
@wli	Esto significa que realmente está mirando el mapa de bits y (en teoría) tardando O(sizeof(pidspace)); en la práctica dominan los efectos de caché, y el algoritmo hace con frecuencia consultas directas a la lista de tareas, y se espera un rendimiento de O(1).
@wli	Si ocupásemos algo de espacio adicional para indizado, se podría hacer que el peor caso fuera O(1), pero cualquier ganancia sobre el caso medio sería marginal.
@wli	Direcciones para el futuro:
@wli	El resto de consulta a la lista de tareas no son tan críticas en rendimiento como las anteriores.
@wli	En el centro del núcleo, hay una operación poco común, que es establecer la prioridad de todas las tareas que pertenecen a un usuario dado, y varios caminos erróneos que buscan tareas que tengan un mm dado.
@wli	También el establecer máscaras globales de capacidades (capabilities), y enviar señales a todas las tareas.
@wli	No se consideró (bueno, yo no consideré) muy útil optimizar la búsqueda de mm para volcar un core ni el OOM killing, y la búsqueda de uid es una operación tan rara que no está muy claro que sea beneficiosa la sobrecarga de mantener los enlaces de una lista.
@wli	También puede aparecer algunos otros casos "misceláneos":
@wli	el módulo ipt_owner de netfilter comprueba la lista de tareas en busca de una tarea que tenga un task->comm coincidente
@wli	En realidad esto puede ser de rendimiento crítico en máquinas que aguanten cargas de red intensivas mientras usan ipt_owner, pero no hay suficiente infraestructura para copar esto siendo un módulo.
@wli	También hay una comprobación de mal comportamiento cuadrático de la lista de tareas en /proc, para simular la lectura del directorio raíz de /proc, donde aún no tenemos una solución aceptable.
@wli	Una cosa en la que tenemos un camino claro es la validación de tareas.
@wli	Hay un nuevo mecanismo para llevar una cuenta de referencias de estructuras de tareas que nos da algunas garantías de que una estructura de tarea siga siendo válida.
@wli	Hay varias partes del núcleo, siendo notables los driver de control de entorno vm82 y SBUS, que quieren mantener referencias a tareas, pero el único método que tienen (creo) de verificar es comparar los punteros a la tabla de estructuras en una búsqueda por la lista de tareas.
@wli	Esto no funciona realmente, porque las estructuras se reservan con slab y pueden ser reutilizadas por otras tareas.
@wli	La solución ahora es bien llevar una cuenta de referencias a la estructura de la tarea o poner un 'hook' en release_thread()
@wli	Claramente esto constituye una eliminación de fallos, de manera que no hay duda de que esta estrategia va a ser útil.
@wli	Hay una infraestructura adicional que podría potencialmente permitir a netfilter, por ejemplo, acabar con el problema de la actualización de la tabla de hash:
@wli	Esto es, registrar funciones para que sean llamadas durante fork(), exec(), exit() y otros eventos útiles relacionados con las tareas.
@wli	En este momento, no hay una gran variedad de usuarios potenciales, y dada la naturaleza poco usual de las cosas que lo necesitan, puede que nunca llegue a hacerse.
@wli	Pero tiene la posibilidad de proporcionar la infraestructura para características como el entorno ambiental de SBUS, vm86 y netfilter sean módulos y aún así sean eficientes.
@wli	<cdub:#qc> ¿aún pretendes proporcionar una función de comprobación genérica con una callback para las comparaciones?
@wli	Ahí mi intención en realidad era controlar muy estrictamente a los usuarios de tal interfaz y limitar su uso sólo a eventos catastróficos pre-aprobados de manear que se evitase la reintroducción de algoritmos de examen de la lista de tareas o código ineficiente en general; hoy día estoy trabajando menos en eso, y creo que dudo que fuera popular este tipo de control de admisión.
@wli	<cdub:#qc> y LSM tiene 'hooks' en estos puntos que podrían hacer las actualizaciones (de la misma manera, creo que podrían ayudar los 'task ornaments').
@wli	Estaba intentando conectar los 'task ornaments' para este tipo de cosas. =)
@wli	Reutilizar los 'hooks' de LSM para este tipo de eventos suena muy interesante, aunque podría ser difícil justificar poner algo como las necesidades de hacer hash de ->comm de ipt_owner en lo que se supone que es un modelo deseguridad... algo así como "renombrar el juego" (rename game) podría ser útil para tratar con este problema.
@wli	Otra dirección a seguir que tiene bastantes posibilidades de realizarse es algún método de reducir el espacio reservado de forma estática para los hash de pid.
@wli	Y algo para hacer a más largo plazo sería comparar los enfoques más deterministas de mapas de bits multinivel con el actual para determinar si el rendimiento medio durante cargas de trabajo reales se ve afectado de forma negativa por los efectos de caché al estar actualizando siempre varios niveles hasta el punto en que la ganancia en determinismo del algoritmo actual no merezca la pena.
@wli	No tengo planeado investigar esto a menos que me encuentre realmente aburrido; ha sido imposible reproducir los peores casos.
@wli	También hay que tener en cuenta que en las máquinas de 32 bits con PAE (que precisan tablas de páginas de tres niveles) las páginas de segundo nivel (pmd's) siempre están instanciadas.
@wli	Esto significa 12KB de sobrecarga por tarea.
@wli	32K tareas * 12KB == 768MB, de manera que las pmd consumen toda la memoria baja llegados a ese punto, de manera que para un grupo muy importante, el espacio de 32K es bastante.
@wli	Por último, pero no por ello menos, me gustaría dar las gracias a Ingo Molndar, cuyos arreglos de fallos, limpiezas de código y promoción de estos métodos consiguieron introducirlos en el núcleo.
@wli	Bien, gracias a todos los que asistieron y escucharon, también. =)
@sarnold	gracias wli :)
@sarnold	gracias también a gareoda, que tradujo a holandés en #taee...
@sarnold	vizard traducirá esto a español más tarde, para el sitio web...
nota de traducción: al final, vizard no tuvo tiempo :P

Generated by irclog2html.pl by Jeff Waugh - find it at freshmeat.net!