[Linux Kernel] RCU (Read-Copy-Update)

공부하다보니 여기저기서 RCU가 나와서 이것도 정리를 해야겠다. RCU는 읽기가 대부분인 상황에서 사용하는 동기화 매커니즘이다. 다른 동기화 매커니즘은 읽기와 쓰기에 대한 오버헤드가 발생하지만, RCU는 읽기에 대한 오버헤드가 존재하지 않는다는 특징이 있다. 커널 문서를 보면 사람들이 RCU를 가지고 오해를 많이 한 것 같다. 이렇게 쓰여있다. 그만큼 RCU가 헷갈리는 주제가 아닌가 싶다.

 

기존에는 RCU가 RCU를 한 가지 진실된 방법으로 설명할 수 있을거라는 잘못된 가정하에 설명되었다. 사람들은 RCU를 서로 다른 과정으로 이해한다. 따라서 이 문서는 여러가지 방법으로 RCU를 설명한다.

Notes

이 글은 비실시간 커널(non real-time kernel)에서의 RCU를 설명한다. 실시간 커널에서는 매커니즘이 다르다. 왜냐하면 이 글에서 설명하는 매커니즘은 read-side critical section이 선점이 불가능하다는 조건 하에 작동하기 때문이다. 기회가 되면 실시간 커널에서의 RCU도 글로 정리해보겠다.

 

참고로 이 글은 커널 문서와 LWN.net 글을 토대로 RCU를 정리한 것이다.

Overview

스핀락, 뮤텍스, 세마포어와 같은 일반적인 동기화 매커니즘은 락을 획득(acquire)하고, 데이터를 갱신(update)하고, 락을 반환(release)하는 방식으로 작동한다. RCU는 이런 일반적인 매커니즘과는 달리 '갱신(update)' 이라는 단계를 removal과 reclamation라는 두 단계로 나눈다.

 

removal에서는 프로세서간 공유하는 자료구조 상에서 가리키는 포인터를 없애버린다. 또는 새로운 포인터로 바꿔치기한다. 이때 현대적인 프로세서라면 reader는 writer가 데이터를 갱신/삭제하기 전과 후 둘중 한 가지 상태의 데이터만을 읽게 된다. 수정하기 전과 후의 중간 상태와 같은 데이터는 읽지 않는다. 왜냐하면 현대적인 프로세서에서 포인터의 주소를 덮어씌우는 것은 원자적이기 때문이다.

https://lwn.net/Articles/262464/

위 그림은 방금 말한 내용을 그림으로 나타낸 것이다. removal 단계 이전에 읽기를 시작한 reader도 있고, removal 단계 중간이나 이후에 읽기를 시작한 reader도 있다. 이때 유예 기간(Grace Period)은 removal 단계에서 제거한 포인터를 reclaim(예를 들어 kfree)하기 전까지의 기간이다. removal 단계가 끝나기 전에 읽기를 시작한 reader가 모두 종료하기 전까지가 유예 기간이며 이 기간 동안에는 reclaim이 불가능하다. 누군가 읽고있는데 kfree()를 해버리면 당연히 문제가 생긴다.

 

하지만 유예기간이 끝난 이후에는, 즉 removal 단계가 끝나기 이전에 읽기를 시작한 모든 reader가 읽기를 끝낸 이후에는 removal 단계에서 삭제한 포인터를 reclaim할 수 있다. 즉, 모든 reader가 읽기를 마칠 때까지 기다린 후에 reclaim을 한다.

 

RCU와 기존의 락 매커니즘을 대조해보자면 스핀락, 뮤텍스와 같은 전통적인 동기화 매커니즘은 writer가 쓰기를 하는 동안 모든 reader를 배제(exclude)한다. 하지만 RCU는 reader와 writer가 동시에 실행되게 함으로써 기존의 동기화 매커니즘과 비교했을 때, 읽기 작업의 오버헤드를 없애버린다. 다시 강조하지만 줄이는 게 아니라 없애버린다. RCU로 보호를 한다고 해서 읽기의 성능이 저하되지 않는다. 따라서 RCU는 쓰기 작업이 드물고 읽기 작업이 대부분인 상황에서 다른 동기화 매커니즘보다 매우 효율적이다. 단, 쓰기 작업이 읽기 작업을 기다리기 때문에 쓰기 작업의 비율이 높은 상황에서는 적합하지 않다.

RCU Core API

개념을 간단하게 알아봤으니 API를 살펴보자. RCU는 몇 가지 래퍼 함수가 있긴 하지만 핵심적인 API는 다섯개이다.

- rcu_read_lock()
- rcu_read_unlock()

- synchronize_rcu() / call_rcu()
- rcu_assign_pointer()
- rcu_dereference()

rcu_read_lock(), rcu_read_unlock()

void rcu_read_lock(void);
void rcu_read_unlock(void);

rcu_read_{lock,unlock}은 reader가 읽기를 하는 범위를 나타낼 때 사용된다. rcu_read_lock()을 호출하면 읽기를 시작하고, rcu_read_unlock()을 호출하면 읽기가 끝났음을 의미한다. reader는 반드시 rcu_read_lock() ~ rcu_read_unlock()으로 감싸진 영역 내에서만 읽기를 해야한다. 이 영역을 read-side critical section이라고 하자. read-side critical section에서는 절대로 sleep을 해서는 안된다. 왜냐하면 RCU 자체가 read-side critical section에서 선점이 불가능하다는 조건을 활용해서 구현되기 때문이다. (sleep을 할 수 있는 SRCU도 존재한다.)

synchronize_rcu(), call_rcu()

void synchronize_rcu(void);
void call_rcu(struct rcu_head *head, rcu_callback_t func);

synchronize_rcu()는 synchronize_rcu()를 호출하기 전까지 실행중이던 reader가 끝나기를 기다린다. synchronize_rcu()가 호출되고 끝나기까지의 기간이 아까 봤던 그림에서의 Grace Period와 동일하다.

https://lwn.net/Articles/262464/

하지만 synchronize_rcu()는 sleep이 가능한 함수이므로 선점이 비활성화된 상태에서는 사용할 수 없다. 이러한 컨텍스트에서는 reader가 끝나기를 기다리는 대신 call_rcu()를 이용하면 콜백함수를 등록할 수 있다. call_rcu()에 등록한 콜백함수는 임의의 컨텍스트에서 호출될 수 있으므로 콜백함수 자체는 sleep을 하면 안된다.

rcu_assign_pointer(), rcu_dereference()

/* 파라미터의 타입을 안 적은 이유는 함수가 아니라 매크로이기 때문임 */
rcu_assign_pointer(p, v)
rcu_dereference(p)

rcu_assign_pointer()는 writer가 포인터를 갱신할 때 사용되는 API이고, rcu_dereference()는 reader가 포인터를 역참조할 때 사용되는 API이다. 아니 왜 단순한 포인터 갱신과 역참조에 이런 API가 필요한가 싶겠지만, 이건 전통적인 락과 달리 RCU는 reader와 writer가 동시에 실행될 수 있기 때문이다. 아래의 예시를 생각해보자.

/* What is RCU, Fundamentally?
 (https://lwn.net/Articles/262464/) */

  struct foo {
    int a;
    int b;
    int c;
  };
  struct foo *gp = NULL;
  
  /* . . . */
  
 p = kmalloc(sizeof(*p), GFP_KERNEL);
 p->a = 1;
 p->b = 2;
 p->c = 3;
 gp = p;

위 코드에서는 컴파일러나 CPU의 최적화에 의해 마지막 네 문장의 순서가 바뀔 수 있다. 그렇다면 writer 쪽에서 gp = p;를 p->b = 2; 보다 먼저 실행하는 순간 초기화가 끝나지 않은 상태에서 reader가 gp에 접근하는 문제가 생긴다.

  p->a = 1;
  p->b = 2;
  p->c = 3;
  rcu_assign_pointer(gp, p);

하지만 gp = p 대신 rcu_assign_pointer(gp, p)를 사용하면 메모리 배리어로 인해 rcu_assign_pointer()가 변수 p의 초기화보다 먼저 실행되도록 최적화가 되지 않는다.

 

단, 여기서 주의할 점은 writer에서 자료구조에 접근할 때는 스핀락이나 뮤텍스 등등 별도의 락을 사용해야한다. 왜냐하면 RCU는 writer간의 배제를 지원하지 않기 때문이다.

 

reader측에서 포인터 역참조를 할때 사용하는 rcu_dereference()도 rcu_assign_pointer()와 비슷하다.

  p = gp;
  if (p != NULL) {
    do_something_with(p->a, p->b, p->c);
  }

일부 아키텍처에서는 (p != NULL)보다 p->a, p->b, p->c가 먼저 fetch될 수 있다. (의존성이 존재하지 않으므로) 하지만 p가 writer에 의해 실시간으로 갱신중이라면 p->a, p->b, p->c를 fetch한 이후에 gp의 값이 이미 바뀌었을 수도 있다. 따라서 RCU를 사용해서 안전하게 읽으려면 다음과 같이 사용해야 한다.

  rcu_read_lock(); /* 읽기 시작 */
  p = rcu_dereference(gp); /* 역참조 + 메모리 배리어 */
  if (p != NULL) {
    do_something_with(p->a, p->b, p->c);
  }
  rcu_read_unlock(); /* 읽기 끝 */

rcu_read_lock(), rcu_read_unlock(), synchronize_rcu()의 작동 매커니즘

rcu_read_{lock,unlock}으로 지정된 read-side critical section에서는 반드시 선점이 비활성화 되어야하는데, 아래에서 설명하는 synchronize_rcu()의 구현 때문에 그렇다. rcu_read_lock(), rcu_read_unlock()은 비선점 커널에서는 아무 동작도 하지 않는다. 선점 커널(CONFIG_PREEMPT=y)에서는 선점을 비활성화한다.

 

synchronize_rcu()는 간단하게 개념적으로 아래의 코드로 나타낼 수 있다.

  for_each_online_cpu(cpu)
     run_on(cpu);

run_on()은 현재 실행중인 스레드를 cpu로 옮기는 역할을 한다. 현재 스레드가 cpu에서 실행되었다는 의미는 cpu에서 적어도 하나의 context switch가 발생했다는 의미이고, context switch가 발생했다는 것은 적어도 synchronize_rcu()의 호출 이전에 시작된 read-side critical section의 수행이 끝났다는 의미이다. (왜냐하면 read-side critical section은 선점을 허용하지 않기 때문이다.) 모든 cpu에 대해 synchronize_rcu()의 read-side critical section이 종료되었다면 유예 기간의 끝을 의미하므로 포인터를 안전하게 reclaim할 수 있다. 단, 이 설명은 단순히 개념적인 설명일 뿐이다. 실제 구현은 고려해야할 것도 많고 성능도 최적화 해야하므로 더 복잡하다.

List RCU Example

이 예제는 LWN.net 글에서 빌려온 것이다.

Deletion

  p = search(head, key);
  if (p != NULL) {
    list_del_rcu(&p->list);
    synchronize_rcu();
    kfree(p);
  }

위 코드는 RCU를 통해 리스트의 원소를 제거하는 예시를 간단하게 나타낸다. 그림에서 빨간색 테두리는 해당 원소를 누군가 참조하고 있음을 나타낸다.

초기 상태

list_del_rcu()로 원소를 리스트 상에서 지운다.

synchronize_rcu() 이후: 모든 reader가 읽기를 종료해서 유예 기간이 끝났다. 이제 reclaim할 수 있다.

reclamation 이후

Replacement

이번엔 원소를 교체하는 예시도 알아보자.

  q = kmalloc(sizeof(*p), GFP_KERNEL);
  *q = *p;
  q->b = 2;
  q->c = 3;
  list_replace_rcu(&p->list, &q->list);
  synchronize_rcu();
  kfree(p);

초기 상태

q라는 원소를 할당한다.

*q = *p

q->b = 2

q->c = 3

list_replace_rcu()로 p를 q로 교체한다.

synchronize_rcu()가 끝난 후에는 모든 reader가 읽기를 종료했으므로 reclaim할 수 있다.

참고 문서

What is RCU, Fundamentally? [LWN.net]

What is RCU? – “Read, Copy, Update” — The Linux Kernel documentation