[CS:APP] Chap 3.7 - 9

3.7 프로시저

프로시저 호출은 소프트웨어에서의 주요 추상화이다. 이들은 지정된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공한다.

이 함수는 프로그램의 여러 지점으로부터 호출 될 수 있게 된다.

• [우] 즉, 함수는 프로그램 안에서 어디서든 호출 될 수 있는 ‘독립적인 코드 덩어리’ 이다.
• 잘 설계된 소프트웨어는 무슨 값이 계산되고, 이 프로시저가 프로그램 상태에 무슨 효과를 갖는지에 대한 명쾌하고 간결한 인터페이스 정의를 제공하는 한편, 일부 동작의 구체적인 구현은 감춰주는 방식이다.
  • 이런 식으로 추상화 메커니즘을 이용하며, 프로시저는 서로 다른 프로그래밍 언어에서 여러가지 다른 모습 : 함수, 메소드, 서브루틴, 핸들러 등으로 사용된다. 그러나 이 모두는 일반적인 특징들을 공유한다.
    • [우] 인터페이스는 명확하게, 내부 동작을 숨겨야 한다. 필요한 정보만 밖으로 드러내는것이 프로시저의 본질적 의미를 말한다.
• x86 같은 하드웨어 입장에서 프로시저 호출을 지원하려면 어떤 것들을 준비해야 할까? 논의를 진행하기 위해 프로시저 P가 프로시저 Q를 호출하고, Q가 실행한 후에 다시 P로 리턴한다고 하자.
  • 이러한 동작들은 다음과 같은 하나 이상의 메커니즘이 연관된다.
  •  이 세 가지는 함수 호출을 기계어 레벨에서 처리하기 위해 필수적인 요소들이다.

제어권 전달	프로그램 카운터는 진입할 때 Q에 대한 코드의 시작주소로 설정되고, 리턴 할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정 되어야한다. call 명령 → 스택에 리턴 주소를 push → Q에 진입한다. → ret 스택에서 리턴 주소 pop → 그리고 jump 리턴주소를 저장한 덕분에 P의 어느 위치로 복귀해야하는지 정확히 기억 할 수 있게 된다.
데이터 전달	P는 하나 이상의 매개변수를 Q에 제공 할 수 있어야 하며, Q는 다시 P로 하나의 값을 리턴 할 수 있어야 한다. 리턴 값은 %rax 레지스터를 사용한다.
메모리 할당과 반납	Q는 시작 할 때 지역변수들을 위한 공간을 할당 할 수도 있고, 리턴할 때 이 저장소를 반납 할 수 있다. Q 진입시 → 스택 포인터 (rsp ) 감소 → 공간을 확보한다. Q 종료시 → 스택 포인터 복원 → 공간을 반납한다.

64비트에서의 프로시저 구현은 레지스터와 프로그램 메모리 같은 머신들의 자원들을 사용하는 방법에 관한 특수 인스트럭션들과 일련의 관습들과 연관되어 있다.

• 프로시저를 호출하는 데 연관된 오버헤드를 최소화 하기 위한 엄청난 노력들이 시도되었다.
  • 그 결과, 위에 언급한 동작방식 중 각 프로시저가 요구하는 메커니즘만을 최소한으로 구현하는 최소주의자 전략으로 볼 수 있는 방식들을 따른다.
  • [우] 함수 호출을 지원하려면 기계적으로 이런 저런 준비 할게 많은데, 진짜 필요한 것만 준비해서 쓰자.
    • 스택 프레임 생성, 레지스터 백업, 스택에 저장, 스택 정리, 전부 다 필요할때만 고려하기로 하자.

 

3.7.1 런타임 스택

C언어를 포함한 다양한 언어에서의 프로시저 호출 동작방식의 주요 특징은, 스택 자료구조가 제공하는 후입선출 메모리 관리 방식을 활용 할 수 있다는 것이다.

• 우리는 프로시저 P가 Q를 호출하는 예제를 사용해, Q가 실행되고 있는 동안 P까지의 연속된 호출 중의 프로시저 P는 일시적으로 정지되는 것을 볼 수 있다.
  • Q가 실행되는 동안에는 자신의 지역변수를 위한 새로운 저장공간을 할당 할 수 있는 능력이나 다른 프로시저로의 호출을 설정하는 능력만을 필요로 한다.
  • 반대로, Q가 리턴 할 때에는 자신이 할당받은 로컬 저장장소는 반납 될 수 있다. 따라서 프로그램은 스택을 사용해서 프로시저들이 요구하는 저장장소를 관리 할 수 있다.
  • 또, 여기서 스택과 프로그램 레지스터들은 제어와 데이터를 전송하기 위해, 그리고 메모리를 할당하기 위해 필요한 정보를 저장한다.
• [우] 왜 스택을 써야하는가?
  • 상황 : 부모 함수 P가 실행중 -> 자식 함수인 Q를 호출
    • P는 잠시 멈추고, Q가 실행되면서 Q만의 공간, 정보가 필요해진다. 그리고 Q 실행이 끝나면 다시 자기 자원을 반납하고 P로 복귀하게 끔 한다.
    • 스택은 최근 호출한 함수가 가장 먼저 끝나고, 함수마다 필요한 만큼만 동적으로 할당이 가능하며, 스택 포인터만 되돌리면 정리가 끝나는 점으로 제일 적합하다.
• [우] 스택 동작 방식의 물리적인 부분, 즉 메모리 관점으로써 이야기 해보자.
  • 스택은 큰 주소에서 작은 주소 방향(탑 다운) 방식으로 성장하며, 스택 포인터 %rsp는 스택의 최상위 원소를 가리킨다.
  • 데이터를 읽기 위한 인스트럭션은 pushq 와 popq 이 있다.
  • 특정 값으로 초기화되지 않은 데이터를 위한 공간은 적당한 양의 스택 포인터를 감소시킴으로써 간단하게 할당 할 수 있다.
  • 할당은 스택 포인터를 감소 시킴으로써 이루어졌다면 반납은 스택 포인터를 증가시키면서 구현이 가능하다.
  • 64비트 프로시저가 레지스터들에 저장 할 수 있는 개수 이상의 저장공간을 필요로 할 때는 공간을 스택에 할당한다. 이 영역을 프로시저의 스택 프레임이라고 부른다.
    • 스택 프레임은 특정한 함수만을 위해 스택 위에 잠깐 동안 만들어지는 저장 공간이다.
      • 그럼 왜 필요하냐? : 64비트 프로시저에는 레지스터가 꽤 많은데, 이것도 모든걸 처리하기엔 한계가 있다. 그래서 스택까지 활용 하는 것이다.
       

일반적인 스택 프레임 구조

이것은 런타임 스택의 전체적인 구조이며, 이것을 다시 스택 프레임들로 나눈 가장 일반적인 형태를 보여주고 있다.

• 즉, 런타임 스택은 스택 프레임들의 모음이라고도 할 수 있다.

현재 실행 중인 프로시저에 대한 프레임은 항상 스택의 맨 위에 위치한다.

• 프로시저 P가 Q를 호출 할 때 리턴주소를 스택의 푸시해서, Q가 리턴 할 때 P 부분에서 재개되어야 하는 위치를 알려주게 된다.
  • 이 상황에서는, 리턴 주소가 P에 관계된 상태들을 저장하기 때문에 리턴주소는 P의 스택 프레임에 속하는 것으로 간주한다.
• 자식 함수인 Q에 대한 코드는 현재 스택 경계를 확장해서 자신의 스택 프레임을 위한 공간을 할당한다.
  • 이 공간 내에서 레지스터 값들을 저장하고, 지역변수들을 위한 공간을 할당하며, 자신이 호출하는 프로시저들을 위한 인자들을 설정 할 수 있다.
• 대부분의 프로시저의 스택 프레임들은 시작되면서 할당되는 고정 크기를 갖는다. 몇몇 프로시저는 가변크기의 프레임을 필요로 한다.
  • 프로시저 P는 최대 여섯 개의 정수 값들(포인터나 정수)을 레지스터로 전송 할 수 있다.
    • 하지만, 만일 Q가 더 많은 인자를 요구한다면 이들은 호출을 하기 전에 자신의 스택 프레임 내에 P에 의해 저장 될 수 있다.

시간과 공간 효율성을 위해 64비트 프로시저는 요청받은 스택 프레임의 부분만을 할당한다.

• 예를 들어, 많은 프로시저들은 여섯 개 이하 인자들을 가지며, 그래서 이들의 모든 매개변수들은 레지스터로 전달 될 수 있다.
• 그래서 앞에서 본 그림에 나타낸 스택 프레임들의 일부분은 생략 될 수 있다.
• 사실 많은 함수들은 스택 프레임을 요청하지도 않는다. 이런 경우는 모든 지역변수를 레지스터에 보관 할 수 있고, 이 함수가 다른 함수를 호출하지 않을 때 발생한다.

 

3.7.2 제어의 이동

제어를 funcP에서 funcQ로 전달 하는 것은 단순히 Program Counter를 Q를 위한 코드의 시작주소로 설정하는 것과 관련된다.

• 그렇지만, 나중에 Q가 리턴해야 할 때가 오면 프로세서는 P의 살행을 다시 시작해야하는 코드 위치의 일부 기록을 가지고 있어야한다.
• 이 정보는 64비트 머신에서는 인스트럭션 call Q로 프로시저 Q를 호출해서 기록된다.
• 이 인스트럭션은 주소 A를 스택에 푸시하고 PC를 Q의 시작으로 설정한다.
  • 푸시된 주소 A는 리턴 주소라고 불리며, call 인스트럭션 바로 다음 인스트럭션의 주소로 계산된다.
  • 이에 대응하는 인스트럭션 ret는 주소 A를 스택에서 pop해온 후, PC를 A로 설정한다.
  • call과 ret 인스트럭션의 일반적인 형태는 다음과 같이 설명된다.
  
  

  Instruction	Description
  call Label	Procedure Call
  call *Operand	Procedure Call
  ret	Return from call

  • objdump 를 거치면 callq, retq로 찍히는 경우도 있다.
  • call 은 호출된 프로시저가 시작하는 인스트럭션의 주소를 목적지로 갖는다. 점프와 유사하게 명령은 직접 또는 간접 형태를 갖는다.
  • 어셈블리 코드에서 직접 호출의 목적지는 레이블로 주어지는 반면, 간접 호출의 목적지는 ‘*’와 이전에 설명한(책에서 그림 3.3) 형식을 사용하는 식별자에 의해 주어진다.
• 이 그림은 앞에 3.2 챕터에서 언급되었던 main, multstore 함수에 대한 call, ret의 실행을 보여준다. 

이어서 보게 되는 것은 이 두 함수를 역 어셈블 한 일부이다.

• 이 코드에서, main의 주소 0x400563를 인자로 갖는 call은 함수 multstore를 호출한다. 이 상태가 위의 좀 더 추상적인 그림에 나와 있으며, 스택 포인터 %rsp 와 프로그램 카운터 %rip 의 값으로 표시된다.
  • call의 효과는 리턴 주소 0x400568을 스택에 저장하고, 0x400540(b)에 위치한 함수 multsotre의 첫 번째 인스트럭션으로 점프하는 것이다
  • 함수 multstore는 주소 0x40054d의 ret을 만날 때까지 실행된다.
    • 이 인스트럭션은 스택에서 0x400568을 pop해서 이 주소로 점프한 후에 call 바로 다음의 main의 실행을 재개한다.

제어를 프로시저로 전달하고, 프로시저로부터 전달받는 좀 더 상세한 그림을 볼 수 있는 아래 그림의 (a)부분을 보자.

• top을 호출하는 main 함수의 코드 일부분과 두 함수 top, leaf의 역 어셈블한 코드를 보여준다.
  • 각 인스트럭션은 L1-L2(leaf 에서), T1-T4(top 에서), main에서는 M1-M2 레이블로 식별된다.
  • 그림의 (b)에서는 코드 실행의 구체적인 추적과정을 보여주며, main 함수에서는 top(100)을 호출해서 top이 leaf(95)를 호출하게 한다.
    • 함수 leaf는 97을 top으로 리턴하며, 그 후 194를 리턴한다.
• 처음 세 개의 열은 인스트럭션 레이블, 주소, 인스트럭션 유형으로 실행 인스트럭션을 설명한다. 다음 네 개의 열은 레지스터를 %rdi, %rax, %rsp 스택 탑의 값으로 구성되며, 인스트럭션 실행 전의 프로그램 상태를 보여준다.
• 이 표의 값은 주의 깊게 보는 것이 좋다.
  • 이들이 프로시저 콜과 리턴을 지원하기 위해 필요한 저장공간을 관리하는 데 런타임 스택의 중요 역할을 시연하기 때문이다.
• leaf의 L1은 리턴되는 값 97을 %rax 에 설정한다. 그리고 L2는 리턴한다.
  • 0x400054를 스택에서 팝한다. 이 값으로 PC를 설정하고, 제어 이동은 T3의 top으로 돌아온다.
  • 이 프로그램은 leaf로의 호출과 top으로의 리턴을 성공적으로 완료했다.
• T3은 %rax 에 탑에서 리턴되는 값으로 194로 설정한다. T4는 이제 리턴한다.
  • 이것은 스택에서 0x4000560을 팝한다. 그리고 PC를 main의 M2로 설정한다.
  • 이 프로그램은 top으로의 호출과 main으로의 리턴을 완료했다.
  • 스택 포인터 또한 top로 호출되기 전 값인 0x7fffffffe820으로 복원된 것을 확인 하고 있다.
  • 이렇게 리턴 주소를 스택에 푸시하는 간단한 방법으로 함수가 나중에 적절한 위치로 리턴이 가능함을 확인했다.
    • C언어의 표준 콜/리턴 동장 방식은 스택이 제공하는 후입선출 메모리 관리 방식과 일치한다.

3.7.3 데이터 전송

호출 될 때, 그리고 프로시저가 다시 리턴하게 될 때 프로시저로 제어를 전달하는 것뿐만 아니라, 프로시저 콜은 데이터를 인자로 전달하는 것과 관련이 있다.

프로시저에서 리턴하는 것도 어떤 값을 리턴하는 것과 관련되어 있을 수 있다. 64비트에서 대부분의 이들 프로시저로, 프로시저로부터의 데이터 전달은 레지스터를 통해서 일어난다.

• 예를 들어, 우리는 수많은 함수 예제를 통해서 인자들이 레지스터 %rdi, %rsi 등으로 전달되고 값들이 레지스터 %rax 로 리턴되는 것을 이미 보아왔다.
  • 프로시저 P가 프로시저 Q를 호출 할 때, P에 대한 코드는 먼저 인자들을 적절한 레지스터들에 복사해야 한다.
  • 유사하게 Q가 P로 다시 리턴 할 때, P에 대한 코드는 리턴 값을 레지스터 %rax 에서 접근 할 수 있다.

64비트에서는 최대 여섯 개의 정수형 인자가 레지스터로 전달 될 수 있다.

이 레지스터들은 전달되는 데이터 형의 길이에 따라 레지스터 이름을 이용해서 정해진 순서로 이용된다. 이런 방식이 바로 이 그림에 반영되어 있다.

인자들은 인자 리스트에서 각자의 순서에 따라 이들 레지스터에 할당된다.
64비트보다 작은 인자들은 64비트 레지스터의 적절한 일부분을 이용해서 접근 할 수 있다.

예를 들어, 만일 첫 번째 인자가 32비트라면, %edi로 접근 할 수 있다.

함수가 여섯 개 이상의 정수형 인자를 가질 때, 다른 인자들은 스택으로 전달된다.
프로시저 P가 프로시저 Q를 n > 6인 n개의 정수형 인자를 가지면서 호출한다고 가정하자.

그러면, P에 대한 코드는 인자 7에서 n까지를 위한 충분한 크기의 저장공간을 스택 프레임에 할당해야 한다.
인자 1-6은 적절한 레지스터들에 복사하고, 인자 7에서 n까지는 인자 7을 스택 탑에 넣는 방법으로 저장한다.

매개변수들을 스택으로 전달 할 때, 모든 데이터 길이는 8의 배수로 반올림된다.

인자들이 배치되면, 프로그램은 프로시저 Q로 제어를 전달하기 위해 call 인스트럭션을 실행 할 수 있다.
프로시저 Q는 레지스터와 스택을 통해 자신의 인자들에 접근 할 수 있다.

만일 Q가 그 다음에 여섯 개가 넘는 인자를 갖는 어떤 함수를 호출하려면, 자신의 스택 프레임에 Argument build area 라고 이름 붙인 영역으로 이들을 위한 공간을 할당 할 수 있다.

인자 전달의 예제로, 뒤에서 나올 C함수 proc에 대해 생각해보자.

// C code.
void proc(long a1, long *a1p, int a2, int *a2p, short a3, short *a3p, char a4, char *a4p)
{
	*a1p += a1; *a2p += a2; *a3p += a3; *a4p += a4;
}

참고 테이블, a1 = %rdi | a1p = %rsi | a2 = %edx | a2p = %rcx | a3 = %r8w | a3p = %r9 | a4 = %rsp + 6 | a4p = %rsp + 16
proc:
	movq 16(%rsp), %rax
	addq %rdi, (%rsi)
	addl %edx, (%rcx)
	addw %r8w, (%r9)
	movl 8(%rsp), %edx
	addb %dl, (%rax)
	ret

이 함수는 여러 가지 크기의 정수(1, 2, 4, 8 바이트)와 각각 8 바이트 길이의 포인터형 인자를 포함하는 여덟 개의 인자를 갖는다.
또, proc에 의해 생성된 어셈블리 코드가 이어서 보여지고 있다. 첫 여섯 개의 인자들은 레지스터로 전달된다.
마지막 두 개의 인자는 아래 그림의 도형으로 문서화 한 것처럼 스택으로 전달된다.

 

이 도형은 proc의 실행 중에 스택의 상태를 보여준다. 프로시저 콜의 일부분으로 스택에 리턴 주소가 푸시되는 것을 알 수 있다.
이 두 개의 인자들은 따라서 스택 포인터 기준으로 위치 8과 16에 각각 저장되어 있다.
이 코드에서 오퍼랜드의 길이에 따라 여러 가지 버전의 ADD가 사용 된 것을 볼 수 있다 :

• long a1 에 addq
• int a2 에 addl
• short a3 에 addw
• char a4 에 addb
• 6번 줄의 movl 인스트럭션이 메모리에서 4바이트를 읽는다는 것을 살펴보자. 다음에 오는 addb는 단지 하위 바이트만을 활용 할 뿐이다.

 

3.7.4 스택에서의 지역 저장 공간

지금까지의 예제는 레지스터의 감당 가능한 것보다 더 많은 지역 저장소가 필요 없었지만, 가끔은 더 메모리까지 넘어가는 경우가 있다.
보통은 이럴 때가 해당된다 :

• 지역 데이터 모두를 저장하기에는 레지스터의 수가 부족하다.
• 지역변수의 연산자 ‘&’가 사용되었으며, 이 변수의 주소를 생성 할 수 있어야 한다.
• 일부 지역변수들이 배열 또는 구조체여서 이들이 배열이나 구조체 참조로 접근되어야 한다.

보통 프로시저는 스택 포인터를 감소시키면서 스택 프레임에 공간을 할당한다.

• 이렇게 하면 전에 봤던 스택 프레임 전체 그림에서 Local Variables 로 명명된 스택 프레임의 일부분이 생겨난다.
• 주소 연산자를 다루는 예제로 아래에 설명할 두 함수를 고려해보자.
  • 함수 swap_add 는 포인터 xp, yp로 이름 붙여진 값의 위치를 바꾸고 합을 리턴한다.
  • 함수 caller 는 지역변수 arg1, arg2의 포인터를 생성하고 이들을 swap_add로 전달한다.
  • 어셈블리 코드에서는 어떻게 caller가 스택 프레임을 이용해서 이들을 구현하는지를 보여준다.

 

long swap_add(long *xp, long *yp)
{
	long x = *xp;
	long y = *yp;
	*xp = y;
	*yp = x;
	return x + y;
}

long caller()
{
	long arg1 = 534;
	long arg2 = 1057;
	long sum = swap_add(&arg1, &arg2);
	long diff = arg1 - arg2;
	return sum * diff;
}

위 아래의 양쪽 예제를 통해 런타임 스택이 지역 저장소가 요구 될 때, 할당하고 함수의 수행이 완료되었을 때 이것을 반환하는 간단한 방식을 제공한다는 것을 알 수 있다.

 

caller:
	subq $16, %rsp
	movq $534, (%rsp)
	movq $1057, 8(%rsp)
	leaq 8(%rsp), %rsi
	movq %rsp, %rdi
	call swap_add
	movq (%rsp), %rdx
	subq 8(%rsp), %rdx
	imulq %rdx, %rax
	addq $16, %rsp
	ret

• caller를 위한 코드는 스택 포인터를 16 감소시키는 것으로 시작한다;
  • 이것은 결국 스택에 16바이트를 할당한다.
  • S를 스택 포인터의 값이라고 하면, 이 코드가 &arg2를 S+8(5번 줄로), &arg1을 S(6번 줄)로 계산한다는 것을 알 수 있다.
  • swap_add로의 호출이 완료되면, caller에 대한 코드는 스택에서 두 값을 가져와서(8-9) 차이를 계산하고, 이것을 swap_add가 레지스터 %rax 에 리턴하는 값으로 곱한다. (10)
  • 마지막으로 이 함수는 스택 포인터를 16 증가시킨 뒤 스택 프레임을 반환한다. (11)

더 복잡한 예제를 확인해보자.

call_proc:
	subq $32, %rsp
	movq $1, 24(%rsp)
	movl $2, 20(%rsp)
	movw $3, 18(%rsp)
	movb $4, 17(%rsp)
	leaq 17(%rsp), %rax
	movq %rax, 8(%rsp)
	movl $4, (%rsp)
	leaq 18(%rsp), %r9
	movl $3, %r8d
	leaq 20(%rsp), %rcx
	movl #2, %edx
	leaq 24(%rsp, %rsi)
	movl $1, %edi
	
	call proc
	movslq 20(%rsp), %rdx
	addq 24(%rsp), %rdx
	movswl 18(%rsp), %eax
	movsbl 17(%rsp), %ecx
	subl %ecx, %eax
	cltq
	imulq %rdx, %rax
	addq $32, %rsp
	ret

long call_proc()
{
	long x1 = 1; int x2 = 2; short x3= 3; char x4 = 4;
	proc(x1, &x1, x2, &x2, x3, &x3, x4, &x4);
	return (x1 + x2) * (x3 - x4);
}

이 예제는 지역변수를 위해 스택에 저장공간을 할당 해야하고, 8개의 인자를 갖는 함수 proc로 값들을 전달하는 함수를 보여준다.
이 함수는 아래 그림과 같이 스택 프레임을 생성한다.

• call_proc에 대한 어셈블리 코드를 살펴보면, 상당한 부분의 코드가 함수 proc을 호출하기 위한 준비를 위해 사용되는 것을 알 수 있다. (2-15 line) 이 부분은 지역변수와 함수 매개변수를 위해, 그리고 레지스터에 함수 인자들을 적재하기 위해 스택 프레임을 설정하는 것을 포함한다.
• 바로 윗 그림이 보여주는 것처럼 지역변수는 스택에 할당 되며 여러가지 크기를 갖는다.
• 프로시저 proc이 호출 될 때 이 프로그램은
  void proc(long a1, long *a1p, int a2, int *a2p, short a3, short *a3p, char a4, char *a4p) 을 실행 할 것이다.

인자 7과 8은 이제 스택 포인터 대비 오프셋 8과 16에 위치하는데, 리턴주소가 스택에 푸시 되었기 때문이다.
이 프로그램이 call_proc 으로 리턴 될 때, 이 코드는 네 개의 지역변수 값을 가져오고 (17-20번 줄) 최종 계산이 이루어진다.

• 스택 프레임 반환을 위해 32 감소시켜서 완성된다.

3.7.5 레지스터를 이용하는 지역 저장소

프로그램 레지스터들은 모든 프로시저들이 공유하는 단일 자원의 역할을 한다.

• 비록 어떤 한 순간에는 오직 하나의 프로시저만이 활성화 될 수 있지만, 하나의 프로시저가 다른 프로시저를 호출 할 때, 피호출자는 호출자가 나중에 사용할 계획인 일부 레지스터 값은 덮어쓰지 않는다.
  • 이 때문에 x86-64는 라이브러리에 있는 프로시저들을 포함한 모든 프로시저들이 준수해야 할 통일된 일련의 레지스터 사용관습을 채택하고있다.
  • 관습적으로 %rbx, %rbp, %r12 - %r15 는 피호출자-저장 레지스터로 구분한다.
    • 프로시저 P가 Q를 호출 할 때, Q는 Q가 P로 리턴될 때 Q가 호출되었을 때의 값들과 동일하도록 보장 할 수 있게 이 레지스터들의 값을 보존해야한다.
    • 프로시저 Q는 이 값을 전혀 변경하지 않거나, 원래의 값을 스택에 푸시해두고 이 값을 변경한다.
      • 그리고 리턴하기 전에 스택에서 이전 값을 팝해오는 방식으로 레지스터를 보존한다.
  • 레지스터 값들을 푸시하는 것은 스택 프레임에서 Saved Registers 이라고 이름 붙인 일부를 생성하는 효과를 갖는다.
    • P에 대한 코드는 피호출자-저장 레지스터에 안전하게 값을 저장 할 수 있으며, Q를 호출하고 이 값이 깨지는 위험 없이 레지스터에서 이 값을 사용 할 수 있게 된다.

스택 포인터 %rsp 를 제외한 다른 모든 레지스터들은 호출자-저장 레지스터로 구분된다.

• 이것은 이들이 함수에 의해 변경 될 수 있다는 것을 의미한다.
  • “호출자-저장”이라는 이름은 지역데이터를 레지스터에 보관하며, 프로시저 Q를 호출하는 프로시저 P의 문맥에서 이해 될 수 있다.
    • Q는 이 레지스터를 자유롭게 변경 할 수 있기 때문에, P가 호출하기 전에 먼저 데이터를 저장해야 할 의무가 있다.

long P(long x, long y)
{
	long u = Q(y);
	long v = Q(x);
	return u + v;
}

이 함수 P에 대해 생각해보자. Q를 두 번 호출하고 있다. 첫 번째 호출동안, x를 사용하기 위해 유지해야한다. 유사하게, 두번째 호출 때도 Q(y)의 결과인 u를 유지해야 한다. 오른쪽 코드를 보면, 어셈블리 코드에서는 두 개의 피호출자-저장 레지스터들을 사용한다는 것을 확인 할 수 있다.

이 함수의 시작부분에서 이 두 레지스터의 값을 스택에 보관한다. (2-3L)
Q로 두번 째 호출을 하기 전에 (8L) 이 호출의 결과를 %rbx 로 복사한다.
이것은 인자 x를 %rbp에 Q로 의 첫번 째 호출 이전에 복사한다. (5L)

이 함수의 마지막에서 (13-14L), 이 두개의 피 호출자-저장 레지스터들의 값을 스택에서 팝해와서 복원한다.

P:
	pushq %rbp
	pushq %rbx
	subq $8, %rsp
	movq %rdi, %rbp
	movq %rsi, %rdi
	call Q
	movq %rax, %rbx
	movq %rbp, %rdi
	call Q
	addq %rbx, %rax
	addq $8, %rsp
	popq %rbx
	popq %rbp
	ret

3.7.6 재귀 프로시저

레지스터와 스택을 사용하는 것에 대해 설명한 관습으로, 64비트 프로시저들이 이들을 재귀적으로 호출하는 것을 설명 할 수 있다.

• 각 프로시저 콜은 스택상에 자신만의 사적인 공간을 가진다. 따라서 다수의 별도의 호출들의 지역 변수들은 서로 간섭하지 않는다.
• 뿐만 아니라, 스택 운영 방식은 프로시저가 호출 될 때 지역 저장소를 할당하고, 리턴하기 전에 이것을 반환하는 적절한 정책을 자연스럽게 제공한다.

아래에서 설명할 코드는 재귀적인 팩토리얼 함수에 대한 생성된 어셈블리 코드를 보여준다.

long rfact(long n)
{
	long result;
	if (n <= 1)
		result = 1;
	else
		result = n * rfact(n-1);
	return result;
}

rfact:
	pushq %rbx
	movq %rdi, %rbx
	movl $1, %eax
	cmpq $1, %rdi
	jle .L35
	leaq -1(%rdi), %di
	call rfact
	imulq %rbx, %rax
.L35:
	popq %rbx
	ret

어셈블러 코드가 먼저 스택에 기존 값을 보관한 후 (2L)에 레지스터 %rbx 를 매개변수 n을 저장하기 위해 사용하며, 나중에 리턴하기 전에 그 값을 복원하는 것(11L)을 알 수 있다. 스택 운영방식과 레지스터 저장 관습으로 인해 언제 rfact(n-1)로의 호출이 리턴(9L) 할 때,

1. 호출의 결과가 레지스터 %rax 에 저장 될 것이라는 점.
2. 인자 n의 값이 레지스터 %rbx 에 보관될 것이라는 점을 확신 할 수 있다.

함수를 재귀적으로 호출하는 것도 다른 함수의 호출과 마찬가지로 진행되는 것을 알 수 있었다.

• 스택 기법을 사용해서 함수의 각 호출 시에 상태정보를 위한 자신만의 개별적 저장공간을 제공한다.
  • 필요한 경우에는, 지역변수를 위한 저장공간도 제공 할 수 있다.
• 스택의 할당과 반환 동작은 자연스럽게 함수의 호출-리턴 순서와 일치한다.
  • 이와 같은 함수 호출과 리턴을 구현하는 방법은 상호 재귀함수 (P → Q → P) 같은 보다 복잡한 형태에서도 동작한다.

 

3.8 배열의 할당과 접근

C에서 배열은 스칼라 데이터를 보다 큰 자료형으로 연계시키는 수단이다.

• C에서는 매우 단순한 구현 방법을 사용하고 있어서, 기계어로의 번역도 매우 손쉬운 편이다.
  • C 배열은 단순히 연속된 메모리 공간이다. 배열 이름 자체가 첫번째 원소 주소를 가리킨다.
    • arr[i]는 *(arr + i)와 같다고 생각 할 수 있다.
  • 반면에 Java, Python 등은 배열이 객체던가 리스트로, 주소 계산 방식은 아닌 편이다.
• C의 한 가지 특이한 점은 배열 원소들에 대한 포인터를 만들고, 이들 포인터 간에 연산을 할 수 있다는 점이다.
  • 이것은 기계어에서 주소 계산으로 번역된다.
• 최적화 컴파일러는 배열의 인덱스를 사용 할 때 필요한 주소 계산을 단순화하는데 특히 우수한 성능을 보인다.
  • 이 때문에, C 코드와 그 기계어 번역 간의 관계는 다소 해석하기 어려울 수 있다.

3.8.1 기본 원리

자료형 T와 정수형 상수 N에 대해서 다음과 같은 선언에 대해 고려해보자.

	T A[N];

시작하는 위치는 x_a라고 하자. 이 선언은 두 가지 효과를 갖는다.

• 첫째, 이것은 L * N 바이트의 연속적인 공간을 메모리에 할당하며, 여기서 L(바이트 단위)은 자료형 T의 크기를 나타낸다.
• 둘째, 위 선언문은 새로운 식별자 A 를 통해서 배열이 시작하는 위치의 포인터로 사용한다.
  • 이 포인터의 값은 x_a 이다. 배열의 각 원소는 0에서 N-1 사이의 정수형 인덱스를 사용해서 접근 할 수 있다.

[예시] 다음의 선언문을 확인해보자.

char A[12];
char *B[8];
int C[6];
double *D[5];

Array Element Size Total Size Start Address Element i

A	1	12	x_a	x_a + i
B	8	64	x_b	x_b + 8i
C	4	24	x_c	x_c + 4i
D	8	40	x_d	x_d + 8i

배열 A는 12개의 단일 바이트(char) 원소로 구성된다. 배열 C는 각각 4바이트씩 필요로 하는 6개의 정수로 구성된다. 배열 B와 D는 모두 포인터의 배열로, 배열의 원소는 각각 8바이트 크기를 갖는다.

x86-64의 메모리 참조 인스트럭션은 배열 접근을 간단히 하도록 설계되었다.

• 예를 들어, E가 정수형 데이터 값들의 배열이고, E[i]를 계산하려 한다고 하자.
• 여기서 E의 주소는 레지스터 %rdx에, i는 %rcx에 저장되어 있다.
• 그러며, 다음의 인스트럭션은 주소계산 x_e + 4i 를 수행하고, 메모리 위치를 읽어서 그 결과를 레지스터 %eax에 저장한다.

movl (%rdx, %rcx, 4), %eax

허용된 배율 값 1, 2, 4, 8은 기본 자료형들의 크기이다.

3.8.2 포인터 연산

C는 포인터 간의 연산을 허용하며, 계산된 값은 포인터가 참조하게 되는 자료형의 크기에 따라 그 값이 확대된다.

• 즉, 만일 p가 자료형 T의 데이터에 대한 포인터이고, p의 값을 x_p 라고 한다면, 수식 p+i는 x_p + L * i가 되며, 여기서 L은 자료형 T의 크기이다.
• 단항 연산자 ‘&’, ‘*’는 포인터의 생성과 역참조를 수행한다. 즉, 어떤 객체를 나타내는 식 Expr에 대해 &Expr은 그 객체의 주소를 주는 포인터이다. 주소를 나타내는 식 AExpr에 대해 *AExpr은 그 주소에 위치한 값을 준다.
  • 따라서 Expr과 *&Expr은 동일하다. 배열 첨자 계산 방식은 배열과 포인터에 모두 적용 될 수 있다.
    • 앞에서 언급했듯 배열 참조 A[i]는 *(A + i)와 동일하다. 이것은 i번째 배열 원소의 주소를 계산해서 이 메모리 위치에 접근한다.
  • 이전 예제의 크기를 좀만 더 키워서, 정수 배열 E의 시작주소와 정수 인덱스 i가 레지스터 %rdx와 %rcx에 각각 저장되어 있는 경우에 대해 생각해보자.
    • 아래는 E와 관련된 수식들을 보여준다. %eax (데이터를 위해) | %rax (포인터를 위해) 저장하는 각 수식의 어셈블리 코드 구현을 볼 수 있다.
  
  

  Expression	Type	Value	Assembly Code
  E	int *	x_e	movq %rdx, %rax
  E[0]	int	M[x_e]	movl (%rdx), %eax
  E[i]	int	M[x_e + 4i]	movl (%rdx, %rcx, 4), %eax
  &E[2]	int *	x_e + 8	leaq 8(%rdx), %rax
  E+i-1	int *	x+e + 4i - 4	leaq -4(%rdx, %rcx, 4), %rax
  *(E+i-3)	int	M[x_e + 4i - 12]	movl -12(%rdx, %rcx, 4), %eax
  &E[i] - E	long	i	movq %rcx, %rax

• 이 예제에서 배열 값들을 리턴하는 연산들이 자료형 int를 가지며, 그래서 4바이트 연산(movl)과 레지스터(%eax)와 연관된다는 것을 알 수 있다.
• 포인터를 리턴하는 연산들은 자료형 int * 를 가지며, 그래서 8바이트 연산 (leaq)과 레지스터들(%rax)과 연관된다.
• 마지막 예제는 결과 값을 자료형 long을 가지며, 값은 자료형의 크기로 두 개의 주소를 나눈 것과 같게 되는 결과를 가지므로 동일한 자료구조 내에서 두 포인터의 차를 계산 할 수 있음을 보여준다.

3.8.3 다중 배열

배열 할당과 참조에 관한 일반적인 원칙들은 배열의 배열, (2차원 배열)을 생성 할 때도 적용된다.

int A[5][3];

은 다음의 선언문과 동일하다.

typedef int row3_t[3];
row3_t A[5];

자료형 row3_t 는 세 정수의 배열로 정의된다.

• 배열 A는 다섯 개의 배열을 원소로 가지며, 이들 각각은 세 개의 정수로 저장하기 위해 12바이트를 필요로 한다. 배열의 총 크기는 4 * 5 * 3 = 60바이트이다.
• 다섯 개의 행과 세 개의 열을 갖는 2차원 배열로 볼 수 있으며, 참고 가능 영역은 A[0 - 4][0 - 2]까지이다. 배열의 모든 원소들은 메모리에 “행 우선” 순서로 저장된다.
  • A[0]으로 표시하는 모든 행 0 의 원소들 다음에 행 1(A[1])의 원소가 따라오는 방식으로 저장된다.
  • 이러한 저장 순서는 우리가 사용한 다중 선언의 결과이다. A를 다섯 개의 원소를 갖는 배열로 보면, 각각 세 개의 정수들의 배열로 따라오는 방식이다.
• 다차원 배열의 원소를 접근하기 위해서 컴파일러는 원하는 원소의 오프셋을 계산하는 코드를 생성한다.
  • 이후, 배열의 시작을 기본 주소로, 오프셋을 인덱스로 하는 MOV 인스트럭션을 사용한다.
  • 일반적으로 다음과 같이 선언된 배열에 대해서 T D[R][C];
  • 배열 원소 D[i][j]는 메모리 주소 &D[i][j] = x_d + L(C * i + j) 에 위치한다. [수식 3.1 ]
  • 여기서 L 은 자료형 T의 바이트 크기이다. 예를 들어 앞에서 정의한 5 * 3 정수 배열 A를 생각해보자.
  • x_a, i, j 는 %ebp 레지스터 %rdi, %rsi, %rdx에 각각 위치한다고 하자.
    • 그러면 배열의 원소 A[i][j]는 레지스터 %eax에 다음과 같은 코드에 의해 복사 될 수 있다:

    leaq (%rsi, %rsi, 2), %rax
    leaq (%rdi, %rax, 4), %rax
    movl (%rax, %rdx, 4), %eax
    

  이 코드는 원소의 주소를 x86-64 주소연산의 덧셈과 배율을 사용해서 xA + 12i + 4j = x_a + 4(3i + j) 형태로 계산하였다.

 

3.8.4 고정크기의 배열

C 컴파일러는 고정크기의 다차원 배열을 위한 코드에 대해 다양한 최적화를 수행 할 수 있다.

• 자료형 fix_matrix를 16 * 16 정수의 배열로 선언하였다고 하자:

#define N 16
typedef int fix_matrix[N][N];

/* Compute i, k of fixed matrix product. */
int fix_prod_ele (fix_matrix A, fix_matrix B, long i, long k)
{
	long j;
	int result = 0;
	
	for (j = 0; i < N; j++)
	{
		result += A[i][j] * B[j][k];
	}
	return result;
}

int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k)
{
	int *Aptr = &A[i][0];
	int *Bptr = &B[0][k];
	int *Bend = &B[N][k];
	int result = 0;
	
	do {
		result += *Aptr * *Bptr;
		Aptr++;
		Bptr += N;
	} while (Bptr != Bend);
	return result;
}

윗 코드는 배열 A와 B의 곱의 원소 i, k를 계산한다.

• 즉 A의 행 i와 B의 열 k의 내적을 계산한다.

GCC는 아랫 코드에서 함수로 나타낸 것처럼 C로 작성한 코드를 생성한다.

• 이 코드는 여러가지 영리한 최적화를 포함한다.
• 정수 인덱스 j를 제거하고 모든 배열 참조를 포인터 역참조로 변환한다. 이것은 :
  1. A의 행 i의 연속된 원소들을 가리키는 Aptr로 이름 붙인 포인터를 생성한다.
  2. B의 열 k 연속된 원소들을 가리키는 Bptr로 이름 붙인 포인터를 생성한다.
  3. 루프를 종료 할 때 Bptr이 갖게 될 값과 동일한 Bend라고 이름 붙인 포인터를 생성한다.
  • Aptr의 초기값은 C 수식 &A[i][0]로 주어지는 A의 행 i의 첫 번째 원소의 주소이다.
  • Bptr의 초기값은 C 수식 &B[0][k]로 주어지는 B의 열 k의 첫 번째 주소의 원소이다.
  • Bend의 값은 C 수식 &B[N][k]로 주어지는 B의 열 j의 (n + 1)번째 원소가 되는 인덱스이다.

아래 작성되는 내용은 함수 fix_prod_ele 에 대해 GCC가 생성한 실제 어셈블리 코드이다.

• %eax는 result | %rdi는 Aptr | %rcx는 Bptr | %rsi는 Bend를 저장한다.

fix_prod_ele:
	salq %6, %rdx
	addq %rdx, %rdi
	leaq (%rsi, %rcx, 4), %rcx
	leaq 1024(%rcx), %rsi
	movl $0, %eax
.L7:
	movl (%rdi), %edx
	imull (%rcx), %edx
	addl %edx, %eax
	addq $4, %rdi
	addq $64, %rcx
	cmpq %rsi, %rcx
	jne .L7
	rep; ret

 

3.8.5 가변크기 배열

역사적으로 C에서는 컴파일 시에 그 크기가 결정 될 수 있는 다차원 배열만을 지원해 왔다.

• 가변크기 배열을 원하는 프로그래머는 배열들을 위한 저장공간을 함수를 사용하여 할당해야했다.
• 다차원 배열을 1차원 배열들로 행 우선 인덱싱을 사용해서 명시적 변환이 필요했다.
• ISO C99에서, 배열의 차원을 배열이 할당 될 때 계산 될 수 있는 수식으로 할 수 있는 방법을 제안했다.
  • 가변크기 배열의 C 버전에서는 배열을 int A[expr1][expr2] 다음과 같이 선언 할 수 있다.
  • 배열의 차원은 선언 부분을 만날 때 수식 expr1과 expr2를 계산해서 결정된다.
  • 예를 들어, n * n 배열의 i, j 원소에 접근하는 함수를 이렇게 써볼 수 있다.

  int var_ele(long n, int A[n][n], long i, long j)
  {
  	return A[i][j];
  }
  

매개변수 n은 반드시 매개변수 A[n][n]보다 먼저 나와야 한다. 그래야 함수가 배열의 차원을 계산 할 수 있다.

• GCC는 이 역참조 함수에 대한 코드를 다음과 같이 생성한다.

var_ele:
	imulq %rdx, %rdi
	leaq (%rsi, %rdi, 4), %rax
	movl (%rax, %rcx, 4), %eax
	ret

이 코드는 원소 i, j의 주소를 x_a + 4(n * i) + 4j = x_a + 4(n * i + j) 로 계산한다. 이 주소 계산은

• 첫째, 레지스터 사용법이 추가된 인자 n으로 인해 변경된다는 점.
• 둘째, n * i를 계산하기 위해 leaq instrucion을 사용해서 3i를 계산할바에는 곱셈 instrucion이 사용된 2번 줄만 빼고는 고정 크기 배열에서와 유사하다.

따라서 가변크기 배열을 참조하기 위해서는 고정크기 배열의 결과를 약간만 일반화하면 된다.

• 동적 버전에서는 일련의 쉬프트와 더하기 대신에 i를 n으로 확대하기 위해 곱셈을 사용해야 한다.
• 일부 프로세서에서는 곱셈이 상당한 성능 저하를 가져오지만, 이 경우에는 어쩔 수 없다.

루프 내에서 가변크기 배열을 참조 할 때, 컴파일러는 접근하는 유형의 규칙성을 활용해서 종종 인덱스 계산을 최적화 할 수 있다.

• 아래에서 설명할 코드 중 윗 코드는 두 개의 n * n 배열 A과 B의 곱에서 i, k 원소를 계산하는 코드를 보여준다.
• 아래 코드는 GCC로 C로 재생성한 어셈블리 코드이다.
• 이 코드는 더 앞에서 언급했던 고정 크기 배열에 대해 최적화된 코드랑 다른 유형을 따른다.
  • 이것은 두 개 함수에 대한 근본적인 요구사항이라기 보다는 컴파일러의 선택에 따른 부산물이다.
  • 쉽게 말해서, 컴파일러가 그냥 괜찮아 보이는걸 고른 것이지, 필수적인 영역이 선택된게 아니다.

.L24:
	movl (%rsi, %rdx, 4), %r8d
	imull (%rcx), %r8d
	addl %r8d, %eax
	addq $1, %rdx
	addq %r9, %rcx
	cmpq %rdi, %rdx
	jne .L24

이 프로그램에서는 확장된 값 4n(레지스터 %r9)을 Bptr을 증가시키는 데 사용하며,
n의 값(레지스터 %rdi)은 루프의 경계를 체크하기 위해 사용한다.
두 값이 왜 필요한지는 포인터 산술연산 배율때문에 이 C 코드에서는 드러나지 않는다.

최적화를 활성화하여 GCC가 프로그램이 다중배열이 원소들을 접근 할 때 발생하는 패턴을 인식 할 수 있다는 것을 살펴보았다.
컴파일러는 그 후 [수식 3.1]을 직접 응용해서 발생 했을 곱셈을 회피하는 코드를 생성 할 수 있다. 이러한 최적화들은 프로그램 성능을 상당히 개선하게 된다.

// 초기 C 코드
int var_prod_ele(long n, int A[n][n], int B[n][n], long i, long k)
{
	long j;
	int result = 0;
	
	for (j = 0; j < n; j++)
	{
		result += A[i][j] * B[j][k];
	}
		return result;
	}
	

// 최적화 된 C 코드
int var_prod_ele_opt(long n, int A[n][n], int B[n][n], long i, long k)
{
	int *Arow = A[i];
	int *Bptr = &B[0][k];
	int result = 0;
	
	long j;
	for (j = 0; j < n; j++)
	{
		result += Arow[j] * *Bptr;
		Bptr += n;
	}
	return result;
}

 

3.9 이기종 자료구조

C는 서로 다른 유형의 객체를 연결해서 자료형을 만드는 두 가지 방법을 제공한다.

• struct 키워드를 사용해서 선언하는 구조체는 다수의 객체를 하나의 단위로 연결한다.
• 키워드 union으로 연결하는 공용체는 하나의 객체를 여러 개의 다른 자료형으로 참조 될 수 있도록 한다.

3.9.1 구조체

C struct 선언은 서로 다른 유형의 객체들을 객체 하나로 묶어주는 자료형을 생성한다.

• 하나의 구조체 내의 서로 다른 컴포넌트들은 이름을 이용해서 참조된다.
• 구조체의 구현은 구조체의 모든 컴포넌트들이 메모리의 연속된 영역에 저장되게 한다.
• 구조체의 포인터가 첫 번째 바이트의 주소라는 점에서는 배열과 유사하다.
• 컴파일러는..
  • 각 필드의 바이트 오프셋을 가리키는 각 구조체 유형에 관한 정보를 관리한다.
  • 메모리 참조 인스트럭션에서의 변위로, 이 오프셋을 사용하여 구조체 원소 참조를 생성한다.

struct rec {
	int i;
	int j;
	int a[2];
	int *p;
}

위에서 본 이 구조체는 네 개의 필드를 갖는다.

• 두 개의 4바이트 int, 두 개의 4바이트 정수로 이루어진 배열, 8바이트 정수형 포인터. 총 24바이트

• 배열 a가 구조체에 들어있는 점에 주목해 보자. 그럼 상단에 표시한 숫자들은 구조체에서의 위치를 오프셋으로 표시한 것이다.
  • 구조체의 각 필드에 접근하기 위해서는 컴파일러는 구조체 주소에 적절한 오프셋 값을 더하는 코드를 생성한다. 예를 들어, struct rec* 자료형의 변수 r이 레지스터 %di에 저장된다고 가정하자. 그러면, 다음의 코드는 r→i 필드를 r→j로 복사한다.

movl (%rdi), %eax
movl %eax, 4(%rdi)

필드 i의 오프셋이 0이기 때문에 이 필드의 주소는 간단히 r의 값이다.

• 필드 j에 저장하기 위해서 코드는 r의 주소에 오프셋 4를 더해준다.
• 구조체 내 객체의 포인터를 생성하기 위해서 필드의 오프셋을 구조체의 주소에 더해준다.
• 예를 들어, 포인터 &(r→a[1])은 오프셋 8 + 4 * 1 = 12를 더해서 얻는다.
• 레지스터 %rdi 에 저장된 포인터 r과 레지스터 %rsi 의 long integer 변수에 대해서는 포인터 &(r->a[i]) 를 다음과 같이 한 개의 인스트럭션으로 생성 할 수 있다.

leaq 8(%rdi, %rsi, 4), %rax

하나 더, r->p = &r->a[4->i + r->j]; 라는 코드는 r 값이 레지스터 %rdi 에 저장된 상태로 다음과 같이 구현된다.

			movl 4(%rdi), %eax
			addl (%rdi), %eax
			cltq
			leaq 8(%rdi, %rax, 4), %rax
			movq %rax, 16(%rdi) 

위 예제들에서 나타난 것과 같이, 구조체에서 다른 필드를 선택하는 것은 컴파일 시에 완벽하게 처리된다.
기계어 코드는 필드 선언, 이름에 관한 정보를 포함하지 않는다.

3.9.2 공용체

공용체(Union)은 C언어의 자료형 체제를 회피해서 하나의 객체가 다수의 자료형에 따라 참조 될 수 있도록 해준다.

• 공용체를 선언하는 문법은 구조체와 동일하나, 그 의미는 매우 다르다.
• 다른 필드들이 메모리의 다른 블록을 참조하는 것이 아니라, 동일한 블록을 참조한다.
• 다음의 선언문을 한번 보자.

union U3
{
	char c;
	int i[2];
	double v;
};

struct S3
{
	char c;
	int i[2];
	double v;
};

x86-64 리눅스 컴퓨터에서 컴파일 될 때, S3, U3 필드의 오프셋 크기는 다음과 같다.

Type	c	i	v	Size
S3	0	4	16	24
U3	0	0	0	8

공용체 U3 * 자료형의 포인터 p에 대해서 p→c | p→i[0] | p→v 같은 참조들은 모두 자료구조의 시작 부분을 참조하게 된다.
또한 공용체의 전체 크기는 구성하는 필드 중에서 크기가 가장 큰 것과 동일하게 된다는 점을 발견 할 수 있다.

• 공용체는 여러 가지 측면에서 유용 할 수 있지만..
  • C언어의 자료형 체제에서 제공하는 안전망을 피해가기 때문에 오히려 치명적인 버그를 발생 시킬 수도 있다.
• 한 가지 응용은 어떤 자료구조의 서로 다른 두 개의 필드를 상호 배타적으로 사용한다는 점을 미리 알고 있는 경우이다.
  • 이 경우에는 구조체보다는 공용체로 이 두 개의 필드를 선언하면 전체 할당 된 공간을 줄일 수 있다.
  • 예를 들어, 각 잎새 노드는 값을 가지며 각 내부 노드들은 데이터 값 없이 두 개의 자식 노드의 포인터를 갖는 이진 트리 구조체를 구현하다고 하자.

struct node_s
{
	struct node_s *left;
	struct node_s *right;
	double data[2];
};

이렇게 선언한다면, 각 노드는 32바이트가 소요되고, 이 중에 절반은 각 노드에서 낭비된다.

• 반면에, 만일 노드를 다음과 같이 선언한다면, 모든 노드는 단 16바이트만을 필요로 한다.

union node_u
{
	struct {
		union node_u *left;
		union node_u *right;
	} internal;
	double data[2];
};

만일 n이 union node_u * 타입의 노드라면,

• 잎새 노드의 데이터를 n→data[0] 형태로 참조하며, 내부 노드의 자식들은 n→internal.left와 n→internal.right로 참조 할 수 있다.

이런 인코딩 방식을 사용하면 주어진 노드가 잎새 노드인지 내부 노드인지 구분 할 수 없다. 일반적인 방법으로는 공용체에서 다른 여러 가지 선택을 정의하는 열거형(enumerated) 자료형을 사용하고, 태그 필드와 공용체를 포함하는 구조체를 만드는 것이다.

typedef enum { N_LEAF, N_INTERNAL } nodetype_t;

struct node_t {
	nodetype_t type;
	union {
		struct {
			struct node_t *left;
			struct node_t *right;
		} internal;
		double data[2];
	} info;
};

이 구조체는 총 24바이트를 필요로 한다.

• 4바이트를 type, 8바이트를 각각 info.internal.left | right 또는 16바이트를 info.data에 사용한다.
• 이 경우, 공용체를 사용해서 얻는 이득은 최종 코드가 이상해진다는 점을 고려하면 비교적 크지 않다.
  • 필드가 더 많은 자료구조에서는 이러한 이득이 더 중요 할 수 있다.

공용체는 서로 다른 자료형들의 비트 패턴에 접근하는 데도 사용 될 수 있다.

• 예를 들어, 다음 코드는 double에서 unsigned long 타입의 값을 생성한다:

unsigned long u = (unsigned long) d;

값 u는 d의 정수 표현이 된다. d가 0.0인 경우를 제외하고, u의 비트 표현은 d와는 매우 다른 것이 된다.

• 이제 double에서 unsigned long 형의 값을 생성하는 다음의 코드를 보자.

unsigned long double2bits(double d)
{
	union {
		double d;
		unsigned long u;
	} temp;
	temp.d = d;
	return temp.u;
};

 

이 코드에서 인자를 공용체에 한 개의 자료형을 이용해서 저장하고, 다른 하나를 이용해서 접근한다.

• 결과적으로 u는 부호비트, 지수, 유효숫자 필드를 포함해서 d와 동일한 비트 표현을 갖게된다.
• u의 숫자 값은 d가 0.0인 경우 외에는 d의 값과는 연관성이 없게 된다.

서로 다른 크기의 자료형들을 한데 묶기 위해 공용체를 사용 할 때는 바이트 순서 문제가 중요해 질 수 있다.

• 예를 들어, 두 개의 4바이트 unsigned로 주어진 비트 패턴을 사용해서 8바이트 double을 만드는 프로시저를 작성한다고 하자.

double uu2double(unsigned word0, unsigned word1)
{
	union {
		double d;
		unsigned u[2];
	} temp;
	
	temp.u[0] = word0;
	temp.u[1] = word1;
	return temp.d;
}

x86-64 같은 리틀 엔지안 컴퓨터에서 인자 word0은 d의 낮은 순서 4바이트가 되지만, word1은 높은 순서 4바이트가 된다.

• 빅 엔디안 컴퓨터에서는 두 인자의 역할이 뒤바뀐다.
• [!!] 뭐가 빅이고 리틀인지 구분해야 함

 

3.9.3 데이터의 정렬

많은 컴퓨터 시스템들은 기본 자료형들에 대해 사용 가능한 주소를 제한하고 있다.

• 어떤 객체의 주소는 어떤 값(K)의 배수가 되도록 요구한다.
  • 이러한 정렬제한은 프로세서와 메모리 시스템 간의 인터페이스를 구성하는 하드웨어의 설계를 단순화 한다.
  • 예를 들어, 어떤 프로세서는 항상 8의 배수인 주소로 메모리에서 8바이트를 인출한다고 하자. 만일 모든 double 값이 주소가 8의 배수로 정렬된다고 보장 할 수 있다면, 이 값은 하나의 메모리 연산으로 읽거나 쓸 수 있다.
  • 그렇지 않다면, 객체가 두 개의 8바이트 메모리 블록에 걸쳐서 나누어져 있을 수 있으므로 메모리에 두 번 접근해야 할 수 있다.
• x86-64 하드웨어는 데이터의 정렬과 상관없이 정확하게 동작 할 것이다.
  • 그러나 인텔은 메모리 시스템 성능을 개선하기 위해서 데이터가 정렬될 것을 추천한다.
  • 이들 정렬 규칙은 모든 K의 원시 객체들은 K의 배수를 주소로 가져야 한다는 원칙에 기초한다.
    이 규칙이 다음과 같은 정렬을 의미한다는 것을 알 수 있다.
    

    K	Types
    1	char
    2	short
    4	int, float
    8	long, double, char *

  • 정렬은 자료형 내의 모든 객체들이 각각의 정렬 제한사항을 만족하는 방법으로 조직되고 할당되도록 강요된다.
  • 컴파일러는 어셈블리 코드에 디렉티브들을 삽입하여 전역 데이터를 위하여 원하는 정렬을 표시한다.
    • 예를 들어, 226쪽의 점프 테이블(챕터 3.6 내용 일부)에서는 .align 8 이라는 디렉티브를 포함하는 내용이 있다.
    • 이것은 다음에 오는 데이터가 8의 배수인 주소로 시작하도록 보장해준다. 각 테이블의 원소가 8바이트 길이를 가지므로, 다음의 원소들은 8바이트 정렬 제한을 준수 할 것이다.
    • 구조체가 관련된 코드에서 컴파일러는 구조체의 각 원소들이 각각의 정렬 요구사항을 만족하도록 필드 할당 시 빈 공간을 삽입한다.
      • 그러면 구조체는 자신의 시작주소가 가져야 하는 정렬 요건이 정해진다.

예를 들어 다음의 구조체 선언을 살펴보자.

struct S1
{
	int i;
	char c;
	int j;
};

왼쪽의 코드를 보았다면, 연이어 컴파일러가 다음의 그림에 표시한 것과 같이 최소 크기인 9바이트 할당을 사용 했다고 가정하자.

그러면, 필드 i(오프셋 0)와 j(오프셋 5) 모두에 대해 4바이트 정렬 요건을 만족시키는 것은 불가능해진다.

• 대신에 컴파일러는 필드 C와 j 사이에 3바이트 공간을 삽입한다 : 아래와 같이.
• 질문, 왜 하필 c에 배정하기로 선택했을까? 넣을 곳이 거기밖에 없다.

그 결과 j는 오프셋 8을 가지게 되고, 전체 구조체의 크기는 12바이트가 된다.

• 뿐만 아니라, 컴파일러는 모든 struct S1* 형의 포인터 p가 4바이트 정렬을 만족하도록 보장해준다.
• 이전의 표시 방법을 사용해서 포인터 p가 값 x_p를 갖는다고 하자. 그러면 x_p는 4의 배수가 되어야 한다. [왜??]
• 이것은 p→i(주소 x_p)와 p→j(주소 x_p + 8) 모두 각각의 4바이트 정렬 요건을 만족하도록 보장해준다.
• 추가로, 컴파일러는 구조체의 마지막에 0을 채워서 구조체 배열에서 각 원소가 각각의 정렬 요건을 만족하도록 해준다.
  • 예를 들어, 다음의 구조체 선언을 살펴보자.

struct S2
{
	int i; int j; char c;
}

 

만일 이 구조체를 9바이트 내에 저장하려 한다고 생각해보자.

• 구조체의 시작주소가 4바이트 정렬 요건을 만족시키도록 해서 필드 i, j에 대한 정렬 요건을 여전히 만족 시킬 수 있다.
• 그렇지만, 다음의 선언문을 보자. struct S2 d[4];
  • 9바이트 할당을 사용한다면 d의 각 원소들의 정렬 요건을 만족시킬 수 없다.
  • 왜냐하면 이 원소들은 x_d, x_d + 9, x_d + 18, x_d + 27의 주소를 갖기 때문이다.
  • 그 대신에 컴파일러는 구조체 S2에 대해서 마지막 3바이트를 낭비하는 공간으로 추가해서 12바이트를 할당한다.

 

이 방법을 사용해서 d의 원소들은 x_d, x_d + 12, x_d + 24, x_d + 36을 주소로 갖는다.

• x_d가 4의 배수를 만족하면, 모든 정렬제한은 만족 될 수 있다.