c# - ¿Cómo se detecta una excepción StackOverflowException?

stack-overflow infinite-loop

Question

TL; TR
Cuando hice la pregunta, asumí que StackOverflowException es un mecanismo para evitar que las aplicaciones se ejecuten infinitamente. Esto no es verdad.
No se detecta una StackOverflowException .
Se lanza cuando la pila no tiene la capacidad de asignar más memoria.

[Pregunta original:]

Esta es una pregunta general, que puede tener diferentes respuestas por lenguaje de programación.
No estoy seguro de cómo los lenguajes distintos de C # procesan un desbordamiento de pila.

Estaba pasando por excepciones hoy y seguí pensando en cómo se puede detectar una StackOverflowException . Creo que no es posible decir fe si la pila tiene 1000 llamadas de profundidad, luego lanzar la excepción. Porque quizás en algunos casos la lógica correcta sea tan profunda.

¿Cuál es la lógica detrás de la detección de un bucle infinito en mi programa?

Clase StackOverflowException :
https://msdn.microsoft.com/de-de/library/system.stackoverflowexception%28v=vs.110%29.aspx

Referencia cruzada mencionada en la documentación de la clase StackOverflowException :
https://msdn.microsoft.com/de-de/library/system.reflection.emit.opcodes.localloc(v=vs.110).aspx

Acabo de agregar la etiqueta de stack-overflow a esta pregunta, y la descripción dice que se está lanzando cuando la pila de llamadas consume demasiada memoria. ¿Eso significa que la pila de llamadas es algún tipo de ruta a la posición de ejecución actual de mi programa y si no puede almacenar más información de ruta , entonces se lanza la excepción?

Answer 1

ADVERTENCIA: Esto tiene mucho que ver con la mecánica debajo del capó, incluida la forma en que el CLR tiene que funcionar. Esto solo tendrá sentido si comienzas a estudiar la programación a nivel de ensamblaje.

Bajo el capó, las llamadas a métodos se realizan pasando el control al sitio de otro método. Para pasar argumentos y devoluciones, estos se cargan en la pila. Para saber cómo devolver el control al método de llamada, el CLR también debe implementar una pila de llamadas , que se empuja cuando se llama a un método y se abre cuando un método regresa. Esta pila le dice al método de retorno dónde devolver el control.

Dado que una computadora solo tiene una memoria finita, hay momentos en que la pila de llamadas se vuelve demasiado grande. Por lo tanto, una StackOverflowException no es la detección de un programa infinitamente recursivo o en ejecución , es la detección de que la computadora ya no puede manejar el tamaño de la pila requerida para realizar un seguimiento de dónde deben regresar sus métodos, los argumentos necesarios, retornos, variables o (más comúnmente) una combinación de los mismos. El hecho de que esta excepción ocurra durante la recursión infinita se debe a que la lógica inevitablemente abruma a la pila.

Para responder a su pregunta, si un programa tiene intencionalmente una lógica que sobrecargaría la pila, entonces sí verá una StackOverflowException . Sin embargo, esto generalmente es de miles a millones de llamadas profundas y rara vez es una preocupación real a menos que haya creado un bucle infinitamente recursivo.

Anexo: La razón por la que menciono los bucles recursivos es porque la excepción solo sucederá si sobrecarga la pila, lo que generalmente significa que está llamando a métodos que eventualmente vuelven a llamar al mismo método y aumentan la pila de llamadas. Si tiene algo que es lógicamente infinito, pero no recursivo, generalmente no verá una StackOverflowException

Answer 2

El problema con los desbordamientos de la pila no es que puedan provenir de un cálculo infinito. El problema es el agotamiento de la memoria de la pila, que es un recurso finito en los sistemas operativos e idiomas actuales.

Esta condición se detecta cuando el programa intenta acceder a una porción de memoria que está más allá de lo que está asignado a la pila. Esto resulta en una excepción.

Answer 3

La mayoría de las subpreguntas han sido suficientemente respondidas. Me gustaría aclarar la parte sobre la detección de la condición de desbordamiento de la pila, con suerte de una manera que sea más fácil de entender que la respuesta de Eric Lippert (que es correcta, por supuesto, pero innecesariamente complicada). En cambio, complicaré mi respuesta de una manera diferente, al mencionar no uno, sino dos enfoques diferentes.

Hay dos formas de detectar el desbordamiento de la pila: con código o con la ayuda de hardware.

La detección de desbordamiento de pila mediante código se usaba en los días en que las PC se ejecutaban en modo real de 16 bits y el hardware no funcionaba. Ya no se usa, pero vale la pena mencionarlo. En este escenario, especificamos un cambio de compilador que le pide al compilador que emita una pieza especial oculta de código de comprobación de pila al comienzo de cada función que escribimos. Este código simplemente lee el valor del registro del puntero de la pila y comprueba si está demasiado cerca del final de la pila; si es así, detiene nuestro programa. La pila en la arquitectura x86 aumenta hacia abajo, por lo que si el rango de direcciones de 0x80000 a 0x90000 se ha designado como la pila de nuestro programa, entonces el puntero de la pila apunta inicialmente a 0x90000 y, a medida que sigue invocando funciones anidadas, desciende hacia 0x80000. Entonces, si el código de verificación de la pila ve que el puntero de la pila está demasiado cerca de 0x80000, (digamos, en o por debajo de 0x80010), entonces se detiene.

Todo esto tiene la desventaja de a) agregar gastos generales a cada llamada de función que realizamos, yb) no poder detectar un desbordamiento de pila durante las llamadas a código externo que no se compiló con ese conmutador de compilador especial y, por lo tanto, no realiza ningún comprobación de desbordamiento de pila. En aquellos días, una excepción de era un lujo inaudito: su programa terminaría con un mensaje de error muy lacónico (casi se podría decir grosero ), o habría un bloqueo del sistema, que requeriría un reinicio.

La detección de desbordamiento de pila con la ayuda del hardware básicamente delega el trabajo a la CPU. Las CPU modernas tienen un sistema elaborado para subdividir la memoria en páginas (generalmente de 4 KB de longitud cada una) y hacer varios trucos con cada página, incluida la capacidad de tener una interrupción (en algunas arquitecturas llamada ''trampa'') emitida automáticamente cuando se accede a una página en particular . Por lo tanto, el sistema operativo configura la CPU de tal manera que se emitirá una interrupción si intenta acceder a una dirección de memoria de pila por debajo del mínimo asignado. Cuando se produce esa interrupción, la recibe el tiempo de ejecución de su idioma (en el caso de C #, el tiempo de ejecución .Net) y se traduce en una excepción de .

Esto tiene el beneficio de no tener absolutamente ningún gasto adicional. Hay una sobrecarga asociada con la administración de la página que la CPU realiza todo el tiempo, pero esto se paga de todos modos, ya que es necesario para que funcione la memoria virtual y para varias otras cosas como proteger el espacio de direcciones de memoria de un proceso de otro procesos, etc.

Answer 4

La pila es simplemente un bloque de memoria de un tamaño fijo que se asigna cuando se crea el hilo. También hay un "puntero de pila", una forma de realizar un seguimiento de la cantidad de pila que se está utilizando actualmente. Como parte de la creación de un nuevo marco de pila (cuando se llama a un método, propiedad, constructor, etc.) mueve el puntero de la pila hacia arriba por la cantidad que necesitará el nuevo marco. En ese momento verificará si ha movido el puntero de la pila más allá del final de la pila y, de ser así, arrojará un SOE.

El programa no hace nada para detectar la recursión infinita. La recursión infinita (cuando el tiempo de ejecución se ve obligado a crear un nuevo marco de pila para cada invocación) simplemente da como resultado que se realicen tantas llamadas de método como para llenar este espacio finito. Puede llenar fácilmente ese espacio finito con un número finito de llamadas a métodos anidados que consumen más espacio del que tiene la pila. (Sin embargo, esto suele ser bastante difícil de hacer; generalmente es causado por métodos que son recursivos, y no infinitamente, pero de suficiente profundidad para que la pila no pueda manejarlo).

Answer 5

Ya hay varias respuestas aquí, muchas de las cuales transmiten la esencia, y muchas de las cuales tienen errores sutiles o grandes. En lugar de tratar de explicar todo desde cero, permítanme dar algunos puntos importantes.

No estoy seguro de cómo los lenguajes distintos de C # manejan un desbordamiento de pila.

Su pregunta es "¿cómo se detecta un desbordamiento de pila?" ¿Es su pregunta sobre cómo se detecta en C # o en algún otro idioma? Si tiene una pregunta sobre otro idioma, le recomiendo crear una nueva pregunta.

Creo que no es posible decir (por ejemplo) si la pila tiene 1000 llamadas de profundidad, luego lanzar la excepción. Porque quizás en algunos casos la lógica correcta sea tan profunda.

Es absolutamente posible implementar una detección de desbordamiento de pila como esa. En la práctica, no es así como se hace, pero no hay una razón en principio por la cual el sistema no podría haber sido diseñado de esa manera.

¿Cuál es la lógica detrás de la detección de un bucle infinito en mi programa?

Se refiere a una recursión ilimitada , no a un bucle infinito .

Lo describiré a continuación.

Acabo de agregar la etiqueta de desbordamiento de pila a esta pregunta, y la descripción dice que se está lanzando cuando la pila de llamadas consume demasiada memoria. ¿Eso significa que la pila de llamadas es algún tipo de ruta a la posición de ejecución actual de mi programa y si no puede almacenar más información de ruta, entonces se lanza la excepción?

Respuesta corta: sí.

Respuesta más larga: la pila de llamadas se usa para dos propósitos.

Primero, para representar la información de activación . Es decir, los valores de las variables locales y los valores temporales cuyas vidas son iguales o más cortas que la activación actual ("llamada") de un método.

Segundo, representar la información de continuación . Es decir, cuando termine con este método, ¿qué debo hacer a continuación? Tenga en cuenta que la pila no representa "¿de dónde vengo?". La pila representa a dónde voy a continuación , y sucede que, por lo general, cuando un método regresa, regresas a donde viniste.

La pila también almacena información para continuaciones no locales, es decir, manejo de excepciones. Cuando se lanza un método, la pila de llamadas contiene datos que ayudan al tiempo de ejecución a determinar qué código, si lo hay, contiene el bloque catch correspondiente. Ese bloque de captura se convierte en la continuación , el "qué hago a continuación", del método.

Ahora, antes de continuar, noto que la pila de llamadas es una estructura de datos que se está utilizando para dos propósitos, violando el principio de responsabilidad única. No hay requisito de que se use una pila para dos propósitos, y de hecho hay algunas arquitecturas exóticas en las que hay dos pilas, una para cuadros de activación y otra para direcciones de retorno (que son la reificación de la continuación). menos vulnerable a los ataques de "aplastamiento de la pila" que pueden ocurrir en lenguajes como C.

Cuando llama a un método, la memoria se asigna en la pila para almacenar la dirección de retorno, qué hago a continuación, y el marco de activación, los locales del nuevo método. Las pilas en Windows son por defecto de tamaño fijo, por lo que si no hay suficiente espacio, suceden cosas malas.

En más detalle, ¿cómo funciona Windows fuera de la detección de pila?

Escribí la lógica de detección fuera de pila para las versiones de Windows de 32 bits de VBScript y JScript en la década de 1990; el CLR utiliza técnicas similares a las que yo usé, pero si desea conocer los detalles específicos de CLR, deberá consultar a un experto en CLR.

Consideremos solo Windows de 32 bits; Windows de 64 bits funciona de manera similar.

Por supuesto, Windows usa memoria virtual: si no comprende cómo funciona la memoria virtual, ahora sería un buen momento para aprender antes de seguir leyendo. A cada proceso se le asigna un espacio de dirección plano de 32 bits, la mitad reservado para el sistema operativo y la otra mitad para el código de usuario. Por defecto, a cada subproceso se le asigna un bloque contiguo reservado de un megabyte de espacio de direcciones. (Nota: esta es una de las razones por las que los subprocesos son pesados. Un millón de bytes de memoria contigua es mucho cuando solo tienes dos mil millones de bytes en primer lugar).

Aquí hay algunas sutilezas con respecto a si ese espacio de direcciones contiguas está simplemente reservado o realmente comprometido, pero pasemos por alto eso. Continuaré describiendo cómo funciona en un programa convencional de Windows en lugar de entrar en los detalles de CLR.

Bien, entonces tenemos, digamos, un millón de bytes de memoria, divididos en 250 páginas de 4kb cada una. Pero el programa cuando comienza a ejecutarse solo necesitará quizás unos pocos kb de pila. Así es como funciona. La página de pila actual es una página comprometida perfectamente buena; Es solo memoria normal. La página más allá de eso está marcada como una página de protección. Y la última página en nuestra pila de millones de bytes está marcada como una página de protección muy especial.

Supongamos que intentamos escribir un byte de memoria de pila más allá de nuestra buena página de pila. Esa página está protegida, por lo que se produce un error de página. El sistema operativo maneja la falla al hacer que esa página de pila sea buena, y la siguiente página se convierte en la nueva página de protección.

Sin embargo , si se golpea la última página de protección, la muy especial, Windows desencadena una excepción fuera de la pila y restablece la página de protección para que signifique "si se golpea nuevamente esta página, finalice el proceso". Si eso sucede, Windows finaliza el proceso de inmediato . Sin excepción. Sin código de limpieza. Sin cuadro de diálogo. Si alguna vez has visto una aplicación de Windows desaparecer por completo de repente, probablemente lo que sucedió fue que alguien golpeó la página de guardia al final de la pila por segunda vez.

Bien, ahora que entendemos los mecanismos, y de nuevo, estoy pasando por alto muchos detalles aquí, probablemente pueda ver cómo escribir código que haga excepciones fuera de la pila. La forma educada, que es lo que hice en VBScript y JScript, es hacer una consulta de memoria virtual en la pila y preguntar dónde está la página de protección final. Luego, mire periódicamente el puntero de la pila actual y, si está llegando a un par de páginas, simplemente cree un error de VBScript o arroje una excepción de JavaScript en ese mismo momento, en lugar de dejar que el sistema operativo lo haga por usted.

Si no quiere hacerlo usted mismo, puede manejar la excepción de primera oportunidad que el sistema operativo le da cuando se golpea la página de protección final, convertir eso en una excepción de desbordamiento de pila que C # entiende, y tenga mucho cuidado de No golpear la página de guardia por segunda vez.

Answer 6

La pila se desborda

Te lo haré fácil; pero esto en realidad es bastante complejo ... Tenga en cuenta que generalizaré bastante aquí.

Como probablemente sepa, la mayoría de los idiomas usan la pila para almacenar información de llamadas. Consulte también: https://msdn.microsoft.com/en-us/library/zkwh89ks.aspx para ver cómo funciona cdecl. Si llamas a un método, empujas cosas en la pila; si regresas, sacas cosas de la pila.

Tenga en cuenta que la recursividad no suele estar "en línea". (Nota: aquí digo explícitamente ''recursión'' y no ''recursión de cola''; esta última funciona como un ''goto'' y no aumenta la pila).

La forma más fácil de detectar un desbordamiento de la pila es verificar la profundidad de la pila actual (p. Ej., Bytes utilizados) y, si llega a un límite, generar un error. Para aclarar sobre esta ''verificación de límites'': la forma en que se realizan estas verificaciones es normalmente mediante el uso de páginas de protección; esto significa que las comprobaciones de límites normalmente no se implementan como verificaciones if-then-else (aunque existen algunas implementaciones ...).

En la mayoría de los idiomas, cada hilo tiene su propia pila.

Detectando bucles infinitos

Bueno, aquí hay una pregunta que no he escuchado en mucho tiempo. :-)

Básicamente, detectar todos los bucles infinitos requiere que resuelva el problema de detención . Lo cual, por cierto, es un problema indecidible . Esto definitivamente no lo hacen los compiladores.

Esto no significa que no pueda hacer ningún análisis; de hecho, puedes hacer bastante análisis. Sin embargo, también tenga en cuenta que a veces desea que las cosas se ejecuten indefinidamente (como el bucle principal en un servidor web).

Otros idiomas

También es interesante ... Los lenguajes funcionales utilizan la recursividad, por lo que básicamente están vinculados por la pila. (Dicho esto, los lenguajes funcionales también tienden a usar la recursión de cola, que funciona más o menos como un ''goto'' y no aumenta la pila).

Y luego están los lenguajes lógicos ... bueno, ahora no estoy seguro de cómo hacer un bucle para siempre en eso, probablemente terminarás con algo que no evaluará en absoluto (no se puede encontrar una solución). (Sin embargo, esto probablemente depende del idioma ...)

Rendimientos, asíncronos, continuaciones

Un concepto interesante en el que podría pensar se llama continuations . Escuché de Microsoft que cuando se implementó el yield por primera vez, las continuaciones reales se consideraron como implementación. Las continuaciones básicamente le permiten ''guardar'' la pila, continuar en otro lugar y ''restaurar'' la pila nuevamente en un punto posterior ... (Nuevamente, los detalles son mucho más complicados que esto; esta es solo la idea básica).

Desafortunadamente, Microsoft no eligió esta idea (aunque puedo imaginar por qué), sino que la implementó utilizando una clase auxiliar. Rendimiento y asíncrono en C # funcionan agregando una clase temporal e internando todas las variables locales dentro de la clase. Si llama a un método que hace un ''rendimiento'' o ''asíncrono'', en realidad crea una clase auxiliar (desde dentro del método que llama y empuja en la pila) que se empuja en el montón. La clase que se empuja en el montón tiene la funcionalidad (por ejemplo, para yield esta es la implementación de enumeración). La forma en que se hace esto es mediante el uso de una variable de estado, que almacena la ubicación (por ejemplo, alguna identificación de estado) donde el programa debe continuar cuando se MoveNext . Una rama (conmutador) que usa esta ID se encarga del resto. Tenga en cuenta que este mecanismo no hace nada ''especial'' con la forma en que funciona la pila; puede implementar lo mismo utilizando clases y métodos (solo implica más tipeo :-)).

Resolver desbordamientos de pila con una pila manual

Siempre me gusta un buen relleno de inundación. Una imagen le dará muchas llamadas de recursión si hace esto mal ... diga, así:

public void FloodFill(int x, int y, int color)
{
    // Wait for the crash to happen...
    if (Valid(x,y))
    {
        SetPixel(x, y, color);
        FloodFill(x - 1, y, color);
        FloodFill(x + 1, y, color);
        FloodFill(x, y - 1, color);
        FloodFill(x, y + 1, color);
    }
}

Sin embargo, no hay nada malo con este código. Hace todo el trabajo, pero nuestra pila se interpone en el camino. Tener una pila manual resuelve esto, a pesar de que la implementación es básicamente la misma:

public void FloodFill(int x, int y, int color)
{
    Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>();
    stack.Push(new Tuple<int, int>(x, y));
    while (stack.Count > 0)
    {
        var current = stack.Pop();

        int x2 = current.Item1;
        int y2 = current.Item2;

        // "Recurse"
        if (Valid(x2, y2))
        {
            SetPixel(x2, y2, color);
            stack.Push(new Tuple<int, int>(x2-1, y2));
            stack.Push(new Tuple<int, int>(x2+1, y2));
            stack.Push(new Tuple<int, int>(x2, y2-1));
            stack.Push(new Tuple<int, int>(x2, y2+1));
        }
    }
}