RustBelt가 Arc::get_mut의 동기화 결함을 계기로 약한 메모리, 원자적 접근, Acquire/Release 순서화, 데이터 레이스의 정의와 방지 방법을 설명하고, Arc 구현에서의 수정 사항과 그 배경을 소개한다.
While I was busy doing Rust-unrelated research, RustBelt continues to move and recently found another bug (after a missing impl !Sync that we found previously): It turns out that Arc::get_mut did not perform sufficient synchronization, leading to a data race.
Notice that I am just the messenger here, the bug was actually found by Hai and Jacques-Henri. Still, I’d like to use this opportunity to talk a bit about weak memory, synchronization and data races. This is just a primer, there are tons of resources on the web that go into more detail (for example here).
다음 예제를 보자(러스트가 배제하려 애쓰는 동작을 보여 주기 위해 unsafe 코드가 잔뜩 들어 있다):
extern crate rayon;
static mut DATA : Option<String> = None;
static mut FLAG : usize = 0;
fn main() { unsafe {
rayon::join(
|| {
// 데이터 초기화
DATA = Some("Hello World!".to_string());
// 완료 신호
FLAG = 1;
},
|| {
// 다른 스레드가 끝날 때까지 대기
while FLAG == 0 {}
// 데이터 출력
println!("{}", DATA.as_ref().unwrap());
}
);
} }
질문: 이 프로그램은 무엇을 출력할까? “Hello World!”라고 생각했다면 틀린 것은 아니지만, 완전히 맞는 것도 아니다. “Hello World!”가 한 가지 가능성이지만, 이 프로그램은 unwrap에서 패닉할 수도 있고, 사실상 정의되지 않은 동작을 가지므로 무엇이든 할 수 있다.
우선 패닉 가능성부터 이야기해 보자. 어떻게 그런 일이 일어날 수 있을까? 그 이유는 메모리에 접근하는 비용이 높기 때문이다. 산술 연산이나 레지스터 접근 같은 다른 작업에 비해 느리다. 컴파일러와 CPU는 프로그램이 메모리를 기다리는 시간을 줄이기 위해 가능한 모든 일을 한다. 예를 들어, 컴파일러는 첫 번째 스레드의 두 명령 순서를 바꾸는 것이 유리하다고 판단해 DATA = Some(...)보다 앞에 FLAG = 1을 둘 수 있다. 서로 다른 메모리 위치에 대한 쓰기이므로 전체 결과는 같고, 따라서 재배열해도 괜찮다 — 맞을까?
단일 스레드 프로그램만 있던 시절에는 맞았다. 하지만 동시성 프로그램에서는 다른 스레드가 이 쓰기들이 다른 순서로 일어났다는 것을 실제로 관찰할 수 있다! 그래서 두 번째 스레드는 FLAG = 1을 보았지만 여전히 DATA = NONE을 읽을 수도 있다. 더구나 컴파일러가 그런 일을 전혀 하지 않더라도, 이 프로그램을 ARM 칩에서 실행하면 여전히 “0”이라는 결과를 볼 수 있다. 이들 칩은 메모리 접근을 매우 공격적으로 캐시하기 때문에, 위와 같은 프로그램을 어셈블리로 작성하더라도 놀랄 만한 결과를 마주칠 수 있다.
이처럼 이상한 재배열 현상을 보일 수 있는 메모리를, 사람들이 순진하게 기대하는 보장보다 더 적은 보장만 제공한다는 의미에서 “약한 메모리(weak memory)”라고 부른다.
그렇다면 왜 이 프로그램은 정의되지 않은 동작을 가질까? 그 이유는 러스트에는 동시성이 개입되면 사실상 명세하기 어려운 많은 프리미티브가 있기 때문이다. 위의 DATA = Some(...) 할당을 생각해 보자. 전체 Option<String>이 복사된다. 만약 다른 스레드가 그 할당이 진행 중인 동안 DATA를 읽는다면 무슨 일이 일어날까? 다른 스레드는 옛값과 새값이 뒤섞인 어떤 형태의 DATA를 보게 될 것이다! 완전한 쓰레기다. 그래서 시스템 프로그래밍 언어들은 이 지점에서 사실상 포기하고, _데이터 레이스_를 정의되지 않은 동작으로 선언한다.
데이터 레이스는 다음과 같이 정의된다:
동일한 위치에 대한 두 접근은 다음 조건을 만족하면 데이터 레이스를 이룬다:
- 그중 적어도 하나는 쓰기이고,
- 그중 적어도 하나는 특별한 원자적(atomic) 접근이 아니며,
- 그 접근들이 _순서화(ordering)_되어 있지 않다.
“순서”에 대해서는 나중에 이야기하자. 지금은 “원자적 접근”을 보자.
위 프로그램에서 FLAG에 대한 읽기/쓰기는 세 조건을 모두 만족한다. 이를 고치려면 조건 (2)를 부정하자: _원자적 접근_을 사용하자.
보통의 접근(위 예제 코드의 모든 접근처럼)은 비원자적(non-atomic) 접근이라고 부른다. 효율적으로 컴파일할 수 있고 강력하게 최적화되지만, 보았듯이 저수준 동시성 코드를 작성할 때 금방 문제가 된다. 이런 코드를 작성할 수 있게 하면서도 기존 최적화를 대부분 유지하기 위해, C++11 표준은 어떤 위치에 대한 읽기/쓰기 접근을 _원자적_으로 수행하는 특별한 함수를 도입했다. 러스트에도 이러한 원자적 접근이 있으며, 다음과 같이 프로그램에 사용할 수 있다:
extern crate rayon;
use std::sync::atomic::{AtomicUsize, Ordering};
static mut DATA : Option<String> = None;
static FLAG : AtomicUsize = AtomicUsize::new(0);
fn main() {
rayon::join(
|| {
// 데이터 초기화
unsafe { DATA = Some("Hello World!".to_string()); }
// 완료 신호
FLAG.store(1, Ordering::Relaxed); },
|| {
// 다른 스레드가 끝날 때까지 대기
while FLAG.load(Ordering::Relaxed) == 0 {}
// 데이터 출력
println!("{}", unsafe { DATA.as_ref().unwrap() });
}
);
}
FLAG의 타입으로 AtomicUsize를 사용하고, 비원자적 메모리 접근 대신 AtomicUsize::load와 AtomicUsize::store를 사용하는 것에 주목하라. 이들은 원자적 접근이며, 따라서 더 이상 FLAG에 데이터 레이스가 없다. (곧 Ordering::Relaxed 매개변수로 돌아오겠다.) 또한 AtomicUsize는 여러 스레드에서 완전히 안전하게 사용할 수 있으므로, unsafe 연산의 양을 크게 줄였다는 점도 주목하라.
하지만 아직 끝나지 않았다: 여전히 DATA에 대한 레이스가 있다! DATA에 대해서는 그 타입이 Option<String>이라 너무 커서 원자적으로 읽고/쓸 수 없으므로 원자적 접근을 사용할 수도 없다. 여기서 데이터 레이스 정의의 세 번째 조건으로 돌아오자: 두 번의 DATA 접근을 어떻게든 “순서화”해야 한다.
그 “순서”란 무엇일까? 일반적으로 동시성 프로그램의 연산들은 병렬로 일어날 수 있고, 그 결과 처음 프로그램이 패닉할 수도 있는 이상한 효과가 나타난다. 하지만 일부 연산들은 제대로 “순서화”된다고 믿을 수 있다. 예를 들어, 단일 스레드 내의 모든 연산은 코드에 쓰인 순서대로 순서화된다. 즉, 첫 번째 스레드에서는 DATA = Some(...)가 FLAG.store에 앞선다. 그러나 위 프로그램에는 _다른 스레드_의 연산들 사이에 순서를 얻을 방법이 빠져 있다. 여기서 Ordering::Relaxed 매개변수가 등장한다: 모든 원자적 접근에는, 어떤 상황에서 이 접근이 연산들 사이에 순서를 유도할 것인지 나타내는 순서 모드가 붙는다. 위 접근들은 Relaxed이므로 어떤 순서도 유도하지 않는다.
따라서 해야 할 일은, 첫 번째 스레드에서 값 1을 쓰는 동작과 두 번째 스레드에서 값 1을 읽는 동작 사이에 순서를 유도하도록 FLAG 접근의 모드를 강화하는 것이다. 이를 위해 Release와 Acquire 모드 쌍을 사용한다:
extern crate rayon;
use std::sync::atomic::{AtomicUsize, Ordering};
static mut DATA : Option<String> = None;
static FLAG : AtomicUsize = AtomicUsize::new(0);
fn main() {
rayon::join(
|| {
// 데이터 초기화
unsafe { DATA = Some("Hello World!".to_string()); }
// 완료 신호
FLAG.store(1, Ordering::Release); },
|| {
// 다른 스레드가 끝날 때까지 대기
while FLAG.load(Ordering::Acquire) == 0 {}
// 데이터 출력
println!("{}", unsafe { DATA.as_ref().unwrap() });
}
);
}
드디어 이 프로그램은 데이터 레이스가 없고, 따라서 정의되지 않은 동작이 없으며 “Hello World!”를 출력할 것이 보장된다.
핵심은, load(Acquire)가 store(\_, Release)에서 쓴 값을 읽어 올 때, 이 두 접근 사이에 순서가 유도된다는 것이다. 두 접근이 _동기화_한다고도 말한다. 스레드별 순서와 결합하면, 첫 번째 스레드의 DATA = Some(...)와 두 번째 스레드의 DATA 로드 사이에, FLAG에 대한 접근을 통해 순서가 생긴다. 직관적으로, 첫 번째 스레드의 store(_, Release)는 지금까지 이 스레드가 변경한 모든 것을 “해제(release)”하고, 두 번째 스레드의 load(Acquire)는 그러한 모든 데이터를 “획득(acquire)”하여 이 스레드의 이후 접근에서 이용 가능하게 만든다.
대부분의 경우에는 Mutex나 RwLock이면 데이터를 동시 접근으로부터 보호하기에 충분하므로 이런 세부사항을 신경 쓸 필요가 없다. (그리고 러스트의 스레드 안전 보장 덕분에, 안전한 코드에서는 이런 세부사항을 전혀 걱정할 필요가 없다!) 하지만 지금까지 배운 바를 바탕으로, 스레드 A가 락을 해제할 때는 Release 접근을 통해 일어나고, 스레드 B가 락을 획득할 때는 Acquire 접근을 통해 일어난다는 것이 충분히 말이 될 것이다. 이렇게 락은 스레드 A가 락을 잡고 있을 때 수행한 접근들(Release 이전)과 스레드 B가 락을 잡고 있을 때 수행할 접근들(Acquire 이후) 사이에 순서를 보장한다.
Arc로 돌아와서나는 Mutex/RwLock이 대부분의 경우에 충분하다고 말했다. 하지만 Arc는 배타적 락이 유발하는 오버헤드가 너무 커서, 더 최적화된 unsafe 구현을 사용하는 것이 가치 있는 경우 중 하나다. 그래서 Arc의 소스 코드에는 원자적 접근이 잔뜩 등장한다.
그리고 Arc::get_mut의 정당성을 증명하려던 Hai와 Jacques-Henri가 발견했듯이, 어느 한 곳에서 순서로 Relaxed가 사용되었지만 사실은 Acquire여야 했다. 버그의 정확한 세부사항을 논의하려면 아마 블로그 글 하나를 더 써야 할 것이다(Arc는 정말 미묘하다). 하지만 큰 그림은 위의 예제와 정확히 같다: Acquire 덕분에, get_mut 다음에 이어지는 코드와, 다른 스레드에서 마지막 다른 Arc를 드롭하여 참조 카운트를 1로 감소시킨 코드 사이에 순서가 유도된다. 문제를 고친 PR에는 주석으로 좀 더 자세한 내용이 있다. Relaxed일 경우에는 그런 순서가 유도되지 않으므로 데이터 레이스가 생긴다. 공정하게 말하자면, 이 레이스가 실제 오동작으로 이어질 가능성은 매우 낮지만, 그래도 이제 Arc가 대부분1 올바르게 동기화되어 있음을 증명했다는 사실은 기쁘다.
마지막으로 한 가지: 나는 예전에 첫 번째 RustBelt 논문에서 이미 Arc의 정당성을 검증했다고 말했는데, 그렇다면 어떻게 여전히 버그가 있을 수 있을까? 그 논문에서는 여기서 논의한 이러한 순서 문제들에 대해 현실적으로 추론할 도구가 (아직) 없었기 때문에, 대신 모든 원자적 접근에 대해 본질적으로 가장 강한 모드인 SeqCst를 가정하는 “순차적 일관성(sequentially consistent)” 논리를 사용했다. (위에서는 SeqCst를 논의하지 않았고, 실제로 꼭 필요한 경우도 많지 않다. 대부분의 경우 Release와 Acquire로 충분하다.) 이는 검증을 가능하게 하기 위해 실제 러스트와 비교해 우리가 한 단순화 중 하나였다. 우리는 또 다른 버그를 찾을 만큼은 현실적이었지만, 이 버그를 잡을 만큼 충분히 현실적이진 못했다. Hai와 Jacques-Henri는 현재 첫 번째 RustBelt 논문을 확장해 약한 메모리도 다루도록 하여 이 단순화를 바로잡고 있으며, 그 과정에서 이 문제를 마주쳤다.
Update: Servo에는 복사된 Arc가 있는데, 같은 문제가 있었다. 덕분에 하나 값으로 두 개의 버그를 얻었다. :) /Update
make_mut 안의 어떤 Relaxed 접근 하나에 대해서는 Hai와 Jacques-Henri가 아직 정당성을 증명하지 못했다. 하지만 이는 전체 증명을 더 복잡하게 만들어 해결할 수 있을 가능성이 높다. 그 Relaxed도 Acquire로 바꾼 버전은 이미 증명되었지만, 아직 C11만큼 약한 완화 메모리 모델은 아니다.↩