<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