/ PROGRAMMING, RUST, OS

Rust - Memory Management

운영체제에서 메모리 관리하는 방식과 Rust가 그것을 어떻게 활용, 구현하는지 알아보겠습니다.

Rust 맛보기

Memory Allocation

Low-level 언어에서는 memory allocation이 프로그래머에 의해 명시적으로 행해지며, 메모리 관리에 대한 책임을 집니다. 또한 두 가지 유형이 있습니다.

  1. Fixed-sized allocation

컴파일 타임에 크기가 결정되는 경우입니다(정수, boolean, fixed-size 배열 등). 이는 stack에 할당됩니다.

  1. Dynamically-sized allocation

런타임에 크기가 변하고 위치가 변경될 수 있는 경우입니다. 이는 heap에 할당됩니다.

Memory Management Lifecycle

Memory release

C, C++와 같은 언어에서는 free() 함수를 사용하여 메모리를 해제합니다. Rust에서는 ownership system을 통해 메모리를 관리하죠.

Memory tracking

커널은 각 프로세스가 영역별로 얼마나 메모리를 사용하고 있는지 추적합니다. 이를 통해 메모리가 부족한 경우, 메모리를 할당할 수 없는 경우 등을 판단합니다. 커널에 의해 호출되는 System call이, 프로세스당 메모리 할당과 해제를 추적하는데 사용됩니다.

Swapping/paging

커널은 메모리가 부족한 경우, 메모리를 디스크로 swap하거나 페이지를 할당하여 이용 가능한 memory resource를 abstract하는 Virtual Memory 기능을 제공합니다. 이를 통해 메모리 부족 문제를 해결할 수 있습니다.

Smart Pointers in Rust

스마트 포인터는 Rust의 reference처럼 동작하나 추가적인 메터데이터와 기능을 갖고 있는 자료구조입니다. Rust는 표준 라이브러리에 다양한 smart pointer를 정의하고 있습니다. 예를 들어 reference counting smart pointer 타입은 데이터의 owner가 여러 명이 되는 것을 허용하고, owner의 수를 추적하며, owner가 남아 있지 않을 때 자동으로 데이터를 삭제합니다.

일반적인 reference와 가장 큰 차이점은, smart pointer는 대부분의 경우 가리키는 data를 소유한다는 것입니다. 이런 이유로 String과 Vec<T>는 스마트 포인터로 볼 수 있습니다.

스마트 포인터는 다음 두 가지의 trait을 구현합니다.

Deref: reference처럼 행동하도록 하여 스마트 포인터가 reference를 대체할 수 있도록 합니다.

Drop: 스마트 포인터가 범위를 벗어나면 실행되는 코드를 정의합니다.

Box<T>

단일 데이터를 heap에 저장하는 스마트 포인터입니다. Box<T>는 heap에 데이터를 저장하고, stack에는 그 데이터를 가리키는 스마트 포인터인 Box<T> 자체가 저장됩니다. Box<T>는 다음과 같은 상황에서 자주 활용됩니다. Box<T>는 데이터를 heap에 저장하는 것 외에 특별한 기능을 제공하지 않기 때문에 추가적인 runtime overhead가 없습니다.

  1. 크기가 큰 데이터를 갖고 있고 데이터 복사 없이 ownership 이동이 필요할 때

  2. 컴파일 타임에 크기를 알 수 없는 타입을 다룰 때(예: recursive types)

Box::new() 메소드로 Box<T>를 생성할 수 있습니다.

let b = Box::new(5);
println!("b = {}", b);

Box<T>가 범위를 벗어나면 힙의 데이터와 스택의 Box<T> 모두가 할당 해제됩니다.

Box를 사용하여 Recursive Type 다루기

recursive type의 값은 자기 자신의 일부로써 같은 타입의 다른 값을 가질 수 있습니다. 이러한 value nesting은 이론적으로 무한히 깊어질 수 있습니다. 이러한 경우, Rust의 컴파일러는 타입의 크기를 알 수 없기 때문에 컴파일 에러를 발생시킵니다.

Reucrsive type의 예: cons list

함수형 프로그래밍 언어에서 흔히 사용되는 타입입니다.

cons list의 각 아이템은 두 element를 갖습니다: 현재 아이템의 value와 다음 아이템입니다.

enum List {
    Cons(i32, List),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(1, Cons(2, Cons(3, Nil)));
}

하지만 이를 컴파일하려 하면 다음과 같은 에러가 발생합니다.

error[E0072]: recursive type `List` has infinite size
 --> src/main.rs:1:1
  |
...

enum 타입의 크기는 가장 큰 variant를 저장하기 위해 필요한 공간인데, 위에서 정의한 List는 Cons variant가 다른 List를 가리키기 때문에 무한히 큰 크기를 갖게 되기 때문입니다.

이를 해결하기 위해 Box<T>를 사용할 수 있습니다. Rust 컴파일러는 heap 메모리에 할당된 데이터의 크기를 컴파일 타임에 신경쓰지 않기 때문입니다. 그리고 enum에 데이터 자체보다 포인터를 저장하면 고정된 크기를 정의할 수 있죠. String을 enum의 variant로 사용할 수 있는 원리도 사실 동일합니다. String 타입의 경우 3개의 usize(64비트) 값을 저장할 공간만 필요로 하고 실제 문자열은 heap에 저장되기 때문입니다.

위에서 정의한 cons list의 경우 두 번째 element를 Box<List>로 변경하면 됩니다.

enum List {
    Cons(i32, Box<List>),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))));
}

이렇게 되면 최상위 List는 stack에 저장되고, 나머지는 heap에 저장됩니다. List의 크기가 고정되어(32비트 + 64비트) 무한히 큰 크기를 갖지 않게 됩니다.

Deref trait

Deref trait은 dereference operator *의 동작을 customize하는 것을 허용합니다. 이를 통해 스마트 포인터가 reference처럼 동작하도록 할 수 있습니다.

fn main() {
    let x = 5;
    let y = &x;

    assert_eq!(5, x);
    assert_eq!(5, *y);
}

fn main() {
    let x = 5;
    let y = Box::new(x);

    assert_eq!(5, x);
    assert_eq!(5, *y);
}

Smart pointer인 Box<T>에도 위와 같이 *를 사용할 수 있습니다. 이는 Box<T>가 Deref trait을 구현했기 때문입니다.

Deref trait을 구현하기 위해 먼저 std 라이브러리에서 정의를 살펴봅시다.

pub trait Deref {
    type Target: ?Sized;

    // Required method
    fn deref(&self) -> &Self::Target;
}

type Target = T;는 Deref trait이 사용할 관련 타입을 정의합니다.

구현해야 하는 deref() 메소드는 &self를 받아서 &Self::Target을 반환합니다. 이는 * 연산자를 사용하여 접근하고 싶은 값에 대한 reference를 반환하는 것입니다. 다음과 같이 Deref trait을 구현할 수 있습니다.

use std::ops::Deref;

struct MyBox<T>(T);

impl<T> MyBox<T> {
    fn new(x: T) -> MyBox<T> {
        MyBox(x)
    }
}

impl<T> Deref for MyBox<T> {
    type Target = T;

    fn deref(&self) -> &T {
        &self.0
    }
}

위와 같이 .0으로 tuple struct의 첫 번째 값에 접근한 후, 그것에 대한 immutable reference를 반환합니다.

이제 * 연산자를 사용 가능한데, 사실 * 연산자는 내부적으로 다음과 같이 동작합니다.

fn main() {
    let x = 5;
    let y = MyBox::new(x);

    assert_eq!(5, x);
    assert_eq!(5, *(y.deref()));
}

deref()를 통해 MyBox에 대한 reference가 아닌 T에 대한 reference를 반환하고, T는 이미 Deref trait을 구현하고 있는 타입이기 때문에 * 연산자를 통해 해당 값을 얻을 수 있습니다. 이때 deref()로의 호출은 한 번만 일어납니다. 두 번째 *은 deref()에 대한 호출을 또 발생시키지 않습니다.

deref()가 값을 직접적으로 반환하지 않는 이유는, 값의 ownership을 유지하기 위함입니다. deref() 함수 내에서는 reference만 사용하기 때문에 ownership transfer가 발생하지 않죠.

Deref Coercions

Rust는 Deref trait을 사용하여 reference를 다른 타입에 대한 reference로 변환하는 것을 허용합니다. 이를 deref coercions이라고 합니다. Rust는 Deref trait에 구현된 deref() 메소드를 참조해 Deref trait을 구현한 타입의 reference를 얻을 경우 자동으로 reference를 deref()메소드가 반환하는 타입의 reference로 변환합니다. 예를 들어 &String을 &str로 변환하는 것입니다. String이 &str을 반환하는 Deref trait을 구현하고 있기 때문이죠.

&과 *의 사용 빈도를 크게 줄여줘서 유용하며, reference와 smart pointer 모두에 대해 동작하는 코드를 작성하는 것도 가능하게 합니다.

예시

fn hello(name: &str) {
    println!("Hello, {}!", name);
}

fn main() {
    let m = MyBox::new(String::from("Rust"));
    hello(&m);
}

&m은 &MyBox<String> 타입이지만, Deref trait을 통해 내부적으로 .deref() 메소드를 호출해서 &String으로 변환됩니다. 그리고 &String은 다시 .deref() 메소드 호출로 &str으로 변환됩니다. 그래서 hello의 parameter type인 &str과 일치하게 됩니다.

DerefMut trait

Deref trait은 immutable reference를 반환하는 반면, DerefMut trait은 mutable reference를 반환합니다. 이는 * 연산자를 사용하여 mutable reference를 얻을 수 있게 합니다.

use std::ops::DerefMut;
use std::ops::Deref;

impl<T> Deref for MyBox<T> {
    type Target = T;

    fn deref(&self) -> &T {
        &self.0
    }
}

impl<T> DerefMut for MyBox<T> {
    //왜 type Target = T;를 정의하지 않는지?
    fn deref_mut(&mut self) -> &mut T {
        &mut self.0
    }
}

Deref Coercion with Mutability

mutable reference를 immutable reference로 변환, immutable reference를 imuutable reference로 변환, mutable reference를 mutable reference로 변환하는 것은 모두 가능합니다. 그러나 immutable reference를 mutable reference로 변환하는 것은 불가능합니다. 이는 Rust의 borrowing rule을 지키기 위함입니다.

Drop trait

Drop trait은 스마트 포인터가 범위를 벗어나면 실행되는 코드를 정의합니다. 이는 C++의 소멸자와 유사합니다. Rust는 Drop trait을 구현한 타입의 인스턴스가 범위를 벗어나면 자동으로 drop() 메소드를 호출합니다.

변수들은 생성된 순서의 반대 순서로 drop() 메소드가 호출됩니다. 이는 스택에 저장된 변수들이 범위를 벗어나는 순서와 일치합니다.

Drop trait을 구현할 때에는 self의 mutable reference를 받는 drop() 메소드를 구현할 필요가 있습니다.

struct CustomSmartPointer {
    data: String,
}

impl Drop for CustomSmartPointer {
    fn drop(&mut self) {
        println!("Dropping CustomSmartPointer with data `{}`!", self.data);
    }
} // 왜 println!만 호출하는데 메모리 해제가 일어나는지?

일찍 drop하기

std::mem::drop 함수를 사용하여 변수를 일찍 drop할 수 있습니다.

fn main() {
    let x = 5;
    let y = MyBox::new(x);

    assert_eq!(5, x);
    assert_eq!(5, *y);

    drop(y); // y를 일찍 drop
    // assert_eq!(5, *y); // y는 이미 drop되었으므로 에러 발생
}

Rc<T> (Reference Counting)

때때로, 다수의 owner를 갖는 단일 value가 존재하는 경우가 있습니다. 예를 들어, 그래프 자료 구조는 여러 edge가 하나의 node를 가리키고, 해당 노드는 개념적으로 그걸 가리키는 모든 edge에 의해 소유됩니다. 해당 node는 edge가 모두 소멸되기 전까지 살아있어야 하죠.

이러한 경우, Rc<T> 타입을 사용할 수 있습니다. Rc<T>는 reference counting smart pointer로, 데이터의 owner가 여러 명이 되는 것을 허용하고, owner의 수를 추적하며, owner가 남아 있지 않을 때 자동으로 데이터를 삭제합니다. 참고로 reference를 대신 사용하는 것은 lifetime 문제 때문에 완벽한 해결 방법이 아닙니다.

Rc<T>는 thread safety를 위해 single-threaded scenario에서만 사용 가능합니다.

Rc::clone() 메소드를 사용하여 Rc<T>의 reference count를 증가시킬 수 있습니다. 이는 Rc<T>의 reference count를 증가시키는 것이지, 데이터를 복사하는 것이 아닙니다. 그래서 computational cost가 추가적으로 발생하지 않습니다.

use std::rc::Rc;
use crate::List::{Cons, Nil};

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
    let b = Cons(3, Rc::clone(&a)); // a에 대한 reference 복사
    let c = Cons(4, Rc::clone(&a));
}

Interior Mutability Pattern

Rust에서의 design pattern으로, immutable reference가 존재하는 경우에도 데이터를 변경할 수 있도록 하기 위해서 사용합니다.

이 패턴은 자료 구조 내에 unsafe 코드를 삽입해서 compile time의 borrowing rule 검사를 우회합니다.

Interior mutability를 사용하기 위해서는 런타임에 borrowing rule이 지켜지는 것을 보장할 수 있을 때만 가능합니다. 이때 unsafe code는 safe API에 의해 랩핑됩니다.

RefCell<T>

Box와 비슷한 기능을 하지만, 컴파일 타임이 아닌 런타임에 borrowing rule을 강제하는 한 자료구조입니다. Deref와 Drop trait을 구현하고 있지 않으므로 기술적으로 smart pointer는 아닙니다. 하지만 실제 사용은 그냥 smart pointer처럼 하면 됩니다. 만약 runtime에 borrowing rule을 위반하면 panic이 발생하게 됩니다.

runtime checking에 의해 더 유연한 프로그래밍이 가능하지만, panic의 가능성이 존재하고 약간의 성능 저하가 유발될 수 있습니다.

Immutable 변수의 Mutable borrowing

원래는 let 키워드로 선언한 immutable 변수는 값의 변경이 불가하지만, RefCell<T> 등을 사용하면 interior mutability를 얻어와 값의 변경을 허용할 수 있습니다.

use std::cell::RefCell;

fn main() {
    let x = RefCell::new(42);
    let mut y = x.borrow_mut();
    *y = 13; // x의 값이 변경됨
}

trait에 정의된 메소드를 구현할 때, 해당 메소드가 immutable reference를 parameter로 하고 있는데 테스팅을 위해 임시로 구현한 mock object가 해당 메소드를 통해 argument의 값을 변경할 필요가 있는 경우 등에 유용합니다.

RefCell<T>의 borrow() 메소드와 borrow_mut()는 각각 스마트 포인터 Ref<T>와 RefMut<T>를 리턴하는데 내부적으로 이 reference들의 count를 관리합니다. 이를 통해 borrowing rule의 runtime checking을 가능하게 합니다.

Multipler Owners on Mutable data

Rc<T>는 데이터에 대한 immutable reference만 허용하지만, RefCell<T>를 Rc<T>가 가리키게 하면 결과적으로 RefCell<T> 가 가리키는 mutable data가 multiple owner를 가지게 할 수 있습니다.

위에서 정의한 List enum의 Cons variant 정의를 수정하면, 리스트의 모든 원소를 수정할 수 있죠.

#[derive(Debug)]
enum List {
    Cons(Rc<RefCell<i32>>, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;
use std::cell::RefCell;

fn main() {
    let value = Rc::new(RefCell::new(5));

    let a = Rc::new(Cons(Rc::clone(&value), Rc::new(Nil)));

    let b = Cons(Rc::new(RefCell::new(3)), Rc::clone(&a));
    let c = Cons(Rc::new(RefCell::new(4)), Rc::clone(&a));

    *value.borrow_mut() += 10;
    //borrow_mut로 얻어진 mutable reference에 대해 automatic dereference가 발생하여 실제 i32 값에 10이 더해진다.

    println!("a after = {:?}", a);
    println!("b after = {:?}", b);
    println!("c after = {:?}", c);
}

Automatic Referencing and Dereferencing

어떤 객체의 메소드를 object.something()과 같이 호출할 때, Rust는 object의 타입에 따라 자동으로 &, &mut, *를 추가하여 object가 method signature와 일치하도록 해줍니다. 이를 automatic referencing and dereferencing라고 합니다.

예를 들어 위 코드에서 value.borrow_mut() 라고 작성하면 자동으로 *가 추가되어 RefCell의 메소드를 호출할 수 있도록 해줍니다.

참고 문헌

Rust 맛보기