RCU(Read Copy Update) -3-

RCU(Read Copy Update) -3-

다음과 같은 내용을 분석해본다.

  • rcu와 관련된 커널 스레드들을 생성하는 과정
  • grace period의 시작과 끝을 관리하는 rcu_gp_kthread의 분석
  • quiescent state 및 force 처리

 

RCU 관련 스레드 생성

rcu_spawn_gp_kthread()

kernel/rcu/tree.c

/*
 * Spawn the kthreads that handle each RCU flavor's grace periods.
 */
static int __init rcu_spawn_gp_kthread(void)
{
        unsigned long flags;
        int kthread_prio_in = kthread_prio;
        struct rcu_node *rnp;
        struct rcu_state *rsp;
        struct sched_param sp;
        struct task_struct *t;

        /* Force priority into range. */
        if (IS_ENABLED(CONFIG_RCU_BOOST) && kthread_prio < 1)
                kthread_prio = 1;
        else if (kthread_prio < 0)
                kthread_prio = 0;
        else if (kthread_prio > 99)
                kthread_prio = 99;
        if (kthread_prio != kthread_prio_in)
                pr_alert("rcu_spawn_gp_kthread(): Limited prio to %d from %d\n",
                         kthread_prio, kthread_prio_in);

        rcu_scheduler_fully_active = 1;
        for_each_rcu_flavor(rsp) {
                t = kthread_create(rcu_gp_kthread, rsp, "%s", rsp->name);
                BUG_ON(IS_ERR(t));
                rnp = rcu_get_root(rsp);
                raw_spin_lock_irqsave(&rnp->lock, flags);
                rsp->gp_kthread = t;
                if (kthread_prio) {
                        sp.sched_priority = kthread_prio;
                        sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
                }
                wake_up_process(t);
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
        }
        rcu_spawn_nocb_kthreads();
        rcu_spawn_boost_kthreads();
        return 0;
}
early_initcall(rcu_spawn_gp_kthread);
  • 코드 라인 14~22에서 rcu 커널 스레드의 우선 순위가 0~99 범위를 벗어나지 않도록 조정한다. rcu boost 기능을 사용하는 경우에는 preempt된 rcu가 가장 빠르게 처리될 수 있도록 0번 우선 순위를 사용하므로 rcu 커널 스레드들이 0번 우선 순위를 사용하지 않게 한다.
  • 코드 라인 24~37에서 커널이 사용하는 rcu state 수 만큼 반복하여 rcu_gp_kthread를 생성한다. 생성 시에 SCHED_FIFO 정책을 사용하는 RT 스레드를 사용한다.
    • rcu_gp_kthread 태스크명: [rcu_sched], [rcu_bh], [rcu_preempt]
  • 코드 라인 38에서 rcu state 곱하기 no-cb 설정된 online cpu 수 만큼 rcu_nocb_kthread를 생성하고 동작시킨다.
    • rcu_nocb_kthread 태스크명: [rcuo<state>/<cpu>]
      • <rcu state>
        • “s”=rcu_sched
        • “b”=rcu_bh
        • “p”=rcu_preempt
    • 예) [rcuos/0], [rcuos/1], …, [rcuob/0], [rcuob/1], …, [rcuop/0], [rcuop/1], …
  • 코드 라인 39에서 rcu_cpu_kthread를 cpu 수 만큼 생성한다. 그리고 rcu boost 기능을 사용하는 경우 leaf 노드 수 만큼 rcu_boost_kthread 들도 생성하고 동작시킨다. 이들은 SCHED_FIFO 스레드로 생성시킨다.
    • rcu_cpu_kthread 태스크명: [rcuc/<cpu>]
    • 예) [rcuc/0], [rcuc/1], …
    • rcu_boost_kthread 태스크명: [rcub/<rcu leaf node 인덱스>]
    • 예) [rcub/0], [rcub/1], …

 

다음 그림은 rcu 관련 스레드들을 생성시키는 함수들간의 호출 관계를 보여준다.

 

gp 커널 스레드의 우선 순위

kernel/rcu/tree.c

/* rcuc/rcub kthread realtime priority */
static int kthread_prio = CONFIG_RCU_KTHREAD_PRIO;
module_param(kthread_prio, int, 0644);

SCHED_FIFO 정책을 사용하는 RCU 워커 스레드를 위한 우선 순위이다. 디폴트 값으로 가장 빠른 우선 순위(0 또는 1)를 사용하는데 RCU_BOOST 커널 옵션이 사용되는 경우에는 0번을 비워둔다. 사용자가 설정하여 커널을 빌드할 수 있는 값은 최대 99까지이다.

 

rcu_spawn_nocb_kthreads()

kernel/rcu/tree_plugin.h

/*
 * Once the scheduler is running, spawn rcuo kthreads for all online
 * no-CBs CPUs.  This assumes that the early_initcall()s happen before
 * non-boot CPUs come online -- if this changes, we will need to add
 * some mutual exclusion.
 */
static void __init rcu_spawn_nocb_kthreads(void)
{
        int cpu;

        for_each_online_cpu(cpu)
                rcu_spawn_all_nocb_kthreads(cpu);
}

online cpu들 수 만큼 각각의 rcu state 에 해당하는 no-cb용 커널 스레드들을 생성시킨다.

 

/*
 * If the specified CPU is a no-CBs CPU that does not already have its
 * rcuo kthreads, spawn them.
 */
static void rcu_spawn_all_nocb_kthreads(int cpu)
{
        struct rcu_state *rsp;

        if (rcu_scheduler_fully_active) 
                for_each_rcu_flavor(rsp)
                        rcu_spawn_one_nocb_kthread(rsp, cpu); 
}

각각의 rcu state 에 해당하는 no-cb용 커널 스레드들을 생성시킨다.

 

rcu_spawn_one_nocb_kthread()

kernel/rcu/tree_plugin.h

/*
 * If the specified CPU is a no-CBs CPU that does not already have its
 * rcuo kthread for the specified RCU flavor, spawn it.  If the CPUs are
 * brought online out of order, this can require re-organizing the
 * leader-follower relationships.
 */
static void rcu_spawn_one_nocb_kthread(struct rcu_state *rsp, int cpu)
{
        struct rcu_data *rdp;
        struct rcu_data *rdp_last;
        struct rcu_data *rdp_old_leader;
        struct rcu_data *rdp_spawn = per_cpu_ptr(rsp->rda, cpu);
        struct task_struct *t;

        /*
         * If this isn't a no-CBs CPU or if it already has an rcuo kthread,
         * then nothing to do.
         */
        if (!rcu_is_nocb_cpu(cpu) || rdp_spawn->nocb_kthread)
                return;

        /* If we didn't spawn the leader first, reorganize! */
        rdp_old_leader = rdp_spawn->nocb_leader;
        if (rdp_old_leader != rdp_spawn && !rdp_old_leader->nocb_kthread) {
                rdp_last = NULL;
                rdp = rdp_old_leader;
                do {
                        rdp->nocb_leader = rdp_spawn;
                        if (rdp_last && rdp != rdp_spawn)
                                rdp_last->nocb_next_follower = rdp;
                        if (rdp == rdp_spawn) {
                                rdp = rdp->nocb_next_follower;
                        } else {
                                rdp_last = rdp;
                                rdp = rdp->nocb_next_follower;
                                rdp_last->nocb_next_follower = NULL;
                        }
                } while (rdp);
                rdp_spawn->nocb_next_follower = rdp_old_leader;
        }

        /* Spawn the kthread for this CPU and RCU flavor. */
        t = kthread_run(rcu_nocb_kthread, rdp_spawn,
                        "rcuo%c/%d", rsp->abbr, cpu);
        BUG_ON(IS_ERR(t));
        ACCESS_ONCE(rdp_spawn->nocb_kthread) = t;
}

해당 rcu state 및 cpu에 해당하는 no-cb용 커널 스레드를 생성시킨다.

 

rcu_spawn_boost_kthreads()

kernel/rcu/tree_plugin.h

/*
 * Spawn boost kthreads -- called as soon as the scheduler is running.
 */
static void __init rcu_spawn_boost_kthreads(void)
{
        struct rcu_node *rnp;
        int cpu;

        for_each_possible_cpu(cpu)
                per_cpu(rcu_cpu_has_work, cpu) = 0;
        BUG_ON(smpboot_register_percpu_thread(&rcu_cpu_thread_spec));
        rcu_for_each_leaf_node(rcu_state_p, rnp) 
                (void)rcu_spawn_one_boost_kthread(rcu_state_p, rnp);
}

rcu_cpu_kthread를 online cpu 수 만큼 생성한다. 그리고 rcu boost 기능을 사용하는 경우 leaf 노드 수 만큼 rcu_boost_kthread 들도 생성하고 동작시킨다. 이들은 SCHED_FIFO 스레드로 생성시킨다.

 

rcu_spawn_one_boost_kthread()

kernel/rcu/tree_plugin.h

/*
 * Create an RCU-boost kthread for the specified node if one does not
 * already exist.  We only create this kthread for preemptible RCU.
 * Returns zero if all is well, a negated errno otherwise.
 */
static int rcu_spawn_one_boost_kthread(struct rcu_state *rsp,
                                                 struct rcu_node *rnp)
{
        int rnp_index = rnp - &rsp->node[0];
        unsigned long flags;
        struct sched_param sp;
        struct task_struct *t;

        if (&rcu_preempt_state != rsp)
                return 0;

        if (!rcu_scheduler_fully_active || rnp->qsmaskinit == 0)
                return 0;

        rsp->boost = 1;
        if (rnp->boost_kthread_task != NULL)
                return 0;
        t = kthread_create(rcu_boost_kthread, (void *)rnp,
                           "rcub/%d", rnp_index);
        if (IS_ERR(t))
                return PTR_ERR(t);
        raw_spin_lock_irqsave(&rnp->lock, flags);
        smp_mb__after_unlock_lock();
        rnp->boost_kthread_task = t;
        raw_spin_unlock_irqrestore(&rnp->lock, flags);
        sp.sched_priority = kthread_prio;
        sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
        wake_up_process(t); /* get to TASK_INTERRUPTIBLE quickly. */
        return 0;
}

rcu boost 기능을 위해 leaf 노드 수 만큼 rcu_boost_kthread 들도 생성하고 동작시킨다. 이들은 SCHED_FIFO 스레드로 생성시킨다.

 

Grace Period를 관리하는 커널 스레드

rcu gp 커널 스레드는 새 gp를 시작하는 rcu_gp_init() 함수와 gp를 종료 처리하는 rcu_gp_cleanup() 함수를 무한 반복한다. 장 시간 gp가 hang하는 경우 rcu_gp_fqs() 함수를 통해 강제로 모든 cpu의 qs 상태를 강제로 패스시켜 gp를 종료할 수 있게 한다.

 

다음 그림은 rcu_gp_kthread() 함수내에서 사용하는 gp 상태(gp_state), gp 플래그(gp_flags), fqs 상태(fqs_state)의 변화를 보여준다.

rcu_gp_kthread()

kernel/rcu/tree.c -1/2-

/*
 * Body of kthread that handles grace periods.
 */
static int __noreturn rcu_gp_kthread(void *arg)
{
        int fqs_state;
        int gf;
        unsigned long j;
        int ret;
        struct rcu_state *rsp = arg;
        struct rcu_node *rnp = rcu_get_root(rsp);

        for (;;) {

                /* Handle grace-period start. */
                for (;;) {
                        trace_rcu_grace_period(rsp->name,
                                               ACCESS_ONCE(rsp->gpnum),
                                               TPS("reqwait"));
                        rsp->gp_state = RCU_GP_WAIT_GPS;
                        wait_event_interruptible(rsp->gp_wq,
                                                 ACCESS_ONCE(rsp->gp_flags) &
                                                 RCU_GP_FLAG_INIT);
                        /* Locking provides needed memory barrier. */
                        if (rcu_gp_init(rsp))
                                break;
                        cond_resched_rcu_qs();
                        ACCESS_ONCE(rsp->gp_activity) = jiffies;
                        WARN_ON(signal_pending(current));
                        trace_rcu_grace_period(rsp->name,
                                               ACCESS_ONCE(rsp->gpnum),
                                               TPS("reqwaitsig"));
                }

                /* Handle quiescent-state forcing. */
                fqs_state = RCU_SAVE_DYNTICK;
                j = jiffies_till_first_fqs;
                if (j > HZ) {
                        j = HZ;
                        jiffies_till_first_fqs = HZ;
                }

rcu grace period를 관리하기 위한 커널 스레드로 무한 루프를 돌며 외부에서 state가 바뀔 때마다 깨어나 gp 상태를 처리한다.

  • 코드 라인 16~33에서 gp 상태를 RCU_GP_WAIT_GPS로 설정한 후 RCU_GP_FLAG_INIT 상태로 바뀌기를 대기한다. 즉 gp가 시작되기를 대기한다.
  • 코드 라인 36~41에서 첫 번째 fqs인 RCU_SAVE_DYNTICK을 기다릴 시간이 1초에 해당하는 틱을 초과한 경우 1초에 해당하는 틱 수로 제한한다.

 

kernel/rcu/tree.c -2/2-

                ret = 0;
                for (;;) {
                        if (!ret)
                                rsp->jiffies_force_qs = jiffies + j;
                        trace_rcu_grace_period(rsp->name,
                                               ACCESS_ONCE(rsp->gpnum),
                                               TPS("fqswait"));
                        rsp->gp_state = RCU_GP_WAIT_FQS;
                        ret = wait_event_interruptible_timeout(rsp->gp_wq,
                                        ((gf = ACCESS_ONCE(rsp->gp_flags)) &
                                         RCU_GP_FLAG_FQS) ||
                                        (!ACCESS_ONCE(rnp->qsmask) &&
                                         !rcu_preempt_blocked_readers_cgp(rnp)),
                                        j);
                        /* Locking provides needed memory barriers. */
                        /* If grace period done, leave loop. */
                        if (!ACCESS_ONCE(rnp->qsmask) &&
                            !rcu_preempt_blocked_readers_cgp(rnp))
                                break;
                        /* If time for quiescent-state forcing, do it. */
                        if (ULONG_CMP_GE(jiffies, rsp->jiffies_force_qs) ||
                            (gf & RCU_GP_FLAG_FQS)) {
                                trace_rcu_grace_period(rsp->name,
                                                       ACCESS_ONCE(rsp->gpnum),
                                                       TPS("fqsstart"));
                                fqs_state = rcu_gp_fqs(rsp, fqs_state);
                                trace_rcu_grace_period(rsp->name,
                                                       ACCESS_ONCE(rsp->gpnum),
                                                       TPS("fqsend"));
                                cond_resched_rcu_qs();
                                ACCESS_ONCE(rsp->gp_activity) = jiffies;
                        } else {
                                /* Deal with stray signal. */
                                cond_resched_rcu_qs();
                                ACCESS_ONCE(rsp->gp_activity) = jiffies;
                                WARN_ON(signal_pending(current));
                                trace_rcu_grace_period(rsp->name,
                                                       ACCESS_ONCE(rsp->gpnum),
                                                       TPS("fqswaitsig"));
                        }
                        j = jiffies_till_next_fqs;
                        if (j > HZ) {
                                j = HZ;
                                jiffies_till_next_fqs = HZ;
                        } else if (j < 1) {
                                j = 1;
                                jiffies_till_next_fqs = 1;
                        }
                }

                /* Handle grace-period end. */
                rcu_gp_cleanup(rsp);
        }
}

gp가 시작된 후에는 gp가 만료될 때까지 루프를 돌며 대기한다. 그런 후 gp가 만료되면 gp 클린업 처리 후 다시 가장 바깥 루프로 나가서 다시 처음부터 무한 반복한다.

  • 코드 라인 1~4에서 fqs 상태가 완료될 때까지 대기할 만료 시각을 준비한다.
  • 코드 라인 8~14에서 gp 상태를  RCU_GP_WAIT_FQS로 바꾼 후 RCU_GP_FLAG_FQS 플래그가 준비될 때까지 기다린다.
  • 코드 라인 17~19에서 이미 모든 cpu의 qs가 패스된 경우 gp를 종료 처리하기 위해 루프를 벗어난다.
  • 코드 라인 21~31에서 너무 오랜 시간을 gp가 지속되는 경우 cpu가 gp hang으로 인식하여 이를 강제로 모든 cpu의 qs 상태를 pass 상태로 바꾸게 한다.
  • 코드 라인 32~40에서 qs 상태등을 체크한다.
  • 코드 라인 41~48에서 fqs 대기 시간을 조정하고 다시 모든 cpu의 qs가 만료될 때까지 기다리기 위해 루프를 돈다.
    • 최소=1틱, 최대 1초
  • 코드 라인 52에서 현재 gp를 종료 처리한 후 다시 새 gp를 시작하기 위해 루프를 돈다.

 

rcu_preempt_blocked_readers_cgp()

kernel/rcu/tree_plugin.h

/*
 * Check for preempted RCU readers blocking the current grace period
 * for the specified rcu_node structure.  If the caller needs a reliable
 * answer, it must hold the rcu_node's ->lock.
 */
static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
{
        return rnp->gp_tasks != NULL;
}

rcu 노드 내에서 선점형 rcu 리더가 블러킹되었는지 체크한다.

 

Grace Period 시작 처리

rcu_gp_init()

kernel/rcu/tree.c

/*
 * Initialize a new grace period.  Return 0 if no grace period required.
 */
static int rcu_gp_init(struct rcu_state *rsp)
{
        struct rcu_data *rdp;
        struct rcu_node *rnp = rcu_get_root(rsp);

        ACCESS_ONCE(rsp->gp_activity) = jiffies;
        rcu_bind_gp_kthread();
        raw_spin_lock_irq(&rnp->lock);
        smp_mb__after_unlock_lock();
        if (!ACCESS_ONCE(rsp->gp_flags)) {
                /* Spurious wakeup, tell caller to go back to sleep.  */
                raw_spin_unlock_irq(&rnp->lock);
                return 0;
        }
        ACCESS_ONCE(rsp->gp_flags) = 0; /* Clear all flags: New grace period. */

        if (WARN_ON_ONCE(rcu_gp_in_progress(rsp))) {
                /*
                 * Grace period already in progress, don't start another.
                 * Not supposed to be able to happen.
                 */
                raw_spin_unlock_irq(&rnp->lock);
                return 0;
        }

        /* Advance to a new grace period and initialize state. */
        record_gp_stall_check_time(rsp);
        /* Record GP times before starting GP, hence smp_store_release(). */
        smp_store_release(&rsp->gpnum, rsp->gpnum + 1);
        trace_rcu_grace_period(rsp->name, rsp->gpnum, TPS("start"));
        raw_spin_unlock_irq(&rnp->lock);

새로운 grace period의 시작 처리를 수행한다. 이 때 rsp->gpnum이 1 증가된다.

  • 코드 라인 10에서 nohz full 을 위해 현재 태스크를 timekeeping 처리를 하는 cpu들에서만 동작하도록 제한시킨다.
  • 코드 라인 11~18에서 노드 락을 걸고 gp 플래그를 클리어한다. 만일 gp 플래그가 0인 상태라면(현재 상태에서 변경 없이 깨어났을 때) 다시 sleep 하도록 노드락을 풀고 0을 반환한다.
  • 코드 라인 20~27에서 만일 rcu가 이미 진행 중인 상태라면 경고 메시지를 출력하고 노드 락을 풀고 0을 반환한다.
  • 코드 라인 30에서 gp stall 여부 체크를 위해 시간을 gp 시작 시간을 기록해둔다.
    • CONFIG_RCU_STALL_COMMON 커널 옵션을 사용하는 경우 장시간 동안 gp가 끝나지 않으면 stall이 된 것으로 판단하여 강제로 gp 종료 처리를 하기 위해 사용한다.
  • 코드 라인 32~35에서 gp 번호를 1 증가시키고 노드 락을 푼다.

 

        /* Exclude any concurrent CPU-hotplug operations. */
        mutex_lock(&rsp->onoff_mutex);
        smp_mb__after_unlock_lock(); /* ->gpnum increment before GP! */

        /*
         * Set the quiescent-state-needed bits in all the rcu_node
         * structures for all currently online CPUs in breadth-first order,
         * starting from the root rcu_node structure, relying on the layout
         * of the tree within the rsp->node[] array.  Note that other CPUs
         * will access only the leaves of the hierarchy, thus seeing that no
         * grace period is in progress, at least until the corresponding
         * leaf node has been initialized.  In addition, we have excluded
         * CPU-hotplug operations.
         *
         * The grace period cannot complete until the initialization
         * process finishes, because this kthread handles both.
         */
        rcu_for_each_node_breadth_first(rsp, rnp) {
                raw_spin_lock_irq(&rnp->lock);
                smp_mb__after_unlock_lock();
                rdp = this_cpu_ptr(rsp->rda);
                rcu_preempt_check_blocked_tasks(rnp);
                rnp->qsmask = rnp->qsmaskinit;
                ACCESS_ONCE(rnp->gpnum) = rsp->gpnum;
                WARN_ON_ONCE(rnp->completed != rsp->completed);
                ACCESS_ONCE(rnp->completed) = rsp->completed;
                if (rnp == rdp->mynode)
                        (void)__note_gp_changes(rsp, rnp, rdp);
                rcu_preempt_boost_start_gp(rnp);
                trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
                                            rnp->level, rnp->grplo,
                                            rnp->grphi, rnp->qsmask);
                raw_spin_unlock_irq(&rnp->lock);
                cond_resched_rcu_qs();
                ACCESS_ONCE(rsp->gp_activity) = jiffies;
        }

        mutex_unlock(&rsp->onoff_mutex);
        return 1;
}
  • 코드 라인 18~23에서 모든 노드를 순회하며 qsmask를 qsmaskinit 값으로 초기화한다.
    • qsmaskinit
      • online cpu 비트마스크로 online/offline에 반응하여 갱신된다.
    • rcu_cleanup_dead_cpu()
      • 특정 cpu가 offline 될 때 호출된다.
    • rcu_cleanup_dead_rnp()
      • 특정 노드에 소속된 모든 cpu가 offline될 때 호출된다.
  • 코드 라인 24~26에서 노드의 gpnum과 completed를 갱신한다.
  • 코드 라인 27~28에서 현재 cpu에 해당하는 노드인 경우 해당 cpu의 next 리스트에 등록된 콜백들에 대해 completed 번호 식별을 한다. 그리고 gp 상태에 변화가 있는지를 체크한다.
  • 코드 라인 29에서 priority boost 기능을 위해 gp 후에 delay boosting할 노드의 boost 타임을 지정한다.
  • 코드 라인 34에서 우선 리스케줄링 요청이 없는 경우 현재 cpu의 rcu_qs_ctr을 1 증가시킨다. 또한 nohz idle을 위해 qs가 pass된 상태이면 rcu core가 알 수 있도록 한다.
  • 코드 라인 35에서 gp 시작 시각을 기록한다.

 

Quiscent State 체크 및 리포트

 

qs의 보고 순서는 다음 그림과 같다.

  • local cpu -> rdp(rcu_data) -> rnp(rcu_node) -> rsp(rcu_state) -> gp 스레드(gp 종료 및 new gp 시작)
    • rnp(rcu_node)는 하이라키 구조로되어 있으므로 최상위 루트 노드까지 qs의 pass가 완료되면 rsp(rcu_state)에 보고한다.

 

다음 그림에서는 36개의 cpu에 대한 rnp(rcu_node) 보고와 관련된 멤버 변수의 상태를 알 수 있다.

  • grpmask: 현재 노드에 대응하는 상위 노드 비트
  • qsmaskinit: 현재 노드가 취급하는 online cpu 비트마스크로 qs 시작할 때 마다 이 값은 qsmask에 복사된다.
  • qsmask: 노드에 포함된 online cpu 비트마스크로 qs가 pass된 cpu는 0으로 클리어된다.

 

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);
}

grace period 시작 후 로컬 cpu의 첫번째 qs가 지났는지 체크하여 갱신한다.

  • 코드 라인 11에서 gp의 시작과 끝의 변화를 체크한다.
  • 코드 라인 17~18에서 로컬 cpu의 qs 처리가 필요 없으면 함수를 빠져나간다.
    • gp 시작 후 로컬 cpu의 qs가 아직 pass되지 않은 경우 true 상태이다.
  • 코드 라인 24~26에서 로컬 qs가 pass되지 않았지만 gp도 시작한 상태가 아니면 함수를 빠져나간다.
    • rcu_qs_ctr은 user 태스크 수행 중 스케줄 틱이 발생하면 증가된다. 이 값이 snap 값과 동일한 상태라면 아직 qs control이 유효한 상태가 아니다.
  • 코드 라인 32에서 로컬 cpu의 qs 상태를 확인하여 보고한다.

 

rcu_report_qs_rdp()

kernel/rcu/tree.c

/*
 * Record a quiescent state for the specified CPU to that CPU's rcu_data
 * structure.  This must be either called from the specified CPU, or
 * called when the specified CPU is known to be offline (and when it is
 * also known that no other CPU is concurrently trying to help the offline
 * CPU).  The lastcomp argument is used to make sure we are still in the
 * grace period of interest.  We don't want to end the current grace period
 * based on quiescent states detected in an earlier grace period!
 */
static void
rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp)
{
        unsigned long flags;
        unsigned long mask;
        bool needwake;
        struct rcu_node *rnp;

        rnp = rdp->mynode;
        raw_spin_lock_irqsave(&rnp->lock, flags);
        smp_mb__after_unlock_lock();
        if ((rdp->passed_quiesce == 0 &&
             rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) ||
            rdp->gpnum != rnp->gpnum || rnp->completed == rnp->gpnum ||
            rdp->gpwrap) {

                /*
                 * The grace period in which this quiescent state was
                 * recorded has ended, so don't report it upwards.
                 * We will instead need a new quiescent state that lies
                 * within the current grace period.
                 */
                rdp->passed_quiesce = 0;        /* need qs for new gp. */
                rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr);
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
                return;
        }
        mask = rdp->grpmask;
        if ((rnp->qsmask & mask) == 0) {
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
        } else {
                rdp->qs_pending = 0;

                /*
                 * This GP can't end until cpu checks in, so all of our
                 * callbacks can be processed during the next GP.
                 */
                needwake = rcu_accelerate_cbs(rsp, rnp, rdp);

                rcu_report_qs_rnp(mask, rsp, rnp, flags); /* rlses rnp->lock */
                if (needwake)
                        rcu_gp_kthread_wake(rsp);
        }
}

로컬 qs 상태가 pass된 경우 노드에 보고한다.

  • 코드 라인 18~36에서 다음의 조건들 중 하나를 만족하는 경우 qs가 아직 패스되지 않은 상태로 하고, qs 컨트롤을 클리어한다. 그런후 노드 락을 풀고 함수를 빠져나간다.
    • qs가 pass되지 않았지만 qs 컨트롤이 시작되지 않은 경우
    • 로컬 gpnum이 아직 갱신되지 않은 경우
    • 로컬 completed가 다 처리된 경우
    • 로컬 gp가 진행중인 경우
  • 코드 라인 37~52에서 로컬 qs가 이미 패스된 후 처리된 경우 노드 락을 풀고 함수를 빠져나간다. 그렇지 않은 경우 로컬 qs_pending을 클리어하고 새롭게 추가되어 아직 식별되지 않은 콜백들에 대해 completed 번호를 발급한다. 그런 후 노드에 대해 로컬 cpu가 qs 패스된 것을 보고한다. 그리고 gp 상태에 변경이 있는 경우 gp kthread를 깨운다.

 

rcu_report_qs_rnp()

kernel/rcu/tree.c

/*
 * Similar to rcu_report_qs_rdp(), for which it is a helper function.
 * Allows quiescent states for a group of CPUs to be reported at one go
 * to the specified rcu_node structure, though all the CPUs in the group
 * must be represented by the same rcu_node structure (which need not be
 * a leaf rcu_node structure, though it often will be).  That structure's
 * lock must be held upon entry, and it is released before return.
 */
static void
rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp,
                  struct rcu_node *rnp, unsigned long flags)
        __releases(rnp->lock)
{
        struct rcu_node *rnp_c;

        /* Walk up the rcu_node hierarchy. */
        for (;;) {
                if (!(rnp->qsmask & mask)) {

                        /* Our bit has already been cleared, so done. */
                        raw_spin_unlock_irqrestore(&rnp->lock, flags);
                        return;
                }
                rnp->qsmask &= ~mask;
                trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum,
                                                 mask, rnp->qsmask, rnp->level,
                                                 rnp->grplo, rnp->grphi,
                                                 !!rnp->gp_tasks);
                if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {

                        /* Other bits still set at this level, so done. */
                        raw_spin_unlock_irqrestore(&rnp->lock, flags);
                        return;
                }
                mask = rnp->grpmask;
                if (rnp->parent == NULL) {

                        /* No more levels.  Exit loop holding root lock. */

                        break;
                }
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
                rnp_c = rnp;
                rnp = rnp->parent;
                raw_spin_lock_irqsave(&rnp->lock, flags);
                smp_mb__after_unlock_lock();
                WARN_ON_ONCE(rnp_c->qsmask);
        }

        /*
         * Get here if we are the last CPU to pass through a quiescent
         * state for this grace period.  Invoke rcu_report_qs_rsp()
         * to clean up and start the next grace period if one is needed.
         */
        rcu_report_qs_rsp(rsp, flags); /* releases rnp->lock. */
}

현재 cpu의 qs가 완료되어 노드로 보고한다. 노드에 소속된 모든 cpu의 qs가 모두 완료된 경우 부모 노드로 계층을 밟아 올라가면서 최상위까지 처리한다. 최상위에서 모든 cpu의 처리가 완료되었음을 인식하면 해당 state의 gp 커널 스레드를 깨워 새로운 gp를 시작하게 한다.

  • 코드 라인 17~23에서 해당 cpu의 처리가 이미 끝난 경우 함수를 빠져나간다.
  • 코드 라인 24에서 해당 cpu의 qs 처리가 완료되었음을 기록하기 위해 노드의 cpu에 해당하는 비트를 클리어한다.
    • 예) qsmask=0xff, mask=0x20
      • 노드에 8개의 cpu에 대한 qs가 아직 pass되지 않은 상태이다. 이 때 노드 내에 있는 여섯번째 cpu의 qs 처리가 끝났음을 기록하면 qsmask=0xdf가 된다.
  • 코드 라인 29~34에서 노드의 속한 cpu들의 qs가 모두 pass되지 않은 경우 함수를 빠져나간다.
  • 코드 라인 35에서 현재 노드에 속한 cpu들이 모두 pass되었다. 다음 상위 노드를 처리하기 위해 상위 노드에 해당하는 mask를 알아온다.
  • 코드 라인 36~41에서 현재 노드가 루트 노드인 경우 부모 노드가 없다. 이러한 경우 모든 cpu의 qs가 끝난 것이다. 루프를 벗어나 새로운 gp의 시작 처리를 위해 gp 커널 스레드를 깨우도록 한다.
  • 코드 라인 42~48에서 부모 노드를 처리하기 위해 계속 루프를 돈다.
  • 코드 라인 55에서 현재 state의 모든 qs가 끝났으므로 새로운 gp의 시작 처리를 위해 gp 커널 스레드를 깨우도록 한다.

 

rcu_report_qs_rsp()

kernel/rcu/tree.c

/*
 * Report a full set of quiescent states to the specified rcu_state
 * data structure.  This involves cleaning up after the prior grace
 * period and letting rcu_start_gp() start up the next grace period
 * if one is needed.  Note that the caller must hold rnp->lock, which
 * is released before return.
 */
static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
        __releases(rcu_get_root(rsp)->lock)
{
        WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
        raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
        rcu_gp_kthread_wake(rsp);
}

모든 qs가 pass되었으므로 gp를 갱신하기 위해 해당 state의 gp 커널 스레드를 깨워 새로운 gp를 시작하게 한다.

 

Force Quiescent State

gp가 장시간 진행되면 문제(cpu stall)가 생긴것으로 판단하여 강제로 qs를 패스한 것처럼 시도한다. 또한 대기 콜백이 하나도 없는 상태에서 새롭게 진입한 콜백을 빠르게 처리하기 위해 기존 gp를 완료하고 새로운 gp를 처리하기 위해서도 fqs(force quiescent state)를 수행한다.

 

force_quiescent_state()

kernel/rcu/tree.c

/*
 * Force quiescent states on reluctant CPUs, and also detect which
 * CPUs are in dyntick-idle mode.
 */
static void force_quiescent_state(struct rcu_state *rsp)
{
        unsigned long flags;
        bool ret;
        struct rcu_node *rnp;
        struct rcu_node *rnp_old = NULL;

        /* Funnel through hierarchy to reduce memory contention. */
        rnp = __this_cpu_read(rsp->rda->mynode);
        for (; rnp != NULL; rnp = rnp->parent) {
                ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
                      !raw_spin_trylock(&rnp->fqslock);
                if (rnp_old != NULL)
                        raw_spin_unlock(&rnp_old->fqslock);
                if (ret) {
                        rsp->n_force_qs_lh++;
                        return;
                }
                rnp_old = rnp;
        }
        /* rnp_old == rcu_get_root(rsp), rnp == NULL. */

        /* Reached the root of the rcu_node tree, acquire lock. */
        raw_spin_lock_irqsave(&rnp_old->lock, flags);
        smp_mb__after_unlock_lock();
        raw_spin_unlock(&rnp_old->fqslock);
        if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
                rsp->n_force_qs_lh++;
                raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
                return;  /* Someone beat us to it. */
        }
        ACCESS_ONCE(rsp->gp_flags) =
                ACCESS_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS;
        raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
        rcu_gp_kthread_wake(rsp);
}

force quiescent state를 진행시켜 기존 gp를 종료시키고 새로운 gp를 시작하기 위해 시도한다.

  • 코드 라인 13~24에서 요청한 cpu에 해당하는 노드에서 최상위 루트 노드까지 상위로 올라가면서 fqs 락 획득과 해제를 시도한다. 만일 다른 cpu로부터 노드에 이미 fqs 락을 걸어 로컬 cpu에서 락의 획득이 실패한 경우 역시 함수를 빠져나간다. 물론 rsp(rcu_state)에  RCU_GP_FLAG_FQS 플래그가 이미 설정되어 Force Quiescent State를 처리하고 있는 경우 함수를 빠져나간다.
  • 코드 라인 28~30에서 최상위 루트 노드까지 fqs 락을 걸고 풀어보면서 진행을 하였다. 마지막 남은 최상위 루트 노드를 처리하기 위해 노드 락을 획득한 채로 fqs 락을 풀고 노드 락도 푼다.
  • 코드 라인 31~35에서 다시 한 번 최종 확인하는 것으로 rsp(rcu_state)에 이미 RCU_GP_FLAG_FQS가 설정된 경우 함수를 빠져나간다.
  • 코드 라인 36~39에서 gp를 강제로 완료하도록 RCU_GP_FLAG_FQS를 rsp(rcu_state)에 대입하고 최상위 노드의 언락을 푼 후 gp 커널 스레드를 깨워 gp 종료 및 새로운 gp의 시작을 처리하도록 요청한다.

 

rcu_gp_fqs()

kernel/rcu/tree.c

/*
 * Do one round of quiescent-state forcing.
 */
static int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in)
{
        int fqs_state = fqs_state_in;
        bool isidle = false;
        unsigned long maxj;
        struct rcu_node *rnp = rcu_get_root(rsp);

        ACCESS_ONCE(rsp->gp_activity) = jiffies;
        rsp->n_force_qs++;
        if (fqs_state == RCU_SAVE_DYNTICK) {
                /* Collect dyntick-idle snapshots. */
                if (is_sysidle_rcu_state(rsp)) {
                        isidle = true;
                        maxj = jiffies - ULONG_MAX / 4;
                }
                force_qs_rnp(rsp, dyntick_save_progress_counter,
                             &isidle, &maxj);
                rcu_sysidle_report_gp(rsp, isidle, maxj);
                fqs_state = RCU_FORCE_QS;
        } else {
                /* Handle dyntick-idle and offline CPUs. */
                isidle = false;
                force_qs_rnp(rsp, rcu_implicit_dynticks_qs, &isidle, &maxj);
        }
        /* Clear flag to prevent immediate re-entry. */
        if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
                raw_spin_lock_irq(&rnp->lock);
                smp_mb__after_unlock_lock();
                ACCESS_ONCE(rsp->gp_flags) =
                        ACCESS_ONCE(rsp->gp_flags) & ~RCU_GP_FLAG_FQS;
                raw_spin_unlock_irq(&rnp->lock);
        }
        return fqs_state;
}

모든 처리되지 않은 qs들을 강제로 qs 패스된 것으로 처리한다. 두 가지 용도로 함수를 사용하는데

  • 코드 라인 13~22에서 qfs_state_in이 RCU_SAVE_DYNTICK으로 진입한 경우 nohz-idle cpu 상태를 스캔하여 처리한다.
  • 코드 라인 23~27에서 그외의 경우는 판정된 nohz-idle 및 offline cpu들의 fqs 처리를 수행한다.
  • 코드 라인 29~35에서 이미 RCU_GP_FLAG_FQS 플래그가 설정된 경우 다시 재진입하지 않도록 플래그를 제거한다.

 

다음 그림과 같이 좌측은 fqs를 처리하는 함수가 우측의 정상적인 qs 처리 함수를 이용하는 것을 알 수 있다.

 

force_qs_rnp()

kernel/rcu/tree.c

/*
 * Scan the leaf rcu_node structures, processing dyntick state for any that
 * have not yet encountered a quiescent state, using the function specified.
 * Also initiate boosting for any threads blocked on the root rcu_node.
 *
 * The caller must have suppressed start of new grace periods.
 */
static void force_qs_rnp(struct rcu_state *rsp,
                         int (*f)(struct rcu_data *rsp, bool *isidle,
                                  unsigned long *maxj),
                         bool *isidle, unsigned long *maxj)
{
        unsigned long bit;
        int cpu;
        unsigned long flags;
        unsigned long mask;
        struct rcu_node *rnp;

        rcu_for_each_leaf_node(rsp, rnp) {
                cond_resched_rcu_qs();
                mask = 0;
                raw_spin_lock_irqsave(&rnp->lock, flags);
                smp_mb__after_unlock_lock();
                if (!rcu_gp_in_progress(rsp)) {
                        raw_spin_unlock_irqrestore(&rnp->lock, flags);
                        return;
                }
                if (rnp->qsmask == 0) {
                        rcu_initiate_boost(rnp, flags); /* releases rnp->lock */
                        continue;
                }
                cpu = rnp->grplo;
                bit = 1;
                for (; cpu <= rnp->grphi; cpu++, bit <<= 1) {
                        if ((rnp->qsmask & bit) != 0) {
                                if ((rnp->qsmaskinit & bit) != 0)
                                        *isidle = false;
                                if (f(per_cpu_ptr(rsp->rda, cpu), isidle, maxj))
                                        mask |= bit;
                        }
                }
                if (mask != 0) {

                        /* rcu_report_qs_rnp() releases rnp->lock. */
                        rcu_report_qs_rnp(mask, rsp, rnp, flags);
                        continue;
                }
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
        }
}

leaf 노드의 모든 처리되지 않은 qs들을 강제로 qs 패스된 것으로 처리한다. 두 가지 용도로 함수를 사용하는데 qfs_state_in이 RCU_SAVE_DYNTICK으로 진입한 경우 nohz-idle cpu 상태를 스캔하여 처리한다. 그외의 경우는 판정된 nohz-idle 및 offline cpu들의 fqs 처리를 수행한다.

  • 코드 라인 19~20에서 모든 leaf 노드들을 대상으로 순회하며 우선 리스케줄링 요청이 없는 경우 현재 cpu의 rcu_qs_ctr을 1 증가시킨다. 또한 nohz idle을 위해 qs가 pass된 상태이면 rcu core가 알 수 있도록 한다.
  • 코드 라인 22~27에서 노드 락을 건 상태로 gp 진행 상태를 확인하여 이미 gp가 완료된 경우 노드 락을 풀고 함수를 빠져나간다.
  • 코드 라인 28~31에서 노드의 모든 cpu에 대해 qs가 패스된 경우 skip 한다. 또한 boost 처리해야 할 rcu 리더가 있는지 확인하고, 존재 시 부스트한다.
  • 코드 라인 32~41에서 노드가 관리하는 cpu들을 순회하며 해당 cpu의 qs가 아직 패스되지 않은 경우 출력 인수 isidle에 false를 대입한다. 또한 인수로 제공된 다음 함수의 결과가 true인 경우 노드 내 해당 cpu에 대한 비트를 설정한다.
    • nohz-idle cpu 스캔 목적으로 이 함수를 진입한 경우: dyntick_save_progress_counter() 함수를 인수 f로 사용
    • nohz-idle cpu 및 offline cpu들을 처리하기 위해 이 함수를 진입한 경우: rcu_implicit_dynticks_qs() 함수를 인수 f로 사용
  • 코드 라인 42~47에서 mask 설정된 cpu들을 대상으로 qs가 패스된 것으로 보고하게 한다.

 

rcu_initiate_boost()

kernel/rcu/tree.c

/*
 * Check to see if it is time to start boosting RCU readers that are
 * blocking the current grace period, and, if so, tell the per-rcu_node
 * kthread to start boosting them.  If there is an expedited grace
 * period in progress, it is always time to boost.
 *
 * The caller must hold rnp->lock, which this function releases.
 * The ->boost_kthread_task is immortal, so we don't need to worry
 * about it going away.
 */
static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags)
        __releases(rnp->lock)
{
        struct task_struct *t;

        if (!rcu_preempt_blocked_readers_cgp(rnp) && rnp->exp_tasks == NULL) {
                rnp->n_balk_exp_gp_tasks++;
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
                return;
        }
        if (rnp->exp_tasks != NULL ||
            (rnp->gp_tasks != NULL &&
             rnp->boost_tasks == NULL &&
             rnp->qsmask == 0 &&
             ULONG_CMP_GE(jiffies, rnp->boost_time))) {
                if (rnp->exp_tasks == NULL)
                        rnp->boost_tasks = rnp->gp_tasks;
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
                t = rnp->boost_kthread_task;
                if (t)
                        rcu_wake_cond(t, rnp->boost_kthread_status);
        } else {
                rcu_initiate_boost_trace(rnp);
                raw_spin_unlock_irqrestore(&rnp->lock, flags);
        }                   
}

boost 처리해야 할 rcu 리더가 있는지 확인하고, 존재 시 부스트한다.

 

Grace Period 종료 처리

rcu_gp_cleanup()

kernel/rcu/tree.c – 1/2

/*
 * Clean up after the old grace period.
 */
static void rcu_gp_cleanup(struct rcu_state *rsp)
{
        unsigned long gp_duration;
        bool needgp = false;
        int nocb = 0;
        struct rcu_data *rdp;
        struct rcu_node *rnp = rcu_get_root(rsp);

        ACCESS_ONCE(rsp->gp_activity) = jiffies;
        raw_spin_lock_irq(&rnp->lock);
        smp_mb__after_unlock_lock();
        gp_duration = jiffies - rsp->gp_start;
        if (gp_duration > rsp->gp_max)
                rsp->gp_max = gp_duration;

        /*
         * We know the grace period is complete, but to everyone else
         * it appears to still be ongoing.  But it is also the case
         * that to everyone else it looks like there is nothing that
         * they can do to advance the grace period.  It is therefore
         * safe for us to drop the lock in order to mark the grace
         * period as completed in all of the rcu_node structures.
         */
        raw_spin_unlock_irq(&rnp->lock);

현재 gp의 종료 처리를 수행한다.

  • 코드 라인 15~17에서 gp가 진행된 시간을 알아와서 gp_max를 갱신한다.

 

kernel/rcu/tree.c – 2/2

        /*
         * Propagate new ->completed value to rcu_node structures so
         * that other CPUs don't have to wait until the start of the next
         * grace period to process their callbacks.  This also avoids
         * some nasty RCU grace-period initialization races by forcing
         * the end of the current grace period to be completely recorded in
         * all of the rcu_node structures before the beginning of the next
         * grace period is recorded in any of the rcu_node structures.
         */
        rcu_for_each_node_breadth_first(rsp, rnp) {
                raw_spin_lock_irq(&rnp->lock);
                smp_mb__after_unlock_lock();
                ACCESS_ONCE(rnp->completed) = rsp->gpnum;
                rdp = this_cpu_ptr(rsp->rda);
                if (rnp == rdp->mynode)
                        needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
                /* smp_mb() provided by prior unlock-lock pair. */
                nocb += rcu_future_gp_cleanup(rsp, rnp);
                raw_spin_unlock_irq(&rnp->lock);
                cond_resched_rcu_qs();
                ACCESS_ONCE(rsp->gp_activity) = jiffies;
        }
        rnp = rcu_get_root(rsp);
        raw_spin_lock_irq(&rnp->lock);
        smp_mb__after_unlock_lock(); /* Order GP before ->completed update. */
        rcu_nocb_gp_set(rnp, nocb);

        /* Declare grace period done. */
        ACCESS_ONCE(rsp->completed) = rsp->gpnum;
        trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end"));
        rsp->fqs_state = RCU_GP_IDLE;
        rdp = this_cpu_ptr(rsp->rda);
        /* Advance CBs to reduce false positives below. */
        needgp = rcu_advance_cbs(rsp, rnp, rdp) || needgp;
        if (needgp || cpu_needs_another_gp(rsp, rdp)) {
                ACCESS_ONCE(rsp->gp_flags) = RCU_GP_FLAG_INIT;
                trace_rcu_grace_period(rsp->name,
                                       ACCESS_ONCE(rsp->gpnum),
                                       TPS("newreq"));
        }
        raw_spin_unlock_irq(&rnp->lock);
}
  • 코드 라인 10~22에서 모든 노드를 대상으로 completed 번호를 rsp->gpnum으로 대입한다. 또한 노드내 no-cb cpu들에 대해 gp 클린업 처리를 하도록 no-cb 스레드들을 wakeup한다.
  • 코드 라인 29~31에서 rsp->completed 발급 번호를 rsp->gpnum을 대입하여 일치시키고 fqs_state를 RCU_GP_IDLE로 초기화한다.

 

참고

 

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.