C/C++와 Rust의 최적화를 가능하게 하는 고수준 메모리 모델 관점에서, 포인터가 왜 단순한 정수가 아니며 바이트도 단순한 8비트 값이 아님을 설명한다. 포인터 동등성, one-past-the-end 규칙, restrict, 포인터 모델, 포인터-정수 캐스트의 난점, 그리고 미초기화 메모리를 표현하기 위한 바이트 표현(비트/포인터 조각/미초기화)을 다룬다.
This summer, I am again working on Rust full-time, and again I will work (amongst other things) on a “memory model” for Rust/MIR. However, before I can talk about the ideas I have for this year, I have to finally take the time and dispel the myth that “pointers are simple: they are just integers”. Both parts of this statement are false, at least in languages with unsafe features like Rust or C: Pointers are neither simple nor (just) integers.
I also want to define a piece of the memory model that has to be fixed before we can even talk about some of the more complex parts: Just what is the data that is stored in memory? It is organized in bytes, the minimal addressable unit and the smallest piece that can be accessed (at least on most platforms), but what are the possible values of a byte? Again, it turns out “it’s just an 8-bit integer” does not actually work as the answer.
I hope that by the end of this post, you will agree with me on both of these statements. :)
포인터는 단순히 정수일 뿐이라는 주장에 무슨 문제가 있을까? 다음 예제를 보자:
(여기서는 C++ 코드를 사용한다. 러스트보다 C++에서 unsafe 코드를 더 쉽게 쓸 수 있고, 이런 문제가 드러나는 곳이 바로 unsafe 코드이기 때문이다. C에도 같은 문제가 있으며, unsafe Rust도 마찬가지다.)
int test() {
auto x = new int[8];
auto y = new int[8];
y[0] = 42;
int i = /* some side-effect-free computation */;
auto x_ptr = &x[i];
*x_ptr = 23;
return y[0];
}
마지막 y[0] 읽기를 그냥 42를 반환하도록 최적화할 수 있다면 좋을 것이다. C++ 컴파일러는 이런 최적화를 자주 수행하는데, 고품질의 어셈블리를 생성하는 데 중요하기 때문이다. 이 최적화의 근거는 x를 가리키는 x_ptr에 쓰기를 해도 y가 바뀌지 않는다는 사실이다.
하지만 C++이 얼마나 저수준 언어인지 감안하면, 실제로 i를 y-x로 설정해서 이 가정을 깰 수 있다. &x[i]는 x+i와 같으므로, 실제로는 &y[0]에 23을 쓰게 된다.
물론 그렇다고 해서 C++ 컴파일러가 이런 최적화를 멈추지는 않는다. 이를 허용하기 위해 표준은 우리의 코드를 정의되지 않은 동작으로 만든다.
우선, 시작한 배열의 양 끝을 벗어나는 포인터 산술(&x[i] 같은)을 수행하는 것은 허용되지 않는다. 우리의 프로그램은 이 규칙을 위반한다. x[i]는 x의 범위를 벗어나므로, 이는 UB다. 명확히 하자면, x_ptr을 계산하는 것만으로도 이미 UB이며, 이 포인터를 사용 하려는 부분까지 가지도 못한다
하지만 아직 끝이 아니다. 이 규칙에는 우리가 유리하게 쓸 수 있는 특별한 예외가 있다. 산술 결과가 할당의 끝을 막 지난 포인터가 된다면, 그 계산은 허용된다. (이 예외는 흔한 C++98 이터레이터 루프에서 vec.end()를 계산하는 것을 허용하기 위해 필요하다.)
그렇다면 예제를 조금 바꿔 보자:
int test() {
auto x = new int[8];
auto y = new int[8];
y[0] = 42;
auto x_ptr = x+8; // one past the end
if (x_ptr == &y[0])
*x_ptr = 23;
return y[0];
}
이제 x와 y가 서로 바로 이웃 해 있고, y가 더 높은 주소에 할당됐다고 상상해 보자. 그러면 x_ptr은 실제로 y의 시작 을 가리킨다! 조건은 참이 되고 쓰기가 일어난다. 그래도 범위를 벗어난 포인터 산술로 인한 UB는 없다.
이는 최적화를 깨뜨리는 것처럼 보인다. 하지만 C++ 표준에는 컴파일러 제작자를 돕는 또 다른 장치가 있다. 위의 x_ptr을 실제로 사용 하는 것을 허용하지 않는 것이다. 표준의 포인터에 대한 덧셈에 대한 설명에 따르면, x_ptr은 “배열 객체의 마지막 원소 바로 뒤”를 가리킨다. 비록 동일한 주소를 가진다 해도 실제로 다른 객체의 원소를 가리키지는 않는다. (적어도 이것이 표준에 대한 일반적인 해석이며, 이에 기반해 LLVM은 이 코드를 최적화한다.)
여기서 핵심은, x_ptr과 &y[0]이 같은 주소 를 가리킨다고 해서 그것들이 같은 포인터 라는 뜻은 아니라는 점이다. 즉, 서로 바꿔 쓸 수 없다. &y[0]은 y의 첫 원소를 가리키고, x_ptr은 x의 끝을 지난 위치를 가리킨다. *x_ptr = 23을 *&y[0] = 23으로 바꾸면, 비록 두 포인터가 동등 비교를 통과했다 하더라도 프로그램의 의미는 달라진다.
다시 한 번 강조하자면:
두 포인터가 같은 주소를 가리킨다고 해서, 그것들이 동일하며 서로 바꿔 쓸 수 있다는 뜻은 아니다.
이게 미묘하게 들린다면 실제로 그렇다. 사실, 이는 LLVM과 GCC 모두에서 여전히 오컴파일을 일으킨다.
또한 이 one-past-the-end 규칙만이 C/C++에서 이 효과를 볼 수 있는 유일한 곳은 아니다. 또 다른 예로 C의 restrict 키워드는 포인터가 서로 앨리어싱하지 않음을 표현한다:
int foo(int *restrict x, int *restrict y) {
*x = 42;
if (x == y) {
*y = 23;
}
return *x;
}
int test() {
int x;
return foo(&x, &x);
}
test()를 호출하면 foo 안의 두 접근이 서로 앨리어싱해서는 안 되므로 UB가 트리거된다. foo에서 *y를 *x로 바꾸면, 더 이상 UB가 없는 의미로 프로그램이 바뀐다. 즉 다시 말해, x와 y가 같은 주소를 가진다 해도 서로 바꿔 쓸 수 없다.
포인터는 결정적으로 정수가 아니다.
그렇다면 포인터란 무엇 인가? 이에 대한 완전한 답은 나도 모른다. 사실, 이는 활발한 연구 주제다.
여기서 강조하고 싶은 중요한 점은 우리가 찾는 것이 포인터의 추상적 모델 이라는 것이다. 물론 실제 기계에서는 포인터가 정수다. 하지만 실제 기계는 현대 C++ 컴파일러가 수행하는 종류의 최적화를 하지 않으므로, 그렇게 해도 된다. 위의 프로그램을 어셈블리로 작성했다면 UB도 없고 최적화도 없었을 것이다. C++와 Rust는 메모리와 포인터에 대해 더 “고수준”의 관점을 취해, 최적화를 위해 프로그래머를 제약한다. 이러한 언어에서 프로그래머가 무엇을 해도 되고 해서는 안 되는지를 형식적으로 설명할 때, 앞서 보았듯 포인터=정수 모델은 무너진다. 따라서 다른 것을 찾아야 한다. 이는 명세 목적을 위해 실제 기계와 다른 “가상 기계”를 사용하는 또 다른 예로, 이에 대해서는 예전에 블로그에 쓴 바 있다.
간단한 제안을 하나 하자(실제로 이는 CompCert와 나의 RustBelt 작업에서 사용된 포인터 모델이며, miri가 포인터를 구현하는 방식이기도 하다): 포인터는 할당 을 고유하게 식별하는 어떤 종류의 ID와, 그 할당 내의 오프셋 쌍이다. 이를 러스트로 정의한다면 대략 이렇게 쓸 수 있다.
struct Pointer {
alloc_id: usize,
offset: isize,
}
포인터에 정수를 더하거나 빼는 것은 오프셋에만 작용하므로, 할당을 벗어날 수 없다. 포인터끼리의 뺄셈은 두 포인터가 같은 할당을 가리킬 때에만 허용된다(이는 C++과 일치한다).4
결국(그리고 miri가 보여주듯) 이 모델은 상당히 유용하다. 우리는 항상 포인터가 어느 할당을 가리키는지 기억하므로, 한 할당의 “끝을 지난” 포인터와 다른 할당의 시작을 가리키는 포인터를 구분할 수 있다. miri가 두 번째 예제(&x[8])가 UB임을 감지하는 방식이 바로 이것이다.
이 모델에서 포인터는 정수가 아니지만 적어도 단순하다. 하지만 포인터-정수 캐스트를 고려하면 이 단순한 모델은 금세 무너진다. miri에서는 포인터를 정수로 캐스팅해도 실제로는 아무 일도 일어나지 않는다. 이제 정수 변수(즉, 타입 이 정수)인데 값 은 포인터(즉, 할당-오프셋 쌍)인 셈이다. 하지만 그 “정수”를 2로 곱하면 오류가 난다. 이런 추상 포인터를 2로 곱하는 것이 무엇을 의미하는지 전혀 명확하지 않기 때문이다.
이는 언어 의미를 정의할 때 좋은 해결책이 아님 을 분명히 해 두고 싶다. 다만 인터프리터에는 잘 작동한다. 우리가 이렇게 하는 이유는, 무엇을 해야 할지 명확하지 않기 때문이다(이 캐스트를 아예 지원하지 않는 것 외에는 — 하지만 이렇게 하면 miri가 더 많은 프로그램을 실행할 수 있다). 우리의 추상 기계에는 모든 할당이 사는 단일하고 일관된 “주소 공간”이 없다. 즉, 모든 포인터를 서로 다른 정수에 매핑할 수 있는 그런 공간이 없다. 각 할당은 (관측 불가능한) ID로만 식별된다. 이제 이 모델을 각 할당에 대한 베이스 주소 같은 추가 데이터로 풍부하게 만들고, 정수를 포인터로 다시 캐스팅할 때 이를 어떻게든 사용하게 만들 수는 있겠다… 하지만 거기서부터 정말 복잡해지며, 어차피 이 글의 요점은 그런 모델을 논하는 것이 아니다. 요점은 그런 모델이 필요 하다는 점을 논하는 것이다. 관심이 있다면, 위 아이디어(베이스 주소 추가)를 탐구한 이 논문을 읽어 보길 권한다.
요컨대, 포인터-정수 캐스트는 위에서 논한 최적화까지 고려하면 지저분하고 형식적으로 정의하기 어렵다. 최적화를 가능하게 하는 고수준 관점과, 포인터를 정수로 캐스팅했다가 다시 되돌리는 것을 설명하는 데 필요한 저수준 관점 사이에 충돌이 있다. 우리는 miri에서 이 문제를 대체로 무시하고, 사용 중인 단순한 모델에서 가능한 만큼 기회주의적으로 처리한다. 물론 C++이나 Rust 같은 언어의 완전한 정의는 이런 지름길을 쓸 수 없고, 실제로 무엇이 일어나는지 설명해야 한다. 내 지식으로는 만족스러운 해법은 아직 없지만, 학계 연구가 점점 가까워지고 있다.
Update: 이것은 결코 C 전반에 대한 학술 연구를 포괄적으로 나열하려는 의도가 아니다. 정수-포인터 캐스트와 최적화의 상호작용에 직접 초점을 맞춘 다른 연구는 알지 못하지만, C의 형식화에 관한 주목할 만한 작업으로는 KCC, Robbert Krebber의 박사학위 논문, Cerberus가 있다. /Update
이것이 포인터가 단순하지도 않은 이유다.
정수만이 C++이나 (unsafe 부분의) Rust 같은 저수준 언어를 형식적으로 명세할 때 고려해야 할 데이터가 아니라는 점을 설득력 있게 보여주었길 바란다. 하지만 이는 메모리에서 바이트를 로드하는 것 같은 단순한 연산이 단지 u8을 반환할 수만은 없다는 뜻이기도 하다. 예를 들어, 소스의 모든 바이트를 차례로 어떤 지역 변수 v에 로드한 다음 타깃에 저장하는 방식으로 memcpy를 구현한다고 상상해 보자. 그 바이트가 포인터의 일부라면 어떻게 될까? 포인터가 할당과 오프셋의 쌍이라면, 그 첫 번째 바이트는 무엇인가? 우리는 v의 값을 말해야 하므로, 이 질문에 답할 방법을 찾아야 한다. (그리고 이것은 앞 절에서 나온 곱셈 문제와는 완전히 별개의 이슈다. 여기서는 어떤 추상 타입 Pointer가 있다고 가정한다.)
포인터의 바이트 하나를 0..256의 원소로 표현할 수는 없다. 본질적으로, 순진한 메모리 모델을 사용하면, 포인터가 메모리에 저장되었다가 다시 로드될 때 포인터가 “그저 정수 이상의 무엇”이게 하는 추가적인 “숨은” 부분이 사라진다. 이를 바로잡아야 하며, 따라서 “바이트”의 개념을 확장해 그 추가 상태를 수용해야 한다. 즉, 바이트는 이제 0..256의 원소(“날 비트”) 이거나, 어떤 추상 포인터의 n번째 바이트가 된다. 메모리 모델을 러스트로 구현한다면 대략 다음과 같을 것이다:
enum ByteV1 {
Bits(u8),
PtrFragment(Pointer, u8),
}
예를 들어, PtrFragment(ptr, 0)는 ptr의 첫 번째 바이트를 나타낸다. 이렇게 하면 memcpy는 메모리에 있는 포인터를 구성하는 개별 바이트로 포인터를 “분해”해 별도로 복사할 수 있다. 32비트 아키텍처에서 ptr을 나타내는 전체 값은 다음 4개의 바이트로 구성된다:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
이런 표현은 포인터에 대한 모든 바이트 단위의 “데이터 이동” 연산을 지원하며, 이는 memcpy에 충분하다. 산술이나 비트 단위 연산은 완전하게 지원되지 않는다. 이미 위에서 언급했듯, 그것은 더 정교한 포인터 표현이 필요하다.
하지만 “바이트”의 정의는 아직 끝나지 않았다. 프로그램의 동작을 완전히 설명하려면 한 가지 가능성을 더 고려해야 한다. 메모리의 바이트는 미초기화 일 수 있다. 따라서 바이트의 최종 정의(포인터용으로 Pointer 타입이 있다고 가정) 는 다음과 같다:
enum Byte {
Bits(u8),
PtrFragment(Pointer, u8),
Uninit,
}
Uninit은 할당되었지만 아직 쓰여지지 않은 모든 바이트에 사용하는 값이다. 미초기화 메모리를 읽는 것 자체는 괜찮지만, 그 바이트들로 실제로 무언가를 하는 것(예: 정수 산술에 사용)은 정의되지 않은 동작이다.
이는 LLVM의 특수 값 poison에 대한 규칙과 매우 유사하다. LLVM에는 미초기화 메모리에 사용되며 동작이 다소 다른 undef라는 값도 있다. 하지만 우리의 Uninit을 undef로 컴파일하는 것은 실제로 올바르다(undef가 어떤 의미에서는 “더 약하다”). 그리고 LLVM에서 undef를 제거하고 poison으로 대체하자는 제안도 있다.
왜 굳이 특별한 Uninit 값이 필요한지 궁금할 수 있다. 새로 할당된 각 바이트에 대해 임의의 b: u8을 선택해 초기값으로 Bits(b)를 쓰면 안 될까? 그것도 가능하다. 하지만 우선 거의 모든 컴파일러가 미초기화 메모리에 대한 센티넬 값을 갖도록 수렴했다. 그렇게 하지 않으면 LLVM을 통한 컴파일에 문제가 생길 뿐 아니라, 이 변경된 모델로도 최적화가 올바르게 작동하는지 확인하기 위해 많은 최적화를 재검토해야 한다. 핵심은, 컴파일 도중 언제든 Uninit을 어떤 값으로든 대체하는 것이 안전하다는 점이다. 어차피 이 값을 실제로 관측하는 어떤 연산이든 UB이기 때문이다.
예를 들어, 다음 C 코드는 Uninit이 있을 때 더 쉽게 최적화할 수 있다:
int test() {
int x;
if (condA()) x = 1;
// Lots of hard to analyze code that will definitely return when condA()
// does NOT hold, but will not change x.
use(x); // want to optimize x to 1.
}
Uninit이 있으면, x는 Uninit이거나 1임을 쉽게 논증할 수 있고, Uninit을 1로 치환하는 것이 허용되므로 최적화는 손쉽게 정당화된다. 하지만 Uninit이 없다면, x는 “어떤 임의의 비트 패턴”이거나 1이 된다. 같은 최적화를 정당화하기가 훨씬 어려워진다.5
마지막으로, Uninit은 miri 같은 인터프리터에도 더 낫다. 이런 인터프리터는 “이 값들 중 하나를 임의로 선택하라”(즉, 비결정적 연산) 형태의 동작을 다루기 어렵다. 가능한 모든 프로그램 실행을 완전히 탐색하려면 가능한 모든 값을 시도해야 하기 때문이다. 임의의 비트 패턴 대신 Uninit을 사용하면, miri는 단일 실행으로 프로그램이 미초기화 값을 잘못 사용하는지 신뢰성 있게 알려줄 수 있다.
Update: 이 절을 쓴 이후, 더 많은 세부사항, 예제, 참고문헌을 담은 미초기화 메모리와 “실제 하드웨어”에 관한 포스트를 따로 작성했다. /Update
C++와 Rust 같은 언어(실제 하드웨어와는 달리)에서는, 포인터가 같은 주소를 가리키더라도 서로 다를 수 있으며, 바이트는 0..256의 숫자 이상이라는 것을 살펴보았다. 이것이 C를 “이식 가능한 어셈블리”라고 부르는 것이 1978년에는 적절했을지 몰라도, 오늘날에는 위험하게 오해를 부르는 표현인 이유이기도 하다. 이제 이것으로, “2018 메모리 모델”(가제 ;)의 첫 초안을 — 다음 글에서 — 살펴볼 준비가 되었다고 생각한다. :)
Uninit이 필요한 이유에 대한 논거를 찾는 데 도움을 준 @rkruppe와 @nagisa에게 감사한다. 질문이 있다면 포럼에서 자유롭게 물어보라!
공정하게 말하자면, 이것들이 고품질 어셈블리를 생성하는 데 중요하다고 주장 된다. 이 주장은 그럴듯해 보이지만, 이런 최적화의 성능 이점을 체계적으로 탐구한 연구는 유감스럽게도 알지 못한다.↩
프로그래밍 모델을 단순하게 만들기 위해 컴파일러가 이런 최적화를 아예 하지 말아야 한다는 주장도 제기할 수 있다. 이 논의는 해볼 가치가 있지만, 이 글의 요점은 이 트레이드오프를 파헤치는 것이 아니라 C++에서 이루어진 선택의 결과를 탐구하는 데 있다.↩
사실 i = y-x 역시 같은 할당 내 포인터끼리만 뺄셈이 허용되므로 UB다. 다만 i = ((size_t)y - (size_t)x)/sizeof(int)로 우회할 수는 있다.↩
앞서 보았듯, C++ 표준은 실제로 이 규칙을 할당 단위가 아니라 배열 단위에서 적용한다. 하지만 LLVM은 이 규칙을 할당 단위로 적용한다.↩
비결정적 선택이 언제 일어나는지를 재배치할 수 있다고 주장할 수도 있지만, 그러면 분석하기 어려운 코드가 x를 관측하지 않는다는 것을 증명해야 한다. Uninit은 그 불필요한 추가 증명 부담을 피하게 해준다.↩