Estimación del tamaño de pila

Question

En el software integrado de subprocesos múltiples (escrito en C o C++), un subproceso debe tener suficiente espacio de pila para permitirle completar sus operaciones sin desbordamiento. El tamaño correcto de la pila es crítico en algunos entornos integrados en tiempo real, porque (al menos en algunos sistemas con los que he trabajado), el sistema operativo NO detectará esto por usted.

Por lo general, el tamaño de pila para un nuevo subproceso (que no sea el principal) se designa en el momento en que se crea el subproceso (es decir, en un argumento para pthread_create() o similar). A menudo, estos tamaños de pila están codificados de forma rígida con valores que se sabe que son buenos en el momento en que el código fue originalmente escrito o probado.

Sin embargo, los cambios futuros en el código a menudo rompen las suposiciones en las que se basan los tamaños de pila, y un día fatídico, su subproceso entra en una de las ramas más profundas de su gráfico de llamadas y desborda la pila. abajo de todo el sistema o corrompiendo silenciosamente la memoria.

He visto personalmente este problema en el caso en que el código ejecutado en el hilo declara instancias de estructura en la pila. Cuando la estructura se aumenta para contener datos adicionales, el tamaño de la pila se infla de forma correspondiente, lo que permite potencialmente que se produzcan desbordamientos de pila. Me imagino que esto podría ser un gran problema para las bases de código establecidas donde los efectos completos de agregar campos a una estructura no se pueden conocer de inmediato (demasiados hilos/funciones para encontrar todos los lugares donde se usa esa estructura).

Dado que la respuesta habitual a las preguntas sobre el "tamaño de la pila" es "no son portátiles", supongamos que el compilador, el sistema operativo y el procesador son cantidades conocidas para esta investigación. Supongamos también que la recursión no se utiliza, por lo que no se trata de la posibilidad de un escenario de "recursión infinita".

¿Cuáles son algunas formas confiables de estimar el tamaño de pila necesario para un hilo? Preferiría métodos que están fuera de línea (análisis estático) y automáticos, pero todas las ideas son bienvenidas.

Answer 1

Tiempo de ejecución-evaluación

un método en línea es pintar la pila completa con un cierto valor, como 0xAAAA (o 0xAA, sea cual sea su anchura es). Luego puedes verificar qué tan grande ha crecido la pila al máximo en el pasado al verificar qué parte de la pintura queda intacta.

Eche un vistazo al enlace this para una explicación con la ilustración.

La ventaja es que es simple. Una desventaja es que no puede estar seguro de que el tamaño de su pila no excederá la cantidad de pilas usadas durante la prueba.

evaluación estática

Hay algunas comprobaciones estáticas y creo que incluso existe una versión hackeada gcc que trata de hacer esto. Lo único que puedo decirle es que la comprobación estática es muy difícil de hacer en el caso general.

También eche un vistazo a la pregunta this.

Answer 2

No es gratis, pero Coverity realiza un análisis estático de la pila.

Answer 3

Como se discutió en la respuesta a this question, una técnica común es inicializar la pila con un valor conocido y luego ejecutar el código por un tiempo y ver dónde se detiene el patrón.

Answer 4

Este no es un método fuera de línea, pero en el proyecto en el que estoy trabajando tenemos un comando de depuración que lee la marca de agua máxima en todas las pilas de tareas dentro de la aplicación. Esto genera una tabla del uso de la pila para cada tarea y la cantidad de espacio libre disponible. Verificar estos datos después de una ejecución de 24 horas con mucha interacción del usuario nos da cierta confianza de que las asignaciones de pila definidas son "seguras".

Esto funciona usando la técnica bien probada de llenar las pilas con un patrón conocido y suponiendo que la única manera de que esto pueda ser reescrito es mediante el uso normal de la pila, aunque si está siendo escrito por cualquier otro medio, desbordamiento de pila es la menor de tus preocupaciones!

Answer 5

Puede usar una herramienta de análisis estático como StackAnalyzer, si su objetivo cumple con los requisitos.

Answer 6

Hemos tratado de resolver este problema en un sistema integrado en mi trabajo. Se volvió loco, hay demasiados códigos (tanto nuestros propios como de terceros) para obtener una respuesta confiable. Afortunadamente, nuestro dispositivo estaba basado en Linux, por lo que recurrimos al comportamiento estándar de dar a cada hilo 2mb y permitir que el administrador de memoria virtual optimice el uso.

Nuestro único problema con esta solución era una de las herramientas de terceros realizadas con mlock en todo el espacio de la memoria (idealmente para mejorar el rendimiento). Esto provocó que todos los 2mb de pila para cada subproceso de sus subprocesos (75-150) se localizaran. Perdimos la mitad de nuestro espacio de memoria hasta que lo resolvimos y comentábamos la línea ofensiva.

Nota: El administrador de memoria virtual (vmm) de Linux asigna RAM en 4k fragmentos. Cuando un nuevo hilo solicita 2MB de espacio de direcciones para su pila, el vmm asigna páginas de memoria falsas a todas menos a la página más alta. Cuando la pila se convierte en una página falsa, el kernel detecta un error de página y cambia la página falsa por una real, (que consume otros 4k de RAM real). De esta forma, la pila de un subproceso puede crecer al tamaño que necesite (siempre que sea menor a 2mb) y el vmm se asegurará de que solo se use una cantidad mínima de memoria.

Answer 7

Si desea gastar mucho dinero, puede utilizar una herramienta comercial de análisis estático como Klocwork. Aunque Klocwork está principalmente dirigido a detectar defectos de software y vulnerabilidades de seguridad. Sin embargo, también tiene una herramienta llamada 'kwstackoverflow' que se puede usar para detectar el desbordamiento de pila dentro de una tarea o subproceso. Estoy usando el proyecto integrado en el que trabajo, y he tenido resultados positivos. No creo que ninguna herramienta como esta sea perfecta, pero creo que estas herramientas comerciales son muy buenas. La mayoría de las herramientas con las que me he encontrado luchan con los indicadores de función. También sé que muchos proveedores de compiladores como Green Hills ahora crean funcionalidades similares directamente en sus compiladores. Esta es probablemente la mejor solución porque el compilador tiene un conocimiento profundo de todos los detalles necesarios para tomar decisiones precisas sobre el tamaño de la pila.

Si tiene tiempo, estoy seguro de que puede usar un lenguaje de scripting para crear su propia herramienta de análisis de desbordamiento de pila. El script necesitaría identificar el punto de entrada de la tarea o hilo, generar un árbol completo de llamadas a funciones y luego calcular la cantidad de espacio de pila que utiliza cada función. Sospecho que probablemente haya herramientas gratuitas disponibles que pueden generar un árbol completo de llamadas de funciones, así que debería ser más fácil. Si conoce los detalles de la plataforma que genera el espacio de pila que utiliza cada función, puede ser muy fácil. Por ejemplo, la primera instrucción de ensamblaje de una función de PowerPC a menudo es la palabra de la tienda con la instrucción de actualización que ajusta el puntero de la pila en la cantidad necesaria para la función. Puede tomar el tamaño en bytes desde la primera instrucción, lo que hace que la determinación del espacio total de la pila sea relativamente fácil.

Estos tipos de análisis le darán una aproximación del límite superior del caso más desfavorable para el uso de la pila, que es exactamente lo que desea saber.Por supuesto, los expertos (como aquellos con los que trabajo) podrían quejarse de que estás asignando demasiado espacio de pila, pero son dinosaurios a los que no les importa la buena calidad de software :)

Otra posibilidad, aunque no Calcular el uso de la pila sería usar la unidad de administración de memoria (MMU) de su procesador (si tiene uno) para detectar el desbordamiento de la pila. He hecho esto en VxWorks 5.4 usando un PowerPC. La idea es simple, solo coloca una página de memoria protegida contra escritura en la parte superior de tu pila. Si se desborda, se producirá una ejecución del procesador y se le alertará rápidamente sobre el problema de desbordamiento de la pila. Por supuesto, no te dice por cuánto necesitas aumentar el tamaño de la pila, pero si eres bueno con la depuración de archivos de excepción/núcleo, al menos puedes descubrir la secuencia de llamadas que desbordó la pila. A continuación, puede utilizar esta información para aumentar el tamaño de su pila de forma adecuada.

-djhaus

Answer 8

estático (fuera de línea) comprobación de la pila no es tan difícil como parece. Lo he implementado para nuestro IDE integrado (RapidiTTy) — actualmente funciona para ARM7 (NXP LPC2xxx), Cortex-M3 (STM32 y NXP LPC17xx), x86 y nuestro FPGA interno compatible con MIPS ISA soft-core.

Esencialmente utilizamos un análisis simple del código ejecutable para determinar el uso de la pila de cada función. La asignación de stack más significativa se realiza al inicio de cada función; solo asegúrese de ver cómo se altera con diferentes niveles de optimización y, si corresponde, conjuntos de instrucciones ARM/Thumb, etc. Recuerde también que las tareas suelen tener sus propios stacks, y los ISR a menudo (pero no siempre) comparten un área de pila separada.

Una vez que tenga el uso de cada función, es bastante fácil construir un árbol de llamadas a partir del análisis sintáctico y calcular el uso máximo para cada función. Nuestro IDE genera planificadores (RTOSes finos efectivos) para usted, de modo que sabemos exactamente qué funciones se designan como 'tareas' y cuáles son ISR, por lo que podemos decir el uso del peor caso para cada área de pila.

Por supuesto, estas cifras casi siempre superan el real máximo. Piense en una función como sprintf que puede usar un lote de espacio de pila, pero varía enormemente según la cadena de formato y los parámetros que proporcione. Para estas situaciones también puede utilizar el análisis dinámico — llene la pila con un valor conocido en su inicio, luego ejecute en el depurador por un tiempo, haga una pausa y vea cuánto de cada pila todavía se llena con su valor (prueba de estilo de marca de agua alta) .

Ninguno de los dos enfoques es perfecto, pero la combinación de ambos le dará una idea bastante buena de cómo será el uso en el mundo real.

Answer 9

Además de algunas de las sugerencias ya realizadas, me gustaría señalar que a menudo en los sistemas integrados tiene que controlar el uso de la pila de forma estricta porque debe mantener el tamaño de la pila en un tamaño razonable. En cierto sentido, usar espacio de pila es como asignar memoria pero sin una forma (fácil) de determinar si su asignación fue exitosa, por lo que no controlar el uso de la pila resultará en una lucha permanente para descubrir por qué su sistema se bloquea nuevamente. . Entonces, por ejemplo, si su sistema asigna memoria para variables locales de la pila, asigne esa memoria con malloc() o, si no puede usar malloc(), escriba su propio controlador de memoria (que es una tarea bastante simple).

No-no:

void func(myMassiveStruct_t par) 
{ 
    myMassiveStruct_t tmpVar; 
} 

Sí, sí:

void func (myMassiveStruct_t *par) 
{ 
    myMassiveStruct_t *tmpVar; 
    tmpVar = (myMassiveStruct_t*) malloc (sizeof(myMassicveStruct_t)); 
} 

parece bastante obvio, pero a menudo no es - en especial cuando no se puede utilizar malloc().

Por supuesto, seguirá teniendo problemas, por lo que esto es solo algo para ayudar, pero no resuelve su problema. Sin embargo, te ayudará a estimar el tamaño de la pila en el futuro, ya que una vez que hayas encontrado un buen tamaño para tus pilas, si luego, tras algunas modificaciones al código, se queda sin espacio, puedes detectar una cantidad de errores o otros problemas (pilas de llamadas demasiado profundas para uno).

Answer 10

No estoy 100% seguro, pero creo que esto también se puede hacer. Si tiene un puerto jtag expuesto, puede conectarse a Trace32 y verificar el uso máximo de la pila. Aunque para esto, tendrás que dar un tamaño de pila arbitrario inicial bastante grande.