StackOverflowException은 어떻게 감지됩니까?

StackOverflowException은 어떻게 감지됩니까?

---

TL; TR
내가 질문을했을 때 나는 StackOverflowException응용 프로그램이 무한히 실행되는 것을 방지하는 메커니즘 이라고 가정했습니다 . 이것은 사실이 아닙니다.
A StackOverflowException가 감지되지 않습니다.
스택에 더 많은 메모리를 할당 할 용량이 없을 때 발생합니다.

[원래 질문 :]

이것은 프로그래밍 언어마다 다른 답변이있을 수있는 일반적인 질문입니다.
C # 이외의 언어가 스택 오버플로를 처리하는 방법을 잘 모르겠습니다.

나는 오늘 예외를 겪고 있었고 어떻게 StackOverflowException탐지 될 수 있는지 계속 생각했습니다 . 스택이 1000 호출 깊이이면 fe라고 말할 수 없다고 생각하고 예외를 던집니다. 어떤 경우에는 올바른 논리가 그렇게 깊기 때문입니다.

내 프로그램에서 무한 루프를 감지하는 논리는 무엇입니까?

StackOverflowException클래스 :
https://msdn.microsoft.com/de-de/library/system.stackoverflowexception%28v=vs.110%29.aspx 클래스 설명서에

언급 된 상호 참조 StackOverflowException:
https://msdn.microsoft.com/de -de / library / system.reflection.emit.opcodes.localloc (v = vs.110) .aspx

방금 stack-overflow이 질문에 태그를 추가 했는데 설명에 호출 스택이 너무 많은 메모리를 소비 할 때 발생한다고 나와 있습니다. 그것은 호출 스택이 내 프로그램의 현재 실행 위치에 대한 일종의 경로라는 것을 의미하며 더 많은 경로 정보를 저장할 수 없으면 예외가 발생합니까?

---

스택 오버플로

나는 당신을 위해 쉽게 만들 것입니다. 하지만 이것은 실제로 꽤 복잡합니다. 여기서는 꽤 일반화 할 것입니다.

아시다시피 대부분의 언어는 호출 정보를 저장하기 위해 스택을 사용합니다. cdecl의 작동 방식은 https://msdn.microsoft.com/en-us/library/zkwh89ks.aspx 를 참조하십시오 . 메서드를 호출하면 스택에 항목을 푸시합니다. 돌아 오면 스택에서 물건을 꺼냅니다.

재귀는 일반적으로 '인라인'되지 않습니다. (참고 : 여기서는 '꼬리 재귀'가 아니라 '재귀'라고 명시 적으로 말합니다. 후자는 '고토'처럼 작동하며 스택을 늘리지 않습니다.)

스택 오버플로를 감지하는 가장 쉬운 방법은 현재 스택 깊이 (예 : 사용 된 바이트)를 확인하고 경계에 도달하면 오류를 제공하는 것입니다. 이 '경계 검사'에 대해 명확히하기 위해 이러한 검사가 수행되는 방식은 일반적으로 보호 페이지를 사용하는 것입니다. 이것은 경계 검사가 일반적으로 if-then-else 검사로 구현되지 않음을 의미합니다 (일부 구현이 존재하지만 ...).

대부분의 언어에서 각 스레드에는 자체 스택이 있습니다.

무한 루프 감지

자, 여기에 한동안 들어 보지 못한 질문이 있습니다. :-)

기본적으로 모든 무한 루프를 감지하려면 정지 문제 를 해결해야합니다 . 그건 그렇고 결정 불가능한 문제 입니다. 이것은 확실히 컴파일러에 의해 수행되지 않습니다.

이것은 분석을 할 수 없다는 것을 의미하지는 않습니다. 사실 꽤 많은 분석을 할 수 있습니다. 그러나 가끔은 (웹 서버의 메인 루프와 같이) 무한정 실행되기를 원할 수도 있습니다.

다른 언어

또한 흥미 롭습니다. 기능 언어는 재귀를 사용하므로 기본적으로 스택에 묶여 있습니다. (즉, 기능적 언어는 꼬리 재귀를 사용하는 경향이 있는데, 이는 'goto'와 비슷하게 작동하며 스택을 늘리지 않습니다.)

그리고 논리적 언어가 있습니다. 글쎄요, 나는 그것을 영원히 반복하는 방법을 모르겠습니다. 당신은 아마도 전혀 평가되지 않는 무언가로 끝날 것입니다 (해결책을 찾을 수 없습니다). (그러나 이것은 아마도 언어에 따라 다릅니다 ...)

양보, 비동기, 연속

흥미로운 개념은 당신이 생각할 수있는 것이 연속 이라는 것 입니다. Microsoft yield에서 처음 구현 되었을 때 실제 연속 작업이 구현으로 간주 되었다고 들었습니다 . 연속은 기본적으로 스택을 '저장'하고 다른 곳에서 계속하고 나중에 스택을 '복원'할 수 있도록합니다 ... (다시 말하지만 세부 사항은 이것보다 훨씬 더 복잡합니다. 이것은 기본 아이디어 일뿐입니다).

안타깝게도 Microsoft는이 아이디어를 사용하지 않았지만 (이유는 상상할 수 있지만) 도우미 클래스를 사용하여 구현했습니다. C #의 Yield 및 async는 임시 클래스를 추가하고 클래스 내의 모든 로컬 변수를 인터 닝하여 작동합니다. 'yield'또는 'async'를 수행하는 메서드를 호출하는 경우 실제로는 힙에 푸시되는 도우미 클래스 (호출하고 스택에 푸시하는 메서드 내에서)를 만듭니다. 힙에 푸시 된 클래스에는 기능이 있습니다 (예 : yield열거 형 구현). 이 작업을 수행하는 방법은 상태 변수를 사용하는 것입니다. 상태 변수는 다음과 같은 경우 프로그램이 계속되어야하는 위치 (예 : 상태 ID)를 저장합니다.MoveNext호출됩니다. 이 ID를 사용하는 분기 (스위치)가 나머지를 처리합니다. 이 메커니즘은 스택 자체가 작동하는 방식과 관련하여 '특별한'작업을 수행하지 않습니다. 클래스와 메서드를 사용하여 직접 구현할 수 있습니다 (더 많은 타이핑이 필요합니다 :-)).

수동 스택으로 스택 오버플로 해결

나는 항상 좋은 홍수 채우기를 좋아합니다. 당신이 이것을 잘못하면 그림은 당신에게 많은 재귀 호출을 줄 것입니다 ... 이렇게 말하십시오 :

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);
    }
}

하지만이 코드에는 아무런 문제가 없습니다. 모든 작업을 수행하지만 스택이 방해를받습니다. 구현이 기본적으로 동일하더라도 수동 스택을 사용하면이 문제를 해결할 수 있습니다.

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));
        }
    }
}

---

여기에는 이미 많은 답변이 있으며, 그 중 많은 것들이 요점을 이해하고 있으며 그중 많은 것에는 미묘하거나 큰 오류가 있습니다. 모든 것을 처음부터 설명하려고하기보다는 몇 가지 중요한 점을 알려 드리겠습니다.

I am not sure how languages other than C# handle a stack overflow.

Your question is "how is a stack overflow detected?" Is your question about how it is detected in C#, or in some other language? If you have a question about another language, I recommend creating a new question.

I think it is not possible to say (for example) if the stack is 1000 calls deep, then throw the exception. Because maybe in some cases the correct logic will be that deep.

It is absolutely possible to implement a stack overflow detection like that. In practice, this is not how it is done, but there is no in-principle reason why the system could not have been designed that way.

What is the logic behind the detection of an infinite loop in my program?

You mean an unbounded recursion, not an infinite loop.

I'll describe it below.

I just added the stack-overflow tag to this question, and the description says it is being thrown when the call stack consumes too much memory. Does that mean the call stack is some sort of path to the current executing position of my program and if it cannot store more path information, then the exception is thrown?

Short answer: yes.

Longer answer: The call stack is used for two purposes.

First, to represent activation information. That is, the values of the local variables and temporary values whose lifetimes are equal to or shorter than the present activation ("call") of a method.

Second, to represent continuation information. That is, when I am done with this method, what do I need to do next? Note that the stack does not represent "where did I come from?". The stack represents where am I going next, and it just so happens that usually when a method returns, you go back to where you came from.

The stack also stores information for non-local continuations -- that is, exception handling. When a method throws, the call stack contains data that helps the runtime determine what code, if any, contains the relevant catch block. That catch block then becomes the continuation -- the "what do I do next" -- of the method.

Now, before I go on, I note that the call stack is a data structure that is being used for two purposes, violating the single responsibility principle. There is no requirement that there be one stack used for two purposes, and in fact there are some exotic architectures in which there are two stacks, one for activation frames and one for return addresses (which are the reification of continuation.) Such architectures are less vulnerable to "stack smashing" attacks that can occur in languages like C.

When you call a method, memory is allocated on the stack to store the return address -- what do I do next -- and the activation frame -- the locals of the new method. Stacks on Windows are by default of fixed size, so if there is not enough room, bad things happen.

In more detail, how does Windows do out of stack detection?

I wrote the out-of-stack detection logic for 32 bit Windows versions of VBScript and JScript in the 1990s; the CLR uses similar techniques as I used, but if you want to know the CLR-specific details, you'll have to consult an expert on the CLR.

Let's consider just 32 bit Windows; 64 bit Windows works similarly.

Windows uses virtual memory of course -- if you do not understand how virtual memory works, now would be a good time to learn before you read on. Each process is given a 32 bit flat address space, half reserved for the operating system and half for the user code. Each thread is by default given a reserved contiguous block of one megabyte of address space. (Note: this is one reason why threads are heavyweight. A million bytes of contiguous memory is a lot when you only have two billion bytes in the first place.)

There are some subtleties here regarding whether that contiguous address space is merely reserved or actually committed, but let's gloss those over. I'll continue to describe how it works in a conventional Windows program rather than going into the CLR details.

OK, so we have lets say a million bytes of memory, divided into 250 pages of 4kb each. But the program when it first starts running is only going to need maybe a few kb of stack. So here's how it works. The current stack page is a perfectly good committed page; it's just normal memory. The page beyond that is marked as a guard page. And the last page in our million byte stack is marked as a very special guard page.

Suppose we try to write a byte of stack memory beyond our good stack page. That page is guarded, so a page fault occurs. The operating system handles the fault by making that stack page good, and the next page becomes the new guard page.

However, if the last guard page is hit -- the very special one -- then Windows triggers an out-of-stack exception, and Windows resets the guard page to mean "if this page is hit again, terminate the process". If that happens then Windows terminates the process immediately. No exception. No cleanup code. No dialog box. If you've ever seen a Windows app just suddenly disappear completely, probably what happened was someone hit the guard page at the end of the stack for the second time.

OK, so now that we understand the mechanisms -- and again, I am glossing over many details here -- you can probably see how to write code that makes out-of-stack exceptions. The polite way -- which is what I did in VBScript and JScript -- is to do a virtual memory query on the stack and ask where the final guard page is. Then periodically look at the current stack pointer, and if it is getting within a couple of pages, simply create a VBScript error or throw a JavaScript exception right then and there rather than letting the operating system do it for you.

If you don't want to do that probing yourself, then you can handle the first chance exception that the operating system gives you when the final guard page is hit, turn that into a stack overflow exception that C# understands, and be very careful to not hit the guard page a second time.

---

The stack is simply a block of memory of a fixed size that is allocated when the thread is created. There is also a "stack pointer", a way of keeping track how much of the stack is currently being used. As a part of creating a new stack frame (when calling a method, property, constructor, etc.) it moves the stack pointer up by the amount that the new frame is going to need. At that time it will check if has moved the stack pointer past the end of the stack, and if so, throw a SOE.

The program does nothing to detect infinite recursion. Infinite recursion (when the runtime is forced to create a new stack frame for each invocation) it simply results in so many method calls being performed as to fill up this finite space. You can just as easily fill up that finite space with a finite number of nested method calls that just happen to consume more space than the stack has. (This tend to be rather hard to do though; it's usually caused by methods that are recursive, and not infinitely so, but of sufficient depth that the stack can't handle it.)

---

WARNING: This has a lot to do with under the hood mechanics, including how the CLR itself has to work. This will only really make sense if you start to study assembly-level programming.

Under the hood, method calls are performed by passing control to the site of another method. In order to pass arguments and returns, these are loaded onto the stack. In order to know how to return control to the calling method, the CLR must also implement a call stack, which is pushed to when a method is called and popped from when a method returns. This stack tells the returning method where to return control to.

Since a computer only has a finite memory, there are times when the call stack gets too big. Thus, a StackOverflowException is not the detection of a infinitely running or infinitely recursive program, it is the detection that the computer can no longer handle the size of the stack required to keep track of where your methods need to return to, the necessary arguments, returns, variables, or (more commonly) a combination thereof. The fact that this exception occurs during infinite recursion is because the logic inevitably overwhelms the stack.

To answer your question, if a program intentionally has logic which would overload the stack then yes you will see a StackOverflowException. However, this is generally thousands up to millions of calls deep and rarely an actual concern unless you've created an infinitely recursive loop.

addendum: The reason I mention recursive loops is beause the exception will only happen if you overwhlem the stack - which generally means you're calling methods which eventually call back into the same method and grow the call stack. If you have something which is logically infinite, but not recursive, you generally won't see a StackOverflowException

---

The problem with stack overflows is not that they might stem from an infinite computation. The problem is exhaustion of stack memory which is a finite resource in today's operating systems and languages.

This condition is detected when the program tries to access a portion of memory that is beyond what is allocated to the stack. This results in an exception.

---

Most of the sub-questions have been sufficiently answered. I would like to clarify the part about the detection of the stack overflow condition, hopefully in a way which is easier to understand than Eric Lippert's answer (which is, correct, of course, but unnecessarily convoluted.) Instead, I will convolute my answer in a different way, by mentioning not one, but two different approaches.

There are two ways to detect stack overflow: either with code, or with the help of hardware.

Stack overflow detection using code was being used back in the days when PCs were running in 16-bit real mode and the hardware was wimpy. It is not used anymore, but it is worth mentioning. In this scenario, we specify a compiler switch asking the compiler to emit a special hidden piece of stack-checking code in the beginning of each function that we write. This code simply reads the value of the stack pointer register and checks to see if it is too close to the end of the stack; if so, it halts our program. The stack on the x86 architecture increases downwards, so if the address range 0x80000 to 0x90000 has been designated as our program's stack, then the stack pointer initially points at 0x90000, and as you keep invoking nested functions it goes down towards 0x80000. So, if the stack checking code sees that the stack pointer is too close to 0x80000, (say, at or below 0x80010,) then it halts.

All this has the disadvantage of a) adding overhead to every single function call that we make, and b) not being able to detect a stack overflow during calls to external code which was not compiled with that special compiler switch and therefore is not performing any stack overflow checking. Back in those days a StackOverflow exception was a luxury unheard of: your program would either terminate with a very laconic (one could almost say rude) error message, or there would be a system crash, requiring a reboot.

Stack overflow detection with the help of hardware basically delegates the job to the CPU. Modern CPUs have an elaborate system for subdividing memory into pages (usually 4KB long each) and doing various tricks with each page, including the ability to have an interrupt (in some architectures called a 'trap') automatically issued when a particular page gets accessed. So, the operating system configures the CPU in such a way that an interrupt will be issued if you attempt to access a stack memory address below the assigned minimum. When that interrupt occurs, it is received by the runtime of your language, (in C#'s case, the .Net runtime,) and it gets translated into a StackOverflow exception.

This has the benefit of having absolutely no extra overhead. There is an overhead associated with the page management that the CPU is performing all the time, but this gets paid anyway, as it is necessary for virtual memory to work, and for various other things like protecting the memory address space of one process from other processes, etc.

참고URL : https://stackoverflow.com/questions/30327674/how-is-a-stackoverflowexception-detected