콜 스택

컴퓨터 과학에서 콜 스택(call stack)은 컴퓨터 프로그램의 활성 서브루틴과 인라인 블록에 대한 정보를 저장하는 스택 자료 구조이다. 이러한 유형의 스택은 실행 스택(execution stack), 프로그램 스택(program stack), 제어 스택(control stack), 런타임 스택(run-time stack) 또는 머신 스택(machine stack)으로도 알려져 있으며, 종종 간단히 "스택"(stack)이라고 줄여 부른다. 콜 스택의 유지는 대부분의 소프트웨어가 제대로 작동하는 데 중요하지만, 세부 사항은 일반적으로 고급 프로그래밍 언어에서 숨겨져 있고 자동으로 처리된다. 많은 컴퓨터 명령어 집합은 스택을 조작하기 위한 특별한 명령어를 제공한다.

콜 스택은 몇 가지 관련 목적을 위해 사용되지만, 가장 중요한 이유는 각 활성 서브루틴이 실행을 마칠 때 제어를 반환해야 할 지점을 추적하는 것이다. 활성 서브루틴은 호출되었지만 아직 실행을 완료하지 않은 서브루틴이며, 실행 완료 후에는 제어가 호출 지점으로 반환되어야 한다. 이러한 서브루틴의 활성화는 어떤 수준으로든 중첩될 수 있으므로(특별한 경우로서 재귀), 스택 구조가 필요하다. 예를 들어, DrawSquare 서브루틴이 네 개의 다른 위치에서 DrawLine 서브루틴을 호출하는 경우, DrawLine은 실행이 완료될 때 어디로 반환해야 하는지 알아야 한다. 이를 위해 DrawLine으로 점프하는 명령 다음에 오는 주소, 즉 복귀 주소는 각 호출의 일부로 콜 스택의 맨 위에 푸시된다.

설명

콜 스택은 스택으로 구성되어 있으므로, 프로시저의 호출자는 복귀 주소를 스택에 푸시하고, 호출된 서브루틴은 실행을 마칠 때 콜 스택에서 복귀 주소를 풀(pull)하거나 팝(pop)하고 해당 주소로 제어를 전송한다. 마찬가지로, 인라인 블록의 프롤로그는 스택 프레임을 푸시하고 에필로그는 이를 팝한다. 호출된 서브루틴이 다른 서브루틴을 또 호출하면, 다른 복귀 주소를 콜 스택에 푸시하는 식으로 정보가 프로그램에 따라 쌓이고 풀린다. 푸싱이 콜 스택에 할당된 모든 공간을 소비하면 스택 오버플로라는 오류가 발생하여 일반적으로 프로그램이 충돌한다. 블록이나 서브루틴의 엔트리를 콜 스택에 추가하는 것을 때때로 "winding"이라고 하고, 엔트리를 제거하는 것을 "unwinding"이라고 한다.

실행 중인 프로그램(또는 더 정확하게는 프로세스 (컴퓨팅)의 각 태스크 또는 스레드)과 연결된 콜 스택은 일반적으로 하나만 존재하지만, 시그널 처리 또는 협동적 멀티태스킹(setcontext와 같이)을 위해 추가 스택이 생성될 수 있다. 이 중요한 문맥에서는 하나만 존재하므로 스택(암묵적으로 "태스크의" 스택)이라고 부를 수 있다. 그러나 포스 프로그래밍 언어에서는 데이터 스택 또는 파라미터 스택이 콜 스택보다 더 명시적으로 접근되며, 일반적으로 스택이라고 부른다(아래 참조).

고급 프로그래밍 언어에서는 콜 스택의 세부 사항이 일반적으로 프로그래머에게 숨겨져 있다. 프로그래머는 스택 자체의 메모리가 아닌, 일련의 함수에만 접근할 수 있다. 이는 추상화의 한 예이다. 반면에 대부분의 어셈블리어는 프로그래머가 스택 조작에 직접 관여해야 한다. 프로그래밍 언어에서 스택의 실제 세부 사항은 컴파일러, 운영체제, 그리고 사용 가능한 명령어 집합에 따라 달라진다.

콜 스택의 기능

 스택 기반 메모리 할당 문서를 참고하십시오.

위에서 언급했듯이, 콜 스택의 주요 목적은 복귀 주소를 저장하는 것이다. 서브루틴이 호출될 때, 호출 루틴이 나중에 다시 시작할 수 있는 명령어의 위치(주소)는 어딘가에 저장되어야 한다. 복귀 주소를 저장하기 위해 스택을 사용하는 것은 호출된 서브루틴 시작 전에 또는 다른 고정된 위치에 복귀 주소를 저장하는 것과 같은 다른 호출 규약에 비해 중요한 장점이 있다. 한 가지 장점은 각 태스크가 자체 스택을 가질 수 있으므로 서브루틴이 스레드 안전하게, 즉 다른 작업을 수행하는 여러 태스크에 대해 동시에 활성화될 수 있다는 것이다. 또 다른 이점은 재진입성을 제공함으로써 재귀가 자동으로 지원된다는 것이다. 함수가 재귀적으로 자신을 호출할 때, 각 함수 활성화에 대한 복귀 주소가 저장되어야 나중에 함수 활성화에서 반환하는 데 사용될 수 있다. 스택 구조는 이 기능을 자동으로 제공한다.

언어, 운영체제 및 기계 환경에 따라 콜 스택은 다음과 같은 추가 목적을 제공할 수 있다.

지역 데이터 저장

서브루틴은 활성 서브루틴 내에서만 알려져 있고 반환 후에는 값을 유지하지 않는 지역 변수의 값을 저장하기 위한 메모리 공간이 자주 필요하다. 단순히 스택의 상단을 충분히 이동하여 이 용도로 공간을 할당하는 것이 편리한 경우가 많다. 이는 힙 공간을 사용하는 동적 메모리 할당에 비해 매우 빠르다. 서브루틴의 각 별도 활성화는 지역 변수를 위해 스택에 자체 별도 공간을 얻는다.

마찬가지로, 인라인 블록은 지역 변수를 위해 스택 프레임을 할당할 수 있다. 호출 프레임과 마찬가지로 블록이 종료되면 값은 손실된다.

매개변수 전달

서브루틴은 종종 호출하는 코드에 의해 매개변수 값이 제공되어야 하며, 이러한 매개변수를 위한 공간이 콜 스택에 배치되는 것은 드물지 않다. 일반적으로 몇 개의 작은 매개변수만 있는 경우 프로세서 레지스터가 값을 전달하는 데 사용되지만, 이 방식으로 처리할 수 있는 것보다 더 많은 매개변수가 있는 경우 메모리 공간이 필요하다. 콜 스택은 이러한 매개변수를 위한 공간으로 잘 작동하며, 특히 매개변수에 대해 다른 값을 갖는 서브루틴에 대한 각 호출에 대해 콜 스택에 해당 값을 위한 별도의 공간이 제공될 것이기 때문이다. C++와 같은 객체 지향 언어에서는 매개변수 목록에 this 포인터도 포함될 수 있다.

평가 스택

산술 또는 논리 연산을 위한 피연산자는 주로 레지스터에 배치되어 거기서 연산된다. 그러나 어떤 상황에서는 피연산자가 임의의 깊이로 쌓일 수 있으며, 이는 레지스터 이상의 것이 사용되어야 함을 의미한다(이것은 레지스터 스필링의 경우이다). 이러한 피연산자의 스택은 RPN 계산기의 스택과 유사하게 평가 스택이라고 불리며, 콜 스택에서 공간을 차지할 수 있다.

둘러싸는 서브루틴 컨텍스트

일부 프로그래밍 언어(파스칼 및 에이다 등)는 중첩 서브루틴 선언을 지원하며, 이는 둘러싸는 루틴의 컨텍스트, 즉 외부 루틴의 범위 내에 있는 매개변수와 지역 변수에 접근할 수 있다. 이러한 정적 중첩은 반복될 수 있다(함수 내부에 선언된 함수 내부에 선언된 함수…). 구현은 주어진 정적 중첩 수준의 호출된 함수가 각 둘러싸는 중첩 수준에서 둘러싸는 프레임을 참조할 수 있는 수단을 제공해야 한다. 이 참조는 일반적으로 "다운스택 링크" 또는 "정적 링크"라고 불리는, 둘러싸는 함수의 가장 최근 활성화 인스턴스의 프레임에 대한 포인터로 구현되며, 즉시 호출자(정적 부모 함수가 아닐 수 있음)를 참조하는 "동적 링크"와 구별된다.

정적 링크 대신, 둘러싸는 정적 프레임에 대한 참조는 디스플레이(display)라고 알려진 포인터 배열로 수집될 수 있으며, 이는 원하는 프레임을 찾기 위해 인덱싱된다. 루틴의 어휘적 중첩 깊이는 알려진 상수이므로, 루틴의 디스플레이 크기는 고정되어 있다. 또한 포함하는 범위의 개수가 알려져 있으므로, 디스플레이에 대한 인덱스도 고정되어 있다. 일반적으로 루틴의 디스플레이는 자체 스택 프레임에 위치하지만, 버로스 B6500은 최대 32단계의 정적 중첩을 지원하는 하드웨어에 이러한 디스플레이를 구현했다.

포함하는 범위를 나타내는 디스플레이 항목은 호출자의 디스플레이의 적절한 접두사에서 얻는다. 재귀하는 내부 루틴은 각 호출에 대해 별도의 호출 프레임을 생성한다. 이 경우 모든 내부 루틴의 정적 링크는 동일한 외부 루틴 컨텍스트를 가리킨다.

둘러싸는 블록 컨텍스트

일부 언어, 예를 들어 ALGOL 60, PL/I에서는 프로시저 내의 블록이 자체 지역 변수를 가질 수 있으며, 블록 진입 시 할당되고 블록 종료 시 해제된다. 마찬가지로 블록은 자체 예외 처리기를 가질 수 있으며, 블록 종료 시 비활성화된다.

기타 반환 상태

복귀 주소 외에도 일부 환경에서는 서브루틴이 반환될 때 복원해야 하는 다른 기계 또는 소프트웨어 상태가 있을 수 있다. 여기에는 특권 수준, 예외 처리 정보, 산술 모드 등이 포함될 수 있다. 필요한 경우, 복귀 주소와 마찬가지로 콜 스택에 저장될 수 있다.

일반적인 콜 스택은 복귀 주소, 지역 변수 및 매개변수(콜 프레임이라고도 함)에 사용된다. 일부 환경에서는 콜 스택에 더 많거나 적은 함수가 할당될 수 있다. 예를 들어 포스 프로그래밍 언어에서는 일반적으로 복귀 주소, 카운트된 루프 매개변수 및 인덱스, 그리고 아마도 지역 변수만이 콜 스택(이 환경에서는 리턴 스택이라고 불림)에 저장되지만, 호출 및 반환의 요구 사항이 충족되는 한 특별한 리턴 스택 처리 코드를 사용하여 모든 데이터를 임시로 거기에 배치할 수 있다. 매개변수는 일반적으로 별도의 데이터 스택 또는 매개변수 스택에 저장되며, 포스 용어에서는 콜 스택이 있음에도 불구하고 일반적으로 더 명시적으로 접근되기 때문에 스택이라고 불린다. 일부 포스 구현은 부동소수점 매개변수를 위한 세 번째 스택을 가지기도 한다.

구조

DrawSquare 서브루틴(blue|파란색으로 표시)이 현재 실행 중인 루틴인 DrawLine(green|녹색으로 표시)을 호출한 후 위쪽으로 성장하는 스택에 대한 콜 스택 레이아웃

콜 스택은 스택 프레임(활성화 레코드 또는 활성화 프레임이라고도 함)으로 구성된다. 이들은 기계 의존적이며 ABI 의존적인, 서브루틴 상태 정보를 포함하는 데이터 구조이다. 각 스택 프레임은 아직 반환으로 완료되지 않은 서브루틴의 호출에 해당한다.^[1] 스택의 맨 위 스택 프레임은 현재 실행 중인 루틴에 대한 것이다. 예를 들어, DrawSquare 서브루틴에 의해 호출된 DrawLine 서브루틴이 현재 실행 중인 경우, 콜 스택의 맨 위 부분은 인접한 그림과 같이 배치될 수 있다.

이와 같은 다이어그램은 상단의 위치와 스택 증가 방향이 이해되는 한 어느 방향으로든 그릴 수 있다. 아키텍처는 콜 스택이 높은 주소로 증가하는지 낮은 주소로 증가하는지에 따라 다르므로, 어떤 다이어그램의 논리도 이러한 주소 지정 선택에 따라 달라지지 않는다.

스택 맨 위에 자신의 프레임을 가지고 활발하게 실행되는 동안, 루틴은 필요에 따라 자신의 프레임 내 정보에 접근할 수 있다.^[2] 스택 프레임은 일반적으로 최소한 다음 항목(푸시된 순서대로)을 포함한다:

• 콜 스택에서 루틴에 전달된 인자(매개변수 값)(있는 경우)
• 루틴의 호출자로 돌아가는 복귀 주소(예: DrawLine 스택 프레임에서 DrawSquare 코드 내의 주소), 레지스터가 아닌 콜 스택에 저장되는 경우
• 루틴의 지역 변수를 위한 공간(있는 경우)

스택 및 프레임 포인터

스택 프레임 크기가 다를 수 있는 경우(예: 다른 함수 간 또는 특정 함수 호출 간), 스택에서 프레임을 팝하는 것은 스택 포인터의 고정된 감소를 구성하지 않는다. 함수 반환 시 스택 포인터는 대신 함수가 호출되기 직전의 스택 포인터 값인 프레임 포인터로 복원된다. 각 스택 프레임은 바로 아래 프레임의 상단에 대한 프레임 포인터를 포함한다. 스택 포인터는 모든 호출 간에 공유되는 가변 레지스터이다. 함수의 주어진 호출의 프레임 포인터는 함수가 호출되기 전의 스택 포인터의 복사본이다.^[3]

프레임의 다른 모든 필드의 위치는 스택 포인터의 음수 오프셋으로 프레임의 상단에 상대적으로 정의되거나, 프레임 포인터의 양수 오프셋으로 아래 프레임의 상단에 상대적으로 정의될 수 있다. 프레임 포인터 자체의 위치는 본질적으로 스택 포인터의 음수 오프셋으로 정의되어야 한다.

호출자의 프레임 주소 저장

대부분의 시스템에서 스택 프레임은 이전 프레임 포인터 레지스터의 값, 즉 호출자가 실행 중일 때 가졌던 값을 포함하는 필드를 갖는다. 예를 들어, DrawLine의 스택 프레임은 DrawSquare가 사용하는 프레임 포인터 값을 저장하는 메모리 위치를 가질 것이다(위 다이어그램에는 표시되지 않음). 이 값은 서브루틴 진입 시 저장된다. 스택 프레임의 알려진 위치에 이러한 필드를 가짐으로써 코드가 현재 실행 중인 루틴의 프레임 아래에 있는 각 프레임에 순차적으로 접근할 수 있으며, 또한 루틴이 반환하기 직전에 프레임 포인터를 호출자의 프레임으로 쉽게 복원할 수 있다.

어휘적으로 중첩된 루틴

 중첩 함수 및 비지역 변수 문서에 이 부분의 추가 정보가 있습니다.

중첩 서브루틴을 지원하는 프로그래밍 언어는 또한 호출 프레임에 호출자를 가장 밀접하게 감싸는 프로시저의 최신 활성화의 스택 프레임을 가리키는 필드를 가지고 있다. 즉, 호출자의 즉각적인 범위를 가리킨다. 이를 접근 링크 또는 정적 링크(동적 및 재귀 호출 중에 정적 중첩을 추적하기 때문에)라고 하며, 루틴(및 루틴이 호출할 수 있는 다른 루틴)이 모든 중첩 수준에서 자신을 감싸는 루틴의 지역 데이터에 접근할 수 있도록 한다. 일부 아키텍처, 컴파일러 또는 최적화 사례는 각 둘러싸는 수준에 대해 하나의 링크를 저장하므로(즉시 둘러싸는 수준뿐만 아니라), 깊이 중첩된 루틴이 얕은 데이터에 접근할 때 여러 링크를 거쳐야 할 필요가 없다. 이 전략은 종종 "디스플레이"라고 불린다.^[4]

접근 링크는 예를 들어 인수와 반환 값을 통해서만 통신하는 순수 함수와 같이 내부 함수가 캡슐화 내의 (상수가 아닌) 지역 데이터에 접근하지 않을 때 최적화되어 제거될 수 있다. 일렉트로로지카 X8 및 나중에 버로스 대형 시스템과 같은 일부 역사적인 컴퓨터는 중첩 함수를 지원하기 위한 특별한 "디스플레이 레지스터"를 가졌지만, 대부분의 현대 기계(유비쿼터스 x86과 같은)용 컴파일러는 필요에 따라 포인터에 대한 몇 단어를 스택에 예약한다.

오버랩

일부 목적을 위해 서브루틴의 스택 프레임과 호출자의 스택 프레임은 오버랩되는 것으로 간주될 수 있으며, 오버랩은 매개변수가 호출자에서 호출자에게 전달되는 영역으로 구성된다. 일부 환경에서는 호출자가 각 인수를 스택에 푸시하여 스택 프레임을 확장한 다음 호출자를 호출한다. 다른 환경에서는 호출자가 호출하는 다른 서브루틴에 제공하는 인수를 저장하기 위해 스택 프레임 상단에 미리 할당된 영역을 갖는다. 이 영역은 때때로 외부 인수 영역 또는 호출 영역이라고 불린다. 이 접근 방식에서는 영역의 크기가 호출된 서브루틴에 필요한 가장 큰 크기로 컴파일러에 의해 계산된다.

사용

호출 지점 처리

일반적으로 서브루틴 호출 시 필요한 콜 스택 조작은 최소화된다(이는 호출될 각 서브루틴에 대해 많은 호출 지점이 있을 수 있으므로 좋다). 실제 인수에 대한 값은 특정 호출에 따라 달라지므로 호출 지점에서 평가되며, 사용되는 호출 규약에 따라 스택에 푸시되거나 레지스터에 배치된다. 그런 다음 "분기 및 링크"와 같은 실제 호출 명령어가 일반적으로 실행되어 대상 서브루틴의 코드로 제어를 전송한다.

서브루틴 진입 처리

호출된 서브루틴에서 실행되는 첫 번째 코드는 일반적으로 서브루틴 프롤로그라고 불리는데, 이는 루틴의 문장에 대한 코드가 시작되기 전에 필요한 정리 작업을 수행하기 때문이다.

서브루틴을 호출하는 데 사용되는 명령어가 복귀 주소를 스택에 푸시하는 대신 레지스터에 넣는 명령어 집합 아키텍처에서는, 프롤로그가 일반적으로 값을 콜 스택에 푸시하여 복귀 주소를 저장하지만, 호출된 서브루틴이 다른 루틴을 호출하지 않는 경우에는 값을 레지스터에 남겨둘 수도 있다. 마찬가지로 현재 스택 포인터 및 프레임 포인터 값이 푸시될 수 있다.

프레임 포인터가 사용되는 경우, 프롤로그는 일반적으로 스택 포인터에서 프레임 포인터 레지스터의 새 값을 설정한다. 그런 다음 스택 포인터를 점진적으로 변경하여 지역 변수를 위한 스택 공간을 할당할 수 있다.

포스 프로그래밍 언어는 콜 스택(거기서는 "리턴 스택"이라고 불림)의 명시적 와인딩을 허용한다.

반환 처리

서브루틴이 반환 준비가 되면, 프롤로그의 단계를 되돌리는 에필로그를 실행한다. 이는 일반적으로 스택 프레임에서 저장된 레지스터 값(프레임 포인터 값 등)을 복원하고, 스택 포인터 값을 변경하여 전체 스택 프레임을 스택에서 팝하며, 마지막으로 복귀 주소의 명령어로 분기한다. 많은 호출 규약에 따르면, 에필로그에 의해 스택에서 팝되는 항목에는 원래 인수 값이 포함되며, 이 경우 호출자가 수행해야 할 추가 스택 조작은 일반적으로 없다. 그러나 일부 호출 규약에서는 반환 후에 스택에서 인수를 제거하는 것이 호출자의 책임이다.

언와인딩

호출된 함수에서 반환하면 스택의 최상위 프레임이 팝되고, 아마도 반환 값이 남게 될 것이다. 프로그램의 다른 곳에서 실행을 재개하기 위해 스택에서 하나 이상의 프레임을 팝하는 더 일반적인 행위를 스택 언와인딩이라고 하며, 예외 처리에 사용되는 것과 같은 비지역 제어 구조가 사용될 때 수행되어야 한다. 이 경우 함수의 스택 프레임에는 하나 이상의 예외 처리기를 지정하는 엔트리가 포함된다. 예외가 발생하면, 스택은 발생한 예외 유형을 처리할(catch할) 준비가 된 처리기를 찾을 때까지 언와인딩된다.

일부 언어에는 일반적인 언와인딩을 요구하는 다른 제어 구조가 있다. 파스칼은 전역 GOTO 문을 사용하여 중첩된 함수에서 이전 호출된 외부 함수로 제어를 전송할 수 있도록 허용한다. 이 작업은 스택을 언와인딩하여, 둘러싸는 외부 함수 내의 대상 문으로 제어를 전송하는 데 필요한 올바른 컨텍스트를 복원하기 위해 필요한 만큼의 스택 프레임을 제거해야 한다. 마찬가지로, C는 비지역 goto로 작동하는 setjmp 및 longjmp 함수를 가지고 있다. 커먼 리스프는 unwind-protect 특수 연산자를 사용하여 스택이 언와인딩될 때 발생하는 일을 제어할 수 있도록 한다.

계속을 적용할 때, 스택은 (논리적으로) 언와인딩된 다음 계속의 스택으로 다시 와인딩된다. 이는 계속을 구현하는 유일한 방법은 아니다. 예를 들어, 여러 개의 명시적 스택을 사용하면 계속의 적용은 단순히 해당 스택을 활성화하고 전달할 값을 와인딩할 수 있다. 스킴 프로그래밍 언어는 계속이 호출될 때 제어 스택의 "언와인딩" 또는 "리와인딩"의 특정 지점에서 임의의 썽크를 실행할 수 있도록 한다.

검사

 프로파일링 (컴퓨터 프로그래밍) 문서를 참고하십시오.

콜 스택은 프로그램이 실행 중일 때 때때로 검사될 수 있다. 프로그램이 작성되고 컴파일되는 방식에 따라 스택의 정보는 중간 값과 함수 호출 추적을 결정하는 데 사용될 수 있다. 이는 세밀한 자동화 테스트를 생성하는 데 사용되었으며,^[5] Ruby 및 Smalltalk와 같은 경우에는 일급 계속을 구현하는 데 사용되었다. 예를 들어, GNU 디버거(GDB)는 실행 중이지만 일시 중지된 C 프로그램의 콜 스택에 대한 대화형 검사를 구현한다.^[6]

콜 스택의 정기적인 시간 샘플링은 프로그램 성능을 프로파일링하는 데 유용할 수 있다. 서브루틴의 주소가 콜 스택 샘플링 데이터에 여러 번 나타나면 코드 병목 현상으로 작용할 가능성이 높으며 성능 문제를 검사해야 한다.

보안

 이 부분의 본문은 스택 버퍼 오버플로입니다.

자유 포인터나 검사되지 않는 배열 쓰기를 가진 언어(예: C)에서는 코드 실행에 영향을 미치는 제어 흐름 데이터(복귀 주소 또는 저장된 프레임 포인터)와 단순 프로그램 데이터(매개변수 또는 반환 값)를 콜 스택에 혼합하는 것이 보안 위험이며, 스택 버퍼 오버플로를 통해 공격될 수 있으며, 이는 가장 흔한 유형의 버퍼 오버플로이다.

그러한 공격 중 하나는 임의의 실행 가능한 코드로 버퍼를 채우고, 이 버퍼 또는 다른 버퍼를 오버플로시켜 일부 복귀 주소를 실행 가능한 코드를 직접 가리키는 값으로 덮어쓰는 것이다. 결과적으로 함수가 반환될 때 컴퓨터는 해당 코드를 실행한다. 이러한 종류의 공격은 W^X로 차단할 수 있지만, Return-to-libc 공격 또는 반환 지향형 프로그래밍에서 비롯된 공격을 포함하여 W^X 보호가 활성화된 경우에도 유사한 공격이 성공할 수 있다. 배열을 복귀 스택과 완전히 다른 위치에 저장하는 것과 같은 다양한 완화책이 제안되었으며, 이는 포스 프로그래밍 언어의 경우이다.^[7]

같이 보기

• 자동 메모리 할당
• 호출 규약
• 코루틴
• 오버헤드
• 스파게티 스택
• 스택 기반 메모리 할당
• 스택 머신
• 스택 추적