RCU(Read Copy Update) -2- (Callback process)

 

RCU(Read Copy Update) -2- (Callback process)

 

RCU 동기 Update

synchronize_rcu()

kernel/rcu/tree_plugin.h

/**
 * 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.
 *
 * See the description of synchronize_sched() for more detailed information
 * on memory ordering guarantees.
 */
void synchronize_rcu(void)
{
        rcu_lockdep_assert(!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_scheduler_active)
                return;
        if (rcu_expedited)
                synchronize_rcu_expedited();
        else
                wait_rcu_gp(call_rcu);
}
EXPORT_SYMBOL_GPL(synchronize_rcu);

grace period가 지날때까지 기다린다.

  • if (!rcu_scheduler_active) return;
    • 아직 rcu 스케쥴러가 동작하지 않는 경우 처리를 포기하고 함수를 빠져나온다.
  • if (rcu_expedited) synchronize_rcu_expedited(); else  wait_rcu_gp(call_rcu);
    • /sys/kernel/rcu_expedited 값이 설정된 경우 일반 RCU grace period 방법을 사용하는 대신 더 신속한 Brute-force RCU grace period 방법을 사용한다.
    • 그렇지 않은 경우 일반 RCU grace period 방법을 사용한다.

 

다음 그림은 동기화 rcu 요청 함수인 synchronize_rcu() 및 비동기 rcu 요청 함수인 call_rcu() 함수 두 가지에 대해 각각 호출 경로를 보여준다.

  • 3 가지 gp 사용에 대한 동기 및 비동기 API 경로(rcu_preemp, rcu_sched, rcu_bh)별로 총 6개의 API 경로를 보여준다.
  • 3 가지 gp 사용 각각에 대해 동기화 API를 사용하면 다음 두 가지 경로가 나뉜다.
    • Brute-force RCU gp wait을 사용하는 함수 호출 경로
    • 일반 gp wait을 이용하는 함수 호출 경로

 

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 리스트에 콜백이 존재하면 처리한다.

 

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]이 추가된 마지막 콜백을 항상 가리키게 해야한다.

  • 일반적인 콜백 진행은 위와 같지만 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를 진행한다.

 

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가 소요되는 단점이 있다.

 

메모리가 충분하지 않은 특정 임베디드 시스템에서 부트 타임에 gp kthread가 동작하지 전까지 메모리의 clean-up이 지연되어 발생하는 OOM을 막기 위해 CONFIG_RCU_EXPEDITE_BOOT 커널 옵션을 사용하여 부트 타임에 expedited gp 방식으로 동작하게 할 수 있다. “echo 0 > /sys/kernel/rcu_expedited”을 사용하여 normal gp 방식으로 전환할 수 있다. (gp 커널 스레드가 동작해야 하므로 normal 전환에 시간이 걸리는 점을 유의해야한다.)

 

expedited gp는 rcu_sched와 rcu_preempt에서 구현되어 있다. rcu_bh에서는 rcu_sched를 호출하여 사용한다.

 

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이내의 구성에서만 가능하다.
  • 코드 라인 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)
  • 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 상황인 경우
  • 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과 값이 달라진다.
  • 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는 여기서 콜백 처리하지 않는다.
  • 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)
  • *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를 가리키는 포인터

 

참고

댓글 남기기

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