Rust's Miri and Linked List

Miri

Rust는 "memory safe"한 언어로 사랑 받고 있습니다. 참조자(reference) 와 빌림(borrow) 그리고 라이프타임(lifetime)을 통해 Rust는 메모리 누출(memory leak) 없는 안정적이고 만족스러운 프로그래밍 경험을 제공합니다.

하지만 때론 Rust의 메모리 안정성 규칙을 위배하고 싶은, 또는 그래야만 하는 때가 있습니다. 이때 Rust는 usafe를 통해 규칙 위반을 허용하죠. unsafe scope 안에서 발생하는 일에 대해 Rust는 조금도 책임지지 않습니다. 컴파일이 되더라도 런타임에서 발생하는 오류는 온전히 작성자의 책임입니다. 그렇다면 런타임 전에 미리미리 메모리 누수 가능성을 체크해볼 수는 없을까요?

오늘 소개하려는 것은 Rust의 Miri 기능입니다. 한국어로 미리에서 따온 말은... 당연히 아닙니다. Miri는 "Mid-level intermediate representation(MIR)을 위한 interpreter"라는 뜻으로, 런타임 시 발생할 수 있는 오류를 미리 검사하는 기능을 지원합니다. Miri가 지원하는 기능에는 많은 종류가 있고, 여전히 활발하게 발전중이며, 당연하게도 모든 발생 가능한 오류를 미리 체크해주지는 못합니다. 다만 메모리 오류를 불러일으킬 수 있는 코드가 없는지 미리 확인하는 용도로 톡톡히 활용할 수 있습니다.

특히 불가피하게 unsafe 코드를 사용했다면 Miri로 검사해보는 게 필수겠죠!

Using Miri

Miri를 사용하기 위해서는 rust의 nightly 툴체인을 함께 사용해야 합니다. 다음 명령어로 nightly 버전과 miri를 함께 설치합니다.

rustup +nightly component add miri

이제 miri를 사용하면 됩니다. cargo run이나 cargo test 명령어처럼, cargo miri run과 cargo miri test 명령어를 사용할 수 있습니다. 즉 Miri는 test run에 쓰거나 binary 파일의 run에 쓰일 수 있습니다. 각각의 런타임 과정에서 오류를 확인하는 것이죠.

기본적인 memory leak이 발생하는 코드를 작성해 보겠습니다.

fn main() {
let x: *mut i32 = Box::into_raw(Box::new(0));
unsafe {
  *x = 10;
}
}

위 코드를 cargo run으로 실행하면 문제 없이 컴파일 됩니다. 하지만 사실은 raw pointer인 x가 제대로 drop되지 않아 memory leak이 발생하는 코드입니다. cargo miri run을 실행하면 "error: memory leaked"와 같은 에러 문구가 뜨게 됩니다. Box<>에 잡혀있는 raw pointer를 drop하기 위해서는 다음과 같이 코드를 수정해야 합니다.

fn main() {
let x: *mut i32 = Box::into_raw(Box::new(0));
unsafe {
  *x = 10;
  let _ = Box::from_raw(x);
}
}

비슷한 경우로 다음 코드를 봅시다:

fn main() {
let x: *mut i32 = Box::into_raw(Box::new(0));
unsafe {
  let _ = Box::from_raw(x);
  let y = *x + 10;
  println!("{}", y);
}
}

cargo run은 문제 없이 컴파일 되지만, cargo miri run은 "x가 이미 freed되었기 때문에 y가 dangling pointer에 접근하고 있다"는 memory access failed 오류를 알려줍니다.

참고로 위 코드에서 cargo run을 그래도 실행해보세요. 할 때마다 각기 다른 값이 y의 값으로 출력될 것입니다. (계속 10이 나올 수도 있습니다.)

이제 한번 test 코드를 작성해 봅시다.

#![allow(unused)]
fn main() {
#[test]
fn no_memory_leak() {
  let x: *mut i32 = Box::into_raw(Box::new(0));
  unsafe {
    *x = 10;
    let _ = Box::from_raw(x);
  }
}

#[test]
// #[cfg_attr(miri, ignore)]
fn yeah_memory_leak() {
  let x: *mut i32 = Box::into_raw(Box::new(0));
  unsafe {
    *x = 10;
  }
}
}

cargo test 를 사용하면 두 test 함수 모두 문제 없이 작동하지만, cargo miri test를 사용하면 yeah_memory_leak()에 memory leak이 발생함을 알려줍니다. 만일 이것이 의도된 것이고 miri가 해당 함수를 무시하길 바란다면, #[cfg_attr(miri, ignore)] 플래그를 추가해주면 됩니다.

Stacked borrow

앞서 본 기본적인 문제와 함께, miri는 stacked borrow에 대한 검사를 진행합니다. stacked borrow는 간단히 말해 메모리 빌림이 stack 구조로 저장되어 있는 상태를 뜻합니다. stack 구조는 전형적인 후입선출 구조입니다. 가장 늦게 들어온 데이터가 가장 먼저 나가야 하죠. 만일 더 먼저 들어온 데이터가 자신보다 늦게 들어온 (stack의 더 위에 있는) 데이터보다 먼저 접근된다면, 삐빅-🚨 메모리 오류입니다.

예컨대 Rust의 safe code에서도 다음 코드는 불가능합니다. 컴파일러가 승인하지 않죠.

fn main() {
let mut a: i32 = 10;
let b = &mut a;

a += 20;
*b += 20;
}

반면 다음은 가능합니다.

fn main() {
let mut a: i32 = 10;
let b = &mut a;

*b += 20;
a += 20;
}

Unsafe 코드는 컴파일러에 의해 검사되지 않습니다. 대신 Miri를 이용해 stacked borrow 오류가 있는지 확인해볼 수 있죠. 다음 예시는 유명한 rust book 중 하나인 "Too Many Linked Lists"의 관련 챕터를 참고했습니다.

#![allow(unused)]
fn main() {
#[test]
fn ok_stacked_borrow() {
  let mut a: i32 = 10;
  unsafe {
    let b: *mut i32 = &mut a;
    let c: *mut i32 = &mut *b;

    *c += 10;
    *b += 10;
  }
  assert_eq!(a, 30);
}

#[test]
fn bad_stacked_borrow() {
  let mut a: i32 = 10;
  unsafe {
    let b: *mut i32 = &mut a;
    let c: *mut i32 = &mut *b;

    *b += 10;
    *c += 10;
  }
  assert_eq!(a, 30);
}
}

cargo test은 두 테스트 모두 통과시킵니다. 하지만 cargo miri test는 bad_stacked_borrow()에 대해 "접근하려는 위치가 borrow stack에 없다"는 내용의 오류 코드를 보고합니다. c가 borrow stack의 가장 위에 있고 아직 접근될 기회가 남아 있는데 b에 먼저 접근하고 있으니 메모리 오류가 발생한 것이죠.

Linked List

Rust에서 unsafe raw pointer를 사용하게 되는 경우 중 하나는 linked list를 구현할 때입니다. linked list는 일반적인 list나 vector 구조처럼 하나의 데이터 구조 안에 개별 데이터들이 index를 가지고 담겨 있는 것과 달리, 개별 데이터가 다른 데이터를 가르키면서(pointer를 통해) 연결되어 있는 구조입니다.

이때 데이터가 다른 데이터를 가르키는 pointer를 raw pointer로 구현하게 됩니다. 물론! 꼭 raw pointer를 써야 하는 것은 아닙니다. 하지만 Rust가 강제하는 메모리 안정성을 그대로 준수하면서 linked list를 만드는 것은 오히려 복잡하고, 비효율적인 일일 수 있습니다. 특히 꼬리와 머리까지 서로 연결된 Circular list를 Rust의 safe code로 작성하는 일은 꽤나 번거롭습니다. 앞서 언급한 "Too Many Linked Lists" 자체가 Rust에서 linked list 만드는 일의 기쁨과 슬픔에 대한 내용이기도 합니다.

여기서는 한번 간단한 Circular linked list를 구현해보겠습니다. safe code와 unsafe code로 각각 구현해보고, miri test를 진행해봅시다. 해당 코드는 https://github.com/AcheuleanGraph/tech.blob에서 찾아볼 수 있습니다. 여기서 데이터 구조와 연관 함수에 대한 너무 자세한 설명은 생략하겠습니다.

Comparison

먼저 unsafe 코드를 사용한 circular list입니다. Rust에서 다중 참조가 필요한 경우 많이 쓰는 Rc<RefCell<>> 구조를 사용했습니다:

#![allow(unused)]
fn main() {
pub struct NodeA<T: Clone>{
  pub data: T,
  pub prev: Option<Rc<RefCell<NodeA<T>>>>,
  pub i: usize,
  pub next: Option<Rc<RefCell<NodeA<T>>>>
}
}

하나의 노드가 이전 노드(prev)와 다음 노드(next)를 가리키고 있습니다. i는 전체 노드를 순회할 때, 순회의 시점과 기점을 기억하기 위해 각 노드마다 갖게 하는 고유값입니다. 만일 이런 표식이 없다면 실제 사용시 circular list는 무한 순환을 일으킬 것이고 쉽게 memory leak이 발생할 것입니다. 참고로 제너릭 <T>는 각 노드가 갖는 데이터를 표현한 것입니다.

아! Rc와 RefCell를 같이 사용하는 일은 (따로 사용하는 일 만큼이나) 힘겨운 일입니다. linked data를 다룰 때만큼은 Rust가 야속합니다.

다음은 시원하게(?) raw pointer를 사용한 구조입니다:

#![allow(unused)]
fn main() {
pub struct NodeB<T: Clone>{
  pub data: T,
  pub prev: *mut NodeB<T>,
  pub i: usize,
  pub next: *mut NodeB<T>
}
}

Rc<RefCell<>>이 감싸던 prev와 next 노드를 이제는 raw pointer가 가르키고 있습니다. raw pointer를 사용했다는 것 말고는 데이터 구조나 전반적인 사용에는 크게 달라질 것이 없습니다. 이제 이웃 노드에 직접 접근할 때는 unsafe 스코프를 씌어주면 됩니다. unsafe 스코프를 씌어주는 것이 번거로울 수도 있지만, Rc와 RefCell의 이중구조를 뚫고 데이터에 접근하는 일보다는 훨씬 간결합니다.

다만 이제 unsafe raw pointer를 사용하고 있기 때문에, memory leak이 발생하지 않도록 더 신경 써야 합니다. 예컨대 더이상 사용되지 않는 노드의 메모리는 직접 drop시켜줘야 합니다.

예컨대 중간에 있는 노드를 잘라내는 다음 연관함수를 정의한다고 합시다:

#![allow(unused)]
fn main() {
fn cut(node: *mut Self) -> Option<(T, *mut Self)> {
  unsafe {
    let prev = (*node).prev;
    let next = (*node).next;
    let data = (*node).data.clone();

    // destruct cut out node
    let _ = Box::from_raw(node);

    (*prev).next = next;
    (*next).prev = prev;

    Some((data, next))
  }
}
}

보시다시피, 중간에 있는 node를 잘라내고 이웃한 prev와 next를 서로 직접 연결시켜주고 있습니다. 이렇게 되면 잘려나온 가운데 node는 다른 노드들에 의해 더이상 접근될 수 없는, 붕 뜬 상태가 됩니다. raw pointer를 사용했기 때문에 별다른 조치가 없으면 그대로 memory leak이 됩니다. 따라서 let _ = Box::from_raw(node);와 같은 코드를 사용해 해당 raw pointer를 소진하고, scope 밖에서 자동으로 drop되게 했습니다.

연결 리스트를 다 사용한 이후에도 마찬가지로 모든 node에 대한 drop을 수행해야 할 것입니다. 만일 이런 조치가 없이 miri test를 실시해보면 memory leak에 대한 수많은 경고를 마주하게 됩니다.

그런데 놀라운 사실이 하나더 있습니다. 앞서 safe 코드를 사용한 NodeA의 경우, miri test를 실시하면 memory leak 경고가 뜨게 됩니다. 이것은 단순히 linked list가 아닌 circular list를 만들었기 때문입니다. 실제로 처음 연결 리스트를 만들 때 head와 tail을 연결시켜주지 않으면 miri의 경고도 발생하지 않습니다. 이 점은 아무래도 circular list를 만드는 이상 어쩔 수 없이 감수해야 할 점인데요, 이 때문에라도 차라리 Rc<RefCell<>> 구조가 아닌 raw pointer를 주의깊게 사용하는 것이 더 나은 선택지라고 할 수 있겠죠.

Circular linked list는 이렇게 번거롭고 위험하지만... 여전히 많이 사용되는 분야들이 있습니다. 특히 계산 기하학(Computational geometry)에서 다각형 폴리곤의 꼭짓점이나 선분 정보를 표현할 때 많이 사용됩니다. 딱! 감이 오시죠.

Fig1. Circular linked list는 Computational Geometry에서 많이 사용됩니다

Unsafe 코드를 사용한 NodeB가 safe 코드를 사용한 NodeA보다 성능은 우수할까요? 연결 리스트 생성, 노드 삭제, 노드 추가, 스텝 이동, 데이터 조회 등 몇 가지 기능을 상정하고 bench test를 진행해본 결과 전반적으로 95% 정도 더 효율적이었습니다. 특히 데이터 조회 속도는 unsafe 코드가 30~40% 정도 더 빨랐습니다. 벤치마크 테스트 코드도 위 repository에 있습니다.

만일 이런저런 이유로 unsafe 코드를 사용한다면 Miri를 함께 사용하는 게 좋겠네요! 🙂

wrapup

Rust는 안정적인 프로그래밍을 제공하는 점도 매력적이지만, Nightly 버전을 통해 다양하고 톡톡 튀는 기능을 제공하는 점도 매력입니다. Miri 역시 Rust의 매력 포인트 중 하나죠.

다만 Miri는 여전히 발전 중에 있으며, 그 컨셉상 모든 가능한 오류를 잡아낼 수는 없습니다. 따라서 만일 unsafe 코드를 사용하게 된다면 Miri 같은 외부 도구에만 의존하기보다 처음부터 데이터 안전성에 각별한 주의를 기울여야겠죠. 네, 당연한 얘기입니다! 🔬