memory - ¿Cómo se determina el uso máximo de la pila?

embedded stack

Question

¿Qué métodos están disponibles para determinar el tamaño de pila óptimo para el sistema incrustado / memoria limitada? Si es demasiado grande, se desperdicia memoria que podría usarse en otro lugar. Sin embargo, si es demasiado pequeño, obtendremos el nombre de este sitio web ...

Para intentar poner en marcha las cosas: Jack Ganssle afirma en The Art of Designing Embedded Systems que, "Con la experiencia, uno aprende la manera estándar y científica de calcular el tamaño adecuado para una pila: elija un tamaño al azar y espere". ¿Alguien puede hacer algo mejor que eso?

Se solicitó un ejemplo más específico. Entonces, ¿qué tal un programa C dirigido a una MCU MSP430 con 2 kB de RAM utilizando la cadena de herramientas IAR Embedded Workbench sin un sistema operativo? Este IDE puede mostrar el contenido y uso de la pila al usar un depurador JTAG.

Answer 1

Con una buena herramienta de análisis estático de código fuente, puede generar un gráfico de llamadas para su aplicación. Dado eso, y las estimaciones de la cantidad de locales / temporales producidos por su compilador, puede calcular directamente una estimación conservadora de la demanda de la pila.

Lo que quiero decir con una herramienta de análisis "buena" es aquella que puede leer todas las unidades de compilación involucradas, puede determinar llamadas de función directa, puede determinar punteros indirectos, en la unidad de compilación, puede calcular un análisis conservador de puntos en todo el sistema, puede construir un gráfico de llamadas teniendo en cuenta el análisis de puntos a. Esto elimina muchas herramientas, por lo que uno ve métodos ad hoc como "llenar la pila en tiempo de ejecución y ver qué pasa". También necesita estimaciones de las demandas de la pila que el compilador coloca en la pila; Puede aproximarse mucho a esto simplemente conociendo cuán grandes son las demandas de almacenamiento de todos los tipos, que generalmente es bastante fácil de determinar para los programas integrados de los sistemas C. Finalmente, debe creer que su aplicación no tiene llamadas recursivas, o que la herramienta tiene una idea de la recursión más profunda (probablemente diciéndola).

El kit de herramientas de reingeniería de software DMS cumple con todos estos requisitos para los programas C. Consulte http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html . Aún debe configurarlo para calcular la demanda de la pila rastreando el gráfico de llamadas y utilizando las diversas estimaciones de tamaño.

Si quieres una respuesta rápida, utiliza el truco de llenar pila. Si desea una respuesta que pueda volver a calcular después de cada cambio en el código fuente, necesitará el enfoque de análisis estático.

Answer 2

Estoy trabajando en este problema en este momento, es decir, el cálculo analítico de Stacksize. Claramente va a ser una pieza de código altamente recursiva, porque una llamada de función podría tener una matriz indexada como uno o más de sus argumentos y uno o más de los índices de matriz podrían involucrar llamadas de función.

Sin embargo, un par de realizaciones permiten cierto alivio de la complejidad:

(1) Cuando se utiliza un compilador de lenguaje de alto nivel, el stackpointer al final de la ejecución de cada instrucción / línea de código debe estar en el mismo lugar que estaba al inicio. (Al menos esta sería una buena regla para observar; de lo contrario, ¡tendrás problemas!)

(2) El stackpointer después de regresar de cada función o llamada de subrutina debe ser el mismo que antes de la llamada. Por lo tanto, el tamaño máximo de la pila es el máximo, en todas las declaraciones en el programa, del pico acumulado alcanzado en cada declaración. (Al menos esta sería una buena regla para observar; de lo contrario, ¡tendrás problemas!)

Por supuesto, una declaración puede incluir los problemas recursivos que mencioné anteriormente, pero al menos el problema de encontrar el requisito máximo de un paquete completo de un programa se reduce a encontrar el requisito de tamaño máximo de cada declaración, y luego elegir el máximo de esos.

Esto no puede completarse hasta que todas las funciones llamadas también hayan sido compiladas. Así que genero un archivo para cada módulo compilado que registra un número de stacksizes para cada declaración (básicamente el valor pico antes de cada llamada de función y el valor inmediatamente anterior a cada llamada de función (excluyendo cualquier adición aún desconocida al tamaño de pila causado por la función) llamada), y los nombres de las funciones involucradas. Luego, retrospectivamente, proceso estos archivos usando una rutina recursiva, una vez que todas las funciones han sido compiladas, para determinar el pico de tamaño de la pila.

Lo afortunado es que, aparte de las rutinas recursivas, el máximo requisito posible de apilamiento no depende del flujo del programa, aunque en un flujo típico (que depende de los datos) nunca se alcanzará este máximo posible.

Ejemplo: Supongamos que la función 1 llama a la función 2 y el flujo de ambos depende de un valor de datos X. Supongamos que hay un rango de X que hace que la función 1 ejecute su peor declaración, que incluye una llamada a la función 2, que no se ejecuta su peor declaración de caso para ese mismo rango de X. Dado que calculamos el máximo posible de apilamiento utilizando los peores casos tanto para la función 1 como para la función 2 simultáneamente, es posible que hayamos sobreestimado el tamaño de la pila. Al menos nos equivocamos en el lado seguro.

Me gusta dar a las rutinas de interrupción su propio stackspace en una pila de sistema operativo si lo necesitan, para que no se agreguen a los requisitos de la pila de programas, además de la dirección de retorno de la interrupción

Answer 3

Etiquetaste tu pregunta con análisis estático, pero este es un problema que es difícil de resolver a través del análisis estático. El uso de la pila depende del perfil de tiempo de ejecución del programa, especialmente si está utilizando recursion o alloca. Dado que se trata de una plataforma incrustada, supongo que también es difícil ejecutar algo así como ps o top y ver cuánta pila está usando su aplicación.

Un enfoque interesante es usar la dirección del marco de pila actual para determinar cuánta pila se usa. Puede hacerlo tomando la dirección del argumento de una función o variable local. Hazlo para la función principal y para las funciones que creas que están usando la mayor cantidad de stack. La diferencia le dirá la cantidad de pila que su aplicación requiere. Aquí hay un ejemplo (suponiendo el crecimiento habitual de pila alta a baja).

char *stack_top, stack_bottom;

int
main(int argc, char *argv[])
{
    stack_top = (char *)&argc;
    // ...
    printf("Stack usage: %d/n", stack_top - stack_bottom);
}

void
deeply_nested_function(void)
{
    int a;
    stack_bottom = (char *)&a;
    // ...
}

Si su compilador le permite especificar un prólogo de función personalizado (muchos lo hacen para permitir el perfilado de programas basado en gráficos), puede incluso organizar que todas las funciones llamen a dicho código de medición. Entonces su función de medición se convierte en algo así como

void
stack_measurement_function(void)
{
    int a;
    stack_bottom = min(stack_bottom, (char *)&a);
    // ...
}

Usé un enfoque similar al que describí para generar estos gráficos .

Answer 4

La forma más común de determinar el uso más profundo de la pila es inicializar la memoria de la pila con algún valor conocido pero inusual, luego periódicamente (o al final de una prueba grande) ver dónde se detiene ese patrón.

Esto es exactamente cómo el IAR IDE determina la cantidad de pila utilizada.

Answer 5

• No use algoritmos recursivos o recurrentes alguna vez . (cuidado con las bibliotecas regex)
• No use matrices, siempre use malloc ().
• No use alloca (), algunos compiladores incluso tienen errores en esta función.

Luego, examine a mano la parte del código, buscando dónde es probable que el uso de la pila sea el más alto (recuerde que dije que no había arreglos)

• Compruebe el uso de la pila en el punto alto sospechado en el código en sí, inicie sesión en la interfaz del depurador.
• Coloque un límite basado en el uso estimado de la pila con ese límite en su lugar. por ejemplo, limitar las conexiones del servidor.