스택 오버플로

Stack overflow
웹 사이트의 경우 스택 오버플로를 참조하십시오.다른 용도는 스택 오버플로(동음이의)를 참조하십시오.

소프트웨어에서는 콜 스택포인터가 스택바운드를 넘으면 스택오버플로우가 발생합니다.콜 스택은 제한된 양의 주소 공간으로 구성될 수 있습니다.많은 경우 프로그램 시작 시 결정됩니다.콜 스택의 크기는 프로그래밍 언어, 머신아키텍처, 멀티스레딩, 사용 가능한 메모리 용량 등 많은 요소에 따라 달라집니다.프로그램이 콜 스택에서 사용 가능한 공간보다 더 많은 공간을 사용하려고 하면(즉, 기본적으로 버퍼 오버플로인 콜스택의 경계를 넘어 메모리에 액세스하려고 하면), 스택은 오버플로우라고 간주되어 일반적으로 프로그램크래시가 [1]발생합니다.

원인들

무한 재귀

주요 기사:무한 재귀

스택 오버플로의 가장 일반적인 원인은 과도하게 깊은 재귀 또는 무한 재귀입니다.이 경우 함수는 자신을 여러 번 호출하여 각 콜에 관련된 변수와 정보를 저장하는 데 필요한 공간이 [2]스택에 들어갈 수 있는 공간보다 커집니다.

C에서의 무한 재귀의 예. 

인트 후우()  {      돌아가다 후우(); }

foo 함수는 foo가 호출되면 스택이 오버플로우하여 [2]세그멘테이션 장애가 발생할 때까지 스택에 추가 공간을 할당할 때마다 계속 호출됩니다.단, 일부 컴파일러는 테일콜 최적화를 구현하여 스택오버플로 없이 특정 정렬(테일 재귀)의 무한 재귀가 가능합니다.테일 재귀 콜은 추가 스택스페이스를 [3]차지하지 않기 때문에 이 기능은 동작합니다.

일부 C 컴파일러 옵션에서는 테일콜 최적화가 유효하게 됩니다.예를 들어 gcc를 사용하여 위의 간단한 프로그램을 컴파일하여-O1세그멘테이션 장애는 발생하지만 를 사용할 때는 발생하지 않습니다.-O2또는-O3이러한 최적화 수준은,-foptimize-sibling-calls컴파일러 옵션.[4]Scheme 등의 다른 언어에서는 모든 구현에서 테일 재귀가 언어 [5]표준의 일부로 포함되어야 합니다.

매우 깊은 재귀

이론적으로는 종료되지만 실제로는 콜스택 버퍼 오버플로를 일으키는 재귀 함수는 재귀를 루프로 변환하여 (콜스택의 암묵적인 사용이 아닌) 명시적 스택에 함수 인수를 저장함으로써 수정할 수 있습니다.이것은 원시 재귀 함수의 클래스가 LOUP 계산 가능 함수의 클래스와 동일하기 때문에 항상 가능합니다.C++와 같은 의사 코드로 다음 예를 생각해 보겠습니다.

무효 기능. (논쟁)  {   한다면 (조건.)     기능. (논쟁.다음 분.);  } 
스택.밀다(논쟁); 하는 동안에 (!스택.빈()) {   논쟁 = 스택.팝();   한다면 (조건.)     스택.밀다(논쟁.다음 분.); }

왼쪽과 같은 원시 재귀 함수는 항상 오른쪽과 같은 루프로 변환할 수 있습니다.

왼쪽의 위의 예와 같은 함수는 테일콜 최적화를 지원하는 환경에서는 문제가 되지 않습니다.다만, 이러한 언어에서는 스택 오버플로를 일으킬 가능성이 있는 재귀 함수를 작성할 수 있습니다.다음의 2개의 간단한 정수 지수 함수의 예를 생각해 봅시다. 

인트 전원(인트 기초, 인트 exp) {     한다면 (exp > 0)         돌아가다 기초 * 전원(기초, exp - 1);     또 다른         돌아가다 1; } 
인트 전원(인트 기초, 인트 exp) {     돌아가다 전원(기초, exp, 1); }  인트 전원(인트 기초, 인트 exp, 인트 축적하다) {     한다면 (exp > 0)         돌아가다 전원(기초, exp - 1, 축적하다 * 기초);     또 다른         돌아가다 축적하다; }

둘다요.pow(base, exp)위의 함수는 동등한 결과를 계산하지만 왼쪽 함수는 테일콜 최적화를 할 수 없기 때문에 스택오버플로를 일으키기 쉽습니다.실행 중 다음 기능의 스택은 다음과 같습니다.

전원(5, 4) 5 * 전원(5, 3) 5 * (5 * 전원(5, 2)) 5 * (5 * (5 * 전원(5, 1))) 5 * (5 * (5 * (5 * 전원(5, 0)))) 5 * (5 * (5 * (5 * 1))) 625 
전원(5, 4) 전원(5, 4, 1) 전원(5, 3, 5) 전원(5, 2, 25) 전원(5, 1, 125) 전원(5, 0, 625) 625

왼쪽 함수는 스택에 저장해야 합니다.exp정수 수. 재귀가 종료되고 함수가 1을 반환할 때 곱합니다.반면 오른쪽 함수는 항상 3개의 정수만 저장해야 하며, 중간 결과를 계산하여 다음 호출로 전달합니다.현재 함수 호출 이외의 정보는 저장해서는 안 되기 때문에 테일 재귀 옵티마이저는 이전 스택프레임을 "폐기"할 수 있기 때문에 스택오버플로우 가능성을 배제할 수 있습니다.

매우 큰 스택 변수

스택 오버플로의 다른 주요 원인은 예를 들어 너무 큰 로컬 어레이 변수를 작성하는 등 스택에 필요한 메모리보다 더 많은 메모리를 할당하려는 시도가 원인입니다.따라서 일부 저자는 몇 [6]킬로바이트보다 큰 어레이를 로컬 변수가 아닌 동적으로 할당할 것을 권장합니다.

C의 매우 큰 스택 변수의 예를 다음에 나타냅니다.

인트 후우()  {      더블 x[1048576]; }

8 바이트의 2배 정밀도를 가진 C 구현에서는 선언된 배열은 8 MB의 데이터를 소비합니다.이것이 스택에서 사용 가능한 메모리보다 많은 경우(스레드 작성 파라미터 또는 운영체제 제한에 따라 설정됨) 스택오버플로우가 발생합니다.

스택 오버플로우는 특정 프로그램의 유효 스택사이즈를 줄이는 것에 의해서 악화됩니다.예를 들어, 같은 프로그램이 여러 스레드 없이 실행되면 정상적으로 동작할 수 있지만 멀티스레딩을 활성화하면 프로그램이 크래시됩니다.이는 스레드가 있는 대부분의 프로그램은 스레드가 지원되지 않는 프로그램보다 스레드당 스택 공간이 적기 때문입니다.커널은 일반적으로 멀티 스레드이기 때문에 커널 개발을 처음 하는 사람들은 일반적으로 재귀 알고리즘이나 큰 스택 [7]버퍼를 사용하지 않는 것이 좋습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Burley, James Craig (1991-06-01). "Using and Porting GNU Fortran". Archived from the original on 2012-02-06.
  2. ^ a b 세그멘테이션 장애와 스택 오버플로의 차이점은 무엇입니까?StackOverflow에서
  3. ^ "An Introduction to Scheme and its Implementation". 1997-02-19. Archived from the original on 2007-08-10.
  4. ^ "Using the GNU Compiler Collection (GCC): Optimize Options". Retrieved 2017-08-20.
  5. ^ Richard Kelsey; William Clinger; Jonathan Rees; et al. (August 1998). "Revised5 Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation. 11 (1): 7–105. doi:10.1023/A:1010051815785. S2CID 14069423. Retrieved 2012-08-09.
  6. ^ Feldman, Howard (2005-11-23). "Modern Memory Management, Part 2".
  7. ^ "Kernel Programming Guide: Performance and Stability Tips". Apple Inc. 2014-05-02.

외부 링크