<kernel v5.4>
RCU(Read Copy Update) -2- (Callback process)
Brute-force RCU-sched grace period(Expedited Grace Period)
고속 네트워크(10G, 100G) 장치를 사용하는 경우 gp 완료를 늦게 감지하면 메모리의 clean-up이 지연되어 OOM(Out Of Memory)가 발생하여 다운될 수도 있다. 이러한 경우를 위해 expedited gp 대기 방식을 사용하면 기본 normal gp 대기 방식보다 더 빠르게 gp의 완료를 수행할 수 있다. 강제로 idle cpu를 제외한 online cpu들에 대해 IPI call을 호출하여 강제로 interrupt context를 발생시키고 메모리 배리어를 호출한다. 이렇게 하는 것으로 호출된 각 cpu의 context 스위칭을 빠르게 유발하여 qs 패스를 보고하게 한다. 이 방법은 모든 cpu들에 대해 ipi call을 호출하므로 대단위 cpu 시스템에서는 많은 cost가 소요되는 단점이 있다.
- 참고: Expedited-Grace-Periods | Kernel.org
메모리가 충분하지 않은 특정 임베디드 시스템에서 부트 타임에 gp kthread가 동작하지 전까지 메모리의 clean-up이 지연되어 발생하는 OOM을 막기 위해 CONFIG_RCU_EXPEDITE_BOOT 커널 옵션을 사용하여 부트 타임에 expedited gp 방식으로 동작하게 할 수 있다. “echo 0 > /sys/kernel/rcu_expedited”을 사용하여 normal gp 방식으로 전환할 수 있다. (gp 커널 스레드가 동작해야 하므로 normal 전환에 시간이 걸리는 점을 유의해야한다.)
RCU_BH 및 RCU_SCHED state 제거
커널 v4.20-rc1 부터 기본 rcu API, rcu_*_bh() 및 rcu_*_sched() 관련한 rcu_state가 제거되어 기본 API만 사용하는 것으로 통합되었다. 따라서 rcu_read_lock_bh() 및 rcu_read_lock_sched() 등의 API를 사용하지 않아도 된다.
RCU 동기 Update
synchronize_rcu()
kernel/rcu/tree.c
/** * synchronize_rcu - wait until a grace period has elapsed. * * Control will return to the caller some time after a full grace * period has elapsed, in other words after all currently executing RCU * read-side critical sections have completed. Note, however, that * upon return from synchronize_rcu(), the caller might well be executing * concurrently with new RCU read-side critical sections that began while * synchronize_rcu() was waiting. RCU read-side critical sections are * delimited by rcu_read_lock() and rcu_read_unlock(), and may be nested. * In addition, regions of code across which interrupts, preemption, or * softirqs have been disabled also serve as RCU read-side critical * sections. This includes hardware interrupt handlers, softirq handlers, * and NMI handlers. * * Note that this guarantee implies further memory-ordering guarantees. * On systems with more than one CPU, when synchronize_rcu() returns, * each CPU is guaranteed to have executed a full memory barrier since * the end of its last RCU read-side critical section whose beginning * preceded the call to synchronize_rcu(). In addition, each CPU having * an RCU read-side critical section that extends beyond the return from * synchronize_rcu() is guaranteed to have executed a full memory barrier * after the beginning of synchronize_rcu() and before the beginning of * that RCU read-side critical section. Note that these guarantees include * CPUs that are offline, idle, or executing in user mode, as well as CPUs * that are executing in the kernel. * * Furthermore, if CPU A invoked synchronize_rcu(), which returned * to its caller on CPU B, then both CPU A and CPU B are guaranteed * to have executed a full memory barrier during the execution of * synchronize_rcu() -- even if CPU A and CPU B are the same CPU (but * again only if the system has more than one CPU). */
void synchronize_rcu(void)
{
RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
lock_is_held(&rcu_lock_map) ||
lock_is_held(&rcu_sched_lock_map),
"Illegal synchronize_rcu() in RCU read-side critical section");
if (rcu_blocking_is_gp())
return;
if (rcu_gp_is_expedited())
synchronize_rcu_expedited();
else
wait_rcu_gp(call_rcu);
}
EXPORT_SYMBOL_GPL(synchronize_rcu);
grace period가 지날때까지 기다린다.
- 코드 라인 7~8에서 아직 rcu의 gp 사용이 블러킹상태인 경우엔 gp 대기 없이 곧바로 함수를 빠져나간다.
- preemptible 커널에서 아직 rcu 스케쥴러가 동작하지 않는 경우
- 부팅 중인 경우 또는 1개의 online cpu만을 사용하는 경우
- 코드 라인 9~12에서 gp를 대기할 때 조건에 따라 다음 두 가지중 하나를 선택하여 동작한다.
- 더 신속한 Brute-force RCU grace period 방법
- 일반 RCU grace period 방법
rcu_blocking_is_gp()
kernel/rcu/tree.c
/* * During early boot, any blocking grace-period wait automatically * implies a grace period. Later on, this is never the case for PREEMPT. * * Howevr, because a context switch is a grace period for !PREEMPT, any * blocking grace-period wait automatically implies a grace period if * there is only one CPU online at any point time during execution of * either synchronize_rcu() or synchronize_rcu_expedited(). It is OK to * occasionally incorrectly indicate that there are multiple CPUs online * when there was in fact only one the whole time, as this just adds some * overhead: RCU still operates correctly. */
static int rcu_blocking_is_gp(void)
{
int ret;
if (IS_ENABLED(CONFIG_PREEMPTION))
return rcu_scheduler_active == RCU_SCHEDULER_INACTIVE;
might_sleep(); /* Check for RCU read-side critical section. */
preempt_disable();
ret = num_online_cpus() <= 1;
preempt_enable();
return ret;
}
rcu의 gp 사용이 블러킹된 상태인지 여부를 반환한다.
- 코드 라인 5~6에서 preemptible 커널인 경우 rcu 스케쥴러가 비활성화 여부에 따라 반환한다.
- 코드 라인 7~11에서 online cpu수를 카운트하여 1개 이하인 경우 blocking 상태로 반환한다. 1개의 cpu인 경우 might_sleep() 이후에 preempt_disable() 및 preempt_enable()을 반복하였으므로 필요한 GP는 완료된 것으로 간주한다.
rcu_gp_is_expedited()
kernel/rcu/update.c
/* * Should normal grace-period primitives be expedited? Intended for * use within RCU. Note that this function takes the rcu_expedited * sysfs/boot variable and rcu_scheduler_active into account as well * as the rcu_expedite_gp() nesting. So looping on rcu_unexpedite_gp() * until rcu_gp_is_expedited() returns false is a -really- bad idea. */
bool rcu_gp_is_expedited(void)
{
return rcu_expedited || atomic_read(&rcu_expedited_nesting);
}
EXPORT_SYMBOL_GPL(rcu_gp_is_expedited);
RCU GP 대기 시 급행 방법 사용 여부를 반환한다.
- /sys/kernel/rcu_expedited 값이 설정된 경우 일반 RCU grace period 방법을 사용하는 대신 Brute-force RCU grace period 방법을 사용한다.
- torture 테스트(CONFIG_RCU_TORTURE_TEST 커널 옵션 사용) 모듈을 동작시킨 경우
다음 그림은 동기화 rcu 요청 함수인 synchronize_rcu() 및 비동기 rcu 요청 함수인 call_rcu() 함수 두 가지에 대해 각각 호출 경로를 보여준다.
—이하 v5.4 변경 작업 중—
wait_rcu_gp()
kernel/rcu/update.c
void wait_rcu_gp(call_rcu_func_t crf)
{
struct rcu_synchronize rcu;
init_rcu_head_on_stack(&rcu.head);
init_completion(&rcu.completion);
/* Will wake me after RCU finished. */
crf(&rcu.head, wakeme_after_rcu);
/* Wait for it. */
wait_for_completion(&rcu.completion);
destroy_rcu_head_on_stack(&rcu.head);
}
EXPORT_SYMBOL_GPL(wait_rcu_gp);
Grace Period가 완료될 때까지 대기한다. 대기를 하기 위해 wakeme_after_rcu라는 함수를 RCU callback으로 하여 비동기 rcu 요청한다. GP가 끝난 후에 해당 callback 함수가 호출되면 자연스럽게 이 함수가 완료된다.
- init_rcu_head_on_stack(&rcu.head);
- rcu_head를 stack에서 초기화한다.
- init_completion(&rcu.completion);
- completion 구조체를 초기화한다.
- crf(&rcu.head, wakeme_after_rcu);
- 인수 crf에는 call_rcu_sched() 또는 call_rcu_bh()함수가 담겨 비동기 rcu callback을 요청한다.
- gp가 완료되면 wakeme_after_rcu()함수가 호출된다.
- wakeme_after_rcu() 함수는 대기 중인 wait_for_completion() 함수의 완료시킨다.
- wait_for_completion(&rcu.completion);
- 작업이 끝날 때까지 대기한다.
- destroy_rcu_head_on_stack(&rcu.head);
- 스택에 위치한 rcu.head를 제거한다.
wakeme_after_rcu()
kernel/rcu/update.c
/*
* Awaken the corresponding synchronize_rcu() instance now that a
* grace period has elapsed.
*/
static void wakeme_after_rcu(struct rcu_head *head)
{
struct rcu_synchronize *rcu;
rcu = container_of(head, struct rcu_synchronize, head);
complete(&rcu->completion);
}
작업 완료를 기다리고 있는 rcu에 complete 처리를 한다.
RCU 비동기 Update
call_rcu()
kernel/rcu/tree_plugin.h
/*
* Queue a preemptible-RCU callback for invocation after a grace period.
*/
void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
{
__call_rcu(head, func, &rcu_preempt_state, -1, 0);
}
EXPORT_SYMBOL_GPL(call_rcu);
grace period가 지난 후에 preemtible-RCU 콜백을 호출할 수 있도록 큐에 추가한다.
- 현재 커널의 rcu가 preemptible을 지원하지 않는 경우 rcu_preempt_state 대신 rcu_sched_state을 사용한다.
__call_rcu()
kernel/rcu/tree_plugin.h
/*
* Helper function for call_rcu() and friends. The cpu argument will
* normally be -1, indicating "currently running CPU". It may specify
* a CPU only if that CPU is a no-CBs CPU. Currently, only _rcu_barrier()
* is expected to specify a CPU.
*/
static void
__call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu),
struct rcu_state *rsp, int cpu, bool lazy)
{
unsigned long flags;
struct rcu_data *rdp;
WARN_ON_ONCE((unsigned long)head & 0x1); /* Misaligned rcu_head! */
if (debug_rcu_head_queue(head)) {
/* Probable double call_rcu(), so leak the callback. */
ACCESS_ONCE(head->func) = rcu_leak_callback;
WARN_ONCE(1, "__call_rcu(): Leaked duplicate callback\n");
return;
}
head->func = func;
head->next = NULL;
/*
* Opportunistically note grace-period endings and beginnings.
* Note that we might see a beginning right after we see an
* end, but never vice versa, since this CPU has to pass through
* a quiescent state betweentimes.
*/
local_irq_save(flags);
rdp = this_cpu_ptr(rsp->rda);
/* Add the callback to our list. */
if (unlikely(rdp->nxttail[RCU_NEXT_TAIL] == NULL) || cpu != -1) {
int offline;
if (cpu != -1)
rdp = per_cpu_ptr(rsp->rda, cpu);
offline = !__call_rcu_nocb(rdp, head, lazy, flags);
WARN_ON_ONCE(offline);
/* _call_rcu() is illegal on offline CPU; leak the callback. */
local_irq_restore(flags);
return;
}
ACCESS_ONCE(rdp->qlen) = rdp->qlen + 1;
if (lazy)
rdp->qlen_lazy++;
else
rcu_idle_count_callbacks_posted();
smp_mb(); /* Count before adding callback for rcu_barrier(). */
*rdp->nxttail[RCU_NEXT_TAIL] = head;
rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
if (__is_kfree_rcu_offset((unsigned long)func))
trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func,
rdp->qlen_lazy, rdp->qlen);
else
trace_rcu_callback(rsp->name, head, rdp->qlen_lazy, rdp->qlen);
/* Go handle any RCU core processing required. */
__call_rcu_core(rsp, rdp, head, flags);
local_irq_restore(flags);
}
call_rcu의 헬퍼 함수로 grace period가 지난 후에 preemtible-RCU 콜백을 호출할 수 있도록 큐에 추가한다. 인수 cpu는 일반적으로 -1이 입력되는 경우 현재 러닝 중인 cpu를 의미한다.
- 코드 라인 15~20에서 CONFIG_DEBUG_OBJECTS_RCU_HEAD 커널 옵션을 사용하여 디버깅을 하는 동안 __call_rcu() 함수가 이중 호출되는 경우 경고 메시지를 출력하고 함수를 빠져나간다.
- 코드 라인 21~22에서 rcu 인스턴스에 인수로 전달받은 콜백 함수를 대입한다. rcu는 리스트로 연결되는데 가장 마지막에 추가되므로 마지막을 의미하는 null을 대입한다.
- 코드 라인 31에서 현재 cpu에 대한 rcu 데이터를 알아온다.
- 코드 라인 34~44에서 낮은 확률로 no-cb용 커널 스레드에서 처리할 콜백이 인입된 경우를 위한 처리를 수행한다.
- rdp->nxttail[RCU_NEXT_TAIL]이 nul인 경우 no-cb 처리한다.
- 코드 라인 45~47에서 rcu 요청되어 큐에 들어올 때 마다 qlen이 1씩 증가되고 처리가 완료되면 처리된 수 만큼 감소한다. kfree용 rcu인 경우에는 qlen 및 qlen_lazy가 같이 증가되고 처리가 완료되면 처리된 수 만큼 같이 감소한다.
- 코드 라인 51~52에서 nxttail[RCU_NEXT_TAIL]이 가리키는 곳의 다음에 cb를 추가한다. 즉 rdp->nxtlist의 가장 마지막에 cb를 추가한다.
- nxttail[RCU_NEXT_TAIL]은 항상 마지막에 추가된 cb를 가리킨다.
- 코드 라인 54~58에서 kfree 타입 또는 일반 타입의 rcu 요청에 맞게 trace 로그를 출력한다.
- 코드 라인 61에서 rcu core 처리를 수행한다.
다음 그림은 __call_rcu() 함수를 호출하여 콜백을 추가하는 과정과 이를 처리하는 과정 두 가지를 모두 보여준다.
- CB용과 NO-CB용으로 나뉘어 리스트가 관리된다.
- CB용
- 1개의 리스트를 4개의 구간별로 나누어 관리한다.
- rcu boost 커널 옵션을 사용하면 per-cpu 커널 스레드가 콜백을 처리한다.
- rcu boost 커널 옵션을 사용하지 않으면 softirq 에서 콜백을 처리한다.
- NO-CB용
- 3개의 리스트에서 관리된다.
- DDOS attack 상황에서 OOM을 막기 위해 nocb 지정된 cpu들의 nocb 커널 스레드가 콜백을 처리한다.
- 리더 cpu가 소속된 팔로워 cpu들의 리스트를 관리한다.
- 모든 팔로워 cpu들은 follower 리스트에 콜백이 존재하면 처리한다.
- CB용
RCU 콜백 리스트
RCU 콜백들이 추가되는 리스트에 대해 알아보자. 하나의 리스트를 사용하였고, 4개의 구간으로 나누어 관리하기 위해 4개의 포인터 배열을 사용한다.
- 1개의 리스트: rdp->nxtlist
- 4개의 포인터 배열: rdp->nxttail[4]
- 1 번째 done 구간:
- *nxtlist ~ nxttail[0]
- nxtlist에 연결된 다음 콜백 위치부터 nxttail[RCU_DONE_TAIL] 까지
- g.p가 완료하여 처리 가능한 구간이다. blimit 제한으로 인해 다 처리되지 못한 콜백들이 이 구간에 남아 있을 수 있다.
- 이 구간의 콜백들은 아무때나 처리 가능하다.
- 2 번째 wait 구간
- *nxttail[0] ~ nxttail[1]
- nxttail[RCU_DONE_TAIL]에 연결된 다음 콜백 위치부터 nxttail[RCU_WAIT_TAIL] 까지
- current gp 이전에 추가된 콜백으로 current gp가 끝난 후에 처리될 예정인 콜백들이 대기중인 구간이다.
- 3 번째 next-ready 구간 (=wait 2 구간)
- *nxttail[1] ~ nxttail[2]
- nxttail[RCU_WAIT_TAIL]에 연결된 다음 콜백 위치부터 nxttail[RCU_NEXT_READY_TAIL] 까지
- current gp 진행 중에 추가된 콜백들이 추가된 구간이다. 이 콜백들은 current gp가 완료되어도 곧바로 처리되면 안되고, 다음 gp가 완료된 후에 처리될 예정인 콜백들이 있는 구간이다.
- 이 구간의 콜백들은 current gp 및 next gp 까지 완료된 후에 처리되어야 한다.
- 전통적인(classic) rcu에서는 이 구간이 없이 1개의 wait 구간만으로 처리가 되었지만 preemptible rcu 처리를 위해 1 번의 gp를 더 연장하기 위해 구간을 추가하였다. preemptible rcu 에서 rcu_read_lock()에서 메모리 배리어를 사용하지 않게 하기 위해 gp를 1단계 더 delay하여 처리한다.
- 4 번째 next 구간
- *nxttail[2] ~ nxttail[3]
- nxttail[RCU_NEXT_READY_TAIL]에 연결된 다음 콜백 위치부터 nxttail[RCU_NEXT_TAIL] 까지
- 새 콜백이 추가되면 이 구간의 마지막에 추가되고, nxttail[RCU_NEXT_TAIL]이 추가된 마지막 콜백을 항상 가리키게 해야한다.
- 1 번째 done 구간:
- 일반적인 콜백 진행은 위와 같지만 cpu가 16개를 초과하면 1 단계를 더 지연처리할 수도 있다.
기존 nxtlist, nxttail[], nxtcompleted[]에서 관리되던 멤버 변수들이 커널 v4.12-rc에서 struct rcu_seglist에서 관리되는 형태로 바뀌었다.
include/linux/rcu_segcblist.h
struct rcu_segcblist {
struct rcu_head *head;
struct rcu_head **tails[RCU_CBLIST_NSEGS];
unsigned long gp_seq[RCU_CBLIST_NSEGS];
long len;
long len_lazy;
};
__call_rcu_core()
kernel/rcu/tree.c
/*
* Handle any core-RCU processing required by a call_rcu() invocation.
*/
static void __call_rcu_core(struct rcu_state *rsp, struct rcu_data *rdp,
struct rcu_head *head, unsigned long flags)
{
bool needwake;
/*
* If called from an extended quiescent state, invoke the RCU
* core in order to force a re-evaluation of RCU's idleness.
*/
if (!rcu_is_watching() && cpu_online(smp_processor_id()))
invoke_rcu_core();
/* If interrupts were disabled or CPU offline, don't invoke RCU core. */
if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
return;
/*
* Force the grace period if too many callbacks or too long waiting.
* Enforce hysteresis, and don't invoke force_quiescent_state()
* if some other CPU has recently done so. Also, don't bother
* invoking force_quiescent_state() if the newly enqueued callback
* is the only one waiting for a grace period to complete.
*/
if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) {
/* Are we ignoring a completed grace period? */
note_gp_changes(rsp, rdp);
/* Start a new grace period if one not already started. */
if (!rcu_gp_in_progress(rsp)) {
struct rcu_node *rnp_root = rcu_get_root(rsp);
raw_spin_lock(&rnp_root->lock);
smp_mb__after_unlock_lock();
needwake = rcu_start_gp(rsp);
raw_spin_unlock(&rnp_root->lock);
if (needwake)
rcu_gp_kthread_wake(rsp);
} else {
/* Give the grace period a kick. */
rdp->blimit = LONG_MAX;
if (rsp->n_force_qs == rdp->n_force_qs_snap &&
*rdp->nxttail[RCU_DONE_TAIL] != head)
force_quiescent_state(rsp);
rdp->n_force_qs_snap = rsp->n_force_qs;
rdp->qlen_last_fqs_check = rdp->qlen;
}
}
}
rcu 처리(새 콜백, qs, gp 등의 변화) 를 위해 rcu core를 호출한다.
- 코드 라인 13~14에서 디버깅 및 tracing이 설정된 경우 rcu core 처리를 위해 softirq를 호출한다.
- 코드 라인 17~18에서 인터럽트가 disable된 상태인 경우이거나 offline 상태이면 함수를 빠져나간다.
- 코드 라인 27에서 rcu 콜백이 너무 많이 대기 중이면
- 코드 라인 33~41에서 gp가 진행 중이 아니면 새로운 gp를 시작시키기 위해 gp 스레드를 깨운다.
- 코드 라인 42~49에서 gp가 이미 진행 중이면 blimit 제한을 풀고 fqs를 진행한다.
synchronize_rcu_expedited()
kernel/rcu/tree_plugin.h
/**
* synchronize_rcu_expedited - Brute-force RCU grace period
*
* Wait for an RCU-preempt grace period, but expedite it. The basic
* idea is to invoke synchronize_sched_expedited() to push all the tasks to
* the ->blkd_tasks lists and wait for this list to drain. This consumes
* significant time on all CPUs and is unfriendly to real-time workloads,
* so is thus not recommended for any sort of common-case code.
* In fact, if you are using synchronize_rcu_expedited() in a loop,
* please restructure your code to batch your updates, and then Use a
* single synchronize_rcu() instead.
*/
void synchronize_rcu_expedited(void)
{
unsigned long flags;
struct rcu_node *rnp;
struct rcu_state *rsp = &rcu_preempt_state;
unsigned long snap;
int trycount = 0;
smp_mb(); /* Caller's modifications seen first by other CPUs. */
snap = ACCESS_ONCE(sync_rcu_preempt_exp_count) + 1;
smp_mb(); /* Above access cannot bleed into critical section. */
/*
* Block CPU-hotplug operations. This means that any CPU-hotplug
* operation that finds an rcu_node structure with tasks in the
* process of being boosted will know that all tasks blocking
* this expedited grace period will already be in the process of
* being boosted. This simplifies the process of moving tasks
* from leaf to root rcu_node structures.
*/
if (!try_get_online_cpus()) {
/* CPU-hotplug operation in flight, fall back to normal GP. */
wait_rcu_gp(call_rcu);
return;
}
/*
* Acquire lock, falling back to synchronize_rcu() if too many
* lock-acquisition failures. Of course, if someone does the
* expedited grace period for us, just leave.
*/
while (!mutex_trylock(&sync_rcu_preempt_exp_mutex)) {
if (ULONG_CMP_LT(snap,
ACCESS_ONCE(sync_rcu_preempt_exp_count))) {
put_online_cpus();
goto mb_ret; /* Others did our work for us. */
}
if (trycount++ < 10) {
udelay(trycount * num_online_cpus());
} else {
put_online_cpus();
wait_rcu_gp(call_rcu);
return;
}
}
if (ULONG_CMP_LT(snap, ACCESS_ONCE(sync_rcu_preempt_exp_count))) {
put_online_cpus();
goto unlock_mb_ret; /* Others did our work for us. */
}
Brute-force RCU grace period 방법을 사용하여 gp가 완료될 때까지 기다린다. 이 방법을 사용할 수 없는 상황인 경우 일반 gp를 대기하는 방식을 사용한다.
- struct rcu_state *rsp = &rcu_preempt_state;
- 전역 rcu_preempt_state 객체를 통해 rcu 트리 노드등을 사용할 목적으로 rsp 포인터에 대입한다.
- snap = ACCESS_ONCE(sync_rcu_preempt_exp_count) + 1;
- sync_rcu_preempt_exp_count 값을 읽어 1을 추가하여 snap에 대입한다.
- if (!try_get_online_cpus()) { wait_rcu_gp(call_rcu); return; }
- cpu hotplug용 mutex lock을 획득하지 못한 경우 일반 RCU grace period 방식을 사용한다.
- 참고: Optimizing CPU hotplug locking | LWN.net
- while (!mutex_trylock(&sync_rcu_preempt_exp_mutex)) {
- contension 상황이라 아직 rcu용 mutex 락을 획득하지 못한 경우 루프를 돈다.
- if (ULONG_CMP_LT(snap, ACCESS_ONCE(sync_rcu_preempt_exp_count))) { put_online_cpus(); goto mb_ret; }
- snap 값이 sync_rcu_preempt_exp_count 값보다 작은 경우 함수를 빠져나간다.
- if (trycount++ < 10) { udelay(trycount * num_online_cpus()); } else { put_online_cpus(); wait_rcu_gp(call_rcu); return; }
- 10번 이내 시도 시 시도 횟 수만큼 비례하여 약간의 딜레이를 갖는다. 시도가 10번 이상인 경우 일반 RCU grace period 방식을 사용하여 대기를 한 후 함수를 빠져나간다.
- if (ULONG_CMP_LT(snap, ACCESS_ONCE(sync_rcu_preempt_exp_count))) { put_online_cpus(); goto unlock_mb_ret; }
- mutex 락 획득 후 snap 값이 sync_rcu_preempt_exp_count 보다 작은 경우 함수를 빠져나간다.
/* force all RCU readers onto ->blkd_tasks lists. */
synchronize_sched_expedited();
/* Initialize ->expmask for all non-leaf rcu_node structures. */
rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) {
raw_spin_lock_irqsave(&rnp->lock, flags);
smp_mb__after_unlock_lock();
rnp->expmask = rnp->qsmaskinit;
raw_spin_unlock_irqrestore(&rnp->lock, flags);
}
/* Snapshot current state of ->blkd_tasks lists. */
rcu_for_each_leaf_node(rsp, rnp)
sync_rcu_preempt_exp_init(rsp, rnp);
if (NUM_RCU_NODES > 1)
sync_rcu_preempt_exp_init(rsp, rcu_get_root(rsp));
put_online_cpus();
/* Wait for snapshotted ->blkd_tasks lists to drain. */
rnp = rcu_get_root(rsp);
wait_event(sync_rcu_preempt_exp_wq,
sync_rcu_preempt_exp_done(rnp));
/* Clean up and exit. */
smp_mb(); /* ensure expedited GP seen before counter increment. */
ACCESS_ONCE(sync_rcu_preempt_exp_count) =
sync_rcu_preempt_exp_count + 1;
unlock_mb_ret:
mutex_unlock(&sync_rcu_preempt_exp_mutex);
mb_ret:
smp_mb(); /* ensure subsequent action seen after grace period. */
}
EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
- synchronize_sched_expedited();
- sched용 brute-force rcu gp(expedited gp)를 처리한다.
- rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) { raw_spin_lock_irqsave(&rnp->lock, flags); smp_mb__after_unlock_lock(); rnp->expmask = rnp->qsmaskinit; raw_spin_unlock_irqrestore(&rnp->lock, flags); }
- leaf 노드가 아닌 rcu 노드에 대해 루프를 돌며 rnp->expmask에 rnp->qsmaskinit을 대입하여 초기화한다.
- rcu_for_each_leaf_node(rsp, rnp) sync_rcu_preempt_exp_init(rsp, rnp);
- leaf 노드에 대해 루프를 돌며지정된 rcu 노드에 대해 preemptible-RCU expedited gp를 시작을 위해 초기화한다.
- if (NUM_RCU_NODES > 1) sync_rcu_preempt_exp_init(rsp, rcu_get_root(rsp));
- RCU 노드가 2단계 레벨 이상 구성된 경우 루트 노드에 대해서도 preemptible-RCU expedited gp 시작을 위해 초기화한다.
- rnp = rcu_get_root(rsp); wait_event(sync_rcu_preempt_exp_wq, sync_rcu_preempt_exp_done(rnp));
- sync_rcu_preempt_exp_wq에 이벤트가 도착하고 루트노드에서 RCU expedited grace period가 진행중이지 않을 때까지 기다린다.
- ACCESS_ONCE(sync_rcu_preempt_exp_count) = sync_rcu_preempt_exp_count + 1
- sync_rcu_preempt_exp_count를 1 증가시킨다.
synchronize_sched_expedited()
kernel/rcu/tree.c – 1/3
/**
* synchronize_sched_expedited - Brute-force RCU-sched grace period
*
* Wait for an RCU-sched grace period to elapse, but use a "big hammer"
* approach to force the grace period to end quickly. This consumes
* significant time on all CPUs and is unfriendly to real-time workloads,
* so is thus not recommended for any sort of common-case code. In fact,
* if you are using synchronize_sched_expedited() in a loop, please
* restructure your code to batch your updates, and then use a single
* synchronize_sched() instead.
*
* This implementation can be thought of as an application of ticket
* locking to RCU, with sync_sched_expedited_started and
* sync_sched_expedited_done taking on the roles of the halves
* of the ticket-lock word. Each task atomically increments
* sync_sched_expedited_started upon entry, snapshotting the old value,
* then attempts to stop all the CPUs. If this succeeds, then each
* CPU will have executed a context switch, resulting in an RCU-sched
* grace period. We are then done, so we use atomic_cmpxchg() to
* update sync_sched_expedited_done to match our snapshot -- but
* only if someone else has not already advanced past our snapshot.
*
* On the other hand, if try_stop_cpus() fails, we check the value
* of sync_sched_expedited_done. If it has advanced past our
* initial snapshot, then someone else must have forced a grace period
* some time after we took our snapshot. In this case, our work is
* done for us, and we can simply return. Otherwise, we try again,
* but keep our initial snapshot for purposes of checking for someone
* doing our work for us.
*
* If we fail too many times in a row, we fall back to synchronize_sched().
*/
void synchronize_sched_expedited(void)
{
cpumask_var_t cm;
bool cma = false;
int cpu;
long firstsnap, s, snap;
int trycount = 0;
struct rcu_state *rsp = &rcu_sched_state;
/*
* If we are in danger of counter wrap, just do synchronize_sched().
* By allowing sync_sched_expedited_started to advance no more than
* ULONG_MAX/8 ahead of sync_sched_expedited_done, we are ensuring
* that more than 3.5 billion CPUs would be required to force a
* counter wrap on a 32-bit system. Quite a few more CPUs would of
* course be required on a 64-bit system.
*/
if (ULONG_CMP_GE((ulong)atomic_long_read(&rsp->expedited_start),
(ulong)atomic_long_read(&rsp->expedited_done) +
ULONG_MAX / 8)) {
synchronize_sched();
atomic_long_inc(&rsp->expedited_wrap);
return;
}
/*
* Take a ticket. Note that atomic_inc_return() implies a
* full memory barrier.
*/
snap = atomic_long_inc_return(&rsp->expedited_start);
firstsnap = snap;
if (!try_get_online_cpus()) {
/* CPU hotplug operation in flight, fall back to normal GP. */
wait_rcu_gp(call_rcu_sched);
atomic_long_inc(&rsp->expedited_normal);
return;
}
WARN_ON_ONCE(cpu_is_offline(raw_smp_processor_id()));
/* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */
cma = zalloc_cpumask_var(&cm, GFP_KERNEL);
if (cma) {
cpumask_copy(cm, cpu_online_mask);
cpumask_clear_cpu(raw_smp_processor_id(), cm);
for_each_cpu(cpu, cm) {
struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1))
cpumask_clear_cpu(cpu, cm);
}
if (cpumask_weight(cm) == 0)
goto all_cpus_idle;
}
expedited 방식으로 gp의 완료까지 대기한다.
- 코드 라인 50~56에서 expedited_start 카운터가 expedited_done보다 4(32bit) 또는 8(64bit) 보다 크거나 같은 경우 여러 cpu에서 요청하는 상황이다. 이러한 경우 기존 normal gp를 사용하는 방식을 사용하여 gp를 대기한다.
- 코드 라인 62~69에서 cpu hotplug가 진행중일 때에는 fallback으로 normal gp 대기를 수행한다.
- 코드 라인 72~84에서 현재 cpu 및 idle cpu를 제외한 online cpu를 cm이라는 cpumask에 구한다. 모든 cpu들이 idle 상태인경우 all_cpus_idle 레이블로 이동한다.
kernel/rcu/tree.c – 2/3
. /*
* Each pass through the following loop attempts to force a
* context switch on each CPU.
*/
while (try_stop_cpus(cma ? cm : cpu_online_mask,
synchronize_sched_expedited_cpu_stop,
NULL) == -EAGAIN) {
put_online_cpus();
atomic_long_inc(&rsp->expedited_tryfail);
/* Check to see if someone else did our work for us. */
s = atomic_long_read(&rsp->expedited_done);
if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
/* ensure test happens before caller kfree */
smp_mb__before_atomic(); /* ^^^ */
atomic_long_inc(&rsp->expedited_workdone1);
free_cpumask_var(cm);
return;
}
/* No joy, try again later. Or just synchronize_sched(). */
if (trycount++ < 10) {
udelay(trycount * num_online_cpus());
} else {
wait_rcu_gp(call_rcu_sched);
atomic_long_inc(&rsp->expedited_normal);
free_cpumask_var(cm);
return;
}
/* Recheck to see if someone else did our work for us. */
s = atomic_long_read(&rsp->expedited_done);
if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
/* ensure test happens before caller kfree */
smp_mb__before_atomic(); /* ^^^ */
atomic_long_inc(&rsp->expedited_workdone2);
free_cpumask_var(cm);
return;
}
/*
* Refetching sync_sched_expedited_started allows later
* callers to piggyback on our grace period. We retry
* after they started, so our grace period works for them,
* and they started after our first try, so their grace
* period works for us.
*/
if (!try_get_online_cpus()) {
/* CPU hotplug operation in flight, use normal GP. */
wait_rcu_gp(call_rcu_sched);
atomic_long_inc(&rsp->expedited_normal);
free_cpumask_var(cm);
return;
}
snap = atomic_long_read(&rsp->expedited_start);
smp_mb(); /* ensure read is before try_stop_cpus(). */
}
atomic_long_inc(&rsp->expedited_stoppedcpus);
- 코드 라인 5~7에서 현재 cpu 및 idle cpu를 제외한 online cpu들에 대해 IPI(Inter Process Interrupt) 호출을 하여 해당 cpu들이 synchronize_sched_expedited_cpu_stop() 함수를 실행하여 강제로 메모리 배리어를 동작하게 한다. 이 작업이 실패하면 while() 문 내의 코드를 수행하고 반복한다.
- 강제로 interrupt context가 발생하게 만들고 메모리 배리어를 수행해둔다.
- 코드 라인 12~19에서 다른 cpu에서 같은 작업을 이미 호출한 경우 이 cpu는 처리를 포기하고 함수를 빠져나간다.
- 코드 라인 22~29에서 10회 이상 처리한 경우 일반 gp를 대기하는 방식으로 선회한다. 10회 이내의 경우에 한해서는 trycount * online cpu 수만큼의 마이크로 딜레이를 갖고 계속 진행한다.
- 코드 라인 32~39에서다른 cpu에서 같은 작업을 또 호출했는지 다시 한 번 확인한다.
- 코드 라인 48~54에서 cpu hotplug 작업이 진행 중인 경우에는 일반 gp를 대기하는 방식으로 선회한다.
- 코드 라인 55~57에서 expedited_start 값을 snap에 읽어오고 다시 루프를 돈다.
- 코드 라인 58에서 IPI 호출이 모두 정상적으로 완료된 경우 expedited_stoppedcpus 카운터를 1 증가시킨다.
kernel/rcu/tree.c – 3/3
all_cpus_idle:
free_cpumask_var(cm);
/*
* Everyone up to our most recent fetch is covered by our grace
* period. Update the counter, but only if our work is still
* relevant -- which it won't be if someone who started later
* than we did already did their update.
*/
do {
atomic_long_inc(&rsp->expedited_done_tries);
s = atomic_long_read(&rsp->expedited_done);
if (ULONG_CMP_GE((ulong)s, (ulong)snap)) {
/* ensure test happens before caller kfree */
smp_mb__before_atomic(); /* ^^^ */
atomic_long_inc(&rsp->expedited_done_lost);
break;
}
} while (atomic_long_cmpxchg(&rsp->expedited_done, s, snap) != s);
atomic_long_inc(&rsp->expedited_done_exit);
put_online_cpus();
}
EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
- 코드 라인 10~19에서 expedited_done 카운터를 snap 값으로 atomic하게 업데이트한다.
RCU CB 처리
rcu_process_callbacks()
kernel/rcu/tree.c
/*
* Do RCU core processing for the current CPU.
*/
static void rcu_process_callbacks(struct softirq_action *unused)
{
struct rcu_state *rsp;
if (cpu_is_offline(smp_processor_id()))
return;
trace_rcu_utilization(TPS("Start RCU core"));
for_each_rcu_flavor(rsp)
__rcu_process_callbacks(rsp);
trace_rcu_utilization(TPS("End RCU core"));
}
rcu flavor 리스트에 등록된 rcu state는 rcu_sched_state, rcu_bh_state, rcu_preempt_state가 있다. 이들에 등록되어 있는 콜백을 단계별로 처리한다.
__rcu_process_callbacks()
kernel/rcu/tree.c
/*
* This does the RCU core processing work for the specified rcu_state
* and rcu_data structures. This may be called only from the CPU to
* whom the rdp belongs.
*/
static void
__rcu_process_callbacks(struct rcu_state *rsp)
{
unsigned long flags;
bool needwake;
struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
WARN_ON_ONCE(rdp->beenonline == 0);
/* Update RCU state based on any recent quiescent states. */
rcu_check_quiescent_state(rsp, rdp);
/* Does this CPU require a not-yet-started grace period? */
local_irq_save(flags);
if (cpu_needs_another_gp(rsp, rdp)) {
raw_spin_lock(&rcu_get_root(rsp)->lock); /* irqs disabled. */
needwake = rcu_start_gp(rsp);
raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
if (needwake)
rcu_gp_kthread_wake(rsp);
} else {
local_irq_restore(flags);
}
/* If there are callbacks ready, invoke them. */
if (cpu_has_callbacks_ready_to_invoke(rdp))
invoke_rcu_callbacks(rsp, rdp);
/* Do any needed deferred wakeups of rcuo kthreads. */
do_nocb_deferred_wakeup(rdp);
}
rcu 콜백을 처리한다.
- 코드 라인 16에서 qs가 지났는지 체크한다.
- 코드 라인 19~28에서 irq를 disable한 상태에서 새로운 gp가 필요하면 gp를 시작한다. 필요에 의해 gp 스레드가 필요하면 깨운다.
- 코드 라인 31~32에서 rcu 콜백을 처리할 수 있는 상태이면 호출하여 단계별로 처리한다.
- 코드 라인 35에서 rcu no-callback을 위한 처리를 한다.
RCU gpnum & completed 번호 관계
각각의 구조체 포인터 표현은 다음과 같다.
- rsp -> rcu_state 구조체 포인터 (글로벌 락 사용)
- rnp -> rcu_node 구조체 포인터 (노드에 포함된 cpu만 영향을 받는 노드락 사용)
- rdp -> rcu_data 구조체 포인터 (per-cpu 로컬이므로 락 없이 사용)
위 3가지 구조체에 담긴 gpnum과 completed가 담겨 있다. rcu 관리에서 최대한 락 사용을 억제하기 위해 per-cpu를 사용한 rcu_data는 로컬 cpu 데이터를 취급한다. 로컬 데이터는 해당 cpu가 필요한 시점에서만 갱신한다. 따라서 이로 인해 로컬 gpnum과 completed 번호는 글로벌 gpnum과 completed 번호에 비해 최대 1 만큼 늦어질 수도 있다. 루트 노드의 값은 항상 rcu_state의 값들과 동시에 변경되지만 그 외의 노드들 값들은 노드 락을 거는 시간이 필요하므로 약간씩 지연된다. (모든 값의 차이는 최대 1을 초과할 수 없다.) gp 번호가 담긴 gpnum은 gp가 시작할 때 증가된다. gp가 완료된 후 완료된 글로벌 gpnum 번호로 글로벌의 completed 번호를 갱신한다. gp가 완료되었으므로 completed 번호까지는 cb들을 처리할 수 있게된다.
rcu_check_quiescent_state()
kernel/rcu/tree.c
/*
* Check to see if there is a new grace period of which this CPU
* is not yet aware, and if so, set up local rcu_data state for it.
* Otherwise, see if this CPU has just passed through its first
* quiescent state for this grace period, and record that fact if so.
*/
static void
rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
{
/* Check for grace-period ends and beginnings. */
note_gp_changes(rsp, rdp);
/*
* Does this CPU still need to do its part for current grace period?
* If no, return and let the other CPUs do their part as well.
*/
if (!rdp->qs_pending)
return;
/*
* Was there a quiescent state since the beginning of the grace
* period? If no, then exit and wait for the next call.
*/
if (!rdp->passed_quiesce &&
rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr))
return;
/*
* Tell RCU we are done (but rcu_report_qs_rdp() will be the
* judge of that).
*/
rcu_report_qs_rdp(rdp->cpu, rsp, rdp);
}
현재 cpu에 대해 새 gp가 시작되었는지 체크한다. 또한 qs 상태를 체크하고 패스된 경우 rdp에 기록하여 상위 노드로 보고하게 한다.
- 코드 라인 11에서 gp가 끝나고 새로운 gp가 시작되었는지 체크한다.
- 코드 라인 17~18에서 현재 cpu에 대한 qs 체크가 필요 없으면 함수를 빠져나간다.
- 코드 라인 24~26에서 qs가 패스되지 않았더라도 아직 gp가 시작되지 않았으므로 함수를 빠져나간다.
- 코드 라인 32에서 현재 cpu의 qs가 패스되었는지 확인하고 패스된 경우 rcu_data에 기록하고 해당 노드에 보고한다.
note_gp_changes()
kernel/rcu/tree.c
static void note_gp_changes(struct rcu_state *rsp, struct rcu_data *rdp)
{
unsigned long flags;
bool needwake;
struct rcu_node *rnp;
local_irq_save(flags);
rnp = rdp->mynode;
if ((rdp->gpnum == ACCESS_ONCE(rnp->gpnum) &&
rdp->completed == ACCESS_ONCE(rnp->completed) &&
!unlikely(ACCESS_ONCE(rdp->gpwrap))) || /* w/out lock. */
!raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */
local_irq_restore(flags);
return;
}
smp_mb__after_unlock_lock();
needwake = __note_gp_changes(rsp, rnp, rdp);
raw_spin_unlock_irqrestore(&rnp->lock, flags);
if (needwake)
rcu_gp_kthread_wake(rsp);
}
next 리스트에 등록된 콜백들에 대해 completed 번호 식별을 한다. gp 상태에 변화가 있는지를 체크한다. gp kthread를 깨운다.
- 코드 라인 9~15에서 로컬 gpnum과 completed가 이미 갱신되었고 gpwrap이 0이거나 노드 락을 잡을 수 없는 경우 다음 기회로 미룬다.
- 코드 라인 17에서 next 리스트에 등록된 콜백들에 대해 completed 번호 식별을 한다.
- 코드 라인 19~20에서 gp 상태에 변화가 있는지를 체크한다. 변화가 있으면 gp kthread를 깨운다.
__note_gp_changes()
kernel/rcu/tree.c
/*
* Update CPU-local rcu_data state to record the beginnings and ends of
* grace periods. The caller must hold the ->lock of the leaf rcu_node
* structure corresponding to the current CPU, and must have irqs disabled.
* Returns true if the grace-period kthread needs to be awakened.
*/
static bool __note_gp_changes(struct rcu_state *rsp, struct rcu_node *rnp,
struct rcu_data *rdp)
{
bool ret;
/* Handle the ends of any preceding grace periods first. */
if (rdp->completed == rnp->completed &&
!unlikely(ACCESS_ONCE(rdp->gpwrap))) {
/* No grace period end, so just accelerate recent callbacks. */
ret = rcu_accelerate_cbs(rsp, rnp, rdp);
} else {
/* Advance callbacks. */
ret = rcu_advance_cbs(rsp, rnp, rdp);
/* Remember that we saw this grace-period completion. */
rdp->completed = rnp->completed;
trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuend"));
}
if (rdp->gpnum != rnp->gpnum || unlikely(ACCESS_ONCE(rdp->gpwrap))) {
/*
* If the current grace period is waiting for this CPU,
* set up to detect a quiescent state, otherwise don't
* go looking for one.
*/
rdp->gpnum = rnp->gpnum;
trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpustart"));
rdp->passed_quiesce = 0;
rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr);
rdp->qs_pending = !!(rnp->qsmask & rdp->grpmask);
zero_cpu_stall_ticks(rdp);
ACCESS_ONCE(rdp->gpwrap) = false;
}
return ret;
}
next 리스트에 등록된 콜백들에 대해 completed 번호 식별을 한다. 그런 후 gp 상태에 변화가 있는지를 체크한다. gp kthread를 깨울 수 있도록 gp 상태가 변경된 경우 true를 반환한다.
- 코드 라인 13~17에서 gp가 완료되지 않은 상태이다. 이러한 경우 새롭게 진입한 콜백들의 completed 번호 식별을 수행한다. gp 상태에 변화가 있는 경우 true를 반환한다.
- 코드 라인 19~27에서 gp가 완료된 상태이다. 모든 기존 콜백 및 추가된 콜백들에 대해 식별 처리 후 done 구간으로 옮긴다. 그런 후 로컬completed를 갱신하고 gp 상태에 변화가 있는 경우 true를 반환한다.
- 코드 라인 29~42에서 로컬 gpnum이 갱신되지 않았거나 gp가 진행 중에 있는 경우 로컬 gpnum을 갱신하고 로컬 qs 상태를 0으로 한다. 로컬 gpwrap을 false로 갱신한다.
RCU Cascading 처리
rcu_advance_cbs()
kernel/rcu/tree.c
/*
* Move any callbacks whose grace period has completed to the
* RCU_DONE_TAIL sublist, then compact the remaining sublists and
* assign ->completed numbers to any callbacks in the RCU_NEXT_TAIL
* sublist. This function is idempotent, so it does not hurt to
* invoke it repeatedly. As long as it is not invoked -too- often...
* Returns true if the RCU grace-period kthread needs to be awakened.
*
* The caller must hold rnp->lock with interrupts disabled.
*/
static bool rcu_advance_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
struct rcu_data *rdp)
{
int i, j;
/* If the CPU has no callbacks, nothing to do. */
if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
return false;
/*
* Find all callbacks whose ->completed numbers indicate that they
* are ready to invoke, and put them into the RCU_DONE_TAIL sublist.
*/
for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
if (ULONG_CMP_LT(rnp->completed, rdp->nxtcompleted[i]))
break;
rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[i];
}
/* Clean up any sublist tail pointers that were misordered above. */
for (j = RCU_WAIT_TAIL; j < i; j++)
rdp->nxttail[j] = rdp->nxttail[RCU_DONE_TAIL];
/* Copy down callbacks to fill in empty sublists. */
for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
if (rdp->nxttail[j] == rdp->nxttail[RCU_NEXT_TAIL])
break;
rdp->nxttail[j] = rdp->nxttail[i];
rdp->nxtcompleted[j] = rdp->nxtcompleted[i];
}
/* Classify any remaining callbacks. */
return rcu_accelerate_cbs(rsp, rnp, rdp);
}
콜백들을 앞쪽으로 옮기는 cascade 처리를 수행한다. gp가 만료된 콜백들을 done 구간으로 옮기고, wait 구간이 빈 경우 next-ready 구간의 콜백들을 wait구간으로 옮긴다. 신규 진입한 콜백들의 경우 동일한 completed 발급번호를 사용하는 구간이 있으면 그 구간(wait or next-ready)과 합치는 acceleration작업도 수행한다. gp kthread를 깨워야 하는 경우 true를 반환한다.
- 코드 라인 17~18에서 done 구간 이후에 처리할 콜백이 없으면 false를 반환한다.
- nxttail[RCU_NEXT_TAIL]에 null이 있는 경우 no-cb 콜백 처리를 사용하는 cpu이다.
- 코드 라인 24~28에서 wait 구간과 next 구간에 이미 만료된 completed 번호의 콜백을 done 구간으로 옮긴다.
- rnp->completed < rdp->nxtcompleted[]인 경우는 gp가 아직 완료되지 않아 처리할 수 없는 콜백들이다.
- 코드 라인 30~31에서 위에서 wait 구간 또는 next 구간에 콜백들이 있었던 경우 wait tail 또는 next ready tail이 done tail 보다 앞서 있을 수 있다. 따라서 해당 구간을 일단 done tail과 동일하게 조정한다.
- 코드 라인 34~39에서 next ready 구간에 있었던 콜백들을 wait 구간으로 옮긴다.
- 코드 라인 42에서 next 구역에 새로 추가된 콜백들이 wait 또는 next-ready 구간에서 처리될 수 있는 경우 next 구간의 콜백들을 해당 구간으로 옮겨 합친다. (acceleration)
다음 그림은 rnp->completed=101이 되는 순간 wait 구간에서 대기하던 101번까지의 콜백들이 모두 done 구간으로 옮겨진다. 그리고 다음 구간들이 한 단계씩 앞으로 이동하게되는 것을 알 수 있다. 아직 rcu_accelerate_cbs() 함수를 호출하기 전까지의 상황을 표현하였고 다음 코드에서 계속해서 알아본다.
신규 콜백들의 cascade 처리
rcu_accelerate_cbs()
kernel/rcu/tree.c -1/2-
/*
* If there is room, assign a ->completed number to any callbacks on
* this CPU that have not already been assigned. Also accelerate any
* callbacks that were previously assigned a ->completed number that has
* since proven to be too conservative, which can happen if callbacks get
* assigned a ->completed number while RCU is idle, but with reference to
* a non-root rcu_node structure. This function is idempotent, so it does
* not hurt to call it repeatedly. Returns an flag saying that we should
* awaken the RCU grace-period kthread.
*
* The caller must hold rnp->lock with interrupts disabled.
*/
static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
struct rcu_data *rdp)
{
unsigned long c;
int i;
bool ret;
/* If the CPU has no callbacks, nothing to do. */
if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
return false;
/*
* Starting from the sublist containing the callbacks most
* recently assigned a ->completed number and working down, find the
* first sublist that is not assignable to an upcoming grace period.
* Such a sublist has something in it (first two tests) and has
* a ->completed number assigned that will complete sooner than
* the ->completed number for newly arrived callbacks (last test).
*
* The key point is that any later sublist can be assigned the
* same ->completed number as the newly arrived callbacks, which
* means that the callbacks in any of these later sublist can be
* grouped into a single sublist, whether or not they have already
* been assigned a ->completed number.
*/
c = rcu_cbs_completed(rsp, rnp);
for (i = RCU_NEXT_TAIL - 1; i > RCU_DONE_TAIL; i--)
if (rdp->nxttail[i] != rdp->nxttail[i - 1] &&
!ULONG_CMP_GE(rdp->nxtcompleted[i], c))
break;
이 함수에서는 next 구간에 새로 진입한 콜백들이 여건이 되면 next-ready 또는 더 나아가 wait 구간으로 옮겨 빠르게 처리할 수 있도록 앞당긴다.(acceleration). rcu gp kthread를 깨워햐 하는 경우 true를 반환한다.
- 코드 라인 21~22에서 done 구간 뒤 대기중인 콜백이 하나도 없는 경우 false를 반환한다.
- 로컬 cpu가 no-cb로 지정된 경우 콜백 대기 리스트(nxtlist)를 사용하지 않는다.
- done 구간 뒤로 대기중인 콜백이 하나도 없으면 *rdp->nxttail[RCU_DONE_TAIL] == null이다.
- 코드 라인 38에서 completed 번호를 부여하지 않은 각 구간을 위해 새 completed 번호로 사용하기 위해 c를 구해온다.
- 이 구간들에 존재하는 콜백들은 completed 번호와 동일한 gpnum이 완료된 후 처리된다.
- 각 구간에 속한 콜백들의 completed 번호는 동일하고 4개 엔트리로 구성된 nxtcompleted[] 배열에 각 completed 번호가 저장된다.
- 코드 라인 39~42에서 NEXT_READY(2) 구간과 WAIT(1) 구간에 대해 역순회한다. 만일 assign된 콜백들이 존재하면 루프를 벗어난다.
kernel/rcu/tree.c -2/2-
/*
* If there are no sublist for unassigned callbacks, leave.
* At the same time, advance "i" one sublist, so that "i" will
* index into the sublist where all the remaining callbacks should
* be grouped into.
*/
if (++i >= RCU_NEXT_TAIL)
return false;
/*
* Assign all subsequent callbacks' ->completed number to the next
* full grace period and group them all in the sublist initially
* indexed by "i".
*/
for (; i <= RCU_NEXT_TAIL; i++) {
rdp->nxttail[i] = rdp->nxttail[RCU_NEXT_TAIL];
rdp->nxtcompleted[i] = c;
}
/* Record any needed additional grace periods. */
ret = rcu_start_future_gp(rnp, rdp, NULL);
/* Trace depending on how much we were able to accelerate. */
if (!*rdp->nxttail[RCU_WAIT_TAIL])
trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccWaitCB"));
else
trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccReadyCB"));
return ret;
}
- 코드 라인 7~8에서 wait 및 next-ready 구간에서 대기하는 콜백들이 이미 assign된 콜백이라면 추가된 신규 콜백들을 acceleration 할 수 없으므로 false를 반환하고 함수를 빠져나간다.
- 코드 라인 15~18에서 next 구간의 콜백들을 wait 또는 next-ready 구간에 통합하여 한꺼번에 nextcompleted[i]에 새로 사용할 completed 번호로 대입한다.
- 코드 라인 20에서 다음 gp를 시작해야 하는지 알아온다.
콜백용 completed 번호 발급
rcu_cbs_completed()
kernel/rcu/tree.c
/*
* Determine the value that ->completed will have at the end of the
* next subsequent grace period. This is used to tag callbacks so that
* a CPU can invoke callbacks in a timely fashion even if that CPU has
* been dyntick-idle for an extended period with callbacks under the
* influence of RCU_FAST_NO_HZ.
*
* The caller must hold rnp->lock with interrupts disabled.
*/
static unsigned long rcu_cbs_completed(struct rcu_state *rsp,
struct rcu_node *rnp)
{
/*
* If RCU is idle, we just wait for the next grace period.
* But we can only be sure that RCU is idle if we are looking
* at the root rcu_node structure -- otherwise, a new grace
* period might have started, but just not yet gotten around
* to initializing the current non-root rcu_node structure.
*/
if (rcu_get_root(rsp) == rnp && rnp->gpnum == rnp->completed)
return rnp->completed + 1;
/*
* Otherwise, wait for a possible partial grace period and
* then the subsequent full grace period.
*/
return rnp->completed + 2;
}
콜백들의 completed 번호 발급을 위해 다음 gp 번호 값을 반환한다.
- 코드 라인 20~21에서 rcu idling 중, 즉 다음 gp가 시작되지 않은 상태이면 completed 번호에 1을 추가한 값을 반환한다.
- gp가 시작되지 않았고 rcu idling이라는 것을 노드 정보로만 빠르게 확인할 수 있는 조건은 다음과 같다.
- 현재 cpu가 루트 rcu 노드에 포함된 경우만 더 빠른 파악이 가능하다.
- 그리고 진행 중인 노드의 gpnum이 노드의 completed와 동일한 경우이면 gp가 완료된 후 새로운 gp가 시작되지 않았음을 의미한다. (= rcu idle)
- 예) 로컬 cpu가 루트 노드에 포함되었고, 노드의 complete=100, 노드의 gpnum=100인 경우
- 다음 추가되는 콜백들을 위한 completed 값으로 다음에 시작될 101번 gp가 완료된 후 처리가 되도록 101번을 부여한다.
- 참고로 로컬 노드가 루트노드에 포함되었다는 말은 cpu가 16이내의 구성에서만 가능하다.
- gp가 시작되지 않았고 rcu idling이라는 것을 노드 정보로만 빠르게 확인할 수 있는 조건은 다음과 같다.
- 코드 라인 27에서 루트 노드를 통해 rcu idling이 확인되지 않거나 그 밖의 경우 gp가 진행중인 것으로 가정한다. 이 때에는 노드의 completed 번호에 +2를 하여 반환한다.
- 현재 노드 gp(partial gp)가 진행 중에 있다. 이러한 경우 콜백들에 부여할 complete 번호로 노드 completed에 2를 더한 값을 반환한다.
- 그 이외에 cpu가 16개를 초과하는 경우도 무조건 completed+2를 발급한다. (보수적으로 발급한다)
- 예) 노드 complete=100, 노드 gpnum=101
- 다음 추가되는 콜백들을 위한 completed 값으로 다음에 시작될 102번 gp가 완료된 후 처리가 되도록 102번을 부여한다.
다음 그림은 해당 cpu가 루트 노드에 포함되었다고 가정한 모습을 보여준다. 아래 하늘색 구간에서 콜백들이 추가되면 101번 gp가 끝나고 처리되도록 completed 번호로 101번을 발급한다.
cpu_needs_another_gp()
kernel/rcu/tree.c
/*
* Does the current CPU require a not-yet-started grace period?
* The caller must have disabled interrupts to prevent races with
* normal callback registry.
*/
static int
cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
{
int i;
if (rcu_gp_in_progress(rsp))
return 0; /* No, a grace period is already in progress. */
if (rcu_future_needs_gp(rsp))
return 1; /* Yes, a no-CBs CPU needs one. */
if (!rdp->nxttail[RCU_NEXT_TAIL])
return 0; /* No, this is a no-CBs (or offline) CPU. */
if (*rdp->nxttail[RCU_NEXT_READY_TAIL])
return 1; /* Yes, this CPU has newly registered callbacks. */
for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
if (rdp->nxttail[i - 1] != rdp->nxttail[i] &&
ULONG_CMP_LT(ACCESS_ONCE(rsp->completed),
rdp->nxtcompleted[i]))
return 1; /* Yes, CBs for future grace period. */
return 0; /* No grace period needed. */
}
새로운 gp가 시작되어야 하는지 체크한다. (true=new gp 필요)
- 코드 라인 11~12에서 아직 gp가 진행 중인 경우 새 gp를 시작할 필요가 없으므로 0을 반환한다.
- 코드 라인 13~14에서 gp가 필요한 경우라면 1을 반환한다.
- 코드 라인 15~16에서 no-cb cpu이거나 cpu가 offline인 경우 0을 반환한다.
- NEXT_TAIL 포인터가 null로 설정된 경우는 no-cb cpu인 경우이므로 이 곳에 콜백들을 추가하지 않는다.
- 아래 그림에서 case A)
- 코드 라인 17~18에서 NEXT 구간에 처리할 콜백이 있는 경우 1을 반환한다.
- 아래 그림에서 case B-2)
- 코드 라인 19~23에서 wait 및 next ready 구간에 추후 처리할 콜백들이 있는 경우 1을 반환한다.
- new gp 또는 new+1 gp에서 처리할 콜백들이 있고, current GP가 완료된 경우 새 gp를 시작해도 되므로 1을 반환한다.
- 아래 그림에서 case C)
구조체
rcu_state 구조체
kernel/rcu/tree.h – 1/2
/*
* RCU global state, including node hierarchy. This hierarchy is
* represented in "heap" form in a dense array. The root (first level)
* of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
* level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]),
* and the third level in ->node[m+1] and following (->node[m+1] referenced
* by ->level[2]). The number of levels is determined by the number of
* CPUs and by CONFIG_RCU_FANOUT. Small systems will have a "hierarchy"
* consisting of a single rcu_node.
*/
struct rcu_state {
struct rcu_node node[NUM_RCU_NODES]; /* Hierarchy. */
struct rcu_node *level[RCU_NUM_LVLS]; /* Hierarchy levels. */
u32 levelcnt[MAX_RCU_LVLS + 1]; /* # nodes in each level. */
u8 levelspread[RCU_NUM_LVLS]; /* kids/node in each level. */
u8 flavor_mask; /* bit in flavor mask. */
struct rcu_data __percpu *rda; /* pointer of percu rcu_data. */
void (*call)(struct rcu_head *head, /* call_rcu() flavor. */
void (*func)(struct rcu_head *head));
/* The following fields are guarded by the root rcu_node's lock. */
u8 fqs_state ____cacheline_internodealigned_in_smp;
/* Force QS state. */
u8 boost; /* Subject to priority boost. */
unsigned long gpnum; /* Current gp number. */
unsigned long completed; /* # of last completed gp. */
struct task_struct *gp_kthread; /* Task for grace periods. */
wait_queue_head_t gp_wq; /* Where GP task waits. */
short gp_flags; /* Commands for GP task. */
short gp_state; /* GP kthread sleep state. */
/* End of fields guarded by root rcu_node's lock. */
raw_spinlock_t orphan_lock ____cacheline_internodealigned_in_smp;
/* Protect following fields. */
struct rcu_head *orphan_nxtlist; /* Orphaned callbacks that */
/* need a grace period. */
struct rcu_head **orphan_nxttail; /* Tail of above. */
struct rcu_head *orphan_donelist; /* Orphaned callbacks that */
/* are ready to invoke. */
struct rcu_head **orphan_donetail; /* Tail of above. */
long qlen_lazy; /* Number of lazy callbacks. */
long qlen; /* Total number of callbacks. */
/* End of fields guarded by orphan_lock. */
struct mutex onoff_mutex; /* Coordinate hotplug & GPs. */
struct mutex barrier_mutex; /* Guards barrier fields. */
atomic_t barrier_cpu_count; /* # CPUs waiting on. */
struct completion barrier_completion; /* Wake at barrier end. */
unsigned long n_barrier_done; /* ++ at start and end of */
/* _rcu_barrier(). */
/* End of fields guarded by barrier_mutex. */
- node[]
- 컴파일 타임에 산출된 NUM_RCU_NODES 수 만큼 rcu_node 들이 배열에 배치된다.
- *level[]
- 각 레벨의 (0(top) 레벨부터 최대 3레벨까지) 첫 rcu_node를 가리킨다.
- 최소 노드가 1개 이상 존재하므로 level[0]는 항상 node[0]를 가리킨다.
- 노드가 2개 이상되면 level[1]은 node[1]을 가리킨다.
- levelcnt[]
- 각 노드 레벨(0(top) 레벨 ~ 최대 3레벨)에서 사용된 노드 수
- levelspread[]
- 각 노드 레벨이 관리하는 서브 노드의 수
- flavor_mask
- rcu_state가 등록될 때 마다 비트가 설정된다.
- 첫 rcu_state 등록 시 1부터 시작하여 다음 rcu_state가 등록되면 3이 되고, 마지막 rcu_state가 등록되면 7이 된다.
- rcu_state가 rcu_sched와 rcu_bh만 운영되면 3으로 끝나고, rcu_preempt도 추가된 경우 7이 마지막이다.
- *rda
- rcu_data를 가리키는 per-cpu 포인터이다.
- *call
- 각각의 rcu_state는 call_rcu_sched(), call_rcu_bh(), call_rcu_preempt() 콜백 함수 중 하나씩이 등록되어 있다.
- fqs_state
- force quiscent state의 상태로 5가지로 분류되어 있다. 그 중 사용되는 것은 3가지이다.
- RCU_GP_IDLE(0) -> 사용
- RCU_GP_INIT(1)
- RCU_SAVE_DYNTICK(2) -> 사용
- RCU_FORCE_QS(3) -> 사용
- RCU_SIGNAL_INIT(4)
- force quiscent state의 상태로 5가지로 분류되어 있다. 그 중 사용되는 것은 3가지이다.
- boost
- CONFIG_RCU_BOOST 커널 옵션을 사용하여 rcu boost 기능을 사용하는 경우 rcu boost kthread를 동작시키고 1로 설정된다.
- rcu boost 커널 스레드는 “rcub/<node #>”로 표기된다.
- gpnum
- 현재 grace period 번호
- gpnum은 gp가 시작할 때마다 1씩 증가한다.
- overflow에 관련된 에러가 발생하는 것에 대해 빠르게 감지하기 위해 -300UL부터 시작한다.
- completed
- 마지막 완료된 gp 번호
- completed는 언제나 gpnum 또는 gpnum-1과 같다.
- overflow에 관련된 에러가 발생하는 것에 대해 빠르게 감지하기 위해 -300UL부터 시작한다.
- gp_kthread
- grace period를 관리하는 커널 스레드이다.
- 각각의 rcu_state에 따른 “rcu_sched”, “rcu_bh”, “rcu_preempt” 라는 이름을 사용한다.
- gp_wq
- gp 커널 스레드가 대기하는 wait queue이다.
- gp_flags
- gp 커널 스레드에 대한 명령이다.
- 2개의 gp 플래그를 사용한다.
- RCU_GP_FLAG_INIT(0x1) -> gp 시작 필요
- RCU_GP_FLAG_FQS(0x2) -> fqs 필요
- gp_state
- gp 커널 스레드의 sleep 상태이다.
- 3개의 gp 상태 중 2개를 사용한다.
- RCU_GP_WAIT_INIT(0) – 초기 상태
- RCU_GP_WAIT_GPS(1) -> gp 시작 대기 -> 사용
- RCU_GP_WAIT_FQS(2) -> fqs 대기 -> 사용
- orphan_lock
- dead cpu 처리를 위해 고아 리스트에 추가될 콜백 관리를 위해 사용되는 락
- *orphan_nxtlist
- gp 후에 처리할 고아 콜백들이 담기는 리스트
- **orphan_nxttail
- gp 후에 처리할 고아 콜백들의 마지막 콜백을 가리킨다.
- *orphan_donelist
- gp 완료되어 처리 가능한 고아 콜백들이 담기는 리스트
- **orphan_donetail
- gp 완료되어 처리 가능한 고아 콜백들 중 마지막 콜백을 가리킨다.
- qlen_lazy
- lazy 콜백 수
- qlen
- 콜백 수
kernel/rcu/tree.h – 2/2
atomic_long_t expedited_start; /* Starting ticket. */
atomic_long_t expedited_done; /* Done ticket. */
atomic_long_t expedited_wrap; /* # near-wrap incidents. */
atomic_long_t expedited_tryfail; /* # acquisition failures. */
atomic_long_t expedited_workdone1; /* # done by others #1. */
atomic_long_t expedited_workdone2; /* # done by others #2. */
atomic_long_t expedited_normal; /* # fallbacks to normal. */
atomic_long_t expedited_stoppedcpus; /* # successful stop_cpus. */
atomic_long_t expedited_done_tries; /* # tries to update _done. */
atomic_long_t expedited_done_lost; /* # times beaten to _done. */
atomic_long_t expedited_done_exit; /* # times exited _done loop. */
unsigned long jiffies_force_qs; /* Time at which to invoke */
/* force_quiescent_state(). */
unsigned long n_force_qs; /* Number of calls to */
/* force_quiescent_state(). */
unsigned long n_force_qs_lh; /* ~Number of calls leaving */
/* due to lock unavailable. */
unsigned long n_force_qs_ngp; /* Number of calls leaving */
/* due to no GP active. */
unsigned long gp_start; /* Time at which GP started, */
/* but in jiffies. */
unsigned long gp_activity; /* Time of last GP kthread */
/* activity in jiffies. */
unsigned long jiffies_stall; /* Time at which to check */
/* for CPU stalls. */
unsigned long jiffies_resched; /* Time at which to resched */
/* a reluctant CPU. */
unsigned long n_force_qs_gpstart; /* Snapshot of n_force_qs at */
/* GP start. */
unsigned long gp_max; /* Maximum GP duration in */
/* jiffies. */
const char *name; /* Name of structure. */
char abbr; /* Abbreviated name. */
struct list_head flavors; /* List of RCU flavors. */
};
- jiffies_force_qs
- force_quiescent_state() -> gp kthread -> rcu_gp_fqs() 함수를 호출하여 fqs를 해야 할 시각(jiffies)
- gp 커널 스레드가 gp가 완료되지 않아 강제로 fqs를 해야할 때까지 기다릴 시각이 담긴다.
- n_force_qs
- force_quiescent_state() -> gp kthread -> rcu_gp_fqs() 함수를 호출하여 fqs를 수행한 횟수
- n_force_qs_lh
- force_quiescent_state() 함수를 호출할 때 실패 시 n_force_qs_lh를 1 증가
- 실패: 이미 fqs가 진행 중에 있거나 노드 lock contension 상황인 경우
- force_quiescent_state() 함수를 호출할 때 실패 시 n_force_qs_lh를 1 증가
- n_force_qs_ngp
- 현재 증가되지 않고 0
- gp_start
- gp 시작된 시각(jiffies)
- gp_activity
- gp kthread가 동작했던 마지막 시각(jiffies)
- jiffies_stall
- cpu stall을 체크할 시각(jiffies)
- jiffies_resched
- cpu stall을 체크하는 시간의 절반의 시각(jiffies)으로 설정되고 필요에 따라 5 틱씩 증가
- 이 시각이 되면 리스케줄한다.
- n_force_qs_gpstart
- gp가 시작될 때마다 fqs를 수행한 횟수(n_force_qs)로 복사(snapshot)된다.
- gp_max
- 최대 gp 기간(jiffies)
- *name
- rcu 명
- “rcu_sched”, “rcu_bh”, “rcu_preempt”
- abbr
- 축약된 1 자리 rcu 명
- ‘s’, ‘b’, ‘p’
- flavors
- RCU flavors 리스트에 추가될 때 사용하는 list_head
rcu_node 구조체
kernel/rcu/tree.h – 1/2
/*
* Definition for node within the RCU grace-period-detection hierarchy.
*/
struct rcu_node {
raw_spinlock_t lock; /* Root rcu_node's lock protects some */
/* rcu_state fields as well as following. */
unsigned long gpnum; /* Current grace period for this node. */
/* This will either be equal to or one */
/* behind the root rcu_node's gpnum. */
unsigned long completed; /* Last GP completed for this node. */
/* This will either be equal to or one */
/* behind the root rcu_node's gpnum. */
unsigned long qsmask; /* CPUs or groups that need to switch in */
/* order for current grace period to proceed.*/
/* In leaf rcu_node, each bit corresponds to */
/* an rcu_data structure, otherwise, each */
/* bit corresponds to a child rcu_node */
/* structure. */
unsigned long expmask; /* Groups that have ->blkd_tasks */
/* elements that need to drain to allow the */
/* current expedited grace period to */
/* complete (only for PREEMPT_RCU). */
unsigned long qsmaskinit;
/* Per-GP initial value for qsmask & expmask. */
unsigned long grpmask; /* Mask to apply to parent qsmask. */
/* Only one bit will be set in this mask. */
int grplo; /* lowest-numbered CPU or group here. */
int grphi; /* highest-numbered CPU or group here. */
u8 grpnum; /* CPU/group number for next level up. */
u8 level; /* root is at level 0. */
struct rcu_node *parent;
struct list_head blkd_tasks;
/* Tasks blocked in RCU read-side critical */
/* section. Tasks are placed at the head */
/* of this list and age towards the tail. */
struct list_head *gp_tasks;
/* Pointer to the first task blocking the */
/* current grace period, or NULL if there */
/* is no such task. */
struct list_head *exp_tasks;
/* Pointer to the first task blocking the */
/* current expedited grace period, or NULL */
/* if there is no such task. If there */
/* is no current expedited grace period, */
/* then there can cannot be any such task. */
- lock
- rcu 노드 락
- gpnum
- 이 노드에 대한 gp 번호
- 루트 rcu 노드의 gpnum과 같거나 1이 작은 수
- completed
- 이 노드에 대한 completed 번호
- 루트 rcu 노드의 gpnum과 같거나 1이 작은 수
- qsmask
- leaf 노드의 경우 qs를 보고해야 할 rcu_data에 대응하는 비트가 1로 설정된다.
- leaf 노드가 아닌 경우 qs를 보고해야 할 child 노드에 대응하는 비트가 1로 설정된다.
- expmask
- preemptible-rcu에서만 사용되며, 빠른(expedited) grace period가 진행중인 경우 설정된다..
- leaf 노드가 아닌 노드들의 초기값은 qsmaskinit으로한다. (snapshot)
- qsmaskinit
- gp가 시작할 때마다 적용되는 초기값
- qsmask & expmask
- grpmask
- 이 노드가 부모 노드의 qsmask에 대응하는 비트 값이다.
- 예) 512개의 cpu를 위해 루트노드에 32개의 leaf 노드가 있을 때 각 leaf 노드의 grpmask 값은 각각 0x1, 0x2, … 0x8000_0000이다.
- grplo
- 이 노드가 관리하는 시작 cpu 번호
- grphi
- 이 노드가 관리하는 끝 cpu 번호
- grpnum
- 상위 노드에서 볼 때 이 노드에 해당하는 그룹번호(0~31까지)
- grpmask에 설정된 비트 번호와 같다.
- 예) grpmask=0x8000_0000인 경우 bit31이 설정되어 있다. 이러한 경우 grpnum=31이다.
- level
- 이 노드에 해당하는 노드 레벨
- 루트 노드는 0이다.
- 최대 값은 3이다. (최대 4 단계의 레벨 구성이 가능하다)
- *parent
- 부모 노드를 가리킨다.
- blkd_tasks
- read side critical section에서 블럭된 태스크들이 이 리스트에 추가된다.
- *gp_tasks
- 현재 GP를 블러킹하는 첫 번째 태스크(read side critical section에서 블럭)
- exp_tasks
- 현재 빠른(expeditied) GP를 블러킹하는 첫 번째 태스크(read side critical section에서 블럭)
kernel/rcu/tree.h – 2/2
#ifdef CONFIG_RCU_BOOST
struct list_head *boost_tasks;
/* Pointer to first task that needs to be */
/* priority boosted, or NULL if no priority */
/* boosting is needed for this rcu_node */
/* structure. If there are no tasks */
/* queued on this rcu_node structure that */
/* are blocking the current grace period, */
/* there can be no such task. */
struct rt_mutex boost_mtx;
/* Used only for the priority-boosting */
/* side effect, not as a lock. */
unsigned long boost_time;
/* When to start boosting (jiffies). */
struct task_struct *boost_kthread_task;
/* kthread that takes care of priority */
/* boosting for this rcu_node structure. */
unsigned int boost_kthread_status;
/* State of boost_kthread_task for tracing. */
unsigned long n_tasks_boosted;
/* Total number of tasks boosted. */
unsigned long n_exp_boosts;
/* Number of tasks boosted for expedited GP. */
unsigned long n_normal_boosts;
/* Number of tasks boosted for normal GP. */
unsigned long n_balk_blkd_tasks;
/* Refused to boost: no blocked tasks. */
unsigned long n_balk_exp_gp_tasks;
/* Refused to boost: nothing blocking GP. */
unsigned long n_balk_boost_tasks;
/* Refused to boost: already boosting. */
unsigned long n_balk_notblocked;
/* Refused to boost: RCU RS CS still running. */
unsigned long n_balk_notyet;
/* Refused to boost: not yet time. */
unsigned long n_balk_nos;
/* Refused to boost: not sure why, though. */
/* This can happen due to race conditions. */
#endif /* #ifdef CONFIG_RCU_BOOST */
#ifdef CONFIG_RCU_NOCB_CPU
wait_queue_head_t nocb_gp_wq[2];
/* Place for rcu_nocb_kthread() to wait GP. */
#endif /* #ifdef CONFIG_RCU_NOCB_CPU */
int need_future_gp[2];
/* Counts of upcoming no-CB GP requests. */
raw_spinlock_t fqslock ____cacheline_internodealigned_in_smp;
} ____cacheline_internodealigned_in_smp;
- *boost_tasks
- priority 부스트가 필요한 첫 태스크
- boost_mtx
- priority 부스트에 사용되는 락
- *boost_kthread_task
- 이 노드에서 priority 부스트를 수행하는 boost 커널 스레드
- boost_kthread_status
- boost_kthread_task trace를 위한 상태
- n_tasks_boosted
- priority 부스트된 태스크들의 수
- = n_exp_boosts + n_normal_boosts
- n_exp_boosts
- expedited gp를 위해 부스트된 태스크들의 수
- n_normal_boosts
- 일반 gp를 위해 부스트된 태스크들의 수
- nocb_gp_wq[]
- 2 개의 no-cb용 커널 스레드의 대기큐
- need_future_gp[]
- gp 요청을 위해 no-cb용 콜백이 진입된 수
- fqslock
- fqs용 lock
rcu_data 구조체
kernel/rcu/tree.h – 1/2
/* Per-CPU data for read-copy update. */
struct rcu_data {
/* 1) quiescent-state and grace-period handling : */
unsigned long completed; /* Track rsp->completed gp number */
/* in order to detect GP end. */
unsigned long gpnum; /* Highest gp number that this CPU */
/* is aware of having started. */
unsigned long rcu_qs_ctr_snap;/* Snapshot of rcu_qs_ctr to check */
/* for rcu_all_qs() invocations. */
bool passed_quiesce; /* User-mode/idle loop etc. */
bool qs_pending; /* Core waits for quiesc state. */
bool beenonline; /* CPU online at least once. */
bool gpwrap; /* Possible gpnum/completed wrap. */
struct rcu_node *mynode; /* This CPU's leaf of hierarchy */
unsigned long grpmask; /* Mask to apply to leaf qsmask. */
#ifdef CONFIG_RCU_CPU_STALL_INFO
unsigned long ticks_this_gp; /* The number of scheduling-clock */
/* ticks this CPU has handled */
/* during and after the last grace */
/* period it is aware of. */
#endif /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
/* 2) batch handling */
/*
* If nxtlist is not NULL, it is partitioned as follows.
* Any of the partitions might be empty, in which case the
* pointer to that partition will be equal to the pointer for
* the following partition. When the list is empty, all of
* the nxttail elements point to the ->nxtlist pointer itself,
* which in that case is NULL.
*
* [nxtlist, *nxttail[RCU_DONE_TAIL]):
* Entries that batch # <= ->completed
* The grace period for these entries has completed, and
* the other grace-period-completed entries may be moved
* here temporarily in rcu_process_callbacks().
* [*nxttail[RCU_DONE_TAIL], *nxttail[RCU_WAIT_TAIL]):
* Entries that batch # <= ->completed - 1: waiting for current GP
* [*nxttail[RCU_WAIT_TAIL], *nxttail[RCU_NEXT_READY_TAIL]):
* Entries known to have arrived before current GP ended
* [*nxttail[RCU_NEXT_READY_TAIL], *nxttail[RCU_NEXT_TAIL]):
* Entries that might have arrived after current GP ended
* Note that the value of *nxttail[RCU_NEXT_TAIL] will
* always be NULL, as this is the end of the list.
*/
struct rcu_head *nxtlist;
struct rcu_head **nxttail[RCU_NEXT_SIZE];
unsigned long nxtcompleted[RCU_NEXT_SIZE];
/* grace periods for sublists. */
long qlen_lazy; /* # of lazy queued callbacks */
long qlen; /* # of queued callbacks, incl lazy */
long qlen_last_fqs_check;
/* qlen at last check for QS forcing */
unsigned long n_cbs_invoked; /* count of RCU cbs invoked. */
unsigned long n_nocbs_invoked; /* count of no-CBs RCU cbs invoked. */
unsigned long n_cbs_orphaned; /* RCU cbs orphaned by dying CPU */
unsigned long n_cbs_adopted; /* RCU cbs adopted from dying CPU */
unsigned long n_force_qs_snap;
/* did other CPU force QS recently? */
long blimit; /* Upper limit on a processed batch */
qs와 gp 핸들링 관련
- completed
- gp의 종료를 검출하기 위해 rsp->completed gp 번호를 추적한다.
- gpnum
- 이 cpu가 인식한 가장 높은 gp 번호
- rcu_qs_ctr_snap
- rcu_qs_ctr의 복사(snapshot)본으로 rcu_all_qs() 함수가 호출되었는지 여부를 체크할 때 사용한다.
- rcu_all_qs() 함수 호출 시 rcu_qs_ctr을 1 증가시켜 rcu_qs_ctr_snap과 값이 달라진다.
- rcu_qs_ctr의 복사(snapshot)본으로 rcu_all_qs() 함수가 호출되었는지 여부를 체크할 때 사용한다.
- passed_quiesce
- 유저 모드 또는 idle 루프에서 진입한 경우 이 값을 1로하여 qs가 pass되었음을 의미하게 한다.
- qs_pending
- qs를 체크하기 위해 기다려야 하는 cpu의 경우 1이 설정된다.
- beenonline
- 한 번이라도 online 되었었던 경우 1로 설정된다.
- gpwrap
- *mynode
- 이 cpu를 관리하는 노드
- grpmask
- 이 cpu가 해당 leaf 노드의 qsmask에 대응하는 비트 값으로 qs 패스되면 leaf 노드의 qsmask에 반영한다.
- 예) 노드 당 16개의 cpu가 사용될 수 있으며 각각의 cpu에 대해 0x1, 0x2, … 0x1_0000 값이 배치된다.
- ticks_this_gp
- 마지막 gp 이후 구동된 스케줄 틱 수
- CONFIG_RCU_CPU_STALL_INFO 커널 옵션을 사용한 경우 cpu stall 정보의 출력을 위해 사용된다.
배치 핸들링
- *nxtlist
- 콜백들이 추가되는 리스트이다.
- **nxttail[]
- 위 nxtlist에 등록된 콜백들에 대해 4개의 구간 배열로 나누어 각 구간에 등록된 마지막 콜백을 가리킨다.
- 완료(done) 구간
- 대기(wait) 구간
- 다음 준비(next ready) 구간
- 다음 (next) 구간
- 해당 구간에 콜백이 없는 경우 앞 구간의 마지막 콜백을 가리킨다.
- nxtlist에 어떠한 콜백도 없는 경우 nxttail[] 배열의 모든 값은 nxtlist를 가리킨다.
- nxttail[] 값이 null인 경우 no-cb용 cpu는 여기서 콜백 처리하지 않는다.
- 위 nxtlist에 등록된 콜백들에 대해 4개의 구간 배열로 나누어 각 구간에 등록된 마지막 콜백을 가리킨다.
- nxtcompleted[]
- 4개의 각 구간에 해당하는 다음 처리될 completed 번호가 담긴다.
- 이 값이 rdp->completed 번호 이하인 경우 해당 콜백의 gp가 끝난 것이기 때문에 콜백을 처리할 수 있다.
- qlen_lazy
- lazy 큐된 콜백 수
- qlen
- 큐된 콜백 수 (qlen_lazy도 포함)
- qlen_last_fqs_check
- fqs를 위해 마지막 체크시 사용할 qlen 값
- n_cbs_invoked
- rcu 콜백들이 호출되어 처리된 수
- n_nocbs_invoked
- rcu no-cb용 cpu에서 콜백들이 호출되어 처리된 수
- n_cbs_orphaned
- cpu가 offline되면서 고아가된 콜백 수
- n_cbs_adopted
- 고아 콜백들로 부터 채용된 콜백 수
- n_force_qs_snap
- n_force_qs가 복사된 값으로 최근에 fqs가 수행되었는지 확인하기 위해 사용된다.
- blimit
- 콜백을 처리할 수 있는 배치 수
- 빠른 인터럽트 latency를 보장하게 하기 위해 콜백들이 많은 경우 한 번에 blimit 이하의 콜백들만 처리하게 한다.
kernel/rcu/tree.h – 2/2
/* 3) dynticks interface. */
struct rcu_dynticks *dynticks; /* Shared per-CPU dynticks state. */
int dynticks_snap; /* Per-GP tracking for dynticks. */
/* 4) reasons this CPU needed to be kicked by force_quiescent_state */
unsigned long dynticks_fqs; /* Kicked due to dynticks idle. */
unsigned long offline_fqs; /* Kicked due to being offline. */
unsigned long cond_resched_completed;
/* Grace period that needs help */
/* from cond_resched(). */
/* 5) __rcu_pending() statistics. */
unsigned long n_rcu_pending; /* rcu_pending() calls since boot. */
unsigned long n_rp_qs_pending;
unsigned long n_rp_report_qs;
unsigned long n_rp_cb_ready;
unsigned long n_rp_cpu_needs_gp;
unsigned long n_rp_gp_completed;
unsigned long n_rp_gp_started;
unsigned long n_rp_nocb_defer_wakeup;
unsigned long n_rp_need_nothing;
/* 6) _rcu_barrier() and OOM callbacks. */
struct rcu_head barrier_head;
#ifdef CONFIG_RCU_FAST_NO_HZ
struct rcu_head oom_head;
#endif /* #ifdef CONFIG_RCU_FAST_NO_HZ */
/* 7) Callback offloading. */
#ifdef CONFIG_RCU_NOCB_CPU
struct rcu_head *nocb_head; /* CBs waiting for kthread. */
struct rcu_head **nocb_tail;
atomic_long_t nocb_q_count; /* # CBs waiting for nocb */
atomic_long_t nocb_q_count_lazy; /* invocation (all stages). */
struct rcu_head *nocb_follower_head; /* CBs ready to invoke. */
struct rcu_head **nocb_follower_tail;
wait_queue_head_t nocb_wq; /* For nocb kthreads to sleep on. */
struct task_struct *nocb_kthread;
int nocb_defer_wakeup; /* Defer wakeup of nocb_kthread. */
/* The following fields are used by the leader, hence own cacheline. */
struct rcu_head *nocb_gp_head ____cacheline_internodealigned_in_smp;
/* CBs waiting for GP. */
struct rcu_head **nocb_gp_tail;
bool nocb_leader_sleep; /* Is the nocb leader thread asleep? */
struct rcu_data *nocb_next_follower;
/* Next follower in wakeup chain. */
/* The following fields are used by the follower, hence new cachline. */
struct rcu_data *nocb_leader ____cacheline_internodealigned_in_smp;
/* Leader CPU takes GP-end wakeups. */
#endif /* #ifdef CONFIG_RCU_NOCB_CPU */
/* 8) RCU CPU stall data. */
#ifdef CONFIG_RCU_CPU_STALL_INFO
unsigned int softirq_snap; /* Snapshot of softirq activity. */
#endif /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
int cpu;
struct rcu_state *rsp;
};
dynticks(nohz) 인터페이스
- *dynticks
- per-cpu로 구성된 전역 rcu_dynticks에 연결된다.
- no-hz에서 qs상태를 관리하기 위해 사용한다.
- dynticks_snap
- dynticks->dynticks 값을 복사해두고 카운터 값이 변동이 있는지 확인하기 위해 사용된다.
fqs 동작 이유
- dynticks_fqs
- nohz idle로 인해 암묵적으로 fqs 처리될 때마다 증가되는 카운터로 trace 목적으로 사용된다.
- offline_fqs
- offline cpu들로 인해 암묵적으로 fqs 처리될 때마다 증가되는 카운터로 trace 목적으로 사용된다.
- cond_resched_completed
- nohz ilde 진입 시 cpu를 관리하는 노드의 completed 번호가 백업되며 이 값이 변경되는 경우 qs처리를 skip하기 위해 사용한다.
rcu_pending() 함수내에서 조건에 맞을 때마다 증가되는 카운터들로 trace 목적
- n_rcu_pending
- 부팅 이후로 rcu_pending() 함수가 호출된 수
- n_rp_qs_pending
- qs가 패스되지 않았지만 qs 상태 체크할 때가 아니면 이 값을 증가시킨다.
- n_rp_report_qs
- qs가 패스되어 보고해야 할 때 이 값을 증가시킨다.
- n_rp_cb_ready
- 콜백이 추가되어 준비가 된 경우 이 값을 증가시킨다.
- n_rp_cpu_needs_gp
- 새로운 gp가 필요해지면 이 값을 증가시킨다.
- n_rp_gp_completed
- 현재 cpu에서 gp가 완료되어 처리해야 할 때 이 값을 증가시킨다.
- n_rp_gp_started()
- 새로운 gp가 시작된 경우 이 값을 증가시킨다.
- n_rp_nocb_defer_wakeup
- no-cb 커널 스레드 깨우기가 유예되는 경우 이 값을 증가시킨다.
- n_rp_need_nothing
- rcu_pending() 함수 마지막까지 도달하여 rcu_core를 호출해야 할 이유가 없는 경우에 이 값을 증가시킨다.
아래의 멤버들은 no-cb 관련되었다.
- *nocb_head
- no-cb용 콜백들이 추가되는 리스트이다.
- **nocb_tail
- 마지막 콜백을 가리킨다.
- nocb_q_count
- 대기 중인 no-cb 콜백 수
- nocb_q_count_lazy
- lazy 대기 중인 no-cb 콜백 수
- *nocb_follower_head
- 리스트에서 호출 가능한 콜백의 선두
- *nocb_follower_tail
- 리스트에서 호출 가능한 콜백의 마지막
- nocb_wq
- no-cb용 커널 스레드용 wait queue
- nocb_kthread
- no-cb용 커널 스레드를 가리킨다.
- nocb_defer_wakeup
- no-cb용 커널 스레드를 깨우는 것에 대한 유예 상태
- RCU_NOGP_WAKE_NOT(0)
- RCU_NOGP_WAKE(1)
- RCU_NOGP_WAKE_FORCE(2)
- no-cb용 커널 스레드를 깨우는 것에 대한 유예 상태
- *nocb_gp_head
- gp 종료를 기다리는 콜백 리스트
- **nocb_gp_tail
- gp 종료를 기다리는 마지막 콜백을 가리킨다.
- nocb_leader_sleep
- no-cb 커널 스레드의 슬립 상태
- *nocb_next_follower
- follower cpu(rcu_data)
- *nocb_leader
- leader cpu(rcu_data)
기타
- softirq_snap
- cpu stall 정보를 출력할 때 사용하기 위해 rcu softirq 카운터 값 복사(snap-shot)
- CONFIG_RCU_CPU_STALL_INFO 커널 옵션 필요
- cpu
- cpu 번호
- *rsp
- rcu_state를 가리키는 포인터
참고
- RCU(Read Copy Update) -1- (Basic) | 문c
- RCU(Read Copy Update) -2- (Callback process) | 문c – 현재글
- RCU(Read Copy Update) -3- (RCU threads) | 문c
- RCU(Read Copy Update) -4- (NOCB process) | 문c
- rcu_init() | 문c
- wait_for_completion() | 문c