RCU (Read-Copy-Update) 기초 — Quiescent State·Grace Period

1
RCU의 trade-off
2
- reader O(1), 0 contention
3
- writer는 grace period 만큼 wait
4
- 메모리 사용량 (한순간 old + new 동시 존재)
5
- writer가 빈번하면 RWLock이 더 나음

1
struct config *cfg;
2

3
void writer(void) {
4
    struct config *old, *new;
5

6
    new = kmalloc(sizeof(*new), GFP_KERNEL);
7
    *new = *current_cfg();
8
    new->max_threads = 16;
9

10
    old = rcu_dereference_protected(cfg, lockdep_is_held(&cfg_mtx));
11
    rcu_assign_pointer(cfg, new);
12
    synchronize_rcu();      /* 모든 reader가 끝날 때까지 wait */
13
    kfree(old);
14
}
15

16
void reader(void) {
17
    struct config *c;
18
    rcu_read_lock();
19
    c = rcu_dereference(cfg);
20
    process(c);
21
    rcu_read_unlock();
22
}

1
#include <urcu.h>
2

3
struct config *cfg;
4

5
void *reader_thread(void *arg) {
6
    rcu_register_thread();
7
    for (;;) {
8
        rcu_read_lock();
9
        struct config *c = rcu_dereference(cfg);
10
        process(c);
11
        rcu_read_unlock();
12
    }
13
    rcu_unregister_thread();
14
}
15

16
void update_config(struct config *new_cfg) {
17
    struct config *old = rcu_xchg_pointer(&cfg, new_cfg);
18
    synchronize_rcu();
19
    free(old);
20
}
21

22
int main(void) {
23
    rcu_init();
24
    /* threads ... */
25
}

1
struct foo {
2
    struct rcu_head rcu;
3
    int data;
4
};
5

6
static void foo_free(struct rcu_head *r) {
7
    struct foo *f = container_of(r, struct foo, rcu);
8
    kfree(f);
9
}
10

11
void writer(void) {
12
    struct foo *old = rcu_dereference_protected(g, ...);
13
    rcu_assign_pointer(g, new);
14
    call_rcu(&old->rcu, foo_free);    /* sleep 없이 grace period 예약 */
15
}

1
#include <linux/rculist.h>
2

3
struct entry {
4
    struct list_head list;
5
    int key;
6
};
7

8
LIST_HEAD(g_list);
9

10
void add_entry(struct entry *e) {
11
    spin_lock(&list_lock);
12
    list_add_rcu(&e->list, &g_list);
13
    spin_unlock(&list_lock);
14
}
15

16
void remove_entry(struct entry *e) {
17
    spin_lock(&list_lock);
18
    list_del_rcu(&e->list);
19
    spin_unlock(&list_lock);
20
    synchronize_rcu();
21
    kfree(e);
22
}
23

24
void scan(void) {
25
    struct entry *e;
26
    rcu_read_lock();
27
    list_for_each_entry_rcu(e, &g_list, list) {
28
        process(e);
29
    }
30
    rcu_read_unlock();
31
}

1
/* per-CPU counter — RCU 변종 */
2
DEFINE_PER_CPU(unsigned long, hits);
3

4
void hit(void) {
5
    this_cpu_inc(hits);
6
}
7

8
unsigned long total(void) {
9
    unsigned long s = 0;
10
    for_each_possible_cpu(c) s += per_cpu(hits, c);
11
    return s;
12
}

1
writer 비용 비교
2
spinlock writer         150 ns
3
rwlock writer           수 µs (모든 reader가 끝나야)
4
RCU writer + grace     수 ms (grace period 대기)
5
RCU writer + call_rcu  150 ns (callback 예약)

1
struct config *c = rcu_dereference(cfg);   /* unlock 밖 — UB */

1
rcu_read_lock();
2
msleep(10);    /* preempt 가능 → grace period 추정 깨짐 */
3
rcu_read_unlock();

1
list_add_rcu(...);   /* spinlock 없음 — writer끼리 race */

1
for (i = 0; i < N; i++) {
2
    new = ...;
3
    rcu_assign_pointer(p, new);
4
    synchronize_rcu();     /* 매 iteration ms 대기 */
5
}

1
/* URCU thread가 rcu_register_thread 안 부름 */
2
rcu_read_lock();    /* 등록 안 된 thread → assert fail 또는 silent corruption */